1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2 * vim: set ts=8 sts=2 et sw=2 tw=80:
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/. */
7 #ifndef js_UbiNodeShortestPaths_h
8 #define js_UbiNodeShortestPaths_h
10 #include "mozilla/Attributes.h"
11 #include "mozilla/Maybe.h"
12 #include "mozilla/Move.h"
14 #include "js/AllocPolicy.h"
15 #include "js/UbiNodeBreadthFirst.h"
16 #include "js/UniquePtr.h"
17 #include "js/Vector.h"
23 * A back edge along a path in the heap graph.
25 struct JS_PUBLIC_API BackEdge
{
31 using Ptr
= js::UniquePtr
<BackEdge
>;
33 BackEdge() : predecessor_(), name_(nullptr) {}
35 MOZ_MUST_USE
bool init(const Node
& predecessor
, Edge
& edge
) {
36 MOZ_ASSERT(!predecessor_
);
39 predecessor_
= predecessor
;
40 name_
= std::move(edge
.name
);
44 BackEdge(const BackEdge
&) = delete;
45 BackEdge
& operator=(const BackEdge
&) = delete;
47 BackEdge(BackEdge
&& rhs
)
48 : predecessor_(rhs
.predecessor_
), name_(std::move(rhs
.name_
)) {
49 MOZ_ASSERT(&rhs
!= this);
52 BackEdge
& operator=(BackEdge
&& rhs
) {
54 new (this) BackEdge(std::move(rhs
));
60 const EdgeName
& name() const { return name_
; }
61 EdgeName
& name() { return name_
; }
63 const JS::ubi::Node
& predecessor() const { return predecessor_
; }
67 * A path is a series of back edges from which we discovered a target node.
69 using Path
= JS::ubi::Vector
<BackEdge
*>;
72 * The `JS::ubi::ShortestPaths` type represents a collection of up to N shortest
73 * retaining paths for each of a target set of nodes, starting from the same
76 struct JS_PUBLIC_API ShortestPaths
{
78 // Types, type aliases, and data members.
80 using BackEdgeVector
= JS::ubi::Vector
<BackEdge::Ptr
>;
81 using NodeToBackEdgeVectorMap
=
82 js::HashMap
<Node
, BackEdgeVector
, js::DefaultHasher
<Node
>,
83 js::SystemAllocPolicy
>;
86 using Traversal
= BreadthFirst
<Handler
>;
89 * A `JS::ubi::BreadthFirst` traversal handler that records back edges for
90 * how we reached each node, allowing us to reconstruct the shortest
91 * retaining paths after the traversal.
94 using NodeData
= BackEdge
;
96 ShortestPaths
& shortestPaths
;
97 size_t totalMaxPathsToRecord
;
98 size_t totalPathsRecorded
;
100 explicit Handler(ShortestPaths
& shortestPaths
)
101 : shortestPaths(shortestPaths
),
102 totalMaxPathsToRecord(shortestPaths
.targets_
.count() *
103 shortestPaths
.maxNumPaths_
),
104 totalPathsRecorded(0) {}
106 bool operator()(Traversal
& traversal
, const JS::ubi::Node
& origin
,
107 JS::ubi::Edge
& edge
, BackEdge
* back
, bool first
) {
109 MOZ_ASSERT(origin
== shortestPaths
.root_
||
110 traversal
.visited
.has(origin
));
111 MOZ_ASSERT(totalPathsRecorded
< totalMaxPathsToRecord
);
113 if (first
&& !back
->init(origin
, edge
)) {
117 if (!shortestPaths
.targets_
.has(edge
.referent
)) {
121 // If `first` is true, then we moved the edge's name into `back` in
122 // the above call to `init`. So clone that back edge to get the
123 // correct edge name. If `first` is not true, then our edge name is
124 // still in `edge`. This accounts for the asymmetry between
125 // `back->clone()` in the first branch, and the `init` call in the
129 BackEdgeVector paths
;
130 if (!paths
.reserve(shortestPaths
.maxNumPaths_
)) {
133 auto cloned
= back
->clone();
137 paths
.infallibleAppend(std::move(cloned
));
138 if (!shortestPaths
.paths_
.putNew(edge
.referent
, std::move(paths
))) {
141 totalPathsRecorded
++;
143 auto ptr
= shortestPaths
.paths_
.lookup(edge
.referent
);
145 "This isn't the first time we have seen the target node "
147 "We should have inserted it into shortestPaths.paths_ the "
151 if (ptr
->value().length() < shortestPaths
.maxNumPaths_
) {
152 auto thisBackEdge
= js::MakeUnique
<BackEdge
>();
153 if (!thisBackEdge
|| !thisBackEdge
->init(origin
, edge
)) {
156 ptr
->value().infallibleAppend(std::move(thisBackEdge
));
157 totalPathsRecorded
++;
161 MOZ_ASSERT(totalPathsRecorded
<= totalMaxPathsToRecord
);
162 if (totalPathsRecorded
== totalMaxPathsToRecord
) {
170 // The maximum number of paths to record for each node.
171 uint32_t maxNumPaths_
;
173 // The root node we are starting the search from.
176 // The set of nodes we are searching for paths to.
179 // The resulting paths.
180 NodeToBackEdgeVectorMap paths_
;
182 // Need to keep alive the traversal's back edges so we can walk them later
183 // when the traversal is over when recreating the shortest paths.
184 Traversal::NodeMap backEdges_
;
189 ShortestPaths(uint32_t maxNumPaths
, const Node
& root
, NodeSet
&& targets
)
190 : maxNumPaths_(maxNumPaths
),
192 targets_(std::move(targets
)),
193 paths_(targets_
.count()),
195 MOZ_ASSERT(maxNumPaths_
> 0);
202 ShortestPaths(ShortestPaths
&& rhs
)
203 : maxNumPaths_(rhs
.maxNumPaths_
),
205 targets_(std::move(rhs
.targets_
)),
206 paths_(std::move(rhs
.paths_
)),
207 backEdges_(std::move(rhs
.backEdges_
)) {
208 MOZ_ASSERT(this != &rhs
, "self-move is not allowed");
211 ShortestPaths
& operator=(ShortestPaths
&& rhs
) {
212 this->~ShortestPaths();
213 new (this) ShortestPaths(std::move(rhs
));
217 ShortestPaths(const ShortestPaths
&) = delete;
218 ShortestPaths
& operator=(const ShortestPaths
&) = delete;
221 * Construct a new `JS::ubi::ShortestPaths`, finding up to `maxNumPaths`
222 * shortest retaining paths for each target node in `targets` starting from
225 * The resulting `ShortestPaths` instance must not outlive the
226 * `JS::ubi::Node` graph it was constructed from.
228 * - For `JS::ubi::Node` graphs backed by the live heap graph, this means
229 * that the `ShortestPaths`'s lifetime _must_ be contained within the
230 * scope of the provided `AutoCheckCannotGC` reference because a GC will
231 * invalidate the nodes.
233 * - For `JS::ubi::Node` graphs backed by some other offline structure
234 * provided by the embedder, the resulting `ShortestPaths`'s lifetime is
235 * bounded by that offline structure's lifetime.
237 * Returns `mozilla::Nothing()` on OOM failure. It is the caller's
238 * responsibility to handle and report the OOM.
240 static mozilla::Maybe
<ShortestPaths
> Create(JSContext
* cx
,
241 AutoCheckCannotGC
& noGC
,
242 uint32_t maxNumPaths
,
245 MOZ_ASSERT(targets
.count() > 0);
246 MOZ_ASSERT(maxNumPaths
> 0);
248 ShortestPaths
paths(maxNumPaths
, root
, std::move(targets
));
250 Handler
handler(paths
);
251 Traversal
traversal(cx
, handler
, noGC
);
252 traversal
.wantNames
= true;
253 if (!traversal
.addStart(root
) || !traversal
.traverse()) {
254 return mozilla::Nothing();
257 // Take ownership of the back edges we created while traversing the
258 // graph so that we can follow them from `paths_` and don't
260 paths
.backEdges_
= std::move(traversal
.visited
);
262 return mozilla::Some(std::move(paths
));
266 * Get an iterator over each target node we searched for retaining paths
267 * for. The returned iterator must not outlive the `ShortestPaths`
270 NodeSet::Iterator
targetIter() const { return targets_
.iter(); }
273 * Invoke the provided functor/lambda/callable once for each retaining path
274 * discovered for `target`. The `func` is passed a single `JS::ubi::Path&`
275 * argument, which contains each edge along the path ordered starting from
276 * the root and ending at the target, and must not outlive the scope of the
279 * Note that it is possible that we did not find any paths from the root to
280 * the given target, in which case `func` will not be invoked.
282 template <class Func
>
283 MOZ_MUST_USE
bool forEachPath(const Node
& target
, Func func
) {
284 MOZ_ASSERT(targets_
.has(target
));
286 auto ptr
= paths_
.lookup(target
);
288 // We didn't find any paths to this target, so nothing to do here.
293 MOZ_ASSERT(ptr
->value().length() <= maxNumPaths_
);
296 for (const auto& backEdge
: ptr
->value()) {
299 if (!path
.append(backEdge
.get())) {
303 Node here
= backEdge
->predecessor();
306 while (here
!= root_
) {
307 auto p
= backEdges_
.lookup(here
);
309 if (!path
.append(&p
->value())) {
312 here
= p
->value().predecessor();
328 // A helper function to dump the first `maxNumPaths` shortest retaining paths to
329 // `node` from the GC roots. Useful when GC things you expect to have been
330 // reclaimed by the collector haven't been!
334 // JSObject* foo = ...;
335 // JS::ubi::dumpPaths(rt, JS::ubi::Node(foo));
336 JS_PUBLIC_API
void dumpPaths(JSRuntime
* rt
, Node node
,
337 uint32_t maxNumPaths
= 10);
343 #endif // js_UbiNodeShortestPaths_h