ELF: Implement --build-id.

[ruiu]

Summary

This patch implements --build-id. After the linker creates an output file
in the memory buffer, it computes the FNV1 hash of the resulting file
and set the hash to the .note section as a build-id.

GNU ld and gold have the same feature, but their default choice of the
hash function is different. Their default is SHA1.

We made a deliberate choice to not use a secure hash function for the
sake of performance. Computing a secure hash is slow -- for example,
MD5 throughput is usually 400 MB/s or so. SHA1 is slower than that.

As a result, if you pass --build-id to gold, then the linker becomes about
10% slower than that without the option. We observed a similar degradation
in an experimental implementation of build-id for LLD. On the other hand,
we observed only 1-2% performance degradation with the FNV hash.

Since build-id is not for digital certificate or anything, we think that
a very small probability of collision is acceptable.

We considered using other signals such as using input file timestamps as
inputs to a secure hash function. But such signals would have an issue
with build reproducibility (if you build a binary from the same source
tree using the same toolchain, the build id should become the same.)

GNU linkers accepts --build-id=<style> option where style is one of
"MD5", "SHA1", or an arbitrary hex string. That option is out of scope
of this patch.

[emaste]

ELF/Options.td

15

gold accepted both -build-id and --build-id

[ruiu]

• accept both --build-id and -build-id.

[hjl.tools]

FYI, here is the spec for .note.gnu.build-id section:

https://github.com/hjl-tools/linux-abi/wiki/Linux-Extensions-to-gABI

[emaste]

One issue, if possible the build-id note should be in a loadable note segment and in the first page of the binary. The intent is that it will be copied into a core file so that the original binary can be identified.

from readelf -S, gold:

[ 3] .note.gnu.build-i NOTE             0000000000400248  00000248
     0000000000000024  0000000000000000   A       0     0     4

patched lld:

[34] .note.gnu.build-i NOTE             0000000000000000  00003d41
     0000000000000018  0000000000000000           0     0     0

[ruiu]

• .note.gnu.build-id should have SHF_ALLOC attribute. Otherwise I think the core file wouldn't contain the build ID.

• Use NT_GNU_BUILD_ID constant.

[ruiu]

I think I've just addressed that!

[ruiu]

Does it have to be in the first page of a binary?

[emaste]

ELF/OutputSections.cpp

1543

Where is this defined (maybe I haven't updated something)?

../tools/lld/ELF/OutputSections.cpp:1562:23: error: use of undeclared identifier 'NT_GNU_BUILD_ID'
  write32<E>(Buf + 8, NT_GNU_BUILD_ID); // Type (NT_GNU_BUILD_ID = 3)

[ruiu]

Please synchronize your LLVM repository. (Or replace NT_GNU_BUILD_ID with
3.)

[emaste]

Does it have to be in the first page of a binary?

From https://fedoraproject.org/wiki/Releases/FeatureBuildId:
The build ID note is normally near the beginning of the image and will be in the first page unless there are an unreasonable number of phdrs or other notes. (The kernel should not deal with anything more complex than a simple rule like the first page, so the odd binary with its notes in the wrong places will just lose.)

It is preferred, but not required. And for matching debug files at least it won't matter.

In my hello world I see:

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  [ 0]                   NULL             0000000000000000  00000000
       0000000000000000  0000000000000000           0     0     0
  [ 1] .interp           PROGBITS         0000000000010270  00000270
       0000000000000015  0000000000000000   A       0     0     1
  [ 2] .note.tag         NOTE             0000000000010288  00000288
       0000000000000030  0000000000000000   A       0     0     4
  [ 3] .rodata           PROGBITS         00000000000102b8  000002b8
       0000000000000001  0000000000000000 AMS       0     0     1
  [ 4] .eh_frame         X86_64_UNWIND    00000000000102c0  000002c0
       0000000000000080  0000000000000000   A       0     0     8
  [ 5] .rodata           PROGBITS         0000000000010340  00000340
       000000000000000f  0000000000000000   A       0     0     1
  [ 6] .note.gnu.build-i NOTE             000000000001034f  0000034f
       0000000000000018  0000000000000000   A       0     0     0

and it seems like we should move it immediately after .note.tag.

[emaste]

This looks fine to me. We can revisit hash types, sections included in the hash, and the note location in the object file in subsequent patches.

[ruiu]

Committed as r263292.

ELF/Config.h

struct Configuration {
   llvm::StringRef Sysroot;
   std::string RPath;
   std::vector<llvm::StringRef> SearchPaths;
   std::vector<llvm::StringRef> Undefined;
   bool AllowMultipleDefinition;
   bool AsNeeded = false;
   bool Bsymbolic;
   bool BsymbolicFunctions;
+  bool BuildId;
   bool Demangle = true;
   bool DiscardAll;
   bool DiscardLocals;
   bool DiscardNone;
   bool EhFrameHdr;
   bool EnableNewDtags;
   bool ExportDynamic;
   bool GcSections;

ELF/Driver.cpp

if (auto *Arg = Args.getLastArg(OPT_m)) {
     StringRef S = Arg->getValue();
     std::tie(Config->EKind, Config->EMachine) = parseEmulation(S);
     Config->Emulation = S;
   }
 
   Config->AllowMultipleDefinition = Args.hasArg(OPT_allow_multiple_definition);
   Config->Bsymbolic = Args.hasArg(OPT_Bsymbolic);
   Config->BsymbolicFunctions = Args.hasArg(OPT_Bsymbolic_functions);
+  Config->BuildId = Args.hasArg(OPT_build_id);
   Config->Demangle = !Args.hasArg(OPT_no_demangle);
   Config->DiscardAll = Args.hasArg(OPT_discard_all);
   Config->DiscardLocals = Args.hasArg(OPT_discard_locals);
   Config->DiscardNone = Args.hasArg(OPT_discard_none);
   Config->EhFrameHdr = Args.hasArg(OPT_eh_frame_hdr);
   Config->EnableNewDtags = !Args.hasArg(OPT_disable_new_dtags);
   Config->ExportDynamic = Args.hasArg(OPT_export_dynamic);
   Config->GcSections = Args.hasArg(OPT_gc_sections);

ELF/Options.td

 include "llvm/Option/OptParser.td"
 
 def Bsymbolic: Flag<["-"], "Bsymbolic">,
   HelpText<"Bind defined symbols locally">;
 
 def Bsymbolic_functions: Flag<["-"], "Bsymbolic-functions">,
   HelpText<"Bind defined function symbols locally">;
 
 def Bdynamic: Flag<["-"], "Bdynamic">,
   HelpText<"Link against shared libraries">;
 
 def Bstatic: Flag<["-"], "Bstatic">,
   HelpText<"Do not link against shared libraries">;
 
+def build_id : Flag<["--", "-"], "build-id">,
+  HelpText<"Generate build ID note">;
+
 def L : JoinedOrSeparate<["-"], "L">, MetaVarName<"<dir>">,
   HelpText<"Directory to search for libraries">;
 
 def O : Joined<["-"], "O">, HelpText<"Optimize">;
 
 def allow_multiple_definition: Flag<["--"], "allow-multiple-definition">,
   HelpText<"Allow multiple definitions">;
 

 // than traditional linkers, so we don't need --start-group and --end-group.
 // These options are recongized for compatibility but ignored.
 def end_group : Flag<["--"], "end-group">;
 def end_group_paren: Flag<["-"], ")">;
 def start_group : Flag<["--"], "start-group">;
 def start_group_paren: Flag<["-"], "(">;
 
 // Options listed below are silently ignored for now for compatibility.
-def build_id : Flag<["--"], "build-id">;
 def fatal_warnings : Flag<["--"], "fatal-warnings">;
 def no_add_needed : Flag<["--"], "no-add-needed">;
 def no_fatal_warnings : Flag<["--"], "no-fatal-warnings">;
 def no_warn_mismatch : Flag<["--"], "no-warn-mismatch">;
 def version_script : Separate<["--"], "version-script">;
 def warn_common : Flag<["--"], "warn-common">;
 def warn_shared_textrel : Flag<["--"], "warn-shared-textrel">;
 def G : Separate<["-"], "G">;
 
 // Aliases for ignored options
 def alias_version_script_version_script : Joined<["--"], "version-script=">, Alias<version_script>;
 
 // Debugging options
 def save_temps : Flag<["-"], "save-temps">;

ELF/OutputSections.h

private:
   };
 
   uintX_t getFdePc(uintX_t EhVA, const FdeData &F);
 
   EHOutputSection<ELFT> *Sec = nullptr;
   std::vector<FdeData> FdeList;
 };
 
+template <class ELFT>
+class BuildIdSection final : public OutputSectionBase<ELFT> {
+public:
+  BuildIdSection();
+  void writeTo(uint8_t *Buf) override;
+  void update(ArrayRef<uint8_t> Buf);
+  void writeBuildId();
+
+private:
+  uint64_t Hash = 0xcbf29ce484222325; // FNV1 hash basis
+  uint8_t *HashBuf;
+};
+
 // All output sections that are hadnled by the linker specially are
 // globally accessible. Writer initializes them, so don't use them
 // until Writer is initialized.
 template <class ELFT> struct Out {
   typedef typename llvm::object::ELFFile<ELFT>::uintX_t uintX_t;
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Phdr Elf_Phdr;
+  static BuildIdSection<ELFT> *BuildId;
   static DynamicSection<ELFT> *Dynamic;
   static EhFrameHeader<ELFT> *EhFrameHdr;
   static GnuHashTableSection<ELFT> *GnuHashTab;
   static GotPltSection<ELFT> *GotPlt;
   static GotSection<ELFT> *Got;
   static HashTableSection<ELFT> *HashTab;
   static InterpSection<ELFT> *Interp;
   static OutputSection<ELFT> *Bss;
   static OutputSection<ELFT> *MipsRldMap;
   static OutputSectionBase<ELFT> *Opd;
   static uint8_t *OpdBuf;
   static PltSection<ELFT> *Plt;
   static RelocationSection<ELFT> *RelaDyn;
   static RelocationSection<ELFT> *RelaPlt;
   static StringTableSection<ELFT> *DynStrTab;
   static StringTableSection<ELFT> *ShStrTab;
   static StringTableSection<ELFT> *StrTab;
   static SymbolTableSection<ELFT> *DynSymTab;
   static SymbolTableSection<ELFT> *SymTab;
   static Elf_Phdr *TlsPhdr;
   static OutputSectionBase<ELFT> *ElfHeader;
   static OutputSectionBase<ELFT> *ProgramHeaders;
 };
 
+template <class ELFT> BuildIdSection<ELFT> *Out<ELFT>::BuildId;
 template <class ELFT> DynamicSection<ELFT> *Out<ELFT>::Dynamic;
 template <class ELFT> EhFrameHeader<ELFT> *Out<ELFT>::EhFrameHdr;
 template <class ELFT> GnuHashTableSection<ELFT> *Out<ELFT>::GnuHashTab;
 template <class ELFT> GotPltSection<ELFT> *Out<ELFT>::GotPlt;
 template <class ELFT> GotSection<ELFT> *Out<ELFT>::Got;
 template <class ELFT> HashTableSection<ELFT> *Out<ELFT>::HashTab;
 template <class ELFT> InterpSection<ELFT> *Out<ELFT>::Interp;
 template <class ELFT> OutputSection<ELFT> *Out<ELFT>::Bss;

ELF/OutputSections.cpp

uint8_t SymbolTableSection<ELFT>::getSymbolBinding(SymbolBody *Body) {
   if (const Elf_Sym *ESym = getElfSym<ELFT>(*Body))
     return ESym->getBinding();
   if (isa<DefinedSynthetic<ELFT>>(Body))
     return STB_LOCAL;
   return Body->isWeak() ? STB_WEAK : STB_GLOBAL;
 }
 
 template <class ELFT>
+BuildIdSection<ELFT>::BuildIdSection()
+    : OutputSectionBase<ELFT>(".note.gnu.build-id", SHT_NOTE, SHF_ALLOC) {
+  // 16 bytes for the note section header and 8 bytes for FNV1 hash.
+  this->Header.sh_size = 24;
+}
+
+template <class ELFT> void BuildIdSection<ELFT>::writeTo(uint8_t *Buf) {
+  const endianness E = ELFT::TargetEndianness;
+  write32<E>(Buf, 4);                   // Name size
+  write32<E>(Buf + 4, sizeof(Hash));    // Content size
+  write32<E>(Buf + 8, NT_GNU_BUILD_ID); // Type
+  memcpy(Buf + 12, "GNU", 4);           // Name string
+  HashBuf = Buf + 16;
+}
+
+template <class ELFT> void BuildIdSection<ELFT>::update(ArrayRef<uint8_t> Buf) {
+  // 64-bit FNV1 hash
+  const uint64_t Prime = 0x100000001b3;
+  for (uint8_t B : Buf) {
+    Hash *= Prime;
+    Hash ^= B;
+  }
+}
+
+template <class ELFT> void BuildIdSection<ELFT>::writeBuildId() {
+  const endianness E = ELFT::TargetEndianness;
+  write64<E>(HashBuf, Hash);
+}
+
+template <class ELFT>
 MipsReginfoOutputSection<ELFT>::MipsReginfoOutputSection()
     : OutputSectionBase<ELFT>(".reginfo", SHT_MIPS_REGINFO, SHF_ALLOC) {
   this->Header.sh_addralign = 4;
   this->Header.sh_entsize = sizeof(Elf_Mips_RegInfo);
   this->Header.sh_size = sizeof(Elf_Mips_RegInfo);
 }
 
 template <class ELFT>

 template class StringTableSection<ELF32BE>;
 template class StringTableSection<ELF64LE>;
 template class StringTableSection<ELF64BE>;
 
 template class SymbolTableSection<ELF32LE>;
 template class SymbolTableSection<ELF32BE>;
 template class SymbolTableSection<ELF64LE>;
 template class SymbolTableSection<ELF64BE>;
+
+template class BuildIdSection<ELF32LE>;
+template class BuildIdSection<ELF32BE>;
+template class BuildIdSection<ELF64LE>;
+template class BuildIdSection<ELF64BE>;
 }
 }

ELF/Writer.cpp

private:
   void scanRelocs(InputSectionBase<ELFT> &S, const Elf_Shdr &RelSec);
   void createPhdrs();
   void assignAddresses();
   void assignAddressesRelocatable();
   void fixAbsoluteSymbols();
   bool openFile();
   void writeHeader();
   void writeSections();
+  void writeBuildId();
   bool isDiscarded(InputSectionBase<ELFT> *IS) const;
   StringRef getOutputSectionName(InputSectionBase<ELFT> *S) const;
   bool needsInterpSection() const {
     return !Symtab.getSharedFiles().empty() && !Config->DynamicLinker.empty();
   }
   bool isOutputDynamic() const {
     return !Symtab.getSharedFiles().empty() || Config->Shared;
   }
template <class ELFT> void elf::writeResult(SymbolTable<ELFT> *Symtab) {
   StringTableSection<ELFT> ShStrTab(".shstrtab", false);
   SymbolTableSection<ELFT> DynSymTab(*Symtab, DynStrTab);
 
   OutputSectionBase<ELFT> ElfHeader("", 0, SHF_ALLOC);
   OutputSectionBase<ELFT> ProgramHeaders("", 0, SHF_ALLOC);
   ProgramHeaders.updateAlign(sizeof(uintX_t));
 
   // Instantiate optional output sections if they are needed.
+  std::unique_ptr<BuildIdSection<ELFT>> BuildId;
   std::unique_ptr<GnuHashTableSection<ELFT>> GnuHashTab;
   std::unique_ptr<GotPltSection<ELFT>> GotPlt;
   std::unique_ptr<HashTableSection<ELFT>> HashTab;
   std::unique_ptr<RelocationSection<ELFT>> RelaPlt;
   std::unique_ptr<StringTableSection<ELFT>> StrTab;
   std::unique_ptr<SymbolTableSection<ELFT>> SymTabSec;
   std::unique_ptr<OutputSection<ELFT>> MipsRldMap;
 
+  if (Config->BuildId)
+    BuildId.reset(new BuildIdSection<ELFT>);
   if (Config->GnuHash)
     GnuHashTab.reset(new GnuHashTableSection<ELFT>);
   if (Config->SysvHash)
     HashTab.reset(new HashTableSection<ELFT>);
   if (Target->UseLazyBinding) {
     StringRef S = IsRela ? ".rela.plt" : ".rel.plt";
     GotPlt.reset(new GotPltSection<ELFT>);
     RelaPlt.reset(new RelocationSection<ELFT>(S, IsRela));
   }
   if (!Config->StripAll) {
     StrTab.reset(new StringTableSection<ELFT>(".strtab", false));
     SymTabSec.reset(new SymbolTableSection<ELFT>(*Symtab, *StrTab));
   }
   if (Config->EMachine == EM_MIPS && !Config->Shared) {
     // This is a MIPS specific section to hold a space within the data segment
     // of executable file which is pointed to by the DT_MIPS_RLD_MAP entry.
     // See "Dynamic section" in Chapter 5 in the following document:
     // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
     MipsRldMap.reset(new OutputSection<ELFT>(".rld_map", SHT_PROGBITS,
                                              SHF_ALLOC | SHF_WRITE));
     MipsRldMap->setSize(sizeof(uintX_t));
     MipsRldMap->updateAlign(sizeof(uintX_t));
   }
 
+  Out<ELFT>::BuildId = BuildId.get();
   Out<ELFT>::DynStrTab = &DynStrTab;
   Out<ELFT>::DynSymTab = &DynSymTab;
   Out<ELFT>::Dynamic = &Dynamic;
   Out<ELFT>::EhFrameHdr = &EhFrameHdr;
   Out<ELFT>::GnuHashTab = GnuHashTab.get();
   Out<ELFT>::Got = &Got;
   Out<ELFT>::GotPlt = GotPlt.get();
   Out<ELFT>::HashTab = HashTab.get();
template <class ELFT> void Writer<ELFT>::run() {
   } else {
     assignAddressesRelocatable();
   }
   fixAbsoluteSymbols();
   if (!openFile())
     return;
   writeHeader();
   writeSections();
+  writeBuildId();
   if (HasError)
     return;
   check(Buffer->commit());
 }
 
 namespace {
 template <bool Is64Bits> struct SectionKey {
   typedef typename std::conditional<Is64Bits, uint64_t, uint32_t>::type uintX_t;

 template <class ELFT> void Writer<ELFT>::addPredefinedSections() {
   auto Add = [&](OutputSectionBase<ELFT> *C) {
     if (C)
       OutputSections.push_back(C);
   };
 
   // This order is not the same as the final output order
   // because we sort the sections using their attributes below.
+  Add(Out<ELFT>::BuildId);
   Add(Out<ELFT>::SymTab);
   Add(Out<ELFT>::ShStrTab);
   Add(Out<ELFT>::StrTab);
   if (isOutputDynamic()) {
     Add(Out<ELFT>::DynSymTab);
     Add(Out<ELFT>::GnuHashTab);
     Add(Out<ELFT>::HashTab);
     Add(Out<ELFT>::Dynamic);
if (OutputSectionBase<ELFT> *Sec = Out<ELFT>::Opd) {
     Sec->writeTo(Buf + Sec->getFileOff());
   }
 
   for (OutputSectionBase<ELFT> *Sec : OutputSections)
     if (Sec != Out<ELFT>::Opd)
       Sec->writeTo(Buf + Sec->getFileOff());
 }
 
+template <class ELFT> void Writer<ELFT>::writeBuildId() {
+  BuildIdSection<ELFT> *S = Out<ELFT>::BuildId;
+  if (!S)
+    return;
+
+  // Compute a hash of all sections except .debug_* sections.
+  // We skip debug sections because they tend to be very large
+  // and their contents are very likely to be the same as long as
+  // other sections are the same.
+  uint8_t *Start = Buffer->getBufferStart();
+  uint8_t *Last = Start;
+  for (OutputSectionBase<ELFT> *Sec : OutputSections) {
+    uint8_t *End = Start + Sec->getFileOff();
+    if (!Sec->getName().startswith(".debug_"))
+      S->update({Last, End});
+    Last = End;
+  }
+  S->update({Last, Start + FileSize});
+
+  // Fill the hash value field in the .note.gnu.build-id section.
+  S->writeBuildId();
+}
+
 template void elf::writeResult<ELF32LE>(SymbolTable<ELF32LE> *Symtab);
 template void elf::writeResult<ELF32BE>(SymbolTable<ELF32BE> *Symtab);
 template void elf::writeResult<ELF64LE>(SymbolTable<ELF64LE> *Symtab);
 template void elf::writeResult<ELF64BE>(SymbolTable<ELF64BE> *Symtab);

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=BUILDID %s
+# RUN: ld.lld %t -o %t2
+# RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=NO-BUILDID %s
+
+.globl _start;
+_start:
+  nop
+
+# BUILDID:      Contents of section .note.gnu.build-id:
+# BUILDID-NEXT: 04000000 08000000 03000000 474e5500  ............GNU.
+
+# NO-BUILDID-NOT: Contents of section .note.gnu.build-id: