diff -r 000000000000 -r 6474c204b198 js/src/jsweakmap.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/js/src/jsweakmap.h Wed Dec 31 06:09:35 2014 +0100 @@ -0,0 +1,260 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- + * vim: set ts=8 sts=4 et sw=4 tw=99: + * 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 "jscompartment.h" +#include "jsfriendapi.h" +#include "jsobj.h" + +#include "gc/Marking.h" +#include "js/HashTable.h" + +namespace js { + +// 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 collected if and only if either the WeakMap or the entry's key +// is collected. If an entry is not collected, it remains in the WeakMap and it has a +// strong reference to the value. +// +// You must call this table's 'trace' method when the object of which it is a part is +// reached by the garbage collection tracer. Once a table is known to be live, the +// implementation takes care of the iterative marking needed for weak tables and removing +// table entries when collection is complete. + +// The value for the next pointer for maps not in the map list. +static WeakMapBase * const WeakMapNotInList = reinterpret_cast(1); + +typedef Vector WeakMapVector; + +// Common base class for all WeakMap specializations. The collector uses this to call +// their markIteratively and sweep methods. +class WeakMapBase { + public: + WeakMapBase(JSObject *memOf, JSCompartment *c); + virtual ~WeakMapBase(); + + void trace(JSTracer *tracer) { + if (IS_GC_MARKING_TRACER(tracer)) { + // We don't do anything with a WeakMap at trace time. Rather, we wait until as + // many keys as possible have been marked, and add ourselves to the list of + // known-live WeakMaps to be scanned in the iterative marking phase, by + // markAllIteratively. + JS_ASSERT(tracer->eagerlyTraceWeakMaps() == DoNotTraceWeakMaps); + + // Add ourselves to the list if we are not already in the list. We can already + // be in the list if the weak map is marked more than once due delayed marking. + if (next == WeakMapNotInList) { + next = compartment->gcWeakMapList; + compartment->gcWeakMapList = this; + } + } else { + // If we're not actually doing garbage collection, the keys won't be marked + // nicely as needed by the true ephemeral marking algorithm --- custom tracers + // such as the cycle collector must use their own means for cycle detection. + // So here we do a conservative approximation: pretend all keys are live. + if (tracer->eagerlyTraceWeakMaps() == DoNotTraceWeakMaps) + return; + + nonMarkingTraceValues(tracer); + if (tracer->eagerlyTraceWeakMaps() == TraceWeakMapKeysValues) + nonMarkingTraceKeys(tracer); + } + } + + // Garbage collector entry points. + + // Check all weak maps in a compartment 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 markCompartmentIteratively(JSCompartment *c, JSTracer *tracer); + + // Remove entries whose keys are dead from all weak maps in a compartment marked as + // live in this garbage collection. + static void sweepCompartment(JSCompartment *c); + + // Trace all delayed weak map bindings. Used by the cycle collector. + static void traceAllMappings(WeakMapTracer *tracer); + + bool isInList() { return next != WeakMapNotInList; } + void check() { JS_ASSERT(!isInList()); } + + // Remove everything from the weak map list for a compartment. + static void resetCompartmentWeakMapList(JSCompartment *c); + + // Save the live weak map list for a compartment, appending the data to a vector. + static bool saveCompartmentWeakMapList(JSCompartment *c, WeakMapVector &vector); + + // Restore live weak map lists for multiple compartments from a vector. + static void restoreCompartmentWeakMapLists(WeakMapVector &vector); + + // Remove a weakmap from the live weakmaps list + static void removeWeakMapFromList(WeakMapBase *weakmap); + + protected: + // Instance member functions called by the above. Instantiations of WeakMap override + // these with definitions appropriate for their Key and Value types. + virtual void nonMarkingTraceKeys(JSTracer *tracer) = 0; + virtual void nonMarkingTraceValues(JSTracer *tracer) = 0; + virtual bool markIteratively(JSTracer *tracer) = 0; + virtual void sweep() = 0; + virtual void traceMappings(WeakMapTracer *tracer) = 0; + + // Object that this weak map is part of, if any. + JSObject *memberOf; + + // Compartment that this weak map is part of. + JSCompartment *compartment; + + private: + // Link in a list of WeakMaps to mark iteratively and sweep in this garbage + // collection, headed by JSCompartment::gcWeakMapList. The last element of + // the list has nullptr as its next. Maps not in the list have + // WeakMapNotInList as their next. We must distinguish these cases to + // avoid creating infinite lists when a weak map gets traced twice due to + // delayed marking. + WeakMapBase *next; +}; + +template > +class WeakMap : public HashMap, public WeakMapBase +{ + public: + typedef HashMap Base; + typedef typename Base::Enum Enum; + typedef typename Base::Lookup Lookup; + typedef typename Base::Range Range; + + explicit WeakMap(JSContext *cx, JSObject *memOf = nullptr) + : Base(cx->runtime()), WeakMapBase(memOf, cx->compartment()) { } + + private: + bool markValue(JSTracer *trc, Value *x) { + if (gc::IsMarked(x)) + return false; + gc::Mark(trc, x, "WeakMap entry value"); + JS_ASSERT(gc::IsMarked(x)); + return true; + } + + void nonMarkingTraceKeys(JSTracer *trc) { + for (Enum e(*this); !e.empty(); e.popFront()) { + Key key(e.front().key()); + gc::Mark(trc, &key, "WeakMap entry key"); + if (key != e.front().key()) + entryMoved(e, key); + } + } + + void nonMarkingTraceValues(JSTracer *trc) { + for (Range r = Base::all(); !r.empty(); r.popFront()) + gc::Mark(trc, &r.front().value(), "WeakMap entry value"); + } + + bool keyNeedsMark(JSObject *key) { + if (JSWeakmapKeyDelegateOp op = key->getClass()->ext.weakmapKeyDelegateOp) { + JSObject *delegate = op(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::IsObjectMarked(&delegate); + } + return false; + } + + bool keyNeedsMark(gc::Cell *cell) { + return false; + } + + bool markIteratively(JSTracer *trc) { + bool markedAny = false; + for (Enum e(*this); !e.empty(); e.popFront()) { + /* If the entry is live, ensure its key and value are marked. */ + Key key(e.front().key()); + if (gc::IsMarked(const_cast(&key))) { + if (markValue(trc, &e.front().value())) + markedAny = true; + if (e.front().key() != key) + entryMoved(e, key); + } else if (keyNeedsMark(key)) { + gc::Mark(trc, &e.front().value(), "WeakMap entry value"); + gc::Mark(trc, &key, "proxy-preserved WeakMap entry key"); + if (e.front().key() != key) + entryMoved(e, key); + markedAny = true; + } + key.unsafeSet(nullptr); + } + return markedAny; + } + + void sweep() { + /* Remove all entries whose keys remain unmarked. */ + for (Enum e(*this); !e.empty(); e.popFront()) { + Key k(e.front().key()); + if (gc::IsAboutToBeFinalized(&k)) + e.removeFront(); + else if (k != e.front().key()) + entryMoved(e, k); + } + /* + * Once we've swept, all remaining edges should stay within the + * known-live part of the graph. + */ + assertEntriesNotAboutToBeFinalized(); + } + + /* memberOf can be nullptr, which means that the map is not part of a JSObject. */ + void traceMappings(WeakMapTracer *tracer) { + 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->callback(tracer, memberOf, + key, gc::TraceKind(r.front().key()), + value, gc::TraceKind(r.front().value())); + } + } + } + + /* Rekey an entry when moved, ensuring we do not trigger barriers. */ + void entryMoved(Enum &eArg, const Key &k) { + typedef typename HashMap::type, + typename Unbarriered::type, + typename Unbarriered::type, + RuntimeAllocPolicy>::Enum UnbarrieredEnum; + UnbarrieredEnum &e = reinterpret_cast(eArg); + e.rekeyFront(reinterpret_cast::type &>(k)); + } + +protected: + void assertEntriesNotAboutToBeFinalized() { +#if DEBUG + for (Range r = Base::all(); !r.empty(); r.popFront()) { + Key k(r.front().key()); + JS_ASSERT(!gc::IsAboutToBeFinalized(&k)); + JS_ASSERT(!gc::IsAboutToBeFinalized(&r.front().value())); + JS_ASSERT(k == r.front().key()); + } +#endif + } +}; + +} /* namespace js */ + +extern JSObject * +js_InitWeakMapClass(JSContext *cx, js::HandleObject obj); + +#endif /* jsweakmap_h */