1 个不稳定版本
0.1.0 | 2023 年 5 月 29 日 |
---|
#721 在 并发
40KB
718 行
简介
这是一个仅依赖于 Rust 核心库的无堆单生产者单消费者(SPSC)环形缓冲区。其实现在内部包含一个环形缓冲区和用于提供可移动的访问处理器的轻量级包装器,这些处理器可以被移动到相应的生产者和消费者实体中。内部环形缓冲区设计得易于实例化,作为全局静态封装,无需在用户代码中使用 unsafe
来访问结构。
基本环形缓冲区
底层环形缓冲区采用 "数组 + 两个未掩码索引" 的方法,具体说明请参见 这里。本质上,这允许使用缓冲区中分配的所有元素,而不需要存储长度和读写索引。如果 Const Generics 参数容量 N
是 2 的幂,则在缓冲区访问时,只需要对读写索引进行掩码(在 [0, N-1]
内)。如果 N
不是 2 的幂,则实现将索引在 0
和 2*N-1
之间包装,因为它们是递增的。
支持的最大缓冲区大小为 2^32 - 1
项。这个限制来自读写索引的大小(u32
)。如果需要,可以通过将索引更改为 usize
类型来放宽这个限制。
环形缓冲区项是一个没有特例要求的泛型结构。
使用模型
生产者调用 write_front()
从 buffer[mask(wr_idx)]
下的位置开始写入。这返回了对底层项目的可变引用。在位置被填充后,生产者调用 commit()
来推进写入索引。消费者可以使用 read_front()
来检查(并读取)新可用的项目。消费者使用 pop()
来消费项目并推进读取索引。
绕过静态全局变量的限制
为了在避免要求使用该结构的所有代码都被包裹在 unsafe
中的情况下,实现这些队列的静态分配,实现采用了以下方法
Cell
包裹读写索引,以提供索引的内部可变性- 有限的内部
unsafe
代码以返回内部缓冲区的可变引用。由于只有一个生产者和一个消费者,这被认为是安全的。即写入索引仅由生产者修改,读取索引仅由消费者修改。 - 在内部缓冲区中使用
MaybeUninit
以避免静态初始化(在队列中不需要) Cell
结构本身不是线程安全的,并且包含 Cells 的全局变量不能实例化,因为没有Sync
特性标记。再次由于 SPSC 前提,core::marker::Sync
被添加到RingbufRef
结构。直白地说,标记应该 仅 添加到包装Ringbuf
结构,该结构通过split
操作强制使用 SPSC。但这样做是为了允许在不产生处理开销的情况下实例化全局RingbufRef
,如果用户决定使用是足够安全的。
顶层包装器
顶层 RingBuf
结构提供了对内部循环缓冲区的不当直接使用的最终保护。此包装器提供了一个一次性调用,返回一个(可变)句柄对,可以移动到生产者和消费者实体。由于 writ_front
、commit
和 pop
函数都需要可变 self
,Rust 的单个可变引用检查应保证只有一个生产者或消费者是可能的。
共享单例
此 crate 还提供了一个更便宜的实现,用于单项目循环缓冲区的特殊情况。在这个版本中,一个三态 owner
标志取代了所有读写索引操作的开销。此结构也可以与循环缓冲区一起使用,作为循环缓冲区数据扩展。在一个堆环境,例如,可以想象在动态分配中,由于不是所有命令都需要有效负载,因此很难创建比可用的命令“有效负载”更深度的命令队列。
在包含的 SharedPool
示例中,可以通过在队列中传递的命令索引从共享单例池中分配有效负载。owner
标志为有效负载池中的每个项目提供了单独的所有权跟踪。在初始化时,返回环缓冲区被填充以指示每个池项目都属于分配生产者。生产者从池中分配一个项目,并通过 alloc_prod
环缓冲区传递索引以及任何其他信息。当消费者完成对分配项目的使用后,该项目(以池索引的形式)通过返回环缓冲区返回。
Pool of SharedSingleton<T>
┌─┬─┬─┬─┐ ┌───┐
│0│1│2│3│ ..│N-1│
└─┴─┴─┴┬┘ └───┘
┌────────────────┐ │PoolIndex<N> ┌────────────────┐
│Producer │ ┌───┘ │Consumer │
│ ┌───────────┐ │ │ │ ┌───────────┐ │
│ │alloc_prod ├──┼───┐ ┌─┬┴┬─┬─┬─┐ ┌───┐ ┌──► │alloc_cons │ │
│ └───────────┘ │ └─►│0│1│2│3│4│.. │M-1├─────┘ │ └───────────┘ │
│ RingbufProducer └─┴─┴─┴─┴─┘ └───┘ │ │
│ ┌───────────┐ │ Prod. -> Cons Ringbuf<Q,M> │ ┌───────────┐ │
│ │return_cons│◄─┼──┐ ┌─┼─┤return_prod│ │
│ └───────────┘ │ │ ┌─┬─┬─┬─┬─┐ ┌───┐ │ │ └───────────┘ │
│ RingbufConsumer│ └───┤0│1│2│3│4│.. │M-1│◄─────┘ │ │
└────────────────┘ └─┴─┴─┴─┴─┘ └───┘ └────────────────┘
Cons. -> Prod. Ringbuf<Q,M>