Implement Systhreads in terms of domains

[kayceesrk]

The systhread implementation is currently only safe when there is a single domain. The implementation aims to be backwards compatible with vanilla OCaml. Eventually, systhreads should be deprecated, with possibly a backwards compatible implementation over domains.

[lpw25]

I don't think that systhreads should be deprecated. I think having multiple threads inside a single domain is the right way to implement asynchronous versions of synchronous system operations. It is probably useful in other situations as well.

Of course it should be made clear in documentation that domains are how to get parallelism. Since the name "threads" is pretty firmly connected to parallelism, it may even be necessary to rename the threads library to get the point across, but the functionality should still be available.

[lpw25]

I think it would be useful to have a vaguely concrete implementation
plan about how to do this, and also how to handle asynchronous effects
and preemption. So here is my attempt to outline a design that I think
will work.

The aims of this design are:

1. Support the existing Threads API
2. Support using "asynchronous" effects to do preemptive schedulers and
   handle things like signals
3. Remove from OCaml any genuine asynchronous exceptions -- this makes
   reasoning about resource management much simpler/possible.

Perhaps, those aren't actually the aims we need, but they are some
things that I'm most interested in, so that's what I've started from.

Threads

The first step is to add a concept of "thread" to the multicore
runtime. These are not the current heavyweight threads tied to system
threads. They are a lightweight concept based on the existing
continuations.

A thread that is not currently running is represented by just a
continuation. Although continuations/stacks would need to be extended to
include information about which asynchronous events (e.g. signals,
alarms for preemptive schedulers) can be handled and how they should be
handled.

Unlike an ordinary continuation created when an effect is performed,
this continuation may be at a location that is not "exception-safe". By
"exception-safe" I mean a place where an effect or exception can safely
be performed/raised. As such, this continuation should never be
discontinued, it may only be continued. The continuation is always at a
point that expects () so there is essentially just a simple resume
operation on threads that takes no other arguments.

At any time a domain may have multiple threads scheduled to run. If there
are multiple threads then they are scheduled preemptively, using similar
heuristics to the current system threads implementation for when to
switch threads.

My reasoning for including another concept alongside effect
continuations is that when multiple threads are created using the
Threads API we need to run them concurrently even when there is no
user-level scheduler provided. You can imagine that there is a built-in
user-level scheduler surrounding the whole program and the threads API
performs effects that are handled by this scheduler. However, we can't
track these effects in the type system backwards compatibly so they
can't really be ordinary effects. Also the concept of "the whole
program" is a bit tricky. The behaviour of these threading effects in
places like signal handlers needs to be well specified -- especially for
the case of finalisers which are crucial for allowing "asynchronous"
effects without causing genuinely asynchronous exceptions.

So, rather than having the threads API perform effects that are handled
by a builtin user-level scheduler, we have the builtin scheduler be part
of the runtime and create an explicit concept in the runtime to
represent the units of work handled by this scheduler.

"Asynchronous" effects

In order to handle asynchronous events like signals we would provide
functions that interpreted these events as effects. Such functions
would look something like:

val handle_signal : int -> ('a -> 'b) -> 'a -[ Signal : int -> unit ]-> 'b

Calling this function would mark the current thread as able to handle the
given signal, and then execute the given function. If that signal is
received whilst running the given function, then this thread may be chosen
by the runtime to handle it. When that happens we:

1. Pause execution of the currently running thread.
2. Create a thread/continuation representing the computation from the
   top of the stack down to the nearest enclosing effect handler from
   the call to handle_signal (the information required for this would
   be included in the thread).
3. Pass this thread to the enclosing effect handler along with the
   Signal effect.

Since this continuation was created when not performing any effects,
this continuation is not exception safe. As such, we need to specify
what happens if it is discontinued by the user or dropped on the floor
and garbage collected. In these cases, we essentially just hand the
thread/continuation to the builtin scheduler to be scheduled just as if
it had been created using the Threads API. When the thread finishes
it's result is simply ignored. If the thread performs an effect which is
not handled by any of the effect handlers within it, then we simply
raise the Killed exception -- which is what we do if an ordinary
effect continuation is garbage collected. This is safe since we know the
thread is now at an exception safe location.

Note that some care needs to be taken to mark the appropriate
continuations as handling a particular asynchronous event. Essentially,
a continuation should only be marked as handling a signal if it contains
the stack frame for the call to handle_signal.

Preemptive schedulers

Preemptive schedulers would be written using a function like:

val preempt : int -> ('a -> 'b) -> 'a -[ Preempted : unit -> unit ]-> 'b

which would mark the current thread/continuation to be preempted, then
run the given function. Whilst that function is running, the runtime
will interrupted at the given period (not sure what measure this should
be yet -- maybe time in ms, maybe some other measure of progress). When
the thread is interrupted the same process as happened for handle_signal
happens, only this time performing the Preempted effect.

As before, the produced continuation cannot be safely discontinued or
garbage collected, so in those cases it will continue to be executed by
the scheduler.

Thread API

The Thread API would be reimplemented on top of the new runtime
threads instead of system threads. Possibly we could use parts of the
existing implementation based on VM-threads, since what we're doing is
pretty similar.

Since Thread.create would no longer create a separate system thread,
we need to handle the case where a blocking C call is made. I believe
@stedolan already has a whole plan for how to handle this transparently
using a pool of system threads. So I defer to his plan on that point.

We would also deprecate Thread.kill, which is already a
noop in native code.

Asynchronous exceptions

OCaml currently supports a number of asynchronous exceptions (as well as
some situations where any exception can become asynchronous, but those
are basically bugs). In particular, there is Out_of_memory,
Stack_overflow, and Break.

Out_of_memory should almost certainly be a fatal_error -- and it
barely ever happens since you either hit swap space and wait for the
heat death of the universe or you get OOM killed.

Stack_overflow is notoriously unreliable and again could easily be
replaced by a fatal error. Some people use it as a lazy implementation
of searching for something up to a limit -- this is a very bad idea and
they should rewrite their code to not be crazy.

Treating Break as an exception has some use cases. People use it to
allow long running operations to be interrupted. However, this is
unsafe in general and instead they should implement a proper mechanism
to safely kill their operations.

One exception to this is the OCaml toplevel -- where the code that might
need to be interrupted is the user's code (e.g. the user accidentally
writes an infinite loop and wants to carry on with their day). I suggest
we add some unsafe mechanism, probably in Obj, to handle this
case. Something like:

val kill_continuation : (_, _) continuation -> unit

that marks a continuation as run even though it hasn't been. Then you
can use handle_signal to catch the interrupt and just kill the
returned continuation.

[kayceesrk]

I have a few high-level concerns and a few comments on this specific proposal.

The motivation for Threads API is to provide a way to implement asynchronous versions of blocking system operations (such as reads from the disk). Do we necessarily need a Threads API in addition to effect handlers? It creates an additional layer in the scheduling hierarchy now Effect Handlers => Threads => Domains. Can we solve this in a way that doesn’t introduce a new scheduling layer?

This roughly solves the same problem as Safe FFI calls in GHC, but one that works with the fact that the scheduler is not part of the runtime system. Safe FFI in GHC solves two problems:

1. How to handoff control to another system thread when the current system thread blocks on a system call.
2. How to find the next Haskell task to run.

We need to solve (1) in almost the same way as safe FFI, with backup threads servicing a domain. When the current system thread blocks, the backup thread wakes up to do useful work. In GHC, (2) is straightforward since the thread scheduler is part of the runtime system. However, in Multicore OCaml, the scheduler is not (and shouldn’t be) part of the runtime system. How does the Threads API handle (2). I don’t think you are proposing to implement the Thread scheduler in the runtime system?

I am leaning towards the solution that we have described in TFP paper Sec 4.4 (http://kcsrk.info/papers/system_effects_feb_18.pdf) in order to solve (2). When the current task gets blocked on a synchronous system call, the same task gets taken over by the backup thread, in which Delayed effect is raised. This allows the control to get to the scheduler queue and schedule another thread. When the system call returns, we raise Completed effect to so that we can enqueue the thread back into the scheduler. There is some magic that needs to happen to properly handle the return value from the system call (and to get the type of the continuation right), but this is just detail. The default handler for Delayed is to just block the thread making the system call waiting for it to return. With the Delayed and Completed effects, you can implement Systhreads like interface on top.

Other comments

• In order to reason about the interaction between effect handlers and threads, is it appropriate to consider thread scheduler to be the outermost handler?

• Once we add a Threads API with its own default scheduler, we need a way to synchronise between them. Perhaps there should also be a simple MVar library to go with the Threads API such as: https://github.com/kayceesrk/effects-examples/blob/master/mvar/MVar.ml. Since these threads are effect oblivious and we imagine a top-level scheduler / MVar library, the effects Suspend and Resume (from the linked example) would also be “built-in” effects, so that they don’t get tracked in the effect system. If the scheduler for Threads live in the runtime system, then the MVar also should live there, which is undesirable.

• What is the signal handling behaviour when the thread with the signal handler is not currently running? Should the signal be deferred until the thread with the signal handler runs next? Alternatively, the current thread may be interrupted with the signal handler and the default handler kicks in. Perhaps latter is the right behaviour since it minimises bookkeeping associated with signal handlers.

The rest makes sense to me.

[lpw25]

My aim with this proposal is to try and address a few issues. Part of the underlying problem is working out exactly how inter-related these issues are. I hope that by determining that it should become clear how many additional concepts are needed in the runtime. The issues I have in mind are the following:

1. We need a backwards compatible implementation of the Thread API because there is too much code using it in the wild for us to just drop it in multicore OCaml.
2. In addition to the existing concurrency from the Thread API, there are other parts of the existing runtime that produce concurrency: signal handlers and finalisers. So even if we drop Thread we will still be in a situation where there is not simply a single running fiber.
3. To make things like handle_signal work for driving signal handling in a user scheduler we need to ensure that all signals are given to one of the schedulers (assuming a scheduler in each domain) rather than attempting to perform them in another thread or dropping them on the floor because the currently running thread doesn't handle them. For example, we need to make things well behaved when a signal arrives whilst we are running a finaliser.
4. We need a clean story about what to do when a continuation created by handle_signal or preempt is discontinued or garbage collected. Ideally we want to resume that continuation until we hit some exception-safe point and then discontinue it but I think for clean semantics it should probably be an exception-safe point related to the handler which did the discontinue (i.e. when we have executed the continuation to completion or performed an effect which is handled by that handler).

In my first attempt, I essentially addressed issue 4 by treating these zombie continuations like threads started by Thread. I addressed issue 3 by having threads marked with the signals that they can handle. However, now that I've made these issues explicit I can see that I don't address issue 2, in particular I don't actually address issue 3 for finalisers and signal handlers.

Signal handlers and finalisers

I can see two possible directions for addressing issue 2.

• We could run every signal handler and finaliser in its own thread, scheduled just like all other threads, and thus marked with the signals which they can handle.
• We could create another concept to represent things like signal handlers and finalisers. I can't think of a good name so lets just use the word "context" -- i.e. when executing a finaliser you create a new context and run the finaliser in that. In particular, the context would be the thing which tracks which signals can be handled, and each continuation/thread would have an associated context. Note that when running a finaliser, the context of the main thread still needs to be stored in the runtime so that we can tell which signals should be delayed until the finaliser is done.

An alternative for "zombie continuations"

Thinking about these issues also suggests to me another approach for "zombie continuations" (i.e. issue 4). Rather than turning them into threads and giving them to the thread scheduler, we could treat them like signal handlers and finalisers. So they would get executed at the next minor collection in a new context. They would run until they completed. If they performed an effect that reached their outermost effect handler -- i.e. the one which turned them into a zombie -- then it would be handled by discontinue. This ensures that zombie continuations don't interfere with the original scheduler -- which is important since they are executed concurrently with it.

This approach leaves the whole threads concept as only used for implementing the Thread API, which does sound better.

Answers to specific questions

Do we necessarily need a Threads API in addition to effect handlers?

I think we need one for backwards compatibility.

I also think we need the "context" part to deal with signals properly. In my mind, I originally tied that idea closely to the "threads" concept, but now I think it is more a property of continuations in general.

Can we solve this in a way that doesn’t introduce a new scheduling layer?

I don't see how. The problem is that it is not a new scheduling layer, it is an existing scheduling layer, so it is hard to remove.

Safe FFI in GHC solves two problems:

1. How to handoff control to another system thread when the current system thread blocks on a system call.
2. How to find the next Haskell task to run.

We need to solve (1) in almost the same way as safe FFI, with backup threads servicing a domain. When the current system thread blocks, the backup thread wakes up to do useful work. In GHC, (2) is straightforward since the thread scheduler is part of the runtime system. However, in Multicore OCaml, the scheduler is not (and shouldn’t be) part of the runtime system. How does the Threads API handle (2). I don’t think you are proposing to implement the Thread scheduler in the runtime system?

I am leaning towards the solution that we have described in TFP paper Sec 4.4

I hadn't given this aspect much though. But how about the following scheme:

When we call an external function and it does enter_blocking_section, we pause the current thread and if there are other available threads we try to execute them -- obviously the system thread running the call is no longer available for use in other C calls. When the system thread does leave_blocking_section the thread is made available for scheduling again. This is basically an implementation of the current OCaml behaviour but using a pool of system threads rather than one per OCaml thread.

Then we add a new form of external:

external foo : int -> int -[ Delayed : int -> unit ]-> int = "foo"
[@@blocking]

When one of these externals does enter_blocking_section we do exactly as the paper suggests.

Essentially, the answer to the question of "How to find the next [OCaml] task to run." is to use the thread scheduler to find another thread for old externals and to use the Delayed mechanism with the current thread for new [@@blocking] externals.

This should allow existing code using Thread to work as expected and also allow new code to use the nicer effects based approach. I think we need some kind of transition plan like this anyway because the nice new mechanism requires a change to the type of the external.

In order to reason about the interaction between effect handlers and threads, is it appropriate to consider thread scheduler to be the outermost handler?

I think so. I think it is a handler surrounding the entire program, including all the default handlers, using some special untyped effects. Since those effects can only be handled by this outer handler we optimise their implementation by not searching our way up the stack of handlers.

What is the signal handling behaviour when the thread with the signal handler is not currently running? Should the signal be deferred until the thread with the signal handler runs next?

Yes it should be delayed, or the other thread should be resumed as the handler now. This is an instance of my issue 3 above, and it is crucial for getting predictable behaviour.

Once we add a Threads API with its own default scheduler, we need a way to synchronise between them. Perhaps there should also be a simple MVar library to go with the Threads API

Well, the Threads API already has its own synchronisation primitives. Personally, I'm not particularly interested in adding more as I think that the Threads API will essentially be deprecated by the new stuff.

[bluddy]

Would it be possible to create an emulation layer for Thread? Wrap it in a generic effect handler, translate all synchronous calls to asynchronous ones, and place a yield effect at every allocation point, similar to the way haskell does it implicitly? This could be a special compilation mode for backwards compatibility invoked when the thread lib is requested. If any synchronous call cannot be mapped to an async one, it would fail.

[lpw25]

I think that would be ridiculously inefficient. The point is to allow Threads code to keep working, that means it can't take a huge performance hit.

[lpw25]

Maybe I'm not being ambitious enough. Maybe we could remove Thread support in multicore. A lot of code would be updated by updating the code in Async and Lwt. However, it would be a much more painful upgrade path than we've used for anything else. There would be no version of the OCaml runtime that supported both the old API and the new API, so things using threads will have to have different versions for before and after the change. My proposal here is essentially that we should add Threads support to OCaml multicore so that the API can be deprecated over a number of versions rather than all at once.

[kayceesrk]

part 1 of N, rest to follow

1. We need a backwards compatible implementation of the Thread API because there is too much code using it in the wild for us to just drop it in multicore OCaml.

Agreed. My original comment in the issue of dropping systhreads was on the incorrect assumption that systhreads weren't widely used. I think we should maintain the systhreads API to provide a transition path.

2. In addition to the existing concurrency from the Thread API, there are other parts of the existing runtime that produce concurrency: signal handlers and finalisers. So even if we drop Thread we will still be in a situation where there is not simply a single running fiber.

Aren't finalisers simpler than signal handlers? Finaliser actions in trunk and also in multicore currently are run in a caml_callback_exn. Exceptions escaping the finaliser action interrupts whatever is being done currently, which isn't a good behaviour and I would like that to be a fatal error. In the same way, if we treat effects escaping finalisers to run their default actions, we would have sensible semantics for finaliser actions.

I like the context idea. If the finaliser were to be run in its own context (with the main computation's context saved in the runtime), we will have sensible semantics for finalisers. Finalisers are always run in a default context (for a start).

[lpw25]

Aren't finalisers simpler than signal handlers?

Possibly, although to me they seem to have the same problems as finalisers. For clarity, I should point out that I mean the OCaml signal handlers, not the OS level ones. The OCaml runtime creates its own OS level signal handlers that capture signals and put them on a queue to be handled by the appropriate OCaml signal handler when the system is in a sensible state.

Exceptions escaping the finaliser action interrupts whatever is being done currently, which isn't a good behaviour and I would like that to be a fatal error.

100% agree. I basically consider that a bug. IIRC the same happens with exceptions from signal handlers as well.

[mshinwell]

I was going to propose a patch to make the out of memory error, together with any exceptions escaping from finalisers, fatal errors. Maybe I should do that for 4.08.

[mshinwell]

(Exceptions from signal handlers I guess should be treated the same as from finalisers.)