[Stackless] LLVM coroutine support [was: [LLVMdev] Proposal: stack/context switching within a thread]

[Kristján Valur Jónsson]

Hello Jeffrey.
This is very interesting.  I am not familiar with the C apis that this appears to emulate.  The concept of a "linked" context is novel to me.

One thing that is not immediately is apparent to me is if this system does not support "stack slicing".
I see the "makecontext"  This has some problems:
1) You have to know beforehand how much stack you will use
2) You Therefore have to allocate conservatively.
3) This generous amount of preallocated memory that remains fixed for the lifetime of the context causes memory fragmentation, similar to what you see with regular threads.  This limits the number of contexts that can be alive by virtual memory in the same way as the number of threads are limited.

In stackless python, we use "stack slicing".  If you are not familiar with the concept, it involves always using the same C stack, which therefore can grow, and storing the "active" part of the stack away into heap memory when contexts are switched.  An inactive context therefore has not only cpu registers associated with it, but also slice of the stack (as little as required to represent that particular context) tucked away into a heap memory block.

It is unclear to me if a context created by "getcontext" could be used as a base point for stack slicing.
Could one create such a base point (ctxt A), and then decend deeper into the stack, then "swapcontext" from a nex context B back to the previous point on the stack?  Will the stack data in the between points A and B on the stack be "tucked away", to be restored when returning to context B?

When doing stack slicing, one has to define a "base", and in the exaple above, context A would be the base, and all other contexts would have to be from deeper on the stack.  I don't see a provision for identifying such a base.  And indeed, if some of the contexts come from a separate "makecontext" area, they would have a different base.

If stack slicing is not supported, as I suspect, it would be relatively simple to add it by being able to specify a "base context" to "getcontext" and "swapcontext", which would serve the base point on the stack between which and the current stack position, memory would need to be saved.  The contexts thus generated would have an associated stack slice with them.

Adding such a "base context" argument go getcontext() and swapcontext() would enable us to build current stackless behaviour on top of such an API.


Just to add weight to my argument:  My company runs internet servers using stackless python, each of which runs a single stackless python process handling 30.000 TCP connections.  Each connection's stack, when not active, is tucked away in a tight malloc´d block when it is not in use.  Having 30.000 preallocated, reatively large, stacks present at fixed positions in virtual memory for the duration of the process would be impossible in 32 bits.

Cheers,

Kristján

> -----Original Message-----
> From: stackless-bounces at stackless.com [mailto:stackless-
> bounces at stackless.com] On Behalf Of Jeffrey Yasskin
> Sent: 8. apríl 2010 00:30
> To: stackless at stackless.com
> Subject: [Stackless] LLVM coroutine support [was: [LLVMdev] Proposal:
> stack/context switching within a thread]
> 
> Hi Stackless folks,
> 
> The following message was recently sent to the LLVM developers list
> proposing to add primitives along the lines of the posix makecontext
> and swapcontext functions. Since you guys have implemented coroutines
> (in assembly if I'm remembering right), you have much more expertise
> about this than I do. I'd like to make sure that LLVM supports your
> needs in case you want to support jitted code, so could some of you
> look over this to see if it does what you need? If there's anything
> broken about it, you can either reply to llvmdev at cs.uiuc.edu or send me
> comments and I'll forward them.
> 
> Thanks,
> Jeffrey
> 
> 
> ---------- Forwarded message ----------
> From: Kenneth Uildriks <kennethuil at gmail.com>
> Date: Wed, Apr 7, 2010 at 12:14 PM
> Subject: [LLVMdev] Proposal: stack/context switching within a thread
> To: LLVM Developers Mailing List <llvmdev at cs.uiuc.edu>
> 
> 
> Right now the functionality is available, sometimes, from the C
> standard library.  But embedded environments (often running a limited
> standard library) and server environments would benefit heavily from a
> standard way to specify context switches within a single thread in the
> style of makecontext/swapcontext/setcontext, and built-in support for
> these operations would also open the way for optimizers to begin
> handling these execution paths.
> 
> The use cases for these operations, and things like coroutines built on
> top of them, will only increase in the future as developers look for
> ways to get more concurrency while limiting the number of high-overhead
> and difficult to manage native threads, locks, and mutexes.
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev