[patch] switch to xxhash for buildid recomputation

[Frank Ch. Eigler]

Hi, Mark -

> I think we shouldn't zero-pad, just replace the first 128 bits. Don't
> disturb what we aren't changing. Especially since most build-ids are
> currently 160 bits (sha1), so then they would suddenly all end in 4
> zeros.

Makes sense.

> [...]
> > +# Checks for xxhash (mandatory, md5/sha1 buildid hashes are removed)
> > +AC_CHECK_HEADERS([xxhash.h], [], AC_MSG_ERROR([missing xxhash.h]))
> 
> I think this configure check it not enough.  You also want to make
> sure you have at least xxhash 0.8.0 by checking for XXH3 types or
> functions (xxhash before 0.8.0 only supported 32/64bit hashes.

Replaced with a pkgconfig check.

> [...]
> > +$CC $CFLAGS -o main main.c
> 
> Note that gcc doesn't generate build-ids unless configured with
> --enable-linker-build-id (which every distro seem to enable, but often
> isn't enabled when using a none distro gcc). So you might want to
> explicitly add -Wl,--build-id here.

Fixed.

> [...]
> > +  /* Accept any build_id_size > 0.  Hashes will be truncated or padded
> > +     to the incoming note size, as debugedit cannot change their
> > +     size. */
> > +  if (build_id_size <= 0)
> >      {
> >        error (1, 0, "Cannot handle %zu-byte build ID", build_id_size);
> >      }
> 
> Do we really want to allow really small build_ids? We really need at
> least 4 bytes, if they should be usable in the /usr/lib/.build-id
> scheme. And at least 16 bytes (128 bits) to generate universially
> unique build-ids.

They're silly small, but on the other hand, this is what the developer
wanted with the incoming binaries.  debugedit per se can handle it and
can leave policy to elsewhere.


> > @@ -3439,22 +3443,15 @@ handle_build_id (DSO *dso, Elf_Data *build_id,
> >    /* Clear the old bits so they do not affect the new hash.  */
> >    memset ((char *) build_id->d_buf + build_id_offset, 0, build_id_size);
> 
> I would use the same length as used in the memcpy below
> MIN (build_id_size, sizeof(XXH128_canonical_t))
> so we don't disturb any bits we aren't replacing.

Done.

OK, v2:


gpg: Signature made Tue 01 Oct 2024 05:28:59 PM EDT
gpg:                using RSA key 4DD136490411C0A42B28844F258B6EFA0F209D24
gpg: Good signature from "Frank Ch. Eigler <fche@elastic.org>" [ultimate]
Author: Frank Ch. Eigler <fche@redhat.com>
Date:   Tue Sep 24 15:34:44 2024 -0400

    debugedit: switch to xxhash for buildid recomputation
    
    When debugedit recomputes build-id (due to -i), it previously used md5
    or sha1 (depending on length of incoming buildid).  This patch
    replaces both those (including the code that does all the hashing)
    with a 128-bit xxhash.  The 128-bit hash is truncated or 0-padded to
    whatever the incoming ELF note width was.
    
    xxhash is much faster (8x over sha1) than either of those
    crypto-flavoured hashes, and still produces fairly collision-free
    values.  This was confirmed informally with a bulk build-id
    recomputation of a few million binaries in the debuginfod server
    corpus, yielding zero unexpected collisions.
    
    Signed-off-by: Frank Ch. Eigler <fche@redhat.com>

diff --git a/configure.ac b/configure.ac
index 999e31f39750..c4823722ea61 100644
--- a/configure.ac
+++ b/configure.ac
@@ -75,13 +75,11 @@ AC_SYS_LARGEFILE
 PKG_PROG_PKG_CONFIG
 PKG_CHECK_MODULES([LIBELF], [libelf])
 PKG_CHECK_MODULES([LIBDW], [libdw])
+PKG_CHECK_MODULES([XXHASH], [libxxhash >= 0.8.2])
 
 # Checks for header files.
 AC_CHECK_HEADERS([fcntl.h inttypes.h limits.h malloc.h stddef.h stdint.h stdlib.h string.h unistd.h])
 
-# Checks for xxhash (mandatory, md5/sha1 buildid hashes are removed)
-AC_CHECK_HEADERS([xxhash.h], [], AC_MSG_ERROR([missing xxhash.h]))
-
 # Checks for typedefs, structures, and compiler characteristics.
 AC_CHECK_HEADER_STDBOOL
 AC_C_INLINE
diff --git a/tests/debugedit.at b/tests/debugedit.at
index 4413704acc0b..68886b1f3d79 100644
--- a/tests/debugedit.at
+++ b/tests/debugedit.at
@@ -717,3 +717,43 @@ $CC $CFLAGS -gdwarf-5 -o main main.c
 AT_CHECK([[debugedit -l sources.list main]])
 AT_CHECK([[grep -q main.c sources.list]])
 AT_CLEANUP
+
+
+# ===
+# build-id recomputation
+# ===
+AT_SETUP([debugedit build-id recompute])
+AT_KEYWORDS([debuginfo] [debugedit] [build-id])
+
+# compile a test program and extract its linker-assigned build-id
+echo "int main () { }" > main.c
+$CC $CFLAGS -Wl,--build-id -o main main.c
+AT_CHECK([[$READELF -n main | grep Build.ID: | awk '{print $3}']], [0], [stdout], [ignore])
+bid="`cat stdout`"
+AT_CHECK([[expr "$bid" : '[0-9a-f]*']], [0], [ignore])
+
+# run debugedit to recompute build-id
+AT_CHECK([[debugedit -i -s deadbeef main]], [0], [stdout])
+bid2a="`cat stdout`"
+AT_CHECK([[expr "$bid2a" : '[0-9a-f]*']], [0], [ignore])
+AT_CHECK([[test "$bid" != "$bid2a"]])
+
+# check that debugedit's stdout matches readelf -n note
+AT_CHECK([[$READELF -n main | grep Build.ID: | awk '{print $3}']], [0], [stdout], [ignore])
+bid2b="`cat stdout`"
+AT_CHECK([[expr "$bid2b" : '[0-9a-f]*']], [0], [ignore])
+AT_CHECK([[test "$bid2a" == "$bid2b"]])
+
+# run debugedit to recompute build-id, check for idempotence
+AT_CHECK([[debugedit -i -s deadbeef main]], [0], [stdout])
+bid2c="`cat stdout`"
+AT_CHECK([[expr "$bid2c" : '[0-9a-f]*']], [0], [ignore])
+AT_CHECK([[test "$bid2a" == "$bid2c"]])
+
+# check that debugedit -i with different -s seed results in different valid build-id
+AT_CHECK([[debugedit -i -s zoofoo main]], [0], [stdout])
+bid3="`cat stdout`"
+AT_CHECK([[expr "$bid3" : '[0-9a-f]*']], [0], [ignore])
+AT_CHECK([[test "$bid3" != "$bid2a"]])
+
+AT_CLEANUP
diff --git a/tools/debugedit.c b/tools/debugedit.c
index 83ee755a1523..d31e8e4d2207 100644
--- a/tools/debugedit.c
+++ b/tools/debugedit.c
@@ -3440,8 +3440,14 @@ handle_build_id (DSO *dso, Elf_Data *build_id,
       || (! dirty_elf && build_id_seed == NULL))
     goto print;
 
-  /* Clear the old bits so they do not affect the new hash.  */
-  memset ((char *) build_id->d_buf + build_id_offset, 0, build_id_size);
+  /* Clear the bits about to be recomputed, so they do not affect the
+     new hash.  Extra bits left over from wider-than-128-bit hash are
+     preserved for extra entropy.  This computation should be
+     idempotent, so repeated rehashes (with the same seed) should
+     result in the same hash. */
+  XXH128_canonical_t result_canon;
+  memset ((char *) build_id->d_buf + build_id_offset, 0,
+          MIN (build_id_size, sizeof(result_canon)));
 
   XXH3_state_t* state = XXH3_createState();
   if (!state)
@@ -3519,7 +3525,6 @@ handle_build_id (DSO *dso, Elf_Data *build_id,
   XXH128_hash_t result = XXH3_128bits_digest (state);
   XXH3_freeState (state);
   /* Use canonical-endianness output. */
-  XXH128_canonical_t result_canon;
   XXH128_canonicalFromHash (&result_canon, result);
   memcpy((unsigned char *)build_id->d_buf + build_id_offset, &result_canon,
          MIN (build_id_size, sizeof(result_canon)));