Skip to contentSkip to conversation

Implement Data Access Monitoring-based Memory Operation Schemes

RFC Superseded SeongJae Park 2 participants 12 messages Jun 9, 2020

Subsystems (6)

v11 of 15 Superseded Latest is v15 →

lore
Share & tools
lore
#0 lore raw

v11 cover Implement Data Access Monitoring-based Memory Operation Schemes

From: SeongJae Park <[email protected]>

DAMON[1] can be used as a primitive for data access awared memory management optimizations. For that, users who want such optimizations should run DAMON, read the monitoring results, analyze it, plan a new memory management scheme, and apply the new scheme by themselves. Such efforts will be inevitable for some complicated optimizations.

However, in many other cases, the users would simply want the system to apply a memory management action to a memory region of a specific size having a specific access frequency for a specific time. For example, "page out a memory region larger than 100 MiB keeping only rare accesses more than 2 minutes", or "Do not use THP for a memory region larger than 2 MiB rarely accessed for more than 1 seconds".

This RFC patchset makes DAMON to handle such data access monitoring-based operation schemes. With this change, users can do the data access aware optimizations by simply specifying their schemes to DAMON.

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

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 RFC v9 of this 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 the latest DAMON patchset for detailed evaluation setup and results.

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

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-damos
[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 Tree
==============================

The patches are based on the v5.7 plus v15 DAMON patchset[1] and Minchan's ``do_madvise()`` patch[2], which retrieved from linux-next/master and slightly modified for backporting on v5.7. You can also clone the complete git tree:

    $ git clone git://github.com/sjp38/linux -b damos/rfc/v11

The web is also available:
https://github.com/sjp38/linux/releases/tag/damos/rfc/v11

There are a couple of trees for entire DAMON patchset series that future features are included. The first one[3] contains the changes for latest release, while the other one[4] contains the changes for next release.

[1] TODO: Add DAMON v15 patchset link
[2] https://lore.kernel.org/linux-mm/[email protected]/
[3] https://github.com/sjp38/linux/tree/damon/master
[4] https://github.com/sjp38/linux/tree/damon/next

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

The 1st patch allows DAMON to reuse ``madvise()`` code for the actions. The 2nd patch accounts age of each region. The 3rd patch implements the handling of the schemes in DAMON and exports a kernel space programming interface for it. The 4th patch implements a debugfs interface for the privileged people and user programs. The 5th patch implements schemes statistics feature for easier tuning of the schemes and runtime access pattern analysis. The 6th patche adds selftests for these changes, and the 7th patch adds human friendly schemes support to the user space tool for DAMON. Finally, the 8th patch documents this new feature in the document.

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

Changes from RFC v10
(https://lore.kernel.org/linux-mm/[email protected]/)
- Fix the wrong error handling for schemes debugfs file
- Handle the schemes stats from the user space tool
- Remove the schemes implementation plan from the document

Changes from RFC v9
(https://lore.kernel.org/linux-mm/[email protected]/)
- Rebase on v5.7
- Fix wrong comments and documents for schemes apply conditions

Changes from RFC v8
(https://lore.kernel.org/linux-mm/[email protected]/)
- Rewrite the document (Stefan Nuernberger)
- Make 'damon_for_each_*' argument order consistent (Leonard Foerster)
- Implement statistics for schemes
- Avoid races between debugfs readers and writers
- Reset age for only significant access frequency changes
- Add kernel-doc comments in damon.h

Changes from RFC v7
(https://lore.kernel.org/linux-mm/[email protected]/)
- Rebase on DAMON v11 patchset
- Add documentation

Changes from RFC v6
(https://lore.kernel.org/linux-mm/[email protected]/)
- Rebase on DAMON v9 patchset
- Cleanup code and fix typos (Stefan Nuernberger)

Changes from RFC v5
(https://lore.kernel.org/linux-mm/[email protected]/)
- Rebase on DAMON v8 patchset
- Update test results
- Fix DAMON userspace tool crash on signal handling
- Fix checkpatch warnings

Changes from RFC v4
(https://lore.kernel.org/linux-mm/[email protected]/)
- Handle CONFIG_ADVISE_SYSCALL
- Clean up code (Jonathan Cameron)
- Update test results
- Rebase on v5.6 + DAMON v7

Changes from RFC v3
(https://lore.kernel.org/linux-mm/[email protected]/)
- Add Reviewed-by from Brendan Higgins
- Code cleanup: Modularize madvise() call
- Fix a trivial bug in the wrapper python script
- Add more stable and detailed evaluation results with updated ETHP scheme

Changes from RFC v2
(https://lore.kernel.org/linux-mm/[email protected]/)
- Fix aging mechanism for more better 'old region' selection
- Add more kunittests and kselftests for this patchset
- Support more human friedly description and application of 'schemes'

Changes from RFC v1
(https://lore.kernel.org/linux-mm/[email protected]/)
- Properly adjust age accounting related properties after splitting, merging, and action applying

SeongJae Park (8):
mm/madvise: Export do_madvise() to external GPL modules mm/damon: Account age of target regions
mm/damon: Implement data access monitoring-based operation schemes mm/damon/schemes: Implement a debugfs interface mm/damon/schemes: Implement statistics feature mm/damon/selftests: Add 'schemes' debugfs tests damon/tools: Support more human friendly 'schemes' control Documentation/admin-guide/mm: Document DAMON-based operation schemes

 Documentation/admin-guide/mm/damon/guide.rst  |  35 ++
 Documentation/admin-guide/mm/damon/plans.rst  |  26 +-
 Documentation/admin-guide/mm/damon/usage.rst  | 127 +++++-
 include/linux/damon.h                         |  66 ++++
 mm/damon.c                                    | 363 +++++++++++++++++-
 mm/madvise.c                                  |   1 +
 tools/damon/_convert_damos.py                 | 128 ++++++
 tools/damon/_damon.py                         | 146 +++++++
 tools/damon/damo                              |   7 +
 tools/damon/record.py                         | 139 +------
 tools/damon/schemes.py                        | 109 ++++++
 .../testing/selftests/damon/debugfs_attrs.sh  |  29 ++
 12 files changed, 1008 insertions(+), 168 deletions(-)
 create mode 100755 tools/damon/_convert_damos.py
 create mode 100644 tools/damon/_damon.py
 create mode 100644 tools/damon/schemes.py
Signature · 1 line
2.17.1
#1 lore raw

RFC v11 1/8 mm/madvise: Export do_madvise() to external GPL modules

From: SeongJae Park <[email protected]>

This commit exports 'do_madvise()' to external GPL modules, so that other modules including DAMON could use the function.

---
 mm/madvise.c | 1 +
 1 file changed, 1 insertion(+)
mm/madvise.c +1 -0
index 1ad7522567d4..fcd951694ebc 100644
@@ -1171,6 +1171,7 @@ int do_madvise(struct task_struct *target_task, struct mm_struct *mm,
 
 	return error;
 }
+EXPORT_SYMBOL_GPL(do_madvise);
 
 SYSCALL_DEFINE3(madvise, unsigned long, start, size_t, len_in, int, behavior)
 {
Signature · 1 line
2.17.1
#2 lore raw

RFC v11 2/8 mm/damon: Account age of target regions

In reply to SeongJae Park

From: SeongJae Park <[email protected]>

DAMON can be used as a primitive for data access pattern aware memory management optimizations. However, users who want such optimizations should run DAMON, read the monitoring results, analyze it, plan a new memory management scheme, and apply the new scheme by themselves. It would not be too hard, but still require some level of effort. For complicated optimizations, this effort is inevitable.

That said, in many cases, users would simply want to apply an actions to a memory region of a specific size having a specific access frequency for a specific time. For example, "page out a memory region larger than 100 MiB but having a low access frequency more than 10 minutes", or "Use THP for a memory region larger than 2 MiB having a high access frequency for more than 2 seconds".

For such optimizations, users will need to first account the age of each region themselves. To reduce such efforts, this commit implements a simple age account of each region in DAMON. For each aggregation step, DAMON compares the access frequency with that from last aggregation and reset the age of the region if the change is significant. Else, the age is incremented. Also, in case of the merge of regions, the region size-weighted average of the ages is set as the age of merged new region.

---
 include/linux/damon.h | 10 ++++++++++
 mm/damon.c            | 29 +++++++++++++++++++++--------
 2 files changed, 31 insertions(+), 8 deletions(-)
include/linux/damon.h +10 -0
index c4796a10cb1a..6a8ff2c63c2a 100644
@@ -24,6 +24,13 @@
  * @sampling_addr:	Address of the sample for the next access check.
  * @nr_accesses:	Access frequency of this region.
  * @list:		List head for siblings.
+ * @age:		Age of this region.
+ * @last_nr_accesses:	Internal value for age calculation.
+ *
+ * @age is initially zero, increased for each aggregation interval, and reset
+ * to zero again if the access frequency is significantly changed.  If two
+ * regions are merged into a new region, both @nr_accesses and @age of the new
+ * region are set as region size-weighted average of those of the two regions.
  */
 struct damon_region {
 	unsigned long vm_start;
@@ -31,6 +38,9 @@ struct damon_region {
 	unsigned long sampling_addr;
 	unsigned int nr_accesses;
 	struct list_head list;
+
+	unsigned int age;
+	unsigned int last_nr_accesses;
 };
 
 /**
mm/damon.c +21 -8
index c390a0cbc54a..17ec5fcc1b96 100644
@@ -101,6 +101,9 @@ static struct damon_region *damon_new_region(struct damon_ctx *ctx,
 	region->nr_accesses = 0;
 	INIT_LIST_HEAD(&region->list);
 
+	region->age = 0;
+	region->last_nr_accesses = 0;
+
 	return region;
 }
 
@@ -770,6 +773,7 @@ static void kdamond_reset_aggregated(struct damon_ctx *c)
 			damon_write_rbuf(c, &r->nr_accesses,
 					sizeof(r->nr_accesses));
 			trace_damon_aggregated(t, r, nr);
+			r->last_nr_accesses = r->nr_accesses;
 			r->nr_accesses = 0;
 		}
 	}
@@ -783,9 +787,11 @@ static void kdamond_reset_aggregated(struct damon_ctx *c)
 static void damon_merge_two_regions(struct damon_region *l,
 				struct damon_region *r)
 {
-	l->nr_accesses = (l->nr_accesses * sz_damon_region(l) +
-			r->nr_accesses * sz_damon_region(r)) /
-			(sz_damon_region(l) + sz_damon_region(r));
+	unsigned long sz_l = sz_damon_region(l), sz_r = sz_damon_region(r);
+
+	l->nr_accesses = (l->nr_accesses * sz_l + r->nr_accesses * sz_r) /
+			(sz_l + sz_r);
+	l->age = (l->age * sz_l + r->age * sz_r) / (sz_l + sz_r);
 	l->vm_end = r->vm_end;
 	damon_destroy_region(r);
 }
@@ -803,12 +809,16 @@ static void damon_merge_regions_of(struct damon_task *t, unsigned int thres)
 	struct damon_region *r, *prev = NULL, *next;
 
 	damon_for_each_region_safe(r, next, t) {
-		if (!prev || prev->vm_end != r->vm_start ||
-		    diff_of(prev->nr_accesses, r->nr_accesses) > thres) {
+		if (diff_of(r->nr_accesses, r->last_nr_accesses) > thres)
+			r->age = 0;
+		else
+			r->age++;
+
+		if (prev && prev->vm_end == r->vm_start &&
+		    diff_of(prev->nr_accesses, r->nr_accesses) <= thres)
+			damon_merge_two_regions(prev, r);
+		else
 			prev = r;
-			continue;
-		}
-		damon_merge_two_regions(prev, r);
 	}
 }
 
@@ -844,6 +854,9 @@ static void damon_split_region_at(struct damon_ctx *ctx,
 	new = damon_new_region(ctx, r->vm_start + sz_r, r->vm_end);
 	r->vm_end = new->vm_start;
 
+	new->age = r->age;
+	new->last_nr_accesses = r->last_nr_accesses;
+
 	damon_insert_region(new, r, damon_next_region(r));
 }
 
Signature · 1 line
2.17.1
#3 lore raw

RFC v11 3/8 mm/damon: Implement data access monitoring-based operation schemes

In reply to SeongJae Park

From: SeongJae Park <[email protected]>

In many cases, users might use DAMON for simple data access aware memory management optimizations such as applying an operation scheme to a memory region of a specific size having a specific access frequency for a specific time. For example, "page out a memory region larger than 100 MiB but having a low access frequency more than 10 minutes", or "Use THP for a memory region larger than 2 MiB having a high access frequency for more than 2 seconds".

To minimize users from spending their time for implementation of such simple data access monitoring-based operation schemes, this commit makes DAMON to handle such schemes directly. With this commit, users can simply specify their desired schemes to DAMON.

Each of the schemes is composed with conditions for filtering of the target memory regions and desired memory management action for the target. Specifically, the format is::

<min/max size> <min/max access frequency> <min/max age> <action>

The filtering conditions are size of memory region, number of accesses to the region monitored by DAMON, and the age of the region. The age of region is incremented periodically but reset when its addresses or access frequency has significantly changed or the action of a scheme was applied. For the action, current implementation supports only a few of madvise() hints, ``MADV_WILLNEED``, ``MADV_COLD``, ``MADV_PAGEOUT``, ``MADV_HUGEPAGE``, and ``MADV_NOHUGEPAGE``.

---
 include/linux/damon.h |  50 ++++++++++++++
 mm/damon.c            | 149 ++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 199 insertions(+)
include/linux/damon.h +50 -0
index 6a8ff2c63c2a..842a01e80c6e 100644
@@ -55,6 +55,52 @@ struct damon_task {
 	struct list_head list;
 };
 
+/**
+ * enum damos_action - Represents an action of a Data Access Monitoring-based
+ * Operation Scheme.
+ *
+ * @DAMOS_WILLNEED:	Call ``madvise()`` for the region with MADV_WILLNEED.
+ * @DAMOS_COLD:		Call ``madvise()`` for the region with MADV_COLD.
+ * @DAMOS_PAGEOUT:	Call ``madvise()`` for the region with MADV_PAGEOUT.
+ * @DAMOS_HUGEPAGE:	Call ``madvise()`` for the region with MADV_HUGEPAGE.
+ * @DAMOS_NOHUGEPAGE:	Call ``madvise()`` for the region with MADV_NOHUGEPAGE.
+ * @DAMOS_ACTION_LEN:	Number of supported actions.
+ */
+enum damos_action {
+	DAMOS_WILLNEED,
+	DAMOS_COLD,
+	DAMOS_PAGEOUT,
+	DAMOS_HUGEPAGE,
+	DAMOS_NOHUGEPAGE,
+	DAMOS_ACTION_LEN,
+};
+
+/**
+ * struct damos - Represents a Data Access Monitoring-based Operation Scheme.
+ * @min_sz_region:	Minimum size of target regions.
+ * @max_sz_region:	Maximum size of target regions.
+ * @min_nr_accesses:	Minimum ``->nr_accesses`` of target regions.
+ * @max_nr_accesses:	Maximum ``->nr_accesses`` of target regions.
+ * @min_age_region:	Minimum age of target regions.
+ * @max_age_region:	Maximum age of target regions.
+ * @action:		&damo_action to be applied to the target regions.
+ * @list:		List head for siblings.
+ *
+ * For each aggregation interval, DAMON applies @action to monitoring target
+ * regions fit in the condition and updates the statistics.  Note that both
+ * the minimums and the maximums are inclusive.
+ */
+struct damos {
+	unsigned int min_sz_region;
+	unsigned int max_sz_region;
+	unsigned int min_nr_accesses;
+	unsigned int max_nr_accesses;
+	unsigned int min_age_region;
+	unsigned int max_age_region;
+	enum damos_action action;
+	struct list_head list;
+};
+
 /**
  * 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
@@ -98,6 +144,7 @@ struct damon_task {
  * @kdamond_lock.  Accesses to other fields must be protected by themselves.
  *
  * @tasks_list:		Head of monitoring target tasks (&damon_task) list.
+ * @schemes_list:	Head of schemes (&damos) list.
  *
  * @sample_cb:			Called for each sampling interval.
  * @aggregate_cb:		Called for each aggregation interval.
@@ -128,6 +175,7 @@ struct damon_ctx {
 	struct mutex kdamond_lock;
 
 	struct list_head tasks_list;	/* 'damon_task' objects */
+	struct list_head schemes_list;	/* 'damos' objects */
 
 	/* callbacks */
 	void (*sample_cb)(struct damon_ctx *context);
@@ -138,6 +186,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_schemes(struct damon_ctx *ctx,
+			struct damos **schemes, ssize_t nr_schemes);
 int damon_set_recording(struct damon_ctx *ctx,
 				unsigned int rbuf_len, char *rfile_path);
 int damon_start(struct damon_ctx *ctx);
mm/damon.c +149 -0

191 lines not on this page · raw message

Signature · 1 line
2.17.1
#4 lore raw

Re: [RFC v11 3/8] mm/damon: Implement data access monitoring-based operation schemes

Quoted 10 lines · SeongJae Park

From: SeongJae Park <[email protected]>

In many cases, users might use DAMON for simple data access aware memory management optimizations such as applying an operation scheme to a memory region of a specific size having a specific access frequency for a specific time. For example, "page out a memory region larger than 100 MiB but having a low access frequency more than 10 minutes", or "Use THP for a memory region larger than 2 MiB having a high access frequency for more than 2 seconds".

Quoted 4 lines

To minimize users from spending their time for implementation of such simple data access monitoring-based operation schemes, this commit makes DAMON to handle such schemes directly. With this commit, users can simply specify their desired schemes to DAMON.

What would be the alternative? How would a solution where these policies are handled by user space (or inside an application?) look like?

Quoted 7 lines

Each of the schemes is composed with conditions for filtering of the target memory regions and desired memory management action for the target. Specifically, the format is::

<min/max size> <min/max access frequency> <min/max age> <action>

Quoted 7 lines

The filtering conditions are size of memory region, number of accesses to the region monitored by DAMON, and the age of the region. The age of region is incremented periodically but reset when its addresses or access frequency has significantly changed or the action of a scheme was applied. For the action, current implementation supports only a few of madvise() hints, ``MADV_WILLNEED``, ``MADV_COLD``, ``MADV_PAGEOUT``, ``MADV_HUGEPAGE``, and ``MADV_NOHUGEPAGE``.

I am missing some important information. Is this specified for *all* user space processes? Or how is this configured? What are examples?

E.g., messing with ``MADV_HUGEPAGE`` vs. ``MADV_NOHUGEPAGE`` of random applications can change the behavior/break these applications. (e.g., if userfaultfd is getting used and the applciation explicitly sets MADV_NOHUGEPAGE).

Quoted 292 lines
---
 include/linux/damon.h |  50 ++++++++++++++
 mm/damon.c            | 149 ++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 199 insertions(+)
include/linux/damon.h +50 -0
index 6a8ff2c63c2a..842a01e80c6e 100644
@@ -55,6 +55,52 @@ struct damon_task {
 	struct list_head list;
 };
 
+/**
+ * enum damos_action - Represents an action of a Data Access Monitoring-based
+ * Operation Scheme.
+ *
+ * @DAMOS_WILLNEED:	Call ``madvise()`` for the region with MADV_WILLNEED.
+ * @DAMOS_COLD:		Call ``madvise()`` for the region with MADV_COLD.
+ * @DAMOS_PAGEOUT:	Call ``madvise()`` for the region with MADV_PAGEOUT.
+ * @DAMOS_HUGEPAGE:	Call ``madvise()`` for the region with MADV_HUGEPAGE.
+ * @DAMOS_NOHUGEPAGE:	Call ``madvise()`` for the region with MADV_NOHUGEPAGE.
+ * @DAMOS_ACTION_LEN:	Number of supported actions.
+ */
+enum damos_action {
+	DAMOS_WILLNEED,
+	DAMOS_COLD,
+	DAMOS_PAGEOUT,
+	DAMOS_HUGEPAGE,
+	DAMOS_NOHUGEPAGE,
+	DAMOS_ACTION_LEN,
+};
+
+/**
+ * struct damos - Represents a Data Access Monitoring-based Operation Scheme.
+ * @min_sz_region:	Minimum size of target regions.
+ * @max_sz_region:	Maximum size of target regions.
+ * @min_nr_accesses:	Minimum ``->nr_accesses`` of target regions.
+ * @max_nr_accesses:	Maximum ``->nr_accesses`` of target regions.
+ * @min_age_region:	Minimum age of target regions.
+ * @max_age_region:	Maximum age of target regions.
+ * @action:		&damo_action to be applied to the target regions.
+ * @list:		List head for siblings.
+ *
+ * For each aggregation interval, DAMON applies @action to monitoring target
+ * regions fit in the condition and updates the statistics.  Note that both
+ * the minimums and the maximums are inclusive.
+ */
+struct damos {
+	unsigned int min_sz_region;
+	unsigned int max_sz_region;
+	unsigned int min_nr_accesses;
+	unsigned int max_nr_accesses;
+	unsigned int min_age_region;
+	unsigned int max_age_region;
+	enum damos_action action;
+	struct list_head list;
+};
+
 /**
  * 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
@@ -98,6 +144,7 @@ struct damon_task {
  * @kdamond_lock.  Accesses to other fields must be protected by themselves.
  *
  * @tasks_list:		Head of monitoring target tasks (&damon_task) list.
+ * @schemes_list:	Head of schemes (&damos) list.
  *
  * @sample_cb:			Called for each sampling interval.
  * @aggregate_cb:		Called for each aggregation interval.
@@ -128,6 +175,7 @@ struct damon_ctx {
 	struct mutex kdamond_lock;
 
 	struct list_head tasks_list;	/* 'damon_task' objects */
+	struct list_head schemes_list;	/* 'damos' objects */
 
 	/* callbacks */
 	void (*sample_cb)(struct damon_ctx *context);
@@ -138,6 +186,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_schemes(struct damon_ctx *ctx,
+			struct damos **schemes, ssize_t nr_schemes);
 int damon_set_recording(struct damon_ctx *ctx,
 				unsigned int rbuf_len, char *rfile_path);
 int damon_start(struct damon_ctx *ctx);
mm/damon.c +149 -0
index 17ec5fcc1b96..1ec6fa3dd671 100644
@@ -22,6 +22,7 @@
 
 #define CREATE_TRACE_POINTS
 
+#include <asm-generic/mman-common.h>
 #include <linux/damon.h>
 #include <linux/debugfs.h>
 #include <linux/delay.h>
@@ -67,6 +68,12 @@
 #define damon_for_each_task_safe(t, next, ctx) \
 	list_for_each_entry_safe(t, next, &(ctx)->tasks_list, list)
 
+#define damon_for_each_scheme(s, ctx) \
+	list_for_each_entry(s, &(ctx)->schemes_list, list)
+
+#define damon_for_each_scheme_safe(s, next, ctx) \
+	list_for_each_entry_safe(s, next, &(ctx)->schemes_list, list)
+
 #define MAX_RECORD_BUFFER_LEN	(4 * 1024 * 1024)
 #define MAX_RFILE_PATH_LEN	256
 
@@ -181,6 +188,27 @@ static void damon_destroy_task(struct damon_task *t)
 	damon_free_task(t);
 }
 
+static void damon_add_scheme(struct damon_ctx *ctx, struct damos *s)
+{
+	list_add_tail(&s->list, &ctx->schemes_list);
+}
+
+static void damon_del_scheme(struct damos *s)
+{
+	list_del(&s->list);
+}
+
+static void damon_free_scheme(struct damos *s)
+{
+	kfree(s);
+}
+
+static void damon_destroy_scheme(struct damos *s)
+{
+	damon_del_scheme(s);
+	damon_free_scheme(s);
+}
+
 static unsigned int nr_damon_tasks(struct damon_ctx *ctx)
 {
 	struct damon_task *t;
@@ -779,6 +807,101 @@ static void kdamond_reset_aggregated(struct damon_ctx *c)
 	}
 }
 
+#ifndef CONFIG_ADVISE_SYSCALLS
+static int damos_madvise(struct damon_task *task, struct damon_region *r,
+			int behavior)
+{
+	return -EINVAL;
+}
+#else
+static int damos_madvise(struct damon_task *task, struct damon_region *r,
+			int behavior)
+{
+	struct task_struct *t;
+	struct mm_struct *mm;
+	int ret = -ENOMEM;
+
+	t = damon_get_task_struct(task);
+	if (!t)
+		goto out;
+	mm = damon_get_mm(task);
+	if (!mm)
+		goto put_task_out;
+
+	ret = do_madvise(t, mm, PAGE_ALIGN(r->vm_start),
+			PAGE_ALIGN(r->vm_end - r->vm_start), behavior);
+	mmput(mm);
+put_task_out:
+	put_task_struct(t);
+out:
+	return ret;
+}
+#endif	/* CONFIG_ADVISE_SYSCALLS */
+
+static int damos_do_action(struct damon_task *task, struct damon_region *r,
+			enum damos_action action)
+{
+	int madv_action;
+
+	switch (action) {
+	case DAMOS_WILLNEED:
+		madv_action = MADV_WILLNEED;
+		break;
+	case DAMOS_COLD:
+		madv_action = MADV_COLD;
+		break;
+	case DAMOS_PAGEOUT:
+		madv_action = MADV_PAGEOUT;
+		break;
+	case DAMOS_HUGEPAGE:
+		madv_action = MADV_HUGEPAGE;
+		break;
+	case DAMOS_NOHUGEPAGE:
+		madv_action = MADV_NOHUGEPAGE;
+		break;
+	default:
+		pr_warn("Wrong action %d\n", action);
+		return -EINVAL;
+	}
+
+	return damos_madvise(task, r, madv_action);
+}
+
+static void damon_do_apply_schemes(struct damon_ctx *c, struct damon_task *t,
+				struct damon_region *r)
+{
+	struct damos *s;
+	unsigned long sz;
+
+	damon_for_each_scheme(s, c) {
+		sz = r->vm_end - r->vm_start;
+		if ((s->min_sz_region && sz < s->min_sz_region) ||
+				(s->max_sz_region && s->max_sz_region < sz))
+			continue;
+		if ((s->min_nr_accesses && r->nr_accesses < s->min_nr_accesses)
+				|| (s->max_nr_accesses &&
+					s->max_nr_accesses < r->nr_accesses))
+			continue;
+		if ((s->min_age_region && r->age < s->min_age_region) ||
+				(s->max_age_region &&
+				 s->max_age_region < r->age))
+			continue;
+		damos_do_action(t, r, s->action);
+		r->age = 0;
+	}
+}
+
+static void kdamond_apply_schemes(struct damon_ctx *c)
+{
+	struct damon_task *t;
+	struct damon_region *r;
+
+	damon_for_each_task(t, c) {
+		damon_for_each_region(r, t)
+			damon_do_apply_schemes(c, t, r);
+	}
+}
+
 #define sz_damon_region(r) (r->vm_end - r->vm_start)
 
 /*
@@ -1001,6 +1124,7 @@ static int kdamond_fn(void *data)
 			kdamond_merge_regions(ctx, max_nr_accesses / 10);
 			if (ctx->aggregate_cb)
 				ctx->aggregate_cb(ctx);
+			kdamond_apply_schemes(ctx);
 			kdamond_reset_aggregated(ctx);
 			kdamond_split_regions(ctx);
 		}
@@ -1081,6 +1205,30 @@ int damon_stop(struct damon_ctx *ctx)
 	return -EPERM;
 }
 
+/**
+ * damon_set_schemes() - Set data access monitoring based operation schemes.
+ * @ctx:	monitoring context
+ * @schemes:	array of the schemes
+ * @nr_schemes:	number of entries in @schemes
+ *
+ * This function should not be called while the kdamond of the context is
+ * running.
+ *
+ * Return: 0 if success, or negative error code otherwise.
+ */
+int damon_set_schemes(struct damon_ctx *ctx, struct damos **schemes,
+			ssize_t nr_schemes)
+{
+	struct damos *s, *next;
+	ssize_t i;
+
+	damon_for_each_scheme_safe(s, next, ctx)
+		damon_destroy_scheme(s);
+	for (i = 0; i < nr_schemes; i++)
+		damon_add_scheme(ctx, schemes[i]);
+	return 0;
+}
+
 /**
  * damon_set_pids() - Set monitoring target processes.
  * @ctx:	monitoring context
@@ -1525,6 +1673,7 @@ static int __init damon_init_user_ctx(void)
 	mutex_init(&ctx->kdamond_lock);
 
 	INIT_LIST_HEAD(&ctx->tasks_list);
+	INIT_LIST_HEAD(&ctx->schemes_list);
 
 	return 0;
 }
Signature · 3 lines
Thanks,

David / dhildenb
#5 lore raw

Re: Re: [RFC v11 3/8] mm/damon: Implement data access monitoring-based operation schemes

Quoted 11 lines · On Tue, 9 Jun 2020 10:47:45 +0200 David Hildenbrand <[email protected]> wrote:
Quoted 10 lines · SeongJae Park

From: SeongJae Park <[email protected]>

In many cases, users might use DAMON for simple data access aware memory management optimizations such as applying an operation scheme to a memory region of a specific size having a specific access frequency for a specific time. For example, "page out a memory region larger than 100 MiB but having a low access frequency more than 10 minutes", or "Use THP for a memory region larger than 2 MiB having a high access frequency for more than 2 seconds".

Quoted 7 lines
Quoted 4 lines

To minimize users from spending their time for implementation of such simple data access monitoring-based operation schemes, this commit makes DAMON to handle such schemes directly. With this commit, users can simply specify their desired schemes to DAMON.

What would be the alternative? How would a solution where these policies are handled by user space (or inside an application?) look like?

Most simple form of the altermative solution would be doing offline data access pattern profiling using DAMON and modifying the application source code or system configuration based on the profiling results.

More automated alternative solution would be a daemon constructed with two modules:

- monitor: monitors the data access pattern of the workload via the DAMON debugfs interface
- memory manager: based on the monitoring result, make appropriate memory management changes via mlock(), madvise(), sysctl, etc.

The daemon would be able to run inside the application process as a thread, or outside as a standalone process. If the daemon could not run inside the application process, the memory management changes it could make would be further limited, though, as mlock() and madvise() would not be available. The madvise_process(), which is already merged in the next tree, would be helpful in this case.

Quoted 15 lines
Quoted 7 lines

Each of the schemes is composed with conditions for filtering of the target memory regions and desired memory management action for the target. Specifically, the format is::

<min/max size> <min/max access frequency> <min/max age> <action>

Quoted 7 lines

The filtering conditions are size of memory region, number of accesses to the region monitored by DAMON, and the age of the region. The age of region is incremented periodically but reset when its addresses or access frequency has significantly changed or the action of a scheme was applied. For the action, current implementation supports only a few of madvise() hints, ``MADV_WILLNEED``, ``MADV_COLD``, ``MADV_PAGEOUT``, ``MADV_HUGEPAGE``, and ``MADV_NOHUGEPAGE``.

Quoted 7 lines

I am missing some important information. Is this specified for *all* user space processes? Or how is this configured? What are examples?

E.g., messing with ``MADV_HUGEPAGE`` vs. ``MADV_NOHUGEPAGE`` of random applications can change the behavior/break these applications. (e.g., if userfaultfd is getting used and the applciation explicitly sets MADV_NOHUGEPAGE).

Only monitoring target processes will be applied. The monitoring target processes can be specified by writing the process ids to 'pids' debugfs file or constructing the 'struct damon_ctx' via the programming interface.

I will refine the commit message to make the points clearer, in the next spin.

[...]

Quoted 6 lines
Signature · 4 lines
-- 
Thanks,

David / dhildenb
#6 lore raw

Re: [RFC v11 3/8] mm/damon: Implement data access monitoring-based operation schemes

Quoted 63 lines · SeongJae Park
Quoted 11 lines · On Tue, 9 Jun 2020 10:47:45 +0200 David Hildenbrand <[email protected]> wrote:
Quoted 10 lines · SeongJae Park

From: SeongJae Park <[email protected]>

In many cases, users might use DAMON for simple data access aware memory management optimizations such as applying an operation scheme to a memory region of a specific size having a specific access frequency for a specific time. For example, "page out a memory region larger than 100 MiB but having a low access frequency more than 10 minutes", or "Use THP for a memory region larger than 2 MiB having a high access frequency for more than 2 seconds".

Quoted 7 lines
Quoted 4 lines

To minimize users from spending their time for implementation of such simple data access monitoring-based operation schemes, this commit makes DAMON to handle such schemes directly. With this commit, users can simply specify their desired schemes to DAMON.

What would be the alternative? How would a solution where these policies are handled by user space (or inside an application?) look like?

Most simple form of the altermative solution would be doing offline data access pattern profiling using DAMON and modifying the application source code or system configuration based on the profiling results.

More automated alternative solution would be a daemon constructed with two modules:

- monitor: monitors the data access pattern of the workload via the DAMON debugfs interface
- memory manager: based on the monitoring result, make appropriate memory management changes via mlock(), madvise(), sysctl, etc.

The daemon would be able to run inside the application process as a thread, or outside as a standalone process. If the daemon could not run inside the application process, the memory management changes it could make would be further limited, though, as mlock() and madvise() would not be available. The madvise_process(), which is already merged in the next tree, would be helpful in this case.

Quoted 15 lines
Quoted 7 lines

Each of the schemes is composed with conditions for filtering of the target memory regions and desired memory management action for the target. Specifically, the format is::

<min/max size> <min/max access frequency> <min/max age> <action>

Quoted 7 lines

The filtering conditions are size of memory region, number of accesses to the region monitored by DAMON, and the age of the region. The age of region is incremented periodically but reset when its addresses or access frequency has significantly changed or the action of a scheme was applied. For the action, current implementation supports only a few of madvise() hints, ``MADV_WILLNEED``, ``MADV_COLD``, ``MADV_PAGEOUT``, ``MADV_HUGEPAGE``, and ``MADV_NOHUGEPAGE``.

Quoted 7 lines

I am missing some important information. Is this specified for *all* user space processes? Or how is this configured? What are examples?

E.g., messing with ``MADV_HUGEPAGE`` vs. ``MADV_NOHUGEPAGE`` of random applications can change the behavior/break these applications. (e.g., if userfaultfd is getting used and the applciation explicitly sets MADV_NOHUGEPAGE).

Quoted 5 lines

Only monitoring target processes will be applied. The monitoring target processes can be specified by writing the process ids to 'pids' debugfs file or constructing the 'struct damon_ctx' via the programming interface.

I will refine the commit message to make the points clearer, in the next spin.

Understood, so a process configures damon to only modify its mappings. thanks for clarifying! This makes exposing the do_madvise() look less dangerous.

Signature · 3 lines
Thanks,

David / dhildenb
#7 lore raw

RFC v11 4/8 mm/damon/schemes: Implement a debugfs interface

In reply to SeongJae Park

From: SeongJae Park <[email protected]>

This commit implements a debugfs interface for the data access monitoring oriented memory management schemes. It is supposed to be used by administrators and/or privileged user space programs. Users can read and update the rules using ``<debugfs>/damon/schemes`` file. The format is::

<min/max size> <min/max access frequency> <min/max age> <action>

---
 mm/damon.c | 178 ++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 176 insertions(+), 2 deletions(-)
mm/damon.c +176 -2
index 1ec6fa3dd671..0d12a74aba58 100644
@@ -188,6 +188,29 @@ static void damon_destroy_task(struct damon_task *t)
 	damon_free_task(t);
 }
 
+static struct damos *damon_new_scheme(
+		unsigned int min_sz_region, unsigned int max_sz_region,
+		unsigned int min_nr_accesses, unsigned int max_nr_accesses,
+		unsigned int min_age_region, unsigned int max_age_region,
+		enum damos_action action)
+{
+	struct damos *scheme;
+
+	scheme = kmalloc(sizeof(*scheme), GFP_KERNEL);
+	if (!scheme)
+		return NULL;
+	scheme->min_sz_region = min_sz_region;
+	scheme->max_sz_region = max_sz_region;
+	scheme->min_nr_accesses = min_nr_accesses;
+	scheme->max_nr_accesses = max_nr_accesses;
+	scheme->min_age_region = min_age_region;
+	scheme->max_age_region = max_age_region;
+	scheme->action = action;
+	INIT_LIST_HEAD(&scheme->list);
+
+	return scheme;
+}
+
 static void damon_add_scheme(struct damon_ctx *ctx, struct damos *s)
 {
 	list_add_tail(&s->list, &ctx->schemes_list);
@@ -1387,6 +1410,151 @@ static ssize_t debugfs_monitor_on_write(struct file *file,
 	return ret;
 }
 
+static ssize_t sprint_schemes(struct damon_ctx *c, char *buf, ssize_t len)
+{
+	struct damos *s;
+	int written = 0;
+	int rc;
+
+	damon_for_each_scheme(s, c) {
+		rc = snprintf(&buf[written], len - written,
+				"%u %u %u %u %u %u %d\n",
+				s->min_sz_region, s->max_sz_region,
+				s->min_nr_accesses, s->max_nr_accesses,
+				s->min_age_region, s->max_age_region,
+				s->action);
+		if (!rc)
+			return -ENOMEM;
+
+		written += rc;
+	}
+	return written;
+}
+
+static ssize_t debugfs_schemes_read(struct file *file, char __user *buf,
+		size_t count, loff_t *ppos)
+{
+	struct damon_ctx *ctx = &damon_user_ctx;
+	char *kbuf;
+	ssize_t len;
+
+	kbuf = kmalloc(count, GFP_KERNEL);
+	if (!kbuf)
+		return -ENOMEM;
+
+	mutex_lock(&ctx->kdamond_lock);
+	len = sprint_schemes(ctx, kbuf, count);
+	mutex_unlock(&ctx->kdamond_lock);
+	if (len < 0)
+		goto out;
+	len = simple_read_from_buffer(buf, count, ppos, kbuf, len);
+
+out:
+	kfree(kbuf);
+	return len;
+}
+
+static void free_schemes_arr(struct damos **schemes, ssize_t nr_schemes)
+{
+	ssize_t i;
+
+	for (i = 0; i < nr_schemes; i++)
+		kfree(schemes[i]);
+	kfree(schemes);
+}
+
+/*
+ * Converts a string into an array of struct damos pointers
+ *
+ * Returns an array of struct damos pointers that converted if the conversion
+ * success, or NULL otherwise.
+ */
+static struct damos **str_to_schemes(const char *str, ssize_t len,
+				ssize_t *nr_schemes)
+{
+	struct damos *scheme, **schemes;
+	const int max_nr_schemes = 256;
+	int pos = 0, parsed, ret;
+	unsigned int min_sz, max_sz, min_nr_a, max_nr_a, min_age, max_age;
+	unsigned int action;
+
+	schemes = kmalloc_array(max_nr_schemes, sizeof(scheme),
+			GFP_KERNEL);
+	if (!schemes)
+		return NULL;
+
+	*nr_schemes = 0;
+	while (pos < len && *nr_schemes < max_nr_schemes) {
+		ret = sscanf(&str[pos], "%u %u %u %u %u %u %u%n",
+				&min_sz, &max_sz, &min_nr_a, &max_nr_a,
+				&min_age, &max_age, &action, &parsed);
+		if (ret != 7)
+			break;
+		if (action >= DAMOS_ACTION_LEN) {
+			pr_err("wrong action %d\n", action);
+			goto fail;
+		}
+
+		pos += parsed;
+		scheme = damon_new_scheme(min_sz, max_sz, min_nr_a, max_nr_a,
+				min_age, max_age, action);
+		if (!scheme)
+			goto fail;
+
+		schemes[*nr_schemes] = scheme;
+		*nr_schemes += 1;
+	}
+	return schemes;
+fail:
+	free_schemes_arr(schemes, *nr_schemes);
+	return NULL;
+}
+
+static ssize_t debugfs_schemes_write(struct file *file, const char __user *buf,
+		size_t count, loff_t *ppos)
+{
+	struct damon_ctx *ctx = &damon_user_ctx;
+	char *kbuf;
+	struct damos **schemes;
+	ssize_t nr_schemes = 0, ret;
+	int err;
+
+	if (*ppos)
+		return -EINVAL;
+
+	kbuf = kmalloc(count, GFP_KERNEL);
+	if (!kbuf)
+		return -ENOMEM;
+
+	ret = simple_write_to_buffer(kbuf, count, ppos, buf, count);
+	if (ret < 0)
+		goto out;
+
+	schemes = str_to_schemes(kbuf, ret, &nr_schemes);
+	if (!schemes) {
+		ret = -EINVAL;
+		goto out;
+	}
+
+	mutex_lock(&ctx->kdamond_lock);
+	if (ctx->kdamond) {
+		ret = -EBUSY;
+		goto unlock_out;
+	}
+
+	err = damon_set_schemes(ctx, schemes, nr_schemes);
+	if (err)
+		ret = err;
+	else
+		nr_schemes = 0;
+unlock_out:
+	mutex_unlock(&ctx->kdamond_lock);
+	free_schemes_arr(schemes, nr_schemes);
+out:
+	kfree(kbuf);
+	return ret;
+}
+
 static ssize_t damon_sprint_pids(struct damon_ctx *ctx, char *buf, ssize_t len)
 {
 	struct damon_task *t;
@@ -1618,6 +1786,12 @@ static const struct file_operations pids_fops = {
 	.write = debugfs_pids_write,
 };
 
+static const struct file_operations schemes_fops = {
+	.owner = THIS_MODULE,
+	.read = debugfs_schemes_read,
+	.write = debugfs_schemes_write,
+};
+
 static const struct file_operations record_fops = {
 	.owner = THIS_MODULE,
 	.read = debugfs_record_read,
@@ -1634,10 +1808,10 @@ static struct dentry *debugfs_root;
 
 static int __init damon_debugfs_init(void)
 {
-	const char * const file_names[] = {"attrs", "record",
+	const char * const file_names[] = {"attrs", "record", "schemes",
 		"pids", "monitor_on"};
 	const struct file_operations *fops[] = {&attrs_fops, &record_fops,
-		&pids_fops, &monitor_on_fops};
+		&schemes_fops, &pids_fops, &monitor_on_fops};
 	int i;
 
 	debugfs_root = debugfs_create_dir("damon", NULL);
Signature · 1 line
2.17.1
#8 lore raw

RFC v11 5/8 mm/damon/schemes: Implement statistics feature

In reply to SeongJae Park

From: SeongJae Park <[email protected]>

To tune the DAMON-based operation schemes, knowing how many and how large regions are affected by each of the schemes will be helful. Those stats could be used for not only the tuning, but also monitoring of the working set size and the number of regions, if the scheme does not change the program behavior too much.

For the reason, this commit implements the statistics for the schemes. The total number and size of the regions that each scheme is applied are exported to users via '->stat_count' and '->stat_sz' of 'struct damos'. Admins can also check the number by reading 'schemes' debugfs file. The last two integers now represents the stats. To allow collecting the stats without changing the program behavior, this commit also adds new scheme action, 'DAMOS_STAT'. Note that 'DAMOS_STAT' is not only making no memory operation actions, but also does not reset the age of regions.

---
 include/linux/damon.h |  6 ++++++
 mm/damon.c            | 13 ++++++++++---
 2 files changed, 16 insertions(+), 3 deletions(-)
include/linux/damon.h +6 -0
index 842a01e80c6e..e77256cf30dd 100644
@@ -64,6 +64,7 @@ struct damon_task {
  * @DAMOS_PAGEOUT:	Call ``madvise()`` for the region with MADV_PAGEOUT.
  * @DAMOS_HUGEPAGE:	Call ``madvise()`` for the region with MADV_HUGEPAGE.
  * @DAMOS_NOHUGEPAGE:	Call ``madvise()`` for the region with MADV_NOHUGEPAGE.
+ * @DAMOS_STAT:		Do nothing but count the stat.
  * @DAMOS_ACTION_LEN:	Number of supported actions.
  */
 enum damos_action {
@@ -72,6 +73,7 @@ enum damos_action {
 	DAMOS_PAGEOUT,
 	DAMOS_HUGEPAGE,
 	DAMOS_NOHUGEPAGE,
+	DAMOS_STAT,		/* Do nothing but only record the stat */
 	DAMOS_ACTION_LEN,
 };
 
@@ -84,6 +86,8 @@ enum damos_action {
  * @min_age_region:	Minimum age of target regions.
  * @max_age_region:	Maximum age of target regions.
  * @action:		&damo_action to be applied to the target regions.
+ * @stat_count:		Total number of regions that this scheme is applied.
+ * @stat_sz:		Total size of regions that this scheme is applied.
  * @list:		List head for siblings.
  *
  * For each aggregation interval, DAMON applies @action to monitoring target
@@ -98,6 +102,8 @@ struct damos {
 	unsigned int min_age_region;
 	unsigned int max_age_region;
 	enum damos_action action;
+	unsigned long stat_count;
+	unsigned long stat_sz;
 	struct list_head list;
 };
 
mm/damon.c +10 -3
index 0d12a74aba58..98fd32ace6f7 100644
@@ -206,6 +206,8 @@ static struct damos *damon_new_scheme(
 	scheme->min_age_region = min_age_region;
 	scheme->max_age_region = max_age_region;
 	scheme->action = action;
+	scheme->stat_count = 0;
+	scheme->stat_sz = 0;
 	INIT_LIST_HEAD(&scheme->list);
 
 	return scheme;
@@ -882,6 +884,8 @@ static int damos_do_action(struct damon_task *task, struct damon_region *r,
 	case DAMOS_NOHUGEPAGE:
 		madv_action = MADV_NOHUGEPAGE;
 		break;
+	case DAMOS_STAT:
+		return 0;
 	default:
 		pr_warn("Wrong action %d\n", action);
 		return -EINVAL;
@@ -909,8 +913,11 @@ static void damon_do_apply_schemes(struct damon_ctx *c, struct damon_task *t,
 				(s->max_age_region &&
 				 s->max_age_region < r->age))
 			continue;
+		s->stat_count++;
+		s->stat_sz += sz;
 		damos_do_action(t, r, s->action);
-		r->age = 0;
+		if (s->action != DAMOS_STAT)
+			r->age = 0;
 	}
 }
 
@@ -1418,11 +1425,11 @@ static ssize_t sprint_schemes(struct damon_ctx *c, char *buf, ssize_t len)
 
 	damon_for_each_scheme(s, c) {
 		rc = snprintf(&buf[written], len - written,
-				"%u %u %u %u %u %u %d\n",
+				"%u %u %u %u %u %u %d %lu %lu\n",
 				s->min_sz_region, s->max_sz_region,
 				s->min_nr_accesses, s->max_nr_accesses,
 				s->min_age_region, s->max_age_region,
-				s->action);
+				s->action, s->stat_count, s->stat_sz);
 		if (!rc)
 			return -ENOMEM;
 
Signature · 1 line
2.17.1
#9 lore raw

RFC v11 6/8 mm/damon/selftests: Add 'schemes' debugfs tests

In reply to SeongJae Park

From: SeongJae Park <[email protected]>

This commit adds simple selftets for 'schemes' debugfs file of DAMON.

---
 .../testing/selftests/damon/debugfs_attrs.sh  | 29 +++++++++++++++++++
 1 file changed, 29 insertions(+)
tools/testing/selftests/damon/debugfs_attrs.sh +29 -0
index d5188b0f71b1..4aeb2037a67e 100755
@@ -97,6 +97,35 @@ fi
 
 echo $ORIG_CONTENT > $file
 
+# Test schemes file
+file="$DBGFS/schemes"
+
+ORIG_CONTENT=$(cat $file)
+echo "1 2 3 4 5 6 3" > $file
+if [ $? -ne 0 ]
+then
+	echo "$file write fail"
+	echo $ORIG_CONTENT > $file
+	exit 1
+fi
+
+echo "1 2
+3 4 5 6 3" > $file
+if [ $? -eq 0 ]
+then
+	echo "$file multi line write success (expected fail)"
+	echo $ORIG_CONTENT > $file
+	exit 1
+fi
+
+echo > $file
+if [ $? -ne 0 ]
+then
+	echo "$file empty string writing fail"
+	echo $ORIG_CONTENT > $file
+	exit 1
+fi
+
 # Test pids file
 file="$DBGFS/pids"
 
Signature · 1 line
2.17.1
#10 lore raw

RFC v11 7/8 damon/tools: Support more human friendly 'schemes' control

In reply to SeongJae Park

From: SeongJae Park <[email protected]>

This commit implements 'schemes' subcommand of the damon userspace tool. It can be used to describe and apply the data access monitoring-based operation schemes in more human friendly fashion.

---
 tools/damon/_convert_damos.py | 128 +++++++++++++++++++++++++++++
 tools/damon/_damon.py         | 146 ++++++++++++++++++++++++++++++++++
 tools/damon/damo              |   7 ++
 tools/damon/record.py         | 139 ++++----------------------------
 tools/damon/schemes.py        | 109 +++++++++++++++++++++++++
 5 files changed, 404 insertions(+), 125 deletions(-)
 create mode 100755 tools/damon/_convert_damos.py
 create mode 100644 tools/damon/_damon.py
 create mode 100644 tools/damon/schemes.py
tools/damon/_convert_damos.py new file +128 -0
new file mode 100755
index 000000000000..23cd52980a89
@@ -0,0 +1,128 @@
+#!/usr/bin/env python3
+# SPDX-License-Identifier: GPL-2.0
+
+"""
+Change human readable data access monitoring-based operation schemes to the low
+level input for the '<debugfs>/damon/schemes' file.  Below is an example of the
+schemes written in the human readable format:
+
+    # format is:
+    # <min/max size> <min/max frequency (0-99)> <min/max age> <action>
+    #
+    # B/K/M/G/T for Bytes/KiB/MiB/GiB/TiB
+    # us/ms/s/m/h/d for micro-seconds/milli-seconds/seconds/minutes/hours/days
+    # 'null' means zero for size and age.
+
+    # if a region keeps a high access frequency for more than 100ms, put the
+    # region on the head of the LRU list (call madvise() with MADV_WILLNEED).
+    null    null    80      null    100ms   0s      willneed
+
+    # if a region keeps a low access frequency for more than 200ms and less
+    # than one hour, put the # region on the tail of the LRU list (call
+    # madvise() with MADV_COLD).
+    0B      0B      10      20      200ms   1h cold
+
+    # if a region keeps a very low access frequency for more than 1 minute,
+    # swap out the region immediately (call madvise() with MADV_PAGEOUT).
+    0B      null    0       10      60s     0s pageout
+
+    # if a region of a size bigger than 2MiB keeps a very high access frequency
+    # for more than 100ms, let the region to use huge pages (call madvise()
+    # with MADV_HUGEPAGE).
+    2M      null    90      99      100ms   0s hugepage
+
+    # If a regions of a size bigger than 2MiB keeps small access frequency for
+    # more than 100ms, avoid the region using huge pages (call madvise() with
+    # MADV_NOHUGEPAGE).
+    2M      null    0       25      100ms   0s nohugepage
+"""
+
+import argparse
+
+unit_to_bytes = {'B': 1, 'K': 1024, 'M': 1024 * 1024, 'G': 1024 * 1024 * 1024,
+        'T': 1024 * 1024 * 1024 * 1024}
+
+def text_to_bytes(txt):
+    if txt == 'null':
+        return 0
+    unit = txt[-1]
+    number = int(txt[:-1])
+    return number * unit_to_bytes[unit]
+
+unit_to_usecs = {'us': 1, 'ms': 1000, 's': 1000 * 1000, 'm': 60 * 1000 * 1000,
+        'h': 60 * 60 * 1000 * 1000, 'd': 24 * 60 * 60 * 1000 * 1000}
+
+def text_to_us(txt):
+    if txt == 'null':
+        return 0
+    unit = txt[-2:]
+    if unit in ['us', 'ms']:
+        number = int(txt[:-2])
+    else:
+        unit = txt[-1]
+        number = int(txt[:-1])
+    return number * unit_to_usecs[unit]
+
+damos_action_to_int = {'DAMOS_WILLNEED': 0, 'DAMOS_COLD': 1,
+        'DAMOS_PAGEOUT': 2, 'DAMOS_HUGEPAGE': 3, 'DAMOS_NOHUGEPAGE': 4,
+        'DAMOS_STAT': 5}
+
+def text_to_damos_action(txt):
+    return damos_action_to_int['DAMOS_' + txt.upper()]
+
+def text_to_nr_accesses(txt, max_nr_accesses):
+    if txt == 'null':
+        return 0
+    return int(int(txt) * max_nr_accesses / 100)
+
+def debugfs_scheme(line, sample_interval, aggr_interval):
+    fields = line.split()
+    if len(fields) != 7:
+        print('wrong input line: %s' % line)
+        exit(1)
+
+    limit_nr_accesses = aggr_interval / sample_interval
+    try:
+        min_sz = text_to_bytes(fields[0])
+        max_sz = text_to_bytes(fields[1])
+        min_nr_accesses = text_to_nr_accesses(fields[2], limit_nr_accesses)
+        max_nr_accesses = text_to_nr_accesses(fields[3], limit_nr_accesses)
+        min_age = text_to_us(fields[4]) / aggr_interval
+        max_age = text_to_us(fields[5]) / aggr_interval
+        action = text_to_damos_action(fields[6])
+    except:
+        print('wrong input field')
+        raise
+    return '%d\t%d\t%d\t%d\t%d\t%d\t%d' % (min_sz, max_sz, min_nr_accesses,
+            max_nr_accesses, min_age, max_age, action)
+
+def convert(schemes_file, sample_interval, aggr_interval):
+    lines = []
+    with open(schemes_file, 'r') as f:
+        for line in f:
+            if line.startswith('#'):
+                continue
+            line = line.strip()
+            if line == '':
+                continue
+            lines.append(debugfs_scheme(line, sample_interval, aggr_interval))
+    return '\n'.join(lines)
+
+def main():
+    parser = argparse.ArgumentParser()
+    parser.add_argument('input', metavar='<file>',
+            help='input file describing the schemes')
+    parser.add_argument('-s', '--sample', metavar='<interval>', type=int,
+            default=5000, help='sampling interval (us)')
+    parser.add_argument('-a', '--aggr', metavar='<interval>', type=int,
+            default=100000, help='aggregation interval (us)')
+    args = parser.parse_args()
+
+    schemes_file = args.input
+    sample_interval = args.sample
+    aggr_interval = args.aggr
+
+    print(convert(schemes_file, sample_interval, aggr_interval))
+
+if __name__ == '__main__':
+    main()
tools/damon/_damon.py new file +146 -0

146 lines not on this page · raw message

tools/damon/damo +7 -0
index 58e1099ae5fc..ce7180069bef 100755
@@ -5,6 +5,7 @@ import argparse
 
 import record
 import report
+import schemes
 
 class SubCmdHelpFormatter(argparse.RawDescriptionHelpFormatter):
     def _format_action(self, action):
@@ -25,6 +26,10 @@ parser_record = subparser.add_parser('record',
         help='record data accesses of the given target processes')
 record.set_argparser(parser_record)
 
+parser_schemes = subparser.add_parser('schemes',
+        help='apply operation schemes to the given target process')
+schemes.set_argparser(parser_schemes)
+
 parser_report = subparser.add_parser('report',
         help='report the recorded data accesses in the specified form')
 report.set_argparser(parser_report)
@@ -33,5 +38,7 @@ args = parser.parse_args()
 
 if args.command == 'record':
     record.main(args)
+elif args.command == 'schemes':
+    schemes.main(args)
 elif args.command == 'report':
     report.main(args)
tools/damon/record.py +14 -125

204 lines not on this page · raw message

tools/damon/schemes.py new file +109 -0

109 lines not on this page · raw message

Signature · 1 line
2.17.1
#11 lore raw

RFC v11 8/8 Documentation/admin-guide/mm: Document DAMON-based operation schemes

In reply to SeongJae Park

From: SeongJae Park <[email protected]>

This commit documents DAMON-based operation schemes in the DAMON document.

---
 Documentation/admin-guide/mm/damon/guide.rst |  35 +++++
 Documentation/admin-guide/mm/damon/plans.rst |  26 +---
 Documentation/admin-guide/mm/damon/usage.rst | 127 +++++++++++++++++--
 3 files changed, 155 insertions(+), 33 deletions(-)
Documentation/admin-guide/mm/damon/guide.rst +35 -0
index 4a840d1b02d4..c10f65ce721c 100644
@@ -55,6 +55,11 @@ 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 Optimization`_.
 
+If the access pattern is very frequently changing so that you cannot figure out
+what is the performance important region using your human eye, `Automated
+DAMON-based Memory Operations`_ might help the case owing to its machine-level
+microscope view.
+
 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.  If you still
 want to absorb more benefits, you should develop `Personalized DAMON
@@ -158,6 +163,36 @@ object is the hot object.
           The chronological changes of working set size.
 
 
+Automated DAMON-based Memory Operations
+---------------------------------------
+
+Though `Manual Program Optimization` works well in many cases and DAMON can
+help it, modifying the source code is not a good option in many cases.  First
+of all, the source code could be too old or unavailable.  And, many workloads
+will have complex data access patterns that even hard to distinguish hot memory
+objects and cold memory objects with the human eye.  Finding the mapping from
+the visualized access pattern to the source code and injecting the hinting
+system calls inside the code will also be quite challenging.
+
+By using DAMON-based operation schemes (DAMOS) via ``damo schemes``, you will
+be able to easily optimize your workload in such a case.  Our example schemes
+called 'efficient THP' and 'proactive reclamation' achieved significant speedup
+and memory space saves against 25 realistic workloads [2]_, [3]_.
+
+That said, note that you need careful tune of the schemes (e.g., target region
+size and age) and monitoring attributes for the successful use of this
+approach.  Because the optimal values of the parameters will be dependent on
+each system and workload, misconfiguring the parameters could result in worse
+memory management.
+
+For the tuning, you could measure the performance metrics such as IPC, TLB
+misses, and swap in/out events and adjusts the parameters based on their
+changes.  The total number and the total size of the regions that each scheme
+is applied, which are provided via the debugfs interface and the programming
+interface can also be useful.  Writing a program automating this optimal
+parameter could be an option.
+
+
 Personalized DAMON Application
 ------------------------------
 
Documentation/admin-guide/mm/damon/plans.rst +3 -23
index 96251752b3f0..8eba8a1dcb98 100644
@@ -4,25 +4,7 @@
 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 being used as a building block of the data access
-pattern aware kernel memory management subsystem optimization.  However, as
-always, some users having very special workloads will want to do their
-optimization.  DAMON will automate most of the tasks for such manual
-optimizations soon.  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]_.
+DAMON is still on its early stage.  Below plans are still under development.
 
 
 Support Various Address Spaces
@@ -42,8 +24,6 @@ primitives by themselves for their special use cases.  Monitoring of
 clean/dirty/entire page cache, NUMA nodes, specific files, or block devices
 would be examples of such use cases.
 
-An RFC patchset for this plan is available [3]_.
+An RFC patchset for this plan is available [1]_.
 
-.. [1] https://damonitor.github.io/test/result/perf/latest/html/
-.. [2] https://lore.kernel.org/linux-mm/[email protected]/
-.. [3] https://lore.kernel.org/linux-mm/[email protected]/
+.. [1] https://lore.kernel.org/linux-mm/[email protected]/
Documentation/admin-guide/mm/damon/usage.rst +117 -10

145 lines not on this page · raw message

Signature · 1 line
2.17.1