616 lines · plain
1.. SPDX-License-Identifier: GPL-2.02 3======4Design5======6 7 8.. _damon_design_execution_model_and_data_structures:9 10Execution Model and Data Structures11===================================12 13The monitoring-related information including the monitoring request14specification and DAMON-based operation schemes are stored in a data structure15called DAMON ``context``. DAMON executes each context with a kernel thread16called ``kdamond``. Multiple kdamonds could run in parallel, for different17types of monitoring.18 19To know how user-space can do the configurations and start/stop DAMON, refer to20:ref:`DAMON sysfs interface <sysfs_interface>` documentation.21 22 23Overall Architecture24====================25 26DAMON subsystem is configured with three layers including27 28- :ref:`Operations Set <damon_operations_set>`: Implements fundamental29 operations for DAMON that depends on the given monitoring target30 address-space and available set of software/hardware primitives,31- :ref:`Core <damon_core_logic>`: Implements core logics including monitoring32 overhead/accuracy control and access-aware system operations on top of the33 operations set layer, and34- :ref:`Modules <damon_modules>`: Implements kernel modules for various35 purposes that provides interfaces for the user space, on top of the core36 layer.37 38 39.. _damon_operations_set:40 41Operations Set Layer42====================43 44.. _damon_design_configurable_operations_set:45 46For data access monitoring and additional low level work, DAMON needs a set of47implementations for specific operations that are dependent on and optimized for48the given target address space. For example, below two operations for access49monitoring are address-space dependent.50 511. Identification of the monitoring target address range for the address space.522. Access check of specific address range in the target space.53 54DAMON consolidates these implementations in a layer called DAMON Operations55Set, and defines the interface between it and the upper layer. The upper layer56is dedicated for DAMON's core logics including the mechanism for control of the57monitoring accruracy and the overhead.58 59Hence, DAMON can easily be extended for any address space and/or available60hardware features by configuring the core logic to use the appropriate61operations set. If there is no available operations set for a given purpose, a62new operations set can be implemented following the interface between the63layers.64 65For example, physical memory, virtual memory, swap space, those for specific66processes, NUMA nodes, files, and backing memory devices would be supportable.67Also, if some architectures or devices support special optimized access check68features, those will be easily configurable.69 70DAMON currently provides below three operation sets. Below two subsections71describe how those work.72 73 - vaddr: Monitor virtual address spaces of specific processes74 - fvaddr: Monitor fixed virtual address ranges75 - paddr: Monitor the physical address space of the system76 77To know how user-space can do the configuration via :ref:`DAMON sysfs interface78<sysfs_interface>`, refer to :ref:`operations <sysfs_context>` file part of the79documentation.80 81 82 .. _damon_design_vaddr_target_regions_construction:83 84VMA-based Target Address Range Construction85-------------------------------------------86 87A mechanism of ``vaddr`` DAMON operations set that automatically initializes88and updates the monitoring target address regions so that entire memory89mappings of the target processes can be covered.90 91This mechanism is only for the ``vaddr`` operations set. In cases of92``fvaddr`` and ``paddr`` operation sets, users are asked to manually set the93monitoring target address ranges.94 95Only small parts in the super-huge virtual address space of the processes are96mapped to the physical memory and accessed. Thus, tracking the unmapped97address regions is just wasteful. However, because DAMON can deal with some98level of noise using the adaptive regions adjustment mechanism, tracking every99mapping is not strictly required but could even incur a high overhead in some100cases. That said, too huge unmapped areas inside the monitoring target should101be removed to not take the time for the adaptive mechanism.102 103For the reason, this implementation converts the complex mappings to three104distinct regions that cover every mapped area of the address space. The two105gaps between the three regions are the two biggest unmapped areas in the given106address space. The two biggest unmapped areas would be the gap between the107heap and the uppermost mmap()-ed region, and the gap between the lowermost108mmap()-ed region and the stack in most of the cases. Because these gaps are109exceptionally huge in usual address spaces, excluding these will be sufficient110to make a reasonable trade-off. Below shows this in detail::111 112 <heap>113 <BIG UNMAPPED REGION 1>114 <uppermost mmap()-ed region>115 (small mmap()-ed regions and munmap()-ed regions)116 <lowermost mmap()-ed region>117 <BIG UNMAPPED REGION 2>118 <stack>119 120 121PTE Accessed-bit Based Access Check122-----------------------------------123 124Both of the implementations for physical and virtual address spaces use PTE125Accessed-bit for basic access checks. Only one difference is the way of126finding the relevant PTE Accessed bit(s) from the address. While the127implementation for the virtual address walks the page table for the target task128of the address, the implementation for the physical address walks every page129table having a mapping to the address. In this way, the implementations find130and clear the bit(s) for next sampling target address and checks whether the131bit(s) set again after one sampling period. This could disturb other kernel132subsystems using the Accessed bits, namely Idle page tracking and the reclaim133logic. DAMON does nothing to avoid disturbing Idle page tracking, so handling134the interference is the responsibility of sysadmins. However, it solves the135conflict with the reclaim logic using ``PG_idle`` and ``PG_young`` page flags,136as Idle page tracking does.137 138 139.. _damon_core_logic:140 141Core Logics142===========143 144.. _damon_design_monitoring:145 146Monitoring147----------148 149Below four sections describe each of the DAMON core mechanisms and the five150monitoring attributes, ``sampling interval``, ``aggregation interval``,151``update interval``, ``minimum number of regions``, and ``maximum number of152regions``.153 154To know how user-space can set the attributes via :ref:`DAMON sysfs interface155<sysfs_interface>`, refer to :ref:`monitoring_attrs <sysfs_monitoring_attrs>`156part of the documentation.157 158 159Access Frequency Monitoring160~~~~~~~~~~~~~~~~~~~~~~~~~~~161 162The output of DAMON says what pages are how frequently accessed for a given163duration. The resolution of the access frequency is controlled by setting164``sampling interval`` and ``aggregation interval``. In detail, DAMON checks165access to each page per ``sampling interval`` and aggregates the results. In166other words, counts the number of the accesses to each page. After each167``aggregation interval`` passes, DAMON calls callback functions that previously168registered by users so that users can read the aggregated results and then169clears the results. This can be described in below simple pseudo-code::170 171 while monitoring_on:172 for page in monitoring_target:173 if accessed(page):174 nr_accesses[page] += 1175 if time() % aggregation_interval == 0:176 for callback in user_registered_callbacks:177 callback(monitoring_target, nr_accesses)178 for page in monitoring_target:179 nr_accesses[page] = 0180 sleep(sampling interval)181 182The monitoring overhead of this mechanism will arbitrarily increase as the183size of the target workload grows.184 185 186.. _damon_design_region_based_sampling:187 188Region Based Sampling189~~~~~~~~~~~~~~~~~~~~~190 191To avoid the unbounded increase of the overhead, DAMON groups adjacent pages192that assumed to have the same access frequencies into a region. As long as the193assumption (pages in a region have the same access frequencies) is kept, only194one page in the region is required to be checked. Thus, for each ``sampling195interval``, DAMON randomly picks one page in each region, waits for one196``sampling interval``, checks whether the page is accessed meanwhile, and197increases the access frequency counter of the region if so. The counter is198called ``nr_accesses`` of the region. Therefore, the monitoring overhead is199controllable by setting the number of regions. DAMON allows users to set the200minimum and the maximum number of regions for the trade-off.201 202This scheme, however, cannot preserve the quality of the output if the203assumption is not guaranteed.204 205 206Adaptive Regions Adjustment207~~~~~~~~~~~~~~~~~~~~~~~~~~~208 209Even somehow the initial monitoring target regions are well constructed to210fulfill the assumption (pages in same region have similar access frequencies),211the data access pattern can be dynamically changed. This will result in low212monitoring quality. To keep the assumption as much as possible, DAMON213adaptively merges and splits each region based on their access frequency.214 215For each ``aggregation interval``, it compares the access frequencies216(``nr_accesses``) of adjacent regions. If the difference is small, and if the217sum of the two regions' sizes is smaller than the size of total regions divided218by the ``minimum number of regions``, DAMON merges the two regions. If the219resulting number of total regions is still higher than ``maximum number of220regions``, it repeats the merging with increasing access frequenceis difference221threshold until the upper-limit of the number of regions is met, or the222threshold becomes higher than possible maximum value (``aggregation interval``223divided by ``sampling interval``). Then, after it reports and clears the224aggregated access frequency of each region, it splits each region into two or225three regions if the total number of regions will not exceed the user-specified226maximum number of regions after the split.227 228In this way, DAMON provides its best-effort quality and minimal overhead while229keeping the bounds users set for their trade-off.230 231 232.. _damon_design_age_tracking:233 234Age Tracking235~~~~~~~~~~~~236 237By analyzing the monitoring results, users can also find how long the current238access pattern of a region has maintained. That could be used for good239understanding of the access pattern. For example, page placement algorithm240utilizing both the frequency and the recency could be implemented using that.241To make such access pattern maintained period analysis easier, DAMON maintains242yet another counter called ``age`` in each region. For each ``aggregation243interval``, DAMON checks if the region's size and access frequency244(``nr_accesses``) has significantly changed. If so, the counter is reset to245zero. Otherwise, the counter is increased.246 247 248Dynamic Target Space Updates Handling249~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~250 251The monitoring target address range could dynamically changed. For example,252virtual memory could be dynamically mapped and unmapped. Physical memory could253be hot-plugged.254 255As the changes could be quite frequent in some cases, DAMON allows the256monitoring operations to check dynamic changes including memory mapping changes257and applies it to monitoring operations-related data structures such as the258abstracted monitoring target memory area only for each of a user-specified time259interval (``update interval``).260 261User-space can get the monitoring results via DAMON sysfs interface and/or262tracepoints. For more details, please refer to the documentations for263:ref:`DAMOS tried regions <sysfs_schemes_tried_regions>` and :ref:`tracepoint`,264respectively.265 266 267.. _damon_design_damos:268 269Operation Schemes270-----------------271 272One common purpose of data access monitoring is access-aware system efficiency273optimizations. For example,274 275 paging out memory regions that are not accessed for more than two minutes276 277or278 279 using THP for memory regions that are larger than 2 MiB and showing a high280 access frequency for more than one minute.281 282One straightforward approach for such schemes would be profile-guided283optimizations. That is, getting data access monitoring results of the284workloads or the system using DAMON, finding memory regions of special285characteristics by profiling the monitoring results, and making system286operation changes for the regions. The changes could be made by modifying or287providing advice to the software (the application and/or the kernel), or288reconfiguring the hardware. Both offline and online approaches could be289available.290 291Among those, providing advice to the kernel at runtime would be flexible and292effective, and therefore widely be used. However, implementing such schemes293could impose unnecessary redundancy and inefficiency. The profiling could be294redundant if the type of interest is common. Exchanging the information295including monitoring results and operation advice between kernel and user296spaces could be inefficient.297 298To allow users to reduce such redundancy and inefficiencies by offloading the299works, DAMON provides a feature called Data Access Monitoring-based Operation300Schemes (DAMOS). It lets users specify their desired schemes at a high301level. For such specifications, DAMON starts monitoring, finds regions having302the access pattern of interest, and applies the user-desired operation actions303to the regions, for every user-specified time interval called304``apply_interval``.305 306To know how user-space can set ``apply_interval`` via :ref:`DAMON sysfs307interface <sysfs_interface>`, refer to :ref:`apply_interval_us <sysfs_scheme>`308part of the documentation.309 310 311.. _damon_design_damos_action:312 313Operation Action314~~~~~~~~~~~~~~~~315 316The management action that the users desire to apply to the regions of their317interest. For example, paging out, prioritizing for next reclamation victim318selection, advising ``khugepaged`` to collapse or split, or doing nothing but319collecting statistics of the regions.320 321The list of supported actions is defined in DAMOS, but the implementation of322each action is in the DAMON operations set layer because the implementation323normally depends on the monitoring target address space. For example, the code324for paging specific virtual address ranges out would be different from that for325physical address ranges. And the monitoring operations implementation sets are326not mandated to support all actions of the list. Hence, the availability of327specific DAMOS action depends on what operations set is selected to be used328together.329 330The list of the supported actions, their meaning, and DAMON operations sets331that supports each action are as below.332 333 - ``willneed``: Call ``madvise()`` for the region with ``MADV_WILLNEED``.334 Supported by ``vaddr`` and ``fvaddr`` operations set.335 - ``cold``: Call ``madvise()`` for the region with ``MADV_COLD``.336 Supported by ``vaddr`` and ``fvaddr`` operations set.337 - ``pageout``: Reclaim the region.338 Supported by ``vaddr``, ``fvaddr`` and ``paddr`` operations set.339 - ``hugepage``: Call ``madvise()`` for the region with ``MADV_HUGEPAGE``.340 Supported by ``vaddr`` and ``fvaddr`` operations set.341 - ``nohugepage``: Call ``madvise()`` for the region with ``MADV_NOHUGEPAGE``.342 Supported by ``vaddr`` and ``fvaddr`` operations set.343 - ``lru_prio``: Prioritize the region on its LRU lists.344 Supported by ``paddr`` operations set.345 - ``lru_deprio``: Deprioritize the region on its LRU lists.346 Supported by ``paddr`` operations set.347 - ``migrate_hot``: Migrate the regions prioritizing warmer regions.348 Supported by ``paddr`` operations set.349 - ``migrate_cold``: Migrate the regions prioritizing colder regions.350 Supported by ``paddr`` operations set.351 - ``stat``: Do nothing but count the statistics.352 Supported by all operations sets.353 354Applying the actions except ``stat`` to a region is considered as changing the355region's characteristics. Hence, DAMOS resets the age of regions when any such356actions are applied to those.357 358To know how user-space can set the action via :ref:`DAMON sysfs interface359<sysfs_interface>`, refer to :ref:`action <sysfs_scheme>` part of the360documentation.361 362 363.. _damon_design_damos_access_pattern:364 365Target Access Pattern366~~~~~~~~~~~~~~~~~~~~~367 368The access pattern of the schemes' interest. The patterns are constructed with369the properties that DAMON's monitoring results provide, specifically the size,370the access frequency, and the age. Users can describe their access pattern of371interest by setting minimum and maximum values of the three properties. If a372region's three properties are in the ranges, DAMOS classifies it as one of the373regions that the scheme is having an interest in.374 375To know how user-space can set the access pattern via :ref:`DAMON sysfs376interface <sysfs_interface>`, refer to :ref:`access_pattern377<sysfs_access_pattern>` part of the documentation.378 379 380.. _damon_design_damos_quotas:381 382Quotas383~~~~~~384 385DAMOS upper-bound overhead control feature. DAMOS could incur high overhead if386the target access pattern is not properly tuned. For example, if a huge memory387region having the access pattern of interest is found, applying the scheme's388action to all pages of the huge region could consume unacceptably large system389resources. Preventing such issues by tuning the access pattern could be390challenging, especially if the access patterns of the workloads are highly391dynamic.392 393To mitigate that situation, DAMOS provides an upper-bound overhead control394feature called quotas. It lets users specify an upper limit of time that DAMOS395can use for applying the action, and/or a maximum bytes of memory regions that396the action can be applied within a user-specified time duration.397 398To know how user-space can set the basic quotas via :ref:`DAMON sysfs interface399<sysfs_interface>`, refer to :ref:`quotas <sysfs_quotas>` part of the400documentation.401 402 403.. _damon_design_damos_quotas_prioritization:404 405Prioritization406^^^^^^^^^^^^^^407 408A mechanism for making a good decision under the quotas. When the action409cannot be applied to all regions of interest due to the quotas, DAMOS410prioritizes regions and applies the action to only regions having high enough411priorities so that it will not exceed the quotas.412 413The prioritization mechanism should be different for each action. For example,414rarely accessed (colder) memory regions would be prioritized for page-out415scheme action. In contrast, the colder regions would be deprioritized for huge416page collapse scheme action. Hence, the prioritization mechanisms for each417action are implemented in each DAMON operations set, together with the actions.418 419Though the implementation is up to the DAMON operations set, it would be common420to calculate the priority using the access pattern properties of the regions.421Some users would want the mechanisms to be personalized for their specific422case. For example, some users would want the mechanism to weigh the recency423(``age``) more than the access frequency (``nr_accesses``). DAMOS allows users424to specify the weight of each access pattern property and passes the425information to the underlying mechanism. Nevertheless, how and even whether426the weight will be respected are up to the underlying prioritization mechanism427implementation.428 429To know how user-space can set the prioritization weights via :ref:`DAMON sysfs430interface <sysfs_interface>`, refer to :ref:`weights <sysfs_quotas>` part of431the documentation.432 433 434.. _damon_design_damos_quotas_auto_tuning:435 436Aim-oriented Feedback-driven Auto-tuning437^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^438 439Automatic feedback-driven quota tuning. Instead of setting the absolute quota440value, users can specify the metric of their interest, and what target value441they want the metric value to be. DAMOS then automatically tunes the442aggressiveness (the quota) of the corresponding scheme. For example, if DAMOS443is under achieving the goal, DAMOS automatically increases the quota. If DAMOS444is over achieving the goal, it decreases the quota.445 446The goal can be specified with three parameters, namely ``target_metric``,447``target_value``, and ``current_value``. The auto-tuning mechanism tries to448make ``current_value`` of ``target_metric`` be same to ``target_value``.449Currently, two ``target_metric`` are provided.450 451- ``user_input``: User-provided value. Users could use any metric that they452 has interest in for the value. Use space main workload's latency or453 throughput, system metrics like free memory ratio or memory pressure stall454 time (PSI) could be examples. Note that users should explicitly set455 ``current_value`` on their own in this case. In other words, users should456 repeatedly provide the feedback.457- ``some_mem_psi_us``: System-wide ``some`` memory pressure stall information458 in microseconds that measured from last quota reset to next quota reset.459 DAMOS does the measurement on its own, so only ``target_value`` need to be460 set by users at the initial time. In other words, DAMOS does self-feedback.461 462To know how user-space can set the tuning goal metric, the target value, and/or463the current value via :ref:`DAMON sysfs interface <sysfs_interface>`, refer to464:ref:`quota goals <sysfs_schemes_quota_goals>` part of the documentation.465 466 467.. _damon_design_damos_watermarks:468 469Watermarks470~~~~~~~~~~471 472Conditional DAMOS (de)activation automation. Users might want DAMOS to run473only under certain situations. For example, when a sufficient amount of free474memory is guaranteed, running a scheme for proactive reclamation would only475consume unnecessary system resources. To avoid such consumption, the user would476need to manually monitor some metrics such as free memory ratio, and turn477DAMON/DAMOS on or off.478 479DAMOS allows users to offload such works using three watermarks. It allows the480users to configure the metric of their interest, and three watermark values,481namely high, middle, and low. If the value of the metric becomes above the482high watermark or below the low watermark, the scheme is deactivated. If the483metric becomes below the mid watermark but above the low watermark, the scheme484is activated. If all schemes are deactivated by the watermarks, the monitoring485is also deactivated. In this case, the DAMON worker thread only periodically486checks the watermarks and therefore incurs nearly zero overhead.487 488To know how user-space can set the watermarks via :ref:`DAMON sysfs interface489<sysfs_interface>`, refer to :ref:`watermarks <sysfs_watermarks>` part of the490documentation.491 492 493.. _damon_design_damos_filters:494 495Filters496~~~~~~~497 498Non-access pattern-based target memory regions filtering. If users run499self-written programs or have good profiling tools, they could know something500more than the kernel, such as future access patterns or some special501requirements for specific types of memory. For example, some users may know502only anonymous pages can impact their program's performance. They can also503have a list of latency-critical processes.504 505To let users optimize DAMOS schemes with such special knowledge, DAMOS provides506a feature called DAMOS filters. The feature allows users to set an arbitrary507number of filters for each scheme. Each filter specifies the type of target508memory, and whether it should exclude the memory of the type (filter-out), or509all except the memory of the type (filter-in).510 511For efficient handling of filters, some types of filters are handled by the512core layer, while others are handled by operations set. In the latter case,513hence, support of the filter types depends on the DAMON operations set. In514case of the core layer-handled filters, the memory regions that excluded by the515filter are not counted as the scheme has tried to the region. In contrast, if516a memory regions is filtered by an operations set layer-handled filter, it is517counted as the scheme has tried. This difference affects the statistics.518 519Below types of filters are currently supported.520 521- anonymous page522 - Applied to pages that containing data that not stored in files.523 - Handled by operations set layer. Supported by only ``paddr`` set.524- memory cgroup525 - Applied to pages that belonging to a given cgroup.526 - Handled by operations set layer. Supported by only ``paddr`` set.527- young page528 - Applied to pages that are accessed after the last access check from the529 scheme.530 - Handled by operations set layer. Supported by only ``paddr`` set.531- address range532 - Applied to pages that belonging to a given address range.533 - Handled by the core logic.534- DAMON monitoring target535 - Applied to pages that belonging to a given DAMON monitoring target.536 - Handled by the core logic.537 538To know how user-space can set the watermarks via :ref:`DAMON sysfs interface539<sysfs_interface>`, refer to :ref:`filters <sysfs_filters>` part of the540documentation.541 542 543Application Programming Interface544---------------------------------545 546The programming interface for kernel space data access-aware applications.547DAMON is a framework, so it does nothing by itself. Instead, it only helps548other kernel components such as subsystems and modules building their data549access-aware applications using DAMON's core features. For this, DAMON exposes550its all features to other kernel components via its application programming551interface, namely ``include/linux/damon.h``. Please refer to the API552:doc:`document </mm/damon/api>` for details of the interface.553 554 555.. _damon_modules:556 557Modules558=======559 560Because the core of DAMON is a framework for kernel components, it doesn't561provide any direct interface for the user space. Such interfaces should be562implemented by each DAMON API user kernel components, instead. DAMON subsystem563itself implements such DAMON API user modules, which are supposed to be used564for general purpose DAMON control and special purpose data access-aware system565operations, and provides stable application binary interfaces (ABI) for the566user space. The user space can build their efficient data access-aware567applications using the interfaces.568 569 570General Purpose User Interface Modules571--------------------------------------572 573DAMON modules that provide user space ABIs for general purpose DAMON usage in574runtime.575 576DAMON user interface modules, namely 'DAMON sysfs interface' and 'DAMON debugfs577interface' are DAMON API user kernel modules that provide ABIs to the578user-space. Please note that DAMON debugfs interface is currently deprecated.579 580Like many other ABIs, the modules create files on sysfs and debugfs, allow581users to specify their requests to and get the answers from DAMON by writing to582and reading from the files. As a response to such I/O, DAMON user interface583modules control DAMON and retrieve the results as user requested via the DAMON584API, and return the results to the user-space.585 586The ABIs are designed to be used for user space applications development,587rather than human beings' fingers. Human users are recommended to use such588user space tools. One such Python-written user space tool is available at589Github (https://github.com/damonitor/damo), Pypi590(https://pypistats.org/packages/damo), and Fedora591(https://packages.fedoraproject.org/pkgs/python-damo/damo/).592 593Please refer to the ABI :doc:`document </admin-guide/mm/damon/usage>` for594details of the interfaces.595 596 597Special-Purpose Access-aware Kernel Modules598-------------------------------------------599 600DAMON modules that provide user space ABI for specific purpose DAMON usage.601 602DAMON sysfs/debugfs user interfaces are for full control of all DAMON features603in runtime. For each special-purpose system-wide data access-aware system604operations such as proactive reclamation or LRU lists balancing, the interfaces605could be simplified by removing unnecessary knobs for the specific purpose, and606extended for boot-time and even compile time control. Default values of DAMON607control parameters for the usage would also need to be optimized for the608purpose.609 610To support such cases, yet more DAMON API user kernel modules that provide more611simple and optimized user space interfaces are available. Currently, two612modules for proactive reclamation and LRU lists manipulation are provided. For613more detail, please read the usage documents for those614(:doc:`/admin-guide/mm/damon/reclaim` and615:doc:`/admin-guide/mm/damon/lru_sort`).616