mutex.c File Reference

#include "serene/rt/fiber/mutex.h"
#include "serene/rt/fiber.h"

Include dependency graph for mutex.c:

Go to the source code of this file.

Macros
#define	SRN_MUTEX_HELD_WITH_NO_WAITER   (&srn_mutex_held_marker)

Functions
static bool	srn_fiber_mutex_suspend (srn_fiber_t *self, void *arg)
	Suspend commit function for a contended srn_fiber_mutex_lock.
void	srn_fiber_mutex_init (srn_fiber_mutex_t *m)
	Initialise m to the unlocked state.
void	srn_fiber_mutex_lock (srn_fiber_mutex_t *m)
	Acquire m.
void	srn_fiber_mutex_unlock (srn_fiber_mutex_t *m)
	Release m.

Variables
static srn_fiber_t	srn_mutex_held_marker
	Marker stored in srn_fiber_mutex_t.state to mean the lock is held with no waiter queued.

Macro Definition Documentation

SRN_MUTEX_HELD_WITH_NO_WAITER

#define SRN_MUTEX_HELD_WITH_NO_WAITER   (&srn_mutex_held_marker)

Definition at line 30 of file mutex.c.

Function Documentation

srn_fiber_mutex_init()

void srn_fiber_mutex_init

(

srn_fiber_mutex_t *

m

)

Initialise m to the unlocked state.

Definition at line 76 of file mutex.c.

                                                {
  atomic_init(&m->state, nullptr);
  m->waiters_head = nullptr;
}

Here is the caller graph for this function:

srn_fiber_mutex_lock()

void srn_fiber_mutex_lock

(

srn_fiber_mutex_t *

m

)

Acquire m.

If the lock is free it is taken at once, otherwise the calling fiber is suspended and resumes owning the lock, handed off directly by the unlocking fiber. Must be called from a running fiber.

Definition at line 81 of file mutex.c.

                                                {
  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);
}

Here is the call graph for this function:

Here is the caller graph for this function:

srn_fiber_mutex_suspend()

bool srn_fiber_mutex_suspend ( srn_fiber_t * self, void * arg )

static

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.

Definition at line 41 of file mutex.c.

                                                                  {
  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;
    }
  }
}

Here is the caller graph for this function:

srn_fiber_mutex_unlock()

void srn_fiber_mutex_unlock

(

srn_fiber_mutex_t *

m

)

Release m.

If any fibers are waiting, the longest waiting one is handed the lock and made ready, otherwise the lock is dropped. Must be called by the fiber that currently holds m.

Definition at line 99 of file mutex.c.

                                                  {
  // 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;
    }
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

srn_mutex_held_marker

srn_fiber_t srn_mutex_held_marker

static

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.

Definition at line 29 of file mutex.c.