lkml.org 
[lkml]   [2010]   [Feb]   [23]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    Date
    From
    Subject[PATCH 13/15] radixtree: speed up the search for hole
    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 <nickpiggin@yahoo.com.au>
    Signed-off-by: Wu Fengguang <fengguang.wu@intel.com>
    ---
    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);



    \
     
     \ /
      Last update: 2010-02-24 04:15    [W:4.020 / U:0.024 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site