[ELF] Implement --build-id={md5,sha1} with truncated BLAKE3

[MaskRay]

Summary

--build-id was introduced as "approximation of true uniqueness across all
binaries that might be used by overlapping sets of people". It does not require
the above mentioned resistance. In practice, people just use --build-id=md5
for 16-byte build ID and --build-id=sha1 for 20-byte build ID.

BLAKE3 has 256-bit key length, which provides 128-bit security against
(second-)preimage, collision, and differentiability attacks. Its portable
implementation is fast. It additionally provides Arm Neon/AVX2/AVX-512. Just
implement --build-id={md5,sha1} with truncated BLAKE3.

Linking clang 14 RelWithDebInfo with --threads=8 on a Skylake CPU:

• 1.13x as fast with --build-id=md5
• 1.15x as fast with --build-id=sha1

--threads=4 on Apple m1:

• 1.25x as fast with --build-id=md5
• 1.17x as fast with --build-id=sha1

[MaskRay]

Remove unused headers. Add a comment

[tschuett]

lld/ELF/Writer.cpp

2927

Do you have link?

[MaskRay]

lld/ELF/Writer.cpp

2927

It's a deleted page https://fedoraproject.org/w/index.php?title=RolandMcGrath/BuildID&oldid=16098
I do not want to put the URI in the comment.

[joerg]

I would find it quite surprising to find two binaries produced with the same command line now resulting in different build-ids, if that is the only difference. Especially when the cryptographic hash function is explicitly set.

For reference, I did some tests a while ago in the context of Mercurial's SHA1 replacement and got the following numbers on a Threadripper using a large file:

BLAKE2s256	asm	13.8s
SHA2-256	asm	4.5s
SHA2-256	C	28.0s
SHA3-256	asm	16.7s
SHA3-256	C	19.8s
K12	asm	5.9s
K12	C	9.2s
BLAKE3	asm	4.1s
BLAKE3	C	10.1s
BLAKE3*	asm	5.5s
BLAKE3*	C	13.8s

I've included variants of BLAKE3 with the same number of rounds as BLAKE2 to show that much of the gain is actually from the weaker security. There are arguments speaking for K12, especially that we are likely to see some form of hardware support in the future given that it is using the sponge function of SHA3.

[MaskRay]

In D121531#3377547, @joerg wrote:

I would find it quite surprising to find two binaries produced with the same command line now resulting in different build-ids, if that is the only difference. Especially when the cryptographic hash function is explicitly set.

lld built at different commits don't guarantee a binary gets hashed in the same way.
When a tree hash style parallelism was added, the hash obviously changed.
The stability/determinism is only related to lld built at the same commit.

This is like we don't guarantee output may be the same with lld different at different commits.
The hash changes very infrequently, though.
If lld X and lld X+1 use different layouts or generate some synthetic section differently, I don't see how "same content => same build ID" is very useful, since content may be very unlikely the same using lld of different versions.

[ikudrin]

I like the idea and don't see real drawbacks, so LGTM.

lld/ELF/Writer.cpp

 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 #include "lld/Common/Arrays.h"
 #include "lld/Common/CommonLinkerContext.h"
 #include "lld/Common/Filesystem.h"
 #include "lld/Common/Strings.h"
 #include "llvm/ADT/StringMap.h"
-#include "llvm/Support/MD5.h"
+#include "llvm/Support/BLAKE3.h"
 #include "llvm/Support/Parallel.h"
 #include "llvm/Support/RandomNumberGenerator.h"
-#include "llvm/Support/SHA1.h"
 #include "llvm/Support/TimeProfiler.h"
 #include "llvm/Support/xxhash.h"
 #include <climits>
 
 #define DEBUG_TYPE "lld"
 
 using namespace llvm;
 using namespace llvm::ELF;
template <class ELFT> void Writer<ELFT>::writeBuildId() {
   }
 
   // Compute a hash of all sections of the output file.
   size_t hashSize = mainPart->buildId->hashSize;
   std::unique_ptr<uint8_t[]> buildId(new uint8_t[hashSize]);
   MutableArrayRef<uint8_t> output(buildId.get(), hashSize);
   llvm::ArrayRef<uint8_t> input{Out::bufferStart, size_t(fileSize)};
 
+  // Fedora introduced build ID as "approximation of true uniqueness across all
+  // binaries that might be used by overlapping sets of people". It does not
+  // need some security goals that some hash algorithms strive to provide, e.g.
+  // (second-)preimage and collision resistance. In practice people use 'md5'
+  // and 'sha1' just for different lengths. Implement them with the more
+  // efficient BLAKE3.
   switch (config->buildId) {
   case BuildIdKind::Fast:
     computeHash(output, input, [](uint8_t *dest, ArrayRef<uint8_t> arr) {
       write64le(dest, xxHash64(arr));
     });
     break;
   case BuildIdKind::Md5:
     computeHash(output, input, [&](uint8_t *dest, ArrayRef<uint8_t> arr) {
-      memcpy(dest, MD5::hash(arr).data(), hashSize);
+      memcpy(dest, BLAKE3::hash<16>(arr).data(), hashSize);
     });
     break;
   case BuildIdKind::Sha1:
     computeHash(output, input, [&](uint8_t *dest, ArrayRef<uint8_t> arr) {
-      memcpy(dest, SHA1::hash(arr).data(), hashSize);
+      memcpy(dest, BLAKE3::hash<20>(arr).data(), hashSize);
     });
     break;
   case BuildIdKind::Uuid:
     if (auto ec = llvm::getRandomBytes(buildId.get(), hashSize))
       error("entropy source failure: " + ec.message());
     break;
   default:
     llvm_unreachable("unknown BuildIdKind");

lld/test/ELF/build-id.s

 
 # DEFAULT:      Contents of section .note.test:
 # DEFAULT:      Contents of section .note.gnu.build-id:
 # DEFAULT-NEXT: 04000000 08000000 03000000 474e5500  ............GNU.
 # DEFAULT-NEXT: 7e8ddeff 3ed41fa3
 
 # MD5:      Contents of section .note.gnu.build-id:
 # MD5-NEXT: 04000000 10000000 03000000 474e5500  ............GNU.
-# MD5-NEXT: 7b00fd9e 054ceb4b 06f64d0e 482cb476
+# MD5-NEXT: dbf0bc13 b3ff11e9 fde6e17c 0304983c
 
 # SHA1:      Contents of section .note.gnu.build-id:
 # SHA1-NEXT: 04000000 14000000 03000000 474e5500  ............GNU.
-# SHA1-NEXT: 221a99da dd1d2bf3 05e48a91 dde8a0cb
+# SHA1-NEXT: 1215775f d3b60050 70afd970 e8a10972
 
 # UUID:      Contents of section .note.gnu.build-id:
 # UUID-NEXT: 04000000 10000000 03000000 474e5500  ............GNU.
 
 # HEX:      Contents of section .note.gnu.build-id:
 # HEX-NEXT: 04000000 04000000 03000000 474e5500  ............GNU.
 # HEX-NEXT: 12345678
 
 # NONE-NOT: Contents of section .note.gnu.build-id:
 
 # RUN: ld.lld --build-id=sha1 -z separate-loadable-segments %t -o %t2
 # RUN: llvm-readelf -x .note.gnu.build-id %t2 | FileCheck --check-prefix=SEPARATE %s
 
 # SEPARATE:      Hex dump of section '.note.gnu.build-id':
 # SEPARATE-NEXT: 0x00200198 04000000 14000000 03000000 474e5500
-# SEPARATE-NEXT: 0x002001a8 96820adf d90d5470 0a0c32ff a88c4017
+# SEPARATE-NEXT: 0x002001a8 5cd067a4 2631c0fd 42029037 4b8e0938
 
 # RUN: ld.lld --build-id=sha1 --no-rosegment %t -o %t2
 # RUN: llvm-readelf -x .note.gnu.build-id %t2 | FileCheck --check-prefix=NORO %s
 
 # NORO:      Hex dump of section '.note.gnu.build-id':
 # NORO-NEXT: 0x00200160 04000000 14000000 03000000 474e5500
-# NORO-NEXT: 0x00200170 cf6d7b3a 0b3297c3 5b47c079 ce048349
+# NORO-NEXT: 0x00200170 a328cc99 45bfc3fc a9fc8615 37102f9d

lld/test/ELF/partition-notes.s

 // CHECK-NEXT:   NoteSection {
 // CHECK-NEXT:     Name: .note.gnu.build-id
 // CHECK-NEXT:     Offset:
 // CHECK-NEXT:     Size:
 // CHECK-NEXT:     Note {
 // CHECK-NEXT:       Owner: GNU
 // CHECK-NEXT:       Data size:
 // CHECK-NEXT:       Type: NT_GNU_BUILD_ID (unique build ID bitstring)
-// CHECK-NEXT:       Build ID: bb5542bd74252653e286044980d602874d237ae0
+// CHECK-NEXT:       Build ID: ab81108a3d85b729980356331fddc2bfc4c10177{{$}}
 // CHECK-NEXT:     }
 // CHECK-NEXT:   }
 // CHECK-NEXT: ]
 
 .section .llvm_sympart,"",@llvm_sympart
 .asciz "part1"
 .quad p1