[lld][ELF] Dynamic library support

[shankarke]

Summary

This patch adds the below functionalities :-

• Adds required hash section
• Adds changes to Hexagon got and .got.plt sections

This also makes shared libraries work with Hexagon for object files containing PLT/GOTOFF/GOTPCREL relocations.

[Bigcheese]

lib/ReaderWriter/ELF/SectionChunks.h

634

doSort, or just sort.

836

When does this ever happen?

[shankarke]

lib/ReaderWriter/ELF/SectionChunks.h

634

Will make the change.

836

For the first undefined symbol.

[Bigcheese]

lib/ReaderWriter/ELF/SectionChunks.h

836

But undefined symbols shouldn't be in the hash table.

[shankarke]

lib/ReaderWriter/ELF/SectionChunks.h

836

The hash table(chains array) contains an entry for every entry in the dynamic symbol table.

[Eugene.Zelenko]

Committed in rL178323.

lib/ReaderWriter/ELF/Hexagon/HexagonDynamicAtoms.h

 
 namespace lld {
 namespace elf {
 
 class HexagonGOTAtom : public GOTAtom {
   static const uint8_t _defaultContent[8];
 
 public:
-  HexagonGOTAtom(const File &f, StringRef secName)
-      : GOTAtom(f, secName) {
+  HexagonGOTAtom(const File &f) : GOTAtom(f, ".got") {}
+
+  virtual ArrayRef<uint8_t> rawContent() const {
+    return ArrayRef<uint8_t>(_defaultContent, 8);
   }
 
+  virtual Alignment alignment() const { return Alignment(2); }
+};
+
+class HexagonGOTPLTAtom : public GOTAtom {
+  static const uint8_t _defaultContent[8];
+
+public:
+  HexagonGOTPLTAtom(const File &f) : GOTAtom(f, ".got.plt") {}
+
   virtual ArrayRef<uint8_t> rawContent() const {
     return ArrayRef<uint8_t>(_defaultContent, 8);
   }
 };
 
+class HexagonGOTPLT0Atom : public GOTAtom {
+  static const uint8_t _defaultContent[16];
+
+public:
+  HexagonGOTPLT0Atom(const File &f) : GOTAtom(f, ".got.plt") {}
+
+  virtual ArrayRef<uint8_t> rawContent() const {
+    return ArrayRef<uint8_t>(_defaultContent, 16);
+  }
+};
+
 const uint8_t HexagonGOTAtom::_defaultContent[8] = { 0 };
+const uint8_t HexagonGOTPLTAtom::_defaultContent[8] = { 0 };
+const uint8_t HexagonGOTPLT0Atom::_defaultContent[16] = { 0 };
 
 class HexagonPLTAtom : public PLTAtom {
   static const uint8_t _defaultContent[16];
 
 public:
   HexagonPLTAtom(const File &f, StringRef secName)
       : PLTAtom(f, secName) {
   }

lib/ReaderWriter/ELF/Hexagon/HexagonTargetHandler.h

public:
   }
 
   virtual const HexagonTargetRelocationHandler &getRelocationHandler() const {
     return _relocationHandler;
   }
 
   void addDefaultAtoms() {
     _hexagonRuntimeFile.addAbsoluteAtom("_SDA_BASE_");
-    if (_targetInfo.isDynamic())
+    if (_targetInfo.isDynamic()) {
       _hexagonRuntimeFile.addAbsoluteAtom("_GLOBAL_OFFSET_TABLE_");
+      _hexagonRuntimeFile.addAbsoluteAtom("_DYNAMIC");
+    }
   }
 
   virtual void addFiles(InputFiles &inputFiles) {
     addDefaultAtoms();
     inputFiles.prependFile(_hexagonRuntimeFile);
   }
 
   void finalizeSymbolValues() {
     auto sdabaseAtomIter = _targetLayout.findAbsoluteAtom("_SDA_BASE_");
     (*sdabaseAtomIter)->_virtualAddr =
         _targetLayout.getSDataSection()->virtualAddr();
     if (_targetInfo.isDynamic()) {
       auto gotAtomIter =
           _targetLayout.findAbsoluteAtom("_GLOBAL_OFFSET_TABLE_");
       _gotSymAtom = (*gotAtomIter);
       auto gotpltSection = _targetLayout.findOutputSection(".got.plt");
       if (gotpltSection)
         _gotSymAtom->_virtualAddr = gotpltSection->virtualAddr();
       else
         _gotSymAtom->_virtualAddr = 0;
+      auto dynamicAtomIter = _targetLayout.findAbsoluteAtom("_DYNAMIC");
+      auto dynamicSection = _targetLayout.findOutputSection(".dynamic");
+      if (dynamicSection)
+        (*dynamicAtomIter)->_virtualAddr = dynamicSection->virtualAddr();
+      else
+        (*dynamicAtomIter)->_virtualAddr = 0;
     }
   }
 
   uint64_t getGOTSymAddr() const { return _gotSymAtom->_virtualAddr; }
 
 private:
   HexagonTargetLayout<HexagonELFType> _targetLayout;
   HexagonTargetRelocationHandler _relocationHandler;
   HexagonTargetAtomHandler<HexagonELFType> _targetAtomHandler;
   HexagonRuntimeFile<HexagonELFType> _hexagonRuntimeFile;
   AtomLayout *_gotSymAtom;
 };
 } // end namespace elf
 } // end namespace lld
 
 #endif

lib/ReaderWriter/ELF/Hexagon/HexagonTargetHandler.cpp

case R_HEX_GOT_11_X:
       break;
     }
   }
 
 protected:
   /// \brief Create a GOT entry containing 0.
   const GOTAtom *getNullGOT() {
     if (!_null) {
-      _null = new (_file._alloc) HexagonGOTAtom(_file, ".got.plt");
+      _null = new (_file._alloc) HexagonGOTPLTAtom(_file);
 #ifndef NDEBUG
       _null->_name = "__got_null";
 #endif
     }
     return _null;
   }
 
 public:
protected:
   PLT0Atom *_PLT0;
   GOTAtom *_got0;
   /// @}
 };
 
 class DynamicGOTPLTPass LLVM_FINAL : public GOTPLTPass<DynamicGOTPLTPass> {
 public:
   DynamicGOTPLTPass(const elf::HexagonTargetInfo &ti) : GOTPLTPass(ti) {
-    // Fill in the null entry.
-    getNullGOT();
-    _got0 = new (_file._alloc) HexagonGOTAtom(_file, ".got.plt");
+    _got0 = new (_file._alloc) HexagonGOTPLT0Atom(_file);
 #ifndef NDEBUG
     _got0->_name = "__got0";
 #endif
   }
 
   const PLT0Atom *getPLT0() {
     if (_PLT0)
       return _PLT0;
     _PLT0 = new (_file._alloc) HexagonPLT0Atom(_file);
     _PLT0->addReference(R_HEX_B32_PCREL_X, 0, _got0, 0);
-    _PLT0->addReference(R_HEX_6_PCREL_X, 4, _got0, 0);
+    _PLT0->addReference(R_HEX_6_PCREL_X, 4, _got0, 4);
     DEBUG_WITH_TYPE("PLT", llvm::dbgs() << "[ PLT0/GOT0 ] "
                                         << "Adding plt0/got0 \n");
     return _PLT0;
   }
 
   const PLTAtom *getPLTEntry(const Atom *a) {
     auto plt = _pltMap.find(a);
     if (plt != _pltMap.end())
       return plt->second;
-    auto ga = new (_file._alloc) HexagonGOTAtom(_file, ".got.plt");
+    auto ga = new (_file._alloc) HexagonGOTPLTAtom(_file);
     ga->addReference(R_HEX_JMP_SLOT, 0, a, 0);
     auto pa = new (_file._alloc) HexagonPLTAtom(_file, ".plt");
     pa->addReference(R_HEX_B32_PCREL_X, 0, ga, 0);
     pa->addReference(R_HEX_6_PCREL_X, 4, ga, 4);
 
     // Point the got entry to the PLT0 atom initially
     ga->addReference(R_HEX_32, 0, getPLT0(), 0);
 #ifndef NDEBUG
#endif
     _pltVector.push_back(pa);
     return pa;
   }
 
   const GOTAtom *getGOTEntry(const Atom *a) {
     auto got = _gotMap.find(a);
     if (got != _gotMap.end())
       return got->second;
-    auto ga = new (_file._alloc) HexagonGOTAtom(_file, ".got");
+    auto ga = new (_file._alloc) HexagonGOTAtom(_file);
     ga->addReference(R_HEX_GLOB_DAT, 0, a, 0);
 
 #ifndef NDEBUG
     ga->_name = "__got_";
     ga->_name += a->name();
     DEBUG_WITH_TYPE("GOT", llvm::dbgs() << "[" << a->name() << "] "
                                         << "Adding got: " << ga->_name << "\n");
 #endif
     _gotMap[a] = ga;
     _gotVector.push_back(ga);
     return ga;
   }
 
   ErrorOr<void> handleGOTREL(const Reference &ref) {
-    // Turn this so that the target is set to the GOT entry 
+    // Turn this so that the target is set to the GOT entry
     const_cast<Reference &>(ref).setTarget(getGOTEntry(ref.target()));
     return error_code::success();
   }
 
   ErrorOr<void> handlePLT32(const Reference &ref) {
     // Turn this into a PC32 to the PLT entry.
     const_cast<Reference &>(ref).setKind(R_HEX_B22_PCREL);
     const_cast<Reference &>(ref).setTarget(getPLTEntry(ref.target()));

lib/ReaderWriter/ELF/OutputELFWriter.h

for (const auto sla : file.sharedLibrary()) {
     _soNeeded.insert(sla->loadName());
   }
   for (const auto &loadName : _soNeeded) {
     Elf_Dyn dyn;
     dyn.d_tag = DT_NEEDED;
     dyn.d_un.d_val = _dynamicStringTable->addString(loadName.getKey());
     _dynamicTable->addEntry(dyn);
   }
+  // The dynamic symbol table need to be sorted earlier because the hash
+  // table needs to be built using the dynamic symbol table. It would be
+  // late to sort the symbols due to that in finalize. In the dynamic symbol
+  // table finalize, we call the symbol table finalize and we dont want to
+  // sort again
+  _dynamicSymbolTable->sortSymbols();
+
+  // Add the dynamic symbols into the hash table
+  _dynamicSymbolTable->addSymbolsToHashTable();
 }
 
 template <class ELFT> void OutputELFWriter<ELFT>::buildAtomToAddressMap() {
   for (auto sec : _layout->sections())
     if (auto section = dyn_cast<AtomSection<ELFT>>(sec))
       for (const auto &atom : section->atoms())
         _atomToAddressMap[atom->_atom] = atom->_virtualAddr;
   // build the atomToAddressMap that contains absolute symbols too
_dynamicTable.reset(new (_alloc) DynamicTable<ELFT>(
         _targetInfo, ".dynamic", DefaultLayout<ELFT>::ORDER_DYNAMIC));
     _dynamicStringTable.reset(new (_alloc) StringTable<ELFT>(
         _targetInfo, ".dynstr", DefaultLayout<ELFT>::ORDER_DYNAMIC_STRINGS,
         true));
     _dynamicSymbolTable.reset(new (_alloc) DynamicSymbolTable<ELFT>(
         _targetInfo, ".dynsym", DefaultLayout<ELFT>::ORDER_DYNAMIC_SYMBOLS));
     _hashTable.reset(new (_alloc) HashSection<ELFT>(
         _targetInfo, ".hash", DefaultLayout<ELFT>::ORDER_HASH));
+    // Set the hash table in the dynamic symbol table so that the entries in the
+    // hash table can be created
+    _dynamicSymbolTable->setHashTable(_hashTable.get());
+    _hashTable->setSymbolTable(_dynamicSymbolTable.get());
     _layout->addSection(_dynamicTable.get());
     _layout->addSection(_dynamicStringTable.get());
     _layout->addSection(_dynamicSymbolTable.get());
     _layout->addSection(_hashTable.get());
     _dynamicSymbolTable->setStringSection(_dynamicStringTable.get());
+    _dynamicTable->setSymbolTable(_dynamicSymbolTable.get());
+    _dynamicTable->setHashTable(_hashTable.get());
     if (_layout->hasDynamicRelocationTable())
-      _layout->getDynamicRelocationTable()->setSymbolTable(
-          _dynamicSymbolTable.get());
+      _layout->getDynamicRelocationTable()
+          ->setSymbolTable(_dynamicSymbolTable.get());
     if (_layout->hasPLTRelocationTable())
       _layout->getPLTRelocationTable()->setSymbolTable(
           _dynamicSymbolTable.get());
   }
 
   // give a chance for the target to add sections
   _targetHandler.createDefaultSections();
 }
error_code OutputELFWriter<ELFT>::buildOutput(const File &file) {
   // build Section Header table
   buildSectionHeaderTable();
 
   // assign Offsets and virtual addresses
   // for sections with no segments
   assignSectionsWithNoSegments();
 
   if (_targetInfo.isDynamic())
-    _dynamicTable->updateDynamicTable(_hashTable.get(),
-                                      _dynamicSymbolTable.get());
+    _dynamicTable->updateDynamicTable();
 
   return error_code::success();
 }
 
 template <class ELFT>
 error_code OutputELFWriter<ELFT>::writeFile(const File &file, StringRef path) {
 
   buildOutput(file);

lib/ReaderWriter/ELF/SectionChunks.h

auto se = std::find_if(_symbolTable.begin(), _symbolTable.end(),
                            [=](const SymbolEntry &se) {
       return se._atom == a;
     });
     if (se == _symbolTable.end())
       return STN_UNDEF;
     return std::distance(_symbolTable.begin(), se);
   }
 
+  virtual void finalize() { finalize(true); }
+
+  virtual void sortSymbols() {
+    std::stable_sort(_symbolTable.begin(), _symbolTable.end(),
+                     [](const SymbolEntry & A, const SymbolEntry & B) {
+      return A._symbol.getBinding() < B._symbol.getBinding();
+    });
+  }
+
   virtual void addAbsoluteAtom(Elf_Sym &sym, const AbsoluteAtom *aa,
                                int64_t addr);
 
   virtual void addDefinedAtom(Elf_Sym &sym, const DefinedAtom *da,
                               int64_t addr);
 
   virtual void addUndefinedAtom(Elf_Sym &sym, const UndefinedAtom *ua);
 
   virtual void addSharedLibAtom(Elf_Sym &sym, const SharedLibraryAtom *sla);
 
-  virtual void finalize();
+  virtual void finalize(bool do_sort = true);
 
   virtual void write(ELFWriter *writer, llvm::FileOutputBuffer &buffer);
 
   void setStringSection(StringTable<ELFT> *s) { _stringSection = s; }
 
   StringTable<ELFT> *getStringTable() const { return _stringSection; }
 
 protected:
else
     addUndefinedAtom(symbol, llvm::dyn_cast<UndefinedAtom>(atom));
 
   _symbolTable.push_back(SymbolEntry(atom, symbol, atomLayout));
   this->_fsize += sizeof(Elf_Sym);
   if (this->_flags & SHF_ALLOC)
     this->_msize = this->_fsize;
 }
 
-template <class ELFT> void SymbolTable<ELFT>::finalize() {
+template <class ELFT> void SymbolTable<ELFT>::finalize(bool do_sort) {
   // sh_info should be one greater than last symbol with STB_LOCAL binding
   // we sort the symbol table to keep all local symbols at the beginning
-  std::stable_sort(_symbolTable.begin(), _symbolTable.end(),
-                   [](const SymbolEntry & A, const SymbolEntry & B) {
-    return A._symbol.getBinding() < B._symbol.getBinding();
-  });
+  if (do_sort)
+    sortSymbols();
+
   uint16_t shInfo = 0;
   for (const auto &i : _symbolTable) {
     if (i._symbol.getBinding() != llvm::ELF::STB_LOCAL)
       break;
     shInfo++;
   }
   this->_info = shInfo;
   this->_link = _stringSection->ordinal();
void SymbolTable<ELFT>::write(ELFWriter *writer,
   uint8_t *chunkBuffer = buffer.getBufferStart();
   uint8_t *dest = chunkBuffer + this->fileOffset();
   for (const auto &sti : _symbolTable) {
     memcpy(dest, &sti._symbol, sizeof(Elf_Sym));
     dest += sizeof(Elf_Sym);
   }
 }
 
+template <class ELFT> class HashSection;
+
 template <class ELFT> class DynamicSymbolTable : public SymbolTable<ELFT> {
 public:
   DynamicSymbolTable(const ELFTargetInfo &ti, const char *str, int32_t order)
-      : SymbolTable<ELFT>(ti, str, order) {
+      : SymbolTable<ELFT>(ti, str, order), _hashTable(nullptr) {
     this->_type = SHT_DYNSYM;
     this->_flags = SHF_ALLOC;
     this->_msize = this->_fsize;
   }
 
+  // Set the dynamic hash table for symbols to be added into
+  void setHashTable(HashSection<ELFT> *hashTable) { _hashTable = hashTable; }
+
+  // Add all the dynamic symbos to the hash table
+  void addSymbolsToHashTable() {
+    int index = 0;
+    for (auto &ste : this->_symbolTable) {
+      if (!ste._atom)
+        _hashTable->addSymbol("", index);
+      else
+        _hashTable->addSymbol(ste._atom->name(), index);
+      ++index;
+    }
+  }
+
   virtual void finalize() {
     // Defined symbols which have been added into the dynamic symbol table
     // dont have their addresses known until addresses have been assigned
     // so lets update the symbol values after they have got assigned
     for (auto &ste: this->_symbolTable) {
       const AtomLayout *atomLayout = ste._atomLayout;
       if (!atomLayout)
         continue;
       ste._symbol.st_value = atomLayout->_virtualAddr;
     }
-    SymbolTable<ELFT>::finalize();
+
+    // Dont sort the symbols
+    SymbolTable<ELFT>::finalize(false);
   }
 
+private:
+  HashSection<ELFT> *_hashTable;
 };
 
 template <class ELFT> class RelocationTable : public Section<ELFT> {
 public:
   typedef llvm::object::Elf_Rel_Impl<ELFT, true> Elf_Rela;
 
   RelocationTable(const ELFTargetInfo &ti, StringRef str, int32_t order)
       : Section<ELFT>(ti, str), _symbolTable(nullptr) {
auto rel = std::find_if(
       return false;
     });
     if (rel == _relocs.end())
       return false;
     res = std::distance(_relocs.begin(), rel);
     return true;
   }
 
-  void setSymbolTable(const SymbolTable<ELFT> *symbolTable) {
+  void setSymbolTable(const DynamicSymbolTable<ELFT> *symbolTable) {
     _symbolTable = symbolTable;
   }
 
   virtual void finalize() {
     this->_link = _symbolTable ? _symbolTable->ordinal() : 0;
     if (this->_parent)
       this->_parent->setLink(this->_link);
   }
 
   virtual void write(ELFWriter *writer, llvm::FileOutputBuffer &buffer) {
     uint8_t *chunkBuffer = buffer.getBufferStart();
     uint8_t *dest = chunkBuffer + this->fileOffset();
     for (const auto &rel : _relocs) {
       Elf_Rela *r = reinterpret_cast<Elf_Rela *>(dest);
       uint32_t index =
           _symbolTable ? _symbolTable->getSymbolTableIndex(rel.second->target())
                        : (uint32_t) STN_UNDEF;
       r->setSymbolAndType(index, rel.second->kind());
       r->r_offset =
           writer->addressOfAtom(rel.first) + rel.second->offsetInAtom();
+      // FIXME: The addend is used only by IRELATIVE relocations while static
+      // linking executable statically, check to see how does dynamic linking
+      // work with IFUNC and change accordingly
+      if (!this->_targetInfo.isDynamic())
         r->r_addend =
             writer->addressOfAtom(rel.second->target()) + rel.second->addend();
       dest += sizeof(Elf_Rela);
-      DEBUG_WITH_TYPE("ELFRelocationTable",
-                      llvm::dbgs()
-                      << kindOrUnknown(this->_targetInfo.stringFromRelocKind(
+      DEBUG_WITH_TYPE(
+          "ELFRelocationTable",
+          llvm::dbgs() << kindOrUnknown(this->_targetInfo.stringFromRelocKind(
                               rel.second->kind())) << " relocation at "
                        << rel.first->name() << "@" << r->r_offset << " to "
                        << rel.second->target()->name() << "@" << r->r_addend
                        << "\n");
     }
   }
 
 private:
-  std::vector<std::pair<const DefinedAtom *, const Reference *>> _relocs;
-  const SymbolTable<ELFT> *_symbolTable;
+  std::vector<std::pair<const DefinedAtom *, const Reference *> > _relocs;
+  const DynamicSymbolTable<ELFT> *_symbolTable;
 };
 
 template <class ELFT> class HashSection;
 
 template <class ELFT> class DynamicTable : public Section<ELFT> {
   typedef llvm::object::Elf_Dyn_Impl<ELFT> Elf_Dyn;
   typedef std::vector<Elf_Dyn> EntriesT;
 
if (_layout->hasPLTRelocationTable()) {
       dyn.d_un.d_val = DT_RELA;
       _dt_pltrel = addEntry(dyn);
       dyn.d_un.d_val = 0;
       dyn.d_tag = DT_JMPREL;
       _dt_jmprel = addEntry(dyn);
     }
   }
 
-  void updateDynamicTable(HashSection<ELFT> *hashTable,
-                          DynamicSymbolTable<ELFT> *dynamicSymbolTable) {
+  virtual void finalize() {
+    StringTable<ELFT> *dynamicStringTable =
+        _dynamicSymbolTable->getStringTable();
+    this->_link = dynamicStringTable->ordinal();
+    if (this->_parent) {
+      this->_parent->setInfo(this->_info);
+      this->_parent->setLink(this->_link);
+    }
+  }
+
+  void setSymbolTable(DynamicSymbolTable<ELFT> *dynsym) {
+    _dynamicSymbolTable = dynsym;
+  }
+
+  void setHashTable(HashSection<ELFT> *hsh) { _hashTable = hsh; }
+
+  void updateDynamicTable() {
     StringTable<ELFT> *dynamicStringTable =
-        dynamicSymbolTable->getStringTable();
-    _entries[_dt_hash].d_un.d_val = hashTable->virtualAddr();
+        _dynamicSymbolTable->getStringTable();
+    _entries[_dt_hash].d_un.d_val = _hashTable->virtualAddr();
     _entries[_dt_strtab].d_un.d_val = dynamicStringTable->virtualAddr();
-    _entries[_dt_symtab].d_un.d_val = dynamicSymbolTable->virtualAddr();
+    _entries[_dt_symtab].d_un.d_val = _dynamicSymbolTable->virtualAddr();
     _entries[_dt_strsz].d_un.d_val = dynamicStringTable->memSize();
-    _entries[_dt_syment].d_un.d_val = dynamicSymbolTable->getEntSize();
+    _entries[_dt_syment].d_un.d_val = _dynamicSymbolTable->getEntSize();
     if (_layout->hasDynamicRelocationTable()) {
       auto relaTbl = _layout->getDynamicRelocationTable();
       _entries[_dt_rela].d_un.d_val = relaTbl->virtualAddr();
       _entries[_dt_relasz].d_un.d_val = relaTbl->memSize();
       _entries[_dt_relaent].d_un.d_val = relaTbl->getEntSize();
     }
     if (_layout->hasPLTRelocationTable()) {
       auto relaTbl = _layout->getPLTRelocationTable();
private:
   std::size_t _dt_relaent;
   std::size_t _dt_strsz;
   std::size_t _dt_syment;
   std::size_t _dt_pltrelsz;
   std::size_t _dt_pltgot;
   std::size_t _dt_pltrel;
   std::size_t _dt_jmprel;
   TargetLayout<ELFT> *_layout;
+  DynamicSymbolTable<ELFT> *_dynamicSymbolTable;
+  HashSection<ELFT> *_hashTable;
 };
 
 template <class ELFT> class InterpSection : public Section<ELFT> {
 public:
   InterpSection(const ELFTargetInfo &ti, StringRef str, int32_t order,
                 StringRef interp)
       : Section<ELFT>(ti, str),
         _interp(interp){
void write(ELFWriter *writer, llvm::FileOutputBuffer &buffer) {
     uint8_t *dest = chunkBuffer + this->fileOffset();
     std::memcpy(dest, _interp.data(), _interp.size());
   }
 
 private:
   StringRef _interp;
 };
 
+/// The hash table in the dynamic linker is organized into
+///
+///     [ nbuckets              ]
+///     [ nchains               ]
+///     [ buckets[0]            ]
+///     .........................
+///     [ buckets[nbuckets-1]   ]
+///     [ chains[0]             ]
+///     .........................
+///     [ chains[nchains - 1]   ]
+///
+/// nbuckets - total number of hash buckets
+/// nchains is equal to the number of dynamic symbols.
+///
+/// The symbol is searched by the dynamic linker using the below approach.
+///  * Calculate the hash of the symbol that needs to be searched
+///  * Take the value from the buckets[hash % nbuckets] as the index of symbol
+///  * Compare the symbol's name, if true return, if false, look through the
+///  * array since there was a collision
+
 template <class ELFT> class HashSection : public Section<ELFT> {
   struct SymbolTableEntry {
     StringRef _name;
     uint32_t _index;
   };
 
 public:
   HashSection(const ELFTargetInfo &ti, StringRef name, int32_t order)
-      : Section<ELFT>(ti, name) {
+      : Section<ELFT>(ti, name), _symbolTable(nullptr) {
     this->setOrder(order);
-    this->_align2 = 4; // Alignment of Elf32_Word.
+    this->_entSize = 4;
     this->_type = SHT_HASH;
     this->_flags = SHF_ALLOC;
-    // The size of nbucket and nchain.
-    this->_fsize = 8;
-    this->_msize = this->_fsize;
+    // Set the alignment properly depending on the target architecture
+    if (ti.is64Bits())
+      this->_align2 = 8;
+    else
+      this->_align2 = 4;
+    this->_fsize = 0;
+    this->_msize = 0;
   }
 
+  /// \brief add the dynamic symbol into the table so that the
+  /// hash could be calculated
   void addSymbol(StringRef name, uint32_t index) {
     SymbolTableEntry ste;
     ste._name = name;
     ste._index = index;
     _entries.push_back(ste);
   }
 
+  /// \brief Set the dynamic symbol table
+  void setSymbolTable(const DynamicSymbolTable<ELFT> *symbolTable) {
+    _symbolTable = symbolTable;
+  }
+
+  // The size of the section has to be determined so that fileoffsets
+  // may be properly assigned. Lets calculate the buckets and the chains
+  // and fill the chains and the buckets hash table used by the dynamic
+  // linker and update the filesize and memory size accordingly
+  virtual void doPreFlight() {
+    // The number of buckets to use for a certain number of symbols.
+    // If there are less than 3 symbols, 1 bucket will be used. If
+    // there are less than 17 symbols, 3 buckets will be used, and so
+    // forth. The bucket numbers are defined by GNU ld. We use the
+    // same rules here so we generate hash sections with the same
+    // size as those generated by GNU ld.
+    uint32_t hashBuckets[] = { 1, 3, 17, 37, 67, 97, 131, 197, 263, 521, 1031,
+                               2053, 4099, 8209, 16411, 32771, 65537, 131101,
+                               262147 };
+    int hashBucketsCount = sizeof(hashBuckets) / sizeof(uint32_t);
+
+    unsigned int bucketsCount = 0;
+    unsigned int dynSymCount = _entries.size();
+
+    // Get the number of buckes that we want to use
+    for (int i = 0; i < hashBucketsCount; ++i) {
+      if (dynSymCount < hashBuckets[i])
+        break;
+      bucketsCount = hashBuckets[i];
+    }
+    _buckets.resize(bucketsCount);
+    _chains.resize(_entries.size());
+
+    // Create the hash table for the dynamic linker
+    for (auto ai : _entries) {
+      unsigned int dynsymIndex = ai._index;
+      unsigned int bucketpos = llvm::object::elf_hash(ai._name) % bucketsCount;
+      _chains[dynsymIndex] = _buckets[bucketpos];
+      _buckets[bucketpos] = dynsymIndex;
+    }
+
+    this->_fsize = (2 + _chains.size() + _buckets.size()) * sizeof(uint32_t);
+    this->_msize = this->_fsize;
+  }
+
+  virtual void finalize() {
+    this->_link = _symbolTable ? _symbolTable->ordinal() : 0;
+    if (this->_parent)
+      this->_parent->setLink(this->_link);
+  }
+
   virtual void write(ELFWriter *writer, llvm::FileOutputBuffer &buffer) {
     uint8_t *chunkBuffer = buffer.getBufferStart();
     uint8_t *dest = chunkBuffer + this->fileOffset();
-    // TODO: Calculate hashes and build the hash table in finalize. We currently
-    // just emit an empty hash table so the dynamic loader doesn't crash.
-    std::memset(dest, 0, this->_fsize);
+    uint32_t bucketChainCounts[2];
+    bucketChainCounts[0] = _buckets.size();
+    bucketChainCounts[1] = _chains.size();
+    std::memcpy(dest, (char *)bucketChainCounts, sizeof(bucketChainCounts));
+    dest += sizeof(bucketChainCounts);
+    // write bucket values
+    for (auto bi : _buckets) {
+      uint32_t val = (bi);
+      std::memcpy(dest, &val, sizeof(uint32_t));
+      dest += sizeof(uint32_t);
+    }
+    // write chain values
+    for (auto ci : _chains) {
+      uint32_t val = (ci);
+      std::memcpy(dest, &val, sizeof(uint32_t));
+      dest += sizeof(uint32_t);
+    }
   }
 
 private:
   std::vector<SymbolTableEntry> _entries;
+  std::vector<uint32_t> _buckets;
+  std::vector<uint32_t> _chains;
+  const DynamicSymbolTable<ELFT> *_symbolTable;
 };
 } // end namespace elf
 } // end namespace lld
 
 #endif

test/elf/Hexagon/dynlib-gotoff.test

 RUN: lld -core -target hexagon %p/Inputs/dynobj.o \
 RUN: -output=%t -emit-yaml -noinhibit-exec -output-type=shared
 RUN: FileCheck -check-prefix=CHECKGOTPLT %s < %t
 
+              - name:            __got0
+CHECKGOTPLT:    type:            got
+CHECKGOTPLT:    content:         [ 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 
+CHECKGOTPLT:                       00, 00, 00, 00 ]
+CHECKGOTPLT:    alignment:       2^3
+CHECKGOTPLT:    section-name:    .got.plt
               - name:            __got_c
 CHECKGOTPLT:    type:            got
 CHECKGOTPLT:    content:         [ 00, 00, 00, 00, 00, 00, 00, 00 ]
-CHECKGOTPLT:    alignment:       2^3
+CHECKGOTPLT:    alignment:       2^2
 CHECKGOTPLT:    section-name:    .got
 CHECKGOTPLT:    permissions:     rw-
 CHECKGOTPLT:    references:      
 CHECKGOTPLT:      - kind:            R_HEX_GLOB_DAT
 CHECKGOTPLT:        offset:          0
 CHECKGOTPLT:        target:          c
               - name:            __got_shankar
 CHECKGOTPLT:    type:            got
 CHECKGOTPLT:    content:         [ 00, 00, 00, 00, 00, 00, 00, 00 ]
-CHECKGOTPLT:    alignment:       2^3
+CHECKGOTPLT:    alignment:       2^2
 CHECKGOTPLT:    section-name:    .got
 CHECKGOTPLT:    permissions:     rw-
 CHECKGOTPLT:    references:      
 CHECKGOTPLT:      - kind:            R_HEX_GLOB_DAT
 CHECKGOTPLT:        offset:          0
 CHECKGOTPLT:        target:          shankar
               - name:            __got_fn
 CHECKGOTPLT:    type:            got

test/elf/Hexagon/dynlib-hash.test

+RUN: lld -core -target hexagon %p/Inputs/dynobj.o \
+RUN: -output=%t -output=%t -noinhibit-exec -output-type=shared
+RUN: llvm-objdump -s %t > %t1
+RUN: FileCheck -check-prefix=CHECKHASH %s < %t1
+
+CHECKHASH: Contents of section .hash:
+CHECKHASH: 00b4 03000000 06000000 05000000 01000000  ................
+CHECKHASH: 00c4 04000000 00000000 00000000 00000000  ................
+CHECKHASH: 00d4 00000000 03000000 02000000           ............

test/elf/Hexagon/dynlib-syms.test

+RUN: lld -core -target hexagon %p/Inputs/dynobj.o \
+RUN: -output=%t -output=%t -noinhibit-exec -output-type=shared
+RUN: llvm-nm -n -s %t > %t1
+RUN: FileCheck -check-prefix=CHECKSYMS %s < %t1
+
+CHECKSYMS: 00000288 A _DYNAMIC
+CHECKSYMS: 00001010 A _GLOBAL_OFFSET_TABLE_
+CHECKSYMS: 00002000 A _SDA_BASE_

test/elf/dynamic.test

 CHECK: flags r--
 
 CHECK: Dynamic Symbols:
 CHECK:   foo FUNC {{[0-9a-f]+}} 0 {{[0-9a-f]+}} undef,global
 CHECK:   i FUNC {{[0-9a-f]+}} 0 {{[0-9a-f]+}} undef,global
 CHECK:   Total: 2
 
 CHECK: Sections:
-CHECK:   .hash {{[0-9a-f]+}} 8 4 required,rodata
+CHECK:   .hash {{[0-9a-f]+}} 20 8 required,rodata
 
 CHECK: Dynamic section contains 14 entries
 CHECK:   Tag                Type                 Name/Value
 CHECK:  0x0000000000000004 (HASH)
 CHECK:  0x0000000000000005 (STRTAB)
 CHECK:  0x0000000000000006 (SYMTAB)
 CHECK:  0x000000000000000a (STRSZ)
 CHECK:  0x000000000000000b (SYMENT) 24