12:24 p.m.
The following series gets the radix tree test suite compiling again in
the current linux/master, adds a unit test which exposes a race in the
radix tree multi-order iteration code, and then fixes that race.
This race was initially hit on a v4.15 based kernel and results in a GP
fault. I've described the race in detail in patches 4 and 5.
The fix is simple and necessary, and I think it should be merged for
v4.17.
This tree has gotten positive build confirmation from the 0-day bot,
passes the updated radix tree test suite, xfstests, and the original
test that was hitting the race with the v4.15 based kernel.
Ross Zwisler (5):
radix tree test suite: fix mapshift build target
radix tree test suite: fix compilation issue
radix tree test suite: add item_delete_rcu()
radix tree test suite: multi-order iteration race
radix tree: fix multi-order iteration race
lib/radix-tree.c | 6 ++--
tools/include/linux/spinlock.h | 3 +-
tools/testing/radix-tree/Makefile | 6 ++--
tools/testing/radix-tree/multiorder.c | 63 +++++++++++++++++++++++++++++++++++
tools/testing/radix-tree/test.c | 19 +++++++++++
tools/testing/radix-tree/test.h | 3 ++
6 files changed, 91 insertions(+), 9 deletions(-)
--
2.14.3
12:24 p.m.
New subject: [PATCH 1/5] radix tree test suite: fix mapshift build target
The following commit
commit c6ce3e2fe3da ("radix tree test suite: Add config option for map
shift")
Introduced a phony makefile target called 'mapshift' that ends up
generating the file generated/map-shift.h. This phony target was then
added as a dependency of the top level 'targets' build target, which is
what is run when you go to tools/testing/radix-tree and just type 'make'.
Unfortunately, this phony target doesn't actually work as a dependency, so
you end up getting:
$ make
make: *** No rule to make target 'generated/map-shift.h', needed by
'main.o'. Stop.
make: *** Waiting for unfinished jobs....
Fix this by making the file generated/map-shift.h our real makefile target,
and add this a dependency of the top level build target.
Signed-off-by: Ross Zwisler <ross.zwisler(a)linux.intel.com>
---
tools/testing/radix-tree/Makefile | 6 ++----
1 file changed, 2 insertions(+), 4 deletions(-)
diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile
index fa7ee369b3c9..db66f8a0d4be 100644
--- a/tools/testing/radix-tree/Makefile
+++ b/tools/testing/radix-tree/Makefile
@@ -17,7 +17,7 @@ ifeq ($(BUILD), 32)
LDFLAGS += -m32
endif
-targets: mapshift $(TARGETS)
+targets: generated/map-shift.h $(TARGETS)
main: $(OFILES)
@@ -42,9 +42,7 @@ radix-tree.c: ../../../lib/radix-tree.c
idr.c: ../../../lib/idr.c
sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline //'
< $< > $@
-.PHONY: mapshift
-
-mapshift:
+generated/map-shift.h:
@if ! grep -qws $(SHIFT) generated/map-shift.h; then \
echo "#define RADIX_TREE_MAP_SHIFT $(SHIFT)" > \
generated/map-shift.h; \
--
2.14.3
4 p.m.
New subject: [PATCH 1/5] radix tree test suite: fix mapshift build target
On Thu, May 03, 2018 at 01:24:26PM -0600, Ross Zwisler wrote:
The following commit
commit c6ce3e2fe3da ("radix tree test suite: Add config option for map
shift")
Introduced a phony makefile target called 'mapshift' that ends up
generating the file generated/map-shift.h. This phony target was then
added as a dependency of the top level 'targets' build target, which is
what is run when you go to tools/testing/radix-tree and just type 'make'.
Unfortunately, this phony target doesn't actually work as a dependency, so
you end up getting:
$ make
make: *** No rule to make target 'generated/map-shift.h', needed by
'main.o'. Stop.
make: *** Waiting for unfinished jobs....
Fix this by making the file generated/map-shift.h our real makefile target,
and add this a dependency of the top level build target.
This commit breaks typing 'make SHIFT=6'. It doesn't rebuild the
test suite any more. If I revert this patch, it works. Also, I can't
reproduce the problem you're reporting here. So ... how do I reproduce
it? Otherwise, I'm just going to revert this patch since it regresses
a feature I find useful.
Signed-off-by: Ross Zwisler <ross.zwisler(a)linux.intel.com>
---
tools/testing/radix-tree/Makefile | 6 ++----
1 file changed, 2 insertions(+), 4 deletions(-)
diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile
index fa7ee369b3c9..db66f8a0d4be 100644
--- a/tools/testing/radix-tree/Makefile
+++ b/tools/testing/radix-tree/Makefile
@@ -17,7 +17,7 @@ ifeq ($(BUILD), 32)
LDFLAGS += -m32
endif
-targets: mapshift $(TARGETS)
+targets: generated/map-shift.h $(TARGETS)
main: $(OFILES)
@@ -42,9 +42,7 @@ radix-tree.c: ../../../lib/radix-tree.c
idr.c: ../../../lib/idr.c
sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline
//' < $< > $@
-.PHONY: mapshift
-
-mapshift:
+generated/map-shift.h:
@if ! grep -qws $(SHIFT) generated/map-shift.h; then \
echo "#define RADIX_TREE_MAP_SHIFT $(SHIFT)" > \
generated/map-shift.h; \
--
2.14.3
9:07 a.m.
New subject: [PATCH 1/5] radix tree test suite: fix mapshift build target
On Sun, Jul 15, 2018 at 04:00:52PM -0700, Matthew Wilcox wrote:
On Thu, May 03, 2018 at 01:24:26PM -0600, Ross Zwisler wrote:
> The following commit
>
> commit c6ce3e2fe3da ("radix tree test suite: Add config option for map
> shift")
>
> Introduced a phony makefile target called 'mapshift' that ends up
> generating the file generated/map-shift.h. This phony target was then
> added as a dependency of the top level 'targets' build target, which is
> what is run when you go to tools/testing/radix-tree and just type 'make'.
>
> Unfortunately, this phony target doesn't actually work as a dependency, so
> you end up getting:
>
> $ make
> make: *** No rule to make target 'generated/map-shift.h', needed by
'main.o'. Stop.
> make: *** Waiting for unfinished jobs....
>
> Fix this by making the file generated/map-shift.h our real makefile target,
> and add this a dependency of the top level build target.
This commit breaks typing 'make SHIFT=6'. It doesn't rebuild the
test suite any more. If I revert this patch, it works. Also, I can't
reproduce the problem you're reporting here. So ... how do I reproduce
it? Otherwise, I'm just going to revert this patch since it regresses
a feature I find useful.
The test suite builds fine for me in v4.17. From a completely clean tree, in
tools/testing/radix-tree:
$ make
sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline //'
< ../../../lib/radix-tree.c > radix-tree.c
sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline //'
< ../../../lib/idr.c > idr.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o main.o
main.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o linux.o
linux.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o test.o
test.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o find_bit.o
../../lib/find_bit.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
regression1.o regression1.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
regression2.o regression2.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
regression3.o regression3.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
tag_check.o tag_check.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
multiorder.o multiorder.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o idr-test.o
idr-test.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
iteration_check.o iteration_check.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
benchmark.o benchmark.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o idr.o
idr.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
radix-tree.o radix-tree.c
cc -fsanitize=address multiorder.o radix-tree.o idr.o linux.o test.o find_bit.o
-lpthread -lurcu -o multiorder
cc -fsanitize=address main.o radix-tree.o idr.o linux.o test.o find_bit.o regression1.o
regression2.o regression3.o tag_check.o multiorder.o idr-test.o iteration_check.o
benchmark.o -lpthread -lurcu -o main
cc -fsanitize=address idr-test.o radix-tree.o idr.o linux.o test.o find_bit.o
-lpthread -lurcu -o idr-test
and you can successfully run the radix tree test suite by running 'main'.
With the above mentioned commit reverted, this build fails:
$ make
make: *** No rule to make target 'generated/map-shift.h', needed by
'main.o'. Stop.
make: *** Waiting for unfinished jobs....
If you want generated/map-shift.h to be rebuilt each time you run 'make' so
that it can take a new SHIFT argument, that's fine, but let's not make users
run 'make mapshift' before an actual 'make' will work, which is where
we're at
with v4.17 with my commit reverted.
Incidentally, in the current linux/master the radix tree test suite again
fails to build:
$ make
sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline //'
< ../../../lib/radix-tree.c > radix-tree.c
sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline //'
< ../../../lib/idr.c > idr.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o main.o
main.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o linux.o
linux.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o test.o
test.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o find_bit.o
../../lib/find_bit.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
regression1.o regression1.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
regression2.o regression2.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
regression3.o regression3.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
tag_check.o tag_check.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
multiorder.o multiorder.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o idr-test.o
idr-test.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
iteration_check.o iteration_check.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
benchmark.o benchmark.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o idr.o
idr.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
radix-tree.o radix-tree.c
idr.c:7:10: fatal error: linux/xarray.h: No such file or directory
#include <linux/xarray.h>
^~~~~~~~~~~~~~~~
compilation terminated.
make: *** [<builtin>: idr.o] Error 1
Can you look into this?
0-day folks, would it be possible for you to add a radix tree build & test
runs to your automated tests? We would really appreciate any help in reducing
this kind of breakage, which seems to happen pretty often.
12:52 p.m.
New subject: [PATCH 1/5] radix tree test suite: fix mapshift build target
On Mon, Jul 16, 2018 at 10:07:10AM -0600, Ross Zwisler wrote:
On Sun, Jul 15, 2018 at 04:00:52PM -0700, Matthew Wilcox wrote:
> On Thu, May 03, 2018 at 01:24:26PM -0600, Ross Zwisler wrote:
> > Unfortunately, this phony target doesn't actually work as a dependency, so
> > you end up getting:
> >
> > $ make
> > make: *** No rule to make target 'generated/map-shift.h', needed by
'main.o'. Stop.
> > make: *** Waiting for unfinished jobs....
> >
> > Fix this by making the file generated/map-shift.h our real makefile target,
> > and add this a dependency of the top level build target.
>
> This commit breaks typing 'make SHIFT=6'. It doesn't rebuild the
> test suite any more. If I revert this patch, it works. Also, I can't
> reproduce the problem you're reporting here. So ... how do I reproduce
> it? Otherwise, I'm just going to revert this patch since it regresses
> a feature I find useful.
The test suite builds fine for me in v4.17. From a completely clean tree, in
tools/testing/radix-tree:
$ make
sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline
//' < ../../../lib/radix-tree.c > radix-tree.c
sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline
//' < ../../../lib/idr.c > idr.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o main.o
main.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o linux.o
linux.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o test.o
test.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
find_bit.o ../../lib/find_bit.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
regression1.o regression1.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
regression2.o regression2.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
regression3.o regression3.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
tag_check.o tag_check.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
multiorder.o multiorder.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
idr-test.o idr-test.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
iteration_check.o iteration_check.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
benchmark.o benchmark.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o idr.o
idr.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
radix-tree.o radix-tree.c
cc -fsanitize=address multiorder.o radix-tree.o idr.o linux.o test.o find_bit.o
-lpthread -lurcu -o multiorder
cc -fsanitize=address main.o radix-tree.o idr.o linux.o test.o find_bit.o
regression1.o regression2.o regression3.o tag_check.o multiorder.o idr-test.o
iteration_check.o benchmark.o -lpthread -lurcu -o main
cc -fsanitize=address idr-test.o radix-tree.o idr.o linux.o test.o find_bit.o
-lpthread -lurcu -o idr-test
and you can successfully run the radix tree test suite by running 'main'.
With the above mentioned commit reverted, this build fails:
$ make
make: *** No rule to make target 'generated/map-shift.h', needed by
'main.o'. Stop.
make: *** Waiting for unfinished jobs....
OK ... what version of make are you using? Because this works fine for me:
$ git clone linux clean
$ cd clean
$ git checkout v4.17
$ cd tools/testing/radix-tree/
$ git revert 8d9fa88edd5e360b71765feeadb915d4066c9684
$ make
$ make --version
GNU Make 4.1
Built for x86_64-pc-linux-gnu
It's Debian's Version: 4.1-9.1
If you want generated/map-shift.h to be rebuilt each time you run
'make' so
that it can take a new SHIFT argument, that's fine, but let's not make users
run 'make mapshift' before an actual 'make' will work, which is where
we're at
with v4.17 with my commit reverted.
I don't want it to be rebuilt, I want it to be checked before each
build, regenerated if SHIFT has changed, and everything to rebuild if
it has changed.
Incidentally, in the current linux/master the radix tree test suite
again
fails to build:
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
radix-tree.o radix-tree.c
idr.c:7:10: fatal error: linux/xarray.h: No such file or directory
#include <linux/xarray.h>
^~~~~~~~~~~~~~~~
compilation terminated.
make: *** [<builtin>: idr.o] Error 1
Can you look into this?
Ah ... Andrew broke it fixing something else ;-) The first commit in
my xarray branch fixes it -- looks like I tested my own commits but not
the commit I based on ;-)
diff --git a/tools/testing/radix-tree/linux/xarray.h
b/tools/testing/radix-tree/linux/xarray.h
new file mode 100644
index 000000000000..df3812cda376
--- /dev/null
+++ b/tools/testing/radix-tree/linux/xarray.h
@@ -0,0 +1,2 @@
+#include "generated/map-shift.h"
+#include "../../../../include/linux/xarray.h"
0-day folks, would it be possible for you to add a radix tree build
& test
runs to your automated tests? We would really appreciate any help in reducing
this kind of breakage, which seems to happen pretty often.
Yeah, that would be good.
2:08 p.m.
New subject: [PATCH 1/5] radix tree test suite: fix mapshift build target
On Mon, Jul 16, 2018 at 12:52:49PM -0700, Matthew Wilcox wrote:
On Mon, Jul 16, 2018 at 10:07:10AM -0600, Ross Zwisler wrote:
<>
OK ... what version of make are you using? Because this works fine
for me:
$ git clone linux clean
$ cd clean
$ git checkout v4.17
$ cd tools/testing/radix-tree/
$ git revert 8d9fa88edd5e360b71765feeadb915d4066c9684
$ make
$ make --version
GNU Make 4.1
Built for x86_64-pc-linux-gnu
It's Debian's Version: 4.1-9.1
$ make --version
GNU Make 4.2.1
Built for x86_64-redhat-linux-gnu
The one from Fedora 27.
> If you want generated/map-shift.h to be rebuilt each time you
run 'make' so
> that it can take a new SHIFT argument, that's fine, but let's not make
users
> run 'make mapshift' before an actual 'make' will work, which is
where we're at
> with v4.17 with my commit reverted.
I don't want it to be rebuilt, I want it to be checked before each
build, regenerated if SHIFT has changed, and everything to rebuild if
it has changed.
Sure, sounds good.
7:41 p.m.
New subject: [PATCH 1/5] radix tree test suite: fix mapshift build target
On Mon, Jul 16, 2018 at 03:08:20PM -0600, Ross Zwisler wrote:
On Mon, Jul 16, 2018 at 12:52:49PM -0700, Matthew Wilcox wrote:
> On Mon, Jul 16, 2018 at 10:07:10AM -0600, Ross Zwisler wrote:
<>
> OK ... what version of make are you using? Because this works fine for me:
>
> $ git clone linux clean
> $ cd clean
> $ git checkout v4.17
> $ cd tools/testing/radix-tree/
> $ git revert 8d9fa88edd5e360b71765feeadb915d4066c9684
> $ make
>
> $ make --version
> GNU Make 4.1
> Built for x86_64-pc-linux-gnu
>
> It's Debian's Version: 4.1-9.1
$ make --version
GNU Make 4.2.1
Built for x86_64-redhat-linux-gnu
The one from Fedora 27.
Huh. I just tried 4.2.1-1.1 from Debian unstable and that doesn't
produce the problem either. I'm not sure how to proceed at this point.
I'm really not a makefile expert.
4:45 p.m.
New subject: [PATCH 1/5] radix tree test suite: fix mapshift build target
On Mon, Jul 16, 2018 at 07:41:32PM -0700, Matthew Wilcox wrote:
On Mon, Jul 16, 2018 at 03:08:20PM -0600, Ross Zwisler wrote:
> On Mon, Jul 16, 2018 at 12:52:49PM -0700, Matthew Wilcox wrote:
> > On Mon, Jul 16, 2018 at 10:07:10AM -0600, Ross Zwisler wrote:
> <>
> > OK ... what version of make are you using? Because this works fine for me:
> >
> > $ git clone linux clean
> > $ cd clean
> > $ git checkout v4.17
> > $ cd tools/testing/radix-tree/
> > $ git revert 8d9fa88edd5e360b71765feeadb915d4066c9684
> > $ make
> >
> > $ make --version
> > GNU Make 4.1
> > Built for x86_64-pc-linux-gnu
> >
> > It's Debian's Version: 4.1-9.1
>
> $ make --version
> GNU Make 4.2.1
> Built for x86_64-redhat-linux-gnu
>
> The one from Fedora 27.
Huh. I just tried 4.2.1-1.1 from Debian unstable and that doesn't
produce the problem either. I'm not sure how to proceed at this point.
I'm really not a makefile expert.
This smells like a problem we just hit with make 4.2.1 in fedora 28
in fstests - the regex expanstion has been screwed up such that
things like [a-z] will match [A-Z] and other things as well. Debian
is unaffected, apparently fedora has a backport of stuff from the
as-yet-unreleased next version of make/glibc. See this thread:
https://www.spinics.net/lists/fstests/msg10200.html
Try setting LANG=C and seeing if the problem goes away....
Cheers,
Dave.
--
Dave Chinner
david(a)fromorbit.com
8:11 p.m.
New subject: [PATCH 1/5] radix tree test suite: fix mapshift build target
On Sun, Jul 22, 2018 at 09:45:50AM +1000, Dave Chinner wrote:
On Mon, Jul 16, 2018 at 07:41:32PM -0700, Matthew Wilcox wrote:
> On Mon, Jul 16, 2018 at 03:08:20PM -0600, Ross Zwisler wrote:
> > On Mon, Jul 16, 2018 at 12:52:49PM -0700, Matthew Wilcox wrote:
> > > On Mon, Jul 16, 2018 at 10:07:10AM -0600, Ross Zwisler wrote:
> > <>
> > > OK ... what version of make are you using? Because this works fine for
me:
> > >
> > > $ git clone linux clean
> > > $ cd clean
> > > $ git checkout v4.17
> > > $ cd tools/testing/radix-tree/
> > > $ git revert 8d9fa88edd5e360b71765feeadb915d4066c9684
> > > $ make
> > >
> > > $ make --version
> > > GNU Make 4.1
> > > Built for x86_64-pc-linux-gnu
> > >
> > > It's Debian's Version: 4.1-9.1
> >
> > $ make --version
> > GNU Make 4.2.1
> > Built for x86_64-redhat-linux-gnu
> >
> > The one from Fedora 27.
>
> Huh. I just tried 4.2.1-1.1 from Debian unstable and that doesn't
> produce the problem either. I'm not sure how to proceed at this point.
> I'm really not a makefile expert.
This smells like a problem we just hit with make 4.2.1 in fedora 28
in fstests - the regex expanstion has been screwed up such that
things like [a-z] will match [A-Z] and other things as well. Debian
is unaffected, apparently fedora has a backport of stuff from the
as-yet-unreleased next version of make/glibc. See this thread:
https://www.spinics.net/lists/fstests/msg10200.html
Try setting LANG=C and seeing if the problem goes away....
Hey Dave, we root caused this difference to to be the fact that I had 'make'
aliased to 'make -j32' in my .bashrc. Matthew was running a singled threaded
build, while I was running a multi-threaded one. When Matthew ran a
multi-threaded build, he was able to reproduce the issue.
So, essentially I think that the makefile just needs to be enhanced so that
all the dependencies are explicit to allow multi-threaded builds to work
properly.
8:18 p.m.
New subject: [PATCH 1/5] radix tree test suite: fix mapshift build target
On Mon, Jul 16, 2018 at 10:07:10AM -0600, Ross Zwisler wrote:
Incidentally, in the current linux/master the radix tree test suite
again
fails to build:
$ make
sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline
//' < ../../../lib/radix-tree.c > radix-tree.c
sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline
//' < ../../../lib/idr.c > idr.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o main.o
main.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o linux.o
linux.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o test.o
test.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
find_bit.o ../../lib/find_bit.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
regression1.o regression1.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
regression2.o regression2.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
regression3.o regression3.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
tag_check.o tag_check.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
multiorder.o multiorder.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
idr-test.o idr-test.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
iteration_check.o iteration_check.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
benchmark.o benchmark.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o idr.o
idr.c
cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
radix-tree.o radix-tree.c
idr.c:7:10: fatal error: linux/xarray.h: No such file or directory
#include <linux/xarray.h>
^~~~~~~~~~~~~~~~
compilation terminated.
Umm. I think I know the problem here. I have a suspicion that either
Fedora or you have changed make to be parallel by default (or you're
lying to me and saying you typed 'make' when you actually typed 'make
-j4', but I'm pretty sure you wouldn't do that). Because there's no
way you'd get this output if you were compiling with make -j1.
Indeed, if I revert your commit and then build with make -j4, I see the
same error as you. I'll look at how to fix this properly tomorrow.
10:17 a.m.
New subject: [PATCH 1/5] radix tree test suite: fix mapshift build target
On Mon, Jul 16, 2018 at 08:18:11PM -0700, Matthew Wilcox wrote:
On Mon, Jul 16, 2018 at 10:07:10AM -0600, Ross Zwisler wrote:
> Incidentally, in the current linux/master the radix tree test suite again
> fails to build:
>
> $ make
> sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline
//' < ../../../lib/radix-tree.c > radix-tree.c
> sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline
//' < ../../../lib/idr.c > idr.c
> cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
main.o main.c
> cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
linux.o linux.c
> cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
test.o test.c
> cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
find_bit.o ../../lib/find_bit.c
> cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
regression1.o regression1.c
> cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
regression2.o regression2.c
> cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
regression3.o regression3.c
> cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
tag_check.o tag_check.c
> cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
multiorder.o multiorder.c
> cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
idr-test.o idr-test.c
> cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
iteration_check.o iteration_check.c
> cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
benchmark.o benchmark.c
> cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
idr.o idr.c
> cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address -c -o
radix-tree.o radix-tree.c
> idr.c:7:10: fatal error: linux/xarray.h: No such file or directory
> #include <linux/xarray.h>
> ^~~~~~~~~~~~~~~~
> compilation terminated.
Umm. I think I know the problem here. I have a suspicion that either
Fedora or you have changed make to be parallel by default (or you're
lying to me and saying you typed 'make' when you actually typed 'make
-j4', but I'm pretty sure you wouldn't do that). Because there's no
way you'd get this output if you were compiling with make -j1.
Indeed, if I revert your commit and then build with make -j4, I see the
same error as you. I'll look at how to fix this properly tomorrow.
Ah, yep.
$ alias make
alias make='make -j32'
You've found it. :)
12:24 p.m.
New subject: [PATCH 2/5] radix tree test suite: fix compilation issue
Pulled from a patch from Matthew Wilcox entitled
"xarray: Add definition of struct xarray":
From: Matthew Wilcox <mawilcox(a)microsoft.com>
Signed-off-by: Matthew Wilcox <mawilcox(a)microsoft.com>
https://patchwork.kernel.org/patch/10341249/
These defines fix this compilation error:
In file included from ./linux/radix-tree.h:6:0,
from ./linux/../../../../include/linux/idr.h:15,
from ./linux/idr.h:1,
from idr.c:4:
./linux/../../../../include/linux/idr.h: In function ‘idr_init_base’:
./linux/../../../../include/linux/radix-tree.h:129:2: warning: implicit declaration of
function ‘spin_lock_init’; did you mean ‘spinlock_t’? [-Wimplicit-function-declaration]
spin_lock_init(&(root)->xa_lock); \
^
./linux/../../../../include/linux/idr.h:126:2: note: in expansion of macro
‘INIT_RADIX_TREE’
INIT_RADIX_TREE(&idr->idr_rt, IDR_RT_MARKER);
^~~~~~~~~~~~~~~
by providing a spin_lock_init() wrapper for the v4.17-rc* version of the
radix tree test suite.
Signed-off-by: Ross Zwisler <ross.zwisler(a)linux.intel.com>
---
tools/include/linux/spinlock.h | 3 ++-
1 file changed, 2 insertions(+), 1 deletion(-)
diff --git a/tools/include/linux/spinlock.h b/tools/include/linux/spinlock.h
index b21b586b9854..1738c0391da4 100644
--- a/tools/include/linux/spinlock.h
+++ b/tools/include/linux/spinlock.h
@@ -6,8 +6,9 @@
#include <stdbool.h>
#define spinlock_t pthread_mutex_t
-#define DEFINE_SPINLOCK(x) pthread_mutex_t x = PTHREAD_MUTEX_INITIALIZER;
+#define DEFINE_SPINLOCK(x) pthread_mutex_t x = PTHREAD_MUTEX_INITIALIZER
#define __SPIN_LOCK_UNLOCKED(x) (pthread_mutex_t)PTHREAD_MUTEX_INITIALIZER
+#define spin_lock_init(x) pthread_mutex_init(x, NULL)
#define spin_lock_irqsave(x, f) (void)f, pthread_mutex_lock(x)
#define spin_unlock_irqrestore(x, f) (void)f, pthread_mutex_unlock(x)
--
2.14.3
12:24 p.m.
New subject: [PATCH 3/5] radix tree test suite: add item_delete_rcu()
Currently the lifetime of "struct item" entries in the radix tree are not
controlled by RCU, but are instead deleted inline as they are removed from
the tree.
In the following patches we add a test which has threads iterating over
items pulled from the tree and verifying them in an
rcu_read_lock()/rcu_read_unlock() section. This means that though an item
has been removed from the tree it could still be being worked on by other
threads until the RCU grace period expires. So, we need to actually free
the "struct item" structures at the end of the grace period, just as we do
with "struct radix_tree_node" items.
Signed-off-by: Ross Zwisler <ross.zwisler(a)linux.intel.com>
---
tools/testing/radix-tree/test.c | 19 +++++++++++++++++++
tools/testing/radix-tree/test.h | 2 ++
2 files changed, 21 insertions(+)
diff --git a/tools/testing/radix-tree/test.c b/tools/testing/radix-tree/test.c
index 5978ab1f403d..def6015570b2 100644
--- a/tools/testing/radix-tree/test.c
+++ b/tools/testing/radix-tree/test.c
@@ -75,6 +75,25 @@ int item_delete(struct radix_tree_root *root, unsigned long index)
return 0;
}
+static void item_free_rcu(struct rcu_head *head)
+{
+ struct item *item = container_of(head, struct item, rcu_head);
+
+ free(item);
+}
+
+int item_delete_rcu(struct radix_tree_root *root, unsigned long index)
+{
+ struct item *item = radix_tree_delete(root, index);
+
+ if (item) {
+ item_sanity(item, index);
+ call_rcu(&item->rcu_head, item_free_rcu);
+ return 1;
+ }
+ return 0;
+}
+
void item_check_present(struct radix_tree_root *root, unsigned long index)
{
struct item *item;
diff --git a/tools/testing/radix-tree/test.h b/tools/testing/radix-tree/test.h
index d9c031dbeb1a..8cf4a7a7f94c 100644
--- a/tools/testing/radix-tree/test.h
+++ b/tools/testing/radix-tree/test.h
@@ -5,6 +5,7 @@
#include <linux/rcupdate.h>
struct item {
+ struct rcu_head rcu_head;
unsigned long index;
unsigned int order;
};
@@ -15,6 +16,7 @@ int item_insert(struct radix_tree_root *root, unsigned long index);
int item_insert_order(struct radix_tree_root *root, unsigned long index,
unsigned order);
int item_delete(struct radix_tree_root *root, unsigned long index);
+int item_delete_rcu(struct radix_tree_root *root, unsigned long index);
struct item *item_lookup(struct radix_tree_root *root, unsigned long index);
void item_check_present(struct radix_tree_root *root, unsigned long index);
--
2.14.3
12:24 p.m.
New subject: [PATCH 4/5] radix tree test suite: multi-order iteration race
Add a test which shows a race in the multi-order iteration code. This test
reliably hits the race in under a second on my machine, and is the result
of a real bug report against kernel a production v4.15 based kernel
(4.15.6-300.fc27.x86_64). With a real kernel this issue is hit when using
order 9 PMD DAX radix tree entries.
The race has to do with how we tear down multi-order sibling entries when
we are removing an item from the tree. Remember that an order 2 entry
looks like this:
struct radix_tree_node.slots[] = [entry][sibling][sibling][sibling]
where 'entry' is in some slot in the struct radix_tree_node, and the three
slots following 'entry' contain sibling pointers which point back to
'entry.'
When we delete 'entry' from the tree, we call :
radix_tree_delete()
radix_tree_delete_item()
__radix_tree_delete()
replace_slot()
replace_slot() first removes the siblings in order from the first to the
last, then at then replaces 'entry' with NULL. This means that for a brief
period of time we end up with one or more of the siblings removed, so:
struct radix_tree_node.slots[] = [entry][NULL][sibling][sibling]
This causes an issue if you have a reader iterating over the slots in the
tree via radix_tree_for_each_slot() while only under
rcu_read_lock()/rcu_read_unlock() protection. This is a common case in
mm/filemap.c.
The issue is that when __radix_tree_next_slot() => skip_siblings() tries to
skip over the sibling entries in the slots, it currently does so with an
exact match on the slot directly preceding our current slot. Normally this
works:
V preceding slot
struct radix_tree_node.slots[] = [entry][sibling][sibling][sibling]
^ current slot
This lets you find the first sibling, and you skip them all in order.
But in the case where one of the siblings is NULL, that slot is skipped and
then our sibling detection is interrupted:
V preceding slot
struct radix_tree_node.slots[] = [entry][NULL][sibling][sibling]
^ current slot
This means that the sibling pointers aren't recognized since they point all
the way back to 'entry', so we think that they are normal internal radix
tree pointers. This causes us to think we need to walk down to a struct
radix_tree_node starting at the address of 'entry'.
In a real running kernel this will crash the thread with a GP fault when
you try and dereference the slots in your broken node starting at 'entry'.
In the radix tree test suite this will be caught by the address sanitizer:
==27063==ERROR: AddressSanitizer: heap-buffer-overflow on address
0x60c0008ae400 at pc 0x00000040ce4f bp 0x7fa89b8fcad0 sp 0x7fa89b8fcac0
READ of size 8 at 0x60c0008ae400 thread T3
#0 0x40ce4e in __radix_tree_next_slot
/home/rzwisler/project/linux/tools/testing/radix-tree/radix-tree.c:1660
#1 0x4022cc in radix_tree_next_slot linux/../../../../include/linux/radix-tree.h:567
#2 0x4022cc in iterator_func
/home/rzwisler/project/linux/tools/testing/radix-tree/multiorder.c:655
#3 0x7fa8a088d50a in start_thread (/lib64/libpthread.so.0+0x750a)
#4 0x7fa8a03bd16e in clone (/lib64/libc.so.6+0xf516e)
Signed-off-by: Ross Zwisler <ross.zwisler(a)linux.intel.com>
---
tools/testing/radix-tree/multiorder.c | 63 +++++++++++++++++++++++++++++++++++
tools/testing/radix-tree/test.h | 1 +
2 files changed, 64 insertions(+)
diff --git a/tools/testing/radix-tree/multiorder.c
b/tools/testing/radix-tree/multiorder.c
index 59245b3d587c..7bf405638b0b 100644
--- a/tools/testing/radix-tree/multiorder.c
+++ b/tools/testing/radix-tree/multiorder.c
@@ -16,6 +16,7 @@
#include <linux/radix-tree.h>
#include <linux/slab.h>
#include <linux/errno.h>
+#include <pthread.h>
#include "test.h"
@@ -624,6 +625,67 @@ static void multiorder_account(void)
item_kill_tree(&tree);
}
+bool stop_iteration = false;
+
+static void *creator_func(void *ptr)
+{
+ /* 'order' is set up to ensure we have sibling entries */
+ unsigned int order = RADIX_TREE_MAP_SHIFT - 1;
+ struct radix_tree_root *tree = ptr;
+ int i;
+
+ for (i = 0; i < 10000; i++) {
+ item_insert_order(tree, 0, order);
+ item_delete_rcu(tree, 0);
+ }
+
+ stop_iteration = true;
+ return NULL;
+}
+
+static void *iterator_func(void *ptr)
+{
+ struct radix_tree_root *tree = ptr;
+ struct radix_tree_iter iter;
+ struct item *item;
+ void **slot;
+
+ while (!stop_iteration) {
+ rcu_read_lock();
+ radix_tree_for_each_slot(slot, tree, &iter, 0) {
+ item = radix_tree_deref_slot(slot);
+
+ if (!item)
+ continue;
+ if (radix_tree_deref_retry(item)) {
+ slot = radix_tree_iter_retry(&iter);
+ continue;
+ }
+
+ item_sanity(item, iter.index);
+ }
+ rcu_read_unlock();
+ }
+ return NULL;
+}
+
+static void multiorder_iteration_race(void)
+{
+ const int num_threads = sysconf(_SC_NPROCESSORS_ONLN);
+ pthread_t worker_thread[num_threads];
+ RADIX_TREE(tree, GFP_KERNEL);
+ int i;
+
+ pthread_create(&worker_thread[0], NULL, &creator_func, &tree);
+ for (i = 1; i < num_threads; i++)
+ pthread_create(&worker_thread[i], NULL, &iterator_func, &tree);
+
+ for (i = 0; i < num_threads; i++)
+ pthread_join(worker_thread[i], NULL);
+
+ item_kill_tree(&tree);
+}
+
void multiorder_checks(void)
{
int i;
@@ -644,6 +706,7 @@ void multiorder_checks(void)
multiorder_join();
multiorder_split();
multiorder_account();
+ multiorder_iteration_race();
radix_tree_cpu_dead(0);
}
diff --git a/tools/testing/radix-tree/test.h b/tools/testing/radix-tree/test.h
index 8cf4a7a7f94c..31f1d9b6f506 100644
--- a/tools/testing/radix-tree/test.h
+++ b/tools/testing/radix-tree/test.h
@@ -13,6 +13,7 @@ struct item {
struct item *item_create(unsigned long index, unsigned int order);
int __item_insert(struct radix_tree_root *root, struct item *item);
int item_insert(struct radix_tree_root *root, unsigned long index);
+void item_sanity(struct item *item, unsigned long index);
int item_insert_order(struct radix_tree_root *root, unsigned long index,
unsigned order);
int item_delete(struct radix_tree_root *root, unsigned long index);
--
2.14.3
12:24 p.m.
New subject: [PATCH 5/5] radix tree: fix multi-order iteration race
Fix a race in the multi-order iteration code which causes the kernel to hit
a GP fault. This was first seen with a production v4.15 based kernel
(4.15.6-300.fc27.x86_64) utilizing a DAX workload which used order 9 PMD
DAX entries.
The race has to do with how we tear down multi-order sibling entries when
we are removing an item from the tree. Remember for example that an order
2 entry looks like this:
struct radix_tree_node.slots[] = [entry][sibling][sibling][sibling]
where 'entry' is in some slot in the struct radix_tree_node, and the three
slots following 'entry' contain sibling pointers which point back to
'entry.'
When we delete 'entry' from the tree, we call :
radix_tree_delete()
radix_tree_delete_item()
__radix_tree_delete()
replace_slot()
replace_slot() first removes the siblings in order from the first to the
last, then at then replaces 'entry' with NULL. This means that for a brief
period of time we end up with one or more of the siblings removed, so:
struct radix_tree_node.slots[] = [entry][NULL][sibling][sibling]
This causes an issue if you have a reader iterating over the slots in the
tree via radix_tree_for_each_slot() while only under
rcu_read_lock()/rcu_read_unlock() protection. This is a common case in
mm/filemap.c.
The issue is that when __radix_tree_next_slot() => skip_siblings() tries to
skip over the sibling entries in the slots, it currently does so with an
exact match on the slot directly preceding our current slot. Normally this
works:
V preceding slot
struct radix_tree_node.slots[] = [entry][sibling][sibling][sibling]
^ current slot
This lets you find the first sibling, and you skip them all in order.
But in the case where one of the siblings is NULL, that slot is skipped and
then our sibling detection is interrupted:
V preceding slot
struct radix_tree_node.slots[] = [entry][NULL][sibling][sibling]
^ current slot
This means that the sibling pointers aren't recognized since they point all
the way back to 'entry', so we think that they are normal internal radix
tree pointers. This causes us to think we need to walk down to a struct
radix_tree_node starting at the address of 'entry'.
In a real running kernel this will crash the thread with a GP fault when
you try and dereference the slots in your broken node starting at 'entry'.
We fix this race by fixing the way that skip_siblings() detects sibling
nodes. Instead of testing against the preceding slot we instead look for
siblings via is_sibling_entry() which compares against the position of the
struct radix_tree_node.slots[] array. This ensures that sibling entries
are properly identified, even if they are no longer contiguous with the
'entry' they point to.
Signed-off-by: Ross Zwisler <ross.zwisler(a)linux.intel.com>
Reported-by: CR, Sapthagirish <sapthagirish.cr(a)intel.com>
Fixes: commit 148deab223b2 ("radix-tree: improve multiorder iterators")
Cc: <stable(a)vger.kernel.org>
---
lib/radix-tree.c | 6 ++----
1 file changed, 2 insertions(+), 4 deletions(-)
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index da9e10c827df..43e0cbedc3a0 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -1612,11 +1612,9 @@ static void set_iter_tags(struct radix_tree_iter *iter,
static void __rcu **skip_siblings(struct radix_tree_node **nodep,
void __rcu **slot, struct radix_tree_iter *iter)
{
- void *sib = node_to_entry(slot - 1);
-
while (iter->index < iter->next_index) {
*nodep = rcu_dereference_raw(*slot);
- if (*nodep && *nodep != sib)
+ if (*nodep && !is_sibling_entry(iter->node, *nodep))
return slot;
slot++;
iter->index = __radix_tree_iter_add(iter, 1);
@@ -1631,7 +1629,7 @@ void __rcu **__radix_tree_next_slot(void __rcu **slot,
struct radix_tree_iter *iter, unsigned flags)
{
unsigned tag = flags & RADIX_TREE_ITER_TAG_MASK;
- struct radix_tree_node *node = rcu_dereference_raw(*slot);
+ struct radix_tree_node *node;
slot = skip_siblings(&node, slot, iter);
--
2.14.3
5:46 a.m.
New subject: [PATCH 5/5] radix tree: fix multi-order iteration race
On Thu 03-05-18 13:24:30, Ross Zwisler wrote:
Fix a race in the multi-order iteration code which causes the kernel
to hit
a GP fault. This was first seen with a production v4.15 based kernel
(4.15.6-300.fc27.x86_64) utilizing a DAX workload which used order 9 PMD
DAX entries.
The race has to do with how we tear down multi-order sibling entries when
we are removing an item from the tree. Remember for example that an order
2 entry looks like this:
struct radix_tree_node.slots[] = [entry][sibling][sibling][sibling]
where 'entry' is in some slot in the struct radix_tree_node, and the three
slots following 'entry' contain sibling pointers which point back to
'entry.'
When we delete 'entry' from the tree, we call :
radix_tree_delete()
radix_tree_delete_item()
__radix_tree_delete()
replace_slot()
replace_slot() first removes the siblings in order from the first to the
last, then at then replaces 'entry' with NULL. This means that for a brief
period of time we end up with one or more of the siblings removed, so:
struct radix_tree_node.slots[] = [entry][NULL][sibling][sibling]
This causes an issue if you have a reader iterating over the slots in the
tree via radix_tree_for_each_slot() while only under
rcu_read_lock()/rcu_read_unlock() protection. This is a common case in
mm/filemap.c.
The issue is that when __radix_tree_next_slot() => skip_siblings() tries to
skip over the sibling entries in the slots, it currently does so with an
exact match on the slot directly preceding our current slot. Normally this
works:
V preceding slot
struct radix_tree_node.slots[] = [entry][sibling][sibling][sibling]
^ current slot
This lets you find the first sibling, and you skip them all in order.
But in the case where one of the siblings is NULL, that slot is skipped and
then our sibling detection is interrupted:
V preceding slot
struct radix_tree_node.slots[] = [entry][NULL][sibling][sibling]
^ current slot
This means that the sibling pointers aren't recognized since they point all
the way back to 'entry', so we think that they are normal internal radix
tree pointers. This causes us to think we need to walk down to a struct
radix_tree_node starting at the address of 'entry'.
In a real running kernel this will crash the thread with a GP fault when
you try and dereference the slots in your broken node starting at 'entry'.
We fix this race by fixing the way that skip_siblings() detects sibling
nodes. Instead of testing against the preceding slot we instead look for
siblings via is_sibling_entry() which compares against the position of the
struct radix_tree_node.slots[] array. This ensures that sibling entries
are properly identified, even if they are no longer contiguous with the
'entry' they point to.
Signed-off-by: Ross Zwisler <ross.zwisler(a)linux.intel.com>
Reported-by: CR, Sapthagirish <sapthagirish.cr(a)intel.com>
Fixes: commit 148deab223b2 ("radix-tree: improve multiorder iterators")
Cc: <stable(a)vger.kernel.org>
Looks good to me. You can add:
Reviewed-by: Jan Kara <jack(a)suse.cz>
Honza
---
lib/radix-tree.c | 6 ++----
1 file changed, 2 insertions(+), 4 deletions(-)
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index da9e10c827df..43e0cbedc3a0 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -1612,11 +1612,9 @@ static void set_iter_tags(struct radix_tree_iter *iter,
static void __rcu **skip_siblings(struct radix_tree_node **nodep,
void __rcu **slot, struct radix_tree_iter *iter)
{
- void *sib = node_to_entry(slot - 1);
-
while (iter->index < iter->next_index) {
*nodep = rcu_dereference_raw(*slot);
- if (*nodep && *nodep != sib)
+ if (*nodep && !is_sibling_entry(iter->node, *nodep))
return slot;
slot++;
iter->index = __radix_tree_iter_add(iter, 1);
@@ -1631,7 +1629,7 @@ void __rcu **__radix_tree_next_slot(void __rcu **slot,
struct radix_tree_iter *iter, unsigned flags)
{
unsigned tag = flags & RADIX_TREE_ITER_TAG_MASK;
- struct radix_tree_node *node = rcu_dereference_raw(*slot);
+ struct radix_tree_node *node;
slot = skip_siblings(&node, slot, iter);
--
2.14.3
--
Jan Kara <jack(a)suse.com>
SUSE Labs, CR
8:09 a.m.
New subject: [PATCH 5/5] radix tree: fix multi-order iteration race
On Wed, May 09, 2018 at 02:46:11PM +0200, Jan Kara wrote:
On Thu 03-05-18 13:24:30, Ross Zwisler wrote:
> Fix a race in the multi-order iteration code which causes the kernel to hit
> a GP fault. This was first seen with a production v4.15 based kernel
> (4.15.6-300.fc27.x86_64) utilizing a DAX workload which used order 9 PMD
> DAX entries.
>
> The race has to do with how we tear down multi-order sibling entries when
> we are removing an item from the tree. Remember for example that an order
> 2 entry looks like this:
>
> struct radix_tree_node.slots[] = [entry][sibling][sibling][sibling]
>
> where 'entry' is in some slot in the struct radix_tree_node, and the three
> slots following 'entry' contain sibling pointers which point back to
> 'entry.'
>
> When we delete 'entry' from the tree, we call :
> radix_tree_delete()
> radix_tree_delete_item()
> __radix_tree_delete()
> replace_slot()
>
> replace_slot() first removes the siblings in order from the first to the
> last, then at then replaces 'entry' with NULL. This means that for a brief
> period of time we end up with one or more of the siblings removed, so:
>
> struct radix_tree_node.slots[] = [entry][NULL][sibling][sibling]
>
> This causes an issue if you have a reader iterating over the slots in the
> tree via radix_tree_for_each_slot() while only under
> rcu_read_lock()/rcu_read_unlock() protection. This is a common case in
> mm/filemap.c.
>
> The issue is that when __radix_tree_next_slot() => skip_siblings() tries to
> skip over the sibling entries in the slots, it currently does so with an
> exact match on the slot directly preceding our current slot. Normally this
> works:
> V preceding slot
> struct radix_tree_node.slots[] = [entry][sibling][sibling][sibling]
> ^ current slot
>
> This lets you find the first sibling, and you skip them all in order.
>
> But in the case where one of the siblings is NULL, that slot is skipped and
> then our sibling detection is interrupted:
>
> V preceding slot
> struct radix_tree_node.slots[] = [entry][NULL][sibling][sibling]
> ^ current slot
>
> This means that the sibling pointers aren't recognized since they point all
> the way back to 'entry', so we think that they are normal internal radix
> tree pointers. This causes us to think we need to walk down to a struct
> radix_tree_node starting at the address of 'entry'.
>
> In a real running kernel this will crash the thread with a GP fault when
> you try and dereference the slots in your broken node starting at 'entry'.
>
> We fix this race by fixing the way that skip_siblings() detects sibling
> nodes. Instead of testing against the preceding slot we instead look for
> siblings via is_sibling_entry() which compares against the position of the
> struct radix_tree_node.slots[] array. This ensures that sibling entries
> are properly identified, even if they are no longer contiguous with the
> 'entry' they point to.
>
> Signed-off-by: Ross Zwisler <ross.zwisler(a)linux.intel.com>
> Reported-by: CR, Sapthagirish <sapthagirish.cr(a)intel.com>
> Fixes: commit 148deab223b2 ("radix-tree: improve multiorder iterators")
> Cc: <stable(a)vger.kernel.org>
Looks good to me. You can add:
Reviewed-by: Jan Kara <jack(a)suse.cz>
Thank you for the review, Jan.
10:44 a.m.
On Thu, May 03, 2018 at 01:24:25PM -0600, Ross Zwisler wrote:
The following series gets the radix tree test suite compiling again
in
the current linux/master, adds a unit test which exposes a race in the
radix tree multi-order iteration code, and then fixes that race.
This race was initially hit on a v4.15 based kernel and results in a GP
fault. I've described the race in detail in patches 4 and 5.
The fix is simple and necessary, and I think it should be merged for
v4.17.
This tree has gotten positive build confirmation from the 0-day bot,
passes the updated radix tree test suite, xfstests, and the original
test that was hitting the race with the v4.15 based kernel.
Ross Zwisler (5):
radix tree test suite: fix mapshift build target
radix tree test suite: fix compilation issue
radix tree test suite: add item_delete_rcu()
radix tree test suite: multi-order iteration race
radix tree: fix multi-order iteration race
lib/radix-tree.c | 6 ++--
tools/include/linux/spinlock.h | 3 +-
tools/testing/radix-tree/Makefile | 6 ++--
tools/testing/radix-tree/multiorder.c | 63 +++++++++++++++++++++++++++++++++++
tools/testing/radix-tree/test.c | 19 +++++++++++
tools/testing/radix-tree/test.h | 3 ++
6 files changed, 91 insertions(+), 9 deletions(-)
--
2.14.3
Ping on this series. Does anyone have any feedback? Matthew?
I'd really like to get it into v4.17.
We can take it through the libnvdimm tree, if that's easiest.
3:48 p.m.
On Tue, 8 May 2018 11:44:24 -0600 Ross Zwisler <ross.zwisler(a)linux.intel.com>
wrote:
On Thu, May 03, 2018 at 01:24:25PM -0600, Ross Zwisler wrote:
> The following series gets the radix tree test suite compiling again in
> the current linux/master, adds a unit test which exposes a race in the
> radix tree multi-order iteration code, and then fixes that race.
>
> This race was initially hit on a v4.15 based kernel and results in a GP
> fault. I've described the race in detail in patches 4 and 5.
>
> The fix is simple and necessary, and I think it should be merged for
> v4.17.
>
> This tree has gotten positive build confirmation from the 0-day bot,
> passes the updated radix tree test suite, xfstests, and the original
> test that was hitting the race with the v4.15 based kernel.
>
> Ross Zwisler (5):
> radix tree test suite: fix mapshift build target
> radix tree test suite: fix compilation issue
> radix tree test suite: add item_delete_rcu()
> radix tree test suite: multi-order iteration race
> radix tree: fix multi-order iteration race
>
> lib/radix-tree.c | 6 ++--
> tools/include/linux/spinlock.h | 3 +-
> tools/testing/radix-tree/Makefile | 6 ++--
> tools/testing/radix-tree/multiorder.c | 63 +++++++++++++++++++++++++++++++++++
> tools/testing/radix-tree/test.c | 19 +++++++++++
> tools/testing/radix-tree/test.h | 3 ++
> 6 files changed, 91 insertions(+), 9 deletions(-)
>
> --
> 2.14.3
>
Ping on this series. Does anyone have any feedback? Matthew?
I'd really like to get it into v4.17.
We can take it through the libnvdimm tree, if that's easiest.
There's a copy in Dan's linux-next tree which is missing
- The Link: tag
- The Fixes: tag
- The Reported-by
- Jan's reviewed-by
- the cc:stable tag
so I think I'll just ignore all that and send this series off to Linus next
week.
3:54 p.m.
On Thu, May 10, 2018 at 3:48 PM, Andrew Morton
<akpm(a)linux-foundation.org> wrote:
On Tue, 8 May 2018 11:44:24 -0600 Ross Zwisler
<ross.zwisler(a)linux.intel.com> wrote:
> On Thu, May 03, 2018 at 01:24:25PM -0600, Ross Zwisler wrote:
> > The following series gets the radix tree test suite compiling again in
> > the current linux/master, adds a unit test which exposes a race in the
> > radix tree multi-order iteration code, and then fixes that race.
> >
> > This race was initially hit on a v4.15 based kernel and results in a GP
> > fault. I've described the race in detail in patches 4 and 5.
> >
> > The fix is simple and necessary, and I think it should be merged for
> > v4.17.
> >
> > This tree has gotten positive build confirmation from the 0-day bot,
> > passes the updated radix tree test suite, xfstests, and the original
> > test that was hitting the race with the v4.15 based kernel.
> >
> > Ross Zwisler (5):
> > radix tree test suite: fix mapshift build target
> > radix tree test suite: fix compilation issue
> > radix tree test suite: add item_delete_rcu()
> > radix tree test suite: multi-order iteration race
> > radix tree: fix multi-order iteration race
> >
> > lib/radix-tree.c | 6 ++--
> > tools/include/linux/spinlock.h | 3 +-
> > tools/testing/radix-tree/Makefile | 6 ++--
> > tools/testing/radix-tree/multiorder.c | 63 +++++++++++++++++++++++++++++++++++
> > tools/testing/radix-tree/test.c | 19 +++++++++++
> > tools/testing/radix-tree/test.h | 3 ++
> > 6 files changed, 91 insertions(+), 9 deletions(-)
> >
> > --
> > 2.14.3
> >
>
> Ping on this series. Does anyone have any feedback? Matthew?
>
> I'd really like to get it into v4.17.
>
> We can take it through the libnvdimm tree, if that's easiest.
There's a copy in Dan's linux-next tree which is missing
- The Link: tag
Yes, I normally don't add those.
- The Fixes: tag
- The Reported-by
Those were there.
- Jan's reviewed-by
Right, Jan's came after I pushed it for -next soaking, but I updated it.
- the cc:stable tag
That was there too, not sure where you were looking.
so I think I'll just ignore all that and send this series off to
Linus next
week.
It's all backed out now from my tree.
4:12 p.m.
On Thu, 10 May 2018 15:54:53 -0700 Dan Williams <dan.j.williams(a)intel.com> wrote:
> - The Fixes: tag
> - The Reported-by
Those were there.
> - Jan's reviewed-by
Right, Jan's came after I pushed it for -next soaking, but I updated it.
> - the cc:stable tag
That was there too, not sure where you were looking.
git show 4272afac65e0debacae7eb6af4591e31ba89dcad
4:19 p.m.
On Thu, May 10, 2018 at 4:12 PM, Andrew Morton
<akpm(a)linux-foundation.org> wrote:
On Thu, 10 May 2018 15:54:53 -0700 Dan Williams
<dan.j.williams(a)intel.com> wrote:
> > - The Fixes: tag
> > - The Reported-by
>
> Those were there.
>
> > - Jan's reviewed-by
>
> Right, Jan's came after I pushed it for -next soaking, but I updated it.
>
> > - the cc:stable tag
>
> That was there too, not sure where you were looking.
git show 4272afac65e0debacae7eb6af4591e31ba89dcad
That was the unit test suite patch, see the following actual fix:
7fa96cd88dbc: before Jan's reviewed-by
ce376ed6b706: after
677
days inactive
757
days old
22 comments
6 participants
participants (6)
-
Andrew Morton -
Dan Williams -
Dave Chinner -
Jan Kara -
Matthew Wilcox -
Ross Zwisler