llvm dev - Apr 2010 - [LLVMdev] Proposal: stack/context switching within a thread

On Sat, Apr 10, 2010 at 12:54 PM, Jeffrey Yasskin <jyasskin at google.com>
wrote:
> I took the liberty of forwarding this to the Stackless Python list,
> since they switch stacks, and I got a response at
> http://thread.gmane.org/gmane.comp.python.stackless/4464/focus=4467.
> The upshot is that they really need the ability to allocate only a
> tiny amount of space for each thread and grow that as the thread
> actually uses more stack. The way they accomplish that now is by
> copying the entire stack to the heap on a context switch, and having
> all threads share the main C stack. This isn't quite as bad as it
> sounds because it only happens to threads that call into C extension
> modules. Pure Python threads operate entirely within heap Python
> frames. Still, it would be nice to support this use case.
>
> Kenneth, I don't want to insist that the first version of this be both
> a floor wax _and_ a dessert topping, but is there a natural extension
> to supporting what Stackless needs that we could add later? It looks
> like swapcontext() simply repoints the stack pointer and restores the
> registers, while Stackless wants it to be able to allocate memory and
> copy the stack. Maybe that implies a "mode" argument?
>
> Alternately, Stackless could probably work with a segmented stack
> mechanism like Ian Taylor implemented in gcc for Go. Do you see
> anything that would prevent us from layering segmented stacks on top
> of this context switching mechanism later?
>
> Thanks,
> Jeffrey
As I see it, the context switching mechanism itself needs to know
where to point the stack register when switching.  The C routines take
an initial stack pointer when creating the context, and keep track of
it from there.  If we don't actually need to interoperate with
contexts created from the C routines, we have a lot more freedom.

Anyway, one approach would be to expose intrinsics to interrogate an
inactive context, to get its initial stack pointer (the one it was
created with) and its current stack pointer, and also  to modify both
before making the context active again.

I don't see any reason why this scheme wouldn't also be compatible
with segmented stacks.  In fact, one could segment an inactive context
stack at any time rather than copying the whole thing, as long as you
can assume that there aren't any pointers into the context's stack
living outside the context.

>  In fact, one could segment an inactive context
> stack at any time rather than copying the whole thing, as long as you
> can assume that there aren't any pointers into the context's stack
> living outside the context.
>
Never mind that... stacks by default don't have back pointers to
previous stack frames.  We'd still need runtime support apart from the
context switching bit, and without such support we'd have to copy the
whole stack.

On the other hand, stack manipulation really ought to be handled by
the target, since only the target knows the details of how the stack
is laid out to begin with.  Also, if we have stack manipulation calls
in the IR, optimization quickly becomes very difficult.  Unless we
just allow optimizers to ignore the stack manipulations and assume
they're doing the "right" thing.

On the gripping hand, we don't want the target emitting memory
allocation calls in order to grow the stack (unless a function pointer
to malloc or its equivalent is passed in from the IR).
> The way they accomplish that now is by
> copying the entire stack to the heap on a context switch, and having
> all threads share the main C stack. This isn't quite as bad as it
> sounds because it only happens to threads that call into C extension
> modules. Pure Python threads operate entirely within heap Python
> frames. Still, it would be nice to support this use case.
This wouldn't hold in IR, since virtual registers regularly get
spilled to the stack.. every context, regardless of the language,
would have to have its stack saved.  Also, this method would mean that
a context cannot be used in any native thread other than the one that
created it, right?