Documentation/core-api/xarray.rst

4 XArray  title
12 The XArray is an abstract data type which behaves like a very large array
21 The XArray implementation is efficient when the indices used are densely
23 perform well.  The XArray is optimised for small indices, but still has
25 ``ULONG_MAX`` then the XArray is not the data type for you.  The most
26 important user of the XArray is the page cache.
28 Normal pointers may be stored in the XArray directly.  They must be 4-byte
34 You can also store integers between 0 and ``LONG_MAX`` in the XArray.
36 When you retrieve an entry from the XArray, you can check whether it is
40 Some users want to tag the pointers they store in the XArray.  You can
46 particular XArray.
48 The XArray does not support storing IS_ERR() pointers as some
51 An unusual feature of the XArray is the ability to create entries which
56 xa_erase() or xa_store() with ``NULL``) any entry will cause the XArray
62 Start by initialising an XArray, either with DEFINE_XARRAY()
64 allocated ones.  A freshly-initialised XArray contains a ``NULL``
74 XArray was initialized with ``XA_FLAGS_ALLOC``.
86 You can copy entries out of the XArray into a plain array by calling
87 xa_extract().  Or you can iterate over the present entries in the XArray
90 present entry in the XArray.
112 Finally, you can remove all entries from an XArray by calling
113 xa_destroy().  If the XArray entries are pointers, you may wish
115 entries in the XArray using the xa_for_each() iterator.
127 xa_clear_mark().  You can ask whether any entry in the XArray has a
129 XArray causes all marks associated with that entry to be cleared.
145 If you use DEFINE_XARRAY_ALLOC() to define the XArray, or
147 the XArray changes to track whether entries are in use or not.
150 in the XArray.  If you need to modify the array from interrupt context,
155 also mark the entry as being allocated.  Unlike a normal XArray, storing
166 You cannot use ``XA_MARK_0`` with an allocating XArray as this mark
175 parameter in case the XArray needs to allocate memory to store this entry.
189 The XArray uses RCU and an internal spinlock to synchronise access:
239 that you are storing in the XArray, you can call xa_lock()
247 The XArray does not disable interrupts or softirqs while modifying
248 the array.  It is safe to read the XArray from interrupt or softirq
251 If, for example, you want to store entries in the XArray in process
280 If you are going to modify the XArray from interrupt or softirq context,
288 Sharing the XArray with interrupt context is also possible, either
296 Sometimes you need to protect access to the XArray with a mutex because
322 XArray.  It is used as a cursor to maintain the position in the XArray
335 errors currently generated by the XArray code itself are ``ENOMEM`` and
354 The XArray reserves some entries for its own purposes.  These are never
368      - An XArray node.  May be visible when using a multi-index xa_state.
385        an entry in the XArray which can be used to reserve the index for
401 XArray is marked with ``XA_FLAGS_TRACK_FREE``, in which case mark 0 is set
411 If you need to move to a different index in the XArray, call
434 When iterating over a range of the XArray using xas_for_each()
445 XArray; they will do nothing if you have called xas_pause() or xas_set()
449 called each time the XArray updates a node.  This is used by the page
456 The XArray has the ability to tie multiple indices together so that
477 in the xa_state will not be changed.  When iterating over an XArray