Glossary

The following definitions help illuminate the concepts underlying RCU.

Live Variable:

A variable that might be accessed before it is next modified, so that its current value has some possibility of influencing future execution state.

Dead Variable:

A variable that will be modified before it is next accessed, so that its current value cannot possibly have any influence over future execution state.

Critical Section:

A region of code that is protected from outside interference by some locking mechanism, such as spinlocks or RCU.

Read-Side Critical Section:

A region of code that is protected from other CPUs' modifications, but which allows multiple CPUs to read simultaneously.

Temporary Variable:

A variable that is only live inside a critical section. One example is an auto variable used as a pointer while traversing a linked list.

Permanent Variable:

A variable that is live outside of critical sections. One example would be the header for a linked list. Although it is possible for the same variable to be temporary sometimes and permanent at other times, this practice can lead to confusion, so is not generally recommended. Relying on the register-allocation capabilities of modern optimizing compilers is usually a far better strategy.

Quiescent State:

A point in the code where all of the current CPU's temporary variables that were previously in use in a critical section are dead. In a non-preemptive Linux kernel, a context switch is a quiescent state for CPUs. In a preemptive Linux kernel, rcu_read_lock() and rcu_read_unlock() suppress preemption for short read-side critical sections, so that context switch is still a quiescent state with respect to these read-side critical sections. Although there are implementations of RCU that do not require preemption to be suppressed [Gamsa99,McK02a], they can be prone to excessively long grace periods.

Grace Period:

Time interval during which all CPUs pass through at least one quiescent state. The key property of a grace period is that the values that were contained in any temporary variable in use in a critical section at the beginning of the grace period cannot possibly have any direct effect after the end of the grace period. This property will be examined more closely in the next section. Note that any time interval containing a grace period is itself a grace period.