1 /*
   2  * Copyright (c) 2014, 2018, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 #include "precompiled.hpp"
  26 #include "jfr/leakprofiler/chains/dfsClosure.hpp"
  27 #include "jfr/leakprofiler/chains/edge.hpp"
  28 #include "jfr/leakprofiler/chains/edgeStore.hpp"
  29 #include "jfr/leakprofiler/utilities/granularTimer.hpp"
  30 #include "jfr/leakprofiler/chains/bitset.hpp"
  31 #include "jfr/leakprofiler/utilities/unifiedOop.hpp"
  32 #include "jfr/leakprofiler/utilities/rootType.hpp"
  33 #include "jfr/leakprofiler/chains/rootSetClosure.hpp"
  34 #include "memory/resourceArea.hpp"
  35 #include "oops/access.inline.hpp"
  36 #include "utilities/align.hpp"
  37 
  38 // max dfs depth should not exceed size of stack
  39 static const size_t max_dfs_depth = 5000;
  40 
  41 EdgeStore* DFSClosure::_edge_store = NULL;
  42 BitSet* DFSClosure::_mark_bits = NULL;
  43 const Edge* DFSClosure::_start_edge = NULL;
  44 size_t DFSClosure::_max_depth = max_dfs_depth;
  45 bool DFSClosure::_ignore_root_set = false;
  46 
  47 DFSClosure::DFSClosure() :
  48   _parent(NULL),
  49   _reference(NULL),
  50   _depth(0) {
  51 }
  52 
  53 DFSClosure::DFSClosure(DFSClosure* parent, size_t depth) :
  54   _parent(parent),
  55   _reference(NULL),
  56   _depth(depth) {
  57 }
  58 
  59 void DFSClosure::find_leaks_from_edge(EdgeStore* edge_store,
  60                                       BitSet* mark_bits,
  61                                       const Edge* start_edge) {
  62   assert(edge_store != NULL, "invariant");
  63   assert(mark_bits != NULL," invariant");
  64   assert(start_edge != NULL, "invariant");
  65 
  66   _edge_store = edge_store;
  67   _mark_bits = mark_bits;
  68   _start_edge = start_edge;
  69   _ignore_root_set = false;
  70   assert(_max_depth == max_dfs_depth, "invariant");
  71 
  72   // Depth-first search, starting from a BFS egde
  73   DFSClosure dfs;
  74   start_edge->pointee()->oop_iterate(&dfs);
  75 }
  76 
  77 void DFSClosure::find_leaks_from_root_set(EdgeStore* edge_store,
  78                                           BitSet* mark_bits) {
  79   assert(edge_store != NULL, "invariant");
  80   assert(mark_bits != NULL, "invariant");
  81 
  82   _edge_store = edge_store;
  83   _mark_bits = mark_bits;
  84   _start_edge = NULL;
  85 
  86   // Mark root set, to avoid going sideways
  87   _max_depth = 1;
  88   _ignore_root_set = false;
  89   DFSClosure dfs1;
  90   RootSetClosure::process_roots(&dfs1);
  91 
  92   // Depth-first search
  93   _max_depth = max_dfs_depth;
  94   _ignore_root_set = true;
  95   assert(_start_edge == NULL, "invariant");
  96   DFSClosure dfs2;
  97   RootSetClosure::process_roots(&dfs2);
  98 }
  99 
 100 void DFSClosure::closure_impl(const oop* reference, const oop pointee) {
 101   assert(pointee != NULL, "invariant");
 102   assert(reference != NULL, "invariant");
 103 
 104   if (GranularTimer::is_finished()) {
 105      return;
 106   }
 107   if (_depth == 0 && _ignore_root_set) {
 108     // Root set is already marked, but we want
 109     // to continue, so skip is_marked check.
 110     assert(_mark_bits->is_marked(pointee), "invariant");
 111   } else {
 112     if (_mark_bits->is_marked(pointee)) {
 113       return;
 114     }
 115   }
 116 
 117   _reference = reference;
 118   _mark_bits->mark_obj(pointee);
 119   assert(_mark_bits->is_marked(pointee), "invariant");
 120 
 121   // is the pointee a sample object?
 122   if (NULL == pointee->mark()) {
 123     add_chain();
 124   }
 125 
 126   assert(_max_depth >= 1, "invariant");
 127   if (_depth < _max_depth - 1) {
 128     DFSClosure next_level(this, _depth + 1);
 129     pointee->oop_iterate(&next_level);
 130   }
 131 }
 132 
 133 void DFSClosure::add_chain() {
 134   const size_t length = _start_edge == NULL ? _depth + 1 :
 135                         _start_edge->distance_to_root() + 1 + _depth + 1;
 136 
 137   ResourceMark rm;
 138   Edge* const chain = NEW_RESOURCE_ARRAY(Edge, length);
 139   size_t idx = 0;
 140 
 141   // aggregate from depth-first search
 142   const DFSClosure* c = this;
 143   while (c != NULL) {
 144     chain[idx++] = Edge(NULL, c->reference());
 145     c = c->parent();
 146   }
 147 
 148   assert(idx == _depth + 1, "invariant");
 149 
 150   // aggregate from breadth-first search
 151   const Edge* current = _start_edge;
 152   while (current != NULL) {
 153     chain[idx++] = Edge(NULL, current->reference());
 154     current = current->parent();
 155   }
 156   assert(idx == length, "invariant");
 157   _edge_store->add_chain(chain, length);
 158 }
 159 
 160 void DFSClosure::do_oop(oop* ref) {
 161   assert(ref != NULL, "invariant");
 162   assert(is_aligned(ref, HeapWordSize), "invariant");
 163   const oop pointee = *ref;
 164   if (pointee != NULL) {
 165     closure_impl(ref, pointee);
 166   }
 167 }
 168 
 169 void DFSClosure::do_oop(narrowOop* ref) {
 170   assert(ref != NULL, "invariant");
 171   assert(is_aligned(ref, sizeof(narrowOop)), "invariant");
 172   const oop pointee = RawAccess<>::oop_load(ref);
 173   if (pointee != NULL) {
 174     closure_impl(UnifiedOop::encode(ref), pointee);
 175   }
 176 }