kern/mpsc_queue.h Kernel.framework

@typedef struct mpsc_queue_chain @brief Type for the intrusive linkage used by MPSC queues.

@typedef struct mpsc_queue_head @brief The type for a multi-producer single-consumer queue. @discussion MPSC queues allow for producers to not be affected by other producers or the consumer. Which means in turn that having producers in interrupt context does not require that other producers disable interrupts like a traditional spinlock based approach would require. These queues shine when data is produced from the entire system and is consumed from a single serial context (logging, tracing, ...). mpsc_daemon_queue_t is provided as a fully ready/easy-to-use pre-packaged solution for these common use cases. - mpsc_queue_append() can be used to append a single item - mpsc_queue_append_list() can be used to append a batch of items at once. Functions for the consumer side assume proper serialization that is not provided by the MPSC queue itself. Dequeuing doesn't require preemption to be disabled. <h2>Algorithm</h2> The base of the enqueue algorithm is a single atomic exchange (first half, called __mpsc_queue_append_update_tail) and a list fixup (2nd half, called __mpsc_queue_append_update_prev). Graphically, enqueuing `X` looks like this, with each step being done atomically (for the empty queue case, `tail` points to `head`): | orig state | update_tail | update_prev | +---------------------+---------------------+---------------------+ | | | | | head -> e1 -> e2 -. | head -> e1 -> e2 -. | head -> e1 -> e2 -. | | | | | | | | | ,- ... <--' | ,- ... <--' | ,- ... <--' | | | | | | | | | v | v | v | | tail -> eN -> NULL | tail eN -> NULL | tail eN | | | | | | | | | | | | | v | | X -> NULL | `---> X -> NULL | '---> X -> NULL | | | | | +---------------------+---------------------+---------------------+ There is a small 1-instruction gap of inconsistency which makes the chosen algorithm non linearizable, and requires enqueuers to disable preemption during the enqueue so as not to starve the consumer forever. As far as memory visibility is concerned, enqueuing uses a release fence in update_tail which pairs with memory fences in mpsc_queue_dequeue_batch(). Note: as far as the data structure in memory, its layout is equivalent to a BSD <sys/queue.h> STAILQ. However because of this inconsistency window and memory ordering concerns, it is incorrect to use STAILQ macros on an MPSC queue.

@macro MPSC_QUEUE_INITIALIZER @brief Macro to use in static initializers for mpsc queues. @param head The name of the variable to initialize.

#define MPSC_QUEUE_INITIALIZER(head) { .mpqh_tail = &(head).mpqh_head }