Index: llvm/trunk/test/tools/llvm-readobj/elf-hash-histogram.test =================================================================== --- llvm/trunk/test/tools/llvm-readobj/elf-hash-histogram.test +++ llvm/trunk/test/tools/llvm-readobj/elf-hash-histogram.test @@ -0,0 +1,27 @@ +RUN: llvm-readobj -elf-hash-histogram %p/Inputs/gnuhash.so.elf-ppc64 \ +RUN: --elf-output-style=GNU | FileCheck %s -check-prefix PPC64GNU +RUN: llvm-readobj -elf-hash-histogram %p/Inputs/gnuhash.so.elf-x86_64 --elf-output-style=GNU \ +RUN: | FileCheck %s -check-prefix X86GNU +RUN: llvm-readobj -elf-hash-histogram %p/Inputs/got-plt.exe.elf-mipsel --elf-output-style=GNU \ +RUN: | FileCheck %s -check-prefix SYSV + +PPC64GNU: Histogram for `.gnu.hash' bucket list length (total of 3 buckets) +PPC64GNU-NEXT: Length Number % of total Coverage +PPC64GNU-NEXT: 0 1 ( 33.3%) 0.0% +PPC64GNU-NEXT: 1 1 ( 33.3%) 25.0% +PPC64GNU-NEXT: 2 0 ( 0.0%) 25.0% +PPC64GNU-NEXT: 3 1 ( 33.3%) 100.0% + +X86GNU: Histogram for `.gnu.hash' bucket list length (total of 3 buckets) +X86GNU-NEXT: Length Number % of total Coverage +X86GNU-NEXT: 0 1 ( 33.3%) 0.0% +X86GNU-NEXT: 1 1 ( 33.3%) 25.0% +X86GNU-NEXT: 2 0 ( 0.0%) 25.0% +X86GNU-NEXT: 3 1 ( 33.3%) 100.0% + +SYSV: Histogram for bucket list length (total of 3 buckets) +SYSV-NEXT: Length Number % of total Coverage +SYSV-NEXT: 0 0 ( 0.0%) 0.0% +SYSV-NEXT: 1 0 ( 0.0%) 0.0% +SYSV-NEXT: 2 2 ( 66.7%) 57.1% +SYSV-NEXT: 3 1 ( 33.3%) 100.0% Index: llvm/trunk/tools/llvm-readobj/ELFDumper.cpp =================================================================== --- llvm/trunk/tools/llvm-readobj/ELFDumper.cpp +++ llvm/trunk/tools/llvm-readobj/ELFDumper.cpp @@ -61,6 +61,8 @@ typedef typename ELFO::Elf_Half Elf_Half; \ typedef typename ELFO::Elf_Ehdr Elf_Ehdr; \ typedef typename ELFO::Elf_Word Elf_Word; \ + typedef typename ELFO::Elf_Hash Elf_Hash; \ + typedef typename ELFO::Elf_GnuHash Elf_GnuHash; \ typedef typename ELFO::uintX_t uintX_t; namespace { @@ -121,6 +123,8 @@ void printStackMap() const override; + void printHashHistogram() override; + private: std::unique_ptr> ELFDumperStyle; typedef ELFFile ELFO; @@ -234,6 +238,8 @@ const DynRegionInfo &getDynRelRegion() const { return DynRelRegion; } const DynRegionInfo &getDynRelaRegion() const { return DynRelaRegion; } const DynRegionInfo &getDynPLTRelRegion() const { return DynPLTRelRegion; } + const Elf_Hash *getHashTable() const { return HashTable; } + const Elf_GnuHash *getGnuHashTable() const { return GnuHashTable; } }; template @@ -284,6 +290,7 @@ const Elf_Sym *FirstSym, StringRef StrTable, bool IsDynamic) = 0; virtual void printProgramHeaders(const ELFFile *Obj) = 0; + virtual void printHashHistogram(const ELFFile *Obj) = 0; const ELFDumper *dumper() const { return Dumper; } private: const ELFDumper *Dumper; @@ -305,6 +312,7 @@ virtual void printSymtabMessage(const ELFO *Obj, StringRef Name, size_t Offset) override; void printProgramHeaders(const ELFO *Obj) override; + void printHashHistogram(const ELFFile *Obj) override; private: struct Field { @@ -357,6 +365,7 @@ void printDynamicSymbols(const ELFO *Obj) override; void printDynamicRelocations(const ELFO *Obj) override; void printProgramHeaders(const ELFO *Obj) override; + void printHashHistogram(const ELFFile *Obj) override; private: void printRelocation(const ELFO *Obj, Elf_Rela Rel, const Elf_Shdr *SymTab); @@ -1390,6 +1399,9 @@ ELFDumperStyle->printDynamicSymbols(Obj); } +template void ELFDumper::printHashHistogram() { + ELFDumperStyle->printHashHistogram(Obj); +} #define LLVM_READOBJ_TYPE_CASE(name) \ case DT_##name: return #name @@ -2920,6 +2932,111 @@ } } +// Hash histogram shows statistics of how efficient the hash was for the +// dynamic symbol table. The table shows number of hash buckets for different +// lengths of chains as absolute number and percentage of the total buckets. +// Additionally cumulative coverage of symbols for each set of buckets. +template +void GNUStyle::printHashHistogram(const ELFFile *Obj) { + + const Elf_Hash *HashTable = this->dumper()->getHashTable(); + const Elf_GnuHash *GnuHashTable = this->dumper()->getGnuHashTable(); + + // Print histogram for .hash section + if (HashTable) { + size_t NBucket = HashTable->nbucket; + size_t NChain = HashTable->nchain; + ArrayRef Buckets = HashTable->buckets(); + ArrayRef Chains = HashTable->chains(); + size_t TotalSyms = 0; + // If hash table is correct, we have at least chains with 0 length + size_t MaxChain = 1; + size_t CumulativeNonZero = 0; + + if (NChain == 0 || NBucket == 0) + return; + + std::vector ChainLen(NBucket, 0); + // Go over all buckets and and note chain lengths of each bucket (total + // unique chain lengths). + for (size_t B = 0; B < NBucket; B++) { + for (size_t C = Buckets[B]; C > 0 && C < NChain; C = Chains[C]) + if (MaxChain <= ++ChainLen[B]) + MaxChain++; + TotalSyms += ChainLen[B]; + } + + if (!TotalSyms) + return; + + std::vector Count(MaxChain, 0) ; + // Count how long is the chain for each bucket + for (size_t B = 0; B < NBucket; B++) + ++Count[ChainLen[B]]; + // Print Number of buckets with each chain lengths and their cumulative + // coverage of the symbols + OS << "Histogram for bucket list length (total of " << NBucket + << " buckets)\n" + << " Length Number % of total Coverage\n"; + for (size_t I = 0; I < MaxChain; I++) { + CumulativeNonZero += Count[I] * I; + OS << format("%7lu %-10lu (%5.1f%%) %5.1f%%\n", I, Count[I], + (Count[I] * 100.0) / NBucket, + (CumulativeNonZero * 100.0) / TotalSyms); + } + } + + // Print histogram for .gnu.hash section + if (GnuHashTable) { + size_t NBucket = GnuHashTable->nbuckets; + ArrayRef Buckets = GnuHashTable->buckets(); + unsigned NumSyms = this->dumper()->dynamic_symbols().size(); + if (!NumSyms) + return; + ArrayRef Chains = GnuHashTable->values(NumSyms); + size_t Symndx = GnuHashTable->symndx; + size_t TotalSyms = 0; + size_t MaxChain = 1; + size_t CumulativeNonZero = 0; + + if (Chains.size() == 0 || NBucket == 0) + return; + + std::vector ChainLen(NBucket, 0); + + for (size_t B = 0; B < NBucket; B++) { + if (!Buckets[B]) + continue; + size_t Len = 1; + for (size_t C = Buckets[B] - Symndx; + C < Chains.size() && (Chains[C] & 1) == 0; C++) + if (MaxChain < ++Len) + MaxChain++; + ChainLen[B] = Len; + TotalSyms += Len; + } + MaxChain++; + + if (!TotalSyms) + return; + + std::vector Count(MaxChain, 0) ; + for (size_t B = 0; B < NBucket; B++) + ++Count[ChainLen[B]]; + // Print Number of buckets with each chain lengths and their cumulative + // coverage of the symbols + OS << "Histogram for `.gnu.hash' bucket list length (total of " << NBucket + << " buckets)\n" + << " Length Number % of total Coverage\n"; + for (size_t I = 0; I void LLVMStyle::printFileHeaders(const ELFO *Obj) { const Elf_Ehdr *e = Obj->getHeader(); { @@ -3281,3 +3398,7 @@ W.printNumber("Alignment", Phdr.p_align); } } +template +void LLVMStyle::printHashHistogram(const ELFFile *Obj) { + W.startLine() << "Hash Histogram not implemented!\n"; +} Index: llvm/trunk/tools/llvm-readobj/ObjDumper.h =================================================================== --- llvm/trunk/tools/llvm-readobj/ObjDumper.h +++ llvm/trunk/tools/llvm-readobj/ObjDumper.h @@ -43,6 +43,7 @@ virtual void printLoadName() {} virtual void printVersionInfo() {} virtual void printGroupSections() {} + virtual void printHashHistogram() {} // Only implemented for ARM ELF at this time. virtual void printAttributes() { } Index: llvm/trunk/tools/llvm-readobj/llvm-readobj.cpp =================================================================== --- llvm/trunk/tools/llvm-readobj/llvm-readobj.cpp +++ llvm/trunk/tools/llvm-readobj/llvm-readobj.cpp @@ -232,6 +232,11 @@ cl::desc("Display ELF section group contents")); cl::alias SectionGroupsShort("g", cl::desc("Alias for -elf-sections-groups"), cl::aliasopt(SectionGroups)); + cl::opt HashHistogram( + "elf-hash-histogram", + cl::desc("Display bucket list histogram for hash sections")); + cl::alias HashHistogramShort("I", cl::desc("Alias for -elf-hash-histogram"), + cl::aliasopt(HashHistogram)); cl::opt Output("elf-output-style", cl::desc("Specify ELF dump style"), @@ -360,6 +365,8 @@ } if (opts::SectionGroups) Dumper->printGroupSections(); + if (opts::HashHistogram) + Dumper->printHashHistogram(); } if (Obj->isCOFF()) { if (opts::COFFImports)