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