[v3,00/11] Introduce Data Access MONitor (DAMON)

Message

SeongJae Park Feb. 4, 2020, 6:23 a.m. UTC

From: SeongJae Park <[e-mail]>

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

Memory management decisions can normally be more efficient if finer data access
informations are available.  However, because finer information usually comes
with higher overhead, most systems including Linux made a tradeoff: Forgive
some wise decisions and use coarse information and/or light-weight heuristics.

A number of experimental data access pattern awared memory management
optimizations (refer to 'Appendix D' for more detail) say the sacrifices are
huge (2.55x slowdown).  However, none of those has successfully adopted to
Linux kernel mainly due to the absence of a scalable and efficient data access
monitoring mechanism.  Refer to 'Appendix C' to see the limitations of existing
memory monitoring mechanisms.

DAMON is a data access monitoring solution for the problem.  It is 1) accurate
enough for the DRAM level memory management, 2) light-weight enough to be
applied online, and 3) keeps predefined upper-bound overhead regardless of the
size of target workloads (thus scalable).  Refer to 'Appendix A: Mechanisms of
DAMON' if you interested in how it is possible.

DAMON is implemented as a standalone kernel module and provides several simple
interfaces.  Owing to that, though it has mainly designed for the kernel's
memory management mechanisms, it can be also used for a wide range of user
space programs and people.  Refer to 'Appendix B: Expectd Use-cases' for more
detailed expected usages of DAMON.


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

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

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

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


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

A prototype of DAMON has evaluated on an Intel Xeon E7-8837 machine using 20
benchmarks that picked from SPEC CPU 2006, NAS, Tensorflow Benchmark,
SPLASH-2X, and PARSEC 3 benchmark suite.  Nonethless, this section provides
only summary of the results.  For more detail, please refer to the slides used
for the introduction of DAMON at the Linux Plumbers Conference 2019[1] or the
MIDDLEWARE'19 industrial track paper[2].


Quality
-------

We first traced and visualized the data access pattern of each workload.  We
were able to confirm that the visualized results are reasonably accurate by
manually comparing those with the source code of the workloads.

To see the usefulness of the monitoring, we optimized 9 memory intensive
workloads among them for memory pressure situations using the DAMON outputs.
In detail, we identified frequently accessed memory regions in each workload
based on the DAMON results and protected them with ``mlock()`` system calls.
The optimized versions consistently show speedup (2.55x in best case, 1.65x in
average) under memory pressure situation.


Overhead
--------

We also measured the overhead of DAMON.  It was not only under the upperbound
we set, but was much lower (0.6 percent of the bound in best case, 13.288
percent of the bound in average).  This reduction of the overhead is mainly
resulted from the adaptive regions adjustment.  We also compared the overhead
with that of the straightforward periodic Accessed bit check-based monitoring,
which checks the access of every page frame.  DAMON's overhead was much smaller
than the straightforward mechanism by 94,242.42x in best case, 3,159.61x in
average.


References
==========

Prototypes of DAMON have introduced by an LPC kernel summit track talk[1] and
two academic papers[2,3].  Please refer to those for more detailed information,
especially the evaluations.

[1] SeongJae Park, Tracing Data Access Pattern with Bounded Overhead and
    Best-effort Accuracy. In The Linux Kernel Summit, September 2019.
    https://linuxplumbersconf.org/event/4/contributions/548/
[2] SeongJae Park, Yunjae Lee, Heon Y. Yeom, Profiling Dynamic Data Access
    Patterns with Controlled Overhead and Quality. In 20th ACM/IFIP
    International Middleware Conference Industry, December 2019.
    https://dl.acm.org/doi/10.1145/3366626.3368125
[3] SeongJae Park, Yunjae Lee, Yunhee Kim, Heon Y. Yeom, Profiling Dynamic Data
    Access Patterns with Bounded Overhead and Accuracy. In IEEE International
    Workshop on Foundations and Applications of Self- Systems (FAS 2019), June
    2019.


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

The patches are organized in the following sequence.  The first patch
introduces DAMON module and it's small common functions.  Following three
patches (2nd to 4th) implement the core logics of DAMON, regions based
sampling, adaptive regions adjustment, and dynamic memory mapping chage
adoption, one by one.

Next three patches (5th to 7th) adds interfaces of DAMON.  Each of those adds
an api for other kernel code, a debugfs interface for super users and a
tracepoint for other tracepoint supporting tracers such as perf.

To provide a minimal reference to the debugfs interface and for more convenient
use/tests of the DAMON, the next patch (8th) implements an user space tool.
The 9th patch adds a document for administrators of DAMON, and the 10th patch
provides DAMON's kunit tests.  Finally, the last patch (11th) updates the
MAINTAINERS file.

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

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

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


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

Changes from v2
(https://lore.kernel.org/linux-mm/[e-mail]/)
 - Move MAINTAINERS changes to last commit (Brendan Higgins)
 - Add descriptions for kunittest: why not only entire mappings and what the 4
   input sets are trying to test (Brendan Higgins)
 - Remove 'kdamond_need_stop()' test (Brendan Higgins)
 - Discuss about the 'perf mem' and DAMON (Peter Zijlstra)
 - Make CV clearly say what it actually does (Peter Zijlstra)
 - Answer why new module (Qian Cai)
 - Diable DAMON by default (Randy Dunlap)
 - Change the interface: Seperate recording attributes
   (attrs, record, rules) and allow multiple kdamond instances
 - Implement kernel API interface

Changes from v1
(https://lore.kernel.org/linux-mm/[e-mail]/)
 - Rebase on v5.5
 - Add a tracepoint for integration with other tracers (Kirill A. Shutemov)
 - document: Add more description for the user space tool (Brendan Higgins)
 - unittest: Improve readability (Brendan Higgins)
 - unittest: Use consistent name and helpers function (Brendan Higgins)
 - Update PG_Young to avoid reclaim logic interference (Yunjae Lee)

Changes from RFC
(https://lore.kernel.org/linux-mm/[e-mail]/)
 - Specify an ambiguous plan of access pattern based mm optimizations
 - Support loadable module build
 - Cleanup code

SeongJae Park (11):
  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 kernel space API
  mm/damon: Add debugfs interface
  mm/damon: Add a tracepoint for result writing
  mm/damon: Add minimal user-space tools
  Documentation/admin-guide/mm: Add a document for DAMON
  mm/damon: Add kunit tests
  MAINTAINERS: Update for DAMON

 .../admin-guide/mm/data_access_monitor.rst    |  414 +++++
 Documentation/admin-guide/mm/index.rst        |    1 +
 MAINTAINERS                                   |   11 +
 include/linux/damon.h                         |   71 +
 include/trace/events/damon.h                  |   32 +
 mm/Kconfig                                    |   23 +
 mm/Makefile                                   |    1 +
 mm/damon-test.h                               |  604 +++++++
 mm/damon.c                                    | 1412 +++++++++++++++++
 tools/damon/.gitignore                        |    1 +
 tools/damon/_dist.py                          |   35 +
 tools/damon/bin2txt.py                        |   64 +
 tools/damon/damo                              |   37 +
 tools/damon/heats.py                          |  358 +++++
 tools/damon/nr_regions.py                     |   88 +
 tools/damon/record.py                         |  219 +++
 tools/damon/report.py                         |   45 +
 tools/damon/wss.py                            |   94 ++
 18 files changed, 3510 insertions(+)
 create mode 100644 Documentation/admin-guide/mm/data_access_monitor.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/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