From patchwork Mon Feb 10 14:48:01 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: SeongJae Park X-Patchwork-Id: 11373415 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 7B998138D for ; Mon, 10 Feb 2020 14:49:07 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id 1E2E92082F for ; Mon, 10 Feb 2020 14:49:07 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=fail reason="signature verification failed" (1024-bit key) header.d=amazon.com header.i=@amazon.com header.b="BgIkwtGd" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 1E2E92082F Authentication-Results: mail.kernel.org; dmarc=fail (p=quarantine dis=none) header.from=amazon.com Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=owner-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix) id 205FE6B0103; Mon, 10 Feb 2020 09:49:06 -0500 (EST) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id 18F116B0104; Mon, 10 Feb 2020 09:49:06 -0500 (EST) X-Original-To: int-list-linux-mm@kvack.org X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id F255A6B0105; Mon, 10 Feb 2020 09:49:05 -0500 (EST) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0046.hostedemail.com [216.40.44.46]) by kanga.kvack.org (Postfix) with ESMTP id D35E96B0103 for ; Mon, 10 Feb 2020 09:49:05 -0500 (EST) Received: from smtpin17.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay05.hostedemail.com (Postfix) with ESMTP id 783CF181AC9B6 for ; Mon, 10 Feb 2020 14:49:05 +0000 (UTC) X-FDA: 76474499850.17.lace29_150e12b69d248 X-Spam-Summary: 1,0,0,,d41d8cd98f00b204,prvs=302a421da=sjpark@amazon.com,:akpm@linux-foundation.org:sjpark@amazon.de:acme@kernel.org:alexander.shishkin@linux.intel.com:amit@kernel.org:brendan.d.gregg@gmail.com:brendanhiggins@google.com:cai@lca.pw:colin.king@canonical.com:corbet@lwn.net:dwmw@amazon.com:jolsa@redhat.com:kirill@shutemov.name:mark.rutland@arm.com:mgorman@suse.de:minchan@kernel.org:mingo@redhat.com:namhyung@kernel.org:peterz@infradead.org:rdunlap@infradead.org:rostedt@goodmis.org:sj38.park@gmail.com:vdavydov.dev@gmail.com::linux-doc@vger.kernel.org:linux-kernel@vger.kernel.org,RULES_HIT:30003:30005:30006:30012:30016:30029:30034:30041:30045:30051:30054:30055:30064:30070:30074:30075:30090:30091,0,RBL:207.171.190.10:@amazon.com:.lbl8.mailshell.net-62.18.0.100 66.10.201.10,CacheIP:none,Bayesian:0.5,0.5,0.5,Netcheck:none,DomainCache:0,MSF:not bulk,SPF:fp,MSBL:0,DNSBL:none,Custom_rules:0:2:0,LFtime:24,LUA_SUMMARY:none X-HE-Tag: lace29_150e12b69d248 X-Filterd-Recvd-Size: 27214 Received: from smtp-fw-33001.amazon.com (smtp-fw-33001.amazon.com [207.171.190.10]) by imf25.hostedemail.com (Postfix) with ESMTP for ; Mon, 10 Feb 2020 14:49:04 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=amazon.com; i=@amazon.com; q=dns/txt; s=amazon201209; t=1581346145; x=1612882145; h=from:to:cc:subject:date:message-id:mime-version: content-transfer-encoding; bh=IS0iAN8DCISLSTO+8BG2lfb5wqlX5tPHbF2p5KPBN0A=; b=BgIkwtGdPpsURQuHA0/9kfHMazanhjwLsKQgZ8qPGfkKsk99+A+u346Y z7CIiqFOjuuMMlic8hbv5POjs+dx9diMdybRjh79y7HbOcaRx22FYkg1E 5RGM/ePAV5sS2/jKvu4yCzAOv+RkrTHU7E6psfcMqFo5DaD78nzMx4ne+ 4=; IronPort-SDR: CGwbVkGzsc4LdtzDOWKoUV3/y9YR97XlrIuJXWH70aODrV0OQ7DzkyCdJG4XaTe+1gt/8eMu+L 7Jse76iWvI1Q== X-IronPort-AV: E=Sophos;i="5.70,425,1574121600"; d="scan'208";a="25461803" Received: from sea32-co-svc-lb4-vlan3.sea.corp.amazon.com (HELO email-inbound-relay-1d-9ec21598.us-east-1.amazon.com) ([10.47.23.38]) by smtp-border-fw-out-33001.sea14.amazon.com with ESMTP; 10 Feb 2020 14:48:51 +0000 Received: from EX13MTAUEA002.ant.amazon.com (iad55-ws-svc-p15-lb9-vlan3.iad.amazon.com [10.40.159.166]) by email-inbound-relay-1d-9ec21598.us-east-1.amazon.com (Postfix) with ESMTPS id F23AEA1FA2; Mon, 10 Feb 2020 14:48:42 +0000 (UTC) Received: from EX13D31EUA001.ant.amazon.com (10.43.165.15) by EX13MTAUEA002.ant.amazon.com (10.43.61.77) with Microsoft SMTP Server (TLS) id 15.0.1236.3; Mon, 10 Feb 2020 14:48:42 +0000 Received: from u886c93fd17d25d.ant.amazon.com (10.43.161.203) by EX13D31EUA001.ant.amazon.com (10.43.165.15) with Microsoft SMTP Server (TLS) id 15.0.1367.3; Mon, 10 Feb 2020 14:48:28 +0000 From: To: CC: SeongJae Park , , , , , , , , , , , , , , , , , , , , , , , , Subject: [PATCH v4 00/11] Introduce Data Access MONitor (DAMON) Date: Mon, 10 Feb 2020 15:48:01 +0100 Message-ID: <20200210144812.26845-1-sjpark@amazon.com> X-Mailer: git-send-email 2.17.1 MIME-Version: 1.0 X-Originating-IP: [10.43.161.203] X-ClientProxiedBy: EX13D35UWC004.ant.amazon.com (10.43.162.180) To EX13D31EUA001.ant.amazon.com (10.43.165.15) X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: From: SeongJae Park Introduction ============ Memory management systems can improve their performance and efficiency by utilizing finer informations about data access However, because such finer informations usually comes with higher overhead, most systems including Linux forgives the potential improvement and rely on coarse informations and/or some light-weight heuristics. The psuedo-LRU and the aggressive THP promotions are 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 solution 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. Frequently Asked Questions ========================== Q: Why DAMON is not integrated with perf? A: From the perspective of perf like profilers, DAMON can be thought of as a data source in kernel, like the tracepoints, the pressure stall information (psi), or the idle page tracking. Thus, it is easy to integrate DAMON with the profilers. 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 a debugfs interface based user space tool for DAMON. It can be used to record, visualize, and analyze data access patterns 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. Therefore, 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, its 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. 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 its core mechanism called adaptive regions adjustment. Refer to 'Appendix D' for more detail about the mechanism. We also compared the overhead of DAMON with that of a straightforward periodic access check-based monitoring. DAMON's overhead was smaller than it 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, namely 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 privileged 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/v4 The web is also available: https://github.com/sjp38/linux/releases/tag/damon/patches/v4 Patch History ============= Changes from v3 (https://lore.kernel.org/linux-mm/20200204062312.19913-1-sj38.park@gmail.com/) - Fix i386 build issue Reported-by: kbuild test robot - Increase the default size of the monitoring result buffer to 1 MiB - Fix misc bugs in debugfs interface Changes from v2 (https://lore.kernel.org/linux-mm/20200128085742.14566-1-sjpark@amazon.com/) - 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/20200120162757.32375-1-sjpark@amazon.com/) - 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/20200110131522.29964-1-sjpark@amazon.com/) - Specify an ambiguous plan of access pattern based mm optimizations - Support loadable module build - Cleanup code SeongJae Park (11): 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 kernel space API mm/damon: Add debugfs interface mm/damon: Add a tracepoint for result writing tools: Add a minimal user-space tool for DAMON 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 | 1413 +++++++++++++++++ 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, 3511 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 base-commit: d5226fa6dbae0569ee43ecfc08bdcd6770fc4755