1 // Copyright 2015 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 #include "src/v8.h" 6 7 #include "src/identity-map.h" 8 #include "src/zone.h" 9 10 #include "test/cctest/cctest.h" 11 12 namespace v8 { 13 namespace internal { 14 15 // Helper for testing. A "friend" of the IdentityMapBase class, it is able to 16 // "move" objects to simulate GC for testing the internals of the map. 17 class IdentityMapTester : public HandleAndZoneScope { 18 public: 19 IdentityMap<void*> map; 20 21 IdentityMapTester() : map(heap(), main_zone()) {} 22 23 Heap* heap() { return isolate()->heap(); } 24 Isolate* isolate() { return main_isolate(); } 25 26 void TestGetFind(Handle<Object> key1, void* val1, Handle<Object> key2, 27 void* val2) { 28 CHECK_NULL(map.Find(key1)); 29 CHECK_NULL(map.Find(key2)); 30 31 // Set {key1} the first time. 32 void** entry = map.Get(key1); 33 CHECK_NOT_NULL(entry); 34 *entry = val1; 35 36 for (int i = 0; i < 3; i++) { // Get and find {key1} K times. 37 { 38 void** nentry = map.Get(key1); 39 CHECK_EQ(entry, nentry); 40 CHECK_EQ(val1, *nentry); 41 CHECK_NULL(map.Find(key2)); 42 } 43 { 44 void** nentry = map.Find(key1); 45 CHECK_EQ(entry, nentry); 46 CHECK_EQ(val1, *nentry); 47 CHECK_NULL(map.Find(key2)); 48 } 49 } 50 51 // Set {key2} the first time. 52 void** entry2 = map.Get(key2); 53 CHECK_NOT_NULL(entry2); 54 *entry2 = val2; 55 56 for (int i = 0; i < 3; i++) { // Get and find {key1} and {key2} K times. 57 { 58 void** nentry = map.Get(key2); 59 CHECK_EQ(entry2, nentry); 60 CHECK_EQ(val2, *nentry); 61 } 62 { 63 void** nentry = map.Find(key2); 64 CHECK_EQ(entry2, nentry); 65 CHECK_EQ(val2, *nentry); 66 } 67 { 68 void** nentry = map.Find(key1); 69 CHECK_EQ(val1, *nentry); 70 } 71 } 72 } 73 74 Handle<Smi> smi(int value) { 75 return Handle<Smi>(Smi::FromInt(value), isolate()); 76 } 77 78 Handle<Object> num(double value) { 79 return isolate()->factory()->NewNumber(value); 80 } 81 82 void SimulateGCByIncrementingSmisBy(int shift) { 83 for (int i = 0; i < map.size_; i++) { 84 if (map.keys_[i]->IsSmi()) { 85 map.keys_[i] = Smi::FromInt(Smi::cast(map.keys_[i])->value() + shift); 86 } 87 } 88 map.gc_counter_ = -1; 89 } 90 91 void CheckFind(Handle<Object> key, void* value) { 92 void** entry = map.Find(key); 93 CHECK_NOT_NULL(entry); 94 CHECK_EQ(value, *entry); 95 } 96 97 void CheckGet(Handle<Object> key, void* value) { 98 void** entry = map.Get(key); 99 CHECK_NOT_NULL(entry); 100 CHECK_EQ(value, *entry); 101 } 102 103 void PrintMap() { 104 PrintF("{\n"); 105 for (int i = 0; i < map.size_; i++) { 106 PrintF(" %3d: %p => %p\n", i, reinterpret_cast<void*>(map.keys_[i]), 107 reinterpret_cast<void*>(map.values_[i])); 108 } 109 PrintF("}\n"); 110 } 111 112 void Resize() { map.Resize(); } 113 114 void Rehash() { map.Rehash(); } 115 }; 116 117 118 TEST(Find_smi_not_found) { 119 IdentityMapTester t; 120 for (int i = 0; i < 100; i++) { 121 CHECK_NULL(t.map.Find(t.smi(i))); 122 } 123 } 124 125 126 TEST(Find_num_not_found) { 127 IdentityMapTester t; 128 for (int i = 0; i < 100; i++) { 129 CHECK_NULL(t.map.Find(t.num(i + 0.2))); 130 } 131 } 132 133 134 TEST(GetFind_smi_13) { 135 IdentityMapTester t; 136 t.TestGetFind(t.smi(13), t.isolate(), t.smi(17), t.heap()); 137 } 138 139 140 TEST(GetFind_num_13) { 141 IdentityMapTester t; 142 t.TestGetFind(t.num(13.1), t.isolate(), t.num(17.1), t.heap()); 143 } 144 145 146 TEST(GetFind_smi_17m) { 147 const int kInterval = 17; 148 const int kShift = 1099; 149 IdentityMapTester t; 150 151 for (int i = 1; i < 100; i += kInterval) { 152 t.map.Set(t.smi(i), reinterpret_cast<void*>(i + kShift)); 153 } 154 155 for (int i = 1; i < 100; i += kInterval) { 156 t.CheckFind(t.smi(i), reinterpret_cast<void*>(i + kShift)); 157 } 158 159 for (int i = 1; i < 100; i += kInterval) { 160 t.CheckGet(t.smi(i), reinterpret_cast<void*>(i + kShift)); 161 } 162 163 for (int i = 1; i < 100; i++) { 164 void** entry = t.map.Find(t.smi(i)); 165 if ((i % kInterval) != 1) { 166 CHECK_NULL(entry); 167 } else { 168 CHECK_NOT_NULL(entry); 169 CHECK_EQ(reinterpret_cast<void*>(i + kShift), *entry); 170 } 171 } 172 } 173 174 175 TEST(GetFind_num_1000) { 176 const int kPrime = 137; 177 IdentityMapTester t; 178 int val1; 179 int val2; 180 181 for (int i = 0; i < 1000; i++) { 182 t.TestGetFind(t.smi(i * kPrime), &val1, t.smi(i * kPrime + 1), &val2); 183 } 184 } 185 186 187 TEST(GetFind_smi_gc) { 188 const int kKey = 33; 189 const int kShift = 1211; 190 IdentityMapTester t; 191 192 t.map.Set(t.smi(kKey), &t); 193 t.SimulateGCByIncrementingSmisBy(kShift); 194 t.CheckFind(t.smi(kKey + kShift), &t); 195 t.CheckGet(t.smi(kKey + kShift), &t); 196 } 197 198 199 TEST(GetFind_smi_gc2) { 200 int kKey1 = 1; 201 int kKey2 = 33; 202 const int kShift = 1211; 203 IdentityMapTester t; 204 205 t.map.Set(t.smi(kKey1), &kKey1); 206 t.map.Set(t.smi(kKey2), &kKey2); 207 t.SimulateGCByIncrementingSmisBy(kShift); 208 t.CheckFind(t.smi(kKey1 + kShift), &kKey1); 209 t.CheckGet(t.smi(kKey1 + kShift), &kKey1); 210 t.CheckFind(t.smi(kKey2 + kShift), &kKey2); 211 t.CheckGet(t.smi(kKey2 + kShift), &kKey2); 212 } 213 214 215 TEST(GetFind_smi_gc_n) { 216 const int kShift = 12011; 217 IdentityMapTester t; 218 int keys[12] = {1, 2, 7, 8, 15, 23, 219 1 + 32, 2 + 32, 7 + 32, 8 + 32, 15 + 32, 23 + 32}; 220 // Initialize the map first. 221 for (size_t i = 0; i < arraysize(keys); i += 2) { 222 t.TestGetFind(t.smi(keys[i]), &keys[i], t.smi(keys[i + 1]), &keys[i + 1]); 223 } 224 // Check the above initialization. 225 for (size_t i = 0; i < arraysize(keys); i++) { 226 t.CheckFind(t.smi(keys[i]), &keys[i]); 227 } 228 // Simulate a GC by "moving" the smis in the internal keys array. 229 t.SimulateGCByIncrementingSmisBy(kShift); 230 // Check that searching for the incremented smis finds the same values. 231 for (size_t i = 0; i < arraysize(keys); i++) { 232 t.CheckFind(t.smi(keys[i] + kShift), &keys[i]); 233 } 234 // Check that searching for the incremented smis gets the same values. 235 for (size_t i = 0; i < arraysize(keys); i++) { 236 t.CheckGet(t.smi(keys[i] + kShift), &keys[i]); 237 } 238 } 239 240 241 TEST(GetFind_smi_num_gc_n) { 242 const int kShift = 12019; 243 IdentityMapTester t; 244 int smi_keys[] = {1, 2, 7, 15, 23}; 245 Handle<Object> num_keys[] = {t.num(1.1), t.num(2.2), t.num(3.3), t.num(4.4), 246 t.num(5.5), t.num(6.6), t.num(7.7), t.num(8.8), 247 t.num(9.9), t.num(10.1)}; 248 // Initialize the map first. 249 for (size_t i = 0; i < arraysize(smi_keys); i++) { 250 t.map.Set(t.smi(smi_keys[i]), &smi_keys[i]); 251 } 252 for (size_t i = 0; i < arraysize(num_keys); i++) { 253 t.map.Set(num_keys[i], &num_keys[i]); 254 } 255 // Check the above initialization. 256 for (size_t i = 0; i < arraysize(smi_keys); i++) { 257 t.CheckFind(t.smi(smi_keys[i]), &smi_keys[i]); 258 } 259 for (size_t i = 0; i < arraysize(num_keys); i++) { 260 t.CheckFind(num_keys[i], &num_keys[i]); 261 } 262 263 // Simulate a GC by moving SMIs. 264 // Ironically the SMIs "move", but the heap numbers don't! 265 t.SimulateGCByIncrementingSmisBy(kShift); 266 267 // Check that searching for the incremented smis finds the same values. 268 for (size_t i = 0; i < arraysize(smi_keys); i++) { 269 t.CheckFind(t.smi(smi_keys[i] + kShift), &smi_keys[i]); 270 t.CheckGet(t.smi(smi_keys[i] + kShift), &smi_keys[i]); 271 } 272 273 // Check that searching for the numbers finds the same values. 274 for (size_t i = 0; i < arraysize(num_keys); i++) { 275 t.CheckFind(num_keys[i], &num_keys[i]); 276 t.CheckGet(num_keys[i], &num_keys[i]); 277 } 278 } 279 280 281 void CollisionTest(int stride, bool rehash = false, bool resize = false) { 282 for (int load = 15; load <= 120; load = load * 2) { 283 IdentityMapTester t; 284 285 { // Add entries to the map. 286 HandleScope scope(t.isolate()); 287 int next = 1; 288 for (int i = 0; i < load; i++) { 289 t.map.Set(t.smi(next), reinterpret_cast<void*>(next)); 290 t.CheckFind(t.smi(next), reinterpret_cast<void*>(next)); 291 next = next + stride; 292 } 293 } 294 if (resize) t.Resize(); // Explicit resize (internal method). 295 if (rehash) t.Rehash(); // Explicit rehash (internal method). 296 { // Check find and get. 297 HandleScope scope(t.isolate()); 298 int next = 1; 299 for (int i = 0; i < load; i++) { 300 t.CheckFind(t.smi(next), reinterpret_cast<void*>(next)); 301 t.CheckGet(t.smi(next), reinterpret_cast<void*>(next)); 302 next = next + stride; 303 } 304 } 305 } 306 } 307 308 309 TEST(Collisions_1) { CollisionTest(1); } 310 TEST(Collisions_2) { CollisionTest(2); } 311 TEST(Collisions_3) { CollisionTest(3); } 312 TEST(Collisions_5) { CollisionTest(5); } 313 TEST(Collisions_7) { CollisionTest(7); } 314 TEST(Resize) { CollisionTest(9, false, true); } 315 TEST(Rehash) { CollisionTest(11, true, false); } 316 317 318 TEST(ExplicitGC) { 319 IdentityMapTester t; 320 Handle<Object> num_keys[] = {t.num(2.1), t.num(2.4), t.num(3.3), t.num(4.3), 321 t.num(7.5), t.num(6.4), t.num(7.3), t.num(8.3), 322 t.num(8.9), t.num(10.4)}; 323 324 // Insert some objects that should be in new space. 325 for (size_t i = 0; i < arraysize(num_keys); i++) { 326 t.map.Set(num_keys[i], &num_keys[i]); 327 } 328 329 // Do an explicit, real GC. 330 t.heap()->CollectGarbage(i::NEW_SPACE); 331 332 // Check that searching for the numbers finds the same values. 333 for (size_t i = 0; i < arraysize(num_keys); i++) { 334 t.CheckFind(num_keys[i], &num_keys[i]); 335 t.CheckGet(num_keys[i], &num_keys[i]); 336 } 337 } 338 339 340 TEST(CanonicalHandleScope) { 341 Isolate* isolate = CcTest::i_isolate(); 342 Heap* heap = CcTest::heap(); 343 HandleScope outer(isolate); 344 CanonicalHandleScope outer_canonical(isolate); 345 346 // Deduplicate smi handles. 347 List<Handle<Object> > smi_handles; 348 for (int i = 0; i < 100; i++) { 349 smi_handles.Add(Handle<Object>(Smi::FromInt(i), isolate)); 350 } 351 Object** next_handle = isolate->handle_scope_data()->next; 352 for (int i = 0; i < 100; i++) { 353 Handle<Object> new_smi = Handle<Object>(Smi::FromInt(i), isolate); 354 Handle<Object> old_smi = smi_handles[i]; 355 CHECK_EQ(new_smi.location(), old_smi.location()); 356 } 357 // Check that no new handles have been allocated. 358 CHECK_EQ(next_handle, isolate->handle_scope_data()->next); 359 360 // Deduplicate root list items. 361 Handle<String> empty_string(heap->empty_string()); 362 Handle<Map> free_space_map(heap->free_space_map()); 363 Handle<Symbol> uninitialized_symbol(heap->uninitialized_symbol()); 364 CHECK_EQ(isolate->factory()->empty_string().location(), 365 empty_string.location()); 366 CHECK_EQ(isolate->factory()->free_space_map().location(), 367 free_space_map.location()); 368 CHECK_EQ(isolate->factory()->uninitialized_symbol().location(), 369 uninitialized_symbol.location()); 370 // Check that no new handles have been allocated. 371 CHECK_EQ(next_handle, isolate->handle_scope_data()->next); 372 373 // Test ordinary heap objects. 374 Handle<HeapNumber> number1 = isolate->factory()->NewHeapNumber(3.3); 375 Handle<String> string1 = 376 isolate->factory()->NewStringFromAsciiChecked("test"); 377 next_handle = isolate->handle_scope_data()->next; 378 Handle<HeapNumber> number2(*number1); 379 Handle<String> string2(*string1); 380 CHECK_EQ(number1.location(), number2.location()); 381 CHECK_EQ(string1.location(), string2.location()); 382 heap->CollectAllGarbage(); 383 Handle<HeapNumber> number3(*number2); 384 Handle<String> string3(*string2); 385 CHECK_EQ(number1.location(), number3.location()); 386 CHECK_EQ(string1.location(), string3.location()); 387 // Check that no new handles have been allocated. 388 CHECK_EQ(next_handle, isolate->handle_scope_data()->next); 389 390 // Inner handle scope do not create canonical handles. 391 { 392 HandleScope inner(isolate); 393 Handle<HeapNumber> number4(*number1); 394 Handle<String> string4(*string1); 395 CHECK_NE(number1.location(), number4.location()); 396 CHECK_NE(string1.location(), string4.location()); 397 398 // Nested canonical scope does not conflict with outer canonical scope, 399 // but does not canonicalize across scopes. 400 CanonicalHandleScope inner_canonical(isolate); 401 Handle<HeapNumber> number5(*number4); 402 Handle<String> string5(*string4); 403 CHECK_NE(number4.location(), number5.location()); 404 CHECK_NE(string4.location(), string5.location()); 405 CHECK_NE(number1.location(), number5.location()); 406 CHECK_NE(string1.location(), string5.location()); 407 408 Handle<HeapNumber> number6(*number1); 409 Handle<String> string6(*string1); 410 CHECK_NE(number4.location(), number6.location()); 411 CHECK_NE(string4.location(), string6.location()); 412 CHECK_NE(number1.location(), number6.location()); 413 CHECK_NE(string1.location(), string6.location()); 414 CHECK_EQ(number5.location(), number6.location()); 415 CHECK_EQ(string5.location(), string6.location()); 416 } 417 } 418 419 } // namespace internal 420 } // namespace v8 421