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