[ELF2] Determine the order of entries of symbol tables in the finalize() phase.

[ikudrin]

Summary

• Move the responsibility to call SymbolBody::setDynamicSymbolTableIndex() from hash table to dynamic symbol table.
• Hash table is not longer responsible for filling dynamic symbol table.
• The final order of symbols of both symbol tables is set before writing phase starts.

[ruiu]

ELF/OutputSections.cpp

694–697 ↗

(On Diff #37911)

Do we have to sort them even if isDynamic() is false?

698 ↗

(On Diff #37911)

Early return.

if (!StrTabSec.isDynamic())
  return;

ELF/Writer.cpp

512–514 ↗

(On Diff #37911)

Remove {}.

[ikudrin]

ELF/OutputSections.cpp

694–697 ↗

(On Diff #37911)

It's a replacement for removed lines 813-818.

[ruiu]

ELF/OutputSections.cpp

699–702 ↗

(On Diff #37911)

size_t I = 0;
for (SymbolBody *B : Symbols)
  B->setDynamicSymbolTableIndex(++I);

829–832 ↗

(On Diff #37911)

You can inline this function in .h.

[ikudrin]

• Remove redundant braces.
• Don't sort dynamic symbol table (yet).

[ruiu]

LGTM with a nit.

ELF/OutputSections.cpp

698 ↗

(On Diff #37916)

Early return before this 'else' to remove this 'else'.

[ruiu]

This comment is not directly related to this change (so you can ignore), but I noticed that the symbol handling in SymbolTableSection is very odd. We do call addSymbol only when includeInSymtab() is true for a symbol, but we basically discard that information and iterate over the symbol table again inside SymbolTableSection when writing an output (and call includeInSymtab() again so that the output is consistent). This needs to be straightened.

[ikudrin]

In D13911#271550, @ruiu wrote:

This comment is not directly related to this change (so you can ignore), but I noticed that the symbol handling in SymbolTableSection is very odd. We do call addSymbol only when includeInSymtab() is true for a symbol, but we basically discard that information and iterate over the symbol table again inside SymbolTableSection when writing an output (and call includeInSymtab() again so that the output is consistent). This needs to be straightened.

This patch fixes that behavior for global symbols.

[ruiu]

Yes, that's awesome. Local symbols are handled differently, so it's probably a bit hard to remove that.

lld/trunk/ELF/OutputSections.h

public:
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Sym Elf_Sym;
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Sym_Range Elf_Sym_Range;
   typedef typename llvm::object::ELFFile<ELFT>::uintX_t uintX_t;
   SymbolTableSection(SymbolTable<ELFT> &Table,
                      StringTableSection<ELFT> &StrTabSec);
 
   void finalize() override;
   void writeTo(uint8_t *Buf) override;
-  void addSymbol(StringRef Name, bool isLocal = false);
+  void addLocalSymbol(StringRef Name);
+  void addSymbol(SymbolBody *Body);
   StringTableSection<ELFT> &getStrTabSec() const { return StrTabSec; }
   unsigned getNumSymbols() const { return NumVisible + 1; }
 
+  ArrayRef<SymbolBody *> getSymbols() const { return Symbols; }
+
 private:
   void writeLocalSymbols(uint8_t *&Buf);
   void writeGlobalSymbols(uint8_t *Buf);
 
   static uint8_t getSymbolBinding(SymbolBody *Body);
 
   SymbolTable<ELFT> &Table;
   StringTableSection<ELFT> &StrTabSec;
+  std::vector<SymbolBody *> Symbols;
   unsigned NumVisible = 0;
   unsigned NumLocals = 0;
 };
 
 template <class ELFT>
 class RelocationSection final : public OutputSectionBase<ELFT> {
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Rel Elf_Rel;
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Rela Elf_Rela;

 };
 
 template <class ELFT>
 class HashTableSection final : public OutputSectionBase<ELFT> {
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Word Elf_Word;
 
 public:
   HashTableSection();
-  void addSymbol(SymbolBody *S);
   void finalize() override;
   void writeTo(uint8_t *Buf) override;
-
-private:
-  std::vector<uint32_t> Hashes;
 };
 
 template <class ELFT>
 class DynamicSection final : public OutputSectionBase<ELFT> {
   typedef OutputSectionBase<ELFT> Base;
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Dyn Elf_Dyn;
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Rel Elf_Rel;
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Rela Elf_Rela;

lld/trunk/ELF/OutputSections.cpp

for (char C : Name) {
     uint32_t G = H & 0xf0000000;
     if (G)
       H ^= G >> 24;
     H &= ~G;
   }
   return H;
 }
 
-template <class ELFT> void HashTableSection<ELFT>::addSymbol(SymbolBody *S) {
-  StringRef Name = S->getName();
-  Out<ELFT>::DynSymTab->addSymbol(Name);
-  Hashes.push_back(hash(Name));
-  S->setDynamicSymbolTableIndex(Hashes.size());
-}
-
 template <class ELFT> void HashTableSection<ELFT>::finalize() {
   this->Header.sh_link = Out<ELFT>::DynSymTab->SectionIndex;
 
-  assert(Out<ELFT>::DynSymTab->getNumSymbols() == Hashes.size() + 1);
   unsigned NumEntries = 2;                 // nbucket and nchain.
   NumEntries += Out<ELFT>::DynSymTab->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 += Out<ELFT>::DynSymTab->getNumSymbols();
   this->Header.sh_size = NumEntries * sizeof(Elf_Word);
 }
 
 template <class ELFT> void HashTableSection<ELFT>::writeTo(uint8_t *Buf) {
   unsigned NumSymbols = Out<ELFT>::DynSymTab->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;
+  for (SymbolBody *Body : Out<ELFT>::DynSymTab->getSymbols()) {
+    StringRef Name = Body->getName();
+    unsigned I = Body->getDynamicSymbolTableIndex();
+    uint32_t Hash = hash(Name) % NumSymbols;
     Chains[I] = Buckets[Hash];
     Buckets[Hash] = I;
   }
 }
 
 template <class ELFT>
 DynamicSection<ELFT>::DynamicSection(SymbolTable<ELFT> &SymTab)
     : OutputSectionBase<ELFT>(".dynamic", llvm::ELF::SHT_DYNAMIC,
SymbolTableSection<ELFT>::SymbolTableSection(
   Header.sh_entsize = sizeof(Elf_Sym);
   Header.sh_addralign = ELFT::Is64Bits ? 8 : 4;
 }
 
 template <class ELFT> void SymbolTableSection<ELFT>::finalize() {
   this->Header.sh_size = getNumSymbols() * sizeof(Elf_Sym);
   this->Header.sh_link = StrTabSec.SectionIndex;
   this->Header.sh_info = NumLocals + 1;
+
+  if (!StrTabSec.isDynamic()) {
+    std::stable_sort(Symbols.begin(), Symbols.end(),
+                     [](SymbolBody *L, SymbolBody *R) {
+                       return getSymbolBinding(L) == STB_LOCAL &&
+                              getSymbolBinding(R) != STB_LOCAL;
+                     });
+    return;
+  }
+  size_t I = 0;
+  for (SymbolBody *Body : Symbols)
+    Body->setDynamicSymbolTableIndex(++I);
 }
 
 template <class ELFT>
-void SymbolTableSection<ELFT>::addSymbol(StringRef Name, bool isLocal) {
+void SymbolTableSection<ELFT>::addLocalSymbol(StringRef Name) {
   StrTabSec.add(Name);
   ++NumVisible;
-  if (isLocal)
-    ++NumLocals;
 }
 
+template <class ELFT>
+void SymbolTableSection<ELFT>::addSymbol(SymbolBody *Body) {
+  StrTabSec.add(Body->getName());
+  Symbols.push_back(Body);
+  ++NumVisible;
+}
+
 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())
     writeLocalSymbols(Buf);
 
for (const std::unique_ptr<ObjectFile<ELFT>> &File : Table.getObjectFiles()) {
     }
   }
 }
 
 template <class ELFT>
 void SymbolTableSection<ELFT>::writeGlobalSymbols(uint8_t *Buf) {
   // Write the internal symbol table contents to the output symbol table
   // pointed by Buf.
-  uint8_t *Start = Buf;
-  for (const std::pair<StringRef, Symbol *> &P : Table.getSymbols()) {
-    StringRef Name = P.first;
-    Symbol *Sym = P.second;
-    SymbolBody *Body = Sym->Body;
-    if (!includeInSymtab<ELFT>(*Body))
-      continue;
-    if (StrTabSec.isDynamic() && !includeInDynamicSymtab(*Body))
-      continue;
-
-    auto *ESym = reinterpret_cast<Elf_Sym *>(Buf);
-    Buf += sizeof(*ESym);
+  for (SymbolBody *Body : Symbols) {
+    StringRef Name = Body->getName();
 
     ESym->st_name = StrTabSec.getFileOff(Name);
 
     const OutputSectionBase<ELFT> *OutSec = nullptr;
     const InputSectionBase<ELFT> *Section = nullptr;
 
     switch (Body->kind()) {
     case SymbolBody::DefinedSyntheticKind:
for (SymbolBody *Body : Symbols) {
 
     if (Section)
       OutSec = Section->OutSec;
 
     if (isa<DefinedAbsolute<ELFT>>(Body))
       ESym->st_shndx = SHN_ABS;
     else if (OutSec)
       ESym->st_shndx = OutSec->SectionIndex;
+
+    ++ESym;
   }
-  if (!StrTabSec.isDynamic())
-    std::stable_sort(
-        reinterpret_cast<Elf_Sym *>(Start), reinterpret_cast<Elf_Sym *>(Buf),
-        [](const Elf_Sym &A, const Elf_Sym &B) -> bool {
-          return A.getBinding() == STB_LOCAL && B.getBinding() != STB_LOCAL;
-        });
 }
 
 template <class ELFT>
 uint8_t SymbolTableSection<ELFT>::getSymbolBinding(SymbolBody *Body) {
   uint8_t Visibility = Body->getMostConstrainingVisibility();
   if (Visibility != STV_DEFAULT && Visibility != STV_PROTECTED)
     return STB_LOCAL;
   if (const auto *EBody = dyn_cast<ELFSymbolBody<ELFT>>(Body))

lld/trunk/ELF/Writer.cpp

 template <class ELFT> void Writer<ELFT>::copyLocalSymbols() {
   for (const std::unique_ptr<ObjectFile<ELFT>> &F : Symtab.getObjectFiles()) {
     for (const Elf_Sym &Sym : F->getLocalSymbols()) {
       ErrorOr<StringRef> SymNameOrErr = Sym.getName(F->getStringTable());
       error(SymNameOrErr);
       StringRef SymName = *SymNameOrErr;
       if (!shouldKeepInSymtab<ELFT>(*F, SymName, Sym))
         continue;
-      Out<ELFT>::SymTab->addSymbol(SymName, true);
+      Out<ELFT>::SymTab->addLocalSymbol(SymName);
     }
   }
 }
 
 // PPC64 has a number of special SHT_PROGBITS+SHF_ALLOC+SHF_WRITE sections that
 // we would like to make sure appear is a specific order to maximize their
 // coverage by a single signed 16-bit offset from the TOC base pointer.
 // Conversely, the special .tocbss section should be first among all SHT_NOBITS
for (const std::unique_ptr<ObjectFile<ELFT>> &F : Symtab.getObjectFiles())
     for (InputSectionBase<ELFT> *B : F->getSections())
       if (auto *S = dyn_cast_or_null<InputSection<ELFT>>(B))
         if (S != &InputSection<ELFT>::Discarded)
           scanRelocs(*S);
 
   // FIXME: Try to avoid the extra walk over all global symbols.
   std::vector<DefinedCommon<ELFT> *> CommonSymbols;
   for (auto &P : Symtab.getSymbols()) {
-    StringRef Name = P.first;
     SymbolBody *Body = P.second->Body;
     if (auto *U = dyn_cast<Undefined<ELFT>>(Body))
       if (!U->isWeak() && !U->canKeepUndefined())
         reportUndefined<ELFT>(Symtab, *Body);
 
     if (auto *C = dyn_cast<DefinedCommon<ELFT>>(Body))
       CommonSymbols.push_back(C);
     if (!includeInSymtab<ELFT>(*Body))
       continue;
-    Out<ELFT>::SymTab->addSymbol(Name);
+    Out<ELFT>::SymTab->addSymbol(Body);
 
     if (isOutputDynamic() && includeInDynamicSymtab(*Body))
-      Out<ELFT>::HashTab->addSymbol(Body);
+      Out<ELFT>::DynSymTab->addSymbol(Body);
   }
   addCommonSymbols(CommonSymbols);
 
   // This order is not the same as the final output order
   // because we sort the sections using their attributes below.
   OutputSections.push_back(Out<ELFT>::SymTab);
   OutputSections.push_back(Out<ELFT>::ShStrTab);
   OutputSections.push_back(Out<ELFT>::StrTab);