Re: [PATCH 02/23] radixtree: look-aside cache

[Wu Fengguang <wfg@mail.ustc.edu.cn>]

On Mon, Mar 20, 2006 at 08:01:01AM -0800, Christoph Lameter wrote:
> On Sun, 19 Mar 2006, Wu Fengguang wrote:
> 
> > Signed-off-by: Christoph Lameter <clameter@sgi.com>
> 
> Hmm... This signoff exists because you are using some bit of earlier 
> patches by me?

Yes, the __lookup_slot() part of your patch named
        [PATCH] radix-tree: Remove unnecessary indirections and clean up code
is integrated into this patch, for Andrew found that it simply cannot be a
standalone patch:
        http://www.ussg.iu.edu/hypermail/linux/kernel/0512.0/0922.html

> Typically the _node endings mean that one can specify a node number where 
> to allocate memory.

Ah, I named it _node for this function is a generalized radix_tree_lookup().
The main difference is that radix_tree_lookup() returns the data in leaf node,
whereas radix_tree_lookup_node() returns the data or one of its parent nodes.

If _node is a misleading name, will _parent or _level do the job?

> Wont partial lookups like this complicate further work on the radixtree? 

Yes the new function is a bit of confusing ;)
But the change of code is minimal. Conceptually it works as follows:

-void *radix_tree_lookup(struct radix_tree_root *root,
-                               unsigned long index)                                              
+void *radix_tree_lookup_node(struct radix_tree_root *root,
+                               unsigned long index, unsigned int level)
 {
        unsigned int height, shift;
        struct radix_tree_node *slot;
@@ -300,7 +304,7 @@ static inline void **__lookup_slot(struc
        shift = (height-1) * RADIX_TREE_MAP_SHIFT;
        slot = root->rnode;

-       while (height > 0) {
+       while (height > level) {
                if (slot == NULL)
                        return NULL;

The main concern might be Nick's RCU patch. Since this function or
the look-aside cache concept do not collide with RCU's basic
assumptions, the impact should be minimal.

> Could you  get your speed optimizations into radixtree.c so that others 
> can use it in the future?

Sure.
There are three set of optimized functions that can be used by others:

- radix_tree_lookup_node(): used by the radix tree look-aside cache
                            code and context based read-ahead.
- radix_tree_cache_lookup()/radix_tree_cache_lookup_node():
- radix_tree_scan_hole()/radix_tree_scan_hole_backward():
  currently only used by context based read-ahead.

In the future I'd like to introduce a new function named
radix_tree_scan_data() to replace __lookup(), and rebase
radix_tree_gang_lookup() on it.

This change makes possible for a better __do_page_cache_readahead()
implementation based on radix_tree_scan_hole()/radix_tree_scan_data().

Cheers,
Wu