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