PGO, HashMaps and build inputs

[kpcyrd]

Hello!

following up on an IRC discussion about PGO profiling on the build server 
causing undeterministic binaries, I made a simple repository to demo this - 
there's other ways to achieve the same effect (like race-y readiness of e.g. 
file descriptors due to disk speed, causing different code branches to be taken).

https://github.com/kpcyrd/pgo-hashmap-unreproducible

PGO stands for "profile guided optimizations" and works by building an 
instrumented binary `gcc -O2 -fprofile-generate=profile`, running test cases on 
the binary, then using the measured code paths to hint to the compiler which 
paths are hot and which ones are cold, building the release binary with `gcc -O2 
-fprofile-use=profile`.

To manually hint control flow probability, the following options are available:
- https://doc.rust-lang.org/std/hint/fn.cold_path.html
- https://clang.llvm.org/docs/LanguageExtensions.html#builtin-expect

Back to PGO, the specific example I went for are HashMaps. As a quick recap of 
how they work, instead of putting values in a list and having to scan the entire 
list every time I want to find a value, a hashmap defines a number of buckets. 
To decide which bucket to use for which key, the key is hashed using a very fast 
hash function (it doesn't need to be cryptographically secure, it just needs to 
evenly distribute across the buckets as fast as possible).

     map = [bucket, bucket, bucket, ...]
     bucket_index = H(key)
     map[bucket_index]

But what's inside the bucket slots? Ideally each slot only ever holds one value, 
but for the worst-case scenario of two keys hashing to the same bucket, we still 
have a list in each slot that we are going to scan through. This, obviously, 
doesn't perform well and should only happen rarely.

At some point people figured out, since the hash function is often known, they 
could come up with a list of keys that would all get sorted into the same 
bucket, essentially turning the hashmap into a list. When putting all those 
colliding keys into a POST request, they could waste the servers CPU time 
effectively.

To stop this from happening people switched to a keyed hash function. The 
program generates a random number (once per process is often enough), this 
number is supposed to stay secret and is used to key the hash function. This 
needs to happen at runtime obviously, we can't just put this number into the 
binary for anyone to see.

     secret = random()
     map = [bucket, bucket, bucket, ...]
     bucket_index = keyed_H(key, secret)
     map[bucket_index]

Without knowing the secret value, it's not possible anymore to reliably generate 
keys that all sort into the same bucket.

However, if we insert 1.000 keys, the value of random() is now going to 
influence the number of collisions we are going to get, causing different 
weights on the code branches executed. The compiler may decide to optimize the 
binary differently when more collisions happened, versus one with less collisions.

The repo contains a diffoscope.txt showing the different assembly generated.

This is what the repository demonstrates. It doesn't implement a full hashmap, 
rather a toy hashset, but it does it good enough to demonstrate how code that 
produces binaries that are perfectly reproducible without PGO, become 
unreproducible with PGO enabled.

Some projects benefit heavily from optimizations possible with those profiles 
(probably too much to ignore). I suggest they could be a documented build input 
however, instead of attempting to generate them on the fly. Either as a regular 
build input like source code, or as part of "the build environment", meaning 
it's an additional output of the initial build, like buildinfo files.

People liked the example repo (to have something to play around with), so I 
figured it might be worth sharing on the list too.

See you on the summit next week. :)

cheers,
kpcyrd