The purpose of crash_exclude_mem_range() is to remove all memory ranges
that overlap with [mstart-mend]. However, the current logic only removes
the first overlapping memory range.

Commit a2e9a95d2190 ("kexec: Improve & fix crash_exclude_mem_range() to
handle overlapping ranges") attempted to address this issue, but it did not
fix all error cases.

Let's fix and simplify the logic of crash_exclude_mem_range().

Signed-off-by: Yuntao Wang <ytcoode@gmail.com>
---
 kernel/crash_core.c | 80 ++++++++++++++++-----------------------------
 1 file changed, 29 insertions(+), 51 deletions(-)

diff --git a/kernel/crash_core.c b/kernel/crash_core.c
index efe87d501c8c..c51d0a54296b 100644
--- a/kernel/crash_core.c
+++ b/kernel/crash_core.c
@@ -565,9 +565,8 @@ int crash_prepare_elf64_headers(struct crash_mem *mem, int need_kernel_map,
 int crash_exclude_mem_range(struct crash_mem *mem,
 			    unsigned long long mstart, unsigned long long mend)
 {
-	int i, j;
+	int i;
 	unsigned long long start, end, p_start, p_end;
-	struct range temp_range = {0, 0};
 
 	for (i = 0; i < mem->nr_ranges; i++) {
 		start = mem->ranges[i].start;
@@ -575,72 +574,51 @@ int crash_exclude_mem_range(struct crash_mem *mem,
 		p_start = mstart;
 		p_end = mend;
 
-		if (mstart > end || mend < start)
+		if (p_start > end)
 			continue;
 
+		/*
+		 * Because the memory ranges in mem->ranges are stored in
+		 * ascending order, when we detect `p_end < start`, we can
+		 * immediately exit the for loop, as the subsequent memory
+		 * ranges will definitely be outside the range we are looking
+		 * for.
+		 */
+		if (p_end < start)
+			break;
+
 		/* Truncate any area outside of range */
-		if (mstart < start)
+		if (p_start < start)
 			p_start = start;
-		if (mend > end)
+		if (p_end > end)
 			p_end = end;
 
 		/* Found completely overlapping range */
 		if (p_start == start && p_end == end) {
-			mem->ranges[i].start = 0;
-			mem->ranges[i].end = 0;
-			if (i < mem->nr_ranges - 1) {
-				/* Shift rest of the ranges to left */
-				for (j = i; j < mem->nr_ranges - 1; j++) {
-					mem->ranges[j].start =
-						mem->ranges[j+1].start;
-					mem->ranges[j].end =
-							mem->ranges[j+1].end;
-				}
-
-				/*
-				 * Continue to check if there are another overlapping ranges
-				 * from the current position because of shifting the above
-				 * mem ranges.
-				 */
-				i--;
-				mem->nr_ranges--;
-				continue;
-			}
+			memmove(&mem->ranges[i], &mem->ranges[i + 1],
+				(mem->nr_ranges - (i + 1)) * sizeof(mem->ranges[i]));
+			i--;
 			mem->nr_ranges--;
-			return 0;
-		}
-
-		if (p_start > start && p_end < end) {
+		} else if (p_start > start && p_end < end) {
 			/* Split original range */
+			if (mem->nr_ranges >= mem->max_nr_ranges)
+				return -ENOMEM;
+
+			memmove(&mem->ranges[i + 2], &mem->ranges[i + 1],
+				(mem->nr_ranges - (i + 1)) * sizeof(mem->ranges[i]));
+
 			mem->ranges[i].end = p_start - 1;
-			temp_range.start = p_end + 1;
-			temp_range.end = end;
+			mem->ranges[i + 1].start = p_end + 1;
+			mem->ranges[i + 1].end = end;
+
+			i++;
+			mem->nr_ranges++;
 		} else if (p_start != start)
 			mem->ranges[i].end = p_start - 1;
 		else
 			mem->ranges[i].start = p_end + 1;
-		break;
-	}
-
-	/* If a split happened, add the split to array */
-	if (!temp_range.end)
-		return 0;
-
-	/* Split happened */
-	if (i == mem->max_nr_ranges - 1)
-		return -ENOMEM;
-
-	/* Location where new range should go */
-	j = i + 1;
-	if (j < mem->nr_ranges) {
-		/* Move over all ranges one slot towards the end */
-		for (i = mem->nr_ranges - 1; i >= j; i--)
-			mem->ranges[i + 1] = mem->ranges[i];
 	}
 
-	mem->ranges[j].start = temp_range.start;
-	mem->ranges[j].end = temp_range.end;
-	mem->nr_ranges++;
 	return 0;
 }
 
-- 
2.43.0

On 01/02/24 at 10:49pm, Yuntao Wang wrote:
> The purpose of crash_exclude_mem_range() is to remove all memory ranges
> that overlap with [mstart-mend]. However, the current logic only removes
> the first overlapping memory range.
> 
> Commit a2e9a95d2190 ("kexec: Improve & fix crash_exclude_mem_range() to
> handle overlapping ranges") attempted to address this issue, but it did not
> fix all error cases.
> 
> Let's fix and simplify the logic of crash_exclude_mem_range().

Thanks, this makes the code logic much clearer and easier to follow.

Acked-by: Baoquan He <bhe@redhat.com>

> 
> Signed-off-by: Yuntao Wang <ytcoode@gmail.com>
> ---
>  kernel/crash_core.c | 80 ++++++++++++++++-----------------------------
>  1 file changed, 29 insertions(+), 51 deletions(-)
> 
> diff --git a/kernel/crash_core.c b/kernel/crash_core.c
> index efe87d501c8c..c51d0a54296b 100644
> --- a/kernel/crash_core.c
> +++ b/kernel/crash_core.c
> @@ -565,9 +565,8 @@ int crash_prepare_elf64_headers(struct crash_mem *mem, int need_kernel_map,
>  int crash_exclude_mem_range(struct crash_mem *mem,
>  			    unsigned long long mstart, unsigned long long mend)
>  {
> -	int i, j;
> +	int i;
>  	unsigned long long start, end, p_start, p_end;
> -	struct range temp_range = {0, 0};
>  
>  	for (i = 0; i < mem->nr_ranges; i++) {
>  		start = mem->ranges[i].start;
> @@ -575,72 +574,51 @@ int crash_exclude_mem_range(struct crash_mem *mem,
>  		p_start = mstart;
>  		p_end = mend;
>  
> -		if (mstart > end || mend < start)
> +		if (p_start > end)
>  			continue;
>  
> +		/*
> +		 * Because the memory ranges in mem->ranges are stored in
> +		 * ascending order, when we detect `p_end < start`, we can
> +		 * immediately exit the for loop, as the subsequent memory
> +		 * ranges will definitely be outside the range we are looking
> +		 * for.
> +		 */
> +		if (p_end < start)
> +			break;
> +
>  		/* Truncate any area outside of range */
> -		if (mstart < start)
> +		if (p_start < start)
>  			p_start = start;
> -		if (mend > end)
> +		if (p_end > end)
>  			p_end = end;
>  
>  		/* Found completely overlapping range */
>  		if (p_start == start && p_end == end) {
> -			mem->ranges[i].start = 0;
> -			mem->ranges[i].end = 0;
> -			if (i < mem->nr_ranges - 1) {
> -				/* Shift rest of the ranges to left */
> -				for (j = i; j < mem->nr_ranges - 1; j++) {
> -					mem->ranges[j].start =
> -						mem->ranges[j+1].start;
> -					mem->ranges[j].end =
> -							mem->ranges[j+1].end;
> -				}
> -
> -				/*
> -				 * Continue to check if there are another overlapping ranges
> -				 * from the current position because of shifting the above
> -				 * mem ranges.
> -				 */
> -				i--;
> -				mem->nr_ranges--;
> -				continue;
> -			}
> +			memmove(&mem->ranges[i], &mem->ranges[i + 1],
> +				(mem->nr_ranges - (i + 1)) * sizeof(mem->ranges[i]));
> +			i--;
>  			mem->nr_ranges--;
> -			return 0;
> -		}
> -
> -		if (p_start > start && p_end < end) {
> +		} else if (p_start > start && p_end < end) {
>  			/* Split original range */
> +			if (mem->nr_ranges >= mem->max_nr_ranges)
> +				return -ENOMEM;
> +
> +			memmove(&mem->ranges[i + 2], &mem->ranges[i + 1],
> +				(mem->nr_ranges - (i + 1)) * sizeof(mem->ranges[i]));
> +
>  			mem->ranges[i].end = p_start - 1;
> -			temp_range.start = p_end + 1;
> -			temp_range.end = end;
> +			mem->ranges[i + 1].start = p_end + 1;
> +			mem->ranges[i + 1].end = end;
> +
> +			i++;
> +			mem->nr_ranges++;
>  		} else if (p_start != start)
>  			mem->ranges[i].end = p_start - 1;
>  		else
>  			mem->ranges[i].start = p_end + 1;
> -		break;
> -	}
> -
> -	/* If a split happened, add the split to array */
> -	if (!temp_range.end)
> -		return 0;
> -
> -	/* Split happened */
> -	if (i == mem->max_nr_ranges - 1)
> -		return -ENOMEM;
> -
> -	/* Location where new range should go */
> -	j = i + 1;
> -	if (j < mem->nr_ranges) {
> -		/* Move over all ranges one slot towards the end */
> -		for (i = mem->nr_ranges - 1; i >= j; i--)
> -			mem->ranges[i + 1] = mem->ranges[i];
>  	}
>  
> -	mem->ranges[j].start = temp_range.start;
> -	mem->ranges[j].end = temp_range.end;
> -	mem->nr_ranges++;
>  	return 0;
>  }
>  
> -- 
> 2.43.0
>