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