10.3.1 RCU Fundamentals

Authors: Paul E. McKenney and Jonathan Walpole

Read-copy update (RCU) is a synchronization mechanism that was added to the Linux kernel in October of 2002. RCU achieves scalability improvements by allowing reads to occur concurrently with updates. In contrast with conventional locking primitives that ensure mutual exclusion among concurrent threads regardless of whether they be readers or updaters, or with reader-writer locks that allow concurrent reads but not in the presence of updates, RCU supports concurrency between a single updater and multiple readers. RCU ensures that reads are coherent by maintaining multiple versions of objects and ensuring that they are not freed up until all pre-existing read-side critical sections complete. RCU defines and uses efficient and scalable mechanisms for publishing and reading new versions of an object, and also for deferring the collection of old versions. These mechanisms distribute the work among read and update paths in such a way as to make read paths extremely fast. In some cases (non-preemptible kernels), RCU's read-side primitives have zero overhead.

Quick Quiz 10.6: But doesn't seqlock also permit readers and updaters to get work done concurrently? End Quick Quiz

This leads to the question ``what exactly is RCU?'', and perhaps also to the question ``how can RCU possibly work?'' (or, not infrequently, the assertion that RCU cannot possibly work). This document addresses these questions from a fundamental viewpoint; later installments look at them from usage and from API viewpoints. This last installment also includes a list of references.

RCU is made up of three fundamental mechanisms, the first being used for insertion, the second being used for deletion, and the third being used to allow readers to tolerate concurrent insertions and deletions. Section [*] describes the publish-subscribe mechanism used for insertion, Section [*] describes how waiting for pre-existing RCU readers enabled deletion, and Section [*] discusses how maintaining multiple versions of recently updated objects permits concurrent insertions and deletions. Finally, Section [*] summarizes RCU fundamentals.



Subsections
Paul E. McKenney 2011-12-16