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 HeapPtrObject 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 marked = JS::IsIncrementalGCInProgress(zone->runtimeFromMainThread());
140 return true;
141 }
142
143 // Overwritten to add a read barrier to prevent an incorrectly gray value
144 // from escaping the weak map. See the UnmarkGrayTracer::onChild comment in
145 // gc/Marking.cpp.
lookup(const Lookup & l)146 Ptr lookup(const Lookup& l) const {
147 Ptr p = Base::lookup(l);
148 if (p)
149 exposeGCThingToActiveJS(p->value());
150 return p;
151 }
152
lookupForAdd(const Lookup & l)153 AddPtr lookupForAdd(const Lookup& l) const {
154 AddPtr p = Base::lookupForAdd(l);
155 if (p)
156 exposeGCThingToActiveJS(p->value());
157 return p;
158 }
159
lookupWithDefault(const Key & k,const Value & defaultValue)160 Ptr lookupWithDefault(const Key& k, const Value& defaultValue) {
161 Ptr p = Base::lookupWithDefault(k, defaultValue);
162 if (p)
163 exposeGCThingToActiveJS(p->value());
164 return p;
165 }
166
167 // Resolve ambiguity with LinkedListElement<>::remove.
168 using Base::remove;
169
170 // Trace a WeakMap entry based on 'markedCell' getting marked, where
171 // 'origKey' is the key in the weakmap. These will probably be the same,
172 // but can be different eg when markedCell is a delegate for origKey.
173 //
174 // This implementation does not use 'markedCell'; it looks up origKey and
175 // checks the mark bits on everything it cares about, one of which will be
176 // markedCell. But a subclass might use it to optimize the liveness check.
traceEntry(JSTracer * trc,gc::Cell * markedCell,JS::GCCellPtr origKey)177 void traceEntry(JSTracer* trc, gc::Cell* markedCell, JS::GCCellPtr origKey) override
178 {
179 MOZ_ASSERT(marked);
180
181 gc::Cell* l = origKey.asCell();
182 Ptr p = Base::lookup(reinterpret_cast<Lookup&>(l));
183 MOZ_ASSERT(p.found());
184
185 Key key(p->key());
186 MOZ_ASSERT((markedCell == extractUnbarriered(key)) || (markedCell == getDelegate(key)));
187 if (gc::IsMarked(trc->runtime(), &key)) {
188 TraceEdge(trc, &p->value(), "ephemeron value");
189 } else if (keyNeedsMark(key)) {
190 TraceEdge(trc, &p->value(), "WeakMap ephemeron value");
191 TraceEdge(trc, &key, "proxy-preserved WeakMap ephemeron key");
192 MOZ_ASSERT(key == p->key()); // No moving
193 }
194 key.unsafeSet(nullptr); // Prevent destructor from running barriers.
195 }
196
trace(JSTracer * trc)197 void trace(JSTracer* trc) override {
198 MOZ_ASSERT(isInList());
199
200 if (trc->isMarkingTracer())
201 marked = true;
202
203 if (trc->weakMapAction() == DoNotTraceWeakMaps)
204 return;
205
206 if (!trc->isMarkingTracer()) {
207 // Trace keys only if weakMapAction() says to.
208 if (trc->weakMapAction() == TraceWeakMapKeysValues) {
209 for (Enum e(*this); !e.empty(); e.popFront())
210 TraceEdge(trc, &e.front().mutableKey(), "WeakMap entry key");
211 }
212
213 // Always trace all values (unless weakMapAction() is
214 // DoNotTraceWeakMaps).
215 for (Range r = Base::all(); !r.empty(); r.popFront())
216 TraceEdge(trc, &r.front().value(), "WeakMap entry value");
217
218 return;
219 }
220
221 // Marking tracer
222 MOZ_ASSERT(trc->weakMapAction() == ExpandWeakMaps);
223 (void) traceEntries(trc);
224 }
225
226 protected:
addWeakEntry(JSTracer * trc,JS::GCCellPtr key,gc::WeakMarkable markable)227 static void addWeakEntry(JSTracer* trc, JS::GCCellPtr key, gc::WeakMarkable markable)
228 {
229 GCMarker& marker = *static_cast<GCMarker*>(trc);
230 Zone* zone = key.asCell()->asTenured().zone();
231
232 auto p = zone->gcWeakKeys.get(key);
233 if (p) {
234 gc::WeakEntryVector& weakEntries = p->value;
235 if (!weakEntries.append(Move(markable)))
236 marker.abortLinearWeakMarking();
237 } else {
238 gc::WeakEntryVector weakEntries;
239 MOZ_ALWAYS_TRUE(weakEntries.append(Move(markable)));
240 if (!zone->gcWeakKeys.put(JS::GCCellPtr(key), Move(weakEntries)))
241 marker.abortLinearWeakMarking();
242 }
243 }
244
traceEntries(JSTracer * trc)245 bool traceEntries(JSTracer* trc) override {
246 MOZ_ASSERT(marked);
247
248 bool markedAny = false;
249
250 for (Enum e(*this); !e.empty(); e.popFront()) {
251 // If the entry is live, ensure its key and value are marked.
252 bool keyIsMarked = gc::IsMarked(trc->runtime(), &e.front().mutableKey());
253 if (!keyIsMarked && keyNeedsMark(e.front().key())) {
254 TraceEdge(trc, &e.front().mutableKey(), "proxy-preserved WeakMap entry key");
255 keyIsMarked = true;
256 markedAny = true;
257 }
258
259 if (keyIsMarked) {
260 if (!gc::IsMarked(trc->runtime(), &e.front().value())) {
261 TraceEdge(trc, &e.front().value(), "WeakMap entry value");
262 markedAny = true;
263 }
264 } else if (trc->isWeakMarkingTracer()) {
265 // Entry is not yet known to be live. Record this weakmap and
266 // the lookup key in the list of weak keys. Also record the
267 // delegate, if any, because marking the delegate also marks
268 // the entry.
269 JS::GCCellPtr weakKey(extractUnbarriered(e.front().key()));
270 gc::WeakMarkable markable(this, weakKey);
271 addWeakEntry(trc, weakKey, markable);
272 if (JSObject* delegate = getDelegate(e.front().key()))
273 addWeakEntry(trc, JS::GCCellPtr(delegate), markable);
274 }
275 }
276
277 return markedAny;
278 }
279
280 private:
exposeGCThingToActiveJS(const JS::Value & v)281 void exposeGCThingToActiveJS(const JS::Value& v) const { JS::ExposeValueToActiveJS(v); }
exposeGCThingToActiveJS(JSObject * obj)282 void exposeGCThingToActiveJS(JSObject* obj) const { JS::ExposeObjectToActiveJS(obj); }
283
getDelegate(JSObject * key)284 JSObject* getDelegate(JSObject* key) const {
285 JSWeakmapKeyDelegateOp op = key->getClass()->ext.weakmapKeyDelegateOp;
286 if (!op)
287 return nullptr;
288
289 JSObject* obj = op(key);
290 if (!obj)
291 return nullptr;
292
293 MOZ_ASSERT(obj->runtimeFromMainThread() == zone->runtimeFromMainThread());
294 return obj;
295 }
296
getDelegate(gc::Cell * cell)297 JSObject* getDelegate(gc::Cell* cell) const {
298 return nullptr;
299 }
300
keyNeedsMark(JSObject * key)301 bool keyNeedsMark(JSObject* key) const {
302 JSObject* delegate = getDelegate(key);
303 /*
304 * Check if the delegate is marked with any color to properly handle
305 * gray marking when the key's delegate is black and the map is gray.
306 */
307 return delegate && gc::IsMarkedUnbarriered(zone->runtimeFromMainThread(), &delegate);
308 }
309
keyNeedsMark(gc::Cell * cell)310 bool keyNeedsMark(gc::Cell* cell) const {
311 return false;
312 }
313
findZoneEdges()314 bool findZoneEdges() override {
315 // This is overridden by ObjectValueMap.
316 return true;
317 }
318
sweep()319 void sweep() override {
320 /* Remove all entries whose keys remain unmarked. */
321 for (Enum e(*this); !e.empty(); e.popFront()) {
322 if (gc::IsAboutToBeFinalized(&e.front().mutableKey()))
323 e.removeFront();
324 }
325 /*
326 * Once we've swept, all remaining edges should stay within the
327 * known-live part of the graph.
328 */
329 assertEntriesNotAboutToBeFinalized();
330 }
331
finish()332 void finish() override {
333 Base::finish();
334 }
335
336 /* memberOf can be nullptr, which means that the map is not part of a JSObject. */
traceMappings(WeakMapTracer * tracer)337 void traceMappings(WeakMapTracer* tracer) override {
338 for (Range r = Base::all(); !r.empty(); r.popFront()) {
339 gc::Cell* key = gc::ToMarkable(r.front().key());
340 gc::Cell* value = gc::ToMarkable(r.front().value());
341 if (key && value) {
342 tracer->trace(memberOf,
343 JS::GCCellPtr(r.front().key().get()),
344 JS::GCCellPtr(r.front().value().get()));
345 }
346 }
347 }
348
349 protected:
assertEntriesNotAboutToBeFinalized()350 void assertEntriesNotAboutToBeFinalized() {
351 #if DEBUG
352 for (Range r = Base::all(); !r.empty(); r.popFront()) {
353 Key k(r.front().key());
354 MOZ_ASSERT(!gc::IsAboutToBeFinalized(&k));
355 MOZ_ASSERT(!gc::IsAboutToBeFinalized(&r.front().value()));
356 MOZ_ASSERT(k == r.front().key());
357 }
358 #endif
359 }
360 };
361
362 /* WeakMap methods exposed so they can be installed in the self-hosting global. */
363
364 extern JSObject*
365 InitBareWeakMapCtor(JSContext* cx, js::HandleObject obj);
366
367 extern bool
368 WeakMap_has(JSContext* cx, unsigned argc, Value* vp);
369
370 extern bool
371 WeakMap_get(JSContext* cx, unsigned argc, Value* vp);
372
373 extern bool
374 WeakMap_set(JSContext* cx, unsigned argc, Value* vp);
375
376 extern bool
377 WeakMap_delete(JSContext* cx, unsigned argc, Value* vp);
378
379 extern bool
380 WeakMap_clear(JSContext* cx, unsigned argc, Value* vp);
381
382 extern JSObject*
383 InitWeakMapClass(JSContext* cx, HandleObject obj);
384
385
386 class ObjectValueMap : public WeakMap<RelocatablePtrObject, RelocatableValue,
387 MovableCellHasher<RelocatablePtrObject>>
388 {
389 public:
ObjectValueMap(JSContext * cx,JSObject * obj)390 ObjectValueMap(JSContext* cx, JSObject* obj)
391 : WeakMap<RelocatablePtrObject, RelocatableValue,
392 MovableCellHasher<RelocatablePtrObject>>(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