The counterpart of radix_tree_next_hole(). To be used by context readahead.
Signed-off-by: Wu Fengguang <[email protected]>
---
include/linux/radix-tree.h | 2 +
lib/radix-tree.c | 37 +++++++++++++++++++++++++++++++++++
2 files changed, 39 insertions(+)
--- mm.orig/lib/radix-tree.c
+++ mm/lib/radix-tree.c
@@ -666,6 +666,43 @@ unsigned long radix_tree_next_hole(struc
}
EXPORT_SYMBOL(radix_tree_next_hole);
+/**
+ * radix_tree_prev_hole - find the prev hole (not-present entry)
+ * @root: tree root
+ * @index: index key
+ * @max_scan: maximum range to search
+ *
+ * Search backwards in the range [max(index-max_scan+1, 0), index]
+ * for the first hole.
+ *
+ * Returns: the index of the hole if found, otherwise returns an index
+ * outside of the set specified (in which case 'index - return >= max_scan'
+ * will be true). In rare cases of wrap-around, LONG_MAX will be returned.
+ *
+ * radix_tree_next_hole may be called under rcu_read_lock. However, like
+ * radix_tree_gang_lookup, this will not atomically search a snapshot of
+ * the tree at a single point in time. For example, if a hole is created
+ * at index 10, then subsequently a hole is created at index 5,
+ * radix_tree_prev_hole covering both indexes may return 5 if called under
+ * rcu_read_lock.
+ */
+unsigned long radix_tree_prev_hole(struct radix_tree_root *root,
+ unsigned long index, unsigned long max_scan)
+{
+ unsigned long i;
+
+ for (i = 0; i < max_scan; i++) {
+ if (!radix_tree_lookup(root, index))
+ break;
+ index--;
+ if (index == LONG_MAX)
+ break;
+ }
+
+ return index;
+}
+EXPORT_SYMBOL(radix_tree_prev_hole);
+
static unsigned int
__lookup(struct radix_tree_node *slot, void ***results, unsigned long index,
unsigned int max_items, unsigned long *next_index)
--- mm.orig/include/linux/radix-tree.h
+++ mm/include/linux/radix-tree.h
@@ -167,6 +167,8 @@ radix_tree_gang_lookup_slot(struct radix
unsigned long first_index, unsigned int max_items);
unsigned long radix_tree_next_hole(struct radix_tree_root *root,
unsigned long index, unsigned long max_scan);
+unsigned long radix_tree_prev_hole(struct radix_tree_root *root,
+ unsigned long index, unsigned long max_scan);
int radix_tree_preload(gfp_t gfp_mask);
void radix_tree_init(void);
void *radix_tree_tag_set(struct radix_tree_root *root,
--
On Sun, 12 Apr 2009 15:19:51 +0800 Wu Fengguang <[email protected]> wrote:
> +unsigned long radix_tree_prev_hole(struct radix_tree_root *root,
> + unsigned long index, unsigned long max_scan)
> +{
> + unsigned long i;
> +
> + for (i = 0; i < max_scan; i++) {
> + if (!radix_tree_lookup(root, index))
> + break;
> + index--;
> + if (index == LONG_MAX)
> + break;
> + }
> +
> + return index;
> +}
argh. This is about as inefficient as we could possibly make it :(
Really, this function should dive into radix-tree internals and walk
individual radix_tree_node.slots[] arrays. And heck, it can peek at
radix_tree_node.count and _bypass_ entire nodes, too.
On Sun, Apr 12, 2009 at 10:29:52AM -0700, Andrew Morton wrote:
> On Sun, 12 Apr 2009 15:19:51 +0800 Wu Fengguang <[email protected]> wrote:
>
> > +unsigned long radix_tree_prev_hole(struct radix_tree_root *root,
> > + unsigned long index, unsigned long max_scan)
> > +{
> > + unsigned long i;
> > +
> > + for (i = 0; i < max_scan; i++) {
> > + if (!radix_tree_lookup(root, index))
> > + break;
> > + index--;
> > + if (index == LONG_MAX)
> > + break;
> > + }
> > +
> > + return index;
> > +}
>
> argh. This is about as inefficient as we could possibly make it :(
Right, a dumb loop!
> Really, this function should dive into radix-tree internals and walk
> individual radix_tree_node.slots[] arrays. And heck, it can peek at
> radix_tree_node.count and _bypass_ entire nodes, too.
Good idea! In fact I'm planning such a smart version. It will be using
radix_tree_lookup_slot() to access the ->count member, in order to
check if the whole slot can be bypassed.
radix_tree_next_hole() is another optimization candidate.
But that will be a post 2.6.30 stuff.
The current dumb-but-obvious-right version is OK for 2.6.30, because
in most radix_tree_prev_hole() invocations the actual loop count will
be merely 1.
Thanks,
Fengguang