mm/memblock: reduce the two round insertion of memblock_add_range()
PATCH 1/6 mm/memblock: reduce the two round insertion of memblock_add_range()
Current memblock_add_range() does the insertion with two round iteration.
First round does the calculation of new region required, and second round does the actual insertion. Between them, if current max can't meet new region requirement, it is expanded.
The worst case is:
1. cnt == max
2. new range overlaps all existing region
This means the final cnt should be (2 * max + 1). Since we always double the array size, this means we only need to double the array twice at the worst case, which is fairly rare. For other cases, only once array double is enough.
Let's double the array immediately when there is no room for new region. This simplify the code a little.
--- mm/memblock.c | 74 +++++++++++++++------------------------------------ 1 file changed, 22 insertions(+), 52 deletions(-)
mm/memblock.c +22 -52
@@ -585,10 +585,9 @@ static int __init_memblock memblock_add_range(struct memblock_type *type, phys_addr_t base, phys_addr_t size, int nid, enum memblock_flags flags) { - bool insert = false; phys_addr_t obase = base;phys_addr_t end = base +memblock_cap_size (base, &size); -int idx, nr_new, start_rgn =-1 , end_rgn; +int idx, start_rgn =-1 , end_rgn;struct memblock_region *rgn;if (!size)
@@ -606,25 +605,6 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,return 0 ; } -/* -* The worst case is when new range overlaps all existing regions, -* then we'll need type->cnt + 1 empty regions in @type. So if -* type->cnt * 2 + 1 is less than or equal to type->max, we know -* that there is enough empty regions in @type, and we can insert -* regions directly. -*/ -if (type->cnt *2 +1 <= type->max) - insert = true; - -repeat: -/* -* The following is executed twice. Once with %false @insert and -* then with %true. The first counts the number of regions needed -* to accommodate the new area. The second actually inserts them. -*/ - base = obase; - nr_new =0 ; -for_each_memblock_type (idx, type, rgn) {phys_addr_t rbase = rgn->base;phys_addr_t rend = rbase + rgn->size;
@@ -642,15 +622,17 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,WARN_ON (nid !=memblock_get_region_node (rgn));#endif WARN_ON (flags != rgn->flags); - nr_new++; -if (insert) { -if (start_rgn ==-1 ) - start_rgn = idx; - end_rgn = idx +1 ; -memblock_insert_region (type, idx++, base, - rbase - base, nid, - flags); +if (type->cnt >= type->max) { +if (memblock_double_array (type, obase, size) <0 ) +return -ENOMEM ; } + +if (start_rgn ==-1 ) + start_rgn = idx; + end_rgn = idx +1 ; +memblock_insert_region (type, idx++, base, + rbase - base, nid, + flags); }/* area below @rend is dealt with, forget about it */ base =min (rend, end);
@@ -658,33 +640,21 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,/* insert the remaining portion */ if (base < end) { - nr_new++; -if (insert) { -if (start_rgn ==-1 ) - start_rgn = idx; - end_rgn = idx +1 ; -memblock_insert_region (type, idx, base, end - base, - nid, flags); +if (type->cnt >= type->max) { +if (memblock_double_array (type, obase, size) <0 ) +return -ENOMEM ; } - } -if (!nr_new) -return 0 ; +if (start_rgn ==-1 ) + start_rgn = idx; + end_rgn = idx +1 ; +memblock_insert_region (type, idx, base, end - base, + nid, flags); + } -/* -* If this was the first round, resize array and repeat for actual -* insertions; otherwise, merge and return. -*/ -if (!insert) { -while (type->cnt + nr_new > type->max) -if (memblock_double_array (type, obase, size) <0 ) -return -ENOMEM ; - insert = true; - goto repeat; - }else { +if (start_rgn !=-1 )memblock_merge_regions (type, start_rgn, end_rgn); -return 0 ; - } +return 0 ; }/**
Signature · 1 line
2.34.1
PATCH 2/6 memblock tests: add the 129th memory block at all possible position
After previous change, we may double the array based on the position of the new range.
Let's make sure the 129th memory block would double the size correctly at all possible position.
--- tools/testing/memblock/tests/basic_api.c | 132 +++++++++++++---------- 1 file changed, 73 insertions(+), 59 deletions(-)
tools/testing/memblock/tests/basic_api.c +73 -59
@@ -431,84 +431,98 @@ static int memblock_add_near_max_check(void)*/ static int memblock_add_many_check (void ) { -int i; +int i, skip;void *orig_region;struct region r = { .base =SZ_16K , .size =SZ_16K , };phys_addr_t new_memory_regions_size; -phys_addr_t base, size =SZ_64 ; +phys_addr_t base, base_start, size =SZ_64 ;phys_addr_t gap_size =SZ_64 ;PREFIX_PUSH (); -reset_memblock_regions (); -memblock_allow_resize (); - -dummy_physical_memory_init (); -/* -* We allocated enough memory by using dummy_physical_memory_init(), and -* split it into small block. First we split a large enough memory block -* as the memory region which will be choosed by memblock_double_array(). -*/ - base =PAGE_ALIGN (dummy_physical_memory_base ()); - new_memory_regions_size =PAGE_ALIGN (INIT_MEMBLOCK_REGIONS *2 * -sizeof (struct memblock_region )); -memblock_add (base, new_memory_regions_size); - -/* This is the base of small memory block. */ - base += new_memory_regions_size + gap_size; - - orig_region = memblock.memory.regions; +/* Add the 129th memory block for all possible positions*/ +for (skip =0 ; skip <INIT_MEMBLOCK_REGIONS ; skip++) { +reset_memblock_regions (); +memblock_allow_resize (); -for (i =0 ; i <INIT_MEMBLOCK_REGIONS ; i++) { +dummy_physical_memory_init ();/* -* Add these small block to fulfill the memblock. We keep a -* gap between the nearby memory to avoid being merged. +* We allocated enough memory by using dummy_physical_memory_init(), and +* split it into small block. First we split a large enough memory block +* as the memory region which will be choosed by memblock_double_array(). */ -memblock_add (base, size); - base += size + gap_size; - -ASSERT_EQ (memblock.memory.cnt, i +2 ); + base =PAGE_ALIGN (dummy_physical_memory_base ()); + new_memory_regions_size =PAGE_ALIGN (INIT_MEMBLOCK_REGIONS *2 * +sizeof (struct memblock_region )); +memblock_add (base, new_memory_regions_size); + +/* This is the base of small memory block. */ + base_start = base += new_memory_regions_size + gap_size; + orig_region = memblock.memory.regions; + +for (i =0 ; i <INIT_MEMBLOCK_REGIONS ; i++, base += size + gap_size) { +if (i == skip) +continue ; +/* +* Add these small block to fulfill the memblock. We keep a +* gap between the nearby memory to avoid being merged. +*/ +memblock_add (base, size); + +if (i < skip) { +ASSERT_EQ (memblock.memory.cnt, i +2 ); +ASSERT_EQ (memblock.memory.total_size, + new_memory_regions_size + (i +1 ) * size); + }else { +ASSERT_EQ (memblock.memory.cnt, i +1 ); +ASSERT_EQ (memblock.memory.total_size, + new_memory_regions_size + i * size); + } + } + +/* Add the skipped one to trigger memblock_double_array() */ +memblock_add (base_start + skip * (size + gap_size), size); +ASSERT_EQ (memblock.memory.cnt, i +1 );ASSERT_EQ (memblock.memory.total_size, new_memory_regions_size + - (i +1 ) * size); - } + i * size); +/* +* At there, memblock_double_array() has been succeed, check if it +* update the memory.max. +*/ +ASSERT_EQ (memblock.memory.max,INIT_MEMBLOCK_REGIONS *2 ); -/* -* At there, memblock_double_array() has been succeed, check if it -* update the memory.max. -*/ -ASSERT_EQ (memblock.memory.max,INIT_MEMBLOCK_REGIONS *2 ); +/* memblock_double_array() will reserve the memory it used. Check it. */ +ASSERT_EQ (memblock.reserved.cnt,1 ); +ASSERT_EQ (memblock.reserved.total_size, new_memory_regions_size); -/* memblock_double_array() will reserve the memory it used. Check it. */ -ASSERT_EQ (memblock.reserved.cnt,1 ); -ASSERT_EQ (memblock.reserved.total_size, new_memory_regions_size); - -/* -* Now memblock_double_array() works fine. Let's check after the -* double_array(), the memblock_add() still works as normal. -*/ -memblock_add (r.base, r.size); -ASSERT_EQ (memblock.memory.regions[0 ].base, r.base); -ASSERT_EQ (memblock.memory.regions[0 ].size, r.size); +/* +* Now memblock_double_array() works fine. Let's check after the +* double_array(), the memblock_add() still works as normal. +*/ +memblock_add (r.base, r.size); +ASSERT_EQ (memblock.memory.regions[0 ].base, r.base); +ASSERT_EQ (memblock.memory.regions[0 ].size, r.size); -ASSERT_EQ (memblock.memory.cnt,INIT_MEMBLOCK_REGIONS +2 ); -ASSERT_EQ (memblock.memory.total_size,INIT_MEMBLOCK_REGIONS * size + - new_memory_regions_size + - r.size); -ASSERT_EQ (memblock.memory.max,INIT_MEMBLOCK_REGIONS *2 ); +ASSERT_EQ (memblock.memory.cnt,INIT_MEMBLOCK_REGIONS +2 ); +ASSERT_EQ (memblock.memory.total_size,INIT_MEMBLOCK_REGIONS * size + + new_memory_regions_size + + r.size); +ASSERT_EQ (memblock.memory.max,INIT_MEMBLOCK_REGIONS *2 ); -dummy_physical_memory_cleanup (); +dummy_physical_memory_cleanup (); -/* -* The current memory.regions is occupying a range of memory that -* allocated from dummy_physical_memory_init(). After free the memory, -* we must not use it. So restore the origin memory region to make sure -* the tests can run as normal and not affected by the double array. -*/ - memblock.memory.regions = orig_region; - memblock.memory.cnt =INIT_MEMBLOCK_REGIONS ; +/* +* The current memory.regions is occupying a range of memory that +* allocated from dummy_physical_memory_init(). After free the memory, +* we must not use it. So restore the origin memory region to make sure +* the tests can run as normal and not affected by the double array. +*/ + memblock.memory.regions = orig_region; + memblock.memory.cnt =INIT_MEMBLOCK_REGIONS ; + }test_pass_pop ();
Signature · 1 line
2.34.1
Mike Rapoport
maintainerRe: [PATCH 2/6] memblock tests: add the 129th memory block at all possible position
Quoted 5 lines · Wei Yang
After previous change, we may double the array based on the position of the new range.
Let's make sure the 129th memory block would double the size correctly at all possible position.
Rather than rewrite an existing test, just add a new one. Besides, it would be more interesting to test additions to memblock.reserved and a mix of memblock_add() and memblock_reserve() that will require resizing the memblock arrays.
Quoted 170 lines
Signed-off-by Wei Yang <[email protected]>--- tools/testing/memblock/tests/basic_api.c | 132 +++++++++++++---------- 1 file changed, 73 insertions(+), 59 deletions(-)tools/testing/memblock/tests/basic_api.c +73
-59@@ -431,84 +431,98 @@ static int memblock_add_near_max_check(void)*/ static int memblock_add_many_check (void ) { -int i; +int i, skip;void *orig_region;struct region r = { .base =SZ_16K , .size =SZ_16K , };phys_addr_t new_memory_regions_size; -phys_addr_t base, size =SZ_64 ; +phys_addr_t base, base_start, size =SZ_64 ;phys_addr_t gap_size =SZ_64 ;PREFIX_PUSH (); -reset_memblock_regions (); -memblock_allow_resize (); - -dummy_physical_memory_init (); -/* -* We allocated enough memory by using dummy_physical_memory_init(), and -* split it into small block. First we split a large enough memory block -* as the memory region which will be choosed by memblock_double_array(). -*/ - base =PAGE_ALIGN (dummy_physical_memory_base ()); - new_memory_regions_size =PAGE_ALIGN (INIT_MEMBLOCK_REGIONS *2 * -sizeof (struct memblock_region )); -memblock_add (base, new_memory_regions_size); - -/* This is the base of small memory block. */ - base += new_memory_regions_size + gap_size; - - orig_region = memblock.memory.regions; +/* Add the 129th memory block for all possible positions*/ +for (skip =0 ; skip <INIT_MEMBLOCK_REGIONS ; skip++) { +reset_memblock_regions (); +memblock_allow_resize (); -for (i =0 ; i <INIT_MEMBLOCK_REGIONS ; i++) { +dummy_physical_memory_init ();/* -* Add these small block to fulfill the memblock. We keep a -* gap between the nearby memory to avoid being merged. +* We allocated enough memory by using dummy_physical_memory_init(), and +* split it into small block. First we split a large enough memory block +* as the memory region which will be choosed by memblock_double_array(). */ -memblock_add (base, size); - base += size + gap_size; - -ASSERT_EQ (memblock.memory.cnt, i +2 ); + base =PAGE_ALIGN (dummy_physical_memory_base ()); + new_memory_regions_size =PAGE_ALIGN (INIT_MEMBLOCK_REGIONS *2 * +sizeof (struct memblock_region )); +memblock_add (base, new_memory_regions_size); + +/* This is the base of small memory block. */ + base_start = base += new_memory_regions_size + gap_size; + orig_region = memblock.memory.regions; + +for (i =0 ; i <INIT_MEMBLOCK_REGIONS ; i++, base += size + gap_size) { +if (i == skip) +continue ; +/* +* Add these small block to fulfill the memblock. We keep a +* gap between the nearby memory to avoid being merged. +*/ +memblock_add (base, size); + +if (i < skip) { +ASSERT_EQ (memblock.memory.cnt, i +2 ); +ASSERT_EQ (memblock.memory.total_size, + new_memory_regions_size + (i +1 ) * size); + }else { +ASSERT_EQ (memblock.memory.cnt, i +1 ); +ASSERT_EQ (memblock.memory.total_size, + new_memory_regions_size + i * size); + } + } + +/* Add the skipped one to trigger memblock_double_array() */ +memblock_add (base_start + skip * (size + gap_size), size); +ASSERT_EQ (memblock.memory.cnt, i +1 );ASSERT_EQ (memblock.memory.total_size, new_memory_regions_size + - (i +1 ) * size); - } + i * size); +/* +* At there, memblock_double_array() has been succeed, check if it +* update the memory.max. +*/ +ASSERT_EQ (memblock.memory.max,INIT_MEMBLOCK_REGIONS *2 ); -/* -* At there, memblock_double_array() has been succeed, check if it -* update the memory.max. -*/ -ASSERT_EQ (memblock.memory.max,INIT_MEMBLOCK_REGIONS *2 ); +/* memblock_double_array() will reserve the memory it used. Check it. */ +ASSERT_EQ (memblock.reserved.cnt,1 ); +ASSERT_EQ (memblock.reserved.total_size, new_memory_regions_size); -/* memblock_double_array() will reserve the memory it used. Check it. */ -ASSERT_EQ (memblock.reserved.cnt,1 ); -ASSERT_EQ (memblock.reserved.total_size, new_memory_regions_size); - -/* -* Now memblock_double_array() works fine. Let's check after the -* double_array(), the memblock_add() still works as normal. -*/ -memblock_add (r.base, r.size); -ASSERT_EQ (memblock.memory.regions[0 ].base, r.base); -ASSERT_EQ (memblock.memory.regions[0 ].size, r.size); +/* +* Now memblock_double_array() works fine. Let's check after the +* double_array(), the memblock_add() still works as normal. +*/ +memblock_add (r.base, r.size); +ASSERT_EQ (memblock.memory.regions[0 ].base, r.base); +ASSERT_EQ (memblock.memory.regions[0 ].size, r.size); -ASSERT_EQ (memblock.memory.cnt,INIT_MEMBLOCK_REGIONS +2 ); -ASSERT_EQ (memblock.memory.total_size,INIT_MEMBLOCK_REGIONS * size + - new_memory_regions_size + - r.size); -ASSERT_EQ (memblock.memory.max,INIT_MEMBLOCK_REGIONS *2 ); +ASSERT_EQ (memblock.memory.cnt,INIT_MEMBLOCK_REGIONS +2 ); +ASSERT_EQ (memblock.memory.total_size,INIT_MEMBLOCK_REGIONS * size + + new_memory_regions_size + + r.size); +ASSERT_EQ (memblock.memory.max,INIT_MEMBLOCK_REGIONS *2 ); -dummy_physical_memory_cleanup (); +dummy_physical_memory_cleanup (); -/* -* The current memory.regions is occupying a range of memory that -* allocated from dummy_physical_memory_init(). After free the memory, -* we must not use it. So restore the origin memory region to make sure -* the tests can run as normal and not affected by the double array. -*/ - memblock.memory.regions = orig_region; - memblock.memory.cnt =INIT_MEMBLOCK_REGIONS ; +/* +* The current memory.regions is occupying a range of memory that +* allocated from dummy_physical_memory_init(). After free the memory, +* we must not use it. So restore the origin memory region to make sure +* the tests can run as normal and not affected by the double array. +*/ + memblock.memory.regions = orig_region; + memblock.memory.cnt =INIT_MEMBLOCK_REGIONS ; + }test_pass_pop ();Signature · 1 line
2.34.1
Signature · 2 lines
Sincerely yours, Mike.
Re: [PATCH 2/6] memblock tests: add the 129th memory block at all possible position
Quoted 8 lines · Mike Rapoport
Quoted 5 lines · Wei Yang
After previous change, we may double the array based on the position of the new range.
Let's make sure the 129th memory block would double the size correctly at all possible position.
Rather than rewrite an existing test, just add a new one.
Ok, will add a new one for this.
Quoted 3 lines
Besides, it would be more interesting to test additions to memblock.reserved and a mix of
memblock_add()andmemblock_reserve()that will require resizing the memblock arrays.
I don't get this very clearly. Would you mind give more hint?
Quoted 8 lines
Quoted 4 lines
Signature · 2 lines
-- 2.34.1Signature · 2 lines
Sincerely yours, Mike.
Signature · 2 lines
Wei Yang Help you, Help me
Mike Rapoport
maintainerRe: [PATCH 2/6] memblock tests: add the 129th memory block at all possible position
Quoted 10 lines · Wei Yang
Quoted 8 lines · Mike Rapoport
Quoted 5 lines · Wei Yang
After previous change, we may double the array based on the position of the new range.
Let's make sure the 129th memory block would double the size correctly at all possible position.
Rather than rewrite an existing test, just add a new one.
Quoted 7 lines
Ok, will add a new one for this.
Quoted 3 lines
Besides, it would be more interesting to test additions to memblock.reserved and a mix of
memblock_add()andmemblock_reserve()that will require resizing the memblock arrays.I don't get this very clearly. Would you mind give more hint?
There is memblock_reserve_many_check() that verifies that memblock.reserved is properly resized. I think it's better to add test that adds 129th block at multiple locations to memblock.reserved.
Quoted 3 lines
Signature · 2 lines
Wei Yang Help you, Help me
Signature · 2 lines
Sincerely yours, Mike.
Re: [PATCH 2/6] memblock tests: add the 129th memory block at all possible position
Quoted 17 lines · Mike Rapoport
Quoted 16 lines · Wei Yang
Quoted 8 lines · Mike Rapoport
Quoted 5 lines · Wei Yang
After previous change, we may double the array based on the position of the new range.
Let's make sure the 129th memory block would double the size correctly at all possible position.
Rather than rewrite an existing test, just add a new one.
Ok, will add a new one for this.
Quoted 3 lines
Besides, it would be more interesting to test additions to memblock.reserved and a mix of
memblock_add()andmemblock_reserve()that will require resizing the memblock arrays.
Quoted 6 lines
Quoted 1 line
I don't get this very clearly. Would you mind give more hint?
There is
memblock_reserve_many_check()that verifies that memblock.reserved is properly resized. I think it's better to add test that adds 129th block at multiple locations to memblock.reserved.
I write a draft as below, is this what you expect?
tools/testing/memblock/tests/basic_api.c +72 -62
@@ -912,84 +912,94 @@ static int memblock_reserve_near_max_check(void)* memblock.memory.max, find a new valid memory as * reserved.regions. */ +/* Keep the gap so these memory region will not be merged. */ +#define MEMORY_BASE (idx) (SZ_128K + (MEM_SIZE * 2) * (idx))static int memblock_reserve_many_check (void ) { -int i; +int i, skip;void *orig_region;struct region r = { .base =SZ_16K , .size =SZ_16K , }; -phys_addr_t memory_base =SZ_128K ;phys_addr_t new_reserved_regions_size;PREFIX_PUSH (); -reset_memblock_regions (); -memblock_allow_resize (); +/* Reserve the 129th memory block for all possible positions*/ +for (skip =0 ; skip <INIT_MEMBLOCK_REGIONS +1 ; skip++) + { +reset_memblock_regions (); +memblock_allow_resize (); -/* Add a valid memory region used by double_array(). */ -dummy_physical_memory_init (); -memblock_add (dummy_physical_memory_base (),MEM_SIZE ); +/* Add a valid memory region used by double_array(). */ +dummy_physical_memory_init (); +memblock_add (dummy_physical_memory_base (),MEM_SIZE ); -for (i =0 ; i <INIT_MEMBLOCK_REGIONS ; i++) { -/* Reserve some fakes memory region to fulfill the memblock. */ -memblock_reserve (memory_base,MEM_SIZE ); +for (i =0 ; i <INIT_MEMBLOCK_REGIONS +1 ; i++) { +if (i == skip) +continue ; -ASSERT_EQ (memblock.reserved.cnt, i +1 ); -ASSERT_EQ (memblock.reserved.total_size, (i +1 ) *MEM_SIZE ); +/* Reserve some fakes memory region to fulfill the memblock. */ +memblock_reserve (MEMORY_BASE (i),MEM_SIZE ); -/* Keep the gap so these memory region will not be merged. */ - memory_base +=MEM_SIZE *2 ; - } +if (i < skip) { +ASSERT_EQ (memblock.reserved.cnt, i +1 ); +ASSERT_EQ (memblock.reserved.total_size, (i +1 ) *MEM_SIZE ); + }else { +ASSERT_EQ (memblock.reserved.cnt, i); +ASSERT_EQ (memblock.reserved.total_size, i *MEM_SIZE ); + } + } - orig_region = memblock.reserved.regions; - -/* This reserve the 129 memory_region, and makes it double array. */ -memblock_reserve (memory_base,MEM_SIZE ); - -/* -* This is the memory region size used by the doubled reserved.regions, -* and it has been reserved due to it has been used. The size is used to -* calculate the total_size that the memblock.reserved have now. -*/ - new_reserved_regions_size =PAGE_ALIGN ((INIT_MEMBLOCK_REGIONS *2 ) * -sizeof (struct memblock_region )); -/* -* The double_array() will find a free memory region as the new -* reserved.regions, and the used memory region will be reserved, so -* there will be one more region exist in the reserved memblock. And the -* one more reserved region's size is new_reserved_regions_size. -*/ -ASSERT_EQ (memblock.reserved.cnt,INIT_MEMBLOCK_REGIONS +2 ); -ASSERT_EQ (memblock.reserved.total_size, (INIT_MEMBLOCK_REGIONS +1 ) *MEM_SIZE + - new_reserved_regions_size); -ASSERT_EQ (memblock.reserved.max,INIT_MEMBLOCK_REGIONS *2 ); - -/* -* Now memblock_double_array() works fine. Let's check after the -* double_array(), the memblock_reserve() still works as normal. -*/ -memblock_reserve (r.base, r.size); -ASSERT_EQ (memblock.reserved.regions[0 ].base, r.base); -ASSERT_EQ (memblock.reserved.regions[0 ].size, r.size); - -ASSERT_EQ (memblock.reserved.cnt,INIT_MEMBLOCK_REGIONS +3 ); -ASSERT_EQ (memblock.reserved.total_size, (INIT_MEMBLOCK_REGIONS +1 ) *MEM_SIZE + - new_reserved_regions_size + - r.size); -ASSERT_EQ (memblock.reserved.max,INIT_MEMBLOCK_REGIONS *2 ); - -dummy_physical_memory_cleanup (); - -/* -* The current reserved.regions is occupying a range of memory that -* allocated from dummy_physical_memory_init(). After free the memory, -* we must not use it. So restore the origin memory region to make sure -* the tests can run as normal and not affected by the double array. -*/ - memblock.reserved.regions = orig_region; - memblock.reserved.cnt =INIT_MEMBLOCK_RESERVED_REGIONS ; + orig_region = memblock.reserved.regions; + +/* This reserve the 129 memory_region, and makes it double array. */ +memblock_reserve (MEMORY_BASE (skip),MEM_SIZE ); + +/* +* This is the memory region size used by the doubled reserved.regions, +* and it has been reserved due to it has been used. The size is used to +* calculate the total_size that the memblock.reserved have now. +*/ + new_reserved_regions_size =PAGE_ALIGN ((INIT_MEMBLOCK_REGIONS *2 ) * +sizeof (struct memblock_region )); +/* +* The double_array() will find a free memory region as the new +* reserved.regions, and the used memory region will be reserved, so +* there will be one more region exist in the reserved memblock. And the +* one more reserved region's size is new_reserved_regions_size. +*/ +ASSERT_EQ (memblock.reserved.cnt,INIT_MEMBLOCK_REGIONS +2 ); +ASSERT_EQ (memblock.reserved.total_size, (INIT_MEMBLOCK_REGIONS +1 ) *MEM_SIZE + + new_reserved_regions_size); +ASSERT_EQ (memblock.reserved.max,INIT_MEMBLOCK_REGIONS *2 ); + +/* +* Now memblock_double_array() works fine. Let's check after the +* double_array(), the memblock_reserve() still works as normal. +*/ +memblock_reserve (r.base, r.size); +ASSERT_EQ (memblock.reserved.regions[0 ].base, r.base); +ASSERT_EQ (memblock.reserved.regions[0 ].size, r.size); + +ASSERT_EQ (memblock.reserved.cnt,INIT_MEMBLOCK_REGIONS +3 ); +ASSERT_EQ (memblock.reserved.total_size, (INIT_MEMBLOCK_REGIONS +1 ) *MEM_SIZE + + new_reserved_regions_size + + r.size); +ASSERT_EQ (memblock.reserved.max,INIT_MEMBLOCK_REGIONS *2 ); + +dummy_physical_memory_cleanup (); + +/* +* The current reserved.regions is occupying a range of memory that +* allocated from dummy_physical_memory_init(). After free the memory, +* we must not use it. So restore the origin memory region to make sure +* the tests can run as normal and not affected by the double array. +*/ + memblock.reserved.regions = orig_region; + memblock.reserved.cnt =INIT_MEMBLOCK_RESERVED_REGIONS ; + }test_pass_pop ();
Signature · 1 line
2.34.1
Quoted 7 lines
Quoted 3 lines
Signature · 2 lines
Wei Yang Help you, Help meSignature · 2 lines
Sincerely yours, Mike.
Signature · 2 lines
Wei Yang Help you, Help me
Re: [PATCH 2/6] memblock tests: add the 129th memory block at all possible position
In reply to Mike RapoportQuoted 17 lines · Mike Rapoport
Quoted 16 lines · Wei Yang
Quoted 8 lines · Mike Rapoport
Quoted 5 lines · Wei Yang
After previous change, we may double the array based on the position of the new range.
Let's make sure the 129th memory block would double the size correctly at all possible position.
Rather than rewrite an existing test, just add a new one.
Ok, will add a new one for this.
Quoted 3 lines
Besides, it would be more interesting to test additions to memblock.reserved and a mix of
memblock_add()andmemblock_reserve()that will require resizing the memblock arrays.
Quoted 6 lines
Quoted 1 line
I don't get this very clearly. Would you mind give more hint?
There is
memblock_reserve_many_check()that verifies that memblock.reserved is properly resized. I think it's better to add test that adds 129th block at multiple locations to memblock.reserved.
I come up with another version, which could address the bug fixed by commit 48c3b583bbdd ("mm/memblock: fix overlapping allocation when doubling reserved array").
Comment out the fix, the test failed since cnt mismatch after double array.
Not sure you prefer to have both or just leave this version by replacing current memblock_reserve_many_check().
tools/testing/memblock/tests/basic_api.c +114 -0
@@ -1006,6 +1006,119 @@ static int memblock_reserve_many_check(void)return 0 ; } +/* Keep the gap so these memory region will not be merged. */ +#define MEMORY_BASE_OFFSET (idx, offset) ((offset) + (MEM_SIZE * 2) * (idx)) +static int memblock_reserve_many_conflict_check (void ) +{ +int i, skip; +void *orig_region; +struct region r = { + .base =SZ_16K , + .size =SZ_16K , + }; +phys_addr_t new_reserved_regions_size; + +/* +* 0 1 129 +* +---+ +---+ +---+ +* |32K| |32K| .. |32K| +* +---+ +---+ +---+ +* +* Pre-allocate the range for 129 memory block + one range for double +* memblock.reserved.regions at idx 0. +* See commit 48c3b583bbdd ("mm/memblock: fix overlapping allocation +* when doubling reserved array") +*/ +phys_addr_t memory_base = (phys_addr_t )malloc (130 * (2 *SZ_32K )); +phys_addr_t offset =PAGE_ALIGN (memory_base); + +PREFIX_PUSH (); + +/* Reserve the 129th memory block for all possible positions*/ +for (skip =1 ; skip <=INIT_MEMBLOCK_REGIONS +1 ; skip++) + { +reset_memblock_regions (); +memblock_allow_resize (); + +reset_memblock_attributes (); +/* Add a valid memory region used by double_array(). */ +memblock_add (MEMORY_BASE_OFFSET (0 , offset),MEM_SIZE ); +/* +* Add a memory region which will be reserved as 129th memory +* region. This is not expected to be used by double_array(). +*/ +memblock_add (MEMORY_BASE_OFFSET (skip, offset),MEM_SIZE ); + +for (i =1 ; i <=INIT_MEMBLOCK_REGIONS +1 ; i++) { +if (i == skip) +continue ; + +/* Reserve some fakes memory region to fulfill the memblock. */ +memblock_reserve (MEMORY_BASE_OFFSET (i, offset),MEM_SIZE ); + +if (i < skip) { +ASSERT_EQ (memblock.reserved.cnt, i); +ASSERT_EQ (memblock.reserved.total_size, i *MEM_SIZE ); + }else { +ASSERT_EQ (memblock.reserved.cnt, i -1 ); +ASSERT_EQ (memblock.reserved.total_size, (i -1 ) *MEM_SIZE ); + } + } + + orig_region = memblock.reserved.regions; + +/* This reserve the 129 memory_region, and makes it double array. */ +memblock_reserve (MEMORY_BASE_OFFSET (skip, offset),MEM_SIZE ); + +/* +* This is the memory region size used by the doubled reserved.regions, +* and it has been reserved due to it has been used. The size is used to +* calculate the total_size that the memblock.reserved have now. +*/ + new_reserved_regions_size =PAGE_ALIGN ((INIT_MEMBLOCK_REGIONS *2 ) * +sizeof (struct memblock_region )); +/* +* The double_array() will find a free memory region as the new +* reserved.regions, and the used memory region will be reserved, so +* there will be one more region exist in the reserved memblock. And the +* one more reserved region's size is new_reserved_regions_size. +*/ +ASSERT_EQ (memblock.reserved.cnt,INIT_MEMBLOCK_REGIONS +2 ); +ASSERT_EQ (memblock.reserved.total_size, (INIT_MEMBLOCK_REGIONS +1 ) *MEM_SIZE + + new_reserved_regions_size); +ASSERT_EQ (memblock.reserved.max,INIT_MEMBLOCK_REGIONS *2 ); + +/* +* Now memblock_double_array() works fine. Let's check after the +* double_array(), the memblock_reserve() still works as normal. +*/ +memblock_reserve (r.base, r.size); +ASSERT_EQ (memblock.reserved.regions[0 ].base, r.base); +ASSERT_EQ (memblock.reserved.regions[0 ].size, r.size); + +ASSERT_EQ (memblock.reserved.cnt,INIT_MEMBLOCK_REGIONS +3 ); +ASSERT_EQ (memblock.reserved.total_size, (INIT_MEMBLOCK_REGIONS +1 ) *MEM_SIZE + + new_reserved_regions_size + + r.size); +ASSERT_EQ (memblock.reserved.max,INIT_MEMBLOCK_REGIONS *2 ); + +/* +* The current reserved.regions is occupying a range of memory that +* allocated from dummy_physical_memory_init(). After free the memory, +* we must not use it. So restore the origin memory region to make sure +* the tests can run as normal and not affected by the double array. +*/ + memblock.reserved.regions = orig_region; + memblock.reserved.cnt =INIT_MEMBLOCK_RESERVED_REGIONS ; + } + +free ((void *)memory_base); + +test_pass_pop (); + +return 0 ; +} +static int memblock_reserve_checks (void ) {prefix_reset ();
@@ -1021,6 +1134,7 @@ static int memblock_reserve_checks(void)memblock_reserve_between_check ();memblock_reserve_near_max_check ();memblock_reserve_many_check (); +memblock_reserve_many_conflict_check ();prefix_pop ();
Signature · 1 line
2.34.1
Quoted 7 lines
Quoted 3 lines
Signature · 2 lines
Wei Yang Help you, Help meSignature · 2 lines
Sincerely yours, Mike.
Signature · 2 lines
Wei Yang Help you, Help me
Mike Rapoport
maintainerRe: [PATCH 2/6] memblock tests: add the 129th memory block at all possible position
Quoted 25 lines · Wei Yang
Quoted 17 lines · Mike Rapoport
Quoted 16 lines · Wei Yang
Quoted 8 lines · Mike Rapoport
Quoted 5 lines · Wei Yang
After previous change, we may double the array based on the position of the new range.
Let's make sure the 129th memory block would double the size correctly at all possible position.
Rather than rewrite an existing test, just add a new one.
Ok, will add a new one for this.
Quoted 3 lines
Besides, it would be more interesting to test additions to memblock.reserved and a mix of
memblock_add()andmemblock_reserve()that will require resizing the memblock arrays.Quoted 6 lines
Quoted 1 line
I don't get this very clearly. Would you mind give more hint?
There is
memblock_reserve_many_check()that verifies that memblock.reserved is properly resized. I think it's better to add test that adds 129th block at multiple locations to memblock.reserved.
Quoted 8 lines
I come up with another version, which could address the bug fixed by commit
48c3b583bbdd("mm/memblock: fix overlapping allocation when doubling reserved array").Comment out the fix, the test failed since cnt mismatch after double array.
Not sure you prefer to have both or just leave this version by replacing current
memblock_reserve_many_check().
Let's have both of them.
Quoted 22 lines
tools/testing/memblock/tests/basic_api.c +14
-0@@ -1006,6 +1006,119 @@ static int memblock_reserve_many_check(void)return 0 ; } +/* Keep the gap so these memory region will not be merged. */ +#define MEMORY_BASE_OFFSET (idx, offset) ((offset) + (MEM_SIZE * 2) * (idx)) +static int memblock_reserve_many_conflict_check (void ) +{ +int i, skip; +void *orig_region; +struct region r = { + .base =SZ_16K , + .size =SZ_16K , + }; +phys_addr_t new_reserved_regions_size; + +/* +* 0 1 129
tools/testing/memblock/tests/basic_api.c static int memblock_reserve_many_check(void) · line 1032
Quoted 10 lines
tools/testing/memblock/tests/basic_api.c +10
-0+* +---+ +---+ +---+ +* |32K| |32K| .. |32K| +* +---+ +---+ +---+ +* +* Pre-allocate the range for 129 memory block + one range for double +* memblock.reserved.regions at idx 0. +* See commit 48c3b583bbdd ("mm/memblock: fix overlapping allocation +* when doubling reserved array") +*/ +phys_addr_t memory_base = (phys_addr_t )malloc (130 * (2 *SZ_32K ));
Just increase MEM_SIZE to, say, SZ_1M and use dummy_physical_memory_init() etc
Quoted 102 lines
tools/testing/memblock/tests/basic_api.c +90
-0+phys_addr_t offset =PAGE_ALIGN (memory_base); + +PREFIX_PUSH (); + +/* Reserve the 129th memory block for all possible positions*/ +for (skip =1 ; skip <=INIT_MEMBLOCK_REGIONS +1 ; skip++) + { +reset_memblock_regions (); +memblock_allow_resize (); + +reset_memblock_attributes (); +/* Add a valid memory region used by double_array(). */ +memblock_add (MEMORY_BASE_OFFSET (0 , offset),MEM_SIZE ); +/* +* Add a memory region which will be reserved as 129th memory +* region. This is not expected to be used by double_array(). +*/ +memblock_add (MEMORY_BASE_OFFSET (skip, offset),MEM_SIZE ); + +for (i =1 ; i <=INIT_MEMBLOCK_REGIONS +1 ; i++) { +if (i == skip) +continue ; + +/* Reserve some fakes memory region to fulfill the memblock. */ +memblock_reserve (MEMORY_BASE_OFFSET (i, offset),MEM_SIZE ); + +if (i < skip) { +ASSERT_EQ (memblock.reserved.cnt, i); +ASSERT_EQ (memblock.reserved.total_size, i *MEM_SIZE ); + }else { +ASSERT_EQ (memblock.reserved.cnt, i -1 ); +ASSERT_EQ (memblock.reserved.total_size, (i -1 ) *MEM_SIZE ); + } + } + + orig_region = memblock.reserved.regions; + +/* This reserve the 129 memory_region, and makes it double array. */ +memblock_reserve (MEMORY_BASE_OFFSET (skip, offset),MEM_SIZE ); + +/* +* This is the memory region size used by the doubled reserved.regions, +* and it has been reserved due to it has been used. The size is used to +* calculate the total_size that the memblock.reserved have now. +*/ + new_reserved_regions_size =PAGE_ALIGN ((INIT_MEMBLOCK_REGIONS *2 ) * +sizeof (struct memblock_region )); +/* +* The double_array() will find a free memory region as the new +* reserved.regions, and the used memory region will be reserved, so +* there will be one more region exist in the reserved memblock. And the +* one more reserved region's size is new_reserved_regions_size. +*/ +ASSERT_EQ (memblock.reserved.cnt,INIT_MEMBLOCK_REGIONS +2 ); +ASSERT_EQ (memblock.reserved.total_size, (INIT_MEMBLOCK_REGIONS +1 ) *MEM_SIZE + + new_reserved_regions_size); +ASSERT_EQ (memblock.reserved.max,INIT_MEMBLOCK_REGIONS *2 ); + +/* +* Now memblock_double_array() works fine. Let's check after the +* double_array(), the memblock_reserve() still works as normal. +*/ +memblock_reserve (r.base, r.size); +ASSERT_EQ (memblock.reserved.regions[0 ].base, r.base); +ASSERT_EQ (memblock.reserved.regions[0 ].size, r.size); + +ASSERT_EQ (memblock.reserved.cnt,INIT_MEMBLOCK_REGIONS +3 ); +ASSERT_EQ (memblock.reserved.total_size, (INIT_MEMBLOCK_REGIONS +1 ) *MEM_SIZE + + new_reserved_regions_size + + r.size); +ASSERT_EQ (memblock.reserved.max,INIT_MEMBLOCK_REGIONS *2 ); + +/* +* The current reserved.regions is occupying a range of memory that +* allocated from dummy_physical_memory_init(). After free the memory, +* we must not use it. So restore the origin memory region to make sure +* the tests can run as normal and not affected by the double array. +*/ + memblock.reserved.regions = orig_region; + memblock.reserved.cnt =INIT_MEMBLOCK_RESERVED_REGIONS ; + } + +free ((void *)memory_base); + +test_pass_pop (); + +return 0 ; +} +static int memblock_reserve_checks (void ) {prefix_reset ();@@ -1021,6 +1134,7 @@ static int memblock_reserve_checks(void)memblock_reserve_between_check ();memblock_reserve_near_max_check ();memblock_reserve_many_check (); +memblock_reserve_many_conflict_check ();prefix_pop ();Signature · 1 line
2.34.1
Signature · 2 lines
Sincerely yours, Mike.
PATCH 3/6 mm/memblock: fix comment for memblock_isolate_range()
In reply to Wei YangThe isolated range is [*@start_rgn, *@end_rgn - 1], while the comment says "the end region inside the range" is *@end_rgn.
Let's correct it.
--- mm/memblock.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
mm/memblock.c +2 -2
@@ -742,12 +742,12 @@ bool __init_memblock memblock_validate_numa_coverage(unsigned long threshold_byt* @base: base of range to isolate * @size: size of range to isolate * @start_rgn: out parameter for the start of isolated region -* @end_rgn: out parameter for the end of isolated region +* @end_rgn: out parameter for the (end + 1) of isolated region * * Walk @type and ensure that regions don't cross the boundaries defined by * [@base, @base + @size). Crossing regions are split at the boundaries, * which may create at most two more regions. The index of the first -* region inside the range is returned in *@start_rgn and end in *@end_rgn. +* region inside the range is returned in *@start_rgn and (end + 1) in *@end_rgn. * * Return: * 0 on success, -errno on failure.
Signature · 1 line
2.34.1
PATCH 4/6 mm/memblock: remove consecutive regions at once
In reply to Wei YangIn memblock_remove_range, we would remove consecutive regions after isolation.
Instead of removing each region from end to start one by one, we could remove those consecutive regions at once.
--- mm/memblock.c | 24 ++++++++++++++++-------- 1 file changed, 16 insertions(+), 8 deletions(-)
mm/memblock.c +16 -8
@@ -343,12 +343,15 @@ static phys_addr_t __init_memblock memblock_find_in_range(phys_addr_t start,return ret; } -static void __init_memblock memblock_remove_region(struct memblock_type *type, unsigned long r) +static void __init_memblock memblock_remove_regions(struct memblock_type *type, +unsigned long r, +unsigned int num) { - type->total_size -= type->regions[r].size; -memmove (&type->regions[r], &type->regions[r +1 ], - (type->cnt - (r +1 )) *sizeof (type->regions[r])); - type->cnt--; +for (int i =0 ; i < num; i++) + type->total_size -= type->regions[r + i].size; +memmove (&type->regions[r], &type->regions[r + num], + (type->cnt - (r + num)) *sizeof (type->regions[r])); + type->cnt -= num;/* Special case for empty arrays */ if (type->cnt ==0 ) {
@@ -360,6 +363,11 @@ static void __init_memblock memblock_remove_region(struct memblock_type *type, u } } +static void __init_memblock memblock_remove_region(struct memblock_type *type, unsigned long r) +{ +memblock_remove_regions (type, r,1 ); +} +#ifndef CONFIG_ARCH_KEEP_MEMBLOCK /** * memblock_discard - discard memory and reserved arrays if they were allocated
@@ -816,14 +824,14 @@ static int __init_memblock memblock_remove_range(struct memblock_type *type, phys_addr_t base, phys_addr_t size) { int start_rgn, end_rgn; -int i, ret; +int ret; ret =memblock_isolate_range (type, base, size, &start_rgn, &end_rgn);if (ret)return ret; -for (i = end_rgn -1 ; i >= start_rgn; i--) -memblock_remove_region (type, i); +if (end_rgn - start_rgn) +memblock_remove_regions (type, start_rgn, end_rgn - start_rgn);return 0 ; }
Signature · 1 line
2.34.1
PATCH 5/6 memblock tests: add memblock_overlaps_region_checks
In reply to Wei YangAdd a test case for memblock_overlaps_region().
--- tools/testing/memblock/tests/basic_api.c | 48 ++++++++++++++++++++++++ tools/testing/memblock/tests/common.h | 3 ++ 2 files changed, 51 insertions(+)
tools/testing/memblock/tests/basic_api.c +48 -0
@@ -2143,6 +2143,53 @@ static int memblock_trim_memory_checks(void)return 0 ; } +static int memblock_overlaps_region_check (void ) +{ +struct region r = { + .base =SZ_1G , + .size =SZ_4M + }; + +PREFIX_PUSH (); + +reset_memblock_regions (); +memblock_add (r.base, r.size); + +/* Far Away */ +ASSERT_FALSE (memblock_overlaps_region (&memblock.memory,SZ_1M ,SZ_1M )); +ASSERT_FALSE (memblock_overlaps_region (&memblock.memory,SZ_2G ,SZ_1M )); + +/* Neighbor */ +ASSERT_FALSE (memblock_overlaps_region (&memblock.memory,SZ_1G -SZ_1M ,SZ_1M )); +ASSERT_FALSE (memblock_overlaps_region (&memblock.memory,SZ_1G +SZ_4M ,SZ_1M )); + +/* Partial Overlap */ +ASSERT_TRUE (memblock_overlaps_region (&memblock.memory,SZ_1G -SZ_1M ,SZ_2M )); +ASSERT_TRUE (memblock_overlaps_region (&memblock.memory,SZ_1G +SZ_2M ,SZ_2M )); + +/* Totally Overlap */ +ASSERT_TRUE (memblock_overlaps_region (&memblock.memory,SZ_1G ,SZ_4M )); +ASSERT_TRUE (memblock_overlaps_region (&memblock.memory,SZ_1G -SZ_2M ,SZ_8M )); +ASSERT_TRUE (memblock_overlaps_region (&memblock.memory,SZ_1G +SZ_1M ,SZ_1M )); + +test_pass_pop (); + +return 0 ; +} + +static int memblock_overlaps_region_checks (void ) +{ +prefix_reset (); +prefix_push ("memblock_overlaps_region" ); +test_print ("Running memblock_overlaps_region tests...\n" ); + +memblock_overlaps_region_check (); + +prefix_pop (); + +return 0 ; +} +int memblock_basic_checks (void ) {memblock_initialization_check ();
@@ -2152,6 +2199,7 @@ int memblock_basic_checks(void)memblock_free_checks ();memblock_bottom_up_checks ();memblock_trim_memory_checks (); +memblock_overlaps_region_checks ();return 0 ; }
tools/testing/memblock/tests/common.h +3 -0
@@ -39,6 +39,9 @@ enum test_flags {assert ((_expected) == (_seen)); \ } while (0) +#define ASSERT_TRUE (_seen) ASSERT_EQ(true, _seen) +#define ASSERT_FALSE (_seen) ASSERT_EQ(false, _seen) +/** * ASSERT_NE(): * Check the condition
Signature · 1 line
2.34.1
PATCH 6/6 mm/memblock: return true directly on finding overlap region
In reply to Wei YangNot necessary to break and check i against type->cnt again.
--- mm/memblock.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
mm/memblock.c +2 -2
@@ -194,8 +194,8 @@ bool __init_memblock memblock_overlaps_region(struct memblock_type *type,for (i =0 ; i < type->cnt; i++)if (memblock_addrs_overlap (base, size, type->regions[i].base, type->regions[i].size)) -break ; -return i < type->cnt; +return true; +return false; }/**
Signature · 1 line
2.34.1
Mike Rapoport
maintainerQuoted 12 lines · Wei Yang
Current
memblock_add_range()does the insertion with two round iteration.First round does the calculation of new region required, and second round does the actual insertion. Between them, if current max can't meet new region requirement, it is expanded.
The worst case is:
1. cnt == max
2. new range overlaps all existing region
Quoted 7 lines
This means the final cnt should be (2 * max + 1). Since we always double the array size, this means we only need to double the array twice at the worst case, which is fairly rare. For other cases, only once array double is enough.
Let's double the array immediately when there is no room for new region. This simplify the code a little.
Very similar patch was posted a while ago:
https://lore.kernel.org/all/[email protected]
and it caused boot regression:
https://lore.kernel.org/linux-mm/[email protected]
Quoted 123 lines
Signed-off-by Wei Yang <[email protected]>CC Jinyu Tang <[email protected]>CC Peng Zhang <[email protected]>--- mm/memblock.c | 74 +++++++++++++++------------------------------------ 1 file changed, 22 insertions(+), 52 deletions(-)mm/memblock.c +22
-52@@ -585,10 +585,9 @@ static int __init_memblock memblock_add_range(struct memblock_type *type, phys_addr_t base, phys_addr_t size, int nid, enum memblock_flags flags) { - bool insert = false; phys_addr_t obase = base;phys_addr_t end = base +memblock_cap_size (base, &size); -int idx, nr_new, start_rgn =-1 , end_rgn; +int idx, start_rgn =-1 , end_rgn;struct memblock_region *rgn;if (!size)@@ -606,25 +605,6 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,return 0 ; } -/* -* The worst case is when new range overlaps all existing regions, -* then we'll need type->cnt + 1 empty regions in @type. So if -* type->cnt * 2 + 1 is less than or equal to type->max, we know -* that there is enough empty regions in @type, and we can insert -* regions directly. -*/ -if (type->cnt *2 +1 <= type->max) - insert = true; - -repeat: -/* -* The following is executed twice. Once with %false @insert and -* then with %true. The first counts the number of regions needed -* to accommodate the new area. The second actually inserts them. -*/ - base = obase; - nr_new =0 ; -for_each_memblock_type (idx, type, rgn) {phys_addr_t rbase = rgn->base;phys_addr_t rend = rbase + rgn->size;@@ -642,15 +622,17 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,WARN_ON (nid !=memblock_get_region_node (rgn));#endif WARN_ON (flags != rgn->flags); - nr_new++; -if (insert) { -if (start_rgn ==-1 ) - start_rgn = idx; - end_rgn = idx +1 ; -memblock_insert_region (type, idx++, base, - rbase - base, nid, - flags); +if (type->cnt >= type->max) { +if (memblock_double_array (type, obase, size) <0 ) +return -ENOMEM ; } + +if (start_rgn ==-1 ) + start_rgn = idx; + end_rgn = idx +1 ; +memblock_insert_region (type, idx++, base, + rbase - base, nid, + flags); }/* area below @rend is dealt with, forget about it */ base =min (rend, end);@@ -658,33 +640,21 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,/* insert the remaining portion */ if (base < end) { - nr_new++; -if (insert) { -if (start_rgn ==-1 ) - start_rgn = idx; - end_rgn = idx +1 ; -memblock_insert_region (type, idx, base, end - base, - nid, flags); +if (type->cnt >= type->max) { +if (memblock_double_array (type, obase, size) <0 ) +return -ENOMEM ; } - } -if (!nr_new) -return 0 ; +if (start_rgn ==-1 ) + start_rgn = idx; + end_rgn = idx +1 ; +memblock_insert_region (type, idx, base, end - base, + nid, flags); + } -/* -* If this was the first round, resize array and repeat for actual -* insertions; otherwise, merge and return. -*/ -if (!insert) { -while (type->cnt + nr_new > type->max) -if (memblock_double_array (type, obase, size) <0 ) -return -ENOMEM ; - insert = true; - goto repeat; - }else { +if (start_rgn !=-1 )memblock_merge_regions (type, start_rgn, end_rgn); -return 0 ; - } +return 0 ; }/** Signature · 1 line
2.34.1
Signature · 2 lines
Sincerely yours, Mike.
Quoted 18 lines · Mike Rapoport
Quoted 17 lines · Wei Yang
Current
memblock_add_range()does the insertion with two round iteration.First round does the calculation of new region required, and second round does the actual insertion. Between them, if current max can't meet new region requirement, it is expanded.
The worst case is:
1. cnt == max
2. new range overlaps all existing regionThis means the final cnt should be (2 * max + 1). Since we always double the array size, this means we only need to double the array twice at the worst case, which is fairly rare. For other cases, only once array double is enough.
Quoted 9 lines
Quoted 2 lines
Let's double the array immediately when there is no room for new region. This simplify the code a little.
Very similar patch was posted a while ago:
https://lore.kernel.org/all/[email protected]and it caused boot regression:
https://lore.kernel.org/linux-mm/[email protected]
Got the reason for the error.
When we add range to reserved and need double array, following call happends:
memblock_add_range()
idx <- where we want to insert new range
memblock_double_array()
find available range for new regions
memblock_reserve() available range
memblock_insert_region() at idx
The error case happens when find available range below what we want to add, the idx may change after memblock_reserve().
The following change looks could fix it.
mm/memblock.c +19 -1
@@ -395,6 +395,7 @@ void __init memblock_discard(void)/** * memblock_double_array - double the size of the memblock regions array * @type: memblock type of the regions array being doubled +* @idx: current region index if we are iterating * @new_area_start: starting address of memory range to avoid overlap with * @new_area_size: size of memory range to avoid overlap with *
@@ -408,6 +409,7 @@ void __init memblock_discard(void)* 0 on success, -1 on failure. */ static int __init_memblock memblock_double_array(struct memblock_type *type, +int *idx,phys_addr_t new_area_start,phys_addr_t new_area_size) {
@@ -490,8 +492,24 @@ static int __init_memblock memblock_double_array(struct memblock_type *type,* Reserve the new array if that comes from the memblock. Otherwise, we * needn't do it */ -if (!use_slab) +if (!use_slab) { +/* +* When double array for reserved.regions, we may need to +* adjust the index on finding new_array below +* new_area_start. This is because memblock_reserve() below +* will insert the range ahead of us. +* While the insertion may result into three cases: +* 1. not adjacent any region, increase one index +* 2. adjacent one region, not change index +* 3. adjacent two regions, reduce one index +*/ +int ocnt =-1 ; +if (idx && type == &memblock.reserved && addr <= new_area_start) + ocnt = type->cnt;BUG_ON (memblock_reserve (addr, new_alloc_size)); +if (ocnt >=0 ) + *idx += type->cnt - ocnt; + }/* Update slab flag */ *in_slab = use_slab;
Signature · 2 lines
Wei Yang Help you, Help me
Mike Rapoport
maintainerQuoted 40 lines · Wei Yang
Quoted 18 lines · Mike Rapoport
Quoted 17 lines · Wei Yang
Current
memblock_add_range()does the insertion with two round iteration.First round does the calculation of new region required, and second round does the actual insertion. Between them, if current max can't meet new region requirement, it is expanded.
The worst case is:
1. cnt == max
2. new range overlaps all existing regionThis means the final cnt should be (2 * max + 1). Since we always double the array size, this means we only need to double the array twice at the worst case, which is fairly rare. For other cases, only once array double is enough.
Quoted 9 lines
Quoted 2 lines
Let's double the array immediately when there is no room for new region. This simplify the code a little.
Very similar patch was posted a while ago:
https://lore.kernel.org/all/[email protected]and it caused boot regression:
https://lore.kernel.org/linux-mm/[email protected]Got the reason for the error.
When we add range to reserved and need double array, following call happends:
memblock_add_range()
idx <- where we want to insert new range
memblock_double_array()
find available range for new regions
memblock_reserve()available range
memblock_insert_region()at idx
Quoted 4 lines
The error case happens when find available range below what we want to add, the idx may change after
memblock_reserve().The following change looks could fix it.
I don't think the micro-optimization of the second loop in memblock_add_range() worth the churn and potential bugs.
Quoted 51 lines
mm/memblock.c +19
-1@@ -395,6 +395,7 @@ void __init memblock_discard(void)/** * memblock_double_array - double the size of the memblock regions array * @type: memblock type of the regions array being doubled +* @idx: current region index if we are iterating * @new_area_start: starting address of memory range to avoid overlap with * @new_area_size: size of memory range to avoid overlap with * @@ -408,6 +409,7 @@ void __init memblock_discard(void)* 0 on success, -1 on failure. */ static int __init_memblock memblock_double_array(struct memblock_type *type, +int *idx,phys_addr_t new_area_start,phys_addr_t new_area_size) {@@ -490,8 +492,24 @@ static int __init_memblock memblock_double_array(struct memblock_type *type,* Reserve the new array if that comes from the memblock. Otherwise, we * needn't do it */ -if (!use_slab) +if (!use_slab) { +/* +* When double array for reserved.regions, we may need to +* adjust the index on finding new_array below +* new_area_start. This is because memblock_reserve() below +* will insert the range ahead of us. +* While the insertion may result into three cases: +* 1. not adjacent any region, increase one index +* 2. adjacent one region, not change index +* 3. adjacent two regions, reduce one index +*/ +int ocnt =-1 ; +if (idx && type == &memblock.reserved && addr <= new_area_start) + ocnt = type->cnt;BUG_ON (memblock_reserve (addr, new_alloc_size)); +if (ocnt >=0 ) + *idx += type->cnt - ocnt; + }/* Update slab flag */ *in_slab = use_slab;Signature · 3 lines
-- Wei Yang Help you, Help me
Signature · 2 lines
Sincerely yours, Mike.
Quoted 41 lines · Mike Rapoport
Quoted 40 lines · Wei Yang
Quoted 18 lines · Mike Rapoport
Quoted 17 lines · Wei Yang
Current
memblock_add_range()does the insertion with two round iteration.First round does the calculation of new region required, and second round does the actual insertion. Between them, if current max can't meet new region requirement, it is expanded.
The worst case is:
1. cnt == max
2. new range overlaps all existing regionThis means the final cnt should be (2 * max + 1). Since we always double the array size, this means we only need to double the array twice at the worst case, which is fairly rare. For other cases, only once array double is enough.
Quoted 9 lines
Quoted 2 lines
Let's double the array immediately when there is no room for new region. This simplify the code a little.
Very similar patch was posted a while ago:
https://lore.kernel.org/all/[email protected]and it caused boot regression:
https://lore.kernel.org/linux-mm/[email protected]Got the reason for the error.
When we add range to reserved and need double array, following call happends:
memblock_add_range()
idx <- where we want to insert new range
memblock_double_array()
find available range for new regions
memblock_reserve()available range
memblock_insert_region()at idx
Quoted 8 lines
Quoted 4 lines
The error case happens when find available range below what we want to add, the idx may change after
memblock_reserve().The following change looks could fix it.
I don't think the micro-optimization of the second loop in
memblock_add_range()worth the churn and potential bugs.
Sure, would drop this one.
Signature · 2 lines
Wei Yang Help you, Help me