Re: [PATCH v2 7/9] mm/compaction: redesign compaction

[Joonsoo Kim]

On Wed, Oct 14, 2015 at 01:38:07PM +0200, Vlastimil Babka wrote:
> On 08/24/2015 04:19 AM, Joonsoo Kim wrote:
> 
> [...]
> 
> > This patch solves these problems mentioned in above.
> > Freepage scanner is largely changed to scan zone from zone_start_pfn
> > to zone_end_pfn. And, by this change, compaction finish condition is also
> > changed that migration scanner reach zone_end_pfn. With these changes,
> > migration scanner can traverse anywhere in the zone.
> > 
> > To prevent back and forth migration within one compaction iteration,
> > freepage scanner marks skip-bit when scanning pageblock. migration scanner
> > checks it and will skip this marked pageblock so back and forth migration
> > cannot be possible in one compaction iteration.
> > 
> > If freepage scanner reachs the end of zone, it restarts at zone_start_pfn.
> > In this time, freepage scanner would scan the pageblock where migration
> > scanner has migrated some pages but fail to make high order page. This
> > leaved freepages means that they can't become high order page due to
> > the fragmentation so it is good source for freepage scanner.
> 
> Hmm, there might be danger that freepage scanner will proceed faster than
> migration scanner, as evidenced by the current code where the scanners meet
> earlier than in the middle. Thus, it would likely mark pageblocks as 
> unsuitable
> for migration scanner, before it can reach them?

That's right.

> 
> > With this change, above test result is:
> > 
> > Kernel: Base vs Redesign
> > 
> > Test: hogger-frag-movable
> > 
> > Success(N)70  94
> > compact_stall3073642
> > compact_success   64 144
> > compact_fail 2433498
> > pgmigrate_success  3459215897219
> > compact_isolated   7397731899553
> > compact_migrate_scanned  228077059146745
> > compact_free_scanned 471031349566134
> > 
> > Test: hogger-frag-movable with free memory variation
> > 
> > 200MB-Success(N)70  94
> > 250MB-Success(N)38  93
> > 300MB-Success(N)29  89
> > 
> > Compaction gives us almost all possible high order page. Overhead is
> > highly increased, but, further patch will reduce it greatly
> > by adjusting depletion check with this new algorithm.
> > 
> > Signed-off-by: Joonsoo Kim 
> > ---
> >  mm/compaction.c | 145 
> > ++--
> >  1 file changed, 77 insertions(+), 68 deletions(-)
> > 
> > diff --git a/mm/compaction.c b/mm/compaction.c
> > index a259608..ca4d6d1 100644
> > --- a/mm/compaction.c
> > +++ b/mm/compaction.c
> > @@ -53,17 +53,17 @@ static const char *const compaction_status_string[] = {
> >  static unsigned long release_freepages(struct list_head *freelist)
> >  {
> > struct page *page, *next;
> > -   unsigned long high_pfn = 0;
> > +   unsigned long low_pfn = ULONG_MAX;
> >  
> > list_for_each_entry_safe(page, next, freelist, lru) {
> > unsigned long pfn = page_to_pfn(page);
> > list_del(>lru);
> > __free_page(page);
> > -   if (pfn > high_pfn)
> > -   high_pfn = pfn;
> > +   if (pfn < low_pfn)
> > +   low_pfn = pfn;
> > }
> >  
> > -   return high_pfn;
> > +   return low_pfn;
> 
> This assumes that the freelist won't contain both pages from the end of the
> zone, and from the beginning the zone after the free scanner has wrapped. 
> Which
> is true, but not immediately obvious, so it deserves some comment.

Okay. Will add it.

> >  }
> >  
> >  static void map_pages(struct list_head *list)
> > @@ -243,7 +243,7 @@ static void __reset_isolation_suitable(struct zone 
> > *zone)
> >  
> > zone->compact_cached_migrate_pfn[0] = start_pfn;
> > zone->compact_cached_migrate_pfn[1] = start_pfn;
> > -   zone->compact_cached_free_pfn = end_pfn;
> > +   zone->compact_cached_free_pfn = start_pfn;
> > zone->compact_blockskip_flush = false;
> >  
> > clear_bit(ZONE_COMPACTION_SCANALLFREE, >flags);
> > @@ -335,7 +335,7 @@ static void update_pageblock_skip(struct 
> > compact_control *cc,
> > if (!nr_isolated)
> > set_pageblock_skip_freescan(page);
> >  
> > -   if (pfn < zone->compact_cached_free_pfn)
> > +   if (pfn > zone->compact_cached_free_pfn)
> > zone->compact_cached_free_pfn = pfn;
> > }
> >  }
> > @@ -869,8 +869,11 @@ isolate_success:
> > nr_scanned, nr_isolated);
> >  
> > count_compact_events(COMPACTMIGRATE_SCANNED, nr_scanned);
> > -   if (nr_isolated)
> > +   if (nr_isolated) {
> > count_compact_events(COMPACTISOLATED, nr_isolated);
> > +   if (valid_page)
> > +   clear_pageblock_skip_freescan(valid_page);
> 
> This is explained in changelog, but a comment here would be useful too.

Okay.

> > +   }
> >  
> > 

Re: [PATCH v2 7/9] mm/compaction: redesign compaction

[Vlastimil Babka]

On 08/24/2015 04:19 AM, Joonsoo Kim wrote:

[...]

> This patch solves these problems mentioned in above.
> Freepage scanner is largely changed to scan zone from zone_start_pfn
> to zone_end_pfn. And, by this change, compaction finish condition is also
> changed that migration scanner reach zone_end_pfn. With these changes,
> migration scanner can traverse anywhere in the zone.
> 
> To prevent back and forth migration within one compaction iteration,
> freepage scanner marks skip-bit when scanning pageblock. migration scanner
> checks it and will skip this marked pageblock so back and forth migration
> cannot be possible in one compaction iteration.
> 
> If freepage scanner reachs the end of zone, it restarts at zone_start_pfn.
> In this time, freepage scanner would scan the pageblock where migration
> scanner has migrated some pages but fail to make high order page. This
> leaved freepages means that they can't become high order page due to
> the fragmentation so it is good source for freepage scanner.

Hmm, there might be danger that freepage scanner will proceed faster than
migration scanner, as evidenced by the current code where the scanners meet
earlier than in the middle. Thus, it would likely mark pageblocks as unsuitable
for migration scanner, before it can reach them?

> With this change, above test result is:
> 
> Kernel:   Base vs Redesign
> 
> Test: hogger-frag-movable
> 
> Success(N)70  94
> compact_stall3073642
> compact_success   64 144
> compact_fail 2433498
> pgmigrate_success  3459215897219
> compact_isolated   7397731899553
> compact_migrate_scanned  228077059146745
> compact_free_scanned 471031349566134
> 
> Test: hogger-frag-movable with free memory variation
> 
> 200MB-Success(N)  70  94
> 250MB-Success(N)  38  93
> 300MB-Success(N)  29  89
> 
> Compaction gives us almost all possible high order page. Overhead is
> highly increased, but, further patch will reduce it greatly
> by adjusting depletion check with this new algorithm.
> 
> Signed-off-by: Joonsoo Kim 
> ---
>  mm/compaction.c | 145 
> ++--
>  1 file changed, 77 insertions(+), 68 deletions(-)
> 
> diff --git a/mm/compaction.c b/mm/compaction.c
> index a259608..ca4d6d1 100644
> --- a/mm/compaction.c
> +++ b/mm/compaction.c
> @@ -53,17 +53,17 @@ static const char *const compaction_status_string[] = {
>  static unsigned long release_freepages(struct list_head *freelist)
>  {
>   struct page *page, *next;
> - unsigned long high_pfn = 0;
> + unsigned long low_pfn = ULONG_MAX;
>  
>   list_for_each_entry_safe(page, next, freelist, lru) {
>   unsigned long pfn = page_to_pfn(page);
>   list_del(>lru);
>   __free_page(page);
> - if (pfn > high_pfn)
> - high_pfn = pfn;
> + if (pfn < low_pfn)
> + low_pfn = pfn;
>   }
>  
> - return high_pfn;
> + return low_pfn;

This assumes that the freelist won't contain both pages from the end of the
zone, and from the beginning the zone after the free scanner has wrapped. Which
is true, but not immediately obvious, so it deserves some comment.

>  }
>  
>  static void map_pages(struct list_head *list)
> @@ -243,7 +243,7 @@ static void __reset_isolation_suitable(struct zone *zone)
>  
>   zone->compact_cached_migrate_pfn[0] = start_pfn;
>   zone->compact_cached_migrate_pfn[1] = start_pfn;
> - zone->compact_cached_free_pfn = end_pfn;
> + zone->compact_cached_free_pfn = start_pfn;
>   zone->compact_blockskip_flush = false;
>  
>   clear_bit(ZONE_COMPACTION_SCANALLFREE, >flags);
> @@ -335,7 +335,7 @@ static void update_pageblock_skip(struct compact_control 
> *cc,
>   if (!nr_isolated)
>   set_pageblock_skip_freescan(page);
>  
> - if (pfn < zone->compact_cached_free_pfn)
> + if (pfn > zone->compact_cached_free_pfn)
>   zone->compact_cached_free_pfn = pfn;
>   }
>  }
> @@ -869,8 +869,11 @@ isolate_success:
>   nr_scanned, nr_isolated);
>  
>   count_compact_events(COMPACTMIGRATE_SCANNED, nr_scanned);
> - if (nr_isolated)
> + if (nr_isolated) {
>   count_compact_events(COMPACTISOLATED, nr_isolated);
> + if (valid_page)
> + clear_pageblock_skip_freescan(valid_page);

This is explained in changelog, but a comment here would be useful too.

> + }
>  
>   return low_pfn;
>  }
> @@ -969,12 +972,14 @@ static void isolate_freepages(struct compact_control 
> *cc)
>  {
>   struct zone *zone = cc->zone;
>   struct page *page;
> + unsigned long pfn;
>   unsigned long block_start_pfn;  /* start of current pageblock */
> - 

Re: [PATCH v2 7/9] mm/compaction: redesign compaction

[Vlastimil Babka]

On 08/24/2015 04:19 AM, Joonsoo Kim wrote:

[...]

> This patch solves these problems mentioned in above.
> Freepage scanner is largely changed to scan zone from zone_start_pfn
> to zone_end_pfn. And, by this change, compaction finish condition is also
> changed that migration scanner reach zone_end_pfn. With these changes,
> migration scanner can traverse anywhere in the zone.
> 
> To prevent back and forth migration within one compaction iteration,
> freepage scanner marks skip-bit when scanning pageblock. migration scanner
> checks it and will skip this marked pageblock so back and forth migration
> cannot be possible in one compaction iteration.
> 
> If freepage scanner reachs the end of zone, it restarts at zone_start_pfn.
> In this time, freepage scanner would scan the pageblock where migration
> scanner has migrated some pages but fail to make high order page. This
> leaved freepages means that they can't become high order page due to
> the fragmentation so it is good source for freepage scanner.

Hmm, there might be danger that freepage scanner will proceed faster than
migration scanner, as evidenced by the current code where the scanners meet
earlier than in the middle. Thus, it would likely mark pageblocks as unsuitable
for migration scanner, before it can reach them?

> With this change, above test result is:
> 
> Kernel:   Base vs Redesign
> 
> Test: hogger-frag-movable
> 
> Success(N)70  94
> compact_stall3073642
> compact_success   64 144
> compact_fail 2433498
> pgmigrate_success  3459215897219
> compact_isolated   7397731899553
> compact_migrate_scanned  228077059146745
> compact_free_scanned 471031349566134
> 
> Test: hogger-frag-movable with free memory variation
> 
> 200MB-Success(N)  70  94
> 250MB-Success(N)  38  93
> 300MB-Success(N)  29  89
> 
> Compaction gives us almost all possible high order page. Overhead is
> highly increased, but, further patch will reduce it greatly
> by adjusting depletion check with this new algorithm.
> 
> Signed-off-by: Joonsoo Kim 
> ---
>  mm/compaction.c | 145 
> ++--
>  1 file changed, 77 insertions(+), 68 deletions(-)
> 
> diff --git a/mm/compaction.c b/mm/compaction.c
> index a259608..ca4d6d1 100644
> --- a/mm/compaction.c
> +++ b/mm/compaction.c
> @@ -53,17 +53,17 @@ static const char *const compaction_status_string[] = {
>  static unsigned long release_freepages(struct list_head *freelist)
>  {
>   struct page *page, *next;
> - unsigned long high_pfn = 0;
> + unsigned long low_pfn = ULONG_MAX;
>  
>   list_for_each_entry_safe(page, next, freelist, lru) {
>   unsigned long pfn = page_to_pfn(page);
>   list_del(>lru);
>   __free_page(page);
> - if (pfn > high_pfn)
> - high_pfn = pfn;
> + if (pfn < low_pfn)
> + low_pfn = pfn;
>   }
>  
> - return high_pfn;
> + return low_pfn;

This assumes that the freelist won't contain both pages from the end of the
zone, and from the beginning the zone after the free scanner has wrapped. Which
is true, but not immediately obvious, so it deserves some comment.

>  }
>  
>  static void map_pages(struct list_head *list)
> @@ -243,7 +243,7 @@ static void __reset_isolation_suitable(struct zone *zone)
>  
>   zone->compact_cached_migrate_pfn[0] = start_pfn;
>   zone->compact_cached_migrate_pfn[1] = start_pfn;
> - zone->compact_cached_free_pfn = end_pfn;
> + zone->compact_cached_free_pfn = start_pfn;
>   zone->compact_blockskip_flush = false;
>  
>   clear_bit(ZONE_COMPACTION_SCANALLFREE, >flags);
> @@ -335,7 +335,7 @@ static void update_pageblock_skip(struct compact_control 
> *cc,
>   if (!nr_isolated)
>   set_pageblock_skip_freescan(page);
>  
> - if (pfn < zone->compact_cached_free_pfn)
> + if (pfn > zone->compact_cached_free_pfn)
>   zone->compact_cached_free_pfn = pfn;
>   }
>  }
> @@ -869,8 +869,11 @@ isolate_success:
>   nr_scanned, nr_isolated);
>  
>   count_compact_events(COMPACTMIGRATE_SCANNED, nr_scanned);
> - if (nr_isolated)
> + if (nr_isolated) {
>   count_compact_events(COMPACTISOLATED, nr_isolated);
> + if (valid_page)
> + clear_pageblock_skip_freescan(valid_page);

This is explained in changelog, but a comment here would be useful too.

> + }
>  
>   return low_pfn;
>  }
> @@ -969,12 +972,14 @@ static void isolate_freepages(struct compact_control 
> *cc)
>  {
>   struct zone *zone = cc->zone;
>   struct page *page;
> + unsigned long pfn;
>   unsigned long block_start_pfn;  /* start of 

Re: [PATCH v2 7/9] mm/compaction: redesign compaction

[Joonsoo Kim]

On Wed, Oct 14, 2015 at 01:38:07PM +0200, Vlastimil Babka wrote:
> On 08/24/2015 04:19 AM, Joonsoo Kim wrote:
> 
> [...]
> 
> > This patch solves these problems mentioned in above.
> > Freepage scanner is largely changed to scan zone from zone_start_pfn
> > to zone_end_pfn. And, by this change, compaction finish condition is also
> > changed that migration scanner reach zone_end_pfn. With these changes,
> > migration scanner can traverse anywhere in the zone.
> > 
> > To prevent back and forth migration within one compaction iteration,
> > freepage scanner marks skip-bit when scanning pageblock. migration scanner
> > checks it and will skip this marked pageblock so back and forth migration
> > cannot be possible in one compaction iteration.
> > 
> > If freepage scanner reachs the end of zone, it restarts at zone_start_pfn.
> > In this time, freepage scanner would scan the pageblock where migration
> > scanner has migrated some pages but fail to make high order page. This
> > leaved freepages means that they can't become high order page due to
> > the fragmentation so it is good source for freepage scanner.
> 
> Hmm, there might be danger that freepage scanner will proceed faster than
> migration scanner, as evidenced by the current code where the scanners meet
> earlier than in the middle. Thus, it would likely mark pageblocks as 
> unsuitable
> for migration scanner, before it can reach them?

That's right.

> 
> > With this change, above test result is:
> > 
> > Kernel: Base vs Redesign
> > 
> > Test: hogger-frag-movable
> > 
> > Success(N)70  94
> > compact_stall3073642
> > compact_success   64 144
> > compact_fail 2433498
> > pgmigrate_success  3459215897219
> > compact_isolated   7397731899553
> > compact_migrate_scanned  228077059146745
> > compact_free_scanned 471031349566134
> > 
> > Test: hogger-frag-movable with free memory variation
> > 
> > 200MB-Success(N)70  94
> > 250MB-Success(N)38  93
> > 300MB-Success(N)29  89
> > 
> > Compaction gives us almost all possible high order page. Overhead is
> > highly increased, but, further patch will reduce it greatly
> > by adjusting depletion check with this new algorithm.
> > 
> > Signed-off-by: Joonsoo Kim 
> > ---
> >  mm/compaction.c | 145 
> > ++--
> >  1 file changed, 77 insertions(+), 68 deletions(-)
> > 
> > diff --git a/mm/compaction.c b/mm/compaction.c
> > index a259608..ca4d6d1 100644
> > --- a/mm/compaction.c
> > +++ b/mm/compaction.c
> > @@ -53,17 +53,17 @@ static const char *const compaction_status_string[] = {
> >  static unsigned long release_freepages(struct list_head *freelist)
> >  {
> > struct page *page, *next;
> > -   unsigned long high_pfn = 0;
> > +   unsigned long low_pfn = ULONG_MAX;
> >  
> > list_for_each_entry_safe(page, next, freelist, lru) {
> > unsigned long pfn = page_to_pfn(page);
> > list_del(>lru);
> > __free_page(page);
> > -   if (pfn > high_pfn)
> > -   high_pfn = pfn;
> > +   if (pfn < low_pfn)
> > +   low_pfn = pfn;
> > }
> >  
> > -   return high_pfn;
> > +   return low_pfn;
> 
> This assumes that the freelist won't contain both pages from the end of the
> zone, and from the beginning the zone after the free scanner has wrapped. 
> Which
> is true, but not immediately obvious, so it deserves some comment.

Okay. Will add it.

> >  }
> >  
> >  static void map_pages(struct list_head *list)
> > @@ -243,7 +243,7 @@ static void __reset_isolation_suitable(struct zone 
> > *zone)
> >  
> > zone->compact_cached_migrate_pfn[0] = start_pfn;
> > zone->compact_cached_migrate_pfn[1] = start_pfn;
> > -   zone->compact_cached_free_pfn = end_pfn;
> > +   zone->compact_cached_free_pfn = start_pfn;
> > zone->compact_blockskip_flush = false;
> >  
> > clear_bit(ZONE_COMPACTION_SCANALLFREE, >flags);
> > @@ -335,7 +335,7 @@ static void update_pageblock_skip(struct 
> > compact_control *cc,
> > if (!nr_isolated)
> > set_pageblock_skip_freescan(page);
> >  
> > -   if (pfn < zone->compact_cached_free_pfn)
> > +   if (pfn > zone->compact_cached_free_pfn)
> > zone->compact_cached_free_pfn = pfn;
> > }
> >  }
> > @@ -869,8 +869,11 @@ isolate_success:
> > nr_scanned, nr_isolated);
> >  
> > count_compact_events(COMPACTMIGRATE_SCANNED, nr_scanned);
> > -   if (nr_isolated)
> > +   if (nr_isolated) {
> > count_compact_events(COMPACTISOLATED, nr_isolated);
> > +   if (valid_page)
> > +   clear_pageblock_skip_freescan(valid_page);
> 
> This is explained in changelog, but a comment here would be useful too.

Okay.

> 

[PATCH v2 7/9] mm/compaction: redesign compaction

[Joonsoo Kim]

Currently, compaction works as following.
1) migration scanner scans from zone_start_pfn to zone_end_pfn
to find migratable pages
2) free scanner scans from zone_end_pfn to zone_start_pfn to
find free pages
3) If both scanner crossed, compaction is finished.

This algorithm has some drawbacks. 1) Back of the zone cannot be
scanned by migration scanner because migration scanner can't pass
over freepage scanner. So, although there are some high order page
candidates at back of the zone, we can't utilize it.
Another weakness is 2) compaction's success highly depends on amount
of freepage. Compaction can migrate used pages by amount of freepage
at maximum. If we can't make high order page by this effort, both
scanner should meet and compaction will fail.

We can easily observe problem 1) by following test.

Memory is artificially fragmented to make order 3 allocation hard. And,
most of pageblocks are changed to movable migratetype.

  System: 512 MB with 32 MB Zram
  Memory: 25% memory is allocated to make fragmentation and 200 MB is
occupied by memory hogger. Most pageblocks are movable
migratetype.
  Fragmentation: Successful order 3 allocation candidates may be around
1500 roughly.
  Allocation attempts: Roughly 3000 order 3 allocation attempts
with GFP_NORETRY. This value is determined to saturate allocation
success.

Test: hogger-frag-movable

Success(N)70
compact_stall307
compact_success   64
compact_fail 243
pgmigrate_success  34592
compact_isolated   73977
compact_migrate_scanned  2280770
compact_free_scanned 4710313

Column 'Success(N) are calculated by following equations.

Success(N) = successful allocation * 100 /
number of successful order-3 candidates

As mentioned above, there are roughly 1500 high order page candidates,
but, compaction just returns 70% of them, because migration scanner
can't pass over freepage scanner. With new compaction approach, it can
be increased to 94% by this patch.

To check 2), hogger-frag-movable benchmark is used again, but, with some
tweaks. Amount of allocated memory by memory hogger varys.

Test: hogger-frag-movable with free memory variation

Kernel: Base

200MB-Success(N)70
250MB-Success(N)38
300MB-Success(N)29

As background knowledge, up to 250MB, there is enough
memory to succeed all order-3 allocation attempts. In 300MB case,
available memory before starting allocation attempt is just 57MB,
so all of attempts cannot succeed.

Anyway, as free memory decreases, compaction success rate also decreases.
It is better to remove this dependency to get stable compaction result
in any case.

This patch solves these problems mentioned in above.
Freepage scanner is largely changed to scan zone from zone_start_pfn
to zone_end_pfn. And, by this change, compaction finish condition is also
changed that migration scanner reach zone_end_pfn. With these changes,
migration scanner can traverse anywhere in the zone.

To prevent back and forth migration within one compaction iteration,
freepage scanner marks skip-bit when scanning pageblock. migration scanner
checks it and will skip this marked pageblock so back and forth migration
cannot be possible in one compaction iteration.

If freepage scanner reachs the end of zone, it restarts at zone_start_pfn.
In this time, freepage scanner would scan the pageblock where migration
scanner has migrated some pages but fail to make high order page. This
leaved freepages means that they can't become high order page due to
the fragmentation so it is good source for freepage scanner.

With this change, above test result is:

Kernel: Base vs Redesign

Test: hogger-frag-movable

Success(N)70  94
compact_stall3073642
compact_success   64 144
compact_fail 2433498
pgmigrate_success  3459215897219
compact_isolated   7397731899553
compact_migrate_scanned  228077059146745
compact_free_scanned 471031349566134

Test: hogger-frag-movable with free memory variation

200MB-Success(N)70  94
250MB-Success(N)38  93
300MB-Success(N)29  89

Compaction gives us almost all possible high order page. Overhead is
highly increased, but, further patch will reduce it greatly
by adjusting depletion check with this new algorithm.

Signed-off-by: Joonsoo Kim 
---
 mm/compaction.c | 145 ++--
 1 file changed, 77 insertions(+), 68 deletions(-)

diff --git a/mm/compaction.c b/mm/compaction.c
index a259608..ca4d6d1 100644
--- a/mm/compaction.c
+++ b/mm/compaction.c
@@ -53,17 +53,17 @@ static const char *const compaction_status_string[] = {
 static unsigned long release_freepages(struct list_head *freelist)
 {
struct page *page, *next;
-   unsigned long 

[PATCH v2 7/9] mm/compaction: redesign compaction

[Joonsoo Kim]

Currently, compaction works as following.
1) migration scanner scans from zone_start_pfn to zone_end_pfn
to find migratable pages
2) free scanner scans from zone_end_pfn to zone_start_pfn to
find free pages
3) If both scanner crossed, compaction is finished.

This algorithm has some drawbacks. 1) Back of the zone cannot be
scanned by migration scanner because migration scanner can't pass
over freepage scanner. So, although there are some high order page
candidates at back of the zone, we can't utilize it.
Another weakness is 2) compaction's success highly depends on amount
of freepage. Compaction can migrate used pages by amount of freepage
at maximum. If we can't make high order page by this effort, both
scanner should meet and compaction will fail.

We can easily observe problem 1) by following test.

Memory is artificially fragmented to make order 3 allocation hard. And,
most of pageblocks are changed to movable migratetype.

  System: 512 MB with 32 MB Zram
  Memory: 25% memory is allocated to make fragmentation and 200 MB is
occupied by memory hogger. Most pageblocks are movable
migratetype.
  Fragmentation: Successful order 3 allocation candidates may be around
1500 roughly.
  Allocation attempts: Roughly 3000 order 3 allocation attempts
with GFP_NORETRY. This value is determined to saturate allocation
success.

Test: hogger-frag-movable

Success(N)70
compact_stall307
compact_success   64
compact_fail 243
pgmigrate_success  34592
compact_isolated   73977
compact_migrate_scanned  2280770
compact_free_scanned 4710313

Column 'Success(N) are calculated by following equations.

Success(N) = successful allocation * 100 /
number of successful order-3 candidates

As mentioned above, there are roughly 1500 high order page candidates,
but, compaction just returns 70% of them, because migration scanner
can't pass over freepage scanner. With new compaction approach, it can
be increased to 94% by this patch.

To check 2), hogger-frag-movable benchmark is used again, but, with some
tweaks. Amount of allocated memory by memory hogger varys.

Test: hogger-frag-movable with free memory variation

Kernel: Base

200MB-Success(N)70
250MB-Success(N)38
300MB-Success(N)29

As background knowledge, up to 250MB, there is enough
memory to succeed all order-3 allocation attempts. In 300MB case,
available memory before starting allocation attempt is just 57MB,
so all of attempts cannot succeed.

Anyway, as free memory decreases, compaction success rate also decreases.
It is better to remove this dependency to get stable compaction result
in any case.

This patch solves these problems mentioned in above.
Freepage scanner is largely changed to scan zone from zone_start_pfn
to zone_end_pfn. And, by this change, compaction finish condition is also
changed that migration scanner reach zone_end_pfn. With these changes,
migration scanner can traverse anywhere in the zone.

To prevent back and forth migration within one compaction iteration,
freepage scanner marks skip-bit when scanning pageblock. migration scanner
checks it and will skip this marked pageblock so back and forth migration
cannot be possible in one compaction iteration.

If freepage scanner reachs the end of zone, it restarts at zone_start_pfn.
In this time, freepage scanner would scan the pageblock where migration
scanner has migrated some pages but fail to make high order page. This
leaved freepages means that they can't become high order page due to
the fragmentation so it is good source for freepage scanner.

With this change, above test result is:

Kernel: Base vs Redesign

Test: hogger-frag-movable

Success(N)70  94
compact_stall3073642
compact_success   64 144
compact_fail 2433498
pgmigrate_success  3459215897219
compact_isolated   7397731899553
compact_migrate_scanned  228077059146745
compact_free_scanned 471031349566134

Test: hogger-frag-movable with free memory variation

200MB-Success(N)70  94
250MB-Success(N)38  93
300MB-Success(N)29  89

Compaction gives us almost all possible high order page. Overhead is
highly increased, but, further patch will reduce it greatly
by adjusting depletion check with this new algorithm.

Signed-off-by: Joonsoo Kim iamjoonsoo@lge.com
---
 mm/compaction.c | 145 ++--
 1 file changed, 77 insertions(+), 68 deletions(-)

diff --git a/mm/compaction.c b/mm/compaction.c
index a259608..ca4d6d1 100644
--- a/mm/compaction.c
+++ b/mm/compaction.c
@@ -53,17 +53,17 @@ static const char *const compaction_status_string[] = {
 static unsigned long release_freepages(struct list_head *freelist)
 {
struct page *page, *next;
-