mono/metadata/sgen-new-bridge.c

   1 /**
   2  * \file
   3  * Simple generational GC.
   4  *
   5  * Copyright 2011 Novell, Inc (http://www.novell.com)
   6  * Copyright 2011 Xamarin Inc (http://www.xamarin.com)
   7  * Copyright 2001-2003 Ximian, Inc
   8  * Copyright 2003-2010 Novell, Inc.
   9  *
  10  * Licensed under the MIT license. See LICENSE file in the project root for full license information.
  11  */
  12
  13 #include "config.h"
  14
  15 #ifdef HAVE_SGEN_GC
  16
  17 #include <stdlib.h>
  18 #include <errno.h>
  19
  20 #include "sgen/sgen-gc.h"
  21 #include "sgen-bridge-internals.h"
  22 #include "sgen/sgen-hash-table.h"
  23 #include "sgen/sgen-qsort.h"
  24 #include "sgen/sgen-client.h"
  25 #include "tabledefs.h"
  26 #include "utils/mono-logger-internals.h"
  27
  28 #define OPTIMIZATION_COPY
  29 #define OPTIMIZATION_FORWARD
  30 #define OPTIMIZATION_SINGLETON_DYN_ARRAY
  31 #include "sgen-dynarray.h"
  32
  33 //#define NEW_XREFS
  34 #ifdef NEW_XREFS
  35 //#define TEST_NEW_XREFS
  36 #endif
  37
  38 #if !defined(NEW_XREFS) || defined(TEST_NEW_XREFS)
  39 #define OLD_XREFS
  40 #endif
  41
  42 #ifdef NEW_XREFS
  43 #define XREFS new_xrefs
  44 #else
  45 #define XREFS old_xrefs
  46 #endif
  47
  48 /*
  49  * Bridge data for a single managed object
  50  *
  51  * FIXME: Optimizations:
  52  *
  53  * Don't allocate a srcs array for just one source.  Most objects have
  54  * just one source, so use the srcs pointer itself.
  55  */
  56 typedef struct _HashEntry {
  57         gboolean is_bridge;
  58
  59         union {
  60                 struct {
  61                         guint32 is_visited : 1;
  62                         guint32 finishing_time : 31;
  63                         struct _HashEntry *forwarded_to;
  64                 } dfs1;
  65                 struct {
  66                         // Index in sccs array of SCC this object was folded into
  67                         int scc_index;
  68                 } dfs2;
  69         } v;
  70
  71         // "Source" managed objects pointing at this destination
  72         DynPtrArray srcs;
  73 } HashEntry;
  74
  75 typedef struct {
  76         HashEntry entry;
  77         double weight;
  78 } HashEntryWithAccounting;
  79
  80 // The graph of managed objects/HashEntries is reduced to a graph of strongly connected components
  81 typedef struct _SCC {
  82         int index;
  83         int api_index;
  84
  85         // How many bridged objects does this SCC hold references to?
  86         int num_bridge_entries;
  87
  88         gboolean flag;
  89
  90         /*
  91          * Index in global sccs array of SCCs holding pointers to this SCC
  92          *
  93          * New and old xrefs are typically mutually exclusive.  Only when TEST_NEW_XREFS is
  94          * enabled we do both, and compare the results.  This should only be done for
  95          * debugging, obviously.
  96          */
  97 #ifdef OLD_XREFS
  98         DynIntArray old_xrefs;          /* these are incoming, not outgoing */
  99 #endif
 100 #ifdef NEW_XREFS
 101         DynIntArray new_xrefs;
 102 #endif
 103 } SCC;
 104
 105 static char *dump_prefix = NULL;
 106
 107 // Maps managed objects to corresponding HashEntry stricts
 108 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);
 109
 110 static guint32 current_time;
 111
 112 static gboolean bridge_accounting_enabled = FALSE;
 113
 114 static SgenBridgeProcessor *bridge_processor;
 115
 116 /* Core functions */
 117
 118 /*SCC */
 119
 120 static void
 121 dyn_array_scc_init (DynSCCArray *da)
 122 {
 123         dyn_array_init (&da->array);
 124 }
 125
 126 static void
 127 dyn_array_scc_uninit (DynSCCArray *da)
 128 {
 129         dyn_array_uninit (&da->array, sizeof (SCC));
 130 }
 131
 132 static int
 133 dyn_array_scc_size (DynSCCArray *da)
 134 {
 135         return da->array.size;
 136 }
 137
 138 static SCC*
 139 dyn_array_scc_add (DynSCCArray *da)
 140 {
 141         return (SCC *)dyn_array_add (&da->array, sizeof (SCC));
 142 }
 143
 144 static SCC*
 145 dyn_array_scc_get_ptr (DynSCCArray *da, int x)
 146 {
 147         return &((SCC*)da->array.data)[x];
 148 }
 149
 150 /* Merge code*/
 151
 152 static DynIntArray merge_array;
 153
 154 #ifdef NEW_XREFS
 155 static gboolean
 156 dyn_array_int_contains (DynIntArray *da, int x)
 157 {
 158         int i;
 159         for (i = 0; i < dyn_array_int_size (da); ++i)
 160                 if (dyn_array_int_get (da, i) == x)
 161                         return TRUE;
 162         return FALSE;
 163 }
 164 #endif
 165
 166 static void
 167 set_config (const SgenBridgeProcessorConfig *config)
 168 {
 169         if (config->accounting) {
 170                 SgenHashTable table = SGEN_HASH_TABLE_INIT (INTERNAL_MEM_BRIDGE_HASH_TABLE, INTERNAL_MEM_BRIDGE_HASH_TABLE_ENTRY, sizeof (HashEntryWithAccounting), mono_aligned_addr_hash, NULL);
 171                 bridge_accounting_enabled = TRUE;
 172                 hash_table = table;
 173         }
 174         if (config->dump_prefix) {
 175                 dump_prefix = strdup (config->dump_prefix);
 176         }
 177 }
 178
 179 static MonoGCBridgeObjectKind
 180 class_kind (MonoClass *klass)
 181 {
 182         MonoGCBridgeObjectKind res = bridge_callbacks.bridge_class_kind (klass);
 183
 184         /* If it's a bridge, nothing we can do about it. */
 185         if (res == GC_BRIDGE_TRANSPARENT_BRIDGE_CLASS || res == GC_BRIDGE_OPAQUE_BRIDGE_CLASS)
 186                 return res;
 187
 188         /* Non bridge classes with no pointers will never point to a bridge, so we can savely ignore them. */
 189         if (!klass->has_references) {
 190                 SGEN_LOG (6, "class %s is opaque\n", klass->name);
 191                 return GC_BRIDGE_OPAQUE_CLASS;
 192         }
 193
 194         /* Some arrays can be ignored */
 195         if (klass->rank == 1) {
 196                 MonoClass *elem_class = klass->element_class;
 197
 198                 /* FIXME the bridge check can be quite expensive, cache it at the class level. */
 199                 /* An array of a sealed type that is not a bridge will never get to a bridge */
 200                 if ((mono_class_get_flags (elem_class) & TYPE_ATTRIBUTE_SEALED) && !elem_class->has_references && !bridge_callbacks.bridge_class_kind (elem_class)) {
 201                         SGEN_LOG (6, "class %s is opaque\n", klass->name);
 202                         return GC_BRIDGE_OPAQUE_CLASS;
 203                 }
 204         }
 205
 206         return GC_BRIDGE_TRANSPARENT_CLASS;
 207 }
 208
 209 static HashEntry*
 210 get_hash_entry (MonoObject *obj, gboolean *existing)
 211 {
 212         HashEntry *entry = (HashEntry *)sgen_hash_table_lookup (&hash_table, obj);
 213         HashEntry new_entry;
 214
 215         if (entry) {
 216                 if (existing)
 217                         *existing = TRUE;
 218                 return entry;
 219         }
 220         if (existing)
 221                 *existing = FALSE;
 222
 223         memset (&new_entry, 0, sizeof (HashEntry));
 224
 225         dyn_array_ptr_init (&new_entry.srcs);
 226         new_entry.v.dfs1.finishing_time = 0;
 227
 228         sgen_hash_table_replace (&hash_table, obj, &new_entry, NULL);
 229
 230         return (HashEntry *)sgen_hash_table_lookup (&hash_table, obj);
 231 }
 232
 233 static void
 234 add_source (HashEntry *entry, HashEntry *src)
 235 {
 236         dyn_array_ptr_add (&entry->srcs, src);
 237 }
 238
 239 static void
 240 free_data (void)
 241 {
 242         MonoObject *obj G_GNUC_UNUSED;
 243         HashEntry *entry;
 244         int total_srcs = 0;
 245         int max_srcs = 0;
 246
 247         SGEN_HASH_TABLE_FOREACH (&hash_table, MonoObject *, obj, HashEntry *, entry) {
 248                 int entry_size = dyn_array_ptr_size (&entry->srcs);
 249                 total_srcs += entry_size;
 250                 if (entry_size > max_srcs)
 251                         max_srcs = entry_size;
 252                 dyn_array_ptr_uninit (&entry->srcs);
 253         } SGEN_HASH_TABLE_FOREACH_END;
 254
 255         sgen_hash_table_clean (&hash_table);
 256
 257         dyn_array_int_uninit (&merge_array);
 258         //g_print ("total srcs %d - max %d\n", total_srcs, max_srcs);
 259 }
 260
 261 static HashEntry*
 262 register_bridge_object (MonoObject *obj)
 263 {
 264         HashEntry *entry = get_hash_entry (obj, NULL);
 265         entry->is_bridge = TRUE;
 266         return entry;
 267 }
 268
 269 static void
 270 register_finishing_time (HashEntry *entry, guint32 t)
 271 {
 272         g_assert (entry->v.dfs1.finishing_time == 0);
 273         /* finishing_time has 31 bits, so it must be within signed int32 range. */
 274         g_assert (t > 0 && t <= G_MAXINT32);
 275         entry->v.dfs1.finishing_time = t;
 276 }
 277
 278 static int ignored_objects;
 279
 280 static gboolean
 281 is_opaque_object (MonoObject *obj)
 282 {
 283         if ((obj->vtable->gc_bits & SGEN_GC_BIT_BRIDGE_OPAQUE_OBJECT) == SGEN_GC_BIT_BRIDGE_OPAQUE_OBJECT) {
 284                 SGEN_LOG (6, "ignoring %s\n", obj->vtable->klass->name);
 285                 ++ignored_objects;
 286                 return TRUE;
 287         }
 288         return FALSE;
 289 }
 290
 291 static gboolean
 292 object_needs_expansion (MonoObject **objp)
 293 {
 294         MonoObject *obj = *objp;
 295         MonoObject *fwd = SGEN_OBJECT_IS_FORWARDED (obj);
 296         if (fwd) {
 297                 *objp = fwd;
 298                 if (is_opaque_object (fwd))
 299                         return FALSE;
 300                 return sgen_hash_table_lookup (&hash_table, fwd) != NULL;
 301         }
 302         if (is_opaque_object (obj))
 303                 return FALSE;
 304         if (!sgen_object_is_live (obj))
 305                 return TRUE;
 306         return sgen_hash_table_lookup (&hash_table, obj) != NULL;
 307 }
 308
 309 static HashEntry*
 310 follow_forward (HashEntry *entry)
 311 {
 312 #ifdef OPTIMIZATION_FORWARD
 313         while (entry->v.dfs1.forwarded_to) {
 314                 HashEntry *next = entry->v.dfs1.forwarded_to;
 315                 if (next->v.dfs1.forwarded_to)
 316                         entry->v.dfs1.forwarded_to = next->v.dfs1.forwarded_to;
 317                 entry = next;
 318         }
 319 #else
 320         g_assert (!entry->v.dfs1.forwarded_to);
 321 #endif
 322         return entry;
 323 }
 324
 325 static DynPtrArray registered_bridges;
 326 static DynPtrArray dfs_stack;
 327
 328 static int dfs1_passes, dfs2_passes;
 329
 330 /*
 331  * DFS1 maintains a stack, where each two entries are effectively one entry.  (FIXME:
 332  * Optimize this via pointer tagging.)  There are two different types of entries:
 333  *
 334  * entry, src: entry needs to be expanded via scanning, and linked to from src
 335  * NULL, entry: entry has already been expanded and needs to be finished
 336  */
 337
 338 #undef HANDLE_PTR
 339 #define HANDLE_PTR(ptr,obj)     do {                                    \
 340                 GCObject *dst = (GCObject*)*(ptr);                      \
 341                 if (dst && object_needs_expansion (&dst)) {                     \
 342                         ++num_links;                                    \
 343                         dyn_array_ptr_push (&dfs_stack, obj_entry);     \
 344                         dyn_array_ptr_push (&dfs_stack, follow_forward (get_hash_entry (dst, NULL))); \
 345                 }                                                       \
 346         } while (0)
 347
 348 static void
 349 dfs1 (HashEntry *obj_entry)
 350 {
 351         HashEntry *src;
 352         g_assert (dyn_array_ptr_size (&dfs_stack) == 0);
 353
 354         dyn_array_ptr_push (&dfs_stack, NULL);
 355         dyn_array_ptr_push (&dfs_stack, obj_entry);
 356
 357         do {
 358                 MonoObject *obj;
 359                 char *start;
 360                 ++dfs1_passes;
 361
 362                 obj_entry = (HashEntry *)dyn_array_ptr_pop (&dfs_stack);
 363                 if (obj_entry) {
 364                         /* obj_entry needs to be expanded */
 365                         src = (HashEntry *)dyn_array_ptr_pop (&dfs_stack);
 366
 367                         if (src)
 368                                 g_assert (!src->v.dfs1.forwarded_to);
 369
 370                         obj_entry = follow_forward (obj_entry);
 371
 372                 again:
 373                         g_assert (!obj_entry->v.dfs1.forwarded_to);
 374                         obj = sgen_hash_table_key_for_value_pointer (obj_entry);
 375                         start = (char*)obj;
 376
 377                         if (!obj_entry->v.dfs1.is_visited) {
 378                                 int num_links = 0;
 379                                 mword desc = sgen_obj_get_descriptor_safe (obj);
 380
 381                                 obj_entry->v.dfs1.is_visited = 1;
 382
 383                                 /* push the finishing entry on the stack */
 384                                 dyn_array_ptr_push (&dfs_stack, obj_entry);
 385                                 dyn_array_ptr_push (&dfs_stack, NULL);
 386
 387 #include "sgen/sgen-scan-object.h"
 388
 389                                 /*
 390                                  * We can remove non-bridge objects with a single outgoing
 391                                  * link by forwarding links going to it.
 392                                  *
 393                                  * This is the first time we've encountered this object, so
 394                                  * no links to it have yet been added.  We'll keep it that
 395                                  * way by setting the forward pointer, and instead of
 396                                  * continuing processing this object, we start over with the
 397                                  * object it points to.
 398                                  */
 399 #ifdef OPTIMIZATION_FORWARD
 400                                 if (!obj_entry->is_bridge && num_links == 1) {
 401                                         HashEntry *dst_entry = (HashEntry *)dyn_array_ptr_pop (&dfs_stack);
 402                                         HashEntry *obj_entry_again = (HashEntry *)dyn_array_ptr_pop (&dfs_stack);
 403                                         g_assert (obj_entry_again == obj_entry);
 404                                         g_assert (!dst_entry->v.dfs1.forwarded_to);
 405                                         if (obj_entry != dst_entry) {
 406                                                 obj_entry->v.dfs1.forwarded_to = dst_entry;
 407                                                 obj_entry = dst_entry;
 408                                         }
 409                                         goto again;
 410                                 }
 411 #endif
 412                         }
 413
 414                         if (src) {
 415                                 //g_print ("link %s -> %s\n", sgen_safe_name (src->obj), sgen_safe_name (obj));
 416                                 g_assert (!obj_entry->v.dfs1.forwarded_to);
 417                                 add_source (obj_entry, src);
 418                         } else {
 419                                 //g_print ("starting with %s\n", sgen_safe_name (obj));
 420                         }
 421                 } else {
 422                         /* obj_entry needs to be finished */
 423
 424                         obj_entry = (HashEntry *)dyn_array_ptr_pop (&dfs_stack);
 425
 426                         //g_print ("finish %s\n", sgen_safe_name (obj_entry->obj));
 427                         register_finishing_time (obj_entry, ++current_time);
 428                 }
 429         } while (dyn_array_ptr_size (&dfs_stack) > 0);
 430 }
 431
 432 static DynSCCArray sccs;
 433 static SCC *current_scc;
 434
 435 /*
 436  * At the end of bridge processing we need to end up with an (acyclyc) graph of bridge
 437  * object SCCs, where the links between the nodes (each one an SCC) in that graph represent
 438  * the presence of a direct or indirect link between those SCCs.  An example:
 439  *
 440  *                       D
 441  *                       |
 442  *                       v
 443  *        A -> B -> c -> e -> F
 444  *
 445  * A, B, D and F are SCCs that contain bridge objects, c and e don't contain bridge objects.
 446  * The graph we need to produce from this is:
 447  *
 448  *                  D
 449  *                  |
 450  *                  v
 451  *        A -> B -> F
 452  *
 453  * Note that we don't need to produce an edge from A to F.  It's sufficient that F is
 454  * indirectly reachable from A.
 455  *
 456  * The old algorithm would create a set, for each SCC, of bridge SCCs that can reach it,
 457  * directly or indirectly, by merging the ones sets for those that reach it directly.  The
 458  * sets it would build up are these:
 459  *
 460  *   A: {}
 461  *   B: {A}
 462  *   c: {B}
 463  *   D: {}
 464  *   e: {B,D}
 465  *   F: {B,D}
 466  *
 467  * The merge operations on these sets turned out to be huge time sinks.
 468  *
 469  * The new algorithm proceeds in two passes: During DFS2, it only builds up the sets of SCCs
 470  * that directly point to each SCC:
 471  *
 472  *   A: {}
 473  *   B: {A}
 474  *   c: {B}
 475  *   D: {}
 476  *   e: {c,D}
 477  *   F: {e}
 478  *
 479  * This is the adjacency list for the SCC graph, in other words.  In a separate step
 480  * afterwards, it does a depth-first traversal of that graph, for each bridge node, to get
 481  * to the final list.  It uses a flag to avoid traversing any node twice.
 482  */
 483 static void
 484 scc_add_xref (SCC *src, SCC *dst)
 485 {
 486         g_assert (src != dst);
 487         g_assert (src->index != dst->index);
 488
 489 #ifdef NEW_XREFS
 490         /*
 491          * FIXME: Right now we don't even unique the direct ancestors, but just add to the
 492          * list.  Doing a containment check slows this algorithm down to almost the speed of
 493          * the old one.  Use the flag instead!
 494          */
 495         dyn_array_int_add (&dst->new_xrefs, src->index);
 496 #endif
 497
 498 #ifdef OLD_XREFS
 499         if (dyn_array_int_is_copy (&dst->old_xrefs)) {
 500                 int i;
 501                 dyn_array_int_ensure_independent (&dst->old_xrefs);
 502                 for (i = 0; i < dyn_array_int_size (&dst->old_xrefs); ++i) {
 503                         int j = dyn_array_int_get (&dst->old_xrefs, i);
 504                         SCC *bridge_scc = dyn_array_scc_get_ptr (&sccs, j);
 505                         g_assert (!bridge_scc->flag);
 506                         bridge_scc->flag = TRUE;
 507                 }
 508         }
 509
 510         if (src->num_bridge_entries) {
 511                 if (src->flag)
 512                         return;
 513                 src->flag = TRUE;
 514                 dyn_array_int_add (&dst->old_xrefs, src->index);
 515 #ifdef OPTIMIZATION_COPY
 516         } else if (dyn_array_int_size (&dst->old_xrefs) == 0) {
 517                 dyn_array_int_copy (&dst->old_xrefs, &src->old_xrefs);
 518 #endif
 519         } else {
 520                 int i;
 521                 for (i = 0; i < dyn_array_int_size (&src->old_xrefs); ++i) {
 522                         int j = dyn_array_int_get (&src->old_xrefs, i);
 523                         SCC *bridge_scc = dyn_array_scc_get_ptr (&sccs, j);
 524                         g_assert (bridge_scc->num_bridge_entries);
 525                         if (!bridge_scc->flag) {
 526                                 bridge_scc->flag = TRUE;
 527                                 dyn_array_int_add (&dst->old_xrefs, j);
 528                         }
 529                 }
 530         }
 531 #endif
 532 }
 533
 534 static void
 535 scc_add_entry (SCC *scc, HashEntry *entry)
 536 {
 537         g_assert (entry->v.dfs2.scc_index < 0);
 538         entry->v.dfs2.scc_index = scc->index;
 539         if (entry->is_bridge)
 540                 ++scc->num_bridge_entries;
 541 }
 542
 543 static void
 544 dfs2 (HashEntry *entry)
 545 {
 546         int i;
 547
 548         g_assert (dyn_array_ptr_size (&dfs_stack) == 0);
 549
 550         dyn_array_ptr_push (&dfs_stack, entry);
 551
 552         do {
 553                 entry = (HashEntry *)dyn_array_ptr_pop (&dfs_stack);
 554                 ++dfs2_passes;
 555
 556                 if (entry->v.dfs2.scc_index >= 0) {
 557                         if (entry->v.dfs2.scc_index != current_scc->index)
 558                                 scc_add_xref (dyn_array_scc_get_ptr (&sccs, entry->v.dfs2.scc_index), current_scc);
 559                         continue;
 560                 }
 561
 562                 scc_add_entry (current_scc, entry);
 563
 564                 for (i = 0; i < dyn_array_ptr_size (&entry->srcs); ++i)
 565                         dyn_array_ptr_push (&dfs_stack, dyn_array_ptr_get (&entry->srcs, i));
 566         } while (dyn_array_ptr_size (&dfs_stack) > 0);
 567
 568 #ifdef OLD_XREFS
 569         /* If xrefs is a copy then we haven't set a single flag. */
 570         if (dyn_array_int_is_copy (&current_scc->old_xrefs))
 571                 return;
 572         for (i = 0; i < dyn_array_int_size (&current_scc->old_xrefs); ++i) {
 573                 int j = dyn_array_int_get (&current_scc->old_xrefs, i);
 574                 SCC *bridge_scc = dyn_array_scc_get_ptr (&sccs, j);
 575                 g_assert (bridge_scc->flag);
 576                 bridge_scc->flag = FALSE;
 577         }
 578 #endif
 579 }
 580
 581 #ifdef NEW_XREFS
 582 static void
 583 gather_xrefs (SCC *scc)
 584 {
 585         int i;
 586         for (i = 0; i < dyn_array_int_size (&scc->new_xrefs); ++i) {
 587                 int index = dyn_array_int_get (&scc->new_xrefs, i);
 588                 SCC *src = dyn_array_scc_get_ptr (&sccs, index);
 589                 if (src->flag)
 590                         continue;
 591                 src->flag = TRUE;
 592                 if (src->num_bridge_entries)
 593                         dyn_array_int_add (&merge_array, index);
 594                 else
 595                         gather_xrefs (src);
 596         }
 597 }
 598
 599 static void
 600 reset_flags (SCC *scc)
 601 {
 602         int i;
 603         for (i = 0; i < dyn_array_int_size (&scc->new_xrefs); ++i) {
 604                 int index = dyn_array_int_get (&scc->new_xrefs, i);
 605                 SCC *src = dyn_array_scc_get_ptr (&sccs, index);
 606                 if (!src->flag)
 607                         continue;
 608                 src->flag = FALSE;
 609                 if (!src->num_bridge_entries)
 610                         reset_flags (src);
 611         }
 612 }
 613 #endif
 614
 615 static void
 616 dump_graph (void)
 617 {
 618         static int counter = 0;
 619
 620         MonoObject *obj;
 621         HashEntry *entry;
 622         size_t prefix_len = strlen (dump_prefix);
 623         char *filename = (char *)alloca (prefix_len + 64);
 624         FILE *file;
 625         int edge_id = 0;
 626
 627         sprintf (filename, "%s.%d.gexf", dump_prefix, counter++);
 628         file = fopen (filename, "w");
 629
 630         if (file == NULL) {
 631                 fprintf (stderr, "Warning: Could not open bridge dump file `%s` for writing: %s\n", filename, strerror (errno));
 632                 return;
 633         }
 634
 635         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");
 636
 637         fprintf (file, "<graph defaultedgetype=\"directed\">\n"
 638                         "<attributes class=\"node\">\n"
 639                         "<attribute id=\"0\" title=\"class\" type=\"string\"/>\n"
 640                         "<attribute id=\"1\" title=\"bridge\" type=\"boolean\"/>\n"
 641                         "</attributes>\n");
 642
 643         fprintf (file, "<nodes>\n");
 644         SGEN_HASH_TABLE_FOREACH (&hash_table, MonoObject *, obj, HashEntry *, entry) {
 645                 MonoVTable *vt = SGEN_LOAD_VTABLE (obj);
 646                 fprintf (file, "<node id=\"%p\"><attvalues><attvalue for=\"0\" value=\"%s.%s\"/><attvalue for=\"1\" value=\"%s\"/></attvalues></node>\n",
 647                                 obj, vt->klass->name_space, vt->klass->name, entry->is_bridge ? "true" : "false");
 648         } SGEN_HASH_TABLE_FOREACH_END;
 649         fprintf (file, "</nodes>\n");
 650
 651         fprintf (file, "<edges>\n");
 652         SGEN_HASH_TABLE_FOREACH (&hash_table, MonoObject *, obj, HashEntry *, entry) {
 653                 int i;
 654                 for (i = 0; i < dyn_array_ptr_size (&entry->srcs); ++i) {
 655                         HashEntry *src = (HashEntry *)dyn_array_ptr_get (&entry->srcs, i);
 656                         fprintf (file, "<edge id=\"%d\" source=\"%p\" target=\"%p\"/>\n", edge_id++, sgen_hash_table_key_for_value_pointer (src), obj);
 657                 }
 658         } SGEN_HASH_TABLE_FOREACH_END;
 659         fprintf (file, "</edges>\n");
 660
 661         fprintf (file, "</graph></gexf>\n");
 662
 663         fclose (file);
 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.%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->set_config = set_config;
1091
1092         bridge_processor = collector;
1093 }
1094
1095 #endif