Understanding and validating an RCU implementation is much easier given
a view of RCU at the lowest possible level.
This section gives a very brief overview of the
most basic concurrency requirements that an RCU implementation must
support.
For more detail, please see
Section .
RCU implementations must obey the following rule: if any statement in a given RCU read-side critical section precedes a grace period, then all statements in that RCU read-side critical section must complete before that grace period ends.
This is illustrated by
Figure ,
where time advances from left to right.
The red "Removal" box represents the update-side critical section that
modifies the RCU-protected data structure, for example, via
list_del_rcu(); the large yellow "Grace Period" box
represents a grace period (surprise!) which might be invoked via
synchronize_rcu(), and the green "Reclamation" box
represents freeing the affected data element,
perhaps via kfree().
The blue "Reader" boxes each represent an RCU read-side critical section,
for example, beginning with rcu_read_lock() and ending with
rcu_read_unlock().
The red-rimmed "Reader" box is an example of an illegal situation:
any so-called RCU implementation that permits a read-side critical section
to completely overlap a grace period is buggy, since the updater might
free up memory that this reader is still using.
So, what is the poor RCU implementation to do in this situation?
It must extend the grace period, perhaps as shown in
Figure .
In short, the RCU implementation must ensure that any
RCU read-side critical sections in progress at the start of a given grace
period have completely finished, memory operations and all, before that
grace period is permitted to complete.
This fact allows RCU validation to be extremely focused: simply demonstrate
that any RCU read-side critical section in progress at the beginning of
a grace period must terminate before that grace period ends, along with
sufficient barriers to prevent either the compiler or the CPU from undoing
the RCU implementation's work.
Paul E. McKenney 2011-12-16