[ELF] Support for --build-id=uuid

[evgeny777]

Summary

This has to be done differently on Windows and Unix systems.
I ran test suite on Windows, Ubuntu and FreeBSD.

[ruiu]

ELF/OutputSections.cpp

1687 ↗

(On Diff #67505)

I'd add code to generate a RNG to LLVM rather than to LLD because it seems generic and should be useful in other places.

[ruiu]

One more question: is there any project that actually uses this option?

[evgeny777]

Our project does, but we need only Windows version. We can keep this patch proprietary of course, if it's not desired for some reason

[evgeny777]

ELF/OutputSections.cpp

1687 ↗

(On Diff #67505)

You mean creating random GUID, don't you?

[ruiu]

I asked the question because we do not usually create features just because other linkers have them, so I wanted to confirm that you actually needed it. So there's no problem to add this feature to LLD.

ELF/OutputSections.cpp

1687 ↗

(On Diff #67505)

GUID is actually jus random 16 bytes, so maybe adding a function to create a GUID is too narrowly scoped. How about defining a function that returns truely random bytes of any length? Like

std::vector<uint8_t> getRandomBytes(size_t Length);

[evgeny777]

ELF/OutputSections.cpp

1687 ↗

(On Diff #67505)

There is a special routine on Windows which should be used to create GUID (UuidCreate). I'm afraid getRandomBytes is too generic for this particular case.

[evgeny777]

Just curious if using std::mt19937_64 would be easier.

[ruiu]

I have a concern about using current time as a random source. Even with a nano second resolution timer (and I think timers are in reality not that accurate), there's a small chance for two machines to create two different executables at the same time. If that happens, the two files get the same build-id. That's a small probability but much larger than a collision in 2^128 space.

[evgeny777]

How about using timer value + Bufs and calculate md5 of the combined value (a sort of hmac-md5)?

[ruiu]

Maybe you can, but it's still less entropy than real random values, so why don't you just use a true random value such as /dev/random?

[evgeny777]

Patch to support library landed, so I'm updating diff.

[ruiu]

LGTM

lld/trunk/ELF/Config.h

 enum ELFKind {
   ELFNoneKind,
   ELF32LEKind,
   ELF32BEKind,
   ELF64LEKind,
   ELF64BEKind
 };
 
-enum class BuildIdKind { None, Fnv1, Md5, Sha1, Hexstring };
+enum class BuildIdKind { None, Fnv1, Md5, Sha1, Hexstring, Uuid };
 
 enum class UnresolvedPolicy { NoUndef, Error, Warn, Ignore };
 
 struct SymbolVersion {
   llvm::StringRef Name;
   bool IsExternCpp;
 };
 

lld/trunk/ELF/Driver.cpp

void LinkerDriver::readConfigs(opt::InputArgList &Args) {
   if (Args.hasArg(OPT_build_id))
     Config->BuildId = BuildIdKind::Fnv1;
   if (auto *Arg = Args.getLastArg(OPT_build_id_eq)) {
     StringRef S = Arg->getValue();
     if (S == "md5") {
       Config->BuildId = BuildIdKind::Md5;
     } else if (S == "sha1") {
       Config->BuildId = BuildIdKind::Sha1;
+    } else if (S == "uuid") {
+      Config->BuildId = BuildIdKind::Uuid;
     } else if (S == "none") {
       Config->BuildId = BuildIdKind::None;
     } else if (S.startswith("0x")) {
       Config->BuildId = BuildIdKind::Hexstring;
       Config->BuildIdVector = parseHex(S.substr(2));
     } else {
       error("unknown --build-id style: " + S);
     }

lld/trunk/ELF/OutputSections.h

 };
 
 template <class ELFT> class BuildIdSha1 final : public BuildIdSection<ELFT> {
 public:
   BuildIdSha1() : BuildIdSection<ELFT>(20) {}
   void writeBuildId(ArrayRef<ArrayRef<uint8_t>> Bufs) override;
 };
 
+template <class ELFT> class BuildIdUuid final : public BuildIdSection<ELFT> {
+public:
+  BuildIdUuid() : BuildIdSection<ELFT>(16) {}
+  void writeBuildId(ArrayRef<ArrayRef<uint8_t>> Bufs) override;
+};
+
 template <class ELFT>
 class BuildIdHexstring final : public BuildIdSection<ELFT> {
 public:
   BuildIdHexstring();
   void writeBuildId(ArrayRef<ArrayRef<uint8_t>> Bufs) override;
 };
 
 // All output sections that are hadnled by the linker specially are

lld/trunk/ELF/OutputSections.cpp

 #include "Strings.h"
 #include "SymbolTable.h"
 #include "Target.h"
 #include "lld/Core/Parallel.h"
 #include "llvm/Support/Dwarf.h"
 #include "llvm/Support/MD5.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/SHA1.h"
-#include <map>
+#include "llvm/Support/RandomNumberGenerator.h"
 
 using namespace llvm;
 using namespace llvm::dwarf;
 using namespace llvm::object;
 using namespace llvm::support::endian;
 using namespace llvm::ELF;
 
 using namespace lld;

 void BuildIdSha1<ELFT>::writeBuildId(ArrayRef<ArrayRef<uint8_t>> Bufs) {
   SHA1 Hash;
   for (ArrayRef<uint8_t> Buf : Bufs)
     Hash.update(Buf);
   memcpy(this->HashBuf, Hash.final().data(), 20);
 }
 
 template <class ELFT>
+void BuildIdUuid<ELFT>::writeBuildId(ArrayRef<ArrayRef<uint8_t>> Bufs) {
+  if (getRandomBytes(this->HashBuf, 16))
+    error("entropy source failure");
+}
+
+template <class ELFT>
 BuildIdHexstring<ELFT>::BuildIdHexstring()
     : BuildIdSection<ELFT>(Config->BuildIdVector.size()) {}
 
 template <class ELFT>
 void BuildIdHexstring<ELFT>::writeBuildId(ArrayRef<ArrayRef<uint8_t>> Bufs) {
   memcpy(this->HashBuf, Config->BuildIdVector.data(),
          Config->BuildIdVector.size());
 }

 template class BuildIdMd5<ELF64LE>;
 template class BuildIdMd5<ELF64BE>;
 
 template class BuildIdSha1<ELF32LE>;
 template class BuildIdSha1<ELF32BE>;
 template class BuildIdSha1<ELF64LE>;
 template class BuildIdSha1<ELF64BE>;
 
+template class BuildIdUuid<ELF32LE>;
+template class BuildIdUuid<ELF32BE>;
+template class BuildIdUuid<ELF64LE>;
+template class BuildIdUuid<ELF64BE>;
+
 template class BuildIdHexstring<ELF32LE>;
 template class BuildIdHexstring<ELF32BE>;
 template class BuildIdHexstring<ELF64LE>;
 template class BuildIdHexstring<ELF64BE>;
 
 template class OutputSectionFactory<ELF32LE>;
 template class OutputSectionFactory<ELF32BE>;
 template class OutputSectionFactory<ELF64LE>;
 template class OutputSectionFactory<ELF64BE>;
 }
 }

lld/trunk/ELF/Writer.cpp

if (needsInterpSection<ELFT>())
     Interp.reset(new InterpSection<ELFT>);
 
   if (Config->BuildId == BuildIdKind::Fnv1)
     BuildId.reset(new BuildIdFnv1<ELFT>);
   else if (Config->BuildId == BuildIdKind::Md5)
     BuildId.reset(new BuildIdMd5<ELFT>);
   else if (Config->BuildId == BuildIdKind::Sha1)
     BuildId.reset(new BuildIdSha1<ELFT>);
+  else if (Config->BuildId == BuildIdKind::Uuid)
+    BuildId.reset(new BuildIdUuid<ELFT>);
   else if (Config->BuildId == BuildIdKind::Hexstring)
     BuildId.reset(new BuildIdHexstring<ELFT>);
 
   if (!Symtab<ELFT>::X->getSharedFiles().empty() || Config->Pic) {
     DynStrTab.reset(new StringTableSection<ELFT>(".dynstr", true));
     DynSymTab.reset(new SymbolTableSection<ELFT>(*DynStrTab));
   }
 

lld/trunk/test/ELF/build-id.s

 # REQUIRES: x86
 
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
 # RUN: ld.lld --build-id %t -o %t2
 # RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=DEFAULT %s
 # RUN: ld.lld --build-id=md5 %t -o %t2
 # RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=MD5 %s
 # RUN: ld.lld --build-id=sha1 %t -o %t2
 # RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=SHA1 %s
+# RUN: ld.lld --build-id=uuid %t -o %t2
+# RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=UUID %s
 # RUN: ld.lld --build-id=0x12345678 %t -o %t2
 # RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=HEX %s
 # RUN: ld.lld %t -o %t2
 # RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=NONE %s
 # RUN: ld.lld --build-id=md5 --build-id=none %t -o %t2
 # RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=NONE %s
 
 .globl _start
 _start:
   nop
 
 .section .note.test, "a", @note
    .quad 42
 
 # DEFAULT:      Contents of section .note.gnu.build-id:
 # DEFAULT-NEXT: 04000000 08000000 03000000 474e5500  ............GNU.
 # DEFAULT:      Contents of section .note.test:
 
 # MD5:      Contents of section .note.gnu.build-id:
 # MD5-NEXT: 04000000 10000000 03000000 474e5500  ............GNU.
 
 # SHA1:      Contents of section .note.gnu.build-id:
 # SHA1-NEXT: 04000000 14000000 03000000 474e5500  ............GNU.
 
+# 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: