🌎🔒 interlock

实验性，需要不稳定编译器特性

为锁定区间设计的 读者-写入者锁。与 #![no_std] 兼容。

use std::pin::Pin;
use interlock::{hl::slice::SyncRbTreeVecIntervalRwLock, state};

let vec = Box::pin(SyncRbTreeVecIntervalRwLock::new(vec![0u8; 64]));
let vec = vec.as_ref();

// Borrow `vec[0..32]`
state!(let mut state);
let guard1 = vec.read(0..32, (), state);

// Borrow `vec[16..32]`
state!(let mut state);
let guard2 = vec.read(16..32, (), state);

// Mutably borrow `vec[16..48]` unsuccessfully
state!(let mut state);
vec.try_write(16..48, Pin::as_mut(&mut state)).unwrap_err();

// Unborrow `vec[0..32]` completely
drop(guard1);
drop(guard2);

// Mutably borrow `vec[16..48]`
vec.try_write(16..48, Pin::as_mut(&mut state)).unwrap();

use parking_lot::RawMutex;
use interlock::{hl::slice::AsyncRbTreeVecIntervalRwLock, state};

#[tokio::main]
async fn main() {
    let vec = Box::pin(AsyncRbTreeVecIntervalRwLock::<RawMutex, _>::new(vec![0u8; 64]));
    let vec = vec.as_ref();

    state!(let mut state);
    let _guard = vec.async_read(0..32, (), state).await;

    state!(let mut state);
    let _guard = vec.async_read(16..48, (), state).await;
}

设计

基于红黑树实现

它们被模拟为一个虚拟读者-写入者锁的数组。在锁定时，按升序锁定指定范围内的虚拟锁。在解锁时，按降序解锁。（锁定顺序很重要，以防止死锁。）每个虚拟锁的等待列表按 (priority, sequence) 排序，其中 sequence 是单调递增的数字（从而强制执行 FIFO 排序）。当虚拟锁被解锁时，将检查等待列表中的所有条目，并按顺序立即（如果可能）恢复。

在锁定冲突时，可错误处理接口失败，并保留所有虚拟锁不变。其他接口在取消或通过移除冲突借用完成之前保持不完全借用。

以 Future 为中心的接口支持取消。

最坏情况下的时间复杂度如下所示

空间复杂度为 O(existing_borrows)。

Cargo 功能

• std 启用了依赖 std 或 alloc 的项。
• alloc 启用了依赖 alloc 的项。这目前需要一个具有 usize 原子操作支持的 target，因为 stable_deref_trait 和 alloc 无条件地在 Arc 上实现了 StableDeref，而这由 cfg(target_has_atomic = "ptr") 控制。
• async 启用了以 Future 为导向的 API。这目前需要一个具有加载/存储原子操作支持的 target。当 lock_api 问题 #277 得到解决时，这个要求将被取消，并且这个 Cargo 功能将被弃用。

未来方向

• 可能需要对不受信任的特质 impl 和各种类型的安全性进行更彻底的测试。
• 除了 RwLock 外，还应提供 Mutex 和 ReentrantMutex 的对应物。
• 应提供具有更简单算法的变体，例如链表。
• 应尽可能在某个时候移除对不稳定编译器特性的依赖。
• 当 Rust 的内存模型调整以正确容纳此类结构时，应移除用于声音侵入性数据结构（EarlyDropGuard）的技巧。

替代方案

interlock 意外地很狭窄。虽然它可能对大规模输入具有良好的可扩展性，但其复杂性和开销可能在许多实际情况下超过其益处。在选择 interlock 之前，请考虑以下替代方案

• 分割切片： 语言和标准库提供了许多分割 &mut [T] 的方法。例如

  • 模式匹配（例如，if let [first, rest @ ..] ...）可以将切片的前几个或最后几个元素与剩余部分分开。
  • slice::iter_mut 创建了一个 &mut T 集合，可以单独使用。
  • slice::chunks_mut 将 &mut [T] 分成块。
  • slice::split_at_mut 将 &mut [T] 分成两部分。可以通过重复此过程创建任意数量的片段。

• 无排序要求，无引用形成： 如果借用可以相对于其他借用无序，则获取对&[T]或&mut [T]的访问是不必要的，并且...

  • 单线程： ...切片[T]只被一个线程引用，那么考虑用Cell<T>封装单个元素。你可以通过Cell::as_slice_of_cells将&mut [T]转换为&[Cell<T>]。
  • 整数： ...元素是原始整数类型，那么考虑将元素类型更改为std::sync::atomic::Atomic*，并使用Ordering::Relaxed进行访问。

• 短期借用： 如果预计每个借用都是短期的，考虑用一个Mutex或RwLock封装整个切片。《interlock》使用一个Mutex来保护内部结构，因此它承担了Mutex的额外开销。

• 并行数据处理： 考虑使用Rayon进行并行计算。

• 按元素或按段借用： 如果你只需要借用单个元素或段（即，如果你可以接受获取&mut T或&mut [T; SEGMENT_LEN]而不是更通用的、连续的&mut [T]），考虑使用parking_lot::{Mutex, RwLock}来封装单个元素或段，它们分别只占用一个字节和一个字的空间。在某些情况下，spin可能是一个更好的选择。

  • 假设您将 N 从 Mutex 替换为对 SyncRbTreeSliceIntervalRwLock 的一次借用。尽管后者的锁定时间不依赖于 N，但由于其固有的复杂性，如果 N 过小，您可能会实际上降低性能。根据在 AMD Zen 处理器上进行的某些单线程微基准测试，阈值似乎在 N = 6 附近。由于缓存效应和锁竞争，在实际应用程序中可能期望更高的阈值。

• 单处理器，CPU 密集型： 如果只有一个处理器同时访问切片，并且预计处理器在借用切片时将完全占用，请考虑用 Mutex 或 RwLock 包装整个切片。在这种情况下，能够同时借用不相交的子切片并不会提高整体吞吐量。