Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 : * vim: set ts=8 sts=4 et sw=4 tw=99:
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 jsweakmap_h
8 : #define jsweakmap_h
9 :
10 : #include "mozilla/LinkedList.h"
11 : #include "mozilla/Move.h"
12 :
13 : #include "jscompartment.h"
14 : #include "jsfriendapi.h"
15 : #include "jsobj.h"
16 :
17 : #include "gc/Marking.h"
18 : #include "gc/StoreBuffer.h"
19 : #include "js/HashTable.h"
20 :
21 : namespace js {
22 :
23 : class GCMarker;
24 : class WeakMapBase;
25 :
26 : // A subclass template of js::HashMap whose keys and values may be garbage-collected. When
27 : // a key is collected, the table entry disappears, dropping its reference to the value.
28 : //
29 : // More precisely:
30 : //
31 : // A WeakMap entry is live if and only if both the WeakMap and the entry's key
32 : // are live. An entry holds a strong reference to its value.
33 : //
34 : // You must call this table's 'trace' method when its owning object is reached
35 : // by the garbage collection tracer. Once a table is known to be live, the
36 : // implementation takes care of the special weak marking (ie, marking through
37 : // the implicit edges stored in the map) and of removing (sweeping) table
38 : // entries when collection is complete.
39 :
40 : typedef HashSet<WeakMapBase*, DefaultHasher<WeakMapBase*>, SystemAllocPolicy> WeakMapSet;
41 :
42 : // Common base class for all WeakMap specializations, used for calling
43 : // subclasses' GC-related methods.
44 : class WeakMapBase : public mozilla::LinkedListElement<WeakMapBase>
45 : {
46 : friend class js::GCMarker;
47 :
48 : public:
49 : WeakMapBase(JSObject* memOf, JS::Zone* zone);
50 : virtual ~WeakMapBase();
51 :
52 20 : Zone* zone() const { return zone_; }
53 :
54 : // Garbage collector entry points.
55 :
56 : // Unmark all weak maps in a zone.
57 : static void unmarkZone(JS::Zone* zone);
58 :
59 : // Mark all the weakmaps in a zone.
60 : static void traceZone(JS::Zone* zone, JSTracer* tracer);
61 :
62 : // Check all weak maps in a zone that have been marked as live in this garbage
63 : // collection, and mark the values of all entries that have become strong references
64 : // to them. Return true if we marked any new values, indicating that we need to make
65 : // another pass. In other words, mark my marked maps' marked members' mid-collection.
66 : static bool markZoneIteratively(JS::Zone* zone, GCMarker* marker);
67 :
68 : // Add zone edges for weakmaps with key delegates in a different zone.
69 : static bool findInterZoneEdges(JS::Zone* zone);
70 :
71 : // Sweep the weak maps in a zone, removing dead weak maps and removing
72 : // entries of live weak maps whose keys are dead.
73 : static void sweepZone(JS::Zone* zone);
74 :
75 : // Trace all delayed weak map bindings. Used by the cycle collector.
76 : static void traceAllMappings(WeakMapTracer* tracer);
77 :
78 : // Save information about which weak maps are marked for a zone.
79 : static bool saveZoneMarkedWeakMaps(JS::Zone* zone, WeakMapSet& markedWeakMaps);
80 :
81 : // Restore information about which weak maps are marked for many zones.
82 : static void restoreMarkedWeakMaps(WeakMapSet& markedWeakMaps);
83 :
84 : protected:
85 : // Instance member functions called by the above. Instantiations of WeakMap override
86 : // these with definitions appropriate for their Key and Value types.
87 : virtual void trace(JSTracer* tracer) = 0;
88 : virtual bool findZoneEdges() = 0;
89 : virtual void sweep() = 0;
90 : virtual void traceMappings(WeakMapTracer* tracer) = 0;
91 : virtual void finish() = 0;
92 :
93 : // Any weakmap key types that want to participate in the non-iterative
94 : // ephemeron marking must override this method.
95 : virtual void markEntry(GCMarker* marker, gc::Cell* markedCell, JS::GCCellPtr l) = 0;
96 :
97 : virtual bool markIteratively(GCMarker* marker) = 0;
98 :
99 : protected:
100 : // Object that this weak map is part of, if any.
101 : GCPtrObject memberOf;
102 :
103 : // Zone containing this weak map.
104 : JS::Zone* zone_;
105 :
106 : // Whether this object has been traced during garbage collection.
107 : bool marked;
108 : };
109 :
110 : template <typename T>
111 0 : static T extractUnbarriered(const WriteBarrieredBase<T>& v)
112 : {
113 0 : return v.get();
114 : }
115 : template <typename T>
116 : static T* extractUnbarriered(T* v)
117 : {
118 : return v;
119 : }
120 :
121 : template <class Key, class Value,
122 : class HashPolicy = DefaultHasher<Key> >
123 0 : class WeakMap : public HashMap<Key, Value, HashPolicy, RuntimeAllocPolicy>,
124 : public WeakMapBase
125 : {
126 : public:
127 : typedef HashMap<Key, Value, HashPolicy, RuntimeAllocPolicy> Base;
128 : typedef typename Base::Enum Enum;
129 : typedef typename Base::Lookup Lookup;
130 : typedef typename Base::Entry Entry;
131 : typedef typename Base::Range Range;
132 : typedef typename Base::Ptr Ptr;
133 : typedef typename Base::AddPtr AddPtr;
134 :
135 20 : explicit WeakMap(JSContext* cx, JSObject* memOf = nullptr)
136 20 : : Base(cx->runtime()), WeakMapBase(memOf, cx->compartment()->zone()) { }
137 :
138 20 : bool init(uint32_t len = 16) {
139 20 : if (!Base::init(len))
140 0 : return false;
141 20 : zone()->gcWeakMapList().insertFront(this);
142 20 : marked = JS::IsIncrementalGCInProgress(TlsContext.get());
143 20 : return true;
144 : }
145 :
146 : // Overwritten to add a read barrier to prevent an incorrectly gray value
147 : // from escaping the weak map. See the UnmarkGrayTracer::onChild comment in
148 : // gc/Marking.cpp.
149 827 : Ptr lookup(const Lookup& l) const {
150 827 : Ptr p = Base::lookup(l);
151 827 : if (p)
152 732 : exposeGCThingToActiveJS(p->value());
153 827 : return p;
154 : }
155 :
156 0 : AddPtr lookupForAdd(const Lookup& l) const {
157 0 : AddPtr p = Base::lookupForAdd(l);
158 0 : if (p)
159 0 : exposeGCThingToActiveJS(p->value());
160 0 : return p;
161 : }
162 :
163 : Ptr lookupWithDefault(const Key& k, const Value& defaultValue) {
164 : Ptr p = Base::lookupWithDefault(k, defaultValue);
165 : if (p)
166 : exposeGCThingToActiveJS(p->value());
167 : return p;
168 : }
169 :
170 : // Resolve ambiguity with LinkedListElement<>::remove.
171 : using Base::remove;
172 :
173 : // Trace a WeakMap entry based on 'markedCell' getting marked, where
174 : // 'origKey' is the key in the weakmap. These will probably be the same,
175 : // but can be different eg when markedCell is a delegate for origKey.
176 : //
177 : // This implementation does not use 'markedCell'; it looks up origKey and
178 : // checks the mark bits on everything it cares about, one of which will be
179 : // markedCell. But a subclass might use it to optimize the liveness check.
180 0 : void markEntry(GCMarker* marker, gc::Cell* markedCell, JS::GCCellPtr origKey) override
181 : {
182 0 : MOZ_ASSERT(marked);
183 :
184 : // If this cast fails, then you're instantiating the WeakMap with a
185 : // Lookup that can't be constructed from a Cell*. The WeakKeyTable
186 : // mechanism is indexed with a GCCellPtr, so that won't work.
187 0 : Ptr p = Base::lookup(static_cast<Lookup>(origKey.asCell()));
188 0 : MOZ_ASSERT(p.found());
189 :
190 0 : Key key(p->key());
191 0 : MOZ_ASSERT((markedCell == extractUnbarriered(key)) || (markedCell == getDelegate(key)));
192 0 : if (gc::IsMarked(marker->runtime(), &key)) {
193 0 : TraceEdge(marker, &p->value(), "ephemeron value");
194 0 : } else if (keyNeedsMark(key)) {
195 0 : TraceEdge(marker, &p->value(), "WeakMap ephemeron value");
196 0 : TraceEdge(marker, &key, "proxy-preserved WeakMap ephemeron key");
197 0 : MOZ_ASSERT(key == p->key()); // No moving
198 : }
199 0 : key.unsafeSet(nullptr); // Prevent destructor from running barriers.
200 0 : }
201 :
202 15 : void trace(JSTracer* trc) override {
203 15 : MOZ_ASSERT_IF(JS::CurrentThreadIsHeapBusy(), isInList());
204 :
205 15 : TraceNullableEdge(trc, &memberOf, "WeakMap owner");
206 :
207 15 : if (!Base::initialized())
208 0 : return;
209 :
210 15 : if (trc->isMarkingTracer()) {
211 2 : MOZ_ASSERT(trc->weakMapAction() == ExpandWeakMaps);
212 2 : marked = true;
213 2 : (void) markIteratively(GCMarker::fromTracer(trc));
214 2 : return;
215 : }
216 :
217 13 : if (trc->weakMapAction() == DoNotTraceWeakMaps)
218 0 : return;
219 :
220 : // Trace keys only if weakMapAction() says to.
221 13 : if (trc->weakMapAction() == TraceWeakMapKeysValues) {
222 417 : for (Enum e(*this); !e.empty(); e.popFront())
223 404 : TraceEdge(trc, &e.front().mutableKey(), "WeakMap entry key");
224 : }
225 :
226 : // Always trace all values (unless weakMapAction() is
227 : // DoNotTraceWeakMaps).
228 417 : for (Range r = Base::all(); !r.empty(); r.popFront())
229 404 : TraceEdge(trc, &r.front().value(), "WeakMap entry value");
230 : }
231 :
232 : protected:
233 0 : static void addWeakEntry(GCMarker* marker, JS::GCCellPtr key, gc::WeakMarkable markable)
234 : {
235 0 : Zone* zone = key.asCell()->asTenured().zone();
236 :
237 0 : auto p = zone->gcWeakKeys().get(key);
238 0 : if (p) {
239 0 : gc::WeakEntryVector& weakEntries = p->value;
240 0 : if (!weakEntries.append(Move(markable)))
241 0 : marker->abortLinearWeakMarking();
242 : } else {
243 0 : gc::WeakEntryVector weakEntries;
244 0 : MOZ_ALWAYS_TRUE(weakEntries.append(Move(markable)));
245 0 : if (!zone->gcWeakKeys().put(JS::GCCellPtr(key), Move(weakEntries)))
246 0 : marker->abortLinearWeakMarking();
247 : }
248 0 : }
249 :
250 2 : bool markIteratively(GCMarker* marker) override {
251 2 : MOZ_ASSERT(marked);
252 :
253 2 : bool markedAny = false;
254 :
255 65 : for (Enum e(*this); !e.empty(); e.popFront()) {
256 : // If the entry is live, ensure its key and value are marked.
257 63 : bool keyIsMarked = gc::IsMarked(marker->runtime(), &e.front().mutableKey());
258 63 : if (!keyIsMarked && keyNeedsMark(e.front().key())) {
259 0 : TraceEdge(marker, &e.front().mutableKey(), "proxy-preserved WeakMap entry key");
260 0 : keyIsMarked = true;
261 0 : markedAny = true;
262 : }
263 :
264 63 : if (keyIsMarked) {
265 0 : if (!gc::IsMarked(marker->runtime(), &e.front().value())) {
266 0 : TraceEdge(marker, &e.front().value(), "WeakMap entry value");
267 0 : markedAny = true;
268 : }
269 63 : } else if (marker->isWeakMarkingTracer()) {
270 : // Entry is not yet known to be live. Record this weakmap and
271 : // the lookup key in the list of weak keys. Also record the
272 : // delegate, if any, because marking the delegate also marks
273 : // the entry.
274 0 : JS::GCCellPtr weakKey(extractUnbarriered(e.front().key()));
275 0 : gc::WeakMarkable markable(this, weakKey);
276 0 : addWeakEntry(marker, weakKey, markable);
277 0 : if (JSObject* delegate = getDelegate(e.front().key()))
278 0 : addWeakEntry(marker, JS::GCCellPtr(delegate), markable);
279 : }
280 : }
281 :
282 2 : return markedAny;
283 : }
284 :
285 63 : JSObject* getDelegate(JSObject* key) const {
286 63 : JSWeakmapKeyDelegateOp op = key->getClass()->extWeakmapKeyDelegateOp();
287 63 : if (!op)
288 63 : return nullptr;
289 :
290 0 : JSObject* obj = op(key);
291 0 : if (!obj)
292 0 : return nullptr;
293 :
294 0 : MOZ_ASSERT(obj->runtimeFromActiveCooperatingThread() == zone()->runtimeFromActiveCooperatingThread());
295 0 : return obj;
296 : }
297 :
298 0 : JSObject* getDelegate(JSScript* script) const {
299 0 : return nullptr;
300 : }
301 :
302 : private:
303 732 : void exposeGCThingToActiveJS(const JS::Value& v) const { JS::ExposeValueToActiveJS(v); }
304 0 : void exposeGCThingToActiveJS(JSObject* obj) const { JS::ExposeObjectToActiveJS(obj); }
305 :
306 63 : bool keyNeedsMark(JSObject* key) const {
307 63 : JSObject* delegate = getDelegate(key);
308 : /*
309 : * Check if the delegate is marked with any color to properly handle
310 : * gray marking when the key's delegate is black and the map is gray.
311 : */
312 63 : return delegate && gc::IsMarkedUnbarriered(zone()->runtimeFromActiveCooperatingThread(), &delegate);
313 : }
314 :
315 0 : bool keyNeedsMark(JSScript* script) const {
316 0 : return false;
317 : }
318 :
319 0 : bool findZoneEdges() override {
320 : // This is overridden by ObjectValueMap.
321 0 : return true;
322 : }
323 :
324 0 : void sweep() override {
325 : /* Remove all entries whose keys remain unmarked. */
326 0 : for (Enum e(*this); !e.empty(); e.popFront()) {
327 0 : if (gc::IsAboutToBeFinalized(&e.front().mutableKey()))
328 0 : e.removeFront();
329 : }
330 : /*
331 : * Once we've swept, all remaining edges should stay within the
332 : * known-live part of the graph.
333 : */
334 0 : assertEntriesNotAboutToBeFinalized();
335 0 : }
336 :
337 0 : void finish() override {
338 0 : Base::finish();
339 0 : }
340 :
341 : /* memberOf can be nullptr, which means that the map is not part of a JSObject. */
342 0 : void traceMappings(WeakMapTracer* tracer) override {
343 0 : for (Range r = Base::all(); !r.empty(); r.popFront()) {
344 0 : gc::Cell* key = gc::ToMarkable(r.front().key());
345 0 : gc::Cell* value = gc::ToMarkable(r.front().value());
346 0 : if (key && value) {
347 0 : tracer->trace(memberOf,
348 0 : JS::GCCellPtr(r.front().key().get()),
349 0 : JS::GCCellPtr(r.front().value().get()));
350 : }
351 : }
352 0 : }
353 :
354 : protected:
355 0 : void assertEntriesNotAboutToBeFinalized() {
356 : #if DEBUG
357 0 : for (Range r = Base::all(); !r.empty(); r.popFront()) {
358 0 : Key k(r.front().key());
359 0 : MOZ_ASSERT(!gc::IsAboutToBeFinalized(&k));
360 0 : MOZ_ASSERT(!gc::IsAboutToBeFinalized(&r.front().value()));
361 0 : MOZ_ASSERT(k == r.front().key());
362 : }
363 : #endif
364 0 : }
365 : };
366 :
367 : /* WeakMap methods exposed so they can be installed in the self-hosting global. */
368 :
369 : extern JSObject*
370 : InitBareWeakMapCtor(JSContext* cx, js::HandleObject obj);
371 :
372 : extern bool
373 : WeakMap_has(JSContext* cx, unsigned argc, Value* vp);
374 :
375 : extern bool
376 : WeakMap_get(JSContext* cx, unsigned argc, Value* vp);
377 :
378 : extern bool
379 : WeakMap_set(JSContext* cx, unsigned argc, Value* vp);
380 :
381 : extern bool
382 : WeakMap_delete(JSContext* cx, unsigned argc, Value* vp);
383 :
384 : extern JSObject*
385 : InitWeakMapClass(JSContext* cx, HandleObject obj);
386 :
387 :
388 0 : class ObjectValueMap : public WeakMap<HeapPtr<JSObject*>, HeapPtr<Value>,
389 : MovableCellHasher<HeapPtr<JSObject*>>>
390 : {
391 : public:
392 20 : ObjectValueMap(JSContext* cx, JSObject* obj)
393 20 : : WeakMap<HeapPtr<JSObject*>, HeapPtr<Value>,
394 20 : MovableCellHasher<HeapPtr<JSObject*>>>(cx, obj)
395 20 : {}
396 :
397 : virtual bool findZoneEdges();
398 : };
399 :
400 :
401 : // Generic weak map for mapping objects to other objects.
402 0 : class ObjectWeakMap
403 : {
404 : ObjectValueMap map;
405 :
406 : public:
407 : explicit ObjectWeakMap(JSContext* cx);
408 : bool init();
409 :
410 : JS::Zone* zone() const { return map.zone(); }
411 :
412 : JSObject* lookup(const JSObject* obj);
413 : bool add(JSContext* cx, JSObject* obj, JSObject* target);
414 : void clear();
415 :
416 : void trace(JSTracer* trc);
417 : size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf);
418 0 : size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) {
419 0 : return mallocSizeOf(this) + sizeOfExcludingThis(mallocSizeOf);
420 : }
421 :
422 : #ifdef JSGC_HASH_TABLE_CHECKS
423 : void checkAfterMovingGC();
424 : #endif
425 : };
426 :
427 : } /* namespace js */
428 :
429 : namespace JS {
430 :
431 : template <>
432 : struct DeletePolicy<js::ObjectValueMap> : public js::GCManagedDeletePolicy<js::ObjectValueMap>
433 : {};
434 :
435 : } /* namespace JS */
436 :
437 : #endif /* jsweakmap_h */
|
