mm/damon: introduce DAMON_STAT for simple and practical access monitoring

DAMON-based access monitoring is not simple due to required DAMON control and results visualizations. Introduce a static kernel module for making it simple. The module can be enabled without manual setup and provides access pattern metrics that easy to fetch and understand the practical access pattern information, namely estimated memory bandwidth and memory idle time percentiles.

Background and Problems
=======================

DAMON can be used for monitoring data access patterns of the system and workloads. Specifically, users can start DAMON to monitor access events on specific address space with fine controls including address ranges to monitor and time intervals between samplings and aggregations. The resulting access information snapshot contains access frequency (nr_accesses) and how long the frequency was kept (age) for each byte.

The monitoring usage is not simple and practical enough for production usage. Users should first start DAMON with a number of parameters, and wait until DAMON's monitoring results capture a reasonable amount of the time data (age). In production, such manual start and wait is impractical to capture useful information from a high number of machines in a timely manner.

The monitoring result is also too detailed to be used on production environments. The raw results are hard to be aggregated and/or compared for production environments having a large scale of time, space and machines fleet.

Users have to implement and use their own automation of DAMON control and results processing. It is repetitive and challenging since there is no good reference or guideline for such automation.

Solution: DAMON_STAT
====================

Implement such automation in kernel space as a static kernel module, namely DAMON_STAT. It can be enabled at build, boot, or run time via its build configuration or module parameter. It monitors the entire physical address space with monitoring intervals that auto-tuned for a reasonable amount of access observations and minimum overhead. It converts the raw monitoring results into simpler metrics that can easily be aggregated and compared, namely estimated memory bandwidth and idle time percentiles. Refer to the commit messages of the second and the third patches of this patch series for more details about the metrics.

Discussions
===========

The module aims to be useful on production environments constructed with a large number of machines that run a long time. The auto-tuned monitoring intervals ensure a reasonable quality of the outputs. The auto-tuning also ensures its overhead be reasonable and low enough to be enabled always on the production. The simplified monitoring results metrics can be useful for showing both coldness (idle time percentiles) and hotness (memory bandwidth) of the system's access pattern. We expect the information can be useful for assessing system memory utilization and inspiring optimizations or investigations on both kernel and user space memory management logics for large scale fleets.

We hence expect the module is good enough to be just used in most environments. For special cases that require a custom access monitoring automation, users will still benefit by using DAMON_STAT as a reference or a guideline for their specialized automation.

Revision History
================

Changes from RFC
(https://lore.kernel.org/[email protected])
- Add an admin-guide documentation
- Wordsmith commit messages
- Rebase to latest mm-new

SeongJae Park (4):
mm/damon: introduce DAMON_STAT module
mm/damon/stat: calculate and expose estimated memory bandwidth mm/damon/stat: calculate and expose idle time percentiles Docs/admin-guide/mm/damon: add DAMON_STAT usage document

 Documentation/admin-guide/mm/damon/index.rst |   1 +
 Documentation/admin-guide/mm/damon/stat.rst  |  69 ++++++
 mm/damon/Kconfig                             |  16 ++
 mm/damon/Makefile                            |   1 +
 mm/damon/stat.c                              | 245 +++++++++++++++++++
 5 files changed, 332 insertions(+)
 create mode 100644 Documentation/admin-guide/mm/damon/stat.rst
 create mode 100644 mm/damon/stat.c

base-commit: 90887f57d7a67917136e7c70d26fb3f2fcdc6f53

2.39.5

To use DAMON for monitoring access patterns of the system, users should manually start DAMON via DAMON sysfs ABI with a number of parameters for specifying the monitoring target address space, address ranges, and monitoring intervals. After that, users should also wait until desired amount of time data is captured into DAMON's monitoring results. It is bothersome and take a long time to be practical for access monitoring on large fleet level production environments.

For access-aware system operations use cases like proactive cold memory reclamation, similar problems existed. We we solved those by introducing dedicated static kernel modules such as DAMON_RECLAIM.

Implement such static kernel module for access monitoring, namely DAMON_STAT. It monitors the entire physical address space with auto-tuned monitoring intervals. The auto-tuning is set to capture 4 % of observable access events in each snapshot while keeping the sampling intervals 5 milliseconds in minimum and 10 seconds in maximum. From a few production environments, we confirmed this setup provides high quality monitoring results with minimum overheads. The module therefore receives only one user input, whether to enable or disable it. It can be set on build or boot time via build configuration or kernel boot command line. It can also be overridden at runtime.

Note that this commit only implements the DAMON control part of the module. Users could get the monitoring results via damon:damon_aggregated tracepoint, but that's of course not the recommended way. Following commits will implement convenient and optimized ways for serving the monitoring results to users.

---
 mm/damon/Kconfig  |  16 ++++++
 mm/damon/Makefile |   1 +
 mm/damon/stat.c   | 138 ++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 155 insertions(+)
 create mode 100644 mm/damon/stat.c

index 551745df011b..9f482e3adc67 100644
@@ -95,4 +95,20 @@ config DAMON_LRU_SORT
 	  protect frequently accessed (hot) pages while rarely accessed (cold)
 	  pages reclaimed first under memory pressure.
 
+config DAMON_STAT
+	bool "Build data access monitoring stat (DAMON_STAT)"
+	depends on DAMON_PADDR
+	help
+	  This builds the DAMON-based access monitoring statistics subsystem.
+	  It runs DAMON and expose access monitoring results in simple stat
+	  metrics.
+
+config DAMON_STAT_ENABLED_DEFAULT
+	bool "Enable DAMON_STAT by default"
+	depends on DAMON_PADDR
+	default DAMON_STAT
+	help
+	  Whether to enable DAMON_STAT by default.  Users can disable it in
+	  boot or runtime using its 'enabled' parameter.
+
 endmenu

index 8b49012ba8c3..d8d6bf5f8bff 100644
@@ -6,3 +6,4 @@ obj-$(CONFIG_DAMON_PADDR)	+= ops-common.o paddr.o
 obj-$(CONFIG_DAMON_SYSFS)	+= sysfs-common.o sysfs-schemes.o sysfs.o
 obj-$(CONFIG_DAMON_RECLAIM)	+= modules-common.o reclaim.o
 obj-$(CONFIG_DAMON_LRU_SORT)	+= modules-common.o lru_sort.o
+obj-$(CONFIG_DAMON_STAT)	+= modules-common.o stat.o

2.39.5

The raw form of DAMON's monitoring results captures many details of the information. However, not every bit of the information is always required for understanding practical access patterns. Especially on real world production systems of high scale time and size, the raw form is difficult to be aggregated and compared.

Convert the raw monitoring results into a single number metric, namely estimated memory bandwidth and expose it to users as a read-only DAMON_STAT parameter. The metric represents access intensiveness (hotness) of the system. It can easily be aggregated and compared for high level understanding of the access pattern on large systems.

---
 mm/damon/stat.c | 35 +++++++++++++++++++++++++++++++++++
 1 file changed, 35 insertions(+)

index 852848ce844e..f9ae44db265b 100644
@@ -28,8 +28,42 @@ static bool enabled __read_mostly = CONFIG_DAMON_STAT_ENABLED_DEFAULT;
 module_param_cb(enabled, &enabled_param_ops, &enabled, 0600);
 MODULE_PARM_DESC(enabled, "Enable of disable DAMON_STAT");
 
+static unsigned long estimated_memory_bandwidth __read_mostly;
+module_param(estimated_memory_bandwidth, ulong, 0400);
+MODULE_PARM_DESC(estimated_memory_bandwidth,
+		"Estimated memory bandwidth usage in bytes per second");
+
 static struct damon_ctx *damon_stat_context;
 
+static void damon_stat_set_estimated_memory_bandwidth(struct damon_ctx *c)
+{
+	struct damon_target *t;
+	struct damon_region *r;
+	unsigned long access_bytes = 0;
+
+	damon_for_each_target(t, c) {
+		damon_for_each_region(r, t)
+			access_bytes += (r->ar.end - r->ar.start) *
+				r->nr_accesses;
+	}
+	estimated_memory_bandwidth = access_bytes * USEC_PER_MSEC *
+		MSEC_PER_SEC / c->attrs.aggr_interval;
+}
+
+static int damon_stat_after_aggregation(struct damon_ctx *c)
+{
+	static unsigned long last_refresh_jiffies;
+
+	/* avoid unnecessarily frequent stat update */
+	if (time_before_eq(jiffies, last_refresh_jiffies +
+				msecs_to_jiffies(5 * MSEC_PER_SEC)))
+		return 0;
+	last_refresh_jiffies = jiffies;
+
+	damon_stat_set_estimated_memory_bandwidth(c);
+	return 0;
+}
+
 static struct damon_ctx *damon_stat_build_ctx(void)
 {
 	struct damon_ctx *ctx;

@@ -75,6 +109,7 @@ static struct damon_ctx *damon_stat_build_ctx(void)
 	damon_add_target(ctx, target);
 	if (damon_set_region_biggest_system_ram_default(target, &start, &end))
 		goto free_out;
+	ctx->callback.after_aggregation = damon_stat_after_aggregation;
 	return ctx;
 free_out:
 	damon_destroy_ctx(ctx);

2.39.5

Knowing how much memory is how cold can be useful for understanding coldness and utilization efficiency of memory. The raw form of DAMON's monitoring results has the information. Convert the raw results into the per-byte idle time distributions and expose it as percentiles metric to users, as a read-only DAMON_STAT parameter.

In detail, the metrics are calculated as follows. First, DAMON's per-region access frequency and age information is converted into per-byte idle time. If access frequency of a region is higher than zero, every byte of the region has zero idle time. If the access frequency of a region is zero, every byte of the region has idle time as the age of the region. Then the logic sorts the per-byte idle times and provides the value at 0/100, 1/100, ..., 99/100 and 100/100 location of the sorted array.

The metric can be easily aggregated and compared on large scale production systems. For example, if an average of 75-th percentile idle time of machines that collected on similar time is two minutes, it means the system's 25 percent memory is not accessed at all for two minutes or more on average. If a workload considers two minutes as unit work time, we can conclude its working set size is only 75 percent of the memory. If the system utilizes proactive reclamation and it supports coldness-based thresholds like DAMON_RECLAIM, the idle time percentiles can be used to find a more safe or aggressive coldness threshold for aimed memory saving.

---
 mm/damon/stat.c | 72 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 72 insertions(+)

index f9ae44db265b..7ef13ea22221 100644
@@ -33,6 +33,11 @@ module_param(estimated_memory_bandwidth, ulong, 0400);
 MODULE_PARM_DESC(estimated_memory_bandwidth,
 		"Estimated memory bandwidth usage in bytes per second");
 
+static unsigned long memory_idle_ms_percentiles[101] __read_mostly = {0,};
+module_param_array(memory_idle_ms_percentiles, ulong, NULL, 0400);
+MODULE_PARM_DESC(memory_idle_ms_percentiles,
+		"Memory idle time percentiles in milliseconds");
+
 static struct damon_ctx *damon_stat_context;
 
 static void damon_stat_set_estimated_memory_bandwidth(struct damon_ctx *c)

@@ -50,6 +55,72 @@ static void damon_stat_set_estimated_memory_bandwidth(struct damon_ctx *c)
 		MSEC_PER_SEC / c->attrs.aggr_interval;
 }
 
+static unsigned int damon_stat_idletime(const struct damon_region *r)
+{
+	if (r->nr_accesses)
+		return 0;
+	return r->age + 1;
+}
+
+static int damon_stat_cmp_regions(const void *a, const void *b)
+{
+	const struct damon_region *ra = *(const struct damon_region **)a;
+	const struct damon_region *rb = *(const struct damon_region **)b;
+
+	return damon_stat_idletime(ra) - damon_stat_idletime(rb);
+}
+
+static int damon_stat_sort_regions(struct damon_ctx *c,
+		struct damon_region ***sorted_ptr, int *nr_regions_ptr,
+		unsigned long *total_sz_ptr)
+{
+	struct damon_target *t;
+	struct damon_region *r;
+	struct damon_region **region_pointers;
+	unsigned int nr_regions = 0;
+	unsigned long total_sz = 0;
+
+	damon_for_each_target(t, c) {
+		/* there is only one target */
+		region_pointers = kmalloc_array(damon_nr_regions(t),
+				sizeof(*region_pointers), GFP_KERNEL);
+		if (!region_pointers)
+			return -ENOMEM;
+		damon_for_each_region(r, t) {
+			region_pointers[nr_regions++] = r;
+			total_sz += r->ar.end - r->ar.start;
+		}
+	}
+	sort(region_pointers, nr_regions, sizeof(*region_pointers),
+			damon_stat_cmp_regions, NULL);
+	*sorted_ptr = region_pointers;
+	*nr_regions_ptr = nr_regions;
+	*total_sz_ptr = total_sz;
+	return 0;
+}
+
+static void damon_stat_set_idletime_percentiles(struct damon_ctx *c)
+{
+	struct damon_region **sorted_regions, *region;
+	int nr_regions;
+	unsigned long total_sz, accounted_bytes = 0;
+	int err, i, next_percentile = 0;
+
+	err = damon_stat_sort_regions(c, &sorted_regions, &nr_regions,
+			&total_sz);
+	if (err)
+		return;
+	for (i = 0; i < nr_regions; i++) {
+		region = sorted_regions[i];
+		accounted_bytes += region->ar.end - region->ar.start;
+		while (next_percentile <= accounted_bytes * 100 / total_sz)
+			memory_idle_ms_percentiles[next_percentile++] =
+				damon_stat_idletime(region) *
+				c->attrs.aggr_interval / USEC_PER_MSEC;
+	}
+	kfree(sorted_regions);
+}
+
 static int damon_stat_after_aggregation(struct damon_ctx *c)
 {
 	static unsigned long last_refresh_jiffies;

@@ -61,6 +132,7 @@ static int damon_stat_after_aggregation(struct damon_ctx *c)
 	last_refresh_jiffies = jiffies;
 
 	damon_stat_set_estimated_memory_bandwidth(c);
+	damon_stat_set_idletime_percentiles(c);
 	return 0;
 }
 

2.39.5

Document DAMON_STAT usage and add a link to it on DAMON admin-guide page.

---
 Documentation/admin-guide/mm/damon/index.rst |  1 +
 Documentation/admin-guide/mm/damon/stat.rst  | 69 ++++++++++++++++++++
 2 files changed, 70 insertions(+)
 create mode 100644 Documentation/admin-guide/mm/damon/stat.rst

index bc7e976120e0..3ce3164480c7 100644
@@ -14,3 +14,4 @@ access monitoring and access-aware system operations.
    usage
    reclaim
    lru_sort
+   stat

2.39.5

Hi SeongJae,

Thanks for your work.

I see the description looks good but it'd be useful if you could share some execution commands and expected output examples that some newbies can get better ideas.

I honestly do not have a clear idea how I can use this kind of static kernel modules as general users although I have developed some features of DAMON.

So could you please help?

Thanks,
Honggyu

Hi Honggyu,

Thank you for the feedback. In my humble opinion, nevertheless, this is what the fourth patch of this series is aiming to provide. And thanks to your comment, I now realize I forgot mentioning this on the above comment.

Of course we can add execution commands and output example here, but without understanding of the metrics, it would just look like mysterious numbers. Meanhile, user interface of the module is simply module parameters that should be familiar to most kernel users, so I don't think it necessarily deserves example commands.

I agree this cover letter is not enough for getting clear idea of how readers can use this feature. Thank you for letting me realize this. But I think this cover letter might be better to keep the brevity, as long as it points where readers can get necessary details. What do you think about revising this cover letter to

1. point the fourth patch for usage of DAMON_STAT, and
2. elaborate the fact that readers are recommended to read the metric definitions and usages to get more clear idea of DAMON_STAT?

Thanks,
SJ

[...]