[WebAssembly] Implement build-id feature

[dschuff]

Summary

Implement the --build-id flag similarly to ELF, and generate a build_id section according to the WebAssembly tool convention specified in https://github.com/WebAssembly/tool-conventions/pull/183

The default style ("fast" aka "tree") hashes the contents of the output and (unlike ELF) generates a v5 UUID based on the hash (using a random namespace).
It also supports generating a random v4 UUID, a sha1 hash, and a user-specified string (as ELF does).

[dschuff]

fix, and rebase

[dschuff]

• Clean up and add test

[dschuff]

• remove stray line

[sbc100]

Great to see this happening!

lld/test/wasm/build-id.s

1 ↗

(On Diff #433561)

lld/test/wasm/lit.local.cfg already takes care of this IIUC

43 ↗

(On Diff #433561)

Why not just use lld/test/wasm/Inputs/start.s for this test .. or does it depend on there being some data?

When you could remove all the --no-entry flags above, and all the comment markers, and just call this file .test.

lld/wasm/Driver.cpp

390

Do we want to support the tree alias? I assume this comes from the ELF backend?

lld/wasm/SyntheticSections.cpp

923

Do you want to leave these TODOs in here?

[dschuff]

• use start.s as a test instead

lld/test/wasm/build-id.s

43 ↗

(On Diff #433561)

no, it doesn't depend on there being data, I basically just started with the x86 version of this same test. But it has some additional assertions that don't apply to us.
So you're saying this would be a .test file because it would only have RUN lines, and the runs would just assemble start.s? That sounds good.

lld/wasm/Driver.cpp

390

yes, this comes from the ELF backend. I think it probably makes sense to support the same options? I would think we'd at least want random UUID, some kind of hash, and user-defined. See also the discussion on the tool-conventions issue though, I'm open to making the implementation different if that makes sense.

lld/wasm/SyntheticSections.cpp

923

no, the idea is to remove them once the discussion on tool-conventions is resolved and before committing this.

[dschuff]

Rebase, create valid UUID for fast hash build ID, remove md5

[dschuff]

Correctly rebase against main

[dschuff]

I think this is ready for another review, PTAL.

I'd like to maybe also update objdump and/or other tools to print the build ID in UUID form when applicable, but that can be a followup change.

[sbc100]

lgtm % some minor nits

lld/wasm/SyntheticSections.h

444

This seems a little hacky / fragile, but I can't think of a more elegant way to do it..

lld/wasm/Writer.cpp

1834

I wonder if this should have a name that lets the reader know its going back an patching an existing location? Maybe patchBuildId ? But that doesn't convey that this function also calulates the buildid? "calculateAndPatchBuildId" seems like too much of a mouthful.

Maybe your existing names is best :)

[dschuff]

• clean up baked-in buffer size

lld/wasm/SyntheticSections.h

444

Ah yes I meant to try to fix that; WDYT of this fix?

lld/wasm/Writer.cpp

1834

Yeah, those names are maybe a bit more descriptive but not obviously much better. This is the same name used by the other object formats (and has similar behavior) so consistency seems good in the end.

[sbc100]

lld/wasm/SyntheticSections.h

444

Seems better, but maybe add a comment here. What is hashBuf for? Could a better name be used here? isHashLocation? hashPlaceholderPtr?

lld/wasm/Writer.cpp

1834

Makes sense

[dschuff]

• add comment and rename hashBuf

[dyung]

@dschuff, I'm not sure if you are aware, but your change fails to build on Windows. You can see the failure on this buildbot:
https://lab.llvm.org/buildbot/#/builders/216/builds/17875

FAILED: tools/lld/wasm/CMakeFiles/lldWasm.dir/Writer.cpp.obj 
C:\bin\ccache.exe C:\PROGRA~2\MICROS~1\2019\BUILDT~1\VC\Tools\MSVC\1429~1.301\bin\HostX64\x64\cl.exe  /nologo /TP -DGTEST_HAS_RTTI=0 -DUNICODE -D_CRT_NONSTDC_NO_DEPRECATE -D_CRT_NONSTDC_NO_WARNINGS -D_CRT_SECURE_NO_DEPRECATE -D_CRT_SECURE_NO_WARNINGS -D_GLIBCXX_ASSERTIONS -D_HAS_EXCEPTIONS=0 -D_LIBCPP_ENABLE_ASSERTIONS -D_SCL_SECURE_NO_DEPRECATE -D_SCL_SECURE_NO_WARNINGS -D_UNICODE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -Itools\lld\wasm -IC:\buildbot-root\llvm-clang-x86_64-sie-win\llvm-project\lld\wasm -IC:\buildbot-root\llvm-clang-x86_64-sie-win\llvm-project\lld\include -Itools\lld\include -Iinclude -IC:\buildbot-root\llvm-clang-x86_64-sie-win\llvm-project\llvm\include /DWIN32 /D_WINDOWS   /Zc:inline /Zc:preprocessor /Zc:__cplusplus /Oi /bigobj /permissive- /W4 -wd4141 -wd4146 -wd4244 -wd4267 -wd4291 -wd4351 -wd4456 -wd4457 -wd4458 -wd4459 -wd4503 -wd4624 -wd4722 -wd4100 -wd4127 -wd4512 -wd4505 -wd4610 -wd4510 -wd4702 -wd4245 -wd4706 -wd4310 -wd4701 -wd4703 -wd4389 -wd4611 -wd4805 -wd4204 -wd4577 -wd4091 -wd4592 -wd4319 -wd4709 -wd5105 -wd4324 -w14062 -we4238 /Gw /MD /O2 /Ob2   -wd4530 -wd4062  /EHs-c- /GR- -UNDEBUG -std:c++17 /showIncludes /Fotools\lld\wasm\CMakeFiles\lldWasm.dir\Writer.cpp.obj /Fdtools\lld\wasm\CMakeFiles\lldWasm.dir\lldWasm.pdb /FS -c C:\buildbot-root\llvm-clang-x86_64-sie-win\llvm-project\lld\wasm\Writer.cpp
C:\buildbot-root\llvm-clang-x86_64-sie-win\llvm-project\lld\wasm\Writer.cpp(263): error C2672: 'std::copy': no matching overloaded function found
C:\buildbot-root\llvm-clang-x86_64-sie-win\llvm-project\lld\wasm\Writer.cpp(263): error C2780: '_FwdIt2 std::copy(_ExPo &&,_FwdIt1,_FwdIt1,_FwdIt2) noexcept': expects 4 arguments - 3 provided
C:\Program Files (x86)\Microsoft Visual Studio\2019\BuildTools\VC\Tools\MSVC\14.29.30133\include\xutility(4463): note: see declaration of 'std::copy'
C:\buildbot-root\llvm-clang-x86_64-sie-win\llvm-project\lld\wasm\Writer.cpp(263): error C2782: '_OutIt std::copy(_InIt,_InIt,_OutIt)': template parameter '_InIt' is ambiguous
C:\Program Files (x86)\Microsoft Visual Studio\2019\BuildTools\VC\Tools\MSVC\14.29.30133\include\xutility(4452): note: see declaration of 'std::copy'
C:\buildbot-root\llvm-clang-x86_64-sie-win\llvm-project\lld\wasm\Writer.cpp(263): note: could be '_Ty *'
        with
        [
            _Ty=uint8_t
        ]
C:\buildbot-root\llvm-clang-x86_64-sie-win\llvm-project\lld\wasm\Writer.cpp(263): note: or       'std::_Array_iterator<_Ty,20>'
        with
        [
            _Ty=uint8_t
        ]
C:\buildbot-root\llvm-clang-x86_64-sie-win\llvm-project\lld\wasm\Writer.cpp(263): error C2784: '_OutIt std::copy(_InIt,_InIt,_OutIt)': could not deduce template argument for '_InIt' from '_Ty *'
        with
        [
            _Ty=uint8_t
        ]
C:\Program Files (x86)\Microsoft Visual Studio\2019\BuildTools\VC\Tools\MSVC\14.29.30133\include\xutility(4452): note: see declaration of 'std::copy'

The failure was masked by an earlier failure which meant the buildbot never got to your code and so the failure didn't show up until the original problem was fixed.

Note this also seems to be the same failure the pre-merge checks hit. Can you take a look and revert if you need time to investigate?

[dschuff]

Sorry about that, will fix.
And I guess I'll have to get into the habit of the pre-merge checks being useful!

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::vector<uint8_t> 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(), &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)));
 }