Struct atomic_ring_buffer::AtomicRingBuffer
[−]
[src]
pub struct AtomicRingBuffer<T, U: InvariantAsMut<[T]>> { /* fields omitted */ }
A fixed-size multi-producer multi-consumer queue that works on bare-metal systems.
An atomic ring buffer provides two basic operations: enqueue and dequeue, both acting on a single element. Under certain restrictions, the queue is lock-free or wait-free.
Lock-freedom means that, when the whole program is run for sufficient time, at least
one thread of execution is making progress, although any individual thread may stall
indefinitely. This data structure is lock-free when every closure passed to enqueue()
or dequeue() terminates in a bounded time.
Wait-freedom means that any operation on the data structure terminates in a bounded time. This data structure is wait-free with respect to a producer (consumer) when there is only one producer (consumer).
Modes of operation
This data structure provides different useful guarantees depending on how it's used. It may be used as a locking multiple-producer multiple-consumer queue, lock-free multiple-producer multiple-consumer queue, or a wait-free single-producer single-consumer queue.
Locking queue
While the closure passed to enqueue() or dequeue() executes, there is a lock on
the producer or consumer side. No other thread of execution may enqueue or dequeue elements,
and the corresponding call will return Err(Error::Locked).
Even when an operating system is present, the queue provides no functionality to suspend and afterwards wake the current thread of execution. This can be added on top of the queue using a building block such as thread parking or a futex.
Lock-free queue
It may seem odd to use locks for implementing a lock-free queue. However, when the lock is always taken for a bounded amount of time, the lock-free property is preserved.
Defining the queue operations as passing a &mut pointer has several benefits: there is
no requirement for a T: Copy bound; exactly one copy will be performed; it is possible
to read or write only a part of the element.
Another benefit is implementation simplicity. This queue implementation uses contiguous
storage and two indexes to manage itself. In order to ensure atomic updates, a 'true'
lock-free implementation would have to use a linked list, which inflicts excessive overhead
for small elements (e.g. u8) and makes it impossible to initialize a static with
a new queue.
To aid the lock-free mode of operation, the enqueue_spin() and dequeue_spin() methods
can be used, which retry the operation every time one fails with an Error::Locked.
Wait-free queue
Lock-freedom is not always enough. In a real-time system, not only the entire program must make progress, but also certain threads of execution must make progress quickly enough.
When there is only one producer (only one consumer), the enqueue (dequeue) operation is
guaranteed to terminate in bounded time, and never return Err(Error::Locked).
If there is both only a single producer and a single consumer, the queue is fully wait-free.
A partially wait-free queue is still useful. For example, if only an interrupt handler bound to a single core produces elements, but multiple threads consume them, the interrupt handler is still guaranteed to terminate in bounded time.
Panic safety
The queue maintains memory safety even if an enqueue or a dequeue operation panics. However, it will remain locked forever.
Methods
impl<T, U: InvariantAsMut<[T]>> AtomicRingBuffer<T, U>[src]
fn new(storage: U) -> AtomicRingBuffer<T, U>
Create a ring buffer.
fn enqueue<F: FnOnce(&mut T) -> R, R>(&self, f: F) -> Result<R, Error>
Enqueue an element.
This function returns Err(Error::Exhausted) if the queue is full,
or Err(Error::Locked) if another enqueue operation is in progress.
fn dequeue<F: FnOnce(&mut T) -> R, R>(&self, f: F) -> Result<R, Error>
Dequeue an element.
This function returns Err(Error::Exhausted) if the queue is empty,
or Err(Error::Locked) if another dequeue operation is in progress.
fn enqueue_spin<F: FnMut(&mut T) -> R, R>(&self, f: F) -> Result<R, ()>
Enqueue an element.
This function returns Err(()) if the queue is full, and retries the operation
if another enqueue operation is in progress.
fn dequeue_spin<F: FnMut(&mut T) -> R, R>(&self, f: F) -> Result<R, ()>
Dequeue an element.
This function returns Err(()) if the queue is empty, and retries the operation
if another dequeue operation is in progress.