Re: XArray documentation

[Andreas Dilger]

On Nov 23, 2017, at 6:16 PM, Matthew Wilcox <willy@xxxxxxxxxxxxx> wrote:
> 
> 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.

Thought - if storing error values into the XArray in addition to regular
pointers is important for some use case, it would be easy to make
"ERR_PTR_XA()", "PTR_ERR_XA()", and "IS_ERR_XA()" macros that just shift
the error values up and down by two bits to avoid the conflict.  That
would still allow error values up (down) to -1023 to be stored without
any chance of a pointer conflict, which should be enough.

> 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.

How can it be 3 tag bits, if the pointers only need to be 4-byte aligned?

> 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

... the XArray using xa_for_each() ?

> 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

.. calling :c:func:`xas_nomem` ... ?

> 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

... then you try to allocate ...

> 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.

This last sentence is not totally clear.  How about:

If you called :c:func:`xas_nomem` to allocate memory, but didn't need
to use the memory for some reason, you need to call :c:func:`xas_destroy`
to free the allocated memory.


The question is where the "allocated memory" is stored, if it isn't in
the XArray?  Is it in the XA_STATE?  How do you know if the allocated
memory was needed, or is it always safe to call xas_destroy?  Is the
allocated memory always consumed if xa_store/xa_cmpxchg are called?
What if there was another process that also added the same entry while
the xa_lock was dropped?

> 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.

How do you know if a returned value is an "internal entry"?  Is there
some "xas_is_internal()" macro/function that tells you this?

> Functions
> =========
> 
> .. kernel-doc:: include/linux/xarray.h
> .. kernel-doc:: lib/xarray.c


Cheers, Andreas

Attachment: signature.asc
Description: Message signed with OpenPGP