Documentation/RCU/RTFP.txt

Source file repositories/reference/linux-study-clean/Documentation/RCU/RTFP.txt

File Facts

System
Linux kernel
Corpus path
Documentation/RCU/RTFP.txt
Extension
.txt
Size
86206 bytes
Lines
2813
Domain
Support Tooling And Documentation
Bucket
Documentation
Inferred role
Support Tooling And Documentation: exported/initcall integration point
Status
integration implementation candidate

Why This File Exists

Repository support layer: documentation, build tooling, samples, user-space helper tools, generated initramfs support, licenses, and validation utilities.

Dependency Surface

Detected Declarations

Annotated Snippet

Read the Fscking Papers!


This document describes RCU-related publications, and is followed by
the corresponding bibtex entries.  A number of the publications may
be found at http://www.rdrop.com/users/paulmck/RCU/.  For others, browsers
and search engines will usually find what you are looking for.

The first thing resembling RCU was published in 1980, when Kung and Lehman
[Kung80] recommended use of a garbage collector to defer destruction
of nodes in a parallel binary search tree in order to simplify its
implementation.  This works well in environments that have garbage
collectors, but most production garbage collectors incur significant
overhead.

In 1982, Manber and Ladner [Manber82,Manber84] recommended deferring
destruction until all threads running at that time have terminated, again
for a parallel binary search tree.  This approach works well in systems
with short-lived threads, such as the K42 research operating system.
However, Linux has long-lived tasks, so more is needed.

In 1986, Hennessy, Osisek, and Seigh [Hennessy89] introduced passive
serialization, which is an RCU-like mechanism that relies on the presence
of "quiescent states" in the VM/XA hypervisor that are guaranteed not
to be referencing the data structure.  However, this mechanism was not
optimized for modern computer systems, which is not surprising given
that these overheads were not so expensive in the mid-80s.  Nonetheless,
passive serialization appears to be the first deferred-destruction
mechanism to be used in production.  Furthermore, the relevant patent
has lapsed, so this approach may be used in non-GPL software, if desired.
(In contrast, implementation of RCU is permitted only in software licensed
under either GPL or LGPL.  Sorry!!!)

In 1987, Rashid et al. described lazy TLB-flush [RichardRashid87a].
At first glance, this has nothing to do with RCU, but nevertheless
this paper helped inspire the update-side batching used in the later
RCU implementation in DYNIX/ptx.  In 1988, Barbara Liskov published
a description of Argus that noted that use of out-of-date values can
be tolerated in some situations.  Thus, this paper provides some early
theoretical justification for use of stale data.

In 1990, Pugh [Pugh90] noted that explicitly tracking which threads
were reading a given data structure permitted deferred free to operate
in the presence of non-terminating threads.  However, this explicit
tracking imposes significant read-side overhead, which is undesirable
in read-mostly situations.  This algorithm does take pains to avoid
write-side contention and parallelize the other write-side overheads by
providing a fine-grained locking design, however, it would be interesting
to see how much of the performance advantage reported in 1990 remains
today.

At about this same time, Andrews [Andrews91textbook] described ``chaotic
relaxation'', where the normal barriers between successive iterations
of convergent numerical algorithms are relaxed, so that iteration $n$
might use data from iteration $n-1$ or even $n-2$.  This introduces
error, which typically slows convergence and thus increases the number of
iterations required.  However, this increase is sometimes more than made
up for by a reduction in the number of expensive barrier operations,
which are otherwise required to synchronize the threads at the end
of each iteration.  Unfortunately, chaotic relaxation requires highly
structured data, such as the matrices used in scientific programs, and
is thus inapplicable to most data structures in operating-system kernels.

In 1992, Henry (now Alexia) Massalin completed a dissertation advising
parallel programmers to defer processing when feasible to simplify
synchronization [HMassalinPhD].  RCU makes extremely heavy use of
this advice.

In 1993, Jacobson [Jacobson93] verbally described what is perhaps the
simplest deferred-free technique: simply waiting a fixed amount of time

Annotation

Implementation Notes