2 +----------------------------------------------------------------------+
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 +----------------------------------------------------------------------+
17 #ifndef incl_HPHP_HEAP_GRAPH_H_
18 #define incl_HPHP_HEAP_GRAPH_H_
20 #include "hphp/util/type-scan.h"
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:
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).
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.
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).
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
51 static constexpr auto NumPtrKinds
= 3;
59 type_scan::Index tyindex
;
61 int first_in
; // first out-ptr and in-ptr, respectively
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)
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
74 template<class F
> void eachSuccNode(int n
, F f
) const {
75 eachOutPtr(n
, [&](int p
) { f(ptrs
[p
].to
); });
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
) {
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
) {
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
) {
96 template<class F
> void eachRootPtr(F f
) const {
97 for (auto p
: root_ptrs
) f(ptrs
[p
]);
101 // Summary of heap cycles found in a HeapGraph
103 using NodeList
= std::vector
<int>;
104 std::vector
<NodeList
> live_cycles
, leaked_cycles
;
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);
114 // Analyze the graph for cycles, then TRACE interesting things about cycles.
115 void printHeapReport(const HeapGraph
&, const char* phase
);
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
&);
124 // integrity check pointers and refcounts
125 bool checkPointers(const HeapGraph
& g
, const char* phase
);