Reapply: [WebAssembly] Implement build-id feature

[dschuff]

Summary

Add explicit cast to hopefully satisfy MSVC

[dschuff]

• clang-format
• more cast?

lld/test/wasm/build-id.test

+# RUN: llvm-mc -filetype=obj -triple=wasm32 %p/Inputs/start.s -o %t
+
+# RUN: wasm-ld --build-id %t -o %t2
+# RUN: llvm-objdump -s %t2 | FileCheck --check-prefix=DEFAULT %s
+# RUN: wasm-ld  --build-id=fast %t -o %t2
+# RUN: llvm-objdump -s %t2 | FileCheck --check-prefix=DEFAULT %s
+# RUN: wasm-ld  --build-id %t -o %t2 --threads=1
+# RUN: llvm-objdump -s %t2 | FileCheck --check-prefix=DEFAULT %s
+
+# RUN: wasm-ld  --build-id=sha1 %t -o %t2
+# RUN: llvm-objdump -s %t2 | FileCheck --check-prefix=SHA1 %s
+# RUN: wasm-ld  --build-id=sha1 %t -o %t2 --threads=1
+# RUN: llvm-objdump -s %t2 | FileCheck --check-prefix=SHA1 %s
+
+# RUN: wasm-ld  --build-id=tree %t -o %t2
+# RUN: llvm-objdump -s %t2 | FileCheck --check-prefix=SHA1 %s
+# RUN: wasm-ld  --build-id=tree %t -o %t2 --threads=1
+# RUN: llvm-objdump -s %t2 | FileCheck --check-prefix=SHA1 %s
+
+# RUN: wasm-ld  --build-id=uuid %t -o %t2
+# RUN: llvm-objdump -s %t2 | FileCheck --check-prefix=UUID %s
+
+# RUN: wasm-ld  --build-id=0x12345678 %t -o %t2
+# RUN: llvm-objdump -s %t2 | FileCheck --check-prefix=HEX %s
+
+# RUN: wasm-ld  %t -o %t2
+# RUN: llvm-objdump -s %t2 | FileCheck --check-prefix=NONE %s
+
+# RUN: wasm-ld  --build-id=sha1 --build-id=none %t -o %t2
+# RUN: llvm-objdump -s %t2 | FileCheck --check-prefix=NONE %s
+# RUN: wasm-ld  --build-id --build-id=none %t -o %t2
+# RUN: llvm-objdump -s %t2 | FileCheck --check-prefix=NONE %s
+# RUN: wasm-ld  --build-id=none --build-id %t -o %t2
+# RUN: llvm-objdump -s %t2 | FileCheck --check-prefix=DEFAULT %s
+
+.section .data.foo,"",@
+        .globl  foo
+        .hidden  foo
+        .p2align        2
+foo:
+        .int32  1
+        .size   foo, 4
+
+
+# DEFAULT:      Contents of section build_id:
+# DEFAULT-NEXT: 0000 10cdbf99 f76b1f5e ebb2f36a 1bde1d6c  .....k.^...j...l
+# DEFAULT-NEXT: 0010 01
+
+# SHA1:      Contents of section build_id:
+# SHA1-NEXT: 0000 14ad22e8 54d72438 94af85de 3c5592bd  ..".T.$8....<U..
+# SHA1-NEXT: 0010 1b5ec96f 6b                          .^.ok
+
+# UUID:      Contents of section build_id:
+# UUID-NEXT: 0000 10
+
+# HEX:      Contents of section build_id:
+# HEX-NEXT:  0000 04123456 78                          ..4Vx
+
+
+# NONE-NOT: Contents of section build_id:

lld/wasm/Config.h

 } // namespace llvm::CodeGenOpt
 
 namespace lld {
 namespace wasm {
 
 // For --unresolved-symbols.
 enum class UnresolvedPolicy { ReportError, Warn, Ignore, ImportDynamic };
 
+// For --build-id.
+enum class BuildIdKind { None, Fast, Sha1, Hexstring, Uuid };
+
 // This struct contains the global configuration for the linker.
 // Most fields are direct mapping from the command line options
 // and such fields have the same name as the corresponding options.
 // Most fields are initialized by the driver.
 struct Configuration {
   bool bsymbolic;
   bool checkFeatures;
   bool compressRelocations;
struct Configuration {
   uint64_t zStackSize;
   unsigned ltoPartitions;
   unsigned ltoo;
   llvm::CodeGenOpt::Level ltoCgo;
   unsigned optimize;
   llvm::StringRef thinLTOJobs;
   bool ltoDebugPassManager;
   UnresolvedPolicy unresolvedSymbols;
+  BuildIdKind buildId = BuildIdKind::None;
 
   llvm::StringRef entry;
   llvm::StringRef mapFile;
   llvm::StringRef outputFile;
   llvm::StringRef thinLTOCacheDir;
 
   llvm::StringSet<> allowUndefinedSymbols;
   llvm::StringSet<> exportedSymbols;
   std::vector<llvm::StringRef> requiredExports;
   llvm::SmallVector<llvm::StringRef, 0> searchPaths;
   llvm::CachePruningPolicy thinLTOCachePolicy;
   std::optional<std::vector<std::string>> features;
   std::optional<std::vector<std::string>> extraFeatures;
+  llvm::SmallVector<uint8_t, 0> buildIdVector;
 
   // The following config options do not directly correspond to any
   // particular command line options.
 
   // True if we are creating position-independent code.
   bool isPic;
 
   // True if we have an MVP input that uses __indirect_function_table and which

lld/wasm/Driver.cpp

if (auto *arg = args.getLastArg(OPT_unresolved_symbols)) {
     if (s == "report-all")
       return errorOrWarn;
     error("unknown --unresolved-symbols value: " + s);
   }
 
   return errorOrWarn;
 }
 
+// Parse --build-id or --build-id=<style>. We handle "tree" as a
+// synonym for "sha1" because all our hash functions including
+// -build-id=sha1 are actually tree hashes for performance reasons.
+static std::pair<BuildIdKind, SmallVector<uint8_t, 0>>
+getBuildId(opt::InputArgList &args) {
+  auto *arg = args.getLastArg(OPT_build_id, OPT_build_id_eq);
+  if (!arg)
+    return {BuildIdKind::None, {}};
+
+  if (arg->getOption().getID() == OPT_build_id)
+    return {BuildIdKind::Fast, {}};
+
+  StringRef s = arg->getValue();
+  if (s == "fast")
+    return {BuildIdKind::Fast, {}};
+  if (s == "sha1" || s == "tree")
+    return {BuildIdKind::Sha1, {}};
+  if (s == "uuid")
+    return {BuildIdKind::Uuid, {}};
+  if (s.startswith("0x"))
+    return {BuildIdKind::Hexstring, parseHex(s.substr(2))};
+
+  if (s != "none")
+    error("unknown --build-id style: " + s);
+  return {BuildIdKind::None, {}};
+}
+
 // Initializes Config members by the command line options.
 static void readConfigs(opt::InputArgList &args) {
   config->bsymbolic = args.hasArg(OPT_Bsymbolic);
   config->checkFeatures =
       args.hasFlag(OPT_check_features, OPT_no_check_features, true);
   config->compressRelocations = args.hasArg(OPT_compress_relocations);
   config->demangle = args.hasFlag(OPT_demangle, OPT_no_demangle, true);
   config->disableVerify = args.hasArg(OPT_disable_verify);
static void readConfigs(opt::InputArgList &args) {
   // --unresolve-symbols=ignore + --import-undefined
   if (args.hasArg(OPT_allow_undefined)) {
     config->importUndefined = true;
     config->unresolvedSymbols = UnresolvedPolicy::Ignore;
   }
 
   if (args.hasArg(OPT_print_map))
     config->mapFile = "-";
+
+  std::tie(config->buildId, config->buildIdVector) = getBuildId(args);
 }
 
 // Some Config members do not directly correspond to any particular
 // command line options, but computed based on other Config values.
 // This function initialize such members. See Config.h for the details
 // of these values.
 static void setConfigs() {
   config->isPic = config->pie || config->shared;

lld/wasm/Options.td

 
 // The following flags are shared with the ELF linker
 def Bsymbolic: F<"Bsymbolic">, HelpText<"Bind defined symbols locally">;
 
 def Bdynamic: F<"Bdynamic">, HelpText<"Link against shared libraries (default)">;
 
 def Bstatic: F<"Bstatic">, HelpText<"Do not link against shared libraries">;
 
+def build_id: F<"build-id">, HelpText<"Alias for --build-id=fast">;
+
+def build_id_eq: J<"build-id=">, HelpText<"Generate build ID note">,
+  MetaVarName<"[fast,sha1,uuid,0x<hexstring>]">;
+
 defm color_diagnostics: B<"color-diagnostics",
   "Alias for --color-diagnostics=always",
   "Alias for --color-diagnostics=never">;
 def color_diagnostics_eq: J<"color-diagnostics=">,
   HelpText<"Use colors in diagnostics (default: auto)">,
   MetaVarName<"[auto,always,never]">;
 
 def compress_relocations: F<"compress-relocations">,

lld/wasm/SyntheticSections.h

RelocSection(StringRef name, OutputSection *sec)
         sec(sec) {}
   void writeBody() override;
   bool isNeeded() const override { return sec->getNumRelocations() > 0; };
 
 protected:
   OutputSection *sec;
 };
 
+class BuildIdSection : public SyntheticSection {
+public:
+  BuildIdSection();
+  void writeBody() override;
+  bool isNeeded() const override {
+    return config->buildId != BuildIdKind::None;
+  }
+  void writeBuildId(llvm::ArrayRef<uint8_t> buf);
+  void writeTo(uint8_t *buf) override {
+    LLVM_DEBUG(llvm::dbgs() << "BuildId writeto buf " << buf << " offset "
+               << offset << " headersize " << header.size() << '\n');
+    // The actual build ID is derived from a hash of all of the output
+    // sections, so it can't be calculated until they are written. Here
+    // we write the section leaving zeros in place of the hash.
+    SyntheticSection::writeTo(buf);
+    // Calculate and store the location where the hash will be written.
+    hashPlaceholderPtr = buf + offset + header.size() +
+                         +sizeof(buildIdSectionName) /*name string*/ +
+                         1 /* hash size */;
+  }
+
+  const uint32_t hashSize;
+
+private:
+  static constexpr char buildIdSectionName[] = "build_id";
+  uint8_t *hashPlaceholderPtr = nullptr;
+};
+
 // Linker generated output sections
 struct OutStruct {
   DylinkSection *dylinkSec;
   TypeSection *typeSec;
   FunctionSection *functionSec;
   ImportSection *importSec;
   TableSection *tableSec;
   MemorySection *memorySec;
   GlobalSection *globalSec;
   TagSection *tagSec;
   ExportSection *exportSec;
   StartSection *startSec;
   ElemSection *elemSec;
   DataCountSection *dataCountSec;
   LinkingSection *linkingSec;
   NameSection *nameSec;
   ProducersSection *producersSec;
   TargetFeaturesSection *targetFeaturesSec;
+  BuildIdSection *buildIdSec;
 };
 
 extern OutStruct out;
 
 } // namespace wasm
 } // namespace lld
 
 #endif

lld/wasm/SyntheticSections.cpp

 void RelocSection::writeBody() {
   uint32_t count = sec->getNumRelocations();
   assert(sec->sectionIndex != UINT32_MAX);
   writeUleb128(bodyOutputStream, sec->sectionIndex, "reloc section");
   writeUleb128(bodyOutputStream, count, "reloc count");
   sec->writeRelocations(bodyOutputStream);
 }
 
+static size_t getHashSize() {
+  switch (config->buildId) {
+  case BuildIdKind::Fast:
+  case BuildIdKind::Uuid:
+    return 16;
+  case BuildIdKind::Sha1:
+    return 20;
+  case BuildIdKind::Hexstring:
+    return config->buildIdVector.size();
+  case BuildIdKind::None:
+    return 0;
+  }
+}
+
+BuildIdSection::BuildIdSection()
+    : SyntheticSection(llvm::wasm::WASM_SEC_CUSTOM, buildIdSectionName),
+      hashSize(getHashSize()) {}
+
+void BuildIdSection::writeBody() {
+  LLVM_DEBUG(llvm::dbgs() << "BuildId writebody\n");
+  // Write hash size
+  auto &os = bodyOutputStream;
+  writeUleb128(os, hashSize, "build id size");
+  writeBytes(os, std::vector<char>(hashSize, ' ').data(), hashSize,
+   "placeholder");
+}
+
+void BuildIdSection::writeBuildId(llvm::ArrayRef<uint8_t> buf) {
+  assert(buf.size() == hashSize);
+  LLVM_DEBUG(dbgs() << "buildid write " << buf.size() << " "
+                    << hashPlaceholderPtr << '\n');
+  memcpy(hashPlaceholderPtr, buf.data(), hashSize);
+}
+
 } // namespace wasm
 } // namespace lld

lld/wasm/Writer.cpp

 #include "InputElement.h"
 #include "MapFile.h"
 #include "OutputSections.h"
 #include "OutputSegment.h"
 #include "Relocations.h"
 #include "SymbolTable.h"
 #include "SyntheticSections.h"
 #include "WriterUtils.h"
+#include "lld/Common/Arrays.h"
 #include "lld/Common/CommonLinkerContext.h"
 #include "lld/Common/Strings.h"
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/BinaryFormat/Wasm.h"
 #include "llvm/BinaryFormat/WasmTraits.h"
 #include "llvm/Support/FileOutputBuffer.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/LEB128.h"
 #include "llvm/Support/Parallel.h"
+#include "llvm/Support/RandomNumberGenerator.h"
+#include "llvm/Support/SHA1.h"
+#include "llvm/Support/xxhash.h"
 
 #include <cstdarg>
 #include <map>
 #include <optional>
 
 #define DEBUG_TYPE "lld"
 
 using namespace llvm;
private:
   void createSyntheticSectionsPostLayout();
   void finalizeSections();
 
   // Custom sections
   void createRelocSections();
 
   void writeHeader();
   void writeSections();
+  void writeBuildId();
 
   uint64_t fileSize = 0;
 
   std::vector<WasmInitEntry> initFunctions;
   llvm::StringMap<std::vector<InputChunk *>> customSectionMapping;
 
   // Stable storage for command export wrapper function name strings.
   std::list<std::string> commandExportWrapperNames;

 void Writer::writeSections() {
   uint8_t *buf = buffer->getBufferStart();
   parallelForEach(outputSections, [buf](OutputSection *s) {
     assert(s->isNeeded());
     s->writeTo(buf);
   });
 }
 
+// Computes a hash value of Data using a given hash function.
+// In order to utilize multiple cores, we first split data into 1MB
+// chunks, compute a hash for each chunk, and then compute a hash value
+// of the hash values.
+
+static void
+computeHash(llvm::MutableArrayRef<uint8_t> hashBuf,
+            llvm::ArrayRef<uint8_t> data,
+            std::function<void(uint8_t *dest, ArrayRef<uint8_t> arr)> hashFn) {
+  std::vector<ArrayRef<uint8_t>> chunks = split(data, 1024 * 1024);
+  std::vector<uint8_t> hashes(chunks.size() * hashBuf.size());
+
+  // Compute hash values.
+  parallelFor(0, chunks.size(), [&](size_t i) {
+    hashFn(hashes.data() + i * hashBuf.size(), chunks[i]);
+  });
+
+  // Write to the final output buffer.
+  hashFn(hashBuf.data(), hashes);
+}
+
+static void makeUUID(unsigned version, llvm::ArrayRef<uint8_t> fileHash,
+                     llvm::MutableArrayRef<uint8_t> output) {
+  assert(version == 4 || version == 5 && "Unknown UUID version");
+  assert(output.size() == 16 && "Wrong size for UUID output");
+  if (version == 5) {
+    // Build a valid v5 UUID from a hardcoded (randomly-generated) namespace
+    // UUID, and the computed hash of the output.
+    std::array<uint8_t, 16> namespaceUUID{0xA1, 0xFA, 0x48, 0x2D, 0x0E, 0x22,
+                                          0x03, 0x8D, 0x33, 0x8B, 0x52, 0x1C,
+                                          0xD6, 0xD2, 0x12, 0xB2};
+    SHA1 sha;
+    sha.update(namespaceUUID);
+    sha.update(fileHash);
+    auto s = sha.final();
+    std::copy(s.begin(),
+              // Explicit cast to make MSVC happy
+              static_cast<uint8_t *>(&s[output.size()]),
+              output.begin());
+  } else if (version == 4) {
+    if (auto ec = llvm::getRandomBytes(output.data(), output.size()))
+      error("entropy source failure: " + ec.message());
+  }
+  // Set the UUID version and variant fields.
+  // The version is the upper nibble of byte 6 (0b0101xxxx or 0b0100xxxx)
+  output[6] = (static_cast<uint8_t>(version) << 4) | (output[6] & 0xF);
+
+  // The variant is DCE 1.1/ISO 11578 (0b10xxxxxx)
+  output[8] &= 0xBF;
+  output[8] |= 0x80;
+}
+
+void Writer::writeBuildId() {
+  if (!out.buildIdSec->isNeeded())
+    return;
+  if (config->buildId == BuildIdKind::Hexstring) {
+    out.buildIdSec->writeBuildId(config->buildIdVector);
+    return;
+  }
+
+  // Compute a hash of all sections of the output file.
+  size_t hashSize = out.buildIdSec->hashSize;
+  std::vector<uint8_t> buildId(hashSize);
+  llvm::ArrayRef<uint8_t> buf{buffer->getBufferStart(), size_t(fileSize)};
+
+  switch (config->buildId) {
+   case BuildIdKind::Fast:{
+    std::vector<uint8_t> fileHash(8);
+    computeHash(fileHash, buf, [](uint8_t *dest, ArrayRef<uint8_t> arr) {
+      support::endian::write64le(dest, xxHash64(arr));
+    });
+    makeUUID(5, fileHash, buildId);
+    break;
+   }
+  case BuildIdKind::Sha1:
+    computeHash(buildId, buf, [&](uint8_t *dest, ArrayRef<uint8_t> arr) {
+      memcpy(dest, SHA1::hash(arr).data(), hashSize);
+    });
+    break;
+  case BuildIdKind::Uuid:
+    makeUUID(4, {}, buildId);
+    break;
+  default:
+    llvm_unreachable("unknown BuildIdKind");
+  }
+  out.buildIdSec->writeBuildId(buildId);
+}
+
 static void setGlobalPtr(DefinedGlobal *g, uint64_t memoryPtr) {
   LLVM_DEBUG(dbgs() << "setGlobalPtr " << g->getName() << " -> " << memoryPtr << "\n");
   g->global->setPointerValue(memoryPtr);
 }
 
 // Fix the memory layout of the output binary.  This assigns memory offsets
 // to each of the input data sections as well as the explicit stack region.
 // The default memory layout is as follows, from low to high.
void Writer::addSections() {
   addSection(out.linkingSec);
   if (config->emitRelocs || config->relocatable) {
     createRelocSections();
   }
 
   addSection(out.nameSec);
   addSection(out.producersSec);
   addSection(out.targetFeaturesSec);
+  addSection(out.buildIdSec);
 }
 
 void Writer::finalizeSections() {
   for (OutputSection *s : outputSections) {
     s->setOffset(fileSize);
     s->finalizeContents();
     fileSize += s->getSize();
   }
void Writer::createSyntheticSections() {
   out.memorySec = make<MemorySection>();
   out.tagSec = make<TagSection>();
   out.globalSec = make<GlobalSection>();
   out.exportSec = make<ExportSection>();
   out.startSec = make<StartSection>();
   out.elemSec = make<ElemSection>();
   out.producersSec = make<ProducersSection>();
   out.targetFeaturesSec = make<TargetFeaturesSection>();
+  out.buildIdSec = make<BuildIdSection>();
 }
 
 void Writer::createSyntheticSectionsPostLayout() {
   out.dataCountSec = make<DataCountSection>(segments);
   out.linkingSec = make<LinkingSection>(initFunctions, segments);
   out.nameSec = make<NameSection>(segments);
 }
 
void Writer::run() {
   openFile();
   if (errorCount())
     return;
 
   writeHeader();
 
   log("-- writeSections");
   writeSections();
+  writeBuildId();
   if (errorCount())
     return;
 
   if (Error e = buffer->commit())
     fatal("failed to write output '" + buffer->getPath() +
           "': " + toString(std::move(e)));
 }