Simplify Radix handling

Step 1

The radix tree stores a pointer and 2 tags per entry. These fit neatly
into a single machine word since pointers are aligned to 4 byte boundaries.
This makes the lowest bits always zero. Thus we can stuff the tags in there
eliminating the tags and simplifying the algorithms.

Step 2

The size of the radix tree is 2^RADIX_TREE_MAP_SHIFT plus a 32 bit count.
If this word is removed then the radix tree could have a size of 2^X which
is easier to manage

Index: linux-2.6.13-rc6-mm2/lib/radix-tree.c
===================================================================
--- linux-2.6.13-rc6-mm2.orig/lib/radix-tree.c	2005-08-24 16:57:42.000000000 -0700
+++ linux-2.6.13-rc6-mm2/lib/radix-tree.c	2005-08-25 17:14:15.000000000 -0700
@@ -32,24 +32,35 @@
 
 
 #ifdef __KERNEL__
-#define RADIX_TREE_MAP_SHIFT	6
+/* For IA64 16k/8 = 2048 = 11 */
+#define RADIX_TREE_MAP_SHIFT	11
 #else
 #define RADIX_TREE_MAP_SHIFT	3	/* For more stressful testing */
 #endif
 #define RADIX_TREE_TAGS		2
 
 #define RADIX_TREE_MAP_SIZE	(1UL << RADIX_TREE_MAP_SHIFT)
+/* = 1024 */
 #define RADIX_TREE_MAP_MASK	(RADIX_TREE_MAP_SIZE-1)
 
 #define RADIX_TREE_TAG_LONGS	\
 	((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)
+/* = 1024 / 8 = 128 */
 
 struct radix_tree_node {
-	unsigned int	count;
 	void		*slots[RADIX_TREE_MAP_SIZE];
-	unsigned long	tags[RADIX_TREE_TAGS][RADIX_TREE_TAG_LONGS];
 };
 
+static inline int get_tag(struct radix_tree_node *x, int nr, int tagnr)
+{
+	return ((x->slots[nr] << targnr) & 1)
+}
+
+static inline void * get_pointer(struct radix_tree_node *x, int nr)
+{
+	return (void *)((unsigned long)(x->slots[nr]) & ~0x3);
+}
+
 struct radix_tree_path {
 	struct radix_tree_node *node, **slot;
 	int offset;
@@ -61,11 +72,6 @@ struct radix_tree_path {
 static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH] __read_mostly;
 
 /*
- * Radix tree node cache.
- */
-static kmem_cache_t *radix_tree_node_cachep;
-
-/*
  * Per-cpu pool of preloaded nodes
  */
 struct radix_tree_preload {
@@ -83,7 +89,7 @@ radix_tree_node_alloc(struct radix_tree_
 {
 	struct radix_tree_node *ret;
 
-	ret = kmem_cache_alloc(radix_tree_node_cachep, root->gfp_mask);
+	ret = (struct radix_tree_node *) alloc_pages(root->gfp_mask, 0);
 	if (ret == NULL && !(root->gfp_mask & __GFP_WAIT)) {
 		struct radix_tree_preload *rtp;
 
@@ -94,13 +100,15 @@ radix_tree_node_alloc(struct radix_tree_
 			rtp->nr--;
 		}
 	}
+	if (ret)
+		memset(ret, 0, sizeof(struct radix_tree_node));
 	return ret;
 }
 
 static inline void
 radix_tree_node_free(struct radix_tree_node *node)
 {
-	kmem_cache_free(radix_tree_node_cachep, node);
+	free_pages((unsigned long)node, 0);
 }
 
 /*
@@ -119,7 +127,7 @@ int radix_tree_preload(unsigned int __no
 	rtp = &__get_cpu_var(radix_tree_preloads);
 	while (rtp->nr < ARRAY_SIZE(rtp->nodes)) {
 		preempt_enable();
-		node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
+		node = (struct radix_tree_node) alloc_pages(gfp_mask, 0);
 		if (node == NULL)
 			goto out;
 		preempt_disable();
@@ -127,7 +135,7 @@ int radix_tree_preload(unsigned int __no
 		if (rtp->nr < ARRAY_SIZE(rtp->nodes))
 			rtp->nodes[rtp->nr++] = node;
 		else
-			kmem_cache_free(radix_tree_node_cachep, node);
+			free_pages((unsigned long)node);
 	}
 	ret = 0;
 out:
@@ -137,18 +145,18 @@ EXPORT_SYMBOL(radix_tree_preload);
 
 static inline void tag_set(struct radix_tree_node *node, int tag, int offset)
 {
-	if (!test_bit(offset, &node->tags[tag][0]))
-		__set_bit(offset, &node->tags[tag][0]);
+	if (!test_bit(1 << tag, &node->slots[offset]))
+		__set_bit(1 << tag, &node->slots[offset]);
 }
 
 static inline void tag_clear(struct radix_tree_node *node, int tag, int offset)
 {
-	__clear_bit(offset, &node->tags[tag][0]);
+	__clear_bit(1 << tag, &node->slots[offset]);
 }
 
 static inline int tag_get(struct radix_tree_node *node, int tag, int offset)
 {
-	return test_bit(offset, &node->tags[tag][0]);
+	return ((node->slots[offset] << tag) & 1)
 }
 
 /*
@@ -209,7 +217,6 @@ static int radix_tree_extend(struct radi
 				tag_set(node, tag, 0);
 		}
 
-		node->count = 1;
 		root->rnode = node;
 		root->height++;
 	} while (height > root->height);
@@ -252,8 +259,6 @@ int radix_tree_insert(struct radix_tree_
 			if (!(tmp = radix_tree_node_alloc(root)))
 				return -ENOMEM;
 			*slot = tmp;
-			if (node)
-				node->count++;
 		}
 
 		/* Go a level down */
@@ -267,7 +272,6 @@ int radix_tree_insert(struct radix_tree_
 	if (*slot != NULL)
 		return -EEXIST;
 	if (node) {
-		node->count++;
 		BUG_ON(tag_get(node, 0, offset));
 		BUG_ON(tag_get(node, 1, offset));
 	}
@@ -744,7 +748,7 @@ void *radix_tree_delete(struct radix_tre
 
 	pathp = orig_pathp;
 	*pathp[0].slot = NULL;
-	while (pathp[0].node && --pathp[0].node->count == 0) {
+	while (pathp[0].node && cacheline_zero(pathp[0].slot) && page_zero(pathp[0].node)) {
 		pathp--;
 		BUG_ON(*pathp[0].slot == NULL);
 		*pathp[0].slot = NULL;
@@ -776,12 +780,6 @@ int radix_tree_tagged(struct radix_tree_
 }
 EXPORT_SYMBOL(radix_tree_tagged);
 
-static void
-radix_tree_node_ctor(void *node, kmem_cache_t *cachep, unsigned long flags)
-{
-	memset(node, 0, sizeof(struct radix_tree_node));
-}
-
 static __init unsigned long __maxindex(unsigned int height)
 {
 	unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
@@ -824,9 +822,6 @@ static int radix_tree_callback(struct no
 
 void __init radix_tree_init(void)
 {
-	radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
-			sizeof(struct radix_tree_node), 0,
-			SLAB_PANIC, radix_tree_node_ctor, NULL);
 	radix_tree_init_maxindex();
 	hotcpu_notifier(radix_tree_callback, 0);
 }