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

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.

>> +       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