lkml.org 
[lkml]   [2020]   [Jan]   [13]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
SubjectRe: [RFC PATCH 0/5] Introduce Data Access MONitor (DAMON)
Date
Adding more recipients for comments.  The original RFC mail is available at:
https://lore.kernel.org/linux-mm/20200110131522.29964-1-sjpark@amazon.com/


Thanks,
SeongJae Park

On Fri, 10 Jan 2020 14:15:17 +0100 SeongJae Park <sjpark@amazon.com> wrote:

> From: SeongJae Park <sjpark@amazon.de>
>
> This RFC patchset introduces a new kernel module for practical monitoring of
> data accesses, namely DAMON.
>
> The patches are organized in the following sequence. The first and second
> patch introduces the core logic and the raw level user interface of DAMON,
> respectively. To provide a minimal reference to the raw level interfaces and
> for more convenient test of the DAMON itself, the third patch implements an
> user space wrapper tools for the DAMON. The fourth patch adds a document for
> the DAMON, and finally the fifth patch provides DAMON's unit tests, which is
> using the kunit framework.
>
> The patches are based on the v5.4 plus the back-ported kunit, which retrieved
> from v5.5-rc1. You can also clone the complete git tree by:
>
> $ git clone git://github.com/sjp38/linux -b damon/rfc/v1
>
> The web is also available:
> https://github.com/sjp38/linux/releases/tag/damon/rfc/v1
>
> ----
>
> 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.
>
> For the goals, DAMON utilizes its two core mechanisms, called region-based
> sampling and adaptive regions adjustment. The region-based sampling allows
> users to make their own trade-off between the quality and the overhead of the
> monitoring and set the upperbound of the monitoring overhead. Further, the
> adaptive regions adjustment mechanism makes DAMON to maximize the quality and
> minimize the overhead with its best efforts while preserving the users
> configured trade-off.
>
>
> Background
> ==========
>
> For performance-centric analysis and optimizations of memory management schemes
> (either that of kernel space or user space), the actual data access pattern of
> the workloads is highly useful. The information need to be only reasonable
> rather than strictly correct, because some level of incorrectness can be
> handled in many performance-centric domains. It also need to be taken within
> reasonably short time with only light-weight overhead.
>
> Manually extracting such data is not easy and time consuming if the target
> workload is huge and complex, even for the developers of the programs. There
> are a range of tools and techniques developed for general memory access
> investigations, and some of those could be partially used for this purpose.
> However, most of those are not practical or unscalable, mainly because those
> are designed with no consideration about the trade-off between the accuracy of
> the output and the overhead.
>
> The memory access instrumentation techniques which is applied to many tools
> such as Intel PIN is essential for correctness required cases such as invalid
> memory access bug detections. However, those usually incur high overhead which
> is unacceptable for many of the performance-centric domains. Periodic access
> checks based on H/W or S/W access counting features (e.g., the Accessed bits of
> PTEs or the PG_Idle flags of pages) can dramatically decrease the overhead by
> forgiving some of the quality, compared to the instrumentation based
> techniques. The reduced quality is still reasonable for many of the domains,
> but the overhead can arbitrarily increase as the size of the target workload
> grows. Miniature-like static region based sampling can set the upperbound of
> the overhead, but it will now decrease the quality of the output as the size of
> the workload grows.
>
>
> Related Works
> =============
>
> There are a number of researches[1,2,3,4,5,6] optimizing memory management
> mechanisms based on the actual memory access patterns that shows impressive
> results. However, most of those has no deep consideration about the monitoring
> of the accesses itself. Some of those focused on the overhead of the
> monitoring, but does not consider the accuracy scalability[6] or has additional
> dependencies[7]. Indeed, one recent research[5] about the proactive
> reclamation has also proposed[8] to the kernel community but the monitoring
> overhead was considered a main problem.
>
> [1] Subramanya R Dulloor, Amitabha Roy, Zheguang Zhao, Narayanan Sundaram,
> Nadathur Satish, Rajesh Sankaran, Jeff Jackson, and Karsten Schwan. 2016.
> Data tiering in heterogeneous memory systems. In Proceedings of the 11th
> European Conference on Computer Systems (EuroSys). ACM, 15.
> [2] Youngjin Kwon, Hangchen Yu, Simon Peter, Christopher J Rossbach, and Emmett
> Witchel. 2016. Coordinated and efficient huge page management with ingens.
> In 12th USENIX Symposium on Operating Systems Design and Implementation
> (OSDI). 705–721.
> [3] Harald Servat, Antonio J Peña, Germán Llort, Estanislao Mercadal,
> HansChristian Hoppe, and Jesús Labarta. 2017. Automating the application
> data placement in hybrid memory systems. In 2017 IEEE International
> Conference on Cluster Computing (CLUSTER). IEEE, 126–136.
> [4] Vlad Nitu, Boris Teabe, Alain Tchana, Canturk Isci, and Daniel Hagimont.
> 2018. Welcome to zombieland: practical and energy-efficient memory
> disaggregation in a datacenter. In Proceedings of the 13th European
> Conference on Computer Systems (EuroSys). ACM, 16.
> [5] Andres Lagar-Cavilla, Junwhan Ahn, Suleiman Souhlal, Neha Agarwal, Radoslaw
> Burny, Shakeel Butt, Jichuan Chang, Ashwin Chaugule, Nan Deng, Junaid
> Shahid, Greg Thelen, Kamil Adam Yurtsever, Yu Zhao, and Parthasarathy
> Ranganathan. 2019. Software-Defined Far Memory in Warehouse-Scale
> Computers. In Proceedings of the 24th International Conference on
> Architectural Support for Programming Languages and Operating Systems
> (ASPLOS). ACM, New York, NY, USA, 317–330.
> DOI:https://doi.org/10.1145/3297858.3304053
> [6] Carl Waldspurger, Trausti Saemundsson, Irfan Ahmad, and Nohhyun Park.
> 2017. Cache Modeling and Optimization using Miniature Simulations. In 2017
> USENIX Annual Technical Conference (ATC). USENIX Association, Santa
> Clara, CA, 487–498.
> https://www.usenix.org/conference/atc17/technical-sessions/
> [7] Haojie Wang, Jidong Zhai, Xiongchao Tang, Bowen Yu, Xiaosong Ma, and
> Wenguang Chen. 2018. Spindle: Informed Memory Access Monitoring. In 2018
> USENIX Annual Technical Conference (ATC). USENIX Association, Boston, MA,
> 561–574. https://www.usenix.org/conference/atc18/presentation/wang-haojie
> [8] Jonathan Corbet. 2019. Proactively reclaiming idle memory. (2019).
> https://lwn.net/Articles/787611/.
>
>
> Expected Use-cases
> ==================
>
> A straightforward usecase of DAMON would be the program behavior analysis.
> With the DAMON output, users can confirm whether the program is running as
> intended or not. This will be useful for debuggings and tests of design
> points.
>
> The monitored results can also be useful for counting the dynamic working set
> size of workloads. For the administration of memory overcommitted systems or
> selection of the environments (e.g., containers providing different amount of
> memory) for your workloads, this will be useful.
>
> If you are a programmer, you can optimize your program by managing the memory
> based on the actual data access pattern. For example, you can identify the
> dynamic hotness of your data using DAMON and call ``mlock()`` to keep your hot
> data in DRAM, or call ``madvise()`` with ``MADV_PAGEOUT`` to proactively
> reclaim cold data. Even though your program is guaranteed to not encounter
> memory pressure, you can still improve the performance by applying the DAMON
> outputs for call of ``MADV_HUGEPAGE`` and ``MADV_NOHUGEPAGE``. More creative
> optimizations would be possible. Our evaluations of DAMON includes a
> straightforward optimization using the ``mlock()``. Please refer to the below
> Evaluation section for more detail.
>
> As DAMON incurs very low overhead, such optimizations can be applied not only
> offline, but also online. Also, there is no reason to limit such optimizations
> to the user space. Several parts of the kernel's memory management mechanisms
> could be also optimized using DAMON. The reclamation, the THP (de)promotion
> decisions, and the compaction would be such a candidates. Nevertheless,
> current version of DAMON is not highly optimized for the online/in-kernel uses.
>
>
> Mechanisms of DAMON
> ===================
>
>
> Basic Access Check
> ------------------
>
> DAMON basically reports what pages are how frequently accessed. The report is
> passed to users in binary format via a ``result file`` which users can set it's
> path. Note that the frequency is not an absolute number of accesses, but a
> relative frequency among the pages of the target workloads.
>
> Users can also 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 the previously mentioned periodic access checks based
> 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. DAMON allows users to set the minimal and
> maximum number of regions for the trade-off.
>
> Except the assumption, this is almost same with the above-mentioned
> miniature-like static region based sampling. In other words, this scheme
> cannot preserve the quality of the output if the assumption is not guaranteed.
>
>
> Adaptive Regions Adjustment
> ---------------------------
>
> 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 is normally not kept and thus the 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.
>
>
> Applying Dynamic Memory Mappings
> --------------------------------
>
> Only a number of small parts in the super-huge 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 an
> user-specified time interval (``regions update interval``).
>
>
> 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.
>
>
> SeongJae Park (5):
> mm: Introduce Data Access MONitor (DAMON)
> mm/damon: Add debugfs interface
> mm/damon: Add minimal user-space tools
> Documentation/admin-guide/mm: Add a document for DAMON
> mm/damon: Add kunit tests
>
> .../admin-guide/mm/data_access_monitor.rst | 235 +++
> Documentation/admin-guide/mm/index.rst | 1 +
> mm/Kconfig | 23 +
> mm/Makefile | 1 +
> mm/damon-test.h | 571 ++++++++
> mm/damon.c | 1266 +++++++++++++++++
> tools/damon/bin2txt.py | 64 +
> tools/damon/damn | 36 +
> tools/damon/heats.py | 358 +++++
> tools/damon/nr_regions.py | 116 ++
> tools/damon/record.py | 182 +++
> tools/damon/report.py | 45 +
> tools/damon/wss.py | 121 ++
> 13 files changed, 3019 insertions(+)
> create mode 100644 Documentation/admin-guide/mm/data_access_monitor.rst
> create mode 100644 mm/damon-test.h
> create mode 100644 mm/damon.c
> create mode 100644 tools/damon/bin2txt.py
> create mode 100644 tools/damon/damn
> 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
>
> --
> 2.17.1
>

\
 
 \ /
  Last update: 2020-01-13 09:57    [W:0.089 / U:5.364 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site