Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1372859 > unrolled thread

[PATCH 00/30] Radix tree multiorder fixes

Back to article view | Back to linux.kernel

Contents

  [PATCH 00/30] Radix tree multiorder fixes Matthew Wilcox <willy@linux.intel.com> - 2016-04-06 23:30 +0200
    [PATCH 24/30] radix-tree: Rewrite radix_tree_tag_get Matthew Wilcox <willy@linux.intel.com> - 2016-04-06 23:30 +0200
    [PATCH 21/30] radix tree test suite: Add multiorder shrinking test Matthew Wilcox <willy@linux.intel.com> - 2016-04-06 23:30 +0200
    [PATCH 30/30] radix-tree: Add copyright statements Matthew Wilcox <willy@linux.intel.com> - 2016-04-06 23:30 +0200
    [PATCH 13/30] radix-tree: Introduce radix_tree_load_root() Matthew Wilcox <willy@linux.intel.com> - 2016-04-06 23:30 +0200
    [PATCH 02/30] radix tree test suite: Fix build Matthew Wilcox <willy@linux.intel.com> - 2016-04-06 23:40 +0200
    [PATCH 05/30] radix tree test suite: keep regression test runs short Matthew Wilcox <willy@linux.intel.com> - 2016-04-06 23:40 +0200
    [PATCH 06/30] radix tree test suite: rebuild when headers change Matthew Wilcox <willy@linux.intel.com> - 2016-04-06 23:40 +0200
    [PATCH 10/30] radix-tree: Fix sibling entry insertion Matthew Wilcox <willy@linux.intel.com> - 2016-04-06 23:40 +0200
    [PATCH 11/30] radix-tree: Fix deleting a multi-order entry through an alias Matthew Wilcox <willy@linux.intel.com> - 2016-04-06 23:40 +0200
    [PATCH 01/30] radix-tree: Introduce radix_tree_empty Matthew Wilcox <willy@linux.intel.com> - 2016-04-06 23:40 +0200

#1372859 — [PATCH 00/30] Radix tree multiorder fixes

I must apologise for commit f96d18ff84 which left the impression that
the support for multiorder radix tree entries was functional.  As soon as
Ross tried to use it, it became apparent that my testing was completely
inadequate, and it didn't even work a little bit for orders that were
not a multiple of shift.

This series of patches is the result of about 5 weeks of redesign,
reimplementation, testing, arguing and hair-pulling.  The great news is
that the test-suite is now far better than it was.  That's reflected in
the diffstat for the test-suite alone:
 12 files changed, 427 insertions(+), 28 deletions(-)

The highlight for users of the tree is that the restriction on the order
being >= RADIX_TREE_MAP_SHIFT is now gone; the radix tree now supports
any order between 0 and 64.

For those who are interested in how the tree works, patch 9 is probably
the most interesting one as it introduces the new machinery for handling
sibling entries.

I've tried to be fair in attributing authorship to the person who
contributed the majority of the code in each patch; Ross has been an
invaluable partner in the development of this support and it's fair to
say that each of us has code in every commit.

I should also express my appreciation of the 0day testing.  It prompted
me that I was bloating the tinyconfig in an unacceptable way, and it
bisected to a commit which contained a rahter nasty memory-corruption bug.

Matthew Wilcox (20):
  radix-tree: Introduce radix_tree_empty
  radix tree test suite: Fix build
  radix tree test suite: Add tests for radix_tree_locate_item()
  Introduce CONFIG_RADIX_TREE_MULTIORDER
  radix-tree: Add missing sibling entry functionality
  radix-tree: Fix sibling entry insertion
  radix-tree: Fix deleting a multi-order entry through an alias
  radix-tree: Remove restriction on multi-order entries
  radix-tree: Introduce radix_tree_load_root()
  radix-tree: Fix extending the tree for multi-order entries at offset 0
  radix-tree: Fix several shrinking bugs with multiorder entries
  radix tree test suite: Start adding multiorder tests
  radix-tree: Rewrite __radix_tree_lookup
  radix-tree: Fix multiorder BUG_ON in radix_tree_insert
  radix-tree: add support for multi-order iterating
  radix tree test suite: Add multiorder shrinking test
  radix-tree: Fix radix_tree_create for sibling entries
  radix-tree: Rewrite radix_tree_locate_item
  radix-tree: Fix two bugs in radix_tree_range_tag_if_tagged()
  radix-tree: Add copyright statements

Ross Zwisler (10):
  radix tree test suite: Allow testing other fan-out values
  radix tree test suite: keep regression test runs short
  radix tree test suite: rebuild when headers change
  radix-tree: remove unused looping macros
  radix tree test suite: multi-order iteration test
  radix-tree: Rewrite radix_tree_tag_set
  radix-tree: Rewrite radix_tree_tag_clear
  radix-tree: Rewrite radix_tree_tag_get
  radix-tree test suite: add multi-order tag test
  radix-tree: Fix radix_tree_dump() for multi-order entries

 include/linux/radix-tree.h                    | 103 +++--
 kernel/irq/irqdomain.c                        |   7 +-
 lib/Kconfig                                   |   3 +
 lib/radix-tree.c                              | 545 +++++++++++++++-----------
 mm/Kconfig                                    |   1 +
 tools/testing/radix-tree/Makefile             |   4 +-
 tools/testing/radix-tree/generated/autoconf.h |   3 +
 tools/testing/radix-tree/linux/init.h         |   0
 tools/testing/radix-tree/linux/kernel.h       |  15 +-
 tools/testing/radix-tree/linux/slab.h         |   1 -
 tools/testing/radix-tree/linux/types.h        |   7 +-
 tools/testing/radix-tree/main.c               |  71 +++-
 tools/testing/radix-tree/multiorder.c         | 317 +++++++++++++++
 tools/testing/radix-tree/regression2.c        |   7 -
 tools/testing/radix-tree/tag_check.c          |  10 +
 tools/testing/radix-tree/test.c               |  13 +-
 tools/testing/radix-tree/test.h               |   7 +-
 17 files changed, 807 insertions(+), 307 deletions(-)
 create mode 100644 tools/testing/radix-tree/generated/autoconf.h
 create mode 100644 tools/testing/radix-tree/linux/init.h
 create mode 100644 tools/testing/radix-tree/multiorder.c

-- 
2.8.0.rc3

[toc] | [next] | [standalone]

#1372860 — [PATCH 24/30] radix-tree: Rewrite radix_tree_tag_get

From: Ross Zwisler <ross.zwisler@linux.intel.com>

Use the new multi-order support functions to rewrite radix_tree_tag_get()

Signed-off-by: Ross Zwisler <ross.zwisler@linux.intel.com>
Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
---
 lib/radix-tree.c | 44 ++++++++++++++++++--------------------------
 1 file changed, 18 insertions(+), 26 deletions(-)

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index aca7b2814d26..d894654b5ecc 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -838,45 +838,37 @@ EXPORT_SYMBOL(radix_tree_tag_clear);
 int radix_tree_tag_get(struct radix_tree_root *root,
 			unsigned long index, unsigned int tag)
 {
-	unsigned int height, shift;
-	struct radix_tree_node *node;
+	struct radix_tree_node *node, *parent;
+	unsigned long maxindex;
+	unsigned int shift;
 
-	/* check the root's tag bit */
 	if (!root_tag_get(root, tag))
 		return 0;
 
-	node = rcu_dereference_raw(root->rnode);
+	shift = radix_tree_load_root(root, &node, &maxindex);
+	if (index > maxindex)
+		return 0;
 	if (node == NULL)
 		return 0;
 
-	if (!radix_tree_is_indirect_ptr(node))
-		return (index == 0);
-	node = indirect_to_ptr(node);
-
-	height = node->path & RADIX_TREE_HEIGHT_MASK;
-	if (index > radix_tree_maxindex(height))
-		return 0;
+	while (radix_tree_is_indirect_ptr(node)) {
+		int offset;
 
-	shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
+		shift -= RADIX_TREE_MAP_SHIFT;
+		offset = (index >> shift) & RADIX_TREE_MAP_MASK;
 
-	for ( ; ; ) {
-		int offset;
+		parent = indirect_to_ptr(node);
+		offset = radix_tree_descend(parent, &node, offset);
 
-		if (node == NULL)
+		if (!node)
 			return 0;
-		node = indirect_to_ptr(node);
-
-		offset = (index >> shift) & RADIX_TREE_MAP_MASK;
-		if (!tag_get(node, tag, offset))
+		if (!tag_get(parent, tag, offset))
 			return 0;
-		if (height == 1)
-			return 1;
-		node = rcu_dereference_raw(node->slots[offset]);
-		if (!radix_tree_is_indirect_ptr(node))
-			return 1;
-		shift -= RADIX_TREE_MAP_SHIFT;
-		height--;
+		if (node == RADIX_TREE_RETRY)
+			break;
 	}
+
+	return 1;
 }
 EXPORT_SYMBOL(radix_tree_tag_get);
 
-- 
2.8.0.rc3

[toc] | [prev] | [next] | [standalone]

#1372861 — [PATCH 21/30] radix tree test suite: Add multiorder shrinking test

Ensure that the tree goes back down to the same height when an item is
inserted & removed from the tree at a higher index.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross Zwisler <ross.zwisler@linux.intel.com>
---
 tools/testing/radix-tree/multiorder.c | 38 +++++++++++++++++++++++++++++++++++
 1 file changed, 38 insertions(+)

diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c
index 583c5127fbcf..10b9708a71f9 100644
--- a/tools/testing/radix-tree/multiorder.c
+++ b/tools/testing/radix-tree/multiorder.c
@@ -46,6 +46,41 @@ static void multiorder_check(unsigned long index, int order)
 		item_check_absent(&tree, i);
 }
 
+static void multiorder_shrink(unsigned long index, int order)
+{
+	unsigned long i;
+	unsigned long max = 1 << order;
+	RADIX_TREE(tree, GFP_KERNEL);
+	struct radix_tree_node *node;
+
+	printf("Multiorder shrink index %ld, order %d\n", index, order);
+
+	assert(item_insert_order(&tree, 0, order) == 0);
+
+	node = tree.rnode;
+
+	assert(item_insert(&tree, index) == 0);
+	assert(node != tree.rnode);
+
+	assert(item_delete(&tree, index) != 0);
+	assert(node == tree.rnode);
+
+	for (i = 0; i < max; i++) {
+		struct item *item = item_lookup(&tree, i);
+		assert(item != 0);
+		assert(item->index == 0);
+	}
+	for (i = max; i < 2*max; i++)
+		item_check_absent(&tree, i);
+
+	if (!item_delete(&tree, 0)) {
+		printf("failed to delete index %ld (order %d)\n", index, order);		abort();
+	}
+
+	for (i = 0; i < 2*max; i++)
+		item_check_absent(&tree, i);
+}
+
 static void multiorder_insert_bug(void)
 {
 	RADIX_TREE(tree, GFP_KERNEL);
@@ -157,6 +192,9 @@ void multiorder_checks(void)
 		multiorder_check((1UL << i) + 1, i);
 	}
 
+	for (i = 0; i < 15; i++)
+		multiorder_shrink((1UL << (i + RADIX_TREE_MAP_SHIFT)), i);
+
 	multiorder_iteration();
 	multiorder_tagged_iteration();
 	multiorder_insert_bug();
-- 
2.8.0.rc3

[toc] | [prev] | [next] | [standalone]

#1372862 — [PATCH 30/30] radix-tree: Add copyright statements

The multiorder support is a sufficiently large feature to be worth adding
copyrigt lines for.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross Zwisler <ross.zwisler@linux.intel.com>
---
 lib/radix-tree.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 0402c4f1a344..edaf4771feb0 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -4,6 +4,8 @@
  * Copyright (C) 2005 SGI, Christoph Lameter
  * Copyright (C) 2006 Nick Piggin
  * Copyright (C) 2012 Konstantin Khlebnikov
+ * Copyright (C) 2016 Intel, Matthew Wilcox
+ * Copyright (C) 2016 Intel, Ross Zwisler
  *
  * This program is free software; you can redistribute it and/or
  * modify it under the terms of the GNU General Public License as
-- 
2.8.0.rc3

[toc] | [prev] | [next] | [standalone]

#1372863 — [PATCH 13/30] radix-tree: Introduce radix_tree_load_root()

All the tree walking functions start with some variant of this code;
centralise it in one place so we're not chasing subtly different bugs
everywhere.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross Zwisler <ross.zwisler@linux.intel.com>
---
 lib/radix-tree.c | 23 +++++++++++++++++++++++
 1 file changed, 23 insertions(+)

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index f2a314cf42cc..b3a7e6cd5773 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -405,6 +405,29 @@ static inline unsigned long radix_tree_maxindex(unsigned int height)
 	return height_to_maxindex[height];
 }
 
+static inline unsigned long node_maxindex(struct radix_tree_node *node)
+{
+	return radix_tree_maxindex(node->path & RADIX_TREE_HEIGHT_MASK);
+}
+
+static unsigned radix_tree_load_root(struct radix_tree_root *root,
+		struct radix_tree_node **nodep, unsigned long *maxindex)
+{
+	struct radix_tree_node *node = rcu_dereference_raw(root->rnode);
+
+	*nodep = node;
+
+	if (likely(radix_tree_is_indirect_ptr(node))) {
+		node = indirect_to_ptr(node);
+		*maxindex = node_maxindex(node);
+		return (node->path & RADIX_TREE_HEIGHT_MASK) *
+			RADIX_TREE_MAP_SHIFT;
+	}
+
+	*maxindex = 0;
+	return 0;
+}
+
 /*
  *	Extend a radix tree so it can store key @index.
  */
-- 
2.8.0.rc3

[toc] | [prev] | [next] | [standalone]

#1372864 — [PATCH 02/30] radix tree test suite: Fix build

Add an empty linux/init.h, and definitions for a few parts of the kernel
API either in use now, or to be used in the near future.  Start using
the common definitions in tools/include/linux, although more work needs
to be done here.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross Zwisler <ross.zwisler@linux.intel.com>
---
 tools/testing/radix-tree/linux/init.h   |  0
 tools/testing/radix-tree/linux/kernel.h | 12 ++++++++++--
 tools/testing/radix-tree/linux/slab.h   |  1 -
 tools/testing/radix-tree/linux/types.h  |  7 ++-----
 4 files changed, 12 insertions(+), 8 deletions(-)
 create mode 100644 tools/testing/radix-tree/linux/init.h

diff --git a/tools/testing/radix-tree/linux/init.h b/tools/testing/radix-tree/linux/init.h
new file mode 100644
index 000000000000..e69de29bb2d1
diff --git a/tools/testing/radix-tree/linux/kernel.h b/tools/testing/radix-tree/linux/kernel.h
index ae013b0160ac..6d0cdf618084 100644
--- a/tools/testing/radix-tree/linux/kernel.h
+++ b/tools/testing/radix-tree/linux/kernel.h
@@ -7,19 +7,25 @@
 #include <stddef.h>
 #include <limits.h>
 
+#include "../../include/linux/compiler.h"
+
 #ifndef NULL
 #define NULL	0
 #endif
 
 #define BUG_ON(expr)	assert(!(expr))
+#define WARN_ON(expr)	assert(!(expr))
 #define __init
 #define __must_check
 #define panic(expr)
 #define printk printf
 #define __force
-#define likely(c) (c)
-#define unlikely(c) (c)
 #define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d))
+#define pr_debug printk
+
+#define smp_rmb()	barrier()
+#define smp_wmb()	barrier()
+#define cpu_relax()	barrier()
 
 #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]))
 
@@ -28,6 +34,8 @@
 	(type *)( (char *)__mptr - offsetof(type, member) );})
 #define min(a, b) ((a) < (b) ? (a) : (b))
 
+#define cond_resched()	sched_yield()
+
 static inline int in_interrupt(void)
 {
 	return 0;
diff --git a/tools/testing/radix-tree/linux/slab.h b/tools/testing/radix-tree/linux/slab.h
index 57282506c21d..6d5a34770fd4 100644
--- a/tools/testing/radix-tree/linux/slab.h
+++ b/tools/testing/radix-tree/linux/slab.h
@@ -3,7 +3,6 @@
 
 #include <linux/types.h>
 
-#define GFP_KERNEL 1
 #define SLAB_HWCACHE_ALIGN 1
 #define SLAB_PANIC 2
 #define SLAB_RECLAIM_ACCOUNT    0x00020000UL            /* Objects are reclaimable */
diff --git a/tools/testing/radix-tree/linux/types.h b/tools/testing/radix-tree/linux/types.h
index 72a9d85f6c76..faa0b6ff9ca8 100644
--- a/tools/testing/radix-tree/linux/types.h
+++ b/tools/testing/radix-tree/linux/types.h
@@ -1,15 +1,13 @@
 #ifndef _TYPES_H
 #define _TYPES_H
 
+#include "../../include/linux/types.h"
+
 #define __rcu
 #define __read_mostly
 
 #define BITS_PER_LONG (sizeof(long) * 8)
 
-struct list_head {
-	struct list_head *next, *prev;
-};
-
 static inline void INIT_LIST_HEAD(struct list_head *list)
 {
 	list->next = list;
@@ -22,7 +20,6 @@ typedef struct {
 
 #define uninitialized_var(x) x = x
 
-typedef unsigned gfp_t;
 #include <linux/gfp.h>
 
 #endif
-- 
2.8.0.rc3

[toc] | [prev] | [next] | [standalone]

#1372865 — [PATCH 05/30] radix tree test suite: keep regression test runs short

From: Ross Zwisler <ross.zwisler@linux.intel.com>

Currently the full suite of regression tests take upwards of 30 minutes to
run on my development machine.  The vast majority of this time is taken by
the big_gang_check() and copy_tag_check() tests, which each run their tests
through thousands of iterations...does this have value?

Without big_gang_check() and copy_tag_check(), the test suite runs in
around 15 seconds on my box.

Honestly the first time I ever ran through the entire test suite was to
gather the timings for this email - it simply takes too long to be useful
on a normal basis.

Instead, hide the excessive iterations through big_gang_check() and
copy_tag_check() tests behind an '-l' flag (for "long run") in case they
are still useful, but allow the regression test suite to complete in a
reasonable amount of time.  We still run each of these tests a few times (3
at present) to try and keep the test coverage.

Signed-off-by: Ross Zwisler <ross.zwisler@linux.intel.com>
Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
---
 tools/testing/radix-tree/main.c | 22 +++++++++++++++-------
 1 file changed, 15 insertions(+), 7 deletions(-)

diff --git a/tools/testing/radix-tree/main.c b/tools/testing/radix-tree/main.c
index 71c5272443b1..122c8b9be17e 100644
--- a/tools/testing/radix-tree/main.c
+++ b/tools/testing/radix-tree/main.c
@@ -61,11 +61,11 @@ void __big_gang_check(void)
 	} while (!wrapped);
 }
 
-void big_gang_check(void)
+void big_gang_check(bool long_run)
 {
 	int i;
 
-	for (i = 0; i < 1000; i++) {
+	for (i = 0; i < (long_run ? 1000 : 3); i++) {
 		__big_gang_check();
 		srand(time(0));
 		printf("%d ", i);
@@ -270,7 +270,7 @@ static void locate_check(void)
 	item_kill_tree(&tree);
 }
 
-static void single_thread_tests(void)
+static void single_thread_tests(bool long_run)
 {
 	int i;
 
@@ -285,9 +285,9 @@ static void single_thread_tests(void)
 	printf("after add_and_check: %d allocated\n", nr_allocated);
 	dynamic_height_check();
 	printf("after dynamic_height_check: %d allocated\n", nr_allocated);
-	big_gang_check();
+	big_gang_check(long_run);
 	printf("after big_gang_check: %d allocated\n", nr_allocated);
-	for (i = 0; i < 2000; i++) {
+	for (i = 0; i < (long_run ? 2000 : 3); i++) {
 		copy_tag_check();
 		printf("%d ", i);
 		fflush(stdout);
@@ -295,15 +295,23 @@ static void single_thread_tests(void)
 	printf("after copy_tag_check: %d allocated\n", nr_allocated);
 }
 
-int main(void)
+int main(int argc, char **argv)
 {
+	bool long_run = false;
+	int opt;
+
+	while ((opt = getopt(argc, argv, "l")) != -1) {
+		if (opt == 'l')
+			long_run = true;
+	}
+
 	rcu_register_thread();
 	radix_tree_init();
 
 	regression1_test();
 	regression2_test();
 	regression3_test();
-	single_thread_tests();
+	single_thread_tests(long_run);
 
 	sleep(1);
 	printf("after sleep(1): %d allocated\n", nr_allocated);
-- 
2.8.0.rc3

[toc] | [prev] | [next] | [standalone]

#1372866 — [PATCH 06/30] radix tree test suite: rebuild when headers change

From: Ross Zwisler <ross.zwisler@linux.intel.com>

When we make changes to radix-tree.h in the regular kernel source
(include/linux/radix-tree.h), we really want our test code to be rebuilt.

We also include a few other headers from tools/include and probably want
to rebuild if these have been changed.

Update the makefile so that all of our objects will be rebuilt when any
of the headers we depend on are changed.

Signed-off-by: Ross Zwisler <ross.zwisler@linux.intel.com>
Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
---
 tools/testing/radix-tree/Makefile | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile
index 604212db9d4b..43febba864bd 100644
--- a/tools/testing/radix-tree/Makefile
+++ b/tools/testing/radix-tree/Makefile
@@ -13,7 +13,7 @@ main:	$(OFILES)
 clean:
 	$(RM) -f $(TARGETS) *.o radix-tree.c
 
-$(OFILES): *.h */*.h
+$(OFILES): *.h */*.h ../../../include/linux/radix-tree.h ../../include/linux/*.h
 
 radix-tree.c: ../../../lib/radix-tree.c
 	sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline //' < $< > $@
-- 
2.8.0.rc3

[toc] | [prev] | [next] | [standalone]

#1372867 — [PATCH 10/30] radix-tree: Fix sibling entry insertion

The subtraction was the wrong way round, leading to undefined behaviour
(shift by an amount larger than the size of the type).

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross Zwisler <ross.zwisler@linux.intel.com>
---
 lib/radix-tree.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 40343f28a705..42a0492b2ba2 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -526,8 +526,8 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
 
 #ifdef CONFIG_RADIX_TREE_MULTIORDER
 	/* Insert pointers to the canonical entry */
-	if ((shift - order) > 0) {
-		int i, n = 1 << (shift - order);
+	if (order > shift) {
+		int i, n = 1 << (order - shift);
 		offset = offset & ~(n - 1);
 		slot = ptr_to_indirect(&node->slots[offset]);
 		for (i = 0; i < n; i++) {
-- 
2.8.0.rc3

[toc] | [prev] | [next] | [standalone]

#1372869 — [PATCH 11/30] radix-tree: Fix deleting a multi-order entry through an alias

If we deleted an entry through an index which looked up a sibling
pointer, we'd end up zeroing out the wrong slots in the node.
Use get_sibling_offset() to find the right slot.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross Zwisler <ross.zwisler@linux.intel.com>
---
 lib/radix-tree.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 42a0492b2ba2..554986599c63 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -1557,7 +1557,7 @@ void *radix_tree_delete_item(struct radix_tree_root *root,
 		return entry;
 	}
 
-	offset = index & RADIX_TREE_MAP_MASK;
+	offset = get_sibling_offset(node, slot);
 
 	/*
 	 * Clear all tags associated with the item to be deleted.
-- 
2.8.0.rc3

[toc] | [prev] | [next] | [standalone]

#1372873 — [PATCH 01/30] radix-tree: Introduce radix_tree_empty

The irqdomain code was checking for 0 or 1 entries, not 0 entries like
the comment said they were.  Introduce a new helper that will actually
check for an empty tree.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross Zwisler <ross.zwisler@linux.intel.com>
---
 include/linux/radix-tree.h | 5 +++++
 kernel/irq/irqdomain.c     | 7 +------
 2 files changed, 6 insertions(+), 6 deletions(-)

diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index 51a97ac8bfbf..83f708e5db59 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -136,6 +136,11 @@ do {									\
 	(root)->rnode = NULL;						\
 } while (0)
 
+static inline bool radix_tree_empty(struct radix_tree_root *root)
+{
+	return root->rnode == NULL;
+}
+
 /**
  * Radix-tree synchronization
  *
diff --git a/kernel/irq/irqdomain.c b/kernel/irq/irqdomain.c
index 3a519a01118b..ba3f60d8df2f 100644
--- a/kernel/irq/irqdomain.c
+++ b/kernel/irq/irqdomain.c
@@ -139,12 +139,7 @@ void irq_domain_remove(struct irq_domain *domain)
 {
 	mutex_lock(&irq_domain_mutex);
 
-	/*
-	 * radix_tree_delete() takes care of destroying the root
-	 * node when all entries are removed. Shout if there are
-	 * any mappings left.
-	 */
-	WARN_ON(domain->revmap_tree.height);
+	WARN_ON(!radix_tree_empty(&domain->revmap_tree));
 
 	list_del(&domain->link);
 
-- 
2.8.0.rc3

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web