hphp/runtime/base/heap-graph.cpp

   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 #include "hphp/runtime/base/heap-graph.h"
  17 #include "hphp/runtime/base/heap-algorithms.h"
  18 #include "hphp/runtime/base/types.h"
  19 #include "hphp/runtime/base/req-containers.h"
  20 #include "hphp/runtime/base/memory-manager-defs.h"
  21 #include "hphp/runtime/base/heap-scan.h"
  22 #include "hphp/runtime/base/thread-info.h"
  23 #include "hphp/runtime/base/container-functions.h"
  24 #include "hphp/runtime/base/tv-mutate.h"
  25 #include "hphp/runtime/base/tv-variant.h"
  26 #include "hphp/runtime/ext/weakref/weakref-data-handle.h"
  27 #include "hphp/util/alloc.h"
  28 #include "hphp/util/ptr-map.h"
  29
  30 #include <vector>
  31 #include <folly/Range.h>
  32
  33 namespace HPHP {
  34
  35 template<class Fn> void FOLLY_DISABLE_ADDRESS_SANITIZER
  36 conservativeScan(const void* start, size_t len, Fn fn) {
  37   const uintptr_t M{7}; // word size - 1
  38   auto s = (const void**)((uintptr_t(start) + M) & ~M); // round up
  39   auto e = (const void**)((uintptr_t(start) + len) & ~M); // round down
  40   for (; s < e; s++) {
  41     // Mask off the upper 16-bits to handle things like
  42     // DiscriminatedPtr which stores things up there.
  43     fn(s, (const void*)(uintptr_t(*s) & (-1ULL >> 16)));
  44   }
  45 }
  46
  47 namespace {
  48
  49 size_t addPtr(HeapGraph& g, int from, int to, HeapGraph::PtrKind kind,
  50             ptrdiff_t offset) {
  51   auto& from_node = g.nodes[from];
  52   auto& to_node = g.nodes[to];
  53   auto e = g.ptrs.size();
  54   g.ptrs.push_back(
  55     HeapGraph::Ptr{from, to, from_node.first_out, to_node.first_in,
  56                    (int)offset, kind}
  57   );
  58   from_node.first_out = to_node.first_in = e;
  59   return e;
  60 }
  61
  62 void addRootNode(HeapGraph& g, const PtrMap<const HeapObject*>& blocks,
  63                  type_scan::Scanner& scanner,
  64                  const void* h, size_t size, type_scan::Index ty) {
  65   auto from = g.nodes.size();
  66   g.nodes.push_back(
  67     HeapGraph::Node{h, size, true, ty, -1, -1}
  68   );
  69   g.root_nodes.push_back(from);
  70   scanner.scanByIndex(ty, h, size);
  71   scanner.finish(
  72     [&](const void* p, std::size_t size) {
  73       conservativeScan(p, size, [&](const void** addr, const void* ptr) {
  74         if (auto r = blocks.region(ptr)) {
  75           auto to = blocks.index(r);
  76           auto offset = uintptr_t(addr) - uintptr_t(h);
  77           auto e = addPtr(g, from, to, HeapGraph::Ambiguous, offset);
  78           g.root_ptrs.push_back(e);
  79         }
  80       });
  81     },
  82     [&](const void** addr) {
  83       if (auto r = blocks.region(*addr)) {
  84         auto to = blocks.index(r);
  85         auto offset = uintptr_t(addr) - uintptr_t(h);
  86         auto e = addPtr(g, from, to, HeapGraph::Counted, offset);
  87         g.root_ptrs.push_back(e);
  88       }
  89     },
  90     [&](const void* p) {
  91       auto weak = static_cast<const WeakRefDataHandle*>(p);
  92       auto addr = &(weak->wr_data->pointee.m_data.pobj);
  93       if (auto r = blocks.region(*addr)) {
  94         auto to = blocks.index(r);
  95         // Note that offset is going to be meaningless because weak->wr_data is
  96         // a shared_ptr, so &pointee.m_data.pobj will be inside the shared_ptr's
  97         // internal node, allocated separately.
  98         addPtr(g, from, to, HeapGraph::Weak, 0);
  99       }
 100     }
 101   );
 102 }
 103
 104 } // anon namespace
 105
 106 // Run a DFS over the heap, remember the first pointer id to each
 107 // reachable node, aka its "parent". The tree formed by the parent
 108 // edges is a spanning tree for the reachable nodes.
 109 // Given a node, you can walk the parents towards roots to find out
 110 // why the node is reachable. parent[k] == -1 for unreachable nodes.
 111 std::vector<int> makeParentTree(const HeapGraph& g) {
 112   std::vector<int> parents(g.nodes.size(), -1);
 113   dfs_ptrs(g, g.root_ptrs, [&](int node, int ptr) {
 114     parents[node] = ptr;
 115   });
 116   return parents;
 117 }
 118
 119 // parse the heap to find valid objects and initialize metadata, then
 120 // add edges for every known root pointer and every known obj->obj ptr.
 121 HeapGraph makeHeapGraph(bool include_free) {
 122   HeapGraph g;
 123   PtrMap<const HeapObject*> blocks;
 124
 125   // parse the heap once to create a PtrMap for pointer filtering. Create
 126   // one node for every parsed block, including NativeData and AsyncFuncFrame
 127   // blocks. Only include free blocks if requested.
 128   tl_heap->forEachHeapObject([&](HeapObject* h, size_t alloc_size) {
 129     if (h->kind() != HeaderKind::Free || include_free) {
 130       blocks.insert(h, alloc_size); // adds interval [h, h+alloc_size[
 131     }
 132   });
 133   blocks.prepare();
 134
 135   // initialize nodes by iterating over PtrMap's regions
 136   g.nodes.reserve(blocks.size());
 137   blocks.iterate([&](const HeapObject* h, size_t size) {
 138     type_scan::Index ty;
 139     switch (h->kind()) {
 140       case HeaderKind::NativeData:
 141         ty = static_cast<const NativeNode*>(h)->typeIndex();
 142         break;
 143       case HeaderKind::Resource:
 144         ty = static_cast<const ResourceHdr*>(h)->typeIndex();
 145         break;
 146       case HeaderKind::SmallMalloc:
 147       case HeaderKind::BigMalloc:
 148         ty = static_cast<const MallocNode*>(h)->typeIndex();
 149         break;
 150       default:
 151         ty = type_scan::kIndexUnknown;
 152         break;
 153     }
 154     g.nodes.push_back(
 155       HeapGraph::Node{h, size, false, ty, -1, -1}
 156     );
 157   });
 158
 159   // find root nodes
 160   type_scan::Scanner scanner;
 161   iterateRoots([&](const void* h, size_t size, type_scan::Index tyindex) {
 162     // it's important that we actually scan each root node before
 163     // returning, since at least one will be the C++ stack, and some
 164     // nodes will only exist for the duration of the call to this lambda,
 165     // for example EphemeralPtrWrapper<T>.
 166     addRootNode(g, blocks, scanner, h, size, tyindex);
 167   });
 168
 169   // find heap->heap pointers
 170   for (size_t i = 0, n = g.nodes.size(); i < n; i++) {
 171     if (g.nodes[i].is_root) continue;
 172     auto h = g.nodes[i].h;
 173     scanHeapObject(h, scanner);
 174     auto from = blocks.index(h);
 175     assert(from == i);
 176     scanner.finish(
 177       [&](const void* p, std::size_t size) {
 178         conservativeScan(p, size, [&](const void** addr, const void* ptr) {
 179           if (auto r = blocks.region(ptr)) {
 180             auto to = blocks.index(r);
 181             auto offset = uintptr_t(addr) - uintptr_t(h);
 182             addPtr(g, from, to, HeapGraph::Ambiguous, offset);
 183           }
 184         });
 185       },
 186       [&](const void** addr) {
 187         if (auto r = blocks.region(*addr)) {
 188           auto to = blocks.index(r);
 189           auto offset = uintptr_t(addr) - uintptr_t(h);
 190           addPtr(g, from, to, HeapGraph::Counted, offset);
 191         }
 192       },
 193       [&](const void* p) {
 194         auto weak = static_cast<const WeakRefDataHandle*>(p);
 195         auto addr = &(weak->wr_data->pointee.m_data.pobj);
 196         if (auto r = blocks.region(*addr)) {
 197           auto to = blocks.index(r);
 198           addPtr(g, from, to, HeapGraph::Weak, 0);
 199         }
 200       }
 201     );
 202   }
 203   g.nodes.shrink_to_fit();
 204   g.ptrs.shrink_to_fit();
 205   g.root_ptrs.shrink_to_fit();
 206   g.root_nodes.shrink_to_fit();
 207   return g;
 208 }
 209
 210 }