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

["Paul McKenney" <Paul.McKenney@us.ibm.com>]

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