Jeffrey Yasskin
2010-Apr-12 05:07 UTC
[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(): 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: 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 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
Kenneth Uildriks
2010-Apr-12 13:15 UTC
[LLVMdev] Proposal: stack/context switching within a thread
I created a wiki at 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.
Jeffrey Yasskin
2010-Apr-12 16:21 UTC
[LLVMdev] Proposal: stack/context switching within a thread
On Mon, Apr 12, 2010 at 6:15 AM, Kenneth Uildriks <kennethuil at gmail.com> wrote:> I created a wiki at 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.
Jeffrey Yasskin
2010-Apr-17 02:30 UTC
[LLVMdev] Proposal: stack/context switching within a thread
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: 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
Kenneth Uildriks
2010-Apr-21 00:47 UTC
[LLVMdev] Proposal: stack/context switching within a thread
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: 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.
Reasonably Related Threads
- [LLVMdev] Proposal: stack/context switching within a thread
- [LLVMdev] Proposal: stack/context switching within a thread
- [LLVMdev] Proposal: stack/context switching within a thread
- [LLVMdev] Proposal: stack/context switching within a thread
- [LLVMdev] Proposal: stack/context switching within a thread