8 ms·

Towards Idempotent Rebuilds?

59 points by JNRowe 2y ago

outsomnia 2y ago
I was expecting to see the word "yocto", did I miss it? This goes quite far along the path, building all the build tools and toolchain to the same version before building the packages.
ethegwo 2y ago
As I know, LLVM optimizer (maybe also GCC) is not idempotent, does it mean we need to pay performance for idempotent buildings?
- bpfrh 2y ago
  Shouldn't same system+same version+same flags produce the same result?
  - jiehong 2y ago
    The algorithms used might not produce a deterministic result (like order is different), and maybe it also depends on timings of the CPU with threads scheduled on different cores, or faster/slower cores, etc. Deterministic builds aren't always that straightforward
    - 0x457 2y ago
      I'm using nix and clang/llvm - never have I ever got a different binary. If what you're saying is true - stage 3 bootstrap wouldn't be possible.
      - malkia 2y ago
        bit obvious, but all it takes something that takes something that changes everytime to make it non-reproducible - like __DATE__ and __TIME__
        zaphar 2y ago
        Nix solves this by forcing __DATE__ and __TIME__ to be a single immutable value in the sandbox for all builds. If you look in the store the file timestamps will be this value.
    - plorkyeran 2y ago
      All C and C++ compilers in common use are single-threaded, and parallelism is achieved by compiling multiple files at once. An optimizer pass producing nondeterministic results due to a bug is not impossible, but would be a bug to fix. Multithreaded linkers which are expected to have nondeterministic results do exist, and you have to not use that for reproduce able builds. There's a long tail of tricky problems to solve for reproducible builds, but a specific build of a compiler producing different executable code from run to run hasn't really been one of them.
      - bobmcnamara 2y ago
        Now I'm wondering how differently my multithreaded tcc fork produces code. I don't think it should but it always wouldn't surprise me if there was some shared state remaining.
    - kardos 2y ago
      Forcing the ordering to be deterministic is a well-established part of the process https://reproducible-builds.org/docs/stable-inputs/ https://reproducible-builds.org/docs/stable-inputs/ https://reproducible-builds.org/docs/stable-outputs/ https://reproducible-builds.org/docs/stable-outputs/
- patmorgan23 2y ago
  Compilation performance or end executable performance?
  - ethegwo 2y ago
    The latter I mean, conservative optimization level is benefit to keep idempotency
- compiler-guy 2y ago
  Google takes great care to ensure that the LLVM optimizer produces bit-identical results for identical inputs across plenty of machines. If the llvm optimizer produced non-bit-identical results for identical inputs (all sources and command-line flags), Google would consider that a high priority bug. So I'm reasonably sure it does produce bit-identical results.
vzaliva 2y ago
Coming from maths, I am confused by use of the term "idempotent" here. Unless we are talking about bootstrapping a compiler and I do not see how it applicable here. Am I missing something?
- algernonramone 2y ago
  I feel that "deterministic" is probably a better word here than "idempotent".
  - craigching 2y ago
    Maybe even hermetic builds? https://bazel.build/basics/hermeticity https://bazel.build/basics/hermeticity
  - appplication 2y ago
    Not speaking to your comment specifically, but adding context to the thread: idempotence would mean having the same result, regardless of whether you run something once, twice, or 10 times, over the same input set. Idempotence requires but goes beyond determinism, as it also accounts for any externalities and side effects. For example, let’s consider a function that accepts a string as an argument and then writes that string to disk. We can consider the disk state as a side effect of the function. The function itself is perfectly deterministic (output string is a predictable and consistent function of input string), but depending on the implementation of side effects it may not be idempotent. If, for example, this function room simply added the output to a file “output.txt”, this file would grow with every incantation, which is not idempotent. If instead we overwrote the output file so that it reflects only the singular output of the previous run, then the side effects would also be deterministic, that would be idempotent. At a pedantic level you could redefine your scope of deterministic to not just include outputs, but also include the external state and side effects, but for practical purposes the above distinction is generally how deterministic and idempotent would be applied in practice in computing. I cannot speak to the math-centric view, if there is a different definition there.
    - 2y ago
no-dr-onboard 2y ago
I maintain the reproducible builds effort for my company and, please, let me tell you that this is the main pitfall of the whole effort. There is always going to be a degree of un-reproducibility just due to the nature of math. If you don't have the same system, same compiler version (down to the minor or patch level), same dependency versions, same build flags, filesystem ordering, OS handling etc. . .you're going to get differences. The RB project has readily disclosed that there is a degree of "significantly reproducible" sussing that each end user is going to have to do. The fact that the Debian maintainers chose not to display the degree of reproducibility is probably because showing low reproducibility scores undermines the efforts to evangelize the movement. I think that's understandable, but also is a bit of a two edged sword. If we don't disclose scores, we allow for the misrepresentation that "this is safe because it has the word reproducible in it". If we disclose scores, we get articles like this saying "wow, thats a really low score, wtf" and short lived paranoia gives way to ambivalence about the whole thing. It's difficult to capture the nuance in this in pithy tidbits, hence blog post on HN with me explaining this :).
- BonusPlay 2y ago
  From my experience, you either go full reproducible builds with nix, or none at all. Sitting in the middle results with additional downsides from modifying pipeline without core upsides of reproducible builds.
- kardos 2y ago
  The reproducible builds effort means same input (code, libraries, compiler, flags, build-environment), should give the same output (build artifacts). I don't think RB is trying to get reproducible across platforms and across varying compilers/dependencies -- that is a much bigger and much harder goal. > There is always going to be a degree of un-reproducibility just due to the nature of math. Fundamentally the math is deterministic (reproducible): if you do the same sequence of mathematical operations you get the same result. I gather you're getting at the non-associativity of floating point (eg additions), which is a fair point, but if you arrange to do your floating point operations in the same sequence then it will be reproducible.
alganet 2y ago
> (...) rebuilding packages using a bootsrappable build process, both seem orthogonal to the idempotent rebuild problem You know what would be awesome? If someone could start from, let's say, live-bootstrap[1] and build towards matching the checksums for some distro kernel+toolchain. It sounds like the same kind of problem, it all comes down to knowing what build conditions affect the resulting binaries, so I think you nailed the problem description on this and yes, it all feels very orthogonal from that perspective! Thanks for writing this blog entry! [1]: http://github.com/fosslinux/live-bootstrap http://github.com/fosslinux/live-bootstrap
simpaticoder 2y ago
Idempotent, deterministic builds are an argument in favor of synthetic virtual machines. Synthetic VMs like the JVM or CLR should, at least insofar as they don't contain native code, execute in a manner largely isolated from the vagaries of minor hardware/OS differences. Not an expert, but native VMs do not and cannot isolate processes from hardware details (e.g. Xen, Virtual Box), or from OS details (e.g. Docker, containerd).
- saagarjha 2y ago
  This is most true of software VMs too, which leak information via side channels.
nixosbestos 2y ago
Men will do anything except go to therapy ^H^H^H^H^H^H^H^H^H^H learn Nix.
- gaganyaan 2y ago
  It's odd that the article didn't mention nix, at least to say "We didn't like it for this reason".
  - hansvm 2y ago
    Nix's definition of "reproducible" is different from what the author says they want though. Nix gives you a similar system from a given config, when it works, where the author wants bitwise identical results (even when compiled at a much later point in time and on a different machine, which you can't accomplish just from caching (unless the caches are remotely hosted)). The reason they don't like Nix should be obvious; it blatantly and vocally doesn't even try to do the thing the authors want. It'd be just as relevant to bring up Gentoo or something -- another fine project, like Nix, but not especially helpful for the stated problem, and so obviously so that it shouldn't be worth paying lip service to in the article.
    - narrowbyte 2y ago
      "Doesn't even try" is too strong. "When compiling from the same source on independent infrastructure yields bit-by-bit identical results, this gives confidence that the build infrastructure was not compromised and the artifact really does correspond to the source." - https://reproducible.nixos.org/ https://reproducible.nixos.org/
      - hansvm 2y ago
        That's fair. Attempting to rationalize my choice of language: - Their homepage defines reproducibility to be something other than bitwise identical results. - Getting actual bitwise reproducible builds is still hard for most large projects, even with the work Nix has done (note that the quote you pulled doesn't actually say that Nix _does_ provide such builds, and the rest of that linked text just tries to highlight some of the tools you have at your disposal to achieve that). They do "try" insofar as they're aware of the desire for bitwise identical results, provide them in some cases, and provide tools to diagnose problems. They're also 20 years old and more than happy to call the current results reproducible. At the very least, it doesn't look like one of the top properties for the project.
xiande04 2y ago
Nix?
spyspy 2y ago
I spent some time trying to prove two go binaries were the same in the name of reproducible builds but couldn’t figure out if it was possible, even though I had built both myself and knew they were in effect the exact same. Go binaries have some sort of randomness (timestamp? Map entry? No idea) that I couldn’t pin down. Sometimes the hash of the binaries were the same and sometimes they weren’t. Short of cataloguing and hashing every file that went into the build I couldn’t figure it out and gave up.
- aleksi 2y ago
  It is possible to make Go builds reproducible. The first step might be to inspect two binaries with the diffoscope (https://diffoscope.org https://diffoscope.org).
compiler-guy 2y ago
For whatever it is worth, Google internal builds using the internal version of bazel are deterministic and reproducible. And google spends a lot of time and effort keeping them that way. You do have to ensure that nothing ever sorts based on pointer value, for example. Clang works fine as a compiler for this--there is nothing in it that normally produces different results due to timing or whatever. When something does leak in, we fix it upstream. You do have to ensure that no one uses __DATE__ or similar macros, or that you redefine them to a known value on the command line.
rsc 2y ago
Idempotent is a somewhat confusing word choice here. "Verifiable builds" seems more a accurate description of what they want. (See also https://go.dev/blog/rebuild https://go.dev/blog/rebuild.)

59 points by JNRowe 2y ago

I was expecting to see the word "yocto", did I miss it? This goes quite far along the path, building all the build tools and toolchain to the same version before building the packages.

ethegwo 2y ago

As I know, LLVM optimizer (maybe also GCC) is not idempotent, does it mean we need to pay performance for idempotent buildings?

bpfrh 2y ago
Shouldn't same system+same version+same flags produce the same result?
- jiehong 2y ago
  The algorithms used might not produce a deterministic result (like order is different), and maybe it also depends on timings of the CPU with threads scheduled on different cores, or faster/slower cores, etc. Deterministic builds aren't always that straightforward
  - 0x457 2y ago
    I'm using nix and clang/llvm - never have I ever got a different binary. If what you're saying is true - stage 3 bootstrap wouldn't be possible.
    - malkia 2y ago
      bit obvious, but all it takes something that takes something that changes everytime to make it non-reproducible - like __DATE__ and __TIME__
      - zaphar 2y ago
        Nix solves this by forcing __DATE__ and __TIME__ to be a single immutable value in the sandbox for all builds. If you look in the store the file timestamps will be this value.
  - plorkyeran 2y ago
    All C and C++ compilers in common use are single-threaded, and parallelism is achieved by compiling multiple files at once. An optimizer pass producing nondeterministic results due to a bug is not impossible, but would be a bug to fix. Multithreaded linkers which are expected to have nondeterministic results do exist, and you have to not use that for reproduce able builds. There's a long tail of tricky problems to solve for reproducible builds, but a specific build of a compiler producing different executable code from run to run hasn't really been one of them.
    - bobmcnamara 2y ago
      Now I'm wondering how differently my multithreaded tcc fork produces code. I don't think it should but it always wouldn't surprise me if there was some shared state remaining.
  - kardos 2y ago
    Forcing the ordering to be deterministic is a well-established part of the process https://reproducible-builds.org/docs/stable-inputs/ https://reproducible-builds.org/docs/stable-inputs/ https://reproducible-builds.org/docs/stable-outputs/ https://reproducible-builds.org/docs/stable-outputs/
patmorgan23 2y ago
Compilation performance or end executable performance?
- ethegwo 2y ago
  The latter I mean, conservative optimization level is benefit to keep idempotency
compiler-guy 2y ago
Google takes great care to ensure that the LLVM optimizer produces bit-identical results for identical inputs across plenty of machines. If the llvm optimizer produced non-bit-identical results for identical inputs (all sources and command-line flags), Google would consider that a high priority bug. So I'm reasonably sure it does produce bit-identical results.

vzaliva 2y ago

Coming from maths, I am confused by use of the term "idempotent" here. Unless we are talking about bootstrapping a compiler and I do not see how it applicable here. Am I missing something?

algernonramone 2y ago
I feel that "deterministic" is probably a better word here than "idempotent".
- craigching 2y ago
  Maybe even hermetic builds? https://bazel.build/basics/hermeticity https://bazel.build/basics/hermeticity
- appplication 2y ago
  Not speaking to your comment specifically, but adding context to the thread: idempotence would mean having the same result, regardless of whether you run something once, twice, or 10 times, over the same input set. Idempotence requires but goes beyond determinism, as it also accounts for any externalities and side effects. For example, let’s consider a function that accepts a string as an argument and then writes that string to disk. We can consider the disk state as a side effect of the function. The function itself is perfectly deterministic (output string is a predictable and consistent function of input string), but depending on the implementation of side effects it may not be idempotent. If, for example, this function room simply added the output to a file “output.txt”, this file would grow with every incantation, which is not idempotent. If instead we overwrote the output file so that it reflects only the singular output of the previous run, then the side effects would also be deterministic, that would be idempotent. At a pedantic level you could redefine your scope of deterministic to not just include outputs, but also include the external state and side effects, but for practical purposes the above distinction is generally how deterministic and idempotent would be applied in practice in computing. I cannot speak to the math-centric view, if there is a different definition there.
  - 2y ago

no-dr-onboard 2y ago

I maintain the reproducible builds effort for my company and, please, let me tell you that this is the main pitfall of the whole effort. There is always going to be a degree of un-reproducibility just due to the nature of math. If you don't have the same system, same compiler version (down to the minor or patch level), same dependency versions, same build flags, filesystem ordering, OS handling etc. . .you're going to get differences. The RB project has readily disclosed that there is a degree of "significantly reproducible" sussing that each end user is going to have to do. The fact that the Debian maintainers chose not to display the degree of reproducibility is probably because showing low reproducibility scores undermines the efforts to evangelize the movement. I think that's understandable, but also is a bit of a two edged sword. If we don't disclose scores, we allow for the misrepresentation that "this is safe because it has the word reproducible in it". If we disclose scores, we get articles like this saying "wow, thats a really low score, wtf" and short lived paranoia gives way to ambivalence about the whole thing. It's difficult to capture the nuance in this in pithy tidbits, hence blog post on HN with me explaining this :).

BonusPlay 2y ago
From my experience, you either go full reproducible builds with nix, or none at all. Sitting in the middle results with additional downsides from modifying pipeline without core upsides of reproducible builds.
kardos 2y ago
The reproducible builds effort means same input (code, libraries, compiler, flags, build-environment), should give the same output (build artifacts). I don't think RB is trying to get reproducible across platforms and across varying compilers/dependencies -- that is a much bigger and much harder goal. > There is always going to be a degree of un-reproducibility just due to the nature of math. Fundamentally the math is deterministic (reproducible): if you do the same sequence of mathematical operations you get the same result. I gather you're getting at the non-associativity of floating point (eg additions), which is a fair point, but if you arrange to do your floating point operations in the same sequence then it will be reproducible.

alganet 2y ago

> (...) rebuilding packages using a bootsrappable build process, both seem orthogonal to the idempotent rebuild problem You know what would be awesome? If someone could start from, let's say, live-bootstrap[1] and build towards matching the checksums for some distro kernel+toolchain. It sounds like the same kind of problem, it all comes down to knowing what build conditions affect the resulting binaries, so I think you nailed the problem description on this and yes, it all feels very orthogonal from that perspective! Thanks for writing this blog entry! [1]: http://github.com/fosslinux/live-bootstrap http://github.com/fosslinux/live-bootstrap

simpaticoder 2y ago

Idempotent, deterministic builds are an argument in favor of synthetic virtual machines. Synthetic VMs like the JVM or CLR should, at least insofar as they don't contain native code, execute in a manner largely isolated from the vagaries of minor hardware/OS differences. Not an expert, but native VMs do not and cannot isolate processes from hardware details (e.g. Xen, Virtual Box), or from OS details (e.g. Docker, containerd).

saagarjha 2y ago
This is most true of software VMs too, which leak information via side channels.

nixosbestos 2y ago

Men will do anything except go to therapy ^H^H^H^H^H^H^H^H^H^H learn Nix.

gaganyaan 2y ago
It's odd that the article didn't mention nix, at least to say "We didn't like it for this reason".
- hansvm 2y ago
  Nix's definition of "reproducible" is different from what the author says they want though. Nix gives you a similar system from a given config, when it works, where the author wants bitwise identical results (even when compiled at a much later point in time and on a different machine, which you can't accomplish just from caching (unless the caches are remotely hosted)). The reason they don't like Nix should be obvious; it blatantly and vocally doesn't even try to do the thing the authors want. It'd be just as relevant to bring up Gentoo or something -- another fine project, like Nix, but not especially helpful for the stated problem, and so obviously so that it shouldn't be worth paying lip service to in the article.
  - narrowbyte 2y ago
    "Doesn't even try" is too strong. "When compiling from the same source on independent infrastructure yields bit-by-bit identical results, this gives confidence that the build infrastructure was not compromised and the artifact really does correspond to the source." - https://reproducible.nixos.org/ https://reproducible.nixos.org/
    - hansvm 2y ago
      That's fair. Attempting to rationalize my choice of language: - Their homepage defines reproducibility to be something other than bitwise identical results. - Getting actual bitwise reproducible builds is still hard for most large projects, even with the work Nix has done (note that the quote you pulled doesn't actually say that Nix _does_ provide such builds, and the rest of that linked text just tries to highlight some of the tools you have at your disposal to achieve that). They do "try" insofar as they're aware of the desire for bitwise identical results, provide them in some cases, and provide tools to diagnose problems. They're also 20 years old and more than happy to call the current results reproducible. At the very least, it doesn't look like one of the top properties for the project.

xiande04 2y ago

Nix?

spyspy 2y ago

I spent some time trying to prove two go binaries were the same in the name of reproducible builds but couldn’t figure out if it was possible, even though I had built both myself and knew they were in effect the exact same. Go binaries have some sort of randomness (timestamp? Map entry? No idea) that I couldn’t pin down. Sometimes the hash of the binaries were the same and sometimes they weren’t. Short of cataloguing and hashing every file that went into the build I couldn’t figure it out and gave up.

aleksi 2y ago
It is possible to make Go builds reproducible. The first step might be to inspect two binaries with the diffoscope (https://diffoscope.org https://diffoscope.org).

compiler-guy 2y ago

For whatever it is worth, Google internal builds using the internal version of bazel are deterministic and reproducible. And google spends a lot of time and effort keeping them that way. You do have to ensure that nothing ever sorts based on pointer value, for example. Clang works fine as a compiler for this--there is nothing in it that normally produces different results due to timing or whatever. When something does leak in, we fix it upstream. You do have to ensure that no one uses __DATE__ or similar macros, or that you redefine them to a known value on the command line.

rsc 2y ago

Idempotent is a somewhat confusing word choice here. "Verifiable builds" seems more a accurate description of what they want. (See also https://go.dev/blog/rebuild https://go.dev/blog/rebuild.)