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