1.. SPDX-License-Identifier: GPL-2.0 2 3====== 4Design 5====== 6 7 8.. _damon_design_execution_model_and_data_structures: 9 10Execution Model and Data Structures 11=================================== 12 13The monitoring-related information including the monitoring request 14specification and DAMON-based operation schemes are stored in a data structure 15called DAMON ``context``. DAMON executes each context with a kernel thread 16called ``kdamond``. Multiple kdamonds could run in parallel, for different 17types of monitoring. 18 19To know how user-space can do the configurations and start/stop DAMON, refer to 20:ref:`DAMON sysfs interface <sysfs_interface>` documentation. 21 22Users can also request each context execution to be paused and resumed. When 23it is paused, the kdamond does nothing other than applying online parameter 24update. 25 26To know how user-space can pause/resume each context, refer to :ref:`DAMON 27sysfs context <sysfs_context>` usage documentation. 28 29 30Overall Architecture 31==================== 32 33DAMON subsystem is configured with three layers including 34 35- :ref:`Operations Set <damon_operations_set>`: Implements fundamental 36 operations for DAMON that depends on the given monitoring target 37 address-space and available set of software/hardware primitives, 38- :ref:`Core <damon_core_logic>`: Implements core logics including monitoring 39 overhead/accuracy control and access-aware system operations on top of the 40 operations set layer, and 41- :ref:`Modules <damon_modules>`: Implements kernel modules for various 42 purposes that provides interfaces for the user space, on top of the core 43 layer. 44 45 46.. _damon_operations_set: 47 48Operations Set Layer 49==================== 50 51.. _damon_design_configurable_operations_set: 52 53For data access monitoring and additional low level work, DAMON needs a set of 54implementations for specific operations that are dependent on and optimized for 55the given target address space. For example, below two operations for access 56monitoring are address-space dependent. 57 581. Identification of the monitoring target address range for the address space. 592. Access check of specific address range in the target space. 60 61DAMON consolidates these implementations in a layer called DAMON Operations 62Set, and defines the interface between it and the upper layer. The upper layer 63is dedicated for DAMON's core logics including the mechanism for control of the 64monitoring accuracy and the overhead. 65 66Hence, DAMON can easily be extended for any address space and/or available 67hardware features by configuring the core logic to use the appropriate 68operations set. If there is no available operations set for a given purpose, a 69new operations set can be implemented following the interface between the 70layers. 71 72For example, physical memory, virtual memory, swap space, those for specific 73processes, NUMA nodes, files, and backing memory devices would be supportable. 74Also, if some architectures or devices support special optimized access check 75features, those will be easily configurable. 76 77DAMON currently provides below three operation sets. Below three subsections 78describe how those work. 79 80 - vaddr: Monitor virtual address spaces of specific processes 81 - fvaddr: Monitor fixed virtual address ranges 82 - paddr: Monitor the physical address space of the system 83 84To know how user-space can do the configuration via :ref:`DAMON sysfs interface 85<sysfs_interface>`, refer to :ref:`operations <sysfs_context>` file part of the 86documentation. 87 88 89 .. _damon_design_vaddr_target_regions_construction: 90 91VMA-based Target Address Range Construction 92------------------------------------------- 93 94A mechanism of ``vaddr`` DAMON operations set that automatically initializes 95and updates the monitoring target address regions so that entire memory 96mappings of the target processes can be covered. 97 98This mechanism is only for the ``vaddr`` operations set. In cases of 99``fvaddr`` and ``paddr`` operation sets, users are asked to manually set the 100monitoring target address ranges. 101 102Only small parts in the super-huge virtual address space of the processes are 103mapped to the physical memory and accessed. Thus, tracking the unmapped 104address regions is just wasteful. However, because DAMON can deal with some 105level of noise using the adaptive regions adjustment mechanism, tracking every 106mapping is not strictly required but could even incur a high overhead in some 107cases. That said, too huge unmapped areas inside the monitoring target should 108be removed to not take the time for the adaptive mechanism. 109 110For the reason, this implementation converts the complex mappings to three 111distinct regions that cover every mapped area of the address space. The two 112gaps between the three regions are the two biggest unmapped areas in the given 113address space. The two biggest unmapped areas would be the gap between the 114heap and the uppermost mmap()-ed region, and the gap between the lowermost 115mmap()-ed region and the stack in most of the cases. Because these gaps are 116exceptionally huge in usual address spaces, excluding these will be sufficient 117to make a reasonable trade-off. Below shows this in detail:: 118 119 <heap> 120 <BIG UNMAPPED REGION 1> 121 <uppermost mmap()-ed region> 122 (small mmap()-ed regions and munmap()-ed regions) 123 <lowermost mmap()-ed region> 124 <BIG UNMAPPED REGION 2> 125 <stack> 126 127 128PTE Accessed-bit Based Access Check 129----------------------------------- 130 131Both of the implementations for physical and virtual address spaces use PTE 132Accessed-bit for basic access checks. Only one difference is the way of 133finding the relevant PTE Accessed bit(s) from the address. While the 134implementation for the virtual address walks the page table for the target task 135of the address, the implementation for the physical address walks every page 136table having a mapping to the address. In this way, the implementations find 137and clear the bit(s) for next sampling target address and checks whether the 138bit(s) set again after one sampling period. This could disturb other kernel 139subsystems using the Accessed bits, namely Idle page tracking and the reclaim 140logic. DAMON does nothing to avoid disturbing Idle page tracking, so handling 141the interference is the responsibility of sysadmins. However, it solves the 142conflict with the reclaim logic using ``PG_idle`` and ``PG_young`` page flags, 143as Idle page tracking does. 144 145.. _damon_design_addr_unit: 146 147Address Unit 148------------ 149 150DAMON core layer uses ``unsigned long`` type for monitoring target address 151ranges. In some cases, the address space for a given operations set could be 152too large to be handled with the type. ARM (32-bit) with large physical 153address extension is an example. For such cases, a per-operations set 154parameter called ``address unit`` is provided. It represents the scale factor 155that need to be multiplied to the core layer's address for calculating real 156address on the given address space. Support of ``address unit`` parameter is 157up to each operations set implementation. ``paddr`` is the only operations set 158implementation that supports the parameter. 159 160If the value is smaller than ``PAGE_SIZE``, only a power of two should be used. 161 162.. _damon_core_logic: 163 164Core Logics 165=========== 166 167.. _damon_design_monitoring: 168 169Monitoring 170---------- 171 172Below four sections describe each of the DAMON core mechanisms and the five 173monitoring attributes, ``sampling interval``, ``aggregation interval``, 174``update interval``, ``minimum number of regions``, and ``maximum number of 175regions``. 176 177Note that ``minimum number of regions`` must be 3 or higher. This is because the 178virtual address space monitoring is designed to handle at least three regions to 179accommodate two large unmapped areas commonly found in normal virtual address 180spaces. While this restriction might not be strictly necessary for other 181operation sets like ``paddr``, it is currently enforced across all DAMON 182operations for consistency. 183 184To know how user-space can set the attributes via :ref:`DAMON sysfs interface 185<sysfs_interface>`, refer to :ref:`monitoring_attrs <sysfs_monitoring_attrs>` 186part of the documentation. 187 188 189Access Frequency Monitoring 190~~~~~~~~~~~~~~~~~~~~~~~~~~~ 191 192The output of DAMON says what pages are how frequently accessed for a given 193duration. The resolution of the access frequency is controlled by setting 194``sampling interval`` and ``aggregation interval``. In detail, DAMON checks 195access to each page per ``sampling interval`` and aggregates the results. In 196other words, counts the number of the accesses to each page. After each 197``aggregation interval`` passes, DAMON calls callback functions that previously 198registered by users so that users can read the aggregated results and then 199clears the results. This can be described in below simple pseudo-code:: 200 201 while monitoring_on: 202 for page in monitoring_target: 203 if accessed(page): 204 nr_accesses[page] += 1 205 if time() % aggregation_interval == 0: 206 for callback in user_registered_callbacks: 207 callback(monitoring_target, nr_accesses) 208 for page in monitoring_target: 209 nr_accesses[page] = 0 210 sleep(sampling interval) 211 212The monitoring overhead of this mechanism will arbitrarily increase as the 213size of the target workload grows. 214 215 216.. _damon_design_region_based_sampling: 217 218Region Based Sampling 219~~~~~~~~~~~~~~~~~~~~~ 220 221To avoid the unbounded increase of the overhead, DAMON groups adjacent pages 222that assumed to have the same access frequencies into a region. As long as the 223assumption (pages in a region have the same access frequencies) is kept, only 224one page in the region is required to be checked. Thus, for each ``sampling 225interval``, DAMON randomly picks one page in each region, waits for one 226``sampling interval``, checks whether the page is accessed meanwhile, and 227increases the access frequency counter of the region if so. The counter is 228called ``nr_accesses`` of the region. Therefore, the monitoring overhead is 229controllable by setting the number of regions. DAMON allows users to set the 230minimum and the maximum number of regions for the trade-off. 231 232This scheme, however, cannot preserve the quality of the output if the 233assumption is not guaranteed. 234 235 236.. _damon_design_adaptive_regions_adjustment: 237 238Adaptive Regions Adjustment 239~~~~~~~~~~~~~~~~~~~~~~~~~~~ 240 241Even somehow the initial monitoring target regions are well constructed to 242fulfill the assumption (pages in same region have similar access frequencies), 243the data access pattern can be dynamically changed. This will result in low 244monitoring quality. To keep the assumption as much as possible, DAMON 245adaptively merges and splits each region based on their access frequency. 246 247For each ``aggregation interval``, it compares the access frequencies 248(``nr_accesses``) of adjacent regions. If the difference is small, and if the 249sum of the two regions' sizes is smaller than the size of total regions divided 250by the ``minimum number of regions``, DAMON merges the two regions. If the 251resulting number of total regions is still higher than ``maximum number of 252regions``, it repeats the merging with increasing access frequenceis difference 253threshold until the upper-limit of the number of regions is met, or the 254threshold becomes higher than possible maximum value (``aggregation interval`` 255divided by ``sampling interval``). Then, after it reports and clears the 256aggregated access frequency of each region, it splits each region into two or 257three regions if the total number of regions will not exceed the user-specified 258maximum number of regions after the split. 259 260In this way, DAMON provides its best-effort quality and minimal overhead while 261keeping the bounds users set for their trade-off. 262 263 264.. _damon_design_age_tracking: 265 266Age Tracking 267~~~~~~~~~~~~ 268 269By analyzing the monitoring results, users can also find how long the current 270access pattern of a region has maintained. That could be used for good 271understanding of the access pattern. For example, page placement algorithm 272utilizing both the frequency and the recency could be implemented using that. 273To make such access pattern maintained period analysis easier, DAMON maintains 274yet another counter called ``age`` in each region. For each ``aggregation 275interval``, DAMON checks if the region's size and access frequency 276(``nr_accesses``) has significantly changed. If so, the counter is reset to 277zero. Otherwise, the counter is increased. 278 279.. _damon_design_data_attrs_monitoring: 280 281Data Attributes Monitoring 282~~~~~~~~~~~~~~~~~~~~~~~~~~ 283 284Data access pattern is only one type of data attributes. In some use cases, 285users need to know more data attributes information. For example, users may 286need to know how much of a given hot or cold memory region is backed by 287anonymous pages, or belong to a specific cgroup. For such use case, data 288attributes monitoring feature is provided. 289 290Using the feature, users can register data attributes of their interest to the 291DAMON :ref:`context <damon_design_execution_model_and_data_structures>`. The 292registration is made by specifying a probe per attribute. Each of the probe 293specifies a rule to determine if a given memory region has the related 294attribute. The rule is constructed with multiple filters. The filters work 295same to :ref:`DAMOS filters <damon_design_damos_filters>` except the supported 296filter types. Currently only ``anon`` and ``memcg`` filter types are supported 297for data attributes monitoring. 298 299If such probes are registered, DAMON executes the probes for each region's 300sampling memory when it does the access :ref:`sampling 301<damon_design_region_based_sampling>`. The number of samples that identified 302as having the data attribute (hitting the probe) per :ref:`aggregation interval 303<damon_design_monitoring>` is accounted in a per-region per-probe counter. 304Users can therefore know how much of a given DAMON region has a specific data 305attribute by reading the per-region per-probe probe hits counter after each 306aggregation interval. 307 308This is a sampling based mechanism. Hence, it is lightweight but the output 309may include some measurement errors. The output should be used with good 310understanding of statistics. 311 312Another way to do this for higher accuracy is using :ref:`DAMOS filter 313<damon_design_damos_filters>` with ``stat`` :ref:`action 314<damon_design_damos_action>` and ``sz_ops_filter_passed`` :ref:`stat 315<damon_design_damos_stat>`. This approach provides the data attributes 316information in page level. But, because it is operated in page level, the 317overhead is proportional to the size of the memory. 318 319Dynamic Target Space Updates Handling 320~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 321 322The monitoring target address range could dynamically changed. For example, 323virtual memory could be dynamically mapped and unmapped. Physical memory could 324be hot-plugged. 325 326As the changes could be quite frequent in some cases, DAMON allows the 327monitoring operations to check dynamic changes including memory mapping changes 328and applies it to monitoring operations-related data structures such as the 329abstracted monitoring target memory area only for each of a user-specified time 330interval (``update interval``). 331 332User-space can get the monitoring results via DAMON sysfs interface and/or 333tracepoints. For more details, please refer to the documentations for 334:ref:`DAMOS tried regions <sysfs_schemes_tried_regions>` and :ref:`tracepoint`, 335respectively. 336 337 338.. _damon_design_monitoring_params_tuning_guide: 339 340Monitoring Parameters Tuning Guide 341~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 342 343In short, set ``aggregation interval`` to capture meaningful amount of accesses 344for the purpose. The amount of accesses can be measured using ``nr_accesses`` 345and ``age`` of regions in the aggregated monitoring results snapshot. The 346default value of the interval, ``100ms``, turns out to be too short in many 347cases. Set ``sampling interval`` proportional to ``aggregation interval``. By 348default, ``1/20`` is recommended as the ratio. 349 350``Aggregation interval`` should be set as the time interval that the workload 351can make an amount of accesses for the monitoring purpose, within the interval. 352If the interval is too short, only small number of accesses are captured. As a 353result, the monitoring results look everything is samely accessed only rarely. 354For many purposes, that would be useless. If it is too long, however, the time 355to converge regions with the :ref:`regions adjustment mechanism 356<damon_design_adaptive_regions_adjustment>` can be too long, depending on the 357time scale of the given purpose. This could happen if the workload is actually 358making only rare accesses but the user thinks the amount of accesses for the 359monitoring purpose too high. For such cases, the target amount of access to 360capture per ``aggregation interval`` should carefully reconsidered. Also, note 361that the captured amount of accesses is represented with not only 362``nr_accesses``, but also ``age``. For example, even if every region on the 363monitoring results show zero ``nr_accesses``, regions could still be 364distinguished using ``age`` values as the recency information. 365 366Hence the optimum value of ``aggregation interval`` depends on the access 367intensiveness of the workload. The user should tune the interval based on the 368amount of access that captured on each aggregated snapshot of the monitoring 369results. 370 371Note that the default value of the interval is 100 milliseconds, which is too 372short in many cases, especially on large systems. 373 374``Sampling interval`` defines the resolution of each aggregation. If it is set 375too large, monitoring results will look like every region was samely rarely 376accessed, or samely frequently accessed. That is, regions become 377undistinguishable based on access pattern, and therefore the results will be 378useless in many use cases. If ``sampling interval`` is too small, it will not 379degrade the resolution, but will increase the monitoring overhead. If it is 380appropriate enough to provide a resolution of the monitoring results that 381sufficient for the given purpose, it shouldn't be unnecessarily further 382lowered. It is recommended to be set proportional to ``aggregation interval``. 383By default, the ratio is set as ``1/20``, and it is still recommended. 384 385Based on the manual tuning guide, DAMON provides more intuitive knob-based 386intervals auto tuning mechanism. Please refer to :ref:`the design document of 387the feature <damon_design_monitoring_intervals_autotuning>` for detail. 388 389Refer to below documents for an example tuning based on the above guide. 390 391.. toctree:: 392 :maxdepth: 1 393 394 monitoring_intervals_tuning_example 395 396 397.. _damon_design_monitoring_intervals_autotuning: 398 399Monitoring Intervals Auto-tuning 400~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 401 402DAMON provides automatic tuning of the ``sampling interval`` and ``aggregation 403interval`` based on the :ref:`the tuning guide idea 404<damon_design_monitoring_params_tuning_guide>`. The tuning mechanism allows 405users to set the aimed amount of access events to observe via DAMON within 406given time interval. The target can be specified by the user as a ratio of 407DAMON-observed access events to the theoretical maximum amount of the events 408(``access_bp``) that measured within a given number of aggregations 409(``aggrs``). 410 411The DAMON-observed access events are calculated in byte granularity based on 412DAMON :ref:`region assumption <damon_design_region_based_sampling>`. For 413example, if a region of size ``X`` bytes of ``Y`` ``nr_accesses`` is found, it 414means ``X * Y`` access events are observed by DAMON. Theoretical maximum 415access events for the region is calculated in same way, but replacing ``Y`` 416with theoretical maximum ``nr_accesses``, which can be calculated as 417``aggregation interval / sampling interval``. 418 419The mechanism calculates the ratio of access events for ``aggrs`` aggregations, 420and increases or decrease the ``sampling interval`` and ``aggregation 421interval`` in same ratio, if the observed access ratio is lower or higher than 422the target, respectively. The ratio of the intervals change is decided in 423proportion to the distance between current samples ratio and the target ratio. 424 425The user can further set the minimum and maximum ``sampling interval`` that can 426be set by the tuning mechanism using two parameters (``min_sample_us`` and 427``max_sample_us``). Because the tuning mechanism changes ``sampling interval`` 428and ``aggregation interval`` in same ratio always, the minimum and maximum 429``aggregation interval`` after each of the tuning changes can automatically set 430together. 431 432The tuning is turned off by default, and need to be set explicitly by the user. 433As a rule of thumbs and the Parreto principle, 4% access samples ratio target 434is recommended. Note that Parreto principle (80/20 rule) has applied twice. 435That is, assumes 4% (20% of 20%) DAMON-observed access events ratio (source) 436to capture 64% (80% multiplied by 80%) real access events (outcomes). 437 438To know how user-space can use this feature via :ref:`DAMON sysfs interface 439<sysfs_interface>`, refer to :ref:`intervals_goal 440<damon_usage_sysfs_monitoring_intervals_goal>` part of the documentation. 441 442 443.. _damon_design_damos: 444 445Operation Schemes 446----------------- 447 448One common purpose of data access monitoring is access-aware system efficiency 449optimizations. For example, 450 451 paging out memory regions that are not accessed for more than two minutes 452 453or 454 455 using THP for memory regions that are larger than 2 MiB and showing a high 456 access frequency for more than one minute. 457 458One straightforward approach for such schemes would be profile-guided 459optimizations. That is, getting data access monitoring results of the 460workloads or the system using DAMON, finding memory regions of special 461characteristics by profiling the monitoring results, and making system 462operation changes for the regions. The changes could be made by modifying or 463providing advice to the software (the application and/or the kernel), or 464reconfiguring the hardware. Both offline and online approaches could be 465available. 466 467Among those, providing advice to the kernel at runtime would be flexible and 468effective, and therefore widely be used. However, implementing such schemes 469could impose unnecessary redundancy and inefficiency. The profiling could be 470redundant if the type of interest is common. Exchanging the information 471including monitoring results and operation advice between kernel and user 472spaces could be inefficient. 473 474To allow users to reduce such redundancy and inefficiencies by offloading the 475works, DAMON provides a feature called Data Access Monitoring-based Operation 476Schemes (DAMOS). It lets users specify their desired schemes at a high 477level. For such specifications, DAMON starts monitoring, finds regions having 478the access pattern of interest, and applies the user-desired operation actions 479to the regions, for every user-specified time interval called 480``apply_interval``. 481 482To know how user-space can set ``apply_interval`` via :ref:`DAMON sysfs 483interface <sysfs_interface>`, refer to :ref:`apply_interval_us <sysfs_scheme>` 484part of the documentation. 485 486 487.. _damon_design_damos_action: 488 489Operation Action 490~~~~~~~~~~~~~~~~ 491 492The management action that the users desire to apply to the regions of their 493interest. For example, paging out, prioritizing for next reclamation victim 494selection, advising ``khugepaged`` to collapse or split, or doing nothing but 495collecting statistics of the regions. 496 497The list of supported actions is defined in DAMOS, but the implementation of 498each action is in the DAMON operations set layer because the implementation 499normally depends on the monitoring target address space. For example, the code 500for paging specific virtual address ranges out would be different from that for 501physical address ranges. And the monitoring operations implementation sets are 502not mandated to support all actions of the list. Hence, the availability of 503specific DAMOS action depends on what operations set is selected to be used 504together. 505 506The list of the supported actions, their meaning, and DAMON operations sets 507that supports each action are as below. 508 509 - ``willneed``: Call ``madvise()`` for the region with ``MADV_WILLNEED``. 510 Supported by ``vaddr`` and ``fvaddr`` operations set. 511 - ``cold``: Call ``madvise()`` for the region with ``MADV_COLD``. 512 Supported by ``vaddr`` and ``fvaddr`` operations set. 513 - ``pageout``: Reclaim the region. 514 Supported by ``vaddr``, ``fvaddr`` and ``paddr`` operations set. 515 - ``hugepage``: Call ``madvise()`` for the region with ``MADV_HUGEPAGE``. 516 Supported by ``vaddr`` and ``fvaddr`` operations set. When 517 TRANSPARENT_HUGEPAGE is disabled, the application of the action will just 518 fail. 519 - ``nohugepage``: Call ``madvise()`` for the region with ``MADV_NOHUGEPAGE``. 520 Supported by ``vaddr`` and ``fvaddr`` operations set. When 521 TRANSPARENT_HUGEPAGE is disabled, the application of the action will just 522 fail. 523 - ``collapse``: Call ``madvise()`` for the region with ``MADV_COLLAPSE``. 524 Supported by ``vaddr`` and ``fvaddr`` operations set. When 525 TRANSPARENT_HUGEPAGE is disabled, the application of the action will just 526 fail. 527 - ``lru_prio``: Prioritize the region on its LRU lists. 528 Supported by ``paddr`` operations set. 529 - ``lru_deprio``: Deprioritize the region on its LRU lists. 530 Supported by ``paddr`` operations set. 531 - ``migrate_hot``: Migrate the regions prioritizing warmer regions. 532 Supported by ``vaddr``, ``fvaddr`` and ``paddr`` operations set. 533 - ``migrate_cold``: Migrate the regions prioritizing colder regions. 534 Supported by ``vaddr``, ``fvaddr`` and ``paddr`` operations set. 535 - ``stat``: Do nothing but count the statistics. 536 Supported by all operations sets. 537 538Applying the actions except ``stat`` to a region is considered as changing the 539region's characteristics. Hence, DAMOS resets the age of regions when any such 540actions are applied to those. 541 542To know how user-space can set the action via :ref:`DAMON sysfs interface 543<sysfs_interface>`, refer to :ref:`action <sysfs_scheme>` part of the 544documentation. 545 546 547.. _damon_design_damos_access_pattern: 548 549Target Access Pattern 550~~~~~~~~~~~~~~~~~~~~~ 551 552The access pattern of the schemes' interest. The patterns are constructed with 553the properties that DAMON's monitoring results provide, specifically the size, 554the access frequency, and the age. Users can describe their access pattern of 555interest by setting minimum and maximum values of the three properties. If a 556region's three properties are in the ranges, DAMOS classifies it as one of the 557regions that the scheme is having an interest in. 558 559To know how user-space can set the access pattern via :ref:`DAMON sysfs 560interface <sysfs_interface>`, refer to :ref:`access_pattern 561<sysfs_access_pattern>` part of the documentation. 562 563 564.. _damon_design_damos_quotas: 565 566Quotas 567~~~~~~ 568 569DAMOS upper-bound overhead control feature. DAMOS could incur high overhead if 570the target access pattern is not properly tuned. For example, if a huge memory 571region having the access pattern of interest is found, applying the scheme's 572action to all pages of the huge region could consume unacceptably large system 573resources. Preventing such issues by tuning the access pattern could be 574challenging, especially if the access patterns of the workloads are highly 575dynamic. 576 577To mitigate that situation, DAMOS provides an upper-bound overhead control 578feature called quotas. It lets users specify an upper limit of time that DAMOS 579can use for applying the action, and/or a maximum bytes of memory regions that 580the action can be applied within a user-specified time duration. 581 582To know how user-space can set the basic quotas via :ref:`DAMON sysfs interface 583<sysfs_interface>`, refer to :ref:`quotas <sysfs_quotas>` part of the 584documentation. 585 586 587.. _damon_design_damos_quotas_prioritization: 588 589Prioritization 590^^^^^^^^^^^^^^ 591 592A mechanism for making a good decision under the quotas. When the action 593cannot be applied to all regions of interest due to the quotas, DAMOS 594prioritizes regions and applies the action to only regions having high enough 595priorities so that it will not exceed the quotas. 596 597The prioritization mechanism should be different for each action. For example, 598rarely accessed (colder) memory regions would be prioritized for page-out 599scheme action. In contrast, the colder regions would be deprioritized for huge 600page collapse scheme action. Hence, the prioritization mechanisms for each 601action are implemented in each DAMON operations set, together with the actions. 602 603Though the implementation is up to the DAMON operations set, it would be common 604to calculate the priority using the access pattern properties of the regions. 605Some users would want the mechanisms to be personalized for their specific 606case. For example, some users would want the mechanism to weigh the recency 607(``age``) more than the access frequency (``nr_accesses``). DAMOS allows users 608to specify the weight of each access pattern property and passes the 609information to the underlying mechanism. Nevertheless, how and even whether 610the weight will be respected are up to the underlying prioritization mechanism 611implementation. 612 613To know how user-space can set the prioritization weights via :ref:`DAMON sysfs 614interface <sysfs_interface>`, refer to :ref:`weights <sysfs_quotas>` part of 615the documentation. 616 617 618.. _damon_design_damos_quotas_failed_memory_charging_ratio: 619 620Action-failed Memory Charging Ratio 621^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 622 623DAMOS action to a given region can fail for some subsets of the memory of the 624region. For example, if the action is ``pageout`` and the region has some 625unreclaimable pages, applying the action to the pages will fail. The amount of 626system resource that is taken for such failed action applications is usually 627different from that for successful action applications. For such cases, users 628can set different charging ratio for such failed memory. The ratio can be 629specified using ``fail_charge_num`` and ``fail_charge_denom`` parameters. The 630two parameters represent the numerator and denominator of the ratio. The 631feature is enabled only if ``fail_charge_denom`` is not zero. 632 633For example, let's suppose a DAMOS action is applied to a region of 1,000 MiB 634size. The action is successfully applied to only 700 MiB of the region. 635``fail_charge_num`` and ``fail_charge_denom`` are set to ``1`` and ``1024``, 636respectively. Then only 700 MiB and 300 KiB of size (``700 MiB + 300 MiB * 1 / 6371024``) will be charged. 638 639 640.. _damon_design_damos_quotas_auto_tuning: 641 642Aim-oriented Feedback-driven Auto-tuning 643^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 644 645Automatic feedback-driven quota tuning. Instead of setting the absolute quota 646value, users can specify the metric of their interest, and what target value 647they want the metric value to be. DAMOS then automatically tunes the 648aggressiveness (the quota) of the corresponding scheme. For example, if DAMOS 649is under achieving the goal, DAMOS automatically increases the quota. If DAMOS 650is over achieving the goal, it decreases the quota. 651 652There are two such tuning algorithms that users can select as they need. 653 654- ``consist``: A proportional feedback loop based algorithm. Tries to find an 655 optimum quota that should be consistently kept, to keep achieving the goal. 656 Useful for kernel-only operation on dynamic and long-running environments. 657 This is the default selection. If unsure, use this. 658- ``temporal``: More straightforward algorithm. Tries to achieve the goal as 659 fast as possible, using maximum allowed quota, but only for a temporal short 660 time. When the quota is under-achieved, this algorithm keeps tuning quota to 661 a maximum allowed one. Once the quota is [over]-achieved, this sets the 662 quota zero. Useful for deterministic control required environments. 663 664The goal can be specified with five parameters, namely ``target_metric``, 665``target_value``, ``current_value``, ``nid`` and ``path``. The auto-tuning 666mechanism tries to make ``current_value`` of ``target_metric`` be same to 667``target_value``. 668 669- ``user_input``: User-provided value. Users could use any metric that they 670 has interest in for the value. Use space main workload's latency or 671 throughput, system metrics like free memory ratio or memory pressure stall 672 time (PSI) could be examples. Note that users should explicitly set 673 ``current_value`` on their own in this case. In other words, users should 674 repeatedly provide the feedback. 675- ``some_mem_psi_us``: System-wide ``some`` memory pressure stall information 676 in microseconds that measured from last quota reset to next quota reset. 677 DAMOS does the measurement on its own, so only ``target_value`` need to be 678 set by users at the initial time. In other words, DAMOS does self-feedback. 679- ``node_mem_used_bp``: Specific NUMA node's used memory ratio in bp (1/10,000). 680- ``node_mem_free_bp``: Specific NUMA node's free memory ratio in bp (1/10,000). 681- ``node_memcg_used_bp``: Specific cgroup's node used memory ratio for a 682 specific NUMA node, in bp (1/10,000). 683- ``node_memcg_free_bp``: Specific cgroup's node unused memory ratio for a 684 specific NUMA node, in bp (1/10,000). 685- ``active_mem_bp``: Active to active + inactive (LRU) memory size ratio in bp 686 (1/10,000). 687- ``inactive_mem_bp``: Inactive to active + inactive (LRU) memory size ratio in 688 bp (1/10,000). 689 690``nid`` is optionally required for only ``node_mem_used_bp``, 691``node_mem_free_bp``, ``node_memcg_used_bp`` and ``node_memcg_free_bp`` to 692point the specific NUMA node. 693 694``path`` is optionally required for only ``node_memcg_used_bp`` and 695``node_memcg_free_bp`` to point the path to the cgroup. The value should be 696the path of the memory cgroup from the cgroups mount point. 697 698To know how user-space can set the tuning goal metric, the target value, and/or 699the current value via :ref:`DAMON sysfs interface <sysfs_interface>`, refer to 700:ref:`quota goals <sysfs_schemes_quota_goals>` part of the documentation. 701 702 703.. _damon_design_damos_watermarks: 704 705Watermarks 706~~~~~~~~~~ 707 708Conditional DAMOS (de)activation automation. Users might want DAMOS to run 709only under certain situations. For example, when a sufficient amount of free 710memory is guaranteed, running a scheme for proactive reclamation would only 711consume unnecessary system resources. To avoid such consumption, the user would 712need to manually monitor some metrics such as free memory ratio, and turn 713DAMON/DAMOS on or off. 714 715DAMOS allows users to offload such works using three watermarks. It allows the 716users to configure the metric of their interest, and three watermark values, 717namely high, middle, and low. If the value of the metric becomes above the 718high watermark or below the low watermark, the scheme is deactivated. If the 719metric becomes below the mid watermark but above the low watermark, the scheme 720is activated. If all schemes are deactivated by the watermarks, the monitoring 721is also deactivated. In this case, the DAMON worker thread only periodically 722checks the watermarks and therefore incurs nearly zero overhead. 723 724To know how user-space can set the watermarks via :ref:`DAMON sysfs interface 725<sysfs_interface>`, refer to :ref:`watermarks <sysfs_watermarks>` part of the 726documentation. 727 728 729.. _damon_design_damos_filters: 730 731Filters 732~~~~~~~ 733 734Non-access pattern-based target memory regions filtering. If users run 735self-written programs or have good profiling tools, they could know something 736more than the kernel, such as future access patterns or some special 737requirements for specific types of memory. For example, some users may know 738only anonymous pages can impact their program's performance. They can also 739have a list of latency-critical processes. 740 741To let users optimize DAMOS schemes with such special knowledge, DAMOS provides 742a feature called DAMOS filters. The feature allows users to set an arbitrary 743number of filters for each scheme. Each filter specifies 744 745- a type of memory (``type``), 746- whether it is for the memory of the type or all except the type 747 (``matching``), and 748- whether it is to allow (include) or reject (exclude) applying 749 the scheme's action to the memory (``allow``). 750 751For efficient handling of filters, some types of filters are handled by the 752core layer, while others are handled by operations set. In the latter case, 753hence, support of the filter types depends on the DAMON operations set. In 754case of the core layer-handled filters, the memory regions that excluded by the 755filter are not counted as the scheme has tried to the region. In contrast, if 756a memory regions is filtered by an operations set layer-handled filter, it is 757counted as the scheme has tried. This difference affects the statistics. 758 759When multiple filters are installed, the group of filters that handled by the 760core layer are evaluated first. After that, the group of filters that handled 761by the operations layer are evaluated. Filters in each of the groups are 762evaluated in the installed order. If a part of memory is matched to one of the 763filter, next filters are ignored. If the part passes through the filters 764evaluation stage because it is not matched to any of the filters, applying the 765scheme's action to it depends on the last filter's allowance type. If the last 766filter was for allowing, the part of memory will be rejected, and vice versa. 767 768For example, let's assume 1) a filter for allowing anonymous pages and 2) 769another filter for rejecting young pages are installed in the order. If a page 770of a region that eligible to apply the scheme's action is an anonymous page, 771the scheme's action will be applied to the page regardless of whether it is 772young or not, since it matches with the first allow-filter. If the page is 773not anonymous but young, the scheme's action will not be applied, since the 774second reject-filter blocks it. If the page is neither anonymous nor young, 775the page will pass through the filters evaluation stage since there is no 776matching filter, and the action will be applied to the page. 777 778Below ``type`` of filters are currently supported. 779 780- Core layer handled 781 - addr 782 - Applied to pages that belonging to a given address range. 783 - target 784 - Applied to pages that belonging to a given DAMON monitoring target. 785- Operations layer handled, supported by only ``paddr`` operations set. 786 - anon 787 - Applied to pages that containing data that not stored in files. 788 - active 789 - Applied to active pages. 790 - memcg 791 - Applied to pages that belonging to a given cgroup. 792 - young 793 - Applied to pages that are accessed after the last access check from the 794 scheme. 795 - hugepage_size 796 - Applied to pages that managed in a given size range. 797 - unmapped 798 - Applied to pages that unmapped. 799 800To know how user-space can set the filters via :ref:`DAMON sysfs interface 801<sysfs_interface>`, refer to :ref:`filters <sysfs_filters>` part of the 802documentation. 803 804.. _damon_design_damos_stat: 805 806Statistics 807~~~~~~~~~~ 808 809The statistics of DAMOS behaviors that designed to help monitoring, tuning and 810debugging of DAMOS. 811 812DAMOS accounts below statistics for each scheme, from the beginning of the 813scheme's execution. 814 815- ``nr_tried``: Total number of regions that the scheme is tried to be applied. 816- ``sz_tried``: Total size of regions that the scheme is tried to be applied. 817- ``sz_ops_filter_passed``: Total bytes that passed operations set 818 layer-handled DAMOS filters. 819- ``nr_applied``: Total number of regions that the scheme is applied. 820- ``sz_applied``: Total size of regions that the scheme is applied. 821- ``qt_exceeds``: Total number of times the quota of the scheme has exceeded. 822- ``nr_snapshots``: Total number of DAMON snapshots that the scheme is tried to 823 be applied. 824- ``max_nr_snapshots``: Upper limit of ``nr_snapshots``. 825 826"A scheme is tried to be applied to a region" means DAMOS core logic determined 827the region is eligible to apply the scheme's :ref:`action 828<damon_design_damos_action>`. The :ref:`access pattern 829<damon_design_damos_access_pattern>`, :ref:`quotas 830<damon_design_damos_quotas>`, :ref:`watermarks 831<damon_design_damos_watermarks>`, and :ref:`filters 832<damon_design_damos_filters>` that handled on core logic could affect this. 833The core logic will only ask the underlying :ref:`operation set 834<damon_operations_set>` to do apply the action to the region, so whether the 835action is really applied or not is unclear. That's why it is called "tried". 836 837"A scheme is applied to a region" means the :ref:`operation set 838<damon_operations_set>` has applied the action to at least a part of the 839region. The :ref:`filters <damon_design_damos_filters>` that handled by the 840operation set, and the types of the :ref:`action <damon_design_damos_action>` 841and the pages of the region can affect this. For example, if a filter is set 842to exclude anonymous pages and the region has only anonymous pages, or if the 843action is ``pageout`` while all pages of the region are unreclaimable, applying 844the action to the region will fail. 845 846Unlike normal stats, ``max_nr_snapshots`` is set by users. If it is set as 847non-zero and ``nr_snapshots`` be same to or greater than ``nr_snapshots``, the 848scheme is deactivated. 849 850To know how user-space can read the stats via :ref:`DAMON sysfs interface 851<sysfs_interface>`, refer to :ref:s`stats <sysfs_stats>` part of the 852documentation. 853 854Regions Walking 855~~~~~~~~~~~~~~~ 856 857DAMOS feature allowing users access each region that a DAMOS action has just 858applied. Using this feature, DAMON :ref:`API <damon_design_api>` allows users 859access full properties of the regions including the access monitoring results 860and amount of the region's internal memory that passed the DAMOS filters. 861:ref:`DAMON sysfs interface <sysfs_interface>` also allows users read the data 862via special :ref:`files <sysfs_schemes_tried_regions>`. 863 864.. _damon_design_api: 865 866Application Programming Interface 867--------------------------------- 868 869The programming interface for kernel space data access-aware applications. 870DAMON is a framework, so it does nothing by itself. Instead, it only helps 871other kernel components such as subsystems and modules building their data 872access-aware applications using DAMON's core features. For this, DAMON exposes 873its all features to other kernel components via its application programming 874interface, namely ``include/linux/damon.h``. Please refer to the API 875:doc:`document </mm/damon/api>` for details of the interface. 876 877 878.. _damon_modules: 879 880Modules 881======= 882 883Because the core of DAMON is a framework for kernel components, it doesn't 884provide any direct interface for the user space. Such interfaces should be 885implemented by each DAMON API user kernel components, instead. DAMON subsystem 886itself implements such DAMON API user modules, which are supposed to be used 887for general purpose DAMON control and special purpose data access-aware system 888operations, and provides stable application binary interfaces (ABI) for the 889user space. The user space can build their efficient data access-aware 890applications using the interfaces. 891 892 893General Purpose User Interface Modules 894-------------------------------------- 895 896DAMON modules that provide user space ABIs for general purpose DAMON usage in 897runtime. 898 899Like many other ABIs, the modules create files on pseudo file systems like 900'sysfs', allow users to specify their requests to and get the answers from 901DAMON by writing to and reading from the files. As a response to such I/O, 902DAMON user interface modules control DAMON and retrieve the results as user 903requested via the DAMON API, and return the results to the user-space. 904 905The ABIs are designed to be used for user space applications development, 906rather than human beings' fingers. Human users are recommended to use such 907user space tools. One such Python-written user space tool is available at 908Github (https://github.com/damonitor/damo), Pypi 909(https://pypistats.org/packages/damo), and multiple distros 910(https://repology.org/project/damo/versions). 911 912Currently, one module for this type, namely 'DAMON sysfs interface' is 913available. Please refer to the ABI :ref:`doc <sysfs_interface>` for details of 914the interfaces. 915 916 917.. _damon_modules_special_purpose: 918 919Special-Purpose Access-aware Kernel Modules 920------------------------------------------- 921 922DAMON modules that provide user space ABI for specific purpose DAMON usage. 923 924DAMON user interface modules are for full control of all DAMON features in 925runtime. For each special-purpose system-wide data access-aware system 926operations such as proactive reclamation or LRU lists balancing, the interfaces 927could be simplified by removing unnecessary knobs for the specific purpose, and 928extended for boot-time and even compile time control. Default values of DAMON 929control parameters for the usage would also need to be optimized for the 930purpose. 931 932To support such cases, yet more DAMON API user kernel modules that provide more 933simple and optimized user space interfaces are available. Currently, two 934modules for proactive reclamation and LRU lists manipulation are provided. For 935more detail, please read the usage documents for those 936(:doc:`/admin-guide/mm/damon/stat`, :doc:`/admin-guide/mm/damon/reclaim` and 937:doc:`/admin-guide/mm/damon/lru_sort`). 938 939.. _damon_design_special_purpose_modules_exclusivity: 940 941Note that these modules currently run in an exclusive manner. If one of those 942is already running, others will return ``-EBUSY`` upon start requests. 943 944Sample DAMON Modules 945-------------------- 946 947DAMON modules that provides example DAMON kernel API usages. 948 949kernel programmers can build their own special or general purpose DAMON modules 950using DAMON kernel API. To help them easily understand how DAMON kernel API 951can be used, a few sample modules are provided under ``samples/damon/`` of the 952linux source tree. Please note that these modules are not developed for being 953used on real products, but only for showing how DAMON kernel API can be used in 954simple ways. 955