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