[lld-macho] Implement support for PIC

[int3]

Summary

• Implement rebase opcodes. Rebase opcodes tell dyld where absolute addresses have been encoded in the binary. If the binary is not loaded at its preferred address, dyld has to rebase these addresses by adding an offset to them.
• Support -pie and use it to test rebase opcodes.

This is necessary for absolute address references in dylibs, bundles etc
to work.

[compnerd]

Is there a funnel point that we know that all the rebase entries will pass through to ensure that we catch them rather than adding them at a couple of sites?

lld/MachO/SyntheticSections.h

187

What do you think of moving addend to after target?

214

Similar

[int3]

Is there a funnel point that we know that all the rebase entries will pass through to ensure that we catch them rather than adding them at a couple of sites?

It may be clearer if we scan the GOT/LazyPointerSection inside RebaseSection::finalizeContents() for any absolute addresses, rather than relying on the code that's adding entries to either of those sections to also handle the rebasing. I will try that... however, there isn't a funnel point that will cover absolute addresses from both our SyntheticSections as well as from InputSections.

lld/MachO/SyntheticSections.cpp

159

I should just return early instead of checking locations.empty() twice

lld/MachO/SyntheticSections.h

187

What's the rationale behind your preference? I thought putting the addend next to the symbol made sense since they both determine what address gets written into the target

[int3]

It may be clearer if we scan the GOT/LazyPointerSection inside RebaseSection::finalizeContents() for any absolute addresses

Actually, this doesn't really work either, because we need to add the rebases early in order that the isNeeded() filtering doesn't filter out RebaseSection. Also there's a fair bit of code duplication in this approach; it essentially mirrors the logic in NonLazyPointerSectionBase::writeTo() and LazyPointerSection::writeTo(). I don't see a nice solution here...

[int3]

minor update

[smeenai]

In D87199#2262522, @int3 wrote:

Is there a funnel point that we know that all the rebase entries will pass through to ensure that we catch them rather than adding them at a couple of sites?

It may be clearer if we scan the GOT/LazyPointerSection inside RebaseSection::finalizeContents() for any absolute addresses, rather than relying on the code that's adding entries to either of those sections to also handle the rebasing. I will try that... however, there isn't a funnel point that will cover absolute addresses from both our SyntheticSections as well as from InputSections.

I haven't reviewed this yet so I'm missing a bunch of context, and I haven't thought through this very much yet either, but would any of this be easier if SyntheticSections were InputSections instead of OutputSections? (There's definitely downsides to that too, but it's worth thinking about the trade-offs.)

[int3]

but would any of this be easier if SyntheticSections were InputSections instead of OutputSections

Maybe... we could make them InputSections and then generate unsigned relocations for each of their entries. There would be some additional overhead (e.g. the addend field would be useless) but it would allow us to handle the rebases in one place. One thing I'm not sure about is whether other architectures have an equivalent of X86_64_RELOC_UNSIGNED that can be used for this; it looks like arm64 does, but not sure about PPC (not that it really matters).

There are other benefits to having SyntheticSections be InputSections: there would no longer be a need for the SectionPointerUnion, and DSOHandle could just be an ordinary Defined symbol.

I actually can't think of many real downsides... do you have any in mind? That said, the current architecture is not terrible, and I'm inclined to work on implementing more features and pushing the refactoring till later.

[int3]

emit rebase opcodes for section relocations too

[int3]

rebase

[gkm]

lld/MachO/Writer.cpp

339–341

Without checking godbolt, I boldly assume that the computation for the string compare will be hoisted out of the inner loop. Please add a testcase for mixing -pie and compact unwind.

[gkm]

In lld/MachO/SyntheticSections.cpp, there are three instances of ...

clang-tidy: warning: 'auto *osec' can be declared as 'const auto *osec' [llvm-qualified-auto]

... which seem worthy of addressing.

[smeenai]

lld/MachO/Writer.cpp

339–341

There's gonna be lots of relocations, so it's probably worth confirming that the hoisting happens :)

The section comparison seems fine for now, but it also seems a bit janky. Is there any long-term redesign we could do here to make it cleaner? We should add a TODO somewhere if so to keep track of it.

[smeenai]

In D87199#2264781, @int3 wrote:

but would any of this be easier if SyntheticSections were InputSections instead of OutputSections

Maybe... we could make them InputSections and then generate unsigned relocations for each of their entries. There would be some additional overhead (e.g. the addend field would be useless) but it would allow us to handle the rebases in one place. One thing I'm not sure about is whether other architectures have an equivalent of X86_64_RELOC_UNSIGNED that can be used for this; it looks like arm64 does, but not sure about PPC (not that it really matters).

There are other benefits to having SyntheticSections be InputSections: there would no longer be a need for the SectionPointerUnion, and DSOHandle could just be an ordinary Defined symbol.

I actually can't think of many real downsides... do you have any in mind? That said, the current architecture is not terrible, and I'm inclined to work on implementing more features and pushing the refactoring till later.

I agree with refactoring later (not too much later, but it probably makes sense to at least get some experience with implementing other architectures first). We decided to make SyntheticSections be OutputSections back in https://reviews.llvm.org/D77893#inline-716459. We were debating why ELF makes them InputSections; it appears the main motivation for that design was to allow synthetic sections to be manipulated via linker scripts, which we don't need to support with Mach-O. We can decide what ultimately makes more sense when we have a bit more of the implementation completed though.

@psmith, in your talk on LLD's performance (https://archive.fosdem.org/2019/schedule/event/llvm_lld/), you mentioned something along the lines of LLD's synthetic sections being input sections (as opposed to output) significantly speeding up thunks (at the 25:10 mark). Would you be able to elaborate on why? We'll need to implement thunks when we add the ARM64 support, although our design will probably be closer to COFF's than ELF's (since we don't have linker scripts).

[gkm]

lld/MachO/Writer.cpp

339–341

The section comparison seems fine for now, but it also seems a bit janky. Is there any long-term redesign we could do here to make it cleaner? We should add a TODO somewhere if so to keep track of it.

What springs to mind is a flag indicating that an InputSection (or its parent MergedOutputSection) will not be written to the output file. We can add S_COMPACT_UNWIND to enum SectionType, which is cheaper to check than string compare on the name. And/or we can add an attribute S_ATTR_TEMPORARY or S_ATTR_INTERNAL or some such, indicating an input section is for internal use and not destined for output. The attribute will not be set on compact unwind sections with -r.

[MaskRay]

lld/MachO/SyntheticSections.cpp

165

If there are empty sections, there may be stability concerns.

[gkm]

lld/MachO/Writer.cpp

330–332

This is better: nothing in the relocs loop pertains to __compact_unwind so we can skip it at the top.

[int3]

lld/MachO/SyntheticSections.cpp

165

we can't have a rebase entry pointing to an empty section though

[int3]

address comments

[int3]

lld/MachO/Writer.cpp

330–332

good point. I've gone with this option, plus added a TODO so we revisit

[gkm]

Feel free to land when you have the -pie + compact unwind testcase.

[int3]

@gkm the test is already in the latest revision :)

[thakis]

lld/MachO/Driver.cpp

641

This didn't remove HelpHidden from pie, so we still warn that this is unimplemented.

Also, this should be on by default when targeting macOS 10.7+.

[int3]

lld/MachO/Driver.cpp

641

Thanks! Addressed in D92362.

lld/MachO/Arch/X86_64.cpp

case X86_64_RELOC_GOT: {
     in.got->addEntry(sym);
 
     if (sym->isTlv())
       error("found GOT relocation referencing thread-local variable in " +
             toString(isec));
     break;
   }
   case X86_64_RELOC_BRANCH: {
+    // TODO: factor this logic out so it can be reused for different
+    // architectures
     if (auto *dysym = dyn_cast<DylibSymbol>(sym)) {
       if (in.stubs->addEntry(dysym)) {
         if (sym->isWeakDef()) {
           in.binding->addEntry(dysym, in.lazyPointers,
                                sym->stubsIndex * WordSize);
           in.weakBinding->addEntry(sym, in.lazyPointers,
                                    sym->stubsIndex * WordSize);
         } else {
           in.lazyBinding->addEntry(dysym);
         }
       }
     } else if (auto *defined = dyn_cast<Defined>(sym)) {
-      if (defined->isWeakDef() && defined->isExternal())
-        if (in.stubs->addEntry(sym))
+      if (defined->isWeakDef() && defined->isExternal()) {
+        if (in.stubs->addEntry(sym)) {
+          in.rebase->addEntry(in.lazyPointers, sym->stubsIndex * WordSize);
           in.weakBinding->addEntry(sym, in.lazyPointers,
                                    sym->stubsIndex * WordSize);
         }
+      }
+    }
     break;
   }
   case X86_64_RELOC_UNSIGNED: {
     if (auto *dysym = dyn_cast<DylibSymbol>(sym)) {
       if (r.length != 3) {
         error("X86_64_RELOC_UNSIGNED referencing the dynamic symbol " +
               dysym->getName() + " must have r_length = 3");
         return;

lld/MachO/Config.h

struct PlatformInfo {
   llvm::VersionTuple sdk;
 };
 
 struct Configuration {
   Symbol *entry;
   bool hasReexports = false;
   bool allLoad = false;
   bool forceLoadObjC = false;
+  bool isPic = false;
   uint32_t headerPad;
   llvm::StringRef installName;
   llvm::StringRef outputFile;
   llvm::MachO::Architecture arch;
   PlatformInfo platform;
   llvm::MachO::HeaderFileType outputType;
   std::vector<llvm::StringRef> systemLibraryRoots;
   std::vector<llvm::StringRef> librarySearchPaths;

lld/MachO/Driver.cpp

case OPT_framework: {
       break;
     }
     case OPT_platform_version:
       handlePlatformVersion(arg);
       break;
     case OPT_all_load:
     case OPT_o:
     case OPT_dylib:
+    case OPT_pie:
     case OPT_e:
     case OPT_F:
     case OPT_L:
     case OPT_ObjC:
     case OPT_headerpad:
     case OPT_install_name:
     case OPT_rpath:
     case OPT_sub_library:
     case OPT_Z:
     case OPT_arch:
     case OPT_syslibroot:
     case OPT_sectcreate:
       // handled elsewhere
       break;
     default:
       warnIfUnimplementedOption(opt);
       break;
     }
   }
 
+  config->isPic = config->outputType == MH_DYLIB ||
+                  (config->outputType == MH_EXECUTE && args.hasArg(OPT_pie));
+
   // Now that all dylibs have been loaded, search for those that should be
   // re-exported.
   for (opt::Arg *arg : args.filtered(OPT_sub_library)) {
     config->hasReexports = true;
     StringRef searchName = arg->getValue();
     if (!markSubLibrary(searchName))
       error("-sub_library " + searchName + " does not match a supplied dylib");
   }

lld/MachO/SyntheticSections.h

 namespace lld {
 namespace macho {
 
 namespace section_names {
 
 constexpr const char pageZero[] = "__pagezero";
 constexpr const char common[] = "__common";
 constexpr const char header[] = "__mach_header";
+constexpr const char rebase[] = "__rebase";
 constexpr const char binding[] = "__binding";
 constexpr const char weakBinding[] = "__weak_binding";
 constexpr const char lazyBinding[] = "__lazy_binding";
 constexpr const char export_[] = "__export";
 constexpr const char symbolTable[] = "__symbol_table";
 constexpr const char indirectSymbolTable[] = "__ind_sym_tab";
 constexpr const char stringTable[] = "__string_table";
 constexpr const char got[] = "__got";
public:
   TlvPointerSection()
       : NonLazyPointerSectionBase(segment_names::data,
                                   section_names::threadPtrs) {}
 };
 
 using SectionPointerUnion =
     llvm::PointerUnion<const InputSection *, const OutputSection *>;
 
-struct BindingTarget {
-  SectionPointerUnion section;
-  uint64_t offset;
-  int64_t addend;
-
-  BindingTarget(SectionPointerUnion section, uint64_t offset, int64_t addend)
-      : section(section), offset(offset), addend(addend) {}
+struct Location {
+  SectionPointerUnion section = nullptr;
+  uint64_t offset = 0;
 
+  Location(SectionPointerUnion section, uint64_t offset)
+      : section(section), offset(offset) {}
   uint64_t getVA() const;
 };
 
+// Stores rebase opcodes, which tell dyld where absolute addresses have been
+// encoded in the binary. If the binary is not loaded at its preferred address,
+// dyld has to rebase these addresses by adding an offset to them.
+class RebaseSection : public LinkEditSection {
+public:
+  RebaseSection();
+  void finalizeContents();
+  uint64_t getRawSize() const override { return contents.size(); }
+  bool isNeeded() const override { return !locations.empty(); }
+  void writeTo(uint8_t *buf) const override;
+
+  void addEntry(SectionPointerUnion section, uint64_t offset) {
+    if (config->isPic)
+      locations.push_back({section, offset});
+  }
+
+private:
+  std::vector<Location> locations;
+  SmallVector<char, 128> contents;
+};
+
 struct BindingEntry {
   const DylibSymbol *dysym;
-  BindingTarget target;
-  BindingEntry(const DylibSymbol *dysym, BindingTarget target)
-      : dysym(dysym), target(std::move(target)) {}
+  int64_t addend;
+  Location target;
+  BindingEntry(const DylibSymbol *dysym, int64_t addend, Location target)
+      : dysym(dysym), addend(addend), target(std::move(target)) {}
 };
 
 // Stores bind opcodes for telling dyld which symbols to load non-lazily.
 class BindingSection : public LinkEditSection {
 public:
   BindingSection();
   void finalizeContents();
   uint64_t getRawSize() const override { return contents.size(); }
   bool isNeeded() const override { return !bindings.empty(); }
   void writeTo(uint8_t *buf) const override;
 
   void addEntry(const DylibSymbol *dysym, SectionPointerUnion section,
                 uint64_t offset, int64_t addend = 0) {
-    bindings.emplace_back(dysym, BindingTarget(section, offset, addend));
+    bindings.emplace_back(dysym, addend, Location(section, offset));
   }
 
 private:
   std::vector<BindingEntry> bindings;
   SmallVector<char, 128> contents;
 };
 
 struct WeakBindingEntry {
   const Symbol *symbol;
-  BindingTarget target;
-  WeakBindingEntry(const Symbol *symbol, BindingTarget target)
-      : symbol(symbol), target(std::move(target)) {}
+  int64_t addend;
+  Location target;
+  WeakBindingEntry(const Symbol *symbol, int64_t addend, Location target)
+      : symbol(symbol), addend(addend), target(std::move(target)) {}
 };
 
 // Stores bind opcodes for telling dyld which weak symbols need coalescing.
 // There are two types of entries in this section:
 //
 //   1) Non-weak definitions: This is a symbol definition that weak symbols in
 //   other dylibs should coalesce to.
 //
public:
   bool isNeeded() const override {
     return !bindings.empty() || !definitions.empty();
   }
 
   void writeTo(uint8_t *buf) const override;
 
   void addEntry(const Symbol *symbol, SectionPointerUnion section,
                 uint64_t offset, int64_t addend = 0) {
-    bindings.emplace_back(symbol, BindingTarget(section, offset, addend));
+    bindings.emplace_back(symbol, addend, Location(section, offset));
   }
 
   bool hasEntry() const { return !bindings.empty(); }
 
   void addNonWeakDefinition(const Defined *defined) {
     definitions.emplace_back(defined);
   }
 
uint64_t getRawSize() const override {
     return getNumSymbols() * sizeof(uint32_t);
   }
   bool isNeeded() const override;
   void writeTo(uint8_t *buf) const override;
 };
 
 struct InStruct {
   MachHeaderSection *header = nullptr;
+  RebaseSection *rebase = nullptr;
   BindingSection *binding = nullptr;
   WeakBindingSection *weakBinding = nullptr;
   LazyBindingSection *lazyBinding = nullptr;
   ExportSection *exports = nullptr;
   GotSection *got = nullptr;
   TlvPointerSection *tlvPointers = nullptr;
   LazyPointerSection *lazyPointers = nullptr;
   StubsSection *stubs = nullptr;

lld/MachO/SyntheticSections.cpp

void MachHeaderSection::writeTo(uint8_t *buf) const {
   hdr->filetype = config->outputType;
   hdr->ncmds = loadCommands.size();
   hdr->sizeofcmds = sizeOfCmds;
   hdr->flags = MachO::MH_NOUNDEFS | MachO::MH_DYLDLINK | MachO::MH_TWOLEVEL;
 
   if (config->outputType == MachO::MH_DYLIB && !config->hasReexports)
     hdr->flags |= MachO::MH_NO_REEXPORTED_DYLIBS;
 
+  if (config->outputType == MachO::MH_EXECUTE && config->isPic)
+    hdr->flags |= MachO::MH_PIE;
+
   if (in.exports->hasWeakSymbol || in.weakBinding->hasNonWeakDefinition())
     hdr->flags |= MachO::MH_WEAK_DEFINES;
 
   if (in.exports->hasWeakSymbol || in.weakBinding->hasEntry())
     hdr->flags |= MachO::MH_BINDS_TO_WEAK;
 
   for (OutputSegment *seg : outputSegments) {
     for (OutputSection *osec : seg->getSections()) {
for (LoadCommand *lc : loadCommands) {
     lc->writeTo(p);
     p += lc->getSize();
   }
 }
 
 PageZeroSection::PageZeroSection()
     : SyntheticSection(segment_names::pageZero, section_names::pageZero) {}
 
+uint64_t Location::getVA() const {
+  if (auto *isec = section.dyn_cast<const InputSection *>())
+    return isec->getVA() + offset;
+  return section.get<const OutputSection *>()->addr + offset;
+}
+
+RebaseSection::RebaseSection()
+    : LinkEditSection(segment_names::linkEdit, section_names::rebase) {}
+
+namespace {
+struct Rebase {
+  OutputSegment *segment = nullptr;
+  uint64_t offset = 0;
+  uint64_t consecutiveCount = 0;
+};
+} // namespace
+
+// Rebase opcodes allow us to describe a contiguous sequence of rebase location
+// using a single DO_REBASE opcode. To take advantage of it, we delay emitting
+// `DO_REBASE` until we have reached the end of a contiguous sequence.
+static void encodeDoRebase(Rebase &rebase, raw_svector_ostream &os) {
+  using namespace llvm::MachO;
+  assert(rebase.consecutiveCount != 0);
+  if (rebase.consecutiveCount <= REBASE_IMMEDIATE_MASK) {
+    os << static_cast<uint8_t>(REBASE_OPCODE_DO_REBASE_IMM_TIMES |
+                               rebase.consecutiveCount);
+  } else {
+    os << static_cast<uint8_t>(REBASE_OPCODE_DO_REBASE_ULEB_TIMES);
+    encodeULEB128(rebase.consecutiveCount, os);
+  }
+  rebase.consecutiveCount = 0;
+}
+
+static void encodeRebase(const OutputSection *osec, uint64_t outSecOff,
+                         Rebase &lastRebase, raw_svector_ostream &os) {
+  using namespace llvm::MachO;
+  OutputSegment *seg = osec->parent;
+  uint64_t offset = osec->getSegmentOffset() + outSecOff;
+  if (lastRebase.segment != seg || lastRebase.offset != offset) {
+    if (lastRebase.consecutiveCount != 0)
+      encodeDoRebase(lastRebase, os);
+
+    if (lastRebase.segment != seg) {
+      os << static_cast<uint8_t>(REBASE_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB |
+                                 seg->index);
+      encodeULEB128(offset, os);
+      lastRebase.segment = seg;
+      lastRebase.offset = offset;
+    } else {
+      assert(lastRebase.offset != offset);
+      os << static_cast<uint8_t>(REBASE_OPCODE_ADD_ADDR_ULEB);
+      encodeULEB128(offset - lastRebase.offset, os);
+      lastRebase.offset = offset;
+    }
+  }
+  ++lastRebase.consecutiveCount;
+  // DO_REBASE causes dyld to both perform the binding and increment the offset
+  lastRebase.offset += WordSize;
+}
+
+void RebaseSection::finalizeContents() {
+  using namespace llvm::MachO;
+  if (locations.empty())
+    return;
+
+  raw_svector_ostream os{contents};
+  Rebase lastRebase;
+
+  os << static_cast<uint8_t>(REBASE_OPCODE_SET_TYPE_IMM | REBASE_TYPE_POINTER);
+
+  llvm::sort(locations, [](const Location &a, const Location &b) {
+    return a.getVA() < b.getVA();
+  });
+  for (const Location &loc : locations) {
+    if (auto *isec = loc.section.dyn_cast<const InputSection *>()) {
+      encodeRebase(isec->parent, isec->outSecOff + loc.offset, lastRebase, os);
+    } else {
+      auto *osec = loc.section.get<const OutputSection *>();
+      encodeRebase(osec, loc.offset, lastRebase, os);
+    }
+  }
+  if (lastRebase.consecutiveCount != 0)
+    encodeDoRebase(lastRebase, os);
+
+  os << static_cast<uint8_t>(REBASE_OPCODE_DONE);
+}
+
+void RebaseSection::writeTo(uint8_t *buf) const {
+  memcpy(buf, contents.data(), contents.size());
+}
+
 NonLazyPointerSectionBase::NonLazyPointerSectionBase(const char *segname,
                                                      const char *name)
     : SyntheticSection(segname, name) {
   align = 8;
   flags = MachO::S_NON_LAZY_SYMBOL_POINTERS;
 }
 
 void NonLazyPointerSectionBase::addEntry(Symbol *sym) {

 static void encodeWeakOverride(const Defined *defined,
                                raw_svector_ostream &os) {
   using namespace llvm::MachO;
   os << static_cast<uint8_t>(BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM |
                              BIND_SYMBOL_FLAGS_NON_WEAK_DEFINITION)
      << defined->getName() << '\0';
 }
 
-uint64_t BindingTarget::getVA() const {
-  if (auto *isec = section.dyn_cast<const InputSection *>())
-    return isec->getVA() + offset;
-  return section.get<const OutputSection *>()->addr + offset;
-}
-
 // Emit bind opcodes, which are a stream of byte-sized opcodes that dyld
 // interprets to update a record with the following fields:
 //  * segment index (of the segment to write the symbol addresses to, typically
 //    the __DATA_CONST segment which contains the GOT)
 //  * offset within the segment, indicating the next location to write a binding
 //  * symbol type
 //  * symbol library ordinal (the index of its library's LC_LOAD_DYLIB command)
 //  * symbol name
void BindingSection::finalizeContents() {
   // same segment / section are located together.
   llvm::sort(bindings, [](const BindingEntry &a, const BindingEntry &b) {
     return a.target.getVA() < b.target.getVA();
   });
   for (const BindingEntry &b : bindings) {
     encodeDylibOrdinal(b.dysym, lastBinding, os);
     if (auto *isec = b.target.section.dyn_cast<const InputSection *>()) {
       encodeBinding(b.dysym, isec->parent, isec->outSecOff + b.target.offset,
-                    b.target.addend, lastBinding, os);
+                    b.addend, lastBinding, os);
     } else {
       auto *osec = b.target.section.get<const OutputSection *>();
-      encodeBinding(b.dysym, osec, b.target.offset, b.target.addend,
-                    lastBinding, os);
+      encodeBinding(b.dysym, osec, b.target.offset, b.addend, lastBinding, os);
     }
   }
   if (!bindings.empty())
     os << static_cast<uint8_t>(MachO::BIND_OPCODE_DONE);
 }
 
 void BindingSection::writeTo(uint8_t *buf) const {
   memcpy(buf, contents.data(), contents.size());
void WeakBindingSection::finalizeContents() {
   // result.
   llvm::sort(bindings,
              [](const WeakBindingEntry &a, const WeakBindingEntry &b) {
                return a.target.getVA() < b.target.getVA();
              });
   for (const WeakBindingEntry &b : bindings) {
     if (auto *isec = b.target.section.dyn_cast<const InputSection *>()) {
       encodeBinding(b.symbol, isec->parent, isec->outSecOff + b.target.offset,
-                    b.target.addend, lastBinding, os);
+                    b.addend, lastBinding, os);
     } else {
       auto *osec = b.target.section.get<const OutputSection *>();
-      encodeBinding(b.symbol, osec, b.target.offset, b.target.addend,
-                    lastBinding, os);
+      encodeBinding(b.symbol, osec, b.target.offset, b.addend, lastBinding, os);
     }
   }
   if (!bindings.empty() || !definitions.empty())
     os << static_cast<uint8_t>(MachO::BIND_OPCODE_DONE);
 }
 
 void WeakBindingSection::writeTo(uint8_t *buf) const {
   memcpy(buf, contents.data(), contents.size());

 void macho::addNonLazyBindingEntries(const Symbol *sym,
                                      SectionPointerUnion section,
                                      uint64_t offset, int64_t addend) {
   if (auto *dysym = dyn_cast<DylibSymbol>(sym)) {
     in.binding->addEntry(dysym, section, offset, addend);
     if (dysym->isWeakDef())
       in.weakBinding->addEntry(sym, section, offset, addend);
   } else if (auto *defined = dyn_cast<Defined>(sym)) {
+    in.rebase->addEntry(section, offset);
     if (defined->isWeakDef() && defined->isExternal())
       in.weakBinding->addEntry(sym, section, offset, addend);
   } else if (isa<DSOHandle>(sym)) {
     error("cannot bind to " + DSOHandle::name);
   } else {
     // Undefined symbols are filtered out in scanRelocations(); we should never
     // get here
     llvm_unreachable("cannot bind to an undefined symbol");
for (DylibSymbol *sym : entries)
     sym->lazyBindOffset = encode(*sym);
 }
 
 void LazyBindingSection::writeTo(uint8_t *buf) const {
   memcpy(buf, contents.data(), contents.size());
 }
 
 void LazyBindingSection::addEntry(DylibSymbol *dysym) {
-  if (entries.insert(dysym))
+  if (entries.insert(dysym)) {
     dysym->stubsHelperIndex = entries.size() - 1;
+    in.rebase->addEntry(in.lazyPointers, dysym->stubsIndex * WordSize);
+  }
 }
 
 // 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.

lld/MachO/Writer.cpp

public:
   StringTableSection *stringTableSection = nullptr;
   SymtabSection *symtabSection = nullptr;
   IndirectSymtabSection *indirectSymtabSection = nullptr;
 };
 
 // LC_DYLD_INFO_ONLY stores the offsets of symbol import/export information.
 class LCDyldInfo : public LoadCommand {
 public:
-  LCDyldInfo(BindingSection *bindingSection,
+  LCDyldInfo(RebaseSection *rebaseSection, BindingSection *bindingSection,
              WeakBindingSection *weakBindingSection,
              LazyBindingSection *lazyBindingSection,
              ExportSection *exportSection)
-      : bindingSection(bindingSection), weakBindingSection(weakBindingSection),
+      : rebaseSection(rebaseSection), bindingSection(bindingSection),
+        weakBindingSection(weakBindingSection),
         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 (rebaseSection->isNeeded()) {
+      c->rebase_off = rebaseSection->fileOff;
+      c->rebase_size = rebaseSection->getFileSize();
+    }
     if (bindingSection->isNeeded()) {
       c->bind_off = bindingSection->fileOff;
       c->bind_size = bindingSection->getFileSize();
     }
     if (weakBindingSection->isNeeded()) {
       c->weak_bind_off = weakBindingSection->fileOff;
       c->weak_bind_size = weakBindingSection->getFileSize();
     }
     if (lazyBindingSection->isNeeded()) {
       c->lazy_bind_off = lazyBindingSection->fileOff;
       c->lazy_bind_size = lazyBindingSection->getFileSize();
     }
     if (exportSection->isNeeded()) {
       c->export_off = exportSection->fileOff;
       c->export_size = exportSection->getFileSize();
     }
   }
 
+  RebaseSection *rebaseSection;
   BindingSection *bindingSection;
   WeakBindingSection *weakBindingSection;
   LazyBindingSection *lazyBindingSection;
   ExportSection *exportSection;
 };
 
 class LCDysymtab : public LoadCommand {
 public:
public:
   }
 
   const PlatformInfo &platform;
 };
 
 } // namespace
 
 void Writer::scanRelocations() {
   for (InputSection *isec : inputSections) {
     for (Reloc &r : isec->relocs) {
       if (auto *s = r.target.dyn_cast<lld::macho::Symbol *>()) {
         if (isa<Undefined>(s))
           error("undefined symbol " + s->getName() + ", referenced from " +
                 sys::path::filename(isec->file->getName()));
         else
           target->prepareSymbolRelocation(s, isec, r);
+      } else {
+        assert(r.target.is<InputSection *>());
+        if (!r.pcrel)
+          in.rebase->addEntry(isec, r.offset);
       }
     }
   }
 }
 
 void Writer::createLoadCommands() {
-  in.header->addLoadCommand(
-      make<LCDyldInfo>(in.binding, in.weakBinding, in.lazyBinding, in.exports));
+  in.header->addLoadCommand(make<LCDyldInfo>(
+      in.rebase, in.binding, in.weakBinding, in.lazyBinding, in.exports));
   in.header->addLoadCommand(make<LCSymtab>(symtabSection, stringTableSection));
   in.header->addLoadCommand(make<LCDysymtab>(indirectSymtabSection));
   for (StringRef path : config->runtimePaths)
     in.header->addLoadCommand(make<LCRPath>(path));
 
   switch (config->outputType) {
   case MH_EXECUTE:
     in.header->addLoadCommand(make<LCMain>());

 static int sectionOrder(OutputSection *osec) {
   StringRef segname = osec->parent->name;
   // Sections are uniquely identified by their segment + section name.
   if (segname == segment_names::text) {
     if (osec->name == section_names::header)
       return -1;
   } else if (segname == segment_names::linkEdit) {
     return StringSwitch<int>(osec->name)
+        .Case(section_names::rebase, -8)
         .Case(section_names::binding, -7)
         .Case(section_names::weakBinding, -6)
         .Case(section_names::lazyBinding, -5)
         .Case(section_names::export_, -4)
         .Case(section_names::symbolTable, -3)
         .Case(section_names::indirectSymbolTable, -2)
         .Case(section_names::stringTable, -1)
         .Default(0);
void Writer::run() {
   // 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)
     if (seg != linkEditSegment)
       assignAddresses(seg);
 
   // Fill __LINKEDIT contents.
+  in.rebase->finalizeContents();
   in.binding->finalizeContents();
   in.weakBinding->finalizeContents();
   in.lazyBinding->finalizeContents();
   in.exports->finalizeContents();
   symtabSection->finalizeContents();
   indirectSymtabSection->finalizeContents();
 
   // Now that __LINKEDIT is filled out, do a proper calculation of its
void Writer::run() {
   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.header = make<MachHeaderSection>();
+  in.rebase = make<RebaseSection>();
   in.binding = make<BindingSection>();
   in.weakBinding = make<WeakBindingSection>();
   in.lazyBinding = make<LazyBindingSection>();
   in.exports = make<ExportSection>();
   in.got = make<GotSection>();
   in.tlvPointers = make<TlvPointerSection>();
   in.lazyPointers = make<LazyPointerSection>();
   in.stubs = make<StubsSection>();
   in.stubHelper = make<StubHelperSection>();
   in.imageLoaderCache = make<ImageLoaderCacheSection>();
 }

lld/test/MachO/dylink-lazy.s

 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t/dylink-lazy.o
 # RUN: lld -flavor darwinnew -o %t/dylink-lazy \
 # RUN:   -L%S/Inputs/MacOSX.sdk/usr/lib -L%t -lhello -lgoodbye %t/dylink-lazy.o -lSystem
 
 ## 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 --syms --rebase --bind --lazy-bind %t/dylink-lazy; \
 # RUN:  llvm-objdump -D --no-show-raw-insn %t/dylink-lazy) | FileCheck %s
 
+# RUN: lld -flavor darwinnew -pie -o %t/dylink-lazy-pie \
+# RUN:   -L%S/Inputs/MacOSX.sdk/usr/lib -L%t -lhello -lgoodbye %t/dylink-lazy.o -lSystem
+# RUN: llvm-objdump --macho --rebase %t/dylink-lazy-pie | FileCheck %s --check-prefix=PIE
+
 # 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 that the rebase table is empty.
+# CHECK-LABEL: Rebase table:
+# CHECK-NEXT:  segment section address type
+
+# CHECK-NEXT:  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 $21
 # CHECK-NEXT:    jmp 0x[[#STUB_HELPER_ENTRY]]
 
+# PIE:         Rebase table:
+# PIE-NEXT:    segment  section            address           type
+# PIE-NEXT:    __DATA   __la_symbol_ptr    0x[[#%X, ADDR:]]  pointer
+# PIE-NEXT:    __DATA   __la_symbol_ptr    0x[[#ADDR + 8]]   pointer
+
 .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

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 -flavor darwinnew -L%S/Inputs/MacOSX.sdk/usr/lib -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 -flavor darwinnew -L%S/Inputs/MacOSX.sdk/usr/lib -lSystem -o %t/test %t/test.o -L%t -lhello
-# RUN: llvm-objdump --full-contents --bind %t/test | FileCheck %s --match-full-lines
+# 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 {{.*}}
 
 ## 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: [[#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: Bind table:
+# CHECK-NEXT: Bind table:
 # CHECK-NEXT: segment      section  address         type     addend  dylib     symbol
 # CHECK-NEXT: __DATA_CONST __got    0x[[#ADDR+16]]  pointer  0       libhello  _hello_its_me
 
+# RUN: lld -flavor darwinnew -pie -L%S/Inputs/MacOSX.sdk/usr/lib -lSystem -o %t/test %t/test.o -L%t -lhello
+# RUN: llvm-objdump --macho --rebase --bind %t/test | FileCheck %s --check-prefix=PIE --match-full-lines
+# PIE:      Rebase table:
+# PIE-NEXT: segment      section  address          type
+# PIE-NEXT: __DATA_CONST __got    0x[[#%X,ADDR:]]  pointer
+# PIE-NEXT: __DATA_CONST __got    0x[[#ADDR + 8]]  pointer
+
+# PIE-NEXT: Bind table:
+# PIE-NEXT: segment      section  address          type     addend  dylib     symbol
+# PIE-NEXT: __DATA_CONST __got    0x[[#ADDR+16]]   pointer  0       libhello  _hello_its_me
+
 .globl _main
 
 .text
 _main:
   movl $0x2000004, %eax # write() syscall
   mov $1, %rdi # stdout
   movq _hello_its_me@GOTPCREL(%rip), %rsi
   mov $15, %rdx # length of str

lld/test/MachO/x86-64-reloc-unsigned.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t.o
 # RUN: lld -flavor darwinnew -o %t %t.o
-# RUN: llvm-objdump --full-contents %t | FileCheck %s
-# CHECK: Contents of section __DATA,foo:
-# CHECK:  100001000 08100000 01000000
-# CHECK: Contents of section __DATA,bar:
-# CHECK:  100001008 011000f0 11211111 02000000
+# RUN: llvm-objdump --macho --rebase --full-contents %t | FileCheck %s
+
+# RUN: lld -flavor darwinnew -pie -o %t-pie %t.o
+# RUN: llvm-objdump --macho --rebase %t-pie | FileCheck %s --check-prefix=PIE
+
+# CHECK:       Contents of section __DATA,foo:
+# CHECK-NEXT:  100001000 08100000 01000000
+# CHECK:       Contents of section __DATA,bar:
+# CHECK-NEXT:  100001008 011000f0 11211111 02000000
+# CHECK:       Rebase table:
+# CHECK-NEXT:  segment  section            address     type
+# CHECK-EMPTY:
+
+# PIE:      Rebase table:
+# PIE-NEXT: segment  section            address           type
+# PIE-DAG:  __DATA   foo                0x[[#%X,ADDR:]]   pointer
+# PIE-DAG:  __DATA   bar                0x[[#ADDR + 8]]   pointer
+# PIE-DAG:  __DATA   bar                0x[[#ADDR + 12]]  pointer
+# PIE-DAG:  __DATA   baz                0x[[#ADDR + 20]]  pointer
 
 .globl _main, _foo, _bar
 
 .section __DATA,foo
 _foo:
 .quad _bar
 
 .section __DATA,bar
 _bar:
 ## We create a .int symbol reference here -- with non-zero data immediately
 ## after -- to check that lld reads precisely 32 bits (and not more) of the
 ## implicit addend when handling unsigned relocations of r_length = 2.
 ## Note that __PAGEZERO occupies the lower 32 bits, so all symbols are above
 ## that. To get a final relocated address that fits within 32 bits, we need to
 ## subtract an offset here.
 .int _foo - 0x0fffffff
 ## The unsigned relocation should support 64-bit addends too (r_length = 3).
 .quad _foo + 0x111111111
 
+.section __DATA,baz
+## Generates a section relocation.
+.quad L_.baz
+L_.baz:
+  .space 0
+
 .text
 _main:
   mov $0, %rax
   ret