3 ms·

If you do not have an independent context structure how do you avoid stack overflow in the event of a coroutine cycle with an unknown cycle length (e.g A -> B -

by Veserv 6y ago

If you do not have an independent context structure how do you avoid stack overflow in the event of a coroutine cycle with an unknown cycle length (e.g A -> B -> C -> ... -> A in an infinite loop)? For an example of where this comes up in schedulers, consider a simple periodic schedule that runs A then B then C then ... then starts back over.

gpderetta 6y ago
I do not understand, why would there be a stack overflow? The "context" is saved (pushed) at the top of the suspended coroutine stack and restored (popped) when the coroutine is resumed (each coroutine has of course its own stack), so with a simple a->b->c->...->a cycle there is no issue. In fact given swap_context_ex, yielding to the next ready task in the scheduler (and queuing the current task at the end of the queue) is trivial [1]. To simplify the code and the boundary conditions, I maintain the invariant that the ready queue always has at least one coroutine (the 'idle' coroutine). Also note how the queue node is stack allocated directly on the suspended coroutine stack. [1] https://github.com/gpderetta/libtask/blob/master/task.cpp#L149 https://github.com/gpderetta/libtask/blob/master/task.cpp#L1... ; note that here 'swap_context_ex' is called 'callcc' as is conceptually very similar to scheme call-with-current-continuation. edit: of course if you are not careful with swap_context_ex and keep pushing new functions to execute on a context without them ever returning to the (recursively) previous context, you can run out of space, but I haven't found a case where this would happen in practice (not that I looked hard enough though).
- Veserv 6y ago
  Okay. I see. I did not realize you had separate stacks which would allow you to save on the caller stack before a switch to the callee stack. I was thinking you were nesting on a single stack like “stackless coroutines”. So if I am understanding correctly, essentially in your design each coroutine uses the end of its stack to push its context which can be trivially popped when you switch back to it and its stack.
  - gpderetta 6y ago
    yes, you understood correctly. The intuition here is that the rest of the callers saved registers are already saved by the compiler itself in the stack, you just need to complete the work. In fact, via GCC inline ASM, you can leave to the compiler the job of saving all registers and the swap routine doesn't have to touch memory at all [1] You can actually do it on a single stack though: when you detect a stack overflow, you traverse the stack and garbage collect no longer referenced stack frames (in practice you copy referenced stack frames to a new stack). The "small" catch is that your functions can no longer return and you need to commit to pure CPS, so this technique [2] is only used for some compilers-to-c for other languages with first class continuations. [1] https://github.com/gpderetta/delimited/blob/master/delimited.hpp#L264 https://github.com/gpderetta/delimited/blob/master/delimited... the idea is very simple, 99% of the complexity here is because I'm trying to transparently (i.e. with zero cost) propagate C++ exceptions across coroutines. [2] https://wiki.c2.com/?CheneyOnTheMta https://wiki.c2.com/?CheneyOnTheMta

by Veserv 6y ago

gpderetta 6y ago

I do not understand, why would there be a stack overflow? The "context" is saved (pushed) at the top of the suspended coroutine stack and restored (popped) when the coroutine is resumed (each coroutine has of course its own stack), so with a simple a->b->c->...->a cycle there is no issue. In fact given swap_context_ex, yielding to the next ready task in the scheduler (and queuing the current task at the end of the queue) is trivial [1]. To simplify the code and the boundary conditions, I maintain the invariant that the ready queue always has at least one coroutine (the 'idle' coroutine). Also note how the queue node is stack allocated directly on the suspended coroutine stack. [1] https://github.com/gpderetta/libtask/blob/master/task.cpp#L149 https://github.com/gpderetta/libtask/blob/master/task.cpp#L1... ; note that here 'swap_context_ex' is called 'callcc' as is conceptually very similar to scheme call-with-current-continuation. edit: of course if you are not careful with swap_context_ex and keep pushing new functions to execute on a context without them ever returning to the (recursively) previous context, you can run out of space, but I haven't found a case where this would happen in practice (not that I looked hard enough though).

Veserv 6y ago
Okay. I see. I did not realize you had separate stacks which would allow you to save on the caller stack before a switch to the callee stack. I was thinking you were nesting on a single stack like “stackless coroutines”. So if I am understanding correctly, essentially in your design each coroutine uses the end of its stack to push its context which can be trivially popped when you switch back to it and its stack.
- gpderetta 6y ago
  yes, you understood correctly. The intuition here is that the rest of the callers saved registers are already saved by the compiler itself in the stack, you just need to complete the work. In fact, via GCC inline ASM, you can leave to the compiler the job of saving all registers and the swap routine doesn't have to touch memory at all [1] You can actually do it on a single stack though: when you detect a stack overflow, you traverse the stack and garbage collect no longer referenced stack frames (in practice you copy referenced stack frames to a new stack). The "small" catch is that your functions can no longer return and you need to commit to pure CPS, so this technique [2] is only used for some compilers-to-c for other languages with first class continuations. [1] https://github.com/gpderetta/delimited/blob/master/delimited.hpp#L264 https://github.com/gpderetta/delimited/blob/master/delimited... the idea is very simple, 99% of the complexity here is because I'm trying to transparently (i.e. with zero cost) propagate C++ exceptions across coroutines. [2] https://wiki.c2.com/?CheneyOnTheMta https://wiki.c2.com/?CheneyOnTheMta