hphp/runtime/base/heap-graph.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #ifndef incl_HPHP_HEAP_GRAPH_H_
  18 #define incl_HPHP_HEAP_GRAPH_H_
  19
  20 #include "hphp/util/type-scan.h"
  21 #include <vector>
  22 #include <cstdint>
  23 #include <cstddef>
  24
  25 namespace HPHP {
  26
  27 struct HeapObject;
  28
  29 // Graph representation of the heap. The heap consists of some objects
  30 // (Nodes), and directed pointers (Ptrs) from Node to Node. For each
  31 // node, we maintain two singly linked lists:
  32 //
  33 // 1. a list of pointers from this node to other nodes (out-ptrs)
  34 // 2. a list of pointers from other nodes to this node (in-ptrs).
  35 //
  36 // Each pointer is a member of both lists, except root pointers which
  37 // are only a member of a node's in-ptr list.
  38 //
  39 // Additionally, each Ptr records it's from and to nodes. This allows
  40 // traversing the heap graph in either direction (roots toward leaves,
  41 // or vice-versa). However, each list is singly linked; the order of
  42 // pointers in the least is meaningless and we don't need to support
  43 // deleting pointers (or nodes).
  44
  45 struct HeapGraph {
  46   enum PtrKind : uint8_t {
  47     Counted, // exactly-marked, ref-counted, pointer
  48     Ambiguous, // any ambiguous pointer into a valid object
  49     Weak, // a weak pointer to a possibly dead object
  50   };
  51   static constexpr auto NumPtrKinds = 3;
  52   struct Node {
  53     union {
  54       const void* ptr;
  55       const HeapObject* h;
  56     };
  57     size_t size;
  58     bool is_root;
  59     type_scan::Index tyindex;
  60     int first_out;
  61     int first_in; // first out-ptr and in-ptr, respectively
  62   };
  63   struct Ptr {
  64     int from, to; // node ids. if root, from == -1
  65     int next_out, next_in; // from's next out-ptr, to's next in-ptr
  66     int offset; // byte offset of ptr within from node. (0 if unknown)
  67     PtrKind ptr_kind;
  68   };
  69   std::vector<Node> nodes;
  70   std::vector<Ptr> ptrs;
  71   std::vector<int> root_ptrs; // ptr ids
  72   std::vector<int> root_nodes; // node ids
  73
  74   template<class F> void eachSuccNode(int n, F f) const {
  75     eachOutPtr(n, [&](int p) { f(ptrs[p].to); });
  76   }
  77
  78   template<class F> void eachOutPtr(int n, F f) const {
  79     for (int p = nodes[n].first_out; p != -1; p = ptrs[p].next_out) {
  80       f(p);
  81     }
  82   }
  83
  84   template<class F> void eachInPtr(int n, F f) const {
  85     for (int p = nodes[n].first_in; p != -1; p = ptrs[p].next_in) {
  86       f(p);
  87     }
  88   }
  89
  90   template<class F> void eachPred(int n, F f) const {
  91     for (int p = nodes[n].first_in; p != -1; p = ptrs[p].next_in) {
  92       f(ptrs[p]);
  93     }
  94   }
  95
  96   template<class F> void eachRootPtr(F f) const {
  97     for (auto p : root_ptrs) f(ptrs[p]);
  98   }
  99 };
 100
 101 // Summary of heap cycles found in a HeapGraph
 102 struct HeapCycles {
 103   using NodeList = std::vector<int>;
 104   std::vector<NodeList> live_cycles, leaked_cycles;
 105 };
 106
 107 // Make a snapshot of the heap. It will contain pointers to objects
 108 // in the heap so their properties or contents can be inspected.
 109 // With great power comes great responsibility; if you invoke anything
 110 // that frees or moves objects, pointers in this snapshot will be stale.
 111 // if include_free is true, include free blocks, allowing dangling pointers
 112 HeapGraph makeHeapGraph(bool include_free = false);
 113
 114 // Analyze the graph for cycles, then TRACE interesting things about cycles.
 115 void printHeapReport(const HeapGraph&, const char* phase);
 116
 117 // Run a DFS over the heap, remember the first pointer id to each
 118 // reachable node, aka its "parent". The tree formed by the parent
 119 // edges is a spanning tree for the reachable nodes.
 120 // Given a node, you can walk the parents towards roots to find out
 121 // why the node is reachable. parent[k] == -1 for unreachable nodes.
 122 std::vector<int> makeParentTree(const HeapGraph&);
 123
 124 // integrity check pointers and refcounts
 125 bool checkPointers(const HeapGraph& g, const char* phase);
 126
 127 }
 128
 129 #endif