1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/jsweakmap.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,260 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: set ts=8 sts=4 et sw=4 tw=99:
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#ifndef jsweakmap_h
1.11 +#define jsweakmap_h
1.12 +
1.13 +#include "jscompartment.h"
1.14 +#include "jsfriendapi.h"
1.15 +#include "jsobj.h"
1.16 +
1.17 +#include "gc/Marking.h"
1.18 +#include "js/HashTable.h"
1.19 +
1.20 +namespace js {
1.21 +
1.22 +// A subclass template of js::HashMap whose keys and values may be garbage-collected. When
1.23 +// a key is collected, the table entry disappears, dropping its reference to the value.
1.24 +//
1.25 +// More precisely:
1.26 +//
1.27 +// A WeakMap entry is collected if and only if either the WeakMap or the entry's key
1.28 +// is collected. If an entry is not collected, it remains in the WeakMap and it has a
1.29 +// strong reference to the value.
1.30 +//
1.31 +// You must call this table's 'trace' method when the object of which it is a part is
1.32 +// reached by the garbage collection tracer. Once a table is known to be live, the
1.33 +// implementation takes care of the iterative marking needed for weak tables and removing
1.34 +// table entries when collection is complete.
1.35 +
1.36 +// The value for the next pointer for maps not in the map list.
1.37 +static WeakMapBase * const WeakMapNotInList = reinterpret_cast<WeakMapBase *>(1);
1.38 +
1.39 +typedef Vector<WeakMapBase *, 0, SystemAllocPolicy> WeakMapVector;
1.40 +
1.41 +// Common base class for all WeakMap specializations. The collector uses this to call
1.42 +// their markIteratively and sweep methods.
1.43 +class WeakMapBase {
1.44 + public:
1.45 + WeakMapBase(JSObject *memOf, JSCompartment *c);
1.46 + virtual ~WeakMapBase();
1.47 +
1.48 + void trace(JSTracer *tracer) {
1.49 + if (IS_GC_MARKING_TRACER(tracer)) {
1.50 + // We don't do anything with a WeakMap at trace time. Rather, we wait until as
1.51 + // many keys as possible have been marked, and add ourselves to the list of
1.52 + // known-live WeakMaps to be scanned in the iterative marking phase, by
1.53 + // markAllIteratively.
1.54 + JS_ASSERT(tracer->eagerlyTraceWeakMaps() == DoNotTraceWeakMaps);
1.55 +
1.56 + // Add ourselves to the list if we are not already in the list. We can already
1.57 + // be in the list if the weak map is marked more than once due delayed marking.
1.58 + if (next == WeakMapNotInList) {
1.59 + next = compartment->gcWeakMapList;
1.60 + compartment->gcWeakMapList = this;
1.61 + }
1.62 + } else {
1.63 + // If we're not actually doing garbage collection, the keys won't be marked
1.64 + // nicely as needed by the true ephemeral marking algorithm --- custom tracers
1.65 + // such as the cycle collector must use their own means for cycle detection.
1.66 + // So here we do a conservative approximation: pretend all keys are live.
1.67 + if (tracer->eagerlyTraceWeakMaps() == DoNotTraceWeakMaps)
1.68 + return;
1.69 +
1.70 + nonMarkingTraceValues(tracer);
1.71 + if (tracer->eagerlyTraceWeakMaps() == TraceWeakMapKeysValues)
1.72 + nonMarkingTraceKeys(tracer);
1.73 + }
1.74 + }
1.75 +
1.76 + // Garbage collector entry points.
1.77 +
1.78 + // Check all weak maps in a compartment that have been marked as live in this garbage
1.79 + // collection, and mark the values of all entries that have become strong references
1.80 + // to them. Return true if we marked any new values, indicating that we need to make
1.81 + // another pass. In other words, mark my marked maps' marked members' mid-collection.
1.82 + static bool markCompartmentIteratively(JSCompartment *c, JSTracer *tracer);
1.83 +
1.84 + // Remove entries whose keys are dead from all weak maps in a compartment marked as
1.85 + // live in this garbage collection.
1.86 + static void sweepCompartment(JSCompartment *c);
1.87 +
1.88 + // Trace all delayed weak map bindings. Used by the cycle collector.
1.89 + static void traceAllMappings(WeakMapTracer *tracer);
1.90 +
1.91 + bool isInList() { return next != WeakMapNotInList; }
1.92 + void check() { JS_ASSERT(!isInList()); }
1.93 +
1.94 + // Remove everything from the weak map list for a compartment.
1.95 + static void resetCompartmentWeakMapList(JSCompartment *c);
1.96 +
1.97 + // Save the live weak map list for a compartment, appending the data to a vector.
1.98 + static bool saveCompartmentWeakMapList(JSCompartment *c, WeakMapVector &vector);
1.99 +
1.100 + // Restore live weak map lists for multiple compartments from a vector.
1.101 + static void restoreCompartmentWeakMapLists(WeakMapVector &vector);
1.102 +
1.103 + // Remove a weakmap from the live weakmaps list
1.104 + static void removeWeakMapFromList(WeakMapBase *weakmap);
1.105 +
1.106 + protected:
1.107 + // Instance member functions called by the above. Instantiations of WeakMap override
1.108 + // these with definitions appropriate for their Key and Value types.
1.109 + virtual void nonMarkingTraceKeys(JSTracer *tracer) = 0;
1.110 + virtual void nonMarkingTraceValues(JSTracer *tracer) = 0;
1.111 + virtual bool markIteratively(JSTracer *tracer) = 0;
1.112 + virtual void sweep() = 0;
1.113 + virtual void traceMappings(WeakMapTracer *tracer) = 0;
1.114 +
1.115 + // Object that this weak map is part of, if any.
1.116 + JSObject *memberOf;
1.117 +
1.118 + // Compartment that this weak map is part of.
1.119 + JSCompartment *compartment;
1.120 +
1.121 + private:
1.122 + // Link in a list of WeakMaps to mark iteratively and sweep in this garbage
1.123 + // collection, headed by JSCompartment::gcWeakMapList. The last element of
1.124 + // the list has nullptr as its next. Maps not in the list have
1.125 + // WeakMapNotInList as their next. We must distinguish these cases to
1.126 + // avoid creating infinite lists when a weak map gets traced twice due to
1.127 + // delayed marking.
1.128 + WeakMapBase *next;
1.129 +};
1.130 +
1.131 +template <class Key, class Value,
1.132 + class HashPolicy = DefaultHasher<Key> >
1.133 +class WeakMap : public HashMap<Key, Value, HashPolicy, RuntimeAllocPolicy>, public WeakMapBase
1.134 +{
1.135 + public:
1.136 + typedef HashMap<Key, Value, HashPolicy, RuntimeAllocPolicy> Base;
1.137 + typedef typename Base::Enum Enum;
1.138 + typedef typename Base::Lookup Lookup;
1.139 + typedef typename Base::Range Range;
1.140 +
1.141 + explicit WeakMap(JSContext *cx, JSObject *memOf = nullptr)
1.142 + : Base(cx->runtime()), WeakMapBase(memOf, cx->compartment()) { }
1.143 +
1.144 + private:
1.145 + bool markValue(JSTracer *trc, Value *x) {
1.146 + if (gc::IsMarked(x))
1.147 + return false;
1.148 + gc::Mark(trc, x, "WeakMap entry value");
1.149 + JS_ASSERT(gc::IsMarked(x));
1.150 + return true;
1.151 + }
1.152 +
1.153 + void nonMarkingTraceKeys(JSTracer *trc) {
1.154 + for (Enum e(*this); !e.empty(); e.popFront()) {
1.155 + Key key(e.front().key());
1.156 + gc::Mark(trc, &key, "WeakMap entry key");
1.157 + if (key != e.front().key())
1.158 + entryMoved(e, key);
1.159 + }
1.160 + }
1.161 +
1.162 + void nonMarkingTraceValues(JSTracer *trc) {
1.163 + for (Range r = Base::all(); !r.empty(); r.popFront())
1.164 + gc::Mark(trc, &r.front().value(), "WeakMap entry value");
1.165 + }
1.166 +
1.167 + bool keyNeedsMark(JSObject *key) {
1.168 + if (JSWeakmapKeyDelegateOp op = key->getClass()->ext.weakmapKeyDelegateOp) {
1.169 + JSObject *delegate = op(key);
1.170 + /*
1.171 + * Check if the delegate is marked with any color to properly handle
1.172 + * gray marking when the key's delegate is black and the map is
1.173 + * gray.
1.174 + */
1.175 + return delegate && gc::IsObjectMarked(&delegate);
1.176 + }
1.177 + return false;
1.178 + }
1.179 +
1.180 + bool keyNeedsMark(gc::Cell *cell) {
1.181 + return false;
1.182 + }
1.183 +
1.184 + bool markIteratively(JSTracer *trc) {
1.185 + bool markedAny = false;
1.186 + for (Enum e(*this); !e.empty(); e.popFront()) {
1.187 + /* If the entry is live, ensure its key and value are marked. */
1.188 + Key key(e.front().key());
1.189 + if (gc::IsMarked(const_cast<Key *>(&key))) {
1.190 + if (markValue(trc, &e.front().value()))
1.191 + markedAny = true;
1.192 + if (e.front().key() != key)
1.193 + entryMoved(e, key);
1.194 + } else if (keyNeedsMark(key)) {
1.195 + gc::Mark(trc, &e.front().value(), "WeakMap entry value");
1.196 + gc::Mark(trc, &key, "proxy-preserved WeakMap entry key");
1.197 + if (e.front().key() != key)
1.198 + entryMoved(e, key);
1.199 + markedAny = true;
1.200 + }
1.201 + key.unsafeSet(nullptr);
1.202 + }
1.203 + return markedAny;
1.204 + }
1.205 +
1.206 + void sweep() {
1.207 + /* Remove all entries whose keys remain unmarked. */
1.208 + for (Enum e(*this); !e.empty(); e.popFront()) {
1.209 + Key k(e.front().key());
1.210 + if (gc::IsAboutToBeFinalized(&k))
1.211 + e.removeFront();
1.212 + else if (k != e.front().key())
1.213 + entryMoved(e, k);
1.214 + }
1.215 + /*
1.216 + * Once we've swept, all remaining edges should stay within the
1.217 + * known-live part of the graph.
1.218 + */
1.219 + assertEntriesNotAboutToBeFinalized();
1.220 + }
1.221 +
1.222 + /* memberOf can be nullptr, which means that the map is not part of a JSObject. */
1.223 + void traceMappings(WeakMapTracer *tracer) {
1.224 + for (Range r = Base::all(); !r.empty(); r.popFront()) {
1.225 + gc::Cell *key = gc::ToMarkable(r.front().key());
1.226 + gc::Cell *value = gc::ToMarkable(r.front().value());
1.227 + if (key && value) {
1.228 + tracer->callback(tracer, memberOf,
1.229 + key, gc::TraceKind(r.front().key()),
1.230 + value, gc::TraceKind(r.front().value()));
1.231 + }
1.232 + }
1.233 + }
1.234 +
1.235 + /* Rekey an entry when moved, ensuring we do not trigger barriers. */
1.236 + void entryMoved(Enum &eArg, const Key &k) {
1.237 + typedef typename HashMap<typename Unbarriered<Key>::type,
1.238 + typename Unbarriered<Value>::type,
1.239 + typename Unbarriered<HashPolicy>::type,
1.240 + RuntimeAllocPolicy>::Enum UnbarrieredEnum;
1.241 + UnbarrieredEnum &e = reinterpret_cast<UnbarrieredEnum &>(eArg);
1.242 + e.rekeyFront(reinterpret_cast<const typename Unbarriered<Key>::type &>(k));
1.243 + }
1.244 +
1.245 +protected:
1.246 + void assertEntriesNotAboutToBeFinalized() {
1.247 +#if DEBUG
1.248 + for (Range r = Base::all(); !r.empty(); r.popFront()) {
1.249 + Key k(r.front().key());
1.250 + JS_ASSERT(!gc::IsAboutToBeFinalized(&k));
1.251 + JS_ASSERT(!gc::IsAboutToBeFinalized(&r.front().value()));
1.252 + JS_ASSERT(k == r.front().key());
1.253 + }
1.254 +#endif
1.255 + }
1.256 +};
1.257 +
1.258 +} /* namespace js */
1.259 +
1.260 +extern JSObject *
1.261 +js_InitWeakMapClass(JSContext *cx, js::HandleObject obj);
1.262 +
1.263 +#endif /* jsweakmap_h */
