요약·해설과 원문, 전문 번역을 서로 분리했습니다. API 이름, symbol, source path는 원문 표기를 사용합니다.
1. 요약·해설
원문의 핵심 논리와 kernel programming 관점의 보충 설명입니다. 아래의 전문 번역과는 별도로 작성했습니다.
2. 영어 원문 전체
번역 기준이 된 Linux v6.18.37 원문입니다. 줄 번호는 이 버전의 파일 좌표입니다.
원문 전체 펼치기
.. SPDX-License-Identifier: GPL-2.0+
==========
Maple Tree
==========
:Author: Liam R. Howlett
Overview
========
The Maple Tree is a B-Tree data type which is optimized for storing
non-overlapping ranges, including ranges of size 1. The tree was designed to
be simple to use and does not require a user written search method. It
supports iterating over a range of entries and going to the previous or next
entry in a cache-efficient manner. The tree can also be put into an RCU-safe
mode of operation which allows reading and writing concurrently. Writers must
synchronize on a lock, which can be the default spinlock, or the user can set
the lock to an external lock of a different type.
The Maple Tree maintains a small memory footprint and was designed to use
modern processor cache efficiently. The majority of the users will be able to
use the normal API. An :ref:`maple-tree-advanced-api` exists for more complex
scenarios. The most important usage of the Maple Tree is the tracking of the
virtual memory areas.
The Maple Tree can store values between ``0`` and ``ULONG_MAX``. The Maple
Tree reserves values with the bottom two bits set to '10' which are below 4096
(ie 2, 6, 10 .. 4094) for internal use. If the entries may use reserved
entries then the users can convert the entries using xa_mk_value() and convert
them back by calling xa_to_value(). If the user needs to use a reserved
value, then the user can convert the value when using the
:ref:`maple-tree-advanced-api`, but are blocked by the normal API.
The Maple Tree can also be configured to support searching for a gap of a given
size (or larger).
Pre-allocating of nodes is also supported using the
:ref:`maple-tree-advanced-api`. This is useful for users who must guarantee a
successful store operation within a given
code segment when allocating cannot be done. Allocations of nodes are
relatively small at around 256 bytes.
.. _maple-tree-normal-api:
Normal API
==========
Start by initialising a maple tree, either with DEFINE_MTREE() for statically
allocated maple trees or mt_init() for dynamically allocated ones. A
freshly-initialised maple tree contains a ``NULL`` pointer for the range ``0``
- ``ULONG_MAX``. There are currently two types of maple trees supported: the
allocation tree and the regular tree. The regular tree has a higher branching
factor for internal nodes. The allocation tree has a lower branching factor
but allows the user to search for a gap of a given size or larger from either
``0`` upwards or ``ULONG_MAX`` down. An allocation tree can be used by
passing in the ``MT_FLAGS_ALLOC_RANGE`` flag when initialising the tree.
You can then set entries using mtree_store() or mtree_store_range().
mtree_store() will overwrite any entry with the new entry and return 0 on
success or an error code otherwise. mtree_store_range() works in the same way
but takes a range. mtree_load() is used to retrieve the entry stored at a
given index. You can use mtree_erase() to erase an entire range by only
knowing one value within that range, or mtree_store() call with an entry of
NULL may be used to partially erase a range or many ranges at once.
If you want to only store a new entry to a range (or index) if that range is
currently ``NULL``, you can use mtree_insert_range() or mtree_insert() which
return -EEXIST if the range is not empty.
You can search for an entry from an index upwards by using mt_find().
You can walk each entry within a range by calling mt_for_each(). You must
provide a temporary variable to store a cursor. If you want to walk each
element of the tree then ``0`` and ``ULONG_MAX`` may be used as the range. If
the caller is going to hold the lock for the duration of the walk then it is
worth looking at the mas_for_each() API in the :ref:`maple-tree-advanced-api`
section.
Sometimes it is necessary to ensure the next call to store to a maple tree does
not allocate memory, please see :ref:`maple-tree-advanced-api` for this use case.
You can use mtree_dup() to duplicate an entire maple tree. It is a more
efficient way than inserting all elements one by one into a new tree.
Finally, you can remove all entries from a maple tree by calling
mtree_destroy(). If the maple tree entries are pointers, you may wish to free
the entries first.
Allocating Nodes
----------------
The allocations are handled by the internal tree code. See
:ref:`maple-tree-advanced-alloc` for other options.
Locking
-------
You do not have to worry about locking. See :ref:`maple-tree-advanced-locks`
for other options.
The Maple Tree uses RCU and an internal spinlock to synchronise access:
Takes RCU read lock:
* mtree_load()
* mt_find()
* mt_for_each()
* mt_next()
* mt_prev()
Takes ma_lock internally:
* mtree_store()
* mtree_store_range()
* mtree_insert()
* mtree_insert_range()
* mtree_erase()
* mtree_dup()
* mtree_destroy()
* mt_set_in_rcu()
* mt_clear_in_rcu()
If you want to take advantage of the internal lock to protect the data
structures that you are storing in the Maple Tree, you can call mtree_lock()
before calling mtree_load(), then take a reference count on the object you
have found before calling mtree_unlock(). This will prevent stores from
removing the object from the tree between looking up the object and
incrementing the refcount. You can also use RCU to avoid dereferencing
freed memory, but an explanation of that is beyond the scope of this
document.
.. _maple-tree-advanced-api:
Advanced API
============
The advanced API offers more flexibility and better performance at the
cost of an interface which can be harder to use and has fewer safeguards.
You must take care of your own locking while using the advanced API.
You can use the ma_lock, RCU or an external lock for protection.
You can mix advanced and normal operations on the same array, as long
as the locking is compatible. The :ref:`maple-tree-normal-api` is implemented
in terms of the advanced API.
The advanced API is based around the ma_state, this is where the 'mas'
prefix originates. The ma_state struct keeps track of tree operations to make
life easier for both internal and external tree users.
Initialising the maple tree is the same as in the :ref:`maple-tree-normal-api`.
Please see above.
The maple state keeps track of the range start and end in mas->index and
mas->last, respectively.
mas_walk() will walk the tree to the location of mas->index and set the
mas->index and mas->last according to the range for the entry.
You can set entries using mas_store(). mas_store() will overwrite any entry
with the new entry and return the first existing entry that is overwritten.
The range is passed in as members of the maple state: index and last.
You can use mas_erase() to erase an entire range by setting index and
last of the maple state to the desired range to erase. This will erase
the first range that is found in that range, set the maple state index
and last as the range that was erased and return the entry that existed
at that location.
You can walk each entry within a range by using mas_for_each(). If you want
to walk each element of the tree then ``0`` and ``ULONG_MAX`` may be used as
the range. If the lock needs to be periodically dropped, see the locking
section mas_pause().
Using a maple state allows mas_next() and mas_prev() to function as if the
tree was a linked list. With such a high branching factor the amortized
performance penalty is outweighed by cache optimization. mas_next() will
return the next entry which occurs after the entry at index. mas_prev()
will return the previous entry which occurs before the entry at index.
mas_find() will find the first entry which exists at or above index on
the first call, and the next entry from every subsequent calls.
mas_find_rev() will find the first entry which exists at or below the last on
the first call, and the previous entry from every subsequent calls.
If the user needs to yield the lock during an operation, then the maple state
must be paused using mas_pause().
There are a few extra interfaces provided when using an allocation tree.
If you wish to search for a gap within a range, then mas_empty_area()
or mas_empty_area_rev() can be used. mas_empty_area() searches for a gap
starting at the lowest index given up to the maximum of the range.
mas_empty_area_rev() searches for a gap starting at the highest index given
and continues downward to the lower bound of the range.
.. _maple-tree-advanced-alloc:
Advanced Allocating Nodes
-------------------------
Allocations are usually handled internally to the tree, however if allocations
need to occur before a write occurs then calling mas_expected_entries() will
allocate the worst-case number of needed nodes to insert the provided number of
ranges. This also causes the tree to enter mass insertion mode. Once
insertions are complete calling mas_destroy() on the maple state will free the
unused allocations.
.. _maple-tree-advanced-locks:
Advanced Locking
----------------
The maple tree uses a spinlock by default, but external locks can be used for
tree updates as well. To use an external lock, the tree must be initialized
with the ``MT_FLAGS_LOCK_EXTERN flag``, this is usually done with the
MTREE_INIT_EXT() #define, which takes an external lock as an argument.
Functions and structures
========================
.. kernel-doc:: include/linux/maple_tree.h
.. kernel-doc:: lib/maple_tree.c
3. 한국어 전문 번역
영어 원문의 문단 순서와 의미를 유지한 전체 번역입니다. 코드, 함수명, symbol과 URL은 원문 표기를 유지합니다.
Maple Tree 개요
1-44SPDX license 식별자는 GPL-2.0+입니다.
Maple Tree
저자: Liam R. Howlett
개요 (Overview)
Maple Tree는 크기가 1인 range를 포함한 서로 겹치지 않는 range를 저장하도록 최적화한 B-Tree data type입니다. 사용하기 단순하도록 설계되어 사용자가 search method를 직접 작성할 필요가 없습니다. Cache 효율적인 방식으로 entry range를 순회하고 이전 또는 다음 entry로 이동할 수 있습니다. RCU-safe operation mode로 설정하면 read와 write를 동시에 수행할 수도 있습니다. Writer는 lock으로 동기화해야 하며, 기본 spinlock을 사용하거나 사용자가 다른 type의 external lock을 지정할 수 있습니다.
Maple Tree는 작은 memory footprint를 유지하며 현대 processor cache를 효율적으로 사용하도록 설계되었습니다. 대부분의 사용자는 normal API를 사용할 수 있고, 더 복잡한 상황을 위한 `maple-tree-advanced-api`도 있습니다. Maple Tree의 가장 중요한 용도는 virtual memory area를 추적하는 것입니다.
Maple Tree는 `0`부터 `ULONG_MAX`까지의 값을 저장할 수 있습니다. 다만 4096보다 작고 하위 두 bit가 `10`인 값, 즉 2, 6, 10부터 4094까지는 내부 용도로 예약합니다. Entry가 예약 값을 사용할 수 있다면 `xa_mk_value()`로 변환한 뒤 `xa_to_value()`로 되돌릴 수 있습니다. 예약 값을 써야 하는 사용자는 advanced API에서 값을 변환할 수 있지만 normal API에서는 차단됩니다.
Maple Tree는 지정한 크기 이상의 gap을 검색하도록 구성할 수도 있습니다.
Advanced API를 사용하면 node pre-allocation도 지원합니다. Allocation을 수행할 수 없는 특정 code segment 안에서 store operation의 성공을 보장해야 하는 사용자에게 유용합니다. Node allocation 크기는 약 256 byte로 비교적 작습니다.
Normal API
45-90Normal API anchor는 `maple-tree-normal-api`입니다.
정적으로 할당한 Maple Tree는 `DEFINE_MTREE()`로, 동적으로 할당한 tree는 `mt_init()`으로 초기화합니다. 새로 초기화한 Maple Tree는 `0`부터 `ULONG_MAX` range에 `NULL` pointer를 담습니다. 현재 allocation tree와 regular tree라는 두 type을 지원합니다. Regular tree는 internal node의 branching factor가 더 높습니다. Allocation tree는 branching factor가 더 낮지만 `0`부터 위쪽으로 또는 `ULONG_MAX`부터 아래쪽으로 지정 크기 이상의 gap을 검색할 수 있습니다. 초기화할 때 `MT_FLAGS_ALLOC_RANGE` flag를 전달하면 allocation tree를 사용할 수 있습니다.
`mtree_store()` 또는 `mtree_store_range()`로 entry를 설정합니다. `mtree_store()`는 기존 entry를 새 entry로 덮어쓰며 성공하면 0, 실패하면 error code를 반환합니다. `mtree_store_range()`도 같은 방식으로 동작하지만 range를 받습니다. `mtree_load()`는 지정 index에 저장한 entry를 가져옵니다. `mtree_erase()`는 range 안의 값 하나만 알고 있어도 range 전체를 지울 수 있습니다. 또는 `NULL` entry를 전달한 `mtree_store()` 호출로 range 일부나 여러 range를 한 번에 지울 수 있습니다.
현재 `NULL`인 range 또는 index에만 새 entry를 저장하려면 `mtree_insert_range()` 또는 `mtree_insert()`를 사용합니다. Range가 비어 있지 않으면 `-EEXIST`를 반환합니다.
`mt_find()`를 사용하면 지정 index부터 위쪽으로 entry를 검색할 수 있습니다.
`mt_for_each()`를 호출하면 range 안의 각 entry를 순회할 수 있습니다. Cursor를 저장할 임시 변수를 제공해야 합니다. Tree의 모든 element를 순회하려면 range로 `0`과 `ULONG_MAX`를 사용합니다. Caller가 순회하는 동안 lock을 계속 보유한다면 advanced API의 `mas_for_each()`를 살펴볼 가치가 있습니다.
다음 Maple Tree store 호출에서 memory allocation이 일어나지 않도록 보장해야 할 때가 있습니다. 이 사용 사례는 advanced API를 참고하십시오.
`mtree_dup()`는 Maple Tree 전체를 복제합니다. 새 tree에 element를 하나씩 insert하는 것보다 효율적입니다.
마지막으로 `mtree_destroy()`를 호출하면 Maple Tree의 모든 entry를 제거할 수 있습니다. Entry가 pointer라면 먼저 entry가 가리키는 object를 해제해야 할 수 있습니다.
Normal API의 node allocation
91-96Node 할당 (Allocating Nodes)
Allocation은 internal tree code가 처리합니다. 다른 선택지는 `maple-tree-advanced-alloc`을 참고하십시오.
Normal API locking
97-131Locking
Normal API에서는 사용자가 locking을 직접 걱정할 필요가 없습니다. 다른 선택지는 `maple-tree-advanced-locks`를 참고하십시오.
Maple Tree는 access 동기화에 RCU와 internal spinlock을 사용합니다.
다음 operation은 RCU read lock을 획득합니다.
- `mtree_load()`
- `mt_find()`
- `mt_for_each()`
- `mt_next()`
- `mt_prev()`
다음 operation은 내부에서 `ma_lock`을 획득합니다.
- `mtree_store()`
- `mtree_store_range()`
- `mtree_insert()`
- `mtree_insert_range()`
- `mtree_erase()`
- `mtree_dup()`
- `mtree_destroy()`
- `mt_set_in_rcu()`
- `mt_clear_in_rcu()`
Maple Tree에 저장한 data structure를 internal lock으로 보호하려면 `mtree_load()`를 호출하기 전에 `mtree_lock()`을 호출하고, 찾은 object의 reference count를 증가시킨 뒤 `mtree_unlock()`을 호출할 수 있습니다. 그러면 object를 찾은 시점과 refcount를 증가시키는 시점 사이에 store가 tree에서 object를 제거하지 못합니다. 해제된 memory를 dereference하지 않도록 RCU를 사용할 수도 있지만 자세한 설명은 이 문서의 범위를 벗어납니다.
Advanced API 개요
132-151Advanced API anchor는 `maple-tree-advanced-api`입니다.
Advanced API는 더 많은 유연성과 더 나은 성능을 제공하지만 interface가 더 어렵고 safeguard가 적습니다. Advanced API를 사용할 때는 사용자가 직접 locking을 처리해야 합니다. 보호 수단으로 `ma_lock`, RCU 또는 external lock을 사용할 수 있습니다. Locking이 호환된다면 같은 tree에서 advanced operation과 normal operation을 섞어 사용할 수 있습니다. Normal API는 advanced API를 기반으로 구현됩니다.
Advanced API는 `ma_state`를 중심으로 구성되며 `mas` prefix도 여기에서 나옵니다. `ma_state` structure는 tree operation의 상태를 추적하여 internal 사용자와 external 사용자 모두가 쉽게 작업할 수 있게 합니다.
Maple Tree 초기화는 normal API와 같으므로 앞의 설명을 참고하십시오.
Advanced API operation
152-187Maple state는 range 시작과 끝을 각각 `mas->index`와 `mas->last`에 추적합니다.
`mas_walk()`은 tree를 `mas->index` 위치까지 탐색하고 해당 entry의 range에 맞춰 `mas->index`와 `mas->last`를 설정합니다.
`mas_store()`로 entry를 설정할 수 있습니다. 기존 entry를 새 entry로 덮어쓰고, 덮어쓴 첫 번째 기존 entry를 반환합니다. Range는 maple state의 `index`와 `last` member로 전달합니다.
`mas_erase()`는 maple state의 `index`와 `last`를 지울 range로 설정하여 range 전체를 지웁니다. 지정 range 안에서 처음 발견한 range를 지우고, 지운 range에 맞춰 maple state의 `index`와 `last`를 설정한 뒤 그 위치에 있던 entry를 반환합니다.
`mas_for_each()`로 range 안의 각 entry를 순회할 수 있습니다. Tree의 모든 element를 순회하려면 range로 `0`과 `ULONG_MAX`를 사용합니다. Lock을 주기적으로 놓아야 한다면 locking section의 `mas_pause()`를 참고하십시오.
Maple state를 사용하면 `mas_next()`와 `mas_prev()`가 tree를 linked list처럼 다룰 수 있습니다. Branching factor가 매우 높으므로 cache 최적화의 이점이 amortized performance penalty보다 큽니다. `mas_next()`는 현재 index의 entry 뒤에 나타나는 다음 entry를 반환하고, `mas_prev()`는 현재 index의 entry 앞에 나타나는 이전 entry를 반환합니다.
`mas_find()`는 첫 호출에서 index 이상에 존재하는 첫 entry를 찾고 이후 호출마다 다음 entry를 찾습니다.
`mas_find_rev()`는 첫 호출에서 `last` 이하에 존재하는 첫 entry를 찾고 이후 호출마다 이전 entry를 찾습니다.
Operation 도중 사용자가 lock을 양보해야 한다면 `mas_pause()`로 maple state를 pause해야 합니다.
Allocation tree의 gap 검색
188-194Allocation tree를 사용할 때는 몇 가지 추가 interface가 제공됩니다. Range 안에서 gap을 찾으려면 `mas_empty_area()` 또는 `mas_empty_area_rev()`를 사용합니다. `mas_empty_area()`는 지정한 가장 낮은 index부터 range의 최대값까지 위쪽으로 gap을 검색합니다. `mas_empty_area_rev()`는 지정한 가장 높은 index부터 아래쪽 경계까지 아래로 gap을 검색합니다.
Advanced node allocation
195-206Advanced allocation anchor는 `maple-tree-advanced-alloc`입니다.
Advanced node 할당 (Advanced Allocating Nodes)
보통 tree가 allocation을 내부에서 처리합니다. 그러나 write 전에 allocation을 끝내야 한다면 `mas_expected_entries()`를 호출하여 지정한 수의 range를 insert하는 데 필요한 최악의 경우 node 수를 미리 할당합니다. 이 호출은 tree를 mass insertion mode로 전환하기도 합니다. Insert가 끝난 뒤 maple state에 `mas_destroy()`를 호출하면 사용하지 않은 allocation을 해제합니다.
Advanced locking과 API 문서
207-221Advanced locking anchor는 `maple-tree-advanced-locks`입니다.
Advanced Locking
Maple Tree는 기본적으로 spinlock을 사용하지만 tree update에 external lock을 사용할 수도 있습니다. External lock을 사용하려면 `MT_FLAGS_LOCK_EXTERN` flag로 tree를 초기화해야 합니다. 일반적으로 external lock을 argument로 받는 `MTREE_INIT_EXT()` macro로 초기화합니다.
Function과 structure (Functions and structures)
다음 kernel-doc directive는 public Maple Tree header와 implementation의 function 및 structure 문서를 포함합니다.
.. kernel-doc:: include/linux/maple_tree.h
.. kernel-doc:: lib/maple_tree.c
요약과 해설
maple_tree.rst:1-221Maple Tree는 virtual memory area처럼 겹치지 않는 range를 저장하는 B-Tree입니다. Regular tree는 높은 branching factor로 cache 효율을 높이고, allocation tree는 위쪽 또는 아래쪽으로 일정 크기 이상의 빈 range를 검색하는 기능을 제공합니다.
Normal API는 내부 RCU와 spinlock을 관리하며 `mtree_store()`, `mtree_load()`, `mtree_insert()`, `mt_for_each()` 같은 간단한 interface를 제공합니다. Advanced API는 `ma_state`의 `index`와 `last`로 탐색 상태와 range를 유지해 반복 작업과 lock 유지 비용을 줄이지만, caller가 locking을 책임져야 합니다.
Allocation이 불가능한 write 구간은 `mas_expected_entries()`로 최악의 경우 필요한 node를 미리 확보할 수 있습니다. External lock이 필요하면 `MT_FLAGS_LOCK_EXTERN`과 `MTREE_INIT_EXT()`를 사용합니다.