[lkml]   [2001]   [Oct]   [12]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion
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

if (atomic_dec_and_test(&count))

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))

you may do

if (atomic_dec_and_test(&count))

where in free_it()

if (atomic_read(&count))

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
(ipv4 route cache).

Dipankar Sarma <> Project:
Linux Technology Center, IBM Software Lab, Bangalore, India.
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at
Please read the FAQ at

 \ /
  Last update: 2005-03-22 13:08    [W:0.273 / U:0.004 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site