[LLVMdev] Proposal: stack/context switching within a thread

[Jeffrey Yasskin]

On Sun, Apr 11, 2010 at 2:41 PM, Kenneth Uildriks <kennethuil at gmail.com> wrote:
> On Sun, Apr 11, 2010 at 4:09 PM, Jeffrey Yasskin <jyasskin at google.com> wrote:
>> Kenneth Uildriks <kennethuil at gmail.com> wrote:
>>> 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.
>>
>> I guess the reason to interoperate with contexts from the C routines
>> would be to support ucontext_t's passed into signal handlers? But then
>> the LLVM intrinsics need to specify that their context's layout is the
>> same as ucontext_t's, on platforms where ucontext_t exists.
>
> Or perhaps it can be an argument to the target code generator, if
> there's any need to switch "compatibility mode" off and on.  All that
> the intrinsics require is that context creators be given
> a memory area of at least size llvm.context.size() to write contexts
> into, and that nothing besides the intrinsics mess with the context
> structure.

Yeah, that sounds right.

>>> 2. We should be able to support "hard switching" in Stackless Python
>>> by adding a llvm.getcontextstacktop intrinsic.  If, as in Kristján's
>>> example, llvm.getcontext is used to create context A, and then
>>> execution continues until context B is created with
>>> llvm.swapcontext(B, A), the region of memory between
>>> llvm.getcontextstacktop(A) and llvm.getcontextstacktop(B) can be saved
>>> and later restored when B is resumed.
>>
>> Wait, what stack top does swapcontext get? I'd thought that A's and
>> B's stack top would be the same since they're executing on the same
>> stack.
>
> No, A's stack top would be whatever the stack pointer was when
> llvm.getcontext was called to
> create it.  B's stack top would be whatever the stack pointer was when
> llvm.swapcontext was
> called to create it... it would be further from the common base than
> A's stack top.  The region
> between them is what needs to be restored before B can become active
> again, assuming that
> A's stack space remained valid.

Oops. Either I can't read, or I was confused by the fact that x86
stacks grow down. Probably the reading.

> I forgot to mention that this depends on the assumption that the
> function that created context A did not return to its caller before
> the llvm.swapcontext that created context B was executed.  And while
> I'm at it, what it the function that created context A made a tail
> call in the meantime?

Yep. The opengroup manpages are pretty bad about describing the limits
of setcontext():
http://www.opengroup.org/onlinepubs/007908775/xsh/getcontext.html.
Could you sketch out the restrictions in your document? They may be
identical to setjmp/longjmp, which opengroup does document:
http://www.opengroup.org/onlinepubs/007908775/xsh/longjmp.html.

> Me either. Stack copying, mmap'ing, slicing, or whatever should be
> done by the scheduler.  LLVM
> would not include any part of a scheduler, just intrinsics to allow a
> scheduler to create and switch contexts.

+1

> Anyway, I updated the document to take a lot of this discussion into
> account.  I hope that the assumptions I made actually are universally
> applicable in (non-split-stack-enabled) LLVM.

Thanks! Here are some thoughts on your additions. (just the "Stack
management" section, right?)

A working document like this may work better on a wiki, in
http://codereview.appspot.com, or in a public repository rather than
as a series of email attachments. :)

"The context will not carry any information about the maximum stack
space available to it" <- and this is the only line that would need to
change to add split stacks, I think.

"1. A function call will ..." -> "1. A non-tail function call will ..."  ?

Item 3 starts referring to "active" and "inactive" contexts, but I
don't think you've introduced the terms.

The opengroup manpages of swapcontext() and friends don't mention
whether it's possible to use them to move a context from one thread to
another. *sigh*. I suspect it works fine, but there's a chance it does
the wrong thing to thread-local variables. Could you add that as an
open question? It'd be nice for LLVM to allow it.

Point 4 is a bit confusing. Normally, it's fine for a thread to share
some of its stack space with another thread, but your wording seems to
prohibit that.

I'll forward your next draft back to the stackless folks, unless you
want to pick up the thread with them.

Thanks,
Jeffrey