Documentation/core-api/xarray.rst

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

File Facts

System
Linux kernel
Corpus path
Documentation/core-api/xarray.rst
Extension
.rst
Size
22418 bytes
Lines
511
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+

======
XArray
======

:Author: Matthew Wilcox

Overview
========

The XArray is an abstract data type which behaves like a very large array
of pointers.  It meets many of the same needs as a hash or a conventional
resizable array.  Unlike a hash, it allows you to sensibly go to the
next or previous entry in a cache-efficient manner.  In contrast to a
resizable array, there is no need to copy data or change MMU mappings in
order to grow the array.  It is more memory-efficient, parallelisable
and cache friendly than a doubly-linked list.  It takes advantage of
RCU to perform lookups without locking.

The XArray implementation is efficient when the indices used are densely
clustered; hashing the object and using the hash as the index will not
perform well.  The XArray is optimised for small indices, but still has
good performance with large indices.  If your index can be larger than
``ULONG_MAX`` then the XArray is not the data type for you.  The most
important user of the XArray is the page cache.

Normal pointers may be stored in the XArray directly.  They must be 4-byte
aligned, which is true for any pointer returned from kmalloc() and
alloc_page().  It isn't true for arbitrary user-space pointers,
nor for function pointers.  You can store pointers to statically allocated
objects, as long as those objects have an alignment of at least 4.

You can also store integers between 0 and ``LONG_MAX`` in the XArray.
You must first convert it into an entry using xa_mk_value().
When you retrieve an entry from the XArray, you can check whether it is
a value entry by calling xa_is_value(), and convert it back to
an integer by calling xa_to_value().

Some users want to tag the pointers they store in the XArray.  You can
call xa_tag_pointer() to create an entry with a tag, xa_untag_pointer()
to turn a tagged entry back into an untagged pointer and xa_pointer_tag()
to retrieve the tag of an entry.  Tagged pointers use the same bits that
are used to distinguish value entries from normal pointers, so you must
decide whether you want to store value entries or tagged pointers in any
particular XArray.

The XArray does not support storing IS_ERR() pointers as some
conflict with value entries or internal entries.

An unusual feature of the XArray is the ability to create entries which
occupy a range of indices.  Once stored to, looking up any index in
the range will return the same entry as looking up any other index in
the range.  Storing to any index will store to all of them.  Multi-index
entries can be explicitly split into smaller entries. Unsetting (using
xa_erase() or xa_store() with ``NULL``) any entry will cause the XArray
to forget about the range.

Normal API
==========

Start by initialising an XArray, either with DEFINE_XARRAY()
for statically allocated XArrays or xa_init() for dynamically
allocated ones.  A freshly-initialised XArray contains a ``NULL``
pointer at every index.

You can then set entries using xa_store() and get entries using
xa_load().  xa_store() will overwrite any entry with the new entry and
return the previous entry stored at that index.  You can unset entries
using xa_erase() or by setting the entry to ``NULL`` using xa_store().

Annotation

Implementation Notes