[llvm-readelf] - Do not enter an infinite loop when printing histogram.

[grimar]

Summary

This is similar to D68086.
We are entering an infinite loop when dumping a histogram for a specially crafted
.hash section with a loop in a chain.

[MaskRay]

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

51 ↗

(On Diff #224291)

Delete all of Address AddressAlign VAddr (see elf-hash-symbols.test)

[grimar]

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

51 ↗

(On Diff #224291)

I think I can't, elf-hash-symbols.test is different, see:
https://github.com/llvm-mirror/llvm/blob/master/tools/llvm-readobj/ELFDumper.cpp#L3954

Here getHashTable returns something based on DT_HASH:
https://github.com/llvm-mirror/llvm/blob/master/tools/llvm-readobj/ELFDumper.cpp#L1713

I.e, I think I've already simplified this YAML to a minimum or at least to a very reasonable minimum.
Am I missing something?

[grimar]

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

51 ↗

(On Diff #224291)

Ah, sorry, I've got it now. I've looked at the wrong test case.

[grimar]

• Addressed review comments.

[jhenderson]

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

45

Nit: This should probably have been ET_DYN or ET_EXEC. Program headers and dynamic sections in relocatable objects are... odd :) No need to change it again though if you don't want to.

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

-RUN: llvm-readelf --elf-hash-histogram %p/Inputs/gnuhash.so.elf-ppc64 \
-RUN:   | FileCheck %s -check-prefix PPC64GNU
-RUN: llvm-readelf --elf-hash-histogram %p/Inputs/gnuhash.so.elf-x86_64 \
-RUN:   | FileCheck %s -check-prefix X86GNU
-RUN: llvm-readelf --elf-hash-histogram %p/Inputs/got-plt.exe.elf-mipsel \
-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%
+# RUN: llvm-readelf --elf-hash-histogram %p/Inputs/gnuhash.so.elf-ppc64 \
+# RUN:   | FileCheck %s -check-prefix PPC64GNU
+# RUN: llvm-readelf --elf-hash-histogram %p/Inputs/gnuhash.so.elf-x86_64 \
+# RUN:   | FileCheck %s -check-prefix X86GNU
+# RUN: llvm-readelf --elf-hash-histogram %p/Inputs/got-plt.exe.elf-mipsel \
+# 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%
+
+## Show that we report a warning for a hash table which contains an entry of
+## the bucket array pointing to a cycle.
+
+# RUN: yaml2obj %s -o %t.o
+# RUN: llvm-readelf --elf-hash-histogram 2>&1 %t.o | FileCheck -DFILE=%t.o %s --check-prefix BROKEN
+
+# BROKEN:       warning: '[[FILE]]': .hash section is invalid: bucket 1: a cycle was detected in the linked chain
+# BROKEN:       Histogram for bucket list length (total of 1 buckets)
+# BROKEN-NEXT:  Length  Number     % of total  Coverage
+# BROKEN-NEXT:       0  0          (  0.0%)       0.0%
+# BROKEN-NEXT:       1  1          (100.0%)     100.0%
+
+--- !ELF
+FileHeader:
+  Class:   ELFCLASS32
+  Data:    ELFDATA2LSB
+  Type:    ET_REL
+  Machine: EM_386
+Sections:
+  - Name:   .hash
+    Type:   SHT_HASH
+    Link:   .dynsym
+    Bucket: [ 1 ]
+    Chain:  [ 0, 1 ]
+  - Name:  .dynamic
+    Type:  SHT_DYNAMIC
+    Flags: [ SHF_ALLOC ]
+    Entries:
+## llvm-readelf will read the hash table from the file offset
+## p_offset + (p_vaddr - DT_HASH) = p_offset + (0 - 0) = p_offset,
+## which is the start of PT_LOAD, i.e. the file offset of .hash.
+      - Tag:   DT_HASH
+        Value: 0x0
+      - Tag:   DT_NULL
+        Value: 0
+DynamicSymbols:
+  - Name: foo
+ProgramHeaders:
+  - Type:  PT_LOAD
+    Sections:
+      - Section: .hash
+      - Section: .dynamic

llvm/tools/llvm-readobj/ELFDumper.cpp

if (const Elf_Hash *HashTable = this->dumper()->getHashTable()) {
 
     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])
+      std::vector<bool> Visited(NChain);
+      for (size_t C = Buckets[B]; C < NChain; C = Chains[C]) {
+        if (C == ELF::STN_UNDEF)
+          break;
+        if (Visited[C]) {
+          reportWarning(
+              createError(".hash section is invalid: bucket " + Twine(C) +
+                          ": a cycle was detected in the linked chain"),
+              this->FileName);
+          break;
+        }
+        Visited[C] = true;
         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