This is an automated email from the ASF dual-hosted git repository. xiaoxiang781216 pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/nuttx.git
commit 74a387b2e68adf4e378d71156c73ee9def4a00ca Author: Xiang Xiao <[email protected]> AuthorDate: Sun Apr 26 23:18:52 2026 +0800 include/nuttx/mpsc.h: add intrusive MPSC lock-free queue Add a multi-producer/single-consumer intrusive lock-free linked-list queue based on Dmitry Vyukov's stub-sentinel MPSC algorithm. Producers serialise via a single atomic xchg on the tail; the consumer walks the linked list from head, skipping or recycling the embedded stub to keep the list well-formed. Enqueue is wait-free (1 xchg-release + 1 release-store, wrapped in local irq_save/restore to bound the per-core transient window). Dequeue is lock-free; the common case is a single acquire-load. The two-step publish creates an intrinsic transient window in which the consumer can observe head != tail with head->next == NULL. The base mpsc_dequeue() returns NULL in this window, preserving lock- freedom and letting the caller pick its own wait policy. Two helper wrappers are provided for callers that want the queue to hide the transient: mpsc_dequeue_spin - busy-spin while a producer is in flight mpsc_dequeue_yield - sched_yield() while a producer is in flight Both wrappers fall back to mpsc_empty() to distinguish "really empty" from "transient" and only return NULL when genuinely empty. Mirrors the SPSC macro family: MPSC_INIT / MPSC_DEFINE / MPSC_DECLARE for static and dynamic queue construction. The descriptor is cache- line padded to keep producer-shared tail and consumer-private head on separate lines. Signed-off-by: Bowen Wang <[email protected]> Signed-off-by: Xiang Xiao <[email protected]> --- include/nuttx/mpsc.h | 427 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 427 insertions(+) diff --git a/include/nuttx/mpsc.h b/include/nuttx/mpsc.h new file mode 100644 index 00000000000..882723e7421 --- /dev/null +++ b/include/nuttx/mpsc.h @@ -0,0 +1,427 @@ +/**************************************************************************** + * include/nuttx/mpsc.h + * + * SPDX-License-Identifier: Apache-2.0 + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. The + * ASF licenses this file to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance with the + * License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT + * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the + * License for the specific language governing permissions and limitations + * under the License. + * + ****************************************************************************/ + +/* Multi-producer/single-consumer intrusive lock-free linked-list queue. + * + * Algorithm: Dmitry Vyukov's MPSC (stub-sentinel with recycle). The queue + * is initialised with a single sentinel node (`stub`) so that `head` and + * `tail` are never NULL. Producers serialise via a single atomic exchange + * on `tail`; the consumer walks the linked list from `head`, skipping or + * re-inserting the stub as needed to keep the list well-formed. + * + * Producer-shared state : q->tail (atomic, xchg) + * Consumer-private state: q->head + * Cross-thread sync : release-store on prev->next (producer) + * acquire-load on head->next (consumer) + * + * Hot-path cost (per round-trip, low contention): + * enqueue : 1 xchg-release + 1 release-store, wrapped in + * irq_save()/irq_restore() to bound the same-core + * "transient inconsistent" window if a producer is + * preempted between the xchg and the prev->next publish. + * dequeue : 1 acquire-load (best case). When the queue is about to + * become empty, dequeue re-enqueues the stub to keep the + * list non-empty - that path adds one xchg + release-store + * call, so worst-case dequeue cost is roughly equal to + * enqueue. + * Both sides are lock-free; enqueue is wait-free. + * + * Transient inconsistent state: + * Between a producer's xchg on `tail` and its store on `prev->next`, + * the consumer can observe `q->tail != q->head` while `head->next` + * is still NULL. This is intrinsic to any two-step intrusive MPSC + * publish and cannot be removed without losing lock-freedom. + * mpsc_dequeue() returns NULL in this window. Callers that need to + * distinguish "really empty" from "transient" can use mpsc_empty(), + * or use one of the helper wrappers below: + * mpsc_dequeue - lock-free, returns NULL on transient/empty + * mpsc_dequeue_spin - busy-spin transient, return NULL on empty + * mpsc_dequeue_yield - sched_yield() through transient, NULL on empty + * For "block until a node arrives", combine mpsc_dequeue() + + * mpsc_empty() with a semaphore the producer posts after enqueue. + * + * Node lifetime: + * The node returned by mpsc_dequeue() has been fully detached from + * the linked list before return; the caller may free or re-enqueue + * it immediately. The stub (q->stub) is owned by the queue and + * must never be freed or re-enqueued by the caller. + * + * IRQ handling: + * mpsc_enqueue() disables interrupts on the calling core for the + * duration of the xchg + release-store window only. This keeps the + * per-core preemption-induced transient bounded. Cross-core + * producers serialise via the atomic exchange and do not disable + * each other's interrupts. Do not extend the IRQ-disabled window by + * performing unrelated work between manual irq_save and + * mpsc_enqueue - prepare the node *before* calling mpsc_enqueue(). + * + * Multi-core placement: + * When producers and consumer run on different cores, the queue + * descriptor and all enqueued nodes (including the embedded stub) + * must reside in cache-coherent memory. See the multi-core notes + * in include/nuttx/ring.h. + */ + +#ifndef __INCLUDE_NUTTX_MPSC_H +#define __INCLUDE_NUTTX_MPSC_H + +/**************************************************************************** + * Included Files + ****************************************************************************/ + +#include <nuttx/config.h> +#include <nuttx/compiler.h> +#include <nuttx/atomic.h> +#include <nuttx/irq.h> + +#include <sched.h> +#include <stdbool.h> +#include <stddef.h> +#include <stdint.h> + +/**************************************************************************** + * Pre-processor Definitions + ****************************************************************************/ + +#ifndef CACHELINE_SIZE +# define CACHELINE_SIZE 64 +#endif + +/* MPSC_INIT - designated initialiser for a queue object. + * + * Uses a self-referencing initialiser to point head/tail at the + * embedded stub. This relies on the GCC/Clang extension that allows + * taking the address of the object being initialised; both compilers + * supported by NuttX accept this form. + * + * Usage: + * struct mpsc_queue_s g_q = MPSC_INIT(g_q); + */ + +#define MPSC_INIT(q) \ + { \ + .head = &(q).stub, \ + .tail = (intptr_t)&(q).stub, \ + .stub.next = 0, \ + } + +/* MPSC_DEFINE - define and initialise a queue. + * + * Usage: + * MPSC_DEFINE(g_my_queue); + * mpsc_enqueue(&g_my_queue, &node); + */ + +#define MPSC_DEFINE(name) \ + struct mpsc_queue_s name = MPSC_INIT(name) + +/* MPSC_DECLARE - declare a queue without initialisation. + * + * Caller must invoke mpsc_init() before any enqueue/dequeue. Use + * this for queues placed in shared/uncached memory or allocated + * dynamically. + */ + +#define MPSC_DECLARE(name) \ + struct mpsc_queue_s name + +/**************************************************************************** + * Public Types + ****************************************************************************/ + +/* Intrusive queue node. Embed inside the user data structure and convert + * with container_of(). The `next` field is the cross-thread sync point. + */ + +struct mpsc_node_s +{ + atomic_ptr_t next; +}; + +/* MPSC queue descriptor. Head (consumer-private) and tail (producer- + * shared) sit on separate cache lines to avoid false sharing. + */ + +struct aligned_data(CACHELINE_SIZE) mpsc_queue_s +{ + /* Consumer side - written only by the consumer */ + + FAR struct mpsc_node_s *head; + uint8_t pad0[CACHELINE_SIZE - sizeof(FAR struct mpsc_node_s *)]; + + /* Producer side - all producers contend on this atomic */ + + atomic_ptr_t tail; + uint8_t pad1[CACHELINE_SIZE - sizeof(atomic_ptr_t)]; + + /* Embedded sentinel. Always present in the linked list; recycled + * by the consumer when the queue is about to drain. + */ + + struct mpsc_node_s stub; +}; + +/**************************************************************************** + * Inline Functions + ****************************************************************************/ + +/**************************************************************************** + * Name: mpsc_init + * + * Description: + * Initialise a queue. Required for MPSC_DECLARE() and for queues + * placed in shared memory; MPSC_DEFINE() initialises statically and + * does not need this. In multi-core setups, ensure a memory barrier + * (and any required IPI handshake) between init and first use on + * remote cores. + * + ****************************************************************************/ + +static inline_function void mpsc_init(FAR struct mpsc_queue_s *q) +{ + atomic_ptr_set(&q->stub.next, 0); + q->head = &q->stub; + atomic_ptr_set(&q->tail, (intptr_t)&q->stub); +} + +/**************************************************************************** + * Name: mpsc_empty + * + * Description: + * Return true when the queue is genuinely empty - no linked + * successor *and* no producer in flight. Distinguishes "really + * empty" from "transient inconsistent" (where a producer has won + * the xchg but not yet completed the prev->next store). + * + * Only meaningful when called from the consumer side. + * + ****************************************************************************/ + +static inline_function bool mpsc_empty(FAR struct mpsc_queue_s *q) +{ + FAR struct mpsc_node_s *head = q->head; + FAR struct mpsc_node_s *next; + FAR struct mpsc_node_s *tail; + + next = (FAR struct mpsc_node_s *) + (intptr_t)atomic_ptr_read_acquire(&head->next); + if (next != NULL) + { + return false; + } + + /* No linked successor; verify no producer is in flight. */ + + tail = (FAR struct mpsc_node_s *) + (intptr_t)atomic_ptr_read(&q->tail); + return head == tail; +} + +/**************************************************************************** + * Name: mpsc_enqueue + * + * Description: + * Append a node. Wait-free per producer; safe from any number of + * concurrent producers (and from the consumer's stub recycle path). + * + * The caller must populate the user data of `node` before this call. + * Once enqueued, the node belongs to the queue and must not be + * touched until returned by mpsc_dequeue(). + * + ****************************************************************************/ + +static inline_function void +mpsc_enqueue(FAR struct mpsc_queue_s *q, FAR struct mpsc_node_s *node) +{ + FAR struct mpsc_node_s *prev; + irqstate_t flags; + + /* Mark the new tail terminal. Relaxed is fine: the consumer reaches + * `node` only through the release-store on prev->next below. + */ + + atomic_ptr_set(&node->next, 0); + + /* Bound the per-core preemption window: between the xchg and the + * prev->next store, the queue is "transiently inconsistent" - tail + * points at node but prev->next is still NULL. Disabling local IRQs + * keeps another producer on the same core from extending this gap. + */ + + flags = irq_save(); + prev = (FAR struct mpsc_node_s *) + (intptr_t)atomic_ptr_xchg_release(&q->tail, (intptr_t)node); + atomic_ptr_set_release(&prev->next, (intptr_t)node); + irq_restore(flags); +} + +/**************************************************************************** + * Name: mpsc_dequeue + * + * Description: + * Remove and return the next node, or NULL when the queue is empty + * or transiently inconsistent. Single consumer only. Lock-free. + * + * The returned node is fully detached from the queue; the caller + * may free or re-enqueue it. Returning NULL is not an error - it + * may simply mean a producer is in the middle of an enqueue and + * the caller should retry shortly. See mpsc_dequeue_spin() and + * mpsc_dequeue_yield() for wrappers that hide the transient. + * + ****************************************************************************/ + +static inline_function FAR struct mpsc_node_s * +mpsc_dequeue(FAR struct mpsc_queue_s *q) +{ + FAR struct mpsc_node_s *head = q->head; + FAR struct mpsc_node_s *next; + FAR struct mpsc_node_s *tail; + + next = (FAR struct mpsc_node_s *) + (intptr_t)atomic_ptr_read_acquire(&head->next); + + /* Skip the stub if we are sitting on it. */ + + if (head == &q->stub) + { + if (next == NULL) + { + return NULL; + } + + q->head = next; + head = next; + next = (FAR struct mpsc_node_s *) + (intptr_t)atomic_ptr_read_acquire(&head->next); + } + + /* Common case: another node is already linked after `head`. Advance + * past `head` and return it - it is now detached from the list. + */ + + if (next != NULL) + { + q->head = next; + return head; + } + + /* `head` looks like the last node. If a producer has won the xchg + * but not yet completed the prev->next store, treat as empty - + * caller retries. + */ + + tail = (FAR struct mpsc_node_s *) + (intptr_t)atomic_ptr_read(&q->tail); + if (head != tail) + { + return NULL; + } + + /* Re-enqueue the stub so the queue remains non-empty after we + * detach `head`. Producers see this exactly like any other enqueue. + */ + + mpsc_enqueue(q, &q->stub); + + next = (FAR struct mpsc_node_s *) + (intptr_t)atomic_ptr_read_acquire(&head->next); + if (next == NULL) + { + return NULL; + } + + q->head = next; + return head; +} + +/**************************************************************************** + * Name: mpsc_dequeue_spin + * + * Description: + * Wrapper that hides the transient-inconsistent window from the + * caller. Busy-spins while a producer is in the middle of an + * enqueue, returns NULL only when the queue is genuinely empty. + * + * Use when transient windows are expected to be very short + * (hand-off between cores, no producer preemption) and the caller + * prefers low-latency to giving up the CPU. Not suitable when a + * producer may be preempted while in mpsc_enqueue() - the spin + * would last as long as that preemption. + * + * Loses lock-freedom of the consumer side: progress depends on + * the in-flight producer making progress. + * + ****************************************************************************/ + +static inline_function FAR struct mpsc_node_s * +mpsc_dequeue_spin(FAR struct mpsc_queue_s *q) +{ + FAR struct mpsc_node_s *node; + + while ((node = mpsc_dequeue(q)) == NULL) + { + if (mpsc_empty(q)) + { + return NULL; + } + + /* Transient: producer between xchg and prev->next store. */ + } + + return node; +} + +/**************************************************************************** + * Name: mpsc_dequeue_yield + * + * Description: + * Wrapper that hides the transient-inconsistent window by yielding + * the CPU instead of busy-spinning. Returns NULL only when the + * queue is genuinely empty. + * + * Use in cooperative or user-space contexts where giving up the + * CPU is preferable to spinning - especially when a producer may + * be preempted (yielding gives it a chance to run). + * + * Must not be called from interrupt context. + * + ****************************************************************************/ + +static inline_function FAR struct mpsc_node_s * +mpsc_dequeue_yield(FAR struct mpsc_queue_s *q) +{ + FAR struct mpsc_node_s *node; + + while ((node = mpsc_dequeue(q)) == NULL) + { + if (mpsc_empty(q)) + { + return NULL; + } + + sched_yield(); + } + + return node; +} + +#endif /* __INCLUDE_NUTTX_MPSC_H */
