[RFC PATCH 0/3] mm/damon/schemes: Extend DAMOS for Proactive LRU-lists Sorting

[RFC PATCH 0/3] mm/damon/schemes: Extend DAMOS for Proactive LRU-lists Sorting

[SeongJae Park]

From: SeongJae Park <sjpark@amazon.de>

Introduction
============

As page-granularity access checking overhead could be too significant on huge
systems, LRU lists are normally sorted reactively and partially for special
events including explicit system calls and memory pressure.  As a result, LRU
lists could be not well sorted to be used for finding good reclamation target
pages, especially when memory pressure is first happened after a while.

Proactive reclamation is well known to be helpful for minimizing the memory
pressure performance drops.  However, proactive reclamation could incur
additional I/O, so not a best option for some cases.  For an example, cloud
block storages would charge each I/O.

Using DAMON for Proactive LRU-lists Sorting (PLRUS) could be helpful for this
situation, as DAMON can identify access patterns while inducing only controlled
overhead.  The idea is simple.  Find hot pages and cold pages using DAMON, and
do 'mark_page_accessed()' for the hot pages while doing 'deactivate_page()' for
the cold pages.  This patchset extends DAMON to support PLRUS by introducing a
new DAMOS action for doing the 'mark_page_accessed()' to memory regions of a
specific access pattern, and supporting 'cold' DAMOS action from the physical
address space monitoring operations set.

In terms of making reclamation less harmful, PLRUS will work similar to the
proactive reclamation, but avoids the additional I/Os.  Of course, PLRUS will
not reduce memory utilization on its own, unlike proactive reclamation.  If
that's a problem, doing DAMON-based proactive reclamation (DAMON_RECLAIM)
simultaneously for only super cold pages, or for severe memory pressure could
work.  One additional advantage of PLRUS is that it makes LRU lists a more
trustworthy source of access patterns.

Example DAMON-based Operation Schemes for PLRUS
===============================================

So, users will be able to do PLRUS via DAMON-based Operation Schemes (DAMOS)
after applying this patchset.  An example of such DAMOS config for PLRUS would
be something like below.  Sorry for the crippy format.  Please refer to the
parser script[1] for detail of the format.  In short, this config asks DAMON to

1. find any memory regions of >=4K size having shown at least some access
   (approximately 20 accesses per 100 sampling) and apply 'mark_accessed()' to
   those using up to 2% CPU time.  Under the CPU time limit, apply the function
   to regions having higher access frequency and kept the access frequency
   longer first.

2. find any memory regions of >=4K size having shown no access for 200ms or
   more and 'deactivate()' those using up to 2% CPU time.  Under the CPU time
   limit, apply the function to regions kept the no access longer first.

    # format is:
    # <min/max size> <min/max frequency (0-100)> <min/max age> <action> \
    # 		<quota> <weights> <watermarks>
 
    # LRU-activate hot pages (more hot ones first) under 2% CPU usage limit
    4K  max         20 max           min max         hot \
    		20ms 0B 1s      0 7 3   free_mem_rate 5s 1000 999 0
 
    # LRU-deactivate cold pages (colder ones first) under 2% CPU usage limit
    4K  max         min min         20ms max         cold \
    		20ms 0B 1s      0 3 7   free_mem_rate 5s 1000 999 0

[1] https://github.com/awslabs/damo/blob/next/_convert_damos.py

Evaluation
==========

To show the effect of PLRUS, I ran PARSEC3 and SPLASH-2X benchmarks under below
variant kernels and measured the runtime of each workload.

- orig: Latest mm-unstable kernel + this patchset, but no DAMON scheme applied.
- mprs: Same to orig but have artificial memory pressure.
- plrus: Same to mprs but above example PLRUS scheme is applied to the physical
         address space of the system.

For the artificial memory pressure, I set memory.limit_in_bytes to 75% of the
running workload's peak RSS, wait 3 seconds, remove the pressure by setting it
to 200% of the running workload's peak RSS, wait 30 seconds, and repeat the
procedure until the workload finishes[1].  I use zram based swap device.  The
tests are automated[2].

I repeat the tests five times and calculate average runtime of the five
measurements.  The results are as below:

    runtime_secs            orig    mprs    plrus   plrus/mprs
    parsec3/blackscholes    139.35  139.68  140.37  1.00
    parsec3/bodytrack       124.67  127.26  128.31  1.01
    parsec3/canneal         207.61  400.95  355.23  0.89
    parsec3/dedup           18.30   18.84   19.30   1.02
    parsec3/facesim         350.42  353.69  349.14  0.99
    parsec3/fluidanimate    338.57  337.16  342.18  1.01
    parsec3/freqmine        434.39  435.67  436.49  1.00
    parsec3/raytrace        182.24  186.18  189.08  1.02
    parsec3/streamcluster   634.49  2993.27 2576.04 0.86
    parsec3/swaptions       221.68  221.84  221.97  1.00
    parsec3/vips            87.82   103.01  103.18  1.00
    parsec3/x264            108.92  132.82  128.22  0.97
    splash2x/barnes         130.30  135.87  138.52  1.02
    splash2x/fft            62.09   98.33   99.85   1.02
    splash2x/lu_cb          132.15  135.49  135.22  1.00
    splash2x/lu_ncb         149.89  154.92  155.26  1.00
    splash2x/ocean_cp       80.04   108.20  113.85  1.05
    splash2x/ocean_ncp      163.70  217.40  231.09  1.06
    splash2x/radiosity      142.32  143.13  144.50  1.01
    splash2x/radix          50.28   78.21   85.96   1.10
    splash2x/raytrace       133.75  134.21  136.21  1.01
    splash2x/volrend        120.39  121.72  120.87  0.99
    splash2x/water_nsquared 373.37  388.31  398.72  1.03
    splash2x/water_spatial  133.81  143.73  144.00  1.00
    total                   4520.54 7309.87 6893.55 0.94
    average                 188.36  304.58  287.23  0.94

The second, third, and fourth cells shows the runtime of each workload under
the configs in seconds, and the fifth cell shows the plrus runtime divided by
mprs runtime.

On average, 'plrus' achieves about 6% speedup under memory pressure.  For the
two best cases (parsec3/canneal and parsec3/streamcluster), 'plrus' achieves
about 11% and 14% speedup under memory pressure.  Please note that the scheme
is not tuned for each workload, applied to entire system memory, and uses only
up to 4% single CPU time.

[1] https://github.com/awslabs/damon-tests/blob/next/perf/runners/back/0009_memcg_pressure.sh
[2] https://github.com/awslabs/damon-tests/tree/next/perf

Sequence of Patches
===================

The first patch cleans up DAMOS_PAGEOUT handling code of physical address space
monitoring operations implementation for easier extension of the code.  The
second patch implements a new DAMOS action called 'hot', which applies
'mark_page_accessed()' to the pages under the memory regions having the target
access pattern.  Finally, the third patch makes the physical address space
monitoring operations implementation supports the 'cold' action, which applies
'deactivate_page()' to the pages under the memory regions having the target
access pattern.

SeongJae Park (3):
  mm/damon/paddr: move DAMOS_PAGEOUT handling to a separate function
  mm/damon/schemes: Support 'hot' action
  mm/damon/paddr: Support DAMOS_COLD

 include/linux/damon.h |  2 ++
 mm/damon/ops-common.c | 42 ++++++++++++++++++++++++++++++
 mm/damon/ops-common.h |  2 ++
 mm/damon/paddr.c      | 60 ++++++++++++++++++++++++++++++++++++++-----
 mm/damon/sysfs.c      |  1 +
 5 files changed, 101 insertions(+), 6 deletions(-)

-- 
2.17.1

[RFC PATCH 1/3] mm/damon/paddr: move DAMOS_PAGEOUT handling to a separate function

[SeongJae Park]

This commit moves code for DAMOS_PAGEOUT handling to a separate function
other than damon_pa_apply_scheme() to make damon_pa_apply_scheme()
prepared for later additional DAMOS actions support.

Signed-off-by: SeongJae Park <sj@kernel.org>
---
 mm/damon/paddr.c | 20 ++++++++++++++------
 1 file changed, 14 insertions(+), 6 deletions(-)

diff --git a/mm/damon/paddr.c b/mm/damon/paddr.c
index 21474ae63bc7..08deee12ebfd 100644
--- a/mm/damon/paddr.c
+++ b/mm/damon/paddr.c
@@ -204,16 +204,11 @@ static unsigned int damon_pa_check_accesses(struct damon_ctx *ctx)
 	return max_nr_accesses;
 }
 
-static unsigned long damon_pa_apply_scheme(struct damon_ctx *ctx,
-		struct damon_target *t, struct damon_region *r,
-		struct damos *scheme)
+static unsigned long damon_pa_pageout(struct damon_region *r)
 {
 	unsigned long addr, applied;
 	LIST_HEAD(page_list);
 
-	if (scheme->action != DAMOS_PAGEOUT)
-		return 0;
-
 	for (addr = r->ar.start; addr < r->ar.end; addr += PAGE_SIZE) {
 		struct page *page = damon_get_page(PHYS_PFN(addr));
 
@@ -238,6 +233,19 @@ static unsigned long damon_pa_apply_scheme(struct damon_ctx *ctx,
 	return applied * PAGE_SIZE;
 }
 
+static unsigned long damon_pa_apply_scheme(struct damon_ctx *ctx,
+		struct damon_target *t, struct damon_region *r,
+		struct damos *scheme)
+{
+	switch (scheme->action) {
+	case DAMOS_PAGEOUT:
+		return damon_pa_pageout(r);
+	default:
+		break;
+	}
+	return 0;
+}
+
 static int damon_pa_scheme_score(struct damon_ctx *context,
 		struct damon_target *t, struct damon_region *r,
 		struct damos *scheme)
-- 
2.17.1

[RFC PATCH 2/3] mm/damon/schemes: Support 'hot' action

[SeongJae Park]

This commit adds another DAMOS action called 'hot'.  The action marks
pages in the memory area of the taregt access pattern to be marked as
accessed.  Specifically, calls 'mark_page_accessed()'.  This is supposed
to be used for memory regions having frequent access so that hot pages
could be more protected under memory pressure.

Signed-off-by: SeongJae Park <sj@kernel.org>
---
 include/linux/damon.h |  2 ++
 mm/damon/ops-common.c | 42 ++++++++++++++++++++++++++++++++++++++++++
 mm/damon/ops-common.h |  2 ++
 mm/damon/paddr.c      | 20 ++++++++++++++++++++
 mm/damon/sysfs.c      |  1 +
 5 files changed, 67 insertions(+)

diff --git a/include/linux/damon.h b/include/linux/damon.h
index 7c62da31ce4b..ed5338c3133d 100644
--- a/include/linux/damon.h
+++ b/include/linux/damon.h
@@ -87,6 +87,7 @@ struct damon_target {
  * @DAMOS_HUGEPAGE:	Call ``madvise()`` for the region with MADV_HUGEPAGE.
  * @DAMOS_NOHUGEPAGE:	Call ``madvise()`` for the region with MADV_NOHUGEPAGE.
  * @DAMOS_STAT:		Do nothing but count the stat.
+ * @DAMOS_HOT:		Mark the region as hot.
  * @NR_DAMOS_ACTIONS:	Total number of DAMOS actions
  */
 enum damos_action {
@@ -96,6 +97,7 @@ enum damos_action {
 	DAMOS_HUGEPAGE,
 	DAMOS_NOHUGEPAGE,
 	DAMOS_STAT,		/* Do nothing but only record the stat */
+	DAMOS_HOT,
 	NR_DAMOS_ACTIONS,
 };
 
diff --git a/mm/damon/ops-common.c b/mm/damon/ops-common.c
index e346cc10d143..fe9288025bae 100644
--- a/mm/damon/ops-common.c
+++ b/mm/damon/ops-common.c
@@ -131,3 +131,45 @@ int damon_pageout_score(struct damon_ctx *c, struct damon_region *r,
 	/* Return coldness of the region */
 	return DAMOS_MAX_SCORE - hotness;
 }
+
+int damon_hot_score(struct damon_ctx *c, struct damon_region *r,
+			struct damos *s)
+{
+	unsigned int max_nr_accesses;
+	int freq_subscore;
+	unsigned int age_in_sec;
+	int age_in_log, age_subscore;
+	unsigned int freq_weight = s->quota.weight_nr_accesses;
+	unsigned int age_weight = s->quota.weight_age;
+	int hotness;
+
+	max_nr_accesses = c->aggr_interval / c->sample_interval;
+	freq_subscore = r->nr_accesses * DAMON_MAX_SUBSCORE / max_nr_accesses;
+
+	age_in_sec = (unsigned long)r->age * c->aggr_interval / 1000000;
+	for (age_in_log = 0; age_in_log < DAMON_MAX_AGE_IN_LOG && age_in_sec;
+			age_in_log++, age_in_sec >>= 1)
+		;
+
+	/* If frequency is 0, higher age means it's colder */
+	if (freq_subscore == 0)
+		age_in_log *= -1;
+
+	/*
+	 * Now age_in_log is in [-DAMON_MAX_AGE_IN_LOG, DAMON_MAX_AGE_IN_LOG].
+	 * Scale it to be in [0, 100] and set it as age subscore.
+	 */
+	age_in_log += DAMON_MAX_AGE_IN_LOG;
+	age_subscore = age_in_log * DAMON_MAX_SUBSCORE /
+		DAMON_MAX_AGE_IN_LOG / 2;
+
+	hotness = (freq_weight * freq_subscore + age_weight * age_subscore);
+	if (freq_weight + age_weight)
+		hotness /= freq_weight + age_weight;
+	/*
+	 * Transform it to fit in [0, DAMOS_MAX_SCORE]
+	 */
+	hotness = hotness * DAMOS_MAX_SCORE / DAMON_MAX_SUBSCORE;
+
+	return hotness;
+}
diff --git a/mm/damon/ops-common.h b/mm/damon/ops-common.h
index e790cb5f8fe0..52329ff361cd 100644
--- a/mm/damon/ops-common.h
+++ b/mm/damon/ops-common.h
@@ -14,3 +14,5 @@ void damon_pmdp_mkold(pmd_t *pmd, struct mm_struct *mm, unsigned long addr);
 
 int damon_pageout_score(struct damon_ctx *c, struct damon_region *r,
 			struct damos *s);
+int damon_hot_score(struct damon_ctx *c, struct damon_region *r,
+			struct damos *s);
diff --git a/mm/damon/paddr.c b/mm/damon/paddr.c
index 08deee12ebfd..69980b922bf4 100644
--- a/mm/damon/paddr.c
+++ b/mm/damon/paddr.c
@@ -233,6 +233,22 @@ static unsigned long damon_pa_pageout(struct damon_region *r)
 	return applied * PAGE_SIZE;
 }
 
+static unsigned long damon_pa_mark_accessed(struct damon_region *r)
+{
+	unsigned long addr, applied = 0;
+
+	for (addr = r->ar.start; addr < r->ar.end; addr += PAGE_SIZE) {
+		struct page *page = damon_get_page(PHYS_PFN(addr));
+
+		if (!page)
+			continue;
+		mark_page_accessed(page);
+		put_page(page);
+		applied++;
+	}
+	return applied * PAGE_SIZE;
+}
+
 static unsigned long damon_pa_apply_scheme(struct damon_ctx *ctx,
 		struct damon_target *t, struct damon_region *r,
 		struct damos *scheme)
@@ -240,6 +256,8 @@ static unsigned long damon_pa_apply_scheme(struct damon_ctx *ctx,
 	switch (scheme->action) {
 	case DAMOS_PAGEOUT:
 		return damon_pa_pageout(r);
+	case DAMOS_HOT:
+		return damon_pa_mark_accessed(r);
 	default:
 		break;
 	}
@@ -253,6 +271,8 @@ static int damon_pa_scheme_score(struct damon_ctx *context,
 	switch (scheme->action) {
 	case DAMOS_PAGEOUT:
 		return damon_pageout_score(context, r, scheme);
+	case DAMOS_HOT:
+		return damon_hot_score(context, r, scheme);
 	default:
 		break;
 	}
diff --git a/mm/damon/sysfs.c b/mm/damon/sysfs.c
index 09f9e8ca3d1f..a1de2278f8c2 100644
--- a/mm/damon/sysfs.c
+++ b/mm/damon/sysfs.c
@@ -763,6 +763,7 @@ static const char * const damon_sysfs_damos_action_strs[] = {
 	"hugepage",
 	"nohugepage",
 	"stat",
+	"hot",
 };
 
 static struct damon_sysfs_scheme *damon_sysfs_scheme_alloc(
-- 
2.17.1

[RFC PATCH 3/3] mm/damon/paddr: Support DAMOS_COLD

[SeongJae Park]

DAMOS_COLD is currently supported by the virtual address spaces
monitoring operations set (vaddr).  This commit adds support of the
action to the physical address space monitoring operations set (paddr).
Using this together with hot DAMOS action, users can proactively sort
LRU lists so that performance degradation under memory pressure can be
reduced.

Signed-off-by: SeongJae Park <sj@kernel.org>
---
 mm/damon/paddr.c | 20 ++++++++++++++++++++
 1 file changed, 20 insertions(+)

diff --git a/mm/damon/paddr.c b/mm/damon/paddr.c
index 69980b922bf4..761b1580271c 100644
--- a/mm/damon/paddr.c
+++ b/mm/damon/paddr.c
@@ -249,6 +249,22 @@ static unsigned long damon_pa_mark_accessed(struct damon_region *r)
 	return applied * PAGE_SIZE;
 }
 
+static unsigned long damon_pa_cold(struct damon_region *r)
+{
+	unsigned long addr, applied = 0;
+
+	for (addr = r->ar.start; addr < r->ar.end; addr += PAGE_SIZE) {
+		struct page *page = damon_get_page(PHYS_PFN(addr));
+
+		if (!page)
+			continue;
+		deactivate_page(page);
+		put_page(page);
+		applied++;
+	}
+	return applied * PAGE_SIZE;
+}
+
 static unsigned long damon_pa_apply_scheme(struct damon_ctx *ctx,
 		struct damon_target *t, struct damon_region *r,
 		struct damos *scheme)
@@ -258,6 +274,8 @@ static unsigned long damon_pa_apply_scheme(struct damon_ctx *ctx,
 		return damon_pa_pageout(r);
 	case DAMOS_HOT:
 		return damon_pa_mark_accessed(r);
+	case DAMOS_COLD:
+		return damon_pa_cold(r);
 	default:
 		break;
 	}
@@ -273,6 +291,8 @@ static int damon_pa_scheme_score(struct damon_ctx *context,
 		return damon_pageout_score(context, r, scheme);
 	case DAMOS_HOT:
 		return damon_hot_score(context, r, scheme);
+	case DAMOS_COLD:
+		return damon_pageout_score(context, r, scheme);
 	default:
 		break;
 	}
-- 
2.17.1