]> git.ozlabs.org Git - ccan/commitdiff
coroutine: New module
authorDavid Gibson <david@gibson.dropbear.id.au>
Wed, 6 Jul 2016 11:31:03 +0000 (21:31 +1000)
committerDavid Gibson <david@gibson.dropbear.id.au>
Fri, 9 Dec 2016 10:15:38 +0000 (21:15 +1100)
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 <david@gibson.dropbear.id.au>
ccan/coroutine/LICENSE [new symlink]
ccan/coroutine/_info [new file with mode: 0644]
ccan/coroutine/coroutine.c [new file with mode: 0644]
ccan/coroutine/coroutine.h [new file with mode: 0644]
ccan/coroutine/test/api-1.c [new file with mode: 0644]
ccan/coroutine/test/api-2.c [new file with mode: 0644]
ccan/coroutine/test/api-3.c [new file with mode: 0644]

diff --git a/ccan/coroutine/LICENSE b/ccan/coroutine/LICENSE
new file mode 120000 (symlink)
index 0000000..dc314ec
--- /dev/null
@@ -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 (file)
index 0000000..a99629c
--- /dev/null
@@ -0,0 +1,44 @@
+#include "config.h"
+#include <stdio.h>
+#include <string.h>
+
+/**
+ * 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 <david@gibson.dropbear.id.au>
+ * 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 (file)
index 0000000..60ba416
--- /dev/null
@@ -0,0 +1,136 @@
+/* GNU LGPL version 2 (or later) - see LICENSE file for details */
+#include <assert.h>
+#include <string.h>
+#include <stdio.h>
+#include <inttypes.h>
+#include <stdlib.h>
+
+#include <ccan/ptrint/ptrint.h>
+#include <ccan/compiler/compiler.h>
+#include <ccan/build_assert/build_assert.h>
+#include <ccan/coroutine/coroutine.h>
+
+/*
+ * 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 (file)
index 0000000..1d746f4
--- /dev/null
@@ -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 <stddef.h>
+#include <stdint.h>
+#include <stdbool.h>
+#include <assert.h>
+
+#include <ccan/compiler/compiler.h>
+#include <ccan/typesafe_cb/typesafe_cb.h>
+
+/**
+ * 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 <ucontext.h>
+#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 (file)
index 0000000..fbf66df
--- /dev/null
@@ -0,0 +1,52 @@
+#include <stdlib.h>
+
+#include <ccan/coroutine/coroutine.h>
+#include <ccan/tap/tap.h>
+
+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 (file)
index 0000000..3564e0d
--- /dev/null
@@ -0,0 +1,110 @@
+#include <stdlib.h>
+
+#include <ccan/coroutine/coroutine.h>
+#include <ccan/tap/tap.h>
+
+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 (file)
index 0000000..e06c03d
--- /dev/null
@@ -0,0 +1,90 @@
+#include <stdlib.h>
+
+#include <ccan/coroutine/coroutine.h>
+#include <ccan/tap/tap.h>
+
+/* 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();
+}