Skip to contentSkip to conversation

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

Fwd: Re: + radixtree-look-aside-cache.patch added to -mm tree Nick Piggin 2 participants 2 messages May 25, 2006

lore
Share & tools
lore
#0 lore raw

Hmm, this didn't get to lkml. Sorry 'bout that.

-------- Original Message --------
Subject: Re: + radixtree-look-aside-cache.patch added to -mm tree
Date: Thu, 25 May 2006 15:18:07 +1000
From: Nick Piggin <[email protected]>
To: [email protected]
CC: [email protected], [email protected]
References: <[email protected]>

Quoted 11 lines · [email protected] wrote:

The patch titled

radixtree: look-aside cache

has been added to the -mm tree. Its filename is

radixtree-look-aside-cache.patch

See http://www.zip.com.au/~akpm/linux/patches/stuff/added-to-mm.txt to find out what to do about this

Quoted 8 lines

------------------------------------------------------
Subject: radixtree: look-aside cache
From: Wu Fengguang <[email protected]>

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.

[edit] there are a couple of bugs in the patch itself, too (see below)

Quoted 16 lines

- 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;
+

Quoted 9 lines
 +       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.

+ 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.

Quoted 3 lines

Can't remember if I exactly acked it, but stuff has changed a bit, so it is a nack for the moment ;)

Quoted 47 lines

---

include/linux/radix-tree.h | 83 +++++++++++++++++++++++++++
lib/radix-tree.c | 104 ++++++++++++++++++++++++++---------

2 files changed, 161 insertions(+), 26 deletions(-)

diff -puN include/linux/radix-tree.h~radixtree-look-aside-cache include/linux/radix-tree.h

include/linux/radix-tree.h renamed from include/linux/radix-tree.h~radixtree-look-aside-cache +17 -1
@@ -26,12 +26,29 @@
 #define RADIX_TREE_MAX_TAGS 2
 
 /* root tags are stored in gfp_mask, shifted by __GFP_BITS_SHIFT */
+#ifdef __KERNEL__
+#define RADIX_TREE_MAP_SHIFT	(CONFIG_BASE_SMALL ? 4 : 6)
+#else
+#define RADIX_TREE_MAP_SHIFT	3	/* For more stressful testing */
+#endif
+
+#define RADIX_TREE_MAP_SIZE	(1UL << RADIX_TREE_MAP_SHIFT)
+#define RADIX_TREE_MAP_MASK	(RADIX_TREE_MAP_SIZE-1)
+
 struct radix_tree_root {
 	unsigned int		height;
 	gfp_t			gfp_mask;
 	struct radix_tree_node	*rnode;
 };
 
+/*
+ * Lookaside cache to support access patterns with strong locality.
+ */
+struct radix_tree_cache {
+	unsigned long first_index;
+	struct radix_tree_node *tree_node;
+};
+
 #define RADIX_TREE_INIT(mask)	{					\
 	.height = 0,							\
 	.gfp_mask = (mask),						\
@@ -49,9 +66,14 @@ do {									\
 } while (0)
 
 int radix_tree_insert(struct radix_tree_root *, unsigned long, void *);
-void *radix_tree_lookup(struct radix_tree_root *, unsigned long);

include/linux/radix-tree.h do { \ · line 77

Quoted 10 lines
include/linux/radix-tree.h renamed from include/linux/radix-tree.h~radixtree-look-aside-cache +7 -1
-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.

Quoted 33 lines

diff -puN lib/radix-tree.c~radixtree-look-aside-cache lib/radix-tree.c

lib/radix-tree.c renamed from lib/radix-tree.c~radixtree-look-aside-cache +17 -3
@@ -308,36 +308,90 @@ int radix_tree_insert(struct radix_tree_
 }
 EXPORT_SYMBOL(radix_tree_insert);
 
-static inline void **__lookup_slot(struct radix_tree_root *root,
-				   unsigned long index)
+/**
+ *	radix_tree_lookup_parent    -    low level lookup routine
+ *	@root:		radix tree root
+ *	@index:		index key
+ *	@level:		stop at that many levels from the tree leaf
+ *
+ *	Lookup the @level'th parent of the slot at @index in radix tree @root.
+ *	The return value is:
+ *	@level == 0:      page at @index;
+ *	@level == 1:      the corresponding bottom level tree node;
+ *	@level < height:  (@level-1)th parent node of the bottom node
+ *			  that contains @index;
+ *	@level >= height: the root node.
+ */
+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))

lib/radix-tree.c int radix_tree_insert(struct radix_tree_ · line 339

Quoted 10 lines
lib/radix-tree.c renamed from lib/radix-tree.c~radixtree-look-aside-cache +1 -4
 		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).

Quoted 67 lines
lib/radix-tree.c renamed from lib/radix-tree.c~radixtree-look-aside-cache +49 -6
-	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);
+
+/**
+ *	radix_tree_cache_lookup_parent    -    cached lookup node
+ *	@root:		radix tree root
+ *	@cache:		look-aside cache
+ *	@index:		index key
+ *
+ *	Lookup the item at the position @index in the radix tree @root,
+ *	and return the node @level levels from the bottom in the search path.
+ *
+ *	@cache stores the last accessed upper level tree node by this
+ *	function, and is always checked first before searching in the tree.
+ *	It can improve speed for access patterns with strong locality.
+ *
+ *	NOTE:
+ *	- The cache becomes invalid on leaving the lock;
+ *	- Do not intermix calls with different @level.
+ */
+void *radix_tree_cache_lookup_parent(struct radix_tree_root *root,
+				struct radix_tree_cache *cache,
+				unsigned long index, unsigned int level)
+{
+	struct radix_tree_node *node;
+        unsigned long i;
+        unsigned long mask;
+
+        if (level >= root->height)
+                return radix_tree_lookup_parent(root, index, level);
+
+        i = (index >> (level * RADIX_TREE_MAP_SHIFT)) & RADIX_TREE_MAP_MASK;
+        mask = (~0UL) << ((level + 1) * RADIX_TREE_MAP_SHIFT);
+
+	if ((index & mask) == cache->first_index)
+                return cache->tree_node->slots[i];
+
+	node = radix_tree_lookup_parent(root, index, level + 1);
+	if (!node)
+		return 0;
+
+	cache->tree_node = node;
+	cache->first_index = (index & mask);
+        return node->slots[i];
 }
+EXPORT_SYMBOL(radix_tree_cache_lookup_parent);
 
 /**

* radix_tree_lookup_slot - lookup a slot in a radix tree

lib/radix-tree.c renamed from lib/radix-tree.c~radixtree-look-aside-cache +0 -0
@@ -349,25 +403,27 @@ static inline void **__lookup_slot(struc
 */

lib/radix-tree.c static inline void **__lookup_slot(struc · line 412

Quoted 10 lines
lib/radix-tree.c renamed from lib/radix-tree.c~radixtree-look-aside-cache +4 -1
 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.

Send instant messages to your online friends http://au.messenger.yahoo.com

#1 lore raw
Quoted 10 lines · Nick Piggin
Quoted 3 lines

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.

Quoted 3 lines

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.

Quoted 45 lines
Quoted 25 lines

- 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() {

(quoted diff) +4 -1
+       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);
Quoted 2 lines

}

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:

(quoted diff) +2 -0
+static pgoff_t find_segtail_backward(struct address_space *mapping,
+					pgoff_t index, unsigned long 

max_scan)

(quoted diff) +10 -0
+{
+	struct radix_tree_cache cache;
+	struct page *page;
+	pgoff_t origin;
+
+	origin = index;
+	if (max_scan > index)
+		max_scan = index;
+
+	cond_resched();
Quoted 2 lines

BTW. cond_resched here? It should normally be in the caller if they expect really high latency.

Right, will remove it.

Quoted 13 lines
(quoted diff) +11 -0
+	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);
Quoted 4 lines

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 :)

Quoted 17 lines

Review

Quoted 13 lines

int radix_tree_insert(struct radix_tree_root *, unsigned long, void *);

(quoted diff) +3 -2
-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);

(quoted diff) +4 -0
+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 ;)

Quoted 4 lines

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.

Quoted 12 lines
Quoted 12 lines
(quoted diff) +2 -0
+void *radix_tree_lookup_parent(struct radix_tree_root *root,
+				unsigned long index, unsigned int level)
{
	unsigned int height, shift;
(quoted diff) +1 -1
-	struct radix_tree_node **slot;
+	struct radix_tree_node *slot;
	height = root->height;

	if (index > radix_tree_maxindex(height))
		return NULL;
Quoted 11 lines

Review

Quoted 8 lines
(quoted diff) +0 -3
-	if (height == 0 && root->rnode)
-		return (void **)&root->rnode;
-
	shift = (height-1) * RADIX_TREE_MAP_SHIFT;
(quoted diff) +1 -1
-	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.

Quoted 18 lines
Quoted 17 lines
(quoted diff) +2 -2
-	while (height > 0) {
-		if (*slot == NULL)
+	while (height > level) {
+		if (slot == NULL)
			return NULL;
(quoted diff) +1 -3
-		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--;
	}
(quoted diff) +2 -1
-	return (void **)slot;
+	return slot;
+}
Quoted 14 lines
Quoted 9 lines

+EXPORT_SYMBOL(radix_tree_lookup_parent);
void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
{

(quoted diff) +4 -1
-	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);
Quoted 3 lines

}
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