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