[PATCH 0/5] fix radix tree multi-order iteration race

[PATCH 0/5] fix radix tree multi-order iteration race

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

-- 
2.14.3

[PATCH 1/5] radix tree test suite: fix mapshift build target

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

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

[PATCH 2/5] radix tree test suite: fix compilation issue

[Ross Zwisler]

Pulled from a patch from Matthew Wilcox entitled
"xarray: Add definition of struct xarray":

> From: Matthew Wilcox <mawilcox@microsoft.com>
> Signed-off-by: Matthew Wilcox <mawilcox@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@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

[PATCH 3/5] radix tree test suite: add item_delete_rcu()

[Ross Zwisler]

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

[PATCH 4/5] radix tree test suite: multi-order iteration race

[Ross Zwisler]

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

[PATCH 5/5] radix tree: fix multi-order iteration race

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

Signed-off-by: Ross Zwisler <ross.zwisler@linux.intel.com>
Reported-by: CR, Sapthagirish <sapthagirish.cr@intel.com>
Fixes: commit 148deab223b2 ("radix-tree: improve multiorder iterators")
Cc: <stable@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

Re: [PATCH 0/5] fix radix tree multi-order iteration race

[Ross Zwisler]

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.

Re: [PATCH 5/5] radix tree: fix multi-order iteration race

[Jan Kara]

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@linux.intel.com>
> Reported-by: CR, Sapthagirish <sapthagirish.cr@intel.com>
> Fixes: commit 148deab223b2 ("radix-tree: improve multiorder iterators")
> Cc: <stable@vger.kernel.org>

Looks good to me. You can add:

Reviewed-by: Jan Kara <jack@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@suse.com>
SUSE Labs, CR

Re: [PATCH 5/5] radix tree: fix multi-order iteration race

[Ross Zwisler]

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@linux.intel.com>
> > Reported-by: CR, Sapthagirish <sapthagirish.cr@intel.com>
> > Fixes: commit 148deab223b2 ("radix-tree: improve multiorder iterators")
> > Cc: <stable@vger.kernel.org>
> 
> Looks good to me. You can add:
> 
> Reviewed-by: Jan Kara <jack@suse.cz>

Thank you for the review, Jan.

Re: [PATCH 0/5] fix radix tree multi-order iteration race

[Andrew Morton]

On Tue, 8 May 2018 11:44:24 -0600 Ross Zwisler <ross.zwisler@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.

Re: [PATCH 0/5] fix radix tree multi-order iteration race

[Dan Williams]

On Thu, May 10, 2018 at 3:48 PM, Andrew Morton
<akpm@linux-foundation.org> wrote:
> On Tue, 8 May 2018 11:44:24 -0600 Ross Zwisler <ross.zwisler@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.

Re: [PATCH 0/5] fix radix tree multi-order iteration race

[Andrew Morton]

On Thu, 10 May 2018 15:54:53 -0700 Dan Williams <dan.j.williams@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

Re: [PATCH 0/5] fix radix tree multi-order iteration race

[Dan Williams]

On Thu, May 10, 2018 at 4:12 PM, Andrew Morton
<akpm@linux-foundation.org> wrote:
> On Thu, 10 May 2018 15:54:53 -0700 Dan Williams <dan.j.williams@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

Re: [PATCH 0/5] fix radix tree multi-order iteration race

[Ross Zwisler]

On Thu, May 10, 2018 at 03:48:44PM -0700, Andrew Morton wrote:
> so I think I'll just ignore all that and send this series off to Linus next
> week.

Great.  Thank you, Andrew.

Re: [PATCH 1/5] radix tree test suite: fix mapshift build target

[Matthew Wilcox]

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

Re: [PATCH 1/5] radix tree test suite: fix mapshift build target

[Ross Zwisler]

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.

Re: [PATCH 1/5] radix tree test suite: fix mapshift build target

[Matthew Wilcox]

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.

Re: [PATCH 1/5] radix tree test suite: fix mapshift build target

[Ross Zwisler]

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.

Re: [PATCH 1/5] radix tree test suite: fix mapshift build target

[Matthew Wilcox]

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.

Re: [PATCH 1/5] radix tree test suite: fix mapshift build target

[Matthew Wilcox]

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.

Re: [PATCH 1/5] radix tree test suite: fix mapshift build target

[Ross Zwisler]

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

Re: [PATCH 1/5] radix tree test suite: fix mapshift build target

[Dave Chinner]

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@fromorbit.com

Re: [PATCH 1/5] radix tree test suite: fix mapshift build target

[Ross Zwisler]

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.