1 // Copyright 2021 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef V8_TEST_CCTEST_TEST_SWISS_HASH_TABLE_SHARED_TESTS_H_ 6 #define V8_TEST_CCTEST_TEST_SWISS_HASH_TABLE_SHARED_TESTS_H_ 7 8 #include <algorithm> 9 #include <string> 10 11 #include "test/cctest/test-swiss-name-dictionary-infra.h" 12 13 namespace v8 { 14 namespace internal { 15 namespace test_swiss_hash_table { 16 17 // The name of the test-*.cc file that executes the tests below with the 18 // RuntimeTestRunner. 19 extern const char kRuntimeTestFileName[]; 20 21 // The name of the test-*.cc file that executes the tests below with the 22 // CSATestRunner. 23 extern const char kCSATestFileName[]; 24 25 // This class contains test cases for SwissNameDictionary that can be executed 26 // by different "test runners", which are supplied as a template parameter. The 27 // TestRunner determines how the operations on dictionaries are actually 28 // executed. Currently there are two TestRunners: RuntimeTestRunner calls C++ 29 // functions, whereas CSATestRunner executes dictionary operations by executing 30 // CSA-generated code. 31 // To execute the tests, just create an instance of the class below with an 32 // appropriate TestRunner. 33 // Whenever creating an instance of this class in a file bar.cc, the template 34 // parameter |kTestFileName| should be set to the name of the file that 35 // *instantiates the class* (i.e., "bar.cc"). This ensures that the tests 36 // defined below are then registred within the overall cctest machinery as if 37 // they were directly written within bar.cc. 38 template <typename TestRunner, char const* kTestFileName> 39 struct SharedSwissTableTests { 40 STATIC_ASSERT((std::is_same<TestRunner, RuntimeTestRunner>::value) || 41 (std::is_same<TestRunner, CSATestRunner>::value)); 42 SharedSwissTableTestsSharedSwissTableTests43 SharedSwissTableTests() { 44 CHECK(kTestFileName == kRuntimeTestFileName || 45 kTestFileName == kCSATestFileName); 46 } 47 48 using TS = TestSequence<TestRunner>; 49 50 // 51 // Helpers 52 // 53 54 // We add this value when we want to create fake H1 values to prevent us from 55 // accidentally creating an overall hash of 0, which is forbidden. Due to all 56 // H1 values are used modulo the capacity of the table, this has no further 57 // effects. Note that using just this value itself as an H1 value means that a 58 // key will (try to) occupy bucket 0. 59 static const int kBigModulus = (1 << 22); 60 STATIC_ASSERT(SwissNameDictionary::IsValidCapacity(kBigModulus)); 61 62 // Returns elements from TS::distinct_property_details in a determinstic 63 // order. Subsequent calls with increasing |index| (and the same |offset|) 64 // will return pairwise different values until |index| has risen by more than 65 // {TS::distinct_property_details.size()}. 66 static PropertyDetails distinct_details(int index, int offset = 0) { 67 int size = static_cast<int>(distinct_property_details.size()); 68 return distinct_property_details[(index + offset) % size]; 69 } 70 71 // Adds elements at the boundaries of the table, e.g. to buckets 0, 1, 72 // Capacity() - 2, and Capacity() - 1. (But only three of those if the table 73 // can't hold 4 elements without resizing). AddAtBoundariesSharedSwissTableTests74 static void AddAtBoundaries(TS& s) { 75 int capacity = s.initial_capacity; 76 std::vector<int> interesting_indices = s.boundary_indices(capacity); 77 78 s.CheckCounts(capacity, 0, 0); 79 80 int count = 0; 81 for (int index : interesting_indices) { 82 std::string key = "k" + std::to_string(index); 83 std::string value = "v" + std::to_string(index); 84 PropertyDetails details = distinct_details(count++); 85 s.Add(Key{key, FakeH1{index + kBigModulus}}, value, details); 86 } 87 88 // We didn't want to cause a resize: 89 s.CheckCounts(capacity); 90 } 91 92 // Adds |count| entries to the table, using their unmodified hashes, of the 93 // form key_i -> (value_i, details_i), where key_i and value_i are build from 94 // appending the actual index (e.g., 0, ...., counts - 1) to |key_prefix| and 95 // |value_prefix|, respectively. The property details are taken from 96 // |distinct_property_details|. 97 static void AddMultiple(TS& s, int count, std::string key_prefix = "key", 98 std::string value_prefix = "value", 99 int details_offset = 0) { 100 for (int i = 0; i < count; ++i) { 101 std::string key = key_prefix + std::to_string(i); 102 std::string value = value_prefix + std::to_string(i); 103 PropertyDetails d = distinct_details(i); 104 s.Add(Key{key}, value, d); 105 } 106 } 107 108 // Checks that |count| entries exist, as they would have been added by a call 109 // to AddMultiple with the same arguments. 110 static void CheckMultiple(TS& s, int count, std::string key_prefix = "key", 111 std::string value_prefix = "value", 112 int details_offset = 0) { 113 DCHECK_LE(count, 114 SwissNameDictionary::MaxUsableCapacity(s.initial_capacity)); 115 116 std::vector<std::string> expected_keys; 117 for (int i = 0; i < count; ++i) { 118 std::string key = key_prefix + std::to_string(i); 119 expected_keys.push_back(key); 120 std::string value = value_prefix + std::to_string(i); 121 int details_index = 122 (details_offset + i) % distinct_property_details.size(); 123 PropertyDetails d = distinct_property_details[details_index]; 124 s.CheckDataAtKey(Key{key}, kIndexUnknown, value, d); 125 } 126 s.CheckEnumerationOrder(expected_keys); 127 } 128 129 // 130 // Start of actual tests. 131 // 132 MEMBER_TESTSharedSwissTableTests133 MEMBER_TEST(Allocation) { 134 TS::WithAllInterestingInitialCapacities([](TS& s) { 135 // The test runner does the allocation automatically. 136 s.CheckCounts(s.initial_capacity, 0, 0); 137 s.VerifyHeap(); 138 }); 139 } 140 141 // Simple test for adding entries. Also uses non-Symbol keys and non-String 142 // values, which is not supported by the higher-level testing infrastructure. MEMBER_TESTSharedSwissTableTests143 MEMBER_TEST(SimpleAdd) { 144 // TODO(v8:11330): Remove once CSA implementation has a fallback for 145 // non-SSSE3/AVX configurations. 146 if (!TestRunner::IsEnabled()) return; 147 TS::WithInitialCapacity(4, [](TS& s) { 148 Handle<String> key1 = s.isolate->factory()->InternalizeUtf8String("foo"); 149 Handle<String> value1 = 150 s.isolate->factory()->InternalizeUtf8String("bar"); 151 PropertyDetails details1 = 152 PropertyDetails(PropertyKind::kData, PropertyAttributes::DONT_DELETE, 153 PropertyCellType::kNoCell); 154 155 s.CheckCounts(4, 0, 0); 156 s.CheckKeyAbsent(key1); 157 158 s.Add(key1, value1, details1); 159 s.CheckDataAtKey(key1, kIndexUnknown, value1, details1); 160 s.CheckCounts(4, 1, 0); 161 162 Handle<Symbol> key2 = s.isolate->factory()->NewSymbol(); 163 Handle<Smi> value2 = handle(Smi::FromInt(123), s.isolate); 164 PropertyDetails details2 = 165 PropertyDetails(PropertyKind::kData, PropertyAttributes::DONT_DELETE, 166 PropertyCellType::kNoCell); 167 168 s.CheckKeyAbsent(key2); 169 s.Add(key2, value2, details2); 170 s.CheckDataAtKey(key2, kIndexUnknown, value2, details2); 171 s.CheckCounts(4, 2, 0); 172 }); 173 } 174 175 // Simple test for updating existing entries. Also uses non-Symbol keys and 176 // non-String values, which is not supported by the higher-level testing 177 // infrastructure. MEMBER_TESTSharedSwissTableTests178 MEMBER_TEST(SimpleUpdate) { 179 // TODO(v8:11330): Remove once CSA implementation has a fallback for 180 // non-SSSE3/AVX configurations. 181 if (!TestRunner::IsEnabled()) return; 182 TS::WithInitialCapacity(4, [](TS& s) { 183 Handle<String> key1 = s.isolate->factory()->InternalizeUtf8String("foo"); 184 Handle<String> value1 = 185 s.isolate->factory()->InternalizeUtf8String("bar"); 186 PropertyDetails details1 = 187 PropertyDetails(PropertyKind::kData, PropertyAttributes::DONT_DELETE, 188 PropertyCellType::kNoCell); 189 190 s.Add(key1, value1, details1); 191 192 Handle<Symbol> key2 = s.isolate->factory()->NewSymbol(); 193 Handle<Smi> value2 = handle(Smi::FromInt(123), s.isolate); 194 PropertyDetails details2 = 195 PropertyDetails(PropertyKind::kData, PropertyAttributes::DONT_DELETE, 196 PropertyCellType::kNoCell); 197 198 s.Add(key2, value2, details2); 199 200 // Until here same operations as in Test "Add". 201 202 Handle<Smi> value1_updated = handle(Smi::FromInt(456), s.isolate); 203 Handle<String> value2_updated = 204 s.isolate->factory()->InternalizeUtf8String("updated"); 205 PropertyDetails details1_updated = details2; 206 PropertyDetails details2_updated = details1; 207 208 s.UpdateByKey(key1, value1_updated, details1_updated); 209 s.CheckDataAtKey(key1, kIndexUnknown, value1_updated, details1_updated); 210 s.CheckDataAtKey(key2, kIndexUnknown, value2, details2); 211 212 s.UpdateByKey(key2, value2_updated, details2_updated); 213 s.CheckDataAtKey(key1, kIndexUnknown, value1_updated, details1_updated); 214 s.CheckDataAtKey(key2, kIndexUnknown, value2_updated, details2_updated); 215 s.CheckCounts(4, 2, 0); 216 }); 217 } 218 219 // Simple test for deleting existing entries. Also uses non-Symbol keys and 220 // non-String values, which is not supported by the higher-level testing 221 // infrastructure. MEMBER_TESTSharedSwissTableTests222 MEMBER_TEST(SimpleDelete) { 223 // TODO(v8:11330): Remove once CSA implementation has a fallback for 224 // non-SSSE3/AVX configurations. 225 if (!TestRunner::IsEnabled()) return; 226 TS::WithInitialCapacity(4, [](TS& s) { 227 Handle<String> key1 = s.isolate->factory()->InternalizeUtf8String("foo"); 228 Handle<String> value1 = 229 s.isolate->factory()->InternalizeUtf8String("bar"); 230 PropertyDetails details1 = 231 PropertyDetails(PropertyKind::kData, PropertyAttributes::DONT_DELETE, 232 PropertyCellType::kNoCell); 233 234 s.Add(key1, value1, details1); 235 236 Handle<Symbol> key2 = s.isolate->factory()->NewSymbol(); 237 Handle<Smi> value2 = handle(Smi::FromInt(123), s.isolate); 238 PropertyDetails details2 = 239 PropertyDetails(PropertyKind::kData, PropertyAttributes::DONT_DELETE, 240 PropertyCellType::kNoCell); 241 242 s.Add(key2, value2, details2); 243 244 // Until here same operations as in Test "Add". 245 246 s.DeleteByKey(key1); 247 s.CheckKeyAbsent(key1); 248 s.CheckDataAtKey(key2, kIndexUnknown, value2, details2); 249 s.CheckCounts(4, 1, 1); 250 251 s.DeleteByKey(key2); 252 s.CheckKeyAbsent(key1); 253 s.CheckKeyAbsent(key2); 254 s.CheckCounts(4, 0, 0); 255 }); 256 } 257 258 // Adds entries that occuppy the boundaries (first and last 259 // buckets) of the hash table. MEMBER_TESTSharedSwissTableTests260 MEMBER_TEST(AddAtBoundaries) { 261 // TODO(v8:11330): Remove once CSA implementation has a fallback for 262 // non-SSSE3/AVX configurations. 263 if (!TestRunner::IsEnabled()) return; 264 TS::WithAllInterestingInitialCapacities([](TS& s) { 265 AddAtBoundaries(s); 266 267 int capacity = s.initial_capacity; 268 269 std::vector<int> boundary_indices = s.boundary_indices(capacity); 270 int size = static_cast<int>(boundary_indices.size()); 271 272 int count = 0; 273 for (int index : boundary_indices) { 274 std::string key = "k" + std::to_string(index); 275 std::string value = "v" + std::to_string(index); 276 PropertyDetails details = distinct_details(count++); 277 278 s.CheckDataAtKey(Key{key, FakeH1{index + kBigModulus}}, 279 InternalIndex(index), value, details); 280 } 281 s.CheckCounts(capacity, size, 0); 282 }); 283 } 284 285 // Adds entries that occuppy the boundaries of the hash table, then updates 286 // their values and property details. MEMBER_TESTSharedSwissTableTests287 MEMBER_TEST(UpdateAtBoundaries) { 288 // TODO(v8:11330): Remove once CSA implementation has a fallback for 289 // non-SSSE3/AVX configurations. 290 if (!TestRunner::IsEnabled()) return; 291 TS::WithAllInterestingInitialCapacities([](TS& s) { 292 AddAtBoundaries(s); 293 294 int capacity = s.initial_capacity; 295 296 std::vector<int> boundary_indices = s.boundary_indices(capacity); 297 int size = static_cast<int>(boundary_indices.size()); 298 299 int count = 0; 300 for (int index : boundary_indices) { 301 std::string key = "k" + std::to_string(index); 302 std::string value = "newv" + std::to_string(index); 303 // setting offset means getting other PropertyDetails than before 304 PropertyDetails details = distinct_details(count++, size); 305 306 s.UpdateByKey(Key{key, FakeH1{index + kBigModulus}}, value, details); 307 } 308 309 count = 0; 310 for (int index : boundary_indices) { 311 std::string key = "k" + std::to_string(index); 312 std::string value = "newv" + std::to_string(index); 313 PropertyDetails details = distinct_details(count++, size); 314 315 s.CheckDataAtKey(Key{key, FakeH1{index + kBigModulus}}, 316 InternalIndex(index), value, details); 317 } 318 }); 319 } 320 321 // Adds entries that occuppy the boundaries of the hash table, then updates 322 // their values and property details. MEMBER_TESTSharedSwissTableTests323 MEMBER_TEST(DeleteAtBoundaries) { 324 // TODO(v8:11330): Remove once CSA implementation has a fallback for 325 // non-SSSE3/AVX configurations. 326 if (!TestRunner::IsEnabled()) return; 327 // The maximum value of {TS::boundary_indices(capacity).size()} for any 328 // |capacity|. 329 int count = 4; 330 331 // Due to shrink-on-delete, we create a new dictionary prior to each 332 // deletion, so that we don't re-hash (which would defeat the purpose of 333 // this test). 334 for (int i = 0; i < count; ++i) { 335 // In this iteration, we delete the i-th element of |boundary_indices|. 336 337 TS::WithAllInterestingInitialCapacities([&](TS& s) { 338 std::vector<int> boundary_indices = 339 TS::boundary_indices(s.initial_capacity); 340 int number_of_entries = static_cast<int>(boundary_indices.size()); 341 DCHECK_GE(count, number_of_entries); 342 343 if (i >= static_cast<int>(boundary_indices.size())) { 344 // Nothing to do. 345 return; 346 } 347 348 AddAtBoundaries(s); 349 350 int entry_to_delete = boundary_indices[i]; 351 int h1 = entry_to_delete + kBigModulus; 352 353 // We know that the key in question was added at bucket 354 // |entry_to_delete| by AddAtBoundaries. 355 Key key = Key{"k" + std::to_string(entry_to_delete), FakeH1{h1}}; 356 s.DeleteByKey(key); 357 s.CheckKeyAbsent(key); 358 359 // Account for the fact that a shrink-on-delete may have happened. 360 int expected_capacity = number_of_entries - 1 < s.initial_capacity / 4 361 ? s.initial_capacity / 2 362 : s.initial_capacity; 363 s.CheckCounts(expected_capacity, number_of_entries - 1); 364 }); 365 } 366 } 367 368 // Adds entries that occuppy the boundaries of the hash table, then add 369 // further entries targeting the same buckets. MEMBER_TESTSharedSwissTableTests370 MEMBER_TEST(OverwritePresentAtBoundaries) { 371 // TODO(v8:11330): Remove once CSA implementation has a fallback for 372 // non-SSSE3/AVX configurations. 373 if (!TestRunner::IsEnabled()) return; 374 TS::WithAllInterestingInitialCapacities([](TS& s) { 375 AddAtBoundaries(s); 376 377 int capacity = s.initial_capacity; 378 379 std::vector<int> boundary_indices = s.boundary_indices(capacity); 380 381 std::vector<std::string> keys, values; 382 std::vector<PropertyDetails> details; 383 384 int count = 0; 385 for (int index : boundary_indices) { 386 std::string key = "additional_k" + std::to_string(index); 387 std::string value = "additional_v" + std::to_string(index); 388 389 PropertyDetails d = distinct_details(count++); 390 keys.push_back(key); 391 values.push_back(value); 392 details.push_back(d); 393 s.Add(Key{key, FakeH1{index + kBigModulus}}, value, d); 394 } 395 396 count = 0; 397 for (int entry : boundary_indices) { 398 std::string key = keys[count]; 399 std::string value = values[count]; 400 PropertyDetails d = details[count]; 401 402 // We don't know the indices where the new entries will land. 403 s.CheckDataAtKey(Key{key, FakeH1{entry + kBigModulus}}, 404 base::Optional<InternalIndex>(), value, d); 405 count++; 406 } 407 408 // The entries added by AddAtBoundaries must also still be there, at their 409 // original indices. 410 count = 0; 411 for (int index : boundary_indices) { 412 std::string key = "k" + std::to_string(index); 413 std::string value = "v" + std::to_string(index); 414 PropertyDetails details = distinct_property_details.at(count++); 415 s.CheckDataAtKey(Key{key, FakeH1{index + kBigModulus}}, 416 InternalIndex(index), value, details); 417 } 418 }); 419 } 420 MEMBER_TESTSharedSwissTableTests421 MEMBER_TEST(Empty) { 422 // TODO(v8:11330): Remove once CSA implementation has a fallback for 423 // non-SSSE3/AVX configurations. 424 if (!TestRunner::IsEnabled()) return; 425 TS::WithInitialCapacities({0}, [](TS& s) { 426 // FindEntry on empty table succeeds. 427 s.CheckKeyAbsent(Key{"some non-existing key"}); 428 }); 429 430 TS::WithInitialCapacities({0}, [](TS& s) { 431 PropertyDetails d = PropertyDetails::Empty(); 432 433 // Adding to empty table causes resize. 434 s.Add(Key{"some key"}, "some value", d); 435 s.CheckDataAtKey(Key{"some key"}, kIndexUnknown, "some value", d); 436 437 s.CheckCounts(SwissNameDictionary::kInitialCapacity, 1, 0); 438 }); 439 440 TS::WithInitialCapacity(0, [](TS& s) { s.CheckEnumerationOrder({}); }); 441 442 // Inplace rehashing and shrinking don't have CSA versions. 443 if (TS::IsRuntimeTest()) { 444 TS::WithInitialCapacity(0, [](TS& s) { 445 s.RehashInplace(); 446 s.CheckCounts(0, 0, 0); 447 s.VerifyHeap(); 448 }); 449 450 TS::WithInitialCapacity(0, [](TS& s) { 451 s.Shrink(); 452 s.CheckCounts(0, 0, 0); 453 s.VerifyHeap(); 454 }); 455 } 456 } 457 458 // We test that hash tables get resized/rehashed correctly by repeatedly 459 // adding an deleting elements. MEMBER_TESTSharedSwissTableTests460 MEMBER_TEST(Resize1) { 461 // TODO(v8:11330): Remove once CSA implementation has a fallback for 462 // non-SSSE3/AVX configurations. 463 if (!TestRunner::IsEnabled()) return; 464 TS::WithInitialCapacity(0, [](TS& s) { 465 // Should be at least 8 so that we capture the transition from 8 bit to 16 466 // bit meta table entries: 467 const int max_exponent = 9; 468 469 // For all |exponent| between 0 and |max_exponent|, we add 2^|exponent| 470 // entries, and then delete every second one of those. Note that we do 471 // this all on a single table, meaning that the entries from the previous 472 // value of |exponent| are still present. 473 int added = 0; 474 int deleted = 0; 475 int offset = 0; 476 for (int exponent = 0; exponent <= max_exponent; ++exponent) { 477 int count = 1 << exponent; 478 for (int i = 0; i < count; ++i) { 479 std::string key = "key" + std::to_string(offset + i); 480 std::string value = "value" + std::to_string(offset + i); 481 482 s.Add(Key{key}, value, distinct_details(i, offset)); 483 ++added; 484 } 485 for (int i = 0; i < count; i += 2) { 486 if (offset + i == 0) { 487 continue; 488 } 489 std::string key = "key" + std::to_string(offset + i); 490 s.DeleteByKey(Key{key}); 491 ++deleted; 492 } 493 494 s.CheckCounts(kNoInt, added - deleted, kNoInt); 495 offset += count; 496 } 497 498 // Some internal consistency checks on the test itself: 499 DCHECK_EQ((1 << (max_exponent + 1)) - 1, offset); 500 DCHECK_EQ(offset, added); 501 DCHECK_EQ(offset / 2, deleted); 502 503 // Check that those entries that we expect are indeed present. 504 for (int i = 0; i < offset; i += 2) { 505 std::string key = "key" + std::to_string(i); 506 std::string value = "value" + std::to_string(i); 507 508 s.CheckDataAtKey(Key{key}, kIndexUnknown, value, distinct_details(i)); 509 } 510 s.VerifyHeap(); 511 }); 512 } 513 514 // Check that we resize exactly when expected. MEMBER_TESTSharedSwissTableTests515 MEMBER_TEST(Resize2) { 516 // TODO(v8:11330): Remove once CSA implementation has a fallback for 517 // non-SSSE3/AVX configurations. 518 if (!TestRunner::IsEnabled()) return; 519 TS::WithInitialCapacities({4, 8, 16, 128}, [](TS& s) { 520 int count = SwissNameDictionary::MaxUsableCapacity(s.initial_capacity); 521 522 AddMultiple(s, count, "resize2"); 523 524 // No resize: 525 s.CheckCounts(s.initial_capacity, count, 0); 526 527 s.Add(Key{"key causing resize"}); 528 s.CheckCounts(2 * s.initial_capacity, count + 1, 0); 529 }); 530 } 531 532 // There are certain capacities where we can fill every single bucket of the 533 // table before resizing (i.e., the max load factor is 100% for those 534 // particular configurations. Test that this works as intended. MEMBER_TESTSharedSwissTableTests535 MEMBER_TEST(AtFullCapacity) { 536 // TODO(v8:11330): Remove once CSA implementation has a fallback for 537 // non-SSSE3/AVX configurations. 538 if (!TestRunner::IsEnabled()) return; 539 // Determine those capacities, allowing 100% max load factor. We trust 540 // MaxUsableCapacity to tell us which capacities that are (e.g., 4 and 8), 541 // because we tested that function separately elsewhere. 542 std::vector<int> capacities_allowing_full_utilization; 543 for (int c = SwissNameDictionary::kInitialCapacity; 544 c <= static_cast<int>(SwissNameDictionary::kGroupWidth); c *= 2) { 545 if (SwissNameDictionary::MaxUsableCapacity(c) == c) { 546 capacities_allowing_full_utilization.push_back(c); 547 } 548 } 549 550 DCHECK_IMPLIES(SwissNameDictionary::kGroupWidth == 16, 551 capacities_allowing_full_utilization.size() > 0); 552 553 TS::WithInitialCapacities(capacities_allowing_full_utilization, [](TS& s) { 554 AddMultiple(s, s.initial_capacity, "k_full_capacity", "v_full_capacity"); 555 556 // No resize must have happened. 557 s.CheckCounts(s.initial_capacity, s.initial_capacity, 0); 558 559 CheckMultiple(s, s.initial_capacity, "k_full_capacity", 560 "v_full_capacity"); 561 562 // Must make sure that the first |SwissNameDictionary::kGroupWidth| 563 // entries of the ctrl table contain a kEmpty, so that an unsuccessful 564 // search stop, instead of going into an infinite loop. Therefore, search 565 // for a fake key whose H1 is 0, making us start from ctrl table bucket 0. 566 s.CheckKeyAbsent(Key{"non_existing_key", FakeH1{0}, FakeH2{1}}); 567 }); 568 } 569 MEMBER_TESTSharedSwissTableTests570 MEMBER_TEST(EnumerationOrder) { 571 // TODO(v8:11330) Disabling this for now until the real CSA testing has 572 // landed. 573 if (true) return; 574 575 // This test times out on sanitizer builds in CSA mode when testing the 576 // larger capacities. 577 // TODO(v8:11330) Revisit this once the actual CSA/Torque versions are run 578 // by the test suite, which will speed things up. 579 std::vector<int> capacities_to_test = 580 TS::IsRuntimeTest() ? interesting_initial_capacities 581 : capacities_for_slow_sanitizer_tests; 582 583 TS::WithInitialCapacities(capacities_to_test, [](TS& s) { 584 std::vector<std::string> expected_keys; 585 int count = std::min( 586 SwissNameDictionary::MaxUsableCapacity(s.initial_capacity), 1000); 587 588 for (int i = 0; i < count; ++i) { 589 std::string key = "enumkey" + std::to_string(i); 590 expected_keys.push_back(key); 591 s.Add(Key{key}); 592 } 593 s.CheckEnumerationOrder(expected_keys); 594 595 // Delete some entries. 596 597 std::string last_key = "enumkey" + std::to_string(count - 1); 598 s.DeleteByKey(Key{"enumkey0"}); 599 s.DeleteByKey(Key{"enumkey1"}); 600 s.DeleteByKey(Key{last_key}); 601 602 auto should_be_deleted = [&](const std::string& k) -> bool { 603 return k == "enumkey0" || k == "enumkey1" || k == last_key; 604 }; 605 expected_keys.erase( 606 std::remove_if(expected_keys.begin(), expected_keys.end(), 607 should_be_deleted), 608 expected_keys.end()); 609 DCHECK_EQ(expected_keys.size(), count - 3); 610 611 s.CheckEnumerationOrder(expected_keys); 612 613 if (s.initial_capacity <= 1024) { 614 // Now cause a resize. Doing + 4 on top of the maximum usable capacity 615 // rather than just + 1 because in the case where the initial capacity 616 // is 4 and the group size is 8, the three deletes above caused a 617 // shrink, which in this case was just a rehash. So we need to add 4 618 // elements to cause a resize. 619 int resize_at = 620 SwissNameDictionary::MaxUsableCapacity(s.initial_capacity) + 4; 621 622 for (int i = count; i < resize_at; ++i) { 623 std::string key = "enumkey" + std::to_string(i); 624 expected_keys.push_back(key); 625 s.Add(Key{key}); 626 } 627 s.CheckCounts(2 * s.initial_capacity); 628 s.CheckEnumerationOrder(expected_keys); 629 } 630 }); 631 } 632 633 // Make sure that keys with colliding H1 and same H2 don't get mixed up. MEMBER_TESTSharedSwissTableTests634 MEMBER_TEST(SameH2) { 635 // TODO(v8:11330): Remove once CSA implementation has a fallback for 636 // non-SSSE3/AVX configurations. 637 if (!TestRunner::IsEnabled()) return; 638 int i = 0; 639 TS::WithAllInterestingInitialCapacities([&](TS& s) { 640 // Let's try a few differnet values for h1, starting at big_modulus;. 641 int first_h1 = i * 13 + kBigModulus; 642 int second_h1 = first_h1 + s.initial_capacity; 643 644 int first_entry = first_h1 % s.initial_capacity; 645 int second_entry = (first_h1 + 1) % s.initial_capacity; 646 647 // Add two keys with same H1 modulo capacity and same H2. 648 Key k1{"first_key", FakeH1{first_h1}, FakeH2{42}}; 649 Key k2{"second_key", FakeH1{second_h1}, FakeH2{42}}; 650 651 s.Add(k1, "v1"); 652 s.Add(k2, "v2"); 653 654 s.CheckDataAtKey(k1, InternalIndex(first_entry), "v1"); 655 s.CheckDataAtKey(k2, InternalIndex(second_entry), "v2"); 656 657 // Deletion works, too. 658 s.DeleteByKey(k2); 659 s.CheckHasKey(k1); 660 s.CheckKeyAbsent(k2); 661 662 ++i; 663 }); 664 } 665 666 // Check that we can delete a key and add it again. MEMBER_TESTSharedSwissTableTests667 MEMBER_TEST(ReAddSameKey) { 668 // TODO(v8:11330): Remove once CSA implementation has a fallback for 669 // non-SSSE3/AVX configurations. 670 if (!TestRunner::IsEnabled()) return; 671 TS::WithInitialCapacity(4, [](TS& s) { 672 s.Add(Key{"some_key"}, "some_value", distinct_details(0)); 673 s.DeleteByKey(Key{"some_key"}); 674 s.Add(Key{"some_key"}, "new_value", distinct_details(1)); 675 s.CheckDataAtKey(Key{"some_key"}, kIndexUnknown, "new_value", 676 distinct_details(1)); 677 s.CheckEnumerationOrder({"some_key"}); 678 }); 679 } 680 681 // Make sure that we continue probing if there is no match in the first 682 // group and that the quadratic probing for choosing subsequent groups to 683 // probe works as intended. MEMBER_TESTSharedSwissTableTests684 MEMBER_TEST(BeyondInitialGroup) { 685 // TODO(v8:11330): Remove once CSA implementation has a fallback for 686 // non-SSSE3/AVX configurations. 687 if (!TestRunner::IsEnabled()) return; 688 TS::WithInitialCapacity(128, [](TS& s) { 689 int h1 = 33; // Arbitrarily chosen. 690 int count = 37; // Will lead to more than 2 groups being filled. 691 692 for (int i = 0; i < count; ++i) { 693 std::string key = "key" + std::to_string(i); 694 std::string value = "value" + std::to_string(i); 695 696 s.Add(Key{key, FakeH1{h1}}, value); 697 } 698 699 s.CheckDataAtKey(Key{"key36", FakeH1{h1}}, kIndexUnknown, "value36"); 700 701 // Deleting something shouldn't disturb further additions. 702 s.DeleteByKey(Key{"key14", FakeH1{h1}}); 703 s.DeleteByKey(Key{"key15", FakeH1{h1}}); 704 s.DeleteByKey(Key{"key16", FakeH1{h1}}); 705 s.DeleteByKey(Key{"key17", FakeH1{h1}}); 706 707 s.Add(Key{"key37", FakeH1{h1}}, "value37"); 708 s.CheckDataAtKey(Key{"key37", FakeH1{h1}}, kIndexUnknown, "value37"); 709 }); 710 } 711 712 // Check that we correclty "wrap around" when probing the control table. This 713 // means that when we probe a group starting at a bucket such that there are 714 // fewer than kGroupWidth bucktets before the end of the control table, we 715 // (logically) continue at bucket 0. Note that actually, we use the copy of 716 // first group at the end of the control table. MEMBER_TESTSharedSwissTableTests717 MEMBER_TEST(WrapAround) { 718 // TODO(v8:11330) Disabling this for now until the real CSA testing has 719 // landed. 720 if (true) { 721 return; 722 } 723 724 // This test times out in CSA mode when testing the larger capacities. 725 // TODO(v8:11330) Revisit this once the actual CSA/Torque versions are run 726 // by the test suite, which will speed things up. 727 std::vector<int> capacities_to_test = TS::IsRuntimeTest() 728 ? interesting_initial_capacities 729 : capacities_for_slow_debug_tests; 730 731 int width = SwissNameDictionary::kGroupWidth; 732 for (int offset_from_end = 0; offset_from_end < width; ++offset_from_end) { 733 TS::WithInitialCapacities(capacities_to_test, [&](TS& s) { 734 int capacity = s.initial_capacity; 735 int first_bucket = capacity - offset_from_end; 736 737 // How many entries to add (carefully chosen not to cause a resize). 738 int filler_entries = 739 std::min(width, SwissNameDictionary::MaxUsableCapacity(capacity)) - 740 1; 741 742 if (first_bucket < 0 || 743 // No wraparound in this case: 744 first_bucket + filler_entries < capacity) { 745 return; 746 } 747 748 // Starting at bucket |first_bucket|, add a sequence of |kGroupWitdth| 749 // - 1 (if table can take that many, see calculation of |filler_entries| 750 // above) entries in a single collision chain. 751 for (int f = 0; f < filler_entries; ++f) { 752 std::string key = "filler" + std::to_string(f); 753 s.Add(Key{key, FakeH1{first_bucket}}); 754 } 755 756 // ... then add a final key which (unless table too small) will end up 757 // in the last bucket belonging to the group started at |first_bucket|. 758 // Check that we can indeed find it. 759 s.Add(Key{"final_key", FakeH1{first_bucket}}); 760 s.CheckDataAtKey(Key{"final_key", FakeH1{first_bucket}}, 761 InternalIndex(filler_entries - offset_from_end)); 762 763 // + 1 due to the final key. 764 s.CheckCounts(s.initial_capacity, filler_entries + 1, 0); 765 766 // Now delete the entries in between and make sure that this 767 // doesn't break anything. 768 for (int f = 0; f < filler_entries; ++f) { 769 std::string key = "filler" + std::to_string(f); 770 s.DeleteByKey(Key{key, FakeH1{first_bucket}}); 771 } 772 773 s.CheckHasKey(Key{"final_key", FakeH1{first_bucket}}); 774 }); 775 } 776 } 777 MEMBER_TESTSharedSwissTableTests778 MEMBER_TEST(RehashInplace) { 779 // This test may fully fill the table and hardly depends on the underlying 780 // shape (e.g., meta table structure). Thus not testing overly large 781 // capacities. 782 std::vector<int> capacities_to_test = {4, 8, 16, 128, 1024}; 783 if (TS::IsRuntimeTest()) { 784 TS::WithInitialCapacities(capacities_to_test, [](TS& s) { 785 if (s.initial_capacity <= 8) { 786 // Add 3 elements, which will not cause a resize. Then delete the 787 // first key before rehasing. 788 789 AddMultiple(s, 3); 790 s.DeleteByKey(Key{"key0"}); 791 792 // We shouldn't have done a resize on deletion or addition: 793 s.CheckCounts(s.initial_capacity, 2, 1); 794 795 s.RehashInplace(); 796 797 s.CheckDataAtKey(Key{"key1"}, kIndexUnknown, "value1"); 798 s.CheckDataAtKey(Key{"key2"}, kIndexUnknown, "value2"); 799 s.CheckEnumerationOrder({"key1", "key2"}); 800 } else { 801 int count = 802 SwissNameDictionary::MaxUsableCapacity(s.initial_capacity) - 5; 803 AddMultiple(s, count); 804 805 s.DeleteByKey(Key{"key1"}); 806 s.DeleteByKey(Key{"key2"}); 807 s.DeleteByKey(Key{"key" + std::to_string(count - 1)}); 808 809 // We shouldn't have done a resize on deletion or addition: 810 s.CheckCounts(s.initial_capacity, count - 3, 3); 811 812 s.RehashInplace(); 813 814 std::vector<std::string> expected_enum_order; 815 for (int i = 0; i < count; ++i) { 816 if (i == 1 || i == 2 || i == count - 1) { 817 // These are the keys we deleted. 818 continue; 819 } 820 821 std::string key = "key" + std::to_string(i); 822 PropertyDetails d = 823 distinct_property_details[i % distinct_property_details.size()]; 824 s.CheckDataAtKey(Key{key}, kIndexUnknown, 825 "value" + std::to_string(i), d); 826 827 expected_enum_order.push_back(key); 828 } 829 830 s.CheckEnumerationOrder(expected_enum_order); 831 } 832 }); 833 } 834 } 835 MEMBER_TESTSharedSwissTableTests836 MEMBER_TEST(Shrink) { 837 if (TS::IsRuntimeTest()) { 838 TS::WithInitialCapacity(32, [&](TS& s) { 839 // Filling less than a forth of the table: 840 int count = 4; 841 842 AddMultiple(s, count); 843 844 s.Shrink(); 845 846 CheckMultiple(s, count, "key", "value", 0); 847 848 // Shrink doesn't shrink to fit, but only halves the capacity. 849 int expected_capacity = s.initial_capacity / 2; 850 s.CheckCounts(expected_capacity, 4, 0); 851 852 s.CheckEnumerationOrder({"key0", "key1", "key2", "key3"}); 853 s.VerifyHeap(); 854 }); 855 } 856 } 857 MEMBER_TESTSharedSwissTableTests858 MEMBER_TEST(ShrinkToInitial) { 859 // When shrinking, we never go below SwissNameDictionary::kInitialCapacity. 860 if (TS::IsRuntimeTest()) { 861 TS::WithInitialCapacity(8, [&](TS& s) { 862 s.Shrink(); 863 864 s.CheckCounts(SwissNameDictionary::kInitialCapacity, 0, 0); 865 }); 866 } 867 } 868 MEMBER_TESTSharedSwissTableTests869 MEMBER_TEST(ShrinkOnDelete) { 870 // TODO(v8:11330): Remove once CSA implementation has a fallback for 871 // non-SSSE3/AVX configurations. 872 if (!TestRunner::IsEnabled()) return; 873 TS::WithInitialCapacity(32, [](TS& s) { 874 // Adds key0 ... key9: 875 AddMultiple(s, 10); 876 877 // We remove some entries. Each time less than a forth of the table is 878 // used by present entries, it's shrunk to half. 879 880 s.DeleteByKey(Key{"key9"}); 881 s.DeleteByKey(Key{"key8"}); 882 883 s.CheckCounts(32, 8, 2); 884 885 s.DeleteByKey(Key{"key7"}); 886 887 // Deleted count is 0 after rehash. 888 s.CheckCounts(16, 7, 0); 889 }); 890 } 891 MEMBER_TESTSharedSwissTableTests892 MEMBER_TEST(Copy) { 893 // TODO(v8:11330) Disabling this for now until the real CSA testing has 894 // landed. 895 if (true) return; 896 897 // This test times out on sanitizer builds in CSA mode when testing the 898 // larger capacities. 899 // TODO(v8:11330) Revisit this once the actual CSA/Torque versions are run 900 // by the test suite, which will speed things up. 901 std::vector<int> capacities_to_test = 902 TS::IsRuntimeTest() ? interesting_initial_capacities 903 : capacities_for_slow_sanitizer_tests; 904 TS::WithInitialCapacities(capacities_to_test, [](TS& s) { 905 int fill = std::min( 906 1000, 907 // -2 due to the two manually added keys below. 908 SwissNameDictionary::MaxUsableCapacity(s.initial_capacity) - 2); 909 AddMultiple(s, fill); 910 911 // Occupy first and last bucket (another key may occuppy these already, 912 // but let's don't bother with that): 913 s.Add(Key{"first_bucket_key", FakeH1{kBigModulus}}); 914 s.Add(Key{"last_bucket_key", FakeH1{s.initial_capacity - 1}}); 915 916 // We shouldn't have caused a resize. 917 s.CheckCounts(s.initial_capacity); 918 919 // Creates a copy and compares it against the original. In order to check 920 // copying of large dictionary, need to check before deletion due to 921 // shrink-on-delete kicking in. 922 s.CheckCopy(); 923 924 // Let's delete a few entries, most notably the first and last two in enum 925 // order and the keys (potentially) occupying the first and last bucket. 926 s.DeleteByKey(Key{"key0"}); 927 if (fill > 1) { 928 s.DeleteByKey(Key{"key1"}); 929 } 930 s.DeleteByKey(Key{"first_bucket_key", FakeH1{kBigModulus}}); 931 s.DeleteByKey(Key{"last_bucket_key", FakeH1{s.initial_capacity - 1}}); 932 933 s.CheckCopy(); 934 }); 935 } 936 }; 937 938 } // namespace test_swiss_hash_table 939 } // namespace internal 940 } // namespace v8 941 942 #endif // V8_TEST_CCTEST_TEST_SWISS_HASH_TABLE_SHARED_TESTS_H_ 943