Crate maillon 

A concurrent intrusive list for building synchronization primitives.

Maillon is the French word for a chain link.

Features

• 100% safe API
• #![no_std], no allocation
• Atomic emptiness check to avoid acquiring the mutex if the list is empty
• Lock-free insertion: multiple nodes can be inserted concurrently while another is being removed; removal requires locking
• Optional atomic state embedded in the list when empty (to carry a semaphore counter, a closed flag, etc.)
• WaitList, a high-level asynchronous wait list with customizable synchronization built on top of the low-level List

Usage

WaitList is a ready-to-use asynchronous wait list, built on top of List:

use std::sync::atomic::{AtomicBool, Ordering::Relaxed};

use maillon::WaitList;

#[derive(Default)]
pub struct Event {
    done: AtomicBool,
    wait_list: WaitList,
}

impl Event {
    pub async fn wait(&self) {
        let _ = self.wait_list.wait_until(|_| self.done.load(Relaxed)).await;
    }

    pub fn set(&self) {
        self.done.store(true, Relaxed);
        self.wait_list.notify_all();
    }
}

List is the building block: Nodes are pinned, carry user data implementing NodeData, and are pushed to the back without locking, while every other operation goes through List::lock. Here is a minimal wait list, supporting only notify_one:

use std::{
    future::Future,
    mem,
    pin::Pin,
    sync::atomic::{
        Ordering::{Relaxed, SeqCst},
        fence,
    },
    task::{Context, Poll, Waker},
};

use maillon::{List, Node, NodeData, NodeState, list::LockedList, node_wrapper};

#[derive(Default)]
pub struct WaitList {
    list: List<Waiter>,
}

#[derive(Default)]
struct Waiter {
    waker: Option<Waker>,
    notified: bool,
}

impl WaitList {
    pub fn notify_one(&self) {
        fence(SeqCst);
        if !self.list.is_empty(Relaxed) {
            Self::notify_one_cold(&self.list);
        }
    }

    #[cold]
    fn notify_one_cold(list: &List<Waiter>) {
        Self::notify_one_locked(list.lock());
    }

    fn notify_one_locked(mut locked: LockedList<'_, Waiter>) {
        let Some(mut front) = locked.front() else {
            return;
        };
        front.notified = true;
        let waker = front.waker.take();
        front.unlink();
        drop(locked);
        if let Some(waker) = waker {
            waker.wake();
        }
    }

    pub fn wait(&self) -> Wait<'_> {
        Wait(Node::new(&self.list))
    }
}

node_wrapper! {
    pub struct Wait<'a>(Node<&'a List<Waiter>>);
}

impl Future for Wait<'_> {
    type Output = ();

    fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<()> {
        match self.node_mut().state() {
            NodeState::Unlinked(mut node) => {
                if mem::take(&mut node.notified) {
                    return Poll::Ready(());
                }
                node.waker = Some(cx.waker().clone());
                node.push_back(Relaxed);
                fence(SeqCst);
                Poll::Pending
            }
            NodeState::Linked(mut node) => node.update_waker(cx, |node| &mut node.waker),
        }
    }
}

impl NodeData<&List<Waiter>> for Waiter {
    fn new_state_if_last_node_on_drop(
        self: Pin<&mut Self>,
        _list: &&List<Waiter>,
        _list_data: &mut (),
    ) {
    }

    fn on_drop<'list>(
        self: Pin<&mut Self>,
        list: &'list &List<Waiter>,
        locked: Option<LockedList<'list, Self>>,
        _state_updated_on_unlink: bool,
    ) {
        if self.notified {
            match locked {
                Some(locked) => WaitList::notify_one_locked(locked),
                None => WaitList::notify_one_cold(list),
            }
        }
    }
}

See the examples for full implementations of tokio::sync::Notify and tokio::sync::Semaphore built with maillon, with fully identical API and behavior.

Re-exports

pub use list::List;

pub use list::ListRef;

pub use list::LockedList;

pub use node::Node;

pub use node::NodeData;

pub use node::NodeState;

pub use wait_list::WaitList;

pub use atomic_backoff as backoff;

Modules

linking

Linking and its variants.

list

The List and the types to operate on it.

node

The list Node and its accessors.

sync

The synchronization primitive abstractions (Mutex and Parker) used by List, and their implementations for the supported backends.

wait_list

An asynchronous wait list with customizable synchronization, built on top of List.

Macros

node_wrapper

A macro to define a simple wrapper around a Node, handling pin-projection.

Structs

WakerBatch

A fixed-capacity buffer of Wakers, stored inline.