summaryrefslogtreecommitdiff
path: root/tools
diff options
context:
space:
mode:
authorMatthew Wilcox <willy@linux.intel.com>2016-05-20 17:02:52 -0700
committerLinus Torvalds <torvalds@linux-foundation.org>2016-05-20 17:58:30 -0700
commit070c5ac2740b5db89d381a09fb03b2480b2f7a74 (patch)
tree1ad983222d48c155f20d6f1e03d759484e873823 /tools
parenteb73f7f3300c144c4b886dd56ea4c3d2b2d58249 (diff)
downloadlinux-070c5ac2740b5db89d381a09fb03b2480b2f7a74.tar.gz
radix-tree: fix radix_tree_range_tag_if_tagged() for multiorder entries
I had previously decided that tagging a single multiorder entry would count as tagging 2^order entries for the purposes of 'nr_to_tag'. I now believe that decision to be a mistake, and it should count as a single entry. That's more likely to be what callers expect. When walking back up the tree from a newly-tagged entry, the current code assumed we were starting from the lowest level of the tree; if we have a multiorder entry with an order at least RADIX_TREE_MAP_SHIFT in size then we need to shift the index by 'shift' before we start walking back up the tree, or we will end up not setting tags on higher entries, and then mistakenly thinking that entries below a certain point in the tree are not tagged. If the first index we examine is a sibling entry of a tagged multiorder entry, we were not tagging it. We need to examine the canonical entry, and the easiest way to do that is to use radix_tree_descend(). We then have to skip over sibling slots when looking for the next entry in the tree or we will end up walking back to the canonical entry. Add several tests for radix_tree_range_tag_if_tagged(). 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/multiorder.c25
-rw-r--r--tools/testing/radix-tree/tag_check.c10
2 files changed, 34 insertions, 1 deletions
diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c
index fc934578e1ef..c061f4bd6c05 100644
--- a/tools/testing/radix-tree/multiorder.c
+++ b/tools/testing/radix-tree/multiorder.c
@@ -26,6 +26,7 @@ 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);
@@ -59,13 +60,16 @@ static void __multiorder_tag_test(int index, int order)
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_get(&tree, i, 1));
}
+ assert(radix_tree_tag_clear(&tree, index, 1));
+
assert(!radix_tree_tagged(&tree, 0));
assert(!radix_tree_tagged(&tree, 1));
@@ -244,6 +248,7 @@ void multiorder_tagged_iteration(void)
RADIX_TREE(tree, GFP_KERNEL);
struct radix_tree_iter iter;
void **slot;
+ unsigned long first = 0;
int i;
printf("Multiorder tagged iteration test\n");
@@ -280,6 +285,24 @@ void multiorder_tagged_iteration(void)
i++;
}
+ radix_tree_range_tag_if_tagged(&tree, &first, ~0UL,
+ MT_NUM_ENTRIES, 1, 2);
+
+ i = 0;
+ radix_tree_for_each_tagged(slot, &tree, &iter, 1, 2) {
+ assert(iter.index == tag_index[i]);
+ 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);
}
diff --git a/tools/testing/radix-tree/tag_check.c b/tools/testing/radix-tree/tag_check.c
index 83136be552a0..b7447ceb75e9 100644
--- a/tools/testing/radix-tree/tag_check.c
+++ b/tools/testing/radix-tree/tag_check.c
@@ -12,6 +12,7 @@
static void
__simple_checks(struct radix_tree_root *tree, unsigned long index, int tag)
{
+ unsigned long first = 0;
int ret;
item_check_absent(tree, index);
@@ -22,6 +23,10 @@ __simple_checks(struct radix_tree_root *tree, unsigned long index, int tag)
item_tag_set(tree, index, tag);
ret = item_tag_get(tree, index, tag);
assert(ret != 0);
+ ret = radix_tree_range_tag_if_tagged(tree, &first, ~0UL, 10, tag, !tag);
+ assert(ret == 1);
+ ret = item_tag_get(tree, index, !tag);
+ assert(ret != 0);
ret = item_delete(tree, index);
assert(ret != 0);
item_insert(tree, index);
@@ -304,6 +309,7 @@ static void single_check(void)
struct item *items[BATCH];
RADIX_TREE(tree, GFP_KERNEL);
int ret;
+ unsigned long first = 0;
item_insert(&tree, 0);
item_tag_set(&tree, 0, 0);
@@ -313,6 +319,10 @@ static void single_check(void)
assert(ret == 0);
verify_tag_consistency(&tree, 0);
verify_tag_consistency(&tree, 1);
+ ret = radix_tree_range_tag_if_tagged(&tree, &first, 10, 10, 0, 1);
+ assert(ret == 1);
+ ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 1);
+ assert(ret == 1);
item_kill_tree(&tree);
}