summaryrefslogtreecommitdiffstats
path: root/js/src/jsweakmap.h
blob: c13baa782569c9bbd8e139377e30fc30cc03a251 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#ifndef jsweakmap_h
#define jsweakmap_h

#include "mozilla/LinkedList.h"
#include "mozilla/Move.h"

#include "jscompartment.h"
#include "jsfriendapi.h"
#include "jsobj.h"

#include "gc/Marking.h"
#include "gc/StoreBuffer.h"
#include "js/HashTable.h"

namespace js {

class WeakMapBase;

// A subclass template of js::HashMap whose keys and values may be garbage-collected. When
// a key is collected, the table entry disappears, dropping its reference to the value.
//
// More precisely:
//
//     A WeakMap entry is live if and only if both the WeakMap and the entry's key
//     are live. An entry holds a strong reference to its value.
//
// You must call this table's 'trace' method when its owning object is reached
// by the garbage collection tracer. Once a table is known to be live, the
// implementation takes care of the special weak marking (ie, marking through
// the implicit edges stored in the map) and of removing (sweeping) table
// entries when collection is complete.

typedef HashSet<WeakMapBase*, DefaultHasher<WeakMapBase*>, SystemAllocPolicy> WeakMapSet;

// Common base class for all WeakMap specializations, used for calling
// subclasses' GC-related methods.
class WeakMapBase : public mozilla::LinkedListElement<WeakMapBase>
{
    friend class js::GCMarker;

  public:
    WeakMapBase(JSObject* memOf, JS::Zone* zone);
    virtual ~WeakMapBase();

    // Garbage collector entry points.

    // Unmark all weak maps in a zone.
    static void unmarkZone(JS::Zone* zone);

    // Mark all the weakmaps in a zone.
    static void markAll(JS::Zone* zone, JSTracer* tracer);

    // Check all weak maps in a zone that have been marked as live in this garbage
    // collection, and mark the values of all entries that have become strong references
    // to them. Return true if we marked any new values, indicating that we need to make
    // another pass. In other words, mark my marked maps' marked members' mid-collection.
    static bool markZoneIteratively(JS::Zone* zone, JSTracer* tracer);

    // Add zone edges for weakmaps with key delegates in a different zone.
    static bool findInterZoneEdges(JS::Zone* zone);

    // Sweep the weak maps in a zone, removing dead weak maps and removing
    // entries of live weak maps whose keys are dead.
    static void sweepZone(JS::Zone* zone);

    // Trace all delayed weak map bindings. Used by the cycle collector.
    static void traceAllMappings(WeakMapTracer* tracer);

    // Save information about which weak maps are marked for a zone.
    static bool saveZoneMarkedWeakMaps(JS::Zone* zone, WeakMapSet& markedWeakMaps);

    // Restore information about which weak maps are marked for many zones.
    static void restoreMarkedWeakMaps(WeakMapSet& markedWeakMaps);

  protected:
    // Instance member functions called by the above. Instantiations of WeakMap override
    // these with definitions appropriate for their Key and Value types.
    virtual void trace(JSTracer* tracer) = 0;
    virtual bool findZoneEdges() = 0;
    virtual void sweep() = 0;
    virtual void traceMappings(WeakMapTracer* tracer) = 0;
    virtual void finish() = 0;

    // Any weakmap key types that want to participate in the non-iterative
    // ephemeron marking must override this method.
    virtual void traceEntry(JSTracer* trc, gc::Cell* markedCell, JS::GCCellPtr l) = 0;

    virtual bool traceEntries(JSTracer* trc) = 0;

  protected:
    // Object that this weak map is part of, if any.
    GCPtrObject memberOf;

    // Zone containing this weak map.
    JS::Zone* zone;

    // Whether this object has been traced during garbage collection.
    bool marked;
};

template <typename T>
static T extractUnbarriered(WriteBarrieredBase<T> v)
{
    return v.get();
}
template <typename T>
static T* extractUnbarriered(T* v)
{
    return v;
}

template <class Key, class Value,
          class HashPolicy = DefaultHasher<Key> >
class WeakMap : public HashMap<Key, Value, HashPolicy, RuntimeAllocPolicy>,
                public WeakMapBase
{
  public:
    typedef HashMap<Key, Value, HashPolicy, RuntimeAllocPolicy> Base;
    typedef typename Base::Enum Enum;
    typedef typename Base::Lookup Lookup;
    typedef typename Base::Entry Entry;
    typedef typename Base::Range Range;
    typedef typename Base::Ptr Ptr;
    typedef typename Base::AddPtr AddPtr;

    explicit WeakMap(JSContext* cx, JSObject* memOf = nullptr)
        : Base(cx->runtime()), WeakMapBase(memOf, cx->compartment()->zone()) { }

    bool init(uint32_t len = 16) {
        if (!Base::init(len))
            return false;
        zone->gcWeakMapList.insertFront(this);
        JSRuntime* rt = zone->runtimeFromMainThread();
        marked = JS::IsIncrementalGCInProgress(rt->contextFromMainThread());
        return true;
    }

    // Overwritten to add a read barrier to prevent an incorrectly gray value
    // from escaping the weak map. See the UnmarkGrayTracer::onChild comment in
    // gc/Marking.cpp.
    Ptr lookup(const Lookup& l) const {
        Ptr p = Base::lookup(l);
        if (p)
            exposeGCThingToActiveJS(p->value());
        return p;
    }

    AddPtr lookupForAdd(const Lookup& l) const {
        AddPtr p = Base::lookupForAdd(l);
        if (p)
            exposeGCThingToActiveJS(p->value());
        return p;
    }

    Ptr lookupWithDefault(const Key& k, const Value& defaultValue) {
        Ptr p = Base::lookupWithDefault(k, defaultValue);
        if (p)
            exposeGCThingToActiveJS(p->value());
        return p;
    }

    // Resolve ambiguity with LinkedListElement<>::remove.
    using Base::remove;

    // Trace a WeakMap entry based on 'markedCell' getting marked, where
    // 'origKey' is the key in the weakmap. These will probably be the same,
    // but can be different eg when markedCell is a delegate for origKey.
    //
    // This implementation does not use 'markedCell'; it looks up origKey and
    // checks the mark bits on everything it cares about, one of which will be
    // markedCell. But a subclass might use it to optimize the liveness check.
    void traceEntry(JSTracer* trc, gc::Cell* markedCell, JS::GCCellPtr origKey) override
    {
        MOZ_ASSERT(marked);

        // If this cast fails, then you're instantiating the WeakMap with a
        // Lookup that can't be constructed from a Cell*. The WeakKeyTable
        // mechanism is indexed with a GCCellPtr, so that won't work.
        Ptr p = Base::lookup(static_cast<Lookup>(origKey.asCell()));
        MOZ_ASSERT(p.found());

        Key key(p->key());
        MOZ_ASSERT((markedCell == extractUnbarriered(key)) || (markedCell == getDelegate(key)));
        if (gc::IsMarked(trc->runtime(), &key)) {
            TraceEdge(trc, &p->value(), "ephemeron value");
        } else if (keyNeedsMark(key)) {
            TraceEdge(trc, &p->value(), "WeakMap ephemeron value");
            TraceEdge(trc, &key, "proxy-preserved WeakMap ephemeron key");
            MOZ_ASSERT(key == p->key()); // No moving
        }
        key.unsafeSet(nullptr); // Prevent destructor from running barriers.
    }

    void trace(JSTracer* trc) override {
        MOZ_ASSERT(isInList());

        if (trc->isMarkingTracer())
            marked = true;

        if (trc->weakMapAction() == DoNotTraceWeakMaps)
            return;

        if (!trc->isMarkingTracer()) {
            // Trace keys only if weakMapAction() says to.
            if (trc->weakMapAction() == TraceWeakMapKeysValues) {
                for (Enum e(*this); !e.empty(); e.popFront())
                    TraceEdge(trc, &e.front().mutableKey(), "WeakMap entry key");
            }

            // Always trace all values (unless weakMapAction() is
            // DoNotTraceWeakMaps).
            for (Range r = Base::all(); !r.empty(); r.popFront())
                TraceEdge(trc, &r.front().value(), "WeakMap entry value");

            return;
        }

        // Marking tracer
        MOZ_ASSERT(trc->weakMapAction() == ExpandWeakMaps);
        (void) traceEntries(trc);
    }

  protected:
    static void addWeakEntry(JSTracer* trc, JS::GCCellPtr key, gc::WeakMarkable markable)
    {
        GCMarker& marker = *static_cast<GCMarker*>(trc);
        Zone* zone = key.asCell()->asTenured().zone();

        auto p = zone->gcWeakKeys.get(key);
        if (p) {
            gc::WeakEntryVector& weakEntries = p->value;
            if (!weakEntries.append(Move(markable)))
                marker.abortLinearWeakMarking();
        } else {
            gc::WeakEntryVector weakEntries;
            MOZ_ALWAYS_TRUE(weakEntries.append(Move(markable)));
            if (!zone->gcWeakKeys.put(JS::GCCellPtr(key), Move(weakEntries)))
                marker.abortLinearWeakMarking();
        }
    }

    bool traceEntries(JSTracer* trc) override {
        MOZ_ASSERT(marked);

        bool markedAny = false;

        for (Enum e(*this); !e.empty(); e.popFront()) {
            // If the entry is live, ensure its key and value are marked.
            bool keyIsMarked = gc::IsMarked(trc->runtime(), &e.front().mutableKey());
            if (!keyIsMarked && keyNeedsMark(e.front().key())) {
                TraceEdge(trc, &e.front().mutableKey(), "proxy-preserved WeakMap entry key");
                keyIsMarked = true;
                markedAny = true;
            }

            if (keyIsMarked) {
                if (!gc::IsMarked(trc->runtime(), &e.front().value())) {
                    TraceEdge(trc, &e.front().value(), "WeakMap entry value");
                    markedAny = true;
                }
            } else if (trc->isWeakMarkingTracer()) {
                // Entry is not yet known to be live. Record this weakmap and
                // the lookup key in the list of weak keys. Also record the
                // delegate, if any, because marking the delegate also marks
                // the entry.
                JS::GCCellPtr weakKey(extractUnbarriered(e.front().key()));
                gc::WeakMarkable markable(this, weakKey);
                addWeakEntry(trc, weakKey, markable);
                if (JSObject* delegate = getDelegate(e.front().key()))
                    addWeakEntry(trc, JS::GCCellPtr(delegate), markable);
            }
        }

        return markedAny;
    }

    JSObject* getDelegate(JSObject* key) const {
        JSWeakmapKeyDelegateOp op = key->getClass()->extWeakmapKeyDelegateOp();
        if (!op)
            return nullptr;

        JSObject* obj = op(key);
        if (!obj)
            return nullptr;

        MOZ_ASSERT(obj->runtimeFromMainThread() == zone->runtimeFromMainThread());
        return obj;
    }

    JSObject* getDelegate(JSScript* script) const {
        return nullptr;
    }

  private:
    void exposeGCThingToActiveJS(const JS::Value& v) const { JS::ExposeValueToActiveJS(v); }
    void exposeGCThingToActiveJS(JSObject* obj) const { JS::ExposeObjectToActiveJS(obj); }

    bool keyNeedsMark(JSObject* key) const {
        JSObject* delegate = getDelegate(key);
        /*
         * Check if the delegate is marked with any color to properly handle
         * gray marking when the key's delegate is black and the map is gray.
         */
        return delegate && gc::IsMarkedUnbarriered(zone->runtimeFromMainThread(), &delegate);
    }

    bool keyNeedsMark(JSScript* script) const {
        return false;
    }

    bool findZoneEdges() override {
        // This is overridden by ObjectValueMap.
        return true;
    }

    void sweep() override {
        /* Remove all entries whose keys remain unmarked. */
        for (Enum e(*this); !e.empty(); e.popFront()) {
            if (gc::IsAboutToBeFinalized(&e.front().mutableKey()))
                e.removeFront();
        }
        /*
         * Once we've swept, all remaining edges should stay within the
         * known-live part of the graph.
         */
        assertEntriesNotAboutToBeFinalized();
    }

    void finish() override {
        Base::finish();
    }

    /* memberOf can be nullptr, which means that the map is not part of a JSObject. */
    void traceMappings(WeakMapTracer* tracer) override {
        for (Range r = Base::all(); !r.empty(); r.popFront()) {
            gc::Cell* key = gc::ToMarkable(r.front().key());
            gc::Cell* value = gc::ToMarkable(r.front().value());
            if (key && value) {
                tracer->trace(memberOf,
                              JS::GCCellPtr(r.front().key().get()),
                              JS::GCCellPtr(r.front().value().get()));
            }
        }
    }

  protected:
    void assertEntriesNotAboutToBeFinalized() {
#if DEBUG
        for (Range r = Base::all(); !r.empty(); r.popFront()) {
            Key k(r.front().key());
            MOZ_ASSERT(!gc::IsAboutToBeFinalized(&k));
            MOZ_ASSERT(!gc::IsAboutToBeFinalized(&r.front().value()));
            MOZ_ASSERT(k == r.front().key());
        }
#endif
    }
};

/* WeakMap methods exposed so they can be installed in the self-hosting global. */

extern JSObject*
InitBareWeakMapCtor(JSContext* cx, js::HandleObject obj);

extern bool
WeakMap_has(JSContext* cx, unsigned argc, Value* vp);

extern bool
WeakMap_get(JSContext* cx, unsigned argc, Value* vp);

extern bool
WeakMap_set(JSContext* cx, unsigned argc, Value* vp);

extern bool
WeakMap_delete(JSContext* cx, unsigned argc, Value* vp);

extern JSObject*
InitWeakMapClass(JSContext* cx, HandleObject obj);


class ObjectValueMap : public WeakMap<HeapPtr<JSObject*>, HeapPtr<Value>,
                                      MovableCellHasher<HeapPtr<JSObject*>>>
{
  public:
    ObjectValueMap(JSContext* cx, JSObject* obj)
      : WeakMap<HeapPtr<JSObject*>, HeapPtr<Value>,
                MovableCellHasher<HeapPtr<JSObject*>>>(cx, obj)
    {}

    virtual bool findZoneEdges();
};


// Generic weak map for mapping objects to other objects.
class ObjectWeakMap
{
    ObjectValueMap map;

  public:
    explicit ObjectWeakMap(JSContext* cx);
    bool init();

    JSObject* lookup(const JSObject* obj);
    bool add(JSContext* cx, JSObject* obj, JSObject* target);
    void clear();

    void trace(JSTracer* trc);
    size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf);
    size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) {
        return mallocSizeOf(this) + sizeOfExcludingThis(mallocSizeOf);
    }

#ifdef JSGC_HASH_TABLE_CHECKS
    void checkAfterMovingGC();
#endif
};

} /* namespace js */

namespace JS {

template <>
struct DeletePolicy<js::ObjectValueMap> : public js::GCManagedDeletePolicy<js::ObjectValueMap>
{};

} /* namespace JS */

#endif /* jsweakmap_h */