[patch] switch to xxhash for buildid recomputation
Mark Wielaard
mark@klomp.org
Sun Sep 29 21:39:22 GMT 2024
Hi Frank,
On Fri, Sep 27, 2024 at 03:14:41PM -0400, Frank Ch. Eigler wrote:
>
> commit 98e40a7a9a13625646f2e4494aaee402016d3716 (HEAD -> main)
> 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.
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.
> 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.
Thanks for testing. It looks like xxhash also contains tests itself to
make sure it is collission free (at least for 128bits):
https://github.com/Cyan4973/xxHash/wiki/Collision-ratio-comparison
> Signed-off-by: Frank Ch. Eigler <fche@redhat.com>
>
> diff --git a/Makefile.am b/Makefile.am
> index 4a5092dfcbec..c590edf94f4f 100644
> --- a/Makefile.am
> +++ b/Makefile.am
> @@ -41,9 +41,7 @@ find-debuginfo: $(top_srcdir)/scripts/find-debuginfo.in Makefile
> chmod +x "$@"
>
> debugedit_SOURCES = tools/debugedit.c \
> - tools/hashtab.c \
> - tools/md5.c \
> - tools/sha1.c
> + tools/hashtab.c
> debugedit_CFLAGS = @LIBELF_CFLAGS@ @LIBDW_CFLAGS@ $(AM_CFLAGS)
> debugedit_LDADD = @LIBELF_LIBS@ @LIBDW_LIBS@
>
> @@ -85,8 +83,6 @@ find-debuginfo.1: $(top_srcdir)/scripts/find-debuginfo.in configure.ac find-debu
> esac
>
> noinst_HEADERS= tools/ansidecl.h \
> - tools/hashtab.h \
> - tools/md5.h \
> - tools/sha1.h
> + tools/hashtab.h
So you are removing more than you add. Nice.
> EXTRA_DIST = README COPYING COPYING3 COPYING.LIB scripts/find-debuginfo.in
> diff --git a/configure.ac b/configure.ac
> index 79803dc8d197..999e31f39750 100644
> --- a/configure.ac
> +++ b/configure.ac
> @@ -79,6 +79,9 @@ PKG_CHECK_MODULES([LIBDW], [libdw])
> # 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]))
> +
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.
> # 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..de748c7f49a9 100644
> --- a/tests/debugedit.at
> +++ b/tests/debugedit.at
> @@ -717,3 +717,37 @@ $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 -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.
> +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"]])
> +
> +# 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
Nice check.
> diff --git a/tools/debugedit.c b/tools/debugedit.c
> index 6bdb3f7f1d63..83ee755a1523 100644
> --- a/tools/debugedit.c
> +++ b/tools/debugedit.c
> @@ -30,6 +30,7 @@
> #include <limits.h>
> #include <string.h>
> #include <stdlib.h>
> +#include <stdio.h>
> #include <stdint.h>
> #include <inttypes.h>
> #include <unistd.h>
> @@ -44,6 +45,9 @@
> #ifndef MAX
> #define MAX(m, n) ((m) < (n) ? (n) : (m))
> #endif
> +#ifndef MIN
> +#define MIN(m, n) ((m) > (n) ? (n) : (m))
> +#endif
>
>
> /* Unfortunately strtab manipulation functions were only officially added
> @@ -77,8 +81,8 @@ typedef struct Ebl_Strtab Strtab;
>
> #include "tools/hashtab.h"
>
> -#include "tools/md5.h"
> -#include "tools/sha1.h"
> +#define XXH_INLINE_ALL
> +#include "xxhash.h"
>
> #define DW_TAG_partial_unit 0x3c
> #define DW_FORM_sec_offset 0x17
> @@ -3423,10 +3427,10 @@ static void
> handle_build_id (DSO *dso, Elf_Data *build_id,
> size_t build_id_offset, size_t build_id_size)
> {
> - /* For now we only handle 16 byte (128 bits) with md5 or 20 bytes
> - (160 bits) with sha1. */
> -
> - if (build_id_size != 16 && build_id_size != 20)
> + /* 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.
> @@ -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.
> - struct md5_ctx md5_ctx;
> - struct sha1_ctx sha1_ctx;
> -
> - if (build_id_size == 16)
> - md5_init_ctx (&md5_ctx);
> - else
> - sha1_init_ctx (&sha1_ctx);
> + XXH3_state_t* state = XXH3_createState();
> + if (!state)
> + error (1, errno, "Failed to create xxhash state");
> + XXH3_128bits_reset (state);
>
> /* If a seed string was given use it to prime the hash. */
> if (build_id_seed != NULL)
> - {
> - if (build_id_size == 16)
> - md5_process_bytes (build_id_seed, strlen (build_id_seed), &md5_ctx);
> - else
> - sha1_process_bytes (build_id_seed, strlen (build_id_seed), &sha1_ctx);
> - }
> + /* Another choice is XXH3_generateSecret. */
> + XXH3_128bits_update (state, build_id_seed, strlen (build_id_seed));
>
> /* Slurp the relevant header bits and section contents and feed them
> into the hash function. The only bits we ignore are the offset
> @@ -3493,10 +3490,7 @@ handle_build_id (DSO *dso, Elf_Data *build_id,
> if (elf64_xlatetom (&x, &x, dso->ehdr.e_ident[EI_DATA]) == NULL)
> goto bad;
>
> - if (build_id_size == 16)
> - md5_process_bytes (x.d_buf, x.d_size, &md5_ctx);
> - else
> - sha1_process_bytes (x.d_buf, x.d_size, &sha1_ctx);
> + XXH3_128bits_update (state, x.d_buf, x.d_size);
> }
>
> x.d_type = ELF_T_SHDR;
> @@ -3509,10 +3503,7 @@ handle_build_id (DSO *dso, Elf_Data *build_id,
> if (elf64_xlatetom (&x, &x, dso->ehdr.e_ident[EI_DATA]) == NULL)
> goto bad;
>
> - if (build_id_size == 16)
> - md5_process_bytes (x.d_buf, x.d_size, &md5_ctx);
> - else
> - sha1_process_bytes (x.d_buf, x.d_size, &sha1_ctx);
> + XXH3_128bits_update (state, x.d_buf, x.d_size);
>
> if (dso->shdr[i].sh_type != SHT_NOBITS)
> {
> @@ -3520,26 +3511,18 @@ handle_build_id (DSO *dso, Elf_Data *build_id,
> if (d == NULL)
> goto bad;
>
> - if (build_id_size == 16)
> - md5_process_bytes (d->d_buf, d->d_size, &md5_ctx);
> - else
> - sha1_process_bytes (d->d_buf, d->d_size, &sha1_ctx);
> + XXH3_128bits_update (state, d->d_buf, d->d_size);
> }
> }
> }
>
> - /* Allocate the memory first to make sure alignment is correct. */
> - void *digest = malloc (build_id_size);
> - if (digest == NULL)
> - goto bad;
> -
> - if (build_id_size == 16)
> - md5_finish_ctx (&md5_ctx, digest);
> - else
> - sha1_finish_ctx (&sha1_ctx, digest);
> -
> - memcpy((unsigned char *)build_id->d_buf + build_id_offset, digest, build_id_size);
> - free(digest);
> + 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)));
>
> elf_flagdata (build_id, ELF_C_SET, ELF_F_DIRTY);
Code looks correct. It does replace tabs by spaces.
> diff --git a/tools/md5.c b/tools/md5.c
> deleted file mode 100644
> index a8c8de22c210..000000000000
> --- a/tools/md5.c
> +++ /dev/null
And lots of code removal.
Thanks,
Mark
More information about the Debugedit
mailing list