mono/metadata/sgen-old-bridge.c

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