[Fwd: Re: + radixtree-look-aside-cache.patch added to -mm tree]
From: Nick Piggin
Date: Thu May 25 2006 - 01:44:37 EST
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 <nickpiggin@xxxxxxxxxxxx>
To: akpm@xxxxxxxx
CC: wfg@xxxxxxxxxxxxxxxx, clameter@xxxxxxx
References: <200605242345.k4ONjqnE004454@xxxxxxxxxxxxxxxxxxx>
akpm@xxxxxxxx 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
------------------------------------------------------
Subject: radixtree: look-aside cache
From: Wu Fengguang <wfg@xxxxxxxxxxxxxxxx>
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)
- 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.
+ 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.
Acked-by: Nick Piggin <nickpiggin@xxxxxxxxxxxx>
Can't remember if I exactly acked it, but stuff has changed a bit, so it is
a nack for the moment ;)
Signed-off-by: Christoph Lameter <clameter@xxxxxxx>
Signed-off-by: Wu Fengguang <wfg@xxxxxxxxxxxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxx>
---
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
--- 25/include/linux/radix-tree.h~radixtree-look-aside-cache Wed May 24 16:48:44 2006
+++ 25-akpm/include/linux/radix-tree.h Wed May 24 16:48:44 2006
@@ -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);
-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.
diff -puN lib/radix-tree.c~radixtree-look-aside-cache lib/radix-tree.c
--- 25/lib/radix-tree.c~radixtree-look-aside-cache Wed May 24 16:48:44 2006
+++ 25-akpm/lib/radix-tree.c Wed May 24 16:48:44 2006
@@ -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))
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).
- 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
@@ -349,25 +403,27 @@ static inline void **__lookup_slot(struc
*/
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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/