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