1992a8e60SMatthew Wilcox.. SPDX-License-Identifier: GPL-2.0+ 2992a8e60SMatthew Wilcox 3992a8e60SMatthew Wilcox====== 4992a8e60SMatthew WilcoxXArray 5992a8e60SMatthew Wilcox====== 6992a8e60SMatthew Wilcox 7992a8e60SMatthew Wilcox:Author: Matthew Wilcox 8992a8e60SMatthew Wilcox 9992a8e60SMatthew WilcoxOverview 10992a8e60SMatthew Wilcox======== 11992a8e60SMatthew Wilcox 12992a8e60SMatthew WilcoxThe XArray is an abstract data type which behaves like a very large array 13992a8e60SMatthew Wilcoxof pointers. It meets many of the same needs as a hash or a conventional 14992a8e60SMatthew Wilcoxresizable array. Unlike a hash, it allows you to sensibly go to the 15992a8e60SMatthew Wilcoxnext or previous entry in a cache-efficient manner. In contrast to a 16992a8e60SMatthew Wilcoxresizable array, there is no need to copy data or change MMU mappings in 17992a8e60SMatthew Wilcoxorder to grow the array. It is more memory-efficient, parallelisable 18992a8e60SMatthew Wilcoxand cache friendly than a doubly-linked list. It takes advantage of 19992a8e60SMatthew WilcoxRCU to perform lookups without locking. 20992a8e60SMatthew Wilcox 21992a8e60SMatthew WilcoxThe XArray implementation is efficient when the indices used are densely 22992a8e60SMatthew Wilcoxclustered; hashing the object and using the hash as the index will not 23992a8e60SMatthew Wilcoxperform well. The XArray is optimised for small indices, but still has 24992a8e60SMatthew Wilcoxgood performance with large indices. If your index can be larger than 25992a8e60SMatthew Wilcox``ULONG_MAX`` then the XArray is not the data type for you. The most 26992a8e60SMatthew Wilcoximportant user of the XArray is the page cache. 27992a8e60SMatthew Wilcox 28992a8e60SMatthew WilcoxEach non-``NULL`` entry in the array has three bits associated with 29992a8e60SMatthew Wilcoxit called marks. Each mark may be set or cleared independently of 30992a8e60SMatthew Wilcoxthe others. You can iterate over entries which are marked. 31992a8e60SMatthew Wilcox 32992a8e60SMatthew WilcoxNormal pointers may be stored in the XArray directly. They must be 4-byte 33992a8e60SMatthew Wilcoxaligned, which is true for any pointer returned from :c:func:`kmalloc` and 34992a8e60SMatthew Wilcox:c:func:`alloc_page`. It isn't true for arbitrary user-space pointers, 35992a8e60SMatthew Wilcoxnor for function pointers. You can store pointers to statically allocated 36992a8e60SMatthew Wilcoxobjects, as long as those objects have an alignment of at least 4. 37992a8e60SMatthew Wilcox 38992a8e60SMatthew WilcoxYou can also store integers between 0 and ``LONG_MAX`` in the XArray. 39992a8e60SMatthew WilcoxYou must first convert it into an entry using :c:func:`xa_mk_value`. 40992a8e60SMatthew WilcoxWhen you retrieve an entry from the XArray, you can check whether it is 41992a8e60SMatthew Wilcoxa value entry by calling :c:func:`xa_is_value`, and convert it back to 42992a8e60SMatthew Wilcoxan integer by calling :c:func:`xa_to_value`. 43992a8e60SMatthew Wilcox 44992a8e60SMatthew WilcoxSome users want to store tagged pointers instead of using the marks 45992a8e60SMatthew Wilcoxdescribed above. They can call :c:func:`xa_tag_pointer` to create an 46992a8e60SMatthew Wilcoxentry with a tag, :c:func:`xa_untag_pointer` to turn a tagged entry 47992a8e60SMatthew Wilcoxback into an untagged pointer and :c:func:`xa_pointer_tag` to retrieve 48992a8e60SMatthew Wilcoxthe tag of an entry. Tagged pointers use the same bits that are used 49992a8e60SMatthew Wilcoxto distinguish value entries from normal pointers, so each user must 50992a8e60SMatthew Wilcoxdecide whether they want to store value entries or tagged pointers in 51992a8e60SMatthew Wilcoxany particular XArray. 52992a8e60SMatthew Wilcox 53992a8e60SMatthew WilcoxThe XArray does not support storing :c:func:`IS_ERR` pointers as some 54992a8e60SMatthew Wilcoxconflict with value entries or internal entries. 55992a8e60SMatthew Wilcox 56992a8e60SMatthew WilcoxAn unusual feature of the XArray is the ability to create entries which 57992a8e60SMatthew Wilcoxoccupy a range of indices. Once stored to, looking up any index in 58992a8e60SMatthew Wilcoxthe range will return the same entry as looking up any other index in 59992a8e60SMatthew Wilcoxthe range. Setting a mark on one index will set it on all of them. 60992a8e60SMatthew WilcoxStoring to any index will store to all of them. Multi-index entries can 61992a8e60SMatthew Wilcoxbe explicitly split into smaller entries, or storing ``NULL`` into any 62992a8e60SMatthew Wilcoxentry will cause the XArray to forget about the range. 63992a8e60SMatthew Wilcox 64992a8e60SMatthew WilcoxNormal API 65992a8e60SMatthew Wilcox========== 66992a8e60SMatthew Wilcox 67992a8e60SMatthew WilcoxStart by initialising an XArray, either with :c:func:`DEFINE_XARRAY` 68992a8e60SMatthew Wilcoxfor statically allocated XArrays or :c:func:`xa_init` for dynamically 69992a8e60SMatthew Wilcoxallocated ones. A freshly-initialised XArray contains a ``NULL`` 70992a8e60SMatthew Wilcoxpointer at every index. 71992a8e60SMatthew Wilcox 72992a8e60SMatthew WilcoxYou can then set entries using :c:func:`xa_store` and get entries 73992a8e60SMatthew Wilcoxusing :c:func:`xa_load`. xa_store will overwrite any entry with the 74992a8e60SMatthew Wilcoxnew entry and return the previous entry stored at that index. You can 75992a8e60SMatthew Wilcoxuse :c:func:`xa_erase` instead of calling :c:func:`xa_store` with a 76992a8e60SMatthew Wilcox``NULL`` entry. There is no difference between an entry that has never 77804dfaf0SMatthew Wilcoxbeen stored to, one that has been erased and one that has most recently 78804dfaf0SMatthew Wilcoxhad ``NULL`` stored to it. 79992a8e60SMatthew Wilcox 80992a8e60SMatthew WilcoxYou can conditionally replace an entry at an index by using 81992a8e60SMatthew Wilcox:c:func:`xa_cmpxchg`. Like :c:func:`cmpxchg`, it will only succeed if 82992a8e60SMatthew Wilcoxthe entry at that index has the 'old' value. It also returns the entry 83992a8e60SMatthew Wilcoxwhich was at that index; if it returns the same entry which was passed as 84992a8e60SMatthew Wilcox'old', then :c:func:`xa_cmpxchg` succeeded. 85992a8e60SMatthew Wilcox 86992a8e60SMatthew WilcoxIf you want to only store a new entry to an index if the current entry 87992a8e60SMatthew Wilcoxat that index is ``NULL``, you can use :c:func:`xa_insert` which 88992a8e60SMatthew Wilcoxreturns ``-EEXIST`` if the entry is not empty. 89992a8e60SMatthew Wilcox 90992a8e60SMatthew WilcoxYou can enquire whether a mark is set on an entry by using 91992a8e60SMatthew Wilcox:c:func:`xa_get_mark`. If the entry is not ``NULL``, you can set a mark 92992a8e60SMatthew Wilcoxon it by using :c:func:`xa_set_mark` and remove the mark from an entry by 93992a8e60SMatthew Wilcoxcalling :c:func:`xa_clear_mark`. You can ask whether any entry in the 94992a8e60SMatthew WilcoxXArray has a particular mark set by calling :c:func:`xa_marked`. 95992a8e60SMatthew Wilcox 96992a8e60SMatthew WilcoxYou can copy entries out of the XArray into a plain array by calling 97992a8e60SMatthew Wilcox:c:func:`xa_extract`. Or you can iterate over the present entries in 98992a8e60SMatthew Wilcoxthe XArray by calling :c:func:`xa_for_each`. You may prefer to use 99992a8e60SMatthew Wilcox:c:func:`xa_find` or :c:func:`xa_find_after` to move to the next present 100992a8e60SMatthew Wilcoxentry in the XArray. 101992a8e60SMatthew Wilcox 1020e9446c3SMatthew WilcoxCalling :c:func:`xa_store_range` stores the same entry in a range 1030e9446c3SMatthew Wilcoxof indices. If you do this, some of the other operations will behave 1040e9446c3SMatthew Wilcoxin a slightly odd way. For example, marking the entry at one index 1050e9446c3SMatthew Wilcoxmay result in the entry being marked at some, but not all of the other 1060e9446c3SMatthew Wilcoxindices. Storing into one index may result in the entry retrieved by 1070e9446c3SMatthew Wilcoxsome, but not all of the other indices changing. 1080e9446c3SMatthew Wilcox 1094c0608f4SMatthew WilcoxSometimes you need to ensure that a subsequent call to :c:func:`xa_store` 1104c0608f4SMatthew Wilcoxwill not need to allocate memory. The :c:func:`xa_reserve` function 111b0606fedSMatthew Wilcoxwill store a reserved entry at the indicated index. Users of the 112b0606fedSMatthew Wilcoxnormal API will see this entry as containing ``NULL``. If you do 113b0606fedSMatthew Wilcoxnot need to use the reserved entry, you can call :c:func:`xa_release` 114b0606fedSMatthew Wilcoxto remove the unused entry. If another user has stored to the entry 115b0606fedSMatthew Wilcoxin the meantime, :c:func:`xa_release` will do nothing; if instead you 116b0606fedSMatthew Wilcoxwant the entry to become ``NULL``, you should use :c:func:`xa_erase`. 117b0606fedSMatthew WilcoxUsing :c:func:`xa_insert` on a reserved entry will fail. 1184c0608f4SMatthew Wilcox 119804dfaf0SMatthew WilcoxIf all entries in the array are ``NULL``, the :c:func:`xa_empty` function 120804dfaf0SMatthew Wilcoxwill return ``true``. 121804dfaf0SMatthew Wilcox 122992a8e60SMatthew WilcoxFinally, you can remove all entries from an XArray by calling 123992a8e60SMatthew Wilcox:c:func:`xa_destroy`. If the XArray entries are pointers, you may wish 124992a8e60SMatthew Wilcoxto free the entries first. You can do this by iterating over all present 125992a8e60SMatthew Wilcoxentries in the XArray using the :c:func:`xa_for_each` iterator. 126992a8e60SMatthew Wilcox 127d9c48043SMatthew WilcoxAllocating XArrays 128d9c48043SMatthew Wilcox------------------ 129d9c48043SMatthew Wilcox 130d9c48043SMatthew WilcoxIf you use :c:func:`DEFINE_XARRAY_ALLOC` to define the XArray, or 131d9c48043SMatthew Wilcoxinitialise it by passing ``XA_FLAGS_ALLOC`` to :c:func:`xa_init_flags`, 132d9c48043SMatthew Wilcoxthe XArray changes to track whether entries are in use or not. 133371c752dSMatthew Wilcox 134371c752dSMatthew WilcoxYou can call :c:func:`xa_alloc` to store the entry at any unused index 135371c752dSMatthew Wilcoxin the XArray. If you need to modify the array from interrupt context, 136371c752dSMatthew Wilcoxyou can use :c:func:`xa_alloc_bh` or :c:func:`xa_alloc_irq` to disable 137d9c48043SMatthew Wilcoxinterrupts while allocating the ID. 138d9c48043SMatthew Wilcox 139d9c48043SMatthew WilcoxUsing :c:func:`xa_store`, :c:func:`xa_cmpxchg` or :c:func:`xa_insert` 140d9c48043SMatthew Wilcoxwill mark the entry as being allocated. Unlike a normal XArray, storing 141d9c48043SMatthew Wilcox``NULL`` will mark the entry as being in use, like :c:func:`xa_reserve`. 142d9c48043SMatthew WilcoxTo free an entry, use :c:func:`xa_erase` (or :c:func:`xa_release` if 143d9c48043SMatthew Wilcoxyou only want to free the entry if it's ``NULL``). 144d9c48043SMatthew Wilcox 145d9c48043SMatthew WilcoxYou cannot use ``XA_MARK_0`` with an allocating XArray as this mark 146d9c48043SMatthew Wilcoxis used to track whether an entry is free or not. The other marks are 147d9c48043SMatthew Wilcoxavailable for your use. 148371c752dSMatthew Wilcox 149992a8e60SMatthew WilcoxMemory allocation 150992a8e60SMatthew Wilcox----------------- 151992a8e60SMatthew Wilcox 152371c752dSMatthew WilcoxThe :c:func:`xa_store`, :c:func:`xa_cmpxchg`, :c:func:`xa_alloc`, 153371c752dSMatthew Wilcox:c:func:`xa_reserve` and :c:func:`xa_insert` functions take a gfp_t 154371c752dSMatthew Wilcoxparameter in case the XArray needs to allocate memory to store this entry. 155992a8e60SMatthew WilcoxIf the entry is being deleted, no memory allocation needs to be performed, 156992a8e60SMatthew Wilcoxand the GFP flags specified will be ignored. 157992a8e60SMatthew Wilcox 158992a8e60SMatthew WilcoxIt is possible for no memory to be allocatable, particularly if you pass 159992a8e60SMatthew Wilcoxa restrictive set of GFP flags. In that case, the functions return a 160992a8e60SMatthew Wilcoxspecial value which can be turned into an errno using :c:func:`xa_err`. 161992a8e60SMatthew WilcoxIf you don't need to know exactly which error occurred, using 162992a8e60SMatthew Wilcox:c:func:`xa_is_err` is slightly more efficient. 163992a8e60SMatthew Wilcox 164992a8e60SMatthew WilcoxLocking 165992a8e60SMatthew Wilcox------- 166992a8e60SMatthew Wilcox 167992a8e60SMatthew WilcoxWhen using the Normal API, you do not have to worry about locking. 168992a8e60SMatthew WilcoxThe XArray uses RCU and an internal spinlock to synchronise access: 169992a8e60SMatthew Wilcox 170992a8e60SMatthew WilcoxNo lock needed: 171992a8e60SMatthew Wilcox * :c:func:`xa_empty` 172992a8e60SMatthew Wilcox * :c:func:`xa_marked` 173992a8e60SMatthew Wilcox 174992a8e60SMatthew WilcoxTakes RCU read lock: 175992a8e60SMatthew Wilcox * :c:func:`xa_load` 176992a8e60SMatthew Wilcox * :c:func:`xa_for_each` 177992a8e60SMatthew Wilcox * :c:func:`xa_find` 178992a8e60SMatthew Wilcox * :c:func:`xa_find_after` 179992a8e60SMatthew Wilcox * :c:func:`xa_extract` 180992a8e60SMatthew Wilcox * :c:func:`xa_get_mark` 181992a8e60SMatthew Wilcox 182992a8e60SMatthew WilcoxTakes xa_lock internally: 183992a8e60SMatthew Wilcox * :c:func:`xa_store` 18484e5acb7SMatthew Wilcox * :c:func:`xa_store_bh` 18584e5acb7SMatthew Wilcox * :c:func:`xa_store_irq` 186992a8e60SMatthew Wilcox * :c:func:`xa_insert` 187b0606fedSMatthew Wilcox * :c:func:`xa_insert_bh` 188b0606fedSMatthew Wilcox * :c:func:`xa_insert_irq` 189992a8e60SMatthew Wilcox * :c:func:`xa_erase` 190992a8e60SMatthew Wilcox * :c:func:`xa_erase_bh` 191992a8e60SMatthew Wilcox * :c:func:`xa_erase_irq` 192992a8e60SMatthew Wilcox * :c:func:`xa_cmpxchg` 19355f3f7eaSMatthew Wilcox * :c:func:`xa_cmpxchg_bh` 19455f3f7eaSMatthew Wilcox * :c:func:`xa_cmpxchg_irq` 1950e9446c3SMatthew Wilcox * :c:func:`xa_store_range` 196371c752dSMatthew Wilcox * :c:func:`xa_alloc` 197371c752dSMatthew Wilcox * :c:func:`xa_alloc_bh` 198371c752dSMatthew Wilcox * :c:func:`xa_alloc_irq` 1994c0608f4SMatthew Wilcox * :c:func:`xa_reserve` 2004c0608f4SMatthew Wilcox * :c:func:`xa_reserve_bh` 2014c0608f4SMatthew Wilcox * :c:func:`xa_reserve_irq` 202992a8e60SMatthew Wilcox * :c:func:`xa_destroy` 203992a8e60SMatthew Wilcox * :c:func:`xa_set_mark` 204992a8e60SMatthew Wilcox * :c:func:`xa_clear_mark` 205992a8e60SMatthew Wilcox 206992a8e60SMatthew WilcoxAssumes xa_lock held on entry: 207992a8e60SMatthew Wilcox * :c:func:`__xa_store` 208992a8e60SMatthew Wilcox * :c:func:`__xa_insert` 209992a8e60SMatthew Wilcox * :c:func:`__xa_erase` 210992a8e60SMatthew Wilcox * :c:func:`__xa_cmpxchg` 211371c752dSMatthew Wilcox * :c:func:`__xa_alloc` 2124c0608f4SMatthew Wilcox * :c:func:`__xa_reserve` 213992a8e60SMatthew Wilcox * :c:func:`__xa_set_mark` 214992a8e60SMatthew Wilcox * :c:func:`__xa_clear_mark` 215992a8e60SMatthew Wilcox 216992a8e60SMatthew WilcoxIf you want to take advantage of the lock to protect the data structures 217992a8e60SMatthew Wilcoxthat you are storing in the XArray, you can call :c:func:`xa_lock` 218992a8e60SMatthew Wilcoxbefore calling :c:func:`xa_load`, then take a reference count on the 219992a8e60SMatthew Wilcoxobject you have found before calling :c:func:`xa_unlock`. This will 220992a8e60SMatthew Wilcoxprevent stores from removing the object from the array between looking 221992a8e60SMatthew Wilcoxup the object and incrementing the refcount. You can also use RCU to 222992a8e60SMatthew Wilcoxavoid dereferencing freed memory, but an explanation of that is beyond 223992a8e60SMatthew Wilcoxthe scope of this document. 224992a8e60SMatthew Wilcox 225992a8e60SMatthew WilcoxThe XArray does not disable interrupts or softirqs while modifying 226992a8e60SMatthew Wilcoxthe array. It is safe to read the XArray from interrupt or softirq 227992a8e60SMatthew Wilcoxcontext as the RCU lock provides enough protection. 228992a8e60SMatthew Wilcox 229992a8e60SMatthew WilcoxIf, for example, you want to store entries in the XArray in process 230992a8e60SMatthew Wilcoxcontext and then erase them in softirq context, you can do that this way:: 231992a8e60SMatthew Wilcox 232992a8e60SMatthew Wilcox void foo_init(struct foo *foo) 233992a8e60SMatthew Wilcox { 234992a8e60SMatthew Wilcox xa_init_flags(&foo->array, XA_FLAGS_LOCK_BH); 235992a8e60SMatthew Wilcox } 236992a8e60SMatthew Wilcox 237992a8e60SMatthew Wilcox int foo_store(struct foo *foo, unsigned long index, void *entry) 238992a8e60SMatthew Wilcox { 239992a8e60SMatthew Wilcox int err; 240992a8e60SMatthew Wilcox 241992a8e60SMatthew Wilcox xa_lock_bh(&foo->array); 242992a8e60SMatthew Wilcox err = xa_err(__xa_store(&foo->array, index, entry, GFP_KERNEL)); 243992a8e60SMatthew Wilcox if (!err) 244992a8e60SMatthew Wilcox foo->count++; 245992a8e60SMatthew Wilcox xa_unlock_bh(&foo->array); 246992a8e60SMatthew Wilcox return err; 247992a8e60SMatthew Wilcox } 248992a8e60SMatthew Wilcox 249992a8e60SMatthew Wilcox /* foo_erase() is only called from softirq context */ 250992a8e60SMatthew Wilcox void foo_erase(struct foo *foo, unsigned long index) 251992a8e60SMatthew Wilcox { 252992a8e60SMatthew Wilcox xa_lock(&foo->array); 253992a8e60SMatthew Wilcox __xa_erase(&foo->array, index); 254992a8e60SMatthew Wilcox foo->count--; 255992a8e60SMatthew Wilcox xa_unlock(&foo->array); 256992a8e60SMatthew Wilcox } 257992a8e60SMatthew Wilcox 258992a8e60SMatthew WilcoxIf you are going to modify the XArray from interrupt or softirq context, 259992a8e60SMatthew Wilcoxyou need to initialise the array using :c:func:`xa_init_flags`, passing 260992a8e60SMatthew Wilcox``XA_FLAGS_LOCK_IRQ`` or ``XA_FLAGS_LOCK_BH``. 261992a8e60SMatthew Wilcox 262992a8e60SMatthew WilcoxThe above example also shows a common pattern of wanting to extend the 263992a8e60SMatthew Wilcoxcoverage of the xa_lock on the store side to protect some statistics 264992a8e60SMatthew Wilcoxassociated with the array. 265992a8e60SMatthew Wilcox 266992a8e60SMatthew WilcoxSharing the XArray with interrupt context is also possible, either 267992a8e60SMatthew Wilcoxusing :c:func:`xa_lock_irqsave` in both the interrupt handler and process 268992a8e60SMatthew Wilcoxcontext, or :c:func:`xa_lock_irq` in process context and :c:func:`xa_lock` 269992a8e60SMatthew Wilcoxin the interrupt handler. Some of the more common patterns have helper 27084e5acb7SMatthew Wilcoxfunctions such as :c:func:`xa_store_bh`, :c:func:`xa_store_irq`, 27155f3f7eaSMatthew Wilcox:c:func:`xa_erase_bh`, :c:func:`xa_erase_irq`, :c:func:`xa_cmpxchg_bh` 27255f3f7eaSMatthew Wilcoxand :c:func:`xa_cmpxchg_irq`. 273992a8e60SMatthew Wilcox 274992a8e60SMatthew WilcoxSometimes you need to protect access to the XArray with a mutex because 275992a8e60SMatthew Wilcoxthat lock sits above another mutex in the locking hierarchy. That does 276992a8e60SMatthew Wilcoxnot entitle you to use functions like :c:func:`__xa_erase` without taking 277992a8e60SMatthew Wilcoxthe xa_lock; the xa_lock is used for lockdep validation and will be used 278992a8e60SMatthew Wilcoxfor other purposes in the future. 279992a8e60SMatthew Wilcox 280992a8e60SMatthew WilcoxThe :c:func:`__xa_set_mark` and :c:func:`__xa_clear_mark` functions are also 281992a8e60SMatthew Wilcoxavailable for situations where you look up an entry and want to atomically 282992a8e60SMatthew Wilcoxset or clear a mark. It may be more efficient to use the advanced API 283992a8e60SMatthew Wilcoxin this case, as it will save you from walking the tree twice. 284992a8e60SMatthew Wilcox 285992a8e60SMatthew WilcoxAdvanced API 286992a8e60SMatthew Wilcox============ 287992a8e60SMatthew Wilcox 288992a8e60SMatthew WilcoxThe advanced API offers more flexibility and better performance at the 289992a8e60SMatthew Wilcoxcost of an interface which can be harder to use and has fewer safeguards. 290992a8e60SMatthew WilcoxNo locking is done for you by the advanced API, and you are required 291992a8e60SMatthew Wilcoxto use the xa_lock while modifying the array. You can choose whether 292992a8e60SMatthew Wilcoxto use the xa_lock or the RCU lock while doing read-only operations on 293992a8e60SMatthew Wilcoxthe array. You can mix advanced and normal operations on the same array; 294992a8e60SMatthew Wilcoxindeed the normal API is implemented in terms of the advanced API. The 295992a8e60SMatthew Wilcoxadvanced API is only available to modules with a GPL-compatible license. 296992a8e60SMatthew Wilcox 297992a8e60SMatthew WilcoxThe advanced API is based around the xa_state. This is an opaque data 298992a8e60SMatthew Wilcoxstructure which you declare on the stack using the :c:func:`XA_STATE` 299992a8e60SMatthew Wilcoxmacro. This macro initialises the xa_state ready to start walking 300992a8e60SMatthew Wilcoxaround the XArray. It is used as a cursor to maintain the position 301992a8e60SMatthew Wilcoxin the XArray and let you compose various operations together without 302992a8e60SMatthew Wilcoxhaving to restart from the top every time. 303992a8e60SMatthew Wilcox 304992a8e60SMatthew WilcoxThe xa_state is also used to store errors. You can call 305992a8e60SMatthew Wilcox:c:func:`xas_error` to retrieve the error. All operations check whether 306992a8e60SMatthew Wilcoxthe xa_state is in an error state before proceeding, so there's no need 307992a8e60SMatthew Wilcoxfor you to check for an error after each call; you can make multiple 308992a8e60SMatthew Wilcoxcalls in succession and only check at a convenient point. The only 309992a8e60SMatthew Wilcoxerrors currently generated by the XArray code itself are ``ENOMEM`` and 310992a8e60SMatthew Wilcox``EINVAL``, but it supports arbitrary errors in case you want to call 311992a8e60SMatthew Wilcox:c:func:`xas_set_err` yourself. 312992a8e60SMatthew Wilcox 313992a8e60SMatthew WilcoxIf the xa_state is holding an ``ENOMEM`` error, calling :c:func:`xas_nomem` 314992a8e60SMatthew Wilcoxwill attempt to allocate more memory using the specified gfp flags and 315992a8e60SMatthew Wilcoxcache it in the xa_state for the next attempt. The idea is that you take 316992a8e60SMatthew Wilcoxthe xa_lock, attempt the operation and drop the lock. The operation 317992a8e60SMatthew Wilcoxattempts to allocate memory while holding the lock, but it is more 318992a8e60SMatthew Wilcoxlikely to fail. Once you have dropped the lock, :c:func:`xas_nomem` 319992a8e60SMatthew Wilcoxcan try harder to allocate more memory. It will return ``true`` if it 320992a8e60SMatthew Wilcoxis worth retrying the operation (i.e. that there was a memory error *and* 321992a8e60SMatthew Wilcoxmore memory was allocated). If it has previously allocated memory, and 322992a8e60SMatthew Wilcoxthat memory wasn't used, and there is no error (or some error that isn't 323992a8e60SMatthew Wilcox``ENOMEM``), then it will free the memory previously allocated. 324992a8e60SMatthew Wilcox 325992a8e60SMatthew WilcoxInternal Entries 326992a8e60SMatthew Wilcox---------------- 327992a8e60SMatthew Wilcox 328992a8e60SMatthew WilcoxThe XArray reserves some entries for its own purposes. These are never 329992a8e60SMatthew Wilcoxexposed through the normal API, but when using the advanced API, it's 330992a8e60SMatthew Wilcoxpossible to see them. Usually the best way to handle them is to pass them 331992a8e60SMatthew Wilcoxto :c:func:`xas_retry`, and retry the operation if it returns ``true``. 332992a8e60SMatthew Wilcox 333992a8e60SMatthew Wilcox.. flat-table:: 334992a8e60SMatthew Wilcox :widths: 1 1 6 335992a8e60SMatthew Wilcox 336992a8e60SMatthew Wilcox * - Name 337992a8e60SMatthew Wilcox - Test 338992a8e60SMatthew Wilcox - Usage 339992a8e60SMatthew Wilcox 340992a8e60SMatthew Wilcox * - Node 341992a8e60SMatthew Wilcox - :c:func:`xa_is_node` 342992a8e60SMatthew Wilcox - An XArray node. May be visible when using a multi-index xa_state. 343992a8e60SMatthew Wilcox 344992a8e60SMatthew Wilcox * - Sibling 345992a8e60SMatthew Wilcox - :c:func:`xa_is_sibling` 346992a8e60SMatthew Wilcox - A non-canonical entry for a multi-index entry. The value indicates 347992a8e60SMatthew Wilcox which slot in this node has the canonical entry. 348992a8e60SMatthew Wilcox 349992a8e60SMatthew Wilcox * - Retry 350992a8e60SMatthew Wilcox - :c:func:`xa_is_retry` 351992a8e60SMatthew Wilcox - This entry is currently being modified by a thread which has the 352992a8e60SMatthew Wilcox xa_lock. The node containing this entry may be freed at the end 353992a8e60SMatthew Wilcox of this RCU period. You should restart the lookup from the head 354992a8e60SMatthew Wilcox of the array. 355992a8e60SMatthew Wilcox 3569f14d4f1SMatthew Wilcox * - Zero 3579f14d4f1SMatthew Wilcox - :c:func:`xa_is_zero` 3589f14d4f1SMatthew Wilcox - Zero entries appear as ``NULL`` through the Normal API, but occupy 3599f14d4f1SMatthew Wilcox an entry in the XArray which can be used to reserve the index for 360d9c48043SMatthew Wilcox future use. This is used by allocating XArrays for allocated entries 361d9c48043SMatthew Wilcox which are ``NULL``. 3629f14d4f1SMatthew Wilcox 363992a8e60SMatthew WilcoxOther internal entries may be added in the future. As far as possible, they 364992a8e60SMatthew Wilcoxwill be handled by :c:func:`xas_retry`. 365992a8e60SMatthew Wilcox 366992a8e60SMatthew WilcoxAdditional functionality 367992a8e60SMatthew Wilcox------------------------ 368992a8e60SMatthew Wilcox 369992a8e60SMatthew WilcoxThe :c:func:`xas_create_range` function allocates all the necessary memory 370992a8e60SMatthew Wilcoxto store every entry in a range. It will set ENOMEM in the xa_state if 371992a8e60SMatthew Wilcoxit cannot allocate memory. 372992a8e60SMatthew Wilcox 373992a8e60SMatthew WilcoxYou can use :c:func:`xas_init_marks` to reset the marks on an entry 374992a8e60SMatthew Wilcoxto their default state. This is usually all marks clear, unless the 375992a8e60SMatthew WilcoxXArray is marked with ``XA_FLAGS_TRACK_FREE``, in which case mark 0 is set 376992a8e60SMatthew Wilcoxand all other marks are clear. Replacing one entry with another using 377992a8e60SMatthew Wilcox:c:func:`xas_store` will not reset the marks on that entry; if you want 378992a8e60SMatthew Wilcoxthe marks reset, you should do that explicitly. 379992a8e60SMatthew Wilcox 380992a8e60SMatthew WilcoxThe :c:func:`xas_load` will walk the xa_state as close to the entry 381992a8e60SMatthew Wilcoxas it can. If you know the xa_state has already been walked to the 382992a8e60SMatthew Wilcoxentry and need to check that the entry hasn't changed, you can use 383992a8e60SMatthew Wilcox:c:func:`xas_reload` to save a function call. 384992a8e60SMatthew Wilcox 385992a8e60SMatthew WilcoxIf you need to move to a different index in the XArray, call 386992a8e60SMatthew Wilcox:c:func:`xas_set`. This resets the cursor to the top of the tree, which 387992a8e60SMatthew Wilcoxwill generally make the next operation walk the cursor to the desired 388992a8e60SMatthew Wilcoxspot in the tree. If you want to move to the next or previous index, 389992a8e60SMatthew Wilcoxcall :c:func:`xas_next` or :c:func:`xas_prev`. Setting the index does 390992a8e60SMatthew Wilcoxnot walk the cursor around the array so does not require a lock to be 391992a8e60SMatthew Wilcoxheld, while moving to the next or previous index does. 392992a8e60SMatthew Wilcox 393992a8e60SMatthew WilcoxYou can search for the next present entry using :c:func:`xas_find`. This 394992a8e60SMatthew Wilcoxis the equivalent of both :c:func:`xa_find` and :c:func:`xa_find_after`; 395992a8e60SMatthew Wilcoxif the cursor has been walked to an entry, then it will find the next 396992a8e60SMatthew Wilcoxentry after the one currently referenced. If not, it will return the 397992a8e60SMatthew Wilcoxentry at the index of the xa_state. Using :c:func:`xas_next_entry` to 398992a8e60SMatthew Wilcoxmove to the next present entry instead of :c:func:`xas_find` will save 399992a8e60SMatthew Wilcoxa function call in the majority of cases at the expense of emitting more 400992a8e60SMatthew Wilcoxinline code. 401992a8e60SMatthew Wilcox 402992a8e60SMatthew WilcoxThe :c:func:`xas_find_marked` function is similar. If the xa_state has 403992a8e60SMatthew Wilcoxnot been walked, it will return the entry at the index of the xa_state, 404992a8e60SMatthew Wilcoxif it is marked. Otherwise, it will return the first marked entry after 405992a8e60SMatthew Wilcoxthe entry referenced by the xa_state. The :c:func:`xas_next_marked` 406992a8e60SMatthew Wilcoxfunction is the equivalent of :c:func:`xas_next_entry`. 407992a8e60SMatthew Wilcox 408992a8e60SMatthew WilcoxWhen iterating over a range of the XArray using :c:func:`xas_for_each` 409992a8e60SMatthew Wilcoxor :c:func:`xas_for_each_marked`, it may be necessary to temporarily stop 410992a8e60SMatthew Wilcoxthe iteration. The :c:func:`xas_pause` function exists for this purpose. 411992a8e60SMatthew WilcoxAfter you have done the necessary work and wish to resume, the xa_state 412992a8e60SMatthew Wilcoxis in an appropriate state to continue the iteration after the entry 413992a8e60SMatthew Wilcoxyou last processed. If you have interrupts disabled while iterating, 414992a8e60SMatthew Wilcoxthen it is good manners to pause the iteration and reenable interrupts 415992a8e60SMatthew Wilcoxevery ``XA_CHECK_SCHED`` entries. 416992a8e60SMatthew Wilcox 417992a8e60SMatthew WilcoxThe :c:func:`xas_get_mark`, :c:func:`xas_set_mark` and 418992a8e60SMatthew Wilcox:c:func:`xas_clear_mark` functions require the xa_state cursor to have 419992a8e60SMatthew Wilcoxbeen moved to the appropriate location in the xarray; they will do 420992a8e60SMatthew Wilcoxnothing if you have called :c:func:`xas_pause` or :c:func:`xas_set` 421992a8e60SMatthew Wilcoximmediately before. 422992a8e60SMatthew Wilcox 423992a8e60SMatthew WilcoxYou can call :c:func:`xas_set_update` to have a callback function 424992a8e60SMatthew Wilcoxcalled each time the XArray updates a node. This is used by the page 425992a8e60SMatthew Wilcoxcache workingset code to maintain its list of nodes which contain only 426992a8e60SMatthew Wilcoxshadow entries. 427992a8e60SMatthew Wilcox 428992a8e60SMatthew WilcoxMulti-Index Entries 429992a8e60SMatthew Wilcox------------------- 430992a8e60SMatthew Wilcox 431992a8e60SMatthew WilcoxThe XArray has the ability to tie multiple indices together so that 432992a8e60SMatthew Wilcoxoperations on one index affect all indices. For example, storing into 433992a8e60SMatthew Wilcoxany index will change the value of the entry retrieved from any index. 434992a8e60SMatthew WilcoxSetting or clearing a mark on any index will set or clear the mark 435992a8e60SMatthew Wilcoxon every index that is tied together. The current implementation 436992a8e60SMatthew Wilcoxonly allows tying ranges which are aligned powers of two together; 437992a8e60SMatthew Wilcoxeg indices 64-127 may be tied together, but 2-6 may not be. This may 438992a8e60SMatthew Wilcoxsave substantial quantities of memory; for example tying 512 entries 439992a8e60SMatthew Wilcoxtogether will save over 4kB. 440992a8e60SMatthew Wilcox 441992a8e60SMatthew WilcoxYou can create a multi-index entry by using :c:func:`XA_STATE_ORDER` 442992a8e60SMatthew Wilcoxor :c:func:`xas_set_order` followed by a call to :c:func:`xas_store`. 443992a8e60SMatthew WilcoxCalling :c:func:`xas_load` with a multi-index xa_state will walk the 444992a8e60SMatthew Wilcoxxa_state to the right location in the tree, but the return value is not 445992a8e60SMatthew Wilcoxmeaningful, potentially being an internal entry or ``NULL`` even when there 446992a8e60SMatthew Wilcoxis an entry stored within the range. Calling :c:func:`xas_find_conflict` 447992a8e60SMatthew Wilcoxwill return the first entry within the range or ``NULL`` if there are no 448992a8e60SMatthew Wilcoxentries in the range. The :c:func:`xas_for_each_conflict` iterator will 449992a8e60SMatthew Wilcoxiterate over every entry which overlaps the specified range. 450992a8e60SMatthew Wilcox 451992a8e60SMatthew WilcoxIf :c:func:`xas_load` encounters a multi-index entry, the xa_index 452992a8e60SMatthew Wilcoxin the xa_state will not be changed. When iterating over an XArray 453992a8e60SMatthew Wilcoxor calling :c:func:`xas_find`, if the initial index is in the middle 454992a8e60SMatthew Wilcoxof a multi-index entry, it will not be altered. Subsequent calls 455992a8e60SMatthew Wilcoxor iterations will move the index to the first index in the range. 456992a8e60SMatthew WilcoxEach entry will only be returned once, no matter how many indices it 457992a8e60SMatthew Wilcoxoccupies. 458992a8e60SMatthew Wilcox 459992a8e60SMatthew WilcoxUsing :c:func:`xas_next` or :c:func:`xas_prev` with a multi-index xa_state 460992a8e60SMatthew Wilcoxis not supported. Using either of these functions on a multi-index entry 461992a8e60SMatthew Wilcoxwill reveal sibling entries; these should be skipped over by the caller. 462992a8e60SMatthew Wilcox 463992a8e60SMatthew WilcoxStoring ``NULL`` into any index of a multi-index entry will set the entry 464992a8e60SMatthew Wilcoxat every index to ``NULL`` and dissolve the tie. Splitting a multi-index 465992a8e60SMatthew Wilcoxentry into entries occupying smaller ranges is not yet supported. 466992a8e60SMatthew Wilcox 467992a8e60SMatthew WilcoxFunctions and structures 468992a8e60SMatthew Wilcox======================== 469992a8e60SMatthew Wilcox 470992a8e60SMatthew Wilcox.. kernel-doc:: include/linux/xarray.h 471992a8e60SMatthew Wilcox.. kernel-doc:: lib/xarray.c 472