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