Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
From:   SeongJae Park <sj38.park@gmail.com>
To:     akpm@linux-foundation.org
Cc:     SeongJae Park <sjpark@amazon.de>, Jonathan.Cameron@Huawei.com,
        acme@kernel.org, alexander.shishkin@linux.intel.com,
        amit@kernel.org, benh@kernel.crashing.org,
        brendanhiggins@google.com, corbet@lwn.net, david@redhat.com,
        dwmw@amazon.com, elver@google.com, fan.du@intel.com,
        foersleo@amazon.de, greg@kroah.com, gthelen@google.com,
        guoju.fgj@alibaba-inc.com, jgowans@amazon.com, joe@perches.com,
        mgorman@suse.de, mheyne@amazon.de, minchan@kernel.org,
        mingo@redhat.com, namhyung@kernel.org, peterz@infradead.org,
        riel@surriel.com, rientjes@google.com, rostedt@goodmis.org,
        rppt@kernel.org, shakeelb@google.com, shuah@kernel.org,
        sieberf@amazon.com, sj38.park@gmail.com, snu@zelle79.org,
        vbabka@suse.cz, vdavydov.dev@gmail.com, zgf574564920@gmail.com,
        linux-damon@amazon.com, linux-mm@kvack.org,
        linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org
Subject: [RFC v3 00/15] Introduce DAMON-based Proactive Reclamation
Date:   Tue, 20 Jul 2021 13:12:54 +0000
Message-Id: <20210720131309.22073-1-sj38.park@gmail.com>
Precedence: bulk

From: SeongJae Park <sjpark@amazon.de>

NOTE: This is only an RFC for future features of DAMON patchset[1], which is
not merged in the mainline yet.  The aim of this RFC is to show how DAMON would
be evolved once it is merged in.  So, if you have some interest here, please
consider reviewing the DAMON patchset, either.

[1] https://lore.kernel.org/linux-mm/20210716081449.22187-1-sj38.park@gmail.com/

Changes from Previous Version (RFC v2)
======================================

Compared to the RFC v2
(https://lore.kernel.org/linux-mm/20210608115254.11930-1-sj38.park@gmail.com/),
this version contains below changes.

- Rebase on latest -mm tree (v5.14-rc1-mmots-2021-07-15-18-47)
- Implement a time quota (limits the time for trying reclamation of cold pages)
- Make reclamation restarts from exactly the point it stopped due to the limit

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

In short, this patchset 1) makes the engine for general data access
pattern-oriented memory management be useful for production environments, and
2) implements a static kernel module for lightweight proactive reclamation
using the engine.

Proactive Reclamation
---------------------

On general memory over-committed systems, proactively reclaiming cold pages
helps saving memory and reducing latency spikes that incurred by the direct
reclaim or the CPU consumption of kswapd, while incurring only minimal
performance degradation[2].

Particularly, a Free Pages Reporting[9] based memory over-commit virtualization
system would be one of such use cases.  In the system, the guest VMs reports
their free memory to host, and the host reallocates the reported memory to
other guests.  As a result, the system's memory can be fully utilized.
However, the guests could be not so memory-frugal, mainly because some kernel
subsystems and user-space applications are designed to use as much memory as
available.  Then, guests would report only small amount of free memory to host,
and results in poor memory utilization.  Running the proactive reclamation in
guests could help mitigating this problem.

Google has implemented the general idea and using it in their data center.
They further proposed upstreaming it in LSFMM'19, and "the general consensus
was that, while this sort of proactive reclaim would be useful for a number of
users, the cost of this particular solution was too high to consider merging it
upstream"[3].  The cost mainly comes from the coldness tracking.  Roughly
speaking, the implementation periodically scans the 'Accessed' bit of each
page.  For the reason, the overhead linearly increases as the size of the
memory and the scanning frequency grows.  As a result, Google is known to
dedicating one CPU for the work.  That's a reasonable option to someone like
Google, but it wouldn't be so to some others.

DAMON and DAMOS: An engine for data access pattern-oriented memory management
-----------------------------------------------------------------------------

DAMON[4] is a framework for general data access monitoring.  Its adaptive
monitoring overhead control feature minimizes its monitoring overhead.  It also
let the upper-bounded of the overhead be configurable by clients, regardless of
the size of the monitoring target memory.  While monitoring 70 GB memory of a
production system every 5 milliseconds, it consumes less than 1% single CPU
time.  For this, it could sacrify some of the quality of the monitoring
results.  Nevertheless, the lower-bound of the quality is configurable, and it
uses a best-effort algorithm for better quality.  Our test results[5] show the
quality is practical enough.  From the production system monitoring, we were
able to find a 4 KB region in the 70 GB memory that shows highest access
frequency.  For people having different requirements, the features can
selectively turned off, and DAMON supports the page-granularity monitoring[6],
though it makes the overhead higher and proportional to the memory size again.

We normally don't monitor the data access pattern just for fun but to improve
something like memory management.  Proactive reclamation is one such usage.
For such general cases, DAMON provides a feature called DAMon-based Operation
Schemes (DAMOS)[7].  It makes DAMON an engine for general data access pattern
oriented memory management.  Using this, clients can ask DAMON to find memory
regions of specific data access pattern and apply some memory management action
(e.g., page out, move to head of the LRU list, use huge page, ...).  We call
the request 'scheme'.

Proactive Reclamation on top of DAMON/DAMOS
-------------------------------------------

Therefore, by using DAMON for the cold pages detection, the proactive
reclamation's monitoring overhead issue could be solved.  If someone like
Google is ok to dedicate some CPUs for the monitoring and wants
page-granularity monitoring, they can configure DAMON so.

Actually, we previously implemented a version of proactive reclamation using
DAMOS and achieved noticeable improvements with our evaluation setup[5].
Nevertheless, it was only for a proof-of-concept.  It supports only virtual
address spaces of processes, and require additional tuning efforts for given
workloads and the hardware.  For the tuning, we recently introduced a simple
auto-tuning user space tool[8].  Google is also known to using a ML-based
similar approach for their fleets[2].  But, making it just works in the kernel
would be more convenient for general users.

To this end, this patchset improves DAMOS to be ready for such production
usages, and implements another version of the proactive reclamation, namely
DAMON_RECLAIM, on top of it.

DAMOS Improvements: Speed Limit, Prioritization, and Watermarks
---------------------------------------------------------------

First of all, the current version of DAMOS supports only virtual address
spaces.  This patchset makes it supports the physical address space for the
page out action.

One major problem of the current version of DAMOS is the lack of the
aggressiveness control, which can results in arbitrary overhead.  For example,
if huge memory regions having the data access pattern of interest are found,
applying the requested action to all of the regions could incur significant
overhead.  It can be controlled by modifying the target data access pattern
with manual or automated approaches[2,8].  But, some people would prefer the
kernel to just work with only intuitive tuning or default values.

For this, this patchset implements a safeguard time/size quota.  Using this,
the clients can specify up to how much time can be used for applying the
action, and/or up to how much memory regions the action can be applied within
specific time duration.  A followup question is, to which memory regions should
the action applied within the limits?  We implement a simple regions
prioritization mechanism for each action and make DAMOS to apply the action to
high priority regions first.  It also allows clients tune the prioritization
mechanism to use different weights for region's size, access frequency, and
age.  This means we could use not only LRU but also LFU or some fancy
algorithms like CAR[10] with lightweight overhead.

Though DAMON is lightweight, someone would want to remove even the overhead
when it is unnecessary.  Currently, it should manually turned on and off by
clients, but some clients would simply want to turn it on and off based on some
metrics like free memory ratio or memory fragmentation.  For such cases, this
patchset implements a watermarks-based automatic activation feature.  It allows
the clients configure the metric of their interest, and three watermarks of the
metric.  If the metric is higher than the high watermark or lower than the low
watermark, the scheme is deactivated.  If the metric is lower than the mid
watermark but higher than the low watermark, the scheme is activated.

DAMON-based Reclaim
-------------------

Using the improved DAMOS, this patchset implements a static kernel module
called 'damon_reclaim'.  It finds memory regions that didn't accessed for
specific time duration and page out.  Consuming too much CPU for the paging out
operations, or invoking it too frequently can be critical for systems
configuring its swap devices with software-defined in-memory block devices like
zram or total number of writes limited devices like SSDs, respectively.  To
avoid the problems, the time and/or size quotas can be configured.  Under the
quotas, it pages out memory regions that didn't accessed longer first.  Also,
to remove the monitoring overhead under peaceful situation, and to fall back to
the LRU-list based page granularity reclamation when it doesn't make progress,
the three watermarks based activation mechanism is used, with the free memory
ratio as the watermark metric.

For convenient configurations, it provides several module parameters.  Using
these, sysadmins can enable/disable it and tune the coldness identification
time threshold, the time/size quotas, and the three watermarks.  In detail,
sysadmins can use the kernel command line for a boot time tuning, or the sysfs
('/sys/modules/damon_reclaimparameters/') for overriding those in runtime.

Evaluation
==========

In short, DAMON_RECLAIM on v5.13 Linux kernel with ZRAM swap device and 50ms/s
time quota achieves 40.34% memory saving with only 3.38% runtime overhead.  For
this, DAMON_RECLAIM consumes only 5.16% of single CPU time.  Among the CPU
consumption, only up to about 1.448% of single CPU time is expected to be used
for the access pattern monitoring.

Setup
-----

We evaluate DAMON_RECLAIM to show how each of the DAMOS improvements make
effect.  For this, we measure entire system memory footprint and runtime of 24
realistic workloads in PARSEC3 and SPLASH-2X benchmark suites on my QEMU/KVM
based virtual machine.  The virtual machine runs on an i3.metal AWS instance
and has 130GiB memory.  It also utilizes a 4 GiB ZRAM swap device.  We do the
measurement 5 times and use averages.  We also measure the CPU consumption of
DAMON_RECLAIM.

Detailed Results
----------------

The result numbers are shown in below table.

DAMON_RECLAIM without the speed limit achieves 47.16% memory saving, but incur
5.4% runtime slowdown to the workloads on average.  For this, DAMON_RECLAIM
consumes about 11.62% single CPU time.

Applying 10ms/s, 50ms/s, and 200ms/s time quotas without the regions
prioritization reduces the slowdown to 2.51%, 4.53%, and 4.69%, respectively.
DAMON_RECLAIM's CPU utilization also similarly reduced: 1.78%, 5.7%, and 10.92%
of single CPU time.  That is, the overhead is proportional to the speed limit.
Nevertheless, it also reduces the memory saving because it becomes less
aggressive.  In detail, the three variants show 4.55%, 40.84%, and 48.42%
memory saving, respectively.

Applying the regions prioritization (page out regions that not accessed longer
first within the time quota) further reduces the performance degradation.
Runtime slowdowns has been 2.51% -> 1.84% (10ms/s), 4.53% -> 3.38% (50ms/s), and
4.69% -> 5.1% (200ms/s).  Interestingly, prioritization also reduced memory
saving a little bit.  I think that's because already paged out regions are
prioritized again.

    time quota   prioritization  memory_saving  cpu_util  slowdown
    N            N               47.16%         11.62%    5.4%
    10ms/s       N               4.55%          1.78%     2.51%
    50ms/s       N               40.84%         5.7%      4.53%
    200ms/s      N               48.42%         10.92%    4.69%
    10ms/s       Y               0.77%          1.37%     1.84%
    50ms/s       Y               40.34%         5.16%     3.38%
    200ms/s      Y               47.99%         10.41%    5.1%

Baseline and Complete Git Trees
===============================

The patches are based on the latest -mm tree (v5.14-rc1-mmots-2021-07-15-18-47)
plus DAMON patchset[1], DAMOS patchset[7], and physical address space support
patchset[6].  You can also clone the complete git tree from:

    $ git clone git://github.com/sjp38/linux -b damon_reclaim/rfc/v3

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

Development Trees
-----------------

There are a couple of trees for entire DAMON patchset series and
features for future release.

- For latest release: https://github.com/sjp38/linux/tree/damon/master
- For next release: https://github.com/sjp38/linux/tree/damon/next

Long-term Support Trees
-----------------------

For people who want to test DAMON patchset series but using only LTS kernels,
there are another couple of trees based on two latest LTS kernels respectively
and containing the 'damon/master' backports.

- For v5.4.y: https://github.com/sjp38/linux/tree/damon/for-v5.4.y
- For v5.10.y: https://github.com/sjp38/linux/tree/damon/for-v5.10.y

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

The first patch makes DAMOS to support the physical address space for the page
out action.  Following five patches (patches 2-6) implement the time/size
quotas.  Next four patches (patches 7-10) implement the memory regions
prioritization within the limit.  Then, three following patches (patches 11-13)
implement the watermarks-based schemes activation.  Finally, the last two
patches (patches 14-15) implement and document the DAMON-based reclamation on
top of the advanced DAMOS.

[1] https://lore.kernel.org/linux-mm/20210716081449.22187-1-sj38.park@gmail.com/
[2] https://research.google/pubs/pub48551/
[3] https://lwn.net/Articles/787611/
[4] https://damonitor.github.io
[5] https://damonitor.github.io/doc/html/latest/vm/damon/eval.html
[6] https://lore.kernel.org/linux-mm/20201216094221.11898-1-sjpark@amazon.com/
[7] https://lore.kernel.org/linux-mm/20201216084404.23183-1-sjpark@amazon.com/
[8] https://github.com/awslabs/damoos
[9] https://www.kernel.org/doc/html/latest/vm/free_page_reporting.html
[10] https://www.usenix.org/conference/fast-04/car-clock-adaptive-replacement

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

Changes from RFC v2
(https://lore.kernel.org/linux-mm/20210608115254.11930-1-sj38.park@gmail.com/)
- Rebase on latest -mm tree (v5.14-rc1-mmots-2021-07-15-18-47)
- Make reclamation restarts from exactly the point it stopped due to the limit
- Implement a time quota (limits the time for trying reclamation of cold pages)

[1] https://lore.kernel.org/linux-mm/20210716081449.22187-1-sj38.park@gmail.com/

Changes from RFC v1
(https://lore.kernel.org/linux-mm/20210531133816.12689-1-sj38.park@gmail.com/)
- Avoid fake I/O load reporting (James Gowans)
- Remove kernel configs for the build time enabling and the parameters setting
- Export kdamond pid via a readonly parameter file
- Elaborate coverletter, especially for evaluation and DAMON_RECLAIM interface
- Add documentation
- Rebase on -mm tree
- Cleanup code

SeongJae Park (15):
  mm/damon/paddr: Support the pageout scheme
  mm/damon/damos: Make schemes aggressiveness controllable
  damon/core/schemes: Skip already charged targets and regions
  mm/damon/schemes: Implement time quota
  mm/damon/dbgfs: Support schemes' time/IO quotas
  mm/damon/selftests: Support schemes quotas
  mm/damon/schemes: Prioritize regions within the quotas
  mm/damon/vaddr,paddr: Support pageout prioritization
  mm/damon/dbgfs: Support prioritization weights
  tools/selftests/damon: Update for regions prioritization of schemes
  mm/damon/schemes: Activate schemes based on a watermarks mechanism
  mm/damon/dbgfs: Support watermarks
  selftests/damon: Support watermarks
  mm/damon: Introduce DAMON-based reclamation
  Documentation/admin-guide/mm/damon: Add a document for DAMON_RECLAIM

 Documentation/admin-guide/mm/damon/index.rst  |   1 +
 .../admin-guide/mm/damon/reclaim.rst          | 233 ++++++++++++
 include/linux/damon.h                         | 136 ++++++-
 mm/damon/Kconfig                              |  12 +
 mm/damon/Makefile                             |   1 +
 mm/damon/core.c                               | 283 +++++++++++++-
 mm/damon/dbgfs.c                              |  47 ++-
 mm/damon/paddr.c                              |  52 ++-
 mm/damon/prmtv-common.c                       |  48 ++-
 mm/damon/prmtv-common.h                       |   5 +
 mm/damon/reclaim.c                            | 354 ++++++++++++++++++
 mm/damon/vaddr.c                              |  15 +
 .../testing/selftests/damon/debugfs_attrs.sh  |   4 +-
 13 files changed, 1163 insertions(+), 28 deletions(-)
 create mode 100644 Documentation/admin-guide/mm/damon/reclaim.rst
 create mode 100644 mm/damon/reclaim.c

-- 
2.17.1