hashtablez_sampler_test.cc (17833B)
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 <cassert> 19 #include <cstddef> 20 #include <cstdint> 21 #include <limits> 22 #include <random> 23 #include <vector> 24 25 #include "gmock/gmock.h" 26 #include "gtest/gtest.h" 27 #include "absl/base/attributes.h" 28 #include "absl/base/config.h" 29 #include "absl/profiling/internal/sample_recorder.h" 30 #include "absl/synchronization/blocking_counter.h" 31 #include "absl/synchronization/internal/thread_pool.h" 32 #include "absl/synchronization/mutex.h" 33 #include "absl/synchronization/notification.h" 34 #include "absl/time/clock.h" 35 #include "absl/time/time.h" 36 37 #ifdef ABSL_INTERNAL_HAVE_SSE2 38 constexpr int kProbeLength = 16; 39 #else 40 constexpr int kProbeLength = 8; 41 #endif 42 43 namespace absl { 44 ABSL_NAMESPACE_BEGIN 45 namespace container_internal { 46 #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) 47 class HashtablezInfoHandlePeer { 48 public: 49 static HashtablezInfo* GetInfo(HashtablezInfoHandle* h) { return h->info_; } 50 }; 51 #else 52 class HashtablezInfoHandlePeer { 53 public: 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 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 71 HashtablezInfo* Register(HashtablezSampler* s, size_t size) { 72 const int64_t test_stride = 123; 73 const size_t test_element_size = 17; 74 const size_t test_key_size = 3; 75 const size_t test_value_size = 5; 76 auto* info = 77 s->Register(test_stride, test_element_size, /*key_size=*/test_key_size, 78 /*value_size=*/test_value_size, /*soo_capacity=*/0); 79 assert(info != nullptr); 80 info->size.store(size); 81 return info; 82 } 83 84 TEST(HashtablezInfoTest, PrepareForSampling) { 85 absl::Time test_start = absl::Now(); 86 const int64_t test_stride = 123; 87 const size_t test_element_size = 17; 88 const size_t test_key_size = 15; 89 const size_t test_value_size = 13; 90 91 HashtablezInfo info; 92 absl::MutexLock l(&info.init_mu); 93 info.PrepareForSampling(test_stride, test_element_size, 94 /*key_size=*/test_key_size, 95 /*value_size=*/test_value_size, 96 /*soo_capacity_value=*/1); 97 98 EXPECT_EQ(info.capacity.load(), 0); 99 EXPECT_EQ(info.size.load(), 0); 100 EXPECT_EQ(info.num_erases.load(), 0); 101 EXPECT_EQ(info.num_rehashes.load(), 0); 102 EXPECT_EQ(info.max_probe_length.load(), 0); 103 EXPECT_EQ(info.total_probe_length.load(), 0); 104 EXPECT_EQ(info.hashes_bitwise_or.load(), 0); 105 EXPECT_EQ(info.hashes_bitwise_and.load(), ~size_t{}); 106 EXPECT_EQ(info.hashes_bitwise_xor.load(), 0); 107 EXPECT_EQ(info.max_reserve.load(), 0); 108 EXPECT_GE(info.create_time, test_start); 109 EXPECT_EQ(info.weight, test_stride); 110 EXPECT_EQ(info.inline_element_size, test_element_size); 111 EXPECT_EQ(info.key_size, test_key_size); 112 EXPECT_EQ(info.value_size, test_value_size); 113 EXPECT_EQ(info.soo_capacity, 1); 114 115 info.capacity.store(1, std::memory_order_relaxed); 116 info.size.store(1, std::memory_order_relaxed); 117 info.num_erases.store(1, std::memory_order_relaxed); 118 info.max_probe_length.store(1, std::memory_order_relaxed); 119 info.total_probe_length.store(1, std::memory_order_relaxed); 120 info.hashes_bitwise_or.store(1, std::memory_order_relaxed); 121 info.hashes_bitwise_and.store(1, std::memory_order_relaxed); 122 info.hashes_bitwise_xor.store(1, std::memory_order_relaxed); 123 info.max_reserve.store(1, std::memory_order_relaxed); 124 info.create_time = test_start - absl::Hours(20); 125 126 info.PrepareForSampling(test_stride * 2, test_element_size, 127 /*key_size=*/test_key_size, 128 /*value_size=*/test_value_size, 129 /*soo_capacity_value=*/0); 130 EXPECT_EQ(info.capacity.load(), 0); 131 EXPECT_EQ(info.size.load(), 0); 132 EXPECT_EQ(info.num_erases.load(), 0); 133 EXPECT_EQ(info.num_rehashes.load(), 0); 134 EXPECT_EQ(info.max_probe_length.load(), 0); 135 EXPECT_EQ(info.total_probe_length.load(), 0); 136 EXPECT_EQ(info.hashes_bitwise_or.load(), 0); 137 EXPECT_EQ(info.hashes_bitwise_and.load(), ~size_t{}); 138 EXPECT_EQ(info.hashes_bitwise_xor.load(), 0); 139 EXPECT_EQ(info.max_reserve.load(), 0); 140 EXPECT_EQ(info.weight, 2 * test_stride); 141 EXPECT_EQ(info.inline_element_size, test_element_size); 142 EXPECT_EQ(info.key_size, test_key_size); 143 EXPECT_EQ(info.value_size, test_value_size); 144 EXPECT_GE(info.create_time, test_start); 145 EXPECT_EQ(info.soo_capacity, 0); 146 } 147 148 TEST(HashtablezInfoTest, RecordStorageChanged) { 149 HashtablezInfo info; 150 absl::MutexLock l(&info.init_mu); 151 const int64_t test_stride = 21; 152 const size_t test_element_size = 19; 153 const size_t test_key_size = 17; 154 const size_t test_value_size = 15; 155 156 info.PrepareForSampling(test_stride, test_element_size, 157 /*key_size=*/test_key_size, 158 /*value_size=*/test_value_size, 159 /*soo_capacity_value=*/0); 160 RecordStorageChangedSlow(&info, 17, 47); 161 EXPECT_EQ(info.size.load(), 17); 162 EXPECT_EQ(info.capacity.load(), 47); 163 RecordStorageChangedSlow(&info, 20, 20); 164 EXPECT_EQ(info.size.load(), 20); 165 EXPECT_EQ(info.capacity.load(), 20); 166 } 167 168 TEST(HashtablezInfoTest, RecordInsert) { 169 HashtablezInfo info; 170 absl::MutexLock l(&info.init_mu); 171 const int64_t test_stride = 25; 172 const size_t test_element_size = 23; 173 const size_t test_key_size = 21; 174 const size_t test_value_size = 19; 175 176 info.PrepareForSampling(test_stride, test_element_size, 177 /*key_size=*/test_key_size, 178 /*value_size=*/test_value_size, 179 /*soo_capacity_value=*/0); 180 EXPECT_EQ(info.max_probe_length.load(), 0); 181 RecordInsertSlow(&info, 0x0000FF00, 6 * kProbeLength); 182 EXPECT_EQ(info.max_probe_length.load(), 6); 183 EXPECT_EQ(info.hashes_bitwise_and.load(), 0x0000FF00); 184 EXPECT_EQ(info.hashes_bitwise_or.load(), 0x0000FF00); 185 EXPECT_EQ(info.hashes_bitwise_xor.load(), 0x0000FF00); 186 RecordInsertSlow(&info, 0x000FF000, 4 * kProbeLength); 187 EXPECT_EQ(info.max_probe_length.load(), 6); 188 EXPECT_EQ(info.hashes_bitwise_and.load(), 0x0000F000); 189 EXPECT_EQ(info.hashes_bitwise_or.load(), 0x000FFF00); 190 EXPECT_EQ(info.hashes_bitwise_xor.load(), 0x000F0F00); 191 RecordInsertSlow(&info, 0x00FF0000, 12 * kProbeLength); 192 EXPECT_EQ(info.max_probe_length.load(), 12); 193 EXPECT_EQ(info.hashes_bitwise_and.load(), 0x00000000); 194 EXPECT_EQ(info.hashes_bitwise_or.load(), 0x00FFFF00); 195 EXPECT_EQ(info.hashes_bitwise_xor.load(), 0x00F00F00); 196 } 197 198 TEST(HashtablezInfoTest, RecordErase) { 199 const int64_t test_stride = 31; 200 const size_t test_element_size = 29; 201 const size_t test_key_size = 27; 202 const size_t test_value_size = 25; 203 204 HashtablezInfo info; 205 absl::MutexLock l(&info.init_mu); 206 info.PrepareForSampling(test_stride, test_element_size, 207 /*key_size=*/test_key_size, 208 /*value_size=*/test_value_size, 209 /*soo_capacity_value=*/1); 210 EXPECT_EQ(info.num_erases.load(), 0); 211 EXPECT_EQ(info.size.load(), 0); 212 RecordInsertSlow(&info, 0x0000FF00, 6 * kProbeLength); 213 EXPECT_EQ(info.size.load(), 1); 214 RecordEraseSlow(&info); 215 EXPECT_EQ(info.size.load(), 0); 216 EXPECT_EQ(info.num_erases.load(), 1); 217 EXPECT_EQ(info.inline_element_size, test_element_size); 218 EXPECT_EQ(info.key_size, test_key_size); 219 EXPECT_EQ(info.value_size, test_value_size); 220 EXPECT_EQ(info.soo_capacity, 1); 221 } 222 223 TEST(HashtablezInfoTest, RecordRehash) { 224 const int64_t test_stride = 33; 225 const size_t test_element_size = 31; 226 const size_t test_key_size = 29; 227 const size_t test_value_size = 27; 228 HashtablezInfo info; 229 absl::MutexLock l(&info.init_mu); 230 info.PrepareForSampling(test_stride, test_element_size, 231 /*key_size=*/test_key_size, 232 /*value_size=*/test_value_size, 233 234 /*soo_capacity_value=*/0); 235 RecordInsertSlow(&info, 0x1, 0); 236 RecordInsertSlow(&info, 0x2, kProbeLength); 237 RecordInsertSlow(&info, 0x4, kProbeLength); 238 RecordInsertSlow(&info, 0x8, 2 * kProbeLength); 239 EXPECT_EQ(info.size.load(), 4); 240 EXPECT_EQ(info.total_probe_length.load(), 4); 241 242 RecordEraseSlow(&info); 243 RecordEraseSlow(&info); 244 EXPECT_EQ(info.size.load(), 2); 245 EXPECT_EQ(info.total_probe_length.load(), 4); 246 EXPECT_EQ(info.num_erases.load(), 2); 247 248 RecordRehashSlow(&info, 3 * kProbeLength); 249 EXPECT_EQ(info.size.load(), 2); 250 EXPECT_EQ(info.total_probe_length.load(), 3); 251 EXPECT_EQ(info.num_erases.load(), 0); 252 EXPECT_EQ(info.num_rehashes.load(), 1); 253 EXPECT_EQ(info.inline_element_size, test_element_size); 254 EXPECT_EQ(info.key_size, test_key_size); 255 EXPECT_EQ(info.value_size, test_value_size); 256 EXPECT_EQ(info.soo_capacity, 0); 257 } 258 259 TEST(HashtablezInfoTest, RecordReservation) { 260 HashtablezInfo info; 261 absl::MutexLock l(&info.init_mu); 262 const int64_t test_stride = 35; 263 const size_t test_element_size = 33; 264 const size_t test_key_size = 31; 265 const size_t test_value_size = 29; 266 267 info.PrepareForSampling(test_stride, test_element_size, 268 /*key_size=*/test_key_size, 269 /*value_size=*/test_value_size, 270 271 /*soo_capacity_value=*/0); 272 RecordReservationSlow(&info, 3); 273 EXPECT_EQ(info.max_reserve.load(), 3); 274 275 RecordReservationSlow(&info, 2); 276 // High watermark does not change 277 EXPECT_EQ(info.max_reserve.load(), 3); 278 279 RecordReservationSlow(&info, 10); 280 // High watermark does change 281 EXPECT_EQ(info.max_reserve.load(), 10); 282 } 283 284 #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) 285 TEST(HashtablezSamplerTest, SmallSampleParameter) { 286 const size_t test_element_size = 31; 287 const size_t test_key_size = 33; 288 const size_t test_value_size = 35; 289 290 SetHashtablezEnabled(true); 291 SetHashtablezSampleParameter(100); 292 293 for (int i = 0; i < 1000; ++i) { 294 SamplingState next_sample = {0, 0}; 295 HashtablezInfo* sample = 296 SampleSlow(next_sample, test_element_size, 297 /*key_size=*/test_key_size, /*value_size=*/test_value_size, 298 299 /*soo_capacity=*/0); 300 EXPECT_GT(next_sample.next_sample, 0); 301 EXPECT_EQ(next_sample.next_sample, next_sample.sample_stride); 302 EXPECT_NE(sample, nullptr); 303 UnsampleSlow(sample); 304 } 305 } 306 307 TEST(HashtablezSamplerTest, LargeSampleParameter) { 308 const size_t test_element_size = 31; 309 const size_t test_key_size = 33; 310 const size_t test_value_size = 35; 311 SetHashtablezEnabled(true); 312 SetHashtablezSampleParameter(std::numeric_limits<int32_t>::max()); 313 314 for (int i = 0; i < 1000; ++i) { 315 SamplingState next_sample = {0, 0}; 316 HashtablezInfo* sample = 317 SampleSlow(next_sample, test_element_size, 318 /*key_size=*/test_key_size, /*value_size=*/test_value_size, 319 /*soo_capacity=*/0); 320 EXPECT_GT(next_sample.next_sample, 0); 321 EXPECT_EQ(next_sample.next_sample, next_sample.sample_stride); 322 EXPECT_NE(sample, nullptr); 323 UnsampleSlow(sample); 324 } 325 } 326 327 TEST(HashtablezSamplerTest, Sample) { 328 const size_t test_element_size = 31; 329 const size_t test_key_size = 33; 330 const size_t test_value_size = 35; 331 SetHashtablezEnabled(true); 332 SetHashtablezSampleParameter(100); 333 int64_t num_sampled = 0; 334 int64_t total = 0; 335 double sample_rate = 0.0; 336 for (int i = 0; i < 1000000; ++i) { 337 HashtablezInfoHandle h = 338 Sample(test_element_size, 339 /*key_size=*/test_key_size, /*value_size=*/test_value_size, 340 341 /*soo_capacity=*/0); 342 343 ++total; 344 if (h.IsSampled()) { 345 ++num_sampled; 346 } 347 sample_rate = static_cast<double>(num_sampled) / total; 348 if (0.005 < sample_rate && sample_rate < 0.015) break; 349 } 350 EXPECT_NEAR(sample_rate, 0.01, 0.005); 351 } 352 353 TEST(HashtablezSamplerTest, Handle) { 354 auto& sampler = GlobalHashtablezSampler(); 355 const int64_t test_stride = 41; 356 const size_t test_element_size = 39; 357 const size_t test_key_size = 37; 358 const size_t test_value_size = 35; 359 HashtablezInfoHandle h(sampler.Register(test_stride, test_element_size, 360 /*key_size=*/test_key_size, 361 /*value_size=*/test_value_size, 362 /*soo_capacity=*/0)); 363 auto* info = HashtablezInfoHandlePeer::GetInfo(&h); 364 info->hashes_bitwise_and.store(0x12345678, std::memory_order_relaxed); 365 366 bool found = false; 367 sampler.Iterate([&](const HashtablezInfo& h) { 368 if (&h == info) { 369 EXPECT_EQ(h.weight, test_stride); 370 EXPECT_EQ(h.hashes_bitwise_and.load(), 0x12345678); 371 found = true; 372 } 373 }); 374 EXPECT_TRUE(found); 375 376 h.Unregister(); 377 h = HashtablezInfoHandle(); 378 found = false; 379 sampler.Iterate([&](const HashtablezInfo& h) { 380 if (&h == info) { 381 // this will only happen if some other thread has resurrected the info 382 // the old handle was using. 383 if (h.hashes_bitwise_and.load() == 0x12345678) { 384 found = true; 385 } 386 } 387 }); 388 EXPECT_FALSE(found); 389 } 390 #endif 391 392 393 TEST(HashtablezSamplerTest, Registration) { 394 HashtablezSampler sampler; 395 auto* info1 = Register(&sampler, 1); 396 EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(1)); 397 398 auto* info2 = Register(&sampler, 2); 399 EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(1, 2)); 400 info1->size.store(3); 401 EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(3, 2)); 402 403 sampler.Unregister(info1); 404 sampler.Unregister(info2); 405 } 406 407 TEST(HashtablezSamplerTest, Unregistration) { 408 HashtablezSampler sampler; 409 std::vector<HashtablezInfo*> infos; 410 for (size_t i = 0; i < 3; ++i) { 411 infos.push_back(Register(&sampler, i)); 412 } 413 EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(0, 1, 2)); 414 415 sampler.Unregister(infos[1]); 416 EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(0, 2)); 417 418 infos.push_back(Register(&sampler, 3)); 419 infos.push_back(Register(&sampler, 4)); 420 EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(0, 2, 3, 4)); 421 sampler.Unregister(infos[3]); 422 EXPECT_THAT(GetSizes(&sampler), UnorderedElementsAre(0, 2, 4)); 423 424 sampler.Unregister(infos[0]); 425 sampler.Unregister(infos[2]); 426 sampler.Unregister(infos[4]); 427 EXPECT_THAT(GetSizes(&sampler), IsEmpty()); 428 } 429 430 TEST(HashtablezSamplerTest, MultiThreaded) { 431 HashtablezSampler sampler; 432 Notification stop; 433 ThreadPool pool(10); 434 435 for (int i = 0; i < 10; ++i) { 436 const int64_t sampling_stride = 11 + i % 3; 437 const size_t elt_size = 10 + i % 2; 438 const size_t key_size = 12 + i % 4; 439 const size_t value_size = 13 + i % 5; 440 pool.Schedule([&sampler, &stop, sampling_stride, elt_size, key_size, 441 value_size]() { 442 std::random_device rd; 443 std::mt19937 gen(rd()); 444 445 std::vector<HashtablezInfo*> infoz; 446 while (!stop.HasBeenNotified()) { 447 if (infoz.empty()) { 448 infoz.push_back(sampler.Register(sampling_stride, elt_size, 449 /*key_size=*/key_size, 450 /*value_size=*/value_size, 451 /*soo_capacity=*/0)); 452 } 453 switch (std::uniform_int_distribution<>(0, 2)(gen)) { 454 case 0: { 455 infoz.push_back(sampler.Register(sampling_stride, elt_size, 456 /*key_size=*/key_size, 457 /*value_size=*/value_size, 458 459 /*soo_capacity=*/0)); 460 break; 461 } 462 case 1: { 463 size_t p = 464 std::uniform_int_distribution<>(0, infoz.size() - 1)(gen); 465 HashtablezInfo* info = infoz[p]; 466 infoz[p] = infoz.back(); 467 infoz.pop_back(); 468 EXPECT_EQ(info->weight, sampling_stride); 469 sampler.Unregister(info); 470 break; 471 } 472 case 2: { 473 absl::Duration oldest = absl::ZeroDuration(); 474 sampler.Iterate([&](const HashtablezInfo& info) { 475 oldest = std::max(oldest, absl::Now() - info.create_time); 476 }); 477 ASSERT_GE(oldest, absl::ZeroDuration()); 478 break; 479 } 480 } 481 } 482 }); 483 } 484 // The threads will hammer away. Give it a little bit of time for tsan to 485 // spot errors. 486 absl::SleepFor(absl::Seconds(3)); 487 stop.Notify(); 488 } 489 490 TEST(HashtablezSamplerTest, Callback) { 491 HashtablezSampler sampler; 492 493 auto* info1 = Register(&sampler, 1); 494 auto* info2 = Register(&sampler, 2); 495 496 static const HashtablezInfo* expected; 497 498 auto callback = [](const HashtablezInfo& info) { 499 // We can't use `info` outside of this callback because the object will be 500 // disposed as soon as we return from here. 501 EXPECT_EQ(&info, expected); 502 }; 503 504 // Set the callback. 505 EXPECT_EQ(sampler.SetDisposeCallback(callback), nullptr); 506 expected = info1; 507 sampler.Unregister(info1); 508 509 // Unset the callback. 510 EXPECT_EQ(callback, sampler.SetDisposeCallback(nullptr)); 511 expected = nullptr; // no more calls. 512 sampler.Unregister(info2); 513 } 514 515 } // namespace 516 } // namespace container_internal 517 ABSL_NAMESPACE_END 518 } // namespace absl