diff --git a/llvm/test/tools/llvm-readobj/ELF/hash-histogram.test b/llvm/test/tools/llvm-readobj/ELF/hash-histogram.test --- a/llvm/test/tools/llvm-readobj/ELF/hash-histogram.test +++ b/llvm/test/tools/llvm-readobj/ELF/hash-histogram.test @@ -12,6 +12,10 @@ # RUN: yaml2obj --docnum=1 -D BITS=64 %s -o %t1-64.o # RUN: llvm-readelf --elf-hash-histogram %t1-64.o | FileCheck %s --check-prefix=HIST +## Check that LLVM output has the expected format. +# RUN: llvm-readobj --elf-hash-histogram %t1-32.o | FileCheck %s --check-prefix=LLVM-HIST +# RUN: llvm-readobj --elf-hash-histogram %t1-64.o | FileCheck %s --check-prefix=LLVM-HIST + # HIST: Histogram for bucket list length (total of 3 buckets) # HIST-NEXT: Length Number % of total Coverage # HIST-NEXT: 0 2 ( 66.7%) 0.0% @@ -26,6 +30,65 @@ # HIST-NEXT: 3 1 ( 33.3%) 100.0% # HIST-NOT: {{.}} +# LLVM-HIST: HashHistogram { +# LLVM-HIST-NEXT: TotalBuckets: 3 +# LLVM-HIST-NEXT: Chains [ +# LLVM-HIST-NEXT: Chain { +# LLVM-HIST-NEXT: Length: 0 +# LLVM-HIST-NEXT: Count: 2 +# LLVM-HIST-NEXT: Percentage: 66.7 +# LLVM-HIST-NEXT: Coverage: 0.0 +# LLVM-HIST-NEXT: } +# LLVM-HIST-NEXT: Chain { +# LLVM-HIST-NEXT: Length: 1 +# LLVM-HIST-NEXT: Count: 0 +# LLVM-HIST-NEXT: Percentage: 0.0 +# LLVM-HIST-NEXT: Coverage: 0.0 +# LLVM-HIST-NEXT: } +# LLVM-HIST-NEXT: Chain { +# LLVM-HIST-NEXT: Length: 2 +# LLVM-HIST-NEXT: Count: 0 +# LLVM-HIST-NEXT: Percentage: 0.0 +# LLVM-HIST-NEXT: Coverage: 0.0 +# LLVM-HIST-NEXT: } +# LLVM-HIST-NEXT: Chain { +# LLVM-HIST-NEXT: Length: 3 +# LLVM-HIST-NEXT: Count: 1 +# LLVM-HIST-NEXT: Percentage: 33.3 +# LLVM-HIST-NEXT: Coverage: 100.0 +# LLVM-HIST-NEXT: } +# LLVM-HIST-NEXT: ] +# LLVM-HIST-NEXT: } +# LLVM-HIST-NEXT: GnuHashHistogram { +# LLVM-HIST-NEXT: TotalBuckets: 3 +# LLVM-HIST-NEXT: Buckets [ +# LLVM-HIST-NEXT: Bucket { +# LLVM-HIST-NEXT: Length: 0 +# LLVM-HIST-NEXT: Count: 1 +# LLVM-HIST-NEXT: Percentage: 33.3 +# LLVM-HIST-NEXT: Coverage: 0.0 +# LLVM-HIST-NEXT: } +# LLVM-HIST-NEXT: Bucket { +# LLVM-HIST-NEXT: Length: 1 +# LLVM-HIST-NEXT: Count: 1 +# LLVM-HIST-NEXT: Percentage: 33.3 +# LLVM-HIST-NEXT: Coverage: 25.0 +# LLVM-HIST-NEXT: } +# LLVM-HIST-NEXT: Bucket { +# LLVM-HIST-NEXT: Length: 2 +# LLVM-HIST-NEXT: Count: 0 +# LLVM-HIST-NEXT: Percentage: 0.0 +# LLVM-HIST-NEXT: Coverage: 25.0 +# LLVM-HIST-NEXT: } +# LLVM-HIST-NEXT: Bucket { +# LLVM-HIST-NEXT: Length: 3 +# LLVM-HIST-NEXT: Count: 1 +# LLVM-HIST-NEXT: Percentage: 33.3 +# LLVM-HIST-NEXT: Coverage: 100.0 +# LLVM-HIST-NEXT: } +# LLVM-HIST-NEXT: ] +# LLVM-HIST-NEXT: } + --- !ELF FileHeader: Class: ELFCLASS[[BITS]] diff --git a/llvm/tools/llvm-readobj/ELFDumper.cpp b/llvm/tools/llvm-readobj/ELFDumper.cpp --- a/llvm/tools/llvm-readobj/ELFDumper.cpp +++ b/llvm/tools/llvm-readobj/ELFDumper.cpp @@ -222,6 +222,13 @@ void printStackMap() const override; void printMemtag() override; + // Hash histogram shows statistics of how efficient the hash was for the + // dynamic symbol table. The table shows the number of hash buckets for + // different lengths of chains as an absolute number and percentage of the + // total buckets, and the cumulative coverage of symbols for each set of + // buckets. + void printHashHistograms() override; + const object::ELFObjectFile &getElfObject() const { return ObjF; }; std::string describe(const Elf_Shdr &Sec) const; @@ -304,6 +311,12 @@ const ArrayRef> DynamicEntries, const ArrayRef AndroidNoteDesc) = 0; + virtual void printHashHistogram(const Elf_Hash &HashTable) const; + virtual void printGnuHashHistogram(const Elf_GnuHash &GnuHashTable) const; + virtual void printHashHistogramStats(size_t NBucket, size_t MaxChain, + size_t TotalSyms, ArrayRef Count, + bool IsGnu) const = 0; + Expected> getVersionTable(const Elf_Shdr &Sec, ArrayRef *SymTab, StringRef *StrTab, const Elf_Shdr **SymTabSec) const; @@ -572,7 +585,6 @@ void printVersionSymbolSection(const Elf_Shdr *Sec) override; void printVersionDefinitionSection(const Elf_Shdr *Sec) override; void printVersionDependencySection(const Elf_Shdr *Sec) override; - void printHashHistograms() override; void printCGProfile() override; void printBBAddrMaps() override; void printAddrsig() override; @@ -582,10 +594,11 @@ void printMemtag( const ArrayRef> DynamicEntries, const ArrayRef AndroidNoteDesc) override; + void printHashHistogramStats(size_t NBucket, size_t MaxChain, + size_t TotalSyms, ArrayRef Count, + bool IsGnu) const override; private: - void printHashHistogram(const Elf_Hash &HashTable); - void printGnuHashHistogram(const Elf_GnuHash &GnuHashTable); void printHashTableSymbols(const Elf_Hash &HashTable); void printGnuHashTableSymbols(const Elf_GnuHash &GnuHashTable); @@ -679,7 +692,6 @@ void printVersionSymbolSection(const Elf_Shdr *Sec) override; void printVersionDefinitionSection(const Elf_Shdr *Sec) override; void printVersionDependencySection(const Elf_Shdr *Sec) override; - void printHashHistograms() override; void printCGProfile() override; void printBBAddrMaps() override; void printAddrsig() override; @@ -691,6 +703,9 @@ const ArrayRef AndroidNoteDesc) override; void printSymbolSection(const Elf_Sym &Symbol, unsigned SymIndex, DataRegion ShndxTable) const; + void printHashHistogramStats(size_t NBucket, size_t MaxChain, + size_t TotalSyms, ArrayRef Count, + bool IsGnu) const override; private: void printRelrReloc(const Elf_Relr &R) override; @@ -2682,6 +2697,116 @@ W.printHexList("Values", *Chains); } +template void ELFDumper::printHashHistograms() { + // Print histogram for the .hash section. + if (this->HashTable) { + if (Error E = checkHashTable(*this, this->HashTable)) + this->reportUniqueWarning(std::move(E)); + else + printHashHistogram(*this->HashTable); + } + + // Print histogram for the .gnu.hash section. + if (this->GnuHashTable) { + if (Error E = checkGNUHashTable(this->Obj, this->GnuHashTable)) + this->reportUniqueWarning(std::move(E)); + else + printGnuHashHistogram(*this->GnuHashTable); + } +} + +template +void ELFDumper::printHashHistogram(const Elf_Hash &HashTable) const { + 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; + + 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) { + BitVector Visited(NChain); + for (size_t C = Buckets[B]; C < NChain; C = Chains[C]) { + if (C == ELF::STN_UNDEF) + break; + if (Visited[C]) { + this->reportUniqueWarning( + ".hash section is invalid: bucket " + Twine(C) + + ": a cycle was detected in the linked chain"); + break; + } + Visited[C] = true; + 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. + printHashHistogramStats(NBucket, MaxChain, TotalSyms, Count, /*IsGnu=*/false); +} + +template +void ELFDumper::printGnuHashHistogram( + const Elf_GnuHash &GnuHashTable) const { + Expected> ChainsOrErr = + getGnuHashTableChains(this->DynSymRegion, &GnuHashTable); + if (!ChainsOrErr) { + this->reportUniqueWarning("unable to print the GNU hash table histogram: " + + toString(ChainsOrErr.takeError())); + return; + } + + ArrayRef Chains = *ChainsOrErr; + size_t Symndx = GnuHashTable.symndx; + size_t TotalSyms = 0; + size_t MaxChain = 1; + + size_t NBucket = GnuHashTable.nbuckets; + if (Chains.empty() || NBucket == 0) + return; + + ArrayRef Buckets = GnuHashTable.buckets(); + 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. + printHashHistogramStats(NBucket, MaxChain, TotalSyms, Count, /*IsGnu=*/true); +} + template void ELFDumper::printLoadName() { StringRef SOName = ""; if (SONameOffset) @@ -4831,108 +4956,16 @@ } template -void GNUELFDumper::printHashHistogram(const Elf_Hash &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++) { - BitVector Visited(NChain); - for (size_t C = Buckets[B]; C < NChain; C = Chains[C]) { - if (C == ELF::STN_UNDEF) - break; - if (Visited[C]) { - this->reportUniqueWarning(".hash section is invalid: bucket " + - Twine(C) + - ": a cycle was detected in the linked chain"); - break; - } - Visited[C] = true; - 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); - } -} - -template -void GNUELFDumper::printGnuHashHistogram( - const Elf_GnuHash &GnuHashTable) { - Expected> ChainsOrErr = - getGnuHashTableChains(this->DynSymRegion, &GnuHashTable); - if (!ChainsOrErr) { - this->reportUniqueWarning("unable to print the GNU hash table histogram: " + - toString(ChainsOrErr.takeError())); - return; - } - - ArrayRef Chains = *ChainsOrErr; - size_t Symndx = GnuHashTable.symndx; - size_t TotalSyms = 0; - size_t MaxChain = 1; +void GNUELFDumper::printHashHistogramStats(size_t NBucket, + size_t MaxChain, + size_t TotalSyms, + ArrayRef Count, + bool IsGnu) const { size_t CumulativeNonZero = 0; - - size_t NBucket = GnuHashTable.nbuckets; - if (Chains.empty() || NBucket == 0) - return; - - ArrayRef Buckets = GnuHashTable.buckets(); - 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" + OS << "Histogram for" << (IsGnu ? " `.gnu.hash'" : "") + << " bucket list length (total of " << NBucket << " buckets)\n" << " Length Number % of total Coverage\n"; - for (size_t I = 0; I < MaxChain; I++) { + 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, @@ -4940,28 +4973,6 @@ } } -// Hash histogram shows statistics of how efficient the hash was for the -// dynamic symbol table. The table shows the number of hash buckets for -// different lengths of chains as an absolute number and percentage of the total -// buckets, and the cumulative coverage of symbols for each set of buckets. -template void GNUELFDumper::printHashHistograms() { - // Print histogram for the .hash section. - if (this->HashTable) { - if (Error E = checkHashTable(*this, this->HashTable)) - this->reportUniqueWarning(std::move(E)); - else - printHashHistogram(*this->HashTable); - } - - // Print histogram for the .gnu.hash section. - if (this->GnuHashTable) { - if (Error E = checkGNUHashTable(this->Obj, this->GnuHashTable)) - this->reportUniqueWarning(std::move(E)); - else - printGnuHashHistogram(*this->GnuHashTable); - } -} - template void GNUELFDumper::printCGProfile() { OS << "GNUStyle::printCGProfile not implemented\n"; } @@ -7151,8 +7162,27 @@ } } -template void LLVMELFDumper::printHashHistograms() { - W.startLine() << "Hash Histogram not implemented!\n"; +template +void LLVMELFDumper::printHashHistogramStats(size_t NBucket, + size_t MaxChain, + size_t TotalSyms, + ArrayRef Count, + bool IsGnu) const { + StringRef HistName = IsGnu ? "GnuHashHistogram" : "HashHistogram"; + StringRef BucketName = IsGnu ? "Bucket" : "Chain"; + StringRef ListName = IsGnu ? "Buckets" : "Chains"; + DictScope Outer(W, HistName); + W.printNumber("TotalBuckets", NBucket); + ListScope Buckets(W, ListName); + size_t CumulativeNonZero = 0; + for (size_t I = 0; I < MaxChain; ++I) { + CumulativeNonZero += Count[I] * I; + DictScope Bucket(W, BucketName); + W.printNumber("Length", I); + W.printNumber("Count", Count[I]); + W.printNumber("Percentage", (float)(Count[I] * 100.0) / NBucket); + W.printNumber("Coverage", (float)(CumulativeNonZero * 100.0) / TotalSyms); + } } // Returns true if rel/rela section exists, and populates SymbolIndices.