teach kswapd about higher order allocations

3/3

------------------------------------------------------------------------

Teach kswapd to free memory on behalf of higher order allocators. This could be important for higher order atomic allocations because they otherwise have no means to free the memory themselves.

Signed-off-by Nick Piggin <[email protected]>

---

 linux-2.6-npiggin/include/linux/mmzone.h |    5 +--
 linux-2.6-npiggin/mm/page_alloc.c        |    3 +
 linux-2.6-npiggin/mm/vmscan.c            |   48 ++++++++++++++++++-------------
 3 files changed, 34 insertions(+), 22 deletions(-)

diff -puN mm/vmscan.c~vm-kswapd-heed-order-watermarks mm/vmscan.c

2/3

Move the watermark checking code into a single function. Extend it to account for the order of the allocation and the number of free pages that could satisfy such a request.

Signed-off-by Nick Piggin <[email protected]>

 linux-2.6-npiggin/include/linux/mmzone.h |    2 +
 linux-2.6-npiggin/mm/page_alloc.c        |   58 ++++++++++++++++++++-----------
 2 files changed, 41 insertions(+), 19 deletions(-)

diff -puN mm/page_alloc.c~vm-alloc-order-watermarks mm/page_alloc.c

mm/page_alloc.c renamed from mm/page_alloc.c~vm-alloc-order-watermarks +13 -0

@@ -586,6 +586,37 @@ buffered_rmqueue(struct zone *zone, int 
 }
 
 /*
+ * Return 1 if free pages are above 'mark'. This takes into account the order
+ * of the allocation.
+ */
+int zone_watermark_ok(struct zone *z, int order, unsigned long mark,
+		int alloc_type, int can_try_harder, int gfp_high)
+{
+	/* free_pages my go negative - that's OK */
+	long min = mark, free_pages = z->free_pages - (1 << order) + 1;
+	int o;
+
+	if (gfp_high)
+		min -= min / 2;
+	if (can_try_harder)

mm/page_alloc.c renamed from mm/page_alloc.c~vm-alloc-order-watermarks +8 -1

+
+		if (free_pages <= min)
+			return 0;
+	}
+	return 1;
+}
+
+/*
  * This is the 'heart' of the zoned buddy allocator.
  *
  * Herein lies the mysterious "incremental min".  That's the

@@ -606,7 +637,6 @@ __alloc_pages(unsigned int gfp_mask, uns
 		struct zonelist *zonelist)
 {
 	const int wait = gfp_mask & __GFP_WAIT;
-	unsigned long min;
 	struct zone **zones, *z;
 	struct page *page;
 	struct reclaim_state reclaim_state;

mm/page_alloc.c renamed from mm/page_alloc.c~vm-alloc-order-watermarks +6 -16

 			continue;
 
 		page = buffered_rmqueue(z, order, gfp_mask);

@@ -654,14 +684,9 @@ __alloc_pages(unsigned int gfp_mask, uns
 	 * coming from realtime tasks to go deeper into reserves
 	 */
 	for (i = 0; (z = zones[i]) != NULL; i++) {
-		min = z->pages_min;
-		if (gfp_mask & __GFP_HIGH)
-			min /= 2;
-		if (can_try_harder)
-			min -= min / 4;
-		min += (1<<order) + z->protection[alloc_type];
-
-		if (z->free_pages < min)
+		if (!zone_watermark_ok(z, order, z->pages_min,
+				alloc_type, can_try_harder,
+				gfp_mask & __GFP_HIGH))
 			continue;
 
 		page = buffered_rmqueue(z, order, gfp_mask);

@@ -697,14 +722,9 @@ rebalance:
 
 	/* go through the zonelist yet one more time */
 	for (i = 0; (z = zones[i]) != NULL; i++) {
-		min = z->pages_min;
-		if (gfp_mask & __GFP_HIGH)
-			min /= 2;
-		if (can_try_harder)
-			min -= min / 4;
-		min += (1<<order) + z->protection[alloc_type];
-
-		if (z->free_pages < min)
+		if (!zone_watermark_ok(z, order, z->pages_min,
+				alloc_type, can_try_harder,
+				gfp_mask & __GFP_HIGH))
 			continue;
 
 		page = buffered_rmqueue(z, order, gfp_mask);

diff -puN include/linux/mmzone.h~vm-alloc-order-watermarks include/linux/mmzone.h

include/linux/mmzone.h renamed from include/linux/mmzone.h~vm-alloc-order-watermarks +2 -0

@@ -279,6 +279,8 @@ void get_zone_counts(unsigned long *acti
 			unsigned long *free);
 void build_all_zonelists(void);
 void wakeup_kswapd(struct zone *zone);
+int zone_watermark_ok(struct zone *z, int order, unsigned long mark,
+		int alloc_type, int can_try_harder, int gfp_high);
 
 /*
  * zone_idx() returns 0 for the ZONE_DMA zone, 1 for the ZONE_NORMAL zone, etc.

_

Quoted 8 lines · Nick Piggin

2/3

Move the watermark checking code into a single function. Extend it to account for the order of the allocation and the number of free pages that could satisfy such a request.

Quoted 1 line

Signed-off-by Nick Piggin <[email protected]>

Hi Nick,

I have a few comments and doubts.

Quoted 25 lines

linux-2.6-npiggin/include/linux/mmzone.h | 2 +
linux-2.6-npiggin/mm/page_alloc.c | 58 ++++++++++++++++++++-----------

2 files changed, 41 insertions(+), 19 deletions(-)

diff -puN mm/page_alloc.c~vm-alloc-order-watermarks mm/page_alloc.c

mm/page_alloc.c renamed from mm/page_alloc.c~vm-alloc-order-watermarks +13 -0

@@ -586,6 +586,37 @@ buffered_rmqueue(struct zone *zone, int 
 }
 
 /*
+ * Return 1 if free pages are above 'mark'. This takes into account the order
+ * of the allocation.
+ */
+int zone_watermark_ok(struct zone *z, int order, unsigned long mark,
+		int alloc_type, int can_try_harder, int gfp_high)
+{
+	/* free_pages my go negative - that's OK */
+	long min = mark, free_pages = z->free_pages - (1 << order) + 1;
+	int o;
+
+	if (gfp_high)
+		min -= min / 2;
+	if (can_try_harder)

mm/page_alloc.c buffered_rmqueue(struct zone *zone, int · line 611

Quoted 10 lines

mm/page_alloc.c renamed from mm/page_alloc.c~vm-alloc-order-watermarks +10 -0

+		min -= min / 4;
+
+	if (free_pages <= min + z->protection[alloc_type])
+		return 0;
+	for (o = 0; o < order; o++) {
+		/* At the next order, this order's pages become unavailable */
+		free_pages -= z->free_area[order].nr_free << o;
+
+		/* Require fewer higher order pages to be free */
+		min >>= 1;

I can't understand this. You decrease from free_pages nr_order_free_pages << o, in a loop, and divide min by two.

What is the meaning of "nr_free_pages[order] << o" ? Its only meaningful when o == order?

You're multiplying the number of free pages of the order the allocation wants by "0, 1..order". The two values have different meanings, until o == order.

In the first iteration of the loop, order is 0, so you decrease from free_pages "z->free_area[order].nr_free". Again, the two values mean different things.

Can you enlight me?

I see you're trying to have some kind of extra protection, but the calculation is difficult to understand for me.

Quoted 21 lines

mm/page_alloc.c renamed from mm/page_alloc.c~vm-alloc-order-watermarks +8 -1

+
+		if (free_pages <= min)
+			return 0;
+	}
+	return 1;
+}
+
+/*
 * This is the 'heart' of the zoned buddy allocator.
 *
 * Herein lies the mysterious "incremental min".  That's the

@@ -606,7 +637,6 @@ __alloc_pages(unsigned int gfp_mask, uns
 		struct zonelist *zonelist)
 {
 	const int wait = gfp_mask & __GFP_WAIT;
-	unsigned long min;
 	struct zone **zones, *z;
 	struct page *page;
 	struct reclaim_state reclaim_state;

mm/page_alloc.c __alloc_pages(unsigned int gfp_mask, uns · line 671

Quoted 8 lines

mm/page_alloc.c renamed from mm/page_alloc.c~vm-alloc-order-watermarks +2 -2

@@ -636,9 +666,9 @@ __alloc_pages(unsigned int gfp_mask, uns
 
 	/* Go through the zonelist once, looking for a zone with enough free */
 	for (i = 0; (z = zones[i]) != NULL; i++) {
-		min = z->pages_low + (1<<order) + z->protection[alloc_type];
 
-		if (z->free_pages < min)
+		if (!zone_watermark_ok(z, order, z->pages_low,
+				alloc_type, 0, 0))

The original code didnt had the can_try_harder/gfp_high decrease which is now on zone_watermark_ok.

Means that those allocations will now be successful earlier, instead of going to the next zonelist iteration. kswapd will not be awake when it used to be.

Hopefully it doesnt matter that much. You did this by intention?

Quoted 12 lines · Marcelo Tosatti

Quoted 10 lines · Nick Piggin

2/3

Move the watermark checking code into a single function. Extend it to account
for the order of the allocation and the number of free pages that could satisfy
such a request.

Quoted 7 lines

Quoted 1 line

Signed-off-by Nick Piggin <[email protected]>

Hi Nick,

I have a few comments and doubts.

Hi Marcelo,
Thanks for the comments and review. It is always very helpful to have more eyes on this area of code especially. Let's see...

Quoted 52 lines

Quoted 36 lines

linux-2.6-npiggin/include/linux/mmzone.h | 2 +
linux-2.6-npiggin/mm/page_alloc.c | 58
++++++++++++++++++++-----------

2 files changed, 41 insertions(+), 19 deletions(-)

diff -puN mm/page_alloc.c~vm-alloc-order-watermarks mm/page_alloc.c
--- linux-2.6/mm/page_alloc.c~vm-alloc-order-watermarks 2004-10-27
16:41:32.000000000 +1000
+++ linux-2.6-npiggin/mm/page_alloc.c 2004-10-27
17:53:33.000000000 +1000

(quoted diff) +1 -0

@@ -586,6 +586,37 @@ buffered_rmqueue(struct zone *zone, int 
 }
 
 /*
+ * Return 1 if free pages are above 'mark'. This takes into account the 

order
+ * of the allocation.
+ */

mm/page_alloc.c renamed from mm/page_alloc.c~vm-alloc-order-watermarks +16 -0

+int zone_watermark_ok(struct zone *z, int order, unsigned long mark,
+		int alloc_type, int can_try_harder, int gfp_high)
+{
+	/* free_pages my go negative - that's OK */
+	long min = mark, free_pages = z->free_pages - (1 << order) + 1;
+	int o;
+
+	if (gfp_high)
+		min -= min / 2;
+	if (can_try_harder)
+		min -= min / 4;
+
+	if (free_pages <= min + z->protection[alloc_type])
+		return 0;
+	for (o = 0; o < order; o++) {
+		/* At the next order, this order's pages become unavailable 

*/

mm/page_alloc.c buffered_rmqueue(struct zone *zone, int · line 611

Quoted 4 lines

mm/page_alloc.c renamed from mm/page_alloc.c~vm-alloc-order-watermarks +4 -0

+		free_pages -= z->free_area[order].nr_free << o;
+
+		/* Require fewer higher order pages to be free */
+		min >>= 1;

I can't understand this. You decrease from free_pages nr_order_free_pages << o, in a loop, and divide min by two.

What is the meaning of "nr_free_pages[order] << o" ? Its only meaningful when o == order?

You're multiplying the number of free pages of the order the allocation wants by "0, 1..order". The two values have different meanings, until
o == order.

Quoted 9 lines

In the first iteration of the loop, order is 0, so you decrease from free_pages "z->free_area[order].nr_free". Again, the two values mean different things.

Can you enlight me?

I see you're trying to have some kind of extra protection, but the calculation is difficult to understand for me.

OK, we store the number of "order-pages" free for each order, so for example, 16K worth of order-2 pages (on a 4K page architecture) will count towards just 1 nr_free.

So now what we need to do in order to calculate, say the amount of memory that will satisfy order-2 *and above* (this is important) is the following:

	z->free_pages - (order[0].nr_free << 0) - (order[1].nr_free << 1)

to find order-3 and above, you also need to subtract (order[2].nr_free << 2).

I quite liked this method because it has progressively less cost on lower order allocations, and for order-0 we don't need to do any calculation.

Of course it is slightly racy, which is why I say free_pages can go negative,
but that should be OK.

Probably the comment there is woefully inadequate? - I sometimes forget that people can't read my mind :\

Quoted 40 lines

Quoted 21 lines

mm/page_alloc.c renamed from mm/page_alloc.c~vm-alloc-order-watermarks +8 -0

+
+		if (free_pages <= min)
+			return 0;
+	}
+	return 1;
+}
+
+/*

* This is the 'heart' of the zoned buddy allocator. *
* Herein lies the mysterious "incremental min". That's the

mm/page_alloc.c renamed from mm/page_alloc.c~vm-alloc-order-watermarks +0 -1

@@ -606,7 +637,6 @@ __alloc_pages(unsigned int gfp_mask, uns
 		struct zonelist *zonelist)
 {
 	const int wait = gfp_mask & __GFP_WAIT;
-	unsigned long min;
 	struct zone **zones, *z;
 	struct page *page;
 	struct reclaim_state reclaim_state;

mm/page_alloc.c __alloc_pages(unsigned int gfp_mask, uns · line 672

Quoted 9 lines

mm/page_alloc.c renamed from mm/page_alloc.c~vm-alloc-order-watermarks +2 -2

@@ -636,9 +666,9 @@ __alloc_pages(unsigned int gfp_mask, uns
 
 	/* Go through the zonelist once, looking for a zone with enough free 
 	*/
 	for (i = 0; (z = zones[i]) != NULL; i++) {
-		min = z->pages_low + (1<<order) + z->protection[alloc_type];
 
-		if (z->free_pages < min)
+		if (!zone_watermark_ok(z, order, z->pages_low,
+				alloc_type, 0, 0))

The original code didnt had the can_try_harder/gfp_high decrease which is now on zone_watermark_ok.

Means that those allocations will now be successful earlier, instead of going to the next zonelist iteration. kswapd will not be awake when it used to be.

Quoted 2 lines

Hopefully it doesnt matter that much. You did this by intention?

That should be OK: the last two zero arguments mean that doesn't get evaluated; so it should work as you'd expect I think?

Hi Nick!

Quoted 4 lines · Nick Piggin

So now what we need to do in order to calculate, say the amount of memory that will satisfy order-2 *and above* (this is important) is the following:

	z->free_pages - (order[0].nr_free << 0) - (order[1].nr_free << 1)

Shouldnt that be then

free_pages -= z->free_area[o].nr_free << o;

instead of the current

free_pages -= z->free_area[order].nr_free << o;

No?

Quoted 5 lines

to find order-3 and above, you also need to subtract (order[2].nr_free << 2).

I quite liked this method because it has progressively less cost on lower order allocations, and for order-0 we don't need to do any calculation.

OK, now I get it. The only think which bugs me is the multiplication of values with different meanings.

Quoted 14 lines · Marcelo Tosatti

Hi Nick!

Quoted 5 lines · Nick Piggin

So now what we need to do in order to calculate, say the amount of memory that will satisfy order-2 *and above* (this is important) is the following:

	z->free_pages - (order[0].nr_free << 0) - (order[1].nr_free << 1)

Shouldnt that be then

Quoted 8 lines

free_pages -= z->free_area[o].nr_free << o;

instead of the current

free_pages -= z->free_area[order].nr_free << o;

No?

Yes, you're absolutely right. Sorry, this is what you were getting at all along :P

Quoted 8 lines

Quoted 6 lines

to find order-3 and above, you also need to subtract (order[2].nr_free << 2).

I quite liked this method because it has progressively less cost on lower order allocations, and for order-0 we don't need to do any calculation.

Quoted 3 lines

OK, now I get it. The only think which bugs me is the multiplication of values with different meanings.

Yeah it's wrong, of course. Good catch, thanks.

If you would care to send a patch Marcelo? I don't have a recent -mm on hand at the moment. Would that be alright?

This typo probably means that the current code is not actually working as
intented - did any of you receive any feedback on this patch, wrt high order allocation intensive driver setup/workload, Nick and Andrew?

Quoted 2 lines · Nick Piggin

Yeah it's wrong, of course. Good catch, thanks.

Quoted 2 lines

If you would care to send a patch Marcelo? I don't have a recent -mm on hand at the moment. Would that be alright?

Sure, I'll prepare a patch.

This typo probably means that the current code is not actually working as intented - did any of you receive any feedback on this patch, wrt high order allocation intensive driver setup/workload, Nick and Andrew?

I have been using a simple module which allocates a big number of high order allocations in a row (for the defragmentation code testing), I'll give it a shot tomorrow to test Nick's high-order-kswapd scheme effectiveness.

Anyway, here is the patch:

Description:
Fix typo in Nick's kswapd-high-order awareness patch

Quoted 12 lines · Marcelo Tosatti

Quoted 10 lines · Nick Piggin

2/3

Move the watermark checking code into a single function. Extend it to account
for the order of the allocation and the number of free pages that could satisfy
such a request.

Quoted 7 lines

Quoted 1 line

Signed-off-by Nick Piggin <[email protected]>

Hi Nick,

I have a few comments and doubts.

Hi Marcelo,
Thanks for the comments and review. It is always very helpful to have more eyes on this area of code especially. Let's see...

Quoted 52 lines

Quoted 36 lines

linux-2.6-npiggin/include/linux/mmzone.h | 2 +
linux-2.6-npiggin/mm/page_alloc.c | 58
++++++++++++++++++++-----------

2 files changed, 41 insertions(+), 19 deletions(-)

diff -puN mm/page_alloc.c~vm-alloc-order-watermarks mm/page_alloc.c
--- linux-2.6/mm/page_alloc.c~vm-alloc-order-watermarks 2004-10-27
16:41:32.000000000 +1000
+++ linux-2.6-npiggin/mm/page_alloc.c 2004-10-27
17:53:33.000000000 +1000

(quoted diff) +1 -0

@@ -586,6 +586,37 @@ buffered_rmqueue(struct zone *zone, int 
 }
 
 /*
+ * Return 1 if free pages are above 'mark'. This takes into account the 

order
+ * of the allocation.
+ */

mm/page_alloc.c renamed from mm/page_alloc.c~vm-alloc-order-watermarks +16 -0

+int zone_watermark_ok(struct zone *z, int order, unsigned long mark,
+		int alloc_type, int can_try_harder, int gfp_high)
+{
+	/* free_pages my go negative - that's OK */
+	long min = mark, free_pages = z->free_pages - (1 << order) + 1;
+	int o;
+
+	if (gfp_high)
+		min -= min / 2;
+	if (can_try_harder)
+		min -= min / 4;
+
+	if (free_pages <= min + z->protection[alloc_type])
+		return 0;
+	for (o = 0; o < order; o++) {
+		/* At the next order, this order's pages become unavailable 

*/

mm/page_alloc.c buffered_rmqueue(struct zone *zone, int · line 611

Quoted 4 lines

mm/page_alloc.c renamed from mm/page_alloc.c~vm-alloc-order-watermarks +4 -0

+		free_pages -= z->free_area[order].nr_free << o;
+
+		/* Require fewer higher order pages to be free */
+		min >>= 1;

I can't understand this. You decrease from free_pages nr_order_free_pages << o, in a loop, and divide min by two.

What is the meaning of "nr_free_pages[order] << o" ? Its only meaningful when o == order?

You're multiplying the number of free pages of the order the allocation wants by "0, 1..order". The two values have different meanings, until
o == order.

Quoted 9 lines

In the first iteration of the loop, order is 0, so you decrease from free_pages "z->free_area[order].nr_free". Again, the two values mean different things.

Can you enlight me?

I see you're trying to have some kind of extra protection, but the calculation is difficult to understand for me.

OK, we store the number of "order-pages" free for each order, so for example, 16K worth of order-2 pages (on a 4K page architecture) will count towards just 1 nr_free.

So now what we need to do in order to calculate, say the amount of memory that will satisfy order-2 *and above* (this is important) is the following:

	z->free_pages - (order[0].nr_free << 0) - (order[1].nr_free << 1)

to find order-3 and above, you also need to subtract (order[2].nr_free << 2).

I quite liked this method because it has progressively less cost on lower order allocations, and for order-0 we don't need to do any calculation.

Of course it is slightly racy, which is why I say free_pages can go negative,
but that should be OK.

Probably the comment there is woefully inadequate? - I sometimes forget that people can't read my mind :\

Quoted 2 lines · Nick Piggin

Probably the comment there is woefully inadequate? - I sometimes forget that people can't read my mind :\

Nick, care to add a comment on top of zone_watermark_ok explaining the reasoning behind the calculation and its expected effects?

That would be really nice.

The original code didnt had the can_try_harder/gfp_high decrease which is now on zone_watermark_ok.

Means that those allocations will now be successful earlier, instead of going to the next zonelist iteration. kswapd will not be awake when it used to be.

Hopefully it doesnt matter that much. You did this by intention?

Quoted 7 lines · Marcelo Tosatti

The original code didnt had the can_try_harder/gfp_high decrease which is now on zone_watermark_ok.

Means that those allocations will now be successful earlier, instead of going to the next zonelist iteration. kswapd will not be awake when it used to be.

Hopefully it doesnt matter that much. You did this by intention?

Another thing Nick is that now balance_pgdat uses zone_watermark_ok, and that sums "z->protection[alloc_type]".

        if (free_pages <= min + z->protection[alloc_type])
                return 0;

Since balance_pgdat calls with alloc_type=0, the code will sum ZONE_DMA (alloc_type = 0) protection, and it should not.

kswapd should be working on the bare min/low/high watermarks AFAICT, without the protections.

Comments?

Quoted 22 lines · Marcelo Tosatti

Quoted 8 lines · Marcelo Tosatti

The original code didnt had the can_try_harder/gfp_high decrease which is now on zone_watermark_ok.

Means that those allocations will now be successful earlier, instead of going to the next zonelist iteration. kswapd will not be awake when it used to be.

Hopefully it doesnt matter that much. You did this by intention?

Another thing Nick is that now balance_pgdat uses zone_watermark_ok, and that sums "z->protection[alloc_type]".

       if (free_pages <= min + z->protection[alloc_type])
               return 0;

Since balance_pgdat calls with alloc_type=0, the code will sum ZONE_DMA (alloc_type = 0) protection, and it should not.

Quoted 6 lines

kswapd should be working on the bare min/low/high watermarks AFAICT, without the protections.

Comments?

Yeah.. I think z->protection[0] should always be 0, shouldn't it?

I was just hesitant to add another parameter to the function and have yet another case to check.