package miou

Sleepers: how to inject syscalls into Miou?

This tutorial shows how to inject a new syscall to Miou and extend the API of it with blocking operations. For the example, we're going to implement the sleepers. Unix.sleepf is a blocking operation. The fundamental problem with Miou is that it performs operations in the background (scheduling). So using a blocking operation with Miou prevents it from managing other tasks concurrently (manage tasks entered with Miou.call_cc) or in parallel (wait for parallel process tasks introduced by Miou.call).

As stated in the documentation, and this is a fundamental rule: > you should never give Miou blocking tasks (such as Unix.sleepf)

That said, how do you manage blocking tasks? Miou offers an API that allows you to extend its API with such tasks. The idea is to inform Miou of a promise that is not associated with a task (because the latter would be blocking) and to notify it of the task that we would like to do as soon as we are sure that it is a non-blocking task.

This notification is possible because Miou lets you inject such a function which will notify it. This is the events function expected as a parameter to the Miou.run function.

What we want to do?

So let's get down to business. The aim of this tutorial is to enable you to write this code:

open Miou

let program () =
  Miou.run @@ fun () ->
  let a = Miou.call_cc (fun () -> sleep 1.) in
  let b = Miou.call_cc (fun () -> sleep 2.) in
  Miou.await_all [ a; b ]
  |> List.iter @@ function Ok () -> () | Error exn -> raise exn

let () =
  let t0 = Unix.gettimeofday () in
  program ();
  let t1 = Unix.gettimeofday () in
  assert (t1 -. t0 < 3.)

This code explains simple behaviour: our tasks a and b should run concurrently. In other words, in the end, we should consume strictly less than 3 seconds (about 2 seconds) to complete this little program.

You can have fun replacing sleep with Unix.sleepf and you'll see that we're back to a simple sequential execution where we need 3 seconds to finish the program. And that's normal, Miou doesn't know that Unix.sleepf is blocking, so it will execute the two tasks one after the other without scheduling them correctly.

So we've got our test, which will validate what we're expecting.

Syscalls.

Syscalls are indicators of a "suspension point" that needs to be "continued". Continuation can only be made when a system event occurs: in our case, when we have waited n seconds. In this way, the user is able to:

1. create such an indicator (Miou.make)
2. create a suspension point from this indicator (Miou.suspend)
3. organise their indicator management according to a unique ID (Miou.uid)
4. transfer the continuation once the system has warned us to do so (Miou.task)

The first function allows us to create our sleep "syscall". The second will allow us to specify the point at which we would like to obtain the result of our blocking operation and the third function will allow us to keep (and store) this syscall so that we can find it again later.

open Miou

let sleepers = Hashtbl.create 0x100

let sleep until =
  let return () = () in
  let syscall = Miou.make return in
  Hashtbl.add sleepers (Miou.uid syscall) (syscall, until);
  Miou.suspend syscall

As you can see, the implementation of a 'syscall' is relatively simple, but it is always associated with the implementation or extension of another function: the events function. The return value is the function that is called as soon as the given continuation has ended. In our case, we would like to return () : unit but we could very well return the value of a reference that the given continuation filled up.

Miou is quite stupid, trying to carry out all the tasks we give it in the hope that they will solve our promises. And it does this as long as it has at least one unresolved promise. In our case, the promise we've just created will never be resolved by any task. To clarify Miou's behaviour in this situation, you can run this code:

let dummy _ =
  { select= Fun.const []
  ; interrupt= ignore }

let () = Miou.(run ~events:dummy @@ fun () -> sleep 1.; ())

This code will never end simply because we didn't give Miou anything (a Miou.continue value) to un-suspend (and continue) our suspension point.

But as you can see, I've specified an events function here which always returns an empty list. In truth, if Miou has no more tasks to do and there are still syscalls, it will try one last thing: execute our events function. This can return a new continuation (always non-blocking) that could resolve our syscall. And it's here that we'll be able to inject the tasks that will continue (un-suspend) our sleepers.

Contrary to what we have just said, this events function (and only this one) can block! And, in reality, this is not a problem as all the tasks have been executed. We can therefore be in a busy waiting state for the next event to unblock our execution flow.

In our case, it's a case of taking the smallest sleeper, waiting and then returning a continuation that un-suspend that same sleeper. We also need to update the other sleepers because we're going to consume time.

let select () =
  let min =
    Hashtbl.fold
      (fun uid (prm, until) -> function
        | Some (_uid', _prm', until') when until < until' ->
            Some (uid, prm, until)
        | Some _ as acc -> acc
        | None -> Some (uid, prm, until))
      sleepers None
  in
  match min with
  | None -> []
  | Some (uid, prm, until) ->
      let until = Float.min 0.100 until in
      Unix.sleepf until;
      Hashtbl.filter_map_inplace
        (fun _ (prm, until') -> Some (prm, Float.max 0. (until' -. until)))
        sleepers;
      Hashtbl.fold
        (fun uid (syscall, until) acc ->
          if until <= 0. then
            Miou.task syscall (fun () -> Hashtbl.remove sleepers uid) :: acc
          else acc)
        sleepers []

let events _ = { select; interrupt= ignore }

Availability.

In our introduction to Miou, we mention the availability of tasks so that they can be executed fairly in relation to each other. The same should apply to "system tasks".

In this case, instead of prioritising the execution of the most minimal task, we give it the chance to run for at most 100ms (our quanta). The interest here is abstract, since we've only implemented "sleep", but it's very important when it comes to events such as reading a socket or receiving a connection. Both tasks should have a fair chance of asking the system if we can un-suspend them.

Usage.

Now that we have our events function and our syscall sleep, we can use them:

let prgm () =
  Miou.run ~events @@ fun () ->
  let a = Miou.call_cc (fun () -> sleep 1.) in
  let b = Miou.call_cc (fun () -> sleep 2.) in
  ignore (Miou.await a);
  ignore (Miou.await b)

let () =
  let t0 = Unix.gettimeofday () in
  prgm ();
  let t1 = Unix.gettimeofday () in
  assert (t1 -. t0 < 3.)

Note that our events function has been transferred to Miou.run! Without it, our code wouldn't work. And that's it! Our program did not fail to run, which means that we used less than 3 seconds (about 2).

$ ocamlfind opt -linkpkg -package miou main.ml
$ ./a.out
$ echo $?
0

And now we have proof that our 2 processes ran "at the same time". We say that they ran concurrently. Sleepers are a good example for understanding the syscalls mechanism with Miou, but of course you can extend this yourself with read, write and select as functions notifying us of system events.

The reason behind this API.

The fundamental objective remains the ability to specify/inject a system other than Unix. The ambition is, of course, to integrate Miou into unikernels. In this respect, we consider that lwt introduced the design that is probably the least costly for the user and the most maintainable for us. As such, we have simply reproduced what lwt already offered: miou and miou.unix.

There are many ways of abstracting and injecting implementations. Functors and value passing are examples. Once again, experience and usage may not be the state of the art of what can be done with OCaml, but they are valid arguments for the choice we have made.

It should also be noted that Miou has been designed for the development of system and network applications. Although the scheduler itself (miou) does not interact with the system, its task management policy is intrinsic to the way in which we can interact with the system today. Here again, experience and usage come first. There are many ways of interacting with the system (and some may be more interesting than others, depending on our specific application). But select() is still the simplest and most widely accepted of all systems (like Windows!).

Given the combination of unikernels and what the systems can offer, we have once again decided to take into account what has already been done. It's certainly not fancy, but it has the merit of having worked for quite some time.

Events & domains.

As you can imagine, this little introduction is not complete if we take into account Miou.call. Miou can launch tasks in parallel and these tasks can perform I/O. In our example, we can replace Miou.call_cc with Miou.call. The problems that will arise from such a change will be, to say the least, difficult to explain in full. However, they focus on a point that is fairly simple to see: we are not protecting our sleepers from changes that several domains can make at the same time.

Overall, this often requires synchronisation mechanisms between domains in order to manage parallel access to our sleepers. However, if you have already done some parallel programming, these mechanisms can:

• be cumbersome and require resources such as Mutex, Condition, etc.
• be error prone in very subtle cases of how domains will react.

Based on these findings, we propose a fairly simple design: a syscall is always managed by the domain that launched it. It is somewhat equivalent to Miou.call_cc, suspension only (Miou.suspend) operates concurrently with other tasks.

Local events at domains and local storage.

So, if we consider syscalls that can suspend the flow of execution that are always local to a domain, we can consider that each domain should have its own sleepers and that access to them should only be made by a single domain (the one with which they are associated).

From this idea, you can use a local storage. OCaml proposes that you can associate values with domains and retrieve these values according to the domain. This is done using the Domain.DLS module.

let sleepers =
  let make () = Hashtbl.create 0x100 in
  let key = Domain.DLS.new_key make in
  fun () -> Domain.DLS.get key

We then just need to call sleepers () in all the places where we use our hash-table to make sure we're using the one that's local to the domain. And voilà! As you can see, using Domain Local Storage simplifies our code enormously and saves us from having to implement and manage synchronisation mechanisms between domains.

Cancellation & interruption.

There is, however, one final point that we have deliberately omitted from this little tutorial: interruption. It was explained above that our events function can block and that it's no big deal - in fact, it is. We need to rephrase this assumption: events can block, but there must be a way for Miou to unblock the function - and by extension, the domain.

It's fair to ask why we would need such a mechanism. The answer is cancellation. It is possible to Miou.cancel a task with Miou.

let prgm () =
  Miou.run ~events @@ fun () ->
  let a = Miou.call (fun () -> sleep 10.) in
  sleep 1.; Miou.cancel a;
  match Miou.await a with
  | Error Miou.Cancelled -> ()
  | _ -> failwith "test"

let () =
  let t0 = Unix.gettimeofday () in
  prgm () ;
  let t1 = Unix.gettimeofday ()  in
  assert (t1 -. t0 < 10.)

In this example, a domain is asked to sleep for 10 seconds. But, at the same time, we want to Miou.cancel this task. At the moment, the domain will wait 10 seconds and then be "cancelled". This is where the interrupt mechanism comes in: Miou will interrupt the domain to tell it that something in its tasks has changed (cancellation). The domain will then recalculate these tasks and re-observe their states before finally realising that the task it was doing has just been cancelled.

The problem is that this interrupt must also interrupt our Unix.sleepf on which our domain is based. It's here, in our events function, that we're going to replace Unix.sleepf (which can't be interrupted) with Unix.select!

In fact, Unix.select can both wait (like Unix.sleepf) and interrupt itself if an event occurs on one of its file-descriptors. We are going to use the latter mechanism to implement an interrupt mechanism. To do this, we need to create a pipe (Unix.pipe). The interrupt function will be called by Miou whenever domains need to be interrupted (as in the case of cancellation). This interruption consists of writing to one side of the pipe while Unix.select observes the other side.

We also need to handle only syscalls that are pending. A task cancellation clean-up syscalls into the said task and we also need to clean-up the syscalls that have been deleted by Miou in our sleepers.

Finally, we will have to manage 2 cases, the one where we receive an interrupt and the one where we have just consumed our quanta. In the first case, we'll need to consume the byte sent to us by Miou, while the second case is similar to what we did before.

let rec consume_interrupt ic =
  if Unix.read ic (Bytes.create 1) 0 1 = 0 then consume_interrupt ic

let update sleepers n =
  Hashtbl.filter_map_inplace
    (fun _ (prm, until) ->
      let until' = Float.max 0. (until -. n) in
      Some (prm, until'))
    sleepers

let select interrupt () =
  let sleepers = sleepers () in
  (* clean-up our sleepers. *)
  Hashtbl.filter_map_inplace
    (fun _ (prm, until) ->
      if Miou.is_pending prm then Some (prm, until) else None)
    sleepers;
  let min =
    Hashtbl.fold
      (fun uid (prm, until) -> function
        | Some (_uid', _prm', until') when until < until' ->
            Some (uid, prm, until)
        | Some _ as acc -> acc
        | None -> Some (uid, prm, until))
      sleepers None
  in
  let ts =
    Option.map (fun (_, _, until) -> until) min |> function
    | Some ts -> ts
    | None -> 0. (* don't wait *) in
  let t0 = Unix.gettimeofday ()
  (* we must record how long we [select ()] to update then our [sleepers]. *)
  match Unix.select [ interrupt ] [] [] ts with
  | [], _, _ -> (
    (* no interruption *)
    let t1 = Unix.gettimeofday () in
    update sleepers (t1 -. t0);
    match min with
    | Some (uid, prm, _) ->
      Hashtbl.remove sleepers uid;
      [ Miou.task prm (Fun.const ()) ]
    | None -> [])
  | _ ->
    (* we got an interruption signal *)
    let t1 = Unix.gettimeofday () in
    consume_interrupt interrupt;
    update sleepers (t1 -. t0);
    []

let events _ =
  let ic, oc = Unix.pipe ~cloexec:true () in
  let rec interrupt () =
    if Unix.write oc (Bytes.make 1 '\000') 0 1 = 0 then interrupt () in
  { Miou.select= select ic; interrupt }

And there you have it, if you run our example code with cancellation, you can see the interrupt mechanism and the fact that one of our syscalls has been cleaned out. And our program finishes after 1 second.

This code shows the basic architecture of a real scheduler. We centralise everything around the select (which can become poll or something else). Quite a few issues have not been mentioned here (such as signal management, system interruption, or how to properly close our pipes). Above all, this means that this code is just an example! It does, however, give a general idea of how Miou_unix (Miou's Unix extension) works and how you can extend Miou for more specific system events.

Conclusion.

Miou offers a fairly straightforward API for its extension to system event management. There are many ways of abstracting and subsequently injecting what is fundamentally necessary in the development of system and network applications.

In this respect, we have chosen to re-use what has already suited us for a number of years.

Once again, our approach is part of the development of unikernels too. And it is in this context (of systems and network applications and unikernels) that we have developed the Miou API.

It should also be noted that this tutorial is aimed primarily at those who are curious (in their understanding of Miou_unix) and at those who want to extend Miou to other possible interactions with the system.