[PATCH 0/2] mm: compaction: improve free pages selection

[PATCH 0/2] mm: compaction: improve free pages selection

[Bartlomiej Zolnierkiewicz]

These patches lift some limitations on free pages selection so there
is a much higher chance of memory migration succeeding in case of heavy
memory fragmentation.

[ From looking at the compaction free pages selection code I'm under
  the impression that the noticed limitations exist because the code
  was originally designed to mainly deal with hugepages? ]


My test case on a ARM EXYNOS4 device with 512 MiB (to be exact:
131072 standard 4KiB pages in 'Normal' zone) is to:
- allocate 120000 pages for kernel's usage
- free every second page (60000 pages) of memory just allocated
- allocate and use 60000 pages from user space
- free remaining 60000 pages of kernel memory
(now we have fragmented memory occupied mostly by user space pages)
- try to allocate 100 order-9 (2048 KiB) pages for kernel's usage

The results:
- with compaction disabled I get 11 successful allocations
- with compaction enabled - 14 successful allocations
- with patch #1 - 34 successful allocations
- with patches #1+2 all 100 allocations succeed


On the cons side of the changes is the increased CPU usage spent on
finding suitable free pages.  However once we try memory compaction to
help us to allocate higher order pages we are already in the slow-path
and it is better to spent some extra cycles than to fail the allocation
completely.

Best regards,
--
Bartlomiej Zolnierkiewicz
Samsung Poland R&D Center


Bartlomiej Zolnierkiewicz (2):
  mm: compaction: try harder to isolate free pages
  mm: compaction: allow isolation of lower order buddy pages

 mm/compaction.c |    9 ++++-----
 1 file changed, 4 insertions(+), 5 deletions(-)

-- 
1.7.9.4

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[PATCH 1/2] mm: compaction: try harder to isolate free pages

[Bartlomiej Zolnierkiewicz]

In isolate_freepages() check each page in a pageblock
instead of checking only first pages of pageblock_nr_pages
intervals (suitable_migration_target(page) is called before
isolate_freepages_block() so if page is "unsuitable" whole
pageblock_nr_pages pages will be ommited from the check).
It greatly improves possibility of finding free pages to
isolate during compaction_alloc() phase.

Cc: Mel Gorman <mgorman@suse.de>
Signed-off-by: Bartlomiej Zolnierkiewicz <b.zolnierkie@samsung.com>
Signed-off-by: Kyungmin Park <kyungmin.park@samsung.com>
---
 mm/compaction.c |    5 ++---
 1 file changed, 2 insertions(+), 3 deletions(-)

diff --git a/mm/compaction.c b/mm/compaction.c
index d9ebebe..bc77135 100644
--- a/mm/compaction.c
+++ b/mm/compaction.c
@@ -65,7 +65,7 @@ static unsigned long isolate_freepages_block(struct zone *zone,
 
 	/* Get the last PFN we should scan for free pages at */
 	zone_end_pfn = zone->zone_start_pfn + zone->spanned_pages;
-	end_pfn = min(blockpfn + pageblock_nr_pages, zone_end_pfn);
+	end_pfn = min(blockpfn + 1, zone_end_pfn);
 
 	/* Find the first usable PFN in the block to initialse page cursor */
 	for (; blockpfn < end_pfn; blockpfn++) {
@@ -160,8 +160,7 @@ static void isolate_freepages(struct zone *zone,
 	 * pages on cc->migratepages. We stop searching if the migrate
 	 * and free page scanners meet or enough free pages are isolated.
 	 */
-	for (; pfn > low_pfn && cc->nr_migratepages > nr_freepages;
-					pfn -= pageblock_nr_pages) {
+	for (; pfn > low_pfn && cc->nr_migratepages > nr_freepages; pfn--) {
 		unsigned long isolated;
 
 		if (!pfn_valid(pfn))
-- 
1.7.9.4

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[PATCH 2/2] mm: compaction: allow isolation of lower order buddy pages

[Bartlomiej Zolnierkiewicz]

Allow lower order buddy pages in suitable_migration_target()
so isolate_freepages() can isolate them as free pages during
compaction_alloc() phase.

Cc: Mel Gorman <mgorman@suse.de>
Signed-off-by: Bartlomiej Zolnierkiewicz <b.zolnierkie@samsung.com>
Signed-off-by: Kyungmin Park <kyungmin.park@samsung.com>
---
 mm/compaction.c |    4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/mm/compaction.c b/mm/compaction.c
index bc77135..642c17a 100644
--- a/mm/compaction.c
+++ b/mm/compaction.c
@@ -115,8 +115,8 @@ static bool suitable_migration_target(struct page *page)
 	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)
+	/* If the page is a free page, then allow migration */
+	if (PageBuddy(page))
 		return true;
 
 	/* If the block is MIGRATE_MOVABLE, allow migration */
-- 
1.7.9.4

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH 2/2] mm: compaction: allow isolation of lower order buddy pages

[David Rientjes]

On Thu, 5 Apr 2012, Bartlomiej Zolnierkiewicz wrote:

> diff --git a/mm/compaction.c b/mm/compaction.c
> index bc77135..642c17a 100644
> --- a/mm/compaction.c
> +++ b/mm/compaction.c
> @@ -115,8 +115,8 @@ static bool suitable_migration_target(struct page *page)
>  	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)
> +	/* If the page is a free page, then allow migration */
> +	if (PageBuddy(page))
>  		return true;
>  
>  	/* If the block is MIGRATE_MOVABLE, allow migration */

So when we try to allocate a 2M hugepage through the buddy allocator where 
the pageblock is also 2M, wouldn't this result in a lot of unnecessary 
migration of memory that may not end up defragmented enough for the 
allocation to succeed?  Sounds like a regression for hugepage allocation.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH 1/2] mm: compaction: try harder to isolate free pages

[Minchan Kim]

[-- Attachment #1: Type: text/plain, Size: 2497 bytes --]

On Fri, Apr 6, 2012 at 1:32 AM, Bartlomiej Zolnierkiewicz <
b.zolnierkie@samsung.com> wrote:

> In isolate_freepages() check each page in a pageblock
> instead of checking only first pages of pageblock_nr_pages
> intervals (suitable_migration_target(page) is called before
> isolate_freepages_block() so if page is "unsuitable" whole
> pageblock_nr_pages pages will be ommited from the check).
> It greatly improves possibility of finding free pages to
> isolate during compaction_alloc() phase.
>

I doubt how this can help keeping free pages.
Now, compaction works by pageblock_nr_pages unit so although you work by
per page, all pages in a block would have same block type.
It means we can't pass suitable_migration_target. No?


> Cc: Mel Gorman <mgorman@suse.de>
> Signed-off-by: Bartlomiej Zolnierkiewicz <b.zolnierkie@samsung.com>
> Signed-off-by: Kyungmin Park <kyungmin.park@samsung.com>
> ---
>  mm/compaction.c |    5 ++---
>  1 file changed, 2 insertions(+), 3 deletions(-)
>
> diff --git a/mm/compaction.c b/mm/compaction.c
> index d9ebebe..bc77135 100644
> --- a/mm/compaction.c
> +++ b/mm/compaction.c
> @@ -65,7 +65,7 @@ static unsigned long isolate_freepages_block(struct zone
> *zone,
>
>        /* Get the last PFN we should scan for free pages at */
>        zone_end_pfn = zone->zone_start_pfn + zone->spanned_pages;
> -       end_pfn = min(blockpfn + pageblock_nr_pages, zone_end_pfn);
> +       end_pfn = min(blockpfn + 1, zone_end_pfn);
>
>        /* Find the first usable PFN in the block to initialse page cursor
> */
>        for (; blockpfn < end_pfn; blockpfn++) {
> @@ -160,8 +160,7 @@ static void isolate_freepages(struct zone *zone,
>         * pages on cc->migratepages. We stop searching if the migrate
>         * and free page scanners meet or enough free pages are isolated.
>         */
> -       for (; pfn > low_pfn && cc->nr_migratepages > nr_freepages;
> -                                       pfn -= pageblock_nr_pages) {
> +       for (; pfn > low_pfn && cc->nr_migratepages > nr_freepages; pfn--)
> {
>                unsigned long isolated;
>
>                if (!pfn_valid(pfn))
> --
> 1.7.9.4
>
> --
> To unsubscribe, send a message with 'unsubscribe linux-mm' in
> the body to majordomo@kvack.org.  For more info on Linux MM,
> see: http://www.linux-mm.org/ .
> Fight unfair telecom internet charges in Canada: sign
> http://stopthemeter.ca/
> Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
>



-- 
Kind regards,
Minchan Kim

[-- Attachment #2: Type: text/html, Size: 3694 bytes --]

Re: [PATCH 2/2] mm: compaction: allow isolation of lower order buddy pages

[Minchan Kim]

[-- Attachment #1: Type: text/plain, Size: 372 bytes --]

On Fri, Apr 6, 2012 at 1:32 AM, Bartlomiej Zolnierkiewicz <
b.zolnierkie@samsung.com> wrote:

> Allow lower order buddy pages in suitable_migration_target()
> so isolate_freepages() can isolate them as free pages during
> compaction_alloc() phase.
>

It could mix movable pages in unmovable block so that it would mess page
grouping up. :(


-- 
Kind regards,
Minchan Kim

[-- Attachment #2: Type: text/html, Size: 674 bytes --]

Re: [PATCH 1/2] mm: compaction: try harder to isolate free pages

[Bartlomiej Zolnierkiewicz]

On Friday 06 April 2012 08:40:56 Minchan Kim wrote:
> On Fri, Apr 6, 2012 at 1:32 AM, Bartlomiej Zolnierkiewicz <
> b.zolnierkie@samsung.com> wrote:
> 
> > In isolate_freepages() check each page in a pageblock
> > instead of checking only first pages of pageblock_nr_pages
> > intervals (suitable_migration_target(page) is called before
> > isolate_freepages_block() so if page is "unsuitable" whole
> > pageblock_nr_pages pages will be ommited from the check).
> > It greatly improves possibility of finding free pages to
> > isolate during compaction_alloc() phase.
> >
> 
> I doubt how this can help keeping free pages.
> Now, compaction works by pageblock_nr_pages unit so although you work by
> per page, all pages in a block would have same block type.
> It means we can't pass suitable_migration_target. No?

suitable_migration_target() only checks first page of pageblock_nr_pages
block (1024 normal 4KiB pages in my test case cause there is no hugepage
support on ARM) and pages in pageblock_nr_pages block can have different
types otherwise I would not see improvement from this patch.

Best regards,
--
Bartlomiej Zolnierkiewicz
Samsung Poland R&D Center

> > Cc: Mel Gorman <mgorman@suse.de>
> > Signed-off-by: Bartlomiej Zolnierkiewicz <b.zolnierkie@samsung.com>
> > Signed-off-by: Kyungmin Park <kyungmin.park@samsung.com>
> > ---
> >  mm/compaction.c |    5 ++---
> >  1 file changed, 2 insertions(+), 3 deletions(-)
> >
> > diff --git a/mm/compaction.c b/mm/compaction.c
> > index d9ebebe..bc77135 100644
> > --- a/mm/compaction.c
> > +++ b/mm/compaction.c
> > @@ -65,7 +65,7 @@ static unsigned long isolate_freepages_block(struct zone
> > *zone,
> >
> >        /* Get the last PFN we should scan for free pages at */
> >        zone_end_pfn = zone->zone_start_pfn + zone->spanned_pages;
> > -       end_pfn = min(blockpfn + pageblock_nr_pages, zone_end_pfn);
> > +       end_pfn = min(blockpfn + 1, zone_end_pfn);
> >
> >        /* Find the first usable PFN in the block to initialse page cursor
> > */
> >        for (; blockpfn < end_pfn; blockpfn++) {
> > @@ -160,8 +160,7 @@ static void isolate_freepages(struct zone *zone,
> >         * pages on cc->migratepages. We stop searching if the migrate
> >         * and free page scanners meet or enough free pages are isolated.
> >         */
> > -       for (; pfn > low_pfn && cc->nr_migratepages > nr_freepages;
> > -                                       pfn -= pageblock_nr_pages) {
> > +       for (; pfn > low_pfn && cc->nr_migratepages > nr_freepages; pfn--)
> > {
> >                unsigned long isolated;
> >
> >                if (!pfn_valid(pfn))

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH 2/2] mm: compaction: allow isolation of lower order buddy pages

[Bartlomiej Zolnierkiewicz]

On Thursday 05 April 2012 23:46:17 David Rientjes wrote:
> On Thu, 5 Apr 2012, Bartlomiej Zolnierkiewicz wrote:
> 
> > diff --git a/mm/compaction.c b/mm/compaction.c
> > index bc77135..642c17a 100644
> > --- a/mm/compaction.c
> > +++ b/mm/compaction.c
> > @@ -115,8 +115,8 @@ static bool suitable_migration_target(struct page *page)
> >  	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)
> > +	/* If the page is a free page, then allow migration */
> > +	if (PageBuddy(page))
> >  		return true;
> >  
> >  	/* If the block is MIGRATE_MOVABLE, allow migration */
> 
> So when we try to allocate a 2M hugepage through the buddy allocator where 
> the pageblock is also 2M, wouldn't this result in a lot of unnecessary 
> migration of memory that may not end up defragmented enough for the 
> allocation to succeed?  Sounds like a regression for hugepage allocation.

I haven't tested it with hugepage allocation yet (no hugepage support
on ARM) but the code isolating pages for migration remains unchanged
so after migration memory we are trying to allocate pages from should
end up at least as defragmented as before the patch.  Some migrations
may turn out to be unnecessary but it doesn't seem as it introduces
additional problems with hugepage allocation.

Best regards,
--
Bartlomiej Zolnierkiewicz
Samsung Poland R&D Center

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH 1/2] mm: compaction: try harder to isolate free pages

[Minchan Kim]

On Fri, Apr 6, 2012 at 5:21 PM, Bartlomiej Zolnierkiewicz
<b.zolnierkie@samsung.com> wrote:
> On Friday 06 April 2012 08:40:56 Minchan Kim wrote:
>> On Fri, Apr 6, 2012 at 1:32 AM, Bartlomiej Zolnierkiewicz <
>> b.zolnierkie@samsung.com> wrote:
>>
>> > In isolate_freepages() check each page in a pageblock
>> > instead of checking only first pages of pageblock_nr_pages
>> > intervals (suitable_migration_target(page) is called before
>> > isolate_freepages_block() so if page is "unsuitable" whole
>> > pageblock_nr_pages pages will be ommited from the check).
>> > It greatly improves possibility of finding free pages to
>> > isolate during compaction_alloc() phase.
>> >
>>
>> I doubt how this can help keeping free pages.
>> Now, compaction works by pageblock_nr_pages unit so although you work by
>> per page, all pages in a block would have same block type.
>> It means we can't pass suitable_migration_target. No?
>
> suitable_migration_target() only checks first page of pageblock_nr_pages
> block (1024 normal 4KiB pages in my test case cause there is no hugepage
> support on ARM) and pages in pageblock_nr_pages block can have different
> types otherwise I would not see improvement from this patch.

How?
pages in a block should be same type.


-- 
Kind regards,
Minchan Kim

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH 1/2] mm: compaction: try harder to isolate free pages

[Mel Gorman]

On Thu, Apr 05, 2012 at 06:32:12PM +0200, Bartlomiej Zolnierkiewicz wrote:
> In isolate_freepages() check each page in a pageblock
> instead of checking only first pages of pageblock_nr_pages
> intervals (suitable_migration_target(page) is called before
> isolate_freepages_block() so if page is "unsuitable" whole
> pageblock_nr_pages pages will be ommited from the check).
> It greatly improves possibility of finding free pages to
> isolate during compaction_alloc() phase.
> 
> Cc: Mel Gorman <mgorman@suse.de>
> Signed-off-by: Bartlomiej Zolnierkiewicz <b.zolnierkie@samsung.com>
> Signed-off-by: Kyungmin Park <kyungmin.park@samsung.com>
> ---
>  mm/compaction.c |    5 ++---
>  1 file changed, 2 insertions(+), 3 deletions(-)
> 
> diff --git a/mm/compaction.c b/mm/compaction.c
> index d9ebebe..bc77135 100644
> --- a/mm/compaction.c
> +++ b/mm/compaction.c
> @@ -65,7 +65,7 @@ static unsigned long isolate_freepages_block(struct zone *zone,
>  
>  	/* Get the last PFN we should scan for free pages at */
>  	zone_end_pfn = zone->zone_start_pfn + zone->spanned_pages;
> -	end_pfn = min(blockpfn + pageblock_nr_pages, zone_end_pfn);
> +	end_pfn = min(blockpfn + 1, zone_end_pfn);
>  
>  	/* Find the first usable PFN in the block to initialse page cursor */
>  	for (; blockpfn < end_pfn; blockpfn++) {

This changes the meaning of the function significantly. Before your
patch it isolates all the free pages within a block. After your change
it is isolating a single page and the function name should be updated to
reflect that. Of greater concern is that isolate_freepages()
is now calling suitable_migration_target() for every page scanned
calling get_pageblock_migratetype() every time which is slow. Worse, you
are now acquiring the zone lock for every page scanned which is slower
again.

I think the bug you are accidentally fixing is related to how high_pfn
is updated inside that loop. The intent is that when free pages are
isolated that the next scan started from the same place as page
migration may have released those pages again. As it gets updated every
time a page is isolated the scanner is moving faster than it should.

Try this;

diff --git a/mm/compaction.c b/mm/compaction.c
index 74a8c82..177e161 100644
--- a/mm/compaction.c
+++ b/mm/compaction.c
@@ -139,6 +139,7 @@ static void isolate_freepages(struct zone *zone,
 	unsigned long flags;
 	int nr_freepages = cc->nr_freepages;
 	struct list_head *freelist = &cc->freepages;
+	bool first_isolation = true;
 
 	/*
 	 * Initialise the free scanner. The starting point is where we last
@@ -201,8 +202,10 @@ static void isolate_freepages(struct zone *zone,
 		 * looking for free pages, the search will restart here as
 		 * page migration may have returned some pages to the allocator
 		 */
-		if (isolated)
+		if (isolated && first_isolation) {
+			first_isolation = false;
 			high_pfn = max(high_pfn, pfn);
+		}
 	}
 
 	/* split_free_page does not map the pages */

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH 2/2] mm: compaction: allow isolation of lower order buddy pages

[Mel Gorman]

On Thu, Apr 05, 2012 at 06:32:13PM +0200, Bartlomiej Zolnierkiewicz wrote:
> Allow lower order buddy pages in suitable_migration_target()
> so isolate_freepages() can isolate them as free pages during
> compaction_alloc() phase.
> 
> Cc: Mel Gorman <mgorman@suse.de>
> Signed-off-by: Bartlomiej Zolnierkiewicz <b.zolnierkie@samsung.com>
> Signed-off-by: Kyungmin Park <kyungmin.park@samsung.com>

Nak.

This patch depends on patch 1 to scan every page in isolate_freepages()
and I explained why that is a problem already. That aside, a side-effect
of this is that movable pages can get migrated to MIGRATE_UNMOVABLE
and MIGRATE_RECLAIMABLE pageblocks. This will have a negative impact on
fragmentation avoidance. In your particular use-case it will slightly
increase allocation success rates early in the lifetime of the system at
the cost of degrading success rates later.

-- 
Mel Gorman
SUSE Labs

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH 1/2] mm: compaction: try harder to isolate free pages

[Mel Gorman]

On Tue, Apr 10, 2012 at 11:38:33AM +0100, Mel Gorman wrote:
> I think the bug you are accidentally fixing is related to how high_pfn
> is updated inside that loop. The intent is that when free pages are
> isolated that the next scan started from the same place as page
> migration may have released those pages again. As it gets updated every
> time a page is isolated the scanner is moving faster than it should.
> 
> Try this;
> 

That patch is obviously wrong so you're still looking for some other
side-effect of your patch that explains why it appears to behave better.

-- 
Mel Gorman
SUSE Labs

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>