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