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.
- 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.
- 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.
- RCU read-side primitives should have
computational
complexity to enable real-time use.
(This implies that readers run concurrently with updaters.)
- 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.
- 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.
- 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.
- It should be possible to update an RCU-protected data structure
while executing within an RCU read-side critical section.
- 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.
- 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