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