1.. SPDX-License-Identifier: GPL-2.0 2 3====== 4Design 5====== 6 7 8Overall Architecture 9==================== 10 11DAMON subsystem is configured with three layers including 12 13- Operations Set: Implements fundamental operations for DAMON that depends on 14 the given monitoring target address-space and available set of 15 software/hardware primitives, 16- Core: Implements core logics including monitoring overhead/accurach control 17 and access-aware system operations on top of the operations set layer, and 18- Modules: Implements kernel modules for various purposes that provides 19 interfaces for the user space, on top of the core layer. 20 21 22Configurable Operations Set 23--------------------------- 24 25For data access monitoring and additional low level work, DAMON needs a set of 26implementations for specific operations that are dependent on and optimized for 27the given target address space. On the other hand, the accuracy and overhead 28tradeoff mechanism, which is the core logic of DAMON, is in the pure logic 29space. DAMON separates the two parts in different layers, namely DAMON 30Operations Set and DAMON Core Logics Layers, respectively. It further defines 31the interface between the layers to allow various operations sets to be 32configured with the core logic. 33 34Due to this design, users can extend DAMON for any address space by configuring 35the core logic to use the appropriate operations set. If any appropriate set 36is unavailable, users can implement one on their own. 37 38For example, physical memory, virtual memory, swap space, those for specific 39processes, NUMA nodes, files, and backing memory devices would be supportable. 40Also, if some architectures or devices supporting special optimized access 41check primitives, those will be easily configurable. 42 43 44Programmable Modules 45-------------------- 46 47Core layer of DAMON is implemented as a framework, and exposes its application 48programming interface to all kernel space components such as subsystems and 49modules. For common use cases of DAMON, DAMON subsystem provides kernel 50modules that built on top of the core layer using the API, which can be easily 51used by the user space end users. 52 53 54Operations Set Layer 55==================== 56 57The monitoring operations are defined in two parts: 58 591. Identification of the monitoring target address range for the address space. 602. Access check of specific address range in the target space. 61 62DAMON currently provides the implementations of the operations for the physical 63and virtual address spaces. Below two subsections describe how those work. 64 65 66VMA-based Target Address Range Construction 67------------------------------------------- 68 69This is only for the virtual address space monitoring operations 70implementation. That for the physical address space simply asks users to 71manually set the monitoring target address ranges. 72 73Only small parts in the super-huge virtual address space of the processes are 74mapped to the physical memory and accessed. Thus, tracking the unmapped 75address regions is just wasteful. However, because DAMON can deal with some 76level of noise using the adaptive regions adjustment mechanism, tracking every 77mapping is not strictly required but could even incur a high overhead in some 78cases. That said, too huge unmapped areas inside the monitoring target should 79be removed to not take the time for the adaptive mechanism. 80 81For the reason, this implementation converts the complex mappings to three 82distinct regions that cover every mapped area of the address space. The two 83gaps between the three regions are the two biggest unmapped areas in the given 84address space. The two biggest unmapped areas would be the gap between the 85heap and the uppermost mmap()-ed region, and the gap between the lowermost 86mmap()-ed region and the stack in most of the cases. Because these gaps are 87exceptionally huge in usual address spaces, excluding these will be sufficient 88to make a reasonable trade-off. Below shows this in detail:: 89 90 <heap> 91 <BIG UNMAPPED REGION 1> 92 <uppermost mmap()-ed region> 93 (small mmap()-ed regions and munmap()-ed regions) 94 <lowermost mmap()-ed region> 95 <BIG UNMAPPED REGION 2> 96 <stack> 97 98 99PTE Accessed-bit Based Access Check 100----------------------------------- 101 102Both of the implementations for physical and virtual address spaces use PTE 103Accessed-bit for basic access checks. Only one difference is the way of 104finding the relevant PTE Accessed bit(s) from the address. While the 105implementation for the virtual address walks the page table for the target task 106of the address, the implementation for the physical address walks every page 107table having a mapping to the address. In this way, the implementations find 108and clear the bit(s) for next sampling target address and checks whether the 109bit(s) set again after one sampling period. This could disturb other kernel 110subsystems using the Accessed bits, namely Idle page tracking and the reclaim 111logic. DAMON does nothing to avoid disturbing Idle page tracking, so handling 112the interference is the responsibility of sysadmins. However, it solves the 113conflict with the reclaim logic using ``PG_idle`` and ``PG_young`` page flags, 114as Idle page tracking does. 115 116 117Core Logics 118=========== 119 120 121Monitoring 122---------- 123 124Below four sections describe each of the DAMON core mechanisms and the five 125monitoring attributes, ``sampling interval``, ``aggregation interval``, 126``update interval``, ``minimum number of regions``, and ``maximum number of 127regions``. 128 129 130Access Frequency Monitoring 131~~~~~~~~~~~~~~~~~~~~~~~~~~~ 132 133The output of DAMON says what pages are how frequently accessed for a given 134duration. The resolution of the access frequency is controlled by setting 135``sampling interval`` and ``aggregation interval``. In detail, DAMON checks 136access to each page per ``sampling interval`` and aggregates the results. In 137other words, counts the number of the accesses to each page. After each 138``aggregation interval`` passes, DAMON calls callback functions that previously 139registered by users so that users can read the aggregated results and then 140clears the results. This can be described in below simple pseudo-code:: 141 142 while monitoring_on: 143 for page in monitoring_target: 144 if accessed(page): 145 nr_accesses[page] += 1 146 if time() % aggregation_interval == 0: 147 for callback in user_registered_callbacks: 148 callback(monitoring_target, nr_accesses) 149 for page in monitoring_target: 150 nr_accesses[page] = 0 151 sleep(sampling interval) 152 153The monitoring overhead of this mechanism will arbitrarily increase as the 154size of the target workload grows. 155 156 157.. _damon_design_region_based_sampling: 158 159Region Based Sampling 160~~~~~~~~~~~~~~~~~~~~~ 161 162To avoid the unbounded increase of the overhead, DAMON groups adjacent pages 163that assumed to have the same access frequencies into a region. As long as the 164assumption (pages in a region have the same access frequencies) is kept, only 165one page in the region is required to be checked. Thus, for each ``sampling 166interval``, DAMON randomly picks one page in each region, waits for one 167``sampling interval``, checks whether the page is accessed meanwhile, and 168increases the access frequency counter of the region if so. The counter is 169called ``nr_regions`` of the region. Therefore, the monitoring overhead is 170controllable by setting the number of regions. DAMON allows users to set the 171minimum and the maximum number of regions for the trade-off. 172 173This scheme, however, cannot preserve the quality of the output if the 174assumption is not guaranteed. 175 176 177Adaptive Regions Adjustment 178~~~~~~~~~~~~~~~~~~~~~~~~~~~ 179 180Even somehow the initial monitoring target regions are well constructed to 181fulfill the assumption (pages in same region have similar access frequencies), 182the data access pattern can be dynamically changed. This will result in low 183monitoring quality. To keep the assumption as much as possible, DAMON 184adaptively merges and splits each region based on their access frequency. 185 186For each ``aggregation interval``, it compares the access frequencies of 187adjacent regions and merges those if the frequency difference is small. Then, 188after it reports and clears the aggregated access frequency of each region, it 189splits each region into two or three regions if the total number of regions 190will not exceed the user-specified maximum number of regions after the split. 191 192In this way, DAMON provides its best-effort quality and minimal overhead while 193keeping the bounds users set for their trade-off. 194 195 196.. _damon_design_age_tracking: 197 198Age Tracking 199~~~~~~~~~~~~ 200 201By analyzing the monitoring results, users can also find how long the current 202access pattern of a region has maintained. That could be used for good 203understanding of the access pattern. For example, page placement algorithm 204utilizing both the frequency and the recency could be implemented using that. 205To make such access pattern maintained period analysis easier, DAMON maintains 206yet another counter called ``age`` in each region. For each ``aggregation 207interval``, DAMON checks if the region's size and access frequency 208(``nr_accesses``) has significantly changed. If so, the counter is reset to 209zero. Otherwise, the counter is increased. 210 211 212Dynamic Target Space Updates Handling 213~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 214 215The monitoring target address range could dynamically changed. For example, 216virtual memory could be dynamically mapped and unmapped. Physical memory could 217be hot-plugged. 218 219As the changes could be quite frequent in some cases, DAMON allows the 220monitoring operations to check dynamic changes including memory mapping changes 221and applies it to monitoring operations-related data structures such as the 222abstracted monitoring target memory area only for each of a user-specified time 223interval (``update interval``). 224 225 226.. _damon_design_damos: 227 228Operation Schemes 229----------------- 230 231One common purpose of data access monitoring is access-aware system efficiency 232optimizations. For example, 233 234 paging out memory regions that are not accessed for more than two minutes 235 236or 237 238 using THP for memory regions that are larger than 2 MiB and showing a high 239 access frequency for more than one minute. 240 241One straightforward approach for such schemes would be profile-guided 242optimizations. That is, getting data access monitoring results of the 243workloads or the system using DAMON, finding memory regions of special 244characteristics by profiling the monitoring results, and making system 245operation changes for the regions. The changes could be made by modifying or 246providing advice to the software (the application and/or the kernel), or 247reconfiguring the hardware. Both offline and online approaches could be 248available. 249 250Among those, providing advice to the kernel at runtime would be flexible and 251effective, and therefore widely be used. However, implementing such schemes 252could impose unnecessary redundancy and inefficiency. The profiling could be 253redundant if the type of interest is common. Exchanging the information 254including monitoring results and operation advice between kernel and user 255spaces could be inefficient. 256 257To allow users to reduce such redundancy and inefficiencies by offloading the 258works, DAMON provides a feature called Data Access Monitoring-based Operation 259Schemes (DAMOS). It lets users specify their desired schemes at a high 260level. For such specifications, DAMON starts monitoring, finds regions having 261the access pattern of interest, and applies the user-desired operation actions 262to the regions, for every user-specified time interval called 263``apply_interval``. 264 265 266.. _damon_design_damos_action: 267 268Operation Action 269~~~~~~~~~~~~~~~~ 270 271The management action that the users desire to apply to the regions of their 272interest. For example, paging out, prioritizing for next reclamation victim 273selection, advising ``khugepaged`` to collapse or split, or doing nothing but 274collecting statistics of the regions. 275 276The list of supported actions is defined in DAMOS, but the implementation of 277each action is in the DAMON operations set layer because the implementation 278normally depends on the monitoring target address space. For example, the code 279for paging specific virtual address ranges out would be different from that for 280physical address ranges. And the monitoring operations implementation sets are 281not mandated to support all actions of the list. Hence, the availability of 282specific DAMOS action depends on what operations set is selected to be used 283together. 284 285Applying an action to a region is considered as changing the region's 286characteristics. Hence, DAMOS resets the age of regions when an action is 287applied to those. 288 289 290.. _damon_design_damos_access_pattern: 291 292Target Access Pattern 293~~~~~~~~~~~~~~~~~~~~~ 294 295The access pattern of the schemes' interest. The patterns are constructed with 296the properties that DAMON's monitoring results provide, specifically the size, 297the access frequency, and the age. Users can describe their access pattern of 298interest by setting minimum and maximum values of the three properties. If a 299region's three properties are in the ranges, DAMOS classifies it as one of the 300regions that the scheme is having an interest in. 301 302 303.. _damon_design_damos_quotas: 304 305Quotas 306~~~~~~ 307 308DAMOS upper-bound overhead control feature. DAMOS could incur high overhead if 309the target access pattern is not properly tuned. For example, if a huge memory 310region having the access pattern of interest is found, applying the scheme's 311action to all pages of the huge region could consume unacceptably large system 312resources. Preventing such issues by tuning the access pattern could be 313challenging, especially if the access patterns of the workloads are highly 314dynamic. 315 316To mitigate that situation, DAMOS provides an upper-bound overhead control 317feature called quotas. It lets users specify an upper limit of time that DAMOS 318can use for applying the action, and/or a maximum bytes of memory regions that 319the action can be applied within a user-specified time duration. 320 321 322.. _damon_design_damos_quotas_prioritization: 323 324Prioritization 325^^^^^^^^^^^^^^ 326 327A mechanism for making a good decision under the quotas. When the action 328cannot be applied to all regions of interest due to the quotas, DAMOS 329prioritizes regions and applies the action to only regions having high enough 330priorities so that it will not exceed the quotas. 331 332The prioritization mechanism should be different for each action. For example, 333rarely accessed (colder) memory regions would be prioritized for page-out 334scheme action. In contrast, the colder regions would be deprioritized for huge 335page collapse scheme action. Hence, the prioritization mechanisms for each 336action are implemented in each DAMON operations set, together with the actions. 337 338Though the implementation is up to the DAMON operations set, it would be common 339to calculate the priority using the access pattern properties of the regions. 340Some users would want the mechanisms to be personalized for their specific 341case. For example, some users would want the mechanism to weigh the recency 342(``age``) more than the access frequency (``nr_accesses``). DAMOS allows users 343to specify the weight of each access pattern property and passes the 344information to the underlying mechanism. Nevertheless, how and even whether 345the weight will be respected are up to the underlying prioritization mechanism 346implementation. 347 348 349.. _damon_design_damos_watermarks: 350 351Watermarks 352~~~~~~~~~~ 353 354Conditional DAMOS (de)activation automation. Users might want DAMOS to run 355only under certain situations. For example, when a sufficient amount of free 356memory is guaranteed, running a scheme for proactive reclamation would only 357consume unnecessary system resources. To avoid such consumption, the user would 358need to manually monitor some metrics such as free memory ratio, and turn 359DAMON/DAMOS on or off. 360 361DAMOS allows users to offload such works using three watermarks. It allows the 362users to configure the metric of their interest, and three watermark values, 363namely high, middle, and low. If the value of the metric becomes above the 364high watermark or below the low watermark, the scheme is deactivated. If the 365metric becomes below the mid watermark but above the low watermark, the scheme 366is activated. If all schemes are deactivated by the watermarks, the monitoring 367is also deactivated. In this case, the DAMON worker thread only periodically 368checks the watermarks and therefore incurs nearly zero overhead. 369 370 371.. _damon_design_damos_filters: 372 373Filters 374~~~~~~~ 375 376Non-access pattern-based target memory regions filtering. If users run 377self-written programs or have good profiling tools, they could know something 378more than the kernel, such as future access patterns or some special 379requirements for specific types of memory. For example, some users may know 380only anonymous pages can impact their program's performance. They can also 381have a list of latency-critical processes. 382 383To let users optimize DAMOS schemes with such special knowledge, DAMOS provides 384a feature called DAMOS filters. The feature allows users to set an arbitrary 385number of filters for each scheme. Each filter specifies the type of target 386memory, and whether it should exclude the memory of the type (filter-out), or 387all except the memory of the type (filter-in). 388 389Currently, anonymous page, memory cgroup, address range, and DAMON monitoring 390target type filters are supported by the feature. Some filter target types 391require additional arguments. The memory cgroup filter type asks users to 392specify the file path of the memory cgroup for the filter. The address range 393type asks the start and end addresses of the range. The DAMON monitoring 394target type asks the index of the target from the context's monitoring targets 395list. Hence, users can apply specific schemes to only anonymous pages, 396non-anonymous pages, pages of specific cgroups, all pages excluding those of 397specific cgroups, pages in specific address range, pages in specific DAMON 398monitoring targets, and any combination of those. 399 400To handle filters efficiently, the address range and DAMON monitoring target 401type filters are handled by the core layer, while others are handled by 402operations set. If a memory region is filtered by a core layer-handled filter, 403it is not counted as the scheme has tried to the region. In contrast, if a 404memory regions is filtered by an operations set layer-handled filter, it is 405counted as the scheme has tried. The difference in accounting leads to changes 406in the statistics. 407 408 409Application Programming Interface 410--------------------------------- 411 412The programming interface for kernel space data access-aware applications. 413DAMON is a framework, so it does nothing by itself. Instead, it only helps 414other kernel components such as subsystems and modules building their data 415access-aware applications using DAMON's core features. For this, DAMON exposes 416its all features to other kernel components via its application programming 417interface, namely ``include/linux/damon.h``. Please refer to the API 418:doc:`document </mm/damon/api>` for details of the interface. 419 420 421Modules 422======= 423 424Because the core of DAMON is a framework for kernel components, it doesn't 425provide any direct interface for the user space. Such interfaces should be 426implemented by each DAMON API user kernel components, instead. DAMON subsystem 427itself implements such DAMON API user modules, which are supposed to be used 428for general purpose DAMON control and special purpose data access-aware system 429operations, and provides stable application binary interfaces (ABI) for the 430user space. The user space can build their efficient data access-aware 431applications using the interfaces. 432 433 434General Purpose User Interface Modules 435-------------------------------------- 436 437DAMON modules that provide user space ABIs for general purpose DAMON usage in 438runtime. 439 440DAMON user interface modules, namely 'DAMON sysfs interface' and 'DAMON debugfs 441interface' are DAMON API user kernel modules that provide ABIs to the 442user-space. Please note that DAMON debugfs interface is currently deprecated. 443 444Like many other ABIs, the modules create files on sysfs and debugfs, allow 445users to specify their requests to and get the answers from DAMON by writing to 446and reading from the files. As a response to such I/O, DAMON user interface 447modules control DAMON and retrieve the results as user requested via the DAMON 448API, and return the results to the user-space. 449 450The ABIs are designed to be used for user space applications development, 451rather than human beings' fingers. Human users are recommended to use such 452user space tools. One such Python-written user space tool is available at 453Github (https://github.com/awslabs/damo), Pypi 454(https://pypistats.org/packages/damo), and Fedora 455(https://packages.fedoraproject.org/pkgs/python-damo/damo/). 456 457Please refer to the ABI :doc:`document </admin-guide/mm/damon/usage>` for 458details of the interfaces. 459 460 461Special-Purpose Access-aware Kernel Modules 462------------------------------------------- 463 464DAMON modules that provide user space ABI for specific purpose DAMON usage. 465 466DAMON sysfs/debugfs user interfaces are for full control of all DAMON features 467in runtime. For each special-purpose system-wide data access-aware system 468operations such as proactive reclamation or LRU lists balancing, the interfaces 469could be simplified by removing unnecessary knobs for the specific purpose, and 470extended for boot-time and even compile time control. Default values of DAMON 471control parameters for the usage would also need to be optimized for the 472purpose. 473 474To support such cases, yet more DAMON API user kernel modules that provide more 475simple and optimized user space interfaces are available. Currently, two 476modules for proactive reclamation and LRU lists manipulation are provided. For 477more detail, please read the usage documents for those 478(:doc:`/admin-guide/mm/damon/reclaim` and 479:doc:`/admin-guide/mm/damon/lru_sort`). 480 481 482.. _damon_design_execution_model_and_data_structures: 483 484Execution Model and Data Structures 485=================================== 486 487The monitoring-related information including the monitoring request 488specification and DAMON-based operation schemes are stored in a data structure 489called DAMON ``context``. DAMON executes each context with a kernel thread 490called ``kdamond``. Multiple kdamonds could run in parallel, for different 491types of monitoring. 492