D.4 Preemptible RCU
Keywords: perfbook_html

#
D.4 Preemptible RCU

The preemptible RCU implementation 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, which is described in Appendix . 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 [McK05c] had some limitations, including:

1. Its read-side primitives cannot be called from within non-maskable interrupt (NMI) or systems-management interrupt handlers.
2. Its read-side primitives use both atomic instructions and memory barriers, both of which have excessive overhead.
3. It does no priority boosting of RCU read-side critical sections [McK07d].

The new preemptible RCU implementation that accepted into the 2.6.26 Linux kernel removes these limitations, and this appendix describes its design, serving as an update to the LWN article [McK07a]. However, please note that this implementation was replaced with a faster and simpler implementation in the 2.6.32 Linux kernel. This description nevertheless remains to bear witness to the most complex RCU implementation ever devised.

Quick Quiz D.56: Why is it important that blocking primitives called from within a preemptible-RCU read-side critical section be subject to priority inheritance? End Quick Quiz

Quick Quiz D.57: Could the prohibition against using primitives that would block in a non-CONFIG_PREEMPT kernel be lifted, and if so, under what conditions? End Quick Quiz

Subsections

- D.4.1 Conceptual RCU
- D.4.2 Overview of Preemptible RCU Algorithm
  - D.4.2.1 General Approach
  - D.4.2.2 Data Structures
    - D.4.2.2.1 `rcu_ctrlblk`
    - D.4.2.2.2 `rcu_data`
    - D.4.2.2.3 `rcu_flipctr`
    - D.4.2.2.4 `rcu_try_flip_state`
    - D.4.2.2.5 `rcu_try_flip_flag`
    - D.4.2.2.6 `rcu_mb_flag`
  - D.4.2.3 Grace-Period State Machine
    - D.4.2.3.1 Grace-Period State Machine Overview
    - D.4.2.3.2 Grace-Period State Machine Walkthrough
  - D.4.2.4 Read-Side Primitives
    - D.4.2.4.1 `rcu_read_lock()`
    - D.4.2.4.2 `rcu_read_unlock()`
    - D.4.2.4.3 Memory-Barrier Considerations
- D.4.3 Validation of Preemptible RCU
  - D.4.3.1 Testing
  - D.4.3.2 Conceptual Validation
  - D.4.3.3 Formal Validation