Starnix Read-Copy-Update (RCU)

本文档介绍了 Starnix 内核使用的读时复制 (RCU) 同步方法。

背景

Starnix 内核管理着大量由许多线程并发访问的状态。执行 Linux 用户空间代码的任何线程都可以触发系统调用或接收异常，从而导致该特定线程转换到 Starnix 地址空间以执行内核代码。为了高效处理这种高并发级别，Starnix 采用了各种同步机制，包括 Read-Copy-Update (RCU)。

RCU 允许多个线程同时读取共享数据，而不会相互阻塞或阻塞写入者。为了修改共享数据，写入者会先复制数据，然后修改副本，再将副本发布到其他线程，因此得名“读取、复制、更新”。由于线程在更新发生时可能仍在读取旧副本，因此无法立即回收内存。Starnix 会等待所有活跃的读取器完成对旧数据的访问，然后再释放旧数据；此等待时间间隔称为“宽限期”。

RCU 存在以下明显的权衡：

一致性保证较弱：与互斥锁或读/写锁等同步原语相比，RCU 的一致性较弱。使用 RCU 时，写入者修改数据后，读取者可能会在短时间内看到过时的数据。Mutex 和读/写锁可防止这种不一致性，因为写入者必须等待活跃的读取者完成操作才能修改数据，而读取者必须等待活跃的写入者完成操作才能读取数据。
延迟资源回收：与修改后的数据关联的资源不会在写入时立即释放。相反，它们会一直占用内存，直到宽限期结束（即所有未完成的读取操作都已完成）。这样一来，RCU 就类似于垃圾回收器，其中对象终结器会被延迟。

RCU 由 Linux 内核推广，现在已广泛应用于操作系统设计中。它非常适合 Starnix，因为内核工作负载主要是读取，这使得系统能够充分利用 RCU 读取器的效率。此外，Starnix 很少需要严格的一致性，因为它旨在复制 Linux UAPI 的语义。由于 Linux 内核已使用 RCU 实现这些接口，因此 Starnix 可以采用相同的较弱一致性保证，同时正确匹配预期行为。

`RcuHashMap`和`RcuCache`

Starnix 中的大多数 RCU 用法都应依赖于 RcuHashMap 和 RcuCache 等高级数据结构。这些类型利用 Rust 的类型系统安全地封装了读取-复制-更新模式，因此比低级原语更容易使用。在大多数情况下，这些结构应优先于将标准 HashMap 封装在 Mutex 或 RwLock 中。

示例：使用 `RcuHashMap`

RcuHashMap 支持无等待并发读取，而写入操作则通过内部互斥锁进行同步。例如：

use starnix_rcu::{RcuHashMap, RcuReadScope};

// Create a new RcuHashMap.
let map = RcuHashMap::default();

// Single write operation.
// This internally acquires the write lock for the duration of the insert.
map.insert("key", "value".to_string());

// Batched write operations.
// Explicitly locking allows multiple updates to occur atomically.
{
    let mut guard = map.lock();
    guard.insert("key2", "value2".to_string());
    guard.remove(&"key");
} // The write lock is released here.

// Read operation.
// An RcuReadScope is required to protect the data from reclamation.
{
    // Enter an RCU read-side critical section.
    let scope = RcuReadScope::new();

    if let Some(value) = map.get(&scope, &"key2") {
        println!("Found value: {}", value);
    } else {
        println!("Key not found");
    }
} // The `scope` is dropped, ending the read-side critical section.

`RcuArc`和`RcuOptionArc`

RCU 还提供 RcuArc 和 RcuOptionArc，可实现 Arc 的并发读取和突变，从而提高效率。这些数据结构非常高效，因为它们除了 Arc 本身之外，不会引入额外的存储开销。它们通常应用于替代将 Arc 封装在 Mutex 或 RwLock 中。

示例：使用 `RcuArc`

RcuArc 可实现对 Arc 的原子更新，从而允许现有读取器在写入器发布新值时继续访问旧值。

use fuchsia_rcu::RcuArc;
use std::sync::Arc;

// Initialize an RcuArc with an initial value.
let rcu_arc = RcuArc::new(Arc::new(42));

// Access the current value.
// The returned guard dereferences to the inner type T.
{
    let val = rcu_arc.read();
    println!("Current value: {}", *val);
}

// Atomically replace the inner Arc.
// Concurrent readers may still see the old value during this update.
rcu_arc.update(Arc::new(100));

// Subsequent readers will observe the new value.
{
    let val = rcu_arc.read();
    println!("New value: {}", *val);
}

与 `register_delayed_release()` 的关系

Starnix 目前维护着两种用于延迟对象释放的独立机制：RCU 和 register_delayed_release()。虽然 register_delayed_release() 最终计划使用 RCU 重新实现，但目前两者作为独立的池运行。目前，这两个池是独立排空的，但它们的处理是在同一执行安全点触发的。

实现状态

当前的 RCU 实现是使用原子操作和 futex 构建的。这种方法非常高效，以至于从 Mutex 和 RwLock 迁移到 RCU 已在各种基准测试（包括单线程微基准测试）中取得了可衡量的改进。目前正在进行的工作重点是基于可重启序列 (RSEQ) 的新实现，该实现将完全消除对原子操作的需求，从而进一步优化读取路径。

一般来说，只要有合适的高级数据结构，新代码就应使用 RCU。随着 RCU 支持的结构库的扩展，Starnix 的更多领域将能够利用这些性能优势。

Starnix Read-Copy-Update (RCU)

背景

RcuHashMap和RcuCache

示例：使用 RcuHashMap

RcuArc和RcuOptionArc

示例：使用 RcuArc

与 register_delayed_release() 的关系