mutex_tests.h

Go to the documentation of this file.

/* -*- C -*-
 * Serene programming language
 * Copyright (C) 2019-2026 Sameer Rahmani <lxsameer@lxsameer.com>
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 */
 
#pragma once
 
#include <stdatomic.h>
#include <stdint.h>
 
#include "base.h"
#include "serene/rt/fiber.h"
#include "serene/rt/fiber/mutex.h"
 
#define MUTEX_TESTS(X)                                                                \
  X("mutex::init", test_mutex_init), X("mutex::uncontended", test_mutex_uncontended), \
    X("mutex::mutual_exclusion", test_mutex_mutual_exclusion),                        \
    X("mutex::fifo_order", test_mutex_fifo_order),                                    \
    X("mutex::mt_contention", test_mutex_mt_contention)
 
static srn_fiber_mutex_t test_mtx;
static bool test_mtx_uncontended_ran;
 
static inline srn_fiber_t *test_mtx_state(void) {
  return atomic_load_explicit(&test_mtx.state, memory_order_relaxed);
}
 
// A freshly initialised lock is unlocked and has no waiters
static void test_mutex_init() {
  srn_fiber_mutex_init(&test_mtx);
  TEST_CHECK(test_mtx_state() == nullptr);
  TEST_CHECK(test_mtx.waiters_head == nullptr);
}
 
static srn_fiber_result_t test_mtx_uncontended_entry(srn_context_t *ctx, void *arg) {
  UNUSED(ctx);
  UNUSED(arg);
  test_mtx_uncontended_ran = false;
 
  srn_fiber_mutex_lock(&test_mtx);
  srn_fiber_mutex_unlock(&test_mtx);
  // Re-acquiring a just-released lock must succeed.
  srn_fiber_mutex_lock(&test_mtx);
  srn_fiber_mutex_unlock(&test_mtx);
  test_mtx_uncontended_ran = true;
  return nullptr;
}
 
static void test_mutex_uncontended() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
  srn_scheduler_t *sched = engine->scheduler;
  ASSERT_NOT_NULL(sched);
 
  srn_fiber_mutex_init(&test_mtx);
 
  (void)srn_fiber_spawn(ctx, test_mtx_uncontended_entry, nullptr);
  srn_sched_run(sched, 1);
 
  TEST_CHECK(test_mtx_uncontended_ran);
  // The lock is released once the fiber is done.
  TEST_CHECK(test_mtx_state() == nullptr);
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}
 
// TL;DR: Holding a lock and yielding, is safe and protects the critical path.
// N fibers on one worker each read a shared counter, yield while holding the lock, then write the
// incremented value back. The yield inside the critical section is the trap, it hands the worker to
// another fiber mid-update. Without the lock that peer would read the same stale value and an
// update would be lost, leaving the total below N. The lock forces the peer to suspend at its own
// lock() until the holder unlocks, so every increment lands.
#define MTX_MUTEX_N 8
static int test_mtx_me_counter;
 
static srn_fiber_result_t test_mtx_me_entry(srn_context_t *ctx, void *arg) {
  UNUSED(ctx);
  UNUSED(arg);
  srn_fiber_mutex_lock(&test_mtx);
  int seen = test_mtx_me_counter;
  // Yield the execution and let other fibers run
  srn_fiber_yield();
  test_mtx_me_counter = seen + 1;
  srn_fiber_mutex_unlock(&test_mtx);
  return nullptr;
}
 
static void test_mutex_mutual_exclusion() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
  srn_scheduler_t *sched = engine->scheduler;
  ASSERT_NOT_NULL(sched);
 
  srn_fiber_mutex_init(&test_mtx);
  test_mtx_me_counter = 0;
 
  for (int i = 0; i < MTX_MUTEX_N; i++) {
    UNUSED(srn_fiber_spawn(ctx, test_mtx_me_entry, nullptr));
  }
  srn_sched_run(sched, 4);
 
  // No update was lost despite each holder yielding in the middle of the criticalsection.
  TEST_CHECK(test_mtx_me_counter == MTX_MUTEX_N);
  TEST_CHECK(test_mtx_state() == nullptr);
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}
 
// Waiters are served oldest first. On one worker a holder takes the lock, then yields once. Then
// Round robin runs the three waiters in arrival order and each blocks on lock(), so they queue as
// 1, 2, 3. When the holder unlocks, the reversal in unlock hands the lock back in that same
// order, so the recorded acquisition order is {1, 2, 3}. A LIFO stack would record {3, 2, 1}.
#define MTX_FIFO_N 3
static int test_mtx_fifo_order[MTX_FIFO_N];
static int test_mtx_fifo_n;
 
static srn_fiber_result_t test_mtx_fifo_waiter_entry(srn_context_t *ctx, void *arg) {
  UNUSED(ctx);
  int id = (int)(intptr_t)arg;
  srn_fiber_mutex_lock(&test_mtx);
  test_mtx_fifo_order[test_mtx_fifo_n++] = id;
  srn_fiber_mutex_unlock(&test_mtx);
  return nullptr;
}
 
static srn_fiber_result_t test_mtx_fifo_holder_entry(srn_context_t *ctx, void *arg) {
  UNUSED(ctx);
  UNUSED(arg);
  srn_fiber_mutex_lock(&test_mtx);
  // One yield is enough: the single worker runs all three waiters (each parking
  // on lock) before this holder is scheduled again.
  srn_fiber_yield();
  srn_fiber_mutex_unlock(&test_mtx);
  return nullptr;
}
 
static void test_mutex_fifo_order() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
  srn_scheduler_t *sched = engine->scheduler;
  ASSERT_NOT_NULL(sched);
 
  srn_fiber_mutex_init(&test_mtx);
  test_mtx_fifo_n = 0;
 
  // Holder first so it owns the lock before any waiter runs, then the waiters
  // in the order whose service order we assert.
  (void)srn_fiber_spawn(ctx, test_mtx_fifo_holder_entry, nullptr);
  for (int i = 0; i < MTX_FIFO_N; i++) {
    (void)srn_fiber_spawn(ctx, test_mtx_fifo_waiter_entry, (void *)(intptr_t)(i + 1));
  }
  srn_sched_run(sched, 1);
 
  TEST_CHECK(test_mtx_fifo_n == MTX_FIFO_N);
  for (int i = 0; i < MTX_FIFO_N; i++) {
    TEST_CHECK(test_mtx_fifo_order[i] == i + 1);
    TEST_MSG(
      "order: %d %d %d", test_mtx_fifo_order[0], test_mtx_fifo_order[1], test_mtx_fifo_order[2]
    );
  }
  TEST_CHECK(test_mtx_state() == nullptr);
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}
 
// Real parallelism. Many fibers across several worker threads each hammer the lock, doing a plain
// (nonatomic) read, modify, write of a shared counter inside the critical section. The count is
// only exact if the lock both excludes concurrent holders and publishes the previous holder's write
// to the next one. Any missed exclusion or ordering shows up as a total. It is also the case TSan
// watches for a data race on the plain counter.
#define MTX_MT_N     64
#define MTX_MT_ITERS 100
static long test_mtx_mt_counter;
 
static srn_fiber_result_t test_mtx_mt_entry(srn_context_t *ctx, void *arg) {
  UNUSED(ctx);
  UNUSED(arg);
  for (int i = 0; i < MTX_MT_ITERS; i++) {
    srn_fiber_mutex_lock(&test_mtx);
    // plain RMW, guarded solely by the lock
    test_mtx_mt_counter++;
    srn_fiber_mutex_unlock(&test_mtx);
  }
  return nullptr;
}
 
static void test_mutex_mt_contention() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
  srn_scheduler_t *sched = engine->scheduler;
  ASSERT_NOT_NULL(sched);
 
  srn_fiber_mutex_init(&test_mtx);
  test_mtx_mt_counter = 0;
 
  for (int i = 0; i < MTX_MT_N; i++) {
    (void)srn_fiber_spawn(ctx, test_mtx_mt_entry, nullptr);
  }
  srn_sched_run(sched, 4);
 
  TEST_CHECK(test_mtx_mt_counter == (long)MTX_MT_N * MTX_MT_ITERS);
  TEST_CHECK(test_mtx_state() == nullptr);
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}