[ELF] .gnu.hash bloom filter: use Shift2 = 26 instead of 6

[MaskRay]

Summary

For the 2-bit bloom filter, we currently pick the bits Hash%64 and Hash>>6%64 (Shift2=6), but bits [6:...] are also used to select a word, causing a loss of precision.

In this patch, we choose Shift2=26, with is suggested by Ambrose Feinstein.

Note, Shift2 is computed as maskbitslog2 in bfd/elflink.c and gold/dynobj.cc

[ruiu]

Can you include more benchmark numbers or something that support your claim in the commit message?

[MaskRay]

ref of gold and bfd

[ruiu]

Discussed with Ambrose and I'm convinced that this change makes sense.

So, this is the code to create the bitmap.

for (const Entry &Sym : Symbols) {
  size_t I = (Sym.Hash / C) & (MaskWords - 1);
  uint64_t Val = readUint(Buf + I * Config->Wordsize);
  // We choose Shift2 = 26 to give us high 6 bits for the 64-bit case,
  // (nearly) independent from the low 6 bits, and thus less collision.
  Val |= uint64_t(1) << (Sym.Hash % C);
  Val |= uint64_t(1) << ((Sym.Hash >> Shift2) % C);
  writeUint(Buf + I * Config->Wordsize, Val);
}

Assume a 64-bit target, then C is 64 (or 1 << 6). We compute I which is bit [N:6] of Sym.Hash where N is some integer. (Sym.Hash % C) is bit [0:5]. ((Sym.Hash >> Shift2) % C) is bit [11:6]. Thus, I and the last expression are likely to compute the same value. That results in setting the same bit again and again for each word, so even though we have two bits for each word, we effectively has only one bit if that happens.

[ruiu]

ELF/SyntheticSections.cpp

2181–2182

This is perhaps not the best place to write a comment because it's a bit too deep inside a loop. You probably should give a broader view for a reader.

I'd explain that we choose a word using bit [MaskWords+6 : 6] and set 1 to two bits in the word using bit [0:5] and [26:31].

[MaskRay]

.

[MaskRay]

Update description

[MaskRay]

Better comment

[MaskRay]

Sorry for whatever reason I thought 2 was chosen... Fixed the test

[ruiu]

LGTM

ELF/SyntheticSections.cpp

2180

"It is important to be independent." is a bit too vague or too obvious. I'd just remove that sentence.

[MaskRay]

This comment was removed by MaskRay.

ELF/SyntheticSections.h

public:
   void writeTo(uint8_t *Buf) override;
   size_t getSize() const override { return Size; }
 
   // Adds symbols to the hash table.
   // Sorts the input to satisfy GNU hash section requirements.
   void addSymbols(std::vector<SymbolTableEntry> &Symbols);
 
 private:
+  // See the comment in writeBloomFilter.
   enum { Shift2 = 6 };
 
   void writeBloomFilter(uint8_t *Buf);
   void writeHashTable(uint8_t *Buf);
 
   struct Entry {
     Symbol *Sym;
     size_t StrTabOffset;

ELF/SyntheticSections.cpp

 // filtered out by a bloom filter.
 //
 // [1] Ulrich Drepper (2011), "How To Write Shared Libraries" (Ver. 4.1.2),
 //     p.9, https://www.akkadia.org/drepper/dsohowto.pdf
 void GnuHashTableSection::writeBloomFilter(uint8_t *Buf) {
   unsigned C = Config->Is64 ? 64 : 32;
   for (const Entry &Sym : Symbols) {
     size_t I = (Sym.Hash / C) & (MaskWords - 1);
     uint64_t Val = readUint(Buf + I * Config->Wordsize);
+    // We choose Shift2 = 6 to give us 6 bits (nearly) independent from the low
+    // 6 bits, and thus less collision.
     Val |= uint64_t(1) << (Sym.Hash % C);
     Val |= uint64_t(1) << ((Sym.Hash >> Shift2) % C);
     writeUint(Buf + I * Config->Wordsize, Val);
   }
 }
 
 void GnuHashTableSection::writeHashTable(uint8_t *Buf) {
   uint32_t *Buckets = reinterpret_cast<uint32_t *>(Buf);

test/ELF/gnu-hash-table-rwsegment.s

 # REQUIRES: x86
 
 # RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t.o
 # RUN: ld.lld -shared -hash-style=gnu --no-rosegment -o %t.so %t.o
 # RUN: llvm-readobj -gnu-hash-table %t.so | FileCheck %s
 
 # CHECK:      GnuHashTable {
 # CHECK-NEXT:   Num Buckets: 1
 # CHECK-NEXT:   First Hashed Symbol Index: 1
 # CHECK-NEXT:   Num Mask Words: 1
-# CHECK-NEXT:   Shift Count: 6
-# CHECK-NEXT:   Bloom Filter: [0x400000000004204]
+# CHECK-NEXT:   Shift Count: 26
+# CHECK-NEXT:   Bloom Filter: [0x400000000000204]
 # CHECK-NEXT:   Buckets: [1]
 # CHECK-NEXT:   Values: [0xB8860BA, 0xB887389]
 # CHECK-NEXT: }
 
 .globl foo, bar
 foo:
 bar:
   ret

test/ELF/gnu-hash-table.s

 # EMPTY-NEXT:     Other: 0
 # EMPTY-NEXT:     Section: Undefined
 # EMPTY-NEXT:   }
 # EMPTY-NEXT: ]
 # EMPTY:      GnuHashTable {
 # EMPTY-NEXT:   Num Buckets: 1
 # EMPTY-NEXT:   First Hashed Symbol Index: 2
 # EMPTY-NEXT:   Num Mask Words: 1
-# EMPTY-NEXT:   Shift Count: 6
+# EMPTY-NEXT:   Shift Count: 26
 # EMPTY-NEXT:   Bloom Filter: [0x0]
 # EMPTY-NEXT:   Buckets: [0]
 # EMPTY-NEXT:   Values: []
 # EMPTY-NEXT: }
 
 # I386:      Format: ELF32-i386
 # I386:      Arch: i386
 # I386:      AddressSize: 32bit

 # I386:          Binding: Global
 # I386:          Section: .text
 # I386:        }
 # I386:      ]
 # I386:      GnuHashTable {
 # I386-NEXT:   Num Buckets: 1
 # I386-NEXT:   First Hashed Symbol Index: 4
 # I386-NEXT:   Num Mask Words: 1
-# I386-NEXT:   Shift Count: 6
-# I386-NEXT:   Bloom Filter: [0x4004204]
+# I386-NEXT:   Shift Count: 26
+# I386-NEXT:   Bloom Filter: [0x4000204]
 # I386-NEXT:   Buckets: [4]
 # I386-NEXT:   Values: [0xB8860BA, 0xB887389]
 # I386-NEXT: }
 
 # X86_64:      Format: ELF64-x86-64
 # X86_64:      Arch: x86_64
 # X86_64:      AddressSize: 64bit
 # X86_64:      Sections [

 # X86_64:          Binding: Global
 # X86_64:          Section: .text
 # X86_64:        }
 # X86_64:      ]
 # X86_64:      GnuHashTable {
 # X86_64-NEXT:   Num Buckets: 1
 # X86_64-NEXT:   First Hashed Symbol Index: 4
 # X86_64-NEXT:   Num Mask Words: 1
-# X86_64-NEXT:   Shift Count: 6
-# X86_64-NEXT:   Bloom Filter: [0x400000000004204]
+# X86_64-NEXT:   Shift Count: 26
+# X86_64-NEXT:   Bloom Filter: [0x400000000000204]
 # X86_64-NEXT:   Buckets: [4]
 # X86_64-NEXT:   Values: [0xB8860BA, 0xB887389]
 # X86_64-NEXT: }
 
 # PPC64:      Format: ELF64-ppc64
 # PPC64:      Arch: powerpc64
 # PPC64:      AddressSize: 64bit
 # PPC64:      Sections [

 # PPC64:          Binding: Global
 # PPC64:          Section: .text
 # PPC64:        }
 # PPC64:      ]
 # PPC64:      GnuHashTable {
 # PPC64-NEXT:   Num Buckets: 1
 # PPC64-NEXT:   First Hashed Symbol Index: 4
 # PPC64-NEXT:   Num Mask Words: 1
-# PPC64-NEXT:   Shift Count: 6
-# PPC64-NEXT:   Bloom Filter: [0x400000000004204]
+# PPC64-NEXT:   Shift Count: 26
+# PPC64-NEXT:   Bloom Filter: [0x400000000000204]
 # PPC64-NEXT:   Buckets: [4]
 # PPC64-NEXT:   Values: [0xB8860BA, 0xB887389]
 # PPC64-NEXT: }
 
 .globl foo,bar,baz
 foo:
 bar:
 .weak zed
 .global xyz
 .data
   .dc.a baz