Skip to contentSkip to conversation

Lumpy Reclaim V5

PATCH In review Andy Whitcroft 3 participants 8 messages Mar 12, 2007 – Mar 17, 2007

Subsystems (6)
Memory management VFS Page allocator MGLRU +2 more subsystems
lore
Share & tools
lore

Andy Whitcroft

author
#0 lore raw

cover Lumpy Reclaim V5

Following this email are three patches which represent the current state of the lumpy reclaim patches; collectively lumpy V5. This patch kit is against 2.6.21-rc3-mm2. This stack is split out to show the incremental changes in this version. This contains one fixup following on from Christoph Lameters feedback and one change affecting scan rates. Andrew, please consider for -mm.

Comparitive testing between lumpy-V4 and lump-V5 generally shows a small improvement, coming from the slight increase in scanning coming from second of the patches.

I have taken the lumpy-V3 patches and the last batch of changes and folded them back into a single patch (collectively lumpy-V4), updating attribution. On top of this are are two patches the first the result of feedback from Christoph and the latter a change which I believe is a correctness issue for scanning rates:

lumpy-reclaim-V4: folded back base, changes incorporated are listed
in the changelog which is included in the patch.

lumpy-back-out-removal-of-active-check-in-isolate_lru_pages:
reinstating a BUG where the active state missmatched the lru we are scanning. As pointed out by Christoph Lameter, there should not be a missmatch and testing confirms with this base there are none.

lumpy-only-count-taken-pages-as-scanned: when scanning an area
around a target page taken from the LRU we will only take pages which match the active state. Previously we would count the missmatching pages passed over as 'scanned'. Prior to lumpy a page was only counted as 'scanned' if we had removed it from the LRU and reclaimed or rotated it back to the list. This leads to reduced reclaim scanning and affects reclaim performance. Move to counting pages as scanned only when actually touched.

Against: 2.6.21-rc3-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>

author
#1 lore raw

PATCH 1/3 Lumpy Reclaim V4

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 at order-0 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. Credit to Mel Gorman for sanitity checking.

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

Signed-off-by Andy Whitcroft <[email protected]>
Acked-by Peter Zijlstra <[email protected]>
Acked-by Mel Gorman <[email protected]>
Signed-off-by Andrew Morton <[email protected]>

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

fs/buffer.c +1 -1
index 8666f62..a9273ab 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 +2 -1
index a461480..5b9ee5a 100644
@@ -189,7 +189,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);
mm/page_alloc.c +1 -1
index 6abe947..23917f8 100644
@@ -1694,7 +1694,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;
mm/vmscan.c +107 -19

185 lines not on this page · raw message

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

#2 lore raw

Re: [PATCH 1/3] Lumpy Reclaim V4

mm/vmscan.c keep: · line 726

Quoted 9 lines · Andy Whitcroft
mm/vmscan.c +8 -0
+                       /* 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

Would having something like:

        static inline int pfn_in_zone_hole(unsigned long pfn)
        {
        #ifdef CONFIG_HOLES_IN_ZONE
        	if (unlikely(!pfn_valid(pfn)))
        		return 1;
        #endif 
        	return 0;
        }

help us out? page_is_buddy() and page_is_consistent() appear to do the exact same thing, with the same #ifdef.

-- Dave

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

author
#3 lore raw

Re: [PATCH 1/3] Lumpy Reclaim V4

Quoted 21 lines · Dave Hansen

mm/vmscan.c keep: · line 726

Quoted 8 lines · Andy Whitcroft
mm/vmscan.c +8 -0
+                       /* 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

Would having something like:

        static inline int pfn_in_zone_hole(unsigned long pfn)
        {
        #ifdef CONFIG_HOLES_IN_ZONE
        	if (unlikely(!pfn_valid(pfn)))
        		return 1;
        #endif 
        	return 0;
        }
Quoted 2 lines

help us out? page_is_buddy() and page_is_consistent() appear to do the exact same thing, with the same #ifdef.

Funny you mention that. I have a patch hanging around which basically does that. I'd been planning to send it up. It adds a pfn_valid_within() which you use when you already know a relative page within the MAX_ORDER block is valid. I'd not sent it cause I thought the name sucked.

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

author
#4 lore raw

PATCH 2/3 lumpy: back out removal of active check in isolate_lru_pages

In reply to Andy Whitcroft

As pointed out by Christop Lameter it should not be possible for a page to change its active/inactive state without taking the lru_lock. Reinstate this safety net.

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

---

mm/vmscan.c +5 -2
index bda63a0..d7a0860 100644
@@ -691,10 +691,13 @@ static unsigned long isolate_lru_pages(unsigned long nr_to_scan,
 			nr_taken++;
 			break;
 
-		default:
-			/* page is being freed, or is a missmatch */
+		case -EBUSY:
+			/* else it is being freed elsewhere */
 			list_move(&page->lru, src);
 			continue;
+
+		default:
+			BUG();
 		}
 
 		if (!order)

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

author
#5 lore raw

PATCH 3/3 lumpy: only count taken pages as scanned

In reply to Andy Whitcroft

When scanning the order sized area around the tag page we pull all pages of the matching active state; the non-matching pages are not otherwise affected. We currently count these as scanned increasing the apparent scan rates. Previously we would only count a page scanned if it was actually removed from the LRU, either then being reclaimed or rotated back onto the head of the LRU.

The effect of this is to cause reclaim to terminate artificially early when the scan count is reached, reducing effectivness. Move to counting only those pages we actually remove from the LRU as scanned.

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

---

mm/vmscan.c +1 -1
index d7a0860..c3dc544 100644
@@ -732,11 +732,11 @@ static unsigned long isolate_lru_pages(unsigned long nr_to_scan,
 			/* Check that we have not crossed a zone boundary. */
 			if (unlikely(page_zone_id(cursor_page) != zone_id))
 				continue;
-			scan++;
 			switch (__isolate_lru_page(cursor_page, active)) {
 			case 0:
 				list_move(&cursor_page->lru, dst);
 				nr_taken++;
+				scan++;
 				break;
 
 			case -EBUSY:

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

maintainer
#6 lore raw
In reply to Andy Whitcroft
Quoted 2 lines · On Mon, 12 Mar 2007 18:22:45 +0000 Andy Whitcroft <[email protected]> wrote:

Following this email are three patches which represent the current state of the lumpy reclaim patches; collectively lumpy V5.

So where do we stand with this now? Does it make anything get better?

I (continue to) think that if this is to be truly useful, we need some way of using it from kswapd to keep a certain minimum number of order-1, order-2, etc pages in the freelists.

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

author
#7 lore raw
Quoted 6 lines · Andrew Morton
Quoted 2 lines · On Mon, 12 Mar 2007 18:22:45 +0000 Andy Whitcroft <[email protected]> wrote:

Following this email are three patches which represent the current state of the lumpy reclaim patches; collectively lumpy V5.

So where do we stand with this now? Does it make anything get better?

I am still working to fairly compare the various combinations. One of the problems is that if you push any reclaim algorithm to its physical limits you will get the same overall success rates.

I think there is still some work to do refining lumpy, and reclaim in general. But I feel what we have now is pretty solid base for that.

Quoted 3 lines

I (continue to) think that if this is to be truly useful, we need some way of using it from kswapd to keep a certain minimum number of order-1, order-2, etc pages in the freelists.

I think this is a key component of the mix and am just starting to play with this. I hope that this can provide improvements in the instantaneous availability of these higher orders and improve average latency.

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