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 - * Author: Matthew Wilcox - * - * 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 -#include -#include - -#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);