Starnix Read-Copy-Update (RCU)

本文說明 Starnix 核心使用的讀取-複製-更新 (RCU) 同步方法。

背景

Starnix 核心會管理大量狀態，這些狀態會由許多執行緒同時存取。執行 Linux 使用者空間程式碼的任何執行緒都可以觸發系統呼叫或接收例外狀況，導致該特定執行緒轉換至 Starnix 位址空間，以執行核心程式碼。為有效處理這種高並行程度，Starnix 採用各種同步機制，包括 Read-Copy-Update (RCU)。

RCU 可讓許多執行緒同時讀取共用資料，而不必互相封鎖或封鎖寫入者。如要修改共用資料，寫入者必須複製資料、修改副本，然後發布至其他執行緒，這就是「讀取、複製、更新」名稱的由來。因為更新發生時，執行緒可能仍在讀取舊副本，因此記憶體無法立即回收。Starnix 會等待所有有效讀取器完成舊資料的存取作業，再釋放舊資料；這段等待間隔稱為「寬限期」。

RCU 有以下顯著的取捨條件：

  • 較弱的一致性保證：RCU 的一致性比同步基本類型 (例如互斥鎖或讀取/寫入鎖) 弱。使用 RCU 時，寫入者修改資料後，讀取者可能會在短時間內看到過時的資料。Mutex 和讀取/寫入鎖可避免這種不一致的情況，因為寫入者必須等待作用中的讀取者完成作業，才能修改資料；讀取者則必須等待作用中的寫入者完成作業，才能讀取資料。

  • 延後資源回收：與修改後資料相關聯的資源不會在寫入後立即釋出，這些物件會佔用記憶體，直到寬限期結束 (也就是所有未完成的讀取作業都已完成) 為止。因此，RCU 類似於垃圾收集器，會延後物件終結器。

RCU 由 Linux 核心發揚光大，現在已廣泛用於作業系統設計。由於核心工作負載大多是讀取作業，因此系統可充分運用 RCU 讀取器的效率，非常適合 Starnix。此外，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()。雖然我們最終計畫使用 RCU 重新實作 register_delayed_release()，但目前這兩者是獨立運作的集區。目前，這兩個集區會獨立排空，但處理作業會在相同的執行安全點觸發。

導入狀態

目前的 RCU 實作方式是使用原子和 futex 建構而成。這種做法效率極高，因此從 Mutex 和 RwLock 遷移至 RCU 後，各種基準測試 (包括單一執行緒微基準測試) 的成效都有顯著提升。目前的工作重點是根據可重新啟動的序列 (RSEQ) 進行新的實作，完全消除原子作業的需求，進一步最佳化讀取路徑。

一般來說，只要有合適的高階資料結構，新程式碼就應使用 RCU。隨著 RCU 支援的結構體庫擴充，Starnix 的更多領域將能運用這些效能優勢。