diff options
Diffstat (limited to 'js/public/UbiNode.h')
| -rw-r--r-- | js/public/UbiNode.h | 1146 |
1 files changed, 1146 insertions, 0 deletions
diff --git a/js/public/UbiNode.h b/js/public/UbiNode.h new file mode 100644 index 000000000..7332f198f --- /dev/null +++ b/js/public/UbiNode.h @@ -0,0 +1,1146 @@ +/* -*- 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 js_UbiNode_h +#define js_UbiNode_h + +#include "mozilla/Alignment.h" +#include "mozilla/Assertions.h" +#include "mozilla/Attributes.h" +#include "mozilla/Maybe.h" +#include "mozilla/MemoryReporting.h" +#include "mozilla/Move.h" +#include "mozilla/RangedPtr.h" +#include "mozilla/TypeTraits.h" +#include "mozilla/Variant.h" + +#include "jspubtd.h" + +#include "js/GCAPI.h" +#include "js/HashTable.h" +#include "js/RootingAPI.h" +#include "js/TracingAPI.h" +#include "js/TypeDecls.h" +#include "js/UniquePtr.h" +#include "js/Value.h" +#include "js/Vector.h" + +// JS::ubi::Node +// +// JS::ubi::Node is a pointer-like type designed for internal use by heap +// analysis tools. A ubi::Node can refer to: +// +// - a JS value, like a string, object, or symbol; +// - an internal SpiderMonkey structure, like a shape or a scope chain object +// - an instance of some embedding-provided type: in Firefox, an XPCOM +// object, or an internal DOM node class instance +// +// A ubi::Node instance provides metadata about its referent, and can +// enumerate its referent's outgoing edges, so you can implement heap analysis +// algorithms that walk the graph - finding paths between objects, or +// computing heap dominator trees, say - using ubi::Node, while remaining +// ignorant of the details of the types you're operating on. +// +// Of course, when it comes to presenting the results in a developer-facing +// tool, you'll need to stop being ignorant of those details, because you have +// to discuss the ubi::Nodes' referents with the developer. Here, ubi::Node +// can hand you dynamically checked, properly typed pointers to the original +// objects via the as<T> method, or generate descriptions of the referent +// itself. +// +// ubi::Node instances are lightweight (two-word) value types. Instances: +// - compare equal if and only if they refer to the same object; +// - have hash values that respect their equality relation; and +// - have serializations that are only equal if the ubi::Nodes are equal. +// +// A ubi::Node is only valid for as long as its referent is alive; if its +// referent goes away, the ubi::Node becomes a dangling pointer. A ubi::Node +// that refers to a GC-managed object is not automatically a GC root; if the +// GC frees or relocates its referent, the ubi::Node becomes invalid. A +// ubi::Node that refers to a reference-counted object does not bump the +// reference count. +// +// ubi::Node values require no supporting data structures, making them +// feasible for use in memory-constrained devices --- ideally, the memory +// requirements of the algorithm which uses them will be the limiting factor, +// not the demands of ubi::Node itself. +// +// One can construct a ubi::Node value given a pointer to a type that ubi::Node +// supports. In the other direction, one can convert a ubi::Node back to a +// pointer; these downcasts are checked dynamically. In particular, one can +// convert a 'JSContext*' to a ubi::Node, yielding a node with an outgoing edge +// for every root registered with the runtime; starting from this, one can walk +// the entire heap. (Of course, one could also start traversal at any other kind +// of type to which one has a pointer.) +// +// +// Extending ubi::Node To Handle Your Embedding's Types +// +// To add support for a new ubi::Node referent type R, you must define a +// specialization of the ubi::Concrete template, ubi::Concrete<R>, which +// inherits from ubi::Base. ubi::Node itself uses the specialization for +// compile-time information (i.e. the checked conversions between R * and +// ubi::Node), and the inheritance for run-time dispatching. +// +// +// ubi::Node Exposes Implementation Details +// +// In many cases, a JavaScript developer's view of their data differs +// substantially from its actual implementation. For example, while the +// ECMAScript specification describes objects as maps from property names to +// sets of attributes (like ECMAScript's [[Value]]), in practice many objects +// have only a pointer to a shape, shared with other similar objects, and +// indexed slots that contain the [[Value]] attributes. As another example, a +// string produced by concatenating two other strings may sometimes be +// represented by a "rope", a structure that points to the two original +// strings. +// +// We intend to use ubi::Node to write tools that report memory usage, so it's +// important that ubi::Node accurately portray how much memory nodes consume. +// Thus, for example, when data that apparently belongs to multiple nodes is +// in fact shared in a common structure, ubi::Node's graph uses a separate +// node for that shared structure, and presents edges to it from the data's +// apparent owners. For example, ubi::Node exposes SpiderMonkey objects' +// shapes and base shapes, and exposes rope string and substring structure, +// because these optimizations become visible when a tool reports how much +// memory a structure consumes. +// +// However, fine granularity is not a goal. When a particular object is the +// exclusive owner of a separate block of memory, ubi::Node may present the +// object and its block as a single node, and add their sizes together when +// reporting the node's size, as there is no meaningful loss of data in this +// case. Thus, for example, a ubi::Node referring to a JavaScript object, when +// asked for the object's size in bytes, includes the object's slot and +// element arrays' sizes in the total. There is no separate ubi::Node value +// representing the slot and element arrays, since they are owned exclusively +// by the object. +// +// +// Presenting Analysis Results To JavaScript Developers +// +// If an analysis provides its results in terms of ubi::Node values, a user +// interface presenting those results will generally need to clean them up +// before they can be understood by JavaScript developers. For example, +// JavaScript developers should not need to understand shapes, only JavaScript +// objects. Similarly, they should not need to understand the distinction +// between DOM nodes and the JavaScript shadow objects that represent them. +// +// +// Rooting Restrictions +// +// At present there is no way to root ubi::Node instances, so instances can't be +// live across any operation that might GC. Analyses using ubi::Node must either +// run to completion and convert their results to some other rootable type, or +// save their intermediate state in some rooted structure if they must GC before +// they complete. (For algorithms like path-finding and dominator tree +// computation, we implement the algorithm avoiding any operation that could +// cause a GC --- and use AutoCheckCannotGC to verify this.) +// +// If this restriction prevents us from implementing interesting tools, we may +// teach the GC how to root ubi::Nodes, fix up hash tables that use them as +// keys, etc. +// +// +// Hostile Graph Structure +// +// Analyses consuming ubi::Node graphs must be robust when presented with graphs +// that are deliberately constructed to exploit their weaknesses. When operating +// on live graphs, web content has control over the object graph, and less +// direct control over shape and string structure, and analyses should be +// prepared to handle extreme cases gracefully. For example, if an analysis were +// to use the C++ stack in a depth-first traversal, carefully constructed +// content could cause the analysis to overflow the stack. +// +// When ubi::Nodes refer to nodes deserialized from a heap snapshot, analyses +// must be even more careful: since snapshots often come from potentially +// compromised e10s content processes, even properties normally guaranteed by +// the platform (the proper linking of DOM nodes, for example) might be +// corrupted. While it is the deserializer's responsibility to check the basic +// structure of the snapshot file, the analyses should be prepared for ubi::Node +// graphs constructed from snapshots to be even more bizarre. + +class JSAtom; + +namespace JS { +namespace ubi { + +class Edge; +class EdgeRange; +class StackFrame; + +} // namespace ubi +} // namespace JS + +namespace JS { +namespace ubi { + +using mozilla::Forward; +using mozilla::Maybe; +using mozilla::Move; +using mozilla::RangedPtr; +using mozilla::Variant; + +template <typename T> +using Vector = mozilla::Vector<T, 0, js::SystemAllocPolicy>; + +/*** ubi::StackFrame ******************************************************************************/ + +// Concrete JS::ubi::StackFrame instances backed by a live SavedFrame object +// store their strings as JSAtom*, while deserialized stack frames from offline +// heap snapshots store their strings as const char16_t*. In order to provide +// zero-cost accessors to these strings in a single interface that works with +// both cases, we use this variant type. +class JS_PUBLIC_API(AtomOrTwoByteChars) : public Variant<JSAtom*, const char16_t*> { + using Base = Variant<JSAtom*, const char16_t*>; + + public: + template<typename T> + MOZ_IMPLICIT AtomOrTwoByteChars(T&& rhs) : Base(Forward<T>(rhs)) { } + + template<typename T> + AtomOrTwoByteChars& operator=(T&& rhs) { + MOZ_ASSERT(this != &rhs, "self-move disallowed"); + this->~AtomOrTwoByteChars(); + new (this) AtomOrTwoByteChars(Forward<T>(rhs)); + return *this; + } + + // Return the length of the given AtomOrTwoByteChars string. + size_t length(); + + // Copy the given AtomOrTwoByteChars string into the destination buffer, + // inflating if necessary. Does NOT null terminate. Returns the number of + // characters written to destination. + size_t copyToBuffer(RangedPtr<char16_t> destination, size_t length); +}; + +// The base class implemented by each ConcreteStackFrame<T> type. Subclasses +// must not add data members to this class. +class BaseStackFrame { + friend class StackFrame; + + BaseStackFrame(const StackFrame&) = delete; + BaseStackFrame& operator=(const StackFrame&) = delete; + + protected: + void* ptr; + explicit BaseStackFrame(void* ptr) : ptr(ptr) { } + + public: + // This is a value type that should not have a virtual destructor. Don't add + // destructors in subclasses! + + // Get a unique identifier for this StackFrame. The identifier is not valid + // across garbage collections. + virtual uint64_t identifier() const { return uint64_t(uintptr_t(ptr)); } + + // Get this frame's parent frame. + virtual StackFrame parent() const = 0; + + // Get this frame's line number. + virtual uint32_t line() const = 0; + + // Get this frame's column number. + virtual uint32_t column() const = 0; + + // Get this frame's source name. Never null. + virtual AtomOrTwoByteChars source() const = 0; + + // Return this frame's function name if named, otherwise the inferred + // display name. Can be null. + virtual AtomOrTwoByteChars functionDisplayName() const = 0; + + // Returns true if this frame's function is system JavaScript running with + // trusted principals, false otherwise. + virtual bool isSystem() const = 0; + + // Return true if this frame's function is a self-hosted JavaScript builtin, + // false otherwise. + virtual bool isSelfHosted(JSContext* cx) const = 0; + + // Construct a SavedFrame stack for the stack starting with this frame and + // containing all of its parents. The SavedFrame objects will be placed into + // cx's current compartment. + // + // Note that the process of + // + // SavedFrame + // | + // V + // JS::ubi::StackFrame + // | + // V + // offline heap snapshot + // | + // V + // JS::ubi::StackFrame + // | + // V + // SavedFrame + // + // is lossy because we cannot serialize and deserialize the SavedFrame's + // principals in the offline heap snapshot, so JS::ubi::StackFrame + // simplifies the principals check into the boolean isSystem() state. This + // is fine because we only expose JS::ubi::Stack to devtools and chrome + // code, and not to the web platform. + virtual MOZ_MUST_USE bool constructSavedFrameStack(JSContext* cx, + MutableHandleObject outSavedFrameStack) + const = 0; + + // Trace the concrete implementation of JS::ubi::StackFrame. + virtual void trace(JSTracer* trc) = 0; +}; + +// A traits template with a specialization for each backing type that implements +// the ubi::BaseStackFrame interface. Each specialization must be the a subclass +// of ubi::BaseStackFrame. +template<typename T> class ConcreteStackFrame; + +// A JS::ubi::StackFrame represents a frame in a recorded stack. It can be +// backed either by a live SavedFrame object or by a structure deserialized from +// an offline heap snapshot. +// +// It is a value type that may be memcpy'd hither and thither without worrying +// about constructors or destructors, similar to POD types. +// +// Its lifetime is the same as the lifetime of the graph that is being analyzed +// by the JS::ubi::Node that the JS::ubi::StackFrame came from. That is, if the +// graph being analyzed is the live heap graph, the JS::ubi::StackFrame is only +// valid within the scope of an AutoCheckCannotGC; if the graph being analyzed +// is an offline heap snapshot, the JS::ubi::StackFrame is valid as long as the +// offline heap snapshot is alive. +class StackFrame { + // Storage in which we allocate BaseStackFrame subclasses. + mozilla::AlignedStorage2<BaseStackFrame> storage; + + BaseStackFrame* base() { return storage.addr(); } + const BaseStackFrame* base() const { return storage.addr(); } + + template<typename T> + void construct(T* ptr) { + static_assert(mozilla::IsBaseOf<BaseStackFrame, ConcreteStackFrame<T>>::value, + "ConcreteStackFrame<T> must inherit from BaseStackFrame"); + static_assert(sizeof(ConcreteStackFrame<T>) == sizeof(*base()), + "ubi::ConcreteStackFrame<T> specializations must be the same size as " + "ubi::BaseStackFrame"); + ConcreteStackFrame<T>::construct(base(), ptr); + } + struct ConstructFunctor; + + public: + StackFrame() { construct<void>(nullptr); } + + template<typename T> + MOZ_IMPLICIT StackFrame(T* ptr) { + construct(ptr); + } + + template<typename T> + StackFrame& operator=(T* ptr) { + construct(ptr); + return *this; + } + + // Constructors accepting SpiderMonkey's generic-pointer-ish types. + + template<typename T> + explicit StackFrame(const JS::Handle<T*>& handle) { + construct(handle.get()); + } + + template<typename T> + StackFrame& operator=(const JS::Handle<T*>& handle) { + construct(handle.get()); + return *this; + } + + template<typename T> + explicit StackFrame(const JS::Rooted<T*>& root) { + construct(root.get()); + } + + template<typename T> + StackFrame& operator=(const JS::Rooted<T*>& root) { + construct(root.get()); + return *this; + } + + // Because StackFrame is just a vtable pointer and an instance pointer, we + // can memcpy everything around instead of making concrete classes define + // virtual constructors. See the comment above Node's copy constructor for + // more details; that comment applies here as well. + StackFrame(const StackFrame& rhs) { + memcpy(storage.u.mBytes, rhs.storage.u.mBytes, sizeof(storage.u)); + } + + StackFrame& operator=(const StackFrame& rhs) { + memcpy(storage.u.mBytes, rhs.storage.u.mBytes, sizeof(storage.u)); + return *this; + } + + bool operator==(const StackFrame& rhs) const { return base()->ptr == rhs.base()->ptr; } + bool operator!=(const StackFrame& rhs) const { return !(*this == rhs); } + + explicit operator bool() const { + return base()->ptr != nullptr; + } + + // Copy this StackFrame's source name into the given |destination| + // buffer. Copy no more than |length| characters. The result is *not* null + // terminated. Returns how many characters were written into the buffer. + size_t source(RangedPtr<char16_t> destination, size_t length) const; + + // Copy this StackFrame's function display name into the given |destination| + // buffer. Copy no more than |length| characters. The result is *not* null + // terminated. Returns how many characters were written into the buffer. + size_t functionDisplayName(RangedPtr<char16_t> destination, size_t length) const; + + // Get the size of the respective strings. 0 is returned for null strings. + size_t sourceLength(); + size_t functionDisplayNameLength(); + + // Methods that forward to virtual calls through BaseStackFrame. + + void trace(JSTracer* trc) { base()->trace(trc); } + uint64_t identifier() const { + auto id = base()->identifier(); + MOZ_ASSERT(JS::Value::isNumberRepresentable(id)); + return id; + } + uint32_t line() const { return base()->line(); } + uint32_t column() const { return base()->column(); } + AtomOrTwoByteChars source() const { return base()->source(); } + AtomOrTwoByteChars functionDisplayName() const { return base()->functionDisplayName(); } + StackFrame parent() const { return base()->parent(); } + bool isSystem() const { return base()->isSystem(); } + bool isSelfHosted(JSContext* cx) const { return base()->isSelfHosted(cx); } + MOZ_MUST_USE bool constructSavedFrameStack(JSContext* cx, + MutableHandleObject outSavedFrameStack) const { + return base()->constructSavedFrameStack(cx, outSavedFrameStack); + } + + struct HashPolicy { + using Lookup = JS::ubi::StackFrame; + + static js::HashNumber hash(const Lookup& lookup) { + return lookup.identifier(); + } + + static bool match(const StackFrame& key, const Lookup& lookup) { + return key == lookup; + } + + static void rekey(StackFrame& k, const StackFrame& newKey) { + k = newKey; + } + }; +}; + +// The ubi::StackFrame null pointer. Any attempt to operate on a null +// ubi::StackFrame crashes. +template<> +class ConcreteStackFrame<void> : public BaseStackFrame { + explicit ConcreteStackFrame(void* ptr) : BaseStackFrame(ptr) { } + + public: + static void construct(void* storage, void*) { new (storage) ConcreteStackFrame(nullptr); } + + uint64_t identifier() const override { return 0; } + void trace(JSTracer* trc) override { } + MOZ_MUST_USE bool constructSavedFrameStack(JSContext* cx, MutableHandleObject out) + const override + { + out.set(nullptr); + return true; + } + + uint32_t line() const override { MOZ_CRASH("null JS::ubi::StackFrame"); } + uint32_t column() const override { MOZ_CRASH("null JS::ubi::StackFrame"); } + AtomOrTwoByteChars source() const override { MOZ_CRASH("null JS::ubi::StackFrame"); } + AtomOrTwoByteChars functionDisplayName() const override { MOZ_CRASH("null JS::ubi::StackFrame"); } + StackFrame parent() const override { MOZ_CRASH("null JS::ubi::StackFrame"); } + bool isSystem() const override { MOZ_CRASH("null JS::ubi::StackFrame"); } + bool isSelfHosted(JSContext* cx) const override { MOZ_CRASH("null JS::ubi::StackFrame"); } +}; + +MOZ_MUST_USE JS_PUBLIC_API(bool) +ConstructSavedFrameStackSlow(JSContext* cx, + JS::ubi::StackFrame& frame, + MutableHandleObject outSavedFrameStack); + + +/*** ubi::Node ************************************************************************************/ + +// A concrete node specialization can claim its referent is a member of a +// particular "coarse type" which is less specific than the actual +// implementation type but generally more palatable for web developers. For +// example, JitCode can be considered to have a coarse type of "Script". This is +// used by some analyses for putting nodes into different buckets. The default, +// if a concrete specialization does not provide its own mapping to a CoarseType +// variant, is "Other". +// +// NB: the values associated with a particular enum variant must not change or +// be reused for new variants. Doing so will cause inspecting ubi::Nodes backed +// by an offline heap snapshot from an older SpiderMonkey/Firefox version to +// break. Consider this enum append only. +enum class CoarseType: uint32_t { + Other = 0, + Object = 1, + Script = 2, + String = 3, + + FIRST = Other, + LAST = String +}; + +inline uint32_t +CoarseTypeToUint32(CoarseType type) +{ + return static_cast<uint32_t>(type); +} + +inline bool +Uint32IsValidCoarseType(uint32_t n) +{ + auto first = static_cast<uint32_t>(CoarseType::FIRST); + auto last = static_cast<uint32_t>(CoarseType::LAST); + MOZ_ASSERT(first < last); + return first <= n && n <= last; +} + +inline CoarseType +Uint32ToCoarseType(uint32_t n) +{ + MOZ_ASSERT(Uint32IsValidCoarseType(n)); + return static_cast<CoarseType>(n); +} + +// The base class implemented by each ubi::Node referent type. Subclasses must +// not add data members to this class. +class JS_PUBLIC_API(Base) { + friend class Node; + + // For performance's sake, we'd prefer to avoid a virtual destructor; and + // an empty constructor seems consistent with the 'lightweight value type' + // visible behavior we're trying to achieve. But if the destructor isn't + // virtual, and a subclass overrides it, the subclass's destructor will be + // ignored. Is there a way to make the compiler catch that error? + + protected: + // Space for the actual pointer. Concrete subclasses should define a + // properly typed 'get' member function to access this. + void* ptr; + + explicit Base(void* ptr) : ptr(ptr) { } + + public: + bool operator==(const Base& rhs) const { + // Some compilers will indeed place objects of different types at + // the same address, so technically, we should include the vtable + // in this comparison. But it seems unlikely to cause problems in + // practice. + return ptr == rhs.ptr; + } + bool operator!=(const Base& rhs) const { return !(*this == rhs); } + + // An identifier for this node, guaranteed to be stable and unique for as + // long as this ubi::Node's referent is alive and at the same address. + // + // This is probably suitable for use in serializations, as it is an integral + // type. It may also help save memory when constructing HashSets of + // ubi::Nodes: since a uint64_t will always be smaller-or-equal-to the size + // of a ubi::Node, a HashSet<ubi::Node::Id> may use less space per element + // than a HashSet<ubi::Node>. + // + // (Note that 'unique' only means 'up to equality on ubi::Node'; see the + // caveats about multiple objects allocated at the same address for + // 'ubi::Node::operator=='.) + using Id = uint64_t; + virtual Id identifier() const { return Id(uintptr_t(ptr)); } + + // Returns true if this node is pointing to something on the live heap, as + // opposed to something from a deserialized core dump. Returns false, + // otherwise. + virtual bool isLive() const { return true; }; + + // Return the coarse-grained type-of-thing that this node represents. + virtual CoarseType coarseType() const { return CoarseType::Other; } + + // Return a human-readable name for the referent's type. The result should + // be statically allocated. (You can use u"strings" for this.) + // + // This must always return Concrete<T>::concreteTypeName; we use that + // pointer as a tag for this particular referent type. + virtual const char16_t* typeName() const = 0; + + // Return the size of this node, in bytes. Include any structures that this + // node owns exclusively that are not exposed as their own ubi::Nodes. + // |mallocSizeOf| should be a malloc block sizing function; see + // |mfbt/MemoryReporting.h|. + // + // Because we can use |JS::ubi::Node|s backed by a snapshot that was taken + // on a 64-bit platform when we are currently on a 32-bit platform, we + // cannot rely on |size_t| for node sizes. Instead, |Size| is uint64_t on + // all platforms. + using Size = uint64_t; + virtual Size size(mozilla::MallocSizeOf mallocSizeof) const { return 1; } + + // Return an EdgeRange that initially contains all the referent's outgoing + // edges. The caller takes ownership of the EdgeRange. + // + // If wantNames is true, compute names for edges. Doing so can be expensive + // in time and memory. + virtual js::UniquePtr<EdgeRange> edges(JSContext* cx, bool wantNames) const = 0; + + // Return the Zone to which this node's referent belongs, or nullptr if the + // referent is not of a type allocated in SpiderMonkey Zones. + virtual JS::Zone* zone() const { return nullptr; } + + // Return the compartment for this node. Some ubi::Node referents are not + // associated with JSCompartments, such as JSStrings (which are associated + // with Zones). When the referent is not associated with a compartment, + // nullptr is returned. + virtual JSCompartment* compartment() const { return nullptr; } + + // Return whether this node's referent's allocation stack was captured. + virtual bool hasAllocationStack() const { return false; } + + // Get the stack recorded at the time this node's referent was + // allocated. This must only be called when hasAllocationStack() is true. + virtual StackFrame allocationStack() const { + MOZ_CRASH("Concrete classes that have an allocation stack must override both " + "hasAllocationStack and allocationStack."); + } + + // Methods for JSObject Referents + // + // These methods are only semantically valid if the referent is either a + // JSObject in the live heap, or represents a previously existing JSObject + // from some deserialized heap snapshot. + + // Return the object's [[Class]]'s name. + virtual const char* jsObjectClassName() const { return nullptr; } + + // If this object was constructed with `new` and we have the data available, + // place the contructor function's display name in the out parameter. + // Otherwise, place nullptr in the out parameter. Caller maintains ownership + // of the out parameter. True is returned on success, false is returned on + // OOM. + virtual MOZ_MUST_USE bool jsObjectConstructorName(JSContext* cx, UniqueTwoByteChars& outName) + const + { + outName.reset(nullptr); + return true; + } + + // Methods for CoarseType::Script referents + + // Return the script's source's filename if available. If unavailable, + // return nullptr. + virtual const char* scriptFilename() const { return nullptr; } + + private: + Base(const Base& rhs) = delete; + Base& operator=(const Base& rhs) = delete; +}; + +// A traits template with a specialization for each referent type that +// ubi::Node supports. The specialization must be the concrete subclass of Base +// that represents a pointer to the referent type. It must include these +// members: +// +// // The specific char16_t array returned by Concrete<T>::typeName(). +// static const char16_t concreteTypeName[]; +// +// // Construct an instance of this concrete class in |storage| referring +// // to |referent|. Implementations typically use a placement 'new'. +// // +// // In some cases, |referent| will contain dynamic type information that +// // identifies it a some more specific subclass of |Referent|. For +// // example, when |Referent| is |JSObject|, then |referent->getClass()| +// // could tell us that it's actually a JSFunction. Similarly, if +// // |Referent| is |nsISupports|, we would like a ubi::Node that knows its +// // final implementation type. +// // +// // So we delegate the actual construction to this specialization, which +// // knows Referent's details. +// static void construct(void* storage, Referent* referent); +template<typename Referent> +class Concrete; + +// A container for a Base instance; all members simply forward to the contained +// instance. This container allows us to pass ubi::Node instances by value. +class Node { + // Storage in which we allocate Base subclasses. + mozilla::AlignedStorage2<Base> storage; + Base* base() { return storage.addr(); } + const Base* base() const { return storage.addr(); } + + template<typename T> + void construct(T* ptr) { + static_assert(sizeof(Concrete<T>) == sizeof(*base()), + "ubi::Base specializations must be the same size as ubi::Base"); + static_assert(mozilla::IsBaseOf<Base, Concrete<T>>::value, + "ubi::Concrete<T> must inherit from ubi::Base"); + Concrete<T>::construct(base(), ptr); + } + struct ConstructFunctor; + + public: + Node() { construct<void>(nullptr); } + + template<typename T> + MOZ_IMPLICIT Node(T* ptr) { + construct(ptr); + } + template<typename T> + Node& operator=(T* ptr) { + construct(ptr); + return *this; + } + + // We can construct and assign from rooted forms of pointers. + template<typename T> + MOZ_IMPLICIT Node(const Rooted<T*>& root) { + construct(root.get()); + } + template<typename T> + Node& operator=(const Rooted<T*>& root) { + construct(root.get()); + return *this; + } + + // Constructors accepting SpiderMonkey's other generic-pointer-ish types. + // Note that we *do* want an implicit constructor here: JS::Value and + // JS::ubi::Node are both essentially tagged references to other sorts of + // objects, so letting conversions happen automatically is appropriate. + MOZ_IMPLICIT Node(JS::HandleValue value); + explicit Node(const JS::GCCellPtr& thing); + + // copy construction and copy assignment just use memcpy, since we know + // instances contain nothing but a vtable pointer and a data pointer. + // + // To be completely correct, concrete classes could provide a virtual + // 'construct' member function, which we could invoke on rhs to construct an + // instance in our storage. But this is good enough; there's no need to jump + // through vtables for copying and assignment that are just going to move + // two words around. The compiler knows how to optimize memcpy. + Node(const Node& rhs) { + memcpy(storage.u.mBytes, rhs.storage.u.mBytes, sizeof(storage.u)); + } + + Node& operator=(const Node& rhs) { + memcpy(storage.u.mBytes, rhs.storage.u.mBytes, sizeof(storage.u)); + return *this; + } + + bool operator==(const Node& rhs) const { return *base() == *rhs.base(); } + bool operator!=(const Node& rhs) const { return *base() != *rhs.base(); } + + explicit operator bool() const { + return base()->ptr != nullptr; + } + + bool isLive() const { return base()->isLive(); } + + // Get the canonical type name for the given type T. + template<typename T> + static const char16_t* canonicalTypeName() { return Concrete<T>::concreteTypeName; } + + template<typename T> + bool is() const { + return base()->typeName() == canonicalTypeName<T>(); + } + + template<typename T> + T* as() const { + MOZ_ASSERT(isLive()); + MOZ_ASSERT(is<T>()); + return static_cast<T*>(base()->ptr); + } + + template<typename T> + T* asOrNull() const { + MOZ_ASSERT(isLive()); + return is<T>() ? static_cast<T*>(base()->ptr) : nullptr; + } + + // If this node refers to something that can be represented as a JavaScript + // value that is safe to expose to JavaScript code, return that value. + // Otherwise return UndefinedValue(). JSStrings, JS::Symbols, and some (but + // not all!) JSObjects can be exposed. + JS::Value exposeToJS() const; + + CoarseType coarseType() const { return base()->coarseType(); } + const char16_t* typeName() const { return base()->typeName(); } + JS::Zone* zone() const { return base()->zone(); } + JSCompartment* compartment() const { return base()->compartment(); } + const char* jsObjectClassName() const { return base()->jsObjectClassName(); } + MOZ_MUST_USE bool jsObjectConstructorName(JSContext* cx, UniqueTwoByteChars& outName) const { + return base()->jsObjectConstructorName(cx, outName); + } + + const char* scriptFilename() const { return base()->scriptFilename(); } + + using Size = Base::Size; + Size size(mozilla::MallocSizeOf mallocSizeof) const { + auto size = base()->size(mallocSizeof); + MOZ_ASSERT(size > 0, + "C++ does not have zero-sized types! Choose 1 if you just need a " + "conservative default."); + return size; + } + + js::UniquePtr<EdgeRange> edges(JSContext* cx, bool wantNames = true) const { + return base()->edges(cx, wantNames); + } + + bool hasAllocationStack() const { return base()->hasAllocationStack(); } + StackFrame allocationStack() const { + return base()->allocationStack(); + } + + using Id = Base::Id; + Id identifier() const { + auto id = base()->identifier(); + MOZ_ASSERT(JS::Value::isNumberRepresentable(id)); + return id; + } + + // A hash policy for ubi::Nodes. + // This simply uses the stock PointerHasher on the ubi::Node's pointer. + // We specialize DefaultHasher below to make this the default. + class HashPolicy { + typedef js::PointerHasher<void*, mozilla::tl::FloorLog2<sizeof(void*)>::value> PtrHash; + + public: + typedef Node Lookup; + + static js::HashNumber hash(const Lookup& l) { return PtrHash::hash(l.base()->ptr); } + static bool match(const Node& k, const Lookup& l) { return k == l; } + static void rekey(Node& k, const Node& newKey) { k = newKey; } + }; +}; + +using NodeSet = js::HashSet<Node, js::DefaultHasher<Node>, js::SystemAllocPolicy>; +using NodeSetPtr = mozilla::UniquePtr<NodeSet, JS::DeletePolicy<NodeSet>>; + +/*** Edge and EdgeRange ***************************************************************************/ + +using EdgeName = UniqueTwoByteChars; + +// An outgoing edge to a referent node. +class Edge { + public: + Edge() : name(nullptr), referent() { } + + // Construct an initialized Edge, taking ownership of |name|. + Edge(char16_t* name, const Node& referent) + : name(name) + , referent(referent) + { } + + // Move construction and assignment. + Edge(Edge&& rhs) + : name(mozilla::Move(rhs.name)) + , referent(rhs.referent) + { } + + Edge& operator=(Edge&& rhs) { + MOZ_ASSERT(&rhs != this); + this->~Edge(); + new (this) Edge(mozilla::Move(rhs)); + return *this; + } + + Edge(const Edge&) = delete; + Edge& operator=(const Edge&) = delete; + + // This edge's name. This may be nullptr, if Node::edges was called with + // false as the wantNames parameter. + // + // The storage is owned by this Edge, and will be freed when this Edge is + // destructed. You may take ownership of the name by `mozilla::Move`ing it + // out of the edge; it is just a UniquePtr. + // + // (In real life we'll want a better representation for names, to avoid + // creating tons of strings when the names follow a pattern; and we'll need + // to think about lifetimes carefully to ensure traversal stays cheap.) + EdgeName name; + + // This edge's referent. + Node referent; +}; + +// EdgeRange is an abstract base class for iterating over a node's outgoing +// edges. (This is modeled after js::HashTable<K,V>::Range.) +// +// Concrete instances of this class need not be as lightweight as Node itself, +// since they're usually only instantiated while iterating over a particular +// object's edges. For example, a dumb implementation for JS Cells might use +// JS::TraceChildren to to get the outgoing edges, and then store them in an +// array internal to the EdgeRange. +class EdgeRange { + protected: + // The current front edge of this range, or nullptr if this range is empty. + Edge* front_; + + EdgeRange() : front_(nullptr) { } + + public: + virtual ~EdgeRange() { } + + // True if there are no more edges in this range. + bool empty() const { return !front_; } + + // The front edge of this range. This is owned by the EdgeRange, and is + // only guaranteed to live until the next call to popFront, or until + // the EdgeRange is destructed. + const Edge& front() const { return *front_; } + Edge& front() { return *front_; } + + // Remove the front edge from this range. This should only be called if + // !empty(). + virtual void popFront() = 0; + + private: + EdgeRange(const EdgeRange&) = delete; + EdgeRange& operator=(const EdgeRange&) = delete; +}; + + +typedef mozilla::Vector<Edge, 8, js::SystemAllocPolicy> EdgeVector; + +// An EdgeRange concrete class that holds a pre-existing vector of +// Edges. A PreComputedEdgeRange does not take ownership of its +// EdgeVector; it is up to the PreComputedEdgeRange's consumer to manage +// that lifetime. +class PreComputedEdgeRange : public EdgeRange { + EdgeVector& edges; + size_t i; + + void settle() { + front_ = i < edges.length() ? &edges[i] : nullptr; + } + + public: + explicit PreComputedEdgeRange(EdgeVector& edges) + : edges(edges), + i(0) + { + settle(); + } + + void popFront() override { + MOZ_ASSERT(!empty()); + i++; + settle(); + } +}; + +/*** RootList *************************************************************************************/ + +// RootList is a class that can be pointed to by a |ubi::Node|, creating a +// fictional root-of-roots which has edges to every GC root in the JS +// runtime. Having a single root |ubi::Node| is useful for algorithms written +// with the assumption that there aren't multiple roots (such as computing +// dominator trees) and you want a single point of entry. It also ensures that +// the roots themselves get visited by |ubi::BreadthFirst| (they would otherwise +// only be used as starting points). +// +// RootList::init itself causes a minor collection, but once the list of roots +// has been created, GC must not occur, as the referent ubi::Nodes are not +// stable across GC. The init calls emplace on |noGC|'s AutoCheckCannotGC, whose +// lifetime must extend at least as long as the RootList itself. +// +// Example usage: +// +// { +// mozilla::Maybe<JS::AutoCheckCannotGC> maybeNoGC; +// JS::ubi::RootList rootList(cx, maybeNoGC); +// if (!rootList.init()) +// return false; +// +// // The AutoCheckCannotGC is guaranteed to exist if init returned true. +// MOZ_ASSERT(maybeNoGC.isSome()); +// +// JS::ubi::Node root(&rootList); +// +// ... +// } +class MOZ_STACK_CLASS JS_PUBLIC_API(RootList) { + Maybe<AutoCheckCannotGC>& noGC; + + public: + JSContext* cx; + EdgeVector edges; + bool wantNames; + + RootList(JSContext* cx, Maybe<AutoCheckCannotGC>& noGC, bool wantNames = false); + + // Find all GC roots. + MOZ_MUST_USE bool init(); + // Find only GC roots in the provided set of |JSCompartment|s. + MOZ_MUST_USE bool init(CompartmentSet& debuggees); + // Find only GC roots in the given Debugger object's set of debuggee + // compartments. + MOZ_MUST_USE bool init(HandleObject debuggees); + + // Returns true if the RootList has been initialized successfully, false + // otherwise. + bool initialized() { return noGC.isSome(); } + + // Explicitly add the given Node as a root in this RootList. If wantNames is + // true, you must pass an edgeName. The RootList does not take ownership of + // edgeName. + MOZ_MUST_USE bool addRoot(Node node, const char16_t* edgeName = nullptr); +}; + + +/*** Concrete classes for ubi::Node referent types ************************************************/ + +template<> +class JS_PUBLIC_API(Concrete<RootList>) : public Base { + protected: + explicit Concrete(RootList* ptr) : Base(ptr) { } + RootList& get() const { return *static_cast<RootList*>(ptr); } + + public: + static void construct(void* storage, RootList* ptr) { new (storage) Concrete(ptr); } + + js::UniquePtr<EdgeRange> edges(JSContext* cx, bool wantNames) const override; + + const char16_t* typeName() const override { return concreteTypeName; } + static const char16_t concreteTypeName[]; +}; + +// A reusable ubi::Concrete specialization base class for types supported by +// JS::TraceChildren. +template<typename Referent> +class JS_PUBLIC_API(TracerConcrete) : public Base { + js::UniquePtr<EdgeRange> edges(JSContext* cx, bool wantNames) const override; + JS::Zone* zone() const override; + + protected: + explicit TracerConcrete(Referent* ptr) : Base(ptr) { } + Referent& get() const { return *static_cast<Referent*>(ptr); } +}; + +// For JS::TraceChildren-based types that have a 'compartment' method. +template<typename Referent> +class JS_PUBLIC_API(TracerConcreteWithCompartment) : public TracerConcrete<Referent> { + typedef TracerConcrete<Referent> TracerBase; + JSCompartment* compartment() const override; + + protected: + explicit TracerConcreteWithCompartment(Referent* ptr) : TracerBase(ptr) { } +}; + +// Define specializations for some commonly-used public JSAPI types. +// These can use the generic templates above. +template<> +class JS_PUBLIC_API(Concrete<JS::Symbol>) : TracerConcrete<JS::Symbol> { + protected: + explicit Concrete(JS::Symbol* ptr) : TracerConcrete(ptr) { } + + public: + static void construct(void* storage, JS::Symbol* ptr) { + new (storage) Concrete(ptr); + } + + Size size(mozilla::MallocSizeOf mallocSizeOf) const override; + + const char16_t* typeName() const override { return concreteTypeName; } + static const char16_t concreteTypeName[]; +}; + +template<> +class JS_PUBLIC_API(Concrete<JSScript>) : TracerConcreteWithCompartment<JSScript> { + protected: + explicit Concrete(JSScript *ptr) : TracerConcreteWithCompartment<JSScript>(ptr) { } + + public: + static void construct(void *storage, JSScript *ptr) { new (storage) Concrete(ptr); } + + CoarseType coarseType() const final { return CoarseType::Script; } + Size size(mozilla::MallocSizeOf mallocSizeOf) const override; + const char* scriptFilename() const final; + + const char16_t* typeName() const override { return concreteTypeName; } + static const char16_t concreteTypeName[]; +}; + +// The JSObject specialization. +template<> +class JS_PUBLIC_API(Concrete<JSObject>) : public TracerConcreteWithCompartment<JSObject> { + protected: + explicit Concrete(JSObject* ptr) : TracerConcreteWithCompartment(ptr) { } + + public: + static void construct(void* storage, JSObject* ptr) { + new (storage) Concrete(ptr); + } + + const char* jsObjectClassName() const override; + MOZ_MUST_USE bool jsObjectConstructorName(JSContext* cx, UniqueTwoByteChars& outName) + const override; + Size size(mozilla::MallocSizeOf mallocSizeOf) const override; + + bool hasAllocationStack() const override; + StackFrame allocationStack() const override; + + CoarseType coarseType() const final { return CoarseType::Object; } + + const char16_t* typeName() const override { return concreteTypeName; } + static const char16_t concreteTypeName[]; +}; + +// For JSString, we extend the generic template with a 'size' implementation. +template<> +class JS_PUBLIC_API(Concrete<JSString>) : TracerConcrete<JSString> { + protected: + explicit Concrete(JSString *ptr) : TracerConcrete<JSString>(ptr) { } + + public: + static void construct(void *storage, JSString *ptr) { new (storage) Concrete(ptr); } + + Size size(mozilla::MallocSizeOf mallocSizeOf) const override; + + CoarseType coarseType() const final { return CoarseType::String; } + + const char16_t* typeName() const override { return concreteTypeName; } + static const char16_t concreteTypeName[]; +}; + +// The ubi::Node null pointer. Any attempt to operate on a null ubi::Node asserts. +template<> +class JS_PUBLIC_API(Concrete<void>) : public Base { + const char16_t* typeName() const override; + Size size(mozilla::MallocSizeOf mallocSizeOf) const override; + js::UniquePtr<EdgeRange> edges(JSContext* cx, bool wantNames) const override; + JS::Zone* zone() const override; + JSCompartment* compartment() const override; + CoarseType coarseType() const final; + + explicit Concrete(void* ptr) : Base(ptr) { } + + public: + static void construct(void* storage, void* ptr) { new (storage) Concrete(ptr); } +}; + + +} // namespace ubi +} // namespace JS + +namespace js { + +// Make ubi::Node::HashPolicy the default hash policy for ubi::Node. +template<> struct DefaultHasher<JS::ubi::Node> : JS::ubi::Node::HashPolicy { }; +template<> struct DefaultHasher<JS::ubi::StackFrame> : JS::ubi::StackFrame::HashPolicy { }; + +} // namespace js + +#endif // js_UbiNode_h |