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 Push and Pop 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, Push and Pop. As their names suggest, Push can be used to push things into the queue, and Pop can be used to pop things out of it.

The Push and Pop 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 Push and Pop endpoints borrow the central Queue, and an async operation to push or pop through an endpoint borrows that endpoint in turn. Neither Push nor Pop 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 Push or Pop 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

• Permit
  A “permit” giving its holder the right to push one element into a queue, without waiting.
• Pop
  Queue endpoint for popping data. Access to a Pop only gives you the right to pop data and enquire about pop-related properties.
• Push
  Queue endpoint for pushing data. Access to a Push 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.