fix radix tree multi-order iteration race

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 <[email protected]>

---
 tools/testing/radix-tree/Makefile | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)

tools/testing/radix-tree/Makefile +2 -4

index fa7ee369b3c9..db66f8a0d4be 100644
@@ -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;			\

Signature · 1 line

2.14.3

Quoted 17 lines · Ross Zwisler

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

Quoted 2 lines

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.

Quoted 8 lines · Matthew Wilcox

Quoted 7 lines · Ross Zwisler

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

Quoted 8 lines

Quoted 2 lines

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:

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.

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

Quoted 4 lines

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.

Quoted 1 line · Matthew Wilcox

On Mon, Jul 16, 2018 at 10:07:10AM -0600, Ross Zwisler wrote:

<>

Quoted 13 lines

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

Quoted 1 line

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.

Quoted 22 lines · Ross Zwisler

Quoted 1 line · Matthew Wilcox

On Mon, Jul 16, 2018 at 10:07:10AM -0600, Ross Zwisler wrote:

<>

Quoted 9 lines

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

Quoted 5 lines

$ 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

Quoted 1 line

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.

Quoted 23 lines · Matthew Wilcox

Quoted 22 lines · Ross Zwisler

Quoted 1 line · Matthew Wilcox

On Mon, Jul 16, 2018 at 10:07:10AM -0600, Ross Zwisler wrote:

<>

Quoted 9 lines

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

Quoted 5 lines

$ 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

Quoted 5 lines

Quoted 1 line

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

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.

Quoted 16 lines · Ross Zwisler

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

Quoted 8 lines

  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.

From: Matthew Wilcox <[email protected]>

Signed-off-by Matthew Wilcox <[email protected]>

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 <[email protected]>

Reported-by CR, Sapthagirish <[email protected]>

Fixes commit 148deab223b2 ("radix-tree: improve multiorder iterators")

Cc <[email protected]>

---
 lib/radix-tree.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)

lib/radix-tree.c +2 -4

index da9e10c827df..43e0cbedc3a0 100644
@@ -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);
 

Signature · 1 line

2.14.3

Quoted 64 lines · Ross Zwisler

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.

Quoted 4 lines

Signed-off-by Ross Zwisler <[email protected]>

Reported-by CR, Sapthagirish <[email protected]>

Fixes commit 148deab223b2 ("radix-tree: improve multiorder iterators")

Cc <[email protected]>

Looks good to me. You can add:

Reviewed-by Jan Kara <[email protected]>

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

Signature · 1 line

2.14.3

Quoted 21 lines · Ross Zwisler

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

Quoted 11 lines

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

Signature · 1 line

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.

Quoted 36 lines · On Tue, 8 May 2018 11:44:24 -0600 Ross Zwisler <[email protected]>…

Quoted 29 lines · Ross Zwisler

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

Quoted 3 lines

--
2.14.3

Ping on this series. Does anyone have any feedback? Matthew?

Quoted 3 lines

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.

Quoted 2 lines

- The Fixes: tag
- The Reported-by

Those were there.

Quoted 1 line

- Jan's reviewed-by

Right, Jan's came after I pushed it for -next soaking, but I updated it.

Quoted 1 line

- the cc:stable tag

That was there too, not sure where you were looking.

Quoted 7 lines · On Thu, 10 May 2018 15:54:53 -0700 Dan Williams <[email protected]>…

Quoted 2 lines

- The Fixes: tag
- The Reported-by

Those were there.

Quoted 1 line

- Jan's reviewed-by

Quoted 5 lines

Right, Jan's came after I pushed it for -next soaking, but I updated it.

Quoted 1 line

- the cc:stable tag

That was there too, not sure where you were looking.

git show 4272afac65e0debacae7eb6af4591e31ba89dcad

so I think I'll just ignore all that and send this series off to Linus next week.