please consider using a 128 bit fast build-id

[llvmbot]

Bugzilla Link	44138
Version	unspecified
OS	Linux
Reporter	LLVM Bugzilla Contributor
CC	@rui314,@smithp35

Extended Description

lld defaults to a fast build-id hash (which is currently xxhash). That produces a 64 bit hash.

The other hash options are md5 and sha1, which are probably a bit too slow to be the default. Linking a release version of scylla with split dwarf I get:

none 2.022252056 seconds
fast 2.061659922 seconds
md5 2.740843349 seconds
sha1 2.318114449 seconds

One issue with fast producing a 64 bit hash is that rpm considers it too small. I initially reported it as a problem in rpm (rpm-software-management/rpm#950), but there is an argument why given the birthday problem and the desire to have a small probability of a collision on an entire distro 64 bits might not be enough.

I wonder if there is 128 bit hash that would be fast enough to be the default. Farmhash comes to mind.

[rui314]

If they want to make a build-id globally unique, I don't think using 128-bit non-cryptographic hash function can be a solution, as it is not collision-resistant.

One thing we should try is to optimize the SHA implementation in LLVM so that it uses SHA1 acceleration instructions. That might be able to bring the performance of SHA1 to the point that we are just fine with that.

[llvmbot]

If they want to make a build-id globally unique, I don't think using 128-bit
non-cryptographic hash function can be a solution, as it is not
collision-resistant.

I think the non-cryptographic versus cryptographic issue is independent. The request is not that it is hard for a malicious agent to produce a collision, it is that every binary produced over the entire lifespan of a distro has a high probability of being unique.

There is some analysis at
rpm-software-management/rpm#950 (comment)

One thing we should try is to optimize the SHA implementation in LLVM so
that it uses SHA1 acceleration instructions. That might be able to bring the
performance of SHA1 to the point that we are just fine with that.

But this is an awesome idea anyway. If that makes sha1 fast enough we might as well use it, and if it doesn't, a faster sha1 is always nice.

[rui314]

Does anyone want to try to add a hardware-accelerated SHA function? Intel and AMD CPUs have the special-purpose SHA1 acceleration instructions for years, so it is now available on most computers. I don't think that you need to actually write code to compute SHA1 because I believe there's a reference implementation that uses the acceleration instructions.

Clang and GCC have intrinsic for the instructions, so you don't have to write assembly.

[Andarwinux]

There is now XXH128 (XXH3 128-bit variant).