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

[Jens Axboe <axboe@kernel.dk>]

On 6/11/26 10:49 AM, Gabriel Krisman Bertazi wrote:
> Jens Axboe <axboe@kernel.dk> writes:
> 
>> Local task_work is currently using llists for managing the work,
>> but that's a LIFO type of list. This means that running this task_work
>> needs to reverse the list first, to ensure fairness in running the
>> queued items.
>>
>> Add a lockless FIFO queued, based on Dmitry Vyukov's intrusive MPSC
>> node-based queue algorithm, modified with an externally held consumer
>> cursor and conditional stub reinsertion. See comments in the header.
>>
>> Producers are wait-free: a push is a single xchg() on the queue tail,
>> which serializes concurrent producers and defines the FIFO order, plus
>> a store linking the node to its predecessor. There are no cmpxchg retry
>> loops, and pushing is safe from any context, including hardirq.
>>
>> The cost of linked list FIFO ordering is that a push publishes the node
>> in two steps - the xchg() makes it visible as the new tail before the
>> subsequent store links it into the chain that is reachable from the
>> head. A consumer hitting that window gets a NULL from mpscq_pop() while
>> mpscq_empty() reports false, and must retry later rather than treat the
>> queue as empty. The window is two instructions wide, but a producer can
>> get preempted inside it, so the consumer must not busy wait on it.
>>
>> The consumer side supports a single consumer at a time, with callers
>> providing their own serialization. A stub node, which also defines the
>> empty state (tail == stub), allows the consumer to detach the final
>> node without racing against producer link stores: that node is only
>> handed out once the stub has been cmpxchg'ed back in as the tail. This
>> also guarantees that the previous tail returned by mpscq_push() cannot
>> get freed before that push has linked it, making it always valid for
>> comparisons.
>>
>> The consumer cursor is deliberately not part of the queue struct - the
>> caller owns it and passes it to mpscq_pop(). This is done to separate
>> the consumer and producers cacheline.The cursor is written for
> 
> Interesting stuff!  The commit message is truncated here, though.

Huh yes indeed, wonder how that happened. Was doing some shuffling and
editing, probably messed it up.

>> Signed-off-by: Jens Axboe <axboe@kernel.dk>
>> ---
>>  include/linux/io_uring_types.h |  12 ++++
>>  io_uring/mpscq.h               | 121 +++++++++++++++++++++++++++++++++
> 
> There's nothing io_uring specific here.  Perhaps put in lib/ directly
> some a wider audience can review  and use?

I think keeping it local is fine, if someone else wants to use it, then
it should just get migrated to include/linux/ instead as it's all in
that header. Code is small enough that it doesn't warrant .c and
non-inlines for it.

For now, as there's one consumer of this, better to keep it local.

-- 
Jens Axboe