Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1578730 > unrolled thread

[PATCH v2 00/10] try to reduce fragmenting fallbacks

Back to article view | Back to linux.kernel

Contents

  [PATCH v2 00/10] try to reduce fragmenting fallbacks Vlastimil Babka <vbabka@suse.cz> - 2017-02-10 20:20 +0100
    [PATCH v2 03/10] mm, page_alloc: split smallest stolen page in fallback Vlastimil Babka <vbabka@suse.cz> - 2017-02-10 20:20 +0100
      Re: [PATCH v2 03/10] mm, page_alloc: split smallest stolen page in  fallback Mel Gorman <mgorman@techsingularity.net> - 2017-02-13 12:00 +0100
        Re: [PATCH v2 03/10] mm, page_alloc: split smallest stolen page in  fallback Vlastimil Babka <vbabka@suse.cz> - 2017-02-13 12:00 +0100
    [PATCH v2 01/10] mm, compaction: reorder fields in struct compact_control Vlastimil Babka <vbabka@suse.cz> - 2017-02-10 20:20 +0100
      Re: [PATCH v2 01/10] mm, compaction: reorder fields in struct  compact_control Mel Gorman <mgorman@techsingularity.net> - 2017-02-13 11:50 +0100
    [PATCH v2 06/10] mm, compaction: add migratetype to compact_control Vlastimil Babka <vbabka@suse.cz> - 2017-02-10 20:20 +0100
      Re: [PATCH v2 06/10] mm, compaction: add migratetype to  compact_control Mel Gorman <mgorman@techsingularity.net> - 2017-02-13 12:00 +0100
    [PATCH v2 02/10] mm, compaction: remove redundant watermark check in compact_finished() Vlastimil Babka <vbabka@suse.cz> - 2017-02-10 20:20 +0100
      Re: [PATCH v2 02/10] mm, compaction: remove redundant watermark  check in compact_finished() Mel Gorman <mgorman@techsingularity.net> - 2017-02-13 11:50 +0100
    Re: [PATCH v2 00/10] try to reduce fragmenting fallbacks Mel Gorman <mgorman@techsingularity.net> - 2017-02-13 12:10 +0100

#1578730 — [PATCH v2 00/10] try to reduce fragmenting fallbacks

Hi,

this is a v2 of [1] from last year, which was a response to Johanes' worries
about mobility grouping regressions. There are some new patches and the order
goes from cleanups to "obvious wins" towards "just RFC" (last two patches).
But it's all theoretical for now, I'm trying to run some tests with the usual
problem of not having good workloads and metrics :) But I'd like to hear some
feedback anyway. For now this is based on v4.9.

I think the only substantial new patch is 08/10, the rest is some cleanups,
small tweaks and bugfixes.

[1] https://www.spinics.net/lists/linux-mm/msg114380.html

Vlastimil Babka (10):
  mm, compaction: reorder fields in struct compact_control
  mm, compaction: remove redundant watermark check in compact_finished()
  mm, page_alloc: split smallest stolen page in fallback
  mm, page_alloc: count movable pages when stealing from pageblock
  mm, compaction: change migrate_async_suitable() to
    suitable_migration_source()
  mm, compaction: add migratetype to compact_control
  mm, compaction: restrict async compaction to pageblocks of same
    migratetype
  mm, compaction: finish whole pageblock to reduce fragmentation
  mm, page_alloc: disallow migratetype fallback in fastpath
  mm, page_alloc: introduce MIGRATE_MIXED migratetype

 include/linux/mmzone.h         |   6 ++
 include/linux/page-isolation.h |   5 +-
 mm/compaction.c                | 116 +++++++++++++++++-------
 mm/internal.h                  |  14 +--
 mm/page_alloc.c                | 196 +++++++++++++++++++++++++++++------------
 mm/page_isolation.c            |   5 +-
 6 files changed, 246 insertions(+), 96 deletions(-)

-- 
2.11.0

[toc] | [next] | [standalone]

#1578733 — [PATCH v2 03/10] mm, page_alloc: split smallest stolen page in fallback

The __rmqueue_fallback() function is called when there's no free page of
requested migratetype, and we need to steal from a different one. There are
various heuristics to make this event infrequent and reduce permanent
fragmentation. The main one is to try stealing from a pageblock that has the
most free pages, and possibly steal them all at once and convert the whole
pageblock. Precise searching for such pageblock would be expensive, so instead
the heuristics walks the free lists from MAX_ORDER down to requested order and
assumes that the block with highest-order free page is likely to also have the
most free pages in total.

Chances are that together with the highest-order page, we steal also pages of
lower orders from the same block. But then we still split the highest order
page. This is wasteful and can contribute to fragmentation instead of avoiding
it.

This patch thus changes __rmqueue_fallback() to just steal the page(s) and put
them on the freelist of the requested migratetype, and only report whether it
was successful. Then we pick (and eventually split) the smallest page with
__rmqueue_smallest().  This all happens under zone lock, so nobody can steal it
from us in the process. This should reduce fragmentation due to fallbacks. At
worst we are only stealing a single highest-order page and waste some cycles by
moving it between lists and then removing it, but fallback is not exactly hot
path so that should not be a concern. As a side benefit the patch removes some
duplicate code by reusing __rmqueue_smallest().

Signed-off-by: Vlastimil Babka <vbabka@suse.cz>
---
 mm/page_alloc.c | 48 ++++++++++++++++++++++++------------------------
 1 file changed, 24 insertions(+), 24 deletions(-)

diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index 6de9440e3ae2..314e6b9ddbc4 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c
@@ -1960,14 +1960,24 @@ static bool can_steal_fallback(unsigned int order, int start_mt)
  * use it's pages as requested migratetype in the future.
  */
 static void steal_suitable_fallback(struct zone *zone, struct page *page,
-							  int start_type)
+					 int start_type, bool whole_block)
 {
 	unsigned int current_order = page_order(page);
+	struct free_area *area;
 	int pages;
 
 	/* Take ownership for orders >= pageblock_order */
 	if (current_order >= pageblock_order) {
 		change_pageblock_range(page, current_order, start_type);
+		area = &zone->free_area[current_order];
+		list_move(&page->lru, &area->free_list[start_type]);
+		return;
+	}
+
+	/* We are not allowed to try stealing from the whole block */
+	if (!whole_block) {
+		area = &zone->free_area[current_order];
+		list_move(&page->lru, &area->free_list[start_type]);
 		return;
 	}
 
@@ -2111,8 +2121,13 @@ static void unreserve_highatomic_pageblock(const struct alloc_context *ac)
 	}
 }
 
-/* Remove an element from the buddy allocator from the fallback list */
-static inline struct page *
+/*
+ * Try finding a free buddy page on the fallback list and put it on the free
+ * list of requested migratetype, possibly along with other pages from the same
+ * block, depending on fragmentation avoidance heuristics. Returns true if
+ * fallback was found so that __rmqueue_smallest() can grab it.
+ */
+static inline bool
 __rmqueue_fallback(struct zone *zone, unsigned int order, int start_migratetype)
 {
 	struct free_area *area;
@@ -2133,32 +2148,16 @@ __rmqueue_fallback(struct zone *zone, unsigned int order, int start_migratetype)
 
 		page = list_first_entry(&area->free_list[fallback_mt],
 						struct page, lru);
-		if (can_steal)
-			steal_suitable_fallback(zone, page, start_migratetype);
 
-		/* Remove the page from the freelists */
-		area->nr_free--;
-		list_del(&page->lru);
-		rmv_page_order(page);
-
-		expand(zone, page, order, current_order, area,
-					start_migratetype);
-		/*
-		 * The pcppage_migratetype may differ from pageblock's
-		 * migratetype depending on the decisions in
-		 * find_suitable_fallback(). This is OK as long as it does not
-		 * differ for MIGRATE_CMA pageblocks. Those can be used as
-		 * fallback only via special __rmqueue_cma_fallback() function
-		 */
-		set_pcppage_migratetype(page, start_migratetype);
+		steal_suitable_fallback(zone, page, start_migratetype, can_steal);
 
 		trace_mm_page_alloc_extfrag(page, order, current_order,
 			start_migratetype, fallback_mt);
 
-		return page;
+		return true;
 	}
 
-	return NULL;
+	return false;
 }
 
 /*
@@ -2170,13 +2169,14 @@ static struct page *__rmqueue(struct zone *zone, unsigned int order,
 {
 	struct page *page;
 
+retry:
 	page = __rmqueue_smallest(zone, order, migratetype);
 	if (unlikely(!page)) {
 		if (migratetype == MIGRATE_MOVABLE)
 			page = __rmqueue_cma_fallback(zone, order);
 
-		if (!page)
-			page = __rmqueue_fallback(zone, order, migratetype);
+		if (!page && __rmqueue_fallback(zone, order, migratetype))
+			goto retry;
 	}
 
 	trace_mm_page_alloc_zone_locked(page, order, migratetype);
-- 
2.11.0

[toc] | [prev] | [next] | [standalone]

#1579611 — Re: [PATCH v2 03/10] mm, page_alloc: split smallest stolen page in fallback

On Fri, Feb 10, 2017 at 06:23:36PM +0100, Vlastimil Babka wrote:
> The __rmqueue_fallback() function is called when there's no free page of
> requested migratetype, and we need to steal from a different one. There are
> various heuristics to make this event infrequent and reduce permanent
> fragmentation. The main one is to try stealing from a pageblock that has the
> most free pages, and possibly steal them all at once and convert the whole
> pageblock. Precise searching for such pageblock would be expensive, so instead
> the heuristics walks the free lists from MAX_ORDER down to requested order and
> assumes that the block with highest-order free page is likely to also have the
> most free pages in total.
> 
> Chances are that together with the highest-order page, we steal also pages of
> lower orders from the same block. But then we still split the highest order
> page. This is wasteful and can contribute to fragmentation instead of avoiding
> it.
> 

The original intent was that if an allocation request was stealing a
pageblock that taking the largest one would reduce the likelihood of a
steal in the near future by the same type.

> This patch thus changes __rmqueue_fallback() to just steal the page(s) and put
> them on the freelist of the requested migratetype, and only report whether it
> was successful. Then we pick (and eventually split) the smallest page with
> __rmqueue_smallest().  This all happens under zone lock, so nobody can steal it
> from us in the process. This should reduce fragmentation due to fallbacks. At
> worst we are only stealing a single highest-order page and waste some cycles by
> moving it between lists and then removing it, but fallback is not exactly hot
> path so that should not be a concern. As a side benefit the patch removes some
> duplicate code by reusing __rmqueue_smallest().
> 
> Signed-off-by: Vlastimil Babka <vbabka@suse.cz>

But conceptually this is better so

Acked-by: Mel Gorman <mgorman@techsingularity.net>

-- 
Mel Gorman
SUSE Labs

[toc] | [prev] | [next] | [standalone]

#1579616 — Re: [PATCH v2 03/10] mm, page_alloc: split smallest stolen page in fallback

On 02/13/2017 11:51 AM, Mel Gorman wrote:
> On Fri, Feb 10, 2017 at 06:23:36PM +0100, Vlastimil Babka wrote:
>> The __rmqueue_fallback() function is called when there's no free page of
>> requested migratetype, and we need to steal from a different one. There are
>> various heuristics to make this event infrequent and reduce permanent
>> fragmentation. The main one is to try stealing from a pageblock that has the
>> most free pages, and possibly steal them all at once and convert the whole
>> pageblock. Precise searching for such pageblock would be expensive, so instead
>> the heuristics walks the free lists from MAX_ORDER down to requested order and
>> assumes that the block with highest-order free page is likely to also have the
>> most free pages in total.
>>
>> Chances are that together with the highest-order page, we steal also pages of
>> lower orders from the same block. But then we still split the highest order
>> page. This is wasteful and can contribute to fragmentation instead of avoiding
>> it.
>>
> 
> The original intent was that if an allocation request was stealing a
> pageblock that taking the largest one would reduce the likelihood of a
> steal in the near future by the same type.

I understand the intent and tried to explain that in the first
paragraph. This patch doesn't change that, we still select the pageblock
for stealing based on the largest free page we find. But if we manage to
steal also some smaller pages from the same pageblock, we will split the
smallest one instead of the largest one.

>> This patch thus changes __rmqueue_fallback() to just steal the page(s) and put
>> them on the freelist of the requested migratetype, and only report whether it
>> was successful. Then we pick (and eventually split) the smallest page with
>> __rmqueue_smallest().  This all happens under zone lock, so nobody can steal it
>> from us in the process. This should reduce fragmentation due to fallbacks. At
>> worst we are only stealing a single highest-order page and waste some cycles by
>> moving it between lists and then removing it, but fallback is not exactly hot
>> path so that should not be a concern. As a side benefit the patch removes some
>> duplicate code by reusing __rmqueue_smallest().
>>
>> Signed-off-by: Vlastimil Babka <vbabka@suse.cz>
> 
> But conceptually this is better so
> 
> Acked-by: Mel Gorman <mgorman@techsingularity.net>

Thanks!

[toc] | [prev] | [next] | [standalone]

#1578734 — [PATCH v2 01/10] mm, compaction: reorder fields in struct compact_control

While currently there are (mostly by accident) no holes in struct
compact_control (on x86_64), but we are going to add more bool flags, so place
them all together to the end of the structure. While at it, just order all
fields from largest to smallest.

Signed-off-by: Vlastimil Babka <vbabka@suse.cz>
---
 mm/internal.h | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

diff --git a/mm/internal.h b/mm/internal.h
index 537ac9951f5f..da37ddd3db40 100644
--- a/mm/internal.h
+++ b/mm/internal.h
@@ -171,21 +171,21 @@ extern int user_min_free_kbytes;
 struct compact_control {
 	struct list_head freepages;	/* List of free pages to migrate to */
 	struct list_head migratepages;	/* List of pages being migrated */
+	struct zone *zone;
 	unsigned long nr_freepages;	/* Number of isolated free pages */
 	unsigned long nr_migratepages;	/* Number of pages to migrate */
 	unsigned long free_pfn;		/* isolate_freepages search base */
 	unsigned long migrate_pfn;	/* isolate_migratepages search base */
 	unsigned long last_migrated_pfn;/* Not yet flushed page being freed */
+	const gfp_t gfp_mask;		/* gfp mask of a direct compactor */
+	int order;			/* order a direct compactor needs */
+	const unsigned int alloc_flags;	/* alloc flags of a direct compactor */
+	const int classzone_idx;	/* zone index of a direct compactor */
 	enum migrate_mode mode;		/* Async or sync migration mode */
 	bool ignore_skip_hint;		/* Scan blocks even if marked skip */
 	bool ignore_block_suitable;	/* Scan blocks considered unsuitable */
 	bool direct_compaction;		/* False from kcompactd or /proc/... */
 	bool whole_zone;		/* Whole zone should/has been scanned */
-	int order;			/* order a direct compactor needs */
-	const gfp_t gfp_mask;		/* gfp mask of a direct compactor */
-	const unsigned int alloc_flags;	/* alloc flags of a direct compactor */
-	const int classzone_idx;	/* zone index of a direct compactor */
-	struct zone *zone;
 	bool contended;			/* Signal lock or sched contention */
 };
 
-- 
2.11.0

[toc] | [prev] | [next] | [standalone]

#1579600 — Re: [PATCH v2 01/10] mm, compaction: reorder fields in struct compact_control

On Fri, Feb 10, 2017 at 06:23:34PM +0100, Vlastimil Babka wrote:
> While currently there are (mostly by accident) no holes in struct
> compact_control (on x86_64), but we are going to add more bool flags, so place
> them all together to the end of the structure. While at it, just order all
> fields from largest to smallest.
> 
> Signed-off-by: Vlastimil Babka <vbabka@suse.cz>

Acked-by: Mel Gorman <mgorman@techsingularity.net>

-- 
Mel Gorman
SUSE Labs

[toc] | [prev] | [next] | [standalone]

#1578735 — [PATCH v2 06/10] mm, compaction: add migratetype to compact_control

Preparation patch. We are going to need migratetype at lower layers than
compact_zone() and compact_finished().

Signed-off-by: Vlastimil Babka <vbabka@suse.cz>
---
 mm/compaction.c | 15 +++++++--------
 mm/internal.h   |  1 +
 2 files changed, 8 insertions(+), 8 deletions(-)

diff --git a/mm/compaction.c b/mm/compaction.c
index 6c477025c3da..b7094700712b 100644
--- a/mm/compaction.c
+++ b/mm/compaction.c
@@ -1290,10 +1290,11 @@ static inline bool is_via_compact_memory(int order)
 	return order == -1;
 }
 
-static enum compact_result __compact_finished(struct zone *zone, struct compact_control *cc,
-			    const int migratetype)
+static enum compact_result __compact_finished(struct zone *zone,
+						struct compact_control *cc)
 {
 	unsigned int order;
+	const int migratetype = cc->migratetype;
 
 	if (cc->contended || fatal_signal_pending(current))
 		return COMPACT_CONTENDED;
@@ -1349,12 +1350,11 @@ static enum compact_result __compact_finished(struct zone *zone, struct compact_
 }
 
 static enum compact_result compact_finished(struct zone *zone,
-			struct compact_control *cc,
-			const int migratetype)
+			struct compact_control *cc)
 {
 	int ret;
 
-	ret = __compact_finished(zone, cc, migratetype);
+	ret = __compact_finished(zone, cc);
 	trace_mm_compaction_finished(zone, cc->order, ret);
 	if (ret == COMPACT_NO_SUITABLE_PAGE)
 		ret = COMPACT_CONTINUE;
@@ -1487,9 +1487,9 @@ static enum compact_result compact_zone(struct zone *zone, struct compact_contro
 	enum compact_result ret;
 	unsigned long start_pfn = zone->zone_start_pfn;
 	unsigned long end_pfn = zone_end_pfn(zone);
-	const int migratetype = gfpflags_to_migratetype(cc->gfp_mask);
 	const bool sync = cc->mode != MIGRATE_ASYNC;
 
+	cc->migratetype = gfpflags_to_migratetype(cc->gfp_mask);
 	ret = compaction_suitable(zone, cc->order, cc->alloc_flags,
 							cc->classzone_idx);
 	/* Compaction is likely to fail */
@@ -1539,8 +1539,7 @@ static enum compact_result compact_zone(struct zone *zone, struct compact_contro
 
 	migrate_prep_local();
 
-	while ((ret = compact_finished(zone, cc, migratetype)) ==
-						COMPACT_CONTINUE) {
+	while ((ret = compact_finished(zone, cc)) == COMPACT_CONTINUE) {
 		int err;
 
 		switch (isolate_migratepages(zone, cc)) {
diff --git a/mm/internal.h b/mm/internal.h
index da37ddd3db40..888f33cc7641 100644
--- a/mm/internal.h
+++ b/mm/internal.h
@@ -179,6 +179,7 @@ struct compact_control {
 	unsigned long last_migrated_pfn;/* Not yet flushed page being freed */
 	const gfp_t gfp_mask;		/* gfp mask of a direct compactor */
 	int order;			/* order a direct compactor needs */
+	int migratetype;		/* migratetype of direct compactor */
 	const unsigned int alloc_flags;	/* alloc flags of a direct compactor */
 	const int classzone_idx;	/* zone index of a direct compactor */
 	enum migrate_mode mode;		/* Async or sync migration mode */
-- 
2.11.0

[toc] | [prev] | [next] | [standalone]

#1579615 — Re: [PATCH v2 06/10] mm, compaction: add migratetype to compact_control

On Fri, Feb 10, 2017 at 06:23:39PM +0100, Vlastimil Babka wrote:
> Preparation patch. We are going to need migratetype at lower layers than
> compact_zone() and compact_finished().
> 
> Signed-off-by: Vlastimil Babka <vbabka@suse.cz>

Acked-by: Mel Gorman <mgorman@techsingularity.net>

-- 
Mel Gorman
SUSE Labs

[toc] | [prev] | [next] | [standalone]

#1578736 — [PATCH v2 02/10] mm, compaction: remove redundant watermark check in compact_finished()

When detecting whether compaction has succeeded in forming a high-order page,
__compact_finished() employs a watermark check, followed by an own search for
a suitable page in the freelists. This is not ideal for two reasons:

- The watermark check also searches high-order freelists, but has a less strict
  criteria wrt fallback. It's therefore redundant and waste of cycles. This was
  different in the past when high-order watermark check attempted to apply
  reserves to high-order pages.

- The watermark check might actually fail due to lack of order-0 pages.
  Compaction can't help with that, so there's no point in continuing because of
  that. It's possible that high-order page still exists and it terminates.

This patch therefore removes the watermark check. This should save some cycles
and terminate compaction sooner in some cases.

Signed-off-by: Vlastimil Babka <vbabka@suse.cz>
---
 mm/compaction.c | 8 --------
 1 file changed, 8 deletions(-)

diff --git a/mm/compaction.c b/mm/compaction.c
index 0409a4ad6ea1..fc88e7b6fe37 100644
--- a/mm/compaction.c
+++ b/mm/compaction.c
@@ -1291,7 +1291,6 @@ static enum compact_result __compact_finished(struct zone *zone, struct compact_
 			    const int migratetype)
 {
 	unsigned int order;
-	unsigned long watermark;
 
 	if (cc->contended || fatal_signal_pending(current))
 		return COMPACT_CONTENDED;
@@ -1319,13 +1318,6 @@ static enum compact_result __compact_finished(struct zone *zone, struct compact_
 	if (is_via_compact_memory(cc->order))
 		return COMPACT_CONTINUE;
 
-	/* Compaction run is not finished if the watermark is not met */
-	watermark = zone->watermark[cc->alloc_flags & ALLOC_WMARK_MASK];
-
-	if (!zone_watermark_ok(zone, cc->order, watermark, cc->classzone_idx,
-							cc->alloc_flags))
-		return COMPACT_CONTINUE;
-
 	/* Direct compactor: Is a suitable page free? */
 	for (order = cc->order; order < MAX_ORDER; order++) {
 		struct free_area *area = &zone->free_area[order];
-- 
2.11.0

[toc] | [prev] | [next] | [standalone]

#1579598 — Re: [PATCH v2 02/10] mm, compaction: remove redundant watermark check in compact_finished()

On Fri, Feb 10, 2017 at 06:23:35PM +0100, Vlastimil Babka wrote:
> When detecting whether compaction has succeeded in forming a high-order page,
> __compact_finished() employs a watermark check, followed by an own search for
> a suitable page in the freelists. This is not ideal for two reasons:
> 
> - The watermark check also searches high-order freelists, but has a less strict
>   criteria wrt fallback. It's therefore redundant and waste of cycles. This was
>   different in the past when high-order watermark check attempted to apply
>   reserves to high-order pages.
> 
> - The watermark check might actually fail due to lack of order-0 pages.
>   Compaction can't help with that, so there's no point in continuing because of
>   that. It's possible that high-order page still exists and it terminates.
> 
> This patch therefore removes the watermark check. This should save some cycles
> and terminate compaction sooner in some cases.
> 
> Signed-off-by: Vlastimil Babka <vbabka@suse.cz>

Acked-by: Mel Gorman <mgorman@techsingularity.net>

-- 
Mel Gorman
SUSE Labs

[toc] | [prev] | [next] | [standalone]

#1579626

On Fri, Feb 10, 2017 at 06:23:33PM +0100, Vlastimil Babka wrote:
> Hi,
> 
> this is a v2 of [1] from last year, which was a response to Johanes' worries
> about mobility grouping regressions. There are some new patches and the order
> goes from cleanups to "obvious wins" towards "just RFC" (last two patches).
> But it's all theoretical for now, I'm trying to run some tests with the usual
> problem of not having good workloads and metrics :) But I'd like to hear some
> feedback anyway. For now this is based on v4.9.
> 
> I think the only substantial new patch is 08/10, the rest is some cleanups,
> small tweaks and bugfixes.
> 

By and large, I like the series, particularly patches 7 and 8. I cannot
make up my mind about the RFC patches 9 and 10 yet. Conceptually they
seem sound but they are much more far reaching than the rest of the
series.

It would be nice if patches 1-8 could be treated in isolation with data
on the number of extfrag events triggered, time spent in compaction and
the success rate. Patches 9 and 10 are tricy enough that they would need
data per patch where as patches 1-8 should be ok with data gathered for
the whole series.

-- 
Mel Gorman
SUSE Labs

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web