[llvm-readobj] - Add a validation of the GNU hash table to printGnuHashHistogram().

[grimar]

Summary

Similar to D81937, we might crash when printing a histogram for a GNU hash table
with a 'symndx' index that is larger than the number of dynamic symbols.

This patch adopts and reuses the getGnuHashTableChains() helper which performs
a validation of the table. As a side effect the warning reported for
the --gnu-hash-table was improved.

Also with this change we start to report a warning when the histogram is requested for
the GNU hash table, but the dynamic symbols table is empty (size == 0).

[jhenderson]

If I'm following things right, the behaviour for an empty dynsym is changing with this patch. Is the new behaviour compatible with GNU?

llvm/test/tools/llvm-readobj/ELF/gnuhash.test

130

Hmm... This message is clearly not quite right even before your change: 2 is obviously not larger than 2...

Anyway, that's a separate issue.

llvm/test/tools/llvm-readobj/ELF/hash-histogram.test

335

Perhaps this should be non-zero rather than non-null? Similar null -> zero below.

342

No need for the comma here or in Case C.

386

It might also locate it by name, but I hope it wouldn't :-)

Perhaps this should say "The code locates the..."

[grimar]

In D82010#2100106, @jhenderson wrote:

If I'm following things right, the behaviour for an empty dynsym is changing with this patch. Is the new behaviour compatible with GNU?

Right. It it what I mentioned in the description:
"Also with this change we start to report a warning when the histogram is requested for
the GNU hash table, but the dynamic symbols table is empty (size == 0)."

GNU readelf doesn't warn about that. But isn't it a bug? When we have a zero sized dynamic table it is already incorrect, because it should have a zero symbol at least.
And it is wierd to have a hash table in this case too.

llvm/test/tools/llvm-readobj/ELF/hash-histogram.test

386

There is also an option currently where it uses the DT_SYMTAB tag.
In this test cases we have no such tag, so I think your suggestion is ok, I'll apply it.

[grimar]

• Addressed review comments.

[grimar]

llvm/test/tools/llvm-readobj/ELF/gnuhash.test

130

I'll fix, thanks for spotting.

[jhenderson]

In D82010#2100253, @grimar wrote:

In D82010#2100106, @jhenderson wrote:

If I'm following things right, the behaviour for an empty dynsym is changing with this patch. Is the new behaviour compatible with GNU?

Right. It it what I mentioned in the description:
"Also with this change we start to report a warning when the histogram is requested for
the GNU hash table, but the dynamic symbols table is empty (size == 0)."

GNU readelf doesn't warn about that. But isn't it a bug? When we have a zero sized dynamic table it is already incorrect, because it should have a zero symbol at least.
And it is wierd to have a hash table in this case too.

You're probably right that it's a bug. I think I'm okay with this. LGTM.

llvm/test/tools/llvm-readobj/ELF/gnuhash.test

 
 # SYMNDX:      GnuHashTable {
 # SYMNDX-NEXT:   Num Buckets: 1
 # SYMNDX-NEXT:   First Hashed Symbol Index: 2
 # SYMNDX-NEXT:   Num Mask Words: 1
 # SYMNDX-NEXT:   Shift Count: 0
 # SYMNDX-NEXT:   Bloom Filter: [0x1]
 # SYMNDX-NEXT:   Buckets: [2]
-# SYMNDX-NEXT: warning: '[[FILE]]': the first hashed symbol index (2) is larger than the number of dynamic symbols (2)
+# SYMNDX-NEXT: warning: '[[FILE]]': unable to dump 'Values' for the SHT_GNU_HASH section: the first hashed symbol index (2) is larger than the number of dynamic symbols (2)
 # SYMNDX-NEXT: }
 
 --- !ELF
 FileHeader:
   Class:   ELFCLASS64
   Data:    ELFDATA2LSB
   Type:    ET_DYN
   Machine: EM_X86_64

llvm/test/tools/llvm-readobj/ELF/hash-histogram.test

Entries:
       - Tag:   DT_NULL
         Value: 0x0
 DynamicSymbols: []
 ProgramHeaders:
   - Type: PT_LOAD
     Sections:
       - Section: .gnu.hash
       - Section: .dynamic
+
+## Linkers might produce an empty no-op SHT_GNU_HASH section when
+## there are no dynamic symbols or when all dynamic symbols are undefined.
+## Such sections normally have a single zero entry in the bloom
+## filter, a single zero entry in the hash bucket and no values.
+##
+## The index of the first symbol in the dynamic symbol table
+## included in the hash table can be set to the number of dynamic symbols,
+## which is one larger than the index of the last dynamic symbol.
+## For empty tables however, this value is unimportant and can be ignored.
+
+## Check the case when a 'symndx' index of the first symbol in the dynamic symbol
+## table is larger than the number of dynamic symbols.
+
+## Case A: when the buckets array is not empty and has a non-zero value we report a warning.
+# RUN: yaml2obj --docnum=7 -DVAL=0x1 %s -o %t9
+# RUN: llvm-readelf --elf-hash-histogram %t9 2>&1 | \
+# RUN:   FileCheck %s -DFILE=%t9 --check-prefix=ERR6
+
+# ERR6: warning: '[[FILE]]': unable to print the GNU hash table histogram: the first hashed symbol index (16) is larger than the number of dynamic symbols (1)
+
+## Case B: we do not report a warning when the buckets array contains only zero values.
+# RUN: yaml2obj --docnum=7 -DVAL=0x0 %s -o %t10
+# RUN: llvm-readelf --elf-hash-histogram %t10 2>&1 | \
+# RUN:   FileCheck %s --allow-empty --implicit-check-not="Histogram"
+
+## Case C: we do not report a warning when the buckets array is empty.
+# RUN: yaml2obj --docnum=7 -DVAL="" %s -o %t11
+# RUN: llvm-readelf --elf-hash-histogram %t11 2>&1 | \
+# RUN:   FileCheck %s --allow-empty --implicit-check-not="Histogram"
+
+--- !ELF
+FileHeader:
+  Class:   ELFCLASS64
+  Data:    ELFDATA2LSB
+  Type:    ET_DYN
+  Machine: EM_X86_64
+Sections:
+  - Name:  .gnu.hash
+    Type:  SHT_GNU_HASH
+    Flags: [ SHF_ALLOC ]
+    Header:
+      SymNdx: 0x10
+      Shift2: 0x0
+    BloomFilter: [ 0x0 ]
+    HashBuckets: [ [[VAL]] ]
+    HashValues:  [ 0x0 ]
+  - Name:  .dynamic
+    Type:  SHT_DYNAMIC
+    Flags: [ SHF_ALLOC ]
+    Link:  .dynstr
+    Entries:
+      - Tag:   DT_GNU_HASH
+        Value: 0x0
+      - Tag:   DT_NULL
+        Value: 0x0
+DynamicSymbols: []
+ProgramHeaders:
+  - Type: PT_LOAD
+    Sections:
+      - Section: .gnu.hash
+      - Section: .dynamic
+
+## Check we report warnings when the dynamic symbol table is absent or empty.
+
+## The code locates the dynamic symbol table by the section type. Use SHT_PROGBITS to hide it.
+# RUN: yaml2obj --docnum=8 -DTYPE=SHT_PROGBITS %s -o %t12
+# RUN: llvm-readelf --elf-hash-histogram %t12 2>&1 | \
+# RUN:   FileCheck %s -DFILE=%t12 --check-prefix=ERR7
+
+# ERR7: warning: '[[FILE]]': unable to print the GNU hash table histogram: no dynamic symbol table found
+
+# RUN: yaml2obj --docnum=8 -DTYPE=SHT_DYNSYM %s -o %t13
+# RUN: llvm-readelf --elf-hash-histogram %t13 2>&1 | \
+# RUN:   FileCheck %s -DFILE=%t13 --check-prefix=ERR8
+
+# ERR8: warning: '[[FILE]]': unable to print the GNU hash table histogram: the dynamic symbol table is empty
+
+--- !ELF
+FileHeader:
+  Class:   ELFCLASS64
+  Data:    ELFDATA2LSB
+  Type:    ET_DYN
+  Machine: EM_X86_64
+Sections:
+  - Name:  .gnu.hash
+    Type:  SHT_GNU_HASH
+    Flags: [ SHF_ALLOC ]
+    Header:
+      SymNdx: 0x0
+      Shift2: 0x0
+    BloomFilter: [ 0x0 ]
+    HashBuckets: [ 0x0 ]
+    HashValues:  [ 0x0 ]
+  - Name:  .dynamic
+    Type:  SHT_DYNAMIC
+    Flags: [ SHF_ALLOC ]
+    Entries:
+      - Tag:   DT_GNU_HASH
+        Value: 0x0
+      - Tag:   DT_NULL
+        Value: 0x0
+  - Name: .dynsym
+    Type: [[TYPE]]
+    Size: 0
+ProgramHeaders:
+  - Type: PT_LOAD
+    Sections:
+      - Section: .gnu.hash

llvm/tools/llvm-readobj/ELFDumper.cpp

Elf_Dyn_Range dynamic_table() const {
     size_t Size = 0;
     while (Size < Table.size())
       if (Table[Size++].getTag() == DT_NULL)
         break;
 
     return Table.slice(0, Size);
   }
 
+  Optional<DynRegionInfo> getDynSymRegion() const { return DynSymRegion; }
+
   Elf_Sym_Range dynamic_symbols() const {
     if (!DynSymRegion)
       return Elf_Sym_Range();
     return DynSymRegion->getAsArrayRef<Elf_Sym>();
   }
 
   Elf_Rel_Range dyn_rels() const;
   Elf_Rela_Range dyn_relas() const;
template <typename ELFT> void ELFDumper<ELFT>::printHashTable() {
   }
 
   W.printList("Buckets", HashTable->buckets());
   W.printList("Chains", HashTable->chains());
 }
 
 template <class ELFT>
 static Expected<ArrayRef<typename ELFT::Word>>
-getGnuHashTableChains(const typename ELFT::SymRange DynSymTable,
+getGnuHashTableChains(Optional<DynRegionInfo> DynSymRegion,
                       const typename ELFT::GnuHash *GnuHashTable) {
+  if (!DynSymRegion)
+    return createError("no dynamic symbol table found");
+
+  ArrayRef<typename ELFT::Sym> DynSymTable =
+      DynSymRegion->getAsArrayRef<typename ELFT::Sym>();
   size_t NumSyms = DynSymTable.size();
   if (!NumSyms)
-    return createError("unable to dump 'Values' for the SHT_GNU_HASH "
-                       "section: the dynamic symbol table is empty");
+    return createError("the dynamic symbol table is empty");
 
   if (GnuHashTable->symndx < NumSyms)
     return GnuHashTable->values(NumSyms);
 
   // A normal empty GNU hash table section produced by linker might have
   // symndx set to the number of dynamic symbols + 1 (for the zero symbol)
   // and have dummy null values in the Bloom filter and in the buckets
   // vector (or no values at all). It happens because the value of symndx is not
void ELFDumper<ELFT>::printGnuHashTable(const object::ObjectFile *Obj) {
   }
 
   ArrayRef<typename ELFT::Off> BloomFilter = GnuHashTable->filter();
   W.printHexList("Bloom Filter", BloomFilter);
 
   ArrayRef<Elf_Word> Buckets = GnuHashTable->buckets();
   W.printList("Buckets", Buckets);
 
-  if (!DynSymRegion) {
-    reportWarning(createError("unable to dump 'Values' for the SHT_GNU_HASH "
-                              "section: no dynamic symbol table found"),
-                  ObjF->getFileName());
-    return;
-  }
-
   Expected<ArrayRef<Elf_Word>> Chains =
-      getGnuHashTableChains<ELFT>(dynamic_symbols(), GnuHashTable);
+      getGnuHashTableChains<ELFT>(DynSymRegion, GnuHashTable);
   if (!Chains) {
-    reportUniqueWarning(Chains.takeError());
+    reportUniqueWarning(
+        createError("unable to dump 'Values' for the SHT_GNU_HASH "
+                    "section: " +
+                    toString(Chains.takeError())));
     return;
   }
 
   W.printHexList("Values", *Chains);
 }
 
 template <typename ELFT> void ELFDumper<ELFT>::printLoadName() {
   W.printString("LoadName", SOName);
for (size_t I = 0; I < MaxChain; 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 GNUStyle<ELFT>::printGnuHashHistogram(const Elf_GnuHash &GnuHashTable) {
-  size_t NBucket = GnuHashTable.nbuckets;
-  ArrayRef<Elf_Word> Buckets = GnuHashTable.buckets();
-  unsigned NumSyms = this->dumper()->dynamic_symbols().size();
-  if (!NumSyms)
+  Expected<ArrayRef<Elf_Word>> ChainsOrErr = getGnuHashTableChains<ELFT>(
+      this->dumper()->getDynSymRegion(), &GnuHashTable);
+  if (!ChainsOrErr) {
+    this->reportUniqueWarning(
+        createError("unable to print the GNU hash table histogram: " +
+                    toString(ChainsOrErr.takeError())));
     return;
-  ArrayRef<Elf_Word> Chains = GnuHashTable.values(NumSyms);
+  }
+
+  ArrayRef<Elf_Word> Chains = *ChainsOrErr;
   size_t Symndx = GnuHashTable.symndx;
   size_t TotalSyms = 0;
   size_t MaxChain = 1;
   size_t CumulativeNonZero = 0;
 
+  size_t NBucket = GnuHashTable.nbuckets;
   if (Chains.empty() || NBucket == 0)
     return;
 
+  ArrayRef<Elf_Word> Buckets = GnuHashTable.buckets();
   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)