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/edgeStore.hpp"
  27 #include "jfr/leakprofiler/chains/edgeUtils.hpp"
  28 #include "oops/oop.inline.hpp"
  29 
  30 RoutableEdge::RoutableEdge() : Edge() {}
  31 RoutableEdge::RoutableEdge(const Edge* parent, const oop* reference) : Edge(parent, reference),
  32                                                                        _skip_edge(NULL),
  33                                                                        _skip_length(0),
  34                                                                        _processed(false) {}
  35 
  36 RoutableEdge::RoutableEdge(const Edge& edge) : Edge(edge),
  37                                                _skip_edge(NULL),
  38                                                _skip_length(0),
  39                                                _processed(false) {}
  40 
  41 RoutableEdge::RoutableEdge(const RoutableEdge& edge) : Edge(edge),
  42                                                       _skip_edge(edge._skip_edge),
  43                                                       _skip_length(edge._skip_length),
  44                                                       _processed(edge._processed) {}
  45 
  46 void RoutableEdge::operator=(const RoutableEdge& edge) {
  47   Edge::operator=(edge);
  48   _skip_edge = edge._skip_edge;
  49   _skip_length = edge._skip_length;
  50   _processed = edge._processed;
  51 }
  52 
  53 size_t RoutableEdge::logical_distance_to_root() const {
  54   size_t depth = 0;
  55   const RoutableEdge* current = logical_parent();
  56   while (current != NULL) {
  57     depth++;
  58     current = current->logical_parent();
  59   }
  60   return depth;
  61 }
  62 
  63 traceid EdgeStore::_edge_id_counter = 0;
  64 
  65 EdgeStore::EdgeStore() : _edges(NULL) {
  66   _edges = new EdgeHashTable(this);
  67 }
  68 
  69 EdgeStore::~EdgeStore() {
  70   assert(_edges != NULL, "invariant");
  71   delete _edges;
  72   _edges = NULL;
  73 }
  74 
  75 const Edge* EdgeStore::get_edge(const Edge* edge) const {
  76   assert(edge != NULL, "invariant");
  77   EdgeEntry* const entry = _edges->lookup_only(*edge, (uintptr_t)edge->reference());
  78   return entry != NULL ? entry->literal_addr() : NULL;
  79 }
  80 
  81 const Edge* EdgeStore::put(const Edge* edge) {
  82   assert(edge != NULL, "invariant");
  83   const RoutableEdge e = *edge;
  84   assert(NULL == _edges->lookup_only(e, (uintptr_t)e.reference()), "invariant");
  85   EdgeEntry& entry = _edges->put(e, (uintptr_t)e.reference());
  86   return entry.literal_addr();
  87 }
  88 
  89 traceid EdgeStore::get_id(const Edge* edge) const {
  90   assert(edge != NULL, "invariant");
  91   EdgeEntry* const entry = _edges->lookup_only(*edge, (uintptr_t)edge->reference());
  92   assert(entry != NULL, "invariant");
  93   return entry->id();
  94 }
  95 
  96 traceid EdgeStore::get_root_id(const Edge* edge) const {
  97   assert(edge != NULL, "invariant");
  98   const Edge* root = EdgeUtils::root(*edge);
  99   assert(root != NULL, "invariant");
 100   return get_id(root);
 101 }
 102 
 103 void EdgeStore::add_chain(const Edge* chain, size_t length) {
 104   assert(chain != NULL, "invariant");
 105   assert(length > 0, "invariant");
 106 
 107   size_t bottom_index = length - 1;
 108   const size_t top_index = 0;
 109 
 110   const Edge* stored_parent_edge = NULL;
 111 
 112   // determine level of shared ancestry
 113   for (; bottom_index > top_index; --bottom_index) {
 114     const Edge* stored_edge = get_edge(&chain[bottom_index]);
 115     if (stored_edge != NULL) {
 116       stored_parent_edge = stored_edge;
 117       continue;
 118     }
 119     break;
 120   }
 121 
 122   // insertion of new Edges
 123   for (int i = (int)bottom_index; i >= (int)top_index; --i) {
 124     Edge edge(stored_parent_edge, chain[i].reference());
 125     stored_parent_edge = put(&edge);
 126   }
 127 
 128   const oop sample_object = stored_parent_edge->pointee();
 129   assert(sample_object != NULL, "invariant");
 130   assert(NULL == sample_object->mark(), "invariant");
 131 
 132   // Install the "top" edge of the chain into the sample object mark oop.
 133   // This associates the sample object with its navigable reference chain.
 134   sample_object->set_mark(markOop(stored_parent_edge));
 135 }
 136 
 137 bool EdgeStore::is_empty() const {
 138   return !_edges->has_entries();
 139 }
 140 
 141 size_t EdgeStore::number_of_entries() const {
 142   return _edges->cardinality();
 143 }
 144 
 145 void EdgeStore::assign_id(EdgeEntry* entry) {
 146   assert(entry != NULL, "invariant");
 147   assert(entry->id() == 0, "invariant");
 148   entry->set_id(++_edge_id_counter);
 149 }
 150 
 151 bool EdgeStore::equals(const Edge& query, uintptr_t hash, const EdgeEntry* entry) {
 152   assert(entry != NULL, "invariant");
 153   assert(entry->hash() == hash, "invariant");
 154   return true;
 155 }