Index: lib/ReaderWriter/ELF/Hexagon/HexagonDynamicAtoms.h =================================================================== --- lib/ReaderWriter/ELF/Hexagon/HexagonDynamicAtoms.h +++ lib/ReaderWriter/ELF/Hexagon/HexagonDynamicAtoms.h @@ -20,16 +20,40 @@ 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 rawContent() const { + return ArrayRef(_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 rawContent() const { return ArrayRef(_defaultContent, 8); } }; +class HexagonGOTPLT0Atom : public GOTAtom { + static const uint8_t _defaultContent[16]; + +public: + HexagonGOTPLT0Atom(const File &f) : GOTAtom(f, ".got.plt") {} + + virtual ArrayRef rawContent() const { + return ArrayRef(_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]; Index: lib/ReaderWriter/ELF/Hexagon/HexagonTargetHandler.h =================================================================== --- lib/ReaderWriter/ELF/Hexagon/HexagonTargetHandler.h +++ lib/ReaderWriter/ELF/Hexagon/HexagonTargetHandler.h @@ -170,8 +170,10 @@ 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) { @@ -192,6 +194,12 @@ _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; } } Index: lib/ReaderWriter/ELF/Hexagon/HexagonTargetHandler.cpp =================================================================== --- lib/ReaderWriter/ELF/Hexagon/HexagonTargetHandler.cpp +++ lib/ReaderWriter/ELF/Hexagon/HexagonTargetHandler.cpp @@ -54,7 +54,7 @@ /// \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 @@ -132,9 +132,7 @@ class DynamicGOTPLTPass LLVM_FINAL : public GOTPLTPass { 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 @@ -145,7 +143,7 @@ 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; @@ -155,7 +153,7 @@ 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); @@ -183,7 +181,7 @@ 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 @@ -198,7 +196,7 @@ } ErrorOr 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(ref).setTarget(getGOTEntry(ref.target())); return error_code::success(); } Index: lib/ReaderWriter/ELF/OutputELFWriter.h =================================================================== --- lib/ReaderWriter/ELF/OutputELFWriter.h +++ lib/ReaderWriter/ELF/OutputELFWriter.h @@ -156,6 +156,15 @@ 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 void OutputELFWriter::buildAtomToAddressMap() { @@ -227,14 +236,20 @@ _targetInfo, ".dynsym", DefaultLayout::ORDER_DYNAMIC_SYMBOLS)); _hashTable.reset(new (_alloc) HashSection( _targetInfo, ".hash", DefaultLayout::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()); @@ -288,8 +303,7 @@ assignSectionsWithNoSegments(); if (_targetInfo.isDynamic()) - _dynamicTable->updateDynamicTable(_hashTable.get(), - _dynamicSymbolTable.get()); + _dynamicTable->updateDynamicTable(); return error_code::success(); } Index: lib/ReaderWriter/ELF/SectionChunks.h =================================================================== --- lib/ReaderWriter/ELF/SectionChunks.h +++ lib/ReaderWriter/ELF/SectionChunks.h @@ -612,6 +612,15 @@ 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); @@ -622,7 +631,7 @@ 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); @@ -774,13 +783,12 @@ this->_msize = this->_fsize; } -template void SymbolTable::finalize() { +template void SymbolTable::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) @@ -806,15 +814,32 @@ } } +template class HashSection; + template class DynamicSymbolTable : public SymbolTable { public: DynamicSymbolTable(const ELFTargetInfo &ti, const char *str, int32_t order) - : SymbolTable(ti, str, order) { + : SymbolTable(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 *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 @@ -825,9 +850,13 @@ continue; ste._symbol.st_value = atomLayout->_virtualAddr; } - SymbolTable::finalize(); + + // Dont sort the symbols + SymbolTable::finalize(false); } +private: + HashSection *_hashTable; }; template class RelocationTable : public Section { @@ -865,7 +894,7 @@ return true; } - void setSymbolTable(const SymbolTable *symbolTable) { + void setSymbolTable(const DynamicSymbolTable *symbolTable) { _symbolTable = symbolTable; } @@ -886,22 +915,26 @@ r->setSymbolAndType(index, rel.second->kind()); r->r_offset = writer->addressOfAtom(rel.first) + rel.second->offsetInAtom(); - r->r_addend = - writer->addressOfAtom(rel.second->target()) + rel.second->addend(); + // 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( - rel.second->kind())) << " relocation at " - << rel.first->name() << "@" << r->r_offset << " to " - << rel.second->target()->name() << "@" << r->r_addend - << "\n"); + 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> _relocs; - const SymbolTable *_symbolTable; + std::vector > _relocs; + const DynamicSymbolTable *_symbolTable; }; template class HashSection; @@ -981,15 +1014,30 @@ } } - void updateDynamicTable(HashSection *hashTable, - DynamicSymbolTable *dynamicSymbolTable) { + virtual void finalize() { + StringTable *dynamicStringTable = + _dynamicSymbolTable->getStringTable(); + this->_link = dynamicStringTable->ordinal(); + if (this->_parent) { + this->_parent->setInfo(this->_info); + this->_parent->setLink(this->_link); + } + } + + void setSymbolTable(DynamicSymbolTable *dynsym) { + _dynamicSymbolTable = dynsym; + } + + void setHashTable(HashSection *hsh) { _hashTable = hsh; } + + void updateDynamicTable() { StringTable *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(); @@ -1020,6 +1068,8 @@ std::size_t _dt_pltrel; std::size_t _dt_jmprel; TargetLayout *_layout; + DynamicSymbolTable *_dynamicSymbolTable; + HashSection *_hashTable; }; template class InterpSection : public Section { @@ -1047,6 +1097,26 @@ 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 HashSection : public Section { struct SymbolTableEntry { StringRef _name; @@ -1055,16 +1125,22 @@ public: HashSection(const ELFTargetInfo &ti, StringRef name, int32_t order) - : Section(ti, name) { + : Section(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; @@ -1072,16 +1148,84 @@ _entries.push_back(ste); } + /// \brief Set the dynamic symbol table + void setSymbolTable(const DynamicSymbolTable *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 _entries; + std::vector _buckets; + std::vector _chains; + const DynamicSymbolTable *_symbolTable; }; } // end namespace elf } // end namespace lld Index: test/elf/Hexagon/dynlib-gotoff.test =================================================================== --- test/elf/Hexagon/dynlib-gotoff.test +++ test/elf/Hexagon/dynlib-gotoff.test @@ -2,10 +2,16 @@ 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: @@ -15,7 +21,7 @@ - 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: Index: test/elf/Hexagon/dynlib-hash.test =================================================================== --- test/elf/Hexagon/dynlib-hash.test +++ test/elf/Hexagon/dynlib-hash.test @@ -0,0 +1,9 @@ +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 ............ Index: test/elf/Hexagon/dynlib-syms.test =================================================================== --- test/elf/Hexagon/dynlib-syms.test +++ test/elf/Hexagon/dynlib-syms.test @@ -0,0 +1,8 @@ +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_ Index: test/elf/dynamic.test =================================================================== --- test/elf/dynamic.test +++ test/elf/dynamic.test @@ -32,7 +32,7 @@ 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