Print ELF hash histogram

[khemant]

Summary

The patch print histogram data of hash buckets in ELF file. It works on SHT_HASH or SHT_GNU_HASH type sections.

The output shows how many buckets are for each chain length and how many symbols they cover cumulatively.

[echristo]

In general looks ok. Reminding khemant to go ahead and do post-commit review of his readobj changes :)

-eric

[khemant]

Thanks for the reminder :)

llvm/trunk/test/tools/llvm-readobj/elf-hash-histogram.test

+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%

llvm/trunk/tools/llvm-readobj/ELFDumper.cpp

#define TYPEDEF_ELF_TYPES(ELFT)                                                \
   typedef typename ELFO::Elf_Dyn_Range Elf_Dyn_Range;                          \
   typedef typename ELFO::Elf_Rel Elf_Rel;                                      \
   typedef typename ELFO::Elf_Rela Elf_Rela;                                    \
   typedef typename ELFO::Elf_Rela_Range Elf_Rela_Range;                        \
   typedef typename ELFO::Elf_Phdr Elf_Phdr;                                    \
   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 {
 
 template <class ELFT> class DumpStyle;
 
 /// Represents a contiguous uniform range in the file. We cannot just create a
 /// range directly because when creating one of these from the .dynamic table
public:
 
   void printAttributes() override;
   void printMipsPLTGOT() override;
   void printMipsABIFlags() override;
   void printMipsReginfo() override;
 
   void printStackMap() const override;
 
+  void printHashHistogram() override;
+
 private:
   std::unique_ptr<DumpStyle<ELFT>> ELFDumperStyle;
   typedef ELFFile<ELFT> ELFO;
   typedef typename ELFO::Elf_Shdr Elf_Shdr;
   typedef typename ELFO::Elf_Sym Elf_Sym;
   typedef typename ELFO::Elf_Sym_Range Elf_Sym_Range;
   typedef typename ELFO::Elf_Dyn Elf_Dyn;
   typedef typename ELFO::Elf_Dyn_Range Elf_Dyn_Range;
public:
 
   void printSymbolsHelper(bool IsDynamic) const;
   const Elf_Shdr *getDotSymtabSec() const { return DotSymtabSec; }
   ArrayRef<Elf_Word> getShndxTable() const { return ShndxTable; }
   StringRef getDynamicStringTable() const { return DynamicStringTable; }
   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 <class ELFT>
 void ELFDumper<ELFT>::printSymbolsHelper(bool IsDynamic) const {
   StringRef StrTable, SymtabName;
   size_t Entries = 0;
   Elf_Sym_Range Syms(nullptr, nullptr);
   if (IsDynamic) {
public:
   virtual void printSymtabMessage(const ELFFile<ELFT> *obj, StringRef Name,
                                   size_t Offset) {
     return;
   }
   virtual void printSymbol(const ELFFile<ELFT> *Obj, const Elf_Sym *Symbol,
                            const Elf_Sym *FirstSym, StringRef StrTable,
                            bool IsDynamic) = 0;
   virtual void printProgramHeaders(const ELFFile<ELFT> *Obj) = 0;
+  virtual void printHashHistogram(const ELFFile<ELFT> *Obj) = 0;
   const ELFDumper<ELFT> *dumper() const { return Dumper; }
 private:
   const ELFDumper<ELFT> *Dumper;
 };
 
 template <typename ELFT> class GNUStyle : public DumpStyle<ELFT> {
   formatted_raw_ostream OS;
 public:
   TYPEDEF_ELF_TYPES(ELFT)
   GNUStyle(StreamWriter &W, ELFDumper<ELFT> *Dumper)
       : DumpStyle<ELFT>(Dumper), OS(W.getOStream()) {}
   void printFileHeaders(const ELFO *Obj) override;
   void printGroupSections(const ELFFile<ELFT> *Obj) override;
   void printRelocations(const ELFO *Obj) override;
   void printSections(const ELFO *Obj) override;
   void printSymbols(const ELFO *Obj) override;
   void printDynamicSymbols(const ELFO *Obj) override;
   void printDynamicRelocations(const ELFO *Obj) override;
   virtual void printSymtabMessage(const ELFO *Obj, StringRef Name,
                                   size_t Offset) override;
   void printProgramHeaders(const ELFO *Obj) override;
+  void printHashHistogram(const ELFFile<ELFT> *Obj) override;
 
 private:
   struct Field {
     StringRef Str;
     unsigned Column;
     Field(StringRef S, unsigned Col) : Str(S), Column(Col) {}
     Field(unsigned Col) : Str(""), Column(Col) {}
   };
public:
   void printGroupSections(const ELFFile<ELFT> *Obj) override;
   void printRelocations(const ELFO *Obj) override;
   void printRelocations(const Elf_Shdr *Sec, const ELFO *Obj);
   void printSections(const ELFO *Obj) override;
   void printSymbols(const ELFO *Obj) override;
   void printDynamicSymbols(const ELFO *Obj) override;
   void printDynamicRelocations(const ELFO *Obj) override;
   void printProgramHeaders(const ELFO *Obj) override;
+  void printHashHistogram(const ELFFile<ELFT> *Obj) override;
 
 private:
   void printRelocation(const ELFO *Obj, Elf_Rela Rel, const Elf_Shdr *SymTab);
   void printDynamicRelocation(const ELFO *Obj, Elf_Rela Rel);
   void printSymbol(const ELFO *Obj, const Elf_Sym *Symbol, const Elf_Sym *First,
                    StringRef StrTable, bool IsDynamic) override;
   StreamWriter &W;
 };
void ELFDumper<ELFT>::printSymbols() {
   ELFDumperStyle->printSymbols(Obj);
 }
 
 template<class ELFT>
 void ELFDumper<ELFT>::printDynamicSymbols() {
   ELFDumperStyle->printDynamicSymbols(Obj);
 }
 
+template <class ELFT> void ELFDumper<ELFT>::printHashHistogram() {
+  ELFDumperStyle->printHashHistogram(Obj);
+}
 #define LLVM_READOBJ_TYPE_CASE(name) \
   case DT_##name: return #name
 
 static const char *getTypeString(uint64_t Type) {
   switch (Type) {
   LLVM_READOBJ_TYPE_CASE(BIND_NOW);
   LLVM_READOBJ_TYPE_CASE(DEBUG);
   LLVM_READOBJ_TYPE_CASE(FINI);
for (const Elf_Rel &Rel : DynPLTRelRegion.getAsArrayRef<Elf_Rel>()) {
       Rela.r_offset = Rel.r_offset;
       Rela.r_info = Rel.r_info;
       Rela.r_addend = 0;
       printDynamicRelocation(Obj, Rela, false);
     }
   }
 }
 
+// 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 <class ELFT>
+void GNUStyle<ELFT>::printHashHistogram(const ELFFile<ELFT> *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<Elf_Word> Buckets = HashTable->buckets();
+    ArrayRef<Elf_Word> 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<size_t> 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<size_t> 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<Elf_Word> Buckets = GnuHashTable->buckets();
+    unsigned NumSyms = this->dumper()->dynamic_symbols().size();
+    if (!NumSyms)
+      return;
+    ArrayRef<Elf_Word> 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<size_t> 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<size_t> 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 <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 <class ELFT> void LLVMStyle<ELFT>::printFileHeaders(const ELFO *Obj) {
   const Elf_Ehdr *e = Obj->getHeader();
   {
     DictScope D(W, "ElfHeader");
     {
       DictScope D(W, "Ident");
       W.printBinary("Magic", makeArrayRef(e->e_ident).slice(ELF::EI_MAG0, 4));
       W.printEnum("Class", e->e_ident[ELF::EI_CLASS], makeArrayRef(ElfClass));
for (const Elf_Phdr &Phdr : Obj->program_headers()) {
     W.printHex("VirtualAddress", Phdr.p_vaddr);
     W.printHex("PhysicalAddress", Phdr.p_paddr);
     W.printNumber("FileSize", Phdr.p_filesz);
     W.printNumber("MemSize", Phdr.p_memsz);
     W.printFlags("Flags", Phdr.p_flags, makeArrayRef(ElfSegmentFlags));
     W.printNumber("Alignment", Phdr.p_align);
   }
 }
+template <class ELFT>
+void LLVMStyle<ELFT>::printHashHistogram(const ELFFile<ELFT> *Obj) {
+  W.startLine() << "Hash Histogram not implemented!\n";
+}

llvm/trunk/tools/llvm-readobj/ObjDumper.h

public:
   virtual void printDynamicTable() { }
   virtual void printNeededLibraries() { }
   virtual void printProgramHeaders() { }
   virtual void printHashTable() { }
   virtual void printGnuHashTable() { }
   virtual void printLoadName() {}
   virtual void printVersionInfo() {}
   virtual void printGroupSections() {}
+  virtual void printHashHistogram() {}
 
   // Only implemented for ARM ELF at this time.
   virtual void printAttributes() { }
 
   // Only implemented for MIPS ELF at this time.
   virtual void printMipsPLTGOT() { }
   virtual void printMipsABIFlags() { }
   virtual void printMipsReginfo() { }

llvm/trunk/tools/llvm-readobj/llvm-readobj.cpp

cl::opt<bool>
                   cl::desc("Display ELF version sections (if present)"));
   cl::alias VersionInfoShort("V", cl::desc("Alias for -version-info"),
                              cl::aliasopt(VersionInfo));
 
   cl::opt<bool> SectionGroups("elf-section-groups",
                               cl::desc("Display ELF section group contents"));
   cl::alias SectionGroupsShort("g", cl::desc("Alias for -elf-sections-groups"),
                                cl::aliasopt(SectionGroups));
+  cl::opt<bool> 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<OutputStyleTy>
       Output("elf-output-style", cl::desc("Specify ELF dump style"),
              cl::values(clEnumVal(LLVM, "LLVM default style"),
                         clEnumVal(GNU, "GNU readelf style"), clEnumValEnd),
              cl::init(LLVM));
 } // namespace opts
 
if (isMipsArch(Obj->getArch())) {
         Dumper->printMipsPLTGOT();
       if (opts::MipsABIFlags)
         Dumper->printMipsABIFlags();
       if (opts::MipsReginfo)
         Dumper->printMipsReginfo();
     }
     if (opts::SectionGroups)
       Dumper->printGroupSections();
+    if (opts::HashHistogram)
+      Dumper->printHashHistogram();
   }
   if (Obj->isCOFF()) {
     if (opts::COFFImports)
       Dumper->printCOFFImports();
     if (opts::COFFExports)
       Dumper->printCOFFExports();
     if (opts::COFFDirectives)
       Dumper->printCOFFDirectives();