Re: [Fwd: Re: + radixtree-look-aside-cache.patch added to -mm tree]

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

On Thu, May 25, 2006 at 03:45:22PM +1000, Nick Piggin wrote:
> >Introduce a set of lookup functions to radix tree for the read-ahead logic.
> >Other access patterns with high locality may also benefit from them.
> >
> 
> Your radix tree stuff doesn't _seem_ like a bad idea, but I would be
> much more comfortable if it was in a completely different patchset.
> Ie. implement your readahead stuff using the current radix-tree API,
> then show eg. 15% CPU reduction on workload X when using look-aside
> cache for blah.
> 
> It is more complexity, and the intention might be nice, but it might
> not actually help as much (or at all) as you think: eg. it might
> increase cache footprint and actually slow things down.

I have oprofile numbers against the look-aside cache:
http://marc.theaimsgroup.com/?l=linux-kernel&m=113231595618167&w=2

Indeed, there's not much gain. It's ok to remove it.

> >
> >- radix_tree_lookup_parent(root, index, level)
> >	Perform partial lookup, return the @level'th parent of the slot at
> >	@index.
> >
> >- radix_tree_cache_xxx()
> >	Init/Query the cache.
> >- radix_tree_cache_lookup(root, cache, index)
> >	Perform lookup with the aid of a look-aside cache.
> >	For sequential scans, it has a time complexity of 64*O(1) + 
> >	1*O(logN).
> >
> >	Typical usage:
> >
> >  void func() {
> > +       struct radix_tree_cache cache;
> > +
> > +       radix_tree_cache_init(&cache);
> >         read_lock_irq(&mapping->tree_lock);
> >         for(;;) {
> > -               page = radix_tree_lookup(&mapping->page_tree, index);
> > +               page = radix_tree_cache_lookup(&mapping->page_tree, 
> > &cache, index);
> >         }
> >         read_unlock_irq(&mapping->tree_lock);
> >  }
> >
> 
> Still not really convinced with this. I can't see why you shouldn't just
> use a gang lookup or "scan" type function. Let's take your real example:
> 
> +static pgoff_t find_segtail_backward(struct address_space *mapping,
> +					pgoff_t index, unsigned long 
> max_scan)
> +{
> +	struct radix_tree_cache cache;
> +	struct page *page;
> +	pgoff_t origin;
> +
> +	origin = index;
> +	if (max_scan > index)
> +		max_scan = index;
> +
> +	cond_resched();
> 
> BTW. cond_resched here? It should normally be in the caller if they expect
> really high latency.

Right, will remove it.

> +	radix_tree_cache_init(&cache);
> +	read_lock_irq(&mapping->tree_lock);
> +	for (; origin - index < max_scan;) {
> +		page = radix_tree_cache_lookup(&mapping->page_tree,
> +							&cache, --index);
> +		if (page) {
> +			read_unlock_irq(&mapping->tree_lock);
> +			return index + 1;
> +		}
> +	}
> +	read_unlock_irq(&mapping->tree_lock);
> 
> 
> This should just be a scan_page_backward (not scan_hole), should it not?
> I didn't find other usages of the radix tree cache after a quick scan, but
> if you point them out, let's see if they can't be replaced with something
> else.

Sure ok. The radix tree cache is trivial to remove.

However this function is not performance critical, so I'd like to
rest on the poor man's scan_page_backward() implementation :)

> >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);
> >+void *radix_tree_lookup_parent(struct radix_tree_root *, unsigned long,
> >+							unsigned int);
> >+void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned 
> >long);
> >void *radix_tree_delete(struct radix_tree_root *, unsigned long);
> >+unsigned int radix_tree_cache_count(struct radix_tree_cache *cache);
> >+void *radix_tree_cache_lookup_parent(struct radix_tree_root *root,
> >+				struct radix_tree_cache *cache,
> >+				unsigned long index, unsigned int level);
> >
> 
> Nitpick: I don't really like the name lookup_parent. No better suggestions
> though ;)
> 
> But the function seems really nasty for an exported API: callers should
> have no concept of the internals of the data structure. If you just need
> it to implement these inline functions, maybe prepend it with a double
> underscore.

It was once named lookup_node, and was distasted by Christoph Lameter.
Maybe we can settle with __radix_tree_lookup_parent() and only use it
inside radix-tree.c/.h.

> >+void *radix_tree_lookup_parent(struct radix_tree_root *root,
> >+				unsigned long index, unsigned int level)
> >{
> >	unsigned int height, shift;
> >-	struct radix_tree_node **slot;
> >+	struct radix_tree_node *slot;
> >
> >	height = root->height;
> >
> >	if (index > radix_tree_maxindex(height))
> >		return NULL;
> >
> >-	if (height == 0 && root->rnode)
> >-		return (void **)&root->rnode;
> >-
> >	shift = (height-1) * RADIX_TREE_MAP_SHIFT;
> >-	slot = &root->rnode;
> >+	slot = root->rnode;
> >
> >
> 
> This couldn't work: we have direct data now in -mm (unless that's been 
> thrown out).

Should be ok: the while loop below will be skipped if height == 0.

> >-	while (height > 0) {
> >-		if (*slot == NULL)
> >+	while (height > level) {
> >+		if (slot == NULL)
> >			return NULL;
> >
> >-		slot = (struct radix_tree_node **)
> >-			((*slot)->slots +
> >-				((index >> shift) & RADIX_TREE_MAP_MASK));
> >+		slot = slot->slots[(index >> shift) & RADIX_TREE_MAP_MASK];
> >		shift -= RADIX_TREE_MAP_SHIFT;
> >		height--;
> >	}
> >
> >-	return (void **)slot;
> >+	return slot;
> >+}

> >+EXPORT_SYMBOL(radix_tree_lookup_parent);
> >void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long 
> >index)
> >{
> >-	return __lookup_slot(root, index);
> >+	struct radix_tree_node *node;
> >+
> >+	node = radix_tree_lookup_parent(root, index, 1);
> >+	return node->slots + (index & RADIX_TREE_MAP_MASK);
> >}
> >EXPORT_SYMBOL(radix_tree_lookup_slot);
> >
> 
> radix_tree_lookup_parent can return NULL, right? Oops.

Thanks, I'm amazed that it didn't crashed my machine ;)

Regards,
Wu