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