4 ms·

Coroutines in C with Arbitrary Arguments

62 points by rumcajz 12y ago

david-given 12y ago
That is majestically vile. It took me a while before I figured out how it was assigning the new coroutine's stack pointer, and then I was filled with admiration and a little nausea. I'm not sure if this will work in real life; it looks like it's relying heavily on C compiler magic to ensure that the stack's laid out the way it wants. (Plus, allocating stacks with malloc() doesn't work on some architectures, and I have encountered pthreads implementations that get very unhappy if you change stacks on them). But it's still a deeply impressive piece of lateral thinking.
- ehmmm 12y ago
  Can you elaborate on that. It doesn't seem to work correctly on my machine. Writing beyond heap bounds and uninitialized reads.
  - rumcajz 12y ago
    It uses dynamically allocated array (char filler_[...]) to shift stack pointer to arbitrary memory address. If it doesn't work with your compiler you may try to use alloca() instead.
    - ehmmm 12y ago
      Oh I see, it moves the stack pointer so it coincides with the heap allocated memory? I like articles that combine hacking and C, but this one really needs more explanation.
      - rumcajz 12y ago
        This article is really about the arguments to the coroutine. The original idea for shifting the stack pointer comes from here: http://fanf.livejournal.com/105413.html http://fanf.livejournal.com/105413.html
    - thechao 12y ago
      Here's my implementation in c++, using alloca(): https://github.com/jaroslov/coro https://github.com/jaroslov/coro. Without debugger support, coroutines are pretty difficult to work with.
- userbinator 12y ago
  It should be possible to do this without malloc(), by allocating the co-stack as an array within the current stack. Something like this... char stack[STACK_SIZE]; int anchor_[unoptimisable_]; char filler_[(char*)&anchor_ - (char*)(stack + STACK_SIZE)]; ... (Haven't tested it, but it's basically the same principle. The same caveats about stack layout and VLAs apply.)
  - rumcajz 12y ago
    Except that if the parent function terminated before the coroutine it have launched, you would get memory overwrites.
  - mtanski 12y ago
    You would also need to align the stack per. target requirements (gcc keyword, or offset the address). The aliment guarantees for char[] placed on stack are probably insufficient for many machines.
    - userbinator 12y ago
      If none of the variables on the stack are smaller than your desired alignment size, and the stack starts out aligned (which it should), then it will remain aligned.
- mtanski 12y ago
  The code in question strikes me as being a proof of concept. Obviously, a more complete implementation would be more complex. In the real world you'd create a stack with mmap with the MMAP_STACK flag. You would ensure the stack is property aligned and make sure there's a guard page at the end of it.
amelius 12y ago
Would it be possible to make a coroutine implementation that allows the stacks to grow dynamically? (If there are N coroutines, you will need N stacks, so for large N it does not suffice to have a statically conservatively preallocated stack for each coroutine). Also, how is Rust's support for coroutines?
- errordeveloper 12y ago
  I have recently found this: https://github.com/rustcc/coroutine-rs https://github.com/rustcc/coroutine-rs
  - amelius 12y ago
    Interesting, but the documentation does not seem to describe how stacks/memory management is done.
    - keeperofdakeys 12y ago
      From a quick look at the code, it seems to use segmented stacks with memory mapping. https://github.com/rustcc/coroutine-rs/blob/master/src/stack.rs https://github.com/rustcc/coroutine-rs/blob/master/src/stack...
- rumcajz 12y ago
  There's -fsplit-stack option in gcc IIRC.
aninteger 12y ago
Semi off topic, but are there examples of coroutine usage in any relatively popular open source C or C++ code bases? The only thing that comes to mind is the MAME and MESS code bases (I could be wrong here). We see coroutine articles on HN from time to time but I've always wondered who or what software out there are using these types of techniques.
- userbinator 12y ago
  QEMU is another one that I know of: http://blog.vmsplice.net/2014/01/coroutines-in-qemu-basics.html http://blog.vmsplice.net/2014/01/coroutines-in-qemu-basics.h... Coroutines seem like the type of concept that relatively few programmers understand and use, but when they are used well, it can simplify the code flow greatly.
  - pm215 12y ago
    Speaking as a QEMU developer, I really don't like the coroutine use. They're a portability mess, they tend to expose bugs in dusty corners of the compiler, and they can be painful to debug around. I would much rather take a view that C is simply not a language with coroutines in it, and not try to retrofit them without explicit support from the compiler and runtime...
- jhallenworld 12y ago
  There is a branch of JOE which uses co-routines: http://sourceforge.net/p/joe-editor/mercurial/ci/default/tree/docs/hacking.md http://sourceforge.net/p/joe-editor/mercurial/ci/default/tre... The main release doesn't use them yet, but the Windows port does. My co-routine library also allows arbitrary arguments, but it just uses va_list for this. Also I use setjmp/longjump and stack allocations (if ucontext is not available), but do not depend on c99 dynamic arrays to do it. BTW, the array trick doesn't work on some architectures: IA64 (there are two stacks) or Cray (the stack is a linked-list).
- Pfiffer 12y ago
  The lwan webserver uses them: http://tia.mat.br/blog/html/2012/09/29/asynchronous_i_o_in_c_with_coroutines.html http://tia.mat.br/blog/html/2012/09/29/asynchronous_i_o_in_c...

62 points by rumcajz 12y ago

That is majestically vile. It took me a while before I figured out how it was assigning the new coroutine's stack pointer, and then I was filled with admiration and a little nausea. I'm not sure if this will work in real life; it looks like it's relying heavily on C compiler magic to ensure that the stack's laid out the way it wants. (Plus, allocating stacks with malloc() doesn't work on some architectures, and I have encountered pthreads implementations that get very unhappy if you change stacks on them). But it's still a deeply impressive piece of lateral thinking.

ehmmm 12y ago
Can you elaborate on that. It doesn't seem to work correctly on my machine. Writing beyond heap bounds and uninitialized reads.
- rumcajz 12y ago
  It uses dynamically allocated array (char filler_[...]) to shift stack pointer to arbitrary memory address. If it doesn't work with your compiler you may try to use alloca() instead.
  - ehmmm 12y ago
    Oh I see, it moves the stack pointer so it coincides with the heap allocated memory? I like articles that combine hacking and C, but this one really needs more explanation.
    - rumcajz 12y ago
      This article is really about the arguments to the coroutine. The original idea for shifting the stack pointer comes from here: http://fanf.livejournal.com/105413.html http://fanf.livejournal.com/105413.html
  - thechao 12y ago
    Here's my implementation in c++, using alloca(): https://github.com/jaroslov/coro https://github.com/jaroslov/coro. Without debugger support, coroutines are pretty difficult to work with.
userbinator 12y ago
It should be possible to do this without malloc(), by allocating the co-stack as an array within the current stack. Something like this... char stack[STACK_SIZE]; int anchor_[unoptimisable_]; char filler_[(char*)&anchor_ - (char*)(stack + STACK_SIZE)]; ... (Haven't tested it, but it's basically the same principle. The same caveats about stack layout and VLAs apply.)
- rumcajz 12y ago
  Except that if the parent function terminated before the coroutine it have launched, you would get memory overwrites.
- mtanski 12y ago
  You would also need to align the stack per. target requirements (gcc keyword, or offset the address). The aliment guarantees for char[] placed on stack are probably insufficient for many machines.
  - userbinator 12y ago
    If none of the variables on the stack are smaller than your desired alignment size, and the stack starts out aligned (which it should), then it will remain aligned.
mtanski 12y ago
The code in question strikes me as being a proof of concept. Obviously, a more complete implementation would be more complex. In the real world you'd create a stack with mmap with the MMAP_STACK flag. You would ensure the stack is property aligned and make sure there's a guard page at the end of it.

amelius 12y ago

Would it be possible to make a coroutine implementation that allows the stacks to grow dynamically? (If there are N coroutines, you will need N stacks, so for large N it does not suffice to have a statically conservatively preallocated stack for each coroutine). Also, how is Rust's support for coroutines?

errordeveloper 12y ago
I have recently found this: https://github.com/rustcc/coroutine-rs https://github.com/rustcc/coroutine-rs
- amelius 12y ago
  Interesting, but the documentation does not seem to describe how stacks/memory management is done.
  - keeperofdakeys 12y ago
    From a quick look at the code, it seems to use segmented stacks with memory mapping. https://github.com/rustcc/coroutine-rs/blob/master/src/stack.rs https://github.com/rustcc/coroutine-rs/blob/master/src/stack...
rumcajz 12y ago
There's -fsplit-stack option in gcc IIRC.

aninteger 12y ago

Semi off topic, but are there examples of coroutine usage in any relatively popular open source C or C++ code bases? The only thing that comes to mind is the MAME and MESS code bases (I could be wrong here). We see coroutine articles on HN from time to time but I've always wondered who or what software out there are using these types of techniques.

userbinator 12y ago
QEMU is another one that I know of: http://blog.vmsplice.net/2014/01/coroutines-in-qemu-basics.html http://blog.vmsplice.net/2014/01/coroutines-in-qemu-basics.h... Coroutines seem like the type of concept that relatively few programmers understand and use, but when they are used well, it can simplify the code flow greatly.
- pm215 12y ago
  Speaking as a QEMU developer, I really don't like the coroutine use. They're a portability mess, they tend to expose bugs in dusty corners of the compiler, and they can be painful to debug around. I would much rather take a view that C is simply not a language with coroutines in it, and not try to retrofit them without explicit support from the compiler and runtime...
jhallenworld 12y ago
There is a branch of JOE which uses co-routines: http://sourceforge.net/p/joe-editor/mercurial/ci/default/tree/docs/hacking.md http://sourceforge.net/p/joe-editor/mercurial/ci/default/tre... The main release doesn't use them yet, but the Windows port does. My co-routine library also allows arbitrary arguments, but it just uses va_list for this. Also I use setjmp/longjump and stack allocations (if ucontext is not available), but do not depend on c99 dynamic arrays to do it. BTW, the array trick doesn't work on some architectures: IA64 (there are two stacks) or Cray (the stack is a linked-list).
Pfiffer 12y ago
The lwan webserver uses them: http://tia.mat.br/blog/html/2012/09/29/asynchronous_i_o_in_c_with_coroutines.html http://tia.mat.br/blog/html/2012/09/29/asynchronous_i_o_in_c...