Crate twizzler_queue_raw

A raw queue interface for Twizzler, making no assumptions about where the underlying headers and circular buffers are located. This means you probably don’t want to use this — instead, I suggest you use the wrapped version of this library, twizzler-queue, since that actually interacts with the object system.

This library exists to provide an underlying implementation of the concurrent data structure for each individual raw queue so that this complex code can be reused in both userspace and the kernel.

The basic design of a raw queue is two parts:

1. A header, which contains things like head pointers, tail pointers, etc.
2. A buffer, which contains the items that are enqueued.

The queue is an MPSC lock-free blocking data structure. Any thread may submit to a queue, but only one thread may receive on that queue at a time. The queue is implemented with a head pointer, a tail pointer, a doorbell, and a waiters counter. Additionally, the queue is maintained in terms of “turns”, that indicate which “go around” of the queue we are on (mod 2).

Let’s look at an insert

Here’s what the queue looks like to start with. The 0_ indicates that it’s empty, and turn is set to 0.

 b
 t
 h
[0_, 0_, 0_]

When inserting, the thread first reserves space:

 b
 t
     h
[0_, 0_, 0_]

Then it fills out the data:

 b
 t
     h
[0X, 0_, 0_]

Then it toggles the turn bit:

 b
 t
     h
[1X, 0_, 0_]

Next, it bumps the doorbell (and maybe wakes up a waiting consumer):

     b
 t
     h
[1X, 0_, 0_]

Now, let’s say the consumer comes along and dequeues. First, it checks if it’s empty by comparing tail and bell, and finds it’s not empty. Then it checks if it’s the correct turn. This turn is 1, so yes. Next, it remove the data from the queue:

     b
 t
     h
[1_, 0_, 0_]

And then finally it increments the tail counter:

     b
     t
     h
[1_, 0_, 0_]

Structs

• QueueBase
  The base info structure stored in a Twizzler queue object. Used to open Twizzler queue objects and create a [Queue].
• QueueEntry
  A queue entry. All queues must be formed of these, as the queue algorithm uses data inside this struct as part of its operation. The cmd_slot is used internally to track turn, and the info is used by the full queue structure to manage completion. The data T is user data passed around the queue.
• RawQueue
  A raw queue, comprising of a header to track the algorithm and a buffer to hold queue entries.
• RawQueueHdr
  A raw queue header. This contains all the necessary counters and info to run the queue algorithm.
• ReceiveFlags
  Flags to control how queue receive works.
• SubmissionFlags
  Flags to control how queue submission works.

Enums

• QueueError
  Possible errors for submitting to a queue.

Functions

• multi_receive
  Wait for receiving on multiple raw queues. If any of the passed raw queues can return data, they will do so by writing it into the output array at the same index that they are in the queues variable. The queues and output arrays must be the same length. If no data is available in any queues, then the function will call back on multi_wait, which it expects to wait until any of the pairs (&x, y) meet the condition that *x != y. Before returning any data, the function will callback on multi_ring, to inform multiple queues that data was taken from them. It expects the multi_ring function to wake up any waiting threads on the supplied words of memory.