D.4.1 Conceptual RCU
Keywords: perfbook_html

##
D.4.1 Conceptual RCU

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.

Figure: Buggy Grace Period From Broken RCU

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?

Figure: Good Grace Period From Correct RCU

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.