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