OLD | NEW |
(Empty) | |
| 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/heap/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 = 1; 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 } |
OLD | NEW |