Thomas Gazagnaire

OCaml is a pragmatic functional language. You can do very advanced things with its type system (like an entire roguelike), and you can also hide the traditional buffer management techniques of C behind a nice abstract interface. One of those techniques stopped being safe when OCaml became multicore; I've hit it in ocaml-wire last week. ocaml-wire is the codec layer of Parsimoni's space protocol stack; its decode path runs for every packet, so it should be safe and fast (and ideally, work with multiple domains!).

Validators

ocaml-wire implements EverParse's model of binary formats. EverParse is Project Everest's verified parser generator: a format description carries its own validity constraints, and the generated validator rejects malformed input before any application code sees it. The library keeps that shape in OCaml, and can emit .3d files when formally verified C parsers are needed.

For instance, take a record of three 16-bit fields x, y and z whose last field must be the sum of the first two. EverParse calls this kind of constraint a where clause:

let f_x = Field.v "X" uint16be
let f_y = Field.v "Y" uint16be
let f_z = Field.v "Z" uint16be

let codec =
  Codec.v "Record"
    ~where:Expr.(Field.ref f_x + Field.ref f_y = Field.ref f_z)
    (fun x y z -> { x; y; z })
    [
      (f_x $ fun r -> r.x);
      (f_y $ fun r -> r.y);
      (f_z $ fun r -> r.z);
    ]

A hand-written version of the same validator shows what runs underneath: the decoder pulls each field into a slot, then evaluates the constraint over the slots:

let valid_naive buf off =
  let slots = Array.make 3 0 in
  for i = 0 to 2 do
    slots.(i) <- Bytes.get_uint16_be buf (off + (2 * i))
  done;
  slots.(0) + slots.(1) = slots.(2)

It allocates its slots on every call. A good way to see it is by using memtrace, OCaml's allocation profiler. The program opts in with one call at startup, Memtrace.trace_if_requested (), and setting MEMTRACE=naive.ctf in the environment turns sampling on, at a default rate of one sample per million allocated words. Running the validator ten million times under the profiler gives:

$ memtrace_hotspots naive.ctf
   36 samples of  0.3 GB allocations

 0.3 GB (100.0%) at Dune__exe__Records.valid_naive (records.ml:8:14-28)

Four words per call (the three slots plus the array header) over ten million calls, at eight bytes per word, is the 0.3 GB; the sampling rate reduces it to a few dozen samples, each with a source location.

The usual fix is to hoist the scratch to the toplevel and reuse it:

let slots = Array.make 3 0

let valid_scratch buf off =
  for i = 0 to 2 do
    slots.(i) <- Bytes.get_uint16_be buf (off + (2 * i))
  done;
  slots.(0) + slots.(1) = slots.(2)

The same trace now reports 0 samples of 0 B allocations. ocaml-wire's validators use this layout: decoded fields land in slots owned by the codec value, allocated once when the codec is built.

Domains

OCaml 5 gave the language real parallelism: spawn a domain and two pieces of OCaml run on two cores at once. It also turned every persistent scratch into shared mutable state, because a codec value shared between domains shares its slots too. Run valid_scratch from two domains, one validating a well-formed record and one a malformed record, a million times each, and each domain overwrites the other's slots mid-validation:

115726 wrong decodes out of 2000000

No exception is raised; the calls return wrong verdicts. For ocaml-wire it means that valid packets can be silently dropped (in a TCP stack that runs one connection per core, the dropped segment stalls the connection), so adding cores decreases throughput. Fortunately, OCaml ships a ThreadSanitizer build, available as an opam switch with ocaml-option-tsan (read more on the Tarides blog). It instruments every memory access, and the first run reports the racing pair, both stacks pointing at the validator:

WARNING: ThreadSanitizer: data race (pid=90385)
  Write of size 8 at 0x00010a5ff720 by thread T4 (mutexes: write M0):
    #0 camlRecords$valid_scratch_432 (race_tsan:arm64+0x10000465c)
  Previous write of size 8 at 0x00010a5ff720 by thread T2 (mutexes: write M1):
    #0 camlRecords$valid_scratch_432 (race_tsan:arm64+0x10000465c)

To fix this, the OCaml standard library has several tools. Here I picked Domain.DLS, domain-local storage: a key is created once, and each domain gets its own value, initialised on first use. With it the scratch moves from one per program to one per domain:

let slots_key = Domain.DLS.new_key (fun () -> Array.make 3 0)

let valid_dls buf off =
  let slots = Domain.DLS.get slots_key in
  for i = 0 to 2 do
    slots.(i) <- Bytes.get_uint16_be buf (off + (2 * i))
  done;
  slots.(0) + slots.(1) = slots.(2)

The race test now reports zero wrong decodes and ThreadSanitizer is silent. The per-call allocation count stays at zero, since the scratch is created once per domain and Domain.DLS.get is a lookup. Domain-local is not thread-local: two preemptive systhreads sharing a domain must still not decode one codec value at once. OCaml 5 also ships green-thread machinery through effect handlers, with frameworks like Eio and Miou building fibers on top. Those are safe here: fibers interleave only at effect points, and a decode performs no effects, so a fiber is never descheduled mid-decode.

ocaml-wire had this bug in two places. The decode scratch was shared exactly like valid_scratch above (ocaml-wire#223). Parametric codecs had a second copy: a codec can take an input parameter, for instance a max_len bound on a payload, and the cell holding that parameter also lived in the codec value (ocaml-wire#224). Two domains decoding with different bounds overwrote each other's max_len, so a payload within its own bound could fail the other domain's where check. Both fixes shipped in wire 1.1.0.