From 1ddc881f084e2527ad9e3541807469920ac299b4 Mon Sep 17 00:00:00 2001 From: David Gibson Date: Wed, 6 Jul 2016 21:31:03 +1000 Subject: [PATCH] coroutine: New module This is essentially a wrapper around ucontext.h, but the idea is that alternative back end implementations could be used in future. Signed-off-by: David Gibson --- ccan/coroutine/LICENSE | 1 + ccan/coroutine/_info | 44 +++++++ ccan/coroutine/coroutine.c | 136 +++++++++++++++++++++ ccan/coroutine/coroutine.h | 233 ++++++++++++++++++++++++++++++++++++ ccan/coroutine/test/api-1.c | 52 ++++++++ ccan/coroutine/test/api-2.c | 110 +++++++++++++++++ ccan/coroutine/test/api-3.c | 90 ++++++++++++++ 7 files changed, 666 insertions(+) create mode 120000 ccan/coroutine/LICENSE create mode 100644 ccan/coroutine/_info create mode 100644 ccan/coroutine/coroutine.c create mode 100644 ccan/coroutine/coroutine.h create mode 100644 ccan/coroutine/test/api-1.c create mode 100644 ccan/coroutine/test/api-2.c create mode 100644 ccan/coroutine/test/api-3.c diff --git a/ccan/coroutine/LICENSE b/ccan/coroutine/LICENSE new file mode 120000 index 00000000..dc314eca --- /dev/null +++ b/ccan/coroutine/LICENSE @@ -0,0 +1 @@ +../../licenses/LGPL-2.1 \ No newline at end of file diff --git a/ccan/coroutine/_info b/ccan/coroutine/_info new file mode 100644 index 00000000..a99629c9 --- /dev/null +++ b/ccan/coroutine/_info @@ -0,0 +1,44 @@ +#include "config.h" +#include +#include + +/** + * coroutine - Co-routines + * + * This code has helper functions for implementing co-routines, that + * is, explicit co-operative context switching. It's intended to + * provide similar functionality to ucontext, but with a cleaner + * interface. At the moment this is implemented in terms of ucontext, + * but the hope is to add other implementations for platforms that + * don't have ucontext in future. + * + * Author: David Gibson + * License: LGPL (v2.1 or any later version) + * + * Ccanlint: + * // Context switching really confuses valgrind + * tests_pass_valgrind FAIL + */ +int main(int argc, char *argv[]) +{ + /* Expect exactly one argument */ + if (argc != 2) + return 1; + + if (strcmp(argv[1], "depends") == 0) { + printf("ccan/ptrint\n"); + printf("ccan/compiler\n"); + printf("ccan/build_assert\n"); + printf("ccan/typesafe_cb\n"); + return 0; + } + + if (strcmp(argv[1], "ported") == 0) { +#if !HAVE_UCONTEXT + printf("Requires working ucontext.h\n"); +#endif + return 0; + } + + return 1; +} diff --git a/ccan/coroutine/coroutine.c b/ccan/coroutine/coroutine.c new file mode 100644 index 00000000..60ba4169 --- /dev/null +++ b/ccan/coroutine/coroutine.c @@ -0,0 +1,136 @@ +/* GNU LGPL version 2 (or later) - see LICENSE file for details */ +#include +#include +#include +#include +#include + +#include +#include +#include +#include + +/* + * Stack management + */ + +struct coroutine_stack { + uint64_t magic; + size_t size; +}; + +/* Returns lowest stack addres, regardless of growth direction */ +static UNNEEDED void *coroutine_stack_base(struct coroutine_stack *stack) +{ +#if HAVE_STACK_GROWS_UPWARDS + return (char *)(stack + 1); +#else + return (char *)stack - stack->size; +#endif +} + +struct coroutine_stack *coroutine_stack_init(void *buf, size_t bufsize, + size_t metasize) +{ + struct coroutine_stack *stack; + + BUILD_ASSERT(COROUTINE_STK_OVERHEAD == sizeof(*stack)); +#ifdef MINSIGSTKSZ + BUILD_ASSERT(COROUTINE_MIN_STKSZ >= MINSIGSTKSZ); +#endif + + if (bufsize < (COROUTINE_MIN_STKSZ + sizeof(*stack) + metasize)) + return NULL; + +#if HAVE_STACK_GROWS_UPWARDS + stack = (char *)buf + metasize; +#else + stack = (struct coroutine_stack *) + ((char *)buf + bufsize - metasize) - 1; +#endif + + stack->magic = COROUTINE_STACK_MAGIC; + stack->size = bufsize - sizeof(*stack) - metasize; + + return stack; +} + +void coroutine_stack_release(struct coroutine_stack *stack, size_t metasize) +{ + memset(stack, 0, sizeof(*stack)); +} + +struct coroutine_stack *coroutine_stack_check(struct coroutine_stack *stack, + const char *abortstr) +{ + if (stack && (stack->magic == COROUTINE_STACK_MAGIC) + && (stack->size >= COROUTINE_MIN_STKSZ)) + return stack; + + if (abortstr) { + if (!stack) + fprintf(stderr, "%s: NULL coroutine stack\n", abortstr); + else + fprintf(stderr, + "%s: Bad coroutine stack at %p (magic=0x%"PRIx64" size=%zd)\n", + abortstr, stack, stack->magic, stack->size); + abort(); + } + return NULL; +} + +size_t coroutine_stack_size(const struct coroutine_stack *stack) +{ + return stack->size; +} + +#if HAVE_UCONTEXT +static void coroutine_uc_stack(stack_t *uc_stack, + const struct coroutine_stack *stack) +{ + uc_stack->ss_size = coroutine_stack_size(stack); + uc_stack->ss_sp = coroutine_stack_base((struct coroutine_stack *)stack); +} +#endif /* HAVE_UCONTEXT */ + +/* + * Coroutine switching + */ + +#if HAVE_UCONTEXT +void coroutine_init_(struct coroutine_state *cs, + void (*fn)(void *), void *arg, + struct coroutine_stack *stack) +{ + getcontext (&cs->uc); + + coroutine_uc_stack(&cs->uc.uc_stack, stack); + + if (HAVE_POINTER_SAFE_MAKECONTEXT) { + makecontext(&cs->uc, (void *)fn, 1, arg); + } else { + ptrdiff_t si = ptr2int(arg); + ptrdiff_t mask = (1UL << (sizeof(int) * 8)) - 1; + int lo = si & mask; + int hi = si >> (sizeof(int) * 8); + + makecontext(&cs->uc, (void *)fn, 2, lo, hi); + } + +} + +void coroutine_jump(const struct coroutine_state *to) +{ + setcontext(&to->uc); + assert(0); +} + +void coroutine_switch(struct coroutine_state *from, + const struct coroutine_state *to) +{ + int rc; + + rc = swapcontext(&from->uc, &to->uc); + assert(rc == 0); +} +#endif /* HAVE_UCONTEXT */ diff --git a/ccan/coroutine/coroutine.h b/ccan/coroutine/coroutine.h new file mode 100644 index 00000000..1d746f49 --- /dev/null +++ b/ccan/coroutine/coroutine.h @@ -0,0 +1,233 @@ +/* Licensed under LGPLv2.1+ - see LICENSE file for details */ +#ifndef CCAN_COROUTINE_H +#define CCAN_COROUTINE_H +/*#define CCAN_COROUTINE_DEBUG 1*/ +#include "config.h" + +#include +#include +#include +#include + +#include +#include + +/** + * struct coroutine_stack + * + * Describes a stack suitable for executing a coroutine. This + * structure is always contained within the stack it describes. + */ +struct coroutine_stack; + +/** + * struct coroutine_state + * + * Describes the state of an in-progress coroutine. + */ +struct coroutine_state; + +/* + * Stack management + */ + +/** + * COROUTINE_STK_OVERHEAD - internal stack overhead + * + * Number of bytes of a stack which coroutine needs for its own + * tracking information. + */ +#define COROUTINE_STK_OVERHEAD (sizeof(uint64_t) + sizeof(size_t)) + +/** + * COROUTINE_MIN_STKSZ - Minimum coroutine stack size + * + * Contains the minimum size for a coroutine stack (not including + * overhead). On systems with MINSTKSZ, guaranteed to be at least as + * large as MINSTKSZ. + */ +#define COROUTINE_MIN_STKSZ 2048 + +/** + * COROUTINE_STACK_MAGIC - Magic number for coroutine stacks + */ +#define COROUTINE_STACK_MAGIC 0xc040c040574c574c + + +/** + * coroutine_stack_init - Prepare a coroutine stack in an existing buffer + * @buf: buffer to use for the coroutine stack + * @bufsize: size of @buf + * @metasize: size of metadata to add to the stack (not including + * coroutine internal overhead) + * + * Prepares @buf for use as a coroutine stack, returning a + * coroutine_stack *, allocated from within the buffer. Returns NULL + * on failure. + * + * This will fail if the bufsize < (COROUTINE_MIN_STKSZ + + * COROUTINE_STK_OVERHEAD + metasize). + */ +struct coroutine_stack *coroutine_stack_init(void *buf, size_t bufsize, + size_t metasize); + +/** + * coroutine_stack_release - Stop using a coroutine stack + * @stack: coroutine stack to release + * @metasize: size of metadata + * + * This releases @stack, making it no longer suitable for use as a + * coroutine stack. @metasize must be equal to the metasize passed to + * coroutine_stack_init. + */ +void coroutine_stack_release(struct coroutine_stack *stack, size_t metasize); + +/** + * coroutine_stack_check - Validate and return a coroutine stack + * @stack: stack to check + * @abortstr: the location to print on aborting, or NULL. + * + * Debugging check if @stack doesn't appear to be a valid coroutine + * stack, and @abortstr is non-NULL it will be printed and the + * function will abort. + * + * Returns @stack if it appears valid, NULL if not (it can never + * return NULL if @abortstr is set). + */ +struct coroutine_stack *coroutine_stack_check(struct coroutine_stack *stack, + const char *abortstr); + +/** + * coroutine_stack_to_metadata - Returns pointer to user's metadata + * allocated within the stack + * @stack: coroutine stack + * @metasize: size of metadata + * + * Returns a pointer to the metadata area within @stack. This is of + * size given at initialization time, and won't be overwritten by + * coroutines executing on the stack. It's up to the caller what to + * put in here. @metasize must be equal to the value passed to + * coroutine_stack_init(). + */ +static inline void *coroutine_stack_to_metadata(struct coroutine_stack *stack, + size_t metasize) +{ +#if HAVE_STACK_GROWS_UPWARDS + return (char *)stack - metasize; +#else + return (char *)stack + COROUTINE_STK_OVERHEAD; +#endif +} + +/** + * coroutine_stack_from_metadata - Returns pointer to coroutine stack + * pointer given pointer to user metadata + * @metadat: user metadata within a stack + * @metasize: size of metadata + * + * Returns a pointer to the coroutine_stack handle within a stack. + * The argument must be a pointer returned by + * coroutine_stack_to_metadata() at an earlier time. @metasize must be + * equal to the value passed to coroutine_stack_init(). + */ +static inline struct coroutine_stack * +coroutine_stack_from_metadata(void *metadata, size_t metasize) +{ +#if HAVE_STACK_GROWS_UPWARDS + return (struct coroutine_stack *)((char *)metadata + metasize); +#else + return (struct coroutine_stack *)((char *)metadata + - COROUTINE_STK_OVERHEAD); +#endif +} + +/** + * coroutine_stack_size - Return size of a coroutine stack + * @stack: coroutine stack + * + * Returns the size of the coroutine stack @stack. This does not + * include the overhead of struct coroutine_stack or metdata. + */ +size_t coroutine_stack_size(const struct coroutine_stack *stack); + +/* + * Coroutine switching + */ + +#if HAVE_UCONTEXT +#include +#define COROUTINE_AVAILABLE 1 +#else +#define COROUTINE_AVAILABLE 0 +#endif + +struct coroutine_state { +#if HAVE_UCONTEXT + ucontext_t uc; +#endif /* HAVE_UCONTEXT */ +}; + +#if COROUTINE_AVAILABLE + +/** + * coroutine_init - Prepare a coroutine for execution + * @cs: coroutine_state structure to initialize + * @fn: function to start executing in the coroutine + * @arg: argument for @fn + * @stack: stack to use for the coroutine + * + * Prepares @cs as a new coroutine which will execute starting with + * function @fn, using stack @stack. + */ +void coroutine_init_(struct coroutine_state *cs, + void (*fn)(void *), void *arg, + struct coroutine_stack *stack); +#define coroutine_init(cs, fn, arg, stack) \ + coroutine_init_((cs), \ + typesafe_cb(void, void *, (fn), (arg)), \ + (arg), (stack)) + +/** + * coroutine_jump - Irreversibly switch to executing a coroutine + * @to: coroutine to switch to + * + * Immediately jump to executing coroutine @to (at whatever point in + * execution it was up to). Never returns. + */ +void NORETURN coroutine_jump(const struct coroutine_state *to); + +/** + * coroutine_switch - Switch coroutines + * @from: coroutine in which to store current execution state + * @to: coroutine to switch to + * + * Stop executing the current routine, saving its state in @from, and + * switch to executing the coroutine @to. Returns only when something + * switches or jumps back to @from. + */ +void coroutine_switch(struct coroutine_state *from, + const struct coroutine_state *to); + +#else + +static inline void coroutine_init(struct coroutine_state *cs, + void (*fn)(void *), void *arg, + struct coroutine_stack *stack) +{ + assert(0); +} + +static inline void NORETURN coroutine_jump(const struct coroutine_state *to) +{ + assert(0); +} + +static inline void coroutine_switch(struct coroutine_state *from, + const struct coroutine_state *to) +{ + assert(0); +} + +#endif /* !COROUTINE_AVAILABLE */ + +#endif /* CCAN_COROUTINE_H */ diff --git a/ccan/coroutine/test/api-1.c b/ccan/coroutine/test/api-1.c new file mode 100644 index 00000000..fbf66df6 --- /dev/null +++ b/ccan/coroutine/test/api-1.c @@ -0,0 +1,52 @@ +#include + +#include +#include + +static int global = 0; + +static void trivial_fn(void *p) +{ + struct coroutine_state *ret = (struct coroutine_state *)p; + + global = 1; + + coroutine_jump(ret); +} + +static void test_trivial(struct coroutine_stack *stack) +{ + struct coroutine_state t, master; + + if (!COROUTINE_AVAILABLE) { + skip(1, "Coroutines not available"); + return; + } + + coroutine_init(&t, trivial_fn, &master, stack); + coroutine_switch(&master, &t); + + ok1(global == 1); +} + + +int main(void) +{ + char buf[COROUTINE_MIN_STKSZ + COROUTINE_STK_OVERHEAD]; + struct coroutine_stack *stack; + + /* This is how many tests you plan to run */ + plan_tests(4); + + stack = coroutine_stack_init(buf, sizeof(buf), 0); + ok1(stack != NULL); + ok1(coroutine_stack_check(stack, NULL) == stack); + ok1(coroutine_stack_size(stack) == COROUTINE_MIN_STKSZ); + + test_trivial(stack); + + coroutine_stack_release(stack, 0); + + /* This exits depending on whether all tests passed */ + return exit_status(); +} diff --git a/ccan/coroutine/test/api-2.c b/ccan/coroutine/test/api-2.c new file mode 100644 index 00000000..3564e0df --- /dev/null +++ b/ccan/coroutine/test/api-2.c @@ -0,0 +1,110 @@ +#include + +#include +#include + +struct state { + struct coroutine_state c1, c2; + struct coroutine_state master; + int val; +}; + +static void f1(void *p) +{ + struct state *state = (struct state *)p; + + coroutine_switch(&state->c1, &state->c2); + + ok(state->val == 17, "state->val == %d [expected 17]", state->val); + state->val = 23; + + coroutine_switch(&state->c1, &state->c2); + + ok(state->val == 24, "state->val == %d [expected 24]", state->val); + + coroutine_switch(&state->c1, &state->c2); + + ok(state->val == 26, "state->val == %d [expected 26]", state->val); + + coroutine_switch(&state->c1, &state->c2); + + ok(state->val == 29, "state->val == %d [expected 29]", state->val); + + coroutine_switch(&state->c1, &state->c2); +} + +static void f2(void *p) +{ + struct state *state = (struct state *)p; + + state->val = 17; + + coroutine_switch(&state->c2, &state->c1); + + ok(state->val == 23, "state->val == %d [expected 23]", state->val); + state->val += 1; + + coroutine_switch(&state->c2, &state->c1); + + state->val += 2; + + coroutine_switch(&state->c2, &state->c1); + + state->val += 3; + + coroutine_switch(&state->c2, &state->c1); + + coroutine_jump(&state->master); +} + +static void test1(size_t bufsz) +{ + void *buf1, *buf2; + struct coroutine_stack *stack1, *stack2; + + buf1 = malloc(bufsz); + ok1(buf1 != NULL); + stack1 = coroutine_stack_init(buf1, bufsz, 0); + diag("buf1=%p stack1=%p bufsz=0x%zx overhead=0x%zx\n", + buf1, stack1, bufsz, COROUTINE_STK_OVERHEAD); + ok1(coroutine_stack_check(stack1, NULL) == stack1); + ok1(coroutine_stack_size(stack1) == bufsz - COROUTINE_STK_OVERHEAD); + + buf2 = malloc(bufsz); + ok1(buf2 != NULL); + stack2 = coroutine_stack_init(buf2, bufsz, 0); + ok1(coroutine_stack_check(stack2, NULL) == stack2); + ok1(coroutine_stack_size(stack2) == bufsz - COROUTINE_STK_OVERHEAD); + + if (COROUTINE_AVAILABLE) { + struct state s; + + coroutine_init(&s.c1, f1, &s, stack1); + coroutine_init(&s.c2, f2, &s, stack2); + + coroutine_switch(&s.master, &s.c1); + } else { + skip(5, "Coroutines not available"); + } + + ok(1, "Completed test1"); + + coroutine_stack_release(stack1, 0); + ok1(coroutine_stack_check(stack1, NULL) == NULL); + free(buf1); + coroutine_stack_release(stack2, 0); + ok1(coroutine_stack_check(stack2, NULL) == NULL); + free(buf2); +} + + +int main(void) +{ + /* This is how many tests you plan to run */ + plan_tests(14); + + test1(8192); + + /* This exits depending on whether all tests passed */ + return exit_status(); +} diff --git a/ccan/coroutine/test/api-3.c b/ccan/coroutine/test/api-3.c new file mode 100644 index 00000000..e06c03d3 --- /dev/null +++ b/ccan/coroutine/test/api-3.c @@ -0,0 +1,90 @@ +#include + +#include +#include + +/* Test metadata */ +#define META_MAGIC 0x4d86aa82ec1892f6 +#define BUFSIZE 8192 + +struct metadata { + uint64_t magic; +}; + +struct state { + struct coroutine_state ret; + unsigned long total; +}; + +/* Touch a bunch of stack */ +static void clobber(void *p) +{ + struct state *s = (struct state *)p; + char buf[BUFSIZE - COROUTINE_MIN_STKSZ]; + int i; + + for (i = 0; i < sizeof(buf); i++) { + buf[i] = random() & 0xff; + } + + diag("Wrote random to buffer\n"); + + s->total = 0; + for (i = 0; i < sizeof(buf); i++) { + s->total += buf[i]; + } + + coroutine_jump(&s->ret); +} + +static void test_metadata(struct coroutine_stack *stack) +{ + struct metadata *meta; + + meta = coroutine_stack_to_metadata(stack, sizeof(*meta)); + ok1(coroutine_stack_from_metadata(meta, sizeof(*meta)) == stack); + + meta->magic = META_MAGIC; + ok1(meta->magic == META_MAGIC); + + if (COROUTINE_AVAILABLE) { + struct coroutine_state t; + struct state s = { + }; + + coroutine_init(&t, clobber, &s, stack); + coroutine_switch(&s.ret, &t); + ok1(s.total != 0); + } else { + skip(1, "Coroutines not available"); + } + + ok1(coroutine_stack_to_metadata(stack, sizeof(*meta)) == meta); + ok1(coroutine_stack_from_metadata(meta, sizeof(*meta)) == stack); + ok1(meta->magic == META_MAGIC); +} + +int main(void) +{ + char buf[BUFSIZE]; + struct coroutine_stack *stack; + + /* This is how many tests you plan to run */ + plan_tests(9); + + /* Fix seed so we get consistent, though pseudo-random results */ + srandom(0); + + stack = coroutine_stack_init(buf, sizeof(buf), sizeof(struct metadata)); + ok1(stack != NULL); + ok1(coroutine_stack_check(stack, NULL) == stack); + ok1(coroutine_stack_size(stack) + == BUFSIZE - COROUTINE_STK_OVERHEAD - sizeof(struct metadata)); + + test_metadata(stack); + + coroutine_stack_release(stack, sizeof(struct metadata)); + + /* This exits depending on whether all tests passed */ + return exit_status(); +} -- 2.39.2