linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [PATCH] mm/page_alloc: speeding up the iteration of max_order
@ 2020-12-02 12:18 Muchun Song
  2020-12-03 17:37 ` Vlastimil Babka
  0 siblings, 1 reply; 5+ messages in thread
From: Muchun Song @ 2020-12-02 12:18 UTC (permalink / raw)
  To: akpm; +Cc: linux-mm, linux-kernel, Muchun Song

When we free a page whose order is very close to MAX_ORDER and greater
than pageblock_order, it wastes some CPU cycles to increase max_order
to MAX_ORDER one by one and check the pageblock migratetype of that page
repeatedly especially when MAX_ORDER is much larger than pageblock_order.

Signed-off-by: Muchun Song <songmuchun@bytedance.com>
---
 mm/page_alloc.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index 141f12e5142c..959541234e1d 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c
@@ -1041,7 +1041,7 @@ static inline void __free_one_page(struct page *page,
 		pfn = combined_pfn;
 		order++;
 	}
-	if (max_order < MAX_ORDER) {
+	if (max_order < MAX_ORDER && order < MAX_ORDER - 1) {
 		/* If we are here, it means order is >= pageblock_order.
 		 * We want to prevent merge between freepages on isolate
 		 * pageblock and normal pageblock. Without this, pageblock
@@ -1062,6 +1062,8 @@ static inline void __free_one_page(struct page *page,
 						is_migrate_isolate(buddy_mt)))
 				goto done_merging;
 		}
+		if (unlikely(order != max_order - 1))
+			max_order = order + 1;
 		max_order++;
 		goto continue_merging;
 	}
-- 
2.11.0


^ permalink raw reply	[flat|nested] 5+ messages in thread

* Re: [PATCH] mm/page_alloc: speeding up the iteration of max_order
  2020-12-02 12:18 [PATCH] mm/page_alloc: speeding up the iteration of max_order Muchun Song
@ 2020-12-03 17:37 ` Vlastimil Babka
  2020-12-04  4:03   ` [External] " Muchun Song
  0 siblings, 1 reply; 5+ messages in thread
From: Vlastimil Babka @ 2020-12-03 17:37 UTC (permalink / raw)
  To: Muchun Song, akpm; +Cc: linux-mm, linux-kernel

On 12/2/20 1:18 PM, Muchun Song wrote:
> When we free a page whose order is very close to MAX_ORDER and greater
> than pageblock_order, it wastes some CPU cycles to increase max_order
> to MAX_ORDER one by one and check the pageblock migratetype of that page

But we have to do that. It's not the same page, it's the merged page and the new
buddy is a different pageblock and we need to check if they have compatible
migratetypes and can merge, or we have to bail out. So the patch is wrong.

> repeatedly especially when MAX_ORDER is much larger than pageblock_order.

Do we have such architectures/configurations anyway?

> Signed-off-by: Muchun Song <songmuchun@bytedance.com>
> ---
>  mm/page_alloc.c | 4 +++-
>  1 file changed, 3 insertions(+), 1 deletion(-)
> 
> diff --git a/mm/page_alloc.c b/mm/page_alloc.c
> index 141f12e5142c..959541234e1d 100644
> --- a/mm/page_alloc.c
> +++ b/mm/page_alloc.c
> @@ -1041,7 +1041,7 @@ static inline void __free_one_page(struct page *page,
>  		pfn = combined_pfn;
>  		order++;
>  	}
> -	if (max_order < MAX_ORDER) {
> +	if (max_order < MAX_ORDER && order < MAX_ORDER - 1) {
>  		/* If we are here, it means order is >= pageblock_order.
>  		 * We want to prevent merge between freepages on isolate
>  		 * pageblock and normal pageblock. Without this, pageblock
> @@ -1062,6 +1062,8 @@ static inline void __free_one_page(struct page *page,
>  						is_migrate_isolate(buddy_mt)))
>  				goto done_merging;
>  		}
> +		if (unlikely(order != max_order - 1))
> +			max_order = order + 1;

Or maybe I just don't understand what this is doing. When is the new 'if' even
true? We just bailed out of "while (order < max_order - 1)" after the last
"order++", which means it should hold that "order == max_order - 1")?
Your description sounds like you want to increase max_order to MAX_ORDER in one
step, which as I explained would be wrong. But the implementation looks actually
like a no-op.

>  		max_order++;
>  		goto continue_merging;
>  	}
> 


^ permalink raw reply	[flat|nested] 5+ messages in thread

* Re: [External] Re: [PATCH] mm/page_alloc: speeding up the iteration of max_order
  2020-12-03 17:37 ` Vlastimil Babka
@ 2020-12-04  4:03   ` Muchun Song
  2020-12-04 10:28     ` Vlastimil Babka
  0 siblings, 1 reply; 5+ messages in thread
From: Muchun Song @ 2020-12-04  4:03 UTC (permalink / raw)
  To: Vlastimil Babka; +Cc: Andrew Morton, Linux Memory Management List, LKML

On Fri, Dec 4, 2020 at 1:37 AM Vlastimil Babka <vbabka@suse.cz> wrote:
>
> On 12/2/20 1:18 PM, Muchun Song wrote:
> > When we free a page whose order is very close to MAX_ORDER and greater
> > than pageblock_order, it wastes some CPU cycles to increase max_order
> > to MAX_ORDER one by one and check the pageblock migratetype of that page
>
> But we have to do that. It's not the same page, it's the merged page and the new
> buddy is a different pageblock and we need to check if they have compatible
> migratetypes and can merge, or we have to bail out. So the patch is wrong.
>
> > repeatedly especially when MAX_ORDER is much larger than pageblock_order.
>
> Do we have such architectures/configurations anyway?
>
> > Signed-off-by: Muchun Song <songmuchun@bytedance.com>
> > ---
> >  mm/page_alloc.c | 4 +++-
> >  1 file changed, 3 insertions(+), 1 deletion(-)
> >
> > diff --git a/mm/page_alloc.c b/mm/page_alloc.c
> > index 141f12e5142c..959541234e1d 100644
> > --- a/mm/page_alloc.c
> > +++ b/mm/page_alloc.c
> > @@ -1041,7 +1041,7 @@ static inline void __free_one_page(struct page *page,
> >               pfn = combined_pfn;
> >               order++;
> >       }
> > -     if (max_order < MAX_ORDER) {

If we free a page with order == MAX_ORDER - 1, it has no buddy.
The following pageblock operation is also pointless.

> > +     if (max_order < MAX_ORDER && order < MAX_ORDER - 1) {
> >               /* If we are here, it means order is >= pageblock_order.
> >                * We want to prevent merge between freepages on isolate
> >                * pageblock and normal pageblock. Without this, pageblock
> > @@ -1062,6 +1062,8 @@ static inline void __free_one_page(struct page *page,
> >                                               is_migrate_isolate(buddy_mt)))
> >                               goto done_merging;
> >               }
> > +             if (unlikely(order != max_order - 1))
> > +                     max_order = order + 1;
>
> Or maybe I just don't understand what this is doing. When is the new 'if' even
> true? We just bailed out of "while (order < max_order - 1)" after the last
> "order++", which means it should hold that "order == max_order - 1")?

No, I do not agree. The MAX_ORDER may be greater than 11.

# git grep "CONFIG_FORCE_MAX_ZONEORDER"
# arch/arm/configs/imx_v6_v7_defconfig:CONFIG_FORCE_MAX_ZONEORDER=14
# arch/powerpc/configs/85xx/ge_imp3a_defconfig:CONFIG_FORCE_MAX_ZONEORDER=17
# arch/powerpc/configs/fsl-emb-nonhw.config:CONFIG_FORCE_MAX_ZONEORDER=13

Have you seen it? On some architecture, the MAX_ORDER
can be 17. When we free a page with an order 16. Without this
patch, the max_order should be increased one by one from 10 to
17.

Thanks.


> Your description sounds like you want to increase max_order to MAX_ORDER in one
> step, which as I explained would be wrong. But the implementation looks actually
> like a no-op.
>
> >               max_order++;
> >               goto continue_merging;
> >       }
> >
>


--
Yours,
Muchun

^ permalink raw reply	[flat|nested] 5+ messages in thread

* Re: [External] Re: [PATCH] mm/page_alloc: speeding up the iteration of max_order
  2020-12-04  4:03   ` [External] " Muchun Song
@ 2020-12-04 10:28     ` Vlastimil Babka
  2020-12-04 11:11       ` Muchun Song
  0 siblings, 1 reply; 5+ messages in thread
From: Vlastimil Babka @ 2020-12-04 10:28 UTC (permalink / raw)
  To: Muchun Song; +Cc: Andrew Morton, Linux Memory Management List, LKML

On 12/4/20 5:03 AM, Muchun Song wrote:
> On Fri, Dec 4, 2020 at 1:37 AM Vlastimil Babka <vbabka@suse.cz> wrote:
>>
>> On 12/2/20 1:18 PM, Muchun Song wrote:
>> > When we free a page whose order is very close to MAX_ORDER and greater
>> > than pageblock_order, it wastes some CPU cycles to increase max_order
>> > to MAX_ORDER one by one and check the pageblock migratetype of that page
>>
>> But we have to do that. It's not the same page, it's the merged page and the new
>> buddy is a different pageblock and we need to check if they have compatible
>> migratetypes and can merge, or we have to bail out. So the patch is wrong.
>>
>> > repeatedly especially when MAX_ORDER is much larger than pageblock_order.
>>
>> Do we have such architectures/configurations anyway?
>>
>> > Signed-off-by: Muchun Song <songmuchun@bytedance.com>
>> > ---
>> >  mm/page_alloc.c | 4 +++-
>> >  1 file changed, 3 insertions(+), 1 deletion(-)
>> >
>> > diff --git a/mm/page_alloc.c b/mm/page_alloc.c
>> > index 141f12e5142c..959541234e1d 100644
>> > --- a/mm/page_alloc.c
>> > +++ b/mm/page_alloc.c
>> > @@ -1041,7 +1041,7 @@ static inline void __free_one_page(struct page *page,
>> >               pfn = combined_pfn;
>> >               order++;
>> >       }
>> > -     if (max_order < MAX_ORDER) {
> 
> If we free a page with order == MAX_ORDER - 1, it has no buddy.
> The following pageblock operation is also pointless.

OK, I see.

>> > +     if (max_order < MAX_ORDER && order < MAX_ORDER - 1) {

Yes, this makes sense, as in your other patch we shouldn't check the buddy when
order == MAX_ORDER - 1 already.

>> >               /* If we are here, it means order is >= pageblock_order.
>> >                * We want to prevent merge between freepages on isolate
>> >                * pageblock and normal pageblock. Without this, pageblock
>> > @@ -1062,6 +1062,8 @@ static inline void __free_one_page(struct page *page,
>> >                                               is_migrate_isolate(buddy_mt)))
>> >                               goto done_merging;
>> >               }
>> > +             if (unlikely(order != max_order - 1))
>> > +                     max_order = order + 1;
>> >               max_order++;

OK I see now what you want to do here. the "if" may be true if we already
entered the function with order > pageblock_order.
I think we could just simplfy the "if" and "max_order++" above to:

max_order = order + 2

which starts to get a bit ugly, so why not change max_order to be -1 (compared
to now) in the whole function:

max_order = min_t(unsigned int, MAX_ORDER - 1, pageblock_order);
...
continue_merging:
        while (order < max_order) {
...
if (order < MAX_ORDER - 1) {
// it's redundant to keep checking max_order < MAX_ORDER - 1 here after your
change, right?
...

max_order = order + 1; // less weird than "+ 2"

Off by one errors, here we go!

>> Or maybe I just don't understand what this is doing. When is the new 'if' even
>> true? We just bailed out of "while (order < max_order - 1)" after the last
>> "order++", which means it should hold that "order == max_order - 1")?
> 
> No, I do not agree. The MAX_ORDER may be greater than 11.
> 
> # git grep "CONFIG_FORCE_MAX_ZONEORDER"
> # arch/arm/configs/imx_v6_v7_defconfig:CONFIG_FORCE_MAX_ZONEORDER=14
> # arch/powerpc/configs/85xx/ge_imp3a_defconfig:CONFIG_FORCE_MAX_ZONEORDER=17
> # arch/powerpc/configs/fsl-emb-nonhw.config:CONFIG_FORCE_MAX_ZONEORDER=13
> 
> Have you seen it? On some architecture, the MAX_ORDER
> can be 17. When we free a page with an order 16. Without this
> patch, the max_order should be increased one by one from 10 to
> 17.
> 
> Thanks.
> 
> 
>> Your description sounds like you want to increase max_order to MAX_ORDER in one
>> step, which as I explained would be wrong. But the implementation looks actually
>> like a no-op.
>>
>> >               max_order++;
>> >               goto continue_merging;
>> >       }
>> >
>>
> 
> 
> --
> Yours,
> Muchun
> 


^ permalink raw reply	[flat|nested] 5+ messages in thread

* Re: [External] Re: [PATCH] mm/page_alloc: speeding up the iteration of max_order
  2020-12-04 10:28     ` Vlastimil Babka
@ 2020-12-04 11:11       ` Muchun Song
  0 siblings, 0 replies; 5+ messages in thread
From: Muchun Song @ 2020-12-04 11:11 UTC (permalink / raw)
  To: Vlastimil Babka; +Cc: Andrew Morton, Linux Memory Management List, LKML

On Fri, Dec 4, 2020 at 6:28 PM Vlastimil Babka <vbabka@suse.cz> wrote:
>
> On 12/4/20 5:03 AM, Muchun Song wrote:
> > On Fri, Dec 4, 2020 at 1:37 AM Vlastimil Babka <vbabka@suse.cz> wrote:
> >>
> >> On 12/2/20 1:18 PM, Muchun Song wrote:
> >> > When we free a page whose order is very close to MAX_ORDER and greater
> >> > than pageblock_order, it wastes some CPU cycles to increase max_order
> >> > to MAX_ORDER one by one and check the pageblock migratetype of that page
> >>
> >> But we have to do that. It's not the same page, it's the merged page and the new
> >> buddy is a different pageblock and we need to check if they have compatible
> >> migratetypes and can merge, or we have to bail out. So the patch is wrong.
> >>
> >> > repeatedly especially when MAX_ORDER is much larger than pageblock_order.
> >>
> >> Do we have such architectures/configurations anyway?
> >>
> >> > Signed-off-by: Muchun Song <songmuchun@bytedance.com>
> >> > ---
> >> >  mm/page_alloc.c | 4 +++-
> >> >  1 file changed, 3 insertions(+), 1 deletion(-)
> >> >
> >> > diff --git a/mm/page_alloc.c b/mm/page_alloc.c
> >> > index 141f12e5142c..959541234e1d 100644
> >> > --- a/mm/page_alloc.c
> >> > +++ b/mm/page_alloc.c
> >> > @@ -1041,7 +1041,7 @@ static inline void __free_one_page(struct page *page,
> >> >               pfn = combined_pfn;
> >> >               order++;
> >> >       }
> >> > -     if (max_order < MAX_ORDER) {
> >
> > If we free a page with order == MAX_ORDER - 1, it has no buddy.
> > The following pageblock operation is also pointless.
>
> OK, I see.
>
> >> > +     if (max_order < MAX_ORDER && order < MAX_ORDER - 1) {
>
> Yes, this makes sense, as in your other patch we shouldn't check the buddy when
> order == MAX_ORDER - 1 already.
>
> >> >               /* If we are here, it means order is >= pageblock_order.
> >> >                * We want to prevent merge between freepages on isolate
> >> >                * pageblock and normal pageblock. Without this, pageblock
> >> > @@ -1062,6 +1062,8 @@ static inline void __free_one_page(struct page *page,
> >> >                                               is_migrate_isolate(buddy_mt)))
> >> >                               goto done_merging;
> >> >               }
> >> > +             if (unlikely(order != max_order - 1))
> >> > +                     max_order = order + 1;
> >> >               max_order++;
>
> OK I see now what you want to do here. the "if" may be true if we already
> entered the function with order > pageblock_order.
> I think we could just simplfy the "if" and "max_order++" above to:
>
> max_order = order + 2
>
> which starts to get a bit ugly, so why not change max_order to be -1 (compared
> to now) in the whole function:
>
> max_order = min_t(unsigned int, MAX_ORDER - 1, pageblock_order);
> ...
> continue_merging:
>         while (order < max_order) {
> ...
> if (order < MAX_ORDER - 1) {
> // it's redundant to keep checking max_order < MAX_ORDER - 1 here after your
> change, right?
> ...
>
> max_order = order + 1; // less weird than "+ 2"
>
> Off by one errors, here we go!

Great! Good suggestions. Thanks.

>
> >> Or maybe I just don't understand what this is doing. When is the new 'if' even
> >> true? We just bailed out of "while (order < max_order - 1)" after the last
> >> "order++", which means it should hold that "order == max_order - 1")?
> >
> > No, I do not agree. The MAX_ORDER may be greater than 11.
> >
> > # git grep "CONFIG_FORCE_MAX_ZONEORDER"
> > # arch/arm/configs/imx_v6_v7_defconfig:CONFIG_FORCE_MAX_ZONEORDER=14
> > # arch/powerpc/configs/85xx/ge_imp3a_defconfig:CONFIG_FORCE_MAX_ZONEORDER=17
> > # arch/powerpc/configs/fsl-emb-nonhw.config:CONFIG_FORCE_MAX_ZONEORDER=13
> >
> > Have you seen it? On some architecture, the MAX_ORDER
> > can be 17. When we free a page with an order 16. Without this
> > patch, the max_order should be increased one by one from 10 to
> > 17.
> >
> > Thanks.
> >
> >
> >> Your description sounds like you want to increase max_order to MAX_ORDER in one
> >> step, which as I explained would be wrong. But the implementation looks actually
> >> like a no-op.
> >>
> >> >               max_order++;
> >> >               goto continue_merging;
> >> >       }
> >> >
> >>
> >
> >
> > --
> > Yours,
> > Muchun
> >
>


-- 
Yours,
Muchun

^ permalink raw reply	[flat|nested] 5+ messages in thread

end of thread, other threads:[~2020-12-04 11:12 UTC | newest]

Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-12-02 12:18 [PATCH] mm/page_alloc: speeding up the iteration of max_order Muchun Song
2020-12-03 17:37 ` Vlastimil Babka
2020-12-04  4:03   ` [External] " Muchun Song
2020-12-04 10:28     ` Vlastimil Babka
2020-12-04 11:11       ` Muchun Song

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).