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