src/trace_processor/importers/proto/heap_graph_walker.h

/*
 * Copyright (C) 2019 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef SRC_TRACE_PROCESSOR_IMPORTERS_PROTO_HEAP_GRAPH_WALKER_H_
#define SRC_TRACE_PROCESSOR_IMPORTERS_PROTO_HEAP_GRAPH_WALKER_H_

#include <inttypes.h>
#include <map>
#include <set>
#include <vector>

// Implements two algorithms that walk a HeapGraph.
// a) Traverse all references from roots and mark the nodes as reachable.
// b) For each node, calculate two numbers:
//    1. retained: The number of bytes that are directly and indirectly
//       referenced by the node.
//    2. uniquely retained: The number of bytes that are only retained through
//       this object. If this object were destroyed, this many bytes would be
//       freed up.
//
// The algorithm for b) is a modified Tarjan's algorithm. We use Tarjan's
// algorithm to find connected components. This is such that we break cycles
// that can exist in the retention graphs. All nodes within the cycle get
// assigned the same component. Then, most of the graph algorithm operates on
// these components.
//
// For instance, the below graph, which for simplicity does not contain any
// loops.
// Apart from nodes retaining / uniquely retaining themselves:
// a retains nothing
// a uniquely retains nothing
//
// b retains a
// b uniquely retains nothing
//
// c retains a
// c uniquely retains nothing
//
// d retains a, b, c
// d uniquely retains a, b, c
//
//     a      |
//    ^^      |
//   /  \     |
//   b   c    |
//   ^   ^    |
//    \ /     |
//     d      |
//
// The basic idea of the algorithm is to assign every node a fractional
// retention of other nodes. In the same graph:
// a retains nothing
// a uniquely retains nothing
//
// b retains a
// b 1/2 uniquely retains a
//
// c retains a
// c 1/2 uniquely retains a
//
// d retains a, b, c
// d 1/2 + 1/2 = 1 uniquely retains a
// d 1 uniquely retains b and c
//
// A more complete example
//
//     a       |
//    ^^       |
//   /  \      |
//   b   c     |
//   ^   ^     |
//    \ / \    |
//     d  e    |
//     ^  ^    |
//     \  /    |
//      f      |
//
// b: 1/2 retains a
// c: 1/2 retains a
// d: 3/4 retains a (all of b's share, half of c's)
// e: 1/4 retains a (half of c's share)
// f: 4/4 = 1 retains a

namespace perfetto {
namespace trace_processor {

class Fraction {
 public:
  Fraction() : Fraction(0, 1) {}

  Fraction(const Fraction&) = default;
  Fraction(uint64_t numerator, uint64_t denominator);
  Fraction& operator+=(const Fraction& other);
  bool operator==(uint64_t other) const;
  Fraction operator*(const Fraction& other);

  uint64_t numerator() const { return numerator_; }
  uint64_t denominator() const { return denominator_; }

 private:
  // Reduce fraction. E.g., turn 2 / 4 into 1 / 2.
  void Reduce();

  uint64_t numerator_;
  uint64_t denominator_;
};

class HeapGraphWalker {
 public:
  class Delegate {
   public:
    virtual ~Delegate();
    virtual void MarkReachable(int64_t row) = 0;
    virtual void SetRetained(int64_t row,
                             int64_t retained,
                             int64_t unique_retained) = 0;
  };

  HeapGraphWalker(Delegate* delegate) : delegate_(delegate) {}

  void AddEdge(int64_t owner_row, int64_t owned_row);
  void AddNode(int64_t row, uint64_t size);

  // Mark a a node as root. This marks all the nodes reachable from it as
  // reachable.
  void MarkRoot(int64_t row);
  // Calculate the retained and unique retained size for each node. This
  // includes nodes not reachable from roots.
  void CalculateRetained();

 private:
  struct Node {
    // These are sets to conveniently get rid of double edges between nodes.
    // We do not care if an object owns another object via multiple references
    // or only one.
    std::set<Node*> children;
    std::set<Node*> parents;
    bool reachable = false;
    bool on_stack = false;
    uint64_t self_size = 0;
    uint64_t retained_size = 0;

    int64_t row = 0;
    uint64_t node_index = 0;
    uint64_t lowlink = 0;
    int64_t component = -1;
  };

  struct Component {
    uint64_t unique_retained_size = 0;
    size_t incoming_edges = 0;
    size_t orig_incoming_edges = 0;
    std::map<int64_t, Fraction> children_components;
    uint64_t lowlink = 0;
  };

  Node& GetNode(int64_t id) { return nodes_[static_cast<size_t>(id)]; }

  void FindSCC(Node*);
  void FoundSCC(Node*);
  int64_t RetainedSize(const Component&);

  // Make node and all transitive children as reachable.
  void ReachableNode(Node*);

  std::vector<Component> components_;
  std::vector<Node*> node_stack_;
  uint64_t next_node_index_ = 1;
  std::vector<Node> nodes_;

  Delegate* delegate_;
};

}  // namespace trace_processor
}  // namespace perfetto

#endif  // SRC_TRACE_PROCESSOR_IMPORTERS_PROTO_HEAP_GRAPH_WALKER_H_