Re: XArray documentation

[Matthew Wilcox <willy@infradead.org>]

On Thu, Nov 23, 2017 at 09:30:21PM -0700, Andreas Dilger wrote:
> > 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.

We could do something along those lines.  It's not something anybody's
trying to do with the radix tree today, but I wanted to document it
just in case anybody got a clever idea in the future.  Another source
of ambiguity that I didn't mention is that xa_store() can return
ERR_PTR(-ENOMEM), so if we encode the xarray-error-pointers in some
way, they have to be distinguishable from errors returned by the xa_*
functions.  There's no ambiguity when using the xas_ functions as they
signal errors in the xa_state.

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

The same way the radix tree does it -- there are three bitfields in each
node.  So all your PAGECACHE_DIRTY tags are stored in the same bitfield.

(I'm taking these two questions as request for more information on the
implementation, which I don't want to put in this document.  I want
this to be the users manual.  I think the appropriate place to put this
information is in source code comments.)

> > 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() ?

I swear I wrote that ... editing error.  New paragraph:

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 the :c:func:`xa_for_each` iterator.

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

Fair point -- if xas_nomem() fails to allocate memory, it'll return 'false'
to indicate not to bother retrying the operation.

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

That was earlier in the document:

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

> How do you know if the allocated
> memory was needed, or is it always safe to call xas_destroy?

It's always safe to call xas_destroy.

> Is the
> allocated memory always consumed if xa_store/xa_cmpxchg are called?

Usually.  If another process added the same node that we were trying to
store to, we won't allocate memory.

> What if there was another process that also added the same entry while
> the xa_lock was dropped?

We'll overwrite it.

I've rewritten this whole section.  Thanks for the feedback!

The xa_state is also used to store errors.  You can call
:c:func:`xas_error` to retrieve 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, calling :c:func:`xas_nomem`
will attempt to allocate more memory using the specified gfp flags and
cache 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.  The operation
attempts to allocate memory while holding the lock, but it is more
likely to fail.  Once you have dropped the lock, :c:func:`xas_nomem`
can try harder to allocate more memory.  It will return ``true`` if it
is worth retrying the operation (ie that there was a memory error *and*
more memory was allocated.  You must call :c:func:`xas_destroy` if you
call :c:func:`xas_nomem` in case memory was allocated and then turned
out not to be needed.

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

I know I chose the right name for that function, since you guessed it :-)

I've rewritten this whole section.  I'll post the updated document in a bit.