1.. SPDX-License-Identifier: GPL-2.0+ 2 3 4========== 5Maple Tree 6========== 7 8:Author: Liam R. Howlett 9 10Overview 11======== 12 13The Maple Tree is a B-Tree data type which is optimized for storing 14non-overlapping ranges, including ranges of size 1. The tree was designed to 15be simple to use and does not require a user written search method. It 16supports iterating over a range of entries and going to the previous or next 17entry in a cache-efficient manner. The tree can also be put into an RCU-safe 18mode of operation which allows reading and writing concurrently. Writers must 19synchronize on a lock, which can be the default spinlock, or the user can set 20the lock to an external lock of a different type. Note that external locks may 21interfere with allocations in a low memory situation. 22 23The Maple Tree maintains a small memory footprint and was designed to use 24modern processor cache efficiently. The majority of the users will be able to 25use the normal API. An :ref:`maple-tree-advanced-api` exists for more complex 26scenarios. The most important usage of the Maple Tree is the tracking of the 27virtual memory areas. 28 29The Maple Tree can store values between ``0`` and ``ULONG_MAX``. The Maple 30Tree reserves values with the bottom two bits set to '10' which are below 4096 31(ie 2, 6, 10 .. 4094) for internal use. If the entries may use reserved 32entries then the users can convert the entries using xa_mk_value() and convert 33them back by calling xa_to_value(). If the user needs to use a reserved 34value, then the user can convert the value when using the 35:ref:`maple-tree-advanced-api`, but are blocked by the normal API. 36 37The Maple Tree can also be configured to support searching for a gap of a given 38size (or larger). 39 40Pre-allocating of nodes is also supported using the 41:ref:`maple-tree-advanced-api`. This is useful for users who must guarantee a 42successful store operation within a given 43code segment when allocating cannot be done. Allocations of nodes are 44relatively small at around 256 bytes. 45 46Since the maple tree uses internal nodes that are allocated and has rules on 47data density, erasing an entry may cause allocations to occur. That is, 48erasing an entry may consume memory. Users must take care to ensure that they 49do not violate the larger system constraints on when and how memory is 50allocated. Most situations are fine to allocate, but the pre-allocation 51support is provided as a mechanism to avoid trickier situations. There is also 52the possibility of using special entries and clean up the tree later, in 53extreme circumstances. 54 55.. _maple-tree-normal-api: 56 57Normal API 58========== 59 60Start by initialising a maple tree, either with DEFINE_MTREE() for statically 61allocated maple trees or mt_init() for dynamically allocated ones. A 62freshly-initialised maple tree contains a ``NULL`` pointer for the range ``0`` 63- ``ULONG_MAX``. There are currently two types of maple trees supported: the 64allocation tree and the regular tree. The regular tree has a higher branching 65factor for internal nodes. The allocation tree has a lower branching factor 66but allows the user to search for a gap of a given size or larger from either 67``0`` upwards or ``ULONG_MAX`` down. An allocation tree can be used by 68passing in the ``MT_FLAGS_ALLOC_RANGE`` flag when initialising the tree. 69 70You can then set entries using mtree_store() or mtree_store_range(). 71mtree_store() will overwrite any entry with the new entry and return 0 on 72success or an error code otherwise. mtree_store_range() works in the same way 73but takes a range. mtree_load() is used to retrieve the entry stored at a 74given index. You can use mtree_erase() to erase an entire range by only 75knowing one value within that range, or mtree_store() call with an entry of 76NULL may be used to partially erase a range or many ranges at once. Note that 77mtree_erase() may use GFP_KERNEL | __GFP_NOFAIL for allocations and cannot 78fail. mtree_erase() can sleep, so it must not be called from an atomic 79context. 80 81If you want to only store a new entry to a range (or index) if that range is 82currently ``NULL``, you can use mtree_insert_range() or mtree_insert() which 83return -EEXIST if the range is not empty. 84 85You can search for an entry from an index upwards by using mt_find(). 86 87You can walk each entry within a range by calling mt_for_each(). You must 88provide a temporary variable to store a cursor. If you want to walk each 89element of the tree then ``0`` and ``ULONG_MAX`` may be used as the range. If 90the caller is going to hold the lock for the duration of the walk then it is 91worth looking at the mas_for_each() API in the :ref:`maple-tree-advanced-api` 92section. 93 94Sometimes it is necessary to ensure the next call to store to a maple tree does 95not allocate memory, please see :ref:`maple-tree-advanced-api` for this use case. 96 97You can use mtree_dup() to duplicate an entire maple tree. It is a more 98efficient way than inserting all elements one by one into a new tree. 99 100Finally, you can remove all entries from a maple tree by calling 101mtree_destroy(). If the maple tree entries are pointers, you may wish to free 102the entries first. 103 104Allocating Nodes 105---------------- 106 107The allocations are handled by the internal tree code. See 108:ref:`maple-tree-advanced-alloc` for other options. 109 110Locking 111------- 112 113You do not have to worry about locking. See :ref:`maple-tree-advanced-locks` 114for other options. 115 116The Maple Tree uses RCU and an internal spinlock to synchronise access: 117 118Takes RCU read lock: 119 * mtree_load() 120 * mt_find() 121 * mt_for_each() 122 * mt_next() 123 * mt_prev() 124 125Takes ma_lock internally: 126 * mtree_store() 127 * mtree_store_range() 128 * mtree_insert() 129 * mtree_insert_range() 130 * mtree_erase() 131 * mtree_dup() 132 * mtree_destroy() 133 * mt_set_in_rcu() 134 * mt_clear_in_rcu() 135 136If you want to take advantage of the internal lock to protect the data 137structures that you are storing in the Maple Tree, you can call mtree_lock() 138before calling mtree_load(), then take a reference count on the object you 139have found before calling mtree_unlock(). This will prevent stores from 140removing the object from the tree between looking up the object and 141incrementing the refcount. You can also use RCU to avoid dereferencing 142freed memory, but an explanation of that is beyond the scope of this 143document. 144 145.. _maple-tree-advanced-api: 146 147Advanced API 148============ 149 150The advanced API offers more flexibility and better performance at the 151cost of an interface which can be harder to use and has fewer safeguards. 152You must take care of your own locking while using the advanced API. 153You can use the ma_lock, RCU or an external lock for protection. 154You can mix advanced and normal operations on the same array, as long 155as the locking is compatible. The :ref:`maple-tree-normal-api` is implemented 156in terms of the advanced API. 157 158The advanced API is based around the ma_state, this is where the 'mas' 159prefix originates. The ma_state struct keeps track of tree operations to make 160life easier for both internal and external tree users. 161 162Initialising the maple tree is the same as in the :ref:`maple-tree-normal-api`. 163Please see above. 164 165The maple state keeps track of the range start and end in mas->index and 166mas->last, respectively. 167 168mas_walk() will walk the tree to the location of mas->index and set the 169mas->index and mas->last according to the range for the entry. 170 171You can set entries using mas_store(). mas_store() will overwrite any entry 172with the new entry and return the first existing entry that is overwritten. 173The range is passed in as members of the maple state: index and last. 174 175You can use mas_erase() to erase an entire range by setting index and 176last of the maple state to the desired range to erase. This will erase 177the first range that is found in that range, set the maple state index 178and last as the range that was erased and return the entry that existed 179at that location. Note that mas_erase() may allocate with the GFP_KERNEL 180__GFP_NOFAIL and cannot fail, but may sleep. If this is not okay, consider 181using mas_store_gfp() and pass it a ``NULL``, 182after setting up the correct range by walking to the entry. 183 184You can walk each entry within a range by using mas_for_each(). If you want 185to walk each element of the tree then ``0`` and ``ULONG_MAX`` may be used as 186the range. If the lock needs to be periodically dropped, see the locking 187section mas_pause(). 188 189Using a maple state allows mas_next() and mas_prev() to function as if the 190tree was a linked list. With such a high branching factor the amortized 191performance penalty is outweighed by cache optimization. mas_next() will 192return the next entry which occurs after the entry at index. mas_prev() 193will return the previous entry which occurs before the entry at index. 194 195mas_find() will find the first entry which exists at or above index on 196the first call, and the next entry from every subsequent calls. 197 198mas_find_rev() will find the first entry which exists at or below the last on 199the first call, and the previous entry from every subsequent calls. 200 201If the user needs to yield the lock during an operation, then the maple state 202must be paused using mas_pause(). 203 204There are a few extra interfaces provided when using an allocation tree. 205If you wish to search for a gap within a range, then mas_empty_area() 206or mas_empty_area_rev() can be used. mas_empty_area() searches for a gap 207starting at the lowest index given up to the maximum of the range. 208mas_empty_area_rev() searches for a gap starting at the highest index given 209and continues downward to the lower bound of the range. 210 211.. _maple-tree-advanced-alloc: 212 213Advanced Allocating Nodes 214------------------------- 215 216Allocations are usually handled internally to the tree, however if allocations 217need to occur before a write occurs then calling mas_expected_entries() will 218allocate the worst-case number of needed nodes to insert the provided number of 219ranges. This also causes the tree to enter mass insertion mode. Once 220insertions are complete calling mas_destroy() on the maple state will free the 221unused allocations. 222 223.. _maple-tree-advanced-locks: 224 225Advanced Locking 226---------------- 227 228The maple tree uses a spinlock by default, but external locks can be used for 229tree updates as well. To use an external lock, the tree must be initialized 230with the ``MT_FLAGS_LOCK_EXTERN`` flag, this is usually done with the 231MTREE_INIT_EXT() #define, which takes an external lock as an argument. 232 233Functions and structures 234======================== 235 236.. kernel-doc:: include/linux/maple_tree.h 237.. kernel-doc:: lib/maple_tree.c 238