js/src/gc/WeakMap-inl.h

   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  * This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #ifndef gc_WeakMap_inl_h
   8 #define gc_WeakMap_inl_h
   9
  10 #include "gc/WeakMap.h"
  11
  12 #include "mozilla/DebugOnly.h"
  13 #include "mozilla/Maybe.h"
  14
  15 #include <algorithm>
  16 #include <type_traits>
  17
  18 #include "gc/GCLock.h"
  19 #include "gc/Marking.h"
  20 #include "gc/Zone.h"
  21 #include "js/TraceKind.h"
  22 #include "vm/JSContext.h"
  23
  24 #include "gc/StableCellHasher-inl.h"
  25
  26 namespace js {
  27
  28 namespace gc::detail {
  29
  30 // Return the effective cell color given the current marking state.
  31 // This must be kept in sync with ShouldMark in Marking.cpp.
  32 template <typename T>
  33 static CellColor GetEffectiveColor(GCMarker* marker, const T& item) {
  34   Cell* cell = ToMarkable(item);
  35   if (!cell->isTenured()) {
  36     return CellColor::Black;
  37   }
  38   const TenuredCell& t = cell->asTenured();
  39   if (!t.zoneFromAnyThread()->shouldMarkInZone(marker->markColor())) {
  40     return CellColor::Black;
  41   }
  42   MOZ_ASSERT(t.runtimeFromAnyThread() == marker->runtime());
  43   return t.color();
  44 }
  45
  46 // Only objects have delegates, so default to returning nullptr. Note that some
  47 // compilation units will only ever use the object version.
  48 static MOZ_MAYBE_UNUSED JSObject* GetDelegateInternal(gc::Cell* key) {
  49   return nullptr;
  50 }
  51
  52 static MOZ_MAYBE_UNUSED JSObject* GetDelegateInternal(JSObject* key) {
  53   JSObject* delegate = UncheckedUnwrapWithoutExpose(key);
  54   return (key == delegate) ? nullptr : delegate;
  55 }
  56
  57 // Use a helper function to do overload resolution to handle cases like
  58 // Heap<ObjectSubclass*>: find everything that is convertible to JSObject* (and
  59 // avoid calling barriers).
  60 template <typename T>
  61 static inline JSObject* GetDelegate(const T& key) {
  62   return GetDelegateInternal(key);
  63 }
  64
  65 template <>
  66 inline JSObject* GetDelegate(gc::Cell* const&) = delete;
  67
  68 }  // namespace gc::detail
  69
  70 // Weakmap entry -> value edges are only visible if the map is traced, which
  71 // only happens if the map zone is being collected. If the map and the value
  72 // were in different zones, then we could have a case where the map zone is not
  73 // collecting but the value zone is, and incorrectly free a value that is
  74 // reachable solely through weakmaps.
  75 template <class K, class V>
  76 void WeakMap<K, V>::assertMapIsSameZoneWithValue(const V& v) {
  77 #ifdef DEBUG
  78   gc::Cell* cell = gc::ToMarkable(v);
  79   if (cell) {
  80     Zone* cellZone = cell->zoneFromAnyThread();
  81     MOZ_ASSERT(zone() == cellZone || cellZone->isAtomsZone());
  82   }
  83 #endif
  84 }
  85
  86 template <class K, class V>
  87 WeakMap<K, V>::WeakMap(JSContext* cx, JSObject* memOf)
  88     : WeakMap(cx->zone(), memOf) {}
  89
  90 template <class K, class V>
  91 WeakMap<K, V>::WeakMap(JS::Zone* zone, JSObject* memOf)
  92     : Base(zone), WeakMapBase(memOf, zone) {
  93   using ElemType = typename K::ElementType;
  94   using NonPtrType = std::remove_pointer_t<ElemType>;
  95
  96   // The object's TraceKind needs to be added to CC graph if this object is
  97   // used as a WeakMap key, otherwise the key is considered to be pointed from
  98   // somewhere unknown, and results in leaking the subgraph which contains the
  99   // key. See the comments in NoteWeakMapsTracer::trace for more details.
 100   static_assert(JS::IsCCTraceKind(NonPtrType::TraceKind),
 101                 "Object's TraceKind should be added to CC graph.");
 102
 103   zone->gcWeakMapList().insertFront(this);
 104   if (zone->gcState() > Zone::Prepare) {
 105     mapColor = CellColor::Black;
 106   }
 107 }
 108
 109 // If the entry is live, ensure its key and value are marked. Also make sure the
 110 // key is at least as marked as min(map, delegate), so it cannot get discarded
 111 // and then recreated by rewrapping the delegate.
 112 //
 113 // Optionally adds edges to the ephemeron edges table for any keys (or
 114 // delegates) where future changes to their mark color would require marking the
 115 // value (or the key).
 116 template <class K, class V>
 117 bool WeakMap<K, V>::markEntry(GCMarker* marker, K& key, V& value,
 118                               bool populateWeakKeysTable) {
 119 #ifdef DEBUG
 120   MOZ_ASSERT(mapColor);
 121   if (marker->isParallelMarking()) {
 122     marker->runtime()->gc.assertCurrentThreadHasLockedGC();
 123   }
 124 #endif
 125
 126   bool marked = false;
 127   CellColor markColor = marker->markColor();
 128   CellColor keyColor = gc::detail::GetEffectiveColor(marker, key);
 129   JSObject* delegate = gc::detail::GetDelegate(key);
 130   JSTracer* trc = marker->tracer();
 131
 132   if (delegate) {
 133     CellColor delegateColor = gc::detail::GetEffectiveColor(marker, delegate);
 134     // The key needs to stay alive while both the delegate and map are live.
 135     CellColor proxyPreserveColor = std::min(delegateColor, mapColor);
 136     if (keyColor < proxyPreserveColor) {
 137       MOZ_ASSERT(markColor >= proxyPreserveColor);
 138       if (markColor == proxyPreserveColor) {
 139         TraceWeakMapKeyEdge(trc, zone(), &key,
 140                             "proxy-preserved WeakMap entry key");
 141         MOZ_ASSERT(key->color() >= proxyPreserveColor);
 142         marked = true;
 143         keyColor = proxyPreserveColor;
 144       }
 145     }
 146   }
 147
 148   gc::Cell* cellValue = gc::ToMarkable(value);
 149   if (keyColor) {
 150     if (cellValue) {
 151       CellColor targetColor = std::min(mapColor, keyColor);
 152       CellColor valueColor = gc::detail::GetEffectiveColor(marker, cellValue);
 153       if (valueColor < targetColor) {
 154         MOZ_ASSERT(markColor >= targetColor);
 155         if (markColor == targetColor) {
 156           TraceEdge(trc, &value, "WeakMap entry value");
 157           MOZ_ASSERT(cellValue->color() >= targetColor);
 158           marked = true;
 159         }
 160       }
 161     }
 162   }
 163
 164   if (populateWeakKeysTable) {
 165     // Note that delegateColor >= keyColor because marking a key marks its
 166     // delegate, so we only need to check whether keyColor < mapColor to tell
 167     // this.
 168
 169     if (keyColor < mapColor) {
 170       MOZ_ASSERT(trc->weakMapAction() == JS::WeakMapTraceAction::Expand);
 171       // The final color of the key is not yet known. Record this weakmap and
 172       // the lookup key in the list of weak keys. If the key has a delegate,
 173       // then the lookup key is the delegate (because marking the key will end
 174       // up marking the delegate and thereby mark the entry.)
 175       gc::TenuredCell* tenuredValue = nullptr;
 176       if (cellValue && cellValue->isTenured()) {
 177         tenuredValue = &cellValue->asTenured();
 178       }
 179
 180       if (!this->addImplicitEdges(key, delegate, tenuredValue)) {
 181         marker->abortLinearWeakMarking();
 182       }
 183     }
 184   }
 185
 186   return marked;
 187 }
 188
 189 template <class K, class V>
 190 void WeakMap<K, V>::trace(JSTracer* trc) {
 191   MOZ_ASSERT(isInList());
 192
 193   TraceNullableEdge(trc, &memberOf, "WeakMap owner");
 194
 195   if (trc->isMarkingTracer()) {
 196     MOZ_ASSERT(trc->weakMapAction() == JS::WeakMapTraceAction::Expand);
 197     auto* marker = GCMarker::fromTracer(trc);
 198
 199     // Lock if we are marking in parallel to synchronize updates to:
 200     //  - the weak map's color
 201     //  - the ephemeron edges table
 202     mozilla::Maybe<AutoLockGC> lock;
 203     if (marker->isParallelMarking()) {
 204       lock.emplace(marker->runtime());
 205     }
 206
 207     // Don't downgrade the map color from black to gray. This can happen when a
 208     // barrier pushes the map object onto the black mark stack when it's
 209     // already present on the gray mark stack, which is marked later.
 210     if (mapColor < marker->markColor()) {
 211       mapColor = marker->markColor();
 212       (void)markEntries(marker);
 213     }
 214     return;
 215   }
 216
 217   if (trc->weakMapAction() == JS::WeakMapTraceAction::Skip) {
 218     return;
 219   }
 220
 221   // Trace keys only if weakMapAction() says to.
 222   if (trc->weakMapAction() == JS::WeakMapTraceAction::TraceKeysAndValues) {
 223     for (Enum e(*this); !e.empty(); e.popFront()) {
 224       TraceWeakMapKeyEdge(trc, zone(), &e.front().mutableKey(),
 225                           "WeakMap entry key");
 226     }
 227   }
 228
 229   // Always trace all values (unless weakMapAction() is Skip).
 230   for (Range r = Base::all(); !r.empty(); r.popFront()) {
 231     TraceEdge(trc, &r.front().value(), "WeakMap entry value");
 232   }
 233 }
 234
 235 bool WeakMapBase::addImplicitEdges(gc::Cell* key, gc::Cell* delegate,
 236                                    gc::TenuredCell* value) {
 237   if (delegate) {
 238     auto& edgeTable = delegate->zone()->gcEphemeronEdges(delegate);
 239     auto* p = edgeTable.get(delegate);
 240
 241     gc::EphemeronEdgeVector newVector;
 242     gc::EphemeronEdgeVector& edges = p ? p->value : newVector;
 243
 244     // Add a <weakmap, delegate> -> key edge: the key must be preserved for
 245     // future lookups until either the weakmap or the delegate dies.
 246     gc::EphemeronEdge keyEdge{mapColor, key};
 247     if (!edges.append(keyEdge)) {
 248       return false;
 249     }
 250
 251     if (value) {
 252       gc::EphemeronEdge valueEdge{mapColor, value};
 253       if (!edges.append(valueEdge)) {
 254         return false;
 255       }
 256     }
 257
 258     if (!p) {
 259       return edgeTable.put(delegate, std::move(newVector));
 260     }
 261
 262     return true;
 263   }
 264
 265   // No delegate. Insert just the key -> value edge.
 266
 267   if (!value) {
 268     return true;
 269   }
 270
 271   auto& edgeTable = key->zone()->gcEphemeronEdges(key);
 272   auto* p = edgeTable.get(key);
 273   gc::EphemeronEdge valueEdge{mapColor, value};
 274   if (p) {
 275     return p->value.append(valueEdge);
 276   }
 277
 278   gc::EphemeronEdgeVector edges;
 279   MOZ_ALWAYS_TRUE(edges.append(valueEdge));
 280   return edgeTable.put(key, std::move(edges));
 281 }
 282
 283 template <class K, class V>
 284 bool WeakMap<K, V>::markEntries(GCMarker* marker) {
 285   // This method is called whenever the map's mark color changes. Mark values
 286   // (and keys with delegates) as required for the new color and populate the
 287   // ephemeron edges if we're in incremental marking mode.
 288
 289 #ifdef DEBUG
 290   if (marker->isParallelMarking()) {
 291     marker->runtime()->gc.assertCurrentThreadHasLockedGC();
 292   }
 293 #endif
 294
 295   MOZ_ASSERT(mapColor);
 296   bool markedAny = false;
 297
 298   // If we don't populate the weak keys table now then we do it when we enter
 299   // weak marking mode.
 300   bool populateWeakKeysTable =
 301       marker->incrementalWeakMapMarkingEnabled || marker->isWeakMarking();
 302
 303   for (Enum e(*this); !e.empty(); e.popFront()) {
 304     if (markEntry(marker, e.front().mutableKey(), e.front().value(),
 305                   populateWeakKeysTable)) {
 306       markedAny = true;
 307     }
 308   }
 309
 310   return markedAny;
 311 }
 312
 313 template <class K, class V>
 314 void WeakMap<K, V>::traceWeakEdges(JSTracer* trc) {
 315   // Remove all entries whose keys remain unmarked.
 316   for (Enum e(*this); !e.empty(); e.popFront()) {
 317     if (!TraceWeakEdge(trc, &e.front().mutableKey(), "WeakMap key")) {
 318       e.removeFront();
 319     }
 320   }
 321
 322 #if DEBUG
 323   // Once we've swept, all remaining edges should stay within the known-live
 324   // part of the graph.
 325   assertEntriesNotAboutToBeFinalized();
 326 #endif
 327 }
 328
 329 // memberOf can be nullptr, which means that the map is not part of a JSObject.
 330 template <class K, class V>
 331 void WeakMap<K, V>::traceMappings(WeakMapTracer* tracer) {
 332   for (Range r = Base::all(); !r.empty(); r.popFront()) {
 333     gc::Cell* key = gc::ToMarkable(r.front().key());
 334     gc::Cell* value = gc::ToMarkable(r.front().value());
 335     if (key && value) {
 336       tracer->trace(memberOf, JS::GCCellPtr(r.front().key().get()),
 337                     JS::GCCellPtr(r.front().value().get()));
 338     }
 339   }
 340 }
 341
 342 template <class K, class V>
 343 bool WeakMap<K, V>::findSweepGroupEdges() {
 344   // For weakmap keys with delegates in a different zone, add a zone edge to
 345   // ensure that the delegate zone finishes marking before the key zone.
 346   JS::AutoSuppressGCAnalysis nogc;
 347   for (Range r = all(); !r.empty(); r.popFront()) {
 348     const K& key = r.front().key();
 349
 350     // If the key type doesn't have delegates, then this will always return
 351     // nullptr and the optimizer can remove the entire body of this function.
 352     JSObject* delegate = gc::detail::GetDelegate(key);
 353     if (!delegate) {
 354       continue;
 355     }
 356
 357     // Marking a WeakMap key's delegate will mark the key, so process the
 358     // delegate zone no later than the key zone.
 359     Zone* delegateZone = delegate->zone();
 360     Zone* keyZone = key->zone();
 361     if (delegateZone != keyZone && delegateZone->isGCMarking() &&
 362         keyZone->isGCMarking()) {
 363       if (!delegateZone->addSweepGroupEdgeTo(keyZone)) {
 364         return false;
 365       }
 366     }
 367   }
 368   return true;
 369 }
 370
 371 template <class K, class V>
 372 size_t WeakMap<K, V>::sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) {
 373   return mallocSizeOf(this) + shallowSizeOfExcludingThis(mallocSizeOf);
 374 }
 375
 376 #if DEBUG
 377 template <class K, class V>
 378 void WeakMap<K, V>::assertEntriesNotAboutToBeFinalized() {
 379   for (Range r = Base::all(); !r.empty(); r.popFront()) {
 380     UnbarrieredKey k = r.front().key();
 381     MOZ_ASSERT(!gc::IsAboutToBeFinalizedUnbarriered(k));
 382     JSObject* delegate = gc::detail::GetDelegate(k);
 383     if (delegate) {
 384       MOZ_ASSERT(!gc::IsAboutToBeFinalizedUnbarriered(delegate),
 385                  "weakmap marking depends on a key tracing its delegate");
 386     }
 387     MOZ_ASSERT(!gc::IsAboutToBeFinalized(r.front().value()));
 388   }
 389 }
 390 #endif
 391
 392 #ifdef JS_GC_ZEAL
 393 template <class K, class V>
 394 bool WeakMap<K, V>::checkMarking() const {
 395   bool ok = true;
 396   for (Range r = Base::all(); !r.empty(); r.popFront()) {
 397     gc::Cell* key = gc::ToMarkable(r.front().key());
 398     gc::Cell* value = gc::ToMarkable(r.front().value());
 399     if (key && value) {
 400       if (!gc::CheckWeakMapEntryMarking(this, key, value)) {
 401         ok = false;
 402       }
 403     }
 404   }
 405   return ok;
 406 }
 407 #endif
 408
 409 }  // namespace js
 410
 411 #endif /* gc_WeakMap_inl_h */