DAMON Design

실행 모델과 데이터 구조

이 문서는 DAMON의 설계를 설명합니다. 모니터링 요청 명세와 DAMON 기반 동작 스킴을 포함한 모니터링 관련 정보는 DAMON `context`라는 데이터 구조에 저장됩니다.

DAMON은 각 context를 `kdamond`라는 커널 스레드로 실행합니다. 서로 다른 유형의 모니터링을 위해 여러 kdamond가 병렬로 실행될 수 있습니다.

사용자 공간에서 설정하고 DAMON을 시작하거나 중지하는 방법은 `DAMON sysfs interface` 문서를 참조합니다.

.. SPDX-License-Identifier: GPL-2.0

======
Design
======


.. _damon_design_execution_model_and_data_structures:

Execution Model and Data Structures
===================================

The monitoring-related information including the monitoring request
specification and DAMON-based operation schemes are stored in a data structure
called DAMON ``context``.  DAMON executes each context with a kernel thread
called ``kdamond``.  Multiple kdamonds could run in parallel, for different
types of monitoring.

To know how user-space can do the configurations and start/stop DAMON, refer to
:ref:`DAMON sysfs interface <sysfs_interface>` documentation.

전체 아키텍처

DAMON 서브시스템은 다음 세 계층으로 구성됩니다.

• `Operations Set`: 지정된 모니터링 대상 주소 공간과 사용 가능한 소프트웨어 및 하드웨어 primitive에 의존하는 DAMON 기본 동작을 구현합니다.
• `Core`: operations set 계층 위에서 모니터링 오버헤드와 정확도 제어, 접근 패턴을 인지하는 시스템 동작을 비롯한 핵심 로직을 구현합니다.
• `Modules`: core 계층 위에서 여러 목적의 커널 모듈과 사용자 공간 인터페이스를 구현합니다.

Overall Architecture
====================

DAMON subsystem is configured with three layers including

- :ref:`Operations Set <damon_operations_set>`: Implements fundamental
  operations for DAMON that depends on the given monitoring target
  address-space and available set of software/hardware primitives,
- :ref:`Core <damon_core_logic>`: Implements core logics including monitoring
  overhead/accuracy control and access-aware system operations on top of the
  operations set layer, and
- :ref:`Modules <damon_modules>`: Implements kernel modules for various
  purposes that provides interfaces for the user space, on top of the core
  layer.

Operations Set 계층

데이터 접근 모니터링과 추가 저수준 작업을 수행하려면 대상 주소 공간에 의존하고 그 공간에 최적화된 동작 구현 집합이 필요합니다. 대표적으로 주소 공간에서 모니터링할 대상 주소 범위를 식별하는 동작과 대상 공간의 특정 주소 범위에 대한 접근 여부를 검사하는 동작은 주소 공간에 따라 달라집니다.

DAMON은 이런 구현을 DAMON Operations Set이라는 계층에 모으고 상위 계층과의 인터페이스를 정의합니다. 상위 계층은 모니터링 정확도와 오버헤드를 제어하는 메커니즘을 포함한 DAMON 핵심 로직에 집중합니다.

따라서 적절한 operations set을 core 로직에 연결하면 임의의 주소 공간이나 사용 가능한 하드웨어 기능으로 DAMON을 쉽게 확장할 수 있습니다. 목적에 맞는 operations set이 없다면 계층 사이의 인터페이스에 따라 새 구현을 추가할 수 있습니다.

지원 가능한 예로는 물리 메모리, 가상 메모리, swap 공간, 특정 프로세스나 NUMA node, 파일 및 backing memory device가 있습니다. 아키텍처나 장치가 최적화된 특별 접근 검사 기능을 제공하는 경우에도 쉽게 구성할 수 있습니다.

• `vaddr`: 특정 프로세스의 가상 주소 공간을 모니터링합니다.
• `fvaddr`: 고정된 가상 주소 범위를 모니터링합니다.
• `paddr`: 시스템의 물리 주소 공간을 모니터링합니다.

사용자 공간에서 sysfs로 이를 설정하는 방법은 `DAMON sysfs interface`의 `operations` 파일 설명을 참조합니다.

.. _damon_operations_set:

Operations Set Layer
====================

.. _damon_design_configurable_operations_set:

For data access monitoring and additional low level work, DAMON needs a set of
implementations for specific operations that are dependent on and optimized for
the given target address space.  For example, below two operations for access
monitoring are address-space dependent.

1. Identification of the monitoring target address range for the address space.
2. Access check of specific address range in the target space.

DAMON consolidates these implementations in a layer called DAMON Operations
Set, and defines the interface between it and the upper layer.  The upper layer
is dedicated for DAMON's core logics including the mechanism for control of the
monitoring accuracy and the overhead.

Hence, DAMON can easily be extended for any address space and/or available
hardware features by configuring the core logic to use the appropriate
operations set.  If there is no available operations set for a given purpose, a
new operations set can be implemented following the interface between the
layers.

For example, physical memory, virtual memory, swap space, those for specific
processes, NUMA nodes, files, and backing memory devices would be supportable.
Also, if some architectures or devices support special optimized access check
features, those will be easily configurable.

DAMON currently provides below three operation sets.  Below three subsections
describe how those work.

 - vaddr: Monitor virtual address spaces of specific processes
 - fvaddr: Monitor fixed virtual address ranges
 - paddr: Monitor the physical address space of the system

To know how user-space can do the configuration via :ref:`DAMON sysfs interface
<sysfs_interface>`, refer to :ref:`operations <sysfs_context>` file part of the
documentation.

VMA 기반 대상 주소 범위 구성

`vaddr` DAMON operations set은 대상 프로세스의 모든 메모리 mapping을 덮도록 모니터링 대상 주소 region을 자동으로 초기화하고 갱신합니다. 이 메커니즘은 `vaddr` 전용이며, `fvaddr`와 `paddr`에서는 사용자가 모니터링 대상 주소 범위를 직접 지정해야 합니다.

프로세스의 매우 큰 가상 주소 공간 가운데 실제 물리 메모리에 mapping되고 접근되는 부분은 작으므로 unmapped 주소 영역 추적은 낭비입니다. 반면 DAMON은 adaptive regions adjustment로 어느 정도 잡음을 다룰 수 있어 모든 mapping을 하나씩 추적할 필요가 없고, 오히려 그렇게 하면 오버헤드가 커질 수 있습니다. 다만 지나치게 큰 unmapped 영역은 적응 메커니즘이 처리하느라 시간을 쓰지 않도록 대상에서 제외해야 합니다.

이 구현은 복잡한 mapping을 주소 공간의 모든 mapped 영역을 포괄하는 세 개의 서로 다른 region으로 변환합니다. 세 region 사이의 두 gap은 주소 공간에서 가장 큰 두 unmapped 영역입니다. 일반적인 주소 공간에서는 heap과 가장 위쪽 `mmap()` region 사이, 가장 아래쪽 `mmap()` region과 stack 사이의 gap이 이에 해당합니다. 이 두 gap은 보통 유난히 크므로 제외하는 것만으로 합리적인 절충이 됩니다.

 .. _damon_design_vaddr_target_regions_construction:

VMA-based Target Address Range Construction
-------------------------------------------

A mechanism of ``vaddr`` DAMON operations set that automatically initializes
and updates the monitoring target address regions so that entire memory
mappings of the target processes can be covered.

This mechanism is only for the ``vaddr`` operations set.  In cases of
``fvaddr`` and ``paddr`` operation sets, users are asked to manually set the
monitoring target address ranges.

Only small parts in the super-huge virtual address space of the processes are
mapped to the physical memory and accessed.  Thus, tracking the unmapped
address regions is just wasteful.  However, because DAMON can deal with some
level of noise using the adaptive regions adjustment mechanism, tracking every
mapping is not strictly required but could even incur a high overhead in some
cases.  That said, too huge unmapped areas inside the monitoring target should
be removed to not take the time for the adaptive mechanism.

For the reason, this implementation converts the complex mappings to three
distinct regions that cover every mapped area of the address space.  The two
gaps between the three regions are the two biggest unmapped areas in the given
address space.  The two biggest unmapped areas would be the gap between the
heap and the uppermost mmap()-ed region, and the gap between the lowermost
mmap()-ed region and the stack in most of the cases.  Because these gaps are
exceptionally huge in usual address spaces, excluding these will be sufficient
to make a reasonable trade-off.  Below shows this in detail::

    <heap>
    <BIG UNMAPPED REGION 1>
    <uppermost mmap()-ed region>
    (small mmap()-ed regions and munmap()-ed regions)
    <lowermost mmap()-ed region>
    <BIG UNMAPPED REGION 2>
    <stack>

PTE Accessed bit 접근 검사와 주소 단위

물리 주소 공간과 가상 주소 공간 구현은 모두 기본 접근 검사에 PTE Accessed bit를 사용합니다. 차이는 주소로부터 관련 PTE Accessed bit를 찾는 방법입니다. 가상 주소 구현은 대상 task의 page table을 순회하고, 물리 주소 구현은 해당 주소를 mapping한 모든 page table을 순회합니다.

구현은 다음 샘플링 대상 주소의 bit를 찾아 지운 뒤 sampling period 하나가 지난 후 bit가 다시 설정되었는지 확인합니다. 이 과정은 Accessed bit를 쓰는 Idle page tracking과 reclaim 로직에 간섭할 수 있습니다. DAMON은 Idle page tracking 간섭을 피하지 않으므로 이를 처리할 책임은 시스템 관리자에게 있습니다. reclaim 로직과의 충돌은 Idle page tracking과 마찬가지로 `PG_idle` 및 `PG_young` page flag를 사용해 해결합니다.

DAMON core 계층은 모니터링 대상 주소 범위에 `unsigned long` 형식을 사용합니다. ARM 32-bit의 large physical address extension처럼 operations set의 주소 공간이 이 형식으로 표현하기에 너무 클 수 있습니다. 이를 위해 operations set별 `address unit` 매개변수를 제공하며, 실제 주소는 core 주소에 이 scale factor를 곱해 계산합니다. 지원 여부는 각 operations set 구현에 달려 있고 현재는 `paddr`만 지원합니다.

PTE Accessed-bit Based Access Check
-----------------------------------

Both of the implementations for physical and virtual address spaces use PTE
Accessed-bit for basic access checks.  Only one difference is the way of
finding the relevant PTE Accessed bit(s) from the address.  While the
implementation for the virtual address walks the page table for the target task
of the address, the implementation for the physical address walks every page
table having a mapping to the address.  In this way, the implementations find
and clear the bit(s) for next sampling target address and checks whether the
bit(s) set again after one sampling period.  This could disturb other kernel
subsystems using the Accessed bits, namely Idle page tracking and the reclaim
logic.  DAMON does nothing to avoid disturbing Idle page tracking, so handling
the interference is the responsibility of sysadmins.  However, it solves the
conflict with the reclaim logic using ``PG_idle`` and ``PG_young`` page flags,
as Idle page tracking does.

.. _damon_design_addr_unit:

Address Unit
------------

DAMON core layer uses ``unsinged long`` type for monitoring target address
ranges.  In some cases, the address space for a given operations set could be
too large to be handled with the type.  ARM (32-bit) with large physical
address extension is an example.  For such cases, a per-operations set
parameter called ``address unit`` is provided.  It represents the scale factor
that need to be multiplied to the core layer's address for calculating real
address on the given address space.  Support of ``address unit`` parameter is
up to each operations set implementation.  ``paddr`` is the only operations set
implementation that supports the parameter.

Core 모니터링 속성

DAMON core의 모니터링 메커니즘은 `sampling interval`, `aggregation interval`, `update interval`, `minimum number of regions`, `maximum number of regions`라는 다섯 속성으로 제어됩니다. 이어지는 네 절이 각 메커니즘과 속성을 설명합니다.

사용자 공간에서 이 속성을 설정하는 방법은 `DAMON sysfs interface`의 `monitoring_attrs` 부분을 참조합니다.

.. _damon_core_logic:

Core Logics
===========

.. _damon_design_monitoring:

Monitoring
----------

Below four sections describe each of the DAMON core mechanisms and the five
monitoring attributes, ``sampling interval``, ``aggregation interval``,
``update interval``, ``minimum number of regions``, and ``maximum number of
regions``.

To know how user-space can set the attributes via :ref:`DAMON sysfs interface
<sysfs_interface>`, refer to :ref:`monitoring_attrs <sysfs_monitoring_attrs>`
part of the documentation.

접근 빈도 모니터링

DAMON 출력은 주어진 기간에 어떤 page가 얼마나 자주 접근되었는지를 보여 줍니다. 접근 빈도의 해상도는 `sampling interval`과 `aggregation interval`로 제어합니다. DAMON은 각 `sampling interval`마다 각 page 접근을 검사해 결과를 합산하며, 다시 말해 page별 접근 횟수를 셉니다.

각 `aggregation interval`이 끝나면 미리 등록된 사용자 callback을 호출해 합산 결과를 읽게 한 다음 결과를 지웁니다. 아래 의사 코드는 이 동작을 나타냅니다.

while monitoring_on:
    for page in monitoring_target:
        if accessed(page):
            nr_accesses[page] += 1
    if time() % aggregation_interval == 0:
        for callback in user_registered_callbacks:
            callback(monitoring_target, nr_accesses)
        for page in monitoring_target:
            nr_accesses[page] = 0
    sleep(sampling interval)

이 메커니즘을 page 단위로 그대로 수행하면 대상 workload 크기가 증가할수록 모니터링 오버헤드가 제한 없이 커집니다.

Access Frequency Monitoring
~~~~~~~~~~~~~~~~~~~~~~~~~~~

The output of DAMON says what pages are how frequently accessed for a given
duration.  The resolution of the access frequency is controlled by setting
``sampling interval`` and ``aggregation interval``.  In detail, DAMON checks
access to each page per ``sampling interval`` and aggregates the results.  In
other words, counts the number of the accesses to each page.  After each
``aggregation interval`` passes, DAMON calls callback functions that previously
registered by users so that users can read the aggregated results and then
clears the results.  This can be described in below simple pseudo-code::

    while monitoring_on:
        for page in monitoring_target:
            if accessed(page):
                nr_accesses[page] += 1
        if time() % aggregation_interval == 0:
            for callback in user_registered_callbacks:
                callback(monitoring_target, nr_accesses)
            for page in monitoring_target:
                nr_accesses[page] = 0
        sleep(sampling interval)

The monitoring overhead of this mechanism will arbitrarily increase as the
size of the target workload grows.

Region 기반 샘플링과 적응형 조정

오버헤드가 끝없이 증가하지 않도록 DAMON은 접근 빈도가 같다고 가정할 수 있는 인접 page를 하나의 region으로 묶습니다. region 안의 page가 같은 접근 빈도를 가진다는 가정이 유지되는 동안에는 region당 page 하나만 검사하면 됩니다.

각 `sampling interval`마다 DAMON은 region마다 page 하나를 무작위로 고르고, `sampling interval` 하나를 기다린 뒤 그동안 접근되었는지 검사합니다. 접근됐다면 region의 `nr_accesses` counter를 증가시킵니다. 따라서 region 수를 정하면 모니터링 오버헤드를 제어할 수 있고, 사용자는 `minimum number of regions`와 `maximum number of regions`를 지정해 절충점을 정합니다. 다만 region 내부 접근 빈도가 같다는 가정이 깨지면 출력 품질을 보장할 수 없습니다.

초기 region이 잘 구성되어도 데이터 접근 패턴은 동적으로 바뀔 수 있습니다. DAMON은 가정을 최대한 유지하도록 접근 빈도를 바탕으로 region을 적응적으로 병합하고 분할합니다.

매 `aggregation interval`마다 인접 region의 `nr_accesses`를 비교합니다. 차이가 작고 두 region 크기의 합이 전체 region 크기를 `minimum number of regions`로 나눈 값보다 작으면 둘을 병합합니다. 전체 region 수가 여전히 `maximum number of regions`보다 많으면 접근 빈도 차이 threshold를 점차 높여 상한을 만족하거나 threshold가 가능한 최댓값인 `aggregation interval / sampling interval`보다 커질 때까지 병합을 반복합니다.

그 뒤 각 region의 합산 접근 빈도를 보고하고 지운 다음, 분할 후에도 전체 수가 사용자가 정한 최댓값을 넘지 않는 범위에서 각 region을 두 개 또는 세 개로 나눕니다. 이 방식으로 DAMON은 사용자가 정한 절충 범위 안에서 최선 노력 방식의 품질과 최소 오버헤드를 제공합니다.

.. _damon_design_region_based_sampling:

Region Based Sampling
~~~~~~~~~~~~~~~~~~~~~

To avoid the unbounded increase of the overhead, DAMON groups adjacent pages
that assumed to have the same access frequencies into a region.  As long as the
assumption (pages in a region have the same access frequencies) is kept, only
one page in the region is required to be checked.  Thus, for each ``sampling
interval``, DAMON randomly picks one page in each region, waits for one
``sampling interval``, checks whether the page is accessed meanwhile, and
increases the access frequency counter of the region if so.  The counter is
called ``nr_accesses`` of the region.  Therefore, the monitoring overhead is
controllable by setting the number of regions.  DAMON allows users to set the
minimum and the maximum number of regions for the trade-off.

This scheme, however, cannot preserve the quality of the output if the
assumption is not guaranteed.


.. _damon_design_adaptive_regions_adjustment:

Adaptive Regions Adjustment
~~~~~~~~~~~~~~~~~~~~~~~~~~~

Even somehow the initial monitoring target regions are well constructed to
fulfill the assumption (pages in same region have similar access frequencies),
the data access pattern can be dynamically changed.  This will result in low
monitoring quality.  To keep the assumption as much as possible, DAMON
adaptively merges and splits each region based on their access frequency.

For each ``aggregation interval``, it compares the access frequencies
(``nr_accesses``) of adjacent regions.  If the difference is small, and if the
sum of the two regions' sizes is smaller than the size of total regions divided
by the ``minimum number of regions``, DAMON merges the two regions.  If the
resulting number of total regions is still higher than ``maximum number of
regions``, it repeats the merging with increasing access frequenceis difference
threshold until the upper-limit of the number of regions is met, or the
threshold becomes higher than possible maximum value (``aggregation interval``
divided by ``sampling interval``).   Then, after it reports and clears the
aggregated access frequency of each region, it splits each region into two or
three regions if the total number of regions will not exceed the user-specified
maximum number of regions after the split.

In this way, DAMON provides its best-effort quality and minimal overhead while
keeping the bounds users set for their trade-off.

Age 추적과 동적 대상 공간 갱신

모니터링 결과를 분석하면 region의 현재 접근 패턴이 얼마나 오래 유지되었는지도 알 수 있습니다. 이는 접근 패턴 이해에 유용하며, 예를 들어 빈도와 최근성을 함께 이용하는 page placement 알고리즘을 구현할 수 있습니다.

DAMON은 이 분석을 쉽게 하도록 각 region에 `age` counter를 유지합니다. 매 `aggregation interval`마다 region 크기와 접근 빈도인 `nr_accesses`가 유의미하게 변했는지 확인합니다. 변했다면 `age`를 0으로 재설정하고, 그렇지 않으면 증가시킵니다.

모니터링 대상 주소 범위도 동적으로 변할 수 있습니다. 가상 메모리는 mapping되거나 unmapping될 수 있고, 물리 메모리는 hot-plug될 수 있습니다. 이런 변경이 매우 잦을 수 있으므로 DAMON은 매번 반영하지 않고 사용자가 지정한 `update interval`마다 메모리 mapping 변경 같은 동적 변화를 확인해 추상화된 모니터링 대상 메모리 영역 등 관련 데이터 구조에 적용합니다.

사용자 공간은 DAMON sysfs interface 또는 tracepoint로 결과를 얻을 수 있습니다. 자세한 내용은 `DAMOS tried regions`와 `tracepoint` 문서를 각각 참조합니다.

.. _damon_design_age_tracking:

Age Tracking
~~~~~~~~~~~~

By analyzing the monitoring results, users can also find how long the current
access pattern of a region has maintained.  That could be used for good
understanding of the access pattern.  For example, page placement algorithm
utilizing both the frequency and the recency could be implemented using that.
To make such access pattern maintained period analysis easier, DAMON maintains
yet another counter called ``age`` in each region.  For each ``aggregation
interval``, DAMON checks if the region's size and access frequency
(``nr_accesses``) has significantly changed.  If so, the counter is reset to
zero.  Otherwise, the counter is increased.


Dynamic Target Space Updates Handling
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The monitoring target address range could dynamically changed.  For example,
virtual memory could be dynamically mapped and unmapped.  Physical memory could
be hot-plugged.

As the changes could be quite frequent in some cases, DAMON allows the
monitoring operations to check dynamic changes including memory mapping changes
and applies it to monitoring operations-related data structures such as the
abstracted monitoring target memory area only for each of a user-specified time
interval (``update interval``).

User-space can get the monitoring results via DAMON sysfs interface and/or
tracepoints.  For more details, please refer to the documentations for
:ref:`DAMOS tried regions <sysfs_schemes_tried_regions>` and :ref:`tracepoint`,
respectively.

모니터링 매개변수 조정 지침

요약하면 목적에 의미 있는 양의 접근을 포착하도록 `aggregation interval`을 정합니다. 합산된 모니터링 결과 snapshot에서 region의 `nr_accesses`와 `age`로 접근량을 측정할 수 있습니다. 기본값 `100ms`는 많은 경우 너무 짧습니다. `sampling interval`은 `aggregation interval`에 비례하도록 정하며 기본 및 권장 비율은 `1/20`입니다.

`aggregation interval`은 workload가 모니터링 목적에 필요한 접근량을 그 안에서 만들 수 있는 시간이어야 합니다. 너무 짧으면 소수의 접근만 포착되어 모든 곳이 똑같이 드물게 접근되는 것처럼 보이므로 많은 목적에서 쓸모가 없습니다. 너무 길면 목적의 시간 규모에 따라 adaptive regions adjustment가 region을 수렴시키는 시간이 지나치게 길어질 수 있습니다.

workload가 실제로는 드물게 접근하지만 사용자가 interval마다 포착하려는 접근량을 너무 높게 잡았을 때도 문제가 생깁니다. 이 경우 `aggregation interval`마다 포착할 목표 접근량을 다시 신중히 정해야 합니다. 접근량은 `nr_accesses`뿐 아니라 `age`에도 나타납니다. 모든 region의 `nr_accesses`가 0이어도 `age`를 최근성 정보로 사용해 region을 구분할 수 있습니다.

최적 `aggregation interval`은 workload의 접근 집약도에 달려 있으므로 각 합산 snapshot이 포착한 접근량을 보고 조정해야 합니다. 기본 100ms는 특히 큰 시스템에서 너무 짧은 경우가 많습니다.

`sampling interval`은 각 aggregation의 해상도를 결정합니다. 너무 크면 모든 region이 똑같이 드물게 또는 자주 접근된 것처럼 보여 접근 패턴으로 구분할 수 없고 결과가 쓸모없어집니다. 너무 작으면 해상도는 나빠지지 않지만 오버헤드가 증가합니다. 목적에 충분한 해상도를 제공한다면 불필요하게 더 낮추지 않아야 합니다. `aggregation interval`에 비례시키고 기본 비율 `1/20`을 사용하는 것이 권장됩니다.

DAMON은 이 수동 조정 지침을 바탕으로 더 직관적인 knob 기반 interval 자동 조정도 제공합니다. 자세한 내용은 `Monitoring Intervals Auto-tuning` 설계 문서를, 실제 조정 예는 `monitoring_intervals_tuning_example` 문서를 참조합니다.

.. _damon_design_monitoring_params_tuning_guide:

Monitoring Parameters Tuning Guide
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

In short, set ``aggregation interval`` to capture meaningful amount of accesses
for the purpose.  The amount of accesses can be measured using ``nr_accesses``
and ``age`` of regions in the aggregated monitoring results snapshot.  The
default value of the interval, ``100ms``, turns out to be too short in many
cases.  Set ``sampling interval`` proportional to ``aggregation interval``.  By
default, ``1/20`` is recommended as the ratio.

``Aggregation interval`` should be set as the time interval that the workload
can make an amount of accesses for the monitoring purpose, within the interval.
If the interval is too short, only small number of accesses are captured.  As a
result, the monitoring results look everything is samely accessed only rarely.
For many purposes, that would be useless.  If it is too long, however, the time
to converge regions with the :ref:`regions adjustment mechanism
<damon_design_adaptive_regions_adjustment>` can be too long, depending on the
time scale of the given purpose.  This could happen if the workload is actually
making only rare accesses but the user thinks the amount of accesses for the
monitoring purpose too high.  For such cases, the target amount of access to
capture per ``aggregation interval`` should carefully reconsidered.  Also, note
that the captured amount of accesses is represented with not only
``nr_accesses``, but also ``age``.  For example, even if every region on the
monitoring results show zero ``nr_accesses``, regions could still be
distinguished using ``age`` values as the recency information.

Hence the optimum value of ``aggregation interval`` depends on the access
intensiveness of the workload.  The user should tune the interval based on the
amount of access that captured on each aggregated snapshot of the monitoring
results.

Note that the default value of the interval is 100 milliseconds, which is too
short in many cases, especially on large systems.

``Sampling interval`` defines the resolution of each aggregation.  If it is set
too large, monitoring results will look like every region was samely rarely
accessed, or samely frequently accessed.  That is, regions become
undistinguishable based on access pattern, and therefore the results will be
useless in many use cases.  If ``sampling interval`` is too small, it will not
degrade the resolution, but will increase the monitoring overhead.  If it is
appropriate enough to provide a resolution of the monitoring results that
sufficient for the given purpose, it shouldn't be unnecessarily further
lowered.  It is recommended to be set proportional to ``aggregation interval``.
By default, the ratio is set as ``1/20``, and it is still recommended.

Based on the manual tuning guide, DAMON provides more intuitive knob-based
intervals auto tuning mechanism.  Please refer to :ref:`the design document of
the feature <damon_design_monitoring_intervals_autotuning>` for detail.

Refer to below documents for an example tuning based on the above guide.

.. toctree::
   :maxdepth: 1

   monitoring_intervals_tuning_example

모니터링 interval 자동 조정

DAMON은 앞의 조정 지침을 바탕으로 `sampling interval`과 `aggregation interval`을 자동 조정합니다. 사용자는 일정 시간 동안 DAMON이 관찰하기를 원하는 접근 event 양을 지정할 수 있습니다. 목표는 `aggrs`개의 aggregation 동안 측정한 이론적 최대 event 수에 대한 DAMON 관찰 event 수의 비율인 `access_bp`로 표현합니다.

관찰 event는 DAMON의 region 가정에 따라 byte 단위로 계산합니다. 크기가 `X` byte이고 `nr_accesses`가 `Y`인 region은 `X * Y`개의 접근 event를 관찰했다는 뜻입니다. 이론적 최대 event 수도 같은 방식으로 계산하되 `Y` 대신 이론적 최대 `nr_accesses`, 즉 `aggregation interval / sampling interval`을 사용합니다.

메커니즘은 `aggrs`번의 aggregation 동안 접근 event 비율을 계산합니다. 관찰 비율이 목표보다 낮으면 `sampling interval`과 `aggregation interval`을 같은 비율로 늘리고, 목표보다 높으면 같은 비율로 줄입니다. interval 변경 비율은 현재 sample 비율과 목표 비율 사이의 거리에 비례해 정합니다.

사용자는 `min_sample_us`와 `max_sample_us`로 자동 조정 가능한 `sampling interval`의 최솟값과 최댓값을 제한할 수 있습니다. 두 interval은 항상 같은 비율로 바뀌므로 각 조정 뒤 `aggregation interval`의 최솟값과 최댓값도 함께 자동으로 제한됩니다.

자동 조정은 기본으로 꺼져 있으므로 사용자가 명시적으로 켜야 합니다. 경험칙과 Pareto 원칙을 두 번 적용한 권장 목표는 4%입니다. 즉 DAMON이 실제 접근 결과의 64%인 `80% * 80%`를 포착하기 위해 접근 event 원천의 4%인 `20% * 20%`를 관찰한다고 가정합니다.

sysfs에서 이 기능을 쓰는 방법은 `DAMON sysfs interface` 문서의 `intervals_goal` 부분을 참조합니다.

.. _damon_design_monitoring_intervals_autotuning:

Monitoring Intervals Auto-tuning
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

DAMON provides automatic tuning of the ``sampling interval`` and ``aggregation
interval`` based on the :ref:`the tuning guide idea
<damon_design_monitoring_params_tuning_guide>`.  The tuning mechanism allows
users to set the aimed amount of access events to observe via DAMON within
given time interval.  The target can be specified by the user as a ratio of
DAMON-observed access events to the theoretical maximum amount of the events
(``access_bp``) that measured within a given number of aggregations
(``aggrs``).

The DAMON-observed access events are calculated in byte granularity based on
DAMON :ref:`region assumption <damon_design_region_based_sampling>`.  For
example, if a region of size ``X`` bytes of ``Y`` ``nr_accesses`` is found, it
means ``X * Y`` access events are observed by DAMON.  Theoretical maximum
access events for the region is calculated in same way, but replacing ``Y``
with theoretical maximum ``nr_accesses``, which can be calculated as
``aggregation interval / sampling interval``.

The mechanism calculates the ratio of access events for ``aggrs`` aggregations,
and increases or decrease the ``sampleing interval`` and ``aggregation
interval`` in same ratio, if the observed access ratio is lower or higher than
the target, respectively.  The ratio of the intervals change is decided in
proportion to the distance between current samples ratio and the target ratio.

The user can further set the minimum and maximum ``sampling interval`` that can
be set by the tuning mechanism using two parameters (``min_sample_us`` and
``max_sample_us``).  Because the tuning mechanism changes ``sampling interval``
and ``aggregation interval`` in same ratio always, the minimum and maximum
``aggregation interval`` after each of the tuning changes can automatically set
together.

The tuning is turned off by default, and need to be set explicitly by the user.
As a rule of thumbs and the Parreto principle, 4% access samples ratio target
is recommended.  Note that Parreto principle (80/20 rule) has applied twice.
That is, assumes 4% (20% of 20%) DAMON-observed access events ratio (source)
to capture 64% (80% multipled by 80%) real access events (outcomes).

To know how user-space can use this feature via :ref:`DAMON sysfs interface
<sysfs_interface>`, refer to :ref:`intervals_goal <sysfs_scheme>` part of
the documentation.

DAMOS 동작 스킴

데이터 접근 모니터링의 일반적인 목적은 접근 패턴을 인지하는 시스템 효율 최적화입니다. 예를 들면 2분 넘게 접근되지 않은 메모리 region을 page out하거나, 2 MiB보다 크고 1분 넘게 높은 접근 빈도를 보이는 region에 THP를 사용할 수 있습니다.

직관적인 방법은 profile-guided optimization입니다. DAMON으로 workload나 시스템의 접근 결과를 얻고, 결과를 profiling해 특별한 특성의 region을 찾은 뒤 그 region에 대한 시스템 동작을 바꿉니다. 응용 프로그램이나 커널 소프트웨어를 수정하거나 조언을 제공할 수도 있고, 하드웨어를 재구성할 수도 있으며, offline과 online 방식 모두 가능합니다.

그중 runtime에 커널에 조언하는 방식은 유연하고 효과적이어서 널리 쓰이지만 불필요한 중복과 비효율을 만들 수 있습니다. 관심 패턴이 흔한 유형이라면 profiling 자체가 중복되고, 모니터링 결과와 동작 조언을 포함한 정보를 커널 공간과 사용자 공간 사이에서 교환하는 것도 비효율적일 수 있습니다.

DAMON은 이 작업을 offload해 중복과 비효율을 줄이는 Data Access Monitoring-based Operation Schemes, 즉 DAMOS를 제공합니다. 사용자는 원하는 스킴을 높은 수준에서 명세합니다. DAMON은 모니터링을 시작하고 관심 접근 패턴을 가진 region을 찾아 사용자가 정한 `apply_interval`마다 원하는 동작을 적용합니다.

sysfs에서 `apply_interval`을 설정하는 방법은 `DAMON sysfs interface`의 `apply_interval_us` 부분을 참조합니다.

.. _damon_design_damos:

Operation Schemes
-----------------

One common purpose of data access monitoring is access-aware system efficiency
optimizations.  For example,

    paging out memory regions that are not accessed for more than two minutes

or

    using THP for memory regions that are larger than 2 MiB and showing a high
    access frequency for more than one minute.

One straightforward approach for such schemes would be profile-guided
optimizations.  That is, getting data access monitoring results of the
workloads or the system using DAMON, finding memory regions of special
characteristics by profiling the monitoring results, and making system
operation changes for the regions.  The changes could be made by modifying or
providing advice to the software (the application and/or the kernel), or
reconfiguring the hardware.  Both offline and online approaches could be
available.

Among those, providing advice to the kernel at runtime would be flexible and
effective, and therefore widely be used.   However, implementing such schemes
could impose unnecessary redundancy and inefficiency.  The profiling could be
redundant if the type of interest is common.  Exchanging the information
including monitoring results and operation advice between kernel and user
spaces could be inefficient.

To allow users to reduce such redundancy and inefficiencies by offloading the
works, DAMON provides a feature called Data Access Monitoring-based Operation
Schemes (DAMOS).  It lets users specify their desired schemes at a high
level.  For such specifications, DAMON starts monitoring, finds regions having
the access pattern of interest, and applies the user-desired operation actions
to the regions, for every user-specified time interval called
``apply_interval``.

To know how user-space can set ``apply_interval`` via :ref:`DAMON sysfs
interface <sysfs_interface>`, refer to :ref:`apply_interval_us <sysfs_scheme>`
part of the documentation.

동작 action

Action은 사용자가 관심 region에 적용하려는 관리 동작입니다. page out, 다음 reclaim victim 선택에서 우선순위 지정, `khugepaged`에 collapse 또는 split 조언, 아무 동작 없이 region 통계만 수집하는 것 등이 있습니다.

지원 action 목록은 DAMOS가 정의하지만 각 구현은 일반적으로 대상 주소 공간에 의존하므로 DAMON operations set 계층에 있습니다. 특정 가상 주소 범위를 page out하는 코드와 물리 주소 범위를 처리하는 코드는 다르며, 모든 operations set이 모든 action을 지원해야 하는 것도 아닙니다. 따라서 특정 DAMOS action의 사용 가능 여부는 함께 선택한 operations set에 달려 있습니다.

`stat` 이외 action을 region에 적용하면 region 특성이 바뀐 것으로 간주하므로 DAMOS는 해당 region의 `age`를 재설정합니다. sysfs 설정은 `DAMON sysfs interface`의 `action` 부분을 참조합니다.

.. _damon_design_damos_action:

Operation Action
~~~~~~~~~~~~~~~~

The management action that the users desire to apply to the regions of their
interest.  For example, paging out, prioritizing for next reclamation victim
selection, advising ``khugepaged`` to collapse or split, or doing nothing but
collecting statistics of the regions.

The list of supported actions is defined in DAMOS, but the implementation of
each action is in the DAMON operations set layer because the implementation
normally depends on the monitoring target address space.  For example, the code
for paging specific virtual address ranges out would be different from that for
physical address ranges.  And the monitoring operations implementation sets are
not mandated to support all actions of the list.  Hence, the availability of
specific DAMOS action depends on what operations set is selected to be used
together.

The list of the supported actions, their meaning, and DAMON operations sets
that supports each action are as below.

 - ``willneed``: Call ``madvise()`` for the region with ``MADV_WILLNEED``.
   Supported by ``vaddr`` and ``fvaddr`` operations set.
 - ``cold``: Call ``madvise()`` for the region with ``MADV_COLD``.
   Supported by ``vaddr`` and ``fvaddr`` operations set.
 - ``pageout``: Reclaim the region.
   Supported by ``vaddr``, ``fvaddr`` and ``paddr`` operations set.
 - ``hugepage``: Call ``madvise()`` for the region with ``MADV_HUGEPAGE``.
   Supported by ``vaddr`` and ``fvaddr`` operations set.
 - ``nohugepage``: Call ``madvise()`` for the region with ``MADV_NOHUGEPAGE``.
   Supported by ``vaddr`` and ``fvaddr`` operations set.
 - ``lru_prio``: Prioritize the region on its LRU lists.
   Supported by ``paddr`` operations set.
 - ``lru_deprio``: Deprioritize the region on its LRU lists.
   Supported by ``paddr`` operations set.
 - ``migrate_hot``: Migrate the regions prioritizing warmer regions.
   Supported by ``vaddr``, ``fvaddr`` and ``paddr`` operations set.
 - ``migrate_cold``: Migrate the regions prioritizing colder regions.
   Supported by ``vaddr``, ``fvaddr`` and ``paddr`` operations set.
 - ``stat``: Do nothing but count the statistics.
   Supported by all operations sets.

Applying the actions except ``stat`` to a region is considered as changing the
region's characteristics.  Hence, DAMOS resets the age of regions when any such
actions are applied to those.

To know how user-space can set the action via :ref:`DAMON sysfs interface
<sysfs_interface>`, refer to :ref:`action <sysfs_scheme>` part of the
documentation.

대상 접근 패턴과 quota

스킴이 관심을 두는 접근 패턴은 DAMON 결과가 제공하는 region 크기, 접근 빈도, `age` 속성으로 구성됩니다. 사용자는 세 속성 각각의 최솟값과 최댓값을 설정해 관심 패턴을 표현합니다. region의 세 속성이 모두 범위 안에 있으면 DAMOS는 그 region을 스킴의 관심 대상으로 분류합니다. sysfs 설정은 `access_pattern` 부분을 참조합니다.

Quota는 DAMOS 오버헤드의 상한을 제어합니다. 대상 접근 패턴을 적절히 조정하지 않으면 DAMOS가 높은 오버헤드를 낼 수 있습니다. 예를 들어 관심 패턴을 가진 거대한 메모리 region이 발견됐을 때 모든 page에 action을 적용하면 받아들이기 어려울 만큼 많은 시스템 자원을 쓸 수 있습니다. workload의 접근 패턴이 매우 동적이면 패턴 조정만으로 이를 막기도 어렵습니다.

DAMOS quota는 사용자가 정한 기간 안에서 action 적용에 쓸 수 있는 시간의 상한과 action을 적용할 수 있는 메모리 region의 최대 byte 수 가운데 하나 또는 둘 다를 지정하게 합니다. 기본 quota의 sysfs 설정은 `DAMON sysfs interface`의 `quotas` 부분을 참조합니다.

.. _damon_design_damos_access_pattern:

Target Access Pattern
~~~~~~~~~~~~~~~~~~~~~

The access pattern of the schemes' interest.  The patterns are constructed with
the properties that DAMON's monitoring results provide, specifically the size,
the access frequency, and the age.  Users can describe their access pattern of
interest by setting minimum and maximum values of the three properties.  If a
region's three properties are in the ranges, DAMOS classifies it as one of the
regions that the scheme is having an interest in.

To know how user-space can set the access pattern via :ref:`DAMON sysfs
interface <sysfs_interface>`, refer to :ref:`access_pattern
<sysfs_access_pattern>` part of the documentation.


.. _damon_design_damos_quotas:

Quotas
~~~~~~

DAMOS upper-bound overhead control feature.  DAMOS could incur high overhead if
the target access pattern is not properly tuned.  For example, if a huge memory
region having the access pattern of interest is found, applying the scheme's
action to all pages of the huge region could consume unacceptably large system
resources.  Preventing such issues by tuning the access pattern could be
challenging, especially if the access patterns of the workloads are highly
dynamic.

To mitigate that situation, DAMOS provides an upper-bound overhead control
feature called quotas.  It lets users specify an upper limit of time that DAMOS
can use for applying the action, and/or a maximum bytes of memory regions that
the action can be applied within a user-specified time duration.

To know how user-space can set the basic quotas via :ref:`DAMON sysfs interface
<sysfs_interface>`, refer to :ref:`quotas <sysfs_quotas>` part of the
documentation.

Quota 우선순위와 목표 기반 자동 조정

Quota 때문에 모든 관심 region에 action을 적용할 수 없으면 DAMOS는 region 우선순위를 계산하고 quota를 넘지 않는 범위에서 충분히 높은 우선순위의 region에만 action을 적용합니다.

우선순위 메커니즘은 action마다 달라야 합니다. page-out에서는 드물게 접근되는 cold region을 우선하지만 huge page collapse에서는 같은 region의 우선순위를 낮춰야 합니다. 따라서 각 action의 우선순위 구현은 action과 함께 각 DAMON operations set에 들어갑니다.

구현 방식은 operations set에 달려 있지만 일반적으로 region의 접근 패턴 속성으로 우선순위를 계산합니다. 사용자는 특정 사례에 맞춰 `age` 같은 최근성에 `nr_accesses`보다 큰 가중치를 주고 싶을 수 있습니다. DAMOS는 각 접근 패턴 속성의 weight를 지정해 하위 메커니즘에 전달할 수 있게 하지만, 실제로 weight를 어떻게 또는 아예 반영할지는 하위 우선순위 구현에 달려 있습니다. sysfs에서는 `weights` 부분을 참조합니다.

목표 지향 feedback 기반 자동 조정에서는 절대 quota 대신 관심 metric과 원하는 목표값을 지정합니다. DAMOS가 목표를 덜 달성하면 quota를 늘려 공격성을 높이고, 목표를 초과 달성하면 quota를 줄입니다.

목표는 `target_metric`, `target_value`, `current_value`, `nid` 네 매개변수로 지정합니다. 자동 조정은 `target_metric`의 `current_value`를 `target_value`와 같게 만들려고 합니다.

• `user_input`: 사용자가 제공하는 값입니다. 주 workload의 latency나 throughput, free memory 비율, memory pressure stall time인 PSI 등 임의의 관심 metric을 쓸 수 있습니다. 이 경우 사용자가 `current_value`를 반복해서 직접 제공해 feedback해야 합니다.
• `some_mem_psi_us`: quota reset 사이에 측정한 system-wide `some` memory pressure stall 시간을 microsecond로 나타냅니다. DAMOS가 직접 측정하므로 사용자는 처음에 `target_value`만 정하면 되고 DAMOS가 자체 feedback을 수행합니다.
• `node_mem_used_bp`: 특정 NUMA node의 사용 메모리 비율을 bp, 즉 1/10,000 단위로 나타냅니다.
• `node_mem_free_bp`: 특정 NUMA node의 여유 메모리 비율을 bp, 즉 1/10,000 단위로 나타냅니다.

`nid`는 `node_mem_used_bp`와 `node_mem_free_bp`에서 특정 NUMA node를 가리킬 때만 선택적으로 필요합니다. 목표 metric과 목표값 또는 현재값의 sysfs 설정은 `quota goals` 부분을 참조합니다.

.. _damon_design_damos_quotas_prioritization:

Prioritization
^^^^^^^^^^^^^^

A mechanism for making a good decision under the quotas.  When the action
cannot be applied to all regions of interest due to the quotas, DAMOS
prioritizes regions and applies the action to only regions having high enough
priorities so that it will not exceed the quotas.

The prioritization mechanism should be different for each action.  For example,
rarely accessed (colder) memory regions would be prioritized for page-out
scheme action.  In contrast, the colder regions would be deprioritized for huge
page collapse scheme action.  Hence, the prioritization mechanisms for each
action are implemented in each DAMON operations set, together with the actions.

Though the implementation is up to the DAMON operations set, it would be common
to calculate the priority using the access pattern properties of the regions.
Some users would want the mechanisms to be personalized for their specific
case.  For example, some users would want the mechanism to weigh the recency
(``age``) more than the access frequency (``nr_accesses``).  DAMOS allows users
to specify the weight of each access pattern property and passes the
information to the underlying mechanism.  Nevertheless, how and even whether
the weight will be respected are up to the underlying prioritization mechanism
implementation.

To know how user-space can set the prioritization weights via :ref:`DAMON sysfs
interface <sysfs_interface>`, refer to :ref:`weights <sysfs_quotas>` part of
the documentation.


.. _damon_design_damos_quotas_auto_tuning:

Aim-oriented Feedback-driven Auto-tuning
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Automatic feedback-driven quota tuning.  Instead of setting the absolute quota
value, users can specify the metric of their interest, and what target value
they want the metric value to be.  DAMOS then automatically tunes the
aggressiveness (the quota) of the corresponding scheme.  For example, if DAMOS
is under achieving the goal, DAMOS automatically increases the quota.  If DAMOS
is over achieving the goal, it decreases the quota.

The goal can be specified with four parameters, namely ``target_metric``,
``target_value``, ``current_value`` and ``nid``.  The auto-tuning mechanism
tries to make ``current_value`` of ``target_metric`` be same to
``target_value``.

- ``user_input``: User-provided value.  Users could use any metric that they
  has interest in for the value.  Use space main workload's latency or
  throughput, system metrics like free memory ratio or memory pressure stall
  time (PSI) could be examples.  Note that users should explicitly set
  ``current_value`` on their own in this case.  In other words, users should
  repeatedly provide the feedback.
- ``some_mem_psi_us``: System-wide ``some`` memory pressure stall information
  in microseconds that measured from last quota reset to next quota reset.
  DAMOS does the measurement on its own, so only ``target_value`` need to be
  set by users at the initial time.  In other words, DAMOS does self-feedback.
- ``node_mem_used_bp``: Specific NUMA node's used memory ratio in bp (1/10,000).
- ``node_mem_free_bp``: Specific NUMA node's free memory ratio in bp (1/10,000).

``nid`` is optionally required for only ``node_mem_used_bp`` and
``node_mem_free_bp`` to point the specific NUMA node.

To know how user-space can set the tuning goal metric, the target value, and/or
the current value via :ref:`DAMON sysfs interface <sysfs_interface>`, refer to
:ref:`quota goals <sysfs_schemes_quota_goals>` part of the documentation.

Watermark 기반 조건부 활성화

Watermark는 조건에 따라 DAMOS를 자동으로 활성화하거나 비활성화합니다. 예를 들어 충분한 free memory가 보장될 때 proactive reclamation 스킴을 실행하면 시스템 자원만 낭비합니다. 이 낭비를 피하려면 사용자가 free memory 비율 같은 metric을 감시하며 DAMON 또는 DAMOS를 수동으로 켜고 꺼야 합니다.

DAMOS는 이 작업을 세 watermark로 offload합니다. 사용자는 관심 metric과 `high`, `middle`, `low` 값을 정합니다. metric이 high보다 높거나 low보다 낮아지면 스킴을 비활성화합니다. metric이 middle보다 낮고 low보다 높으면 활성화합니다.

모든 스킴이 watermark로 비활성화되면 모니터링도 비활성화됩니다. 이 상태에서 DAMON worker thread는 주기적으로 watermark만 확인하므로 오버헤드가 거의 0입니다. sysfs 설정은 `watermarks` 부분을 참조합니다.

.. _damon_design_damos_watermarks:

Watermarks
~~~~~~~~~~

Conditional DAMOS (de)activation automation.  Users might want DAMOS to run
only under certain situations.  For example, when a sufficient amount of free
memory is guaranteed, running a scheme for proactive reclamation would only
consume unnecessary system resources.  To avoid such consumption, the user would
need to manually monitor some metrics such as free memory ratio, and turn
DAMON/DAMOS on or off.

DAMOS allows users to offload such works using three watermarks.  It allows the
users to configure the metric of their interest, and three watermark values,
namely high, middle, and low.  If the value of the metric becomes above the
high watermark or below the low watermark, the scheme is deactivated.  If the
metric becomes below the mid watermark but above the low watermark, the scheme
is activated.  If all schemes are deactivated by the watermarks, the monitoring
is also deactivated.  In this case, the DAMON worker thread only periodically
checks the watermarks and therefore incurs nearly zero overhead.

To know how user-space can set the watermarks via :ref:`DAMON sysfs interface
<sysfs_interface>`, refer to :ref:`watermarks <sysfs_watermarks>` part of the
documentation.

DAMOS filter

DAMOS filter는 접근 패턴 이외의 조건으로 대상 메모리 region을 거릅니다. 사용자가 자체 프로그램이나 좋은 profiling 도구를 갖고 있다면 미래 접근 패턴이나 특정 메모리 유형의 특별 요구처럼 커널보다 많은 정보를 알 수 있습니다. 예를 들어 anonymous page만 프로그램 성능에 영향을 준다는 사실이나 latency-critical 프로세스 목록을 알고 있을 수 있습니다.

각 스킴에는 임의 개수의 filter를 둘 수 있습니다. 각 filter는 메모리 유형 `type`, 그 유형 자체인지 그 유형을 제외한 나머지인지 나타내는 `matching`, 해당 메모리에 action 적용을 허용할지 포함하거나 거부할지 나타내는 `allow`를 지정합니다.

효율을 위해 일부 filter 유형은 core 계층이, 나머지는 operations set이 처리합니다. 후자의 지원 여부는 DAMON operations set에 달려 있습니다. core 처리 filter가 제외한 메모리 region은 스킴이 적용을 시도한 것으로 집계되지 않지만 operations set 처리 filter에서 제외된 region은 시도한 것으로 집계되며, 이 차이는 통계에 반영됩니다.

여러 filter가 설치되면 core 처리 그룹을 먼저, operations 계층 처리 그룹을 다음에 평가합니다. 각 그룹 안에서는 설치 순서를 따릅니다. 메모리 일부가 filter 하나와 일치하면 뒤 filter는 무시합니다. 어느 filter와도 일치하지 않아 평가 단계를 통과했다면 마지막 filter의 허용 유형과 반대로 처리합니다. 마지막 filter가 allow라면 일치하지 않은 메모리를 거부하고, 마지막이 reject라면 허용합니다.

예를 들어 1) anonymous page 허용 filter와 2) young page 거부 filter가 이 순서로 설치됐다고 합시다. 대상 page가 anonymous이면 첫 allow filter와 일치하므로 young 여부와 무관하게 action을 적용합니다. anonymous가 아니고 young이면 두 번째 reject filter가 막습니다. 둘 다 아니면 일치하는 filter 없이 통과하고, 마지막 filter가 reject였으므로 action을 적용합니다.

사용자 공간에서 filter를 설정하는 방법은 `DAMON sysfs interface`의 `filters` 부분을 참조합니다.

.. _damon_design_damos_filters:

Filters
~~~~~~~

Non-access pattern-based target memory regions filtering.  If users run
self-written programs or have good profiling tools, they could know something
more than the kernel, such as future access patterns or some special
requirements for specific types of memory. For example, some users may know
only anonymous pages can impact their program's performance.  They can also
have a list of latency-critical processes.

To let users optimize DAMOS schemes with such special knowledge, DAMOS provides
a feature called DAMOS filters.  The feature allows users to set an arbitrary
number of filters for each scheme.  Each filter specifies

- a type of memory (``type``),
- whether it is for the memory of the type or all except the type
  (``matching``), and
- whether it is to allow (include) or reject (exclude) applying
  the scheme's action to the memory (``allow``).

For efficient handling of filters, some types of filters are handled by the
core layer, while others are handled by operations set.  In the latter case,
hence, support of the filter types depends on the DAMON operations set.  In
case of the core layer-handled filters, the memory regions that excluded by the
filter are not counted as the scheme has tried to the region.  In contrast, if
a memory regions is filtered by an operations set layer-handled filter, it is
counted as the scheme has tried.  This difference affects the statistics.

When multiple filters are installed, the group of filters that handled by the
core layer are evaluated first.  After that, the group of filters that handled
by the operations layer are evaluated.  Filters in each of the groups are
evaluated in the installed order.  If a part of memory is matched to one of the
filter, next filters are ignored.  If the part passes through the filters
evaluation stage because it is not matched to any of the filters, applying the
scheme's action to it depends on the last filter's allowance type.  If the last
filter was for allowing, the part of memory will be rejected, and vice versa.

For example, let's assume 1) a filter for allowing anonymous pages and 2)
another filter for rejecting young pages are installed in the order.  If a page
of a region that eligible to apply the scheme's action is an anonymous page,
the scheme's action will be applied to the page regardless of whether it is
young or not, since it matches with the first allow-filter.  If the page is
not anonymous but young, the scheme's action will not be applied, since the
second reject-filter blocks it.  If the page is neither anonymous nor young,
the page will pass through the filters evaluation stage since there is no
matching filter, and the action will be applied to the page.

Below ``type`` of filters are currently supported.

- Core layer handled
    - addr
        - Applied to pages that belonging to a given address range.
    - target
        - Applied to pages that belonging to a given DAMON monitoring target.
- Operations layer handled, supported by only ``paddr`` operations set.
    - anon
        - Applied to pages that containing data that not stored in files.
    - active
        - Applied to active pages.
    - memcg
        - Applied to pages that belonging to a given cgroup.
    - young
        - Applied to pages that are accessed after the last access check from the
          scheme.
    - hugepage_size
        - Applied to pages that managed in a given size range.
    - unmapped
        - Applied to pages that unmapped.

To know how user-space can set the filters via :ref:`DAMON sysfs interface
<sysfs_interface>`, refer to :ref:`filters <sysfs_filters>` part of the
documentation.

DAMOS 통계와 region walking

DAMOS는 동작 감시, 조정, debugging을 돕기 위해 각 스킴의 실행 시작 시점부터 다음 통계를 누적합니다.

"region에 스킴 적용을 시도했다"는 말은 DAMOS core가 그 region을 action 적용 가능 대상으로 판정했다는 뜻입니다. core에서 처리되는 `access pattern`, `quotas`, `watermarks`, `filters`가 이 판정에 영향을 줍니다. core는 하위 operations set에 action 적용을 요청할 뿐 실제 적용 여부는 알 수 없으므로 이를 `tried`라고 부릅니다.

"region에 스킴이 적용됐다"는 말은 operations set이 region의 적어도 일부에 action을 적용했다는 뜻입니다. operations set이 처리하는 filter, action 유형, region의 page 상태가 결과에 영향을 줍니다. anonymous page 제외 filter가 있는데 region이 anonymous page로만 구성됐거나, action이 `pageout`인데 모든 page가 reclaim 불가능하면 적용은 실패합니다.

사용자 공간에서 통계를 읽는 방법은 `DAMON sysfs interface`의 `stats` 부분을 참조합니다.

Regions Walking은 DAMOS action이 방금 적용된 각 region에 사용자가 접근하게 하는 기능입니다. DAMON API로 접근 모니터링 결과와 DAMOS filter를 통과한 region 내부 메모리 양을 포함한 region의 모든 속성을 읽을 수 있습니다. DAMON sysfs interface도 `schemes_tried_regions`의 특수 파일로 이 데이터를 제공합니다.

.. _damon_design_damos_stat:

Statistics
~~~~~~~~~~

The statistics of DAMOS behaviors that designed to help monitoring, tuning and
debugging of DAMOS.

DAMOS accounts below statistics for each scheme, from the beginning of the
scheme's execution.

- ``nr_tried``: Total number of regions that the scheme is tried to be applied.
- ``sz_tried``: Total size of regions that the scheme is tried to be applied.
- ``sz_ops_filter_passed``: Total bytes that passed operations set
  layer-handled DAMOS filters.
- ``nr_applied``: Total number of regions that the scheme is applied.
- ``sz_applied``: Total size of regions that the scheme is applied.
- ``qt_exceeds``: Total number of times the quota of the scheme has exceeded.

"A scheme is tried to be applied to a region" means DAMOS core logic determined
the region is eligible to apply the scheme's :ref:`action
<damon_design_damos_action>`.  The :ref:`access pattern
<damon_design_damos_access_pattern>`, :ref:`quotas
<damon_design_damos_quotas>`, :ref:`watermarks
<damon_design_damos_watermarks>`, and :ref:`filters
<damon_design_damos_filters>` that handled on core logic could affect this.
The core logic will only ask the underlying :ref:`operation set
<damon_operations_set>` to do apply the action to the region, so whether the
action is really applied or not is unclear.  That's why it is called "tried".

"A scheme is applied to a region" means the :ref:`operation set
<damon_operations_set>` has applied the action to at least a part of the
region.  The :ref:`filters <damon_design_damos_filters>` that handled by the
operation set, and the types of the :ref:`action <damon_design_damos_action>`
and the pages of the region can affect this.  For example, if a filter is set
to exclude anonymous pages and the region has only anonymous pages, or if the
action is ``pageout`` while all pages of the region are unreclaimable, applying
the action to the region will fail.

To know how user-space can read the stats via :ref:`DAMON sysfs interface
<sysfs_interface>`, refer to :ref:s`stats <sysfs_stats>` part of the
documentation.

Regions Walking
~~~~~~~~~~~~~~~

DAMOS feature allowing users access each region that a DAMOS action has just
applied.  Using this feature, DAMON :ref:`API <damon_design_api>` allows users
access full properties of the regions including the access monitoring results
and amount of the region's internal memory that passed the DAMOS filters.
:ref:`DAMON sysfs interface <sysfs_interface>` also allows users read the data
via special :ref:`files <sysfs_schemes_tried_regions>`.

Kernel API와 사용자 인터페이스 모듈

DAMON의 programming interface는 커널 공간에서 데이터 접근을 인지하는 응용을 만들기 위한 것입니다. DAMON은 framework이므로 자체적으로 아무 동작도 하지 않습니다. 대신 다른 커널 subsystem과 module이 DAMON core 기능을 사용해 데이터 접근 인지 응용을 만들도록 돕습니다. 모든 기능은 `include/linux/damon.h`의 API로 노출되며 자세한 내용은 `/mm/damon/api` 문서를 참조합니다.

DAMON core는 커널 component용 framework이므로 사용자 공간에 직접 interface를 제공하지 않습니다. 각 DAMON API 사용자 커널 component가 이를 구현해야 합니다. DAMON 서브시스템은 범용 제어와 특수 목적의 접근 인지 시스템 동작을 위한 API 사용자 module을 자체 제공하고, 사용자 공간에 안정적인 ABI를 제공합니다.

범용 사용자 interface module은 runtime의 일반적인 DAMON 사용을 위한 ABI를 제공합니다. 다른 ABI처럼 `sysfs` 같은 pseudo file system에 파일을 만들고, 사용자가 파일을 읽고 쓰며 요청과 결과를 주고받게 합니다. 이 I/O에 응답해 module은 DAMON API로 DAMON을 제어하고 요청한 결과를 가져와 사용자 공간에 돌려줍니다.

ABI는 사람이 손으로 직접 조작하기보다 사용자 공간 응용 개발을 위해 설계되었습니다. 사람 사용자는 전용 도구를 쓰는 것이 권장됩니다. Python으로 작성된 `damo`는 GitHub `https://github.com/damonitor/damo`, PyPI 통계 `https://pypistats.org/packages/damo`, Fedora package `https://packages.fedoraproject.org/pkgs/python-damo/damo/`에서 구할 수 있습니다. 현재 이 유형으로 `DAMON sysfs interface` module 하나가 제공되며 자세한 ABI는 `sysfs_interface` 문서를 참조합니다.

특수 목적 접근 인지 커널 module은 특정 DAMON 사용 목적의 사용자 공간 ABI를 제공합니다. 범용 interface는 runtime에서 모든 기능을 제어하지만 proactive reclamation이나 LRU list balancing 같은 시스템 전역의 특수 동작에서는 불필요한 knob를 없애 interface를 단순화하고 boot-time 또는 compile-time 제어를 추가할 수 있습니다. DAMON 제어 매개변수 기본값도 목적에 맞게 최적화할 필요가 있습니다.

이런 사례를 위해 더 단순하고 최적화된 사용자 공간 interface를 제공하는 DAMON API 사용자 커널 module이 있습니다. 현재 proactive reclamation과 LRU list 조작을 위한 두 module을 제공하며 자세한 내용은 `/admin-guide/mm/damon/reclaim`과 `/admin-guide/mm/damon/lru_sort` 사용 문서를 참조합니다.

.. _damon_design_api:

Application Programming Interface
---------------------------------

The programming interface for kernel space data access-aware applications.
DAMON is a framework, so it does nothing by itself.  Instead, it only helps
other kernel components such as subsystems and modules building their data
access-aware applications using DAMON's core features.  For this, DAMON exposes
its all features to other kernel components via its application programming
interface, namely ``include/linux/damon.h``.  Please refer to the API
:doc:`document </mm/damon/api>` for details of the interface.


.. _damon_modules:

Modules
=======

Because the core of DAMON is a framework for kernel components, it doesn't
provide any direct interface for the user space.  Such interfaces should be
implemented by each DAMON API user kernel components, instead.  DAMON subsystem
itself implements such DAMON API user modules, which are supposed to be used
for general purpose DAMON control and special purpose data access-aware system
operations, and provides stable application binary interfaces (ABI) for the
user space.  The user space can build their efficient data access-aware
applications using the interfaces.


General Purpose User Interface Modules
--------------------------------------

DAMON modules that provide user space ABIs for general purpose DAMON usage in
runtime.

Like many other ABIs, the modules create files on pseudo file systems like
'sysfs', allow users to specify their requests to and get the answers from
DAMON by writing to and reading from the files.  As a response to such I/O,
DAMON user interface modules control DAMON and retrieve the results as user
requested via the DAMON API, and return the results to the user-space.

The ABIs are designed to be used for user space applications development,
rather than human beings' fingers.  Human users are recommended to use such
user space tools.  One such Python-written user space tool is available at
Github (https://github.com/damonitor/damo), Pypi
(https://pypistats.org/packages/damo), and Fedora
(https://packages.fedoraproject.org/pkgs/python-damo/damo/).

Currently, one module for this type, namely 'DAMON sysfs interface' is
available.  Please refer to the ABI :ref:`doc <sysfs_interface>` for details of
the interfaces.


Special-Purpose Access-aware Kernel Modules
-------------------------------------------

DAMON modules that provide user space ABI for specific purpose DAMON usage.

DAMON user interface modules are for full control of all DAMON features in
runtime.  For each special-purpose system-wide data access-aware system
operations such as proactive reclamation or LRU lists balancing, the interfaces
could be simplified by removing unnecessary knobs for the specific purpose, and
extended for boot-time and even compile time control.  Default values of DAMON
control parameters for the usage would also need to be optimized for the
purpose.

To support such cases, yet more DAMON API user kernel modules that provide more
simple and optimized user space interfaces are available.  Currently, two
modules for proactive reclamation and LRU lists manipulation are provided.  For
more detail, please read the usage documents for those
(:doc:`/admin-guide/mm/damon/reclaim` and
:doc:`/admin-guide/mm/damon/lru_sort`).