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