Index: lld/trunk/ELF/OutputSections.h =================================================================== --- lld/trunk/ELF/OutputSections.h +++ lld/trunk/ELF/OutputSections.h @@ -44,7 +44,6 @@ Base, EHFrame, EHFrameHdr, - GnuHashTable, HashTable, Merge, Plt, @@ -150,11 +149,6 @@ std::vector> Entries; }; -struct SymbolTableEntry { - SymbolBody *Symbol; - size_t StrTabOffset; -}; - // For more information about .gnu.version and .gnu.version_r see: // https://www.akkadia.org/drepper/symbol-versioning @@ -336,48 +330,6 @@ } }; -// Outputs GNU Hash section. For detailed explanation see: -// https://blogs.oracle.com/ali/entry/gnu_hash_elf_sections -template -class GnuHashTableSection final : public OutputSectionBase { - typedef typename ELFT::Off Elf_Off; - typedef typename ELFT::Word Elf_Word; - typedef typename ELFT::uint uintX_t; - -public: - GnuHashTableSection(); - void finalize() override; - void writeTo(uint8_t *Buf) override; - - // Adds symbols to the hash table. - // Sorts the input to satisfy GNU hash section requirements. - void addSymbols(std::vector &Symbols); - Kind getKind() const override { return GnuHashTable; } - static bool classof(const OutputSectionBase *B) { - return B->getKind() == GnuHashTable; - } - -private: - static unsigned calcNBuckets(unsigned NumHashed); - static unsigned calcMaskWords(unsigned NumHashed); - - void writeHeader(uint8_t *&Buf); - void writeBloomFilter(uint8_t *&Buf); - void writeHashTable(uint8_t *Buf); - - struct SymbolData { - SymbolBody *Body; - size_t STName; - uint32_t Hash; - }; - - std::vector Symbols; - - unsigned MaskWords; - unsigned NBuckets; - unsigned Shift2; -}; - // --eh-frame-hdr option tells linker to construct a header for all the // .eh_frame sections. This header is placed to a section named .eh_frame_hdr // and also to a PT_GNU_EH_FRAME segment. @@ -420,7 +372,6 @@ static EhFrameHeader *EhFrameHdr; static EhOutputSection *EhFrame; static GdbIndexSection *GdbIndex; - static GnuHashTableSection *GnuHashTab; static HashTableSection *HashTab; static OutputSection *Bss; static OutputSection *MipsRldMap; @@ -476,7 +427,6 @@ template EhFrameHeader *Out::EhFrameHdr; template EhOutputSection *Out::EhFrame; template GdbIndexSection *Out::GdbIndex; -template GnuHashTableSection *Out::GnuHashTab; template HashTableSection *Out::HashTab; template OutputSection *Out::Bss; template OutputSection *Out::MipsRldMap; Index: lld/trunk/ELF/OutputSections.cpp =================================================================== --- lld/trunk/ELF/OutputSections.cpp +++ lld/trunk/ELF/OutputSections.cpp @@ -179,153 +179,6 @@ } } -static uint32_t hashGnu(StringRef Name) { - uint32_t H = 5381; - for (uint8_t C : Name) - H = (H << 5) + H + C; - return H; -} - -template -GnuHashTableSection::GnuHashTableSection() - : OutputSectionBase(".gnu.hash", SHT_GNU_HASH, SHF_ALLOC) { - this->Entsize = ELFT::Is64Bits ? 0 : 4; - this->Addralign = sizeof(uintX_t); -} - -template -unsigned GnuHashTableSection::calcNBuckets(unsigned NumHashed) { - if (!NumHashed) - return 0; - - // These values are prime numbers which are not greater than 2^(N-1) + 1. - // In result, for any particular NumHashed we return a prime number - // which is not greater than NumHashed. - static const unsigned Primes[] = { - 1, 1, 3, 3, 7, 13, 31, 61, 127, 251, - 509, 1021, 2039, 4093, 8191, 16381, 32749, 65521, 131071}; - - return Primes[std::min(Log2_32_Ceil(NumHashed), - array_lengthof(Primes) - 1)]; -} - -// Bloom filter estimation: at least 8 bits for each hashed symbol. -// GNU Hash table requirement: it should be a power of 2, -// the minimum value is 1, even for an empty table. -// Expected results for a 32-bit target: -// calcMaskWords(0..4) = 1 -// calcMaskWords(5..8) = 2 -// calcMaskWords(9..16) = 4 -// For a 64-bit target: -// calcMaskWords(0..8) = 1 -// calcMaskWords(9..16) = 2 -// calcMaskWords(17..32) = 4 -template -unsigned GnuHashTableSection::calcMaskWords(unsigned NumHashed) { - if (!NumHashed) - return 1; - return NextPowerOf2((NumHashed - 1) / sizeof(Elf_Off)); -} - -template void GnuHashTableSection::finalize() { - unsigned NumHashed = Symbols.size(); - NBuckets = calcNBuckets(NumHashed); - MaskWords = calcMaskWords(NumHashed); - // Second hash shift estimation: just predefined values. - Shift2 = ELFT::Is64Bits ? 6 : 5; - - this->Link = In::DynSymTab->OutSec->SectionIndex; - this->Size = sizeof(Elf_Word) * 4 // Header - + sizeof(Elf_Off) * MaskWords // Bloom Filter - + sizeof(Elf_Word) * NBuckets // Hash Buckets - + sizeof(Elf_Word) * NumHashed; // Hash Values -} - -template void GnuHashTableSection::writeTo(uint8_t *Buf) { - writeHeader(Buf); - if (Symbols.empty()) - return; - writeBloomFilter(Buf); - writeHashTable(Buf); -} - -template -void GnuHashTableSection::writeHeader(uint8_t *&Buf) { - auto *P = reinterpret_cast(Buf); - *P++ = NBuckets; - *P++ = In::DynSymTab->getNumSymbols() - Symbols.size(); - *P++ = MaskWords; - *P++ = Shift2; - Buf = reinterpret_cast(P); -} - -template -void GnuHashTableSection::writeBloomFilter(uint8_t *&Buf) { - unsigned C = sizeof(Elf_Off) * 8; - - auto *Masks = reinterpret_cast(Buf); - for (const SymbolData &Sym : Symbols) { - size_t Pos = (Sym.Hash / C) & (MaskWords - 1); - uintX_t V = (uintX_t(1) << (Sym.Hash % C)) | - (uintX_t(1) << ((Sym.Hash >> Shift2) % C)); - Masks[Pos] |= V; - } - Buf += sizeof(Elf_Off) * MaskWords; -} - -template -void GnuHashTableSection::writeHashTable(uint8_t *Buf) { - Elf_Word *Buckets = reinterpret_cast(Buf); - Elf_Word *Values = Buckets + NBuckets; - - int PrevBucket = -1; - int I = 0; - for (const SymbolData &Sym : Symbols) { - int Bucket = Sym.Hash % NBuckets; - assert(PrevBucket <= Bucket); - if (Bucket != PrevBucket) { - Buckets[Bucket] = Sym.Body->DynsymIndex; - PrevBucket = Bucket; - if (I > 0) - Values[I - 1] |= 1; - } - Values[I] = Sym.Hash & ~1; - ++I; - } - if (I > 0) - Values[I - 1] |= 1; -} - -// Add symbols to this symbol hash table. Note that this function -// destructively sort a given vector -- which is needed because -// GNU-style hash table places some sorting requirements. -template -void GnuHashTableSection::addSymbols(std::vector &V) { - // Ideally this will just be 'auto' but GCC 6.1 is not able - // to deduce it correctly. - std::vector::iterator Mid = - std::stable_partition(V.begin(), V.end(), [](const SymbolTableEntry &S) { - return S.Symbol->isUndefined(); - }); - if (Mid == V.end()) - return; - for (auto I = Mid, E = V.end(); I != E; ++I) { - SymbolBody *B = I->Symbol; - size_t StrOff = I->StrTabOffset; - Symbols.push_back({B, StrOff, hashGnu(B->getName())}); - } - - unsigned NBuckets = calcNBuckets(Symbols.size()); - std::stable_sort(Symbols.begin(), Symbols.end(), - [&](const SymbolData &L, const SymbolData &R) { - return L.Hash % NBuckets < R.Hash % NBuckets; - }); - - V.erase(Mid, V.end()); - for (const SymbolData &Sym : Symbols) - V.push_back({Sym.Body, Sym.STName}); -} - // Returns the number of version definition entries. Because the first entry // is for the version definition itself, it is the number of versioned symbols // plus one. Note that we don't support multiple versions yet. @@ -1085,11 +938,6 @@ template class PltSection; template class PltSection; -template class GnuHashTableSection; -template class GnuHashTableSection; -template class GnuHashTableSection; -template class GnuHashTableSection; - template class HashTableSection; template class HashTableSection; template class HashTableSection; Index: lld/trunk/ELF/SyntheticSections.h =================================================================== --- lld/trunk/ELF/SyntheticSections.h +++ lld/trunk/ELF/SyntheticSections.h @@ -11,7 +11,6 @@ #define LLD_ELF_SYNTHETIC_SECTION_H #include "InputSection.h" -#include "OutputSections.h" #include "llvm/ADT/SmallPtrSet.h" namespace lld { @@ -401,6 +400,11 @@ std::vector> Relocs; }; +struct SymbolTableEntry { + SymbolBody *Symbol; + size_t StrTabOffset; +}; + template class SymbolTableSection final : public SyntheticSection { public: @@ -432,6 +436,46 @@ std::vector Symbols; }; +// Outputs GNU Hash section. For detailed explanation see: +// https://blogs.oracle.com/ali/entry/gnu_hash_elf_sections +template +class GnuHashTableSection final : public SyntheticSection { + typedef typename ELFT::Off Elf_Off; + typedef typename ELFT::Word Elf_Word; + typedef typename ELFT::uint uintX_t; + +public: + GnuHashTableSection(); + void finalize() override; + void writeTo(uint8_t *Buf) override; + size_t getSize() const override { return this->Size; } + + // Adds symbols to the hash table. + // Sorts the input to satisfy GNU hash section requirements. + void addSymbols(std::vector &Symbols); + +private: + static unsigned calcNBuckets(unsigned NumHashed); + static unsigned calcMaskWords(unsigned NumHashed); + + void writeHeader(uint8_t *&Buf); + void writeBloomFilter(uint8_t *&Buf); + void writeHashTable(uint8_t *Buf); + + struct SymbolData { + SymbolBody *Body; + size_t STName; + uint32_t Hash; + }; + + std::vector Symbols; + + unsigned MaskWords; + unsigned NBuckets; + unsigned Shift2; + uintX_t Size = 0; +}; + template InputSection *createCommonSection(); template InputSection *createInterpSection(); template MergeInputSection *createCommentSection(); @@ -443,6 +487,7 @@ static DynamicSection *Dynamic; static StringTableSection *DynStrTab; static SymbolTableSection *DynSymTab; + static GnuHashTableSection *GnuHashTab; static GotSection *Got; static MipsGotSection *MipsGot; static GotPltSection *GotPlt; @@ -462,6 +507,7 @@ template DynamicSection *In::Dynamic; template StringTableSection *In::DynStrTab; template SymbolTableSection *In::DynSymTab; +template GnuHashTableSection *In::GnuHashTab; template GotSection *In::Got; template MipsGotSection *In::MipsGot; template GotPltSection *In::GotPlt; Index: lld/trunk/ELF/SyntheticSections.cpp =================================================================== --- lld/trunk/ELF/SyntheticSections.cpp +++ lld/trunk/ELF/SyntheticSections.cpp @@ -794,8 +794,8 @@ add({DT_SYMENT, sizeof(Elf_Sym)}); add({DT_STRTAB, In::DynStrTab}); add({DT_STRSZ, In::DynStrTab->getSize()}); - if (Out::GnuHashTab) - add({DT_GNU_HASH, Out::GnuHashTab}); + if (In::GnuHashTab) + add({DT_GNU_HASH, In::GnuHashTab}); if (Out::HashTab) add({DT_HASH, Out::HashTab}); @@ -1021,9 +1021,9 @@ }); return; } - if (Out::GnuHashTab) + if (In::GnuHashTab) // NB: It also sorts Symbols to meet the GNU hash table requirements. - Out::GnuHashTab->addSymbols(Symbols); + In::GnuHashTab->addSymbols(Symbols); else if (Config->EMachine == EM_MIPS) std::stable_sort(Symbols.begin(), Symbols.end(), [](const SymbolTableEntry &L, const SymbolTableEntry &R) { @@ -1142,6 +1142,154 @@ return nullptr; } +template +GnuHashTableSection::GnuHashTableSection() + : SyntheticSection(SHF_ALLOC, SHT_GNU_HASH, sizeof(uintX_t), + ".gnu.hash") { + this->Entsize = ELFT::Is64Bits ? 0 : 4; +} + +template +unsigned GnuHashTableSection::calcNBuckets(unsigned NumHashed) { + if (!NumHashed) + return 0; + + // These values are prime numbers which are not greater than 2^(N-1) + 1. + // In result, for any particular NumHashed we return a prime number + // which is not greater than NumHashed. + static const unsigned Primes[] = { + 1, 1, 3, 3, 7, 13, 31, 61, 127, 251, + 509, 1021, 2039, 4093, 8191, 16381, 32749, 65521, 131071}; + + return Primes[std::min(Log2_32_Ceil(NumHashed), + array_lengthof(Primes) - 1)]; +} + +// Bloom filter estimation: at least 8 bits for each hashed symbol. +// GNU Hash table requirement: it should be a power of 2, +// the minimum value is 1, even for an empty table. +// Expected results for a 32-bit target: +// calcMaskWords(0..4) = 1 +// calcMaskWords(5..8) = 2 +// calcMaskWords(9..16) = 4 +// For a 64-bit target: +// calcMaskWords(0..8) = 1 +// calcMaskWords(9..16) = 2 +// calcMaskWords(17..32) = 4 +template +unsigned GnuHashTableSection::calcMaskWords(unsigned NumHashed) { + if (!NumHashed) + return 1; + return NextPowerOf2((NumHashed - 1) / sizeof(Elf_Off)); +} + +template void GnuHashTableSection::finalize() { + unsigned NumHashed = Symbols.size(); + NBuckets = calcNBuckets(NumHashed); + MaskWords = calcMaskWords(NumHashed); + // Second hash shift estimation: just predefined values. + Shift2 = ELFT::Is64Bits ? 6 : 5; + + this->OutSec->Entsize = this->Entsize; + this->OutSec->Link = this->Link = In::DynSymTab->OutSec->SectionIndex; + this->Size = sizeof(Elf_Word) * 4 // Header + + sizeof(Elf_Off) * MaskWords // Bloom Filter + + sizeof(Elf_Word) * NBuckets // Hash Buckets + + sizeof(Elf_Word) * NumHashed; // Hash Values +} + +template void GnuHashTableSection::writeTo(uint8_t *Buf) { + writeHeader(Buf); + if (Symbols.empty()) + return; + writeBloomFilter(Buf); + writeHashTable(Buf); +} + +template +void GnuHashTableSection::writeHeader(uint8_t *&Buf) { + auto *P = reinterpret_cast(Buf); + *P++ = NBuckets; + *P++ = In::DynSymTab->getNumSymbols() - Symbols.size(); + *P++ = MaskWords; + *P++ = Shift2; + Buf = reinterpret_cast(P); +} + +template +void GnuHashTableSection::writeBloomFilter(uint8_t *&Buf) { + unsigned C = sizeof(Elf_Off) * 8; + + auto *Masks = reinterpret_cast(Buf); + for (const SymbolData &Sym : Symbols) { + size_t Pos = (Sym.Hash / C) & (MaskWords - 1); + uintX_t V = (uintX_t(1) << (Sym.Hash % C)) | + (uintX_t(1) << ((Sym.Hash >> Shift2) % C)); + Masks[Pos] |= V; + } + Buf += sizeof(Elf_Off) * MaskWords; +} + +template +void GnuHashTableSection::writeHashTable(uint8_t *Buf) { + Elf_Word *Buckets = reinterpret_cast(Buf); + Elf_Word *Values = Buckets + NBuckets; + + int PrevBucket = -1; + int I = 0; + for (const SymbolData &Sym : Symbols) { + int Bucket = Sym.Hash % NBuckets; + assert(PrevBucket <= Bucket); + if (Bucket != PrevBucket) { + Buckets[Bucket] = Sym.Body->DynsymIndex; + PrevBucket = Bucket; + if (I > 0) + Values[I - 1] |= 1; + } + Values[I] = Sym.Hash & ~1; + ++I; + } + if (I > 0) + Values[I - 1] |= 1; +} + +static uint32_t hashGnu(StringRef Name) { + uint32_t H = 5381; + for (uint8_t C : Name) + H = (H << 5) + H + C; + return H; +} + +// Add symbols to this symbol hash table. Note that this function +// destructively sort a given vector -- which is needed because +// GNU-style hash table places some sorting requirements. +template +void GnuHashTableSection::addSymbols(std::vector &V) { + // Ideally this will just be 'auto' but GCC 6.1 is not able + // to deduce it correctly. + std::vector::iterator Mid = + std::stable_partition(V.begin(), V.end(), [](const SymbolTableEntry &S) { + return S.Symbol->isUndefined(); + }); + if (Mid == V.end()) + return; + for (auto I = Mid, E = V.end(); I != E; ++I) { + SymbolBody *B = I->Symbol; + size_t StrOff = I->StrTabOffset; + Symbols.push_back({B, StrOff, hashGnu(B->getName())}); + } + + unsigned NBuckets = calcNBuckets(Symbols.size()); + std::stable_sort(Symbols.begin(), Symbols.end(), + [&](const SymbolData &L, const SymbolData &R) { + return L.Hash % NBuckets < R.Hash % NBuckets; + }); + + V.erase(Mid, V.end()); + for (const SymbolData &Sym : Symbols) + V.push_back({Sym.Body, Sym.STName}); +} + template InputSection *elf::createCommonSection(); template InputSection *elf::createCommonSection(); template InputSection *elf::createCommonSection(); @@ -1236,3 +1384,8 @@ template class elf::SymbolTableSection; template class elf::SymbolTableSection; template class elf::SymbolTableSection; + +template class elf::GnuHashTableSection; +template class elf::GnuHashTableSection; +template class elf::GnuHashTableSection; +template class elf::GnuHashTableSection; Index: lld/trunk/ELF/Writer.cpp =================================================================== --- lld/trunk/ELF/Writer.cpp +++ lld/trunk/ELF/Writer.cpp @@ -239,7 +239,7 @@ Out::EhFrameHdr = make>(); if (Config->GnuHash) - Out::GnuHashTab = make>(); + In::GnuHashTab = make>(); if (Config->SysvHash) Out::HashTab = make>(); if (Config->GdbIndex) @@ -943,23 +943,19 @@ Sec->ShName = In::ShStrTab->addString(Sec->getName()); } - // FIXME: this should be removed after converting GnuHashTableSection - // to input section. - // Finalizers fix each section's size. - // .dynsym is finalized early since that may fill up .gnu.hash. - finalizeSynthetic({In::DynSymTab}); - // Fill other section headers. The dynamic table is finalized // at the end because some tags like RELSZ depend on result // of finalizing other sections. for (OutputSectionBase *Sec : OutputSections) Sec->finalize(); - // Dynamic section must be the last one in this list. + // Dynamic section must be the last one in this list and dynamic + // symbol table section (DynSymTab) must be the first one. finalizeSynthetic( - {In::SymTab, In::ShStrTab, In::StrTab, - In::DynStrTab, In::Got, In::MipsGot, In::GotPlt, - In::RelaDyn, In::RelaPlt, In::Dynamic}); + {In::DynSymTab, In::GnuHashTab, In::SymTab, + In::ShStrTab, In::StrTab, In::DynStrTab, In::Got, + In::MipsGot, In::GotPlt, In::RelaDyn, + In::RelaPlt, In::Dynamic}); } template bool Writer::needsGot() { @@ -1000,7 +996,7 @@ if (HasVerNeed) Add(Out::VerNeed); - Add(Out::GnuHashTab); + addInputSec(In::GnuHashTab); Add(Out::HashTab); addInputSec(In::Dynamic); addInputSec(In::DynStrTab);