bootstrap is not reproducible wrt -j value

[bmwiedemann]

While working on reproducible builds for openSUSE, I found that our ocaml-dune 3.12.1 package varies depending on the amount of parallelism.

Expected Behavior

Build output should be deterministic - as it still was in the previous version 3.11.1

Actual Behavior

Binaries produced by -j 1 and -j 4 vary even in length.
A diff of strings output looks thus:

 camlDune_rules__Package_db__fun_2964                                           
-camlOpamSystem__303
 camlDune_engine__Action_exec__fun_5160
 camlDune_engine__Action_builder0__code_begin
+camlStdune__Signal__3410
 camlDune_re__Core__witness_2586
 camlDune_rules__Modules__fun_4126
+camlNotty_uucp_data__16639
 camlDune_rpc_impl__fun_970
[...snipped...]

one created a _boot/compiled_ml_files and the other a _boot/mods_list. Build logs also differ a lot.

Reproduction

• PR with a reproducing test:

1. on openSUSE or Debian

#!/bin/sh
osc co openSUSE:Factory/ocaml-dune && cd $_ || exit 1
for N in 1 2 ; do
    osc build -j $N --vm-type=kvm --noservice --no-preinstallimage --keep-pkg=RPMS.$N
    unrpm RPMS.$N/ocaml-dune-*.x86_64.rpm
    strings usr/bin/dune > $N.strings
done
diff -u {1,2}.strings

Specifications

• Version of dune (output of dune --version): 3.12.1
• Version of ocaml (output of ocamlc --version): 4.14.1
• Operating system (distribution and version): openSUSE Tumbleweed 20231213

Additional information

• Link to gist with verbose output (run dune with the --verbose flag):
  https://gist.github.com/bmwiedemann/c05ab97a162d966ae40b7a39065efd6e

[bmwiedemann]

-ocaml boot/bootstrap.ml --verbose ${jobs}                                      
+ocaml boot/bootstrap.ml

did not improve the outcome, but I found that the below helps to avoid the race:

-ocaml boot/bootstrap.ml --verbose ${jobs}                                      
+ocaml boot/bootstrap.ml -j 1

(--verbose did not make a difference)

[emillon]

Thanks for the report. At first I thought it was something like #9152, but it looks like this particular issue is about dune's bootstrap process itself. I'll have a look.

[emillon]

I had a look at this. The core of the issue is this check:

https://github.com/ocaml/dune/blob/3.12.1/boot/duneboot.ml#L1194

For -j 1, there's a special case where instead of running the custom concurrency engine, we instead build using a single command. I guess that this is done for performance reasons, since this goes from 37s to 28s on my machine.

Build output should be deterministic - as it still was in the previous version 3.11.1

That seemed weird since I don't think we touched that recently, so I did some testing with the following test:

#!/usr/bin/env bash
rm -rf _boot
ocaml boot/bootstrap.ml --verbose -j 1 2>/dev/null
cp _boot/dune.exe dune1.exe
rm -rf _boot
ocaml boot/bootstrap.ml --verbose -j 8 2>/dev/null
cp _boot/dune.exe dune8.exe
if cmp dune1.exe dune8.exe; then
    echo "identical"
elif (( $(stat -c%s dune1.exe)==$(stat -c%s dune8.exe)));then
  echo "same size"
else
  echo "completely different"
fi

For 3.6.0, 3.11.1 and 3.12.1 this prints "completely different", so I think that this has been the case since the new bootstrap process got introduced in #2854. And I verified that removing the optimization prints "identical".

As for how to fix this: this is easy to add (remove the if concurrency = 1 test) but this causes a tradeoff between performance and reproducibility, and I'm not sure how we should make the choice.

• we could try to make both build plans create the same binary. TBH, I don't think that's possible. I don't think that there are huge concerns that the binaries are going to act differently, but they're built from different sequences of commands.
• we could say it's not an issue. -j1 and -jx return different results, but -j1 will all return the same thing and -jx will always return the same thing (I don't think that's the right answer)
• we could remove the optimization
• otherwise, we need a way to tweak the behaviour. let's say we add a -prefer flag, -prefer performance will use the single command build, and -prefer reproducibility will use the sequential build (using the concurrency engine running at most 1 job). which one should be the default, then?
  • if performance is the default (equivalent to today), it means that downstream users including opensuse need to adapt their build instructions to get reproducibility
  • if reproducible is the default, this means that users doing sequential builds of dune will need a way to get that extra juice, but it's unlikely they can plumb that to opam (assuming they're using opam).

Having written that, I think that the easiest way for now is to introduce a -reproducible flag to the bootstrap process to disable the optimization, so that -reproducible -j 1 and -reproducible -j 4 will create the same binary. If this sounds like a good idea we can try to make that the default later. What do you think?

[rgrinberg]

Getting rid of the optimization sounds like the simplest thing tbh. It's problematic in other contexts - such as on systems with limited memory. A flag like -reproducible is another way of saying -avoid-buggy-behavior, which doesn't sound like a good interface.

[rgrinberg]

If building in a single command is important to someone, we could always move it to a separate -build-single-command option.

[bmwiedemann]

You are right. I re-ran the test with 3.11.1 and it produced the same variations today.
A default -reproducible option sounds good.

I checked the different (j1/j4) commands used to build dune.exe and besides -no-alias-deps -w -49-6 the diff is between the ordering in -args mods_list vs -args compiled_ml_files - so I wonder if both produced the same output with a consistently ordered input list.

[emillon]

I checked the difference between the binaries using https://github.com/noseglasses/elf_diff. In the separately-built version, the compiler managed to do some optimizations and some functions in OpamFormula are different.
I tried to add some flags to make sure that the outputs match but it seems impossible.
So yes, let's get rid of the optimization by default. We still need the single build command for windows anyway.

[rgrinberg]

We still need the single build command for windows anyway.

Could you remind me why? Seems odd and probably means that we can't build dune on a windows box with low memory.

[emillon]

I actually don't know. I opened #9613 and it doesn't seem to be necessary.