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