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

PATCH In review Xishi Qiu 2 participants 9 messages Jul 31, 2015 – Aug 14, 2015

Subsystems (2)

Memory management Page allocator

lore

Share & tools

lore

Xishi Qiu

author

2015-07-31 09:31 UTC #0 lore raw

PATCH 1/1 mm: add the block to the tail of the list in expand()

__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 <[email protected]>

---
 mm/page_alloc.c |    7 ++++++-
 1 files changed, 6 insertions(+), 1 deletions(-)

mm/page_alloc.c +6 -1

index 506eac8..517a11c 100644
@@ -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);
 	}

Signature · 1 line

1.7.1

Dave Hansen

2015-07-31 23:24 UTC #1 lore raw

Quoted 3 lines · 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.

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?

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

Xishi Qiu

author

2015-08-03 02:06 UTC #2 lore raw

Quoted 13 lines · Dave Hansen

Quoted 3 lines · 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.
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.

Quoted 5 lines

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

Quoted 5 lines

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

Dave Hansen

2015-08-03 04:10 UTC #3 lore raw

Quoted 6 lines · Xishi Qiu

Quoted 3 lines
Quoted 3 lines
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.

Xishi Qiu

author

2015-08-04 01:13 UTC #4 lore raw

Quoted 5 lines · Dave Hansen

Quoted 4 lines · Xishi Qiu
Quoted 3 lines
Quoted 3 lines
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

Quoted 8 lines

Quoted 2 lines
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

Quoted 2 lines

.

Dave Hansen

2015-08-04 14:27 UTC #5 lore raw

Quoted 1 line · Xishi Qiu

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.

Xishi Qiu

author

2015-08-05 07:54 UTC #6 lore raw

Quoted 7 lines · Dave Hansen

Quoted 1 line · Xishi Qiu
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().

mm/page_alloc.c +6 -0

@@ -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);

Quoted 9 lines

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.
.

Dave Hansen

2015-08-05 14:50 UTC #7 lore raw

Quoted 1 line · Xishi Qiu

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

...

mm/page_alloc.c static inline void expand(struct zone *zone, struct page *page, · line 842

Quoted 5 lines

mm/page_alloc.c +5 -0

+         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.

Xishi Qiu

author

2015-08-14 07:56 UTC #8 lore raw

Quoted 12 lines · Dave Hansen

Quoted 1 line · Xishi Qiu
I add some debug code like this, but it doesn't trigger the dump_stack().
...
mm/page_alloc.c static inline void expand(struct zone *zone, struct page *page, · line 842
Quoted 5 lines
mm/page_alloc.c +5 -0
+         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

Quoted 2 lines

.