Here's the current state of the documentation for the XArray. Suggestions for improvement gratefully received. ====== XArray ====== Overview ======== The XArray is an array of ULONG_MAX entries. Each entry can be either a pointer, or an encoded value between 0 and LONG_MAX. It is efficient when the indices used are densely clustered; hashing the object and using the hash as the index will not perform well. A freshly-initialised XArray contains a NULL pointer at every index. There is no difference between an entry which has never been stored to and an entry which has most recently had NULL stored to it. Pointers to be stored in the XArray must have the bottom two bits clear (ie must point to something which is 4-byte aligned). This includes all objects allocated by calling :c:func:`kmalloc` and :c:func:`alloc_page`, but you cannot store pointers to arbitrary offsets within an object. The XArray does not support storing :c:func:`IS_ERR` pointers; some conflict with data values and others conflict with entries the XArray uses for its own purposes. If you need to store special values which cannot be confused with real kernel pointers, the values 4, 8, ... 4092 are available. Each non-NULL entry in the array has three bits associated with it called tags. Each tag may be flipped on or off independently of the others. You can search for entries with a given tag set. An unusual feature of the XArray is the ability to tie multiple entries together. Once stored to, looking up any entry in the range will give the same result as looking up any other entry in the range. Setting a tag on one entry will set it on all of them. Multiple entries can be explicitly split into smaller entries, or storing NULL into any entry will cause the XArray to forget about the tie. Normal API ========== Start by initialising an XArray, either with :c:func:`DEFINE_XARRAY` for statically allocated XArrays or :c:func:`xa_init` for dynamically allocated ones. You can then set entries using :c:func:`xa_store` and get entries using :c:func:`xa_load`. xa_store will overwrite a non-NULL entry with the new entry. It returns the previous entry stored at that index. You can conditionally replace an entry at an index by using :c:func:`xa_cmpxchg`. Like :c:func:`cmpxchg`, it will only succeed if the entry at that index has the 'old' value. It also returns the entry which was at that index; if it returns the same entry which was passed as 'old', then :c:func:`xa_cmpxchg` succeeded. If you want to store a pointer, you can do that directly. If you want to store an integer between 0 and LONG_MAX, you must first encode it using :c:func:`xa_mk_value`. When you retrieve an entry from the XArray, you can check whether it is a data value by calling :c:func:`xa_is_value`, and convert it back to an integer by calling :c:func:`xa_to_value`. You can enquire whether a tag is set on an entry by using :c:func:`xa_get_tag`. If the entry is not NULL, you can set a tag on it by using :c:func:`xa_set_tag` and remove the tag from an entry by calling :c:func:`xa_clear_tag`. You can ask whether any entry in the XArray has a particular tag set by calling :c:func:`xa_tagged`. You can copy entries out of the XArray into a plain array by calling :c:func:`xa_get_entries` and copy tagged entries by calling :c:func:`xa_get_tagged`. Or you can iterate over the non-NULL entries in place in the XArray by calling :c:func:`xa_for_each`. You may prefer to use :c:func:`xa_find` or :c:func:`xa_next` to move to the next present entry in the XArray. Finally, you can remove all entries from an XArray by calling :c:func:`xa_destroy`. If the XArray entries are pointers, you may wish to free the entries first. You can do this by iterating over all non-NULL entries in When using the Normal API, you do not have to worry about locking. The XArray uses RCU and an irq-safe spinlock to synchronise access to the XArray: No lock needed: * :c:func:`xa_empty` * :c:func:`xa_tagged` Takes RCU read lock: * :c:func:`xa_load` * :c:func:`xa_for_each` * :c:func:`xa_find` * :c:func:`xa_next` * :c:func:`xa_get_entries` * :c:func:`xa_get_tagged` * :c:func:`xa_get_tag` Takes xa_lock internally: * :c:func:`xa_store` * :c:func:`xa_cmpxchg` * :c:func:`xa_destroy` * :c:func:`xa_set_tag` * :c:func:`xa_clear_tag` The :c:func:`xa_store` and :c:func:`xa_cmpxchg` functions take a gfp_t parameter in case the XArray needs to allocate memory to store this entry. If the entry being stored is NULL, no memory allocation needs to be performed, and the GFP flags specified here will be ignored. Advanced API ============ The advanced API offers more flexibility and better performance at the cost 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 required to use the xa_lock while modifying the array. You can choose whether to use the xa_lock or the RCU lock while doing read-only operations on the array. The advanced API is based around the xa_state. This is an opaque data structure which you declare on the stack using the :c:func:`XA_STATE` macro. This macro initialises the xa_state ready to start walking around the XArray. It is used as a cursor to maintain the position in the XArray and let you compose various operations together without having to restart from the top every time. The xa_state is also used to store errors. If an operation fails, it calls :c:func:`xas_set_err` to note the error. All operations check whether the xa_state is in an error state before proceeding, so there's no need for you to check for an error after each call; you can make multiple calls in succession and only check at a convenient point. The only error currently generated by the xarray code itself is ENOMEM, but it supports arbitrary errors in case you want to call :c:func:`xas_set_err` yourself. If the xa_state is holding an ENOMEM error, :c:func:`xas_nomem` will attempt to allocate a single xa_node using the specified gfp flags and store it in the xa_state for the next attempt. The idea is that you take the xa_lock, attempt the operation and drop the lock. Then you allocate memory if there was a memory allocation failure and retry the operation. You must call :c:func:`xas_destroy` if you call :c:func:`xas_nomem` in case it's not necessary to use the memory that was allocated. When using the advanced API, it's possible to see internal entries in the XArray. You should never see an :c:func:`xa_is_node` entry, but you may see other internal entries, including sibling entries, skip entries and retry entries. The :c:func:`xas_retry` function is a useful helper function for handling internal entries, particularly in the middle of iterations. Functions ========= .. kernel-doc:: include/linux/xarray.h .. kernel-doc:: lib/xarray.c
