[PATCH v2] mm/memblock: fix overlapping allocation when doubling reserved array

[PATCH v2] mm/memblock: fix overlapping allocation when doubling reserved array

[Greg Pearson]

The __alloc_memory_core_early() routine will ask memblock for a range
of memory then try to reserve it. If the reserved region array lacks
space for the new range, memblock_double_array() is called to allocate
more space for the array. If memblock is used to allocate memory for
the new array it can end up using a range that overlaps with the range
originally allocated in __alloc_memory_core_early(), leading to possible
data corruption.

With this patch memblock_double_array() now calls memblock_find_in_range()
with a narrowed candidate range so any memory allocated will not overlap
with the original range that was being reserved. The range is narrowed by
passing in both the starting and ending address of the previously allocated
range. Then the range above the ending address is searched and if a candidate
is not found, the range below the starting address is searched.

Changes from v1: (based on comments from Yinghai Lu)
- use obase instead of base in memblock_add_region() for exclude start address
- pass in both the starting and ending address of the exclude range to
  memblock_double_array()
- have memblock_double_array() search above the exclude ending address
  and below the exclude starting address for a free range

Signed-off-by: Greg Pearson <greg.pearson@hp.com>
---
 mm/memblock.c |   15 +++++++++++----
 1 files changed, 11 insertions(+), 4 deletions(-)

diff --git a/mm/memblock.c b/mm/memblock.c
index 952123e..fee3ad9 100644
--- a/mm/memblock.c
+++ b/mm/memblock.c
@@ -184,7 +184,8 @@ static void __init_memblock memblock_remove_region(struct memblock_type *type, u
 	}
 }
 
-static int __init_memblock memblock_double_array(struct memblock_type *type)
+static int __init_memblock memblock_double_array(struct memblock_type *type,
+			phys_addr_t exclude_start, phys_addr_t exclude_end)
 {
 	struct memblock_region *new_array, *old_array;
 	phys_addr_t old_size, new_size, addr;
@@ -222,7 +223,12 @@ static int __init_memblock memblock_double_array(struct memblock_type *type)
 		new_array = kmalloc(new_size, GFP_KERNEL);
 		addr = new_array ? __pa(new_array) : 0;
 	} else {
-		addr = memblock_find_in_range(0, MEMBLOCK_ALLOC_ACCESSIBLE, new_size, sizeof(phys_addr_t));
+		addr = memblock_find_in_range(exclude_end,
+			MEMBLOCK_ALLOC_ACCESSIBLE,
+			new_size, sizeof(phys_addr_t));
+		if (!addr)
+			addr = memblock_find_in_range(0, exclude_start,
+				new_size, sizeof(phys_addr_t));
 		new_array = addr ? __va(addr) : 0;
 	}
 	if (!addr) {
@@ -399,7 +405,8 @@ repeat:
 	 */
 	if (!insert) {
 		while (type->cnt + nr_new > type->max)
-			if (memblock_double_array(type) < 0)
+			/* Avoid possible overlap if range is being reserved */
+			if (memblock_double_array(type, obase, obase+size) < 0)
 				return -ENOMEM;
 		insert = true;
 		goto repeat;
@@ -450,7 +457,7 @@ static int __init_memblock memblock_isolate_range(struct memblock_type *type,
 
 	/* we'll create at most two more regions */
 	while (type->cnt + 2 > type->max)
-		if (memblock_double_array(type) < 0)
+		if (memblock_double_array(type, 0, MEMBLOCK_ALLOC_ACCESSIBLE) < 0)
 			return -ENOMEM;
 
 	for (i = 0; i < type->cnt; i++) {
-- 
1.7.5.4

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH v2] mm/memblock: fix overlapping allocation when doubling reserved array

[Yinghai Lu]

[-- Attachment #1: Type: text/plain, Size: 1515 bytes --]

On Fri, Jun 15, 2012 at 5:28 PM, Greg Pearson <greg.pearson@hp.com> wrote:
> The __alloc_memory_core_early() routine will ask memblock for a range
> of memory then try to reserve it. If the reserved region array lacks
> space for the new range, memblock_double_array() is called to allocate
> more space for the array. If memblock is used to allocate memory for
> the new array it can end up using a range that overlaps with the range
> originally allocated in __alloc_memory_core_early(), leading to possible
> data corruption.
>
> With this patch memblock_double_array() now calls memblock_find_in_range()
> with a narrowed candidate range so any memory allocated will not overlap
> with the original range that was being reserved. The range is narrowed by
> passing in both the starting and ending address of the previously allocated
> range. Then the range above the ending address is searched and if a candidate
> is not found, the range below the starting address is searched.
>
> Changes from v1: (based on comments from Yinghai Lu)
> - use obase instead of base in memblock_add_region() for exclude start address
> - pass in both the starting and ending address of the exclude range to
>  memblock_double_array()
> - have memblock_double_array() search above the exclude ending address
>  and below the exclude starting address for a free range
>
> Signed-off-by: Greg Pearson <greg.pearson@hp.com>

found more problem, please check -v3

also add cc to Ben.

Thanks

Yinghai

[-- Attachment #2: memblock_double_array_fix.patch --]
[-- Type: application/octet-stream, Size: 3788 bytes --]

From:	Greg Pearson <greg.pearson@hp.com>
Subject: [PATCH] memblock: fix overlapping allocation when doubling reserved array

The __alloc_memory_core_early() routine will ask memblock for a range
of memory then try to reserve it. If the reserved region array lacks
space for the new range, memblock_double_array() is called to allocate
more space for the array. If memblock is used to allocate memory for
the new array it can end up using a range that overlaps with the range
originally allocated in __alloc_memory_core_early(), leading to possible
data corruption.

With this patch memblock_double_array() now calls memblock_find_in_range()
with a narrowed candidate range so any memory allocated will not overlap
with the original range that was being reserved. The range is narrowed by
passing in the starting address of the previously allocated range as the
end of the candidate range. Since memblock_find_in_range_node() looks for
a free range by walking the free memory list in reverse order (highest
memory address to lowest address) this change should not unnecessarily
exclude chunks of memory that could otherwise be used to satisfy the
request.

-v3: a. need to use obase instead for exclude_start, because base is changed.
     b. change to pass exclude_start/size.
     c. searching will be try high then low.
     d.	could make sure the range is accessible, so need to check with current_limit
     e. only need to exclude when double reserved.regions.
     f. for less confusing, even memblock_isolate_range pass exclude start/size too.
     g. remove not needed comment between while and one line loop body.

Signed-off-by: Greg Pearson <greg.pearson@hp.com>
Cc: Tejun Heo <tj@kernel.org>
Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Yinghai Lu <yinghai@kernel.org>

---
 mm/memblock.c |   21 +++++++++++++++++----
 1 file changed, 17 insertions(+), 4 deletions(-)

Index: linux-2.6/mm/memblock.c
===================================================================
--- linux-2.6.orig/mm/memblock.c
+++ linux-2.6/mm/memblock.c
@@ -184,7 +184,9 @@ static void __init_memblock memblock_rem
 	}
 }
 
-static int __init_memblock memblock_double_array(struct memblock_type *type)
+static int __init_memblock memblock_double_array(struct memblock_type *type,
+						 phys_addr_t exclude_start,
+						 phys_addr_t exclude_size)
 {
 	struct memblock_region *new_array, *old_array;
 	phys_addr_t old_size, new_size, addr;
@@ -222,7 +224,18 @@ static int __init_memblock memblock_doub
 		new_array = kmalloc(new_size, GFP_KERNEL);
 		addr = new_array ? __pa(new_array) : 0;
 	} else {
-		addr = memblock_find_in_range(0, MEMBLOCK_ALLOC_ACCESSIBLE, new_size, sizeof(phys_addr_t));
+		/* only exclude range when trying to double reserved.regions */
+		if (type != &memblock.reserved)
+			exclude_start = exclude_size = 0;
+
+		addr = memblock_find_in_range(exclude_start + exclude_size,
+						memblock.current_limit,
+						new_size, sizeof(phys_addr_t));
+		if (!addr && exclude_size)
+			addr = memblock_find_in_range(0,
+				    min(exclude_start, memblock.current_limit),
+				    new_size, sizeof(phys_addr_t));
+
 		new_array = addr ? __va(addr) : 0;
 	}
 	if (!addr) {
@@ -399,7 +412,7 @@ repeat:
 	 */
 	if (!insert) {
 		while (type->cnt + nr_new > type->max)
-			if (memblock_double_array(type) < 0)
+			if (memblock_double_array(type, obase, size) < 0)
 				return -ENOMEM;
 		insert = true;
 		goto repeat;
@@ -450,7 +463,7 @@ static int __init_memblock memblock_isol
 
 	/* we'll create at most two more regions */
 	while (type->cnt + 2 > type->max)
-		if (memblock_double_array(type) < 0)
+		if (memblock_double_array(type, base, size) < 0)
 			return -ENOMEM;
 
 	for (i = 0; i < type->cnt; i++) {