[RFC PATCH 0/3] mm/damon: provide pseudo moving sum probe_hits

[RFC PATCH 0/3] mm/damon: provide pseudo moving sum probe_hits

[SeongJae Park]

Data attribute counters (probe_hits) of DAMON are managed in the
classical way.  The counter value is accumulated every sampling
interval, gets the complete view at the end of the aggregation interval,
and is reset when the next aggregation interval starts.  Hence, the
complete view can be retrieved only once per aggregation interval, which
can be quite long.  With the suggested intervals autotuning setup, it
becomes 2-4 seconds in common real production systems.  It can span up
to 200 seconds in theory.  This will restrict online monitoring use case
of DAMON.

Actually DAMON is already providing online monitoring of probe_hits.
DAMON sysfs interface exposes the values via schemes tried regions
directory files.  However, due to the above mentioned limitation, it
usually shows only partially accumulated hit counters and therefore not
useful.

DAMOS is not using probe_hits at the moment.  In the future, using it
can further strengthen DAMOS.  However, a recommended setup of DAMOS is
utilizing sampling/aggregation intervals auto-tuning, and having its own
DAMOS apply_interval (1 second is mostly recommended).  In the setup,
DAMOS will nearly always show incompletely accumulated probe_hits, which
will not really be useful.

Data frequency counter (nr_accesses) of DAMON solves this problem using
the pseudo moving sum value.  The infrastructure is not limited to
nr_accesses but general sampling based counters.  Maintain and provide
the pseudo moving sum of probe_hits similar to nr_accesses, using the
infrastructure.

Tests
=====

On an idle system, I ran DAMON with an attribute probe filter for
non-anonymous page, using DAMON user-space tool, like below.

    $ sudo ./damo start --probe_filter allow non anon

Because the system is idle, nearly all memory is not an anonymous page
but a free page, so the probe_hits are expected to be nearly always
full.  In this setup, since the sampling interval is 5ms and the
aggregation interval is 100ms, the counter value is expected to always
be near 20.

On kernels not having this series, if we retrieve the probe hits in an
arbitrary time that is likely not aligned to the aggregation interval,
the values are usually much lower than the expectation like below.  This
is because the tool is showing the incompletely aggregated values.

    $ sudo ./damo report access --format append region "probe_hits: <probe hits>"
    heatmap: 00000000000000000000000000000000000000008999999711111111000000000000000000000000
    # min/max temperatures: -1,630,000,000, 0, column size: 99.800 MiB
    intervals: sample 5 ms aggr 100 ms (max access hz 200)
    0   addr 4.000 KiB    size 3.898 GiB   access 0 hz   age 16.300 s     probe_hits: 11
    1   addr 3.898 GiB    size 77.859 MiB  access 0 hz   age 1.500 s      probe_hits: 11
    2   addr 3.974 GiB    size 700.770 MiB access 0 hz   age 0 ns         probe_hits: 11
    3   addr 4.659 GiB    size 791.078 MiB access 0 hz   age 13.700 s     probe_hits: 11
    4   addr 5.431 GiB    size 1.472 GiB   access 0 hz   age 15.800 s     probe_hits: 11
    5   addr 6.903 GiB    size 915.059 MiB access 0 hz   age 15.300 s     probe_hits: 11
    memory bw estimate: 0 B per second
    total size: 7.797 GiB
    record DAMON intervals: sample 5 ms, aggr 100 ms

After applying this series, I was able to reliably show the expected
results like below.

    $ sudo ./damo report access --format append region "probe_hits: <probe hits>"
    heatmap: 00000000333333330000000166666665111111139999999855555555333333333333333444444444
    intervals: sample 5 ms aggr 100 ms (max access hz 200)
    0   addr 4.000 KiB    size 790.496 MiB access 0 hz   age 1 m 33.300 s probe_hits: 20
    1   addr 790.500 MiB  size 791.160 MiB access 0 hz   age 1 m 15.400 s probe_hits: 19
    2   addr 1.545 GiB    size 792.316 MiB access 0 hz   age 1 m 32.400 s probe_hits: 19
    3   addr 2.318 GiB    size 795.465 MiB access 0 hz   age 1 m 2.600 s  probe_hits: 19
    4   addr 3.095 GiB    size 797.102 MiB access 0 hz   age 1 m 23.500 s probe_hits: 20
    5   addr 3.874 GiB    size 797.293 MiB access 0 hz   age 47.900 s     probe_hits: 20
    6   addr 4.652 GiB    size 787.516 MiB access 0 hz   age 1 m 3.800 s  probe_hits: 20
    7   addr 5.421 GiB    size 784.461 MiB access 0 hz   age 1 m 14.400 s probe_hits: 19
    8   addr 6.187 GiB    size 795.621 MiB access 0 hz   age 1 m 15.700 s probe_hits: 20
    9   addr 6.964 GiB    size 798.000 MiB access 0 hz   age 1 m 10.200 s probe_hits: 20
    10  addr 7.744 GiB    size 54.566 MiB  access 0 hz   age 1 m 9.300 s  probe_hits: 20
    memory bw estimate: 0 B per second
    total size: 7.797 GiB
    record DAMON intervals: sample 5 ms, aggr 100 ms

Patches Sequence
================

Patch 1 adds probe_hits counters for values that fully accumulated in
the last aggregation interval.  This is required for using the moving
sum infrastructure.  Patch 2 introduces a function for getting the
moving sum values on demand, using the infrastructure.   Finally, patch
3 updates the DAMON sysfs interface to expose the moving sum values to
the schemes tried regions directory.

SeongJae Park (3):
  mm/damon: add damon_region->last_probe_hits
  mm/damon/core: introduce damon_probe_hits_mvsum()
  mm/damon/sysfs-schemes: set probe hits as pseudo moving sums

 include/linux/damon.h    |  4 +++-
 mm/damon/core.c          | 31 +++++++++++++++++++++++++++++--
 mm/damon/sysfs-schemes.c |  3 ++-
 3 files changed, 34 insertions(+), 4 deletions(-)


base-commit: 2c13bf619ad5282c48f178288dc632822d0629da
-- 
2.47.3

[RFC PATCH 1/3] mm/damon: add damon_region->last_probe_hits

[SeongJae Park]

Add new damon_region filed, last_probe_hits.  Maintain fully accumulated
probe_hits values from the last aggregation interval in the field.

Signed-off-by: SeongJae Park <sj@kernel.org>
---
 include/linux/damon.h |  2 +-
 mm/damon/core.c       | 10 ++++++++--
 2 files changed, 9 insertions(+), 3 deletions(-)

diff --git a/include/linux/damon.h b/include/linux/damon.h
index fc3d467dc2e34..f0dd45ca788f5 100644
--- a/include/linux/damon.h
+++ b/include/linux/damon.h
@@ -70,10 +70,10 @@ struct damon_region {
 	unsigned int nr_accesses;
 	unsigned char probe_hits[DAMON_MAX_PROBES];
 	struct list_head list;
-
 	unsigned int age;
 /* private: Internal value for age calculation. */
 	unsigned int last_nr_accesses;
+	unsigned char last_probe_hits[DAMON_MAX_PROBES];
 };
 
 /**
diff --git a/mm/damon/core.c b/mm/damon/core.c
index 4f7954b383d18..e84f2f1b07cc6 100644
--- a/mm/damon/core.c
+++ b/mm/damon/core.c
@@ -304,8 +304,10 @@ struct damon_region *damon_new_region(unsigned long start, unsigned long end)
 	region->ar.start = start;
 	region->ar.end = end;
 	region->nr_accesses = 0;
-	for (i = 0; i < DAMON_MAX_PROBES; i++)
+	for (i = 0; i < DAMON_MAX_PROBES; i++) {
 		region->probe_hits[i] = 0;
+		region->last_probe_hits[i] = 0;
+	}
 	INIT_LIST_HEAD(&region->list);
 
 	region->age = 0;
@@ -2024,8 +2026,10 @@ static void kdamond_reset_aggregated(struct damon_ctx *c)
 					damon_nr_regions(t), nr_probes);
 			r->last_nr_accesses = r->nr_accesses;
 			r->nr_accesses = 0;
-			for (i = 0; i < DAMON_MAX_PROBES; i++)
+			for (i = 0; i < DAMON_MAX_PROBES; i++) {
+				r->last_probe_hits[i] = r->probe_hits[i];
 				r->probe_hits[i] = 0;
+			}
 		}
 		ti++;
 	}
@@ -3216,6 +3220,8 @@ static void damon_split_region_at(struct damon_target *t,
 	new->nr_accesses = r->nr_accesses;
 	/* todo: do this for only installed probes */
 	memcpy(new->probe_hits, r->probe_hits, sizeof(r->probe_hits));
+	memcpy(new->last_probe_hits, r->last_probe_hits,
+			sizeof(r->last_probe_hits));
 
 	damon_insert_region(new, r, damon_next_region(r), t);
 }
-- 
2.47.3

[RFC PATCH 2/3] mm/damon/core: introduce damon_probe_hits_mvsum()

[SeongJae Park]

Implement a function for getting a reasonable best effort quality pseudo
moving sums of probe_hits on demands.  It reuses the internal function
for the pseudo moving sum for data access frequency (nr_accesses).

Signed-off-by: SeongJae Park <sj@kernel.org>
---
 include/linux/damon.h |  2 ++
 mm/damon/core.c       | 21 +++++++++++++++++++++
 2 files changed, 23 insertions(+)

diff --git a/include/linux/damon.h b/include/linux/damon.h
index f0dd45ca788f5..46394171cd2d0 100644
--- a/include/linux/damon.h
+++ b/include/linux/damon.h
@@ -1005,6 +1005,8 @@ void damon_add_probe(struct damon_ctx *ctx, struct damon_probe *probe);
 struct damon_region *damon_new_region(unsigned long start, unsigned long end);
 unsigned int damon_nr_accesses_mvsum(struct damon_region *r,
 		struct damon_ctx *ctx);
+unsigned char damon_probe_hits_mvsum(int probe_idx, struct damon_region *r,
+		struct damon_ctx *ctx);
 
 int damon_set_regions(struct damon_target *t, struct damon_addr_range *ranges,
 		unsigned int nr_ranges, unsigned long min_region_sz);
diff --git a/mm/damon/core.c b/mm/damon/core.c
index e84f2f1b07cc6..b5f63f2f726be 100644
--- a/mm/damon/core.c
+++ b/mm/damon/core.c
@@ -275,6 +275,27 @@ unsigned int damon_nr_accesses_mvsum(struct damon_region *r,
 			left_window_bp);
 }
 
+unsigned char damon_probe_hits_mvsum(int probe_idx, struct damon_region *r,
+		struct damon_ctx *ctx)
+{
+	unsigned long sample_interval, aggr_interval;
+	unsigned long window_len, left_window, left_window_bp;
+
+	sample_interval = ctx->attrs.sample_interval ? : 1;
+	aggr_interval =  ctx->attrs.aggr_interval ? : 1;
+	window_len = aggr_interval / sample_interval;
+	if (time_after_eq(ctx->passed_sample_intervals,
+				ctx->next_aggregation_sis))
+		left_window = 0;
+	else
+		left_window = ctx->next_aggregation_sis -
+			ctx->passed_sample_intervals;
+	left_window_bp = mult_frac(left_window, 10000, window_len);
+
+	return damon_mvsum(r->probe_hits[probe_idx],
+			r->last_probe_hits[probe_idx], left_window_bp);
+}
+
 #ifdef CONFIG_DAMON_DEBUG_SANITY
 static void damon_verify_new_region(unsigned long start, unsigned long end)
 {
-- 
2.47.3

[RFC PATCH 3/3] mm/damon/sysfs-schemes: set probe hits as pseudo moving sums

[SeongJae Park]

DAMON sysfs interface exposes damon_region->probe_hits via probe hit
files.  Because the counters are completed only at the end of the
aggregation interval, users can show incomplete values if they requested
the file content update (update_schemes_tried_regions command) in the
middle of an aggregation interval.  Set the value as the pseudo moving
sum value of the counter, similar to that for nr_accesses.

Signed-off-by: SeongJae Park <sj@kernel.org>
---
 mm/damon/sysfs-schemes.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/mm/damon/sysfs-schemes.c b/mm/damon/sysfs-schemes.c
index 30a007bcf82f4..06ebf381c32b6 100644
--- a/mm/damon/sysfs-schemes.c
+++ b/mm/damon/sysfs-schemes.c
@@ -112,7 +112,8 @@ static int damos_sysfs_probes_add_dirs(struct damos_sysfs_probes *probes,
 		struct damos_sysfs_probe *sys_probe;
 		int err;
 
-		sys_probe = damos_sysfs_probe_alloc(region->probe_hits[i]);
+		sys_probe = damos_sysfs_probe_alloc(
+				damon_probe_hits_mvsum(i, region, ctx));
 		if (!sys_probe) {
 			damos_sysfs_probes_rm_dirs(probes);
 			return -ENOMEM;
-- 
2.47.3