[Rust] 实现一个线程安全且迭代器可以保存的链表

owent

发布于 2023-03-06 12:00:30

6650

发布于 2023-03-06 12:00:30

文章被收录于专栏：owent

背景

今年有个想法，重新设计 libatbus 然后用 Rust 实现出来，然后可以加入一些云原生的支持。这需要一个定时器模块，我看了下 Rust 现有的几种定时器的实现，大多是基于堆或树的结构的，没有找到jiffies定时器的实现，所以想自己实现一个算了。这个定时器的实现又需要类似 C++ 的 std::list::iterator 的 插入和删除某个迭代器对其他迭代器没有影响 的特性，但是 Rust 的数据结构都不是这种设计模型。所以就决定自己写一个吧。

为什么不使用现有的链表

像链表这种基础的数据结构，稍微现代化的语言肯定都是带的。Rust 也不例外，提供了标准库的 std::collections::LinkedList 。但是它的实现没法满足上面提到的需求。一个重要的原因是 std::collections::LinkedList 也遵循 Rust 的借用和可变借用的规则，另一方面也是由于它的实现是尽可能没有额外开销。

Rust 是在编译期去分析管理对象的生命周期的，所有对象的生命周期的持有者只能有一个。所有对象都只能有一个可变借用或多个不可变借用。但是可变借用和多个不可变借用直接不能共存，相当于是编译期的读写锁。借用可以理解为不管理生命周期的引用。

稳定版本的 std::collections::LinkedList 的迭代器 Iter 和 IterMut 是没有插入和删除接口的。只有向前和向后迭代的接口，也就是说只能读写链表内的元素，不能修改链表本身。 Nightly版本的 Rust 标准库里的 std::collections::LinkedList 额外提供了 cursor_front(&self) 、cursor_front_mut(&mut self) 、cursor_back(&self) 、cursor_back_mut(&mut self) 来返回游标，这个游标就是在迭代器的基础上有增加了向前向后插入和删除接口，可以修改链表本身。乍看起来好像是可以符合需求，但是实际上也没法使用。

比如说，如果使用 cursor_front_mut(&mut self) 函数创建一个可变的 CursorMut。那么会占用掉容器的可变借用的权限。相当于会锁住这个 std::collections::LinkedList 。这时候直到我释放这个 CursorMut 前，对链表的其他操作都无法进行。所以就不能把这个游标保存起来以后用。那可不可以包一层 RefCell 来运行时借用，然后只用不可变的 Cursor 呢? 其实也是不可以的，因为首先 Cursor 和迭代器一样没有提供修改链表本身的接口，另一方面持有 Cursor 也会导致容器本身不能使用mutable的接口，也就无法完成增删链表节点的操作。

简单来说，无论是 Iter 还是 Cursor 都是用于放在栈上临时使用的，迭代器和游标的生命周期都低于容器本身，并不适用于需要长期保存的场景。

新链表的结构

从另一个角度说，我们需要的是能够保存迭代器，并在需要的时候基于迭代器操作。这本身是一个运行时可以修改容器的行为，属于运行时可变借用。与此同时还需要考虑多线程问题，即迭代器可以在多个线程中转移，就意味着可变借用这个过程可能在多个线程上同时发生。这两点都会带来额外开销。

链表的实体和节点数据结构如下:

pub type LinkedListItem<T> = Arc<T>;
type Node<T> = Arc<RwLock<NodeEntry<T>>>;

struct NodeEntry<T> {
    next: Option<NonNull<Node<T>>>,
    prev: Option<NonNull<Node<T>>>,
    element: Option<LinkedListItem<T>>,
    end: Weak<RwLock<NodeEntry<T>>>,
    leak: Option<NonNull<Node<T>>>,
}

struct UnmoveableLinkedList<T> {
    end: Node<T>,
    len: usize,
}

pub struct Iter<T> {
    node: Weak<RwLock<NodeEntry<T>>>,
    last_back: bool,
}

我采用了和 std::collections::LinkedList 类似的做法。数据节点创建完以后，通过 Box::leak 函数转换成指针，然后内部使用指针来手动维护数据。然后还有几个个标准库实现不同的地方。

首先是增加了 leak 字段，用于简化对自己的地址的访问。像标准库的实现，接口调用的数据源都是上层的 Iter 或者 Cursor 或者链表的头尾。里面都记录了对应节点的地址。但是我们这里是需要根据节点自身的数据反推出自己的地址的，不加 leak 字段就必须通过 next 和 prev 访问来取。比较麻烦而且增加冲突率，所以干脆直接加了 leak 字段。

其次增加了 end 字段指向链表的 Ghost 节点。这也有两个作用，其一是用于实现和 Cursor 类似的功能。如果移到最后或者第一个，再往后或往前移一次移到 Ghost 节点，之所以要这个字段来辅助是因为 std::collections::LinkedList 的 Cursor 是不能存在两个同时改的，而我们这个链表可以。这意味着可能迭代器向后移到 Ghost 之后，接下来最后一个节点被其他地方删除了，这个迭代器再向前移一次能够移动到新的尾部节点。其二是用于检查迭代器的所属容器，因为节点里的 end 总是指向容器的 end ，然后按迭代器做插入删除的时候，我们就能根据这个检查，如果迭代器对应的节点不属于调用的容器的时候要禁止操作。

至于容器里用 Node<T> 包一层而不是像 std::collections::LinkedList 直接存 next 和 prev 也是为了上面提到的目的。这个节点的生命周期也是跟着容器本身的。如果容器释放了，这个节点也就释放了，外部的迭代器对象无论是尝试解引用还是移到末尾都是会失败的。

关于Send语义、Sync语义、线程安全

标准库的 std::collections::LinkedList<T> 在实例化类型 T 支持 Send 和 Sync 语义的时候，分别也提供了 Send 和 Sync 语义的支持。但是到我们这里会更复杂一点。因为标准库的 std::collections::LinkedList<T> 实际上是走了 Rust 语言层面的对修改控制权限的管理。

包括标准库实现里的 Iter 和 Cursor 里都存了 len 和提供方法获取后续有多少可用元素都是依赖于此。因为 IterMut 或 CursorMut 只要能创建出来，那之前一定没有不可变借用了。那么对 len 字段的修改就有且仅有最后创建出来的这个 IterMut 或 CursorMut。也就不存在修改一个迭代器或游标导致影响其他迭代器或游标的问题。

但是我们这里分离了迭代器和容器的生命周期，就不能简单地这么声明了。

首先，由于我需要让这个链表的迭代器和容器的生命周期解绑，所以对链表的节点包了一层 Arc 。所以我们这个链表节点本身，其实对于所有的类型 T 都可以支持 Send 语义。但是访问实际数据的层面还是需要可以 Sync 才能跨线程读的。所以为了防止误用目前只对同时满足 Sync + Send 的 T 类型实现 atlist_rs::LinkedList<T> 生命为支持 Send 和 Sync 。

减少锁的临界区

可以看到我们实际节点的类型为 Arc<RwLock<NodeEntry<T>>> , 中间还有一层 RwLock 。因为我们解绑了迭代器和容器的生命周期，那么就无法在编译期保证多线程的场景下对节点的修改操作互相不冲突，这里的锁的作用其实也是为了支持多线程访问容器。对链表节点的 mutable 操作其实已经在链表接口那一层，通过 Rust 自带的借用管理控制了，不会发生冲突。举个例子，在迭代器和容器的生命周期解绑的情况下，可能发生一个线程在做删除操作，另一个线程在做这个节点的 prev 正在执行 next(&mut self) 。这时候需要读这个节点内的数据，然后读到的 next 的指针就有可能是无效的。

这个 RwLock 我们控制在内部使用，不会暴露到外部，这样可以我们自己管理和缩减锁的临界区，并且避免死锁。

首先所有的加锁操作都是先 prev 再 next 这个顺序，就是不会出现一个线程锁 A->B 另一个线程锁 B->A 的死锁操作。另一方面，所有的写操作生命周期都是绑在 atlist_rs::LinkedList<T> 上的，根本不会并发。

其实在写操作被限制在 atlist_rs::LinkedList<T> 的基础上，这个 RwLock 理论上是可以省掉的，如果我们的记录节点内部的 next 和 prev 直接用 Arc 保存，而不是按标准库一样存指针，那么也是可以保证多线程安全的，但是目前 Arc 只提供了非可变借用的访问接口， pub unsafe fn get_mut_unchecked(this: &mut Arc<T>) -> &mut T 还处于nightly阶段。我也不想多去造这个轮子，没啥意义，所以这个去除锁的操作还是等这个特性stable了，我再来优化吧。

另一种不依赖 pub unsafe fn get_mut_unchecked(this: &mut Arc<T>) -> &mut T 的方式是再套一层 RefCell 但是这会影响 Send 和 Sync 语义。所以也没有选择这么做。

运行时可变借用

我们的链表里，用户类型的定义为 pub type LinkedListItem<T> = Arc<T>; 。这意味着对外提供的解引用接口解出的 Arc<T> 只能获取 T 的immutable 借用。本来最初我是想要不要套一层 RefCell 来实现运行时可变借用的。但是这样感觉会提供整个库使用的难度和复杂度，而且也不线程安全。要线程安全就得也套个 RwLock 或者 Mutex ，这样开销高不说也不能覆盖实际使用的场景。所以最终还是决定不套了。由使用者来决定要怎么用，要不要要跨线程等等。

未来可能的偏特化优化

还有个理想的情况是如果实例化的类型 T 不支持 Sync + Send ，那么我们的链表不需要使用 Arc 包装，直接用 Rc 就可以了，节点管理的 RwLock也可以去掉。这样能省掉原子操作时的CPU Cache miss开销。现在的想法是使用 偏特化 实现。但是 Rust 里的 偏特化 特性目前还只处于 nightly 阶段，等这个特性stable了再优化吧。