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

Paul McKenney (
Wed, 10 Oct 2001 09:00:21 -0700

> > So I'm still at a loss for what this could actually be _used_. IP
> > Certainly not sockets (which have uniqueness requirements).
> Yes. We used it in IP routing in DYNIX/ptx back then at Sequent as well
> as for Multipath I/O routes for storage. That is all I can remember,
> but Paul will remember and know more about it. Paul ?


RCU was used in the following portions of PTX:

o Distributed lock manager: recovery, lists of callbacks used to
report completions and error conditions to user processes, and
lists of server and client lock data structures.

o TCP/IP: routing tables, interface tables, and protocol-control-block
lists. As Linus suspected, RCU was -not- applied to the socket
data structures. ;-)

o Storage-area network (SAN): routing tables and error-injection
tables (used for stress testing).

o Clustered journalling file systems: in-core inode lists and
distributed-locking data structures.

o Lock-contention measurement: data structure used to map from
spinlock addresses to the corresponding measurement data. (This
was needed since PTX locks are one byte long, and you can't put
much extra data into one byte.)

o Application regions manager (which is a workload-management
subsystem): maintains a list of "regions" into which processes
may be confined.

o Process management: per-process system-call tables and MP trace
data structures used for debuggers that handle multi-threaded

o LAN drivers to resolve races between shutting down a LAN device
and packets being received by that device. (This use is in many
ways similar to that of Rusty's, Anton's, and Greg's hotplug

PTX used RCU on an as-needed basis. K42 made more
pervasive use of a very similar technique.

RCU is definitely -not- a wholesale replacement for all locking.
For example, as Dipankar noted, it can be integrated with reference-count
schemes. It -can- be used to replace reference counts, but only in
cases where no task blocks while holding a reference.

RCU works best in read-mostly data structures. The most common use
is to allow lock-free dereferencing of pointers, for example, removing
the lock on a -list-, keeping locking/reference counts only on the
elements themselves.

In addition, when moving from one element in a list to the next, RCU
allows you to drop the refcnt/lock of the preceding element -before-
traversing the pointer to the next element. This can make the
traversal code a bit simpler.

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