From 531d55f2aaa35770addb2e4bd92414b3d1194e51 Mon Sep 17 00:00:00 2001 From: the lemons Date: Sat, 3 Sep 2022 09:41:47 -0500 Subject: initial commit: coroutine library --- coroutine/+test.ha | 57 ++++++++++++++++++++++++++++ coroutine/+x86_64.s | 87 ++++++++++++++++++++++++++++++++++++++++++ coroutine/coroutine.ha | 96 +++++++++++++++++++++++++++++++++++++++++++++++ coroutine/types+x86_64.ha | 4 ++ 4 files changed, 244 insertions(+) create mode 100644 coroutine/+test.ha create mode 100644 coroutine/+x86_64.s create mode 100644 coroutine/coroutine.ha create mode 100644 coroutine/types+x86_64.ha diff --git a/coroutine/+test.ha b/coroutine/+test.ha new file mode 100644 index 0000000..1ac5217 --- /dev/null +++ b/coroutine/+test.ha @@ -0,0 +1,57 @@ +// License: MPL-2.0 +// (c) 2022 citrons + +@test fn coroutine() void = { + let test: int = 0; + let co1 = new(&test_coroutine); + let co2 = new(&test_coroutine); + defer destroy(co1); + defer destroy(co2); + for (co1.status != status::dead || co2.status != status::dead) { + let val = test; + test = *(resume(co1, &val) as *int); + val = test; + test = *(resume(co2, &val) as *int); + }; + assert(test == 100); +}; + +fn test_coroutine(arg: nullable *void) nullable *void = { + let i = *(arg as *int); + let v: nullable *void = null; + for (let j = 0; j < 50; j += 1) { + v = suspend(&(i + 1)); + i = *(v as *int); + }; + return v; +}; + +let test: int = 0; +@test fn nested_coroutine() void = { + let co1 = new(&nested); + defer destroy(co1); + resume(co1, null); + for (co1.status != status::dead) { + let co2 = new(&nested); + defer destroy(co2); + resume(co1, co2); + assert(co2.status == status::dead); + }; + assert(test == 2500); +}; + +fn nested(arg: nullable *void) nullable *void = { + for (let i = 0; i < 50; i += 1) { + let co = suspend(null): + nullable *coroutine; + match (co) { + case null => + test += 1; + case let co: *coroutine => + for (co.status != status::dead) + resume(co, null); + }; + }; + return null; +}; + diff --git a/coroutine/+x86_64.s b/coroutine/+x86_64.s new file mode 100644 index 0000000..aaa69e0 --- /dev/null +++ b/coroutine/+x86_64.s @@ -0,0 +1,87 @@ +.global couroutine._start +.type couroutine._start,@function + +.bss +.align 8 +coro_state: .quad 0 +caller_state: .quad 0 + +.macro savestate to +mov %rsp,(\to) +mov %rbp,8(\to) +mov %r12,16(\to) +mov %r13,24(\to) +mov %r14,32(\to) +mov %r15,40(\to) +mov %rbx,48(\to) +.endm + +.macro loadstate from +mov (\from),%rsp +mov 8(\from),%rbp +mov 16(\from),%r12 +mov 24(\from),%r13 +mov 32(\from),%r14 +mov 40(\from),%r15 +mov 48(\from),%rbx +.endm + +.text +.global coroutine.arch_init +.type couroutine.arch_init,@function +coroutine.arch_init: + movabs $coro_state,%rax + push (%rax) + mov %rsi,(%rax) + + movabs $caller_state,%rax + push (%rax) + sub $56,%rsp + mov %rsp,(%rax) + savestate %rsp + + // Initialize stack pointer to supplied stack. + add %rcx,%rdx + mov %rdx,%rsp + mov %rdx,%rbp + + // rdi contains function to be called by _start. + call coroutine._start + +.global coroutine.arch_resume +.type coroutine.arch_resume,@function +coroutine.arch_resume: + movabs $coro_state,%rax + push (%rax) + mov %rdi,(%rax) + + movabs $caller_state,%rax + push (%rax) + sub $56,%rsp + mov %rsp,(%rax) + savestate %rsp + + loadstate %rdi + mov %rsi,%rax + ret + +.global coroutine.arch_suspend +.type coroutine.arch_suspend,@function +coroutine.arch_suspend: + movabs $coro_state,%rcx + mov (%rcx),%rax + savestate %rax + + movabs $caller_state,%rdx + mov (%rdx),%rax + loadstate %rax + + // The stack pointer (and other callee-saved registers) is now set back to + // the original call to arch_resume. Restore the original coro_state and + // caller_state values and return the value supplied as argument. + add $56,%rsp + pop (%rdx) + pop (%rcx) + mov %rdi,%rax + ret + diff --git a/coroutine/coroutine.ha b/coroutine/coroutine.ha new file mode 100644 index 0000000..00536d8 --- /dev/null +++ b/coroutine/coroutine.ha @@ -0,0 +1,96 @@ +// License: MPL-2.0 +// (c) 2022 citrons +use rt; +use fmt; + +def STACK_SIZE: size = 8192; + +// A coroutine. +export type coroutine = struct { + // The function comprising the body of the coroutine. + func: *func, + // The current execution status of the coroutine. + status: status, + stack: *void, + state: arch_state, +}; + +// Represents the execution status of a coroutine. +export type status = enum { + // The coroutine has been suspended or has not been executed yet. + suspended, + // The coroutine is currently executing. + running, + // The coroutine has completed. + dead, + dying, +}; + +// A function that can be run as a coroutine. +export type func = fn(arg: nullable *void) nullable *void; + +// Create a coroutine which will execute the function f. When done using the +// coroutine, use [[destroy]]. +export fn new(f: *func) *coroutine = { + let stack = rt::malloc(STACK_SIZE) as *void; + let co = alloc(coroutine {func = f, stack = stack, ...}); + arch_init(co.func, &co.state, stack, STACK_SIZE); + return co; +}; + +// Stop a coroutine. +export fn terminate(co: *coroutine) void = { + if (co.status == status::dead) return; + assert(co.status != status::running); + rt::free_(co.stack); + co.status = status::dead; +}; + +// Free a coroutine. +export fn destroy(co: *coroutine) void = { + terminate(co); + free(co); +}; + +let running_: nullable *coroutine = null; + +// Returns the currently running coroutine. +export fn running() nullable *coroutine = running_; + +// Start or resume a coroutine. When called for the first time on a coroutine, +// arg is passed as the argument to the body. If the coroutine has suspended, +// [[resume]] restarts it, and arg is returned as the result of [[suspend]]. +// When the body completes, [[resume]] returns its return value. +export fn resume(co: *coroutine, arg: nullable *void) nullable *void = { + if (co.status == status::dead) return null; + assert(co.status == status::suspended, + "cannot resume non-suspended coroutine"); + let prev = running_; + defer running_ = prev; + running_ = co; + defer if (co.status == status::dying) terminate(co); + co.status = status::running; + return arch_resume(&co.state); +}; + +// Suspend the execution of the present coroutine. arg is returned by +// [[resume]]. +export fn suspend(arg: nullable *void) nullable *void = { + let co = running_ as *coroutine; + if (co.status == status::running) + co.status = status::suspended; + return arch_suspend(arg); +}; + +export @noreturn fn _start(f: *func) void = { + let arg = arch_suspend(null); + let retval = f(arg); + let co = running_ as *coroutine; + co.status = status::dying; + suspend(retval); + assert(false); +}; + +fn arch_suspend(arg: nullable *void) nullable *void; +fn arch_init(f: *func, s: *arch_state, stack: *void, stack_size: size) void; +fn arch_resume(s: *arch_state) nullable *void; diff --git a/coroutine/types+x86_64.ha b/coroutine/types+x86_64.ha new file mode 100644 index 0000000..3ceafe2 --- /dev/null +++ b/coroutine/types+x86_64.ha @@ -0,0 +1,4 @@ +// License: MPL-2.0 +// (c) 2022 citrons + +export type arch_state = [7]u64; -- cgit v1.2.3