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

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

I created a wiki at http://code.google.com/p/llvm-stack-switch/

Right now I just copied and formatted the document as-is... I'll go
back over it with your comments in mind soon.  One more question,
which you can answer here or there:
> 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.
Really?  How does that work?
>
> I'll forward your next draft back to the stackless folks, unless you
> want to pick up the thread with them.
If you're willing to be the go-between, I really appreciate it..  I
don't think I have the time to really get involved with Stackless
Python, especially as I would have to learn regular Python first.

On Mon, Apr 12, 2010 at 6:15 AM, Kenneth Uildriks <kennethuil at
gmail.com> wrote:
> I created a wiki at http://code.google.com/p/llvm-stack-switch/
>
> Right now I just copied and formatted the document as-is... I'll go
> back over it with your comments in mind soon.  One more question,
> which you can answer here or there:
>
>> 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.
>
> Really?  How does that work?
void thread1() {
  Foo shared_var;
  queue.send(&shared_var);
  int result = otherqueue.recv();
  return;
}

void thread2() {
  Foo* shared_var = queue.recv();
  otherqueue.send(work_on(shared_var));
}

is legal with posix threads. It's just illegal to return out of a
function while its stack space is used by another thread. I've seen
this used inside a condition variable implementation, among other
places.
>> I'll forward your next draft back to the stackless folks, unless
you
>> want to pick up the thread with them.
>
> If you're willing to be the go-between, I really appreciate it..  I
> don't think I have the time to really get involved with Stackless
> Python, especially as I would have to learn regular Python first.
Sure.

On Sun, Apr 11, 2010 at 10:07 PM, Jeffrey Yasskin <jyasskin at google.com>
wrote:
> I'll forward your next draft back to the stackless folks, unless you
> want to pick up the thread with them.
Their reply: http://thread.gmane.org/gmane.comp.python.stackless/4464/focus=4475

Instead of @llvm.getcontextstacktop(%context), they want
@llvm.getcurrentstacktop() so that they can copy the stack out before
switching, and copy it back in after switching. I'm not sure this
exactly works either, since before "copying the stack back", any
allocas are pointing at old-frame data and so are invalid. They'd need
to guarantee that any relevant data is in machine registers rather
than the stack during the switch, but LLVM doesn't provide a way to do
that. The cleaner way to do this is to switch to an intermediate stack
scheduler context with its own stack, have it replace the stacks, and
then switch to the target context back on the original stack. But that
requires two swapcontext() calls, which seems less than idea
performance-wise.

Since the backend _can_ ensure that the relevant data is in machine
registers, do you think it makes sense to provide a swapcontext() that
also moves the stack? Or is there another way to do this that I'm
missing?

Jeffrey

On Fri, Apr 16, 2010 at 9:30 PM, Jeffrey Yasskin <jyasskin at google.com>
wrote:
> On Sun, Apr 11, 2010 at 10:07 PM, Jeffrey Yasskin <jyasskin at
google.com> wrote:
>> I'll forward your next draft back to the stackless folks, unless
you
>> want to pick up the thread with them.
>
> Their reply:
http://thread.gmane.org/gmane.comp.python.stackless/4464/focus=4475
(From the reply)
> But any function call we perform after the
> swapcontext() may trample the unsaved stack, if the source and destination
stack positions
> overlap.
I'm having trouble visualizing that situation.  Is there a "main"
context that will handle all this saving and restoring of stacks?  If
so, does it actually share stacks with other contexts in the way
they're expected to share it with each other?
>
> Instead of @llvm.getcontextstacktop(%context), they want
> @llvm.getcurrentstacktop() so that they can copy the stack out before
> switching, and copy it back in after switching. I'm not sure this
> exactly works either, since before "copying the stack back", any
> allocas are pointing at old-frame data and so are invalid. They'd need
> to guarantee that any relevant data is in machine registers rather
> than the stack during the switch, but LLVM doesn't provide a way to do
> that. The cleaner way to do this is to switch to an intermediate stack
> scheduler context with its own stack, have it replace the stacks, and
> then switch to the target context back on the original stack. But that
> requires two swapcontext() calls, which seems less than idea
> performance-wise.
OK, I see you don't want to have a "main" context that does this
and
dispatches other contexts if it can be avoided.  Compared to copying
stacks, though, I'm not sure that two swapcontexts will be that bad,
especially if we don't implement them as posix library function calls.
>
> Since the backend _can_ ensure that the relevant data is in machine
> registers, do you think it makes sense to provide a swapcontext() that
> also moves the stack? Or is there another way to do this that I'm
> missing?
Can it really ensure that on all targets?  Some of them don't exactly
have an abundance of registers.