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

Paul McKenney (Paul.McKenney@us.ibm.com)
Sat, 13 Oct 2001 07:42:49 -0700


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

???

Ah! Are you thinking of the trick that associates a reference counter
with each pointer, and where one uses a double-compare-and-swap instruction
to do updates? That is definitely -not- what we are proposing here, since
it is important to avoid writes during read-only traversals.

Instead, we use side information to deduce when it is no longer possible
for there to be any references to a given data structure.

It -is- possible to use RCU in Linux -without- reference counts. See
the Maneesh Soni's FD-management patch and description at:

http://lse.sourceforge.net/locking/patches/files_struct_rcu-2.4.10-04.patch
http://lse.sourceforge.net/locking/files_struct_rcu.txt

The reference counts are needed -only- in cases where references to an
RCU-protected data structure may be held across a sleep. Dipankar Sarma's
IPV4 route-cache lookup patch at:

http://lse.sourceforge.net/locking/patches/rt_rcu-2.4.6-02.patch

is an example use of RCU where reference counts are used, since entries
can be queued.

Thanx, Paul

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