Introduce Data Access MONitor (DAMON)

From: SeongJae Park <[email protected]>

This commit exports 'lookup_page_ext()' to GPL modules. It will be used by DAMON in following commit for the implementation of the region based sampling.

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

Reviewed-by Leonard Foerster <[email protected]>

Reviewed-by Varad Gautam <[email protected]>

---
 mm/page_ext.c | 1 +
 1 file changed, 1 insertion(+)

mm/page_ext.c +1 -0

index a3616f7a0e9e..9d802d01fcb5 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)
 {

Signature · 1 line

2.17.1

Hi,

Quoted 5 lines · SeongJae Park

From: SeongJae Park <[email protected]>

This commit exports 'lookup_page_ext()' to GPL modules. It will be used by DAMON in following commit for the implementation of the region based sampling.

Maybe I'm missing something, but why is DAMON a module?

Quoted 23 lines

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

Reviewed-by Leonard Foerster <[email protected]>

Reviewed-by Varad Gautam <[email protected]>

---
 mm/page_ext.c | 1 +
 1 file changed, 1 insertion(+)

mm/page_ext.c +1 -0

index a3616f7a0e9e..9d802d01fcb5 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)
 {

Signature · 1 line

2.17.1

Signature · 2 lines

Sincerely yours,
Mike.

Quoted 5 lines · On Mon, 13 Jul 2020 15:08:42 +0300 Mike Rapoport <[email protected]> wrote:

Hi,

Quoted 2 lines · SeongJae Park

From: SeongJae Park <[email protected]>

Quoted 5 lines

Quoted 3 lines

This commit exports 'lookup_page_ext()' to GPL modules. It will be used by DAMON in following commit for the implementation of the region based sampling.

Maybe I'm missing something, but why is DAMON a module?

I made it loadable just for easier adoption from downstream kernels. I could drop the module build support if asked.

Thanks,
SeongJae Park

Quoted 27 lines

Quoted 23 lines

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

Reviewed-by Leonard Foerster <[email protected]>

Reviewed-by Varad Gautam <[email protected]>

---
 mm/page_ext.c | 1 +
 1 file changed, 1 insertion(+)

mm/page_ext.c +1 -0

index a3616f7a0e9e..9d802d01fcb5 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)
 {

Signature · 1 line

2.17.1

Signature · 2 lines

Sincerely yours,
Mike.

Quoted 11 lines · SeongJae Park

Quoted 9 lines · On Mon, 13 Jul 2020 15:08:42 +0300 Mike Rapoport <[email protected]> wrote:

Hi,

Quoted 5 lines · SeongJae Park

From: SeongJae Park <[email protected]>

This commit exports 'lookup_page_ext()' to GPL modules. It will be used by DAMON in following commit for the implementation of the region based sampling.

Quoted 4 lines

Quoted 1 line

Maybe I'm missing something, but why is DAMON a module?

I made it loadable just for easier adoption from downstream kernels. I could drop the module build support if asked.

Well, exporting core mm symbols to modules should be considred very carefully.

Why lookup_page_ext() is required for DAMON? It is not used anywhere in this patchset.

Quoted 12 lines · On Mon, 13 Jul 2020 20:19:09 +0300 Mike Rapoport <[email protected]> wrote:

Quoted 11 lines · SeongJae Park

Quoted 9 lines · On Mon, 13 Jul 2020 15:08:42 +0300 Mike Rapoport <[email protected]> wrote:

Hi,

Quoted 5 lines · SeongJae Park

From: SeongJae Park <[email protected]>

This commit exports 'lookup_page_ext()' to GPL modules. It will be used by DAMON in following commit for the implementation of the region based sampling.

Quoted 7 lines

Quoted 4 lines

Quoted 1 line

Maybe I'm missing something, but why is DAMON a module?

I made it loadable just for easier adoption from downstream kernels. I could drop the module build support if asked.

Well, exporting core mm symbols to modules should be considred very carefully.

Agreed. I will drop the module support from the next spin.

Quoted 1 line

Quoted 2 lines

Why lookup_page_ext() is required for DAMON? It is not used anywhere in this patchset.

It's indirectly used. In the 6th patch, DAMON uses 'set_page_young()' to not interfere with other PTE Accessed bit users. And, 'set_page_young()' uses 'lookup_page_ext()' if !CONFIG_64BIT. That's why I exported it.

From: SeongJae Park <[email protected]>

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

- accurate (the monitoring output is useful enough for DRAM level memory management; It might not appropriate for CPU Cache levels, though),
- light-weight (the monitoring overhead is 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, therefore, the kernel's memory management mechanisms can make advanced decisions. Experimental memory management optimization works that incurring high data accesses monitoring overhead could implemented again. In user space, meanwhile, users who have some special workloads can write personalized applications for better understanding and optimizations of their workloads and systems.

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.

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

Reviewed-by Leonard Foerster <[email protected]>

Reviewed-by Varad Gautam <[email protected]>

---
 include/linux/damon.h |  63 ++++++++++++++
 mm/Kconfig            |  12 +++
 mm/Makefile           |   1 +
 mm/damon.c            | 188 ++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 264 insertions(+)
 create mode 100644 include/linux/damon.h
 create mode 100644 mm/damon.c

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

new file mode 100644
index 000000000000..c8f8c1c41a45
@@ -0,0 +1,63 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * DAMON api
+ *
+ * Copyright 2019-2020 Amazon.com, Inc. or its affiliates.
+ *
+ * Author: SeongJae Park <[email protected]>
+ */
+
+#ifndef _DAMON_H_
+#define _DAMON_H_
+
+#include <linux/random.h>
+#include <linux/types.h>
+
+/**
+ * struct damon_addr_range - Represents an address region of [@start, @end).
+ * @start:     Start address of the region (inclusive).
+ * @end:       End address of the region (exclusive).
+ */
+struct damon_addr_range {
+       unsigned long start;
+       unsigned long end;
+};
+
+/**
+ * struct damon_region - Represents a monitoring target region.
+ * @ar:                        The address range of the region.
+ * @sampling_addr:     Address of the sample for the next access check.
+ * @nr_accesses:       Access frequency of this region.
+ * @list:              List head for siblings.
+ */
+struct damon_region {
+       struct damon_addr_range ar;
+       unsigned long sampling_addr;
+       unsigned int nr_accesses;
+       struct list_head list;
+};
+
+/**

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

+       struct list_head regions_list;
+       struct list_head list;
+};
+
+/**
+ * struct damon_ctx - Represents a context for each monitoring.
+ * @tasks_list:                Head of monitoring target tasks (&damon_task) list.
+ */
+struct damon_ctx {
+       struct list_head tasks_list;    /* 'damon_task' objects */
+};
+
+#endif

mm/Kconfig +12 -0

index c1acc34c1c35..464e9594dcec 100644
@@ -867,4 +867,16 @@ config ARCH_HAS_HUGEPD
 config MAPPING_DIRTY_HELPERS
         bool
 
+config DAMON
+       tristate "Data Access Monitor"
+       depends on MMU
+       help
+         This feature allows to monitor access frequency of each memory
+         region. The information can be useful for performance-centric DRAM
+         level memory management.
+
+         See https://damonitor.github.io/doc/html/latest-damon/index.html for
+         more information.
+         If unsure, say N.
+
 endmenu

mm/Makefile +1 -0

index fccd3756b25f..230e545b6e07 100644
@@ -112,3 +112,4 @@ obj-$(CONFIG_MEMFD_CREATE) += memfd.o
 obj-$(CONFIG_MAPPING_DIRTY_HELPERS) += mapping_dirty_helpers.o
 obj-$(CONFIG_PTDUMP_CORE) += ptdump.o
 obj-$(CONFIG_PAGE_REPORTING) += page_reporting.o
+obj-$(CONFIG_DAMON) += damon.o

mm/damon.c new file +19 -0

new file mode 100644
index 000000000000..5ab13b1c15cf
@@ -0,0 +1,188 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * Data Access Monitor
+ *
+ * Copyright 2019-2020 Amazon.com, Inc. or its affiliates.
+ *
+ * Author: SeongJae Park <[email protected]>
+ *
+ * This file is constructed in below parts.
+ *
+ * - Functions and macros for DAMON data structures
+ * - Functions for the module loading/unloading
+ *
+ * The core parts are not implemented yet.
+ */
+
+#define pr_fmt(fmt) "damon: " fmt
+
+#include <linux/damon.h>

mm/damon.c new file +159 -1

+
+#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(t, ctx) \
+       list_for_each_entry(t, &(ctx)->tasks_list, list)
+
+#define damon_for_each_task_safe(t, next, ctx) \
+       list_for_each_entry_safe(t, next, &(ctx)->tasks_list, list)
+
+/* Get a random number in [l, r) */
+#define damon_rand(l, r) (l + prandom_u32() % (r - l))
+
+/*
+ * Construct a damon_region struct
+ *
+ * Returns the pointer to the new struct if success, or NULL otherwise
+ */
+static struct damon_region *damon_new_region(unsigned long start,
+                                            unsigned long end)
+{
+       struct damon_region *region;
+
+       region = kmalloc(sizeof(*region), GFP_KERNEL);
+       if (!region)
+               return NULL;
+
+       region->ar.start = start;
+       region->ar.end = end;
+       region->nr_accesses = 0;
+       INIT_LIST_HEAD(&region->list);
+
+       return region;
+}
+
+/*
+ * Add a region between two other regions
+ */
+static inline void damon_insert_region(struct damon_region *r,
+               struct damon_region *prev, struct damon_region *next)
+{
+       __list_add(&r->list, &prev->list, &next->list);
+}
+
+static void damon_add_region(struct damon_region *r, struct damon_task *t)
+{
+       list_add_tail(&r->list, &t->regions_list);
+}
+
+static void damon_del_region(struct damon_region *r)
+{
+       list_del(&r->list);
+}
+
+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
+ */
+static struct damon_task *damon_new_task(int pid)
+{
+       struct damon_task *t;
+
+       t = kmalloc(sizeof(*t), GFP_KERNEL);
+       if (!t)
+               return NULL;
+
+       t->pid = pid;
+       INIT_LIST_HEAD(&t->regions_list);
+
+       return t;
+}
+
+static void damon_add_task(struct damon_ctx *ctx, struct damon_task *t)
+{
+       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)
+{
+       damon_del_task(t);
+       damon_free_task(t);
+}
+
+static unsigned int nr_damon_tasks(struct damon_ctx *ctx)
+{
+       struct damon_task *t;
+       unsigned int nr_tasks = 0;
+
+       damon_for_each_task(t, ctx)
+               nr_tasks++;
+
+       return nr_tasks;
+}
+
+static unsigned int nr_damon_regions(struct damon_task *t)
+{
+       struct damon_region *r;
+       unsigned int nr_regions = 0;
+
+       damon_for_each_region(r, t)
+               nr_regions++;
+
+       return nr_regions;
+}
+
+/*
+ * Functions for the module loading/unloading
+ */
+
+static int __init damon_init(void)
+{
+       return 0;
+}
+
+static void __exit damon_exit(void)
+{
+}
+
+module_init(damon_init);
+module_exit(damon_exit);
+
+MODULE_LICENSE("GPL");
+MODULE_AUTHOR("SeongJae Park <[email protected]>");
+MODULE_DESCRIPTION("DAMON: Data Access MONitor");
--

2.17.1

Quoted 53 lines · SeongJae Park

From: SeongJae Park <[email protected]>

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

- accurate (the monitoring output is useful enough for DRAM level memory management; It might not appropriate for CPU Cache levels, though),
- light-weight (the monitoring overhead is 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, therefore, the kernel's memory management mechanisms can make advanced decisions. Experimental memory management optimization works that incurring high data accesses monitoring overhead could implemented again. In user space, meanwhile, users who have some special workloads can write personalized applications for better understanding and optimizations of their workloads and systems.

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.

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

Reviewed-by Leonard Foerster <[email protected]>

Reviewed-by Varad Gautam <[email protected]>

---
 include/linux/damon.h |  63 ++++++++++++++
 mm/Kconfig            |  12 +++
 mm/Makefile           |   1 +
 mm/damon.c            | 188 ++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 264 insertions(+)
 create mode 100644 include/linux/damon.h
 create mode 100644 mm/damon.c

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

new file mode 100644
index 000000000000..c8f8c1c41a45
@@ -0,0 +1,63 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * DAMON api
+ *
+ * Copyright 2019-2020 Amazon.com, Inc. or its affiliates.
+ *
+ * Author: SeongJae Park <[email protected]>
+ */
+

include/linux/damon.h line 50

Quoted 12 lines

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

+
+/**
+ * struct damon_task - Represents a monitoring target task.
+ * @pid:               Process id of the task.
+ * @regions_list:      Head of the monitoring target regions of this task.
+ * @list:              List head for siblings.
+ *
+ * If the monitoring target address space is task independent (e.g., physical
+ * memory address space monitoring), @pid should be '-1'.
+ */
+struct damon_task {
+       int pid;

Storing and accessing pid like this is racy. Why not save the "struct pid" after getting the reference? I am still going over the usage, maybe storing mm_struct would be an even better choice.

Quoted 4 lines

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

+       struct list_head regions_list;
+       struct list_head list;
+};
+

include/linux/damon.h

Quoted 3 lines

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

+
+#define damon_get_task_struct(t) \
+       (get_pid_task(find_vpid(t->pid), PIDTYPE_PID))

You need at least rcu lock around find_vpid(). Also you need to be careful about the context. If you accept my previous suggestion then you just need to do this in the process context which is registering the pid (no need to worry about the pid namespace).

I am wondering if there should be an interface to register processes with DAMON using pidfd instead of integer pid.

Quoted 54 lines · On Fri, 17 Jul 2020 19:47:50 -0700 Shakeel Butt <[email protected]> wrote:

Quoted 53 lines · SeongJae Park

From: SeongJae Park <[email protected]>

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

- accurate (the monitoring output is useful enough for DRAM level memory management; It might not appropriate for CPU Cache levels, though),
- light-weight (the monitoring overhead is 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, therefore, the kernel's memory management mechanisms can make advanced decisions. Experimental memory management optimization works that incurring high data accesses monitoring overhead could implemented again. In user space, meanwhile, users who have some special workloads can write personalized applications for better understanding and optimizations of their workloads and systems.

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.

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

Reviewed-by Leonard Foerster <[email protected]>

Reviewed-by Varad Gautam <[email protected]>

---
 include/linux/damon.h |  63 ++++++++++++++
 mm/Kconfig            |  12 +++
 mm/Makefile           |   1 +
 mm/damon.c            | 188 ++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 264 insertions(+)
 create mode 100644 include/linux/damon.h
 create mode 100644 mm/damon.c

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

new file mode 100644
index 000000000000..c8f8c1c41a45
@@ -0,0 +1,63 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * DAMON api
+ *
+ * Copyright 2019-2020 Amazon.com, Inc. or its affiliates.
+ *
+ * Author: SeongJae Park <[email protected]>
+ */
+

[...]

Quoted 21 lines

include/linux/damon.h line 50

Quoted 12 lines

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

+
+/**
+ * struct damon_task - Represents a monitoring target task.
+ * @pid:               Process id of the task.
+ * @regions_list:      Head of the monitoring target regions of this task.
+ * @list:              List head for siblings.
+ *
+ * If the monitoring target address space is task independent (e.g., physical
+ * memory address space monitoring), @pid should be '-1'.
+ */
+struct damon_task {
+       int pid;

Storing and accessing pid like this is racy. Why not save the "struct pid" after getting the reference? I am still going over the usage, maybe storing mm_struct would be an even better choice.

Quoted 4 lines

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

+       struct list_head regions_list;
+       struct list_head list;
+};
+

[...]

Quoted 11 lines

include/linux/damon.h

Quoted 3 lines

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

+
+#define damon_get_task_struct(t) \
+       (get_pid_task(find_vpid(t->pid), PIDTYPE_PID))

You need at least rcu lock around find_vpid(). Also you need to be careful about the context. If you accept my previous suggestion then you just need to do this in the process context which is registering the pid (no need to worry about the pid namespace).

I am wondering if there should be an interface to register processes with DAMON using pidfd instead of integer pid.

Good points! I will use pidfd for this purpose, instead.

BTW, 'struct damon_task' was introduced while DAMON supports only virtual address spaces and recently extended to support physical memory address monitoring case by defining an exceptional pid (-1) for such case. I think it doesn't smoothly fit with the design.

Therefore, I would like to change it with more general named struct, e.g.,

    struct damon_target {
            void *id;
            struct list_head regions_list;
            struct list_head list;
    };

The 'id' field will be able to store or point pid_t, struct mm_struct, struct pid, or anything relevant, depending on the target address space.

Only one part of the address space independent logics of DAMON, namely 'kdamon_need_stop()', uses '->pid' of the 'struct damon_task'. It will be introduced by the next patch ("mm/damon: Implement region based sampling"). Therefore, the conversion will be easy. For the part, I could add another callback, e.g.,

    struct damon_ctx {
            [...]
            bool (*is_target_valid)(struct damon_target *t);
    };

And let the address space specific primitives to implement this.

Then, damon_get_task_struct() and damon_get_mm() will be introduced by the sixth patch ("mm/damon: Implement callbacks for the virtual memory address spaces") as a part of the virtual address space specific primitives implementation.

I gonna make the change in the next spin. If you have some opinions on this, please let me know.

Quoted 123 lines · SeongJae Park

Quoted 54 lines · On Fri, 17 Jul 2020 19:47:50 -0700 Shakeel Butt <[email protected]> wrote:

Quoted 53 lines · SeongJae Park

From: SeongJae Park <[email protected]>

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

- accurate (the monitoring output is useful enough for DRAM level memory management; It might not appropriate for CPU Cache levels, though),
- light-weight (the monitoring overhead is 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, therefore, the kernel's memory management mechanisms can make advanced decisions. Experimental memory management optimization works that incurring high data accesses monitoring overhead could implemented again. In user space, meanwhile, users who have some special workloads can write personalized applications for better understanding and optimizations of their workloads and systems.

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.

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

Reviewed-by Leonard Foerster <[email protected]>

Reviewed-by Varad Gautam <[email protected]>

---
 include/linux/damon.h |  63 ++++++++++++++
 mm/Kconfig            |  12 +++
 mm/Makefile           |   1 +
 mm/damon.c            | 188 ++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 264 insertions(+)
 create mode 100644 include/linux/damon.h
 create mode 100644 mm/damon.c

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

new file mode 100644
index 000000000000..c8f8c1c41a45
@@ -0,0 +1,63 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * DAMON api
+ *
+ * Copyright 2019-2020 Amazon.com, Inc. or its affiliates.
+ *
+ * Author: SeongJae Park <[email protected]>
+ */
+

[...]

Quoted 21 lines

include/linux/damon.h line 50

Quoted 12 lines

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

+
+/**
+ * struct damon_task - Represents a monitoring target task.
+ * @pid:               Process id of the task.
+ * @regions_list:      Head of the monitoring target regions of this task.
+ * @list:              List head for siblings.
+ *
+ * If the monitoring target address space is task independent (e.g., physical
+ * memory address space monitoring), @pid should be '-1'.
+ */
+struct damon_task {
+       int pid;

Storing and accessing pid like this is racy. Why not save the "struct pid" after getting the reference? I am still going over the usage, maybe storing mm_struct would be an even better choice.

Quoted 4 lines

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

+       struct list_head regions_list;
+       struct list_head list;
+};
+

[...]

Quoted 11 lines

include/linux/damon.h

Quoted 3 lines

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

+
+#define damon_get_task_struct(t) \
+       (get_pid_task(find_vpid(t->pid), PIDTYPE_PID))

You need at least rcu lock around find_vpid(). Also you need to be careful about the context. If you accept my previous suggestion then you just need to do this in the process context which is registering the pid (no need to worry about the pid namespace).

I am wondering if there should be an interface to register processes with DAMON using pidfd instead of integer pid.

Good points! I will use pidfd for this purpose, instead.

BTW, 'struct damon_task' was introduced while DAMON supports only virtual address spaces and recently extended to support physical memory address monitoring case by defining an exceptional pid (-1) for such case. I think it doesn't smoothly fit with the design.

Therefore, I would like to change it with more general named struct, e.g.,

    struct damon_target {
            void *id;
            struct list_head regions_list;
            struct list_head list;
    };

The 'id' field will be able to store or point pid_t, struct mm_struct, struct pid, or anything relevant, depending on the target address space.

Only one part of the address space independent logics of DAMON, namely 'kdamon_need_stop()', uses '->pid' of the 'struct damon_task'. It will be introduced by the next patch ("mm/damon: Implement region based sampling"). Therefore, the conversion will be easy. For the part, I could add another callback, e.g.,

    struct damon_ctx {
            [...]
            bool (*is_target_valid)(struct damon_target *t);
    };

And let the address space specific primitives to implement this.

Quoted 9 lines

Then, damon_get_task_struct() and damon_get_mm() will be introduced by the sixth patch ("mm/damon: Implement callbacks for the virtual memory address spaces") as a part of the virtual address space specific primitives implementation.

I gonna make the change in the next spin. If you have some opinions on this, please let me know.

Sorry for the late response. I think the general direction you are taking is fine but there are still some open questions. I am trying to reason if 'address space' is general enough abstraction for different types of monitoring targets. It fits well for the 'processes' targets.

For the physical memory, the monitoring part of the abstraction (i.e. damon_ctx) seems fine but I am not sure about the optimization part (i.e. [merge|split]_regions) which raises the question that should the merge/split functionality be part of the abstraction.

I am also very interested in the 'cgroups' as the target and I am not sure if 'address space' is the right abstraction for the cgroups as well. Well we can think of cgroups as a combination of tasks but cgroup also contains unmapped pages. So, maybe it is a combination of virtual and physical address space targets damon can monitor but I am still not clear how to specify that in the abstractions provided by damon.

Anyways these are the questions for later and we can start simple with just processes but I would like to not expose these abstractions/interfaces to userspace otherwise it would be really hard to change later.

Another topic I want to discuss is managing/charging the resource (cpu) usage of monitoring. Yes, damon with optimization has low cpu cost but as the number of targets increase the cpu cost will increase which will be in a range which can not be ignored as system overhead. At the moment, it seems like there is one kthread doing all the monitoring, since we can control the cpu usage of kthreads, it might make sense to allow different kthreads for different sets of targets (processes in a cgroup).

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. To avoid disturbing other Accessed bit users such as the reclamation logic, the implementation adjusts the ``PG_Idle`` and ``PG_Young`` appropriately, as same to the 'Idle Page Tracking'.

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

mm/damon.c +8 -0

+                       clear_page_idle(pte_page(*pte));
+                       set_page_young(pte_page(*pte));
+               }
+               *pte = pte_mkold(*pte);
+               pte_unmap_unlock(pte, ptl);
+               return;
+       }
+

Quoted 60 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. To avoid disturbing other Accessed bit users such as the reclamation logic, the implementation adjusts the ``PG_Idle`` and ``PG_Young`` appropriately, as same to the 'Idle Page Tracking'.

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

[snip]

mm/damon.c static unsigned long damon_region_sz_limit(struct damon_ctx *ctx) · line 552

Quoted 12 lines

mm/damon.c +12 -0

+
+static void damon_mkold(struct mm_struct *mm, unsigned long addr)
+{
+       pte_t *pte = NULL;
+       pmd_t *pmd = NULL;
+       spinlock_t *ptl;
+
+       if (follow_pte_pmd(mm, addr, NULL, &pte, &pmd, &ptl))
+               return;
+
+       if (pte) {
+               if (pte_young(*pte)) {

Any reason for skipping mmu_notifier_clear_young()? Why exclude VMs as DAMON's target applications?

Quoted 9 lines

mm/damon.c +8 -0

+                       clear_page_idle(pte_page(*pte));
+                       set_page_young(pte_page(*pte));
+               }
+               *pte = pte_mkold(*pte);
+               pte_unmap_unlock(pte, ptl);
+               return;
+       }
+

Quoted 62 lines · On Thu, 16 Jul 2020 17:46:54 -0700 Shakeel Butt <[email protected]> wrote:

Quoted 60 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. To avoid disturbing other Accessed bit users such as the reclamation logic, the implementation adjusts the ``PG_Idle`` and ``PG_Young`` appropriately, as same to the 'Idle Page Tracking'.

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

[snip]

Quoted 15 lines

mm/damon.c static unsigned long damon_region_sz_limit(struct damon_ctx *ctx) · line 552

Quoted 12 lines

mm/damon.c +12 -0

+
+static void damon_mkold(struct mm_struct *mm, unsigned long addr)
+{
+       pte_t *pte = NULL;
+       pmd_t *pmd = NULL;
+       spinlock_t *ptl;
+
+       if (follow_pte_pmd(mm, addr, NULL, &pte, &pmd, &ptl))
+               return;
+
+       if (pte) {
+               if (pte_young(*pte)) {

Any reason for skipping mmu_notifier_clear_young()? Why exclude VMs as DAMON's target applications?

Obviously my mistake, thank you for pointing this! I will add the function call in the next spin.

Quoted 81 lines · SeongJae Park

Quoted 77 lines · On Thu, 16 Jul 2020 17:46:54 -0700 Shakeel Butt <[email protected]> wrote:

Quoted 60 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. To avoid disturbing other Accessed bit users such as the reclamation logic, the implementation adjusts the ``PG_Idle`` and ``PG_Young`` appropriately, as same to the 'Idle Page Tracking'.

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

[snip]

mm/damon.c static unsigned long damon_region_sz_limit(struct damon_ctx *ctx) · line 552

Quoted 12 lines

mm/damon.c +12 -0

+
+static void damon_mkold(struct mm_struct *mm, unsigned long addr)
+{
+       pte_t *pte = NULL;
+       pmd_t *pmd = NULL;
+       spinlock_t *ptl;
+
+       if (follow_pte_pmd(mm, addr, NULL, &pte, &pmd, &ptl))
+               return;
+
+       if (pte) {
+               if (pte_young(*pte)) {

Any reason for skipping mmu_notifier_clear_young()? Why exclude VMs as DAMON's target applications?

Quoted 3 lines

Obviously my mistake, thank you for pointing this! I will add the function call in the next spin.

Similarly mmu_notifier_test_young() for the damon_young().

BTW I think we can combine ctx->prepare_access_checks() and ctx->check_accesses() into one i.e. get the young state for the previous cycle and mkold for the next cycle in a single step.

I am wondering if there is any advantage to having "Page Idle Tracking" beside DAMON. I think we can make them mutually exclusive. Once we have established that I think DAMON can steal the two page flag bits from it and can make use of them. What do you think?

Quoted 82 lines · On Fri, 17 Jul 2020 08:17:09 -0700 Shakeel Butt <[email protected]> wrote:

Quoted 81 lines · SeongJae Park

Quoted 77 lines · On Thu, 16 Jul 2020 17:46:54 -0700 Shakeel Butt <[email protected]> wrote:

Quoted 60 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. To avoid disturbing other Accessed bit users such as the reclamation logic, the implementation adjusts the ``PG_Idle`` and ``PG_Young`` appropriately, as same to the 'Idle Page Tracking'.

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

[snip]

mm/damon.c static unsigned long damon_region_sz_limit(struct damon_ctx *ctx) · line 552

Quoted 12 lines

mm/damon.c +12 -0

+
+static void damon_mkold(struct mm_struct *mm, unsigned long addr)
+{
+       pte_t *pte = NULL;
+       pmd_t *pmd = NULL;
+       spinlock_t *ptl;
+
+       if (follow_pte_pmd(mm, addr, NULL, &pte, &pmd, &ptl))
+               return;
+
+       if (pte) {
+               if (pte_young(*pte)) {

Any reason for skipping mmu_notifier_clear_young()? Why exclude VMs as DAMON's target applications?

Quoted 5 lines

Quoted 3 lines

Obviously my mistake, thank you for pointing this! I will add the function call in the next spin.

Similarly mmu_notifier_test_young() for the damon_young().

Yes, indeed. Thanks for pointing this, either :)

Quoted 3 lines

BTW I think we can combine ctx->prepare_access_checks() and ctx->check_accesses() into one i.e. get the young state for the previous cycle and mkold for the next cycle in a single step.

Yes, we could. But, I'm unsure what is the advantage of doing that. First of all, if the combined implementation is required, peopld could simply implement the two logics in the combined way in one of the callbacks and leave the other one blank. Also, I'm worrying if combining those could make the code a little bit hard to read. IMHO, I think separating those makes the 'kdamond_fn()' code little bit easier to read. Actually, I started from the combined approach but separated the two logics since v7 after Jonathan's comment[1].

[1] https://lore.kernel.org/linux-mm/[email protected]/

Quoted 1 line

Quoted 4 lines

I am wondering if there is any advantage to having "Page Idle Tracking" beside DAMON. I think we can make them mutually exclusive. Once we have established that I think DAMON can steal the two page flag bits from it and can make use of them. What do you think?

Again, yes, I think we could. But I don't see clear advantage of it for now.

Quoted 115 lines · SeongJae Park

Quoted 82 lines · On Fri, 17 Jul 2020 08:17:09 -0700 Shakeel Butt <[email protected]> wrote:

Quoted 81 lines · SeongJae Park

Quoted 77 lines · On Thu, 16 Jul 2020 17:46:54 -0700 Shakeel Butt <[email protected]> wrote:

Quoted 60 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. To avoid disturbing other Accessed bit users such as the reclamation logic, the implementation adjusts the ``PG_Idle`` and ``PG_Young`` appropriately, as same to the 'Idle Page Tracking'.

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

[snip]

mm/damon.c static unsigned long damon_region_sz_limit(struct damon_ctx *ctx) · line 552

Quoted 12 lines

mm/damon.c +12 -0

+
+static void damon_mkold(struct mm_struct *mm, unsigned long addr)
+{
+       pte_t *pte = NULL;
+       pmd_t *pmd = NULL;
+       spinlock_t *ptl;
+
+       if (follow_pte_pmd(mm, addr, NULL, &pte, &pmd, &ptl))
+               return;
+
+       if (pte) {
+               if (pte_young(*pte)) {

Any reason for skipping mmu_notifier_clear_young()? Why exclude VMs as DAMON's target applications?

Quoted 5 lines

Quoted 3 lines

Obviously my mistake, thank you for pointing this! I will add the function call in the next spin.

Similarly mmu_notifier_test_young() for the damon_young().

Yes, indeed. Thanks for pointing this, either :)

Quoted 3 lines

BTW I think we can combine ctx->prepare_access_checks() and ctx->check_accesses() into one i.e. get the young state for the previous cycle and mkold for the next cycle in a single step.

Yes, we could. But, I'm unsure what is the advantage of doing that. First of all, if the combined implementation is required, peopld could simply implement the two logics in the combined way in one of the callbacks and leave the other one blank. Also, I'm worrying if combining those could make the code a little bit hard to read. IMHO, I think separating those makes the 'kdamond_fn()' code little bit easier to read. Actually, I started from the combined approach but separated the two logics since v7 after Jonathan's comment[1].

[1] https://lore.kernel.org/linux-mm/[email protected]/

Quoted 5 lines

I am wondering if there is any advantage to having "Page Idle Tracking" beside DAMON. I think we can make them mutually exclusive. Once we have established that I think DAMON can steal the two page flag bits from it and can make use of them. What do you think?

Quoted 3 lines

Again, yes, I think we could. But I don't see clear advantage of it for now.

Hmm, I will think more about it. Somehow I feel if we want to monitor at the page sized region granularity then this will be really helpful. Anyways, it needs more brainstorming.

BTW I am still going over the series and my humble request would be to wait till I have gone through the series completely and provided the feedback then you can send the next version after incorporating the feedback.

Shakeel

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. To avoid disturbing other Accessed bit users such as the reclamation logic, the implementation adjusts the ``PG_Idle`` and ``PG_Young`` appropriately, as same to the 'Idle Page Tracking'.

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 |   6 +
 mm/damon.c            | 474 ++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 480 insertions(+)

include/linux/damon.h +6 -0

index 3c0b92a679e8..310d36d123b3 100644
@@ -144,6 +144,12 @@ struct damon_ctx {
 	void (*aggregate_cb)(struct damon_ctx *context);
 };
 
+/* Reference callback implementations for virtual memory */
+void kdamond_init_vm_regions(struct damon_ctx *ctx);
+void kdamond_update_vm_regions(struct damon_ctx *ctx);
+void kdamond_prepare_vm_access_checks(struct damon_ctx *ctx);
+unsigned int kdamond_check_vm_accesses(struct damon_ctx *ctx);
+
 int damon_set_pids(struct damon_ctx *ctx, int *pids, ssize_t nr_pids);
 int damon_set_attrs(struct damon_ctx *ctx, unsigned long sample_int,
 		unsigned long aggr_int, unsigned long regions_update_int,

mm/damon.c +346 -0

index b844924b9fdb..386780739007 100644
@@ -9,6 +9,9 @@
  * This file is constructed in below parts.
  *
  * - Functions and macros for DAMON data structures
+ * - Functions for the initial monitoring target regions construction
+ * - Functions for the dynamic monitoring target regions update
+ * - Functions for the access checking of the regions
  * - Functions for DAMON core logics and features
  * - Functions for the DAMON programming interface
  * - Functions for the module loading/unloading

@@ -196,6 +199,477 @@ static unsigned long damon_region_sz_limit(struct damon_ctx *ctx)
 	return sz;
 }
 
+/*
+ * Get the mm_struct of the given task
+ *
+ * Caller _must_ 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;
+}
+
+/*
+ * Functions for the initial monitoring target regions construction
+ */
+
+/*
+ * 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 *n = NULL, *next;
+	unsigned long start;
+
+	if (!r || !nr_pieces)
+		return -EINVAL;
+
+	orig_end = r->ar.end;
+	sz_orig = r->ar.end - r->ar.start;
+	sz_piece = ALIGN_DOWN(sz_orig / nr_pieces, MIN_REGION);
+
+	if (!sz_piece)
+		return -EINVAL;
+
+	r->ar.end = r->ar.start + sz_piece;
+	next = damon_next_region(r);
+	for (start = r->ar.end; start + sz_piece <= orig_end;
+			start += sz_piece) {
+		n = damon_new_region(start, start + sz_piece);
+		if (!n)
+			return -ENOMEM;
+		damon_insert_region(n, r, next);
+		r = n;
+	}
+	/* complement last region for possible rounding error */
+	if (n)
+		n->ar.end = orig_end;
+
+	return 0;
+}
+
+static unsigned long sz_range(struct damon_addr_range *r)
+{
+	return r->end - r->start;
+}
+
+static void swap_ranges(struct damon_addr_range *r1,
+			struct damon_addr_range *r2)
+{
+	struct damon_addr_range tmp;
+
+	tmp = *r1;
+	*r1 = *r2;
+	*r2 = tmp;
+}
+
+/*
+ * Find three regions separated by two biggest unmapped regions
+ *
+ * vma		the head vma of the target address space
+ * regions	an array of three address ranges 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_vm_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 damon_addr_range regions[3])
+{
+	struct damon_addr_range gap = {0}, first_gap = {0}, second_gap = {0};
+	struct vm_area_struct *last_vma = NULL;
+	unsigned long start = 0;
+	struct rb_root rbroot;
+
+	/* Find two biggest gaps so that first_gap > second_gap > others */
+	for (; vma; vma = vma->vm_next) {
+		if (!last_vma) {
+			start = vma->vm_start;
+			goto next;
+		}
+
+		if (vma->rb_subtree_gap <= sz_range(&second_gap)) {
+			rbroot.rb_node = &vma->vm_rb;
+			vma = rb_entry(rb_last(&rbroot),
+					struct vm_area_struct, vm_rb);
+			goto next;
+		}
+
+		gap.start = last_vma->vm_end;
+		gap.end = vma->vm_start;
+		if (sz_range(&gap) > sz_range(&second_gap)) {
+			swap_ranges(&gap, &second_gap);
+			if (sz_range(&second_gap) > sz_range(&first_gap))
+				swap_ranges(&second_gap, &first_gap);
+		}
+next:
+		last_vma = vma;
+	}
+
+	if (!sz_range(&second_gap) || !sz_range(&first_gap))
+		return -EINVAL;
+
+	/* Sort the two biggest gaps by address */
+	if (first_gap.start > second_gap.start)
+		swap_ranges(&first_gap, &second_gap);
+
+	/* Store the result */
+	regions[0].start = ALIGN(start, MIN_REGION);
+	regions[0].end = ALIGN(first_gap.start, MIN_REGION);
+	regions[1].start = ALIGN(first_gap.end, MIN_REGION);
+	regions[1].end = ALIGN(second_gap.start, MIN_REGION);
+	regions[2].start = ALIGN(second_gap.end, MIN_REGION);
+	regions[2].end = ALIGN(last_vma->vm_end, MIN_REGION);
+
+	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 damon_addr_range regions[3])
+{
+	struct mm_struct *mm;
+	int rc;
+
+	mm = damon_get_mm(t);
+	if (!mm)
+		return -EINVAL;
+
+	down_read(&mm->mmap_sem);
+	rc = damon_three_regions_in_vmas(mm->mmap, regions);
+	up_read(&mm->mmap_sem);
+
+	mmput(mm);
+	return rc;
+}
+
+/*
+ * 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 actually 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.  The adaptive regions adjustment mechanism will further help to deal
+ * with the noise by simply identifying the unmapped areas as a region that
+ * has no access.  Moreover, applying the real mappings that would have many
+ * unmapped areas inside will make the adaptive mechanism quite complex.  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, we convert 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.  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_vm_regions_of(struct damon_ctx *c, struct damon_task *t)
+{
+	struct damon_region *r;
+	struct damon_addr_range regions[3];
+	unsigned long sz = 0, nr_pieces;
+	int i;
+
+	if (damon_three_regions_of(t, regions)) {
+		pr_err("Failed to get three regions of task %d\n", t->pid);
+		return;
+	}
+
+	for (i = 0; i < 3; i++)
+		sz += regions[i].end - regions[i].start;
+	if (c->min_nr_regions)
+		sz /= c->min_nr_regions;
+	if (sz < MIN_REGION)
+		sz = MIN_REGION;
+
+	/* Set the initial three regions of the task */
+	for (i = 0; i < 3; i++) {
+		r = damon_new_region(regions[i].start, regions[i].end);
+		if (!r) {
+			pr_err("%d'th init region creation failed\n", i);
+			return;
+		}
+		damon_add_region(r, t);
+
+		nr_pieces = (regions[i].end - regions[i].start) / sz;
+		damon_split_region_evenly(c, r, nr_pieces);
+	}
+}
+
+/* Initialize '->regions_list' of every task */
+void kdamond_init_vm_regions(struct damon_ctx *ctx)
+{
+	struct damon_task *t;
+
+	damon_for_each_task(t, ctx) {
+		/* the user may set the target regions as they want */
+		if (!nr_damon_regions(t))
+			damon_init_vm_regions_of(ctx, t);
+	}
+}
+
+/*
+ * Functions for the dynamic monitoring target regions update
+ */
+
+/*
+ * Check whether a region is intersecting an address range
+ *
+ * Returns true if it is.
+ */
+static bool damon_intersect(struct damon_region *r, struct damon_addr_range *re)
+{
+	return !(r->ar.end <= re->start || re->end <= r->ar.start);
+}
+
+/*
+ * Update damon regions for the three big regions of the given task
+ *
+ * t		the given task
+ * bregions	the three big regions of the task
+ */
+static void damon_apply_three_regions(struct damon_ctx *ctx,
+		struct damon_task *t, struct damon_addr_range bregions[3])
+{
+	struct damon_region *r, *next;
+	unsigned int i = 0;
+
+	/* Remove regions which are not in the three big regions now */
+	damon_for_each_region_safe(r, next, t) {
+		for (i = 0; i < 3; i++) {
+			if (damon_intersect(r, &bregions[i]))
+				break;
+		}
+		if (i == 3)
+			damon_destroy_region(r);
+	}
+
+	/* Adjust intersecting regions to fit with the three big regions */
+	for (i = 0; i < 3; i++) {
+		struct damon_region *first = NULL, *last;
+		struct damon_region *newr;
+		struct damon_addr_range *br;
+
+		br = &bregions[i];
+		/* Get the first and last regions which intersects with br */
+		damon_for_each_region(r, t) {
+			if (damon_intersect(r, br)) {
+				if (!first)
+					first = r;
+				last = r;
+			}
+			if (r->ar.start >= br->end)
+				break;
+		}
+		if (!first) {
+			/* no damon_region intersects with this big region */
+			newr = damon_new_region(
+					ALIGN_DOWN(br->start, MIN_REGION),
+					ALIGN(br->end, MIN_REGION));
+			if (!newr)
+				continue;
+			damon_insert_region(newr, damon_prev_region(r), r);
+		} else {
+			first->ar.start = ALIGN_DOWN(br->start, MIN_REGION);
+			last->ar.end = ALIGN(br->end, MIN_REGION);
+		}
+	}
+}
+
+/*
+ * Update regions for current memory mappings
+ */
+void kdamond_update_vm_regions(struct damon_ctx *ctx)
+{
+	struct damon_addr_range three_regions[3];
+	struct damon_task *t;
+
+	damon_for_each_task(t, ctx) {
+		if (damon_three_regions_of(t, three_regions))
+			continue;
+		damon_apply_three_regions(ctx, t, three_regions);
+	}
+}
+
+/*
+ * Functions for the access checking of the regions
+ */
+
+static void damon_mkold(struct mm_struct *mm, unsigned long addr)
+{
+	pte_t *pte = NULL;

mm/damon.c +118 -0

+		}
+		*pte = pte_mkold(*pte);
+		pte_unmap_unlock(pte, ptl);
+		return;
+	}
+
+#ifdef CONFIG_TRANSPARENT_HUGEPAGE
+	if (pmd_young(*pmd)) {
+		clear_page_idle(pmd_page(*pmd));
+		set_page_young(pmd_page(*pmd));
+	}
+	*pmd = pmd_mkold(*pmd);
+	spin_unlock(ptl);
+#endif /* CONFIG_TRANSPARENT_HUGEPAGE */
+}
+
+static void damon_prepare_vm_access_check(struct damon_ctx *ctx,
+			struct mm_struct *mm, struct damon_region *r)
+{
+	r->sampling_addr = damon_rand(r->ar.start, r->ar.end);
+
+	damon_mkold(mm, r->sampling_addr);
+}
+
+void kdamond_prepare_vm_access_checks(struct damon_ctx *ctx)
+{
+	struct damon_task *t;
+	struct mm_struct *mm;
+	struct damon_region *r;
+
+	damon_for_each_task(t, ctx) {
+		mm = damon_get_mm(t);
+		if (!mm)
+			continue;
+		damon_for_each_region(r, t)
+			damon_prepare_vm_access_check(ctx, mm, r);
+		mmput(mm);
+	}
+}
+
+static bool damon_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);
+		pte_unmap_unlock(pte, ptl);
+		return young;
+	}
+
+#ifdef CONFIG_TRANSPARENT_HUGEPAGE
+	young = pmd_young(*pmd);
+	spin_unlock(ptl);
+	*page_sz = ((1UL) << HPAGE_PMD_SHIFT);
+#endif	/* CONFIG_TRANSPARENT_HUGEPAGE */
+
+	return young;
+}
+
+/*
+ * Check whether the region was accessed after the last preparation
+ *
+ * mm	'mm_struct' for the given virtual address space
+ * r	the region to be checked
+ */
+static void damon_check_vm_access(struct damon_ctx *ctx,
+			       struct mm_struct *mm, struct damon_region *r)
+{
+	static struct mm_struct *last_mm;
+	static unsigned long last_addr;
+	static unsigned long last_page_sz = PAGE_SIZE;
+	static bool last_accessed;
+
+	/* If the region is in the last checked page, reuse the result */
+	if (mm == last_mm && (ALIGN_DOWN(last_addr, last_page_sz) ==
+				ALIGN_DOWN(r->sampling_addr, last_page_sz))) {
+		if (last_accessed)
+			r->nr_accesses++;
+		return;
+	}
+
+	last_accessed = damon_young(mm, r->sampling_addr, &last_page_sz);
+	if (last_accessed)
+		r->nr_accesses++;
+
+	last_mm = mm;
+	last_addr = r->sampling_addr;
+}
+
+unsigned int kdamond_check_vm_accesses(struct damon_ctx *ctx)
+{
+	struct damon_task *t;
+	struct mm_struct *mm;
+	struct damon_region *r;
+	unsigned int max_nr_accesses = 0;
+
+	damon_for_each_task(t, ctx) {
+		mm = damon_get_mm(t);
+		if (!mm)
+			continue;
+		damon_for_each_region(r, t) {
+			damon_check_vm_access(ctx, mm, r);
+			max_nr_accesses = max(r->nr_accesses, max_nr_accesses);
+		}
+		mmput(mm);
+	}
+
+	return max_nr_accesses;
+}
+
 /*
  * Functions for DAMON core logics and features
  */

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

Quoted 5 lines

mm/damon.c +0 -0

index b844924b9fdb..386780739007 100644
@@ -9,6 +9,9 @@

Quoted 13 lines

mm/damon.c +13 -0

+/*
+ * Functions for the access checking of the regions
+ */
+
+static void damon_mkold(struct mm_struct *mm, unsigned long addr)
+{
+	pte_t *pte = NULL;
+	pmd_t *pmd = NULL;
+	spinlock_t *ptl;
+
+	if (follow_pte_pmd(mm, addr, NULL, &pte, &pmd, &ptl))
+		return;
+

mm/damon.c static unsigned long damon_region_sz_limit(struct damon_ctx *ctx) · line 554

Quoted 4 lines

mm/damon.c +4 -0

+	if (pte) {
+		if (pte_young(*pte)) {
+			clear_page_idle(pte_page(*pte));
+			set_page_young(pte_page(*pte));

While this compiles without support for PG_young and PG_idle, I assume it won't work well because it'd clear pte.young without setting PG_young. And this would mess with vmscan.

So this code appears to depend on PG_young and PG_idle, which are currently only available via CONFIG_IDLE_PAGE_TRACKING. DAMON could depend on CONFIG_IDLE_PAGE_TRACKING via Kconfig. But I assume that CONFIG_IDLE_PAGE_TRACKING and CONFIG_DAMON cannot be concurrently used because they'll stomp on each other's use of pte.young, PG_young, PG_idle.
So I suspect we want:
1. CONFIG_DAMON to depend on !CONFIG_IDLE_PAGE_TRACKING and vise-versa.
2. PG_young,PG_idle and related helpers to depend on CONFIG_DAMON||CONFIG_IDLE_PAGE_TRACKING.

Quoted 17 lines

mm/damon.c +16 -0

+		}
+		*pte = pte_mkold(*pte);
+		pte_unmap_unlock(pte, ptl);
+		return;
+	}
+
+#ifdef CONFIG_TRANSPARENT_HUGEPAGE
+	if (pmd_young(*pmd)) {
+		clear_page_idle(pmd_page(*pmd));
+		set_page_young(pmd_page(*pmd));
+	}
+	*pmd = pmd_mkold(*pmd);
+	spin_unlock(ptl);
+#endif /* CONFIG_TRANSPARENT_HUGEPAGE */
+}
+

Quoted 9 lines · On Mon, 27 Jul 2020 00:34:54 -0700 Greg Thelen <[email protected]> wrote:

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

[...]

Quoted 5 lines

Quoted 5 lines

mm/damon.c +0 -0

index b844924b9fdb..386780739007 100644
@@ -9,6 +9,9 @@

[...]

Quoted 13 lines

Quoted 13 lines

mm/damon.c +13 -0

+/*
+ * Functions for the access checking of the regions
+ */
+
+static void damon_mkold(struct mm_struct *mm, unsigned long addr)
+{
+   pte_t *pte = NULL;
+   pmd_t *pmd = NULL;
+   spinlock_t *ptl;
+
+   if (follow_pte_pmd(mm, addr, NULL, &pte, &pmd, &ptl))
+           return;
+

Quoted 8 lines

mm/damon.c static unsigned long damon_region_sz_limit(struct damon_ctx *ctx) · line 554

Quoted 4 lines

mm/damon.c +4 -0

+   if (pte) {
+           if (pte_young(*pte)) {
+                   clear_page_idle(pte_page(*pte));
+                   set_page_young(pte_page(*pte));

While this compiles without support for PG_young and PG_idle, I assume it won't work well because it'd clear pte.young without setting PG_young. And this would mess with vmscan.

You're right, thanks for catching this up! This definitely need to be fixed in the next spin.

Quoted 11 lines

So this code appears to depend on PG_young and PG_idle, which are currently only available via CONFIG_IDLE_PAGE_TRACKING. DAMON could depend on CONFIG_IDLE_PAGE_TRACKING via Kconfig. But I assume that CONFIG_IDLE_PAGE_TRACKING and CONFIG_DAMON cannot be concurrently used because they'll stomp on each other's use of pte.young, PG_young, PG_idle.
So I suspect we want:
1. CONFIG_DAMON to depend on !CONFIG_IDLE_PAGE_TRACKING and vise-versa.
2. PG_young,PG_idle and related helpers to depend on CONFIG_DAMON||CONFIG_IDLE_PAGE_TRACKING.

Awesome insights and suggestions, thanks!

I would like to note that DAMON could be interfered by IDLE_PAGE_TRACKING and vmscan, but not vice versa, as DAMON respects PG_idle and PG_young. This design came from the weak goal of DAMON. DAMON aims to provide not perfect monitoring but only best effort accuracy that would be sufficient for performance-centric DRAM level memory management. So, at that time, I thought being interfered by IDLE_PAGE_TRACKING and the reclaim logic would not be a real problem but letting IDLE_PAGE_TRACKING coexist is somehow beneficial. That said, I couldn't find a real benefit of the coexistance yet, and the problem of being interference now seems bigger as we will support more cases including the page granularity.

Maybe we could make IDLE_PAGE_TRACKING and DAMON coexist but mutual exclusive in runtime, if the beneficial of coexistance turns out big. However, I would like to make it simple first and optimize the case later if real requirement found.

Quoted 69 lines · SeongJae Park

Quoted 9 lines · On Mon, 27 Jul 2020 00:34:54 -0700 Greg Thelen <[email protected]> wrote:

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

[...]

Quoted 5 lines

Quoted 5 lines

mm/damon.c +0 -0

index b844924b9fdb..386780739007 100644
@@ -9,6 +9,9 @@

[...]

Quoted 13 lines

Quoted 13 lines

mm/damon.c +13 -0

+/*
+ * Functions for the access checking of the regions
+ */
+
+static void damon_mkold(struct mm_struct *mm, unsigned long addr)
+{
+   pte_t *pte = NULL;
+   pmd_t *pmd = NULL;
+   spinlock_t *ptl;
+
+   if (follow_pte_pmd(mm, addr, NULL, &pte, &pmd, &ptl))
+           return;
+

Quoted 8 lines

mm/damon.c static unsigned long damon_region_sz_limit(struct damon_ctx *ctx) · line 554

Quoted 4 lines

mm/damon.c +4 -0

+   if (pte) {
+           if (pte_young(*pte)) {
+                   clear_page_idle(pte_page(*pte));
+                   set_page_young(pte_page(*pte));

While this compiles without support for PG_young and PG_idle, I assume it won't work well because it'd clear pte.young without setting PG_young. And this would mess with vmscan.

You're right, thanks for catching this up! This definitely need to be fixed in the next spin.

Quoted 11 lines

So this code appears to depend on PG_young and PG_idle, which are currently only available via CONFIG_IDLE_PAGE_TRACKING. DAMON could depend on CONFIG_IDLE_PAGE_TRACKING via Kconfig. But I assume that CONFIG_IDLE_PAGE_TRACKING and CONFIG_DAMON cannot be concurrently used because they'll stomp on each other's use of pte.young, PG_young, PG_idle.
So I suspect we want:
1. CONFIG_DAMON to depend on !CONFIG_IDLE_PAGE_TRACKING and vise-versa.
2. PG_young,PG_idle and related helpers to depend on CONFIG_DAMON||CONFIG_IDLE_PAGE_TRACKING.

Awesome insights and suggestions, thanks!

I would like to note that DAMON could be interfered by IDLE_PAGE_TRACKING and vmscan, but not vice versa, as DAMON respects PG_idle and PG_young. This design came from the weak goal of DAMON. DAMON aims to provide not perfect monitoring but only best effort accuracy that would be sufficient for performance-centric DRAM level memory management. So, at that time, I thought being interfered by IDLE_PAGE_TRACKING and the reclaim logic would not be a real problem but letting IDLE_PAGE_TRACKING coexist is somehow beneficial. That said, I couldn't find a real benefit of the coexistance yet, and the problem of being interference now seems bigger as we will support more cases including the page granularity.

Quoted 4 lines

Maybe we could make IDLE_PAGE_TRACKING and DAMON coexist but mutual exclusive in runtime, if the beneficial of coexistance turns out big. However, I would like to make it simple first and optimize the case later if real requirement found.

If you are planning to have support for tracking at page granularity and physical memory monitoring in DAMON then I don't see any benefit of coexistence of DAMON with IDLE_PAGE_TRACKING. Though I will not push you to go that route if the code with coexistence is simple enough.

From: SeongJae Park <[email protected]>

This commit implements a debugfs interface for DAMON. It works for the virtual address spaces monitoring.

mm/damon.c +19 -0

+/*
+ * 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 int *str_to_pids(const char *str, ssize_t len, ssize_t *nr_pids)
+{
+	int *pids;
+	const int max_nr_pids = 32;
+	int pid;
+	int pos = 0, parsed, ret;
+
+	*nr_pids = 0;
+	pids = kmalloc_array(max_nr_pids, sizeof(pid), GFP_KERNEL);
+	if (!pids)
+		return NULL;
+	while (*nr_pids < max_nr_pids && pos < len) {
+		ret = sscanf(&str[pos], "%d%n", &pid, &parsed);

From: SeongJae Park <[email protected]>

This commit adds documents for DAMON under Documentation/admin-guide/mm/damon/ and Documentation/vm/damon/.

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

---
 Documentation/admin-guide/mm/damon/guide.rst | 157 ++++++++++
 Documentation/admin-guide/mm/damon/index.rst |  15 +
 Documentation/admin-guide/mm/damon/plans.rst |  29 ++
 Documentation/admin-guide/mm/damon/start.rst |  98 ++++++
 Documentation/admin-guide/mm/damon/usage.rst | 298 +++++++++++++++++++
 Documentation/admin-guide/mm/index.rst       |   1 +
 Documentation/vm/damon/api.rst               |  20 ++
 Documentation/vm/damon/eval.rst              | 222 ++++++++++++++
 Documentation/vm/damon/faq.rst               |  59 ++++
 Documentation/vm/damon/index.rst             |  32 ++
 Documentation/vm/damon/mechanisms.rst        | 165 ++++++++++
 Documentation/vm/index.rst                   |   1 +
 12 files changed, 1097 insertions(+)
 create mode 100644 Documentation/admin-guide/mm/damon/guide.rst
 create mode 100644 Documentation/admin-guide/mm/damon/index.rst
 create mode 100644 Documentation/admin-guide/mm/damon/plans.rst
 create mode 100644 Documentation/admin-guide/mm/damon/start.rst
 create mode 100644 Documentation/admin-guide/mm/damon/usage.rst
 create mode 100644 Documentation/vm/damon/api.rst
 create mode 100644 Documentation/vm/damon/eval.rst
 create mode 100644 Documentation/vm/damon/faq.rst
 create mode 100644 Documentation/vm/damon/index.rst
 create mode 100644 Documentation/vm/damon/mechanisms.rst

Documentation/admin-guide/mm/damon/guide.rst new file +157 -0

new file mode 100644
index 000000000000..c51fb843efaa
@@ -0,0 +1,157 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+==================
+Optimization Guide
+==================
+
+This document helps you estimating the amount of benefit that you could get
+from DAMON-based optimizations, and describes how you could achieve it.  You
+are assumed to already read :doc:`start`.
+
+
+Check The Signs
+===============
+
+No optimization can provide same extent of benefit to every case.  Therefore
+you should first guess how much improvements you could get using DAMON.  If
+some of below conditions match your situation, you could consider using DAMON.
+
+- *Low IPC and High Cache Miss Ratios.*  Low IPC means most of the CPU time is
+  spent waiting for the completion of time-consuming operations such as memory
+  access, while high cache miss ratios mean the caches don't help it well.
+  DAMON is not for cache level optimization, but DRAM level.  However,
+  improving DRAM management will also help this case by reducing the memory
+  operation latency.
+- *Memory Over-commitment and Unknown Users.*  If you are doing memory
+  overcommitment and you cannot control every user of your system, a memory
+  bank run could happen at any time.  You can estimate when it will happen
+  based on DAMON's monitoring results and act earlier to avoid or deal better
+  with the crisis.
+- *Frequent Memory Pressure.*  Frequent memory pressure means your system has
+  wrong configurations or memory hogs.  DAMON will help you find the right
+  configuration and/or the criminals.
+- *Heterogeneous Memory System.*  If your system is utilizing memory devices
+  that placed between DRAM and traditional hard disks, such as non-volatile
+  memory or fast SSDs, DAMON could help you utilizing the devices more
+  efficiently.
+
+
+Profile
+=======
+
+If you found some positive signals, you could start by profiling your workloads
+using DAMON.  Find major workloads on your systems and analyze their data
+access pattern to find something wrong or can be improved.  The DAMON user
+space tool (``damo``) will be useful for this.
+
+We recommend you to start from working set size distribution check using ``damo
+report wss``.  If the distribution is ununiform or quite different from what
+you estimated, you could consider `Memory Configuration`_ optimization.
+
+Then, review the overall access pattern in heatmap form using ``damo report
+heats``.  If it shows a simple pattern consists of a small number of memory
+regions having high contrast of access temperature, you could consider manual
+`Program Modification`_.
+
+If you still want to absorb more benefits, you should develop `Personalized
+DAMON Application`_ for your special case.
+
+You don't need to take only one approach among the above plans, but you could
+use multiple of the above approaches to maximize the benefit.
+
+
+Optimize
+========
+
+If the profiling result also says it's worth trying some optimization, you
+could consider below approaches.  Note that some of the below approaches assume
+that your systems are configured with swap devices or other types of auxiliary
+memory so that you don't strictly required to accommodate the whole working set
+in the main memory.  Most of the detailed optimization should be made on your
+concrete understanding of your memory devices.
+
+
+Memory Configuration
+--------------------
+
+No more no less, DRAM should be large enough to accommodate only important
+working sets, because DRAM is highly performance critical but expensive and
+heavily consumes the power.  However, knowing the size of the real important
+working sets is difficult.  As a consequence, people usually equips
+unnecessarily large or too small DRAM.  Many problems stem from such wrong
+configurations.
+
+Using the working set size distribution report provided by ``damo report wss``,
+you can know the appropriate DRAM size for you.  For example, roughly speaking,
+if you worry about only 95 percentile latency, you don't need to equip DRAM of
+a size larger than 95 percentile working set size.
+
+Let's see a real example.  This `page
+<https://damonitor.github.io/doc/html/v17/admin-guide/mm/damon/guide.html#memory-configuration>`_
+shows the heatmap and the working set size distributions/changes of
+``freqmine`` workload in PARSEC3 benchmark suite.  The working set size spikes
+up to 180 MiB, but keeps smaller than 50 MiB for more than 95% of the time.
+Even though you give only 50 MiB of memory space to the workload, it will work
+well for 95% of the time.  Meanwhile, you can save the 130 MiB of memory space.
+
+
+Program Modification
+--------------------
+
+If the data access pattern heatmap plotted by ``damo report heats`` is quite
+simple so that you can understand how the things are going in the workload with
+your human eye, you could manually optimize the memory management.
+
+For example, suppose that the workload has two big memory object but only one
+object is frequently accessed while the other one is only occasionally
+accessed.  Then, you could modify the program source code to keep the hot
+object in the main memory by invoking ``mlock()`` or ``madvise()`` with
+``MADV_WILLNEED``.  Or, you could proactively evict the cold object using
+``madvise()`` with ``MADV_COLD`` or ``MADV_PAGEOUT``.  Using both together
+would be also worthy.
+
+A research work [1]_ using the ``mlock()`` achieved up to 2.55x performance
+speedup.
+
+Let's see another realistic example access pattern for this kind of
+optimizations.  This `page
+<https://damonitor.github.io/doc/html/v17/admin-guide/mm/damon/guide.html#program-modification>`_
+shows the visualized access patterns of streamcluster workload in PARSEC3
+benchmark suite.  We can easily identify the 100 MiB sized hot object.
+
+
+Personalized DAMON Application
+------------------------------
+
+Above approaches will work well for many general cases, but would not enough
+for some special cases.
+
+If this is the case, it might be the time to forget the comfortable use of the
+user space tool and dive into the debugfs interface (refer to :doc:`usage` for
+the detail) of DAMON.  Using the interface, you can control the DAMON more
+flexibly.  Therefore, you can write your personalized DAMON application that
+controls the monitoring via the debugfs interface, analyzes the result, and
+applies complex optimizations itself.  Using this, you can make more creative
+and wise optimizations.
+
+If you are a kernel space programmer, writing kernel space DAMON applications
+using the API (refer to the :doc:`/vm/damon/api` for more detail) would be an
+option.
+
+
+Reference Practices
+===================
+
+Referencing previously done successful practices could help you getting the
+sense for this kind of optimizations.  There is an academic paper [1]_
+reporting the visualized access pattern and manual `Program
+Modification`_ results for a number of realistic workloads.  You can also get
+the visualized access patterns [3]_ [4]_ [5]_ and automated DAMON-based memory
+operations results for other realistic workloads that collected with latest
+version of DAMON [2]_ .
+
+.. [1] https://dl.acm.org/doi/10.1145/3366626.3368125
+.. [2] https://damonitor.github.io/test/result/perf/latest/html/
+.. [3] https://damonitor.github.io/test/result/visual/latest/rec.heatmap.1.png.html
+.. [4] https://damonitor.github.io/test/result/visual/latest/rec.wss_sz.png.html
+.. [5] https://damonitor.github.io/test/result/visual/latest/rec.wss_time.png.html

Documentation/admin-guide/mm/damon/index.rst new file +15 -0

new file mode 100644
index 000000000000..0baae7a5402b
@@ -0,0 +1,15 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+========================
+Monitoring Data Accesses
+========================
+
+:doc:`DAMON </vm/damon/index>` allows light-weight data access monitoring.
+Using this, users can analyze and optimize their systems.
+
+.. toctree::
+   :maxdepth: 2
+
+   start
+   guide
+   usage

Documentation/admin-guide/mm/damon/plans.rst new file +29 -0

new file mode 100644
index 000000000000..e3aa5ab96c29
@@ -0,0 +1,29 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+============
+Future Plans
+============
+
+DAMON is still on its first stage.  Below plans are still under development.
+
+
+Automate Data Access Monitoring-based Memory Operation Schemes Execution
+========================================================================
+
+The ultimate goal of DAMON is to be used as a building block for the data
+access pattern aware kernel memory management optimization.  It will make
+system just works efficiently.  However, some users having very special
+workloads will want to further do their own optimization.  DAMON will automate
+most of the tasks for such manual optimizations in near future.  Users will be
+required to only describe what kind of data access pattern-based operation
+schemes they want in a simple form.
+
+By applying a very simple scheme for THP promotion/demotion with a prototype
+implementation, DAMON reduced 60% of THP memory footprint overhead while
+preserving 50% of the THP performance benefit.  The detailed results can be
+seen on an external web page [1]_.
+
+Several RFC patchsets for this plan are available [2]_.
+
+.. [1] https://damonitor.github.io/test/result/perf/latest/html/
+.. [2] https://lore.kernel.org/linux-mm/[email protected]/

Documentation/admin-guide/mm/damon/start.rst new file +98 -0

new file mode 100644
index 000000000000..a6f04d966adc
@@ -0,0 +1,98 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+===============
+Getting Started
+===============
+
+This document briefly describes how you can use DAMON by demonstrating its
+default user space tool.  Please note that this document describes only a part
+of its features for brevity.  Please refer to :doc:`usage` for more details.
+
+
+TL; DR
+======
+
+Follow below 5 commands to monitor and visualize the access pattern of your
+workload. ::
+
+    $ git clone https://github.com/sjp38/linux -b damon/master
+    /* build the kernel with CONFIG_DAMON=y, install, reboot */
+    $ mount -t debugfs none /sys/kernel/debug/
+    $ cd linux/tools/damon
+    $ ./damo record $(pidof <your workload>)
+    $ ./damo report heats --heatmap access_pattern.png
+
+
+Prerequisites
+=============
+
+Kernel
+------
+
+You should first ensure your system is running on a kernel built with
+``CONFIG_DAMON``.  If the value is set to ``m``, load the module first::
+
+    # modprobe damon
+
+
+User Space Tool
+---------------
+
+For the demonstration, we will use the default user space tool for DAMON,
+called DAMON Operator (DAMO).  It is located at ``tools/damon/damo`` of the
+kernel source tree.  For brevity, below examples assume you set ``$PATH`` to
+point it.  It's not mandatory, though.
+
+Because DAMO is using the debugfs interface (refer to :doc:`usage` for the
+detail) of DAMON, you should ensure debugfs is mounted.  Mount it manually as
+below::
+
+    # mount -t debugfs none /sys/kernel/debug/
+
+or append below line to your ``/etc/fstab`` file so that your system can
+automatically mount debugfs from next booting::
+
+    debugfs /sys/kernel/debug debugfs defaults 0 0
+
+
+Recording Data Access Patterns
+==============================
+
+Below commands record memory access pattern of a program and save the
+monitoring results in a file. ::
+
+    $ git clone https://github.com/sjp38/masim
+    $ cd masim; make; ./masim ./configs/zigzag.cfg &
+    $ sudo damo record -o damon.data $(pidof masim)
+
+The first two lines of the commands get an artificial memory access generator
+program and runs it in the background.  It will repeatedly access two 100 MiB
+sized memory regions one by one.  You can substitute this with your real
+workload.  The last line asks ``damo`` to record the access pattern in
+``damon.data`` file.
+
+
+Visualizing Recorded Patterns
+=============================
+
+Below three commands visualize the recorded access patterns into three
+image files. ::
+
+    $ damo report heats --heatmap access_pattern_heatmap.png
+    $ damo report wss --range 0 101 1 --plot wss_dist.png
+    $ damo report wss --range 0 101 1 --sortby time --plot wss_chron_change.png
+
+- ``access_pattern_heatmap.png`` will show the data access pattern in a
+  heatmap, which shows when (x-axis) what memory region (y-axis) is how
+  frequently accessed (color).
+- ``wss_dist.png`` will show the distribution of the working set size.
+- ``wss_chron_change.png`` will show how the working set size has
+  chronologically changed.
+
+You can show the images in a web page [1]_ .  Those made with other realistic
+workloads are also available [2]_ [3]_ [4]_.
+
+.. [1] https://damonitor.github.io/doc/html/v17/admin-guide/mm/damon/start.html#visualizing-recorded-patterns
+.. [2] https://damonitor.github.io/test/result/visual/latest/rec.heatmap.1.png.html
+.. [3] https://damonitor.github.io/test/result/visual/latest/rec.wss_sz.png.html
+.. [4] https://damonitor.github.io/test/result/visual/latest/rec.wss_time.png.html

Documentation/admin-guide/mm/damon/usage.rst new file +22 -0

new file mode 100644
index 000000000000..971e6b06b4ac
@@ -0,0 +1,298 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+===============
+Detailed Usages
+===============
+
+DAMON provides below three interfaces for different users.
+
+- *DAMON user space tool.*
+  This is for privileged people such as system administrators who want a
+  just-working human-friendly interface.  Using this, users can use the DAMON’s
+  major features in a human-friendly way.  It may not be highly tuned for
+  special cases, though.  It supports only virtual address spaces monitoring.
+- *debugfs interface.*
+  This is for privileged user space programmers who want more optimized use of
+  DAMON.  Using this, users can use DAMON’s major features by reading
+  from and writing to special debugfs files.  Therefore, you can write and use
+  your personalized DAMON debugfs wrapper programs that reads/writes the
+  debugfs files instead of you.  The DAMON user space tool is also a reference
+  implementation of such programs.  It supports only virtual address spaces
+  monitoring.
+- *Kernel Space Programming Interface.*