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