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