3 ms·
I love coroutines and have written a few implementations myself. A few comments: Don't have separate get and set_context. They are hard to understand and use (
by gpderetta 6y ago
I love coroutines and have written a few implementations myself. A few comments:
Don't have separate get and set_context. They are hard to understand and use (see the volatile x) and are suboptimal, a swap_context is better.
With this change, you do not need to store the callee save registers in the context, you can save them on the top of the stack directly, including ip. The pointer to context is just a pointer to the top of stack of the suspended context (there is no actual Context object).
The perfect primitives are:
// switch to 'to'. Returns another context on return, possibly,
// but not necessarily 'from', also possibly null.
// This is an optimization as the next funciton is enough
ctx* swap_context(ctx * to);
// same as swap_context, but execute fn in the 'to' context, before
// returning from swap_context. 'fn' takes a pointer to the newly suspended
// calling context and closure is passed through.
// The function should return a context (possible 'from') or nullptr.
ctx* swap_context_ex(ctx* to, ctx* (*fn)(ctx*, void*), void* closure);
// create an empty context with an allocated stack. swapping to it will deallocate
// the stack and terminate the context. use swap_context_ex to actually assign a
// function to run on the the context
ctx* make_empty_context();
edit: the bits in the article about improving the gdb and *san experience are great and it something I wasn't aware!
- Veserv 6y agoIf 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 agoI 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 agoOkay. 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 agoyes, 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
- gpderetta 6y agoOh, I forgot, you also probably want to be able to pass a a pointer sized argument to the next coroutine (and get one back); In the previous prototypes, convert all uses of 'ctx * ' to plain 'ctx', where ctx is: struct ctx { void * sp;, void * payload; }; If you get things just right, at least on linux, you can get ctx to always be passed and returned via registers. edit: HN ate my asterisks.
- artemonster 6y agoI suppose the „fn“ executed in „to“ context before return is executed to do some clean-up or de-allocations for caller? I.e. to make a proper „return“ possible? Could you explain this maybe in more detail? And which closure is passed?
- gpderetta 6y agoIt is a more principled replacement for the get_context, set_context pair. And more powerful vecause it is run inside the to coroutine, so the coroutine that called swap is already suspended. Things you can do from the closure: - delete the 'from' coroutine - return into the 'to' coroutine a different coroutine than 'from' (or even bo coroutine at all). This is useful to implement blocking primitives amd schedulers. - throw an exception into the to coroutine (for example for exception forwarding or even just to force the target coroutine to exit) And much more of course. It is a very powerful primitive analogous to call-with-current-continuation.
- artemonster 6y agoThanks for the explanation!