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/. */
10 #include "mozilla/Atomics.h"
11 #include "mozilla/LinkedList.h"
13 #include "gc/Barrier.h"
14 #include "gc/Marking.h"
15 #include "gc/Tracer.h"
17 #include "gc/ZoneAllocator.h"
18 #include "js/HashTable.h"
19 #include "js/HeapAPI.h"
31 extern void DumpWeakMapLog(JSRuntime
* rt
);
37 #if defined(JS_GC_ZEAL) || defined(DEBUG)
38 // Check whether a weak map entry is marked correctly.
39 bool CheckWeakMapEntryMarking(const WeakMapBase
* map
, Cell
* key
, Cell
* value
);
44 // A subclass template of js::HashMap whose keys and values may be
45 // garbage-collected. When a key is collected, the table entry disappears,
46 // dropping its reference to the value.
50 // A WeakMap entry is live if and only if both the WeakMap and the entry's
51 // key are live. An entry holds a strong reference to its value.
53 // You must call this table's 'trace' method when its owning object is reached
54 // by the garbage collection tracer. Once a table is known to be live, the
55 // implementation takes care of the special weak marking (ie, marking through
56 // the implicit edges stored in the map) and of removing (sweeping) table
57 // entries when collection is complete.
59 // WeakMaps are marked with an incremental linear-time algorithm that handles
60 // all orderings of map and key marking. The basic algorithm is:
62 // At first while marking, do nothing special when marking WeakMap keys (there
63 // is no straightforward way to know whether a particular object is being used
64 // as a key in some weakmap.) When a WeakMap is marked, scan through it to mark
65 // all entries with live keys, and collect all unmarked keys into a "weak keys"
68 // At some point, everything reachable has been marked. At this point, enter
69 // "weak marking mode". In this mode, whenever any object is marked, look it up
70 // in the weak keys table to see if it is the key for any WeakMap entry and if
71 // so, mark the value. When entering weak marking mode, scan the weak key table
72 // to find all keys that have been marked since we added them to the table, and
73 // mark those entries.
75 // In addition, we want weakmap marking to work incrementally. So WeakMap
76 // mutations are barriered to keep the weak keys table up to date: entries are
77 // removed if their key is removed from the table, etc.
79 // You can break down various ways that WeakMap values get marked based on the
80 // order that the map and key are marked. All of these assume the map and key
81 // get marked at some point:
83 // key marked, then map marked:
84 // - value was marked with map in `markEntries()`
85 // map marked, key already in map, key marked before weak marking mode:
86 // - key added to gcEphemeronEdges when map marked in `markEntries()`
87 // - value marked during `enterWeakMarkingMode`
88 // map marked, key already in map, key marked after weak marking mode:
89 // - when key is marked, gcEphemeronEdges[key] triggers marking of value in
90 // `markImplicitEdges()`
91 // map marked, key inserted into map, key marked:
92 // - value was live when inserted and must get marked at some point
95 using WeakMapColors
= HashMap
<WeakMapBase
*, js::gc::CellColor
,
96 DefaultHasher
<WeakMapBase
*>, SystemAllocPolicy
>;
98 // Common base class for all WeakMap specializations, used for calling
99 // subclasses' GC-related methods.
100 class WeakMapBase
: public mozilla::LinkedListElement
<WeakMapBase
> {
101 friend class js::GCMarker
;
104 using CellColor
= js::gc::CellColor
;
106 WeakMapBase(JSObject
* memOf
, JS::Zone
* zone
);
107 virtual ~WeakMapBase();
109 JS::Zone
* zone() const { return zone_
; }
111 // Garbage collector entry points.
113 // Unmark all weak maps in a zone.
114 static void unmarkZone(JS::Zone
* zone
);
116 // Check all weak maps in a zone that have been marked as live in this garbage
117 // collection, and mark the values of all entries that have become strong
118 // references to them. Return true if we marked any new values, indicating
119 // that we need to make another pass. In other words, mark my marked maps'
120 // marked members' mid-collection.
121 static bool markZoneIteratively(JS::Zone
* zone
, GCMarker
* marker
);
123 // Add zone edges for weakmaps with key delegates in a different zone.
124 [[nodiscard
]] static bool findSweepGroupEdgesForZone(JS::Zone
* zone
);
126 // Sweep the marked weak maps in a zone, updating moved keys.
127 static void sweepZoneAfterMinorGC(JS::Zone
* zone
);
129 // Trace all weak map bindings. Used by the cycle collector.
130 static void traceAllMappings(WeakMapTracer
* tracer
);
132 // Save information about which weak maps are marked for a zone.
133 static bool saveZoneMarkedWeakMaps(JS::Zone
* zone
,
134 WeakMapColors
& markedWeakMaps
);
136 // Restore information about which weak maps are marked for many zones.
137 static void restoreMarkedWeakMaps(WeakMapColors
& markedWeakMaps
);
139 #if defined(JS_GC_ZEAL) || defined(DEBUG)
140 static bool checkMarkingForZone(JS::Zone
* zone
);
144 // Instance member functions called by the above. Instantiations of WeakMap
145 // override these with definitions appropriate for their Key and Value types.
146 virtual void trace(JSTracer
* tracer
) = 0;
147 virtual bool findSweepGroupEdges() = 0;
148 virtual void traceWeakEdges(JSTracer
* trc
) = 0;
149 virtual void traceMappings(WeakMapTracer
* tracer
) = 0;
150 virtual void clearAndCompact() = 0;
152 // We have a key that, if it or its delegate is marked, may lead to a WeakMap
153 // value getting marked. Insert it or its delegate (if any) into the
154 // appropriate zone's gcEphemeronEdges or gcNurseryEphemeronEdges.
155 [[nodiscard
]] bool addImplicitEdges(gc::MarkColor mapColor
, gc::Cell
* key
,
157 gc::TenuredCell
* value
);
158 [[nodiscard
]] bool addEphemeronTableEntries(gc::MarkColor mapColor
,
159 gc::Cell
* key
, gc::Cell
* value
,
160 gc::Cell
* maybeValue
);
162 virtual bool markEntries(GCMarker
* marker
) = 0;
164 gc::CellColor
mapColor() const { return gc::CellColor(uint32_t(mapColor_
)); }
165 void setMapColor(gc::CellColor newColor
) { mapColor_
= uint32_t(newColor
); }
166 bool markMap(gc::MarkColor markColor
);
169 virtual bool checkMarking() const = 0;
170 virtual bool allowKeysInOtherZones() const { return false; }
171 friend bool gc::CheckWeakMapEntryMarking(const WeakMapBase
*, gc::Cell
*,
175 // Object that this weak map is part of, if any.
176 HeapPtr
<JSObject
*> memberOf
;
178 // Zone containing this weak map.
181 // Whether this object has been marked during garbage collection and which
182 // color it was marked.
183 mozilla::Atomic
<uint32_t, mozilla::Relaxed
> mapColor_
;
185 friend class JS::Zone
;
188 template <class Key
, class Value
>
190 : private HashMap
<Key
, Value
, StableCellHasher
<Key
>, ZoneAllocPolicy
>,
193 using Base
= HashMap
<Key
, Value
, StableCellHasher
<Key
>, ZoneAllocPolicy
>;
195 using Lookup
= typename
Base::Lookup
;
196 using Entry
= typename
Base::Entry
;
197 using Range
= typename
Base::Range
;
198 using Ptr
= typename
Base::Ptr
;
199 using AddPtr
= typename
Base::AddPtr
;
201 struct Enum
: public Base::Enum
{
202 explicit Enum(WeakMap
& map
) : Base::Enum(static_cast<Base
&>(map
)) {}
210 using Base::shallowSizeOfExcludingThis
;
212 // Resolve ambiguity with LinkedListElement<>::remove.
215 using UnbarrieredKey
= typename RemoveBarrier
<Key
>::Type
;
217 explicit WeakMap(JSContext
* cx
, JSObject
* memOf
= nullptr);
218 explicit WeakMap(JS::Zone
* zone
, JSObject
* memOf
= nullptr);
220 // Add a read barrier to prevent an incorrectly gray value from escaping the
221 // weak map. See the UnmarkGrayTracer::onChild comment in gc/Marking.cpp.
222 Ptr
lookup(const Lookup
& l
) const {
223 Ptr p
= Base::lookup(l
);
225 exposeGCThingToActiveJS(p
->value());
230 Ptr
lookupUnbarriered(const Lookup
& l
) const { return Base::lookup(l
); }
232 AddPtr
lookupForAdd(const Lookup
& l
) {
233 AddPtr p
= Base::lookupForAdd(l
);
235 exposeGCThingToActiveJS(p
->value());
240 template <typename KeyInput
, typename ValueInput
>
241 [[nodiscard
]] bool add(AddPtr
& p
, KeyInput
&& k
, ValueInput
&& v
) {
242 MOZ_ASSERT(gc::ToMarkable(k
));
243 return Base::add(p
, std::forward
<KeyInput
>(k
), std::forward
<ValueInput
>(v
));
246 template <typename KeyInput
, typename ValueInput
>
247 [[nodiscard
]] bool relookupOrAdd(AddPtr
& p
, KeyInput
&& k
, ValueInput
&& v
) {
248 MOZ_ASSERT(gc::ToMarkable(k
));
249 return Base::relookupOrAdd(p
, std::forward
<KeyInput
>(k
),
250 std::forward
<ValueInput
>(v
));
253 template <typename KeyInput
, typename ValueInput
>
254 [[nodiscard
]] bool put(KeyInput
&& k
, ValueInput
&& v
) {
255 MOZ_ASSERT(gc::ToMarkable(k
));
256 return Base::put(std::forward
<KeyInput
>(k
), std::forward
<ValueInput
>(v
));
259 template <typename KeyInput
, typename ValueInput
>
260 [[nodiscard
]] bool putNew(KeyInput
&& k
, ValueInput
&& v
) {
261 MOZ_ASSERT(gc::ToMarkable(k
));
262 return Base::putNew(std::forward
<KeyInput
>(k
), std::forward
<ValueInput
>(v
));
265 template <typename KeyInput
, typename ValueInput
>
266 void putNewInfallible(KeyInput
&& k
, ValueInput
&& v
) {
267 MOZ_ASSERT(gc::ToMarkable(k
));
268 Base::putNewInfallible(std::forward(k
), std::forward
<KeyInput
>(k
));
272 template <typename KeyInput
, typename ValueInput
>
273 bool hasEntry(KeyInput
&& key
, ValueInput
&& value
) {
274 Ptr p
= Base::lookup(std::forward
<KeyInput
>(key
));
275 return p
&& p
->value() == value
;
279 bool markEntry(GCMarker
* marker
, gc::CellColor mapColor
, Key
& key
,
280 Value
& value
, bool populateWeakKeysTable
);
282 void trace(JSTracer
* trc
) override
;
284 size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf
);
287 inline void assertMapIsSameZoneWithValue(const Value
& v
);
289 bool markEntries(GCMarker
* marker
) override
;
292 // Find sweep group edges for delegates, if the key type has delegates. (If
293 // not, the optimizer should make this a nop.)
294 bool findSweepGroupEdges() override
;
297 * If a wrapper is used as a key in a weakmap, the garbage collector should
298 * keep that object around longer than it otherwise would. We want to avoid
299 * collecting the wrapper (and removing the weakmap entry) as long as the
300 * wrapped object is alive (because the object can be rewrapped and looked up
301 * again). As long as the wrapper is used as a weakmap key, it will not be
302 * collected (and remain in the weakmap) until the wrapped object is
306 void exposeGCThingToActiveJS(const JS::Value
& v
) const {
307 JS::ExposeValueToActiveJS(v
);
309 void exposeGCThingToActiveJS(JSObject
* obj
) const {
310 JS::ExposeObjectToActiveJS(obj
);
313 void traceWeakEdges(JSTracer
* trc
) override
;
315 void clearAndCompact() override
{
320 // memberOf can be nullptr, which means that the map is not part of a
322 void traceMappings(WeakMapTracer
* tracer
) override
;
326 void assertEntriesNotAboutToBeFinalized();
330 bool checkMarking() const override
;
334 using ObjectValueWeakMap
= WeakMap
<HeapPtr
<JSObject
*>, HeapPtr
<Value
>>;
335 using ValueValueWeakMap
= WeakMap
<HeapPtr
<Value
>, HeapPtr
<Value
>>;
337 // Generic weak map for mapping objects to other objects.
338 class ObjectWeakMap
{
339 ObjectValueWeakMap map
;
342 explicit ObjectWeakMap(JSContext
* cx
);
344 JS::Zone
* zone() const { return map
.zone(); }
346 JSObject
* lookup(const JSObject
* obj
);
347 bool add(JSContext
* cx
, JSObject
* obj
, JSObject
* target
);
348 void remove(JSObject
* key
);
351 void trace(JSTracer
* trc
);
352 size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf
);
353 size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf
) {
354 return mallocSizeOf(this) + sizeOfExcludingThis(mallocSizeOf
);
357 ObjectValueWeakMap
& valueMap() { return map
; }
359 #ifdef JSGC_HASH_TABLE_CHECKS
360 void checkAfterMovingGC();
364 // Get the hash from the Symbol.
365 [[nodiscard
]] HashNumber
GetHash(JS::Symbol
* sym
);
367 // Return true if the hashes of two Symbols match.
368 [[nodiscard
]] bool HashMatch(JS::Symbol
* key
, JS::Symbol
* lookup
);
370 // NB: The specialization works based on pointer equality and not on JS Value
371 // semantics, and it will assert if the Value's isGCThing() is false.
373 // When the JS Value is of type JS::Symbol, we cannot access uniqueIds when it
374 // runs on the worker thread, so we get the hashes from the Symbols directly
377 struct StableCellHasher
<HeapPtr
<Value
>> {
378 using Key
= HeapPtr
<Value
>;
379 using Lookup
= Value
;
381 static bool maybeGetHash(const Lookup
& l
, HashNumber
* hashOut
) {
383 *hashOut
= GetHash(l
.toSymbol());
386 return StableCellHasher
<gc::Cell
*>::maybeGetHash(l
.toGCThing(), hashOut
);
388 static bool ensureHash(const Lookup
& l
, HashNumber
* hashOut
) {
390 *hashOut
= GetHash(l
.toSymbol());
393 return StableCellHasher
<gc::Cell
*>::ensureHash(l
.toGCThing(), hashOut
);
395 static HashNumber
hash(const Lookup
& l
) {
397 return GetHash(l
.toSymbol());
399 return StableCellHasher
<gc::Cell
*>::hash(l
.toGCThing());
401 static bool match(const Key
& k
, const Lookup
& l
) {
403 return HashMatch(k
.toSymbol(), l
.toSymbol());
405 return StableCellHasher
<gc::Cell
*>::match(k
.toGCThing(), l
.toGCThing());
411 #endif /* gc_WeakMap_h */