diff -r 13588c901957 -r 9cf78a70fa4f src/hotspot/share/jfr/leakprofiler/chains/edgeStore.cpp
--- a/src/hotspot/share/jfr/leakprofiler/chains/edgeStore.cpp	Thu Oct 17 20:27:44 2019 +0100
+++ b/src/hotspot/share/jfr/leakprofiler/chains/edgeStore.cpp	Thu Oct 17 20:53:35 2019 +0100
@@ -1,5 +1,5 @@
 /*
- * 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
@@ -27,37 +27,17 @@
 #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) {}
+StoredEdge::StoredEdge() : Edge() {}
+StoredEdge::StoredEdge(const Edge* parent, const oop* reference) : Edge(parent, reference), _gc_root_id(0), _skip_length(0) {}
 
-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(const Edge& edge) : Edge(edge), _gc_root_id(0), _skip_length(0) {}
 
-void RoutableEdge::operator=(const RoutableEdge& edge) {
-  Edge::operator=(edge);
-  _skip_edge = edge._skip_edge;
-  _skip_length = edge._skip_length;
-  _processed = edge._processed;
-}
+StoredEdge::StoredEdge(const StoredEdge& edge) : Edge(edge), _gc_root_id(edge._gc_root_id), _skip_length(edge._skip_length) {}
 
-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;
+void StoredEdge::operator=(const StoredEdge& edge) {
+  Edge::operator=(edge);
+  _gc_root_id = edge._gc_root_id;
+  _skip_length = edge._skip_length;
 }
 
 traceid EdgeStore::_edge_id_counter = 0;
@@ -69,87 +49,275 @@
 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());
-  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());
-  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 {
-  assert(edge != NULL, "invariant");
-  const Edge* root = EdgeUtils::root(*edge);
-  assert(root != NULL, "invariant");
-  return get_id(root);
-}
-
-void EdgeStore::add_chain(const Edge* chain, size_t length) {
-  assert(chain != NULL, "invariant");
-  assert(length > 0, "invariant");
-
-  size_t bottom_index = length - 1;
-  const size_t top_index = 0;
-
-  const Edge* stored_parent_edge = NULL;
-
-  // 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;
-  }
-
-  // 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);
-  }
-
-  const oop sample_object = stored_parent_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));
 }
 
 bool EdgeStore::is_empty() const {
   return !_edges->has_entries();
 }
 
-size_t EdgeStore::number_of_entries() const {
-  return _edges->cardinality();
-}
-
-void EdgeStore::assign_id(EdgeEntry* entry) {
+void EdgeStore::on_link(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) {
+bool EdgeStore::on_equals(uintptr_t hash, const EdgeEntry* entry) {
   assert(entry != NULL, "invariant");
   assert(entry->hash() == hash, "invariant");
   return true;
 }
+
+void EdgeStore::on_unlink(EdgeEntry* entry) {
+  assert(entry != NULL, "invariant");
+  // nothing
+}
+
+#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");
+  EdgeEntry* const entry = _edges->lookup_only((uintptr_t)reference);
+  return entry != NULL ? entry->literal_addr() : NULL;
+}
+
+StoredEdge* EdgeStore::put(const oop* reference) {
+  assert(reference != NULL, "invariant");
+  const StoredEdge e(NULL, reference);
+  assert(NULL == _edges->lookup_only((uintptr_t)reference), "invariant");
+  EdgeEntry& entry = _edges->put((uintptr_t)reference, e);
+  return entry.literal_addr();
+}
+
+traceid EdgeStore::get_id(const Edge* edge) const {
+  assert(edge != NULL, "invariant");
+  EdgeEntry* const entry = _edges->lookup_only((uintptr_t)edge->reference());
+  assert(entry != NULL, "invariant");
+  return entry->id();
+}
+
+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* const root = EdgeUtils::root(*edge);
+  assert(root != NULL, "invariant");
+  assert(root->parent() == NULL, "invariant");
+  return get_id(root);
+}
+
+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 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;
+  }
+
+  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);
+}
+
+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;
+}
+
+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**>(&current_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;
+}
+
+// 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().to_pointer(), "invariant");
+  sample_object->set_mark(markWord::from_pointer(leak_context_edge));
+  return leak_context_edge;
+}
+
+/*
+ * 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;
+  }
+
+  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, &current, 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, &current, 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, &current, EdgeUtils::root_context);
+  assert(previous != NULL, "invariant");
+  put_chain_epilogue(leak_context_edge, EdgeUtils::root(*previous));
+}
+
+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");
+}
+
+// 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");
+}