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