From 1366c37ed84b166a0fffe201154b0d3b78a3976b Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Thu, 17 Mar 2016 14:21:45 -0700 Subject: radix tree test harness This code is mostly from Andrew Morton and Nick Piggin; tarball downloaded from http://ozlabs.org/~akpm/rtth.tar.gz with sha1sum 0ce679db9ec047296b5d1ff7a1dfaa03a7bef1bd Some small modifications were necessary to the test harness to fix the build with the current Linux source code. I also made minor modifications to automatically test the radix-tree.c and radix-tree.h files that are in the current source tree, as opposed to a copied and slightly modified version. I am sure more could be done to tidy up the harness, as well as adding more tests. [koct9i@gmail.com: fix compilation] Signed-off-by: Matthew Wilcox Cc: Shuah Khan Cc: Johannes Weiner Cc: Matthew Wilcox Cc: "Kirill A. Shutemov" Cc: Ross Zwisler Cc: Hugh Dickins Signed-off-by: Konstantin Khlebnikov Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- tools/testing/radix-tree/test.c | 218 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 218 insertions(+) create mode 100644 tools/testing/radix-tree/test.c (limited to 'tools/testing/radix-tree/test.c') diff --git a/tools/testing/radix-tree/test.c b/tools/testing/radix-tree/test.c new file mode 100644 index 000000000000..c9b0bd75b6c6 --- /dev/null +++ b/tools/testing/radix-tree/test.c @@ -0,0 +1,218 @@ +#include +#include +#include +#include +#include +#include + +#include "test.h" + +struct item * +item_tag_set(struct radix_tree_root *root, unsigned long index, int tag) +{ + return radix_tree_tag_set(root, index, tag); +} + +struct item * +item_tag_clear(struct radix_tree_root *root, unsigned long index, int tag) +{ + return radix_tree_tag_clear(root, index, tag); +} + +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) +{ + return radix_tree_insert(root, item->index, item); +} + +int item_insert(struct radix_tree_root *root, unsigned long index) +{ + return __item_insert(root, item_create(index)); +} + +int item_delete(struct radix_tree_root *root, unsigned long index) +{ + struct item *item = radix_tree_delete(root, index); + + if (item) { + assert(item->index == index); + free(item); + return 1; + } + return 0; +} + +struct item *item_create(unsigned long index) +{ + struct item *ret = malloc(sizeof(*ret)); + + ret->index = index; + return ret; +} + +void item_check_present(struct radix_tree_root *root, unsigned long index) +{ + struct item *item; + + item = radix_tree_lookup(root, index); + assert(item != 0); + assert(item->index == index); +} + +struct item *item_lookup(struct radix_tree_root *root, unsigned long index) +{ + return radix_tree_lookup(root, index); +} + +void item_check_absent(struct radix_tree_root *root, unsigned long index) +{ + struct item *item; + + item = radix_tree_lookup(root, index); + assert(item == 0); +} + +/* + * Scan only the passed (start, start+nr] for present items + */ +void item_gang_check_present(struct radix_tree_root *root, + unsigned long start, unsigned long nr, + int chunk, int hop) +{ + struct item *items[chunk]; + unsigned long into; + + for (into = 0; into < nr; ) { + int nfound; + int nr_to_find = chunk; + int i; + + if (nr_to_find > (nr - into)) + nr_to_find = nr - into; + + nfound = radix_tree_gang_lookup(root, (void **)items, + start + into, nr_to_find); + assert(nfound == nr_to_find); + for (i = 0; i < nfound; i++) + assert(items[i]->index == start + into + i); + into += hop; + } +} + +/* + * Scan the entire tree, only expecting present items (start, start+nr] + */ +void item_full_scan(struct radix_tree_root *root, unsigned long start, + unsigned long nr, int chunk) +{ + struct item *items[chunk]; + unsigned long into = 0; + unsigned long this_index = start; + int nfound; + int i; + +// printf("%s(0x%08lx, 0x%08lx, %d)\n", __FUNCTION__, start, nr, chunk); + + while ((nfound = radix_tree_gang_lookup(root, (void **)items, into, + chunk))) { +// printf("At 0x%08lx, nfound=%d\n", into, nfound); + for (i = 0; i < nfound; i++) { + assert(items[i]->index == this_index); + this_index++; + } +// printf("Found 0x%08lx->0x%08lx\n", +// items[0]->index, items[nfound-1]->index); + into = this_index; + } + if (chunk) + assert(this_index == start + nr); + nfound = radix_tree_gang_lookup(root, (void **)items, + this_index, chunk); + assert(nfound == 0); +} + +static int verify_node(struct radix_tree_node *slot, unsigned int tag, + unsigned int height, int tagged) +{ + int anyset = 0; + int i; + int j; + + /* Verify consistency at this level */ + for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) { + if (slot->tags[tag][i]) { + anyset = 1; + break; + } + } + if (tagged != anyset) { + printf("tag: %u, height %u, tagged: %d, anyset: %d\n", tag, height, tagged, anyset); + for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) { + printf("tag %d: ", j); + for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) + printf("%016lx ", slot->tags[j][i]); + printf("\n"); + } + return 1; + } + assert(tagged == anyset); + + /* Go for next level */ + if (height > 1) { + for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) + if (slot->slots[i]) + if (verify_node(slot->slots[i], tag, height - 1, + !!test_bit(i, slot->tags[tag]))) { + printf("Failure at off %d\n", i); + for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) { + printf("tag %d: ", j); + for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) + printf("%016lx ", slot->tags[j][i]); + printf("\n"); + } + return 1; + } + } + return 0; +} + +void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag) +{ + if (!root->height) + return; + verify_node(indirect_to_ptr(root->rnode), + tag, root->height, !!root_tag_get(root, tag)); +} + +void item_kill_tree(struct radix_tree_root *root) +{ + struct item *items[32]; + int nfound; + + while ((nfound = radix_tree_gang_lookup(root, (void **)items, 0, 32))) { + int i; + + for (i = 0; i < nfound; i++) { + void *ret; + + ret = radix_tree_delete(root, items[i]->index); + assert(ret == items[i]); + free(items[i]); + } + } + assert(radix_tree_gang_lookup(root, (void **)items, 0, 32) == 0); + assert(root->rnode == NULL); +} + +void tree_verify_min_height(struct radix_tree_root *root, int maxindex) +{ + assert(radix_tree_maxindex(root->height) >= maxindex); + if (root->height > 1) + assert(radix_tree_maxindex(root->height-1) < maxindex); + else if (root->height == 1) + assert(radix_tree_maxindex(root->height-1) <= maxindex); +} -- cgit v1.2.3 From 339e6353046dd4f675304d696a88aefdd727298e Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Thu, 17 Mar 2016 14:21:48 -0700 Subject: radix_tree: tag all internal tree nodes as indirect pointers Set the 'indirect_ptr' bit on all the pointers to internal nodes, not just on the root node. This enables the following patches to support multi-order entries in the radix tree. This patch is split out for ease of bisection. Signed-off-by: Matthew Wilcox Cc: Johannes Weiner Cc: Matthew Wilcox Cc: "Kirill A. Shutemov" Cc: Ross Zwisler Cc: Hugh Dickins Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/radix-tree.c | 24 ++++++++++++++++++------ tools/testing/radix-tree/test.c | 5 +++-- 2 files changed, 21 insertions(+), 8 deletions(-) (limited to 'tools/testing/radix-tree/test.c') diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 224b369f5a5e..ff91792346f6 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -368,9 +368,10 @@ static int radix_tree_extend(struct radix_tree_root *root, unsigned long index) node->count = 1; node->parent = NULL; slot = root->rnode; - if (newheight > 1) { + if (radix_tree_is_indirect_ptr(slot) && newheight > 1) { slot = indirect_to_ptr(slot); slot->parent = node; + slot = ptr_to_indirect(slot); } node->slots[0] = slot; node = ptr_to_indirect(node); @@ -425,17 +426,20 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index, slot->path = height; slot->parent = node; if (node) { - rcu_assign_pointer(node->slots[offset], slot); + rcu_assign_pointer(node->slots[offset], + ptr_to_indirect(slot)); node->count++; slot->path |= offset << RADIX_TREE_HEIGHT_SHIFT; } else - rcu_assign_pointer(root->rnode, ptr_to_indirect(slot)); + rcu_assign_pointer(root->rnode, + ptr_to_indirect(slot)); } /* Go a level down */ offset = (index >> shift) & RADIX_TREE_MAP_MASK; node = slot; slot = node->slots[offset]; + slot = indirect_to_ptr(slot); shift -= RADIX_TREE_MAP_SHIFT; height--; } @@ -533,6 +537,7 @@ void *__radix_tree_lookup(struct radix_tree_root *root, unsigned long index, node = rcu_dereference_raw(*slot); if (node == NULL) return NULL; + node = indirect_to_ptr(node); shift -= RADIX_TREE_MAP_SHIFT; height--; @@ -619,6 +624,7 @@ void *radix_tree_tag_set(struct radix_tree_root *root, tag_set(slot, tag, offset); slot = slot->slots[offset]; BUG_ON(slot == NULL); + slot = indirect_to_ptr(slot); shift -= RADIX_TREE_MAP_SHIFT; height--; } @@ -658,11 +664,12 @@ void *radix_tree_tag_clear(struct radix_tree_root *root, goto out; shift = height * RADIX_TREE_MAP_SHIFT; - slot = indirect_to_ptr(root->rnode); + slot = root->rnode; while (shift) { if (slot == NULL) goto out; + slot = indirect_to_ptr(slot); shift -= RADIX_TREE_MAP_SHIFT; offset = (index >> shift) & RADIX_TREE_MAP_MASK; @@ -738,6 +745,7 @@ int radix_tree_tag_get(struct radix_tree_root *root, if (node == NULL) return 0; + node = indirect_to_ptr(node); offset = (index >> shift) & RADIX_TREE_MAP_MASK; if (!tag_get(node, tag, offset)) @@ -838,6 +846,7 @@ restart: node = rcu_dereference_raw(node->slots[offset]); if (node == NULL) goto restart; + node = indirect_to_ptr(node); shift -= RADIX_TREE_MAP_SHIFT; offset = (index >> shift) & RADIX_TREE_MAP_MASK; } @@ -939,6 +948,7 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root, shift -= RADIX_TREE_MAP_SHIFT; node = slot; slot = slot->slots[offset]; + slot = indirect_to_ptr(slot); continue; } @@ -1195,6 +1205,7 @@ static unsigned long __locate(struct radix_tree_node *slot, void *item, slot = rcu_dereference_raw(slot->slots[i]); if (slot == NULL) goto out; + slot = indirect_to_ptr(slot); } /* Bottom level: check items */ @@ -1278,7 +1289,8 @@ static inline void radix_tree_shrink(struct radix_tree_root *root) */ if (to_free->count != 1) break; - if (!to_free->slots[0]) + slot = to_free->slots[0]; + if (!slot) break; /* @@ -1288,8 +1300,8 @@ static inline void radix_tree_shrink(struct radix_tree_root *root) * (to_free->slots[0]), it will be safe to dereference the new * one (root->rnode) as far as dependent read barriers go. */ - slot = to_free->slots[0]; if (root->height > 1) { + slot = indirect_to_ptr(slot); slot->parent = NULL; slot = ptr_to_indirect(slot); } diff --git a/tools/testing/radix-tree/test.c b/tools/testing/radix-tree/test.c index c9b0bd75b6c6..2bebf34cdc27 100644 --- a/tools/testing/radix-tree/test.c +++ b/tools/testing/radix-tree/test.c @@ -142,6 +142,8 @@ static int verify_node(struct radix_tree_node *slot, unsigned int tag, int i; int j; + slot = indirect_to_ptr(slot); + /* Verify consistency at this level */ for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) { if (slot->tags[tag][i]) { @@ -184,8 +186,7 @@ void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag) { if (!root->height) return; - verify_node(indirect_to_ptr(root->rnode), - tag, root->height, !!root_tag_get(root, tag)); + verify_node(root->rnode, tag, root->height, !!root_tag_get(root, tag)); } void item_kill_tree(struct radix_tree_root *root) -- cgit v1.2.3