Re: [PATCH 2/2] radix-tree: Fix optimisation problem

From: Linus Torvalds
Date: Sat Sep 24 2016 - 16:47:47 EST

On Sat, Sep 24, 2016 at 1:21 PM, Linus Torvalds
<torvalds@xxxxxxxxxxxxxxxxxxxx> wrote:
>
> That said, if this code isn't even used, as Konstantin says (THP
> selects it - doesn't THP use it?), then the fix really should be to
> just remove the odd code instead of adding to it.
>
> Looking around for uses that set "order" to anything but zero, I
> really don't see it. So maybe we should just do *that* trivial thing
> instead, and remove CONFIG_RADIX_TREE_MULTIORDER, since it's appears
> to be buggy and always has been.

IOW, a patch something like this?

NOTE! This is entirely untested. Things still seem to compile with it,
at least with some configurations. That's all I can say.

I do like this part:

11 files changed, 29 insertions(+), 518 deletions(-)

although admittedly 2/3rds of the deletions were for the multiorder
tests. But even if you ignore the test side, it's just fairly clean
removal of code that is apparently not used, and that was buggy.

Linus
include/linux/radix-tree.h | 48 +---
lib/Kconfig | 3 -
lib/radix-tree.c | 100 +-------
mm/Kconfig | 1 -
mm/filemap.c | 2 +-
tools/testing/radix-tree/Makefile | 2 +-
tools/testing/radix-tree/generated/autoconf.h | 1 -
tools/testing/radix-tree/main.c | 34 +--
tools/testing/radix-tree/multiorder.c | 337 --------------------------
tools/testing/radix-tree/test.c | 14 +-
tools/testing/radix-tree/test.h | 5 -
11 files changed, 29 insertions(+), 518 deletions(-)

diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index 4c45105dece3..ac546baa604c 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -263,15 +263,9 @@ static inline void radix_tree_replace_slot(void **pslot, void *item)
}

int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
- unsigned order, struct radix_tree_node **nodep,
+ struct radix_tree_node **nodep,
void ***slotp);
-int __radix_tree_insert(struct radix_tree_root *, unsigned long index,
- unsigned order, void *);
-static inline int radix_tree_insert(struct radix_tree_root *root,
- unsigned long index, void *entry)
-{
- return __radix_tree_insert(root, index, 0, entry);
-}
+int radix_tree_insert(struct radix_tree_root *, unsigned long index, void *);
void *__radix_tree_lookup(struct radix_tree_root *root, unsigned long index,
struct radix_tree_node **nodep, void ***slotp);
void *radix_tree_lookup(struct radix_tree_root *, unsigned long);
@@ -338,20 +332,8 @@ struct radix_tree_iter {
unsigned long index;
unsigned long next_index;
unsigned long tags;
-#ifdef CONFIG_RADIX_TREE_MULTIORDER
- unsigned int shift;
-#endif
};

-static inline unsigned int iter_shift(struct radix_tree_iter *iter)
-{
-#ifdef CONFIG_RADIX_TREE_MULTIORDER
- return iter->shift;
-#else
- return 0;
-#endif
-}
-
#define RADIX_TREE_ITER_TAG_MASK 0x00FF /* tag index in lower byte */
#define RADIX_TREE_ITER_TAGGED 0x0100 /* lookup tagged slots */
#define RADIX_TREE_ITER_CONTIG 0x0200 /* stop at first hole */
@@ -415,7 +397,7 @@ void **radix_tree_iter_retry(struct radix_tree_iter *iter)
static inline unsigned long
__radix_tree_iter_add(struct radix_tree_iter *iter, unsigned long slots)
{
- return iter->index + (slots << iter_shift(iter));
+ return iter->index + slots;
}

/**
@@ -443,7 +425,7 @@ void **radix_tree_iter_next(struct radix_tree_iter *iter)
static __always_inline long
radix_tree_chunk_size(struct radix_tree_iter *iter)
{
- return (iter->next_index - iter->index) >> iter_shift(iter);
+ return iter->next_index - iter->index;
}

static inline struct radix_tree_node *entry_to_node(void *ptr)
@@ -466,22 +448,9 @@ static __always_inline void **
radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
{
if (flags & RADIX_TREE_ITER_TAGGED) {
- void *canon = slot;
-
iter->tags >>= 1;
if (unlikely(!iter->tags))
return NULL;
- while (IS_ENABLED(CONFIG_RADIX_TREE_MULTIORDER) &&
- radix_tree_is_internal_node(slot[1])) {
- if (entry_to_node(slot[1]) == canon) {
- iter->tags >>= 1;
- iter->index = __radix_tree_iter_add(iter, 1);
- slot++;
- continue;
- }
- iter->next_index = __radix_tree_iter_add(iter, 1);
- return NULL;
- }
if (likely(iter->tags & 1ul)) {
iter->index = __radix_tree_iter_add(iter, 1);
return slot + 1;
@@ -495,20 +464,11 @@ radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
}
} else {
long count = radix_tree_chunk_size(iter);
- void *canon = slot;

while (--count > 0) {
slot++;
iter->index = __radix_tree_iter_add(iter, 1);

- if (IS_ENABLED(CONFIG_RADIX_TREE_MULTIORDER) &&
- radix_tree_is_internal_node(*slot)) {
- if (entry_to_node(*slot) == canon)
- continue;
- iter->next_index = iter->index;
- break;
- }
-
if (likely(*slot))
return slot;
if (flags & RADIX_TREE_ITER_CONTIG) {
diff --git a/lib/Kconfig b/lib/Kconfig
index d79909dc01ec..61d55bd0ed89 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -362,9 +362,6 @@ config INTERVAL_TREE

for more information.

-config RADIX_TREE_MULTIORDER
- bool
-
config ASSOCIATIVE_ARRAY
bool
help
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 1b7bf7314141..b8b12172bb60 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -76,21 +76,6 @@ static inline void *node_to_entry(void *ptr)

#define RADIX_TREE_RETRY node_to_entry(NULL)

-#ifdef CONFIG_RADIX_TREE_MULTIORDER
-/* Sibling slots point directly to another slot in the same node */
-static inline bool is_sibling_entry(struct radix_tree_node *parent, void *node)
-{
- void **ptr = node;
- return (parent->slots <= ptr) &&
- (ptr < parent->slots + RADIX_TREE_MAP_SIZE);
-}
-#else
-static inline bool is_sibling_entry(struct radix_tree_node *parent, void *node)
-{
- return false;
-}
-#endif
-
static inline unsigned long get_slot_offset(struct radix_tree_node *parent,
void **slot)
{
@@ -103,16 +88,6 @@ static unsigned int radix_tree_descend(struct radix_tree_node *parent,
unsigned int offset = (index >> parent->shift) & RADIX_TREE_MAP_MASK;
void **entry = rcu_dereference_raw(parent->slots[offset]);

-#ifdef CONFIG_RADIX_TREE_MULTIORDER
- if (radix_tree_is_internal_node(entry)) {
- unsigned long siboff = get_slot_offset(parent, entry);
- if (siboff < RADIX_TREE_MAP_SIZE) {
- offset = siboff;
- entry = rcu_dereference_raw(parent->slots[offset]);
- }
- }
-#endif
-
*nodep = (void *)entry;
return offset;
}
@@ -231,12 +206,7 @@ static void dump_node(struct radix_tree_node *node, unsigned long index)
void *entry = node->slots[i];
if (!entry)
continue;
- if (is_sibling_entry(node, entry)) {
- pr_debug("radix sblng %p offset %ld val %p indices %ld-%ld\n",
- entry, i,
- *(void **)entry_to_node(entry),
- first, last);
- } else if (!radix_tree_is_internal_node(entry)) {
+ if (!radix_tree_is_internal_node(entry)) {
pr_debug("radix entry %p offset %ld indices %ld-%ld\n",
entry, i, first, last);
} else {
@@ -551,29 +521,28 @@ out:
* Returns -ENOMEM, or 0 for success.
*/
int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
- unsigned order, struct radix_tree_node **nodep,
+ struct radix_tree_node **nodep,
void ***slotp)
{
struct radix_tree_node *node = NULL, *child;
void **slot = (void **)&root->rnode;
unsigned long maxindex;
unsigned int shift, offset = 0;
- unsigned long max = index | ((1UL << order) - 1);

shift = radix_tree_load_root(root, &child, &maxindex);

/* Make sure the tree is high enough. */
- if (max > maxindex) {
- int error = radix_tree_extend(root, max, shift);
+ if (index > maxindex) {
+ int error = radix_tree_extend(root, index, shift);
if (error < 0)
return error;
shift = error;
child = root->rnode;
- if (order == shift)
+ if (!shift)
shift += RADIX_TREE_MAP_SHIFT;
}

- while (shift > order) {
+ while (shift > 0) {
shift -= RADIX_TREE_MAP_SHIFT;
if (child == NULL) {
/* Have to add a child node. */
@@ -595,25 +564,6 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
slot = &node->slots[offset];
}

-#ifdef CONFIG_RADIX_TREE_MULTIORDER
- /* Insert pointers to the canonical entry */
- if (order > shift) {
- unsigned i, n = 1 << (order - shift);
- offset = offset & ~(n - 1);
- slot = &node->slots[offset];
- child = node_to_entry(slot);
- for (i = 0; i < n; i++) {
- if (slot[i])
- return -EEXIST;
- }
-
- for (i = 1; i < n; i++) {
- rcu_assign_pointer(slot[i], child);
- node->count++;
- }
- }
-#endif
-
if (nodep)
*nodep = node;
if (slotp)
@@ -630,8 +580,7 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
*
* Insert an item into the radix tree at position @index.
*/
-int __radix_tree_insert(struct radix_tree_root *root, unsigned long index,
- unsigned order, void *item)
+int radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item)
{
struct radix_tree_node *node;
void **slot;
@@ -639,7 +588,7 @@ int __radix_tree_insert(struct radix_tree_root *root, unsigned long index,

BUG_ON(radix_tree_is_internal_node(item));

- error = __radix_tree_create(root, index, order, &node, &slot);
+ error = __radix_tree_create(root, index, &node, &slot);
if (error)
return error;
if (*slot != NULL)
@@ -658,7 +607,7 @@ int __radix_tree_insert(struct radix_tree_root *root, unsigned long index,

return 0;
}
-EXPORT_SYMBOL(__radix_tree_insert);
+EXPORT_SYMBOL(radix_tree_insert);

/**
* __radix_tree_lookup - lookup an item in a radix tree
@@ -894,14 +843,6 @@ int radix_tree_tag_get(struct radix_tree_root *root,
}
EXPORT_SYMBOL(radix_tree_tag_get);

-static inline void __set_iter_shift(struct radix_tree_iter *iter,
- unsigned int shift)
-{
-#ifdef CONFIG_RADIX_TREE_MULTIORDER
- iter->shift = shift;
-#endif
-}
-
/**
* radix_tree_next_chunk - find next chunk of slots for iteration
*
@@ -945,7 +886,6 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
iter->index = index;
iter->next_index = maxindex + 1;
iter->tags = 1;
- __set_iter_shift(iter, 0);
return (void **)&root->rnode;
}

@@ -967,8 +907,6 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
else
while (++offset < RADIX_TREE_MAP_SIZE) {
void *slot = node->slots[offset];
- if (is_sibling_entry(node, slot))
- continue;
if (slot)
break;
}
@@ -989,7 +927,6 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
/* Update the iterator state */
iter->index = (index &~ node_maxindex(node)) | (offset << node->shift);
iter->next_index = (index | node_maxindex(node)) + 1;
- __set_iter_shift(iter, node->shift);

/* Construct iter->tags bit-mask from node->tags[tag] array */
if (flags & RADIX_TREE_ITER_TAGGED) {
@@ -1112,8 +1049,6 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
node = node->parent;
offset = (index >> node->shift) & RADIX_TREE_MAP_MASK;
}
- if (is_sibling_entry(node, node->slots[offset]))
- goto next;
if (tagged >= nr_to_tag)
break;
}
@@ -1329,8 +1264,6 @@ static unsigned long __locate(struct radix_tree_node *slot, void *item,
continue;
}
node = entry_to_node(node);
- if (is_sibling_entry(slot, node))
- continue;
slot = node;
break;
}
@@ -1505,20 +1438,6 @@ bool __radix_tree_delete_node(struct radix_tree_root *root,
return deleted;
}

-static inline void delete_sibling_entries(struct radix_tree_node *node,
- void *ptr, unsigned offset)
-{
-#ifdef CONFIG_RADIX_TREE_MULTIORDER
- int i;
- for (i = 1; offset + i < RADIX_TREE_MAP_SIZE; i++) {
- if (node->slots[offset + i] != ptr)
- break;
- node->slots[offset + i] = NULL;
- node->count--;
- }
-#endif
-}
-
/**
* radix_tree_delete_item - delete an item from a radix tree
* @root: radix tree root
@@ -1558,7 +1477,6 @@ void *radix_tree_delete_item(struct radix_tree_root *root,
for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
node_tag_clear(root, node, tag, offset);

- delete_sibling_entries(node, node_to_entry(slot), offset);
node->slots[offset] = NULL;
node->count--;

diff --git a/mm/Kconfig b/mm/Kconfig
index be0ee11fa0d9..57fad7262c42 100644
--- a/mm/Kconfig
+++ b/mm/Kconfig
@@ -412,7 +412,6 @@ config TRANSPARENT_HUGEPAGE
bool "Transparent Hugepage Support"
depends on HAVE_ARCH_TRANSPARENT_HUGEPAGE
select COMPACTION
- select RADIX_TREE_MULTIORDER
help
Transparent Hugepages allows the kernel to use huge pages and
huge tlb transparently to the applications whenever possible.
diff --git a/mm/filemap.c b/mm/filemap.c
index 8a287dfc5372..3046d7583267 100644
--- a/mm/filemap.c
+++ b/mm/filemap.c
@@ -591,7 +591,7 @@ static int page_cache_tree_insert(struct address_space *mapping,
void **slot;
int error;

- error = __radix_tree_create(&mapping->page_tree, page->index, 0,
+ error = __radix_tree_create(&mapping->page_tree, page->index,
&node, &slot);
if (error)
return error;
diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile
index 3b530467148e..43febba864bd 100644
--- a/tools/testing/radix-tree/Makefile
+++ b/tools/testing/radix-tree/Makefile
@@ -3,7 +3,7 @@ CFLAGS += -I. -g -Wall -D_LGPL_SOURCE
LDFLAGS += -lpthread -lurcu
TARGETS = main
OFILES = main.o radix-tree.o linux.o test.o tag_check.o find_next_bit.o \
- regression1.o regression2.o regression3.o multiorder.o
+ regression1.o regression2.o regression3.o

targets: $(TARGETS)

diff --git a/tools/testing/radix-tree/generated/autoconf.h b/tools/testing/radix-tree/generated/autoconf.h
index ad18cf5a2a3a..a6b5fba4c3e0 100644
--- a/tools/testing/radix-tree/generated/autoconf.h
+++ b/tools/testing/radix-tree/generated/autoconf.h
@@ -1,3 +1,2 @@
-#define CONFIG_RADIX_TREE_MULTIORDER 1
#define CONFIG_SHMEM 1
#define CONFIG_SWAP 1
diff --git a/tools/testing/radix-tree/main.c b/tools/testing/radix-tree/main.c
index b7619ff3b552..bdee099410f0 100644
--- a/tools/testing/radix-tree/main.c
+++ b/tools/testing/radix-tree/main.c
@@ -232,18 +232,17 @@ void copy_tag_check(void)
item_kill_tree(&tree);
}

-static void __locate_check(struct radix_tree_root *tree, unsigned long index,
- unsigned order)
+static void __locate_check(struct radix_tree_root *tree, unsigned long index)
{
struct item *item;
unsigned long index2;

- item_insert_order(tree, index, order);
+ item_insert(tree, index);
item = item_lookup(tree, index);
index2 = radix_tree_locate_item(tree, item);
if (index != index2) {
- printf("index %ld order %d inserted; found %ld\n",
- index, order, index2);
+ printf("index %ld inserted; found %ld\n",
+ index, index2);
abort();
}
}
@@ -254,7 +253,7 @@ static void __order_0_locate_check(void)
int i;

for (i = 0; i < 50; i++)
- __locate_check(&tree, rand() % INT_MAX, 0);
+ __locate_check(&tree, rand() % INT_MAX);

item_kill_tree(&tree);
}
@@ -262,28 +261,23 @@ static void __order_0_locate_check(void)
static void locate_check(void)
{
RADIX_TREE(tree, GFP_KERNEL);
- unsigned order;
unsigned long offset, index;

__order_0_locate_check();

- for (order = 0; order < 20; order++) {
- for (offset = 0; offset < (1 << (order + 3));
- offset += (1UL << order)) {
- for (index = 0; index < (1UL << (order + 5));
- index += (1UL << order)) {
- __locate_check(&tree, index + offset, order);
- }
- if (radix_tree_locate_item(&tree, &tree) != -1)
- abort();
-
- item_kill_tree(&tree);
+ for (offset = 0; offset < (1 << 3); offset++) {
+ for (index = 0; index < (1UL << 5); index++) {
+ __locate_check(&tree, index + offset);
}
+ if (radix_tree_locate_item(&tree, &tree) != -1)
+ abort();
+
+ item_kill_tree(&tree);
}

if (radix_tree_locate_item(&tree, &tree) != -1)
abort();
- __locate_check(&tree, -1, 0);
+ __locate_check(&tree, -1);
if (radix_tree_locate_item(&tree, &tree) != -1)
abort();
item_kill_tree(&tree);
@@ -294,8 +288,6 @@ static void single_thread_tests(bool long_run)
int i;

printf("starting single_thread_tests: %d allocated\n", nr_allocated);
- multiorder_checks();
- printf("after multiorder_check: %d allocated\n", nr_allocated);
locate_check();
printf("after locate_check: %d allocated\n", nr_allocated);
tag_check();
diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c
deleted file mode 100644
index 39d9b9568fe2..000000000000
--- a/tools/testing/radix-tree/multiorder.c
+++ /dev/null
@@ -1,337 +0,0 @@
-/*
- * multiorder.c: Multi-order radix tree entry testing
- * Copyright (c) 2016 Intel Corporation
- * Author: Ross Zwisler <ross.zwisler@xxxxxxxxxxxxxxx>
- * Author: Matthew Wilcox <matthew.r.wilcox@xxxxxxxxx>
- *
- * This program is free software; you can redistribute it and/or modify it
- * under the terms and conditions of the GNU General Public License,
- * version 2, as published by the Free Software Foundation.
- *
- * This program is distributed in the hope it will be useful, but WITHOUT
- * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
- * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
- * more details.
- */
-#include <linux/radix-tree.h>
-#include <linux/slab.h>
-#include <linux/errno.h>
-
-#include "test.h"
-
-#define for_each_index(i, base, order) \
- for (i = base; i < base + (1 << order); i++)
-
-static void __multiorder_tag_test(int index, int order)
-{
- RADIX_TREE(tree, GFP_KERNEL);
- int base, err, i;
- unsigned long first = 0;
-
- /* our canonical entry */
- base = index & ~((1 << order) - 1);
-
- printf("Multiorder tag test with index %d, canonical entry %d\n",
- index, base);
-
- err = item_insert_order(&tree, index, order);
- assert(!err);
-
- /*
- * Verify we get collisions for covered indices. We try and fail to
- * insert an exceptional entry so we don't leak memory via
- * item_insert_order().
- */
- for_each_index(i, base, order) {
- err = __radix_tree_insert(&tree, i, order,
- (void *)(0xA0 | RADIX_TREE_EXCEPTIONAL_ENTRY));
- assert(err == -EEXIST);
- }
-
- for_each_index(i, base, order) {
- assert(!radix_tree_tag_get(&tree, i, 0));
- assert(!radix_tree_tag_get(&tree, i, 1));
- }
-
- assert(radix_tree_tag_set(&tree, index, 0));
-
- for_each_index(i, base, order) {
- assert(radix_tree_tag_get(&tree, i, 0));
- assert(!radix_tree_tag_get(&tree, i, 1));
- }
-
- assert(radix_tree_range_tag_if_tagged(&tree, &first, ~0UL, 10, 0, 1) == 1);
- assert(radix_tree_tag_clear(&tree, index, 0));
-
- for_each_index(i, base, order) {
- assert(!radix_tree_tag_get(&tree, i, 0));
- assert(radix_tree_tag_get(&tree, i, 1));
- }
-
- assert(radix_tree_tag_clear(&tree, index, 1));
-
- assert(!radix_tree_tagged(&tree, 0));
- assert(!radix_tree_tagged(&tree, 1));
-
- item_kill_tree(&tree);
-}
-
-static void multiorder_tag_tests(void)
-{
- /* test multi-order entry for indices 0-7 with no sibling pointers */
- __multiorder_tag_test(0, 3);
- __multiorder_tag_test(5, 3);
-
- /* test multi-order entry for indices 8-15 with no sibling pointers */
- __multiorder_tag_test(8, 3);
- __multiorder_tag_test(15, 3);
-
- /*
- * Our order 5 entry covers indices 0-31 in a tree with height=2.
- * This is broken up as follows:
- * 0-7: canonical entry
- * 8-15: sibling 1
- * 16-23: sibling 2
- * 24-31: sibling 3
- */
- __multiorder_tag_test(0, 5);
- __multiorder_tag_test(29, 5);
-
- /* same test, but with indices 32-63 */
- __multiorder_tag_test(32, 5);
- __multiorder_tag_test(44, 5);
-
- /*
- * Our order 8 entry covers indices 0-255 in a tree with height=3.
- * This is broken up as follows:
- * 0-63: canonical entry
- * 64-127: sibling 1
- * 128-191: sibling 2
- * 192-255: sibling 3
- */
- __multiorder_tag_test(0, 8);
- __multiorder_tag_test(190, 8);
-
- /* same test, but with indices 256-511 */
- __multiorder_tag_test(256, 8);
- __multiorder_tag_test(300, 8);
-
- __multiorder_tag_test(0x12345678UL, 8);
-}
-
-static void multiorder_check(unsigned long index, int order)
-{
- unsigned long i;
- unsigned long min = index & ~((1UL << order) - 1);
- unsigned long max = min + (1UL << order);
- RADIX_TREE(tree, GFP_KERNEL);
-
- printf("Multiorder index %ld, order %d\n", index, order);
-
- assert(item_insert_order(&tree, index, order) == 0);
-
- for (i = min; i < max; i++) {
- struct item *item = item_lookup(&tree, i);
- assert(item != 0);
- assert(item->index == index);
- }
- for (i = 0; i < min; i++)
- item_check_absent(&tree, i);
- for (i = max; i < 2*max; i++)
- item_check_absent(&tree, i);
- for (i = min; i < max; i++) {
- static void *entry = (void *)
- (0xA0 | RADIX_TREE_EXCEPTIONAL_ENTRY);
- assert(radix_tree_insert(&tree, i, entry) == -EEXIST);
- }
-
- assert(item_delete(&tree, index) != 0);
-
- for (i = 0; i < 2*max; i++)
- 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);
-
- item_insert(&tree, 0);
- radix_tree_tag_set(&tree, 0, 0);
- item_insert_order(&tree, 3 << 6, 6);
-
- item_kill_tree(&tree);
-}
-
-void multiorder_iteration(void)
-{
- RADIX_TREE(tree, GFP_KERNEL);
- struct radix_tree_iter iter;
- void **slot;
- int i, j, err;
-
- printf("Multiorder iteration test\n");
-
-#define NUM_ENTRIES 11
- int index[NUM_ENTRIES] = {0, 2, 4, 8, 16, 32, 34, 36, 64, 72, 128};
- int order[NUM_ENTRIES] = {1, 1, 2, 3, 4, 1, 0, 1, 3, 0, 7};
-
- for (i = 0; i < NUM_ENTRIES; i++) {
- err = item_insert_order(&tree, index[i], order[i]);
- assert(!err);
- }
-
- for (j = 0; j < 256; j++) {
- for (i = 0; i < NUM_ENTRIES; i++)
- if (j <= (index[i] | ((1 << order[i]) - 1)))
- break;
-
- radix_tree_for_each_slot(slot, &tree, &iter, j) {
- int height = order[i] / RADIX_TREE_MAP_SHIFT;
- int shift = height * RADIX_TREE_MAP_SHIFT;
- int mask = (1 << order[i]) - 1;
-
- assert(iter.index >= (index[i] &~ mask));
- assert(iter.index <= (index[i] | mask));
- assert(iter.shift == shift);
- i++;
- }
- }
-
- item_kill_tree(&tree);
-}
-
-void multiorder_tagged_iteration(void)
-{
- RADIX_TREE(tree, GFP_KERNEL);
- struct radix_tree_iter iter;
- void **slot;
- unsigned long first = 0;
- int i, j;
-
- printf("Multiorder tagged iteration test\n");
-
-#define MT_NUM_ENTRIES 9
- int index[MT_NUM_ENTRIES] = {0, 2, 4, 16, 32, 40, 64, 72, 128};
- int order[MT_NUM_ENTRIES] = {1, 0, 2, 4, 3, 1, 3, 0, 7};
-
-#define TAG_ENTRIES 7
- int tag_index[TAG_ENTRIES] = {0, 4, 16, 40, 64, 72, 128};
-
- for (i = 0; i < MT_NUM_ENTRIES; i++)
- assert(!item_insert_order(&tree, index[i], order[i]));
-
- assert(!radix_tree_tagged(&tree, 1));
-
- for (i = 0; i < TAG_ENTRIES; i++)
- assert(radix_tree_tag_set(&tree, tag_index[i], 1));
-
- for (j = 0; j < 256; j++) {
- int mask, k;
-
- for (i = 0; i < TAG_ENTRIES; i++) {
- for (k = i; index[k] < tag_index[i]; k++)
- ;
- if (j <= (index[k] | ((1 << order[k]) - 1)))
- break;
- }
-
- radix_tree_for_each_tagged(slot, &tree, &iter, j, 1) {
- for (k = i; index[k] < tag_index[i]; k++)
- ;
- mask = (1 << order[k]) - 1;
-
- assert(iter.index >= (tag_index[i] &~ mask));
- assert(iter.index <= (tag_index[i] | mask));
- i++;
- }
- }
-
- radix_tree_range_tag_if_tagged(&tree, &first, ~0UL,
- MT_NUM_ENTRIES, 1, 2);
-
- for (j = 0; j < 256; j++) {
- int mask, k;
-
- for (i = 0; i < TAG_ENTRIES; i++) {
- for (k = i; index[k] < tag_index[i]; k++)
- ;
- if (j <= (index[k] | ((1 << order[k]) - 1)))
- break;
- }
-
- radix_tree_for_each_tagged(slot, &tree, &iter, j, 2) {
- for (k = i; index[k] < tag_index[i]; k++)
- ;
- mask = (1 << order[k]) - 1;
-
- assert(iter.index >= (tag_index[i] &~ mask));
- assert(iter.index <= (tag_index[i] | mask));
- i++;
- }
- }
-
- first = 1;
- radix_tree_range_tag_if_tagged(&tree, &first, ~0UL,
- MT_NUM_ENTRIES, 1, 0);
- i = 0;
- radix_tree_for_each_tagged(slot, &tree, &iter, 0, 0) {
- assert(iter.index == tag_index[i]);
- i++;
- }
-
- item_kill_tree(&tree);
-}
-
-void multiorder_checks(void)
-{
- int i;
-
- for (i = 0; i < 20; i++) {
- multiorder_check(200, i);
- multiorder_check(0, i);
- multiorder_check((1UL << i) + 1, i);
- }
-
- for (i = 0; i < 15; i++)
- multiorder_shrink((1UL << (i + RADIX_TREE_MAP_SHIFT)), i);
-
- multiorder_insert_bug();
- multiorder_tag_tests();
- multiorder_iteration();
- multiorder_tagged_iteration();
-}
diff --git a/tools/testing/radix-tree/test.c b/tools/testing/radix-tree/test.c
index a6e8099eaf4f..81377b40af79 100644
--- a/tools/testing/radix-tree/test.c
+++ b/tools/testing/radix-tree/test.c
@@ -24,21 +24,9 @@ int item_tag_get(struct radix_tree_root *root, unsigned long index, int tag)
return radix_tree_tag_get(root, index, tag);
}

-int __item_insert(struct radix_tree_root *root, struct item *item,
- unsigned order)
-{
- return __radix_tree_insert(root, item->index, order, item);
-}
-
int item_insert(struct radix_tree_root *root, unsigned long index)
{
- return __item_insert(root, item_create(index), 0);
-}
-
-int item_insert_order(struct radix_tree_root *root, unsigned long index,
- unsigned order)
-{
- return __item_insert(root, item_create(index), order);
+ return radix_tree_insert(root, index, item_create(index));
}

int item_delete(struct radix_tree_root *root, unsigned long index)
diff --git a/tools/testing/radix-tree/test.h b/tools/testing/radix-tree/test.h
index e85131369723..7c2e290e4c3e 100644
--- a/tools/testing/radix-tree/test.h
+++ b/tools/testing/radix-tree/test.h
@@ -8,11 +8,7 @@ struct item {
};

struct item *item_create(unsigned long index);
-int __item_insert(struct radix_tree_root *root, struct item *item,
- unsigned order);
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);
struct item *item_lookup(struct radix_tree_root *root, unsigned long index);

@@ -26,7 +22,6 @@ void item_full_scan(struct radix_tree_root *root, unsigned long start,
void item_kill_tree(struct radix_tree_root *root);

void tag_check(void);
-void multiorder_checks(void);

struct item *
item_tag_set(struct radix_tree_root *root, unsigned long index, int tag);