@@ -1036,14 +1036,13 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
unsigned long nr_to_tag,
unsigned int iftag, unsigned int settag)
{
- unsigned int height = root->height;
- struct radix_tree_node *node = NULL;
- struct radix_tree_node *slot;
- unsigned int shift;
+ struct radix_tree_node *slot, *node = NULL;
+ unsigned long maxindex;
+ unsigned int shift = radix_tree_load_root(root, &slot, &maxindex);
unsigned long tagged = 0;
unsigned long index = *first_indexp;
- last_index = min(last_index, radix_tree_maxindex(height));
+ last_index = min(last_index, maxindex);
if (index > last_index)
return 0;
if (!nr_to_tag)
@@ -1052,14 +1051,14 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
*first_indexp = last_index + 1;
return 0;
}
- if (height == 0) {
+ if (!radix_tree_is_indirect_ptr(slot)) {
*first_indexp = last_index + 1;
root_tag_set(root, settag);
return 1;
}
- shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
- slot = indirect_to_ptr(root->rnode);
+ shift -= RADIX_TREE_MAP_SHIFT;
+ slot = indirect_to_ptr(slot);
for (;;) {
unsigned long upindex;
@@ -1075,6 +1074,7 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
slot = slot->slots[offset];
if (radix_tree_is_indirect_ptr(slot)) {
slot = indirect_to_ptr(slot);
+ /* Sibling slots are never tagged */
shift -= RADIX_TREE_MAP_SHIFT;
continue;
} else {
@@ -1084,11 +1084,11 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
}
/* tag the leaf */
- tagged += 1 << shift;
+ tagged++;
tag_set(slot, settag, offset);
/* walk back up the path tagging interior nodes */
- upindex = index;
+ upindex = index >> shift;
while (node) {
upindex >>= RADIX_TREE_MAP_SHIFT;
offset = upindex & RADIX_TREE_MAP_MASK;
@@ -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,15 @@ 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++;
+ }
+
item_kill_tree(&tree);
}
@@ -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);
}