Skip to contentSkip to conversation

XArray: several cleanups

PATCH In review Wei Yang 2 participants 41 messages Mar 30, 2020 – Apr 28, 2020

Subsystems (3)
lore
Share & tools
lore

Wei Yang

author
#0 lore raw

cover XArray: several cleanups

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(-)
Signature · 1 line
2.23.0
author
#1 lore raw

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

Correct the comment according to definition.

---
 include/linux/xarray.h | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
include/linux/xarray.h +2 -2
index f73e1775ded0..a491653d8882 100644
@@ -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
Signature · 1 line
2.23.0
maintainer
#2 lore raw

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

Quoted 1 line · Wei Yang

Correct the comment according to definition.

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

author
#3 lore raw

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

Quoted 5 lines · Matthew Wilcox
Quoted 1 line · Wei Yang

Correct the comment according to definition.

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

Oh, thanks

Signature · 2 lines
Wei Yang
Help you, Help me
author
#4 lore raw

PATCH 2/9 XArray: simplify the calculation of shift

In reply to 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.

---
 lib/xarray.c | 6 +-----
 1 file changed, 1 insertion(+), 5 deletions(-)
lib/xarray.c +1 -5
index 1d9fab7db8da..6454cf3f5b4c 100644
@@ -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;
Signature · 1 line
2.23.0
maintainer
#5 lore raw

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

Quoted 16 lines · 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.

---
 lib/xarray.c | 6 +-----
 1 file changed, 1 insertion(+), 5 deletions(-)
lib/xarray.c +0 -0
index 1d9fab7db8da..6454cf3f5b4c 100644

lib/xarray.c static int xas_expand(struct xa_state *xas, void *head) · line 563

Quoted 9 lines
lib/xarray.c +1 -5
@@ -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.

author
#6 lore raw

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

Quoted 37 lines · Matthew Wilcox
Quoted 16 lines · 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.

---
 lib/xarray.c | 6 +-----
 1 file changed, 1 insertion(+), 5 deletions(-)
lib/xarray.c +0 -0
index 1d9fab7db8da..6454cf3f5b4c 100644

lib/xarray.c static int xas_expand(struct xa_state *xas, void *head) · line 563

Quoted 9 lines
lib/xarray.c +1 -5
@@ -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

Quoted 3 lines

Your replacement does:

fls_long(64) = 6

fls_long(64) = 7

Quoted 3 lines

roundup(6, 6) is 6.

Please be more careful.

Signature · 2 lines
Wei Yang
Help you, Help me
author
#7 lore raw

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

In reply to 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.

---
 lib/xarray.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)
lib/xarray.c +3 -2
index 6454cf3f5b4c..1a092c87fca5 100644
@@ -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;
 	}
Signature · 1 line
2.23.0
author
#8 lore raw

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

In reply to Wei Yang

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

---
 lib/xarray.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
lib/xarray.c +1 -1
index 1a092c87fca5..e08a0388a156 100644
@@ -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);
Signature · 1 line
2.23.0
author
#9 lore raw

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

In reply to 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.

---
 lib/xarray.c | 2 --
 1 file changed, 2 deletions(-)
lib/xarray.c +0 -2
index e08a0388a156..0c5b44def3aa 100644
@@ -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;
 }
Signature · 1 line
2.23.0
maintainer
#10 lore raw

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

Quoted 3 lines · 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.

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

author
#11 lore raw

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

Quoted 6 lines · Matthew Wilcox
Quoted 3 lines · 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.

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?

Signature · 2 lines
Wei Yang
Help you, Help me
maintainer
#12 lore raw

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

Quoted 6 lines · Wei Yang
Quoted 5 lines · Matthew Wilcox
Quoted 3 lines · 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.

Quoted 6 lines
Quoted 1 line

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.

author
#13 lore raw

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

Quoted 9 lines · Matthew Wilcox
Quoted 8 lines · Wei Yang
Quoted 6 lines · Matthew Wilcox
Quoted 3 lines · 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.

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

Quoted 8 lines
Quoted 4 lines

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.

Signature · 2 lines
Wei Yang
Help you, Help me
author
#14 lore raw

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

In reply to Matthew Wilcox
Quoted 7 lines · Matthew Wilcox
Quoted 6 lines · Wei Yang
Quoted 5 lines · Matthew Wilcox
Quoted 3 lines · 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.

Quoted 9 lines
Quoted 6 lines
Quoted 1 line

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?

Quoted 1 line

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

Signature · 2 lines
Wei Yang
Help you, Help me
maintainer
#15 lore raw

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

Quoted 12 lines · Wei Yang
Quoted 11 lines · Matthew Wilcox
Quoted 10 lines · Wei Yang
Quoted 6 lines · Matthew Wilcox
Quoted 3 lines · 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.

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.

Quoted 8 lines
Quoted 5 lines
Quoted 2 lines

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?

author
#16 lore raw

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

Quoted 16 lines · Matthew Wilcox
Quoted 15 lines · Wei Yang
Quoted 14 lines · Matthew Wilcox
Quoted 12 lines · Wei Yang
Quoted 6 lines · Matthew Wilcox
Quoted 3 lines · 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.

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?

Quoted 7 lines
Quoted 5 lines
Quoted 2 lines

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.

Signature · 2 lines
Wei Yang
Help you, Help me
maintainer
#17 lore raw

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

Quoted 9 lines · Wei Yang

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.

author
#18 lore raw

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

Quoted 11 lines · Matthew Wilcox
Quoted 9 lines · Wei Yang

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

Quoted 2 lines

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

Signature · 2 lines
Wei Yang
Help you, Help me
maintainer
#19 lore raw

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

Quoted 12 lines · Wei Yang
Quoted 11 lines · Matthew Wilcox
Quoted 9 lines · Wei Yang

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

Quoted 4 lines
Quoted 2 lines

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

author
#20 lore raw

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

Quoted 13 lines · Matthew Wilcox
Quoted 12 lines · Wei Yang
Quoted 11 lines · Matthew Wilcox
Quoted 9 lines · Wei Yang

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

Quoted 7 lines
Quoted 4 lines
Quoted 2 lines

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.

Signature · 2 lines
Wei Yang
Help you, Help me
author
#21 lore raw

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

In reply to Matthew Wilcox
Quoted 13 lines · Matthew Wilcox
Quoted 12 lines · Wei Yang
Quoted 11 lines · Matthew Wilcox
Quoted 9 lines · Wei Yang

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

Quoted 7 lines
Quoted 4 lines
Quoted 2 lines

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?

Signature · 2 lines
Wei Yang
Help you, Help me
maintainer
#22 lore raw

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

Quoted 13 lines · Wei Yang

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

Quoted 1 line

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.

author
#23 lore raw

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

In reply to Matthew Wilcox
Quoted 13 lines · Matthew Wilcox
Quoted 12 lines · Wei Yang
Quoted 11 lines · Matthew Wilcox
Quoted 9 lines · Wei Yang

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

Quoted 7 lines
Quoted 4 lines
Quoted 2 lines

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.

Signature · 2 lines
Wei Yang
Help you, Help me
maintainer
#24 lore raw

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

Quoted 1 line · Wei Yang

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

Quoted 28 lines

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)
Quoted 6 lines

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.

author
#25 lore raw

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

Quoted 33 lines · Matthew Wilcox
Quoted 1 line · Wei Yang

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

Quoted 28 lines

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)
Quoted 9 lines
Quoted 6 lines

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.

Quoted 3 lines

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.

Signature · 2 lines
Wei Yang
Help you, Help me
author
#26 lore raw

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

In reply to Matthew Wilcox
Quoted 6 lines · Matthew Wilcox
Quoted 3 lines · 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.

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.

Signature · 2 lines
Wei Yang
Help you, Help me
author
#27 lore raw

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

Quoted 8 lines · Wei Yang
Quoted 6 lines · Matthew Wilcox
Quoted 3 lines · 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.

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

Matthew

Have you got my mail?

Quoted 26 lines

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

(quoted diff) +2 -0
@@ -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.

Signature · 2 lines
Wei Yang
Help you, Help me
Signature · 2 lines
Wei Yang
Help you, Help me
author
#28 lore raw

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

In reply to Matthew Wilcox
Quoted 6 lines · Matthew Wilcox
Quoted 3 lines · 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.

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?

Signature · 2 lines
Wei Yang
Help you, Help me
author
#29 lore raw

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

In reply to 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.

---
 include/linux/xarray.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
include/linux/xarray.h +1 -1
index a491653d8882..e9d07483af64 100644
@@ -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 */
Signature · 1 line
2.23.0
maintainer
#30 lore raw

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

Quoted 5 lines · 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.

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

author
#31 lore raw

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

Quoted 9 lines · Matthew Wilcox
Quoted 5 lines · 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.

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?

Signature · 2 lines
Wei Yang
Help you, Help me
maintainer
#32 lore raw

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

Quoted 6 lines · Wei Yang
Quoted 5 lines · Matthew Wilcox
Quoted 4 lines · 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.

Quoted 6 lines
Quoted 4 lines
Quoted 1 line

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.

author
#33 lore raw

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

Quoted 9 lines · Matthew Wilcox
Quoted 8 lines · Wei Yang
Quoted 7 lines · Matthew Wilcox
Quoted 5 lines · 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.

Quoted 7 lines
Quoted 4 lines
Quoted 2 lines

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?

Signature · 2 lines
Wei Yang
Help you, Help me
maintainer
#34 lore raw

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

Quoted 20 lines · Wei Yang
Quoted 9 lines · Matthew Wilcox
Quoted 8 lines · Wei Yang
Quoted 7 lines · Matthew Wilcox
Quoted 5 lines · 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.

Quoted 7 lines
Quoted 4 lines
Quoted 2 lines

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:

Quoted 7 lines

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)

author
#35 lore raw

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

Quoted 11 lines · Matthew Wilcox
Quoted 10 lines · Wei Yang
Quoted 9 lines · Matthew Wilcox
Quoted 8 lines · Wei Yang
Quoted 7 lines · Matthew Wilcox
Quoted 5 lines · 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.

Quoted 8 lines
Quoted 8 lines
Quoted 7 lines
Quoted 4 lines
Quoted 2 lines

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.

Quoted 8 lines
Quoted 8 lines

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.

Quoted 6 lines
Quoted 1 line

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.

Signature · 2 lines
Wei Yang
Help you, Help me
maintainer
#36 lore raw

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

Quoted 17 lines · Wei Yang
Quoted 16 lines · Matthew Wilcox
Quoted 15 lines · Wei Yang
Quoted 14 lines · Matthew Wilcox
Quoted 12 lines · Wei Yang
Quoted 9 lines · Matthew Wilcox
Quoted 5 lines · 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.

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?

Quoted 8 lines
Quoted 3 lines
Quoted 3 lines
Quoted 2 lines

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.

Quoted 2 lines

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

Quoted 4 lines
Quoted 2 lines

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

author
#37 lore raw

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

Quoted 37 lines · Matthew Wilcox
Quoted 17 lines · Wei Yang
Quoted 16 lines · Matthew Wilcox
Quoted 15 lines · Wei Yang
Quoted 14 lines · Matthew Wilcox
Quoted 12 lines · Wei Yang
Quoted 9 lines · Matthew Wilcox
Quoted 5 lines · 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.

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?

Quoted 8 lines
Quoted 3 lines
Quoted 3 lines
Quoted 2 lines

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.

Quoted 2 lines

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

Quoted 6 lines
Quoted 4 lines
Quoted 2 lines

(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

Signature · 2 lines
Wei Yang
Help you, Help me
author
#38 lore raw

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

In reply to 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.

---
 lib/xarray.c | 6 +-----
 1 file changed, 1 insertion(+), 5 deletions(-)
lib/xarray.c +1 -5
index 0c5b44def3aa..82570bbbf2a5 100644
@@ -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) {
Signature · 1 line
2.23.0
author
#39 lore raw

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

In reply to 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.

---
 lib/xarray.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)
lib/xarray.c +3 -2
index 82570bbbf2a5..01f64a000e14 100644
@@ -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;
 
Signature · 1 line
2.23.0
author
#40 lore raw

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

In reply to 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.

---
 lib/xarray.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)
lib/xarray.c +3 -2
index 01f64a000e14..9546b2b2dce1 100644
@@ -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;
+			}
 		}
 	}
 
Signature · 1 line
2.23.0