From 26a029d407be480d791972afb5975cf62c9360a6 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Fri, 19 Apr 2024 02:47:55 +0200 Subject: Adding upstream version 124.0.1. Signed-off-by: Daniel Baumann --- js/src/gc/WeakMap.h | 411 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 411 insertions(+) create mode 100644 js/src/gc/WeakMap.h (limited to 'js/src/gc/WeakMap.h') 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, SystemAllocPolicy>; + +// Common base class for all WeakMap specializations, used for calling +// subclasses' GC-related methods. +class WeakMapBase : public mozilla::LinkedListElement { + 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 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 mapColor_; + + friend class JS::Zone; +}; + +template +class WeakMap + : private HashMap, ZoneAllocPolicy>, + public WeakMapBase { + public: + using Base = HashMap, 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(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::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 + [[nodiscard]] bool add(AddPtr& p, KeyInput&& k, ValueInput&& v) { + MOZ_ASSERT(gc::ToMarkable(k)); + return Base::add(p, std::forward(k), std::forward(v)); + } + + template + [[nodiscard]] bool relookupOrAdd(AddPtr& p, KeyInput&& k, ValueInput&& v) { + MOZ_ASSERT(gc::ToMarkable(k)); + return Base::relookupOrAdd(p, std::forward(k), + std::forward(v)); + } + + template + [[nodiscard]] bool put(KeyInput&& k, ValueInput&& v) { + MOZ_ASSERT(gc::ToMarkable(k)); + return Base::put(std::forward(k), std::forward(v)); + } + + template + [[nodiscard]] bool putNew(KeyInput&& k, ValueInput&& v) { + MOZ_ASSERT(gc::ToMarkable(k)); + return Base::putNew(std::forward(k), std::forward(v)); + } + + template + void putNewInfallible(KeyInput&& k, ValueInput&& v) { + MOZ_ASSERT(gc::ToMarkable(k)); + Base::putNewInfallible(std::forward(k), std::forward(k)); + } + +#ifdef DEBUG + template + bool hasEntry(KeyInput&& key, ValueInput&& value) { + Ptr p = Base::lookup(std::forward(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>; +using ValueValueWeakMap = WeakMap, HeapPtr>; + +// 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> { + using Key = HeapPtr; + using Lookup = Value; + + static bool maybeGetHash(const Lookup& l, HashNumber* hashOut) { + if (l.isSymbol()) { + *hashOut = GetHash(l.toSymbol()); + return true; + } + return StableCellHasher::maybeGetHash(l.toGCThing(), hashOut); + } + static bool ensureHash(const Lookup& l, HashNumber* hashOut) { + if (l.isSymbol()) { + *hashOut = GetHash(l.toSymbol()); + return true; + } + return StableCellHasher::ensureHash(l.toGCThing(), hashOut); + } + static HashNumber hash(const Lookup& l) { + if (l.isSymbol()) { + return GetHash(l.toSymbol()); + } + return StableCellHasher::hash(l.toGCThing()); + } + static bool match(const Key& k, const Lookup& l) { + if (l.isSymbol()) { + return HashMatch(k.toSymbol(), l.toSymbol()); + } + return StableCellHasher::match(k.toGCThing(), l.toGCThing()); + } +}; + +} /* namespace js */ + +#endif /* gc_WeakMap_h */ -- cgit v1.2.3