Module lilos::spsc

A queue for moving data from one future/task into another.

This is a “single-producer, single-consumer” queue that splits into separate Pusher and Popper endpoints – at any given time, there is at most one of each alive in your program, ensuring that pushes and pops are not coming from multiple directions.

You create a queue by calling Queue::new and passing it a reference to its backing storage. To actually use the queue, however, you must call Queue::split to break it into two endpoints, Pusher and Popper. As their names suggest, Pusher can be used to push things into the queue, and Popper can be used to pop things out of it.

The Pusher and Popper can then be handed off to separate code paths, so long as they don’t outlive the Queue and its storage. (The compiler will ensure this.)

This queue uses the Rust type system to ensure that only one code path is attempting to push or pop the queue at any given time, because both Pusher and Popper endpoints borrow the central Queue, and an async operation to push or pop through an endpoint borrows that endpoint in turn. Neither Pusher nor Popper can be cloned or copied, ensuring the single-producer single-consumer property.

Implementation

This is implemented as a concurrent lock-free Lamport queue. This has two implications:

1. If you can arrange the lifetimes correctly (i.e. make the queue static) it is actually safe to operate either Pusher or Popper from an ISR.
2. It fills up at N-1 elements because one empty slot is used as a sentinel to distinguish full from empty.

The adaptations to modern memory ordering semantics are taken from Nhat Minh Lê et al’s paper “Correct and Efficient Bounded FIFO Queues,” though this implementation does not use all of the optimizations they identified.

Structs

• Entry
  A reference to a free element in a queue, where you can deposit an element without checking or waiting.
• Popper
  Queue endpoint for popping data. Access to a Popper only gives you the right to pop data and enquire about pop-related properties.
• Pusher
  Queue endpoint for pushing data. Access to a Pusher only gives you the right to push data and enquire about push-related properties.
• Queue
  A single-producer, single-consumer queue. The Queue struct contains the controlling information for the queue overall, and borrows the storage.