Add content to the .hash section.

This also sets DT_HASH.

With this simple shared libraries created by lld can be loaded by the dynamic
linker.

llvm-svn: 247625

2 files changed, 98 insertions, 51 deletions

diff --git a/lld/ELF/Writer.cpp b/lld/ELF/Writer.cpp
index 5cb27ef025f..238cac3fed6 100644
--- a/lld/ELF/Writer.cpp
+++ b/lld/ELF/Writer.cpp
@@ -177,7 +177,7 @@ public:
   }
 
   void finalize() override {
-    this->Header.sh_size = (NumVisible + 1) * sizeof(Elf_Sym);
+    this->Header.sh_size = getNumSymbols() * sizeof(Elf_Sym);
     this->Header.sh_link = StrTabSec.getSectionIndex();
   }
 
@@ -191,6 +191,7 @@ public:
   }
 
   StringTableSection<ELFT::Is64Bits> &getStrTabSec() { return StrTabSec; }
+  unsigned getNumSymbols() const { return NumVisible + 1; }
 
 private:
   SymbolTable &Table;
@@ -204,21 +205,71 @@ class HashTableSection final : public OutputSectionBase<ELFT::Is64Bits> {
   typedef typename ELFFile<ELFT>::Elf_Word Elf_Word;
 
 public:
-  HashTableSection(const SymbolTableSection<ELFT> &DynSymSec)
+  HashTableSection(SymbolTableSection<ELFT> &DynSymSec)
       : OutputSectionBase<ELFT::Is64Bits>(".hash", SHT_HASH, SHF_ALLOC),
         DynSymSec(DynSymSec) {
     this->Header.sh_entsize = sizeof(Elf_Word);
     this->Header.sh_addralign = sizeof(Elf_Word);
   }
 
+  void addSymbol(StringRef Name) {
+    DynSymSec.addSymbol(Name);
+    Hashes.push_back(hash(Name));
+  }
+
   void finalize() override {
     this->Header.sh_link = DynSymSec.getSectionIndex();
+
+    assert(DynSymSec.getNumSymbols() == Hashes.size() + 1);
+    unsigned NumEntries = 2;                 // nbucket and nchain.
+    NumEntries += DynSymSec.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 += DynSymSec.getNumSymbols();
+    this->Header.sh_size = NumEntries * sizeof(Elf_Word);
   }
 
-  void writeTo(uint8_t *Buf) override {}
+  void writeTo(uint8_t *Buf) override {
+    unsigned NumSymbols = DynSymSec.getNumSymbols();
+    auto *P = reinterpret_cast<Elf_Word *>(Buf);
+    *P++ = NumSymbols; // nbucket
+    *P++ = NumSymbols; // nchain
+
+    std::vector<uint32_t> Buckets;
+    Buckets.resize(NumSymbols);
+    std::vector<uint32_t> Chains;
+    Chains.resize(NumSymbols);
+
+    for (unsigned I = 1; I < NumSymbols; ++I) {
+      uint32_t Hash = Hashes[I - 1] % NumSymbols;
+      Chains[I] = Buckets[Hash];
+      Buckets[Hash] = I;
+    }
+
+    for (uint32_t V : Buckets)
+      *P++ = V;
+    for (uint32_t V : Chains)
+      *P++ = V;
+  }
+
+  SymbolTableSection<ELFT> &getDynSymSec() { return DynSymSec; }
 
 private:
-  const SymbolTableSection<ELFT> &DynSymSec;
+  uint32_t hash(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;
+  }
+  SymbolTableSection<ELFT> &DynSymSec;
+  std::vector<uint32_t> Hashes;
 };
 
 template <class ELFT>
@@ -228,11 +279,11 @@ class DynamicSection final : public OutputSectionBase<ELFT::Is64Bits> {
   typedef typename Base::Elf_Dyn Elf_Dyn;
 
 public:
-  DynamicSection(SymbolTable &SymTab, SymbolTableSection<ELFT> &DynSymSec)
+  DynamicSection(SymbolTable &SymTab, HashTableSection<ELFT> &HashSec)
       : OutputSectionBase<ELFT::Is64Bits>(".dynamic", SHT_DYNAMIC,
                                           SHF_ALLOC | SHF_WRITE),
-        DynStrSec(DynSymSec.getStrTabSec()), DynSymSec(DynSymSec),
-        SymTab(SymTab) {
+        HashSec(HashSec), DynSymSec(HashSec.getDynSymSec()),
+        DynStrSec(DynSymSec.getStrTabSec()), SymTab(SymTab) {
     typename Base::HeaderT &Header = this->Header;
     Header.sh_addralign = ELFT::Is64Bits ? 8 : 4;
     Header.sh_entsize = ELFT::Is64Bits ? 16 : 8;
@@ -242,6 +293,7 @@ public:
     ++NumEntries; // DT_SYMTAB
     ++NumEntries; // DT_STRTAB
     ++NumEntries; // DT_STRSZ
+    ++NumEntries; // DT_HASH
 
     StringRef RPath = Config->RPath;
     if (!RPath.empty()) {
@@ -279,6 +331,10 @@ public:
     P->d_un.d_val = DynStrSec.data().size();
     ++P;
 
+    P->d_tag = DT_HASH;
+    P->d_un.d_ptr = HashSec.getVA();
+    ++P;
+
     StringRef RPath = Config->RPath;
     if (!RPath.empty()) {
       P->d_tag = DT_RUNPATH;
@@ -300,8 +356,9 @@ public:
   }
 
 private:
-  StringTableSection<ELFT::Is64Bits> &DynStrSec;
+  HashTableSection<ELFT> &HashSec;
   SymbolTableSection<ELFT> &DynSymSec;
+  StringTableSection<ELFT::Is64Bits> &DynStrSec;
   SymbolTable &SymTab;
 };
 
@@ -315,7 +372,7 @@ public:
   typedef typename ELFFile<ELFT>::Elf_Sym Elf_Sym;
   Writer(SymbolTable *T)
       : SymTabSec(*this, *T, StrTabSec), DynSymSec(*this, *T, DynStrSec),
-        DynamicSec(*T, DynSymSec), HashSec(DynSymSec) {}
+        HashSec(DynSymSec), DynamicSec(*T, HashSec) {}
   void run();
 
   const OutputSection<ELFT> &getBSS() const {
@@ -354,10 +411,10 @@ private:
   SymbolTableSection<ELFT> SymTabSec;
   SymbolTableSection<ELFT> DynSymSec;
 
-  DynamicSection<ELFT> DynamicSec;
-
   HashTableSection<ELFT> HashSec;
 
+  DynamicSection<ELFT> DynamicSec;
+
   InterpSection<ELFT::Is64Bits> InterpSec;
 
   OutputSection<ELFT> *BSSSec = nullptr;
@@ -651,7 +708,7 @@ template <class ELFT> void Writer<ELFT>::createSections() {
     // need to add the symbols use by dynamic relocations when producing
     // an executable (ignoring --export-dynamic).
     if (needsDynamicSections())
-      DynSymSec.addSymbol(Name);
+      HashSec.addSymbol(Name);
   }
 
   // Sort the common symbols by alignment as an heuristic to pack them better.
diff --git a/lld/test/elf2/shared.s b/lld/test/elf2/shared.s
index 4c7f5c37d34..5a796d2ce25 100644
--- a/lld/test/elf2/shared.s
+++ b/lld/test/elf2/shared.s
@@ -3,48 +3,16 @@
 // RUN: lld -flavor gnu2 -shared %t2.o -o %t2.so
 // RUN: llvm-readobj -s %t2.so | FileCheck --check-prefix=SO %s
 // RUN: lld -flavor gnu2 -dynamic-linker /lib64/ld-linux-x86-64.so.2 -rpath foo -rpath bar %t.o %t2.so -o %t
-// RUN: llvm-readobj --program-headers --dynamic-table -t -s -dyn-symbols -section-data %t | FileCheck %s
+// RUN: llvm-readobj --program-headers --dynamic-table -t -s -dyn-symbols -section-data -hash-table %t | FileCheck %s
 // REQUIRES: x86
 
-
-// test that .hash is linked to .dynsym
-// SO:        Index: 4
-// SO-NEXT:   Name: .dynsym
-// SO-NEXT:   Type: SHT_DYNSYM
-// SO-NEXT:   Flags [
-// SO-NEXT:     SHF_ALLOC
-// SO-NEXT:   ]
-// SO-NEXT:   Address:
-// SO-NEXT:   Offset:
-// SO-NEXT:   Size:
-// SO-NEXT:   Link:
-// SO-NEXT:   Info:
-// SO-NEXT:   AddressAlignment: 4
-// SO-NEXT:   EntrySize: 16
-// SO-NEXT: }
-// SO-NEXT: Section {
-// SO-NEXT:   Index: 5
-// SO-NEXT:   Name: .hash
-// SO-NEXT:   Type: SHT_HASH
-// SO-NEXT:   Flags [
-// SO-NEXT:     SHF_ALLOC
-// SO-NEXT:   ]
-// SO-NEXT:   Address:
-// SO-NEXT:   Offset:
-// SO-NEXT:   Size: 0
-// SO-NEXT:   Link: 4
-// SO-NEXT:   Info: 0
-// SO-NEXT:   AddressAlignment: 4
-// SO-NEXT:   EntrySize: 4
-// SO-NEXT: }
-
 // Make sure .symtab is properly aligned.
 // SO:      Name: .symtab
 // SO-NEXT: Type: SHT_SYMTAB
 // SO-NEXT: Flags [
 // SO-NEXT: ]
 // SO-NEXT: Address:
-// SO-NEXT: Offset: 0x300C
+// SO-NEXT: Offset: 0x400C
 // SO-NEXT: Size:
 // SO-NEXT: Link:
 // SO-NEXT: Info:
@@ -68,7 +36,9 @@
 // CHECK-NEXT:   )
 // CHECK-NEXT: }
 
-// CHECK:        Name: .dynsym
+// test that .hash is linked to .dynsym
+// CHECK:        Index: 5
+// CHECK-NEXT:   Name: .dynsym
 // CHECK-NEXT:   Type: SHT_DYNSYM
 // CHECK-NEXT:   Flags [
 // CHECK-NEXT:     SHF_ALLOC
@@ -86,6 +56,21 @@
 // CHECK-NEXT:     0020:
 // CHECK-NEXT:   )
 // CHECK-NEXT: }
+// CHECK-NEXT: Section {
+// CHECK-NEXT:   Index: 6
+// CHECK-NEXT:    Name: .hash
+// CHECK-NEXT:    Type: SHT_HASH
+// CHECK-NEXT:    Flags [
+// CHECK-NEXT:      SHF_ALLOC
+// CHECK-NEXT:    ]
+// CHECK-NEXT:    Address: [[HASHADDR:.*]]
+// CHECK-NEXT:    Offset:
+// CHECK-NEXT:    Size:
+// CHECK-NEXT:    Link: 5
+// CHECK-NEXT:    Info: 0
+// CHECK-NEXT:    AddressAlignment: 4
+// CHECK-NEXT:    EntrySize: 4
+
 
 // CHECK:        Name: .dynamic
 // CHECK-NEXT:   Type: SHT_DYNAMIC
@@ -101,10 +86,7 @@
 // CHECK-NEXT:   AddressAlignment: [[ALIGN:.*]]
 // CHECK-NEXT:   EntrySize: 8
 // CHECK-NEXT:   SectionData (
-// CHECK-NEXT:     0000:
-// CHECK-NEXT:     0010:
-// CHECK-NEXT:     0020:
-// CHECK-NEXT:   )
+// CHECK:        )
 // CHECK-NEXT: }
 
 // CHECK:        Index: [[DYNSTR]]
@@ -190,6 +172,7 @@
 // CHECK-NEXT:   0x00000006 SYMTAB               [[DYNSYMADDR]]
 // CHECK-NEXT:   0x00000005 STRTAB               [[DYNSTRADDR]]
 // CHECK-NEXT:   0x0000000A STRSZ
+// CHECK-NEXT:   0x00000004 HASH                 [[HASHADDR]]
 // CHECK-NEXT:   0x0000001D RUNPATH              foo:bar
 // CHECK-NEXT:   0x00000001 NEEDED               SharedLibrary ({{.*}}2.so)
 // CHECK-NEXT:   0x00000000 NULL                 0x0
@@ -221,6 +204,13 @@
 // CHECK-NEXT:   Alignment: [[ALIGN]]
 // CHECK-NEXT: }
 
+// CHECK:      HashTable {
+// CHECK-NEXT:   Num Buckets: 3
+// CHECK-NEXT:   Num Chains: 3
+// CHECK-NEXT:   Buckets: [2, 0, 1]
+// CHECK-NEXT:   Chains: [0, 0, 0]
+// CHECK-NEXT: }
+
 .global _start
 _start:
 .long bar