| Message ID | 20240414004531.6601-1-richard.weiyang@gmail.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | [1/6] mm/memblock: reduce the two round insertion of memblock_add_range() | expand |
On Sun, Apr 14, 2024 at 12:45:26AM +0000, Wei Yang wrote: > 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. Very similar patch was posted a while ago: https://lore.kernel.org/all/20221025070943.363578-1-yajun.deng@linux.dev and it caused boot regression: https://lore.kernel.org/linux-mm/Y2oLYB7Tu7J91tVm@linux.ibm.com > Signed-off-by: Wei Yang <richard.weiyang@gmail.com> > CC: Jinyu Tang <tjytimi@163.com> > CC: Peng Zhang <zhangpeng.00@bytedance.com> > --- > mm/memblock.c | 74 +++++++++++++++------------------------------------ > 1 file changed, 22 insertions(+), 52 deletions(-) > > diff --git a/mm/memblock.c b/mm/memblock.c > index 98d25689cf10..b46109300927 100644 > --- a/mm/memblock.c > +++ b/mm/memblock.c > @@ -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; > } > > /** > -- > 2.34.1 >
On Mon, Apr 15, 2024 at 06:17:56PM +0300, Mike Rapoport wrote: >On Sun, Apr 14, 2024 at 12:45:26AM +0000, Wei Yang wrote: >> 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. > >Very similar patch was posted a while ago: >https://lore.kernel.org/all/20221025070943.363578-1-yajun.deng@linux.dev > >and it caused boot regression: >https://lore.kernel.org/linux-mm/Y2oLYB7Tu7J91tVm@linux.ibm.com > 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. diff --git a/mm/memblock.c b/mm/memblock.c index 98d25689cf10..52bc9a4b20da 100644 --- a/mm/memblock.c +++ b/mm/memblock.c @@ -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;
On Mon, Apr 22, 2024 at 02:55:00AM +0000, Wei Yang wrote: > On Mon, Apr 15, 2024 at 06:17:56PM +0300, Mike Rapoport wrote: > >On Sun, Apr 14, 2024 at 12:45:26AM +0000, Wei Yang wrote: > >> 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. > > > >Very similar patch was posted a while ago: > >https://lore.kernel.org/all/20221025070943.363578-1-yajun.deng@linux.dev > > > >and it caused boot regression: > >https://lore.kernel.org/linux-mm/Y2oLYB7Tu7J91tVm@linux.ibm.com > > > > 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. I don't think the micro-optimization of the second loop in memblock_add_range() worth the churn and potential bugs. > diff --git a/mm/memblock.c b/mm/memblock.c > index 98d25689cf10..52bc9a4b20da 100644 > --- a/mm/memblock.c > +++ b/mm/memblock.c > @@ -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; > > > -- > Wei Yang > Help you, Help me
On Wed, Apr 24, 2024 at 04:15:30PM +0300, Mike Rapoport wrote: >On Mon, Apr 22, 2024 at 02:55:00AM +0000, Wei Yang wrote: >> On Mon, Apr 15, 2024 at 06:17:56PM +0300, Mike Rapoport wrote: >> >On Sun, Apr 14, 2024 at 12:45:26AM +0000, Wei Yang wrote: >> >> 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. >> > >> >Very similar patch was posted a while ago: >> >https://lore.kernel.org/all/20221025070943.363578-1-yajun.deng@linux.dev >> > >> >and it caused boot regression: >> >https://lore.kernel.org/linux-mm/Y2oLYB7Tu7J91tVm@linux.ibm.com >> > >> >> 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. > >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.
diff --git a/mm/memblock.c b/mm/memblock.c index 98d25689cf10..b46109300927 100644 --- a/mm/memblock.c +++ b/mm/memblock.c @@ -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; } /**
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. Signed-off-by: Wei Yang <richard.weiyang@gmail.com> CC: Jinyu Tang <tjytimi@163.com> CC: Peng Zhang <zhangpeng.00@bytedance.com> --- mm/memblock.c | 74 +++++++++++++++------------------------------------ 1 file changed, 22 insertions(+), 52 deletions(-)