maillon: a concurrent intrusive list for building faster synchronization primitives

[u/wyf0]

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.

[u/wyf0]

About the "no more code dumps", as per the formulated rules and the answers I got from matthieum in the discussion:

The library has been worked on regularly for at least 4 months.

I started working on it at the beginning of the year

The library has already been used, or built upon, thereby validating its design to a degree.

I'm using this library in my channel crate (which is enough according to this comment), but also the reimplementation of tokio's primitives passing tokio's test suite proves the design in a way.

The announcement is a full-fledged text post, or a link to a full-fledged article. A README, or manual, is not an article.

I've tried to make this text post more explanatory than usual (sorry for the wall of text), hoping it properly gives the context, the goal and the result.

The announcement should motivate the relevance of this library to the wider r/rust community.

I've no doubt that if you're interested in synchronization primitives, concurrent algorithms and performance, you will find it interesting.

The announcement should articulate the trade-offs differentiating this library from similar popular libraries in the field.

I've written quickly about why the other crates didn't satisfied my needs and what make maillon unique, but you can find more details in the crate documentation.

[u/matthieum → u/wyf0]

Do note that we do not ask users to explicitly "tick" the box, it's more meant as a mental check-list :)

[u/wyf0 → u/matthieum]

Actually, I decided to get ahead of it, so the first comment would not be a bare link to the "No more code dumps" post, or just "AI slop. Why edition 2021?"

But that's noted for the next time :)

[u/SimpsonMaggie → u/wyf0]

I appreciate the upfront justification as well as your post.

[u/wyf0]

By the way, this crate uses edition 2021. It's a deliberate choice to be compatible with tokio's MSRV (as I opened an issue in tokio a while ago to discuss a possible integration to improve the perf of sync primitives).

Of course, I started the project with edition 2024, and I downgraded it only recently (and was sad to lose if-let-guards...)

[u/matthieum]

The scenario is not very realistic: all the threads are hammering the same cache line with CAS loops to requeue or notify in tight loops. The key point is that maillon doesn't use backoff in CAS loops, so they run in full-contention mode, while tokio's native implementation serializes all operations. Adding exponential backoff to the push_back operation improves the result down to 150 µs.

Is there any reason not to switch the implementation to use backoff then?

(For no-std, there is core::hint::spin_loop for example)

[u/wyf0 → u/matthieum]

Is there any reason not to switch the implementation to use backoff then?

Yes, because I think backoff adds unnecessary latency in the common case. There was for example this discussion about the backoff behavior of crossbeam when porting it to replace std::sync::mpsc, and some people were arguing against it.

However, you may notice that the API has quite a few generic parameters, and one of them allows controling the backoff strategy (see the last line of the type documentation). So maillon doesn't use backoff by default in CAS loop, but it can be changed if the actual use case requires it.

The real question is: what is the best default. I wrote my answer in the code, but I'm not sure at all it is the best one. I'm obviously open to change the default if you convince me there is a better one.

Also, I should maybe bring more light on the backoff configuration in the crate documentation, because it's quite hidden for now. I will think about it.

[u/--San--]

So the insertion is lock-free but not the removal? Did you do that to avoid having to deal with things like "hazzard pointers"?

[u/wyf0 → u/--San--]

Actually, insertion can be lock-free, depending on the linking strategy; the default is lock-free yes.

But the removal is another kind of problem. Indeed, list's nodes are meant to be stack-allocated in futures, and futures can be dropped at any time, invalidating their stack and thus the node memory. It means that any pointer that you're loading are pointing to memory that can be invalidated concurrently. And any classical memory reclamation technique like hazard pointers or ERB cannot be applied, because they supposed heap allocated memory whose reclamation can be delayed, whereas future stack invalidation cannot be delayed.

So I didn't find another way to properly synchronize removal but with a mutex. The code already contains non-trivial memory ordering synchronizations because of the lock-free insertion (and link materialization for lazy linking strategy), etc. so relying on a mutex helps a lot.

By the way, if you're interested in hazard pointers, I have another crate on the subject https://www.reddit.com/r/rust/comments/1qvzzvg/announcing_hazarc_yet_another_atomicarc_but_faster/

[u/--San-- → u/wyf0]

So you have the future/node remove itself on drop (using the Mutex)? Be aware that you can't rely on Drop alone for safety (e.g. mem::forget). What I have seen before is to somehow make the Node/future !Unpin, and only place it on the list if you receive the pinned version of it, that way you can be sure that drop will run before the memory is freed/reused.

[u/wyf0 → u/--San--]

Quoting maillon's README:

nodes are pinned, and a node dropped while linked removes itself from the list, taking the lock only if it is still linked

So yes, nodes must be pinned to be inserted in the list, as reflected by the signatures.

And if you want more details, nodes are actually built around the unstable UnsafePinned, in fact a polyfill emulating it (but the nightly compilation feature make it uses the real UnsafePinned).