[lld-macho] Check address ranges when applying relocations

[int3]

Summary

This diff required fixing getEmbeddedAddend to apply sign
extension to 32-bit values. We were previously passing around wrong
64-bit addend values that became "right" after being truncated back to
32-bit.

I've also made getEmbeddedAddend return a signed int, which is similar
to what LLD-ELF does for its getImplicitAddend.

reportRangeError, checkUInt, and checkInt are counterparts of similar
functions in LLD-ELF.

[thakis]

lld/MachO/Arch/ARM64.cpp

173

(Should the check be in encodeBranch26() instead (etc)? The we won't miss it for other calls, and the 26/28 discrepancy is maybe a bit less magical when the check is closer to the shift.

191

(same question)

[int3]

check range in encoding function

[int3]

lld/MachO/Arch/ARM64.cpp

173

Good idea. In fact while implementing it I realized we were actually missing ranges checks for the pointers to stubs, which lld-ELF does check. I've therefore added support for it by introducing SymbolDiagnostic. Want to have another look before I land this?

[thakis]

This breaks tests everywhere, eg http://45.33.8.238/linux/41614/step_11.txt (but every platform really)

Please take a look, and revert for now if it takes a while to fix.

[int3]

Weird, it seems like the addresses are off by 8 bytes. Perhaps llvm-mc is somehow being configured to auto-align things on my machine? Anyway, I guess we can replace those numbers with [[#]], their exact values aren't that important

lld/MachO/Arch/ARM64.cpp

 using namespace lld;
 using namespace lld::macho;
 
 namespace {
 
 struct ARM64 : TargetInfo {
   ARM64();
 
-  uint64_t getEmbeddedAddend(MemoryBufferRef, const section_64 &,
-                             const relocation_info) const override;
+  int64_t getEmbeddedAddend(MemoryBufferRef, const section_64 &,
   void relocateOne(uint8_t *loc, const Reloc &, uint64_t va,
                    uint64_t pc) const override;
 
   void writeStub(uint8_t *buf, const macho::Symbol &) const override;
   void writeStubHelperHeader(uint8_t *buf) const override;
   void writeStubHelperEntry(uint8_t *buf, const DylibSymbol &,
                             uint64_t entryAddr) const override;
 

 #undef B
   }};
   assert(type < relocAttrsArray.size() && "invalid relocation type");
   if (type >= relocAttrsArray.size())
     return invalidRelocAttrs;
   return relocAttrsArray[type];
 }
 
-uint64_t ARM64::getEmbeddedAddend(MemoryBufferRef mb, const section_64 &sec,
-                                  const relocation_info rel) const {
+int64_t ARM64::getEmbeddedAddend(MemoryBufferRef mb, const section_64 &sec,
   if (rel.r_type != ARM64_RELOC_UNSIGNED &&
       rel.r_type != ARM64_RELOC_SUBTRACTOR) {
     // All other reloc types should use the ADDEND relocation to store their
     // addends.
     // TODO(gkm): extract embedded addend just so we can assert that it is 0
     return 0;
   }
 
   auto *buf = reinterpret_cast<const uint8_t *>(mb.getBufferStart());
   const uint8_t *loc = buf + sec.offset + rel.r_address;
   switch (rel.r_length) {
   case 2:
-    return read32le(loc);
+    return static_cast<int32_t>(read32le(loc));
   case 3:
     return read64le(loc);
   default:
     llvm_unreachable("invalid r_length");
   }
 }
 
 inline uint64_t bitField(uint64_t value, int right, int width, int left) {
   return ((value >> right) & ((1 << width) - 1)) << left;
 }
 
 //              25                                                0
 // +-----------+---------------------------------------------------+
 // |           |                       imm26                       |
 // +-----------+---------------------------------------------------+
 
-inline uint64_t encodeBranch26(uint64_t base, uint64_t va) {
+inline uint64_t encodeBranch26(const Reloc &r, uint64_t base, uint64_t va) {
+  checkInt(r, va, 28);
   // Since branch destinations are 4-byte aligned, the 2 least-
   // significant bits are 0. They are right shifted off the end.
   return (base | bitField(va, 2, 26, 0));
 }
 
+inline uint64_t encodeBranch26(SymbolDiagnostic d, uint64_t base, uint64_t va) {
+  checkInt(d, va, 28);
+  return (base | bitField(va, 2, 26, 0));
+}
+
 //   30 29          23                                  5
 // +-+---+---------+-------------------------------------+---------+
 // | |ilo|         |                immhi                |         |
 // +-+---+---------+-------------------------------------+---------+
 
-inline uint64_t encodePage21(uint64_t base, uint64_t va) {
+inline uint64_t encodePage21(const Reloc &r, uint64_t base, uint64_t va) {
+  checkInt(r, va, 35);
+  return (base | bitField(va, 12, 2, 29) | bitField(va, 14, 19, 5));
+}
+
+inline uint64_t encodePage21(SymbolDiagnostic d, uint64_t base, uint64_t va) {
+  checkInt(d, va, 35);
   return (base | bitField(va, 12, 2, 29) | bitField(va, 14, 19, 5));
 }
 
 //                      21                   10
 // +-------------------+-----------------------+-------------------+
 // |                   |         imm12         |                   |
 // +-------------------+-----------------------+-------------------+
 

 // operands, then write-back the completed instruction.
 
 void ARM64::relocateOne(uint8_t *loc, const Reloc &r, uint64_t value,
                         uint64_t pc) const {
   uint32_t base = ((r.length == 2) ? read32le(loc) : 0);
   value += r.addend;
   switch (r.type) {
   case ARM64_RELOC_BRANCH26:
-    value = encodeBranch26(base, value - pc);
+    value = encodeBranch26(r, base, value - pc);
     break;
   case ARM64_RELOC_SUBTRACTOR:
   case ARM64_RELOC_UNSIGNED:
+    if (r.length == 2)
+      checkInt(r, value, 32);
     break;
   case ARM64_RELOC_POINTER_TO_GOT:
     if (r.pcrel)
       value -= pc;
+    checkInt(r, value, 32);
     break;
   case ARM64_RELOC_PAGE21:
   case ARM64_RELOC_GOT_LOAD_PAGE21:
-  case ARM64_RELOC_TLVP_LOAD_PAGE21:
+  case ARM64_RELOC_TLVP_LOAD_PAGE21: {
     assert(r.pcrel);
-    value = encodePage21(base, pageBits(value) - pageBits(pc));
+    value = encodePage21(r, base, pageBits(value) - pageBits(pc));
     break;
+  }
   case ARM64_RELOC_PAGEOFF12:
   case ARM64_RELOC_GOT_LOAD_PAGEOFF12:
   case ARM64_RELOC_TLVP_LOAD_PAGEOFF12:
     assert(!r.pcrel);
     value = encodePageOff12(base, value);
     break;
   default:
     llvm_unreachable("unexpected relocation type");
static constexpr uint32_t stubCode[] = {
     0xd61f0200, // 08: br    x16
 };
 
 void ARM64::writeStub(uint8_t *buf8, const macho::Symbol &sym) const {
   auto *buf32 = reinterpret_cast<uint32_t *>(buf8);
   uint64_t pcPageBits =
       pageBits(in.stubs->addr + sym.stubsIndex * sizeof(stubCode));
   uint64_t lazyPointerVA = in.lazyPointers->addr + sym.stubsIndex * WordSize;
-  buf32[0] = encodePage21(stubCode[0], pageBits(lazyPointerVA) - pcPageBits);
+  buf32[0] = encodePage21({&sym, "stub"}, stubCode[0],
+                          pageBits(lazyPointerVA) - pcPageBits);
   buf32[1] = encodePageOff12(stubCode[1], lazyPointerVA);
   buf32[2] = stubCode[2];
 }
 
 static constexpr uint32_t stubHelperHeaderCode[] = {
     0x90000011, // 00: adrp  x17, _dyld_private@page
     0x91000231, // 04: add   x17, x17, _dyld_private@pageoff
     0xa9bf47f0, // 08: stp   x16/x17, [sp, #-16]!
     0x90000010, // 0c: adrp  x16, dyld_stub_binder@page
     0xf9400210, // 10: ldr   x16, [x16, dyld_stub_binder@pageoff]
     0xd61f0200, // 14: br    x16
 };
 
 void ARM64::writeStubHelperHeader(uint8_t *buf8) const {
   auto *buf32 = reinterpret_cast<uint32_t *>(buf8);
   auto pcPageBits = [](int i) {
     return pageBits(in.stubHelper->addr + i * sizeof(uint32_t));
   };
   uint64_t loaderVA = in.imageLoaderCache->getVA();
-  buf32[0] =
-      encodePage21(stubHelperHeaderCode[0], pageBits(loaderVA) - pcPageBits(0));
+  SymbolDiagnostic d = {nullptr, "stub header helper"};
+  buf32[0] = encodePage21(d, stubHelperHeaderCode[0],
+                          pageBits(loaderVA) - pcPageBits(0));
   buf32[1] = encodePageOff12(stubHelperHeaderCode[1], loaderVA);
   buf32[2] = stubHelperHeaderCode[2];
   uint64_t binderVA =
       in.got->addr + in.stubHelper->stubBinder->gotIndex * WordSize;
-  buf32[3] =
-      encodePage21(stubHelperHeaderCode[3], pageBits(binderVA) - pcPageBits(3));
+  buf32[3] = encodePage21(d, stubHelperHeaderCode[3],
+                          pageBits(binderVA) - pcPageBits(3));
   buf32[4] = encodePageOff12(stubHelperHeaderCode[4], binderVA);
   buf32[5] = stubHelperHeaderCode[5];
 }
 
 static constexpr uint32_t stubHelperEntryCode[] = {
     0x18000050, // 00: ldr  w16, l0
     0x14000000, // 04: b    stubHelperHeader
     0x00000000, // 08: l0: .long 0
 };
 
 void ARM64::writeStubHelperEntry(uint8_t *buf8, const DylibSymbol &sym,
                                  uint64_t entryVA) const {
   auto *buf32 = reinterpret_cast<uint32_t *>(buf8);
   auto pcVA = [entryVA](int i) { return entryVA + i * sizeof(uint32_t); };
   uint64_t stubHelperHeaderVA = in.stubHelper->addr;
   buf32[0] = stubHelperEntryCode[0];
-  buf32[1] =
-      encodeBranch26(stubHelperEntryCode[1], stubHelperHeaderVA - pcVA(1));
+  buf32[1] = encodeBranch26({&sym, "stub helper"}, stubHelperEntryCode[1],
+                            stubHelperHeaderVA - pcVA(1));
   buf32[2] = sym.lazyBindOffset;
 }
 
 void ARM64::relaxGotLoad(uint8_t *loc, uint8_t type) const {
   // The instruction format comments below are quoted from
   // Arm® Architecture Reference Manual
   // Armv8, for Armv8-A architecture profile
   // ARM DDI 0487G.a (ID011921)

lld/MachO/Arch/X86_64.cpp

 using namespace lld;
 using namespace lld::macho;
 
 namespace {
 
 struct X86_64 : TargetInfo {
   X86_64();
 
-  uint64_t getEmbeddedAddend(MemoryBufferRef, const section_64 &,
-                             const relocation_info) const override;
+  int64_t getEmbeddedAddend(MemoryBufferRef, const section_64 &,
   void relocateOne(uint8_t *loc, const Reloc &, uint64_t va,
                    uint64_t relocVA) const override;
 
   void writeStub(uint8_t *buf, const macho::Symbol &) const override;
   void writeStubHelperHeader(uint8_t *buf) const override;
   void writeStubHelperEntry(uint8_t *buf, const DylibSymbol &,
                             uint64_t entryAddr) const override;
 
case X86_64_RELOC_SIGNED_2:
     return 2;
   case X86_64_RELOC_SIGNED_4:
     return 4;
   default:
     return 0;
   }
 }
 
-uint64_t X86_64::getEmbeddedAddend(MemoryBufferRef mb, const section_64 &sec,
-                                   relocation_info rel) const {
+int64_t X86_64::getEmbeddedAddend(MemoryBufferRef mb, const section_64 &sec,
   auto *buf = reinterpret_cast<const uint8_t *>(mb.getBufferStart());
   const uint8_t *loc = buf + sec.offset + rel.r_address;
 
   switch (rel.r_length) {
   case 2:
-    return read32le(loc) + pcrelOffset(rel.r_type);
+    return static_cast<int32_t>(read32le(loc)) + pcrelOffset(rel.r_type);
   case 3:
     return read64le(loc) + pcrelOffset(rel.r_type);
   default:
     llvm_unreachable("invalid r_length");
   }
 }
 
 void X86_64::relocateOne(uint8_t *loc, const Reloc &r, uint64_t value,
                          uint64_t relocVA) const {
   value += r.addend;
   if (r.pcrel) {
     uint64_t pc = relocVA + 4 + pcrelOffset(r.type);
     value -= pc;
   }
 
   switch (r.length) {
   case 2:
+    if (r.type == X86_64_RELOC_UNSIGNED)
+      checkUInt(r, value, 32);
+    else
+      checkInt(r, value, 32);
     write32le(loc, value);
     break;
   case 3:
     write64le(loc, value);
     break;
   default:
     llvm_unreachable("invalid r_length");
   }
 }
 
 // The following methods emit a number of assembly sequences with RIP-relative
 // addressing. Note that RIP-relative addressing on X86-64 has the RIP pointing
 // to the next instruction, not the current instruction, so we always have to
 // account for the current instruction's size when calculating offsets.
 // writeRipRelative helps with that.
 //
 // bufAddr:  The virtual address corresponding to buf[0].
 // bufOff:   The offset within buf of the next instruction.
 // destAddr: The destination address that the current instruction references.
-static void writeRipRelative(uint8_t *buf, uint64_t bufAddr, uint64_t bufOff,
-                             uint64_t destAddr) {
+static void writeRipRelative(SymbolDiagnostic d, uint8_t *buf, uint64_t bufAddr,
+                             uint64_t bufOff, uint64_t destAddr) {
   uint64_t rip = bufAddr + bufOff;
+  checkInt(d, destAddr - rip, 32);
   // For the instructions we care about, the RIP-relative address is always
   // stored in the last 4 bytes of the instruction.
   write32le(buf + bufOff - 4, destAddr - rip);
 }
 
 static constexpr uint8_t stub[] = {
     0xff, 0x25, 0, 0, 0, 0, // jmpq *__la_symbol_ptr(%rip)
 };
 
 void X86_64::writeStub(uint8_t *buf, const macho::Symbol &sym) const {
   memcpy(buf, stub, 2); // just copy the two nonzero bytes
   uint64_t stubAddr = in.stubs->addr + sym.stubsIndex * sizeof(stub);
-  writeRipRelative(buf, stubAddr, sizeof(stub),
+  writeRipRelative({&sym, "stub"}, buf, stubAddr, sizeof(stub),
                    in.lazyPointers->addr + sym.stubsIndex * WordSize);
 }
 
 static constexpr uint8_t stubHelperHeader[] = {
     0x4c, 0x8d, 0x1d, 0, 0, 0, 0, // 0x0: leaq ImageLoaderCache(%rip), %r11
     0x41, 0x53,                   // 0x7: pushq %r11
     0xff, 0x25, 0,    0, 0, 0,    // 0x9: jmpq *dyld_stub_binder@GOT(%rip)
     0x90,                         // 0xf: nop
 };
 
 void X86_64::writeStubHelperHeader(uint8_t *buf) const {
   memcpy(buf, stubHelperHeader, sizeof(stubHelperHeader));
-  writeRipRelative(buf, in.stubHelper->addr, 7, in.imageLoaderCache->getVA());
-  writeRipRelative(buf, in.stubHelper->addr, 0xf,
+  SymbolDiagnostic d = {nullptr, "stub helper header"};
+  writeRipRelative(d, buf, in.stubHelper->addr, 7,
+                   in.imageLoaderCache->getVA());
+  writeRipRelative(d, buf, in.stubHelper->addr, 0xf,
                    in.got->addr +
                        in.stubHelper->stubBinder->gotIndex * WordSize);
 }
 
 static constexpr uint8_t stubHelperEntry[] = {
     0x68, 0, 0, 0, 0, // 0x0: pushq <bind offset>
     0xe9, 0, 0, 0, 0, // 0x5: jmp <__stub_helper>
 };
 
 void X86_64::writeStubHelperEntry(uint8_t *buf, const DylibSymbol &sym,
                                   uint64_t entryAddr) const {
   memcpy(buf, stubHelperEntry, sizeof(stubHelperEntry));
   write32le(buf + 1, sym.lazyBindOffset);
-  writeRipRelative(buf, entryAddr, sizeof(stubHelperEntry),
-                   in.stubHelper->addr);
+  writeRipRelative({&sym, "stub helper"}, buf, entryAddr,
+                   sizeof(stubHelperEntry), in.stubHelper->addr);
 }
 
 void X86_64::relaxGotLoad(uint8_t *loc, uint8_t type) const {
   // Convert MOVQ to LEAQ
   if (loc[-2] != 0x8b)
     error(getRelocAttrs(type).name + " reloc requires MOVQ instruction");
   loc[-2] = 0x8d;
 }

lld/MachO/InputFiles.cpp

for (size_t i = 0; i < relInfos.size(); i++) {
     // so there is no need to merge opcode bits with address
     // bits. Therefore, it's easy and convenient to store addends in the
     // instruction-stream bytes that would otherwise contain zeroes. By
     // contrast, RISC ISAs such as ARM64 mix opcode bits with with
     // address bits so that bitwise arithmetic is necessary to extract
     // and insert them. Storing addends in the instruction stream is
     // possible, but inconvenient and more costly at link time.
 
-    uint64_t pairedAddend = 0;
+    int64_t pairedAddend = 0;
     relocation_info relInfo = relInfos[i];
     if (target->hasAttr(relInfo.r_type, RelocAttrBits::ADDEND)) {
       pairedAddend = SignExtend64<24>(relInfo.r_symbolnum);
       relInfo = relInfos[++i];
     }
     assert(i < relInfos.size());
     if (!validateRelocationInfo(this, sec, relInfo))
       continue;
     if (relInfo.r_address & R_SCATTERED)
       fatal("TODO: Scattered relocations not supported");
 
-    uint64_t embeddedAddend = target->getEmbeddedAddend(mb, sec, relInfo);
+    int64_t embeddedAddend = target->getEmbeddedAddend(mb, sec, relInfo);
     assert(!(embeddedAddend && pairedAddend));
-    uint64_t totalAddend = pairedAddend + embeddedAddend;
+    int64_t totalAddend = pairedAddend + embeddedAddend;
     Reloc r;
     r.type = relInfo.r_type;
     r.pcrel = relInfo.r_pcrel;
     r.length = relInfo.r_length;
     r.offset = relInfo.r_address;
     if (relInfo.r_extern) {
       r.referent = symbols[relInfo.r_symbolnum];
       r.addend = totalAddend;

lld/MachO/Relocations.h

struct Reloc {
   uint8_t type = llvm::MachO::GENERIC_RELOC_INVALID;
   bool pcrel = false;
   uint8_t length = 0;
   // The offset from the start of the subsection that this relocation belongs
   // to.
   uint32_t offset = 0;
   // Adding this offset to the address of the referent symbol or subsection
   // gives the destination that this relocation refers to.
-  uint64_t addend = 0;
+  int64_t addend = 0;
   llvm::PointerUnion<Symbol *, InputSection *> referent = nullptr;
 };
 
 bool validateSymbolRelocation(const Symbol *, const InputSection *,
                               const Reloc &);
 
+/*
+ * v: The value the relocation is attempting to encode
+ * bits: The number of bits actually available to encode this relocation
+ */
+void reportRangeError(const Reloc &, const llvm::Twine &v, uint8_t bits,
+                      int64_t min, uint64_t max);
+
+struct SymbolDiagnostic {
+  const Symbol *symbol;
+  llvm::StringRef reason;
+};
+
+void reportRangeError(SymbolDiagnostic, const llvm::Twine &v, uint8_t bits,
+                      int64_t min, uint64_t max);
+
+template <typename Diagnostic>
+inline void checkInt(Diagnostic d, int64_t v, int bits) {
+  if (v != llvm::SignExtend64(v, bits))
+    reportRangeError(d, llvm::Twine(v), bits, llvm::minIntN(bits),
+                     llvm::maxIntN(bits));
+}
+
+template <typename Diagnostic>
+inline void checkUInt(Diagnostic d, uint64_t v, int bits) {
+  if ((v >> bits) != 0)
+    reportRangeError(d, llvm::Twine(v), bits, 0, llvm::maxUIntN(bits));
+}
+
 extern const RelocAttrs invalidRelocAttrs;
 
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/Relocations.cpp

bool macho::validateSymbolRelocation(const Symbol *sym,
   if (relocAttrs.hasAttr(RelocAttrBits::DYSYM8) && isa<DylibSymbol>(sym) &&
       r.length != 3)
     error(message("has width " + std::to_string(1 << r.length) +
                   " bytes, but must be 8 bytes"));
 
   return valid;
 }
 
+void macho::reportRangeError(const Reloc &r, const Twine &v, uint8_t bits,
+                             int64_t min, uint64_t max) {
+  std::string hint;
+  if (auto *sym = r.referent.dyn_cast<Symbol *>())
+    hint = "; references " + toString(*sym);
+  // TODO: get location of reloc using something like LLD-ELF's getErrorPlace()
+  error("relocation " + target->getRelocAttrs(r.type).name +
+        " is out of range: " + v + " is not in [" + Twine(min) + ", " +
+        Twine(max) + "]" + hint);
+}
+
+void macho::reportRangeError(SymbolDiagnostic d, const Twine &v, uint8_t bits,
+                             int64_t min, uint64_t max) {
+  std::string hint;
+  if (d.symbol)
+    hint = "; references " + toString(*d.symbol);
+  error(d.reason + " is out of range: " + v + " is not in [" + Twine(min) +
+        ", " + Twine(max) + "]" + hint);
+}
+
 const RelocAttrs macho::invalidRelocAttrs{"INVALID", RelocAttrBits::_0};

lld/MachO/Target.h

enum : uint64_t {
   MaxAlignmentPowerOf2 = 32,
 };
 
 class TargetInfo {
 public:
   virtual ~TargetInfo() = default;
 
   // Validate the relocation structure and get its addend.
-  virtual uint64_t
+  virtual int64_t
   getEmbeddedAddend(llvm::MemoryBufferRef, const llvm::MachO::section_64 &,
                     const llvm::MachO::relocation_info) const = 0;
   virtual void relocateOne(uint8_t *loc, const Reloc &, uint64_t va,
                            uint64_t relocVA) const = 0;
 
   // Write code for lazy binding. See the comments on StubsSection for more
   // details.
   virtual void writeStub(uint8_t *buf, const Symbol &) const = 0;

lld/test/MachO/invalid/range-check.s

+# REQUIRES: x86
+
+# RUN: split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/test.s -o %t/test.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/bar.s -o %t/bar.o
+# RUN: %lld -dylib %t/bar.o -o %t/libbar.dylib
+# RUN: not %lld -lSystem -o /dev/null %t/libbar.dylib %t/test.o 2>&1 | FileCheck %s
+
+# CHECK: error: relocation UNSIGNED is out of range: 8589942792 is not in [0, 4294967295]; references _foo
+# CHECK: error: relocation GOT_LOAD is out of range: 4294974033 is not in [-2147483648, 2147483647]; references _foo
+# CHECK: error: stub is out of range: 4294974006 is not in [-2147483648, 2147483647]; references _bar
+# CHECK: error: stub helper header is out of range: 4294974005 is not in [-2147483648, 2147483647]
+# CHECK: error: stub helper header is out of range: 4294969893 is not in [-2147483648, 2147483647]
+
+#--- bar.s
+.globl _bar
+_bar:
+
+#--- test.s
+.globl _main, _foo
+
+_main:
+  movq _foo@GOTPCREL(%rip), %rax
+  callq _bar
+  ret
+
+.int _foo
+.zerofill __TEXT,bss,_zero,0xffffffff
+
+.data
+_foo:
+  .space 0