[PATCH] radix-tree tags for selective lookup

Add radix-tree tagging so we can look up dirty or writeback pages in
O(log64(n)) time.

Each radix-tree node gains two bits for each slot: one for page dirtiness and
one for page writebackness.

If a tag bit is set on a leaf node, it indicates that item at the
corresponding slot is tagged (say, a dirty page).

If a tag bit is set in a non-leaf node it indicates that the same tag bit is
set in the subtree which lies under the corresponding slot.  ie: "there is a
dirty page under here somewhere, but you need to search down further to find
it".

A gang lookup function is provided which can walk the radix tree in
logarithmic time looking for items which are tagged, starting from a
specified offset.  We use this for in-order searches for dirty or writeback
pages.

There is a userspace test harness for this code at

http://www.zip.com.au/~akpm/linux/patches/stuff/rtth.tar.gz

1 files changed, 26 insertions, 12 deletions

diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index c32a45fd1f0d..8081a281fa5e 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -20,8 +20,7 @@
 #define _LINUX_RADIX_TREE_H
 
 #include <linux/preempt.h>
-
-struct radix_tree_node;
+#include <linux/types.h>
 
 struct radix_tree_root {
 	unsigned int		height;
@@ -29,25 +28,40 @@ struct radix_tree_root {
 	struct radix_tree_node	*rnode;
 };
 
-#define RADIX_TREE_INIT(mask)	{0, (mask), NULL}
+#define RADIX_TREE_INIT(mask)	{					\
+	.height = 0,							\
+	.gfp_mask = (mask),						\
+	.rnode = NULL,							\
+}
 
 #define RADIX_TREE(name, mask) \
 	struct radix_tree_root name = RADIX_TREE_INIT(mask)
 
-#define INIT_RADIX_TREE(root, mask)	\
-do {					\
-	(root)->height = 0;		\
-	(root)->gfp_mask = (mask);	\
-	(root)->rnode = NULL;		\
+#define INIT_RADIX_TREE(root, mask)					\
+do {									\
+	(root)->height = 0;						\
+	(root)->gfp_mask = (mask);					\
+	(root)->rnode = NULL;						\
 } while (0)
 
-extern int radix_tree_insert(struct radix_tree_root *, unsigned long, void *);
-extern void *radix_tree_lookup(struct radix_tree_root *, unsigned long);
-extern void *radix_tree_delete(struct radix_tree_root *, unsigned long);
-extern unsigned int
+int radix_tree_insert(struct radix_tree_root *, unsigned long, void *);
+void *radix_tree_lookup(struct radix_tree_root *, unsigned long);
+void *radix_tree_delete(struct radix_tree_root *, unsigned long);
+unsigned int
 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
 			unsigned long first_index, unsigned int max_items);
 int radix_tree_preload(int gfp_mask);
+void radix_tree_init(void);
+void *radix_tree_tag_set(struct radix_tree_root *root,
+			unsigned long index, int tag);
+void *radix_tree_tag_clear(struct radix_tree_root *root,
+			unsigned long index, int tag);
+int radix_tree_tag_get(struct radix_tree_root *root,
+			unsigned long index, int tag);
+unsigned int
+radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
+		unsigned long first_index, unsigned int max_items, int tag);
+int radix_tree_tagged(struct radix_tree_root *root, int tag);
 
 static inline void radix_tree_preload_end(void)
 {