ELF: Implement --build-id.

[MaskRay]

Summary

This is not ready for submission.

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

The problem is that its performance impact is too large. Computing a secure
hash is a computational intensive task (our md5sum function seems a bit too
slow, though). Here are some numbers (milliseconds to link):

LLD: 713.78 -> 883.44 (+23.8%)
Scylla: 5005.64 -> 5437.84 (+8.6%)

Even if we replace MD5 with a faster hash function, it cannot be within
an "okay" range, which is, say, +3%.

Do you guys have any opnion on this? I have a few ideas.

• Use CRC32 instead of MD5. Non-secure hash should be much faster.
• Make clang to calculate a secure hash for each section. This is basically moving the workload from the linker to the compiler, but we can use the hash for ICF in the linker, so it might be a overall win.
• Compute a build-id from input files' timestamps. This makes builds non-reproducible if you touch a file, so I don't think we want this.
• Build-id is not needed for program execution in general. So we may be able to let the linker exit as soon as it's done with linking, and backfill the hash value in a background process which is kicked in by the linker. (It's probably unrealistic plan, though.)
• Do not support build-id and let the user pass --build-id=<hash value>.

[emaste]

I think crc32 is a nonstarter: we probably don't need all of the attributes of a cryptographically secure hash, we do want to avoid collisions and I don't think crc32 is sufficient. Off hand I'd suggest we might want to try blake2b (https://blake2.net/). Timestamps are no good due to collisions and nonreproducibility.

Make clang to calculate a secure hash for each section. This is basically moving the workload from the linker to the compiler, but we can use the hash for ICF in the linker, so it might be a overall win.

This is a pretty neat idea, and we can easily combine those hashes into the output build-id value. We'd have to come up with an appropriate way to store those hashes though.

I was thinking about an approach of post-filling build-id in FreeBSD, because we'd like --build-id and it's not supported in GNU ld 2.17.50 that we have in the base system. We'd provide a dummy space for a build-id note e.g. in csu, and give objcopy the ability to fill that in. But I agree that it doesn't make a lot of sense in the context of a feature to add to lld.

Do not support build-id and let the user pass --build-id=<hash value>.

bfd and gold both allow a hash value to be specified directly and it seems reasonable to support that mode even when some other hashing is implemented.

All of that said, I think something like blake2 is not too far off -- my 4 year old desktop uses 1.6 CPU seconds to hash a 1GB random file. We can also look at a threaded model for hash calculation.

In any case, a straightforward (but optimized) approach in lld is going to be no worse than invoking a separate tool to calculate and store the hash, and for my use case that's fine. Is it that unreasonable to pay the cost if the user specifies --build-id, and it's off by default for the regular edit-compile-test cycle?

[dblaikie]

Do you have a sense of how other linkers implement this feature and/or how
much it costs in performance/link time? You mention what an "okay" cost for
this would be, but it's not clear to me how you determined that cost.

[• rafael]

BTW, have you tried this in combination with the patch for using
posix_memalign? Since this basically reads back the output of the
linker I would be curious if that patch makes any difference is the
results.

• Use CRC32 instead of MD5. Non-secure hash should be much faster.

That is a bit too weak I think, but we can block this on getting a
better MD5 or use another strong but fast hash.

• Make clang to calculate a secure hash for each section. This is basically moving the workload from the linker to the compiler, but we can use the hash for ICF in the linker, so it might be a overall win.

Seems like something we should do in the future, but should not depend
on it. That is, having the hash available speeds up build-id, but
build-id should work without it.

• Compute a build-id from input files' timestamps. This makes builds non-reproducible if you touch a file, so I don't think we want this.

Not this. O use of build-id is for checking for reproducible builds I think.

• Build-id is not needed for program execution in general. So we may be able to let the linker exit as soon as it's done with linking, and backfill the hash value in a background process which is kicked in by the linker. (It's probably unrealistic plan, though.)

A bit dangerous I would say.

Cheers,
Rafael

[silvas]

One thing that is missing from the data you provided in the OP is the actual amount of data hashed, and in what pattern (lots of small, or a couple large?). How fast does the hashing have to be to be "acceptable"? E.g. ADT/Hashing.h claims 6.5GB/s hashing for large keys on Nehalem (which is pretty old at this point, modern CPU's likely to better). That is 6.5MB/ms. If we need to hash 100MB then the overhead should be about 15ms.

For LLD, you quoted a number 713.78ms link time. So for 1% overhead we need to spend <7ms. This is enough for 45MB hashed with ADT/Hashing.h (which is similar to LLD text+data size), assuming that we can get max memory bandwidth (like Rafael said, we can do this while we would be copying data otherwise, so I don't see a reason we can't hit the full performance of ADT/Hashing.h).

[ruiu]

For LLD, it hashed 75,421,320 bytes. For Scylla, it hashed 207,703,010
bytes. So the throughput of MD5 is 444 MB/s and 480 MB/s, respectively.

BLAKE2 claims that it is about 1.6x faster than MD5, but it is probably the
lower bound for a secure hash function.

[ismail]

This comment was removed by ismail.

[emaste]

Moved to D18091

[ruiu]

I implemented --build-id=md5 in this patch (http://reviews.llvm.org/D18055),
but since this patch adds more knobs to the linker, I'm not going to submit
this until someone comes and convinces us that we really need this.

[ruiu]

Sorry, the correct URL is http://reviews.llvm.org/D18114.

[emaste]

This review should be closed or abandoned as --build-id is implemented

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">;
+
 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

 //===- OutputSections.h -----------------------------------------*- C++ -*-===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_ELF_OUTPUT_SECTIONS_H
 #define LLD_ELF_OUTPUT_SECTIONS_H
 
 #include "lld/Core/LLVM.h"
 
 #include "llvm/MC/StringTableBuilder.h"
 #include "llvm/Object/ELF.h"
+#include "llvm/Support/MD5.h"
 
 #include "Config.h"
 
 #include <type_traits>
 
 namespace lld {
 namespace elf {
 
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:
+  llvm::MD5 Hash;
+  uint8_t *Md5Buf;
+};
+
 // 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, 0) {
+  // 16 bytes for the note section header and 16 bytes for MD5.
+  this->Header.sh_size = 32;
+}
+
+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, 16);    // Content size
+  write32<E>(Buf + 8, 3);     // Type (NT_GNU_BUILD_ID = 3)
+  memcpy(Buf + 12, "GNU", 4); // Name string
+  Md5Buf = Buf + 16;
+}
+
+template <class ELFT> void BuildIdSection<ELFT>::update(ArrayRef<uint8_t> Buf) {
+  Hash.update(Buf);
+}
+
+template <class ELFT> void BuildIdSection<ELFT>::writeBuildId() {
+  MD5::MD5Result Res;
+  Hash.final(Res);
+  memcpy(Md5Buf, Res, 16);
+}
+
+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<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>;
+
 template uint32_t getLocalRelTarget(const ObjectFile<ELF32LE> &,
                                     const ELFFile<ELF32LE>::Elf_Rel &,
                                     uint32_t);
 template uint32_t getLocalRelTarget(const ObjectFile<ELF32BE> &,
                                     const ELFFile<ELF32BE>::Elf_Rel &,
                                     uint32_t);
 template uint64_t getLocalRelTarget(const ObjectFile<ELF64LE> &,
                                     const ELFFile<ELF64LE>::Elf_Rel &,

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() {
   }
   fixAbsoluteSymbols();
   if (!openFile())
     return;
   writeHeader();
   writeSections();
   if (HasError)
     return;
+  writeBuildId();
   check(Buffer->commit());
 }
 
 namespace {
 template <bool Is64Bits> struct SectionKey {
   typedef typename std::conditional<Is64Bits, uint64_t, uint32_t>::type uintX_t;
   StringRef Name;
   uint32_t Type;

 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 the md5sum 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 MD5 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);