10.3.4.10 Summary of Toy RCU Implementations

If you made it this far, congratulations! You should now have a much clearer understanding not only of RCU itself, but also of the requirements of enclosing software environments and applications. Those wishing an even deeper understanding are invited to read Appendix [*], which presents some RCU implementations that have seen extensive use in production.

The preceding sections listed some desirable properties of the various RCU primitives. The following list is provided for easy reference for those wishing to create a new RCU implementation.

  1. There must be read-side primitives (such as rcu_read_lock() and rcu_read_unlock()) and grace-period primitives (such as synchronize_rcu() and call_rcu()), such that any RCU read-side critical section in existence at the start of a grace period has completed by the end of the grace period.
  2. RCU read-side primitives should have minimal overhead. In particular, expensive operations such as cache misses, atomic instructions, memory barriers, and branches should be avoided.
  3. RCU read-side primitives should have $O\left(1\right)$ computational complexity to enable real-time use. (This implies that readers run concurrently with updaters.)
  4. RCU read-side primitives should be usable in all contexts (in the Linux kernel, they are permitted everywhere except in the idle loop). An important special case is that RCU read-side primitives be usable within an RCU read-side critical section, in other words, that it be possible to nest RCU read-side critical sections.
  5. RCU read-side primitives should be unconditional, with no failure returns. This property is extremely important, as failure checking increases complexity and complicates testing and validation.
  6. Any operation other than a quiescent state (and thus a grace period) should be permitted in an RCU read-side critical section. In particular, non-idempotent operations such as I/O should be permitted.
  7. It should be possible to update an RCU-protected data structure while executing within an RCU read-side critical section.
  8. Both RCU read-side and update-side primitives should be independent of memory allocator design and implementation, in other words, the same RCU implementation should be able to protect a given data structure regardless of how the data elements are allocated and freed.
  9. RCU grace periods should not be blocked by threads that halt outside of RCU read-side critical sections. (But note that most quiescent-state-based implementations violate this desideratum.)

Quick Quiz 10.60: Given that grace periods are prohibited within RCU read-side critical sections, how can an RCU data structure possibly be updated while in an RCU read-side critical section? End Quick Quiz

Paul E. McKenney 2011-12-16