[lld-macho] Support subtractor relocations that reference sections

[int3]

Summary

The minuend (but not the subtrahend) can reference a section.

Note that we do not yet properly validate that the subtrahend isn't
referencing a section; I've filed PR50034 to track that.

I've also extended the reloc-subtractor.s test to reorder symbols, to
make sure that the addends are being associated with the minuend (and not
the subtrahend) relocation.

Fixes PR49999.

[int3]

[int3]

lld/MachO/Arch/X86_64.cpp

97

I hoisted this into the caller for uniformity (because in the case of subtractor relocs we need to handle the minuend's addend in the caller.)

[int3]

lld/MachO/Arch/ARM64.cpp

 // are weird -- it results in the value of the GOT slot being written, instead
 // of the address. Let's not support it unless we find a real-world use case.
 
 const RelocAttrs &ARM64::getRelocAttrs(uint8_t type) const {
   static const std::array<RelocAttrs, 11> relocAttrsArray{{
 #define B(x) RelocAttrBits::x
       {"UNSIGNED",
        B(UNSIGNED) | B(ABSOLUTE) | B(EXTERN) | B(LOCAL) | B(BYTE4) | B(BYTE8)},
-      {"SUBTRACTOR", B(SUBTRAHEND) | B(BYTE4) | B(BYTE8)},
+      {"SUBTRACTOR", B(SUBTRAHEND) | B(EXTERN) | B(BYTE4) | B(BYTE8)},
       {"BRANCH26", B(PCREL) | B(EXTERN) | B(BRANCH) | B(BYTE4)},
       {"PAGE21", B(PCREL) | B(EXTERN) | B(BYTE4)},
       {"PAGEOFF12", B(ABSOLUTE) | B(EXTERN) | B(BYTE4)},
       {"GOT_LOAD_PAGE21", B(PCREL) | B(EXTERN) | B(GOT) | B(BYTE4)},
       {"GOT_LOAD_PAGEOFF12",
        B(ABSOLUTE) | B(EXTERN) | B(GOT) | B(LOAD) | B(BYTE4)},
       {"POINTER_TO_GOT", B(PCREL) | B(EXTERN) | B(GOT) | B(POINTER) | B(BYTE4)},
       {"TLVP_LOAD_PAGE21", B(PCREL) | B(EXTERN) | B(TLV) | B(BYTE4)},

lld/MachO/Arch/ARM64Common.cpp

 // 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 {
   uint32_t base = ((r.length == 2) ? read32le(loc) : 0);
-  value += r.addend;
   switch (r.type) {
   case ARM64_RELOC_BRANCH26:
     value = encodeBranch26(r, base, value - pc);
     break;
   case ARM64_RELOC_SUBTRACTOR:
   case ARM64_RELOC_UNSIGNED:
     if (r.length == 2)
       checkInt(r, value, 32);

lld/MachO/Arch/ARM64_32.cpp

 } // namespace
 
 // These are very similar to ARM64's relocation attributes, except that we don't
 // have the BYTE8 flag set.
 const RelocAttrs &ARM64_32::getRelocAttrs(uint8_t type) const {
   static const std::array<RelocAttrs, 11> relocAttrsArray{{
 #define B(x) RelocAttrBits::x
       {"UNSIGNED", B(UNSIGNED) | B(ABSOLUTE) | B(EXTERN) | B(LOCAL) | B(BYTE4)},
-      {"SUBTRACTOR", B(SUBTRAHEND) | B(BYTE4)},
+      {"SUBTRACTOR", B(SUBTRAHEND) | B(EXTERN) | B(BYTE4)},
       {"BRANCH26", B(PCREL) | B(EXTERN) | B(BRANCH) | B(BYTE4)},
       {"PAGE21", B(PCREL) | B(EXTERN) | B(BYTE4)},
       {"PAGEOFF12", B(ABSOLUTE) | B(EXTERN) | B(BYTE4)},
       {"GOT_LOAD_PAGE21", B(PCREL) | B(EXTERN) | B(GOT) | B(BYTE4)},
       {"GOT_LOAD_PAGEOFF12",
        B(ABSOLUTE) | B(EXTERN) | B(GOT) | B(LOAD) | B(BYTE4)},
       {"POINTER_TO_GOT", B(PCREL) | B(EXTERN) | B(GOT) | B(POINTER) | B(BYTE4)},
       {"TLVP_LOAD_PAGE21", B(PCREL) | B(EXTERN) | B(TLV) | B(BYTE4)},

lld/MachO/Arch/X86_64.cpp

const RelocAttrs &X86_64::getRelocAttrs(uint8_t type) const {
   static const std::array<RelocAttrs, 10> relocAttrsArray{{
 #define B(x) RelocAttrBits::x
       {"UNSIGNED",
        B(UNSIGNED) | B(ABSOLUTE) | B(EXTERN) | B(LOCAL) | B(BYTE4) | B(BYTE8)},
       {"SIGNED", B(PCREL) | B(EXTERN) | B(LOCAL) | B(BYTE4)},
       {"BRANCH", B(PCREL) | B(EXTERN) | B(BRANCH) | B(BYTE4)},
       {"GOT_LOAD", B(PCREL) | B(EXTERN) | B(GOT) | B(LOAD) | B(BYTE4)},
       {"GOT", B(PCREL) | B(EXTERN) | B(GOT) | B(POINTER) | B(BYTE4)},
-      {"SUBTRACTOR", B(SUBTRAHEND) | B(BYTE4) | B(BYTE8)},
+      {"SUBTRACTOR", B(SUBTRAHEND) | B(EXTERN) | B(BYTE4) | B(BYTE8)},
       {"SIGNED_1", B(PCREL) | B(EXTERN) | B(LOCAL) | B(BYTE4)},
       {"SIGNED_2", B(PCREL) | B(EXTERN) | B(LOCAL) | B(BYTE4)},
       {"SIGNED_4", B(PCREL) | B(EXTERN) | B(LOCAL) | B(BYTE4)},
       {"TLV", B(PCREL) | B(EXTERN) | B(TLV) | B(LOAD) | B(BYTE4)},
 #undef B
   }};
   assert(type < relocAttrsArray.size() && "invalid relocation type");
   if (type >= relocAttrsArray.size())
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)

lld/MachO/InputFiles.cpp

if (target->hasAttr(relInfo.r_type, RelocAttrBits::ADDEND)) {
       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");
 
+    bool isSubtrahend =
+        target->hasAttr(relInfo.r_type, RelocAttrBits::SUBTRAHEND);
     int64_t embeddedAddend = target->getEmbeddedAddend(mb, sec.offset, relInfo);
     assert(!(embeddedAddend && pairedAddend));
     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;
+      r.addend = isSubtrahend ? 0 : totalAddend;
     } else {
-      SubsectionMap &referentSubsecMap = subsections[relInfo.r_symbolnum - 1];
+      assert(!isSubtrahend);
       const Section &referentSec = sectionHeaders[relInfo.r_symbolnum - 1];
       uint64_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.
         // FIXME This logic was written around x86_64 behavior -- ARM64 doesn't
         // have pcrel section relocations. We may want to factor this out into
         // the arch-specific .cpp file.
         assert(target->hasAttr(r.type, RelocAttrBits::BYTE4));
         referentOffset =
             sec.addr + relInfo.r_address + 4 + totalAddend - referentSec.addr;
       } else {
         // The addend for a non-pcrel relocation is its absolute address.
         referentOffset = totalAddend - referentSec.addr;
       }
+      SubsectionMap &referentSubsecMap = subsections[relInfo.r_symbolnum - 1];
       r.referent = findContainingSubsection(referentSubsecMap, &referentOffset);
       r.addend = referentOffset;
     }
 
     InputSection *subsec = findContainingSubsection(subsecMap, &r.offset);
     subsec->relocs.push_back(r);
 
-    if (target->hasAttr(r.type, RelocAttrBits::SUBTRAHEND)) {
-      relInfo = relInfos[++i];
+    if (isSubtrahend) {
+      relocation_info minuendInfo = relInfos[++i];
       // SUBTRACTOR relocations should always be followed by an UNSIGNED one
-      // indicating the minuend symbol.
-      assert(target->hasAttr(relInfo.r_type, RelocAttrBits::UNSIGNED) &&
-             relInfo.r_extern);
+      // attached to the same address.
+      assert(target->hasAttr(minuendInfo.r_type, RelocAttrBits::UNSIGNED) &&
+             relInfo.r_address == minuendInfo.r_address);
       Reloc p;
-      p.type = relInfo.r_type;
-      p.referent = symbols[relInfo.r_symbolnum];
+      p.type = minuendInfo.r_type;
+      if (minuendInfo.r_extern) {
+        p.referent = symbols[minuendInfo.r_symbolnum];
+        p.addend = totalAddend;
+      } else {
+        uint64_t referentOffset =
+            totalAddend - sectionHeaders[minuendInfo.r_symbolnum - 1].addr;
+        SubsectionMap &referentSubsecMap =
+            subsections[minuendInfo.r_symbolnum - 1];
+        p.referent =
+            findContainingSubsection(referentSubsecMap, &referentOffset);
+        p.addend = referentOffset;
+      }
       subsec->relocs.push_back(p);
     }
   }
 }
 
 template <class NList>
 static macho::Symbol *createDefined(const NList &sym, StringRef name,
                                     InputSection *isec, uint64_t value,

lld/MachO/InputSection.cpp

void InputSection::writeTo(uint8_t *buf) {
   memcpy(buf, data.data(), data.size());
 
   for (size_t i = 0; i < relocs.size(); i++) {
     const Reloc &r = relocs[i];
     uint8_t *loc = buf + r.offset;
     uint64_t referentVA = 0;
     if (target->hasAttr(r.type, RelocAttrBits::SUBTRAHEND)) {
       const Symbol *fromSym = r.referent.get<Symbol *>();
-      const Symbol *toSym = relocs[++i].referent.get<Symbol *>();
-      referentVA = toSym->getVA() - fromSym->getVA();
+      const Reloc &minuend = relocs[++i];
+      uint64_t minuendVA;
+      if (const Symbol *toSym = minuend.referent.dyn_cast<Symbol *>())
+        minuendVA = toSym->getVA();
+      else
+        minuendVA = minuend.referent.get<InputSection *>()->getVA();
+      referentVA = minuendVA - fromSym->getVA() + minuend.addend;
     } else if (auto *referentSym = r.referent.dyn_cast<Symbol *>()) {
       if (target->hasAttr(r.type, RelocAttrBits::LOAD) &&
           !referentSym->isInGot())
         target->relaxGotLoad(loc, r.type);
       referentVA = resolveSymbolVA(loc, *referentSym, r.type);
 
       if (isThreadLocalVariables(flags)) {
         // References from thread-local variable sections are treated as offsets
         // relative to the start of the thread-local data memory area, which
         // is initialized via copying all the TLV data sections (which are all
         // contiguous).
         if (isa<Defined>(referentSym))
           referentVA -= firstTLVDataSection->addr;
       }
     } else if (auto *referentIsec = r.referent.dyn_cast<InputSection *>()) {
       referentVA = referentIsec->getVA();
     }
-    target->relocateOne(loc, r, referentVA, getVA() + r.offset);
+    target->relocateOne(loc, r, referentVA + r.addend, getVA() + r.offset);
   }
 }
 
 bool macho::isCodeSection(InputSection *isec) {
   uint32_t type = isec->flags & SECTION_TYPE;
   if (type != S_REGULAR && type != S_COALESCED)
     return false;
 

lld/MachO/Writer.cpp

for (InputSection *isec : inputSections) {
 
     for (auto it = isec->relocs.begin(); it != isec->relocs.end(); ++it) {
       Reloc &r = *it;
       if (target->hasAttr(r.type, RelocAttrBits::SUBTRAHEND)) {
         // Skip over the following UNSIGNED relocation -- it's just there as the
         // minuend, and doesn't have the usual UNSIGNED semantics. We don't want
         // to emit rebase opcodes for it.
         it = std::next(it);
-        assert(isa<Defined>(it->referent.dyn_cast<Symbol *>()));
         continue;
       }
       if (auto *sym = r.referent.dyn_cast<Symbol *>()) {
         if (auto *undefined = dyn_cast<Undefined>(sym))
           treatUndefinedSymbol(*undefined);
         // treatUndefinedSymbol() can replace sym with a DylibSymbol; re-check.
         if (!isa<Undefined>(sym) && validateSymbolRelocation(sym, isec, r))
           prepareSymbolRelocation(sym, isec, r);

lld/test/MachO/reloc-subtractor.s

 # REQUIRES: x86, aarch64
-# RUN: rm -rf %t; mkdir %t
-# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t/x86_64.o
-# RUN: llvm-mc -filetype=obj -triple=arm64-apple-darwin %s -o %t/arm64.o
-# RUN: %lld -lSystem %t/x86_64.o -o %t/x86_64
+# RUN: rm -rf %t; split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/test.s -o %t/x86_64.o
+# RUN: llvm-mc -filetype=obj -triple=arm64-apple-darwin %t/test.s -o %t/arm64.o
+# RUN: %lld -lSystem %t/x86_64.o -o %t/x86_64 -order_file %t/order-file
 # RUN: llvm-objdump --syms --full-contents --rebase %t/x86_64 | FileCheck %s
-# RUN: %lld -arch arm64 -lSystem %t/arm64.o -o %t/arm64
+# RUN: %lld -arch arm64 -lSystem %t/arm64.o -o %t/arm64 -order_file %t/order-file
 # RUN: llvm-objdump --syms --full-contents --rebase %t/arm64 | FileCheck %s
 
 # CHECK-LABEL: SYMBOL TABLE:
-# CHECK:       {{0*}}[[#%x, SUB1ADDR:]] l {{.*}} __DATA,__data _sub1
-# CHECK:       {{0*}}[[#%x, SUB2ADDR:]] l {{.*}} __DATA,__data _sub2
-# CHECK:       {{0*}}[[#%x, SUB3ADDR:]] l {{.*}} __DATA,__data _sub3
-# CHECK:       {{0*}}[[#%x, SUB4ADDR:]] l {{.*}} __DATA,__data _sub4
-# CHECK-LABEL: Contents of section __DATA,__data:
+# CHECK:       {{0*}}[[#%x, SUB1ADDR:]] l {{.*}} __DATA,bar _sub1
+# CHECK:       {{0*}}[[#%x, SUB2ADDR:]] l {{.*}} __DATA,bar _sub2
+# CHECK:       {{0*}}[[#%x, SUB3ADDR:]] l {{.*}} __DATA,bar _sub3
+# CHECK:       {{0*}}[[#%x, SUB4ADDR:]] l {{.*}} __DATA,bar _sub4
+# CHECK:       {{0*}}[[#%x, SUB5ADDR:]] l {{.*}} __DATA,bar _sub5
+# CHECK-LABEL: Contents of section __DATA,bar:
 # CHECK:       [[#SUB1ADDR]] 10000000
 # CHECK-NEXT:  [[#SUB2ADDR]] f2ffffff
 # CHECK-NEXT:  [[#SUB3ADDR]] 14000000 00000000
 # CHECK-NEXT:  [[#SUB4ADDR]] f6ffffff ffffffff
+# CHECK-NEXT:  [[#SUB5ADDR]] f1ffffff ffffffff
 # CHECK:       Rebase table:
 # CHECK-NEXT:  segment  section            address     type
 # CHECK-EMPTY:
 
+#--- test.s
+
 .globl _main, _subtrahend_1, _subtrahend_2, _minuend1, _minuend2
 
-.data
-_subtrahend_1:
+.section __DATA,foo
+  .space 16
+L_.minuend:
   .space 16
+
+.section __DATA,bar
 _minuend_1:
   .space 16
 _minuend_2:
   .space 16
+_subtrahend_1:
+  .space 16
 _subtrahend_2:
   .space 16
+
 _sub1:
   .long _minuend_1 - _subtrahend_1
   .space 12
 _sub2:
   .long _minuend_2 - _subtrahend_2 + 2
   .space 12
 _sub3:
   .quad _minuend_1 - _subtrahend_1 + 4
   .space 8
 _sub4:
   .quad _minuend_2 - _subtrahend_2 + 6
+  .space 8
+_sub5:
+  .quad L_.minuend - _subtrahend_1 + 1
+  .space 8
 
 .text
 .p2align 2
 _main:
   ret
+
+.subsections_via_symbols
+
+#--- order-file
+## Reorder the symbols to make sure that the addends are being associated with
+## the minuend (and not the subtrahend) relocation.
+_subtrahend_1
+_minuend_1
+_minuend_2
+_subtrahend_2