[PATCH] radix-tree: fix radix_tree_replace_slot

[PATCH] radix-tree: fix radix_tree_replace_slot

[Lee Schermerhorn]

I was waiting to hear from Nick on this, but I understand that he has
severely injured one hand, restricting his keyboard access for a while. 

Christoph has been too swamped to take a look, either.   So, having
tested it myself, I'll send it on.

Paul:

could you take a look at this one.  Also, I'll be sending another
rcu-radix-tree "cleanup" patch that I'd like your opinion on.

Lee

Fix radix tree direct slot replacement - 2.6.18-rc4-mm2

radix_tree_replace_slot() was assigning to local variable 'slot'
instead of to where pslot pointed.  Changed to directly replace
location pointed to by argument pslot.

Added comments specifying required locking.

Note that we do not need to rcu_dereference() the slot to
obtain the direct pointer flag, as we hold the tree write locked.

Fixes the migration corruption that we were seeing since the
rcu-radix-tree patches went in.  With this patch, we can back out
page-migration-replace-radix_tree_lookup_slot-with-radix_tree_lockup.patch
to use the more efficient direct access to radix tree slot.

Signed-off-by:  Lee Schermerhorn <lee.schermerhorn@hp.com>

 include/linux/radix-tree.h |    5 ++++-
 1 files changed, 4 insertions(+), 1 deletion(-)

Index: linux-2.6.18-rc4-mm2/include/linux/radix-tree.h
===================================================================
--- linux-2.6.18-rc4-mm2.orig/include/linux/radix-tree.h	2006-08-22 14:30:38.000000000 -0400
+++ linux-2.6.18-rc4-mm2/include/linux/radix-tree.h	2006-08-22 14:36:54.000000000 -0400
@@ -133,12 +133,15 @@ static inline void *radix_tree_deref_slo
  * radix_tree_replace_slot	- replace item in a slot
  * @pslot:	pointer to slot, returned by radix_tree_lookup_slot
  * @item:	new item to store in the slot.
+ *
+ * For use with radix_tree_lookup_slot().  Caller must hold tree write locked
+ * across slot lookup and replacement.
  */
 static inline void radix_tree_replace_slot(void *pslot, void *item)
 {
 	void *slot = *(void **)pslot;
 	BUG_ON(radix_tree_is_direct_ptr(item));
-	rcu_assign_pointer(slot,
+	rcu_assign_pointer(*(void **)pslot,
 		(void *)((unsigned long)item |
 			((unsigned long)slot & RADIX_TREE_DIRECT_PTR)));
 }


--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] radix-tree: fix radix_tree_replace_slot

[Christoph Lameter]

On Tue, 22 Aug 2006, Lee Schermerhorn wrote:

>   * @item:	new item to store in the slot.
> + *
> + * For use with radix_tree_lookup_slot().  Caller must hold tree write locked
> + * across slot lookup and replacement.
>   */
>  static inline void radix_tree_replace_slot(void *pslot, void *item)
>  {
>  	void *slot = *(void **)pslot;
>  	BUG_ON(radix_tree_is_direct_ptr(item));
> -	rcu_assign_pointer(slot,
> +	rcu_assign_pointer(*(void **)pslot,
>  		(void *)((unsigned long)item |
>  			((unsigned long)slot & RADIX_TREE_DIRECT_PTR)));
                                        ^^^^ Is this a legit use of slot?

>  }
> 

Would it not be better to change the calling conventions of 
radix_tree_replace_slot? It should get passsed a void **pslot right?

static inline void radix_tree_replace_slot(void **pslot, void *item)
{
	BUG_ON(radix_tree_is_direct_ptr(item));
	rcu_assign_pointer(*pslot,
		(void *)((unsigned long)item |
			((unsigned long)*pslot & RADIX_TREE_DIRECT_PTR)));
}

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] radix-tree: fix radix_tree_replace_slot

[Lee Schermerhorn]

On Tue, 2006-08-22 at 14:06 -0700, Christoph Lameter wrote:
> On Tue, 22 Aug 2006, Lee Schermerhorn wrote:
> 
> >   * @item:	new item to store in the slot.
> > + *
> > + * For use with radix_tree_lookup_slot().  Caller must hold tree write locked
> > + * across slot lookup and replacement.
> >   */
> >  static inline void radix_tree_replace_slot(void *pslot, void *item)
> >  {
> >  	void *slot = *(void **)pslot;
> >  	BUG_ON(radix_tree_is_direct_ptr(item));
> > -	rcu_assign_pointer(slot,
> > +	rcu_assign_pointer(*(void **)pslot,
> >  		(void *)((unsigned long)item |
> >  			((unsigned long)slot & RADIX_TREE_DIRECT_PTR)));
>                                         ^^^^ Is this a legit use of slot?
> 
> >  }
> > 
> 
> Would it not be better to change the calling conventions of 
> radix_tree_replace_slot? It should get passsed a void **pslot right?
> 
> static inline void radix_tree_replace_slot(void **pslot, void *item)
> {
> 	BUG_ON(radix_tree_is_direct_ptr(item));
> 	rcu_assign_pointer(*pslot,
> 		(void *)((unsigned long)item |
> 			((unsigned long)*pslot & RADIX_TREE_DIRECT_PTR)));
> }
> 

I did consider that, and I looked at where the value of pslot came from
[radix_tree_lookup_slot()] and all of the casts and other uses of that
value.  I decided to limit the change to the one line that I submitted.
I don't actually recall my reasoning now.  Probably to maintain the
symmetry of _deref_slot() and _replace_slot().

Your suggestion certainly looks cleaner.  Could/should also change
_deref_slot()'s arg to 'void **pslot' and save a cast?

Lee

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] radix-tree: fix radix_tree_replace_slot

[Nick Piggin]

Lee Schermerhorn wrote:
> I was waiting to hear from Nick on this, but I understand that he has
> severely injured one hand, restricting his keyboard access for a while. 

Yeah sorry Lee, ping times have gone up and throughput down.

This does look like the right fix to me. Thanks very much for tracking
it down. Both these patches are

Acked-by: Nick Piggin <npiggin@suse.de>

BTW. I'll have to do a little rework on the radix tree to get the
lockless pagecache patches working properly after the direct-data
patches (based on review feedback)... that will take me a while :(

In the meantime, RCU radix tree isn't getting any lock-free testing
because everything still takes tree_lock... I wonder if Andrew would
be brave enough to lift the tree_lock from mm/readahead.c ?

-- 
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] radix-tree: fix radix_tree_replace_slot

[Paul E. McKenney]

On Tue, Aug 22, 2006 at 04:25:17PM -0400, Lee Schermerhorn wrote:
> Andrew:
> 
> I was waiting to hear from Nick on this, but I understand that he has
> severely injured one hand, restricting his keyboard access for a while. 
> 
> Christoph has been too swamped to take a look, either.   So, having
> tested it myself, I'll send it on.
> 
> Paul:
> 
> could you take a look at this one.  Also, I'll be sending another
> rcu-radix-tree "cleanup" patch that I'd like your opinion on.

Color me blind -- I certainly missed this one earlier.

Yes, the original is certainly not very functional...

						Thanx, Paul

> Lee
> 
> Fix radix tree direct slot replacement - 2.6.18-rc4-mm2
> 
> radix_tree_replace_slot() was assigning to local variable 'slot'
> instead of to where pslot pointed.  Changed to directly replace
> location pointed to by argument pslot.
> 
> Added comments specifying required locking.
> 
> Note that we do not need to rcu_dereference() the slot to
> obtain the direct pointer flag, as we hold the tree write locked.
> 
> Fixes the migration corruption that we were seeing since the
> rcu-radix-tree patches went in.  With this patch, we can back out
> page-migration-replace-radix_tree_lookup_slot-with-radix_tree_lockup.patch
> to use the more efficient direct access to radix tree slot.
> 
> Signed-off-by:  Lee Schermerhorn <lee.schermerhorn@hp.com>
> 
>  include/linux/radix-tree.h |    5 ++++-
>  1 files changed, 4 insertions(+), 1 deletion(-)
> 
> Index: linux-2.6.18-rc4-mm2/include/linux/radix-tree.h
> ===================================================================
> --- linux-2.6.18-rc4-mm2.orig/include/linux/radix-tree.h	2006-08-22 14:30:38.000000000 -0400
> +++ linux-2.6.18-rc4-mm2/include/linux/radix-tree.h	2006-08-22 14:36:54.000000000 -0400
> @@ -133,12 +133,15 @@ static inline void *radix_tree_deref_slo
>   * radix_tree_replace_slot	- replace item in a slot
>   * @pslot:	pointer to slot, returned by radix_tree_lookup_slot
>   * @item:	new item to store in the slot.
> + *
> + * For use with radix_tree_lookup_slot().  Caller must hold tree write locked
> + * across slot lookup and replacement.
>   */
>  static inline void radix_tree_replace_slot(void *pslot, void *item)
>  {
>  	void *slot = *(void **)pslot;
>  	BUG_ON(radix_tree_is_direct_ptr(item));
> -	rcu_assign_pointer(slot,
> +	rcu_assign_pointer(*(void **)pslot,
>  		(void *)((unsigned long)item |
>  			((unsigned long)slot & RADIX_TREE_DIRECT_PTR)));
>  }
> 
> 

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>