Lumpy Reclaim V4

Following this email are five patches which represent the current state of the lumpy reclaim patches; collectivly lumpy v4. This patch kit is designed as a complete drop-in replacement for the lumpy patches in 2.6.20-mm2. This stack is split out to show the incremental changes in this version. Andrew please replace your current lumpy stack with this one, you may prefer to fold this kit into a single patch lumpy-v4.

Comparitive testing between lumpy-v3 and lump-v4 generally shows a small improvement, coming from the improved matching of pages taken from the end of the active/inactive list (patch 2 in this series).

I have taken the lumpy-v2 patches and fixes as found in 2.6.20-rc6-mm2 and folded them back into a single patch (collectivly lumpy v3), updating attribution. On top of this are are four patches which represent the updates mainly coming from the detailed review comments from Andrew Morton:

lumpy-reclaim-v3: folded back base, lumpy-v3,

lumpy-isolate_lru_pages-wants-to-specifically-take-active-or-inactive-pages:
ensure we take pages of the expected type from the end of
the active/ inactive lists. This is both a performance and correctness fix,

lumpy-ensure-that-we-compare-PageActive-and-active-safely: ensure
comparisons between PageActive() and coded booleans are safe should PageActive() not return 1/0,

lumpy-update-commentry-on-subtle-comparisons-and-rounding-assumptions:
update the code commentary to explain the subtle exit conditions, and

lumpy-only-check-for-valid-pages-when-holes-are-present:
remove expensive check for invalid pages within MAX_ORDER blocks where those cannot exist.

Against: 2.6.20-mm2

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

When we are out of memory of a suitable size we enter reclaim. The current reclaim algorithm targets pages in LRU order, which is great for fairness but highly unsuitable if you desire pages at higher orders. To get pages of higher order we must shoot down a very high proportion of memory; >95% in a lot of cases.

This patch set adds a lumpy reclaim algorithm to the allocator. It targets groups of pages at the specified order anchored at the end of the active and inactive lists. This encourages groups of pages at the requested orders to move from active to inactive, and active to free lists. This behaviour is only triggered out of direct reclaim when higher order pages have been requested.

This patch set is particularly effective when utilised with an anti-fragmentation scheme which groups pages of similar reclaimability together.

This patch set is based on Peter Zijlstra's lumpy reclaim V2 patch which forms the foundation.

[[email protected]: ia64 pfn_to_nid fixes and loop cleanup] [[email protected]: static declarations for internal functions]

---

index 1b69d61..19d1d2c 100644
@@ -363,7 +363,7 @@ static void free_more_memory(void)
 	for_each_online_pgdat(pgdat) {
 		zones = pgdat->node_zonelists[gfp_zone(GFP_NOFS)].zones;
 		if (*zones)
-			try_to_free_pages(zones, GFP_NOFS);
+			try_to_free_pages(zones, 0, GFP_NOFS);
 	}
 }
 

index eae023a..382a30b 100644
@@ -190,7 +190,8 @@ extern int rotate_reclaimable_page(struct page *page);
 extern void swap_setup(void);
 
 /* linux/mm/vmscan.c */
-extern unsigned long try_to_free_pages(struct zone **, gfp_t);
+extern unsigned long try_to_free_pages(struct zone **zones, int order,
+					gfp_t gfp_mask);
 extern unsigned long shrink_all_memory(unsigned long nr_pages);
 extern int vm_swappiness;
 extern int remove_mapping(struct address_space *mapping, struct page *page);

index 96451c5..887e435 100644
@@ -1415,7 +1415,7 @@ nofail_alloc:
 	reclaim_state.reclaimed_slab = 0;
 	p->reclaim_state = &reclaim_state;
 
-	did_some_progress = try_to_free_pages(zonelist->zones, gfp_mask);
+	did_some_progress = try_to_free_pages(zonelist->zones, order, gfp_mask);
 
 	p->reclaim_state = NULL;
 	p->flags &= ~PF_MEMALLOC;

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

Although the PageLRU is stable as we have the zone->lru_lock we cannot take the page off the LRU unless we can take a reference to it preventing it from being released. The page release code relies on the the caller who takes the reference count to zero having exclusive access to the page to release it. To prevent a race with put_page/__page_cache_release we cannot touch the page once its count drops to zero, which occurs before the PageLRU is cleared. PageLRU being sampled outside the zone->lru_lock in that path to avoid taking the lock if not required.

This is used later in the function for comparison against all of the other pages in the 'order' sized area rooted about the target page. Its mearly an optimisation.

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

The caller of isolate_lru_pages specifically knows whether it wants to take either inactive or active pages. Currently we take the state of the LRU page at hand and use that to scan for matching pages in the order sized block. If that page is transiting we can scan for the wrong type. The caller knows what they want and should be telling us. Pass in the required active/inactive state and match against that.

Note, that now we pass the expected active state when scanning the active/inactive lists we may find missmatching target pages, pages which are in the process of changing state. This is no longer an error and we should simply ignore them.

---

index f15ffcb..b878d54 100644
@@ -663,12 +663,13 @@ static int __isolate_lru_page(struct page *page, int active)
  * @dst:	The temp list to put pages on to.
  * @scanned:	The number of pages that were scanned.
  * @order:	The caller's attempted allocation order
+ * @active:	The caller's trying to obtain active or inactive pages
  *
  * returns how many pages were moved onto *@dst.
  */
 static unsigned long isolate_lru_pages(unsigned long nr_to_scan,
 		struct list_head *src, struct list_head *dst,
-		unsigned long *scanned, int order)
+		unsigned long *scanned, int order, int active)
 {
 	unsigned long nr_taken = 0;
 	unsigned long scan;

@@ -678,7 +679,6 @@ static unsigned long isolate_lru_pages(unsigned long nr_to_scan,
 		unsigned long pfn;
 		unsigned long end_pfn;
 		unsigned long page_pfn;
-		int active;
 		int zone_id;
 
 		page = lru_to_page(src);

@@ -686,20 +686,16 @@ static unsigned long isolate_lru_pages(unsigned long nr_to_scan,
 
 		VM_BUG_ON(!PageLRU(page));
 
-		active = PageActive(page);
 		switch (__isolate_lru_page(page, active)) {
 		case 0:
 			list_move(&page->lru, dst);
 			nr_taken++;
 			break;
 
-		case -EBUSY:
-			/* else it is being freed elsewhere */
+		default:
+			/* page is being freed, or is a missmatch */
 			list_move(&page->lru, src);
 			continue;
-
-		default:
-			BUG();
 		}
 
 		if (!order)

@@ -768,8 +764,8 @@ static unsigned long shrink_inactive_list(unsigned long max_scan,
 		unsigned long nr_freed;
 
 		nr_taken = isolate_lru_pages(sc->swap_cluster_max,
-					     &zone->inactive_list,
-					     &page_list, &nr_scan, sc->order);
+				     &zone->inactive_list,
+				     &page_list, &nr_scan, sc->order, 0);
 		__mod_zone_page_state(zone, NR_INACTIVE, -nr_taken);
 		zone->pages_scanned += nr_scan;
 		zone->total_scanned += nr_scan;

@@ -916,7 +912,7 @@ force_reclaim_mapped:
 	lru_add_drain();
 	spin_lock_irq(&zone->lru_lock);
 	pgmoved = isolate_lru_pages(nr_pages, &zone->active_list,
-				    &l_hold, &pgscanned, sc->order);
+				    &l_hold, &pgscanned, sc->order, 1);
 	zone->pages_scanned += pgscanned;
 	__mod_zone_page_state(zone, NR_ACTIVE, -pgmoved);
 	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>

The page cannot be transiting since we hold the 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>

As you say it should be gated by lru_lock and we should not expect to see pages with the wrong type on the list. I would swear that I was seeing pages on the wrong list there for a bit in testing and mistakenly thought they were in transition. A quick review at least says thats false. So I'll reinstate the BUG() and retest to see if I am smoking crack or there is a bigger bug out there.

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

Now that we are passing in a boolean active flag we need to ensure that the result of PageActive(page) is comparible to that boolean.

---

index b878d54..2bfad79 100644
@@ -632,7 +632,12 @@ static int __isolate_lru_page(struct page *page, int active)
 {
 	int ret = -EINVAL;
 
-	if (PageLRU(page) && (PageActive(page) == active)) {
+	/*
+	 * When checking the active state, we need to be sure we are
+	 * dealing with comparible boolean values.  Take the logical not
+	 * of each.
+	 */
+	if (PageLRU(page) && (!PageActive(page) == !active)) {
 		ret = -EBUSY;
 		if (likely(get_page_unless_zero(page))) {
 			/*

We have a number of subtle comparisons when scanning a block, and we make use of a lot of buddy mem_map guarentees. Add commentary about each.

---

index 2bfad79..bef7e92 100644
@@ -709,7 +709,11 @@ static unsigned long isolate_lru_pages(unsigned long nr_to_scan,
 		/*
 		 * Attempt to take all pages in the order aligned region
 		 * surrounding the tag page.  Only take those pages of
-		 * the same active state as that tag page.
+		 * the same active state as that tag page.  We may safely
+		 * round the target page pfn down to the requested order
+		 * as the mem_map is guarenteed valid out to MAX_ORDER,
+		 * where that page is in a different zone we will detect
+		 * it from its zone id and abort this block scan.
 		 */
 		zone_id = page_zone_id(page);
 		page_pfn = page_to_pfn(page);

@@ -718,12 +722,15 @@ static unsigned long isolate_lru_pages(unsigned long nr_to_scan,
 		for (; pfn < end_pfn; pfn++) {
 			struct page *cursor_page;
 
+			/* The target page is in the block, ignore it. */
 			if (unlikely(pfn == page_pfn))
 				continue;
+			/* Avoid holes within the zone. */
 			if (unlikely(!pfn_valid(pfn)))
 				break;
 
 			cursor_page = pfn_to_page(pfn);
+			/* Check that we have not crossed a zone boundary. */
 			if (unlikely(page_zone_id(cursor_page) != zone_id))
 				continue;
 			scan++;

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

We only need to check that each page is valid with pfn_valid when we are on an architecture which had holes within zones. Make this check conditional.

---

index bef7e92..f249ad7 100644
@@ -725,9 +725,11 @@ static unsigned long isolate_lru_pages(unsigned long nr_to_scan,
 			/* The target page is in the block, ignore it. */
 			if (unlikely(pfn == page_pfn))
 				continue;
+#ifdef CONFIG_HOLES_IN_ZONE
 			/* Avoid holes within the zone. */
 			if (unlikely(!pfn_valid(pfn)))
 				break;
+#endif
 
 			cursor_page = pfn_to_page(pfn);
 			/* Check that we have not crossed a zone boundary. */