From 91aae651bf90be46773a246e4c46b9e221353fbd Mon Sep 17 00:00:00 2001 From: Samuel Williams Date: Thu, 27 Jun 2019 18:59:25 +1200 Subject: Stack copying implementation of coroutines. --- coroutine/copy/Context.c | 141 +++++++++++++++++++++++++++++++++++++++++++++++ coroutine/copy/Context.h | 79 ++++++++++++++++++++++++++ 2 files changed, 220 insertions(+) create mode 100644 coroutine/copy/Context.c create mode 100644 coroutine/copy/Context.h (limited to 'coroutine') diff --git a/coroutine/copy/Context.c b/coroutine/copy/Context.c new file mode 100644 index 0000000000..a1b8a71200 --- /dev/null +++ b/coroutine/copy/Context.c @@ -0,0 +1,141 @@ +/* + * This file is part of the "Coroutine" project and released under the MIT License. + * + * Created by Samuel Williams on 24/6/2019. + * Copyright, 2019, by Samuel Williams. All rights reserved. +*/ + +#include "Context.h" + +// http://gcc.gnu.org/onlinedocs/gcc/Alternate-Keywords.html +#ifndef __GNUC__ +#define __asm__ asm +#endif + +#if defined(__sparc) +__attribute__((noinline)) +// https://marc.info/?l=linux-sparc&m=131914569320660&w=2 +static void coroutine_flush_register_windows() { + __asm__ +#ifdef __GNUC__ + __volatile__ +#endif +#if defined(__sparcv9) || defined(__sparc_v9__) || defined(__arch64__) +#ifdef __GNUC__ + ("flushw" : : : "%o7") +#else + ("flushw") +#endif +#else + ("ta 0x03") +#endif + ; +} +#else +static void coroutine_flush_register_windows() {} +#endif + +int coroutine_save_stack(struct coroutine_context * context) { + void *stack_pointer = &stack_pointer; + + assert(context->stack); + assert(context->base); + + // At this point, you may need to ensure on architectures that use register windows, that all registers are flushed to the stack. + coroutine_flush_register_windows(); + + // Save stack to private area: + if (stack_pointer < context->base) { + size_t size = (char*)context->base - (char*)stack_pointer; + assert(size <= context->size); + + memcpy(context->stack, stack_pointer, size); + context->used = size; + } else { + size_t size = (char*)stack_pointer - (char*)context->base; + assert(size <= context->size); + + memcpy(context->stack, context->base, size); + context->used = size; + } + + // Save registers / restore point: + return _setjmp(context->state); +} + +__attribute__((noreturn, noinline)) +static void coroutine_restore_stack_padded(struct coroutine_context *context, void * buffer) { + void *stack_pointer = &stack_pointer; + + assert(context->base); + + // Restore stack from private area: + if (stack_pointer < context->base) { + void * bottom = (char*)context->base - context->used; + assert(bottom > stack_pointer); + + memcpy(bottom, context->stack, context->used); + } else { + void * top = (char*)context->base + context->used; + assert(top < stack_pointer); + + memcpy(context->base, context->stack, context->used); + } + + // Restore registers: + // The `| (int)buffer` is to force the compiler NOT to elide he buffer and `alloca`. + _longjmp(context->state, 1 | (int)buffer); +} + +static const size_t GAP = 128; + +// In order to swap between coroutines, we need to swap the stack and registers. +// `setjmp` and `longjmp` are able to swap registers, but what about swapping stacks? You can use `memcpy` to copy the current stack to a private area and `memcpy` to copy the private stack of the next coroutine to the main stack. +// But if the stack yop are copying in to the main stack is bigger than the currently executing stack, the `memcpy` will clobber the current stack frame (including the context argument). So we use `alloca` to push the current stack frame *beyond* the stack we are about to copy in. This ensures the current stack frame in `coroutine_restore_stack_padded` remains valid for calling `longjmp`. +__attribute__((noreturn)) +void coroutine_restore_stack(struct coroutine_context *context) { + void *stack_pointer = &stack_pointer; + void *buffer = NULL; + ssize_t offset = 0; + + // We must ensure that the next stack frame is BEYOND the stack we are restoring: + if (stack_pointer < context->base) { + offset = (char*)stack_pointer - ((char*)context->base - context->used) + GAP; + if (offset > 0) buffer = alloca(offset); + } else { + offset = ((char*)context->base + context->used) - (char*)stack_pointer + GAP; + if (offset > 0) buffer = alloca(offset); + } + + assert(context->used > 0); + + coroutine_restore_stack_padded(context, buffer); +} + +struct coroutine_context *coroutine_transfer(struct coroutine_context *current, struct coroutine_context *target) +{ + struct coroutine_context *previous = target->from; + + // In theory, either this condition holds true, or we should assign the base address to target: + assert(current->base == target->base); + // If you are trying to copy the coroutine to a different thread + // target->base = current->base + + target->from = current; + + assert(current != target); + + // It's possible to come here, even thought the current fiber has been terminated. We are never going to return so we don't bother saving the stack. + + if (current->stack) { + if (coroutine_save_stack(current) == 0) { + coroutine_restore_stack(target); + } + } else { + coroutine_restore_stack(target); + } + + target->from = previous; + + return target; +} diff --git a/coroutine/copy/Context.h b/coroutine/copy/Context.h new file mode 100644 index 0000000000..a62efa4e8a --- /dev/null +++ b/coroutine/copy/Context.h @@ -0,0 +1,79 @@ +/* + * This file is part of the "Coroutine" project and released under the MIT License. + * + * Created by Samuel Williams on 27/6/2019. + * Copyright, 2019, by Samuel Williams. All rights reserved. +*/ + +#pragma once + +#include +#include +#include +#include +#include +#include + +#define COROUTINE __attribute__((noreturn)) void + +// This stack copying implementation which uses a private stack for each coroutine, including the main one. +#define COROUTINE_PRIVATE_STACK + +struct coroutine_context +{ + // Private stack: + void *stack; + size_t size, used; + + // The top (or bottom) of the currently executing stack: + void *base; + + jmp_buf state; + + struct coroutine_context *from; +}; + +typedef COROUTINE(*coroutine_start)(struct coroutine_context *from, struct coroutine_context *self); + +int coroutine_save_stack(struct coroutine_context * context); +COROUTINE coroutine_restore_stack(struct coroutine_context *context); + +// @param stack The private stack area memory allocation (pointer to lowest address). +// @param size The size of the private stack area. +// @param base A stack pointer to the base of the main stack. On x86 hardware, this is the upper extent of the region that will be copied to the private stack. +static inline void coroutine_initialize_main(struct coroutine_context *context, void *stack, size_t size, void *base) { + context->stack = stack; + context->size = size; + context->used = 0; + + assert(base); + context->base = base; + + context->from = NULL; +} + +// @param start The start function to invoke. +static inline void coroutine_initialize( + struct coroutine_context *context, + coroutine_start start, + void *stack, + size_t size, + void *base +) { + assert(start && stack && size >= 1024); + + coroutine_initialize_main(context, stack, size, base); + + if (coroutine_save_stack(context)) { + start(context->from, context); + } +} + +struct coroutine_context *coroutine_transfer(struct coroutine_context *current, register struct coroutine_context *target); + +static inline void coroutine_destroy(struct coroutine_context *context) +{ + context->stack = NULL; + context->size = 0; + context->from = NULL; +} -- cgit v1.2.3