Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Bit-for-bit deterministic / reproducible builds #34902

Closed
infinity0 opened this issue Jul 18, 2016 · 76 comments
Closed

Bit-for-bit deterministic / reproducible builds #34902

infinity0 opened this issue Jul 18, 2016 · 76 comments

Comments

@infinity0
Copy link
Contributor

@infinity0 infinity0 commented Jul 18, 2016

It would be good if rustc could generate bit-for-bit reproducible results, even in the presence of minor system environment differences. Currently we have quite a large diff: e.g. see txt diff for 1.9.0 or perhaps txt diff for 1.10.0 a few days after I'm posting this. (You might want to "save link as" instead of displaying it directly in the browser.)

Much of the diff output is due to build-id differences, which can be ignored since they are caused by other deeper issues and will go away once these deeper issues are fixed. One example of a deeper issue is this:

│   │   │   ├── ./usr/lib/i386-linux-gnu/librustc_data_structures-e8edd0fd.so
│   │   │   │   ├── readelf --wide --file-header {}
│   │   │   │   │ @@ -6,15 +6,15 @@
│   │   │   │   │    OS/ABI:                            UNIX - System V
│   │   │   │   │    ABI Version:                       0
│   │   │   │   │    Type:                              DYN (Shared object file)
│   │   │   │   │    Machine:                           Intel 80386
│   │   │   │   │    Version:                           0x1
│   │   │   │   │    Entry point address:               0x4620
│   │   │   │   │    Start of program headers:          52 (bytes into file)
│   │   │   │   │ -  Start of section headers:          338784 (bytes into file)
│   │   │   │   │ +  Start of section headers:          338780 (bytes into file)
│   │   │   │   │    Flags:                             0x0
│   │   │   │   │    Size of this header:               52 (bytes)
│   │   │   │   │    Size of program headers:           32 (bytes)
│   │   │   │   │    Number of program headers:         8
│   │   │   │   │    Size of section headers:           40 (bytes)
│   │   │   │   │    Number of section headers:         30
│   │   │   │   │    Section header string table index: 29
│   │   │   │   ├── readelf --wide --program-header {}

Here are the system variations that might be causing these issues. I myself am not that familiar with ELF, but perhaps someone else here would know why the section header is 4 bytes later in the first vs second builds.

@steveklabnik
Copy link
Member

@steveklabnik steveklabnik commented Jul 18, 2016

In general, being reproducible is something we're interested in; we try to tackle it bug by bug.

@eefriedman
Copy link
Contributor

@eefriedman eefriedman commented Jul 18, 2016

This probably has some obvious cause:

│   │   │   │ -<h4 id='method.unzip' class='method'><code>fn <a href='../../core/iter/trait.Iterator.html#method.unzip' class='fnname'>unzip</a>&lt;A, B, FromA, FromB&gt;(self) -&gt; (FromA, FromB) <span class='where'>where FromB: <a class='trait' href='../../core/default/trait.Default.html' title='core::default::Default'>Default</a> + <a class='trait' href='../../core/iter/trait.Extend.html' title='core::iter::Extend'>Extend</a>&lt;B&gt;, FromA: <a class='trait' href='../../core/default/trait.Default.html' title='core::default::Default'>Default</a> + <a class='trait' href='../../core/iter/trait.Extend.html' title='core::iter::Extend'>Extend</a>&lt;A&gt;, Self: <a class='trait' href='../../core/iter/trait.Iterator.html' title='core::iter::Iterator'>Iterator</a>&lt;Item=(A, B)&gt;</span></code></h4>
│   │   │   │ +<h4 id='method.unzip' class='method'><code>fn <a href='../../core/iter/trait.Iterator.html#method.unzip' class='fnname'>unzip</a>&lt;A, B, FromA, FromB&gt;(self) -&gt; (FromA, FromB) <span class='where'>where FromB: <a class='trait' href='../../core/default/trait.Default.html' title='core::default::Default'>Default</a> + <a class='trait' href='../../core/iter/trait.Extend.html' title='core::iter::Extend'>Extend</a>&lt;B&gt;, Self: <a class='trait' href='../../core/iter/trait.Iterator.html' title='core::iter::Iterator'>Iterator</a>&lt;Item=(A, B)&gt;, FromA: <a class='trait' href='../../core/default/trait.Default.html' title='core::default::Default'>Default</a> + <a class='trait' href='../../core/iter/trait.Extend.html' title='core::iter::Extend'>Extend</a>&lt;A&gt;</span></code></h4>

If someone wants to look at the code generation differences, it's probably best to start with libcore. The reproducible-builds.org diff isn't that useful for that because it doesn't recognize .rlib files as archives.

@infinity0
Copy link
Contributor Author

@infinity0 infinity0 commented Jul 18, 2016

Thanks for the heads up, I just added AR support in diffoscope and hopefully the diff output will see that in the next few weeks, when the website updates.

@infinity0
Copy link
Contributor Author

@infinity0 infinity0 commented Aug 16, 2016

Here's a diff of rust.metadata.bin from libcore.rlib, from 1.10.0. (2.0 MB, ~1700 lines, might make your browser slow.) Mostly ordering differences. @eddyb has suggested HashMap ordering as a culprit, and that would be replaced with FnvHashMap instead.

@eddyb
Copy link
Member

@eddyb eddyb commented Aug 16, 2016

If it's a HashMap, I don't know which one. cc @rust-lang/compiler

@infinity0
Copy link
Contributor Author

@infinity0 infinity0 commented Aug 20, 2016

I tried replacing HashMap with FnvHashMap in src/librustc_metadata/loader.rs but it didn't seem to help. Here is the Makefile i'm using to automate my rebuilds:

TRIPLET = x86_64-unknown-linux-gnu

all: libcore.diff

libcore.diff: rust.metadata.bin.1 rust.metadata.bin.2
    diffoscope --html-dir "$@" rust.metadata.bin.1 rust.metadata.bin.2 \
        --max-diff-block-lines 5000 \
        --max-diff-input-lines 10000000 \
        --max-report-size 204800000; true # diffoscope returns 1 for "there were diffs"

rust.metadata.bin.1 rust.metadata.bin.2: Makefile
    rm -f $(TRIPLET)/stage2/lib/rustlib/$(TRIPLET)/lib/libcore-*.rlib
    rm -f $(TRIPLET)/stage2/lib/rustlib/$(TRIPLET)/lib/stamp.core
    $(MAKE) $(TRIPLET)/stage2/lib/rustlib/$(TRIPLET)/lib/stamp.core
    ar x $(TRIPLET)/stage2/lib/rustlib/$(TRIPLET)/lib/libcore-*.rlib rust.metadata.bin
    mv rust.metadata.bin "$@"

.PHONY: all rust.metadata.bin.1 rust.metadata.bin.2

perhaps i'm Doing It Wrong.

@infinity0
Copy link
Contributor Author

@infinity0 infinity0 commented Aug 20, 2016

As background, HashMap in rust is non-deterministic to protect against certain types of DoS attack. You can switch it to the deterministic FnvHashMap if you're sure your code will always be called in a safe manner. This ought to be true for rustc itself. (I notice some online "try-it-yourself" rust web services let me run "ls /" and other shell commands, so I could also exploit this HashMap ordering issue, but I also assume that they're clever enough to set a ulimit and/or containerise the thing.)

@jonas-schievink
Copy link
Member

@jonas-schievink jonas-schievink commented Aug 22, 2016

I wrote a small script to diff metadata (I couldn't really get the makefile to work).

It looks like even more is changing between two compiles using the current master (or nightly): The crate hash and/or disambiguator, which are stored right after the target triple. @infinity0 can you confirm?

EDIT: That might get fixed by #35854

@jonas-schievink
Copy link
Member

@jonas-schievink jonas-schievink commented Aug 22, 2016

Okay, apparently replacing Hash{Map,Set} in resolve with FnvHash{Map,Set} got rid of the first (smaller) blocks of the diff. The big block at the bottom is still there. Will continue to randomly sed the compiler and report back ;)

@jonas-schievink
Copy link
Member

@jonas-schievink jonas-schievink commented Aug 22, 2016

The remaining issue is that (some?) predicates are encoded in non-deterministic order. Maybe we need to do this for all bounds? Not sure what would be the correct way to do that (or why these are nondeterministic in the first place).

@michaelwoerister
Copy link
Member

@michaelwoerister michaelwoerister commented Aug 22, 2016

Just for reference, there's this: #34805

@jonas-schievink
Copy link
Member

@jonas-schievink jonas-schievink commented Aug 22, 2016

@michaelwoerister Thanks! Too tired to think about it currently. Will have a look tomorrow :)

jonas-schievink added a commit to jonas-schievink/rust that referenced this issue Aug 22, 2016
* A step towards rust-lang#34902
* More stable error messages in some places related to crate loading
* Possible slight performance improvements since all `HashMap`s
  replaced had small keys where `FnvHashMap` should be faster
  (although I didn't measure)
@sanxiyn
Copy link
Member

@sanxiyn sanxiyn commented Aug 23, 2016

#24473 is rustdoc subset of this.

eddyb added a commit to eddyb/rust that referenced this issue Aug 23, 2016
Use `FnvHashMap` in more places

* A step towards rust-lang#34902 (see my comments there)
* More stable error messages in some places related to crate loading
* Possible slight performance improvements since all `HashMap`s
  replaced had small keys where `FnvHashMap` should be faster
  (although I didn't measure)

(likewise for `HashSet` -> `FnvHashSet`)
jonas-schievink added a commit to jonas-schievink/rust that referenced this issue Aug 23, 2016
`ty::Predicate` was being used as a key for a hash map, but its hash
implementation indirectly hashed addresses, which vary between each
compiler run. This is fixed by sorting predicates by their ID before
encoding them.

This *should* basically fix issue rust-lang#34902, although landing a test would
be nice (I also didn't test a scenario where multiple crates were
involved, only libcore).
jonas-schievink added a commit to jonas-schievink/rust that referenced this issue Aug 23, 2016
`ty::Predicate` was being used as a key for a hash map, but its hash
implementation indirectly hashed addresses, which vary between each
compiler run. This is fixed by sorting predicates by their ID before
encoding them.

In my tests, rustc is now able to produce deterministic results when
compiling libcore and libstd.

I've beefed up `run-make/reproducible-build` to compare the produced
artifacts bit-by-bit. This doesn't catch everything, but should be a
good start.

cc rust-lang#34902
jonas-schievink added a commit to jonas-schievink/rust that referenced this issue Aug 24, 2016
`ty::Predicate` was being used as a key for a hash map, but its hash
implementation indirectly hashed addresses, which vary between each
compiler run. This is fixed by sorting predicates by their ID before
encoding them.

In my tests, rustc is now able to produce deterministic results when
compiling libcore and libstd.

I've beefed up `run-make/reproducible-build` to compare the produced
artifacts bit-by-bit. This doesn't catch everything, but should be a
good start.

cc rust-lang#34902
jonas-schievink added a commit to jonas-schievink/rust that referenced this issue Aug 25, 2016
* A step towards rust-lang#34902
* More stable error messages in some places related to crate loading
* Possible slight performance improvements since all `HashMap`s
  replaced had small keys where `FnvHashMap` should be faster
  (although I didn't measure)
jonas-schievink added a commit to jonas-schievink/rust that referenced this issue Aug 25, 2016
`ty::Predicate` was being used as a key for a hash map, but its hash
implementation indirectly hashed addresses, which vary between each
compiler run. This is fixed by sorting predicates by their ID before
encoding them.

In my tests, rustc is now able to produce deterministic results when
compiling libcore and libstd.

I've beefed up `run-make/reproducible-build` to compare the produced
artifacts bit-by-bit. This doesn't catch everything, but should be a
good start.

cc rust-lang#34902
bors added a commit that referenced this issue Aug 26, 2016
Steps towards reproducible builds

cc #34902

Running `make dist` twice will result in a rustc tarball where only `librustc_back.so`, `librustc_llvm.so` and `librustc_trans.so` differ. Building `libstd` and `libcore` twice with the same compiler and flags produces identical artifacts.

The third commit should close #24473
jonas-schievink added a commit to jonas-schievink/rust that referenced this issue Aug 27, 2016
* A step towards rust-lang#34902
* More stable error messages in some places related to crate loading
* Possible slight performance improvements since all `HashMap`s
  replaced had small keys where `FnvHashMap` should be faster
  (although I didn't measure)
jonas-schievink added a commit to jonas-schievink/rust that referenced this issue Aug 27, 2016
`ty::Predicate` was being used as a key for a hash map, but its hash
implementation indirectly hashed addresses, which vary between each
compiler run. This is fixed by sorting predicates by their ID before
encoding them.

In my tests, rustc is now able to produce deterministic results when
compiling libcore and libstd.

I've beefed up `run-make/reproducible-build` to compare the produced
artifacts bit-by-bit. This doesn't catch everything, but should be a
good start.

cc rust-lang#34902
bors added a commit that referenced this issue Aug 28, 2016
Steps towards reproducible builds

cc #34902

Running `make dist` twice will result in a rustc tarball where only `librustc_back.so`, `librustc_llvm.so` and `librustc_trans.so` differ. Building `libstd` and `libcore` twice with the same compiler and flags produces identical artifacts.

The third commit should close #24473
bors added a commit that referenced this issue Aug 28, 2016
Steps towards reproducible builds

cc #34902

Running `make dist` twice will result in a rustc tarball where only `librustc_back.so`, `librustc_llvm.so` and `librustc_trans.so` differ. Building `libstd` and `libcore` twice with the same compiler and flags produces identical artifacts.

The third commit should close #24473
@nikomatsakis
Copy link
Contributor

@nikomatsakis nikomatsakis commented Sep 2, 2016

Potentially relevant, from IRC:

<eddyb> nmatsakis, infinity0: fwiw, I just found another hash table. not random, but may cause issues around incremental recompilation. see rustc_metadata::encoder::encode_reachable (the reachable NodeSet)

though I think that it's not a big issue unless the hashtable is truly random.

@infinity0
Copy link
Contributor Author

@infinity0 infinity0 commented Dec 6, 2019

Sadly 1.39.0 did not reproduce for me when varying the build-path, could you take a look @jgalenson? I believe all the PRs you mentioned above should be part of that version and I also added the compiler-builtins patch specifically to Debian's rustc. The reproducible builds project website has a summary diff but I've uploaded a more detailed version here. If you enable javascript you can click or shift-click the -/+ to expand/collapse (recursively with shift) the different entries.

@infinity0
Copy link
Contributor Author

@infinity0 infinity0 commented Dec 6, 2019

I've also uploaded the build artifacts here and here. If you're not on a Debian system you can extract .deb files directly with ar xf.

@infinity0
Copy link
Contributor Author

@infinity0 infinity0 commented Dec 6, 2019

Also we use a slightly customised config.toml. In particular, debuginfo-level and debuginfo-level-std are both 2.

@jgalenson
Copy link

@jgalenson jgalenson commented Dec 6, 2019

First of all, thanks for looking into this! That dashboard should be a great way to keep tabs on this and spot regressions (once we get it greener).

I wouldn't actually expect builds with debuginfo to be deterministic across different build paths. Can you disable that line and see what changes? And if that does help, do you need it enabled?

In addition, from that config.toml file it looks like you're passing --remap-path-prefix via RUSTFLAGS (in the rules file). I remember that didn't work well for me, and so I instead used the remap-debuginfo config.toml file (see jgalenson/reproducible-rustc@cdf504e for a brief explanation of this). Can you try that as well?

@infinity0
Copy link
Contributor Author

@infinity0 infinity0 commented Dec 6, 2019

Hey thanks for the quick response.

I wouldn't actually expect builds with debuginfo to be deterministic across different build paths. Can you disable that line and see what changes? And if that does help, do you need it enabled?

I will try it, give me a few days. However as I remember, one of the main reason for that flag even existing in the first place is for debuginfo - see #41555 and related issues - so it really ought to be working, and I seem to remember that it worked fine before.

--remap-path-prefix via RUSTFLAGS (in the rules file). I remember that didn't work well for me,

Yes, I fixed this recently in #66834 and included this patch in this Debian version. If I rg the build logs I can see this flag being passed fine.

@infinity0
Copy link
Contributor Author

@infinity0 infinity0 commented Dec 6, 2019

The first string difference is at https://tests.reproducible-builds.org/debian/dbd/unstable/amd64/rustc_1.39.0+dfsg1-2.diffoscope.html#libstd-rust--.--_-.--.--dfsg---_amd--.deb---data.tar.xz---data.tar---.-usr-lib-x--_---linux-gnu-librustc_macros-ce-d-----e------.so---readelf---wide---decompress---hex-dump-.rodata---.

This comes from code in the syn crate:

$ rg "unknown.delimiter"
vendor/syn-0.15.35/src/token.rs
942:            _ => panic!("unknown delimiter: {}", s),

Then again some other stuff seems unrelated to build paths, so maybe someone added a nondeterministic hash table again. (If you scroll slightly down you can even see a deterministically-remapped path starting /usr/src which is where we remap it to in Debian.)

Not sure if many people know this but 1.19.0 was already "nearly reproducible" (see my comments further up from 2 years ago) and so it seems adding some integration tests is really vital to actually maintaining this property.

@jgalenson
Copy link

@jgalenson jgalenson commented Dec 6, 2019

Ever since I first got my builds to reproduce, I've been running a script daily that builds rustc twice and compares the output, and it hasn't regressed yet. Having this integrated into the official test suite is of course a much better solution, but at least with my setup there haven't been any regressions so far.

I'll look into getting this to work with debuginfo next week.

@tarcieri
Copy link

@tarcieri tarcieri commented Dec 6, 2019

@jgalenson awesome! I'm working on a project for BFT consensus-driven proofs of reproducible builds, and that'd make an amazing test case: https://github.com/iqlusioninc/synchronicity

@jgalenson
Copy link

@jgalenson jgalenson commented Dec 13, 2019

I was able to get reproducible builds of rustc with debuginfo by upgrading to a newer version of the compiler_builtins crate that contains rust-lang/compiler-builtins@ca423fe (so at least 0.1.20 should work, although I used 0.1.22). With that, I no longer needed my last remaining patch.

I also had to use a newer C++ compiler that supports the -ffile-prefix-map argument. gcc-8 does, but unfortunately using it did not work (it seems to embed source paths into files generated from assembly). However, since https://reviews.llvm.org/D49466 was merged, Clang supports that option now, so using a random nightly build of LLVM from a few days ago worked.

That's a convoluted setup, but @infinity0, can you reproduce it? Your diff seemed to contain some other differences mine did not, so some things might remain.

@tarcieri that seems pretty cool. Have you gotten it working yet?

@infinity0
Copy link
Contributor Author

@infinity0 infinity0 commented Dec 29, 2019

@jgalenson I'm already including that compiler-builtins -ffile-prefix-map patch in Debian's rustc and it doesn't work, though we're using GCC not LLVM. What exactly is this issue with "it seems to embed source paths into files generated from assembly" you are talking about? I don't remember seeing that last time I was working on GCC reproducibility a few years ago.

tests.r-b.org results for rustc 1.39 are out the results are pretty similar to mine above - unreproducible including build paths relating to the syn crate.

@infinity0
Copy link
Contributor Author

@infinity0 infinity0 commented Dec 29, 2019

I should mention that the differences include more that just C++ compiler output, which is what you seem to be suggesting is the last remaining thing, from your previous comment. My own testing and tests.r-b.org's testing indicates otherwise. At least the syn crate is embedding build paths.

@jgalenson
Copy link

@jgalenson jgalenson commented Dec 30, 2019

I investigated the gcc bug I mentioned. If I take a trivial .c file and compile it with -g and -ffile-prefix-map, I don't see source paths in the output. But if I use the same command line for a trivial assembly file, I do see source paths in the output. Those go away if I change -ffile-prefix-map to -fdebug-prefix-map. I see this with gcc 8.3 but not with recent LLVM builds. Can you reproduce that?

This comes up because compiler-builtins includes a few .S files. This miscompilation then causes a number of other crates to be non-reproducible, including rustc_{driver,llvm} and cargo. Those all go away one I use Clang instead of gcc. I don't, however, see a difference in syn.

The tests.r-b.org link you posted no longer works for me because it seems to fail to build. But if you can send me the config.toml you're using, I'll see if I can reproduce it myself. In addition, you can try using my config and adding in debuginfo-level{,-std,-tools} = 2 and using a recent Clang.

@comex
Copy link
Contributor

@comex comex commented Jan 22, 2020

Filed https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93371 for the GCC bug. As a short-term workaround, compiler-builtins could pass both -ffile-prefix-map and -fdebug-prefix-map...

@infinity0
Copy link
Contributor Author

@infinity0 infinity0 commented Aug 5, 2020

I didn't get around to looking into the above issues in more detail, but I just noticed that tests.r-b.org for rustc has been showing "reproducible" for 1.44.1 including under varying build paths (unstable, experimental)!

1.45.0 is in-progress and we should have results in just a few more days.

@sanxiyn
Copy link
Member

@sanxiyn sanxiyn commented Aug 6, 2020

We should use individual issues tagged A-reproducibility going forward. Closing.

@sanxiyn sanxiyn closed this Aug 6, 2020
@infinity0
Copy link
Contributor Author

@infinity0 infinity0 commented Aug 7, 2020

OK, well results for 1.45.0 say "unreproducible" again, and the auto-generated diff did not complete after 2 hours. Shall I open an issue for CI integration tests on this? If I understand correctly there are concerns about it taking up too much resources, or something.

@sanxiyn
Copy link
Member

@sanxiyn sanxiyn commented Aug 10, 2020

Yes, I think we should open a new issue for reproducible build CI. I also think it would be impractical for a while due to computational demand, but then I am not a member of infra team.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet