1 //===- llvm/unittest/DebugInfo/PDB/HashTableTest.cpp ----------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "llvm/DebugInfo/PDB/Native/HashTable.h"
10 
11 #include "llvm/DebugInfo/PDB/Native/Hash.h"
12 #include "llvm/DebugInfo/PDB/Native/NamedStreamMap.h"
13 #include "llvm/Support/Allocator.h"
14 #include "llvm/Support/BinaryByteStream.h"
15 #include "llvm/Support/BinaryStreamReader.h"
16 #include "llvm/Support/BinaryStreamWriter.h"
17 #include "llvm/Support/StringSaver.h"
18 #include "llvm/Testing/Support/Error.h"
19 
20 #include "gtest/gtest.h"
21 
22 #include <vector>
23 
24 using namespace llvm;
25 using namespace llvm::pdb;
26 using namespace llvm::support;
27 
28 namespace {
29 
30 class HashTableInternals : public HashTable<uint32_t> {
31 public:
32   using HashTable::Buckets;
33   using HashTable::Present;
34   using HashTable::Deleted;
35 };
36 }
37 
38 TEST(HashTableTest, TestSimple) {
39   HashTableInternals Table;
40   EXPECT_EQ(0u, Table.size());
41   EXPECT_GT(Table.capacity(), 0u);
42 
43   Table.set_as(3u, 7);
44   EXPECT_EQ(1u, Table.size());
45   ASSERT_NE(Table.end(), Table.find_as(3u));
46   EXPECT_EQ(7u, Table.get(3u));
47 }
48 
49 TEST(HashTableTest, TestCollision) {
50   HashTableInternals Table;
51   EXPECT_EQ(0u, Table.size());
52   EXPECT_GT(Table.capacity(), 0u);
53 
54   // We use knowledge of the hash table's implementation details to make sure
55   // to add another value that is the equivalent to the first value modulo the
56   // hash table's capacity.
57   uint32_t N1 = Table.capacity() + 1;
58   uint32_t N2 = 2 * N1;
59 
60   Table.set_as(N1, 7);
61   Table.set_as(N2, 12);
62   EXPECT_EQ(2u, Table.size());
63   ASSERT_NE(Table.end(), Table.find_as(N1));
64   ASSERT_NE(Table.end(), Table.find_as(N2));
65 
66   EXPECT_EQ(7u, Table.get(N1));
67   EXPECT_EQ(12u, Table.get(N2));
68 }
69 
70 TEST(HashTableTest, TestRemove) {
71   HashTableInternals Table;
72   EXPECT_EQ(0u, Table.size());
73   EXPECT_GT(Table.capacity(), 0u);
74 
75   Table.set_as(1u, 2);
76   Table.set_as(3u, 4);
77   EXPECT_EQ(2u, Table.size());
78   ASSERT_NE(Table.end(), Table.find_as(1u));
79   ASSERT_NE(Table.end(), Table.find_as(3u));
80 
81   EXPECT_EQ(2u, Table.get(1u));
82   EXPECT_EQ(4u, Table.get(3u));
83 }
84 
85 TEST(HashTableTest, TestCollisionAfterMultipleProbes) {
86   HashTableInternals Table;
87   EXPECT_EQ(0u, Table.size());
88   EXPECT_GT(Table.capacity(), 0u);
89 
90   // Probing looks for the first available slot.  A slot may already be filled
91   // as a result of an item with a *different* hash value already being there.
92   // Test that when this happens, the probe still finds the value.
93   uint32_t N1 = Table.capacity() + 1;
94   uint32_t N2 = N1 + 1;
95   uint32_t N3 = 2 * N1;
96 
97   Table.set_as(N1, 7);
98   Table.set_as(N2, 11);
99   Table.set_as(N3, 13);
100   EXPECT_EQ(3u, Table.size());
101   ASSERT_NE(Table.end(), Table.find_as(N1));
102   ASSERT_NE(Table.end(), Table.find_as(N2));
103   ASSERT_NE(Table.end(), Table.find_as(N3));
104 
105   EXPECT_EQ(7u, Table.get(N1));
106   EXPECT_EQ(11u, Table.get(N2));
107   EXPECT_EQ(13u, Table.get(N3));
108 }
109 
110 TEST(HashTableTest, Grow) {
111   // So that we are independent of the load factor, `capacity` items, which is
112   // guaranteed to trigger a grow.  Then verify that the size is the same, the
113   // capacity is larger, and all the original items are still in the table.
114 
115   HashTableInternals Table;
116   uint32_t OldCapacity = Table.capacity();
117   for (uint32_t I = 0; I < OldCapacity; ++I) {
118     Table.set_as(OldCapacity + I * 2 + 1, I * 2 + 3);
119   }
120   EXPECT_EQ(OldCapacity, Table.size());
121   EXPECT_GT(Table.capacity(), OldCapacity);
122   for (uint32_t I = 0; I < OldCapacity; ++I) {
123     ASSERT_NE(Table.end(), Table.find_as(OldCapacity + I * 2 + 1));
124     EXPECT_EQ(I * 2 + 3, Table.get(OldCapacity + I * 2 + 1));
125   }
126 }
127 
128 TEST(HashTableTest, Serialization) {
129   HashTableInternals Table;
130   uint32_t Cap = Table.capacity();
131   for (uint32_t I = 0; I < Cap; ++I) {
132     Table.set_as(Cap + I * 2 + 1, I * 2 + 3);
133   }
134 
135   std::vector<uint8_t> Buffer(Table.calculateSerializedLength());
136   MutableBinaryByteStream Stream(Buffer, little);
137   BinaryStreamWriter Writer(Stream);
138   EXPECT_THAT_ERROR(Table.commit(Writer), Succeeded());
139   // We should have written precisely the number of bytes we calculated earlier.
140   EXPECT_EQ(Buffer.size(), Writer.getOffset());
141 
142   HashTableInternals Table2;
143   BinaryStreamReader Reader(Stream);
144   EXPECT_THAT_ERROR(Table2.load(Reader), Succeeded());
145   // We should have read precisely the number of bytes we calculated earlier.
146   EXPECT_EQ(Buffer.size(), Reader.getOffset());
147 
148   EXPECT_EQ(Table.size(), Table2.size());
149   EXPECT_EQ(Table.capacity(), Table2.capacity());
150   EXPECT_EQ(Table.Buckets, Table2.Buckets);
151   EXPECT_EQ(Table.Present, Table2.Present);
152   EXPECT_EQ(Table.Deleted, Table2.Deleted);
153 }
154 
155 TEST(HashTableTest, NamedStreamMap) {
156   std::vector<StringRef> Streams = {"One",  "Two", "Three", "Four",
157                                     "Five", "Six", "Seven"};
158   StringMap<uint32_t> ExpectedIndices;
159   for (uint32_t I = 0; I < Streams.size(); ++I)
160     ExpectedIndices[Streams[I]] = I + 1;
161 
162   // To verify the hash table actually works, we want to verify that insertion
163   // order doesn't matter.  So try inserting in every possible order of 7 items.
164   do {
165     NamedStreamMap NSM;
166     for (StringRef S : Streams)
167       NSM.set(S, ExpectedIndices[S]);
168 
169     EXPECT_EQ(Streams.size(), NSM.size());
170 
171     uint32_t N;
172     EXPECT_TRUE(NSM.get("One", N));
173     EXPECT_EQ(1U, N);
174 
175     EXPECT_TRUE(NSM.get("Two", N));
176     EXPECT_EQ(2U, N);
177 
178     EXPECT_TRUE(NSM.get("Three", N));
179     EXPECT_EQ(3U, N);
180 
181     EXPECT_TRUE(NSM.get("Four", N));
182     EXPECT_EQ(4U, N);
183 
184     EXPECT_TRUE(NSM.get("Five", N));
185     EXPECT_EQ(5U, N);
186 
187     EXPECT_TRUE(NSM.get("Six", N));
188     EXPECT_EQ(6U, N);
189 
190     EXPECT_TRUE(NSM.get("Seven", N));
191     EXPECT_EQ(7U, N);
192   } while (std::next_permutation(Streams.begin(), Streams.end()));
193 }
194 
195 namespace {
196 struct FooBar {
197   uint32_t X;
198   uint32_t Y;
199 };
200 
201 } // namespace
202 
203 namespace llvm {
204 namespace pdb {
205 template <> struct PdbHashTraits<FooBar> {
206   std::vector<char> Buffer;
207 
208   PdbHashTraits() { Buffer.push_back(0); }
209 
210   uint32_t hashLookupKey(StringRef S) const {
211     return llvm::pdb::hashStringV1(S);
212   }
213 
214   StringRef storageKeyToLookupKey(uint32_t N) const {
215     if (N >= Buffer.size())
216       return StringRef();
217 
218     return StringRef(Buffer.data() + N);
219   }
220 
221   uint32_t lookupKeyToStorageKey(StringRef S) {
222     uint32_t N = Buffer.size();
223     Buffer.insert(Buffer.end(), S.begin(), S.end());
224     Buffer.push_back('\0');
225     return N;
226   }
227 };
228 } // namespace pdb
229 } // namespace llvm
230 
231 TEST(HashTableTest, NonTrivialValueType) {
232   HashTable<FooBar> Table;
233   uint32_t Cap = Table.capacity();
234   for (uint32_t I = 0; I < Cap; ++I) {
235     FooBar F;
236     F.X = I;
237     F.Y = I + 1;
238     Table.set_as(utostr(I), F);
239   }
240 
241   std::vector<uint8_t> Buffer(Table.calculateSerializedLength());
242   MutableBinaryByteStream Stream(Buffer, little);
243   BinaryStreamWriter Writer(Stream);
244   EXPECT_THAT_ERROR(Table.commit(Writer), Succeeded());
245   // We should have written precisely the number of bytes we calculated earlier.
246   EXPECT_EQ(Buffer.size(), Writer.getOffset());
247 
248   HashTable<FooBar> Table2;
249   BinaryStreamReader Reader(Stream);
250   EXPECT_THAT_ERROR(Table2.load(Reader), Succeeded());
251   // We should have read precisely the number of bytes we calculated earlier.
252   EXPECT_EQ(Buffer.size(), Reader.getOffset());
253 
254   EXPECT_EQ(Table.size(), Table2.size());
255   EXPECT_EQ(Table.capacity(), Table2.capacity());
256   // EXPECT_EQ(Table.Buckets, Table2.Buckets);
257   // EXPECT_EQ(Table.Present, Table2.Present);
258   // EXPECT_EQ(Table.Deleted, Table2.Deleted);
259 }
260