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

From: Paul McKenney (
Date: Wed Oct 10 2001 - 11:00:21 EST

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

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