mono/metadata/sgen-new-bridge.c

   1 /*
   2  * sgen-bridge.c: Simple generational GC.
   3  *
   4  * Copyright 2011 Novell, Inc (http://www.novell.com)
   5  * Copyright 2011 Xamarin Inc (http://www.xamarin.com)
   6  * Copyright 2001-2003 Ximian, Inc
   7  * Copyright 2003-2010 Novell, Inc.
   8  *
   9  * Licensed under the MIT license. See LICENSE file in the project root for full license information.
  10  */
  11
  12 #include "config.h"
  13
  14 #ifdef HAVE_SGEN_GC
  15
  16 #include <stdlib.h>
  17 #include <errno.h>
  18
  19 #include "sgen/sgen-gc.h"
  20 #include "sgen-bridge-internals.h"
  21 #include "sgen/sgen-hash-table.h"
  22 #include "sgen/sgen-qsort.h"
  23 #include "sgen/sgen-client.h"
  24 #include "tabledefs.h"
  25 #include "utils/mono-logger-internals.h"
  26
  27 #define OPTIMIZATION_COPY
  28 #define OPTIMIZATION_FORWARD
  29 #define OPTIMIZATION_SINGLETON_DYN_ARRAY
  30 #include "sgen-dynarray.h"
  31
  32 //#define NEW_XREFS
  33 #ifdef NEW_XREFS
  34 //#define TEST_NEW_XREFS
  35 #endif
  36
  37 #if !defined(NEW_XREFS) || defined(TEST_NEW_XREFS)
  38 #define OLD_XREFS
  39 #endif
  40
  41 #ifdef NEW_XREFS
  42 #define XREFS new_xrefs
  43 #else
  44 #define XREFS old_xrefs
  45 #endif
  46
  47 /*
  48  * Bridge data for a single managed object
  49  *
  50  * FIXME: Optimizations:
  51  *
  52  * Don't allocate a srcs array for just one source.  Most objects have
  53  * just one source, so use the srcs pointer itself.
  54  */
  55 typedef struct _HashEntry {
  56         gboolean is_bridge;
  57
  58         union {
  59                 struct {
  60                         guint32 is_visited : 1;
  61                         guint32 finishing_time : 31;
  62                         struct _HashEntry *forwarded_to;
  63                 } dfs1;
  64                 struct {
  65                         // Index in sccs array of SCC this object was folded into
  66                         int scc_index;
  67                 } dfs2;
  68         } v;
  69
  70         // "Source" managed objects pointing at this destination
  71         DynPtrArray srcs;
  72 } HashEntry;
  73
  74 typedef struct {
  75         HashEntry entry;
  76         double weight;
  77 } HashEntryWithAccounting;
  78
  79 // The graph of managed objects/HashEntries is reduced to a graph of strongly connected components
  80 typedef struct _SCC {
  81         int index;
  82         int api_index;
  83
  84         // How many bridged objects does this SCC hold references to?
  85         int num_bridge_entries;
  86
  87         gboolean flag;
  88
  89         /*
  90          * Index in global sccs array of SCCs holding pointers to this SCC
  91          *
  92          * New and old xrefs are typically mutually exclusive.  Only when TEST_NEW_XREFS is
  93          * enabled we do both, and compare the results.  This should only be done for
  94          * debugging, obviously.
  95          */
  96 #ifdef OLD_XREFS
  97         DynIntArray old_xrefs;          /* these are incoming, not outgoing */
  98 #endif
  99 #ifdef NEW_XREFS
 100         DynIntArray new_xrefs;
 101 #endif
 102 } SCC;
 103
 104 // Maps managed objects to corresponding HashEntry stricts
 105 static SgenHashTable hash_table = SGEN_HASH_TABLE_INIT (INTERNAL_MEM_BRIDGE_HASH_TABLE, INTERNAL_MEM_BRIDGE_HASH_TABLE_ENTRY, sizeof (HashEntry), mono_aligned_addr_hash, NULL);
 106
 107 static guint32 current_time;
 108
 109 static gboolean bridge_accounting_enabled = FALSE;
 110
 111 static SgenBridgeProcessor *bridge_processor;
 112
 113 /* Core functions */
 114
 115 /*SCC */
 116
 117 static void
 118 dyn_array_scc_init (DynSCCArray *da)
 119 {
 120         dyn_array_init (&da->array);
 121 }
 122
 123 static void
 124 dyn_array_scc_uninit (DynSCCArray *da)
 125 {
 126         dyn_array_uninit (&da->array, sizeof (SCC));
 127 }
 128
 129 static int
 130 dyn_array_scc_size (DynSCCArray *da)
 131 {
 132         return da->array.size;
 133 }
 134
 135 static SCC*
 136 dyn_array_scc_add (DynSCCArray *da)
 137 {
 138         return (SCC *)dyn_array_add (&da->array, sizeof (SCC));
 139 }
 140
 141 static SCC*
 142 dyn_array_scc_get_ptr (DynSCCArray *da, int x)
 143 {
 144         return &((SCC*)da->array.data)[x];
 145 }
 146
 147 /* Merge code*/
 148
 149 static DynIntArray merge_array;
 150
 151 #ifdef NEW_XREFS
 152 static gboolean
 153 dyn_array_int_contains (DynIntArray *da, int x)
 154 {
 155         int i;
 156         for (i = 0; i < dyn_array_int_size (da); ++i)
 157                 if (dyn_array_int_get (da, i) == x)
 158                         return TRUE;
 159         return FALSE;
 160 }
 161 #endif
 162
 163 static void
 164 enable_accounting (void)
 165 {
 166         SgenHashTable table = SGEN_HASH_TABLE_INIT (INTERNAL_MEM_BRIDGE_HASH_TABLE, INTERNAL_MEM_BRIDGE_HASH_TABLE_ENTRY, sizeof (HashEntryWithAccounting), mono_aligned_addr_hash, NULL);
 167         bridge_accounting_enabled = TRUE;
 168         hash_table = table;
 169 }
 170
 171 static MonoGCBridgeObjectKind
 172 class_kind (MonoClass *klass)
 173 {
 174         MonoGCBridgeObjectKind res = bridge_callbacks.bridge_class_kind (klass);
 175
 176         /* If it's a bridge, nothing we can do about it. */
 177         if (res == GC_BRIDGE_TRANSPARENT_BRIDGE_CLASS || res == GC_BRIDGE_OPAQUE_BRIDGE_CLASS)
 178                 return res;
 179
 180         /* Non bridge classes with no pointers will never point to a bridge, so we can savely ignore them. */
 181         if (!klass->has_references) {
 182                 SGEN_LOG (6, "class %s is opaque\n", klass->name);
 183                 return GC_BRIDGE_OPAQUE_CLASS;
 184         }
 185
 186         /* Some arrays can be ignored */
 187         if (klass->rank == 1) {
 188                 MonoClass *elem_class = klass->element_class;
 189
 190                 /* FIXME the bridge check can be quite expensive, cache it at the class level. */
 191                 /* An array of a sealed type that is not a bridge will never get to a bridge */
 192                 if ((elem_class->flags & TYPE_ATTRIBUTE_SEALED) && !elem_class->has_references && !bridge_callbacks.bridge_class_kind (elem_class)) {
 193                         SGEN_LOG (6, "class %s is opaque\n", klass->name);
 194                         return GC_BRIDGE_OPAQUE_CLASS;
 195                 }
 196         }
 197
 198         return GC_BRIDGE_TRANSPARENT_CLASS;
 199 }
 200
 201 static HashEntry*
 202 get_hash_entry (MonoObject *obj, gboolean *existing)
 203 {
 204         HashEntry *entry = (HashEntry *)sgen_hash_table_lookup (&hash_table, obj);
 205         HashEntry new_entry;
 206
 207         if (entry) {
 208                 if (existing)
 209                         *existing = TRUE;
 210                 return entry;
 211         }
 212         if (existing)
 213                 *existing = FALSE;
 214
 215         memset (&new_entry, 0, sizeof (HashEntry));
 216
 217         dyn_array_ptr_init (&new_entry.srcs);
 218         new_entry.v.dfs1.finishing_time = 0;
 219
 220         sgen_hash_table_replace (&hash_table, obj, &new_entry, NULL);
 221
 222         return (HashEntry *)sgen_hash_table_lookup (&hash_table, obj);
 223 }
 224
 225 static void
 226 add_source (HashEntry *entry, HashEntry *src)
 227 {
 228         dyn_array_ptr_add (&entry->srcs, src);
 229 }
 230
 231 static void
 232 free_data (void)
 233 {
 234         MonoObject *obj G_GNUC_UNUSED;
 235         HashEntry *entry;
 236         int total_srcs = 0;
 237         int max_srcs = 0;
 238
 239         SGEN_HASH_TABLE_FOREACH (&hash_table, MonoObject *, obj, HashEntry *, entry) {
 240                 int entry_size = dyn_array_ptr_size (&entry->srcs);
 241                 total_srcs += entry_size;
 242                 if (entry_size > max_srcs)
 243                         max_srcs = entry_size;
 244                 dyn_array_ptr_uninit (&entry->srcs);
 245         } SGEN_HASH_TABLE_FOREACH_END;
 246
 247         sgen_hash_table_clean (&hash_table);
 248
 249         dyn_array_int_uninit (&merge_array);
 250         //g_print ("total srcs %d - max %d\n", total_srcs, max_srcs);
 251 }
 252
 253 static HashEntry*
 254 register_bridge_object (MonoObject *obj)
 255 {
 256         HashEntry *entry = get_hash_entry (obj, NULL);
 257         entry->is_bridge = TRUE;
 258         return entry;
 259 }
 260
 261 static void
 262 register_finishing_time (HashEntry *entry, guint32 t)
 263 {
 264         g_assert (entry->v.dfs1.finishing_time == 0);
 265         /* finishing_time has 31 bits, so it must be within signed int32 range. */
 266         g_assert (t > 0 && t <= G_MAXINT32);
 267         entry->v.dfs1.finishing_time = t;
 268 }
 269
 270 static int ignored_objects;
 271
 272 static gboolean
 273 is_opaque_object (MonoObject *obj)
 274 {
 275         if ((obj->vtable->gc_bits & SGEN_GC_BIT_BRIDGE_OPAQUE_OBJECT) == SGEN_GC_BIT_BRIDGE_OPAQUE_OBJECT) {
 276                 SGEN_LOG (6, "ignoring %s\n", obj->vtable->klass->name);
 277                 ++ignored_objects;
 278                 return TRUE;
 279         }
 280         return FALSE;
 281 }
 282
 283 static gboolean
 284 object_needs_expansion (MonoObject **objp)
 285 {
 286         MonoObject *obj = *objp;
 287         MonoObject *fwd = SGEN_OBJECT_IS_FORWARDED (obj);
 288         if (fwd) {
 289                 *objp = fwd;
 290                 if (is_opaque_object (fwd))
 291                         return FALSE;
 292                 return sgen_hash_table_lookup (&hash_table, fwd) != NULL;
 293         }
 294         if (is_opaque_object (obj))
 295                 return FALSE;
 296         if (!sgen_object_is_live (obj))
 297                 return TRUE;
 298         return sgen_hash_table_lookup (&hash_table, obj) != NULL;
 299 }
 300
 301 static HashEntry*
 302 follow_forward (HashEntry *entry)
 303 {
 304 #ifdef OPTIMIZATION_FORWARD
 305         while (entry->v.dfs1.forwarded_to) {
 306                 HashEntry *next = entry->v.dfs1.forwarded_to;
 307                 if (next->v.dfs1.forwarded_to)
 308                         entry->v.dfs1.forwarded_to = next->v.dfs1.forwarded_to;
 309                 entry = next;
 310         }
 311 #else
 312         g_assert (!entry->v.dfs1.forwarded_to);
 313 #endif
 314         return entry;
 315 }
 316
 317 static DynPtrArray registered_bridges;
 318 static DynPtrArray dfs_stack;
 319
 320 static int dfs1_passes, dfs2_passes;
 321
 322 /*
 323  * DFS1 maintains a stack, where each two entries are effectively one entry.  (FIXME:
 324  * Optimize this via pointer tagging.)  There are two different types of entries:
 325  *
 326  * entry, src: entry needs to be expanded via scanning, and linked to from src
 327  * NULL, entry: entry has already been expanded and needs to be finished
 328  */
 329
 330 #undef HANDLE_PTR
 331 #define HANDLE_PTR(ptr,obj)     do {                                    \
 332                 GCObject *dst = (GCObject*)*(ptr);                      \
 333                 if (dst && object_needs_expansion (&dst)) {                     \
 334                         ++num_links;                                    \
 335                         dyn_array_ptr_push (&dfs_stack, obj_entry);     \
 336                         dyn_array_ptr_push (&dfs_stack, follow_forward (get_hash_entry (dst, NULL))); \
 337                 }                                                       \
 338         } while (0)
 339
 340 static void
 341 dfs1 (HashEntry *obj_entry)
 342 {
 343         HashEntry *src;
 344         g_assert (dyn_array_ptr_size (&dfs_stack) == 0);
 345
 346         dyn_array_ptr_push (&dfs_stack, NULL);
 347         dyn_array_ptr_push (&dfs_stack, obj_entry);
 348
 349         do {
 350                 MonoObject *obj;
 351                 char *start;
 352                 ++dfs1_passes;
 353
 354                 obj_entry = (HashEntry *)dyn_array_ptr_pop (&dfs_stack);
 355                 if (obj_entry) {
 356                         /* obj_entry needs to be expanded */
 357                         src = (HashEntry *)dyn_array_ptr_pop (&dfs_stack);
 358
 359                         if (src)
 360                                 g_assert (!src->v.dfs1.forwarded_to);
 361
 362                         obj_entry = follow_forward (obj_entry);
 363
 364                 again:
 365                         g_assert (!obj_entry->v.dfs1.forwarded_to);
 366                         obj = sgen_hash_table_key_for_value_pointer (obj_entry);
 367                         start = (char*)obj;
 368
 369                         if (!obj_entry->v.dfs1.is_visited) {
 370                                 int num_links = 0;
 371                                 mword desc = sgen_obj_get_descriptor_safe (obj);
 372
 373                                 obj_entry->v.dfs1.is_visited = 1;
 374
 375                                 /* push the finishing entry on the stack */
 376                                 dyn_array_ptr_push (&dfs_stack, obj_entry);
 377                                 dyn_array_ptr_push (&dfs_stack, NULL);
 378
 379 #include "sgen/sgen-scan-object.h"
 380
 381                                 /*
 382                                  * We can remove non-bridge objects with a single outgoing
 383                                  * link by forwarding links going to it.
 384                                  *
 385                                  * This is the first time we've encountered this object, so
 386                                  * no links to it have yet been added.  We'll keep it that
 387                                  * way by setting the forward pointer, and instead of
 388                                  * continuing processing this object, we start over with the
 389                                  * object it points to.
 390                                  */
 391 #ifdef OPTIMIZATION_FORWARD
 392                                 if (!obj_entry->is_bridge && num_links == 1) {
 393                                         HashEntry *dst_entry = (HashEntry *)dyn_array_ptr_pop (&dfs_stack);
 394                                         HashEntry *obj_entry_again = (HashEntry *)dyn_array_ptr_pop (&dfs_stack);
 395                                         g_assert (obj_entry_again == obj_entry);
 396                                         g_assert (!dst_entry->v.dfs1.forwarded_to);
 397                                         if (obj_entry != dst_entry) {
 398                                                 obj_entry->v.dfs1.forwarded_to = dst_entry;
 399                                                 obj_entry = dst_entry;
 400                                         }
 401                                         goto again;
 402                                 }
 403 #endif
 404                         }
 405
 406                         if (src) {
 407                                 //g_print ("link %s -> %s\n", sgen_safe_name (src->obj), sgen_safe_name (obj));
 408                                 g_assert (!obj_entry->v.dfs1.forwarded_to);
 409                                 add_source (obj_entry, src);
 410                         } else {
 411                                 //g_print ("starting with %s\n", sgen_safe_name (obj));
 412                         }
 413                 } else {
 414                         /* obj_entry needs to be finished */
 415
 416                         obj_entry = (HashEntry *)dyn_array_ptr_pop (&dfs_stack);
 417
 418                         //g_print ("finish %s\n", sgen_safe_name (obj_entry->obj));
 419                         register_finishing_time (obj_entry, ++current_time);
 420                 }
 421         } while (dyn_array_ptr_size (&dfs_stack) > 0);
 422 }
 423
 424 static DynSCCArray sccs;
 425 static SCC *current_scc;
 426
 427 /*
 428  * At the end of bridge processing we need to end up with an (acyclyc) graph of bridge
 429  * object SCCs, where the links between the nodes (each one an SCC) in that graph represent
 430  * the presence of a direct or indirect link between those SCCs.  An example:
 431  *
 432  *                       D
 433  *                       |
 434  *                       v
 435  *        A -> B -> c -> e -> F
 436  *
 437  * A, B, D and F are SCCs that contain bridge objects, c and e don't contain bridge objects.
 438  * The graph we need to produce from this is:
 439  *
 440  *                  D
 441  *                  |
 442  *                  v
 443  *        A -> B -> F
 444  *
 445  * Note that we don't need to produce an edge from A to F.  It's sufficient that F is
 446  * indirectly reachable from A.
 447  *
 448  * The old algorithm would create a set, for each SCC, of bridge SCCs that can reach it,
 449  * directly or indirectly, by merging the ones sets for those that reach it directly.  The
 450  * sets it would build up are these:
 451  *
 452  *   A: {}
 453  *   B: {A}
 454  *   c: {B}
 455  *   D: {}
 456  *   e: {B,D}
 457  *   F: {B,D}
 458  *
 459  * The merge operations on these sets turned out to be huge time sinks.
 460  *
 461  * The new algorithm proceeds in two passes: During DFS2, it only builds up the sets of SCCs
 462  * that directly point to each SCC:
 463  *
 464  *   A: {}
 465  *   B: {A}
 466  *   c: {B}
 467  *   D: {}
 468  *   e: {c,D}
 469  *   F: {e}
 470  *
 471  * This is the adjacency list for the SCC graph, in other words.  In a separate step
 472  * afterwards, it does a depth-first traversal of that graph, for each bridge node, to get
 473  * to the final list.  It uses a flag to avoid traversing any node twice.
 474  */
 475 static void
 476 scc_add_xref (SCC *src, SCC *dst)
 477 {
 478         g_assert (src != dst);
 479         g_assert (src->index != dst->index);
 480
 481 #ifdef NEW_XREFS
 482         /*
 483          * FIXME: Right now we don't even unique the direct ancestors, but just add to the
 484          * list.  Doing a containment check slows this algorithm down to almost the speed of
 485          * the old one.  Use the flag instead!
 486          */
 487         dyn_array_int_add (&dst->new_xrefs, src->index);
 488 #endif
 489
 490 #ifdef OLD_XREFS
 491         if (dyn_array_int_is_copy (&dst->old_xrefs)) {
 492                 int i;
 493                 dyn_array_int_ensure_independent (&dst->old_xrefs);
 494                 for (i = 0; i < dyn_array_int_size (&dst->old_xrefs); ++i) {
 495                         int j = dyn_array_int_get (&dst->old_xrefs, i);
 496                         SCC *bridge_scc = dyn_array_scc_get_ptr (&sccs, j);
 497                         g_assert (!bridge_scc->flag);
 498                         bridge_scc->flag = TRUE;
 499                 }
 500         }
 501
 502         if (src->num_bridge_entries) {
 503                 if (src->flag)
 504                         return;
 505                 src->flag = TRUE;
 506                 dyn_array_int_add (&dst->old_xrefs, src->index);
 507 #ifdef OPTIMIZATION_COPY
 508         } else if (dyn_array_int_size (&dst->old_xrefs) == 0) {
 509                 dyn_array_int_copy (&dst->old_xrefs, &src->old_xrefs);
 510 #endif
 511         } else {
 512                 int i;
 513                 for (i = 0; i < dyn_array_int_size (&src->old_xrefs); ++i) {
 514                         int j = dyn_array_int_get (&src->old_xrefs, i);
 515                         SCC *bridge_scc = dyn_array_scc_get_ptr (&sccs, j);
 516                         g_assert (bridge_scc->num_bridge_entries);
 517                         if (!bridge_scc->flag) {
 518                                 bridge_scc->flag = TRUE;
 519                                 dyn_array_int_add (&dst->old_xrefs, j);
 520                         }
 521                 }
 522         }
 523 #endif
 524 }
 525
 526 static void
 527 scc_add_entry (SCC *scc, HashEntry *entry)
 528 {
 529         g_assert (entry->v.dfs2.scc_index < 0);
 530         entry->v.dfs2.scc_index = scc->index;
 531         if (entry->is_bridge)
 532                 ++scc->num_bridge_entries;
 533 }
 534
 535 static void
 536 dfs2 (HashEntry *entry)
 537 {
 538         int i;
 539
 540         g_assert (dyn_array_ptr_size (&dfs_stack) == 0);
 541
 542         dyn_array_ptr_push (&dfs_stack, entry);
 543
 544         do {
 545                 entry = (HashEntry *)dyn_array_ptr_pop (&dfs_stack);
 546                 ++dfs2_passes;
 547
 548                 if (entry->v.dfs2.scc_index >= 0) {
 549                         if (entry->v.dfs2.scc_index != current_scc->index)
 550                                 scc_add_xref (dyn_array_scc_get_ptr (&sccs, entry->v.dfs2.scc_index), current_scc);
 551                         continue;
 552                 }
 553
 554                 scc_add_entry (current_scc, entry);
 555
 556                 for (i = 0; i < dyn_array_ptr_size (&entry->srcs); ++i)
 557                         dyn_array_ptr_push (&dfs_stack, dyn_array_ptr_get (&entry->srcs, i));
 558         } while (dyn_array_ptr_size (&dfs_stack) > 0);
 559
 560 #ifdef OLD_XREFS
 561         /* If xrefs is a copy then we haven't set a single flag. */
 562         if (dyn_array_int_is_copy (&current_scc->old_xrefs))
 563                 return;
 564         for (i = 0; i < dyn_array_int_size (&current_scc->old_xrefs); ++i) {
 565                 int j = dyn_array_int_get (&current_scc->old_xrefs, i);
 566                 SCC *bridge_scc = dyn_array_scc_get_ptr (&sccs, j);
 567                 g_assert (bridge_scc->flag);
 568                 bridge_scc->flag = FALSE;
 569         }
 570 #endif
 571 }
 572
 573 #ifdef NEW_XREFS
 574 static void
 575 gather_xrefs (SCC *scc)
 576 {
 577         int i;
 578         for (i = 0; i < dyn_array_int_size (&scc->new_xrefs); ++i) {
 579                 int index = dyn_array_int_get (&scc->new_xrefs, i);
 580                 SCC *src = dyn_array_scc_get_ptr (&sccs, index);
 581                 if (src->flag)
 582                         continue;
 583                 src->flag = TRUE;
 584                 if (src->num_bridge_entries)
 585                         dyn_array_int_add (&merge_array, index);
 586                 else
 587                         gather_xrefs (src);
 588         }
 589 }
 590
 591 static void
 592 reset_flags (SCC *scc)
 593 {
 594         int i;
 595         for (i = 0; i < dyn_array_int_size (&scc->new_xrefs); ++i) {
 596                 int index = dyn_array_int_get (&scc->new_xrefs, i);
 597                 SCC *src = dyn_array_scc_get_ptr (&sccs, index);
 598                 if (!src->flag)
 599                         continue;
 600                 src->flag = FALSE;
 601                 if (!src->num_bridge_entries)
 602                         reset_flags (src);
 603         }
 604 }
 605 #endif
 606
 607 static char *dump_prefix = NULL;
 608
 609 static void
 610 dump_graph (void)
 611 {
 612         static int counter = 0;
 613
 614         MonoObject *obj;
 615         HashEntry *entry;
 616         size_t prefix_len = strlen (dump_prefix);
 617         char *filename = (char *)alloca (prefix_len + 64);
 618         FILE *file;
 619         int edge_id = 0;
 620
 621         sprintf (filename, "%s.%d.gexf", dump_prefix, counter++);
 622         file = fopen (filename, "w");
 623
 624         if (file == NULL) {
 625                 fprintf (stderr, "Warning: Could not open bridge dump file `%s` for writing: %s\n", filename, strerror (errno));
 626                 return;
 627         }
 628
 629         fprintf (file, "<gexf xmlns=\"http://www.gexf.net/1.2draft\" xmlns:xsi=\"http://www.w3.org/2001/XMLSchema-instance\" xsi:schemaLocation=\"http://www.gexf.net/1.2draft http://www.gexf.net/1.2draft/gexf.xsd\" version=\"1.2\">\n");
 630
 631         fprintf (file, "<graph defaultedgetype=\"directed\">\n"
 632                         "<attributes class=\"node\">\n"
 633                         "<attribute id=\"0\" title=\"class\" type=\"string\"/>\n"
 634                         "<attribute id=\"1\" title=\"bridge\" type=\"boolean\"/>\n"
 635                         "</attributes>\n");
 636
 637         fprintf (file, "<nodes>\n");
 638         SGEN_HASH_TABLE_FOREACH (&hash_table, MonoObject *, obj, HashEntry *, entry) {
 639                 MonoVTable *vt = SGEN_LOAD_VTABLE (obj);
 640                 fprintf (file, "<node id=\"%p\"><attvalues><attvalue for=\"0\" value=\"%s.%s\"/><attvalue for=\"1\" value=\"%s\"/></attvalues></node>\n",
 641                                 obj, vt->klass->name_space, vt->klass->name, entry->is_bridge ? "true" : "false");
 642         } SGEN_HASH_TABLE_FOREACH_END;
 643         fprintf (file, "</nodes>\n");
 644
 645         fprintf (file, "<edges>\n");
 646         SGEN_HASH_TABLE_FOREACH (&hash_table, MonoObject *, obj, HashEntry *, entry) {
 647                 int i;
 648                 for (i = 0; i < dyn_array_ptr_size (&entry->srcs); ++i) {
 649                         HashEntry *src = (HashEntry *)dyn_array_ptr_get (&entry->srcs, i);
 650                         fprintf (file, "<edge id=\"%d\" source=\"%p\" target=\"%p\"/>\n", edge_id++, sgen_hash_table_key_for_value_pointer (src), obj);
 651                 }
 652         } SGEN_HASH_TABLE_FOREACH_END;
 653         fprintf (file, "</edges>\n");
 654
 655         fprintf (file, "</graph></gexf>\n");
 656
 657         fclose (file);
 658 }
 659
 660 static void
 661 set_dump_prefix (const char *prefix)
 662 {
 663         dump_prefix = strdup (prefix);
 664 }
 665
 666 static int
 667 compare_hash_entries (const HashEntry *e1, const HashEntry *e2)
 668 {
 669         /* We can cast to signed int here because finishing_time has only 31 bits. */
 670         return (gint32)e2->v.dfs1.finishing_time - (gint32)e1->v.dfs1.finishing_time;
 671 }
 672
 673 DEF_QSORT_INLINE(hash_entries, HashEntry*, compare_hash_entries)
 674
 675 static gint64 step_1, step_2, step_3, step_4, step_5, step_6;
 676 static int fist_pass_links, second_pass_links, sccs_links;
 677 static int max_sccs_links = 0;
 678
 679 static void
 680 register_finalized_object (GCObject *obj)
 681 {
 682         g_assert (sgen_need_bridge_processing ());
 683         dyn_array_ptr_push (&registered_bridges, obj);
 684 }
 685
 686 static void
 687 reset_data (void)
 688 {
 689         dyn_array_ptr_empty (&registered_bridges);
 690 }
 691
 692 static void
 693 processing_stw_step (void)
 694 {
 695         int i;
 696         int bridge_count;
 697         MonoObject *obj G_GNUC_UNUSED;
 698         HashEntry *entry;
 699         SGEN_TV_DECLARE (atv);
 700         SGEN_TV_DECLARE (btv);
 701
 702         if (!dyn_array_ptr_size (&registered_bridges))
 703                 return;
 704
 705         SGEN_TV_GETTIME (btv);
 706
 707         /* first DFS pass */
 708
 709         dyn_array_ptr_init (&dfs_stack);
 710         dyn_array_int_init (&merge_array);
 711
 712         current_time = 0;
 713         /*
 714         First we insert all bridges into the hash table and then we do dfs1.
 715
 716         It must be done in 2 steps since the bridge arrays doesn't come in reverse topological order,
 717         which means that we can have entry N pointing to entry N + 1.
 718
 719         If we dfs1 entry N before N + 1 is registered we'll not consider N + 1 for this bridge
 720         pass and not create the required xref between the two.
 721         */
 722         bridge_count = dyn_array_ptr_size (&registered_bridges);
 723         for (i = 0; i < bridge_count ; ++i)
 724                 register_bridge_object ((MonoObject *)dyn_array_ptr_get (&registered_bridges, i));
 725
 726         for (i = 0; i < bridge_count; ++i)
 727                 dfs1 (get_hash_entry ((MonoObject *)dyn_array_ptr_get (&registered_bridges, i), NULL));
 728
 729         /* Remove all forwarded objects. */
 730         SGEN_HASH_TABLE_FOREACH (&hash_table, MonoObject *, obj, HashEntry *, entry) {
 731                 if (entry->v.dfs1.forwarded_to) {
 732                         g_assert (dyn_array_ptr_size (&entry->srcs) == 0);
 733                         SGEN_HASH_TABLE_FOREACH_REMOVE (TRUE);
 734                         continue;
 735                 }
 736         } SGEN_HASH_TABLE_FOREACH_END;
 737
 738         SGEN_TV_GETTIME (atv);
 739         step_2 = SGEN_TV_ELAPSED (btv, atv);
 740
 741         if (dump_prefix)
 742                 dump_graph ();
 743 }
 744
 745 static int num_registered_bridges, hash_table_size;
 746
 747 static void
 748 processing_build_callback_data (int generation)
 749 {
 750         int i, j;
 751         int num_sccs, num_xrefs;
 752         int max_entries, max_xrefs;
 753         MonoObject *obj G_GNUC_UNUSED;
 754         HashEntry *entry;
 755         HashEntry **all_entries;
 756         MonoGCBridgeSCC **api_sccs;
 757         MonoGCBridgeXRef *api_xrefs;
 758         SGEN_TV_DECLARE (atv);
 759         SGEN_TV_DECLARE (btv);
 760
 761         g_assert (bridge_processor->num_sccs == 0 && bridge_processor->num_xrefs == 0);
 762         g_assert (!bridge_processor->api_sccs && !bridge_processor->api_xrefs);
 763
 764         if (!dyn_array_ptr_size (&registered_bridges))
 765                 return;
 766
 767         g_assert (bridge_processing_in_progress);
 768
 769         SGEN_TV_GETTIME (atv);
 770
 771         /* alloc and fill array of all entries */
 772
 773         all_entries = (HashEntry **)sgen_alloc_internal_dynamic (sizeof (HashEntry*) * hash_table.num_entries, INTERNAL_MEM_BRIDGE_DATA, TRUE);
 774
 775         j = 0;
 776         SGEN_HASH_TABLE_FOREACH (&hash_table, MonoObject *, obj, HashEntry *, entry) {
 777                 g_assert (entry->v.dfs1.finishing_time > 0);
 778                 all_entries [j++] = entry;
 779                 fist_pass_links += dyn_array_ptr_size (&entry->srcs);
 780         } SGEN_HASH_TABLE_FOREACH_END;
 781         g_assert (j == hash_table.num_entries);
 782         hash_table_size = hash_table.num_entries;
 783
 784         /* sort array according to decreasing finishing time */
 785         qsort_hash_entries (all_entries, hash_table.num_entries);
 786
 787         SGEN_HASH_TABLE_FOREACH (&hash_table, MonoObject *, obj, HashEntry *, entry) {
 788                 entry->v.dfs2.scc_index = -1;
 789         } SGEN_HASH_TABLE_FOREACH_END;
 790
 791         SGEN_TV_GETTIME (btv);
 792         step_3 = SGEN_TV_ELAPSED (atv, btv);
 793
 794         /* second DFS pass */
 795
 796         dyn_array_scc_init (&sccs);
 797         for (i = 0; i < hash_table.num_entries; ++i) {
 798                 HashEntry *entry = all_entries [i];
 799                 if (entry->v.dfs2.scc_index < 0) {
 800                         int index = dyn_array_scc_size (&sccs);
 801                         current_scc = dyn_array_scc_add (&sccs);
 802                         current_scc->index = index;
 803                         current_scc->num_bridge_entries = 0;
 804 #ifdef NEW_XREFS
 805                         current_scc->flag = FALSE;
 806                         dyn_array_int_init (&current_scc->new_xrefs);
 807 #endif
 808 #ifdef OLD_XREFS
 809                         dyn_array_int_init (&current_scc->old_xrefs);
 810 #endif
 811                         current_scc->api_index = -1;
 812
 813                         dfs2 (entry);
 814
 815 #ifdef NEW_XREFS
 816                         /*
 817                          * If a node has only one incoming edge, we just copy the source's
 818                          * xrefs array, effectively removing the source from the graph.
 819                          * This takes care of long linked lists.
 820                          */
 821                         if (!current_scc->num_bridge_entries && dyn_array_int_size (&current_scc->new_xrefs) == 1) {
 822                                 SCC *src;
 823                                 j = dyn_array_int_get (&current_scc->new_xrefs, 0);
 824                                 src = dyn_array_scc_get_ptr (&sccs, j);
 825                                 if (src->num_bridge_entries)
 826                                         dyn_array_int_set (&current_scc->new_xrefs, 0, j);
 827                                 else
 828                                         dyn_array_int_copy (&current_scc->new_xrefs, &src->new_xrefs);
 829                         }
 830 #endif
 831                 }
 832         }
 833
 834 #ifdef NEW_XREFS
 835 #ifdef TEST_NEW_XREFS
 836         for (j = 0; j < dyn_array_scc_size (&sccs); ++j) {
 837                 SCC *scc = dyn_array_scc_get_ptr (&sccs, j);
 838                 g_assert (!scc->flag);
 839         }
 840 #endif
 841
 842         for (i = 0; i < dyn_array_scc_size (&sccs); ++i) {
 843                 SCC *scc = dyn_array_scc_get_ptr (&sccs, i);
 844                 g_assert (scc->index == i);
 845                 if (!scc->num_bridge_entries)
 846                         continue;
 847
 848                 dyn_array_int_empty (&merge_array);
 849                 gather_xrefs (scc);
 850                 reset_flags (scc);
 851                 dyn_array_int_copy (&scc->new_xrefs, &merge_array);
 852                 dyn_array_int_ensure_independent (&scc->new_xrefs);
 853
 854 #ifdef TEST_NEW_XREFS
 855                 for (j = 0; j < dyn_array_scc_size (&sccs); ++j) {
 856                         SCC *scc = dyn_array_scc_get_ptr (&sccs, j);
 857                         g_assert (!scc->flag);
 858                 }
 859 #endif
 860         }
 861
 862 #ifdef TEST_NEW_XREFS
 863         for (i = 0; i < dyn_array_scc_size (&sccs); ++i) {
 864                 SCC *scc = dyn_array_scc_get_ptr (&sccs, i);
 865                 g_assert (scc->index == i);
 866                 if (!scc->num_bridge_entries)
 867                         continue;
 868
 869                 g_assert (dyn_array_int_size (&scc->new_xrefs) == dyn_array_int_size (&scc->old_xrefs));
 870                 for (j = 0; j < dyn_array_int_size (&scc->new_xrefs); ++j)
 871                         g_assert (dyn_array_int_contains (&scc->old_xrefs, dyn_array_int_get (&scc->new_xrefs, j)));
 872         }
 873 #endif
 874 #endif
 875
 876         /*
 877          * Compute the weight of each object. The weight of an object is its size plus the size of all
 878          * objects it points do. When the an object is pointed by multiple objects we distribute it's weight
 879          * equally among them. This distribution gives a rough estimate of the real impact of making the object
 880          * go away.
 881          *
 882          * The reasoning for this model is that complex graphs with single roots will have a bridge with very high
 883          * value in comparison to others.
 884          *
 885          * The all_entries array has all objects topologically sorted. To correctly propagate the weights it must be
 886          * done in reverse topological order - so we calculate the weight of the pointed-to objects before processing
 887          * pointer-from objects.
 888          *
 889          * We log those objects in the opposite order for no particular reason. The other constrain is that it should use the same
 890          * direction as the other logging loop that records live/dead information.
 891          */
 892         if (bridge_accounting_enabled) {
 893                 for (i = hash_table.num_entries - 1; i >= 0; --i) {
 894                         double w;
 895                         HashEntryWithAccounting *entry = (HashEntryWithAccounting*)all_entries [i];
 896
 897                         entry->weight += (double)sgen_safe_object_get_size (sgen_hash_table_key_for_value_pointer (entry));
 898                         w = entry->weight / dyn_array_ptr_size (&entry->entry.srcs);
 899                         for (j = 0; j < dyn_array_ptr_size (&entry->entry.srcs); ++j) {
 900                                 HashEntryWithAccounting *other = (HashEntryWithAccounting *)dyn_array_ptr_get (&entry->entry.srcs, j);
 901                                 other->weight += w;
 902                         }
 903                 }
 904                 for (i = 0; i < hash_table.num_entries; ++i) {
 905                         HashEntryWithAccounting *entry = (HashEntryWithAccounting*)all_entries [i];
 906                         if (entry->entry.is_bridge) {
 907                                 MonoObject *obj = sgen_hash_table_key_for_value_pointer (entry);
 908                                 MonoClass *klass = SGEN_LOAD_VTABLE (obj)->klass;
 909                                 mono_trace (G_LOG_LEVEL_INFO, MONO_TRACE_GC, "OBJECT %s::%s (%p) weight %f", klass->name_space, klass->name, obj, entry->weight);
 910                         }
 911                 }
 912         }
 913
 914         for (i = 0; i < hash_table.num_entries; ++i) {
 915                 HashEntry *entry = all_entries [i];
 916                 second_pass_links += dyn_array_ptr_size (&entry->srcs);
 917         }
 918
 919         SGEN_TV_GETTIME (atv);
 920         step_4 = SGEN_TV_ELAPSED (btv, atv);
 921
 922         //g_print ("%d sccs\n", sccs.size);
 923
 924         dyn_array_ptr_uninit (&dfs_stack);
 925
 926         /* init data for callback */
 927
 928         num_sccs = 0;
 929         for (i = 0; i < dyn_array_scc_size (&sccs); ++i) {
 930                 SCC *scc = dyn_array_scc_get_ptr (&sccs, i);
 931                 g_assert (scc->index == i);
 932                 if (scc->num_bridge_entries)
 933                         ++num_sccs;
 934                 sccs_links += dyn_array_int_size (&scc->XREFS);
 935                 max_sccs_links = MAX (max_sccs_links, dyn_array_int_size (&scc->XREFS));
 936         }
 937
 938         api_sccs = (MonoGCBridgeSCC **)sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC*) * num_sccs, INTERNAL_MEM_BRIDGE_DATA, TRUE);
 939         num_xrefs = 0;
 940         j = 0;
 941         for (i = 0; i < dyn_array_scc_size (&sccs); ++i) {
 942                 SCC *scc = dyn_array_scc_get_ptr (&sccs, i);
 943                 if (!scc->num_bridge_entries)
 944                         continue;
 945
 946                 api_sccs [j] = (MonoGCBridgeSCC *)sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC) + sizeof (MonoObject*) * scc->num_bridge_entries, INTERNAL_MEM_BRIDGE_DATA, TRUE);
 947                 api_sccs [j]->is_alive = FALSE;
 948                 api_sccs [j]->num_objs = scc->num_bridge_entries;
 949                 scc->num_bridge_entries = 0;
 950                 scc->api_index = j++;
 951
 952                 num_xrefs += dyn_array_int_size (&scc->XREFS);
 953         }
 954
 955         SGEN_HASH_TABLE_FOREACH (&hash_table, MonoObject *, obj, HashEntry *, entry) {
 956                 if (entry->is_bridge) {
 957                         SCC *scc = dyn_array_scc_get_ptr (&sccs, entry->v.dfs2.scc_index);
 958                         api_sccs [scc->api_index]->objs [scc->num_bridge_entries++] = sgen_hash_table_key_for_value_pointer (entry);
 959                 }
 960         } SGEN_HASH_TABLE_FOREACH_END;
 961
 962         api_xrefs = (MonoGCBridgeXRef *)sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeXRef) * num_xrefs, INTERNAL_MEM_BRIDGE_DATA, TRUE);
 963         j = 0;
 964         for (i = 0; i < dyn_array_scc_size (&sccs); ++i) {
 965                 int k;
 966                 SCC *scc = dyn_array_scc_get_ptr (&sccs, i);
 967                 if (!scc->num_bridge_entries)
 968                         continue;
 969                 for (k = 0; k < dyn_array_int_size (&scc->XREFS); ++k) {
 970                         SCC *src_scc = dyn_array_scc_get_ptr (&sccs, dyn_array_int_get (&scc->XREFS, k));
 971                         if (!src_scc->num_bridge_entries)
 972                                 continue;
 973                         api_xrefs [j].src_scc_index = src_scc->api_index;
 974                         api_xrefs [j].dst_scc_index = scc->api_index;
 975                         ++j;
 976                 }
 977         }
 978
 979         SGEN_TV_GETTIME (btv);
 980         step_5 = SGEN_TV_ELAPSED (atv, btv);
 981
 982         /* free data */
 983
 984         j = 0;
 985         max_entries = max_xrefs = 0;
 986         for (i = 0; i < dyn_array_scc_size (&sccs); ++i) {
 987                 SCC *scc = dyn_array_scc_get_ptr (&sccs, i);
 988                 if (scc->num_bridge_entries)
 989                         ++j;
 990                 if (scc->num_bridge_entries > max_entries)
 991                         max_entries = scc->num_bridge_entries;
 992                 if (dyn_array_int_size (&scc->XREFS) > max_xrefs)
 993                         max_xrefs = dyn_array_int_size (&scc->XREFS);
 994 #ifdef NEW_XREFS
 995                 dyn_array_int_uninit (&scc->new_xrefs);
 996 #endif
 997 #ifdef OLD_XREFS
 998                 dyn_array_int_uninit (&scc->old_xrefs);
 999 #endif
1000
1001         }
1002         dyn_array_scc_uninit (&sccs);
1003
1004         sgen_free_internal_dynamic (all_entries, sizeof (HashEntry*) * hash_table.num_entries, INTERNAL_MEM_BRIDGE_DATA);
1005
1006         free_data ();
1007         /* Empty the registered bridges array */
1008         num_registered_bridges = dyn_array_ptr_size (&registered_bridges);
1009         dyn_array_ptr_empty (&registered_bridges);
1010
1011         SGEN_TV_GETTIME (atv);
1012         step_6 = SGEN_TV_ELAPSED (btv, atv);
1013
1014         //g_print ("%d sccs containing bridges - %d max bridge objects - %d max xrefs\n", j, max_entries, max_xrefs);
1015
1016         bridge_processor->num_sccs = num_sccs;
1017         bridge_processor->api_sccs = api_sccs;
1018         bridge_processor->num_xrefs = num_xrefs;
1019         bridge_processor->api_xrefs = api_xrefs;
1020 }
1021
1022 static void
1023 processing_after_callback (int generation)
1024 {
1025         int i, j;
1026         int num_sccs = bridge_processor->num_sccs;
1027         MonoGCBridgeSCC **api_sccs = bridge_processor->api_sccs;
1028
1029         if (bridge_accounting_enabled) {
1030                 for (i = 0; i < num_sccs; ++i) {
1031                         for (j = 0; j < api_sccs [i]->num_objs; ++j) {
1032                                 GCVTable vtable = SGEN_LOAD_VTABLE (api_sccs [i]->objs [j]);
1033                                 mono_trace (G_LOG_LEVEL_INFO, MONO_TRACE_GC,
1034                                         "OBJECT %s (%p) SCC [%d] %s",
1035                                                 sgen_client_vtable_get_namespace (vtable), sgen_client_vtable_get_name (vtable), api_sccs [i]->objs [j],
1036                                                 i,
1037                                                 api_sccs [i]->is_alive  ? "ALIVE" : "DEAD");
1038                         }
1039                 }
1040         }
1041
1042         mono_trace (G_LOG_LEVEL_INFO, MONO_TRACE_GC, "GC_NEW_BRIDGE num-objects %d num_hash_entries %d sccs size %d init %.2fms df1 %.2fms sort %.2fms dfs2 %.2fms setup-cb %.2fms free-data %.2fms links %d/%d/%d/%d dfs passes %d/%d ignored %d",
1043                 num_registered_bridges, hash_table_size, dyn_array_scc_size (&sccs),
1044                 step_1 / 10000.0f,
1045                 step_2 / 10000.0f,
1046                 step_3 / 10000.0f,
1047                 step_4 / 10000.0f,
1048                 step_5 / 10000.0f,
1049                 step_6 / 10000.0f,
1050                 fist_pass_links, second_pass_links, sccs_links, max_sccs_links,
1051                 dfs1_passes, dfs2_passes, ignored_objects);
1052
1053         step_1 = 0; /* We must cleanup since this value is used as an accumulator. */
1054         fist_pass_links = second_pass_links = sccs_links = max_sccs_links = 0;
1055         dfs1_passes = dfs2_passes = ignored_objects = 0;
1056 }
1057
1058 static void
1059 describe_pointer (GCObject *obj)
1060 {
1061         HashEntry *entry;
1062         int i;
1063
1064         for (i = 0; i < dyn_array_ptr_size (&registered_bridges); ++i) {
1065                 if (obj == dyn_array_ptr_get (&registered_bridges, i)) {
1066                         printf ("Pointer is a registered bridge object.\n");
1067                         break;
1068                 }
1069         }
1070
1071         entry = (HashEntry *)sgen_hash_table_lookup (&hash_table, obj);
1072         if (!entry)
1073                 return;
1074
1075         printf ("Bridge hash table entry %p:\n", entry);
1076         printf ("  is bridge: %d\n", (int)entry->is_bridge);
1077         printf ("  is visited: %d\n", (int)entry->v.dfs1.is_visited);
1078 }
1079
1080 void
1081 sgen_new_bridge_init (SgenBridgeProcessor *collector)
1082 {
1083         collector->reset_data = reset_data;
1084         collector->processing_stw_step = processing_stw_step;
1085         collector->processing_build_callback_data = processing_build_callback_data;
1086         collector->processing_after_callback = processing_after_callback;
1087         collector->class_kind = class_kind;
1088         collector->register_finalized_object = register_finalized_object;
1089         collector->describe_pointer = describe_pointer;
1090         collector->enable_accounting = enable_accounting;
1091         collector->set_dump_prefix = set_dump_prefix;
1092
1093         bridge_processor = collector;
1094 }
1095
1096 #endif