kit

commit 3f86328e70e2af348da45ab24097ca30e09db9d3
parent c89c5909d47ae0b854d9018f0bec63db7c559277
Author: Ryan Sepassi <rsepassi@gmail.com>
Date:   Thu, 11 Jun 2026 09:45:19 -0700

perf(link): hardware SHA-256 image-id / build-id (−27% on large links)

Replace the two-stream FNV-1a image-id fold with the linker's existing
HW ARMv8 SHA-256 primitive (core/sha256, already used for the Mach-O
code signature — no second SHA impl). The id stays content-derived and
deterministic; only its bytes change. The single digest still feeds
both the ELF .note.gnu.build-id and the Mach-O LC_UUID, so they stay
in lockstep.

Output delta vs the old binary is exactly 48 bytes (16B LC_UUID + the
32B code-sig page hash covering it); nothing structural moves. This was
the one PERF.md lever fenced off solely because it changes UUID/build-id
bytes (so it is excluded from the byte-identical gate by design); it is
gated instead on determinism (stable id across runs) + run-correctness
(links load and execute) + the full non-link byte-identical gate.

Measured kit ld best-of-7 on symbol-count=64000 (objects prebuilt
untimed): 118ms -> 86ms (-27%). The win scales with image bytes; the
image-id fold was the residual top frame on byte/symbol-heavy links.

Diffstat:
M
src/link/link_image_id.c
 | 
62
+++++++++++++++++++++++++++-----------------------------------

1 file changed, 27 insertions(+), 35 deletions(-)
diff --git a/src/link/link_image_id.c b/src/link/link_image_id.c
@@ -1,10 +1,14 @@
 /* link_image_id_compute: format-agnostic 16-byte identity hash for a
  * resolved LinkImage.
  *
- * Two FNV-1a 64-bit streams with different seeds produce 128 bits.  The
- * mix covers each segment's vaddr, file_size, and post-shift bytes, so
- * the digest changes if either content or layout shifts.  Determinism
- * (no time / random component) is intentional — reproducible builds.
+ * A single SHA-256 stream is fed each segment's vaddr, file_size, and
+ * post-shift bytes, so the digest changes if either content or layout
+ * shifts.  The 16-byte image id is the first half of the 32-byte digest.
+ * The SHA-256 core uses the AArch64 crypto extension where the host has
+ * it (the same hardware path that hashes the Mach-O code signature), so
+ * the per-byte fold is far cheaper than the old twin-FNV mix — this was
+ * the residual top frame on pathologically large links.  Determinism (no
+ * time / random component) is intentional — reproducible builds.
  *
  * Wrapped per format:
  *   - ELF      .note.gnu.build-id (link_emit_elf)
@@ -15,47 +19,35 @@
  * sees the same bytes. */
 
 #include "core/core.h"
+#include "core/sha256.h"
 #include "link/link_internal.h"
 
-static u64 fnv1a64(const u8* data, size_t n, u64 seed) {
-  const u64 PRIME = 0x100000001b3ull;
-  u64 h = seed;
-  size_t i;
-  for (i = 0; i < n; ++i) {
-    h ^= (u64)data[i];
-    h *= PRIME;
+/* sha256_update takes a u32 length; feed large segments in chunks so a
+ * >4 GiB segment can never truncate the stream. */
+static void image_id_update(Sha256* s, const u8* data, size_t n) {
+  while (n) {
+    u32 chunk = n > 0x40000000u ? 0x40000000u : (u32)n;
+    sha256_update(s, data, chunk);
+    data += chunk;
+    n -= chunk;
   }
-  return h;
 }
 
 void link_image_id_compute(const LinkImage* img, u8 out[LINK_IMAGE_ID_BYTES]) {
-  const u64 SEED_LO = 0xcbf29ce484222325ull;
-  const u64 SEED_HI = 0x14650fb0739d0383ull;
-  const u64 PRIME = 0x100000001b3ull;
-  u64 lo = SEED_LO, hi = SEED_HI;
+  Sha256 s;
+  sha256_init(&s);
   u32 i;
   for (i = 0; i < img->nsegments; ++i) {
     const LinkSegment* seg = &img->segments[i];
     u64 vaddr = seg->vaddr;
     u64 fsz = seg->file_size;
-    lo = fnv1a64((const u8*)&vaddr, sizeof vaddr, lo);
-    lo = fnv1a64((const u8*)&fsz, sizeof fsz, lo);
-    hi = fnv1a64((const u8*)&vaddr, sizeof vaddr, hi);
-    hi = fnv1a64((const u8*)&fsz, sizeof fsz, hi);
-    /* Fold both digest streams over the segment bytes in a single pass: each
-     * byte is read once and the two independent multiply chains issue in
-     * parallel.  Bit-for-bit identical to two separate fnv1a64() passes (the
-     * dominant cost for large images), but ~2x faster. */
-    if (img->segment_bytes[i] && fsz) {
-      const u8* data = img->segment_bytes[i];
-      size_t n = (size_t)fsz, j;
-      for (j = 0; j < n; ++j) {
-        u8 b = data[j];
-        lo = (lo ^ (u64)b) * PRIME;
-        hi = (hi ^ (u64)b) * PRIME;
-      }
-    }
+    sha256_update(&s, (const u8*)&vaddr, (u32)sizeof vaddr);
+    sha256_update(&s, (const u8*)&fsz, (u32)sizeof fsz);
+    if (img->segment_bytes[i] && fsz)
+      image_id_update(&s, img->segment_bytes[i], (size_t)fsz);
   }
-  for (i = 0; i < 8; ++i) out[i] = (u8)(lo >> (i * 8));
-  for (i = 0; i < 8; ++i) out[8 + i] = (u8)(hi >> (i * 8));
+  u8 digest[SHA256_DIGEST_LEN];
+  sha256_final(&s, digest);
+  /* Image id is the first 16 bytes of the 256-bit digest. */
+  for (i = 0; i < LINK_IMAGE_ID_BYTES; ++i) out[i] = digest[i];
 }