[lld-macho] Implement LC_UUID

[int3]

Summary

Apple devtools use this to locate the dSYM files for a given
binary.

The UUID is computed based on an MD5 hash of the binary's contents. In order to
hash the contents, we must first write them, but LC_UUID itself must be part of
the written contents in order for all the offsets to be calculated correctly.
We resolve this circular paradox by first writing an LC_UUID with an all-zero
UUID, then updating the UUID with its real value later.

I'm not sure there's a good way to test that the value of the UUID is
"as expected", so I've just checked that it's present.

[ayrivera]

Hi,

Sorry to post this around a week late. I've been noticing that the same lit test that failed here (windows > lld.ELF/invalid::symtab-sh-info.s) is failing in my local build. I tried to debug it and noticed that a dense map is being deallocated, but it is a nullpointer. Is this a known issue? I apologies if I'm asking in the wrong place. Thanks for your time.

[int3]

The failing test is unrelated to the changes made in this diff (also this diff hasn't been landed yet)

[ayrivera]

In D89418#2352429, @int3 wrote:

The failing test is unrelated to the changes made in this diff (also this diff hasn't been landed yet)

Hi,

Yes, I understand that the failure isn't related to your changes. I've seen the same failure in other changes. I'm just asking if this failure has been discussed. Would it be best mailing to llvm-dev? Sorry for the naïve question. Thanks for your time and help.

[int3]

Yeah I think llvm-dev would probably be a better place to find answers

[smeenai]

In D89418#2348751, @ayrivera wrote:

Hi,

Sorry to post this around a week late. I've been noticing that the same lit test that failed here (windows > lld.ELF/invalid::symtab-sh-info.s) is failing in my local build. I tried to debug it and noticed that a dense map is being deallocated, but it is a nullpointer. Is this a known issue? I apologies if I'm asking in the wrong place. Thanks for your time.

D88348 looks like it has the fix for this.

[ayrivera]

In D89418#2355262, @smeenai wrote:

In D89418#2348751, @ayrivera wrote:

Hi,

Sorry to post this around a week late. I've been noticing that the same lit test that failed here (windows > lld.ELF/invalid::symtab-sh-info.s) is failing in my local build. I tried to debug it and noticed that a dense map is being deallocated, but it is a nullpointer. Is this a known issue? I apologies if I'm asking in the wrong place. Thanks for your time.

D88348 looks like it has the fix for this.

Thank you!

[smeenai]

LGTM

[thakis]

Any reason this uses md5? In the COFF and ELF ports, we found that using md5 as debug info uuid is a bottleneck, but xxhash is fine. https://reviews.llvm.org/D51956 has some discussion on this, and the history for --build-id in lld/ELF probably finds the same discussion for ELF.

[int3]

I used MD5 since that's what ld64 does. I hadn't looked at what lld-ELF/COFF were doing for this though, so thanks for the pointer! The only possible concern I can think of is the fact that the UUID version tags as specified in its RFC only provide for MD5 or SHA1 hashing, and ld64 seemed to think it important that we conform to this RFC. But I'm hard pressed to see how it would be an issue if we used a different hashing algorithm but tagged it as MD5. I'm inclined to just leave a TODO for now and come back later when we are tuning for performance

lld/MachO/Writer.cpp

 #include "Target.h"
 #include "UnwindInfoSection.h"
 
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
 #include "llvm/BinaryFormat/MachO.h"
 #include "llvm/Config/llvm-config.h"
 #include "llvm/Support/LEB128.h"
+#include "llvm/Support/MD5.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/Path.h"
 
 #include <algorithm>
 
 using namespace llvm;
 using namespace llvm::MachO;
 using namespace lld;
 using namespace lld::macho;
 
 namespace {
-class LCLinkEdit;
-class LCDyldInfo;
-class LCSymtab;
+class LCUuid;
 
 class Writer {
 public:
   Writer() : buffer(errorHandler().outputBuffer) {}
 
   void scanRelocations();
   void createOutputSections();
   void createLoadCommands();
   void assignAddresses(OutputSegment *);
   void createSymtabContents();
 
   void openFile();
   void writeSections();
+  void writeUuid();
 
   void run();
 
   std::unique_ptr<FileOutputBuffer> &buffer;
   uint64_t addr = 0;
   uint64_t fileOff = 0;
   MachHeaderSection *header = nullptr;
   StringTableSection *stringTableSection = nullptr;
   SymtabSection *symtabSection = nullptr;
   IndirectSymtabSection *indirectSymtabSection = nullptr;
   UnwindInfoSection *unwindInfoSection = nullptr;
+  LCUuid *uuidCommand = nullptr;
 };
 
 // LC_DYLD_INFO_ONLY stores the offsets of symbol import/export information.
 class LCDyldInfo : public LoadCommand {
 public:
   LCDyldInfo(RebaseSection *rebaseSection, BindingSection *bindingSection,
              WeakBindingSection *weakBindingSection,
              LazyBindingSection *lazyBindingSection,
void writeTo(uint8_t *buf) const override {
     t->tool = TOOL_LD;
     t->version = (LLVM_VERSION_MAJOR << 020) | (LLVM_VERSION_MINOR << 010) |
                  LLVM_VERSION_PATCH;
   }
 
   const PlatformInfo &platform;
 };
 
+// Stores a unique identifier for the output file based on an MD5 hash of its
+// contents. In order to hash the contents, we must first write them, but
+// LC_UUID itself must be part of the written contents in order for all the
+// offsets to be calculated correctly. We resolve this circular paradox by
+// first writing an LC_UUID with an all-zero UUID, then updating the UUID with
+// its real value later.
+class LCUuid : public LoadCommand {
+public:
+  uint32_t getSize() const override { return sizeof(uuid_command); }
+
+  void writeTo(uint8_t *buf) const override {
+    auto *c = reinterpret_cast<uuid_command *>(buf);
+    c->cmd = LC_UUID;
+    c->cmdsize = getSize();
+    uuidBuf = c->uuid;
+  }
+
+  void writeUuid(const std::array<uint8_t, 16> &uuid) const {
+    memcpy(uuidBuf, uuid.data(), uuid.size());
+  }
+
+  mutable uint8_t *uuidBuf;
+};
+
 } // namespace
 
 void Writer::scanRelocations() {
   for (InputSection *isec : inputSections) {
     // We do not wish to add rebase opcodes for __LD,__compact_unwind, because
     // it doesn't actually end up in the final binary. TODO: filtering it out
     // before Writer runs might be cleaner...
     if (isec->segname == segment_names::ld)
void Writer::createLoadCommands() {
   case MH_BUNDLE:
     break;
   default:
     llvm_unreachable("unhandled output file type");
   }
 
   in.header->addLoadCommand(make<LCBuildVersion>(config->platform));
 
+  uuidCommand = make<LCUuid>();
+  in.header->addLoadCommand(uuidCommand);
+
   uint8_t segIndex = 0;
   for (OutputSegment *seg : outputSegments) {
     in.header->addLoadCommand(make<LCSegment>(seg->name, seg));
     seg->index = segIndex++;
   }
 
   uint64_t dylibOrdinal = 1;
   for (InputFile *file : inputFiles) {

 
 void Writer::writeSections() {
   uint8_t *buf = buffer->getBufferStart();
   for (OutputSegment *seg : outputSegments)
     for (OutputSection *osec : seg->getSections())
       osec->writeTo(buf + osec->fileOff);
 }
 
+void Writer::writeUuid() {
+  MD5 hash;
+  const auto *bufStart = reinterpret_cast<char *>(buffer->getBufferStart());
+  const auto *bufEnd = reinterpret_cast<char *>(buffer->getBufferEnd());
+  hash.update(StringRef(bufStart, bufEnd - bufStart));
+  MD5::MD5Result result;
+  hash.final(result);
+  // Conform to UUID version 4 & 5 as specified in RFC 4122:
+  // 1. Set the version field to indicate that this is an MD5-based UUID.
+  result.Bytes[6] = (result.Bytes[6] & 0xf) | 0x30;
+  // 2. Set the two MSBs of uuid_t::clock_seq_hi_and_reserved to zero and one.
+  result.Bytes[8] = (result.Bytes[8] & 0x3f) | 0x80;
+  uuidCommand->writeUuid(result.Bytes);
+}
+
 void Writer::run() {
   // dyld requires __LINKEDIT segment to always exist (even if empty).
   OutputSegment *linkEditSegment =
       getOrCreateOutputSegment(segment_names::linkEdit);
 
   prepareBranchTarget(config->entry);
   scanRelocations();
   if (in.stubHelper->isNeeded())
void Writer::run() {
   // addresses and offsets.
   assignAddresses(linkEditSegment);
 
   openFile();
   if (errorCount())
     return;
 
   writeSections();
+  writeUuid();
 
   if (auto e = buffer->commit())
     error("failed to write to the output file: " + toString(std::move(e)));
 }
 
 void macho::writeResult() { Writer().run(); }
 
 void macho::createSyntheticSections() {

lld/test/MachO/headerpad.s

 # REQUIRES: x86
 
 ## NOTE: Here we check that the first non-header section -- __text -- appears
 ## *exactly* `-headerpad` bytes from the end of the header. ld64 actually
 ## starts laying out the non-header sections in the __TEXT segment from the end
 ## of the (page-aligned) segment rather than the front, so its binaries
 ## typically have more than `-headerpad` bytes of actual padding. `-headerpad`
 ## just enforces a lower bound. We should consider implementing the same
 ## alignment behavior.
 
 ################ Check default behavior
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t.o
 # RUN: %lld -o %t %t.o
 # RUN: llvm-objdump --macho --all-headers %t | FileCheck %s --check-prefix=PADx
 #
-# PADx:      magic        {{.+}}  ncmds sizeofcmds        flags
-# PADx-NEXT: MH_MAGIC_64  {{.+}}  9     [[#%u, CMDSIZE:]] {{.*}}
+# PADx:      magic        {{.+}}  ncmds  sizeofcmds         flags
+# PADx-NEXT: MH_MAGIC_64  {{.+}}  [[#]]  [[#%u, CMDSIZE:]]  {{.*}}
 # PADx:      sectname __text
 # PADx-NEXT: segname __TEXT
 # PADx-NEXT: addr
 # PADx-NEXT: size
 # PADx-NEXT: offset [[#%u, CMDSIZE + 0x20 + 0x20]]
 
 ################ Zero pad, no LCDylibs
 # RUN: %lld -o %t %t.o -headerpad 0
 # RUN: llvm-objdump --macho --all-headers %t | FileCheck %s --check-prefix=PAD0
 # RUN: %lld -o %t %t.o -headerpad 0 -headerpad_max_install_names
 # RUN: llvm-objdump --macho --all-headers %t | FileCheck %s --check-prefix=PAD0
 #
-# PAD0:      magic        {{.+}}  ncmds sizeofcmds        flags
-# PAD0-NEXT: MH_MAGIC_64  {{.+}}  9     [[#%u, CMDSIZE:]] {{.*}}
+# PAD0:      magic        {{.+}}  ncmds  sizeofcmds         flags
+# PAD0-NEXT: MH_MAGIC_64  {{.+}}  [[#]]  [[#%u, CMDSIZE:]]  {{.*}}
 # PAD0:      sectname __text
 # PAD0-NEXT: segname __TEXT
 # PAD0-NEXT: addr
 # PAD0-NEXT: size
 # PAD0-NEXT: offset [[#%u, CMDSIZE + 0x20 + 0]]
 
 ################ Each lexical form of a hex number, no LCDylibs
 # RUN: %lld -o %t %t.o -headerpad 11
 # RUN: llvm-objdump --macho --all-headers %t | FileCheck %s --check-prefix=PAD11
 # RUN: %lld -o %t %t.o -headerpad 0x11
 # RUN: llvm-objdump --macho --all-headers %t | FileCheck %s --check-prefix=PAD11
 # RUN: %lld -o %t %t.o -headerpad 0X11 -headerpad_max_install_names
 # RUN: llvm-objdump --macho --all-headers %t | FileCheck %s --check-prefix=PAD11
 #
-# PAD11:      magic        {{.+}}  ncmds sizeofcmds        flags
-# PAD11-NEXT: MH_MAGIC_64  {{.+}}  9     [[#%u, CMDSIZE:]] {{.*}}
+# PAD11:      magic        {{.+}}  ncmds  sizeofcmds         flags
+# PAD11-NEXT: MH_MAGIC_64  {{.+}}  [[#]]  [[#%u, CMDSIZE:]]  {{.*}}
 # PAD11:      sectname __text
 # PAD11-NEXT: segname __TEXT
 # PAD11-NEXT: addr
 # PAD11-NEXT: size
 # PAD11-NEXT: offset [[#%u, CMDSIZE + 0x20 + 0x11]]
 
 ################ Each & all 3 kinds of LCDylib
 # RUN: echo "" | llvm-mc -filetype=obj -triple=x86_64-apple-darwin -o %T/null.o

 # RUN: llvm-objdump --macho --all-headers %T/libnull.dylib | FileCheck %s --check-prefix=PADMAX
 #
 # PADMAX:      magic        {{.+}}  ncmds        sizeofcmds         flags
 # PADMAX-NEXT: MH_MAGIC_64  {{.+}}  [[#%u, N:]]  [[#%u, CMDSIZE:]]  {{.*}}
 # PADMAX:      sectname __text
 # PADMAX-NEXT: segname __TEXT
 # PADMAX-NEXT: addr
 # PADMAX-NEXT: size
-# PADMAX-NEXT: offset [[#%u, CMDSIZE + 0x20 + mul(0x400, N - 6)]]
+# PADMAX-NEXT: offset [[#%u, CMDSIZE + 0x20 + mul(0x400, N - 7)]]
 
 ################ All 3 kinds of LCDylib swamped by a larger override
 # RUN: %lld -o %T/libnull.dylib %T/null.o -dylib \
 # RUN:     -headerpad_max_install_names -headerpad 0x1001 \
 # RUN:     -lSystem -sub_library libSystem
 # RUN: llvm-objdump --macho --all-headers %T/libnull.dylib | FileCheck %s --check-prefix=PADOVR
 #
 # PADOVR:      magic        {{.+}}  ncmds        sizeofcmds         flags

lld/test/MachO/load-commands.s

 # REQUIRES: x86
 # RUN: rm -rf %t && mkdir -p %t
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t/test.o
 # RUN: %lld -o %t/executable %t/test.o
 # RUN: %lld -bundle -o %t/bundle %t/test.o
 # RUN: %lld -dylib -o %t/dylib %t/test.o
 
 ## These load commands should be in every final output binary.
 # COMMON-DAG: cmd LC_DYLD_INFO_ONLY
 # COMMON-DAG: cmd LC_SYMTAB
 # COMMON-DAG: cmd LC_DYSYMTAB
+# COMMON-DAG: cmd LC_UUID
 
 ## Check for the presence of load commands that are essential for a working
 ## executable. Also check that it has the right filetype.
 # RUN: llvm-objdump --macho --all-headers %t/executable | FileCheck %s --check-prefix=COMMON
 # RUN: llvm-objdump --macho --all-headers %t/executable | FileCheck %s --check-prefix=EXEC
 # EXEC:      magic        cputype cpusubtype  caps    filetype
 # EXEC-NEXT: MH_MAGIC_64  X86_64         ALL  {{.*}}  EXECUTE
 # EXEC-DAG:  cmd LC_MAIN

lld/test/MachO/local-got.s

 # REQUIRES: x86
 # RUN: mkdir -p %t
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %p/Inputs/libhello.s \
 # RUN:   -o %t/libhello.o
 # RUN: %lld -lSystem -dylib -install_name \
 # RUN:   @executable_path/libhello.dylib %t/libhello.o -o %t/libhello.dylib
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t/test.o
 # RUN: %lld -lSystem -o %t/test %t/test.o -L%t -lhello
 # RUN: llvm-objdump --full-contents --rebase --bind %t/test | FileCheck %s --match-full-lines
 
 ## Check that the GOT references the cstrings. --full-contents displays the
 ## address offset and the contents at that address very similarly, so am using
 ## --match-full-lines to make sure we match on the right thing.
 # CHECK:      Contents of section __TEXT,__cstring:
-# CHECK-NEXT: 10000040c {{.*}}
+# CHECK-NEXT: 100000424 {{.*}}
 
 ## 1st 8 bytes refer to the start of __cstring + 0xe, 2nd 8 bytes refer to the
 ## start of __cstring
 # CHECK:      Contents of section __DATA_CONST,__got:
-# CHECK-NEXT: [[#%X,ADDR:]]  1a040000 01000000 0c040000 01000000 {{.*}}
+# CHECK-NEXT: [[#%X,ADDR:]]  32040000 01000000 24040000 01000000 {{.*}}
 # CHECK-NEXT: [[#ADDR + 16]] 00000000 00000000 {{.*}}
 
 ## Check that the rebase table is empty.
 # CHECK:      Rebase table:
 # CHECK-NEXT: segment      section  address         type
 
 ## Check that a non-locally-defined symbol is still bound at the correct offset:
 # CHECK-NEXT: Bind table:

lld/test/MachO/relocations.s

 # CHECK:       leaq [[#%u, STR_OFF:]](%rip), %rsi
 # CHECK-NEXT:  [[#%x, CSTRING_ADDR - STR_OFF]]
 ## Test non-extern (section) X86_64_RELOC_SIGNED
 # CHECK:       leaq [[#%u, LSTR_OFF:]](%rip), %rsi
 # CHECK-NEXT:  [[#%x, CSTRING_ADDR + 22 - LSTR_OFF]]
 
 # RUN: llvm-objdump --section=__const --full-contents %t | FileCheck %s --check-prefix=NONPCREL
 # NONPCREL:      Contents of section __DATA,__const:
-# NONPCREL-NEXT: 100001000 f0030000 01000000 f0030000 01000000
+# NONPCREL-NEXT: 100001000 08040000 01000000 08040000 01000000
 
 .section __TEXT,__text
 .globl _main, _f
 _main:
   callq _f # X86_64_RELOC_BRANCH
   mov $0, %rax
   ret