1 /*
   2  * Copyright (c) 2014, 2019, 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/edgeStore.hpp"
  27 #include "jfr/leakprofiler/chains/edgeUtils.hpp"
  28 #include "oops/oop.inline.hpp"
  29 
  30 StoredEdge::StoredEdge() : Edge() {}
  31 StoredEdge::StoredEdge(const Edge* parent, const oop* reference) : Edge(parent, reference), _gc_root_id(0), _skip_length(0) {}
  32 
  33 StoredEdge::StoredEdge(const Edge& edge) : Edge(edge), _gc_root_id(0), _skip_length(0) {}
  34 
  35 StoredEdge::StoredEdge(const StoredEdge& edge) : Edge(edge), _gc_root_id(edge._gc_root_id), _skip_length(edge._skip_length) {}
  36 
  37 void StoredEdge::operator=(const StoredEdge& edge) {
  38   Edge::operator=(edge);
  39   _gc_root_id = edge._gc_root_id;
  40   _skip_length = edge._skip_length;
  41 }
  42 
  43 traceid EdgeStore::_edge_id_counter = 0;
  44 
  45 EdgeStore::EdgeStore() : _edges(NULL) {
  46   _edges = new EdgeHashTable(this);
  47 }
  48 
  49 EdgeStore::~EdgeStore() {
  50   assert(_edges != NULL, "invariant");
  51   delete _edges;
  52 }
  53 
  54 bool EdgeStore::is_empty() const {
  55   return !_edges->has_entries();
  56 }
  57 
  58 void EdgeStore::assign_id(EdgeEntry* entry) {
  59   assert(entry != NULL, "invariant");
  60   assert(entry->id() == 0, "invariant");
  61   entry->set_id(++_edge_id_counter);
  62 }
  63 
  64 bool EdgeStore::equals(const Edge& query, uintptr_t hash, const EdgeEntry* entry) {
  65   assert(entry != NULL, "invariant");
  66   assert(entry->hash() == hash, "invariant");
  67   return true;
  68 }
  69 
  70 #ifdef ASSERT
  71 bool EdgeStore::contains(const oop* reference) const {
  72   return get(reference) != NULL;
  73 }
  74 #endif
  75 
  76 StoredEdge* EdgeStore::get(const oop* reference) const {
  77   assert(reference != NULL, "invariant");
  78   const StoredEdge e(NULL, reference);
  79   EdgeEntry* const entry = _edges->lookup_only(e, (uintptr_t)reference);
  80   return entry != NULL ? entry->literal_addr() : NULL;
  81 }
  82 
  83 StoredEdge* EdgeStore::put(const oop* reference) {
  84   assert(reference != NULL, "invariant");
  85   const StoredEdge e(NULL, reference);
  86   assert(NULL == _edges->lookup_only(e, (uintptr_t)reference), "invariant");
  87   EdgeEntry& entry = _edges->put(e, (uintptr_t)reference);
  88   return entry.literal_addr();
  89 }
  90 
  91 traceid EdgeStore::get_id(const Edge* edge) const {
  92   assert(edge != NULL, "invariant");
  93   EdgeEntry* const entry = _edges->lookup_only(*edge, (uintptr_t)edge->reference());
  94   assert(entry != NULL, "invariant");
  95   return entry->id();
  96 }
  97 
  98 traceid EdgeStore::gc_root_id(const Edge* edge) const {
  99   assert(edge != NULL, "invariant");
 100   const traceid gc_root_id = static_cast<const StoredEdge*>(edge)->gc_root_id();
 101   if (gc_root_id != 0) {
 102     return gc_root_id;
 103   }
 104   // not cached
 105   assert(edge != NULL, "invariant");
 106   const Edge* const root = EdgeUtils::root(*edge);
 107   assert(root != NULL, "invariant");
 108   assert(root->parent() == NULL, "invariant");
 109   return get_id(root);
 110 }
 111 
 112 static const Edge* get_skip_ancestor(const Edge** current, size_t distance_to_root, size_t* skip_length) {
 113   assert(distance_to_root >= EdgeUtils::root_context, "invariant");
 114   assert(*skip_length == 0, "invariant");
 115   *skip_length = distance_to_root - (EdgeUtils::root_context - 1);
 116   const Edge* const target = EdgeUtils::ancestor(**current, *skip_length);
 117   assert(target != NULL, "invariant");
 118   assert(target->distance_to_root() + 1 == EdgeUtils::root_context, "invariant");
 119   return target;
 120 }
 121 
 122 bool EdgeStore::put_skip_edge(StoredEdge** previous, const Edge** current, size_t distance_to_root) {
 123   assert(*previous != NULL, "invariant");
 124   assert((*previous)->parent() == NULL, "invariant");
 125   assert(*current != NULL, "invariant");
 126   assert((*current)->distance_to_root() == distance_to_root, "invariant");
 127 
 128   if (distance_to_root < EdgeUtils::root_context) {
 129     // nothing to skip
 130     return false;
 131   }
 132 
 133   size_t skip_length = 0;
 134   const Edge* const skip_ancestor = get_skip_ancestor(current, distance_to_root, &skip_length);
 135   assert(skip_ancestor != NULL, "invariant");
 136   (*previous)->set_skip_length(skip_length);
 137 
 138   // lookup target
 139   StoredEdge* stored_target = get(skip_ancestor->reference());
 140   if (stored_target != NULL) {
 141     (*previous)->set_parent(stored_target);
 142     // linked to existing, complete
 143     return true;
 144   }
 145 
 146   assert(stored_target == NULL, "invariant");
 147   stored_target = put(skip_ancestor->reference());
 148   assert(stored_target != NULL, "invariant");
 149   (*previous)->set_parent(stored_target);
 150   *previous = stored_target;
 151   *current = skip_ancestor->parent();
 152   return false;
 153 }
 154 
 155 static void link_edge(const StoredEdge* current_stored, StoredEdge** previous) {
 156   assert(current_stored != NULL, "invariant");
 157   assert(*previous != NULL, "invariant");
 158   assert((*previous)->parent() == NULL, "invariant");
 159   (*previous)->set_parent(current_stored);
 160 }
 161 
 162 static const StoredEdge* find_closest_skip_edge(const StoredEdge* edge, size_t* distance) {
 163   assert(edge != NULL, "invariant");
 164   assert(distance != NULL, "invariant");
 165   const StoredEdge* current = edge;
 166   *distance = 1;
 167   while (current != NULL && !current->is_skip_edge()) {
 168     ++(*distance);
 169     current = current->parent();
 170   }
 171   return current;
 172 }
 173 
 174 void EdgeStore::link_with_existing_chain(const StoredEdge* current_stored, StoredEdge** previous, size_t previous_length) {
 175   assert(current_stored != NULL, "invariant");
 176   assert((*previous)->parent() == NULL, "invariant");
 177   size_t distance_to_skip_edge; // including the skip edge itself
 178   const StoredEdge* const closest_skip_edge = find_closest_skip_edge(current_stored, &distance_to_skip_edge);
 179   if (closest_skip_edge == NULL) {
 180     // no found skip edge implies root
 181     if (distance_to_skip_edge + previous_length <= EdgeUtils::max_ref_chain_depth) {
 182       link_edge(current_stored, previous);
 183       return;
 184     }
 185     assert(current_stored->distance_to_root() == distance_to_skip_edge - 2, "invariant");
 186     put_skip_edge(previous, reinterpret_cast<const Edge**>(&current_stored), distance_to_skip_edge - 2);
 187     return;
 188   }
 189   assert(closest_skip_edge->is_skip_edge(), "invariant");
 190   if (distance_to_skip_edge + previous_length <= EdgeUtils::leak_context) {
 191     link_edge(current_stored, previous);
 192     return;
 193   }
 194   // create a new skip edge with derived information from closest skip edge
 195   (*previous)->set_skip_length(distance_to_skip_edge + closest_skip_edge->skip_length());
 196   (*previous)->set_parent(closest_skip_edge->parent());
 197 }
 198 
 199 StoredEdge* EdgeStore::link_new_edge(StoredEdge** previous, const Edge** current) {
 200   assert(*previous != NULL, "invariant");
 201   assert((*previous)->parent() == NULL, "invariant");
 202   assert(*current != NULL, "invariant");
 203   assert(!contains((*current)->reference()), "invariant");
 204   StoredEdge* const stored_edge = put((*current)->reference());
 205   assert(stored_edge != NULL, "invariant");
 206   link_edge(stored_edge, previous);
 207   return stored_edge;
 208 }
 209 
 210 bool EdgeStore::put_edges(StoredEdge** previous, const Edge** current, size_t limit) {
 211   assert(*previous != NULL, "invariant");
 212   assert(*current != NULL, "invariant");
 213   size_t depth = 1;
 214   while (*current != NULL && depth < limit) {
 215     StoredEdge* stored_edge = get((*current)->reference());
 216     if (stored_edge != NULL) {
 217       link_with_existing_chain(stored_edge, previous, depth);
 218       return true;
 219     }
 220     stored_edge = link_new_edge(previous, current);
 221     assert((*previous)->parent() != NULL, "invariant");
 222     *previous = stored_edge;
 223     *current = (*current)->parent();
 224     ++depth;
 225   }
 226   return NULL == *current;
 227 }
 228 
 229 // Install the immediate edge into the mark word of the leak candidate object
 230 StoredEdge* EdgeStore::associate_leak_context_with_candidate(const Edge* edge) {
 231   assert(edge != NULL, "invariant");
 232   assert(!contains(edge->reference()), "invariant");
 233   StoredEdge* const leak_context_edge = put(edge->reference());
 234   oop sample_object = edge->pointee();
 235   assert(sample_object != NULL, "invariant");
 236   assert(NULL == sample_object->mark(), "invariant");
 237   sample_object->set_mark(markOop(leak_context_edge));
 238   return leak_context_edge;
 239 }
 240 
 241 /*
 242  * The purpose of put_chain() is to reify the edge sequence
 243  * discovered during heap traversal with a normalized logical copy.
 244  * This copy consist of two sub-sequences and a connecting link (skip edge).
 245  *
 246  * "current" can be thought of as the cursor (search) edge, it is not in the edge store.
 247  * "previous" is always an edge in the edge store.
 248  * The leak context edge is the edge adjacent to the leak candidate object, always an edge in the edge store.
 249  */
 250 void EdgeStore::put_chain(const Edge* chain, size_t length) {
 251   assert(chain != NULL, "invariant");
 252   assert(chain->distance_to_root() + 1 == length, "invariant");
 253   StoredEdge* const leak_context_edge = associate_leak_context_with_candidate(chain);
 254   assert(leak_context_edge != NULL, "invariant");
 255   assert(leak_context_edge->parent() == NULL, "invariant");
 256 
 257   if (1 == length) {
 258     return;
 259   }
 260 
 261   const Edge* current = chain->parent();
 262   assert(current != NULL, "invariant");
 263   StoredEdge* previous = leak_context_edge;
 264 
 265   // a leak context is the sequence of (limited) edges reachable from the leak candidate
 266   if (put_edges(&previous, &current, EdgeUtils::leak_context)) {
 267     // complete
 268     assert(previous != NULL, "invariant");
 269     put_chain_epilogue(leak_context_edge, EdgeUtils::root(*previous));
 270     return;
 271   }
 272 
 273   const size_t distance_to_root = length > EdgeUtils::leak_context ? length - 1 - EdgeUtils::leak_context : length - 1;
 274   assert(current->distance_to_root() == distance_to_root, "invariant");
 275 
 276   // a skip edge is the logical link
 277   // connecting the leak context sequence with the root context sequence
 278   if (put_skip_edge(&previous, &current, distance_to_root)) {
 279     // complete
 280     assert(previous != NULL, "invariant");
 281     assert(previous->is_skip_edge(), "invariant");
 282     assert(previous->parent() != NULL, "invariant");
 283     put_chain_epilogue(leak_context_edge, EdgeUtils::root(*previous->parent()));
 284     return;
 285   }
 286 
 287   assert(current->distance_to_root() < EdgeUtils::root_context, "invariant");
 288 
 289   // a root context is the sequence of (limited) edges reachable from the root
 290   put_edges(&previous, &current, EdgeUtils::root_context);
 291   assert(previous != NULL, "invariant");
 292   put_chain_epilogue(leak_context_edge, EdgeUtils::root(*previous));
 293 }
 294 
 295 void EdgeStore::put_chain_epilogue(StoredEdge* leak_context_edge, const Edge* root) const {
 296   assert(leak_context_edge != NULL, "invariant");
 297   assert(root != NULL, "invariant");
 298   store_gc_root_id_in_leak_context_edge(leak_context_edge, root);
 299   assert(leak_context_edge->distance_to_root() + 1 <= EdgeUtils::max_ref_chain_depth, "invariant");
 300 }
 301 
 302 // To avoid another traversal to resolve the root edge id later,
 303 // cache it in the immediate leak context edge for fast retrieval.
 304 void EdgeStore::store_gc_root_id_in_leak_context_edge(StoredEdge* leak_context_edge, const Edge* root) const {
 305   assert(leak_context_edge != NULL, "invariant");
 306   assert(leak_context_edge->gc_root_id() == 0, "invariant");
 307   assert(root != NULL, "invariant");
 308   assert(root->parent() == NULL, "invariant");
 309   assert(root->distance_to_root() == 0, "invariant");
 310   const StoredEdge* const stored_root = static_cast<const StoredEdge*>(root);
 311   traceid root_id = stored_root->gc_root_id();
 312   if (root_id == 0) {
 313     root_id = get_id(root);
 314     stored_root->set_gc_root_id(root_id);
 315   }
 316   assert(root_id != 0, "invariant");
 317   leak_context_edge->set_gc_root_id(root_id);
 318   assert(leak_context_edge->gc_root_id() == stored_root->gc_root_id(), "invariant");
 319 }