168 

   169 #ifdef ASSERT

   170 static void validate_skip_target(const RoutableEdge* skip_target) {

   171   assert(skip_target != NULL, "invariant");

   172   assert(skip_target->distance_to_root() + 1 == root_context, "invariant");

   173   assert(skip_target->is_sentinel(), "invariant");

   174 }

   175 

   176 static void validate_new_skip_edge(const RoutableEdge* new_skip_edge, const RoutableEdge* last_skip_edge, size_t adjustment) {

   177   assert(new_skip_edge != NULL, "invariant");

   178   assert(new_skip_edge->is_skip_edge(), "invariant");

   179   if (last_skip_edge != NULL) {

   180     const RoutableEdge* const target = skip_to(*new_skip_edge->logical_parent(), adjustment);

   181     validate_skip_target(target->logical_parent());

   182     return;

   183   }

   184   assert(last_skip_edge == NULL, "invariant");

   185   // only one level of logical indirection

   186   validate_skip_target(new_skip_edge->logical_parent());

   187 }

   188 #endif // ASSERT

   189 

   190 static void install_logical_route(const RoutableEdge* new_skip_edge, size_t skip_target_distance) {

   191   assert(new_skip_edge != NULL, "invariant");

   192   assert(!new_skip_edge->is_skip_edge(), "invariant");

   193   assert(!new_skip_edge->processed(), "invariant");

   194   const RoutableEdge* const skip_target = skip_to(*new_skip_edge, skip_target_distance);

   195   assert(skip_target != NULL, "invariant");

   196   new_skip_edge->set_skip_edge(skip_target);

   197   new_skip_edge->set_skip_length(skip_target_distance);

   198   assert(new_skip_edge->is_skip_edge(), "invariant");

   199   assert(new_skip_edge->logical_parent() == skip_target, "invariant");

   200 }

   201 

   202 static const RoutableEdge* find_last_skip_edge(const RoutableEdge& edge, size_t& distance) {

   203   assert(distance == 0, "invariant");

   204   const RoutableEdge* current = &edge;

   205   while (current != NULL) {

   206     if (current->is_skip_edge() && current->skip_edge()->is_sentinel()) {

   207       return current;

   208     }

   209     current = current->physical_parent();

   210     ++distance;

   211   }

   212   return current;

   213 }

   214 

   215 static void collapse_overlapping_chain(const RoutableEdge& edge,

   216                                        const RoutableEdge* first_processed_edge,

   217                                        size_t first_processed_distance) {

   218   assert(first_processed_edge != NULL, "invariant");

   219   // first_processed_edge is already processed / written

   220   assert(first_processed_edge->processed(), "invariant");

   221   assert(first_processed_distance + 1 <= leak_context, "invariant");

   222 

   223   // from this first processed edge, attempt to fetch the last skip edge

   224   size_t last_skip_edge_distance = 0;

   225   const RoutableEdge* const last_skip_edge = find_last_skip_edge(*first_processed_edge, last_skip_edge_distance);

   226   const size_t distance_discovered = first_processed_distance + last_skip_edge_distance + 1;

   227 

   228   if (distance_discovered <= leak_context || (last_skip_edge == NULL && distance_discovered <= max_ref_chain_depth)) {

   229     // complete chain can be accommodated without modification

   230     return;

   231   }

   232 

   233   // backtrack one edge from existing processed edge

   234   const RoutableEdge* const new_skip_edge = skip_to(edge, first_processed_distance - 1);

   235   assert(new_skip_edge != NULL, "invariant");

   236   assert(!new_skip_edge->processed(), "invariant");

   237   assert(new_skip_edge->parent() == first_processed_edge, "invariant");

   238 

   239   size_t adjustment = 0;

   240   if (last_skip_edge != NULL) {

   241     assert(leak_context - 1 > first_processed_distance - 1, "invariant");

   242     adjustment = leak_context - first_processed_distance - 1;

   243     assert(last_skip_edge_distance + 1 > adjustment, "invariant");

   244     install_logical_route(new_skip_edge, last_skip_edge_distance + 1 - adjustment);

   245   } else {

   246     install_logical_route(new_skip_edge, last_skip_edge_distance + 1 - root_context);

   247     new_skip_edge->logical_parent()->set_skip_length(1); // sentinel

   248   }

   249 

   250   DEBUG_ONLY(validate_new_skip_edge(new_skip_edge, last_skip_edge, adjustment);)

   251 }

   252 

   253 static void collapse_non_overlapping_chain(const RoutableEdge& edge,

   254                                            const RoutableEdge* first_processed_edge,

   255                                            size_t first_processed_distance) {

   256   assert(first_processed_edge != NULL, "invariant");

   257   assert(!first_processed_edge->processed(), "invariant");

   258   // this implies that the first "processed" edge is the leak context relative "leaf"

   259   assert(first_processed_distance + 1 == leak_context, "invariant");

   260 

   261   const size_t distance_to_root = edge.distance_to_root();

   262   if (distance_to_root + 1 <= max_ref_chain_depth) {

   263     // complete chain can be accommodated without constructing a skip edge

   264     return;

   265   }

   266 

   267   install_logical_route(first_processed_edge, distance_to_root + 1 - first_processed_distance - root_context);

   268   first_processed_edge->logical_parent()->set_skip_length(1); // sentinel

   269 

   270   DEBUG_ONLY(validate_new_skip_edge(first_processed_edge, NULL, 0);)

   271 }

   272 

   273 static const RoutableEdge* processed_edge(const RoutableEdge& edge, size_t& distance) {

   274   assert(distance == 0, "invariant");

   275   const RoutableEdge* current = &edge;

   276   while (current != NULL && distance < leak_context - 1) {

   277     if (current->processed()) {

   278       return current;

   279     }

   280     current = current->physical_parent();

   281     ++distance;

   282   }

   283   assert(distance <= leak_context - 1, "invariant");

   284   return current;

   285 }

   286 

   287 /*

   288  * Some vocabulary:

   289  * -----------

   290  * "Context" is an interval in the chain, it is associcated with an edge and it signifies a number of connected edges.

   291  * "Processed / written" means an edge that has already been serialized.

   292  * "Skip edge" is an edge that contains additional information for logical routing purposes.

   293  * "Skip target" is an edge used as a destination for a skip edge

   294  */

   295 void EdgeUtils::collapse_chain(const RoutableEdge& edge) {

   296   assert(is_leak_edge(edge), "invariant");

   297 

   298   // attempt to locate an already processed edge inside current leak context (if any)

   299   size_t first_processed_distance = 0;

   300   const RoutableEdge* const first_processed_edge = processed_edge(edge, first_processed_distance);

   301   if (first_processed_edge == NULL) {

   302     return;

   303   }

   304 

   305   if (first_processed_edge->processed()) {

   306     collapse_overlapping_chain(edge, first_processed_edge, first_processed_distance);

   307   } else {

   308     collapse_non_overlapping_chain(edge, first_processed_edge, first_processed_distance);

   309   }

   310 

   311   assert(edge.logical_distance_to_root() + 1 <= max_ref_chain_depth, "invariant");

   312 }