/* -*- 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_UbiNodeShortestPaths_h #define js_UbiNodeShortestPaths_h #include "mozilla/Attributes.h" #include "mozilla/Maybe.h" #include "mozilla/Move.h" #include "jsalloc.h" #include "js/UbiNodeBreadthFirst.h" #include "js/Vector.h" namespace JS { namespace ubi { /** * A back edge along a path in the heap graph. */ struct JS_PUBLIC_API(BackEdge) { private: Node predecessor_; EdgeName name_; public: using Ptr = mozilla::UniquePtr<BackEdge, JS::DeletePolicy<BackEdge>>; BackEdge() : predecessor_(), name_(nullptr) { } MOZ_MUST_USE bool init(const Node& predecessor, Edge& edge) { MOZ_ASSERT(!predecessor_); MOZ_ASSERT(!name_); predecessor_ = predecessor; name_ = mozilla::Move(edge.name); return true; } BackEdge(const BackEdge&) = delete; BackEdge& operator=(const BackEdge&) = delete; BackEdge(BackEdge&& rhs) : predecessor_(rhs.predecessor_) , name_(mozilla::Move(rhs.name_)) { MOZ_ASSERT(&rhs != this); } BackEdge& operator=(BackEdge&& rhs) { this->~BackEdge(); new(this) BackEdge(Move(rhs)); return *this; } Ptr clone() const; const EdgeName& name() const { return name_; } EdgeName& name() { return name_; } const JS::ubi::Node& predecessor() const { return predecessor_; } }; /** * A path is a series of back edges from which we discovered a target node. */ using Path = JS::ubi::Vector<BackEdge*>; /** * The `JS::ubi::ShortestPaths` type represents a collection of up to N shortest * retaining paths for each of a target set of nodes, starting from the same * root node. */ struct JS_PUBLIC_API(ShortestPaths) { private: // Types, type aliases, and data members. using BackEdgeVector = JS::ubi::Vector<BackEdge::Ptr>; using NodeToBackEdgeVectorMap = js::HashMap<Node, BackEdgeVector, js::DefaultHasher<Node>, js::SystemAllocPolicy>; struct Handler; using Traversal = BreadthFirst<Handler>; /** * A `JS::ubi::BreadthFirst` traversal handler that records back edges for * how we reached each node, allowing us to reconstruct the shortest * retaining paths after the traversal. */ struct Handler { using NodeData = BackEdge; ShortestPaths& shortestPaths; size_t totalMaxPathsToRecord; size_t totalPathsRecorded; explicit Handler(ShortestPaths& shortestPaths) : shortestPaths(shortestPaths) , totalMaxPathsToRecord(shortestPaths.targets_.count() * shortestPaths.maxNumPaths_) , totalPathsRecorded(0) { } bool operator()(Traversal& traversal, JS::ubi::Node origin, JS::ubi::Edge& edge, BackEdge* back, bool first) { MOZ_ASSERT(back); MOZ_ASSERT(origin == shortestPaths.root_ || traversal.visited.has(origin)); MOZ_ASSERT(totalPathsRecorded < totalMaxPathsToRecord); if (first && !back->init(origin, edge)) return false; if (!shortestPaths.targets_.has(edge.referent)) return true; // If `first` is true, then we moved the edge's name into `back` in // the above call to `init`. So clone that back edge to get the // correct edge name. If `first` is not true, then our edge name is // still in `edge`. This accounts for the asymmetry between // `back->clone()` in the first branch, and the `init` call in the // second branch. if (first) { BackEdgeVector paths; if (!paths.reserve(shortestPaths.maxNumPaths_)) return false; auto cloned = back->clone(); if (!cloned) return false; paths.infallibleAppend(mozilla::Move(cloned)); if (!shortestPaths.paths_.putNew(edge.referent, mozilla::Move(paths))) return false; totalPathsRecorded++; } else { auto ptr = shortestPaths.paths_.lookup(edge.referent); MOZ_ASSERT(ptr, "This isn't the first time we have seen the target node `edge.referent`. " "We should have inserted it into shortestPaths.paths_ the first time we " "saw it."); if (ptr->value().length() < shortestPaths.maxNumPaths_) { BackEdge::Ptr thisBackEdge(js_new<BackEdge>()); if (!thisBackEdge || !thisBackEdge->init(origin, edge)) return false; ptr->value().infallibleAppend(mozilla::Move(thisBackEdge)); totalPathsRecorded++; } } MOZ_ASSERT(totalPathsRecorded <= totalMaxPathsToRecord); if (totalPathsRecorded == totalMaxPathsToRecord) traversal.stop(); return true; } }; // The maximum number of paths to record for each node. uint32_t maxNumPaths_; // The root node we are starting the search from. Node root_; // The set of nodes we are searching for paths to. NodeSet targets_; // The resulting paths. NodeToBackEdgeVectorMap paths_; // Need to keep alive the traversal's back edges so we can walk them later // when the traversal is over when recreating the shortest paths. Traversal::NodeMap backEdges_; private: // Private methods. ShortestPaths(uint32_t maxNumPaths, const Node& root, NodeSet&& targets) : maxNumPaths_(maxNumPaths) , root_(root) , targets_(mozilla::Move(targets)) , paths_() , backEdges_() { MOZ_ASSERT(maxNumPaths_ > 0); MOZ_ASSERT(root_); MOZ_ASSERT(targets_.initialized()); } bool initialized() const { return targets_.initialized() && paths_.initialized() && backEdges_.initialized(); } public: // Public methods. ShortestPaths(ShortestPaths&& rhs) : maxNumPaths_(rhs.maxNumPaths_) , root_(rhs.root_) , targets_(mozilla::Move(rhs.targets_)) , paths_(mozilla::Move(rhs.paths_)) , backEdges_(mozilla::Move(rhs.backEdges_)) { MOZ_ASSERT(this != &rhs, "self-move is not allowed"); } ShortestPaths& operator=(ShortestPaths&& rhs) { this->~ShortestPaths(); new (this) ShortestPaths(mozilla::Move(rhs)); return *this; } ShortestPaths(const ShortestPaths&) = delete; ShortestPaths& operator=(const ShortestPaths&) = delete; /** * Construct a new `JS::ubi::ShortestPaths`, finding up to `maxNumPaths` * shortest retaining paths for each target node in `targets` starting from * `root`. * * The resulting `ShortestPaths` instance must not outlive the * `JS::ubi::Node` graph it was constructed from. * * - For `JS::ubi::Node` graphs backed by the live heap graph, this means * that the `ShortestPaths`'s lifetime _must_ be contained within the * scope of the provided `AutoCheckCannotGC` reference because a GC will * invalidate the nodes. * * - For `JS::ubi::Node` graphs backed by some other offline structure * provided by the embedder, the resulting `ShortestPaths`'s lifetime is * bounded by that offline structure's lifetime. * * Returns `mozilla::Nothing()` on OOM failure. It is the caller's * responsibility to handle and report the OOM. */ static mozilla::Maybe<ShortestPaths> Create(JSContext* cx, AutoCheckCannotGC& noGC, uint32_t maxNumPaths, const Node& root, NodeSet&& targets) { MOZ_ASSERT(targets.count() > 0); MOZ_ASSERT(maxNumPaths > 0); size_t count = targets.count(); ShortestPaths paths(maxNumPaths, root, mozilla::Move(targets)); if (!paths.paths_.init(count)) return mozilla::Nothing(); Handler handler(paths); Traversal traversal(cx, handler, noGC); traversal.wantNames = true; if (!traversal.init() || !traversal.addStart(root) || !traversal.traverse()) return mozilla::Nothing(); // Take ownership of the back edges we created while traversing the // graph so that we can follow them from `paths_` and don't // use-after-free. paths.backEdges_ = mozilla::Move(traversal.visited); MOZ_ASSERT(paths.initialized()); return mozilla::Some(mozilla::Move(paths)); } /** * Get a range that iterates over each target node we searched for retaining * paths for. The returned range must not outlive the `ShortestPaths` * instance. */ NodeSet::Range eachTarget() const { MOZ_ASSERT(initialized()); return targets_.all(); } /** * Invoke the provided functor/lambda/callable once for each retaining path * discovered for `target`. The `func` is passed a single `JS::ubi::Path&` * argument, which contains each edge along the path ordered starting from * the root and ending at the target, and must not outlive the scope of the * call. * * Note that it is possible that we did not find any paths from the root to * the given target, in which case `func` will not be invoked. */ template <class Func> MOZ_MUST_USE bool forEachPath(const Node& target, Func func) { MOZ_ASSERT(initialized()); MOZ_ASSERT(targets_.has(target)); auto ptr = paths_.lookup(target); // We didn't find any paths to this target, so nothing to do here. if (!ptr) return true; MOZ_ASSERT(ptr->value().length() <= maxNumPaths_); Path path; for (const auto& backEdge : ptr->value()) { path.clear(); if (!path.append(backEdge.get())) return false; Node here = backEdge->predecessor(); MOZ_ASSERT(here); while (here != root_) { auto p = backEdges_.lookup(here); MOZ_ASSERT(p); if (!path.append(&p->value())) return false; here = p->value().predecessor(); MOZ_ASSERT(here); } path.reverse(); if (!func(path)) return false; } return true; } }; #ifdef DEBUG // A helper function to dump the first `maxNumPaths` shortest retaining paths to // `node` from the GC roots. Useful when GC things you expect to have been // reclaimed by the collector haven't been! // // Usage: // // JSObject* foo = ...; // JS::ubi::dumpPaths(rt, JS::ubi::Node(foo)); JS_PUBLIC_API(void) dumpPaths(JSRuntime* rt, Node node, uint32_t maxNumPaths = 10); #endif } // namespace ubi } // namespace JS #endif // js_UbiNodeShortestPaths_h