summaryrefslogtreecommitdiffstats
path: root/js/src/gc/WeakMap.h
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-19 00:47:55 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-19 00:47:55 +0000
commit26a029d407be480d791972afb5975cf62c9360a6 (patch)
treef435a8308119effd964b339f76abb83a57c29483 /js/src/gc/WeakMap.h
parentInitial commit. (diff)
downloadfirefox-26a029d407be480d791972afb5975cf62c9360a6.tar.xz
firefox-26a029d407be480d791972afb5975cf62c9360a6.zip
Adding upstream version 124.0.1.upstream/124.0.1
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'js/src/gc/WeakMap.h')
-rw-r--r--js/src/gc/WeakMap.h411
1 files changed, 411 insertions, 0 deletions
diff --git a/js/src/gc/WeakMap.h b/js/src/gc/WeakMap.h
new file mode 100644
index 0000000000..959a6fa57e
--- /dev/null
+++ b/js/src/gc/WeakMap.h
@@ -0,0 +1,411 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: set ts=8 sts=2 et sw=2 tw=80:
+ * 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 gc_WeakMap_h
+#define gc_WeakMap_h
+
+#include "mozilla/Atomics.h"
+#include "mozilla/LinkedList.h"
+
+#include "gc/Barrier.h"
+#include "gc/Marking.h"
+#include "gc/Tracer.h"
+#include "gc/Zone.h"
+#include "gc/ZoneAllocator.h"
+#include "js/HashTable.h"
+#include "js/HeapAPI.h"
+
+namespace JS {
+class Zone;
+}
+
+namespace js {
+
+class GCMarker;
+class WeakMapBase;
+struct WeakMapTracer;
+
+extern void DumpWeakMapLog(JSRuntime* rt);
+
+namespace gc {
+
+struct WeakMarkable;
+
+#if defined(JS_GC_ZEAL) || defined(DEBUG)
+// Check whether a weak map entry is marked correctly.
+bool CheckWeakMapEntryMarking(const WeakMapBase* map, Cell* key, Cell* value);
+#endif
+
+} // namespace gc
+
+// 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.
+
+// WeakMaps are marked with an incremental linear-time algorithm that handles
+// all orderings of map and key marking. The basic algorithm is:
+//
+// At first while marking, do nothing special when marking WeakMap keys (there
+// is no straightforward way to know whether a particular object is being used
+// as a key in some weakmap.) When a WeakMap is marked, scan through it to mark
+// all entries with live keys, and collect all unmarked keys into a "weak keys"
+// table.
+//
+// At some point, everything reachable has been marked. At this point, enter
+// "weak marking mode". In this mode, whenever any object is marked, look it up
+// in the weak keys table to see if it is the key for any WeakMap entry and if
+// so, mark the value. When entering weak marking mode, scan the weak key table
+// to find all keys that have been marked since we added them to the table, and
+// mark those entries.
+//
+// In addition, we want weakmap marking to work incrementally. So WeakMap
+// mutations are barriered to keep the weak keys table up to date: entries are
+// removed if their key is removed from the table, etc.
+//
+// You can break down various ways that WeakMap values get marked based on the
+// order that the map and key are marked. All of these assume the map and key
+// get marked at some point:
+//
+// key marked, then map marked:
+// - value was marked with map in `markEntries()`
+// map marked, key already in map, key marked before weak marking mode:
+// - key added to gcEphemeronEdges when map marked in `markEntries()`
+// - value marked during `enterWeakMarkingMode`
+// map marked, key already in map, key marked after weak marking mode:
+// - when key is marked, gcEphemeronEdges[key] triggers marking of value in
+// `markImplicitEdges()`
+// map marked, key inserted into map, key marked:
+// - value was live when inserted and must get marked at some point
+//
+
+using WeakMapColors = HashMap<WeakMapBase*, js::gc::CellColor,
+ DefaultHasher<WeakMapBase*>, SystemAllocPolicy>;
+
+// 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:
+ using CellColor = js::gc::CellColor;
+
+ WeakMapBase(JSObject* memOf, JS::Zone* zone);
+ virtual ~WeakMapBase();
+
+ JS::Zone* zone() const { return zone_; }
+
+ // Garbage collector entry points.
+
+ // Unmark all weak maps in a zone.
+ static void unmarkZone(JS::Zone* zone);
+
+ // 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, GCMarker* marker);
+
+ // Add zone edges for weakmaps with key delegates in a different zone.
+ [[nodiscard]] static bool findSweepGroupEdgesForZone(JS::Zone* zone);
+
+ // Sweep the marked weak maps in a zone, updating moved keys.
+ static void sweepZoneAfterMinorGC(JS::Zone* zone);
+
+ // Trace all 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,
+ WeakMapColors& markedWeakMaps);
+
+ // Restore information about which weak maps are marked for many zones.
+ static void restoreMarkedWeakMaps(WeakMapColors& markedWeakMaps);
+
+#if defined(JS_GC_ZEAL) || defined(DEBUG)
+ static bool checkMarkingForZone(JS::Zone* zone);
+#endif
+
+ 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 findSweepGroupEdges() = 0;
+ virtual void traceWeakEdges(JSTracer* trc) = 0;
+ virtual void traceMappings(WeakMapTracer* tracer) = 0;
+ virtual void clearAndCompact() = 0;
+
+ // We have a key that, if it or its delegate is marked, may lead to a WeakMap
+ // value getting marked. Insert it or its delegate (if any) into the
+ // appropriate zone's gcEphemeronEdges or gcNurseryEphemeronEdges.
+ [[nodiscard]] bool addImplicitEdges(gc::MarkColor mapColor, gc::Cell* key,
+ gc::Cell* delegate,
+ gc::TenuredCell* value);
+ [[nodiscard]] bool addEphemeronTableEntries(gc::MarkColor mapColor,
+ gc::Cell* key, gc::Cell* value,
+ gc::Cell* maybeValue);
+
+ virtual bool markEntries(GCMarker* marker) = 0;
+
+ gc::CellColor mapColor() const { return gc::CellColor(uint32_t(mapColor_)); }
+ void setMapColor(gc::CellColor newColor) { mapColor_ = uint32_t(newColor); }
+ bool markMap(gc::MarkColor markColor);
+
+#ifdef JS_GC_ZEAL
+ virtual bool checkMarking() const = 0;
+ virtual bool allowKeysInOtherZones() const { return false; }
+ friend bool gc::CheckWeakMapEntryMarking(const WeakMapBase*, gc::Cell*,
+ gc::Cell*);
+#endif
+
+ // Object that this weak map is part of, if any.
+ HeapPtr<JSObject*> memberOf;
+
+ // Zone containing this weak map.
+ JS::Zone* zone_;
+
+ // Whether this object has been marked during garbage collection and which
+ // color it was marked.
+ mozilla::Atomic<uint32_t, mozilla::Relaxed> mapColor_;
+
+ friend class JS::Zone;
+};
+
+template <class Key, class Value>
+class WeakMap
+ : private HashMap<Key, Value, StableCellHasher<Key>, ZoneAllocPolicy>,
+ public WeakMapBase {
+ public:
+ using Base = HashMap<Key, Value, StableCellHasher<Key>, ZoneAllocPolicy>;
+
+ using Lookup = typename Base::Lookup;
+ using Entry = typename Base::Entry;
+ using Range = typename Base::Range;
+ using Ptr = typename Base::Ptr;
+ using AddPtr = typename Base::AddPtr;
+
+ struct Enum : public Base::Enum {
+ explicit Enum(WeakMap& map) : Base::Enum(static_cast<Base&>(map)) {}
+ };
+
+ using Base::all;
+ using Base::clear;
+ using Base::count;
+ using Base::empty;
+ using Base::has;
+ using Base::shallowSizeOfExcludingThis;
+
+ // Resolve ambiguity with LinkedListElement<>::remove.
+ using Base::remove;
+
+ using UnbarrieredKey = typename RemoveBarrier<Key>::Type;
+
+ explicit WeakMap(JSContext* cx, JSObject* memOf = nullptr);
+ explicit WeakMap(JS::Zone* zone, JSObject* memOf = nullptr);
+
+ // 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;
+ }
+
+ Ptr lookupUnbarriered(const Lookup& l) const { return Base::lookup(l); }
+
+ AddPtr lookupForAdd(const Lookup& l) {
+ AddPtr p = Base::lookupForAdd(l);
+ if (p) {
+ exposeGCThingToActiveJS(p->value());
+ }
+ return p;
+ }
+
+ template <typename KeyInput, typename ValueInput>
+ [[nodiscard]] bool add(AddPtr& p, KeyInput&& k, ValueInput&& v) {
+ MOZ_ASSERT(gc::ToMarkable(k));
+ return Base::add(p, std::forward<KeyInput>(k), std::forward<ValueInput>(v));
+ }
+
+ template <typename KeyInput, typename ValueInput>
+ [[nodiscard]] bool relookupOrAdd(AddPtr& p, KeyInput&& k, ValueInput&& v) {
+ MOZ_ASSERT(gc::ToMarkable(k));
+ return Base::relookupOrAdd(p, std::forward<KeyInput>(k),
+ std::forward<ValueInput>(v));
+ }
+
+ template <typename KeyInput, typename ValueInput>
+ [[nodiscard]] bool put(KeyInput&& k, ValueInput&& v) {
+ MOZ_ASSERT(gc::ToMarkable(k));
+ return Base::put(std::forward<KeyInput>(k), std::forward<ValueInput>(v));
+ }
+
+ template <typename KeyInput, typename ValueInput>
+ [[nodiscard]] bool putNew(KeyInput&& k, ValueInput&& v) {
+ MOZ_ASSERT(gc::ToMarkable(k));
+ return Base::putNew(std::forward<KeyInput>(k), std::forward<ValueInput>(v));
+ }
+
+ template <typename KeyInput, typename ValueInput>
+ void putNewInfallible(KeyInput&& k, ValueInput&& v) {
+ MOZ_ASSERT(gc::ToMarkable(k));
+ Base::putNewInfallible(std::forward(k), std::forward<KeyInput>(k));
+ }
+
+#ifdef DEBUG
+ template <typename KeyInput, typename ValueInput>
+ bool hasEntry(KeyInput&& key, ValueInput&& value) {
+ Ptr p = Base::lookup(std::forward<KeyInput>(key));
+ return p && p->value() == value;
+ }
+#endif
+
+ bool markEntry(GCMarker* marker, gc::CellColor mapColor, Key& key,
+ Value& value, bool populateWeakKeysTable);
+
+ void trace(JSTracer* trc) override;
+
+ size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf);
+
+ protected:
+ inline void assertMapIsSameZoneWithValue(const Value& v);
+
+ bool markEntries(GCMarker* marker) override;
+
+ protected:
+ // Find sweep group edges for delegates, if the key type has delegates. (If
+ // not, the optimizer should make this a nop.)
+ bool findSweepGroupEdges() override;
+
+ /**
+ * If a wrapper is used as a key in a weakmap, the garbage collector should
+ * keep that object around longer than it otherwise would. We want to avoid
+ * collecting the wrapper (and removing the weakmap entry) as long as the
+ * wrapped object is alive (because the object can be rewrapped and looked up
+ * again). As long as the wrapper is used as a weakmap key, it will not be
+ * collected (and remain in the weakmap) until the wrapped object is
+ * collected.
+ */
+ private:
+ void exposeGCThingToActiveJS(const JS::Value& v) const {
+ JS::ExposeValueToActiveJS(v);
+ }
+ void exposeGCThingToActiveJS(JSObject* obj) const {
+ JS::ExposeObjectToActiveJS(obj);
+ }
+
+ void traceWeakEdges(JSTracer* trc) override;
+
+ void clearAndCompact() override {
+ Base::clear();
+ Base::compact();
+ }
+
+ // memberOf can be nullptr, which means that the map is not part of a
+ // JSObject.
+ void traceMappings(WeakMapTracer* tracer) override;
+
+ protected:
+#if DEBUG
+ void assertEntriesNotAboutToBeFinalized();
+#endif
+
+#ifdef JS_GC_ZEAL
+ bool checkMarking() const override;
+#endif
+};
+
+using ObjectValueWeakMap = WeakMap<HeapPtr<JSObject*>, HeapPtr<Value>>;
+using ValueValueWeakMap = WeakMap<HeapPtr<Value>, HeapPtr<Value>>;
+
+// Generic weak map for mapping objects to other objects.
+class ObjectWeakMap {
+ ObjectValueWeakMap map;
+
+ public:
+ explicit ObjectWeakMap(JSContext* cx);
+
+ JS::Zone* zone() const { return map.zone(); }
+
+ JSObject* lookup(const JSObject* obj);
+ bool add(JSContext* cx, JSObject* obj, JSObject* target);
+ void remove(JSObject* key);
+ void clear();
+
+ void trace(JSTracer* trc);
+ size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf);
+ size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) {
+ return mallocSizeOf(this) + sizeOfExcludingThis(mallocSizeOf);
+ }
+
+ ObjectValueWeakMap& valueMap() { return map; }
+
+#ifdef JSGC_HASH_TABLE_CHECKS
+ void checkAfterMovingGC();
+#endif
+};
+
+// Get the hash from the Symbol.
+[[nodiscard]] HashNumber GetHash(JS::Symbol* sym);
+
+// Return true if the hashes of two Symbols match.
+[[nodiscard]] bool HashMatch(JS::Symbol* key, JS::Symbol* lookup);
+
+// NB: The specialization works based on pointer equality and not on JS Value
+// semantics, and it will assert if the Value's isGCThing() is false.
+//
+// When the JS Value is of type JS::Symbol, we cannot access uniqueIds when it
+// runs on the worker thread, so we get the hashes from the Symbols directly
+// instead.
+template <>
+struct StableCellHasher<HeapPtr<Value>> {
+ using Key = HeapPtr<Value>;
+ using Lookup = Value;
+
+ static bool maybeGetHash(const Lookup& l, HashNumber* hashOut) {
+ if (l.isSymbol()) {
+ *hashOut = GetHash(l.toSymbol());
+ return true;
+ }
+ return StableCellHasher<gc::Cell*>::maybeGetHash(l.toGCThing(), hashOut);
+ }
+ static bool ensureHash(const Lookup& l, HashNumber* hashOut) {
+ if (l.isSymbol()) {
+ *hashOut = GetHash(l.toSymbol());
+ return true;
+ }
+ return StableCellHasher<gc::Cell*>::ensureHash(l.toGCThing(), hashOut);
+ }
+ static HashNumber hash(const Lookup& l) {
+ if (l.isSymbol()) {
+ return GetHash(l.toSymbol());
+ }
+ return StableCellHasher<gc::Cell*>::hash(l.toGCThing());
+ }
+ static bool match(const Key& k, const Lookup& l) {
+ if (l.isSymbol()) {
+ return HashMatch(k.toSymbol(), l.toSymbol());
+ }
+ return StableCellHasher<gc::Cell*>::match(k.toGCThing(), l.toGCThing());
+ }
+};
+
+} /* namespace js */
+
+#endif /* gc_WeakMap_h */