Lumpy Reclaim V6

Following this email are three patches to the lumpy reclaim algorithm. These apply on top of the lumpy patches in 2.6.21-rc6-mm1 (lumpy V5); making lumpy V6. The first enables kswapd to apply reclaim at the order of the allocations which trigger background reclaim. The second increases pressure on the area at the end of the inactive list. The last introduces a new symbolic constant representing the boundary between easily reclaimed areas and those where extra pressure is applicable. Andrew, please consider for -mm.

Comparitive testing between lumpy-V5 and lumpy-V6 shows a considerable improvement when under extreme load. lumpy-V5 relies on the pages in an area being rotated onto the inactive list together and remaining inactive long enough to be reclaimed from that list. Under high load a significant portion of the pages return to active or are referenced before this can occur. Lumpy-V6 targets all LRU pages in the area greatly increasing the chance of reclaiming it completely.

kswapd-use-reclaim-order-in-background-reclaim: When an allocator
has to dip below the low water mark for a zone, kswapd is awoken to start background reclaim. Make kswapd use the highest order of these allocations to define the order at which it reclaims.

lumpy-increase-pressure-at-the-end-of-the-inactive-list: when
reclaiming at higher order target all pages in the contigious area for reclaim, including active and recently referenced pages. This increases the chances of that area becoming free.

introduce-HIGH_ORDER-delineating-easily-reclaimable-orders:
The memory allocator treats lower and higher order allocations slightly differently. Lumpy reclaim also changes behaviour at this same boundary. Pull out the magic numbers and replace them with a symbolic constant.

Against: 2.6.21-rc6-mm1

-apw

Changes in lumpy V5:

Andy Whitcroft:
lumpy: back out removal of active check in isolate_lru_pages
lumpy: only count taken pages as scanned

Changes in lumpy V4:

Andy Whitcroft:
lumpy: isolate_lru_pages wants to specifically take active
or inactive pages
lumpy: ensure that we compare PageActive and active safely
lumpy: update commentry on subtle comparisons and rounding assumptions
lumpy: only check for valid pages when holes are present

Changes in lumpy V3:

Adrian Bunk:
lumpy-reclaim-cleanup

Andrew Morton:
lumpy-reclaim-v2-page_to_pfn-fix
lumpy-reclaim-v2-tidy

Andy Whitcroft:
lumpy: ensure we respect zone boundaries
lumpy: take the other active/inactive pages in the area

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

When an allocator has to dip below the low water mark for a zone, kswapd is awoken to start background reclaim. The highest order of these dipping allocations are accumulated on the zone. With this patch kswapd uses this hint to force reclaim at that order via balance_pgdat().

---

index 428da1a..466435f 100644
@@ -1212,6 +1212,7 @@ static unsigned long balance_pgdat(pg_data_t *pgdat, int order)
 		.may_swap = 1,
 		.swap_cluster_max = SWAP_CLUSTER_MAX,
 		.swappiness = vm_swappiness,
+		.order = order,
 	};
 	/*
 	 * temp_priority is used to remember the scanning priority at which

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

Having selected an area at the end of the inactive list, reclaim is attempted for all LRU pages within that contiguous area. Currently, any pages in this area found to still be active or referenced are rotated back to the active list as normal and the rest reclaimed. At low orders there is a reasonable likelyhood of finding contigious inactive areas for reclaim. However when reclaiming at higher order there is a very low chance all pages in the area being inactive, unreferenced and therefore reclaimable.

This patch modifies behaviour when reclaiming at higher order (order >= 4). All LRU pages within the target area are reclaimed, including both active and recently referenced pages.

---

index 466435f..e5e77fb 100644
@@ -472,7 +472,7 @@ static unsigned long shrink_page_list(struct list_head *page_list,
 
 		referenced = page_referenced(page, 1);
 		/* In active use or really unfreeable?  Activate it. */
-		if (referenced && page_mapping_inuse(page))
+		if (sc->order <= 3 && referenced && page_mapping_inuse(page))
 			goto activate_locked;
 
 #ifdef CONFIG_SWAP

@@ -505,7 +505,7 @@ static unsigned long shrink_page_list(struct list_head *page_list,
 		}
 
 		if (PageDirty(page)) {
-			if (referenced)
+			if (sc->order <= 3 && referenced)
 				goto keep_locked;
 			if (!may_enter_fs)
 				goto keep_locked;

@@ -599,6 +599,7 @@ keep:
  *
  * returns 0 on success, -ve errno on failure.
  */
+#define ISOLATE_BOTH -1		/* Isolate both active and inactive pages. */
 static int __isolate_lru_page(struct page *page, int active)
 {
 	int ret = -EINVAL;

@@ -608,7 +609,8 @@ static int __isolate_lru_page(struct page *page, int active)
 	 * dealing with comparible boolean values.  Take the logical not
 	 * of each.
 	 */
-	if (PageLRU(page) && (!PageActive(page) == !active)) {
+	if (PageLRU(page) && (active == ISOLATE_BOTH ||
+					(!PageActive(page) == !active))) {
 		ret = -EBUSY;
 		if (likely(get_page_unless_zero(page))) {
 			/*

@@ -729,6 +731,26 @@ static unsigned long isolate_lru_pages(unsigned long nr_to_scan,
 }
 
 /*
+ * deactivate_pages() is a helper for shrink_active_list(), it deactivates
+ * all active pages on the passed list.
+ */
+static unsigned long deactivate_pages(struct list_head *page_list)
+{
+	int nr_active = 0;
+	struct list_head *entry;
+
+	list_for_each(entry, page_list) {
+		struct page *page = list_entry(entry, struct page, lru);
+		if (PageActive(page)) {
+			ClearPageActive(page);
+			nr_active++;
+		}
+	}
+
+	return nr_active;
+}
+
+/*
  * shrink_inactive_list() is a helper for shrink_zone().  It returns the number
  * of reclaimed pages
  */

@@ -749,11 +771,17 @@ static unsigned long shrink_inactive_list(unsigned long max_scan,
 		unsigned long nr_taken;
 		unsigned long nr_scan;
 		unsigned long nr_freed;
+		unsigned long nr_active;
 
 		nr_taken = isolate_lru_pages(sc->swap_cluster_max,
 				     &zone->inactive_list,
-				     &page_list, &nr_scan, sc->order, 0);
-		__mod_zone_page_state(zone, NR_INACTIVE, -nr_taken);
+				     &page_list, &nr_scan, sc->order,
+				     (sc->order > 3)? ISOLATE_BOTH : 0);
+		nr_active = deactivate_pages(&page_list);
+
+		__mod_zone_page_state(zone, NR_ACTIVE, -nr_active);
+		__mod_zone_page_state(zone, NR_INACTIVE,
+						-(nr_taken - nr_active));
 		zone->pages_scanned += nr_scan;
 		zone->total_scanned += nr_scan;
 		spin_unlock_irq(&zone->lru_lock);

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

um, OK, I guess.

Should we use smaller values of 4 if PAGE_SIZE > 4k? I mean, users of the page allocator usually request a number of bytes, not a number of pages. Order 3 allocations on 64k pagesize will be far less common than on 4k pagesize, no?

And is there a relationship between this magic 4 and the magic 3 in __alloc_pages()? (Which has the same PAGE_SIZE problem, btw)

I must say that this is a pretty grotty-looking patch.

	if (!PageLRU(page))
		return;			/* save a tabstop! */

	if (active != ISOLATE_BOTH) {
		if (PageActive(page) && active != ISOLATE_ACTIVE)
			return;
		if (!PageActive(page) && active != ISOLATE_INACTIVE)
			return;
	}

	<isolate the page>

The memory allocator treats lower order (order <= 3) and higher order (order >= 4) allocations in slightly different ways. As lower orders are much more likely to be available and also more likely to be simply reclaimed it is deemed reasonable to wait longer for those. Lumpy reclaim also changes behaviour at this same boundary, more agressivly targetting pages in reclaim at higher order.

This patch removes all these magical numbers and replaces with with a constant HIGH_ORDER.

---

index 8c87d79..f9d2ced 100644
@@ -25,6 +25,13 @@
 #endif
 #define MAX_ORDER_NR_PAGES (1 << (MAX_ORDER - 1))
 
+/*
+ * The boundary between small and large allocations.  That is between
+ * allocation orders which should colesce naturally under reasonable
+ * reclaim pressure and those which will not.
+ */
+#define HIGH_ORDER 3
+
 #ifdef CONFIG_PAGE_GROUP_BY_MOBILITY
 #define MIGRATE_UNMOVABLE     0
 #define MIGRATE_RECLAIMABLE   1

index d7e33cb..44786d9 100644
@@ -1768,7 +1768,7 @@ nofail_alloc:
 	 */
 	do_retry = 0;
 	if (!(gfp_mask & __GFP_NORETRY)) {
-		if ((order <= 3) || (gfp_mask & __GFP_REPEAT))
+		if ((order <= HIGH_ORDER) || (gfp_mask & __GFP_REPEAT))
 			do_retry = 1;
 		if (gfp_mask & __GFP_NOFAIL)
 			do_retry = 1;

index e5e77fb..79aedcb 100644
@@ -472,7 +472,8 @@ static unsigned long shrink_page_list(struct list_head *page_list,
 
 		referenced = page_referenced(page, 1);
 		/* In active use or really unfreeable?  Activate it. */
-		if (sc->order <= 3 && referenced && page_mapping_inuse(page))
+		if (sc->order <= HIGH_ORDER &&
+					referenced && page_mapping_inuse(page))
 			goto activate_locked;
 
 #ifdef CONFIG_SWAP

@@ -505,7 +506,7 @@ static unsigned long shrink_page_list(struct list_head *page_list,
 		}
 
 		if (PageDirty(page)) {
-			if (sc->order <= 3 && referenced)
+			if (sc->order <= HIGH_ORDER && referenced)
 				goto keep_locked;
 			if (!may_enter_fs)
 				goto keep_locked;

@@ -774,9 +775,9 @@ static unsigned long shrink_inactive_list(unsigned long max_scan,
 		unsigned long nr_active;
 
 		nr_taken = isolate_lru_pages(sc->swap_cluster_max,
-				     &zone->inactive_list,
-				     &page_list, &nr_scan, sc->order,
-				     (sc->order > 3)? ISOLATE_BOTH : 0);
+			     &zone->inactive_list,
+			     &page_list, &nr_scan, sc->order,
+			     (sc->order > HIGH_ORDER)? ISOLATE_BOTH : 0);
 		nr_active = deactivate_pages(&page_list);
 
 		__mod_zone_page_state(zone, NR_ACTIVE, -nr_active);

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

oh, there we go.

It would have been better to have patched page_alloc.c independently, then to have used HIGH_ORDER in "lumpy: increase pressure at the end of the inactive list".

The name HIGH_ORDER is a bit squidgy. I'm not sure what would be better though. PAGE_ALLOC_CLUSTER_MAX?

It'd be interesting to turn this into a runtime tunable, perhaps.

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

Actually that doesn't matter, because I plan on lumping all the lumpy patches together into one lump.

I was going to duck patches #2 and #3, such was my outrage. But given that it's all lined up to be a single patch, followup cleanup patches will fit in OK. Please.

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

Yes. Its funny how you can get so close to a change that you can no longer see the obvious warts on it.

I am actually travelling today, so it'll be tommorrow now. But I'll roll the cleanups and get them to you. I can also offer you a clean drop in lumpy stack with the HIGH_ORDER change pulled out to the top once you are happy.

-apw

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