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 ``-EBUSY`` 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
 112 normal API will see this entry as containing ``NULL``.  If you do
 113 not need to use the reserved entry, you can call :c:func:`xa_release`
 114 to remove the unused entry.  If another user has stored to the entry
 115 in the meantime, :c:func:`xa_release` will do nothing; if instead you
 116 want the entry to become ``NULL``, you should use :c:func:`xa_erase`.
 117 Using :c:func:`xa_insert` on a reserved entry will fail.
 118
 119 If all entries in the array are ``NULL``, the :c:func:`xa_empty` function
 120 will return ``true``.
 121
 122 Finally, you can remove all entries from an XArray by calling
 123 :c:func:`xa_destroy`.  If the XArray entries are pointers, you may wish
 124 to free the entries first.  You can do this by iterating over all present
 125 entries in the XArray using the :c:func:`xa_for_each` iterator.
 126
 127 Allocating XArrays
 128 ------------------
 129
 130 If you use :c:func:`DEFINE_XARRAY_ALLOC` to define the XArray, or
 131 initialise it by passing ``XA_FLAGS_ALLOC`` to :c:func:`xa_init_flags`,
 132 the XArray changes to track whether entries are in use or not.
 133
 134 You can call :c:func:`xa_alloc` to store the entry at an unused index
 135 in the XArray.  If you need to modify the array from interrupt context,
 136 you can use :c:func:`xa_alloc_bh` or :c:func:`xa_alloc_irq` to disable
 137 interrupts while allocating the ID.
 138
 139 Using :c:func:`xa_store`, :c:func:`xa_cmpxchg` or :c:func:`xa_insert` will
 140 also mark the entry as being allocated.  Unlike a normal XArray, storing
 141 ``NULL`` will mark the entry as being in use, like :c:func:`xa_reserve`.
 142 To free an entry, use :c:func:`xa_erase` (or :c:func:`xa_release` if
 143 you only want to free the entry if it's ``NULL``).
 144
 145 By default, the lowest free entry is allocated starting from 0.  If you
 146 want to allocate entries starting at 1, it is more efficient to use
 147 :c:func:`DEFINE_XARRAY_ALLOC1` or ``XA_FLAGS_ALLOC1``.  If you want to
 148 allocate IDs up to a maximum, then wrap back around to the lowest free
 149 ID, you can use :c:func:`xa_alloc_cyclic`.
 150
 151 You cannot use ``XA_MARK_0`` with an allocating XArray as this mark
 152 is used to track whether an entry is free or not.  The other marks are
 153 available for your use.
 154
 155 Memory allocation
 156 -----------------
 157
 158 The :c:func:`xa_store`, :c:func:`xa_cmpxchg`, :c:func:`xa_alloc`,
 159 :c:func:`xa_reserve` and :c:func:`xa_insert` functions take a gfp_t
 160 parameter in case the XArray needs to allocate memory to store this entry.
 161 If the entry is being deleted, no memory allocation needs to be performed,
 162 and the GFP flags specified will be ignored.
 163
 164 It is possible for no memory to be allocatable, particularly if you pass
 165 a restrictive set of GFP flags.  In that case, the functions return a
 166 special value which can be turned into an errno using :c:func:`xa_err`.
 167 If you don't need to know exactly which error occurred, using
 168 :c:func:`xa_is_err` is slightly more efficient.
 169
 170 Locking
 171 -------
 172
 173 When using the Normal API, you do not have to worry about locking.
 174 The XArray uses RCU and an internal spinlock to synchronise access:
 175
 176 No lock needed:
 177  * :c:func:`xa_empty`
 178  * :c:func:`xa_marked`
 179
 180 Takes RCU read lock:
 181  * :c:func:`xa_load`
 182  * :c:func:`xa_for_each`
 183  * :c:func:`xa_find`
 184  * :c:func:`xa_find_after`
 185  * :c:func:`xa_extract`
 186  * :c:func:`xa_get_mark`
 187
 188 Takes xa_lock internally:
 189  * :c:func:`xa_store`
 190  * :c:func:`xa_store_bh`
 191  * :c:func:`xa_store_irq`
 192  * :c:func:`xa_insert`
 193  * :c:func:`xa_insert_bh`
 194  * :c:func:`xa_insert_irq`
 195  * :c:func:`xa_erase`
 196  * :c:func:`xa_erase_bh`
 197  * :c:func:`xa_erase_irq`
 198  * :c:func:`xa_cmpxchg`
 199  * :c:func:`xa_cmpxchg_bh`
 200  * :c:func:`xa_cmpxchg_irq`
 201  * :c:func:`xa_store_range`
 202  * :c:func:`xa_alloc`
 203  * :c:func:`xa_alloc_bh`
 204  * :c:func:`xa_alloc_irq`
 205  * :c:func:`xa_reserve`
 206  * :c:func:`xa_reserve_bh`
 207  * :c:func:`xa_reserve_irq`
 208  * :c:func:`xa_destroy`
 209  * :c:func:`xa_set_mark`
 210  * :c:func:`xa_clear_mark`
 211
 212 Assumes xa_lock held on entry:
 213  * :c:func:`__xa_store`
 214  * :c:func:`__xa_insert`
 215  * :c:func:`__xa_erase`
 216  * :c:func:`__xa_cmpxchg`
 217  * :c:func:`__xa_alloc`
 218  * :c:func:`__xa_set_mark`
 219  * :c:func:`__xa_clear_mark`
 220
 221 If you want to take advantage of the lock to protect the data structures
 222 that you are storing in the XArray, you can call :c:func:`xa_lock`
 223 before calling :c:func:`xa_load`, then take a reference count on the
 224 object you have found before calling :c:func:`xa_unlock`.  This will
 225 prevent stores from removing the object from the array between looking
 226 up the object and incrementing the refcount.  You can also use RCU to
 227 avoid dereferencing freed memory, but an explanation of that is beyond
 228 the scope of this document.
 229
 230 The XArray does not disable interrupts or softirqs while modifying
 231 the array.  It is safe to read the XArray from interrupt or softirq
 232 context as the RCU lock provides enough protection.
 233
 234 If, for example, you want to store entries in the XArray in process
 235 context and then erase them in softirq context, you can do that this way::
 236
 237     void foo_init(struct foo *foo)
 238     {
 239         xa_init_flags(&foo->array, XA_FLAGS_LOCK_BH);
 240     }
 241
 242     int foo_store(struct foo *foo, unsigned long index, void *entry)
 243     {
 244         int err;
 245
 246         xa_lock_bh(&foo->array);
 247         err = xa_err(__xa_store(&foo->array, index, entry, GFP_KERNEL));
 248         if (!err)
 249             foo->count++;
 250         xa_unlock_bh(&foo->array);
 251         return err;
 252     }
 253
 254     /* foo_erase() is only called from softirq context */
 255     void foo_erase(struct foo *foo, unsigned long index)
 256     {
 257         xa_lock(&foo->array);
 258         __xa_erase(&foo->array, index);
 259         foo->count--;
 260         xa_unlock(&foo->array);
 261     }
 262
 263 If you are going to modify the XArray from interrupt or softirq context,
 264 you need to initialise the array using :c:func:`xa_init_flags`, passing
 265 ``XA_FLAGS_LOCK_IRQ`` or ``XA_FLAGS_LOCK_BH``.
 266
 267 The above example also shows a common pattern of wanting to extend the
 268 coverage of the xa_lock on the store side to protect some statistics
 269 associated with the array.
 270
 271 Sharing the XArray with interrupt context is also possible, either
 272 using :c:func:`xa_lock_irqsave` in both the interrupt handler and process
 273 context, or :c:func:`xa_lock_irq` in process context and :c:func:`xa_lock`
 274 in the interrupt handler.  Some of the more common patterns have helper
 275 functions such as :c:func:`xa_store_bh`, :c:func:`xa_store_irq`,
 276 :c:func:`xa_erase_bh`, :c:func:`xa_erase_irq`, :c:func:`xa_cmpxchg_bh`
 277 and :c:func:`xa_cmpxchg_irq`.
 278
 279 Sometimes you need to protect access to the XArray with a mutex because
 280 that lock sits above another mutex in the locking hierarchy.  That does
 281 not entitle you to use functions like :c:func:`__xa_erase` without taking
 282 the xa_lock; the xa_lock is used for lockdep validation and will be used
 283 for other purposes in the future.
 284
 285 The :c:func:`__xa_set_mark` and :c:func:`__xa_clear_mark` functions are also
 286 available for situations where you look up an entry and want to atomically
 287 set or clear a mark.  It may be more efficient to use the advanced API
 288 in this case, as it will save you from walking the tree twice.
 289
 290 Advanced API
 291 ============
 292
 293 The advanced API offers more flexibility and better performance at the
 294 cost of an interface which can be harder to use and has fewer safeguards.
 295 No locking is done for you by the advanced API, and you are required
 296 to use the xa_lock while modifying the array.  You can choose whether
 297 to use the xa_lock or the RCU lock while doing read-only operations on
 298 the array.  You can mix advanced and normal operations on the same array;
 299 indeed the normal API is implemented in terms of the advanced API.  The
 300 advanced API is only available to modules with a GPL-compatible license.
 301
 302 The advanced API is based around the xa_state.  This is an opaque data
 303 structure which you declare on the stack using the :c:func:`XA_STATE`
 304 macro.  This macro initialises the xa_state ready to start walking
 305 around the XArray.  It is used as a cursor to maintain the position
 306 in the XArray and let you compose various operations together without
 307 having to restart from the top every time.
 308
 309 The xa_state is also used to store errors.  You can call
 310 :c:func:`xas_error` to retrieve the error.  All operations check whether
 311 the xa_state is in an error state before proceeding, so there's no need
 312 for you to check for an error after each call; you can make multiple
 313 calls in succession and only check at a convenient point.  The only
 314 errors currently generated by the XArray code itself are ``ENOMEM`` and
 315 ``EINVAL``, but it supports arbitrary errors in case you want to call
 316 :c:func:`xas_set_err` yourself.
 317
 318 If the xa_state is holding an ``ENOMEM`` error, calling :c:func:`xas_nomem`
 319 will attempt to allocate more memory using the specified gfp flags and
 320 cache it in the xa_state for the next attempt.  The idea is that you take
 321 the xa_lock, attempt the operation and drop the lock.  The operation
 322 attempts to allocate memory while holding the lock, but it is more
 323 likely to fail.  Once you have dropped the lock, :c:func:`xas_nomem`
 324 can try harder to allocate more memory.  It will return ``true`` if it
 325 is worth retrying the operation (i.e. that there was a memory error *and*
 326 more memory was allocated).  If it has previously allocated memory, and
 327 that memory wasn't used, and there is no error (or some error that isn't
 328 ``ENOMEM``), then it will free the memory previously allocated.
 329
 330 Internal Entries
 331 ----------------
 332
 333 The XArray reserves some entries for its own purposes.  These are never
 334 exposed through the normal API, but when using the advanced API, it's
 335 possible to see them.  Usually the best way to handle them is to pass them
 336 to :c:func:`xas_retry`, and retry the operation if it returns ``true``.
 337
 338 .. flat-table::
 339    :widths: 1 1 6
 340
 341    * - Name
 342      - Test
 343      - Usage
 344
 345    * - Node
 346      - :c:func:`xa_is_node`
 347      - An XArray node.  May be visible when using a multi-index xa_state.
 348
 349    * - Sibling
 350      - :c:func:`xa_is_sibling`
 351      - A non-canonical entry for a multi-index entry.  The value indicates
 352        which slot in this node has the canonical entry.
 353
 354    * - Retry
 355      - :c:func:`xa_is_retry`
 356      - This entry is currently being modified by a thread which has the
 357        xa_lock.  The node containing this entry may be freed at the end
 358        of this RCU period.  You should restart the lookup from the head
 359        of the array.
 360
 361    * - Zero
 362      - :c:func:`xa_is_zero`
 363      - Zero entries appear as ``NULL`` through the Normal API, but occupy
 364        an entry in the XArray which can be used to reserve the index for
 365        future use.  This is used by allocating XArrays for allocated entries
 366        which are ``NULL``.
 367
 368 Other internal entries may be added in the future.  As far as possible, they
 369 will be handled by :c:func:`xas_retry`.
 370
 371 Additional functionality
 372 ------------------------
 373
 374 The :c:func:`xas_create_range` function allocates all the necessary memory
 375 to store every entry in a range.  It will set ENOMEM in the xa_state if
 376 it cannot allocate memory.
 377
 378 You can use :c:func:`xas_init_marks` to reset the marks on an entry
 379 to their default state.  This is usually all marks clear, unless the
 380 XArray is marked with ``XA_FLAGS_TRACK_FREE``, in which case mark 0 is set
 381 and all other marks are clear.  Replacing one entry with another using
 382 :c:func:`xas_store` will not reset the marks on that entry; if you want
 383 the marks reset, you should do that explicitly.
 384
 385 The :c:func:`xas_load` will walk the xa_state as close to the entry
 386 as it can.  If you know the xa_state has already been walked to the
 387 entry and need to check that the entry hasn't changed, you can use
 388 :c:func:`xas_reload` to save a function call.
 389
 390 If you need to move to a different index in the XArray, call
 391 :c:func:`xas_set`.  This resets the cursor to the top of the tree, which
 392 will generally make the next operation walk the cursor to the desired
 393 spot in the tree.  If you want to move to the next or previous index,
 394 call :c:func:`xas_next` or :c:func:`xas_prev`.  Setting the index does
 395 not walk the cursor around the array so does not require a lock to be
 396 held, while moving to the next or previous index does.
 397
 398 You can search for the next present entry using :c:func:`xas_find`.  This
 399 is the equivalent of both :c:func:`xa_find` and :c:func:`xa_find_after`;
 400 if the cursor has been walked to an entry, then it will find the next
 401 entry after the one currently referenced.  If not, it will return the
 402 entry at the index of the xa_state.  Using :c:func:`xas_next_entry` to
 403 move to the next present entry instead of :c:func:`xas_find` will save
 404 a function call in the majority of cases at the expense of emitting more
 405 inline code.
 406
 407 The :c:func:`xas_find_marked` function is similar.  If the xa_state has
 408 not been walked, it will return the entry at the index of the xa_state,
 409 if it is marked.  Otherwise, it will return the first marked entry after
 410 the entry referenced by the xa_state.  The :c:func:`xas_next_marked`
 411 function is the equivalent of :c:func:`xas_next_entry`.
 412
 413 When iterating over a range of the XArray using :c:func:`xas_for_each`
 414 or :c:func:`xas_for_each_marked`, it may be necessary to temporarily stop
 415 the iteration.  The :c:func:`xas_pause` function exists for this purpose.
 416 After you have done the necessary work and wish to resume, the xa_state
 417 is in an appropriate state to continue the iteration after the entry
 418 you last processed.  If you have interrupts disabled while iterating,
 419 then it is good manners to pause the iteration and reenable interrupts
 420 every ``XA_CHECK_SCHED`` entries.
 421
 422 The :c:func:`xas_get_mark`, :c:func:`xas_set_mark` and
 423 :c:func:`xas_clear_mark` functions require the xa_state cursor to have
 424 been moved to the appropriate location in the xarray; they will do
 425 nothing if you have called :c:func:`xas_pause` or :c:func:`xas_set`
 426 immediately before.
 427
 428 You can call :c:func:`xas_set_update` to have a callback function
 429 called each time the XArray updates a node.  This is used by the page
 430 cache workingset code to maintain its list of nodes which contain only
 431 shadow entries.
 432
 433 Multi-Index Entries
 434 -------------------
 435
 436 The XArray has the ability to tie multiple indices together so that
 437 operations on one index affect all indices.  For example, storing into
 438 any index will change the value of the entry retrieved from any index.
 439 Setting or clearing a mark on any index will set or clear the mark
 440 on every index that is tied together.  The current implementation
 441 only allows tying ranges which are aligned powers of two together;
 442 eg indices 64-127 may be tied together, but 2-6 may not be.  This may
 443 save substantial quantities of memory; for example tying 512 entries
 444 together will save over 4kB.
 445
 446 You can create a multi-index entry by using :c:func:`XA_STATE_ORDER`
 447 or :c:func:`xas_set_order` followed by a call to :c:func:`xas_store`.
 448 Calling :c:func:`xas_load` with a multi-index xa_state will walk the
 449 xa_state to the right location in the tree, but the return value is not
 450 meaningful, potentially being an internal entry or ``NULL`` even when there
 451 is an entry stored within the range.  Calling :c:func:`xas_find_conflict`
 452 will return the first entry within the range or ``NULL`` if there are no
 453 entries in the range.  The :c:func:`xas_for_each_conflict` iterator will
 454 iterate over every entry which overlaps the specified range.
 455
 456 If :c:func:`xas_load` encounters a multi-index entry, the xa_index
 457 in the xa_state will not be changed.  When iterating over an XArray
 458 or calling :c:func:`xas_find`, if the initial index is in the middle
 459 of a multi-index entry, it will not be altered.  Subsequent calls
 460 or iterations will move the index to the first index in the range.
 461 Each entry will only be returned once, no matter how many indices it
 462 occupies.
 463
 464 Using :c:func:`xas_next` or :c:func:`xas_prev` with a multi-index xa_state
 465 is not supported.  Using either of these functions on a multi-index entry
 466 will reveal sibling entries; these should be skipped over by the caller.
 467
 468 Storing ``NULL`` into any index of a multi-index entry will set the entry
 469 at every index to ``NULL`` and dissolve the tie.  Splitting a multi-index
 470 entry into entries occupying smaller ranges is not yet supported.
 471
 472 Functions and structures
 473 ========================
 474
 475 .. kernel-doc:: include/linux/xarray.h
 476 .. kernel-doc:: lib/xarray.c