This document describes how to use the Read-Copy Update (RCU) mechanism in the Linux kernel for scalable mutual exclusion. The HOWTO provides examples and explains the interfaces associated with RCU. It also prepares you to save cycles using RCU.
Read-Copy Update (RCU) is a mutual exclusion primitive that takes advantage of the event-driven nature of operating systems and provides a way to read data structures shared between CPUs at zero cost. For read-mostly data structures, it reduces contention on conventional locks and lock cache line bouncing by allowing lock-free reading of data.
RCU allows you to read a shared data structure as if there is no other CPU accessing it. When you need to update the data structure, you can update the global pointer to the data and keep the old copy until all the threads currently executing inside the kernel have completed. The updated pointer ensures that none of the CPUs have any remaining references, so the old copy can be deleted.
The following list explains why you should use the RCU mechanism. It also explains the motivation for RCU's development.
CPU speeds have been increasing by a factor of from 1.5x to 2x per year for more than a decade. However, interconnect speeds (printed circuit boards and buses) have only been increasing by roughly 15% per year over the same period. This increase in overhead provides the motivation for constructing mutual-exclusion schemes that do not rely so heavily on communication over the relatively slow interconnects between the relatively fast CPUs.
The RCU mechanism allows locking operations to be eliminated on read accesses to the data it protects.
The RCU mechanism is not as susceptible to deadlock as are explicit lock operations. The reduced susceptibility to deadlock results in reduction in or elimination of code that would otherwise be required to detect and repair or to avoid deadlocks. This reduction also reduces software development and maintenance costs.
By allowing lock-free reading of data, RCU avoids thrashing of shared lock cache lines. In read-mostly situations, lock-free reading provides significant benefits. One such example is the synthetic "chat" benchmark where a number of cloned tasks share the files_struct. Even though a reader-writer lock is used to read the file pointer in fget(), the bouncing of the lock cache line severely impacts the performance when a large number of CPUs are used. Using RCU, fget() can look up the file pointer without acquiring any lock and that significantly improves the performance.
Additional information about RCU can be found on the RCU homepage at http://lse.sourceforge.net/locking/rcupdate.html. The white paper for RCU for Linux was published at Ottawa Linux Symposium, 2001. This paper is at http://lse.sourceforge.net/locking/rclock_OLS.2001.05.01c.sc.pdf.