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 <cassert>
19 #include <cstddef>
20 #include <cstdint>
21 #include <limits>
22 #include <random>
23 #include <vector>
24
25 #include "gmock/gmock.h"
26 #include "gtest/gtest.h"
27 #include "absl/base/attributes.h"
28 #include "absl/base/config.h"
29 #include "absl/profiling/internal/sample_recorder.h"
30 #include "absl/synchronization/blocking_counter.h"
31 #include "absl/synchronization/internal/thread_pool.h"
32 #include "absl/synchronization/mutex.h"
33 #include "absl/synchronization/notification.h"
34 #include "absl/time/clock.h"
35 #include "absl/time/time.h"
36
37 #ifdef ABSL_INTERNAL_HAVE_SSE2
38 constexpr int kProbeLength = 16;
39 #else
40 constexpr int kProbeLength = 8;
41 #endif
42
43 namespace absl {
44 ABSL_NAMESPACE_BEGIN
45 namespace container_internal {
46 #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
47 class HashtablezInfoHandlePeer {
48 public:
GetInfo(HashtablezInfoHandle * h)49 static HashtablezInfo* GetInfo(HashtablezInfoHandle* h) { return h->info_; }
50 };
51 #else
52 class HashtablezInfoHandlePeer {
53 public:
54 static HashtablezInfo* GetInfo(HashtablezInfoHandle*) { return nullptr; }
55 };
56 #endif // defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
57
58 namespace {
59 using ::absl::synchronization_internal::ThreadPool;
60 using ::testing::IsEmpty;
61 using ::testing::UnorderedElementsAre;
62
GetSizes(HashtablezSampler * s)63 std::vector<size_t> GetSizes(HashtablezSampler* s) {
64 std::vector<size_t> res;
65 s->Iterate([&](const HashtablezInfo& info) {
66 res.push_back(info.size.load(std::memory_order_acquire));
67 });
68 return res;
69 }
70
Register(HashtablezSampler * s,size_t size)71 HashtablezInfo* Register(HashtablezSampler* s, size_t size) {
72 const int64_t test_stride = 123;
73 const size_t test_element_size = 17;
74 const size_t test_key_size = 3;
75 const size_t test_value_size = 5;
76 auto* info =
77 s->Register(test_stride, test_element_size, /*key_size=*/test_key_size,
78 /*value_size=*/test_value_size, /*soo_capacity=*/0);
79 assert(info != nullptr);
80 info->size.store(size);
81 return info;
82 }
83
TEST(HashtablezInfoTest,PrepareForSampling)84 TEST(HashtablezInfoTest, PrepareForSampling) {
85 absl::Time test_start = absl::Now();
86 const int64_t test_stride = 123;
87 const size_t test_element_size = 17;
88 const size_t test_key_size = 15;
89 const size_t test_value_size = 13;
90
91 HashtablezInfo info;
92 absl::MutexLock l(&info.init_mu);
93 info.PrepareForSampling(test_stride, test_element_size,
94 /*key_size=*/test_key_size,
95 /*value_size=*/test_value_size,
96 /*soo_capacity_value=*/1);
97
98 EXPECT_EQ(info.capacity.load(), 0);
99 EXPECT_EQ(info.size.load(), 0);
100 EXPECT_EQ(info.num_erases.load(), 0);
101 EXPECT_EQ(info.num_rehashes.load(), 0);
102 EXPECT_EQ(info.max_probe_length.load(), 0);
103 EXPECT_EQ(info.total_probe_length.load(), 0);
104 EXPECT_EQ(info.hashes_bitwise_or.load(), 0);
105 EXPECT_EQ(info.hashes_bitwise_and.load(), ~size_t{});
106 EXPECT_EQ(info.hashes_bitwise_xor.load(), 0);
107 EXPECT_EQ(info.max_reserve.load(), 0);
108 EXPECT_GE(info.create_time, test_start);
109 EXPECT_EQ(info.weight, test_stride);
110 EXPECT_EQ(info.inline_element_size, test_element_size);
111 EXPECT_EQ(info.key_size, test_key_size);
112 EXPECT_EQ(info.value_size, test_value_size);
113 EXPECT_EQ(info.soo_capacity, 1);
114
115 info.capacity.store(1, std::memory_order_relaxed);
116 info.size.store(1, std::memory_order_relaxed);
117 info.num_erases.store(1, std::memory_order_relaxed);
118 info.max_probe_length.store(1, std::memory_order_relaxed);
119 info.total_probe_length.store(1, std::memory_order_relaxed);
120 info.hashes_bitwise_or.store(1, std::memory_order_relaxed);
121 info.hashes_bitwise_and.store(1, std::memory_order_relaxed);
122 info.hashes_bitwise_xor.store(1, std::memory_order_relaxed);
123 info.max_reserve.store(1, std::memory_order_relaxed);
124 info.create_time = test_start - absl::Hours(20);
125
126 info.PrepareForSampling(test_stride * 2, test_element_size,
127 /*key_size=*/test_key_size,
128 /*value_size=*/test_value_size,
129 /*soo_capacity_value=*/0);
130 EXPECT_EQ(info.capacity.load(), 0);
131 EXPECT_EQ(info.size.load(), 0);
132 EXPECT_EQ(info.num_erases.load(), 0);
133 EXPECT_EQ(info.num_rehashes.load(), 0);
134 EXPECT_EQ(info.max_probe_length.load(), 0);
135 EXPECT_EQ(info.total_probe_length.load(), 0);
136 EXPECT_EQ(info.hashes_bitwise_or.load(), 0);
137 EXPECT_EQ(info.hashes_bitwise_and.load(), ~size_t{});
138 EXPECT_EQ(info.hashes_bitwise_xor.load(), 0);
139 EXPECT_EQ(info.max_reserve.load(), 0);
140 EXPECT_EQ(info.weight, 2 * test_stride);
141 EXPECT_EQ(info.inline_element_size, test_element_size);
142 EXPECT_EQ(info.key_size, test_key_size);
143 EXPECT_EQ(info.value_size, test_value_size);
144 EXPECT_GE(info.create_time, test_start);
145 EXPECT_EQ(info.soo_capacity, 0);
146 }
147
TEST(HashtablezInfoTest,RecordStorageChanged)148 TEST(HashtablezInfoTest, RecordStorageChanged) {
149 HashtablezInfo info;
150 absl::MutexLock l(&info.init_mu);
151 const int64_t test_stride = 21;
152 const size_t test_element_size = 19;
153 const size_t test_key_size = 17;
154 const size_t test_value_size = 15;
155
156 info.PrepareForSampling(test_stride, test_element_size,
157 /*key_size=*/test_key_size,
158 /*value_size=*/test_value_size,
159 /*soo_capacity_value=*/0);
160 RecordStorageChangedSlow(&info, 17, 47);
161 EXPECT_EQ(info.size.load(), 17);
162 EXPECT_EQ(info.capacity.load(), 47);
163 RecordStorageChangedSlow(&info, 20, 20);
164 EXPECT_EQ(info.size.load(), 20);
165 EXPECT_EQ(info.capacity.load(), 20);
166 }
167
TEST(HashtablezInfoTest,RecordInsert)168 TEST(HashtablezInfoTest, RecordInsert) {
169 HashtablezInfo info;
170 absl::MutexLock l(&info.init_mu);
171 const int64_t test_stride = 25;
172 const size_t test_element_size = 23;
173 const size_t test_key_size = 21;
174 const size_t test_value_size = 19;
175
176 info.PrepareForSampling(test_stride, test_element_size,
177 /*key_size=*/test_key_size,
178 /*value_size=*/test_value_size,
179 /*soo_capacity_value=*/0);
180 EXPECT_EQ(info.max_probe_length.load(), 0);
181 RecordInsertSlow(&info, 0x0000FF00, 6 * kProbeLength);
182 EXPECT_EQ(info.max_probe_length.load(), 6);
183 EXPECT_EQ(info.hashes_bitwise_and.load(), 0x0000FF00);
184 EXPECT_EQ(info.hashes_bitwise_or.load(), 0x0000FF00);
185 EXPECT_EQ(info.hashes_bitwise_xor.load(), 0x0000FF00);
186 RecordInsertSlow(&info, 0x000FF000, 4 * kProbeLength);
187 EXPECT_EQ(info.max_probe_length.load(), 6);
188 EXPECT_EQ(info.hashes_bitwise_and.load(), 0x0000F000);
189 EXPECT_EQ(info.hashes_bitwise_or.load(), 0x000FFF00);
190 EXPECT_EQ(info.hashes_bitwise_xor.load(), 0x000F0F00);
191 RecordInsertSlow(&info, 0x00FF0000, 12 * kProbeLength);
192 EXPECT_EQ(info.max_probe_length.load(), 12);
193 EXPECT_EQ(info.hashes_bitwise_and.load(), 0x00000000);
194 EXPECT_EQ(info.hashes_bitwise_or.load(), 0x00FFFF00);
195 EXPECT_EQ(info.hashes_bitwise_xor.load(), 0x00F00F00);
196 }
197
TEST(HashtablezInfoTest,RecordErase)198 TEST(HashtablezInfoTest, RecordErase) {
199 const int64_t test_stride = 31;
200 const size_t test_element_size = 29;
201 const size_t test_key_size = 27;
202 const size_t test_value_size = 25;
203
204 HashtablezInfo info;
205 absl::MutexLock l(&info.init_mu);
206 info.PrepareForSampling(test_stride, test_element_size,
207 /*key_size=*/test_key_size,
208 /*value_size=*/test_value_size,
209 /*soo_capacity_value=*/1);
210 EXPECT_EQ(info.num_erases.load(), 0);
211 EXPECT_EQ(info.size.load(), 0);
212 RecordInsertSlow(&info, 0x0000FF00, 6 * kProbeLength);
213 EXPECT_EQ(info.size.load(), 1);
214 RecordEraseSlow(&info);
215 EXPECT_EQ(info.size.load(), 0);
216 EXPECT_EQ(info.num_erases.load(), 1);
217 EXPECT_EQ(info.inline_element_size, test_element_size);
218 EXPECT_EQ(info.key_size, test_key_size);
219 EXPECT_EQ(info.value_size, test_value_size);
220 EXPECT_EQ(info.soo_capacity, 1);
221 }
222
TEST(HashtablezInfoTest,RecordRehash)223 TEST(HashtablezInfoTest, RecordRehash) {
224 const int64_t test_stride = 33;
225 const size_t test_element_size = 31;
226 const size_t test_key_size = 29;
227 const size_t test_value_size = 27;
228 HashtablezInfo info;
229 absl::MutexLock l(&info.init_mu);
230 info.PrepareForSampling(test_stride, test_element_size,
231 /*key_size=*/test_key_size,
232 /*value_size=*/test_value_size,
233
234 /*soo_capacity_value=*/0);
235 RecordInsertSlow(&info, 0x1, 0);
236 RecordInsertSlow(&info, 0x2, kProbeLength);
237 RecordInsertSlow(&info, 0x4, kProbeLength);
238 RecordInsertSlow(&info, 0x8, 2 * kProbeLength);
239 EXPECT_EQ(info.size.load(), 4);
240 EXPECT_EQ(info.total_probe_length.load(), 4);
241
242 RecordEraseSlow(&info);
243 RecordEraseSlow(&info);
244 EXPECT_EQ(info.size.load(), 2);
245 EXPECT_EQ(info.total_probe_length.load(), 4);
246 EXPECT_EQ(info.num_erases.load(), 2);
247
248 RecordRehashSlow(&info, 3 * kProbeLength);
249 EXPECT_EQ(info.size.load(), 2);
250 EXPECT_EQ(info.total_probe_length.load(), 3);
251 EXPECT_EQ(info.num_erases.load(), 0);
252 EXPECT_EQ(info.num_rehashes.load(), 1);
253 EXPECT_EQ(info.inline_element_size, test_element_size);
254 EXPECT_EQ(info.key_size, test_key_size);
255 EXPECT_EQ(info.value_size, test_value_size);
256 EXPECT_EQ(info.soo_capacity, 0);
257 }
258
TEST(HashtablezInfoTest,RecordReservation)259 TEST(HashtablezInfoTest, RecordReservation) {
260 HashtablezInfo info;
261 absl::MutexLock l(&info.init_mu);
262 const int64_t test_stride = 35;
263 const size_t test_element_size = 33;
264 const size_t test_key_size = 31;
265 const size_t test_value_size = 29;
266
267 info.PrepareForSampling(test_stride, test_element_size,
268 /*key_size=*/test_key_size,
269 /*value_size=*/test_value_size,
270
271 /*soo_capacity_value=*/0);
272 RecordReservationSlow(&info, 3);
273 EXPECT_EQ(info.max_reserve.load(), 3);
274
275 RecordReservationSlow(&info, 2);
276 // High watermark does not change
277 EXPECT_EQ(info.max_reserve.load(), 3);
278
279 RecordReservationSlow(&info, 10);
280 // High watermark does change
281 EXPECT_EQ(info.max_reserve.load(), 10);
282 }
283
284 #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
TEST(HashtablezSamplerTest,SmallSampleParameter)285 TEST(HashtablezSamplerTest, SmallSampleParameter) {
286 const size_t test_element_size = 31;
287 const size_t test_key_size = 33;
288 const size_t test_value_size = 35;
289
290 SetHashtablezEnabled(true);
291 SetHashtablezSampleParameter(100);
292
293 for (int i = 0; i < 1000; ++i) {
294 SamplingState next_sample = {0, 0};
295 HashtablezInfo* sample =
296 SampleSlow(next_sample, test_element_size,
297 /*key_size=*/test_key_size, /*value_size=*/test_value_size,
298
299 /*soo_capacity=*/0);
300 EXPECT_GT(next_sample.next_sample, 0);
301 EXPECT_EQ(next_sample.next_sample, next_sample.sample_stride);
302 EXPECT_NE(sample, nullptr);
303 UnsampleSlow(sample);
304 }
305 }
306
TEST(HashtablezSamplerTest,LargeSampleParameter)307 TEST(HashtablezSamplerTest, LargeSampleParameter) {
308 const size_t test_element_size = 31;
309 const size_t test_key_size = 33;
310 const size_t test_value_size = 35;
311 SetHashtablezEnabled(true);
312 SetHashtablezSampleParameter(std::numeric_limits<int32_t>::max());
313
314 for (int i = 0; i < 1000; ++i) {
315 SamplingState next_sample = {0, 0};
316 HashtablezInfo* sample =
317 SampleSlow(next_sample, test_element_size,
318 /*key_size=*/test_key_size, /*value_size=*/test_value_size,
319 /*soo_capacity=*/0);
320 EXPECT_GT(next_sample.next_sample, 0);
321 EXPECT_EQ(next_sample.next_sample, next_sample.sample_stride);
322 EXPECT_NE(sample, nullptr);
323 UnsampleSlow(sample);
324 }
325 }
326
TEST(HashtablezSamplerTest,Sample)327 TEST(HashtablezSamplerTest, Sample) {
328 const size_t test_element_size = 31;
329 const size_t test_key_size = 33;
330 const size_t test_value_size = 35;
331 SetHashtablezEnabled(true);
332 SetHashtablezSampleParameter(100);
333 int64_t num_sampled = 0;
334 int64_t total = 0;
335 double sample_rate = 0.0;
336 for (int i = 0; i < 1000000; ++i) {
337 HashtablezInfoHandle h =
338 Sample(test_element_size,
339 /*key_size=*/test_key_size, /*value_size=*/test_value_size,
340
341 /*soo_capacity=*/0);
342
343 ++total;
344 if (h.IsSampled()) {
345 ++num_sampled;
346 }
347 sample_rate = static_cast<double>(num_sampled) / total;
348 if (0.005 < sample_rate && sample_rate < 0.015) break;
349 }
350 EXPECT_NEAR(sample_rate, 0.01, 0.005);
351 }
352
TEST(HashtablezSamplerTest,Handle)353 TEST(HashtablezSamplerTest, Handle) {
354 auto& sampler = GlobalHashtablezSampler();
355 const int64_t test_stride = 41;
356 const size_t test_element_size = 39;
357 const size_t test_key_size = 37;
358 const size_t test_value_size = 35;
359 HashtablezInfoHandle h(sampler.Register(test_stride, test_element_size,
360 /*key_size=*/test_key_size,
361 /*value_size=*/test_value_size,
362 /*soo_capacity=*/0));
363 auto* info = HashtablezInfoHandlePeer::GetInfo(&h);
364 info->hashes_bitwise_and.store(0x12345678, std::memory_order_relaxed);
365
366 bool found = false;
367 sampler.Iterate([&](const HashtablezInfo& h) {
368 if (&h == info) {
369 EXPECT_EQ(h.weight, test_stride);
370 EXPECT_EQ(h.hashes_bitwise_and.load(), 0x12345678);
371 found = true;
372 }
373 });
374 EXPECT_TRUE(found);
375
376 h.Unregister();
377 h = HashtablezInfoHandle();
378 found = false;
379 sampler.Iterate([&](const HashtablezInfo& h) {
380 if (&h == info) {
381 // this will only happen if some other thread has resurrected the info
382 // the old handle was using.
383 if (h.hashes_bitwise_and.load() == 0x12345678) {
384 found = true;
385 }
386 }
387 });
388 EXPECT_FALSE(found);
389 }
390 #endif
391
392
TEST(HashtablezSamplerTest,Registration)393 TEST(HashtablezSamplerTest, Registration) {
394 HashtablezSampler sampler;
395 auto* info1 = Register(&sampler, 1);
396 EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(1));
397
398 auto* info2 = Register(&sampler, 2);
399 EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(1, 2));
400 info1->size.store(3);
401 EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(3, 2));
402
403 sampler.Unregister(info1);
404 sampler.Unregister(info2);
405 }
406
TEST(HashtablezSamplerTest,Unregistration)407 TEST(HashtablezSamplerTest, Unregistration) {
408 HashtablezSampler sampler;
409 std::vector<HashtablezInfo*> infos;
410 for (size_t i = 0; i < 3; ++i) {
411 infos.push_back(Register(&sampler, i));
412 }
413 EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(0, 1, 2));
414
415 sampler.Unregister(infos[1]);
416 EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(0, 2));
417
418 infos.push_back(Register(&sampler, 3));
419 infos.push_back(Register(&sampler, 4));
420 EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(0, 2, 3, 4));
421 sampler.Unregister(infos[3]);
422 EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(0, 2, 4));
423
424 sampler.Unregister(infos[0]);
425 sampler.Unregister(infos[2]);
426 sampler.Unregister(infos[4]);
427 EXPECT_THAT(GetSizes(&sampler), IsEmpty());
428 }
429
TEST(HashtablezSamplerTest,MultiThreaded)430 TEST(HashtablezSamplerTest, MultiThreaded) {
431 HashtablezSampler sampler;
432 Notification stop;
433 ThreadPool pool(10);
434
435 for (int i = 0; i < 10; ++i) {
436 const int64_t sampling_stride = 11 + i % 3;
437 const size_t elt_size = 10 + i % 2;
438 const size_t key_size = 12 + i % 4;
439 const size_t value_size = 13 + i % 5;
440 pool.Schedule([&sampler, &stop, sampling_stride, elt_size, key_size,
441 value_size]() {
442 std::random_device rd;
443 std::mt19937 gen(rd());
444
445 std::vector<HashtablezInfo*> infoz;
446 while (!stop.HasBeenNotified()) {
447 if (infoz.empty()) {
448 infoz.push_back(sampler.Register(sampling_stride, elt_size,
449 /*key_size=*/key_size,
450 /*value_size=*/value_size,
451 /*soo_capacity=*/0));
452 }
453 switch (std::uniform_int_distribution<>(0, 2)(gen)) {
454 case 0: {
455 infoz.push_back(sampler.Register(sampling_stride, elt_size,
456 /*key_size=*/key_size,
457 /*value_size=*/value_size,
458
459 /*soo_capacity=*/0));
460 break;
461 }
462 case 1: {
463 size_t p =
464 std::uniform_int_distribution<>(0, infoz.size() - 1)(gen);
465 HashtablezInfo* info = infoz[p];
466 infoz[p] = infoz.back();
467 infoz.pop_back();
468 EXPECT_EQ(info->weight, sampling_stride);
469 sampler.Unregister(info);
470 break;
471 }
472 case 2: {
473 absl::Duration oldest = absl::ZeroDuration();
474 sampler.Iterate([&](const HashtablezInfo& info) {
475 oldest = std::max(oldest, absl::Now() - info.create_time);
476 });
477 ASSERT_GE(oldest, absl::ZeroDuration());
478 break;
479 }
480 }
481 }
482 });
483 }
484 // The threads will hammer away. Give it a little bit of time for tsan to
485 // spot errors.
486 absl::SleepFor(absl::Seconds(3));
487 stop.Notify();
488 }
489
TEST(HashtablezSamplerTest,Callback)490 TEST(HashtablezSamplerTest, Callback) {
491 HashtablezSampler sampler;
492
493 auto* info1 = Register(&sampler, 1);
494 auto* info2 = Register(&sampler, 2);
495
496 static const HashtablezInfo* expected;
497
498 auto callback = [](const HashtablezInfo& info) {
499 // We can't use `info` outside of this callback because the object will be
500 // disposed as soon as we return from here.
501 EXPECT_EQ(&info, expected);
502 };
503
504 // Set the callback.
505 EXPECT_EQ(sampler.SetDisposeCallback(callback), nullptr);
506 expected = info1;
507 sampler.Unregister(info1);
508
509 // Unset the callback.
510 EXPECT_EQ(callback, sampler.SetDisposeCallback(nullptr));
511 expected = nullptr; // no more calls.
512 sampler.Unregister(info2);
513 }
514
515 } // namespace
516 } // namespace container_internal
517 ABSL_NAMESPACE_END
518 } // namespace absl
519