The patch titled
Subject: radix-tree: rewrite radix_tree_locate_item
has been added to the -mm tree. Its filename is
radix-tree-rewrite-radix_tree_locate_item.patch
This patch should soon appear at
http://ozlabs.org/~akpm/mmots/broken-out/radix-tree-rewrite-radix_tree_locate_item.patch
and later at
http://ozlabs.org/~akpm/mmotm/broken-out/radix-tree-rewrite-radix_tree_locate_item.patch
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/SubmitChecklist when testing your code ***
The -mm tree is included into linux-next and is updated
there every 3-4 working days
------------------------------------------------------
From: Matthew Wilcox <willy@xxxxxxxxxxxxxxx>
Subject: 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.
Signed-off-by: Matthew Wilcox <willy@xxxxxxxxxxxxxxx>
Reviewed-by: Ross Zwisler <ross.zwisler@xxxxxxxxxxxxxxx>
Cc: Konstantin Khlebnikov <koct9i@xxxxxxxxx>
Cc: Kirill Shutemov <kirill.shutemov@xxxxxxxxxxxxxxx>
Cc: Jan Kara <jack@xxxxxxxx>
Cc: Neil Brown <neilb@xxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
---
lib/radix-tree.c | 90 +++++++++++++++---------------
tools/testing/radix-tree/main.c | 30 ++++++----
2 files changed, 63 insertions(+), 57 deletions(-)
diff -puN lib/radix-tree.c~radix-tree-rewrite-radix_tree_locate_item lib/radix-tree.c
--- a/lib/radix-tree.c~radix-tree-rewrite-radix_tree_locate_item
+++ a/lib/radix-tree.c
@@ -1303,58 +1303,55 @@ EXPORT_SYMBOL(radix_tree_gang_lookup_tag
#if defined(CONFIG_SHMEM) && defined(CONFIG_SWAP)
#include <linux/sched.h> /* for cond_resched() */
+struct locate_info {
+ unsigned long found_index;
+ bool stop;
+};
+
/*
* This linear search is at present only useful to shmem_unuse_inode().
*/
static unsigned long __locate(struct radix_tree_node *slot, void *item,
- unsigned long index, unsigned long *found_index)
+ unsigned long index, struct locate_info *info)
{
unsigned int shift, height;
- unsigned long i;
+ unsigned long base, i;
height = slot->path & RADIX_TREE_HEIGHT_MASK;
- shift = (height-1) * RADIX_TREE_MAP_SHIFT;
+ shift = height * RADIX_TREE_MAP_SHIFT;
- for ( ; height > 1; height--) {
- i = (index >> shift) & RADIX_TREE_MAP_MASK;
- for (;;) {
- if (slot->slots[i] != NULL)
- break;
- index &= ~((1UL << shift) - 1);
- index += 1UL << shift;
- if (index == 0)
- goto out; /* 32-bit wraparound */
- i++;
- if (i == RADIX_TREE_MAP_SIZE)
- goto out;
- }
+ do {
+ shift -= RADIX_TREE_MAP_SHIFT;
+ base = index & ~((1UL << shift) - 1);
- slot = rcu_dereference_raw(slot->slots[i]);
- if (slot == NULL)
- goto out;
- if (!radix_tree_is_indirect_ptr(slot)) {
- if (slot == item) {
- *found_index = index + i;
- index = 0;
- } else {
- index += shift;
+ for (i = (index >> shift) & RADIX_TREE_MAP_MASK;
+ i < RADIX_TREE_MAP_SIZE;
+ i++, index = base + (i << shift)) {
+ struct radix_tree_node *node =
+ rcu_dereference_raw(slot->slots[i]);
+ if (node == RADIX_TREE_RETRY)
+ goto out;
+ if (!radix_tree_is_indirect_ptr(node)) {
+ if (node == item) {
+ info->found_index = index;
+ info->stop = true;
+ goto out;
+ }
+ continue;
}
- goto out;
+ node = indirect_to_ptr(node);
+ if (is_sibling_entry(slot, node))
+ continue;
+ slot = node;
+ break;
}
- slot = indirect_to_ptr(slot);
- shift -= RADIX_TREE_MAP_SHIFT;
- }
+ if (i == RADIX_TREE_MAP_SIZE)
+ break;
+ } while (shift);
- /* Bottom level: check items */
- for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) {
- if (slot->slots[i] == item) {
- *found_index = index + i;
- index = 0;
- goto out;
- }
- }
- index += RADIX_TREE_MAP_SIZE;
out:
+ if ((index == 0) && (i == RADIX_TREE_MAP_SIZE))
+ info->stop = true;
return index;
}
@@ -1372,7 +1369,10 @@ unsigned long radix_tree_locate_item(str
struct radix_tree_node *node;
unsigned long max_index;
unsigned long cur_index = 0;
- unsigned long found_index = -1;
+ struct locate_info info = {
+ .found_index = -1,
+ .stop = false,
+ };
do {
rcu_read_lock();
@@ -1380,24 +1380,24 @@ unsigned long radix_tree_locate_item(str
if (!radix_tree_is_indirect_ptr(node)) {
rcu_read_unlock();
if (node == item)
- found_index = 0;
+ info.found_index = 0;
break;
}
node = indirect_to_ptr(node);
- max_index = radix_tree_maxindex(node->path &
- RADIX_TREE_HEIGHT_MASK);
+
+ max_index = node_maxindex(node);
if (cur_index > max_index) {
rcu_read_unlock();
break;
}
- cur_index = __locate(node, item, cur_index, &found_index);
+ cur_index = __locate(node, item, cur_index, &info);
rcu_read_unlock();
cond_resched();
- } while (cur_index != 0 && cur_index <= max_index);
+ } while (!info.stop && cur_index <= max_index);
- return found_index;
+ return info.found_index;
}
#else
unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item)
diff -puN tools/testing/radix-tree/main.c~radix-tree-rewrite-radix_tree_locate_item tools/testing/radix-tree/main.c
--- a/tools/testing/radix-tree/main.c~radix-tree-rewrite-radix_tree_locate_item
+++ a/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_ro
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);
_
Patches currently in -mm which might be from willy@xxxxxxxxxxxxxxx are
radix-tree-introduce-radix_tree_empty.patch
radix-tree-test-suite-fix-build.patch
radix-tree-test-suite-add-tests-for-radix_tree_locate_item.patch
introduce-config_radix_tree_multiorder.patch
radix-tree-add-missing-sibling-entry-functionality.patch
radix-tree-fix-sibling-entry-insertion.patch
radix-tree-fix-deleting-a-multi-order-entry-through-an-alias.patch
radix-tree-remove-restriction-on-multi-order-entries.patch
radix-tree-introduce-radix_tree_load_root.patch
radix-tree-fix-extending-the-tree-for-multi-order-entries-at-offset-0.patch
radix-tree-test-suite-start-adding-multiorder-tests.patch
radix-tree-fix-several-shrinking-bugs-with-multiorder-entries.patch
radix-tree-rewrite-__radix_tree_lookup.patch
radix-tree-fix-multiorder-bug_on-in-radix_tree_insert.patch
radix-tree-fix-radix_tree_create-for-sibling-entries.patch
radix-tree-rewrite-radix_tree_locate_item.patch
radix-tree-fix-radix_tree_range_tag_if_tagged-for-multiorder-entries.patch
radix-tree-add-copyright-statements.patch
--
To unsubscribe from this list: send the line "unsubscribe mm-commits" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
