lkml.org 
[lkml]   [2010]   [Mar]   [1]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
From
Subject[PATCH 13/16] radixtree: introduce radix_tree_lookup_leaf_node()
This will be used by the pagecache context based read-ahead/read-around
heuristic to quickly check one pagecache range:
- if there is any hole
- if there is any pages

Cc: Nick Piggin <nickpiggin@yahoo.com.au>
Acked-by: Rik van Riel <riel@redhat.com>
Signed-off-by: Wu Fengguang <fengguang.wu@intel.com>
---
include/linux/radix-tree.h | 2 +
lib/radix-tree.c | 37 ++++++++++++++++++++++++++---------
2 files changed, 30 insertions(+), 9 deletions(-)

--- linux.orig/lib/radix-tree.c 2010-02-27 12:59:22.000000000 +0800
+++ linux/lib/radix-tree.c 2010-02-27 13:00:09.000000000 +0800
@@ -359,19 +359,20 @@ EXPORT_SYMBOL(radix_tree_insert);
* is_slot == 0 : search for the node.
*/
static void *radix_tree_lookup_element(struct radix_tree_root *root,
- unsigned long index, int is_slot)
+ unsigned long index, int is_slot, int level)
{
unsigned int height, shift;
- struct radix_tree_node *node, **slot;
+ struct radix_tree_node *node;
+ struct radix_tree_node **slot = &root->rnode;

node = rcu_dereference(root->rnode);
if (node == NULL)
return NULL;

if (!radix_tree_is_indirect_ptr(node)) {
- if (index > 0)
+ if (index > 0 || level > 0)
return NULL;
- return is_slot ? (void *)&root->rnode : node;
+ goto out;
}
node = radix_tree_indirect_to_ptr(node);

@@ -381,7 +382,7 @@ static void *radix_tree_lookup_element(s

shift = (height-1) * RADIX_TREE_MAP_SHIFT;

- do {
+ while (height > level) {
slot = (struct radix_tree_node **)
(node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK));
node = rcu_dereference(*slot);
@@ -390,9 +391,10 @@ static void *radix_tree_lookup_element(s

shift -= RADIX_TREE_MAP_SHIFT;
height--;
- } while (height > 0);
+ }

- return is_slot ? (void *)slot:node;
+out:
+ return is_slot ? (void *)slot : node;
}

/**
@@ -410,7 +412,7 @@ static void *radix_tree_lookup_element(s
*/
void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
{
- return (void **)radix_tree_lookup_element(root, index, 1);
+ return (void **)radix_tree_lookup_element(root, index, 1, 0);
}
EXPORT_SYMBOL(radix_tree_lookup_slot);

@@ -428,11 +430,28 @@ EXPORT_SYMBOL(radix_tree_lookup_slot);
*/
void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
{
- return radix_tree_lookup_element(root, index, 0);
+ return radix_tree_lookup_element(root, index, 0, 0);
}
EXPORT_SYMBOL(radix_tree_lookup);

/**
+ * radix_tree_lookup_leaf_node - lookup leaf node on a radix tree
+ * @root: radix tree root
+ * @index: index key
+ *
+ * Lookup the leaf node that covers @index in the radix tree @root.
+ * Return NULL if the node does not exist, or is the special root node.
+ *
+ * The typical usage is to check the value of node->count, which shall be
+ * performed inside rcu_read_lock to prevent the node from being freed.
+ */
+struct radix_tree_node *
+radix_tree_lookup_leaf_node(struct radix_tree_root *root, unsigned long index)
+{
+ return radix_tree_lookup_element(root, index, 0, 1);
+}
+
+/**
* radix_tree_tag_set - set a tag on a radix tree node
* @root: radix tree root
* @index: index key
--- linux.orig/include/linux/radix-tree.h 2010-02-27 12:59:22.000000000 +0800
+++ linux/include/linux/radix-tree.h 2010-02-27 12:59:23.000000000 +0800
@@ -158,6 +158,8 @@ static inline void radix_tree_replace_sl
int radix_tree_insert(struct radix_tree_root *, unsigned long, void *);
void *radix_tree_lookup(struct radix_tree_root *, unsigned long);
void **radix_tree_lookup_slot(struct radix_tree_root *, unsigned long);
+struct radix_tree_node *
+radix_tree_lookup_leaf_node(struct radix_tree_root *root, unsigned long index);
void *radix_tree_delete(struct radix_tree_root *, unsigned long);
unsigned int
radix_tree_gang_lookup(struct radix_tree_root *root, void **results,



\
 
 \ /
  Last update: 2010-03-01 06:41    [W:0.078 / U:0.328 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site