js/src/jsapi-tests/testGCWeakCache.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   2  * vim: set ts=8 sts=2 et sw=2 tw=80:
   3  */
   4 /* This Source Code Form is subject to the terms of the Mozilla Public
   5  * License, v. 2.0. If a copy of the MPL was not distributed with this
   6  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   7
   8 #include "gc/Policy.h"
   9 #include "gc/SweepingAPI.h"
  10 #include "gc/Zone.h"
  11 #include "js/GCHashTable.h"
  12 #include "js/RootingAPI.h"
  13
  14 #include "jsapi-tests/tests.h"
  15
  16 using namespace js;
  17
  18 // Exercise WeakCache<GCHashSet>.
  19 BEGIN_TEST(testWeakCacheSet) {
  20   // Create two objects tenured and two in the nursery. If zeal is on,
  21   // this may fail and we'll get more tenured objects. That's fine:
  22   // the test will continue to work, it will just not test as much.
  23   JS::RootedObject tenured1(cx, JS_NewPlainObject(cx));
  24   JS::RootedObject tenured2(cx, JS_NewPlainObject(cx));
  25   JS_GC(cx);
  26   JS::RootedObject nursery1(cx, JS_NewPlainObject(cx));
  27   JS::RootedObject nursery2(cx, JS_NewPlainObject(cx));
  28
  29   using ObjectSet =
  30       GCHashSet<HeapPtr<JSObject*>, StableCellHasher<HeapPtr<JSObject*>>,
  31                 SystemAllocPolicy>;
  32   using Cache = WeakCache<ObjectSet>;
  33   Cache cache(JS::GetObjectZone(tenured1));
  34
  35   cache.put(tenured1);
  36   cache.put(tenured2);
  37   cache.put(nursery1);
  38   cache.put(nursery2);
  39
  40   // Verify relocation and that we don't sweep too aggressively.
  41   JS_GC(cx);
  42   CHECK(cache.has(tenured1));
  43   CHECK(cache.has(tenured2));
  44   CHECK(cache.has(nursery1));
  45   CHECK(cache.has(nursery2));
  46
  47   // Unroot two entries and verify that they get removed.
  48   tenured2 = nursery2 = nullptr;
  49   JS_GC(cx);
  50   CHECK(cache.has(tenured1));
  51   CHECK(cache.has(nursery1));
  52   CHECK(cache.count() == 2);
  53
  54   return true;
  55 }
  56 END_TEST(testWeakCacheSet)
  57
  58 // Exercise WeakCache<GCHashMap>.
  59 BEGIN_TEST(testWeakCacheMap) {
  60   // Create two objects tenured and two in the nursery. If zeal is on,
  61   // this may fail and we'll get more tenured objects. That's fine:
  62   // the test will continue to work, it will just not test as much.
  63   JS::RootedObject tenured1(cx, JS_NewPlainObject(cx));
  64   JS::RootedObject tenured2(cx, JS_NewPlainObject(cx));
  65   JS_GC(cx);
  66   JS::RootedObject nursery1(cx, JS_NewPlainObject(cx));
  67   JS::RootedObject nursery2(cx, JS_NewPlainObject(cx));
  68
  69   using ObjectMap = js::GCHashMap<HeapPtr<JSObject*>, uint32_t,
  70                                   js::StableCellHasher<HeapPtr<JSObject*>>>;
  71   using Cache = WeakCache<ObjectMap>;
  72   Cache cache(JS::GetObjectZone(tenured1), cx);
  73
  74   cache.put(tenured1, 1);
  75   cache.put(tenured2, 2);
  76   cache.put(nursery1, 3);
  77   cache.put(nursery2, 4);
  78
  79   JS_GC(cx);
  80   CHECK(cache.has(tenured1));
  81   CHECK(cache.has(tenured2));
  82   CHECK(cache.has(nursery1));
  83   CHECK(cache.has(nursery2));
  84
  85   tenured2 = nursery2 = nullptr;
  86   JS_GC(cx);
  87   CHECK(cache.has(tenured1));
  88   CHECK(cache.has(nursery1));
  89   CHECK(cache.count() == 2);
  90
  91   return true;
  92 }
  93 END_TEST(testWeakCacheMap)
  94
  95 BEGIN_TEST(testWeakCacheMapWithUniquePtr) {
  96   JS::RootedObject tenured1(cx, JS_NewPlainObject(cx));
  97   JS::RootedObject tenured2(cx, JS_NewPlainObject(cx));
  98   JS_GC(cx);
  99   JS::RootedObject nursery1(cx, JS_NewPlainObject(cx));
 100   JS::RootedObject nursery2(cx, JS_NewPlainObject(cx));
 101
 102   using ObjectMap = js::GCHashMap<HeapPtr<JSObject*>, UniquePtr<uint32_t>,
 103                                   js::StableCellHasher<HeapPtr<JSObject*>>>;
 104   using Cache = WeakCache<ObjectMap>;
 105   Cache cache(JS::GetObjectZone(tenured1), cx);
 106
 107   cache.put(tenured1, MakeUnique<uint32_t>(1));
 108   cache.put(tenured2, MakeUnique<uint32_t>(2));
 109   cache.put(nursery1, MakeUnique<uint32_t>(3));
 110   cache.put(nursery2, MakeUnique<uint32_t>(4));
 111
 112   JS_GC(cx);
 113   CHECK(cache.has(tenured1));
 114   CHECK(cache.has(tenured2));
 115   CHECK(cache.has(nursery1));
 116   CHECK(cache.has(nursery2));
 117
 118   tenured2 = nursery2 = nullptr;
 119   JS_GC(cx);
 120   CHECK(cache.has(tenured1));
 121   CHECK(cache.has(nursery1));
 122   CHECK(cache.count() == 2);
 123
 124   return true;
 125 }
 126 END_TEST(testWeakCacheMapWithUniquePtr)
 127
 128 // Exercise WeakCache<GCVector>.
 129 BEGIN_TEST(testWeakCacheGCVector) {
 130   // Create two objects tenured and two in the nursery. If zeal is on,
 131   // this may fail and we'll get more tenured objects. That's fine:
 132   // the test will continue to work, it will just not test as much.
 133   JS::RootedObject tenured1(cx, JS_NewPlainObject(cx));
 134   JS::RootedObject tenured2(cx, JS_NewPlainObject(cx));
 135   JS_GC(cx);
 136   JS::RootedObject nursery1(cx, JS_NewPlainObject(cx));
 137   JS::RootedObject nursery2(cx, JS_NewPlainObject(cx));
 138
 139   using ObjectVector = WeakCache<GCVector<HeapPtr<JSObject*>>>;
 140   ObjectVector cache(JS::GetObjectZone(tenured1), cx);
 141
 142   CHECK(cache.append(tenured1));
 143   CHECK(cache.append(tenured2));
 144   CHECK(cache.append(nursery1));
 145   CHECK(cache.append(nursery2));
 146
 147   JS_GC(cx);
 148   CHECK(cache.get().length() == 4);
 149   CHECK(cache.get()[0] == tenured1);
 150   CHECK(cache.get()[1] == tenured2);
 151   CHECK(cache.get()[2] == nursery1);
 152   CHECK(cache.get()[3] == nursery2);
 153
 154   tenured2 = nursery2 = nullptr;
 155   JS_GC(cx);
 156   CHECK(cache.get().length() == 2);
 157   CHECK(cache.get()[0] == tenured1);
 158   CHECK(cache.get()[1] == nursery1);
 159
 160   return true;
 161 }
 162 END_TEST(testWeakCacheGCVector)
 163
 164 #ifdef JS_GC_ZEAL
 165
 166 // A simple structure that embeds an object pointer. We cripple the hash
 167 // implementation so that we can test hash table collisions.
 168 struct ObjectEntry {
 169   HeapPtr<JSObject*> obj;
 170   explicit ObjectEntry(JSObject* o) : obj(o) {}
 171   bool operator==(const ObjectEntry& other) const { return obj == other.obj; }
 172   bool traceWeak(JSTracer* trc) {
 173     return TraceWeakEdge(trc, &obj, "ObjectEntry::obj");
 174   }
 175 };
 176
 177 namespace js {
 178 template <>
 179 struct StableCellHasher<ObjectEntry> {
 180   using Key = ObjectEntry;
 181   using Lookup = JSObject*;
 182
 183   static bool maybeGetHash(const Lookup& l, HashNumber* hashOut) {
 184     if (!StableCellHasher<JSObject*>::maybeGetHash(l, hashOut)) {
 185       return false;
 186     }
 187     // Reduce hash code to single bit to generate hash collisions.
 188     *hashOut &= 0x1;
 189     return true;
 190   }
 191   static bool ensureHash(const Lookup& l, HashNumber* hashOut) {
 192     if (!StableCellHasher<JSObject*>::ensureHash(l, hashOut)) {
 193       return false;
 194     }
 195     // Reduce hash code to single bit to generate hash collisions.
 196     *hashOut &= 0x1;
 197     return true;
 198   }
 199   static HashNumber hash(const Lookup& l) {
 200     // Reduce hash code to single bit to generate hash collisions.
 201     return StableCellHasher<HeapPtr<JSObject*>>::hash(l) & 0x1;
 202   }
 203   static bool match(const Key& k, const Lookup& l) {
 204     return StableCellHasher<HeapPtr<JSObject*>>::match(k.obj, l);
 205   }
 206 };
 207 }  // namespace js
 208
 209 // A structure that contains a pointer to a JSObject but is keyed based on an
 210 // integer. This lets us test replacing dying entries in a set.
 211 struct NumberAndObjectEntry {
 212   uint32_t number;
 213   HeapPtr<JSObject*> obj;
 214
 215   NumberAndObjectEntry(uint32_t n, JSObject* o) : number(n), obj(o) {}
 216   bool operator==(const NumberAndObjectEntry& other) const {
 217     return number == other.number && obj == other.obj;
 218   }
 219   bool traceWeak(JSTracer* trc) {
 220     return TraceWeakEdge(trc, &obj, "NumberAndObjectEntry::obj");
 221   }
 222 };
 223
 224 struct NumberAndObjectLookup {
 225   uint32_t number;
 226   HeapPtr<JSObject*> obj;
 227
 228   NumberAndObjectLookup(uint32_t n, JSObject* o) : number(n), obj(o) {}
 229   MOZ_IMPLICIT NumberAndObjectLookup(const NumberAndObjectEntry& entry)
 230       : number(entry.number), obj(entry.obj) {}
 231 };
 232
 233 namespace js {
 234 template <>
 235 struct StableCellHasher<NumberAndObjectEntry> {
 236   using Key = NumberAndObjectEntry;
 237   using Lookup = NumberAndObjectLookup;
 238
 239   static bool maybeGetHash(const Lookup& l, HashNumber* hashOut) {
 240     if (!StableCellHasher<JSObject*>::maybeGetHash(l.obj, hashOut)) {
 241       return false;
 242     }
 243     *hashOut ^= l.number;
 244     return true;
 245   }
 246   static bool ensureHash(const Lookup& l, HashNumber* hashOut) {
 247     if (!StableCellHasher<JSObject*>::ensureHash(l.obj, hashOut)) {
 248       return false;
 249     }
 250     *hashOut ^= l.number;
 251     return true;
 252   }
 253   static HashNumber hash(const Lookup& l) {
 254     return StableCellHasher<HeapPtr<JSObject*>>::hash(l.obj) ^ l.number;
 255   }
 256   static bool match(const Key& k, const Lookup& l) {
 257     return k.number == l.number &&
 258            StableCellHasher<HeapPtr<JSObject*>>::match(k.obj, l.obj);
 259   }
 260 };
 261 }  // namespace js
 262
 263 BEGIN_TEST(testIncrementalWeakCacheSweeping) {
 264   AutoLeaveZeal nozeal(cx);
 265
 266   JS_SetGCParameter(cx, JSGC_INCREMENTAL_GC_ENABLED, true);
 267   JS::SetGCZeal(cx, 17, 1000000);
 268
 269   CHECK(TestSet());
 270   CHECK(TestMap());
 271   CHECK(TestReplaceDyingInSet());
 272   CHECK(TestReplaceDyingInMap());
 273   CHECK(TestUniqueIDLookups());
 274
 275   JS::SetGCZeal(cx, 0, 0);
 276   JS_SetGCParameter(cx, JSGC_INCREMENTAL_GC_ENABLED, false);
 277
 278   return true;
 279 }
 280
 281 template <typename Cache>
 282 bool GCUntilCacheSweep(JSContext* cx, const Cache& cache) {
 283   CHECK(!IsIncrementalGCInProgress(cx));
 284
 285   JS::Zone* zone = JS::GetObjectZone(global);
 286   JS::PrepareZoneForGC(cx, zone);
 287   JS::SliceBudget budget(JS::WorkBudget(1));
 288   cx->runtime()->gc.startDebugGC(JS::GCOptions::Normal, budget);
 289
 290   CHECK(IsIncrementalGCInProgress(cx));
 291   CHECK(zone->isGCSweeping());
 292   CHECK(cache.needsIncrementalBarrier());
 293
 294   return true;
 295 }
 296
 297 template <typename Cache>
 298 bool SweepCacheAndFinishGC(JSContext* cx, const Cache& cache) {
 299   CHECK(IsIncrementalGCInProgress(cx));
 300
 301   PrepareForIncrementalGC(cx);
 302   IncrementalGCSlice(cx, JS::GCReason::API, JS::SliceBudget::unlimited());
 303
 304   JS::Zone* zone = JS::GetObjectZone(global);
 305   CHECK(!IsIncrementalGCInProgress(cx));
 306   CHECK(!zone->isCollecting());
 307   CHECK(!cache.needsIncrementalBarrier());
 308
 309   return true;
 310 }
 311
 312 bool TestSet() {
 313   using ObjectSet =
 314       GCHashSet<HeapPtr<JSObject*>, StableCellHasher<HeapPtr<JSObject*>>,
 315                 TempAllocPolicy>;
 316   using Cache = WeakCache<ObjectSet>;
 317   Cache cache(JS::GetObjectZone(global), cx);
 318
 319   // Sweep empty cache.
 320
 321   CHECK(cache.empty());
 322   JS_GC(cx);
 323   CHECK(cache.empty());
 324
 325   // Add an entry while sweeping.
 326
 327   JS::RootedObject obj1(cx, JS_NewPlainObject(cx));
 328   JS::RootedObject obj2(cx, JS_NewPlainObject(cx));
 329   JS::RootedObject obj3(cx, JS_NewPlainObject(cx));
 330   JS::RootedObject obj4(cx, JS_NewPlainObject(cx));
 331   CHECK(obj1);
 332   CHECK(obj2);
 333   CHECK(obj3);
 334   CHECK(obj4);
 335
 336   CHECK(!cache.has(obj1));
 337   CHECK(cache.put(obj1));
 338   CHECK(cache.count() == 1);
 339   CHECK(cache.has(obj1));
 340   CHECK(*cache.lookup(obj1) == obj1);
 341
 342   CHECK(GCUntilCacheSweep(cx, cache));
 343
 344   CHECK(!cache.has(obj2));
 345   CHECK(cache.put(obj2));
 346   CHECK(cache.has(obj2));
 347   CHECK(*cache.lookup(obj2) == obj2);
 348
 349   CHECK(SweepCacheAndFinishGC(cx, cache));
 350
 351   CHECK(cache.count() == 2);
 352   CHECK(cache.has(obj1));
 353   CHECK(cache.has(obj2));
 354
 355   // Test dying entries are not found while sweeping.
 356
 357   CHECK(cache.put(obj3));
 358   CHECK(cache.put(obj4));
 359   void* old3 = obj3;
 360   void* old4 = obj4;
 361   obj3 = obj4 = nullptr;
 362
 363   CHECK(GCUntilCacheSweep(cx, cache));
 364
 365   CHECK(cache.has(obj1));
 366   CHECK(cache.has(obj2));
 367   CHECK(!cache.has(static_cast<JSObject*>(old3)));
 368   CHECK(!cache.has(static_cast<JSObject*>(old4)));
 369
 370   size_t count = 0;
 371   for (auto r = cache.all(); !r.empty(); r.popFront()) {
 372     CHECK(r.front() == obj1 || r.front() == obj2);
 373     count++;
 374   }
 375   CHECK(count == 2);
 376
 377   CHECK(SweepCacheAndFinishGC(cx, cache));
 378
 379   CHECK(cache.count() == 2);
 380
 381   // Test lookupForAdd while sweeping.
 382
 383   obj3 = JS_NewPlainObject(cx);
 384   obj4 = JS_NewPlainObject(cx);
 385   CHECK(obj3);
 386   CHECK(obj4);
 387
 388   CHECK(cache.lookupForAdd(obj1));
 389   CHECK(*cache.lookupForAdd(obj1) == obj1);
 390
 391   auto addp = cache.lookupForAdd(obj3);
 392   CHECK(!addp);
 393   CHECK(cache.add(addp, obj3));
 394   CHECK(cache.has(obj3));
 395
 396   CHECK(GCUntilCacheSweep(cx, cache));
 397
 398   addp = cache.lookupForAdd(obj4);
 399   CHECK(!addp);
 400   CHECK(cache.add(addp, obj4));
 401   CHECK(cache.has(obj4));
 402
 403   CHECK(SweepCacheAndFinishGC(cx, cache));
 404
 405   CHECK(cache.count() == 4);
 406   CHECK(cache.has(obj3));
 407   CHECK(cache.has(obj4));
 408
 409   // Test remove while sweeping.
 410
 411   cache.remove(obj3);
 412
 413   CHECK(GCUntilCacheSweep(cx, cache));
 414
 415   cache.remove(obj4);
 416
 417   CHECK(SweepCacheAndFinishGC(cx, cache));
 418
 419   CHECK(cache.count() == 2);
 420   CHECK(!cache.has(obj3));
 421   CHECK(!cache.has(obj4));
 422
 423   // Test putNew while sweeping.
 424
 425   CHECK(GCUntilCacheSweep(cx, cache));
 426
 427   CHECK(cache.putNew(obj3));
 428   CHECK(cache.putNew(obj4, obj4));
 429
 430   CHECK(SweepCacheAndFinishGC(cx, cache));
 431
 432   CHECK(cache.count() == 4);
 433   CHECK(cache.has(obj3));
 434   CHECK(cache.has(obj4));
 435
 436   cache.clear();
 437
 438   return true;
 439 }
 440
 441 bool TestMap() {
 442   using ObjectMap =
 443       GCHashMap<HeapPtr<JSObject*>, uint32_t,
 444                 StableCellHasher<HeapPtr<JSObject*>>, TempAllocPolicy>;
 445   using Cache = WeakCache<ObjectMap>;
 446   Cache cache(JS::GetObjectZone(global), cx);
 447
 448   // Sweep empty cache.
 449
 450   CHECK(cache.empty());
 451   JS_GC(cx);
 452   CHECK(cache.empty());
 453
 454   // Add an entry while sweeping.
 455
 456   JS::RootedObject obj1(cx, JS_NewPlainObject(cx));
 457   JS::RootedObject obj2(cx, JS_NewPlainObject(cx));
 458   JS::RootedObject obj3(cx, JS_NewPlainObject(cx));
 459   JS::RootedObject obj4(cx, JS_NewPlainObject(cx));
 460   CHECK(obj1);
 461   CHECK(obj2);
 462   CHECK(obj3);
 463   CHECK(obj4);
 464
 465   CHECK(!cache.has(obj1));
 466   CHECK(cache.put(obj1, 1));
 467   CHECK(cache.count() == 1);
 468   CHECK(cache.has(obj1));
 469   CHECK(cache.lookup(obj1)->key() == obj1);
 470
 471   CHECK(GCUntilCacheSweep(cx, cache));
 472   CHECK(cache.needsIncrementalBarrier());
 473
 474   CHECK(!cache.has(obj2));
 475   CHECK(cache.put(obj2, 2));
 476   CHECK(cache.has(obj2));
 477   CHECK(cache.lookup(obj2)->key() == obj2);
 478
 479   CHECK(SweepCacheAndFinishGC(cx, cache));
 480   CHECK(!cache.needsIncrementalBarrier());
 481
 482   CHECK(cache.count() == 2);
 483   CHECK(cache.has(obj1));
 484   CHECK(cache.has(obj2));
 485
 486   // Test iteration.
 487
 488   CHECK(cache.put(obj3, 3));
 489   CHECK(cache.put(obj4, 4));
 490   void* old3 = obj3;
 491   void* old4 = obj4;
 492   obj3 = obj4 = nullptr;
 493
 494   CHECK(GCUntilCacheSweep(cx, cache));
 495
 496   CHECK(cache.has(obj1));
 497   CHECK(cache.has(obj2));
 498   CHECK(!cache.has(static_cast<JSObject*>(old3)));
 499   CHECK(!cache.has(static_cast<JSObject*>(old4)));
 500
 501   size_t count = 0;
 502   for (auto r = cache.all(); !r.empty(); r.popFront()) {
 503     CHECK(r.front().key() == obj1 || r.front().key() == obj2);
 504     count++;
 505   }
 506   CHECK(count == 2);
 507
 508   CHECK(SweepCacheAndFinishGC(cx, cache));
 509
 510   CHECK(cache.count() == 2);
 511
 512   // Test lookupForAdd while sweeping.
 513
 514   obj3 = JS_NewPlainObject(cx);
 515   obj4 = JS_NewPlainObject(cx);
 516   CHECK(obj3);
 517   CHECK(obj4);
 518
 519   CHECK(cache.lookupForAdd(obj1));
 520   CHECK(cache.lookupForAdd(obj1)->key() == obj1);
 521
 522   auto addp = cache.lookupForAdd(obj3);
 523   CHECK(!addp);
 524   CHECK(cache.add(addp, obj3, 3));
 525   CHECK(cache.has(obj3));
 526
 527   CHECK(GCUntilCacheSweep(cx, cache));
 528
 529   addp = cache.lookupForAdd(obj4);
 530   CHECK(!addp);
 531   CHECK(cache.add(addp, obj4, 4));
 532   CHECK(cache.has(obj4));
 533
 534   CHECK(SweepCacheAndFinishGC(cx, cache));
 535
 536   CHECK(cache.count() == 4);
 537   CHECK(cache.has(obj3));
 538   CHECK(cache.has(obj4));
 539
 540   // Test remove while sweeping.
 541
 542   cache.remove(obj3);
 543
 544   CHECK(GCUntilCacheSweep(cx, cache));
 545
 546   cache.remove(obj4);
 547
 548   CHECK(SweepCacheAndFinishGC(cx, cache));
 549
 550   CHECK(cache.count() == 2);
 551   CHECK(!cache.has(obj3));
 552   CHECK(!cache.has(obj4));
 553
 554   // Test putNew while sweeping.
 555
 556   CHECK(GCUntilCacheSweep(cx, cache));
 557
 558   CHECK(cache.putNew(obj3, 3));
 559   CHECK(cache.putNew(obj4, 4));
 560
 561   CHECK(SweepCacheAndFinishGC(cx, cache));
 562
 563   CHECK(cache.count() == 4);
 564   CHECK(cache.has(obj3));
 565   CHECK(cache.has(obj4));
 566
 567   cache.clear();
 568
 569   return true;
 570 }
 571
 572 bool TestReplaceDyingInSet() {
 573   // Test replacing dying entries with ones that have the same key using the
 574   // various APIs.
 575
 576   using Cache = WeakCache<
 577       GCHashSet<NumberAndObjectEntry, StableCellHasher<NumberAndObjectEntry>,
 578                 TempAllocPolicy>>;
 579   Cache cache(JS::GetObjectZone(global), cx);
 580
 581   RootedObject value1(cx, JS_NewPlainObject(cx));
 582   RootedObject value2(cx, JS_NewPlainObject(cx));
 583   CHECK(value1);
 584   CHECK(value2);
 585
 586   CHECK(cache.put(NumberAndObjectEntry(1, value1)));
 587   CHECK(cache.put(NumberAndObjectEntry(2, value2)));
 588   CHECK(cache.put(NumberAndObjectEntry(3, value2)));
 589   CHECK(cache.put(NumberAndObjectEntry(4, value2)));
 590   CHECK(cache.put(NumberAndObjectEntry(5, value2)));
 591   CHECK(cache.put(NumberAndObjectEntry(6, value2)));
 592   CHECK(cache.put(NumberAndObjectEntry(7, value2)));
 593
 594   value2 = nullptr;
 595   CHECK(GCUntilCacheSweep(cx, cache));
 596
 597   CHECK(!cache.has(NumberAndObjectLookup(2, value1)));
 598   CHECK(!cache.has(NumberAndObjectLookup(3, value1)));
 599   CHECK(!cache.has(NumberAndObjectLookup(4, value1)));
 600   CHECK(!cache.has(NumberAndObjectLookup(5, value1)));
 601   CHECK(!cache.has(NumberAndObjectLookup(6, value1)));
 602
 603   auto ptr = cache.lookupForAdd(NumberAndObjectLookup(2, value1));
 604   CHECK(!ptr);
 605   CHECK(cache.add(ptr, NumberAndObjectEntry(2, value1)));
 606
 607   auto ptr2 = cache.lookupForAdd(NumberAndObjectLookup(3, value1));
 608   CHECK(!ptr2);
 609   CHECK(cache.relookupOrAdd(ptr2, NumberAndObjectLookup(3, value1),
 610                             NumberAndObjectEntry(3, value1)));
 611
 612   CHECK(cache.put(NumberAndObjectEntry(4, value1)));
 613   CHECK(cache.putNew(NumberAndObjectEntry(5, value1)));
 614
 615   CHECK(cache.putNew(NumberAndObjectLookup(6, value1),
 616                      NumberAndObjectEntry(6, value1)));
 617
 618   CHECK(SweepCacheAndFinishGC(cx, cache));
 619
 620   CHECK(cache.count() == 6);
 621   CHECK(cache.has(NumberAndObjectLookup(1, value1)));
 622   CHECK(cache.has(NumberAndObjectLookup(2, value1)));
 623   CHECK(cache.has(NumberAndObjectLookup(3, value1)));
 624   CHECK(cache.has(NumberAndObjectLookup(4, value1)));
 625   CHECK(cache.has(NumberAndObjectLookup(5, value1)));
 626   CHECK(cache.has(NumberAndObjectLookup(6, value1)));
 627
 628   return true;
 629 }
 630
 631 bool TestReplaceDyingInMap() {
 632   // Test replacing dying entries with ones that have the same key using the
 633   // various APIs.
 634
 635   using Cache = WeakCache<GCHashMap<uint32_t, HeapPtr<JSObject*>,
 636                                     DefaultHasher<uint32_t>, TempAllocPolicy>>;
 637   Cache cache(JS::GetObjectZone(global), cx);
 638
 639   RootedObject value1(cx, JS_NewPlainObject(cx));
 640   RootedObject value2(cx, JS_NewPlainObject(cx));
 641   CHECK(value1);
 642   CHECK(value2);
 643
 644   CHECK(cache.put(1, value1));
 645   CHECK(cache.put(2, value2));
 646   CHECK(cache.put(3, value2));
 647   CHECK(cache.put(4, value2));
 648   CHECK(cache.put(5, value2));
 649   CHECK(cache.put(6, value2));
 650
 651   value2 = nullptr;
 652   CHECK(GCUntilCacheSweep(cx, cache));
 653
 654   CHECK(!cache.has(2));
 655   CHECK(!cache.has(3));
 656   CHECK(!cache.has(4));
 657   CHECK(!cache.has(5));
 658   CHECK(!cache.has(6));
 659
 660   auto ptr = cache.lookupForAdd(2);
 661   CHECK(!ptr);
 662   CHECK(cache.add(ptr, 2, value1));
 663
 664   auto ptr2 = cache.lookupForAdd(3);
 665   CHECK(!ptr2);
 666   CHECK(cache.add(ptr2, 3, HeapPtr<JSObject*>()));
 667
 668   auto ptr3 = cache.lookupForAdd(4);
 669   CHECK(!ptr3);
 670   CHECK(cache.relookupOrAdd(ptr3, 4, value1));
 671
 672   CHECK(cache.put(5, value1));
 673   CHECK(cache.putNew(6, value1));
 674
 675   CHECK(SweepCacheAndFinishGC(cx, cache));
 676
 677   CHECK(cache.count() == 6);
 678   CHECK(cache.lookup(1)->value() == value1);
 679   CHECK(cache.lookup(2)->value() == value1);
 680   CHECK(cache.lookup(3)->value() == nullptr);
 681   CHECK(cache.lookup(4)->value() == value1);
 682   CHECK(cache.lookup(5)->value() == value1);
 683   CHECK(cache.lookup(6)->value() == value1);
 684
 685   return true;
 686 }
 687
 688 bool TestUniqueIDLookups() {
 689   // Test hash table lookups during incremental sweeping where the hash is
 690   // generated based on a unique ID. The problem is that the unique ID table
 691   // will have already been swept by this point so looking up a dead pointer
 692   // in the table will fail. This lookup happens if we try to match a live key
 693   // against a dead table entry with the same hash code.
 694
 695   const size_t DeadFactor = 3;
 696   const size_t ObjectCount = 100;
 697
 698   using Cache = WeakCache<
 699       GCHashSet<ObjectEntry, StableCellHasher<ObjectEntry>, TempAllocPolicy>>;
 700   Cache cache(JS::GetObjectZone(global), cx);
 701
 702   Rooted<GCVector<JSObject*, 0, SystemAllocPolicy>> liveObjects(cx);
 703
 704   for (size_t j = 0; j < ObjectCount; j++) {
 705     JSObject* obj = JS_NewPlainObject(cx);
 706     CHECK(obj);
 707     CHECK(cache.put(obj));
 708     if (j % DeadFactor == 0) {
 709       CHECK(liveObjects.get().append(obj));
 710     }
 711   }
 712
 713   CHECK(cache.count() == ObjectCount);
 714
 715   CHECK(GCUntilCacheSweep(cx, cache));
 716
 717   for (size_t j = 0; j < liveObjects.length(); j++) {
 718     CHECK(cache.has(liveObjects[j]));
 719   }
 720
 721   CHECK(SweepCacheAndFinishGC(cx, cache));
 722
 723   CHECK(cache.count() == liveObjects.length());
 724
 725   return true;
 726 }
 727
 728 END_TEST(testIncrementalWeakCacheSweeping)
 729
 730 #endif  // defined JS_GC_ZEAL