[PATCH] mm: add the block to the tail of the list in expand()

[PATCH] mm: add the block to the tail of the list in expand()

[Xishi Qiu]

__free_one_page() will judge whether the the next-highest order is free,
then add the block to the tail or not. So when we split large order block, 
add the small block to the tail, it will reduce fragment.

Signed-off-by: Xishi Qiu <qiuxishi@huawei.com>
---
 mm/page_alloc.c |    7 ++++++-
 1 files changed, 6 insertions(+), 1 deletions(-)

diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index 506eac8..517a11c 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c
@@ -1267,7 +1267,12 @@ static inline void expand(struct zone *zone, struct page *page,
 			set_page_guard(zone, &page[size], high, migratetype);
 			continue;
 		}
-		list_add(&page[size].lru, &area->free_list[migratetype]);
+		/*
+		 * Add the block to the tail of the list, so it's less likely
+		 * to be used soon and more likely to be merged when the page
+		 * is freed.
+		 */
+		list_add_tail(&page[size].lru, &area->free_list[migratetype]);
 		area->nr_free++;
 		set_page_order(&page[size], high);
 	}
-- 
1.7.1

Re: [PATCH] mm: add the block to the tail of the list in expand()

[Dave Hansen]

On 07/31/2015 02:30 AM, Xishi Qiu wrote:
> __free_one_page() will judge whether the the next-highest order is free,
> then add the block to the tail or not. So when we split large order block, 
> add the small block to the tail, it will reduce fragment.

It's an interesting idea, but what does it do in practice?  Can you
measure a decrease in fragmentation?

Further, the comment above the function says:
 * The order of subdivision here is critical for the IO subsystem.
 * Please do not alter this order without good reasons and regression
 * testing.

Has there been regression testing?

Also, this might not do very much good in practice.  If you are
splitting a high-order page, you are doing the split because the
lower-order lists are empty.  So won't that list_add() be to an empty
list most of the time?  Or does the __rmqueue_fallback()
largest->smallest logic dominate?

Re: [PATCH] mm: add the block to the tail of the list in expand()

[Xishi Qiu]

On 2015/8/1 7:24, Dave Hansen wrote:

> On 07/31/2015 02:30 AM, Xishi Qiu wrote:
>> __free_one_page() will judge whether the the next-highest order is free,
>> then add the block to the tail or not. So when we split large order block, 
>> add the small block to the tail, it will reduce fragment.
> 
> It's an interesting idea, but what does it do in practice?  Can you
> measure a decrease in fragmentation?
> 
> Further, the comment above the function says:
>  * The order of subdivision here is critical for the IO subsystem.
>  * Please do not alter this order without good reasons and regression
>  * testing.
> 
> Has there been regression testing?
> 
> Also, this might not do very much good in practice.  If you are
> splitting a high-order page, you are doing the split because the
> lower-order lists are empty.  So won't that list_add() be to an empty

Hi Dave,

I made a mistake, you are right, all the lower-order lists are empty,
so it is no sense to add to the tail.

Thanks,
Xishi Qiu

> list most of the time?  Or does the __rmqueue_fallback()
> largest->smallest logic dominate?
> 
> .
> 

Re: [PATCH] mm: add the block to the tail of the list in expand()

[Dave Hansen]

On 08/02/2015 07:05 PM, Xishi Qiu wrote:
>> > Also, this might not do very much good in practice.  If you are
>> > splitting a high-order page, you are doing the split because the
>> > lower-order lists are empty.  So won't that list_add() be to an empty
> 
> I made a mistake, you are right, all the lower-order lists are empty,
> so it is no sense to add to the tail.

I actually tested this experimentally and the lists are not always
empty.  It's probably __rmqueue_smallest() vs. __rmqueue_fallback() logic.

In any case, you might want to double-check.

Re: [PATCH] mm: add the block to the tail of the list in expand()

[Xishi Qiu]

On 2015/8/3 12:10, Dave Hansen wrote:

> On 08/02/2015 07:05 PM, Xishi Qiu wrote:
>>>> Also, this might not do very much good in practice.  If you are
>>>> splitting a high-order page, you are doing the split because the
>>>> lower-order lists are empty.  So won't that list_add() be to an empty
>>
>> I made a mistake, you are right, all the lower-order lists are empty,
>> so it is no sense to add to the tail.
> 
> I actually tested this experimentally and the lists are not always
> empty.  It's probably __rmqueue_smallest() vs. __rmqueue_fallback() logic.
> 
> In any case, you might want to double-check.
> 

Hi Dave,

How did you do the experiment?

Thanks,
Xishi Qiu

> .
> 

Re: [PATCH] mm: add the block to the tail of the list in expand()

[Dave Hansen]

On 08/03/2015 06:13 PM, Xishi Qiu wrote:
> How did you do the experiment?

I just stuck in some counters in expand() that looked to see whether the
list was empty or not when the page is added and then printed them out
occasionally.

It will be interesting to see the results both on a freshly-booted
system and one that's reached relatively steady-state and is moving
around a minimal number of pageblocks between the different types.

In any case, the end result here needs to be some indication that the
patch either helps ease fragmentation or helps performance.

Re: [PATCH] mm: add the block to the tail of the list in expand()

[Xishi Qiu]

On 2015/8/4 22:27, Dave Hansen wrote:

> On 08/03/2015 06:13 PM, Xishi Qiu wrote:
>> How did you do the experiment?
> 
> I just stuck in some counters in expand() that looked to see whether the
> list was empty or not when the page is added and then printed them out
> occasionally.
> 

Hi Dave,

I add some debug code like this, but it doesn't trigger the dump_stack().

--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c
@@ -834,6 +834,12 @@ static inline void expand(struct zone *zone, struct page *page,
                        continue;
                }
 #endif
+
+         if (!list_empty(&area->free_list[migratetype])) {
+                 printk("expand(), the list is not empty\n");
+                 dump_stack();
+         }
+
                list_add(&page[size].lru, &area->free_list[migratetype]);
                area->nr_free++;
                set_page_order(&page[size], high);


> It will be interesting to see the results both on a freshly-booted
> system and one that's reached relatively steady-state and is moving
> around a minimal number of pageblocks between the different types.
> 
> In any case, the end result here needs to be some indication that the
> patch either helps ease fragmentation or helps performance.
> 
> .
> 

Re: [PATCH] mm: add the block to the tail of the list in expand()

[Dave Hansen]

On 08/05/2015 12:54 AM, Xishi Qiu wrote:
> I add some debug code like this, but it doesn't trigger the dump_stack().
...
> +         if (!list_empty(&area->free_list[migratetype])) {
> +                 printk("expand(), the list is not empty\n");
> +                 dump_stack();
> +         }
> +

That will probably not trigger unless you have allocations that are
falling back and converting other pageblocks from other migratetypes.

Re: [PATCH] mm: add the block to the tail of the list in expand()

[Xishi Qiu]

On 2015/8/5 22:47, Dave Hansen wrote:

> On 08/05/2015 12:54 AM, Xishi Qiu wrote:
>> I add some debug code like this, but it doesn't trigger the dump_stack().
> ...
>> +         if (!list_empty(&area->free_list[migratetype])) {
>> +                 printk("expand(), the list is not empty\n");
>> +                 dump_stack();
>> +         }
>> +
> 
> That will probably not trigger unless you have allocations that are
> falling back and converting other pageblocks from other migratetypes.
> 

Hi Dave,

I run some stress test, and trigger the print, it shows that the list 
is not empty. The reason is than fallback will find the largest possible
block of pages in the other list, 

e.g. 
1. we alloc order=2 block, and call __rmqueue_fallback().
2. we find other list current_order=7 is not empty, and the lists(in the
same pageblock) that order from 3~6 are not empty too.
3. then expand() will find the list is not empty.

right?

Thanks,
Xishi Qiu

> .
>