[lld-macho][nfc] Refactor to accommodate paired relocs

[gkm]

Summary

This is a refactor to pave the way for supporting paired-ADDEND for ARM64. The only paired reloc type for X86_64 is SUBTRACTOR. In a later diff, I will add SUBTRACTOR for both X86_64 and ARM64.

• s/getImplicitAddend/getAddend/ because it handles all forms of addend: implicit, explicit, paired.
• add predicate bool isPairedReloc()
• check range of relInfo.r_symbolnum is internal, unrelated to user-input, so use assert(), not error()
• minor cleanups & rearrangements in InputFile::parseRelocations()

[compnerd]

lld/MachO/Arch/X86_64.cpp

29

I wonder if it makes sense to use a std::pair<const relocation_info, const relocation_info> &. It should be tested, but I could see the compiler being smart enough to unpack the pair if possible, which just makes it much more clear that that the two parameters are the paired relocation. It took me a moment to realize that.

What happens in the case of an unpaired relocation?

lld/MachO/InputFiles.cpp

215

You could also do std::next(&RI) if you want to continue using the range based for loop.

255–256

This really isn't equivalent. The assert may be compiled out, while the previous behaviour would have been preserved and reported an error to the user.

[gkm]

lld/MachO/Arch/X86_64.cpp

29

I looked at some cases with [[ godbolt.org | godbolt.org ]] for paired vs. unpaired caller & callee. When the args are scalars, scalar replacement of aggregates works properly for callees, and functions that accept foo(long a, long b) vs. foo(std::pair<long, long> x) produce identical argument handling code. Note that x here is a value not a reference, otherwise there is extra indirection. When I looked beyond scalars toward struct MachO::relocation_info, I found that neither GCC nor LLVM could apply SRoA to both layers of pair + struct. On the caller side, there is overhead associated with making pairs. Sooo ... pairs come at some runtime cost.

The paired reloc is only valid when it has r_type of *_RELOC_ADDEND or *_RELOC_SUBTRACTOR. Otherwise it is ignored.

I fiddled writing it using std::pair<> and was not impressed that it improve clarity, while imposing runtime overhead.

lld/MachO/InputFiles.cpp

215

That's an improvement! 😺

255–256

I changed it to an assertion on the grounds that it is an internal "can't happen" error, rather than something a user might induce with malformed input.

[gkm]

lld/MachO/InputFiles.cpp

215

Only in concept ... it doesn't work in practice. std::next() accepts and returns an iterator. Range-based for keeps the iterator behind the scenes. The best I can do to make this more C++ish is to use an iterator object with std::next() vs. integer array index with ordinary arithmetic. Methinks there is no great advantage.

[int3]

Nit: Commit title seems to indicate that we are adding support for paired relocs in this diff, but it seems like this diff is just paving the way for adding that support. Might be worth rephrasing... could also tag with [nfc] to make it explicit.

Also, would be good to add some comments explaining what a paired relocation is, especially since it appears to be a Mach-O specific thing. (I know Apple's reloc.h explains it, but ideally someone reading LLD's code would be able to understand what's going on without cross-referencing)

lld/MachO/Arch/X86_64.cpp

72–78

pass by const ref?

73

ditto about parens

77–78

pass by const ref

lld/MachO/InputFiles.cpp

212

other reviewers have mentioned that LLVM style is to evaluate loop constants in the assignment part of the loop header (i.e. size_t i= 0, e = < relInfos.size(); i < e; ...). I don't really care much either way, just FYI

215

nit: I'd prefer to skip the extra parens around assignment and return expressions

255–256

A fuzzer could generate a file to trigger this error though, right?

(As an aside, we do need more compact ways of emitting error strings...)

[gkm]

• revise according to review feedback: remove parens around RHS expressions of return & assignment

[gkm]

• Add block comment about paired relocs

[thakis]

lld/MachO/InputFiles.cpp

255–256

LLD's philosophy is that it assumes that inputs are generally valid: https://github.com/llvm/llvm-project/blob/main/lld/docs/NewLLD.rst "The current policy is that it is your responsibility to give trustworthy object files. The function is guaranteed to return as long as you do not pass corrupted or malicious object files. A corrupted file could cause a fatal error or SEGV. That being said, you don't need to worry too much about it if you create object files in the usual way and give them to the linker. It is naturally expected to work, or otherwise it's a linker's bug." So crashing on fuzzer input is fine, as long as object files generated by compilers or assemblers work.

[int3]

Nit: Commit title seems to indicate that we are adding support for paired relocs in this diff, but it seems like this diff is just paving the way for adding that support. Might be worth rephrasing... could also tag with [nfc] to make it explicit.

^ do remember to address that, as well as the const ref stuff. Otherwise lgtm

lld/MachO/Arch/X86_64.cpp

72–78

doesn't look like the const ref comment was addressed

lld/MachO/InputFiles.cpp

227–236

love the explanation!

250

255–256

oh that's a relief. thanks for pointing it out

[smeenai]

In D90614#2459317, @int3 wrote:

Nit: Commit title seems to indicate that we are adding support for paired relocs in this diff, but it seems like this diff is just paving the way for adding that support. Might be worth rephrasing... could also tag with [nfc] to make it explicit.

^ do remember to address that

As a reminder, if you change your commit message locally, you need to pass --verbatim to arc diff to also update it in Phabricator.

[int3]

lld/MachO/InputFiles.cpp

227–236

inconvenient and more costly at runtime.

I might be misunderstanding, but do you mean link time instead of runtime?

[gkm]

lld/MachO/Arch/X86_64.cpp

72–78

relocation_info is a 64-bit struct that can pass-by-value in a register. Making it a reference introduces unnecessary indirection.

77–78

relocation_info is a 64-bit struct that can pass-by-value in a register. Making it a reference introduces unnecessary indirection.

lld/MachO/InputFiles.cpp

212

I did a quick audit for this in lld. The recommended LLVM style is used approx 1/3 of the time.

227–236

Better.

255–256

No, the assertion is checking for malformed symbol-table entries. Local symbol numbering is not accessible from assembler source.

[gkm]

• cleanup: convert remaining instances of relocation_info pass-by-cost-reference to pass-by-value
• address lingering feedback nits

[smeenai]

lld/MachO/InputFiles.cpp

212

I was curious about this so I looked at the generated assembly (my host compiler was Clang 9). At least in this case, it's smart enough to realize that the loop constant is, well, constant (and that it's just sec.nreloc) and uses that constant value instead of recomputing things in each iteration. (The value gets spilled to the stack so it's still a memory reload, but the extra variable wouldn't have saved you either.) I can imagine that analysis being a lot harder to do for the compiler in the general case though, hence the LLVM style recommendation (but yeah, it doesn't seem too enforced in LLD).

lld/MachO/Arch/X86_64.cpp

 using namespace lld;
 using namespace lld::macho;
 
 namespace {
 
 struct X86_64 : TargetInfo {
   X86_64();
 
-  uint64_t getImplicitAddend(MemoryBufferRef, const section_64 &,
-                             const relocation_info &) const override;
+  bool isPairedReloc(relocation_info) const override;
+  uint64_t getAddend(MemoryBufferRef, const section_64 &, relocation_info,
+                     relocation_info) const override;
   void relocateOne(uint8_t *loc, const Reloc &, uint64_t val) 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;
 
   void prepareSymbolRelocation(lld::macho::Symbol *, const InputSection *,
                                const Reloc &) override;
   uint64_t resolveSymbolVA(uint8_t *buf, const lld::macho::Symbol &,
                            uint8_t type) const override;
 };
 
 } // namespace
 
 static std::string getErrorLocation(MemoryBufferRef mb, const section_64 &sec,
-                                    const relocation_info &rel) {
+                                    relocation_info rel) {
   return ("invalid relocation at offset " + std::to_string(rel.r_address) +
           " of " + sec.segname + "," + sec.sectname + " in " +
           mb.getBufferIdentifier())
       .str();
 }
 
 static void validateLength(MemoryBufferRef mb, const section_64 &sec,
-                           const relocation_info &rel,
+                           relocation_info rel,
                            ArrayRef<uint8_t> validLengths) {
   if (find(validLengths, rel.r_length) != validLengths.end())
     return;
 
   std::string msg = getErrorLocation(mb, sec, rel) + ": relocations of type " +
                     std::to_string(rel.r_type) + " must have r_length of ";
   bool first = true;
   for (uint8_t length : validLengths) {
     if (!first)
       msg += " or ";
     first = false;
     msg += std::to_string(length);
   }
   fatal(msg);
 }
 
-uint64_t X86_64::getImplicitAddend(MemoryBufferRef mb, const section_64 &sec,
-                                   const relocation_info &rel) const {
+bool X86_64::isPairedReloc(relocation_info rel) const {
+  return rel.r_type == X86_64_RELOC_SUBTRACTOR;
+}
+
+uint64_t X86_64::getAddend(MemoryBufferRef mb, const section_64 &sec,
+                           relocation_info rel,
+                           relocation_info pairedRel) const {
   auto *buf = reinterpret_cast<const uint8_t *>(mb.getBufferStart());
   const uint8_t *loc = buf + sec.offset + rel.r_address;
 
   if (isThreadLocalVariables(sec.flags) && rel.r_type != X86_64_RELOC_UNSIGNED)
     error("relocations in thread-local variable sections must be "
           "X86_64_RELOC_UNSIGNED");
 
   switch (rel.r_type) {
case X86_64_RELOC_TLV:
     // since the RIP has advanced by 4 at this point. This is only valid when
     // r_length = 2, which is enforced by validateLength().
     val -= 4;
     break;
   case X86_64_RELOC_UNSIGNED:
     break;
   default:
     llvm_unreachable(
-        "getImplicitAddend should have flagged all unhandled relocation types");
+        "getAddend should have flagged all unhandled relocation types");
   }
 
   switch (r.length) {
   case 0:
     *loc = val;
     break;
   case 1:
     write16le(loc, val);

lld/MachO/InputFiles.cpp

static InputSection *findContainingSubsection(SubsectionMap &map,
   auto it = std::prev(map.upper_bound(*offset));
   *offset -= it->first;
   return it->second;
 }
 
 void ObjFile::parseRelocations(const section_64 &sec,
                                SubsectionMap &subsecMap) {
   auto *buf = reinterpret_cast<const uint8_t *>(mb.getBufferStart());
-  ArrayRef<any_relocation_info> anyRelInfos(
-      reinterpret_cast<const any_relocation_info *>(buf + sec.reloff),
-      sec.nreloc);
+  ArrayRef<relocation_info> relInfos(
+      reinterpret_cast<const relocation_info *>(buf + sec.reloff), sec.nreloc);
 
-  for (const any_relocation_info &anyRelInfo : anyRelInfos) {
-    if (anyRelInfo.r_word0 & R_SCATTERED)
+  for (size_t i = 0; i < relInfos.size(); i++) {
+    // Paired relocations serve as Mach-O's method for attaching a
+    // supplemental datum to a primary relocation record. ELF does not
+    // need them because the *_RELOC_RELA records contain the extra
+    // addend field, vs. *_RELOC_REL which omit the addend.
+    //
+    // The {X86_64,ARM64}_RELOC_SUBTRACTOR record holds the subtrahend,
+    // and the paired *_RELOC_UNSIGNED record holds the minuend. The
+    // datum for each is a symbolic address. The result is the runtime
+    // offset between two addresses.
+    //
+    // The ARM64_RELOC_ADDEND record holds the addend, and the paired
+    // ARM64_RELOC_BRANCH26 or ARM64_RELOC_PAGE21/PAGEOFF12 holds the
+    // base symbolic address.
+    //
+    // Note: X86 does not use *_RELOC_ADDEND because it can embed an
+    // addend into the instruction stream. On X86, a relocatable address
+    // field always occupies an entire contiguous sequence of byte(s),
+    // 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.
+
+    relocation_info pairedInfo = relInfos[i];
+    relocation_info relInfo =
+        target->isPairedReloc(pairedInfo) ? relInfos[++i] : pairedInfo;
+    assert(i < relInfos.size());
+    if (relInfo.r_address & R_SCATTERED)
       fatal("TODO: Scattered relocations not supported");
 
-    auto relInfo = reinterpret_cast<const relocation_info &>(anyRelInfo);
-
     Reloc r;
     r.type = relInfo.r_type;
     r.pcrel = relInfo.r_pcrel;
     r.length = relInfo.r_length;
-    uint64_t rawAddend = target->getImplicitAddend(mb, sec, relInfo);
-
+    r.offset = relInfo.r_address;
+    // For unpaired relocs, pairdInfo (just a copy of relInfo) is ignored
+    uint64_t rawAddend = target->getAddend(mb, sec, relInfo, pairedInfo);
     if (relInfo.r_extern) {
       r.referent = symbols[relInfo.r_symbolnum];
       r.addend = rawAddend;
     } else {
-      if (relInfo.r_symbolnum == 0 || relInfo.r_symbolnum > subsections.size())
-        fatal("invalid section index in relocation for offset " +
-              std::to_string(r.offset) + " in section " + sec.sectname +
-              " of " + getName());
-
       SubsectionMap &referentSubsecMap = subsections[relInfo.r_symbolnum - 1];
       const section_64 &referentSec = sectionHeaders[relInfo.r_symbolnum - 1];
       uint32_t referentOffset;
       if (relInfo.r_pcrel) {
         // The implicit addend for pcrel section relocations is the pcrel offset
         // in terms of the addresses in the input file. Here we adjust it so
         // that it describes the offset from the start of the referent section.
         // TODO: The offset of 4 is probably not right for ARM64, nor for
         //       relocations with r_length != 2.
         referentOffset =
             sec.addr + relInfo.r_address + 4 + rawAddend - referentSec.addr;
       } else {
         // The addend for a non-pcrel relocation is its absolute address.
         referentOffset = rawAddend - referentSec.addr;
       }
       r.referent = findContainingSubsection(referentSubsecMap, &referentOffset);
       r.addend = referentOffset;
     }
 
-    r.offset = relInfo.r_address;
     InputSection *subsec = findContainingSubsection(subsecMap, &r.offset);
     subsec->relocs.push_back(r);
   }
 }
 
 static macho::Symbol *createDefined(const structs::nlist_64 &sym,
                                     StringRef name, InputSection *isec,
                                     uint32_t value) {

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
-  getImplicitAddend(llvm::MemoryBufferRef, const llvm::MachO::section_64 &,
-                    const llvm::MachO::relocation_info &) const = 0;
+  virtual uint64_t getAddend(llvm::MemoryBufferRef,
+                             const llvm::MachO::section_64 &,
+                             llvm::MachO::relocation_info,
+                             llvm::MachO::relocation_info) const = 0;
+  virtual bool isPairedReloc(llvm::MachO::relocation_info) const = 0;
   virtual void relocateOne(uint8_t *loc, const Reloc &, 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 Symbol &) const = 0;
   virtual void writeStubHelperHeader(uint8_t *buf) const = 0;
   virtual void writeStubHelperEntry(uint8_t *buf, const DylibSymbol &,
                                     uint64_t entryAddr) const = 0;