Read-copy-update (RCU) is a mutual exclusion technique which can operate
without locking most of the time. It can yield significant performance
benefits when the data to be protected is accessed via a pointer,
is read frequently, changed rarely, and references to the
structure are not held while a kernel thread sleeps. The core idea behind RCU is
that, when the data requires updating, a pointer to a new structure
containing the new data can be stored immediately. The old structure
containing the outdated data can then be freed at leisure, after it is
certain that no process in the system holds a reference to that structure.
For details on the ideas behind RCU, see this LWN
, or (for many details) this
. Just don't ask SCO, even though they claim to own the technique.
The first step in using RCU within a subsystem is to define a structure
containing the data to be protected. Often that structure already exists;
for example, RCU has been retrofitted into the dentry cache (using
struct dentry), the network routing cache (struct
rtable), and several other, similar contexts. The structures need to
be allocated dynamically and accessed via a pointer - RCU cannot be used
with static structures.
Code which reads data structures protected by RCU need only take a couple
of simple precautions:
- A call to rcu_read_lock() should be made before accessing
the data, and rcu_read_unlock() should be called afterward.
This call disables preemption (and does nothing else) - a fast but
necessary operation for RCU to work properly. These calls (along with
the rest of the RCU definitions) are found in
- The code must not sleep while the "RCU read lock" is held.
Thus, code which reads an RCU-protected data structure will look something
struct my_stuff *stuff;
stuff = find_the_stuff(args...);
do_something_with(stuff); /* Cannot sleep */
do_something_else_with(stuff); /* ditto */
The write side of RCU is a little more complicated, but not that difficult.
To update a data structure, the code starts by allocating a new copy of
that structure, and filling in the new information. The code should then
replace the pointer to the outdated structure with the new one, keeping a
copy of the old pointer. After this operation, kernel code running on any
other processor will find the new version of the structure. The old one
cannot yet be freed, however, since it is possible that another processor
is still using it.
The code should arrange to dispose of the old structure when it is known
that it cannot be referenced anywhere else in the system. That is done
through a call to call_rcu():
void call_rcu(struct rcu_head *head,
void (*func)(void *arg),
The calling code must provide an rcu_head structure, but need not
initialize it in any way. Usually, that structure is embedded within the
larger structure protected by RCU. The function func will be
called when the structure can be safely freed, with arg as its one
argument. All that func need do, normally, is call something like
kfree() to free up the structure.
The RCU algorithm works by waiting until every processor in the system has
scheduled at least once. Since the rules require that references to
RCU-protected structures cannot be held over sleeps, no processor can
possibly hold a reference to an old structure after it has scheduled. When
all processors have scheduled (after the pointer change), references to the
old structure can not
exist, and the structure can be freed.
For what it's worth, the
RCU code exports the "wait for everybody to schedule" functionality, should
it be useful elsewhere. To perform this wait, one need only make a call to
to post comments)