Line data Source code
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 <set>
6 :
7 : #include "src/heap/factory-inl.h"
8 : #include "src/identity-map.h"
9 : #include "src/isolate.h"
10 : #include "src/objects.h"
11 : #include "src/objects/heap-number-inl.h"
12 : #include "src/zone/zone.h"
13 : #include "test/cctest/cctest.h"
14 :
15 : namespace v8 {
16 : namespace internal {
17 :
18 : // Helper for testing. A "friend" of the IdentityMapBase class, it is able to
19 : // "move" objects to simulate GC for testing the internals of the map.
20 740 : class IdentityMapTester : public HandleAndZoneScope {
21 : public:
22 : IdentityMap<void*, ZoneAllocationPolicy> map;
23 :
24 370 : IdentityMapTester() : map(heap(), ZoneAllocationPolicy(main_zone())) {}
25 :
26 : Heap* heap() { return isolate()->heap(); }
27 : Isolate* isolate() { return main_isolate(); }
28 :
29 5045 : void TestGetFind(Handle<Object> key1, void* val1, Handle<Object> key2,
30 : void* val2) {
31 5045 : CHECK_NULL(map.Find(key1));
32 5045 : CHECK_NULL(map.Find(key2));
33 :
34 : // Set {key1} the first time.
35 : void** entry = map.Get(key1);
36 5045 : CHECK_NOT_NULL(entry);
37 5045 : *entry = val1;
38 :
39 35315 : for (int i = 0; i < 3; i++) { // Get and find {key1} K times.
40 : {
41 : void** nentry = map.Get(key1);
42 15135 : CHECK_EQ(entry, nentry);
43 15135 : CHECK_EQ(val1, *nentry);
44 15135 : CHECK_NULL(map.Find(key2));
45 : }
46 : {
47 : void** nentry = map.Find(key1);
48 15135 : CHECK_EQ(entry, nentry);
49 15135 : CHECK_EQ(val1, *nentry);
50 15135 : CHECK_NULL(map.Find(key2));
51 : }
52 : }
53 :
54 : // Set {key2} the first time.
55 : void** entry2 = map.Get(key2);
56 5045 : CHECK_NOT_NULL(entry2);
57 5045 : *entry2 = val2;
58 :
59 35315 : for (int i = 0; i < 3; i++) { // Get and find {key1} and {key2} K times.
60 : {
61 : void** nentry = map.Get(key2);
62 15135 : CHECK_EQ(entry2, nentry);
63 15135 : CHECK_EQ(val2, *nentry);
64 : }
65 : {
66 : void** nentry = map.Find(key2);
67 15135 : CHECK_EQ(entry2, nentry);
68 15135 : CHECK_EQ(val2, *nentry);
69 : }
70 : {
71 : void** nentry = map.Find(key1);
72 15135 : CHECK_EQ(val1, *nentry);
73 : }
74 : }
75 5045 : }
76 :
77 10 : void TestFindDelete(Handle<Object> key1, void* val1, Handle<Object> key2,
78 : void* val2) {
79 10 : CHECK_NULL(map.Find(key1));
80 10 : CHECK_NULL(map.Find(key2));
81 :
82 : // Set {key1} and {key2} for the first time.
83 : void** entry1 = map.Get(key1);
84 10 : CHECK_NOT_NULL(entry1);
85 10 : *entry1 = val1;
86 : void** entry2 = map.Get(key2);
87 10 : CHECK_NOT_NULL(entry2);
88 10 : *entry2 = val2;
89 :
90 70 : for (int i = 0; i < 3; i++) { // Find {key1} and {key2} 3 times.
91 : {
92 : void** nentry = map.Find(key2);
93 30 : CHECK_EQ(val2, *nentry);
94 : }
95 : {
96 : void** nentry = map.Find(key1);
97 30 : CHECK_EQ(val1, *nentry);
98 : }
99 : }
100 :
101 : // Delete {key1}
102 : void* deleted_entry_1;
103 10 : CHECK(map.Delete(key1, &deleted_entry_1));
104 10 : CHECK_NOT_NULL(deleted_entry_1);
105 : deleted_entry_1 = val1;
106 :
107 70 : for (int i = 0; i < 3; i++) { // Find {key1} and not {key2} 3 times.
108 : {
109 : void** nentry = map.Find(key1);
110 30 : CHECK_NULL(nentry);
111 : }
112 : {
113 : void** nentry = map.Find(key2);
114 30 : CHECK_EQ(val2, *nentry);
115 : }
116 : }
117 :
118 : // Delete {key2}
119 : void* deleted_entry_2;
120 10 : CHECK(map.Delete(key2, &deleted_entry_2));
121 10 : CHECK_NOT_NULL(deleted_entry_2);
122 : deleted_entry_2 = val2;
123 :
124 70 : for (int i = 0; i < 3; i++) { // Don't find {key1} and {key2} 3 times.
125 : {
126 : void** nentry = map.Find(key1);
127 30 : CHECK_NULL(nentry);
128 : }
129 : {
130 : void** nentry = map.Find(key2);
131 30 : CHECK_NULL(nentry);
132 : }
133 : }
134 10 : }
135 :
136 98640 : Handle<Smi> smi(int value) {
137 98640 : return Handle<Smi>(Smi::FromInt(value), isolate());
138 : }
139 :
140 : Handle<Object> num(double value) {
141 1260 : return isolate()->factory()->NewNumber(value);
142 : }
143 :
144 : void SimulateGCByIncrementingSmisBy(int shift) {
145 1101 : for (int i = 0; i < map.capacity_; i++) {
146 528 : Address key = map.keys_[i];
147 528 : if (!Internals::HasHeapObjectTag(key)) {
148 450 : map.keys_[i] = Internals::IntToSmi(Internals::SmiValue(key) + shift);
149 : }
150 : }
151 45 : map.gc_counter_ = -1;
152 : }
153 :
154 27395 : void CheckFind(Handle<Object> key, void* value) {
155 : void** entry = map.Find(key);
156 27395 : CHECK_NOT_NULL(entry);
157 27395 : CHECK_EQ(value, *entry);
158 27395 : }
159 :
160 13730 : void CheckGet(Handle<Object> key, void* value) {
161 : void** entry = map.Get(key);
162 13730 : CHECK_NOT_NULL(entry);
163 13730 : CHECK_EQ(value, *entry);
164 13730 : }
165 :
166 5300 : void CheckDelete(Handle<Object> key, void* value) {
167 : void* entry;
168 5300 : CHECK(map.Delete(key, &entry));
169 5300 : CHECK_NOT_NULL(entry);
170 5300 : CHECK_EQ(value, entry);
171 5300 : }
172 :
173 : void PrintMap() {
174 : PrintF("{\n");
175 : for (int i = 0; i < map.capacity_; i++) {
176 : PrintF(" %3d: %p => %p\n", i, reinterpret_cast<void*>(map.keys_[i]),
177 : reinterpret_cast<void*>(map.values_[i]));
178 : }
179 : PrintF("}\n");
180 : }
181 :
182 20 : void Resize() { map.Resize(map.capacity_ * 4); }
183 :
184 20 : void Rehash() { map.Rehash(); }
185 : };
186 :
187 26644 : TEST(Find_smi_not_found) {
188 5 : IdentityMapTester t;
189 1005 : for (int i = 0; i < 100; i++) {
190 1000 : CHECK_NULL(t.map.Find(t.smi(i)));
191 : }
192 5 : }
193 :
194 :
195 26644 : TEST(Find_num_not_found) {
196 5 : IdentityMapTester t;
197 1005 : for (int i = 0; i < 100; i++) {
198 1000 : CHECK_NULL(t.map.Find(t.num(i + 0.2)));
199 : }
200 5 : }
201 :
202 26644 : TEST(Delete_smi_not_found) {
203 5 : IdentityMapTester t;
204 1005 : for (int i = 0; i < 100; i++) {
205 : void* deleted_value = &t;
206 1000 : CHECK(!t.map.Delete(t.smi(i), &deleted_value));
207 500 : CHECK_EQ(&t, deleted_value);
208 : }
209 5 : }
210 :
211 26644 : TEST(Delete_num_not_found) {
212 5 : IdentityMapTester t;
213 1005 : for (int i = 0; i < 100; i++) {
214 : void* deleted_value = &t;
215 1000 : CHECK(!t.map.Delete(t.num(i + 0.2), &deleted_value));
216 500 : CHECK_EQ(&t, deleted_value);
217 : }
218 5 : }
219 :
220 26644 : TEST(GetFind_smi_0) {
221 5 : IdentityMapTester t;
222 15 : t.TestGetFind(t.smi(0), t.isolate(), t.smi(1), t.heap());
223 5 : }
224 :
225 26644 : TEST(GetFind_smi_13) {
226 5 : IdentityMapTester t;
227 15 : t.TestGetFind(t.smi(13), t.isolate(), t.smi(17), t.heap());
228 5 : }
229 :
230 26644 : TEST(GetFind_num_13) {
231 5 : IdentityMapTester t;
232 5 : t.TestGetFind(t.num(13.1), t.isolate(), t.num(17.1), t.heap());
233 5 : }
234 :
235 26644 : TEST(Delete_smi_13) {
236 5 : IdentityMapTester t;
237 15 : t.TestFindDelete(t.smi(13), t.isolate(), t.smi(17), t.heap());
238 5 : CHECK(t.map.empty());
239 5 : }
240 :
241 26644 : TEST(Delete_num_13) {
242 5 : IdentityMapTester t;
243 5 : t.TestFindDelete(t.num(13.1), t.isolate(), t.num(17.1), t.heap());
244 5 : CHECK(t.map.empty());
245 5 : }
246 :
247 26644 : TEST(GetFind_smi_17m) {
248 : const int kInterval = 17;
249 : const int kShift = 1099;
250 5 : IdentityMapTester t;
251 :
252 65 : for (int i = 1; i < 100; i += kInterval) {
253 30 : t.map.Set(t.smi(i), reinterpret_cast<void*>(i + kShift));
254 : }
255 :
256 65 : for (int i = 1; i < 100; i += kInterval) {
257 60 : t.CheckFind(t.smi(i), reinterpret_cast<void*>(i + kShift));
258 : }
259 :
260 65 : for (int i = 1; i < 100; i += kInterval) {
261 60 : t.CheckGet(t.smi(i), reinterpret_cast<void*>(i + kShift));
262 : }
263 :
264 995 : for (int i = 1; i < 100; i++) {
265 495 : void** entry = t.map.Find(t.smi(i));
266 495 : if ((i % kInterval) != 1) {
267 465 : CHECK_NULL(entry);
268 : } else {
269 30 : CHECK_NOT_NULL(entry);
270 30 : CHECK_EQ(reinterpret_cast<void*>(i + kShift), *entry);
271 : }
272 : }
273 5 : }
274 :
275 26644 : TEST(Delete_smi_17m) {
276 : const int kInterval = 17;
277 : const int kShift = 1099;
278 5 : IdentityMapTester t;
279 :
280 65 : for (int i = 1; i < 100; i += kInterval) {
281 30 : t.map.Set(t.smi(i), reinterpret_cast<void*>(i + kShift));
282 : }
283 :
284 65 : for (int i = 1; i < 100; i += kInterval) {
285 60 : t.CheckFind(t.smi(i), reinterpret_cast<void*>(i + kShift));
286 : }
287 :
288 65 : for (int i = 1; i < 100; i += kInterval) {
289 60 : t.CheckDelete(t.smi(i), reinterpret_cast<void*>(i + kShift));
290 390 : for (int j = 1; j < 100; j += kInterval) {
291 180 : void** entry = t.map.Find(t.smi(j));
292 180 : if (j <= i) {
293 105 : CHECK_NULL(entry);
294 : } else {
295 75 : CHECK_NOT_NULL(entry);
296 75 : CHECK_EQ(reinterpret_cast<void*>(j + kShift), *entry);
297 : }
298 : }
299 : }
300 5 : }
301 :
302 26644 : TEST(GetFind_num_1000) {
303 : const int kPrime = 137;
304 5 : IdentityMapTester t;
305 : int val1;
306 : int val2;
307 :
308 10005 : for (int i = 0; i < 1000; i++) {
309 15000 : t.TestGetFind(t.smi(i * kPrime), &val1, t.smi(i * kPrime + 1), &val2);
310 : }
311 5 : }
312 :
313 26644 : TEST(Delete_num_1000) {
314 : const int kPrime = 137;
315 5 : IdentityMapTester t;
316 :
317 10005 : for (int i = 0; i < 1000; i++) {
318 5000 : t.map.Set(t.smi(i * kPrime), reinterpret_cast<void*>(i * kPrime));
319 : }
320 :
321 : // Delete every second value in reverse.
322 5005 : for (int i = 999; i >= 0; i -= 2) {
323 : void* entry;
324 5000 : CHECK(t.map.Delete(t.smi(i * kPrime), &entry));
325 2500 : CHECK_EQ(reinterpret_cast<void*>(i * kPrime), entry);
326 : }
327 :
328 10005 : for (int i = 0; i < 1000; i++) {
329 5000 : void** entry = t.map.Find(t.smi(i * kPrime));
330 5000 : if (i % 2) {
331 2500 : CHECK_NULL(entry);
332 : } else {
333 2500 : CHECK_NOT_NULL(entry);
334 2500 : CHECK_EQ(reinterpret_cast<void*>(i * kPrime), *entry);
335 : }
336 : }
337 :
338 : // Delete the rest.
339 5005 : for (int i = 0; i < 1000; i += 2) {
340 : void* entry;
341 5000 : CHECK(t.map.Delete(t.smi(i * kPrime), &entry));
342 2500 : CHECK_EQ(reinterpret_cast<void*>(i * kPrime), entry);
343 : }
344 :
345 10005 : for (int i = 0; i < 1000; i++) {
346 5000 : void** entry = t.map.Find(t.smi(i * kPrime));
347 5000 : CHECK_NULL(entry);
348 : }
349 5 : }
350 :
351 26644 : TEST(GetFind_smi_gc) {
352 : const int kKey = 33;
353 : const int kShift = 1211;
354 5 : IdentityMapTester t;
355 :
356 5 : t.map.Set(t.smi(kKey), &t);
357 : t.SimulateGCByIncrementingSmisBy(kShift);
358 10 : t.CheckFind(t.smi(kKey + kShift), &t);
359 10 : t.CheckGet(t.smi(kKey + kShift), &t);
360 5 : }
361 :
362 26644 : TEST(Delete_smi_gc) {
363 : const int kKey = 33;
364 : const int kShift = 1211;
365 5 : IdentityMapTester t;
366 :
367 5 : t.map.Set(t.smi(kKey), &t);
368 : t.SimulateGCByIncrementingSmisBy(kShift);
369 10 : t.CheckDelete(t.smi(kKey + kShift), &t);
370 5 : }
371 :
372 26644 : TEST(GetFind_smi_gc2) {
373 5 : int kKey1 = 1;
374 5 : int kKey2 = 33;
375 : const int kShift = 1211;
376 5 : IdentityMapTester t;
377 :
378 5 : t.map.Set(t.smi(kKey1), &kKey1);
379 5 : t.map.Set(t.smi(kKey2), &kKey2);
380 : t.SimulateGCByIncrementingSmisBy(kShift);
381 10 : t.CheckFind(t.smi(kKey1 + kShift), &kKey1);
382 10 : t.CheckGet(t.smi(kKey1 + kShift), &kKey1);
383 10 : t.CheckFind(t.smi(kKey2 + kShift), &kKey2);
384 10 : t.CheckGet(t.smi(kKey2 + kShift), &kKey2);
385 5 : }
386 :
387 26644 : TEST(Delete_smi_gc2) {
388 5 : int kKey1 = 1;
389 5 : int kKey2 = 33;
390 : const int kShift = 1211;
391 5 : IdentityMapTester t;
392 :
393 5 : t.map.Set(t.smi(kKey1), &kKey1);
394 5 : t.map.Set(t.smi(kKey2), &kKey2);
395 : t.SimulateGCByIncrementingSmisBy(kShift);
396 10 : t.CheckDelete(t.smi(kKey1 + kShift), &kKey1);
397 10 : t.CheckDelete(t.smi(kKey2 + kShift), &kKey2);
398 5 : }
399 :
400 26644 : TEST(GetFind_smi_gc_n) {
401 : const int kShift = 12011;
402 5 : IdentityMapTester t;
403 : int keys[12] = {1, 2, 7, 8, 15, 23,
404 5 : 1 + 32, 2 + 32, 7 + 32, 8 + 32, 15 + 32, 23 + 32};
405 : // Initialize the map first.
406 65 : for (size_t i = 0; i < arraysize(keys); i += 2) {
407 90 : t.TestGetFind(t.smi(keys[i]), &keys[i], t.smi(keys[i + 1]), &keys[i + 1]);
408 : }
409 : // Check the above initialization.
410 125 : for (size_t i = 0; i < arraysize(keys); i++) {
411 120 : t.CheckFind(t.smi(keys[i]), &keys[i]);
412 : }
413 : // Simulate a GC by "moving" the smis in the internal keys array.
414 : t.SimulateGCByIncrementingSmisBy(kShift);
415 : // Check that searching for the incremented smis finds the same values.
416 125 : for (size_t i = 0; i < arraysize(keys); i++) {
417 120 : t.CheckFind(t.smi(keys[i] + kShift), &keys[i]);
418 : }
419 : // Check that searching for the incremented smis gets the same values.
420 125 : for (size_t i = 0; i < arraysize(keys); i++) {
421 120 : t.CheckGet(t.smi(keys[i] + kShift), &keys[i]);
422 : }
423 5 : }
424 :
425 26644 : TEST(Delete_smi_gc_n) {
426 : const int kShift = 12011;
427 5 : IdentityMapTester t;
428 : int keys[12] = {1, 2, 7, 8, 15, 23,
429 5 : 1 + 32, 2 + 32, 7 + 32, 8 + 32, 15 + 32, 23 + 32};
430 : // Initialize the map first.
431 125 : for (size_t i = 0; i < arraysize(keys); i++) {
432 60 : t.map.Set(t.smi(keys[i]), &keys[i]);
433 : }
434 : // Simulate a GC by "moving" the smis in the internal keys array.
435 : t.SimulateGCByIncrementingSmisBy(kShift);
436 : // Check that deleting for the incremented smis finds the same values.
437 125 : for (size_t i = 0; i < arraysize(keys); i++) {
438 120 : t.CheckDelete(t.smi(keys[i] + kShift), &keys[i]);
439 : }
440 5 : }
441 :
442 26644 : TEST(GetFind_smi_num_gc_n) {
443 : const int kShift = 12019;
444 5 : IdentityMapTester t;
445 5 : int smi_keys[] = {1, 2, 7, 15, 23};
446 : Handle<Object> num_keys[] = {t.num(1.1), t.num(2.2), t.num(3.3), t.num(4.4),
447 : t.num(5.5), t.num(6.6), t.num(7.7), t.num(8.8),
448 50 : t.num(9.9), t.num(10.1)};
449 : // Initialize the map first.
450 55 : for (size_t i = 0; i < arraysize(smi_keys); i++) {
451 25 : t.map.Set(t.smi(smi_keys[i]), &smi_keys[i]);
452 : }
453 105 : for (size_t i = 0; i < arraysize(num_keys); i++) {
454 50 : t.map.Set(num_keys[i], &num_keys[i]);
455 : }
456 : // Check the above initialization.
457 55 : for (size_t i = 0; i < arraysize(smi_keys); i++) {
458 50 : t.CheckFind(t.smi(smi_keys[i]), &smi_keys[i]);
459 : }
460 105 : for (size_t i = 0; i < arraysize(num_keys); i++) {
461 50 : t.CheckFind(num_keys[i], &num_keys[i]);
462 : }
463 :
464 : // Simulate a GC by moving SMIs.
465 : // Ironically the SMIs "move", but the heap numbers don't!
466 : t.SimulateGCByIncrementingSmisBy(kShift);
467 :
468 : // Check that searching for the incremented smis finds the same values.
469 55 : for (size_t i = 0; i < arraysize(smi_keys); i++) {
470 50 : t.CheckFind(t.smi(smi_keys[i] + kShift), &smi_keys[i]);
471 50 : t.CheckGet(t.smi(smi_keys[i] + kShift), &smi_keys[i]);
472 : }
473 :
474 : // Check that searching for the numbers finds the same values.
475 105 : for (size_t i = 0; i < arraysize(num_keys); i++) {
476 50 : t.CheckFind(num_keys[i], &num_keys[i]);
477 50 : t.CheckGet(num_keys[i], &num_keys[i]);
478 : }
479 5 : }
480 :
481 26644 : TEST(Delete_smi_num_gc_n) {
482 : const int kShift = 12019;
483 5 : IdentityMapTester t;
484 5 : int smi_keys[] = {1, 2, 7, 15, 23};
485 : Handle<Object> num_keys[] = {t.num(1.1), t.num(2.2), t.num(3.3), t.num(4.4),
486 : t.num(5.5), t.num(6.6), t.num(7.7), t.num(8.8),
487 50 : t.num(9.9), t.num(10.1)};
488 : // Initialize the map first.
489 55 : for (size_t i = 0; i < arraysize(smi_keys); i++) {
490 25 : t.map.Set(t.smi(smi_keys[i]), &smi_keys[i]);
491 : }
492 105 : for (size_t i = 0; i < arraysize(num_keys); i++) {
493 50 : t.map.Set(num_keys[i], &num_keys[i]);
494 : }
495 :
496 : // Simulate a GC by moving SMIs.
497 : // Ironically the SMIs "move", but the heap numbers don't!
498 : t.SimulateGCByIncrementingSmisBy(kShift);
499 :
500 : // Check that deleting for the incremented smis finds the same values.
501 55 : for (size_t i = 0; i < arraysize(smi_keys); i++) {
502 50 : t.CheckDelete(t.smi(smi_keys[i] + kShift), &smi_keys[i]);
503 : }
504 :
505 : // Check that deleting the numbers finds the same values.
506 105 : for (size_t i = 0; i < arraysize(num_keys); i++) {
507 50 : t.CheckDelete(num_keys[i], &num_keys[i]);
508 : }
509 5 : }
510 :
511 26644 : TEST(Delete_smi_resizes) {
512 : const int kKeyCount = 1024;
513 : const int kValueOffset = 27;
514 5 : IdentityMapTester t;
515 :
516 : // Insert one element to initialize map.
517 5 : t.map.Set(t.smi(0), reinterpret_cast<void*>(kValueOffset));
518 :
519 : int initial_capacity = t.map.capacity();
520 5 : CHECK_LT(initial_capacity, kKeyCount);
521 :
522 : // Insert another kKeyCount - 1 keys.
523 10235 : for (int i = 1; i < kKeyCount; i++) {
524 5115 : t.map.Set(t.smi(i), reinterpret_cast<void*>(i + kValueOffset));
525 : }
526 :
527 : // Check capacity increased.
528 5 : CHECK_GT(t.map.capacity(), initial_capacity);
529 5 : CHECK_GE(t.map.capacity(), kKeyCount);
530 :
531 : // Delete all the keys.
532 10245 : for (int i = 0; i < kKeyCount; i++) {
533 10240 : t.CheckDelete(t.smi(i), reinterpret_cast<void*>(i + kValueOffset));
534 : }
535 :
536 : // Should resize back to initial capacity.
537 5 : CHECK_EQ(t.map.capacity(), initial_capacity);
538 5 : }
539 :
540 26644 : TEST(Iterator_smi_num) {
541 5 : IdentityMapTester t;
542 5 : int smi_keys[] = {1, 2, 7, 15, 23};
543 : Handle<Object> num_keys[] = {t.num(1.1), t.num(2.2), t.num(3.3), t.num(4.4),
544 : t.num(5.5), t.num(6.6), t.num(7.7), t.num(8.8),
545 50 : t.num(9.9), t.num(10.1)};
546 : // Initialize the map.
547 55 : for (size_t i = 0; i < arraysize(smi_keys); i++) {
548 25 : t.map.Set(t.smi(smi_keys[i]), reinterpret_cast<void*>(i));
549 : }
550 105 : for (size_t i = 0; i < arraysize(num_keys); i++) {
551 50 : t.map.Set(num_keys[i], reinterpret_cast<void*>(i + 5));
552 : }
553 :
554 : // Check iterator sees all values once.
555 : std::set<intptr_t> seen;
556 : {
557 10 : IdentityMap<void*, ZoneAllocationPolicy>::IteratableScope it_scope(&t.map);
558 80 : for (auto it = it_scope.begin(); it != it_scope.end(); ++it) {
559 150 : CHECK(seen.find(reinterpret_cast<intptr_t>(**it)) == seen.end());
560 150 : seen.insert(reinterpret_cast<intptr_t>(**it));
561 : }
562 : }
563 155 : for (intptr_t i = 0; i < 15; i++) {
564 75 : CHECK(seen.find(i) != seen.end());
565 : }
566 5 : }
567 :
568 26644 : TEST(Iterator_smi_num_gc) {
569 : const int kShift = 16039;
570 5 : IdentityMapTester t;
571 5 : int smi_keys[] = {1, 2, 7, 15, 23};
572 : Handle<Object> num_keys[] = {t.num(1.1), t.num(2.2), t.num(3.3), t.num(4.4),
573 : t.num(5.5), t.num(6.6), t.num(7.7), t.num(8.8),
574 50 : t.num(9.9), t.num(10.1)};
575 : // Initialize the map.
576 55 : for (size_t i = 0; i < arraysize(smi_keys); i++) {
577 25 : t.map.Set(t.smi(smi_keys[i]), reinterpret_cast<void*>(i));
578 : }
579 105 : for (size_t i = 0; i < arraysize(num_keys); i++) {
580 50 : t.map.Set(num_keys[i], reinterpret_cast<void*>(i + 5));
581 : }
582 :
583 : // Simulate GC by moving the SMIs.
584 : t.SimulateGCByIncrementingSmisBy(kShift);
585 :
586 : // Check iterator sees all values.
587 : std::set<intptr_t> seen;
588 : {
589 10 : IdentityMap<void*, ZoneAllocationPolicy>::IteratableScope it_scope(&t.map);
590 80 : for (auto it = it_scope.begin(); it != it_scope.end(); ++it) {
591 150 : CHECK(seen.find(reinterpret_cast<intptr_t>(**it)) == seen.end());
592 150 : seen.insert(reinterpret_cast<intptr_t>(**it));
593 : }
594 : }
595 155 : for (intptr_t i = 0; i < 15; i++) {
596 75 : CHECK(seen.find(i) != seen.end());
597 : }
598 5 : }
599 :
600 25 : void IterateCollisionTest(int stride) {
601 225 : for (int load = 15; load <= 120; load = load * 2) {
602 100 : IdentityMapTester t;
603 :
604 : { // Add entries to the map.
605 : HandleScope scope(t.isolate());
606 : int next = 1;
607 11350 : for (int i = 0; i < load; i++) {
608 5625 : t.map.Set(t.smi(next), reinterpret_cast<void*>(next));
609 11250 : t.CheckFind(t.smi(next), reinterpret_cast<void*>(next));
610 5625 : next = next + stride;
611 : }
612 : }
613 : // Iterate through the map and check we see all elements only once.
614 : std::set<intptr_t> seen;
615 : {
616 : IdentityMap<void*, ZoneAllocationPolicy>::IteratableScope it_scope(
617 200 : &t.map);
618 5725 : for (auto it = it_scope.begin(); it != it_scope.end(); ++it) {
619 11250 : CHECK(seen.find(reinterpret_cast<intptr_t>(**it)) == seen.end());
620 11250 : seen.insert(reinterpret_cast<intptr_t>(**it));
621 : }
622 : }
623 : // Check get and find on map.
624 : {
625 : HandleScope scope(t.isolate());
626 : int next = 1;
627 11350 : for (int i = 0; i < load; i++) {
628 11250 : CHECK(seen.find(next) != seen.end());
629 11250 : t.CheckFind(t.smi(next), reinterpret_cast<void*>(next));
630 11250 : t.CheckGet(t.smi(next), reinterpret_cast<void*>(next));
631 5625 : next = next + stride;
632 : }
633 : }
634 : }
635 25 : }
636 :
637 26644 : TEST(IterateCollisions_1) { IterateCollisionTest(1); }
638 26644 : TEST(IterateCollisions_2) { IterateCollisionTest(2); }
639 26644 : TEST(IterateCollisions_3) { IterateCollisionTest(3); }
640 26644 : TEST(IterateCollisions_5) { IterateCollisionTest(5); }
641 26644 : TEST(IterateCollisions_7) { IterateCollisionTest(7); }
642 :
643 35 : void CollisionTest(int stride, bool rehash = false, bool resize = false) {
644 315 : for (int load = 15; load <= 120; load = load * 2) {
645 140 : IdentityMapTester t;
646 :
647 : { // Add entries to the map.
648 : HandleScope scope(t.isolate());
649 : int next = 1;
650 15890 : for (int i = 0; i < load; i++) {
651 7875 : t.map.Set(t.smi(next), reinterpret_cast<void*>(next));
652 15750 : t.CheckFind(t.smi(next), reinterpret_cast<void*>(next));
653 7875 : next = next + stride;
654 : }
655 : }
656 140 : if (resize) t.Resize(); // Explicit resize (internal method).
657 140 : if (rehash) t.Rehash(); // Explicit rehash (internal method).
658 : { // Check find and get.
659 : HandleScope scope(t.isolate());
660 : int next = 1;
661 15890 : for (int i = 0; i < load; i++) {
662 15750 : t.CheckFind(t.smi(next), reinterpret_cast<void*>(next));
663 15750 : t.CheckGet(t.smi(next), reinterpret_cast<void*>(next));
664 7875 : next = next + stride;
665 : }
666 : }
667 : }
668 35 : }
669 :
670 26644 : TEST(Collisions_1) { CollisionTest(1); }
671 26644 : TEST(Collisions_2) { CollisionTest(2); }
672 26644 : TEST(Collisions_3) { CollisionTest(3); }
673 26644 : TEST(Collisions_5) { CollisionTest(5); }
674 26644 : TEST(Collisions_7) { CollisionTest(7); }
675 26644 : TEST(Resize) { CollisionTest(9, false, true); }
676 26644 : TEST(Rehash) { CollisionTest(11, true, false); }
677 :
678 26644 : TEST(ExplicitGC) {
679 5 : IdentityMapTester t;
680 : Handle<Object> num_keys[] = {t.num(2.1), t.num(2.4), t.num(3.3), t.num(4.3),
681 : t.num(7.5), t.num(6.4), t.num(7.3), t.num(8.3),
682 50 : t.num(8.9), t.num(10.4)};
683 :
684 : // Insert some objects that should be in new space.
685 105 : for (size_t i = 0; i < arraysize(num_keys); i++) {
686 50 : t.map.Set(num_keys[i], &num_keys[i]);
687 : }
688 :
689 : // Do an explicit, real GC.
690 5 : t.heap()->CollectGarbage(i::NEW_SPACE, i::GarbageCollectionReason::kTesting);
691 :
692 : // Check that searching for the numbers finds the same values.
693 105 : for (size_t i = 0; i < arraysize(num_keys); i++) {
694 50 : t.CheckFind(num_keys[i], &num_keys[i]);
695 50 : t.CheckGet(num_keys[i], &num_keys[i]);
696 : }
697 5 : }
698 :
699 26644 : TEST(CanonicalHandleScope) {
700 : Isolate* isolate = CcTest::i_isolate();
701 5 : Heap* heap = CcTest::heap();
702 : HandleScope outer(isolate);
703 10 : CanonicalHandleScope outer_canonical(isolate);
704 :
705 : // Deduplicate smi handles.
706 : std::vector<Handle<Object>> smi_handles;
707 1005 : for (int i = 0; i < 100; i++) {
708 500 : smi_handles.push_back(Handle<Object>(Smi::FromInt(i), isolate));
709 : }
710 5 : Address* next_handle = isolate->handle_scope_data()->next;
711 1005 : for (int i = 0; i < 100; i++) {
712 : Handle<Object> new_smi = Handle<Object>(Smi::FromInt(i), isolate);
713 500 : Handle<Object> old_smi = smi_handles[i];
714 500 : CHECK_EQ(new_smi.location(), old_smi.location());
715 : }
716 : // Check that no new handles have been allocated.
717 5 : CHECK_EQ(next_handle, isolate->handle_scope_data()->next);
718 :
719 : // Deduplicate root list items.
720 : Handle<String> empty_string(ReadOnlyRoots(heap).empty_string(), isolate);
721 : Handle<Map> free_space_map(ReadOnlyRoots(heap).free_space_map(), isolate);
722 : Handle<Symbol> uninitialized_symbol(
723 : ReadOnlyRoots(heap).uninitialized_symbol(), isolate);
724 5 : CHECK_EQ(isolate->factory()->empty_string().location(),
725 : empty_string.location());
726 5 : CHECK_EQ(isolate->factory()->free_space_map().location(),
727 : free_space_map.location());
728 5 : CHECK_EQ(isolate->factory()->uninitialized_symbol().location(),
729 : uninitialized_symbol.location());
730 : // Check that no new handles have been allocated.
731 5 : CHECK_EQ(next_handle, isolate->handle_scope_data()->next);
732 :
733 : // Test ordinary heap objects.
734 5 : Handle<HeapNumber> number1 = isolate->factory()->NewHeapNumber(3.3);
735 : Handle<String> string1 =
736 5 : isolate->factory()->NewStringFromAsciiChecked("test");
737 5 : next_handle = isolate->handle_scope_data()->next;
738 : Handle<HeapNumber> number2(*number1, isolate);
739 : Handle<String> string2(*string1, isolate);
740 5 : CHECK_EQ(number1.location(), number2.location());
741 5 : CHECK_EQ(string1.location(), string2.location());
742 5 : CcTest::CollectAllGarbage();
743 : Handle<HeapNumber> number3(*number2, isolate);
744 : Handle<String> string3(*string2, isolate);
745 5 : CHECK_EQ(number1.location(), number3.location());
746 5 : CHECK_EQ(string1.location(), string3.location());
747 : // Check that no new handles have been allocated.
748 5 : CHECK_EQ(next_handle, isolate->handle_scope_data()->next);
749 :
750 : // Inner handle scope do not create canonical handles.
751 : {
752 : HandleScope inner(isolate);
753 : Handle<HeapNumber> number4(*number1, isolate);
754 : Handle<String> string4(*string1, isolate);
755 5 : CHECK_NE(number1.location(), number4.location());
756 5 : CHECK_NE(string1.location(), string4.location());
757 :
758 : // Nested canonical scope does not conflict with outer canonical scope,
759 : // but does not canonicalize across scopes.
760 10 : CanonicalHandleScope inner_canonical(isolate);
761 : Handle<HeapNumber> number5(*number4, isolate);
762 : Handle<String> string5(*string4, isolate);
763 5 : CHECK_NE(number4.location(), number5.location());
764 5 : CHECK_NE(string4.location(), string5.location());
765 5 : CHECK_NE(number1.location(), number5.location());
766 5 : CHECK_NE(string1.location(), string5.location());
767 :
768 : Handle<HeapNumber> number6(*number1, isolate);
769 : Handle<String> string6(*string1, isolate);
770 5 : CHECK_NE(number4.location(), number6.location());
771 5 : CHECK_NE(string4.location(), string6.location());
772 5 : CHECK_NE(number1.location(), number6.location());
773 5 : CHECK_NE(string1.location(), string6.location());
774 5 : CHECK_EQ(number5.location(), number6.location());
775 5 : CHECK_EQ(string5.location(), string6.location());
776 : }
777 5 : }
778 :
779 26644 : TEST(GCShortCutting) {
780 : ManualGCScope manual_gc_scope;
781 5 : IdentityMapTester t;
782 : Isolate* isolate = CcTest::i_isolate();
783 : Factory* factory = isolate->factory();
784 : const int kDummyValue = 0;
785 :
786 165 : for (int i = 0; i < 16; i++) {
787 : // Insert a varying number of Smis as padding to ensure some tests straddle
788 : // a boundary where the thin string short cutting will cause size_ to be
789 : // greater to capacity_ if not corrected by IdentityMap
790 : // (see crbug.com/704132).
791 1280 : for (int j = 0; j < i; j++) {
792 600 : t.map.Set(t.smi(j), reinterpret_cast<void*>(kDummyValue));
793 : }
794 :
795 : Handle<String> thin_string =
796 80 : factory->NewStringFromAsciiChecked("thin_string");
797 : Handle<String> internalized_string =
798 80 : factory->InternalizeString(thin_string);
799 : DCHECK_IMPLIES(FLAG_thin_strings, thin_string->IsThinString());
800 : DCHECK_NE(*thin_string, *internalized_string);
801 :
802 : // Insert both keys into the map.
803 : t.map.Set(thin_string, &thin_string);
804 : t.map.Set(internalized_string, &internalized_string);
805 :
806 : // Do an explicit, real GC, this should short-cut the thin string to point
807 : // to the internalized string.
808 : t.heap()->CollectGarbage(i::NEW_SPACE,
809 80 : i::GarbageCollectionReason::kTesting);
810 : DCHECK_IMPLIES(FLAG_thin_strings && !FLAG_optimize_for_size,
811 : *thin_string == *internalized_string);
812 :
813 : // Check that getting the object points to one of the handles.
814 : void** thin_string_entry = t.map.Get(thin_string);
815 80 : CHECK(*thin_string_entry == &thin_string ||
816 : *thin_string_entry == &internalized_string);
817 : void** internalized_string_entry = t.map.Get(internalized_string);
818 80 : CHECK(*internalized_string_entry == &thin_string ||
819 : *internalized_string_entry == &internalized_string);
820 :
821 : // Trigger resize.
822 2640 : for (int j = 0; j < 16; j++) {
823 1280 : t.map.Set(t.smi(j + 16), reinterpret_cast<void*>(kDummyValue));
824 : }
825 : t.map.Clear();
826 : }
827 5 : }
828 :
829 : } // namespace internal
830 79917 : } // namespace v8
|
