Documentation/vm/damon/design.rst

   1 .. SPDX-License-Identifier: GPL-2.0
   2
   3 ======
   4 Design
   5 ======
   6
   7 Configurable Layers
   8 ===================
   9
  10 DAMON provides data access monitoring functionality while making the accuracy
  11 and the overhead controllable.  The fundamental access monitorings require
  12 primitives that dependent on and optimized for the target address space.  On
  13 the other hand, the accuracy and overhead tradeoff mechanism, which is the core
  14 of DAMON, is in the pure logic space.  DAMON separates the two parts in
  15 different layers and defines its interface to allow various low level
  16 primitives implementations configurable with the core logic.
  17
  18 Due to this separated design and the configurable interface, users can extend
  19 DAMON for any address space by configuring the core logics with appropriate low
  20 level primitive implementations.  If appropriate one is not provided, users can
  21 implement the primitives on their own.
  22
  23 For example, physical memory, virtual memory, swap space, those for specific
  24 processes, NUMA nodes, files, and backing memory devices would be supportable.
  25 Also, if some architectures or devices support special optimized access check
  26 primitives, those will be easily configurable.
  27
  28
  29 Reference Implementations of Address Space Specific Primitives
  30 ==============================================================
  31
  32 The low level primitives for the fundamental access monitoring are defined in
  33 two parts:
  34
  35 1. Identification of the monitoring target address range for the address space.
  36 2. Access check of specific address range in the target space.
  37
  38 DAMON currently provides the implementation of the primitives for only the
  39 virtual address spaces. Below two subsections describe how it works.
  40
  41
  42 VMA-based Target Address Range Construction
  43 -------------------------------------------
  44
  45 Only small parts in the super-huge virtual address space of the processes are
  46 mapped to the physical memory and accessed.  Thus, tracking the unmapped
  47 address regions is just wasteful.  However, because DAMON can deal with some
  48 level of noise using the adaptive regions adjustment mechanism, tracking every
  49 mapping is not strictly required but could even incur a high overhead in some
  50 cases.  That said, too huge unmapped areas inside the monitoring target should
  51 be removed to not take the time for the adaptive mechanism.
  52
  53 For the reason, this implementation converts the complex mappings to three
  54 distinct regions that cover every mapped area of the address space.  The two
  55 gaps between the three regions are the two biggest unmapped areas in the given
  56 address space.  The two biggest unmapped areas would be the gap between the
  57 heap and the uppermost mmap()-ed region, and the gap between the lowermost
  58 mmap()-ed region and the stack in most of the cases.  Because these gaps are
  59 exceptionally huge in usual address spaces, excluding these will be sufficient
  60 to make a reasonable trade-off.  Below shows this in detail::
  61
  62     <heap>
  63     <BIG UNMAPPED REGION 1>
  64     <uppermost mmap()-ed region>
  65     (small mmap()-ed regions and munmap()-ed regions)
  66     <lowermost mmap()-ed region>
  67     <BIG UNMAPPED REGION 2>
  68     <stack>
  69
  70
  71 PTE Accessed-bit Based Access Check
  72 -----------------------------------
  73
  74 The implementation for the virtual address space uses PTE Accessed-bit for
  75 basic access checks.  It finds the relevant PTE Accessed bit from the address
  76 by walking the page table for the target task of the address.  In this way, the
  77 implementation finds and clears the bit for next sampling target address and
  78 checks whether the bit set again after one sampling period.  This could disturb
  79 other kernel subsystems using the Accessed bits, namely Idle page tracking and
  80 the reclaim logic.  To avoid such disturbances, DAMON makes it mutually
  81 exclusive with Idle page tracking and uses ``PG_idle`` and ``PG_young`` page
  82 flags to solve the conflict with the reclaim logic, as Idle page tracking does.
  83
  84
  85 Address Space Independent Core Mechanisms
  86 =========================================
  87
  88 Below four sections describe each of the DAMON core mechanisms and the five
  89 monitoring attributes, ``sampling interval``, ``aggregation interval``,
  90 ``regions update interval``, ``minimum number of regions``, and ``maximum
  91 number of regions``.
  92
  93
  94 Access Frequency Monitoring
  95 ---------------------------
  96
  97 The output of DAMON says what pages are how frequently accessed for a given
  98 duration.  The resolution of the access frequency is controlled by setting
  99 ``sampling interval`` and ``aggregation interval``.  In detail, DAMON checks
 100 access to each page per ``sampling interval`` and aggregates the results.  In
 101 other words, counts the number of the accesses to each page.  After each
 102 ``aggregation interval`` passes, DAMON calls callback functions that previously
 103 registered by users so that users can read the aggregated results and then
 104 clears the results.  This can be described in below simple pseudo-code::
 105
 106     while monitoring_on:
 107         for page in monitoring_target:
 108             if accessed(page):
 109                 nr_accesses[page] += 1
 110         if time() % aggregation_interval == 0:
 111             for callback in user_registered_callbacks:
 112                 callback(monitoring_target, nr_accesses)
 113             for page in monitoring_target:
 114                 nr_accesses[page] = 0
 115         sleep(sampling interval)
 116
 117 The monitoring overhead of this mechanism will arbitrarily increase as the
 118 size of the target workload grows.
 119
 120
 121 Region Based Sampling
 122 ---------------------
 123
 124 To avoid the unbounded increase of the overhead, DAMON groups adjacent pages
 125 that assumed to have the same access frequencies into a region.  As long as the
 126 assumption (pages in a region have the same access frequencies) is kept, only
 127 one page in the region is required to be checked.  Thus, for each ``sampling
 128 interval``, DAMON randomly picks one page in each region, waits for one
 129 ``sampling interval``, checks whether the page is accessed meanwhile, and
 130 increases the access frequency of the region if so.  Therefore, the monitoring
 131 overhead is controllable by setting the number of regions.  DAMON allows users
 132 to set the minimum and the maximum number of regions for the trade-off.
 133
 134 This scheme, however, cannot preserve the quality of the output if the
 135 assumption is not guaranteed.
 136
 137
 138 Adaptive Regions Adjustment
 139 ---------------------------
 140
 141 Even somehow the initial monitoring target regions are well constructed to
 142 fulfill the assumption (pages in same region have similar access frequencies),
 143 the data access pattern can be dynamically changed.  This will result in low
 144 monitoring quality.  To keep the assumption as much as possible, DAMON
 145 adaptively merges and splits each region based on their access frequency.
 146
 147 For each ``aggregation interval``, it compares the access frequencies of
 148 adjacent regions and merges those if the frequency difference is small.  Then,
 149 after it reports and clears the aggregated access frequency of each region, it
 150 splits each region into two or three regions if the total number of regions
 151 will not exceed the user-specified maximum number of regions after the split.
 152
 153 In this way, DAMON provides its best-effort quality and minimal overhead while
 154 keeping the bounds users set for their trade-off.
 155
 156
 157 Dynamic Target Space Updates Handling
 158 -------------------------------------
 159
 160 The monitoring target address range could dynamically changed.  For example,
 161 virtual memory could be dynamically mapped and unmapped.  Physical memory could
 162 be hot-plugged.
 163
 164 As the changes could be quite frequent in some cases, DAMON checks the dynamic
 165 memory mapping changes and applies it to the abstracted target area only for
 166 each of a user-specified time interval (``regions update interval``).