D. Read-Copy Update Implementations
Keywords: perfbook_html

#
D. Read-Copy Update Implementations

This appendix describes several fully functional production-quality RCU implementations. Understanding of these implementations requires a thorough understanding of the material in Chapters and , as well as a reasonably good understanding of the Linux kernel, the latter of which may be found in several textbooks and websites [BC05,CRKH05,Cor08,Lov05].

If you are new to RCU implementations, you should start with the simpler ``toy'' RCU implementations that may be found in Section .

Section presents ``Sleepable RCU'', or SRCU, which allows SRCU readers to sleep arbitrarily. This is a simple implementation, as production-quality RCU implementations go, and a good place to start learning about such implementations.

Section gives an overview of a highly scalable implementation of Classic RCU, designed for SMP systems sporting thousands of CPUs. Section takes the reader on a code walkthrough of this same implementation (as of late 2008).

Finally, Section provides a detailed view of the preemptible RCU implementation used in real-time systems.

Subsections

- D.1 Sleepable RCU Implementation
  - D.1.1 SRCU Implementation Strategy
    - D.1.1.1 Abolish Asynchronous Grace-Period APIs
    - D.1.1.2 Isolate Grace-Period Detection
  - D.1.2 SRCU API and Usage
    - D.1.2.1 Initialization and Cleanup
    - D.1.2.2 Read-Side Primitives
    - D.1.2.3 Update-Side Primitives
    - D.1.2.4 Cleaning Up Safely
  - D.1.3 Implementation
    - D.1.3.1 Data Structures
    - D.1.3.2 Initialization Implementation
    - D.1.3.3 Read-Side Implementation
    - D.1.3.4 Update-Side Implementation
  - D.1.4 SRCU Summary
- D.2 Hierarchical RCU Overview
  - D.2.1 Review of RCU Fundamentals
  - D.2.2 Brief Overview of Classic RCU Implementation
  - D.2.3 RCU Desiderata
  - D.2.4 Towards a More Scalable RCU Implementation
  - D.2.5 Towards a Greener RCU Implementation
  - D.2.6 State Machine
  - D.2.7 Use Cases
    - D.2.7.1 Start a New Grace Period
    - D.2.7.2 Pass Through a Quiescent State
    - D.2.7.3 Announce a Quiescent State to RCU
    - D.2.7.4 Enter and Leave Dynticks Idle Mode
    - D.2.7.5 Interrupt from Dynticks Idle Mode
    - D.2.7.6 NMI from Dynticks Idle Mode
    - D.2.7.7 Note That a CPU is in Dynticks Idle Mode
    - D.2.7.8 Offline a CPU
    - D.2.7.9 Online a CPU
    - D.2.7.10 Detect a Too-Long Grace Period
  - D.2.8 Testing
  - D.2.9 Conclusion
- D.3 Hierarchical RCU Code Walkthrough
  - D.3.1 Data Structures and Kernel Parameters
    - D.3.1.1 Tracking Dyntick State
    - D.3.1.2 Nodes in the Hierarchy
    - D.3.1.3 Per-CPU Data
    - D.3.1.4 RCU Global State
    - D.3.1.5 Kernel Parameters
  - D.3.2 External Interfaces
    - D.3.2.1 Read-Side Critical Sections
    - D.3.2.2 `call_rcu()`
    - D.3.2.3 `rcu_check_callbacks()`
    - D.3.2.4 `rcu_process_callbacks()`
    - D.3.2.5 `rcu_needs_cpu()` and `rcu_cpu_notify()`
  - D.3.3 Initialization
    - D.3.3.1 `rcu_init_levelspread()`
    - D.3.3.2 `rcu_init_one()`
    - D.3.3.3 `__rcu_init()`
  - D.3.4 CPU Hotplug
    - D.3.4.1 `rcu_init_percpu_data()`
    - D.3.4.2 `rcu_online_cpu()`
    - D.3.4.3 `rcu_offline_cpu()`
  - D.3.5 Miscellaneous Functions
  - D.3.6 Grace-Period-Detection Functions
    - D.3.6.1 Noting New Grace Periods
    - D.3.6.2 Noting End of Old Grace Periods
    - D.3.6.3 Starting a Grace Period
    - D.3.6.4 Reporting Quiescent States
  - D.3.7 Dyntick-Idle Functions
    - D.3.7.1 Entering and Exiting Dyntick-Idle Mode
    - D.3.7.2 NMIs from Dyntick-Idle Mode
    - D.3.7.3 Interrupts from Dyntick-Idle Mode
    - D.3.7.4 Checking for Dyntick-Idle Mode
  - D.3.8 Forcing Quiescent States
    - D.3.8.1 Recording and Recalling Dynticks-Idle Grace Period
    - D.3.8.2 Handling Offline and Holdout CPUs
    - D.3.8.3 Scanning for Holdout CPUs
    - D.3.8.4 Code for `force_quiescent_state()`
  - D.3.9 CPU-Stall Detection
  - D.3.10 Possible Flaws and Changes
- D.4 Preemptible RCU
  - 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