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