Skip to contentSkip to conversation

xarray: Document erasing entries during iteration

PATCH Superseded Tobin C. Harding 4 participants 8 messages Feb 12, 2019 – Feb 16, 2019

Subsystems (3)

v1 of 3 Superseded Latest is v3 →

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 xarray: Document erasing entries during iteration

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.

---

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(-)
Documentation/core-api/xarray.rst +2 -1
index 5d54b27c6eba..2578e0bdaa17 100644
@@ -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
include/linux/xarray.h +2 -0
index 5d9d318bcf7a..1f8974281a0a 100644
@@ -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) \
Signature · 1 line
2.20.1
maintainer
#1 lore raw
Quoted 6 lines · Tobin C. Harding

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.

Quoted 2 lines

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

Quoted 15 lines

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(-)
Documentation/core-api/xarray.rst +0 -0
index 5d54b27c6eba..2578e0bdaa17 100644

Documentation/core-api/xarray.rst You can copy entries out of the XArray into a plain array by calling · line 101

Quoted 6 lines
Documentation/core-api/xarray.rst +2 -1
@@ -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 ;-)

Quoted 18 lines
Documentation/core-api/xarray.rst +0 -0
 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
include/linux/xarray.h +2 -0
index 5d9d318bcf7a..1f8974281a0a 100644
@@ -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) \
Signature · 1 line
2.20.1
#2 lore raw
Quoted 21 lines · Matthew Wilcox
Quoted 6 lines · Tobin C. Harding

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.

Quoted 5 lines
Quoted 2 lines

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

Quoted 42 lines
Quoted 15 lines

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(-)
Documentation/core-api/xarray.rst +0 -0
index 5d54b27c6eba..2578e0bdaa17 100644

Documentation/core-api/xarray.rst You can copy entries out of the XArray into a plain array by calling · line 101

Quoted 6 lines
Documentation/core-api/xarray.rst +2 -1
@@ -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 ;-)

Quoted 18 lines
Documentation/core-api/xarray.rst +0 -0
 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
include/linux/xarray.h +2 -0
index 5d9d318bcf7a..1f8974281a0a 100644
@@ -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) \
Signature · 1 line
2.20.1
Signature · 2 lines
Wei Yang
Help you, Help me
maintainer
#3 lore raw
Quoted 4 lines · Wei Yang
Quoted 1 line · Matthew Wilcox

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

Quoted 1 line

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.

#4 lore raw
Quoted 4 lines · Matthew Wilcox
Quoted 3 lines · Wei Yang
Quoted 1 line · Matthew Wilcox

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

Quoted 9 lines
Quoted 1 line

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.

Quoted 8 lines

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?

Quoted 7 lines
Quoted 1 line

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.

Signature · 2 lines
Wei Yang
Help you, Help me
maintainer
#5 lore raw
Quoted 5 lines · Wei Yang
Quoted 2 lines · Matthew Wilcox

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.

Quoted 11 lines
Quoted 6 lines

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.

Quoted 1 line

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.

Quoted 7 lines
Quoted 6 lines
Quoted 1 line

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.

Quoted 5 lines

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

#6 lore raw
Quoted 25 lines · Matthew Wilcox
Quoted 5 lines · Wei Yang
Quoted 2 lines · Matthew Wilcox

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.

Quoted 11 lines
Quoted 6 lines

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.

Quoted 6 lines
Quoted 1 line

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

Quoted 11 lines
Quoted 11 lines
Quoted 6 lines
Quoted 1 line

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?

Quoted 7 lines
Quoted 1 line

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.

Signature · 2 lines
Wei Yang
Help you, Help me
#7 lore raw
In reply to Tobin C. Harding
Quoted 50 lines · 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.

---

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(-)
Documentation/core-api/xarray.rst +0 -0
index 5d54b27c6eba..2578e0bdaa17 100644

Documentation/core-api/xarray.rst You can copy entries out of the XArray into a plain array by calling · line 101

Quoted 6 lines
Documentation/core-api/xarray.rst +2 -1
@@ -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.