[ELF2] Add support for Gnu Hash section

[ikudrin]

Summary

This patch implements --hash-style command line switch.

• By default, or with "sysv" or "both" parameters the linker generates a standard ELF hash section.
• With "gnu" or "both" it produces Gnu-style hash section.

Support for that section requires symbols in the dynamic symbol table section to be divided in
two groups (not hashed and hashed symbols) and the last group have to be sorted to correspond
the hash table of the Gnu Hash section.

The division function, as well as estimations for the section's parameters, are just the first rough
variants and the subjects for further adjustments.

[ruiu]

First round of comments.

ELF/Config.h

54–55

Let's name them GnuHash and SysvHash.

ELF/OutputSections.cpp

235

Remove unsigned.

248–249

What is this condition for?

257–278

Where does this implementation come from?

287–288

Can you return here if empty?

848–855

What is this change for?

ELF/OutputSections.h

322

Remove this line.

331

I'd name this Primes.

332

Remove this. You can use sizeof(Primes) / sizeof(Prime[0]).

354

Rename this SysvHashTab.

[ruiu]

Re-submitting to let Phab to send out a mail...

[ruiu]

ELF/OutputSections.h

59–61

I'm wondering if we really need two distinct functions for the traditional hash table and GNU's. GNU hash table is smaller than the traditional one because it omits some symbols. Technically, such symbols can be removed from the traditional hash table without hurting correctness.

[ikudrin]

ELF/OutputSections.cpp

248–249

It may be rewritten as (Is64Bits ? 0 : 4), but my variant shows the reason for this, I hope.
See http://sourceware.org/ml/binutils/2006-10/msg00377.html:

The .gnu.hash section uses sh_entsize 4 for 32-bit ELF and sh_entsize 0
for 64-bit ELF (as it has then non-uniform entity size; 4 32-bit words,
variable count of ELFCLASS sized words and then variable count of 32-bit
words; it doesn't repeat the historic mistakes on Alpha/s390x with .hash).

257–278

I've just selected prime numbers which are not greater than lower bound of each range. Haven't done any deep investigations, it just looks reasonable for the first try.

848–855

Gnu hash section requires reordering of dynamic symbol table entries. If Gnu hash section is in action, it sets correct indexes in its finalize() method; otherwise, indexes just follow the original order. So, in case of a dynamic symbol table, we write the entry right into its place without any additional sorting.

ELF/OutputSections.h

59–61

It sounds reasonable, but I tried to make this patch to solve just one problem. You may notice that all existent tests are still intact. We may optimize a traditional hash section in a separate patch.

[ikudrin]

• Rebased to the top.
• Addressed comments.

[• rafael]

+template <class ELFT>
+const unsigned GnuHashTableSection<ELFT>::NBucketsEstimation[] = {
+ 1, 0.. 1
+ 1, 2
+ 3, 3.. 4
+ 3, 5.. 8
+ 7, 9.. 16
+ 13, 17.. 32
+ 31, 33.. 64
+ 61, 65.. 128
+ 127, 129.. 256
+ 251, 257.. 512
+ 509, 513.. 1024
+ 1021, 1025.. 2048
+ 2039, 2049.. 4096
+ 4093, 4097.. 8192
+ 8191, 8193.. 16384
+ 16381, 16385.. 32768
+ 32749, 32769.. 65536
+ 65521, 65537..131072
+ 131071 // 131073..
+};

+

ruiu wrote:

Where does this implementation come from?

I've just selected prime numbers which are not greater than lower bound of each range. Haven't done any deep investigations, it just looks reasonable for the first try.

Please add that as a comment.

Cheers,
Rafael

[• rafael]

ELF/OutputSections.cpp

199

This is being removed because the symbols have to be sorted, right?

It is a bit untidy that we now call setDynamicSymbolTableIndex from two places.

Maybe organize this as:

• In the current loop: Out<ELFT>::DynSymTab->addSymbol(...)
• Sort the DynSymTab if needed.
• Walk the DynSymTab, calling setDynamicSymbolTableIndex and adding the symbol to one or both hash tables.

ELF/OutputSections.h

338

Most of these members are named after the section name in the output file, so I would keep the old name.

[• rafael]

ELF/OutputSections.h

62

Optimizing the sysv hash is a good thing, but lets do it in another patch (before or after this one).

177

Independent change, no? If so, please commit it and rebase.

[ikudrin]

ELF/OutputSections.cpp

199

I consider the main reason to remove this function as it is not a hash table's responsibility to fill up a dynamic symbol table.

I like the idea to sort entries of a symbol table within the symbol table class, but in case of the Gnu hash section, it imposes not only some requirements to the order of entries, but also the oreder itself, as it is calculated using hash values and NBuckets parameter. I can't find a better solution than sorting the symbols which belongs to Gnu Hash table within the GnuHashTableSection class.

[ikudrin]

ELF/OutputSections.cpp

199

One more thing. If we implement one method to sort the entire dynamic symbol table and set indexes of the entries, we have to decide, when it should be called. The right place to call thist sort function might be the finalize() method of the symbol table class. But the sort function will require some information, which can only be provided by the Gnu hash table class, and the right place to calculate it is the finalize() method of this class. I don't think it's a good idea to rely on the order of calling of finalize() methods.

[• rafael]

I like the idea to sort entries of a symbol table within the symbol table class, but in case of the Gnu hash section, it imposes not only some requirements to the order of entries, but also the oreder itself, as it is calculated using hash values and NBuckets parameter. I can't find a better solution than sorting the symbols which belongs to Gnu Hash table within the GnuHashTableSection class.

One more thing. If we implement one method to sort the entire dynamic symbol table and set indexes of the entries, we have to decide, when it should be called. The right place to call thist sort function might be the finalize() method of the symbol table class. But the sort function will require some information, which can only be provided by the Gnu hash table class, and the right place to calculate it is the finalize() method of this class. I don't think it's a good idea to rely on the order of calling of finalize() methods.

What about:

• In the current loop: Out<ELFT>::DynSymTab->addSymbol(...)
• Sort the DynSymTab if needed: if (Out<ELFT>::GnuHashTab) GnuHashTable<ELFT>::sortDynamicSymbols()

• Walk the DynSymTab, calling setDynamicSymbolTableIndex and adding

the symbol to one or both hash tables.

[ikudrin]

What about:

• In the current loop: Out<ELFT>::DynSymTab->addSymbol(...)
• Sort the DynSymTab if needed: if (Out<ELFT>::GnuHashTab) GnuHashTable<ELFT>::sortDynamicSymbols()

• Walk the DynSymTab, calling setDynamicSymbolTableIndex and adding

the symbol to one or both hash tables.

I've almost done a new variant which is close to your suggestion, I hope. Let's look at it.

[ikudrin]

• Implemented the new approach to sort symbols within a symbol table. All symbols are added to symbol tables which are responsible for sorting them in the correct order, taking into account all requirements.

NB. If this approach is recognized as acceptable, I think it will be better to commit it in a separate patch.

[ruiu]

ELF/OutputSections.cpp

235

My previous comment is probably wrong. You may want to use uint8_t here.

248–249

OK, thank you for the explanation. I'd prefer Is64Bits ? 0 : 4, as that's what we want.

250

This is always 2, no? Is this correct?

259–277

Remove comments and write them in one line (or two), and add a comment saying that these numbers are the smallest numbers that are not smaller than 2^n.

303

Use llvm::array_lengthof().

309

Remove ';'

312

HashedSymbols.begin(), HashedSymbols.end(),

314–316

return L.Hash % NBuckets < R.Hash % NBuckets;

344

CHAR_BIT is always 8, so write 8. Drop 'static const' -- it is static const but the compiler can easily figure that out.

349

You can directly write (MaskWords - 1) here.

350–351

You can just write 1 because RHS's type of << is the same as the result's type.

359–360

Drop const.

360

auto -> unsigned

362

Please add a reference to the data structure this code is trying to create.

362–364

signed -> int

366

signed -> int

370

1u -> 1

374

HashMask -> ~1

ELF/OutputSections.h

331

Rename this Symbols because all symbols handled by this class are subject of calculation of hash values (so it is redundant).

338

Hm, makes sense.

ELF/Writer.cpp

502

Why do we have to call setDynamicSymbolTableIndex here? That's not obvious.

[ikudrin]

ELF/OutputSections.cpp

250

Hmm, no. It's 8 on 64-bit platform and 4 on 32-bit.

360

It's not unsigned but Elf_Word.

ELF/Writer.cpp

502

Please see my last patch, it's straightforward on that question.

[ruiu]

ELF/OutputSections.cpp

246

Can you then use uintX_t instead of Elf_Off? Elf_Off is, strictly speaking, probably better type, but I think in practice we don't want to distinguish them.

248–249

Can you do this?

ELF/OutputSections.h

164

This name doesn't feel a correct one. Does this return the number of dynamically-linked symbols? Does this return the GNU-style hash table size?

282–284

Sort

[ikudrin]

ELF/OutputSections.cpp

248–249

I'll make the change in the next update.

[ikudrin]

ELF/OutputSections.cpp

246

I don't think sizeof(uintX_t) is relevant here as we don't use that type to store values. Maybe it's better to use (Is64Bins ? 8 : 4) to be in sync with the previous line.

ELF/OutputSections.h

164

Is "getNumGnuHashed()" a better variant? Any suggestions are welcome.

[ikudrin]

Addressed review comments.

[llvm-commits]

Rebased patch attached. I did a merge to review the patch.

• t.diff27 KBDownload
• msg-13923-217.txt162 BDownload

[• rafael]

ELF/OutputSections.cpp

237

Given that you are using a uint32_t, this is a nop, no?

270

The expression is always bigger than 1, no?
Also, given the comment, should it be

RoundUpToAlignment(NumHashed, sizeof(Elf_Off))/sizeof(Elf_Off)?

292

Maybe pass a reference to writeHeader and others so that you don't have to also increment the buf pointer in here?

335

This means that the entries in Bucket are inedxes into the Value vector.

According to https://blogs.oracle.com/ali/entry/gnu_hash_elf_sections, they are indexes into the dynamic symbol table, so in here you would have to add the number of non-hashed symbols.

Is that reference wrong?

760

You are also sorting the non dynamic symbols, right?

I t is probably cleaner if there are two independent sorts, with just the constraints that each section has

if (!StrTabSec.isDynamic()) {
simple sort on just getBinding() == STB_LOCAL.
return;
}
The more complicated sort for the dynamic table.

907

Adding getSymbolBinding is a nice implement on its own. Please commit and rebase.

[ikudrin]

ELF/OutputSections.cpp

237

Thanks for reminding. The reference implementation uses uint_fast32_t, I think we should do the same.

907

Please check it: http://reviews.llvm.org/D13910

[ruiu]

ELF/Driver.cpp

159

I'd name this just "S".

ELF/OutputSections.cpp

237

Unlike uint_fast32_t, uint32_t is always 32-bit. You don't need this mask.

246

Yeah, this looks better than before.

256

Let's remove this line. This implementation should be good enough (not only as a first try).

258–259

No need to align them vertically.

315–317

It's probably better to split this into multiple statements.

size_t Pos = (Item.GnuHash / C) & (MaskWords - 1);
Elf_Off V = uintX_t(1) << (Item.GnuHash % C) | uintX_t(1) << ((Item.GnuHash >> Shift2) % C);
Mask[Pos] |= V;

ELF/OutputSections.h

62

Agreed.

280

Gnu -> GNU

[ikudrin]

ELF/OutputSections.cpp

237

Yep, but I'd prefer to replace the H's type with uint_fast32_t. What do you think?

258–259

It's what clang-format does.

[ruiu]

ELF/OutputSections.cpp

237

I don't prefer to use uint_fast32_t. I don't expect that would make any observable difference because I think the type would be mapped to uint32_t. In addition to that, the type is used so rarely that that would make the code look a bit odd. (If you are a reader, you'd have to stop and think about the type.)

[ikudrin]

ELF/OutputSections.cpp

237

OK.

[ikudrin]

The part of the patch was extracted as a separate change http://reviews.llvm.org/D13911.

• Rebased on the top.
• Bugfix: index of the symbol in the hash values part.
• Addressed the other comments.

[ikudrin]

ELF/OutputSections.cpp

270

Thank you for the suggestion, it looks much better now.

335

Shame on me, you are absolutely correct.

[ruiu]

ELF/OutputSections.cpp

313–314

It's better to parenthesize uintX_t(1) << (Item.GnuHash % C) and uintX_t(1) << ((Item.GnuHash >> Shift2) % C). Not everybody remembers the operator precedence table precisely.

325–342

This part of code is a bit hard to read because too many local variables are used and they look similar. Let's use less variables and make their name shorter.

int PrevHash = -1;
int I = 0;
for (const typename SymbolTableSection<ELFT>::SymbolData &Item :
     Out<ELFT>::DynSymTab->getGnuHashSymbols()) {
  int Hash = Item.GnuHash % NBuckets;
  if (Hash != PrevHash) {
    if (I > 0)
      Values[I - 1] |= 1;
    Buckets[Hash] = Item.Body->getDynamicSymbolTableIndex();
    PrevHash = Hash;
  }
  Values[I] = Item.GnuHash & ~1;
  ++I;
}
if (I > 0)
  Values[I - 1] |= 1;

ELF/OutputSections.h

177

I'd name this HasGnuHash.

[ikudrin]

• Corrected calculation of MaskWords.
• Simplified hash fill loop.
• Addressed other comments.

[ikudrin]

ELF/OutputSections.cpp

270

On the fresh look, I've forgotten about the requirement for this value to be a power of 2.

[• rafael]

ELF/OutputSections.cpp

270

Why the -1?
Why the static_cast?

[ikudrin]

ELF/OutputSections.cpp

270

For 64-bit target: calcMaskWords(0..8) = 1, calcMaskWords(9..16) = 2, calcMaskWords(17..32) = 4... I feel like it'd be better to have a unit test here.

The return type of NextPowerOf2 is uint64_t. I try to avoid a potential warning here about value truncation.

[• rafael]

ELF/OutputSections.cpp

270

OK, I missed the fact that NextPowerOf returns the power of 2 that is grater, not greater or equal.

Can you add your example as a comment?

[ikudrin]

Added an explanatory comment for calcMaskWords() method.

[ruiu]

LGTM

There might be room to improve code even more, but this is I think already good enough. As long as readers understand the structure of .gnu.hash section, this code feels straightforward.

[• rafael]

LGTM for me too.

[ikudrin]

Thank you for all the comments.

ELF/Config.h

struct Configuration {
   bool AllowMultipleDefinition;
   bool AsNeeded = false;
   bool Bsymbolic;
   bool DiscardAll;
   bool DiscardLocals;
   bool DiscardNone;
   bool EnableNewDtags;
   bool ExportDynamic;
+  bool GnuHash = false;
   bool Mips64EL = false;
   bool NoInhibitExec;
   bool NoUndefined;
   bool Shared;
   bool Static = false;
+  bool SysvHash = true;
   bool Verbose;
   bool ZNodelete = false;
   bool ZNow = false;
   ELFKind EKind = ELFNoneKind;
   uint16_t EMachine = llvm::ELF::EM_NONE;
   uint64_t EntryAddr = -1;
 };
 
 extern Configuration *Config;
 
 } // namespace elf2
 } // namespace lld
 
 #endif

ELF/Driver.cpp

void LinkerDriver::createFiles(opt::InputArgList &Args) {
   Config->DynamicLinker = getString(Args, OPT_dynamic_linker);
   Config->Entry = getString(Args, OPT_entry);
   Config->Fini = getString(Args, OPT_fini, "_fini");
   Config->Init = getString(Args, OPT_init, "_init");
   Config->OutputFile = getString(Args, OPT_o);
   Config->SoName = getString(Args, OPT_soname);
   Config->Sysroot = getString(Args, OPT_sysroot);
 
+  if (auto *Arg = Args.getLastArg(OPT_hash_style)) {
+    StringRef Style = Arg->getValue();
+    if (Style == "gnu") {
+      Config->GnuHash = true;
+      Config->SysvHash = false;
+    } else if (Style == "both") {
+      Config->GnuHash = true;
+    } else if (Style != "sysv")
+      error("Unknown hash style: " + Style);
+  }
+
   for (auto *Arg : Args.filtered(OPT_undefined))
     Config->Undefined.push_back(Arg->getValue());
 
   // FIXME: Group -z options together in Config.
   for (auto *Arg : Args.filtered(OPT_z)) {
     if (Arg->getValue() == StringRef("nodelete"))
       Config->ZNodelete = true;
     else if (Arg->getValue() == StringRef("now"))

ELF/Options.td

def entry : Separate<["--", "-"], "entry">, MetaVarName<"<entry>">,
   HelpText<"Name of entry point symbol">;
 
 def export_dynamic : Flag<["--", "-"], "export-dynamic">,
   HelpText<"Put symbols in the dynamic symbol table">;
 
 def fini : Separate<["-"], "fini">, MetaVarName<"<symbol>">,
   HelpText<"Specify a finalizer function">;
 
+def hash_style : Separate<["--", "-"], "hash-style">,
+  HelpText<"Specify hash style (sysv, gnu or both)">;
+
 def init : Separate<["-"], "init">, MetaVarName<"<symbol>">,
   HelpText<"Specify an initializer function">;
 
 def l : Joined<["-"], "l">, MetaVarName<"<libName>">,
   HelpText<"Root name of library to use">;
 
 def m : Separate<["-"], "m">,
   HelpText<"Set target emulation">;

 def alias_Bstatic_dn: Flag<["-"], "dn">, Alias<Bstatic>;
 def alias_Bstatic_non_shared: Flag<["-"], "non_shared">, Alias<Bstatic>;
 def alias_Bstatic_static: Flag<["-"], "static">, Alias<Bstatic>;
 def alias_L__library_path : Joined<["--"], "library-path=">, Alias<L>;
 def alias_discard_all_x: Flag<["-"], "x">, Alias<discard_all>;
 def alias_discard_locals_X: Flag<["-"], "X">, Alias<discard_locals>;
 def alias_entry_e : Separate<["-"], "e">, Alias<entry>;
 def alias_fini_fini : Joined<["-"], "fini=">, Alias<fini>;
+def alias_hash_style_hash_style : Joined<["--", "-"], "hash-style=">, Alias<hash_style>;
 def alias_init_init : Joined<["-"], "init=">, Alias<init>;
 def alias_l__library : Joined<["--"], "library=">, Alias<l>;
 def alias_o_output : Joined<["--"], "output=">, Alias<o>;
 def alias_rpath_rpath : Joined<["-"], "rpath=">, Alias<rpath>;
 def alias_shared_Bshareable : Flag<["-"], "Bshareable">, Alias<shared>;
 def alias_soname_h : Separate<["-"], "h">, Alias<soname>;
 def alias_soname_soname : Separate<["-"], "soname">, Alias<soname>;
 def alias_script_T : Separate<["-"], "T">, Alias<script>;
 def alias_undefined_u : Separate<["-"], "u">, Alias<undefined>;
 
 // Options listed below are silently ignored now.
 def O3 : Flag<["-"], "O3">;
 def build_id : Flag<["--"], "build-id">;
 def eh_frame_hdr : Flag<["--"], "eh-frame-hdr">;
 def end_group : Flag<["--"], "end-group">;
 def fatal_warnings : Flag<["--"], "fatal-warnings">;
 def gc_sections : Flag<["--"], "gc-sections">;
-def hash_style : Joined<["--"], "hash-style=">;
 def no_add_needed : Flag<["--"], "no-add-needed">;
 def no_fatal_warnings : Flag<["--"], "no-fatal-warnings">;
 def no_warn_mismatch : Flag<["--"], "no-warn-mismatch">;
 def start_group : Flag<["--"], "start-group">;
 def strip_all : Flag<["--"], "strip-all">;
 def version_script : Separate<["--"], "version-script">;
 def warn_common : Flag<["--"], "warn-common">;
 def warn_shared_textrel : Flag<["--"], "warn-shared-textrel">;

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);
 
 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
 // input sections, others are created by the linker.
 // The writer creates multiple OutputSections and assign them unique,
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; }
+  unsigned getNumGnuHashSymbols() const { return NumGnuHashed; }
+
+  struct SymbolData {
+    SymbolData(SymbolBody *Body, bool GnuHashed);
+    SymbolBody *Body;
+    bool GnuHashed;
+    uint32_t GnuHash;
+  };
+  ArrayRef<SymbolData> getSymbols() const;
+  ArrayRef<SymbolData> getGnuHashSymbols() const;
 
 private:
   void writeLocalSymbols(uint8_t *&Buf);
   void writeGlobalSymbols(uint8_t *Buf);
 
+  static unsigned char getSymbolBinding(SymbolBody *Body);
+
   SymbolTable<ELFT> &Table;
   StringTableSection<ELFT> &StrTabSec;
+  std::vector<SymbolData> 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;
 

 };
 
 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;
+};
+
+// 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<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);
 
 private:
-  std::vector<uint32_t> Hashes;
+  static unsigned calcMaskWords(unsigned NumHashed);
+
+  void writeHeader(uint8_t *Buf);
+  void writeBloomFilter(uint8_t *Buf);
+  void writeHashTable(uint8_t *Buf);
+
+  unsigned MaskWords;
+  unsigned NBuckets;
+  unsigned Shift2;
 };
 
 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;
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Shdr Elf_Shdr;
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Sym Elf_Sym;
 
 public:
   DynamicSection(SymbolTable<ELFT> &SymTab);
   void finalize() override;
   void writeTo(uint8_t *Buf) override;
 
   OutputSectionBase<ELFT> *PreInitArraySec = nullptr;
   OutputSectionBase<ELFT> *InitArraySec = nullptr;
   OutputSectionBase<ELFT> *FiniArraySec = nullptr;
 
 private:
   SymbolTable<ELFT> &SymTab;
   const ELFSymbolBody<ELFT> *InitSym = nullptr;
   const ELFSymbolBody<ELFT> *FiniSym = nullptr;
 };
 
 // All output sections that are hadnled by the linker specially are
 // globally accessible. Writer initializes them, so don't use them
 // until Writer is initialized.
 template <class ELFT> struct Out {
   static DynamicSection<ELFT> *Dynamic;
+  static GnuHashTableSection<ELFT> *GnuHashTab;
   static GotSection<ELFT> *Got;
   static HashTableSection<ELFT> *HashTab;
   static InterpSection<ELFT> *Interp;
   static OutputSection<ELFT> *Bss;
   static OutputSectionBase<ELFT> *Opd;
   static uint8_t *OpdBuf;
   static PltSection<ELFT> *Plt;
   static RelocationSection<ELFT> *RelaDyn;
   static StringTableSection<ELFT> *DynStrTab;
   static StringTableSection<ELFT> *StrTab;
   static SymbolTableSection<ELFT> *DynSymTab;
   static SymbolTableSection<ELFT> *SymTab;
 };
 
 template <class ELFT> DynamicSection<ELFT> *Out<ELFT>::Dynamic;
+template <class ELFT> GnuHashTableSection<ELFT> *Out<ELFT>::GnuHashTab;
 template <class ELFT> GotSection<ELFT> *Out<ELFT>::Got;
 template <class ELFT> HashTableSection<ELFT> *Out<ELFT>::HashTab;
 template <class ELFT> InterpSection<ELFT> *Out<ELFT>::Interp;
 template <class ELFT> OutputSection<ELFT> *Out<ELFT>::Bss;
 template <class ELFT> OutputSectionBase<ELFT> *Out<ELFT>::Opd;
 template <class ELFT> uint8_t *Out<ELFT>::OpdBuf;
 template <class ELFT> PltSection<ELFT> *Out<ELFT>::Plt;
 template <class ELFT> RelocationSection<ELFT> *Out<ELFT>::RelaDyn;
 template <class ELFT> StringTableSection<ELFT> *Out<ELFT>::DynStrTab;
 template <class ELFT> StringTableSection<ELFT> *Out<ELFT>::StrTab;
 template <class ELFT> SymbolTableSection<ELFT> *Out<ELFT>::DynSymTab;
 template <class ELFT> SymbolTableSection<ELFT> *Out<ELFT>::SymTab;
 }
 }
 #endif

ELF/OutputSections.cpp

 //===- OutputSections.cpp -------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "OutputSections.h"
 #include "Config.h"
 #include "SymbolTable.h"
 #include "Target.h"
+#include "llvm/Support/MathExtras.h"
 
 using namespace llvm;
 using namespace llvm::object;
 using namespace llvm::support::endian;
 using namespace llvm::ELF;
 
 using namespace lld;
 using namespace lld::elf2;

 template <class ELFT>
 HashTableSection<ELFT>::HashTableSection()
     : OutputSectionBase<ELFT>(".hash", llvm::ELF::SHT_HASH,
                               llvm::ELF::SHF_ALLOC) {
   this->Header.sh_entsize = sizeof(Elf_Word);
   this->Header.sh_addralign = sizeof(Elf_Word);
 }
 
-static uint32_t hash(StringRef Name) {
+static uint32_t hashSysv(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;
 }
 
-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 (const typename SymbolTableSection<ELFT>::SymbolData &Item :
+       Out<ELFT>::DynSymTab->getSymbols()) {
+    SymbolBody *Body = Item.Body;
+    StringRef Name = Body->getName();
+    unsigned I = Body->getDynamicSymbolTableIndex();
+    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 & 0xffffffff;
+}
+
+template <class ELFT>
+GnuHashTableSection<ELFT>::GnuHashTableSection()
+    : OutputSectionBase<ELFT>(".gnu.hash", llvm::ELF::SHT_GNU_HASH,
+                              llvm::ELF::SHF_ALLOC) {
+  this->Header.sh_entsize = ELFT::Is64Bits ? 0 : 4;
+  this->Header.sh_addralign = ELFT::Is64Bits ? 8 : 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.
+  // No deep investigation was done, it just looks good for the first try.
+  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)];
+}
+
+template <class ELFT>
+unsigned GnuHashTableSection<ELFT>::calcMaskWords(unsigned NumHashed) {
+  if (!NumHashed)
+    return 1;
+  // Bloom filter estimation: at least 8 bits for each hashed symbol.
+  return std::max<unsigned>((1u << Log2_32_Ceil(NumHashed)) / sizeof(Elf_Off),
+                            1);
+}
+
+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) {
+  writeHeader(Buf);
+  if (!NBuckets) // There are no hashed symbols
+    return;
+  Buf += sizeof(Elf_Word) * 4;
+  writeBloomFilter(Buf);
+  Buf += sizeof(Elf_Off) * MaskWords;
+  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++ = MaskWords;
+  *P++ = Shift2;
+}
+
+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())
+    Masks[(Item.GnuHash / C) & (MaskWords - 1)] |=
+        (static_cast<uintX_t>(1) << (Item.GnuHash % C)) |
+        (static_cast<uintX_t>(1) << ((Item.GnuHash >> Shift2) % C));
+}
+
+template <class ELFT>
+void GnuHashTableSection<ELFT>::writeHashTable(uint8_t *Buf) {
+  Elf_Word *Buckets = reinterpret_cast<Elf_Word *>(Buf);
+  Elf_Word *Values = Buckets + NBuckets;
+
+  int PrevBucketIndex = -1;
+  int PrevValueIndex = -1;
+  int ValueIndex = 0;
+  for (const typename SymbolTableSection<ELFT>::SymbolData &Item :
+       Out<ELFT>::DynSymTab->getGnuHashSymbols()) {
+    int BucketIndex = Item.GnuHash % NBuckets;
+    assert(PrevBucketIndex <= BucketIndex);
+    if (BucketIndex != PrevBucketIndex) {
+      if (PrevValueIndex >= 0)
+        Values[PrevValueIndex] |= 1;
+      Buckets[BucketIndex] = ValueIndex + 1;
+      PrevBucketIndex = BucketIndex;
+    }
+    Values[ValueIndex] = Item.GnuHash & ~1;
+    PrevValueIndex = ValueIndex++;
+  }
+  if (PrevValueIndex >= 0)
+    Values[PrevValueIndex] |= 1;
+}
+
 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;
 }
 
 template <class ELFT> void DynamicSection<ELFT>::finalize() {
   if (this->Header.sh_size)
     return; // Already finalized.
 
   Elf_Shdr &Header = this->Header;
   Header.sh_link = Out<ELFT>::DynStrTab->SectionIndex;
 
   unsigned NumEntries = 0;
   if (Out<ELFT>::RelaDyn->hasRelocs()) {
     ++NumEntries; // DT_RELA / DT_REL
     ++NumEntries; // DT_RELASZ / DT_RELSZ
     ++NumEntries; // DT_RELAENT / DT_RELENT
   }
   ++NumEntries; // DT_SYMTAB
   ++NumEntries; // DT_SYMENT
   ++NumEntries; // DT_STRTAB
   ++NumEntries; // DT_STRSZ
+  if (Out<ELFT>::GnuHashTab)
+    ++NumEntries; // DT_GNU_HASH
+  if (Out<ELFT>::HashTab)
     ++NumEntries; // DT_HASH
 
   if (!Config->RPath.empty()) {
     ++NumEntries; // DT_RUNPATH / DT_RPATH
     Out<ELFT>::DynStrTab->add(Config->RPath);
   }
 
   if (!Config->SoName.empty()) {
     ++NumEntries; // DT_SONAME
if (Out<ELFT>::RelaDyn->hasRelocs()) {
     WriteVal(IsRela ? DT_RELAENT : DT_RELENT,
              IsRela ? sizeof(Elf_Rela) : sizeof(Elf_Rel));
   }
 
   WritePtr(DT_SYMTAB, Out<ELFT>::DynSymTab->getVA());
   WritePtr(DT_SYMENT, sizeof(Elf_Sym));
   WritePtr(DT_STRTAB, Out<ELFT>::DynStrTab->getVA());
   WriteVal(DT_STRSZ, Out<ELFT>::DynStrTab->data().size());
+  if (Out<ELFT>::GnuHashTab)
+    WritePtr(DT_GNU_HASH, Out<ELFT>::GnuHashTab->getVA());
+  if (Out<ELFT>::HashTab)
     WritePtr(DT_HASH, Out<ELFT>::HashTab->getVA());
 
   if (!Config->RPath.empty())
 
     // If --enable-new-dtags is set lld emits DT_RUNPATH
     // instead of DT_RPATH. The two tags are functionally
     // equivalent except for the following:
     // - DT_RUNPATH is searched after LD_LIBRARY_PATH, while
     // DT_RPATH is searched before.
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) {
+  // Assume that includeInDynamicSymtab() is already checked.
+  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 GnuHashed)
+    : Body(Body), GnuHashed(GnuHashed),
+      GnuHash(GnuHashed ? 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;
+
+  const unsigned NBuckets =
+      NumGnuHashed ? GnuHashTableSection<ELFT>::calcNBuckets(NumGnuHashed) : 0;
+  std::stable_sort(
+      Symbols.begin(), Symbols.end(),
+      [NBuckets](const SymbolData &L, const SymbolData &R) -> bool {
+        const bool LLocal = getSymbolBinding(L.Body) == STB_LOCAL;
+        const bool RLocal = getSymbolBinding(R.Body) == STB_LOCAL;
+        if (LLocal || RLocal)
+          return !RLocal;
+        if (!L.GnuHashed || !R.GnuHashed)
+          return R.GnuHashed;
+        return L.GnuHash % NBuckets < R.GnuHash % NBuckets;
+      });
+  if (StrTabSec.isDynamic()) {
+    // All symbols which belong to Gnu Hash section
+    // should be placed after not hashed symbols.
+    assert(std::is_sorted(Symbols.begin(), Symbols.end(),
+                          [](const SymbolData &L, const SymbolData &R) {
+                            return !L.GnuHashed && R.GnuHashed;
+                          }));
+    unsigned Index = 0;
+    for (const SymbolData &Item : Symbols) {
+      Item.Body->setDynamicSymbolTableIndex(++Index);
+    }
+  }
 }
 
 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());
+  const bool GnuHashed = StrTabSec.isDynamic() && Out<ELFT>::GnuHashTab &&
+                         includeInGnuHashTable(*Body);
+  Symbols.emplace_back(Body, GnuHashed);
+  ++NumVisible;
+  if (GnuHashed)
+    ++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())
     writeLocalSymbols(Buf);
 
for (const Elf_Sym &Sym : Syms) {
         VA += OutSec->getVA() + Section->getOffset(Sym);
       }
       ESym->st_value = VA;
     }
   }
 }
 
 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 (const SymbolData &Item : Symbols) {
+    SymbolBody *Body = Item.Body;
+    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:
       OutSec = &cast<DefinedSynthetic<ELFT>>(Body)->Section;
       break;
     case SymbolBody::DefinedRegularKind:
       Section = &cast<DefinedRegular<ELFT>>(Body)->Section;
       break;
     case SymbolBody::DefinedCommonKind:
       OutSec = Out<ELFT>::Bss;
       break;
     case SymbolBody::UndefinedKind:
     case SymbolBody::DefinedAbsoluteKind:
     case SymbolBody::SharedKind:
     case SymbolBody::LazyKind:
       break;
     }
 
-    unsigned char Binding = Body->isWeak() ? STB_WEAK : STB_GLOBAL;
+    unsigned char Binding = getSymbolBinding(Body);
     unsigned char Type = STT_NOTYPE;
     uintX_t Size = 0;
     if (const auto *EBody = dyn_cast<ELFSymbolBody<ELFT>>(Body)) {
       const Elf_Sym &InputSym = EBody->Sym;
-      Binding = InputSym.getBinding();
       Type = InputSym.getType();
       Size = InputSym.st_size;
     }
 
     unsigned char Visibility = Body->getMostConstrainingVisibility();
-    if (Visibility != STV_DEFAULT && Visibility != STV_PROTECTED)
-      Binding = STB_LOCAL;
 
     ESym->setBindingAndType(Binding, Type);
     ESym->st_size = Size;
     ESym->setVisibility(Visibility);
     ESym->st_value = getSymVA<ELFT>(*Body);
 
     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>
+unsigned char SymbolTableSection<ELFT>::getSymbolBinding(SymbolBody *Body) {
+  unsigned char Visibility = Body->getMostConstrainingVisibility();
+  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>::getSymbols() const {
+  return Symbols;
+}
+
+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 RelocationSection<ELF64LE>;
 template class RelocationSection<ELF64BE>;
 
 template class InterpSection<ELF32LE>;
 template class InterpSection<ELF32BE>;
 template class InterpSection<ELF64LE>;
 template class InterpSection<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 DynamicSection<ELF32LE>;
 template class DynamicSection<ELF32BE>;
 template class DynamicSection<ELF64LE>;

ELF/Writer.cpp

template <class ELFT> void lld::elf2::writeResult(SymbolTable<ELFT> *Symtab) {
   Out<ELFT>::Got = &Got;
   PltSection<ELFT> Plt;
   Out<ELFT>::Plt = &Plt;
   SymbolTableSection<ELFT> SymTab(*Symtab, *Out<ELFT>::StrTab);
   Out<ELFT>::SymTab = &SymTab;
   SymbolTableSection<ELFT> DynSymTab(*Symtab, *Out<ELFT>::DynStrTab);
   Out<ELFT>::DynSymTab = &DynSymTab;
   HashTableSection<ELFT> HashTab;
+  if (Config->SysvHash)
     Out<ELFT>::HashTab = &HashTab;
+  GnuHashTableSection<ELFT> GnuHashTab;
+  if (Config->GnuHash)
+    Out<ELFT>::GnuHashTab = &GnuHashTab;
   RelocationSection<ELFT> RelaDyn(Symtab->shouldUseRela());
   Out<ELFT>::RelaDyn = &RelaDyn;
   DynamicSection<ELFT> Dynamic(*Symtab);
   Out<ELFT>::Dynamic = &Dynamic;
 
   Writer<ELFT>(*Symtab).run();
 }
 

 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);
+    if (isOutputDynamic() && includeInDynamicSymtab(*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>::StrTab);
   if (isOutputDynamic()) {
     OutputSections.push_back(Out<ELFT>::DynSymTab);
+    if (Out<ELFT>::GnuHashTab)
+      OutputSections.push_back(Out<ELFT>::GnuHashTab);
+    if (Out<ELFT>::HashTab)
       OutputSections.push_back(Out<ELFT>::HashTab);
     OutputSections.push_back(Out<ELFT>::Dynamic);
     OutputSections.push_back(Out<ELFT>::DynStrTab);
     if (Out<ELFT>::RelaDyn->hasRelocs())
       OutputSections.push_back(Out<ELFT>::RelaDyn);
   }
   if (!Out<ELFT>::Got->empty())
     OutputSections.push_back(Out<ELFT>::Got);
   if (!Out<ELFT>::Plt->empty())

test/elf2/gnu-hash-table.s

+# RUN: echo ".globl foo" > %te.s
+# RUN: llvm-mc -filetype=obj -triple=i386-pc-linux      %te.s -o %te-i386.o
+# RUN: llvm-mc -filetype=obj -triple=i386-pc-linux      %s    -o %t-i386.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux    %s    -o %t-x86_64.o
+# RUN: llvm-mc -filetype=obj -triple=powerpc64-pc-linux %s    -o %t-ppc64.o
+
+# RUN: ld.lld2 -shared --hash-style=gnu  -o %te-i386.so  %te-i386.o
+# RUN: ld.lld2 -shared  -hash-style=gnu  -o %t-i386.so   %t-i386.o
+# RUN: ld.lld2 -shared  -hash-style=gnu  -o %t-x86_64.so %t-x86_64.o
+# RUN: ld.lld2 -shared --hash-style both -o %t-ppc64.so  %t-ppc64.o
+
+# RUN: llvm-readobj -dyn-symbols -gnu-hash-table %te-i386.so \
+# RUN:   | FileCheck %s -check-prefix=EMPTY
+# RUN: llvm-readobj -sections -dyn-symbols -gnu-hash-table %t-i386.so \
+# RUN:   | FileCheck %s -check-prefix=I386
+# RUN: llvm-readobj -sections -dyn-symbols -gnu-hash-table %t-x86_64.so \
+# RUN:   | FileCheck %s -check-prefix=X86_64
+# RUN: llvm-readobj -sections -dyn-symbols -gnu-hash-table %t-ppc64.so \
+# RUN:   | FileCheck %s -check-prefix=PPC64
+
+# EMPTY:      DynamicSymbols [
+# EMPTY:        Symbol {
+# EMPTY:          Name: foo@
+# EMPTY-NEXT:     Value: 0x0
+# EMPTY-NEXT:     Size: 0
+# EMPTY-NEXT:     Binding: Global (0x1)
+# EMPTY-NEXT:     Type: None (0x0)
+# EMPTY-NEXT:     Other: 0
+# EMPTY-NEXT:     Section: Undefined (0x0)
+# EMPTY-NEXT:   }
+# EMPTY-NEXT: ]
+# EMPTY:      GnuHashTable {
+# EMPTY-NEXT:   Num Buckets: 0
+# EMPTY-NEXT:   First Hashed Symbol Index: 2
+# EMPTY-NEXT:   Num Mask Words: 1
+# EMPTY-NEXT:   Shift Count: 5
+# EMPTY-NEXT:   Bloom Filter: [0x0]
+# EMPTY-NEXT:   Buckets: []
+# EMPTY-NEXT:   Values: []
+# EMPTY-NEXT: }
+
+# I386:      Format: ELF32-i386
+# I386:      Arch: i386
+# I386:      AddressSize: 32bit
+# I386:      Sections [
+# I386:          Name: .gnu.hash
+# I386-NEXT:     Type: SHT_GNU_HASH (0x6FFFFFF6)
+# I386-NEXT:     Flags [ (0x2)
+# I386-NEXT:       SHF_ALLOC (0x2)
+# I386-NEXT:     ]
+# I386-NEXT:     Address:
+# I386-NEXT:     Offset:
+# I386-NEXT:     Size: 32
+# I386-NEXT:     Link:
+# I386-NEXT:     Info: 0
+# I386-NEXT:     AddressAlignment: 4
+# I386-NEXT:     EntrySize: 4
+# I386:      ]
+# I386:      DynamicSymbols [
+# I386:        Symbol {
+# I386:          Name: @
+# I386:          Binding: Local (0x0)
+# I386:          Section: Undefined (0x0)
+# I386:        }
+# I386:        Symbol {
+# I386:          Name: baz@
+# I386:          Binding: Global (0x1)
+# I386:          Section: Undefined (0x0)
+# I386:        }
+# I386:        Symbol {
+# I386:          Name: bar@
+# I386:          Binding: Global (0x1)
+# I386:          Section: .text
+# I386:        }
+# I386:        Symbol {
+# I386:          Name: foo@
+# I386:          Binding: Global (0x1)
+# I386:          Section: .text
+# I386:        }
+# I386:      ]
+# I386:      GnuHashTable {
+# I386-NEXT:   Num Buckets: 1
+# I386-NEXT:   First Hashed Symbol Index: 2
+# I386-NEXT:   Num Mask Words: 1
+# I386-NEXT:   Shift Count: 5
+# I386-NEXT:   Bloom Filter: [0x14000220]
+# I386-NEXT:   Buckets: [1]
+# I386-NEXT:   Values: [0xB8860BA, 0xB887389]
+# I386-NEXT: }
+
+# X86_64:      Format: ELF64-x86-64
+# X86_64:      Arch: x86_64
+# X86_64:      AddressSize: 64bit
+# X86_64:      Sections [
+# X86_64:          Name: .gnu.hash (40)
+# X86_64-NEXT:     Type: SHT_GNU_HASH (0x6FFFFFF6)
+# X86_64-NEXT:     Flags [ (0x2)
+# X86_64-NEXT:       SHF_ALLOC (0x2)
+# X86_64-NEXT:     ]
+# X86_64-NEXT:     Address:
+# X86_64-NEXT:     Offset:
+# X86_64-NEXT:     Size: 36
+# X86_64-NEXT:     Link:
+# X86_64-NEXT:     Info: 0
+# X86_64-NEXT:     AddressAlignment: 8
+# X86_64-NEXT:     EntrySize: 0
+# X86_64-NEXT:   }
+# X86_64:      ]
+# X86_64:      DynamicSymbols [
+# X86_64:        Symbol {
+# X86_64:          Name: @
+# X86_64:          Binding: Local (0x0)
+# X86_64:          Section: Undefined (0x0)
+# X86_64:        }
+# X86_64:        Symbol {
+# X86_64:          Name: baz@
+# X86_64:          Binding: Global (0x1)
+# X86_64:          Section: Undefined (0x0)
+# X86_64:        }
+# X86_64:        Symbol {
+# X86_64:          Name: bar@
+# X86_64:          Binding: Global (0x1)
+# X86_64:          Section: .text
+# X86_64:        }
+# X86_64:        Symbol {
+# X86_64:          Name: foo@
+# X86_64:          Binding: Global (0x1)
+# X86_64:          Section: .text
+# X86_64:        }
+# X86_64:      ]
+# X86_64:      GnuHashTable {
+# X86_64-NEXT:   Num Buckets: 1
+# X86_64-NEXT:   First Hashed Symbol Index: 2
+# X86_64-NEXT:   Num Mask Words: 1
+# X86_64-NEXT:   Shift Count: 6
+# X86_64-NEXT:   Bloom Filter: [0x400000000004204]
+# X86_64-NEXT:   Buckets: [1]
+# X86_64-NEXT:   Values: [0xB8860BA, 0xB887389]
+# X86_64-NEXT: }
+
+# PPC64:      Format: ELF64-ppc64
+# PPC64:      Arch: powerpc64
+# PPC64:      AddressSize: 64bit
+# PPC64:      Sections [
+# PPC64:          Name: .gnu.hash (40)
+# PPC64-NEXT:     Type: SHT_GNU_HASH (0x6FFFFFF6)
+# PPC64-NEXT:     Flags [ (0x2)
+# PPC64-NEXT:       SHF_ALLOC (0x2)
+# PPC64-NEXT:     ]
+# PPC64-NEXT:     Address: 0x180
+# PPC64-NEXT:     Offset: 0x180
+# PPC64-NEXT:     Size: 36
+# PPC64-NEXT:     Link: 1
+# PPC64-NEXT:     Info: 0
+# PPC64-NEXT:     AddressAlignment: 8
+# PPC64-NEXT:     EntrySize: 0
+# PPC64-NEXT:   }
+# PPC64:      ]
+# PPC64:      DynamicSymbols [
+# PPC64:        Symbol {
+# PPC64:          Name: @
+# PPC64:          Binding: Local (0x0)
+# PPC64:          Section: Undefined (0x0)
+# PPC64:        }
+# PPC64:        Symbol {
+# PPC64:          Name: baz@
+# PPC64:          Binding: Global (0x1)
+# PPC64:          Section: Undefined (0x0)
+# PPC64:        }
+# PPC64:        Symbol {
+# PPC64:          Name: bar@
+# PPC64:          Binding: Global (0x1)
+# PPC64:          Section: .text
+# PPC64:        }
+# PPC64:        Symbol {
+# PPC64:          Name: foo@
+# PPC64:          Binding: Global (0x1)
+# PPC64:          Section: .text
+# PPC64:        }
+# PPC64:      ]
+# PPC64:      GnuHashTable {
+# PPC64-NEXT:   Num Buckets: 1
+# PPC64-NEXT:   First Hashed Symbol Index: 2
+# PPC64-NEXT:   Num Mask Words: 1
+# PPC64-NEXT:   Shift Count: 6
+# PPC64-NEXT:   Bloom Filter: [0x400000000004204]
+# PPC64-NEXT:   Buckets: [1]
+# PPC64-NEXT:   Values: [0xB8860BA, 0xB887389]
+# PPC64-NEXT: }
+
+.globl foo,bar,baz
+foo:
+bar: