< prev index next >
src/share/vm/jfr/leakprofiler/chains/edgeStore.cpp
Print this page
rev 9055 : 8214542: JFR: Old Object Sample event slow on a deep heap in debug builds
Reviewed-by: egahlin, rwestberg
@@ -1,7 +1,7 @@
/*
- * Copyright (c) 2014, 2018, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2014, 2019, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation.
@@ -25,41 +25,21 @@
#include "precompiled.hpp"
#include "jfr/leakprofiler/chains/edgeStore.hpp"
#include "jfr/leakprofiler/chains/edgeUtils.hpp"
#include "oops/oop.inline.hpp"
-RoutableEdge::RoutableEdge() : Edge() {}
-RoutableEdge::RoutableEdge(const Edge* parent, const oop* reference) : Edge(parent, reference),
- _skip_edge(NULL),
- _skip_length(0),
- _processed(false) {}
-
-RoutableEdge::RoutableEdge(const Edge& edge) : Edge(edge),
- _skip_edge(NULL),
- _skip_length(0),
- _processed(false) {}
-
-RoutableEdge::RoutableEdge(const RoutableEdge& edge) : Edge(edge),
- _skip_edge(edge._skip_edge),
- _skip_length(edge._skip_length),
- _processed(edge._processed) {}
+StoredEdge::StoredEdge() : Edge() {}
+StoredEdge::StoredEdge(const Edge* parent, const oop* reference) : Edge(parent, reference), _gc_root_id(0), _skip_length(0) {}
-void RoutableEdge::operator=(const RoutableEdge& edge) {
+StoredEdge::StoredEdge(const Edge& edge) : Edge(edge), _gc_root_id(0), _skip_length(0) {}
+
+StoredEdge::StoredEdge(const StoredEdge& edge) : Edge(edge), _gc_root_id(edge._gc_root_id), _skip_length(edge._skip_length) {}
+
+void StoredEdge::operator=(const StoredEdge& edge) {
Edge::operator=(edge);
- _skip_edge = edge._skip_edge;
+ _gc_root_id = edge._gc_root_id;
_skip_length = edge._skip_length;
- _processed = edge._processed;
-}
-
-size_t RoutableEdge::logical_distance_to_root() const {
- size_t depth = 0;
- const RoutableEdge* current = logical_parent();
- while (current != NULL) {
- depth++;
- current = current->logical_parent();
- }
- return depth;
}
traceid EdgeStore::_edge_id_counter = 0;
EdgeStore::EdgeStore() : _edges(NULL) {
@@ -67,89 +47,273 @@
}
EdgeStore::~EdgeStore() {
assert(_edges != NULL, "invariant");
delete _edges;
- _edges = NULL;
}
-const Edge* EdgeStore::get_edge(const Edge* edge) const {
- assert(edge != NULL, "invariant");
- EdgeEntry* const entry = _edges->lookup_only(*edge, (uintptr_t)edge->reference());
+bool EdgeStore::is_empty() const {
+ return !_edges->has_entries();
+}
+
+void EdgeStore::assign_id(EdgeEntry* entry) {
+ assert(entry != NULL, "invariant");
+ assert(entry->id() == 0, "invariant");
+ entry->set_id(++_edge_id_counter);
+}
+
+bool EdgeStore::equals(const Edge& query, uintptr_t hash, const EdgeEntry* entry) {
+ assert(entry != NULL, "invariant");
+ assert(entry->hash() == hash, "invariant");
+ return true;
+}
+
+#ifdef ASSERT
+bool EdgeStore::contains(const oop* reference) const {
+ return get(reference) != NULL;
+}
+#endif
+
+StoredEdge* EdgeStore::get(const oop* reference) const {
+ assert(reference != NULL, "invariant");
+ const StoredEdge e(NULL, reference);
+ EdgeEntry* const entry = _edges->lookup_only(e, (uintptr_t)reference);
return entry != NULL ? entry->literal_addr() : NULL;
}
-const Edge* EdgeStore::put(const Edge* edge) {
- assert(edge != NULL, "invariant");
- const RoutableEdge e = *edge;
- assert(NULL == _edges->lookup_only(e, (uintptr_t)e.reference()), "invariant");
- EdgeEntry& entry = _edges->put(e, (uintptr_t)e.reference());
+StoredEdge* EdgeStore::put(const oop* reference) {
+ assert(reference != NULL, "invariant");
+ const StoredEdge e(NULL, reference);
+ assert(NULL == _edges->lookup_only(e, (uintptr_t)reference), "invariant");
+ EdgeEntry& entry = _edges->put(e, (uintptr_t)reference);
return entry.literal_addr();
}
traceid EdgeStore::get_id(const Edge* edge) const {
assert(edge != NULL, "invariant");
EdgeEntry* const entry = _edges->lookup_only(*edge, (uintptr_t)edge->reference());
assert(entry != NULL, "invariant");
return entry->id();
}
-traceid EdgeStore::get_root_id(const Edge* edge) const {
+traceid EdgeStore::gc_root_id(const Edge* edge) const {
+ assert(edge != NULL, "invariant");
+ const traceid gc_root_id = static_cast<const StoredEdge*>(edge)->gc_root_id();
+ if (gc_root_id != 0) {
+ return gc_root_id;
+ }
+ // not cached
assert(edge != NULL, "invariant");
- const Edge* root = EdgeUtils::root(*edge);
+ const Edge* const root = EdgeUtils::root(*edge);
assert(root != NULL, "invariant");
+ assert(root->parent() == NULL, "invariant");
return get_id(root);
}
-void EdgeStore::add_chain(const Edge* chain, size_t length) {
- assert(chain != NULL, "invariant");
- assert(length > 0, "invariant");
+static const Edge* get_skip_ancestor(const Edge** current, size_t distance_to_root, size_t* skip_length) {
+ assert(distance_to_root >= EdgeUtils::root_context, "invariant");
+ assert(*skip_length == 0, "invariant");
+ *skip_length = distance_to_root - (EdgeUtils::root_context - 1);
+ const Edge* const target = EdgeUtils::ancestor(**current, *skip_length);
+ assert(target != NULL, "invariant");
+ assert(target->distance_to_root() + 1 == EdgeUtils::root_context, "invariant");
+ return target;
+}
+
+bool EdgeStore::put_skip_edge(StoredEdge** previous, const Edge** current, size_t distance_to_root) {
+ assert(*previous != NULL, "invariant");
+ assert((*previous)->parent() == NULL, "invariant");
+ assert(*current != NULL, "invariant");
+ assert((*current)->distance_to_root() == distance_to_root, "invariant");
+
+ if (distance_to_root < EdgeUtils::root_context) {
+ // nothing to skip
+ return false;
+ }
- size_t bottom_index = length - 1;
- const size_t top_index = 0;
+ size_t skip_length = 0;
+ const Edge* const skip_ancestor = get_skip_ancestor(current, distance_to_root, &skip_length);
+ assert(skip_ancestor != NULL, "invariant");
+ (*previous)->set_skip_length(skip_length);
+
+ // lookup target
+ StoredEdge* stored_target = get(skip_ancestor->reference());
+ if (stored_target != NULL) {
+ (*previous)->set_parent(stored_target);
+ // linked to existing, complete
+ return true;
+ }
- const Edge* stored_parent_edge = NULL;
+ assert(stored_target == NULL, "invariant");
+ stored_target = put(skip_ancestor->reference());
+ assert(stored_target != NULL, "invariant");
+ (*previous)->set_parent(stored_target);
+ *previous = stored_target;
+ *current = skip_ancestor->parent();
+ return false;
+}
+
+static void link_edge(const StoredEdge* current_stored, StoredEdge** previous) {
+ assert(current_stored != NULL, "invariant");
+ assert(*previous != NULL, "invariant");
+ assert((*previous)->parent() == NULL, "invariant");
+ (*previous)->set_parent(current_stored);
+}
- // determine level of shared ancestry
- for (; bottom_index > top_index; --bottom_index) {
- const Edge* stored_edge = get_edge(&chain[bottom_index]);
- if (stored_edge != NULL) {
- stored_parent_edge = stored_edge;
- continue;
- }
- break;
+static const StoredEdge* find_closest_skip_edge(const StoredEdge* edge, size_t* distance) {
+ assert(edge != NULL, "invariant");
+ assert(distance != NULL, "invariant");
+ const StoredEdge* current = edge;
+ *distance = 1;
+ while (current != NULL && !current->is_skip_edge()) {
+ ++(*distance);
+ current = current->parent();
}
+ return current;
+}
- // insertion of new Edges
- for (int i = (int)bottom_index; i >= (int)top_index; --i) {
- Edge edge(stored_parent_edge, chain[i].reference());
- stored_parent_edge = put(&edge);
+void EdgeStore::link_with_existing_chain(const StoredEdge* current_stored, StoredEdge** previous, size_t previous_length) {
+ assert(current_stored != NULL, "invariant");
+ assert((*previous)->parent() == NULL, "invariant");
+ size_t distance_to_skip_edge; // including the skip edge itself
+ const StoredEdge* const closest_skip_edge = find_closest_skip_edge(current_stored, &distance_to_skip_edge);
+ if (closest_skip_edge == NULL) {
+ // no found skip edge implies root
+ if (distance_to_skip_edge + previous_length <= EdgeUtils::max_ref_chain_depth) {
+ link_edge(current_stored, previous);
+ return;
}
+ assert(current_stored->distance_to_root() == distance_to_skip_edge - 2, "invariant");
+ put_skip_edge(previous, reinterpret_cast<const Edge**>(¤t_stored), distance_to_skip_edge - 2);
+ return;
+ }
+ assert(closest_skip_edge->is_skip_edge(), "invariant");
+ if (distance_to_skip_edge + previous_length <= EdgeUtils::leak_context) {
+ link_edge(current_stored, previous);
+ return;
+ }
+ // create a new skip edge with derived information from closest skip edge
+ (*previous)->set_skip_length(distance_to_skip_edge + closest_skip_edge->skip_length());
+ (*previous)->set_parent(closest_skip_edge->parent());
+}
+
+StoredEdge* EdgeStore::link_new_edge(StoredEdge** previous, const Edge** current) {
+ assert(*previous != NULL, "invariant");
+ assert((*previous)->parent() == NULL, "invariant");
+ assert(*current != NULL, "invariant");
+ assert(!contains((*current)->reference()), "invariant");
+ StoredEdge* const stored_edge = put((*current)->reference());
+ assert(stored_edge != NULL, "invariant");
+ link_edge(stored_edge, previous);
+ return stored_edge;
+}
+
+bool EdgeStore::put_edges(StoredEdge** previous, const Edge** current, size_t limit) {
+ assert(*previous != NULL, "invariant");
+ assert(*current != NULL, "invariant");
+ size_t depth = 1;
+ while (*current != NULL && depth < limit) {
+ StoredEdge* stored_edge = get((*current)->reference());
+ if (stored_edge != NULL) {
+ link_with_existing_chain(stored_edge, previous, depth);
+ return true;
+ }
+ stored_edge = link_new_edge(previous, current);
+ assert((*previous)->parent() != NULL, "invariant");
+ *previous = stored_edge;
+ *current = (*current)->parent();
+ ++depth;
+ }
+ return NULL == *current;
+}
- const oop sample_object = stored_parent_edge->pointee();
+// Install the immediate edge into the mark word of the leak candidate object
+StoredEdge* EdgeStore::associate_leak_context_with_candidate(const Edge* edge) {
+ assert(edge != NULL, "invariant");
+ assert(!contains(edge->reference()), "invariant");
+ StoredEdge* const leak_context_edge = put(edge->reference());
+ oop sample_object = edge->pointee();
assert(sample_object != NULL, "invariant");
assert(NULL == sample_object->mark(), "invariant");
-
- // Install the "top" edge of the chain into the sample object mark oop.
- // This associates the sample object with its navigable reference chain.
- sample_object->set_mark(markOop(stored_parent_edge));
+ sample_object->set_mark(markOop(leak_context_edge));
+ return leak_context_edge;
}
-bool EdgeStore::is_empty() const {
- return !_edges->has_entries();
-}
+/*
+ * The purpose of put_chain() is to reify the edge sequence
+ * discovered during heap traversal with a normalized logical copy.
+ * This copy consist of two sub-sequences and a connecting link (skip edge).
+ *
+ * "current" can be thought of as the cursor (search) edge, it is not in the edge store.
+ * "previous" is always an edge in the edge store.
+ * The leak context edge is the edge adjacent to the leak candidate object, always an edge in the edge store.
+ */
+void EdgeStore::put_chain(const Edge* chain, size_t length) {
+ assert(chain != NULL, "invariant");
+ assert(chain->distance_to_root() + 1 == length, "invariant");
+ StoredEdge* const leak_context_edge = associate_leak_context_with_candidate(chain);
+ assert(leak_context_edge != NULL, "invariant");
+ assert(leak_context_edge->parent() == NULL, "invariant");
+
+ if (1 == length) {
+ return;
+ }
-size_t EdgeStore::number_of_entries() const {
- return _edges->cardinality();
+ const Edge* current = chain->parent();
+ assert(current != NULL, "invariant");
+ StoredEdge* previous = leak_context_edge;
+
+ // a leak context is the sequence of (limited) edges reachable from the leak candidate
+ if (put_edges(&previous, ¤t, EdgeUtils::leak_context)) {
+ // complete
+ assert(previous != NULL, "invariant");
+ put_chain_epilogue(leak_context_edge, EdgeUtils::root(*previous));
+ return;
+ }
+
+ const size_t distance_to_root = length > EdgeUtils::leak_context ? length - 1 - EdgeUtils::leak_context : length - 1;
+ assert(current->distance_to_root() == distance_to_root, "invariant");
+
+ // a skip edge is the logical link
+ // connecting the leak context sequence with the root context sequence
+ if (put_skip_edge(&previous, ¤t, distance_to_root)) {
+ // complete
+ assert(previous != NULL, "invariant");
+ assert(previous->is_skip_edge(), "invariant");
+ assert(previous->parent() != NULL, "invariant");
+ put_chain_epilogue(leak_context_edge, EdgeUtils::root(*previous->parent()));
+ return;
+ }
+
+ assert(current->distance_to_root() < EdgeUtils::root_context, "invariant");
+
+ // a root context is the sequence of (limited) edges reachable from the root
+ put_edges(&previous, ¤t, EdgeUtils::root_context);
+ assert(previous != NULL, "invariant");
+ put_chain_epilogue(leak_context_edge, EdgeUtils::root(*previous));
}
-void EdgeStore::assign_id(EdgeEntry* entry) {
- assert(entry != NULL, "invariant");
- assert(entry->id() == 0, "invariant");
- entry->set_id(++_edge_id_counter);
+void EdgeStore::put_chain_epilogue(StoredEdge* leak_context_edge, const Edge* root) const {
+ assert(leak_context_edge != NULL, "invariant");
+ assert(root != NULL, "invariant");
+ store_gc_root_id_in_leak_context_edge(leak_context_edge, root);
+ assert(leak_context_edge->distance_to_root() + 1 <= EdgeUtils::max_ref_chain_depth, "invariant");
}
-bool EdgeStore::equals(const Edge& query, uintptr_t hash, const EdgeEntry* entry) {
- assert(entry != NULL, "invariant");
- assert(entry->hash() == hash, "invariant");
- return true;
+// To avoid another traversal to resolve the root edge id later,
+// cache it in the immediate leak context edge for fast retrieval.
+void EdgeStore::store_gc_root_id_in_leak_context_edge(StoredEdge* leak_context_edge, const Edge* root) const {
+ assert(leak_context_edge != NULL, "invariant");
+ assert(leak_context_edge->gc_root_id() == 0, "invariant");
+ assert(root != NULL, "invariant");
+ assert(root->parent() == NULL, "invariant");
+ assert(root->distance_to_root() == 0, "invariant");
+ const StoredEdge* const stored_root = static_cast<const StoredEdge*>(root);
+ traceid root_id = stored_root->gc_root_id();
+ if (root_id == 0) {
+ root_id = get_id(root);
+ stored_root->set_gc_root_id(root_id);
+ }
+ assert(root_id != 0, "invariant");
+ leak_context_edge->set_gc_root_id(root_id);
+ assert(leak_context_edge->gc_root_id() == stored_root->gc_root_id(), "invariant");
}
< prev index next >