Introduce Data Access MONitor (DAMON)

From: SeongJae Park <[email protected]>

This commit introduces a kernel module named DAMON. Note that this commit is implementing only the stub for the module load/unload, basic data structures, and simple manipulation functions of the structures to keep the size of commit small. The core mechanisms of DAMON will be implemented one by one by following commits.

Brief Introduction
==================

Memory management decisions can be improved if finer data access information is available. However, because such finer information usually comes with higher overhead, most systems including Linux forgives the potential improvement and rely on only coarse information or some light-weight heuristics. The pseudo-LRU and the aggressive THP promotions are such examples.

A number of experimental data access pattern awared memory management optimizations say the sacrifices are huge. However, none of those has successfully adopted to Linux kernel mainly due to the absence of a scalable and efficient data access monitoring mechanism.

DAMON is a data access monitoring solution for the problem. It is 1) accurate enough for the DRAM level memory management, 2) light-weight enough to be applied online, and 3) keeps predefined upper-bound overhead regardless of the size of target workloads (thus scalable).

DAMON is implemented as a standalone kernel module and provides several simple interfaces. Owing to that, though it has mainly designed for the kernel's memory management mechanisms, it can be also used for a wide range of user space programs and people.

Frequently Asked Questions
==========================

Q: Why not integrated with perf?
A: From the perspective of perf like profilers, DAMON can be thought of as a data source in kernel, like tracepoints, pressure stall information (psi), or idle page tracking. Thus, it can be easily integrated with those. However, this patchset doesn't provide a fancy perf integration because current step of DAMON development is focused on its core logic only. That said, DAMON already provides two interfaces for user space programs, which based on debugfs and tracepoint, respectively. Using the tracepoint interface, you can use DAMON with perf. This patchset also provides the debugfs interface based user space tool for DAMON. It can be used to record, visualize, and analyze data access pattern of target processes in a convenient way.

Q: Why a new module, instead of extending perf or other tools?
A: First, DAMON aims to be used by other programs including the kernel. Therefore, having dependency to specific tools like perf is not desirable. Second, because it need to be lightweight as much as possible so that it can be used online, any unnecessary overhead such as kernel - user space context switching cost should be avoided. These are the two most biggest reasons why DAMON is implemented in the kernel space. The idle page tracking subsystem would be the kernel module that most seems similar to DAMON. However, it's own interface is not compatible with DAMON. Also, the internal implementation of it has no common part to be reused by DAMON.

Q: Can 'perf mem' provide the data required for DAMON?
A: On the systems supporting 'perf mem', yes. DAMON is using the PTE Accessed bits in low level. Other H/W or S/W features that can be used for the purpose could be used. However, as explained with above question, DAMON need to be implemented in the kernel space.

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

---
 mm/Kconfig  |  12 +++
 mm/Makefile |   1 +
 mm/damon.c  | 224 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 237 insertions(+)
 create mode 100644 mm/damon.c

mm/Kconfig +0 -0

index ab80933be65f..387d469f40ec 100644

mm/Kconfig +8 -0

+	help
+	  Provides data access monitoring.
+
+	  DAMON is a kernel module that allows users to monitor the actual
+	  memory access pattern of specific user-space processes.  It aims to
+	  be 1) accurate enough to be useful for performance-centric domains,
+	  and 2) sufficiently light-weight so that it can be applied online.
+
 endmenu

mm/Makefile +1 -0

index 1937cc251883..2911b3832c90 100644
@@ -108,3 +108,4 @@ obj-$(CONFIG_ZONE_DEVICE) += memremap.o
 obj-$(CONFIG_HMM_MIRROR) += hmm.o
 obj-$(CONFIG_MEMFD_CREATE) += memfd.o
 obj-$(CONFIG_MAPPING_DIRTY_HELPERS) += mapping_dirty_helpers.o
+obj-$(CONFIG_DAMON) += damon.o

mm/damon.c new file +61 -0

new file mode 100644
index 000000000000..aafdca35b7b8
@@ -0,0 +1,224 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * Data Access Monitor
+ *
+ * Copyright 2019 Amazon.com, Inc. or its affiliates.  All rights reserved.
+ *
+ * Author: SeongJae Park <[email protected]>
+ */
+
+#define pr_fmt(fmt) "damon: " fmt
+
+#include <linux/mm.h>
+#include <linux/module.h>
+#include <linux/random.h>
+#include <linux/slab.h>
+
+#define damon_get_task_struct(t) \
+	(get_pid_task(find_vpid(t->pid), PIDTYPE_PID))
+
+#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_task(ctx, t) \
+	list_for_each_entry(t, &(ctx)->tasks_list, list)
+
+#define damon_for_each_task_safe(ctx, t, next) \
+	list_for_each_entry_safe(t, next, &(ctx)->tasks_list, list)
+
+/* Represents a monitoring target region on the virtual address space */
+struct damon_region {
+	unsigned long vm_start;
+	unsigned long vm_end;
+	unsigned long sampling_addr;
+	unsigned int nr_accesses;
+	struct list_head list;
+};
+
+/* Represents a monitoring target task */
+struct damon_task {
+	unsigned long pid;
+	struct list_head regions_list;
+	struct list_head list;
+};
+
+struct damon_ctx {
+	struct rnd_state rndseed;
+
+	struct list_head tasks_list;	/* 'damon_task' objects */
+};
+
+/* Get a random number in [l, r) */
+#define damon_rand(ctx, l, r) (l + prandom_u32_state(&ctx->rndseed) % (r - l))

mm/damon.c new file +12 -0

+ */
+static void damon_free_region(struct damon_region *r)
+{
+	kfree(r);
+}
+
+static void damon_destroy_region(struct damon_region *r)
+{
+	damon_del_region(r);
+	damon_free_region(r);
+}
+

mm/damon.c new file +16 -0

+{
+	list_add_tail(&t->list, &ctx->tasks_list);
+}
+
+static void damon_del_task(struct damon_task *t)
+{
+	list_del(&t->list);
+}
+
+static void damon_free_task(struct damon_task *t)
+{
+	struct damon_region *r, *next;
+
+	damon_for_each_region_safe(r, next, t)
+		damon_free_region(r);
+	kfree(t);

mm/damon.c new file +15 -0

+
+	return 0;
+}
+
+static void __exit damon_exit(void)
+{
+	pr_info("exit\n");
+}
+
+module_init(damon_init);
+module_exit(damon_exit);
+
+MODULE_LICENSE("GPL");
+MODULE_AUTHOR("SeongJae Park <[email protected]>");
+MODULE_DESCRIPTION("DAMON: Data Access MONitor");

Apologies if anyone gets these twice. I had an email server throttling issue yesterday.

Quoted 7 lines · On Mon, 24 Feb 2020 13:30:34 +0100 SeongJae Park <[email protected]> wrote:

From: SeongJae Park <[email protected]>

This commit introduces a kernel module named DAMON. Note that this commit is implementing only the stub for the module load/unload, basic data structures, and simple manipulation functions of the structures to keep the size of commit small. The core mechanisms of DAMON will be implemented one by one by following commits.

Interesting piece of work. I'm reviewing this partly as an exercise in understanding it, but I'll point out minor stuff on the basis I might as well whilst I'm here. ;) Note I review bottom up so some comments won't make much sense read from the top.

Quoted 4 lines

Brief Introduction
==================

I'd keep this level of intro for the cover letter / docs. It's not particularly useful in commit message it git.

Quoted 2 lines

mm/Kconfig config ARCH_HAS_HUGEPD · line 745

Quoted 5 lines

mm/Kconfig +4 -0

+config DAMON
+	tristate "Data Access Monitor"
+	depends on MMU
+	default n

No need to specify a default of n.

Quoted 10 lines

mm/Kconfig +8 -0

+	help
+	  Provides data access monitoring.
+
+	  DAMON is a kernel module that allows users to monitor the actual
+	  memory access pattern of specific user-space processes.  It aims to
+	  be 1) accurate enough to be useful for performance-centric domains,
+	  and 2) sufficiently light-weight so that it can be applied online.
+
 endmenu

Quoted 5 lines

+/*
+ * Construct a damon_region struct
+ *
+ * Returns the pointer to the new struct if success, or NULL otherwise
+ */

mm/damon.c line 71

Quoted 4 lines

mm/damon.c new file +4 -0

+static struct damon_region *damon_new_region(struct damon_ctx *ctx,
+				unsigned long vm_start, unsigned long vm_end)
+{
+	struct damon_region *ret;

I'd give this a different variable name. Expectation in kernel is often that ret is simply an magic handle to be passed on. Don't normally expect to set elements of it. I'd go long hand and call it region.

Review

Quoted 3 lines

(quoted diff) +2 -0

+
+	ret = kmalloc(sizeof(struct damon_region), GFP_KERNEL);

sizeof(*ret)

Review

Quoted 3 lines

(quoted diff) +2 -0

+	if (!ret)
+		return NULL;

blank line.

mm/damon.c line 86

Quoted 12 lines

mm/damon.c new file +11 -0

+	ret->vm_start = vm_start;
+	ret->vm_end = vm_end;
+	ret->nr_accesses = 0;
+	ret->sampling_addr = damon_rand(ctx, vm_start, vm_end);
+	INIT_LIST_HEAD(&ret->list);
+
+	return ret;
+}
+
+/*
+ * Add a region between two other regions

Interestingly even the list.h comments for __list_add call this
function "insert". No idea why it isn't simply called that..

Perhaps damon_insert_region would be clearer and avoid need for comment?

mm/damon.c line 95

Quoted 10 lines

+ */

mm/damon.c new file +8 -0

+static inline void damon_add_region(struct damon_region *r,
+		struct damon_region *prev, struct damon_region *next)
+{
+	__list_add(&r->list, &prev->list, &next->list);
+}
+
+/*
+ * Append a region to a task's list of regions

I'd argue the naming is sufficient that the comment adds little.

mm/damon.c line 103

Quoted 9 lines

+ */

mm/damon.c new file +7 -0

+static void damon_add_region_tail(struct damon_region *r, struct damon_task *t)
+{
+	list_add_tail(&r->list, &t->regions_list);
+}
+
+/*
+ * Delete a region from its list

The list is an implementation detail. I'd not mention that in the comments.

mm/damon.c line 111

Quoted 9 lines

+ */

mm/damon.c new file +7 -0

+static void damon_del_region(struct damon_region *r)
+{
+	list_del(&r->list);
+}
+
+/*
+ * De-allocate a region

Obvious comment - seem rot risk note below.

Quoted 18 lines

+ */

mm/damon.c new file +16 -0

+static void damon_free_region(struct damon_region *r)
+{
+	kfree(r);
+}
+
+static void damon_destroy_region(struct damon_region *r)
+{
+	damon_del_region(r);
+	damon_free_region(r);
+}
+
+/*
+ * Construct a damon_task struct
+ *
+ * Returns the pointer to the new struct if success, or NULL otherwise
+ */

mm/damon.c line 133

Quoted 5 lines

mm/damon.c new file +5 -0

+static struct damon_task *damon_new_task(unsigned long pid)
+{
+	struct damon_task *t;
+
+	t = kmalloc(sizeof(struct damon_task), GFP_KERNEL);

sizeof(*t) is probably less error prone if this code is maintained in the long run.

Review

Quoted 3 lines

(quoted diff) +2 -0

+	if (!t)
+		return NULL;

blank line.

Quoted 4 lines

mm/damon.c new file +3 -0

+	t->pid = pid;
+	INIT_LIST_HEAD(&t->regions_list);
+

mm/damon.c line 148

Quoted 10 lines

mm/damon.c new file +10 -0

+	return t;
+}
+
+/* Returns n-th damon_region of the given task */
+struct damon_region *damon_nth_region_of(struct damon_task *t, unsigned int n)
+{
+	struct damon_region *r;
+	unsigned int i;
+
+	i = 0;

	unsigned int i = 0;

mm/damon.c line 152

Quoted 5 lines

mm/damon.c new file +4 -0

+	damon_for_each_region(r, t) {
+		if (i++ == n)
+			return r;
+	}

blank line helps readability a little.

mm/damon.c line 156

Quoted 5 lines

mm/damon.c new file +4 -0

+	return NULL;
+}
+
+static void damon_add_task_tail(struct damon_ctx *ctx, struct damon_task *t)

I'm curious, do we care that it's on the tail? If not I'd look on that as an implementation detail and just call this

damon_add_task()

Quoted 21 lines

mm/damon.c new file +20 -0

+{
+	list_add_tail(&t->list, &ctx->tasks_list);
+}
+
+static void damon_del_task(struct damon_task *t)
+{
+	list_del(&t->list);
+}
+
+static void damon_free_task(struct damon_task *t)
+{
+	struct damon_region *r, *next;
+
+	damon_for_each_region_safe(r, next, t)
+		damon_free_region(r);
+	kfree(t);
+}
+
+static void damon_destroy_task(struct damon_task *t)
+{

mm/damon.c line 182

Quoted 6 lines

mm/damon.c new file +6 -0

+	damon_del_task(t);
+	damon_free_task(t);
+}
+
+/*
+ * Returns number of monitoring target tasks

As below, kind of obvious so just room for rot.

Quoted 10 lines

+ */

mm/damon.c new file +8 -0

+static unsigned int nr_damon_tasks(struct damon_ctx *ctx)
+{
+	struct damon_task *t;
+	unsigned int ret = 0;
+
+	damon_for_each_task(ctx, t)
+		ret++;
+	return ret;

mm/damon.c line 195

Quoted 4 lines

mm/damon.c new file +4 -0

+}
+
+/*
+ * Returns the number of target regions for a given target task

Always a trade off between useful comments and possibility of docs rotting. I'd drop this comment certainly.
The function name is self explanatory.

mm/damon.c line 203

Quoted 9 lines

+ */

mm/damon.c new file +7 -0

+static unsigned int nr_damon_regions(struct damon_task *t)
+{
+	struct damon_region *r;
+	unsigned int ret = 0;
+
+	damon_for_each_region(r, t)
+		ret++;

Blank line here would help readability a tiny bit. Same in other places where we have something followed by a nice simple return statement.

mm/damon.c line 209

Quoted 7 lines

mm/damon.c new file +6 -0

+	return ret;
+}
+
+static int __init damon_init(void)
+{
+	pr_info("init\n");

Drop these. They are just noise.

Quoted 16 lines

mm/damon.c new file +15 -0

+
+	return 0;
+}
+
+static void __exit damon_exit(void)
+{
+	pr_info("exit\n");
+}
+
+module_init(damon_init);
+module_exit(damon_exit);
+
+MODULE_LICENSE("GPL");
+MODULE_AUTHOR("SeongJae Park <[email protected]>");
+MODULE_DESCRIPTION("DAMON: Data Access MONitor");

From: SeongJae Park <[email protected]>

This commit implements DAMON's basic access check and region based sampling mechanisms. This change would seems make no sense, mainly because it is only a part of the DAMON's logics. Following two commits will make more sense.

This commit also exports lookup_page_ext() to GPL modules because DAMON uses the function but also supports the module build.

Basic Access Check
------------------

DAMON basically reports what pages are how frequently accessed. Note that the frequency is not an absolute number of accesses, but a relative frequency among the pages of the target workloads.

Users can control the resolution of the reports by setting two time intervals, ``sampling interval`` and ``aggregation interval``. In detail, DAMON checks access to each page per ``sampling interval``, aggregates the results (counts the number of the accesses to each page), and reports the aggregated results per ``aggregation interval``. For the access check of each page, DAMON uses the Accessed bits of PTEs.

This is thus similar to common periodic access checks based access tracking mechanisms, which overhead is increasing as the size of the target process grows.

Region Based Sampling
---------------------

To avoid the unbounded increase of the overhead, DAMON groups a number of adjacent pages that assumed to have same access frequencies into a region. As long as the assumption (pages in a region have 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 and clears its Accessed bit. After one more ``sampling interval``, DAMON reads the Accessed bit of the page and increases the access frequency of the region if the bit has set meanwhile. Therefore, the monitoring overhead is controllable by setting the number of regions.

Nonetheless, this scheme cannot preserve the quality of the output if the assumption is not kept. Following commit will introduce how we can make the guarantee with best effort.

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

---
 mm/damon.c    | 509 ++++++++++++++++++++++++++++++++++++++++++++++++++
 mm/page_ext.c |   1 +
 2 files changed, 510 insertions(+)

mm/damon.c +22 -0

index aafdca35b7b8..6bdeb84d89af 100644
@@ -9,9 +9,14 @@
 
 #define pr_fmt(fmt) "damon: " fmt
 
+#include <linux/delay.h>
+#include <linux/kthread.h>
 #include <linux/mm.h>
 #include <linux/module.h>
+#include <linux/page_idle.h>
 #include <linux/random.h>
+#include <linux/sched/mm.h>
+#include <linux/sched/task.h>
 #include <linux/slab.h>
 
 #define damon_get_task_struct(t) \

@@ -51,7 +56,24 @@ struct damon_task {
 	struct list_head list;
 };
 
+/*
+ * 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 each 'aggr_interval' time.
+ *
+ * All time intervals are in micro-seconds.
+ */
 struct damon_ctx {
+	unsigned long sample_interval;
+	unsigned long aggr_interval;
+	unsigned long min_nr_regions;
+
+	struct timespec64 last_aggregation;
+
+	struct task_struct *kdamond;
+	bool kdamond_stop;
+	spinlock_t kdamond_lock;
+
 	struct rnd_state rndseed;
 
 	struct list_head tasks_list;	/* 'damon_task' objects */

mm/damon.c +37 -0

+ *
+ * Returns the mm_struct of the task on success, NULL on failure
+ */
+static struct mm_struct *damon_get_mm(struct damon_task *t)
+{
+	struct task_struct *task;
+	struct mm_struct *mm;
+
+	task = damon_get_task_struct(t);
+	if (!task)
+		return NULL;
+
+	mm = get_task_mm(task);
+	put_task_struct(task);
+	return mm;
+}
+
+/*
+ * Size-evenly split a region into 'nr_pieces' small regions
+ *
+ * Returns 0 on success, or negative error code otherwise.
+ */
+static int damon_split_region_evenly(struct damon_ctx *ctx,
+		struct damon_region *r, unsigned int nr_pieces)
+{
+	unsigned long sz_orig, sz_piece, orig_end;
+	struct damon_region *piece = NULL, *next;
+	unsigned long start;
+
+	if (!r || !nr_pieces)
+		return -EINVAL;
+
+	orig_end = r->vm_end;
+	sz_orig = r->vm_end - r->vm_start;
+	sz_piece = sz_orig / nr_pieces;
+
+	if (!sz_piece)

mm/damon.c +97 -0

+	return 0;
+}
+
+struct region {
+	unsigned long start;
+	unsigned long end;
+};
+
+static unsigned long sz_region(struct region *r)
+{
+	return r->end - r->start;
+}
+
+static void swap_regions(struct region *r1, struct region *r2)
+{
+	struct region tmp;
+
+	tmp = *r1;
+	*r1 = *r2;
+	*r2 = tmp;
+}
+
+/*
+ * Find the three regions in an address space
+ *
+ * vma		the head vma of the target address space
+ * regions	an array of three 'struct region's that results will be saved
+ *
+ * This function receives an address space and finds three regions in it which
+ * separated by the two biggest unmapped regions in the space.  Please refer to
+ * below comments of 'damon_init_regions_of()' function to know why this is
+ * necessary.
+ *
+ * Returns 0 if success, or negative error code otherwise.
+ */
+static int damon_three_regions_in_vmas(struct vm_area_struct *vma,
+		struct region regions[3])
+{
+	struct region gap = {0,}, first_gap = {0,}, second_gap = {0,};
+	struct vm_area_struct *last_vma = NULL;
+	unsigned long start = 0;
+
+	/* Find two biggest gaps so that first_gap > second_gap > others */
+	for (; vma; vma = vma->vm_next) {
+		if (!last_vma) {
+			start = vma->vm_start;
+			last_vma = vma;
+			continue;
+		}
+		gap.start = last_vma->vm_end;
+		gap.end = vma->vm_start;
+		if (sz_region(&gap) > sz_region(&second_gap)) {
+			swap_regions(&gap, &second_gap);
+			if (sz_region(&second_gap) > sz_region(&first_gap))
+				swap_regions(&second_gap, &first_gap);
+		}
+		last_vma = vma;
+	}
+
+	if (!sz_region(&second_gap) || !sz_region(&first_gap))
+		return -EINVAL;
+
+	/* Sort the two biggest gaps by address */
+	if (first_gap.start > second_gap.start)
+		swap_regions(&first_gap, &second_gap);
+
+	/* Store the result */
+	regions[0].start = start;
+	regions[0].end = first_gap.start;
+	regions[1].start = first_gap.end;
+	regions[1].end = second_gap.start;
+	regions[2].start = second_gap.end;
+	regions[2].end = last_vma->vm_end;
+
+	return 0;
+}
+
+/*
+ * Get the three regions in the given task
+ *
+ * Returns 0 on success, negative error code otherwise.
+ */
+static int damon_three_regions_of(struct damon_task *t,
+				struct region regions[3])
+{
+	struct mm_struct *mm;
+	int ret;
+
+	mm = damon_get_mm(t);
+	if (!mm)
+		return -EINVAL;
+
+	down_read(&mm->mmap_sem);
+	ret = damon_three_regions_in_vmas(mm->mmap, regions);
+	up_read(&mm->mmap_sem);
+
+	mmput(mm);

mm/damon.c +56 -0

+ * regions is wasteful.  That said, because we can deal with small noises,
+ * tracking every mapping is not strictly required but could even incur a high
+ * overhead if the mapping frequently changes or the number of mappings is
+ * high.  Nonetheless, this may seems very weird.  DAMON's dynamic regions
+ * adjustment mechanism, which will be implemented with following commit will
+ * make this more sense.
+ *
+ * For the reason, we convert the complex mappings to three distinct regions
+ * that cover every mapped areas of the address space.  Also the two gaps
+ * between the three regions are the two biggest unmapped areas in the given
+ * address space.  In detail, this function first identifies the start and the
+ * end of the mappings and the two biggest unmapped areas of the address space.
+ * Then, it constructs the three regions as below:
+ *
+ *     [mappings[0]->start, big_two_unmapped_areas[0]->start)
+ *     [big_two_unmapped_areas[0]->end, big_two_unmapped_areas[1]->start)
+ *     [big_two_unmapped_areas[1]->end, mappings[nr_mappings - 1]->end)
+ *
+ * As usual memory map of processes is as below, the gap between the heap and
+ * the uppermost mmap()-ed region, and the gap between the lowermost mmap()-ed
+ * region and the stack will be two biggest unmapped regions.  Because these
+ * gaps are exceptionally huge areas in usual address space, excluding these
+ * two biggest unmapped regions will be sufficient to make a trade-off.
+ *
+ *   <heap>
+ *   <BIG UNMAPPED REGION 1>
+ *   <uppermost mmap()-ed region>
+ *   (other mmap()-ed regions and small unmapped regions)
+ *   <lowermost mmap()-ed region>
+ *   <BIG UNMAPPED REGION 2>
+ *   <stack>
+ */
+static void damon_init_regions_of(struct damon_ctx *c, struct damon_task *t)
+{
+	struct damon_region *r;
+	struct region regions[3];
+	int i;
+
+	if (damon_three_regions_of(t, regions)) {
+		pr_err("Failed to get three regions of task %lu\n", t->pid);
+		return;
+	}
+
+	/* Set the initial three regions of the task */
+	for (i = 0; i < 3; i++) {
+		r = damon_new_region(c, regions[i].start, regions[i].end);
+		damon_add_region_tail(r, t);
+	}
+
+	/* Split the middle region into 'min_nr_regions - 2' regions */
+	r = damon_nth_region_of(t, 1);
+	if (damon_split_region_evenly(c, r, c->min_nr_regions - 2))
+		pr_warn("Init middle region failed to be split\n");
+}
+
+/* Initialize '->regions_list' of every task */

mm/damon.c +8 -0

+ *
+ * mm	'mm_struct' for the given virtual address space
+ * r	the region to be checked
+ */
+static void kdamond_check_access(struct damon_ctx *ctx,
+			struct mm_struct *mm, struct damon_region *r)
+{
+	pte_t *pte = NULL;

mm/damon.c +25 -0

+	else if (pmd && pmd_young(*pmd))
+		r->nr_accesses++;
+#endif	/* CONFIG_TRANSPARENT_HUGEPAGE */
+
+	spin_unlock(ptl);
+
+mkold:
+	/* mkold next target */
+	r->sampling_addr = damon_rand(ctx, r->vm_start, r->vm_end);
+
+	if (follow_pte_pmd(mm, r->sampling_addr, NULL, &pte, &pmd, &ptl))
+		return;
+
+	if (pte) {
+		if (pte_young(*pte)) {
+			clear_page_idle(pte_page(*pte));
+			set_page_young(pte_page(*pte));
+		}
+		*pte = pte_mkold(*pte);
+	}
+#ifdef CONFIG_TRANSPARENT_HUGEPAGE
+	else if (pmd) {
+		if (pmd_young(*pmd)) {
+			clear_page_idle(pmd_page(*pmd));
+			set_page_young(pmd_page(*pmd));

mm/damon.c +25 -0

+ *
+ * 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.
+ *
+ * Returns 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
+ */

mm/damon.c +14 -0

+{
+	struct damon_task *t;
+	struct damon_region *r;
+
+	damon_for_each_task(c, t) {
+		damon_for_each_region(r, t)
+			r->nr_accesses = 0;
+	}
+}
+
+/*
+ * Check whether current monitoring should be stopped
+ *
+ * If users asked to stop, need stop.  Even though no user has asked to stop,

mm/damon.c +13 -0

+	spin_lock(&ctx->kdamond_lock);
+	stop = ctx->kdamond_stop;
+	spin_unlock(&ctx->kdamond_lock);
+	if (stop)
+		return true;
+
+	damon_for_each_task(ctx, t) {
+		task = damon_get_task_struct(t);
+		if (task) {
+			put_task_struct(task);
+			return false;
+		}
+	}

mm/damon.c +10 -0

+	struct damon_task *t;
+	struct damon_region *r, *next;
+	struct mm_struct *mm;
+
+	pr_info("kdamond (%d) starts\n", ctx->kdamond->pid);
+	kdamond_init_regions(ctx);
+	while (!kdamond_need_stop(ctx)) {
+		damon_for_each_task(ctx, t) {
+			mm = damon_get_mm(t);
+			if (!mm)

mm/damon.c +6 -0

+	return 0;
+}
+
+/*
+ * Controller functions
+ */

mm/damon.c +36 -0

+			spin_lock(&ctx->kdamond_lock);
+			if (!ctx->kdamond)
+				goto success;
+			spin_unlock(&ctx->kdamond_lock);
+
+			usleep_range(ctx->sample_interval,
+					ctx->sample_interval * 2);
+		}
+	}
+
+	/* tried to turn on while turned on, or turn off while turned off */
+
+fail:
+	spin_unlock(&ctx->kdamond_lock);
+	return -EINVAL;
+
+success:
+	spin_unlock(&ctx->kdamond_lock);
+	return 0;
+}
+
+/*
+ * This function should not be called while the kdamond is running.
+ */
+static int damon_set_pids(struct damon_ctx *ctx,
+			unsigned long *pids, ssize_t nr_pids)
+{
+	ssize_t i;
+	struct damon_task *t, *next;
+
+	damon_for_each_task_safe(ctx, t, next)
+		damon_destroy_task(t);
+
+	for (i = 0; i < nr_pids; i++) {
+		t = damon_new_task(pids[i]);
+		if (!t) {

mm/damon.c +13 -0

+ * Set attributes for the monitoring
+ *
+ * sample_int		time interval between samplings
+ * aggr_int		time interval between aggregations
+ * min_nr_reg		minimal number of regions
+ *
+ * This function should not be called while the kdamond is running.
+ * Every time interval is in micro-seconds.
+ *
+ * Returns 0 on success, negative error code otherwise.
+ */
+static int damon_set_attrs(struct damon_ctx *ctx, unsigned long sample_int,
+		unsigned long aggr_int, unsigned long min_nr_reg)

mm/damon.c +3 -0

+	return 0;
+}
+
 static int __init damon_init(void)
 {
 	pr_info("init\n");

mm/page_ext.c +1 -0

index 4ade843ff588..71169b45bba9 100644
@@ -131,6 +131,7 @@ struct page_ext *lookup_page_ext(const struct page *page)
 					MAX_ORDER_NR_PAGES);
 	return get_entry(base, index);
 }
+EXPORT_SYMBOL_GPL(lookup_page_ext);
 
 static int __init alloc_node_page_ext(int nid)
 {

Quoted 7 lines · On Mon, 24 Feb 2020 13:30:35 +0100 SeongJae Park <[email protected]> wrote:

From: SeongJae Park <[email protected]>

This commit implements DAMON's basic access check and region based sampling mechanisms. This change would seems make no sense, mainly because it is only a part of the DAMON's logics. Following two commits will make more sense.

Quoted 2 lines

This commit also exports lookup_page_ext() to GPL modules because DAMON uses the function but also supports the module build.

Do that as a separate patch before this one. Makes it easy to spot.

Quoted 2 lines

Various things inline. In particularly can you make use of standard kthread_stop infrastructure rather than rolling your own?

Quoted 12 lines

---
 mm/damon.c    | 509 ++++++++++++++++++++++++++++++++++++++++++++++++++
 mm/page_ext.c |   1 +
 2 files changed, 510 insertions(+)

mm/damon.c +0 -0

index aafdca35b7b8..6bdeb84d89af 100644
@@ -9,9 +9,14 @@
 

Quoted 4 lines

+/*
+ * Get the mm_struct of the given task
+ *
+ * Callser should put the mm_struct after use, unless it is NULL.

Caller

Quoted 43 lines

+ *
+ * Returns the mm_struct of the task on success, NULL on failure
+ */

mm/damon.c +39 -0

+static struct mm_struct *damon_get_mm(struct damon_task *t)
+{
+	struct task_struct *task;
+	struct mm_struct *mm;
+
+	task = damon_get_task_struct(t);
+	if (!task)
+		return NULL;
+
+	mm = get_task_mm(task);
+	put_task_struct(task);
+	return mm;
+}
+
+/*
+ * Size-evenly split a region into 'nr_pieces' small regions
+ *
+ * Returns 0 on success, or negative error code otherwise.
+ */
+static int damon_split_region_evenly(struct damon_ctx *ctx,
+		struct damon_region *r, unsigned int nr_pieces)
+{
+	unsigned long sz_orig, sz_piece, orig_end;
+	struct damon_region *piece = NULL, *next;
+	unsigned long start;
+
+	if (!r || !nr_pieces)
+		return -EINVAL;
+
+	orig_end = r->vm_end;
+	sz_orig = r->vm_end - r->vm_start;
+	sz_piece = sz_orig / nr_pieces;
+
+	if (!sz_piece)
+		return -EINVAL;
+
+	r->vm_end = r->vm_start + sz_piece;
+	next = damon_next_region(r);
+	for (start = r->vm_end; start + sz_piece <= orig_end;

mm/damon.c static unsigned int nr_damon_regions(struct damon_task *t) · line 279

Quoted 5 lines

mm/damon.c +5 -0

+			start += sz_piece) {
+		piece = damon_new_region(ctx, start, start + sz_piece);
+		damon_add_region(piece, r, next);
+		r = piece;
+	}

I'd add a comment here. I think this next bit is to catch any rounding error holes, but I'm not 100% sure.

mm/damon.c static unsigned int nr_damon_regions(struct damon_task *t) · line 281

Quoted 3 lines

mm/damon.c +2 -0

+	if (piece)
+		piece->vm_end = orig_end;

blank line here.

Quoted 3 lines

mm/damon.c +2 -0

+	return 0;
+}

Quoted 7 lines

+/*
+ * Initialize the monitoring target regions for the given task
+ *
+ * t the given target task
+ *
+ * Because only a number of small portions of the entire address space
+ * is acutally mapped to the memory and accessed, monitoring the unmapped

actually

Quoted 2 lines

+/*
+ * Check whether the given region has accessed since the last check

Should also make clear that this sets us up for the next access check at a different memory address it the region.

Given the lack of connection between activities perhaps just split this into two functions that are always called next to each other.

Quoted 14 lines

+ *
+ * mm 'mm_struct' for the given virtual address space
+ * r the region to be checked
+ */

mm/damon.c +9 -0

+static void kdamond_check_access(struct damon_ctx *ctx,
+			struct mm_struct *mm, struct damon_region *r)
+{
+	pte_t *pte = NULL;
+	pmd_t *pmd = NULL;
+	spinlock_t *ptl;
+
+	if (follow_pte_pmd(mm, r->sampling_addr, NULL, &pte, &pmd, &ptl))
+		goto mkold;

mm/damon.c static unsigned int nr_damon_regions(struct damon_task *t) · line 472

Quoted 5 lines

mm/damon.c +5 -0

+
+	/* Read the page table access bit of the page */
+	if (pte && pte_young(*pte))
+		r->nr_accesses++;
+#ifdef CONFIG_TRANSPARENT_HUGEPAGE

Is it worth having this protection? Seems likely to have only a very small influence on performance and makes it a little harder to reason about the code.

Quoted 31 lines

mm/damon.c +30 -0

+	else if (pmd && pmd_young(*pmd))
+		r->nr_accesses++;
+#endif	/* CONFIG_TRANSPARENT_HUGEPAGE */
+
+	spin_unlock(ptl);
+
+mkold:
+	/* mkold next target */
+	r->sampling_addr = damon_rand(ctx, r->vm_start, r->vm_end);
+
+	if (follow_pte_pmd(mm, r->sampling_addr, NULL, &pte, &pmd, &ptl))
+		return;
+
+	if (pte) {
+		if (pte_young(*pte)) {
+			clear_page_idle(pte_page(*pte));
+			set_page_young(pte_page(*pte));
+		}
+		*pte = pte_mkold(*pte);
+	}
+#ifdef CONFIG_TRANSPARENT_HUGEPAGE
+	else if (pmd) {
+		if (pmd_young(*pmd)) {
+			clear_page_idle(pmd_page(*pmd));
+			set_page_young(pmd_page(*pmd));
+		}
+		*pmd = pmd_mkold(*pmd);
+	}
+#endif
+

mm/damon.c static unsigned int nr_damon_regions(struct damon_task *t) · line 507

Quoted 5 lines

mm/damon.c +5 -0

+	spin_unlock(ptl);
+}
+
+/*
+ * Check whether a time interval is elapsed

Another comment block that would be clearer if it was kernel-doc rather than nearly kernel-doc

Quoted 30 lines

+ *
+ * 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.
+ *
+ * Returns true if the time interval has passed, or false otherwise.
+ */

mm/damon.c +20 -0

+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);

mm/damon.c static unsigned int nr_damon_regions(struct damon_task *t) · line 542

Quoted 6 lines

mm/damon.c +6 -0

+}
+
+/*
+ * Reset the aggregated monitoring results
+ */
+static void kdamond_flush_aggregated(struct damon_ctx *c)

I wouldn't expect a reset function to be called flush.

Quoted 19 lines

mm/damon.c +18 -0

+{
+	struct damon_task *t;
+	struct damon_region *r;
+
+	damon_for_each_task(c, t) {
+		damon_for_each_region(r, t)
+			r->nr_accesses = 0;
+	}
+}
+
+/*
+ * Check whether current monitoring should be stopped
+ *
+ * If users asked to stop, need stop.  Even though no user has asked to stop,
+ * need stop if every target task has dead.
+ *
+ * Returns true if need to stop current monitoring.
+ */

mm/damon.c static unsigned int nr_damon_regions(struct damon_task *t) · line 566

Quoted 6 lines

mm/damon.c +6 -0

+static bool kdamond_need_stop(struct damon_ctx *ctx)
+{
+	struct damon_task *t;
+	struct task_struct *task;
+	bool stop;
+

As below comment asks, can you use kthread_should_stop?

Quoted 19 lines

mm/damon.c +18 -0

+	spin_lock(&ctx->kdamond_lock);
+	stop = ctx->kdamond_stop;
+	spin_unlock(&ctx->kdamond_lock);
+	if (stop)
+		return true;
+
+	damon_for_each_task(ctx, t) {
+		task = damon_get_task_struct(t);
+		if (task) {
+			put_task_struct(task);
+			return false;
+		}
+	}
+
+	return true;
+}
+
+/*

mm/damon.c static unsigned int nr_damon_regions(struct damon_task *t) · line 589

Quoted 5 lines

+ * The monitoring daemon that runs as a kernel thread
+ */

mm/damon.c +3 -0

+static int kdamond_fn(void *data)
+{
+	struct damon_ctx *ctx = (struct damon_ctx *)data;

Never any need to explicitly cast a void * to some other pointer type. (C spec)

	struct damon_ctx *ctx = data;

Quoted 14 lines

mm/damon.c +14 -0

+	struct damon_task *t;
+	struct damon_region *r, *next;
+	struct mm_struct *mm;
+
+	pr_info("kdamond (%d) starts\n", ctx->kdamond->pid);
+	kdamond_init_regions(ctx);
+	while (!kdamond_need_stop(ctx)) {
+		damon_for_each_task(ctx, t) {
+			mm = damon_get_mm(t);
+			if (!mm)
+				continue;
+			damon_for_each_region(r, t)
+				kdamond_check_access(ctx, mm, r);
+			mmput(mm);

mm/damon.c static unsigned int nr_damon_regions(struct damon_task *t) · line 609

Quoted 6 lines

mm/damon.c +6 -0

+		}
+
+		if (kdamond_aggregate_interval_passed(ctx))
+			kdamond_flush_aggregated(ctx);
+
+		usleep_range(ctx->sample_interval, ctx->sample_interval + 1);

Is there any purpose in using a range for such a narrow window?

mm/damon.c static unsigned int nr_damon_regions(struct damon_task *t) · line 615

Quoted 7 lines

mm/damon.c +6 -0

+	}
+	damon_for_each_task(ctx, t) {
+		damon_for_each_region_safe(r, next, t)
+			damon_destroy_region(r);
+	}
+	pr_info("kdamond (%d) finishes\n", ctx->kdamond->pid);

Feels like noise. I'd drop tis to pr_debug.

mm/damon.c static unsigned int nr_damon_regions(struct damon_task *t) · line 618

Quoted 4 lines

mm/damon.c +3 -0

+	spin_lock(&ctx->kdamond_lock);
+	ctx->kdamond = NULL;
+	spin_unlock(&ctx->kdamond_lock);

blank line.

Quoted 11 lines

mm/damon.c +10 -0

+	return 0;
+}
+
+/*
+ * Controller functions
+ */
+
+/*
+ * Start or stop the kdamond
+ *

mm/damon.c static unsigned int nr_damon_regions(struct damon_task *t) · line 634

Quoted 6 lines

+ * Returns 0 if success, negative error code otherwise.
+ */

mm/damon.c +4 -0

+static int damon_turn_kdamond(struct damon_ctx *ctx, bool on)
+{
+	spin_lock(&ctx->kdamond_lock);
+	ctx->kdamond_stop = !on;

Can't use the kthread_stop / kthread_should_stop approach?

mm/damon.c static unsigned int nr_damon_regions(struct damon_task *t) · line 639

Quoted 6 lines

mm/damon.c +5 -0

+	if (!ctx->kdamond && on) {
+		ctx->kdamond = kthread_run(kdamond_fn, ctx, "kdamond");
+		if (!ctx->kdamond)
+			goto fail;
+		goto success;

cleaner as
int ret = 0; above then

		if (!ctx->kdamond)
			ret = -EINVAL;
		goto unlock;

with

unlock:

	spin_unlock(&ctx->dmanond_lock);
	return ret;

mm/damon.c static unsigned int nr_damon_regions(struct damon_task *t) · line 643

Quoted 5 lines

mm/damon.c +4 -0

+	}
+	if (ctx->kdamond && !on) {
+		spin_unlock(&ctx->kdamond_lock);
+		while (true) {

An unbounded loop is probably a bad idea.

Quoted 42 lines

mm/damon.c +41 -0

+			spin_lock(&ctx->kdamond_lock);
+			if (!ctx->kdamond)
+				goto success;
+			spin_unlock(&ctx->kdamond_lock);
+
+			usleep_range(ctx->sample_interval,
+					ctx->sample_interval * 2);
+		}
+	}
+
+	/* tried to turn on while turned on, or turn off while turned off */
+
+fail:
+	spin_unlock(&ctx->kdamond_lock);
+	return -EINVAL;
+
+success:
+	spin_unlock(&ctx->kdamond_lock);
+	return 0;
+}
+
+/*
+ * This function should not be called while the kdamond is running.
+ */
+static int damon_set_pids(struct damon_ctx *ctx,
+			unsigned long *pids, ssize_t nr_pids)
+{
+	ssize_t i;
+	struct damon_task *t, *next;
+
+	damon_for_each_task_safe(ctx, t, next)
+		damon_destroy_task(t);
+
+	for (i = 0; i < nr_pids; i++) {
+		t = damon_new_task(pids[i]);
+		if (!t) {
+			pr_err("Failed to alloc damon_task\n");
+			return -ENOMEM;
+		}
+		damon_add_task_tail(ctx, t);
+	}

mm/damon.c static unsigned int nr_damon_regions(struct damon_task *t) · line 304

Quoted 5 lines

mm/damon.c +5 -0

+
+	return 0;
+}
+
+/*

This is kind of similar to kernel-doc formatting. Might as well just make it kernel-doc!

Quoted 18 lines

+ * Set attributes for the monitoring
+ *
+ * sample_int time interval between samplings
+ * aggr_int time interval between aggregations
+ * min_nr_reg minimal number of regions
+ *
+ * This function should not be called while the kdamond is running.
+ * Every time interval is in micro-seconds.
+ *
+ * Returns 0 on success, negative error code otherwise.
+ */

mm/damon.c +6 -0

+static int damon_set_attrs(struct damon_ctx *ctx, unsigned long sample_int,
+		unsigned long aggr_int, unsigned long min_nr_reg)
+{
+	if (min_nr_reg < 3) {
+		pr_err("min_nr_regions (%lu) should be bigger than 2\n",
+				min_nr_reg);

mm/damon.c static unsigned int nr_damon_regions(struct damon_task *t) · line 712

Quoted 6 lines

mm/damon.c +6 -0

+		return -EINVAL;
+	}
+
+	ctx->sample_interval = sample_int;
+	ctx->aggr_interval = aggr_int;
+	ctx->min_nr_regions = min_nr_reg;

blank line helps readability a tiny little bit.

Quoted 19 lines

mm/damon.c +3 -0

+	return 0;
+}
+
 static int __init damon_init(void)
 {
 	pr_info("init\n");

mm/page_ext.c +1 -0

index 4ade843ff588..71169b45bba9 100644
@@ -131,6 +131,7 @@ struct page_ext *lookup_page_ext(const struct page *page)
 					MAX_ORDER_NR_PAGES);
 	return get_entry(base, index);
 }
+EXPORT_SYMBOL_GPL(lookup_page_ext);
 
 static int __init alloc_node_page_ext(int nid)
 {

Added replies to your every comment in line below. I agree to your whole opinions, will apply those in next spin! :)

Quoted 8 lines

Quoted 2 lines

+/*
+ * Check whether the given region has accessed since the last check

Should also make clear that this sets us up for the next access check at a different memory address it the region.

Given the lack of connection between activities perhaps just split this into two functions that are always called next to each other.

Will make the description more clearer as suggested.

Also, I found that I'm not clearing *pte and *pmd before going 'mkold', thanks to this comment. Will fix it, either.

Quoted 14 lines

Quoted 14 lines

+ *
+ * mm 'mm_struct' for the given virtual address space
+ * r the region to be checked
+ */

mm/damon.c +9 -0

+static void kdamond_check_access(struct damon_ctx *ctx,
+			struct mm_struct *mm, struct damon_region *r)
+{
+	pte_t *pte = NULL;
+	pmd_t *pmd = NULL;
+	spinlock_t *ptl;
+
+	if (follow_pte_pmd(mm, r->sampling_addr, NULL, &pte, &pmd, &ptl))
+		goto mkold;

Quoted 8 lines

mm/damon.c static unsigned int nr_damon_regions(struct damon_task *t) · line 472

Quoted 5 lines

mm/damon.c +5 -0

+
+	/* Read the page table access bit of the page */
+	if (pte && pte_young(*pte))
+		r->nr_accesses++;
+#ifdef CONFIG_TRANSPARENT_HUGEPAGE  

Is it worth having this protection? Seems likely to have only a very small influence on performance and makes it a little harder to reason about the code.

It was necessary for addressing 'implicit declaration' problem of 'pmd_young()' and 'pmd_mkold()' for build of DAMON on several architectures including User Mode Linux.

Will modularize the code for better readability.

Quoted 3 lines

mm/damon.c static unsigned int nr_damon_regions(struct damon_task *t) · line 474

Quoted 3 lines

mm/damon.c +2 -0

+	else if (pmd && pmd_young(*pmd))
+		r->nr_accesses++;

Quoted 31 lines

Quoted 31 lines

mm/damon.c +31 -0

+#endif	/* CONFIG_TRANSPARENT_HUGEPAGE */
+
+	spin_unlock(ptl);
+
+mkold:
+	/* mkold next target */
+	r->sampling_addr = damon_rand(ctx, r->vm_start, r->vm_end);
+
+	if (follow_pte_pmd(mm, r->sampling_addr, NULL, &pte, &pmd, &ptl))
+		return;
+
+	if (pte) {
+		if (pte_young(*pte)) {
+			clear_page_idle(pte_page(*pte));
+			set_page_young(pte_page(*pte));
+		}
+		*pte = pte_mkold(*pte);
+	}
+#ifdef CONFIG_TRANSPARENT_HUGEPAGE
+	else if (pmd) {
+		if (pmd_young(*pmd)) {
+			clear_page_idle(pmd_page(*pmd));
+			set_page_young(pmd_page(*pmd));
+		}
+		*pmd = pmd_mkold(*pmd);
+	}
+#endif
+
+	spin_unlock(ptl);
+}
+

Quoted 3 lines · On Tue, 10 Mar 2020 12:52:33 +0100 SeongJae Park <[email protected]> wrote:

Added replies to your every comment in line below. I agree to your whole opinions, will apply those in next spin! :)

One additional question inline that came to mind. Using a single statistic to monitor huge page and normal page hits is going to give us problems I think.

Perhaps I'm missing something?

Quoted 41 lines

Quoted 8 lines

Quoted 2 lines

+/*
+ * Check whether the given region has accessed since the last check

Should also make clear that this sets us up for the next access check at a different memory address it the region.

Given the lack of connection between activities perhaps just split this into two functions that are always called next to each other.

Will make the description more clearer as suggested.

Also, I found that I'm not clearing *pte and *pmd before going 'mkold', thanks to this comment. Will fix it, either.

Quoted 14 lines

Quoted 14 lines

+ *
+ * mm 'mm_struct' for the given virtual address space
+ * r the region to be checked
+ */

mm/damon.c +9 -0

+static void kdamond_check_access(struct damon_ctx *ctx,
+			struct mm_struct *mm, struct damon_region *r)
+{
+	pte_t *pte = NULL;
+	pmd_t *pmd = NULL;
+	spinlock_t *ptl;
+
+	if (follow_pte_pmd(mm, r->sampling_addr, NULL, &pte, &pmd, &ptl))
+		goto mkold;

Quoted 8 lines

mm/damon.c static unsigned int nr_damon_regions(struct damon_task *t) · line 472

Quoted 5 lines

mm/damon.c +5 -0

+
+	/* Read the page table access bit of the page */
+	if (pte && pte_young(*pte))
+		r->nr_accesses++;
+#ifdef CONFIG_TRANSPARENT_HUGEPAGE  

Is it worth having this protection? Seems likely to have only a very small influence on performance and makes it a little harder to reason about the code.

It was necessary for addressing 'implicit declaration' problem of 'pmd_young()' and 'pmd_mkold()' for build of DAMON on several architectures including User Mode Linux.

Quoted 5 lines

Will modularize the code for better readability.

Quoted 3 lines

mm/damon.c static unsigned int nr_damon_regions(struct damon_task *t) · line 474

Quoted 3 lines

mm/damon.c +2 -0

+	else if (pmd && pmd_young(*pmd))
+		r->nr_accesses++;

So we increment a region count by one if we have an access in a huge page, or in a normal page.

If we get a region that has a mixture of the two, this seems likely to give a bad approximation.

Assume the region is accessed 'evenly' but each " 4k page" is only hit 10% of the time (where a hit is in one check period)

If our address in a page, then we'll hit 10% of the time, but if it is in a 2M huge page then we'll hit a much higher percentage of the time.
1 - (0.9^512) ~= 1

Should we look to somehow account for this?

Quoted 19 lines

Quoted 19 lines

Quoted 19 lines

mm/damon.c +18 -0

+#endif	/* CONFIG_TRANSPARENT_HUGEPAGE */
+
+	spin_unlock(ptl);
+
+mkold:
+	/* mkold next target */
+	r->sampling_addr = damon_rand(ctx, r->vm_start, r->vm_end);
+
+	if (follow_pte_pmd(mm, r->sampling_addr, NULL, &pte, &pmd, &ptl))
+		return;
+
+	if (pte) {
+		if (pte_young(*pte)) {
+			clear_page_idle(pte_page(*pte));
+			set_page_young(pte_page(*pte));
+		}
+		*pte = pte_mkold(*pte);
+	}

Quoted 8 lines

Quoted 8 lines

mm/damon.c static unsigned int nr_damon_regions(struct damon_task *t) · line 500

Quoted 8 lines

mm/damon.c +8 -0

+#ifdef CONFIG_TRANSPARENT_HUGEPAGE
+	else if (pmd) {
+		if (pmd_young(*pmd)) {
+			clear_page_idle(pmd_page(*pmd));
+			set_page_young(pmd_page(*pmd));
+		}
+		*pmd = pmd_mkold(*pmd);
+	}

Quoted 5 lines

Quoted 5 lines

Quoted 5 lines

mm/damon.c +5 -0

+#endif
+
+	spin_unlock(ptl);
+}
+

Quoted 10 lines · On Tue, 10 Mar 2020 15:55:10 +0000 Jonathan Cameron…

Quoted 3 lines · On Tue, 10 Mar 2020 12:52:33 +0100 SeongJae Park <[email protected]> wrote:

Added replies to your every comment in line below. I agree to your whole opinions, will apply those in next spin! :)

One additional question inline that came to mind. Using a single statistic to monitor huge page and normal page hits is going to give us problems I think.

Ah, you're right!!! This is indeed a critical bug!

Quoted 56 lines

Perhaps I'm missing something?

Quoted 41 lines

Quoted 8 lines

Quoted 2 lines

+/*
+ * Check whether the given region has accessed since the last check

Should also make clear that this sets us up for the next access check at a different memory address it the region.

Given the lack of connection between activities perhaps just split this into two functions that are always called next to each other.

Will make the description more clearer as suggested.

Also, I found that I'm not clearing *pte and *pmd before going 'mkold', thanks to this comment. Will fix it, either.

Quoted 14 lines

Quoted 14 lines

+ *
+ * mm 'mm_struct' for the given virtual address space
+ * r the region to be checked
+ */

mm/damon.c +9 -0

+static void kdamond_check_access(struct damon_ctx *ctx,
+			struct mm_struct *mm, struct damon_region *r)
+{
+	pte_t *pte = NULL;
+	pmd_t *pmd = NULL;
+	spinlock_t *ptl;
+
+	if (follow_pte_pmd(mm, r->sampling_addr, NULL, &pte, &pmd, &ptl))
+		goto mkold;

Quoted 8 lines

mm/damon.c static unsigned int nr_damon_regions(struct damon_task *t) · line 472

Quoted 5 lines

mm/damon.c +5 -0

+
+	/* Read the page table access bit of the page */
+	if (pte && pte_young(*pte))
+		r->nr_accesses++;
+#ifdef CONFIG_TRANSPARENT_HUGEPAGE    

Is it worth having this protection? Seems likely to have only a very small influence on performance and makes it a little harder to reason about the code.

It was necessary for addressing 'implicit declaration' problem of 'pmd_young()' and 'pmd_mkold()' for build of DAMON on several architectures including User Mode Linux.

Quoted 5 lines

Will modularize the code for better readability.

Quoted 3 lines

mm/damon.c static unsigned int nr_damon_regions(struct damon_task *t) · line 474

Quoted 3 lines

mm/damon.c +2 -0

+	else if (pmd && pmd_young(*pmd))
+		r->nr_accesses++;  

So we increment a region count by one if we have an access in a huge page, or in a normal page.

If we get a region that has a mixture of the two, this seems likely to give a bad approximation.

Quoted 8 lines

Assume the region is accessed 'evenly' but each " 4k page" is only hit 10% of the time (where a hit is in one check period)

If our address in a page, then we'll hit 10% of the time, but if it is in a 2M huge page then we'll hit a much higher percentage of the time.
1 - (0.9^512) ~= 1

Should we look to somehow account for this?

Yes, this is really critical bug and we should fix this! Thank you so much for finding this!

Quoted 19 lines

Quoted 19 lines

Quoted 19 lines

Quoted 19 lines

mm/damon.c +18 -0

+#endif	/* CONFIG_TRANSPARENT_HUGEPAGE */
+
+	spin_unlock(ptl);
+
+mkold:
+	/* mkold next target */
+	r->sampling_addr = damon_rand(ctx, r->vm_start, r->vm_end);
+
+	if (follow_pte_pmd(mm, r->sampling_addr, NULL, &pte, &pmd, &ptl))
+		return;
+
+	if (pte) {
+		if (pte_young(*pte)) {
+			clear_page_idle(pte_page(*pte));
+			set_page_young(pte_page(*pte));
+		}
+		*pte = pte_mkold(*pte);
+	}

Quoted 8 lines

Quoted 8 lines

Quoted 8 lines

mm/damon.c static unsigned int nr_damon_regions(struct damon_task *t) · line 500

Quoted 8 lines

mm/damon.c +8 -0

+#ifdef CONFIG_TRANSPARENT_HUGEPAGE
+	else if (pmd) {
+		if (pmd_young(*pmd)) {
+			clear_page_idle(pmd_page(*pmd));
+			set_page_young(pmd_page(*pmd));
+		}
+		*pmd = pmd_mkold(*pmd);
+	}  

This is also very problematic if several regions are backed by a single huge page, as only one region in the huge page will be checked as accessed.

Will address these problems in next spin!

Thanks,
SeongJae Park

Quoted 7 lines

Quoted 5 lines

Quoted 5 lines

Quoted 5 lines

mm/damon.c +5 -0

+#endif
+
+	spin_unlock(ptl);
+}
+  

Quoted 114 lines · On Tue, 10 Mar 2020 17:22:40 +0100 SeongJae Park <[email protected]> wrote:

Quoted 10 lines · On Tue, 10 Mar 2020 15:55:10 +0000 Jonathan Cameron…

Quoted 3 lines · On Tue, 10 Mar 2020 12:52:33 +0100 SeongJae Park <[email protected]> wrote:

Added replies to your every comment in line below. I agree to your whole opinions, will apply those in next spin! :)

One additional question inline that came to mind. Using a single statistic to monitor huge page and normal page hits is going to give us problems I think.

Ah, you're right!!! This is indeed a critical bug!

Quoted 56 lines

Perhaps I'm missing something?

Quoted 41 lines

Quoted 8 lines

Quoted 2 lines

+/*
+ * Check whether the given region has accessed since the last check

Should also make clear that this sets us up for the next access check at a different memory address it the region.

Given the lack of connection between activities perhaps just split this into two functions that are always called next to each other.

Will make the description more clearer as suggested.

Also, I found that I'm not clearing *pte and *pmd before going 'mkold', thanks to this comment. Will fix it, either.

Quoted 14 lines

Quoted 14 lines

+ *
+ * mm 'mm_struct' for the given virtual address space
+ * r the region to be checked
+ */

mm/damon.c +9 -0

+static void kdamond_check_access(struct damon_ctx *ctx,
+			struct mm_struct *mm, struct damon_region *r)
+{
+	pte_t *pte = NULL;
+	pmd_t *pmd = NULL;
+	spinlock_t *ptl;
+
+	if (follow_pte_pmd(mm, r->sampling_addr, NULL, &pte, &pmd, &ptl))
+		goto mkold;

Quoted 8 lines

mm/damon.c static unsigned int nr_damon_regions(struct damon_task *t) · line 472

Quoted 5 lines

mm/damon.c +5 -0

+
+	/* Read the page table access bit of the page */
+	if (pte && pte_young(*pte))
+		r->nr_accesses++;
+#ifdef CONFIG_TRANSPARENT_HUGEPAGE    

Is it worth having this protection? Seems likely to have only a very small influence on performance and makes it a little harder to reason about the code.

It was necessary for addressing 'implicit declaration' problem of 'pmd_young()' and 'pmd_mkold()' for build of DAMON on several architectures including User Mode Linux.

Quoted 5 lines

Will modularize the code for better readability.

Quoted 3 lines

mm/damon.c static unsigned int nr_damon_regions(struct damon_task *t) · line 474

Quoted 3 lines

mm/damon.c +2 -0

+	else if (pmd && pmd_young(*pmd))
+		r->nr_accesses++;  

So we increment a region count by one if we have an access in a huge page, or in a normal page.

If we get a region that has a mixture of the two, this seems likely to give a bad approximation.

Quoted 8 lines

Assume the region is accessed 'evenly' but each " 4k page" is only hit 10% of the time (where a hit is in one check period)

If our address in a page, then we'll hit 10% of the time, but if it is in a 2M huge page then we'll hit a much higher percentage of the time.
1 - (0.9^512) ~= 1

Should we look to somehow account for this?

Yes, this is really critical bug and we should fix this! Thank you so much for finding this!

Quoted 19 lines

Quoted 19 lines

Quoted 19 lines

Quoted 19 lines

mm/damon.c +18 -0

+#endif	/* CONFIG_TRANSPARENT_HUGEPAGE */
+
+	spin_unlock(ptl);
+
+mkold:
+	/* mkold next target */
+	r->sampling_addr = damon_rand(ctx, r->vm_start, r->vm_end);
+
+	if (follow_pte_pmd(mm, r->sampling_addr, NULL, &pte, &pmd, &ptl))
+		return;
+
+	if (pte) {
+		if (pte_young(*pte)) {
+			clear_page_idle(pte_page(*pte));
+			set_page_young(pte_page(*pte));
+		}
+		*pte = pte_mkold(*pte);
+	}

Quoted 8 lines

Quoted 8 lines

Quoted 8 lines

mm/damon.c static unsigned int nr_damon_regions(struct damon_task *t) · line 500

Quoted 8 lines

mm/damon.c +8 -0

+#ifdef CONFIG_TRANSPARENT_HUGEPAGE
+	else if (pmd) {
+		if (pmd_young(*pmd)) {
+			clear_page_idle(pmd_page(*pmd));
+			set_page_young(pmd_page(*pmd));
+		}
+		*pmd = pmd_mkold(*pmd);
+	}  

This is also very problematic if several regions are backed by a single huge page, as only one region in the huge page will be checked as accessed.

Quoted 1 line

Will address these problems in next spin!

Good point. There is little point in ever having multiple regions including a single huge page. Would it be possible to tweak the region splitting algorithm to not do this?

Jonathan

Quoted 12 lines

Thanks,
SeongJae Park

Quoted 7 lines

Quoted 5 lines

Quoted 5 lines

Quoted 5 lines

mm/damon.c +5 -0

+#endif
+
+	spin_unlock(ptl);
+}
+  

From: SeongJae Park <[email protected]>

This commit implements DAMON's basic access check and region based sampling mechanisms. This change would seems make no sense, mainly because it is only a part of the DAMON's logics. Following two commits will make more sense.

This commit also exports lookup_page_ext() to GPL modules because DAMON uses the function but also supports the module build.

Basic Access Check
------------------

DAMON basically reports what pages are how frequently accessed. Note that the frequency is not an absolute number of accesses, but a relative frequency among the pages of the target workloads.

Users can control the resolution of the reports by setting two time intervals, ``sampling interval`` and ``aggregation interval``. In detail, DAMON checks access to each page per ``sampling interval``, aggregates the results (counts the number of the accesses to each page), and reports the aggregated results per ``aggregation interval``. For the access check of each page, DAMON uses the Accessed bits of PTEs.

This is thus similar to common periodic access checks based access tracking mechanisms, which overhead is increasing as the size of the target process grows.

Region Based Sampling
---------------------

To avoid the unbounded increase of the overhead, DAMON groups a number of adjacent pages that assumed to have same access frequencies into a region. As long as the assumption (pages in a region have 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 and clears its Accessed bit. After one more ``sampling interval``, DAMON reads the Accessed bit of the page and increases the access frequency of the region if the bit has set meanwhile. Therefore, the monitoring overhead is controllable by setting the number of regions.

Nonetheless, this scheme cannot preserve the quality of the output if the assumption is not kept. Following commit will introduce how we can make the guarantee with best effort.

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

---
 mm/damon.c    | 509 ++++++++++++++++++++++++++++++++++++++++++++++++++
 mm/page_ext.c |   1 +
 2 files changed, 510 insertions(+)

mm/damon.c +420 -0

index aafdca35b7b8..6bdeb84d89af 100644
@@ -9,9 +9,14 @@
 
 #define pr_fmt(fmt) "damon: " fmt
 
+#include <linux/delay.h>
+#include <linux/kthread.h>
 #include <linux/mm.h>
 #include <linux/module.h>
+#include <linux/page_idle.h>
 #include <linux/random.h>
+#include <linux/sched/mm.h>
+#include <linux/sched/task.h>
 #include <linux/slab.h>
 
 #define damon_get_task_struct(t) \

@@ -51,7 +56,24 @@ struct damon_task {
 	struct list_head list;
 };
 
+/*
+ * 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 each 'aggr_interval' time.
+ *
+ * All time intervals are in micro-seconds.
+ */
 struct damon_ctx {
+	unsigned long sample_interval;
+	unsigned long aggr_interval;
+	unsigned long min_nr_regions;
+
+	struct timespec64 last_aggregation;
+
+	struct task_struct *kdamond;
+	bool kdamond_stop;
+	spinlock_t kdamond_lock;
+
 	struct rnd_state rndseed;
 
 	struct list_head tasks_list;	/* 'damon_task' objects */

@@ -204,6 +226,493 @@ static unsigned int nr_damon_regions(struct damon_task *t)
 	return ret;
 }
 
+/*
+ * Get the mm_struct of the given task
+ *
+ * Callser should put the mm_struct after use, unless it is NULL.
+ *
+ * Returns the mm_struct of the task on success, NULL on failure
+ */
+static struct mm_struct *damon_get_mm(struct damon_task *t)
+{
+	struct task_struct *task;
+	struct mm_struct *mm;
+
+	task = damon_get_task_struct(t);
+	if (!task)
+		return NULL;
+
+	mm = get_task_mm(task);
+	put_task_struct(task);
+	return mm;
+}
+
+/*
+ * Size-evenly split a region into 'nr_pieces' small regions
+ *
+ * Returns 0 on success, or negative error code otherwise.
+ */
+static int damon_split_region_evenly(struct damon_ctx *ctx,
+		struct damon_region *r, unsigned int nr_pieces)
+{
+	unsigned long sz_orig, sz_piece, orig_end;
+	struct damon_region *piece = NULL, *next;
+	unsigned long start;
+
+	if (!r || !nr_pieces)
+		return -EINVAL;
+
+	orig_end = r->vm_end;
+	sz_orig = r->vm_end - r->vm_start;
+	sz_piece = sz_orig / nr_pieces;
+
+	if (!sz_piece)
+		return -EINVAL;
+
+	r->vm_end = r->vm_start + sz_piece;
+	next = damon_next_region(r);
+	for (start = r->vm_end; start + sz_piece <= orig_end;
+			start += sz_piece) {
+		piece = damon_new_region(ctx, start, start + sz_piece);
+		damon_add_region(piece, r, next);
+		r = piece;
+	}
+	if (piece)
+		piece->vm_end = orig_end;
+	return 0;
+}
+
+struct region {
+	unsigned long start;
+	unsigned long end;
+};
+
+static unsigned long sz_region(struct region *r)
+{
+	return r->end - r->start;
+}
+
+static void swap_regions(struct region *r1, struct region *r2)
+{
+	struct region tmp;
+
+	tmp = *r1;
+	*r1 = *r2;
+	*r2 = tmp;
+}
+
+/*
+ * Find the three regions in an address space
+ *
+ * vma		the head vma of the target address space
+ * regions	an array of three 'struct region's that results will be saved
+ *
+ * This function receives an address space and finds three regions in it which
+ * separated by the two biggest unmapped regions in the space.  Please refer to
+ * below comments of 'damon_init_regions_of()' function to know why this is
+ * necessary.
+ *
+ * Returns 0 if success, or negative error code otherwise.
+ */
+static int damon_three_regions_in_vmas(struct vm_area_struct *vma,
+		struct region regions[3])
+{
+	struct region gap = {0,}, first_gap = {0,}, second_gap = {0,};
+	struct vm_area_struct *last_vma = NULL;
+	unsigned long start = 0;
+
+	/* Find two biggest gaps so that first_gap > second_gap > others */
+	for (; vma; vma = vma->vm_next) {
+		if (!last_vma) {
+			start = vma->vm_start;
+			last_vma = vma;
+			continue;
+		}
+		gap.start = last_vma->vm_end;
+		gap.end = vma->vm_start;
+		if (sz_region(&gap) > sz_region(&second_gap)) {
+			swap_regions(&gap, &second_gap);
+			if (sz_region(&second_gap) > sz_region(&first_gap))
+				swap_regions(&second_gap, &first_gap);
+		}
+		last_vma = vma;
+	}
+
+	if (!sz_region(&second_gap) || !sz_region(&first_gap))
+		return -EINVAL;
+
+	/* Sort the two biggest gaps by address */
+	if (first_gap.start > second_gap.start)
+		swap_regions(&first_gap, &second_gap);
+
+	/* Store the result */
+	regions[0].start = start;
+	regions[0].end = first_gap.start;
+	regions[1].start = first_gap.end;
+	regions[1].end = second_gap.start;
+	regions[2].start = second_gap.end;
+	regions[2].end = last_vma->vm_end;
+
+	return 0;
+}
+
+/*
+ * Get the three regions in the given task
+ *
+ * Returns 0 on success, negative error code otherwise.
+ */
+static int damon_three_regions_of(struct damon_task *t,
+				struct region regions[3])
+{
+	struct mm_struct *mm;
+	int ret;
+
+	mm = damon_get_mm(t);
+	if (!mm)
+		return -EINVAL;
+
+	down_read(&mm->mmap_sem);
+	ret = damon_three_regions_in_vmas(mm->mmap, regions);
+	up_read(&mm->mmap_sem);
+
+	mmput(mm);
+	return ret;
+}
+
+/*
+ * Initialize the monitoring target regions for the given task
+ *
+ * t	the given target task
+ *
+ * Because only a number of small portions of the entire address space
+ * is acutally mapped to the memory and accessed, monitoring the unmapped
+ * regions is wasteful.  That said, because we can deal with small noises,
+ * tracking every mapping is not strictly required but could even incur a high
+ * overhead if the mapping frequently changes or the number of mappings is
+ * high.  Nonetheless, this may seems very weird.  DAMON's dynamic regions
+ * adjustment mechanism, which will be implemented with following commit will
+ * make this more sense.
+ *
+ * For the reason, we convert the complex mappings to three distinct regions
+ * that cover every mapped areas of the address space.  Also the two gaps
+ * between the three regions are the two biggest unmapped areas in the given
+ * address space.  In detail, this function first identifies the start and the
+ * end of the mappings and the two biggest unmapped areas of the address space.
+ * Then, it constructs the three regions as below:
+ *
+ *     [mappings[0]->start, big_two_unmapped_areas[0]->start)
+ *     [big_two_unmapped_areas[0]->end, big_two_unmapped_areas[1]->start)
+ *     [big_two_unmapped_areas[1]->end, mappings[nr_mappings - 1]->end)
+ *
+ * As usual memory map of processes is as below, the gap between the heap and
+ * the uppermost mmap()-ed region, and the gap between the lowermost mmap()-ed
+ * region and the stack will be two biggest unmapped regions.  Because these
+ * gaps are exceptionally huge areas in usual address space, excluding these
+ * two biggest unmapped regions will be sufficient to make a trade-off.
+ *
+ *   <heap>
+ *   <BIG UNMAPPED REGION 1>
+ *   <uppermost mmap()-ed region>
+ *   (other mmap()-ed regions and small unmapped regions)
+ *   <lowermost mmap()-ed region>
+ *   <BIG UNMAPPED REGION 2>
+ *   <stack>
+ */
+static void damon_init_regions_of(struct damon_ctx *c, struct damon_task *t)
+{
+	struct damon_region *r;
+	struct region regions[3];
+	int i;
+
+	if (damon_three_regions_of(t, regions)) {
+		pr_err("Failed to get three regions of task %lu\n", t->pid);
+		return;
+	}
+
+	/* Set the initial three regions of the task */
+	for (i = 0; i < 3; i++) {
+		r = damon_new_region(c, regions[i].start, regions[i].end);
+		damon_add_region_tail(r, t);
+	}
+
+	/* Split the middle region into 'min_nr_regions - 2' regions */
+	r = damon_nth_region_of(t, 1);
+	if (damon_split_region_evenly(c, r, c->min_nr_regions - 2))
+		pr_warn("Init middle region failed to be split\n");
+}
+
+/* Initialize '->regions_list' of every task */
+static void kdamond_init_regions(struct damon_ctx *ctx)
+{
+	struct damon_task *t;
+
+	damon_for_each_task(ctx, t)
+		damon_init_regions_of(ctx, t);
+}
+
+/*
+ * Check whether the given region has accessed since the last check
+ *
+ * mm	'mm_struct' for the given virtual address space
+ * r	the region to be checked
+ */
+static void kdamond_check_access(struct damon_ctx *ctx,
+			struct mm_struct *mm, struct damon_region *r)
+{
+	pte_t *pte = NULL;
+	pmd_t *pmd = NULL;
+	spinlock_t *ptl;
+
+	if (follow_pte_pmd(mm, r->sampling_addr, NULL, &pte, &pmd, &ptl))
+		goto mkold;
+
+	/* Read the page table access bit of the page */
+	if (pte && pte_young(*pte))
+		r->nr_accesses++;
+#ifdef CONFIG_TRANSPARENT_HUGEPAGE
+	else if (pmd && pmd_young(*pmd))
+		r->nr_accesses++;
+#endif	/* CONFIG_TRANSPARENT_HUGEPAGE */
+
+	spin_unlock(ptl);
+
+mkold:
+	/* mkold next target */
+	r->sampling_addr = damon_rand(ctx, r->vm_start, r->vm_end);
+
+	if (follow_pte_pmd(mm, r->sampling_addr, NULL, &pte, &pmd, &ptl))
+		return;
+
+	if (pte) {
+		if (pte_young(*pte)) {
+			clear_page_idle(pte_page(*pte));
+			set_page_young(pte_page(*pte));
+		}
+		*pte = pte_mkold(*pte);
+	}
+#ifdef CONFIG_TRANSPARENT_HUGEPAGE
+	else if (pmd) {
+		if (pmd_young(*pmd)) {
+			clear_page_idle(pmd_page(*pmd));
+			set_page_young(pmd_page(*pmd));
+		}
+		*pmd = pmd_mkold(*pmd);
+	}
+#endif
+
+	spin_unlock(ptl);
+}
+
+/*
+ * Check whether 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.
+ *
+ * Returns 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
+ */
+static void kdamond_flush_aggregated(struct damon_ctx *c)
+{
+	struct damon_task *t;
+	struct damon_region *r;
+
+	damon_for_each_task(c, t) {
+		damon_for_each_region(r, t)
+			r->nr_accesses = 0;
+	}
+}
+
+/*
+ * Check whether current monitoring should be stopped
+ *
+ * If users asked to stop, need stop.  Even though no user has asked to stop,
+ * need stop if every target task has dead.
+ *
+ * Returns true if need to stop current monitoring.
+ */
+static bool kdamond_need_stop(struct damon_ctx *ctx)
+{
+	struct damon_task *t;
+	struct task_struct *task;
+	bool stop;
+
+	spin_lock(&ctx->kdamond_lock);
+	stop = ctx->kdamond_stop;
+	spin_unlock(&ctx->kdamond_lock);
+	if (stop)
+		return true;
+
+	damon_for_each_task(ctx, t) {
+		task = damon_get_task_struct(t);
+		if (task) {
+			put_task_struct(task);
+			return false;
+		}
+	}
+
+	return true;
+}
+
+/*
+ * 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_task *t;
+	struct damon_region *r, *next;
+	struct mm_struct *mm;
+
+	pr_info("kdamond (%d) starts\n", ctx->kdamond->pid);
+	kdamond_init_regions(ctx);
+	while (!kdamond_need_stop(ctx)) {
+		damon_for_each_task(ctx, t) {
+			mm = damon_get_mm(t);
+			if (!mm)
+				continue;
+			damon_for_each_region(r, t)
+				kdamond_check_access(ctx, mm, r);
+			mmput(mm);
+		}
+
+		if (kdamond_aggregate_interval_passed(ctx))
+			kdamond_flush_aggregated(ctx);
+
+		usleep_range(ctx->sample_interval, ctx->sample_interval + 1);
+	}
+	damon_for_each_task(ctx, t) {
+		damon_for_each_region_safe(r, next, t)
+			damon_destroy_region(r);
+	}
+	pr_info("kdamond (%d) finishes\n", ctx->kdamond->pid);
+	spin_lock(&ctx->kdamond_lock);
+	ctx->kdamond = NULL;
+	spin_unlock(&ctx->kdamond_lock);
+	return 0;
+}
+
+/*
+ * Controller functions
+ */
+
+/*