D.1 Sleepable RCU Implementation

Figure: Sleeping While RCU Reading Considered Harmful
\resizebox{3in}{!}{\includegraphics{cartoons/RCUCallbacks}}

Classic RCU requires that read-side critical sections obey the same rules obeyed by the critical sections of pure spinlocks: blocking or sleeping of any sort is strictly prohibited. This has frequently been an obstacle to the use of RCU, and Paul has received numerous requests for a ``sleepable RCU'' (SRCU) that permits arbitrary sleeping (or blocking) within RCU read-side critical sections. Paul had previously rejected all such requests as unworkable, since arbitrary sleeping in RCU read-side could indefinitely extend grace periods, which in turn could result in arbitrarily large amounts of memory awaiting the end of a grace period, which finally would result in disaster, as fancifully depicted in Figure [*], with the most likely disaster being hangs due to memory exhaustion. After all, any concurrency-control primitive that could result in system hangs -- even when used correctly - does not deserve to exist.

However, the realtime kernels that require spinlock critical sections be preemptible [Mol05] also require that RCU read-side critical sections be preemptible [MS05]. Preemptible critical sections in turn require that lock-acquisition primitives block in order to avoid deadlock, which in turns means that both RCU's and spinlocks' critical sections be able to block awaiting a lock. However, these two forms of sleeping have the special property that priority boosting and priority inheritance may be used to awaken the sleeping tasks in short order.

Nevertheless, use of RCU in realtime kernels was the first crack in the tablets of stone on which were inscribed ``RCU read-side critical sections can never sleep''. That said, indefinite sleeping, such as blocking waiting for an incoming TCP connection, is strictly verboten even in realtime kernels.

Quick Quiz D.1: Why is sleeping prohibited within Classic RCU read-side critical sections? End Quick Quiz

Quick Quiz D.2: Why not permit sleeping in Classic RCU read-side critical sections by eliminating context switch as a quiescent state, leaving user-mode execution and idle loop as the remaining quiescent states? End Quick Quiz



Subsections
Paul E. McKenney 2011-12-16