[LLD] Add support for multiple segments with same name

[zatrazz]

Summary

This patch fixes lld wrong relocation for objects with multiples segments
with same name (mostly due C++ EH cases for COMDAT group sections).

The issue is due the mapping from segments to relocation only the segment's
name is considered. So for cases where the object file constains more than
one segment with same name (.text for instance), some segments relocations
are complete ignored.

The patch changes this by considering the segment index references in the
group section while creating the mapping. It also adds a small optimization
on handleSectionGroup by avoiding using the string name, but rather the segment
header in the sections mapping (it should be no code generation changes for
this change).

With this change I could see no more failures with SingleSource for x86_64
and only TLS one for aarch64 (which currently misses TLS handling in
backend). I will still creating testcases, since it will require changes
for yaml2obj and obj2yaml to correct parse and create objects with multiple
segment of the same name.

[• shankar.easwaran]

Lgtm

[ruiu]

Please add a test.

[zatrazz]

The testcase is my next step, but I need first to add support for multiple segments with same on yam2obj and obj2yaml tools before being able to correct add a testcase. Should I hold this patch until I finish the support for the tools?

[ruiu]

Yeah, it's probably better to check in a patch with a test unless it's
urgent.

[• rafael]

You can trivially create the files you need with llvm-mc. You can also
check in binaries.

lib/ReaderWriter/ELF/ELFFile.h

 //===- lib/ReaderWriter/ELF/ELFFile.h -------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_READER_WRITER_ELF_FILE_H
 #define LLD_READER_WRITER_ELF_FILE_H
 
 #include "Atoms.h"
 #include "FileCommon.h"
 #include "llvm/ADT/MapVector.h"
+#include "llvm/ADT/StringExtras.h"
 #include <map>
 #include <unordered_map>
 
 namespace lld {
 
 namespace elf {
 /// \brief Read a binary, find out based on the symbol table contents what kind
 /// of symbol it is and create corresponding atoms for it
public:
   // However, if an atom is in a section group, we may want to return an
   // undefined atom for targetSym to let the resolver to resolve the
   // symbol. (It's because if targetSym is in a section group A, and the
   // group A is not linked in because other file already provides a
   // section group B, we want to resolve references to B, not to A.)
   Atom *findAtom(const Elf_Sym *sourceSym, const Elf_Sym *targetSym);
 
 protected:
+  typedef llvm::DenseMap<const Elf_Shdr *, std::vector<ELFDefinedAtom<ELFT> *>>
+    AtomsForSectionMap;
+
   ELFDefinedAtom<ELFT> *createDefinedAtomAndAssignRelocations(
       StringRef symbolName, StringRef sectionName, const Elf_Sym *symbol,
-      const Elf_Shdr *section, ArrayRef<uint8_t> symContent,
+      const Elf_Shdr *sectionHdr, int sectionIdx, ArrayRef<uint8_t> symContent,
       ArrayRef<uint8_t> secContent);
 
   std::error_code doParse() override;
 
   /// \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);
protected:
   bool handleSectionWithNoSymbols(const Elf_Shdr *shdr,
                                   std::vector<Elf_Sym_Iter> &syms) const {
     return shdr && (shdr->sh_type == llvm::ELF::SHT_PROGBITS) && syms.empty();
   }
 
   /// Handle creation of atoms for .gnu.linkonce sections.
   std::error_code handleGnuLinkOnceSection(
       const Elf_Shdr *section,
-      llvm::StringMap<std::vector<ELFDefinedAtom<ELFT> *>> &atomsForSection);
+      AtomsForSectionMap &atomsForSection);
 
   // Handle COMDAT scetions.
   std::error_code handleSectionGroup(
       const Elf_Shdr *section,
-      llvm::StringMap<std::vector<ELFDefinedAtom<ELFT> *>> &atomsForSection);
+      AtomsForSectionMap &atomsForSection);
 
   /// Process the Undefined symbol and create an atom for it.
   ELFUndefinedAtom<ELFT> *createUndefinedAtom(StringRef symName,
                                               const Elf_Sym *sym) {
     return new (_readerStorage) ELFUndefinedAtom<ELFT>(*this, symName, sym);
   }
 
   /// Returns true if the symbol is a absolute symbol.
protected:
 
   const Elf_Sym *findSymbolForReference(const ELFReference<ELFT> *r) const {
     auto elfReferenceToSymbol = _referenceToSymbol.find(r);
     if (elfReferenceToSymbol != _referenceToSymbol.end())
       return elfReferenceToSymbol->second;
     return nullptr;
   }
 
+  std::string createSectionKeyWithIndex(StringRef sectionName,
+                                        const Elf_Shdr *section, uint32_t idx) {
+    std::string sectionKey = sectionName;
+    if (isSectionMemberOfGroup(section))
+      sectionKey += llvm::utohexstr(idx);
+    return sectionKey;
+  }
+
+  std::string createSectionKey(StringRef sectionName, const Elf_Shdr *section) {
+    return createSectionKeyWithIndex(sectionName, section, section->sh_info);
+  }
+
   llvm::BumpPtrAllocator _readerStorage;
   std::unique_ptr<llvm::object::ELFFile<ELFT> > _objFile;
 
   /// \brief _relocationAddendReferences and _relocationReferences contain the
   /// list of relocations references.  In ELF, if a section named, ".text" has
   /// relocations will also have a section named ".rel.text" or ".rela.text"
   /// which will hold the entries.
-  std::unordered_map<StringRef, range<Elf_Rela_Iter>>
+  std::unordered_map<std::string, range<Elf_Rela_Iter>>
     _relocationAddendReferences;
+  std::unordered_map<std::string, range<Elf_Rel_Iter>>
+    _relocationReferences;
   MergedSectionMapT _mergedSectionMap;
-  std::unordered_map<StringRef, range<Elf_Rel_Iter>> _relocationReferences;
   std::vector<ELFReference<ELFT> *> _references;
   llvm::DenseMap<const Elf_Sym *, Atom *> _symbolToAtomMapping;
   llvm::DenseMap<const ELFReference<ELFT> *, const Elf_Sym *>
   _referenceToSymbol;
   // Group child atoms have a pair corresponding to the signature and the
   // section header of the section that was used for generating the signature.
   llvm::DenseMap<const Elf_Sym *, std::pair<StringRef, const Elf_Shdr *>>
       _groupChild;
   llvm::StringMap<Atom *> _undefAtomsForGroupChild;
 
   /// \brief Atoms that are created for a section that has the merge property
   /// set
   MergeAtomsT _mergeAtoms;
 
   /// \brief the section and the symbols that are contained within it to create
-  /// used to create atoms
-  llvm::MapVector<const Elf_Shdr *, std::vector<Elf_Sym_Iter>> _sectionSymbols;
+  /// used to create atoms.  Each segment header maps to a pair made of
+  /// its index and the symbols it contains
+  llvm::MapVector<const Elf_Shdr *, 
+    std::pair<uint32_t, std::vector<Elf_Sym_Iter>>> _sectionSymbols;
 
   /// \brief Sections that have merge string property
   std::vector<const Elf_Shdr *> _mergeStringSections;
 
   std::unique_ptr<MemoryBuffer> _mb;
   int64_t _ordinal;
 
   /// \brief the cached options relevant while reading the ELF File

lib/ReaderWriter/ELF/ELFFile.cpp

 
 template <class ELFT>
 std::error_code ELFFile<ELFT>::createAtomizableSections() {
   // Handle: SHT_REL and SHT_RELA sections:
   // Increment over the sections, when REL/RELA section types are found add
   // the contents to the RelocationReferences map.
   // Record the number of relocs to guess at preallocating the buffer.
   uint64_t totalRelocs = 0;
-  for (const Elf_Shdr &section : _objFile->sections()) {
+  uint32_t idx = 0;
+  //for (const Elf_Shdr &section : _objFile->sections()) {
+  auto it = _objFile->begin_sections();
+  auto ite = _objFile->end_sections();
+  for (; it != ite; ++it, ++idx) {
+    const Elf_Shdr &section = *it;
+ 
     if (isIgnoredSection(&section))
       continue;
 
     if (isMergeableStringSection(&section)) {
       _mergeStringSections.push_back(&section);
       continue;
     }
 
     if (section.sh_type == llvm::ELF::SHT_RELA) {
       auto sHdr = _objFile->getSection(section.sh_info);
 
       auto sectionName = _objFile->getSectionName(sHdr);
       if (std::error_code ec = sectionName.getError())
         return ec;
 
       auto rai(_objFile->begin_rela(&section));
       auto rae(_objFile->end_rela(&section));
 
-      _relocationAddendReferences[*sectionName] = make_range(rai, rae);
+      std::string sectionKey = createSectionKey(*sectionName, &section);
+      _relocationAddendReferences[sectionKey] = make_range(rai, rae);
+
       totalRelocs += std::distance(rai, rae);
     } else if (section.sh_type == llvm::ELF::SHT_REL) {
       auto sHdr = _objFile->getSection(section.sh_info);
 
       auto sectionName = _objFile->getSectionName(sHdr);
       if (std::error_code ec = sectionName.getError())
         return ec;
 
       auto ri(_objFile->begin_rel(&section));
       auto re(_objFile->end_rel(&section));
 
-      _relocationReferences[*sectionName] = make_range(ri, re);
+      std::string sectionKey = createSectionKey(*sectionName, &section);
+      _relocationReferences[sectionKey] = make_range(ri, re);
+
       totalRelocs += std::distance(ri, re);
     } else {
-      _sectionSymbols[&section];
+      _sectionSymbols[&section] = std::make_pair(idx, std::vector<Elf_Sym_Iter>());
     }
   }
   _references.reserve(totalRelocs);
   return std::error_code();
 }
 
 template <class ELFT> std::error_code ELFFile<ELFT>::createMergeableAtoms() {
   // Divide the section that contains mergeable strings into tokens
if (isAbsoluteSymbol(&*SymI)) {
       addAtom(*undefAtom);
       _symbolToAtomMapping.insert(std::make_pair(&*SymI, undefAtom));
     } else if (isCommonSymbol(&*SymI)) {
       ELFCommonAtom<ELFT> *commonAtom = createCommonAtom(*symbolName, &*SymI);
       commonAtom->setOrdinal(++_ordinal);
       addAtom(*commonAtom);
       _symbolToAtomMapping.insert(std::make_pair(&*SymI, commonAtom));
     } else if (isDefinedSymbol(&*SymI)) {
-      _sectionSymbols[section].push_back(SymI);
+      _sectionSymbols[section].second.push_back(SymI);
     } else {
       llvm::errs() << "Unable to create atom for: " << *symbolName << "\n";
       return llvm::object::object_error::parse_failed;
     }
   }
 
   return std::error_code();
 }
 
 template <class ELFT> std::error_code ELFFile<ELFT>::createAtoms() {
   // Holds all the atoms that are part of the section. They are the targets of
   // the kindGroupChild reference.
-  llvm::StringMap<std::vector<ELFDefinedAtom<ELFT> *>> atomsForSection;
+  AtomsForSectionMap atomsForSection;
 
-  // Contains a list of comdat sections for a group.
+  // Contains a list of comdat sections for a group.  The sectionIdx is used
+  // to keep track of section ordering to match group section in the References
+  // match when creating ElfDefineAtom.
   for (auto &i : _sectionSymbols) {
     const Elf_Shdr *section = i.first;
-    std::vector<Elf_Sym_Iter> &symbols = i.second;
+    uint32_t sectionIdx = i.second.first;
+    std::vector<Elf_Sym_Iter> &symbols = i.second.second;
 
     // Sort symbols by position.
     std::stable_sort(symbols.begin(), symbols.end(),
                      [this](Elf_Sym_Iter a, Elf_Sym_Iter b) {
                        return getSymbolValue(&*a) < getSymbolValue(&*b);
                      });
 
     ErrorOr<StringRef> sectionName = this->getSectionName(section);
for (auto &i : _sectionSymbols) {
 
     if (handleSectionWithNoSymbols(section, symbols)) {
       ELFDefinedAtom<ELFT> *newAtom =
           createSectionAtom(section, *sectionName, *sectionContents);
       newAtom->setOrdinal(++_ordinal);
       if (addAtoms)
         addAtom(*newAtom);
       else
-        atomsForSection[*sectionName].push_back(newAtom);
+        atomsForSection[section].push_back(newAtom);
       continue;
     }
 
     ELFDefinedAtom<ELFT> *previousAtom = nullptr;
     ELFReference<ELFT> *anonFollowedBy = nullptr;
 
     for (auto si = symbols.begin(), se = symbols.end(); si != se; ++si) {
       auto symbol = *si;
for (auto si = symbols.begin(), se = symbols.end(); si != se; ++si) {
           continue;
         ELFDefinedAtom<ELFT> *atom = createDefinedAtom(
             symbolName, *sectionName, &**si, section, symbolData,
             _references.size(), _references.size(), _references);
         atom->setOrdinal(++_ordinal);
         if (addAtoms)
           addAtom(*atom);
         else
-          atomsForSection[*sectionName].push_back(atom);
+          atomsForSection[section].push_back(atom);
         continue;
       }
 
       // Don't allocate content to a weak symbol, as they may be merged away.
       // Create an anonymous atom to hold the data.
       ELFDefinedAtom<ELFT> *anonAtom = nullptr;
       anonFollowedBy = nullptr;
       if (symbol->getBinding() == llvm::ELF::STB_WEAK) {
         // 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, *sectionContents);
+            "", *sectionName, sym, section, sectionIdx, symbolData, *sectionContents);
         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>(Reference::kindLayoutAfter);
           anonAtom->addReference(anonFollowedBy);
         }
       }
 
       ELFDefinedAtom<ELFT> *newAtom = createDefinedAtomAndAssignRelocations(
-          symbolName, *sectionName, &*symbol, section, symbolData,
+          symbolName, *sectionName, &*symbol, section, sectionIdx, 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) {
         // Set the followon atom to the weak atom that we have created, so
         // that they would alias when the file gets written.
         followOn->setTarget(anonAtom ? anonAtom : newAtom);
       }
 
       // The previous atom is always the atom created before unless the atom
       // is a weak atom.
       previousAtom = anonAtom ? anonAtom : newAtom;
 
       if (addAtoms)
         addAtom(*newAtom);
       else
-        atomsForSection[*sectionName].push_back(newAtom);
+        atomsForSection[section].push_back(newAtom);
 
       _symbolToAtomMapping.insert(std::make_pair(&*symbol, newAtom));
       if (anonAtom) {
         anonAtom->setOrdinal(++_ordinal);
         if (addAtoms)
           addAtom(*anonAtom);
         else
-          atomsForSection[*sectionName].push_back(anonAtom);
+          atomsForSection[section].push_back(anonAtom);
       }
     }
   }
 
   for (auto &i : _sectionSymbols)
     if (std::error_code ec = handleSectionGroup(i.first, atomsForSection))
       return ec;
   for (auto &i : _sectionSymbols)
     if (std::error_code ec = handleGnuLinkOnceSection(i.first, atomsForSection))
       return ec;
 
   updateReferences();
   return std::error_code();
 }
 
 template <class ELFT>
 std::error_code ELFFile<ELFT>::handleGnuLinkOnceSection(
     const Elf_Shdr *section,
-    llvm::StringMap<std::vector<ELFDefinedAtom<ELFT> *>> &atomsForSection) {
+    AtomsForSectionMap &atomsForSection) {
   ErrorOr<StringRef> sectionName = this->getSectionName(section);
   if (std::error_code ec = sectionName.getError())
     return ec;
   if (!isGnuLinkOnceSection(*sectionName))
     return std::error_code();
 
   unsigned int referenceStart = _references.size();
   std::vector<ELFReference<ELFT> *> refs;
-  for (auto ha : atomsForSection[*sectionName]) {
+  for (auto ha : atomsForSection[section]) {
     _groupChild[ha->symbol()] = std::make_pair(*sectionName, section);
     ELFReference<ELFT> *ref =
         new (_readerStorage) ELFReference<ELFT>(Reference::kindGroupChild);
     ref->setTarget(ha);
     refs.push_back(ref);
   }
-  atomsForSection[*sectionName].clear();
+  atomsForSection[section].clear();
   // Create a gnu linkonce atom.
   ELFDefinedAtom<ELFT> *atom = createDefinedAtom(
       *sectionName, *sectionName, nullptr, section, ArrayRef<uint8_t>(),
       referenceStart, _references.size(), _references);
   atom->setOrdinal(++_ordinal);
   addAtom(*atom);
   for (auto reference : refs)
     atom->addReference(reference);
   return std::error_code();
 }
 
 template <class ELFT>
 std::error_code ELFFile<ELFT>::handleSectionGroup(
     const Elf_Shdr *section,
-    llvm::StringMap<std::vector<ELFDefinedAtom<ELFT> *>> &atomsForSection) {
+    AtomsForSectionMap &atomsForSection) {
   ErrorOr<StringRef> sectionName = this->getSectionName(section);
   if (std::error_code ec = sectionName.getError())
     return ec;
   if (!isGroupSection(section))
     return std::error_code();
 
   auto sectionContents = getSectionContents(section);
   if (std::error_code ec = sectionContents.getError())
     return ec;
 
   // A section of type SHT_GROUP defines a grouping of sections. The
   // name of a symbol from one of the containing object's symbol tables
   // provides a signature for the section group. The section header of
   // the SHT_GROUP section specifies the identifying symbol entry, as
   // described: the sh_link member contains the section header index of
   // the symbol table section that contains the entry. The sh_info
   // member contains the symbol table index of the identifying entry.
   // The sh_flags member of the section header contains 0. The name of
   // the section (sh_name) is not specified.
-  std::vector<StringRef> sectionNames;
+  std::vector<const Elf_Shdr *> sections;
   const Elf_Word *groupMembers =
       reinterpret_cast<const Elf_Word *>(sectionContents->data());
   const size_t count = section->sh_size / sizeof(Elf_Word);
   for (size_t i = 1; i < count; i++) {
     const Elf_Shdr *shdr = _objFile->getSection(groupMembers[i]);
-    ErrorOr<StringRef> sectionName = _objFile->getSectionName(shdr);
-    if (std::error_code ec = sectionName.getError())
-      return ec;
-    sectionNames.push_back(*sectionName);
+    sections.push_back(shdr);
   }
   const Elf_Sym *symbol = _objFile->getSymbol(section->sh_info);
   const Elf_Shdr *symtab = _objFile->getSection(section->sh_link);
   ErrorOr<StringRef> symbolName = _objFile->getSymbolName(symtab, symbol);
   if (std::error_code ec = symbolName.getError())
     return ec;
 
   unsigned int referenceStart = _references.size();
   std::vector<ELFReference<ELFT> *> refs;
-  for (auto name : sectionNames) {
-    for (auto ha : atomsForSection[name]) {
+  for (auto sec : sections) {
+    for (auto ha : atomsForSection[sec]) {
       _groupChild[ha->symbol()] = std::make_pair(*symbolName, section);
       ELFReference<ELFT> *ref =
           new (_readerStorage) ELFReference<ELFT>(Reference::kindGroupChild);
       ref->setTarget(ha);
       refs.push_back(ref);
     }
-    atomsForSection[name].clear();
+    atomsForSection[sec].clear();
   }
 
   // Create an atom for comdat signature.
   ELFDefinedAtom<ELFT> *atom = createDefinedAtom(
       *symbolName, *sectionName, nullptr, section, ArrayRef<uint8_t>(),
       referenceStart, _references.size(), _references);
   atom->setOrdinal(++_ordinal);
   addAtom(*atom);
for (auto &wrapsym : _ctx.wrapCalls()) {
     addAtom(*wrapCallAtom);
   }
   return std::error_code();
 }
 
 template <class ELFT>
 ELFDefinedAtom<ELFT> *ELFFile<ELFT>::createDefinedAtomAndAssignRelocations(
     StringRef symbolName, StringRef sectionName, const Elf_Sym *symbol,
-    const Elf_Shdr *section, ArrayRef<uint8_t> symContent,
+    const Elf_Shdr *section, int sectionIdx, ArrayRef<uint8_t> symContent,
     ArrayRef<uint8_t> secContent) {
   unsigned int referenceStart = _references.size();
 
+  std::string sectionKey = createSectionKeyWithIndex(sectionName, section,
+                                                     sectionIdx);
+
   // Add Rela (those with r_addend) references:
-  auto rari = _relocationAddendReferences.find(sectionName);
+  auto rari = _relocationAddendReferences.find(sectionKey);
   if (rari != _relocationAddendReferences.end())
     createRelocationReferences(symbol, symContent, rari->second);
 
   // Add Rel references.
-  auto rri = _relocationReferences.find(sectionName);
+  auto rri = _relocationReferences.find(sectionKey);
   if (rri != _relocationReferences.end())
     createRelocationReferences(symbol, symContent, secContent, rri->second);
 
   // Create the DefinedAtom and add it to the list of DefinedAtoms.
   return createDefinedAtom(symbolName, sectionName, symbol, section, symContent,
                            referenceStart, _references.size(), _references);
 }
 
ELFFile<ELFT>::createSectionAtom(const Elf_Shdr *section, StringRef sectionName,
   Elf_Sym *sym = new (_readerStorage) Elf_Sym;
   sym->st_name = 0;
   sym->setBindingAndType(llvm::ELF::STB_LOCAL, llvm::ELF::STT_SECTION);
   sym->st_other = 0;
   sym->st_shndx = 0;
   sym->st_value = 0;
   sym->st_size = 0;
   auto *newAtom = createDefinedAtomAndAssignRelocations(
-      "", sectionName, sym, section, content, content);
+      "", sectionName, sym, section, -1, content, content);
   newAtom->setOrdinal(++_ordinal);
   return newAtom;
 }
 
 template <class ELFT>
 uint64_t ELFFile<ELFT>::symbolContentSize(const Elf_Shdr *section,
                                           const Elf_Sym *symbol,
                                           const Elf_Sym *nextSymbol) {