[PATCH v4 1/3] mm/cma: change fallback behaviour for CMA freepage

[PATCH v4 1/3] mm/cma: change fallback behaviour for CMA freepage

[Joonsoo Kim]

Freepage with MIGRATE_CMA can be used only for MIGRATE_MOVABLE and
they should not be expanded to other migratetype buddy list
to protect them from unmovable/reclaimable allocation. Implementing
these requirements in __rmqueue_fallback(), that is, finding largest
possible block of freepage has bad effect that high order freepage
with MIGRATE_CMA are broken continually although there are suitable
order CMA freepage. Reason is that they are not be expanded to other
migratetype buddy list and next __rmqueue_fallback() invocation try to
finds another largest block of freepage and break it again. So,
MIGRATE_CMA fallback should be handled separately. This patch
introduces __rmqueue_cma_fallback(), that just wrapper of
__rmqueue_smallest() and call it before __rmqueue_fallback()
if migratetype == MIGRATE_MOVABLE.

This results in unintended behaviour change that MIGRATE_CMA freepage
is always used first rather than other migratetype as movable
allocation's fallback. But, as already mentioned above,
MIGRATE_CMA can be used only for MIGRATE_MOVABLE, so it is better
to use MIGRATE_CMA freepage first as much as possible. Otherwise,
we needlessly take up precious freepages with other migratetype and
increase chance of fragmentation.

Acked-by: Vlastimil Babka <vbabka@suse.cz>
Signed-off-by: Joonsoo Kim <iamjoonsoo.kim@lge.com>
---
 mm/page_alloc.c |   36 +++++++++++++++++++-----------------
 1 file changed, 19 insertions(+), 17 deletions(-)

diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index 8d52ab1..e64b260 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c
@@ -1029,11 +1029,9 @@ struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
 static int fallbacks[MIGRATE_TYPES][4] = {
 	[MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,     MIGRATE_RESERVE },
 	[MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,     MIGRATE_RESERVE },
+	[MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE,   MIGRATE_RESERVE },
 #ifdef CONFIG_CMA
-	[MIGRATE_MOVABLE]     = { MIGRATE_CMA,         MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },
 	[MIGRATE_CMA]         = { MIGRATE_RESERVE }, /* Never used */
-#else
-	[MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE,   MIGRATE_RESERVE },
 #endif
 	[MIGRATE_RESERVE]     = { MIGRATE_RESERVE }, /* Never used */
 #ifdef CONFIG_MEMORY_ISOLATION
@@ -1041,6 +1039,17 @@ static int fallbacks[MIGRATE_TYPES][4] = {
 #endif
 };
 
+#ifdef CONFIG_CMA
+static struct page *__rmqueue_cma_fallback(struct zone *zone,
+					unsigned int order)
+{
+	return __rmqueue_smallest(zone, order, MIGRATE_CMA);
+}
+#else
+static inline struct page *__rmqueue_cma_fallback(struct zone *zone,
+					unsigned int order) { return NULL; }
+#endif
+
 /*
  * Move the free pages in a range to the free lists of the requested type.
  * Note that start_page and end_pages are not aligned on a pageblock
@@ -1192,19 +1201,8 @@ __rmqueue_fallback(struct zone *zone, unsigned int order, int start_migratetype)
 					struct page, lru);
 			area->nr_free--;
 
-			if (!is_migrate_cma(migratetype)) {
-				try_to_steal_freepages(zone, page,
-							start_migratetype,
-							migratetype);
-			} else {
-				/*
-				 * When borrowing from MIGRATE_CMA, we need to
-				 * release the excess buddy pages to CMA
-				 * itself, and we do not try to steal extra
-				 * free pages.
-				 */
-				buddy_type = migratetype;
-			}
+			try_to_steal_freepages(zone, page, start_migratetype,
+								migratetype);
 
 			/* Remove the page from the freelists */
 			list_del(&page->lru);
@@ -1246,7 +1244,11 @@ retry_reserve:
 	page = __rmqueue_smallest(zone, order, migratetype);
 
 	if (unlikely(!page) && migratetype != MIGRATE_RESERVE) {
-		page = __rmqueue_fallback(zone, order, migratetype);
+		if (migratetype == MIGRATE_MOVABLE)
+			page = __rmqueue_cma_fallback(zone, order);
+
+		if (!page)
+			page = __rmqueue_fallback(zone, order, migratetype);
 
 		/*
 		 * Use MIGRATE_RESERVE rather than fail an allocation. goto
-- 
1.7.9.5

[PATCH v4 2/3] mm/page_alloc: factor out fallback freepage checking

[Joonsoo Kim]

This is preparation step to use page allocator's anti fragmentation logic
in compaction. This patch just separates fallback freepage checking part
from fallback freepage management part. Therefore, there is no functional
change.

Signed-off-by: Joonsoo Kim <iamjoonsoo.kim@lge.com>
---
 mm/page_alloc.c |  143 +++++++++++++++++++++++++++++++++++--------------------
 1 file changed, 91 insertions(+), 52 deletions(-)

diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index e64b260..64a4974 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c
@@ -1142,14 +1142,40 @@ static void change_pageblock_range(struct page *pageblock_page,
  * as fragmentation caused by those allocations polluting movable pageblocks
  * is worse than movable allocations stealing from unmovable and reclaimable
  * pageblocks.
- *
- * If we claim more than half of the pageblock, change pageblock's migratetype
- * as well.
  */
-static void try_to_steal_freepages(struct zone *zone, struct page *page,
-				  int start_type, int fallback_type)
+static bool can_steal_fallback(unsigned int order, int start_mt)
+{
+	/*
+	 * Leaving this order check is intended, although there is
+	 * relaxed order check in next check. The reason is that
+	 * we can actually steal whole pageblock if this condition met,
+	 * but, below check doesn't guarantee it and that is just heuristic
+	 * so could be changed anytime.
+	 */
+	if (order >= pageblock_order)
+		return true;
+
+	if (order >= pageblock_order / 2 ||
+		start_mt == MIGRATE_RECLAIMABLE ||
+		start_mt == MIGRATE_UNMOVABLE ||
+		page_group_by_mobility_disabled)
+		return true;
+
+	return false;
+}
+
+/*
+ * This function implements actual steal behaviour. If order is large enough,
+ * we can steal whole pageblock. If not, we first move freepages in this
+ * pageblock and check whether half of pages are moved or not. If half of
+ * pages are moved, we can change migratetype of pageblock and permanently
+ * 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 current_order = page_order(page);
+	int pages;
 
 	/* Take ownership for orders >= pageblock_order */
 	if (current_order >= pageblock_order) {
@@ -1157,19 +1183,40 @@ static void try_to_steal_freepages(struct zone *zone, struct page *page,
 		return;
 	}
 
-	if (current_order >= pageblock_order / 2 ||
-	    start_type == MIGRATE_RECLAIMABLE ||
-	    start_type == MIGRATE_UNMOVABLE ||
-	    page_group_by_mobility_disabled) {
-		int pages;
+	pages = move_freepages_block(zone, page, start_type);
+
+	/* Claim the whole block if over half of it is free */
+	if (pages >= (1 << (pageblock_order-1)) ||
+			page_group_by_mobility_disabled)
+		set_pageblock_migratetype(page, start_type);
+}
+
+/* Check whether there is a suitable fallback freepage with requested order. */
+static int find_suitable_fallback(struct free_area *area, unsigned int order,
+					int migratetype, bool *can_steal)
+{
+	int i;
+	int fallback_mt;
+
+	if (area->nr_free == 0)
+		return -1;
+
+	*can_steal = false;
+	for (i = 0;; i++) {
+		fallback_mt = fallbacks[migratetype][i];
+		if (fallback_mt == MIGRATE_RESERVE)
+			break;
+
+		if (list_empty(&area->free_list[fallback_mt]))
+			continue;
 
-		pages = move_freepages_block(zone, page, start_type);
+		if (can_steal_fallback(order, migratetype))
+			*can_steal = true;
 
-		/* Claim the whole block if over half of it is free */
-		if (pages >= (1 << (pageblock_order-1)) ||
-				page_group_by_mobility_disabled)
-			set_pageblock_migratetype(page, start_type);
+		return fallback_mt;
 	}
+
+	return -1;
 }
 
 /* Remove an element from the buddy allocator from the fallback list */
@@ -1179,53 +1226,45 @@ __rmqueue_fallback(struct zone *zone, unsigned int order, int start_migratetype)
 	struct free_area *area;
 	unsigned int current_order;
 	struct page *page;
+	int fallback_mt;
+	bool can_steal;
 
 	/* Find the largest possible block of pages in the other list */
 	for (current_order = MAX_ORDER-1;
 				current_order >= order && current_order <= MAX_ORDER-1;
 				--current_order) {
-		int i;
-		for (i = 0;; i++) {
-			int migratetype = fallbacks[start_migratetype][i];
-			int buddy_type = start_migratetype;
-
-			/* MIGRATE_RESERVE handled later if necessary */
-			if (migratetype == MIGRATE_RESERVE)
-				break;
-
-			area = &(zone->free_area[current_order]);
-			if (list_empty(&area->free_list[migratetype]))
-				continue;
-
-			page = list_entry(area->free_list[migratetype].next,
-					struct page, lru);
-			area->nr_free--;
-
-			try_to_steal_freepages(zone, page, start_migratetype,
-								migratetype);
+		area = &(zone->free_area[current_order]);
+		fallback_mt = find_suitable_fallback(area, current_order,
+				start_migratetype, &can_steal);
+		if (fallback_mt == -1)
+			continue;
 
-			/* Remove the page from the freelists */
-			list_del(&page->lru);
-			rmv_page_order(page);
+		page = list_entry(area->free_list[fallback_mt].next,
+						struct page, lru);
+		if (can_steal)
+			steal_suitable_fallback(zone, page, start_migratetype);
 
-			expand(zone, page, order, current_order, area,
-					buddy_type);
+		/* Remove the page from the freelists */
+		area->nr_free--;
+		list_del(&page->lru);
+		rmv_page_order(page);
 
-			/*
-			 * The freepage_migratetype may differ from pageblock's
-			 * migratetype depending on the decisions in
-			 * try_to_steal_freepages(). This is OK as long as it
-			 * does not differ for MIGRATE_CMA pageblocks. For CMA
-			 * we need to make sure unallocated pages flushed from
-			 * pcp lists are returned to the correct freelist.
-			 */
-			set_freepage_migratetype(page, buddy_type);
+		expand(zone, page, order, current_order, area,
+					start_migratetype);
+		/*
+		 * The freepage_migratetype may differ from pageblock's
+		 * migratetype depending on the decisions in
+		 * try_to_steal_freepages(). This is OK as long as it
+		 * does not differ for MIGRATE_CMA pageblocks. For CMA
+		 * we need to make sure unallocated pages flushed from
+		 * pcp lists are returned to the correct freelist.
+		 */
+		set_freepage_migratetype(page, start_migratetype);
 
-			trace_mm_page_alloc_extfrag(page, order, current_order,
-				start_migratetype, migratetype);
+		trace_mm_page_alloc_extfrag(page, order, current_order,
+			start_migratetype, fallback_mt);
 
-			return page;
-		}
+		return page;
 	}
 
 	return NULL;
-- 
1.7.9.5

[PATCH v4 3/3] mm/compaction: enhance compaction finish condition

[Joonsoo Kim]

Compaction has anti fragmentation algorithm. It is that freepage
should be more than pageblock order to finish the compaction if we don't
find any freepage in requested migratetype buddy list. This is for
mitigating fragmentation, but, there is a lack of migratetype
consideration and it is too excessive compared to page allocator's anti
fragmentation algorithm.

Not considering migratetype would cause premature finish of compaction.
For example, if allocation request is for unmovable migratetype,
freepage with CMA migratetype doesn't help that allocation and
compaction should not be stopped. But, current logic regards this
situation as compaction is no longer needed, so finish the compaction.

Secondly, condition is too excessive compared to page allocator's logic.
We can steal freepage from other migratetype and change pageblock
migratetype on more relaxed conditions in page allocator. This is designed
to prevent fragmentation and we can use it here. Imposing hard constraint
only to the compaction doesn't help much in this case since page allocator
would cause fragmentation again.

To solve these problems, this patch borrows anti fragmentation logic from
page allocator. It will reduce premature compaction finish in some cases
and reduce excessive compaction work.

stress-highalloc test in mmtests with non movable order 7 allocation shows
considerable increase of compaction success rate.

Compaction success rate (Compaction success * 100 / Compaction stalls, %)
31.82 : 42.20

I tested it on non-reboot 5 runs stress-highalloc benchmark and found that
there is no more degradation on allocation success rate than before. That
roughly means that this patch doesn't result in more fragmentations.

Vlastimil suggests additional idea that we only test for fallbacks
when migration scanner has scanned a whole pageblock. It looked good for
fragmentation because chance of stealing increase due to making more
free pages in certain pageblock. So, I tested it, but, it results in
decreased compaction success rate, roughly 38.00. I guess the reason that
if system is low memory condition, watermark check could be failed due to
not enough order 0 free page and so, sometimes, we can't reach a fallback
check although migrate_pfn is aligned to pageblock_nr_pages. I can insert
code to cope with this situation but it makes code more complicated so
I don't include his idea at this patch.

Signed-off-by: Joonsoo Kim <iamjoonsoo.kim@lge.com>
---
 mm/compaction.c |   14 ++++++++++++--
 mm/internal.h   |    2 ++
 mm/page_alloc.c |   19 ++++++++++++++-----
 3 files changed, 28 insertions(+), 7 deletions(-)

diff --git a/mm/compaction.c b/mm/compaction.c
index 782772d..d40c426 100644
--- a/mm/compaction.c
+++ b/mm/compaction.c
@@ -1170,13 +1170,23 @@ static int __compact_finished(struct zone *zone, struct compact_control *cc,
 	/* Direct compactor: Is a suitable page free? */
 	for (order = cc->order; order < MAX_ORDER; order++) {
 		struct free_area *area = &zone->free_area[order];
+		bool can_steal;
 
 		/* Job done if page is free of the right migratetype */
 		if (!list_empty(&area->free_list[migratetype]))
 			return COMPACT_PARTIAL;
 
-		/* Job done if allocation would set block type */
-		if (order >= pageblock_order && area->nr_free)
+		/* MIGRATE_MOVABLE can fallback on MIGRATE_CMA */
+		if (migratetype == MIGRATE_MOVABLE &&
+			!list_empty(&area->free_list[MIGRATE_CMA]))
+			return COMPACT_PARTIAL;
+
+		/*
+		 * Job done if allocation would steal freepages from
+		 * other migratetype buddy lists.
+		 */
+		if (find_suitable_fallback(area, order, migratetype,
+						true, &can_steal) != -1)
 			return COMPACT_PARTIAL;
 	}
 
diff --git a/mm/internal.h b/mm/internal.h
index c4d6c9b..9640650 100644
--- a/mm/internal.h
+++ b/mm/internal.h
@@ -200,6 +200,8 @@ isolate_freepages_range(struct compact_control *cc,
 unsigned long
 isolate_migratepages_range(struct compact_control *cc,
 			   unsigned long low_pfn, unsigned long end_pfn);
+int find_suitable_fallback(struct free_area *area, unsigned int order,
+			int migratetype, bool only_stealable, bool *can_steal);
 
 #endif
 
diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index 64a4974..95654f9 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c
@@ -1191,9 +1191,14 @@ static void steal_suitable_fallback(struct zone *zone, struct page *page,
 		set_pageblock_migratetype(page, start_type);
 }
 
-/* Check whether there is a suitable fallback freepage with requested order. */
-static int find_suitable_fallback(struct free_area *area, unsigned int order,
-					int migratetype, bool *can_steal)
+/*
+ * Check whether there is a suitable fallback freepage with requested order.
+ * If only_stealable is true, this function returns fallback_mt only if
+ * we can steal other freepages all together. This would help to reduce
+ * fragmentation due to mixed migratetype pages in one pageblock.
+ */
+int find_suitable_fallback(struct free_area *area, unsigned int order,
+			int migratetype, bool only_stealable, bool *can_steal)
 {
 	int i;
 	int fallback_mt;
@@ -1213,7 +1218,11 @@ static int find_suitable_fallback(struct free_area *area, unsigned int order,
 		if (can_steal_fallback(order, migratetype))
 			*can_steal = true;
 
-		return fallback_mt;
+		if (!only_stealable)
+			return fallback_mt;
+
+		if (*can_steal)
+			return fallback_mt;
 	}
 
 	return -1;
@@ -1235,7 +1244,7 @@ __rmqueue_fallback(struct zone *zone, unsigned int order, int start_migratetype)
 				--current_order) {
 		area = &(zone->free_area[current_order]);
 		fallback_mt = find_suitable_fallback(area, current_order,
-				start_migratetype, &can_steal);
+				start_migratetype, false, &can_steal);
 		if (fallback_mt == -1)
 			continue;
 
-- 
1.7.9.5

Re: [PATCH v4 2/3] mm/page_alloc: factor out fallback freepage checking

[Vlastimil Babka]

On 02/12/2015 08:15 AM, Joonsoo Kim wrote:
> This is preparation step to use page allocator's anti fragmentation logic
> in compaction. This patch just separates fallback freepage checking part
> from fallback freepage management part. Therefore, there is no functional
> change.
>
> Signed-off-by: Joonsoo Kim <iamjoonsoo.kim@lge.com>

Acked-by: Vlastimil Babka <vbabka@suse.cz>

> ---
>   mm/page_alloc.c |  143 +++++++++++++++++++++++++++++++++++--------------------
>   1 file changed, 91 insertions(+), 52 deletions(-)
>
> diff --git a/mm/page_alloc.c b/mm/page_alloc.c
> index e64b260..64a4974 100644
> --- a/mm/page_alloc.c
> +++ b/mm/page_alloc.c
> @@ -1142,14 +1142,40 @@ static void change_pageblock_range(struct page *pageblock_page,
>    * as fragmentation caused by those allocations polluting movable pageblocks
>    * is worse than movable allocations stealing from unmovable and reclaimable
>    * pageblocks.
> - *
> - * If we claim more than half of the pageblock, change pageblock's migratetype
> - * as well.
>    */
> -static void try_to_steal_freepages(struct zone *zone, struct page *page,
> -				  int start_type, int fallback_type)
> +static bool can_steal_fallback(unsigned int order, int start_mt)
> +{
> +	/*
> +	 * Leaving this order check is intended, although there is
> +	 * relaxed order check in next check. The reason is that
> +	 * we can actually steal whole pageblock if this condition met,
> +	 * but, below check doesn't guarantee it and that is just heuristic
> +	 * so could be changed anytime.
> +	 */
> +	if (order >= pageblock_order)
> +		return true;
> +
> +	if (order >= pageblock_order / 2 ||
> +		start_mt == MIGRATE_RECLAIMABLE ||
> +		start_mt == MIGRATE_UNMOVABLE ||
> +		page_group_by_mobility_disabled)
> +		return true;
> +
> +	return false;
> +}
> +
> +/*
> + * This function implements actual steal behaviour. If order is large enough,
> + * we can steal whole pageblock. If not, we first move freepages in this
> + * pageblock and check whether half of pages are moved or not. If half of
> + * pages are moved, we can change migratetype of pageblock and permanently
> + * 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 current_order = page_order(page);
> +	int pages;
>
>   	/* Take ownership for orders >= pageblock_order */
>   	if (current_order >= pageblock_order) {
> @@ -1157,19 +1183,40 @@ static void try_to_steal_freepages(struct zone *zone, struct page *page,
>   		return;
>   	}
>
> -	if (current_order >= pageblock_order / 2 ||
> -	    start_type == MIGRATE_RECLAIMABLE ||
> -	    start_type == MIGRATE_UNMOVABLE ||
> -	    page_group_by_mobility_disabled) {
> -		int pages;
> +	pages = move_freepages_block(zone, page, start_type);
> +
> +	/* Claim the whole block if over half of it is free */
> +	if (pages >= (1 << (pageblock_order-1)) ||
> +			page_group_by_mobility_disabled)
> +		set_pageblock_migratetype(page, start_type);
> +}
> +
> +/* Check whether there is a suitable fallback freepage with requested order. */
> +static int find_suitable_fallback(struct free_area *area, unsigned int order,
> +					int migratetype, bool *can_steal)
> +{
> +	int i;
> +	int fallback_mt;
> +
> +	if (area->nr_free == 0)
> +		return -1;
> +
> +	*can_steal = false;
> +	for (i = 0;; i++) {
> +		fallback_mt = fallbacks[migratetype][i];
> +		if (fallback_mt == MIGRATE_RESERVE)
> +			break;
> +
> +		if (list_empty(&area->free_list[fallback_mt]))
> +			continue;
>
> -		pages = move_freepages_block(zone, page, start_type);
> +		if (can_steal_fallback(order, migratetype))
> +			*can_steal = true;
>
> -		/* Claim the whole block if over half of it is free */
> -		if (pages >= (1 << (pageblock_order-1)) ||
> -				page_group_by_mobility_disabled)
> -			set_pageblock_migratetype(page, start_type);
> +		return fallback_mt;
>   	}
> +
> +	return -1;
>   }
>
>   /* Remove an element from the buddy allocator from the fallback list */
> @@ -1179,53 +1226,45 @@ __rmqueue_fallback(struct zone *zone, unsigned int order, int start_migratetype)
>   	struct free_area *area;
>   	unsigned int current_order;
>   	struct page *page;
> +	int fallback_mt;
> +	bool can_steal;
>
>   	/* Find the largest possible block of pages in the other list */
>   	for (current_order = MAX_ORDER-1;
>   				current_order >= order && current_order <= MAX_ORDER-1;
>   				--current_order) {
> -		int i;
> -		for (i = 0;; i++) {
> -			int migratetype = fallbacks[start_migratetype][i];
> -			int buddy_type = start_migratetype;
> -
> -			/* MIGRATE_RESERVE handled later if necessary */
> -			if (migratetype == MIGRATE_RESERVE)
> -				break;
> -
> -			area = &(zone->free_area[current_order]);
> -			if (list_empty(&area->free_list[migratetype]))
> -				continue;
> -
> -			page = list_entry(area->free_list[migratetype].next,
> -					struct page, lru);
> -			area->nr_free--;
> -
> -			try_to_steal_freepages(zone, page, start_migratetype,
> -								migratetype);
> +		area = &(zone->free_area[current_order]);
> +		fallback_mt = find_suitable_fallback(area, current_order,
> +				start_migratetype, &can_steal);
> +		if (fallback_mt == -1)
> +			continue;
>
> -			/* Remove the page from the freelists */
> -			list_del(&page->lru);
> -			rmv_page_order(page);
> +		page = list_entry(area->free_list[fallback_mt].next,
> +						struct page, lru);
> +		if (can_steal)
> +			steal_suitable_fallback(zone, page, start_migratetype);
>
> -			expand(zone, page, order, current_order, area,
> -					buddy_type);
> +		/* Remove the page from the freelists */
> +		area->nr_free--;
> +		list_del(&page->lru);
> +		rmv_page_order(page);
>
> -			/*
> -			 * The freepage_migratetype may differ from pageblock's
> -			 * migratetype depending on the decisions in
> -			 * try_to_steal_freepages(). This is OK as long as it
> -			 * does not differ for MIGRATE_CMA pageblocks. For CMA
> -			 * we need to make sure unallocated pages flushed from
> -			 * pcp lists are returned to the correct freelist.
> -			 */
> -			set_freepage_migratetype(page, buddy_type);
> +		expand(zone, page, order, current_order, area,
> +					start_migratetype);
> +		/*
> +		 * The freepage_migratetype may differ from pageblock's
> +		 * migratetype depending on the decisions in
> +		 * try_to_steal_freepages(). This is OK as long as it
> +		 * does not differ for MIGRATE_CMA pageblocks. For CMA
> +		 * we need to make sure unallocated pages flushed from
> +		 * pcp lists are returned to the correct freelist.
> +		 */
> +		set_freepage_migratetype(page, start_migratetype);
>
> -			trace_mm_page_alloc_extfrag(page, order, current_order,
> -				start_migratetype, migratetype);
> +		trace_mm_page_alloc_extfrag(page, order, current_order,
> +			start_migratetype, fallback_mt);
>
> -			return page;
> -		}
> +		return page;
>   	}
>
>   	return NULL;
>

Re: [PATCH v4 3/3] mm/compaction: enhance compaction finish condition

[Vlastimil Babka]

On 02/12/2015 08:15 AM, Joonsoo Kim wrote:
> Compaction has anti fragmentation algorithm. It is that freepage
> should be more than pageblock order to finish the compaction if we don't
> find any freepage in requested migratetype buddy list. This is for
> mitigating fragmentation, but, there is a lack of migratetype
> consideration and it is too excessive compared to page allocator's anti
> fragmentation algorithm.
>
> Not considering migratetype would cause premature finish of compaction.
> For example, if allocation request is for unmovable migratetype,
> freepage with CMA migratetype doesn't help that allocation and
> compaction should not be stopped. But, current logic regards this
> situation as compaction is no longer needed, so finish the compaction.
>
> Secondly, condition is too excessive compared to page allocator's logic.
> We can steal freepage from other migratetype and change pageblock
> migratetype on more relaxed conditions in page allocator. This is designed
> to prevent fragmentation and we can use it here. Imposing hard constraint
> only to the compaction doesn't help much in this case since page allocator
> would cause fragmentation again.
>
> To solve these problems, this patch borrows anti fragmentation logic from
> page allocator. It will reduce premature compaction finish in some cases
> and reduce excessive compaction work.
>
> stress-highalloc test in mmtests with non movable order 7 allocation shows
> considerable increase of compaction success rate.
>
> Compaction success rate (Compaction success * 100 / Compaction stalls, %)
> 31.82 : 42.20
>
> I tested it on non-reboot 5 runs stress-highalloc benchmark and found that
> there is no more degradation on allocation success rate than before. That
> roughly means that this patch doesn't result in more fragmentations.
>
> Vlastimil suggests additional idea that we only test for fallbacks
> when migration scanner has scanned a whole pageblock. It looked good for
> fragmentation because chance of stealing increase due to making more
> free pages in certain pageblock. So, I tested it, but, it results in
> decreased compaction success rate, roughly 38.00. I guess the reason that
> if system is low memory condition, watermark check could be failed due to
> not enough order 0 free page and so, sometimes, we can't reach a fallback
> check although migrate_pfn is aligned to pageblock_nr_pages. I can insert
> code to cope with this situation but it makes code more complicated so
> I don't include his idea at this patch.

Hm that's weird. I'll try to investigate this later. Meanwhile it can 
stay as it is.

> Signed-off-by: Joonsoo Kim <iamjoonsoo.kim@lge.com>

Acked-by: Vlastimil Babka <vbabka@suse.cz>

But you'll need to fix:

> ---
>   mm/compaction.c |   14 ++++++++++++--
>   mm/internal.h   |    2 ++
>   mm/page_alloc.c |   19 ++++++++++++++-----
>   3 files changed, 28 insertions(+), 7 deletions(-)
>
> diff --git a/mm/compaction.c b/mm/compaction.c
> index 782772d..d40c426 100644
> --- a/mm/compaction.c
> +++ b/mm/compaction.c
> @@ -1170,13 +1170,23 @@ static int __compact_finished(struct zone *zone, struct compact_control *cc,
>   	/* Direct compactor: Is a suitable page free? */
>   	for (order = cc->order; order < MAX_ORDER; order++) {
>   		struct free_area *area = &zone->free_area[order];
> +		bool can_steal;
>
>   		/* Job done if page is free of the right migratetype */
>   		if (!list_empty(&area->free_list[migratetype]))
>   			return COMPACT_PARTIAL;
>
> -		/* Job done if allocation would set block type */
> -		if (order >= pageblock_order && area->nr_free)
> +		/* MIGRATE_MOVABLE can fallback on MIGRATE_CMA */
> +		if (migratetype == MIGRATE_MOVABLE &&
> +			!list_empty(&area->free_list[MIGRATE_CMA]))

This won't compile with !CONFIG_CMA, right? I recall pointing it on v3 
already (or something similar elsewhere).

> +			return COMPACT_PARTIAL;
> +
> +		/*
> +		 * Job done if allocation would steal freepages from
> +		 * other migratetype buddy lists.
> +		 */
> +		if (find_suitable_fallback(area, order, migratetype,
> +						true, &can_steal) != -1)
>   			return COMPACT_PARTIAL;
>   	}
>
> diff --git a/mm/internal.h b/mm/internal.h
> index c4d6c9b..9640650 100644
> --- a/mm/internal.h
> +++ b/mm/internal.h
> @@ -200,6 +200,8 @@ isolate_freepages_range(struct compact_control *cc,
>   unsigned long
>   isolate_migratepages_range(struct compact_control *cc,
>   			   unsigned long low_pfn, unsigned long end_pfn);
> +int find_suitable_fallback(struct free_area *area, unsigned int order,
> +			int migratetype, bool only_stealable, bool *can_steal);
>
>   #endif
>
> diff --git a/mm/page_alloc.c b/mm/page_alloc.c
> index 64a4974..95654f9 100644
> --- a/mm/page_alloc.c
> +++ b/mm/page_alloc.c
> @@ -1191,9 +1191,14 @@ static void steal_suitable_fallback(struct zone *zone, struct page *page,
>   		set_pageblock_migratetype(page, start_type);
>   }
>
> -/* Check whether there is a suitable fallback freepage with requested order. */
> -static int find_suitable_fallback(struct free_area *area, unsigned int order,
> -					int migratetype, bool *can_steal)
> +/*
> + * Check whether there is a suitable fallback freepage with requested order.
> + * If only_stealable is true, this function returns fallback_mt only if
> + * we can steal other freepages all together. This would help to reduce
> + * fragmentation due to mixed migratetype pages in one pageblock.
> + */
> +int find_suitable_fallback(struct free_area *area, unsigned int order,
> +			int migratetype, bool only_stealable, bool *can_steal)
>   {
>   	int i;
>   	int fallback_mt;
> @@ -1213,7 +1218,11 @@ static int find_suitable_fallback(struct free_area *area, unsigned int order,
>   		if (can_steal_fallback(order, migratetype))
>   			*can_steal = true;
>
> -		return fallback_mt;
> +		if (!only_stealable)
> +			return fallback_mt;
> +
> +		if (*can_steal)
> +			return fallback_mt;

Why not just single if (!only_stealable || *can_steal)

>   	}
>
>   	return -1;
> @@ -1235,7 +1244,7 @@ __rmqueue_fallback(struct zone *zone, unsigned int order, int start_migratetype)
>   				--current_order) {
>   		area = &(zone->free_area[current_order]);
>   		fallback_mt = find_suitable_fallback(area, current_order,
> -				start_migratetype, &can_steal);
> +				start_migratetype, false, &can_steal);
>   		if (fallback_mt == -1)
>   			continue;
>
>

Re: [PATCH v4 3/3] mm/compaction: enhance compaction finish condition

[Andrew Morton]

On Thu, 12 Feb 2015 16:15:05 +0900 Joonsoo Kim <iamjoonsoo.kim@lge.com> wrote:

> Compaction has anti fragmentation algorithm. It is that freepage
> should be more than pageblock order to finish the compaction if we don't
> find any freepage in requested migratetype buddy list. This is for
> mitigating fragmentation, but, there is a lack of migratetype
> consideration and it is too excessive compared to page allocator's anti
> fragmentation algorithm.
> 
> Not considering migratetype would cause premature finish of compaction.
> For example, if allocation request is for unmovable migratetype,
> freepage with CMA migratetype doesn't help that allocation and
> compaction should not be stopped. But, current logic regards this
> situation as compaction is no longer needed, so finish the compaction.
> 
> Secondly, condition is too excessive compared to page allocator's logic.
> We can steal freepage from other migratetype and change pageblock
> migratetype on more relaxed conditions in page allocator. This is designed
> to prevent fragmentation and we can use it here. Imposing hard constraint
> only to the compaction doesn't help much in this case since page allocator
> would cause fragmentation again.
> 
> To solve these problems, this patch borrows anti fragmentation logic from
> page allocator. It will reduce premature compaction finish in some cases
> and reduce excessive compaction work.
> 
> stress-highalloc test in mmtests with non movable order 7 allocation shows
> considerable increase of compaction success rate.
> 
> Compaction success rate (Compaction success * 100 / Compaction stalls, %)
> 31.82 : 42.20
> 
> I tested it on non-reboot 5 runs stress-highalloc benchmark and found that
> there is no more degradation on allocation success rate than before. That
> roughly means that this patch doesn't result in more fragmentations.
> 
> Vlastimil suggests additional idea that we only test for fallbacks
> when migration scanner has scanned a whole pageblock. It looked good for
> fragmentation because chance of stealing increase due to making more
> free pages in certain pageblock. So, I tested it, but, it results in
> decreased compaction success rate, roughly 38.00. I guess the reason that
> if system is low memory condition, watermark check could be failed due to
> not enough order 0 free page and so, sometimes, we can't reach a fallback
> check although migrate_pfn is aligned to pageblock_nr_pages. I can insert
> code to cope with this situation but it makes code more complicated so
> I don't include his idea at this patch.
> 
> ...
>
> --- a/mm/compaction.c
> +++ b/mm/compaction.c
> @@ -1170,13 +1170,23 @@ static int __compact_finished(struct zone *zone, struct compact_control *cc,
>  	/* Direct compactor: Is a suitable page free? */
>  	for (order = cc->order; order < MAX_ORDER; order++) {
>  		struct free_area *area = &zone->free_area[order];
> +		bool can_steal;
>  
>  		/* Job done if page is free of the right migratetype */
>  		if (!list_empty(&area->free_list[migratetype]))
>  			return COMPACT_PARTIAL;
>  
> -		/* Job done if allocation would set block type */
> -		if (order >= pageblock_order && area->nr_free)
> +		/* MIGRATE_MOVABLE can fallback on MIGRATE_CMA */
> +		if (migratetype == MIGRATE_MOVABLE &&
> +			!list_empty(&area->free_list[MIGRATE_CMA]))
> +			return COMPACT_PARTIAL;

MIGRATE_CMA isn't defined if CONFIG_CMA=n.

--- a/mm/compaction.c~mm-compaction-enhance-compaction-finish-condition-fix
+++ a/mm/compaction.c
@@ -1180,11 +1180,12 @@ static int __compact_finished(struct zon
 		if (!list_empty(&area->free_list[migratetype]))
 			return COMPACT_PARTIAL;
 
+#ifdef CONFIG_CMA
 		/* MIGRATE_MOVABLE can fallback on MIGRATE_CMA */
 		if (migratetype == MIGRATE_MOVABLE &&
 			!list_empty(&area->free_list[MIGRATE_CMA]))
 			return COMPACT_PARTIAL;
-
+#endif
 		/*
 		 * Job done if allocation would steal freepages from
 		 * other migratetype buddy lists.

Please review the rest of the patchset for the CONFIG_CMA=n case (is it
all necessary?), runtime test it and let me know?

Re: [PATCH v4 3/3] mm/compaction: enhance compaction finish condition

[Joonsoo Kim]

On Tue, Feb 17, 2015 at 10:46:04AM +0100, Vlastimil Babka wrote:
> On 02/12/2015 08:15 AM, Joonsoo Kim wrote:
> >Compaction has anti fragmentation algorithm. It is that freepage
> >should be more than pageblock order to finish the compaction if we don't
> >find any freepage in requested migratetype buddy list. This is for
> >mitigating fragmentation, but, there is a lack of migratetype
> >consideration and it is too excessive compared to page allocator's anti
> >fragmentation algorithm.
> >
> >Not considering migratetype would cause premature finish of compaction.
> >For example, if allocation request is for unmovable migratetype,
> >freepage with CMA migratetype doesn't help that allocation and
> >compaction should not be stopped. But, current logic regards this
> >situation as compaction is no longer needed, so finish the compaction.
> >
> >Secondly, condition is too excessive compared to page allocator's logic.
> >We can steal freepage from other migratetype and change pageblock
> >migratetype on more relaxed conditions in page allocator. This is designed
> >to prevent fragmentation and we can use it here. Imposing hard constraint
> >only to the compaction doesn't help much in this case since page allocator
> >would cause fragmentation again.
> >
> >To solve these problems, this patch borrows anti fragmentation logic from
> >page allocator. It will reduce premature compaction finish in some cases
> >and reduce excessive compaction work.
> >
> >stress-highalloc test in mmtests with non movable order 7 allocation shows
> >considerable increase of compaction success rate.
> >
> >Compaction success rate (Compaction success * 100 / Compaction stalls, %)
> >31.82 : 42.20
> >
> >I tested it on non-reboot 5 runs stress-highalloc benchmark and found that
> >there is no more degradation on allocation success rate than before. That
> >roughly means that this patch doesn't result in more fragmentations.
> >
> >Vlastimil suggests additional idea that we only test for fallbacks
> >when migration scanner has scanned a whole pageblock. It looked good for
> >fragmentation because chance of stealing increase due to making more
> >free pages in certain pageblock. So, I tested it, but, it results in
> >decreased compaction success rate, roughly 38.00. I guess the reason that
> >if system is low memory condition, watermark check could be failed due to
> >not enough order 0 free page and so, sometimes, we can't reach a fallback
> >check although migrate_pfn is aligned to pageblock_nr_pages. I can insert
> >code to cope with this situation but it makes code more complicated so
> >I don't include his idea at this patch.
> 
> Hm that's weird. I'll try to investigate this later. Meanwhile it
> can stay as it is.
> 
> >Signed-off-by: Joonsoo Kim <iamjoonsoo.kim@lge.com>
> 
> Acked-by: Vlastimil Babka <vbabka@suse.cz>

Okay. Thanks.

> 
> But you'll need to fix:
> 
> >---
> >  mm/compaction.c |   14 ++++++++++++--
> >  mm/internal.h   |    2 ++
> >  mm/page_alloc.c |   19 ++++++++++++++-----
> >  3 files changed, 28 insertions(+), 7 deletions(-)
> >
> >diff --git a/mm/compaction.c b/mm/compaction.c
> >index 782772d..d40c426 100644
> >--- a/mm/compaction.c
> >+++ b/mm/compaction.c
> >@@ -1170,13 +1170,23 @@ static int __compact_finished(struct zone *zone, struct compact_control *cc,
> >  	/* Direct compactor: Is a suitable page free? */
> >  	for (order = cc->order; order < MAX_ORDER; order++) {
> >  		struct free_area *area = &zone->free_area[order];
> >+		bool can_steal;
> >
> >  		/* Job done if page is free of the right migratetype */
> >  		if (!list_empty(&area->free_list[migratetype]))
> >  			return COMPACT_PARTIAL;
> >
> >-		/* Job done if allocation would set block type */
> >-		if (order >= pageblock_order && area->nr_free)
> >+		/* MIGRATE_MOVABLE can fallback on MIGRATE_CMA */
> >+		if (migratetype == MIGRATE_MOVABLE &&
> >+			!list_empty(&area->free_list[MIGRATE_CMA]))
> 
> This won't compile with !CONFIG_CMA, right? I recall pointing it on
> v3 already (or something similar elsewhere).

Will fix.

> 
> >+			return COMPACT_PARTIAL;
> >+
> >+		/*
> >+		 * Job done if allocation would steal freepages from
> >+		 * other migratetype buddy lists.
> >+		 */
> >+		if (find_suitable_fallback(area, order, migratetype,
> >+						true, &can_steal) != -1)
> >  			return COMPACT_PARTIAL;
> >  	}
> >
> >diff --git a/mm/internal.h b/mm/internal.h
> >index c4d6c9b..9640650 100644
> >--- a/mm/internal.h
> >+++ b/mm/internal.h
> >@@ -200,6 +200,8 @@ isolate_freepages_range(struct compact_control *cc,
> >  unsigned long
> >  isolate_migratepages_range(struct compact_control *cc,
> >  			   unsigned long low_pfn, unsigned long end_pfn);
> >+int find_suitable_fallback(struct free_area *area, unsigned int order,
> >+			int migratetype, bool only_stealable, bool *can_steal);
> >
> >  #endif
> >
> >diff --git a/mm/page_alloc.c b/mm/page_alloc.c
> >index 64a4974..95654f9 100644
> >--- a/mm/page_alloc.c
> >+++ b/mm/page_alloc.c
> >@@ -1191,9 +1191,14 @@ static void steal_suitable_fallback(struct zone *zone, struct page *page,
> >  		set_pageblock_migratetype(page, start_type);
> >  }
> >
> >-/* Check whether there is a suitable fallback freepage with requested order. */
> >-static int find_suitable_fallback(struct free_area *area, unsigned int order,
> >-					int migratetype, bool *can_steal)
> >+/*
> >+ * Check whether there is a suitable fallback freepage with requested order.
> >+ * If only_stealable is true, this function returns fallback_mt only if
> >+ * we can steal other freepages all together. This would help to reduce
> >+ * fragmentation due to mixed migratetype pages in one pageblock.
> >+ */
> >+int find_suitable_fallback(struct free_area *area, unsigned int order,
> >+			int migratetype, bool only_stealable, bool *can_steal)
> >  {
> >  	int i;
> >  	int fallback_mt;
> >@@ -1213,7 +1218,11 @@ static int find_suitable_fallback(struct free_area *area, unsigned int order,
> >  		if (can_steal_fallback(order, migratetype))
> >  			*can_steal = true;
> >
> >-		return fallback_mt;
> >+		if (!only_stealable)
> >+			return fallback_mt;
> >+
> >+		if (*can_steal)
> >+			return fallback_mt;
> 
> Why not just single if (!only_stealable || *can_steal)

Will fix, too.

Thanks.

Re: [PATCH v4 3/3] mm/compaction: enhance compaction finish condition

[Joonsoo Kim]

On Wed, Feb 18, 2015 at 04:04:05PM -0800, Andrew Morton wrote:
> On Thu, 12 Feb 2015 16:15:05 +0900 Joonsoo Kim <iamjoonsoo.kim@lge.com> wrote:
> 
> > Compaction has anti fragmentation algorithm. It is that freepage
> > should be more than pageblock order to finish the compaction if we don't
> > find any freepage in requested migratetype buddy list. This is for
> > mitigating fragmentation, but, there is a lack of migratetype
> > consideration and it is too excessive compared to page allocator's anti
> > fragmentation algorithm.
> > 
> > Not considering migratetype would cause premature finish of compaction.
> > For example, if allocation request is for unmovable migratetype,
> > freepage with CMA migratetype doesn't help that allocation and
> > compaction should not be stopped. But, current logic regards this
> > situation as compaction is no longer needed, so finish the compaction.
> > 
> > Secondly, condition is too excessive compared to page allocator's logic.
> > We can steal freepage from other migratetype and change pageblock
> > migratetype on more relaxed conditions in page allocator. This is designed
> > to prevent fragmentation and we can use it here. Imposing hard constraint
> > only to the compaction doesn't help much in this case since page allocator
> > would cause fragmentation again.
> > 
> > To solve these problems, this patch borrows anti fragmentation logic from
> > page allocator. It will reduce premature compaction finish in some cases
> > and reduce excessive compaction work.
> > 
> > stress-highalloc test in mmtests with non movable order 7 allocation shows
> > considerable increase of compaction success rate.
> > 
> > Compaction success rate (Compaction success * 100 / Compaction stalls, %)
> > 31.82 : 42.20
> > 
> > I tested it on non-reboot 5 runs stress-highalloc benchmark and found that
> > there is no more degradation on allocation success rate than before. That
> > roughly means that this patch doesn't result in more fragmentations.
> > 
> > Vlastimil suggests additional idea that we only test for fallbacks
> > when migration scanner has scanned a whole pageblock. It looked good for
> > fragmentation because chance of stealing increase due to making more
> > free pages in certain pageblock. So, I tested it, but, it results in
> > decreased compaction success rate, roughly 38.00. I guess the reason that
> > if system is low memory condition, watermark check could be failed due to
> > not enough order 0 free page and so, sometimes, we can't reach a fallback
> > check although migrate_pfn is aligned to pageblock_nr_pages. I can insert
> > code to cope with this situation but it makes code more complicated so
> > I don't include his idea at this patch.
> > 
> > ...
> >
> > --- a/mm/compaction.c
> > +++ b/mm/compaction.c
> > @@ -1170,13 +1170,23 @@ static int __compact_finished(struct zone *zone, struct compact_control *cc,
> >  	/* Direct compactor: Is a suitable page free? */
> >  	for (order = cc->order; order < MAX_ORDER; order++) {
> >  		struct free_area *area = &zone->free_area[order];
> > +		bool can_steal;
> >  
> >  		/* Job done if page is free of the right migratetype */
> >  		if (!list_empty(&area->free_list[migratetype]))
> >  			return COMPACT_PARTIAL;
> >  
> > -		/* Job done if allocation would set block type */
> > -		if (order >= pageblock_order && area->nr_free)
> > +		/* MIGRATE_MOVABLE can fallback on MIGRATE_CMA */
> > +		if (migratetype == MIGRATE_MOVABLE &&
> > +			!list_empty(&area->free_list[MIGRATE_CMA]))
> > +			return COMPACT_PARTIAL;
> 
> MIGRATE_CMA isn't defined if CONFIG_CMA=n.
> 
> --- a/mm/compaction.c~mm-compaction-enhance-compaction-finish-condition-fix
> +++ a/mm/compaction.c
> @@ -1180,11 +1180,12 @@ static int __compact_finished(struct zon
>  		if (!list_empty(&area->free_list[migratetype]))
>  			return COMPACT_PARTIAL;
>  
> +#ifdef CONFIG_CMA
>  		/* MIGRATE_MOVABLE can fallback on MIGRATE_CMA */
>  		if (migratetype == MIGRATE_MOVABLE &&
>  			!list_empty(&area->free_list[MIGRATE_CMA]))
>  			return COMPACT_PARTIAL;
> -
> +#endif
>  		/*
>  		 * Job done if allocation would steal freepages from
>  		 * other migratetype buddy lists.
> 
> Please review the rest of the patchset for the CONFIG_CMA=n case (is it
> all necessary?), runtime test it and let me know?

Okay.

Following is update version which solves compile issue for the
CONFIG_CMA=n and has minor clean-up pointed by Vlastimil.

I did runtime tests for both CONFIG_CMA=y and CONFIG_CMA=n cases and it
was fine. :)

Thanks.

------->8----------
>From 2f38f08289618598d0bf981218dbb9d6fe7ffa7f Mon Sep 17 00:00:00 2001
From: Joonsoo Kim <iamjoonsoo.kim@lge.com>
Date: Mon, 9 Feb 2015 10:59:56 +0900
Subject: [PATCH v5 3/3] mm/compaction: enhance compaction finish condition

Compaction has anti fragmentation algorithm. It is that freepage
should be more than pageblock order to finish the compaction if we don't
find any freepage in requested migratetype buddy list. This is for
mitigating fragmentation, but, there is a lack of migratetype
consideration and it is too excessive compared to page allocator's anti
fragmentation algorithm.

Not considering migratetype would cause premature finish of compaction.
For example, if allocation request is for unmovable migratetype,
freepage with CMA migratetype doesn't help that allocation and
compaction should not be stopped. But, current logic regards this
situation as compaction is no longer needed, so finish the compaction.

Secondly, condition is too excessive compared to page allocator's logic.
We can steal freepage from other migratetype and change pageblock
migratetype on more relaxed conditions in page allocator. This is designed
to prevent fragmentation and we can use it here. Imposing hard constraint
only to the compaction doesn't help much in this case since page allocator
would cause fragmentation again.

To solve these problems, this patch borrows anti fragmentation logic from
page allocator. It will reduce premature compaction finish in some cases
and reduce excessive compaction work.

stress-highalloc test in mmtests with non movable order 7 allocation shows
considerable increase of compaction success rate.

Compaction success rate (Compaction success * 100 / Compaction stalls, %)
31.82 : 42.20

I tested it on non-reboot 5 runs stress-highalloc benchmark and found that
there is no more degradation on allocation success rate than before. That
roughly means that this patch doesn't result in more fragmentations.

Vlastimil suggests additional idea that we only test for fallbacks
when migration scanner has scanned a whole pageblock. It looked good for
fragmentation because chance of stealing increase due to making more
free pages in certain pageblock. So, I tested it, but, it results in
decreased compaction success rate, roughly 38.00. I guess the reason that
if system is low memory condition, watermark check could be failed due to
not enough order 0 free page and so, sometimes, we can't reach a fallback
check although migrate_pfn is aligned to pageblock_nr_pages. I can insert
code to cope with this situation but it makes code more complicated so
I don't include his idea at this patch.

v5: fix compile error if !CONFIG_CMA.
minor cleanup.

Acked-by: Vlastimil Babka <vbabka@suse.cz>
Signed-off-by: Joonsoo Kim <iamjoonsoo.kim@lge.com>
---
 mm/compaction.c | 16 ++++++++++++++--
 mm/internal.h   |  2 ++
 mm/page_alloc.c | 20 ++++++++++++--------
 3 files changed, 28 insertions(+), 10 deletions(-)

diff --git a/mm/compaction.c b/mm/compaction.c
index 8c0d945..ab8037b 100644
--- a/mm/compaction.c
+++ b/mm/compaction.c
@@ -1174,13 +1174,25 @@ static int __compact_finished(struct zone *zone, struct compact_control *cc,
 	/* Direct compactor: Is a suitable page free? */
 	for (order = cc->order; order < MAX_ORDER; order++) {
 		struct free_area *area = &zone->free_area[order];
+		bool can_steal;
 
 		/* Job done if page is free of the right migratetype */
 		if (!list_empty(&area->free_list[migratetype]))
 			return COMPACT_PARTIAL;
 
-		/* Job done if allocation would set block type */
-		if (order >= pageblock_order && area->nr_free)
+#ifdef CONFIG_CMA
+		/* MIGRATE_MOVABLE can fallback on MIGRATE_CMA */
+		if (migratetype == MIGRATE_MOVABLE &&
+			!list_empty(&area->free_list[MIGRATE_CMA]))
+			return COMPACT_PARTIAL;
+#endif
+
+		/*
+		 * Job done if allocation would steal freepages from
+		 * other migratetype buddy lists.
+		 */
+		if (find_suitable_fallback(area, order, migratetype,
+						true, &can_steal) != -1)
 			return COMPACT_PARTIAL;
 	}
 
diff --git a/mm/internal.h b/mm/internal.h
index a96da5b..ba878bf 100644
--- a/mm/internal.h
+++ b/mm/internal.h
@@ -200,6 +200,8 @@ isolate_freepages_range(struct compact_control *cc,
 unsigned long
 isolate_migratepages_range(struct compact_control *cc,
 			   unsigned long low_pfn, unsigned long end_pfn);
+int find_suitable_fallback(struct free_area *area, unsigned int order,
+			int migratetype, bool only_stealable, bool *can_steal);
 
 #endif
 
diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index c397379..ddf59bf 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c
@@ -1194,9 +1194,14 @@ static void steal_suitable_fallback(struct zone *zone, struct page *page,
 		set_pageblock_migratetype(page, start_type);
 }
 
-/* Check whether there is a suitable fallback freepage with requested order. */
-static int find_suitable_fallback(struct free_area *area, unsigned int order,
-					int migratetype, bool *can_steal)
+/*
+ * Check whether there is a suitable fallback freepage with requested order.
+ * If only_stealable is true, this function returns fallback_mt only if
+ * we can steal other freepages all together. This would help to reduce
+ * fragmentation due to mixed migratetype pages in one pageblock.
+ */
+int find_suitable_fallback(struct free_area *area, unsigned int order,
+			int migratetype, bool only_stealable, bool *can_steal)
 {
 	int i;
 	int fallback_mt;
@@ -1213,10 +1218,9 @@ static int find_suitable_fallback(struct free_area *area, unsigned int order,
 		if (list_empty(&area->free_list[fallback_mt]))
 			continue;
 
-		if (can_steal_fallback(order, migratetype))
-			*can_steal = true;
-
-		return fallback_mt;
+		*can_steal = can_steal_fallback(order, migratetype);
+		if (!only_stealable || *can_steal)
+			return fallback_mt;
 	}
 
 	return -1;
@@ -1238,7 +1242,7 @@ __rmqueue_fallback(struct zone *zone, unsigned int order, int start_migratetype)
 				--current_order) {
 		area = &(zone->free_area[current_order]);
 		fallback_mt = find_suitable_fallback(area, current_order,
-				start_migratetype, &can_steal);
+				start_migratetype, false, &can_steal);
 		if (fallback_mt == -1)
 			continue;
 
-- 
1.9.1