summaryrefslogtreecommitdiffstats
path: root/tools
diff options
context:
space:
mode:
authorMatthew Wilcox <willy@linux.intel.com>2016-05-20 17:02:46 -0700
committerLinus Torvalds <torvalds@linux-foundation.org>2016-05-20 17:58:30 -0700
commit0a2efc6c809b01872321d9c7e7d82d59ac6fde10 (patch)
tree18b67497a5df2dfe015ed03fe665fae59f0311ca /tools
parent8a14f4d8328cc8615f8a5487c4173f36a8314796 (diff)
downloadop-kernel-dev-0a2efc6c809b01872321d9c7e7d82d59ac6fde10.zip
op-kernel-dev-0a2efc6c809b01872321d9c7e7d82d59ac6fde10.tar.gz
radix-tree: rewrite radix_tree_locate_item
Use the new multi-order support functions to rewrite radix_tree_locate_item(). Modify the locate tests to test multiorder entries too. [hughd@google.com: radix_tree_locate_item() is often returning the wrong index] Link: http://lkml.kernel.org/r/alpine.LSU.2.11.1605012108490.1166@eggly.anvils Signed-off-by: Matthew Wilcox <willy@linux.intel.com> Reviewed-by: Ross Zwisler <ross.zwisler@linux.intel.com> Cc: Konstantin Khlebnikov <koct9i@gmail.com> Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com> Cc: Jan Kara <jack@suse.com> Cc: Neil Brown <neilb@suse.de> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat (limited to 'tools')
-rw-r--r--tools/testing/radix-tree/main.c30
1 files changed, 18 insertions, 12 deletions
diff --git a/tools/testing/radix-tree/main.c b/tools/testing/radix-tree/main.c
index b6a700b..65231e9 100644
--- a/tools/testing/radix-tree/main.c
+++ b/tools/testing/radix-tree/main.c
@@ -232,17 +232,18 @@ void copy_tag_check(void)
item_kill_tree(&tree);
}
-void __locate_check(struct radix_tree_root *tree, unsigned long index)
+void __locate_check(struct radix_tree_root *tree, unsigned long index,
+ unsigned order)
{
struct item *item;
unsigned long index2;
- item_insert(tree, index);
+ item_insert_order(tree, index, order);
item = item_lookup(tree, index);
index2 = radix_tree_locate_item(tree, item);
if (index != index2) {
- printf("index %ld inserted; found %ld\n",
- index, index2);
+ printf("index %ld order %d inserted; found %ld\n",
+ index, order, index2);
abort();
}
}
@@ -250,21 +251,26 @@ void __locate_check(struct radix_tree_root *tree, unsigned long index)
static void locate_check(void)
{
RADIX_TREE(tree, GFP_KERNEL);
+ unsigned order;
unsigned long offset, index;
- 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();
+ 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);
+ item_kill_tree(&tree);
+ }
}
if (radix_tree_locate_item(&tree, &tree) != -1)
abort();
- __locate_check(&tree, -1);
+ __locate_check(&tree, -1, 0);
if (radix_tree_locate_item(&tree, &tree) != -1)
abort();
item_kill_tree(&tree);
OpenPOWER on IntegriCloud