mutex.h File Reference

A fiber blocking mutex. More...

#include <stdatomic.h>
#include "serene/rt/fiber.h"

Include dependency graph for mutex.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	srn_fiber_mutex_t

Typedefs
typedef struct srn_fiber_mutex_t	srn_fiber_mutex_t

Functions
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.

Detailed Description

A fiber blocking mutex.

This lock suspends the calling fiber while the lock is held elsewhere and lets the worker run other fibers meanwhile. It is therefore only valid to call from INSIDE A RUNNING FIBER. Calling it from the worker thread, a signal handler, or any other non-fiber context is an error, since there would be no fiber to suspend.

The lock is not recursive, a fiber that locks a mutex it already holds deadlocks against itself. state carries no owner identity to detect it.

Waiters are served in FIFO order, so no waiter starves under sustained contention. We achieve that by having the state of a like to act as a stack and unlucky fibers add themselves to the stack and use srn_fiber_t.link to point to the next fiber in the stack. Then a lucky fiber, on the unlocking time, will walk the stack, reverse the order to make it a FIFO queue and populates the waiters_head of the lock. This way the next time a fiber will unlock the lock, it will hand the lock to the oldest waiting fiber.

Definition in file mutex.h.

Typedef Documentation

srn_fiber_mutex_t

typedef struct srn_fiber_mutex_t srn_fiber_mutex_t

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_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: