English

Chinese (Simplified)

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 thanULONG_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 fromkmalloc() 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 andLONG_MAX in the XArray.You must first convert it into an entry usingxa_mk_value().When you retrieve an entry from the XArray, you can check whether it isa value entry by callingxa_is_value(), and convert it back toan integer by callingxa_to_value().

Some users want to tag the pointers they store in the XArray. You cancallxa_tag_pointer() to create an entry with a tag,xa_untag_pointer()to turn a tagged entry back into an untagged pointer andxa_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 storingIS_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() orxa_store() withNULL) any entry will cause the XArrayto forget about the range.

Normal API¶

Start by initialising an XArray, either withDEFINE_XARRAY()for statically allocated XArrays orxa_init() for dynamicallyallocated ones. A freshly-initialised XArray contains aNULLpointer at every index.

You can then set entries usingxa_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 entriesusingxa_erase() or by setting the entry toNULL usingxa_store().There is no difference between an entry that has never been stored toand one that has been erased withxa_erase(); an entry that has mostrecently hadNULL stored to it is also equivalent except if theXArray was initialized withXA_FLAGS_ALLOC.

You can conditionally replace an entry at an index by usingxa_cmpxchg(). Likecmpxchg(), 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’, thenxa_cmpxchg() succeeded.

If you want to only store a new entry to an index if the current entryat that index isNULL, you can usexa_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 callingxa_for_each(),xa_for_each_start() orxa_for_each_range().You may prefer to usexa_find() orxa_find_after() to move to the nextpresent entry in the XArray.

Callingxa_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 toxa_store()will not need to allocate memory. Thexa_reserve() functionwill store a reserved entry at the indicated index. Users of thenormal API will see this entry as containingNULL. If you donot need to use the reserved entry, you can callxa_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 becomeNULL, you should usexa_erase().Usingxa_insert() on a reserved entry will fail.

If all entries in the array areNULL, thexa_empty() functionwill returntrue.

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 thexa_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 thexa_for_each_marked() iterator.

You can enquire whether a mark is set on an entry by usingxa_get_mark(). If the entry is notNULL, you can set a mark on itby usingxa_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 callingxa_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 bothXA_MARK_1 andXA_MARK_2set, or iterate over all entries which haveXA_MARK_0 orXA_MARK_2set). It would be possible to add these if a user arises.

Allocating XArrays¶

If you useDEFINE_XARRAY_ALLOC() to define the XArray, orinitialise it by passingXA_FLAGS_ALLOC toxa_init_flags(),the XArray changes to track whether entries are in use or not.

You can callxa_alloc() to store the entry at an unused indexin the XArray. If you need to modify the array from interrupt context,you can usexa_alloc_bh() orxa_alloc_irq() to disableinterrupts while allocating the ID.

Usingxa_store(),xa_cmpxchg() orxa_insert() willalso mark the entry as being allocated. Unlike a normal XArray, storingNULL will mark the entry as being in use, likexa_reserve().To free an entry, usexa_erase() (orxa_release() ifyou only want to free the entry if it’sNULL).

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() orXA_FLAGS_ALLOC1. If you want toallocate IDs up to a maximum, then wrap back around to the lowest freeID, you can usexa_alloc_cyclic().

You cannot useXA_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¶

Thexa_store(),xa_cmpxchg(),xa_alloc(),xa_reserve() andxa_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 usingxa_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:

Takes RCU read lock:

Takes xa_lock internally:

Assumes xa_lock held on entry:

If you want to take advantage of the lock to protect the data structuresthat you are storing in the XArray, you can callxa_lock()before callingxa_load(), then take a reference count on theobject you have found before callingxa_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 usingxa_init_flags(), passingXA_FLAGS_LOCK_IRQ orXA_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, eitherusingxa_lock_irqsave() in both the interrupt handler and processcontext, orxa_lock_irq() in process context andxa_lock()in the interrupt handler. Some of the more common patterns have helperfunctions such asxa_store_bh(),xa_store_irq(),xa_erase_bh(),xa_erase_irq(),xa_cmpxchg_bh()andxa_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 theXA_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 bythercu_read_lock() or thexas_lock(). If you need to drop whichever ofthose locks is protecting your state and tree, you must callxas_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 areENOMEM andEINVAL, but it supports arbitrary errors in case you want to callxas_set_err() yourself.

If the xa_state is holding anENOMEM error, callingxas_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 returntrue if itis worth retrying the operation (i.e. that there was a memory errorandmore memory was allocated). If it has previously allocated memory, andthat memory wasn’t used, and there is no error (or some error that isn’tENOMEM), 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 themtoxas_retry(), and retry the operation if it returnstrue.

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 indicateswhich slot in this node has the canonical entry.
Retry	`xa_is_retry()`	This entry is currently being modified by a thread which has thexa_lock. The node containing this entry may be freed at the endof this RCU period. You should restart the lookup from the headof the array.
Zero	`xa_is_zero()`	Zero entries appear as`NULL` through the Normal API, but occupyan entry in the XArray which can be used to reserve the index forfuture use. This is used by allocating XArrays for allocated entrieswhich are`NULL`.

Other internal entries may be added in the future. As far as possible, theywill be handled byxas_retry().

Additional functionality¶

Thexas_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 usexas_init_marks() to reset the marks on an entryto their default state. This is usually all marks clear, unless theXArray is marked withXA_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.

Thexas_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,callxas_next() orxas_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 usingxas_find(). Thisis the equivalent of bothxa_find() andxa_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. Usingxas_next_entry() tomove to the next present entry instead ofxas_find() will savea function call in the majority of cases at the expense of emitting moreinline code.

Thexas_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. Thexas_next_marked()function is the equivalent ofxas_next_entry().

When iterating over a range of the XArray usingxas_for_each()orxas_for_each_marked(), it may be necessary to temporarily stopthe iteration. Thexas_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 interruptseveryXA_CHECK_SCHED entries.

Thexas_get_mark(),xas_set_mark() andxas_clear_mark() functions requirethe xa_state cursor to have been moved to the appropriate location in theXArray; they will do nothing if you have calledxas_pause() orxas_set()immediately before.

You can callxas_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 usingXA_STATE_ORDER()orxas_set_order() followed by a call toxas_store().Callingxas_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 orNULL even when thereis an entry stored within the range. Callingxas_find_conflict()will return the first entry within the range orNULL if there are noentries in the range. Thexas_for_each_conflict() iterator williterate over every entry which overlaps the specified range.

Ifxas_load() encounters a multi-index entry, the xa_indexin the xa_state will not be changed. When iterating over an XArrayor callingxas_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.

Usingxas_next() orxas_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.

StoringNULL into any index of a multi-index entry will set theentry at every index toNULL 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 callingxas_split() or callingxas_try_split() with xa_lock. Thedifference betweenxas_split_alloc()+xas_split() andxas_try_alloc() isthatxas_split_alloc() +xas_split() split the entry from the originalorder to the new order in one shot uniformly, whereasxas_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,assumingXA_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¶

void*xa_mk_value(unsignedlongv)¶: Create an XArray entry from an integer.

Parameters

unsignedlongv: Value to store in XArray.

Context

Any context.

Return

An entry suitable for storing in the XArray.

unsignedlongxa_to_value(constvoid*entry)¶: Get value stored in an XArray entry.

Parameters

constvoid*entry: XArray entry.

Context

Any context.

Return

The value stored in the XArray entry.

boolxa_is_value(constvoid*entry)¶: Determine if an entry is a value.

Parameters

constvoid*entry: XArray entry.

Context

Any context.

Return

True if the entry is a value, false if it is a pointer.

void*xa_tag_pointer(void*p,unsignedlongtag)¶: Create an XArray entry for a tagged pointer.

Parameters

void*p: Plain pointer.
unsignedlongtag: Tag value (0, 1 or 3).

Description

If the user of the XArray prefers, they can tag their pointers insteadof storing value entries. Three tags are available (0, 1 and 3).These are distinct from the xa_mark_t as they are not replicated upthrough the array and cannot be searched for.

Context

Any context.

Return

An XArray entry.

void*xa_untag_pointer(void*entry)¶: Turn an XArray entry into a plain pointer.

Parameters

void*entry: XArray entry.

Description

If you have stored a tagged pointer in the XArray, call this functionto get the untagged version of the pointer.

Context

Any context.

Return

A pointer.

unsignedintxa_pointer_tag(void*entry)¶: Get the tag stored in an XArray entry.

Parameters

void*entry: XArray entry.

Description

If you have stored a tagged pointer in the XArray, call this functionto get the tag of that pointer.

Context

Any context.

Return

A tag.

boolxa_is_zero(constvoid*entry)¶: Is the entry a zero entry?

Parameters

constvoid*entry: Entry retrieved from the XArray

Description

The normal API will return NULL as the contents of a slot containinga zero entry. You can only see zero entries by using the advanced API.

Return

true if the entry is a zero entry.

boolxa_is_err(constvoid*entry)¶: Report whether an XArray operation returned an error

Parameters

constvoid*entry: Result from calling an XArray function

Description

If an XArray operation cannot complete an operation, it will returna special value indicating an error. This function tells youwhether an error occurred;xa_err() tells you which error occurred.

Context

Any context.

Return

true if the entry indicates an error.

intxa_err(void*entry)¶: Turn an XArray result into an errno.

Parameters

void*entry: Result from calling an XArray function.

Description

If an XArray operation cannot complete an operation, it will returna special pointer value which encodes an errno. This function extractsthe errno from the pointer value, or returns 0 if the pointer does notrepresent an errno.

Context

Any context.

Return

A negative errno or 0.

structxa_limit¶: Represents a range of IDs.

Definition:

struct xa_limit {    u32 max;    u32 min;};

Members

max: The maximum ID to allocate (inclusive).
min: The lowest ID to allocate (inclusive).

Description

This structure is used either directly or via theXA_LIMIT() macroto communicate the range of IDs that are valid for allocation.Three common ranges are predefined for you:* xa_limit_32b - [0 - UINT_MAX]* xa_limit_31b - [0 - INT_MAX]* xa_limit_16b - [0 - USHRT_MAX]

structxarray¶: The anchor of the XArray.

Definition:

struct xarray {    spinlock_t xa_lock;};

Members

xa_lock: Lock that protects the contents of the XArray.

Description

To use the xarray, define it statically or embed it in your data structure.It is a very small data structure, so it does not usually make sense toallocate it separately and keep a pointer to it in your data structure.

You may use the xa_lock to protect your own data structures as well.

DEFINE_XARRAY_FLAGS¶

DEFINE_XARRAY_FLAGS(name,flags)

Define an XArray with custom flags.

Parameters

name: A string that names your XArray.
flags: XA_FLAG values.

Description

This is intended for file scope definitions of XArrays. It declaresand initialises an empty XArray with the chosen name and flags. It isequivalent to callingxa_init_flags() on the array, but it does theinitialisation at compiletime instead of runtime.

DEFINE_XARRAY¶

DEFINE_XARRAY(name)

Define an XArray.

Parameters

name: A string that names your XArray.

Description

This is intended for file scope definitions of XArrays. It declaresand initialises an empty XArray with the chosen name. It is equivalentto callingxa_init() on the array, but it does the initialisation atcompiletime instead of runtime.

DEFINE_XARRAY_ALLOC¶

DEFINE_XARRAY_ALLOC(name)

Define an XArray which allocates IDs starting at 0.

Parameters

name: A string that names your XArray.

Description

This is intended for file scope definitions of allocating XArrays.See alsoDEFINE_XARRAY().

DEFINE_XARRAY_ALLOC1¶

DEFINE_XARRAY_ALLOC1(name)

Define an XArray which allocates IDs starting at 1.

Parameters

name: A string that names your XArray.

Description

This is intended for file scope definitions of allocating XArrays.See alsoDEFINE_XARRAY().

voidxa_init_flags(structxarray*xa,gfp_tflags)¶: Initialise an empty XArray with flags.

Parameters

structxarray*xa: XArray.
gfp_tflags: XA_FLAG values.

Description

If you need to initialise an XArray with special flags (eg you needto take the lock from interrupt context), use this function insteadofxa_init().

Context

Any context.

voidxa_init(structxarray*xa)¶: Initialise an empty XArray.

Parameters

structxarray*xa: XArray.

Description

An empty XArray is full of NULL entries.

Context

Any context.

boolxa_empty(conststructxarray*xa)¶: Determine if an array has any present entries.

Parameters

conststructxarray*xa: XArray.

Context

Any context.

Return

true if the array contains only NULL pointers.

boolxa_marked(conststructxarray*xa,xa_mark_tmark)¶: Inquire whether any entry in this array has a mark set

Parameters

conststructxarray*xa: Array
xa_mark_tmark: Mark value

Context

Any context.

Return

true if any entry has this mark set.

xa_for_each_range¶

xa_for_each_range(xa,index,entry,start,last)

Iterate over a portion of an XArray.

Parameters

xa: XArray.
index: Index ofentry.
entry: Entry retrieved from array.
start: First index to retrieve from array.
last: Last index to retrieve from array.

Description

During the iteration,entry will have the value of the entry storedinxa atindex. You may modifyindex during the iteration if youwant to skip or reprocess indices. It is safe to modify the arrayduring the iteration. At the end of the iteration,entry will be setto NULL andindex will have a value less than or equal to max.

xa_for_each_range() is O(n.log(n)) whilexas_for_each() is O(n). You haveto handle your own locking withxas_for_each(), and if you have to unlockafter each iteration, it will also end up being O(n.log(n)).xa_for_each_range() will spin if it hits a retry entry; if you intend tosee retry entries, you should use thexas_for_each() iterator instead.Thexas_for_each() iterator will expand into more inline code thanxa_for_each_range().

Context

Any context. Takes and releases the RCU lock.

xa_for_each_start¶

xa_for_each_start(xa,index,entry,start)

Iterate over a portion of an XArray.

Parameters

xa: XArray.
index: Index ofentry.
entry: Entry retrieved from array.
start: First index to retrieve from array.

Description

xa_for_each_start() is O(n.log(n)) whilexas_for_each() is O(n). You haveto handle your own locking withxas_for_each(), and if you have to unlockafter each iteration, it will also end up being O(n.log(n)).xa_for_each_start() will spin if it hits a retry entry; if you intend tosee retry entries, you should use thexas_for_each() iterator instead.Thexas_for_each() iterator will expand into more inline code thanxa_for_each_start().

Context

Any context. Takes and releases the RCU lock.

xa_for_each¶

xa_for_each(xa,index,entry)

Iterate over present entries in an XArray.

Parameters

xa: XArray.
index: Index ofentry.
entry: Entry retrieved from array.

Description

During the iteration,entry will have the value of the entry storedinxa atindex. You may modifyindex during the iteration if you wantto skip or reprocess indices. It is safe to modify the array during theiteration. At the end of the iteration,entry will be set to NULL andindex will have a value less than or equal to max.

xa_for_each() is O(n.log(n)) whilexas_for_each() is O(n). You haveto handle your own locking withxas_for_each(), and if you have to unlockafter each iteration, it will also end up being O(n.log(n)).xa_for_each()will spin if it hits a retry entry; if you intend to see retry entries,you should use thexas_for_each() iterator instead. Thexas_for_each()iterator will expand into more inline code thanxa_for_each().

Context

Any context. Takes and releases the RCU lock.

xa_for_each_marked¶

xa_for_each_marked(xa,index,entry,filter)

Iterate over marked entries in an XArray.

Parameters

xa: XArray.
index: Index ofentry.
entry: Entry retrieved from array.
filter: Selection criterion.

Description

During the iteration,entry will have the value of the entry storedinxa atindex. The iteration will skip all entries in the arraywhich do not matchfilter. You may modifyindex during the iterationif you want to skip or reprocess indices. It is safe to modify the arrayduring the iteration. At the end of the iteration,entry will be set toNULL andindex will have a value less than or equal to max.

xa_for_each_marked() is O(n.log(n)) whilexas_for_each_marked() is O(n).You have to handle your own locking withxas_for_each(), and if you haveto unlock after each iteration, it will also end up being O(n.log(n)).xa_for_each_marked() will spin if it hits a retry entry; if you intend tosee retry entries, you should use thexas_for_each_marked() iteratorinstead. Thexas_for_each_marked() iterator will expand into more inlinecode thanxa_for_each_marked().

Context

Any context. Takes and releases the RCU lock.

void*xa_store_bh(structxarray*xa,unsignedlongindex,void*entry,gfp_tgfp)¶: Store this entry in the XArray.

Parameters

structxarray*xa: XArray.
unsignedlongindex: Index into array.
void*entry: New entry.
gfp_tgfp: Memory allocation flags.

Description

This function is like callingxa_store() except it disables softirqswhile holding the array lock.

Context

Any context. Takes and releases the xa_lock whiledisabling softirqs.

Return

The old entry at this index orxa_err() if an error happened.

void*xa_store_irq(structxarray*xa,unsignedlongindex,void*entry,gfp_tgfp)¶: Store this entry in the XArray.

Parameters

structxarray*xa: XArray.
unsignedlongindex: Index into array.
void*entry: New entry.
gfp_tgfp: Memory allocation flags.

Description

This function is like callingxa_store() except it disables interruptswhile holding the array lock.

Context

Process context. Takes and releases the xa_lock whiledisabling interrupts.

Return

The old entry at this index orxa_err() if an error happened.

void*xa_erase_bh(structxarray*xa,unsignedlongindex)¶: Erase this entry from the XArray.

Parameters

structxarray*xa: XArray.
unsignedlongindex: Index of entry.

Description

After this function returns, loading fromindex will returnNULL.If the index is part of a multi-index entry, all indices will be erasedand none of the entries will be part of a multi-index entry.

Context

Any context. Takes and releases the xa_lock whiledisabling softirqs.

Return

The entry which used to be at this index.

void*xa_erase_irq(structxarray*xa,unsignedlongindex)¶: Erase this entry from the XArray.

Parameters

structxarray*xa: XArray.
unsignedlongindex: Index of entry.

Description

After this function returns, loading fromindex will returnNULL.If the index is part of a multi-index entry, all indices will be erasedand none of the entries will be part of a multi-index entry.

Context

Process context. Takes and releases the xa_lock whiledisabling interrupts.

Return

The entry which used to be at this index.

void*xa_cmpxchg(structxarray*xa,unsignedlongindex,void*old,void*entry,gfp_tgfp)¶: Conditionally replace an entry in the XArray.

Parameters

structxarray*xa: XArray.
unsignedlongindex: Index into array.
void*old: Old value to test against.
void*entry: New value to place in array.
gfp_tgfp: Memory allocation flags.

Description

If the entry atindex is the same asold, replace it withentry.If the return value is equal toold, then the exchange was successful.

Context

Any context. Takes and releases the xa_lock. May sleepif thegfp flags permit.

Return

The old value at this index orxa_err() if an error happened.

void*xa_cmpxchg_bh(structxarray*xa,unsignedlongindex,void*old,void*entry,gfp_tgfp)¶: Conditionally replace an entry in the XArray.

Parameters

structxarray*xa: XArray.
unsignedlongindex: Index into array.
void*old: Old value to test against.
void*entry: New value to place in array.
gfp_tgfp: Memory allocation flags.

Description

This function is like callingxa_cmpxchg() except it disables softirqswhile holding the array lock.

Context

Any context. Takes and releases the xa_lock whiledisabling softirqs. May sleep if thegfp flags permit.

Return

The old value at this index orxa_err() if an error happened.

void*xa_cmpxchg_irq(structxarray*xa,unsignedlongindex,void*old,void*entry,gfp_tgfp)¶: Conditionally replace an entry in the XArray.

Parameters

structxarray*xa: XArray.
unsignedlongindex: Index into array.
void*old: Old value to test against.
void*entry: New value to place in array.
gfp_tgfp: Memory allocation flags.

Description

This function is like callingxa_cmpxchg() except it disables interruptswhile holding the array lock.

Context

Process context. Takes and releases the xa_lock whiledisabling interrupts. May sleep if thegfp flags permit.

Return

The old value at this index orxa_err() if an error happened.

intxa_insert(structxarray*xa,unsignedlongindex,void*entry,gfp_tgfp)¶: Store this entry in the XArray unless another entry is already present.

Parameters

structxarray*xa: XArray.
unsignedlongindex: Index into array.
void*entry: New entry.
gfp_tgfp: Memory allocation flags.

Description

Inserting a NULL entry will store a reserved entry (likexa_reserve())if no entry is present. Inserting will fail if a reserved entry ispresent, even though loading from this index will return NULL.

Context

Any context. Takes and releases the xa_lock. May sleep ifthegfp flags permit.

Return

0 if the store succeeded. -EBUSY if another entry was present.-ENOMEM if memory could not be allocated.

intxa_insert_bh(structxarray*xa,unsignedlongindex,void*entry,gfp_tgfp)¶: Store this entry in the XArray unless another entry is already present.

Parameters

structxarray*xa: XArray.
unsignedlongindex: Index into array.
void*entry: New entry.
gfp_tgfp: Memory allocation flags.

Description

Inserting a NULL entry will store a reserved entry (likexa_reserve())if no entry is present. Inserting will fail if a reserved entry ispresent, even though loading from this index will return NULL.

Context

Any context. Takes and releases the xa_lock whiledisabling softirqs. May sleep if thegfp flags permit.

Return

0 if the store succeeded. -EBUSY if another entry was present.-ENOMEM if memory could not be allocated.

intxa_insert_irq(structxarray*xa,unsignedlongindex,void*entry,gfp_tgfp)¶: Store this entry in the XArray unless another entry is already present.

Parameters

structxarray*xa: XArray.
unsignedlongindex: Index into array.
void*entry: New entry.
gfp_tgfp: Memory allocation flags.

Description

Inserting a NULL entry will store a reserved entry (likexa_reserve())if no entry is present. Inserting will fail if a reserved entry ispresent, even though loading from this index will return NULL.

Context

Process context. Takes and releases the xa_lock whiledisabling interrupts. May sleep if thegfp flags permit.

Return

0 if the store succeeded. -EBUSY if another entry was present.-ENOMEM if memory could not be allocated.

intxa_alloc(structxarray*xa,u32*id,void*entry,structxa_limitlimit,gfp_tgfp)¶: Find somewhere to store this entry in the XArray.

Parameters

structxarray*xa: XArray.
u32*id: Pointer to ID.
void*entry: New entry.
structxa_limitlimit: Range of ID to allocate.
gfp_tgfp: Memory allocation flags.

Description

Finds an empty entry inxa betweenlimit.min andlimit.max,stores the index into theid pointer, then stores the entry atthat index. A concurrent lookup will not see an uninitialisedid.

Must only be operated on an xarray initialized with flag XA_FLAGS_ALLOC setinxa_init_flags().

Context

Any context. Takes and releases the xa_lock. May sleep ifthegfp flags permit.

Return

0 on success, -ENOMEM if memory could not be allocated or-EBUSY if there are no free entries inlimit.

intxa_alloc_bh(structxarray*xa,u32*id,void*entry,structxa_limitlimit,gfp_tgfp)¶: Find somewhere to store this entry in the XArray.

Parameters

structxarray*xa: XArray.
u32*id: Pointer to ID.
void*entry: New entry.
structxa_limitlimit: Range of ID to allocate.
gfp_tgfp: Memory allocation flags.

Description

Finds an empty entry inxa betweenlimit.min andlimit.max,stores the index into theid pointer, then stores the entry atthat index. A concurrent lookup will not see an uninitialisedid.

Must only be operated on an xarray initialized with flag XA_FLAGS_ALLOC setinxa_init_flags().

Context

Any context. Takes and releases the xa_lock whiledisabling softirqs. May sleep if thegfp flags permit.

Return

0 on success, -ENOMEM if memory could not be allocated or-EBUSY if there are no free entries inlimit.

intxa_alloc_irq(structxarray*xa,u32*id,void*entry,structxa_limitlimit,gfp_tgfp)¶: Find somewhere to store this entry in the XArray.

Parameters

structxarray*xa: XArray.
u32*id: Pointer to ID.
void*entry: New entry.
structxa_limitlimit: Range of ID to allocate.
gfp_tgfp: Memory allocation flags.

Description

Finds an empty entry inxa betweenlimit.min andlimit.max,stores the index into theid pointer, then stores the entry atthat index. A concurrent lookup will not see an uninitialisedid.

Must only be operated on an xarray initialized with flag XA_FLAGS_ALLOC setinxa_init_flags().

Context

Process context. Takes and releases the xa_lock whiledisabling interrupts. May sleep if thegfp flags permit.

Return

0 on success, -ENOMEM if memory could not be allocated or-EBUSY if there are no free entries inlimit.

intxa_alloc_cyclic(structxarray*xa,u32*id,void*entry,structxa_limitlimit,u32*next,gfp_tgfp)¶: Find somewhere to store this entry in the XArray.

Parameters

structxarray*xa: XArray.
u32*id: Pointer to ID.
void*entry: New entry.
structxa_limitlimit: Range of allocated ID.
u32*next: Pointer to next ID to allocate.
gfp_tgfp: Memory allocation flags.

Description

Finds an empty entry inxa betweenlimit.min andlimit.max,stores the index into theid pointer, then stores the entry atthat index. A concurrent lookup will not see an uninitialisedid.The search for an empty entry will start atnext and will wraparound if necessary.

Must only be operated on an xarray initialized with flag XA_FLAGS_ALLOC setinxa_init_flags().

Note that callers interested in whether wrapping has occurred shoulduse__xa_alloc_cyclic() instead.

Context

Any context. Takes and releases the xa_lock. May sleep ifthegfp flags permit.

Return

0 if the allocation succeeded, -ENOMEM if memory could not beallocated or -EBUSY if there are no free entries inlimit.

intxa_alloc_cyclic_bh(structxarray*xa,u32*id,void*entry,structxa_limitlimit,u32*next,gfp_tgfp)¶: Find somewhere to store this entry in the XArray.

Parameters

structxarray*xa: XArray.
u32*id: Pointer to ID.
void*entry: New entry.
structxa_limitlimit: Range of allocated ID.
u32*next: Pointer to next ID to allocate.
gfp_tgfp: Memory allocation flags.

Description

Must only be operated on an xarray initialized with flag XA_FLAGS_ALLOC setinxa_init_flags().

Note that callers interested in whether wrapping has occurred shoulduse__xa_alloc_cyclic() instead.

Context

Any context. Takes and releases the xa_lock whiledisabling softirqs. May sleep if thegfp flags permit.

Return

0 if the allocation succeeded, -ENOMEM if memory could not beallocated or -EBUSY if there are no free entries inlimit.

intxa_alloc_cyclic_irq(structxarray*xa,u32*id,void*entry,structxa_limitlimit,u32*next,gfp_tgfp)¶: Find somewhere to store this entry in the XArray.

Parameters

structxarray*xa: XArray.
u32*id: Pointer to ID.
void*entry: New entry.
structxa_limitlimit: Range of allocated ID.
u32*next: Pointer to next ID to allocate.
gfp_tgfp: Memory allocation flags.

Description

Must only be operated on an xarray initialized with flag XA_FLAGS_ALLOC setinxa_init_flags().

Note that callers interested in whether wrapping has occurred shoulduse__xa_alloc_cyclic() instead.

Context

Process context. Takes and releases the xa_lock whiledisabling interrupts. May sleep if thegfp flags permit.

Return

0 if the allocation succeeded, -ENOMEM if memory could not beallocated or -EBUSY if there are no free entries inlimit.

intxa_reserve(structxarray*xa,unsignedlongindex,gfp_tgfp)¶: Reserve this index in the XArray.

Parameters

structxarray*xa: XArray.
unsignedlongindex: Index into array.
gfp_tgfp: Memory allocation flags.

Description

Ensures there is somewhere to store an entry atindex in the array.If there is already something stored atindex, this function doesnothing. If there was nothing there, the entry is marked as reserved.Loading from a reserved entry returns aNULL pointer.

If you do not use the entry that you have reserved, callxa_release()orxa_erase() to free any unnecessary memory.

Context

Any context. Takes and releases the xa_lock.May sleep if thegfp flags permit.

Return

0 if the reservation succeeded or -ENOMEM if it failed.

intxa_reserve_bh(structxarray*xa,unsignedlongindex,gfp_tgfp)¶: Reserve this index in the XArray.

Parameters

structxarray*xa: XArray.
unsignedlongindex: Index into array.
gfp_tgfp: Memory allocation flags.

Description

A softirq-disabling version ofxa_reserve().

Context

Any context. Takes and releases the xa_lock whiledisabling softirqs.

Return

0 if the reservation succeeded or -ENOMEM if it failed.

intxa_reserve_irq(structxarray*xa,unsignedlongindex,gfp_tgfp)¶: Reserve this index in the XArray.

Parameters

structxarray*xa: XArray.
unsignedlongindex: Index into array.
gfp_tgfp: Memory allocation flags.

Description

An interrupt-disabling version ofxa_reserve().

Context

Process context. Takes and releases the xa_lock whiledisabling interrupts.

Return

0 if the reservation succeeded or -ENOMEM if it failed.

voidxa_release(structxarray*xa,unsignedlongindex)¶: Release a reserved entry.

Parameters

structxarray*xa: XArray.
unsignedlongindex: Index of entry.

Description

After callingxa_reserve(), you can call this function to release thereservation. If the entry atindex has been stored to, this functionwill do nothing.

boolxa_is_sibling(constvoid*entry)¶: Is the entry a sibling entry?

Parameters

constvoid*entry: Entry retrieved from the XArray

Return

true if the entry is a sibling entry.

boolxa_is_retry(constvoid*entry)¶: Is the entry a retry entry?

Parameters

constvoid*entry: Entry retrieved from the XArray

Return

true if the entry is a retry entry.

boolxa_is_advanced(constvoid*entry)¶: Is the entry only permitted for the advanced API?

Parameters

constvoid*entry: Entry to be stored in the XArray.

Return

true if the entry cannot be stored by the normal API.

xa_update_node_t¶: Typedef: A callback function from the XArray.

Syntax

voidxa_update_node_t(structxa_node*node)

Parameters

structxa_node*node: The node which is being processed

Description

This function is called every time the XArray updates the count ofpresent and value entries in a node. It allows advanced users tomaintain the private_list in the node.

Context

The xa_lock is held and interrupts may be disabled.Implementations should not drop the xa_lock, nor re-enableinterrupts.

XA_STATE¶

XA_STATE(name,array,index)

Declare an XArray operation state.

Parameters

name: Name of this operation state (usually xas).
array: Array to operate on.
index: Initial index of interest.

Description

Declare and initialise an xa_state on the stack.

XA_STATE_ORDER¶

XA_STATE_ORDER(name,array,index,order)

Declare an XArray operation state.

Parameters

name: Name of this operation state (usually xas).
array: Array to operate on.
index: Initial index of interest.
order: Order of entry.

Description

Declare and initialise an xa_state on the stack. This variant ofXA_STATE() allows you to specify the ‘order’ of the element youwant to operate on.`

intxas_error(conststructxa_state*xas)¶: Return an errno stored in the xa_state.

Parameters

conststructxa_state*xas: XArray operation state.

Return

0 if no error has been noted. A negative errno if one has.

voidxas_set_err(structxa_state*xas,longerr)¶: Note an error in the xa_state.

Parameters

structxa_state*xas: XArray operation state.
longerr: Negative error number.

Description

Only call this function with a negativeerr; zero or positive errorswill probably not behave the way you think they should. If you wantto clear the error from an xa_state, usexas_reset().

boolxas_invalid(conststructxa_state*xas)¶: Is the xas in a retry or error state?

Parameters

conststructxa_state*xas: XArray operation state.

Return

true if the xas cannot be used for operations.

boolxas_valid(conststructxa_state*xas)¶: Is the xas a valid cursor into the array?

Parameters

conststructxa_state*xas: XArray operation state.

Return

true if the xas can be used for operations.

boolxas_is_node(conststructxa_state*xas)¶: Does the xas point to a node?

Parameters

conststructxa_state*xas: XArray operation state.

Return

true if the xas currently references a node.

voidxas_reset(structxa_state*xas)¶: Reset an XArray operation state.

Parameters

structxa_state*xas: XArray operation state.

Description

Resets the error or walk state of thexas so future walks of thearray will start from the root. Use this if you have dropped thexarray lock and want to reuse the xa_state.

Context

Any context.

boolxas_retry(structxa_state*xas,constvoid*entry)¶: Retry the operation if appropriate.

Parameters

structxa_state*xas: XArray operation state.
constvoid*entry: Entry from xarray.

Description

The advanced functions may sometimes return an internal entry, such asa retry entry or a zero entry. This function sets up thexas to restartthe walk from the head of the array if needed.

Context

Any context.

Return

true if the operation needs to be retried.

void*xas_reload(structxa_state*xas)¶: Refetch an entry from the xarray.

Parameters

structxa_state*xas: XArray operation state.

Description

Use this function to check that a previously loaded entry still hasthe same value. This is useful for the lockless pagecache lookup wherewe walk the array with only the RCU lock to protect us, lock the page,then check that the page hasn’t moved since we looked it up.

The caller guarantees thatxas is still valid. If it may be in anerror or restart state, callxas_load() instead.

Return

The entry at this location in the xarray.

voidxas_set(structxa_state*xas,unsignedlongindex)¶: Set up XArray operation state for a different index.

Parameters

structxa_state*xas: XArray operation state.
unsignedlongindex: New index into the XArray.

Description

Move the operation state to refer to a different index. This willhave the effect of starting a walk from the top; seexas_next()to move to an adjacent index.

voidxas_advance(structxa_state*xas,unsignedlongindex)¶: Skip over sibling entries.

Parameters

structxa_state*xas: XArray operation state.
unsignedlongindex: Index of last sibling entry.

Description

Move the operation state to refer to the last sibling entry.This is useful for loops that normally want to see siblingentries but sometimes want to skip them. Usexas_set() if youwant to move to an index which is not part of this entry.

voidxas_set_order(structxa_state*xas,unsignedlongindex,unsignedintorder)¶: Set up XArray operation state for a multislot entry.

Parameters

structxa_state*xas: XArray operation state.
unsignedlongindex: Target of the operation.
unsignedintorder: Entry occupies 2^**order** indices.

voidxas_set_update(structxa_state*xas,xa_update_node_tupdate)¶: Set up XArray operation state for a callback.

Parameters

structxa_state*xas: XArray operation state.
xa_update_node_tupdate: Function to call when updating a node.

Description

The XArray can notify a caller after it has updated an xa_node.This is advanced functionality and is only needed by the pagecache and swap cache.

void*xas_next_entry(structxa_state*xas,unsignedlongmax)¶: Advance iterator to next present entry.

Parameters

structxa_state*xas: XArray operation state.
unsignedlongmax: Highest index to return.

Description

xas_next_entry() is an inline function to optimise xarray traversal forspeed. It is equivalent to callingxas_find(), and will callxas_find()for all the hard cases.

Return

The next present entry after the one currently referred to byxas.

void*xas_next_marked(structxa_state*xas,unsignedlongmax,xa_mark_tmark)¶: Advance iterator to next marked entry.

Parameters

structxa_state*xas: XArray operation state.
unsignedlongmax: Highest index to return.
xa_mark_tmark: Mark to search for.

Description

xas_next_marked() is an inline function to optimise xarray traversal forspeed. It is equivalent to callingxas_find_marked(), and will callxas_find_marked() for all the hard cases.

Return

The next marked entry after the one currently referred to byxas.

xas_for_each¶

xas_for_each(xas,entry,max)

Iterate over a range of an XArray.

Parameters

xas: XArray operation state.
entry: Entry retrieved from the array.
max: Maximum index to retrieve from array.

Description

The loop body will be executed for each entry present in the xarraybetween the current xas position andmax.entry will be set tothe entry retrieved from the xarray. It is safe to delete entriesfrom the array in the loop body. You should hold either the RCU lockor the xa_lock while iterating. If you need to drop the lock, callxas_pause() first.

xas_for_each_marked¶

xas_for_each_marked(xas,entry,max,mark)

Iterate over a range of an XArray.

Parameters

xas: XArray operation state.
entry: Entry retrieved from the array.
max: Maximum index to retrieve from array.
mark: Mark to search for.

Description

The loop body will be executed for each marked entry in the xarraybetween the current xas position andmax.entry will be set tothe entry retrieved from the xarray. It is safe to delete entriesfrom the array in the loop body. You should hold either the RCU lockor the xa_lock while iterating. If you need to drop the lock, callxas_pause() first.

xas_for_each_conflict¶

xas_for_each_conflict(xas,entry)

Iterate over a range of an XArray.

Parameters

xas: XArray operation state.
entry: Entry retrieved from the array.

Description

The loop body will be executed for each entry in the XArray thatlies within the range specified byxas. If the loop terminatesnormally,entry will beNULL. The user may break out of the loop,which will leaveentry set to the conflicting entry. The callermay also callxa_set_err() to exit the loop while setting an errorto record the reason.

void*xas_prev(structxa_state*xas)¶: Move iterator to previous index.

Parameters

structxa_state*xas: XArray operation state.

Description

If thexas was in an error state, it will remain in an error stateand this function will returnNULL. If thexas has never been walked,it will have the effect of callingxas_load(). Otherwise one will besubtracted from the index and the state will be walked to the correctlocation in the array for the next operation.

If the iterator was referencing index 0, this function wrapsaround toULONG_MAX.

Return

The entry at the new index. This may beNULL or an internalentry.

void*xas_next(structxa_state*xas)¶: Move state to next index.

Parameters

structxa_state*xas: XArray operation state.

Description

If thexas was in an error state, it will remain in an error stateand this function will returnNULL. If thexas has never been walked,it will have the effect of callingxas_load(). Otherwise one will beadded to the index and the state will be walked to the correctlocation in the array for the next operation.

If the iterator was referencing indexULONG_MAX, this function wrapsaround to 0.

Return

The entry at the new index. This may beNULL or an internalentry.

void*xas_load(structxa_state*xas)¶: Load an entry from the XArray (advanced).

Parameters

structxa_state*xas: XArray operation state.

Description

Usually walks thexas to the appropriate state to load the entrystored at xa_index. However, it will do nothing and returnNULL ifxas is in an error state.xas_load() will never expand the tree.

If the xa_state is set up to operate on a multi-index entry,xas_load()may returnNULL or an internal entry, even if there are entriespresent within the range specified byxas.

Context

Any context. The caller should hold the xa_lock or the RCU lock.

Return

Usually an entry in the XArray, but see description for exceptions.

boolxas_nomem(structxa_state*xas,gfp_tgfp)¶: Allocate memory if needed.

Parameters

structxa_state*xas: XArray operation state.
gfp_tgfp: Memory allocation flags.

Description

If we need to add new nodes to the XArray, we try to allocate memorywith GFP_NOWAIT while holding the lock, which will usually succeed.If it fails,xas is flagged as needing memory to continue. The callershould drop the lock and callxas_nomem(). Ifxas_nomem() succeeds,the caller should retry the operation.

Forward progress is guaranteed as one node is allocated here andstored in the xa_state where it will be found byxas_alloc(). Morenodes will likely be found in the slab allocator, but we do not tiethem up here.

Return

true if memory was needed, and was successfully allocated.

voidxas_free_nodes(structxa_state*xas,structxa_node*top)¶: Free this node and all nodes that it references

Parameters

structxa_state*xas: Array operation state.
structxa_node*top: Node to free

Description

This node has been removed from the tree. We must now free it and allof its subnodes. There may be RCU walkers with references into the tree,so we must replace all entries with retry markers.

voidxas_create_range(structxa_state*xas)¶: Ensure that stores to this range will succeed

Parameters

structxa_state*xas: XArray operation state.

Description

Creates all of the slots in the range covered byxas. Setsxas tocreate single-index entries and positions it at the beginning of therange. This is for the benefit of users which have not yet beenconverted to use multi-index entries.

void*xas_store(structxa_state*xas,void*entry)¶: Store this entry in the XArray.

Parameters

structxa_state*xas: XArray operation state.
void*entry: New entry.

Description

Ifxas is operating on a multi-index entry, the entry returned by thisfunction is essentially meaningless (it may be an internal entry or itmay beNULL, even if there are non-NULL entries at some of the indicescovered by the range). This is not a problem for any current users,and can be changed if needed.

Return

The old entry at this index.

boolxas_get_mark(conststructxa_state*xas,xa_mark_tmark)¶: Returns the state of this mark.

Parameters

conststructxa_state*xas: XArray operation state.
xa_mark_tmark: Mark number.

Return

true if the mark is set, false if the mark is clear orxasis in an error state.

voidxas_set_mark(conststructxa_state*xas,xa_mark_tmark)¶: Sets the mark on this entry and its parents.

Parameters

conststructxa_state*xas: XArray operation state.
xa_mark_tmark: Mark number.

Description

Sets the specified mark on this entry, and walks up the tree setting iton all the ancestor entries. Does nothing ifxas has not been walked toan entry, or is in an error state.

voidxas_clear_mark(conststructxa_state*xas,xa_mark_tmark)¶: Clears the mark on this entry and its parents.

Parameters

conststructxa_state*xas: XArray operation state.
xa_mark_tmark: Mark number.

Description

Clears the specified mark on this entry, and walks back to the headattempting to clear it on all the ancestor entries. Does nothing ifxas has not been walked to an entry, or is in an error state.

voidxas_init_marks(conststructxa_state*xas)¶: Initialise all marks for the entry

Parameters

conststructxa_state*xas: Array operations state.

Description

Initialise all marks for the entry specified byxas. If we’re trackingfree entries with a mark, we need to set it on all entries. All othermarks are cleared.

This implementation is not as efficient as it could be; we may walkup the tree multiple times.

voidxas_split_alloc(structxa_state*xas,void*entry,unsignedintorder,gfp_tgfp)¶: Allocate memory for splitting an entry.

Parameters

structxa_state*xas: XArray operation state.
void*entry: New entry which will be stored in the array.
unsignedintorder: Current entry order.
gfp_tgfp: Memory allocation flags.

Description

This function should be called before callingxas_split().If necessary, it will allocate new nodes (and fill them withentry)to prepare for the upcoming split of an entry oforder size intoentries of the order stored in thexas.

Context

May sleep ifgfp flags permit.

voidxas_split(structxa_state*xas,void*entry,unsignedintorder)¶: Split a multi-index entry into smaller entries.

Parameters

structxa_state*xas: XArray operation state.
void*entry: New entry to store in the array.
unsignedintorder: Current entry order.

Description

The size of the new entries is set inxas. The value inentry iscopied to all the replacement entries.

Context

Any context. The caller should hold the xa_lock.

unsignedintxas_try_split_min_order(unsignedintorder)¶: Minimal split orderxas_try_split() can accept

Parameters

unsignedintorder: Current entry order.

Description

xas_try_split() can split a multi-index entry to smaller thanorder - 1 ifno new xa_node is needed. This function provides the minimal orderxas_try_split() supports.

Return

the minimal orderxas_try_split() supports

Context

Any context.

voidxas_try_split(structxa_state*xas,void*entry,unsignedintorder)¶: Try to split a multi-index entry.

Parameters

structxa_state*xas: XArray operation state.
void*entry: New entry to store in the array.
unsignedintorder: Current entry order.

Description

The size of the new entries is set inxas. The value inentry iscopied to all the replacement entries. If and only if one new xa_node isneeded, the function will use GFP_NOWAIT to get one if xas->xa_alloc isNULL. If more new xa_node are needed, the function gives EINVAL error.

NOTE

usexas_try_split_min_order() to get next split order instead oforder - 1 if you want to minmizexas_try_split() calls.

Context

Any context. The caller should hold the xa_lock.

voidxas_pause(structxa_state*xas)¶: Pause a walk to drop a lock.

Parameters

structxa_state*xas: XArray operation state.

Description

Some users need to pause a walk and drop the lock they’re holding inorder to yield to a higher priority thread or carry out an operationon an entry. Those users should call this function before they dropthe lock. It resets thexas to be suitable for the next iterationof the loop after the user has reacquired the lock. If most entriesfound during a walk require you to callxas_pause(), thexa_for_each()iterator may be more appropriate.

Note thatxas_pause() only works for forward iteration. If a user needsto pause a reverse iteration, we will need axas_pause_rev().

void*xas_find(structxa_state*xas,unsignedlongmax)¶: Find the next present entry in the XArray.

Parameters

structxa_state*xas: XArray operation state.
unsignedlongmax: Highest index to return.

Description

If thexas has not yet been walked to an entry, return the entrywhich has an index >= xas.xa_index. If it has been walked, the entrycurrently being pointed at has been processed, and so we move to thenext entry.

If no entry is found and the array is smaller thanmax, the iteratoris set to the smallest index not yet in the array. This allowsxasto be immediately passed toxas_store().

Return

The entry, if found, otherwiseNULL.

void*xas_find_marked(structxa_state*xas,unsignedlongmax,xa_mark_tmark)¶: Find the next marked entry in the XArray.

Parameters

structxa_state*xas: XArray operation state.
unsignedlongmax: Highest index to return.
xa_mark_tmark: Mark number to search for.

Description

If thexas has not yet been walked to an entry, return the marked entrywhich has an index >= xas.xa_index. If it has been walked, the entrycurrently being pointed at has been processed, and so we return thefirst marked entry with an index > xas.xa_index.

If no marked entry is found and the array is smaller thanmax,xas isset to the bounds state and xas->xa_index is set to the smallest indexnot yet in the array. This allowsxas to be immediately passed toxas_store().

If no entry is found beforemax is reached,xas is set to the restartstate.

Return

The entry, if found, otherwiseNULL.

void*xas_find_conflict(structxa_state*xas)¶: Find the next present entry in a range.

Parameters

structxa_state*xas: XArray operation state.

Description

Thexas describes both a range and a position within that range.

Context

Any context. Expects xa_lock to be held.

Return

The next entry in the range covered byxas orNULL.

void*xa_load(structxarray*xa,unsignedlongindex)¶: Load an entry from an XArray.

Parameters

structxarray*xa: XArray.
unsignedlongindex: index into array.

Context

Any context. Takes and releases the RCU lock.

Return

The entry atindex inxa.

void*__xa_erase(structxarray*xa,unsignedlongindex)¶: Erase this entry from the XArray while locked.

Parameters

structxarray*xa: XArray.
unsignedlongindex: Index into array.

Description

After this function returns, loading fromindex will returnNULL.If the index is part of a multi-index entry, all indices will be erasedand none of the entries will be part of a multi-index entry.

Context

Any context. Expects xa_lock to be held on entry.

Return

The entry which used to be at this index.

void*xa_erase(structxarray*xa,unsignedlongindex)¶: Erase this entry from the XArray.

Parameters

structxarray*xa: XArray.
unsignedlongindex: Index of entry.

Description

After this function returns, loading fromindex will returnNULL.If the index is part of a multi-index entry, all indices will be erasedand none of the entries will be part of a multi-index entry.

Context

Any context. Takes and releases the xa_lock.

Return

The entry which used to be at this index.

void*__xa_store(structxarray*xa,unsignedlongindex,void*entry,gfp_tgfp)¶: Store this entry in the XArray.

Parameters

structxarray*xa: XArray.
unsignedlongindex: Index into array.
void*entry: New entry.
gfp_tgfp: Memory allocation flags.

Description

You must already be holding the xa_lock when calling this function.It will drop the lock if needed to allocate memory, and then reacquireit afterwards.

Context

Any context. Expects xa_lock to be held on entry. Mayrelease and reacquire xa_lock ifgfp flags permit.

Return

The old entry at this index orxa_err() if an error happened.

void*xa_store(structxarray*xa,unsignedlongindex,void*entry,gfp_tgfp)¶: Store this entry in the XArray.

Parameters

structxarray*xa: XArray.
unsignedlongindex: Index into array.
void*entry: New entry.
gfp_tgfp: Memory allocation flags.

Description

After this function returns, loads from this index will returnentry.Storing into an existing multi-index entry updates the entry of every index.The marks associated withindex are unaffected unlessentry isNULL.

Context

Any context. Takes and releases the xa_lock.May sleep if thegfp flags permit.

Return

The old entry at this index on success, xa_err(-EINVAL) ifentrycannot be stored in an XArray, or xa_err(-ENOMEM) if memory allocationfailed.

void*__xa_cmpxchg(structxarray*xa,unsignedlongindex,void*old,void*entry,gfp_tgfp)¶: Conditionally replace an entry in the XArray.

Parameters

structxarray*xa: XArray.
unsignedlongindex: Index into array.
void*old: Old value to test against.
void*entry: New value to place in array.
gfp_tgfp: Memory allocation flags.

Description

You must already be holding the xa_lock when calling this function.It will drop the lock if needed to allocate memory, and then reacquireit afterwards.

If the entry atindex is the same asold, replace it withentry.If the return value is equal toold, then the exchange was successful.

Context

Any context. Expects xa_lock to be held on entry. Mayrelease and reacquire xa_lock ifgfp flags permit.

Return

The old value at this index orxa_err() if an error happened.

int__xa_insert(structxarray*xa,unsignedlongindex,void*entry,gfp_tgfp)¶: Store this entry in the XArray if no entry is present.

Parameters

structxarray*xa: XArray.
unsignedlongindex: Index into array.
void*entry: New entry.
gfp_tgfp: Memory allocation flags.

Description

Inserting a NULL entry will store a reserved entry (likexa_reserve())if no entry is present. Inserting will fail if a reserved entry ispresent, even though loading from this index will return NULL.

Context

Any context. Expects xa_lock to be held on entry. Mayrelease and reacquire xa_lock ifgfp flags permit.

Return

0 if the store succeeded. -EBUSY if another entry was present.-ENOMEM if memory could not be allocated.

void*xa_store_range(structxarray*xa,unsignedlongfirst,unsignedlonglast,void*entry,gfp_tgfp)¶: Store this entry at a range of indices in the XArray.

Parameters

structxarray*xa: XArray.
unsignedlongfirst: First index to affect.
unsignedlonglast: Last index to affect.
void*entry: New entry.
gfp_tgfp: Memory allocation flags.

Description

After this function returns, loads from any index betweenfirst andlast,inclusive will returnentry.Storing into an existing multi-index entry updates the entry of every index.The marks associated withindex are unaffected unlessentry isNULL.

Context

Process context. Takes and releases the xa_lock. May sleepif thegfp flags permit.

Return

NULL on success, xa_err(-EINVAL) ifentry cannot be stored inan XArray, or xa_err(-ENOMEM) if memory allocation failed.

intxas_get_order(structxa_state*xas)¶: Get the order of an entry.

Parameters

structxa_state*xas: XArray operation state.

Description

Called after xas_load, the xas should not be in an error state.The xas should not be pointing to a sibling entry.

Return

A number between 0 and 63 indicating the order of the entry.

intxa_get_order(structxarray*xa,unsignedlongindex)¶: Get the order of an entry.

Parameters

structxarray*xa: XArray.
unsignedlongindex: Index of the entry.

Return

A number between 0 and 63 indicating the order of the entry.

int__xa_alloc(structxarray*xa,u32*id,void*entry,structxa_limitlimit,gfp_tgfp)¶: Find somewhere to store this entry in the XArray.

Parameters

structxarray*xa: XArray.
u32*id: Pointer to ID.
void*entry: New entry.
structxa_limitlimit: Range for allocated ID.
gfp_tgfp: Memory allocation flags.

Description

Finds an empty entry inxa betweenlimit.min andlimit.max,stores the index into theid pointer, then stores the entry atthat index. A concurrent lookup will not see an uninitialisedid.

Must only be operated on an xarray initialized with flag XA_FLAGS_ALLOC setinxa_init_flags().

Context

Any context. Expects xa_lock to be held on entry. Mayrelease and reacquire xa_lock ifgfp flags permit.

Return

0 on success, -ENOMEM if memory could not be allocated or-EBUSY if there are no free entries inlimit.

int__xa_alloc_cyclic(structxarray*xa,u32*id,void*entry,structxa_limitlimit,u32*next,gfp_tgfp)¶: Find somewhere to store this entry in the XArray.

Parameters

structxarray*xa: XArray.
u32*id: Pointer to ID.
void*entry: New entry.
structxa_limitlimit: Range of allocated ID.
u32*next: Pointer to next ID to allocate.
gfp_tgfp: Memory allocation flags.

Description

Must only be operated on an xarray initialized with flag XA_FLAGS_ALLOC setinxa_init_flags().

Context

Any context. Expects xa_lock to be held on entry. Mayrelease and reacquire xa_lock ifgfp flags permit.

Return

0 if the allocation succeeded without wrapping. 1 if theallocation succeeded after wrapping, -ENOMEM if memory could not beallocated or -EBUSY if there are no free entries inlimit.

void__xa_set_mark(structxarray*xa,unsignedlongindex,xa_mark_tmark)¶: Set this mark on this entry while locked.

Parameters

structxarray*xa: XArray.
unsignedlongindex: Index of entry.
xa_mark_tmark: Mark number.

Description

Attempting to set a mark on aNULL entry does not succeed.

Context

Any context. Expects xa_lock to be held on entry.

void__xa_clear_mark(structxarray*xa,unsignedlongindex,xa_mark_tmark)¶: Clear this mark on this entry while locked.

Parameters

structxarray*xa: XArray.
unsignedlongindex: Index of entry.
xa_mark_tmark: Mark number.

Context

Any context. Expects xa_lock to be held on entry.

boolxa_get_mark(structxarray*xa,unsignedlongindex,xa_mark_tmark)¶: Inquire whether this mark is set on this entry.

Parameters

structxarray*xa: XArray.
unsignedlongindex: Index of entry.
xa_mark_tmark: Mark number.

Description

This function uses the RCU read lock, so the result may be out of dateby the time it returns. If you need the result to be stable, use a lock.

Context

Any context. Takes and releases the RCU lock.

Return

True if the entry atindex has this mark set, false if it doesn’t.

voidxa_set_mark(structxarray*xa,unsignedlongindex,xa_mark_tmark)¶: Set this mark on this entry.

Parameters

structxarray*xa: XArray.
unsignedlongindex: Index of entry.
xa_mark_tmark: Mark number.

Description

Attempting to set a mark on aNULL entry does not succeed.

Context

Process context. Takes and releases the xa_lock.

voidxa_clear_mark(structxarray*xa,unsignedlongindex,xa_mark_tmark)¶: Clear this mark on this entry.

Parameters

structxarray*xa: XArray.
unsignedlongindex: Index of entry.
xa_mark_tmark: Mark number.

Description

Clearing a mark always succeeds.

Context

Process context. Takes and releases the xa_lock.

void*xa_find(structxarray*xa,unsignedlong*indexp,unsignedlongmax,xa_mark_tfilter)¶: Search the XArray for an entry.

Parameters

structxarray*xa: XArray.
unsignedlong*indexp: Pointer to an index.
unsignedlongmax: Maximum index to search to.
xa_mark_tfilter: Selection criterion.

Description

Finds the entry inxa which matches thefilter, and has the lowestindex that is at leastindexp and no more thanmax.If an entry is found,indexp is updated to be the index of the entry.This function is protected by the RCU read lock, so it may not findentries which are being simultaneously added. It will not return anXA_RETRY_ENTRY; if you need to see retry entries, usexas_find().

Context

Any context. Takes and releases the RCU lock.

Return

The entry, if found, otherwiseNULL.

void*xa_find_after(structxarray*xa,unsignedlong*indexp,unsignedlongmax,xa_mark_tfilter)¶: Search the XArray for a present entry.

Parameters

structxarray*xa: XArray.
unsignedlong*indexp: Pointer to an index.
unsignedlongmax: Maximum index to search to.
xa_mark_tfilter: Selection criterion.

Description

Finds the entry inxa which matches thefilter and has the lowestindex that is aboveindexp and no more thanmax.If an entry is found,indexp is updated to be the index of the entry.This function is protected by the RCU read lock, so it may miss entrieswhich are being simultaneously added. It will not return anXA_RETRY_ENTRY; if you need to see retry entries, usexas_find().

Context

Any context. Takes and releases the RCU lock.

Return

The pointer, if found, otherwiseNULL.

unsignedintxa_extract(structxarray*xa,void**dst,unsignedlongstart,unsignedlongmax,unsignedintn,xa_mark_tfilter)¶: Copy selected entries from the XArray into a normal array.

Parameters

structxarray*xa: The source XArray to copy from.
void**dst: The buffer to copy entries into.
unsignedlongstart: The first index in the XArray eligible to be selected.
unsignedlongmax: The last index in the XArray eligible to be selected.
unsignedintn: The maximum number of entries to copy.
xa_mark_tfilter: Selection criterion.

Description

Copies up ton entries that matchfilter from the XArray. Thecopied entries will have indices betweenstart andmax, inclusive.

Thefilter may be an XArray mark value, in which case entries which aremarked with that mark will be copied. It may also beXA_PRESENT, inwhich case all entries which are notNULL will be copied.

The entries returned may not represent a snapshot of the XArray at amoment in time. For example, if another thread stores to index 5, thenindex 10, callingxa_extract() may return the old contents of index 5and the new contents of index 10. Indices not modified while thisfunction is running will not be skipped.

If you need stronger guarantees, holding the xa_lock across calls to thisfunction will prevent concurrent modification.

Context

Any context. Takes and releases the RCU lock.

Return

The number of entries copied.

voidxa_delete_node(structxa_node*node,xa_update_node_tupdate)¶: Private interface for workingset code.

Parameters

structxa_node*node: Node to be removed from the tree.
xa_update_node_tupdate: Function to call to update ancestor nodes.

Context

xa_lock must be held on entry and will not be released.

voidxa_destroy(structxarray*xa)¶: Free all internal data structures.

Parameters

structxarray*xa: XArray.

Description

After calling this function, the XArray is empty and has freed all memoryallocated for its internal data structures. You are responsible forfreeing the objects referenced by the XArray.

Context

Any context. Takes and releases the xa_lock, interrupt-safe.

Movatterモバイル変換

The Linux Kernel

Quick search

Contents

This Page

XArray¶

Overview¶

Normal API¶

Search Marks¶

Allocating XArrays¶

Memory allocation¶

Locking¶

Advanced API¶

Internal Entries¶

Additional functionality¶

Multi-Index Entries¶

Functions and structures¶