Reduce compaction scanning and lock contention

This reverts mm-compaction-check-lock-contention-first-before-taking-lock.patch as it is replaced by a later patch in the series.

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

This reverts mm-compaction-abort-compaction-loop-if-lock-is-contended-or-run-too-long-fix as it is replaced by a later patch in the series.

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

This reverts mm-compaction-abort-compaction-loop-if-lock-is-contended-or-run-too-long.patch as it is replaced by a later patch in the series.

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

From: Shaohua Li <[email protected]>

Changelog since V2
o Fix BUG_ON triggered due to pages left on cc.migratepages
o Make compact_zone_order() require non-NULL arg `contended'

Changelog since V1
o only abort the compaction if lock is contended or run too long
o Rearranged the code by Andrea Arcangeli.

isolate_migratepages_range() might isolate no pages if for example when zone->lru_lock is contended and running asynchronous compaction. In this case, we should abort compaction, otherwise, compact_zone will run a useless loop and make zone->lru_lock is even contended.

[[email protected]: Putback pages isolated for migration if aborting]

[[email protected]: compact_zone_order requires non-NULL arg contended]

Signed-off-by Andrea Arcangeli <[email protected]>

Signed-off-by Shaohua Li <[email protected]>

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

Acked-by Rik van Riel <[email protected]>

---

Changelog since V2
o Fix BUG_ON triggered due to pages left on cc.migratepages
o Make compact_zone_order() require non-NULL arg `contended'

Changelog since V1
o only abort the compaction if lock is contended or run too long
o Rearranged the code by Andrea Arcangeli.

isolate_migratepages_range() might isolate no pages if for example when zone->lru_lock is contended and running asynchronous compaction. In this case, we should abort compaction, otherwise, compact_zone will run a useless loop and make zone->lru_lock is even contended.

From: Shaohua Li <[email protected]>

Changelog since V2
o Fix BUG_ON triggered due to pages left on cc.migratepages
o Make compact_zone_order() require non-NULL arg `contended'

Changelog since V1
o only abort the compaction if lock is contended or run too long
o Rearranged the code by Andrea Arcangeli.

isolate_migratepages_range() might isolate no pages if for example when zone->lru_lock is contended and running asynchronous compaction. In this case, we should abort compaction, otherwise, compact_zone will run a useless loop and make zone->lru_lock is even contended.

[[email protected]: Putback pages isolated for migration if aborting]

[[email protected]: compact_zone_order requires non-NULL arg contended]

Signed-off-by Andrea Arcangeli <[email protected]>

Signed-off-by Shaohua Li <[email protected]>

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

Acked-by Rik van Riel <[email protected]>

Compactions migrate scanner acquires the zone->lru_lock when scanning a range of pages looking for LRU pages to acquire. It does this even if there are no LRU pages in the range. If multiple processes are compacting then this can cause severe locking contention. To make matters worse commit b2eef8c0 (mm: compaction: minimise the time IRQs are disabled while isolating pages for migration) releases the lru_lock every SWAP_CLUSTER_MAX pages that are scanned.

This patch makes two changes to how the migrate scanner acquires the LRU lock. First, it only releases the LRU lock every SWAP_CLUSTER_MAX pages if the lock is contended. This reduces the number of times it unnecessarily disables and re-enables IRQs. The second is that it defers acquiring the LRU lock for as long as possible. If there are no LRU pages or the only LRU pages are transhuge then the LRU lock will not be acquired at all which reduces contention on zone->lru_lock.

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

Acked-by Rik van Riel <[email protected]>

---

Compactions migrate scanner acquires the zone->lru_lock when scanning a range of pages looking for LRU pages to acquire. It does this even if there are no LRU pages in the range. If multiple processes are compacting then this can cause severe locking contention. To make matters worse commit b2eef8c0 (mm: compaction: minimise the time IRQs are disabled while isolating pages for migration) releases the lru_lock every SWAP_CLUSTER_MAX pages that are scanned.

This patch makes two changes to how the migrate scanner acquires the LRU lock. First, it only releases the LRU lock every SWAP_CLUSTER_MAX pages if the lock is contended. This reduces the number of times it unnecessarily disables and re-enables IRQs. The second is that it defers acquiring the LRU lock for as long as possible. If there are no LRU pages or the only LRU pages are transhuge then the LRU lock will not be acquired at all which reduces contention on zone->lru_lock.

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

Acked-by Rik van Riel <[email protected]>

---
 mm/compaction.c |   63 +++++++++++++++++++++++++++++++++++++------------------
 1 file changed, 43 insertions(+), 20 deletions(-)

mm/compaction.c +14 -20

index 6b55491..a6068ff 100644
@@ -50,6 +50,11 @@ static inline bool migrate_async_suitable(int migratetype)
 	return is_migrate_cma(migratetype) || migratetype == MIGRATE_MOVABLE;
 }
 
+static inline bool should_release_lock(spinlock_t *lock)
+{
+	return need_resched() || spin_is_contended(lock);
+}
+
 /*
  * Compaction requires the taking of some coarse locks that are potentially
  * very heavily contended. Check if the process needs to be scheduled or

@@ -62,7 +67,7 @@ static inline bool migrate_async_suitable(int migratetype)
 static bool compact_checklock_irqsave(spinlock_t *lock, unsigned long *flags,
 				      bool locked, struct compact_control *cc)
 {
-	if (need_resched() || spin_is_contended(lock)) {
+	if (should_release_lock(lock)) {
 		if (locked) {
 			spin_unlock_irqrestore(lock, *flags);
 			locked = false;

@@ -327,7 +332,7 @@ isolate_migratepages_range(struct zone *zone, struct compact_control *cc,
 	isolate_mode_t mode = 0;
 	struct lruvec *lruvec;
 	unsigned long flags;
-	bool locked;
+	bool locked = false;
 
 	/*
 	 * Ensure that there are not too many pages isolated from the LRU

@@ -347,23 +352,17 @@ isolate_migratepages_range(struct zone *zone, struct compact_control *cc,
 
 	/* Time to isolate some pages for migration */
 	cond_resched();
-	spin_lock_irqsave(&zone->lru_lock, flags);
-	locked = true;
 	for (; low_pfn < end_pfn; low_pfn++) {
 		struct page *page;
 
 		/* give a chance to irqs before checking need_resched() */
-		if (!((low_pfn+1) % SWAP_CLUSTER_MAX)) {
-			spin_unlock_irqrestore(&zone->lru_lock, flags);
-			locked = false;
+		if (locked && !((low_pfn+1) % SWAP_CLUSTER_MAX)) {
+			if (should_release_lock(&zone->lru_lock)) {
+				spin_unlock_irqrestore(&zone->lru_lock, flags);
+				locked = false;
+			}
 		}
 
-		/* Check if it is ok to still hold the lock */
-		locked = compact_checklock_irqsave(&zone->lru_lock, &flags,
-								locked, cc);
-		if (!locked || fatal_signal_pending(current))
-			break;
-
 		/*
 		 * migrate_pfn does not necessarily start aligned to a
 		 * pageblock. Ensure that pfn_valid is called when moving

@@ -403,21 +402,38 @@ isolate_migratepages_range(struct zone *zone, struct compact_control *cc,
 		pageblock_nr = low_pfn >> pageblock_order;
 		if (!cc->sync && last_pageblock_nr != pageblock_nr &&
 		    !migrate_async_suitable(get_pageblock_migratetype(page))) {
-			low_pfn += pageblock_nr_pages;
-			low_pfn = ALIGN(low_pfn, pageblock_nr_pages) - 1;
-			last_pageblock_nr = pageblock_nr;
-			continue;
+			goto next_pageblock;
 		}
 
+		/* Check may be lockless but that's ok as we recheck later */
 		if (!PageLRU(page))
 			continue;
 
 		/*
-		 * PageLRU is set, and lru_lock excludes isolation,
-		 * splitting and collapsing (collapsing has already
-		 * happened if PageLRU is set).

mm/compaction.c +21 -0

+			low_pfn += (1 << compound_order(page)) - 1;
+			continue;
+		}
+
+		/* Check if it is ok to still hold the lock */
+		locked = compact_checklock_irqsave(&zone->lru_lock, &flags,
+								locked, cc);
+		if (!locked || fatal_signal_pending(current))
+			break;
+
+		/* Recheck PageLRU and PageTransHuge under lock */
+		if (!PageLRU(page))
+			continue;
+		if (PageTransHuge(page)) {
 			low_pfn += (1 << compound_order(page)) - 1;
 			continue;
 		}

@@ -444,6 +460,13 @@ isolate_migratepages_range(struct zone *zone, struct compact_control *cc,
 			++low_pfn;
 			break;
 		}
+
+		continue;
+
+next_pageblock:
+		low_pfn += pageblock_nr_pages;
+		low_pfn = ALIGN(low_pfn, pageblock_nr_pages) - 1;
+		last_pageblock_nr = pageblock_nr;
 	}
 
 	acct_isolated(zone, locked, cc);

Signature · 7 lines

1.7.9.2

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

Hi Mel,

I have a question below.

Quoted 109 lines · Mel Gorman

Compactions migrate scanner acquires the zone->lru_lock when scanning a range of pages looking for LRU pages to acquire. It does this even if there are no LRU pages in the range. If multiple processes are compacting then this can cause severe locking contention. To make matters worse commit b2eef8c0 (mm: compaction: minimise the time IRQs are disabled while isolating pages for migration) releases the lru_lock every SWAP_CLUSTER_MAX pages that are scanned.

This patch makes two changes to how the migrate scanner acquires the LRU lock. First, it only releases the LRU lock every SWAP_CLUSTER_MAX pages if the lock is contended. This reduces the number of times it unnecessarily disables and re-enables IRQs. The second is that it defers acquiring the LRU lock for as long as possible. If there are no LRU pages or the only LRU pages are transhuge then the LRU lock will not be acquired at all which reduces contention on zone->lru_lock.

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

Acked-by Rik van Riel <[email protected]>

---
 mm/compaction.c |   63 +++++++++++++++++++++++++++++++++++++------------------
 1 file changed, 43 insertions(+), 20 deletions(-)

mm/compaction.c +19 -20

index 6b55491..a6068ff 100644
@@ -50,6 +50,11 @@ static inline bool migrate_async_suitable(int migratetype)
 	return is_migrate_cma(migratetype) || migratetype == MIGRATE_MOVABLE;
 }
 
+static inline bool should_release_lock(spinlock_t *lock)
+{
+	return need_resched() || spin_is_contended(lock);
+}
+
 /*
  * Compaction requires the taking of some coarse locks that are potentially
  * very heavily contended. Check if the process needs to be scheduled or

@@ -62,7 +67,7 @@ static inline bool migrate_async_suitable(int migratetype)
 static bool compact_checklock_irqsave(spinlock_t *lock, unsigned long *flags,
 				      bool locked, struct compact_control *cc)
 {
-	if (need_resched() || spin_is_contended(lock)) {
+	if (should_release_lock(lock)) {
 		if (locked) {
 			spin_unlock_irqrestore(lock, *flags);
 			locked = false;

@@ -327,7 +332,7 @@ isolate_migratepages_range(struct zone *zone, struct compact_control *cc,
 	isolate_mode_t mode = 0;
 	struct lruvec *lruvec;
 	unsigned long flags;
-	bool locked;
+	bool locked = false;
 
 	/*
 	 * Ensure that there are not too many pages isolated from the LRU

@@ -347,23 +352,17 @@ isolate_migratepages_range(struct zone *zone, struct compact_control *cc,
 
 	/* Time to isolate some pages for migration */
 	cond_resched();
-	spin_lock_irqsave(&zone->lru_lock, flags);
-	locked = true;
 	for (; low_pfn < end_pfn; low_pfn++) {
 		struct page *page;
 
 		/* give a chance to irqs before checking need_resched() */
-		if (!((low_pfn+1) % SWAP_CLUSTER_MAX)) {
-			spin_unlock_irqrestore(&zone->lru_lock, flags);
-			locked = false;
+		if (locked && !((low_pfn+1) % SWAP_CLUSTER_MAX)) {
+			if (should_release_lock(&zone->lru_lock)) {
+				spin_unlock_irqrestore(&zone->lru_lock, flags);
+				locked = false;
+			}
 		}
 
-		/* Check if it is ok to still hold the lock */
-		locked = compact_checklock_irqsave(&zone->lru_lock, &flags,
-								locked, cc);
-		if (!locked || fatal_signal_pending(current))
-			break;
-
 		/*
 		 * migrate_pfn does not necessarily start aligned to a
 		 * pageblock. Ensure that pfn_valid is called when moving

@@ -403,21 +402,38 @@ isolate_migratepages_range(struct zone *zone, struct compact_control *cc,
 		pageblock_nr = low_pfn >> pageblock_order;
 		if (!cc->sync && last_pageblock_nr != pageblock_nr &&
 		    !migrate_async_suitable(get_pageblock_migratetype(page))) {
-			low_pfn += pageblock_nr_pages;
-			low_pfn = ALIGN(low_pfn, pageblock_nr_pages) - 1;
-			last_pageblock_nr = pageblock_nr;
-			continue;
+			goto next_pageblock;
 		}
 
+		/* Check may be lockless but that's ok as we recheck later */
 		if (!PageLRU(page))
 			continue;
 
 		/*
-		 * PageLRU is set, and lru_lock excludes isolation,
-		 * splitting and collapsing (collapsing has already
-		 * happened if PageLRU is set).
+		 * PageLRU is set. lru_lock normally excludes isolation
+		 * splitting and collapsing (collapsing has already happened
+		 * if PageLRU is set) but the lock is not necessarily taken
+		 * here and it is wasteful to take it just to check transhuge.
+		 * Check transhuge without lock and skip if it's either a

mm/compaction.c isolate_migratepages_range(struct zone *zone, struct compact_control *cc, · line 422

Quoted 5 lines

mm/compaction.c +3 -0

+		 * transhuge or hugetlbfs page.
 		 */
 		if (PageTransHuge(page)) {
+			if (!locked)
+				goto next_pageblock;

Why skip all pages in a pageblock if !locked?
Shouldn't we add some comment?

Quoted 114 lines · Minchan Kim

Hi Mel,

I have a question below.

Quoted 109 lines · Mel Gorman

Compactions migrate scanner acquires the zone->lru_lock when scanning a range of pages looking for LRU pages to acquire. It does this even if there are no LRU pages in the range. If multiple processes are compacting then this can cause severe locking contention. To make matters worse commit b2eef8c0 (mm: compaction: minimise the time IRQs are disabled while isolating pages for migration) releases the lru_lock every SWAP_CLUSTER_MAX pages that are scanned.

This patch makes two changes to how the migrate scanner acquires the LRU lock. First, it only releases the LRU lock every SWAP_CLUSTER_MAX pages if the lock is contended. This reduces the number of times it unnecessarily disables and re-enables IRQs. The second is that it defers acquiring the LRU lock for as long as possible. If there are no LRU pages or the only LRU pages are transhuge then the LRU lock will not be acquired at all which reduces contention on zone->lru_lock.

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

Acked-by Rik van Riel <[email protected]>

---
 mm/compaction.c |   63 +++++++++++++++++++++++++++++++++++++------------------
 1 file changed, 43 insertions(+), 20 deletions(-)

mm/compaction.c +19 -20

index 6b55491..a6068ff 100644
@@ -50,6 +50,11 @@ static inline bool migrate_async_suitable(int migratetype)
 	return is_migrate_cma(migratetype) || migratetype == MIGRATE_MOVABLE;
 }
 
+static inline bool should_release_lock(spinlock_t *lock)
+{
+	return need_resched() || spin_is_contended(lock);
+}
+
 /*
  * Compaction requires the taking of some coarse locks that are potentially
  * very heavily contended. Check if the process needs to be scheduled or

@@ -62,7 +67,7 @@ static inline bool migrate_async_suitable(int migratetype)
 static bool compact_checklock_irqsave(spinlock_t *lock, unsigned long *flags,
 				      bool locked, struct compact_control *cc)
 {
-	if (need_resched() || spin_is_contended(lock)) {
+	if (should_release_lock(lock)) {
 		if (locked) {
 			spin_unlock_irqrestore(lock, *flags);
 			locked = false;

@@ -327,7 +332,7 @@ isolate_migratepages_range(struct zone *zone, struct compact_control *cc,
 	isolate_mode_t mode = 0;
 	struct lruvec *lruvec;
 	unsigned long flags;
-	bool locked;
+	bool locked = false;
 
 	/*
 	 * Ensure that there are not too many pages isolated from the LRU

@@ -347,23 +352,17 @@ isolate_migratepages_range(struct zone *zone, struct compact_control *cc,
 
 	/* Time to isolate some pages for migration */
 	cond_resched();
-	spin_lock_irqsave(&zone->lru_lock, flags);
-	locked = true;
 	for (; low_pfn < end_pfn; low_pfn++) {
 		struct page *page;
 
 		/* give a chance to irqs before checking need_resched() */
-		if (!((low_pfn+1) % SWAP_CLUSTER_MAX)) {
-			spin_unlock_irqrestore(&zone->lru_lock, flags);
-			locked = false;
+		if (locked && !((low_pfn+1) % SWAP_CLUSTER_MAX)) {
+			if (should_release_lock(&zone->lru_lock)) {
+				spin_unlock_irqrestore(&zone->lru_lock, flags);
+				locked = false;
+			}
 		}
 
-		/* Check if it is ok to still hold the lock */
-		locked = compact_checklock_irqsave(&zone->lru_lock, &flags,
-								locked, cc);
-		if (!locked || fatal_signal_pending(current))
-			break;
-
 		/*
 		 * migrate_pfn does not necessarily start aligned to a
 		 * pageblock. Ensure that pfn_valid is called when moving

@@ -403,21 +402,38 @@ isolate_migratepages_range(struct zone *zone, struct compact_control *cc,
 		pageblock_nr = low_pfn >> pageblock_order;
 		if (!cc->sync && last_pageblock_nr != pageblock_nr &&
 		    !migrate_async_suitable(get_pageblock_migratetype(page))) {
-			low_pfn += pageblock_nr_pages;
-			low_pfn = ALIGN(low_pfn, pageblock_nr_pages) - 1;
-			last_pageblock_nr = pageblock_nr;
-			continue;
+			goto next_pageblock;
 		}
 
+		/* Check may be lockless but that's ok as we recheck later */
 		if (!PageLRU(page))
 			continue;
 
 		/*
-		 * PageLRU is set, and lru_lock excludes isolation,
-		 * splitting and collapsing (collapsing has already
-		 * happened if PageLRU is set).
+		 * PageLRU is set. lru_lock normally excludes isolation
+		 * splitting and collapsing (collapsing has already happened
+		 * if PageLRU is set) but the lock is not necessarily taken
+		 * here and it is wasteful to take it just to check transhuge.
+		 * Check transhuge without lock and skip if it's either a

Quoted 9 lines

mm/compaction.c isolate_migratepages_range(struct zone *zone, struct compact_control *cc, · line 422

Quoted 5 lines

mm/compaction.c +3 -0

+		 * transhuge or hugetlbfs page.
 		 */
 		if (PageTransHuge(page)) {
+			if (!locked)
+				goto next_pageblock;

Why skip all pages in a pageblock if !locked?
Shouldn't we add some comment?

The comment is above the block already. The lru_lock normally excludes isolation and splitting. If we do not hold the hold, it's not safe to call compound_order so instead we skip the entire pageblock.

Signature · 9 lines

-- 
Mel Gorman
SUSE Labs

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

I see. To me, your saying is better than current comment. I hope comment could be more explicit.

mm/compaction.c +0 -0

index df01b4e..f1d2cc7 100644
@@ -542,8 +542,9 @@ isolate_migratepages_range(struct zone *zone, struct compact_control *cc,
                 * splitting and collapsing (collapsing has already happened

Quoted 9 lines · On Tue, 25 Sep 2012 17:13:27 +0900 Minchan Kim <[email protected]> wrote:

I see. To me, your saying is better than current comment. I hope comment could be more explicit.

mm/compaction.c +0 -0

index df01b4e..f1d2cc7 100644
@@ -542,8 +542,9 @@ isolate_migratepages_range(struct zone *zone, struct compact_control *cc,
                 * splitting and collapsing (collapsing has already happened

mm/compaction.c isolate_migratepages_range(struct zone *zone, struct compact_control *cc, · line 550

Quoted 10 lines

mm/compaction.c +3 -2

                 * if PageLRU is set) but the lock is not necessarily taken
                 * here and it is wasteful to take it just to check transhuge.
-                * Check transhuge without lock and skip if it's either a
-                * transhuge or hugetlbfs page.
+                * Check transhuge without lock and *skip* if it's either a
+                * transhuge or hugetlbfs page because it's not safe to call
+                * compound_order.
                 */
                if (PageTransHuge(page)) {
                        if (!locked)

Going a bit further:

mm/compaction.c renamed from mm/compaction.c~mm-compaction-acquire-the-zone-lru_lock-as-late-as-possible-fix +2 -1

@@ -415,7 +415,8 @@ isolate_migratepages_range(struct zone *
 		 * if PageLRU is set) but the lock is not necessarily taken
 		 * here and it is wasteful to take it just to check transhuge.
 		 * Check transhuge without lock and skip if it's either a
-		 * transhuge or hugetlbfs page.
+		 * transhuge or hugetlbfs page because calling compound_order()
+		 * requires lru_lock to exclude isolation and splitting.
 		 */
 		if (PageTransHuge(page)) {
 			if (!locked)

_

but... the requirement to hold lru_lock for compound_order() is news to me. It doesn't seem to be written down or explained anywhere, and one wonders why the cheerily undocumented compound_lock() doesn't have this effect. What's going on here??

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

Quoted 9 lines · On Tue, 25 Sep 2012 17:13:27 +0900 Minchan Kim <[email protected]> wrote:

I see. To me, your saying is better than current comment. I hope comment could be more explicit.

mm/compaction.c +0 -0

index df01b4e..f1d2cc7 100644
@@ -542,8 +542,9 @@ isolate_migratepages_range(struct zone *zone, struct compact_control *cc,
                 * splitting and collapsing (collapsing has already happened

mm/compaction.c isolate_migratepages_range(struct zone *zone, struct compact_control *cc, · line 550

Quoted 10 lines

mm/compaction.c +3 -2

                 * if PageLRU is set) but the lock is not necessarily taken
                 * here and it is wasteful to take it just to check transhuge.
-                * Check transhuge without lock and skip if it's either a
-                * transhuge or hugetlbfs page.
+                * Check transhuge without lock and *skip* if it's either a
+                * transhuge or hugetlbfs page because it's not safe to call
+                * compound_order.
                 */
                if (PageTransHuge(page)) {
                        if (!locked)

Going a bit further:

mm/compaction.c renamed from mm/compaction.c~mm-compaction-acquire-the-zone-lru_lock-as-late-as-possible-fix +2 -1

@@ -415,7 +415,8 @@ isolate_migratepages_range(struct zone *
 		 * if PageLRU is set) but the lock is not necessarily taken
 		 * here and it is wasteful to take it just to check transhuge.
 		 * Check transhuge without lock and skip if it's either a
-		 * transhuge or hugetlbfs page.
+		 * transhuge or hugetlbfs page because calling compound_order()
+		 * requires lru_lock to exclude isolation and splitting.
 		 */
 		if (PageTransHuge(page)) {
 			if (!locked)

_

but... the requirement to hold lru_lock for compound_order() is news to me. It doesn't seem to be written down or explained anywhere, and one wonders why the cheerily undocumented compound_lock() doesn't have this effect. What's going on here??

Compactions free scanner acquires the zone->lock when checking for PageBuddy pages and isolating them. It does this even if there are no PageBuddy pages in the range.

This patch defers acquiring the zone lock for as long as possible. In the event there are no free pages in the pageblock then the lock will not be acquired at all which reduces contention on zone->lock.

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

Acked-by Rik van Riel <[email protected]>

---

Compactions free scanner acquires the zone->lock when checking for PageBuddy pages and isolating them. It does this even if there are no PageBuddy pages in the range.

This patch defers acquiring the zone lock for as long as possible. In the event there are no free pages in the pageblock then the lock will not be acquired at all which reduces contention on zone->lock.

...

mm/compaction.c +20 -6

+	int migratetype = get_pageblock_migratetype(page);
+
+	/* Don't interfere with memory hot-remove or the min_free_kbytes blocks */
+	if (migratetype == MIGRATE_ISOLATE || migratetype == MIGRATE_RESERVE)
+		return false;
+
+	/* If the page is a large free page, then allow migration */
+	if (PageBuddy(page) && page_order(page) >= pageblock_order)
+		return true;
+
+	/* If the block is MIGRATE_MOVABLE or MIGRATE_CMA, allow migration */
+	if (migrate_async_suitable(migratetype))
+		return true;
+
+	/* Otherwise skip the block */
+	return false;
+}
+
 
...

@@ -168,23 +193,38 @@ static unsigned long isolate_freepages_block(unsigned long blockpfn,
 		int isolated, i;
 		struct page *page = cursor;
 
-		if (!pfn_valid_within(blockpfn)) {
-			if (strict)
-				return 0;
-			continue;
-		}
+		if (!pfn_valid_within(blockpfn))
+			goto strict_check;
 		nr_scanned++;
 
-		if (!PageBuddy(page)) {

mm/compaction.c +27 -1

+		 * heavily contended if there are parallel allocations
+		 * or parallel compactions. For async compaction do not
+		 * spin on the lock and we acquire the lock as late as
+		 * possible.
+		 */
+		locked = compact_checklock_irqsave(&cc->zone->lock, &flags,
+								locked, cc);
+		if (!locked)
+			break;
+
+		/* Recheck this is a suitable migration target under lock */
+		if (!strict && !suitable_migration_target(page))
+			break;
+
+		/* Recheck this is a buddy page under lock */
+		if (!PageBuddy(page))
+			goto strict_check;
 
 		/* Found a free page, break it into order-0 pages */
 		isolated = split_free_page(page);
 		if (!isolated && strict)
-			return 0;
+			goto strict_check;
 		total_isolated += isolated;
 		for (i = 0; i < isolated; i++) {
 			list_add(&page->lru, freelist);

@@ -196,9 +236,23 @@ static unsigned long isolate_freepages_block(unsigned long blockpfn,
 			blockpfn += isolated - 1;
 			cursor += isolated - 1;
 		}
+
+		continue;
+
+strict_check:
+		/* Abort isolation if the caller requested strict isolation */
+		if (strict) {
+			total_isolated = 0;
+			goto out;
+		}

mm/compaction.c +1 -1

@@ -218,13 +272,18 @@ static unsigned long isolate_freepages_block(unsigned long blockpfn,
 unsigned long
 isolate_freepages_range(unsigned long start_pfn, unsigned long end_pfn)
 {
-	unsigned long isolated, pfn, block_end_pfn, flags;
+	unsigned long isolated, pfn, block_end_pfn;

Quoted 16 lines · On Fri, 21 Sep 2012 11:46:20 +0100 Mel Gorman <[email protected]> wrote:

Compactions free scanner acquires the zone->lock when checking for PageBuddy pages and isolating them. It does this even if there are no PageBuddy pages in the range.

This patch defers acquiring the zone lock for as long as possible. In the event there are no free pages in the pageblock then the lock will not be acquired at all which reduces contention on zone->lock.

...

mm/compaction.c +0 -0

@@ -93,6 +93,28 @@ static inline bool compact_trylock_irqsave(spinlock_t *lock,
 	return compact_checklock_irqsave(lock, flags, false, cc);
 }
 

mm/compaction.c static inline bool compact_trylock_irqsave(spinlock_t *lock, · line 99

Quoted 4 lines

mm/compaction.c +4 -0

+/* Returns true if the page is within a block suitable for migration to */
+static bool suitable_migration_target(struct page *page)
+{
+

stray newline

Quoted 34 lines

mm/compaction.c +20 -5

+	int migratetype = get_pageblock_migratetype(page);
+
+	/* Don't interfere with memory hot-remove or the min_free_kbytes blocks */
+	if (migratetype == MIGRATE_ISOLATE || migratetype == MIGRATE_RESERVE)
+		return false;
+
+	/* If the page is a large free page, then allow migration */
+	if (PageBuddy(page) && page_order(page) >= pageblock_order)
+		return true;
+
+	/* If the block is MIGRATE_MOVABLE or MIGRATE_CMA, allow migration */
+	if (migrate_async_suitable(migratetype))
+		return true;
+
+	/* Otherwise skip the block */
+	return false;
+}
+
 
...

@@ -168,23 +193,38 @@ static unsigned long isolate_freepages_block(unsigned long blockpfn,
 		int isolated, i;
 		struct page *page = cursor;
 
-		if (!pfn_valid_within(blockpfn)) {
-			if (strict)
-				return 0;
-			continue;
-		}
+		if (!pfn_valid_within(blockpfn))
+			goto strict_check;
 		nr_scanned++;
 

mm/compaction.c static unsigned long isolate_freepages_block(unsigned long blockpfn, · line 205

Quoted 11 lines

mm/compaction.c +6 -5

-		if (!PageBuddy(page)) {
-			if (strict)
-				return 0;
-			continue;
-		}
+		if (!PageBuddy(page))
+			goto strict_check;
+
+		/*
+		 * The zone lock must be held to isolate freepages. This
+		 * unfortunately this is a very coarse lock and can be

this this

Quoted 39 lines

mm/compaction.c +27 -1

+		 * heavily contended if there are parallel allocations
+		 * or parallel compactions. For async compaction do not
+		 * spin on the lock and we acquire the lock as late as
+		 * possible.
+		 */
+		locked = compact_checklock_irqsave(&cc->zone->lock, &flags,
+								locked, cc);
+		if (!locked)
+			break;
+
+		/* Recheck this is a suitable migration target under lock */
+		if (!strict && !suitable_migration_target(page))
+			break;
+
+		/* Recheck this is a buddy page under lock */
+		if (!PageBuddy(page))
+			goto strict_check;
 
 		/* Found a free page, break it into order-0 pages */
 		isolated = split_free_page(page);
 		if (!isolated && strict)
-			return 0;
+			goto strict_check;
 		total_isolated += isolated;
 		for (i = 0; i < isolated; i++) {
 			list_add(&page->lru, freelist);

@@ -196,9 +236,23 @@ static unsigned long isolate_freepages_block(unsigned long blockpfn,
 			blockpfn += isolated - 1;
 			cursor += isolated - 1;
 		}
+
+		continue;
+
+strict_check:
+		/* Abort isolation if the caller requested strict isolation */
+		if (strict) {
+			total_isolated = 0;
+			goto out;
+		}

mm/compaction.c static unsigned long isolate_freepages_block(unsigned long blockpfn, · line 257

Quoted 10 lines

mm/compaction.c +5 -0

 	}
 
 	trace_mm_compaction_isolate_freepages(nr_scanned, total_isolated);
+
+out:
+	if (locked)
+		spin_unlock_irqrestore(&cc->zone->lock, flags);
+
 	return total_isolated;
 }

A a few things about this function.

Would it be cleaner if we did

	if (!strict) {
		if (!suitable_migration_target(page))
			break;
	} else {
		if (!PageBuddy(page))
			goto strict_check;
	}

and then remove the test of `strict' from strict_check (which then should be renamed)?

Which perhaps means that the whole `strict_check' block can go away:

	if (!strict) {
		if (!suitable_migration_target(page))
			break;
	} else {
		if (!PageBuddy(page)) {
			total_isolated = 0;
			goto out;
	}

Have a think about it? The function is a little straggly.

Secondly, it is correct/desirable to skip the (now misnamed `trace_mm_compaction_isolate_freepages') tracepoint generation if we baled out of the loop? The fact that we entered isolate_freepages_block() but failed to isolate anything is data which people might be interested in?

Thirdly, that (existing) comment "This assumes the block is valid" is either too vague or wrong. If it's valid, why wo we check pfn_valid_within()?

Quoted 13 lines

mm/compaction.c +2 -1

@@ -218,13 +272,18 @@ static unsigned long isolate_freepages_block(unsigned long blockpfn,
 unsigned long
 isolate_freepages_range(unsigned long start_pfn, unsigned long end_pfn)
 {
-	unsigned long isolated, pfn, block_end_pfn, flags;
+	unsigned long isolated, pfn, block_end_pfn;
 	struct zone *zone = NULL;
 	LIST_HEAD(freelist);
+	struct compact_control cc;
 
 	if (pfn_valid(start_pfn))
 		zone = page_zone(pfn_to_page(start_pfn));
 

mm/compaction.c static unsigned long isolate_freepages_block(unsigned long blockpfn, · line 285

Quoted 3 lines

mm/compaction.c +3 -0

+	/* cc needed for isolate_freepages_block to acquire zone->lock */
+	cc.zone = zone;
+	cc.sync = true;

We initialise two of cc's fields, leave the other 12 fields containing random garbage, then start using it. I see no bug here, but...

Quoted 19 lines · Andrew Morton

Quoted 16 lines · On Fri, 21 Sep 2012 11:46:20 +0100 Mel Gorman <[email protected]> wrote:

Compactions free scanner acquires the zone->lock when checking for PageBuddy pages and isolating them. It does this even if there are no PageBuddy pages in the range.

This patch defers acquiring the zone lock for as long as possible. In the event there are no free pages in the pageblock then the lock will not be acquired at all which reduces contention on zone->lock.

...

mm/compaction.c +0 -0

@@ -93,6 +93,28 @@ static inline bool compact_trylock_irqsave(spinlock_t *lock,
 	return compact_checklock_irqsave(lock, flags, false, cc);
 }
 

Quoted 7 lines

mm/compaction.c static inline bool compact_trylock_irqsave(spinlock_t *lock, · line 99

Quoted 4 lines

mm/compaction.c +4 -0

+/* Returns true if the page is within a block suitable for migration to */
+static bool suitable_migration_target(struct page *page)
+{
+

stray newline

Fixed.

Quoted 34 lines

Quoted 34 lines

mm/compaction.c +20 -5

+	int migratetype = get_pageblock_migratetype(page);
+
+	/* Don't interfere with memory hot-remove or the min_free_kbytes blocks */
+	if (migratetype == MIGRATE_ISOLATE || migratetype == MIGRATE_RESERVE)
+		return false;
+
+	/* If the page is a large free page, then allow migration */
+	if (PageBuddy(page) && page_order(page) >= pageblock_order)
+		return true;
+
+	/* If the block is MIGRATE_MOVABLE or MIGRATE_CMA, allow migration */
+	if (migrate_async_suitable(migratetype))
+		return true;
+
+	/* Otherwise skip the block */
+	return false;
+}
+
 
...

@@ -168,23 +193,38 @@ static unsigned long isolate_freepages_block(unsigned long blockpfn,
 		int isolated, i;
 		struct page *page = cursor;
 
-		if (!pfn_valid_within(blockpfn)) {
-			if (strict)
-				return 0;
-			continue;
-		}
+		if (!pfn_valid_within(blockpfn))
+			goto strict_check;
 		nr_scanned++;
 

Quoted 14 lines

mm/compaction.c static unsigned long isolate_freepages_block(unsigned long blockpfn, · line 205

Quoted 11 lines

mm/compaction.c +6 -5

-		if (!PageBuddy(page)) {
-			if (strict)
-				return 0;
-			continue;
-		}
+		if (!PageBuddy(page))
+			goto strict_check;
+
+		/*
+		 * The zone lock must be held to isolate freepages. This
+		 * unfortunately this is a very coarse lock and can be

this this

Fixed.

Quoted 62 lines

Quoted 39 lines

mm/compaction.c +27 -1

+		 * heavily contended if there are parallel allocations
+		 * or parallel compactions. For async compaction do not
+		 * spin on the lock and we acquire the lock as late as
+		 * possible.
+		 */
+		locked = compact_checklock_irqsave(&cc->zone->lock, &flags,
+								locked, cc);
+		if (!locked)
+			break;
+
+		/* Recheck this is a suitable migration target under lock */
+		if (!strict && !suitable_migration_target(page))
+			break;
+
+		/* Recheck this is a buddy page under lock */
+		if (!PageBuddy(page))
+			goto strict_check;
 
 		/* Found a free page, break it into order-0 pages */
 		isolated = split_free_page(page);
 		if (!isolated && strict)
-			return 0;
+			goto strict_check;
 		total_isolated += isolated;
 		for (i = 0; i < isolated; i++) {
 			list_add(&page->lru, freelist);

@@ -196,9 +236,23 @@ static unsigned long isolate_freepages_block(unsigned long blockpfn,
 			blockpfn += isolated - 1;
 			cursor += isolated - 1;
 		}
+
+		continue;
+
+strict_check:
+		/* Abort isolation if the caller requested strict isolation */
+		if (strict) {
+			total_isolated = 0;
+			goto out;
+		}

mm/compaction.c static unsigned long isolate_freepages_block(unsigned long blockpfn, · line 257

Quoted 10 lines

mm/compaction.c +5 -0

 	}
 
 	trace_mm_compaction_isolate_freepages(nr_scanned, total_isolated);
+
+out:
+	if (locked)
+		spin_unlock_irqrestore(&cc->zone->lock, flags);
+
 	return total_isolated;
 }

A a few things about this function.

Would it be cleaner if we did

	if (!strict) {
		if (!suitable_migration_target(page))
			break;
	} else {
		if (!PageBuddy(page))
			goto strict_check;
	}

Quoted 3 lines

and then remove the test of `strict' from strict_check (which then should be renamed)?

I was not able to implement what you suggested without breakage. However, I can do something very similar if "strict" mode does not bail out ASAP and instead double checks at the end that everything was isolated correctly. This does mean that CMAs failure case is slightly more expensive but that really is a corner case and I think it's acceptable if the code is easier to follow as a result.

Quoted 11 lines

Which perhaps means that the whole `strict_check' block can go away:

	if (!strict) {
		if (!suitable_migration_target(page))
			break;
	} else {
		if (!PageBuddy(page)) {
			total_isolated = 0;
			goto out;
	}

Quoted 2 lines

Have a think about it? The function is a little straggly.

Proposal below.

Quoted 6 lines

Secondly, it is correct/desirable to skip the (now misnamed `trace_mm_compaction_isolate_freepages') tracepoint generation if we baled out of the loop? The fact that we entered isolate_freepages_block() but failed to isolate anything is data which people might be interested in?

You're right, it may be interesting for someone debugging CMA to know that nr_scanned != nr_isolated at the time of allocation failure.

Quoted 4 lines

Thirdly, that (existing) comment "This assumes the block is valid" is either too vague or wrong. If it's valid, why wo we check pfn_valid_within()?

Comment is stale and should be removed.

Quoted 13 lines

Quoted 13 lines

mm/compaction.c +2 -1

@@ -218,13 +272,18 @@ static unsigned long isolate_freepages_block(unsigned long blockpfn,
 unsigned long
 isolate_freepages_range(unsigned long start_pfn, unsigned long end_pfn)
 {
-	unsigned long isolated, pfn, block_end_pfn, flags;
+	unsigned long isolated, pfn, block_end_pfn;
 	struct zone *zone = NULL;
 	LIST_HEAD(freelist);
+	struct compact_control cc;
 
 	if (pfn_valid(start_pfn))
 		zone = page_zone(pfn_to_page(start_pfn));
 

Quoted 7 lines

mm/compaction.c static unsigned long isolate_freepages_block(unsigned long blockpfn, · line 285

Quoted 3 lines

mm/compaction.c +3 -0

+	/* cc needed for isolate_freepages_block to acquire zone->lock */
+	cc.zone = zone;
+	cc.sync = true;

We initialise two of cc's fields, leave the other 12 fields containing random garbage, then start using it. I see no bug here, but...

I get your point. At the very least we should initialise it with zeros.

How about this?

---8<---
mm: compaction: Iron out isolate_freepages_block() and isolate_freepages_range()

Andrew pointed out that isolate_freepages_block() is "straggly" and isolate_freepages_range() is making assumptions on how compact_control is used which is delicate. This patch straightens isolate_freepages_block() and makes it fly straight and initialses compact_control to zeros in isolate_freepages_range(). The code should be easier to follow and is functionally equivalent. The CMA failure path is now a little more expensive but that is a marginal corner-case.

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

Compactions free scanner acquires the zone->lock when checking for PageBuddy pages and isolating them. It does this even if there are no PageBuddy pages in the range.

This patch defers acquiring the zone lock for as long as possible. In the event there are no free pages in the pageblock then the lock will not be acquired at all which reduces contention on zone->lock.

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

Acked-by Rik van Riel <[email protected]>

This reverts commit 7db8889a (mm: have order > 0 compaction start off where it left) and commit de74f1cc (mm: have order > 0 compaction start near a pageblock with free pages). These patches were a good idea and tests confirmed that they massively reduced the amount of scanning but the implementation is complex and tricky to understand. A later patch will cache what pageblocks should be skipped and reimplements the concept of compact_cached_free_pfn on top for both migration and free scanners.

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

Acked-by Rik van Riel <[email protected]>

---

This reverts commit 7db8889a (mm: have order > 0 compaction start off where it left) and commit de74f1cc (mm: have order > 0 compaction start near a pageblock with free pages). These patches were a good idea and tests confirmed that they massively reduced the amount of scanning but the implementation is complex and tricky to understand. A later patch will cache what pageblocks should be skipped and reimplements the concept of compact_cached_free_pfn on top for both migration and free scanners.

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

Acked-by Rik van Riel <[email protected]>

When compaction was implemented it was known that scanning could potentially be excessive. The ideal was that a counter be maintained for each pageblock but maintaining this information would incur a severe penalty due to a shared writable cache line. It has reached the point where the scanning costs are an serious problem, particularly on long-lived systems where a large process starts and allocates a large number of THPs at the same time.

Instead of using a shared counter, this patch adds another bit to the pageblock flags called PG_migrate_skip. If a pageblock is scanned by either migrate or free scanner and 0 pages were isolated, the pageblock is marked to be skipped in the future. When scanning, this bit is checked before any scanning takes place and the block skipped if set.

The main difficulty with a patch like this is "when to ignore the cached information?" If it's ignored too often, the scanning rates will still be excessive. If the information is too stale then allocations will fail that might have otherwise succeeded. In this patch

o CMA always ignores the information
o If the migrate and free scanner meet then the cached information will be discarded if it's at least 5 seconds since the last time the cache was discarded
o If there are a large number of allocation failures, discard the cache.

The time-based heuristic is very clumsy but there are few choices for a better event. Depending solely on multiple allocation failures still allows excessive scanning when THP allocations are failing in quick succession due to memory pressure. Waiting until memory pressure is relieved would cause compaction to continually fail instead of using reclaim/compaction to try allocate the page. The time-based mechanism is clumsy but a better option is not obvious.

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

Acked-by Rik van Riel <[email protected]>

---

When compaction was implemented it was known that scanning could potentially be excessive. The ideal was that a counter be maintained for each pageblock but maintaining this information would incur a severe penalty due to a shared writable cache line. It has reached the point where the scanning costs are an serious problem, particularly on long-lived systems where a large process starts and allocates a large number of THPs at the same time.

Instead of using a shared counter, this patch adds another bit to the pageblock flags called PG_migrate_skip. If a pageblock is scanned by either migrate or free scanner and 0 pages were isolated, the pageblock is marked to be skipped in the future. When scanning, this bit is checked before any scanning takes place and the block skipped if set.

The main difficulty with a patch like this is "when to ignore the cached information?" If it's ignored too often, the scanning rates will still be excessive. If the information is too stale then allocations will fail that might have otherwise succeeded. In this patch

o CMA always ignores the information
o If the migrate and free scanner meet then the cached information will be discarded if it's at least 5 seconds since the last time the cache was discarded
o If there are a large number of allocation failures, discard the cache.

The time-based heuristic is very clumsy but there are few choices for a better event. Depending solely on multiple allocation failures still allows excessive scanning when THP allocations are failing in quick succession due to memory pressure. Waiting until memory pressure is relieved would cause compaction to continually fail instead of using reclaim/compaction to try allocate the page. The time-based mechanism is clumsy but a better option is not obvious.

...

mm/compaction.c +18 -0

+static void reset_isolation_suitable(struct zone *zone)
+{
+	unsigned long start_pfn = zone->zone_start_pfn;
+	unsigned long end_pfn = zone->zone_start_pfn + zone->spanned_pages;
+	unsigned long pfn;
+
+	/*
+	 * Do not reset more than once every five seconds. If allocations are
+	 * failing sufficiently quickly to allow this to happen then continually
+	 * scanning for compaction is not going to help. The choice of five
+	 * seconds is arbitrary but will mitigate excessive scanning.
+	 */
+	if (time_before(jiffies, zone->compact_blockskip_expire))
+		return;
+	zone->compact_blockskip_expire = jiffies + (HZ * 5);
+
+	/* Walk the zone and mark every pageblock as suitable for isolation */
+	for (pfn = start_pfn; pfn < end_pfn; pfn += pageblock_nr_pages) {

mm/compaction.c +2 -0

+}
+
 
...

Quoted 24 lines · On Fri, 21 Sep 2012 11:46:22 +0100 Mel Gorman <[email protected]> wrote:

When compaction was implemented it was known that scanning could potentially be excessive. The ideal was that a counter be maintained for each pageblock but maintaining this information would incur a severe penalty due to a shared writable cache line. It has reached the point where the scanning costs are an serious problem, particularly on long-lived systems where a large process starts and allocates a large number of THPs at the same time.

Instead of using a shared counter, this patch adds another bit to the pageblock flags called PG_migrate_skip. If a pageblock is scanned by either migrate or free scanner and 0 pages were isolated, the pageblock is marked to be skipped in the future. When scanning, this bit is checked before any scanning takes place and the block skipped if set.

The main difficulty with a patch like this is "when to ignore the cached information?" If it's ignored too often, the scanning rates will still be excessive. If the information is too stale then allocations will fail that might have otherwise succeeded. In this patch

o CMA always ignores the information
o If the migrate and free scanner meet then the cached information will be discarded if it's at least 5 seconds since the last time the cache was discarded
o If there are a large number of allocation failures, discard the cache.

Quoted 7 lines

The time-based heuristic is very clumsy but there are few choices for a better event. Depending solely on multiple allocation failures still allows excessive scanning when THP allocations are failing in quick succession due to memory pressure. Waiting until memory pressure is relieved would cause compaction to continually fail instead of using reclaim/compaction to try allocate the page. The time-based mechanism is clumsy but a better option is not obvious.

ick.

Wall time has sooo little relationship to what's happening in there. If we *have* to use polling, cannot we clock the poll with some metric which is at least vaguely related to the amount of activity?

Number
(or proportion) of pages scanned, for example? Or reset everything on the Nth trip around the zone?

Or even a combination of one of these
*and* of wall time, so the system will at least work harder when MM is under load.

Also, what has to be done to avoid the polling altogether? eg/ie, zap a pageblock's PB_migrate_skip synchronously, when something was done to that pageblock which justifies repolling it?

Quoted 25 lines

...

mm/compaction.c +22 -0

+static void reset_isolation_suitable(struct zone *zone)
+{
+	unsigned long start_pfn = zone->zone_start_pfn;
+	unsigned long end_pfn = zone->zone_start_pfn + zone->spanned_pages;
+	unsigned long pfn;
+
+	/*
+	 * Do not reset more than once every five seconds. If allocations are
+	 * failing sufficiently quickly to allow this to happen then continually
+	 * scanning for compaction is not going to help. The choice of five
+	 * seconds is arbitrary but will mitigate excessive scanning.
+	 */
+	if (time_before(jiffies, zone->compact_blockskip_expire))
+		return;
+	zone->compact_blockskip_expire = jiffies + (HZ * 5);
+
+	/* Walk the zone and mark every pageblock as suitable for isolation */
+	for (pfn = start_pfn; pfn < end_pfn; pfn += pageblock_nr_pages) {
+		struct page *page;
+		if (!pfn_valid(pfn))
+			continue;
+

mm/compaction.c static inline bool migrate_async_suitable(int migratetype) · line 95

Quoted 6 lines

mm/compaction.c +6 -0

+		page = pfn_to_page(pfn);
+		if (zone != page_zone(page))
+			continue;
+
+		clear_pageblock_skip(page);
+	}

What's the worst-case loop count here?

Quoted 5 lines

mm/compaction.c +2 -0

+}
+
 
...

Quoted 4 lines · Andrew Morton

Also, what has to be done to avoid the polling altogether? eg/ie, zap a pageblock's PB_migrate_skip synchronously, when something was done to that pageblock which justifies repolling it?

The "something" event you are looking for is pages being freed or allocated in the page allocator. A movable page being allocated in block or a page being freed should clear the PB_migrate_skip bit if it's set. Unfortunately this would impact the fast path of the alloc and free paths of the page allocator. I felt that that was too high a price to pay.

Quoted 25 lines

Quoted 25 lines

...

mm/compaction.c +22 -0

+static void reset_isolation_suitable(struct zone *zone)
+{
+	unsigned long start_pfn = zone->zone_start_pfn;
+	unsigned long end_pfn = zone->zone_start_pfn + zone->spanned_pages;
+	unsigned long pfn;
+
+	/*
+	 * Do not reset more than once every five seconds. If allocations are
+	 * failing sufficiently quickly to allow this to happen then continually
+	 * scanning for compaction is not going to help. The choice of five
+	 * seconds is arbitrary but will mitigate excessive scanning.
+	 */
+	if (time_before(jiffies, zone->compact_blockskip_expire))
+		return;
+	zone->compact_blockskip_expire = jiffies + (HZ * 5);
+
+	/* Walk the zone and mark every pageblock as suitable for isolation */
+	for (pfn = start_pfn; pfn < end_pfn; pfn += pageblock_nr_pages) {
+		struct page *page;
+		if (!pfn_valid(pfn))
+			continue;
+

Quoted 9 lines

mm/compaction.c static inline bool migrate_async_suitable(int migratetype) · line 95

Quoted 6 lines

mm/compaction.c +6 -0

+		page = pfn_to_page(pfn);
+		if (zone != page_zone(page))
+			continue;
+
+		clear_pageblock_skip(page);
+	}

What's the worst-case loop count here?

zone->spanned_pages >> pageblock_order

Quoted 7 lines · On Mon, 24 Sep 2012 10:39:38 +0100 Mel Gorman <[email protected]> wrote:

Quoted 4 lines · Andrew Morton

Also, what has to be done to avoid the polling altogether? eg/ie, zap a pageblock's PB_migrate_skip synchronously, when something was done to that pageblock which justifies repolling it?

Quoted 5 lines

The "something" event you are looking for is pages being freed or allocated in the page allocator. A movable page being allocated in block or a page being freed should clear the PB_migrate_skip bit if it's set. Unfortunately this would impact the fast path of the alloc and free paths of the page allocator. I felt that that was too high a price to pay.

We already do a similar thing in the page allocator: clearing of ->all_unreclaimable and ->pages_scanned.

But that isn't on the "fast
path" really - it happens once per pcp unload.

Can we do something
like that? Drop some hint into the zone without having to visit each page?

Quoted 35 lines

Quoted 34 lines

Quoted 21 lines

...

mm/compaction.c +18 -0

+static void reset_isolation_suitable(struct zone *zone)
+{
+	unsigned long start_pfn = zone->zone_start_pfn;
+	unsigned long end_pfn = zone->zone_start_pfn + zone->spanned_pages;
+	unsigned long pfn;
+
+	/*
+	 * Do not reset more than once every five seconds. If allocations are
+	 * failing sufficiently quickly to allow this to happen then continually
+	 * scanning for compaction is not going to help. The choice of five
+	 * seconds is arbitrary but will mitigate excessive scanning.
+	 */
+	if (time_before(jiffies, zone->compact_blockskip_expire))
+		return;
+	zone->compact_blockskip_expire = jiffies + (HZ * 5);
+
+	/* Walk the zone and mark every pageblock as suitable for isolation */
+	for (pfn = start_pfn; pfn < end_pfn; pfn += pageblock_nr_pages) {

mm/compaction.c static inline bool migrate_async_suitable(int migratetype) · line 95

Quoted 10 lines

mm/compaction.c +10 -0

+		struct page *page;
+		if (!pfn_valid(pfn))
+			continue;
+
+		page = pfn_to_page(pfn);
+		if (zone != page_zone(page))
+			continue;
+
+		clear_pageblock_skip(page);
+	}

What's the worst-case loop count here?

Quoted 1 line

zone->spanned_pages >> pageblock_order

What's the worst-case value of (zone->spanned_pages >> pageblock_order) :)

First, we'd introduce a variant of get_pageblock_migratetype() that returns all the bits for the pageblock flags and then helpers to extract either the migratetype or the PG_migrate_skip. We already are incurring the cost of get_pageblock_migratetype() so it will not be much more expensive than what is already there. If there is an allocation or free within a pageblock that as the PG_migrate_skip bit set then we increment a counter. When the counter reaches some to-be-decided "threshold" then compaction may clear all the bits. This would match the criteria of the clearing being based on activity.

There are four potential problems with this

1. The logic to retrieve all the bits and split them up will be a little convulated but maybe it would not be that bad.

2. The counter is a shared-writable cache line but obviously it could be moved to vmstat and incremented with inc_zone_page_state to offset the cost a little.

3. The biggested weakness is that there is not way to know if the counter is incremented based on activity in a small subset of blocks.

4. What should the threshold be?

The first problem is minor but the other three are potentially a mess. Adding another vmstat counter is bad enough in itself but if the counter is incremented based on a small subsets of pageblocks, the hint becomes is potentially useless.

However, does this match what you have in mind or am I over-complicating things?

Quoted 15 lines

Quoted 15 lines

Quoted 14 lines

mm/compaction.c static inline bool migrate_async_suitable(int migratetype) · line 95

Quoted 11 lines

mm/compaction.c +11 -0

+	for (pfn = start_pfn; pfn < end_pfn; pfn += pageblock_nr_pages) {
+		struct page *page;
+		if (!pfn_valid(pfn))
+			continue;
+
+		page = pfn_to_page(pfn);
+		if (zone != page_zone(page))
+			continue;
+
+		clear_pageblock_skip(page);
+	}

What's the worst-case loop count here?

Quoted 3 lines

Quoted 1 line

zone->spanned_pages >> pageblock_order

What's the worst-case value of (zone->spanned_pages >> pageblock_order) :)

Lets take an unlikely case - 128G single-node machine. That loop count on x86-64 would be 65536. It'll be fast enough, particularly in this path.

Quoted 28 lines · On Tue, 25 Sep 2012 10:12:07 +0100 Mel Gorman <[email protected]> wrote:

First, we'd introduce a variant of get_pageblock_migratetype() that returns all the bits for the pageblock flags and then helpers to extract either the migratetype or the PG_migrate_skip. We already are incurring the cost of get_pageblock_migratetype() so it will not be much more expensive than what is already there. If there is an allocation or free within a pageblock that as the PG_migrate_skip bit set then we increment a counter. When the counter reaches some to-be-decided "threshold" then compaction may clear all the bits. This would match the criteria of the clearing being based on activity.

There are four potential problems with this

1. The logic to retrieve all the bits and split them up will be a little convulated but maybe it would not be that bad.

2. The counter is a shared-writable cache line but obviously it could be moved to vmstat and incremented with inc_zone_page_state to offset the cost a little.

3. The biggested weakness is that there is not way to know if the counter is incremented based on activity in a small subset of blocks.

4. What should the threshold be?

The first problem is minor but the other three are potentially a mess. Adding another vmstat counter is bad enough in itself but if the counter is incremented based on a small subsets of pageblocks, the hint becomes is potentially useless.

Quoted 2 lines

However, does this match what you have in mind or am I over-complicating things?

Sounds complicated.

Using wall time really does suck.

Are you sure you can't think of
something more logical?

How would we demonstrate the suckage? What would be the observeable downside of switching that 5 seconds to 5 hours?

Quoted 3 lines

Lets take an unlikely case - 128G single-node machine. That loop count on x86-64 would be 65536. It'll be fast enough, particularly in this path.

That could easily exceed a millisecond. Can/should we stick a cond_resched() in there?

Quoted 10 lines · Andrew Morton

Quoted 7 lines · On Mon, 24 Sep 2012 10:39:38 +0100 Mel Gorman <[email protected]> wrote:

Quoted 4 lines · Andrew Morton

Also, what has to be done to avoid the polling altogether? eg/ie, zap a pageblock's PB_migrate_skip synchronously, when something was done to that pageblock which justifies repolling it?

Quoted 8 lines

Quoted 5 lines

The "something" event you are looking for is pages being freed or allocated in the page allocator. A movable page being allocated in block or a page being freed should clear the PB_migrate_skip bit if it's set. Unfortunately this would impact the fast path of the alloc and free paths of the page allocator. I felt that that was too high a price to pay.

We already do a similar thing in the page allocator: clearing of ->all_unreclaimable and ->pages_scanned.

That is true but that is a simple write (shared cache line but still) to a struct zone. Worse, now that you point it out, that's pretty stupid. It should be checking if the value is non-zero before writing to it to avoid a cache line bounce.

Clearing the PG_migrate_skip in this path to avoid the need to ever pool is not as cheap as it needs to

set_pageblock_skip
-> set_pageblock_flags_group

    -> page_zone
    -> page_to_pfn
    -> get_pageblock_bitmap
    -> pfn_to_bitidx
    -> __set_bit

Quoted 2 lines

But that isn't on the "fast
path" really - it happens once per pcp unload.

That's still an important enough path that I'm wary of making it fatter and that only covers the free path. To avoid the polling, the allocation side needs to be handled too. It could be shoved down into rmqueue() to put it into a slightly colder path but still, it's a price to pay to keep compaction happy.

Quoted 4 lines

Can we do something
like that? Drop some hint into the zone without having to visit each page?

Not without incurring a cost, but yes, t is possible to give a hint on when PG_migrate_skip should be cleared and move away from that time-based hammer.

First, we'd introduce a variant of get_pageblock_migratetype() that returns all the bits for the pageblock flags and then helpers to extract either the migratetype or the PG_migrate_skip. We already are incurring the cost of get_pageblock_migratetype() so it will not be much more expensive than what is already there. If there is an allocation or free within a pageblock that as the PG_migrate_skip bit set then we increment a counter. When the counter reaches some to-be-decided "threshold" then compaction may clear all the bits. This would match the criteria of the clearing being based on activity.

There are four potential problems with this

1. The logic to retrieve all the bits and split them up will be a little convulated but maybe it would not be that bad.

2. The counter is a shared-writable cache line but obviously it could be moved to vmstat and incremented with inc_zone_page_state to offset the cost a little.

3. The biggested weakness is that there is not way to know if the counter is incremented based on activity in a small subset of blocks.

4. What should the threshold be?

The first problem is minor but the other three are potentially a mess. Adding another vmstat counter is bad enough in itself but if the counter is incremented based on a small subsets of pageblocks, the hint becomes is potentially useless.

However, does this match what you have in mind or am I over-complicating things?

Quoted 35 lines

Quoted 35 lines

Quoted 34 lines

Quoted 21 lines

...

mm/compaction.c +18 -0

+static void reset_isolation_suitable(struct zone *zone)
+{
+	unsigned long start_pfn = zone->zone_start_pfn;
+	unsigned long end_pfn = zone->zone_start_pfn + zone->spanned_pages;
+	unsigned long pfn;
+
+	/*
+	 * Do not reset more than once every five seconds. If allocations are
+	 * failing sufficiently quickly to allow this to happen then continually
+	 * scanning for compaction is not going to help. The choice of five
+	 * seconds is arbitrary but will mitigate excessive scanning.
+	 */
+	if (time_before(jiffies, zone->compact_blockskip_expire))
+		return;
+	zone->compact_blockskip_expire = jiffies + (HZ * 5);
+
+	/* Walk the zone and mark every pageblock as suitable for isolation */
+	for (pfn = start_pfn; pfn < end_pfn; pfn += pageblock_nr_pages) {

mm/compaction.c static inline bool migrate_async_suitable(int migratetype) · line 95

Quoted 10 lines

mm/compaction.c +10 -0

+		struct page *page;
+		if (!pfn_valid(pfn))
+			continue;
+
+		page = pfn_to_page(pfn);
+		if (zone != page_zone(page))
+			continue;
+
+		clear_pageblock_skip(page);
+	}

What's the worst-case loop count here?

Quoted 3 lines

Quoted 1 line

zone->spanned_pages >> pageblock_order

What's the worst-case value of (zone->spanned_pages >> pageblock_order) :)

Lets take an unlikely case - 128G single-node machine. That loop count on x86-64 would be 65536. It'll be fast enough, particularly in this path.

Signature · 8 lines

Mel Gorman
SUSE Labs

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

Quoted 74 lines · Mel Gorman

Quoted 10 lines · Andrew Morton

Quoted 7 lines · On Mon, 24 Sep 2012 10:39:38 +0100 Mel Gorman <[email protected]> wrote:

Quoted 4 lines · Andrew Morton

Also, what has to be done to avoid the polling altogether? eg/ie, zap a pageblock's PB_migrate_skip synchronously, when something was done to that pageblock which justifies repolling it?

Quoted 8 lines

Quoted 5 lines

The "something" event you are looking for is pages being freed or allocated in the page allocator. A movable page being allocated in block or a page being freed should clear the PB_migrate_skip bit if it's set. Unfortunately this would impact the fast path of the alloc and free paths of the page allocator. I felt that that was too high a price to pay.

We already do a similar thing in the page allocator: clearing of ->all_unreclaimable and ->pages_scanned.

That is true but that is a simple write (shared cache line but still) to a struct zone. Worse, now that you point it out, that's pretty stupid. It should be checking if the value is non-zero before writing to it to avoid a cache line bounce.

Clearing the PG_migrate_skip in this path to avoid the need to ever pool is not as cheap as it needs to

set_pageblock_skip
-> set_pageblock_flags_group

    -> page_zone
    -> page_to_pfn
    -> get_pageblock_bitmap
    -> pfn_to_bitidx
    -> __set_bit

Quoted 2 lines

But that isn't on the "fast
path" really - it happens once per pcp unload.

That's still an important enough path that I'm wary of making it fatter and that only covers the free path. To avoid the polling, the allocation side needs to be handled too. It could be shoved down into rmqueue() to put it into a slightly colder path but still, it's a price to pay to keep compaction happy.

Quoted 4 lines

Can we do something
like that? Drop some hint into the zone without having to visit each page?

Not without incurring a cost, but yes, t is possible to give a hint on when PG_migrate_skip should be cleared and move away from that time-based hammer.

First, we'd introduce a variant of get_pageblock_migratetype() that returns all the bits for the pageblock flags and then helpers to extract either the migratetype or the PG_migrate_skip. We already are incurring the cost of get_pageblock_migratetype() so it will not be much more expensive than what is already there. If there is an allocation or free within a pageblock that as the PG_migrate_skip bit set then we increment a counter. When the counter reaches some to-be-decided "threshold" then compaction may clear all the bits. This would match the criteria of the clearing being based on activity.

There are four potential problems with this

1. The logic to retrieve all the bits and split them up will be a little convulated but maybe it would not be that bad.

2. The counter is a shared-writable cache line but obviously it could be moved to vmstat and incremented with inc_zone_page_state to offset the cost a little.

3. The biggested weakness is that there is not way to know if the counter is incremented based on activity in a small subset of blocks.

Quoted 6 lines

4. What should the threshold be?

The first problem is minor but the other three are potentially a mess. Adding another vmstat counter is bad enough in itself but if the counter is incremented based on a small subsets of pageblocks, the hint becomes is potentially useless.

Another idea is that we can add two bits(PG_check_migrate/PG_check_free) in pageblock_flags_group.
In allocation path, we can set PG_check_migrate in a pageblock In free path, we can set PG_check_free in a pageblock.
And they are cleared by compaction's scan like now.
So we can discard 3 and 4 at least.

Another idea is that let's cure it by fixing fundamental problem. Make zone's locks more fine-grained.

As time goes by, system uses bigger memory but our lock of zone isn't scalable. Recently, lru_lock and zone->lock contention report isn't rare so i think it's good time that we move next step.

How about defining struct sub_zone per 2G or 4G?
so a zone can have several sub_zone as size and subzone can replace current zone's role and zone is just container of subzones. Of course, it's not easy to implement but I think someday we should go that way. Is it a really overkill?

This is almost entirely based on Rik's previous patches and discussions with him about how this might be implemented.

Order > 0 compaction stops when enough free pages of the correct page order have been coalesced. When doing subsequent higher order allocations, it is possible for compaction to be invoked many times.

However, the compaction code always starts out looking for things to compact at the start of the zone, and for free pages to compact things to at the end of the zone.

This can cause quadratic behaviour, with isolate_freepages starting at the end of the zone each time, even though previous invocations of the compaction code already filled up all free memory on that end of the zone. This can cause isolate_freepages to take enormous amounts of CPU with certain workloads on larger memory systems.

This patch caches where the migration and free scanner should start from on subsequent compaction invocations using the pageblock-skip information. When compaction starts it begins from the cached restart points and will update the cached restart points until a page is isolated or a pageblock is skipped that would have been scanned by synchronous compaction.

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

Acked-by Rik van Riel <[email protected]>

---

Hi Andrew,

Richard Davies and Shaohua Li have both reported lock contention problems in compaction on the zone and LRU locks as well as significant amounts of time being spent in compaction. This series aims to reduce lock contention and scanning rates to reduce that CPU usage. Richard reported at https://lkml.org/lkml/2012/9/21/91 that this series made a big different to a problem he reported in August
(http://marc.info/?l=kvm&m=134511507015614&w=2).

One way or the other, this series has a large impact on the amount of scanning compaction does when there is a storm of THP allocations.