"Ticket-lock" mutexes motivate "interior concurrency," not just "interior mutability"

I've been experimenting with ticket-style mutexes for sharing a location between async tasks, inspired by the Mellor-Crummy and Scott algorithm described in this paper and used in the Linux kernel's spinlocks.

Each interested task creates a "ticket' structure which looks something like this:

struct Ticket<'l> {
    _pin: PhantomPinned,
    lock: &'l Lock,
    prev: AtomicPtr<Ticket<'static>>,
    next: AtomicPtr<Ticket<'static>>,
    waker: UnsafeCell<Option<Waker>>,
}

These structures are linked together to form a queue of waiting tasks. The task that owns the ticket at the head of the queue is granted exclusive access to the shared resource. When a task unlocks or cancels interest, Ticket is removed from the list, the new head is notified, and the removed Ticket is freed.

Linux (IIUC) allocates tickets in per-CPU storage, but C could also allocate them on the stack. But as far as I can tell, Rust cannot allocate this structure in a local variable (stack or async) in a way that satisfies Miri.

A safe interface to Ticket makes use of unique ownership and borrowing, but neighboring tasks can also access prev, next, and waker. That access could happen while the task is pending or concurrently from another thread.

In order to make this work Ticket can be protected by a pinning guarantee: once Pin<&mut Ticket> is created its location will not be reused until Ticket is dropped. The drop operation must exclude other threads and remove Ticket from the linked list before it returns.

(If Ticket is forgotten, the mutex deadlocks - the same behavior as if MutexGuard is forgotten.)

Unfortunately, as soon as Miri sees &mut Ticket it does not allow previously created raw pointers to access the atomic variables. I don't know how this will translate to concurrency, but it looks like the compiler could assume that the atomic variables are no longer accessible by other threads (they don't alias!) and downgrade the atomic operations within drop to unordered ones.

Wrapping Ticket within another layer of interior mutability doesn't help. Interior mutability is "mut-within-shared" not "shared-within-mut." This very simple Playground demonstrates the issue:

&mut AtomicU32 is never explicitly created; it's always &AtomicU32
But &mut UnsafeCell<AtomicU32> creates a conflict anyway.

The best work-around is to move the shared state into something like Box<TicketInner>. As long as you're lucky enough to have an allocator and don't mind the extra overhead, that works.

UnsafeCell is not "in-line allocation of a distinct place for the purpose of aliasing analysis" like I naively assumed. It's not a cheaper Box.

rust-lang / unsafe-code-guidelines

"Ticket-lock" mutexes motivate "interior concurrency," not just "interior mutability" #275