xarray: Document erasing entries during iteration
Subsystems (3)
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
@@ -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
@@ -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
Matthew Wilcox
maintainerQuoted 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
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
-0Calling :c:func:`xa_store_range` stores the same entry in a range of indices. If you do this, some of the other operations will behaveinclude/linux/xarray.h +2
-0@@ -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
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
-0Documentation/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
-0Calling :c:func:`xa_store_range` stores the same entry in a range of indices. If you do this, some of the other operations will behaveinclude/linux/xarray.h +2
-0@@ -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
Matthew Wilcox
maintainerQuoted 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.
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
Matthew Wilcox
maintainerQuoted 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).
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-treecan 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
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.
Signed-off-by Tobin C. Harding <[email protected]>---
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
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.