From: Paul McKenney <Paul.McK<enney@us...> - 2000-12-21 21:26:45
I believe that read-copy update will be useful in the Linux kernel as it
pushes up into the 8-16x arena for general workloads. Read-copy update is
a method of accessing and updating read-mostly data structures that has
been used in production in Sequent's Dynix/PTX since 1993. A variant of
read-copy update was independently developed by U of Toronto and IBM
Research in the "Tornado" and "K42" projects.
Read-copy update can be thought of as a reader-writer lock where the
readers take no action: they execute the same sequence of code that they
would on a single-threaded environment without interrupts. No locks, no
disabling of interrupts. The writers use some primitives that allow them
to verify that no reader still referencing a given element that had
previously been removed from the data structure. (See references below for
Since the readers do not acquire locks, read-copy update can simply
deadlock avoidance. It can also simplify races that occur when tearing
down data structures that are used to handle packet receptions from
networks (like Internet) that can regenerate old duplicates of earlier
packets or that can delay packet transmission (e.g., due to congestion).
Read-copy update has the distinction of being one of a very few algorithms
developed for PTX that improved both single-CPU speed and high-end scaling.
The former is because interrupts no longer need to be disabled as much, the
latter is because fewer locks need be acquired.
The PTX version of read-copy update was described in the 1998 conference on
Parallel and Distributed Computing Systems in a paper entitled "Read-Copy
Update: Using Execution History to Solve Concurrency Problems" by myself
and Jack Slingwine (see
http://www.rdrop.com/users/paulmck/paper/rclockpdcsproof.pdf for revisions
of this paper). The Tornado/K42 version was described in the 1999 OSDI in
a paper entitled "Tornado: Maximizing Locality and Concurrency in a Shared
Memory Multiprocessor Operating System" by Ben Gamsa, Orran Krieger,
Jonathon Appavoo, and Michael Stumm.
I believe that read-copy update will be very helpful to increase Linux's
ability to scale, while also keeping Linux's great single-CPU performance.
[sorry for the late answer, I missed your mail earlier and only found it now]
On Thu, Dec 21, 2000 at 01:25:42PM -0800, Paul McKenney wrote:
> I believe that read-copy update will be very helpful to increase Linux's
> ability to scale, while also keeping Linux's great single-CPU performance.
Thanks a lot for these references. I have not 100% digested your paper
yet, but it looks very useful so far. A few datastructures
in Linux come immediately to mind where this approach could help a lot:
e.g. Linux 2.4 networking and VFS have developed far too many reference
counters in the recent SMP work, causing lots of locked cycles because
these need to be updated atomically. Another very ugly problem where it
could be used is the module unload problem: with the drop of the big kernel
lock module unloading and kernel code often runs completely multithreaded,
which causes lots of interesting races (the current fixes is adding even
more reference counters and even module pointers to all kind of shared
objects, slow and ugly). It would be very exciting to clean all that mess up.
Linux did go a bit in this direction already with the big-reader locks
(see include/linux/brlock.h in a 2.4 tree). We also considered stop-the-world
schemes for really infrequent events (like the change of the ip protocol table),
but forgot it because on big CPU systems it is possible that such an operation
would never succeed.
The quiescent state approach looks much better than the brlocks of course.