XArray: several cleanups
Subsystems (3)
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
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
@@ -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
Matthew Wilcox
maintainerRe: [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
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
PATCH 2/9 XArray: simplify the calculation of shift
In reply to Wei YangWhen 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
@@ -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
Matthew Wilcox
maintainerRe: [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_SHIFTis 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 <[email protected]>--- lib/xarray.c | 6 +----- 1 file changed, 1 insertion(+), 5 deletions(-)lib/xarray.c +0
-0
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) = 6roundup(6, 6) is 6.
Please be more careful.
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_SHIFTis 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 <[email protected]>--- lib/xarray.c | 6 +----- 1 file changed, 1 insertion(+), 5 deletions(-)lib/xarray.c +0
-0lib/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
PATCH 3/9 XArray: handle a NULL head by itself
In reply to Wei YangFor 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
@@ -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
PATCH 4/9 XArray: don't expect to have more nr_values than count
In reply to Wei YangThe 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
@@ -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
PATCH 5/9 XArray: entry in last level is not expected to be a node
In reply to Wei YangIf 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
@@ -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
Matthew Wilcox
maintainerRe: [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.
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
Matthew Wilcox
maintainerRe: [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.
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; ./mainThe 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
Re: [PATCH 5/9] XArray: entry in last level is not expected to be a node
In reply to Matthew WilcoxQuoted 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
Matthew Wilcox
maintainerRe: [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; ./mainHmm... 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
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; ./mainHmm... 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
Matthew Wilcox
maintainerRe: [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.
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
Matthew Wilcox
maintainerRe: [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
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
Re: [PATCH 5/9] XArray: entry in last level is not expected to be a node
In reply to Matthew WilcoxQuoted 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
Matthew Wilcox
maintainerRe: [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.
Re: [PATCH 5/9] XArray: entry in last level is not expected to be a node
In reply to Matthew WilcoxQuoted 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:64previously 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:44Thread 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:178Thread 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:186SUMMARY: 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
Matthew Wilcox
maintainerRe: [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 address0x60c0031bce81at pc0x00000040b4b3bp0x7f95e87f9bb0sp0x7f95e87f9ba0READ of size 1 at0x60c0031bce81thread 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)
0x60c0031bce81is 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:64previously 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:44Thread 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:178Thread 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:186This 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
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 address0x60c0031bce81at pc0x00000040b4b3bp0x7f95e87f9bb0sp0x7f95e87f9ba0READ of size 1 at0x60c0031bce81thread 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)
0x60c0031bce81is 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:64previously 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:44Thread 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:178Thread 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:186This 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
Re: [PATCH 5/9] XArray: entry in last level is not expected to be a node
In reply to Matthew WilcoxQuoted 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
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
Re: [PATCH 5/9] XArray: entry in last level is not expected to be a node
In reply to Matthew WilcoxQuoted 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
PATCH 6/9 XArray: internal node is a xa_node when it is bigger than XA_ZERO_ENTRY
In reply to Wei YangAs 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
@@ -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
Matthew Wilcox
maintainerRe: [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_ENTRYis a normal node.The checked on
XA_ZERO_ENTRYseems 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
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_ENTRYis a normal node.The checked on
XA_ZERO_ENTRYseems to be more meaningful.257-1023 are also reserved, they just aren't used yet.
XA_ZERO_ENTRYis not guaranteed to be the largest reserved entry.
Then why we choose 4096?
Signature · 2 lines
Wei Yang Help you, Help me
Matthew Wilcox
maintainerRe: [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_ENTRYis a normal node.
Quoted 6 lines
Quoted 4 lines
Quoted 1 line
The checked on
XA_ZERO_ENTRYseems to be more meaningful.257-1023 are also reserved, they just aren't used yet.
XA_ZERO_ENTRYis 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
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_ENTRYis a normal node.The checked on
XA_ZERO_ENTRYseems 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_ENTRYis 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
Matthew Wilcox
maintainerRe: [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_ENTRYis a normal node.The checked on
XA_ZERO_ENTRYseems 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_ENTRYis 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()andalloc_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
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_ENTRYis a normal node.The checked on
XA_ZERO_ENTRYseems 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_ENTRYis 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()andalloc_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
Matthew Wilcox
maintainerRe: [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_ENTRYis a normal node.The checked on
XA_ZERO_ENTRYseems to be more meaningful.257-1023 are also reserved, they just aren't used yet.
XA_ZERO_ENTRYis 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_SIZEwould 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?
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_ENTRYis a normal node.The checked on
XA_ZERO_ENTRYseems to be more meaningful.257-1023 are also reserved, they just aren't used yet.
XA_ZERO_ENTRYis 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_SIZEwould 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
PATCH 7/9 XArray: the NULL xa_node condition is handled in xas_top
In reply to Wei YangFrom 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
@@ -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
PATCH 8/9 XArray: take xas_error() handling for clearer logic
In reply to Wei YangIf 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
@@ -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
PATCH 9/9 XArray: adjust xa_offset till it gets the correct node
In reply to Wei YangDuring 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
@@ -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