mutex.c

Go to the documentation of this file.

/* -*- C -*-
 * Serene programming language
 * Copyright (C) 2019-2026 Sameer Rahmani <lxsameer@lxsameer.com>
 *
 * This library is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library.  If not, see <https://www.gnu.org/licenses/>.
 */
 
#include "serene/rt/fiber/mutex.h"
 
#include "serene/rt/fiber.h"
 
/**
 * Marker stored in srn_fiber_mutex_t.state to mean the lock is held with no waiter queued. Only its
 * address matters, its fields are never touched, so it only has to be a non-null `srn_fiber_t`
 * pointer distinct from every real fiber. It also sits at the bottom of the incoming stack and
 * terminates it, so a waiter push and the drain walk need no null special case.
 */
static srn_fiber_t srn_mutex_held_marker;
#define SRN_MUTEX_HELD_WITH_NO_WAITER (&srn_mutex_held_marker)
 
/**
 * Suspend commit function for a contended `srn_fiber_mutex_lock`. Since the worker routine runs it
 * once `self` is off its stack (see `srn_fiber_suspend`), so pushing `self` onto the waiter stack
 * cannot race the running fiber.
 *
 * If the lock has gone free since the fast path failed, it takes the lock and returns false to
 * resume `self` at once. Otherwise it pushes `self` onto the incoming stack and returns true to
 * stay suspended.
 */
static bool srn_fiber_mutex_suspend(srn_fiber_t *self, void *arg) {
  srn_fiber_mutex_t *m = arg;
  srn_fiber_t *cur     = atomic_load_explicit(&m->state, memory_order_acquire);
  for (;;) {
    // This check is what closes the lost wakeup window between the failed fast path and the push, a
    // concurrent unlock can never leave `self` parked on a lock nobody holds.
    if (cur == nullptr) {
 
      if (
        atomic_compare_exchange_weak_explicit(
          &m->state, &cur, SRN_MUTEX_HELD_WITH_NO_WAITER, memory_order_acquire, memory_order_acquire
        )
      ) {
        // We got lucky. The lock is ours, don't suspend the fiber and run with the lock
        return false;
      }
      // Somebody else change the state before us, `cur` is now loaded with the new value,
      // retry is likely to fail and we will land on the locked branch.
      continue;
    }
 
    // Locked, push self as the new stack top. `cur` is the held marker or a fiber, so the chain
    // always bottoms out at the marker.
    self->link = cur;
    if (
      atomic_compare_exchange_weak_explicit(
        &m->state, &cur, self, memory_order_release, memory_order_acquire
      )
    ) {
      // stay suspended a future unlock hands the lock to us
      return true;
    }
  }
}
 
void srn_fiber_mutex_init(srn_fiber_mutex_t *m) {
  atomic_init(&m->state, nullptr);
  m->waiters_head = nullptr;
}
 
void srn_fiber_mutex_lock(srn_fiber_mutex_t *m) {
  srn_fiber_t *expected = nullptr;
 
  if (
    atomic_compare_exchange_strong_explicit(
      &m->state, &expected, SRN_MUTEX_HELD_WITH_NO_WAITER, memory_order_acquire,
      memory_order_relaxed
    )
  ) {
    // Yay, uncontended
    return;
  }
 
  // Contended: suspend. The reattempt lives in the commit, and on resume we own the lock, so there
  // is nothing to recheck here.
  srn_fiber_suspend(srn_fiber_mutex_suspend, m);
}
 
void srn_fiber_mutex_unlock(srn_fiber_mutex_t *m) {
  // Serve the oldest waiters.
  if (m->waiters_head != nullptr) {
    srn_fiber_t *next = m->waiters_head;
    m->waiters_head   = next->link;
    srn_fiber_ready(next);
    return;
  }
 
  // The FIFO queue is drained. Detach the incoming stack in one swap, or release the
  // lock if no waiter is queued.
  srn_fiber_t *cur = atomic_load_explicit(&m->state, memory_order_relaxed);
  for (;;) {
    if (cur == SRN_MUTEX_HELD_WITH_NO_WAITER) {
      // Held with nothing queued, drop the lock.
      if (
        atomic_compare_exchange_weak_explicit(
          &m->state, &cur, nullptr, memory_order_release, memory_order_relaxed
        )
      ) {
        return;
      }
 
      // Somebody just added itself to the waiters list by moving the state stack
      continue;
    }
 
    // Take the whole batch, leaving the lock held with an empty incoming stack.
    if (
      atomic_compare_exchange_weak_explicit(
        &m->state, &cur, SRN_MUTEX_HELD_WITH_NO_WAITER, memory_order_acquire, memory_order_relaxed
      )
    ) {
      // Reverse the batch (newest first) into oldest first order, stopping at the marker (no waiter
      // marker) that terminates the stack, store it in the waiters list, and ready the oldest
      // fiber.
      //
      // The next call to unlock on the same lock will go through the waiters_head tha we prepared
      srn_fiber_t *fifo = nullptr;
      for (srn_fiber_t *top = cur; top != SRN_MUTEX_HELD_WITH_NO_WAITER;) {
        srn_fiber_t *nxt = top->link;
        top->link        = fifo;
        fifo             = top;
        top              = nxt;
      }
      // Hand off to the oldest; keep the rest queued for later unlocks.
      m->waiters_head = fifo->link;
      srn_fiber_ready(fifo);
      return;
    }
  }
}