[ELF] Regroup code creates ELF relocations references ELFReference into a couple of new virtual functions

[atanasyan]

Summary

Follow-up to the rL203408. Two virtual functions createRelocationReference() responsible for creation of ELFReference have been replaced by a couple of new virtual functions createRelocationReferences() (plural). Each former function creates a single ELFReference for a specified Elf_Rela or Elf_Rel relocation records. The new functions responsible for creation of all relocation references for provided symbol.

For all targets except MIPS there are no functional changes.

MIPS ABI has a notion of paired relocations. An effective addend of such relocations are calculated using addends of both pair's members. Each R_MIPS_HI16 and R_MIPS_GOT16 (for local symbols) relocations must have an associated R_MIPS_LO16 entry immediately following it in the list of relocations. Immediately does not mean "next record" in relocations section but "next record referenced the same symbol". Moreover a single R_MIPS_LO16 relocation can be paired with multiple preceding R_MIPS_HI16/R_MIPS_GOT16 relocations.

The paired relocation can have offsets belong to the different symbols. That is why we need to have access to list of all relocations during construction of ELFReference for MIPS target.

[shankarke]

LGTM.

[atanasyan]

Thanks for review.

Closed by commit rL206102 (authored by @atanasyan)

lib/ReaderWriter/ELF/ELFFile.h

public:
 
   Atom *findAtom(const Elf_Sym *symbol) {
     return _symbolToAtomMapping.lookup(symbol);
   }
 
 protected:
   ELFDefinedAtom<ELFT> *createDefinedAtomAndAssignRelocations(
       StringRef symbolName, StringRef sectionName, const Elf_Sym *symbol,
-      const Elf_Shdr *section, ArrayRef<uint8_t> content);
+      const Elf_Shdr *section, ArrayRef<uint8_t> symContent,
+      ArrayRef<uint8_t> secContent);
 
-  /// \brief Create a reference for the Elf_Sym symbol
-  /// and Elf_Rela relocation entry.
-  virtual ELFReference<ELFT> *createRelocationReference(const Elf_Sym &symbol,
-                                                        const Elf_Rela &rai);
-  /// \brief Create a reference for the Elf_Sym symbol
-  /// and Elf_Rel relocation entry.
-  virtual ELFReference<ELFT> *
-  createRelocationReference(const Elf_Sym &symbol, const Elf_Rel &ri,
-                            ArrayRef<uint8_t> content);
+  /// \brief Iterate over Elf_Rela relocations list and create references.
+  virtual void createRelocationReferences(const Elf_Sym &symbol,
+                                          ArrayRef<uint8_t> content,
+                                          range<Elf_Rela_Iter> rels);
+
+  /// \brief Iterate over Elf_Rel relocations list and create references.
+  virtual void createRelocationReferences(const Elf_Sym &symbol,
+                                          ArrayRef<uint8_t> symContent,
+                                          ArrayRef<uint8_t> secContent,
+                                          range<Elf_Rel_Iter> rels);
 
   /// \brief After all the Atoms and References are created, update each
   /// Reference's target with the Atom pointer it refers to.
   virtual void updateReferences();
 
   /// \brief Return true if the symbol is corresponding to an architecture
   /// specific section. We will let the TargetHandler handle such atoms.
   virtual bool isTargetSpecificAtom(const Elf_Shdr *shdr, const Elf_Sym *sym);
for (auto si = symbols.begin(), se = symbols.end(); si != se; ++si) {
       // Create an anonymous atom to hold the data.
       ELFDefinedAtom<ELFT> *anonAtom = nullptr;
       anonFollowedBy = nullptr;
       if (symbol->getBinding() == llvm::ELF::STB_WEAK && contentSize != 0) {
         // Create anonymous new non-weak ELF symbol that holds the symbol
         // data.
         auto sym = new (_readerStorage) Elf_Sym(*symbol);
         sym->setBinding(llvm::ELF::STB_GLOBAL);
-        anonAtom = createDefinedAtomAndAssignRelocations("", *sectionName, sym,
-                                                         section, symbolData);
+        anonAtom = createDefinedAtomAndAssignRelocations(
+            "", *sectionName, sym, section, symbolData, *sectionContents);
         anonAtom->setOrdinal(++_ordinal);
         symbolData = ArrayRef<uint8_t>();
 
         // If this is the last atom, let's not create a followon reference.
         if (anonAtom && (si + 1) != se) {
           anonFollowedBy = new (_readerStorage)
               ELFReference<ELFT>(lld::Reference::kindLayoutAfter);
           anonAtom->addReference(anonFollowedBy);
         }
       }
 
       ELFDefinedAtom<ELFT> *newAtom = createDefinedAtomAndAssignRelocations(
-          symbolName, *sectionName, &*symbol, section, symbolData);
+          symbolName, *sectionName, &*symbol, section, symbolData,
+          *sectionContents);
       newAtom->setOrdinal(++_ordinal);
 
       // If the atom was a weak symbol, let's create a followon reference to
       // the anonymous atom that we created.
       if (anonAtom)
         createEdge(newAtom, anonAtom, Reference::kindLayoutAfter);
 
       if (previousAtom) {
template <class ELFT> error_code ELFFile<ELFT>::createAtoms() {
 
   updateReferences();
   return error_code::success();
 }
 
 template <class ELFT>
 ELFDefinedAtom<ELFT> *ELFFile<ELFT>::createDefinedAtomAndAssignRelocations(
     StringRef symbolName, StringRef sectionName, const Elf_Sym *symbol,
-    const Elf_Shdr *section, ArrayRef<uint8_t> content) {
+    const Elf_Shdr *section, ArrayRef<uint8_t> symContent,
+    ArrayRef<uint8_t> secContent) {
   unsigned int referenceStart = _references.size();
 
-  // Only relocations that are inside the domain of the atom are added.
-
   // Add Rela (those with r_addend) references:
   auto rari = _relocationAddendReferences.find(sectionName);
-  if (rari != _relocationAddendReferences.end()) {
-    for (const Elf_Rela &rai : rari->second) {
-      if (symbol->st_value <= rai.r_offset &&
-          rai.r_offset < symbol->st_value + content.size())
-        _references.push_back(createRelocationReference(*symbol, rai));
-    }
-  }
+  if (rari != _relocationAddendReferences.end())
+    createRelocationReferences(*symbol, symContent, rari->second);
 
   // Add Rel references.
   auto rri = _relocationReferences.find(sectionName);
-  if (rri != _relocationReferences.end()) {
-    for (const Elf_Rel &ri : rri->second) {
-      if (symbol->st_value <= ri.r_offset &&
-          ri.r_offset < symbol->st_value + content.size())
-        _references.push_back(createRelocationReference(*symbol, ri, content));
-    }
-  }
+  if (rri != _relocationReferences.end())
+    createRelocationReferences(*symbol, symContent, secContent, rri->second);
 
   // Create the DefinedAtom and add it to the list of DefinedAtoms.
-  return *handleDefinedSymbol(symbolName, sectionName, symbol, section, content,
-                              referenceStart, _references.size(), _references);
+  return *handleDefinedSymbol(symbolName, sectionName, symbol, section,
+                              symContent, referenceStart, _references.size(),
+                              _references);
 }
 
 template <class ELFT>
-ELFReference<ELFT> *
-ELFFile<ELFT>::createRelocationReference(const Elf_Sym &symbol,
-                                         const Elf_Rela &rai) {
+void ELFFile<ELFT>::createRelocationReferences(const Elf_Sym &symbol,
+                                               ArrayRef<uint8_t> content,
+                                               range<Elf_Rela_Iter> rels) {
   bool isMips64EL = _objFile->isMips64EL();
-  return new (_readerStorage)
-      ELFReference<ELFT>(&rai, rai.r_offset - symbol.st_value, kindArch(),
-                         rai.getType(isMips64EL), rai.getSymbol(isMips64EL));
+  for (const auto &rel : rels) {
+    if (rel.r_offset < symbol.st_value ||
+        symbol.st_value + content.size() <= rel.r_offset)
+      continue;
+    _references.push_back(new (_readerStorage) ELFReference<ELFT>(
+        &rel, rel.r_offset - symbol.st_value, kindArch(),
+        rel.getType(isMips64EL), rel.getSymbol(isMips64EL)));
+  }
 }
 
 template <class ELFT>
-ELFReference<ELFT> *ELFFile<ELFT>::createRelocationReference(
-    const Elf_Sym &symbol, const Elf_Rel &ri, ArrayRef<uint8_t> content) {
+void ELFFile<ELFT>::createRelocationReferences(const Elf_Sym &symbol,
+                                               ArrayRef<uint8_t> symContent,
+                                               ArrayRef<uint8_t> secContent,
+                                               range<Elf_Rel_Iter> rels) {
   bool isMips64EL = _objFile->isMips64EL();
-  auto *ref = new (_readerStorage)
-      ELFReference<ELFT>(&ri, ri.r_offset - symbol.st_value, kindArch(),
-                         ri.getType(isMips64EL), ri.getSymbol(isMips64EL));
-  int32_t addend = *(content.data() + ri.r_offset - symbol.st_value);
-  ref->setAddend(addend);
-  return ref;
+  for (const auto &rel : rels) {
+    if (rel.r_offset < symbol.st_value ||
+        symbol.st_value + symContent.size() <= rel.r_offset)
+      continue;
+    _references.push_back(new (_readerStorage) ELFReference<ELFT>(
+        &rel, rel.r_offset - symbol.st_value, kindArch(),
+        rel.getType(isMips64EL), rel.getSymbol(isMips64EL)));
+    int32_t addend = *(symContent.data() + rel.r_offset - symbol.st_value);
+    _references.back()->setAddend(addend);
+  }
 }
 
 template <class ELFT>
 int64_t ELFFile<ELFT>::defaultRelocAddend(const Reference &) const {
   return 0;
 }
 
 template <class ELFT> void ELFFile<ELFT>::updateReferences() {

lib/ReaderWriter/ELF/Mips/MipsELFFile.h

public:
   bool isPIC() const {
     return this->_objFile->getHeader()->e_flags & llvm::ELF::EF_MIPS_PIC;
   }
 
 private:
   typedef llvm::object::Elf_Sym_Impl<ELFT> Elf_Sym;
   typedef llvm::object::Elf_Shdr_Impl<ELFT> Elf_Shdr;
   typedef llvm::object::Elf_Rel_Impl<ELFT, false> Elf_Rel;
+  typedef typename llvm::object::ELFFile<ELFT>::Elf_Rel_Iter Elf_Rel_Iter;
 
   ErrorOr<ELFDefinedAtom<ELFT> *> handleDefinedSymbol(
       StringRef symName, StringRef sectionName, const Elf_Sym *sym,
       const Elf_Shdr *sectionHdr, ArrayRef<uint8_t> contentData,
       unsigned int referenceStart, unsigned int referenceEnd,
       std::vector<ELFReference<ELFT> *> &referenceList) override {
     return new (this->_readerStorage) MipsELFDefinedAtom<ELFT>(
         *this, symName, sectionName, sym, sectionHdr, contentData,
         referenceStart, referenceEnd, referenceList);
   }
 
-  ELFReference<ELFT> *
-  createRelocationReference(const Elf_Sym &symbol, const Elf_Rel &ri,
-                            ArrayRef<uint8_t> content) override {
-    bool isMips64EL = this->_objFile->isMips64EL();
-    auto *ref = new (this->_readerStorage)
-        ELFReference<ELFT>(&ri, ri.r_offset - symbol.st_value, this->kindArch(),
-                           ri.getType(isMips64EL), ri.getSymbol(isMips64EL));
-    ref->setAddend(readAddend(symbol, ri, content));
-    return ref;
+  void createRelocationReferences(const Elf_Sym &symbol,
+                                  ArrayRef<uint8_t> symContent,
+                                  ArrayRef<uint8_t> secContent,
+                                  range<Elf_Rel_Iter> rels) override {
+    for (Elf_Rel_Iter rit = rels.begin(), eit = rels.end(); rit != eit; ++rit) {
+      if (rit->r_offset < symbol.st_value ||
+          symbol.st_value + symContent.size() <= rit->r_offset)
+        continue;
+
+      this->_references.push_back(new (this->_readerStorage) ELFReference<ELFT>(
+          &*rit, rit->r_offset - symbol.st_value, this->kindArch(),
+          rit->getType(isMips64EL()), rit->getSymbol(isMips64EL())));
+
+      auto addend = readAddend(*rit, secContent);
+      if (needsMatchingRelocation(*rit)) {
+        auto mit = findMatchingRelocation(rit, eit);
+        // FIXME (simon): Handle this condition in a more user friendly way.
+        assert(mit != eit && "There is no paired R_MIPS_LO16 relocation");
+        auto matchingAddend = readAddend(*mit, secContent);
+        addend = (addend << 16) + int16_t(matchingAddend);
+      }
+      this->_references.back()->setAddend(addend);
+    }
   }
 
-  Reference::Addend readAddend(const Elf_Sym &symbol, const Elf_Rel &ri,
-                               ArrayRef<uint8_t> content) const {
-    const uint8_t *ap = content.data() + ri.r_offset - symbol.st_value;
-    switch (ri.getType(this->_objFile->isMips64EL())) {
+  Reference::Addend readAddend(const Elf_Rel &ri,
+                               const ArrayRef<uint8_t> content) const {
+    const uint8_t *ap = content.data() + ri.r_offset;
+    switch (ri.getType(isMips64EL())) {
     case llvm::ELF::R_MIPS_32:
     case llvm::ELF::R_MIPS_PC32:
       return *(int32_t *)ap;
     case llvm::ELF::R_MIPS_26:
       return *(int32_t *)ap & 0x3ffffff;
     case llvm::ELF::R_MIPS_HI16:
     case llvm::ELF::R_MIPS_LO16:
     case llvm::ELF::R_MIPS_GOT16:
       return *(int16_t *)ap;
     default:
       return 0;
     }
   }
+
+  bool needsMatchingRelocation(const Elf_Rel &rel) {
+    auto rType = rel.getType(isMips64EL());
+    if (rType == llvm::ELF::R_MIPS_HI16)
+      return true;
+    if (rType == llvm::ELF::R_MIPS_GOT16) {
+      const Elf_Sym *symbol =
+          this->_objFile->getSymbol(rel.getSymbol(isMips64EL()));
+      return symbol->getBinding() == llvm::ELF::STB_LOCAL;
+    }
+    return false;
+  }
+
+  Elf_Rel_Iter findMatchingRelocation(Elf_Rel_Iter rit, Elf_Rel_Iter eit) {
+    return std::find_if(rit, eit, [&](const Elf_Rel &rel) {
+      return rel.getType(isMips64EL()) == llvm::ELF::R_MIPS_LO16 &&
+             rel.getSymbol(isMips64EL()) == rit->getSymbol(isMips64EL());
+    });
+  }
+
+  bool isMips64EL() const { return this->_objFile->isMips64EL(); }
 };
 
 } // elf
 } // lld
 
 #endif

lib/ReaderWriter/ELF/Mips/MipsRelocationPass.cpp

private:
   std::vector<ObjectAtom *> _objectVector;
 
   /// \brief the list of LA25 entries.
   std::vector<LA25Atom *> _la25Vector;
 
   /// \brief Handle a specific reference.
   void handleReference(Reference &ref);
 
-  /// \brief Calculate AHL addendums for the atom's references.
-  void calculateAHLs(const DefinedAtom &atom);
-
   void handlePlain(Reference &ref);
   void handlePLT(Reference &ref);
   void handleGOT(Reference &ref);
 
   const GOTAtom *getLocalGOTEntry(const Reference &ref);
   const GOTAtom *getGlobalGOTEntry(const Atom *a);
   const PLTAtom *getPLTEntry(const Atom *a);
   const LA25Atom *getLA25Entry(const Atom *a);
RelocationPass<ELFT>::RelocationPass(MipsLinkingContext &context)
     : _context(context), _file(context) {
   _localGotVector.push_back(new (_file._alloc) GOT0Atom(_file));
   _localGotVector.push_back(new (_file._alloc) GOTModulePointerAtom(_file));
 }
 
 template <typename ELFT>
 void RelocationPass<ELFT>::perform(std::unique_ptr<MutableFile> &mf) {
   // Process all references.
-  for (const auto &atom : mf->defined()) {
-    calculateAHLs(*atom);
+  for (const auto &atom : mf->defined())
     for (const auto &ref : *atom)
       handleReference(const_cast<Reference &>(*ref));
-  }
 
   uint64_t ordinal = 0;
 
   for (auto &got : _localGotVector) {
     DEBUG_WITH_TYPE("MipsGOT", llvm::dbgs() << "[ GOT ] Adding L "
                                             << got->name() << "\n");
     got->setOrdinal(ordinal++);
     mf->addAtom(*got);
void RelocationPass<ELFT>::perform(std::unique_ptr<MutableFile> &mf) {
   }
 
   for (auto la25 : _la25Vector) {
     la25->setOrdinal(ordinal++);
     mf->addAtom(*la25);
   }
 }
 
-/// \brief Calculate AHL value combines addends from 'hi' and 'lo' relocations.
-inline int64_t calcAHL(int64_t AHI, int64_t ALO) {
-  AHI &= 0xffff;
-  ALO &= 0xffff;
-  return (AHI << 16) + (int16_t)ALO;
-}
-
-template <typename ELFT>
-void RelocationPass<ELFT>::calculateAHLs(const DefinedAtom &atom) {
-  std::vector<const Reference *> lo16Refs;
-  std::vector<Reference *> hi16Refs;
-  for (const auto &ref : atom) {
-    if (ref->kindNamespace() != lld::Reference::KindNamespace::ELF)
-      continue;
-    assert(ref->kindArch() == Reference::KindArch::Mips);
-    switch (ref->kindValue()) {
-    case R_MIPS_HI16:
-      hi16Refs.push_back(const_cast<Reference *>(ref));
-    case R_MIPS_LO16:
-      lo16Refs.push_back(ref);
-      break;
-    case R_MIPS_GOT16:
-      if (isLocal(ref->target()))
-        hi16Refs.push_back(const_cast<Reference *>(ref));
-      break;
-    }
-  }
-
-  std::sort(lo16Refs.begin(), lo16Refs.end(),
-            [](const Reference *a, const Reference *b) {
-    return a->offsetInAtom() < b->offsetInAtom();
-  });
-  std::sort(hi16Refs.begin(), hi16Refs.end(),
-            [](const Reference *a, const Reference *b) {
-    return a->offsetInAtom() < b->offsetInAtom();
-  });
-
-  // Iterate over R_MIPS_LO16 relocations sorted by theirs offsets in the atom.
-  // Calculate AHL addend for each R_MIPS_HI16 amd R_MIPS_GOT16 relocation
-  // precedes the current R_MIPS_LO16 one.
-
-  auto hic = hi16Refs.begin();
-  for (const auto &lo : lo16Refs) {
-    for (; hic != hi16Refs.end(); ++hic) {
-      if ((*hic)->offsetInAtom() > lo->offsetInAtom())
-        break;
-      (*hic)->setAddend(calcAHL((*hic)->addend(), lo->addend()));
-    }
-  }
-  assert(hic == hi16Refs.end());
-}
-
 template <typename ELFT>
 void RelocationPass<ELFT>::handleReference(Reference &ref) {
   if (ref.kindNamespace() != lld::Reference::KindNamespace::ELF)
     return;
   assert(ref.kindArch() == Reference::KindArch::Mips);
   switch (ref.kindValue()) {
   case R_MIPS_32:
   case R_MIPS_PC32:

test/elf/Mips/hilo16-4.test

-# Check handling HI16/LO16 relocations go in mixed order.
-#
-# RUN: llvm-mc -triple=mipsel -filetype=obj -o=%t-obj %s
-# RUN: lld -flavor gnu -target mipsel -e A -o %t-exe %t-obj
+# Check pairing of R_MIPS_HI16 and R_MIPS_LO16 relocations.
+# RUN: yaml2obj -format=elf %s > %t-obj
+# RUN: lld -flavor gnu -target mipsel -e glob1 -o %t-exe %t-obj
 # RUN: llvm-objdump -t -disassemble %t-exe | FileCheck %s
 
 # CHECK: Disassembly of section .text:
-# CHECK: A:
-# CHECK-NEXT: 400128:  42 00 08 3c  lui  $8, 66
-# CHECK-NEXT: 40012c:  40 00 08 3c  lui  $8, 64
-# CHECK-NEXT: 400130:  28 01 08 85  lh   $8, 296($8)
-# CHECK-NEXT: 400134:  38 01 08 85  lh   $8, 312($8)
-
-# CHECK: B:
-# CHECK-NEXT: 400138:  42 00 08 3c  lui  $8, 66
-# CHECK-NEXT: 40013c:  40 00 08 3c  lui  $8, 64
-# CHECK-NEXT: 400140:  38 01 08 85  lh   $8, 312($8)
-# CHECK-NEXT: 400144:  28 01 08 85  lh   $8, 296($8)
+# CHECK: glob1:
+# CHECK-NEXT:  400140:  40 00 04 3c  lui  $4, 64
+# CHECK-NEXT:  400144:  ff 9f a6 8c  lw   $6, -24577($5)
+
+# CHECK: glob2:
+# CHECK-NEXT:  400148:  00 20 c7 80  lb   $7, 8192($6)
+# CHECK-NEXT:  40014c:  04 20 c8 80  lb   $8, 8196($6)
+
+# CHECK: glob3:
+# CHECK-NEXT:  400150:  40 80 05 3c  lui  $5, 32832
 
 # CHECK: SYMBOL TABLE:
-# CHECK: 00400128 g F .text  00000010 A
-# CHECK: 00400138 g F .text  00000010 B
+# CHECK: 00400140 g     F .text  00000008 glob1
+# CHECK: 00400148 g     F .text  00000008 glob2
+# CHECK: 00400150 g     F .text  00000004 glob3
+# CHECK: 00402000 g       .data  0000000c X
+
+!ELF
+FileHeader: !FileHeader
+  Class: ELFCLASS32
+  Data: ELFDATA2LSB
+  Type: ET_REL
+  Machine: EM_MIPS
+
+Sections:
+- Name: .text
+  Type: SHT_PROGBITS
+# glob1:
+# lui     $4,%hi(X)             # rel A
+# lw      $6,%lo(X+32767)($5)   # rel B
+# glob2:
+# lb      $7,%lo(X)($6)         # rel C
+# lb      $8,%lo(X+4)($6)       # rel D
+# glob3:
+# lui     $5,%hi(X+32767)       # rel E
+  Content:  "0000043CFF7FA68C0000C7800400C880FF7F053C"
+  AddressAlign: 16
+  Flags: [SHF_EXECINSTR, SHF_ALLOC]
+
+- Name: .data
+  Type: SHT_PROGBITS
+  Content:  "000000000000000000000000"
+  AddressAlign: 16
+  Flags: [SHF_WRITE, SHF_ALLOC]
+
+- Name: .rel.text
+  Type: SHT_REL
+  Info: .text
+  AddressAlign: 4
+  Relocations:
+    - Offset: 0x10          # rel E
+      Symbol: X
+      Type: R_MIPS_HI16
+    - Offset: 0x04          # rel B
+      Symbol: X
+      Type: R_MIPS_LO16
+    - Offset: 0x00          # rel A
+      Symbol: X
+      Type: R_MIPS_HI16
+    - Offset: 0x0C          # rel D
+      Symbol: X
+      Type: R_MIPS_LO16
+    - Offset: 0x08          # rel C
+      Symbol: X
+      Type: R_MIPS_LO16
 
-    .global A
-    .ent    A
-A:
-    lui     $t0,%hi(A+0x1ffff)
-    lui     $t0,%hi(B)
-    lh      $t0,%lo(A)($t0)
-    lh      $t0,%lo(B)($t0)
-    .end    A
-
-    .global B
-    .ent    B
-B:
-    lui     $t0,%hi(A+0x1ffff)
-    lui     $t0,%hi(B)
-    lh      $t0,%lo(B)($t0)
-    lh      $t0,%lo(A)($t0)
-    .end    B
+Symbols:
+  Global:
+    - Name: glob1
+      Section: .text
+      Value: 0x0
+      Size: 8
+    - Name: glob2
+      Section: .text
+      Value: 0x8
+      Size: 8
+    - Name: glob3
+      Section: .text
+      Value: 0x10
+      Size: 4
+    - Name: X
+      Section: .data
+      Value: 0x0
+      Size: 12