Documentation/core-api/xarray.rst

   1 .. SPDX-License-Identifier: GPL-2.0+
   2
   3 ======
   4 XArray
   5 ======
   6
   7 :Author: Matthew Wilcox
   8
   9 Overview
  10 ========
  11
  12 The XArray is an abstract data type which behaves like a very large array
  13 of pointers.  It meets many of the same needs as a hash or a conventional
  14 resizable array.  Unlike a hash, it allows you to sensibly go to the
  15 next or previous entry in a cache-efficient manner.  In contrast to a
  16 resizable array, there is no need to copy data or change MMU mappings in
  17 order to grow the array.  It is more memory-efficient, parallelisable
  18 and cache friendly than a doubly-linked list.  It takes advantage of
  19 RCU to perform lookups without locking.
  20
  21 The XArray implementation is efficient when the indices used are densely
  22 clustered; hashing the object and using the hash as the index will not
  23 perform well.  The XArray is optimised for small indices, but still has
  24 good performance with large indices.  If your index can be larger than
  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.
  27
  28 Each non-``NULL`` entry in the array has three bits associated with
  29 it called marks.  Each mark may be set or cleared independently of
  30 the others.  You can iterate over entries which are marked.
  31
  32 Normal pointers may be stored in the XArray directly.  They must be 4-byte
  33 aligned, which is true for any pointer returned from :c:func:`kmalloc` and
  34 :c:func:`alloc_page`.  It isn't true for arbitrary user-space pointers,
  35 nor for function pointers.  You can store pointers to statically allocated
  36 objects, as long as those objects have an alignment of at least 4.
  37
  38 You can also store integers between 0 and ``LONG_MAX`` in the XArray.
  39 You must first convert it into an entry using :c:func:`xa_mk_value`.
  40 When you retrieve an entry from the XArray, you can check whether it is
  41 a value entry by calling :c:func:`xa_is_value`, and convert it back to
  42 an integer by calling :c:func:`xa_to_value`.
  43
  44 Some users want to store tagged pointers instead of using the marks
  45 described above.  They can call :c:func:`xa_tag_pointer` to create an
  46 entry with a tag, :c:func:`xa_untag_pointer` to turn a tagged entry
  47 back into an untagged pointer and :c:func:`xa_pointer_tag` to retrieve
  48 the tag of an entry.  Tagged pointers use the same bits that are used
  49 to distinguish value entries from normal pointers, so each user must
  50 decide whether they want to store value entries or tagged pointers in
  51 any particular XArray.
  52
  53 The XArray does not support storing :c:func:`IS_ERR` pointers as some
  54 conflict with value entries or internal entries.
  55
  56 An unusual feature of the XArray is the ability to create entries which
  57 occupy a range of indices.  Once stored to, looking up any index in
  58 the range will return the same entry as looking up any other index in
  59 the range.  Setting a mark on one index will set it on all of them.
  60 Storing to any index will store to all of them.  Multi-index entries can
  61 be explicitly split into smaller entries, or storing ``NULL`` into any
  62 entry will cause the XArray to forget about the range.
  63
  64 Normal API
  65 ==========
  66
  67 Start by initialising an XArray, either with :c:func:`DEFINE_XARRAY`
  68 for statically allocated XArrays or :c:func:`xa_init` for dynamically
  69 allocated ones.  A freshly-initialised XArray contains a ``NULL``
  70 pointer at every index.
  71
  72 You can then set entries using :c:func:`xa_store` and get entries
  73 using :c:func:`xa_load`.  xa_store will overwrite any entry with the
  74 new entry and return the previous entry stored at that index.  You can
  75 use :c:func:`xa_erase` instead of calling :c:func:`xa_store` with a
  76 ``NULL`` entry.  There is no difference between an entry that has never
  77 been stored to, one that has been erased and one that has most recently
  78 had ``NULL`` stored to it.
  79
  80 You can conditionally replace an entry at an index by using
  81 :c:func:`xa_cmpxchg`.  Like :c:func:`cmpxchg`, it will only succeed if
  82 the entry at that index has the 'old' value.  It also returns the entry
  83 which was at that index; if it returns the same entry which was passed as
  84 'old', then :c:func:`xa_cmpxchg` succeeded.
  85
  86 If you want to only store a new entry to an index if the current entry
  87 at that index is ``NULL``, you can use :c:func:`xa_insert` which
  88 returns ``-EEXIST`` if the entry is not empty.
  89
  90 You can enquire whether a mark is set on an entry by using
  91 :c:func:`xa_get_mark`.  If the entry is not ``NULL``, you can set a mark
  92 on it by using :c:func:`xa_set_mark` and remove the mark from an entry by
  93 calling :c:func:`xa_clear_mark`.  You can ask whether any entry in the
  94 XArray has a particular mark set by calling :c:func:`xa_marked`.
  95
  96 You can copy entries out of the XArray into a plain array by calling
  97 :c:func:`xa_extract`.  Or you can iterate over the present entries in
  98 the XArray by calling :c:func:`xa_for_each`.  You may prefer to use
  99 :c:func:`xa_find` or :c:func:`xa_find_after` to move to the next present
 100 entry in the XArray.
 101
 102 Calling :c:func:`xa_store_range` stores the same entry in a range
 103 of indices.  If you do this, some of the other operations will behave
 104 in a slightly odd way.  For example, marking the entry at one index
 105 may result in the entry being marked at some, but not all of the other
 106 indices.  Storing into one index may result in the entry retrieved by
 107 some, but not all of the other indices changing.
 108
 109 Sometimes you need to ensure that a subsequent call to :c:func:`xa_store`
 110 will not need to allocate memory.  The :c:func:`xa_reserve` function
 111 will store a reserved entry at the indicated index.  Users of the normal
 112 API will see this entry as containing ``NULL``.  If you do not need to
 113 use the reserved entry, you can call :c:func:`xa_release` to remove the
 114 unused entry.  If another user has stored to the entry in the meantime,
 115 :c:func:`xa_release` will do nothing; if instead you want the entry to
 116 become ``NULL``, you should use :c:func:`xa_erase`.
 117
 118 If all entries in the array are ``NULL``, the :c:func:`xa_empty` function
 119 will return ``true``.
 120
 121 Finally, you can remove all entries from an XArray by calling
 122 :c:func:`xa_destroy`.  If the XArray entries are pointers, you may wish
 123 to free the entries first.  You can do this by iterating over all present
 124 entries in the XArray using the :c:func:`xa_for_each` iterator.
 125
 126 Allocating XArrays
 127 ------------------
 128
 129 If you use :c:func:`DEFINE_XARRAY_ALLOC` to define the XArray, or
 130 initialise it by passing ``XA_FLAGS_ALLOC`` to :c:func:`xa_init_flags`,
 131 the XArray changes to track whether entries are in use or not.
 132
 133 You can call :c:func:`xa_alloc` to store the entry at any unused index
 134 in the XArray.  If you need to modify the array from interrupt context,
 135 you can use :c:func:`xa_alloc_bh` or :c:func:`xa_alloc_irq` to disable
 136 interrupts while allocating the ID.
 137
 138 Using :c:func:`xa_store`, :c:func:`xa_cmpxchg` or :c:func:`xa_insert`
 139 will mark the entry as being allocated.  Unlike a normal XArray, storing
 140 ``NULL`` will mark the entry as being in use, like :c:func:`xa_reserve`.
 141 To free an entry, use :c:func:`xa_erase` (or :c:func:`xa_release` if
 142 you only want to free the entry if it's ``NULL``).
 143
 144 You cannot use ``XA_MARK_0`` with an allocating XArray as this mark
 145 is used to track whether an entry is free or not.  The other marks are
 146 available for your use.
 147
 148 Memory allocation
 149 -----------------
 150
 151 The :c:func:`xa_store`, :c:func:`xa_cmpxchg`, :c:func:`xa_alloc`,
 152 :c:func:`xa_reserve` and :c:func:`xa_insert` functions take a gfp_t
 153 parameter in case the XArray needs to allocate memory to store this entry.
 154 If the entry is being deleted, no memory allocation needs to be performed,
 155 and the GFP flags specified will be ignored.
 156
 157 It is possible for no memory to be allocatable, particularly if you pass
 158 a restrictive set of GFP flags.  In that case, the functions return a
 159 special value which can be turned into an errno using :c:func:`xa_err`.
 160 If you don't need to know exactly which error occurred, using
 161 :c:func:`xa_is_err` is slightly more efficient.
 162
 163 Locking
 164 -------
 165
 166 When using the Normal API, you do not have to worry about locking.
 167 The XArray uses RCU and an internal spinlock to synchronise access:
 168
 169 No lock needed:
 170  * :c:func:`xa_empty`
 171  * :c:func:`xa_marked`
 172
 173 Takes RCU read lock:
 174  * :c:func:`xa_load`
 175  * :c:func:`xa_for_each`
 176  * :c:func:`xa_find`
 177  * :c:func:`xa_find_after`
 178  * :c:func:`xa_extract`
 179  * :c:func:`xa_get_mark`
 180
 181 Takes xa_lock internally:
 182  * :c:func:`xa_store`
 183  * :c:func:`xa_store_bh`
 184  * :c:func:`xa_store_irq`
 185  * :c:func:`xa_insert`
 186  * :c:func:`xa_erase`
 187  * :c:func:`xa_erase_bh`
 188  * :c:func:`xa_erase_irq`
 189  * :c:func:`xa_cmpxchg`
 190  * :c:func:`xa_cmpxchg_bh`
 191  * :c:func:`xa_cmpxchg_irq`
 192  * :c:func:`xa_store_range`
 193  * :c:func:`xa_alloc`
 194  * :c:func:`xa_alloc_bh`
 195  * :c:func:`xa_alloc_irq`
 196  * :c:func:`xa_reserve`
 197  * :c:func:`xa_reserve_bh`
 198  * :c:func:`xa_reserve_irq`
 199  * :c:func:`xa_destroy`
 200  * :c:func:`xa_set_mark`
 201  * :c:func:`xa_clear_mark`
 202
 203 Assumes xa_lock held on entry:
 204  * :c:func:`__xa_store`
 205  * :c:func:`__xa_insert`
 206  * :c:func:`__xa_erase`
 207  * :c:func:`__xa_cmpxchg`
 208  * :c:func:`__xa_alloc`
 209  * :c:func:`__xa_reserve`
 210  * :c:func:`__xa_set_mark`
 211  * :c:func:`__xa_clear_mark`
 212
 213 If you want to take advantage of the lock to protect the data structures
 214 that you are storing in the XArray, you can call :c:func:`xa_lock`
 215 before calling :c:func:`xa_load`, then take a reference count on the
 216 object you have found before calling :c:func:`xa_unlock`.  This will
 217 prevent stores from removing the object from the array between looking
 218 up the object and incrementing the refcount.  You can also use RCU to
 219 avoid dereferencing freed memory, but an explanation of that is beyond
 220 the scope of this document.
 221
 222 The XArray does not disable interrupts or softirqs while modifying
 223 the array.  It is safe to read the XArray from interrupt or softirq
 224 context as the RCU lock provides enough protection.
 225
 226 If, for example, you want to store entries in the XArray in process
 227 context and then erase them in softirq context, you can do that this way::
 228
 229     void foo_init(struct foo *foo)
 230     {
 231         xa_init_flags(&foo->array, XA_FLAGS_LOCK_BH);
 232     }
 233
 234     int foo_store(struct foo *foo, unsigned long index, void *entry)
 235     {
 236         int err;
 237
 238         xa_lock_bh(&foo->array);
 239         err = xa_err(__xa_store(&foo->array, index, entry, GFP_KERNEL));
 240         if (!err)
 241             foo->count++;
 242         xa_unlock_bh(&foo->array);
 243         return err;
 244     }
 245
 246     /* foo_erase() is only called from softirq context */
 247     void foo_erase(struct foo *foo, unsigned long index)
 248     {
 249         xa_lock(&foo->array);
 250         __xa_erase(&foo->array, index);
 251         foo->count--;
 252         xa_unlock(&foo->array);
 253     }
 254
 255 If you are going to modify the XArray from interrupt or softirq context,
 256 you need to initialise the array using :c:func:`xa_init_flags`, passing
 257 ``XA_FLAGS_LOCK_IRQ`` or ``XA_FLAGS_LOCK_BH``.
 258
 259 The above example also shows a common pattern of wanting to extend the
 260 coverage of the xa_lock on the store side to protect some statistics
 261 associated with the array.
 262
 263 Sharing the XArray with interrupt context is also possible, either
 264 using :c:func:`xa_lock_irqsave` in both the interrupt handler and process
 265 context, or :c:func:`xa_lock_irq` in process context and :c:func:`xa_lock`
 266 in the interrupt handler.  Some of the more common patterns have helper
 267 functions such as :c:func:`xa_store_bh`, :c:func:`xa_store_irq`,
 268 :c:func:`xa_erase_bh`, :c:func:`xa_erase_irq`, :c:func:`xa_cmpxchg_bh`
 269 and :c:func:`xa_cmpxchg_irq`.
 270
 271 Sometimes you need to protect access to the XArray with a mutex because
 272 that lock sits above another mutex in the locking hierarchy.  That does
 273 not entitle you to use functions like :c:func:`__xa_erase` without taking
 274 the xa_lock; the xa_lock is used for lockdep validation and will be used
 275 for other purposes in the future.
 276
 277 The :c:func:`__xa_set_mark` and :c:func:`__xa_clear_mark` functions are also
 278 available for situations where you look up an entry and want to atomically
 279 set or clear a mark.  It may be more efficient to use the advanced API
 280 in this case, as it will save you from walking the tree twice.
 281
 282 Advanced API
 283 ============
 284
 285 The advanced API offers more flexibility and better performance at the
 286 cost of an interface which can be harder to use and has fewer safeguards.
 287 No locking is done for you by the advanced API, and you are required
 288 to use the xa_lock while modifying the array.  You can choose whether
 289 to use the xa_lock or the RCU lock while doing read-only operations on
 290 the array.  You can mix advanced and normal operations on the same array;
 291 indeed the normal API is implemented in terms of the advanced API.  The
 292 advanced API is only available to modules with a GPL-compatible license.
 293
 294 The advanced API is based around the xa_state.  This is an opaque data
 295 structure which you declare on the stack using the :c:func:`XA_STATE`
 296 macro.  This macro initialises the xa_state ready to start walking
 297 around the XArray.  It is used as a cursor to maintain the position
 298 in the XArray and let you compose various operations together without
 299 having to restart from the top every time.
 300
 301 The xa_state is also used to store errors.  You can call
 302 :c:func:`xas_error` to retrieve the error.  All operations check whether
 303 the xa_state is in an error state before proceeding, so there's no need
 304 for you to check for an error after each call; you can make multiple
 305 calls in succession and only check at a convenient point.  The only
 306 errors currently generated by the XArray code itself are ``ENOMEM`` and
 307 ``EINVAL``, but it supports arbitrary errors in case you want to call
 308 :c:func:`xas_set_err` yourself.
 309
 310 If the xa_state is holding an ``ENOMEM`` error, calling :c:func:`xas_nomem`
 311 will attempt to allocate more memory using the specified gfp flags and
 312 cache it in the xa_state for the next attempt.  The idea is that you take
 313 the xa_lock, attempt the operation and drop the lock.  The operation
 314 attempts to allocate memory while holding the lock, but it is more
 315 likely to fail.  Once you have dropped the lock, :c:func:`xas_nomem`
 316 can try harder to allocate more memory.  It will return ``true`` if it
 317 is worth retrying the operation (i.e. that there was a memory error *and*
 318 more memory was allocated).  If it has previously allocated memory, and
 319 that memory wasn't used, and there is no error (or some error that isn't
 320 ``ENOMEM``), then it will free the memory previously allocated.
 321
 322 Internal Entries
 323 ----------------
 324
 325 The XArray reserves some entries for its own purposes.  These are never
 326 exposed through the normal API, but when using the advanced API, it's
 327 possible to see them.  Usually the best way to handle them is to pass them
 328 to :c:func:`xas_retry`, and retry the operation if it returns ``true``.
 329
 330 .. flat-table::
 331    :widths: 1 1 6
 332
 333    * - Name
 334      - Test
 335      - Usage
 336
 337    * - Node
 338      - :c:func:`xa_is_node`
 339      - An XArray node.  May be visible when using a multi-index xa_state.
 340
 341    * - Sibling
 342      - :c:func:`xa_is_sibling`
 343      - A non-canonical entry for a multi-index entry.  The value indicates
 344        which slot in this node has the canonical entry.
 345
 346    * - Retry
 347      - :c:func:`xa_is_retry`
 348      - This entry is currently being modified by a thread which has the
 349        xa_lock.  The node containing this entry may be freed at the end
 350        of this RCU period.  You should restart the lookup from the head
 351        of the array.
 352
 353    * - Zero
 354      - :c:func:`xa_is_zero`
 355      - Zero entries appear as ``NULL`` through the Normal API, but occupy
 356        an entry in the XArray which can be used to reserve the index for
 357        future use.  This is used by allocating XArrays for allocated entries
 358        which are ``NULL``.
 359
 360 Other internal entries may be added in the future.  As far as possible, they
 361 will be handled by :c:func:`xas_retry`.
 362
 363 Additional functionality
 364 ------------------------
 365
 366 The :c:func:`xas_create_range` function allocates all the necessary memory
 367 to store every entry in a range.  It will set ENOMEM in the xa_state if
 368 it cannot allocate memory.
 369
 370 You can use :c:func:`xas_init_marks` to reset the marks on an entry
 371 to their default state.  This is usually all marks clear, unless the
 372 XArray is marked with ``XA_FLAGS_TRACK_FREE``, in which case mark 0 is set
 373 and all other marks are clear.  Replacing one entry with another using
 374 :c:func:`xas_store` will not reset the marks on that entry; if you want
 375 the marks reset, you should do that explicitly.
 376
 377 The :c:func:`xas_load` will walk the xa_state as close to the entry
 378 as it can.  If you know the xa_state has already been walked to the
 379 entry and need to check that the entry hasn't changed, you can use
 380 :c:func:`xas_reload` to save a function call.
 381
 382 If you need to move to a different index in the XArray, call
 383 :c:func:`xas_set`.  This resets the cursor to the top of the tree, which
 384 will generally make the next operation walk the cursor to the desired
 385 spot in the tree.  If you want to move to the next or previous index,
 386 call :c:func:`xas_next` or :c:func:`xas_prev`.  Setting the index does
 387 not walk the cursor around the array so does not require a lock to be
 388 held, while moving to the next or previous index does.
 389
 390 You can search for the next present entry using :c:func:`xas_find`.  This
 391 is the equivalent of both :c:func:`xa_find` and :c:func:`xa_find_after`;
 392 if the cursor has been walked to an entry, then it will find the next
 393 entry after the one currently referenced.  If not, it will return the
 394 entry at the index of the xa_state.  Using :c:func:`xas_next_entry` to
 395 move to the next present entry instead of :c:func:`xas_find` will save
 396 a function call in the majority of cases at the expense of emitting more
 397 inline code.
 398
 399 The :c:func:`xas_find_marked` function is similar.  If the xa_state has
 400 not been walked, it will return the entry at the index of the xa_state,
 401 if it is marked.  Otherwise, it will return the first marked entry after
 402 the entry referenced by the xa_state.  The :c:func:`xas_next_marked`
 403 function is the equivalent of :c:func:`xas_next_entry`.
 404
 405 When iterating over a range of the XArray using :c:func:`xas_for_each`
 406 or :c:func:`xas_for_each_marked`, it may be necessary to temporarily stop
 407 the iteration.  The :c:func:`xas_pause` function exists for this purpose.
 408 After you have done the necessary work and wish to resume, the xa_state
 409 is in an appropriate state to continue the iteration after the entry
 410 you last processed.  If you have interrupts disabled while iterating,
 411 then it is good manners to pause the iteration and reenable interrupts
 412 every ``XA_CHECK_SCHED`` entries.
 413
 414 The :c:func:`xas_get_mark`, :c:func:`xas_set_mark` and
 415 :c:func:`xas_clear_mark` functions require the xa_state cursor to have
 416 been moved to the appropriate location in the xarray; they will do
 417 nothing if you have called :c:func:`xas_pause` or :c:func:`xas_set`
 418 immediately before.
 419
 420 You can call :c:func:`xas_set_update` to have a callback function
 421 called each time the XArray updates a node.  This is used by the page
 422 cache workingset code to maintain its list of nodes which contain only
 423 shadow entries.
 424
 425 Multi-Index Entries
 426 -------------------
 427
 428 The XArray has the ability to tie multiple indices together so that
 429 operations on one index affect all indices.  For example, storing into
 430 any index will change the value of the entry retrieved from any index.
 431 Setting or clearing a mark on any index will set or clear the mark
 432 on every index that is tied together.  The current implementation
 433 only allows tying ranges which are aligned powers of two together;
 434 eg indices 64-127 may be tied together, but 2-6 may not be.  This may
 435 save substantial quantities of memory; for example tying 512 entries
 436 together will save over 4kB.
 437
 438 You can create a multi-index entry by using :c:func:`XA_STATE_ORDER`
 439 or :c:func:`xas_set_order` followed by a call to :c:func:`xas_store`.
 440 Calling :c:func:`xas_load` with a multi-index xa_state will walk the
 441 xa_state to the right location in the tree, but the return value is not
 442 meaningful, potentially being an internal entry or ``NULL`` even when there
 443 is an entry stored within the range.  Calling :c:func:`xas_find_conflict`
 444 will return the first entry within the range or ``NULL`` if there are no
 445 entries in the range.  The :c:func:`xas_for_each_conflict` iterator will
 446 iterate over every entry which overlaps the specified range.
 447
 448 If :c:func:`xas_load` encounters a multi-index entry, the xa_index
 449 in the xa_state will not be changed.  When iterating over an XArray
 450 or calling :c:func:`xas_find`, if the initial index is in the middle
 451 of a multi-index entry, it will not be altered.  Subsequent calls
 452 or iterations will move the index to the first index in the range.
 453 Each entry will only be returned once, no matter how many indices it
 454 occupies.
 455
 456 Using :c:func:`xas_next` or :c:func:`xas_prev` with a multi-index xa_state
 457 is not supported.  Using either of these functions on a multi-index entry
 458 will reveal sibling entries; these should be skipped over by the caller.
 459
 460 Storing ``NULL`` into any index of a multi-index entry will set the entry
 461 at every index to ``NULL`` and dissolve the tie.  Splitting a multi-index
 462 entry into entries occupying smaller ranges is not yet supported.
 463
 464 Functions and structures
 465 ========================
 466
 467 .. kernel-doc:: include/linux/xarray.h
 468 .. kernel-doc:: lib/xarray.c