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.

That said, this commit is implementing only basic data structures and simple manipulation functions of the structures. The core mechanisms of DAMON will be implemented by following commits.

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

Reviewed-by Leonard Foerster <[email protected]>

Reviewed-by Varad Gautam <[email protected]>

---

Quoted 29 lines · SeongJae Park

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.

That said, this commit is implementing only basic data structures and simple manipulation functions of the structures. The core mechanisms of DAMON will be implemented by following commits.

Quoted 3 lines

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

Reviewed-by Leonard Foerster <[email protected]>

Reviewed-by Varad Gautam <[email protected]>

I don't see any benefit of this patch on its own. Some of this should be part of the main damon context patch.

I would suggest to separate
the core (damon context) from the target related structs (target, region, addr range).

Also I would prefer the code be added with the actual usage otherwise it is hard to review.

Quoted 2 lines

---

[snip]

mm/damon/core.c line 121

Quoted 10 lines

mm/damon/core.c new file +10 -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++;
+
+       return nr_regions;
+}

Why not keep a count instead of traversing to get the size?

Hi Shakeel,

Thanks for the review! :D

Quoted 34 lines · On Wed, 25 Nov 2020 07:29:10 -0800 Shakeel Butt <[email protected]> wrote:

Quoted 32 lines · SeongJae Park

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.

That said, this commit is implementing only basic data structures and simple manipulation functions of the structures. The core mechanisms of DAMON will be implemented by following commits.

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

Reviewed-by Leonard Foerster <[email protected]>

Reviewed-by Varad Gautam <[email protected]>

Quoted 3 lines

I would suggest to separate
the core (damon context) from the target related structs (target, region, addr range).

To be honest, I unsure if I'm fully understanding what specific change you want to make. So if I'm misunderstanding your point below, please let me know.

Seems like you are concerning for future support of special kind use cases that don't need targets/regions/addresses, such as page granularity monitoring that having interest in only if the pages accessed or not, rather than access frequency. In the context, your suggestion makes sense as the region abstraction is only burden in the case, as I also mentioned in the cover letter. This could be done via idle pages tracking, but DAMON will be able to do this faster by reducing the number of user-kernel context switches.

I once considered adding some change in the core part for efficient support of such use cases, but resulted in believing that the best way for that is implementing another primitive for the case and use it in a controlled way.

In a high level, it should disable the 'adaptive regions adjustment' feature and define it's own targets structs other than the damon_target. Then, your implementation of the primitive callbacks should use your own targets.

In more detail, the 'adaptive regions adjustment' can be disabled by setting the min_nr_regions and max_nr_regions of the damon_ctx with same value, say, 0. Your own targets structs could be stored in 'damon_callback->private'. Or, we could add another 'private' field in damon_ctx for that.

I think this will work, but I also admit that this could look like a hairy hack to someone. Fundamentally, this is because the region based overhead/accuracy handling is strongly coupled in the design. So, I think what you are really suggesting is making DAMON more general by default and supporting the region based overhead/accuracy handling additionally.

If I'm understanding correctly, how about below like change? Obviously this should be cleaned up a lot, but I just want to quickly share my idea and discuss. Also note that it's based on the damon/next tree[1].

[1] https://github.com/sjp38/linux/tree/damon/next

(quoted diff) +18 -5

+enum damon_type {
+       ARBITRARY_TARGETS,
+       ADAPTIVE_REGIONS,
+};
+
+struct damon_adaptive_regions_ctx {
+       unsigned long min_nr_regions;
+       unsigned long max_nr_regions;
+       struct list_head targets;
+       struct list_head schemes;
+};
+
 /**
  * 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

@@ -243,8 +255,6 @@ struct damon_ctx {
        unsigned long sample_interval;
        unsigned long aggr_interval;
        unsigned long regions_update_interval;
-       unsigned long min_nr_regions;
-       unsigned long max_nr_regions;
 
        struct timespec64 last_aggregation;
        struct timespec64 last_regions_update;

@@ -253,11 +263,14 @@ struct damon_ctx {
        bool kdamond_stop;
        struct mutex kdamond_lock;
 
-       struct list_head targets_list;  /* 'damon_target' objects */
-       struct list_head schemes_list;  /* 'damos' objects */
-
        struct damon_primitive primitive;
        struct damon_callback callback;
+
+       enum damon_type type;
+       union {
+               struct damon_adaptive_regions_ctx arctx;
+               void *targets;
+       };
 };
 

The patchset will first introduce DAMON as only ARBITRARY_TARGETS (or, would TINY be a better name?) type supporting form. After that, following patch will add ADAPTIVE_REGIONS type support. Do you think I'm correctly understanding your point and above suggestion makes sense?

From: SeongJae Park <[email protected]>

DAMON separates its monitoring target address space independent high level logics

from the target space dependent low level primitives for flexible support of various address spaces.

This commit implements DAMON's target address space independent high level logics for basic access check and region based sampling.

Hence,
without the target address space specific parts implementations, this doesn't work alone. A reference implementation of those will be provided by a later commit.

Basic Access Check
==================

The output of DAMON says what pages 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 page. 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 monitoring overhead of this mechanism will arbitrarily increase as the size of the target workload grows.

Region Based Sampling
=====================

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``, DAMON randomly picks one page in each region, waits for one ``sampling interval``, checks whether the page is accessed meanwhile, and increases the access frequency of the region if so. Therefore, the monitoring overhead is controllable by setting the number of regions. DAMON allows users to set the minimum and the maximum number of regions for the trade-off.

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

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

Reviewed-by Leonard Foerster <[email protected]>

---
 include/linux/damon.h | 133 ++++++++++++++++-
 mm/damon/core.c       | 333 ++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 465 insertions(+), 1 deletion(-)

include/linux/damon.h +106 -1

index 183e0edd7f43..1f7b095646c2 100644
@@ -8,6 +8,8 @@
 #ifndef _DAMON_H_
 #define _DAMON_H_
 
+#include <linux/mutex.h>
+#include <linux/time64.h>
 #include <linux/types.h>
 
 /**

@@ -23,11 +25,13 @@ struct damon_addr_range {
 /**
  * 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;
 };

@@ -50,12 +54,130 @@ struct damon_target {
        struct list_head list;
 };
 
+struct damon_ctx;
+
 /**
- * struct damon_ctx - Represents a context for each monitoring.
+ * struct damon_primitive      Monitoring primitives for given use cases.
+ *
+ * @init_target_regions:       Constructs initial monitoring target regions.
+ * @prepare_access_checks:     Prepares next access check of target regions.
+ * @check_accesses:            Checks the access of target regions.
+ * @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 before starting the monitoring and
+ * @prepare_access_checks, @check_accesses, and @target_valid for each
+ * @sample_interval.
+ *
+ * @init_target_regions should construct proper monitoring target regions and
+ * link those to the DAMON context struct.
+ * @prepare_access_checks should manipulate the monitoring regions to be
+ * prepare for the next access check.
+ * @check_accesses should check the accesses to each region that made after the
+ * last preparation and update the `->nr_accesses` of each region.  It should
+ * also return max &damon_region.nr_accesses that made as a result of its
+ * update.
+ * @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 (*prepare_access_checks)(struct damon_ctx *context);
+       unsigned int (*check_accesses)(struct damon_ctx *context);
+       bool (*target_valid)(struct damon_target *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 the monitoring and just before
+ * finishing the monitoring.  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 via
+ * &damon_ctx.targets_list without additional protection of
+ * damon_ctx.kdamond_lock.  For the reason, users are recommended to use these
+ * callback for the accesses to the results.
+ *
+ * If any callback returns non-zero, monitoring stops.
+ */
+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
+ * of the monitoring.
+ *
+ * @sample_interval:           The time between access samplings.
+ * @aggr_interval:             The time between monitor results aggregations.
+ * @nr_regions:                        The number of monitoring regions.
+ *
+ * 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.  All time intervals are in
+ * micro-seconds.
+ *
+ * @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 @target_valid callback.  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.

include/linux/damon.h +19 -0

+
+       struct timespec64 last_aggregation;
+
+       struct task_struct *kdamond;
+       bool kdamond_stop;
+       struct mutex kdamond_lock;
+
        struct list_head targets_list;  /* 'damon_target' objects */
+
+       struct damon_primitive primitive;
+       struct damon_callback callback;
 };
 
 #define damon_next_region(r) \

@@ -90,6 +212,15 @@ 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);
 
+int damon_set_targets(struct damon_ctx *ctx,
+               unsigned long *ids, ssize_t nr_ids);
+int damon_set_attrs(struct damon_ctx *ctx, unsigned long sample_int,
+               unsigned long aggr_int, unsigned long nr_reg);
+
+int damon_nr_running_ctxs(void);
+int damon_start(struct damon_ctx **ctxs, int nr_ctxs);
+int damon_stop(struct damon_ctx **ctxs, int nr_ctxs);
+
 #endif /* CONFIG_DAMON */
 
 #endif

mm/damon/core.c +29 -0

index 4562b2458719..eb4ebeaa064d 100644
@@ -8,12 +8,20 @@
 #define pr_fmt(fmt) "damon: " fmt
 
 #include <linux/damon.h>
+#include <linux/delay.h>
+#include <linux/kthread.h>
 #include <linux/slab.h>
 
+/* Minimal region size.  Every damon_region is aligned by this. */
+#define MIN_REGION PAGE_SIZE
+
 /*
  * Functions and macros for DAMON data structures
  */
 
+static DEFINE_MUTEX(damon_lock);
+static int nr_running_ctxs;
+
 /*
  * Construct a damon_region struct
  *

@@ -119,3 +127,328 @@ unsigned int damon_nr_regions(struct damon_target *t)
 
        return nr_regions;
 }
+
+/**
+ * damon_set_targets() - Set monitoring targets.
+ * @ctx:       monitoring context
+ * @ids:       array of target ids
+ * @nr_ids:    number of entries in @ids
+ *
+ * This function should not be called while the kdamond is running.
+ *
+ * Return: 0 on success, negative error code otherwise.
+ */
+int damon_set_targets(struct damon_ctx *ctx,
+                     unsigned long *ids, ssize_t nr_ids)
+{
+       ssize_t i;
+       struct damon_target *t, *next;
+
+       damon_for_each_target_safe(t, next, ctx)
+               damon_destroy_target(t);
+
+       for (i = 0; i < nr_ids; i++) {

mm/damon/core.c +80 -0

+
+/**
+ * damon_set_attrs() - Set attributes for the monitoring.
+ * @ctx:               monitoring context
+ * @sample_int:                time interval between samplings
+ * @aggr_int:          time interval between aggregations
+ * @nr_reg:            number of regions
+ *
+ * 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 nr_reg)
+{
+       if (nr_reg < 3) {
+               pr_err("nr_regions (%lu) must be at least 3\n",
+                               nr_reg);
+               return -EINVAL;
+       }
+
+       ctx->sample_interval = sample_int;
+       ctx->aggr_interval = aggr_int;
+       ctx->nr_regions = nr_reg;
+
+       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.

mm/damon/core.c +125 -0

+               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;
+}
+
+/*
+ * Functions for DAMON core logics
+ */
+
+/*
+ * 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);
+}
+
+/*
+ * 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 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)
+{
+       struct damon_target *t;
+       bool stop;
+
+       mutex_lock(&ctx->kdamond_lock);
+       stop = ctx->kdamond_stop;
+       mutex_unlock(&ctx->kdamond_lock);

mm/damon/core.c +12 -0

+
+       return true;
+}
+
+static void set_kdamond_stop(struct damon_ctx *ctx, bool stop)
+{
+       mutex_lock(&ctx->kdamond_lock);
+       ctx->kdamond_stop = stop;
+       mutex_unlock(&ctx->kdamond_lock);
+}
+
+#define kdamond_call_prmt(ctx, fn)                     \

mm/damon/core.c +35 -1

+       kdamond_call_prmt(ctx, init_target_regions);
+       kdamond_callback(ctx, before_start);
+
+       while (!kdamond_need_stop(ctx)) {
+               kdamond_call_prmt(ctx, prepare_access_checks);
+               kdamond_callback(ctx, after_sampling);
+
+               usleep_range(ctx->sample_interval, ctx->sample_interval + 1);
+
+               kdamond_call_prmt(ctx, check_accesses);
+
+               if (kdamond_aggregate_interval_passed(ctx)) {
+                       kdamond_callback(ctx, after_aggregation);
+                       kdamond_reset_aggregated(ctx);
+               }
+       }
+       damon_for_each_target(t, ctx) {
+               damon_for_each_region_safe(r, next, t)
+                       damon_destroy_region(r);
+       }
+
+       kdamond_callback(ctx, before_terminate);
+       kdamond_call_prmt(ctx, cleanup);
+
+       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

Quoted 5 lines · SeongJae Park

From: SeongJae Park <[email protected]>

DAMON separates its monitoring target address space independent high level logics

Please rewrite the above sentence to be more clear.

Quoted 6 lines

from the target space dependent low level primitives for flexible support of various address spaces.

This commit implements DAMON's target address space independent high level logics for basic access check and region based sampling.

Same for the above text.

Quoted 30 lines

Hence,
without the target address space specific parts implementations, this doesn't work alone. A reference implementation of those will be provided by a later commit.

Basic Access Check
==================

The output of DAMON says what pages 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 page. 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)

Quoted 3 lines

The monitoring overhead of this mechanism will arbitrarily increase as the size of the target workload grows.

Please move the sampling part in a separate patch.

Quoted 167 lines

Region Based Sampling
=====================

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``, DAMON randomly picks one page in each region, waits for one ``sampling interval``, checks whether the page is accessed meanwhile, and increases the access frequency of the region if so. Therefore, the monitoring overhead is controllable by setting the number of regions. DAMON allows users to set the minimum and the maximum number of regions for the trade-off.

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

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

Reviewed-by Leonard Foerster <[email protected]>

---
 include/linux/damon.h | 133 ++++++++++++++++-
 mm/damon/core.c       | 333 ++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 465 insertions(+), 1 deletion(-)

include/linux/damon.h +110 -1

index 183e0edd7f43..1f7b095646c2 100644
@@ -8,6 +8,8 @@
 #ifndef _DAMON_H_
 #define _DAMON_H_
 
+#include <linux/mutex.h>
+#include <linux/time64.h>
 #include <linux/types.h>
 
 /**

@@ -23,11 +25,13 @@ struct damon_addr_range {
 /**
  * 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;
 };

@@ -50,12 +54,130 @@ struct damon_target {
        struct list_head list;
 };
 
+struct damon_ctx;
+
 /**
- * struct damon_ctx - Represents a context for each monitoring.
+ * struct damon_primitive      Monitoring primitives for given use cases.
+ *
+ * @init_target_regions:       Constructs initial monitoring target regions.
+ * @prepare_access_checks:     Prepares next access check of target regions.
+ * @check_accesses:            Checks the access of target regions.
+ * @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 before starting the monitoring and
+ * @prepare_access_checks, @check_accesses, and @target_valid for each
+ * @sample_interval.
+ *
+ * @init_target_regions should construct proper monitoring target regions and
+ * link those to the DAMON context struct.
+ * @prepare_access_checks should manipulate the monitoring regions to be
+ * prepare for the next access check.
+ * @check_accesses should check the accesses to each region that made after the
+ * last preparation and update the `->nr_accesses` of each region.  It should
+ * also return max &damon_region.nr_accesses that made as a result of its
+ * update.
+ * @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 (*prepare_access_checks)(struct damon_ctx *context);
+       unsigned int (*check_accesses)(struct damon_ctx *context);
+       bool (*target_valid)(struct damon_target *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 the monitoring and just before
+ * finishing the monitoring.  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 via
+ * &damon_ctx.targets_list without additional protection of
+ * damon_ctx.kdamond_lock.  For the reason, users are recommended to use these
+ * callback for the accesses to the results.
+ *
+ * If any callback returns non-zero, monitoring stops.
+ */
+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
+ * of the monitoring.
+ *
+ * @sample_interval:           The time between access samplings.
+ * @aggr_interval:             The time between monitor results aggregations.
+ * @nr_regions:                        The number of monitoring regions.
+ *
+ * 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.  All time intervals are in
+ * micro-seconds.
+ *
+ * @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 @target_valid callback.  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.
+ *
  * @targets_list:      Head of monitoring targets (&damon_target) list.
+ *
+ * @primitive: Set of monitoring primitives for given use cases.
+ * @callback:  Set of callbacks for monitoring events notifications.
  */
 struct damon_ctx {

include/linux/damon.h struct damon_target { · line 169

Quoted 3 lines

include/linux/damon.h +3 -0

+       unsigned long sample_interval;
+       unsigned long aggr_interval;
+       unsigned long nr_regions;

IMO region is the property of the target being monitored. There might be multiple types of target which might need the same abstraction like damon_region and damon_addr_range but that sharing can be done at that time.

Quoted 89 lines

include/linux/damon.h +19 -0

+
+       struct timespec64 last_aggregation;
+
+       struct task_struct *kdamond;
+       bool kdamond_stop;
+       struct mutex kdamond_lock;
+
        struct list_head targets_list;  /* 'damon_target' objects */
+
+       struct damon_primitive primitive;
+       struct damon_callback callback;
 };
 
 #define damon_next_region(r) \

@@ -90,6 +212,15 @@ 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);
 
+int damon_set_targets(struct damon_ctx *ctx,
+               unsigned long *ids, ssize_t nr_ids);
+int damon_set_attrs(struct damon_ctx *ctx, unsigned long sample_int,
+               unsigned long aggr_int, unsigned long nr_reg);
+
+int damon_nr_running_ctxs(void);
+int damon_start(struct damon_ctx **ctxs, int nr_ctxs);
+int damon_stop(struct damon_ctx **ctxs, int nr_ctxs);
+
 #endif /* CONFIG_DAMON */
 
 #endif

mm/damon/core.c +37 -0

index 4562b2458719..eb4ebeaa064d 100644
@@ -8,12 +8,20 @@
 #define pr_fmt(fmt) "damon: " fmt
 
 #include <linux/damon.h>
+#include <linux/delay.h>
+#include <linux/kthread.h>
 #include <linux/slab.h>
 
+/* Minimal region size.  Every damon_region is aligned by this. */
+#define MIN_REGION PAGE_SIZE
+
 /*
  * Functions and macros for DAMON data structures
  */
 
+static DEFINE_MUTEX(damon_lock);
+static int nr_running_ctxs;
+
 /*
  * Construct a damon_region struct
  *

@@ -119,3 +127,328 @@ unsigned int damon_nr_regions(struct damon_target *t)
 
        return nr_regions;
 }
+
+/**
+ * damon_set_targets() - Set monitoring targets.
+ * @ctx:       monitoring context
+ * @ids:       array of target ids
+ * @nr_ids:    number of entries in @ids
+ *
+ * This function should not be called while the kdamond is running.
+ *
+ * Return: 0 on success, negative error code otherwise.
+ */
+int damon_set_targets(struct damon_ctx *ctx,
+                     unsigned long *ids, ssize_t nr_ids)
+{
+       ssize_t i;
+       struct damon_target *t, *next;
+
+       damon_for_each_target_safe(t, next, ctx)
+               damon_destroy_target(t);
+
+       for (i = 0; i < nr_ids; i++) {
+               t = damon_new_target(ids[i]);
+               if (!t) {
+                       pr_err("Failed to alloc damon_target\n");
+                       return -ENOMEM;
+               }
+               damon_add_target(ctx, t);
+       }
+

mm/damon/core.c unsigned int damon_nr_regions(struct damon_target *t) · line 160

Quoted 2 lines

mm/damon/core.c +2 -0

+       return 0;
+}

This function looks weird and without usage. I suppose this is called when a user requests to set up monitoring targets. I would change this to add targets one by one. At the moment, it removes the older targets and adds newer ones which can fail and will leave the context in a weird state.

BTW this function should come in the patch which introduces the user interface.

Quoted 85 lines

mm/damon/core.c +84 -0

+
+/**
+ * damon_set_attrs() - Set attributes for the monitoring.
+ * @ctx:               monitoring context
+ * @sample_int:                time interval between samplings
+ * @aggr_int:          time interval between aggregations
+ * @nr_reg:            number of regions
+ *
+ * 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 nr_reg)
+{
+       if (nr_reg < 3) {
+               pr_err("nr_regions (%lu) must be at least 3\n",
+                               nr_reg);
+               return -EINVAL;
+       }
+
+       ctx->sample_interval = sample_int;
+       ctx->aggr_interval = aggr_int;
+       ctx->nr_regions = nr_reg;
+
+       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)

mm/damon/core.c unsigned int damon_nr_regions(struct damon_target *t) · line 250

Quoted 6 lines

mm/damon/core.c +6 -0

+{
+       int i;
+       int err = 0;
+
+       mutex_lock(&damon_lock);
+       if (nr_running_ctxs) {

What is this checking?

Quoted 131 lines

mm/damon/core.c +130 -0

+               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;
+}
+
+/*
+ * Functions for DAMON core logics
+ */
+
+/*
+ * 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);
+}
+
+/*
+ * 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 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)
+{
+       struct damon_target *t;
+       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;

mm/damon/core.c unsigned int damon_nr_regions(struct damon_target *t) · line 385

Quoted 5 lines

mm/damon/core.c +5 -0

+
+       damon_for_each_target(t, ctx) {
+               if (ctx->primitive.target_valid(t))
+                       return false;
+       }

Why check for valid target? Are we gonna create a new kthread when the user set the new target?

Quoted 19 lines

mm/damon/core.c +18 -0

+
+       return true;
+}
+
+static void set_kdamond_stop(struct damon_ctx *ctx, bool stop)
+{
+       mutex_lock(&ctx->kdamond_lock);
+       ctx->kdamond_stop = stop;
+       mutex_unlock(&ctx->kdamond_lock);
+}
+
+#define kdamond_call_prmt(ctx, fn)                     \
+       do {                                            \
+               if (ctx->primitive.fn)                  \
+                       ctx->primitive.fn(ctx);         \
+       } while (0)
+
+#define kdamond_callback(ctx, fn)                              \

mm/damon/core.c unsigned int damon_nr_regions(struct damon_target *t) · line 407

Quoted 4 lines

mm/damon/core.c +4 -0

+       do {                                                    \
+               if (ctx->callback.fn && ctx->callback.fn(ctx))  \
+                       set_kdamond_stop(ctx, true);            \
+       } while (0)

I don't think these macros are helpful rather they make code harder to grasp. Also don't hide the function call like set_kdamond_stop() in a macro.

mm/damon/core.c unsigned int damon_nr_regions(struct damon_target *t) · line 419

Quoted 13 lines

mm/damon/core.c +12 -0

+
+/*
+ * The monitoring daemon that runs as a kernel thread
+ */
+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);
+

Call the callbacks explicitly.

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]>

Quoted 20 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.

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.

Quoted 2 lines

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

Reviewed-by Leonard Foerster <[email protected]>

The high level comment I have is that kdamond_[merge|split]_regions should be part of the abstraction of the target instead of the damon context.

From: SeongJae Park <[email protected]>

The monitoring target address range can be dynamically changed. For example, virtual memory could be dynamically mapped and unmapped. Physical memory could be hot-plugged.

As the changes could be quite frequent in some cases,

DAMON checks the
dynamic memory mapping changes and applies it to the abstracted target area only for each of a user-specified time interval, ``regions update interval``.

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

Reviewed-by Leonard Foerster <[email protected]>

mm/damon/core.c +2 -1

+                       sz_limit = damon_region_sz_limit(ctx);
+               }
        }
        damon_for_each_target(t, ctx) {
                damon_for_each_region_safe(r, next, t)
--

2.17.1

Quoted 3 lines · SeongJae Park

From: SeongJae Park <[email protected]>

Quoted 5 lines

The monitoring target address range can be dynamically changed. For example, virtual memory could be dynamically mapped and unmapped. Physical memory could be hot-plugged.

As the changes could be quite frequent in some cases,

Which cases? Usually address space changes are very infrequent for performance reasons.

Quoted 8 lines

DAMON checks the
dynamic memory mapping changes and applies it to the abstracted target area only for each of a user-specified time interval, ``regions update interval``.

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

Reviewed-by Leonard Foerster <[email protected]>

[snip]

mm/damon/core.c static int kdamond_fn(void *data) · line 630

Quoted 9 lines

* Check whether current monitoring should be stopped *

mm/damon/core.c +3 -0

@@ -612,6 +625,11 @@ static int kdamond_fn(void *data)
                        kdamond_reset_aggregated(ctx);
                        kdamond_split_regions(ctx);
                }
+
+               if (kdamond_need_update_regions(ctx)) {
+                       kdamond_call_prmt(ctx, update_target_regions);

The implementation of update_target_regions callback should be part of this patch.

Quoted 10 lines

mm/damon/core.c +2 -1

+                       sz_limit = damon_region_sz_limit(ctx);
+               }
        }
        damon_for_each_target(t, ctx) {
                damon_for_each_region_safe(r, next, t)
--

2.17.1

From: SeongJae Park <[email protected]>

PG_idle and PG_young allows 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

and PG_idle 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

and PG_idle, respectively, 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, it would be only waste the space. Instead, if the new subsystem is mutually exclusive with IDLE_PAGE_TRACKING, it could 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, if !IDLE_PAGE_TRACKING and IDLE_PAGE_FLAG, a new subsystem would be able to reuse PG_idle.

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]>

---
 include/linux/page-flags.h     |  4 ++--
 include/linux/page_ext.h       |  2 +-
 include/linux/page_idle.h      |  6 +++---
 include/trace/events/mmflags.h |  2 +-
 mm/Kconfig                     |  8 ++++++++
 mm/page_ext.c                  | 12 +++++++++++-
 mm/page_idle.c                 | 10 ----------
 7 files changed, 26 insertions(+), 18 deletions(-)

include/linux/page-flags.h +2 -2

index 6be1aa559b1e..7736d290bb61 100644
@@ -132,7 +132,7 @@ enum pageflags {
 #ifdef CONFIG_MEMORY_FAILURE
        PG_hwpoison,            /* hardware poisoned page. Don't touch */
 #endif
-#if defined(CONFIG_IDLE_PAGE_TRACKING) && defined(CONFIG_64BIT)
+#if defined(CONFIG_PAGE_IDLE_FLAG) && defined(CONFIG_64BIT)
        PG_young,
        PG_idle,
 #endif

@@ -432,7 +432,7 @@ static inline bool set_hwpoison_free_buddy_page(struct page *page)
 #define __PG_HWPOISON 0
 #endif
 
-#if defined(CONFIG_IDLE_PAGE_TRACKING) && defined(CONFIG_64BIT)
+#if defined(CONFIG_PAGE_IDLE_FLAG) && defined(CONFIG_64BIT)
 TESTPAGEFLAG(Young, young, PF_ANY)
 SETPAGEFLAG(Young, young, PF_ANY)
 TESTCLEARFLAG(Young, young, PF_ANY)

include/linux/page_ext.h +1 -1

index cfce186f0c4e..c9cbc9756011 100644
@@ -19,7 +19,7 @@ struct page_ext_operations {
 enum page_ext_flags {
        PAGE_EXT_OWNER,
        PAGE_EXT_OWNER_ALLOCATED,
-#if defined(CONFIG_IDLE_PAGE_TRACKING) && !defined(CONFIG_64BIT)
+#if defined(CONFIG_PAGE_IDLE_FLAG) && !defined(CONFIG_64BIT)
        PAGE_EXT_YOUNG,
        PAGE_EXT_IDLE,
 #endif

include/linux/page_idle.h +3 -3

index 1e894d34bdce..d8a6aecf99cb 100644
@@ -6,7 +6,7 @@
 #include <linux/page-flags.h>
 #include <linux/page_ext.h>
 
-#ifdef CONFIG_IDLE_PAGE_TRACKING
+#ifdef CONFIG_PAGE_IDLE_FLAG
 
 #ifdef CONFIG_64BIT
 static inline bool page_is_young(struct page *page)

@@ -106,7 +106,7 @@ static inline void clear_page_idle(struct page *page)
 }
 #endif /* CONFIG_64BIT */
 
-#else /* !CONFIG_IDLE_PAGE_TRACKING */
+#else /* !CONFIG_PAGE_IDLE_FLAG */
 
 static inline bool page_is_young(struct page *page)
 {

@@ -135,6 +135,6 @@ static inline void clear_page_idle(struct page *page)
 {
 }
 
-#endif /* CONFIG_IDLE_PAGE_TRACKING */
+#endif /* CONFIG_PAGE_IDLE_FLAG */
 
 #endif /* _LINUX_MM_PAGE_IDLE_H */

include/trace/events/mmflags.h +1 -1

index 5fb752034386..4d182c32071b 100644
@@ -73,7 +73,7 @@
 #define IF_HAVE_PG_HWPOISON(flag,string)
 #endif
 
-#if defined(CONFIG_IDLE_PAGE_TRACKING) && defined(CONFIG_64BIT)
+#if defined(CONFIG_PAGE_IDLE_FLAG) && defined(CONFIG_64BIT)
 #define IF_HAVE_PG_IDLE(flag,string) ,{1UL << flag, string}
 #else
 #define IF_HAVE_PG_IDLE(flag,string)

mm/Kconfig +8 -0

index 19fe2251c87a..044317ef9143 100644
@@ -761,10 +761,18 @@ config DEFERRED_STRUCT_PAGE_INIT
          lifetime of the system until these kthreads finish the
          initialisation.
 
+config PAGE_IDLE_FLAG
+       bool "Add PG_idle and PG_young flags"
+       help
+         This feature adds PG_idle and PG_young flags in 'struct page'.  PTE
+         Accessed bit writers can set the state of the bit in the flags to let
+         other PTE Accessed bit readers don't disturbed.
+
 config IDLE_PAGE_TRACKING
        bool "Enable idle page tracking"
        depends on SYSFS && MMU
        select PAGE_EXTENSION if !64BIT
+       select PAGE_IDLE_FLAG
        help
          This feature allows to estimate the amount of user pages that have
          not been touched during a given period of time. This information can

mm/page_ext.c +0 -0

index a3616f7a0e9e..f9a6ff65ac0a 100644

mm/page_ext.c +11 -1

+#if defined(CONFIG_PAGE_IDLE_FLAG) && !defined(CONFIG_64BIT)
+static bool need_page_idle(void)
+{
+       return true;
+}
+struct page_ext_operations page_idle_ops = {
+       .need = need_page_idle,
+};
+#endif
+
 static struct page_ext_operations *page_ext_ops[] = {
 #ifdef CONFIG_PAGE_OWNER
        &page_owner_ops,
 #endif
-#if defined(CONFIG_IDLE_PAGE_TRACKING) && !defined(CONFIG_64BIT)
+#if defined(CONFIG_PAGE_IDLE_FLAG) && !defined(CONFIG_64BIT)
        &page_idle_ops,
 #endif
 };

mm/page_idle.c +0 -11

index 057c61df12db..144fb4ed961d 100644
@@ -211,16 +211,6 @@ static const struct attribute_group page_idle_attr_group = {
        .name = "page_idle",
 };
 
-#ifndef CONFIG_64BIT
-static bool need_page_idle(void)
-{
-       return true;
-}
-struct page_ext_operations page_idle_ops = {
-       .need = need_page_idle,
-};
-#endif
-
 static int __init page_idle_init(void)
 {
        int err;
--

2.17.1

Quoted 7 lines · SeongJae Park

From: SeongJae Park <[email protected]>

PG_idle and PG_young allows 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

Only PG_young bit

Quoted 4 lines

and PG_idle 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

Again only PG_young bit.

PG_idle bit is only read (and set) by the page idle tracking code and it can be cleared by others (reclaim or file access).

Quoted 132 lines

and PG_idle, respectively, 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, it would be only waste the space. Instead, if the new subsystem is mutually exclusive with IDLE_PAGE_TRACKING, it could 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, if !IDLE_PAGE_TRACKING and IDLE_PAGE_FLAG, a new subsystem would be able to reuse PG_idle.

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]>

---
 include/linux/page-flags.h     |  4 ++--
 include/linux/page_ext.h       |  2 +-
 include/linux/page_idle.h      |  6 +++---
 include/trace/events/mmflags.h |  2 +-
 mm/Kconfig                     |  8 ++++++++
 mm/page_ext.c                  | 12 +++++++++++-
 mm/page_idle.c                 | 10 ----------
 7 files changed, 26 insertions(+), 18 deletions(-)

include/linux/page-flags.h +2 -2

index 6be1aa559b1e..7736d290bb61 100644
@@ -132,7 +132,7 @@ enum pageflags {
 #ifdef CONFIG_MEMORY_FAILURE
        PG_hwpoison,            /* hardware poisoned page. Don't touch */
 #endif
-#if defined(CONFIG_IDLE_PAGE_TRACKING) && defined(CONFIG_64BIT)
+#if defined(CONFIG_PAGE_IDLE_FLAG) && defined(CONFIG_64BIT)
        PG_young,
        PG_idle,
 #endif

@@ -432,7 +432,7 @@ static inline bool set_hwpoison_free_buddy_page(struct page *page)
 #define __PG_HWPOISON 0
 #endif
 
-#if defined(CONFIG_IDLE_PAGE_TRACKING) && defined(CONFIG_64BIT)
+#if defined(CONFIG_PAGE_IDLE_FLAG) && defined(CONFIG_64BIT)
 TESTPAGEFLAG(Young, young, PF_ANY)
 SETPAGEFLAG(Young, young, PF_ANY)
 TESTCLEARFLAG(Young, young, PF_ANY)

include/linux/page_ext.h +1 -1

index cfce186f0c4e..c9cbc9756011 100644
@@ -19,7 +19,7 @@ struct page_ext_operations {
 enum page_ext_flags {
        PAGE_EXT_OWNER,
        PAGE_EXT_OWNER_ALLOCATED,
-#if defined(CONFIG_IDLE_PAGE_TRACKING) && !defined(CONFIG_64BIT)
+#if defined(CONFIG_PAGE_IDLE_FLAG) && !defined(CONFIG_64BIT)
        PAGE_EXT_YOUNG,
        PAGE_EXT_IDLE,
 #endif

include/linux/page_idle.h +3 -3

index 1e894d34bdce..d8a6aecf99cb 100644
@@ -6,7 +6,7 @@
 #include <linux/page-flags.h>
 #include <linux/page_ext.h>
 
-#ifdef CONFIG_IDLE_PAGE_TRACKING
+#ifdef CONFIG_PAGE_IDLE_FLAG
 
 #ifdef CONFIG_64BIT
 static inline bool page_is_young(struct page *page)

@@ -106,7 +106,7 @@ static inline void clear_page_idle(struct page *page)
 }
 #endif /* CONFIG_64BIT */
 
-#else /* !CONFIG_IDLE_PAGE_TRACKING */
+#else /* !CONFIG_PAGE_IDLE_FLAG */
 
 static inline bool page_is_young(struct page *page)
 {

@@ -135,6 +135,6 @@ static inline void clear_page_idle(struct page *page)
 {
 }
 
-#endif /* CONFIG_IDLE_PAGE_TRACKING */
+#endif /* CONFIG_PAGE_IDLE_FLAG */
 
 #endif /* _LINUX_MM_PAGE_IDLE_H */

include/trace/events/mmflags.h +1 -1

index 5fb752034386..4d182c32071b 100644
@@ -73,7 +73,7 @@
 #define IF_HAVE_PG_HWPOISON(flag,string)
 #endif
 
-#if defined(CONFIG_IDLE_PAGE_TRACKING) && defined(CONFIG_64BIT)
+#if defined(CONFIG_PAGE_IDLE_FLAG) && defined(CONFIG_64BIT)
 #define IF_HAVE_PG_IDLE(flag,string) ,{1UL << flag, string}
 #else
 #define IF_HAVE_PG_IDLE(flag,string)

mm/Kconfig +8 -0

index 19fe2251c87a..044317ef9143 100644
@@ -761,10 +761,18 @@ config DEFERRED_STRUCT_PAGE_INIT
          lifetime of the system until these kthreads finish the
          initialisation.
 
+config PAGE_IDLE_FLAG
+       bool "Add PG_idle and PG_young flags"
+       help
+         This feature adds PG_idle and PG_young flags in 'struct page'.  PTE
+         Accessed bit writers can set the state of the bit in the flags to let
+         other PTE Accessed bit readers don't disturbed.
+
 config IDLE_PAGE_TRACKING
        bool "Enable idle page tracking"
        depends on SYSFS && MMU
        select PAGE_EXTENSION if !64BIT
+       select PAGE_IDLE_FLAG
        help
          This feature allows to estimate the amount of user pages that have
          not been touched during a given period of time. This information can

mm/page_ext.c +0 -0

index a3616f7a0e9e..f9a6ff65ac0a 100644

mm/page_ext.c line 60

Quoted 6 lines

mm/page_ext.c +0 -0

@@ -58,11 +58,21 @@
  * can utilize this callback to initialize the state of it correctly.
  */
 

Is there a need to move the following code in this patch?

Quoted 39 lines

mm/page_ext.c +11 -1

+#if defined(CONFIG_PAGE_IDLE_FLAG) && !defined(CONFIG_64BIT)
+static bool need_page_idle(void)
+{
+       return true;
+}
+struct page_ext_operations page_idle_ops = {
+       .need = need_page_idle,
+};
+#endif
+
 static struct page_ext_operations *page_ext_ops[] = {
 #ifdef CONFIG_PAGE_OWNER
        &page_owner_ops,
 #endif
-#if defined(CONFIG_IDLE_PAGE_TRACKING) && !defined(CONFIG_64BIT)
+#if defined(CONFIG_PAGE_IDLE_FLAG) && !defined(CONFIG_64BIT)
        &page_idle_ops,
 #endif
 };

mm/page_idle.c +0 -10

index 057c61df12db..144fb4ed961d 100644
@@ -211,16 +211,6 @@ static const struct attribute_group page_idle_attr_group = {
        .name = "page_idle",
 };
 
-#ifndef CONFIG_64BIT
-static bool need_page_idle(void)
-{
-       return true;
-}
-struct page_ext_operations page_idle_ops = {
-       .need = need_page_idle,
-};
-#endif
-

Quoted 6 lines

mm/page_idle.c +0 -1

 static int __init page_idle_init(void)
 {
        int err;
--

2.17.1

Overall this patch looks good to me.

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 provided by this commit is designed 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 other kernel subsystems using the Accessed bits, namely Idle page tracking and the reclaim logic. To avoid such disturbances, DAMON makes it mutually exclusive with Idle page tracking and uses ``PG_idle`` and ``PG_young`` page flags to solve the conflict with the reclaim logics, 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 |  14 +
 mm/damon/Kconfig      |  10 +
 mm/damon/Makefile     |   1 +
 mm/damon/primitives.c | 582 ++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 607 insertions(+)
 create mode 100644 mm/damon/primitives.c

include/linux/damon.h +14 -0

index b8562814751e..70cc4b54212e 100644
@@ -238,4 +238,18 @@ int damon_stop(struct damon_ctx **ctxs, int nr_ctxs);
 
 #endif /* CONFIG_DAMON */
 
+#ifdef CONFIG_DAMON_PRIMITIVES
+
+/* Reference callback implementations for virtual memory */
+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(struct damon_target *t);
+void damon_va_cleanup(struct damon_ctx *ctx);
+void damon_va_set_primitives(struct damon_ctx *ctx);
+
+#endif /* CONFIG_DAMON_PRIMITIVES */
+
+
 #endif

mm/damon/Kconfig +0 -0

index d00e99ac1a15..0d2a18ddb9d8 100644

mm/damon/primitives.c new file +1 -0

@@ -0,0 +1,582 @@
+// SPDX-License-Identifier: GPL-2.0

mm/damon/primitives.c new file +19 -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 101 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 provided by this commit is designed 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 other kernel subsystems using the Accessed bits, namely Idle page tracking and the reclaim logic. To avoid such disturbances, DAMON makes it mutually exclusive with Idle page tracking and uses ``PG_idle`` and ``PG_young`` page flags to solve the conflict with the reclaim logics, 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 |  14 +
 mm/damon/Kconfig      |  10 +
 mm/damon/Makefile     |   1 +
 mm/damon/primitives.c | 582 ++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 607 insertions(+)
 create mode 100644 mm/damon/primitives.c

include/linux/damon.h +14 -0

index b8562814751e..70cc4b54212e 100644
@@ -238,4 +238,18 @@ int damon_stop(struct damon_ctx **ctxs, int nr_ctxs);
 
 #endif /* CONFIG_DAMON */
 
+#ifdef CONFIG_DAMON_PRIMITIVES
+
+/* Reference callback implementations for virtual memory */
+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(struct damon_target *t);
+void damon_va_cleanup(struct damon_ctx *ctx);
+void damon_va_set_primitives(struct damon_ctx *ctx);
+
+#endif /* CONFIG_DAMON_PRIMITIVES */
+
+
 #endif

mm/damon/Kconfig +0 -0

index d00e99ac1a15..0d2a18ddb9d8 100644
@@ -12,4 +12,14 @@ config DAMON
          See https://damonitor.github.io/doc/html/latest-damon/index.html for
          more information.
 

mm/damon/Kconfig config DAMON · line 15

Quoted 1 line

mm/damon/Kconfig +1 -0

+config DAMON_PRIMITIVES

I would rather name this base on virtual address space monitoring maybe like DAMON_VMA_OPTIMIZED_MONITORING or something similar. PRIMITIVES does not seem like a good name for this.

Quoted 18 lines

mm/damon/Kconfig +9 -0

+       bool "Monitoring primitives for virtual address spaces monitoring"
+       depends on DAMON && MMU && !IDLE_PAGE_TRACKING
+       select PAGE_EXTENSION if !64BIT
+       select PAGE_IDLE_FLAG
+       help
+         This builds the default data access monitoring primitives for DAMON.
+         The primitives support only virtual address spaces.  If this cannot
+         cover your use case, you can implement and use your own primitives.
+
 endmenu

mm/damon/Makefile +0 -0

index 4fd2edb4becf..2f3235a52e5e 100644
@@ -1,3 +1,4 @@
 # SPDX-License-Identifier: GPL-2.0
 

mm/damon/primitives.c

Quoted 7 lines

mm/damon/Makefile +1 -0

 obj-$(CONFIG_DAMON)            := core.o
+obj-$(CONFIG_DAMON_PRIMITIVES) += primitives.o

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

new file mode 100644
index 000000000000..9b603ac0077c

Same with the filename.

Quoted 3 lines

mm/damon/primitives.c new file +1 -0

@@ -0,0 +1,582 @@
+// SPDX-License-Identifier: GPL-2.0

[snip]

Quoted 23 lines

mm/damon/primitives.c new file +23 -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)

mm/damon/primitives.c line 493

Quoted 6 lines

mm/damon/primitives.c new file +6 -0

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

Don't you need mmu_notifier_clear_young() here?

I am still looking more into this patch

From: SeongJae Park <[email protected]>

Concurrent Idle Page Tracking users can interfere each other because the interface doesn't provide a central rule for synchronization between the users. Users could implement their own synchronization rule, but even in that case, applications developed by different users would not know how to synchronize with others. To help this situation, this commit introduces a centralized synchronization infrastructure of Idle Page Tracking.

In detail, this commit introduces a mutex lock for Idle Page Tracking, called 'page_idle_lock'. It is exposed to user space via a new bool sysfs file, '/sys/kernel/mm/page_idle/lock'. By writing to and reading from the file, users can hold/release and read status of the mutex. Writes to the Idle Page Tracking 'bitmap' file fails if the lock is not held, while reads of the file can be done regardless of the lock status.

Note that users could still interfere each other if they abuse this locking rule. Nevertheless, this change will let them notice the rule.

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

Quoted 18 lines · SeongJae Park

From: SeongJae Park <[email protected]>

Concurrent Idle Page Tracking users can interfere each other because the interface doesn't provide a central rule for synchronization between the users. Users could implement their own synchronization rule, but even in that case, applications developed by different users would not know how to synchronize with others. To help this situation, this commit introduces a centralized synchronization infrastructure of Idle Page Tracking.

In detail, this commit introduces a mutex lock for Idle Page Tracking, called 'page_idle_lock'. It is exposed to user space via a new bool sysfs file, '/sys/kernel/mm/page_idle/lock'. By writing to and reading from the file, users can hold/release and read status of the mutex. Writes to the Idle Page Tracking 'bitmap' file fails if the lock is not held, while reads of the file can be done regardless of the lock status.

Quoted 4 lines

Note that users could still interfere each other if they abuse this locking rule. Nevertheless, this change will let them notice the rule.

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

I don't think this is allowed. I mean returning to user space with held mutex and other processes can unlock it. I don't think mutex is what you need. Or more importantly is this really an issue?

From: SeongJae Park <[email protected]>

DAMON is designed to be used by kernel space code such as the memory management subsystems, and therefore it provides only kernel space API. That said, letting the user space control DAMON could provide some benefits to them. For example, it will allow user space to analyze their specific workloads and make their own special optimizations.

For such cases, this commit implements a simple DAMON application kernel module, namely 'damon-dbgfs', which merely wraps the DAMON api and exports those to the user space via the debugfs.

'damon-dbgfs' exports three files, ``attrs``, ``target_ids``, and ``monitor_on`` under its debugfs directory, ``<debugfs>/damon/``.

Attributes
----------

Users can read and write the ``sampling interval``, ``aggregation interval``, ``regions update interval``, and min/max number of monitoring target regions by reading from and writing to the ``attrs`` file. For example, below commands set those values to 5 ms, 100 ms, 1,000 ms, 10, 1000 and check it again::

    # cd <debugfs>/damon
    # echo 5000 100000 1000000 10 1000 > attrs
    # cat attrs
    5000 100000 1000000 10 1000

Target IDs
----------

Some types of address spaces supports multiple monitoring target. For example, the virtual memory address spaces monitoring can have multiple processes as the monitoring targets. Users can set the targets by writing relevant id values of the targets to, and get the ids of the current targets by reading from the ``target_ids`` file. In case of the virtual address spaces monitoring, the values should be pids of the monitoring target processes. For example, below commands set processes having pids 42 and 4242 as the monitoring targets and check it again::

    # cd <debugfs>/damon
    # echo 42 4242 > target_ids
    # cat target_ids
    42 4242

Note that setting the target ids doesn't start the monitoring.

Turning On/Off
--------------

Setting the files as described above doesn't incur effect unless you explicitly start the monitoring. You can start, stop, and check the current status of the monitoring by writing to and reading from the ``monitor_on`` file. Writing ``on`` to the file starts the monitoring of the targets with the attributes. Writing ``off`` to the file stops those. DAMON also stops if every targets are invalidated (in case of the virtual memory monitoring, target processes are invalidated when terminated). Below example commands turn on, off, and check the status of DAMON::

    # cd <debugfs>/damon
    # echo on > monitor_on
    # echo off > monitor_on
    # cat monitor_on
    off

Please note that you cannot write to the above-mentioned debugfs files while the monitoring is turned on. If you write to the files while DAMON is running, an error code such as ``-EBUSY`` will be returned.

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

Reviewed-by Leonard Foerster <[email protected]>

---
 include/linux/damon.h |   2 +
 mm/damon/Kconfig      |   9 +
 mm/damon/Makefile     |   1 +
 mm/damon/core.c       |  48 +++++
 mm/damon/dbgfs.c      | 428 ++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 488 insertions(+)
 create mode 100644 mm/damon/dbgfs.c

include/linux/damon.h +2 -0

index 70cc4b54212e..d675ea908a02 100644
@@ -226,6 +226,8 @@ 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(void);
+void damon_destroy_ctx(struct damon_ctx *ctx);
 int damon_set_targets(struct damon_ctx *ctx,
                unsigned long *ids, ssize_t nr_ids);
 int damon_set_attrs(struct damon_ctx *ctx, unsigned long sample_int,

mm/damon/Kconfig +9 -0

index 63b9c905b548..e38f95d28f74 100644
@@ -22,4 +22,13 @@ config DAMON_PRIMITIVES
          The primitives support only virtual address spaces.  If this cannot
          cover your use case, you can implement and use your own primitives.
 
+config DAMON_DBGFS
+       bool "DAMON debugfs interface"
+       depends on DAMON_PRIMITIVES && DEBUG_FS
+       help
+         This builds the debugfs interface for DAMON.  The user space admins
+         can use the interface for arbitrary data access monitoring.
+
+         If unsure, say N.
+
 endmenu

mm/damon/Makefile +1 -0

index 2f3235a52e5e..2295deb2fe0e 100644
@@ -2,3 +2,4 @@
 
 obj-$(CONFIG_DAMON)            := core.o
 obj-$(CONFIG_DAMON_PRIMITIVES) += primitives.o
+obj-$(CONFIG_DAMON_DBGFS)      += dbgfs.o

mm/damon/core.c +35 -0

index d7957d8ff530..47baf859d7d9 100644
@@ -135,6 +135,40 @@ unsigned int damon_nr_regions(struct damon_target *t)
        return nr_regions;
 }
 
+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;
+       ctx->min_nr_regions = 10;
+       ctx->max_nr_regions = 1000;
+
+       ktime_get_coarse_ts64(&ctx->last_aggregation);
+       ctx->last_regions_update = ctx->last_aggregation;
+
+       mutex_init(&ctx->kdamond_lock);
+
+       INIT_LIST_HEAD(&ctx->targets_list);
+
+       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);
+}
+
 /**
  * damon_set_targets() - Set monitoring targets.
  * @ctx:       monitoring context

@@ -204,6 +238,20 @@ int damon_set_attrs(struct damon_ctx *ctx, unsigned long sample_int,
        return 0;
 }
 
+/**

mm/damon/core.c +3 -0

+       return nr_ctxs;
+}
+
 /* Returns the size upper limit for each monitoring region */
 static unsigned long damon_region_sz_limit(struct damon_ctx *ctx)
 {

mm/damon/dbgfs.c new file +204 -0

new file mode 100644
index 000000000000..6316d4cae2a4
@@ -0,0 +1,428 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * DAMON Debugfs Interface
+ *
+ * Author: SeongJae Park <[email protected]>
+ */
+
+#define pr_fmt(fmt) "damon-dbgfs: " fmt
+
+#include <linux/damon.h>
+#include <linux/debugfs.h>
+#include <linux/file.h>
+#include <linux/mm.h>
+#include <linux/module.h>
+#include <linux/page_idle.h>
+#include <linux/slab.h>
+
+static struct damon_ctx **dbgfs_ctxs;
+static int dbgfs_nr_ctxs = 1;
+static int dbgfs_nr_terminated_ctxs;
+static struct dentry **dbgfs_dirs;
+static DEFINE_MUTEX(damon_dbgfs_lock);
+
+/*
+ * Returns non-empty string on success, negarive error code otherwise.
+ */
+static char *user_input_str(const char __user *buf, size_t count, loff_t *ppos)
+{
+       char *kbuf;
+       ssize_t ret;
+
+       /* We do not accept continuous write */
+       if (*ppos)
+               return ERR_PTR(-EINVAL);
+
+       kbuf = kmalloc(count + 1, GFP_KERNEL);
+       if (!kbuf)
+               return ERR_PTR(-ENOMEM);
+
+       ret = simple_write_to_buffer(kbuf, count + 1, ppos, buf, count);
+       if (ret != count) {
+               kfree(kbuf);
+               return ERR_PTR(-EIO);
+       }
+       kbuf[ret] = '\0';
+
+       return kbuf;
+}
+
+static ssize_t dbgfs_attrs_read(struct file *file,
+               char __user *buf, size_t count, loff_t *ppos)
+{
+       struct damon_ctx *ctx = file->private_data;
+       char kbuf[128];
+       int ret;
+
+       mutex_lock(&ctx->kdamond_lock);
+       ret = scnprintf(kbuf, ARRAY_SIZE(kbuf), "%lu %lu %lu %lu %lu\n",
+                       ctx->sample_interval, ctx->aggr_interval,
+                       ctx->regions_update_interval, ctx->min_nr_regions,
+                       ctx->max_nr_regions);
+       mutex_unlock(&ctx->kdamond_lock);
+
+       return simple_read_from_buffer(buf, count, ppos, kbuf, ret);
+}
+
+static ssize_t dbgfs_attrs_write(struct file *file,
+               const char __user *buf, size_t count, loff_t *ppos)
+{
+       struct damon_ctx *ctx = file->private_data;
+       unsigned long s, a, r, minr, maxr;
+       char *kbuf;
+       ssize_t ret = count;
+       int err;
+
+       kbuf = user_input_str(buf, count, ppos);
+       if (IS_ERR(kbuf))
+               return PTR_ERR(kbuf);
+
+       if (sscanf(kbuf, "%lu %lu %lu %lu %lu",
+                               &s, &a, &r, &minr, &maxr) != 5) {
+               ret = -EINVAL;
+               goto out;
+       }
+
+       mutex_lock(&ctx->kdamond_lock);
+       if (ctx->kdamond) {
+               ret = -EBUSY;
+               goto unlock_out;
+       }
+
+       err = damon_set_attrs(ctx, s, a, r, minr, maxr);
+       if (err)
+               ret = err;
+unlock_out:
+       mutex_unlock(&ctx->kdamond_lock);
+out:
+       kfree(kbuf);
+       return ret;
+}
+
+#define targetid_is_pid(ctx)   \
+       (ctx->primitive.target_valid == damon_va_target_valid)
+
+static ssize_t sprint_target_ids(struct damon_ctx *ctx, char *buf, ssize_t len)
+{
+       struct damon_target *t;
+       unsigned long id;
+       int written = 0;
+       int rc;
+
+       damon_for_each_target(t, ctx) {
+               id = t->id;
+               if (targetid_is_pid(ctx))
+                       /* Show pid numbers to debugfs users */
+                       id = (unsigned long)pid_vnr((struct pid *)id);
+
+               rc = scnprintf(&buf[written], len - written, "%lu ", id);
+               if (!rc)
+                       return -ENOMEM;
+               written += rc;
+       }
+       if (written)
+               written -= 1;
+       written += scnprintf(&buf[written], len - written, "\n");
+       return written;
+}
+
+static ssize_t dbgfs_target_ids_read(struct file *file,
+               char __user *buf, size_t count, loff_t *ppos)
+{
+       struct damon_ctx *ctx = file->private_data;
+       ssize_t len;
+       char ids_buf[320];
+
+       mutex_lock(&ctx->kdamond_lock);
+       len = sprint_target_ids(ctx, ids_buf, 320);
+       mutex_unlock(&ctx->kdamond_lock);
+       if (len < 0)
+               return len;
+
+       return simple_read_from_buffer(buf, count, ppos, ids_buf, len);
+}
+
+/*
+ * Converts a string into an array of unsigned long integers
+ *
+ * Returns an array of unsigned long integers if the conversion success, or
+ * NULL otherwise.
+ */
+static unsigned long *str_to_target_ids(const char *str, ssize_t len,
+                                       ssize_t *nr_ids)
+{
+       unsigned long *ids;
+       const int max_nr_ids = 32;
+       unsigned long id;
+       int pos = 0, parsed, ret;
+
+       *nr_ids = 0;
+       ids = kmalloc_array(max_nr_ids, sizeof(id), GFP_KERNEL);
+       if (!ids)
+               return NULL;
+       while (*nr_ids < max_nr_ids && pos < len) {
+               ret = sscanf(&str[pos], "%lu%n", &id, &parsed);
+               pos += parsed;
+               if (ret != 1)
+                       break;
+               ids[*nr_ids] = id;
+               *nr_ids += 1;
+       }
+
+       return ids;
+}
+
+/* Returns pid for the given pidfd if it's valid, or NULL otherwise. */
+static struct pid *damon_get_pidfd_pid(unsigned int pidfd)
+{
+       struct fd f;
+       struct pid *pid;
+
+       f = fdget(pidfd);
+       if (!f.file)
+               return NULL;
+
+       pid = pidfd_pid(f.file);
+       if (!IS_ERR(pid))
+               get_pid(pid);
+       else
+               pid = NULL;
+
+       fdput(f);
+       return pid;
+}
+
+static ssize_t dbgfs_target_ids_write(struct file *file,
+               const char __user *buf, size_t count, loff_t *ppos)
+{
+       struct damon_ctx *ctx = file->private_data;
+       char *kbuf, *nrs;
+       bool received_pidfds = false;
+       unsigned long *targets;
+       ssize_t nr_targets;
+       ssize_t ret = count;
+       int i;