[llvm-readobj] - Fix possible crashes related to dumping gnu hash symbols.

[grimar]

Summary

It fixes possible scenarios when we crash/assert with --hash-symbols when
dumping an invalid GNU hash table which has a broken value in the buckets array.

This fixes a crash reported in comments for
https://bugs.llvm.org/show_bug.cgi?id=47681

[jhenderson]

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

662

It's not clear from this comment what is causing the attempt to read past the end of file. Please could you clarify.

672–673

679–680

Surely we should be diagnosing the attempt to read using an invalid dynamic symbol index in the first place, so that we don't see semi-random warnings?

691

Ditto.

llvm/tools/llvm-readobj/ELFDumper.cpp

4098

Perhaps this - "length" implies the number of entries in the array, whereas "size" could mean either that or the total size taken up by the array (e.g. 4 times the length, if the elements are 4 bytes in size each).

[grimar]

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

679–680

I am not sure honestly. Currently our logic is that we can't get here when there is no SHT_DYNSYM section,
because we take the size of the dynamic symbol table from there and there is no other way to get it.
I.e. there is no dynamic tag for that, so in case when we e.g. don't have a .hash table to infer the size,
we will never be able to dump symbols currently and we return earlier:

void GNUStyle<ELFT>::printGnuHashTableSymbols(const Elf_GnuHash &GnuHash) {
  StringRef StringTable = this->dumper().getDynamicStringTable();
  if (StringTable.empty())
    return;

  Elf_Sym_Range DynSyms = this->dumper().dynamic_symbols();
  const Elf_Sym *FirstSym = DynSyms.empty() ? nullptr : &DynSyms[0];
  if (!FirstSym) {
    Optional<DynRegionInfo> DynSymRegion = this->dumper().getDynSymRegion();
    this->reportUniqueWarning(createError(
        Twine("unable to print symbols for the .gnu.hash table: the "
              "dynamic symbol table ") +
        (DynSymRegion ? "is empty" : "was not found")));
    return;
  }
....

At the same time I think loaders have no any checks (i.e. they don't try to use the size from SHT_DYNSYM) and will try to use a dynamic symbol found via DT_SYMTAB only. In this case it might probably be useful to try to dump symbols here,
even if they are invalid to reveal what loaders see on their side? Perhaps worth showing an additional warning, saying that we think/found that an index is invalid though. And we can also probably change the code shown above to allow us to pass when DynSymRegion.Addr != 0 (i.e. when we found a DT_SYMTAB, but no SHT_DYNSYM and the address is within the file).

If not, we can probably just skip symbols with invalid indices, just like you've suggested.

What do you think?

[uweigand]

I think the handling of the GNU hash table is actually already fully correct. The crash (or error message when using this patch) is simply a side effect of the fact that size of the DynSymRegion was clobbered here (near the end of ELFDumper<ELFT>::parseDynamicTable()):

DynSymRegion->Size = HashTable->nchain * DynSymRegion->EntSize;

This in turn is because HashTable->nchain (like all of HashTable) is just incorrect on s390x at the moment, as discussed in https://bugs.llvm.org/show_bug.cgi?id=47681

[jhenderson]

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

679–680

Ah, I forgot that the dynsym has no size in the dynamic table (that's still dumb, but oh well). I think if we have information implying the index looks broken, due to other information (e.g. the section header), we should at least warn that this is probably not correct. I think the warning would be more than enough to say something is a bit bogus. I also think that means we don't need to try to dump invalid index symbols if we know they are bogus (why would a user care what the loader sees if they know that whatever it is is bad - in such situations they'd need to fix the source of the bad index).

I'm a little struggling to follow the full details of your comment though. so I may be misunderstanding your points/questions.

[uweigand]

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

679–680

As I said in my comment yesterday, in this particular executable we do have the correct size of dynsym from the section table -- it's just that this (correct) size is later replaced by (incorrect) information derived from the .hash section.

[grimar]

In D88561#2304127, @uweigand wrote:

I think the handling of the GNU hash table is actually already fully correct. The crash (or error message when using this patch) is simply a side effect of the fact that size of the DynSymRegion was clobbered here (near the end of ELFDumper<ELFT>::parseDynamicTable()):

DynSymRegion->Size = HashTable->nchain * DynSymRegion->EntSize;

This in turn is because HashTable->nchain (like all of HashTable) is just incorrect on s390x at the moment, as discussed in https://bugs.llvm.org/show_bug.cgi?id=47681

That is true for you executable. But this patch fixes a bit different case. Here I am creating the .gnu.hash table with a broken value in the buckets array.
Currently with the test case provided we crash an all platforms at the same place where your executable crashes too.
So with this patch we fix the crash, but not the reason of PR47681, which is s390x specific.

[grimar]

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

679–680

I'm a little struggling to follow the full details of your comment though. so I may be misunderstanding your points/questions.

Nope. You got me right. I'll update the patch to report a warning and will stop printing a bogus symbol.

[uweigand]

In D88561#2305598, @grimar wrote:

In D88561#2304127, @uweigand wrote:

I think the handling of the GNU hash table is actually already fully correct. The crash (or error message when using this patch) is simply a side effect of the fact that size of the DynSymRegion was clobbered here (near the end of ELFDumper<ELFT>::parseDynamicTable()):

DynSymRegion->Size = HashTable->nchain * DynSymRegion->EntSize;

This in turn is because HashTable->nchain (like all of HashTable) is just incorrect on s390x at the moment, as discussed in https://bugs.llvm.org/show_bug.cgi?id=47681

That is true for you executable. But this patch fixes a bit different case. Here I am creating the .gnu.hash table with a broken value in the buckets array.
Currently with the test case provided we crash an all platforms at the same place where your executable crashes too.
So with this patch we fix the crash, but not the reason of PR47681, which is s390x specific.

I see. In this case this patch doesn't really address PR47681, but only replaces a crash with wrong output ... Still preferable to not crash, but of course we still need to fix the root cause (at the least, by ignoring the .hash section if the entry size doesn't match).

[grimar]

In D88561#2305660, @uweigand wrote:

I see. In this case this patch doesn't really address PR47681, but only replaces a crash with wrong output ... Still preferable to not crash, but of course we still need to fix the root cause (at the least, by ignoring the .hash section if the entry size doesn't match).

The fix for PR47681 (s390 specific) is independent from the crash (all platforms), so it should be fixed separatelly.
I am going to prepare a follow-up to fix the PR47681 after landing this.

[uweigand]

In D88561#2305667, @grimar wrote:

In D88561#2305660, @uweigand wrote:

I see. In this case this patch doesn't really address PR47681, but only replaces a crash with wrong output ... Still preferable to not crash, but of course we still need to fix the root cause (at the least, by ignoring the .hash section if the entry size doesn't match).

The fix for PR47681 (s390 specific) is independent from the crash (all platforms), so it should be fixed separatelly.
I'll am going to prepare a follow-up to fix the PR47681 after landing this.

Thanks!

[grimar]

• Update implementation (validate the symbol index and related changes and simplifications).

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

662

I've updated implementation and had to rework all test cases. Now there are no cases when we try read past the EOF - or at least I can't imagine an input for that atm.

llvm/tools/llvm-readobj/ELFDumper.cpp

4098

This place is gone.

[jhenderson]

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

723

724

llvm/tools/llvm-readobj/ELFDumper.cpp

2745–2746

4061

4073–4074

I'm not sure I understand what 'Values' here is referring to. Is it the hash values, or something else? Either way, there needs to be more context here.

[grimar]

• Addressed review comments.

[jhenderson]

Looks good aside from a possible broken test.

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

128

This test looks like it might need updating?

[grimar]

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

128

This message comes from a different place,
for LLVM style we show it when fail to dump Values:

void ELFDumper<ELFT>::printGnuHashTable() {
.....

  Expected<ArrayRef<Elf_Word>> Chains =
      getGnuHashTableChains<ELFT>(DynSymRegion, GnuHashTable);
  if (!Chains) {
    reportUniqueWarning(
        createError("unable to dump 'Values' for the SHT_GNU_HASH "
                    "section: " +
                    toString(Chains.takeError())));
    return;
  }

  W.printHexList("Values", *Chains);

I.e. it is unrelated to this patch, I think I just copypasted this error previously.
And for this particular place it seems that mentioning 'Values' in the message is reasonable.

[jhenderson]

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

128

Okay (but I don't think 'Values' makes sense - values of what?)

[grimar]

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

128

An example of normal output is:

GnuHashTable {
  Num Buckets: 3
  First Hashed Symbol Index: 1
  Num Mask Words: 2
  Shift Count: 2
  Bloom Filter: [0x3, 0x4]
  Buckets: [5, 6, 7]
  Values: [0x8, 0x9, 0xA, 0xB]
}

I.e. Values refers to the field that was expected to be dumped, but was not because of an error.

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]]': 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: warning: '[[FILE]]': unable to dump 'Values' for the SHT_GNU_HASH section: the first hashed symbol index (2) is greater than or equal to the number of dynamic symbols (2)
 # SYMNDX-NEXT: }
 
 --- !ELF
 FileHeader:
   Class: ELFCLASS64
   Data:  ELFDATA2LSB
   Type:  ET_DYN
 Sections:

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

 ## 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)
+# ERR6: warning: '[[FILE]]': unable to print the GNU hash table histogram: the first hashed symbol index (16) is greater than or equal to 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

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

- Name:  .dynsym
     Size:  0
 ProgramHeaders:
   - Type:  PT_LOAD
     Flags: [ PF_R, PF_X ]
     Sections:
       - Section: .gnu.hash
       - Section: .dynamic
       - Section: .dynstr
+
+## In this case we have a broken value in the hash buckets array. Normally it contains an
+## index into the dynamic symbol table and also is used to get a hash value from the hash values array.
+## llvm-readelf attempts to read a symbol that is past the end of the dynamic symbol table.
+
+# RUN: yaml2obj --docnum=11 -DVALUE=0x2 %s -o %t11.past.dynsym.so
+# RUN: llvm-readelf --hash-symbols %t11.past.dynsym.so 2>&1 | \
+# RUN:   FileCheck %s -DFILE=%t11.past.dynsym.so --check-prefix=BUCKET-PAST-DYNSYM
+
+# BUCKET-PAST-DYNSYM:      Symbol table of .gnu.hash for image:
+# BUCKET-PAST-DYNSYM-NEXT:   Num Buc:    Value          Size   Type   Bind Vis      Ndx Name
+# BUCKET-PAST-DYNSYM-NEXT: warning: '[[FILE]]': unable to print hashed symbol with index 2, which is greater than or equal to the number of dynamic symbols (2)
+# BUCKET-PAST-DYNSYM-NEXT:     1   2: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT UND foo
+# BUCKET-PAST-DYNSYM-NOT:  {{.}}
+
+--- !ELF
+FileHeader:
+  Class: ELFCLASS64
+  Data:  ELFDATA2LSB
+  Type:  ET_DYN
+Sections:
+  - Name:  .gnu.hash
+    Type:  SHT_GNU_HASH
+    Flags: [ SHF_ALLOC ]
+    Link:  .dynsym
+    Header:
+      SymNdx: [[SYMNDX=0x0]]
+      Shift2: 0x0
+    BloomFilter: [ 0x0 ]
+    HashBuckets: [ 0x0, [[VALUE]], 0x1 ]
+    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:
+  - Name:    foo
+    Binding: STB_GLOBAL
+ProgramHeaders:
+  - Type:  PT_LOAD
+    Flags: [ PF_R, PF_X ]
+    Sections:
+      - Section: .gnu.hash
+      - Section: .dynamic
+
+## In this case we are unable to read a hash value for a symbol with
+## an index that is less than the index of the first hashed symbol.
+
+# RUN: yaml2obj --docnum=11 -DSYMNDX=0x2 -DVALUE=0x1 %s -o %t11.first.hashed.so
+# RUN: llvm-readelf --hash-symbols %t11.first.hashed.so 2>&1 | \
+# RUN:   FileCheck %s -DFILE=%t11.first.hashed.so --check-prefix=FIRST-HASHED
+
+# FIRST-HASHED:      Symbol table of .gnu.hash for image:
+# FIRST-HASHED-NEXT:   Num Buc:    Value          Size   Type   Bind Vis      Ndx Name
+# FIRST-HASHED-NEXT: warning: '[[FILE]]': unable to get hash values for the SHT_GNU_HASH section: the first hashed symbol index (2) is greater than or equal to the number of dynamic symbols (2)
+# FIRST-HASHED-NEXT:     1   1: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT UND foo
+# FIRST-HASHED-NEXT: warning: '[[FILE]]': unable to read the hash value for symbol with index 1, which is less than the index of the first hashed symbol (2)
+# FIRST-HASHED-NEXT:     1   2: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT UND foo
+# FIRST-HASHED-NOT:  {{.}}
+
+## In this case one of the chain values doesn't end with a stopper bit and llvm-readelf attempts to read
+## a dynamic symbol with an index that is equal to the number of dynamic symbols.
+
+# RUN: yaml2obj --docnum=11 -DSYMNDX=0x1 -DVALUE=0x1 %s -o %t11.chain.bit.so
+# RUN: llvm-readelf --hash-symbols %t11.chain.bit.so 2>&1 | \
+# RUN:   FileCheck %s -DFILE=%t11.chain.bit.so --check-prefix=CHAIN-BIT
+
+# CHAIN-BIT:      Symbol table of .gnu.hash for image:
+# CHAIN-BIT-NEXT:   Num Buc:    Value          Size   Type   Bind Vis      Ndx Name
+# CHAIN-BIT-NEXT:     1   1: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT UND foo
+# CHAIN-BIT-NEXT: warning: '[[FILE]]': unable to print hashed symbol with index 2, which is greater than or equal to the number of dynamic symbols (2)
+# CHAIN-BIT-NEXT:     1   2: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT UND foo
+# CHAIN-BIT-NOT:  {{.}}

llvm/tools/llvm-readobj/ELFDumper.cpp

getGnuHashTableChains(Optional<DynRegionInfo> DynSymRegion,
   // 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
   // important for dynamic loaders when the GNU hash table is empty. They just
   // skip the whole object during symbol lookup. In such cases, the symndx value
   // is irrelevant and we should not report a warning.
   ArrayRef<typename ELFT::Word> Buckets = GnuHashTable->buckets();
   if (!llvm::all_of(Buckets, [](typename ELFT::Word V) { return V == 0; }))
-    return createError("the first hashed symbol index (" +
-                       Twine(GnuHashTable->symndx) +
-                       ") is larger than the number of dynamic symbols (" +
-                       Twine(NumSyms) + ")");
+    return createError(
+        "the first hashed symbol index (" + Twine(GnuHashTable->symndx) +
+        ") is greater than or equal to the number of dynamic symbols (" +
   // There is no way to represent an array of (dynamic symbols count - symndx)
   // length.
   return ArrayRef<typename ELFT::Word>();
 }
 
 template <typename ELFT>
 void ELFDumper<ELFT>::printGnuHashTable() {
   DictScope D(W, "GnuHashTable");

 template <class ELFT>
 void GNUStyle<ELFT>::printGnuHashTableSymbols(const Elf_GnuHash &GnuHash) {
   StringRef StringTable = this->dumper().getDynamicStringTable();
   if (StringTable.empty())
     return;
 
   Elf_Sym_Range DynSyms = this->dumper().dynamic_symbols();
   const Elf_Sym *FirstSym = DynSyms.empty() ? nullptr : &DynSyms[0];
-  if (!FirstSym) {
-    Optional<DynRegionInfo> DynSymRegion = this->dumper().getDynSymRegion();
+  if (!FirstSym) {
     this->reportUniqueWarning(createError(
         Twine("unable to print symbols for the .gnu.hash table: the "
               "dynamic symbol table ") +
         (DynSymRegion ? "is empty" : "was not found")));
     return;
   }
 
+  auto GetSymbol = [&](uint64_t SymIndex,
+                       uint64_t SymsTotal) -> const Elf_Sym * {
+    if (SymIndex >= SymsTotal) {
+      this->reportUniqueWarning(createError(
+          "unable to print hashed symbol with index " + Twine(SymIndex) +
+          ", which is greater than or equal to the number of dynamic symbols "
+          "(" +
+          Twine::utohexstr(SymsTotal) + ")"));
+      return nullptr;
+    }
+    return FirstSym + SymIndex;
+  };
+
+  Expected<ArrayRef<Elf_Word>> ValuesOrErr =
+      getGnuHashTableChains<ELFT>(DynSymRegion, &GnuHash);
+  ArrayRef<Elf_Word> Values;
+  if (!ValuesOrErr)
+    this->reportUniqueWarning(
+        createError("unable to get hash values for the SHT_GNU_HASH "
+                    "section: " +
+                    toString(ValuesOrErr.takeError())));
+  else
+    Values = *ValuesOrErr;
+
   ArrayRef<Elf_Word> Buckets = GnuHash.buckets();
   for (uint32_t Buc = 0; Buc < GnuHash.nbuckets; Buc++) {
     if (Buckets[Buc] == ELF::STN_UNDEF)
       continue;
     uint32_t Index = Buckets[Buc];
-    uint32_t GnuHashable = Index - GnuHash.symndx;
-    // Print whole chain
+    // Print whole chain.
     while (true) {
       uint32_t SymIndex = Index++;
-      printHashedSymbol(FirstSym + SymIndex, SymIndex, StringTable, Buc);
-      // Chain ends at symbol with stopper bit
-      if ((GnuHash.values(DynSyms.size())[GnuHashable++] & 1) == 1)
+      if (const Elf_Sym *Sym = GetSymbol(SymIndex, DynSyms.size()))
+        printHashedSymbol(Sym, SymIndex, StringTable, Buc);
+      else
+        break;
+
+      if (SymIndex < GnuHash.symndx) {
+        this->reportUniqueWarning(createError(
+            "unable to read the hash value for symbol with index " +
+            Twine(SymIndex) +
+            ", which is less than the index of the first hashed symbol (" +
+            Twine(GnuHash.symndx) + ")"));
+        break;
+      }
+
+       // Chain ends at symbol with stopper bit.
+      if ((Values[SymIndex - GnuHash.symndx] & 1) == 1)
         break;
     }
   }
 }
 
 template <class ELFT> void GNUStyle<ELFT>::printHashSymbols() {
   if (const Elf_Hash *SysVHash = this->dumper().getHashTable()) {
     OS << "\n Symbol table of .hash for image:\n";