[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

350 ↗

(On Diff #38432)

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

414–420 ↗

(On Diff #38432)

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 ↗

(On Diff #38432)

You don't need this constructor. Instead of

HashedSymbolData(X, Y)

you can always do

HashedSymbolData{X, Y}

[ikudrin]

ELF/OutputSections.cpp

350 ↗

(On Diff #38432)

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 ↗

(On Diff #38432)

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 ↗

(On Diff #38447)

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 ↗

(On Diff #38447)

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 ↗

(On Diff #38447)

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 ↗

(On Diff #38447)

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

338 ↗

(On Diff #38513)

Remove this blank line.

lld/trunk/ELF/OutputSections.h

 template <class ELFT, bool IsRela>
 typename llvm::object::ELFFile<ELFT>::uintX_t
 getLocalRelTarget(const ObjectFile<ELFT> &File,
                   const llvm::object::Elf_Rel_Impl<ELFT, IsRela> &Rel);
 bool canBePreempted(const SymbolBody *Body, bool NeedsGot);
 template <class ELFT> bool includeInSymtab(const SymbolBody &B);
 
 bool includeInDynamicSymtab(const SymbolBody &B);
-bool includeInGnuHashTable(const SymbolBody &B);
+bool includeInGnuHashTable(SymbolBody *B);
 
 template <class ELFT>
 bool shouldKeepInSymtab(
     const ObjectFile<ELFT> &File, StringRef Name,
     const typename llvm::object::ELFFile<ELFT>::Elf_Sym &Sym);
 
 // This represents a section in an output file.
 // Different sub classes represent different types of sections. Some contain
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_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);
+  // Adds symbols to the hash table.
+  // Sorts the input to satisfy GNU hash section requirements.
+  void addSymbols(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 MaskWords;
   unsigned NBuckets;
   unsigned Shift2;
 };
 
 template <class ELFT>
 class DynamicSection final : public OutputSectionBase<ELFT> {
   typedef OutputSectionBase<ELFT> Base;

lld/trunk/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();
+  ArrayRef<SymbolBody *> A = Out<ELFT>::DynSymTab->getSymbols();
+  unsigned NumHashed = std::count_if(A.begin(), A.end(), includeInGnuHashTable);
   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) {
   writeHeader(Buf);
-  if (!NBuckets) // There are no hashed symbols
+  if (HashedSymbols.empty())
     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() - HashedSymbols.size();
   *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>::addSymbols(std::vector<SymbolBody *> &Symbols) {
+  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);
+  }
+  if (HashedSymbols.empty())
+    return;
+
+  unsigned NBuckets = calcNBuckets(HashedSymbols.size());
+  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::includeInDynamicSymtab(const SymbolBody &B) {
   if (V != STV_DEFAULT && V != STV_PROTECTED)
     return false;
 
   if (Config->ExportDynamic || Config->Shared)
     return true;
   return B.isUsedInDynamicReloc();
 }
 
-bool lld::elf2::includeInGnuHashTable(const SymbolBody &B) {
+bool lld::elf2::includeInGnuHashTable(SymbolBody *B) {
   // Assume that includeInDynamicSymtab() is already checked.
-  return !B.isUndefined();
+  return !B->isUndefined();
 }
 
 template <class ELFT>
 bool lld::elf2::shouldKeepInSymtab(const ObjectFile<ELFT> &File,
                                    StringRef SymName,
                                    const typename ELFFile<ELFT>::Elf_Sym &Sym) {
   if (Sym.getType() == STT_SECTION)
     return false;
 
   // If sym references a section in a discarded group, don't keep it.
   if (File.getSection(Sym) == &InputSection<ELFT>::Discarded)
     return false;
 
   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)
+    // NB: It also sorts Symbols to meet the GNU hash table requirements.
+    Out<ELFT>::GnuHashTab->addSymbols(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>;