tor-browser

UbiNodeShortestPaths.h (10577B)

---

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
* vim: set ts=8 sts=2 et sw=2 tw=80:
* 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/CheckedInt.h"
#include "mozilla/Maybe.h"

#include <utility>

#include "js/AllocPolicy.h"
#include "js/GCAPI.h"
#include "js/UbiNode.h"
#include "js/UbiNodeBreadthFirst.h"
#include "js/UniquePtr.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 = js::UniquePtr<BackEdge>;

 BackEdge() : predecessor_(), name_(nullptr) {}

 [[nodiscard]] bool init(const Node& predecessor, Edge& edge) {
   MOZ_ASSERT(!predecessor_);
   MOZ_ASSERT(!name_);

   predecessor_ = predecessor;
   name_ = std::move(edge.name);
   return true;
 }

 BackEdge(const BackEdge&) = delete;
 BackEdge& operator=(const BackEdge&) = delete;

 BackEdge(BackEdge&& rhs)
     : predecessor_(rhs.predecessor_), name_(std::move(rhs.name_)) {
   MOZ_ASSERT(&rhs != this);
 }

 BackEdge& operator=(BackEdge&& rhs) {
   this->~BackEdge();
   new (this) BackEdge(std::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, const 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(std::move(cloned));
       if (!shortestPaths.paths_.putNew(edge.referent, std::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_) {
         auto thisBackEdge = js::MakeUnique<BackEdge>();
         if (!thisBackEdge || !thisBackEdge->init(origin, edge)) {
           return false;
         }
         ptr->value().infallibleAppend(std::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_(std::move(targets)),
       paths_(targets_.count()),
       backEdges_() {
   MOZ_ASSERT(maxNumPaths_ > 0);
   MOZ_ASSERT(root_);
 }

public:
 // Public methods.

 ShortestPaths(ShortestPaths&& rhs)
     : maxNumPaths_(rhs.maxNumPaths_),
       root_(rhs.root_),
       targets_(std::move(rhs.targets_)),
       paths_(std::move(rhs.paths_)),
       backEdges_(std::move(rhs.backEdges_)) {
   MOZ_ASSERT(this != &rhs, "self-move is not allowed");
 }

 ShortestPaths& operator=(ShortestPaths&& rhs) {
   this->~ShortestPaths();
   new (this) ShortestPaths(std::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);

   mozilla::CheckedInt<uint32_t> max = maxNumPaths;
   max *= targets.count();
   if (!max.isValid()) {
     return mozilla::Nothing();
   }

   ShortestPaths paths(maxNumPaths, root, std::move(targets));

   Handler handler(paths);
   Traversal traversal(cx, handler, noGC);
   traversal.wantNames = true;
   if (!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_ = std::move(traversal.visited);

   return mozilla::Some(std::move(paths));
 }

 /**
  * Get an iterator over each target node we searched for retaining paths
  * for. The returned iterator must not outlive the `ShortestPaths`
  * instance.
  */
 NodeSet::Iterator targetIter() const { return targets_.iter(); }

 /**
  * 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>
 [[nodiscard]] bool forEachPath(const Node& target, Func func) {
   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