diff options
author | Fangrui Song <maskray@google.com> | 2018-12-21 21:59:34 +0000 |
---|---|---|
committer | Fangrui Song <maskray@google.com> | 2018-12-21 21:59:34 +0000 |
commit | 9eea83be7764ea3b4fc5445272d8c22b5c81d550 (patch) | |
tree | 3536a3eca53b91780e78fb979d1d69109514154f /lld | |
parent | abc3cc30395ce8b2d2e09917cbc9da9ee72bae4f (diff) |
[ELF] .gnu.hash bloom filter: use Shift2 = 26 instead of 6
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
It is varying with the number of dynamic symbols but we don't
necessarily copy its rule.
Reviewers: ruiu, espindola
Reviewed By: ruiu
Subscribers: emaste, arichardson, llvm-commits
Differential Revision: https://reviews.llvm.org/D55971
Diffstat (limited to 'lld')
-rw-r--r-- | lld/ELF/SyntheticSections.cpp | 2 | ||||
-rw-r--r-- | lld/ELF/SyntheticSections.h | 3 | ||||
-rw-r--r-- | lld/test/ELF/gnu-hash-table-rwsegment.s | 4 | ||||
-rw-r--r-- | lld/test/ELF/gnu-hash-table.s | 14 |
4 files changed, 13 insertions, 10 deletions
diff --git a/lld/ELF/SyntheticSections.cpp b/lld/ELF/SyntheticSections.cpp index 293d8452c89..dafd2d02def 100644 --- a/lld/ELF/SyntheticSections.cpp +++ b/lld/ELF/SyntheticSections.cpp @@ -2176,6 +2176,8 @@ void GnuHashTableSection::writeTo(uint8_t *Buf) { void GnuHashTableSection::writeBloomFilter(uint8_t *Buf) { unsigned C = Config->Is64 ? 64 : 32; for (const Entry &Sym : Symbols) { + // When C = 64, we choose a word with bits [6:...] and set 1 to two bits in + // the word using bits [0:5] and [26:31]. size_t I = (Sym.Hash / C) & (MaskWords - 1); uint64_t Val = readUint(Buf + I * Config->Wordsize); Val |= uint64_t(1) << (Sym.Hash % C); diff --git a/lld/ELF/SyntheticSections.h b/lld/ELF/SyntheticSections.h index 63d7897e12a..6fc40d355d5 100644 --- a/lld/ELF/SyntheticSections.h +++ b/lld/ELF/SyntheticSections.h @@ -619,7 +619,8 @@ public: void addSymbols(std::vector<SymbolTableEntry> &Symbols); private: - enum { Shift2 = 6 }; + // See the comment in writeBloomFilter. + enum { Shift2 = 26 }; void writeBloomFilter(uint8_t *Buf); void writeHashTable(uint8_t *Buf); diff --git a/lld/test/ELF/gnu-hash-table-rwsegment.s b/lld/test/ELF/gnu-hash-table-rwsegment.s index b1a50fbde3a..ab1b252bc5d 100644 --- a/lld/test/ELF/gnu-hash-table-rwsegment.s +++ b/lld/test/ELF/gnu-hash-table-rwsegment.s @@ -8,8 +8,8 @@ # 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: } diff --git a/lld/test/ELF/gnu-hash-table.s b/lld/test/ELF/gnu-hash-table.s index 642b445ec5d..9dcd4a081e3 100644 --- a/lld/test/ELF/gnu-hash-table.s +++ b/lld/test/ELF/gnu-hash-table.s @@ -62,7 +62,7 @@ # 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: [] @@ -121,8 +121,8 @@ # 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: } @@ -181,8 +181,8 @@ # 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: } @@ -241,8 +241,8 @@ # 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: } |