fiber.h

Go to the documentation of this file.

/* -*- C -*-
 * Serene programming language
 * Copyright (C) 2019-2026 Sameer Rahmani <[email protected]>
 *
 * 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/>.
 */
 
/** @file
 AI Generated (🤦)
 Fiber subsystem overview
 
 Stackful, cooperative fibers for the runtime. A fiber is a function plus its
 own stack, so it can pause at any call depth and resume later. Nothing is
 preempted. A fiber runs until it explicitly yields, suspends, or finishes.
 
 Terminology (used throughout the fiber subsystem)
   fiber           a unit of work with its own stack. It can pause and resume.
   os thread       a thread the operating system schedules.
   worker          the state one os thread uses to run fibers. It holds a local
                   queue of ready fibers and a worker's loop. There is one
                   worker per os thread.
   worker's loop   a special fiber that stands in for the os thread. A running
                   fiber switches back to it to hand control over, and it picks
                   the next fiber to run.
   worker routine  the steps an os thread repeats. It takes a fiber, switches
                   into it, deals with how the fiber gave up control, and parks
                   when no fiber is runnable.
   scheduler       there is exactly one. It owns the shared ready queue and the
                   list of live fibers and decides what runs next. It does not
                   run fibers itself, workers do.
   suspend         a fiber steps off every queue and waits to be woken. Its os
                   thread stays free to run other fibers.
   park            an os thread blocks because no fiber is runnable anywhere. A
                   notify wakes it.
 
 Every fiber stack is the same fixed size (SRN_FIBER_DEFAULT_STACK_SIZE), one
 mapping with a guard page that never grows. Uniform size is a deliberate
 constraint, not an accident. It lets a finished fiber's stack be handed to any
 later fiber (the stack ring TODO below) without tracking size classes, and it
 keeps switch and mapping costs predictable.
 
 Control flow is a hub. A fiber never jumps to another fiber. It switches back
 to its worker's loop, which picks the next one.
 
     scheduler ready queue:  [F2] -> [F5] -> ...
                                |  the os thread takes the head
                                v
        +----------->  worker's loop  --- switch --->  running fiber
        |                                                  |
        |  yield    (re-enqueue, run next) ----------------+
        |  suspend  (off-queue until srn_fiber_ready) -----+
        |  finish   (reap) --------------------------------+
        +--------------------------------------------------+
 
 A running fiber gives up control three ways:
   - yield    still runnable, so it moves to the back of the ready queue.
   - suspend  off every queue until some party calls srn_fiber_ready. The wake
              seam used by peer fibers, locks, and a future IO reactor.
   - finish   its entry returns and the fiber is reaped.
 
 The spec book's fibers chapter (docs/spec/fibers.typ) is the long-form
 reference. Keep this overview in step with it.
*/
 
#pragma once
 
#include <stddef.h>
#include <stdint.h>
 
// Sanitizer detection. AddressSanitizer and ThreadSanitizer each need a little
// per-fiber bookkeeping (the guarded fields below and the switch path in
// fiber.c), and a normal build carries none of it. Every translation unit in a
// build compiles with the same `-fsanitize` flags, so the struct layout stays
// consistent within that build.
#if defined(__SANITIZE_ADDRESS__)
#  define SRN_ASAN 1
#elif defined(__has_feature)
#  if __has_feature(address_sanitizer)
#    define SRN_ASAN 1
#  endif
#endif
#ifndef SRN_ASAN
#  define SRN_ASAN 0
#endif
 
#if defined(__SANITIZE_THREAD__)
#  define SRN_TSAN 1
#elif defined(__has_feature)
#  if __has_feature(thread_sanitizer)
#    define SRN_TSAN 1
#  endif
#endif
#ifndef SRN_TSAN
#  define SRN_TSAN 0
#endif
 
typedef struct srn_engine_t srn_engine_t;
typedef struct srn_context_t srn_context_t;
typedef struct srn_fiber_t srn_fiber_t;
typedef struct srn_scheduler_t srn_scheduler_t;
 
// What a fiber's entry produces, type-erased. It is an alias for `void *`, so
// the fiber subsystem carries no dependency on the value model. A caller that
// runs fibers over Serene values casts to and from its own type at the
// boundary.
typedef void *srn_fiber_result_t;
 
#define srn_fiber_get_scheduler_m(fiber) fiber->ctx->engine->scheduler
 
// TODO(lxsameer): We need to have a ring with a certain size, which
// would be like a storage for ready to use stacks. When we're done with a fiber
// put its stack in the ring and prepare it for another upcoming fiber.
// it might be even a good idea to allocate a few stacks in advance on start
// up. This ring should be per thread I think.
 
/// Default size of every fiber stack. All fiber stacks share one size (see the
/// subsystem overview), so this is a process-wide value, not a per-fiber one:
/// the default here, eventually overridable through a CLI argument.
///
/// A fiber stack is fixed and cannot grow (see the fibers chapter), so the size
/// must hold realistic call chains yet stay cheap to reserve in bulk. 128 KiB
/// strikes that balance: deep enough for the runtime's C and JIT frames, while
/// lazy page commit means a shallow fiber faults in only the one or two pages
/// it touches and leaves the rest a virtual reservation. For scale, an OS
/// thread stack is far too large to spawn fibers by the thousand, and a few KiB
/// would overflow on modest nesting.
#define SRN_FIBER_DEFAULT_STACK_SIZE (128U * 1024U)
 
// -----------------------------------------------------------------------------
// Saved machine context
// -----------------------------------------------------------------------------
/// The saved context of a suspended fiber is a single word: its stack pointer
/// at the moment it was switched away from. The callee-saved registers live on
/// the fiber's own stack, pushed by srn_fiber_swap and popped when it is
/// resumed.
typedef struct srn_fiber_ctx_t {
  void *sp;
} srn_fiber_ctx_t;
 
// -----------------------------------------------------------------------------
// Stack
// -----------------------------------------------------------------------------
/// One stack per fiber, mapped with a guard page at the low end so an overflow
/// faults deterministically instead of corrupting a neighbour.
/// the layout is like:
/////
/// |... frames ...|... guard page ...|
/// ^ start        ^ limit            ^ guard
///
/// It is a bit unintuitive to see the guard pointing at the end of the the
/// region, but conventionally, the guard is an OS page and since the stack
/// grows downward and allocations normally grow upward, guard is actually
/// the address that OS (POSIX in this example) will return to us as the
/// starting point of the memory region. Or to put it in different terms, we
/// store the stack frames, starting from the end of the allocated memory for
/// the region and move toward the start of the allocated memory.
typedef struct srn_fiber_stack_t {
  /// High end, stack pointer initialises to this address
  void *start;
  /// Low end of usable region
  void *limit;
  /// The protected page to detect stack overflows
  void *guard;
} srn_fiber_stack_t;
 
// -----------------------------------------------------------------------------
// Lifecycle
// -----------------------------------------------------------------------------
typedef enum srn_fiber_state_e : uint8_t {
  /// Created, stack mapped, never resumed
  SRN_FIBER_NEW = 0,
  /// On the run queue, eligible to run
  SRN_FIBER_READY,
  /// Currently executing
  SRN_FIBER_RUNNING,
  /// Parked off the run queue, awaits srn_fiber_ready
  SRN_FIBER_SUSPENDED,
  /// Entry returned. The result is final
  SRN_FIBER_DONE,
} srn_fiber_state_t;
 
/// The function a fiber runs. Allocations made through `ctx` land in the
/// context's block.
/// TODO(lxsameer): The shape is generic until code generation produces
/// fibers, at which point it adopts the Serene ABI.
/// TODO(lxsameer): Should we support two types of entry functions? one
/// for C calling convention and one for FastC?
typedef srn_fiber_result_t (*srn_fiber_entry_t)(srn_context_t *ctx, void *arg);
 
/// Suspend commit callback. The worker routine runs it on its own side once the
/// fiber has switched out. It registers `self` with whatever will wake it and
/// re-checks the awaited condition. It returns true to stay suspended, or false
/// to resume `self` at once because the condition already holds. It must not
/// switch fibers.
typedef bool (*srn_fiber_park_fn)(srn_fiber_t *self, void *arg);
 
struct srn_fiber_t {
  /// Saved stack pointer (see srn_fiber_ctx_t)
  srn_fiber_ctx_t fiber_ctx;
  srn_fiber_stack_t stack;
  /// The lifecycle state. Atomic because a waker may run on a different os
  /// thread than the worker running the fiber. `srn_fiber_ready` flips
  /// `SUSPENDED` to `READY` with a CAS while the worker running the fiber reads
  /// and writes the same field. Making it atomic keeps every access whole, so a
  /// read can never see an inconsistent value.
  _Atomic srn_fiber_state_t state;
  srn_context_t *ctx;
  srn_fiber_entry_t entry;
  void *arg;
  /// Set when state reaches SRN_FIBER_DONE. Type-erased (see
  /// srn_fiber_result_t), the caller interprets it.
  srn_fiber_result_t result;
 
  /// While this fiber is suspending, the commit the worker routine runs once
  /// the fiber is off the stack, to publish it to its waker (see
  /// srn_fiber_suspend). Valid only across that one suspend hand-off.
  srn_fiber_park_fn park_commit;
  void *park_arg;
 
#if SRN_ASAN
  /// AddressSanitizer bookkeeping across switches.
  void *fake_stack;
#endif
 
#if SRN_TSAN
  /// ThreadSanitizer fiber handle. TSan tracks each fiber as its own execution
  /// context, so the switch path tells it which one is current. Created with
  /// the fiber and destroyed when it is reaped.
  void *tsan_fiber;
#endif
 
  /// Intrusive link threading this fiber onto one of the scheduler's
  /// singly-linked lists (the ready run queue, or a wait queue) without a
  /// separate node allocation: the next pointer lives in the fiber itself. A
  /// fiber belongs to at most one such list at a time, so one link suffices.
  srn_fiber_t *link;
 
  /// Head of the list of fibers blocked in srn_fiber_wait_for on this fiber.
  /// They are threaded through their own `link` (a waiter is suspended, so off
  /// the ready queue, and its `link` is free). When this fiber reaches DONE the
  /// worker routine wakes them all.
  srn_fiber_t *waiters;
 
  /// Registry links.
  ///
  /// The scheduler keeps every live fiber on one doubly linked list through
  /// these pointers. It is different from `link`. `link` says where a fiber
  /// sits in the run order, the registry says the fiber exists at all. A fiber
  /// joins the list when it is created and leaves when it is reaped, in
  /// whatever state it is in between -- including SUSPENDED, which sits on no
  /// queue.
  ///
  /// This is how the scheduler accounts for, cleans up, and (later) cancels its
  /// fibers. Doubly linked so reaping can unlink from the middle in O(1).
  srn_fiber_t *reg_prev;
  srn_fiber_t *reg_next;
 
  /// For debugging purposes
  const char *name;
};
 
// -----------------------------------------------------------------------------
// Scheduler
// -----------------------------------------------------------------------------
[[nodiscard]] [[gnu::nonnull(1)]] srn_scheduler_t *
srn_sched_init(srn_engine_t *engine);
 
/// The one stop tear down of the fiber subsystem, should be called once
/// `srn_sched_run` has returned. It joins the os threads, then releases the
/// stack of every fiber still registered (any left unreaped, such as one
/// suspended with no party to wake it, or one left queued when the run stopped
/// early), and frees the scheduler's own resources. The fiber structs
/// themselves live in context blocks and are reclaimed with those blocks, not
/// here.
///
/// The scheduler is NOT usable after this. A later `srn_sched_run` panics, and
/// a repeated `srn_sched_shutdown` is a no-op (so the engine can call it
/// unconditionally even after a caller already did).
///
/// Must be called from outside the pool, never from an os thread that is
/// running a worker nor from a fiber, and only after `srn_sched_run` has
/// returned. Calling it on a live pool panics -- stop the pool with
/// `srn_sched_stop`, let `srn_sched_run` return, then shut down.
[[gnu::nonnull(1)]] void srn_sched_shutdown(srn_scheduler_t *sched);
 
/// Run the scheduler with `nworkers` os threads draining it, returning once the
/// pool goes quiescent (every os thread parked on an empty queue) or a stop is
/// requested with `srn_sched_stop`. The calling os thread becomes worker 0, so
/// it does not return until then. `nworkers` is clamped to at least 1; with 1
/// it is the calling os thread alone, which keeps execution single-threaded and
/// cooperatively ordered. The spawned os threads are not joined here --
/// `srn_sched_shutdown` joins them as part of tearing the subsystem down.
[[gnu::nonnull(1)]] void srn_sched_run(srn_scheduler_t *sched, int nworkers);
 
/// Ask a running scheduler to stop. Each worker routine checks the request at
/// the top of each turn and stops once the fiber it is running yields or
/// finishes, so a slice in flight is never cut mid-execution. `srn_sched_run`
/// then returns. Fibers left queued stay unrun and are reclaimed by
/// `srn_sched_shutdown`. Does not wait. Safe to call from any os thread,
/// including a signal-driven context or a fiber. A no-op if the scheduler is
/// not running.
[[gnu::nonnull(1)]] void srn_sched_stop(srn_scheduler_t *sched);
 
/// Record a fiber in the scheduler's registry of live fibers, where it stays
/// until it is reaped.
[[gnu::nonnull(1, 2)]] void srn_sched_register(srn_scheduler_t *sched,
                                               srn_fiber_t *fiber);
 
/// Place a fiber on a scheduler's ready queue, making it eligible to run.
[[gnu::nonnull(1, 2)]] void srn_sched_enqueue(srn_scheduler_t *sched,
                                              srn_fiber_t *fiber);
 
// -----------------------------------------------------------------------------
// Fibers
// -----------------------------------------------------------------------------
/// Create a fiber that will run entry(ctx, arg). The fiber
/// allocates into its block and never releases it. A `stack_size` of 0 selects
/// SRN_FIBER_DEFAULT_STACK_SIZE.
[[nodiscard]] [[gnu::nonnull(1, 2, 3)]] srn_fiber_t *
srn_fiber_make(srn_context_t *ctx, srn_scheduler_t *sched,
               srn_fiber_entry_t entry, void *arg, size_t stack_size);
 
/// Yield cooperatively: re-enqueue the running fiber and run the next ready
/// one. Acts on the fiber currently running on this thread.
void srn_fiber_yield(void);
 
/// Park the running fiber until a party calls srn_fiber_ready. The fiber
/// switches out first. Only then does the scheduler run `commit` (see
/// srn_fiber_park_fn) to register it and confirm it should stay parked.
/// Registering only after the park completes is what makes it race free -- a
/// waker can never observe a half parked fiber. Acts on the fiber currently
/// running on this thread.
[[gnu::nonnull(1)]] void srn_fiber_suspend(srn_fiber_park_fn commit, void *arg);
 
/// Mark a suspended fiber runnable again. This is the seam an IO reactor,
/// timer, or peer fiber uses to wake a fiber when the event it awaited occurs.
[[gnu::nonnull(1)]] void srn_fiber_ready(srn_fiber_t *fiber);
 
/// Block the calling fiber until `target` finishes, then return its result.
[[gnu::nonnull(1)]] srn_fiber_result_t srn_fiber_wait_for(srn_fiber_t *target);
 
/// The fiber currently running on this os thread (the bootstrap fiber if none).
srn_fiber_t *srn_fiber_current(void);
 
/// The worker's loop of the worker running on the calling os thread. The fiber
/// that resumes when the current fiber yields, suspends, or finishes, the
/// resumer a fiber's launcher hands control back to. Each worker has its own,
/// so this is valid only on an os thread that is currently running the worker
/// routine.
[[gnu::returns_nonnull]] srn_fiber_t *srn_fiber_worker_loop(void);
 
// -----------------------------------------------------------------------------
// Context switch
// -----------------------------------------------------------------------------
/// Save the current execution context into `from`, restore `to`, and resume on
/// `to`'s stack. Returns, on `from`'s stack, when a fiber later switches back
/// into `from`.
[[gnu::nonnull(1, 2)]] void srn_fiber_swap(srn_fiber_ctx_t *from,
                                           srn_fiber_ctx_t *to);
 
/// Initialise a fresh fiber context so the first srn_fiber_swap into it begins
/// executing fn(arg) on `stack`.
///
/// `fn` is the fiber's entry: a `void (*)(void *)` that runs on the new stack
/// and receives `arg`. It must NEVER return -- there is no frame beneath it, so
/// a return traps in the trampoline. Instead it transfers control away with
/// srn_fiber_switch (to yield) or srn_fiber_switch_final (when finished), and
/// as its first action it calls srn_fiber_on_entry(). Typical shape:
///
///   static void worker(void *arg) {
///     srn_fiber_on_entry(&scheduler);        // hand the switch to the
///     sanitizer
///     ... do the fiber's work using arg ...
///     srn_fiber_switch_final(&scheduler);    // finished, never returns
///   }
[[gnu::nonnull(1, 3)]] void srn_fiber_ctx_make(srn_fiber_ctx_t *fiber_ctx,
                                               srn_fiber_stack_t stack,
                                               void (*fn)(void *), void *arg);
 
/// Switch from `from` to `to`, both live fibers, telling AddressSanitizer about
/// the stack change. `from` resumes where it left off when something later
/// switches back into it.
[[gnu::nonnull(1, 2)]] void srn_fiber_switch(srn_fiber_t *from,
                                             srn_fiber_t *to);
 
/// Like srn_fiber_switch, but for a fiber that has finished and must not be
/// resumed: control transfers to `to` and never comes back. The fiber's entry
/// function therefore ends at this call -- any code after it is unreachable,
/// which is why this is [[noreturn]]. Nothing is freed here. The spent fiber's
/// stack is left frozen and reclaimed later by its owner (the scheduler reaps a
/// finished fiber and frees its stack via srn_fiber_stack_free).
[[noreturn]] [[gnu::nonnull(1)]] void srn_fiber_switch_final(srn_fiber_t *to);
 
/// Call as the first action inside a fresh fiber's entry. `from` is the fiber
/// that started this one (the scheduler, or the bootstrap thread fiber). It
/// completes the switch for AddressSanitizer and, since `from`'s stack bounds
/// only become discoverable here, records them into `from` so a later switch
/// back is tracked. `from` may be null. A no-op when the sanitizer is not in
/// use.
void srn_fiber_on_entry(srn_fiber_t *from);
 
/// Call when a finished fiber is reaped, after it has switched away for the
/// last time. Releases the fiber's ThreadSanitizer handle. A no-op when the
/// sanitizer is not in use.
[[gnu::nonnull(1)]] void srn_fiber_on_reap(srn_fiber_t *fiber);
 
/// Represent the calling OS thread as the running fiber ("#0"), so the
/// scheduler or a test can switch away from it and back. The thread's stack
/// bounds are not queried here (there is no portable way). Under the sanitizer
/// they are recorded by the first fiber's srn_fiber_on_entry. The saved context
/// is written by the first switch away.
[[gnu::nonnull(1)]] void srn_fiber_init_thread(srn_fiber_t *f);
 
// -----------------------------------------------------------------------------
// Stack provider (rt/fiber/stack_*.c)
// -----------------------------------------------------------------------------
/// Allocate a stack of at least `size` usable bytes plus a guard page, or
/// SRN_FIBER_DEFAULT_STACK_SIZE when `size` is 0. Platform specific.
[[nodiscard]] srn_fiber_stack_t srn_fiber_stack_alloc(size_t size);
 
void srn_fiber_stack_free(srn_fiber_stack_t stack);
 
// -----------------------------------------------------------------------------
// Helpers
// -----------------------------------------------------------------------------
static inline size_t srn_fiber_stack_size(srn_fiber_stack_t s) {
  return (size_t)((char *)s.start - (char *)s.limit);
}