[ELF2] Use correct symbol table indexes for hash and relocation sections

[ikudrin]

Summary

Hash and relocation sections memorized indexes of symbol table entries during the createSections phase. However, the symbol table section reordered its entries at writing phase. As a result, references in hash and relocation sections might be broken.

This patch forces dependent sections to receive information about actual indexes of symbol table entries from the symbol table section itself when this information is ready.

[ikudrin]

This patch also fixes failures of following test, at least on Windows:

• elf2/dynamic-reloc.s
• elf2/shared.s

[• rafael]

Thanks a lot for the patch and bringing the issue to my attention.

There are a few design options to explore in this area:

• We could pass a custom hash to the DenseMap to get the same

iteration order everywhere.

• We could use MapVector.
• We could use a DenseMap<StringRef, SymbolNumber> along with a

std::vector<Symbol*>. Once resolution is done we then clear the map
and sort the vector.

Given that it is not clear which one is better and given that it will
probably not be too difficult to experiment with them, it is probably
better to keep it simple until we can benchmark the code.

I have then switched to using a MapVector in r247911.

Thanks,
Rafael

lld/trunk/ELF/Writer.cpp

public:
   }
 
   void addReloc(const DynamicReloc<ELFT> &Reloc) { Relocs.push_back(Reloc); }
   void finalize() override {
     this->Header.sh_link = DynSymSec.getSectionIndex();
     this->Header.sh_size = Relocs.size() * this->Header.sh_entsize;
   }
   void writeTo(uint8_t *Buf) override {
+    DynSymSec.prepareGlobalSymbols();
+    for (const SymbolTableEntryInfo &Entry : DynSymSec.getGlobalSymbols()) {
+      assert(!Entry.Body->getDynamicSymbolTableIndex());
+      assert(Entry.SymbolTableIndex > 0);
+      Entry.Body->setDynamicSymbolTableIndex(Entry.SymbolTableIndex);
+    }
     auto *P = reinterpret_cast<Elf_Rela *>(Buf);
     bool IsMips64EL = Relocs[0].C.getFile()->getObj()->isMips64EL();
     for (const DynamicReloc<ELFT> &Rel : Relocs) {
       const SectionChunk<ELFT> &C = Rel.C;
       const Elf_Rel &RI = Rel.RI;
       OutputSection<ELFT> *Out = C.getOutputSection();
       uint32_t SymIndex = RI.getSymbol(IsMips64EL);
       const SymbolBody *Body = C.getFile()->getSymbolBody(SymIndex);

 
 private:
   const bool Dynamic;
   llvm::StringTableBuilder StrTabBuilder;
 };
 
 template <class ELFT> class Writer;
 
+struct SymbolTableEntryInfo {
+  explicit SymbolTableEntryInfo(SymbolBody *Body) : Body(Body) {}
+
+  SymbolBody *Body;
+  unsigned StringTableNameOffset = 0;
+  unsigned SymbolTableIndex = 0;
+};
+
 template <class ELFT>
 class SymbolTableSection final : public OutputSectionBase<ELFT::Is64Bits> {
 public:
   typedef typename ELFFile<ELFT>::Elf_Sym Elf_Sym;
   typedef typename ELFFile<ELFT>::Elf_Sym_Range Elf_Sym_Range;
   typedef typename OutputSectionBase<ELFT::Is64Bits>::uintX_t uintX_t;
   SymbolTableSection(Writer<ELFT> &W, SymbolTable &Table,
                      StringTableSection<ELFT::Is64Bits> &StrTabSec)
void finalize() override {
     this->Header.sh_link = StrTabSec.getSectionIndex();
     this->Header.sh_info = NumLocals + 1;
   }
 
   void writeTo(uint8_t *Buf) override;
 
   const SymbolTable &getSymTable() const { return Table; }
 
-  void addSymbol(StringRef Name, bool isLocal = false) {
+  const std::vector<SymbolTableEntryInfo> &getGlobalSymbols() const {
+    return GlobalSymbols;
+  }
+
+  void addLocalSymbol(StringRef Name) {
+    assert(!GlobalSymbolsPrepared);
     StrTabSec.add(Name);
-    ++NumVisible;
-    if (isLocal)
-      ++NumLocals;
   }
 
+  void addGlobalSymbol(SymbolBody *Body) {
+    assert(!GlobalSymbolsPrepared);
+    StrTabSec.add(Body->getName());
+    GlobalSymbols.emplace_back(Body);
+  }
+
+  // Ensure that StringTableNameOffset and SymbolTableIndex fields
+  // for all global symbols are filled
+  void prepareGlobalSymbols();
+
   StringTableSection<ELFT::Is64Bits> &getStrTabSec() { return StrTabSec; }
-  unsigned getNumSymbols() const { return NumVisible + 1; }
+  unsigned getNumSymbols() const {
+    return GlobalSymbols.size() + NumLocals + 1;
+  }
 
 private:
   SymbolTable &Table;
   StringTableSection<ELFT::Is64Bits> &StrTabSec;
-  unsigned NumVisible = 0;
+  std::vector<SymbolTableEntryInfo> GlobalSymbols;
   unsigned NumLocals = 0;
+  bool GlobalSymbolsPrepared = false;
   const Writer<ELFT> &W;
 };
 
 template <class ELFT>
 class HashTableSection final : public OutputSectionBase<ELFT::Is64Bits> {
   typedef typename ELFFile<ELFT>::Elf_Word Elf_Word;
 
 public:
   HashTableSection(SymbolTableSection<ELFT> &DynSymSec)
       : OutputSectionBase<ELFT::Is64Bits>(".hash", SHT_HASH, SHF_ALLOC),
         DynSymSec(DynSymSec) {
     this->Header.sh_entsize = sizeof(Elf_Word);
     this->Header.sh_addralign = sizeof(Elf_Word);
   }
 
-  void addSymbol(SymbolBody *S) {
-    StringRef Name = S->getName();
-    DynSymSec.addSymbol(Name);
-    Hashes.push_back(hash(Name));
-    S->setDynamicSymbolTableIndex(Hashes.size());
-  }
+  void addSymbol(SymbolBody *S) { DynSymSec.addGlobalSymbol(S); }
 
   void finalize() override {
     this->Header.sh_link = DynSymSec.getSectionIndex();
 
-    assert(DynSymSec.getNumSymbols() == Hashes.size() + 1);
+    assert(DynSymSec.getNumSymbols() ==
+           DynSymSec.getGlobalSymbols().size() + 1);
     unsigned NumEntries = 2;                 // nbucket and nchain.
     NumEntries += DynSymSec.getNumSymbols(); // The chain entries.
 
     // Create as many buckets as there are symbols.
     // FIXME: This is simplistic. We can try to optimize it, but implementing
     // support for SHT_GNU_HASH is probably even more profitable.
     NumEntries += DynSymSec.getNumSymbols();
     this->Header.sh_size = NumEntries * sizeof(Elf_Word);
   }
 
   void writeTo(uint8_t *Buf) override {
+    DynSymSec.prepareGlobalSymbols();
     unsigned NumSymbols = DynSymSec.getNumSymbols();
     auto *P = reinterpret_cast<Elf_Word *>(Buf);
     *P++ = NumSymbols; // nbucket
     *P++ = NumSymbols; // nchain
 
     Elf_Word *Buckets = P;
     Elf_Word *Chains = P + NumSymbols;
 
-    for (unsigned I = 1; I < NumSymbols; ++I) {
-      uint32_t Hash = Hashes[I - 1] % NumSymbols;
+    unsigned I = 1;
+    for (const auto &Entry : DynSymSec.getGlobalSymbols()) {
+      assert(Entry.SymbolTableIndex == I);
+      uint32_t Hash = hash(Entry.Body->getName()) % NumSymbols;
       Chains[I] = Buckets[Hash];
       Buckets[Hash] = I;
+      ++I;
     }
+    assert(I == NumSymbols);
   }
 
   SymbolTableSection<ELFT> &getDynSymSec() { return DynSymSec; }
 
 private:
   uint32_t hash(StringRef Name) {
     uint32_t H = 0;
     for (char C : Name) {
       H = (H << 4) + C;
       uint32_t G = H & 0xf0000000;
       if (G)
         H ^= G >> 24;
       H &= ~G;
     }
     return H;
   }
   SymbolTableSection<ELFT> &DynSymSec;
-  std::vector<uint32_t> Hashes;
 };
 
 template <class ELFT>
 class DynamicSection final : public OutputSectionBase<ELFT::Is64Bits> {
   typedef OutputSectionBase<ELFT::Is64Bits> Base;
   typedef typename Base::HeaderT HeaderT;
   typedef typename Base::Elf_Dyn Elf_Dyn;
 

 }
 
 template <bool Is64Bits>
 void StringTableSection<Is64Bits>::writeTo(uint8_t *Buf) {
   StringRef Data = StrTabBuilder.data();
   memcpy(Buf, Data.data(), Data.size());
 }
 
-template <class ELFT>
-static int compareSym(const typename ELFFile<ELFT>::Elf_Sym *A,
-                      const typename ELFFile<ELFT>::Elf_Sym *B) {
-  uint32_t AN = A->st_name;
-  uint32_t BN = B->st_name;
+static int compareSym(const SymbolTableEntryInfo *A,
+                      const SymbolTableEntryInfo *B) {
+  uint32_t AN = A->StringTableNameOffset;
+  uint32_t BN = B->StringTableNameOffset;
   assert(AN != BN);
   return AN - BN;
 }
 
 static bool includeInSymtab(const SymbolBody &B) {
   if (B.isLazy())
     return false;
   if (!B.isUsedInRegularObj())
     return false;
   uint8_t V = B.getMostConstrainingVisibility();
   if (V != STV_DEFAULT && V != STV_PROTECTED)
     return false;
   return true;
 }
 
+// The order the global symbols are in is not defined. We can use an arbitrary
+// order, but it has to be reproducible. That is true even when cross linking.
+// The default hashing of StringRef produces different results on 32 and 64
+// bit systems so we sort by st_name. That is arbitrary but deterministic.
+// FIXME: Experiment with passing in a custom hashing instead.
+template <class ELFT> void SymbolTableSection<ELFT>::prepareGlobalSymbols() {
+  if (GlobalSymbolsPrepared)
+    return;
+  for (SymbolTableEntryInfo &Entry : GlobalSymbols)
+    Entry.StringTableNameOffset = StrTabSec.getFileOff(Entry.Body->getName());
+  array_pod_sort(GlobalSymbols.begin(), GlobalSymbols.end(), compareSym);
+  unsigned I = NumLocals;
+  for (SymbolTableEntryInfo &Entry : GlobalSymbols)
+    Entry.SymbolTableIndex = ++I;
+  GlobalSymbolsPrepared = true;
+}
+
 template <class ELFT> void SymbolTableSection<ELFT>::writeTo(uint8_t *Buf) {
   Buf += sizeof(Elf_Sym);
 
   // All symbols with STB_LOCAL binding precede the weak and global symbols.
   // .dynsym only contains global symbols.
   if (!Config->DiscardAll && !StrTabSec.isDynamic()) {
     for (const std::unique_ptr<ObjectFileBase> &FileB :
          Table.getObjectFiles()) {
       auto &File = cast<ObjectFile<ELFT>>(*FileB);
       Elf_Sym_Range Syms = File.getLocalSymbols();
       for (const Elf_Sym &Sym : Syms) {
         auto *ESym = reinterpret_cast<Elf_Sym *>(Buf);
         ErrorOr<StringRef> SymName = Sym.getName(File.getStringTable());
         ESym->st_name = (SymName) ? StrTabSec.getFileOff(*SymName) : 0;
         ESym->st_value = Sym.st_value;
         ESym->st_size = Sym.st_size;
         Buf += sizeof(Elf_Sym);
       }
     }
   }
 
-  uint8_t *GlobalStart = Buf;
-
-  for (auto &P : Table.getSymbols()) {
-    StringRef Name = P.first;
-    Symbol *Sym = P.second;
-    SymbolBody *Body = Sym->Body;
-    if (!includeInSymtab(*Body))
-      continue;
+  prepareGlobalSymbols();
+  for (const SymbolTableEntryInfo &Entry : GlobalSymbols) {
+    SymbolBody *Body = Entry.Body;
     const Elf_Sym &InputSym = cast<ELFSymbolBody<ELFT>>(Body)->Sym;
 
     auto *ESym = reinterpret_cast<Elf_Sym *>(Buf);
-    ESym->st_name = StrTabSec.getFileOff(Name);
+    ESym->st_name = Entry.StringTableNameOffset;
 
     const SectionChunk<ELFT> *Section = nullptr;
     const OutputSection<ELFT> *Out = nullptr;
 
     switch (Body->kind()) {
     case SymbolBody::DefinedRegularKind:
       Section = &cast<DefinedRegular<ELFT>>(Body)->Section;
       break;
if (Out) {
         VA += C->OffsetInBSS;
       else
         VA += InputSym.st_value;
       ESym->st_value = VA;
     }
 
     Buf += sizeof(Elf_Sym);
   }
-
-  // The order the global symbols are in is not defined. We can use an arbitrary
-  // order, but it has to be reproducible. That is true even when cross linking.
-  // The default hashing of StringRef produces different results on 32 and 64
-  // bit systems so we sort by st_name. That is arbitrary but deterministic.
-  // FIXME: Experiment with passing in a custom hashing instead.
-  auto *Syms = reinterpret_cast<Elf_Sym *>(GlobalStart);
-  array_pod_sort(Syms, Syms + NumVisible - NumLocals, compareSym<ELFT>);
 }
 
 template <bool Is64Bits>
 template <endianness E>
 void OutputSectionBase<Is64Bits>::writeHeaderTo(
     typename ELFFile<ELFType<E, Is64Bits>>::Elf_Shdr *SHdr) {
   SHdr->sh_name = Header.sh_name;
   SHdr->sh_type = Header.sh_type;
for (auto &P : Symtab.getSymbols()) {
     SymbolBody *Body = P.second->Body;
     if (Body->isStrongUndefined())
       error(Twine("undefined symbol: ") + Name);
 
     if (auto *C = dyn_cast<DefinedCommon<ELFT>>(Body))
       CommonSymbols.push_back(C);
     if (!includeInSymtab(*Body))
       continue;
-    SymTabSec.addSymbol(Name);
+    assert(Name == Body->getName());
+    SymTabSec.addGlobalSymbol(Body);
 
     // FIXME: This adds way too much to the dynamic symbol table. We only
     // need to add the symbols use by dynamic relocations when producing
     // an executable (ignoring --export-dynamic).
     if (needsDynamicSections())
       HashSec.addSymbol(Body);
   }
 
   for (const std::unique_ptr<ObjectFileBase> &FileB : Symtab.getObjectFiles()) {
     auto &File = cast<ObjectFile<ELFT>>(*FileB);
     if (!Config->DiscardAll) {
       Elf_Sym_Range Syms = File.getLocalSymbols();
       for (const Elf_Sym &Sym : Syms) {
         ErrorOr<StringRef> SymName = Sym.getName(File.getStringTable());
         if (SymName)
-          SymTabSec.addSymbol(*SymName, true);
+          SymTabSec.addLocalSymbol(*SymName);
       }
     }
     for (SectionChunk<ELFT> *C : File.getChunks()) {
       if (!C)
         continue;
       const Elf_Shdr *H = C->getSectionHdr();
       OutputSection<ELFT> *Sec =
           getSection(C->getSectionName(), H->sh_type, H->sh_flags);