Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion

[Dipankar Sarma]

On Fri, Oct 12, 2001 at 09:56:58AM -0700, Linus Torvalds wrote:
> 
> Yes. With maybe
> 
> 	non_preempt()
> 	..
> 	preempt()
> 
> around it for the pre-emption patches.

Yes. While in the read side, preemption will have to be disabled
to prevent local pointers being carried across context switches.
It isn't impossible to allow preemption, but that makes the
quiescent point detection logic much more complicated.

> 
> However, you also need to make your free _free_ be aware of the count.
> Which means that the current RCU patch is really unusable for this. You
> need to have the "count" always in a generic place (put it with the hash),
> and your schedule-time free needs to do
> 
> 	if (atomic_read(&count))
> 		skip_this_do_it_next_time
> 
> which starts getting complicated (it means your RCU free now has to have a
> notion of "next time" - just leaving the RCU active will slow down
> scheduling for as long as any reader holds on to an entry). So your
> unread() path probably has to be
> 
> 	if (atomic_dec_and_test(&count))
> 		free_it()
> 
> and the act of hashing should add a count and unhashing should delete a
> count (so that the reader doesn't free it while it is hashed).

Perhaps I am missing something here but shouldn't the refcount based 
schemes anyway have to do this with or without RCU ? If you do

	unhash
	if (atomic_dec_and_test(&count))
		free_it();

the isn't it that if refcount is not 0, sometime later it will have to be 
cleaned up by some garbage collection scheme ? Whatever that scheme is, 
it still needs to be made certain that the element is not back in the 
hash table.  It seems to me that with RCU the same logic can be made use of.
So instead of doing 

	if (atomic_dec_and_test(&count))
		rcu_free_it()

you may do 

	if (atomic_dec_and_test(&count))
		free_it();

where in free_it()

	if (atomic_read(&count))
		return;
	rcu_free_it();

Of course, there may be more complicated freeing schemes for which
we may need additional logic just like you suggested.

> 
> Do that, and the RCU patches may start looking usable for the real world.
> 

One RCU example for refcount + hash table is at
http://lse.sourceforge.net/locking/patches/rt_rcu-2.4.6-02.patch
(ipv4 route cache). 

Thanks
Dipankar
-- 
Dipankar Sarma  <[e-mail]> Project: http://lse.sourceforge.net
Linux Technology Center, IBM Software Lab, Bangalore, India.