[patch rfc]: use xxhash() in ld build-id computation, incl. benchmark

[Mark Wielaard]

Hi,

On Tue, 2024-09-17 at 17:27 -0400, Frank Ch. Eigler wrote:
> > Introducing a new --build-id= value requires the ecosystem to adapt.
> 
> I'm not sure I see why.  Build-ids for any given binary may be
> computed or set any way at all, independent of other binaries or the
> rest of the ecosystem.

I don't think that is really true. The way and the "strength" of the
build-id calculation matter. This is only true if the way the build-id
is calculated is really reproducible, has strong collission resistance
properties and nothing depends on the way the build-id is calculated.
e.g. using --build-id=uuid (not reproducible) or --build-id=0xhexstring
(strong possibility it will collide) are fundementally different from
using --build-id=md5 or --build-id=sha1

(I am probably using the term strong collision resistance wrongly here,
it is one property of a cryptographic hash functions, but we don't need
one of these here.)

I do think it is true for what you are proposing here though. I would
say that build-ids calculated through md5, sha or your proposed xx are
interchangeble even though they use different lengths (because they are
at least 128bit and strongly "random").

> > Therefore, lld/mold's --build-id=fast never gets wide adoption.
> 
> I'm not sure whether why that would be or why it should be a
> consideration for an improvement in binutils.

lld --build-id=fast generates only an 8byte/64bit build-id, which is
why nobody is using that.

> > sha1 is 160 bits, wider than 128 bits, which many fast hash
> > implementations support.  lld and mold truncate BLAKE3's 256-bit
> > digest to 128/160 for md5/sha1 :)
> 
> Digest width is an interesting question, yes.  I don't recall which
> newfangled linker it was, but some years ago, someone proposed that it
> should use an 8-byte (64-bit) buildid, because of speed.  We were not
> a big fan.
> 
> We did some calculations and some checking of the debuginfod buildid
> corpus (which as of today includes ~100 million distinct buildids in
> the public federated servers).  That starts to come foreseeably close
> to 32-bits, and considering the birthday paradox, needing at least 64
> bits to reliably tell apart.  But 128 bits ought to be enough for
> anybody.

I would say if the speedup is really as much as you say then just make
this the default and maybe just use it for md5 or sha1 (with a little
padding) too. Assuming people don't depend on the particular algorithm
used, but just want a strong 128bit+ build-id.

But it would be good to document these calculations somewhere so we are
really sure 128 bits are enough for any binary.

Cheers,

Mark