[lld-macho] Have relocation address included in range-check error message

[int3]

Summary

This makes it easier to debug those errors. See e.g. https://github.com/llvm/llvm-project/issues/52767#issuecomment-1028713943

We take the approach of 'reverse-engineering' the InputSection from the
output buffer offset. This provides for a cleaner Target API, and is
similar to LLD-ELF's implementation of getErrorPlace().

[int3]

lld/MachO/SyntheticSections.h

597–599

So in LLD-ELF, bufferStart is a member of the Out struct, while the synthetic sections are part of the InStruct. We don't have an Out struct at the moment, but IMO our InStruct should be renamed to Out, for unlike LLD-ELF, our synthetic sections are OutputSections.

Alternatively, we could put all the synthetic sections into a Synth struct, and leave just bufferStart in the Out struct... but I'm not sure what else would go into our Out. Maybe bufferStart could just be a global?

anyway we can figure the exact renaming separately from this diff

[int3]

rebase

[Roger]

lld/MachO/Arch/ARM64Common.h

109–112

I'm not sure which way is better. Is there a reason why you didn't use pointer arithmetic here and elsewhere? I'm wondering if the current code performs a dereferencing + address of operations unnecessarily (or if that gets optimized out). It's not a big deal and either way is fine with me but I just wanted to ask.

[int3]

lld/MachO/Arch/ARM64Common.h

109–112

just style preference. This should be trivial for the compiler to optimize, I don't think we have to worry about it (but you can use godbolt to verify)

[Roger]

lld/MachO/Relocations.cpp

66–67

If calling this function on an offset that doesn't belong to a ConcatOutputSection should not be happening, should we be add an assert to enforce this?

[int3]

lld/MachO/Relocations.cpp

66–67

yeah fair. I'll just delete this check, the cast<> below itself contains an assert

lld/MachO/Arch/ARM64Common.h

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(const Reloc &r, uint64_t base, uint64_t va) {
-  checkInt(r, va, 28);
+inline void encodeBranch26(uint32_t *loc, const Reloc &r, uint32_t base,
+                           uint64_t va) {
+  checkInt(loc, 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));
+  llvm::support::endian::write32le(loc, 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));
+inline void encodeBranch26(uint32_t *loc, SymbolDiagnostic d, uint32_t base,
+                           uint64_t va) {
+  checkInt(loc, d, va, 28);
+  llvm::support::endian::write32le(loc, base | bitField(va, 2, 26, 0));
 }
 
 //   30 29          23                                  5
 // +-+---+---------+-------------------------------------+---------+
 // | |ilo|         |                immhi                |         |
 // +-+---+---------+-------------------------------------+---------+
 
-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 void encodePage21(uint32_t *loc, const Reloc &r, uint32_t base,
+                         uint64_t va) {
+  checkInt(loc, r, va, 35);
+  llvm::support::endian::write32le(loc, 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));
+inline void encodePage21(uint32_t *loc, SymbolDiagnostic d, uint32_t base,
+                         uint64_t va) {
+  checkInt(loc, d, va, 35);
+  llvm::support::endian::write32le(loc, base | bitField(va, 12, 2, 29) |
+                                            bitField(va, 14, 19, 5));
 }
 
 //                      21                   10
 // +-------------------+-----------------------+-------------------+
 // |                   |         imm12         |                   |
 // +-------------------+-----------------------+-------------------+
 
-inline uint64_t encodePageOff12(uint32_t base, uint64_t va) {
+inline void encodePageOff12(uint32_t *loc, uint32_t base, uint64_t va) {
   int scale = 0;
   if ((base & 0x3b00'0000) == 0x3900'0000) { // load/store
     scale = base >> 30;
     if (scale == 0 && (base & 0x0480'0000) == 0x0480'0000) // 128-bit variant
       scale = 4;
   }
 
   // TODO(gkm): extract embedded addend and warn if != 0
   // uint64_t addend = ((base & 0x003FFC00) >> 10);
-  return (base | bitField(va, scale, 12 - scale, 10));
+  llvm::support::endian::write32le(loc,
+                                   base | bitField(va, scale, 12 - scale, 10));
 }
 
 inline uint64_t pageBits(uint64_t address) {
   const uint64_t pageMask = ~0xfffull;
   return address & pageMask;
 }
 
 template <class LP>
 inline void writeStub(uint8_t *buf8, const uint32_t stubCode[3],
                       const macho::Symbol &sym) {
   auto *buf32 = reinterpret_cast<uint32_t *>(buf8);
   constexpr size_t stubCodeSize = 3 * sizeof(uint32_t);
   uint64_t pcPageBits =
       pageBits(in.stubs->addr + sym.stubsIndex * stubCodeSize);
   uint64_t lazyPointerVA =
       in.lazyPointers->addr + sym.stubsIndex * LP::wordSize;
-  buf32[0] = encodePage21({&sym, "stub"}, stubCode[0],
-                          pageBits(lazyPointerVA) - pcPageBits);
-  buf32[1] = encodePageOff12(stubCode[1], lazyPointerVA);
+  encodePage21(&buf32[0], {&sym, "stub"}, stubCode[0],
+  encodePageOff12(&buf32[1], stubCode[1], lazyPointerVA);
   buf32[2] = stubCode[2];
 }
 
 template <class LP>
 inline void writeStubHelperHeader(uint8_t *buf8,
                                   const uint32_t stubHelperHeaderCode[6]) {
   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();
   SymbolDiagnostic d = {nullptr, "stub header helper"};
-  buf32[0] = encodePage21(d, stubHelperHeaderCode[0],
-                          pageBits(loaderVA) - pcPageBits(0));
-  buf32[1] = encodePageOff12(stubHelperHeaderCode[1], loaderVA);
+  encodePage21(&buf32[0], d, stubHelperHeaderCode[0],
+  encodePageOff12(&buf32[1], stubHelperHeaderCode[1], loaderVA);
   buf32[2] = stubHelperHeaderCode[2];
   uint64_t binderVA =
       in.got->addr + in.stubHelper->stubBinder->gotIndex * LP::wordSize;
-  buf32[3] = encodePage21(d, stubHelperHeaderCode[3],
-                          pageBits(binderVA) - pcPageBits(3));
-  buf32[4] = encodePageOff12(stubHelperHeaderCode[4], binderVA);
+  encodePage21(&buf32[3], d, stubHelperHeaderCode[3],
+  encodePageOff12(&buf32[4], stubHelperHeaderCode[4], binderVA);
   buf32[5] = stubHelperHeaderCode[5];
 }
 
 inline void writeStubHelperEntry(uint8_t *buf8,
                                  const uint32_t stubHelperEntryCode[3],
                                  const DylibSymbol &sym, uint64_t entryVA) {
   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({&sym, "stub helper"}, stubHelperEntryCode[1],
-                            stubHelperHeaderVA - pcVA(1));
+  encodeBranch26(&buf32[1], {&sym, "stub helper"}, stubHelperEntryCode[1],
   buf32[2] = sym.lazyBindOffset;
 }
 
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/Arch/ARM64Common.cpp

case 2:
     return static_cast<int32_t>(read32le(loc));
   case 3:
     return read64le(loc);
   default:
     llvm_unreachable("invalid r_length");
   }
 }
 
+static void writeValue(uint8_t *loc, const Reloc &r, uint64_t value) {
+  switch (r.length) {
+  case 2:
+    checkInt(loc, r, value, 32);
+    write32le(loc, value);
+    break;
+  case 3:
+    write64le(loc, value);
+    break;
+  default:
+    llvm_unreachable("invalid r_length");
+  }
+}
+
 // For instruction relocations (load, store, add), the base
 // instruction is pre-populated in the text section. A pre-populated
 // instruction has opcode & register-operand bits set, with immediate
 // operands zeroed. We read it from text, OR-in the immediate
 // operands, then write-back the completed instruction.
-
 void ARM64Common::relocateOne(uint8_t *loc, const Reloc &r, uint64_t value,
                               uint64_t pc) const {
+  auto loc32 = reinterpret_cast<uint32_t *>(loc);
   uint32_t base = ((r.length == 2) ? read32le(loc) : 0);
   switch (r.type) {
   case ARM64_RELOC_BRANCH26:
-    value = encodeBranch26(r, base, value - pc);
+    encodeBranch26(loc32, r, base, value - pc);
     break;
   case ARM64_RELOC_SUBTRACTOR:
   case ARM64_RELOC_UNSIGNED:
-    if (r.length == 2)
-      checkInt(r, value, 32);
+    writeValue(loc, r, value);
     break;
   case ARM64_RELOC_POINTER_TO_GOT:
     if (r.pcrel)
       value -= pc;
-    checkInt(r, value, 32);
+    writeValue(loc, r, value);
     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(r, base, pageBits(value) - pageBits(pc));
+    encodePage21(loc32, 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);
+    encodePageOff12(loc32, base, value);
     break;
   default:
     llvm_unreachable("unexpected relocation type");
   }
-
-  switch (r.length) {
-  case 2:
-    write32le(loc, value);
-    break;
-  case 3:
-    write64le(loc, value);
-    break;
-  default:
-    llvm_unreachable("invalid r_length");
-  }
 }
 
 void ARM64Common::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)
   uint32_t instruction = read32le(loc);

lld/MachO/Arch/X86_64.cpp

void X86_64::relocateOne(uint8_t *loc, const Reloc &r, uint64_t value,
   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);
+      checkUInt(loc, r, value, 32);
     else
-      checkInt(r, value, 32);
+      checkInt(loc, 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(SymbolDiagnostic d, uint8_t *buf, uint64_t bufAddr,
                              uint64_t bufOff, uint64_t destAddr) {
   uint64_t rip = bufAddr + bufOff;
-  checkInt(d, destAddr - rip, 32);
+  checkInt(buf, 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)
 };

lld/MachO/Relocations.h

 
 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);
+void reportRangeError(void *loc, 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);
+void reportRangeError(void *loc, 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) {
+inline void checkInt(void *loc, Diagnostic d, int64_t v, int bits) {
   if (v != llvm::SignExtend64(v, bits))
-    reportRangeError(d, llvm::Twine(v), bits, llvm::minIntN(bits),
+    reportRangeError(loc, d, llvm::Twine(v), bits, llvm::minIntN(bits),
                      llvm::maxIntN(bits));
 }
 
 template <typename Diagnostic>
-inline void checkUInt(Diagnostic d, uint64_t v, int bits) {
+inline void checkUInt(void *loc, Diagnostic d, uint64_t v, int bits) {
   if ((v >> bits) != 0)
-    reportRangeError(d, llvm::Twine(v), bits, 0, llvm::maxUIntN(bits));
+    reportRangeError(loc, d, llvm::Twine(v), bits, 0, llvm::maxUIntN(bits));
 }
 
 inline void writeAddress(uint8_t *loc, uint64_t addr, uint8_t length) {
   switch (length) {
   case 2:
     llvm::support::endian::write32le(loc, addr);
     break;
   case 3:

lld/MachO/Relocations.cpp

 //===- Relocations.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 "Relocations.h"
+#include "ConcatOutputSection.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 
 #include "lld/Common/ErrorHandler.h"
 
 using namespace llvm;
 using namespace lld;
bool macho::validateSymbolRelocation(const Symbol *sym,
 
   if (relocAttrs.hasAttr(RelocAttrBits::TLV) != sym->isTlv())
     error(message(Twine("requires that symbol ") + sym->getName() + " " +
                   (sym->isTlv() ? "not " : "") + "be thread-local"));
 
   return valid;
 }
 
-void macho::reportRangeError(const Reloc &r, const Twine &v, uint8_t bits,
-                             int64_t min, uint64_t max) {
+// Given an offset in the output buffer, figure out which ConcatInputSection (if
+// any) maps to it. At the same time, update the offset such that it is relative
+// to the InputSection rather than to the output buffer.
+//
+// Obtaining the InputSection allows us to have better error diagnostics.
+// However, many of our relocation-handling methods do not take the InputSection
+// as a parameter. Since we are already passing the buffer offsets to our Target
+// methods, this function allows us to emit better errors without threading an
+// additional InputSection argument through the call stack.
+//
+// This is implemented as a slow linear search through OutputSegments,
+// OutputSections, and finally the InputSections themselves. However, this
+// function should be called only on error paths, so some overhead is fine.
+static InputSection *offsetToInputSection(uint64_t *off) {
+  for (OutputSegment *seg : outputSegments) {
+    if (*off < seg->fileOff || *off >= seg->fileOff + seg->fileSize)
+      continue;
+
+    const std::vector<OutputSection *> &sections = seg->getSections();
+    size_t osecIdx = 0;
+    for (; osecIdx < sections.size(); ++osecIdx)
+      if (*off < sections[osecIdx]->fileOff)
+        break;
+    assert(osecIdx > 0);
+    // We should be only calling this function on offsets that belong to
+    // ConcatOutputSections.
+    auto *osec = cast<ConcatOutputSection>(sections[osecIdx - 1]);
+    *off -= osec->fileOff;
+
+    size_t isecIdx = 0;
+    for (; isecIdx < osec->inputs.size(); ++isecIdx) {
+      const ConcatInputSection *isec = osec->inputs[isecIdx];
+      if (*off < isec->outSecOff)
+        break;
+    }
+    assert(isecIdx > 0);
+    ConcatInputSection *isec = osec->inputs[isecIdx - 1];
+    *off -= isec->outSecOff;
+    return isec;
+  }
+  return nullptr;
+}
+
+void macho::reportRangeError(void *loc, const Reloc &r, const Twine &v,
+                             uint8_t bits, int64_t min, uint64_t max) {
   std::string hint;
+  uint64_t off = reinterpret_cast<const uint8_t *>(loc) - in.bufferStart;
+  const InputSection *isec = offsetToInputSection(&off);
+  std::string locStr = isec ? isec->getLocation(off) : "(invalid location)";
   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 +
+  error(locStr + ": 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) {
+void macho::reportRangeError(void *loc, SymbolDiagnostic d, const Twine &v,
+                             uint8_t bits, int64_t min, uint64_t max) {
+  // FIXME: should we use `loc` somehow to provide a better error message?
   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/SyntheticSections.h

private:
   // We're using unordered_map instead of DenseMap here because we need to
   // support all possible integer values -- there are no suitable tombstone
   // values for DenseMap.
   std::unordered_map<UInt128, uint64_t, Hasher<UInt128>> literal16Map;
   std::unordered_map<uint64_t, uint64_t> literal8Map;
   std::unordered_map<uint32_t, uint64_t> literal4Map;
 };
 
 struct InStruct {
+  const uint8_t *bufferStart = nullptr;
   MachHeaderSection *header = nullptr;
   CStringSection *cStringSection = nullptr;
   WordLiteralSection *wordLiteralSection = nullptr;
   RebaseSection *rebase = nullptr;
   BindingSection *binding = nullptr;
   WeakBindingSection *weakBinding = nullptr;
   LazyBindingSection *lazyBinding = nullptr;
   ExportSection *exports = nullptr;
   GotSection *got = nullptr;

lld/MachO/Writer.cpp

 }
 
 void Writer::openFile() {
   Expected<std::unique_ptr<FileOutputBuffer>> bufferOrErr =
       FileOutputBuffer::create(config->outputFile, fileOff,
                                FileOutputBuffer::F_executable);
 
   if (!bufferOrErr)
-    error("failed to open " + config->outputFile + ": " +
+    fatal("failed to open " + config->outputFile + ": " +
           llvm::toString(bufferOrErr.takeError()));
-  else
-    buffer = std::move(*bufferOrErr);
+  in.bufferStart = buffer->getBufferStart();
 }
 
 void Writer::writeSections() {
   uint8_t *buf = buffer->getBufferStart();
   for (const OutputSegment *seg : outputSegments)
     for (const OutputSection *osec : seg->getSections())
       osec->writeTo(buf + osec->fileOff);
 }

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

 # REQUIRES: x86
 
 # RUN: rm -rf %t; 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: [[#]] is not in [0, 4294967295]; references _foo
-# CHECK: error: relocation GOT_LOAD is out of range: [[#]] is not in [-2147483648, 2147483647]; references _foo
+# CHECK: error: {{.*}}test.o:(symbol _main+0xd): relocation UNSIGNED is out of range: [[#]] is not in [0, 4294967295]; references _foo
+# CHECK: error: {{.*}}test.o:(symbol _main+0x3): relocation GOT_LOAD is out of range: [[#]] is not in [-2147483648, 2147483647]; references _foo
 # CHECK: error: stub is out of range: [[#]] is not in [-2147483648, 2147483647]; references _bar
 # CHECK: error: stub helper header is out of range: [[#]] is not in [-2147483648, 2147483647]
 # CHECK: error: stub helper header is out of range: [[#]] is not in [-2147483648, 2147483647]
 
 #--- bar.s
 .globl _bar
 _bar: