Lockless MPSC FIFO queues for io_uring [LWN.net]
LWN<br>.net<br>News from the source
Content Weekly Edition<br>Archives<br>Search<br>Kernel<br>Security<br>Events calendar<br>Unread comments
LWN FAQ<br>Write for us
Edition Return to the Front page
User:<br>Password: |
Log in /<br>Subscribe /<br>Register
Lockless MPSC FIFO queues for io_uring
We're bad at marketing
We can admit it, marketing is not our strong suit. Our strength is<br>writing the kind of articles that developers, administrators, and<br>free-software supporters depend on to know what is going on in the<br>Linux world. Please subscribe today to help us keep doing that, and so<br>we don’t have to get good at marketing.
By Jonathan Corbet<br>July 15, 2026
Processes that use io_uring<br>tend to keep a lot of balls in the air; being able to have many operations<br>underway at any given time is part of the point of that API in the first<br>place. The io_uring subsystem must, as a result, keep track of a lot of<br>tasks that have to be performed at the right time. In current kernels,<br>io_uring uses a standard kernel linked-list primitive to track those work<br>items. As of the 7.2 kernel release, though, io_uring will, instead, use a<br>new lockless, multi-producer, single-consumer (MPSC) queue, resulting in<br>some notable performance gains. Lockless algorithms tend to be tricky, but<br>the one used here is relatively approachable and shows how these algorithms<br>can work.
The old way's shortcomings
Task queues in pre-7.2 io_uring are based on the kernel's lockless<br>singly linked list (llist) API. At the core of this type is a simple<br>structure:
struct llist_node {<br>struct llist_node *next;<br>};
This structure, when embedded within another structure containing the<br>actual data of interest, contains the links that bind those outer<br>structures into a list.
There are a few reasons why this list type, despite being designed for<br>performance, is not ideal for io_uring. Since an llist is a singly linked<br>list, it can only realistically be accessed from the head. For a list<br>where producers add items and consumers remove them, an llist is<br>essentially a stack. Work items in io_uring need to be processed in the<br>order they were received, for basic fairness purposes if nothing else, so a<br>pass must be made over the task queue to reverse its order before each<br>processing run. To make things worse, io_uring might choose not to process<br>the whole list if it is too long, but the remaining items, having been<br>reversed in order, cannot simply be put back onto the task list. So a<br>separate list for reversed-but-not-processed items must be maintained.<br>Finally, adding items to an llist involves accessing a single head pointer;<br>that can be done without taking locks, but it does require a retry loop.<br>For heavily contended lists, those retries (and associated cache-line<br>bouncing) can hurt.
Solving these problems requires a data structure that is better suited to<br>the needs of the io_uring subsystem. It must handle multiple producers<br>putting work items on the lists, without locking and with a minimum amount<br>of contention. There is a single consumer for each list; that consumer<br>should avoid cache contention with the producers to the greatest extent<br>possible. And, clearly, the need to reorder lists before processing should<br>not exist.
Lockless MPSC queues
The solution is the lockless MPSC queue, posted by Jens<br>Axboe and using an algorithm credited to Dmitry Vyukov. This queue still<br>uses struct llist_node to tie the entries of the list together,<br>but the head of the list looks like this:
struct mpscq {<br>struct llist_node *tail;<br>struct llist_node stub;<br>};
The term "head" is actually a bit misleading, since there is no pointer to<br>the head of the list here; we'll get to that later. This view of the list<br>is intended for the use of the producers, who need to add items to the tail<br>of the list. The stub entry is a sentinel that is only present on<br>the list if it is the only entry there — if the list is empty, in other<br>words. When the list is initialized, the tail pointer is set to<br>point at the stub entry.
The stub entry's next pointer is set to NULL. The<br>addition of a node to the tail of the list is done with a call to this<br>short function:
static inline bool mpscq_push(struct mpscq *q, struct llist_node *node)<br>struct llist_node *prev;
node->next = NULL;<br>prev = xchg(&q->tail, node);<br>WRITE_ONCE(prev->next, node);<br>return prev == &q->stub;
The next pointer in the new entry is set to NULL,<br>indicating that it is the end of the list. Then, the xchg() call<br>atomically stores a pointer to the new entry in the list's tail<br>pointer, returning the previous value of that pointer; in the case of an<br>empty list, that will be a pointer to the stub entry. The next<br>pointer of the previous end-of-list entry (which, again, might have been<br>the stub) is then set to the new entry, completing the task of adding that<br>entry to the list.
There is a subtlety to lockless algorithms that is worth noting here.<br>Once the tail pointer has been aimed at the new list entry, that<br>entry is...