Add timeout to lock-free mutex

[nyh]

OSv's lock-free mutex implementation (lfmutex.cc, mutex.hh) does not support timeouts. This means that pthread_mutex_timedlock could not be directly implemented over our mutext (see #834), and trying to do this anyway required some ugly hacks and busy-waiting (see #1426).

The reason why our lock-free mutex does no support timeouts isn't a small missing feature, it's lack is for very fundamental reasons. The problem with timeouts is that what a timeout means is that after we have a queue of waiters (in lfmutex, it is lockfree/queue-mpsc.hh) waiting on this semaphore, one of them gives up on a timeout, and we need to remove it from the queue. The problem is how to do this safely and also in a lockfree manner (no spinlocks etc.).

This issue is about one day, perhaps, replacing OSv's lock-free mutex algorithm by a different lock-free mutex algorithm that does support removing waiters from the queue - i.e., timeout or other cancellations.

Claude Sonnet 4.6 proposes the following plan:

Proposed solution: MCS lock with timeout

The correct, lock-free, truly-bounded-timeout solution is the MCS lock with timeout algorithm described in:

Scott, M. L. and Scherer, W. N. III, "Scalable Queue-Based Spin Locks with Timeout", ACM SIGPLAN Notices, Proceedings of PPoPP 2001.

The MCS queue-based lock is a well-known algorithm (Craig 1993; Mellor-Crummey & Scott 1991) that, unlike OSv's current MPSC queue, naturally supports O(1) cancellation by a waiting thread. The Scott & Scherer 2001 paper extends it to handle timeout correctly and without races.

The central idea is:

1. Each thread has a statically allocated queue node (not a stack-allocated wait_record). Because the node's lifetime equals the thread's lifetime, there is no dangling-pointer hazard when another thread accesses it after the owner times out and returns.
2. The mutex holds an atomic tail pointer (rather than the current pushlist)/poplist pair). To enqueue, a thread atomically swaps the tail to point to its own node, and then links the old tail's next to its node. The thread then sleeps on a status field in its own node.
3. To dequeue (unlock), the holder sets the successor's status to granted, waking the successor.
4. Timeout/cancellation: The waiting thread attempts a CAS on its own node's status field from waiting to leaving.
   • If the CAS fails, it means unlock() concurrently set the status to granted — the thread actually holds the mutex and proceeds normally.
   • If the CAS succeeds, the thread is logically removed. It then performs a queue bypass: it updates the predecessor's next pointer to skip over its own node and point directly at its successor (if any). Because the node is statically allocated (in sched::thread), the predecessor can safely dereference it at any point. After the bypass completes, the thread returns ETIMEDOUT.

The bypass step has one non-trivial edge case: the successor may not have enqueued itself yet (the predecessor's next is still null). Scott & Scherer's solution is a two-phase protocol using a special leaving marker in the next pointer: the cancelling thread marks next as "leaving, successor should spin on predecessor's status instead of mine", and any arriving successor that sees this marker links directly to the predecessor, bypassing the cancelled node.

What changes in the codebase

In sched::thread (include/osv/sched.hh, sched.cc), add a per-thread MCS node struct:

struct mcs_node {
    std::atomic<mcs_node*> next{nullptr};
    // Status: waiting / granted / leaving
    std::atomic<int> status{mcs_waiting};
};

Add a mcs_node _mcs_node field to sched::thread. This is the node the thread uses whenever it queues for any lockfree::mutex. Its lifetime is the thread's lifetime.

In lockfree::mutex (include/lockfree/mutex.hh, lfmutex.cc), replace the current fields:

// REMOVED:
queue_mpsc<wait_record> waitqueue;
std::atomic<unsigned int> handoff;
unsigned int sequence;

With a single MCS tail pointer:

std::atomic<mcs_node*> tail{nullptr};

The count field and the owner/depth fields for recursive-mutex support are retained unchanged; they are orthogonal to the queuing mechanism.

Rewrite lock() using MCS enqueue: swap tail to your node, wait (sched::thread::wait_until(...)) on your_node.status until it becomes granted.

Rewrite unlock() using MCS dequeue: if tail == your_node and no successor, CAS tail back to null. Otherwise wait for your_node.next to appear (it must be about to arrive since tail != your_node), then set successor.status = granted.

Add the new method:

bool try_lock_until(sched::timer& timer);

implementing the Scott & Scherer cancellation: CAS status: waiting → leaving; if it fails, got the lock; if it succeeds, do the queue bypass and return false.

The RHO (Responsibility Hand-Off) protocol and all associated handoff/sequence logic is removed entirely. The race that the RHO protocol guards against — between incrementing count and pushing to the queue — does not arise in MCS, because the tail-swap and node linkage are a single atomic step.

The send_lock(), send_lock_unless_already_waiting()], and receive_lock()methods used for wait morphing bycondvar::wait()need to be re-examined. They rely on being able to push an externalwait_recordonto the mutex's queue. With MCS, the queue node belongs to the thread (stored insched::thread, so the morphing protocol needs updating: rather than pushing a foreign wait_record, condvar::wake_one()would transition the target thread's MCS node directly into the mutex's queue. This is possible but requires corresponding changes incondvar.cc`.

pthread.cc - replace the stub / hack pthread_mutex_timedlock and pthread_mutex_clocklock.

Summary of trade-offs

The current RHO-based algorithm is elegant for the non-timed case and avoids any per-thread state in the mutex itself. The MCS algorithm requires a per-thread node but in return gives clean O(1) timeout cancellation that is provably correct, race-free, and requires no spinlocks. The per-thread cost is one pointer and one integer per sched::thread — negligible.

The wait-morphing protocol used by condvar is the most delicate part of the migration and will need its own careful design, documented in a follow-up.

References
Mellor-Crummey, J. M. and Scott, M. L., "Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors", ACM TOCS, 1991. (Original MCS lock)
Scott, M. L. and Scherer, W. N. III, "Scalable Queue-Based Spin Locks with Timeout", PPoPP 2001. (MCS + cancellation — the core algorithm proposed here)
Gidenstam, A. and Papatriantafilou, M., "Blocking without Locking or LFTHREADS: A lock-free thread library", 2007. (RHO protocol — the basis of the algorithm being replaced)

Fixing wait morphing

Goal: restore single-sleep morphing using the per-thread MCS node.

The key idea: instead of pushing the wait_record* into the mutex queue, enqueue the sleeping thread's mcs_node into the MCS tail, and store a back-pointer wake_on_grant = wr in the node. When unlock() eventually grants the lock to that node, instead of setting status = mcs_granted, it calls wake_on_grant->wake(). The thread wakes from wr.wait()` directly — no intermediate wakeup.

Rewrite mutex::send_lock(wait_record* wr)

send_lock(wr):
  t    = wr->thread()
  node = &t->_mcs_node
  node.next            = null
  node.status          = mcs_waiting
  node.wake_on_grant   = wr
  node.in_mutex_queue  = true

  prev = _tail.exchange(node)
  if prev == null:
    // Uncontended: we have the lock immediately.
    node.wake_on_grant  = null
    node.in_mutex_queue = false
    wr->wake()          // thread wakes, calls receive_lock()
    return
  prev->next = node     // Contended: link predecessor; unlock() will call wr->wake() later

Update `mutex::unlock() for morphed nodes. When setting the successor's grant:

if successor->wake_on_grant != null:
    waiter* wr          = successor->wake_on_grant
    successor->wake_on_grant  = null
    successor->in_mutex_queue = false
    // Set status first (for the MCS bypass protocol on the successor side),
    // then wake the thread.
    successor->status.store(mcs_granted)
    wr->wake()          // thread wakes from wr.wait(), calls receive_lock()
else:
    successor->status.store(mcs_granted)  // normal: thread wakes from wait_until

Setting status = mcs_granted before wr->wake() matters for the timeout race:

Update condvar::wait() timeout path: After wr.wait(tmr) returns due to timeout, three cases exist:

1. wr still in condvar FIFO (wake_one was never called): lock _m, remove wr, return ETIMEDOUT as before. This case is unchanged.
2. wr.woken() == true (send_lock was called and the mutex was uncontended): call receive_lock(), return 0. This case is unchanged.
3. wr.woken() == false and wr not in condvar FIFO (send_lock was called, our MCS node is in the mutex queue): apply the Scott & Scherer MCS cancellation on the mutex:
   • CAS node.status: mcs_waiting → mcs_leaving
   • CAS fails (status == mcs_granted): the unlock() already called wr->wake() or is about to. Wait for wr.woken() to become true (one brief spin of at most one store — wr->wake() is called right after setting status). Call receive_lock(), return 0.
   • CAS succeeds: do the MCS bypass (update predecessor's next to skip us), clear in_mutex_queue. Return ETIMEDOUT. The thread then calls user_mutex->lock() normally.

condvar::wake_all()— no structural change needed: wake_all() calls send_lock(wr) in a loop. Since send_lock now enqueues per-thread MCS nodes, multiple threads can be morphed into the mutex queue in sequence. The CPU-affinity optimisation in wake_all (grouping same-CPU threads) can be preserved by sorting the wait_record list before enqueuing; or it can be temporarily dropped and restored later as a separate optimisation.

Then we also need to fix wake_lock / send_lock_unless_already_waiting. This is the path used by the sched::thread::wait_until(mutex, predicate) family, which bridges the mutex and the scheduler's own thread-status state machine (waiting → sending_lock → waking):

Rewrite send_lock_unless_already_waiting(wait_record* wr): This is called while holding the mutex. With MCS and the in_mutex_queue flag:

send_lock_unless_already_waiting(wr):
  assert(owned())
  t    = wr->thread()
  node = &t->_mcs_node
  if node.in_mutex_queue:
    return false             // already morphed by a concurrent condvar signal; skip
  node.next           = null
  node.status         = mcs_waiting
  node.wake_on_grant  = wr
  node.in_mutex_queue = true
  prev = _tail.exchange(node)
  prev->next = node          // prev cannot be null since we hold the lock (we're in the queue)
  return true

Note: since the caller holds the mutex, _tail always points to the holder's own node or some later waiter — it is never null when a thread holds the lock. So no special uncontended case here.

thread::wake_lock() in sched.cc: The function signature and logic stay the same (wake_lock(mutex* mtx, wait_record* wr)is called withmtxheld). The only thing that changes underneath it issend_lock_unless_already_waiting— which now uses the MCS node. Thesending_lockthread status state andlock_sentflag indetached_stateare unchanged. Thewait_until(mutex, predicate template code that checkslock_sentand callsreceive_lock()` is unchanged.

receive_lock() — unchanged. receive_lock() just sets owner = current, depth = 1. This is correct for MCS: by the time a morphed thread calls receive_lock(), the MCS unlock has already done the queue maintenance (cleared in_mutex_queue, nulled wake_on_grant). The thread is the logical owner.

Postscript: Comparison to Linux
Linux adopted the MCS algorithm in 2014, and uses them for spinlocks (so the locking part spins, doesn't sleep). the original MCS lock paper (Mellor-Crummey & Scott 1991), which was designed for shared-memory multiprocessors where threads genuinely busy-poll a memory location. In that context, spinning on a per-thread node (rather than a single shared variable) is the key scalability improvement — each thread's cache line is only written by one other thread (its predecessor), eliminating cache-line bouncing. In OSv, the busy-spin is replaced by a scheduler sleep, which is the right thing to do for a general-purpose OS mutex. The per-thread node structure of MCS is still valuable — it is what makes the timeout cancellation (the bypass) safe and O(1) — but the actual waiting is a sleep, not a spin.

In the Linux implementation, Each CPU waiting for a spinlock spins on its own per-CPU node rather than the shared lock word, exactly to avoid cache-line bouncing. This is in kernel/locking/qspinlock.c and kernel/locking/mcs_spinlock.h.

In Linux also mutex kernel/locking/mutex.c uses an MCS queue (the osq — optimistic spin queue) for the spinning path before a thread goes to sleep.

The Linux MCS nodes are per-CPU (for spinlocks, which cannot sleep) or per-task (for the osq used in mutex/rwsem). This is exactly the "per-thread static node" approach described for OSv — the node lives as long as the CPU/task, so there is no memory lifetime hazard.

[nyh]

A more detailed plan from Claude Sonnet 4.6:
osv-mcs-mutex-plan.md