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