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

From: Paul McKenney (
Date: Sat Oct 13 2001 - 09:42:49 EST

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


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:

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:

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
More majordomo info at
Please read the FAQ at

This archive was generated by hypermail 2b29 : Mon Oct 15 2001 - 21:00:49 EST