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