Lockless MPSC FIFO queues speed up io_uring performance

Linux kernel's io_uring subsystem is moving from the generic lockless singly linked list (llist) to a dedicated lockless multi-producer/single-consumer (MPSC) queue for tracking pending work items, landing in kernel 7.2. The change, posted by Jens Axboe and based on an algorithm by Dmitry Vyukov, fixes structural inefficiencies in the old approach.

Because llist only supports head insertion, io_uring effectively used it as a stack, requiring an extra reversal pass to restore FIFO order before processing, plus a secondary list to hold reversed-but-unprocessed items when a batch was cut short. Adding entries also relied on a compare-and-swap retry loop, which caused cache-line contention under heavy multi-producer load.

The new mpscq structure lets producers append to the tail via a single atomic xchg() operation with no retries, while a sentinel 'stub' node handles the empty-list edge case. Consumers keep a separate head pointer in its own cache line, minimizing false sharing with producers, and process items in true arrival order without any reordering step.

For engineers, this is a concrete example of how targeted lockless data structures can outperform generic kernel primitives in high-throughput, high-concurrency I/O paths, and a readable case study of the Vyukov MPSC queue algorithm in production kernel code.