Check out the new USENIX Web site. next up previous
Next: Reader-Writer-Locking/RCU Analogy Up: Background Previous: Concepts


Figure 4: RCU API
\begin{figure}{\tt\scriptsize\begin{verbatim}void synchronize_kernel(void);
...oid rcu_read_lock(void);
void rcu_read_unlock(void);\end{verbatim}}

Figure 4 shows the external API for RCU. The synchronize_kernel() function blocks for a full grace period. This is a simple, easy-to-use function, but imposes expensive context-switch overhead on its caller. It also cannot be called with locks held or from softirq and irq (interrupt) contexts.

Another approach, taken by call_rcu(), is to schedule a callback function func to be called with argument arg after the end of a full grace period. Since call_rcu() never sleeps, it may be called with locks held. It may also be called from the softirq and irq contexts. The call_rcu() function uses its struct rcu_head argument to remember the specified callback function (in the func field) and argument (in the arg field) for the duration of the grace period. At the end of the grace period, the RCU subsystem invokes the function pointed to by the func field, passing it the contents of the arg field. An rcu_head is often placed within a structure being protected by RCU, eliminating the need to separately allocate it.

The primitives rcu_read_lock() and rcu_read_unlock() demark a read-side RCU critical section, but generate no code in non-preemptive kernels. In preemptive kernels, they disable preemption within the critical section, which is required because both synchronize_kernel() and call_rcu() declare the grace period to be over once each CPU has completed a context switch. Suppressing preemption during the read-side RCU critical section prevents the crashes that could result from such prematurely ending grace periods. There is a patch that implements a proposed call_rcu_preempt() [McK02a] that tolerates preemption in read-side critical sections (based on the K42 implementation [Gamsa99]), but at this writing, there are no RCU uses envisioned in Linux that could tolerate the extremely long grace periods that might result from preemption on a busy system.

Figure 5: RCU List API
\begin{figure}{\tt\scriptsize\begin{verbatim}list_add_rcu(struct list_head *ne...
struct list_head *n,
struct list_head *head);\end{verbatim}}

Modern microprocessors, particularly the DEC/Compaq/HP Alpha, feature very weak memory consistency models. These models require use of special ``memory barrier'' instructions. However, since proper use of these instructions is often difficult to understand and even more difficult to build good test suites for, there is an extension to the Linux list-manipulation API for use with RCU, as shown in Figure 5. Each primitive in this extension is equivalent to its non-RCU counterpart, but with the addition of whatever memory-barrier instructions are required on the machine in question [Spraul01].

RCU may be applied to data structures other than lists, but in such cases, memory-barrier instructions must be used explicitly. An example of such a situation is shown in Section 4.5.

next up previous
Next: Reader-Writer-Locking/RCU Analogy Up: Background Previous: Concepts
Paul McKenney 2003-03-28