https://github.com/wyfo/maillon
Hello Rust,
I've just published my latest crate, a concurrent intrusive list for building synchronization primitives, featuring a high-level wait-list with atomic emptiness check, customizable synchronization, and lock-free insertion.
But first, what is it and why did I write such a data structure?
An intrusive list is a linked list whose inserted nodes directly embed the linking pointers. It is practical as it doesn't require allocating the nodes, which can live directly on the stack. It is especially used all over the async ecosystem in Rust, like in tokio, but also in std primitives like Once, as it allows cheap registration (no allocation) of wakers into primitives' wait-lists. However, having nodes on the stack is dangerous with futures, as futures can be dropped at any moment, releasing their stack memory. That's why node access must be synchronized, and the easiest way to do it is with a mutex, as done by 100% of the Rust implementations I know.
As I'm currently working on an MPSC channel implementation, I needed some synchronization primitives for the producers and for the receiver. In my previous post, I talked about the one I crafted for a single receiver. Then I needed one for multiple producers. Both synchronization primitives have the same design goal in mind: the cheapest possible wake/notify_one operation (i.e. read-only) when no waiter is registered, and a customizable synchronization to use SeqCst atomic operations or SeqCst fences (or RMWs) depending on the use case and/or the platform. Being read-only limits contention so the primitive can be stored in the shared cache-line of the channel.
Because multiple producers might be waiting and register themselves, an intrusive list with stack-allocated nodes was the ideal primitive. There are a few crates in the ecosystem providing this type of list, like pin-list, but there are also many crates that implement their own internal intrusive lists, which is a shame. However, I found no crate providing the primitive I needed (cheap notify_one + customizable synchronization); the closest ones were event-listener and async-event.
I could have gone with a mutex-protected pin-list beside an atomic emptiness flag, which is by the way roughly what crossbeam-channel uses (with a Vec instead of an intrusive list). But I had another idea in mind: what if I could make the node insertion lock-free? This is indeed a good property for an MPSC channel, where all producers register at the same time once the channel is full, while the receiver might concurrently release a slot. This idea led me to the current design, where the tail of the list is an atomic pointer which can simply be loaded to know if the list is empty (correct synchronization is not trivial though).
Then I got another idea: when the list is empty, the tail bits could be used to store an arbitrary state, like a semaphore counter or a mutex state. With it, I reimplemented tokio-compatible Semaphore and Notify, which beat tokio's on its own benchmark. Actually, the maillon-based semaphore beats all other semaphores of the ecosystem (futures-intrusive, asyncband, etc.) by a fair margin. I didn't imagine there were so many of them, but here is a new one to rule them all; you can find the numbers behind this claim in the crate's dedicated README.
But most importantly, my wait-list works well and is as fast and customizable as it can be, so I can use it in my channel. And the crate is of course extensively tested with loom and miri to ensure its correctness; the semaphore and notify reimplementations also pass tokio's loom test suite.
If you are interested in synchronization primitives, don't hesitate to take a look. There is a lot more to talk about (safe API without abort, generic linking strategy, persistent state, priority inversion, etc.), but this post is already quite long. Happy to answer your questions.
LLM disclaimer: most of the code was written at the beginning of the year when I was barely using LLMs to generate code. I did use LLMs for my recent work on it, mostly for refactoring, but also POCing a lot of ideas. There is not a single generated line that I haven't reviewed, and only a few non-boilerplate lines that I haven't reworked. However, while I wrote 100% of the documentation and comments myself in my previous projects, I used AI to sketch a significant part of the documentation, and I have to admit it sucked at it (surely a skill issue). So I ended up rewriting most of it, but LLMs are still fantastic at reviewing. Of course, this post was 100% written by me.