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