[ELF2] Move sorting from symbol table to the GNU hash section.

[ikudrin]

Summary

It is the GNU hash table section which should contain its own data and be responsible for imposing its requirements for the order of dynamic symbols.

[ruiu]

ELF/OutputSections.cpp

349

Is NumHashed always the same as HashedSymbols.size()? If so, remove the variable and use HashedSymbols.size() instead.

413–419

You can use std::partition to separate non-hashed symbols from hashed symbols first, and then sort the latter half.

ELF/OutputSections.h

313–314

You don't need this constructor. Instead of

HashedSymbolData(X, Y)

you can always do

HashedSymbolData{X, Y}

[ikudrin]

ELF/OutputSections.cpp

349

This class requires the other class to call sortSymbols() method. Plus, it requires that addSymbol() is called the exact number of times, and these calls come from the third place. This assert ensures that everything is in sync.

[ruiu]

ELF/OutputSections.h

298–302

This looks really weird. You are not using the argument.

[ikudrin]

• Removed constructor of internal class
• Reworked the sortSymbols() method.

[ikudrin]

ELF/OutputSections.cpp

349

The variable is required in the finalize() method. The HashedSymbols is filled in the sortSymbols() method, which is called from finalize() method of the dynamic symbol table. All finalize() methods should not depend on each other and their call order, I think.

[ruiu]

ELF/OutputSections.cpp

349

Can you count the number of symbols that need to be in .gnu.hash here, instead of calling addSymbol for each symbol? That can be as easy as

ArrayRef<Symbol> A = Out<ELFT>::DynSymTab->getSymbols();
NumHashed = std::count(A.begin(), A.end(), includeInGnuHashTable);

405–406

I think this function should be called "addSymbols" rather than "sortSymbols". This indeed sorts symbols passed to this function, but that's probably secondaly.

ELF/OutputSections.h

299

Add a blank line here.

[ikudrin]

• NumHashed is no longer stored in the class.
• sortSymbols() -> addSymbols().
• assert()s are removed.

[ruiu]

LGTM with a nit. Nice cleanup!

ELF/OutputSections.cpp

337

Remove this blank line.

ELF/OutputSections.h

SymbolTableSection(SymbolTable<ELFT> &Table,
                      StringTableSection<ELFT> &StrTabSec);
 
   void finalize() override;
   void writeTo(uint8_t *Buf) override;
   void addLocalSymbol(StringRef Name);
   void addSymbol(SymbolBody *Body);
   StringTableSection<ELFT> &getStrTabSec() const { return StrTabSec; }
   unsigned getNumSymbols() const { return NumVisible + 1; }
-  unsigned getNumGnuHashSymbols() const { return NumGnuHashed; }
 
-  struct SymbolData {
-    SymbolData(SymbolBody *Body, bool HasGnuHash);
-    SymbolBody *Body;
-    bool HasGnuHash;
-    uint32_t GnuHash;
-  };
-  ArrayRef<SymbolData> getSymbols() const { return Symbols; }
-  ArrayRef<SymbolData> getGnuHashSymbols() const;
+  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<SymbolData> Symbols;
+  std::vector<SymbolBody *> Symbols;
   unsigned NumVisible = 0;
   unsigned NumLocals = 0;
-  unsigned NumGnuHashed = 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;
   typedef typename llvm::object::ELFFile<ELFT>::uintX_t uintX_t;
 
class GnuHashTableSection final : public OutputSectionBase<ELFT> {
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Off Elf_Off;
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Word Elf_Word;
   typedef typename llvm::object::ELFFile<ELFT>::uintX_t uintX_t;
 
 public:
   GnuHashTableSection();
   void finalize() override;
   void writeTo(uint8_t *Buf) override;
-
-  static unsigned calcNBuckets(unsigned NumHashed);
+  void addSymbol() { ++NumHashed; }
+  // Updates the order of the dynamic symbol section symbols
+  // according to the GNU hash section requirements.
+  // Fills its own HashedSymbols as a side effect.
+  void sortSymbols(std::vector<SymbolBody *> &Symbols);
 
 private:
+  static unsigned calcNBuckets(unsigned NumHashed);
   static unsigned calcMaskWords(unsigned NumHashed);
 
   void writeHeader(uint8_t *&Buf);
   void writeBloomFilter(uint8_t *&Buf);
   void writeHashTable(uint8_t *Buf);
 
+  struct HashedSymbolData {
+    SymbolBody *Body;
+    uint32_t Hash;
+  };
+
+  std::vector<HashedSymbolData> HashedSymbols;
+
+  unsigned NumHashed = 0;
   unsigned MaskWords;
   unsigned NBuckets;
   unsigned Shift2;
 };
 
 template <class ELFT>
 class DynamicSection final : public OutputSectionBase<ELFT> {
   typedef OutputSectionBase<ELFT> Base;

ELF/OutputSections.cpp

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 (const typename SymbolTableSection<ELFT>::SymbolData &Item :
-       Out<ELFT>::DynSymTab->getSymbols()) {
-    SymbolBody *Body = Item.Body;
+  for (SymbolBody *Body : Out<ELFT>::DynSymTab->getSymbols()) {
     StringRef Name = Body->getName();
     unsigned I = Body->getDynamicSymbolTableIndex();
     uint32_t Hash = hashSysv(Name) % NumSymbols;
     Chains[I] = Buckets[Hash];
     Buckets[Hash] = I;
   }
 }
 

 template <class ELFT>
 unsigned GnuHashTableSection<ELFT>::calcMaskWords(unsigned NumHashed) {
   if (!NumHashed)
     return 1;
   return NextPowerOf2((NumHashed - 1) / sizeof(Elf_Off));
 }
 
 template <class ELFT> void GnuHashTableSection<ELFT>::finalize() {
-  const unsigned NumHashed = Out<ELFT>::DynSymTab->getNumGnuHashSymbols();
   NBuckets = calcNBuckets(NumHashed);
   MaskWords = calcMaskWords(NumHashed);
   // Second hash shift estimation: just predefined values.
   Shift2 = ELFT::Is64Bits ? 6 : 5;
 
   this->Header.sh_link = Out<ELFT>::DynSymTab->SectionIndex;
   this->Header.sh_size = sizeof(Elf_Word) * 4            // Header
                          + sizeof(Elf_Off) * MaskWords   // Bloom Filter
                          + sizeof(Elf_Word) * NBuckets   // Hash Buckets
                          + sizeof(Elf_Word) * NumHashed; // Hash Values
 }
 
 template <class ELFT> void GnuHashTableSection<ELFT>::writeTo(uint8_t *Buf) {
+  assert(NumHashed == HashedSymbols.size() && "sortSymbols() was not called!");
   writeHeader(Buf);
   if (!NBuckets) // There are no hashed symbols
     return;
   writeBloomFilter(Buf);
   writeHashTable(Buf);
 }
 
 template <class ELFT>
 void GnuHashTableSection<ELFT>::writeHeader(uint8_t *&Buf) {
   auto *P = reinterpret_cast<Elf_Word *>(Buf);
   *P++ = NBuckets;
-  *P++ = Out<ELFT>::DynSymTab->getNumSymbols() -
-         Out<ELFT>::DynSymTab->getNumGnuHashSymbols();
+  *P++ = Out<ELFT>::DynSymTab->getNumSymbols() - NumHashed;
   *P++ = MaskWords;
   *P++ = Shift2;
   Buf = reinterpret_cast<uint8_t *>(P);
 }
 
 template <class ELFT>
 void GnuHashTableSection<ELFT>::writeBloomFilter(uint8_t *&Buf) {
   unsigned C = sizeof(Elf_Off) * 8;
 
   auto *Masks = reinterpret_cast<Elf_Off *>(Buf);
-  for (const typename SymbolTableSection<ELFT>::SymbolData &Item :
-       Out<ELFT>::DynSymTab->getGnuHashSymbols()) {
-    size_t Pos = (Item.GnuHash / C) & (MaskWords - 1);
-    uintX_t V = (uintX_t(1) << (Item.GnuHash % C)) |
-                (uintX_t(1) << ((Item.GnuHash >> Shift2) % C));
+  for (const HashedSymbolData &Item : HashedSymbols) {
+    size_t Pos = (Item.Hash / C) & (MaskWords - 1);
+    uintX_t V = (uintX_t(1) << (Item.Hash % C)) |
+                (uintX_t(1) << ((Item.Hash >> Shift2) % C));
     Masks[Pos] |= V;
   }
   Buf += sizeof(Elf_Off) * MaskWords;
 }
 
 template <class ELFT>
 void GnuHashTableSection<ELFT>::writeHashTable(uint8_t *Buf) {
   Elf_Word *Buckets = reinterpret_cast<Elf_Word *>(Buf);
   Elf_Word *Values = Buckets + NBuckets;
 
   int PrevBucket = -1;
   int I = 0;
-  for (const typename SymbolTableSection<ELFT>::SymbolData &Item :
-       Out<ELFT>::DynSymTab->getGnuHashSymbols()) {
-    int Bucket = Item.GnuHash % NBuckets;
+  for (const HashedSymbolData &Item : HashedSymbols) {
+    int Bucket = Item.Hash % NBuckets;
     assert(PrevBucket <= Bucket);
     if (Bucket != PrevBucket) {
       Buckets[Bucket] = Item.Body->getDynamicSymbolTableIndex();
       PrevBucket = Bucket;
       if (I > 0)
         Values[I - 1] |= 1;
     }
-    Values[I] = Item.GnuHash & ~1;
+    Values[I] = Item.Hash & ~1;
     ++I;
   }
   if (I > 0)
     Values[I - 1] |= 1;
 }
 
 template <class ELFT>
+void GnuHashTableSection<ELFT>::sortSymbols(
+    std::vector<SymbolBody *> &Symbols) {
+  if (!NumHashed)
+    return;
+
+  std::vector<SymbolBody *> NotHashed;
+  NotHashed.reserve(Symbols.size());
+  HashedSymbols.reserve(Symbols.size());
+  for (SymbolBody *B : Symbols) {
+    if (includeInGnuHashTable(*B))
+      HashedSymbols.push_back(HashedSymbolData{B, hashGnu(B->getName())});
+    else
+      NotHashed.push_back(B);
+  }
+  assert(NumHashed == HashedSymbols.size());
+
+  unsigned NBuckets = calcNBuckets(NumHashed);
+  std::stable_sort(HashedSymbols.begin(), HashedSymbols.end(),
+                   [&](const HashedSymbolData &L, const HashedSymbolData &R) {
+                     return L.Hash % NBuckets < R.Hash % NBuckets;
+                   });
+
+  Symbols = std::move(NotHashed);
+  for (const HashedSymbolData &Item : HashedSymbols)
+    Symbols.push_back(Item.Body);
+}
+
+template <class ELFT>
 DynamicSection<ELFT>::DynamicSection(SymbolTable<ELFT> &SymTab)
     : OutputSectionBase<ELFT>(".dynamic", llvm::ELF::SHT_DYNAMIC,
                               llvm::ELF::SHF_ALLOC | llvm::ELF::SHF_WRITE),
       SymTab(SymTab) {
   Elf_Shdr &Header = this->Header;
   Header.sh_addralign = ELFT::Is64Bits ? 8 : 4;
   Header.sh_entsize = ELFT::Is64Bits ? 16 : 8;
 }
bool lld::elf2::shouldKeepInSymtab(const ObjectFile<ELFT> &File,
   if (Config->DiscardNone)
     return true;
 
   // ELF defines dynamic locals as symbols which name starts with ".L".
   return !(Config->DiscardLocals && SymName.startswith(".L"));
 }
 
 template <class ELFT>
-SymbolTableSection<ELFT>::SymbolData::SymbolData(SymbolBody *Body,
-                                                 bool HasGnuHash)
-    : Body(Body), HasGnuHash(HasGnuHash),
-      GnuHash(HasGnuHash ? hashGnu(Body->getName()) : 0) {}
-
-template <class ELFT>
 SymbolTableSection<ELFT>::SymbolTableSection(
     SymbolTable<ELFT> &Table, StringTableSection<ELFT> &StrTabSec)
     : OutputSectionBase<ELFT>(
           StrTabSec.isDynamic() ? ".dynsym" : ".symtab",
           StrTabSec.isDynamic() ? llvm::ELF::SHT_DYNSYM : llvm::ELF::SHT_SYMTAB,
           StrTabSec.isDynamic() ? (uintX_t)llvm::ELF::SHF_ALLOC : 0),
       Table(Table), StrTabSec(StrTabSec) {
   typedef OutputSectionBase<ELFT> Base;
   typename Base::Elf_Shdr &Header = this->Header;
 
   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(),
-                     [](const SymbolData &L, const SymbolData &R) {
-                       return getSymbolBinding(L.Body) == STB_LOCAL &&
-                              getSymbolBinding(R.Body) != STB_LOCAL;
+                     [](SymbolBody *L, SymbolBody *R) {
+                       return getSymbolBinding(L) == STB_LOCAL &&
+                              getSymbolBinding(R) != STB_LOCAL;
                      });
     return;
   }
-  if (NumGnuHashed) {
-    unsigned NBuckets = GnuHashTableSection<ELFT>::calcNBuckets(NumGnuHashed);
-    std::stable_sort(Symbols.begin(), Symbols.end(),
-                     [NBuckets](const SymbolData &L, const SymbolData &R) {
-                       if (!L.HasGnuHash || !R.HasGnuHash)
-                         return R.HasGnuHash;
-                       return L.GnuHash % NBuckets < R.GnuHash % NBuckets;
-                     });
-  }
+  if (Out<ELFT>::GnuHashTab)
+    Out<ELFT>::GnuHashTab->sortSymbols(Symbols);
   size_t I = 0;
-  for (const SymbolData &Item : Symbols)
-    Item.Body->setDynamicSymbolTableIndex(++I);
+  for (SymbolBody *B : Symbols)
+    B->setDynamicSymbolTableIndex(++I);
 }
 
 template <class ELFT>
 void SymbolTableSection<ELFT>::addLocalSymbol(StringRef Name) {
   StrTabSec.add(Name);
   ++NumVisible;
   ++NumLocals;
 }
 
 template <class ELFT>
 void SymbolTableSection<ELFT>::addSymbol(SymbolBody *Body) {
   StrTabSec.add(Body->getName());
-  const bool HasGnuHash = StrTabSec.isDynamic() && Out<ELFT>::GnuHashTab &&
-                          includeInGnuHashTable(*Body);
-  Symbols.emplace_back(Body, HasGnuHash);
+  Symbols.push_back(Body);
   ++NumVisible;
-  if (HasGnuHash)
-    ++NumGnuHashed;
 }
 
 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())
void SymbolTableSection<ELFT>::writeLocalSymbols(uint8_t *&Buf) {
   }
 }
 
 template <class ELFT>
 void SymbolTableSection<ELFT>::writeGlobalSymbols(uint8_t *Buf) {
   // Write the internal symbol table contents to the output symbol table
   // pointed by Buf.
   auto *ESym = reinterpret_cast<Elf_Sym *>(Buf);
-  for (const SymbolData &Item : Symbols) {
-    SymbolBody *Body = Item.Body;
+  for (SymbolBody *Body : Symbols) {
     const OutputSectionBase<ELFT> *OutSec = nullptr;
 
     switch (Body->kind()) {
     case SymbolBody::DefinedSyntheticKind:
       OutSec = &cast<DefinedSynthetic<ELFT>>(Body)->Section;
       break;
     case SymbolBody::DefinedRegularKind: {
       auto *Sym = cast<DefinedRegular<ELFT>>(Body->repl());
uint8_t SymbolTableSection<ELFT>::getSymbolBinding(SymbolBody *Body) {
   uint8_t Visibility = Body->getVisibility();
   if (Visibility != STV_DEFAULT && Visibility != STV_PROTECTED)
     return STB_LOCAL;
   if (const auto *EBody = dyn_cast<ELFSymbolBody<ELFT>>(Body))
     return EBody->Sym.getBinding();
   return Body->isWeak() ? STB_WEAK : STB_GLOBAL;
 }
 
-template <class ELFT>
-ArrayRef<typename SymbolTableSection<ELFT>::SymbolData>
-SymbolTableSection<ELFT>::getGnuHashSymbols() const {
-  return getSymbols().slice(Symbols.size() - NumGnuHashed);
-}
-
 namespace lld {
 namespace elf2 {
 template class OutputSectionBase<ELF32LE>;
 template class OutputSectionBase<ELF32BE>;
 template class OutputSectionBase<ELF64LE>;
 template class OutputSectionBase<ELF64BE>;
 
 template class GotPltSection<ELF32LE>;

ELF/Writer.cpp

for (auto &P : Symtab.getSymbols()) {
 
     if (auto *C = dyn_cast<DefinedCommon<ELFT>>(Body))
       CommonSymbols.push_back(C);
     if (!includeInSymtab<ELFT>(*Body))
       continue;
     if (Out<ELFT>::SymTab)
       Out<ELFT>::SymTab->addSymbol(Body);
 
-    if (isOutputDynamic() && includeInDynamicSymtab(*Body))
+    if (isOutputDynamic() && includeInDynamicSymtab(*Body)) {
       Out<ELFT>::DynSymTab->addSymbol(Body);
+      if (Out<ELFT>::GnuHashTab && includeInGnuHashTable(*Body))
+        Out<ELFT>::GnuHashTab->addSymbol();
+    }
   }
   addCommonSymbols(CommonSymbols);
 
   // This order is not the same as the final output order
   // because we sort the sections using their attributes below.
   if (Out<ELFT>::SymTab)
     OutputSections.push_back(Out<ELFT>::SymTab);
   OutputSections.push_back(Out<ELFT>::ShStrTab);