2.6.17 radix-tree: updates and lockless

Make radix tree lookups safe to be performed without locks. Readers are protected against nodes being deleted by using RCU based freeing. Readers are protected against new node insertion by using memory barriers to ensure the node itself will be properly written before it is visible in the radix tree.

Each radix tree node keeps a record of their height (above leaf nodes). This height does not change after insertion -- when the radix tree is extended, higher nodes are only inserted in the top. So a lookup can take the pointer to what is *now* the root node, and traverse down it even if the tree is concurrently extended and this node becomes a subtree of a new root.

"Direct" pointers (tree height of 0, where root->rnode points directly to the data item) are handled by using the low bit of the pointer to signal whether rnode is a direct pointer or a pointer to a radix tree node.

When a reader wants to traverse the next branch, they will take a copy of the pointer. This pointer will be either NULL (and the branch is empty) or non-NULL (and will point to a valid node).

Signed-off-by Nick Piggin <[email protected]>

Index: linux-2.6/lib/radix-tree.c
===================================================================

lib/radix-tree.c +36 -10

@@ -30,6 +30,7 @@
 #include <linux/gfp.h>
 #include <linux/string.h>
 #include <linux/bitops.h>
+#include <linux/rcupdate.h>
 
 
 #ifdef __KERNEL__

@@ -45,7 +46,9 @@
 	((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)
 
 struct radix_tree_node {
+	unsigned int	height;		/* Height from the bottom */
 	unsigned int	count;
+	struct rcu_head	rcu_head;
 	void		*slots[RADIX_TREE_MAP_SIZE];
 	unsigned long	tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
 };

@@ -100,13 +103,21 @@ radix_tree_node_alloc(struct radix_tree_
 			rtp->nr--;
 		}
 	}
+	BUG_ON(radix_tree_is_direct_ptr(ret));
 	return ret;
 }
 
+static void radix_tree_node_rcu_free(struct rcu_head *head)
+{
+	struct radix_tree_node *node =
+			container_of(head, struct radix_tree_node, rcu_head);
+	kmem_cache_free(radix_tree_node_cachep, node);
+}
+
 static inline void
 radix_tree_node_free(struct radix_tree_node *node)
 {
-	kmem_cache_free(radix_tree_node_cachep, node);
+	call_rcu(&node->rcu_head, radix_tree_node_rcu_free);
 }
 
 /*

@@ -222,11 +233,12 @@ static int radix_tree_extend(struct radi
 	}
 
 	do {
+		unsigned int newheight;
 		if (!(node = radix_tree_node_alloc(root)))
 			return -ENOMEM;
 
 		/* Increase the height.  */
-		node->slots[0] = root->rnode;
+		node->slots[0] = radix_tree_direct_to_ptr(root->rnode);
 
 		/* Propagate the aggregated tag info into the new root */
 		for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {

@@ -234,9 +246,11 @@ static int radix_tree_extend(struct radi
 				tag_set(node, tag, 0);
 		}
 
+		newheight = root->height+1;
+		node->height = newheight;
 		node->count = 1;
-		root->rnode = node;
-		root->height++;
+		rcu_assign_pointer(root->rnode, node);
+		root->height = newheight;
 	} while (height > root->height);
 out:
 	return 0;

@@ -258,6 +272,8 @@ int radix_tree_insert(struct radix_tree_
 	int offset;
 	int error;
 
+	BUG_ON(radix_tree_is_direct_ptr(item));
+
 	/* Make sure the tree is high enough.  */
 	if (index > radix_tree_maxindex(root->height)) {
 		error = radix_tree_extend(root, index);

@@ -275,11 +291,12 @@ int radix_tree_insert(struct radix_tree_
 			/* Have to add a child node.  */
 			if (!(slot = radix_tree_node_alloc(root)))
 				return -ENOMEM;
+			slot->height = height;
 			if (node) {
-				node->slots[offset] = slot;
+				rcu_assign_pointer(node->slots[offset], slot);
 				node->count++;
 			} else
-				root->rnode = slot;
+				rcu_assign_pointer(root->rnode, slot);
 		}
 
 		/* Go a level down */

@@ -295,11 +312,11 @@ int radix_tree_insert(struct radix_tree_
 
 	if (node) {
 		node->count++;
-		node->slots[offset] = item;
+		rcu_assign_pointer(node->slots[offset], item);
 		BUG_ON(tag_get(node, 0, offset));
 		BUG_ON(tag_get(node, 1, offset));
 	} else {
-		root->rnode = item;
+		rcu_assign_pointer(root->rnode, radix_tree_ptr_to_direct(item));
 		BUG_ON(root_tag_get(root, 0));
 		BUG_ON(root_tag_get(root, 1));
 	}

@@ -308,49 +325,51 @@ 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_slot    -    lookup a slot in a radix tree
+ *	@root:		radix tree root
+ *	@index:		index key
+ *
+ *	Lookup the slot corresponding to the position @index in the radix tree
+ *	@root. This is useful for update-if-exists operations.
+ *
+ *	This function cannot be called under rcu_read_lock, it must be
+ *	excluded from writers, as must the returned slot.
+ */

lib/radix-tree.c +9 -1

+	if (node == NULL)
 		return NULL;
 
-	if (height == 0 && root->rnode)
+	if (radix_tree_is_direct_ptr(node)) {
+		if (index > 0)
+			return NULL;
 		return (void **)&root->rnode;
+	}
+
+	height = node->height;
+	if (index > radix_tree_maxindex(height))
+		return NULL;

lib/radix-tree.c +30 -20

+		if (node == NULL)
 			return NULL;
 
-		slot = (struct radix_tree_node **)
-			((*slot)->slots +
-				((index >> shift) & RADIX_TREE_MAP_MASK));
 		shift -= RADIX_TREE_MAP_SHIFT;
 		height--;
-	}
+	} while (height > 0);
 
 	return (void **)slot;
 }
-
-/**
- *	radix_tree_lookup_slot    -    lookup a slot in a radix tree
- *	@root:		radix tree root
- *	@index:		index key
- *
- *	Lookup the slot corresponding to the position @index in the radix tree
- *	@root. This is useful for update-if-exists operations.
- */
-void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
-{
-	return __lookup_slot(root, index);
-}
 EXPORT_SYMBOL(radix_tree_lookup_slot);
 
 /**

@@ -359,13 +378,45 @@ EXPORT_SYMBOL(radix_tree_lookup_slot);
  *	@index:		index key
  *
  *	Lookup the item at the position @index in the radix tree @root.
+ *
+ *	This function can be called under rcu_read_lock, however the caller
+ *	must manage lifetimes of leaf nodes (eg. RCU may also be used to free
+ *	them safely). No RCU barriers are required to access or modify the
+ *	returned item, however.
  */
 void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
 {
-	void **slot;
+	unsigned int height, shift;
+	struct radix_tree_node *node, **slot;
+
+	node = rcu_dereference(root->rnode);
+	if (node == NULL)
+		return NULL;
+
+	if (radix_tree_is_direct_ptr(node)) {
+		if (index > 0)
+			return NULL;
+		return radix_tree_direct_to_ptr(node);
+	}
+
+	height = node->height;
+	if (index > radix_tree_maxindex(height))
+		return NULL;
 
-	slot = __lookup_slot(root, index);
-	return slot != NULL ? *slot : NULL;
+	shift = (height-1) * RADIX_TREE_MAP_SHIFT;
+
+	do {
+		slot = (struct radix_tree_node **)
+			(node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK));
+		node = rcu_dereference(*slot);
+		if (node == NULL)

lib/radix-tree.c +43 -27

 	unsigned int nr_found = 0;
 	unsigned int shift, height;
-	struct radix_tree_node *slot;
 	unsigned long i;
 
-	height = root->height;
-	if (height == 0) {
-		if (root->rnode && index == 0)
-			results[nr_found++] = root->rnode;
+	height = slot->height;
+	if (height == 0)
 		goto out;
-	}
-
 	shift = (height-1) * RADIX_TREE_MAP_SHIFT;
-	slot = root->rnode;
 
 	for ( ; height > 1; height--) {
+		struct radix_tree_node *__s;
 
 		for (i = (index >> shift) & RADIX_TREE_MAP_MASK ;
 				i < RADIX_TREE_MAP_SIZE; i++) {
-			if (slot->slots[i] != NULL)
+			__s = rcu_dereference(slot->slots[i]);
+			if (__s != NULL)
 				break;
 			index &= ~((1UL << shift) - 1);
 			index += 1UL << shift;

@@ -575,14 +622,16 @@ __lookup(struct radix_tree_root *root, v
 			goto out;
 
 		shift -= RADIX_TREE_MAP_SHIFT;
-		slot = slot->slots[i];
+		slot = __s;
 	}
 
 	/* Bottom level: grab some items */
 	for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) {
+		struct radix_tree_node *node;
 		index++;
-		if (slot->slots[i]) {
-			results[nr_found++] = slot->slots[i];
+		node = slot->slots[i];
+		if (node) {
+			results[nr_found++] = node;
 			if (nr_found == max_items)
 				goto out;
 		}

@@ -604,28 +653,54 @@ out:
  *	*@results.
  *
  *	The implementation is naive.
+ *
+ *	Like radix_tree_lookup, radix_tree_gang_lookup may be called under
+ *	rcu_read_lock. In this case, rather than the returned results being
+ *	an atomic snapshot of the tree at a single point in time, the semantics
+ *	of an RCU protected gang lookup are as though multiple radix_tree_lookups
+ *	have been issued in individual locks, and results stored in 'results'.
  */
 unsigned int
 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
 			unsigned long first_index, unsigned int max_items)
 {
-	const unsigned long max_index = radix_tree_maxindex(root->height);
+	unsigned long max_index;
+	struct radix_tree_node *node;
 	unsigned long cur_index = first_index;
-	unsigned int ret = 0;
+	unsigned int ret;
+
+	node = rcu_dereference(root->rnode);
+	if (!node)
+		return 0;
+
+	if (radix_tree_is_direct_ptr(node)) {
+		if (first_index > 0)
+			return 0;
+		results[0] = radix_tree_direct_to_ptr(node);
+		ret = 1;
+		goto out;
+	}
 
+	max_index = radix_tree_maxindex(node->height);
+
+	ret = 0;
 	while (ret < max_items) {
 		unsigned int nr_found;
 		unsigned long next_index;	/* Index of next search */
 
 		if (cur_index > max_index)
 			break;
-		nr_found = __lookup(root, results + ret, cur_index,
+		nr_found = __lookup(node, results + ret, cur_index,
 					max_items - ret, &next_index);
 		ret += nr_found;
 		if (next_index == 0)
 			break;
 		cur_index = next_index;
 	}
+
+out:
+	(void)rcu_dereference(results); /* single barrier for all results */
+
 	return ret;
 }
 EXPORT_SYMBOL(radix_tree_gang_lookup);

@@ -635,24 +710,16 @@ EXPORT_SYMBOL(radix_tree_gang_lookup);
  * open-coding the search.
  */
 static unsigned int
-__lookup_tag(struct radix_tree_root *root, void **results, unsigned long index,
+__lookup_tag(struct radix_tree_node *slot, void **results, unsigned long index,
 	unsigned int max_items, unsigned long *next_index, unsigned int tag)
 {
 	unsigned int nr_found = 0;
 	unsigned int shift;
-	unsigned int height = root->height;
-	struct radix_tree_node *slot;
-
-	if (height == 0) {
-		if (root->rnode && index == 0)
-			results[nr_found++] = root->rnode;
-		goto out;
-	}
+	unsigned int height = slot->height;
 
 	shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
-	slot = root->rnode;
 
-	do {
+	while (height > 0) {
 		unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK;
 
 		for ( ; i < RADIX_TREE_MAP_SIZE; i++) {

@@ -683,7 +750,7 @@ __lookup_tag(struct radix_tree_root *roo
 		}
 		shift -= RADIX_TREE_MAP_SHIFT;
 		slot = slot->slots[i];
-	} while (height > 0);
+	}
 out:
 	*next_index = index;
 	return nr_found;

lib/radix-tree.c +17 -2

 {
-	const unsigned long max_index = radix_tree_maxindex(root->height);
+	struct radix_tree_node *node;
+	unsigned long max_index;
 	unsigned long cur_index = first_index;
 	unsigned int ret = 0;
 

@@ -715,13 +783,27 @@ radix_tree_gang_lookup_tag(struct radix_
 	if (!root_tag_get(root, tag))
 		return 0;
 
+	node = rcu_dereference(root->rnode);
+	if (!node)
+		return ret;
+
+	if (radix_tree_is_direct_ptr(node)) {
+		if (first_index > 0)
+			return 0;
+		node = radix_tree_direct_to_ptr(node);
+		results[0] = node;
+		return 1;
+	}
+
+	max_index = radix_tree_maxindex(node->height);
+
 	while (ret < max_items) {
 		unsigned int nr_found;
 		unsigned long next_index;	/* Index of next search */
 
 		if (cur_index > max_index)
 			break;
-		nr_found = __lookup_tag(root, results + ret, cur_index,
+		nr_found = __lookup_tag(node, results + ret, cur_index,
 					max_items - ret, &next_index, tag);
 		ret += nr_found;
 		if (next_index == 0)

@@ -743,8 +825,17 @@ static inline void radix_tree_shrink(str
 			root->rnode->count == 1 &&

lib/radix-tree.c +9 -2

 {
 	struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;
 	struct radix_tree_node *slot = NULL;
+	struct radix_tree_node *to_free;
 	unsigned int height, shift;
 	int tag;
 	int offset;

@@ -778,6 +870,7 @@ void *radix_tree_delete(struct radix_tre
 
 	slot = root->rnode;
 	if (height == 0 && root->rnode) {
+		slot = radix_tree_direct_to_ptr(slot);
 		root_tag_clear_all(root);
 		root->rnode = NULL;
 		goto out;

@@ -810,8 +903,11 @@ void *radix_tree_delete(struct radix_tre
 			radix_tree_tag_clear(root, index, tag);
 	}
 
+	to_free = NULL;
 	/* Now free the nodes we do not need anymore */
 	while (pathp->node) {
+		if (to_free)
+			radix_tree_node_free(to_free);
 		pathp->node->slots[pathp->offset] = NULL;
 		pathp->node->count--;
 

@@ -822,13 +918,15 @@ void *radix_tree_delete(struct radix_tre
 		}
 
 		/* Node with zero slots in use so free it */
-		radix_tree_node_free(pathp->node);
-
+		to_free = pathp->node;
 		pathp--;
+
 	}
 	root_tag_clear_all(root);
 	root->height = 0;
 	root->rnode = NULL;
+	if (to_free)
+		radix_tree_node_free(to_free);
 
 out:
 	return slot;

Index: linux-2.6/include/linux/radix-tree.h
===================================================================

include/linux/radix-tree.h +33 -0

@@ -22,6 +22,8 @@
 #include <linux/sched.h>
 #include <linux/preempt.h>
 #include <linux/types.h>
+#include <linux/kernel.h>
+#include <linux/rcupdate.h>
 
 #define RADIX_TREE_MAX_TAGS 2
 

@@ -48,6 +50,37 @@ do {									\
 	(root)->rnode = NULL;						\
 } while (0)
 
+#define RADIX_TREE_DIRECT_PTR	1
+
+static inline void *radix_tree_ptr_to_direct(void *ptr)
+{
+	return (void *)((unsigned long)ptr | RADIX_TREE_DIRECT_PTR);
+}
+
+static inline void *radix_tree_direct_to_ptr(void *ptr)
+{
+	return (void *)((unsigned long)ptr & ~RADIX_TREE_DIRECT_PTR);
+}
+
+static inline int radix_tree_is_direct_ptr(void *ptr)
+{
+	return (int)((unsigned long)ptr & RADIX_TREE_DIRECT_PTR);
+}
+
+static inline void *__radix_tree_deref_slot(void **slot)
+{
+	return rcu_dereference(radix_tree_direct_to_ptr(*slot));
+}
+
+#define radix_tree_deref_slot(slot) __radix_tree_deref_slot((void **)slot)
+
+static inline void radix_tree_replace_slot(void **slot, void *item)
+{
+	BUG_ON(radix_tree_is_direct_ptr(item));
+	rcu_assign_pointer(*slot,
+		(void *)((unsigned long)item | ((unsigned long)*slot & RADIX_TREE_DIRECT_PTR)));
+}
+
 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);

Index: linux-2.6/mm/migrate.c
===================================================================

mm/migrate.c +1 -1

@@ -228,7 +228,7 @@ int migrate_page_remove_references(struc
 						page_index(page));
 
 	if (!page_mapping(page) || page_count(page) != nr_refs ||
-			*radix_pointer != page) {
+			radix_tree_deref_slot(radix_pointer) != page) {
 		write_unlock_irq(&mapping->tree_lock);
 		return -EAGAIN;
 	}

On Tue, Jun 20, 2006 at 04:48:48PM +0200, Nick Piggin wrote:

Pretty close, but some questions and comments interspersed. Search for empty lines to find them.

Rough notes from review process at the end, in case anyone has insomnia or something.

Quoted 8 lines

lib/radix-tree.c +2 -3

+void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
 {
 	unsigned int height, shift;
-	struct radix_tree_node **slot;
-
-	height = root->height;
+	struct radix_tree_node *node, **slot;

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

Quoted 2 lines

lib/radix-tree.c +1 -1

-	if (index > radix_tree_maxindex(height))
+	node = rcu_dereference(root->rnode);

If writers are excluded, why is the rcu_dereference() required?

radix_tree_tag_set() needs a comment saying that updates must be excluded. Might be obvious to some, but...

Ditto for radix_tree_tag_clear().

radix_tree_tag_get() either needs a comment saying that updates must be excluded, or needs rcu_dereference() around the access of root->rnode near line 565. Yes, this is test scaffolding, but...

Quoted 4 lines

(quoted diff) +0 -0

@@ -542,29 +593,25 @@ EXPORT_SYMBOL(radix_tree_tag_get);
 #endif
 

lib/radix-tree.c EXPORT_SYMBOL(radix_tree_tag_get); · line 598

Quoted 5 lines

lib/radix-tree.c +1 -1

 static unsigned int
-__lookup(struct radix_tree_root *root, void **results, unsigned long index,
+__lookup(struct radix_tree_node *slot, void **results, unsigned long index,
 	unsigned int max_items, unsigned long *next_index)
 {

Not clear on why common code isn't shared more widely among the various lookups... Not -exactly- the same, I know, but...

Quoted 1 line

lib/radix-tree.c +0 -0

 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,

Quoted 2 lines

lib/radix-tree.c +2 -0

+out:
+	(void)rcu_dereference(results); /* single barrier for all results */

lib/radix-tree.c radix_tree_gang_lookup_tag(struct radix_ · line 775

Quoted 3 lines

lib/radix-tree.c +0 -0

@@ -707,7 +774,8 @@ radix_tree_gang_lookup_tag(struct radix_
 		unsigned long first_index, unsigned int max_items,
 		unsigned int tag)

Need header comment saying that pointers returned in results array must be rcu_dereferenced() by RCU callers before use.

But would be better to just rcu_dereference() them in __lookup_tag():745. This is zero cost on all but Alpha, and keeps the RCU effects more localized.

Or must radix_tree_gang_lookup_tag() exclude updates? If so, need to say so in header comment. Also, in this case, the rcu_dereference() calls are unneeded.

lib/radix-tree.c static inline void radix_tree_shrink(str · line 834

Quoted 12 lines

lib/radix-tree.c +6 -1

@@ -743,8 +825,17 @@ static inline void radix_tree_shrink(str
 			root->rnode->count == 1 &&
 			root->rnode->slots[0]) {
 		struct radix_tree_node *to_free = root->rnode;
+		void *newptr;
 
-		root->rnode = to_free->slots[0];
+		/*
+		 * this doesn't need an rcu_assign_pointer, because
+		 * we aren't touching the object that to_free->slots[0]
+		 * points to.
+		 */

I found this comment to be confusing. Suggest something like the following:

/*
* We don't need rcu_assign_pointer(), since we are
* simply moving the node from one part of the tree
* to another. If it was safe to dereference a pointer
* to it before, it is still safe to dereference a
* pointer to it afterwards.
*/

A few more lines, but well worth it IMHO. Someone with a clearer understanding of the code might be able to create a more concise comment that still gets the idea across clearly. ;-)

lib/radix-tree.c void *radix_tree_delete(struct radix_tre

Quoted 9 lines

lib/radix-tree.c +4 -0

+		newptr = to_free->slots[0];
+		if (root->height == 1)
+			newptr = radix_tree_ptr_to_direct(newptr);
+		root->rnode = newptr;
 		root->height--;
 		/* must only free zeroed nodes into the slab */
 		tag_clear(to_free, 0, 0);

@@ -768,6 +859,7 @@ void *radix_tree_delete(struct radix_tre

Need header comment in radix_tree_delete() saying that if the caller also does lock-free searches, that it is the caller's responsibility to wait a grace period (e.g., call_rcu() or synchronize_rcu()) before freeing or re-using the removed item. Otherwise, people will naturally assume that radix_tree_delete() took care of this detail for them.

For that matter, should radix_tree_delete() do a synchronize_rcu()? My belief is "no", since radix_tree_delete() has no way of knowing whether this particular tree is searched lock-free. One option would be to have some sort of option bit in the tree telling radix_tree_delete() to do a synchronize_rcu(). It does not make sense for radix_tree_delete() to do call_rcu(), since it has no idea what needs to be done to free the item removed -- it could well have arbitrary frilly data structures linked to it that also need to be freed.

Also should add comment saying that caller is responsible for excluding other updates to this tree. Obvious perhaps, but better safe than sorry.

Rough notes, FYA:

o Don't the items placed into the radix tree need to be protected
by RCU? If not, how does the radix tree avoid handing a pointer to something that has recently been removed, that the caller to radix_tree_delete() might have already freed?

If so, what about nfs_inode_add_request(), which adds struct nfs_page to a radix tree? This structure does not appear to have any sort of RCU protection:

But it seems that all radix-tree operations are under a spinlock, so this works after all.

Other calls to radix_tree_delete():

o __remove_from_page_cache() is called under
->tree_lock in all cases, as are other non-initialization uses of ->page_tree.

And that appears to be it. So where is Ben Herrenschmidt's lock-free use of radix-tree lookup? No matter -- Ben just needs to make sure to RCU-protect whatever the heck he is putting into the radix tree if he is calling the lookup functions without locking. ;-)

Probably worth a comment to radix_tree_delete() saying that the caller must wait for a grace period before freeing/reusing the item removed from the tree! (But only if searching done without locking.)

o radix_tree_shrink() -- what is to_free? freelist? If so, protected
by what lock? OK -- the reason that rcu_assign_pointer() can be omitted is that we are simply moving the element unchanged from one location in the tree to another -- if it was safe to access before, it is safe to access now, no additional memory barriers required.

And to_free is just a local variable -- must be blind today. :-/

Need to make the comment more clear.

o RCU-protected fields:

Quoted 7 lines · Paul E. McKenney

On Tue, Jun 20, 2006 at 04:48:48PM +0200, Nick Piggin wrote:

Pretty close, but some questions and comments interspersed. Search for empty lines to find them.

Rough notes from review process at the end, in case anyone has insomnia or something.

Wow ;)
Thanks Paul.

Quoted 8 lines

Quoted 8 lines

lib/radix-tree.c +2 -3

+void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
 {
 	unsigned int height, shift;
-	struct radix_tree_node **slot;
-
-	height = root->height;
+	struct radix_tree_node *node, **slot;

Quoted 4 lines

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

Quoted 2 lines

lib/radix-tree.c +1 -1

-	if (index > radix_tree_maxindex(height))
+	node = rcu_dereference(root->rnode);

If writers are excluded, why is the rcu_dereference() required?

Good point, in earlier versions, radix_tree_lookup_slot was RCU-able, but the direct-data patch ended that idea. I'll go through and clean these out.

Quoted 8 lines

radix_tree_tag_set() needs a comment saying that updates must be excluded. Might be obvious to some, but...

Ditto for radix_tree_tag_clear().

radix_tree_tag_get() either needs a comment saying that updates must be excluded, or needs rcu_dereference() around the access of root->rnode near line 565. Yes, this is test scaffolding, but...

Indeed. I mainly intended to document APIs that _are_ RCU-able, but documented the negative for lookup_slot because it is similar to lookup... but that's messy too.

I'll probably put a little table in radix-tree.h to summarise the API synchronisation requirements, OK?

Quoted 11 lines

lib/radix-tree.c EXPORT_SYMBOL(radix_tree_tag_get); · line 598

Quoted 8 lines

lib/radix-tree.c +1 -1

@@ -542,29 +593,25 @@ EXPORT_SYMBOL(radix_tree_tag_get);
 #endif
 
 static unsigned int
-__lookup(struct radix_tree_root *root, void **results, unsigned long index,
+__lookup(struct radix_tree_node *slot, void **results, unsigned long index,
 	unsigned int max_items, unsigned long *next_index)
 {

Not clear on why common code isn't shared more widely among the various lookups... Not -exactly- the same, I know, but...

Yeah it can get a bit tricky. It's gets a small cleanup now and again, which is probably not a bad pace for our pagecache data structure ;)

Quoted 1 line

Quoted 1 line

lib/radix-tree.c +0 -0

 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,

...

Quoted 2 lines

Quoted 2 lines

lib/radix-tree.c +2 -0

+out:
+	(void)rcu_dereference(results); /* single barrier for all results */

...

Quoted 7 lines

lib/radix-tree.c radix_tree_gang_lookup_tag(struct radix_ · line 775

Quoted 3 lines

lib/radix-tree.c +0 -0

@@ -707,7 +774,8 @@ radix_tree_gang_lookup_tag(struct radix_
 		unsigned long first_index, unsigned int max_items,
 		unsigned int tag)

Need header comment saying that pointers returned in results array must be rcu_dereferenced() by RCU callers before use.

Quoted 3 lines

But would be better to just rcu_dereference() them in __lookup_tag():745. This is zero cost on all but Alpha, and keeps the RCU effects more localized.

Does the single rcu_dereference in radix_tree_gang_lookup look OK?

Quoted 3 lines

Or must radix_tree_gang_lookup_tag() exclude updates? If so, need to say so in header comment. Also, in this case, the rcu_dereference() calls are unneeded.

Ah indeed, that's confusing. Yes, the lookup_tag must exclude updates. I guess I got too mechanical in my conversion... however, tag lookups can be RCUified without a great deal of trouble, so I might take this opportunity.

Quoted 23 lines

lib/radix-tree.c static inline void radix_tree_shrink(str · line 834

Quoted 12 lines

lib/radix-tree.c +6 -1

@@ -743,8 +825,17 @@ static inline void radix_tree_shrink(str
 			root->rnode->count == 1 &&
 			root->rnode->slots[0]) {
 		struct radix_tree_node *to_free = root->rnode;
+		void *newptr;
 
-		root->rnode = to_free->slots[0];
+		/*
+		 * this doesn't need an rcu_assign_pointer, because
+		 * we aren't touching the object that to_free->slots[0]
+		 * points to.
+		 */

I found this comment to be confusing. Suggest something like the following:

/*
* We don't need rcu_assign_pointer(), since we are
* simply moving the node from one part of the tree
* to another. If it was safe to dereference a pointer
* to it before, it is still safe to dereference a
* pointer to it afterwards.
*/

Quoted 3 lines

A few more lines, but well worth it IMHO. Someone with a clearer understanding of the code might be able to create a more concise comment that still gets the idea across clearly. ;-)

That's pretty good, I just made a couple of tiny changes, what do you think?
/*
* We don't need rcu_assign_pointer(), since we are simply
* moving the node from one part of the tree to another. If
* it was safe to dereference the old pointer to it
* (to_free->slots[0]), it will be safe to dereference the new
* one (root->rnode).
*/

Quoted 6 lines

Quoted 6 lines

lib/radix-tree.c +4 -0

+		newptr = to_free->slots[0];
+		if (root->height == 1)
+			newptr = radix_tree_ptr_to_direct(newptr);
+		root->rnode = newptr;
 		root->height--;
 		/* must only free zeroed nodes into the slab */

Quoted 8 lines

lib/radix-tree.c void *radix_tree_delete(struct radix_tre

Quoted 2 lines

lib/radix-tree.c +0 -0

 		tag_clear(to_free, 0, 0);

@@ -768,6 +859,7 @@ void *radix_tree_delete(struct radix_tre

Need header comment in radix_tree_delete() saying that if the caller also does lock-free searches, that it is the caller's responsibility to wait a grace period (e.g., call_rcu() or synchronize_rcu()) before freeing or re-using the removed item. Otherwise, people will naturally assume that radix_tree_delete() took care of this detail for them.

I've tried to get that message across in the radix_tree_lookup_slot comment, if they're using RCU lookups. Enough? I guess I'll add it to the locking summary too.

Quoted 8 lines

For that matter, should radix_tree_delete() do a synchronize_rcu()? My belief is "no", since radix_tree_delete() has no way of knowing whether this particular tree is searched lock-free. One option would be to have some sort of option bit in the tree telling radix_tree_delete() to do a synchronize_rcu(). It does not make sense for radix_tree_delete() to do call_rcu(), since it has no idea what needs to be done to free the item removed -- it could well have arbitrary frilly data structures linked to it that also need to be freed.

Agreed, I think "no". In the current (locked) radix-tree, the caller is still responsible to manage lifetimes of the data (leaf) nodes.

Quoted 2 lines

Also should add comment saying that caller is responsible for excluding other updates to this tree. Obvious perhaps, but better safe than sorry.

Yeah, I'll try to make all this a bit clearer in the locking summary.

Quoted 1 line

Rough notes, FYA:

Quoted 4 lines

o Don't the items placed into the radix tree need to be protected
by RCU? If not, how does the radix tree avoid handing a pointer to something that has recently been removed, that the caller to radix_tree_delete() might have already freed?

Yes, they'll need to be protected by something. In the lockless pagecache, they are never freed, so that isn't an issue. But other users (Ben's irq patch perhaps, unless it uses the slot pointers directly) will have to be careful.

Quoted 3 lines

If so, what about nfs_inode_add_request(), which adds struct nfs_page to a radix tree? This structure does not appear to have any sort of RCU protection:

Well if they retain their existing locking, there shouldn't be a problem. (as you say below...)

Quoted 27 lines

But it seems that all radix-tree operations are under a spinlock, so this works after all.

Other calls to radix_tree_delete():

o __remove_from_page_cache() is called under
->tree_lock in all cases, as are other non-initialization uses of ->page_tree.

And that appears to be it. So where is Ben Herrenschmidt's lock-free use of radix-tree lookup? No matter -- Ben just needs to make sure to RCU-protect whatever the heck he is putting into the radix tree if he is calling the lookup functions without locking. ;-)

Probably worth a comment to radix_tree_delete() saying that the caller must wait for a grace period before freeing/reusing the item removed from the tree! (But only if searching done without locking.)

o radix_tree_shrink() -- what is to_free? freelist? If so, protected
by what lock? OK -- the reason that rcu_assign_pointer() can be omitted is that we are simply moving the element unchanged from one location in the tree to another -- if it was safe to access before, it is safe to access now, no additional memory barriers required.

Quoted 3 lines

And to_free is just a local variable -- must be blind today. :-/

Need to make the comment more clear.

Yeah, to_free is just a redundant node that is being chopped off the top of the tree. It does go through a grace period of course, because lockless lookups can still be referencing it.

Quoted 1 line

o RCU-protected fields:

...

Thanks very much Paul. Very thorough review.

I'll send out an incremental diff with changes.

Quoted 3 lines · Nick Piggin

I'll probably put a little table in radix-tree.h to summarise the API synchronisation requirements, OK?

Makes sense to me -- except will that feed into the docbook stuff? It seems to me to be really important to get these sorts of requirements included in the docbook stuff. I have had too many people show me code that assumed that RCU somehow synchronizes updates, so it is good to call out these requirements early and often.

Quoted 2 lines

Does the single rcu_dereference in radix_tree_gang_lookup look OK?

Well, it does put a memory barrier in the right place on Alpha, but the intent would be more clear to me if the rcu_dereference() were on the assignments to each element of the results array. And there would be no additional overhead on most architectures.

So I would much prefer the rcu_dereference() be on the assignment to the results array.

Quoted 4 lines

Ah indeed, that's confusing. Yes, the lookup_tag must exclude updates. I guess I got too mechanical in my conversion... however, tag lookups can be RCUified without a great deal of trouble, so I might take this opportunity.

The tag lookups would then find anything that (1) had been tagged in a prior operation and (2) had not been deleted in the meantime, right?

And the caller could hold a lock across both the tagging and tag lookup if greater certainty was desired. I could imagine this sort of semantic being useful for deferred operations on ranges of memory, where new additions would have the operation implicit in creation and any deletions would no longer need the operation to be performed (or might be performed as part of deletion operation), but have not actually used this sort of thing myself.

So I must defer to people who have used tagging and tagged lookups in anger.

Quoted 3 lines

I've tried to get that message across in the radix_tree_lookup_slot comment, if they're using RCU lookups. Enough? I guess I'll add it to the locking summary too.

This is what I saw in the radix_tree_lookup_slot() comment:

+ *   radix_tree_lookup_slot    -    lookup a slot in a radix tree
+ *   @root:          radix tree root
+ *   @index:         index key

+ *
+ * Lookup the slot corresponding to the position @index in the radix tree
+ * @root. This is useful for update-if-exists operations.
+ *
+ * This function cannot be called under rcu_read_lock, it must be
+ * excluded from writers, as must the returned slot.

This comment does not make the RCU-protection point clear to me. The constraint is that if you use RCU radix-tree lookups, then you must use synchronize_rcu() or call_rcu() when freeing any elements removed from the radix tree via radix_tree_delete().

Or am I missing something here?

Quoted 1 line

Quoted 1 line

Rough notes, FYA:

You went through all these as well? Hope you have recovered from the bout of insomnia! ;-)

Quoted 10 lines

Quoted 5 lines

o Don't the items placed into the radix tree need to be protected
by RCU? If not, how does the radix tree avoid handing a pointer to something that has recently been removed, that the caller to radix_tree_delete() might have already freed?

Yes, they'll need to be protected by something. In the lockless pagecache, they are never freed, so that isn't an issue. But other users (Ben's irq patch perhaps, unless it uses the slot pointers directly) will have to be careful.

Ah! If they are never freed, there is still a need to take care when reusing them. One approach is to prevent them from being reused until after a grace period has elapsed, another is to use revalidation checks after lookup. Either way, one needs to allow for the fact that a lookup might hand you something that has just been deleted.

Quoted 1 line

I'll send out an incremental diff with changes.

Looking forward to it! Maybe not as anxiously as Ben Herrenschmidt, but so it goes. ;-)

Quoted 5 lines · Paul E. McKenney

Quoted 3 lines · Nick Piggin

I'll probably put a little table in radix-tree.h to summarise the API synchronisation requirements, OK?

Quoted 5 lines

Makes sense to me -- except will that feed into the docbook stuff? It seems to me to be really important to get these sorts of requirements included in the docbook stuff. I have had too many people show me code that assumed that RCU somehow synchronizes updates, so it is good to call out these requirements early and often.

I'm not a docbook expert, but that's a good point. Will RFComments on the comments when I'm done ;)

Quoted 9 lines

Quoted 1 line

Does the single rcu_dereference in radix_tree_gang_lookup look OK?

Well, it does put a memory barrier in the right place on Alpha, but the intent would be more clear to me if the rcu_dereference() were on the assignments to each element of the results array. And there would be no additional overhead on most architectures.

So I would much prefer the rcu_dereference() be on the assignment to the results array.

No problem, will change.

Quoted 7 lines

Quoted 4 lines

Ah indeed, that's confusing. Yes, the lookup_tag must exclude updates. I guess I got too mechanical in my conversion... however, tag lookups can be RCUified without a great deal of trouble, so I might take this opportunity.

The tag lookups would then find anything that (1) had been tagged in a prior operation and (2) had not been deleted in the meantime, right?

Yes. Where "prior" is only really prior as guaranteed by some synchronising (or otherwise dependent) operation. But I don't need to tell you that ;)

Quoted 8 lines

And the caller could hold a lock across both the tagging and tag lookup if greater certainty was desired. I could imagine this sort of semantic being useful for deferred operations on ranges of memory, where new additions would have the operation implicit in creation and any deletions would no longer need the operation to be performed (or might be performed as part of deletion operation), but have not actually used this sort of thing myself.

Quoted 2 lines

So I must defer to people who have used tagging and tagged lookups in anger.

We use tagged lookups for writeout and synching -- slow IO related which is why I had not converted it over to lockless. But it could use lockless tagged lookups: eg. so long as sync catches all the pages that we *know* to be dirty at the time of the sync, that's fine.

Quoted 21 lines

Quoted 3 lines

I've tried to get that message across in the radix_tree_lookup_slot comment, if they're using RCU lookups. Enough? I guess I'll add it to the locking summary too.

This is what I saw in the radix_tree_lookup_slot() comment:

+ *   radix_tree_lookup_slot    -    lookup a slot in a radix tree
+ *   @root:          radix tree root
+ *   @index:         index key

+ *
+ * Lookup the slot corresponding to the position @index in the radix tree
+ * @root. This is useful for update-if-exists operations.
+ *
+ * This function cannot be called under rcu_read_lock, it must be
+ * excluded from writers, as must the returned slot.

This comment does not make the RCU-protection point clear to me. The constraint is that if you use RCU radix-tree lookups, then you must use synchronize_rcu() or call_rcu() when freeing any elements removed from the radix tree via radix_tree_delete().

Quoted 1 line

Or am I missing something here?

Well the pagecache uses pointers to struct page. struct page is never freed, so we can forget the whole thing ;)
(mem unplug may want to free them, so in that case they would have to synchronize_rcu).

From your comments below, looks like you do #2.

But I guess for less specialised users, RCU would be the usual way to go... ah I see, I must have got out of synch somewhere. I have comments along these lines for radix_tree_lookup_slot:

+ *     This function can be called under rcu_read_lock, however it is the
+ *     duty of the caller to manage the lifetimes of the leaf nodes (ie.
+ *     they would usually be RCU protected as well). Also, dereferencing
+ *     the slot pointer would require rcu_dereference, and modifying it
+ *     would require rcu_assign_pointer.

Quoted 4 lines

Quoted 1 line

Quoted 1 line

Rough notes, FYA:

You went through all these as well? Hope you have recovered from the bout of insomnia! ;-)

Pretty well gone through them.

Quoted 10 lines

Quoted 9 lines

Quoted 4 lines

o Don't the items placed into the radix tree need to be protected
by RCU? If not, how does the radix tree avoid handing a pointer to something that has recently been removed, that the caller to radix_tree_delete() might have already freed?

Yes, they'll need to be protected by something. In the lockless pagecache, they are never freed, so that isn't an issue. But other users (Ben's irq patch perhaps, unless it uses the slot pointers directly) will have to be careful.

Quoted 5 lines

Ah! If they are never freed, there is still a need to take care when reusing them. One approach is to prevent them from being reused until after a grace period has elapsed, another is to use revalidation checks after lookup. Either way, one needs to allow for the fact that a lookup might hand you something that has just been deleted.

Yep, validation checks are done after lookup. The core of it, the ``page_cache_get_speculative'' function isn't that big.

Quoted 4 lines

Quoted 1 line

I'll send out an incremental diff with changes.

Looking forward to it! Maybe not as anxiously as Ben Herrenschmidt, but so it goes. ;-)

Well I couldn't ask you to spend any more time on it, but if you get interested and take a peek, that'll be a bonus for me ;)

Thanks again

Quoted 2 lines · Nick Piggin

No problem, will change.

Thank you!

Quoted 5 lines · Paul E. McKenney

Quoted 2 lines · Nick Piggin

No problem, will change.

Thank you!

OK, and with that I believe I've covered all your concerns.

Attached is the incremental patch (plus a little bit of fuzz that's gone to Andrew). The big items are:

- documentation, clarification of comments
- tag lookups are now RCU safe (tested with harness)
- cleanups of various misuses of rcu_ API that Paul spotted
- thought I might put in a copyright -- is this OK?

Andrew, please apply.

Quoted 13 lines · On Thu, 22 Jun 2006 20:11:12 +0200 Nick Piggin <[email protected]> wrote:

Quoted 5 lines · Paul E. McKenney

Quoted 1 line · Nick Piggin

No problem, will change.

Thank you!

OK, and with that I believe I've covered all your concerns.

Attached is the incremental patch (plus a little bit of fuzz that's gone to Andrew). The big items are:

Quoted 6 lines

- documentation, clarification of comments
- tag lookups are now RCU safe (tested with harness)
- cleanups of various misuses of rcu_ API that Paul spotted
- thought I might put in a copyright -- is this OK?

Andrew, please apply.

Freeing unused kernel memory: 316k freed
Write protecting the kernel read-only data: 384k No module found in object
No module found in object
No module found in object
No module found in object
input: AT Translated Set 2 keyboard as /class/input/input0 No module found in object
EXT3-fs: INFO: recovery required on readonly filesystem.
EXT3-fs: write access will be enabled during recovery. kjournald starting. Commit interval 5 seconds
EXT3-fs: recovery complete.
EXT3-fs: mounted filesystem with ordered data mode.

BUG: NMI Watchdog detected LOCKUP on CPU0, eip c0264345, registers:

CPU: 0
EIP is at radix_tree_gang_lookup_tag+0x105/0x1a0
eax: ffffffff ebx: 00000040 ecx: ffffffc0 edx: 00000007
esi: e701e9d8 edi: 000001c0 ebp: e6fbddd8 esp: e6fbdda8
ds: 007b es: 007b ss: 0068
Process fsck.ext3 (pid: 1565, ti=e6fbc000 task=c1fbcb90 task.ti=e6fbc000)

Stack: e77f2dc4 e701e9d8 e701e9d8 00000002 00000fff 00000000 e701e8c8 e6fbde60 
       0000000e c1c6c52c e6fbde60 c1c6c538 e6fbde00 c014b68f c1c6c52c e6fbde60 
       00000000 0000000e 00000000 e6fbde58 00000000 00000001 e6fbde20 c0155631 
Call Trace:
Code: 89 fa 8d 4c 09 fa d3 e3 d3 ea 89 d9 83 e2 3f f7 d9 eb 13 8d 76 00 89 f8 89 df 21 c8 01 c7 74 26 42 83 fa 40 74 95 0f a3 16 19 c0 <85> c0 74 e7 83 7d dc 01 74 3a 31 f6 89 75 f0 e9 6e ff ff ff c7 console shuts up ...

Not sure why, either. It all looks like an equivalent transformation to me.

fwiw, here's what I tested:

Quoted 13 lines · On Thu, 22 Jun 2006 20:11:12 +0200 Nick Piggin <[email protected]> wrote:

Quoted 5 lines · Paul E. McKenney

Quoted 1 line · Nick Piggin

No problem, will change.

Thank you!

OK, and with that I believe I've covered all your concerns.

Attached is the incremental patch (plus a little bit of fuzz that's gone to Andrew). The big items are:

Quoted 6 lines

- documentation, clarification of comments
- tag lookups are now RCU safe (tested with harness)
- cleanups of various misuses of rcu_ API that Paul spotted
- thought I might put in a copyright -- is this OK?

Andrew, please apply.

Freeing unused kernel memory: 316k freed
Write protecting the kernel read-only data: 384k No module found in object
No module found in object
No module found in object
No module found in object
input: AT Translated Set 2 keyboard as /class/input/input0 No module found in object
EXT3-fs: INFO: recovery required on readonly filesystem.
EXT3-fs: write access will be enabled during recovery. kjournald starting. Commit interval 5 seconds
EXT3-fs: recovery complete.
EXT3-fs: mounted filesystem with ordered data mode.

BUG: NMI Watchdog detected LOCKUP on CPU0, eip c0264345, registers:

CPU: 0
EIP is at radix_tree_gang_lookup_tag+0x105/0x1a0
eax: ffffffff ebx: 00000040 ecx: ffffffc0 edx: 00000007
esi: e701e9d8 edi: 000001c0 ebp: e6fbddd8 esp: e6fbdda8
ds: 007b es: 007b ss: 0068
Process fsck.ext3 (pid: 1565, ti=e6fbc000 task=c1fbcb90 task.ti=e6fbc000)

Stack: e77f2dc4 e701e9d8 e701e9d8 00000002 00000fff 00000000 e701e8c8 e6fbde60 
       0000000e c1c6c52c e6fbde60 c1c6c538 e6fbde00 c014b68f c1c6c52c e6fbde60 
       00000000 0000000e 00000000 e6fbde58 00000000 00000001 e6fbde20 c0155631 
Call Trace:
Code: 89 fa 8d 4c 09 fa d3 e3 d3 ea 89 d9 83 e2 3f f7 d9 eb 13 8d 76 00 89 f8 89 df 21 c8 01 c7 74 26 42 83 fa 40 74 95 0f a3 16 19 c0 <85> c0 74 e7 83 7d dc 01 74 3a 31 f6 89 75 f0 e9 6e ff ff ff c7 console shuts up ...

Not sure why, either. It all looks like an equivalent transformation to me.

fwiw, here's what I tested:

lib/radix-tree.c renamed from lib/radix-tree.c~adix-tree-rcu-lockless-readside-update +5 -4

@@ -741,15 +740,19 @@ __lookup_tag(struct radix_tree_node *slo
 			for ( ; j < RADIX_TREE_MAP_SIZE; j++) {
 				index++;
 				if (tag_get(slot, tag, j)) {
-					BUG_ON(slot->slots[j] == NULL);
-					results[nr_found++] = slot->slots[j];
-					if (nr_found == max_items)
-						goto out;
+					struct radix_tree_node *node = slot->slots[j];
+					if (node) {
+						results[nr_found++] = rcu_dereference(node);
+						if (nr_found == max_items)
+							goto out;

Review

Quoted 6 lines

         shift -= RADIX_TREE_MAP_SHIFT;

(quoted diff) +3 -1

-        slot = slot->slots[i];
+        slot = rcu_dereference(slot->slots[i]);
+        if (slot == NULL);
+            break;
     }

                         ^^^^^^^^

Up there.

Just out of interest, attached is my userspace RCU implementation and RCU radix-tree concurrent tests for Andrew Morton's radix-tree test harness.

The RCU implementation is only 100 lines. Awful performance, of course, but I've stretched the rcu_read_lock/unlock over large periods so that we can get full concurrency at the cost of a bit of memory build up. And it still seems to catch use-after RCU-freed errors pretty easily.

Question - our kernel's call_rcu implies a smp_wmb, right? Because that did catch me out initially, because I initially had no barrier to prevent the freeing of the object becoming visible before removal of its last reference becoming visible (fixed by adding smp_wmb() in my call_rcu).

Quoted 10 lines · Nick Piggin

Just out of interest, attached is my userspace RCU implementation and RCU radix-tree concurrent tests for Andrew Morton's radix-tree test harness.

The RCU implementation is only 100 lines. Awful performance, of course, but I've stretched the rcu_read_lock/unlock over large periods so that we can get full concurrency at the cost of a bit of memory build up. And it still seems to catch use-after RCU-freed errors pretty easily.

Interesting approach! One caution -- this approach can result in RCU callbacks being invoked in the context of either call_rcu() or rcu_read_unlock(). In some legitimate uses of RCU, this can result in deadlock. See Documentation/RCU/UP.txt for more info.

One solution is to have some other context (perhaps just a separate pthread, given that performance is not critical) to invoke the callbacks.

Another user-level RCU implementation is available here:

http://www.cs.toronto.edu/~tomhart/perflab/ipdps06.tgz

I have a few user-mode implementations myself, but the lawyers won't let me release them. :-(

Quoted 6 lines

Question - our kernel's call_rcu implies a smp_wmb, right? Because that did catch me out initially, because I initially had no barrier to prevent the freeing of the object becoming visible before removal of its last reference becoming visible (fixed by adding smp_wmb() in my call_rcu).

No and yes... The kernel's call_rcu() itself does not have an smp_wmb(), but the Classic RCU grace-period mechanism forces a memory barrier on each CPU as part of grace-period detection -- which is why rcu_read_lock() and rcu_read_unlock() don't need memory barriers. Looks like your need for an smp_wmb() in call_rcu() itself is due to the fact that you can execute callbacks in the context of the call_rcu() itself.

Quoted 2 lines · Paul E. McKenney

I have a few user-mode implementations myself, but the lawyers won't let me release them. :-(

I imagine they're quite a bit faster than my quick hack, too ;)

I've finally ported the RCU radix tree over my radix tree direct-data patch (the latter patch has been in -mm for a while now).

I've also done the last step required for submission, which was to make a small userspace RCU test harness, and wire up the rtth so that it can handle multiple threads to test the lockless capability. The RCU test harness uses an implementation somewhat like Paul's paper's quiescent state bitmask approach; with infrequent quiescent state updates, performance isn't bad.

This quickly flushed out several obscure bugs just when running on my dual G5. After fixing those, I racked up about 100 CPU hours of testing on SUSE's 64-way Altix without problem. Also passes the normal battery of single threaded rtth tests.

I'd like to hear views regarding merging these patches for 2.6.18. Initially the lockless code would not come into effect (good - one thing at a time) until tree_lock can start getting lifted in -mm and 2.6.19.

I've finally ported the RCU radix tree over my radix tree direct-data patch (the latter patch has been in -mm for a while now).

I've also done the last step required for submission, which was to make a small userspace RCU test harness, and wire up the rtth so that it can handle multiple threads to test the lockless capability. The RCU test harness uses an implementation somewhat like Paul's paper's quiescent state bitmask approach; with infrequent quiescent state updates, performance isn't bad.

This quickly flushed out several obscure bugs just when running on my dual G5. After fixing those, I racked up about 100 CPU hours of testing on SUSE's 64-way Altix without problem. Also passes the normal battery of single threaded rtth tests.

I'd like to hear views regarding merging these patches for 2.6.18. Initially the lockless code would not come into effect (good - one thing at a time) until tree_lock can start getting lifted in -mm and 2.6.19.

So given those complexities, and the lack of a _user_ of radix-tree-rcu-lockless-readside.patch, it doesn't look like 2.6.18 stuff at this time.

Quoted 3 lines · Andrew Morton

So given those complexities, and the lack of a _user_ of radix-tree-rcu-lockless-readside.patch, it doesn't look like 2.6.18 stuff at this time.

So what should I do ?

leave the bug in ppc64 or kill it's scalability when taking interrupts ? You have one user already, me.

From what Nick
says, the patch has been beaten up pretty heavily and seems stable....

Quoted 2 lines

leave the bug in ppc64 or kill it's scalability when taking interrupts ? You have one user already, me.

I didn't know that 30 minutes ago ;)

Quoted 2 lines

From what Nick
says, the patch has been beaten up pretty heavily and seems stable....

Well as I say, the tree_lock crash is way more important. We need to work out what we're going to do then get that fixed, backport the fix to -stable then rebase the radix-tree patches on top and get radix-tree-rcu-lockless-readside.patch tested and reviewed.

I guess we can do all that in time for -rc1, but not knowing _how_ we'll be fixing the tree_lock crash is holding things up.

Paul, if you could take a close look at the RCU aspects of this work it'd help, thanks.

btw guys, theory has it that code which was submitted post-2.6.n is too late for 2.6.n+1..

Anyway, I can drop a spinlock in (in fact I have) the ppc64 irq code for now but that sucks, thus we should really seriously consider having the lockless tree in 2.6.18 or I might have to look into doing an alternate implementation specifically in arch code... or find some other way of doing the inverse mapping there...

Quoted 5 lines · Benjamin Herrenschmidt

Anyway, I can drop a spinlock in (in fact I have) the ppc64 irq code for now but that sucks, thus we should really seriously consider having the lockless tree in 2.6.18 or I might have to look into doing an alternate implementation specifically in arch code... or find some other way of doing the inverse mapping there...

How many interrupts do you have to ? I would expect a simple table lookup would be fine to get from the virtual to the real interrupt.

No, our hardware interrupt numbers are an encoded form containing the geographical location of the device :) so they are 24 bits at least (and we have a platform coming where they can be 64 bits).

Quoted 3 lines · Benjamin Herrenschmidt

No, our hardware interrupt numbers are an encoded form containing the geographical location of the device :) so they are 24 bits at least (and we have a platform coming where they can be 64 bits).

PICs with build in GPSses? And I thought we had weird hardware....