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