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