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 1114c0608f4SMatthew Wilcoxwill store a reserved entry at the indicated index. Users of the normal 1124c0608f4SMatthew WilcoxAPI will see this entry as containing ``NULL``. If you do not need to 1134c0608f4SMatthew Wilcoxuse the reserved entry, you can call :c:func:`xa_release` to remove the 1144c0608f4SMatthew Wilcoxunused entry. If another user has stored to the entry in the meantime, 1154c0608f4SMatthew Wilcox:c:func:`xa_release` will do nothing; if instead you want the entry to 1164c0608f4SMatthew Wilcoxbecome ``NULL``, you should use :c:func:`xa_erase`. 1174c0608f4SMatthew Wilcox 118804dfaf0SMatthew WilcoxIf all entries in the array are ``NULL``, the :c:func:`xa_empty` function 119804dfaf0SMatthew Wilcoxwill return ``true``. 120804dfaf0SMatthew Wilcox 121992a8e60SMatthew WilcoxFinally, you can remove all entries from an XArray by calling 122992a8e60SMatthew Wilcox:c:func:`xa_destroy`. If the XArray entries are pointers, you may wish 123992a8e60SMatthew Wilcoxto free the entries first. You can do this by iterating over all present 124992a8e60SMatthew Wilcoxentries in the XArray using the :c:func:`xa_for_each` iterator. 125992a8e60SMatthew Wilcox 126d9c48043SMatthew WilcoxAllocating XArrays 127d9c48043SMatthew Wilcox------------------ 128d9c48043SMatthew Wilcox 129d9c48043SMatthew WilcoxIf you use :c:func:`DEFINE_XARRAY_ALLOC` to define the XArray, or 130d9c48043SMatthew Wilcoxinitialise it by passing ``XA_FLAGS_ALLOC`` to :c:func:`xa_init_flags`, 131d9c48043SMatthew Wilcoxthe XArray changes to track whether entries are in use or not. 132371c752dSMatthew Wilcox 133371c752dSMatthew WilcoxYou can call :c:func:`xa_alloc` to store the entry at any unused index 134371c752dSMatthew Wilcoxin the XArray. If you need to modify the array from interrupt context, 135371c752dSMatthew Wilcoxyou can use :c:func:`xa_alloc_bh` or :c:func:`xa_alloc_irq` to disable 136d9c48043SMatthew Wilcoxinterrupts while allocating the ID. 137d9c48043SMatthew Wilcox 138d9c48043SMatthew WilcoxUsing :c:func:`xa_store`, :c:func:`xa_cmpxchg` or :c:func:`xa_insert` 139d9c48043SMatthew Wilcoxwill mark the entry as being allocated. Unlike a normal XArray, storing 140d9c48043SMatthew Wilcox``NULL`` will mark the entry as being in use, like :c:func:`xa_reserve`. 141d9c48043SMatthew WilcoxTo free an entry, use :c:func:`xa_erase` (or :c:func:`xa_release` if 142d9c48043SMatthew Wilcoxyou only want to free the entry if it's ``NULL``). 143d9c48043SMatthew Wilcox 144d9c48043SMatthew WilcoxYou cannot use ``XA_MARK_0`` with an allocating XArray as this mark 145d9c48043SMatthew Wilcoxis used to track whether an entry is free or not. The other marks are 146d9c48043SMatthew Wilcoxavailable for your use. 147371c752dSMatthew Wilcox 148992a8e60SMatthew WilcoxMemory allocation 149992a8e60SMatthew Wilcox----------------- 150992a8e60SMatthew Wilcox 151371c752dSMatthew WilcoxThe :c:func:`xa_store`, :c:func:`xa_cmpxchg`, :c:func:`xa_alloc`, 152371c752dSMatthew Wilcox:c:func:`xa_reserve` and :c:func:`xa_insert` functions take a gfp_t 153371c752dSMatthew Wilcoxparameter in case the XArray needs to allocate memory to store this entry. 154992a8e60SMatthew WilcoxIf the entry is being deleted, no memory allocation needs to be performed, 155992a8e60SMatthew Wilcoxand the GFP flags specified will be ignored. 156992a8e60SMatthew Wilcox 157992a8e60SMatthew WilcoxIt is possible for no memory to be allocatable, particularly if you pass 158992a8e60SMatthew Wilcoxa restrictive set of GFP flags. In that case, the functions return a 159992a8e60SMatthew Wilcoxspecial value which can be turned into an errno using :c:func:`xa_err`. 160992a8e60SMatthew WilcoxIf you don't need to know exactly which error occurred, using 161992a8e60SMatthew Wilcox:c:func:`xa_is_err` is slightly more efficient. 162992a8e60SMatthew Wilcox 163992a8e60SMatthew WilcoxLocking 164992a8e60SMatthew Wilcox------- 165992a8e60SMatthew Wilcox 166992a8e60SMatthew WilcoxWhen using the Normal API, you do not have to worry about locking. 167992a8e60SMatthew WilcoxThe XArray uses RCU and an internal spinlock to synchronise access: 168992a8e60SMatthew Wilcox 169992a8e60SMatthew WilcoxNo lock needed: 170992a8e60SMatthew Wilcox * :c:func:`xa_empty` 171992a8e60SMatthew Wilcox * :c:func:`xa_marked` 172992a8e60SMatthew Wilcox 173992a8e60SMatthew WilcoxTakes RCU read lock: 174992a8e60SMatthew Wilcox * :c:func:`xa_load` 175992a8e60SMatthew Wilcox * :c:func:`xa_for_each` 176992a8e60SMatthew Wilcox * :c:func:`xa_find` 177992a8e60SMatthew Wilcox * :c:func:`xa_find_after` 178992a8e60SMatthew Wilcox * :c:func:`xa_extract` 179992a8e60SMatthew Wilcox * :c:func:`xa_get_mark` 180992a8e60SMatthew Wilcox 181992a8e60SMatthew WilcoxTakes xa_lock internally: 182992a8e60SMatthew Wilcox * :c:func:`xa_store` 18384e5acb7SMatthew Wilcox * :c:func:`xa_store_bh` 18484e5acb7SMatthew Wilcox * :c:func:`xa_store_irq` 185992a8e60SMatthew Wilcox * :c:func:`xa_insert` 186992a8e60SMatthew Wilcox * :c:func:`xa_erase` 187992a8e60SMatthew Wilcox * :c:func:`xa_erase_bh` 188992a8e60SMatthew Wilcox * :c:func:`xa_erase_irq` 189992a8e60SMatthew Wilcox * :c:func:`xa_cmpxchg` 19055f3f7eaSMatthew Wilcox * :c:func:`xa_cmpxchg_bh` 19155f3f7eaSMatthew Wilcox * :c:func:`xa_cmpxchg_irq` 1920e9446c3SMatthew Wilcox * :c:func:`xa_store_range` 193371c752dSMatthew Wilcox * :c:func:`xa_alloc` 194371c752dSMatthew Wilcox * :c:func:`xa_alloc_bh` 195371c752dSMatthew Wilcox * :c:func:`xa_alloc_irq` 1964c0608f4SMatthew Wilcox * :c:func:`xa_reserve` 1974c0608f4SMatthew Wilcox * :c:func:`xa_reserve_bh` 1984c0608f4SMatthew Wilcox * :c:func:`xa_reserve_irq` 199992a8e60SMatthew Wilcox * :c:func:`xa_destroy` 200992a8e60SMatthew Wilcox * :c:func:`xa_set_mark` 201992a8e60SMatthew Wilcox * :c:func:`xa_clear_mark` 202992a8e60SMatthew Wilcox 203992a8e60SMatthew WilcoxAssumes xa_lock held on entry: 204992a8e60SMatthew Wilcox * :c:func:`__xa_store` 205992a8e60SMatthew Wilcox * :c:func:`__xa_insert` 206992a8e60SMatthew Wilcox * :c:func:`__xa_erase` 207992a8e60SMatthew Wilcox * :c:func:`__xa_cmpxchg` 208371c752dSMatthew Wilcox * :c:func:`__xa_alloc` 2094c0608f4SMatthew Wilcox * :c:func:`__xa_reserve` 210992a8e60SMatthew Wilcox * :c:func:`__xa_set_mark` 211992a8e60SMatthew Wilcox * :c:func:`__xa_clear_mark` 212992a8e60SMatthew Wilcox 213992a8e60SMatthew WilcoxIf you want to take advantage of the lock to protect the data structures 214992a8e60SMatthew Wilcoxthat you are storing in the XArray, you can call :c:func:`xa_lock` 215992a8e60SMatthew Wilcoxbefore calling :c:func:`xa_load`, then take a reference count on the 216992a8e60SMatthew Wilcoxobject you have found before calling :c:func:`xa_unlock`. This will 217992a8e60SMatthew Wilcoxprevent stores from removing the object from the array between looking 218992a8e60SMatthew Wilcoxup the object and incrementing the refcount. You can also use RCU to 219992a8e60SMatthew Wilcoxavoid dereferencing freed memory, but an explanation of that is beyond 220992a8e60SMatthew Wilcoxthe scope of this document. 221992a8e60SMatthew Wilcox 222992a8e60SMatthew WilcoxThe XArray does not disable interrupts or softirqs while modifying 223992a8e60SMatthew Wilcoxthe array. It is safe to read the XArray from interrupt or softirq 224992a8e60SMatthew Wilcoxcontext as the RCU lock provides enough protection. 225992a8e60SMatthew Wilcox 226992a8e60SMatthew WilcoxIf, for example, you want to store entries in the XArray in process 227992a8e60SMatthew Wilcoxcontext and then erase them in softirq context, you can do that this way:: 228992a8e60SMatthew Wilcox 229992a8e60SMatthew Wilcox void foo_init(struct foo *foo) 230992a8e60SMatthew Wilcox { 231992a8e60SMatthew Wilcox xa_init_flags(&foo->array, XA_FLAGS_LOCK_BH); 232992a8e60SMatthew Wilcox } 233992a8e60SMatthew Wilcox 234992a8e60SMatthew Wilcox int foo_store(struct foo *foo, unsigned long index, void *entry) 235992a8e60SMatthew Wilcox { 236992a8e60SMatthew Wilcox int err; 237992a8e60SMatthew Wilcox 238992a8e60SMatthew Wilcox xa_lock_bh(&foo->array); 239992a8e60SMatthew Wilcox err = xa_err(__xa_store(&foo->array, index, entry, GFP_KERNEL)); 240992a8e60SMatthew Wilcox if (!err) 241992a8e60SMatthew Wilcox foo->count++; 242992a8e60SMatthew Wilcox xa_unlock_bh(&foo->array); 243992a8e60SMatthew Wilcox return err; 244992a8e60SMatthew Wilcox } 245992a8e60SMatthew Wilcox 246992a8e60SMatthew Wilcox /* foo_erase() is only called from softirq context */ 247992a8e60SMatthew Wilcox void foo_erase(struct foo *foo, unsigned long index) 248992a8e60SMatthew Wilcox { 249992a8e60SMatthew Wilcox xa_lock(&foo->array); 250992a8e60SMatthew Wilcox __xa_erase(&foo->array, index); 251992a8e60SMatthew Wilcox foo->count--; 252992a8e60SMatthew Wilcox xa_unlock(&foo->array); 253992a8e60SMatthew Wilcox } 254992a8e60SMatthew Wilcox 255992a8e60SMatthew WilcoxIf you are going to modify the XArray from interrupt or softirq context, 256992a8e60SMatthew Wilcoxyou need to initialise the array using :c:func:`xa_init_flags`, passing 257992a8e60SMatthew Wilcox``XA_FLAGS_LOCK_IRQ`` or ``XA_FLAGS_LOCK_BH``. 258992a8e60SMatthew Wilcox 259992a8e60SMatthew WilcoxThe above example also shows a common pattern of wanting to extend the 260992a8e60SMatthew Wilcoxcoverage of the xa_lock on the store side to protect some statistics 261992a8e60SMatthew Wilcoxassociated with the array. 262992a8e60SMatthew Wilcox 263992a8e60SMatthew WilcoxSharing the XArray with interrupt context is also possible, either 264992a8e60SMatthew Wilcoxusing :c:func:`xa_lock_irqsave` in both the interrupt handler and process 265992a8e60SMatthew Wilcoxcontext, or :c:func:`xa_lock_irq` in process context and :c:func:`xa_lock` 266992a8e60SMatthew Wilcoxin the interrupt handler. Some of the more common patterns have helper 26784e5acb7SMatthew Wilcoxfunctions such as :c:func:`xa_store_bh`, :c:func:`xa_store_irq`, 26855f3f7eaSMatthew Wilcox:c:func:`xa_erase_bh`, :c:func:`xa_erase_irq`, :c:func:`xa_cmpxchg_bh` 26955f3f7eaSMatthew Wilcoxand :c:func:`xa_cmpxchg_irq`. 270992a8e60SMatthew Wilcox 271992a8e60SMatthew WilcoxSometimes you need to protect access to the XArray with a mutex because 272992a8e60SMatthew Wilcoxthat lock sits above another mutex in the locking hierarchy. That does 273992a8e60SMatthew Wilcoxnot entitle you to use functions like :c:func:`__xa_erase` without taking 274992a8e60SMatthew Wilcoxthe xa_lock; the xa_lock is used for lockdep validation and will be used 275992a8e60SMatthew Wilcoxfor other purposes in the future. 276992a8e60SMatthew Wilcox 277992a8e60SMatthew WilcoxThe :c:func:`__xa_set_mark` and :c:func:`__xa_clear_mark` functions are also 278992a8e60SMatthew Wilcoxavailable for situations where you look up an entry and want to atomically 279992a8e60SMatthew Wilcoxset or clear a mark. It may be more efficient to use the advanced API 280992a8e60SMatthew Wilcoxin this case, as it will save you from walking the tree twice. 281992a8e60SMatthew Wilcox 282992a8e60SMatthew WilcoxAdvanced API 283992a8e60SMatthew Wilcox============ 284992a8e60SMatthew Wilcox 285992a8e60SMatthew WilcoxThe advanced API offers more flexibility and better performance at the 286992a8e60SMatthew Wilcoxcost of an interface which can be harder to use and has fewer safeguards. 287992a8e60SMatthew WilcoxNo locking is done for you by the advanced API, and you are required 288992a8e60SMatthew Wilcoxto use the xa_lock while modifying the array. You can choose whether 289992a8e60SMatthew Wilcoxto use the xa_lock or the RCU lock while doing read-only operations on 290992a8e60SMatthew Wilcoxthe array. You can mix advanced and normal operations on the same array; 291992a8e60SMatthew Wilcoxindeed the normal API is implemented in terms of the advanced API. The 292992a8e60SMatthew Wilcoxadvanced API is only available to modules with a GPL-compatible license. 293992a8e60SMatthew Wilcox 294992a8e60SMatthew WilcoxThe advanced API is based around the xa_state. This is an opaque data 295992a8e60SMatthew Wilcoxstructure which you declare on the stack using the :c:func:`XA_STATE` 296992a8e60SMatthew Wilcoxmacro. This macro initialises the xa_state ready to start walking 297992a8e60SMatthew Wilcoxaround the XArray. It is used as a cursor to maintain the position 298992a8e60SMatthew Wilcoxin the XArray and let you compose various operations together without 299992a8e60SMatthew Wilcoxhaving to restart from the top every time. 300992a8e60SMatthew Wilcox 301992a8e60SMatthew WilcoxThe xa_state is also used to store errors. You can call 302992a8e60SMatthew Wilcox:c:func:`xas_error` to retrieve the error. All operations check whether 303992a8e60SMatthew Wilcoxthe xa_state is in an error state before proceeding, so there's no need 304992a8e60SMatthew Wilcoxfor you to check for an error after each call; you can make multiple 305992a8e60SMatthew Wilcoxcalls in succession and only check at a convenient point. The only 306992a8e60SMatthew Wilcoxerrors currently generated by the XArray code itself are ``ENOMEM`` and 307992a8e60SMatthew Wilcox``EINVAL``, but it supports arbitrary errors in case you want to call 308992a8e60SMatthew Wilcox:c:func:`xas_set_err` yourself. 309992a8e60SMatthew Wilcox 310992a8e60SMatthew WilcoxIf the xa_state is holding an ``ENOMEM`` error, calling :c:func:`xas_nomem` 311992a8e60SMatthew Wilcoxwill attempt to allocate more memory using the specified gfp flags and 312992a8e60SMatthew Wilcoxcache it in the xa_state for the next attempt. The idea is that you take 313992a8e60SMatthew Wilcoxthe xa_lock, attempt the operation and drop the lock. The operation 314992a8e60SMatthew Wilcoxattempts to allocate memory while holding the lock, but it is more 315992a8e60SMatthew Wilcoxlikely to fail. Once you have dropped the lock, :c:func:`xas_nomem` 316992a8e60SMatthew Wilcoxcan try harder to allocate more memory. It will return ``true`` if it 317992a8e60SMatthew Wilcoxis worth retrying the operation (i.e. that there was a memory error *and* 318992a8e60SMatthew Wilcoxmore memory was allocated). If it has previously allocated memory, and 319992a8e60SMatthew Wilcoxthat memory wasn't used, and there is no error (or some error that isn't 320992a8e60SMatthew Wilcox``ENOMEM``), then it will free the memory previously allocated. 321992a8e60SMatthew Wilcox 322992a8e60SMatthew WilcoxInternal Entries 323992a8e60SMatthew Wilcox---------------- 324992a8e60SMatthew Wilcox 325992a8e60SMatthew WilcoxThe XArray reserves some entries for its own purposes. These are never 326992a8e60SMatthew Wilcoxexposed through the normal API, but when using the advanced API, it's 327992a8e60SMatthew Wilcoxpossible to see them. Usually the best way to handle them is to pass them 328992a8e60SMatthew Wilcoxto :c:func:`xas_retry`, and retry the operation if it returns ``true``. 329992a8e60SMatthew Wilcox 330992a8e60SMatthew Wilcox.. flat-table:: 331992a8e60SMatthew Wilcox :widths: 1 1 6 332992a8e60SMatthew Wilcox 333992a8e60SMatthew Wilcox * - Name 334992a8e60SMatthew Wilcox - Test 335992a8e60SMatthew Wilcox - Usage 336992a8e60SMatthew Wilcox 337992a8e60SMatthew Wilcox * - Node 338992a8e60SMatthew Wilcox - :c:func:`xa_is_node` 339992a8e60SMatthew Wilcox - An XArray node. May be visible when using a multi-index xa_state. 340992a8e60SMatthew Wilcox 341992a8e60SMatthew Wilcox * - Sibling 342992a8e60SMatthew Wilcox - :c:func:`xa_is_sibling` 343992a8e60SMatthew Wilcox - A non-canonical entry for a multi-index entry. The value indicates 344992a8e60SMatthew Wilcox which slot in this node has the canonical entry. 345992a8e60SMatthew Wilcox 346992a8e60SMatthew Wilcox * - Retry 347992a8e60SMatthew Wilcox - :c:func:`xa_is_retry` 348992a8e60SMatthew Wilcox - This entry is currently being modified by a thread which has the 349992a8e60SMatthew Wilcox xa_lock. The node containing this entry may be freed at the end 350992a8e60SMatthew Wilcox of this RCU period. You should restart the lookup from the head 351992a8e60SMatthew Wilcox of the array. 352992a8e60SMatthew Wilcox 3539f14d4f1SMatthew Wilcox * - Zero 3549f14d4f1SMatthew Wilcox - :c:func:`xa_is_zero` 3559f14d4f1SMatthew Wilcox - Zero entries appear as ``NULL`` through the Normal API, but occupy 3569f14d4f1SMatthew Wilcox an entry in the XArray which can be used to reserve the index for 357d9c48043SMatthew Wilcox future use. This is used by allocating XArrays for allocated entries 358d9c48043SMatthew Wilcox which are ``NULL``. 3599f14d4f1SMatthew Wilcox 360992a8e60SMatthew WilcoxOther internal entries may be added in the future. As far as possible, they 361992a8e60SMatthew Wilcoxwill be handled by :c:func:`xas_retry`. 362992a8e60SMatthew Wilcox 363992a8e60SMatthew WilcoxAdditional functionality 364992a8e60SMatthew Wilcox------------------------ 365992a8e60SMatthew Wilcox 366992a8e60SMatthew WilcoxThe :c:func:`xas_create_range` function allocates all the necessary memory 367992a8e60SMatthew Wilcoxto store every entry in a range. It will set ENOMEM in the xa_state if 368992a8e60SMatthew Wilcoxit cannot allocate memory. 369992a8e60SMatthew Wilcox 370992a8e60SMatthew WilcoxYou can use :c:func:`xas_init_marks` to reset the marks on an entry 371992a8e60SMatthew Wilcoxto their default state. This is usually all marks clear, unless the 372992a8e60SMatthew WilcoxXArray is marked with ``XA_FLAGS_TRACK_FREE``, in which case mark 0 is set 373992a8e60SMatthew Wilcoxand all other marks are clear. Replacing one entry with another using 374992a8e60SMatthew Wilcox:c:func:`xas_store` will not reset the marks on that entry; if you want 375992a8e60SMatthew Wilcoxthe marks reset, you should do that explicitly. 376992a8e60SMatthew Wilcox 377992a8e60SMatthew WilcoxThe :c:func:`xas_load` will walk the xa_state as close to the entry 378992a8e60SMatthew Wilcoxas it can. If you know the xa_state has already been walked to the 379992a8e60SMatthew Wilcoxentry and need to check that the entry hasn't changed, you can use 380992a8e60SMatthew Wilcox:c:func:`xas_reload` to save a function call. 381992a8e60SMatthew Wilcox 382992a8e60SMatthew WilcoxIf you need to move to a different index in the XArray, call 383992a8e60SMatthew Wilcox:c:func:`xas_set`. This resets the cursor to the top of the tree, which 384992a8e60SMatthew Wilcoxwill generally make the next operation walk the cursor to the desired 385992a8e60SMatthew Wilcoxspot in the tree. If you want to move to the next or previous index, 386992a8e60SMatthew Wilcoxcall :c:func:`xas_next` or :c:func:`xas_prev`. Setting the index does 387992a8e60SMatthew Wilcoxnot walk the cursor around the array so does not require a lock to be 388992a8e60SMatthew Wilcoxheld, while moving to the next or previous index does. 389992a8e60SMatthew Wilcox 390992a8e60SMatthew WilcoxYou can search for the next present entry using :c:func:`xas_find`. This 391992a8e60SMatthew Wilcoxis the equivalent of both :c:func:`xa_find` and :c:func:`xa_find_after`; 392992a8e60SMatthew Wilcoxif the cursor has been walked to an entry, then it will find the next 393992a8e60SMatthew Wilcoxentry after the one currently referenced. If not, it will return the 394992a8e60SMatthew Wilcoxentry at the index of the xa_state. Using :c:func:`xas_next_entry` to 395992a8e60SMatthew Wilcoxmove to the next present entry instead of :c:func:`xas_find` will save 396992a8e60SMatthew Wilcoxa function call in the majority of cases at the expense of emitting more 397992a8e60SMatthew Wilcoxinline code. 398992a8e60SMatthew Wilcox 399992a8e60SMatthew WilcoxThe :c:func:`xas_find_marked` function is similar. If the xa_state has 400992a8e60SMatthew Wilcoxnot been walked, it will return the entry at the index of the xa_state, 401992a8e60SMatthew Wilcoxif it is marked. Otherwise, it will return the first marked entry after 402992a8e60SMatthew Wilcoxthe entry referenced by the xa_state. The :c:func:`xas_next_marked` 403992a8e60SMatthew Wilcoxfunction is the equivalent of :c:func:`xas_next_entry`. 404992a8e60SMatthew Wilcox 405992a8e60SMatthew WilcoxWhen iterating over a range of the XArray using :c:func:`xas_for_each` 406992a8e60SMatthew Wilcoxor :c:func:`xas_for_each_marked`, it may be necessary to temporarily stop 407992a8e60SMatthew Wilcoxthe iteration. The :c:func:`xas_pause` function exists for this purpose. 408992a8e60SMatthew WilcoxAfter you have done the necessary work and wish to resume, the xa_state 409992a8e60SMatthew Wilcoxis in an appropriate state to continue the iteration after the entry 410992a8e60SMatthew Wilcoxyou last processed. If you have interrupts disabled while iterating, 411992a8e60SMatthew Wilcoxthen it is good manners to pause the iteration and reenable interrupts 412992a8e60SMatthew Wilcoxevery ``XA_CHECK_SCHED`` entries. 413992a8e60SMatthew Wilcox 414992a8e60SMatthew WilcoxThe :c:func:`xas_get_mark`, :c:func:`xas_set_mark` and 415992a8e60SMatthew Wilcox:c:func:`xas_clear_mark` functions require the xa_state cursor to have 416992a8e60SMatthew Wilcoxbeen moved to the appropriate location in the xarray; they will do 417992a8e60SMatthew Wilcoxnothing if you have called :c:func:`xas_pause` or :c:func:`xas_set` 418992a8e60SMatthew Wilcoximmediately before. 419992a8e60SMatthew Wilcox 420992a8e60SMatthew WilcoxYou can call :c:func:`xas_set_update` to have a callback function 421992a8e60SMatthew Wilcoxcalled each time the XArray updates a node. This is used by the page 422992a8e60SMatthew Wilcoxcache workingset code to maintain its list of nodes which contain only 423992a8e60SMatthew Wilcoxshadow entries. 424992a8e60SMatthew Wilcox 425992a8e60SMatthew WilcoxMulti-Index Entries 426992a8e60SMatthew Wilcox------------------- 427992a8e60SMatthew Wilcox 428992a8e60SMatthew WilcoxThe XArray has the ability to tie multiple indices together so that 429992a8e60SMatthew Wilcoxoperations on one index affect all indices. For example, storing into 430992a8e60SMatthew Wilcoxany index will change the value of the entry retrieved from any index. 431992a8e60SMatthew WilcoxSetting or clearing a mark on any index will set or clear the mark 432992a8e60SMatthew Wilcoxon every index that is tied together. The current implementation 433992a8e60SMatthew Wilcoxonly allows tying ranges which are aligned powers of two together; 434992a8e60SMatthew Wilcoxeg indices 64-127 may be tied together, but 2-6 may not be. This may 435992a8e60SMatthew Wilcoxsave substantial quantities of memory; for example tying 512 entries 436992a8e60SMatthew Wilcoxtogether will save over 4kB. 437992a8e60SMatthew Wilcox 438992a8e60SMatthew WilcoxYou can create a multi-index entry by using :c:func:`XA_STATE_ORDER` 439992a8e60SMatthew Wilcoxor :c:func:`xas_set_order` followed by a call to :c:func:`xas_store`. 440992a8e60SMatthew WilcoxCalling :c:func:`xas_load` with a multi-index xa_state will walk the 441992a8e60SMatthew Wilcoxxa_state to the right location in the tree, but the return value is not 442992a8e60SMatthew Wilcoxmeaningful, potentially being an internal entry or ``NULL`` even when there 443992a8e60SMatthew Wilcoxis an entry stored within the range. Calling :c:func:`xas_find_conflict` 444992a8e60SMatthew Wilcoxwill return the first entry within the range or ``NULL`` if there are no 445992a8e60SMatthew Wilcoxentries in the range. The :c:func:`xas_for_each_conflict` iterator will 446992a8e60SMatthew Wilcoxiterate over every entry which overlaps the specified range. 447992a8e60SMatthew Wilcox 448992a8e60SMatthew WilcoxIf :c:func:`xas_load` encounters a multi-index entry, the xa_index 449992a8e60SMatthew Wilcoxin the xa_state will not be changed. When iterating over an XArray 450992a8e60SMatthew Wilcoxor calling :c:func:`xas_find`, if the initial index is in the middle 451992a8e60SMatthew Wilcoxof a multi-index entry, it will not be altered. Subsequent calls 452992a8e60SMatthew Wilcoxor iterations will move the index to the first index in the range. 453992a8e60SMatthew WilcoxEach entry will only be returned once, no matter how many indices it 454992a8e60SMatthew Wilcoxoccupies. 455992a8e60SMatthew Wilcox 456992a8e60SMatthew WilcoxUsing :c:func:`xas_next` or :c:func:`xas_prev` with a multi-index xa_state 457992a8e60SMatthew Wilcoxis not supported. Using either of these functions on a multi-index entry 458992a8e60SMatthew Wilcoxwill reveal sibling entries; these should be skipped over by the caller. 459992a8e60SMatthew Wilcox 460992a8e60SMatthew WilcoxStoring ``NULL`` into any index of a multi-index entry will set the entry 461992a8e60SMatthew Wilcoxat every index to ``NULL`` and dissolve the tie. Splitting a multi-index 462992a8e60SMatthew Wilcoxentry into entries occupying smaller ranges is not yet supported. 463992a8e60SMatthew Wilcox 464992a8e60SMatthew WilcoxFunctions and structures 465992a8e60SMatthew Wilcox======================== 466992a8e60SMatthew Wilcox 467992a8e60SMatthew Wilcox.. kernel-doc:: include/linux/xarray.h 468992a8e60SMatthew Wilcox.. kernel-doc:: lib/xarray.c 469