linux-kernel - Re: [PATCH v5 00/14] Introduce Data Access MONitor (DAMON)

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Thu, 20 Feb 2020 09:17:10 +0100
From:   SeongJae Park <sjpark@...zon.com>
To:     SeongJae Park <sjpark@...zon.com>
CC:     <akpm@...ux-foundation.org>, SeongJae Park <sjpark@...zon.de>,
        <acme@...nel.org>, <alexander.shishkin@...ux.intel.com>,
        <amit@...nel.org>, <brendan.d.gregg@...il.com>,
        <brendanhiggins@...gle.com>, <cai@....pw>,
        <colin.king@...onical.com>, <corbet@....net>, <dwmw@...zon.com>,
        <jolsa@...hat.com>, <kirill@...temov.name>, <mark.rutland@....com>,
        <mgorman@...e.de>, <minchan@...nel.org>, <mingo@...hat.com>,
        <namhyung@...nel.org>, <peterz@...radead.org>,
        <rdunlap@...radead.org>, <rostedt@...dmis.org>, <shuah@...nel.org>,
        <sj38.park@...il.com>, <vdavydov.dev@...il.com>,
        <linux-mm@...ck.org>, <linux-doc@...r.kernel.org>,
        <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH v5 00/14] Introduce Data Access MONitor (DAMON)

On Mon, 17 Feb 2020 11:25:30 +0100 SeongJae Park <sjpark@...zon.com> wrote:

> From: SeongJae Park <sjpark@...zon.de>
> 
> Introduction
> ============
> 
> Memory management decisions can be improved if finer data access information is
> available.  However, because such finer information usually comes with higher
> overhead, most systems including Linux forgives the potential improvement and
> rely on only coarse information or some light-weight heuristics.  The
> pseudo-LRU and the aggressive THP promotions are such examples.
> 
> A number of experimental data access pattern awared memory management
> optimizations (refer to 'Appendix A' for more details) say the sacrifices are
> huge.  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 B' to see the limitations of existing memory
> monitoring mechanisms.
> 
> DAMON is a data access monitoring subsystem for the problem.  It is 1) accurate
> enough to be used for the DRAM level memory management (a straightforward
> DAMON-based optimization achieved up to 2.55x speedup), 2) light-weight enough
> to be applied online (compared to a straightforward access monitoring scheme,
> DAMON is up to 94.242.42x lighter) and 3) keeps predefined upper-bound overhead
> regardless of the size of target workloads (thus scalable).  Refer to 'Appendix
> C' if you interested in how it is possible.
> 
> DAMON has mainly designed for the kernel's memory management mechanisms.
> However, because it is implemented as a standalone kernel module and provides
> several interfaces, it can be used by a wide range of users including kernel
> space programs, user space programs, programmers, and administrators.  DAMON
> is now supporting the monitoring only, but it will also provide simple and
> convenient data access pattern awared memory managements by itself.  Refer to
> 'Appendix D' for more detailed expected usages of DAMON.

So, with this patchset, you can (1) do data access pattern based memory
management optimizations and (2) analyze your program's dynamic data access
pattern.  For the analysis, this patchset also supports visualization of the
pattern in (1) heatmap form and distribution of the (2-1) dynamic working set
size and (2-2) monitoring overhead.

To help you better understand what DAMON can give you, I made web pages showing
the visualized dynamic data access pattern of various realistic workloads,
which I picked up from PARSEC3 and SPLASH-2X bechmark suites.  Note that
another big part of DAMON's usecases, access pattern based optimization is not
demonstrated in the pages, yet.

There are pages showing the heatmap format dynamic access pattern of each
workload for heap area[1], mmap()-ed area[2], and stack[3] area.  I splitted
the entire address space to the three area because the total address space is
too huge.

You can also show how the dynamic working set size of each workload is
distributed, and how it is changing chronologically[5].

The biggest characteristic of DAMON is its promise of the upperbound of
the monitoring overhead.  To show whether DAMON keeps the promise well, I
visualized the number of monitoring operations required for each 5
milliseconds, which is configured to not exceed 1000.  You can show the
distribution of the numbers[6] and how it changes chronologically[7].

As previously mentioned, these are only a fraction of the outputs of DAMON.  I
believe DAMON can be used for more wide and creative purposes.  Nonetheless, I
hope the pages help you understand what DAMON can give you in more intuitive
fashion.

[1] https://damonitor.github.io/reports/latest/by_image/heatmap.0.png.html
[2] https://damonitor.github.io/reports/latest/by_image/heatmap.1.png.html
[3] https://damonitor.github.io/reports/latest/by_image/heatmap.2.png.html
[4] https://damonitor.github.io/reports/latest/by_image/wss_sz.png.html
[5] https://damonitor.github.io/reports/latest/by_image/wss_time.png.html
[6] https://damonitor.github.io/reports/latest/by_image/nr_regions_sz.png.html
[7] https://damonitor.github.io/reports/latest/by_image/nr_regions_time.png.html