Replace the hole scan functions with more fast versions: - radix_tree_next_hole(root, index, max_scan) - radix_tree_prev_hole(root, index, max_scan) Cc: Nick Piggin Signed-off-by: Wu Fengguang --- lib/radix-tree.c | 67 +++++++++++++++++++++++++++++++++++++-------- 1 file changed, 56 insertions(+), 11 deletions(-) --- linux.orig/lib/radix-tree.c 2010-02-24 10:44:49.000000000 +0800 +++ linux/lib/radix-tree.c 2010-02-24 10:44:50.000000000 +0800 @@ -647,18 +647,41 @@ EXPORT_SYMBOL(radix_tree_tag_get); * under rcu_read_lock. */ unsigned long radix_tree_next_hole(struct radix_tree_root *root, - unsigned long index, unsigned long max_scan) + unsigned long index, unsigned long max_scan) { - unsigned long i; + struct radix_tree_node *node; + unsigned long origin = index; + int i; + + node = rcu_dereference(root->rnode); + if (node == NULL) + return index; + + if (!radix_tree_is_indirect_ptr(node)) + return index ? index : 1; - for (i = 0; i < max_scan; i++) { - if (!radix_tree_lookup(root, index)) + while (index - origin < max_scan) { + node = radix_tree_lookup_leaf_node(root, index); + if (!node) break; - index++; - if (index == 0) + + if (node->count == RADIX_TREE_MAP_SIZE) { + index = (index | RADIX_TREE_MAP_MASK) + 1; + goto check_overflow; + } + + for (i = index & RADIX_TREE_MAP_MASK; + i < RADIX_TREE_MAP_SIZE; + i++, index++) + if (rcu_dereference(node->slots[i]) == NULL) + goto out; + +check_overflow: + if (unlikely(index == 0)) break; } +out: return index; } EXPORT_SYMBOL(radix_tree_next_hole); @@ -686,16 +709,38 @@ EXPORT_SYMBOL(radix_tree_next_hole); unsigned long radix_tree_prev_hole(struct radix_tree_root *root, unsigned long index, unsigned long max_scan) { - unsigned long i; + struct radix_tree_node *node; + unsigned long origin = index; + int i; + + node = rcu_dereference(root->rnode); + if (node == NULL) + return index; + + if (!radix_tree_is_indirect_ptr(node)) + return index ? index : ULONG_MAX; - for (i = 0; i < max_scan; i++) { - if (!radix_tree_lookup(root, index)) + while (origin - index < max_scan) { + node = radix_tree_lookup_leaf_node(root, index); + if (!node) break; - index--; - if (index == LONG_MAX) + + if (node->count == RADIX_TREE_MAP_SIZE) { + index = (index - RADIX_TREE_MAP_SIZE) | + RADIX_TREE_MAP_MASK; + goto check_underflow; + } + + for (i = index & RADIX_TREE_MAP_MASK; i >= 0; i--, index--) + if (rcu_dereference(node->slots[i]) == NULL) + goto out; + +check_underflow: + if (unlikely(index == ULONG_MAX)) break; } +out: return index; } EXPORT_SYMBOL(radix_tree_prev_hole); -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/