Re: [PATCH 1/2] io_uring/mpscq: add lockless multi-producer, single-consumer FIFO queue

On Thu, Jun 11, 2026 at 7:21 PM Jens Axboe <[email protected]> wrote:
>
> On 6/11/26 7:13 PM, Caleb Sander Mateos wrote:
> >> + * Push a node onto the queue. Safe against concurrent pushes from any context,
> >> + * and against the (single) consumer. Returns the previous tail node, which is
> >> + * &q->stub if and only if the queue was empty before this push.
> >> + */
> >> +static inline struct llist_node *mpscq_push(struct mpscq *q,
> >> +                                           struct llist_node *node)
> >
> > It seems odd to return the previous tail node. The pointer can't be
> > dereferenced, as the node could be popped and freed at any point. The
> > return value is only compared against &stub  to determine whether the
> > queue was empty. Seems like the interface would be simpler and avoid
> > leaking implementation details by just returning whether the queue was
> > empty before the push.
>
> That's not a bad idea, I'll take a look at that. I have a v2 of the
> series which converts the non-defer task_work as well, so need to send
> that out. Will do so tomorrow.
>
> >> +{
> >> +       struct llist_node *prev;
> >> +
> >> +       node->next = NULL;
> >> +       /*
> >> +        * xchg() implies a full barrier, so the initialization of the
> >> +        * entry (including ->next above) is visible before the node can
> >> +        * be reached, either via ->tail or via ->next chasing from the
> >> +        * head once the store below has linked it.
> >> +        */
> >> +       prev = xchg(&q->tail, node);
> >> +       WRITE_ONCE(prev->next, node);
> >
> > I think this needs to be a release-order store and the READ_ONCE()s in
> > mpscq_pop() need to be acquire-order loads. Since mpscq_pop() doesn't
> > necessarily load q->tail, there's no happens-before relationship
> > between pushing a node and popping it.
>
> Don't think that's necessary. The xchg() is fully ordered and hence acts
> as smp_mb() on both sides — so every init store propagates before the
> link store. A release on the link store would only add ordering for
> stores issued between the xchg and the link, but we have none of those.
>
> For the consumer, every dereference of a node should be
> address-dependent on the READ_ONCE() that observed it.
> Address dependencies from marked loads are honored everywhere, for
> example alpha even has a read barrier there.

I'm not too familiar with the Linux kernel memory model, you're
probably right :)

Best,
Caleb

>
> >> +       return prev;
> >> +}
> >> +
> >> +/*
> >> + * Pop the oldest node off the queue, or return NULL if no node is available.
> >> + * NULL is returned both when the queue is empty and when a producer has
> >> + * published a node via ->tail but hasn't linked it yet; use mpscq_empty() to
> >> + * tell the two apart. Single consumer only, with headp being the consumer
> >> + * cursor that mpscq_init() set up.
> >> + */
> >> +static inline struct llist_node *mpscq_pop(struct mpscq *q,
> >> +                                          struct llist_node **headp)
> >> +{
> >> +       struct llist_node *head = *headp;
> >> +       struct llist_node *next = READ_ONCE(head->next);
> >> +
> >> +       if (head == &q->stub) {
> >> +               if (!next)
> >> +                       return NULL;
> >> +               *headp = next;
> >> +               head = next;
> >> +               next = READ_ONCE(head->next);
> >> +       }
> >
> > I would find it a bit clearer to avoid using "next" to refer to the
> > actual head in the stub case:
> >
> > struct llist_node *head = *headp, *next;
> > if (head == &q->stub) {
> >         head = READ_ONCE(head->next);
> >         if (!head)
> >                 return NULL;
> >        *headp = head;
> > }
> > next = READ_ONCE(head->next);
>
> I'll see if I can make that part look neater, I agree with you here.
>
> >> +       if (next) {
> >> +               *headp = next;
> >> +               return head;
> >> +       }
> >> +       /*
> >> +        * 'head' is the last linked node, it can only be handed out once the
> >> +        * stub has taken its place as the tail. If the cmpxchg fails, a
> >> +        * producer has made a new node the tail but hasn't linked it to 'head'
> >
> > nit: "but hasn't linked 'head' to it" since the pointer goes from head
> > to the new tail?
>
> Good catch, yes it should read from head to new tail.
>
> >> +        * yet - bail and let the caller retry.
> >> +        */
> >> +       q->stub.next = NULL;
> >> +       if (try_cmpxchg(&q->tail, &head, &q->stub)) {
> >> +               *headp = &q->stub;
> >> +               return head;
> >> +       }
> >> +       return NULL;
> >
> > An early return if the try_cmpxchg() fails would reduce indentation of
> > the successful path.
>
> I deliberately wrote it that way, reads better to me...
>
> --
> Jens Axboe