1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 * vim: set ts=8 sts=4 et sw=4 tw=99:
3 * This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7 #ifndef js_UbiNode_h
8 #define js_UbiNode_h
9
10 #include "mozilla/Alignment.h"
11 #include "mozilla/Assertions.h"
12 #include "mozilla/Attributes.h"
13 #include "mozilla/Maybe.h"
14 #include "mozilla/MemoryReporting.h"
15 #include "mozilla/Move.h"
16 #include "mozilla/RangedPtr.h"
17 #include "mozilla/TypeTraits.h"
18 #include "mozilla/UniquePtr.h"
19 #include "mozilla/Variant.h"
20
21 #include "jspubtd.h"
22
23 #include "js/GCAPI.h"
24 #include "js/HashTable.h"
25 #include "js/RootingAPI.h"
26 #include "js/TracingAPI.h"
27 #include "js/TypeDecls.h"
28 #include "js/Value.h"
29 #include "js/Vector.h"
30
31 // JS::ubi::Node
32 //
33 // JS::ubi::Node is a pointer-like type designed for internal use by heap
34 // analysis tools. A ubi::Node can refer to:
35 //
36 // - a JS value, like a string, object, or symbol;
37 // - an internal SpiderMonkey structure, like a shape or a scope chain object
38 // - an instance of some embedding-provided type: in Firefox, an XPCOM
39 // object, or an internal DOM node class instance
40 //
41 // A ubi::Node instance provides metadata about its referent, and can
42 // enumerate its referent's outgoing edges, so you can implement heap analysis
43 // algorithms that walk the graph - finding paths between objects, or
44 // computing heap dominator trees, say - using ubi::Node, while remaining
45 // ignorant of the details of the types you're operating on.
46 //
47 // Of course, when it comes to presenting the results in a developer-facing
48 // tool, you'll need to stop being ignorant of those details, because you have
49 // to discuss the ubi::Nodes' referents with the developer. Here, ubi::Node
50 // can hand you dynamically checked, properly typed pointers to the original
51 // objects via the as<T> method, or generate descriptions of the referent
52 // itself.
53 //
54 // ubi::Node instances are lightweight (two-word) value types. Instances:
55 // - compare equal if and only if they refer to the same object;
56 // - have hash values that respect their equality relation; and
57 // - have serializations that are only equal if the ubi::Nodes are equal.
58 //
59 // A ubi::Node is only valid for as long as its referent is alive; if its
60 // referent goes away, the ubi::Node becomes a dangling pointer. A ubi::Node
61 // that refers to a GC-managed object is not automatically a GC root; if the
62 // GC frees or relocates its referent, the ubi::Node becomes invalid. A
63 // ubi::Node that refers to a reference-counted object does not bump the
64 // reference count.
65 //
66 // ubi::Node values require no supporting data structures, making them
67 // feasible for use in memory-constrained devices --- ideally, the memory
68 // requirements of the algorithm which uses them will be the limiting factor,
69 // not the demands of ubi::Node itself.
70 //
71 // One can construct a ubi::Node value given a pointer to a type that ubi::Node
72 // supports. In the other direction, one can convert a ubi::Node back to a
73 // pointer; these downcasts are checked dynamically. In particular, one can
74 // convert a 'JSRuntime*' to a ubi::Node, yielding a node with an outgoing edge
75 // for every root registered with the runtime; starting from this, one can walk
76 // the entire heap. (Of course, one could also start traversal at any other kind
77 // of type to which one has a pointer.)
78 //
79 //
80 // Extending ubi::Node To Handle Your Embedding's Types
81 //
82 // To add support for a new ubi::Node referent type R, you must define a
83 // specialization of the ubi::Concrete template, ubi::Concrete<R>, which
84 // inherits from ubi::Base. ubi::Node itself uses the specialization for
85 // compile-time information (i.e. the checked conversions between R * and
86 // ubi::Node), and the inheritance for run-time dispatching.
87 //
88 //
89 // ubi::Node Exposes Implementation Details
90 //
91 // In many cases, a JavaScript developer's view of their data differs
92 // substantially from its actual implementation. For example, while the
93 // ECMAScript specification describes objects as maps from property names to
94 // sets of attributes (like ECMAScript's [[Value]]), in practice many objects
95 // have only a pointer to a shape, shared with other similar objects, and
96 // indexed slots that contain the [[Value]] attributes. As another example, a
97 // string produced by concatenating two other strings may sometimes be
98 // represented by a "rope", a structure that points to the two original
99 // strings.
100 //
101 // We intend to use ubi::Node to write tools that report memory usage, so it's
102 // important that ubi::Node accurately portray how much memory nodes consume.
103 // Thus, for example, when data that apparently belongs to multiple nodes is
104 // in fact shared in a common structure, ubi::Node's graph uses a separate
105 // node for that shared structure, and presents edges to it from the data's
106 // apparent owners. For example, ubi::Node exposes SpiderMonkey objects'
107 // shapes and base shapes, and exposes rope string and substring structure,
108 // because these optimizations become visible when a tool reports how much
109 // memory a structure consumes.
110 //
111 // However, fine granularity is not a goal. When a particular object is the
112 // exclusive owner of a separate block of memory, ubi::Node may present the
113 // object and its block as a single node, and add their sizes together when
114 // reporting the node's size, as there is no meaningful loss of data in this
115 // case. Thus, for example, a ubi::Node referring to a JavaScript object, when
116 // asked for the object's size in bytes, includes the object's slot and
117 // element arrays' sizes in the total. There is no separate ubi::Node value
118 // representing the slot and element arrays, since they are owned exclusively
119 // by the object.
120 //
121 //
122 // Presenting Analysis Results To JavaScript Developers
123 //
124 // If an analysis provides its results in terms of ubi::Node values, a user
125 // interface presenting those results will generally need to clean them up
126 // before they can be understood by JavaScript developers. For example,
127 // JavaScript developers should not need to understand shapes, only JavaScript
128 // objects. Similarly, they should not need to understand the distinction
129 // between DOM nodes and the JavaScript shadow objects that represent them.
130 //
131 //
132 // Rooting Restrictions
133 //
134 // At present there is no way to root ubi::Node instances, so instances can't be
135 // live across any operation that might GC. Analyses using ubi::Node must either
136 // run to completion and convert their results to some other rootable type, or
137 // save their intermediate state in some rooted structure if they must GC before
138 // they complete. (For algorithms like path-finding and dominator tree
139 // computation, we implement the algorithm avoiding any operation that could
140 // cause a GC --- and use AutoCheckCannotGC to verify this.)
141 //
142 // If this restriction prevents us from implementing interesting tools, we may
143 // teach the GC how to root ubi::Nodes, fix up hash tables that use them as
144 // keys, etc.
145 //
146 //
147 // Hostile Graph Structure
148 //
149 // Analyses consuming ubi::Node graphs must be robust when presented with graphs
150 // that are deliberately constructed to exploit their weaknesses. When operating
151 // on live graphs, web content has control over the object graph, and less
152 // direct control over shape and string structure, and analyses should be
153 // prepared to handle extreme cases gracefully. For example, if an analysis were
154 // to use the C++ stack in a depth-first traversal, carefully constructed
155 // content could cause the analysis to overflow the stack.
156 //
157 // When ubi::Nodes refer to nodes deserialized from a heap snapshot, analyses
158 // must be even more careful: since snapshots often come from potentially
159 // compromised e10s content processes, even properties normally guaranteed by
160 // the platform (the proper linking of DOM nodes, for example) might be
161 // corrupted. While it is the deserializer's responsibility to check the basic
162 // structure of the snapshot file, the analyses should be prepared for ubi::Node
163 // graphs constructed from snapshots to be even more bizarre.
164
165 class JSAtom;
166
167 namespace JS {
168 namespace ubi {
169
170 class Edge;
171 class EdgeRange;
172 class StackFrame;
173
174 } // namespace ubi
175 } // namespace JS
176
177 namespace mozilla {
178
179 template<>
180 class DefaultDelete<JS::ubi::EdgeRange> : public JS::DeletePolicy<JS::ubi::EdgeRange> { };
181
182 template<>
183 class DefaultDelete<JS::ubi::StackFrame> : public JS::DeletePolicy<JS::ubi::StackFrame> { };
184
185 } // namespace mozilla
186
187 namespace JS {
188 namespace ubi {
189
190 using mozilla::Forward;
191 using mozilla::Maybe;
192 using mozilla::Move;
193 using mozilla::RangedPtr;
194 using mozilla::UniquePtr;
195 using mozilla::Variant;
196
197 /*** ubi::StackFrame ******************************************************************************/
198
199 // Concrete JS::ubi::StackFrame instances backed by a live SavedFrame object
200 // store their strings as JSAtom*, while deserialized stack frames from offline
201 // heap snapshots store their strings as const char16_t*. In order to provide
202 // zero-cost accessors to these strings in a single interface that works with
203 // both cases, we use this variant type.
204 class AtomOrTwoByteChars : public Variant<JSAtom*, const char16_t*> {
205 using Base = Variant<JSAtom*, const char16_t*>;
206
207 public:
208 template<typename T>
AtomOrTwoByteChars(T && rhs)209 MOZ_IMPLICIT AtomOrTwoByteChars(T&& rhs) : Base(Forward<T>(rhs)) { }
210
211 template<typename T>
212 AtomOrTwoByteChars& operator=(T&& rhs) {
213 MOZ_ASSERT(this != &rhs, "self-move disallowed");
214 this->~AtomOrTwoByteChars();
215 new (this) AtomOrTwoByteChars(Forward<T>(rhs));
216 return *this;
217 }
218
219 // Return the length of the given AtomOrTwoByteChars string.
220 size_t length();
221
222 // Copy the given AtomOrTwoByteChars string into the destination buffer,
223 // inflating if necessary. Does NOT null terminate. Returns the number of
224 // characters written to destination.
225 size_t copyToBuffer(RangedPtr<char16_t> destination, size_t length);
226 };
227
228 // The base class implemented by each ConcreteStackFrame<T> type. Subclasses
229 // must not add data members to this class.
230 class BaseStackFrame {
231 friend class StackFrame;
232
233 BaseStackFrame(const StackFrame&) = delete;
234 BaseStackFrame& operator=(const StackFrame&) = delete;
235
236 protected:
237 void* ptr;
BaseStackFrame(void * ptr)238 explicit BaseStackFrame(void* ptr) : ptr(ptr) { }
239
240 public:
241 // This is a value type that should not have a virtual destructor. Don't add
242 // destructors in subclasses!
243
244 // Get a unique identifier for this StackFrame. The identifier is not valid
245 // across garbage collections.
identifier()246 virtual uint64_t identifier() const { return uint64_t(uintptr_t(ptr)); }
247
248 // Get this frame's parent frame.
249 virtual StackFrame parent() const = 0;
250
251 // Get this frame's line number.
252 virtual uint32_t line() const = 0;
253
254 // Get this frame's column number.
255 virtual uint32_t column() const = 0;
256
257 // Get this frame's source name. Never null.
258 virtual AtomOrTwoByteChars source() const = 0;
259
260 // Return this frame's function name if named, otherwise the inferred
261 // display name. Can be null.
262 virtual AtomOrTwoByteChars functionDisplayName() const = 0;
263
264 // Returns true if this frame's function is system JavaScript running with
265 // trusted principals, false otherwise.
266 virtual bool isSystem() const = 0;
267
268 // Return true if this frame's function is a self-hosted JavaScript builtin,
269 // false otherwise.
270 virtual bool isSelfHosted() const = 0;
271
272 // Construct a SavedFrame stack for the stack starting with this frame and
273 // containing all of its parents. The SavedFrame objects will be placed into
274 // cx's current compartment.
275 //
276 // Note that the process of
277 //
278 // SavedFrame
279 // |
280 // V
281 // JS::ubi::StackFrame
282 // |
283 // V
284 // offline heap snapshot
285 // |
286 // V
287 // JS::ubi::StackFrame
288 // |
289 // V
290 // SavedFrame
291 //
292 // is lossy because we cannot serialize and deserialize the SavedFrame's
293 // principals in the offline heap snapshot, so JS::ubi::StackFrame
294 // simplifies the principals check into the boolean isSystem() state. This
295 // is fine because we only expose JS::ubi::Stack to devtools and chrome
296 // code, and not to the web platform.
297 virtual bool constructSavedFrameStack(JSContext* cx,
298 MutableHandleObject outSavedFrameStack) const = 0;
299
300 // Trace the concrete implementation of JS::ubi::StackFrame.
301 virtual void trace(JSTracer* trc) = 0;
302 };
303
304 // A traits template with a specialization for each backing type that implements
305 // the ubi::BaseStackFrame interface. Each specialization must be the a subclass
306 // of ubi::BaseStackFrame.
307 template<typename T> class ConcreteStackFrame;
308
309 // A JS::ubi::StackFrame represents a frame in a recorded stack. It can be
310 // backed either by a live SavedFrame object or by a structure deserialized from
311 // an offline heap snapshot.
312 //
313 // It is a value type that may be memcpy'd hither and thither without worrying
314 // about constructors or destructors, similar to POD types.
315 //
316 // Its lifetime is the same as the lifetime of the graph that is being analyzed
317 // by the JS::ubi::Node that the JS::ubi::StackFrame came from. That is, if the
318 // graph being analyzed is the live heap graph, the JS::ubi::StackFrame is only
319 // valid within the scope of an AutoCheckCannotGC; if the graph being analyzed
320 // is an offline heap snapshot, the JS::ubi::StackFrame is valid as long as the
321 // offline heap snapshot is alive.
322 class StackFrame : public JS::Traceable {
323 // Storage in which we allocate BaseStackFrame subclasses.
324 mozilla::AlignedStorage2<BaseStackFrame> storage;
325
base()326 BaseStackFrame* base() { return storage.addr(); }
base()327 const BaseStackFrame* base() const { return storage.addr(); }
328
329 template<typename T>
construct(T * ptr)330 void construct(T* ptr) {
331 static_assert(mozilla::IsBaseOf<BaseStackFrame, ConcreteStackFrame<T>>::value,
332 "ConcreteStackFrame<T> must inherit from BaseStackFrame");
333 static_assert(sizeof(ConcreteStackFrame<T>) == sizeof(*base()),
334 "ubi::ConcreteStackFrame<T> specializations must be the same size as "
335 "ubi::BaseStackFrame");
336 ConcreteStackFrame<T>::construct(base(), ptr);
337 }
338 struct ConstructFunctor;
339
340 public:
StackFrame()341 StackFrame() { construct<void>(nullptr); }
342
343 template<typename T>
StackFrame(T * ptr)344 MOZ_IMPLICIT StackFrame(T* ptr) {
345 construct(ptr);
346 }
347
348 template<typename T>
349 StackFrame& operator=(T* ptr) {
350 construct(ptr);
351 return *this;
352 }
353
354 // Constructors accepting SpiderMonkey's generic-pointer-ish types.
355
356 template<typename T>
StackFrame(const JS::Handle<T * > & handle)357 explicit StackFrame(const JS::Handle<T*>& handle) {
358 construct(handle.get());
359 }
360
361 template<typename T>
362 StackFrame& operator=(const JS::Handle<T*>& handle) {
363 construct(handle.get());
364 return *this;
365 }
366
367 template<typename T>
StackFrame(const JS::Rooted<T * > & root)368 explicit StackFrame(const JS::Rooted<T*>& root) {
369 construct(root.get());
370 }
371
372 template<typename T>
373 StackFrame& operator=(const JS::Rooted<T*>& root) {
374 construct(root.get());
375 return *this;
376 }
377
378 // Because StackFrame is just a vtable pointer and an instance pointer, we
379 // can memcpy everything around instead of making concrete classes define
380 // virtual constructors. See the comment above Node's copy constructor for
381 // more details; that comment applies here as well.
StackFrame(const StackFrame & rhs)382 StackFrame(const StackFrame& rhs) {
383 memcpy(storage.u.mBytes, rhs.storage.u.mBytes, sizeof(storage.u));
384 }
385
386 StackFrame& operator=(const StackFrame& rhs) {
387 memcpy(storage.u.mBytes, rhs.storage.u.mBytes, sizeof(storage.u));
388 return *this;
389 }
390
391 bool operator==(const StackFrame& rhs) const { return base()->ptr == rhs.base()->ptr; }
392 bool operator!=(const StackFrame& rhs) const { return !(*this == rhs); }
393
394 explicit operator bool() const {
395 return base()->ptr != nullptr;
396 }
397
398 // Copy this StackFrame's source name into the given |destination|
399 // buffer. Copy no more than |length| characters. The result is *not* null
400 // terminated. Returns how many characters were written into the buffer.
401 size_t source(RangedPtr<char16_t> destination, size_t length) const;
402
403 // Copy this StackFrame's function display name into the given |destination|
404 // buffer. Copy no more than |length| characters. The result is *not* null
405 // terminated. Returns how many characters were written into the buffer.
406 size_t functionDisplayName(RangedPtr<char16_t> destination, size_t length) const;
407
408 // Get the size of the respective strings. 0 is returned for null strings.
409 size_t sourceLength();
410 size_t functionDisplayNameLength();
411
412 // JS::Traceable implementation just forwards to our virtual trace method.
trace(StackFrame * frame,JSTracer * trc)413 static void trace(StackFrame* frame, JSTracer* trc) {
414 if (frame)
415 frame->trace(trc);
416 }
417
418 // Methods that forward to virtual calls through BaseStackFrame.
419
trace(JSTracer * trc)420 void trace(JSTracer* trc) { base()->trace(trc); }
identifier()421 uint64_t identifier() const {
422 auto id = base()->identifier();
423 MOZ_ASSERT(JS::Value::isNumberRepresentable(id));
424 return id;
425 }
line()426 uint32_t line() const { return base()->line(); }
column()427 uint32_t column() const { return base()->column(); }
source()428 AtomOrTwoByteChars source() const { return base()->source(); }
functionDisplayName()429 AtomOrTwoByteChars functionDisplayName() const { return base()->functionDisplayName(); }
parent()430 StackFrame parent() const { return base()->parent(); }
isSystem()431 bool isSystem() const { return base()->isSystem(); }
isSelfHosted()432 bool isSelfHosted() const { return base()->isSelfHosted(); }
constructSavedFrameStack(JSContext * cx,MutableHandleObject outSavedFrameStack)433 bool constructSavedFrameStack(JSContext* cx,
434 MutableHandleObject outSavedFrameStack) const {
435 return base()->constructSavedFrameStack(cx, outSavedFrameStack);
436 }
437
438 struct HashPolicy {
439 using Lookup = JS::ubi::StackFrame;
440
hashHashPolicy441 static js::HashNumber hash(const Lookup& lookup) {
442 return lookup.identifier();
443 }
444
matchHashPolicy445 static bool match(const StackFrame& key, const Lookup& lookup) {
446 return key == lookup;
447 }
448
rekeyHashPolicy449 static void rekey(StackFrame& k, const StackFrame& newKey) {
450 k = newKey;
451 }
452 };
453 };
454
455 // The ubi::StackFrame null pointer. Any attempt to operate on a null
456 // ubi::StackFrame crashes.
457 template<>
458 class ConcreteStackFrame<void> : public BaseStackFrame {
ConcreteStackFrame(void * ptr)459 explicit ConcreteStackFrame(void* ptr) : BaseStackFrame(ptr) { }
460
461 public:
construct(void * storage,void *)462 static void construct(void* storage, void*) { new (storage) ConcreteStackFrame(nullptr); }
463
identifier()464 uint64_t identifier() const override { return 0; }
trace(JSTracer * trc)465 void trace(JSTracer* trc) override { }
constructSavedFrameStack(JSContext * cx,MutableHandleObject out)466 bool constructSavedFrameStack(JSContext* cx, MutableHandleObject out) const override {
467 out.set(nullptr);
468 return true;
469 }
470
line()471 uint32_t line() const override { MOZ_CRASH("null JS::ubi::StackFrame"); }
column()472 uint32_t column() const override { MOZ_CRASH("null JS::ubi::StackFrame"); }
source()473 AtomOrTwoByteChars source() const override { MOZ_CRASH("null JS::ubi::StackFrame"); }
functionDisplayName()474 AtomOrTwoByteChars functionDisplayName() const override { MOZ_CRASH("null JS::ubi::StackFrame"); }
parent()475 StackFrame parent() const override { MOZ_CRASH("null JS::ubi::StackFrame"); }
isSystem()476 bool isSystem() const override { MOZ_CRASH("null JS::ubi::StackFrame"); }
isSelfHosted()477 bool isSelfHosted() const override { MOZ_CRASH("null JS::ubi::StackFrame"); }
478 };
479
480 bool ConstructSavedFrameStackSlow(JSContext* cx, JS::ubi::StackFrame& frame,
481 MutableHandleObject outSavedFrameStack);
482
483
484 /*** ubi::Node ************************************************************************************/
485
486 // A concrete node specialization can claim its referent is a member of a
487 // particular "coarse type" which is less specific than the actual
488 // implementation type but generally more palatable for web developers. For
489 // example, JitCode can be considered to have a coarse type of "Script". This is
490 // used by some analyses for putting nodes into different buckets. The default,
491 // if a concrete specialization does not provide its own mapping to a CoarseType
492 // variant, is "Other".
493 //
494 // NB: the values associated with a particular enum variant must not change or
495 // be reused for new variants. Doing so will cause inspecting ubi::Nodes backed
496 // by an offline heap snapshot from an older SpiderMonkey/Firefox version to
497 // break. Consider this enum append only.
498 enum class CoarseType: uint32_t {
499 Other = 0,
500 Object = 1,
501 Script = 2,
502 String = 3,
503
504 FIRST = Other,
505 LAST = String
506 };
507
508 inline uint32_t
CoarseTypeToUint32(CoarseType type)509 CoarseTypeToUint32(CoarseType type)
510 {
511 return static_cast<uint32_t>(type);
512 }
513
514 inline bool
Uint32IsValidCoarseType(uint32_t n)515 Uint32IsValidCoarseType(uint32_t n)
516 {
517 auto first = static_cast<uint32_t>(CoarseType::FIRST);
518 auto last = static_cast<uint32_t>(CoarseType::LAST);
519 MOZ_ASSERT(first < last);
520 return first <= n && n <= last;
521 }
522
523 inline CoarseType
Uint32ToCoarseType(uint32_t n)524 Uint32ToCoarseType(uint32_t n)
525 {
526 MOZ_ASSERT(Uint32IsValidCoarseType(n));
527 return static_cast<CoarseType>(n);
528 }
529
530 // The base class implemented by each ubi::Node referent type. Subclasses must
531 // not add data members to this class.
532 class Base {
533 friend class Node;
534
535 // For performance's sake, we'd prefer to avoid a virtual destructor; and
536 // an empty constructor seems consistent with the 'lightweight value type'
537 // visible behavior we're trying to achieve. But if the destructor isn't
538 // virtual, and a subclass overrides it, the subclass's destructor will be
539 // ignored. Is there a way to make the compiler catch that error?
540
541 protected:
542 // Space for the actual pointer. Concrete subclasses should define a
543 // properly typed 'get' member function to access this.
544 void* ptr;
545
Base(void * ptr)546 explicit Base(void* ptr) : ptr(ptr) { }
547
548 public:
549 bool operator==(const Base& rhs) const {
550 // Some compilers will indeed place objects of different types at
551 // the same address, so technically, we should include the vtable
552 // in this comparison. But it seems unlikely to cause problems in
553 // practice.
554 return ptr == rhs.ptr;
555 }
556 bool operator!=(const Base& rhs) const { return !(*this == rhs); }
557
558 // An identifier for this node, guaranteed to be stable and unique for as
559 // long as this ubi::Node's referent is alive and at the same address.
560 //
561 // This is probably suitable for use in serializations, as it is an integral
562 // type. It may also help save memory when constructing HashSets of
563 // ubi::Nodes: since a uint64_t will always be smaller-or-equal-to the size
564 // of a ubi::Node, a HashSet<ubi::Node::Id> may use less space per element
565 // than a HashSet<ubi::Node>.
566 //
567 // (Note that 'unique' only means 'up to equality on ubi::Node'; see the
568 // caveats about multiple objects allocated at the same address for
569 // 'ubi::Node::operator=='.)
570 using Id = uint64_t;
identifier()571 virtual Id identifier() const { return Id(uintptr_t(ptr)); }
572
573 // Returns true if this node is pointing to something on the live heap, as
574 // opposed to something from a deserialized core dump. Returns false,
575 // otherwise.
isLive()576 virtual bool isLive() const { return true; };
577
578 // Return the coarse-grained type-of-thing that this node represents.
coarseType()579 virtual CoarseType coarseType() const { return CoarseType::Other; }
580
581 // Return a human-readable name for the referent's type. The result should
582 // be statically allocated. (You can use MOZ_UTF16("strings") for this.)
583 //
584 // This must always return Concrete<T>::concreteTypeName; we use that
585 // pointer as a tag for this particular referent type.
586 virtual const char16_t* typeName() const = 0;
587
588 // Return the size of this node, in bytes. Include any structures that this
589 // node owns exclusively that are not exposed as their own ubi::Nodes.
590 // |mallocSizeOf| should be a malloc block sizing function; see
591 // |mfbt/MemoryReporting.h|.
592 using Size = uint64_t;
size(mozilla::MallocSizeOf mallocSizeof)593 virtual Size size(mozilla::MallocSizeOf mallocSizeof) const { return 1; }
594
595 // Return an EdgeRange that initially contains all the referent's outgoing
596 // edges. The caller takes ownership of the EdgeRange.
597 //
598 // If wantNames is true, compute names for edges. Doing so can be expensive
599 // in time and memory.
600 virtual UniquePtr<EdgeRange> edges(JSRuntime* rt, bool wantNames) const = 0;
601
602 // Return the Zone to which this node's referent belongs, or nullptr if the
603 // referent is not of a type allocated in SpiderMonkey Zones.
zone()604 virtual JS::Zone* zone() const { return nullptr; }
605
606 // Return the compartment for this node. Some ubi::Node referents are not
607 // associated with JSCompartments, such as JSStrings (which are associated
608 // with Zones). When the referent is not associated with a compartment,
609 // nullptr is returned.
compartment()610 virtual JSCompartment* compartment() const { return nullptr; }
611
612 // Return whether this node's referent's allocation stack was captured.
hasAllocationStack()613 virtual bool hasAllocationStack() const { return false; }
614
615 // Get the stack recorded at the time this node's referent was
616 // allocated. This must only be called when hasAllocationStack() is true.
allocationStack()617 virtual StackFrame allocationStack() const {
618 MOZ_CRASH("Concrete classes that have an allocation stack must override both "
619 "hasAllocationStack and allocationStack.");
620 }
621
622 // Methods for JSObject Referents
623 //
624 // These methods are only semantically valid if the referent is either a
625 // JSObject in the live heap, or represents a previously existing JSObject
626 // from some deserialized heap snapshot.
627
628 // Return the object's [[Class]]'s name.
jsObjectClassName()629 virtual const char* jsObjectClassName() const { return nullptr; }
630
631 // If this object was constructed with `new` and we have the data available,
632 // place the contructor function's display name in the out parameter.
633 // Otherwise, place nullptr in the out parameter. Caller maintains ownership
634 // of the out parameter. True is returned on success, false is returned on
635 // OOM.
jsObjectConstructorName(JSContext * cx,UniquePtr<char16_t[],JS::FreePolicy> & outName)636 virtual bool jsObjectConstructorName(JSContext* cx,
637 UniquePtr<char16_t[], JS::FreePolicy>& outName) const {
638 outName.reset(nullptr);
639 return true;
640 }
641
642 // Methods for CoarseType::Script referents
643
644 // Return the script's source's filename if available. If unavailable,
645 // return nullptr.
scriptFilename()646 virtual const char* scriptFilename() const { return nullptr; }
647
648 private:
649 Base(const Base& rhs) = delete;
650 Base& operator=(const Base& rhs) = delete;
651 };
652
653 // A traits template with a specialization for each referent type that
654 // ubi::Node supports. The specialization must be the concrete subclass of
655 // Base that represents a pointer to the referent type. It must also
656 // include the members described here.
657 template<typename Referent>
658 struct Concrete {
659 // The specific char16_t array returned by Concrete<T>::typeName.
660 static const char16_t concreteTypeName[];
661
662 // Construct an instance of this concrete class in |storage| referring
663 // to |referent|. Implementations typically use a placement 'new'.
664 //
665 // In some cases, |referent| will contain dynamic type information that
666 // identifies it a some more specific subclass of |Referent|. For example,
667 // when |Referent| is |JSObject|, then |referent->getClass()| could tell us
668 // that it's actually a JSFunction. Similarly, if |Referent| is
669 // |nsISupports|, we would like a ubi::Node that knows its final
670 // implementation type.
671 //
672 // So, we delegate the actual construction to this specialization, which
673 // knows Referent's details.
674 static void construct(void* storage, Referent* referent);
675 };
676
677 // A container for a Base instance; all members simply forward to the contained
678 // instance. This container allows us to pass ubi::Node instances by value.
679 class Node {
680 // Storage in which we allocate Base subclasses.
681 mozilla::AlignedStorage2<Base> storage;
base()682 Base* base() { return storage.addr(); }
base()683 const Base* base() const { return storage.addr(); }
684
685 template<typename T>
construct(T * ptr)686 void construct(T* ptr) {
687 static_assert(sizeof(Concrete<T>) == sizeof(*base()),
688 "ubi::Base specializations must be the same size as ubi::Base");
689 Concrete<T>::construct(base(), ptr);
690 }
691 struct ConstructFunctor;
692
693 public:
Node()694 Node() { construct<void>(nullptr); }
695
696 template<typename T>
Node(T * ptr)697 MOZ_IMPLICIT Node(T* ptr) {
698 construct(ptr);
699 }
700 template<typename T>
701 Node& operator=(T* ptr) {
702 construct(ptr);
703 return *this;
704 }
705
706 // We can construct and assign from rooted forms of pointers.
707 template<typename T>
Node(const Rooted<T * > & root)708 MOZ_IMPLICIT Node(const Rooted<T*>& root) {
709 construct(root.get());
710 }
711 template<typename T>
712 Node& operator=(const Rooted<T*>& root) {
713 construct(root.get());
714 return *this;
715 }
716
717 // Constructors accepting SpiderMonkey's other generic-pointer-ish types.
718 // Note that we *do* want an implicit constructor here: JS::Value and
719 // JS::ubi::Node are both essentially tagged references to other sorts of
720 // objects, so letting conversions happen automatically is appropriate.
721 MOZ_IMPLICIT Node(JS::HandleValue value);
722 explicit Node(const JS::GCCellPtr& thing);
723
724 // copy construction and copy assignment just use memcpy, since we know
725 // instances contain nothing but a vtable pointer and a data pointer.
726 //
727 // To be completely correct, concrete classes could provide a virtual
728 // 'construct' member function, which we could invoke on rhs to construct an
729 // instance in our storage. But this is good enough; there's no need to jump
730 // through vtables for copying and assignment that are just going to move
731 // two words around. The compiler knows how to optimize memcpy.
Node(const Node & rhs)732 Node(const Node& rhs) {
733 memcpy(storage.u.mBytes, rhs.storage.u.mBytes, sizeof(storage.u));
734 }
735
736 Node& operator=(const Node& rhs) {
737 memcpy(storage.u.mBytes, rhs.storage.u.mBytes, sizeof(storage.u));
738 return *this;
739 }
740
741 bool operator==(const Node& rhs) const { return *base() == *rhs.base(); }
742 bool operator!=(const Node& rhs) const { return *base() != *rhs.base(); }
743
744 explicit operator bool() const {
745 return base()->ptr != nullptr;
746 }
747
isLive()748 bool isLive() const { return base()->isLive(); }
749
750 // Get the canonical type name for the given type T.
751 template<typename T>
canonicalTypeName()752 static const char16_t* canonicalTypeName() { return Concrete<T>::concreteTypeName; }
753
754 template<typename T>
is()755 bool is() const {
756 return base()->typeName() == canonicalTypeName<T>();
757 }
758
759 template<typename T>
as()760 T* as() const {
761 MOZ_ASSERT(isLive());
762 MOZ_ASSERT(is<T>());
763 return static_cast<T*>(base()->ptr);
764 }
765
766 template<typename T>
asOrNull()767 T* asOrNull() const {
768 MOZ_ASSERT(isLive());
769 return is<T>() ? static_cast<T*>(base()->ptr) : nullptr;
770 }
771
772 // If this node refers to something that can be represented as a JavaScript
773 // value that is safe to expose to JavaScript code, return that value.
774 // Otherwise return UndefinedValue(). JSStrings, JS::Symbols, and some (but
775 // not all!) JSObjects can be exposed.
776 JS::Value exposeToJS() const;
777
coarseType()778 CoarseType coarseType() const { return base()->coarseType(); }
typeName()779 const char16_t* typeName() const { return base()->typeName(); }
zone()780 JS::Zone* zone() const { return base()->zone(); }
compartment()781 JSCompartment* compartment() const { return base()->compartment(); }
jsObjectClassName()782 const char* jsObjectClassName() const { return base()->jsObjectClassName(); }
jsObjectConstructorName(JSContext * cx,UniquePtr<char16_t[],JS::FreePolicy> & outName)783 bool jsObjectConstructorName(JSContext* cx,
784 UniquePtr<char16_t[], JS::FreePolicy>& outName) const {
785 return base()->jsObjectConstructorName(cx, outName);
786 }
787
scriptFilename()788 const char* scriptFilename() const { return base()->scriptFilename(); }
789
790 using Size = Base::Size;
size(mozilla::MallocSizeOf mallocSizeof)791 Size size(mozilla::MallocSizeOf mallocSizeof) const {
792 auto size = base()->size(mallocSizeof);
793 MOZ_ASSERT(size > 0,
794 "C++ does not have zero-sized types! Choose 1 if you just need a "
795 "conservative default.");
796 return size;
797 }
798
799 UniquePtr<EdgeRange> edges(JSRuntime* rt, bool wantNames = true) const {
800 return base()->edges(rt, wantNames);
801 }
802
hasAllocationStack()803 bool hasAllocationStack() const { return base()->hasAllocationStack(); }
allocationStack()804 StackFrame allocationStack() const {
805 return base()->allocationStack();
806 }
807
808 using Id = Base::Id;
identifier()809 Id identifier() const {
810 auto id = base()->identifier();
811 MOZ_ASSERT(JS::Value::isNumberRepresentable(id));
812 return id;
813 }
814
815 // A hash policy for ubi::Nodes.
816 // This simply uses the stock PointerHasher on the ubi::Node's pointer.
817 // We specialize DefaultHasher below to make this the default.
818 class HashPolicy {
819 typedef js::PointerHasher<void*, mozilla::tl::FloorLog2<sizeof(void*)>::value> PtrHash;
820
821 public:
822 typedef Node Lookup;
823
hash(const Lookup & l)824 static js::HashNumber hash(const Lookup& l) { return PtrHash::hash(l.base()->ptr); }
match(const Node & k,const Lookup & l)825 static bool match(const Node& k, const Lookup& l) { return k == l; }
rekey(Node & k,const Node & newKey)826 static void rekey(Node& k, const Node& newKey) { k = newKey; }
827 };
828 };
829
830
831 /*** Edge and EdgeRange ***************************************************************************/
832
833 using EdgeName = UniquePtr<const char16_t[], JS::FreePolicy>;
834
835 // An outgoing edge to a referent node.
836 class Edge {
837 public:
Edge()838 Edge() : name(nullptr), referent() { }
839
840 // Construct an initialized Edge, taking ownership of |name|.
Edge(char16_t * name,const Node & referent)841 Edge(char16_t* name, const Node& referent)
842 : name(name)
843 , referent(referent)
844 { }
845
846 // Move construction and assignment.
Edge(Edge && rhs)847 Edge(Edge&& rhs)
848 : name(mozilla::Move(rhs.name))
849 , referent(rhs.referent)
850 { }
851
852 Edge& operator=(Edge&& rhs) {
853 MOZ_ASSERT(&rhs != this);
854 this->~Edge();
855 new (this) Edge(mozilla::Move(rhs));
856 return *this;
857 }
858
859 Edge(const Edge&) = delete;
860 Edge& operator=(const Edge&) = delete;
861
862 // This edge's name. This may be nullptr, if Node::edges was called with
863 // false as the wantNames parameter.
864 //
865 // The storage is owned by this Edge, and will be freed when this Edge is
866 // destructed.
867 //
868 // (In real life we'll want a better representation for names, to avoid
869 // creating tons of strings when the names follow a pattern; and we'll need
870 // to think about lifetimes carefully to ensure traversal stays cheap.)
871 EdgeName name;
872
873 // This edge's referent.
874 Node referent;
875 };
876
877 // EdgeRange is an abstract base class for iterating over a node's outgoing
878 // edges. (This is modeled after js::HashTable<K,V>::Range.)
879 //
880 // Concrete instances of this class need not be as lightweight as Node itself,
881 // since they're usually only instantiated while iterating over a particular
882 // object's edges. For example, a dumb implementation for JS Cells might use
883 // JS::TraceChildren to to get the outgoing edges, and then store them in an
884 // array internal to the EdgeRange.
885 class EdgeRange {
886 protected:
887 // The current front edge of this range, or nullptr if this range is empty.
888 Edge* front_;
889
EdgeRange()890 EdgeRange() : front_(nullptr) { }
891
892 public:
~EdgeRange()893 virtual ~EdgeRange() { }
894
895 // True if there are no more edges in this range.
empty()896 bool empty() const { return !front_; }
897
898 // The front edge of this range. This is owned by the EdgeRange, and is
899 // only guaranteed to live until the next call to popFront, or until
900 // the EdgeRange is destructed.
front()901 const Edge& front() const { return *front_; }
front()902 Edge& front() { return *front_; }
903
904 // Remove the front edge from this range. This should only be called if
905 // !empty().
906 virtual void popFront() = 0;
907
908 private:
909 EdgeRange(const EdgeRange&) = delete;
910 EdgeRange& operator=(const EdgeRange&) = delete;
911 };
912
913
914 typedef mozilla::Vector<Edge, 8, js::SystemAllocPolicy> EdgeVector;
915
916 // An EdgeRange concrete class that holds a pre-existing vector of
917 // Edges. A PreComputedEdgeRange does not take ownership of its
918 // EdgeVector; it is up to the PreComputedEdgeRange's consumer to manage
919 // that lifetime.
920 class PreComputedEdgeRange : public EdgeRange {
921 EdgeVector& edges;
922 size_t i;
923
settle()924 void settle() {
925 front_ = i < edges.length() ? &edges[i] : nullptr;
926 }
927
928 public:
PreComputedEdgeRange(EdgeVector & edges)929 explicit PreComputedEdgeRange(EdgeVector& edges)
930 : edges(edges),
931 i(0)
932 {
933 settle();
934 }
935
popFront()936 void popFront() override {
937 MOZ_ASSERT(!empty());
938 i++;
939 settle();
940 }
941 };
942
943 /*** RootList *************************************************************************************/
944
945 // RootList is a class that can be pointed to by a |ubi::Node|, creating a
946 // fictional root-of-roots which has edges to every GC root in the JS
947 // runtime. Having a single root |ubi::Node| is useful for algorithms written
948 // with the assumption that there aren't multiple roots (such as computing
949 // dominator trees) and you want a single point of entry. It also ensures that
950 // the roots themselves get visited by |ubi::BreadthFirst| (they would otherwise
951 // only be used as starting points).
952 //
953 // RootList::init itself causes a minor collection, but once the list of roots
954 // has been created, GC must not occur, as the referent ubi::Nodes are not
955 // stable across GC. The init calls emplace on |noGC|'s AutoCheckCannotGC, whose
956 // lifetime must extend at least as long as the RootList itself.
957 //
958 // Example usage:
959 //
960 // {
961 // mozilla::Maybe<JS::AutoCheckCannotGC> maybeNoGC;
962 // JS::ubi::RootList rootList(rt, maybeNoGC);
963 // if (!rootList.init())
964 // return false;
965 //
966 // // The AutoCheckCannotGC is guaranteed to exist if init returned true.
967 // MOZ_ASSERT(maybeNoGC.isSome());
968 //
969 // JS::ubi::Node root(&rootList);
970 //
971 // ...
972 // }
973 class MOZ_STACK_CLASS RootList {
974 Maybe<AutoCheckCannotGC>& noGC;
975
976 public:
977 JSRuntime* rt;
978 EdgeVector edges;
979 bool wantNames;
980
981 RootList(JSRuntime* rt, Maybe<AutoCheckCannotGC>& noGC, bool wantNames = false);
982
983 // Find all GC roots.
984 bool init();
985 // Find only GC roots in the provided set of |Zone|s.
986 bool init(ZoneSet& debuggees);
987 // Find only GC roots in the given Debugger object's set of debuggee zones.
988 bool init(HandleObject debuggees);
989
990 // Returns true if the RootList has been initialized successfully, false
991 // otherwise.
initialized()992 bool initialized() { return noGC.isSome(); }
993
994 // Explicitly add the given Node as a root in this RootList. If wantNames is
995 // true, you must pass an edgeName. The RootList does not take ownership of
996 // edgeName.
997 bool addRoot(Node node, const char16_t* edgeName = nullptr);
998 };
999
1000
1001 /*** Concrete classes for ubi::Node referent types ************************************************/
1002
1003 template<>
1004 struct Concrete<RootList> : public Base {
1005 UniquePtr<EdgeRange> edges(JSRuntime* rt, bool wantNames) const override;
1006 const char16_t* typeName() const override { return concreteTypeName; }
1007
1008 protected:
1009 explicit Concrete(RootList* ptr) : Base(ptr) { }
1010 RootList& get() const { return *static_cast<RootList*>(ptr); }
1011
1012 public:
1013 static const char16_t concreteTypeName[];
1014 static void construct(void* storage, RootList* ptr) { new (storage) Concrete(ptr); }
1015 };
1016
1017 // A reusable ubi::Concrete specialization base class for types supported by
1018 // JS::TraceChildren.
1019 template<typename Referent>
1020 class TracerConcrete : public Base {
1021 const char16_t* typeName() const override { return concreteTypeName; }
1022 UniquePtr<EdgeRange> edges(JSRuntime* rt, bool wantNames) const override;
1023 JS::Zone* zone() const override;
1024
1025 protected:
1026 explicit TracerConcrete(Referent* ptr) : Base(ptr) { }
1027 Referent& get() const { return *static_cast<Referent*>(ptr); }
1028
1029 public:
1030 static const char16_t concreteTypeName[];
1031 static void construct(void* storage, Referent* ptr) { new (storage) TracerConcrete(ptr); }
1032 };
1033
1034 // For JS::TraceChildren-based types that have a 'compartment' method.
1035 template<typename Referent>
1036 class TracerConcreteWithCompartment : public TracerConcrete<Referent> {
1037 typedef TracerConcrete<Referent> TracerBase;
1038 JSCompartment* compartment() const override;
1039
1040 protected:
1041 explicit TracerConcreteWithCompartment(Referent* ptr) : TracerBase(ptr) { }
1042
1043 public:
1044 static void construct(void* storage, Referent* ptr) {
1045 new (storage) TracerConcreteWithCompartment(ptr);
1046 }
1047 };
1048
1049 // Define specializations for some commonly-used public JSAPI types.
1050 // These can use the generic templates above.
1051 template<>
1052 struct Concrete<JS::Symbol> : TracerConcrete<JS::Symbol> {
1053 Size size(mozilla::MallocSizeOf mallocSizeOf) const override;
1054
1055 protected:
1056 explicit Concrete(JS::Symbol* ptr) : TracerConcrete(ptr) { }
1057
1058 public:
1059 static void construct(void* storage, JS::Symbol* ptr) {
1060 new (storage) Concrete(ptr);
1061 }
1062 };
1063
1064 template<> struct Concrete<JSScript> : TracerConcreteWithCompartment<JSScript> {
1065 CoarseType coarseType() const final { return CoarseType::Script; }
1066 Size size(mozilla::MallocSizeOf mallocSizeOf) const override;
1067 const char* scriptFilename() const final;
1068
1069 protected:
1070 explicit Concrete(JSScript *ptr) : TracerConcreteWithCompartment<JSScript>(ptr) { }
1071
1072 public:
1073 static void construct(void *storage, JSScript *ptr) { new (storage) Concrete(ptr); }
1074 };
1075
1076 // The JSObject specialization.
1077 template<>
1078 class Concrete<JSObject> : public TracerConcreteWithCompartment<JSObject> {
1079 const char* jsObjectClassName() const override;
1080 bool jsObjectConstructorName(JSContext* cx,
1081 UniquePtr<char16_t[], JS::FreePolicy>& outName) const override;
1082 Size size(mozilla::MallocSizeOf mallocSizeOf) const override;
1083
1084 bool hasAllocationStack() const override;
1085 StackFrame allocationStack() const override;
1086
1087 CoarseType coarseType() const final { return CoarseType::Object; }
1088
1089 protected:
1090 explicit Concrete(JSObject* ptr) : TracerConcreteWithCompartment(ptr) { }
1091
1092 public:
1093 static void construct(void* storage, JSObject* ptr) {
1094 new (storage) Concrete(ptr);
1095 }
1096 };
1097
1098 // For JSString, we extend the generic template with a 'size' implementation.
1099 template<> struct Concrete<JSString> : TracerConcrete<JSString> {
1100 Size size(mozilla::MallocSizeOf mallocSizeOf) const override;
1101
1102 CoarseType coarseType() const final { return CoarseType::String; }
1103
1104 protected:
1105 explicit Concrete(JSString *ptr) : TracerConcrete<JSString>(ptr) { }
1106
1107 public:
1108 static void construct(void *storage, JSString *ptr) { new (storage) Concrete(ptr); }
1109 };
1110
1111 // The ubi::Node null pointer. Any attempt to operate on a null ubi::Node asserts.
1112 template<>
1113 class Concrete<void> : public Base {
1114 const char16_t* typeName() const override;
1115 Size size(mozilla::MallocSizeOf mallocSizeOf) const override;
1116 UniquePtr<EdgeRange> edges(JSRuntime* rt, bool wantNames) const override;
1117 JS::Zone* zone() const override;
1118 JSCompartment* compartment() const override;
1119 CoarseType coarseType() const final;
1120
1121 explicit Concrete(void* ptr) : Base(ptr) { }
1122
1123 public:
1124 static void construct(void* storage, void* ptr) { new (storage) Concrete(ptr); }
1125 static const char16_t concreteTypeName[];
1126 };
1127
1128
1129 } // namespace ubi
1130 } // namespace JS
1131
1132 namespace js {
1133
1134 // Make ubi::Node::HashPolicy the default hash policy for ubi::Node.
1135 template<> struct DefaultHasher<JS::ubi::Node> : JS::ubi::Node::HashPolicy { };
1136 template<> struct DefaultHasher<JS::ubi::StackFrame> : JS::ubi::StackFrame::HashPolicy { };
1137
1138 } // namespace js
1139
1140 #endif // js_UbiNode_h
1141