[PATCH] xarray: Document erasing entries during iteration

[PATCH] xarray: Document erasing entries during iteration

[Tobin C. Harding]

The XArray is, in a way, a replacement data structure for linked lists,
as such, on first use developers may wonder if it is safe to remove
items while iterating over the array.

For example, this is fine:

	DEFINE_XARRAY(things);

	void cleanup()
	{
		struct thing *thing;
		unsigned long index;

		xa_for_each(&things, index, thing)
			xa_erase(&things, index);
	}

Document this feature explicitly in the docs and also for the macro
definition.

Signed-off-by: Tobin C. Harding <tobin@kernel.org>
---

Hi Willy,

I had my first go using the XArray today and during that I wondered if
it was safe to remove items during iteration.  Conceptually it seems
fine and it seemed to work just fine in code - is this something people
should not be doing for any reason?  Is this the best way to traverse
the tree and get every thing just to erase it?  Are we even supposed to
be thinking this is a tree or should we just be thinking it is an array?

(As you might have guessed I _still_ don't know exactly how a radix tree
works :)

Oh, and FTR the XArray is hot - good effort man.

thanks,
Tobin.


 Documentation/core-api/xarray.rst | 3 ++-
 include/linux/xarray.h            | 2 ++
 2 files changed, 4 insertions(+), 1 deletion(-)

diff --git a/Documentation/core-api/xarray.rst b/Documentation/core-api/xarray.rst
index 5d54b27c6eba..2578e0bdaa17 100644
--- a/Documentation/core-api/xarray.rst
+++ b/Documentation/core-api/xarray.rst
@@ -97,7 +97,8 @@ You can copy entries out of the XArray into a plain array by calling
 :c:func:`xa_extract`.  Or you can iterate over the present entries in
 the XArray by calling :c:func:`xa_for_each`.  You may prefer to use
 :c:func:`xa_find` or :c:func:`xa_find_after` to move to the next present
-entry in the XArray.
+entry in the XArray.  It is safe to call :c:func:`xa_release` on entries
+as you iterate over the array using :c:func:`xa_for_each`.
 
 Calling :c:func:`xa_store_range` stores the same entry in a range
 of indices.  If you do this, some of the other operations will behave
diff --git a/include/linux/xarray.h b/include/linux/xarray.h
index 5d9d318bcf7a..1f8974281a0a 100644
--- a/include/linux/xarray.h
+++ b/include/linux/xarray.h
@@ -407,6 +407,8 @@ static inline bool xa_marked(const struct xarray *xa, xa_mark_t mark)
  * you should use the xas_for_each() iterator instead.  The xas_for_each()
  * iterator will expand into more inline code than xa_for_each().
  *
+ * It is safe to erase entries from the XArray as you iterate over it.
+ *
  * Context: Any context.  Takes and releases the RCU lock.
  */
 #define xa_for_each(xa, index, entry) \
-- 
2.20.1

Re: [PATCH] xarray: Document erasing entries during iteration

[Matthew Wilcox]

On Tue, Feb 12, 2019 at 06:29:58PM +1100, Tobin C. Harding wrote:
> I had my first go using the XArray today and during that I wondered if
> it was safe to remove items during iteration.  Conceptually it seems
> fine and it seemed to work just fine in code - is this something people
> should not be doing for any reason?  Is this the best way to traverse
> the tree and get every thing just to erase it?  Are we even supposed to
> be thinking this is a tree or should we just be thinking it is an array?

You should be thinking it's an array.  I've done everything I can to
hide the fact that it's implemented as a tree because it's conceptually
an array.

The xa_for_each() iterator is designed to be extremely robust, at the
expense of some performance.  The only state it keeps is the @index,
so you can do anything you like to the XArray during the iteration.

It's definitely worth being clearer in the documentation, for
the benefit of people who're wondering what the equivalent of
list_for_each_entry_safe() is.  So I'll apply this patch in a day or
two unless anybody has further comment on it.

> (As you might have guessed I _still_ don't know exactly how a radix tree
> works :)

That is _fine_.  As you know I hope to get rid of the radix tree soon ;-)

> Oh, and FTR the XArray is hot - good effort man.
> 
> thanks,
> Tobin.
> 
> 
>  Documentation/core-api/xarray.rst | 3 ++-
>  include/linux/xarray.h            | 2 ++
>  2 files changed, 4 insertions(+), 1 deletion(-)
> 
> diff --git a/Documentation/core-api/xarray.rst b/Documentation/core-api/xarray.rst
> index 5d54b27c6eba..2578e0bdaa17 100644
> --- a/Documentation/core-api/xarray.rst
> +++ b/Documentation/core-api/xarray.rst
> @@ -97,7 +97,8 @@ You can copy entries out of the XArray into a plain array by calling
>  :c:func:`xa_extract`.  Or you can iterate over the present entries in
>  the XArray by calling :c:func:`xa_for_each`.  You may prefer to use
>  :c:func:`xa_find` or :c:func:`xa_find_after` to move to the next present
> -entry in the XArray.
> +entry in the XArray.  It is safe to call :c:func:`xa_release` on entries
> +as you iterate over the array using :c:func:`xa_for_each`.

that's spelled `xa_erase` ;-)

>  Calling :c:func:`xa_store_range` stores the same entry in a range
>  of indices.  If you do this, some of the other operations will behave
> diff --git a/include/linux/xarray.h b/include/linux/xarray.h
> index 5d9d318bcf7a..1f8974281a0a 100644
> --- a/include/linux/xarray.h
> +++ b/include/linux/xarray.h
> @@ -407,6 +407,8 @@ static inline bool xa_marked(const struct xarray *xa, xa_mark_t mark)
>   * you should use the xas_for_each() iterator instead.  The xas_for_each()
>   * iterator will expand into more inline code than xa_for_each().
>   *
> + * It is safe to erase entries from the XArray as you iterate over it.
> + *
>   * Context: Any context.  Takes and releases the RCU lock.
>   */
>  #define xa_for_each(xa, index, entry) \
> -- 
> 2.20.1
> 

Re: [PATCH] xarray: Document erasing entries during iteration

[Tobin C. Harding]

On Tue, Feb 12, 2019 at 06:29:58PM +1100, Tobin C. Harding wrote:
> The XArray is, in a way, a replacement data structure for linked lists,
> as such, on first use developers may wonder if it is safe to remove
> items while iterating over the array.
> 
> For example, this is fine:
> 
> 	DEFINE_XARRAY(things);
> 
> 	void cleanup()
> 	{
> 		struct thing *thing;
> 		unsigned long index;
> 
> 		xa_for_each(&things, index, thing)
> 			xa_erase(&things, index);
> 	}
> 
> Document this feature explicitly in the docs and also for the macro
> definition.
> 
> Signed-off-by: Tobin C. Harding <tobin@kernel.org>
> ---
> 
> Hi Willy,
> 
> I had my first go using the XArray today and during that I wondered if
> it was safe to remove items during iteration.  Conceptually it seems
> fine and it seemed to work just fine in code - is this something people
> should not be doing for any reason?  Is this the best way to traverse
> the tree and get every thing just to erase it?  Are we even supposed to
> be thinking this is a tree or should we just be thinking it is an array?
> 
> (As you might have guessed I _still_ don't know exactly how a radix tree
> works :)
> 
> Oh, and FTR the XArray is hot - good effort man.
> 
> thanks,
> Tobin.
> 
> 
>  Documentation/core-api/xarray.rst | 3 ++-
>  include/linux/xarray.h            | 2 ++
>  2 files changed, 4 insertions(+), 1 deletion(-)
> 
> diff --git a/Documentation/core-api/xarray.rst b/Documentation/core-api/xarray.rst
> index 5d54b27c6eba..2578e0bdaa17 100644
> --- a/Documentation/core-api/xarray.rst
> +++ b/Documentation/core-api/xarray.rst
> @@ -97,7 +97,8 @@ You can copy entries out of the XArray into a plain array by calling
>  :c:func:`xa_extract`.  Or you can iterate over the present entries in
>  the XArray by calling :c:func:`xa_for_each`.  You may prefer to use
>  :c:func:`xa_find` or :c:func:`xa_find_after` to move to the next present
> -entry in the XArray.
> +entry in the XArray.  It is safe to call :c:func:`xa_release` on entries
> +as you iterate over the array using :c:func:`xa_for_each`.

Re-reading documentation this line may be in the wrong place .

Perhaps it would be better added at the end of the 'Normal API' section?

	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 present
	entries in the XArray using the :c:func:`xa_for_each` iterator.  It is safe
	to call :c:func:`xa_erase` while iterating the array.

I'm a bit lazy when I read docs and soon as I find an answer I stop
reading (bad Tobin) so it might be nice to tie the first mention of
xa_for_each with the comment on xa_erase _and_ the section on
xa_destroy.  Man, writing docs is never as easy as it first appears.

Oh and I sent v2 already but it hasn't shown up in my inbox so replying
here on v1.

thanks,
Tobin.

Re: [PATCH] xarray: Document erasing entries during iteration

[Wei Yang]

On Tue, Feb 12, 2019 at 05:51:29AM -0800, Matthew Wilcox wrote:
>On Tue, Feb 12, 2019 at 06:29:58PM +1100, Tobin C. Harding wrote:
>> I had my first go using the XArray today and during that I wondered if
>> it was safe to remove items during iteration.  Conceptually it seems
>> fine and it seemed to work just fine in code - is this something people
>> should not be doing for any reason?  Is this the best way to traverse
>> the tree and get every thing just to erase it?  Are we even supposed to
>> be thinking this is a tree or should we just be thinking it is an array?
>
>You should be thinking it's an array.  I've done everything I can to
>hide the fact that it's implemented as a tree because it's conceptually
>an array.
>
>The xa_for_each() iterator is designed to be extremely robust, at the
>expense of some performance.  The only state it keeps is the @index,
>so you can do anything you like to the XArray during the iteration.
>
>It's definitely worth being clearer in the documentation, for
>the benefit of people who're wondering what the equivalent of
>list_for_each_entry_safe() is.  So I'll apply this patch in a day or
>two unless anybody has further comment on it.
>
>> (As you might have guessed I _still_ don't know exactly how a radix tree
>> works :)
>
>That is _fine_.  As you know I hope to get rid of the radix tree soon ;-)
>

You mean replace radix tree in whole kernel? That would be a big effort.

BTW, have we compared the performance difference?

>> Oh, and FTR the XArray is hot - good effort man.
>> 
>> thanks,
>> Tobin.
>> 
>> 
>>  Documentation/core-api/xarray.rst | 3 ++-
>>  include/linux/xarray.h            | 2 ++
>>  2 files changed, 4 insertions(+), 1 deletion(-)
>> 
>> diff --git a/Documentation/core-api/xarray.rst b/Documentation/core-api/xarray.rst
>> index 5d54b27c6eba..2578e0bdaa17 100644
>> --- a/Documentation/core-api/xarray.rst
>> +++ b/Documentation/core-api/xarray.rst
>> @@ -97,7 +97,8 @@ You can copy entries out of the XArray into a plain array by calling
>>  :c:func:`xa_extract`.  Or you can iterate over the present entries in
>>  the XArray by calling :c:func:`xa_for_each`.  You may prefer to use
>>  :c:func:`xa_find` or :c:func:`xa_find_after` to move to the next present
>> -entry in the XArray.
>> +entry in the XArray.  It is safe to call :c:func:`xa_release` on entries
>> +as you iterate over the array using :c:func:`xa_for_each`.
>
>that's spelled `xa_erase` ;-)
>
>>  Calling :c:func:`xa_store_range` stores the same entry in a range
>>  of indices.  If you do this, some of the other operations will behave
>> diff --git a/include/linux/xarray.h b/include/linux/xarray.h
>> index 5d9d318bcf7a..1f8974281a0a 100644
>> --- a/include/linux/xarray.h
>> +++ b/include/linux/xarray.h
>> @@ -407,6 +407,8 @@ static inline bool xa_marked(const struct xarray *xa, xa_mark_t mark)
>>   * you should use the xas_for_each() iterator instead.  The xas_for_each()
>>   * iterator will expand into more inline code than xa_for_each().
>>   *
>> + * It is safe to erase entries from the XArray as you iterate over it.
>> + *
>>   * Context: Any context.  Takes and releases the RCU lock.
>>   */
>>  #define xa_for_each(xa, index, entry) \
>> -- 
>> 2.20.1
>> 

-- 
Wei Yang
Help you, Help me

Re: [PATCH] xarray: Document erasing entries during iteration

[Matthew Wilcox]

On Wed, Feb 13, 2019 at 02:47:44PM +0000, Wei Yang wrote:
> On Tue, Feb 12, 2019 at 05:51:29AM -0800, Matthew Wilcox wrote:
> >That is _fine_.  As you know I hope to get rid of the radix tree soon ;-)
> 
> You mean replace radix tree in whole kernel? That would be a big effort.

Already mostly done.

http://git.infradead.org/users/willy/linux-dax.git/shortlog/refs/heads/xarray-conv

The only remaining user of the radix tree in that tree is the IDR.  So
now I'm converting the IDR users over to the XArray as well.


But that isn't what I was talking about.  At the moment, the radix
tree and the XArray use the same data structure.  It has good best-case
performance, but shockingly bad worst-case performance.  So we're looking
at replacing the data structure, which won't require changing any of the
users (maybe the page cache ... that has some pretty intimate knowledge
of exactly how the radix tree works).

> BTW, have we compared the performance difference?

It's in the noise.  Sometimes the XArray does a little better because
the APIs encourage the user to do things in a more efficient way.
Some of the users are improved just because the original author didn't
know about a more efficient way of doing what they wanted to do.

Re: [PATCH] xarray: Document erasing entries during iteration

[Wei Yang]

On Wed, Feb 13, 2019 at 08:12:58AM -0800, Matthew Wilcox wrote:
>On Wed, Feb 13, 2019 at 02:47:44PM +0000, Wei Yang wrote:
>> On Tue, Feb 12, 2019 at 05:51:29AM -0800, Matthew Wilcox wrote:
>> >That is _fine_.  As you know I hope to get rid of the radix tree soon ;-)
>> 
>> You mean replace radix tree in whole kernel? That would be a big effort.
>
>Already mostly done.
>
>http://git.infradead.org/users/willy/linux-dax.git/shortlog/refs/heads/xarray-conv
>
>The only remaining user of the radix tree in that tree is the IDR.  So
>now I'm converting the IDR users over to the XArray as well.
>

Wow, really a HUGE work.

>
>But that isn't what I was talking about.  At the moment, the radix
>tree and the XArray use the same data structure.  It has good best-case
>performance, but shockingly bad worst-case performance.  So we're looking
>at replacing the data structure, which won't require changing any of the
>users (maybe the page cache ... that has some pretty intimate knowledge
>of exactly how the radix tree works).
>

Two questions from my curiosity:

1. Why you come up the idea to replace radix tree with XArray even they
   use the same data structure?
2. The worst-case performance is related to the data structure itself?

>> BTW, have we compared the performance difference?
>
>It's in the noise.  Sometimes the XArray does a little better because
>the APIs encourage the user to do things in a more efficient way.
>Some of the users are improved just because the original author didn't
>know about a more efficient way of doing what they wanted to do.
>

So sometimes XArray does a little worse?

Why this happens whey XArray and radix tree has the same data structure?

Interesting.

-- 
Wei Yang
Help you, Help me

Re: [PATCH] xarray: Document erasing entries during iteration

[Matthew Wilcox]

On Thu, Feb 14, 2019 at 10:16:52PM +0000, Wei Yang wrote:
> On Wed, Feb 13, 2019 at 08:12:58AM -0800, Matthew Wilcox wrote:
> >The only remaining user of the radix tree in that tree is the IDR.  So
> >now I'm converting the IDR users over to the XArray as well.
> 
> Wow, really a HUGE work.

Yes ... but necessary.  Have to pay down the technical debt.

> >But that isn't what I was talking about.  At the moment, the radix
> >tree and the XArray use the same data structure.  It has good best-case
> >performance, but shockingly bad worst-case performance.  So we're looking
> >at replacing the data structure, which won't require changing any of the
> >users (maybe the page cache ... that has some pretty intimate knowledge
> >of exactly how the radix tree works).
> 
> Two questions from my curiosity:
> 
> 1. Why you come up the idea to replace radix tree with XArray even they
>    use the same data structure?

The radix tree API was just awful to use.  I tried to convert some users
with their own resizing-array-of-pointers to use the radix tree, and I
gave up in disgust.  I believe the XArray is much simpler to use.

> 2. The worst-case performance is related to the data structure itself?

Yes.  Consider the case where you store a pointer at its own address in
the data structure.  It'll allocate 11 nodes occupying one-and-a-half pages
of RAM in order to store a single pointer.

> >> BTW, have we compared the performance difference?
> >
> >It's in the noise.  Sometimes the XArray does a little better because
> >the APIs encourage the user to do things in a more efficient way.
> >Some of the users are improved just because the original author didn't
> >know about a more efficient way of doing what they wanted to do.
> 
> So sometimes XArray does a little worse?
> 
> Why this happens whey XArray and radix tree has the same data structure?
> 
> Interesting.

I'm not sure there are any cases where the XArray does worse.
Feel free to run your own measurements ... the test cases in
tools/testing/radix-tree can always do with being improved ;-) (that
directory is a bit misnamed as it now features tests for the radix tree,
IDR, IDA and XArray).

Re: [PATCH] xarray: Document erasing entries during iteration

[Wei Yang]

On Thu, Feb 14, 2019 at 02:33:00PM -0800, Matthew Wilcox wrote:
>On Thu, Feb 14, 2019 at 10:16:52PM +0000, Wei Yang wrote:
>> On Wed, Feb 13, 2019 at 08:12:58AM -0800, Matthew Wilcox wrote:
>> >The only remaining user of the radix tree in that tree is the IDR.  So
>> >now I'm converting the IDR users over to the XArray as well.
>> 
>> Wow, really a HUGE work.
>
>Yes ... but necessary.  Have to pay down the technical debt.
>
>> >But that isn't what I was talking about.  At the moment, the radix
>> >tree and the XArray use the same data structure.  It has good best-case
>> >performance, but shockingly bad worst-case performance.  So we're looking
>> >at replacing the data structure, which won't require changing any of the
>> >users (maybe the page cache ... that has some pretty intimate knowledge
>> >of exactly how the radix tree works).
>> 
>> Two questions from my curiosity:
>> 
>> 1. Why you come up the idea to replace radix tree with XArray even they
>>    use the same data structure?
>
>The radix tree API was just awful to use.  I tried to convert some users
>with their own resizing-array-of-pointers to use the radix tree, and I
>gave up in disgust.  I believe the XArray is much simpler to use.
>
>> 2. The worst-case performance is related to the data structure itself?
>
>Yes.  Consider the case where you store a pointer at its own address in
>the data structure.  It'll allocate 11 nodes occupying one-and-a-half pages
>of RAM in order to store a single pointer.
>

Thanks for your explanation :-)

>> >> BTW, have we compared the performance difference?
>> >
>> >It's in the noise.  Sometimes the XArray does a little better because
>> >the APIs encourage the user to do things in a more efficient way.
>> >Some of the users are improved just because the original author didn't
>> >know about a more efficient way of doing what they wanted to do.
>> 
>> So sometimes XArray does a little worse?
>> 
>> Why this happens whey XArray and radix tree has the same data structure?
>> 
>> Interesting.
>
>I'm not sure there are any cases where the XArray does worse.
>Feel free to run your own measurements ... the test cases in
>tools/testing/radix-tree can always do with being improved ;-) (that
>directory is a bit misnamed as it now features tests for the radix tree,
>IDR, IDA and XArray).

Sure, I will try to play with this.

-- 
Wei Yang
Help you, Help me