Lines Matching full:to
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
19 RCU to perform lookups without locking.
31 nor for function pointers. You can store pointers to statically allocated
37 a value entry by calling xa_is_value(), and convert it back to
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 they want to store value entries or tagged pointers in
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
54 the range. Storing to any index will store to all of them. Multi-index
56 into any entry will cause the XArray to forget about the range.
71 been stored to, one that has been erased and one that has most recently
72 had ``NULL`` stored to it.
80 If you want to only store a new entry to an index if the current entry
87 You may prefer to use xa_find() or xa_find_after() to move to the next
97 Sometimes you need to ensure that a subsequent call to xa_store()
98 will not need to allocate memory. The xa_reserve() function
101 not need to use the reserved entry, you can call xa_release()
102 to remove the unused entry. If another user has stored to the entry
104 want the entry to become ``NULL``, you should use xa_erase().
112 to free the entries first. You can do this by iterating over all present
127 XArray causes all marks associated with that entry to be cleared.
133 There is no way to iterate over entries which are not marked; the data
134 structure does not allow this to be implemented efficiently. There are
135 not currently iterators to search for logical combinations of bits (eg
138 set). It would be possible to add these if a user arises.
143 If you use DEFINE_XARRAY_ALLOC() to define the XArray, or
144 initialise it by passing ``XA_FLAGS_ALLOC`` to xa_init_flags(),
145 the XArray changes to track whether entries are in use or not.
147 You can call xa_alloc() to store the entry at an unused index
148 in the XArray. If you need to modify the array from interrupt context,
149 you can use xa_alloc_bh() or xa_alloc_irq() to disable
155 To free an entry, use xa_erase() (or xa_release() if
156 you only want to free the entry if it's ``NULL``).
159 want to allocate entries starting at 1, it is more efficient to use
160 DEFINE_XARRAY_ALLOC1() or ``XA_FLAGS_ALLOC1``. If you want to
161 allocate IDs up to a maximum, then wrap back around to the lowest free
165 is used to track whether an entry is free or not. The other marks are
173 parameter in case the XArray needs to allocate memory to store this entry.
174 If the entry is being deleted, no memory allocation needs to be performed,
177 It is possible for no memory to be allocatable, particularly if you pass
180 If you don't need to know exactly which error occurred, using
186 When using the Normal API, you do not have to worry about locking.
187 The XArray uses RCU and an internal spinlock to synchronise access:
236 If you want to take advantage of the lock to protect the data structures
241 up the object and incrementing the refcount. You can also use RCU to
246 the array. It is safe to read the XArray from interrupt or softirq
249 If, for example, you want to store entries in the XArray in process
278 If you are going to modify the XArray from interrupt or softirq context,
279 you need to initialise the array using xa_init_flags(), passing
282 The above example also shows a common pattern of wanting to extend the
283 coverage of the xa_lock on the store side to protect some statistics
294 Sometimes you need to protect access to the XArray with a mutex because
296 not entitle you to use functions like __xa_erase() without taking
301 available for situations where you look up an entry and want to atomically
302 set or clear a mark. It may be more efficient to use the advanced API
309 cost of an interface which can be harder to use and has fewer safeguards.
311 to use the xa_lock while modifying the array. You can choose whether
312 to use the xa_lock or the RCU lock while doing read-only operations on
315 advanced API is only available to modules with a GPL-compatible license.
319 This macro initialises the xa_state ready to start walking around the
320 XArray. It is used as a cursor to maintain the position in the XArray
321 and let you compose various operations together without having to restart
323 the rcu_read_lock() or the xas_lock(). If you need to drop whichever of
328 The xa_state is also used to store errors. You can call
329 xas_error() to retrieve the error. All operations check whether
331 for you to check for an error after each call; you can make multiple
334 ``EINVAL``, but it supports arbitrary errors in case you want to call
338 will attempt to allocate more memory using the specified gfp flags and
341 attempts to allocate memory while holding the lock, but it is more
342 likely to fail. Once you have dropped the lock, xas_nomem()
343 can try harder to allocate more memory. It will return ``true`` if it
354 possible to see them. Usually the best way to handle them is to pass them
355 to xas_retry(), and retry the operation if it returns ``true``.
383 an entry in the XArray which can be used to reserve the index for
394 to store every entry in a range. It will set ENOMEM in the xa_state if
397 You can use xas_init_marks() to reset the marks on an entry
398 to their default state. This is usually all marks clear, unless the
404 The xas_load() will walk the xa_state as close to the entry
405 as it can. If you know the xa_state has already been walked to the
406 entry and need to check that the entry hasn't changed, you can use
407 xas_reload() to save a function call.
409 If you need to move to a different index in the XArray, call
410 xas_set(). This resets the cursor to the top of the tree, which
411 will generally make the next operation walk the cursor to the desired
412 spot in the tree. If you want to move to the next or previous index,
414 not walk the cursor around the array so does not require a lock to be
415 held, while moving to the next or previous index does.
419 if the cursor has been walked to an entry, then it will find the next
421 entry at the index of the xa_state. Using xas_next_entry() to
422 move to the next present entry instead of xas_find() will save
433 or xas_for_each_marked(), it may be necessary to temporarily stop
435 After you have done the necessary work and wish to resume, the xa_state
436 is in an appropriate state to continue the iteration after the entry
438 then it is good manners to pause the iteration and reenable interrupts
442 the xa_state cursor to have been moved to the appropriate location in the
446 You can call xas_set_update() to have a callback function
448 cache workingset code to maintain its list of nodes which contain only
454 The XArray has the ability to tie multiple indices together so that
465 or xas_set_order() followed by a call to xas_store().
467 xa_state to the right location in the tree, but the return value is not
478 or iterations will move the index to the first index in the range.
487 entry at every index to ``NULL`` and dissolve the tie. A multi-index