Line data Source code
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_UbiNodeShortestPaths_h
8 : #define js_UbiNodeShortestPaths_h
9 :
10 : #include "mozilla/Attributes.h"
11 : #include "mozilla/Maybe.h"
12 : #include "mozilla/Move.h"
13 :
14 : #include "jsalloc.h"
15 :
16 : #include "js/UbiNodeBreadthFirst.h"
17 : #include "js/Vector.h"
18 :
19 : namespace JS {
20 : namespace ubi {
21 :
22 : /**
23 : * A back edge along a path in the heap graph.
24 : */
25 0 : struct JS_PUBLIC_API(BackEdge)
26 : {
27 : private:
28 : Node predecessor_;
29 : EdgeName name_;
30 :
31 : public:
32 : using Ptr = mozilla::UniquePtr<BackEdge, JS::DeletePolicy<BackEdge>>;
33 :
34 0 : BackEdge() : predecessor_(), name_(nullptr) { }
35 :
36 0 : MOZ_MUST_USE bool init(const Node& predecessor, Edge& edge) {
37 0 : MOZ_ASSERT(!predecessor_);
38 0 : MOZ_ASSERT(!name_);
39 :
40 0 : predecessor_ = predecessor;
41 0 : name_ = mozilla::Move(edge.name);
42 0 : return true;
43 : }
44 :
45 : BackEdge(const BackEdge&) = delete;
46 : BackEdge& operator=(const BackEdge&) = delete;
47 :
48 0 : BackEdge(BackEdge&& rhs)
49 0 : : predecessor_(rhs.predecessor_)
50 0 : , name_(mozilla::Move(rhs.name_))
51 : {
52 0 : MOZ_ASSERT(&rhs != this);
53 0 : }
54 :
55 : BackEdge& operator=(BackEdge&& rhs) {
56 : this->~BackEdge();
57 : new(this) BackEdge(Move(rhs));
58 : return *this;
59 : }
60 :
61 : Ptr clone() const;
62 :
63 0 : const EdgeName& name() const { return name_; }
64 0 : EdgeName& name() { return name_; }
65 :
66 0 : const JS::ubi::Node& predecessor() const { return predecessor_; }
67 : };
68 :
69 : /**
70 : * A path is a series of back edges from which we discovered a target node.
71 : */
72 : using Path = JS::ubi::Vector<BackEdge*>;
73 :
74 : /**
75 : * The `JS::ubi::ShortestPaths` type represents a collection of up to N shortest
76 : * retaining paths for each of a target set of nodes, starting from the same
77 : * root node.
78 : */
79 0 : struct JS_PUBLIC_API(ShortestPaths)
80 : {
81 : private:
82 : // Types, type aliases, and data members.
83 :
84 : using BackEdgeVector = JS::ubi::Vector<BackEdge::Ptr>;
85 : using NodeToBackEdgeVectorMap = js::HashMap<Node, BackEdgeVector, js::DefaultHasher<Node>,
86 : js::SystemAllocPolicy>;
87 :
88 : struct Handler;
89 : using Traversal = BreadthFirst<Handler>;
90 :
91 : /**
92 : * A `JS::ubi::BreadthFirst` traversal handler that records back edges for
93 : * how we reached each node, allowing us to reconstruct the shortest
94 : * retaining paths after the traversal.
95 : */
96 : struct Handler
97 : {
98 : using NodeData = BackEdge;
99 :
100 : ShortestPaths& shortestPaths;
101 : size_t totalMaxPathsToRecord;
102 : size_t totalPathsRecorded;
103 :
104 0 : explicit Handler(ShortestPaths& shortestPaths)
105 0 : : shortestPaths(shortestPaths)
106 0 : , totalMaxPathsToRecord(shortestPaths.targets_.count() * shortestPaths.maxNumPaths_)
107 0 : , totalPathsRecorded(0)
108 : {
109 0 : }
110 :
111 : bool
112 0 : operator()(Traversal& traversal, const JS::ubi::Node& origin, JS::ubi::Edge& edge,
113 : BackEdge* back, bool first)
114 : {
115 0 : MOZ_ASSERT(back);
116 0 : MOZ_ASSERT(origin == shortestPaths.root_ || traversal.visited.has(origin));
117 0 : MOZ_ASSERT(totalPathsRecorded < totalMaxPathsToRecord);
118 :
119 0 : if (first && !back->init(origin, edge))
120 0 : return false;
121 :
122 0 : if (!shortestPaths.targets_.has(edge.referent))
123 0 : return true;
124 :
125 : // If `first` is true, then we moved the edge's name into `back` in
126 : // the above call to `init`. So clone that back edge to get the
127 : // correct edge name. If `first` is not true, then our edge name is
128 : // still in `edge`. This accounts for the asymmetry between
129 : // `back->clone()` in the first branch, and the `init` call in the
130 : // second branch.
131 :
132 0 : if (first) {
133 0 : BackEdgeVector paths;
134 0 : if (!paths.reserve(shortestPaths.maxNumPaths_))
135 0 : return false;
136 0 : auto cloned = back->clone();
137 0 : if (!cloned)
138 0 : return false;
139 0 : paths.infallibleAppend(mozilla::Move(cloned));
140 0 : if (!shortestPaths.paths_.putNew(edge.referent, mozilla::Move(paths)))
141 0 : return false;
142 0 : totalPathsRecorded++;
143 : } else {
144 0 : auto ptr = shortestPaths.paths_.lookup(edge.referent);
145 0 : MOZ_ASSERT(ptr,
146 : "This isn't the first time we have seen the target node `edge.referent`. "
147 : "We should have inserted it into shortestPaths.paths_ the first time we "
148 : "saw it.");
149 :
150 0 : if (ptr->value().length() < shortestPaths.maxNumPaths_) {
151 0 : BackEdge::Ptr thisBackEdge(js_new<BackEdge>());
152 0 : if (!thisBackEdge || !thisBackEdge->init(origin, edge))
153 0 : return false;
154 0 : ptr->value().infallibleAppend(mozilla::Move(thisBackEdge));
155 0 : totalPathsRecorded++;
156 : }
157 : }
158 :
159 0 : MOZ_ASSERT(totalPathsRecorded <= totalMaxPathsToRecord);
160 0 : if (totalPathsRecorded == totalMaxPathsToRecord)
161 0 : traversal.stop();
162 :
163 0 : return true;
164 : }
165 :
166 : };
167 :
168 : // The maximum number of paths to record for each node.
169 : uint32_t maxNumPaths_;
170 :
171 : // The root node we are starting the search from.
172 : Node root_;
173 :
174 : // The set of nodes we are searching for paths to.
175 : NodeSet targets_;
176 :
177 : // The resulting paths.
178 : NodeToBackEdgeVectorMap paths_;
179 :
180 : // Need to keep alive the traversal's back edges so we can walk them later
181 : // when the traversal is over when recreating the shortest paths.
182 : Traversal::NodeMap backEdges_;
183 :
184 : private:
185 : // Private methods.
186 :
187 0 : ShortestPaths(uint32_t maxNumPaths, const Node& root, NodeSet&& targets)
188 0 : : maxNumPaths_(maxNumPaths)
189 : , root_(root)
190 0 : , targets_(mozilla::Move(targets))
191 : , paths_()
192 0 : , backEdges_()
193 : {
194 0 : MOZ_ASSERT(maxNumPaths_ > 0);
195 0 : MOZ_ASSERT(root_);
196 0 : MOZ_ASSERT(targets_.initialized());
197 0 : }
198 :
199 0 : bool initialized() const {
200 0 : return targets_.initialized() &&
201 0 : paths_.initialized() &&
202 0 : backEdges_.initialized();
203 : }
204 :
205 : public:
206 : // Public methods.
207 :
208 0 : ShortestPaths(ShortestPaths&& rhs)
209 0 : : maxNumPaths_(rhs.maxNumPaths_)
210 : , root_(rhs.root_)
211 0 : , targets_(mozilla::Move(rhs.targets_))
212 0 : , paths_(mozilla::Move(rhs.paths_))
213 0 : , backEdges_(mozilla::Move(rhs.backEdges_))
214 : {
215 0 : MOZ_ASSERT(this != &rhs, "self-move is not allowed");
216 0 : }
217 :
218 0 : ShortestPaths& operator=(ShortestPaths&& rhs) {
219 0 : this->~ShortestPaths();
220 0 : new (this) ShortestPaths(mozilla::Move(rhs));
221 0 : return *this;
222 : }
223 :
224 : ShortestPaths(const ShortestPaths&) = delete;
225 : ShortestPaths& operator=(const ShortestPaths&) = delete;
226 :
227 : /**
228 : * Construct a new `JS::ubi::ShortestPaths`, finding up to `maxNumPaths`
229 : * shortest retaining paths for each target node in `targets` starting from
230 : * `root`.
231 : *
232 : * The resulting `ShortestPaths` instance must not outlive the
233 : * `JS::ubi::Node` graph it was constructed from.
234 : *
235 : * - For `JS::ubi::Node` graphs backed by the live heap graph, this means
236 : * that the `ShortestPaths`'s lifetime _must_ be contained within the
237 : * scope of the provided `AutoCheckCannotGC` reference because a GC will
238 : * invalidate the nodes.
239 : *
240 : * - For `JS::ubi::Node` graphs backed by some other offline structure
241 : * provided by the embedder, the resulting `ShortestPaths`'s lifetime is
242 : * bounded by that offline structure's lifetime.
243 : *
244 : * Returns `mozilla::Nothing()` on OOM failure. It is the caller's
245 : * responsibility to handle and report the OOM.
246 : */
247 : static mozilla::Maybe<ShortestPaths>
248 0 : Create(JSContext* cx, AutoCheckCannotGC& noGC, uint32_t maxNumPaths, const Node& root, NodeSet&& targets) {
249 0 : MOZ_ASSERT(targets.count() > 0);
250 0 : MOZ_ASSERT(maxNumPaths > 0);
251 :
252 0 : size_t count = targets.count();
253 0 : ShortestPaths paths(maxNumPaths, root, mozilla::Move(targets));
254 0 : if (!paths.paths_.init(count))
255 0 : return mozilla::Nothing();
256 :
257 0 : Handler handler(paths);
258 0 : Traversal traversal(cx, handler, noGC);
259 0 : traversal.wantNames = true;
260 0 : if (!traversal.init() || !traversal.addStart(root) || !traversal.traverse())
261 0 : return mozilla::Nothing();
262 :
263 : // Take ownership of the back edges we created while traversing the
264 : // graph so that we can follow them from `paths_` and don't
265 : // use-after-free.
266 0 : paths.backEdges_ = mozilla::Move(traversal.visited);
267 :
268 0 : MOZ_ASSERT(paths.initialized());
269 0 : return mozilla::Some(mozilla::Move(paths));
270 : }
271 :
272 : /**
273 : * Get a range that iterates over each target node we searched for retaining
274 : * paths for. The returned range must not outlive the `ShortestPaths`
275 : * instance.
276 : */
277 0 : NodeSet::Range eachTarget() const {
278 0 : MOZ_ASSERT(initialized());
279 0 : return targets_.all();
280 : }
281 :
282 : /**
283 : * Invoke the provided functor/lambda/callable once for each retaining path
284 : * discovered for `target`. The `func` is passed a single `JS::ubi::Path&`
285 : * argument, which contains each edge along the path ordered starting from
286 : * the root and ending at the target, and must not outlive the scope of the
287 : * call.
288 : *
289 : * Note that it is possible that we did not find any paths from the root to
290 : * the given target, in which case `func` will not be invoked.
291 : */
292 : template <class Func>
293 0 : MOZ_MUST_USE bool forEachPath(const Node& target, Func func) {
294 0 : MOZ_ASSERT(initialized());
295 0 : MOZ_ASSERT(targets_.has(target));
296 :
297 0 : auto ptr = paths_.lookup(target);
298 :
299 : // We didn't find any paths to this target, so nothing to do here.
300 0 : if (!ptr)
301 0 : return true;
302 :
303 0 : MOZ_ASSERT(ptr->value().length() <= maxNumPaths_);
304 :
305 0 : Path path;
306 0 : for (const auto& backEdge : ptr->value()) {
307 0 : path.clear();
308 :
309 0 : if (!path.append(backEdge.get()))
310 0 : return false;
311 :
312 0 : Node here = backEdge->predecessor();
313 0 : MOZ_ASSERT(here);
314 :
315 0 : while (here != root_) {
316 0 : auto p = backEdges_.lookup(here);
317 0 : MOZ_ASSERT(p);
318 0 : if (!path.append(&p->value()))
319 0 : return false;
320 0 : here = p->value().predecessor();
321 0 : MOZ_ASSERT(here);
322 : }
323 :
324 0 : path.reverse();
325 :
326 0 : if (!func(path))
327 0 : return false;
328 : }
329 :
330 0 : return true;
331 : }
332 : };
333 :
334 : #ifdef DEBUG
335 : // A helper function to dump the first `maxNumPaths` shortest retaining paths to
336 : // `node` from the GC roots. Useful when GC things you expect to have been
337 : // reclaimed by the collector haven't been!
338 : //
339 : // Usage:
340 : //
341 : // JSObject* foo = ...;
342 : // JS::ubi::dumpPaths(rt, JS::ubi::Node(foo));
343 : JS_PUBLIC_API(void)
344 : dumpPaths(JSRuntime* rt, Node node, uint32_t maxNumPaths = 10);
345 : #endif
346 :
347 : } // namespace ubi
348 : } // namespace JS
349 :
350 : #endif // js_UbiNodeShortestPaths_h
|
