jfjr@mbunix.mitre.org (Freedman) (05/20/91)
I posted this earlier but we were having site problems. If this is
redundant I am sorry.
I need to know about implementing threads or lightweight processes
without modifying kernel - ie strictly user level implementations.
How is this accomplished? Some variant on setjmp/longjmp?
Can someone give me pointers into literature? Code?
Jerry Freedman,Jrmouse@thunder.mcrcim.mcgill.edu (der Mouse) (05/26/91)
In article <1991May20.123423.10388@linus.mitre.org>, jfjr@mbunix.mitre.org (Freedman) writes: > I need to know about implementing threads or lightweight processes > without modifying kernel - ie strictly user level implementations. > How is this accomplished? Some variant on setjmp/longjmp? Machine-dependent, perhaps even operating-system-dependent. I did it once for 4.3 on a VAX, using SIGALRM to context-switch. The implementation depended on knowing some of the internal details of signal delivery; if I had to do it again I think I'd go about it differently. (For one thing, my implementation had no way for a thread to voluntarily give up the rest of its timeslice....) Obviously, you will have the problem that any thread blocking in a syscall blocks all other threads as well. This may or may not actually cause you headaches. If you can build a context switcher, you're most of the way there. In fact, if you don't want to ever trigger a context switch from a signal, that's about all you need. Dealing with signals can be, errr, fun.... der Mouse old: mcgill-vision!mouse new: mouse@larry.mcrcim.mcgill.edu
richard@aiai.ed.ac.uk (Richard Tobin) (05/27/91)
In article <1991May20.123423.10388@linus.mitre.org> jfjr@mbunix.mitre.org (Freedman) writes: > I need to know about implementing threads or lightweight processes >without modifying kernel - ie strictly user level implementations. >How is this accomplished? Some variant on setjmp/longjmp? Setjmp() and longjmp() may do the trick, but it's extremely unportable. Once you have n stacks, you may be able to longjmp() between them. If this works, you still have the problem of getting onto a new stack in the first place. Under BSD-like systems you may be able to use a completely disgusting hack due I think to Simon Brown, which involves using sigstack() to set up an alternative stack for signal handlers, and then sending yourself a signal. Here's some code from a Lisp system: #include "defs.h" #include "structs.h" #include <stdio.h> #include <signal.h> #include <setjmp.h> typedef void Sigtype; static jmp_buf newenv, oldenv; static LispObject *(*threadfunction)(); static Sigtype threadstart() { if(_setjmp(newenv) == 0) longjmp(oldenv, 1); (void)(*threadfunction)(); /* If we get here, the thread has returned too far. */ fprintf(stderr, "Panic! Thread returned too far!\n"); exit(1); } void create_thread(thread, fn) struct thread_structure *thread; LispObject *(*fn)(); { struct sigstack stack, ostack; struct sigvec vec, ovec; stack.ss_sp = (char *)(((int)thread->stack + thread->size - 1) & ~7); stack.ss_onstack = 0; sigstack(&stack, &ostack); vec.sv_handler = threadstart; vec.sv_mask = 0; vec.sv_flags = SV_ONSTACK; sigvec(SIGUSR1, &vec, &ovec); if(setjmp(oldenv) == 0) { kill(getpid(), SIGUSR1); /* We never get here, because threadstart longjmps */ } /* * At this point, threadstart has done a setjmp(newenv). When * we jump to it, it will call the function in threadfunction. */ sigvec(SIGUSR1, &ovec, (struct sigvec *)0); sigstack(&ostack, (struct sigstack *)0); threadfunction = fn; _longjmp(newenv, 1); } -- Richard -- Richard Tobin, JANET: R.Tobin@uk.ac.ed AI Applications Institute, ARPA: R.Tobin%uk.ac.ed@nsfnet-relay.ac.uk Edinburgh University. UUCP: ...!ukc!ed.ac.uk!R.Tobin
libes@cme.nist.gov (Don Libes) (05/28/91)
In article <4815@skye.ed.ac.uk> richard@aiai.UUCP (Richard Tobin) writes: >> I need to know about implementing threads or lightweight processes >>without modifying kernel - ie strictly user level implementations. >[Setjmp/longjmp work, but] you still have the problem of getting >onto a new stack in the first place. Under BSD-like systems you may >be able to use a completely disgusting hack due I think to Simon >Brown, which involves using sigstack() to set up an alternative >stack for signal handlers, and then sending yourself a signal. As long as you're assigning credit, in the July '87 ;login:, I described this technique, complete with preemptive scheduling all in user code. The paper was heavily circulated in '86, and while I don't know of an earlier published description, I suspect that whoever designed the BSD signal mechanism did so for exactly this purpose. (Otherwise, the presence of some of the signal features are rather inexplicable.) If they didn't ever create user-level LWPs, they should at least get credit for making it possible. Don Libes libes@cme.nist.gov ...!uunet!cme-durer!libes
torek@elf.ee.lbl.gov (Chris Torek) (05/28/91)
In article <4815@skye.ed.ac.uk> richard@aiai.UUCP (Richard Tobin) writes: >... Once you have n stacks, you may be able to longjmp() between them. And then again, you may not.... Longjmp is only defined for going `up' the stack, and can (and does) abort programs that attempt to use it in the `wrong' direction. When you have two separate stacks and attempt to jump from one to the other, you are going neither up nor down, but the `<' comparison done internally gives an answer anyway (which answer it gives depends on the relative addresses of the two separate stacks) and thus implementations that check (such as 4.xBSD-on-a-VAX) may stop your code dead, rather than changing stacks. It is not impossible to implement this, but it *is* heavily machine dependent. Chances are you will get the best results not by trying longjmp(), but rather by reading up on the machine's calling conventions, the O/S's user stack conventions, and the machine architecture, and writing the context switch code only once you understand all of these. It is probably best to continue to avoid setjmp/longjmp as their specifications have changed in the past, suggesting that they may change again in the future. (Richard Tobin, I note, used _longjmp. This is what used to be called longjmp. POSIX now has sigsetjmp, apparently. In other words, this is dangerous territory. You should know exactly what you are doing, or you will step on a land mine.) -- In-Real-Life: Chris Torek, Lawrence Berkeley Lab CSE/EE (+1 415 486 5427) Berkeley, CA Domain: torek@ee.lbl.gov
simon@castle.ed.ac.uk (Simon Brown) (05/31/91)
In article <13598@dog.ee.lbl.gov> torek@elf.ee.lbl.gov (Chris Torek) writes: >In article <4815@skye.ed.ac.uk> richard@aiai.UUCP (Richard Tobin) writes: >>... Once you have n stacks, you may be able to longjmp() between them. > >And then again, you may not.... Longjmp is only defined for going `up' >the stack, and can (and does) abort programs that attempt to use it in >the `wrong' direction. When you have two separate stacks and attempt >to jump from one to the other, you are going neither up nor down, but >the `<' comparison done internally gives an answer anyway (which answer >it gives depends on the relative addresses of the two separate stacks) >and thus implementations that check (such as 4.xBSD-on-a-VAX) may stop >your code dead, rather than changing stacks. Indeed. However, all is not lost (except your lunch :-)). The problem is that you can't jump down the stack, so the obvious answer is to make sure that you always jump up. So, to jump from one state to another, you have to arrange to temporarily execute on some stack that is lower than *any* of the thread stacks, and you have to get there without using longjmp. And this can be done by a signal trap (with sigstack set to use this lowest stack), from which one does the longjmp, rather than jumping directly. It gets a bit nasty, though. In particular, you have to find some way of ensuring that this trampoline stack is lower than any other stack. I did this (on an IBM RS/6000, which also does longjmp sanity checking) by arranging for all the the thread stacks to be created by malloc, whereas the trampoline stack is declared static - but of course this isn't particularly portable. You also have to remember to clear the sigstack bit in the signal context, so that the signal isn't blocked while you're executing in the thread. Some example code: static Thread lwp_schedjmp; /* scheduler master state */ static Thread *lwp_curjmp; /* ptr to place we're trying to jump to */ static char spring_stack[SPRING_STACK_SIZE]; /* trampoline stack */ static void springboard (int); /* * reschedule some thread */ void thread_reschedule (Thread *thread) { struct sigstack sstk; struct sigvec svec; if (setjmp(lwp_schedjmp.thread) == 0) { /* * we want to jump down to the appropriate stack, but longjmp * won't let us do this directly. we can do it indirectly by * going via a signal handler which is being handled on a * stack which is even lower in memory than the required * lightweight stack. thus, once we're in the signal handler, * we'll be allowed to longjmp to where we want to be. */ /* take a non-auto copy of where we want to go */ lwp_curjmp = thread; /* arrange to trap USR1 on a very low stack */ svec.sv_handler = springboard; svec.sv_mask = 0; svec.sv_flags = SV_ONSTACK; sstk.ss_sp = spring_stack + SPRING_STACK_SIZE; sstk.ss_onstack = 0; sigstack(&sstk, (struct sigstack *)0); sigvec(SIGUSR1, &svec, (struct sigvec *)0); /* raise USR1 which will cause a jump to the thread */ kill(getpid(), SIGUSR1); } } /* * signal handler for indirect thread reschedule */ static void springboard (int signo) { struct sigstack state; /* get rid of sigstack context */ if (sigstack((struct sigstack *)0, &state) == 0) { state.ss_onstack = 0; sigstack(&state, (struct sigstack *)0); } /* jump */ longjmp(lwp_curjmp->thread, 1); } But this is pretty slow, as it needs to handle a signal on each reschedule. And pretty disgusting too, come to think of it. >It is probably best to continue to avoid setjmp/longjmp as their specifications >have changed in the past, suggesting that they may change again in the >future. Such as a change which causes longjmp to destructively unwind the stack, say. (I seem to have a vague clouded memory that the V7 longjmp did this? Or maybe it was 4.1BSD) ------------------------------------------------------------------------------- Simon Brown simon@meiko.co.uk Meiko Scientific Ltd. simon@ed.ac.uk
torek@elf.ee.lbl.gov (Chris Torek) (06/02/91)
In article <10728@castle.ed.ac.uk> simon@castle.ed.ac.uk (Simon Brown) writes: [an involved method for guaranteeing up-stack-jumps] >But this is pretty slow, as it needs to handle a signal on each reschedule. >And pretty disgusting too, come to think of it. Indeed. :-) >Such as a change which causes longjmp to destructively unwind the stack, say. >(I seem to have a vague clouded memory that the V7 longjmp did this? Or maybe >it was 4.1BSD) 4BSD VAX longjmps have done this for some time. It correctly restores the values of registers, so that register int f = 0; (void) setjmp(label); printf("%d\n", ++f); longjmp(label, 1); prints 1 2 3 . . . Many `typical' implementations print 1 1 1 . . . The BSD Vax unwind looks essentially like this: while (fp != desired frame) { if (we are above the desired frame) { write(2, "longjmp botch\n", 14); dump core; } stuff our own address into the return pc; ``return''; } and hence if you have mucked with the stack, and the frames are not in a single chain leading to the top, you will lose out. The BSD tahoe unwind is almost identical. -- In-Real-Life: Chris Torek, Lawrence Berkeley Lab CSE/EE (+1 415 486 5427) Berkeley, CA Domain: torek@ee.lbl.gov
hansen@pegasus.att.com (Tony L. Hansen) (06/08/91)
< From: torek@elf.ee.lbl.gov (Chris Torek)
< In article <4815@skye.ed.ac.uk> richard@aiai.UUCP (Richard Tobin) writes:
< >... Once you have n stacks, you may be able to longjmp() between them.
< And then again, you may not.... Longjmp is only defined for going `up'
< the stack, and can (and does) abort programs that attempt to use it in
< the `wrong' direction. When you have two separate stacks and attempt
< to jump from one to the other, you are going neither up nor down, but
< the `<' comparison done internally gives an answer anyway (which answer
< it gives depends on the relative addresses of the two separate stacks)
< and thus implementations that check (such as 4.xBSD-on-a-VAX) may stop
< your code dead, rather than changing stacks.
< It is not impossible to implement this, but it *is* heavily machine
< dependent. Chances are you will get the best results not by trying
< longjmp(), but rather by reading up on the machine's calling
< conventions, the O/S's user stack conventions, and the machine
< architecture, and writing the context switch code only once you
< understand all of these. It is probably best to continue to avoid
< setjmp/longjmp as their specifications have changed in the past,
< suggesting that they may change again in the future. (Richard Tobin, I
< note, used _longjmp. This is what used to be called longjmp. POSIX
< now has sigsetjmp, apparently. In other words, this is dangerous
< territory. You should know exactly what you are doing, or you will
< step on a land mine.)
I faced this problem when I needed to create a semi-portable task library for
The C++ Answer Book. I wound up using setjmp/longjmp to do it because I
restricted myself to not using any assembly code and to knowing as little
about the stack frame as possible. I used the real stack for the stack, but
copied it out to the heap and then back in whenever I needed to do a context
switch. In order to get around the problem of longjmp only working when it's
executed above where it was created, I used the simple expedient measure of
recursively invoking my function until my address was indeed above the right
limit. (This method was dreamed up with help from Jonathan Shopiro.) And then
longjmp worked just fine. The scheme I used fails in two environments: if
you have multiple stacks, such as a separate register stack on Sparc's; and
if your version of longjmp attempts to walk the stack frames. I do wish that
the libraries which contained the stack frame walking versions of longjmp
also contained a non-walking version. If they did, then this scheme can work
on even more operating systems.
Tony Hansen
hansen@pegasus.att.com, tony@attmail.com
att!pegasus!hansen, attmail!tonyshocking@cs.uq.oz.au (Stephen Hocking) (06/09/91)
I put together a small package to do this sort of thing on 286/386 systems. It used a combination of longjmp/setjmp and alloca to get the stack to the right position. It was created in response to a need to translate some Modula 2 code to C, and thus has semantics similar to that langauges TRANSFER & NEWPROCESS routines, although workspace allocation is done internally. Stephen