[PATCH 0/9] XArray: several cleanups

[PATCH 0/9] XArray: several cleanups

[Wei Yang]

Trivial cleanup for XArray.

No functional change.

Wei Yang (9):
  XArray: fix comment on Zero/Retry entry
  XArray: simplify the calculation of shift
  XArray: handle a NULL head by itself
  XArray: don't expect to have more nr_values than count
  XArray: entry in last level is not expected to be a node
  XArray: internal node is a xa_node when it is bigger than
    XA_ZERO_ENTRY
  XArray: the NULL xa_node condition is handled in xas_top
  XArray: take xas_error() handling for clearer logic
  XArray: adjust xa_offset till it gets the correct node

 include/linux/xarray.h |  6 +++---
 lib/xarray.c           | 31 ++++++++++++-------------------
 2 files changed, 15 insertions(+), 22 deletions(-)

-- 
2.23.0

[PATCH 1/9] XArray: fix comment on Zero/Retry entry

[Wei Yang]

Correct the comment according to definition.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
---
 include/linux/xarray.h | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/include/linux/xarray.h b/include/linux/xarray.h
index f73e1775ded0..a491653d8882 100644
--- a/include/linux/xarray.h
+++ b/include/linux/xarray.h
@@ -32,8 +32,8 @@
  * The following internal entries have a special meaning:
  *
  * 0-62: Sibling entries
- * 256: Zero entry
- * 257: Retry entry
+ * 256: Retry entry
+ * 257: Zero entry
  *
  * Errors are also represented as internal entries, but use the negative
  * space (-4094 to -2).  They're never stored in the slots array; only
-- 
2.23.0

Re: [PATCH 1/9] XArray: fix comment on Zero/Retry entry

[Matthew Wilcox]

On Mon, Mar 30, 2020 at 12:36:35PM +0000, Wei Yang wrote:
> Correct the comment according to definition.

You should work off linux-next; it's already fixed in commit
24a448b165253b6f2ab1e0bcdba9a733007681d6

Re: [PATCH 1/9] XArray: fix comment on Zero/Retry entry

[Wei Yang]

On Mon, Mar 30, 2020 at 05:46:13AM -0700, Matthew Wilcox wrote:
>On Mon, Mar 30, 2020 at 12:36:35PM +0000, Wei Yang wrote:
>> Correct the comment according to definition.
>
>You should work off linux-next; it's already fixed in commit
>24a448b165253b6f2ab1e0bcdba9a733007681d6

Oh, thanks

-- 
Wei Yang
Help you, Help me

[PATCH 2/9] XArray: simplify the calculation of shift

[Wei Yang]

When head is NULL, shift is calculated from max. Currently we use a loop
to detect how many XA_CHUNK_SHIFT is need to cover max.

To achieve this, we can get number of bits max expands and round it up
to XA_CHUNK_SHIFT.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
---
 lib/xarray.c | 6 +-----
 1 file changed, 1 insertion(+), 5 deletions(-)

diff --git a/lib/xarray.c b/lib/xarray.c
index 1d9fab7db8da..6454cf3f5b4c 100644
--- a/lib/xarray.c
+++ b/lib/xarray.c
@@ -560,11 +560,7 @@ static int xas_expand(struct xa_state *xas, void *head)
 	unsigned long max = xas_max(xas);
 
 	if (!head) {
-		if (max == 0)
-			return 0;
-		while ((max >> shift) >= XA_CHUNK_SIZE)
-			shift += XA_CHUNK_SHIFT;
-		return shift + XA_CHUNK_SHIFT;
+		return roundup(fls_long(max), XA_CHUNK_SHIFT);
 	} else if (xa_is_node(head)) {
 		node = xa_to_node(head);
 		shift = node->shift + XA_CHUNK_SHIFT;
-- 
2.23.0

Re: [PATCH 2/9] XArray: simplify the calculation of shift

[Matthew Wilcox]

On Mon, Mar 30, 2020 at 12:36:36PM +0000, Wei Yang wrote:
> When head is NULL, shift is calculated from max. Currently we use a loop
> to detect how many XA_CHUNK_SHIFT is need to cover max.
> 
> To achieve this, we can get number of bits max expands and round it up
> to XA_CHUNK_SHIFT.
> 
> Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
> ---
>  lib/xarray.c | 6 +-----
>  1 file changed, 1 insertion(+), 5 deletions(-)
> 
> diff --git a/lib/xarray.c b/lib/xarray.c
> index 1d9fab7db8da..6454cf3f5b4c 100644
> --- a/lib/xarray.c
> +++ b/lib/xarray.c
> @@ -560,11 +560,7 @@ static int xas_expand(struct xa_state *xas, void *head)
>  	unsigned long max = xas_max(xas);
>  
>  	if (!head) {
> -		if (max == 0)
> -			return 0;
> -		while ((max >> shift) >= XA_CHUNK_SIZE)
> -			shift += XA_CHUNK_SHIFT;
> -		return shift + XA_CHUNK_SHIFT;
> +		return roundup(fls_long(max), XA_CHUNK_SHIFT);

This doesn't give the same number.  Did you test this?

Consider max = 64.  The current code does:

shift = 0;
64 >> 0 >= 64 (true)
shift += 6;
64 >> 6 < 64
return 12

Your replacement does:

fls_long(64) = 6
roundup(6, 6) is 6.

Please be more careful.

Re: [PATCH 2/9] XArray: simplify the calculation of shift

[Wei Yang]

On Mon, Mar 30, 2020 at 06:20:28AM -0700, Matthew Wilcox wrote:
>On Mon, Mar 30, 2020 at 12:36:36PM +0000, Wei Yang wrote:
>> When head is NULL, shift is calculated from max. Currently we use a loop
>> to detect how many XA_CHUNK_SHIFT is need to cover max.
>> 
>> To achieve this, we can get number of bits max expands and round it up
>> to XA_CHUNK_SHIFT.
>> 
>> Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
>> ---
>>  lib/xarray.c | 6 +-----
>>  1 file changed, 1 insertion(+), 5 deletions(-)
>> 
>> diff --git a/lib/xarray.c b/lib/xarray.c
>> index 1d9fab7db8da..6454cf3f5b4c 100644
>> --- a/lib/xarray.c
>> +++ b/lib/xarray.c
>> @@ -560,11 +560,7 @@ static int xas_expand(struct xa_state *xas, void *head)
>>  	unsigned long max = xas_max(xas);
>>  
>>  	if (!head) {
>> -		if (max == 0)
>> -			return 0;
>> -		while ((max >> shift) >= XA_CHUNK_SIZE)
>> -			shift += XA_CHUNK_SHIFT;
>> -		return shift + XA_CHUNK_SHIFT;
>> +		return roundup(fls_long(max), XA_CHUNK_SHIFT);
>
>This doesn't give the same number.  Did you test this?
>
>Consider max = 64.  The current code does:
>
>shift = 0;
>64 >> 0 >= 64 (true)
>shift += 6;
>64 >> 6 < 64
>return 12
>
>Your replacement does:
>
>fls_long(64) = 6

fls_long(64) = 7

>roundup(6, 6) is 6.
>
>Please be more careful.

-- 
Wei Yang
Help you, Help me

[PATCH 3/9] XArray: handle a NULL head by itself

[Wei Yang]

For a NULL head, xas_expand() return the proper shift directly without
other handling.

Let's take this out to emphasize it is handled specially.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
---
 lib/xarray.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/lib/xarray.c b/lib/xarray.c
index 6454cf3f5b4c..1a092c87fca5 100644
--- a/lib/xarray.c
+++ b/lib/xarray.c
@@ -559,9 +559,10 @@ static int xas_expand(struct xa_state *xas, void *head)
 	unsigned int shift = 0;
 	unsigned long max = xas_max(xas);
 
-	if (!head) {
+	if (!head)
 		return roundup(fls_long(max), XA_CHUNK_SHIFT);
-	} else if (xa_is_node(head)) {
+
+	if (xa_is_node(head)) {
 		node = xa_to_node(head);
 		shift = node->shift + XA_CHUNK_SHIFT;
 	}
-- 
2.23.0

[PATCH 4/9] XArray: don't expect to have more nr_values than count

[Wei Yang]

The nr_values is expected to be smaller than count, use a more strict
boundary to do this check.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
---
 lib/xarray.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/xarray.c b/lib/xarray.c
index 1a092c87fca5..e08a0388a156 100644
--- a/lib/xarray.c
+++ b/lib/xarray.c
@@ -744,7 +744,7 @@ static void update_node(struct xa_state *xas, struct xa_node *node,
 	node->count += count;
 	node->nr_values += values;
 	XA_NODE_BUG_ON(node, node->count > XA_CHUNK_SIZE);
-	XA_NODE_BUG_ON(node, node->nr_values > XA_CHUNK_SIZE);
+	XA_NODE_BUG_ON(node, node->nr_values > node->count);
 	xas_update(xas, node);
 	if (count < 0)
 		xas_delete_node(xas);
-- 
2.23.0

[PATCH 5/9] XArray: entry in last level is not expected to be a node

[Wei Yang]

If an entry is at the last level, whose parent's shift is 0, it is not
expected to be a node. We can just leverage the xa_is_node() check to
break the loop instead of check shift additionally.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
---
 lib/xarray.c | 2 --
 1 file changed, 2 deletions(-)

diff --git a/lib/xarray.c b/lib/xarray.c
index e08a0388a156..0c5b44def3aa 100644
--- a/lib/xarray.c
+++ b/lib/xarray.c
@@ -238,8 +238,6 @@ void *xas_load(struct xa_state *xas)
 		if (xas->xa_shift > node->shift)
 			break;
 		entry = xas_descend(xas, node);
-		if (node->shift == 0)
-			break;
 	}
 	return entry;
 }
-- 
2.23.0

Re: [PATCH 5/9] XArray: entry in last level is not expected to be a node

[Matthew Wilcox]

On Mon, Mar 30, 2020 at 12:36:39PM +0000, Wei Yang wrote:
> If an entry is at the last level, whose parent's shift is 0, it is not
> expected to be a node. We can just leverage the xa_is_node() check to
> break the loop instead of check shift additionally.

I know you didn't run the test suite after making this change.

Re: [PATCH 5/9] XArray: entry in last level is not expected to be a node

[Wei Yang]

On Mon, Mar 30, 2020 at 05:48:42AM -0700, Matthew Wilcox wrote:
>On Mon, Mar 30, 2020 at 12:36:39PM +0000, Wei Yang wrote:
>> If an entry is at the last level, whose parent's shift is 0, it is not
>> expected to be a node. We can just leverage the xa_is_node() check to
>> break the loop instead of check shift additionally.
>
>I know you didn't run the test suite after making this change.

I did kernel build test, but not the test suite as you mentioned.

Would you mind sharing some steps on using the test suite? And which case you
think would trigger the problem?

-- 
Wei Yang
Help you, Help me

Re: [PATCH 5/9] XArray: entry in last level is not expected to be a node

[Matthew Wilcox]

On Mon, Mar 30, 2020 at 02:15:58PM +0000, Wei Yang wrote:
> On Mon, Mar 30, 2020 at 05:48:42AM -0700, Matthew Wilcox wrote:
> >On Mon, Mar 30, 2020 at 12:36:39PM +0000, Wei Yang wrote:
> >> If an entry is at the last level, whose parent's shift is 0, it is not
> >> expected to be a node. We can just leverage the xa_is_node() check to
> >> break the loop instead of check shift additionally.
> >
> >I know you didn't run the test suite after making this change.
> 
> I did kernel build test, but not the test suite as you mentioned.
> 
> Would you mind sharing some steps on using the test suite? And which case you
> think would trigger the problem?

cd tools/testing/radix-tree/; make; ./main

The IDR tests are the ones which are going to trigger on this.

Re: [PATCH 5/9] XArray: entry in last level is not expected to be a node

[Wei Yang]

On Mon, Mar 30, 2020 at 07:28:21AM -0700, Matthew Wilcox wrote:
>On Mon, Mar 30, 2020 at 02:15:58PM +0000, Wei Yang wrote:
>> On Mon, Mar 30, 2020 at 05:48:42AM -0700, Matthew Wilcox wrote:
>> >On Mon, Mar 30, 2020 at 12:36:39PM +0000, Wei Yang wrote:
>> >> If an entry is at the last level, whose parent's shift is 0, it is not
>> >> expected to be a node. We can just leverage the xa_is_node() check to
>> >> break the loop instead of check shift additionally.
>> >
>> >I know you didn't run the test suite after making this change.
>> 
>> I did kernel build test, but not the test suite as you mentioned.
>> 
>> Would you mind sharing some steps on using the test suite? And which case you
>> think would trigger the problem?
>
>cd tools/testing/radix-tree/; make; ./main
>
>The IDR tests are the ones which are going to trigger on this.

Thanks, I will give it a shot.

-- 
Wei Yang
Help you, Help me

Re: [PATCH 5/9] XArray: entry in last level is not expected to be a node

[Wei Yang]

On Mon, Mar 30, 2020 at 07:28:21AM -0700, Matthew Wilcox wrote:
>On Mon, Mar 30, 2020 at 02:15:58PM +0000, Wei Yang wrote:
>> On Mon, Mar 30, 2020 at 05:48:42AM -0700, Matthew Wilcox wrote:
>> >On Mon, Mar 30, 2020 at 12:36:39PM +0000, Wei Yang wrote:
>> >> If an entry is at the last level, whose parent's shift is 0, it is not
>> >> expected to be a node. We can just leverage the xa_is_node() check to
>> >> break the loop instead of check shift additionally.
>> >
>> >I know you didn't run the test suite after making this change.
>> 
>> I did kernel build test, but not the test suite as you mentioned.
>> 
>> Would you mind sharing some steps on using the test suite? And which case you
>> think would trigger the problem?
>
>cd tools/testing/radix-tree/; make; ./main
>

Hmm... I did a make on top of 5.6-rc6, it failed. Would you mind taking a look
into this?

>The IDR tests are the ones which are going to trigger on this.

-- 
Wei Yang
Help you, Help me

Re: [PATCH 5/9] XArray: entry in last level is not expected to be a node

[Matthew Wilcox]

On Tue, Mar 31, 2020 at 01:42:08PM +0000, Wei Yang wrote:
> On Mon, Mar 30, 2020 at 07:28:21AM -0700, Matthew Wilcox wrote:
> >On Mon, Mar 30, 2020 at 02:15:58PM +0000, Wei Yang wrote:
> >> On Mon, Mar 30, 2020 at 05:48:42AM -0700, Matthew Wilcox wrote:
> >> >On Mon, Mar 30, 2020 at 12:36:39PM +0000, Wei Yang wrote:
> >> >> If an entry is at the last level, whose parent's shift is 0, it is not
> >> >> expected to be a node. We can just leverage the xa_is_node() check to
> >> >> break the loop instead of check shift additionally.
> >> >
> >> >I know you didn't run the test suite after making this change.
> >> 
> >> I did kernel build test, but not the test suite as you mentioned.
> >> 
> >> Would you mind sharing some steps on using the test suite? And which case you
> >> think would trigger the problem?
> >
> >cd tools/testing/radix-tree/; make; ./main
> >
> 
> Hmm... I did a make on top of 5.6-rc6, it failed. Would you mind taking a look
> into this?

It works for me.  I run it almost every day.  What error did you see?

Re: [PATCH 5/9] XArray: entry in last level is not expected to be a node

[Wei Yang]

On Tue, Mar 31, 2020 at 09:42:12AM -0700, Matthew Wilcox wrote:
>On Tue, Mar 31, 2020 at 01:42:08PM +0000, Wei Yang wrote:
>> On Mon, Mar 30, 2020 at 07:28:21AM -0700, Matthew Wilcox wrote:
>> >On Mon, Mar 30, 2020 at 02:15:58PM +0000, Wei Yang wrote:
>> >> On Mon, Mar 30, 2020 at 05:48:42AM -0700, Matthew Wilcox wrote:
>> >> >On Mon, Mar 30, 2020 at 12:36:39PM +0000, Wei Yang wrote:
>> >> >> If an entry is at the last level, whose parent's shift is 0, it is not
>> >> >> expected to be a node. We can just leverage the xa_is_node() check to
>> >> >> break the loop instead of check shift additionally.
>> >> >
>> >> >I know you didn't run the test suite after making this change.
>> >> 
>> >> I did kernel build test, but not the test suite as you mentioned.
>> >> 
>> >> Would you mind sharing some steps on using the test suite? And which case you
>> >> think would trigger the problem?
>> >
>> >cd tools/testing/radix-tree/; make; ./main
>> >
>> 
>> Hmm... I did a make on top of 5.6-rc6, it failed. Would you mind taking a look
>> into this?
>
>It works for me.  I run it almost every day.  What error did you see?


The error message:

cc -I. -I../../include -g -Og -Wall -D_LGPL_SOURCE -fsanitize=address -fsanitize=undefined   -c -o main.o main.c
In file included from ./linux/../../../../include/linux/radix-tree.h:15,
                 from ./linux/radix-tree.h:5,
                 from main.c:10:
./linux/rcupdate.h:5:10: fatal error: urcu.h: No such file or directory
    5 | #include <urcu.h>
      |          ^~~~~~~~
compilation terminated.
make: *** [<builtin>: main.o] Error 1


I didn't touch any code in testing directory.

-- 
Wei Yang
Help you, Help me

Re: [PATCH 5/9] XArray: entry in last level is not expected to be a node

[Matthew Wilcox]

On Tue, Mar 31, 2020 at 10:04:40PM +0000, Wei Yang wrote:
> cc -I. -I../../include -g -Og -Wall -D_LGPL_SOURCE -fsanitize=address -fsanitize=undefined   -c -o main.o main.c
> In file included from ./linux/../../../../include/linux/radix-tree.h:15,
>                  from ./linux/radix-tree.h:5,
>                  from main.c:10:
> ./linux/rcupdate.h:5:10: fatal error: urcu.h: No such file or directory
>     5 | #include <urcu.h>
>       |          ^~~~~~~~
> compilation terminated.
> make: *** [<builtin>: main.o] Error 1

Oh, you need liburcu installed.  On Debian, that's liburcu-dev ... probably
liburcu-devel on Red Hat style distros.

Re: [PATCH 5/9] XArray: entry in last level is not expected to be a node

[Wei Yang]

On Tue, Mar 31, 2020 at 04:59:12PM -0700, Matthew Wilcox wrote:
>On Tue, Mar 31, 2020 at 10:04:40PM +0000, Wei Yang wrote:
>> cc -I. -I../../include -g -Og -Wall -D_LGPL_SOURCE -fsanitize=address -fsanitize=undefined   -c -o main.o main.c
>> In file included from ./linux/../../../../include/linux/radix-tree.h:15,
>>                  from ./linux/radix-tree.h:5,
>>                  from main.c:10:
>> ./linux/rcupdate.h:5:10: fatal error: urcu.h: No such file or directory
>>     5 | #include <urcu.h>
>>       |          ^~~~~~~~
>> compilation terminated.
>> make: *** [<builtin>: main.o] Error 1
>
>Oh, you need liburcu installed.  On Debian, that's liburcu-dev ... probably
>liburcu-devel on Red Hat style distros.

The bad news is I didn't find the package on Fedora.

I am trying to build it from source. Is this git repo the correct one?

git clone git://git.liburcu.org/userspace-rcu.git

-- 
Wei Yang
Help you, Help me

Re: [PATCH 5/9] XArray: entry in last level is not expected to be a node

[Matthew Wilcox]

On Wed, Apr 01, 2020 at 10:10:21PM +0000, Wei Yang wrote:
> On Tue, Mar 31, 2020 at 04:59:12PM -0700, Matthew Wilcox wrote:
> >On Tue, Mar 31, 2020 at 10:04:40PM +0000, Wei Yang wrote:
> >> cc -I. -I../../include -g -Og -Wall -D_LGPL_SOURCE -fsanitize=address -fsanitize=undefined   -c -o main.o main.c
> >> In file included from ./linux/../../../../include/linux/radix-tree.h:15,
> >>                  from ./linux/radix-tree.h:5,
> >>                  from main.c:10:
> >> ./linux/rcupdate.h:5:10: fatal error: urcu.h: No such file or directory
> >>     5 | #include <urcu.h>
> >>       |          ^~~~~~~~
> >> compilation terminated.
> >> make: *** [<builtin>: main.o] Error 1
> >
> >Oh, you need liburcu installed.  On Debian, that's liburcu-dev ... probably
> >liburcu-devel on Red Hat style distros.
> 
> The bad news is I didn't find the package on Fedora.

Really?  https://www.google.com/search?q=fedora+liburcu has the -devel
package as the second hit from https://pkgs.org/search/?q=liburcu

Re: [PATCH 5/9] XArray: entry in last level is not expected to be a node

[Wei Yang]

On Wed, Apr 01, 2020 at 03:20:00PM -0700, Matthew Wilcox wrote:
>On Wed, Apr 01, 2020 at 10:10:21PM +0000, Wei Yang wrote:
>> On Tue, Mar 31, 2020 at 04:59:12PM -0700, Matthew Wilcox wrote:
>> >On Tue, Mar 31, 2020 at 10:04:40PM +0000, Wei Yang wrote:
>> >> cc -I. -I../../include -g -Og -Wall -D_LGPL_SOURCE -fsanitize=address -fsanitize=undefined   -c -o main.o main.c
>> >> In file included from ./linux/../../../../include/linux/radix-tree.h:15,
>> >>                  from ./linux/radix-tree.h:5,
>> >>                  from main.c:10:
>> >> ./linux/rcupdate.h:5:10: fatal error: urcu.h: No such file or directory
>> >>     5 | #include <urcu.h>
>> >>       |          ^~~~~~~~
>> >> compilation terminated.
>> >> make: *** [<builtin>: main.o] Error 1
>> >
>> >Oh, you need liburcu installed.  On Debian, that's liburcu-dev ... probably
>> >liburcu-devel on Red Hat style distros.
>> 
>> The bad news is I didn't find the package on Fedora.
>
>Really?  https://www.google.com/search?q=fedora+liburcu has the -devel
>package as the second hit from https://pkgs.org/search/?q=liburcu

Thanks, I will try this.

-- 
Wei Yang
Help you, Help me

Re: [PATCH 5/9] XArray: entry in last level is not expected to be a node

[Wei Yang]

On Wed, Apr 01, 2020 at 03:20:00PM -0700, Matthew Wilcox wrote:
>On Wed, Apr 01, 2020 at 10:10:21PM +0000, Wei Yang wrote:
>> On Tue, Mar 31, 2020 at 04:59:12PM -0700, Matthew Wilcox wrote:
>> >On Tue, Mar 31, 2020 at 10:04:40PM +0000, Wei Yang wrote:
>> >> cc -I. -I../../include -g -Og -Wall -D_LGPL_SOURCE -fsanitize=address -fsanitize=undefined   -c -o main.o main.c
>> >> In file included from ./linux/../../../../include/linux/radix-tree.h:15,
>> >>                  from ./linux/radix-tree.h:5,
>> >>                  from main.c:10:
>> >> ./linux/rcupdate.h:5:10: fatal error: urcu.h: No such file or directory
>> >>     5 | #include <urcu.h>
>> >>       |          ^~~~~~~~
>> >> compilation terminated.
>> >> make: *** [<builtin>: main.o] Error 1
>> >
>> >Oh, you need liburcu installed.  On Debian, that's liburcu-dev ... probably
>> >liburcu-devel on Red Hat style distros.
>> 
>> The bad news is I didn't find the package on Fedora.
>
>Really?  https://www.google.com/search?q=fedora+liburcu has the -devel
>package as the second hit from https://pkgs.org/search/?q=liburcu

Did a run on 5.6 without my change. The output is

[root@debug010000002015 radix-tree]# ./main
random seed 1585904186
running tests
XArray: 21151201 of 21151201 tests passed
vvv Ignore these warnings
assertion failed at idr.c:269
assertion failed at idr.c:206
^^^ Warnings over
IDA: 34980531 of 34980531 tests passed
tests completed

Is these two assertion expected?

-- 
Wei Yang
Help you, Help me

Re: [PATCH 5/9] XArray: entry in last level is not expected to be a node

[Matthew Wilcox]

On Fri, Apr 03, 2020 at 10:39:33PM +0000, Wei Yang wrote:
> Did a run on 5.6 without my change. The output is
> 
> [root@debug010000002015 radix-tree]# ./main
> random seed 1585904186
> running tests
> XArray: 21151201 of 21151201 tests passed
> vvv Ignore these warnings
> assertion failed at idr.c:269
> assertion failed at idr.c:206
> ^^^ Warnings over
> IDA: 34980531 of 34980531 tests passed
> tests completed
> 
> Is these two assertion expected?

That's the meaning of the vvv and ^^^ lines.  Feel free to improve the
output here if you can figure out a way to do it.

Re: [PATCH 5/9] XArray: entry in last level is not expected to be a node

[Wei Yang]

On Wed, Apr 01, 2020 at 03:20:00PM -0700, Matthew Wilcox wrote:
>On Wed, Apr 01, 2020 at 10:10:21PM +0000, Wei Yang wrote:
>> On Tue, Mar 31, 2020 at 04:59:12PM -0700, Matthew Wilcox wrote:
>> >On Tue, Mar 31, 2020 at 10:04:40PM +0000, Wei Yang wrote:
>> >> cc -I. -I../../include -g -Og -Wall -D_LGPL_SOURCE -fsanitize=address -fsanitize=undefined   -c -o main.o main.c
>> >> In file included from ./linux/../../../../include/linux/radix-tree.h:15,
>> >>                  from ./linux/radix-tree.h:5,
>> >>                  from main.c:10:
>> >> ./linux/rcupdate.h:5:10: fatal error: urcu.h: No such file or directory
>> >>     5 | #include <urcu.h>
>> >>       |          ^~~~~~~~
>> >> compilation terminated.
>> >> make: *** [<builtin>: main.o] Error 1
>> >
>> >Oh, you need liburcu installed.  On Debian, that's liburcu-dev ... probably
>> >liburcu-devel on Red Hat style distros.
>> 
>> The bad news is I didn't find the package on Fedora.
>
>Really?  https://www.google.com/search?q=fedora+liburcu has the -devel
>package as the second hit from https://pkgs.org/search/?q=liburcu

Occasionally, I see this error message without my change on 5.6.


random seed 1586068185
running tests
XArray: 21151201 of 21151201 tests passed
=================================================================
==6040==ERROR: AddressSanitizer: heap-use-after-free on address 0x60c0031bce81 at pc 0x00000040b4b3 bp 0x7f95e87f9bb0 sp 0x7f95e87f9ba0
READ of size 1 at 0x60c0031bce81 thread T11
    #0 0x40b4b2 in xas_find_marked ../../../lib/xarray.c:1182
    #1 0x45318e in tagged_iteration_fn /root/git/linux/tools/testing/radix-tree/iteration_check.c:77
    #2 0x7f95ef2464e1 in start_thread (/lib64/libpthread.so.0+0x94e1)
    #3 0x7f95ee8026d2 in clone (/lib64/libc.so.6+0x1016d2)

0x60c0031bce81 is located 1 bytes inside of 128-byte region [0x60c0031bce80,0x60c0031bcf00)
freed by thread T1 here:
    #0 0x7f95ef36c91f in __interceptor_free (/lib64/libasan.so.5+0x10d91f)
    #1 0x43e4ba in kmem_cache_free /root/git/linux/tools/testing/radix-tree/linux.c:64

previously allocated by thread T13 here:
    #0 0x7f95ef36cd18 in __interceptor_malloc (/lib64/libasan.so.5+0x10dd18)
    #1 0x43e1af in kmem_cache_alloc /root/git/linux/tools/testing/radix-tree/linux.c:44

Thread T11 created by T0 here:
    #0 0x7f95ef299955 in pthread_create (/lib64/libasan.so.5+0x3a955)
    #1 0x454862 in iteration_test /root/git/linux/tools/testing/radix-tree/iteration_check.c:178

Thread T1 created by T0 here:
    #0 0x7f95ef299955 in pthread_create (/lib64/libasan.so.5+0x3a955)
    #1 0x7f95ef235b89  (/lib64/liburcu.so.6+0x3b89)

Thread T13 created by T0 here:
    #0 0x7f95ef299955 in pthread_create (/lib64/libasan.so.5+0x3a955)
    #1 0x4548a4 in iteration_test /root/git/linux/tools/testing/radix-tree/iteration_check.c:186

SUMMARY: AddressSanitizer: heap-use-after-free ../../../lib/xarray.c:1182 in xas_find_marked
Shadow bytes around the buggy address:
  0x0c188062f980: fa fa fa fa fa fa fa fa 00 00 00 00 00 00 00 00
  0x0c188062f990: 00 00 00 00 00 00 00 00 fa fa fa fa fa fa fa fa
  0x0c188062f9a0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c188062f9b0: fa fa fa fa fa fa fa fa fd fd fd fd fd fd fd fd
  0x0c188062f9c0: fd fd fd fd fd fd fd fd fa fa fa fa fa fa fa fa
=>0x0c188062f9d0:[fd]fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x0c188062f9e0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c188062f9f0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c188062fa00: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x0c188062fa10: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c188062fa20: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==6040==ABORTING

This is not always like this. Didn't figure out the reason yet. Hope you many
have some point.

-- 
Wei Yang
Help you, Help me

Re: [PATCH 5/9] XArray: entry in last level is not expected to be a node

[Matthew Wilcox]

On Sun, Apr 05, 2020 at 11:07:43AM +0000, Wei Yang wrote:
> Occasionally, I see this error message without my change on 5.6.

I've never seen this one before.  Maybe my test machine is insufficient ...

> random seed 1586068185
> running tests
> XArray: 21151201 of 21151201 tests passed
> =================================================================
> ==6040==ERROR: AddressSanitizer: heap-use-after-free on address 0x60c0031bce81 at pc 0x00000040b4b3 bp 0x7f95e87f9bb0 sp 0x7f95e87f9ba0
> READ of size 1 at 0x60c0031bce81 thread T11
>     #0 0x40b4b2 in xas_find_marked ../../../lib/xarray.c:1182
>     #1 0x45318e in tagged_iteration_fn /root/git/linux/tools/testing/radix-tree/iteration_check.c:77
>     #2 0x7f95ef2464e1 in start_thread (/lib64/libpthread.so.0+0x94e1)
>     #3 0x7f95ee8026d2 in clone (/lib64/libc.so.6+0x1016d2)
> 
> 0x60c0031bce81 is located 1 bytes inside of 128-byte region [0x60c0031bce80,0x60c0031bcf00)
> freed by thread T1 here:
>     #0 0x7f95ef36c91f in __interceptor_free (/lib64/libasan.so.5+0x10d91f)
>     #1 0x43e4ba in kmem_cache_free /root/git/linux/tools/testing/radix-tree/linux.c:64
> 
> previously allocated by thread T13 here:
>     #0 0x7f95ef36cd18 in __interceptor_malloc (/lib64/libasan.so.5+0x10dd18)
>     #1 0x43e1af in kmem_cache_alloc /root/git/linux/tools/testing/radix-tree/linux.c:44
> 
> Thread T11 created by T0 here:
>     #0 0x7f95ef299955 in pthread_create (/lib64/libasan.so.5+0x3a955)
>     #1 0x454862 in iteration_test /root/git/linux/tools/testing/radix-tree/iteration_check.c:178
> 
> Thread T1 created by T0 here:
>     #0 0x7f95ef299955 in pthread_create (/lib64/libasan.so.5+0x3a955)
>     #1 0x7f95ef235b89  (/lib64/liburcu.so.6+0x3b89)
> 
> Thread T13 created by T0 here:
>     #0 0x7f95ef299955 in pthread_create (/lib64/libasan.so.5+0x3a955)
>     #1 0x4548a4 in iteration_test /root/git/linux/tools/testing/radix-tree/iteration_check.c:186
> 
> This is not always like this. Didn't figure out the reason yet. Hope you many
> have some point.

How often are you seeing it?

T1 (the thread which frees the memory) is the RCU thread, so the freeing
went through RCU.  For some reason, T11 (the iterating thread) isn't
preventing the freeing by its use of the RCU read lock.

Re: [PATCH 5/9] XArray: entry in last level is not expected to be a node

[Wei Yang]

On Sun, Apr 05, 2020 at 02:56:36PM -0700, Matthew Wilcox wrote:
>On Sun, Apr 05, 2020 at 11:07:43AM +0000, Wei Yang wrote:
>> Occasionally, I see this error message without my change on 5.6.
>
>I've never seen this one before.  Maybe my test machine is insufficient ...
>
>> random seed 1586068185
>> running tests
>> XArray: 21151201 of 21151201 tests passed
>> =================================================================
>> ==6040==ERROR: AddressSanitizer: heap-use-after-free on address 0x60c0031bce81 at pc 0x00000040b4b3 bp 0x7f95e87f9bb0 sp 0x7f95e87f9ba0
>> READ of size 1 at 0x60c0031bce81 thread T11
>>     #0 0x40b4b2 in xas_find_marked ../../../lib/xarray.c:1182
>>     #1 0x45318e in tagged_iteration_fn /root/git/linux/tools/testing/radix-tree/iteration_check.c:77
>>     #2 0x7f95ef2464e1 in start_thread (/lib64/libpthread.so.0+0x94e1)
>>     #3 0x7f95ee8026d2 in clone (/lib64/libc.so.6+0x1016d2)
>> 
>> 0x60c0031bce81 is located 1 bytes inside of 128-byte region [0x60c0031bce80,0x60c0031bcf00)
>> freed by thread T1 here:
>>     #0 0x7f95ef36c91f in __interceptor_free (/lib64/libasan.so.5+0x10d91f)
>>     #1 0x43e4ba in kmem_cache_free /root/git/linux/tools/testing/radix-tree/linux.c:64
>> 
>> previously allocated by thread T13 here:
>>     #0 0x7f95ef36cd18 in __interceptor_malloc (/lib64/libasan.so.5+0x10dd18)
>>     #1 0x43e1af in kmem_cache_alloc /root/git/linux/tools/testing/radix-tree/linux.c:44
>> 
>> Thread T11 created by T0 here:
>>     #0 0x7f95ef299955 in pthread_create (/lib64/libasan.so.5+0x3a955)
>>     #1 0x454862 in iteration_test /root/git/linux/tools/testing/radix-tree/iteration_check.c:178
>> 
>> Thread T1 created by T0 here:
>>     #0 0x7f95ef299955 in pthread_create (/lib64/libasan.so.5+0x3a955)
>>     #1 0x7f95ef235b89  (/lib64/liburcu.so.6+0x3b89)
>> 
>> Thread T13 created by T0 here:
>>     #0 0x7f95ef299955 in pthread_create (/lib64/libasan.so.5+0x3a955)
>>     #1 0x4548a4 in iteration_test /root/git/linux/tools/testing/radix-tree/iteration_check.c:186
>> 
>> This is not always like this. Didn't figure out the reason yet. Hope you many
>> have some point.
>
>How often are you seeing it?
>

Didn't do a strict analysis. My intuition feels 30% of reproduction.

>T1 (the thread which frees the memory) is the RCU thread, so the freeing
>went through RCU.  For some reason, T11 (the iterating thread) isn't
>preventing the freeing by its use of the RCU read lock.

Maybe this is the RCU problem. I didn't manage to install liburcu from rpm,
but build it from source.

-- 
Wei Yang
Help you, Help me

Re: [PATCH 5/9] XArray: entry in last level is not expected to be a node

[Wei Yang]

On Mon, Mar 30, 2020 at 05:48:42AM -0700, Matthew Wilcox wrote:
>On Mon, Mar 30, 2020 at 12:36:39PM +0000, Wei Yang wrote:
>> If an entry is at the last level, whose parent's shift is 0, it is not
>> expected to be a node. We can just leverage the xa_is_node() check to
>> break the loop instead of check shift additionally.
>
>I know you didn't run the test suite after making this change.

Well, I got your point finally. From commit 76b4e5299565 ('XArray: Permit
storing 2-byte-aligned pointers'), xa_is_node() will not be *ACURATE*. Those
2-byte align pointers will be treated as node too.

Well, I found another thing, but not sure whether you have fixed this or not.

If applying following change

@@ -1461,6 +1461,11 @@ static void check_align_1(struct xarray *xa, char *name)
                                        GFP_KERNEL) != 0);
                XA_BUG_ON(xa, id != i);
        }
+       XA_STATE_ORDER(xas, xa, 0, 0);
+       entry = xas_find_conflict(&xas);
        xa_for_each(xa, index, entry)
                XA_BUG_ON(xa, xa_is_err(entry));
        xa_destroy(xa);

We trigger an error message. The reason is the same. And we can fix this with
the same approach in xas_find_conflict().

If you think this is the proper way, I would add a patch for this.

-- 
Wei Yang
Help you, Help me

Re: [PATCH 5/9] XArray: entry in last level is not expected to be a node

[Wei Yang]

On Mon, Apr 06, 2020 at 01:24:53AM +0000, Wei Yang wrote:
>On Mon, Mar 30, 2020 at 05:48:42AM -0700, Matthew Wilcox wrote:
>>On Mon, Mar 30, 2020 at 12:36:39PM +0000, Wei Yang wrote:
>>> If an entry is at the last level, whose parent's shift is 0, it is not
>>> expected to be a node. We can just leverage the xa_is_node() check to
>>> break the loop instead of check shift additionally.
>>
>>I know you didn't run the test suite after making this change.
>

Matthew

Have you got my mail?

>Well, I got your point finally. From commit 76b4e5299565 ('XArray: Permit
>storing 2-byte-aligned pointers'), xa_is_node() will not be *ACURATE*. Those
>2-byte align pointers will be treated as node too.
>
>Well, I found another thing, but not sure whether you have fixed this or not.
>
>If applying following change
>
>@@ -1461,6 +1461,11 @@ static void check_align_1(struct xarray *xa, char *name)
>                                        GFP_KERNEL) != 0);
>                XA_BUG_ON(xa, id != i);
>        }
>+       XA_STATE_ORDER(xas, xa, 0, 0);
>+       entry = xas_find_conflict(&xas);
>        xa_for_each(xa, index, entry)
>                XA_BUG_ON(xa, xa_is_err(entry));
>        xa_destroy(xa);
>
>We trigger an error message. The reason is the same. And we can fix this with
>the same approach in xas_find_conflict().
>
>If you think this is the proper way, I would add a patch for this.
>
>-- 
>Wei Yang
>Help you, Help me

-- 
Wei Yang
Help you, Help me

Re: [PATCH 5/9] XArray: entry in last level is not expected to be a node

[Wei Yang]

On Mon, Mar 30, 2020 at 05:48:42AM -0700, Matthew Wilcox wrote:
>On Mon, Mar 30, 2020 at 12:36:39PM +0000, Wei Yang wrote:
>> If an entry is at the last level, whose parent's shift is 0, it is not
>> expected to be a node. We can just leverage the xa_is_node() check to
>> break the loop instead of check shift additionally.
>
>I know you didn't run the test suite after making this change.

Hi, Matthew

Would you mind picking up this thread again? Or what other concern you have?

-- 
Wei Yang
Help you, Help me

[PATCH 6/9] XArray: internal node is a xa_node when it is bigger than XA_ZERO_ENTRY

[Wei Yang]

As the comment mentioned, we reserved several ranges of internal node
for tree maintenance, 0-62, 256, 257. This means a node bigger than
XA_ZERO_ENTRY is a normal node.

The checked on XA_ZERO_ENTRY seems to be more meaningful.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
---
 include/linux/xarray.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/include/linux/xarray.h b/include/linux/xarray.h
index a491653d8882..e9d07483af64 100644
--- a/include/linux/xarray.h
+++ b/include/linux/xarray.h
@@ -1221,7 +1221,7 @@ static inline struct xa_node *xa_to_node(const void *entry)
 /* Private */
 static inline bool xa_is_node(const void *entry)
 {
-	return xa_is_internal(entry) && (unsigned long)entry > 4096;
+	return xa_is_internal(entry) && entry > XA_ZERO_ENTRY;
 }
 
 /* Private */
-- 
2.23.0

Re: [PATCH 6/9] XArray: internal node is a xa_node when it is bigger than XA_ZERO_ENTRY

[Matthew Wilcox]

On Mon, Mar 30, 2020 at 12:36:40PM +0000, Wei Yang wrote:
> As the comment mentioned, we reserved several ranges of internal node
> for tree maintenance, 0-62, 256, 257. This means a node bigger than
> XA_ZERO_ENTRY is a normal node.
> 
> The checked on XA_ZERO_ENTRY seems to be more meaningful.

257-1023 are also reserved, they just aren't used yet.  XA_ZERO_ENTRY
is not guaranteed to be the largest reserved entry.

Re: [PATCH 6/9] XArray: internal node is a xa_node when it is bigger than XA_ZERO_ENTRY

[Wei Yang]

On Mon, Mar 30, 2020 at 05:50:06AM -0700, Matthew Wilcox wrote:
>On Mon, Mar 30, 2020 at 12:36:40PM +0000, Wei Yang wrote:
>> As the comment mentioned, we reserved several ranges of internal node
>> for tree maintenance, 0-62, 256, 257. This means a node bigger than
>> XA_ZERO_ENTRY is a normal node.
>> 
>> The checked on XA_ZERO_ENTRY seems to be more meaningful.
>
>257-1023 are also reserved, they just aren't used yet.  XA_ZERO_ENTRY
>is not guaranteed to be the largest reserved entry.

Then why we choose 4096?

-- 
Wei Yang
Help you, Help me

Re: [PATCH 6/9] XArray: internal node is a xa_node when it is bigger than XA_ZERO_ENTRY

[Matthew Wilcox]

On Mon, Mar 30, 2020 at 01:45:19PM +0000, Wei Yang wrote:
> On Mon, Mar 30, 2020 at 05:50:06AM -0700, Matthew Wilcox wrote:
> >On Mon, Mar 30, 2020 at 12:36:40PM +0000, Wei Yang wrote:
> >> As the comment mentioned, we reserved several ranges of internal node
> >> for tree maintenance, 0-62, 256, 257. This means a node bigger than
> >> XA_ZERO_ENTRY is a normal node.
> >> 
> >> The checked on XA_ZERO_ENTRY seems to be more meaningful.
> >
> >257-1023 are also reserved, they just aren't used yet.  XA_ZERO_ENTRY
> >is not guaranteed to be the largest reserved entry.
> 
> Then why we choose 4096?

Because 4096 is the smallest page size supported by Linux, so we're
guaranteed that anything less than 4096 is not a valid pointer.

Re: [PATCH 6/9] XArray: internal node is a xa_node when it is bigger than XA_ZERO_ENTRY

[Wei Yang]

On Mon, Mar 30, 2020 at 06:49:03AM -0700, Matthew Wilcox wrote:
>On Mon, Mar 30, 2020 at 01:45:19PM +0000, Wei Yang wrote:
>> On Mon, Mar 30, 2020 at 05:50:06AM -0700, Matthew Wilcox wrote:
>> >On Mon, Mar 30, 2020 at 12:36:40PM +0000, Wei Yang wrote:
>> >> As the comment mentioned, we reserved several ranges of internal node
>> >> for tree maintenance, 0-62, 256, 257. This means a node bigger than
>> >> XA_ZERO_ENTRY is a normal node.
>> >> 
>> >> The checked on XA_ZERO_ENTRY seems to be more meaningful.
>> >
>> >257-1023 are also reserved, they just aren't used yet.  XA_ZERO_ENTRY
>> >is not guaranteed to be the largest reserved entry.
>> 
>> Then why we choose 4096?
>
>Because 4096 is the smallest page size supported by Linux, so we're
>guaranteed that anything less than 4096 is not a valid pointer.

I found this in xarray.rst:

  Normal pointers may be stored in the XArray directly.  They must be 4-byte
  aligned, which is true for any pointer returned from kmalloc() and
  alloc_page().  It isn't true for arbitrary user-space pointers,
  nor for function pointers.  You can store pointers to statically allocated
  objects, as long as those objects have an alignment of at least 4.

So the document here is not correct?

-- 
Wei Yang
Help you, Help me

Re: [PATCH 6/9] XArray: internal node is a xa_node when it is bigger than XA_ZERO_ENTRY

[Matthew Wilcox]

On Mon, Mar 30, 2020 at 02:13:50PM +0000, Wei Yang wrote:
> On Mon, Mar 30, 2020 at 06:49:03AM -0700, Matthew Wilcox wrote:
> >On Mon, Mar 30, 2020 at 01:45:19PM +0000, Wei Yang wrote:
> >> On Mon, Mar 30, 2020 at 05:50:06AM -0700, Matthew Wilcox wrote:
> >> >On Mon, Mar 30, 2020 at 12:36:40PM +0000, Wei Yang wrote:
> >> >> As the comment mentioned, we reserved several ranges of internal node
> >> >> for tree maintenance, 0-62, 256, 257. This means a node bigger than
> >> >> XA_ZERO_ENTRY is a normal node.
> >> >> 
> >> >> The checked on XA_ZERO_ENTRY seems to be more meaningful.
> >> >
> >> >257-1023 are also reserved, they just aren't used yet.  XA_ZERO_ENTRY
> >> >is not guaranteed to be the largest reserved entry.
> >> 
> >> Then why we choose 4096?
> >
> >Because 4096 is the smallest page size supported by Linux, so we're
> >guaranteed that anything less than 4096 is not a valid pointer.
> 
> I found this in xarray.rst:
> 
>   Normal pointers may be stored in the XArray directly.  They must be 4-byte
>   aligned, which is true for any pointer returned from kmalloc() and
>   alloc_page().  It isn't true for arbitrary user-space pointers,
>   nor for function pointers.  You can store pointers to statically allocated
>   objects, as long as those objects have an alignment of at least 4.
> 
> So the document here is not correct?

Why do you say that?

(it is slightly out of date; the XArray actually supports storing unaligned
pointers now, but that's not relevant to this discussion)

Re: [PATCH 6/9] XArray: internal node is a xa_node when it is bigger than XA_ZERO_ENTRY

[Wei Yang]

On Mon, Mar 30, 2020 at 07:27:08AM -0700, Matthew Wilcox wrote:
>On Mon, Mar 30, 2020 at 02:13:50PM +0000, Wei Yang wrote:
>> On Mon, Mar 30, 2020 at 06:49:03AM -0700, Matthew Wilcox wrote:
>> >On Mon, Mar 30, 2020 at 01:45:19PM +0000, Wei Yang wrote:
>> >> On Mon, Mar 30, 2020 at 05:50:06AM -0700, Matthew Wilcox wrote:
>> >> >On Mon, Mar 30, 2020 at 12:36:40PM +0000, Wei Yang wrote:
>> >> >> As the comment mentioned, we reserved several ranges of internal node
>> >> >> for tree maintenance, 0-62, 256, 257. This means a node bigger than
>> >> >> XA_ZERO_ENTRY is a normal node.
>> >> >> 
>> >> >> The checked on XA_ZERO_ENTRY seems to be more meaningful.
>> >> >
>> >> >257-1023 are also reserved, they just aren't used yet.  XA_ZERO_ENTRY
>> >> >is not guaranteed to be the largest reserved entry.
>> >> 
>> >> Then why we choose 4096?
>> >
>> >Because 4096 is the smallest page size supported by Linux, so we're
>> >guaranteed that anything less than 4096 is not a valid pointer.
>> 

So you want to say, the 4096 makes sure XArray will not store an address in
first page? If this is the case, I have two suggestions:

  * use PAGE_SIZE would be more verbose?
  * a node is an internal entry, do we need to compare with xa_mk_internal()
    instead?

And also suggest to add a comment on this, otherwise it seems a little magic.

>> I found this in xarray.rst:
>> 
>>   Normal pointers may be stored in the XArray directly.  They must be 4-byte
>>   aligned, which is true for any pointer returned from kmalloc() and
>>   alloc_page().  It isn't true for arbitrary user-space pointers,
>>   nor for function pointers.  You can store pointers to statically allocated
>>   objects, as long as those objects have an alignment of at least 4.
>> 
>> So the document here is not correct?
>
>Why do you say that?
>
>(it is slightly out of date; the XArray actually supports storing unaligned
>pointers now, but that's not relevant to this discussion)

Ok, maybe this document need to update.

-- 
Wei Yang
Help you, Help me

Re: [PATCH 6/9] XArray: internal node is a xa_node when it is bigger than XA_ZERO_ENTRY

[Matthew Wilcox]

On Mon, Mar 30, 2020 at 10:20:13PM +0000, Wei Yang wrote:
> On Mon, Mar 30, 2020 at 07:27:08AM -0700, Matthew Wilcox wrote:
> >On Mon, Mar 30, 2020 at 02:13:50PM +0000, Wei Yang wrote:
> >> On Mon, Mar 30, 2020 at 06:49:03AM -0700, Matthew Wilcox wrote:
> >> >On Mon, Mar 30, 2020 at 01:45:19PM +0000, Wei Yang wrote:
> >> >> On Mon, Mar 30, 2020 at 05:50:06AM -0700, Matthew Wilcox wrote:
> >> >> >On Mon, Mar 30, 2020 at 12:36:40PM +0000, Wei Yang wrote:
> >> >> >> As the comment mentioned, we reserved several ranges of internal node
> >> >> >> for tree maintenance, 0-62, 256, 257. This means a node bigger than
> >> >> >> XA_ZERO_ENTRY is a normal node.
> >> >> >> 
> >> >> >> The checked on XA_ZERO_ENTRY seems to be more meaningful.
> >> >> >
> >> >> >257-1023 are also reserved, they just aren't used yet.  XA_ZERO_ENTRY
> >> >> >is not guaranteed to be the largest reserved entry.
> >> >> 
> >> >> Then why we choose 4096?
> >> >
> >> >Because 4096 is the smallest page size supported by Linux, so we're
> >> >guaranteed that anything less than 4096 is not a valid pointer.
> >> 
> 
> So you want to say, the 4096 makes sure XArray will not store an address in
> first page? If this is the case, I have two suggestions:
> 
>   * use PAGE_SIZE would be more verbose?

But also incorrect, because it'll be different on different architectures.
It's 4096.  That's all.

>   * a node is an internal entry, do we need to compare with xa_mk_internal()
>     instead?

No.  4096 is better because it's a number which is easily expressible in
many CPU instruction sets.  4094 is much less likely to be an easy number
to encode.

> >(it is slightly out of date; the XArray actually supports storing unaligned
> >pointers now, but that's not relevant to this discussion)
> 
> Ok, maybe this document need to update.

Did you want to send a patch?

Re: [PATCH 6/9] XArray: internal node is a xa_node when it is bigger than XA_ZERO_ENTRY

[Wei Yang]

On Mon, Mar 30, 2020 at 05:06:49PM -0700, Matthew Wilcox wrote:
>On Mon, Mar 30, 2020 at 10:20:13PM +0000, Wei Yang wrote:
>> On Mon, Mar 30, 2020 at 07:27:08AM -0700, Matthew Wilcox wrote:
>> >On Mon, Mar 30, 2020 at 02:13:50PM +0000, Wei Yang wrote:
>> >> On Mon, Mar 30, 2020 at 06:49:03AM -0700, Matthew Wilcox wrote:
>> >> >On Mon, Mar 30, 2020 at 01:45:19PM +0000, Wei Yang wrote:
>> >> >> On Mon, Mar 30, 2020 at 05:50:06AM -0700, Matthew Wilcox wrote:
>> >> >> >On Mon, Mar 30, 2020 at 12:36:40PM +0000, Wei Yang wrote:
>> >> >> >> As the comment mentioned, we reserved several ranges of internal node
>> >> >> >> for tree maintenance, 0-62, 256, 257. This means a node bigger than
>> >> >> >> XA_ZERO_ENTRY is a normal node.
>> >> >> >> 
>> >> >> >> The checked on XA_ZERO_ENTRY seems to be more meaningful.
>> >> >> >
>> >> >> >257-1023 are also reserved, they just aren't used yet.  XA_ZERO_ENTRY
>> >> >> >is not guaranteed to be the largest reserved entry.
>> >> >> 
>> >> >> Then why we choose 4096?
>> >> >
>> >> >Because 4096 is the smallest page size supported by Linux, so we're
>> >> >guaranteed that anything less than 4096 is not a valid pointer.
>> >> 
>> 
>> So you want to say, the 4096 makes sure XArray will not store an address in
>> first page? If this is the case, I have two suggestions:
>> 
>>   * use PAGE_SIZE would be more verbose?
>
>But also incorrect, because it'll be different on different architectures.
>It's 4096.  That's all.
>
>>   * a node is an internal entry, do we need to compare with xa_mk_internal()
>>     instead?
>
>No.  4096 is better because it's a number which is easily expressible in
>many CPU instruction sets.  4094 is much less likely to be an easy number
>to encode.
>
>> >(it is slightly out of date; the XArray actually supports storing unaligned
>> >pointers now, but that's not relevant to this discussion)
>> 
>> Ok, maybe this document need to update.
>
>Did you want to send a patch?

I am not clear how it supports unaligned pointers. So maybe not now.

Actually, I still not get the point between page size and valid pointer. Why a
valid pointer couldn't be less than 4096? The first page in address space is
handled differently? Maybe I miss some point. I'd appreciate it if you'd share
some light.

Thanks
-- 
Wei Yang
Help you, Help me

[PATCH 7/9] XArray: the NULL xa_node condition is handled in xas_top

[Wei Yang]

From the last if/else check, it handles the NULL/non-NULL xa_node
mutually exclusively. While the NULL xa_node case is handled in the
first condition xas_top().

Just remove the redundant handling for NULL xa_node.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
---
 lib/xarray.c | 6 +-----
 1 file changed, 1 insertion(+), 5 deletions(-)

diff --git a/lib/xarray.c b/lib/xarray.c
index 0c5b44def3aa..82570bbbf2a5 100644
--- a/lib/xarray.c
+++ b/lib/xarray.c
@@ -650,16 +650,12 @@ static void *xas_create(struct xa_state *xas, bool allow_root)
 		slot = &xa->xa_head;
 	} else if (xas_error(xas)) {
 		return NULL;
-	} else if (node) {
+	} else {
 		unsigned int offset = xas->xa_offset;
 
 		shift = node->shift;
 		entry = xa_entry_locked(xa, node, offset);
 		slot = &node->slots[offset];
-	} else {
-		shift = 0;
-		entry = xa_head_locked(xa);
-		slot = &xa->xa_head;
 	}
 
 	while (shift > order) {
-- 
2.23.0

[PATCH 8/9] XArray: take xas_error() handling for clearer logic

[Wei Yang]

If xas is already in error state, return NULL directly.

Take this logic out instead of burying in the middle to make the logic
more straight forward.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
---
 lib/xarray.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/lib/xarray.c b/lib/xarray.c
index 82570bbbf2a5..01f64a000e14 100644
--- a/lib/xarray.c
+++ b/lib/xarray.c
@@ -636,6 +636,9 @@ static void *xas_create(struct xa_state *xas, bool allow_root)
 	int shift;
 	unsigned int order = xas->xa_shift;
 
+	if (xas_error(xas))
+		return NULL;
+
 	if (xas_top(node)) {
 		entry = xa_head_locked(xa);
 		xas->xa_node = NULL;
@@ -648,8 +651,6 @@ static void *xas_create(struct xa_state *xas, bool allow_root)
 			shift = XA_CHUNK_SHIFT;
 		entry = xa_head_locked(xa);
 		slot = &xa->xa_head;
-	} else if (xas_error(xas)) {
-		return NULL;
 	} else {
 		unsigned int offset = xas->xa_offset;
 
-- 
2.23.0

[PATCH 9/9] XArray: adjust xa_offset till it gets the correct node

[Wei Yang]

During xas_create_range(), it will go up the tree for next create.

Currently, during moving up the tree, the xa_offset is adjusted every
thime. This is not necessary. Only the offset for the last one matters.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
---
 lib/xarray.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/lib/xarray.c b/lib/xarray.c
index 01f64a000e14..9546b2b2dce1 100644
--- a/lib/xarray.c
+++ b/lib/xarray.c
@@ -712,9 +712,10 @@ void xas_create_range(struct xa_state *xas)
 		for (;;) {
 			struct xa_node *node = xas->xa_node;
 			xas->xa_node = xa_parent_locked(xas->xa, node);
-			xas->xa_offset = node->offset - 1;
-			if (node->offset != 0)
+			if (node->offset != 0) {
+				xas->xa_offset = node->offset - 1;
 				break;
+			}
 		}
 	}
 
-- 
2.23.0