Something went wrong. Try again.
Linux kernel mirror (for testing) git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
Something went wrong. Try again.
22 kB · 510 lines
at master
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511.. SPDX-License-Identifier: GPL-2.0+
======XArray======
:Author: Matthew Wilcox
Overview========
The XArray is an abstract data type which behaves like a very large arrayof pointers. It meets many of the same needs as a hash or a conventionalresizable array. Unlike a hash, it allows you to sensibly go to thenext or previous entry in a cache-efficient manner. In contrast to aresizable array, there is no need to copy data or change MMU mappings inorder to grow the array. It is more memory-efficient, parallelisableand cache friendly than a doubly-linked list. It takes advantage ofRCU to perform lookups without locking.
The XArray implementation is efficient when the indices used are denselyclustered; hashing the object and using the hash as the index will notperform well. The XArray is optimised for small indices, but still hasgood performance with large indices. If your index can be larger than``ULONG_MAX`` then the XArray is not the data type for you. The mostimportant user of the XArray is the page cache.
Normal pointers may be stored in the XArray directly. They must be 4-bytealigned, which is true for any pointer returned from kmalloc() andalloc_page(). It isn't true for arbitrary user-space pointers,nor for function pointers. You can store pointers to statically allocatedobjects, as long as those objects have an alignment of at least 4.
You can also store integers between 0 and ``LONG_MAX`` in the XArray.You must first convert it into an entry using xa_mk_value().When you retrieve an entry from the XArray, you can check whether it isa value entry by calling xa_is_value(), and convert it back toan integer by calling xa_to_value().
Some users want to tag the pointers they store in the XArray. You cancall xa_tag_pointer() to create an entry with a tag, xa_untag_pointer()to turn a tagged entry back into an untagged pointer and xa_pointer_tag()to retrieve the tag of an entry. Tagged pointers use the same bits thatare used to distinguish value entries from normal pointers, so you mustdecide whether you want to store value entries or tagged pointers in anyparticular XArray.
The XArray does not support storing IS_ERR() pointers as someconflict with value entries or internal entries.
An unusual feature of the XArray is the ability to create entries whichoccupy a range of indices. Once stored to, looking up any index inthe range will return the same entry as looking up any other index inthe range. Storing to any index will store to all of them. Multi-indexentries can be explicitly split into smaller entries. Unsetting (usingxa_erase() or xa_store() with ``NULL``) any entry will cause the XArrayto forget about the range.
Normal API==========
Start by initialising an XArray, either with DEFINE_XARRAY()for statically allocated XArrays or xa_init() for dynamicallyallocated ones. A freshly-initialised XArray contains a ``NULL``pointer at every index.
You can then set entries using xa_store() and get entries usingxa_load(). xa_store() will overwrite any entry with the new entry andreturn the previous entry stored at that index. You can unset entriesusing xa_erase() or by setting the entry to ``NULL`` using xa_store().There is no difference between an entry that has never been stored toand one that has been erased with xa_erase(); an entry that has mostrecently had ``NULL`` stored to it is also equivalent except if theXArray was initialized with ``XA_FLAGS_ALLOC``.
You can conditionally replace an entry at an index by usingxa_cmpxchg(). Like cmpxchg(), it will only succeed ifthe entry at that index has the 'old' value. It also returns the entrywhich was at that index; if it returns the same entry which was passed as'old', then xa_cmpxchg() succeeded.
If you want to only store a new entry to an index if the current entryat that index is ``NULL``, you can use xa_insert() whichreturns ``-EBUSY`` if the entry is not empty.
You can copy entries out of the XArray into a plain array by callingxa_extract(). Or you can iterate over the present entries in the XArrayby calling xa_for_each(), xa_for_each_start() or xa_for_each_range().You may prefer to use xa_find() or xa_find_after() to move to the nextpresent entry in the XArray.
Calling xa_store_range() stores the same entry in a rangeof indices. If you do this, some of the other operations will behavein a slightly odd way. For example, marking the entry at one indexmay result in the entry being marked at some, but not all of the otherindices. Storing into one index may result in the entry retrieved bysome, but not all of the other indices changing.
Sometimes you need to ensure that a subsequent call to xa_store()will not need to allocate memory. The xa_reserve() functionwill store a reserved entry at the indicated index. Users of thenormal API will see this entry as containing ``NULL``. If you donot need to use the reserved entry, you can call xa_release()to remove the unused entry. If another user has stored to the entryin the meantime, xa_release() will do nothing; if instead youwant the entry to become ``NULL``, you should use xa_erase().Using xa_insert() on a reserved entry will fail.
If all entries in the array are ``NULL``, the xa_empty() functionwill return ``true``.
Finally, you can remove all entries from an XArray by callingxa_destroy(). If the XArray entries are pointers, you may wishto free the entries first. You can do this by iterating over all presententries in the XArray using the xa_for_each() iterator.
Search Marks------------
Each entry in the array has three bits associated with it called marks.Each mark may be set or cleared independently of the others. You caniterate over marked entries by using the xa_for_each_marked() iterator.
You can enquire whether a mark is set on an entry by usingxa_get_mark(). If the entry is not ``NULL``, you can set a mark on itby using xa_set_mark() and remove the mark from an entry by callingxa_clear_mark(). You can ask whether any entry in the XArray has aparticular mark set by calling xa_marked(). Erasing an entry from theXArray causes all marks associated with that entry to be cleared.
Setting or clearing a mark on any index of a multi-index entry willaffect all indices covered by that entry. Querying the mark on anyindex will return the same result.
There is no way to iterate over entries which are not marked; the datastructure does not allow this to be implemented efficiently. There arenot currently iterators to search for logical combinations of bits (egiterate over all entries which have both ``XA_MARK_1`` and ``XA_MARK_2``set, or iterate over all entries which have ``XA_MARK_0`` or ``XA_MARK_2``set). It would be possible to add these if a user arises.
Allocating XArrays------------------
If you use DEFINE_XARRAY_ALLOC() to define the XArray, orinitialise it by passing ``XA_FLAGS_ALLOC`` to xa_init_flags(),the XArray changes to track whether entries are in use or not.
You can call xa_alloc() to store the entry at an unused indexin the XArray. If you need to modify the array from interrupt context,you can use xa_alloc_bh() or xa_alloc_irq() to disableinterrupts while allocating the ID.
Using xa_store(), xa_cmpxchg() or xa_insert() willalso mark the entry as being allocated. Unlike a normal XArray, storing``NULL`` will mark the entry as being in use, like xa_reserve().To free an entry, use xa_erase() (or xa_release() ifyou only want to free the entry if it's ``NULL``).
By default, the lowest free entry is allocated starting from 0. If youwant to allocate entries starting at 1, it is more efficient to useDEFINE_XARRAY_ALLOC1() or ``XA_FLAGS_ALLOC1``. If you want toallocate IDs up to a maximum, then wrap back around to the lowest freeID, you can use xa_alloc_cyclic().
You cannot use ``XA_MARK_0`` with an allocating XArray as this markis used to track whether an entry is free or not. The other marks areavailable for your use.
Memory allocation-----------------
The xa_store(), xa_cmpxchg(), xa_alloc(),xa_reserve() and xa_insert() functions take a gfp_tparameter in case the XArray needs to allocate memory to store this entry.If the entry is being deleted, no memory allocation needs to be performed,and the GFP flags specified will be ignored.
It is possible for no memory to be allocatable, particularly if you passa restrictive set of GFP flags. In that case, the functions return aspecial value which can be turned into an errno using xa_err().If you don't need to know exactly which error occurred, usingxa_is_err() is slightly more efficient.
Locking-------
When using the Normal API, you do not have to worry about locking.The XArray uses RCU and an internal spinlock to synchronise access:
No lock needed: * xa_empty() * xa_marked()
Takes RCU read lock: * xa_load() * xa_for_each() * xa_for_each_start() * xa_for_each_range() * xa_find() * xa_find_after() * xa_extract() * xa_get_mark()
Takes xa_lock internally: * xa_store() * xa_store_bh() * xa_store_irq() * xa_insert() * xa_insert_bh() * xa_insert_irq() * xa_erase() * xa_erase_bh() * xa_erase_irq() * xa_cmpxchg() * xa_cmpxchg_bh() * xa_cmpxchg_irq() * xa_store_range() * xa_alloc() * xa_alloc_bh() * xa_alloc_irq() * xa_reserve() * xa_reserve_bh() * xa_reserve_irq() * xa_destroy() * xa_set_mark() * xa_clear_mark()
Assumes xa_lock held on entry: * __xa_store() * __xa_insert() * __xa_erase() * __xa_cmpxchg() * __xa_alloc() * __xa_set_mark() * __xa_clear_mark()
If you want to take advantage of the lock to protect the data structuresthat you are storing in the XArray, you can call xa_lock()before calling xa_load(), then take a reference count on theobject you have found before calling xa_unlock(). This willprevent stores from removing the object from the array between lookingup the object and incrementing the refcount. You can also use RCU toavoid dereferencing freed memory, but an explanation of that is beyondthe scope of this document.
The XArray does not disable interrupts or softirqs while modifyingthe array. It is safe to read the XArray from interrupt or softirqcontext as the RCU lock provides enough protection.
If, for example, you want to store entries in the XArray in processcontext and then erase them in softirq context, you can do that this way::
void foo_init(struct foo *foo) { xa_init_flags(&foo->array, XA_FLAGS_LOCK_BH); }
int foo_store(struct foo *foo, unsigned long index, void *entry) { int err;
xa_lock_bh(&foo->array); err = xa_err(__xa_store(&foo->array, index, entry, GFP_KERNEL)); if (!err) foo->count++; xa_unlock_bh(&foo->array); return err; }
/* foo_erase() is only called from softirq context */ void foo_erase(struct foo *foo, unsigned long index) { xa_lock(&foo->array); __xa_erase(&foo->array, index); foo->count--; xa_unlock(&foo->array); }
If you are going to modify the XArray from interrupt or softirq context,you need to initialise the array using xa_init_flags(), passing``XA_FLAGS_LOCK_IRQ`` or ``XA_FLAGS_LOCK_BH``.
The above example also shows a common pattern of wanting to extend thecoverage of the xa_lock on the store side to protect some statisticsassociated with the array.
Sharing the XArray with interrupt context is also possible, eitherusing xa_lock_irqsave() in both the interrupt handler and processcontext, or xa_lock_irq() in process context and xa_lock()in the interrupt handler. Some of the more common patterns have helperfunctions such as xa_store_bh(), xa_store_irq(),xa_erase_bh(), xa_erase_irq(), xa_cmpxchg_bh()and xa_cmpxchg_irq().
Sometimes you need to protect access to the XArray with a mutex becausethat lock sits above another mutex in the locking hierarchy. That doesnot entitle you to use functions like __xa_erase() without takingthe xa_lock; the xa_lock is used for lockdep validation and will be usedfor other purposes in the future.
The __xa_set_mark() and __xa_clear_mark() functions are alsoavailable for situations where you look up an entry and want to atomicallyset or clear a mark. It may be more efficient to use the advanced APIin this case, as it will save you from walking the tree twice.
Advanced API============
The advanced API offers more flexibility and better performance at thecost of an interface which can be harder to use and has fewer safeguards.No locking is done for you by the advanced API, and you are requiredto use the xa_lock while modifying the array. You can choose whetherto use the xa_lock or the RCU lock while doing read-only operations onthe array. You can mix advanced and normal operations on the same array;indeed the normal API is implemented in terms of the advanced API. Theadvanced API is only available to modules with a GPL-compatible license.
The advanced API is based around the xa_state. This is an opaque datastructure which you declare on the stack using the XA_STATE() macro.This macro initialises the xa_state ready to start walking around theXArray. It is used as a cursor to maintain the position in the XArrayand let you compose various operations together without having to restartfrom the top every time. The contents of the xa_state are protected bythe rcu_read_lock() or the xas_lock(). If you need to drop whichever ofthose locks is protecting your state and tree, you must call xas_pause()so that future calls do not rely on the parts of the state which wereleft unprotected.
The xa_state is also used to store errors. You can callxas_error() to retrieve the error. All operations check whetherthe xa_state is in an error state before proceeding, so there's no needfor you to check for an error after each call; you can make multiplecalls in succession and only check at a convenient point. The onlyerrors currently generated by the XArray code itself are ``ENOMEM`` and``EINVAL``, but it supports arbitrary errors in case you want to callxas_set_err() yourself.
If the xa_state is holding an ``ENOMEM`` error, calling xas_nomem()will attempt to allocate more memory using the specified gfp flags andcache it in the xa_state for the next attempt. The idea is that you takethe xa_lock, attempt the operation and drop the lock. The operationattempts to allocate memory while holding the lock, but it is morelikely to fail. Once you have dropped the lock, xas_nomem()can try harder to allocate more memory. It will return ``true`` if itis worth retrying the operation (i.e. that there was a memory error *and*more memory was allocated). If it has previously allocated memory, andthat memory wasn't used, and there is no error (or some error that isn't``ENOMEM``), then it will free the memory previously allocated.
Internal Entries----------------
The XArray reserves some entries for its own purposes. These are neverexposed through the normal API, but when using the advanced API, it'spossible to see them. Usually the best way to handle them is to pass themto xas_retry(), and retry the operation if it returns ``true``.
.. flat-table:: :widths: 1 1 6
* - Name - Test - Usage
* - Node - xa_is_node() - An XArray node. May be visible when using a multi-index xa_state.
* - Sibling - xa_is_sibling() - A non-canonical entry for a multi-index entry. The value indicates which slot in this node has the canonical entry.
* - Retry - xa_is_retry() - This entry is currently being modified by a thread which has the xa_lock. The node containing this entry may be freed at the end of this RCU period. You should restart the lookup from the head of the array.
* - Zero - xa_is_zero() - Zero entries appear as ``NULL`` through the Normal API, but occupy an entry in the XArray which can be used to reserve the index for future use. This is used by allocating XArrays for allocated entries which are ``NULL``.
Other internal entries may be added in the future. As far as possible, theywill be handled by xas_retry().
Additional functionality------------------------
The xas_create_range() function allocates all the necessary memoryto store every entry in a range. It will set ENOMEM in the xa_state ifit cannot allocate memory.
You can use xas_init_marks() to reset the marks on an entryto their default state. This is usually all marks clear, unless theXArray is marked with ``XA_FLAGS_TRACK_FREE``, in which case mark 0 is setand all other marks are clear. Replacing one entry with another usingxas_store() will not reset the marks on that entry; if you wantthe marks reset, you should do that explicitly.
The xas_load() will walk the xa_state as close to the entryas it can. If you know the xa_state has already been walked to theentry and need to check that the entry hasn't changed, you can usexas_reload() to save a function call.
If you need to move to a different index in the XArray, callxas_set(). This resets the cursor to the top of the tree, whichwill generally make the next operation walk the cursor to the desiredspot in the tree. If you want to move to the next or previous index,call xas_next() or xas_prev(). Setting the index doesnot walk the cursor around the array so does not require a lock to beheld, while moving to the next or previous index does.
You can search for the next present entry using xas_find(). Thisis the equivalent of both xa_find() and xa_find_after();if the cursor has been walked to an entry, then it will find the nextentry after the one currently referenced. If not, it will return theentry at the index of the xa_state. Using xas_next_entry() tomove to the next present entry instead of xas_find() will savea function call in the majority of cases at the expense of emitting moreinline code.
The xas_find_marked() function is similar. If the xa_state hasnot been walked, it will return the entry at the index of the xa_state,if it is marked. Otherwise, it will return the first marked entry afterthe entry referenced by the xa_state. The xas_next_marked()function is the equivalent of xas_next_entry().
When iterating over a range of the XArray using xas_for_each()or xas_for_each_marked(), it may be necessary to temporarily stopthe iteration. The xas_pause() function exists for this purpose.After you have done the necessary work and wish to resume, the xa_stateis in an appropriate state to continue the iteration after the entryyou last processed. If you have interrupts disabled while iterating,then it is good manners to pause the iteration and reenable interruptsevery ``XA_CHECK_SCHED`` entries.
The xas_get_mark(), xas_set_mark() and xas_clear_mark() functions requirethe xa_state cursor to have been moved to the appropriate location in theXArray; they will do nothing if you have called xas_pause() or xas_set()immediately before.
You can call xas_set_update() to have a callback functioncalled each time the XArray updates a node. This is used by the pagecache workingset code to maintain its list of nodes which contain onlyshadow entries.
Multi-Index Entries-------------------
The XArray has the ability to tie multiple indices together so thatoperations on one index affect all indices. For example, storing intoany index will change the value of the entry retrieved from any index.Setting or clearing a mark on any index will set or clear the markon every index that is tied together. The current implementationonly allows tying ranges which are aligned powers of two together;eg indices 64-127 may be tied together, but 2-6 may not be. This maysave substantial quantities of memory; for example tying 512 entriestogether will save over 4kB.
You can create a multi-index entry by using XA_STATE_ORDER()or xas_set_order() followed by a call to xas_store().Calling xas_load() with a multi-index xa_state will walk thexa_state to the right location in the tree, but the return value is notmeaningful, potentially being an internal entry or ``NULL`` even when thereis an entry stored within the range. Calling xas_find_conflict()will return the first entry within the range or ``NULL`` if there are noentries in the range. The xas_for_each_conflict() iterator williterate over every entry which overlaps the specified range.
If xas_load() encounters a multi-index entry, the xa_indexin the xa_state will not be changed. When iterating over an XArrayor calling xas_find(), if the initial index is in the middleof a multi-index entry, it will not be altered. Subsequent callsor iterations will move the index to the first index in the range.Each entry will only be returned once, no matter how many indices itoccupies.
Using xas_next() or xas_prev() with a multi-index xa_state is notsupported. Using either of these functions on a multi-index entry willreveal sibling entries; these should be skipped over by the caller.
Storing ``NULL`` into any index of a multi-index entry will set theentry at every index to ``NULL`` and dissolve the tie. A multi-indexentry can be split into entries occupying smaller ranges by callingxas_split_alloc() without the xa_lock held, followed by taking the lockand calling xas_split() or calling xas_try_split() with xa_lock. Thedifference between xas_split_alloc()+xas_split() and xas_try_alloc() isthat xas_split_alloc() + xas_split() split the entry from the originalorder to the new order in one shot uniformly, whereas xas_try_split()iteratively splits the entry containing the index non-uniformly.For example, to split an order-9 entry, which takes 2^(9-6)=8 slots,assuming ``XA_CHUNK_SHIFT`` is 6, xas_split_alloc() + xas_split() need8 xa_node. xas_try_split() splits the order-9 entry into2 order-8 entries, then split one order-8 entry, based on the given index,to 2 order-7 entries, ..., and split one order-1 entry to 2 order-0 entries.When splitting the order-6 entry and a new xa_node is needed, xas_try_split()will try to allocate one if possible. As a result, xas_try_split() would onlyneed 1 xa_node instead of 8.
Functions and structures========================
.. kernel-doc:: include/linux/xarray.h.. kernel-doc:: lib/xarray.c