wip reorg

2 files changed, 528 insertions, 0 deletions

diff --git a/libcr/coroutine.c b/libcr/coroutine.c
new file mode 100644
index 0000000..12d4a25
--- /dev/null
+++ b/libcr/coroutine.c
@@ -0,0 +1,398 @@
+/* coroutine.c - Simple embeddable coroutine implementation
+ *
+ * Copyright (C) 2024  Luke T. Shumaker <lukeshu@lukeshu.com>
+ * SPDX-Licence-Identifier: AGPL-3.0-or-later
+ */
+
+#include <stdint.h> /* for uint8_t */
+#include <stdio.h>  /* for printf(), fprintf(), stderr */
+#include <stdlib.h> /* for malloc(), free() */
+#include <assert.h>
+#include <setjmp.h>
+
+#include "coroutine.h"
+
+/* Configuration **************************************************************/
+
+#define USE_CONFIG_COROUTINE
+#include "config.h"
+
+#ifndef CONFIG_COROUTINE_DEFAULT_STACK_SIZE
+#  error config.h must define CONFIG_COROUTINE_DEFAULT_STACK_SIZE
+#endif
+#ifndef CONFIG_COROUTINE_NUM
+#  error config.h must define CONFIG_COROUTINE_NUM
+#endif
+#ifndef CONFIG_COROUTINE_MEASURE_STACK
+#  error config.h must define CONFIG_COROUTINE_MEASURE_STACK
+#endif
+#ifndef CONFIG_COROUTINE_PROTECT_STACK
+#  error config.h must define CONFIG_COROUTINE_PROTECT_STACK
+#endif
+#ifndef CONFIG_COROUTINE_DEBUG
+#  error config.h must define CONFIG_COROUTINE_DEBUG
+#endif
+
+/* Implementation *************************************************************/
+
+/*
+ * Portability notes:
+ *
+ * - It uses GCC `__attribute__`s, though these can likely be easily
+ *   swapped for other compilers.
+ *
+ * - It has a small bit of CPU-specific code (assembly, and definition
+ *   of a STACK_GROWS_DOWNWARD={0,1} macro) in
+ *   coroutine.c:call_with_stack().  Other than this, it should be
+ *   portable to other CPUs.  It currently contains implementations
+ *   for __x86_64__ and __arm__, and should be fairly easy to add
+ *   implementations for other CPUs.
+ *
+ * - It uses setjmp()/longjmp() in "unsafe" ways.  POSIX-2017
+ *   longjmp(3) says
+ *
+ *   > If the most recent invocation of setjmp() with the
+ *   > corresponding jmp_buf ... or if the function containing the
+ *   > invocation of setjmp() has terminated execution in the interim,
+ *   > or if the invocation of setjmp() was within the scope of an
+ *   > identifier with variably modified type and execution has left
+ *   > that scope in the interim, the behavior is undefined.
+ *
+ *   We use longjmp() both of these scenarios, but make it OK by using
+ *   call_with_stack() to manage the stack ourselves, assuming the
+ *   sole reason that longjmp() behavior is undefined in such cases is
+ *   because the stack that its saved stack-pointer points to is no
+ *   longer around.  It seems absurd that an implementation would
+ *   choose to do something else, but I'm calling it out here because
+ *   you never know.
+ *
+ *   Note that setjmp()/longjmp() are defined in 3 places: in the libc
+ *   (glibc/newlib), as GCC intrinsics, and the lower-level GCC
+ *   __builtin_{setjmp,newlib} which the libc and intrinsic versions
+ *   likely use.  Our assumptions seem to be valid for
+ *   x86_64-pc-linux-gnu/gcc-14.2.1/glibc-2.40 and
+ *   arm-none-eabi/gcc-14.1.0/newlib-4.4.0.
+ *
+ * Why not use <ucontext.h>, the now-deprecated (was in POSIX.1-2001,
+ * is gone in POSIX-2008) predecesor to <setjmp.h>?  It would let us
+ * do this without any assembly or unsafe assumptions.  Simply:
+ * because newlib does not provide it.
+ */
+
+/*
+ * Design decisions and notes:
+ *
+ * - Coroutines are launched with a stack stack that is filled with
+ *   known values (zero or a pre-determined pattern, depending on the
+ *   config above).  Because all stack variables should be initialized
+ *   before they are read, this "shouldn't" make a difference, but:
+ *   (1) Initializing it to a known value allows us to measure how
+ *   much of the stack was written to, which is helpful to tune stack
+ *   sizes.  (2) Leaving it uninitialized just gives me the willies.
+ *
+ * - Because embedded programs should be adverse to using the heap,
+ *   CONFIG_COROUTINE_NUM is fixed, instead of having coroutine_add()
+ *   dynamically grow the coroutine_table as-needed.
+ *
+ * - On the flip-side, coroutine stacks are allocated on the heap
+ *   instead of having them be statically-allocated along with
+ *   coroutine_table.  (1) This reduced the blast-area of damage for a
+ *   stack-overflow; and indeed if the end of the stack alignes with a
+ *   page-boundary then memory-protection can even detect the overflow
+ *   for us.  (2) Having different-looking addresses for stack-area vs
+ *   static-area is handy for making things jump out at you when
+ *   debugging.  (3) This can likely also improve things with being
+ *   page-aligned.
+ *
+ * - Coroutines must use cr_exit() instead of returning because if
+ *   they return then they will return to call_with_stack() in
+ *   coroutine_add() (not to after the longjmp() call in
+ *   coroutine_main()), and besides being
+ *   wrong-for-our-desired-flow-control, that's a stack location that
+ *   no longer exists.
+ *
+ * Things to consider changing:
+ *
+ * - Consider having _cr_transition() go ahead and find the next
+ *   coroutine to run and longjmp() direcly to it, instead of first
+ *   jumping back to coroutine_main().  This could save a few cycles
+ *   and a few bytes.
+ */
+
+#if CONFIG_COROUTINE_DEBUG
+#	define debugf(...) printf("dbg: " __VA_ARGS__)
+#else
+#	define debugf(...)
+#endif
+
+static jmp_buf coroutine_add_env;
+static jmp_buf coroutine_main_env;
+
+enum coroutine_state {
+	CR_NONE = 0,     /* this slot in the table is empty */
+	CR_INITIALIZING, /* running, before cr_begin() */
+	CR_RUNNING,      /* running, after cr_begin() */
+	CR_RUNNABLE,     /* not running, but runnable */
+	CR_PAUSED,       /* not running, and not runnable */ 
+};
+
+/*
+ * Invariants (and non-invariants):
+ *
+ * - exactly 0 or 1 coroutines have state CR_INITIALIZING
+ * - exactly 0 or 1 coroutines have state CR_RUNNING
+ * - if coroutine_running is not zero, then
+ *   coroutine_table[coroutine_running-1] is the currently-running
+ *   coroutine
+ * - the coroutine_running coroutine either has state CR_RUNNING or
+ *   CR_INITIALIZNG
+ * - a coroutine having state CR_RUNNING does *not* imply that
+ *   coroutine_running points at that coroutine; if that coroutine is
+ *   in the middle of coroutine_add(), it coroutine_running points at
+ *   the CR_INITIALIZING child coroutine, while leaving the parent
+ *   coroutine as CR_RUNNING.
+ */
+
+struct coroutine {
+	volatile enum coroutine_state  state;
+	volatile bool                  sig_unpause;
+	jmp_buf                        env;
+	size_t                         stack_size;
+	void                          *stack;
+};
+
+static struct coroutine coroutine_table[CONFIG_COROUTINE_NUM] = {0};
+static cid_t            coroutine_running                     = 0;
+
+static void call_with_stack(void *stack, cr_fn_t fn, void *args) {
+	static void *saved_sp = NULL;
+
+	/* As part of sbc-harness, this only really needs to support
+	 * ARM-32, but being able to run it on x86-64 is useful for
+	 * debugging.  */
+#if __x86_64__
+#define STACK_GROWS_DOWNWARD 1
+	asm volatile ("movq %%rsp , %0\n\t"    /* saved_sp = sp */
+	              "movq %1    , %%rsp\n\t" /* sp = stack */
+	              "movq %3    , %%rdi\n\t" /* arg0 = args */
+	              "call *%2\n\t"           /* fn() */
+	              "movq %0    , %%rsp"     /* sp = saved_sp */
+	              :
+	              : /* %0 */"m"(saved_sp),
+	                /* %1 */"r"(stack),
+	                /* %2 */"r"(fn),
+	                /* %3 */"r"(args)
+	              : "rdi"
+	              );
+#elif __arm__
+#define STACK_GROWS_DOWNWARD 1
+	/* str/ldr can only work with a "lo" register, which sp is
+	 * not, so we use r0 as an intermediate because we're going to
+	 * clobber it with args anyway.  */
+	asm volatile ("mov r0, sp\n\t" /* [saved_sp = sp */
+	              "str r0, %0\n\t" /* ] */
+	              "mov sp, %1\n\t" /* [sp = stack] */
+	              "mov r0, %3\n\t" /* [arg0 = args] */
+	              "blx %2\n\t"     /* [fn()] */
+	              "ldr r0, %0\n\t" /* [sp = staved_sp */
+	              "mov sp, r0"     /* ] */
+	              :
+	              : /* %0 */"m"(saved_sp),
+	                /* %1 */"r"(stack),
+	                /* %2 */"r"(fn),
+	                /* %3 */"r"(args)
+	              : "r0"
+	              );
+#else
+#  error unsupported architecture
+#endif
+}
+
+#if CONFIG_COROUTINE_MEASURE_STACK || CONFIG_COROUTINE_PROTECT_STACK
+/* We just need a pattern that is unlikely to occur naturaly; this is
+ * just a few bytes that I read from /dev/random.  */
+static const uint8_t stack_pattern[] = {0x1e, 0x15, 0x16, 0x0a, 0xcc, 0x52, 0x7e, 0xb7};
+#endif
+
+static void inline assert_cid(cid_t cid) {
+	assert(cid > 0);
+	assert(cid <= CONFIG_COROUTINE_NUM);
+#if CONFIG_COROUTINE_PROTECT_STACK
+	assert(coroutine_table[cid-1].stack_size);
+	assert(coroutine_table[cid-1].stack);
+	for (size_t i = 0; i < sizeof(stack_pattern); i++) {
+		size_t j = coroutine_table[cid-1].stack_size - (i+1);
+		assert(((uint8_t*)coroutine_table[cid-1].stack)[i] == stack_pattern[i]);
+		assert(((uint8_t*)coroutine_table[cid-1].stack)[j] == stack_pattern[j%sizeof(stack_pattern)]);
+	}
+#endif
+}
+
+#define assert_cid_state(cid, opstate) do {                     \
+		assert_cid(cid);                                \
+		assert(coroutine_table[(cid)-1].state opstate); \
+	} while (0)
+
+cid_t coroutine_add_with_stack_size(size_t stack_size, cr_fn_t fn, void *args) {
+	static cid_t last_created = 0;
+	cid_t parent = coroutine_running;
+
+	if (!stack_size)
+		stack_size = CONFIG_COROUTINE_DEFAULT_STACK_SIZE;
+
+	if (parent)
+		assert_cid_state(parent, == CR_RUNNING);
+	assert(stack_size);
+	assert(fn);
+	debugf("coroutine_add_with_stack_size(%zu, %#p, %#p)...\n", stack_size, fn, args);
+
+	cid_t child;
+	{
+		size_t idx_base = last_created;
+		for (size_t idx_shift = 0; idx_shift < CONFIG_COROUTINE_NUM; idx_shift++) {
+			child = ((idx_base + idx_shift) % CONFIG_COROUTINE_NUM) + 1;
+			if (coroutine_table[child-1].state == CR_NONE)
+				goto found;
+		}
+		return 0;
+	found:
+	}
+	debugf("...child=%zu\n", child);
+
+	last_created = child;
+
+	coroutine_table[child-1].stack_size = stack_size;
+	coroutine_table[child-1].stack = malloc(stack_size);
+#if CONFIG_COROUTINE_MEASURE_STACK || CONFIG_COROUTINE_PROTECT_STACK
+	for (size_t i = 0; i < stack_size; i++)
+		((uint8_t*)coroutine_table[child-1].stack)[i] = stack_pattern[i%sizeof(stack_pattern)];
+#endif
+
+	coroutine_running = child; 
+	coroutine_table[child-1].state = CR_INITIALIZING;
+	if (!setjmp(coroutine_add_env)) { /* point=a */
+		void *stack_base = coroutine_table[child-1].stack + (STACK_GROWS_DOWNWARD ? stack_size : 0);
+#if CONFIG_COROUTINE_PROTECT_STACK
+#  if STACK_GROWS_DOWNWARD
+		stack_base -= sizeof(stack_pattern);
+#  else
+		stack_base += sizeof(stack_pattern);
+#  endif
+#endif
+		debugf("...stack     =%#p\n", coroutine_table[child-1].stack);
+		debugf("...stack_base=%#p\n", stack_base);
+		/* run until cr_begin() */
+		call_with_stack(stack_base, fn, args);
+		assert(false); /* should cr_begin() instead of returning */
+	}
+	assert_cid_state(child, == CR_RUNNABLE);
+	if (parent)
+		assert_cid_state(parent, == CR_RUNNING);
+	coroutine_running = parent;
+
+	return child;
+}
+
+void coroutine_main(void) {
+	debugf("coroutine_main()\n");
+	bool ran;
+	for (coroutine_running = 1;; coroutine_running = (coroutine_running%CONFIG_COROUTINE_NUM)+1) {
+		if (coroutine_running == 1)
+			ran = false;
+		struct coroutine *cr = &coroutine_table[coroutine_running-1];
+		if (cr->state == CR_RUNNABLE) {
+			debugf("running cid=%zu...\n", coroutine_running);
+			ran = true;
+			cr->state = CR_RUNNING;
+			if (!setjmp(coroutine_main_env)) { /* point=b */
+				longjmp(cr->env, 1); /* jump to point=c */
+				assert(false); /* should cr_exit() instead of returning */
+			}
+			assert_cid_state(coroutine_running, != CR_RUNNING);
+			if (cr->state == CR_NONE) {
+#if CONFIG_COROUTINE_MEASURE_STACK
+				size_t stack_size = cr->stack_size - (CONFIG_COROUTINE_PROTECT_STACK ? 2*sizeof(stack_pattern) : 0);
+				size_t stack_used = stack_size;
+				for (;;) {
+					size_t i = STACK_GROWS_DOWNWARD
+						? (CONFIG_COROUTINE_PROTECT_STACK ? sizeof(stack_pattern) : 0) + stack_size - stack_used
+						: stack_used - 1 - (CONFIG_COROUTINE_PROTECT_STACK ? sizeof(stack_pattern) : 0);
+					if (stack_used == 0 || ((uint8_t*)cr->stack)[i] != stack_pattern[i%sizeof(stack_pattern)])
+						break;
+					stack_used--;
+				}
+				printf("info: cid=%zu: exited having used %zu B stack space\n", coroutine_running, stack_used);
+#endif
+				free(cr->stack);
+				coroutine_table[coroutine_running-1] = (struct coroutine){0};
+			}
+		}
+		if (coroutine_running == CONFIG_COROUTINE_NUM && !ran) {
+			fprintf(stderr, "error: no runnable coroutines\n");
+			return;
+		}
+	}
+}
+
+void cr_begin(void) {
+	assert_cid_state(coroutine_running, == CR_INITIALIZING);
+
+	coroutine_table[coroutine_running-1].state = CR_RUNNABLE;
+	if (!setjmp(coroutine_table[coroutine_running-1].env)) /* point=c1 */
+		longjmp(coroutine_add_env, 1); /* jump to point=a */
+}
+
+static inline void _cr_transition(enum coroutine_state state) {
+	debugf("cid=%zu: transition %i->%i\n", coroutine_running, coroutine_table[coroutine_running-1].state, state);
+
+	coroutine_table[coroutine_running-1].state = state;
+	if (!setjmp(coroutine_table[coroutine_running-1].env)) /* point=c2 */
+		longjmp(coroutine_main_env, 1); /* jump to point=b */
+}
+
+void cr_yield(void) {
+	assert_cid_state(coroutine_running, == CR_RUNNING);
+	_cr_transition(CR_RUNNABLE);
+}
+
+void cr_pause_and_yield(void) {
+	assert_cid_state(coroutine_running, == CR_RUNNING);
+	if (coroutine_table[cid-1].sig_unpause)
+		_cr_transition(CR_RUNNABLE);
+	else
+		_cr_transition(CR_PAUSED);
+	coroutine_table[cid-1].sig_unpause = false;
+}
+
+void cr_exit(void) {
+	assert_cid_state(coroutine_running, == CR_RUNNING);
+	debugf("cid=%zu: exit\n", coroutine_running);
+
+	coroutine_table[coroutine_running-1].state = CR_NONE;
+	longjmp(coroutine_main_env, 1); /* jump to point=b */
+}
+
+void cr_unpause(cid_t cid) {
+	assert_cid_state(cid, == CR_PAUSED);
+	debugf("cr_unpause(%zu)\n", cid);
+
+	coroutine_table[cid-1].sig_unpause = false;
+	coroutine_table[cid-1].state       = CR_RUNNABLE;
+}
+
+void cr_unpause_from_sighandler(cid_t cid) {
+	assert_cid(cid);
+
+	switch (coroutine_table[cid-1].state) {
+	case CR_RUNNING:
+		coroutine_table[cid-1].sig_unpause = true;
+	case CR_PAUSED:
+		coroutine_table[cid-1].state = CR_RUNNABLE;
+	default:
+		assert(false);
+	}
+}
+
+cid_t cr_getcid(void) {
+	return coroutine_running;
+}
diff --git a/libcr/coroutine.h b/libcr/coroutine.h
new file mode 100644
index 0000000..4d83181
--- /dev/null
+++ b/libcr/coroutine.h
@@ -0,0 +1,130 @@
+/* coroutine.h - Simple embeddable coroutine implementation
+ *
+ * Copyright (C) 2024  Luke T. Shumaker <lukeshu@lukeshu.com>
+ * SPDX-Licence-Identifier: AGPL-3.0-or-later
+ */
+
+/**
+ * A coroutine is a cooperatively-multitasked form of threading.
+ *
+ * This coroutine.{h,c} form a lightweight coroutine implementation
+ * for non-multithreaded environments (only one coroutine may be
+ * running at a time (so no m:n scheduling), coroutine_{add,main} may
+ * not be called concurrently with eachother).
+ *
+ * Unlike many other lightweight or embeddable coroutine
+ * implementations, coroutine.{h,c} allow coroutines to use the stack
+ * as normal C functions and do not forbid switch() blocks in
+ * coroutines.
+ *
+ * See also: coroutine_rpc.h is a request/response system built on top
+ * of coroutine.{h,c}.
+ *
+ * See also: coroutine_chan.h is a 1-way channel system built on top
+ * of coroutine.{h,c}.
+ */
+#ifndef _COROUTINE_H_
+#define _COROUTINE_H_
+
+#include <stddef.h>  /* for size_t */
+#include <stdbool.h> /* for bool */
+
+/* typedefs *******************************************************************/
+
+/**
+ * A cid_t is a "coroutine ID", used to refer to a coroutine.
+ *
+ * May be reused if a coroutine exits.
+ *
+ * Valid IDs are `1 <= cid <= COROUTINE_NUM`; `0` is used for
+ * "none/invalid".
+ */
+typedef size_t cid_t;
+
+/**
+ * The root function for a coroutine; a coroutine function should be
+ * declared as
+ *
+ *    COROUTINE myfunc(void *_args) {
+ *        myargtype *args = args;
+ *        cr_begin();
+ *
+ *        ...
+ *
+ *        cr_end();
+ *    }
+ *
+ * The function MUST NOT ever return (GCC enforces this); call
+ * cr_exit() or cr_end() instead of returning.
+ *
+ * When creating a coroutine with coroutine_add(), the bit before
+ * cr_begin() runs before coroutine_add() returns; if `_args` points
+ * to a place on another coroutine's stack that may go away, then this
+ * is an opportunity to copy it to this coroutine's stack.  Otherwise
+ * you shouldn't do anything else before calling cr_begin().
+ * Specifically, coroutine_add() and
+ * cr_{yield,pause_and_yield,exit,end}() are explicitly forbidden to
+ * call from within a coroutine before cr_begin() (note that the
+ * cr_rpc_*() and cr_chan_*() macros call these functions).
+ */
+typedef void (*cr_fn_t)(void *args);
+#define COROUTINE __attribute__ ((noreturn)) void
+
+/* managing coroutines ********************************************************/
+
+/**
+ * Call `fn(args)` in a new coroutine with stack size `stack_size`.
+ *
+ * See the doc comment on c_fn_t for the requirements imposed on fn.
+ *
+ * May be called from outside any coroutine (before calling
+ * coroutine_main()) or from inside of a coroutine (after it cas
+ * called cr_begin()).
+ *
+ * Returns the cid of the newly-created coroutine.  May return 0 if
+ * there are already COROUTINE_NUM active coroutines.
+ */
+cid_t coroutine_add_with_stack_size(size_t stack_size, cr_fn_t fn, void *args);
+
+/**
+ * Like coroutine_add_with_stack_size(), but uses a default stack size so
+ * you don't need to think about it.
+ */
+#define coroutine_add(fn, args) coroutine_add_with_stack_size(0, fn, args)
+
+/**
+ * The main scheduler loop.
+ *
+ * "Should" never return, but will print a message to stderr and
+ * return if the program has deadlocked and there are no runnable
+ * coroutines.  So be sure to call coroutine_add() at least once
+ * before calling this.
+ */
+void coroutine_main(void);
+
+/* inside of coroutines *******************************************************/
+
+/** cr_begin() goes at the beginning of a coroutine, after it has initialized its stack.  */
+void cr_begin( void);
+/** cr_exit() terminates the currently-running coroutine.  */
+__attribute__ ((noreturn)) void cr_exit(void);
+/** cr_yield() switches to another coroutine (if there is another runnable coroutine to switch to).  */
+void cr_yield(void);
+/** cr_pause_and_yield() marks the current coroutine as not-runnable and switches to another coroutine.  */
+void cr_pause_and_yield(void);
+/** cr_unpause() marks a coroutine as runnable that has previously marked itself as non-runnable with cr_pause_and_yield().  */
+void cr_unpause(cid_t);
+/** cr_unpause_from_sighandler() is like cr_unpause(), but safe to call from a signal handler that might race with the coroutine actually pausing itself.  */
+void cr_unpause_from_sighandler(cid_t);
+/** cr_end() is a counterpart to cr_begin(), but is really just cr_exit().  */
+#define cr_end cr_exit
+
+/** cr_getcid() returns the cid of the currently-running coroutine.  */
+cid_t cr_getcid(void);
+
+/**
+ * It is not possible for one coroutine to kill another or to mark
+ * another as paused; a coroutine may only do those things to itself.
+ */
+
+#endif /* _COROUTINE_H_ */