Can preemptive multitasking of native code be implemented in user space on Linux?

Question

I'm wondering if it's possible to implement preemptive multitasking of native code within a single process in user space on Linux. (That is, externally pause some running native code, save the context, swap in a different context, and resume execution, all orchestrated by user space but using calls that may enter the kernel.) I was thinking this could be done using a signal handler for SIGALRM, and the *context() family but it turns out that the entire *context() family is async-signal-unsafe so that approach isn't guaranteed to work. I did find a gist that implements this idea so apparently it does happen to work on Linux, at least sometimes, even though by POSIX it's not required to work. The gist installs this as a signal handler on SIGALRM, which makes several *context() calls:

void
timer_interrupt(int j, siginfo_t *si, void *old_context)
{
    /* Create new scheduler context */
    getcontext(&signal_context);
    signal_context.uc_stack.ss_sp = signal_stack;
    signal_context.uc_stack.ss_size = STACKSIZE;
    signal_context.uc_stack.ss_flags = 0;
    sigemptyset(&signal_context.uc_sigmask);
    makecontext(&signal_context, scheduler, 1);

    /* save running thread, jump to scheduler */
    swapcontext(cur_context,&signal_context);
}

Does Linux offer any guarantee that makes this approach correct? Is there a way to make this correct? Is there a totally different way to do this correctly?

(By "implement in user space" I don't mean that we never enter the kernel. I mean to contrast with the preemptive multitasking implemented by the kernel.)

Kenakenaf

Sure it can. The Go runtime does its own context switches of goroutines, each with very small stacks. – Thermo

I think early pthread implementations were entirely userland. – Whaleback

@Whaleback I thought early pthreads used LinuxThreads which were closer to processes. – Thermo

@JonathonReinhart Maybe I'm thinking of something else, but I'm pretty sure there were some threading libraries that predated kernel threading. Perhaps it was in Solaris rather than Linux. – Whaleback

It is possible to do in userland, but... Microsoft used to provide it through Fibers. They are lightweight threads and the app is responsible for scheduling. I don't know Microsoft supports them anymore since they have changed to a XAML/tablet company. I don't know what Linux provides. – Knucklebone

@JonathonReinhart This sounds promising but even though Go source may not be cooperative, the Go compiler may still be generating cooperative native code. Are you sure that the Go runtime somehow preempts native code? – Kenakenaf

@JonathonReinhart I'm not fluent in Go, but from this github thread it seems like Go does require code to check if it should yield. – Kenakenaf

@Knucklebone It looks like Window's fibers are for cooperative multitasking and similar to the *context() family in POSIX. (Also, this is very OS-specific and I meant this just for Linux. There's no reason an OS couldn't make this possible and I want to know if Linux does make this possible. I updated the title accordingly.) – Kenakenaf

I remember that I once stumbled over "multitasking" when I searched for setjmp / longjmp. (Actually, I intended to do some kind of "exception handling" in C.) I just googled "c setjmp longjmp thread switch". Look, what I found (among others): SO: Multitasking using setjmp, longjmp. (IMHO, he could tagged it with c also, at least...) – Varnado

Assuming it was possible, (and preemption without interrupts does not seem possible to me), why would it be useful to do this? – Pitiable

@MartinJames The two uses I could see are implementing green threads or garbage collection on top of native code that we're given as-is (i.e. doesn't yield). I can't give you a reason that there's a pressing need for either of those, but I would find them interesting. – Kenakenaf

Answer 1

You cannot reliably change contexts inside signal handlers. (if you did that from some signal handler, it would usually work in practice, but not always, hence it is undefined behavior).

You could set some volatile sig_atomic_t flag (read about sig_atomic_t) in a signal handler (see signal(7), signal-safety(7), sigreturn(2) ...) and check that flag regularly (e.g. at least once every few milliseconds) in your code, for example before most calls, or inside your event loop if you have one, etc... So it becomes cooperative user-land scheduling.

It is easier to do if you can change the code, e.g. when you design some compiler which emits C code (a common practice), or if you hack your C compiler to emit such tests. Then you'll change your code generator to sometimes emit such a test in the generated code.

You may want to forbid blocking system calls and replace them with non-blocking variants or wrappers. See also poll(2), fcntl(2) with F_SETFL and O_NONBLOCK, etc...

You may want the code generator to avoid large call stacks, e.g. like GCC's -fsplit-stack instrumentation option does (read about splitstacks in GCC).

And if you generate (or write some) assembler, you can use such tricks. AFAIK the Go compiler uses something similar for its goroutines. Study your ABI, e.g. from here.

However, kernel initiated preemptive scheduling is preferable (and on Linux will still happen between processes or kernel tasks, see clone(2)).

PS. If garbage collection techniques using similar tricks interest you, look into MPS and Cheney on the MTA (e.g. into Chicken Scheme).

Hulbert

Something worth adding is that glibc does offer relevant safety guarantees that POSIX doesn't require (e.g. getcontext() and makecontext() are AS-Safe) but some of the necessary functions are still AS-Unsafe. – Kenakenaf