[linuxkernelnewbies] The design of preemptible read-copy-update [LWN.net]

[Peter Teoh]

Full article see: http://lwn.net/Articles/253651/ (only partial extraction here) October 8, 2007 This article was contributed by Paul McKenney This document walks through the design of preemptible RCU. Introduction Read-copy update (RCU) is a synchronization API that is sometimes used in place of reader-writer locks. RCU's read-side primitives offer extremely low overhead and deterministic execution time. The downside of this deterministic read-side execution time is that RCU updaters cannot block RCU readers. This means that RCU updaters can be expensive, as they must leave old versions of the data structure in place to accommodate pre-existing readers. Furthermore, these old versions must be reclaimed after all pre-existing readers complete. A time period during which all such pre-existing readers complete is called a "grace period". The Linux kernel offers a number of RCU implementations, the first such implementation being called "Classic RCU". More material introducing RCU may be found in the Documentation/RCU directory in any recent Linux source tree, or at Paul McKenney's RCU page. The RCU implementation for the -rt patchset is unusual in that it permits read-side critical sections to be preempted and to be blocked waiting for locks. However, it does not handle general blocking (for example, via the wait_event() primitive): if you need that, you should instead use SRCU. In contrast to SRCU, preemptible RCU only permits blocking within primitives that are both subject to priority inheritance and non-blocking in a non-CONFIG_PREEMPT kernel. This ability to acquire blocking locks and to be preempted within RCU read-side critical sections is required for the aggressive real-time capabilities provided by Ingo Molnar's -rt patchset. However, the initial preemptible RCU implementation that was added to -rt in August 2005 has some limitations, including: Its read-side primitives cannot be called from within non-maskable interrupt (NMI) or systems-management interrupt handlers. Its read-side primitives use both atomic instructions and memory barriers, both of which have excessive overhead. It does no priority boosting of RCU read-side critical sections (however, this has been described previously, and so will not be discussed further here). The new preemptible RCU implementation that was submitted to LKML (most recently with this patch as of this writing) removes these limitations, and this document describes its design. Quick Quiz 1: Why is it important that blocking primitives called from within a preemptible-RCU read-side critical section be subject to priority inheritance? Quick Quiz 2: Could the prohibition against using primitives that would block in a non-CONFIG_PREEMPT kernel be lifted, and if so, under what conditions? Conceptual RCU Understanding and validating an RCU implementation is much easier given a view of RCU at the lowest possible level. In contrast with other RCU documentation, the goal of this section is not to help you understand how to use RCU, but rather to understand the most basic concurrency requirements that an RCU implementation must support. 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. This is illustrated by the following picture, 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? It must extend the grace period, perhaps as shown below: 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.