Introduce Data Access MONitor (DAMON)

From: SeongJae Park <[email protected]>

Introduction
============

DAMON is a data access monitoring framework subsystem for the Linux kernel. The core mechanisms of DAMON called 'region based sampling' and adaptive regions adjustment' (refer to :doc:mechanisms for the detail) make it

- accurate (The monitored information is useful for DRAM level memory management. It might not appropriate for Cache-level accuracy, though.),
- ligfht-weight (The monitoring overhead is low enough to be applied online while making no impact on the performance of the target workloads.), and
- scalable (the upper-bound of the instrumentation overhead is controllable regardless of the size of target workloads.).

Using this framework, therefore, the kernel's core memory management mechanisms including reclamation and THP can be optimized for better memory management. The experimental memory management optimization works that incurring high instrumentation overhead will be able to have another try. In user space, meanwhile, users who have some special workloads will be able to write personalized tools or applications for deeper understanding and specialized optimizations of their systems.

Evaluations
===========

We evaluated DAMON's overhead, monitoring quality and usefulness using 25 realistic workloads on my QEMU/KVM based virtual machine running a kernel that v13 DAMON patchset is applied.

DAMON is lightweight. It increases system memory usage by only -0.39% and consumes less than 1% CPU time in most case. It slows target workloads down by only 0.63%.

DAMON is accurate and useful for memory management optimizations. An experimental DAMON-based operation scheme for THP, 'ethp', removes 69.43% of THP memory overheads while preserving 37.11% of THP speedup. Another experimental DAMON-based 'proactive reclamation' implementation, 'prcl', reduces 89.30% of residential sets and 22.40% of system memory footprint while incurring only 1.98% runtime overhead in the best case (parsec3/freqmine).

NOTE that the experimentail THP optimization and proactive reclamation are not for production, just only for proof of concepts.

Please refer to the official document[1] or "Documentation/admin-guide/mm: Add a document for DAMON" patch in this patchset for detailed evaluation setup and results.

[1] https://damonitor.github.io/doc/html/latest-damon

More Information
================

We prepared a showcase web site[1] that you can get more information. There are

- the official documentations[2],
- the heatmap format dynamic access pattern of various realistic workloads for heap area[3], mmap()-ed area[4], and stack[5] area,
- the dynamic working set size distribution[6] and chronological working set size changes[7], and
- the latest performance test results[8].

[1] https://damonitor.github.io/_index
[2] https://damonitor.github.io/doc/html/latest-damon
[3] https://damonitor.github.io/test/result/visual/latest/heatmap.0.html
[4] https://damonitor.github.io/test/result/visual/latest/heatmap.1.html
[5] https://damonitor.github.io/test/result/visual/latest/heatmap.2.html
[6] https://damonitor.github.io/test/result/visual/latest/wss_sz.html
[7] https://damonitor.github.io/test/result/visual/latest/wss_time.html
[8] https://damonitor.github.io/test/result/perf/latest/html/index.html

Baseline and Complete Git Trees
===============================

The patches are based on the v5.7. You can also clone the complete git tree:

    $ git clone git://github.com/sjp38/linux -b damon/patches/v14

The web is also available:
https://github.com/sjp38/linux/releases/tag/damon/patches/v14

There are a couple of trees for entire DAMON patchset series. It includes future features. The first one[1] contains the changes for latest release, while the other one[2] contains the changes for next release.

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

Sequence Of Patches
===================

The 1st patch exports 'lookup_page_ext()' to GPL modules so that it can be used by DAMON even though it is built as a loadable module.

Next four patches implement the core of DAMON and it's programming interface. The 2nd patch introduces DAMON module, it's data structures, and data structure related common functions. Following three patches (3rd to 5th) implements the core mechanisms of DAMON, namely regions based sampling (patch 3), adaptive regions adjustment (patch 4), and dynamic memory mapping chage adoption (patch 5).

Following four patches are for low level users of DAMON. The 6th patch implements callbacks for each of monitoring steps so that users can do whatever they want with the access patterns. The 7th one implements recording of access patterns in DAMON for better convenience and efficiency. Each of next two patches (8th and 9th) respectively adds a debugfs interface for privileged people and/or programs in user space, and a tracepoint for other tracepoints supporting tracers such as perf.

Two patches for high level users of DAMON follows. To provide a minimal reference to the debugfs interface and for high level use/tests of the DAMON, the next patch (10th) implements an user space tool. The 11th patch adds a document for administrators of DAMON.

Next three patches are for tests. The 12th and 13th patches provide unit tests (based on the kunit) while the 14th patch adds user space tests (based on the kselftest).

Finally, the last patch (15th) updates the MAINTAINERS file.

Patch History
=============

Changes from v13
(https://lore.kernel.org/linux-mm/[email protected]/)
- Fix a typo (Leonard Foerster)
- Fix wring condition of three sub ranges split (Leonard Foerster)
- Rebase on v5.7

Changes from v12
(https://lore.kernel.org/linux-mm/[email protected]/)
- Avoid races between debugfs readers and writers
- Add kernel-doc comments in damon.h

Changes from v11
(https://lore.kernel.org/linux-mm/[email protected]/)
- Rewrite the document (Stefan Nuernberger)
- Make 'damon_for_each_*' argument order consistent (Leonard Foerster)
- Fix wrong comment in 'kdamond_merge_regions()' (Leonard Foerster)

Changes from v10
(https://lore.kernel.org/linux-mm/[email protected]/)
- Reduce aggressive split overhead by doing it only if required

Changes from v9
(https://lore.kernel.org/linux-mm/[email protected]/)
- Split each region into 4 subregions if possible (Jonathan Cameraon)
- Update kunit test for the split code change

Changes from v8
(https://lore.kernel.org/linux-mm/[email protected]/)
- Make regions always aligned by minimal region size that can be changed (Stefan Nuernberger)
- Store binary format version in the recording file (Stefan Nuernberger)
- Use 'int' for pid instead of 'unsigned long' (Stefan Nuernberger)
- Fix a race condition in damon thread termination (Stefan Nuernberger)
- Optimize random value generation and recording (Stefan Nuernberger)
- Clean up commit messages and comments (Stefan Nuernberger)
- Clean up code (Stefan Nuernberger)
- Use explicit signalling and 'do_exit()' for damon thread termination
- Add more typos to spelling.txt
- Update the performance evaluation results
- Describe future plans in the cover letter

Changes from v7
(https://lore.kernel.org/linux-mm/[email protected]/)
- Cleanup variable names (Jonathan Cameron)
- Split sampling address setup from access_check() (Jonathan Cameron)
- Make sampling address to always locate in the region (Jonathan Cameron)
- Make initial region's sampling addr to be old (Jonathan Cameron)
- Split kdamond on/off function to seperate functions (Jonathan Cameron)
- Fix wrong kernel doc comments (Jonathan Cameron)
- Reset 'last_accessed' to false in kdamond_check_access() if necessary
- Rebase on v5.6

Please refer to v7 patchset to get older history.

SeongJae Park (15):
mm/page_ext: Export lookup_page_ext() to GPL modules
mm: Introduce Data Access MONitor (DAMON) mm/damon: Implement region based sampling mm/damon: Adaptively adjust regions
mm/damon: Apply dynamic memory mapping changes mm/damon: Implement callbacks
mm/damon: Implement access pattern recording mm/damon: Add debugfs interface
mm/damon: Add tracepoints
tools: Add a minimal user-space tool for DAMON Documentation/admin-guide/mm: Add a document for DAMON mm/damon: Add kunit tests
mm/damon-test: Add a kunit test for recording setup mm/damon: Add user space selftests
MAINTAINERS: Update for DAMON

 Documentation/admin-guide/mm/damon/api.rst    |   20 +
 .../admin-guide/mm/damon/damon_heatmap.png    |  Bin 0 -> 8366 bytes
 .../admin-guide/mm/damon/damon_wss_change.png |  Bin 0 -> 7211 bytes
 .../admin-guide/mm/damon/damon_wss_dist.png   |  Bin 0 -> 6173 bytes
 Documentation/admin-guide/mm/damon/eval.rst   |  215 +++
 Documentation/admin-guide/mm/damon/faq.rst    |   39 +
 .../admin-guide/mm/damon/freqmine_heatmap.png |  Bin 0 -> 8687 bytes
 .../admin-guide/mm/damon/freqmine_wss_sz.png  |  Bin 0 -> 4986 bytes
 .../mm/damon/freqmine_wss_time.png            |  Bin 0 -> 6283 bytes
 Documentation/admin-guide/mm/damon/guide.rst  |  196 +++
 Documentation/admin-guide/mm/damon/index.rst  |   36 +
 .../admin-guide/mm/damon/mechanisms.rst       |  111 ++
 Documentation/admin-guide/mm/damon/plans.rst  |   49 +
 Documentation/admin-guide/mm/damon/start.rst  |  119 ++
 .../mm/damon/streamcluster_heatmap.png        |  Bin 0 -> 37916 bytes
 .../mm/damon/streamcluster_wss_sz.png         |  Bin 0 -> 5522 bytes
 .../mm/damon/streamcluster_wss_time.png       |  Bin 0 -> 6322 bytes
 Documentation/admin-guide/mm/damon/usage.rst  |  305 ++++
 Documentation/admin-guide/mm/index.rst        |    1 +
 MAINTAINERS                                   |   12 +
 include/linux/damon.h                         |  136 ++
 include/trace/events/damon.h                  |   43 +
 mm/Kconfig                                    |   23 +
 mm/Makefile                                   |    1 +
 mm/damon-test.h                               |  635 +++++++
 mm/damon.c                                    | 1516 +++++++++++++++++
 mm/page_ext.c                                 |    1 +
 tools/damon/.gitignore                        |    1 +
 tools/damon/_dist.py                          |   36 +
 tools/damon/_recfile.py                       |   23 +
 tools/damon/bin2txt.py                        |   67 +
 tools/damon/damo                              |   37 +
 tools/damon/heats.py                          |  362 ++++
 tools/damon/nr_regions.py                     |   91 +
 tools/damon/record.py                         |  212 +++
 tools/damon/report.py                         |   45 +
 tools/damon/wss.py                            |   97 ++
 tools/testing/selftests/damon/Makefile        |    7 +
 .../selftests/damon/_chk_dependency.sh        |   28 +
 tools/testing/selftests/damon/_chk_record.py  |  108 ++
 .../testing/selftests/damon/debugfs_attrs.sh  |  139 ++
 .../testing/selftests/damon/debugfs_record.sh |   50 +
 42 files changed, 4761 insertions(+)
 create mode 100644 Documentation/admin-guide/mm/damon/api.rst
 create mode 100644 Documentation/admin-guide/mm/damon/damon_heatmap.png
 create mode 100644 Documentation/admin-guide/mm/damon/damon_wss_change.png
 create mode 100644 Documentation/admin-guide/mm/damon/damon_wss_dist.png
 create mode 100644 Documentation/admin-guide/mm/damon/eval.rst
 create mode 100644 Documentation/admin-guide/mm/damon/faq.rst
 create mode 100644 Documentation/admin-guide/mm/damon/freqmine_heatmap.png
 create mode 100644 Documentation/admin-guide/mm/damon/freqmine_wss_sz.png
 create mode 100644 Documentation/admin-guide/mm/damon/freqmine_wss_time.png
 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/mechanisms.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/streamcluster_heatmap.png
 create mode 100644 Documentation/admin-guide/mm/damon/streamcluster_wss_sz.png
 create mode 100644 Documentation/admin-guide/mm/damon/streamcluster_wss_time.png
 create mode 100644 Documentation/admin-guide/mm/damon/usage.rst
 create mode 100644 include/linux/damon.h
 create mode 100644 include/trace/events/damon.h
 create mode 100644 mm/damon-test.h
 create mode 100644 mm/damon.c
 create mode 100644 tools/damon/.gitignore
 create mode 100644 tools/damon/_dist.py
 create mode 100644 tools/damon/_recfile.py
 create mode 100644 tools/damon/bin2txt.py
 create mode 100755 tools/damon/damo
 create mode 100644 tools/damon/heats.py
 create mode 100644 tools/damon/nr_regions.py
 create mode 100644 tools/damon/record.py
 create mode 100644 tools/damon/report.py
 create mode 100644 tools/damon/wss.py
 create mode 100644 tools/testing/selftests/damon/Makefile
 create mode 100644 tools/testing/selftests/damon/_chk_dependency.sh
 create mode 100644 tools/testing/selftests/damon/_chk_record.py
 create mode 100755 tools/testing/selftests/damon/debugfs_attrs.sh
 create mode 100755 tools/testing/selftests/damon/debugfs_record.sh

2.17.1

From: SeongJae Park <[email protected]>

This commit exports 'lookup_page_ext()' to GPL modules. This will be used by DAMON.

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

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)
 {

2.17.1

From: SeongJae Park <[email protected]>

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

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

new file mode 100644
index 000000000000..135633334929
@@ -0,0 +1,54 @@
+/* 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_region - Represents a monitoring target region of
+ * [@vm_start, @vm_end).
+ *
+ * @vm_start:		Start address of the region (inclusive).
+ * @vm_end:		End address of the region (exclusive).
+ * @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 {
+	unsigned long vm_start;
+	unsigned long vm_end;
+	unsigned long sampling_addr;
+	unsigned int nr_accesses;
+	struct list_head list;
+};
+
+/**
+ * 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.
+ */
+struct damon_task {
+	int pid;
+	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

index c1acc34c1c35..ecea0889ea35 100644
@@ -867,4 +867,16 @@ config ARCH_HAS_HUGEPD
 config MAPPING_DIRTY_HELPERS
         bool
 
+config DAMON
+	tristate "Data Access Monitor"
+	depends on MMU
+	help
+	  Provides data access monitoring.
+
+	  DAMON is a kernel module that allows users to monitor the actual
+	  memory access pattern of specific user-space processes.  It aims to
+	  be 1) accurate enough to be useful for performance-centric domains,
+	  and 2) sufficiently light-weight so that it can be applied online.
+	  If unsure, say N.
+
 endmenu

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

2.17.1

From: SeongJae Park <[email protected]>

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

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

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

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

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

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

To avoid the unbounded increase of the overhead, DAMON groups a number of adjacent pages that assumed to have same access frequencies into a region. As long as the assumption (pages in a region have same access frequencies) is kept, only one page in the region is required to be checked. Thus, for each ``sampling interval``, DAMON randomly picks one page in each region and clears its Accessed bit. After one more ``sampling interval``, DAMON reads the Accessed bit of the page and increases the access frequency of the region if the bit has set meanwhile. Therefore, the monitoring overhead is controllable by setting the number of regions.

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

---
 include/linux/damon.h |  48 +++-
 mm/damon.c            | 597 ++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 644 insertions(+), 1 deletion(-)

index 135633334929..f0fe4520a4e9 100644
@@ -11,6 +11,8 @@
 #define _DAMON_H_
 
 #include <linux/random.h>
+#include <linux/mutex.h>
+#include <linux/time64.h>
 #include <linux/types.h>
 
 /**

@@ -44,11 +46,55 @@ struct damon_task {
 };
 
 /**
- * struct damon_ctx - Represents a context for each monitoring.
+ * struct damon_ctx - Represents a context for each monitoring.  This is the
+ * main interface that allows users to set the attributes and get the results
+ * of the monitoring.
+ *
+ * For each monitoring request (damon_start()), a kernel thread for the
+ * monitoring is created.  The pointer to the thread is stored in @kdamond.
+ *
+ * @sample_interval:		The time between access samplings.
+ * @aggr_interval:		The time between monitor results aggregations.
+ * @min_nr_regions:		The number of initial monitoring regions.
+ *
+ * For each @sample_interval, DAMON checks whether each region is accessed or
+ * not.  It aggregates and keeps the access information (number of accesses to
+ * each region) for @aggr_interval time.  All time intervals are in
+ * micro-seconds.
+ *
+ * @kdamond:		Kernel thread who does the monitoring.
+ * @kdamond_stop:	Notifies whether kdamond should stop.
+ * @kdamond_lock:	Mutex for the synchronizations with @kdamond.
+ *
+ * The monitoring thread sets @kdamond to NULL when it terminates.  Therefore,
+ * users can know whether the monitoring is ongoing or terminated by reading
+ * @kdamond.  Also, users can ask @kdamond to be terminated by writing non-zero
+ * to @kdamond_stop.  Reads and writes to @kdamond and @kdamond_stop from
+ * outside of the monitoring thread must be protected by @kdamond_lock.
+ *
+ * Note that the monitoring thread protects only @kdamond and @kdamond_stop via
+ * @kdamond_lock.  Accesses to other fields must be protected by themselves.
+ *
  * @tasks_list:		Head of monitoring target tasks (&damon_task) list.
  */
 struct damon_ctx {
+	unsigned long sample_interval;
+	unsigned long aggr_interval;
+	unsigned long min_nr_regions;
+
+	struct timespec64 last_aggregation;
+
+	struct task_struct *kdamond;
+	bool kdamond_stop;
+	struct mutex kdamond_lock;
+
 	struct list_head tasks_list;	/* 'damon_task' objects */
 };
 
+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 min_nr_reg);
+int damon_start(struct damon_ctx *ctx);
+int damon_stop(struct damon_ctx *ctx);
+
 #endif

2.17.1

From: SeongJae Park <[email protected]>

At the beginning of the monitoring, DAMON constructs the initial regions by evenly splitting the memory mapped address space of the process into the user-specified minimal number of regions. In this initial state, the assumption of the regions (pages in same region have similar access frequencies) is normally not kept and thus the monitoring quality could be low. To keep the assumption as much as possible, DAMON adaptively merges and splits each region.

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

In this way, DAMON provides its best-effort quality and minimal overhead while keeping the bounds users set for their trade-off.

---
 include/linux/damon.h |   7 +-
 mm/damon.c            | 174 +++++++++++++++++++++++++++++++++++++++---
 2 files changed, 169 insertions(+), 12 deletions(-)

index f0fe4520a4e9..babdba6b5c47 100644
@@ -56,6 +56,7 @@ struct damon_task {
  * @sample_interval:		The time between access samplings.
  * @aggr_interval:		The time between monitor results aggregations.
  * @min_nr_regions:		The number of initial monitoring regions.
+ * @max_nr_regions:		The maximum number of monitoring regions.
  *
  * For each @sample_interval, DAMON checks whether each region is accessed or
  * not.  It aggregates and keeps the access information (number of accesses to

@@ -81,6 +82,7 @@ struct damon_ctx {
 	unsigned long sample_interval;
 	unsigned long aggr_interval;
 	unsigned long min_nr_regions;
+	unsigned long max_nr_regions;
 
 	struct timespec64 last_aggregation;
 

@@ -92,8 +94,9 @@ struct damon_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 min_nr_reg);
+int damon_set_attrs(struct damon_ctx *ctx,
+		unsigned long sample_int, unsigned long aggr_int,
+		unsigned long min_nr_reg, unsigned long max_nr_reg);
 int damon_start(struct damon_ctx *ctx);
 int damon_stop(struct damon_ctx *ctx);
 

2.17.1

From: SeongJae Park <[email protected]>

Only a number of parts in the virtual address space of the processes is mapped to physical memory and accessed. Thus, tracking the unmapped address regions is just wasteful. However, tracking every memory mapping change might incur an overhead. For the reason, DAMON applies the dynamic memory mapping changes to the tracking regions only for each of a user-specified time interval (``regions update interval``).

---
 include/linux/damon.h |  13 ++++--
 mm/damon.c            | 101 +++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 108 insertions(+), 6 deletions(-)

index babdba6b5c47..5afcb2bb7f77 100644
@@ -55,13 +55,16 @@ struct damon_task {
  *
  * @sample_interval:		The time between access samplings.
  * @aggr_interval:		The time between monitor results aggregations.
+ * @regions_update_interval:	The time between monitor regions updates.
  * @min_nr_regions:		The number of initial monitoring regions.
  * @max_nr_regions:		The maximum number of monitoring regions.
  *
  * For each @sample_interval, DAMON checks whether each region is accessed or
  * not.  It aggregates and keeps the access information (number of accesses to
- * each region) for @aggr_interval time.  All time intervals are in
- * micro-seconds.
+ * each region) for @aggr_interval time.  DAMON also checks whether the target
+ * memory regions need update (e.g., by ``mmap()`` calls from the application,
+ * in case of virtual memory monitoring) and applies the changes for each
+ * @regions_update_interval.  All time intervals are in micro-seconds.
  *
  * @kdamond:		Kernel thread who does the monitoring.
  * @kdamond_stop:	Notifies whether kdamond should stop.

@@ -81,10 +84,12 @@ struct damon_task {
 struct damon_ctx {
 	unsigned long sample_interval;
 	unsigned long aggr_interval;
+	unsigned long regions_update_interval;
 	unsigned long min_nr_regions;
 	unsigned long max_nr_regions;
 
 	struct timespec64 last_aggregation;
+	struct timespec64 last_regions_update;
 
 	struct task_struct *kdamond;
 	bool kdamond_stop;

@@ -94,8 +99,8 @@ struct damon_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,
+int damon_set_attrs(struct damon_ctx *ctx, unsigned long sample_int,
+		unsigned long aggr_int, unsigned long regions_update_int,
 		unsigned long min_nr_reg, unsigned long max_nr_reg);
 int damon_start(struct damon_ctx *ctx);
 int damon_stop(struct damon_ctx *ctx);

2.17.1

From: SeongJae Park <[email protected]>

This commit implements callbacks for DAMON. Using this, DAMON users can install their callbacks for each step of the access monitoring so that they can do something interesting with the monitored access patterns online. For example, callbacks can report the monitored patterns to users or do some access pattern based memory management such as proactive reclamations or access pattern based THP promotions/demotions decision makings.

---
 include/linux/damon.h | 13 +++++++++++++
 mm/damon.c            |  4 ++++
 2 files changed, 17 insertions(+)

index 5afcb2bb7f77..12536d9d2f74 100644
@@ -80,6 +80,15 @@ struct damon_task {
  * @kdamond_lock.  Accesses to other fields must be protected by themselves.
  *
  * @tasks_list:		Head of monitoring target tasks (&damon_task) list.
+ *
+ * @sample_cb:			Called for each sampling interval.
+ * @aggregate_cb:		Called for each aggregation interval.
+ *
+ * @sample_cb and @aggregate_cb are called from @kdamond for each of the
+ * sampling intervals and aggregation intervals, respectively.  Therefore,
+ * users can safely access to the monitoring results via @tasks_list without
+ * additional protection of @kdamond_lock.  For the reason, users are
+ * recommended to use these callback for the accesses to the results.
  */
 struct damon_ctx {
 	unsigned long sample_interval;

@@ -96,6 +105,10 @@ struct damon_ctx {
 	struct mutex kdamond_lock;
 
 	struct list_head tasks_list;	/* 'damon_task' objects */
+
+	/* callbacks */
+	void (*sample_cb)(struct damon_ctx *context);
+	void (*aggregate_cb)(struct damon_ctx *context);
 };
 
 int damon_set_pids(struct damon_ctx *ctx, int *pids, ssize_t nr_pids);

index de5ed38ac05c..42ce9df47f8b 100644
@@ -850,6 +850,8 @@ static int kdamond_fn(void *data)
 	kdamond_init_regions(ctx);
 	while (!kdamond_need_stop(ctx)) {
 		kdamond_prepare_access_checks(ctx);
+		if (ctx->sample_cb)
+			ctx->sample_cb(ctx);
 
 		usleep_range(ctx->sample_interval, ctx->sample_interval + 1);
 

@@ -857,6 +859,8 @@ static int kdamond_fn(void *data)
 
 		if (kdamond_aggregate_interval_passed(ctx)) {
 			kdamond_merge_regions(ctx, max_nr_accesses / 10);
+			if (ctx->aggregate_cb)
+				ctx->aggregate_cb(ctx);
 			kdamond_reset_aggregated(ctx);
 			kdamond_split_regions(ctx);
 		}

2.17.1

From: SeongJae Park <[email protected]>

This commit implements the recording feature of DAMON. If this feature is enabled, DAMON writes the monitored access patterns in its binary format into a file which specified by the user. This is already able to be implemented by each user using the callbacks. However, as the recording is expected to be used widely, this commit implements the feature in the DAMON, for more convenience and efficiency.

---
 include/linux/damon.h |  15 +++++
 mm/damon.c            | 131 +++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 143 insertions(+), 3 deletions(-)

index 12536d9d2f74..c4796a10cb1a 100644
@@ -66,6 +66,14 @@ struct damon_task {
  * in case of virtual memory monitoring) and applies the changes for each
  * @regions_update_interval.  All time intervals are in micro-seconds.
  *
+ * @rbuf: In-memory buffer for monitoring result recording.
+ * @rbuf_len: The length of @rbuf.
+ * @rbuf_offset: The offset for next write to @rbuf.
+ * @rfile_path: Record file path.
+ *
+ * If @rbuf, @rbuf_len, and @rfile_path are set, the monitored results are
+ * automatically stored in @rfile_path file.
+ *
  * @kdamond:		Kernel thread who does the monitoring.
  * @kdamond_stop:	Notifies whether kdamond should stop.
  * @kdamond_lock:	Mutex for the synchronizations with @kdamond.

@@ -100,6 +108,11 @@ struct damon_ctx {
 	struct timespec64 last_aggregation;
 	struct timespec64 last_regions_update;
 
+	unsigned char *rbuf;
+	unsigned int rbuf_len;
+	unsigned int rbuf_offset;
+	char *rfile_path;
+
 	struct task_struct *kdamond;
 	bool kdamond_stop;
 	struct mutex kdamond_lock;

@@ -115,6 +128,8 @@ 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,
 		unsigned long min_nr_reg, unsigned long max_nr_reg);
+int damon_set_recording(struct damon_ctx *ctx,
+				unsigned int rbuf_len, char *rfile_path);
 int damon_start(struct damon_ctx *ctx);
 int damon_stop(struct damon_ctx *ctx);
 

2.17.1

From: SeongJae Park <[email protected]>

This commit adds a debugfs interface for DAMON.

DAMON exports four files, ``attrs``, ``pids``, ``record``, and ``monitor_on`` under its debugfs directory, ``<debugfs>/damon/``.

Attributes
----------

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

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

Target PIDs
-----------

Users can read and write the pids of current monitoring target processes by reading from and writing to the ``pids`` file. For example, below commands set processes having pids 42 and 4242 as the processes to be monitored and check it again::

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

Note that setting the pids doesn't start the monitoring.

Record
------

DAMON supports direct monitoring result record feature. The recorded results are first written to a buffer and flushed to a file in batch. Users can set the size of the buffer and the path to the result file by reading from and writing to the ``record`` file. For example, below commands set the buffer to be 4 KiB and the result to be saved in '/damon.data'.

    # cd <debugfs>/damon
    # echo 4096 /damon.data > pids
    # cat record
    4096 /damon.data

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

You can check current status, start and stop the monitoring by reading from and writing to the ``monitor_on`` file. Writing ``on`` to the file starts DAMON to monitor the target processes with the attributes. Writing ``off`` to the file stops DAMON. DAMON also stops if every target processes is terminated. Below example commands turn on, off, and check status of DAMON::

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

Please note that you cannot write to the ``attrs`` and ``pids`` files while the monitoring is turned on. If you write to the files while DAMON is running, ``-EINVAL`` will be returned.

---
 mm/damon.c | 357 ++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 356 insertions(+), 1 deletion(-)

index 768ffd08f7ab..6b0b8f21a6c6 100644
@@ -10,6 +10,7 @@
 #define pr_fmt(fmt) "damon: " fmt
 
 #include <linux/damon.h>
+#include <linux/debugfs.h>
 #include <linux/delay.h>
 #include <linux/kthread.h>
 #include <linux/mm.h>

@@ -50,6 +51,15 @@
 /* Get a random number in [l, r) */
 #define damon_rand(l, r) (l + prandom_u32() % (r - l))
 
+/* A monitoring context for debugfs interface users. */
+static struct damon_ctx damon_user_ctx = {
+	.sample_interval = 5 * 1000,
+	.aggr_interval = 100 * 1000,
+	.regions_update_interval = 1000 * 1000,
+	.min_nr_regions = 10,
+	.max_nr_regions = 1000,
+};
+
 /*
  * Construct a damon_region struct
  *

@@ -1133,13 +1143,358 @@ int damon_set_attrs(struct damon_ctx *ctx, unsigned long sample_int,
 	return 0;
 }
 
-static int __init damon_init(void)
+static ssize_t debugfs_monitor_on_read(struct file *file,
+		char __user *buf, size_t count, loff_t *ppos)
+{
+	struct damon_ctx *ctx = &damon_user_ctx;
+	char monitor_on_buf[5];
+	bool monitor_on;
+	int len;
+
+	monitor_on = damon_kdamond_running(ctx);
+	len = snprintf(monitor_on_buf, 5, monitor_on ? "on\n" : "off\n");
+
+	return simple_read_from_buffer(buf, count, ppos, monitor_on_buf, len);
+}
+
+static ssize_t debugfs_monitor_on_write(struct file *file,
+		const char __user *buf, size_t count, loff_t *ppos)
+{
+	struct damon_ctx *ctx = &damon_user_ctx;
+	ssize_t ret;
+	char cmdbuf[5];
+	int err;
+
+	ret = simple_write_to_buffer(cmdbuf, 5, ppos, buf, count);
+	if (ret < 0)
+		return ret;
+
+	if (sscanf(cmdbuf, "%s", cmdbuf) != 1)
+		return -EINVAL;
+	if (!strncmp(cmdbuf, "on", 5))
+		err = damon_start(ctx);
+	else if (!strncmp(cmdbuf, "off", 5))
+		err = damon_stop(ctx);
+	else
+		return -EINVAL;
+
+	if (err)
+		ret = err;
+	return ret;
+}
+
+static ssize_t damon_sprint_pids(struct damon_ctx *ctx, char *buf, ssize_t len)
+{
+	struct damon_task *t;
+	int written = 0;
+	int rc;
+
+	damon_for_each_task(t, ctx) {
+		rc = snprintf(&buf[written], len - written, "%d ", t->pid);
+		if (!rc)
+			return -ENOMEM;
+		written += rc;
+	}
+	if (written)
+		written -= 1;
+	written += snprintf(&buf[written], len - written, "\n");
+	return written;
+}
+
+static ssize_t debugfs_pids_read(struct file *file,
+		char __user *buf, size_t count, loff_t *ppos)
 {
+	struct damon_ctx *ctx = &damon_user_ctx;
+	ssize_t len;
+	char pids_buf[320];
+
+	mutex_lock(&ctx->kdamond_lock);
+	len = damon_sprint_pids(ctx, pids_buf, 320);
+	mutex_unlock(&ctx->kdamond_lock);
+	if (len < 0)
+		return len;
+
+	return simple_read_from_buffer(buf, count, ppos, pids_buf, len);
+}
+
+/*
+ * Converts a string into an array of unsigned long integers
+ *
+ * Returns an array of unsigned long integers if the conversion success, or
+ * NULL otherwise.
+ */
+static 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);
+		pos += parsed;
+		if (ret != 1)
+			break;
+		pids[*nr_pids] = pid;
+		*nr_pids += 1;
+	}
+	if (*nr_pids == 0) {
+		kfree(pids);
+		pids = NULL;
+	}
+
+	return pids;
+}
+
+static ssize_t debugfs_pids_write(struct file *file,
+		const char __user *buf, size_t count, loff_t *ppos)
+{
+	struct damon_ctx *ctx = &damon_user_ctx;
+	char *kbuf;
+	int *targets;
+	ssize_t nr_targets;
+	ssize_t ret;
+	int err;
+
+	kbuf = kmalloc(count, GFP_KERNEL);
+	if (!kbuf)
+		return -ENOMEM;
+
+	ret = simple_write_to_buffer(kbuf, count, ppos, buf, count);
+	if (ret < 0)
+		goto out;
+
+	targets = str_to_pids(kbuf, ret, &nr_targets);
+	if (!targets) {
+		ret = -ENOMEM;
+		goto out;
+	}
+
+	mutex_lock(&ctx->kdamond_lock);
+	if (ctx->kdamond) {
+		ret = -EINVAL;
+		goto unlock_out;
+	}
+
+	err = damon_set_pids(ctx, targets, nr_targets);
+	if (err)
+		ret = err;
+unlock_out:
+	mutex_unlock(&ctx->kdamond_lock);
+	kfree(targets);
+out:
+	kfree(kbuf);
+	return ret;
+}
+
+static ssize_t debugfs_record_read(struct file *file,
+		char __user *buf, size_t count, loff_t *ppos)
+{
+	struct damon_ctx *ctx = &damon_user_ctx;
+	char record_buf[20 + MAX_RFILE_PATH_LEN];
+	int ret;
+
+	mutex_lock(&ctx->kdamond_lock);
+	ret = snprintf(record_buf, ARRAY_SIZE(record_buf), "%u %s\n",
+			ctx->rbuf_len, ctx->rfile_path);
+	mutex_unlock(&ctx->kdamond_lock);
+	return simple_read_from_buffer(buf, count, ppos, record_buf, ret);
+}
+
+static ssize_t debugfs_record_write(struct file *file,
+		const char __user *buf, size_t count, loff_t *ppos)
+{
+	struct damon_ctx *ctx = &damon_user_ctx;
+	char *kbuf;
+	unsigned int rbuf_len;
+	char rfile_path[MAX_RFILE_PATH_LEN];
+	ssize_t ret;
+	int err;
+
+	kbuf = kmalloc(count + 1, GFP_KERNEL);
+	if (!kbuf)
+		return -ENOMEM;
+	kbuf[count] = '\0';
+
+	ret = simple_write_to_buffer(kbuf, count, ppos, buf, count);
+	if (ret < 0)
+		goto out;
+	if (sscanf(kbuf, "%u %s",
+				&rbuf_len, rfile_path) != 2) {
+		ret = -EINVAL;
+		goto out;
+	}
+
+	mutex_lock(&ctx->kdamond_lock);
+	if (ctx->kdamond) {
+		ret = -EBUSY;
+		goto unlock_out;
+	}
+
+	err = damon_set_recording(ctx, rbuf_len, rfile_path);
+	if (err)
+		ret = err;
+unlock_out:
+	mutex_unlock(&ctx->kdamond_lock);
+out:
+	kfree(kbuf);
+	return ret;
+}
+
+
+static ssize_t debugfs_attrs_read(struct file *file,
+		char __user *buf, size_t count, loff_t *ppos)
+{
+	struct damon_ctx *ctx = &damon_user_ctx;
+	char kbuf[128];
+	int ret;
+
+	mutex_lock(&ctx->kdamond_lock);
+	ret = snprintf(kbuf, ARRAY_SIZE(kbuf), "%lu %lu %lu %lu %lu\n",
+			ctx->sample_interval, ctx->aggr_interval,
+			ctx->regions_update_interval, ctx->min_nr_regions,
+			ctx->max_nr_regions);
+	mutex_unlock(&ctx->kdamond_lock);
+
+	return simple_read_from_buffer(buf, count, ppos, kbuf, ret);
+}
+
+static ssize_t debugfs_attrs_write(struct file *file,
+		const char __user *buf, size_t count, loff_t *ppos)
+{
+	struct damon_ctx *ctx = &damon_user_ctx;
+	unsigned long s, a, r, minr, maxr;
+	char *kbuf;
+	ssize_t ret;
+	int err;
+
+	kbuf = kmalloc(count, GFP_KERNEL);
+	if (!kbuf)
+		return -ENOMEM;
+
+	ret = simple_write_to_buffer(kbuf, count, ppos, buf, count);
+	if (ret < 0)
+		goto out;
+
+	if (sscanf(kbuf, "%lu %lu %lu %lu %lu",
+				&s, &a, &r, &minr, &maxr) != 5) {
+		ret = -EINVAL;
+		goto out;
+	}
+
+	mutex_lock(&ctx->kdamond_lock);
+	if (ctx->kdamond) {
+		ret = -EBUSY;
+		goto unlock_out;
+	}
+
+	err = damon_set_attrs(ctx, s, a, r, minr, maxr);
+	if (err)
+		ret = err;
+unlock_out:
+	mutex_unlock(&ctx->kdamond_lock);
+out:
+	kfree(kbuf);
+	return ret;
+}
+
+static const struct file_operations monitor_on_fops = {
+	.owner = THIS_MODULE,
+	.read = debugfs_monitor_on_read,
+	.write = debugfs_monitor_on_write,
+};
+
+static const struct file_operations pids_fops = {
+	.owner = THIS_MODULE,
+	.read = debugfs_pids_read,
+	.write = debugfs_pids_write,
+};
+
+static const struct file_operations record_fops = {
+	.owner = THIS_MODULE,
+	.read = debugfs_record_read,
+	.write = debugfs_record_write,
+};
+
+static const struct file_operations attrs_fops = {
+	.owner = THIS_MODULE,
+	.read = debugfs_attrs_read,
+	.write = debugfs_attrs_write,
+};
+
+static struct dentry *debugfs_root;
+
+static int __init damon_debugfs_init(void)
+{
+	const char * const file_names[] = {"attrs", "record",
+		"pids", "monitor_on"};
+	const struct file_operations *fops[] = {&attrs_fops, &record_fops,
+		&pids_fops, &monitor_on_fops};
+	int i;
+
+	debugfs_root = debugfs_create_dir("damon", NULL);
+	if (!debugfs_root) {
+		pr_err("failed to create the debugfs dir\n");
+		return -ENOMEM;
+	}
+
+	for (i = 0; i < ARRAY_SIZE(file_names); i++) {
+		if (!debugfs_create_file(file_names[i], 0600, debugfs_root,
+					NULL, fops[i])) {
+			pr_err("failed to create %s file\n", file_names[i]);
+			return -ENOMEM;
+		}
+	}
+
 	return 0;
 }
 
+static int __init damon_init_user_ctx(void)
+{
+	int rc;
+
+	struct damon_ctx *ctx = &damon_user_ctx;
+
+	ktime_get_coarse_ts64(&ctx->last_aggregation);
+	ctx->last_regions_update = ctx->last_aggregation;
+
+	rc = damon_set_recording(ctx, 1024 * 1024, "/damon.data");
+	if (rc)
+		return rc;
+
+	mutex_init(&ctx->kdamond_lock);
+
+	INIT_LIST_HEAD(&ctx->tasks_list);
+
+	return 0;
+}
+
+static int __init damon_init(void)
+{
+	int rc;
+
+	rc = damon_init_user_ctx();
+	if (rc)
+		return rc;
+
+	rc = damon_debugfs_init();
+	if (rc)
+		pr_err("%s: debugfs init failed\n", __func__);
+
+	return rc;
+}
+
 static void __exit damon_exit(void)
 {
+	damon_stop(&damon_user_ctx);
+	debugfs_remove_recursive(debugfs_root);
+
+	kfree(damon_user_ctx.rbuf);
+	kfree(damon_user_ctx.rfile_path);
 }
 
 module_init(damon_init);

2.17.1

From: SeongJae Park <[email protected]>

This commit adds a tracepoint for DAMON. It traces the monitoring results of each region for each aggregation interval. Using this, DAMON will be easily integrated with any tracepoints supporting tools such as perf.

---
 include/trace/events/damon.h | 43 ++++++++++++++++++++++++++++++++++++
 mm/damon.c                   |  5 +++++
 2 files changed, 48 insertions(+)
 create mode 100644 include/trace/events/damon.h

new file mode 100644
index 000000000000..22236642d366
@@ -0,0 +1,43 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#undef TRACE_SYSTEM
+#define TRACE_SYSTEM damon
+
+#if !defined(_TRACE_DAMON_H) || defined(TRACE_HEADER_MULTI_READ)
+#define _TRACE_DAMON_H
+
+#include <linux/types.h>
+#include <linux/tracepoint.h>
+
+TRACE_EVENT(damon_aggregated,
+
+	TP_PROTO(int pid, unsigned int nr_regions,
+		unsigned long vm_start, unsigned long vm_end,
+		unsigned int nr_accesses),
+
+	TP_ARGS(pid, nr_regions, vm_start, vm_end, nr_accesses),
+
+	TP_STRUCT__entry(
+		__field(int, pid)
+		__field(unsigned int, nr_regions)
+		__field(unsigned long, vm_start)
+		__field(unsigned long, vm_end)
+		__field(unsigned int, nr_accesses)
+	),
+
+	TP_fast_assign(
+		__entry->pid = pid;
+		__entry->nr_regions = nr_regions;
+		__entry->vm_start = vm_start;
+		__entry->vm_end = vm_end;
+		__entry->nr_accesses = nr_accesses;
+	),
+
+	TP_printk("pid=%d nr_regions=%u %lu-%lu: %u", __entry->pid,
+			__entry->nr_regions, __entry->vm_start,
+			__entry->vm_end, __entry->nr_accesses)
+);
+
+#endif /* _TRACE_DAMON_H */
+
+/* This part must be outside protection */
+#include <trace/define_trace.h>

index 6b0b8f21a6c6..af6f395fe06c 100644
@@ -9,6 +9,8 @@
 
 #define pr_fmt(fmt) "damon: " fmt
 
+#define CREATE_TRACE_POINTS
+
 #include <linux/damon.h>
 #include <linux/debugfs.h>
 #include <linux/delay.h>

@@ -20,6 +22,7 @@
 #include <linux/sched/mm.h>
 #include <linux/sched/task.h>
 #include <linux/slab.h>
+#include <trace/events/damon.h>
 
 /* Minimal region size.  Every damon_region is aligned by this. */
 #define MIN_REGION PAGE_SIZE

@@ -650,6 +653,8 @@ static void kdamond_reset_aggregated(struct damon_ctx *c)
 			damon_write_rbuf(c, &r->vm_end, sizeof(r->vm_end));
 			damon_write_rbuf(c, &r->nr_accesses,
 					sizeof(r->nr_accesses));
+			trace_damon_aggregated(t->pid, nr,
+					r->vm_start, r->vm_end, r->nr_accesses);
 			r->nr_accesses = 0;
 		}
 	}

2.17.1

Good point, I will do so in the next spin!

Thanks,
SeongJae Park

From: SeongJae Park <[email protected]>

This commit adds a shallow wrapper python script, ``/tools/damon/damo`` that provides more convenient interface. Note that it is only aimed to be used for minimal reference of the DAMON's debugfs interfaces and for debugging of the DAMON itself.

---
 tools/damon/.gitignore    |   1 +
 tools/damon/_dist.py      |  36 ++++
 tools/damon/_recfile.py   |  23 +++
 tools/damon/bin2txt.py    |  67 +++++++
 tools/damon/damo          |  37 ++++
 tools/damon/heats.py      | 362 ++++++++++++++++++++++++++++++++++++++
 tools/damon/nr_regions.py |  91 ++++++++++
 tools/damon/record.py     | 212 ++++++++++++++++++++++
 tools/damon/report.py     |  45 +++++
 tools/damon/wss.py        |  97 ++++++++++
 10 files changed, 971 insertions(+)
 create mode 100644 tools/damon/.gitignore
 create mode 100644 tools/damon/_dist.py
 create mode 100644 tools/damon/_recfile.py
 create mode 100644 tools/damon/bin2txt.py
 create mode 100755 tools/damon/damo
 create mode 100644 tools/damon/heats.py
 create mode 100644 tools/damon/nr_regions.py
 create mode 100644 tools/damon/record.py
 create mode 100644 tools/damon/report.py
 create mode 100644 tools/damon/wss.py

new file mode 100644
index 000000000000..96403d36ff93
@@ -0,0 +1 @@
+__pycache__/*

new file mode 100644
index 000000000000..9851ec964e5c
@@ -0,0 +1,36 @@
+#!/usr/bin/env python3
+# SPDX-License-Identifier: GPL-2.0
+
+import os
+import struct
+import subprocess
+
+def access_patterns(f):
+    nr_regions = struct.unpack('I', f.read(4))[0]
+
+    patterns = []
+    for r in range(nr_regions):
+        saddr = struct.unpack('L', f.read(8))[0]
+        eaddr = struct.unpack('L', f.read(8))[0]
+        nr_accesses = struct.unpack('I', f.read(4))[0]
+        patterns.append([eaddr - saddr, nr_accesses])
+    return patterns
+
+def plot_dist(data_file, output_file, xlabel, ylabel):
+    terminal = output_file.split('.')[-1]
+    if not terminal in ['pdf', 'jpeg', 'png', 'svg']:
+        os.remove(data_file)
+        print("Unsupported plot output type.")
+        exit(-1)
+
+    gnuplot_cmd = """
+    set term %s;
+    set output '%s';
+    set key off;
+    set xlabel '%s';
+    set ylabel '%s';
+    plot '%s' with linespoints;""" % (terminal, output_file, xlabel, ylabel,
+            data_file)
+    subprocess.call(['gnuplot', '-e', gnuplot_cmd])
+    os.remove(data_file)
+

new file mode 100644
index 000000000000..331b4d8165d8
@@ -0,0 +1,23 @@
+#!/usr/bin/env python3
+# SPDX-License-Identifier: GPL-2.0
+
+import struct
+
+fmt_version = 0
+
+def set_fmt_version(f):
+    global fmt_version
+
+    mark = f.read(16)
+    if mark == b'damon_recfmt_ver':
+        fmt_version = struct.unpack('i', f.read(4))[0]
+    else:
+        fmt_version = 0
+        f.seek(0)
+    return fmt_version
+
+def pid(f):
+    if fmt_version == 0:
+        return struct.unpack('L', f.read(8))[0]
+    else:
+        return struct.unpack('i', f.read(4))[0]

new file mode 100755
index 000000000000..58e1099ae5fc
@@ -0,0 +1,37 @@
+#!/usr/bin/env python3
+# SPDX-License-Identifier: GPL-2.0
+
+import argparse
+
+import record
+import report
+
+class SubCmdHelpFormatter(argparse.RawDescriptionHelpFormatter):
+    def _format_action(self, action):
+        parts = super(argparse.RawDescriptionHelpFormatter,
+                self)._format_action(action)
+        # skip sub parsers help
+        if action.nargs == argparse.PARSER:
+            parts = '\n'.join(parts.split('\n')[1:])
+        return parts
+
+parser = argparse.ArgumentParser(formatter_class=SubCmdHelpFormatter)
+
+subparser = parser.add_subparsers(title='command', dest='command',
+        metavar='<command>')
+subparser.required = True
+
+parser_record = subparser.add_parser('record',
+        help='record data accesses of the given target processes')
+record.set_argparser(parser_record)
+
+parser_report = subparser.add_parser('report',
+        help='report the recorded data accesses in the specified form')
+report.set_argparser(parser_report)
+
+args = parser.parse_args()
+
+if args.command == 'record':
+    record.main(args)
+elif args.command == 'report':
+    report.main(args)

2.17.1

From: SeongJae Park <[email protected]>

This commit adds a simple document for DAMON under Documentation/admin-guide/mm.

---
 Documentation/admin-guide/mm/damon/api.rst    |  20 ++
 .../admin-guide/mm/damon/damon_heatmap.png    | Bin 0 -> 8366 bytes
 .../admin-guide/mm/damon/damon_wss_change.png | Bin 0 -> 7211 bytes
 .../admin-guide/mm/damon/damon_wss_dist.png   | Bin 0 -> 6173 bytes
 Documentation/admin-guide/mm/damon/eval.rst   | 215 ++++++++++++
 Documentation/admin-guide/mm/damon/faq.rst    |  39 +++
 .../admin-guide/mm/damon/freqmine_heatmap.png | Bin 0 -> 8687 bytes
 .../admin-guide/mm/damon/freqmine_wss_sz.png  | Bin 0 -> 4986 bytes
 .../mm/damon/freqmine_wss_time.png            | Bin 0 -> 6283 bytes
 Documentation/admin-guide/mm/damon/guide.rst  | 196 +++++++++++
 Documentation/admin-guide/mm/damon/index.rst  |  36 +++
 .../admin-guide/mm/damon/mechanisms.rst       | 111 +++++++
 Documentation/admin-guide/mm/damon/plans.rst  |  49 +++
 Documentation/admin-guide/mm/damon/start.rst  | 119 +++++++
 .../mm/damon/streamcluster_heatmap.png        | Bin 0 -> 37916 bytes
 .../mm/damon/streamcluster_wss_sz.png         | Bin 0 -> 5522 bytes
 .../mm/damon/streamcluster_wss_time.png       | Bin 0 -> 6322 bytes
 Documentation/admin-guide/mm/damon/usage.rst  | 305 ++++++++++++++++++
 Documentation/admin-guide/mm/index.rst        |   1 +
 19 files changed, 1091 insertions(+)
 create mode 100644 Documentation/admin-guide/mm/damon/api.rst
 create mode 100644 Documentation/admin-guide/mm/damon/damon_heatmap.png
 create mode 100644 Documentation/admin-guide/mm/damon/damon_wss_change.png
 create mode 100644 Documentation/admin-guide/mm/damon/damon_wss_dist.png
 create mode 100644 Documentation/admin-guide/mm/damon/eval.rst
 create mode 100644 Documentation/admin-guide/mm/damon/faq.rst
 create mode 100644 Documentation/admin-guide/mm/damon/freqmine_heatmap.png
 create mode 100644 Documentation/admin-guide/mm/damon/freqmine_wss_sz.png
 create mode 100644 Documentation/admin-guide/mm/damon/freqmine_wss_time.png
 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/mechanisms.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/streamcluster_heatmap.png
 create mode 100644 Documentation/admin-guide/mm/damon/streamcluster_wss_sz.png
 create mode 100644 Documentation/admin-guide/mm/damon/streamcluster_wss_time.png
 create mode 100644 Documentation/admin-guide/mm/damon/usage.rst

new file mode 100644
index 000000000000..649409828eab
@@ -0,0 +1,20 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+=============
+API Reference
+=============
+
+Kernel space programs can use every feature of DAMON using below APIs.  All you
+need to do is including ``damon.h``, which is located in ``include/linux/`` of
+the source tree.
+
+Structures
+==========
+
+.. kernel-doc:: include/linux/damon.h
+
+
+Functions
+=========
+
+.. kernel-doc:: mm/damon.c

new file mode 100644
index 0000000000000000000000000000000000000000..ff485f9f59ca2717f5221b2824eaaed616b22c0e
GIT binary patch

new file mode 100644
index 0000000000000000000000000000000000000000..36699547c342cd05c9f416c78bc3fc86b9dc415e
GIT binary patch

new file mode 100644
index 0000000000000000000000000000000000000000..3c390f5115af9bcf7bd76ccdf9414de8ace9799b
GIT binary patch

new file mode 100644
index 000000000000..7ea52d1078a0
@@ -0,0 +1,39 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+==========================
+Frequently Asked Questions
+==========================
+
+Why a new module, instead of extending perf or other user space tools?
+======================================================================
+
+First, because it needs to be lightweight as much as possible so that it can be
+used online, any unnecessary overhead such as kernel - user space context
+switching cost should be avoided.  Second, DAMON aims to be used by other
+programs including the kernel.  Therefore, having a dependency on specific
+tools like perf is not desirable.  These are the two biggest reasons why DAMON
+is implemented in the kernel space.
+
+
+Can 'idle pages tracking' or 'perf mem' substitute DAMON?
+=========================================================
+
+Idle page tracking is a low level primitive for access check of each physical
+page frame.  'perf mem' is similar, though it can use sampling to minimize the
+overhead.  DAMON is a higher-level framework for access patterns of data objects
+that focused on memory management optimization and providing sophisticated
+features for that including the overhead handling.  Therefore, 'idle pages
+tracking' and 'perf mem' could provide a subset of DAMON's output, but cannot
+substitute DAMON.  Rather than that, DAMON could use those as it's low-level
+primitives.
+
+
+Does DAMON support virtual memory only?
+========================================
+
+For now, yes.  But, DAMON will be able to support various address spaces
+including physical memory in near future.  An RFC patchset [1]_ for this
+extension is already available.  Please refer :doc:`plans` for detailed plan
+for this.
+
+.. [1] https://lore.kernel.org/linux-mm/[email protected]/

new file mode 100644
index 0000000000000000000000000000000000000000..9641bade4e2e52cfaf77ac2ef50607239ab90899
GIT binary patch

new file mode 100644
index 0000000000000000000000000000000000000000..28049dec5fabfca0ca33896ee6b667dc116aacbf
GIT binary patch

new file mode 100644
index 0000000000000000000000000000000000000000..3ca9df7ee11a9cf650fc75497f653345eba28eea
GIT binary patch

new file mode 100644
index 000000000000..eff50714bbd0
@@ -0,0 +1,36 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+==========================
+DAMON: Data Access MONitor
+==========================
+
+DAMON is a data access monitoring framework subsystem for the Linux kernel.
+The core mechanisms of DAMON called 'region based sampling' and adaptive
+regions adjustment' (refer to :doc:`mechanisms` for the detail) make it
+
+ - *accurate* (The monitored information is useful for DRAM level memory
+   management; It might not appropriate for Cache-level accuracy, though),
+ - *ligfht-weight* (The monitoring overhead is low enough to be applied online
+   while making no impact on the performance of the target workloads), and
+ - *scalable* (The upper-bound of the instrumentation overhead is controllable
+   regardless of the size of target workloads).
+
+Using this framework, therefore, the kernel's core memory management mechanisms
+including reclamation and THP can be optimized for better memory management.
+The experimental memory management optimization works that incurring high
+instrumentation overhead will be able to have another try.  In user space,
+meanwhile, users who have some special workloads will be able to write
+personalized tools or applications for deeper understanding and specialized
+optimizations of their systems.
+
+.. toctree::
+   :maxdepth: 2
+
+   start
+   guide
+   usage
+   api
+   faq
+   mechanisms
+   eval
+   plans

new file mode 100644
index 0000000000000000000000000000000000000000..c9186f63bca4292a3f2e7602b2095c46914b9ae0
GIT binary patch

new file mode 100644
index 0000000000000000000000000000000000000000..8ea84a454233d3ab5f754d8cbdef78a15b134f70
GIT binary patch

new file mode 100644
index 0000000000000000000000000000000000000000..b4f19cce225e43e7b0c23563245c19ebe5ed3f0c
GIT binary patch

index 11db46448354..d3d0ba373eb6 100644
@@ -27,6 +27,7 @@ the Linux memory management.
 
    concepts
    cma_debugfs
+   data_access_monitor
    hugetlbpage
    idle_page_tracking
    ksm

2.17.1

From: SeongJae Park <[email protected]>

This commit adds kunit based unit tests for DAMON.

---
 mm/Kconfig      |  11 +
 mm/damon-test.h | 622 ++++++++++++++++++++++++++++++++++++++++++++++++
 mm/damon.c      |   6 +
 3 files changed, 639 insertions(+)
 create mode 100644 mm/damon-test.h

index ecea0889ea35..91473ed9e7c7 100644
@@ -879,4 +879,15 @@ config DAMON
 	  and 2) sufficiently light-weight so that it can be applied online.
 	  If unsure, say N.
 
+config DAMON_KUNIT_TEST
+	bool "Test for damon"
+	depends on DAMON=y && KUNIT
+	help
+	  This builds the DAMON Kunit test suite.
+
+	  For more information on KUnit and unit tests in general, please refer
+	  to the KUnit documentation.
+
+	  If unsure, say N.
+
 endmenu

index af6f395fe06c..2c44e0860672 100644
@@ -25,7 +25,11 @@
 #include <trace/events/damon.h>
 
 /* Minimal region size.  Every damon_region is aligned by this. */
+#ifndef CONFIG_DAMON_KUNIT_TEST
 #define MIN_REGION PAGE_SIZE
+#else
+#define MIN_REGION 1
+#endif
 
 #define damon_get_task_struct(t) \
 	(get_pid_task(find_vpid(t->pid), PIDTYPE_PID))

@@ -1508,3 +1512,5 @@ module_exit(damon_exit);
 MODULE_LICENSE("GPL");
 MODULE_AUTHOR("SeongJae Park <[email protected]>");
 MODULE_DESCRIPTION("DAMON: Data Access MONitor");
+
+#include "damon-test.h"

2.17.1

From: SeongJae Park <[email protected]>

This commit adds another unit test case for the recording setup.

---
 mm/damon-test.h | 13 +++++++++++++
 1 file changed, 13 insertions(+)

index cf715529ff64..5b18619efe72 100644
@@ -137,6 +137,18 @@ static void damon_test_set_pids(struct kunit *test)
 	KUNIT_EXPECT_STREQ(test, (char *)buf, "\n");
 }
 
+static void damon_test_set_recording(struct kunit *test)
+{
+	struct damon_ctx *ctx = &damon_user_ctx;
+
+	damon_set_recording(ctx, 4242, "foo.bar");
+	KUNIT_EXPECT_EQ(test, ctx->rbuf_len, 4242u);
+	KUNIT_EXPECT_STREQ(test, ctx->rfile_path, "foo.bar");
+	damon_set_recording(ctx, 42, "foo");
+	KUNIT_EXPECT_EQ(test, ctx->rbuf_len, 42u);
+	KUNIT_EXPECT_STREQ(test, ctx->rfile_path, "foo");
+}
+
 /*
  * Test damon_three_regions_in_vmas() function
  *

@@ -596,6 +608,7 @@ static struct kunit_case damon_test_cases[] = {
 	KUNIT_CASE(damon_test_tasks),
 	KUNIT_CASE(damon_test_regions),
 	KUNIT_CASE(damon_test_set_pids),
+	KUNIT_CASE(damon_test_set_recording),
 	KUNIT_CASE(damon_test_three_regions_in_vmas),
 	KUNIT_CASE(damon_test_aggregate),
 	KUNIT_CASE(damon_test_write_rbuf),

2.17.1

Thanks for the review! As the previous patch is also for the kunit test and it already received your 'Reviewed-by', I would like to merge this patch into the previous one in the next spin. If there is any problem, please let me know.

Thanks,
SeongJae Park

No problem. Feel free to do so.

From: SeongJae Park <[email protected]>

This commit adds a simple user space tests for DAMON. The tests are using kselftest framework.

---
 tools/testing/selftests/damon/Makefile        |   7 +
 .../selftests/damon/_chk_dependency.sh        |  28 ++++
 tools/testing/selftests/damon/_chk_record.py  | 108 ++++++++++++++
 .../testing/selftests/damon/debugfs_attrs.sh  | 139 ++++++++++++++++++
 .../testing/selftests/damon/debugfs_record.sh |  50 +++++++
 5 files changed, 332 insertions(+)
 create mode 100644 tools/testing/selftests/damon/Makefile
 create mode 100644 tools/testing/selftests/damon/_chk_dependency.sh
 create mode 100644 tools/testing/selftests/damon/_chk_record.py
 create mode 100755 tools/testing/selftests/damon/debugfs_attrs.sh
 create mode 100755 tools/testing/selftests/damon/debugfs_record.sh

new file mode 100644
index 000000000000..cfd5393a4639
@@ -0,0 +1,7 @@
+# SPDX-License-Identifier: GPL-2.0
+# Makefile for damon selftests
+
+TEST_FILES = _chk_dependency.sh _chk_record_file.py
+TEST_PROGS = debugfs_attrs.sh debugfs_record.sh
+
+include ../lib.mk

new file mode 100644
index 000000000000..814dcadd5e96
@@ -0,0 +1,28 @@
+#!/bin/bash
+# SPDX-License-Identifier: GPL-2.0
+
+# Kselftest framework requirement - SKIP code is 4.
+ksft_skip=4
+
+DBGFS=/sys/kernel/debug/damon
+
+if [ $EUID -ne 0 ];
+then
+	echo "Run as root"
+	exit $ksft_skip
+fi
+
+if [ ! -d $DBGFS ]
+then
+	echo "$DBGFS not found"
+	exit $ksft_skip
+fi
+
+for f in attrs record pids monitor_on
+do
+	if [ ! -f "$DBGFS/$f" ]
+	then
+		echo "$f not found"
+		exit 1
+	fi
+done

2.17.1

From: SeongJae Park <[email protected]>

This commit updates MAINTAINERS file for DAMON related files.

---
 MAINTAINERS | 12 ++++++++++++
 1 file changed, 12 insertions(+)

index 50659d76976b..2396a9098715 100644
@@ -4686,6 +4686,18 @@ F:	net/ax25/ax25_out.c
 F:	net/ax25/ax25_timer.c
 F:	net/ax25/sysctl_net_ax25.c
 
+DATA ACCESS MONITOR
+M:	SeongJae Park <[email protected]>
+L:	[email protected]
+S:	Maintained
+F:	Documentation/admin-guide/mm/damon/*
+F:	include/linux/damon.h
+F:	include/trace/events/damon.h
+F:	mm/damon-test.h
+F:	mm/damon.c
+F:	tools/damon/*
+F:	tools/testing/selftests/damon/*
+
 DAVICOM FAST ETHERNET (DMFE) NETWORK DRIVER
 L:	[email protected]
 S:	Orphan

2.17.1