Something went wrong. Try again.
Linux kernel mirror (for testing) git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
Something went wrong. Try again.
9.4 kB · 221 lines
at master
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222.. 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 storingnon-overlapping ranges, including ranges of size 1. The tree was designed tobe simple to use and does not require a user written search method. Itsupports iterating over a range of entries and going to the previous or nextentry in a cache-efficient manner. The tree can also be put into an RCU-safemode of operation which allows reading and writing concurrently. Writers mustsynchronize on a lock, which can be the default spinlock, or the user can setthe lock to an external lock of a different type.
The Maple Tree maintains a small memory footprint and was designed to usemodern processor cache efficiently. The majority of the users will be able touse the normal API. An :ref:`maple-tree-advanced-api` exists for more complexscenarios. The most important usage of the Maple Tree is the tracking of thevirtual memory areas.
The Maple Tree can store values between ``0`` and ``ULONG_MAX``. The MapleTree 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 reservedentries then the users can convert the entries using xa_mk_value() and convertthem back by calling xa_to_value(). If the user needs to use a reservedvalue, 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 givensize (or larger).
Pre-allocating of nodes is also supported using the:ref:`maple-tree-advanced-api`. This is useful for users who must guarantee asuccessful store operation within a givencode segment when allocating cannot be done. Allocations of nodes arerelatively small at around 256 bytes.
.. _maple-tree-normal-api:
Normal API==========
Start by initialising a maple tree, either with DEFINE_MTREE() for staticallyallocated maple trees or mt_init() for dynamically allocated ones. Afreshly-initialised maple tree contains a ``NULL`` pointer for the range ``0``- ``ULONG_MAX``. There are currently two types of maple trees supported: theallocation tree and the regular tree. The regular tree has a higher branchingfactor for internal nodes. The allocation tree has a lower branching factorbut 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 bypassing 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 onsuccess or an error code otherwise. mtree_store_range() works in the same waybut takes a range. mtree_load() is used to retrieve the entry stored at agiven index. You can use mtree_erase() to erase an entire range by onlyknowing one value within that range, or mtree_store() call with an entry ofNULL 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 iscurrently ``NULL``, you can use mtree_insert_range() or mtree_insert() whichreturn -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 mustprovide a temporary variable to store a cursor. If you want to walk eachelement of the tree then ``0`` and ``ULONG_MAX`` may be used as the range. Ifthe caller is going to hold the lock for the duration of the walk then it isworth 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 doesnot 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 moreefficient way than inserting all elements one by one into a new tree.
Finally, you can remove all entries from a maple tree by callingmtree_destroy(). If the maple tree entries are pointers, you may wish to freethe 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 datastructures 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 youhave found before calling mtree_unlock(). This will prevent stores fromremoving the object from the tree between looking up the object andincrementing the refcount. You can also use RCU to avoid dereferencingfreed memory, but an explanation of that is beyond the scope of thisdocument.
.. _maple-tree-advanced-api:
Advanced API============
The advanced API offers more flexibility and better performance at thecost 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 longas the locking is compatible. The :ref:`maple-tree-normal-api` is implementedin 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 makelife 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 andmas->last, respectively.
mas_walk() will walk the tree to the location of mas->index and set themas->index and mas->last according to the range for the entry.
You can set entries using mas_store(). mas_store() will overwrite any entrywith 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 andlast of the maple state to the desired range to erase. This will erasethe first range that is found in that range, set the maple state indexand last as the range that was erased and return the entry that existedat that location.
You can walk each entry within a range by using mas_for_each(). If you wantto walk each element of the tree then ``0`` and ``ULONG_MAX`` may be used asthe range. If the lock needs to be periodically dropped, see the lockingsection mas_pause().
Using a maple state allows mas_next() and mas_prev() to function as if thetree was a linked list. With such a high branching factor the amortizedperformance penalty is outweighed by cache optimization. mas_next() willreturn 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 onthe 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 onthe first call, and the previous entry from every subsequent calls.
If the user needs to yield the lock during an operation, then the maple statemust 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 gapstarting 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 givenand 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 allocationsneed to occur before a write occurs then calling mas_expected_entries() willallocate the worst-case number of needed nodes to insert the provided number ofranges. This also causes the tree to enter mass insertion mode. Onceinsertions are complete calling mas_destroy() on the maple state will free theunused allocations.
.. _maple-tree-advanced-locks:
Advanced Locking----------------
The maple tree uses a spinlock by default, but external locks can be used fortree updates as well. To use an external lock, the tree must be initializedwith the ``MT_FLAGS_LOCK_EXTERN flag``, this is usually done with theMTREE_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