D.4.3.2 Conceptual Validation

Because neither rcu_read_lock() nor rcu_read_unlock() contain memory barriers, the RCU read-side critical section can bleed out on weakly ordered machines. In addition, the relatively loose coupling of this RCU implementation permits CPUs to disagree on when a given grace period starts and ends. This leads to the question as to how long a given RCU read-side critical section can possibly extend relative to the grace-period state machine.

Figure: Preemptible RCU Worst-Case Scenario
\resizebox{3in}{!}{\includegraphics{appendix/rcuimpl/RCUpreemptValidation}}

The worst-case scenario is shown in Figure [*]. Here, CPU 0 is executing the shortest possible removal and reclamation sequence, while CPU 1 executes the longest possible RCU read-side critical section. Because the callback queues are advanced just before acknowledging a counter flip, the latest that CPU 0 can execute its list_del_rcu() and call_rcu() is just before its scheduling-clock interrupt that acknowledges the counter flip. The call_rcu() invocation places the callback on CPU 0's next list, and the interrupt will move the callback from the next list to the wait[0] list. This callback will move again (from the wait[0] list to the wait[1] list) at CPU 0's first scheduling-clock interrupt following the next counter flip. Similarly, the callback will move from the wait[1] list to the done list at CPU 0's first scheduling-clock interrupt following the counter flip resulting in the value 3. The callback might be invoked immediately afterward.

Meanwhile, CPU 1 is executing an RCU read-side critical section. Let us assume that the rcu_read_lock() follows the first counter flip (the one resulting in the value 1), so that the rcu_read_lock() increments CPU 1's rcu_flipctr[1] counter. Note that because rcu_read_lock() does not contain any memory barriers, the contents of the critical section might be executed early by the CPU. However, this early execution cannot precede the last memory barrier executed by CPU 1, as shown on the diagram. This is nevertheless sufficiently early that an rcu_dereference() could fetch a pointer to the item being deleted by CPU 0's list_del_rcu().

Because the rcu_read_lock() incremented an index-1 counter, the corresponding rcu_read_unlock() must precede the "old counters zero" event for index 1. However, because rcu_read_unlock() contains no memory barriers, the contents of the corresponding RCU read-side critical section (possibly including a reference to the item deleted by CPU 0) can be executed late by CPU 1. However, it cannot be executed after CPU 1's next memory barrier, as shown on the diagram. Because the latest possible reference by CPU 1 precedes the earliest possible callback invocation by CPU 0, two passes through the grace-period state machine suffice to constitute a full grace period, and hence it is safe to do:



    #define GP_STAGES 2


Quick Quiz D.62: Suppose that the irq disabling in rcu_read_lock() was replaced by preemption disabling. What effect would that have on GP_STAGES? End Quick Quiz

Quick Quiz D.63: Why can't the rcu_dereference() precede the memory barrier? End Quick Quiz

Paul E. McKenney 2011-12-16