1 // Copyright 2018 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "absl/container/internal/hashtablez_sampler.h"
16
17 #include <atomic>
18 #include <limits>
19 #include <random>
20
21 #include "gmock/gmock.h"
22 #include "gtest/gtest.h"
23 #include "absl/base/attributes.h"
24 #include "absl/container/internal/have_sse.h"
25 #include "absl/synchronization/blocking_counter.h"
26 #include "absl/synchronization/internal/thread_pool.h"
27 #include "absl/synchronization/mutex.h"
28 #include "absl/synchronization/notification.h"
29 #include "absl/time/clock.h"
30 #include "absl/time/time.h"
31
32 #if SWISSTABLE_HAVE_SSE2
33 constexpr int kProbeLength = 16;
34 #else
35 constexpr int kProbeLength = 8;
36 #endif
37
38 namespace absl {
39 ABSL_NAMESPACE_BEGIN
40 namespace container_internal {
41 class HashtablezInfoHandlePeer {
42 public:
IsSampled(const HashtablezInfoHandle & h)43 static bool IsSampled(const HashtablezInfoHandle& h) {
44 return h.info_ != nullptr;
45 }
46
GetInfo(HashtablezInfoHandle * h)47 static HashtablezInfo* GetInfo(HashtablezInfoHandle* h) { return h->info_; }
48 };
49
50 namespace {
51 using ::absl::synchronization_internal::ThreadPool;
52 using ::testing::IsEmpty;
53 using ::testing::UnorderedElementsAre;
54
GetSizes(HashtablezSampler * s)55 std::vector<size_t> GetSizes(HashtablezSampler* s) {
56 std::vector<size_t> res;
57 s->Iterate([&](const HashtablezInfo& info) {
58 res.push_back(info.size.load(std::memory_order_acquire));
59 });
60 return res;
61 }
62
Register(HashtablezSampler * s,size_t size)63 HashtablezInfo* Register(HashtablezSampler* s, size_t size) {
64 auto* info = s->Register();
65 assert(info != nullptr);
66 info->size.store(size);
67 return info;
68 }
69
TEST(HashtablezInfoTest,PrepareForSampling)70 TEST(HashtablezInfoTest, PrepareForSampling) {
71 absl::Time test_start = absl::Now();
72 HashtablezInfo info;
73 absl::MutexLock l(&info.init_mu);
74 info.PrepareForSampling();
75
76 EXPECT_EQ(info.capacity.load(), 0);
77 EXPECT_EQ(info.size.load(), 0);
78 EXPECT_EQ(info.num_erases.load(), 0);
79 EXPECT_EQ(info.max_probe_length.load(), 0);
80 EXPECT_EQ(info.total_probe_length.load(), 0);
81 EXPECT_EQ(info.hashes_bitwise_or.load(), 0);
82 EXPECT_EQ(info.hashes_bitwise_and.load(), ~size_t{});
83 EXPECT_GE(info.create_time, test_start);
84
85 info.capacity.store(1, std::memory_order_relaxed);
86 info.size.store(1, std::memory_order_relaxed);
87 info.num_erases.store(1, std::memory_order_relaxed);
88 info.max_probe_length.store(1, std::memory_order_relaxed);
89 info.total_probe_length.store(1, std::memory_order_relaxed);
90 info.hashes_bitwise_or.store(1, std::memory_order_relaxed);
91 info.hashes_bitwise_and.store(1, std::memory_order_relaxed);
92 info.create_time = test_start - absl::Hours(20);
93
94 info.PrepareForSampling();
95 EXPECT_EQ(info.capacity.load(), 0);
96 EXPECT_EQ(info.size.load(), 0);
97 EXPECT_EQ(info.num_erases.load(), 0);
98 EXPECT_EQ(info.max_probe_length.load(), 0);
99 EXPECT_EQ(info.total_probe_length.load(), 0);
100 EXPECT_EQ(info.hashes_bitwise_or.load(), 0);
101 EXPECT_EQ(info.hashes_bitwise_and.load(), ~size_t{});
102 EXPECT_GE(info.create_time, test_start);
103 }
104
TEST(HashtablezInfoTest,RecordStorageChanged)105 TEST(HashtablezInfoTest, RecordStorageChanged) {
106 HashtablezInfo info;
107 absl::MutexLock l(&info.init_mu);
108 info.PrepareForSampling();
109 RecordStorageChangedSlow(&info, 17, 47);
110 EXPECT_EQ(info.size.load(), 17);
111 EXPECT_EQ(info.capacity.load(), 47);
112 RecordStorageChangedSlow(&info, 20, 20);
113 EXPECT_EQ(info.size.load(), 20);
114 EXPECT_EQ(info.capacity.load(), 20);
115 }
116
TEST(HashtablezInfoTest,RecordInsert)117 TEST(HashtablezInfoTest, RecordInsert) {
118 HashtablezInfo info;
119 absl::MutexLock l(&info.init_mu);
120 info.PrepareForSampling();
121 EXPECT_EQ(info.max_probe_length.load(), 0);
122 RecordInsertSlow(&info, 0x0000FF00, 6 * kProbeLength);
123 EXPECT_EQ(info.max_probe_length.load(), 6);
124 EXPECT_EQ(info.hashes_bitwise_and.load(), 0x0000FF00);
125 EXPECT_EQ(info.hashes_bitwise_or.load(), 0x0000FF00);
126 RecordInsertSlow(&info, 0x000FF000, 4 * kProbeLength);
127 EXPECT_EQ(info.max_probe_length.load(), 6);
128 EXPECT_EQ(info.hashes_bitwise_and.load(), 0x0000F000);
129 EXPECT_EQ(info.hashes_bitwise_or.load(), 0x000FFF00);
130 RecordInsertSlow(&info, 0x00FF0000, 12 * kProbeLength);
131 EXPECT_EQ(info.max_probe_length.load(), 12);
132 EXPECT_EQ(info.hashes_bitwise_and.load(), 0x00000000);
133 EXPECT_EQ(info.hashes_bitwise_or.load(), 0x00FFFF00);
134 }
135
TEST(HashtablezInfoTest,RecordErase)136 TEST(HashtablezInfoTest, RecordErase) {
137 HashtablezInfo info;
138 absl::MutexLock l(&info.init_mu);
139 info.PrepareForSampling();
140 EXPECT_EQ(info.num_erases.load(), 0);
141 EXPECT_EQ(info.size.load(), 0);
142 RecordInsertSlow(&info, 0x0000FF00, 6 * kProbeLength);
143 EXPECT_EQ(info.size.load(), 1);
144 RecordEraseSlow(&info);
145 EXPECT_EQ(info.size.load(), 0);
146 EXPECT_EQ(info.num_erases.load(), 1);
147 }
148
TEST(HashtablezInfoTest,RecordRehash)149 TEST(HashtablezInfoTest, RecordRehash) {
150 HashtablezInfo info;
151 absl::MutexLock l(&info.init_mu);
152 info.PrepareForSampling();
153 RecordInsertSlow(&info, 0x1, 0);
154 RecordInsertSlow(&info, 0x2, kProbeLength);
155 RecordInsertSlow(&info, 0x4, kProbeLength);
156 RecordInsertSlow(&info, 0x8, 2 * kProbeLength);
157 EXPECT_EQ(info.size.load(), 4);
158 EXPECT_EQ(info.total_probe_length.load(), 4);
159
160 RecordEraseSlow(&info);
161 RecordEraseSlow(&info);
162 EXPECT_EQ(info.size.load(), 2);
163 EXPECT_EQ(info.total_probe_length.load(), 4);
164 EXPECT_EQ(info.num_erases.load(), 2);
165
166 RecordRehashSlow(&info, 3 * kProbeLength);
167 EXPECT_EQ(info.size.load(), 2);
168 EXPECT_EQ(info.total_probe_length.load(), 3);
169 EXPECT_EQ(info.num_erases.load(), 0);
170 }
171
172 #if defined(ABSL_HASHTABLEZ_SAMPLE)
TEST(HashtablezSamplerTest,SmallSampleParameter)173 TEST(HashtablezSamplerTest, SmallSampleParameter) {
174 SetHashtablezEnabled(true);
175 SetHashtablezSampleParameter(100);
176
177 for (int i = 0; i < 1000; ++i) {
178 int64_t next_sample = 0;
179 HashtablezInfo* sample = SampleSlow(&next_sample);
180 EXPECT_GT(next_sample, 0);
181 EXPECT_NE(sample, nullptr);
182 UnsampleSlow(sample);
183 }
184 }
185
TEST(HashtablezSamplerTest,LargeSampleParameter)186 TEST(HashtablezSamplerTest, LargeSampleParameter) {
187 SetHashtablezEnabled(true);
188 SetHashtablezSampleParameter(std::numeric_limits<int32_t>::max());
189
190 for (int i = 0; i < 1000; ++i) {
191 int64_t next_sample = 0;
192 HashtablezInfo* sample = SampleSlow(&next_sample);
193 EXPECT_GT(next_sample, 0);
194 EXPECT_NE(sample, nullptr);
195 UnsampleSlow(sample);
196 }
197 }
198
TEST(HashtablezSamplerTest,Sample)199 TEST(HashtablezSamplerTest, Sample) {
200 SetHashtablezEnabled(true);
201 SetHashtablezSampleParameter(100);
202 int64_t num_sampled = 0;
203 int64_t total = 0;
204 double sample_rate = 0.0;
205 for (int i = 0; i < 1000000; ++i) {
206 HashtablezInfoHandle h = Sample();
207 ++total;
208 if (HashtablezInfoHandlePeer::IsSampled(h)) {
209 ++num_sampled;
210 }
211 sample_rate = static_cast<double>(num_sampled) / total;
212 if (0.005 < sample_rate && sample_rate < 0.015) break;
213 }
214 EXPECT_NEAR(sample_rate, 0.01, 0.005);
215 }
216 #endif
217
TEST(HashtablezSamplerTest,Handle)218 TEST(HashtablezSamplerTest, Handle) {
219 auto& sampler = HashtablezSampler::Global();
220 HashtablezInfoHandle h(sampler.Register());
221 auto* info = HashtablezInfoHandlePeer::GetInfo(&h);
222 info->hashes_bitwise_and.store(0x12345678, std::memory_order_relaxed);
223
224 bool found = false;
225 sampler.Iterate([&](const HashtablezInfo& h) {
226 if (&h == info) {
227 EXPECT_EQ(h.hashes_bitwise_and.load(), 0x12345678);
228 found = true;
229 }
230 });
231 EXPECT_TRUE(found);
232
233 h = HashtablezInfoHandle();
234 found = false;
235 sampler.Iterate([&](const HashtablezInfo& h) {
236 if (&h == info) {
237 // this will only happen if some other thread has resurrected the info
238 // the old handle was using.
239 if (h.hashes_bitwise_and.load() == 0x12345678) {
240 found = true;
241 }
242 }
243 });
244 EXPECT_FALSE(found);
245 }
246
TEST(HashtablezSamplerTest,Registration)247 TEST(HashtablezSamplerTest, Registration) {
248 HashtablezSampler sampler;
249 auto* info1 = Register(&sampler, 1);
250 EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(1));
251
252 auto* info2 = Register(&sampler, 2);
253 EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(1, 2));
254 info1->size.store(3);
255 EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(3, 2));
256
257 sampler.Unregister(info1);
258 sampler.Unregister(info2);
259 }
260
TEST(HashtablezSamplerTest,Unregistration)261 TEST(HashtablezSamplerTest, Unregistration) {
262 HashtablezSampler sampler;
263 std::vector<HashtablezInfo*> infos;
264 for (size_t i = 0; i < 3; ++i) {
265 infos.push_back(Register(&sampler, i));
266 }
267 EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(0, 1, 2));
268
269 sampler.Unregister(infos[1]);
270 EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(0, 2));
271
272 infos.push_back(Register(&sampler, 3));
273 infos.push_back(Register(&sampler, 4));
274 EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(0, 2, 3, 4));
275 sampler.Unregister(infos[3]);
276 EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(0, 2, 4));
277
278 sampler.Unregister(infos[0]);
279 sampler.Unregister(infos[2]);
280 sampler.Unregister(infos[4]);
281 EXPECT_THAT(GetSizes(&sampler), IsEmpty());
282 }
283
TEST(HashtablezSamplerTest,MultiThreaded)284 TEST(HashtablezSamplerTest, MultiThreaded) {
285 HashtablezSampler sampler;
286 Notification stop;
287 ThreadPool pool(10);
288
289 for (int i = 0; i < 10; ++i) {
290 pool.Schedule([&sampler, &stop]() {
291 std::random_device rd;
292 std::mt19937 gen(rd());
293
294 std::vector<HashtablezInfo*> infoz;
295 while (!stop.HasBeenNotified()) {
296 if (infoz.empty()) {
297 infoz.push_back(sampler.Register());
298 }
299 switch (std::uniform_int_distribution<>(0, 2)(gen)) {
300 case 0: {
301 infoz.push_back(sampler.Register());
302 break;
303 }
304 case 1: {
305 size_t p =
306 std::uniform_int_distribution<>(0, infoz.size() - 1)(gen);
307 HashtablezInfo* info = infoz[p];
308 infoz[p] = infoz.back();
309 infoz.pop_back();
310 sampler.Unregister(info);
311 break;
312 }
313 case 2: {
314 absl::Duration oldest = absl::ZeroDuration();
315 sampler.Iterate([&](const HashtablezInfo& info) {
316 oldest = std::max(oldest, absl::Now() - info.create_time);
317 });
318 ASSERT_GE(oldest, absl::ZeroDuration());
319 break;
320 }
321 }
322 }
323 });
324 }
325 // The threads will hammer away. Give it a little bit of time for tsan to
326 // spot errors.
327 absl::SleepFor(absl::Seconds(3));
328 stop.Notify();
329 }
330
TEST(HashtablezSamplerTest,Callback)331 TEST(HashtablezSamplerTest, Callback) {
332 HashtablezSampler sampler;
333
334 auto* info1 = Register(&sampler, 1);
335 auto* info2 = Register(&sampler, 2);
336
337 static const HashtablezInfo* expected;
338
339 auto callback = [](const HashtablezInfo& info) {
340 // We can't use `info` outside of this callback because the object will be
341 // disposed as soon as we return from here.
342 EXPECT_EQ(&info, expected);
343 };
344
345 // Set the callback.
346 EXPECT_EQ(sampler.SetDisposeCallback(callback), nullptr);
347 expected = info1;
348 sampler.Unregister(info1);
349
350 // Unset the callback.
351 EXPECT_EQ(callback, sampler.SetDisposeCallback(nullptr));
352 expected = nullptr; // no more calls.
353 sampler.Unregister(info2);
354 }
355
356 } // namespace
357 } // namespace container_internal
358 ABSL_NAMESPACE_END
359 } // namespace absl
360