[lld-macho] Support calls to functions in dylibs

[int3]

Summary

This diff implements lazy symbol binding -- very similar to the PLT
mechanism in ELF.

ELF's .plt section is broken up into two sections in Mach-O:
StubsSection and StubHelperSection. Calls to functions in dylibs will
end up calling into StubsSection, which contains indirect jumps to
addresses stored in the LazyPointerSection (the counterpart to ELF's
.plt.got).

Initially, the LazyPointerSection contains addresses that point into one
of the entry points in the middle of the StubHelperSection. The code in
StubHelperSection will push on the stack an offset into the
LazyBindingSection. The push is followed by a jump to the beginning of
the StubHelperSection (similar to PLT0), which then calls into
dyld_stub_binder. dyld_stub_binder is a non-lazily bound symbol, so this
call looks it up in the GOT.

The stub binder will look up the bind opcodes in the LazyBindingSection
at the given offset. The bind opcodes will tell the binder to update the
address in the LazyPointerSection to point to the symbol, so that
subsequent calls don't have to redo the symbol resolution. The binder
will then jump to the resolved symbol.

Depends on D78269.

[int3]

tweak

[int3]

rebase

[int3]

update

[int3]

rebase

[MaskRay]

lld/MachO/InputSection.cpp

11–12

Why is #include "SyntheticSections.h" dropped?

lld/test/MachO/dylink-lazy.s

21

--disassemble-all can be shorten as -D. --no-show-raw-insn may not be needed for -D

42

Consider increasing indentation (i.e. add one space) for instructions covered by the section Disassembly of section __TEXT,__stub_helper:

[int3]

address comments

lld/MachO/InputSection.cpp

11–12

It was originally included so we could access in.got. But now we're just using target->getDylibSymbolVA() from Target.h.

lld/test/MachO/dylink-lazy.s

21

Will change. Though it looks like --no-show-raw-insn is still needed

42

Looking at a smattering of lld-ELF's tests, I found files that used zero, two, four, and eight spaces :|

An odd number of spaces feels a bit, uh, odd :P I think I'll go with two

[smeenai]

lld/MachO/Arch/X86_64.cpp

74

I'd add a comment that the + 1 is because RIP on x86-64 reflects the next instruction instead of the current instruction.

Or perhaps that can be a more general comment above this section, since it's relevant for the other stubs as well.

106

Nit: can type be a RelocationInfoType instead of a uint8_t?

113

Are there any other sorts of relocations we would conceivably need to handle for this in the future? If not, this should be an llvm_unreachable

From playing around with this a bit, clang generates an X86_64_RELOC_GOT for dylib function calls when you compile with -fno-plt, so perhaps that's at least one other case we need to care about (eventually).

lld/MachO/Driver.cpp

161

Perhaps add a TODO to replace this with a stub tbd file when we have TAPI support?

lld/MachO/InputFiles.h

68

Why can't we just use the other constructor with your dummy MemoryBufferRef?

lld/MachO/SyntheticSections.cpp

265

What's the purpose of this return, given we're gonna error anyway?

lld/MachO/SyntheticSections.h

102

The comment is great!

151

Huh, interesting.

CC @Ktwu

lld/test/MachO/dylink-lazy.s

49

How come we aren't checking the value here?

[int3]

factor out more target-specific code

[int3]

lld/MachO/Arch/X86_64.cpp

113

I'm not sure if there are others, but I guess I can make this an assert for now and relax it if/when we discover more

lld/MachO/InputFiles.h

68

The DylibFile constructor attempts to read from the MemoryBufferRef and throws errors when it doesn't find what it expects

lld/MachO/SyntheticSections.cpp

265

error doesn't cause the program to exit, for that we need fatal. But I guess this should really be a fatal.

lld/MachO/SyntheticSections.h

102

Thanks! It took me quite a while to figure out how everything fit together, so it was fun to explain it :)

lld/test/MachO/dylink-lazy.s

49

I guess you mean on line 48? That's the offset into the bind opcode stream, and there's no nice arithmetic to describe it. Hard-coding the value will be brittle -- it will vary based on which entries appear earlier in the stream, and how large they are (which includes the length of their symbol names). There's the counterargument that these things aren't likely to change that often in our tests of course...

[alexander-shaposhnikov]

lld/MachO/Arch/X86_64.cpp

92

i'm wondering if we can replace these numbers (7, 11, 15, ... ) either with some expression (like sizeof(..) etc) or named constants or add comments

[smeenai]

lld/MachO/SyntheticSections.cpp

265

I know that error doesn't cause the program to exit right away, but it will eventually cause the program to exit with an error. Given that, I was wondering if not having the return here and instead falling through to the os << below would cause any harm.

lld/test/MachO/dylink-lazy.s

49

Yeah, we should strike a balance between testing everything and having brittle tests, but in this scenario, assuming we don't modify the test itself, I'd say it's worth checking the actual offset. I'd even consider checking the bind opcode bytes we're emitting (assuming those aren't likely to change from future linker changes, only from future changes to this test itself), to ensure we don't accidentally regress those in the future.

[int3]

address comments

lld/MachO/Arch/X86_64.cpp

92

lld-ELF uses a bunch of literal constants too, but I agree it's not ideal. I've added offsets to the comments and added a helper function, hope it's more readable now :)

106

The input parameters would need to be static_cast. Alternatively we could change the definition of relocation_info::type to be a RelocationInfoType, and declare the enum as enum RelocationInfoType : uint8_t, but that currently runs into compile-time errors in the for the lld-macho backend due to an ambiguous type conversion (since what was formerly a strict enum is now maybe also a uint8_t). Seems like too much work to sort it out right now

lld/MachO/SyntheticSections.cpp

265

Chatted offline, and we agreed that fatal is fine for things that we haven't implemented yet. It's not a user error, so error() -- which allows for more than one error diagnostic to be emitted -- isn't really useful as the user can't do much to address the problem. And the code is not unreachable with valid inputs, so llvm_unreachable isn't quite right either.

lld/test/MachO/dylink-lazy.s

49

Fair enough. Re the bind opcodes, they're being indirectly tested via the "Bind table" and "Lazy bind table" checks above, so I think we've got that covered

[int3]

update

[int3]

fatal

[int3]

rebase

[int3]

rebase

[smeenai]

LGTM

lld/MachO/Arch/X86_64.cpp

 //===- X86_64.cpp ---------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
+#include "Symbols.h"
+#include "SyntheticSections.h"
 #include "Target.h"
+
 #include "lld/Common/ErrorHandler.h"
 #include "llvm/BinaryFormat/MachO.h"
 #include "llvm/Support/Endian.h"
 
 using namespace llvm::MachO;
 using namespace llvm::support::endian;
 using namespace lld;
 using namespace lld::macho;
 
 namespace {
 
 struct X86_64 : TargetInfo {
   X86_64();
+
   uint64_t getImplicitAddend(const uint8_t *loc, uint8_t type) const override;
   void relocateOne(uint8_t *loc, uint8_t type, uint64_t val) const override;
+
+  void writeStub(uint8_t *buf, const DylibSymbol &) const override;
+  void writeStubHelperHeader(uint8_t *buf) const override;
+  void writeStubHelperEntry(uint8_t *buf, const DylibSymbol &,
+                            uint64_t entryAddr) const override;
+
+  void prepareDylibSymbolRelocation(DylibSymbol &, uint8_t type) override;
+  uint64_t getDylibSymbolVA(const DylibSymbol &, uint8_t type) const override;
 };
 
-X86_64::X86_64() {
-  cpuType = CPU_TYPE_X86_64;
-  cpuSubtype = CPU_SUBTYPE_X86_64_ALL;
-}
+} // namespace
 
 uint64_t X86_64::getImplicitAddend(const uint8_t *loc, uint8_t type) const {
   switch (type) {
   case X86_64_RELOC_BRANCH:
   case X86_64_RELOC_SIGNED:
   case X86_64_RELOC_GOT_LOAD:
     return read32le(loc);
   default:
case X86_64_RELOC_GOT_LOAD:
     write32le(loc, val - 4);
     break;
   default:
     llvm_unreachable(
         "getImplicitAddend should have flagged all unhandled relocation types");
   }
 }
 
-} // namespace
+static constexpr uint8_t stub[] = {
+    0xff, 0x25, 0, 0, 0, 0, // jmpq *__la_symbol_ptr(%rip)
+};
+
+void X86_64::writeStub(uint8_t *buf, const DylibSymbol &sym) const {
+  memcpy(buf, stub, 2); // just copy the two nonzero bytes
+  uint64_t rip = in.stubs->addr + (sym.stubsIndex + 1) * sizeof(stub);
+  write32le(buf + 2, in.lazyPointers->addr + sym.stubsIndex * WordSize - rip);
+}
+
+static constexpr uint8_t stubHelperHeader[] = {
+    0x4c, 0x8d, 0x1d, 0, 0, 0, 0, // leaq ImageLoaderCache(%rip), %r11
+    0x41, 0x53,                   // pushq %r11
+    0xff, 0x25, 0,    0, 0, 0,    // jmpq *dyld_stub_binder@GOT(%rip)
+    0x90,                         // nop
+};
+
+static constexpr uint8_t stubHelperEntry[] = {
+    0x68, 0, 0, 0, 0, // pushq <bind offset>
+    0xe9, 0, 0, 0, 0, // jmp <__stub_helper>
+};
+
+void X86_64::writeStubHelperHeader(uint8_t *buf) const {
+  memcpy(buf, stubHelperHeader, sizeof(stubHelperHeader));
+  write32le(buf + 3, in.imageLoaderCache->addr - (in.stubHelper->addr + 7));
+  write32le(buf + 11, in.got->addr +
+                          in.stubHelper->stubBinder->gotIndex * WordSize -
+                          (in.stubHelper->addr + 15));
+}
+
+void X86_64::writeStubHelperEntry(uint8_t *buf, const DylibSymbol &sym,
+                                  uint64_t entryAddr) const {
+  memcpy(buf, stubHelperEntry, sizeof(stubHelperEntry));
+  write32le(buf + 1, sym.lazyBindOffset);
+  uint64_t rip = entryAddr + sizeof(stubHelperEntry);
+  write32le(buf + 6, in.stubHelper->addr - rip);
+}
+
+void X86_64::prepareDylibSymbolRelocation(DylibSymbol &sym, uint8_t type) {
+  switch (type) {
+  case X86_64_RELOC_GOT_LOAD:
+    in.got->addEntry(sym);
+    break;
+  case X86_64_RELOC_BRANCH:
+    in.stubs->addEntry(sym);
+    break;
+  default:
+    break;
+  }
+}
+
+uint64_t X86_64::getDylibSymbolVA(const DylibSymbol &sym, uint8_t type) const {
+  switch (type) {
+  case X86_64_RELOC_GOT_LOAD:
+    return in.got->addr + sym.gotIndex * WordSize;
+  case X86_64_RELOC_BRANCH:
+    return in.stubs->addr + sym.stubsIndex * sizeof(stub);
+  default:
+    error("TODO: Unhandled dylib relocation type " + std::to_string(type));
+    return 0;
+  }
+}
+
+X86_64::X86_64() {
+  cpuType = CPU_TYPE_X86_64;
+  cpuSubtype = CPU_SUBTYPE_X86_64_ALL;
+
+  stubSize = sizeof(stub);
+  stubHelperHeaderSize = sizeof(stubHelperHeader);
+  stubHelperEntrySize = sizeof(stubHelperEntry);
+}
 
 TargetInfo *macho::createX86_64TargetInfo() {
   static X86_64 t;
   return &t;
 }

lld/MachO/Driver.cpp

case OPT_INPUT:
       break;
     case OPT_l:
       if (Optional<std::string> path = findDylib(arg->getValue()))
         addFile(*path);
       break;
     }
   }
 
+  // dyld requires us to load libSystem. Since we may run tests on non-OSX
+  // systems which do not have libSystem, we mock it out here.
+  if (StringRef(getenv("LLD_IN_TEST")) == "1" &&
+      config->outputType == MH_EXECUTE) {
+    inputFiles.push_back(DylibFile::createLibSystemMock());
+  }
+
   if (config->outputType == MH_EXECUTE && !isa<Defined>(config->entry)) {
     error("undefined symbol: " + config->entry->getName());
     return false;
   }
 
   createSyntheticSections();
 
   // Initialize InputSections.

lld/MachO/InputFiles.h

 };
 
 // .dylib file
 class DylibFile : public InputFile {
 public:
   explicit DylibFile(MemoryBufferRef mb);
   static bool classof(const InputFile *f) { return f->kind() == DylibKind; }
 
+  // Do not use this constructor!! This is meant only for createLibSystemMock(),
+  // but it cannot be made private as we call it via make().
+  DylibFile();
+  static DylibFile *createLibSystemMock();
+
   StringRef dylibName;
   uint64_t ordinal = 0; // Ordinal numbering starts from 1, so 0 is a sentinel
 };
 
 extern std::vector<InputFile *> inputFiles;
 
 llvm::Optional<MemoryBufferRef> readFile(StringRef path);
 
 } // namespace macho
 
 std::string toString(const macho::InputFile *file);
 } // namespace lld
 
 #endif

lld/MachO/InputFiles.cpp

for (const nlist_64 &sym : nList) {
       // TODO: Figure out what to do about undefined symbols: ignore or warn
       // if unsatisfied? Also make sure we handle re-exported symbols
       // correctly.
       symbols.push_back(symtab->addDylib(name, this));
     }
   }
 }
 
+DylibFile::DylibFile() : InputFile(DylibKind, MemoryBufferRef()) {}
+
+DylibFile *DylibFile::createLibSystemMock() {
+  auto *file = make<DylibFile>();
+  file->mb = MemoryBufferRef("", "/usr/lib/libSystem.B.dylib");
+  file->dylibName = "/usr/lib/libSystem.B.dylib";
+  file->symbols.push_back(symtab->addDylib("dyld_stub_binder", file));
+  return file;
+}
+
 // Returns "<internal>" or "baz.o".
 std::string lld::toString(const InputFile *file) {
   return file ? std::string(file->getName()) : "<internal>";
 }

lld/MachO/InputSection.cpp

 //===- InputSection.cpp ---------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "InputSection.h"
 #include "OutputSegment.h"
 #include "Symbols.h"
-#include "SyntheticSections.h"
 #include "Target.h"
 #include "lld/Common/Memory.h"
 #include "llvm/Support/Endian.h"
 
 using namespace llvm::MachO;
 using namespace llvm::support;
 using namespace lld;
 using namespace lld::macho;
 
 std::vector<InputSection *> macho::inputSections;
 
 uint64_t InputSection::getFileOffset() const {
   return parent->fileOff + addr - parent->firstSection()->addr;
 }
 
 void InputSection::writeTo(uint8_t *buf) {
   if (!data.empty())
     memcpy(buf, data.data(), data.size());
 
   for (Reloc &r : relocs) {
     uint64_t va = 0;
     if (auto *s = r.target.dyn_cast<Symbol *>()) {
       if (auto *dylibSymbol = dyn_cast<DylibSymbol>(s)) {
-        va = in.got->addr + dylibSymbol->gotIndex * WordSize;
+        va = target->getDylibSymbolVA(*dylibSymbol, r.type);
       } else {
         va = s->getVA();
       }
     } else if (auto *isec = r.target.dyn_cast<InputSection *>()) {
       va = isec->addr;
     } else {
       llvm_unreachable("Unknown relocation target");
     }
 
     uint64_t val = va + r.addend;
     if (1) // TODO: handle non-pcrel relocations
       val -= addr + r.offset;
     target->relocateOne(buf + r.offset, r.type, val);
   }
 }

lld/MachO/OutputSegment.h

 #include "lld/Common/LLVM.h"
 #include "llvm/ADT/MapVector.h"
 
 namespace lld {
 namespace macho {
 
 namespace segment_names {
 
-constexpr const char *text = "__TEXT";
 constexpr const char *pageZero = "__PAGEZERO";
+constexpr const char *text = "__TEXT";
+constexpr const char *data = "__DATA";
 constexpr const char *linkEdit = "__LINKEDIT";
 
 } // namespace segment_names
 
 class InputSection;
 
 class OutputSegment {
 public:

lld/MachO/Symbols.h

 public:
   DylibSymbol(DylibFile *file, StringRefZ name)
       : Symbol(DylibKind, name), file(file) {}
 
   static bool classof(const Symbol *s) { return s->kind() == DylibKind; }
 
   DylibFile *file;
   uint32_t gotIndex = UINT32_MAX;
+  uint32_t stubsIndex = UINT32_MAX;
+  uint32_t lazyBindOffset = UINT32_MAX;
 };
 
 inline uint64_t Symbol::getVA() const {
   if (auto *d = dyn_cast<Defined>(this))
     return d->isec->addr + d->value;
   return 0;
 }
 

lld/MachO/SyntheticSections.h

 namespace lld {
 namespace macho {
 
 namespace section_names {
 
 constexpr const char *pageZero = "__pagezero";
 constexpr const char *header = "__mach_header";
 constexpr const char *binding = "__binding";
+constexpr const char *lazyBinding = "__lazy_binding";
 constexpr const char *export_ = "__export";
 constexpr const char *symbolTable = "__symbol_table";
 constexpr const char *stringTable = "__string_table";
 
 } // namespace section_names
 
 class DylibSymbol;
 class LoadCommand;

 };
 
 // This section will be populated by dyld with addresses to non-lazily-loaded
 // dylib symbols.
 class GotSection : public InputSection {
 public:
   GotSection();
 
-  void addEntry(DylibSymbol &sym);
   const llvm::SetVector<const DylibSymbol *> &getEntries() const {
     return entries;
   }
 
   size_t getSize() const override { return entries.size() * WordSize; }
 
   bool isNeeded() const override { return !entries.empty(); }
 
   void writeTo(uint8_t *buf) override {
     // Nothing to write, GOT contains all zeros at link time; it's populated at
     // runtime by dyld.
   }
 
+  void addEntry(DylibSymbol &sym);
+
 private:
   llvm::SetVector<const DylibSymbol *> entries;
 };
 
 // Stores bind opcodes for telling dyld which symbols to load non-lazily.
 class BindingSection : public InputSection {
 public:
   BindingSection();
   void finalizeContents();
   size_t getSize() const override { return contents.size(); }
   // Like other sections in __LINKEDIT, the binding section is special: its
   // offsets are recorded in the LC_DYLD_INFO_ONLY load command, instead of in
   // section headers.
   bool isHidden() const override { return true; }
   bool isNeeded() const override;
   void writeTo(uint8_t *buf) override;
 
   SmallVector<char, 128> contents;
 };
 
+// The following sections implement lazy symbol binding -- very similar to the
+// PLT mechanism in ELF.
+//
+// ELF's .plt section is broken up into two sections in Mach-O: StubsSection and
+// StubHelperSection. Calls to functions in dylibs will end up calling into
+// StubsSection, which contains indirect jumps to addresses stored in the
+// LazyPointerSection (the counterpart to ELF's .plt.got).
+//
+// Initially, the LazyPointerSection contains addresses that point into one of
+// the entry points in the middle of the StubHelperSection. The code in
+// StubHelperSection will push on the stack an offset into the
+// LazyBindingSection. The push is followed by a jump to the beginning of the
+// StubHelperSection (similar to PLT0), which then calls into dyld_stub_binder.
+// dyld_stub_binder is a non-lazily-bound symbol, so this call looks it up in
+// the GOT.
+//
+// The stub binder will look up the bind opcodes in the LazyBindingSection at
+// the given offset. The bind opcodes will tell the binder to update the address
+// in the LazyPointerSection to point to the symbol, so that subsequent calls
+// don't have to redo the symbol resolution. The binder will then jump to the
+// resolved symbol.
+
+class StubsSection : public InputSection {
+public:
+  StubsSection();
+  size_t getSize() const override;
+  bool isNeeded() const override { return !entries.empty(); }
+  void writeTo(uint8_t *buf) override;
+
+  const llvm::SetVector<DylibSymbol *> &getEntries() const { return entries; }
+
+  void addEntry(DylibSymbol &sym);
+
+private:
+  llvm::SetVector<DylibSymbol *> entries;
+};
+
+class StubHelperSection : public InputSection {
+public:
+  StubHelperSection();
+  size_t getSize() const override;
+  bool isNeeded() const override;
+  void writeTo(uint8_t *buf) override;
+
+  void setupSymbols();
+
+  DylibSymbol *stubBinder = nullptr;
+};
+
+// This section contains space for just a single word, and will be used by dyld
+// to cache an address to the image loader it uses. Note that unlike the other
+// synthetic sections, which should become OutputSections once we create that
+// abstraction, the ImageLoaderCacheSection should be an InputSection that
+// gets merged into the __data OutputSection.
+class ImageLoaderCacheSection : public InputSection {
+public:
+  ImageLoaderCacheSection();
+  size_t getSize() const override { return WordSize; }
+  bool isNeeded() const override;
+  // Nothing to write, this contains zeros at link time; it's populated at
+  // runtime by dyld.
+  void writeTo(uint8_t *buf) override {}
+};
+
+class LazyPointerSection : public InputSection {
+public:
+  LazyPointerSection();
+  size_t getSize() const override;
+  bool isNeeded() const override;
+  void writeTo(uint8_t *buf) override;
+};
+
+class LazyBindingSection : public InputSection {
+public:
+  LazyBindingSection();
+  void finalizeContents();
+  size_t getSize() const override { return contents.size(); }
+  uint32_t encode(const DylibSymbol &);
+  // Like other sections in __LINKEDIT, the lazy binding section is special: its
+  // offsets are recorded in the LC_DYLD_INFO_ONLY load command, instead of in
+  // section headers.
+  bool isHidden() const override { return true; }
+  bool isNeeded() const override;
+  void writeTo(uint8_t *buf) override;
+
+private:
+  SmallVector<char, 128> contents;
+  llvm::raw_svector_ostream os{contents};
+};
+
 // Stores a trie that describes the set of exported symbols.
 class ExportSection : public InputSection {
 public:
   ExportSection();
   void finalizeContents();
   size_t getSize() const override { return size; }
   // Like other sections in __LINKEDIT, the export section is special: its
   // offsets are recorded in the LC_DYLD_INFO_ONLY load command, instead of in

 
 private:
   StringTableSection &stringTableSection;
   std::vector<SymtabEntry> symbols;
 };
 
 struct InStruct {
   GotSection *got = nullptr;
+  LazyPointerSection *lazyPointers = nullptr;
+  StubsSection *stubs = nullptr;
+  StubHelperSection *stubHelper = nullptr;
+  ImageLoaderCacheSection *imageLoaderCache = nullptr;
 };
 
 extern InStruct in;
 
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/SyntheticSections.cpp

 
 #include "lld/Common/ErrorHandler.h"
 #include "llvm/Support/EndianStream.h"
 #include "llvm/Support/LEB128.h"
 
 using namespace llvm;
 using namespace llvm::MachO;
 using namespace llvm::support;
+using namespace llvm::support::endian;
 
 namespace lld {
 namespace macho {
 
 MachHeaderSection::MachHeaderSection() {
   // dyld3's MachOLoaded::getSlide() assumes that the __TEXT segment starts
   // from the beginning of the file (i.e. the header).
   segname = segment_names::text;
void MachHeaderSection::writeTo(uint8_t *buf) {
   auto *hdr = reinterpret_cast<mach_header_64 *>(buf);
   hdr->magic = MH_MAGIC_64;
   hdr->cputype = CPU_TYPE_X86_64;
   hdr->cpusubtype = CPU_SUBTYPE_X86_64_ALL | CPU_SUBTYPE_LIB64;
   hdr->filetype = config->outputType;
   hdr->ncmds = loadCommands.size();
   hdr->sizeofcmds = sizeOfCmds;
   hdr->flags = MH_NOUNDEFS | MH_DYLDLINK | MH_TWOLEVEL;
+  if (config->outputType == MH_DYLIB)
+    hdr->flags |= MH_NO_REEXPORTED_DYLIBS;
 
   uint8_t *p = reinterpret_cast<uint8_t *>(hdr + 1);
   for (LoadCommand *lc : loadCommands) {
     lc->writeTo(p);
     p += lc->getSize();
   }
 }
 
void BindingSection::finalizeContents() {
 
   os << static_cast<uint8_t>(BIND_OPCODE_DONE);
 }
 
 void BindingSection::writeTo(uint8_t *buf) {
   memcpy(buf, contents.data(), contents.size());
 }
 
+StubsSection::StubsSection() {
+  segname = segment_names::text;
+  name = "__stubs";
+}
+
+size_t StubsSection::getSize() const {
+  return entries.size() * target->stubSize;
+}
+
+void StubsSection::writeTo(uint8_t *buf) {
+  size_t off = 0;
+  for (const DylibSymbol *sym : in.stubs->getEntries()) {
+    target->writeStub(buf + off, *sym);
+    off += target->stubSize;
+  }
+}
+
+void StubsSection::addEntry(DylibSymbol &sym) {
+  if (entries.insert(&sym))
+    sym.stubsIndex = entries.size() - 1;
+}
+
+StubHelperSection::StubHelperSection() {
+  segname = segment_names::text;
+  name = "__stub_helper";
+}
+
+size_t StubHelperSection::getSize() const {
+  return target->stubHelperHeaderSize +
+         in.stubs->getEntries().size() * target->stubHelperEntrySize;
+}
+
+bool StubHelperSection::isNeeded() const {
+  return !in.stubs->getEntries().empty();
+}
+
+void StubHelperSection::writeTo(uint8_t *buf) {
+  target->writeStubHelperHeader(buf);
+  size_t off = target->stubHelperHeaderSize;
+  for (const DylibSymbol *sym : in.stubs->getEntries()) {
+    target->writeStubHelperEntry(buf + off, *sym, addr + off);
+    off += target->stubHelperEntrySize;
+  }
+}
+
+void StubHelperSection::setupSymbols() {
+  stubBinder = dyn_cast_or_null<DylibSymbol>(symtab->find("dyld_stub_binder"));
+  if (stubBinder == nullptr) {
+    error("symbol dyld_stub_binder not found (normally in libSystem.dylib). "
+          "Needed to perform lazy binding.");
+    return;
+  }
+  in.got->addEntry(*stubBinder);
+
+  symtab->addDefined("__dyld_private", in.imageLoaderCache, 0);
+}
+
+ImageLoaderCacheSection::ImageLoaderCacheSection() {
+  segname = segment_names::data;
+  name = "__data";
+}
+
+bool ImageLoaderCacheSection::isNeeded() const {
+  return !in.stubs->getEntries().empty();
+}
+
+LazyPointerSection::LazyPointerSection() {
+  segname = segment_names::data;
+  name = "__la_symbol_ptr";
+  align = 8;
+  flags = S_LAZY_SYMBOL_POINTERS;
+}
+
+size_t LazyPointerSection::getSize() const {
+  return in.stubs->getEntries().size() * WordSize;
+}
+
+bool LazyPointerSection::isNeeded() const {
+  return !in.stubs->getEntries().empty();
+}
+
+void LazyPointerSection::writeTo(uint8_t *buf) {
+  size_t off = 0;
+  for (const DylibSymbol *sym : in.stubs->getEntries()) {
+    uint64_t stubHelperOffset = target->stubHelperHeaderSize +
+                                sym->stubsIndex * target->stubHelperEntrySize;
+    write64le(buf + off, in.stubHelper->addr + stubHelperOffset);
+    off += WordSize;
+  }
+}
+
+LazyBindingSection::LazyBindingSection() {
+  segname = segment_names::linkEdit;
+  name = section_names::lazyBinding;
+}
+
+bool LazyBindingSection::isNeeded() const { return in.stubs->isNeeded(); }
+
+void LazyBindingSection::finalizeContents() {
+  // TODO: Just precompute output size here instead of writing to a temporary
+  // buffer
+  for (DylibSymbol *sym : in.stubs->getEntries())
+    sym->lazyBindOffset = encode(*sym);
+}
+
+void LazyBindingSection::writeTo(uint8_t *buf) {
+  memcpy(buf, contents.data(), contents.size());
+}
+
+// Unlike the non-lazy binding section, the bind opcodes in this section aren't
+// interpreted all at once. Rather, dyld will start interpreting opcodes at a
+// given offset, typically only binding a single symbol before it finds a
+// BIND_OPCODE_DONE terminator. As such, unlike in the non-lazy-binding case,
+// we cannot encode just the differences between symbols; we have to emit the
+// complete bind information for each symbol.
+uint32_t LazyBindingSection::encode(const DylibSymbol &sym) {
+  uint32_t opstreamOffset = contents.size();
+  OutputSegment *dataSeg = in.lazyPointers->parent;
+  os << static_cast<uint8_t>(BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB |
+                             dataSeg->index);
+  uint64_t offset = in.lazyPointers->addr - dataSeg->firstSection()->addr +
+                    sym.stubsIndex * WordSize;
+  encodeULEB128(offset, os);
+  if (sym.file->ordinal <= BIND_IMMEDIATE_MASK) {
+    os << static_cast<uint8_t>(BIND_OPCODE_SET_DYLIB_ORDINAL_IMM |
+                               sym.file->ordinal);
+  } else {
+    error("TODO: Support larger dylib symbol ordinals");
+    return opstreamOffset;
+  }
+  os << static_cast<uint8_t>(BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM)
+     << sym.getName() << '\0' << static_cast<uint8_t>(BIND_OPCODE_DO_BIND)
+     << static_cast<uint8_t>(BIND_OPCODE_DONE);
+  return opstreamOffset;
+}
+
 ExportSection::ExportSection() {
   segname = segment_names::linkEdit;
   name = section_names::export_;
 }
 
 void ExportSection::finalizeContents() {
   // TODO: We should check symbol visibility.
   for (const Symbol *sym : symtab->getSymbols())

lld/MachO/Target.h

 //===- Target.h -------------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_MACHO_TARGET_H
 #define LLD_MACHO_TARGET_H
 
+#include <cstddef>
 #include <cstdint>
 
 namespace lld {
 namespace macho {
 
+class DylibSymbol;
+
 enum {
   // We are currently only supporting 64-bit targets since macOS and iOS are
   // deprecating 32-bit apps.
   WordSize = 8,
   PageSize = 4096,
   ImageBase = 4096,
   MaxAlignmentPowerOf2 = 32,
 };
 
 class TargetInfo {
 public:
   virtual ~TargetInfo() = default;
   virtual uint64_t getImplicitAddend(const uint8_t *loc,
                                      uint8_t type) const = 0;
   virtual void relocateOne(uint8_t *loc, uint8_t type, uint64_t val) const = 0;
 
+  // Write code for lazy binding. See the comments on StubsSection for more
+  // details.
+  virtual void writeStub(uint8_t *buf, const DylibSymbol &) const = 0;
+  virtual void writeStubHelperHeader(uint8_t *buf) const = 0;
+  virtual void writeStubHelperEntry(uint8_t *buf, const DylibSymbol &,
+                                    uint64_t entryAddr) const = 0;
+
+  // Dylib symbols are referenced via either the GOT or the stubs section,
+  // depending on the relocation type. prepareDylibSymbolRelocation() will set
+  // up the GOT/stubs entries, and getDylibSymbolVA() will return the addresses
+  // of those entries.
+  virtual void prepareDylibSymbolRelocation(DylibSymbol &, uint8_t type) = 0;
+  virtual uint64_t getDylibSymbolVA(const DylibSymbol &,
+                                    uint8_t type) const = 0;
+
   uint32_t cpuType;
   uint32_t cpuSubtype;
+
+  size_t stubSize;
+  size_t stubHelperHeaderSize;
+  size_t stubHelperEntrySize;
 };
 
 TargetInfo *createX86_64TargetInfo();
 
 extern TargetInfo *target;
 
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/Writer.cpp

public:
 
   void run();
 
   std::unique_ptr<FileOutputBuffer> &buffer;
   uint64_t addr = 0;
   uint64_t fileOff = 0;
   MachHeaderSection *headerSection = nullptr;
   BindingSection *bindingSection = nullptr;
+  LazyBindingSection *lazyBindingSection = nullptr;
   ExportSection *exportSection = nullptr;
   StringTableSection *stringTableSection = nullptr;
   SymtabSection *symtabSection = nullptr;
 };
 
 // LC_DYLD_INFO_ONLY stores the offsets of symbol import/export information.
 class LCDyldInfo : public LoadCommand {
 public:
-  LCDyldInfo(BindingSection *bindingSection, ExportSection *exportSection)
-      : bindingSection(bindingSection), exportSection(exportSection) {}
+  LCDyldInfo(BindingSection *bindingSection,
+             LazyBindingSection *lazyBindingSection,
+             ExportSection *exportSection)
+      : bindingSection(bindingSection), lazyBindingSection(lazyBindingSection),
+        exportSection(exportSection) {}
 
   uint32_t getSize() const override { return sizeof(dyld_info_command); }
 
   void writeTo(uint8_t *buf) const override {
     auto *c = reinterpret_cast<dyld_info_command *>(buf);
     c->cmd = LC_DYLD_INFO_ONLY;
     c->cmdsize = getSize();
     if (bindingSection->isNeeded()) {
       c->bind_off = bindingSection->getFileOffset();
       c->bind_size = bindingSection->getFileSize();
     }
+    if (lazyBindingSection->isNeeded()) {
+      c->lazy_bind_off = lazyBindingSection->getFileOffset();
+      c->lazy_bind_size = lazyBindingSection->getFileSize();
+    }
     if (exportSection->isNeeded()) {
       c->export_off = exportSection->getFileOffset();
       c->export_size = exportSection->getFileSize();
     }
   }
 
   BindingSection *bindingSection;
+  LazyBindingSection *lazyBindingSection;
   ExportSection *exportSection;
 };
 
 class LCDysymtab : public LoadCommand {
 public:
   uint32_t getSize() const override { return sizeof(dysymtab_command); }
 
   void writeTo(uint8_t *buf) const override {
SectionType *createInputSection(ArgT &&... args) {
   return section;
 }
 
 void Writer::scanRelocations() {
   for (InputSection *sect : inputSections)
     for (Reloc &r : sect->relocs)
       if (auto *s = r.target.dyn_cast<Symbol *>())
         if (auto *dylibSymbol = dyn_cast<DylibSymbol>(s))
-          in.got->addEntry(*dylibSymbol);
+          target->prepareDylibSymbolRelocation(*dylibSymbol, r.type);
 }
 
 void Writer::createLoadCommands() {
   headerSection->addLoadCommand(
-      make<LCDyldInfo>(bindingSection, exportSection));
+      make<LCDyldInfo>(bindingSection, lazyBindingSection, exportSection));
   headerSection->addLoadCommand(
       make<LCSymtab>(symtabSection, stringTableSection));
   headerSection->addLoadCommand(make<LCDysymtab>());
 
   switch (config->outputType) {
   case MH_EXECUTE:
     headerSection->addLoadCommand(make<LCMain>());
     headerSection->addLoadCommand(make<LCLoadDylinker>());
void Writer::createLoadCommands() {
 
   uint64_t dylibOrdinal = 1;
   for (InputFile *file : inputFiles) {
     if (auto *dylibFile = dyn_cast<DylibFile>(file)) {
       headerSection->addLoadCommand(make<LCLoadDylib>(dylibFile->dylibName));
       dylibFile->ordinal = dylibOrdinal++;
     }
   }
-
-  // TODO: dyld requires libSystem to be loaded. libSystem is a universal
-  // binary and we don't have support for that yet, so mock it out here.
-  headerSection->addLoadCommand(
-      make<LCLoadDylib>("/usr/lib/libSystem.B.dylib"));
 }
 
 void Writer::createHiddenSections() {
   headerSection = createInputSection<MachHeaderSection>();
   bindingSection = createInputSection<BindingSection>();
+  lazyBindingSection = createInputSection<LazyBindingSection>();
   stringTableSection = createInputSection<StringTableSection>();
   symtabSection = createInputSection<SymtabSection>(*stringTableSection);
   exportSection = createInputSection<ExportSection>();
 
   switch (config->outputType) {
   case MH_EXECUTE:
     createInputSection<PageZeroSection>();
     break;
for (auto &sect : seg->getSections()) {
         fileOff += isec->getFileSize();
       }
     }
   }
 }
 
 void Writer::run() {
   scanRelocations();
+  if (in.stubHelper->isNeeded())
+    in.stubHelper->setupSymbols();
+
   createHiddenSections();
   // Sort and assign sections to their respective segments. No more sections can
   // be created after this method runs.
   sortSections();
   // dyld requires __LINKEDIT segment to always exist (even if empty).
   getOrCreateOutputSegment(segment_names::linkEdit);
   // No more segments can be created after this method runs.
   createLoadCommands();
 
   // Ensure that segments (and the sections they contain) are allocated
   // addresses in ascending order, which dyld requires.
   //
   // Note that at this point, __LINKEDIT sections are empty, but we need to
   // determine addresses of other segments/sections before generating its
   // contents.
   for (OutputSegment *seg : outputSegments)
     assignAddresses(seg);
 
   // Fill __LINKEDIT contents.
   bindingSection->finalizeContents();
+  lazyBindingSection->finalizeContents();
   exportSection->finalizeContents();
   symtabSection->finalizeContents();
 
   // Now that __LINKEDIT is filled out, do a proper calculation of its
   // addresses and offsets. We don't have to recalculate the other segments
   // since sortSections() ensures that __LINKEDIT is the last segment.
   assignAddresses(getOutputSegment(segment_names::linkEdit));
 
   openFile();
   if (errorCount())
     return;
 
   writeSections();
 
   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() {
   in.got = createInputSection<GotSection>();
+  in.lazyPointers = createInputSection<LazyPointerSection>();
+  in.stubs = createInputSection<StubsSection>();
+  in.stubHelper = createInputSection<StubHelperSection>();
+  in.imageLoaderCache = createInputSection<ImageLoaderCacheSection>();
 }

lld/test/MachO/Inputs/libgoodbye.s

 .section __TEXT,__cstring
-.globl _goodbye_world
+.globl _goodbye_world, _print_goodbye
 
 _goodbye_world:
 .asciz "Goodbye world!\n"
+
+.text
+_print_goodbye:
+  movl $0x2000004, %eax # write() syscall
+  mov $1, %rdi # stdout
+  leaq _goodbye_world(%rip), %rsi
+  mov $15, %rdx # length of str
+  syscall
+  ret

lld/test/MachO/Inputs/libhello.s

 .section __TEXT,__cstring
-.globl _hello_world, _hello_its_me
+.globl _hello_world, _hello_its_me, _print_hello
 
 _hello_world:
 .asciz "Hello world!\n"
 
 _hello_its_me:
 .asciz "Hello, it's me\n"
+
+.text
+_print_hello:
+  movl $0x2000004, %eax # write() syscall
+  mov $1, %rdi # stdout
+  leaq _hello_world(%rip), %rsi
+  mov $13, %rdx # length of str
+  syscall
+  ret

lld/test/MachO/dylink-lazy.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: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %p/Inputs/libgoodbye.s \
+# RUN:   -o %t/libgoodbye.o
+# RUN: lld -flavor darwinnew -dylib -install_name \
+# RUN:   @executable_path/libhello.dylib %t/libhello.o -o %t/libhello.dylib
+# RUN: lld -flavor darwinnew -dylib -install_name \
+# RUN:   @executable_path/libgoodbye.dylib %t/libgoodbye.o -o %t/libgoodbye.dylib
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t/dylink-lazy.o
+# RUN: lld -flavor darwinnew -o %t/dylink-lazy -L%t -lhello -lgoodbye %t/dylink-lazy.o
+
+## When looking at the __stubs section alone, we are unable to easily tell which
+## symbol each entry points to. So we call objdump twice in order to get the
+## disassembly of __text and the bind tables first, which allow us to check for
+## matching entries in __stubs.
+# RUN: (llvm-objdump -d --no-show-raw-insn --syms --bind --lazy-bind %t/dylink-lazy; \
+# RUN:  llvm-objdump -D --no-show-raw-insn %t/dylink-lazy) | FileCheck %s
+
+# CHECK-LABEL: SYMBOL TABLE:
+# CHECK:       {{0*}}[[#%x, IMGLOADER:]] {{.*}} __DATA,__data __dyld_private
+
+# CHECK-LABEL: Disassembly of section __TEXT,__text:
+# CHECK:         callq 0x[[#%x, HELLO_STUB:]]
+# CHECK-NEXT:    callq 0x[[#%x, GOODBYE_STUB:]]
+
+# CHECK-LABEL: Bind table:
+# CHECK:       __DATA_CONST __got 0x[[#%x, BINDER:]] pointer 0 libSystem dyld_stub_binder
+
+# CHECK-LABEL: Lazy bind table:
+# CHECK-DAG:   __DATA __la_symbol_ptr 0x{{0*}}[[#%x, HELLO_LAZY_PTR:]] libhello _print_hello
+# CHECK-DAG:   __DATA __la_symbol_ptr 0x{{0*}}[[#%x, GOODBYE_LAZY_PTR:]] libgoodbye _print_goodbye
+
+# CHECK-LABEL: Disassembly of section __TEXT,__stubs:
+# CHECK-DAG:     [[#%x, HELLO_STUB]]:   jmpq *[[#%u, HELLO_LAZY_PTR - HELLO_STUB - 6]](%rip)
+# CHECK-DAG:     [[#%x, GOODBYE_STUB]]: jmpq *[[#%u, GOODBYE_LAZY_PTR - GOODBYE_STUB - 6]](%rip)
+
+# CHECK-LABEL: Disassembly of section __TEXT,__stub_helper:
+# CHECK:         {{0*}}[[#%x, STUB_HELPER_ENTRY:]] <__stub_helper>:
+# CHECK-NEXT:    leaq [[#%u, IMGLOADER - STUB_HELPER_ENTRY - 7]](%rip), %r11
+# CHECK-NEXT:    pushq %r11
+# CHECK-NEXT:    jmpq *[[#%u, BINDER_OFF:]](%rip)
+# CHECK-NEXT:    [[#%x, BINDER - BINDER_OFF]]: nop
+# CHECK-NEXT:    pushq $0
+# CHECK-NEXT:    jmp 0x[[#STUB_HELPER_ENTRY]]
+# CHECK-NEXT:    pushq $
+# CHECK-NEXT:    jmp 0x[[#STUB_HELPER_ENTRY]]
+
+.text
+.globl _main
+
+_main:
+  sub $8, %rsp # 16-byte-align the stack; dyld checks for this
+  callq _print_hello
+  callq _print_goodbye
+  add $8, %rsp
+  ret