[ELF] Convert GnuHashTableSection to input section

[evgeny777]

Summary

Other changes:

• SyntheticSections.h: SymbolTableEntry was also moved with this change, so no need to include OutputSections.h any longer
• Writer.cpp: In<ELFT>::DynSymTab is finalized in a same call to finalizeSynthetic with all other synthetic sections.

[ruiu]

LGTM

ELF/Writer.cpp

951–952 ↗

(On Diff #78341)

Thank you for updating the comment.

lld/trunk/ELF/OutputSections.h

 // The writer creates multiple OutputSections and assign them unique,
 // non-overlapping file offsets and VAs.
 class OutputSectionBase {
 public:
   enum Kind {
     Base,
     EHFrame,
     EHFrameHdr,
-    GnuHashTable,
     HashTable,
     Merge,
     Plt,
     Regular,
     VersDef,
     VersNeed,
     VersTable
   };
public:
   static bool classof(const OutputSectionBase *B) {
     return B->getKind() == Plt;
   }
 
 private:
   std::vector<std::pair<const SymbolBody *, unsigned>> Entries;
 };
 
-struct SymbolTableEntry {
-  SymbolBody *Symbol;
-  size_t StrTabOffset;
-};
-
 // For more information about .gnu.version and .gnu.version_r see:
 // https://www.akkadia.org/drepper/symbol-versioning
 
 // The .gnu.version_d section which has a section type of SHT_GNU_verdef shall
 // contain symbol version definitions. The number of entries in this section
 // shall be contained in the DT_VERDEFNUM entry of the .dynamic section.
 // The section shall contain an array of Elf_Verdef structures, optionally
 // followed by an array of Elf_Verdaux structures.
public:
   void finalize() override;
   void writeTo(uint8_t *Buf) override;
   Kind getKind() const override { return HashTable; }
   static bool classof(const OutputSectionBase *B) {
     return B->getKind() == HashTable;
   }
 };
 
-// Outputs GNU Hash section. For detailed explanation see:
-// https://blogs.oracle.com/ali/entry/gnu_hash_elf_sections
-template <class ELFT>
-class GnuHashTableSection final : public OutputSectionBase {
-  typedef typename ELFT::Off Elf_Off;
-  typedef typename ELFT::Word Elf_Word;
-  typedef typename ELFT::uint uintX_t;
-
-public:
-  GnuHashTableSection();
-  void finalize() override;
-  void writeTo(uint8_t *Buf) override;
-
-  // Adds symbols to the hash table.
-  // Sorts the input to satisfy GNU hash section requirements.
-  void addSymbols(std::vector<SymbolTableEntry> &Symbols);
-  Kind getKind() const override { return GnuHashTable; }
-  static bool classof(const OutputSectionBase *B) {
-    return B->getKind() == GnuHashTable;
-  }
-
-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 SymbolData {
-    SymbolBody *Body;
-    size_t STName;
-    uint32_t Hash;
-  };
-
-  std::vector<SymbolData> Symbols;
-
-  unsigned MaskWords;
-  unsigned NBuckets;
-  unsigned Shift2;
-};
-
 // --eh-frame-hdr option tells linker to construct a header for all the
 // .eh_frame sections. This header is placed to a section named .eh_frame_hdr
 // and also to a PT_GNU_EH_FRAME segment.
 // At runtime the unwinder then can find all the PT_GNU_EH_FRAME segments by
 // calling dl_iterate_phdr.
 // This section contains a lookup table for quick binary search of FDEs.
 // Detailed info about internals can be found in Ian Lance Taylor's blog:
 // http://www.airs.com/blog/archives/460 (".eh_frame")

 template <class ELFT> struct Out {
   typedef typename ELFT::uint uintX_t;
   typedef typename ELFT::Phdr Elf_Phdr;
 
   static uint8_t First;
   static EhFrameHeader<ELFT> *EhFrameHdr;
   static EhOutputSection<ELFT> *EhFrame;
   static GdbIndexSection<ELFT> *GdbIndex;
-  static GnuHashTableSection<ELFT> *GnuHashTab;
   static HashTableSection<ELFT> *HashTab;
   static OutputSection<ELFT> *Bss;
   static OutputSection<ELFT> *MipsRldMap;
   static OutputSectionBase *Opd;
   static uint8_t *OpdBuf;
   static PltSection<ELFT> *Plt;
   static VersionDefinitionSection<ELFT> *VerDef;
   static VersionTableSection<ELFT> *VerSym;
if (Config->OFormatBinary)
     return 0;
   return Out<ELFT>::ElfHeader->Size + Out<ELFT>::ProgramHeaders->Size;
 }
 
 template <class ELFT> uint8_t Out<ELFT>::First;
 template <class ELFT> EhFrameHeader<ELFT> *Out<ELFT>::EhFrameHdr;
 template <class ELFT> EhOutputSection<ELFT> *Out<ELFT>::EhFrame;
 template <class ELFT> GdbIndexSection<ELFT> *Out<ELFT>::GdbIndex;
-template <class ELFT> GnuHashTableSection<ELFT> *Out<ELFT>::GnuHashTab;
 template <class ELFT> HashTableSection<ELFT> *Out<ELFT>::HashTab;
 template <class ELFT> OutputSection<ELFT> *Out<ELFT>::Bss;
 template <class ELFT> OutputSection<ELFT> *Out<ELFT>::MipsRldMap;
 template <class ELFT> OutputSectionBase *Out<ELFT>::Opd;
 template <class ELFT> uint8_t *Out<ELFT>::OpdBuf;
 template <class ELFT> PltSection<ELFT> *Out<ELFT>::Plt;
 template <class ELFT> VersionDefinitionSection<ELFT> *Out<ELFT>::VerDef;
 template <class ELFT> VersionTableSection<ELFT> *Out<ELFT>::VerSym;

lld/trunk/ELF/OutputSections.cpp

for (const SymbolTableEntry &S : In<ELFT>::DynSymTab->getSymbols()) {
     StringRef Name = Body->getName();
     unsigned I = Body->DynsymIndex;
     uint32_t Hash = hashSysV(Name) % NumSymbols;
     Chains[I] = Buckets[Hash];
     Buckets[Hash] = I;
   }
 }
 
-static uint32_t hashGnu(StringRef Name) {
-  uint32_t H = 5381;
-  for (uint8_t C : Name)
-    H = (H << 5) + H + C;
-  return H;
-}
-
-template <class ELFT>
-GnuHashTableSection<ELFT>::GnuHashTableSection()
-    : OutputSectionBase(".gnu.hash", SHT_GNU_HASH, SHF_ALLOC) {
-  this->Entsize = ELFT::Is64Bits ? 0 : 4;
-  this->Addralign = sizeof(uintX_t);
-}
-
-template <class ELFT>
-unsigned GnuHashTableSection<ELFT>::calcNBuckets(unsigned NumHashed) {
-  if (!NumHashed)
-    return 0;
-
-  // These values are prime numbers which are not greater than 2^(N-1) + 1.
-  // In result, for any particular NumHashed we return a prime number
-  // which is not greater than NumHashed.
-  static const unsigned Primes[] = {
-      1,   1,    3,    3,    7,    13,    31,    61,    127,   251,
-      509, 1021, 2039, 4093, 8191, 16381, 32749, 65521, 131071};
-
-  return Primes[std::min<unsigned>(Log2_32_Ceil(NumHashed),
-                                   array_lengthof(Primes) - 1)];
-}
-
-// Bloom filter estimation: at least 8 bits for each hashed symbol.
-// GNU Hash table requirement: it should be a power of 2,
-//   the minimum value is 1, even for an empty table.
-// Expected results for a 32-bit target:
-//   calcMaskWords(0..4)   = 1
-//   calcMaskWords(5..8)   = 2
-//   calcMaskWords(9..16)  = 4
-// For a 64-bit target:
-//   calcMaskWords(0..8)   = 1
-//   calcMaskWords(9..16)  = 2
-//   calcMaskWords(17..32) = 4
-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() {
-  unsigned NumHashed = Symbols.size();
-  NBuckets = calcNBuckets(NumHashed);
-  MaskWords = calcMaskWords(NumHashed);
-  // Second hash shift estimation: just predefined values.
-  Shift2 = ELFT::Is64Bits ? 6 : 5;
-
-  this->Link = In<ELFT>::DynSymTab->OutSec->SectionIndex;
-  this->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 (Symbols.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++ = In<ELFT>::DynSymTab->getNumSymbols() - Symbols.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 SymbolData &Sym : Symbols) {
-    size_t Pos = (Sym.Hash / C) & (MaskWords - 1);
-    uintX_t V = (uintX_t(1) << (Sym.Hash % C)) |
-                (uintX_t(1) << ((Sym.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 SymbolData &Sym : Symbols) {
-    int Bucket = Sym.Hash % NBuckets;
-    assert(PrevBucket <= Bucket);
-    if (Bucket != PrevBucket) {
-      Buckets[Bucket] = Sym.Body->DynsymIndex;
-      PrevBucket = Bucket;
-      if (I > 0)
-        Values[I - 1] |= 1;
-    }
-    Values[I] = Sym.Hash & ~1;
-    ++I;
-  }
-  if (I > 0)
-    Values[I - 1] |= 1;
-}
-
-// Add symbols to this symbol hash table. Note that this function
-// destructively sort a given vector -- which is needed because
-// GNU-style hash table places some sorting requirements.
-template <class ELFT>
-void GnuHashTableSection<ELFT>::addSymbols(std::vector<SymbolTableEntry> &V) {
-  // Ideally this will just be 'auto' but GCC 6.1 is not able
-  // to deduce it correctly.
-  std::vector<SymbolTableEntry>::iterator Mid =
-      std::stable_partition(V.begin(), V.end(), [](const SymbolTableEntry &S) {
-        return S.Symbol->isUndefined();
-      });
-  if (Mid == V.end())
-    return;
-  for (auto I = Mid, E = V.end(); I != E; ++I) {
-    SymbolBody *B = I->Symbol;
-    size_t StrOff = I->StrTabOffset;
-    Symbols.push_back({B, StrOff, hashGnu(B->getName())});
-  }
-
-  unsigned NBuckets = calcNBuckets(Symbols.size());
-  std::stable_sort(Symbols.begin(), Symbols.end(),
-                   [&](const SymbolData &L, const SymbolData &R) {
-                     return L.Hash % NBuckets < R.Hash % NBuckets;
-                   });
-
-  V.erase(Mid, V.end());
-  for (const SymbolData &Sym : Symbols)
-    V.push_back({Sym.Body, Sym.STName});
-}
-
 // Returns the number of version definition entries. Because the first entry
 // is for the version definition itself, it is the number of versioned symbols
 // plus one. Note that we don't support multiple versions yet.
 static unsigned getVerDefNum() { return Config->VersionDefinitions.size() + 1; }
 
 template <class ELFT>
 EhFrameHeader<ELFT>::EhFrameHeader()
     : OutputSectionBase(".eh_frame_hdr", SHT_PROGBITS, SHF_ALLOC) {}

 template class EhFrameHeader<ELF64LE>;
 template class EhFrameHeader<ELF64BE>;
 
 template class PltSection<ELF32LE>;
 template class PltSection<ELF32BE>;
 template class PltSection<ELF64LE>;
 template class PltSection<ELF64BE>;
 
-template class GnuHashTableSection<ELF32LE>;
-template class GnuHashTableSection<ELF32BE>;
-template class GnuHashTableSection<ELF64LE>;
-template class GnuHashTableSection<ELF64BE>;
-
 template class HashTableSection<ELF32LE>;
 template class HashTableSection<ELF32BE>;
 template class HashTableSection<ELF64LE>;
 template class HashTableSection<ELF64BE>;
 
 template class OutputSection<ELF32LE>;
 template class OutputSection<ELF32BE>;
 template class OutputSection<ELF64LE>;

lld/trunk/ELF/SyntheticSections.h

 //===- SyntheticSection.h ---------------------------------------*- C++ -*-===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_ELF_SYNTHETIC_SECTION_H
 #define LLD_ELF_SYNTHETIC_SECTION_H
 
 #include "InputSection.h"
-#include "OutputSections.h"
 #include "llvm/ADT/SmallPtrSet.h"
 
 namespace lld {
 namespace elf {
 
 // .MIPS.abiflags section.
 template <class ELFT>
 class MipsAbiFlagsSection final : public InputSection<ELFT> {
public:
   size_t getRelativeRelocCount() const { return NumRelativeRelocs; }
 
 private:
   bool Sort;
   size_t NumRelativeRelocs = 0;
   std::vector<DynamicReloc<ELFT>> Relocs;
 };
 
+struct SymbolTableEntry {
+  SymbolBody *Symbol;
+  size_t StrTabOffset;
+};
+
 template <class ELFT>
 class SymbolTableSection final : public SyntheticSection<ELFT> {
 public:
   typedef typename ELFT::Shdr Elf_Shdr;
   typedef typename ELFT::Sym Elf_Sym;
   typedef typename ELFT::SymRange Elf_Sym_Range;
   typedef typename ELFT::uint uintX_t;
   SymbolTableSection(StringTableSection<ELFT> &StrTabSec);
private:
   void writeGlobalSymbols(uint8_t *Buf);
 
   const OutputSectionBase *getOutputSection(SymbolBody *Sym);
 
   // A vector of symbols and their string table offsets.
   std::vector<SymbolTableEntry> Symbols;
 };
 
+// Outputs GNU Hash section. For detailed explanation see:
+// https://blogs.oracle.com/ali/entry/gnu_hash_elf_sections
+template <class ELFT>
+class GnuHashTableSection final : public SyntheticSection<ELFT> {
+  typedef typename ELFT::Off Elf_Off;
+  typedef typename ELFT::Word Elf_Word;
+  typedef typename ELFT::uint uintX_t;
+
+public:
+  GnuHashTableSection();
+  void finalize() override;
+  void writeTo(uint8_t *Buf) override;
+  size_t getSize() const override { return this->Size; }
+
+  // Adds symbols to the hash table.
+  // Sorts the input to satisfy GNU hash section requirements.
+  void addSymbols(std::vector<SymbolTableEntry> &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 SymbolData {
+    SymbolBody *Body;
+    size_t STName;
+    uint32_t Hash;
+  };
+
+  std::vector<SymbolData> Symbols;
+
+  unsigned MaskWords;
+  unsigned NBuckets;
+  unsigned Shift2;
+  uintX_t Size = 0;
+};
+
 template <class ELFT> InputSection<ELFT> *createCommonSection();
 template <class ELFT> InputSection<ELFT> *createInterpSection();
 template <class ELFT> MergeInputSection<ELFT> *createCommentSection();
 
 // Linker generated sections which can be used as inputs.
 template <class ELFT> struct In {
   static BuildIdSection<ELFT> *BuildId;
   static InputSection<ELFT> *Common;
   static DynamicSection<ELFT> *Dynamic;
   static StringTableSection<ELFT> *DynStrTab;
   static SymbolTableSection<ELFT> *DynSymTab;
+  static GnuHashTableSection<ELFT> *GnuHashTab;
   static GotSection<ELFT> *Got;
   static MipsGotSection<ELFT> *MipsGot;
   static GotPltSection<ELFT> *GotPlt;
   static InputSection<ELFT> *Interp;
   static MipsAbiFlagsSection<ELFT> *MipsAbiFlags;
   static MipsOptionsSection<ELFT> *MipsOptions;
   static MipsReginfoSection<ELFT> *MipsReginfo;
   static RelocationSection<ELFT> *RelaDyn;
   static RelocationSection<ELFT> *RelaPlt;
   static StringTableSection<ELFT> *ShStrTab;
   static StringTableSection<ELFT> *StrTab;
   static SymbolTableSection<ELFT> *SymTab;
 };
 
 template <class ELFT> BuildIdSection<ELFT> *In<ELFT>::BuildId;
 template <class ELFT> InputSection<ELFT> *In<ELFT>::Common;
 template <class ELFT> DynamicSection<ELFT> *In<ELFT>::Dynamic;
 template <class ELFT> StringTableSection<ELFT> *In<ELFT>::DynStrTab;
 template <class ELFT> SymbolTableSection<ELFT> *In<ELFT>::DynSymTab;
+template <class ELFT> GnuHashTableSection<ELFT> *In<ELFT>::GnuHashTab;
 template <class ELFT> GotSection<ELFT> *In<ELFT>::Got;
 template <class ELFT> MipsGotSection<ELFT> *In<ELFT>::MipsGot;
 template <class ELFT> GotPltSection<ELFT> *In<ELFT>::GotPlt;
 template <class ELFT> InputSection<ELFT> *In<ELFT>::Interp;
 template <class ELFT> MipsAbiFlagsSection<ELFT> *In<ELFT>::MipsAbiFlags;
 template <class ELFT> MipsOptionsSection<ELFT> *In<ELFT>::MipsOptions;
 template <class ELFT> MipsReginfoSection<ELFT> *In<ELFT>::MipsReginfo;
 template <class ELFT> RelocationSection<ELFT> *In<ELFT>::RelaDyn;
 template <class ELFT> RelocationSection<ELFT> *In<ELFT>::RelaPlt;
 template <class ELFT> StringTableSection<ELFT> *In<ELFT>::ShStrTab;
 template <class ELFT> StringTableSection<ELFT> *In<ELFT>::StrTab;
 template <class ELFT> SymbolTableSection<ELFT> *In<ELFT>::SymTab;
 } // namespace elf
 } // namespace lld
 
 #endif

lld/trunk/ELF/SyntheticSections.cpp

add({Config->EMachine == EM_MIPS ? DT_MIPS_PLTGOT : DT_PLTGOT,
          In<ELFT>::GotPlt});
     add({DT_PLTREL, uint64_t(Config->Rela ? DT_RELA : DT_REL)});
   }
 
   add({DT_SYMTAB, In<ELFT>::DynSymTab});
   add({DT_SYMENT, sizeof(Elf_Sym)});
   add({DT_STRTAB, In<ELFT>::DynStrTab});
   add({DT_STRSZ, In<ELFT>::DynStrTab->getSize()});
-  if (Out<ELFT>::GnuHashTab)
-    add({DT_GNU_HASH, Out<ELFT>::GnuHashTab});
+  if (In<ELFT>::GnuHashTab)
+    add({DT_GNU_HASH, In<ELFT>::GnuHashTab});
   if (Out<ELFT>::HashTab)
     add({DT_HASH, Out<ELFT>::HashTab});
 
   if (Out<ELFT>::PreinitArray) {
     add({DT_PREINIT_ARRAY, Out<ELFT>::PreinitArray});
     add({DT_PREINIT_ARRAYSZ, Out<ELFT>::PreinitArray, Entry::SecSize});
   }
   if (Out<ELFT>::InitArray) {
template <class ELFT> void SymbolTableSection<ELFT>::finalize() {
   if (!StrTabSec.isDynamic()) {
     std::stable_sort(Symbols.begin(), Symbols.end(),
                      [](const SymbolTableEntry &L, const SymbolTableEntry &R) {
                        return getSymbolBinding(L.Symbol) == STB_LOCAL &&
                               getSymbolBinding(R.Symbol) != STB_LOCAL;
                      });
     return;
   }
-  if (Out<ELFT>::GnuHashTab)
+  if (In<ELFT>::GnuHashTab)
     // NB: It also sorts Symbols to meet the GNU hash table requirements.
-    Out<ELFT>::GnuHashTab->addSymbols(Symbols);
+    In<ELFT>::GnuHashTab->addSymbols(Symbols);
   else if (Config->EMachine == EM_MIPS)
     std::stable_sort(Symbols.begin(), Symbols.end(),
                      [](const SymbolTableEntry &L, const SymbolTableEntry &R) {
                        return sortMipsSymbols(L.Symbol, R.Symbol);
                      });
   size_t I = 0;
   for (const SymbolTableEntry &S : Symbols)
     S.Symbol->DynsymIndex = ++I;
SymbolTableSection<ELFT>::getOutputSection(SymbolBody *Sym) {
   case SymbolBody::UndefinedKind:
   case SymbolBody::LazyArchiveKind:
   case SymbolBody::LazyObjectKind:
     break;
   }
   return nullptr;
 }
 
+template <class ELFT>
+GnuHashTableSection<ELFT>::GnuHashTableSection()
+    : SyntheticSection<ELFT>(SHF_ALLOC, SHT_GNU_HASH, sizeof(uintX_t),
+                             ".gnu.hash") {
+  this->Entsize = ELFT::Is64Bits ? 0 : 4;
+}
+
+template <class ELFT>
+unsigned GnuHashTableSection<ELFT>::calcNBuckets(unsigned NumHashed) {
+  if (!NumHashed)
+    return 0;
+
+  // These values are prime numbers which are not greater than 2^(N-1) + 1.
+  // In result, for any particular NumHashed we return a prime number
+  // which is not greater than NumHashed.
+  static const unsigned Primes[] = {
+      1,   1,    3,    3,    7,    13,    31,    61,    127,   251,
+      509, 1021, 2039, 4093, 8191, 16381, 32749, 65521, 131071};
+
+  return Primes[std::min<unsigned>(Log2_32_Ceil(NumHashed),
+                                   array_lengthof(Primes) - 1)];
+}
+
+// Bloom filter estimation: at least 8 bits for each hashed symbol.
+// GNU Hash table requirement: it should be a power of 2,
+//   the minimum value is 1, even for an empty table.
+// Expected results for a 32-bit target:
+//   calcMaskWords(0..4)   = 1
+//   calcMaskWords(5..8)   = 2
+//   calcMaskWords(9..16)  = 4
+// For a 64-bit target:
+//   calcMaskWords(0..8)   = 1
+//   calcMaskWords(9..16)  = 2
+//   calcMaskWords(17..32) = 4
+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() {
+  unsigned NumHashed = Symbols.size();
+  NBuckets = calcNBuckets(NumHashed);
+  MaskWords = calcMaskWords(NumHashed);
+  // Second hash shift estimation: just predefined values.
+  Shift2 = ELFT::Is64Bits ? 6 : 5;
+
+  this->OutSec->Entsize = this->Entsize;
+  this->OutSec->Link = this->Link = In<ELFT>::DynSymTab->OutSec->SectionIndex;
+  this->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 (Symbols.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++ = In<ELFT>::DynSymTab->getNumSymbols() - Symbols.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 SymbolData &Sym : Symbols) {
+    size_t Pos = (Sym.Hash / C) & (MaskWords - 1);
+    uintX_t V = (uintX_t(1) << (Sym.Hash % C)) |
+                (uintX_t(1) << ((Sym.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 SymbolData &Sym : Symbols) {
+    int Bucket = Sym.Hash % NBuckets;
+    assert(PrevBucket <= Bucket);
+    if (Bucket != PrevBucket) {
+      Buckets[Bucket] = Sym.Body->DynsymIndex;
+      PrevBucket = Bucket;
+      if (I > 0)
+        Values[I - 1] |= 1;
+    }
+    Values[I] = Sym.Hash & ~1;
+    ++I;
+  }
+  if (I > 0)
+    Values[I - 1] |= 1;
+}
+
+static uint32_t hashGnu(StringRef Name) {
+  uint32_t H = 5381;
+  for (uint8_t C : Name)
+    H = (H << 5) + H + C;
+  return H;
+}
+
+// Add symbols to this symbol hash table. Note that this function
+// destructively sort a given vector -- which is needed because
+// GNU-style hash table places some sorting requirements.
+template <class ELFT>
+void GnuHashTableSection<ELFT>::addSymbols(std::vector<SymbolTableEntry> &V) {
+  // Ideally this will just be 'auto' but GCC 6.1 is not able
+  // to deduce it correctly.
+  std::vector<SymbolTableEntry>::iterator Mid =
+      std::stable_partition(V.begin(), V.end(), [](const SymbolTableEntry &S) {
+        return S.Symbol->isUndefined();
+      });
+  if (Mid == V.end())
+    return;
+  for (auto I = Mid, E = V.end(); I != E; ++I) {
+    SymbolBody *B = I->Symbol;
+    size_t StrOff = I->StrTabOffset;
+    Symbols.push_back({B, StrOff, hashGnu(B->getName())});
+  }
+
+  unsigned NBuckets = calcNBuckets(Symbols.size());
+  std::stable_sort(Symbols.begin(), Symbols.end(),
+                   [&](const SymbolData &L, const SymbolData &R) {
+                     return L.Hash % NBuckets < R.Hash % NBuckets;
+                   });
+
+  V.erase(Mid, V.end());
+  for (const SymbolData &Sym : Symbols)
+    V.push_back({Sym.Body, Sym.STName});
+}
+
 template InputSection<ELF32LE> *elf::createCommonSection();
 template InputSection<ELF32BE> *elf::createCommonSection();
 template InputSection<ELF64LE> *elf::createCommonSection();
 template InputSection<ELF64BE> *elf::createCommonSection();
 
 template InputSection<ELF32LE> *elf::createInterpSection();
 template InputSection<ELF32BE> *elf::createInterpSection();
 template InputSection<ELF64LE> *elf::createInterpSection();

 template class elf::RelocationSection<ELF32BE>;
 template class elf::RelocationSection<ELF64LE>;
 template class elf::RelocationSection<ELF64BE>;
 
 template class elf::SymbolTableSection<ELF32LE>;
 template class elf::SymbolTableSection<ELF32BE>;
 template class elf::SymbolTableSection<ELF64LE>;
 template class elf::SymbolTableSection<ELF64BE>;
+
+template class elf::GnuHashTableSection<ELF32LE>;
+template class elf::GnuHashTableSection<ELF32BE>;
+template class elf::GnuHashTableSection<ELF64LE>;
+template class elf::GnuHashTableSection<ELF64BE>;

lld/trunk/ELF/Writer.cpp

template <class ELFT> void Writer<ELFT>::createSyntheticSections() {
   if (!Symtab<ELFT>::X->getSharedFiles().empty() || Config->Pic) {
     In<ELFT>::DynSymTab = make<SymbolTableSection<ELFT>>(*In<ELFT>::DynStrTab);
   }
 
   if (Config->EhFrameHdr)
     Out<ELFT>::EhFrameHdr = make<EhFrameHeader<ELFT>>();
 
   if (Config->GnuHash)
-    Out<ELFT>::GnuHashTab = make<GnuHashTableSection<ELFT>>();
+    In<ELFT>::GnuHashTab = make<GnuHashTableSection<ELFT>>();
   if (Config->SysvHash)
     Out<ELFT>::HashTab = make<HashTableSection<ELFT>>();
   if (Config->GdbIndex)
     Out<ELFT>::GdbIndex = make<GdbIndexSection<ELFT>>();
 
   In<ELFT>::RelaPlt = make<RelocationSection<ELFT>>(
       Config->Rela ? ".rela.plt" : ".rel.plt", false /*Sort*/);
   if (Config->Strip != StripPolicy::All) {
template <class ELFT> void Writer<ELFT>::finalizeSections() {
   sortSections();
 
   unsigned I = 1;
   for (OutputSectionBase *Sec : OutputSections) {
     Sec->SectionIndex = I++;
     Sec->ShName = In<ELFT>::ShStrTab->addString(Sec->getName());
   }
 
-  // FIXME: this should be removed after converting GnuHashTableSection
-  // to input section.
-  // Finalizers fix each section's size.
-  // .dynsym is finalized early since that may fill up .gnu.hash.
-  finalizeSynthetic<ELFT>({In<ELFT>::DynSymTab});
-
   // Fill other section headers. The dynamic table is finalized
   // at the end because some tags like RELSZ depend on result
   // of finalizing other sections.
   for (OutputSectionBase *Sec : OutputSections)
     Sec->finalize();
 
-  // Dynamic section must be the last one in this list.
+  // Dynamic section must be the last one in this list and dynamic
+  // symbol table section (DynSymTab) must be the first one.
   finalizeSynthetic<ELFT>(
-      {In<ELFT>::SymTab, In<ELFT>::ShStrTab, In<ELFT>::StrTab,
-       In<ELFT>::DynStrTab, In<ELFT>::Got, In<ELFT>::MipsGot, In<ELFT>::GotPlt,
-       In<ELFT>::RelaDyn, In<ELFT>::RelaPlt, In<ELFT>::Dynamic});
+      {In<ELFT>::DynSymTab, In<ELFT>::GnuHashTab, In<ELFT>::SymTab,
+       In<ELFT>::ShStrTab, In<ELFT>::StrTab, In<ELFT>::DynStrTab, In<ELFT>::Got,
+       In<ELFT>::MipsGot, In<ELFT>::GotPlt, In<ELFT>::RelaDyn,
+       In<ELFT>::RelaPlt, In<ELFT>::Dynamic});
 }
 
 template <class ELFT> bool Writer<ELFT>::needsGot() {
   // We add the .got section to the result for dynamic MIPS target because
   // its address and properties are mentioned in the .dynamic section.
   if (Config->EMachine == EM_MIPS)
     return !Config->Relocatable;
 
if (In<ELFT>::DynSymTab) {
 
     bool HasVerNeed = Out<ELFT>::VerNeed->getNeedNum() != 0;
     if (Out<ELFT>::VerDef || HasVerNeed)
       Add(Out<ELFT>::VerSym);
     Add(Out<ELFT>::VerDef);
     if (HasVerNeed)
       Add(Out<ELFT>::VerNeed);
 
-    Add(Out<ELFT>::GnuHashTab);
+    addInputSec(In<ELFT>::GnuHashTab);
     Add(Out<ELFT>::HashTab);
     addInputSec(In<ELFT>::Dynamic);
     addInputSec(In<ELFT>::DynStrTab);
     if (In<ELFT>::RelaDyn->hasRelocs())
       addInputSec(In<ELFT>::RelaDyn);
     Add(Out<ELFT>::MipsRldMap);
   }