text: /*
     +----------------------------------------------------------------------+
     | HipHop for PHP                                                       |
     +----------------------------------------------------------------------+
     | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
     +----------------------------------------------------------------------+
     | This source file is subject to version 3.01 of the PHP license,      |
     | that is bundled with this package in the file LICENSE, and is        |
     | available through the world-wide-web at the following url:           |
     | http://www.php.net/license/3_01.txt                                  |
     | If you did not receive a copy of the PHP license and are unable to   |
     | obtain it through the world-wide-web, please send a note to          |
     | license@php.net so we can mail you a copy immediately.               |
     +----------------------------------------------------------------------+
  */
  #include "hphp/runtime/base/heap-graph.h"
  #include "hphp/runtime/base/heap-algorithms.h"
  #include "hphp/runtime/base/types.h"
  #include "hphp/runtime/base/memory-manager-defs.h"
  #include "hphp/runtime/base/heap-scan.h"
  #include "hphp/runtime/base/request-info.h"
  #include "hphp/runtime/base/container-functions.h"
  #include "hphp/runtime/base/tv-mutate.h"
  #include "hphp/runtime/base/tv-variant.h"
  #include "hphp/runtime/ext/weakref/weakref-data-handle.h"
  #include "hphp/util/alloc.h"
  #include "hphp/util/ptr-map.h"
  
  #include <vector>
  #include <folly/Range.h>
  
  namespace HPHP {
  
  template<class Fn> void FOLLY_DISABLE_ADDRESS_SANITIZER
  conservativeScan(const void* start, size_t len, Fn fn) {
    const uintptr_t M{7}; // word size - 1
    auto s = (const void**)((uintptr_t(start) + M) & ~M); // round up
    auto e = (const void**)((uintptr_t(start) + len) & ~M); // round down
    for (; s < e; s++) {
      // Mask off the upper 16-bits to handle things like
      // DiscriminatedPtr which stores things up there.
      fn(s, (const void*)(uintptr_t(*s) & (-1ULL >> 16)));
    }
  }
  
  namespace {
  
  size_t addPtr(HeapGraph& g, int from, int to, HeapGraph::PtrKind kind,
              ptrdiff_t offset) {
    auto& from_node = g.nodes[from];
    auto& to_node = g.nodes[to];
    auto e = g.ptrs.size();
    g.ptrs.push_back(
      HeapGraph::Ptr{from, to, from_node.first_out, to_node.first_in,
                     (int)offset, kind}
    );
    from_node.first_out = to_node.first_in = e;
    return e;
  }
  
  void addRootNode(HeapGraph& g, const PtrMap<const HeapObject*>& blocks,
                   type_scan::Scanner& scanner,
                   const void* h, size_t size, type_scan::Index ty) {
    auto from = g.nodes.size();
    g.nodes.push_back(
      HeapGraph::Node{h, size, true, ty, -1, -1}
    );
    g.root_nodes.push_back(from);
    scanner.scanByIndex(ty, h, size);
    scanner.finish(
      [&](const void* p, std::size_t size) {
        conservativeScan(p, size, [&](const void** addr, const void* ptr) {
          if (auto r = blocks.region(ptr)) {
            auto to = blocks.index(r);
            auto offset = uintptr_t(addr) - uintptr_t(h);
            auto e = addPtr(g, from, to, HeapGraph::Ambiguous, offset);
            g.root_ptrs.push_back(e);
          }
        });
      },
      [&](const void** addr) {
        if (auto r = blocks.region(*addr)) {
          auto to = blocks.index(r);
          auto offset = uintptr_t(addr) - uintptr_t(h);
          auto e = addPtr(g, from, to, HeapGraph::Counted, offset);
          g.root_ptrs.push_back(e);
        }
      },
      [&](const void* p) {
        auto weak = static_cast<const WeakRefData*>(p);
        if (!weak->isValid()) return;
        auto addr = &weak->pointee.m_data.pobj;
        if (auto r = blocks.region(*addr)) {
          auto to = blocks.index(r);
          // Pointee sits within a shared_ptr internal node, so offset
          // is meaningless here.
          addPtr(g, from, to, HeapGraph::Weak, 0);
        }
      }
    );
  }
  
  } // anon namespace
  
  // Run a DFS over the heap, remember the first pointer id to each
  // reachable node, aka its "parent". The tree formed by the parent
  // edges is a spanning tree for the reachable nodes.
  // Given a node, you can walk the parents towards roots to find out
  // why the node is reachable. parent[k] == -1 for unreachable nodes.
  std::vector<int> makeParentTree(const HeapGraph& g) {
    std::vector<int> parents(g.nodes.size(), -1);
    dfs_ptrs(g, g.root_ptrs, [&](int node, int ptr) {
      parents[node] = ptr;
    });
    return parents;
  }
  
  // parse the heap to find valid objects and initialize metadata, then
  // add edges for every known root pointer and every known obj->obj ptr.
  HeapGraph makeHeapGraph(bool include_free) {
    HeapGraph g;
    PtrMap<const HeapObject*> blocks;
  
    // parse the heap once to create a PtrMap for pointer filtering. Create
    // one node for every parsed block, including NativeData and AsyncFuncFrame
    // blocks. Only include free blocks if requested.
    tl_heap->forEachHeapObject([&](HeapObject* h, size_t alloc_size) {
      if (h->kind() != HeaderKind::Free || include_free) {
        blocks.insert(h, alloc_size); // adds interval [h, h+alloc_size[
      }
    });
    blocks.prepare();
  
    // initialize nodes by iterating over PtrMap's regions
    g.nodes.reserve(blocks.size());
    blocks.iterate([&](const HeapObject* h, size_t size) {
      type_scan::Index ty;
      switch (h->kind()) {
        case HeaderKind::NativeData:
          ty = static_cast<const NativeNode*>(h)->typeIndex();
          break;
        case HeaderKind::Resource:
          ty = static_cast<const ResourceHdr*>(h)->typeIndex();
          break;
        case HeaderKind::SmallMalloc:
        case HeaderKind::BigMalloc:
          ty = static_cast<const MallocNode*>(h)->typeIndex();
          break;
        default:
          ty = type_scan::kIndexUnknown;
          break;
      }
      g.nodes.push_back(
        HeapGraph::Node{h, size, false, ty, -1, -1}
      );
    });
  
    // find root nodes
    type_scan::Scanner scanner;
    iterateRoots([&](const void* h, size_t size, type_scan::Index tyindex) {
      // it's important that we actually scan each root node before
      // returning, since at least one will be the C++ stack, and some
      // nodes will only exist for the duration of the call to this lambda,
      // for example EphemeralPtrWrapper<T>.
      addRootNode(g, blocks, scanner, h, size, tyindex);
    });
  
    // find heap->heap pointers
    for (size_t i = 0, n = g.nodes.size(); i < n; i++) {
      if (g.nodes[i].is_root) continue;
      auto h = g.nodes[i].h;
      scanHeapObject(h, scanner);
      auto from = blocks.index(h);
      assertx(from == i);
      scanner.finish(
        [&](const void* p, std::size_t size) {
          conservativeScan(p, size, [&](const void** addr, const void* ptr) {
            if (auto r = blocks.region(ptr)) {
              auto to = blocks.index(r);
              auto offset = uintptr_t(addr) - uintptr_t(h);
              addPtr(g, from, to, HeapGraph::Ambiguous, offset);
            }
          });
        },
        [&](const void** addr) {
          if (auto r = blocks.region(*addr)) {
            auto to = blocks.index(r);
            auto offset = uintptr_t(addr) - uintptr_t(h);
            addPtr(g, from, to, HeapGraph::Counted, offset);
          }
        },
        [&](const void* p) {
          auto weak = static_cast<const WeakRefData*>(p);
          if (!weak->isValid()) return;
          auto addr = &weak->pointee.m_data.pobj;
          if (auto r = blocks.region(*addr)) {
            auto to = blocks.index(r);
            addPtr(g, from, to, HeapGraph::Weak, 0);
          }
        }
      );
    }
    g.nodes.shrink_to_fit();
    g.ptrs.shrink_to_fit();
    g.root_ptrs.shrink_to_fit();
    g.root_nodes.shrink_to_fit();
    return g;
  }
  
  }
  