[Lse-tech] read-copy update for Linux

[Paul M. <Pau...@us...>]

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
more details.)

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/rclock/intro/rclock_intro.html and
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.

Thoughts?

                    Thanx, Paul