test-identity-map.cc 26 KB
Newer Older
1 2 3 4
// Copyright 2015 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

5 6
#include <set>

7
#include "src/execution/isolate.h"
8
#include "src/heap/factory-inl.h"
9
#include "src/objects/heap-number-inl.h"
10
#include "src/utils/identity-map.h"
11
#include "src/objects/objects.h"
12
#include "src/zone/zone.h"
13 14 15 16 17 18 19 20 21
#include "test/cctest/cctest.h"

namespace v8 {
namespace internal {

// Helper for testing. A "friend" of the IdentityMapBase class, it is able to
// "move" objects to simulate GC for testing the internals of the map.
class IdentityMapTester : public HandleAndZoneScope {
 public:
22
  IdentityMap<void*, ZoneAllocationPolicy> map;
23

24
  IdentityMapTester() : map(heap(), ZoneAllocationPolicy(main_zone())) {}
25 26 27 28

  Heap* heap() { return isolate()->heap(); }
  Isolate* isolate() { return main_isolate(); }

29 30
  void TestInsertFind(Handle<Object> key1, void* val1, Handle<Object> key2,
                      void* val2) {
31 32 33 34
    CHECK_NULL(map.Find(key1));
    CHECK_NULL(map.Find(key2));

    // Set {key1} the first time.
35 36 37 38
    auto find_result = map.FindOrInsert(key1);
    CHECK_NOT_NULL(find_result.entry);
    CHECK(!find_result.already_exists);
    *find_result.entry = val1;
39 40 41

    for (int i = 0; i < 3; i++) {  // Get and find {key1} K times.
      {
42 43 44 45
        auto new_find_result = map.FindOrInsert(key1);
        CHECK(new_find_result.already_exists);
        CHECK_EQ(find_result.entry, new_find_result.entry);
        CHECK_EQ(val1, *new_find_result.entry);
46 47 48 49
        CHECK_NULL(map.Find(key2));
      }
      {
        void** nentry = map.Find(key1);
50
        CHECK_EQ(find_result.entry, nentry);
51 52 53 54 55 56
        CHECK_EQ(val1, *nentry);
        CHECK_NULL(map.Find(key2));
      }
    }

    // Set {key2} the first time.
57 58 59 60
    auto find_result2 = map.FindOrInsert(key2);
    CHECK_NOT_NULL(find_result2.entry);
    CHECK(!find_result2.already_exists);
    *find_result2.entry = val2;
61 62 63

    for (int i = 0; i < 3; i++) {  // Get and find {key1} and {key2} K times.
      {
64 65 66
        auto new_find_result = map.FindOrInsert(key2);
        CHECK_EQ(find_result2.entry, new_find_result.entry);
        CHECK_EQ(val2, *new_find_result.entry);
67 68 69
      }
      {
        void** nentry = map.Find(key2);
70
        CHECK_EQ(find_result2.entry, nentry);
71 72 73 74 75 76 77 78 79
        CHECK_EQ(val2, *nentry);
      }
      {
        void** nentry = map.Find(key1);
        CHECK_EQ(val1, *nentry);
      }
    }
  }

80 81 82 83 84 85
  void TestFindDelete(Handle<Object> key1, void* val1, Handle<Object> key2,
                      void* val2) {
    CHECK_NULL(map.Find(key1));
    CHECK_NULL(map.Find(key2));

    // Set {key1} and {key2} for the first time.
86 87 88 89 90 91 92 93
    auto find_result1 = map.FindOrInsert(key1);
    CHECK(!find_result1.already_exists);
    CHECK_NOT_NULL(find_result1.entry);
    *find_result1.entry = val1;
    auto find_result2 = map.FindOrInsert(key2);
    CHECK(!find_result1.already_exists);
    CHECK_NOT_NULL(find_result2.entry);
    *find_result2.entry = val2;
94 95 96 97 98 99 100 101 102 103 104 105 106

    for (int i = 0; i < 3; i++) {  // Find {key1} and {key2} 3 times.
      {
        void** nentry = map.Find(key2);
        CHECK_EQ(val2, *nentry);
      }
      {
        void** nentry = map.Find(key1);
        CHECK_EQ(val1, *nentry);
      }
    }

    // Delete {key1}
107 108
    void* deleted_entry_1;
    CHECK(map.Delete(key1, &deleted_entry_1));
109 110 111 112 113 114 115 116 117 118 119 120 121 122 123
    CHECK_NOT_NULL(deleted_entry_1);
    deleted_entry_1 = val1;

    for (int i = 0; i < 3; i++) {  // Find {key1} and not {key2} 3 times.
      {
        void** nentry = map.Find(key1);
        CHECK_NULL(nentry);
      }
      {
        void** nentry = map.Find(key2);
        CHECK_EQ(val2, *nentry);
      }
    }

    // Delete {key2}
124 125
    void* deleted_entry_2;
    CHECK(map.Delete(key2, &deleted_entry_2));
126 127 128 129 130 131 132 133 134 135 136 137 138 139 140
    CHECK_NOT_NULL(deleted_entry_2);
    deleted_entry_2 = val2;

    for (int i = 0; i < 3; i++) {  // Don't find {key1} and {key2} 3 times.
      {
        void** nentry = map.Find(key1);
        CHECK_NULL(nentry);
      }
      {
        void** nentry = map.Find(key2);
        CHECK_NULL(nentry);
      }
    }
  }

141 142 143 144 145 146 147 148 149
  Handle<Smi> smi(int value) {
    return Handle<Smi>(Smi::FromInt(value), isolate());
  }

  Handle<Object> num(double value) {
    return isolate()->factory()->NewNumber(value);
  }

  void SimulateGCByIncrementingSmisBy(int shift) {
150
    for (int i = 0; i < map.capacity_; i++) {
151 152 153
      Address key = map.keys_[i];
      if (!Internals::HasHeapObjectTag(key)) {
        map.keys_[i] = Internals::IntToSmi(Internals::SmiValue(key) + shift);
154 155 156 157 158 159 160 161 162 163 164
      }
    }
    map.gc_counter_ = -1;
  }

  void CheckFind(Handle<Object> key, void* value) {
    void** entry = map.Find(key);
    CHECK_NOT_NULL(entry);
    CHECK_EQ(value, *entry);
  }

165 166 167 168 169
  void CheckFindOrInsert(Handle<Object> key, void* value) {
    auto find_result = map.FindOrInsert(key);
    CHECK(find_result.already_exists);
    CHECK_NOT_NULL(find_result.entry);
    CHECK_EQ(value, *find_result.entry);
170 171
  }

172
  void CheckDelete(Handle<Object> key, void* value) {
173 174
    void* entry;
    CHECK(map.Delete(key, &entry));
175 176 177 178
    CHECK_NOT_NULL(entry);
    CHECK_EQ(value, entry);
  }

179 180
  void PrintMap() {
    PrintF("{\n");
181
    for (int i = 0; i < map.capacity_; i++) {
182 183 184 185 186 187
      PrintF("  %3d: %p => %p\n", i, reinterpret_cast<void*>(map.keys_[i]),
             reinterpret_cast<void*>(map.values_[i]));
    }
    PrintF("}\n");
  }

188
  void Resize() { map.Resize(map.capacity_ * 4); }
189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207

  void Rehash() { map.Rehash(); }
};

TEST(Find_smi_not_found) {
  IdentityMapTester t;
  for (int i = 0; i < 100; i++) {
    CHECK_NULL(t.map.Find(t.smi(i)));
  }
}


TEST(Find_num_not_found) {
  IdentityMapTester t;
  for (int i = 0; i < 100; i++) {
    CHECK_NULL(t.map.Find(t.num(i + 0.2)));
  }
}

208 209 210
TEST(Delete_smi_not_found) {
  IdentityMapTester t;
  for (int i = 0; i < 100; i++) {
211 212 213
    void* deleted_value = &t;
    CHECK(!t.map.Delete(t.smi(i), &deleted_value));
    CHECK_EQ(&t, deleted_value);
214 215 216 217 218 219
  }
}

TEST(Delete_num_not_found) {
  IdentityMapTester t;
  for (int i = 0; i < 100; i++) {
220 221 222
    void* deleted_value = &t;
    CHECK(!t.map.Delete(t.num(i + 0.2), &deleted_value));
    CHECK_EQ(&t, deleted_value);
223 224 225 226 227
  }
}

TEST(GetFind_smi_0) {
  IdentityMapTester t;
228
  t.TestInsertFind(t.smi(0), t.isolate(), t.smi(1), t.heap());
229
}
230 231 232

TEST(GetFind_smi_13) {
  IdentityMapTester t;
233
  t.TestInsertFind(t.smi(13), t.isolate(), t.smi(17), t.heap());
234 235 236 237
}

TEST(GetFind_num_13) {
  IdentityMapTester t;
238
  t.TestInsertFind(t.num(13.1), t.isolate(), t.num(17.1), t.heap());
239 240
}

241 242 243 244 245 246 247 248 249 250 251
TEST(Delete_smi_13) {
  IdentityMapTester t;
  t.TestFindDelete(t.smi(13), t.isolate(), t.smi(17), t.heap());
  CHECK(t.map.empty());
}

TEST(Delete_num_13) {
  IdentityMapTester t;
  t.TestFindDelete(t.num(13.1), t.isolate(), t.num(17.1), t.heap());
  CHECK(t.map.empty());
}
252 253 254 255 256 257 258

TEST(GetFind_smi_17m) {
  const int kInterval = 17;
  const int kShift = 1099;
  IdentityMapTester t;

  for (int i = 1; i < 100; i += kInterval) {
259
    t.map.Insert(t.smi(i), reinterpret_cast<void*>(i + kShift));
260 261 262 263 264 265 266
  }

  for (int i = 1; i < 100; i += kInterval) {
    t.CheckFind(t.smi(i), reinterpret_cast<void*>(i + kShift));
  }

  for (int i = 1; i < 100; i += kInterval) {
267
    t.CheckFindOrInsert(t.smi(i), reinterpret_cast<void*>(i + kShift));
268 269 270 271 272 273 274 275 276 277 278 279 280
  }

  for (int i = 1; i < 100; i++) {
    void** entry = t.map.Find(t.smi(i));
    if ((i % kInterval) != 1) {
      CHECK_NULL(entry);
    } else {
      CHECK_NOT_NULL(entry);
      CHECK_EQ(reinterpret_cast<void*>(i + kShift), *entry);
    }
  }
}

281 282 283 284 285 286
TEST(Delete_smi_17m) {
  const int kInterval = 17;
  const int kShift = 1099;
  IdentityMapTester t;

  for (int i = 1; i < 100; i += kInterval) {
287
    t.map.Insert(t.smi(i), reinterpret_cast<void*>(i + kShift));
288 289 290 291 292 293 294 295 296
  }

  for (int i = 1; i < 100; i += kInterval) {
    t.CheckFind(t.smi(i), reinterpret_cast<void*>(i + kShift));
  }

  for (int i = 1; i < 100; i += kInterval) {
    t.CheckDelete(t.smi(i), reinterpret_cast<void*>(i + kShift));
    for (int j = 1; j < 100; j += kInterval) {
297
      auto entry = t.map.Find(t.smi(j));
298 299 300 301 302 303 304 305 306
      if (j <= i) {
        CHECK_NULL(entry);
      } else {
        CHECK_NOT_NULL(entry);
        CHECK_EQ(reinterpret_cast<void*>(j + kShift), *entry);
      }
    }
  }
}
307 308 309 310 311 312 313

TEST(GetFind_num_1000) {
  const int kPrime = 137;
  IdentityMapTester t;
  int val1;
  int val2;

314
  for (int i = 0; i < 1000; i++) {
315
    t.TestInsertFind(t.smi(i * kPrime), &val1, t.smi(i * kPrime + 1), &val2);
316 317 318
  }
}

319 320 321 322 323
TEST(Delete_num_1000) {
  const int kPrime = 137;
  IdentityMapTester t;

  for (int i = 0; i < 1000; i++) {
324
    t.map.Insert(t.smi(i * kPrime), reinterpret_cast<void*>(i * kPrime));
325 326 327 328
  }

  // Delete every second value in reverse.
  for (int i = 999; i >= 0; i -= 2) {
329 330
    void* entry;
    CHECK(t.map.Delete(t.smi(i * kPrime), &entry));
331 332 333 334
    CHECK_EQ(reinterpret_cast<void*>(i * kPrime), entry);
  }

  for (int i = 0; i < 1000; i++) {
335
    auto entry = t.map.Find(t.smi(i * kPrime));
336 337 338 339 340 341 342 343 344 345
    if (i % 2) {
      CHECK_NULL(entry);
    } else {
      CHECK_NOT_NULL(entry);
      CHECK_EQ(reinterpret_cast<void*>(i * kPrime), *entry);
    }
  }

  // Delete the rest.
  for (int i = 0; i < 1000; i += 2) {
346 347
    void* entry;
    CHECK(t.map.Delete(t.smi(i * kPrime), &entry));
348 349 350 351
    CHECK_EQ(reinterpret_cast<void*>(i * kPrime), entry);
  }

  for (int i = 0; i < 1000; i++) {
352
    auto entry = t.map.Find(t.smi(i * kPrime));
353 354 355
    CHECK_NULL(entry);
  }
}
356 357 358 359 360 361

TEST(GetFind_smi_gc) {
  const int kKey = 33;
  const int kShift = 1211;
  IdentityMapTester t;

362
  t.map.Insert(t.smi(kKey), &t);
363 364
  t.SimulateGCByIncrementingSmisBy(kShift);
  t.CheckFind(t.smi(kKey + kShift), &t);
365
  t.CheckFindOrInsert(t.smi(kKey + kShift), &t);
366 367
}

368 369 370 371 372
TEST(Delete_smi_gc) {
  const int kKey = 33;
  const int kShift = 1211;
  IdentityMapTester t;

373
  t.map.Insert(t.smi(kKey), &t);
374 375 376
  t.SimulateGCByIncrementingSmisBy(kShift);
  t.CheckDelete(t.smi(kKey + kShift), &t);
}
377 378 379 380 381 382 383

TEST(GetFind_smi_gc2) {
  int kKey1 = 1;
  int kKey2 = 33;
  const int kShift = 1211;
  IdentityMapTester t;

384 385
  t.map.Insert(t.smi(kKey1), &kKey1);
  t.map.Insert(t.smi(kKey2), &kKey2);
386 387
  t.SimulateGCByIncrementingSmisBy(kShift);
  t.CheckFind(t.smi(kKey1 + kShift), &kKey1);
388
  t.CheckFindOrInsert(t.smi(kKey1 + kShift), &kKey1);
389
  t.CheckFind(t.smi(kKey2 + kShift), &kKey2);
390
  t.CheckFindOrInsert(t.smi(kKey2 + kShift), &kKey2);
391 392
}

393 394 395 396 397 398
TEST(Delete_smi_gc2) {
  int kKey1 = 1;
  int kKey2 = 33;
  const int kShift = 1211;
  IdentityMapTester t;

399 400
  t.map.Insert(t.smi(kKey1), &kKey1);
  t.map.Insert(t.smi(kKey2), &kKey2);
401 402 403 404
  t.SimulateGCByIncrementingSmisBy(kShift);
  t.CheckDelete(t.smi(kKey1 + kShift), &kKey1);
  t.CheckDelete(t.smi(kKey2 + kShift), &kKey2);
}
405 406 407 408 409 410 411 412

TEST(GetFind_smi_gc_n) {
  const int kShift = 12011;
  IdentityMapTester t;
  int keys[12] = {1,      2,      7,      8,      15,      23,
                  1 + 32, 2 + 32, 7 + 32, 8 + 32, 15 + 32, 23 + 32};
  // Initialize the map first.
  for (size_t i = 0; i < arraysize(keys); i += 2) {
413 414
    t.TestInsertFind(t.smi(keys[i]), &keys[i], t.smi(keys[i + 1]),
                     &keys[i + 1]);
415 416 417 418 419 420 421 422 423 424 425 426 427
  }
  // Check the above initialization.
  for (size_t i = 0; i < arraysize(keys); i++) {
    t.CheckFind(t.smi(keys[i]), &keys[i]);
  }
  // Simulate a GC by "moving" the smis in the internal keys array.
  t.SimulateGCByIncrementingSmisBy(kShift);
  // Check that searching for the incremented smis finds the same values.
  for (size_t i = 0; i < arraysize(keys); i++) {
    t.CheckFind(t.smi(keys[i] + kShift), &keys[i]);
  }
  // Check that searching for the incremented smis gets the same values.
  for (size_t i = 0; i < arraysize(keys); i++) {
428
    t.CheckFindOrInsert(t.smi(keys[i] + kShift), &keys[i]);
429 430 431
  }
}

432 433 434 435 436 437 438
TEST(Delete_smi_gc_n) {
  const int kShift = 12011;
  IdentityMapTester t;
  int keys[12] = {1,      2,      7,      8,      15,      23,
                  1 + 32, 2 + 32, 7 + 32, 8 + 32, 15 + 32, 23 + 32};
  // Initialize the map first.
  for (size_t i = 0; i < arraysize(keys); i++) {
439
    t.map.Insert(t.smi(keys[i]), &keys[i]);
440 441 442 443 444 445 446 447
  }
  // Simulate a GC by "moving" the smis in the internal keys array.
  t.SimulateGCByIncrementingSmisBy(kShift);
  // Check that deleting for the incremented smis finds the same values.
  for (size_t i = 0; i < arraysize(keys); i++) {
    t.CheckDelete(t.smi(keys[i] + kShift), &keys[i]);
  }
}
448 449 450 451 452 453 454 455 456 457

TEST(GetFind_smi_num_gc_n) {
  const int kShift = 12019;
  IdentityMapTester t;
  int smi_keys[] = {1, 2, 7, 15, 23};
  Handle<Object> num_keys[] = {t.num(1.1), t.num(2.2), t.num(3.3), t.num(4.4),
                               t.num(5.5), t.num(6.6), t.num(7.7), t.num(8.8),
                               t.num(9.9), t.num(10.1)};
  // Initialize the map first.
  for (size_t i = 0; i < arraysize(smi_keys); i++) {
458
    t.map.Insert(t.smi(smi_keys[i]), &smi_keys[i]);
459 460
  }
  for (size_t i = 0; i < arraysize(num_keys); i++) {
461
    t.map.Insert(num_keys[i], &num_keys[i]);
462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477
  }
  // Check the above initialization.
  for (size_t i = 0; i < arraysize(smi_keys); i++) {
    t.CheckFind(t.smi(smi_keys[i]), &smi_keys[i]);
  }
  for (size_t i = 0; i < arraysize(num_keys); i++) {
    t.CheckFind(num_keys[i], &num_keys[i]);
  }

  // Simulate a GC by moving SMIs.
  // Ironically the SMIs "move", but the heap numbers don't!
  t.SimulateGCByIncrementingSmisBy(kShift);

  // Check that searching for the incremented smis finds the same values.
  for (size_t i = 0; i < arraysize(smi_keys); i++) {
    t.CheckFind(t.smi(smi_keys[i] + kShift), &smi_keys[i]);
478
    t.CheckFindOrInsert(t.smi(smi_keys[i] + kShift), &smi_keys[i]);
479 480 481 482 483
  }

  // Check that searching for the numbers finds the same values.
  for (size_t i = 0; i < arraysize(num_keys); i++) {
    t.CheckFind(num_keys[i], &num_keys[i]);
484
    t.CheckFindOrInsert(num_keys[i], &num_keys[i]);
485 486 487
  }
}

488 489 490 491 492 493 494 495 496
TEST(Delete_smi_num_gc_n) {
  const int kShift = 12019;
  IdentityMapTester t;
  int smi_keys[] = {1, 2, 7, 15, 23};
  Handle<Object> num_keys[] = {t.num(1.1), t.num(2.2), t.num(3.3), t.num(4.4),
                               t.num(5.5), t.num(6.6), t.num(7.7), t.num(8.8),
                               t.num(9.9), t.num(10.1)};
  // Initialize the map first.
  for (size_t i = 0; i < arraysize(smi_keys); i++) {
497
    t.map.Insert(t.smi(smi_keys[i]), &smi_keys[i]);
498 499
  }
  for (size_t i = 0; i < arraysize(num_keys); i++) {
500
    t.map.Insert(num_keys[i], &num_keys[i]);
501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523
  }

  // Simulate a GC by moving SMIs.
  // Ironically the SMIs "move", but the heap numbers don't!
  t.SimulateGCByIncrementingSmisBy(kShift);

  // Check that deleting for the incremented smis finds the same values.
  for (size_t i = 0; i < arraysize(smi_keys); i++) {
    t.CheckDelete(t.smi(smi_keys[i] + kShift), &smi_keys[i]);
  }

  // Check that deleting the numbers finds the same values.
  for (size_t i = 0; i < arraysize(num_keys); i++) {
    t.CheckDelete(num_keys[i], &num_keys[i]);
  }
}

TEST(Delete_smi_resizes) {
  const int kKeyCount = 1024;
  const int kValueOffset = 27;
  IdentityMapTester t;

  // Insert one element to initialize map.
524
  t.map.Insert(t.smi(0), reinterpret_cast<void*>(kValueOffset));
525 526 527 528 529 530

  int initial_capacity = t.map.capacity();
  CHECK_LT(initial_capacity, kKeyCount);

  // Insert another kKeyCount - 1 keys.
  for (int i = 1; i < kKeyCount; i++) {
531
    t.map.Insert(t.smi(i), reinterpret_cast<void*>(i + kValueOffset));
532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554
  }

  // Check capacity increased.
  CHECK_GT(t.map.capacity(), initial_capacity);
  CHECK_GE(t.map.capacity(), kKeyCount);

  // Delete all the keys.
  for (int i = 0; i < kKeyCount; i++) {
    t.CheckDelete(t.smi(i), reinterpret_cast<void*>(i + kValueOffset));
  }

  // Should resize back to initial capacity.
  CHECK_EQ(t.map.capacity(), initial_capacity);
}

TEST(Iterator_smi_num) {
  IdentityMapTester t;
  int smi_keys[] = {1, 2, 7, 15, 23};
  Handle<Object> num_keys[] = {t.num(1.1), t.num(2.2), t.num(3.3), t.num(4.4),
                               t.num(5.5), t.num(6.6), t.num(7.7), t.num(8.8),
                               t.num(9.9), t.num(10.1)};
  // Initialize the map.
  for (size_t i = 0; i < arraysize(smi_keys); i++) {
555
    t.map.Insert(t.smi(smi_keys[i]), reinterpret_cast<void*>(i));
556 557
  }
  for (size_t i = 0; i < arraysize(num_keys); i++) {
558
    t.map.Insert(num_keys[i], reinterpret_cast<void*>(i + 5));
559 560
  }

561
  // Check iterator sees all values once.
562 563 564 565
  std::set<intptr_t> seen;
  {
    IdentityMap<void*, ZoneAllocationPolicy>::IteratableScope it_scope(&t.map);
    for (auto it = it_scope.begin(); it != it_scope.end(); ++it) {
566
      CHECK(seen.find(reinterpret_cast<intptr_t>(**it)) == seen.end());
567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583
      seen.insert(reinterpret_cast<intptr_t>(**it));
    }
  }
  for (intptr_t i = 0; i < 15; i++) {
    CHECK(seen.find(i) != seen.end());
  }
}

TEST(Iterator_smi_num_gc) {
  const int kShift = 16039;
  IdentityMapTester t;
  int smi_keys[] = {1, 2, 7, 15, 23};
  Handle<Object> num_keys[] = {t.num(1.1), t.num(2.2), t.num(3.3), t.num(4.4),
                               t.num(5.5), t.num(6.6), t.num(7.7), t.num(8.8),
                               t.num(9.9), t.num(10.1)};
  // Initialize the map.
  for (size_t i = 0; i < arraysize(smi_keys); i++) {
584
    t.map.Insert(t.smi(smi_keys[i]), reinterpret_cast<void*>(i));
585 586
  }
  for (size_t i = 0; i < arraysize(num_keys); i++) {
587
    t.map.Insert(num_keys[i], reinterpret_cast<void*>(i + 5));
588 589 590 591 592 593 594 595 596 597
  }

  // Simulate GC by moving the SMIs.
  t.SimulateGCByIncrementingSmisBy(kShift);

  // Check iterator sees all values.
  std::set<intptr_t> seen;
  {
    IdentityMap<void*, ZoneAllocationPolicy>::IteratableScope it_scope(&t.map);
    for (auto it = it_scope.begin(); it != it_scope.end(); ++it) {
598
      CHECK(seen.find(reinterpret_cast<intptr_t>(**it)) == seen.end());
599 600 601 602 603 604 605 606
      seen.insert(reinterpret_cast<intptr_t>(**it));
    }
  }
  for (intptr_t i = 0; i < 15; i++) {
    CHECK(seen.find(i) != seen.end());
  }
}

607 608 609
void IterateCollisionTest(int stride) {
  for (int load = 15; load <= 120; load = load * 2) {
    IdentityMapTester t;
610

611 612 613 614
    {  // Add entries to the map.
      HandleScope scope(t.isolate());
      int next = 1;
      for (int i = 0; i < load; i++) {
615
        t.map.Insert(t.smi(next), reinterpret_cast<void*>(next));
616 617
        t.CheckFind(t.smi(next), reinterpret_cast<void*>(next));
        next = next + stride;
618 619
      }
    }
620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636
    // Iterate through the map and check we see all elements only once.
    std::set<intptr_t> seen;
    {
      IdentityMap<void*, ZoneAllocationPolicy>::IteratableScope it_scope(
          &t.map);
      for (auto it = it_scope.begin(); it != it_scope.end(); ++it) {
        CHECK(seen.find(reinterpret_cast<intptr_t>(**it)) == seen.end());
        seen.insert(reinterpret_cast<intptr_t>(**it));
      }
    }
    // Check get and find on map.
    {
      HandleScope scope(t.isolate());
      int next = 1;
      for (int i = 0; i < load; i++) {
        CHECK(seen.find(next) != seen.end());
        t.CheckFind(t.smi(next), reinterpret_cast<void*>(next));
637
        t.CheckFindOrInsert(t.smi(next), reinterpret_cast<void*>(next));
638 639
        next = next + stride;
      }
640 641 642
    }
  }
}
643

644 645 646 647 648 649
TEST(IterateCollisions_1) { IterateCollisionTest(1); }
TEST(IterateCollisions_2) { IterateCollisionTest(2); }
TEST(IterateCollisions_3) { IterateCollisionTest(3); }
TEST(IterateCollisions_5) { IterateCollisionTest(5); }
TEST(IterateCollisions_7) { IterateCollisionTest(7); }

650 651 652 653 654 655 656 657
void CollisionTest(int stride, bool rehash = false, bool resize = false) {
  for (int load = 15; load <= 120; load = load * 2) {
    IdentityMapTester t;

    {  // Add entries to the map.
      HandleScope scope(t.isolate());
      int next = 1;
      for (int i = 0; i < load; i++) {
658
        t.map.Insert(t.smi(next), reinterpret_cast<void*>(next));
659 660 661 662 663 664 665 666 667 668 669
        t.CheckFind(t.smi(next), reinterpret_cast<void*>(next));
        next = next + stride;
      }
    }
    if (resize) t.Resize();  // Explicit resize (internal method).
    if (rehash) t.Rehash();  // Explicit rehash (internal method).
    {                        // Check find and get.
      HandleScope scope(t.isolate());
      int next = 1;
      for (int i = 0; i < load; i++) {
        t.CheckFind(t.smi(next), reinterpret_cast<void*>(next));
670
        t.CheckFindOrInsert(t.smi(next), reinterpret_cast<void*>(next));
671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692
        next = next + stride;
      }
    }
  }
}

TEST(Collisions_1) { CollisionTest(1); }
TEST(Collisions_2) { CollisionTest(2); }
TEST(Collisions_3) { CollisionTest(3); }
TEST(Collisions_5) { CollisionTest(5); }
TEST(Collisions_7) { CollisionTest(7); }
TEST(Resize) { CollisionTest(9, false, true); }
TEST(Rehash) { CollisionTest(11, true, false); }

TEST(ExplicitGC) {
  IdentityMapTester t;
  Handle<Object> num_keys[] = {t.num(2.1), t.num(2.4), t.num(3.3), t.num(4.3),
                               t.num(7.5), t.num(6.4), t.num(7.3), t.num(8.3),
                               t.num(8.9), t.num(10.4)};

  // Insert some objects that should be in new space.
  for (size_t i = 0; i < arraysize(num_keys); i++) {
693
    t.map.Insert(num_keys[i], &num_keys[i]);
694 695 696
  }

  // Do an explicit, real GC.
697
  t.heap()->CollectGarbage(i::NEW_SPACE, i::GarbageCollectionReason::kTesting);
698 699 700 701

  // Check that searching for the numbers finds the same values.
  for (size_t i = 0; i < arraysize(num_keys); i++) {
    t.CheckFind(num_keys[i], &num_keys[i]);
702
    t.CheckFindOrInsert(num_keys[i], &num_keys[i]);
703 704
  }
}
705

706 707 708 709 710 711 712
TEST(CanonicalHandleScope) {
  Isolate* isolate = CcTest::i_isolate();
  Heap* heap = CcTest::heap();
  HandleScope outer(isolate);
  CanonicalHandleScope outer_canonical(isolate);

  // Deduplicate smi handles.
713
  std::vector<Handle<Object>> smi_handles;
714
  for (int i = 0; i < 100; i++) {
715
    smi_handles.push_back(Handle<Object>(Smi::FromInt(i), isolate));
716
  }
717
  Address* next_handle = isolate->handle_scope_data()->next;
718 719 720 721 722 723 724 725 726
  for (int i = 0; i < 100; i++) {
    Handle<Object> new_smi = Handle<Object>(Smi::FromInt(i), isolate);
    Handle<Object> old_smi = smi_handles[i];
    CHECK_EQ(new_smi.location(), old_smi.location());
  }
  // Check that no new handles have been allocated.
  CHECK_EQ(next_handle, isolate->handle_scope_data()->next);

  // Deduplicate root list items.
727 728 729 730
  Handle<String> empty_string(ReadOnlyRoots(heap).empty_string(), isolate);
  Handle<Map> free_space_map(ReadOnlyRoots(heap).free_space_map(), isolate);
  Handle<Symbol> uninitialized_symbol(
      ReadOnlyRoots(heap).uninitialized_symbol(), isolate);
731 732 733 734 735 736 737 738 739 740 741 742 743 744
  CHECK_EQ(isolate->factory()->empty_string().location(),
           empty_string.location());
  CHECK_EQ(isolate->factory()->free_space_map().location(),
           free_space_map.location());
  CHECK_EQ(isolate->factory()->uninitialized_symbol().location(),
           uninitialized_symbol.location());
  // Check that no new handles have been allocated.
  CHECK_EQ(next_handle, isolate->handle_scope_data()->next);

  // Test ordinary heap objects.
  Handle<HeapNumber> number1 = isolate->factory()->NewHeapNumber(3.3);
  Handle<String> string1 =
      isolate->factory()->NewStringFromAsciiChecked("test");
  next_handle = isolate->handle_scope_data()->next;
745 746
  Handle<HeapNumber> number2(*number1, isolate);
  Handle<String> string2(*string1, isolate);
747 748
  CHECK_EQ(number1.location(), number2.location());
  CHECK_EQ(string1.location(), string2.location());
749
  CcTest::CollectAllGarbage();
750 751
  Handle<HeapNumber> number3(*number2, isolate);
  Handle<String> string3(*string2, isolate);
752 753 754 755 756 757 758 759
  CHECK_EQ(number1.location(), number3.location());
  CHECK_EQ(string1.location(), string3.location());
  // Check that no new handles have been allocated.
  CHECK_EQ(next_handle, isolate->handle_scope_data()->next);

  // Inner handle scope do not create canonical handles.
  {
    HandleScope inner(isolate);
760 761
    Handle<HeapNumber> number4(*number1, isolate);
    Handle<String> string4(*string1, isolate);
762 763 764 765 766 767
    CHECK_NE(number1.location(), number4.location());
    CHECK_NE(string1.location(), string4.location());

    // Nested canonical scope does not conflict with outer canonical scope,
    // but does not canonicalize across scopes.
    CanonicalHandleScope inner_canonical(isolate);
768 769
    Handle<HeapNumber> number5(*number4, isolate);
    Handle<String> string5(*string4, isolate);
770 771 772 773 774
    CHECK_NE(number4.location(), number5.location());
    CHECK_NE(string4.location(), string5.location());
    CHECK_NE(number1.location(), number5.location());
    CHECK_NE(string1.location(), string5.location());

775 776
    Handle<HeapNumber> number6(*number1, isolate);
    Handle<String> string6(*string1, isolate);
777 778 779 780 781 782 783 784 785
    CHECK_NE(number4.location(), number6.location());
    CHECK_NE(string4.location(), string6.location());
    CHECK_NE(number1.location(), number6.location());
    CHECK_NE(string1.location(), string6.location());
    CHECK_EQ(number5.location(), number6.location());
    CHECK_EQ(string5.location(), string6.location());
  }
}

786
TEST(GCShortCutting) {
787
  if (FLAG_single_generation) return;
788
  ManualGCScope manual_gc_scope;
789 790 791 792 793 794 795 796 797 798 799
  IdentityMapTester t;
  Isolate* isolate = CcTest::i_isolate();
  Factory* factory = isolate->factory();
  const int kDummyValue = 0;

  for (int i = 0; i < 16; i++) {
    // Insert a varying number of Smis as padding to ensure some tests straddle
    // a boundary where the thin string short cutting will cause size_ to be
    // greater to capacity_ if not corrected by IdentityMap
    // (see crbug.com/704132).
    for (int j = 0; j < i; j++) {
800
      t.map.Insert(t.smi(j), reinterpret_cast<void*>(kDummyValue));
801 802 803 804 805 806
    }

    Handle<String> thin_string =
        factory->NewStringFromAsciiChecked("thin_string");
    Handle<String> internalized_string =
        factory->InternalizeString(thin_string);
807
    DCHECK(thin_string->IsThinString());
808 809 810
    DCHECK_NE(*thin_string, *internalized_string);

    // Insert both keys into the map.
811 812
    t.map.Insert(thin_string, &thin_string);
    t.map.Insert(internalized_string, &internalized_string);
813 814 815 816 817

    // Do an explicit, real GC, this should short-cut the thin string to point
    // to the internalized string.
    t.heap()->CollectGarbage(i::NEW_SPACE,
                             i::GarbageCollectionReason::kTesting);
818
    DCHECK_IMPLIES(!FLAG_optimize_for_size,
819 820 821
                   *thin_string == *internalized_string);

    // Check that getting the object points to one of the handles.
822
    void** thin_string_entry = t.map.Find(thin_string);
823 824
    CHECK(*thin_string_entry == &thin_string ||
          *thin_string_entry == &internalized_string);
825
    void** internalized_string_entry = t.map.Find(internalized_string);
826 827 828 829 830
    CHECK(*internalized_string_entry == &thin_string ||
          *internalized_string_entry == &internalized_string);

    // Trigger resize.
    for (int j = 0; j < 16; j++) {
831
      t.map.Insert(t.smi(j + 16), reinterpret_cast<void*>(kDummyValue));
832 833 834 835 836
    }
    t.map.Clear();
  }
}

837 838
}  // namespace internal
}  // namespace v8