Documentation/core-api/maple_tree.rst

Source file repositories/reference/linux-study-clean/Documentation/core-api/maple_tree.rst

File Facts

System
Linux kernel
Corpus path
Documentation/core-api/maple_tree.rst
Extension
.rst
Size
9445 bytes
Lines
222
Domain
Support Tooling And Documentation
Bucket
Documentation
Inferred role
Support Tooling And Documentation: documentation
Status
atlas-only

Why This File Exists

Repository support layer: documentation, build tooling, samples, user-space helper tools, generated initramfs support, licenses, and validation utilities.

Dependency Surface

Detected Declarations

Annotated Snippet

.. 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.

Annotation

Implementation Notes