mutex.h

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/>.
 */
 
#pragma once
 
/** @file
 * 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.
 */
 
#include <stdatomic.h>
 
#include "serene/rt/fiber.h"
 
typedef struct srn_fiber_mutex_t {
  /// A pointer to the waiter's stack head. nullptr == unlocked. Contending fibers push onto the
  /// stack lock free, and the holder drains it (it's basically a treiber stack). So having a waiter
  /// implies the lock is acquired by someone.
  _Atomic(srn_fiber_t *) state;
 
  /// A private (In the sense that it only touched only by the current lock holder during unlock)
  /// pointer to the head of the waiters in order.  Since it is private it needs not to be atomic.
  /// The holder fills it in one reversed batch when it drains the incoming stack, then pops one
  /// fiber from its head per unlock. Threaded through `srn_fiber_t.link`.
  srn_fiber_t *waiters_head;
} srn_fiber_mutex_t;
 
/**
 * Initialise `m` to the unlocked state.
 */
void srn_fiber_mutex_init(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.
 */
void srn_fiber_mutex_lock(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`.
 */
void srn_fiber_mutex_unlock(srn_fiber_mutex_t *m);