Rust Atomics and Locks

About this Book

The Rust programming language is extremely well suited for concurrency, and its ecosystem has many libraries that include lots of concurrent data structures, locks, and more. But implementing those structures correctly can be difficult. Even in the most well-used libraries, memory ordering bugs are not uncommon.

In this practical book, Mara Bos, team lead of the Rust library team, helps Rust programmers of all levels gain a clear understanding of low-level concurrency. You’ll learn everything about atomics and memory ordering and how they're combined with basic operating system APIs to build common primitives like mutexes and condition variables. Once you’re done, you’ll have a firm grasp of how Rust’s memory model, the processor, and the role of the operating system all fit together.

With this guide, you’ll learn:

• How Rust's type system works exceptionally well for programming concurrency correctly
• All about mutexes, condition variables, atomics, and memory ordering
• What happens in practice with atomic operations on Intel and ARM processors
• How locks are implemented with support from the operating system
• How to write correct code that includes concurrency, atomics, and locks
• How to build your own locking and synchronization primitives correctly

Start reading

Code Examples

The code examples from this book are available on GitHub: https://github.com/m-ou-se/rust-atomics-and-locks

Table of Contents

• Foreword by Paul E. McKenney
• Preface
  • Who This Book Is For
  • Overview of the Chapters
  • Code Examples
  • Conventions Used in This Book
  • Acknowledgments
• Chapter 1. Basics of Rust Concurrency
  • Threads in Rust
  • Scoped Threads
  • Shared Ownership and Reference Counting
    • Statics
    • Leaking
    • Reference Counting
  • Borrowing and Data Races
  • Interior Mutability (Cell, RefCell, Mutex and RwLock, Atomics, UnsafeCell)
  • Thread Safety: Send and Sync
  • Locking: Mutexes and RwLocks
    • Rust’s Mutex
    • Lock Poisoning
    • Reader-Writer Lock
  • Waiting: Parking and Condition Variables
    • Thread Parking
    • Condition Variables
  • Summary
• Chapter 2. Atomics
  • Atomic Load and Store Operations
    • Example: Stop Flag
    • Example: Progress Reporting
      • Synchronization
    • Example: Lazy Initialization
  • Fetch-and-Modify Operations
    • Example: Progress Reporting from Multiple Threads
    • Example: Statistics
    • Example: ID Allocation
  • Compare-and-Exchange Operations
    • Example: ID Allocation Without Overflow
    • Example: Lazy One-Time Initialization
  • Summary
• Chapter 3. Memory Ordering
  • Reordering and Optimizations
  • The Memory Model
  • Happens-Before Relationship
    • Spawning and Joining
  • Relaxed Ordering
  • Release and Acquire Ordering
    • Example: Locking
    • Example: Lazy Initialization with Indirection
  • Consume Ordering
  • Sequentially Consistent Ordering
  • Fences
  • Common Misconceptions
  • Summary
• Chapter 4. Building Our Own Spin Lock
  • A Minimal Implementation
  • An Unsafe Spin Lock
  • A Safe Interface Using a Lock Guard
  • Summary
• Chapter 5. Building Our Own Channels
  • A Simple Mutex-Based Channel
  • An Unsafe One-Shot Channel
  • Safety Through Runtime Checks
  • Safety Through Types
  • Borrowing to Avoid Allocation
  • Blocking
  • Summary
• Chapter 6. Building Our Own "Arc"
  • Basic Reference Counting
    • Testing It
    • Mutation
  • Weak Pointers
    • Testing It
  • Optimizing
  • Summary
• Chapter 7. Understanding the Processor
  • Processor Instructions
    • Load and Store
    • Read-Modify-Write Operations
      • x86 lock prefix
      • x86 compare-and-exchange instruction
    • Load-Linked and Store-Conditional Instructions
      • ARM load-exclusive and store-exclusive
      • Compare-and-exchange on ARM
  • Caching
    • Cache Coherence
      • The write-through protocol
      • The MESI protocol
    • Impact on Performance
  • Reordering
  • Memory Ordering
    • x86-64: Strongly Ordered
    • ARM64: Weakly Ordered
    • An Experiment
    • Memory Fences
  • Summary
• Chapter 8. Operating System Primitives
  • Interfacing with the Kernel
  • POSIX
    • Wrapping in Rust
  • Linux
    • Futex
    • Futex Operations
    • Priority Inheritance Futex Operations
  • macOS
    • os_unfair_lock
  • Windows
    • Heavyweight Kernel Objects
    • Lighter-Weight Objects
      • Slim reader-writer locks
    • Address-Based Waiting
  • Summary
• Chapter 9. Building Our Own Locks
  • Mutex
    • Avoiding Syscalls
    • Optimizing Further
    • Benchmarking
  • Condition Variable
    • Avoiding Syscalls
    • Avoiding Spurious Wake-ups
  • Reader-Writer Lock
    • Avoiding Busy-Looping Writers
    • Avoiding Writer Starvation
  • Summary
• Chapter 10. Ideas and Inspiration
  • Semaphore
  • RCU
  • Lock-Free Linked List
  • Queue-Based Locks
  • Parking Lot–Based Locks
  • Sequence Lock
  • Teaching Materials
• Index