Introduce Data Access MONitor (DAMON)

From: SeongJae Park <[email protected]>

DAMON is a data access monitoring framework for the Linux kernel. The core mechanisms of DAMON make it

- accurate (the monitoring output is useful enough for DRAM level performance-centric memory management; It might be inappropriate for CPU cache levels, though),
- light-weight (the monitoring overhead is normally low enough to be applied online), and
- scalable (the upper-bound of the overhead is in constant range regardless of the size of target workloads).

Using this framework, hence, we can easily write efficient kernel space data access monitoring applications. For example, the kernel's memory management mechanisms can make advanced decisions using this. Experimental data access aware optimization works that incurring high access monitoring overhead could implemented again on top of this.

Due to its simple and flexible interface, providing user space interface would be also easy. Then, user space users who have some special workloads can write personalized applications for better understanding and optimizations of their workloads and systems.

---

Nevertheless, this commit is defining and implementing only basic access check part without the overhead-accuracy handling core logic. The basic access check is as below.

The output of DAMON says what memory regions are how frequently accessed for a given duration. The resolution of the access frequency is controlled by setting ``sampling interval`` and ``aggregation interval``. In detail, DAMON checks access to each page per ``sampling interval`` and aggregates the results. In other words, counts the number of the accesses to each region. After each ``aggregation interval`` passes, DAMON calls callback functions that previously registered by users so that users can read the aggregated results and then clears the results. This can be described in below simple pseudo-code::

while monitoring_on:
for page in monitoring_target:
if accessed(page):
nr_accesses[page] += 1
if time() % aggregation_interval == 0:
for callback in user_registered_callbacks:
callback(monitoring_target, nr_accesses)
for page in monitoring_target:
nr_accesses[page] = 0
sleep(sampling interval)

The target regions constructed at the beginning of the monitoring and updated after each ``regions_update_interval``, because the target regions could be dynamically changed (e.g., mmap() or memory hotplug). The monitoring overhead of this mechanism will arbitrarily increase as the size of the target workload grows.

The basic monitoring primitives for actual access check and dynamic target regions construction aren't in the core part of DAMON. Instead, it allows users to implement their own primitives that optimized for

their use case and configure DAMON to use those. In other words, users cannot use current version of DAMON without some additional works.

Following commits will implement the core mechanisms for the overhead-accuracy control and default primitives implementations.

Signed-off-by SeongJae Park <[email protected]>

Reviewed-by Leonard Foerster <[email protected]>

---
 include/linux/damon.h | 167 ++++++++++++++++++++++
 mm/Kconfig            |   2 +
 mm/Makefile           |   1 +
 mm/damon/Kconfig      |  15 ++
 mm/damon/Makefile     |   3 +
 mm/damon/core.c       | 316 ++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 504 insertions(+)
 create mode 100644 include/linux/damon.h
 create mode 100644 mm/damon/Kconfig
 create mode 100644 mm/damon/Makefile
 create mode 100644 mm/damon/core.c

include/linux/damon.h new file +11 -0

new file mode 100644
index 000000000000..387fa4399fc8
@@ -0,0 +1,167 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * DAMON api
+ *
+ * Author: SeongJae Park <[email protected]>
+ */
+
+#ifndef _DAMON_H_
+#define _DAMON_H_
+
+#include <linux/mutex.h>

include/linux/damon.h new file +52 -0

+ * @prepare_access_checks:     Prepares next access check of target regions.
+ * @check_accesses:            Checks the access of target regions.
+ * @reset_aggregated:          Resets aggregated accesses monitoring results.
+ * @target_valid:              Determine if the target is valid.
+ * @cleanup:                   Cleans up the context.
+ *
+ * DAMON can be extended for various address spaces and usages.  For this,
+ * users should register the low level primitives for their target address
+ * space and usecase via the &damon_ctx.primitive.  Then, the monitoring thread
+ * calls @init_target_regions and @prepare_access_checks before starting the
+ * monitoring, @update_target_regions after each
+ * &damon_ctx.regions_update_interval, and @check_accesses, @target_valid and
+ * @prepare_access_checks after each &damon_ctx.sample_interval.  Finally,
+ * @reset_aggregated is called after each &damon_ctx.aggr_interval.
+ *
+ * @init_target_regions should construct proper monitoring target regions and
+ * link those to the DAMON context struct.  The regions should be defined by
+ * user and saved in @damon_ctx.target.
+ * @update_target_regions should update the monitoring target regions for
+ * current status.
+ * @prepare_access_checks should manipulate the monitoring regions to be
+ * prepared for the next access check.
+ * @check_accesses should check the accesses to each region that made after the
+ * last preparation and update the number of observed accesses of each region.
+ * @reset_aggregated should reset the access monitoring results that aggregated
+ * by @check_accesses.
+ * @target_valid should check whether the target is still valid for the
+ * monitoring.
+ * @cleanup is called from @kdamond just before its termination.  After this
+ * call, only @kdamond_lock and @kdamond will be touched.
+ */
+struct damon_primitive {
+       void (*init_target_regions)(struct damon_ctx *context);
+       void (*update_target_regions)(struct damon_ctx *context);
+       void (*prepare_access_checks)(struct damon_ctx *context);
+       void (*check_accesses)(struct damon_ctx *context);
+       void (*reset_aggregated)(struct damon_ctx *context);
+       bool (*target_valid)(void *target);
+       void (*cleanup)(struct damon_ctx *context);
+};
+
+/*
+ * struct damon_callback       Monitoring events notification callbacks.
+ *
+ * @before_start:      Called before starting the monitoring.
+ * @after_sampling:    Called after each sampling.
+ * @after_aggregation: Called after each aggregation.
+ * @before_terminate:  Called before terminating the monitoring.
+ * @private:           User private data.
+ *
+ * The monitoring thread (&damon_ctx->kdamond) calls @before_start and
+ * @before_terminate just before starting and finishing the monitoring,

include/linux/damon.h new file +8 -0

+ */
+struct damon_callback {
+       void *private;
+
+       int (*before_start)(struct damon_ctx *context);
+       int (*after_sampling)(struct damon_ctx *context);
+       int (*after_aggregation)(struct damon_ctx *context);
+       int (*before_terminate)(struct damon_ctx *context);

include/linux/damon.h new file +66 -0

+ *
+ * For each @sample_interval, DAMON checks whether each region is accessed or
+ * not.  It aggregates and keeps the access information (number of accesses to
+ * each region) for @aggr_interval time.  DAMON also checks whether the target
+ * memory regions need update (e.g., by ``mmap()`` calls from the application,
+ * in case of virtual memory monitoring) and applies the changes for each
+ * @regions_update_interval.  All time intervals are in micro-seconds.  Please
+ * refer to &struct damon_primitive and &struct damon_callback for more detail.
+ *
+ * @kdamond:           Kernel thread who does the monitoring.
+ * @kdamond_stop:      Notifies whether kdamond should stop.
+ * @kdamond_lock:      Mutex for the synchronizations with @kdamond.
+ *
+ * For each monitoring context, one kernel thread for the monitoring is
+ * created.  The pointer to the thread is stored in @kdamond.
+ *
+ * Once started, the monitoring thread runs until explicitly required to be
+ * terminated or every monitoring target is invalid.  The validity of the
+ * targets is checked via the &damon_primitive.target_valid of @primitive.  The
+ * termination can also be explicitly requested by writing non-zero to
+ * @kdamond_stop.  The thread sets @kdamond to NULL when it terminates.
+ * Therefore, users can know whether the monitoring is ongoing or terminated by
+ * reading @kdamond.  Reads and writes to @kdamond and @kdamond_stop from
+ * outside of the monitoring thread must be protected by @kdamond_lock.
+ *
+ * Note that the monitoring thread protects only @kdamond and @kdamond_stop via
+ * @kdamond_lock.  Accesses to other fields must be protected by themselves.
+ *
+ * @primitive: Set of monitoring primitives for given use cases.
+ * @callback:  Set of callbacks for monitoring events notifications.
+ *
+ * @target:    Pointer to the user-defined monitoring target.
+ */
+struct damon_ctx {
+       unsigned long sample_interval;
+       unsigned long aggr_interval;
+       unsigned long regions_update_interval;
+
+/* private */
+       struct timespec64 last_aggregation;
+       struct timespec64 last_regions_update;
+
+/* public */
+       struct task_struct *kdamond;
+       bool kdamond_stop;
+       struct mutex kdamond_lock;
+
+       struct damon_primitive primitive;
+       struct damon_callback callback;
+
+       void *target;
+};
+
+#ifdef CONFIG_DAMON
+
+struct damon_ctx *damon_new_ctx(void);
+void damon_destroy_ctx(struct damon_ctx *ctx);
+int damon_set_attrs(struct damon_ctx *ctx, unsigned long sample_int,
+               unsigned long aggr_int, unsigned long regions_update_int);
+
+int damon_start(struct damon_ctx **ctxs, int nr_ctxs);
+int damon_stop(struct damon_ctx **ctxs, int nr_ctxs);
+
+#endif /* CONFIG_DAMON */
+
+#endif /* _DAMON_H */

mm/Kconfig +2 -0

index 390165ffbb0f..b97f2e8ab83f 100644
@@ -859,4 +859,6 @@ config ARCH_HAS_HUGEPD
 config MAPPING_DIRTY_HELPERS
         bool
 
+source "mm/damon/Kconfig"
+
 endmenu

mm/Makefile +1 -0

index d73aed0fc99c..8022b8f04096 100644
@@ -120,3 +120,4 @@ obj-$(CONFIG_MEMFD_CREATE) += memfd.o
 obj-$(CONFIG_MAPPING_DIRTY_HELPERS) += mapping_dirty_helpers.o
 obj-$(CONFIG_PTDUMP_CORE) += ptdump.o
 obj-$(CONFIG_PAGE_REPORTING) += page_reporting.o
+obj-$(CONFIG_DAMON) += damon/

mm/damon/Kconfig new file +15 -0

new file mode 100644
index 000000000000..d00e99ac1a15
@@ -0,0 +1,15 @@
+# SPDX-License-Identifier: GPL-2.0-only
+
+menu "Data Access Monitoring"
+
+config DAMON
+       bool "DAMON: Data Access Monitoring Framework"
+       help
+         This builds a framework that allows kernel subsystems to monitor
+         access frequency of each memory region. The information can be useful
+         for performance-centric DRAM level memory management.
+
+         See https://damonitor.github.io/doc/html/latest-damon/index.html for
+         more information.
+
+endmenu

mm/damon/Makefile new file +3 -0

new file mode 100644
index 000000000000..4fd2edb4becf
@@ -0,0 +1,3 @@
+# SPDX-License-Identifier: GPL-2.0
+
+obj-$(CONFIG_DAMON)            := core.o

mm/damon/core.c new file +269 -0

new file mode 100644
index 000000000000..8963804efdf9
@@ -0,0 +1,316 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * Data Access Monitor
+ *
+ * Author: SeongJae Park <[email protected]>
+ */
+
+#define pr_fmt(fmt) "damon: " fmt
+
+#include <linux/damon.h>
+#include <linux/delay.h>
+#include <linux/kthread.h>
+#include <linux/slab.h>
+
+static DEFINE_MUTEX(damon_lock);
+static int nr_running_ctxs;
+
+struct damon_ctx *damon_new_ctx(void)
+{
+       struct damon_ctx *ctx;
+
+       ctx = kzalloc(sizeof(*ctx), GFP_KERNEL);
+       if (!ctx)
+               return NULL;
+
+       ctx->sample_interval = 5 * 1000;
+       ctx->aggr_interval = 100 * 1000;
+       ctx->regions_update_interval = 1000 * 1000;
+
+       ktime_get_coarse_ts64(&ctx->last_aggregation);
+       ctx->last_regions_update = ctx->last_aggregation;
+
+       mutex_init(&ctx->kdamond_lock);
+
+       ctx->target = NULL;
+
+       return ctx;
+}
+
+void damon_destroy_ctx(struct damon_ctx *ctx)
+{
+       kfree(ctx);
+}
+
+/**
+ * damon_set_attrs() - Set attributes for the monitoring.
+ * @ctx:               monitoring context
+ * @sample_int:                time interval between samplings
+ * @aggr_int:          time interval between aggregations
+ * @regions_update_int:        time interval between target regions update
+ *
+ * This function should not be called while the kdamond is running.
+ * Every time interval is in micro-seconds.
+ *
+ * Return: 0 on success, negative error code otherwise.
+ */
+int damon_set_attrs(struct damon_ctx *ctx, unsigned long sample_int,
+                   unsigned long aggr_int, unsigned long regions_update_int)
+{
+       ctx->sample_interval = sample_int;
+       ctx->aggr_interval = aggr_int;
+       ctx->regions_update_interval = regions_update_int;
+
+       return 0;
+}
+
+static bool damon_kdamond_running(struct damon_ctx *ctx)
+{
+       bool running;
+
+       mutex_lock(&ctx->kdamond_lock);
+       running = ctx->kdamond != NULL;
+       mutex_unlock(&ctx->kdamond_lock);
+
+       return running;
+}
+
+static int kdamond_fn(void *data);
+
+/*
+ * __damon_start() - Starts monitoring with given context.
+ * @ctx:       monitoring context
+ *
+ * This function should be called while damon_lock is hold.
+ *
+ * Return: 0 on success, negative error code otherwise.
+ */
+static int __damon_start(struct damon_ctx *ctx)
+{
+       int err = -EBUSY;
+
+       mutex_lock(&ctx->kdamond_lock);
+       if (!ctx->kdamond) {
+               err = 0;
+               ctx->kdamond_stop = false;
+               ctx->kdamond = kthread_create(kdamond_fn, ctx, "kdamond.%d",
+                               nr_running_ctxs);
+               if (IS_ERR(ctx->kdamond))
+                       err = PTR_ERR(ctx->kdamond);
+               else
+                       wake_up_process(ctx->kdamond);
+       }
+       mutex_unlock(&ctx->kdamond_lock);
+
+       return err;
+}
+
+/**
+ * damon_start() - Starts the monitorings for a given group of contexts.
+ * @ctxs:      an array of the pointers for contexts to start monitoring
+ * @nr_ctxs:   size of @ctxs
+ *
+ * This function starts a group of monitoring threads for a group of monitoring
+ * contexts.  One thread per each context is created and run in parallel.  The
+ * caller should handle synchronization between the threads by itself.  If a
+ * group of threads that created by other 'damon_start()' call is currently
+ * running, this function does nothing but returns -EBUSY.
+ *
+ * Return: 0 on success, negative error code otherwise.
+ */
+int damon_start(struct damon_ctx **ctxs, int nr_ctxs)
+{
+       int i;
+       int err = 0;
+
+       mutex_lock(&damon_lock);
+       if (nr_running_ctxs) {
+               mutex_unlock(&damon_lock);
+               return -EBUSY;
+       }
+
+       for (i = 0; i < nr_ctxs; i++) {
+               err = __damon_start(ctxs[i]);
+               if (err)
+                       break;
+               nr_running_ctxs++;
+       }
+       mutex_unlock(&damon_lock);
+
+       return err;
+}
+
+/*
+ * __damon_stop() - Stops monitoring of given context.
+ * @ctx:       monitoring context
+ *
+ * Return: 0 on success, negative error code otherwise.
+ */
+static int __damon_stop(struct damon_ctx *ctx)
+{
+       mutex_lock(&ctx->kdamond_lock);
+       if (ctx->kdamond) {
+               ctx->kdamond_stop = true;
+               mutex_unlock(&ctx->kdamond_lock);
+               while (damon_kdamond_running(ctx))
+                       usleep_range(ctx->sample_interval,
+                                       ctx->sample_interval * 2);
+               return 0;
+       }
+       mutex_unlock(&ctx->kdamond_lock);
+
+       return -EPERM;
+}
+
+/**
+ * damon_stop() - Stops the monitorings for a given group of contexts.
+ * @ctxs:      an array of the pointers for contexts to stop monitoring
+ * @nr_ctxs:   size of @ctxs
+ *
+ * Return: 0 on success, negative error code otherwise.
+ */
+int damon_stop(struct damon_ctx **ctxs, int nr_ctxs)
+{
+       int i, err = 0;
+
+       for (i = 0; i < nr_ctxs; i++) {
+               /* nr_running_ctxs is decremented in kdamond_fn */
+               err = __damon_stop(ctxs[i]);
+               if (err)
+                       return err;
+       }
+
+       return err;
+}
+
+/*
+ * damon_check_reset_time_interval() - Check if a time interval is elapsed.
+ * @baseline:  the time to check whether the interval has elapsed since
+ * @interval:  the time interval (microseconds)
+ *
+ * See whether the given time interval has passed since the given baseline
+ * time.  If so, it also updates the baseline to current time for next check.
+ *
+ * Return:     true if the time interval has passed, or false otherwise.
+ */
+static bool damon_check_reset_time_interval(struct timespec64 *baseline,
+               unsigned long interval)
+{
+       struct timespec64 now;
+
+       ktime_get_coarse_ts64(&now);
+       if ((timespec64_to_ns(&now) - timespec64_to_ns(baseline)) <
+                       interval * 1000)
+               return false;
+       *baseline = now;
+       return true;
+}
+
+/*
+ * Check whether it is time to flush the aggregated information
+ */
+static bool kdamond_aggregate_interval_passed(struct damon_ctx *ctx)
+{
+       return damon_check_reset_time_interval(&ctx->last_aggregation,
+                       ctx->aggr_interval);
+}
+
+/*
+ * Check whether it is time to check and apply the target monitoring regions
+ *
+ * Returns true if it is.
+ */
+static bool kdamond_need_update_regions(struct damon_ctx *ctx)
+{
+       return damon_check_reset_time_interval(&ctx->last_regions_update,
+                       ctx->regions_update_interval);
+}
+
+/*
+ * Check whether current monitoring should be stopped
+ *
+ * The monitoring is stopped when either the user requested to stop, or all
+ * monitoring targets are invalid.
+ *
+ * Returns true if need to stop current monitoring.
+ */
+static bool kdamond_need_stop(struct damon_ctx *ctx)
+{
+       bool stop;
+
+       mutex_lock(&ctx->kdamond_lock);
+       stop = ctx->kdamond_stop;
+       mutex_unlock(&ctx->kdamond_lock);
+       if (stop)
+               return true;
+
+       if (!ctx->primitive.target_valid)
+               return false;
+
+       return !ctx->primitive.target_valid(ctx->target);
+}
+
+static void set_kdamond_stop(struct damon_ctx *ctx)
+{
+       mutex_lock(&ctx->kdamond_lock);
+       ctx->kdamond_stop = true;
+       mutex_unlock(&ctx->kdamond_lock);
+}
+
+/*
+ * The monitoring daemon that runs as a kernel thread
+ */
+static int kdamond_fn(void *data)
+{
+       struct damon_ctx *ctx = (struct damon_ctx *)data;
+
+       pr_info("kdamond (%d) starts\n", ctx->kdamond->pid);
+
+       if (ctx->primitive.init_target_regions)

mm/damon/core.c new file +4 -0

+
+               usleep_range(ctx->sample_interval, ctx->sample_interval + 1);
+
+               if (ctx->primitive.check_accesses)

mm/damon/core.c new file +23 -1

+               if (kdamond_need_update_regions(ctx)) {
+                       if (ctx->primitive.update_target_regions)
+                               ctx->primitive.update_target_regions(ctx);
+               }
+       }
+
+       if (ctx->callback.before_terminate &&
+                       ctx->callback.before_terminate(ctx))
+               set_kdamond_stop(ctx);
+       if (ctx->primitive.cleanup)
+               ctx->primitive.cleanup(ctx);
+
+       pr_debug("kdamond (%d) finishes\n", ctx->kdamond->pid);
+       mutex_lock(&ctx->kdamond_lock);
+       ctx->kdamond = NULL;
+       mutex_unlock(&ctx->kdamond_lock);
+
+       mutex_lock(&damon_lock);
+       nr_running_ctxs--;
+       mutex_unlock(&damon_lock);
+
+       do_exit(0);
+}
--

2.17.1

First I would like you to prune your To/CC list.

Quoted 14 lines

From: SeongJae Park <[email protected]>

DAMON is a data access monitoring framework for the Linux kernel. The core mechanisms of DAMON make it

- accurate (the monitoring output is useful enough for DRAM level performance-centric memory management; It might be inappropriate for CPU cache levels, though),
- light-weight (the monitoring overhead is normally low enough to be applied online), and
- scalable (the upper-bound of the overhead is in constant range regardless of the size of target workloads).

Quoted 5 lines

Using this framework, hence, we can easily write efficient kernel space data access monitoring applications. For example, the kernel's memory management mechanisms can make advanced decisions using this. Experimental data access aware optimization works that incurring high access monitoring overhead could implemented again on top of this.

*could again be implemented on*

Quoted 24 lines

Due to its simple and flexible interface, providing user space interface would be also easy. Then, user space users who have some special workloads can write personalized applications for better understanding and optimizations of their workloads and systems.

---

Nevertheless, this commit is defining and implementing only basic access check part without the overhead-accuracy handling core logic. The basic access check is as below.

The output of DAMON says what memory regions are how frequently accessed for a given duration. The resolution of the access frequency is controlled by setting ``sampling interval`` and ``aggregation interval``. In detail, DAMON checks access to each page per ``sampling interval`` and aggregates the results. In other words, counts the number of the accesses to each region. After each ``aggregation interval`` passes, DAMON calls callback functions that previously registered by users so that users can read the aggregated results and then clears the results. This can be described in below simple pseudo-code::

Quoted 11 lines

while monitoring_on:
for page in monitoring_target:
if accessed(page):
nr_accesses[page] += 1
if time() % aggregation_interval == 0:
for callback in user_registered_callbacks:
callback(monitoring_target, nr_accesses)
for page in monitoring_target:
nr_accesses[page] = 0
sleep(sampling interval)

The above is a good example and I was hoping to see the almost same actual code.

Quoted 7 lines

The target regions constructed at the beginning of the monitoring and updated after each ``regions_update_interval``, because the target regions could be dynamically changed (e.g., mmap() or memory hotplug). The monitoring overhead of this mechanism will arbitrarily increase as the size of the target workload grows.

Quoted 3 lines

The basic monitoring primitives for actual access check and dynamic target regions construction aren't in the core part of DAMON. Instead, it allows users to implement their own primitives that optimized for

'that are optimized for'

Quoted 44 lines

their use case and configure DAMON to use those. In other words, users cannot use current version of DAMON without some additional works.

Following commits will implement the core mechanisms for the overhead-accuracy control and default primitives implementations.

Signed-off-by SeongJae Park <[email protected]>

Reviewed-by Leonard Foerster <[email protected]>

---
 include/linux/damon.h | 167 ++++++++++++++++++++++
 mm/Kconfig            |   2 +
 mm/Makefile           |   1 +
 mm/damon/Kconfig      |  15 ++
 mm/damon/Makefile     |   3 +
 mm/damon/core.c       | 316 ++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 504 insertions(+)
 create mode 100644 include/linux/damon.h
 create mode 100644 mm/damon/Kconfig
 create mode 100644 mm/damon/Makefile
 create mode 100644 mm/damon/core.c

include/linux/damon.h new file +16 -0

new file mode 100644
index 000000000000..387fa4399fc8
@@ -0,0 +1,167 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * DAMON api
+ *
+ * Author: SeongJae Park <[email protected]>
+ */
+
+#ifndef _DAMON_H_
+#define _DAMON_H_
+
+#include <linux/mutex.h>
+#include <linux/time64.h>
+#include <linux/types.h>
+
+struct damon_ctx;
+

include/linux/damon.h line 21

Quoted 5 lines

include/linux/damon.h new file +5 -0

+/**
+ * struct damon_primitive      Monitoring primitives for given use cases.
+ *
+ * @init_target_regions:       Constructs initial monitoring target regions.
+ * @update_target_regions:     Updates monitoring target regions.

The 'region' here still does not feel right. I prefer to rename the above two to just init() and update().

Quoted 59 lines

include/linux/damon.h new file +58 -0

+ * @prepare_access_checks:     Prepares next access check of target regions.
+ * @check_accesses:            Checks the access of target regions.
+ * @reset_aggregated:          Resets aggregated accesses monitoring results.
+ * @target_valid:              Determine if the target is valid.
+ * @cleanup:                   Cleans up the context.
+ *
+ * DAMON can be extended for various address spaces and usages.  For this,
+ * users should register the low level primitives for their target address
+ * space and usecase via the &damon_ctx.primitive.  Then, the monitoring thread
+ * calls @init_target_regions and @prepare_access_checks before starting the
+ * monitoring, @update_target_regions after each
+ * &damon_ctx.regions_update_interval, and @check_accesses, @target_valid and
+ * @prepare_access_checks after each &damon_ctx.sample_interval.  Finally,
+ * @reset_aggregated is called after each &damon_ctx.aggr_interval.
+ *
+ * @init_target_regions should construct proper monitoring target regions and
+ * link those to the DAMON context struct.  The regions should be defined by
+ * user and saved in @damon_ctx.target.
+ * @update_target_regions should update the monitoring target regions for
+ * current status.
+ * @prepare_access_checks should manipulate the monitoring regions to be
+ * prepared for the next access check.
+ * @check_accesses should check the accesses to each region that made after the
+ * last preparation and update the number of observed accesses of each region.
+ * @reset_aggregated should reset the access monitoring results that aggregated
+ * by @check_accesses.
+ * @target_valid should check whether the target is still valid for the
+ * monitoring.
+ * @cleanup is called from @kdamond just before its termination.  After this
+ * call, only @kdamond_lock and @kdamond will be touched.
+ */
+struct damon_primitive {
+       void (*init_target_regions)(struct damon_ctx *context);
+       void (*update_target_regions)(struct damon_ctx *context);
+       void (*prepare_access_checks)(struct damon_ctx *context);
+       void (*check_accesses)(struct damon_ctx *context);
+       void (*reset_aggregated)(struct damon_ctx *context);
+       bool (*target_valid)(void *target);
+       void (*cleanup)(struct damon_ctx *context);
+};
+
+/*
+ * struct damon_callback       Monitoring events notification callbacks.
+ *
+ * @before_start:      Called before starting the monitoring.
+ * @after_sampling:    Called after each sampling.
+ * @after_aggregation: Called after each aggregation.
+ * @before_terminate:  Called before terminating the monitoring.
+ * @private:           User private data.
+ *
+ * The monitoring thread (&damon_ctx->kdamond) calls @before_start and
+ * @before_terminate just before starting and finishing the monitoring,
+ * respectively.  Therefore, those are good places for installing and cleaning
+ * @private.
+ *
+ * The monitoring thread calls @after_sampling and @after_aggregation for each
+ * of the sampling intervals and aggregation intervals, respectively.
+ * Therefore, users can safely access the monitoring results without additional

include/linux/damon.h line 83

Quoted 4 lines

include/linux/damon.h new file +4 -0

+ * protection.  For the reason, users are recommended to use these callback for
+ * the accesses to the results.
+ *
+ * If any callback returns non-zero, monitoring stops.

I am not sure if this is the right patch to add this struct. Either we need to add text why this is needed or add this patch when the real user i.e. debugfs interface is added.

Quoted 14 lines

include/linux/damon.h new file +13 -0

+ */
+struct damon_callback {
+       void *private;
+
+       int (*before_start)(struct damon_ctx *context);
+       int (*after_sampling)(struct damon_ctx *context);
+       int (*after_aggregation)(struct damon_ctx *context);
+       int (*before_terminate)(struct damon_ctx *context);
+};
+
+/**
+ * struct damon_ctx - Represents a context for each monitoring.  This is the
+ * main interface that allows users to set the attributes and get the results

include/linux/damon.h line 101

Quoted 5 lines

include/linux/damon.h new file +5 -0

+ * of the monitoring.
+ *
+ * @sample_interval:           The time between access samplings.
+ * @aggr_interval:             The time between monitor results aggregations.
+ * @regions_update_interval:   The time between monitor regions updates.

regions_update_internal should be part of the primitive abstraction and the update() callback internally can check this field.

Quoted 55 lines

mm/Kconfig +2 -0

index 390165ffbb0f..b97f2e8ab83f 100644
@@ -859,4 +859,6 @@ config ARCH_HAS_HUGEPD
 config MAPPING_DIRTY_HELPERS
         bool
 
+source "mm/damon/Kconfig"
+
 endmenu

mm/Makefile +1 -0

index d73aed0fc99c..8022b8f04096 100644
@@ -120,3 +120,4 @@ obj-$(CONFIG_MEMFD_CREATE) += memfd.o
 obj-$(CONFIG_MAPPING_DIRTY_HELPERS) += mapping_dirty_helpers.o
 obj-$(CONFIG_PTDUMP_CORE) += ptdump.o
 obj-$(CONFIG_PAGE_REPORTING) += page_reporting.o
+obj-$(CONFIG_DAMON) += damon/

mm/damon/Kconfig new file +15 -0

new file mode 100644
index 000000000000..d00e99ac1a15
@@ -0,0 +1,15 @@
+# SPDX-License-Identifier: GPL-2.0-only
+
+menu "Data Access Monitoring"
+
+config DAMON
+       bool "DAMON: Data Access Monitoring Framework"
+       help
+         This builds a framework that allows kernel subsystems to monitor
+         access frequency of each memory region. The information can be useful
+         for performance-centric DRAM level memory management.
+
+         See https://damonitor.github.io/doc/html/latest-damon/index.html for
+         more information.
+
+endmenu

mm/damon/Makefile new file +3 -0

new file mode 100644
index 000000000000..4fd2edb4becf
@@ -0,0 +1,3 @@
+# SPDX-License-Identifier: GPL-2.0
+
+obj-$(CONFIG_DAMON)            := core.o

mm/damon/core.c new file +0 -0

new file mode 100644
index 000000000000..8963804efdf9

Quoted 15 lines

mm/damon/core.c new file +15 -0

+/*
+ * The monitoring daemon that runs as a kernel thread
+ */
+static int kdamond_fn(void *data)
+{
+       struct damon_ctx *ctx = (struct damon_ctx *)data;
+
+       pr_info("kdamond (%d) starts\n", ctx->kdamond->pid);
+
+       if (ctx->primitive.init_target_regions)
+               ctx->primitive.init_target_regions(ctx);
+       if (ctx->callback.before_start && ctx->callback.before_start(ctx))
+               set_kdamond_stop(ctx);
+
+       while (!kdamond_need_stop(ctx)) {

mm/damon/core.c line 279

Quoted 5 lines

mm/damon/core.c new file +5 -0

+               if (ctx->primitive.prepare_access_checks)
+                       ctx->primitive.prepare_access_checks(ctx);
+               if (ctx->callback.after_sampling &&
+                               ctx->callback.after_sampling(ctx))
+                       set_kdamond_stop(ctx);

Is 'break' needed here? Or do we want to complete this iteration (same for the set_kdamond_stop() below)?

Quoted 5 lines

mm/damon/core.c new file +4 -0

+
+               usleep_range(ctx->sample_interval, ctx->sample_interval + 1);
+
+               if (ctx->primitive.check_accesses)

mm/damon/core.c line 293

Quoted 10 lines

mm/damon/core.c new file +10 -0

+                       ctx->primitive.check_accesses(ctx);
+
+               if (kdamond_aggregate_interval_passed(ctx)) {
+                       if (ctx->callback.after_aggregation &&
+                                       ctx->callback.after_aggregation(ctx))
+                               set_kdamond_stop(ctx);
+                       if (ctx->primitive.reset_aggregated)
+                               ctx->primitive.reset_aggregated(ctx);
+               }
+

The following 'if' can be done in ctx->primitive.update() callback.

Quoted 24 lines

mm/damon/core.c new file +23 -0

+               if (kdamond_need_update_regions(ctx)) {
+                       if (ctx->primitive.update_target_regions)
+                               ctx->primitive.update_target_regions(ctx);
+               }
+       }
+
+       if (ctx->callback.before_terminate &&
+                       ctx->callback.before_terminate(ctx))
+               set_kdamond_stop(ctx);
+       if (ctx->primitive.cleanup)
+               ctx->primitive.cleanup(ctx);
+
+       pr_debug("kdamond (%d) finishes\n", ctx->kdamond->pid);
+       mutex_lock(&ctx->kdamond_lock);
+       ctx->kdamond = NULL;
+       mutex_unlock(&ctx->kdamond_lock);
+
+       mutex_lock(&damon_lock);
+       nr_running_ctxs--;
+       mutex_unlock(&damon_lock);
+
+       do_exit(0);
+}

Quoted 3 lines

--
2.17.1

Overall the patch looks good to me. Two concerns I have are if we should damon_callback here or with the real user and the regions part of primitive abstraction. For the first one, I don't have any strong opinion but for the second one I do.

More specifically the question is if sampling and adaptive region adjustment are general enough to be part of core monitoring context? Can you give an example of a different primitive/use-case where these would be beneficial.

Quoted 4 lines

Overall the patch looks good to me. Two concerns I have are if we should damon_callback here or with the real user and the regions part of primitive abstraction. For the first one, I don't have any strong opinion but for the second one I do.

I'd like to keep 'damon_callback' part here, to let API users know how the monitoring result will be available to them.

For the 'regions' part, I will rename relevant things as below in the next version, to reduce any confusion.

init_target_regions() -> init()
update_target_regions() -> update()
regions_update_interval -> update_interval
last_regions_update -> last_update

Quoted 5 lines

More specifically the question is if sampling and adaptive region adjustment are general enough to be part of core monitoring context? Can you give an example of a different primitive/use-case where these would be beneficial.

I think all adress spaces having some spatial locality and monitoring requests that need to have upper-bound overhead and best-effort accuracy could get benefit from it. The primitives targetting 'virtual address spaces' and the 'physical address space' clearly showed the benefit.

On Wed, Dec 23, 2020 at 8:34 AM SeongJae Park <[email protected]> wrote:
[snip]

Quoted 22 lines

Quoted 4 lines

Overall the patch looks good to me. Two concerns I have are if we should damon_callback here or with the real user and the regions part of primitive abstraction. For the first one, I don't have any strong opinion but for the second one I do.

I'd like to keep 'damon_callback' part here, to let API users know how the monitoring result will be available to them.

For the 'regions' part, I will rename relevant things as below in the next version, to reduce any confusion.

init_target_regions() -> init()
update_target_regions() -> update()
regions_update_interval -> update_interval
last_regions_update -> last_update

Quoted 5 lines

More specifically the question is if sampling and adaptive region adjustment are general enough to be part of core monitoring context? Can you give an example of a different primitive/use-case where these would be beneficial.

Quoted 4 lines

I think all adress spaces having some spatial locality and monitoring requests that need to have upper-bound overhead and best-effort accuracy could get benefit from it. The primitives targetting 'virtual address spaces' and the 'physical address space' clearly showed the benefit.

I am still not much convinced on the 'physical address space' use-case or the way you are presenting it.

Anyways I think we start with what you have and if in future there is a use-case where regions adjustment does not make sense, we can change it then.

From: SeongJae Park <[email protected]>

To avoid the unbounded increase of the overhead, DAMON groups adjacent pages that assumed to have the same access frequencies into a region.

As long as the assumption (pages in a region have the same access frequencies) is kept, only one page in the region is required to be checked. Thus, for each ``sampling interval``,

1. the 'prepare_access_checks' primitive picks one page in each region,
2. waits for one ``sampling interval``,
3. checks whether the page is accessed meanwhile, and
4. increases the access frequency of the region if so.

Therefore, the monitoring overhead is controllable by adjusting the number of regions. DAMON allows both the underlying primitives and user callbacks adjust regions for the trade-off. In other words, this commit

makes DAMON to use not only time-based sampling but also space-based sampling.

This scheme, however, cannot preserve the quality of the output if the assumption is not guaranteed. Next commit will address this problem.

Another problem of this region abstraction is additional memory space overhead for the regions metadata. For example, suppose page granularity monitoring that doesn't want to know fine-grained access frequency but only if each page accessed or not.

Then, we can do that
by directly resetting and reading the PG_Idle flags and/or the PTE Accessed bits. The metadata for the region abstraction is only burden in the case. For the reason, this commit makes DAMON to support the user-defined arbitrary target, which could be stored in a void pointer of the monitoring context with specific target type.

Signed-off-by SeongJae Park <[email protected]>

Reviewed-by Leonard Foerster <[email protected]>

---
 include/linux/damon.h | 109 ++++++++++++++++++++++++++++++--
 mm/damon/core.c       | 142 +++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 243 insertions(+), 8 deletions(-)

include/linux/damon.h +46 -2

index 387fa4399fc8..7d4685adc8a9 100644
@@ -12,6 +12,48 @@
 #include <linux/time64.h>
 #include <linux/types.h>
 
+/**
+ * struct damon_addr_range - Represents an address region of [@start, @end).
+ * @start:     Start address of the region (inclusive).
+ * @end:       End address of the region (exclusive).
+ */
+struct damon_addr_range {
+       unsigned long start;
+       unsigned long end;
+};
+
+/**
+ * struct damon_region - Represents a monitoring target region.
+ * @ar:                        The address range of the region.
+ * @sampling_addr:     Address of the sample for the next access check.
+ * @nr_accesses:       Access frequency of this region.
+ * @list:              List head for siblings.
+ */
+struct damon_region {
+       struct damon_addr_range ar;
+       unsigned long sampling_addr;
+       unsigned int nr_accesses;
+       struct list_head list;
+};
+
+/**
+ * struct damon_target - Represents a monitoring target.
+ * @id:                        Unique identifier for this target.
+ * @regions_list:      Head of the monitoring target regions of this target.
+ * @list:              List head for siblings.
+ *
+ * Each monitoring context could have multiple targets.  For example, a context
+ * for virtual memory address spaces could have multiple target processes.  The
+ * @id of each target should be unique among the targets of the context.  For
+ * example, in the virtual address monitoring context, it could be a pidfd or
+ * an address of an mm_struct.
+ */
+struct damon_target {
+       unsigned long id;
+       struct list_head regions_list;
+       struct list_head list;
+};
+
 struct damon_ctx;
 
 /**

@@ -36,7 +78,8 @@ struct damon_ctx;
  *
  * @init_target_regions should construct proper monitoring target regions and
  * link those to the DAMON context struct.  The regions should be defined by
- * user and saved in @damon_ctx.target.
+ * user and saved in @damon_ctx.arbitrary_target if @damon_ctx.target_type is
+ * &DAMON_ARBITRARY_TARGET.  Otherwise, &struct damon_region should be used.
  * @update_target_regions should update the monitoring target regions for
  * current status.
  * @prepare_access_checks should manipulate the monitoring regions to be

@@ -46,7 +89,8 @@ struct damon_ctx;
  * @reset_aggregated should reset the access monitoring results that aggregated
  * by @check_accesses.
  * @target_valid should check whether the target is still valid for the
- * monitoring.
+ * monitoring.  It receives &damon_ctx.arbitrary_target or &struct damon_target
+ * pointer depends on &damon_ctx.target_type.
  * @cleanup is called from @kdamond just before its termination.  After this
  * call, only @kdamond_lock and @kdamond will be touched.
  */

@@ -91,6 +135,17 @@ struct damon_callback {
        int (*before_terminate)(struct damon_ctx *context);
 };

include/linux/damon.h +49 -3

+};
+
 /**
  * struct damon_ctx - Represents a context for each monitoring.  This is the
  * main interface that allows users to set the attributes and get the results

@@ -130,7 +185,15 @@ struct damon_callback {
  * @primitive: Set of monitoring primitives for given use cases.
  * @callback:  Set of callbacks for monitoring events notifications.
  *
- * @target:    Pointer to the user-defined monitoring target.
+ * @target_type:       Type of the monitoring target.
+ *
+ * @region_targets:    Head of monitoring targets (&damon_target) list.
+ *
+ * @arbitrary_target:  Pointer to arbitrary type target.
+ *
+ * @region_targets are valid only if @target_type is
+ * DAMON_REGION_SAMPLING_TARGET.  @arbitrary_target is valid only if
+ * @target_type is DAMON_ARBITRARY_TARGET.
  */
 struct damon_ctx {
        unsigned long sample_interval;

@@ -149,12 +212,48 @@ struct damon_ctx {
        struct damon_primitive primitive;
        struct damon_callback callback;
 
-       void *target;
+       enum damon_target_type target_type;
+       union {
+               /* DAMON_REGION_SAMPLING_TARGET */
+               struct list_head region_targets;
+
+               /* DAMON_ARBITRARY_TARGET */
+               void *arbitrary_target;
+       };
 };
 
+#define damon_next_region(r) \
+       (container_of(r->list.next, struct damon_region, list))
+
+#define damon_prev_region(r) \
+       (container_of(r->list.prev, struct damon_region, list))
+
+#define damon_for_each_region(r, t) \
+       list_for_each_entry(r, &t->regions_list, list)
+
+#define damon_for_each_region_safe(r, next, t) \
+       list_for_each_entry_safe(r, next, &t->regions_list, list)
+
+#define damon_for_each_target(t, ctx) \
+       list_for_each_entry(t, &(ctx)->region_targets, list)
+
+#define damon_for_each_target_safe(t, next, ctx)       \
+       list_for_each_entry_safe(t, next, &(ctx)->region_targets, list)
+
 #ifdef CONFIG_DAMON
 
-struct damon_ctx *damon_new_ctx(void);
+struct damon_region *damon_new_region(unsigned long start, unsigned long end);
+inline void damon_insert_region(struct damon_region *r,
+               struct damon_region *prev, struct damon_region *next);
+void damon_add_region(struct damon_region *r, struct damon_target *t);
+void damon_destroy_region(struct damon_region *r);
+
+struct damon_target *damon_new_target(unsigned long id);
+void damon_add_target(struct damon_ctx *ctx, struct damon_target *t);
+void damon_free_target(struct damon_target *t);
+void damon_destroy_target(struct damon_target *t);
+
+struct damon_ctx *damon_new_ctx(enum damon_target_type type);
 void damon_destroy_ctx(struct damon_ctx *ctx);
 int damon_set_attrs(struct damon_ctx *ctx, unsigned long sample_int,
                unsigned long aggr_int, unsigned long regions_update_int);

mm/damon/core.c +25 -1

index 8963804efdf9..167487e75737 100644
@@ -15,7 +15,102 @@
 static DEFINE_MUTEX(damon_lock);
 static int nr_running_ctxs;
 
-struct damon_ctx *damon_new_ctx(void)
+/*
+ * Construct a damon_region struct
+ *
+ * Returns the pointer to the new struct if success, or NULL otherwise
+ */
+struct damon_region *damon_new_region(unsigned long start, unsigned long end)
+{
+       struct damon_region *region;
+
+       region = kmalloc(sizeof(*region), GFP_KERNEL);
+       if (!region)
+               return NULL;
+
+       region->ar.start = start;
+       region->ar.end = end;
+       region->nr_accesses = 0;
+       INIT_LIST_HEAD(&region->list);
+
+       return region;
+}
+
+/*
+ * Add a region between two other regions
+ */
+inline void damon_insert_region(struct damon_region *r,

mm/damon/core.c +104 -3

+static void damon_del_region(struct damon_region *r)
+{
+       list_del(&r->list);
+}
+
+static void damon_free_region(struct damon_region *r)
+{
+       kfree(r);
+}
+
+void damon_destroy_region(struct damon_region *r)
+{
+       damon_del_region(r);
+       damon_free_region(r);
+}
+
+/*
+ * Construct a damon_target struct
+ *
+ * Returns the pointer to the new struct if success, or NULL otherwise
+ */
+struct damon_target *damon_new_target(unsigned long id)
+{
+       struct damon_target *t;
+
+       t = kmalloc(sizeof(*t), GFP_KERNEL);
+       if (!t)
+               return NULL;
+
+       t->id = id;
+       INIT_LIST_HEAD(&t->regions_list);
+
+       return t;
+}
+
+void damon_add_target(struct damon_ctx *ctx, struct damon_target *t)
+{
+       list_add_tail(&t->list, &ctx->region_targets);
+}
+
+static void damon_del_target(struct damon_target *t)
+{
+       list_del(&t->list);
+}
+
+void damon_free_target(struct damon_target *t)
+{
+       struct damon_region *r, *next;
+
+       damon_for_each_region_safe(r, next, t)
+               damon_free_region(r);
+       kfree(t);
+}
+
+void damon_destroy_target(struct damon_target *t)
+{
+       damon_del_target(t);
+       damon_free_target(t);
+}
+
+struct damon_ctx *damon_new_ctx(enum damon_target_type type)
 {
        struct damon_ctx *ctx;
 

@@ -32,13 +127,20 @@ struct damon_ctx *damon_new_ctx(void)
 
        mutex_init(&ctx->kdamond_lock);
 
-       ctx->target = NULL;
+       ctx->target_type = type;
+       if (type != DAMON_ARBITRARY_TARGET)
+               INIT_LIST_HEAD(&ctx->region_targets);
 
        return ctx;
 }
 
 void damon_destroy_ctx(struct damon_ctx *ctx)
 {
+       struct damon_target *t, *next_t;
+
+       damon_for_each_target_safe(t, next_t, ctx)
+               damon_destroy_target(t);
+
        kfree(ctx);
 }
 

@@ -215,6 +317,21 @@ static bool kdamond_aggregate_interval_passed(struct damon_ctx *ctx)
                        ctx->aggr_interval);
 }
 
+/*
+ * Reset the aggregated monitoring results ('nr_accesses' of each region).
+ */
+static void kdamond_reset_aggregated(struct damon_ctx *c)
+{
+       struct damon_target *t;
+
+       damon_for_each_target(t, c) {
+               struct damon_region *r;
+
+               damon_for_each_region(r, t)
+                       r->nr_accesses = 0;
+       }
+}
+
 /*
  * Check whether it is time to check and apply the target monitoring regions
  *

@@ -236,6 +353,7 @@ static bool kdamond_need_update_regions(struct damon_ctx *ctx)
  */
 static bool kdamond_need_stop(struct damon_ctx *ctx)
 {
+       struct damon_target *t;
        bool stop;
 
        mutex_lock(&ctx->kdamond_lock);

@@ -247,7 +365,15 @@ static bool kdamond_need_stop(struct damon_ctx *ctx)
        if (!ctx->primitive.target_valid)
                return false;
 
-       return !ctx->primitive.target_valid(ctx->target);
+       if (ctx->target_type == DAMON_ARBITRARY_TARGET)
+               return !ctx->primitive.target_valid(ctx->arbitrary_target);
+
+       damon_for_each_target(t, ctx) {
+               if (ctx->primitive.target_valid(t))
+                       return false;
+       }
+
+       return true;
 }
 
 static void set_kdamond_stop(struct damon_ctx *ctx)

@@ -263,6 +389,8 @@ static void set_kdamond_stop(struct damon_ctx *ctx)
 static int kdamond_fn(void *data)
 {
        struct damon_ctx *ctx = (struct damon_ctx *)data;
+       struct damon_target *t;
+       struct damon_region *r, *next;
 
        pr_info("kdamond (%d) starts\n", ctx->kdamond->pid);
 

@@ -287,6 +415,8 @@ static int kdamond_fn(void *data)
                        if (ctx->callback.after_aggregation &&
                                        ctx->callback.after_aggregation(ctx))
                                set_kdamond_stop(ctx);
+                       if (ctx->target_type != DAMON_ARBITRARY_TARGET)
+                               kdamond_reset_aggregated(ctx);
                        if (ctx->primitive.reset_aggregated)
                                ctx->primitive.reset_aggregated(ctx);
                }

@@ -296,6 +426,12 @@ static int kdamond_fn(void *data)
                                ctx->primitive.update_target_regions(ctx);
                }
        }
+       if (ctx->target_type != DAMON_ARBITRARY_TARGET) {
+               damon_for_each_target(t, ctx) {
+                       damon_for_each_region_safe(r, next, t)
+                               damon_destroy_region(r);
+               }
+       }
 
        if (ctx->callback.before_terminate &&
                        ctx->callback.before_terminate(ctx))
--

2.17.1

Quoted 5 lines · SeongJae Park

From: SeongJae Park <[email protected]>

To avoid the unbounded increase of the overhead, DAMON groups adjacent pages that assumed to have the same access frequencies into a region.

'that are assumed'

Quoted 5 lines

As long as the assumption (pages in a region have the same access frequencies) is kept, only one page in the region is required to be checked. Thus, for each ``sampling interval``,

Quoted 4 lines

1. the 'prepare_access_checks' primitive picks one page in each region,
2. waits for one ``sampling interval``,
3. checks whether the page is accessed meanwhile, and
4. increases the access frequency of the region if so.

I think you meant increasing the access 'count' or something. Increasing the access frequency somewhat conveys that the sampling interval is being decreased.

Quoted 5 lines

Therefore, the monitoring overhead is controllable by adjusting the number of regions. DAMON allows both the underlying primitives and user callbacks adjust regions for the trade-off. In other words, this commit

'callbacks to adjust'

Quoted 8 lines

makes DAMON to use not only time-based sampling but also space-based sampling.

This scheme, however, cannot preserve the quality of the output if the assumption is not guaranteed. Next commit will address this problem.

Quoted 4 lines

Another problem of this region abstraction is additional memory space overhead for the regions metadata. For example, suppose page granularity monitoring that doesn't want to know fine-grained access frequency but only if each page accessed or not.

You mean when the sampling interval is equal to the aggregation interval, right?

Quoted 7 lines

Then, we can do that
by directly resetting and reading the PG_Idle flags and/or the PTE Accessed bits. The metadata for the region abstraction is only burden in the case. For the reason, this commit makes DAMON to support the user-defined arbitrary target, which could be stored in a void pointer of the monitoring context with specific target type.

Sorry I didn't follow. How does sampling interval equal to aggregation interval require user-defined arbitrary targets?

Quoted 86 lines

Signed-off-by SeongJae Park <[email protected]>

Reviewed-by Leonard Foerster <[email protected]>

---
 include/linux/damon.h | 109 ++++++++++++++++++++++++++++++--
 mm/damon/core.c       | 142 +++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 243 insertions(+), 8 deletions(-)

include/linux/damon.h +46 -2

index 387fa4399fc8..7d4685adc8a9 100644
@@ -12,6 +12,48 @@
 #include <linux/time64.h>
 #include <linux/types.h>
 
+/**
+ * struct damon_addr_range - Represents an address region of [@start, @end).
+ * @start:     Start address of the region (inclusive).
+ * @end:       End address of the region (exclusive).
+ */
+struct damon_addr_range {
+       unsigned long start;
+       unsigned long end;
+};
+
+/**
+ * struct damon_region - Represents a monitoring target region.
+ * @ar:                        The address range of the region.
+ * @sampling_addr:     Address of the sample for the next access check.
+ * @nr_accesses:       Access frequency of this region.
+ * @list:              List head for siblings.
+ */
+struct damon_region {
+       struct damon_addr_range ar;
+       unsigned long sampling_addr;
+       unsigned int nr_accesses;
+       struct list_head list;
+};
+
+/**
+ * struct damon_target - Represents a monitoring target.
+ * @id:                        Unique identifier for this target.
+ * @regions_list:      Head of the monitoring target regions of this target.
+ * @list:              List head for siblings.
+ *
+ * Each monitoring context could have multiple targets.  For example, a context
+ * for virtual memory address spaces could have multiple target processes.  The
+ * @id of each target should be unique among the targets of the context.  For
+ * example, in the virtual address monitoring context, it could be a pidfd or
+ * an address of an mm_struct.
+ */
+struct damon_target {
+       unsigned long id;
+       struct list_head regions_list;
+       struct list_head list;
+};
+
 struct damon_ctx;
 
 /**

@@ -36,7 +78,8 @@ struct damon_ctx;
  *
  * @init_target_regions should construct proper monitoring target regions and
  * link those to the DAMON context struct.  The regions should be defined by
- * user and saved in @damon_ctx.target.
+ * user and saved in @damon_ctx.arbitrary_target if @damon_ctx.target_type is
+ * &DAMON_ARBITRARY_TARGET.  Otherwise, &struct damon_region should be used.
  * @update_target_regions should update the monitoring target regions for
  * current status.
  * @prepare_access_checks should manipulate the monitoring regions to be

@@ -46,7 +89,8 @@ struct damon_ctx;
  * @reset_aggregated should reset the access monitoring results that aggregated
  * by @check_accesses.
  * @target_valid should check whether the target is still valid for the
- * monitoring.
+ * monitoring.  It receives &damon_ctx.arbitrary_target or &struct damon_target
+ * pointer depends on &damon_ctx.target_type.
  * @cleanup is called from @kdamond just before its termination.  After this
  * call, only @kdamond_lock and @kdamond will be touched.
  */

@@ -91,6 +135,17 @@ struct damon_callback {
        int (*before_terminate)(struct damon_ctx *context);
 };
 

include/linux/damon.h struct damon_callback { · line 146

Quoted 9 lines

include/linux/damon.h +9 -0

+/**
+ * enum damon_target_type - Represents the type of the monitoring target.
+ *
+ * @DAMON_REGION_SAMPLING_TARGET:      Region based sampling target.
+ * @DAMON_ARBITRARY_TARGET:            User-defined arbitrary type target.
+ */
+enum damon_target_type {
+       DAMON_REGION_SAMPLING_TARGET,
+       DAMON_ARBITRARY_TARGET,

I would suggest removing the arbitrary target in this pathset. This patchset is only adding the region sampling target, so no need to add the arbitrary target here.

Quoted 9 lines

include/linux/damon.h +9 -0

+
+/*
+ * Add a region between two other regions
+ */
+inline void damon_insert_region(struct damon_region *r,
+               struct damon_region *prev, struct damon_region *next)
+{
+       __list_add(&r->list, &prev->list, &next->list);
+}

include/linux/damon.h

Quoted 6 lines

include/linux/damon.h +6 -0

+
+void damon_add_region(struct damon_region *r, struct damon_target *t)
+{
+       list_add_tail(&r->list, &t->regions_list);
+}
+

I don't see the benefit of these one line functions at least the following two.

From: SeongJae Park <[email protected]>

Even somehow the initial monitoring target regions are well constructed to fulfill the assumption (pages in same region have similar access frequencies), the data access pattern can be dynamically changed. This will result in low monitoring quality. To keep the assumption as much as possible, DAMON adaptively merges and splits each region based on their access frequency.

For each ``aggregation interval``, it compares the access frequencies of adjacent regions and merges those if the frequency difference is small. Then, after it reports and clears the aggregated access frequency of each region, it splits each region into two or three regions if the total number of regions will not exceed the user-specified maximum number of regions after the split.

In this way, DAMON provides its best-effort quality and minimal overhead while keeping the upper-bound overhead that users set.

Signed-off-by SeongJae Park <[email protected]>

Reviewed-by Leonard Foerster <[email protected]>

---
 include/linux/damon.h |  41 +++++---
 mm/damon/core.c       | 220 ++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 240 insertions(+), 21 deletions(-)

mm/damon/core.c +0 -0

index 167487e75737..0f9beb60d9dd 100644

From: SeongJae Park <[email protected]>

Even somehow the initial monitoring target regions are well constructed to fulfill the assumption (pages in same region have similar access frequencies), the data access pattern can be dynamically changed. This will result in low monitoring quality. To keep the assumption as much as possible, DAMON adaptively merges and splits each region based on their access frequency.

For each ``aggregation interval``, it compares the access frequencies of adjacent regions and merges those if the frequency difference is small. Then, after it reports and clears the aggregated access frequency of each region, it splits each region into two or three regions if the total number of regions will not exceed the user-specified maximum number of regions after the split.

In this way, DAMON provides its best-effort quality and minimal overhead while keeping the upper-bound overhead that users set.

Signed-off-by SeongJae Park <[email protected]>

Reviewed-by Leonard Foerster <[email protected]>

---
 include/linux/damon.h |  41 +++++---
 mm/damon/core.c       | 220 ++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 240 insertions(+), 21 deletions(-)

include/linux/damon.h +3 -0

index 7d4685adc8a9..f446f8433599 100644
@@ -12,6 +12,9 @@
 #include <linux/time64.h>
 #include <linux/types.h>
 
+/* Minimal region size.  Every damon_region is aligned by this. */
+#define DAMON_MIN_REGION       PAGE_SIZE
+
 /**
  * struct damon_addr_range - Represents an address region of [@start, @end).
  * @start:     Start address of the region (inclusive).

include/linux/damon.h +21 -15

  * @reset_aggregated should reset the access monitoring results that aggregated
  * by @check_accesses.
  * @target_valid should check whether the target is still valid for the

@@ -98,7 +103,7 @@ struct damon_primitive {
        void (*init_target_regions)(struct damon_ctx *context);
        void (*update_target_regions)(struct damon_ctx *context);
        void (*prepare_access_checks)(struct damon_ctx *context);
-       void (*check_accesses)(struct damon_ctx *context);
+       unsigned int (*check_accesses)(struct damon_ctx *context);
        void (*reset_aggregated)(struct damon_ctx *context);
        bool (*target_valid)(void *target);
        void (*cleanup)(struct damon_ctx *context);

@@ -138,11 +143,11 @@ struct damon_callback {
 /**
  * enum damon_target_type - Represents the type of the monitoring target.
  *
- * @DAMON_REGION_SAMPLING_TARGET:      Region based sampling target.
- * @DAMON_ARBITRARY_TARGET:            User-defined arbitrary type target.
+ * @DAMON_ADAPTIVE_TARGET:     Adaptive regions adjustment applied target.
+ * @DAMON_ARBITRARY_TARGET:    User-defined arbitrary type target.
  */
 enum damon_target_type {
-       DAMON_REGION_SAMPLING_TARGET,
+       DAMON_ADAPTIVE_TARGET,
        DAMON_ARBITRARY_TARGET,
 };
 

@@ -187,13 +192,15 @@ enum damon_target_type {
  *
  * @target_type:       Type of the monitoring target.
  *
- * @region_targets:    Head of monitoring targets (&damon_target) list.
+ * @min_nr_regions:    The minimum number of adaptive monitoring regions.
+ * @max_nr_regions:    The maximum number of adaptive monitoring regions.
+ * @adaptive_targets:  Head of monitoring targets (&damon_target) list.
  *
  * @arbitrary_target:  Pointer to arbitrary type target.
  *
- * @region_targets are valid only if @target_type is
- * DAMON_REGION_SAMPLING_TARGET.  @arbitrary_target is valid only if
- * @target_type is DAMON_ARBITRARY_TARGET.
+ * @min_nr_regions, @max_nr_regions and @adaptive_targets are valid only if
+ * @target_type is &DAMON_ADAPTIVE_TARGET.  @arbitrary_target is valid only if
+ * @target_type is &DAMON_ARBITRARY_TARGET.
  */
 struct damon_ctx {
        unsigned long sample_interval;

@@ -214,11 +221,13 @@ struct damon_ctx {
 
        enum damon_target_type target_type;
        union {
-               /* DAMON_REGION_SAMPLING_TARGET */
-               struct list_head region_targets;
+               struct {                /* DAMON_ADAPTIVE_TARGET */
+                       unsigned long min_nr_regions;
+                       unsigned long max_nr_regions;
+                       struct list_head adaptive_targets;
+               };
 
-               /* DAMON_ARBITRARY_TARGET */
-               void *arbitrary_target;
+               void *arbitrary_target; /* DAMON_ARBITRARY_TARGET */
        };
 };
 

@@ -235,10 +244,10 @@ struct damon_ctx {
        list_for_each_entry_safe(r, next, &t->regions_list, list)
 
 #define damon_for_each_target(t, ctx) \
-       list_for_each_entry(t, &(ctx)->region_targets, list)
+       list_for_each_entry(t, &(ctx)->adaptive_targets, list)
 
 #define damon_for_each_target_safe(t, next, ctx)       \
-       list_for_each_entry_safe(t, next, &(ctx)->region_targets, list)
+       list_for_each_entry_safe(t, next, &(ctx)->adaptive_targets, list)
 
 #ifdef CONFIG_DAMON
 

@@ -252,11 +261,13 @@ struct damon_target *damon_new_target(unsigned long id);
 void damon_add_target(struct damon_ctx *ctx, struct damon_target *t);
 void damon_free_target(struct damon_target *t);
 void damon_destroy_target(struct damon_target *t);
+unsigned int damon_nr_regions(struct damon_target *t);
 
 struct damon_ctx *damon_new_ctx(enum damon_target_type type);
 void damon_destroy_ctx(struct damon_ctx *ctx);
 int damon_set_attrs(struct damon_ctx *ctx, unsigned long sample_int,
-               unsigned long aggr_int, unsigned long regions_update_int);
+               unsigned long aggr_int, unsigned long regions_update_int,
+               unsigned long min_nr_reg, unsigned long max_nr_reg);
 
 int damon_start(struct damon_ctx **ctxs, int nr_ctxs);
 int damon_stop(struct damon_ctx **ctxs, int nr_ctxs);

mm/damon/core.c +5 -1

index 167487e75737..0f9beb60d9dd 100644
@@ -10,8 +10,12 @@
 #include <linux/damon.h>
 #include <linux/delay.h>
 #include <linux/kthread.h>
+#include <linux/random.h>
 #include <linux/slab.h>
 
+/* Get a random number in [l, r) */
+#define damon_rand(l, r) (l + prandom_u32_max(r - l))
+
 static DEFINE_MUTEX(damon_lock);
 static int nr_running_ctxs;
 

@@ -87,7 +91,7 @@ struct damon_target *damon_new_target(unsigned long id)
 
 void damon_add_target(struct damon_ctx *ctx, struct damon_target *t)
 {
-       list_add_tail(&t->list, &ctx->region_targets);
+       list_add_tail(&t->list, &ctx->adaptive_targets);
 }
 
 static void damon_del_target(struct damon_target *t)

mm/damon/core.c +4 -0

+
+       return nr_regions;
+}
+
 struct damon_ctx *damon_new_ctx(enum damon_target_type type)
 {
        struct damon_ctx *ctx;

mm/damon/core.c +160 -1

+
+               INIT_LIST_HEAD(&ctx->adaptive_targets);
+       }
 
        return ctx;
 }

@@ -150,6 +169,8 @@ void damon_destroy_ctx(struct damon_ctx *ctx)
  * @sample_int:                time interval between samplings
  * @aggr_int:          time interval between aggregations
  * @regions_update_int:        time interval between target regions update
+ * @min_nr_reg:                minimal number of regions
+ * @max_nr_reg:                maximum number of regions
  *
  * This function should not be called while the kdamond is running.
  * Every time interval is in micro-seconds.

@@ -157,15 +178,51 @@ void damon_destroy_ctx(struct damon_ctx *ctx)
  * Return: 0 on success, negative error code otherwise.
  */
 int damon_set_attrs(struct damon_ctx *ctx, unsigned long sample_int,
-                   unsigned long aggr_int, unsigned long regions_update_int)
+                   unsigned long aggr_int, unsigned long regions_update_int,
+                   unsigned long min_nr_reg, unsigned long max_nr_reg)
 {
+       if (min_nr_reg < 3) {
+               pr_err("min_nr_regions (%lu) must be at least 3\n",
+                               min_nr_reg);
+               return -EINVAL;
+       }
+       if (min_nr_reg > max_nr_reg) {
+               pr_err("invalid nr_regions.  min (%lu) > max (%lu)\n",
+                               min_nr_reg, max_nr_reg);
+               return -EINVAL;
+       }
+
        ctx->sample_interval = sample_int;
        ctx->aggr_interval = aggr_int;
        ctx->regions_update_interval = regions_update_int;
+       if (ctx->target_type != DAMON_ARBITRARY_TARGET) {
+               ctx->min_nr_regions = min_nr_reg;
+               ctx->max_nr_regions = max_nr_reg;
+       }
 
        return 0;
 }
 
+/* Returns the size upper limit for each monitoring region */
+static unsigned long damon_region_sz_limit(struct damon_ctx *ctx)
+{
+       struct damon_target *t;
+       struct damon_region *r;
+       unsigned long sz = 0;
+
+       damon_for_each_target(t, ctx) {
+               damon_for_each_region(r, t)
+                       sz += r->ar.end - r->ar.start;
+       }
+
+       if (ctx->min_nr_regions)
+               sz /= ctx->min_nr_regions;
+       if (sz < DAMON_MIN_REGION)
+               sz = DAMON_MIN_REGION;
+
+       return sz;
+}
+
 static bool damon_kdamond_running(struct damon_ctx *ctx)
 {
        bool running;

@@ -332,6 +389,146 @@ static void kdamond_reset_aggregated(struct damon_ctx *c)
        }
 }
 
+#define sz_damon_region(r) (r->ar.end - r->ar.start)
+
+/*
+ * Merge two adjacent regions into one region
+ */
+static void damon_merge_two_regions(struct damon_region *l,
+                               struct damon_region *r)
+{
+       unsigned long sz_l = sz_damon_region(l), sz_r = sz_damon_region(r);
+
+       l->nr_accesses = (l->nr_accesses * sz_l + r->nr_accesses * sz_r) /
+                       (sz_l + sz_r);
+       l->ar.end = r->ar.end;
+       damon_destroy_region(r);
+}
+
+#define diff_of(a, b) (a > b ? a - b : b - a)
+
+/*
+ * Merge adjacent regions having similar access frequencies
+ *
+ * t           target affected by this merge operation
+ * thres       '->nr_accesses' diff threshold for the merge
+ * sz_limit    size upper limit of each region
+ */
+static void damon_merge_regions_of(struct damon_target *t, unsigned int thres,
+                                  unsigned long sz_limit)
+{
+       struct damon_region *r, *prev = NULL, *next;
+
+       damon_for_each_region_safe(r, next, t) {
+               if (prev && prev->ar.end == r->ar.start &&
+                   diff_of(prev->nr_accesses, r->nr_accesses) <= thres &&
+                   sz_damon_region(prev) + sz_damon_region(r) <= sz_limit)
+                       damon_merge_two_regions(prev, r);
+               else
+                       prev = r;
+       }
+}
+
+/*
+ * Merge adjacent regions having similar access frequencies
+ *
+ * threshold   '->nr_accesses' diff threshold for the merge
+ * sz_limit    size upper limit of each region
+ *
+ * This function merges monitoring target regions which are adjacent and their
+ * access frequencies are similar.  This is for minimizing the monitoring
+ * overhead under the dynamically changeable access pattern.  If a merge was
+ * unnecessarily made, later 'kdamond_split_regions()' will revert it.
+ */
+static void kdamond_merge_regions(struct damon_ctx *c, unsigned int threshold,
+                                 unsigned long sz_limit)
+{
+       struct damon_target *t;
+
+       damon_for_each_target(t, c)
+               damon_merge_regions_of(t, threshold, sz_limit);
+}
+
+/*
+ * Split a region in two
+ *
+ * r           the region to be split
+ * sz_r                size of the first sub-region that will be made
+ */
+static void damon_split_region_at(struct damon_ctx *ctx,
+                                 struct damon_region *r, unsigned long sz_r)
+{
+       struct damon_region *new;
+
+       new = damon_new_region(r->ar.start + sz_r, r->ar.end);
+       r->ar.end = new->ar.start;
+
+       damon_insert_region(new, r, damon_next_region(r));
+}
+
+/* Split every region in the given target into 'nr_subs' regions */
+static void damon_split_regions_of(struct damon_ctx *ctx,
+                                    struct damon_target *t, int nr_subs)
+{
+       struct damon_region *r, *next;
+       unsigned long sz_region, sz_sub = 0;
+       int i;
+
+       damon_for_each_region_safe(r, next, t) {
+               sz_region = r->ar.end - r->ar.start;
+
+               for (i = 0; i < nr_subs - 1 &&
+                               sz_region > 2 * DAMON_MIN_REGION; i++) {
+                       /*
+                        * Randomly select size of left sub-region to be at
+                        * least 10 percent and at most 90% of original region
+                        */
+                       sz_sub = ALIGN_DOWN(damon_rand(1, 10) *
+                                       sz_region / 10, DAMON_MIN_REGION);
+                       /* Do not allow blank region */
+                       if (sz_sub == 0 || sz_sub >= sz_region)
+                               continue;
+
+                       damon_split_region_at(ctx, r, sz_sub);
+                       sz_region = sz_sub;
+               }
+       }
+}
+
+/*
+ * Split every target region into randomly-sized small regions
+ *
+ * This function splits every target region into random-sized small regions if
+ * current total number of the regions is equal or smaller than half of the
+ * user-specified maximum number of regions.  This is for maximizing the
+ * monitoring accuracy under the dynamically changeable access patterns.  If a
+ * split was unnecessarily made, later 'kdamond_merge_regions()' will revert
+ * it.
+ */
+static void kdamond_split_regions(struct damon_ctx *ctx)
+{

mm/damon/core.c +16 -0

+
+       /* Maybe the middle of the region has different access frequency */
+       if (last_nr_regions == nr_regions &&
+                       nr_regions < ctx->max_nr_regions / 3)
+               nr_subregions = 3;
+
+       damon_for_each_target(t, ctx)
+               damon_split_regions_of(ctx, t, nr_subregions);
+
+       last_nr_regions = nr_regions;
+}
+
 /*
  * Check whether it is time to check and apply the target monitoring regions
  *

@@ -391,6 +588,8 @@ static int kdamond_fn(void *data)
        struct damon_ctx *ctx = (struct damon_ctx *)data;
        struct damon_target *t;
        struct damon_region *r, *next;
+       unsigned int max_nr_accesses = 0;
+       unsigned long sz_limit = 0;
 
        pr_info("kdamond (%d) starts\n", ctx->kdamond->pid);
 

@@ -399,6 +598,8 @@ static int kdamond_fn(void *data)
        if (ctx->callback.before_start && ctx->callback.before_start(ctx))
                set_kdamond_stop(ctx);
 
+       sz_limit = damon_region_sz_limit(ctx);
+
        while (!kdamond_need_stop(ctx)) {
                if (ctx->primitive.prepare_access_checks)
                        ctx->primitive.prepare_access_checks(ctx);

mm/damon/core.c +5 -2

+                                               sz_limit);
                        if (ctx->callback.after_aggregation &&
                                        ctx->callback.after_aggregation(ctx))
                                set_kdamond_stop(ctx);
-                       if (ctx->target_type != DAMON_ARBITRARY_TARGET)
+                       if (ctx->target_type != DAMON_ARBITRARY_TARGET) {
                                kdamond_reset_aggregated(ctx);
+                               kdamond_split_regions(ctx);
+                       }
                        if (ctx->primitive.reset_aggregated)
                                ctx->primitive.reset_aggregated(ctx);
                }

@@ -424,6 +631,7 @@ static int kdamond_fn(void *data)
                if (kdamond_need_update_regions(ctx)) {
                        if (ctx->primitive.update_target_regions)
                                ctx->primitive.update_target_regions(ctx);
+                       sz_limit = damon_region_sz_limit(ctx);
                }
        }
        if (ctx->target_type != DAMON_ARBITRARY_TARGET) {
--

2.17.1

Quoted 10 lines · SeongJae Park

From: SeongJae Park <[email protected]>

Even somehow the initial monitoring target regions are well constructed to fulfill the assumption (pages in same region have similar access frequencies), the data access pattern can be dynamically changed. This will result in low monitoring quality. To keep the assumption as much as possible, DAMON adaptively merges and splits each region based on their access frequency.

Quoted 6 lines

For each ``aggregation interval``, it compares the access frequencies of adjacent regions and merges those if the frequency difference is small. Then, after it reports and clears the aggregated access frequency of each region, it splits each region into two or three regions if the total number of regions will not exceed the user-specified maximum number of regions after the split.

Should there be any concerns regarding the number of regions oscillating even when the access pattern of the application is not changing? Does the system converge to equilibrium state or does it not matter?

Quoted 20 lines

In this way, DAMON provides its best-effort quality and minimal overhead while keeping the upper-bound overhead that users set.

Signed-off-by SeongJae Park <[email protected]>

Reviewed-by Leonard Foerster <[email protected]>

---
 include/linux/damon.h |  41 +++++---
 mm/damon/core.c       | 220 ++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 240 insertions(+), 21 deletions(-)

include/linux/damon.h +0 -0

index 7d4685adc8a9..f446f8433599 100644
@@ -12,6 +12,9 @@
 #include <linux/time64.h>
 #include <linux/types.h>
 

include/linux/damon.h struct damon_ctx; · line 93

Quoted 12 lines

include/linux/damon.h +5 -0

+/* Minimal region size.  Every damon_region is aligned by this. */
+#define DAMON_MIN_REGION       PAGE_SIZE
+
 /**
  * struct damon_addr_range - Represents an address region of [@start, @end).
  * @start:     Start address of the region (inclusive).

@@ -86,6 +89,8 @@ struct damon_ctx;
  * prepared for the next access check.
  * @check_accesses should check the accesses to each region that made after the
  * last preparation and update the number of observed accesses of each region.
+ * It should also return max number of observed accesses that made as a result
+ * of its update.

Why?

Quoted 4 lines

include/linux/damon.h +0 -0

  * @reset_aggregated should reset the access monitoring results that aggregated
  * by @check_accesses.
  * @target_valid should check whether the target is still valid for the

include/linux/damon.h

Quoted 8 lines

include/linux/damon.h +7 -0

+unsigned int damon_nr_regions(struct damon_target *t)
+{
+       struct damon_region *r;
+       unsigned int nr_regions = 0;
+
+       damon_for_each_region(r, t)
+               nr_regions++;

Why not just add the region_count filed in damon_target?

Quoted 11 lines

include/linux/damon.h +4 -0

+
+       return nr_regions;
+}
+
 struct damon_ctx *damon_new_ctx(enum damon_target_type type)
 {
        struct damon_ctx *ctx;

@@ -128,8 +143,12 @@ struct damon_ctx *damon_new_ctx(enum damon_target_type type)
        mutex_init(&ctx->kdamond_lock);
 

include/linux/damon.h struct damon_ctx *damon_new_ctx(enum damon_target_type type) · line 148

Quoted 6 lines

include/linux/damon.h +3 -2

        ctx->target_type = type;
-       if (type != DAMON_ARBITRARY_TARGET)
-               INIT_LIST_HEAD(&ctx->region_targets);
+       if (type != DAMON_ARBITRARY_TARGET) {
+               ctx->min_nr_regions = 10;
+               ctx->max_nr_regions = 1000;

IMO these settings/heuristics should be part of the virtual address space monitor primitives and not be in the core monitor.

Quoted 7 lines

include/linux/damon.h +3 -0

+
+               INIT_LIST_HEAD(&ctx->adaptive_targets);
+       }
 
        return ctx;
 }

Quoted 17 lines

include/linux/damon.h +17 -0

+
+/*
+ * Split every target region into randomly-sized small regions
+ *
+ * This function splits every target region into random-sized small regions if
+ * current total number of the regions is equal or smaller than half of the
+ * user-specified maximum number of regions.  This is for maximizing the
+ * monitoring accuracy under the dynamically changeable access patterns.  If a
+ * split was unnecessarily made, later 'kdamond_merge_regions()' will revert
+ * it.
+ */
+static void kdamond_split_regions(struct damon_ctx *ctx)
+{
+       struct damon_target *t;
+       unsigned int nr_regions = 0;
+       static unsigned int last_nr_regions;
+       int nr_subregions = 2;

include/linux/damon.h

Quoted 6 lines

include/linux/damon.h +6 -0

+
+       damon_for_each_target(t, ctx)
+               nr_regions += damon_nr_regions(t);
+
+       if (nr_regions > ctx->max_nr_regions / 2)
+               return;

Shouldn't the limits on region be per-target instead of for the whole context?

Quoted 41 lines

include/linux/damon.h +17 -1

+
+       /* Maybe the middle of the region has different access frequency */
+       if (last_nr_regions == nr_regions &&
+                       nr_regions < ctx->max_nr_regions / 3)
+               nr_subregions = 3;
+
+       damon_for_each_target(t, ctx)
+               damon_split_regions_of(ctx, t, nr_subregions);
+
+       last_nr_regions = nr_regions;
+}
+
 /*
  * Check whether it is time to check and apply the target monitoring regions
  *

@@ -391,6 +588,8 @@ static int kdamond_fn(void *data)
        struct damon_ctx *ctx = (struct damon_ctx *)data;
        struct damon_target *t;
        struct damon_region *r, *next;
+       unsigned int max_nr_accesses = 0;
+       unsigned long sz_limit = 0;
 
        pr_info("kdamond (%d) starts\n", ctx->kdamond->pid);
 

@@ -399,6 +598,8 @@ static int kdamond_fn(void *data)
        if (ctx->callback.before_start && ctx->callback.before_start(ctx))
                set_kdamond_stop(ctx);
 
+       sz_limit = damon_region_sz_limit(ctx);
+
        while (!kdamond_need_stop(ctx)) {
                if (ctx->primitive.prepare_access_checks)
                        ctx->primitive.prepare_access_checks(ctx);

@@ -409,14 +610,20 @@ static int kdamond_fn(void *data)
                usleep_range(ctx->sample_interval, ctx->sample_interval + 1);
 
                if (ctx->primitive.check_accesses)
-                       ctx->primitive.check_accesses(ctx);
+                       max_nr_accesses = ctx->primitive.check_accesses(ctx);
 

include/linux/damon.h static int kdamond_fn(void *data) · line 618

Quoted 4 lines

include/linux/damon.h +3 -0

                if (kdamond_aggregate_interval_passed(ctx)) {
+                       if (ctx->target_type != DAMON_ARBITRARY_TARGET)
+                               kdamond_merge_regions(ctx,
+                                               max_nr_accesses / 10,

What's the reason behind this 10?

From: SeongJae Park <[email protected]>

PG_idle and PG_young allow the two PTE Accessed bit users, Idle Page Tracking and the reclaim logic concurrently work while don't interfere each other. That is, when they need to clear the Accessed bit, they set PG_young to represent the previous state of the bit, respectively. And when they need to read the bit, if the bit is cleared, they further read the PG_young to know whether the other has cleared the bit meanwhile or not.

We could add another page flag and extend the mechanism to use the flag if we need to add another concurrent PTE Accessed bit user subsystem. However, the space is limited. Meanwhile, if the new subsystem is mutually exclusive with IDLE_PAGE_TRACKING or interfering with it is not a real problem, it would be ok to simply reuse the PG_idle flag. However, it's impossible because the flags are dependent on IDLE_PAGE_TRACKING.

To allow such reuse of the flags, this commit separates the PG_young and PG_idle flag logic from IDLE_PAGE_TRACKING and introduces new kernel config, 'PAGE_IDLE_FLAG'. Hence, a new subsystem would be able to reuse PG_idle without depending on IDLE_PAGE_TRACKING.

In the next commit, DAMON's reference implementation of the virtual memory address space monitoring primitives will use it.

Signed-off-by SeongJae Park <[email protected]>

From: SeongJae Park <[email protected]>

This commit introduces a reference implementation of the address space specific low level primitives for the virtual address space, so that users of DAMON can easily monitor the data accesses on virtual address spaces of specific processes by simply configuring the implementation to be used by DAMON.

The low level primitives for the fundamental access monitoring are defined in two parts:

1. Identification of the monitoring target address range for the address space.
2. Access check of specific address range in the target space.

The reference implementation for the virtual address space does the works as below.

PTE Accessed-bit Based Access Check
-----------------------------------

The implementation uses PTE Accessed-bit for basic access checks. That is, it clears the bit for next sampling target page and checks whether

it set again after one sampling period. This could disturb the reclaim

logic. DAMON uses ``PG_idle`` and ``PG_young`` page flags to solve the conflict, as Idle page tracking does.

VMA-based Target Address Range Construction
-------------------------------------------

Only small parts in the super-huge virtual address space of the processes are mapped to physical memory and accessed. Thus, tracking the unmapped address regions is just wasteful. However, because DAMON can deal with some level of noise using the adaptive regions adjustment mechanism, tracking every mapping is not strictly required but could even incur a high overhead in some cases. That said, too huge unmapped areas inside the monitoring target should be removed to not take the time for the adaptive mechanism.

For the reason, this implementation converts the complex mappings to three distinct regions that cover every mapped area of the address space. Also, the two gaps between the three regions are the two biggest unmapped areas in the given address space. The two biggest unmapped areas would be the gap between the heap and the uppermost mmap()-ed region, and the gap between the lowermost mmap()-ed region and the stack in most of the cases. Because these gaps are exceptionally huge in usual address spacees, excluding these will be sufficient to make a

reasonable trade-off. Below shows this in detail::

<heap>
<BIG UNMAPPED REGION 1>
<uppermost mmap()-ed region>
(small mmap()-ed regions and munmap()-ed regions) <lowermost mmap()-ed region>
<BIG UNMAPPED REGION 2>
<stack>

Signed-off-by SeongJae Park <[email protected]>

Reviewed-by Leonard Foerster <[email protected]>

---
 include/linux/damon.h |  13 +
 mm/damon/Kconfig      |   9 +
 mm/damon/Makefile     |   1 +
 mm/damon/vaddr.c      | 579 ++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 602 insertions(+)
 create mode 100644 mm/damon/vaddr.c

include/linux/damon.h +0 -0

index f446f8433599..39b4d6d3ddee 100644
@@ -274,4 +274,17 @@ int damon_stop(struct damon_ctx **ctxs, int nr_ctxs);
 
 #endif /* CONFIG_DAMON */
 

include/linux/damon.h +1 -0

+

include/linux/damon.h +20 -0

+
+static bool damon_va_young(struct mm_struct *mm, unsigned long addr,
+                       unsigned long *page_sz)
+{
+       pte_t *pte = NULL;
+       pmd_t *pmd = NULL;
+       spinlock_t *ptl;
+       bool young = false;
+
+       if (follow_pte_pmd(mm, addr, NULL, &pte, &pmd, &ptl))
+               return false;
+
+       *page_sz = PAGE_SIZE;
+       if (pte) {
+               young = pte_young(*pte);
+               if (!young)
+                       young = !page_is_idle(pte_page(*pte));
+               pte_unmap_unlock(pte, ptl);
+               return young;
+       }

Quoted 22 lines · SeongJae Park

From: SeongJae Park <[email protected]>

This commit introduces a reference implementation of the address space specific low level primitives for the virtual address space, so that users of DAMON can easily monitor the data accesses on virtual address spaces of specific processes by simply configuring the implementation to be used by DAMON.

The low level primitives for the fundamental access monitoring are defined in two parts:

1. Identification of the monitoring target address range for the address space.
2. Access check of specific address range in the target space.

The reference implementation for the virtual address space does the works as below.

PTE Accessed-bit Based Access Check
-----------------------------------

Quoted 2 lines

The implementation uses PTE Accessed-bit for basic access checks. That is, it clears the bit for next sampling target page and checks whether

'for the next'

Quoted 1 line

it set again after one sampling period. This could disturb the reclaim

'it is set'

Quoted 16 lines

logic. DAMON uses ``PG_idle`` and ``PG_young`` page flags to solve the conflict, as Idle page tracking does.

VMA-based Target Address Range Construction
-------------------------------------------

Only small parts in the super-huge virtual address space of the processes are mapped to physical memory and accessed. Thus, tracking the unmapped address regions is just wasteful. However, because DAMON can deal with some level of noise using the adaptive regions adjustment mechanism, tracking every mapping is not strictly required but could even incur a high overhead in some cases. That said, too huge unmapped areas inside the monitoring target should be removed to not take the time for the adaptive mechanism.

Quoted 8 lines

For the reason, this implementation converts the complex mappings to three distinct regions that cover every mapped area of the address space. Also, the two gaps between the three regions are the two biggest unmapped areas in the given address space. The two biggest unmapped areas would be the gap between the heap and the uppermost mmap()-ed region, and the gap between the lowermost mmap()-ed region and the stack in most of the cases. Because these gaps are exceptionally huge in usual address spacees, excluding these will be sufficient to make a

*spaces

Quoted 29 lines

reasonable trade-off. Below shows this in detail::

<heap>
<BIG UNMAPPED REGION 1>
<uppermost mmap()-ed region>
(small mmap()-ed regions and munmap()-ed regions) <lowermost mmap()-ed region>
<BIG UNMAPPED REGION 2>
<stack>

Signed-off-by SeongJae Park <[email protected]>

Reviewed-by Leonard Foerster <[email protected]>

---
 include/linux/damon.h |  13 +
 mm/damon/Kconfig      |   9 +
 mm/damon/Makefile     |   1 +
 mm/damon/vaddr.c      | 579 ++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 602 insertions(+)
 create mode 100644 mm/damon/vaddr.c

include/linux/damon.h +0 -0

index f446f8433599..39b4d6d3ddee 100644
@@ -274,4 +274,17 @@ int damon_stop(struct damon_ctx **ctxs, int nr_ctxs);
 
 #endif /* CONFIG_DAMON */
 

include/linux/damon.h int damon_stop(struct damon_ctx **ctxs, int nr_ctxs); · line 286

Quoted 10 lines

include/linux/damon.h +10 -0

+#ifdef CONFIG_DAMON_VADDR
+
+/* Monitoring primitives for virtual memory address spaces */
+void damon_va_init_regions(struct damon_ctx *ctx);
+void damon_va_update_regions(struct damon_ctx *ctx);
+void damon_va_prepare_access_checks(struct damon_ctx *ctx);
+unsigned int damon_va_check_accesses(struct damon_ctx *ctx);
+bool damon_va_target_valid(void *t);
+void damon_va_cleanup(struct damon_ctx *ctx);
+void damon_va_set_primitives(struct damon_ctx *ctx);

Any reason for these to be in the header?

Quoted 2 lines

include/linux/damon.h +1 -0

+

[snip]

Quoted 25 lines

include/linux/damon.h +25 -0

+
+static bool damon_va_young(struct mm_struct *mm, unsigned long addr,
+                       unsigned long *page_sz)
+{
+       pte_t *pte = NULL;
+       pmd_t *pmd = NULL;
+       spinlock_t *ptl;
+       bool young = false;
+
+       if (follow_pte_pmd(mm, addr, NULL, &pte, &pmd, &ptl))
+               return false;
+
+       *page_sz = PAGE_SIZE;
+       if (pte) {
+               young = pte_young(*pte);
+               if (!young)
+                       young = !page_is_idle(pte_page(*pte));
+               pte_unmap_unlock(pte, ptl);
+               return young;
+       }
+
+#ifdef CONFIG_TRANSPARENT_HUGEPAGE
+       young = pmd_young(*pmd);
+       if (!young)
+               young = !page_is_idle(pmd_page(*pmd));

include/linux/damon.h

Quoted 5 lines

include/linux/damon.h +5 -0

+       spin_unlock(ptl);
+       *page_sz = ((1UL) << HPAGE_PMD_SHIFT);
+#endif /* CONFIG_TRANSPARENT_HUGEPAGE */
+
+       return young;

You need mmu_notifier_test_young() here. Hmm I remember mentioning this in some previous version as well.

Don't you need mmu_notifier_clear_young() here?

BTW have you tested this on a VM?

The patch looks good overall.

Quoted 26 lines

[snip]

Quoted 25 lines

mm/damon/vaddr.c new file +25 -0

+
+static bool damon_va_young(struct mm_struct *mm, unsigned long addr,
+                       unsigned long *page_sz)
+{
+       pte_t *pte = NULL;
+       pmd_t *pmd = NULL;
+       spinlock_t *ptl;
+       bool young = false;
+
+       if (follow_pte_pmd(mm, addr, NULL, &pte, &pmd, &ptl))
+               return false;
+
+       *page_sz = PAGE_SIZE;
+       if (pte) {
+               young = pte_young(*pte);
+               if (!young)
+                       young = !page_is_idle(pte_page(*pte));
+               pte_unmap_unlock(pte, ptl);
+               return young;
+       }
+
+#ifdef CONFIG_TRANSPARENT_HUGEPAGE
+       young = pmd_young(*pmd);
+       if (!young)
+               young = !page_is_idle(pmd_page(*pmd));

Quoted 8 lines

mm/damon/vaddr.c line 488

Quoted 5 lines

mm/damon/vaddr.c new file +5 -0

+       spin_unlock(ptl);
+       *page_sz = ((1UL) << HPAGE_PMD_SHIFT);
+#endif /* CONFIG_TRANSPARENT_HUGEPAGE */
+
+       return young;

You need mmu_notifier_test_young() here. Hmm I remember mentioning this in some previous version as well.

Your question and my answer was as below:

Quoted 1 line

Don't you need mmu_notifier_clear_young() here?

I think we don't need it here because we only read the Accessed bit and PG_Idle if Accessed bit was not set.

I should notice that you mean 'test_young()' but didn't, sorry. I will add it in the next version.