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**>(¤t_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(0 == sample_object->mark().value(), "invariant"); 237 sample_object->set_mark(markWord::from_pointer(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, ¤t, 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, ¤t, 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, ¤t, 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 }