Linear reclaim V1

PATCH In review Andy Whitcroft 4 participants 13 messages Sep 8, 2006 – Sep 11, 2006

Subsystems (7)

Memory management VFS MM core Page allocator +3 more subsystems

lore

Share & tools

lore

Andy Whitcroft

author

2006-09-08 12:24 UTC #0 lore raw

cover Linear reclaim V1

Linear Reclaim (V1)

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 linear reclaim algorithm to the allocator. It targets groups of pages at the specified order rather than in lru order. Passing over each area at this size and assessing the likelyhood of reclaiming all of the pages within. If chances are high, we apply reclaim to all of the busy pages in this area in the hopes of consolidating a complete page at that order. This is designed to be used when we are out of higher order pages.

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

As it stands we introduce a complete second reclaim algorithm. Once this has stablised it would make sense to merge the two algorithms. Targetting variable size blocks using pages at the end of the LRU as seeds. When operating at order 0 the algorithms would then be equivalent.

-apw

Base: 2.6.18-rc5-mm1

Patches:
o linear-reclaim-add-order-to-reclaim-path
o linear-reclaim-export-page_order-and-family
o linear-reclaim-pull-out-unfreeable-page-return
o linear-reclaim-add-pfn_valid_within-for-zone-holes
o linear-reclaim-core

Current version: V1

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

Andy Whitcroft

author

2006-09-08 12:25 UTC #1 lore raw

PATCH 1/5 linear reclaim add order to reclaim path

linear reclaim add order to reclaim path

In order to select an appropriate reclaim algorithm we need to know the order of the original failure. Pass the order down in the reclaim path.

Added in: V1

Signed-off-by Andy Whitcroft <[email protected]>

---

fs/buffer.c +1 -1

index 1e0d740..bc2e7ef 100644
@@ -371,7 +371,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);
 	}
 }

include/linux/swap.h +1 -1

index 051d1c5..27b963f 100644
@@ -187,7 +187,7 @@ extern int rotate_reclaimable_page(struc
 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 **, int, gfp_t);
 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);

mm/page_alloc.c +1 -1

index ea38560..dc41137 100644
@@ -1132,7 +1132,7 @@ rebalance:
 	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;

mm/vmscan.c +1 -1

index bad9c05..afa7c03 100644
@@ -978,7 +978,7 @@ static unsigned long shrink_zones(int pr
  * holds filesystem locks which prevent writeout this might not work, and the
  * allocation attempt will fail.
  */
-unsigned long try_to_free_pages(struct zone **zones, gfp_t gfp_mask)
+unsigned long try_to_free_pages(struct zone **zones, int order, gfp_t gfp_mask)
 {
 	int priority;
 	int ret = 0;

Andy Whitcroft

author

2006-09-08 12:25 UTC #2 lore raw

PATCH 2/5 linear reclaim export page_order and family

In reply to Andy Whitcroft

linear reclaim export page_order and family

We need the free page page order in the linear reclaim algorithm. Export page_order and friends, adding a note indicating that they are only valid when a page is free and owned by the buddy allocator.

Added in: V1

Signed-off-by Andy Whitcroft <[email protected]>

---

include/linux/mm.h +27 -0

index 5b3dacf..50f0922 100644
@@ -292,6 +292,33 @@ #define VM_BUG_ON(condition) do { } whil
 #endif
 
 /*
+ * function for dealing with page's order in buddy system.
+ * zone->lock is already acquired when we use these.
+ * So, we don't need atomic page->flags operations here.
+ * NOTE: these are only valid on free pages owned by the buddy
+ * allocator.
+ */
+static inline unsigned long page_order(struct page *page)
+{
+	VM_BUG_ON(!PageBuddy(page));
+	return page_private(page);
+}
+
+static inline void set_page_order(struct page *page, int order)
+{
+	VM_BUG_ON(PageBuddy(page));
+	set_page_private(page, order);
+	__SetPageBuddy(page);
+}
+
+static inline void rmv_page_order(struct page *page)
+{
+	VM_BUG_ON(!PageBuddy(page));
+	__ClearPageBuddy(page);
+	set_page_private(page, 0);
+}
+
+/*
  * Methods to modify the page usage count.
  *
  * What counts for a page usage:

mm/page_alloc.c +0 ~~-22~~

index dc41137..825a433 100644
@@ -290,28 +290,6 @@ static inline void prep_zero_page(struct
 }
 
 /*
- * function for dealing with page's order in buddy system.
- * zone->lock is already acquired when we use these.
- * So, we don't need atomic page->flags operations here.
- */
-static inline unsigned long page_order(struct page *page)
-{
-	return page_private(page);
-}
-
-static inline void set_page_order(struct page *page, int order)
-{
-	set_page_private(page, order);
-	__SetPageBuddy(page);
-}
-
-static inline void rmv_page_order(struct page *page)
-{
-	__ClearPageBuddy(page);
-	set_page_private(page, 0);
-}
-
-/*
  * Locate the struct page for both the matching buddy in our
  * pair (buddy1) and the combined O(n+1) page they form (page).
  *

Andy Whitcroft

author

2006-09-08 12:26 UTC #3 lore raw

PATCH 3/5 linear reclaim pull out unfreeable page return

In reply to Andy Whitcroft

linear reclaim pull out unfreeable page return

Both lru reclaim and linear reclaim need to return unused pages. Pull out unfreeable page return code for later use by linear reclaim.

Added in: V1

Signed-off-by Andy Whitcroft <[email protected]>

---

mm/vmscan.c +28 ~~-19~~

index afa7c03..4a72976 100644
@@ -632,6 +632,32 @@ static unsigned long isolate_lru_pages(u
 }
 
 /*
+ * Put back any unfreeable pages, returning them to the appropriate
+ * lru list.
+ */
+static void return_unfreeable_pages(struct list_head *page_list,
+				struct zone *zone, struct pagevec *pvec)
+{
+	struct page *page;
+
+	while (!list_empty(page_list)) {
+		page = lru_to_page(page_list);
+		VM_BUG_ON(PageLRU(page));
+		SetPageLRU(page);
+		list_del(&page->lru);
+		if (PageActive(page))
+			add_page_to_active_list(zone, page);
+		else
+			add_page_to_inactive_list(zone, page);
+		if (!pagevec_add(pvec, page)) {
+			spin_unlock_irq(&zone->lru_lock);
+			__pagevec_release(pvec);
+			spin_lock_irq(&zone->lru_lock);
+		}
+	}
+}
+
+/*
  * shrink_inactive_list() is a helper for shrink_zone().  It returns the number
  * of reclaimed pages
  */

@@ -648,7 +674,6 @@ static unsigned long shrink_inactive_lis
 	lru_add_drain();
 	spin_lock_irq(&zone->lru_lock);
 	do {
-		struct page *page;
 		unsigned long nr_taken;
 		unsigned long nr_scan;
 		unsigned long nr_freed;

@@ -676,24 +701,8 @@ static unsigned long shrink_inactive_lis
 			goto done;
 
 		spin_lock(&zone->lru_lock);
-		/*
-		 * Put back any unfreeable pages.
-		 */
-		while (!list_empty(&page_list)) {
-			page = lru_to_page(&page_list);
-			VM_BUG_ON(PageLRU(page));
-			SetPageLRU(page);
-			list_del(&page->lru);
-			if (PageActive(page))
-				add_page_to_active_list(zone, page);
-			else
-				add_page_to_inactive_list(zone, page);
-			if (!pagevec_add(&pvec, page)) {
-				spin_unlock_irq(&zone->lru_lock);
-				__pagevec_release(&pvec);
-				spin_lock_irq(&zone->lru_lock);
-			}
-		}
+
+		return_unfreeable_pages(&page_list, zone, &pvec);
   	} while (nr_scanned < max_scan);
 	spin_unlock(&zone->lru_lock);
 done:

Andy Whitcroft

author

2006-09-08 12:26 UTC #4 lore raw

PATCH 4/5 linear reclaim add pfn_valid_within for zone holes

In reply to Andy Whitcroft

linear reclaim add pfn_valid_within for zone holes

Generally we work under the assumption that memory the mem_map array is contigious and valid out to MAX_ORDER blocks. When this is not true we much check each and every reference we make from a pfn. Add a pfn_valid_within() which should be used when checking pages within a block when we have already checked the validility of the block normally. This can then be optimised away when we have holes.

Added in: V1

Signed-off-by Andy Whitcroft <[email protected]>

---

include/linux/mmzone.h +12 -0

index 3d31354..8c09638 100644
@@ -680,6 +680,18 @@ #endif
 void memory_present(int nid, unsigned long start, unsigned long end);
 unsigned long __init node_memmap_size_bytes(int, unsigned long, unsigned long);
 
+/*
+ * If we have holes within zones (smaller than MAX_ORDER) then we need
+ * to check pfn validility within MAX_ORDER blocks.  pfn_valid_within
+ * should be used in this case; we optimise this away when we have
+ * no holes.
+ */
+#ifdef CONFIG_HOLES_IN_ZONE
+#define pfn_valid_within(pfn) pfn_valid(pfn)
+#else
+#define pfn_valid_within(pfn) (1)
+#endif
+
 #endif /* !__ASSEMBLY__ */
 #endif /* __KERNEL__ */
 #endif /* _LINUX_MMZONE_H */

Andy Whitcroft

author

2006-09-08 12:27 UTC #5 lore raw

PATCH 5/5 linear reclaim core

In reply to Andy Whitcroft

linear reclaim core

This patch introduces an alternative algorithm used when requesting higher order allocations. Here we look at memory in ranges at the order requested. We make a quick pass to see if all pages in that area are likely to be reclaimed, only then do we apply reclaim to the pages in the area.

Testing in combination with fragmentation avoidance shows significantly improved chances of a successful allocation at higher order.

Added in: V1

Issues:
o no longer need to be MAX_ORDER aligned with new iterators

Signed-off-by Andy Whitcroft <[email protected]>

---

include/linux/mmzone.h +1 -0

index 8c09638..83cafb9 100644
@@ -199,6 +199,7 @@ #endif
 	unsigned long		nr_inactive;
 	unsigned long		pages_scanned;	   /* since last reclaim */
 	int			all_unreclaimable; /* All pages pinned */
+	unsigned long		linear_scan_hand;
 
 	/* The accumulated number of activities that may cause page aging,
 	 * that is, make some pages closer to the tail of inactive_list.

mm/page_alloc.c +1 -0

index 825a433..9c71a2d 100644
@@ -2049,6 +2049,7 @@ __meminit int init_currently_empty_zone(
 	pgdat->nr_zones = zone_idx(zone) + 1;
 
 	zone->zone_start_pfn = zone_start_pfn;
+	zone->linear_scan_hand = zone_start_pfn;
 
 	memmap_init(size, pgdat->node_id, zone_idx(zone), zone_start_pfn);

mm/vmscan.c +299 -1

315 lines not on this page · raw message

Andrew Morton

2006-09-08 18:41 UTC #6 lore raw

Re: [PATCH 5/5] linear reclaim core

Quoted 12 lines · On Fri, 8 Sep 2006 13:27:18 +0100 Andy Whitcroft <[email protected]> wrote:

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 introduces an alternative algorithm used when requesting higher order allocations. Here we look at memory in ranges at the order requested. We make a quick pass to see if all pages in that area are likely to be reclaimed, only then do we apply reclaim to the pages in the area.

Quoted 3 lines

Testing in combination with fragmentation avoidance shows significantly improved chances of a successful allocation at higher order.

I bet it does.

I'm somewhat surprised at the implementation. Would it not be sufficient to do this within shrink_inactive_list()? Something along the lines of:

- Pick tail page off LRU.

- For all "neighbour" pages (alignment == 1<<order, count == 1<<order)

- If they're all PageLRU and !PageActive, add them all to page_list for possible reclaim

And, in shrink_active_list:

- Pick tail page off LRU

- For all "neighbour" pages (alignment == 1<<order, count == 1<<order)

If they're all PageLRU, put all the active pages in this block onto l_hold for possible deactivation.

Maybe all that can be done in isolate_lru_pages().

Andy Whitcroft

author

2006-09-10 02:23 UTC #7 lore raw

Re: [PATCH 5/5] linear reclaim core

Quoted 35 lines · Andrew Morton

Quoted 12 lines · On Fri, 8 Sep 2006 13:27:18 +0100 Andy Whitcroft <[email protected]> wrote:
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 introduces an alternative algorithm used when requesting higher order allocations. Here we look at memory in ranges at the order requested. We make a quick pass to see if all pages in that area are likely to be reclaimed, only then do we apply reclaim to the pages in the area.
Quoted 3 lines
Testing in combination with fragmentation avoidance shows significantly improved chances of a successful allocation at higher order.
I bet it does.
I'm somewhat surprised at the implementation. Would it not be sufficient to do this within shrink_inactive_list()? Something along the lines of:
- Pick tail page off LRU.
- For all "neighbour" pages (alignment == 1<<order, count == 1<<order)
- If they're all PageLRU and !PageActive, add them all to page_list for possible reclaim
And, in shrink_active_list:
- Pick tail page off LRU

Quoted 7 lines

- For all "neighbour" pages (alignment == 1<<order, count == 1<<order)
If they're all PageLRU, put all the active pages in this block onto l_hold for possible deactivation.
Maybe all that can be done in isolate_lru_pages().

When we started out down this road we though we needed to scan linearly too due to the buddy marking scheme. Now that we're at this end of the road we know thats pretty easy to fix, we're already considering merging the two reclaims anyhow.

Probabally this would do something pretty similar. It feels at a quick glance as it its going to have slightly different semantics, but that may be better or worse.

I'll go try it out and see how it looks.

Thanks for reading.

-apw

Peter Zijlstra

2006-09-10 09:51 UTC #8 lore raw

Re: [PATCH 5/5] linear reclaim core

In reply to Andrew Morton

Quoted 11 lines · Andrew Morton

- Pick tail page off LRU.
- For all "neighbour" pages (alignment == 1<<order, count == 1<<order)
- If they're all PageLRU and !PageActive, add them all to page_list for possible reclaim
And, in shrink_active_list:
- Pick tail page off LRU

Quoted 7 lines

- For all "neighbour" pages (alignment == 1<<order, count == 1<<order)
If they're all PageLRU, put all the active pages in this block onto l_hold for possible deactivation.
Maybe all that can be done in isolate_lru_pages().

Signed-off-by Peter Zijlstra <[email protected]>

---
 fs/buffer.c          |    2 -
 include/linux/swap.h |    2 -
 mm/page_alloc.c      |    2 -
 mm/vmscan.c          |   70 ++++++++++++++++++++++++++++++++++++---------------
 4 files changed, 53 insertions(+), 23 deletions(-)

mm/vmscan.c +50 ~~-20~~

Index: linux-2.6/mm/vmscan.c
===================================================================
@@ -62,6 +62,8 @@ struct scan_control {
 	int swap_cluster_max;
 
 	int swappiness;
+
+	int order;
 };
 
 /*

@@ -590,35 +592,62 @@ keep:
  *
  * returns how many pages were moved onto *@dst.
  */
+int __isolate_lru_page(struct page *page, int active)
+{
+	int ret = -EINVAL;
+
+	if (PageLRU(page) && (PageActive(page) == active)) {
+		ret = -EBUSY;
+		if (likely(get_page_unless_zero(page))) {
+			/*
+			 * Be careful not to clear PageLRU until after we're
+			 * sure the page is not being freed elsewhere -- the
+			 * page release code relies on it.
+			 */
+			ClearPageLRU(page);
+			ret = 0;
+		}
+	}
+
+	return ret;
+}
+
 static unsigned long isolate_lru_pages(unsigned long nr_to_scan,
 		struct list_head *src, struct list_head *dst,
-		unsigned long *scanned)
+		unsigned long *scanned, int order)
 {
 	unsigned long nr_taken = 0;
 	struct page *page;
-	unsigned long scan;
+	unsigned long scan, pfn, base_pfn;
+	int active;
 
-	for (scan = 0; scan < nr_to_scan && !list_empty(src); scan++) {
-		struct list_head *target;
+	for (scan = 0; scan < nr_to_scan && !list_empty(src);) {
 		page = lru_to_page(src);
 		prefetchw_prev_lru_page(page, src, flags);
 
 		BUG_ON(!PageLRU(page));
 
-		list_del(&page->lru);
-		target = src;
-		if (likely(get_page_unless_zero(page))) {
-			/*
-			 * Be careful not to clear PageLRU until after we're
-			 * sure the page is not being freed elsewhere -- the
-			 * page release code relies on it.
-			 */
-			ClearPageLRU(page);
-			target = dst;
+		active = PageActive(page);
+		pfn = page_to_pfn(page);
+		base_pfn = pfn &= ~((1 << order) - 1);
+		for (; pfn < (base_pfn + (1 << order)) && pfn_valid(pfn); pfn++) {
+			struct page *tmp = pfn_to_page(pfn);
+			int ret;
+
+			BUG_ON(!tmp);
+
+			ret = __isolate_lru_page(tmp, active);
+			scan++;
+			if (ret) {
+				if (ret == -EBUSY) {
+					/* else it is being freed elsewhere */
+					list_move(&tmp->lru, src);
+				}
+				break;
+			} else
+				list_move(&tmp->lru, dst);
 			nr_taken++;
-		} /* else it is being freed elsewhere */
-
-		list_add(&page->lru, target);
+		}
 	}
 
 	*scanned = scan;

@@ -649,7 +678,7 @@ static unsigned long shrink_inactive_lis
 
 		nr_taken = isolate_lru_pages(sc->swap_cluster_max,
 					     &zone->inactive_list,
-					     &page_list, &nr_scan);
+					     &page_list, &nr_scan, sc->order);
 		zone->nr_inactive -= nr_taken;
 		zone->pages_scanned += nr_scan;
 		spin_unlock_irq(&zone->lru_lock);

@@ -771,7 +800,7 @@ static void shrink_active_list(unsigned 
 	lru_add_drain();
 	spin_lock_irq(&zone->lru_lock);
 	pgmoved = isolate_lru_pages(nr_pages, &zone->active_list,
-				    &l_hold, &pgscanned);
+				    &l_hold, &pgscanned, sc->order);
 	zone->pages_scanned += pgscanned;
 	zone->nr_active -= pgmoved;
 	spin_unlock_irq(&zone->lru_lock);

@@ -959,7 +988,7 @@ static unsigned long shrink_zones(int pr
  * holds filesystem locks which prevent writeout this might not work, and the
  * allocation attempt will fail.
  */
-unsigned long try_to_free_pages(struct zone **zones, gfp_t gfp_mask)
+unsigned long try_to_free_pages(struct zone **zones, int order, gfp_t gfp_mask)
 {
 	int priority;
 	int ret = 0;

@@ -974,6 +1003,7 @@ unsigned long try_to_free_pages(struct z
 		.swap_cluster_max = SWAP_CLUSTER_MAX,
 		.may_swap = 1,
 		.swappiness = vm_swappiness,
+		.order = order,
 	};
 
 	count_vm_event(ALLOCSTALL);

fs/buffer.c +1 -1

Index: linux-2.6/fs/buffer.c
===================================================================
@@ -498,7 +498,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);
 	}
 }

include/linux/swap.h +1 -1

Index: linux-2.6/include/linux/swap.h
===================================================================
@@ -181,7 +181,7 @@ extern int rotate_reclaimable_page(struc
 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 **, int, gfp_t);
 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);

mm/page_alloc.c +1 -1

Index: linux-2.6/mm/page_alloc.c
===================================================================
@@ -1000,7 +1000,7 @@ rebalance:
 	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;

Peter Zijlstra

2006-09-10 17:09 UTC #9 lore raw

PATCH 1/1 lumpy reclaim -v2

Hi,

I found a live-lock in my previous version. Unfortunatly this one is a bit longer.

The live lock would occur if we break out of the order loop before moving the tail page ahead, this would lead to retrying the same order block again and again.

This version first handles the tail page, and after that tries to complete the block.

---

When trying to reclaim pages for a higher order allocation, make reclaim try to move lumps of pages (fitting the requested order) about, instead of single pages. This should significantly reduce the number of reclaimed pages for higher order allocations.

Signed-off-by Peter Zijlstra <[email protected]>

---
 fs/buffer.c          |    2 -
 include/linux/swap.h |    2 -
 mm/page_alloc.c      |    2 -
 mm/vmscan.c          |   94 ++++++++++++++++++++++++++++++++++++++++-----------
 4 files changed, 77 insertions(+), 23 deletions(-)

mm/vmscan.c +74 ~~-20~~

Index: linux-2.6/mm/vmscan.c
===================================================================
@@ -62,6 +62,8 @@ struct scan_control {
 	int swap_cluster_max;
 
 	int swappiness;
+
+	int order;
 };
 
 /*

@@ -590,35 +592,86 @@ keep:
  *
  * returns how many pages were moved onto *@dst.
  */
+int __isolate_lru_page(struct page *page, int active)
+{
+	int ret = -EINVAL;
+
+	if (PageLRU(page) && (PageActive(page) == active)) {
+		ret = -EBUSY;
+		if (likely(get_page_unless_zero(page))) {
+			/*
+			 * Be careful not to clear PageLRU until after we're
+			 * sure the page is not being freed elsewhere -- the
+			 * page release code relies on it.
+			 */
+			ClearPageLRU(page);
+			ret = 0;
+		}
+	}
+
+	return ret;
+}
+
 static unsigned long isolate_lru_pages(unsigned long nr_to_scan,
 		struct list_head *src, struct list_head *dst,
-		unsigned long *scanned)
+		unsigned long *scanned, int order)
 {
 	unsigned long nr_taken = 0;
-	struct page *page;
-	unsigned long scan;
+	struct page *page, *tmp;
+	unsigned long scan, pfn, end_pfn, page_pfn;
+	int active;
 
 	for (scan = 0; scan < nr_to_scan && !list_empty(src); scan++) {
-		struct list_head *target;
 		page = lru_to_page(src);
 		prefetchw_prev_lru_page(page, src, flags);
 
 		BUG_ON(!PageLRU(page));
 
-		list_del(&page->lru);
-		target = src;
-		if (likely(get_page_unless_zero(page))) {
-			/*
-			 * Be careful not to clear PageLRU until after we're
-			 * sure the page is not being freed elsewhere -- the
-			 * page release code relies on it.
-			 */
-			ClearPageLRU(page);
-			target = dst;
-			nr_taken++;
-		} /* else it is being freed elsewhere */
+		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 */
+				list_move(&page->lru, src);
+				continue;
+
+			default:
+				BUG();
+		}
 
-		list_add(&page->lru, target);
+		if (!order)
+			continue;
+
+		page_pfn = pfn = __page_to_pfn(page);
+		end_pfn = pfn &= ~((1 << order) - 1);
+		end_pfn += 1 << order;
+		for (; pfn < end_pfn; pfn++) {
+			if (unlikely(pfn == page_pfn))
+				continue;
+			if (unlikely(!pfn_valid(pfn)))
+				break;
+
+			scan++;
+			tmp = __pfn_to_page(pfn);
+			switch (__isolate_lru_page(tmp, active)) {
+				case 0:
+					list_move(&tmp->lru, dst);
+					nr_taken++;
+					continue;
+
+				case -EBUSY:
+					/* else it is being freed elsewhere */
+					list_move(&tmp->lru, src);
+				default:
+					break;
+
+			}
+			break;
+		}
 	}
 
 	*scanned = scan;

@@ -649,7 +702,7 @@ static unsigned long shrink_inactive_lis
 
 		nr_taken = isolate_lru_pages(sc->swap_cluster_max,
 					     &zone->inactive_list,
-					     &page_list, &nr_scan);
+					     &page_list, &nr_scan, sc->order);
 		zone->nr_inactive -= nr_taken;
 		zone->pages_scanned += nr_scan;
 		spin_unlock_irq(&zone->lru_lock);

@@ -771,7 +824,7 @@ static void shrink_active_list(unsigned 
 	lru_add_drain();
 	spin_lock_irq(&zone->lru_lock);
 	pgmoved = isolate_lru_pages(nr_pages, &zone->active_list,
-				    &l_hold, &pgscanned);
+				    &l_hold, &pgscanned, sc->order);
 	zone->pages_scanned += pgscanned;
 	zone->nr_active -= pgmoved;
 	spin_unlock_irq(&zone->lru_lock);

@@ -959,7 +1012,7 @@ static unsigned long shrink_zones(int pr
  * holds filesystem locks which prevent writeout this might not work, and the
  * allocation attempt will fail.
  */
-unsigned long try_to_free_pages(struct zone **zones, gfp_t gfp_mask)
+unsigned long try_to_free_pages(struct zone **zones, int order, gfp_t gfp_mask)
 {
 	int priority;
 	int ret = 0;

@@ -974,6 +1027,7 @@ unsigned long try_to_free_pages(struct z
 		.swap_cluster_max = SWAP_CLUSTER_MAX,
 		.may_swap = 1,
 		.swappiness = vm_swappiness,
+		.order = order,
 	};
 
 	count_vm_event(ALLOCSTALL);

fs/buffer.c +1 -1

Index: linux-2.6/fs/buffer.c
===================================================================
@@ -498,7 +498,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);
 	}
 }

include/linux/swap.h +1 -1

Index: linux-2.6/include/linux/swap.h
===================================================================
@@ -181,7 +181,7 @@ extern int rotate_reclaimable_page(struc
 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 **, int, gfp_t);
 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);

mm/page_alloc.c +1 -1

Index: linux-2.6/mm/page_alloc.c
===================================================================
@@ -1000,7 +1000,7 @@ rebalance:
 	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;

Jörn Engel

2006-09-10 23:45 UTC #10 lore raw

Re: [PATCH 5/5] linear reclaim core

In reply to Andrew Morton

Quoted 11 lines · Andrew Morton

I'm somewhat surprised at the implementation. Would it not be sufficient to do this within shrink_inactive_list()? Something along the lines of:
- Pick tail page off LRU.
- For all "neighbour" pages (alignment == 1<<order, count == 1<<order)
- If they're all PageLRU and !PageActive, add them all to page_list for possible reclaim

Quoted 8 lines

And, in shrink_active_list:
- Pick tail page off LRU
- For all "neighbour" pages (alignment == 1<<order, count == 1<<order)
If they're all PageLRU, put all the active pages in this block onto l_hold for possible deactivation.

Hmm. Trying to shoot holes into your approach, I find two potential problems:
A) With sufficient fragmentation, all inactive pages have one active neighbour, so shrink_inactive_list() will never find a cluster of the required order.
B) With some likelihood, shrink_active_list() will pick neighbours which happen to be rather hot pages. They get freed, only to get paged in again within little more than rotational latency.

How about something like:
1. Free 1<<order pages from the inactive list.
2. Pick a page cluster of requested order.
3. Move all pages from the cluster to the just freed pages.

[ Disclaimer: I just started dabbling in mm after Andi Kleen's presentation on Linux Kongress on friday. My tiny gem of knowledge, if present at all, might be well hidden in the ignorance of an mm-newbie. ]

Jorn

Signature · 8 lines

It's not whether you win or lose, it's how you place the blame.
-- unknown

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

Andrew Morton

2006-09-11 00:40 UTC #11 lore raw

Re: [PATCH 5/5] linear reclaim core

Quoted 18 lines · On Mon, 11 Sep 2006 01:45:09 +0200 Jorn Engel <[email protected]>…

Quoted 17 lines · Andrew Morton
I'm somewhat surprised at the implementation. Would it not be sufficient to do this within shrink_inactive_list()? Something along the lines of:
- Pick tail page off LRU.
- For all "neighbour" pages (alignment == 1<<order, count == 1<<order)
- If they're all PageLRU and !PageActive, add them all to page_list for possible reclaim
And, in shrink_active_list:
- Pick tail page off LRU
- For all "neighbour" pages (alignment == 1<<order, count == 1<<order)

Quoted 8 lines

Quoted 2 lines
If they're all PageLRU, put all the active pages in this block onto l_hold for possible deactivation.
Hmm. Trying to shoot holes into your approach, I find two potential problems:
A) With sufficient fragmentation, all inactive pages have one active neighbour, so shrink_inactive_list() will never find a cluster of the required order.

Nope. If the clump of pages has a mix of active and inactive, the above design would cause the active ones to be deactivated, so now the entire clump is eligible for treatment by shrink_inactive_list().

Quoted 3 lines

B) With some likelihood, shrink_active_list() will pick neighbours which happen to be rather hot pages. They get freed, only to get paged in again within little more than rotational latency.

Maybe. Careful benchmarking and carefully-designed microbenchmarks are, as always, needed.

Bear in mind that simply moving the pages to the inactive list isn't enough to get them reclaimed: we still do various forms of page aging and the pages can still be preserved due to that. IOW, we have several different forms of page aging, one of which is LRU-ordering. The above design compromises just one of those aging steps.

I'd be more concerned about higher-order atomic allocations. If this thing is to work I suspect we'll need per-zone, per-order watermarks and kswapd will need to maintain those.

Quoted 4 lines

How about something like:
1. Free 1<<order pages from the inactive list.
2. Pick a page cluster of requested order.
3. Move all pages from the cluster to the just freed pages.

Don't think in terms of "freeing". Think in terms of "scanning". A lot of page reclaim's balancing tricks are cast in terms of pages-scanned, slabs-scanned, etc.

Jörn Engel

2006-09-11 07:33 UTC #12 lore raw

Re: [PATCH 5/5] linear reclaim core

Quoted 8 lines · Andrew Morton

Quoted 4 lines
A) With sufficient fragmentation, all inactive pages have one active neighbour, so shrink_inactive_list() will never find a cluster of the required order.
Nope. If the clump of pages has a mix of active and inactive, the above design would cause the active ones to be deactivated, so now the entire clump is eligible for treatment by shrink_inactive_list().

Ok? More reading seems necessary before I can follow you here...

Quoted 5 lines

Bear in mind that simply moving the pages to the inactive list isn't enough to get them reclaimed: we still do various forms of page aging and the pages can still be preserved due to that. IOW, we have several different forms of page aging, one of which is LRU-ordering. The above design compromises just one of those aging steps.

Are these different forms of page aging described in written form somewhere?

Quoted 3 lines

I'd be more concerned about higher-order atomic allocations. If this thing is to work I suspect we'll need per-zone, per-order watermarks and kswapd will need to maintain those.

Or simply declare higher-order atomic allocations to be undesired? Not sure how many of those we have that make sense.

Quoted 3 lines

Don't think in terms of "freeing". Think in terms of "scanning". A lot of page reclaim's balancing tricks are cast in terms of pages-scanned, slabs-scanned, etc.

There is a related problem I'm sure you are aware of. Trying to shrink the dentry_cache or the various foofs_inode_caches we remove tons of objects before a full slab (in most cases a page) is free and can be returned. ext3_inode_cache has 8 objects per slab, dentry_cache has 29. That's the equivalent of an order-3 or order-5 page allocation in terms of inefficiency.

And having just started thinking about the problem, my envisioned solution looks fairly similar to Andy's work for high-order allocations here. Except that I cannot think in terms of "scanning", afaict.

Jorn

Signature · 8 lines

Anything that can go wrong, will.
-- Finagle's Law

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