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