hash-histogram.test

## Here we test the --elf-hash-histogram command line option.

## This test case checks how we built histograms for hash sections.

# RUN: yaml2obj --docnum=1 -D BITS=32 %s -o %t1-32.o
# RUN: llvm-readelf --elf-hash-histogram %t1-32.o | FileCheck %s --check-prefix=HIST

## Test --histogram and -I aliases.
# RUN: llvm-readelf --histogram %t1-32.o | FileCheck %s --check-prefix=HIST
# RUN: llvm-readelf -I %t1-32.o | FileCheck %s --check-prefix=HIST

# 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%
# HIST-NEXT:       1  0          (  0.0%)       0.0%
# HIST-NEXT:       2  0          (  0.0%)       0.0%
# HIST-NEXT:       3  1          ( 33.3%)     100.0%
# HIST-NEXT: Histogram for `.gnu.hash' bucket list length (total of 3 buckets)
# HIST-NEXT:  Length  Number     % of total  Coverage
# HIST-NEXT:       0  1          ( 33.3%)       0.0%
# HIST-NEXT:       1  1          ( 33.3%)      25.0%
# HIST-NEXT:       2  0          (  0.0%)      25.0%
# 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]]
  Data:  ELFDATA2LSB
  Type:  ET_DYN
Sections:
  - Name:   .hash
    Type:   SHT_HASH
    Flags:  [ SHF_ALLOC ]
    Bucket: [ 6, 4, 5 ]
    Chain:  [ 0, 0, 1, 0, 2 ]
  - Name:  .gnu.hash
    Type:  SHT_GNU_HASH
    Flags: [ SHF_ALLOC ]
    Header:
      SymNdx: 0x1
      Shift2: 0x0
    BloomFilter: [ 0x0 ]
    HashBuckets: [ 0x00000001, 0x00000004, 0x00000000 ]
    HashValues:  [ 0x0B887388, 0xECD54542, 0x7C92E3BB, 0x1C5871D9 ]
  - Name:  .dynamic
    Type:  SHT_DYNAMIC
    Flags: [ SHF_WRITE, SHF_ALLOC ]
    Entries:
      - Tag:   DT_HASH
        Value: 0x0
      - Tag:   DT_GNU_HASH
## sizeof(.hash) == 0x28.
        Value: 0x28
      - Tag:   DT_NULL
        Value: 0x0
DynamicSymbols:
  - Name: a
  - Name: b
  - Name: c
  - Name: d
ProgramHeaders:
  - Type:     PT_LOAD
    FirstSec: .hash
    LastSec:  .dynamic

## Show that we report a warning for a hash table which contains an entry of
## the bucket array pointing to a cycle.

# RUN: yaml2obj --docnum=2 %s -o %t2.o
# RUN: llvm-readelf --elf-hash-histogram 2>&1 %t2.o | \
# RUN:   FileCheck -DFILE=%t2.o %s --check-prefix=BROKEN --implicit-check-not=warning:

# 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 2 buckets)
# BROKEN-NEXT:  Length  Number     % of total  Coverage
# BROKEN-NEXT:       0  0          (  0.0%)       0.0%
# BROKEN-NEXT:       1  2          (100.0%)     100.0%

--- !ELF
FileHeader:
  Class: ELFCLASS32
  Data:  ELFDATA2LSB
  Type:  ET_REL
Sections:
  - Name:   .hash
    Type:   SHT_HASH
    Link:   .dynsym
    Bucket: [ 1, 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
    FirstSec: .hash
    LastSec:  .dynamic

## Each SHT_HASH section starts with two 32-bit fields: nbucket and nchain.
## Check we report an error when a DT_HASH value points to data that has size less than 8 bytes.

# RUN: yaml2obj --docnum=3 %s -o %t3.o
# RUN: llvm-readelf --elf-hash-histogram %t3.o 2>&1 | FileCheck %s --check-prefix=ERR1 -DFILE=%t3.o

# ERR1: warning: '[[FILE]]': the hash table at offset 0x2b1 goes past the end of the file (0x2b8){{$}}

--- !ELF
FileHeader:
  Class: ELFCLASS64
  Data:  ELFDATA2LSB
  Type:  ET_DYN
Sections:
  - Name:   .hash
    Type:   SHT_HASH
    Flags:  [ SHF_ALLOC ]
    Bucket: [ 0 ]
    Chain:  [ 0 ]
  - Name:  .dynamic
    Type:  SHT_DYNAMIC
    Flags: [ SHF_WRITE, SHF_ALLOC ]
    Entries:
      - Tag:   DT_HASH
        Value: 0x239
      - Tag:   DT_NULL
        Value: 0x0
DynamicSymbols: []
ProgramHeaders:
  - Type:     PT_LOAD
    FileSize: 0x23a
    FirstSec: .hash
    LastSec:  .dynamic

## Check we report a warning when the hash table goes past the end of the file.

## Case A.1: the hash table ends right before the EOF. We have a broken nbucket
##           field that has a value larger than the number of buckets.
# RUN: yaml2obj --docnum=4 %s -o %t4.1.o -DNBUCKET=0x5d -DNCHAIN=0x1
# RUN: llvm-readelf --elf-hash-histogram %t4.1.o 2>&1 | \
# RUN:   FileCheck %s --implicit-check-not={{.}} --allow-empty

## Case A.2: the hash table ends 1 byte past the EOF. We have a broken nbucket
##           field that has a value larger than the number of buckets.
# RUN: yaml2obj --docnum=4 %s -o %t4.2.o -DNBUCKET=0x5e -DNCHAIN=0x1
# RUN: llvm-readelf --elf-hash-histogram %t4.2.o 2>&1 | \
# RUN:   FileCheck %s --check-prefix=ERR2 -DFILE=%t4.2.o --implicit-check-not="warning:"
# ERR2: warning: '[[FILE]]': the hash table at offset 0x54 goes past the end of the file (0x1d4), nbucket = 94, nchain = 1{{$}}

## Case B.1: the hash table ends right before the EOF. We have a broken nchain
##           field that has a value larger than the number of chains.
# RUN: yaml2obj --docnum=4 %s -o %t4.3.o -DNBUCKET=0x1 -DNCHAIN=0x5d
# RUN: llvm-readelf --elf-hash-histogram %t4.3.o 2>&1 | \
# RUN:   FileCheck %s --check-prefix=ERR3 -DFILE=%t4.3.o --implicit-check-not="warning:"
# ERR3: warning: '[[FILE]]': hash table nchain (93) differs from symbol count derived from SHT_DYNSYM section header (1){{$}}
# ERR3: warning: '[[FILE]]': the size (0x5d0) of the dynamic symbol table at 0x78, derived from the hash table, goes past the end of the file (0x1d4) and will be ignored

## Case B.2: the hash table ends 1 byte past the EOF. We have a broken nchain
##           field that has a value larger than the number of chains.
# RUN: yaml2obj --docnum=4 %s -o %t4.4.o -DNBUCKET=0x1 -DNCHAIN=0x5e
# RUN: llvm-readelf --elf-hash-histogram %t4.4.o 2>&1 | \
# RUN:   FileCheck %s --check-prefix=ERR4 -DFILE=%t4.4.o --implicit-check-not="warning:"
# ERR4: warning: '[[FILE]]': hash table nchain (94) differs from symbol count derived from SHT_DYNSYM section header (1){{$}}
# ERR4: warning: '[[FILE]]': the size (0x5e0) of the dynamic symbol table at 0x78, derived from the hash table, goes past the end of the file (0x1d4) and will be ignored
# ERR4: warning: '[[FILE]]': the hash table at offset 0x54 goes past the end of the file (0x1d4), nbucket = 1, nchain = 94{{$}}

--- !ELF
FileHeader:
  Class: ELFCLASS32
  Data:  ELFDATA2LSB
  Type:  ET_DYN
Sections:
  - Name:    .hash
    Type:    SHT_HASH
    Flags:   [ SHF_ALLOC ]
    Bucket:  [ 0 ]
    NBucket: [[NBUCKET]]
    Chain:   [ 0 ]
    NChain:  [[NCHAIN]]
  - Name:  .dynamic
    Type:  SHT_DYNAMIC
    Flags: [ SHF_WRITE, SHF_ALLOC ]
    Entries:
      - Tag:   DT_HASH
        Value: 0x0
      - Tag:   DT_NULL
        Value: 0x0
DynamicSymbols: []
ProgramHeaders:
  - Type:     PT_LOAD
    FirstSec: .hash
    LastSec:  .dynamic

## Check we dump a histogram for the .gnu.hash table even when the .hash table is skipped.

## Case A: the .hash table has no data to build histogram and it is skipped.
# RUN: yaml2obj --docnum=5 %s -o %t5.o
# RUN: llvm-readelf --elf-hash-histogram %t5.o 2>&1 | \
# RUN:   FileCheck %s --check-prefix=GNU-HASH --implicit-check-not="Histogram"

## Case B: the .hash table has a broken nbucket field. We report a warning
##         and skip dumping of the .hash table.
# RUN: yaml2obj --docnum=5 -DNBUCKET=0xffffffff %s -o %t6.o
# RUN: llvm-readelf --elf-hash-histogram %t6.o 2>&1 | \
# RUN:   FileCheck %s -DFILE=%t6.o --check-prefixes=WARN,GNU-HASH

# WARN:     warning: '[[FILE]]': the hash table at offset 0x78 goes past the end of the file (0x358), nbucket = 4294967295, nchain = 2
# GNU-HASH: Histogram for `.gnu.hash' bucket list length (total of 3 buckets)

--- !ELF
FileHeader:
  Class: ELFCLASS64
  Data:  ELFDATA2LSB
  Type:  ET_DYN
Sections:
  - Name:    .hash
    Type:    SHT_HASH
    Flags:   [ SHF_ALLOC ]
    Bucket:  [ 0 ]
## 0x2 is a no-op: it does not change the number of buckets described by the "Bucket" key
    NBucket: [[NBUCKET=0x2]]
    Chain:   [ 0, 0 ]
  - Name:  .gnu.hash
    Type:  SHT_GNU_HASH
    Flags: [ SHF_ALLOC ]
    Header:
      SymNdx: 0x1
      Shift2: 0x0
    BloomFilter: [ 0x0 ]
    HashBuckets: [ 0x00000001, 0x00000004, 0x00000000 ]
    HashValues:  [ 0x0B887388 ]
  - Name:  .dynamic
    Type:  SHT_DYNAMIC
    Flags: [ SHF_WRITE, SHF_ALLOC ]
    Entries:
      - Tag:   DT_HASH
        Value: 0x0
      - Tag:   DT_GNU_HASH
## sizeof(.hash) == 0x14.
        Value: 0x14
      - Tag:   DT_NULL
        Value: 0x0
DynamicSymbols:
  - Name: foo
ProgramHeaders:
  - Type:     PT_LOAD
    FirstSec: .hash
    LastSec:  .dynamic

## Check we report a proper warning when the GNU hash table goes past the end of the file.

## Case A: the 'maskwords' field is set so that the GNU hash table goes past the end of the file.
# RUN: yaml2obj --docnum=6 -D MASKWORDS=0x80000000 %s -o %t7
# RUN: llvm-readelf --elf-hash-histogram %t7 2>&1 | \
# RUN:   FileCheck %s -DFILE=%t7 --check-prefix=ERR5 --implicit-check-not="Histogram"

# ERR5: warning: '[[FILE]]': unable to dump the SHT_GNU_HASH section at 0x78: it goes past the end of the file

## Case B: the 'nbuckets' field is set so that the GNU hash table goes past the end of the file.
# RUN: yaml2obj --docnum=6 -D NBUCKETS=0x80000000 %s -o %t8
# RUN: llvm-readelf --elf-hash-histogram %t8 2>&1 | \
# RUN:   FileCheck %s -DFILE=%t8 --check-prefix=ERR5 --implicit-check-not="Histogram"

--- !ELF
FileHeader:
  Class: ELFCLASS64
  Data:  ELFDATA2LSB
  Type:  ET_DYN
Sections:
  - Name:  .gnu.hash
    Type:  SHT_GNU_HASH
    Flags: [ SHF_ALLOC ]
    Header:
      SymNdx: 0x0
      Shift2: 0x0
## The number of words in the Bloom filter. The value of 1 is no-op.
      MaskWords: [[MASKWORDS=1]]
## The number of hash buckets. The value of 1 is no-op.
      NBuckets:  [[NBUCKETS=1]]
    BloomFilter: [ 0x0 ]
    HashBuckets: [ 0x0 ]
    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
    FirstSec: .gnu.hash
    LastSec:  .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 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
# 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
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
    FirstSec: .gnu.hash
    LastSec:  .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
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
    FirstSec: .gnu.hash
    LastSec:  .gnu.hash