cactus.h

/*
 * cactus — work-stealing parallel recursion (public API)
 *
 * Copyright (c) 2019-2026 Praveen Vaddadi <thynktank@gmail.com>
 * SPDX-License-Identifier: Apache-2.0
 */

#ifndef CACTUS_H
#define CACTUS_H

#define _GNU_SOURCE
#include <unistd.h>
#include <stdlib.h>
#include <pthread.h>
#include <stdio.h>
#include <stddef.h>
#include <sys/mman.h>
#include <stdint.h>
#include <signal.h>

/* ────────────────────────────────────────────────────────────
 *  Public API
 * ──────────────────────────────────────────────────────────── */

typedef struct _cc_frame {
  uint32_t pending;       /* outstanding children             */
  uint32_t steals;        /* theft counter                    */
  int      parked;        /* 0 live · 1 parked · -1 waking   */
  void    *fp;            /* saved frame pointer              */
  void    *sp;            /* saved stack pointer              */
  void    *slab;          /* owning stack slab                */
  void    *ip;            /* resume address                   */
} cactus_t;

#if defined(__clang__)
#define cactus __attribute__((noinline, disable_tail_calls))
#else
#define cactus __attribute__((optimize("no-omit-frame-pointer")))
#endif

extern int cactus_start(int nprocs);
extern int cactus_stop(void);
extern int cactus_workers(void);

/*  cactus_init(&fr)                          prepare a frame
 *  cactus_fork(&fr, fn, (a,b))              void fork
 *  cactus_fork(&fr, &ret, fn, (a,b))        fork with return
 *  cactus_join(&fr)                          synchronize          */

/* ── convenience macros ─────────────────────────────────── */

/*  Usage:
 *
 *    cactus int fib(int n) {
 *        if (n < 2) return n;
 *        int x, y;
 *        BEGIN();
 *        FORK(&x, fib, (n - 1));
 *        y = fib(n - 2);
 *        JOIN();
 *        END();
 *        return x + y;
 *    }
 */
#define BEGIN()              cactus_t _fr; cactus_init(&_fr)
#define FORK(...)            cactus_fork(&_fr, __VA_ARGS__)
#define JOIN()               cactus_join(&_fr)
#define END()                ((void)0)

/* ────────────────────────────────────────────────────────────
 *  Implementation details — do not use directly
 * ──────────────────────────────────────────────────────────── */

/* work queue (per-worker deque) */

extern __thread struct _cc_ring {
  uint64_t lo;
  uint64_t hi;
  void    *slab;
  void    *ring[1024];
} cc_wq;

/* atomic helpers */

#define cc_ld(v)               __atomic_load_n(&(v), __ATOMIC_ACQUIRE)
#define cc_st(v,n)             __atomic_store_n(&(v), n, __ATOMIC_RELEASE)
#define cc_xadd(v,n)           __atomic_fetch_add(&(v), n, __ATOMIC_ACQ_REL)
#define cc_xsub(v,n)           __atomic_fetch_sub(&(v), n, __ATOMIC_ACQ_REL)
#define cc_addf(v,n)           __atomic_add_fetch(&(v), n, __ATOMIC_ACQ_REL)
#define cc_subf(v,n)           __atomic_sub_fetch(&(v), n, __ATOMIC_ACQ_REL)
#define cc_xchg(v,n)           __atomic_exchange_n(&(v), n, __ATOMIC_ACQ_REL)
#define cc_cas(p,c,v)          __atomic_compare_exchange_n(&(p),&(c),v,0,__ATOMIC_ACQ_REL,__ATOMIC_ACQUIRE)
#define cc_ld_m(v,m)           __atomic_load_n(&(v), m)
#define cc_st_m(v,n,m)         __atomic_store_n(&(v), n, m)
#define cc_xadd_m(v,n,m)       __atomic_fetch_add(&(v), n, m)
#define cc_xsub_m(v,n,m)       __atomic_fetch_sub(&(v), n, m)
#define cc_addf_m(v,n,m)       __atomic_add_fetch(&(v), n, m)
#define cc_subf_m(v,n,m)       __atomic_sub_fetch(&(v), n, m)
#define cc_xchg_m(v,n,m)       __atomic_exchange_n(&(v), n, m)
#define cc_cas_m(p,c,v,s,f)    __atomic_compare_exchange_n(&(p),&(c),v,0,s,f)

/* internal entry points (defined in tie.c) */

__attribute__((noinline))  extern void cc_wait(cactus_t *);
__attribute__((noreturn))  extern void cc_park(cactus_t *, uint32_t);

#if defined(__clang__)

__attribute__((noinline))  extern void cc_await(cactus_t *, void *);

#define cc_flush() __asm__ volatile ("" : : : \
    "rax","rbx","rcx","rdx","rsi","rdi", \
    "r8","r9","r10","r11","r12","r13","r14","r15","memory","cc")

enum { CC_VOID = 0, CC_GP = 1, CC_FP = 2 };

typedef struct _cc_task {
  void (*target)(void);
  void    *dest;
  uint8_t  kind, size, ngp, nsse, nstk, _pad[3];
  uint64_t gp[6];
  uint64_t sse[8];
  uint64_t ovf[16];
} cc_task_t;

__attribute__((noinline)) extern
void cc_spawn(cactus_t *, const cc_task_t *, void *);

__attribute__((always_inline)) static inline
void cc_arg_gp(cc_task_t *t, uint64_t v)
{ if (t->ngp < 6) t->gp[t->ngp++] = v; else t->ovf[t->nstk++] = v; }

__attribute__((always_inline)) static inline
void cc_arg_fp(cc_task_t *t, uint64_t v)
{ if (t->nsse < 8) t->sse[t->nsse++] = v; else t->ovf[t->nstk++] = v; }

#define cc_is_real(T) \
    (__builtin_types_compatible_p(T,float)||__builtin_types_compatible_p(T,double))

#define cc_arg(t,a) do { \
    union { __typeof__(a) v; uint64_t r; } _u={0}; _u.v=(a); \
    if (cc_is_real(__typeof__(a))) cc_arg_fp(&(t),_u.r); \
    else                           cc_arg_gp(&(t),_u.r); } while(0)

#define cc_task_void(t,fn) do { \
    (t).target=(void(*)(void))(fn); (t).dest=NULL; \
    (t).kind=CC_VOID; (t).size=0; } while(0)

#define cc_task_ret(t,rp,fn) do { \
    (t).target=(void(*)(void))(fn); (t).dest=(void*)(rp); \
    (t).kind=cc_is_real(__typeof__(*(rp)))?CC_FP:CC_GP; \
    (t).size=sizeof(*(rp)); } while(0)

#define CC_S(x)  #x
#define CC_XS(x) CC_S(x)
#define CC_OFF_FN    0
#define CC_OFF_NSTK  20
#define CC_OFF_GP    24
#define CC_OFF_SSE   72
#define CC_OFF_OVF   136

#endif /* __clang__ */

/* deque operations */

#if defined(__clang__)
__attribute__((noinline)) static
void cc_post_(cactus_t *f, void *resume)
{
  f->ip = resume;
  uint64_t h = cc_ld_m(cc_wq.hi, __ATOMIC_ACQUIRE);
  cc_wq.ring[h % 1024] = f;
  cc_st_m(cc_wq.hi, h + 1, __ATOMIC_RELEASE);
}
#define cc_post_at(f,r)  cc_post_((f),(r))
#else
#define cc_post_at(f,_r) do { \
    (f)->ip = (_r); \
    uint64_t _h = cc_ld_m(cc_wq.hi, __ATOMIC_ACQUIRE); \
    cc_wq.ring[_h % 1024] = (f); \
    cc_st_m(cc_wq.hi, _h + 1, __ATOMIC_RELEASE); \
  } while(0)
#endif

#define cc_post(f) cc_post_at((f), __builtin_return_address(0))

#if defined(__clang__)
__attribute__((noinline)) static
#else
__attribute__((hot)) static
#endif
int cc_claim(void)
{
  uint64_t h = __atomic_sub_fetch(&(cc_wq.hi), 1, 4);
  uint64_t l = __atomic_load_n(&(cc_wq.lo), 2);
  if (h > l) return 1;
  if (l > h) { __atomic_store_n(&(cc_wq.hi), l, 0); return 0; }
  int ok = __atomic_compare_exchange_n(&(cc_wq.lo), &(l), l+1, 0, 4, 0);
  __atomic_store_n(&(cc_wq.hi), h + 1, 0);
  return ok;
}

#define cc_settle(call) do { \
    call; __asm__("nop":::"rbx","r12","r13","r14","r15","memory"); } while(0)

/* cactus_init */

__attribute__((always_inline)) static inline
void cactus_init(cactus_t *f)
{
  void *rbp, *rsp;
  __asm__ volatile("mov\t%%rbp,%0\n\tmov\t%%rsp,%1"
                   :"=r"(rbp),"=r"(rsp)::"memory");
#if !defined(__clang__)
  /* Force RBP-relative locals — prevents RSP-relative addressing that
     breaks when a continuation is stolen to a fresh stack at -O3 -mavx2 */
  volatile size_t _n = 16;
  void * volatile _a = __builtin_alloca(_n);
  *(volatile char *)_a = 0;
#endif
  f->pending = 0;
  f->steals  = 0;
  f->parked  = 0;
  f->fp      = rbp;
  f->sp      = rsp;
  f->slab    = cc_wq.slab;
}

/* cactus_join */

#if defined(__clang__)
#define cc_jl(id) cc_cat(cc_jl_, id)
#define cc_join_impl(id,f) do { \
    if (cc_ld_m((f)->steals, __ATOMIC_ACQUIRE) > 0) { \
      __label__ cc_jl(id); \
      cc_await((f), &&cc_jl(id)); \
      cc_jl(id): cc_flush(); \
      cc_st_m((f)->steals, 0, __ATOMIC_RELEASE); \
      (f)->parked = 0; \
    } } while(0)
#define cactus_join(f) cc_join_impl(__COUNTER__, (f))
#else
__attribute__((always_inline)) static inline
void cactus_join(cactus_t *f)
{
  if (cc_ld_m(f->steals, __ATOMIC_ACQUIRE) > 0) {
    do { cc_wait(f);
         __asm__("nop":::"rbx","r12","r13","r14","r15","memory");
    } while(0);
    cc_st_m(f->steals, 0, __ATOMIC_RELEASE);
    f->parked = 0;
  }
}
#endif

/* fork — variadic argument machinery */

#define cc_cat(a,b) a##b
#define cc_nth(...) cc_nth_(__VA_ARGS__,##__VA_ARGS__, \
    16,16,15,15,14,14,13,13,12,12,11,11,10,10,9,9, \
    8,8,7,7,6,6,5,5,4,4,3,3,2,2,1,0)
#define cc_nth_( \
    _1,_1_,_2,_2_,_3,_3_,_4,_4_,_5,_5_,_6,_6_,_7,_7_,_8,_8_, \
    _9,_9_,_10,_10_,_11,_11_,_12,_12_,_13,_13_,_14,_14_, \
    _15,_15_,_16,_16_,N,...) N
#define cc_unwrap(...) __VA_ARGS__

/* type declarations for nested-function params */
#define cc_types(...)       cc_types_(cc_nth(__VA_ARGS__),##__VA_ARGS__)
#define cc_types_(n,...)    cc_cat(cc_types_,n)(__VA_ARGS__)
#define cc_types_0()
#define cc_types_1(a)       __typeof__(a) a1,
#define cc_types_2(a,...)   __typeof__(a) a2, cc_types_1(__VA_ARGS__)
#define cc_types_3(a,...)   __typeof__(a) a3, cc_types_2(__VA_ARGS__)
#define cc_types_4(a,...)   __typeof__(a) a4, cc_types_3(__VA_ARGS__)
#define cc_types_5(a,...)   __typeof__(a) a5, cc_types_4(__VA_ARGS__)
#define cc_types_6(a,...)   __typeof__(a) a6, cc_types_5(__VA_ARGS__)
#define cc_types_7(a,...)   __typeof__(a) a7, cc_types_6(__VA_ARGS__)
#define cc_types_8(a,...)   __typeof__(a) a8, cc_types_7(__VA_ARGS__)
#define cc_types_9(a,...)   __typeof__(a) a9, cc_types_8(__VA_ARGS__)
#define cc_types_10(a,...)  __typeof__(a) a10,cc_types_9(__VA_ARGS__)
#define cc_types_11(a,...)  __typeof__(a) a11,cc_types_10(__VA_ARGS__)
#define cc_types_12(a,...)  __typeof__(a) a12,cc_types_11(__VA_ARGS__)
#define cc_types_13(a,...)  __typeof__(a) a13,cc_types_12(__VA_ARGS__)
#define cc_types_14(a,...)  __typeof__(a) a14,cc_types_13(__VA_ARGS__)
#define cc_types_15(a,...)  __typeof__(a) a15,cc_types_14(__VA_ARGS__)
#define cc_types_16(a,...)  __typeof__(a) a16,cc_types_15(__VA_ARGS__)

/* param name forwarding */
#define cc_names(...)       cc_names_(cc_nth(__VA_ARGS__),##__VA_ARGS__)
#define cc_names_(n,...)    cc_cat(cc_names_,n)(__VA_ARGS__)
#define cc_names_0()
#define cc_names_1(a)       a1
#define cc_names_2(a,...)   a2, cc_names_1(__VA_ARGS__)
#define cc_names_3(a,...)   a3, cc_names_2(__VA_ARGS__)
#define cc_names_4(a,...)   a4, cc_names_3(__VA_ARGS__)
#define cc_names_5(a,...)   a5, cc_names_4(__VA_ARGS__)
#define cc_names_6(a,...)   a6, cc_names_5(__VA_ARGS__)
#define cc_names_7(a,...)   a7, cc_names_6(__VA_ARGS__)
#define cc_names_8(a,...)   a8, cc_names_7(__VA_ARGS__)
#define cc_names_9(a,...)   a9, cc_names_8(__VA_ARGS__)
#define cc_names_10(a,...)  a10,cc_names_9(__VA_ARGS__)
#define cc_names_11(a,...)  a11,cc_names_10(__VA_ARGS__)
#define cc_names_12(a,...)  a12,cc_names_11(__VA_ARGS__)
#define cc_names_13(a,...)  a13,cc_names_12(__VA_ARGS__)
#define cc_names_14(a,...)  a14,cc_names_13(__VA_ARGS__)
#define cc_names_15(a,...)  a15,cc_names_14(__VA_ARGS__)
#define cc_names_16(a,...)  a16,cc_names_15(__VA_ARGS__)

/* passthrough with trailing comma */
#define cc_pass(...)        cc_pass_(cc_nth(__VA_ARGS__),##__VA_ARGS__)
#define cc_pass_(n,...)     cc_cat(cc_pass_,n)(__VA_ARGS__)
#define cc_pass_0()
#define cc_pass_1(...)  __VA_ARGS__,
#define cc_pass_2(...)  __VA_ARGS__,
#define cc_pass_3(...)  __VA_ARGS__,
#define cc_pass_4(...)  __VA_ARGS__,
#define cc_pass_5(...)  __VA_ARGS__,
#define cc_pass_6(...)  __VA_ARGS__,
#define cc_pass_7(...)  __VA_ARGS__,
#define cc_pass_8(...)  __VA_ARGS__,
#define cc_pass_9(...)  __VA_ARGS__,
#define cc_pass_10(...) __VA_ARGS__,
#define cc_pass_11(...) __VA_ARGS__,
#define cc_pass_12(...) __VA_ARGS__,
#define cc_pass_13(...) __VA_ARGS__,
#define cc_pass_14(...) __VA_ARGS__,
#define cc_pass_15(...) __VA_ARGS__,
#define cc_pass_16(...) __VA_ARGS__,

/* clang arg-packing chain */
#if defined(__clang__)
#define cc_pack(c,...)      cc_pack_(cc_nth(__VA_ARGS__),c,##__VA_ARGS__)
#define cc_pack_(n,...)     cc_cat(cc_pack_,n)(__VA_ARGS__)
#define cc_pack_0(c)
#define cc_pack_1(c,a)      cc_arg(c,a)
#define cc_pack_2(c,a,...)  cc_arg(c,a); cc_pack_1(c,__VA_ARGS__)
#define cc_pack_3(c,a,...)  cc_arg(c,a); cc_pack_2(c,__VA_ARGS__)
#define cc_pack_4(c,a,...)  cc_arg(c,a); cc_pack_3(c,__VA_ARGS__)
#define cc_pack_5(c,a,...)  cc_arg(c,a); cc_pack_4(c,__VA_ARGS__)
#define cc_pack_6(c,a,...)  cc_arg(c,a); cc_pack_5(c,__VA_ARGS__)
#define cc_pack_7(c,a,...)  cc_arg(c,a); cc_pack_6(c,__VA_ARGS__)
#define cc_pack_8(c,a,...)  cc_arg(c,a); cc_pack_7(c,__VA_ARGS__)
#define cc_pack_9(c,a,...)  cc_arg(c,a); cc_pack_8(c,__VA_ARGS__)
#define cc_pack_10(c,a,...) cc_arg(c,a); cc_pack_9(c,__VA_ARGS__)
#define cc_pack_11(c,a,...) cc_arg(c,a); cc_pack_10(c,__VA_ARGS__)
#define cc_pack_12(c,a,...) cc_arg(c,a); cc_pack_11(c,__VA_ARGS__)
#define cc_pack_13(c,a,...) cc_arg(c,a); cc_pack_12(c,__VA_ARGS__)
#define cc_pack_14(c,a,...) cc_arg(c,a); cc_pack_13(c,__VA_ARGS__)
#define cc_pack_15(c,a,...) cc_arg(c,a); cc_pack_14(c,__VA_ARGS__)
#define cc_pack_16(c,a,...) cc_arg(c,a); cc_pack_15(c,__VA_ARGS__)
#endif

/* fork dispatch */

#if defined(__clang__)

#define cc_rl(id) cc_cat(cc_r_, id)

#define cc_go_void_(id,fp,fn,ag) do { \
    __label__ cc_rl(id); cc_task_t _t={0}; \
    cc_task_void(_t,(fn)); cc_pack(_t,cc_unwrap ag); \
    cc_spawn((fp),&_t,&&cc_rl(id)); \
    cc_rl(id): cc_flush(); } while(0)

#define cc_go_ret_(id,fp,rp,fn,ag) do { \
    __label__ cc_rl(id); cc_task_t _t={0}; \
    cc_task_ret(_t,(rp),(fn)); cc_pack(_t,cc_unwrap ag); \
    cc_spawn((fp),&_t,&&cc_rl(id)); \
    cc_rl(id): cc_flush(); } while(0)

#define cc_go_void(fp,fn,ag) cc_go_void_(__COUNTER__,fp,fn,ag)
#define cc_go_ret(fp,rp,fn,ag) cc_go_ret_(__COUNTER__,fp,rp,fn,ag)

#else /* GCC */

#define cc_go_void(fp,fn,ag) do { \
    __attribute__((noinline,hot,optimize(3))) \
    void cc_##fn##_go(cc_types ag cactus_t *_f) { \
      cc_post(_f); fn(cc_names ag); \
      if (!cc_claim()) cc_park(_f,1); } \
    cc_settle(cc_##fn##_go(cc_pass ag fp)); } while(0)

#define cc_go_ret(fp,rp,fn,ag) do { \
    __attribute__((noinline,hot,optimize(3))) \
    void cc_##fn##_go(cc_types ag cactus_t *_f, __typeof__(rp) _p) { \
      cc_post(_f); *_p = fn(cc_names ag); \
      if (!cc_claim()) cc_park(_f,1); } \
    cc_settle(cc_##fn##_go(cc_pass ag fp, rp)); } while(0)

#endif

#define cactus_fork(...)     cc_route(cc_nth(__VA_ARGS__), __VA_ARGS__)
#define cc_route(n,...)   cc_cat(cc_fork_,n)(__VA_ARGS__)
#define cc_fork_3(...)    cc_go_void(__VA_ARGS__)
#define cc_fork_4(...)    cc_go_ret(__VA_ARGS__)

#endif /* CACTUS_H */