[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

181

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

196

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

181

That's an improvement! 😺

196

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

181

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

73

pass by const ref?

74

ditto about parens

78–79

pass by const ref

lld/MachO/InputFiles.cpp

178

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

181

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

196

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

196

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

73

doesn't look like the const ref comment was addressed

lld/MachO/InputFiles.cpp

191

193–202

love the explanation!

196

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

193–202

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

73

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

78–79

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

178

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

193–202

Better.

196

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

178

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(const relocation_info) const override;
+  uint64_t getAddend(MemoryBufferRef, const section_64 &, const relocation_info,
+                     const 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 *,
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(const relocation_info rel) const {
+  return (rel.r_type == X86_64_RELOC_SUBTRACTOR);
+}
+
+uint64_t X86_64::getAddend(MemoryBufferRef mb, const section_64 &sec,
+                           const relocation_info rel,
+                           const 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 InputFile::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++) {
+    const relocation_info pairedInfo = relInfos[i];
+    const 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;
+    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());
-
+      assert(relInfo.r_symbolnum && relInfo.r_symbolnum <= subsections.size());
       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 &,
+                             const llvm::MachO::relocation_info,
+                             const llvm::MachO::relocation_info) const = 0;
+  virtual bool isPairedReloc(const 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;