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

Linus Torvalds (torvalds@transmeta.com)
Fri, 12 Oct 2001 09:56:58 -0700 (PDT)


On Fri, 12 Oct 2001, Rusty Russell wrote:
>
> And the read side is:
> lock
> loopup
> atomic_inc
> unlock
>
> With RCU, read side is:
> loopup
> atomic_inc

Yes. With maybe

non_preempt()
..
preempt()

around it for the pre-emption patches.

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

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

Linus

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/