Upgrade V8 to version 4.9.385.28
https://chromium.googlesource.com/v8/v8/+/4.9.385.28
FPIIM-449
Change-Id: I4b2e74289d4bf3667f2f3dc8aa2e541f63e26eb4
diff --git a/test/cctest/test-identity-map.cc b/test/cctest/test-identity-map.cc
new file mode 100644
index 0000000..648508c
--- /dev/null
+++ b/test/cctest/test-identity-map.cc
@@ -0,0 +1,420 @@
+// 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.
+
+#include "src/v8.h"
+
+#include "src/identity-map.h"
+#include "src/zone.h"
+
+#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:
+ IdentityMap<void*> map;
+
+ IdentityMapTester() : map(heap(), main_zone()) {}
+
+ Heap* heap() { return isolate()->heap(); }
+ Isolate* isolate() { return main_isolate(); }
+
+ void TestGetFind(Handle<Object> key1, void* val1, Handle<Object> key2,
+ void* val2) {
+ CHECK_NULL(map.Find(key1));
+ CHECK_NULL(map.Find(key2));
+
+ // Set {key1} the first time.
+ void** entry = map.Get(key1);
+ CHECK_NOT_NULL(entry);
+ *entry = val1;
+
+ for (int i = 0; i < 3; i++) { // Get and find {key1} K times.
+ {
+ void** nentry = map.Get(key1);
+ CHECK_EQ(entry, nentry);
+ CHECK_EQ(val1, *nentry);
+ CHECK_NULL(map.Find(key2));
+ }
+ {
+ void** nentry = map.Find(key1);
+ CHECK_EQ(entry, nentry);
+ CHECK_EQ(val1, *nentry);
+ CHECK_NULL(map.Find(key2));
+ }
+ }
+
+ // Set {key2} the first time.
+ void** entry2 = map.Get(key2);
+ CHECK_NOT_NULL(entry2);
+ *entry2 = val2;
+
+ for (int i = 0; i < 3; i++) { // Get and find {key1} and {key2} K times.
+ {
+ void** nentry = map.Get(key2);
+ CHECK_EQ(entry2, nentry);
+ CHECK_EQ(val2, *nentry);
+ }
+ {
+ void** nentry = map.Find(key2);
+ CHECK_EQ(entry2, nentry);
+ CHECK_EQ(val2, *nentry);
+ }
+ {
+ void** nentry = map.Find(key1);
+ CHECK_EQ(val1, *nentry);
+ }
+ }
+ }
+
+ 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) {
+ for (int i = 0; i < map.size_; i++) {
+ if (map.keys_[i]->IsSmi()) {
+ map.keys_[i] = Smi::FromInt(Smi::cast(map.keys_[i])->value() + shift);
+ }
+ }
+ map.gc_counter_ = -1;
+ }
+
+ void CheckFind(Handle<Object> key, void* value) {
+ void** entry = map.Find(key);
+ CHECK_NOT_NULL(entry);
+ CHECK_EQ(value, *entry);
+ }
+
+ void CheckGet(Handle<Object> key, void* value) {
+ void** entry = map.Get(key);
+ CHECK_NOT_NULL(entry);
+ CHECK_EQ(value, *entry);
+ }
+
+ void PrintMap() {
+ PrintF("{\n");
+ for (int i = 0; i < map.size_; i++) {
+ PrintF(" %3d: %p => %p\n", i, reinterpret_cast<void*>(map.keys_[i]),
+ reinterpret_cast<void*>(map.values_[i]));
+ }
+ PrintF("}\n");
+ }
+
+ void Resize() { map.Resize(); }
+
+ 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)));
+ }
+}
+
+
+TEST(GetFind_smi_13) {
+ IdentityMapTester t;
+ t.TestGetFind(t.smi(13), t.isolate(), t.smi(17), t.heap());
+}
+
+
+TEST(GetFind_num_13) {
+ IdentityMapTester t;
+ t.TestGetFind(t.num(13.1), t.isolate(), t.num(17.1), t.heap());
+}
+
+
+TEST(GetFind_smi_17m) {
+ const int kInterval = 17;
+ const int kShift = 1099;
+ IdentityMapTester t;
+
+ for (int i = 1; i < 100; i += kInterval) {
+ t.map.Set(t.smi(i), reinterpret_cast<void*>(i + kShift));
+ }
+
+ 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.CheckGet(t.smi(i), reinterpret_cast<void*>(i + kShift));
+ }
+
+ 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);
+ }
+ }
+}
+
+
+TEST(GetFind_num_1000) {
+ const int kPrime = 137;
+ IdentityMapTester t;
+ int val1;
+ int val2;
+
+ for (int i = 0; i < 1000; i++) {
+ t.TestGetFind(t.smi(i * kPrime), &val1, t.smi(i * kPrime + 1), &val2);
+ }
+}
+
+
+TEST(GetFind_smi_gc) {
+ const int kKey = 33;
+ const int kShift = 1211;
+ IdentityMapTester t;
+
+ t.map.Set(t.smi(kKey), &t);
+ t.SimulateGCByIncrementingSmisBy(kShift);
+ t.CheckFind(t.smi(kKey + kShift), &t);
+ t.CheckGet(t.smi(kKey + kShift), &t);
+}
+
+
+TEST(GetFind_smi_gc2) {
+ int kKey1 = 1;
+ int kKey2 = 33;
+ const int kShift = 1211;
+ IdentityMapTester t;
+
+ t.map.Set(t.smi(kKey1), &kKey1);
+ t.map.Set(t.smi(kKey2), &kKey2);
+ t.SimulateGCByIncrementingSmisBy(kShift);
+ t.CheckFind(t.smi(kKey1 + kShift), &kKey1);
+ t.CheckGet(t.smi(kKey1 + kShift), &kKey1);
+ t.CheckFind(t.smi(kKey2 + kShift), &kKey2);
+ t.CheckGet(t.smi(kKey2 + kShift), &kKey2);
+}
+
+
+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) {
+ t.TestGetFind(t.smi(keys[i]), &keys[i], t.smi(keys[i + 1]), &keys[i + 1]);
+ }
+ // 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++) {
+ t.CheckGet(t.smi(keys[i] + kShift), &keys[i]);
+ }
+}
+
+
+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++) {
+ t.map.Set(t.smi(smi_keys[i]), &smi_keys[i]);
+ }
+ for (size_t i = 0; i < arraysize(num_keys); i++) {
+ t.map.Set(num_keys[i], &num_keys[i]);
+ }
+ // 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]);
+ t.CheckGet(t.smi(smi_keys[i] + kShift), &smi_keys[i]);
+ }
+
+ // 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]);
+ t.CheckGet(num_keys[i], &num_keys[i]);
+ }
+}
+
+
+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++) {
+ t.map.Set(t.smi(next), reinterpret_cast<void*>(next));
+ 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));
+ t.CheckGet(t.smi(next), reinterpret_cast<void*>(next));
+ 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++) {
+ t.map.Set(num_keys[i], &num_keys[i]);
+ }
+
+ // Do an explicit, real GC.
+ t.heap()->CollectGarbage(i::NEW_SPACE);
+
+ // 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]);
+ t.CheckGet(num_keys[i], &num_keys[i]);
+ }
+}
+
+
+TEST(CanonicalHandleScope) {
+ Isolate* isolate = CcTest::i_isolate();
+ Heap* heap = CcTest::heap();
+ HandleScope outer(isolate);
+ CanonicalHandleScope outer_canonical(isolate);
+
+ // Deduplicate smi handles.
+ List<Handle<Object> > smi_handles;
+ for (int i = 0; i < 100; i++) {
+ smi_handles.Add(Handle<Object>(Smi::FromInt(i), isolate));
+ }
+ Object** next_handle = isolate->handle_scope_data()->next;
+ 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.
+ Handle<String> empty_string(heap->empty_string());
+ Handle<Map> free_space_map(heap->free_space_map());
+ Handle<Symbol> uninitialized_symbol(heap->uninitialized_symbol());
+ 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;
+ Handle<HeapNumber> number2(*number1);
+ Handle<String> string2(*string1);
+ CHECK_EQ(number1.location(), number2.location());
+ CHECK_EQ(string1.location(), string2.location());
+ heap->CollectAllGarbage();
+ Handle<HeapNumber> number3(*number2);
+ Handle<String> string3(*string2);
+ 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);
+ Handle<HeapNumber> number4(*number1);
+ Handle<String> string4(*string1);
+ 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);
+ Handle<HeapNumber> number5(*number4);
+ Handle<String> string5(*string4);
+ CHECK_NE(number4.location(), number5.location());
+ CHECK_NE(string4.location(), string5.location());
+ CHECK_NE(number1.location(), number5.location());
+ CHECK_NE(string1.location(), string5.location());
+
+ Handle<HeapNumber> number6(*number1);
+ Handle<String> string6(*string1);
+ 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());
+ }
+}
+
+} // namespace internal
+} // namespace v8