mono/metadata/sgen-old-bridge.c

   1 /*
   2  * sgen-bridge.c: Simple generational GC.
   3  *
   4  * Copyright 2011 Novell, Inc (http://www.novell.com)
   5  * Copyright 2011 Xamarin Inc (http://www.xamarin.com)
   6  * Copyright 2001-2003 Ximian, Inc
   7  * Copyright 2003-2010 Novell, Inc.
   8  * Licensed under the MIT license. See LICENSE file in the project root for full license information.
   9  */
  10
  11 #include "config.h"
  12
  13 #ifdef HAVE_SGEN_GC
  14
  15 #include <stdlib.h>
  16
  17 #include "sgen/sgen-gc.h"
  18 #include "sgen-bridge-internals.h"
  19 #include "sgen/sgen-hash-table.h"
  20 #include "sgen/sgen-qsort.h"
  21 #include "sgen/sgen-client.h"
  22 #include "utils/mono-logger-internals.h"
  23
  24 typedef struct {
  25         int size;
  26         int capacity;
  27         char *data;
  28 } DynArray;
  29
  30 /*Specializations*/
  31
  32 typedef struct {
  33         DynArray array;
  34 } DynIntArray;
  35
  36 typedef struct {
  37         DynArray array;
  38 } DynPtrArray;
  39
  40 typedef struct {
  41         DynArray array;
  42 } DynSCCArray;
  43
  44 /*
  45  * Bridge data for a single managed object
  46  *
  47  * FIXME: Optimizations:
  48  *
  49  * Don't allocate a srcs array for just one source.  Most objects have
  50  * just one source, so use the srcs pointer itself.
  51  */
  52 typedef struct _HashEntry {
  53         GCObject *obj;  /* This is a duplicate - it's already stored in the hash table */
  54
  55         gboolean is_bridge;
  56         gboolean is_visited;
  57
  58         int finishing_time;
  59
  60         // "Source" managed objects pointing at this destination
  61         DynPtrArray srcs;
  62
  63         // Index in sccs array of SCC this object was folded into
  64         int scc_index;
  65 } HashEntry;
  66
  67 typedef struct {
  68         HashEntry entry;
  69         double weight;
  70 } HashEntryWithAccounting;
  71
  72 // The graph of managed objects/HashEntries is reduced to a graph of strongly connected components
  73 typedef struct _SCC {
  74         int index;
  75         int api_index;
  76
  77         // How many bridged objects does this SCC hold references to?
  78         int num_bridge_entries;
  79
  80         // Index in global sccs array of SCCs holding pointers to this SCC
  81         DynIntArray xrefs;              /* these are incoming, not outgoing */
  82 } SCC;
  83
  84 // Maps managed objects to corresponding HashEntry stricts
  85 static SgenHashTable hash_table = SGEN_HASH_TABLE_INIT (INTERNAL_MEM_OLD_BRIDGE_HASH_TABLE, INTERNAL_MEM_OLD_BRIDGE_HASH_TABLE_ENTRY, sizeof (HashEntry), mono_aligned_addr_hash, NULL);
  86
  87 static int current_time;
  88
  89 static gboolean bridge_accounting_enabled = FALSE;
  90
  91 static SgenBridgeProcessor *bridge_processor;
  92
  93 /* Core functions */
  94 /* public */
  95
  96 /* private */
  97
  98 static void
  99 dyn_array_init (DynArray *da)
 100 {
 101         da->size = 0;
 102         da->capacity = 0;
 103         da->data = NULL;
 104 }
 105
 106 static void
 107 dyn_array_uninit (DynArray *da, int elem_size)
 108 {
 109         if (da->capacity <= 0)
 110                 return;
 111
 112         sgen_free_internal_dynamic (da->data, elem_size * da->capacity, INTERNAL_MEM_BRIDGE_DATA);
 113         da->data = NULL;
 114 }
 115
 116 static void
 117 dyn_array_ensure_capacity (DynArray *da, int capacity, int elem_size)
 118 {
 119         int old_capacity = da->capacity;
 120         char *new_data;
 121
 122         if (capacity <= old_capacity)
 123                 return;
 124
 125         if (da->capacity == 0)
 126                 da->capacity = 2;
 127         while (capacity > da->capacity)
 128                 da->capacity *= 2;
 129
 130         new_data = (char *)sgen_alloc_internal_dynamic (elem_size * da->capacity, INTERNAL_MEM_BRIDGE_DATA, TRUE);
 131         memcpy (new_data, da->data, elem_size * da->size);
 132         sgen_free_internal_dynamic (da->data, elem_size * old_capacity, INTERNAL_MEM_BRIDGE_DATA);
 133         da->data = new_data;
 134 }
 135
 136 static void*
 137 dyn_array_add (DynArray *da, int elem_size)
 138 {
 139         void *p;
 140
 141         dyn_array_ensure_capacity (da, da->size + 1, elem_size);
 142
 143         p = da->data + da->size * elem_size;
 144         ++da->size;
 145         return p;
 146 }
 147
 148 /* int */
 149 static void
 150 dyn_array_int_init (DynIntArray *da)
 151 {
 152         dyn_array_init (&da->array);
 153 }
 154
 155 static void
 156 dyn_array_int_uninit (DynIntArray *da)
 157 {
 158         dyn_array_uninit (&da->array, sizeof (int));
 159 }
 160
 161 static int
 162 dyn_array_int_size (DynIntArray *da)
 163 {
 164         return da->array.size;
 165 }
 166
 167 static void
 168 dyn_array_int_set_size (DynIntArray *da, int size)
 169 {
 170         da->array.size = size;
 171 }
 172
 173 static void
 174 dyn_array_int_add (DynIntArray *da, int x)
 175 {
 176         int *p = (int *)dyn_array_add (&da->array, sizeof (int));
 177         *p = x;
 178 }
 179
 180 static int
 181 dyn_array_int_get (DynIntArray *da, int x)
 182 {
 183         return ((int*)da->array.data)[x];
 184 }
 185
 186 static void
 187 dyn_array_int_set (DynIntArray *da, int idx, int val)
 188 {
 189         ((int*)da->array.data)[idx] = val;
 190 }
 191
 192 static void
 193 dyn_array_int_ensure_capacity (DynIntArray *da, int capacity)
 194 {
 195         dyn_array_ensure_capacity (&da->array, capacity, sizeof (int));
 196 }
 197
 198 static void
 199 dyn_array_int_set_all (DynIntArray *dst, DynIntArray *src)
 200 {
 201         dyn_array_int_ensure_capacity (dst, src->array.size);
 202         memcpy (dst->array.data, src->array.data, src->array.size * sizeof (int));
 203         dst->array.size = src->array.size;
 204 }
 205
 206 /* ptr */
 207
 208 static void
 209 dyn_array_ptr_init (DynPtrArray *da)
 210 {
 211         dyn_array_init (&da->array);
 212 }
 213
 214 static void
 215 dyn_array_ptr_uninit (DynPtrArray *da)
 216 {
 217         dyn_array_uninit (&da->array, sizeof (void*));
 218 }
 219
 220 static int
 221 dyn_array_ptr_size (DynPtrArray *da)
 222 {
 223         return da->array.size;
 224 }
 225
 226 static void
 227 dyn_array_ptr_set_size (DynPtrArray *da, int size)
 228 {
 229         da->array.size = size;
 230 }
 231
 232 static void*
 233 dyn_array_ptr_get (DynPtrArray *da, int x)
 234 {
 235         return ((void**)da->array.data)[x];
 236 }
 237
 238 static void
 239 dyn_array_ptr_add (DynPtrArray *da, void *ptr)
 240 {
 241         void **p = (void **)dyn_array_add (&da->array, sizeof (void*));
 242         *p = ptr;
 243 }
 244
 245 #define dyn_array_ptr_push dyn_array_ptr_add
 246
 247 static void*
 248 dyn_array_ptr_pop (DynPtrArray *da)
 249 {
 250         void *p;
 251         int size = da->array.size;
 252         g_assert (size > 0);
 253         p = dyn_array_ptr_get (da, size - 1);
 254         --da->array.size;
 255         return p;
 256 }
 257
 258 /*SCC */
 259
 260 static void
 261 dyn_array_scc_init (DynSCCArray *da)
 262 {
 263         dyn_array_init (&da->array);
 264 }
 265
 266 static void
 267 dyn_array_scc_uninit (DynSCCArray *da)
 268 {
 269         dyn_array_uninit (&da->array, sizeof (SCC));
 270 }
 271
 272 static int
 273 dyn_array_scc_size (DynSCCArray *da)
 274 {
 275         return da->array.size;
 276 }
 277
 278 static SCC*
 279 dyn_array_scc_add (DynSCCArray *da)
 280 {
 281         return (SCC *)dyn_array_add (&da->array, sizeof (SCC));
 282 }
 283
 284 static SCC*
 285 dyn_array_scc_get_ptr (DynSCCArray *da, int x)
 286 {
 287         return &((SCC*)da->array.data)[x];
 288 }
 289
 290 /* Merge code*/
 291
 292 static DynIntArray merge_array;
 293
 294 static gboolean
 295 dyn_array_int_contains (DynIntArray *da, int x)
 296 {
 297         int i;
 298         for (i = 0; i < dyn_array_int_size (da); ++i)
 299                 if (dyn_array_int_get (da, i) == x)
 300                         return TRUE;
 301         return FALSE;
 302 }
 303
 304
 305 static void
 306 dyn_array_int_merge (DynIntArray *dst, DynIntArray *src)
 307 {
 308         int i, j;
 309
 310         dyn_array_int_ensure_capacity (&merge_array, dyn_array_int_size (dst) + dyn_array_int_size (src));
 311         dyn_array_int_set_size (&merge_array, 0);
 312
 313         for (i = j = 0; i < dyn_array_int_size (dst) || j < dyn_array_int_size (src); ) {
 314                 if (i < dyn_array_int_size (dst) && j < dyn_array_int_size (src)) {
 315                         int a = dyn_array_int_get (dst, i);
 316                         int b = dyn_array_int_get (src, j);
 317                         if (a < b) {
 318                                 dyn_array_int_add (&merge_array, a);
 319                                 ++i;
 320                         } else if (a == b) {
 321                                 dyn_array_int_add (&merge_array, a);
 322                                 ++i;
 323                                 ++j;
 324                         } else {
 325                                 dyn_array_int_add (&merge_array, b);
 326                                 ++j;
 327                         }
 328                 } else if (i < dyn_array_int_size (dst)) {
 329                         dyn_array_int_add (&merge_array, dyn_array_int_get (dst, i));
 330                         ++i;
 331                 } else {
 332                         dyn_array_int_add (&merge_array, dyn_array_int_get (src, j));
 333                         ++j;
 334                 }
 335         }
 336
 337         if (dyn_array_int_size (&merge_array) > dyn_array_int_size (dst)) {
 338                 dyn_array_int_set_all (dst, &merge_array);
 339         }
 340 }
 341
 342 static void
 343 dyn_array_int_merge_one (DynIntArray *array, int value)
 344 {
 345         int i;
 346         int tmp;
 347         int size = dyn_array_int_size (array);
 348
 349         for (i = 0; i < size; ++i) {
 350                 if (dyn_array_int_get (array, i) == value)
 351                         return;
 352                 else if (dyn_array_int_get (array, i) > value)
 353                         break;
 354         }
 355
 356         dyn_array_int_ensure_capacity (array, size + 1);
 357
 358         if (i < size) {
 359                 tmp = dyn_array_int_get (array, i);
 360                 for (; i < size; ++i) {
 361                         dyn_array_int_set (array, i, value);
 362                         value = tmp;
 363                         tmp = dyn_array_int_get (array, i + 1);
 364                 }
 365                 dyn_array_int_set (array, size, value);
 366         } else {
 367                 dyn_array_int_set (array, size, value);
 368         }
 369
 370         dyn_array_int_set_size (array, size + 1);
 371 }
 372
 373
 374 static void
 375 set_config (const SgenBridgeProcessorConfig *config)
 376 {
 377         if (config->accounting) {
 378                 SgenHashTable table = SGEN_HASH_TABLE_INIT (INTERNAL_MEM_BRIDGE_HASH_TABLE, INTERNAL_MEM_BRIDGE_HASH_TABLE_ENTRY, sizeof (HashEntryWithAccounting), mono_aligned_addr_hash, NULL);
 379                 bridge_accounting_enabled = TRUE;
 380                 hash_table = table;
 381         }
 382 }
 383
 384 static MonoGCBridgeObjectKind
 385 class_kind (MonoClass *klass)
 386 {
 387         return bridge_callbacks.bridge_class_kind (klass);
 388 }
 389
 390 static HashEntry*
 391 get_hash_entry (GCObject *obj, gboolean *existing)
 392 {
 393         HashEntry *entry = (HashEntry *)sgen_hash_table_lookup (&hash_table, obj);
 394         HashEntry new_entry;
 395
 396         if (entry) {
 397                 if (existing)
 398                         *existing = TRUE;
 399                 return entry;
 400         }
 401         if (existing)
 402                 *existing = FALSE;
 403
 404         memset (&new_entry, 0, sizeof (HashEntry));
 405
 406         new_entry.obj = obj;
 407         dyn_array_ptr_init (&new_entry.srcs);
 408         new_entry.finishing_time = -1;
 409         new_entry.scc_index = -1;
 410
 411         sgen_hash_table_replace (&hash_table, obj, &new_entry, NULL);
 412
 413         return (HashEntry *)sgen_hash_table_lookup (&hash_table, obj);
 414 }
 415
 416 static void
 417 add_source (HashEntry *entry, HashEntry *src)
 418 {
 419         dyn_array_ptr_add (&entry->srcs, src);
 420 }
 421
 422 static void
 423 free_data (void)
 424 {
 425         GCObject *obj G_GNUC_UNUSED;
 426         HashEntry *entry;
 427         int total_srcs = 0;
 428         int max_srcs = 0;
 429
 430         SGEN_HASH_TABLE_FOREACH (&hash_table, GCObject *, obj, HashEntry *, entry) {
 431                 int entry_size = dyn_array_ptr_size (&entry->srcs);
 432                 total_srcs += entry_size;
 433                 if (entry_size > max_srcs)
 434                         max_srcs = entry_size;
 435                 dyn_array_ptr_uninit (&entry->srcs);
 436         } SGEN_HASH_TABLE_FOREACH_END;
 437
 438         sgen_hash_table_clean (&hash_table);
 439
 440         dyn_array_int_uninit (&merge_array);
 441         //g_print ("total srcs %d - max %d\n", total_srcs, max_srcs);
 442 }
 443
 444 static HashEntry*
 445 register_bridge_object (GCObject *obj)
 446 {
 447         HashEntry *entry = get_hash_entry (obj, NULL);
 448         entry->is_bridge = TRUE;
 449         return entry;
 450 }
 451
 452 static void
 453 register_finishing_time (HashEntry *entry, int t)
 454 {
 455         g_assert (entry->finishing_time < 0);
 456         entry->finishing_time = t;
 457 }
 458
 459 static gboolean
 460 object_is_live (GCObject **objp)
 461 {
 462         GCObject *obj = *objp;
 463         GCObject *fwd = SGEN_OBJECT_IS_FORWARDED (obj);
 464         if (fwd) {
 465                 *objp = fwd;
 466                 return sgen_hash_table_lookup (&hash_table, fwd) == NULL;
 467         }
 468         if (!sgen_object_is_live (obj))
 469                 return FALSE;
 470         return sgen_hash_table_lookup (&hash_table, obj) == NULL;
 471 }
 472
 473 static DynPtrArray registered_bridges;
 474 static DynPtrArray dfs_stack;
 475
 476 static int dfs1_passes, dfs2_passes;
 477
 478
 479 #undef HANDLE_PTR
 480 #define HANDLE_PTR(ptr,obj)     do {                                    \
 481                 GCObject *dst = (GCObject*)*(ptr);                      \
 482                 if (dst && !object_is_live (&dst)) {                    \
 483                         dyn_array_ptr_push (&dfs_stack, obj_entry);     \
 484                         dyn_array_ptr_push (&dfs_stack, get_hash_entry (dst, NULL)); \
 485                 }                                                       \
 486         } while (0)
 487
 488 static void
 489 dfs1 (HashEntry *obj_entry)
 490 {
 491         HashEntry *src;
 492         g_assert (dyn_array_ptr_size (&dfs_stack) == 0);
 493
 494         dyn_array_ptr_push (&dfs_stack, NULL);
 495         dyn_array_ptr_push (&dfs_stack, obj_entry);
 496
 497         do {
 498                 GCObject *obj;
 499                 ++dfs1_passes;
 500
 501                 obj_entry = (HashEntry *)dyn_array_ptr_pop (&dfs_stack);
 502                 if (obj_entry) {
 503                         char *start;
 504                         mword desc;
 505                         src = (HashEntry *)dyn_array_ptr_pop (&dfs_stack);
 506
 507                         obj = obj_entry->obj;
 508                         desc = sgen_obj_get_descriptor_safe (obj);
 509
 510                         if (src) {
 511                                 //g_print ("link %s -> %s\n", sgen_safe_name (src->obj), sgen_safe_name (obj));
 512                                 add_source (obj_entry, src);
 513                         } else {
 514                                 //g_print ("starting with %s\n", sgen_safe_name (obj));
 515                         }
 516
 517                         if (obj_entry->is_visited)
 518                                 continue;
 519
 520                         obj_entry->is_visited = TRUE;
 521
 522                         dyn_array_ptr_push (&dfs_stack, obj_entry);
 523                         /* NULL marks that the next entry is to be finished */
 524                         dyn_array_ptr_push (&dfs_stack, NULL);
 525
 526                         start = (char*)obj;
 527 #include "sgen/sgen-scan-object.h"
 528                 } else {
 529                         obj_entry = (HashEntry *)dyn_array_ptr_pop (&dfs_stack);
 530
 531                         //g_print ("finish %s\n", sgen_safe_name (obj_entry->obj));
 532                         register_finishing_time (obj_entry, current_time++);
 533                 }
 534         } while (dyn_array_ptr_size (&dfs_stack) > 0);
 535 }
 536
 537 static void
 538 scc_add_xref (SCC *src, SCC *dst)
 539 {
 540         g_assert (src != dst);
 541         g_assert (src->index != dst->index);
 542
 543         if (dyn_array_int_contains (&dst->xrefs, src->index))
 544                 return;
 545         if (src->num_bridge_entries) {
 546                 dyn_array_int_merge_one (&dst->xrefs, src->index);
 547         } else {
 548                 int i;
 549                 dyn_array_int_merge (&dst->xrefs, &src->xrefs);
 550                 for (i = 0; i < dyn_array_int_size (&dst->xrefs); ++i)
 551                         g_assert (dyn_array_int_get (&dst->xrefs, i) != dst->index);
 552         }
 553 }
 554
 555 static void
 556 scc_add_entry (SCC *scc, HashEntry *entry)
 557 {
 558         g_assert (entry->scc_index < 0);
 559         entry->scc_index = scc->index;
 560         if (entry->is_bridge)
 561                 ++scc->num_bridge_entries;
 562 }
 563
 564 static DynSCCArray sccs;
 565 static SCC *current_scc;
 566
 567 static void
 568 dfs2 (HashEntry *entry)
 569 {
 570         int i;
 571
 572         g_assert (dyn_array_ptr_size (&dfs_stack) == 0);
 573
 574         dyn_array_ptr_push (&dfs_stack, entry);
 575
 576         do {
 577                 entry = (HashEntry *)dyn_array_ptr_pop (&dfs_stack);
 578                 ++dfs2_passes;
 579
 580                 if (entry->scc_index >= 0) {
 581                         if (entry->scc_index != current_scc->index)
 582                                 scc_add_xref (dyn_array_scc_get_ptr (&sccs, entry->scc_index), current_scc);
 583                         continue;
 584                 }
 585
 586                 scc_add_entry (current_scc, entry);
 587
 588                 for (i = 0; i < dyn_array_ptr_size (&entry->srcs); ++i)
 589                         dyn_array_ptr_push (&dfs_stack, dyn_array_ptr_get (&entry->srcs, i));
 590         } while (dyn_array_ptr_size (&dfs_stack) > 0);
 591 }
 592
 593 static int
 594 compare_hash_entries (const HashEntry *e1, const HashEntry *e2)
 595 {
 596         return e2->finishing_time - e1->finishing_time;
 597 }
 598
 599 DEF_QSORT_INLINE(hash_entries, HashEntry*, compare_hash_entries)
 600
 601 static gint64 step_1, step_2, step_3, step_4, step_5, step_6;
 602 static int fist_pass_links, second_pass_links, sccs_links;
 603 static int max_sccs_links = 0;
 604
 605 static void
 606 register_finalized_object (GCObject *obj)
 607 {
 608         g_assert (sgen_need_bridge_processing ());
 609         dyn_array_ptr_push (&registered_bridges, obj);
 610 }
 611
 612 static void
 613 reset_data (void)
 614 {
 615         dyn_array_ptr_set_size (&registered_bridges, 0);
 616 }
 617
 618 static void
 619 processing_stw_step (void)
 620 {
 621         int i;
 622         int bridge_count;
 623         SGEN_TV_DECLARE (atv);
 624         SGEN_TV_DECLARE (btv);
 625
 626         if (!dyn_array_ptr_size (&registered_bridges))
 627                 return;
 628
 629         SGEN_TV_GETTIME (btv);
 630
 631         /* first DFS pass */
 632
 633         dyn_array_ptr_init (&dfs_stack);
 634         dyn_array_int_init (&merge_array);
 635
 636         current_time = 0;
 637         /*
 638         First we insert all bridges into the hash table and then we do dfs1.
 639
 640         It must be done in 2 steps since the bridge arrays doesn't come in reverse topological order,
 641         which means that we can have entry N pointing to entry N + 1.
 642
 643         If we dfs1 entry N before N + 1 is registered we'll not consider N + 1 for this bridge
 644         pass and not create the required xref between the two.
 645         */
 646         bridge_count = dyn_array_ptr_size (&registered_bridges);
 647         for (i = 0; i < bridge_count ; ++i)
 648                 register_bridge_object ((GCObject *)dyn_array_ptr_get (&registered_bridges, i));
 649
 650         for (i = 0; i < bridge_count; ++i)
 651                 dfs1 (get_hash_entry ((GCObject *)dyn_array_ptr_get (&registered_bridges, i), NULL));
 652
 653         SGEN_TV_GETTIME (atv);
 654         step_2 = SGEN_TV_ELAPSED (btv, atv);
 655 }
 656
 657 static int num_registered_bridges, hash_table_size;
 658
 659 static void
 660 processing_build_callback_data (int generation)
 661 {
 662         int i, j;
 663         int num_sccs, num_xrefs;
 664         int max_entries, max_xrefs;
 665         GCObject *obj G_GNUC_UNUSED;
 666         HashEntry *entry;
 667         HashEntry **all_entries;
 668         MonoGCBridgeSCC **api_sccs;
 669         MonoGCBridgeXRef *api_xrefs;
 670         SGEN_TV_DECLARE (atv);
 671         SGEN_TV_DECLARE (btv);
 672
 673         g_assert (bridge_processor->num_sccs == 0 && bridge_processor->num_xrefs == 0);
 674         g_assert (!bridge_processor->api_sccs && !bridge_processor->api_xrefs);
 675
 676         if (!dyn_array_ptr_size (&registered_bridges))
 677                 return;
 678
 679         g_assert (bridge_processing_in_progress);
 680
 681         SGEN_TV_GETTIME (atv);
 682
 683         /* alloc and fill array of all entries */
 684
 685         all_entries = (HashEntry **)sgen_alloc_internal_dynamic (sizeof (HashEntry*) * hash_table.num_entries, INTERNAL_MEM_BRIDGE_DATA, TRUE);
 686
 687         j = 0;
 688         SGEN_HASH_TABLE_FOREACH (&hash_table, GCObject *, obj, HashEntry *, entry) {
 689                 g_assert (entry->finishing_time >= 0);
 690                 all_entries [j++] = entry;
 691                 fist_pass_links += dyn_array_ptr_size (&entry->srcs);
 692         } SGEN_HASH_TABLE_FOREACH_END;
 693         g_assert (j == hash_table.num_entries);
 694         hash_table_size = hash_table.num_entries;
 695
 696         /* sort array according to decreasing finishing time */
 697         qsort_hash_entries (all_entries, hash_table.num_entries);
 698
 699         SGEN_TV_GETTIME (btv);
 700         step_3 = SGEN_TV_ELAPSED (atv, btv);
 701
 702         /* second DFS pass */
 703
 704         dyn_array_scc_init (&sccs);
 705         for (i = 0; i < hash_table.num_entries; ++i) {
 706                 HashEntry *entry = all_entries [i];
 707                 if (entry->scc_index < 0) {
 708                         int index = dyn_array_scc_size (&sccs);
 709                         current_scc = dyn_array_scc_add (&sccs);
 710                         current_scc->index = index;
 711                         current_scc->num_bridge_entries = 0;
 712                         current_scc->api_index = -1;
 713                         dyn_array_int_init (&current_scc->xrefs);
 714
 715                         dfs2 (entry);
 716                 }
 717         }
 718
 719         /*
 720          * Compute the weight of each object. The weight of an object is its size plus the size of all
 721          * objects it points do. When the an object is pointed by multiple objects we distribute it's weight
 722          * equally among them. This distribution gives a rough estimate of the real impact of making the object
 723          * go away.
 724          *
 725          * The reasoning for this model is that complex graphs with single roots will have a bridge with very high
 726          * value in comparison to others.
 727          *
 728          * The all_entries array has all objects topologically sorted. To correctly propagate the weights it must be
 729          * done in reverse topological order - so we calculate the weight of the pointed-to objects before processing
 730          * pointer-from objects.
 731          *
 732          * We log those objects in the opposite order for no particular reason. The other constrain is that it should use the same
 733          * direction as the other logging loop that records live/dead information.
 734          */
 735         if (bridge_accounting_enabled) {
 736                 for (i = hash_table.num_entries - 1; i >= 0; --i) {
 737                         double w;
 738                         HashEntryWithAccounting *entry = (HashEntryWithAccounting*)all_entries [i];
 739
 740                         entry->weight += (double)sgen_safe_object_get_size (entry->entry.obj);
 741                         w = entry->weight / dyn_array_ptr_size (&entry->entry.srcs);
 742                         for (j = 0; j < dyn_array_ptr_size (&entry->entry.srcs); ++j) {
 743                                 HashEntryWithAccounting *other = (HashEntryWithAccounting *)dyn_array_ptr_get (&entry->entry.srcs, j);
 744                                 other->weight += w;
 745                         }
 746                 }
 747                 for (i = 0; i < hash_table.num_entries; ++i) {
 748                         HashEntryWithAccounting *entry = (HashEntryWithAccounting*)all_entries [i];
 749                         if (entry->entry.is_bridge) {
 750                                 MonoClass *klass = SGEN_LOAD_VTABLE (entry->entry.obj)->klass;
 751                                 mono_trace (G_LOG_LEVEL_INFO, MONO_TRACE_GC, "OBJECT %s::%s (%p) weight %f", klass->name_space, klass->name, entry->entry.obj, entry->weight);
 752                         }
 753                 }
 754         }
 755
 756         for (i = 0; i < hash_table.num_entries; ++i) {
 757                 HashEntry *entry = all_entries [i];
 758                 second_pass_links += dyn_array_ptr_size (&entry->srcs);
 759         }
 760
 761         SGEN_TV_GETTIME (atv);
 762         step_4 = SGEN_TV_ELAPSED (btv, atv);
 763
 764         //g_print ("%d sccs\n", sccs.size);
 765
 766         dyn_array_ptr_uninit (&dfs_stack);
 767
 768         /* init data for callback */
 769
 770         num_sccs = 0;
 771         for (i = 0; i < dyn_array_scc_size (&sccs); ++i) {
 772                 SCC *scc = dyn_array_scc_get_ptr (&sccs, i);
 773                 g_assert (scc->index == i);
 774                 if (scc->num_bridge_entries)
 775                         ++num_sccs;
 776                 sccs_links += dyn_array_int_size (&scc->xrefs);
 777                 max_sccs_links = MAX (max_sccs_links, dyn_array_int_size (&scc->xrefs));
 778         }
 779
 780         api_sccs = (MonoGCBridgeSCC **)sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC*) * num_sccs, INTERNAL_MEM_BRIDGE_DATA, TRUE);
 781         num_xrefs = 0;
 782         j = 0;
 783         for (i = 0; i < dyn_array_scc_size (&sccs); ++i) {
 784                 SCC *scc = dyn_array_scc_get_ptr (&sccs, i);
 785                 if (!scc->num_bridge_entries)
 786                         continue;
 787
 788                 api_sccs [j] = (MonoGCBridgeSCC *)sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC) + sizeof (MonoObject*) * scc->num_bridge_entries, INTERNAL_MEM_BRIDGE_DATA, TRUE);
 789                 api_sccs [j]->is_alive = FALSE;
 790                 api_sccs [j]->num_objs = scc->num_bridge_entries;
 791                 scc->num_bridge_entries = 0;
 792                 scc->api_index = j++;
 793
 794                 num_xrefs += dyn_array_int_size (&scc->xrefs);
 795         }
 796
 797         SGEN_HASH_TABLE_FOREACH (&hash_table, GCObject *, obj, HashEntry *, entry) {
 798                 if (entry->is_bridge) {
 799                         SCC *scc = dyn_array_scc_get_ptr (&sccs, entry->scc_index);
 800                         api_sccs [scc->api_index]->objs [scc->num_bridge_entries++] = (MonoObject*)entry->obj;
 801                 }
 802         } SGEN_HASH_TABLE_FOREACH_END;
 803
 804         api_xrefs = (MonoGCBridgeXRef *)sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeXRef) * num_xrefs, INTERNAL_MEM_BRIDGE_DATA, TRUE);
 805         j = 0;
 806         for (i = 0; i < dyn_array_scc_size (&sccs); ++i) {
 807                 int k;
 808                 SCC *scc = dyn_array_scc_get_ptr (&sccs, i);
 809                 if (!scc->num_bridge_entries)
 810                         continue;
 811                 for (k = 0; k < dyn_array_int_size (&scc->xrefs); ++k) {
 812                         SCC *src_scc = dyn_array_scc_get_ptr (&sccs, dyn_array_int_get (&scc->xrefs, k));
 813                         if (!src_scc->num_bridge_entries)
 814                                 continue;
 815                         api_xrefs [j].src_scc_index = src_scc->api_index;
 816                         api_xrefs [j].dst_scc_index = scc->api_index;
 817                         ++j;
 818                 }
 819         }
 820
 821         SGEN_TV_GETTIME (btv);
 822         step_5 = SGEN_TV_ELAPSED (atv, btv);
 823
 824         /* free data */
 825
 826         j = 0;
 827         max_entries = max_xrefs = 0;
 828         for (i = 0; i < dyn_array_scc_size (&sccs); ++i) {
 829                 SCC *scc = dyn_array_scc_get_ptr (&sccs, i);
 830                 if (scc->num_bridge_entries)
 831                         ++j;
 832                 if (scc->num_bridge_entries > max_entries)
 833                         max_entries = scc->num_bridge_entries;
 834                 if (dyn_array_int_size (&scc->xrefs) > max_xrefs)
 835                         max_xrefs = dyn_array_int_size (&scc->xrefs);
 836                 dyn_array_int_uninit (&scc->xrefs);
 837
 838         }
 839         dyn_array_scc_uninit (&sccs);
 840
 841         sgen_free_internal_dynamic (all_entries, sizeof (HashEntry*) * hash_table.num_entries, INTERNAL_MEM_BRIDGE_DATA);
 842
 843         free_data ();
 844         /* Empty the registered bridges array */
 845         num_registered_bridges = dyn_array_ptr_size (&registered_bridges);
 846         dyn_array_ptr_set_size (&registered_bridges, 0);
 847
 848         SGEN_TV_GETTIME (atv);
 849         step_6 = SGEN_TV_ELAPSED (btv, atv);
 850
 851         //g_print ("%d sccs containing bridges - %d max bridge objects - %d max xrefs\n", j, max_entries, max_xrefs);
 852
 853         bridge_processor->num_sccs = num_sccs;
 854         bridge_processor->api_sccs = api_sccs;
 855         bridge_processor->num_xrefs = num_xrefs;
 856         bridge_processor->api_xrefs = api_xrefs;
 857 }
 858
 859 static void
 860 processing_after_callback (int generation)
 861 {
 862         int i, j;
 863         int num_sccs = bridge_processor->num_sccs;
 864         MonoGCBridgeSCC **api_sccs = bridge_processor->api_sccs;
 865
 866         if (bridge_accounting_enabled) {
 867                 for (i = 0; i < num_sccs; ++i) {
 868                         for (j = 0; j < api_sccs [i]->num_objs; ++j) {
 869                                 GCVTable vtable = SGEN_LOAD_VTABLE (api_sccs [i]->objs [j]);
 870                                 mono_trace (G_LOG_LEVEL_INFO, MONO_TRACE_GC,
 871                                         "OBJECT %s.%s (%p) SCC [%d] %s",
 872                                                 sgen_client_vtable_get_namespace (vtable), sgen_client_vtable_get_name (vtable), api_sccs [i]->objs [j],
 873                                                 i,
 874                                                 api_sccs [i]->is_alive  ? "ALIVE" : "DEAD");
 875                         }
 876                 }
 877         }
 878
 879         mono_trace (G_LOG_LEVEL_INFO, MONO_TRACE_GC, "GC_OLD_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",
 880                 num_registered_bridges, hash_table_size, dyn_array_scc_size (&sccs),
 881                 step_1 / 10000.0f,
 882                 step_2 / 10000.0f,
 883                 step_3 / 10000.0f,
 884                 step_4 / 10000.0f,
 885                 step_5 / 10000.0f,
 886                 step_6 / 10000.0f,
 887                 fist_pass_links, second_pass_links, sccs_links, max_sccs_links,
 888                 dfs1_passes, dfs2_passes);
 889
 890         step_1 = 0; /* We must cleanup since this value is used as an accumulator. */
 891         fist_pass_links = second_pass_links = sccs_links = max_sccs_links = 0;
 892         dfs1_passes = dfs2_passes = 0;
 893 }
 894
 895 static void
 896 describe_pointer (GCObject *obj)
 897 {
 898         HashEntry *entry;
 899         int i;
 900
 901         for (i = 0; i < dyn_array_ptr_size (&registered_bridges); ++i) {
 902                 if (obj == dyn_array_ptr_get (&registered_bridges, i)) {
 903                         printf ("Pointer is a registered bridge object.\n");
 904                         break;
 905                 }
 906         }
 907
 908         entry = (HashEntry *)sgen_hash_table_lookup (&hash_table, obj);
 909         if (!entry)
 910                 return;
 911
 912         printf ("Bridge hash table entry %p:\n", entry);
 913         printf ("  is bridge: %d\n", (int)entry->is_bridge);
 914         printf ("  is visited: %d\n", (int)entry->is_visited);
 915 }
 916
 917 void
 918 sgen_old_bridge_init (SgenBridgeProcessor *collector)
 919 {
 920         collector->reset_data = reset_data;
 921         collector->processing_stw_step = processing_stw_step;
 922         collector->processing_build_callback_data = processing_build_callback_data;
 923         collector->processing_after_callback = processing_after_callback;
 924         collector->class_kind = class_kind;
 925         collector->register_finalized_object = register_finalized_object;
 926         collector->describe_pointer = describe_pointer;
 927         collector->set_config = set_config;
 928
 929         bridge_processor = collector;
 930 }
 931
 932 #endif