mono/metadata/sgen-bridge.c

   1 /*
   2  * sgen-bridge.c: Simple generational GC.
   3  *
   4  * Copyright 2011 Novell, Inc (http://www.novell.com)
   5  *
   6  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
   7  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
   8  *
   9  * Permission is hereby granted to use or copy this program
  10  * for any purpose,  provided the above notices are retained on all copies.
  11  * Permission to modify the code and to distribute modified code is granted,
  12  * provided the above notices are retained, and a notice that the code was
  13  * modified is included with the above copyright notice.
  14  *
  15  *
  16  * Copyright 2001-2003 Ximian, Inc
  17  * Copyright 2003-2010 Novell, Inc.
  18  *
  19  * Permission is hereby granted, free of charge, to any person obtaining
  20  * a copy of this software and associated documentation files (the
  21  * "Software"), to deal in the Software without restriction, including
  22  * without limitation the rights to use, copy, modify, merge, publish,
  23  * distribute, sublicense, and/or sell copies of the Software, and to
  24  * permit persons to whom the Software is furnished to do so, subject to
  25  * the following conditions:
  26  *
  27  * The above copyright notice and this permission notice shall be
  28  * included in all copies or substantial portions of the Software.
  29  *
  30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  37  */
  38
  39 #ifdef HAVE_SGEN_GC
  40
  41 #include <stdlib.h>
  42
  43 #include "sgen-gc.h"
  44 #include "sgen-bridge.h"
  45 #include "utils/mono-logger-internal.h"
  46 #include "utils/mono-time.h"
  47
  48
  49 typedef struct {
  50         int size;
  51         int elem_size;
  52         int capacity;
  53         char *data;
  54 } DynArray;
  55
  56 #define DYN_ARRAY_REF(da,i)     ((void*)((da)->data + (i) * (da)->elem_size))
  57 #define DYN_ARRAY_PTR_REF(da,i) (((void**)(da)->data) [(i)])
  58 #define DYN_ARRAY_INT_REF(da,i) (((int*)(da)->data) [(i)])
  59 #define DYN_ARRAY_PTR_STATIC_INITIALIZER { 0, sizeof (void*), 0, NULL }
  60 #define DYN_ARRAY_INT_STATIC_INITIALIZER { 0, sizeof (int), 0, NULL }
  61
  62 static void
  63 dyn_array_init (DynArray *da, int elem_size)
  64 {
  65         da->size = 0;
  66         da->elem_size = elem_size;
  67         da->capacity = 0;
  68         da->data = NULL;
  69 }
  70
  71 static void
  72 dyn_array_ptr_init (DynArray *da)
  73 {
  74         dyn_array_init (da, sizeof (void*));
  75 }
  76
  77 static void
  78 dyn_array_int_init (DynArray *da)
  79 {
  80         dyn_array_init (da, sizeof (int));
  81 }
  82
  83 static void
  84 dyn_array_uninit (DynArray *da)
  85 {
  86         if (da->capacity <= 0)
  87                 return;
  88
  89         mono_sgen_free_internal_dynamic (da->data, da->elem_size * da->capacity, INTERNAL_MEM_BRIDGE_DATA);
  90         da->data = NULL;
  91 }
  92
  93 static void
  94 dyn_array_ensure_capacity (DynArray *da, int capacity)
  95 {
  96         int old_capacity = da->capacity;
  97         char *new_data;
  98
  99         if (capacity <= old_capacity)
 100                 return;
 101
 102         if (da->capacity == 0)
 103                 da->capacity = 2;
 104         while (capacity > da->capacity)
 105                 da->capacity *= 2;
 106
 107         new_data = mono_sgen_alloc_internal_dynamic (da->elem_size * da->capacity, INTERNAL_MEM_BRIDGE_DATA);
 108         memcpy (new_data, da->data, da->elem_size * da->size);
 109         mono_sgen_free_internal_dynamic (da->data, da->elem_size * old_capacity, INTERNAL_MEM_BRIDGE_DATA);
 110         da->data = new_data;
 111 }
 112
 113 static void*
 114 dyn_array_add (DynArray *da)
 115 {
 116         void *p;
 117
 118         dyn_array_ensure_capacity (da, da->size + 1);
 119
 120         p = DYN_ARRAY_REF (da, da->size);
 121         ++da->size;
 122         return p;
 123 }
 124
 125 static void
 126 dyn_array_ptr_add (DynArray *da, void *ptr)
 127 {
 128         void **p = dyn_array_add (da);
 129         *p = ptr;
 130 }
 131
 132 #define dyn_array_ptr_push dyn_array_ptr_add
 133
 134 static void*
 135 dyn_array_ptr_pop (DynArray *da)
 136 {
 137         void *p;
 138         g_assert (da->size > 0);
 139         p = DYN_ARRAY_PTR_REF (da, da->size - 1);
 140         --da->size;
 141         return p;
 142 }
 143
 144 static void
 145 dyn_array_int_add (DynArray *da, int x)
 146 {
 147         int *p = dyn_array_add (da);
 148         *p = x;
 149 }
 150
 151 /*
 152 static gboolean
 153 dyn_array_ptr_contains (DynArray *da, void *ptr)
 154 {
 155         int i;
 156         for (i = 0; i < da->size; ++i)
 157                 if (DYN_ARRAY_PTR_REF (da, i) == ptr)
 158                         return TRUE;
 159         return FALSE;
 160 }
 161 */
 162
 163 static gboolean
 164 dyn_array_int_contains (DynArray *da, int x)
 165 {
 166         int i;
 167         for (i = 0; i < da->size; ++i)
 168                 if (DYN_ARRAY_INT_REF (da, i) == x)
 169                         return TRUE;
 170         return FALSE;
 171 }
 172
 173 static DynArray merge_array;
 174
 175 static void
 176 dyn_array_int_merge (DynArray *dst, DynArray *src)
 177 {
 178         int i, j;
 179
 180         dyn_array_ensure_capacity (&merge_array, dst->size + src->size);
 181         merge_array.size = 0;
 182
 183         for (i = j = 0; i < dst->size || j < src->size; ) {
 184                 if (i < dst->size && j < src->size) {
 185                         int a = DYN_ARRAY_INT_REF (dst, i);
 186                         int b = DYN_ARRAY_INT_REF (src, j);
 187                         if (a < b) {
 188                                 dyn_array_int_add (&merge_array, a);
 189                                 ++i;
 190                         } else if (a == b) {
 191                                 dyn_array_int_add (&merge_array, a);
 192                                 ++i;
 193                                 ++j;
 194                         } else {
 195                                 dyn_array_int_add (&merge_array, b);
 196                                 ++j;
 197                         }
 198                 } else if (i < dst->size) {
 199                         dyn_array_int_add (&merge_array, DYN_ARRAY_INT_REF (dst, i));
 200                         ++i;
 201                 } else {
 202                         dyn_array_int_add (&merge_array, DYN_ARRAY_INT_REF (src, j));
 203                         ++j;
 204                 }
 205         }
 206
 207         if (merge_array.size > dst->size) {
 208                 dyn_array_ensure_capacity (dst, merge_array.size);
 209                 memcpy (DYN_ARRAY_REF (dst, 0), DYN_ARRAY_REF (&merge_array, 0), merge_array.size * merge_array.elem_size);
 210                 dst->size = merge_array.size;
 211         }
 212 }
 213
 214 static void
 215 dyn_array_int_merge_one (DynArray *array, int value)
 216 {
 217         int i;
 218         int tmp;
 219         int end = array->size;
 220
 221         for (i = 0; i < end; ++i) {
 222                 if (DYN_ARRAY_INT_REF (array, i) == value)
 223                         return;
 224                 else if (DYN_ARRAY_INT_REF (array, i) > value)
 225                         break;
 226         }
 227
 228         dyn_array_ensure_capacity (array, array->size + 1);
 229
 230         if (i < end) {
 231                 tmp = DYN_ARRAY_INT_REF (array, i);
 232                 for (; i <= end; ++i) {
 233                         DYN_ARRAY_INT_REF (array, i) = value;
 234                         value = tmp;
 235                         tmp = DYN_ARRAY_INT_REF (array, i + 1);
 236                 }
 237                 DYN_ARRAY_INT_REF (array, end + 1) = tmp;
 238         } else {
 239                 DYN_ARRAY_INT_REF (array, end) = value;
 240         }
 241         ++array->size;
 242 }
 243
 244 /*
 245  * FIXME: Optimizations:
 246  *
 247  * Don't allocate a scrs array for just one source.  Most objects have
 248  * just one source, so use the srcs pointer itself.
 249  */
 250 typedef struct _HashEntry {
 251         MonoObject *obj;
 252         gboolean is_bridge;
 253         gboolean is_visited;
 254
 255         int finishing_time;
 256
 257         DynArray srcs;
 258
 259         int scc_index;
 260
 261         struct _HashEntry *next;
 262 } HashEntry;
 263
 264 typedef struct _SCC {
 265         int index;
 266         int api_index;
 267         int num_bridge_entries;
 268         DynArray xrefs;         /* these are incoming, not outgoing */
 269 } SCC;
 270
 271 static int num_hash_entries = 0;
 272 static int hash_size = 0;
 273 static HashEntry **hash_table = NULL;
 274
 275 static MonoGCBridgeCallbacks bridge_callbacks;
 276
 277 static int current_time;
 278
 279 void
 280 mono_gc_register_bridge_callbacks (MonoGCBridgeCallbacks *callbacks)
 281 {
 282         bridge_callbacks = *callbacks;
 283 }
 284
 285 gboolean
 286 mono_sgen_need_bridge_processing (void)
 287 {
 288         return bridge_callbacks.cross_references != NULL;
 289 }
 290
 291 static HashEntry**
 292 alloc_hash_table (int size)
 293 {
 294         HashEntry **table;
 295         table = mono_sgen_alloc_internal_dynamic (sizeof (HashEntry*) * size, INTERNAL_MEM_BRIDGE_DATA);
 296         memset (table, 0, sizeof (HashEntry*) * size);
 297         return table;
 298 }
 299
 300 static void
 301 rehash (void)
 302 {
 303         HashEntry **new_table;
 304         int new_size = hash_size << 1;
 305         int i;
 306
 307         new_table = alloc_hash_table (new_size);
 308         for (i = 0; i < hash_size; ++i) {
 309                 HashEntry *entry = hash_table [i];
 310                 while (entry != NULL) {
 311                         HashEntry *next = entry->next;
 312                         int hash = ((mword)entry->obj >> 4) & (new_size - 1);
 313                         entry->next = new_table [hash];
 314                         new_table [hash] = entry;
 315                         entry = next;
 316                 }
 317         }
 318
 319         mono_sgen_free_internal_dynamic (hash_table, sizeof (HashEntry*) * hash_size, INTERNAL_MEM_BRIDGE_DATA);
 320
 321         hash_table = new_table;
 322         hash_size = new_size;
 323 }
 324
 325 static HashEntry*
 326 lookup_hash_entry (MonoObject *obj)
 327 {
 328         int hash = (mword)obj >> 4;
 329         HashEntry *entry;
 330
 331         if (!hash_table) {
 332                 g_assert (hash_size == 0 && num_hash_entries == 0);
 333                 hash_size = 32;
 334                 hash_table = alloc_hash_table (hash_size);
 335         }
 336
 337         hash &= hash_size - 1;
 338         for (entry = hash_table [hash]; entry != NULL; entry = entry->next) {
 339                 if (entry->obj == obj)
 340                         return entry;
 341         }
 342
 343         return NULL;
 344 }
 345
 346 static HashEntry*
 347 get_hash_entry (MonoObject *obj, gboolean *existing)
 348 {
 349         HashEntry *entry = lookup_hash_entry (obj);
 350         int hash;
 351
 352         if (entry) {
 353                 if (existing)
 354                         *existing = TRUE;
 355                 return entry;
 356         }
 357         if (existing)
 358                 *existing = FALSE;
 359
 360         entry = mono_sgen_alloc_internal_dynamic (sizeof (HashEntry), INTERNAL_MEM_BRIDGE_DATA);
 361         memset (entry, 0, sizeof (HashEntry));
 362
 363         entry->obj = obj;
 364         dyn_array_ptr_init (&entry->srcs);
 365         entry->finishing_time = -1;
 366         entry->scc_index = -1;
 367
 368         hash = ((mword)obj >> 4) & (hash_size - 1);
 369         entry->next = hash_table [hash];
 370         hash_table [hash] = entry;
 371
 372         ++num_hash_entries;
 373
 374         if (num_hash_entries > hash_size >> 1)
 375                 rehash ();
 376
 377         return entry;
 378 }
 379
 380 static void
 381 add_source (HashEntry *entry, HashEntry *src)
 382 {
 383         dyn_array_ptr_add (&entry->srcs, src);
 384 }
 385
 386 static void
 387 free_data (void)
 388 {
 389         int i;
 390         int total_srcs = 0;
 391         int max_srcs = 0;
 392
 393         if (hash_table == NULL)
 394                 return;
 395
 396         for (i = 0; i < hash_size; ++i) {
 397                 HashEntry *entry = hash_table [i];
 398                 while (entry != NULL) {
 399                         HashEntry *next = entry->next;
 400                         total_srcs += entry->srcs.size;
 401                         if (entry->srcs.size > max_srcs)
 402                                 max_srcs = entry->srcs.size;
 403                         dyn_array_uninit (&entry->srcs);
 404                         mono_sgen_free_internal_dynamic (entry, sizeof (HashEntry), INTERNAL_MEM_BRIDGE_DATA);
 405                         entry = next;
 406                 }
 407         }
 408
 409         mono_sgen_free_internal_dynamic (hash_table, sizeof (HashEntry*) * hash_size, INTERNAL_MEM_BRIDGE_DATA);
 410
 411         hash_size = 0;
 412         num_hash_entries = 0;
 413         hash_table = NULL;
 414
 415         dyn_array_uninit (&merge_array);
 416         //g_print ("total srcs %d - max %d\n", total_srcs, max_srcs);
 417 }
 418
 419 static gboolean
 420 register_bridge_object (MonoObject *obj)
 421 {
 422         gboolean existing;
 423         HashEntry *entry = get_hash_entry (obj, &existing);
 424         entry->is_bridge = TRUE;
 425         return !existing;
 426 }
 427
 428 static void
 429 register_finishing_time (HashEntry *entry, int t)
 430 {
 431         g_assert (entry->finishing_time < 0);
 432         entry->finishing_time = t;
 433 }
 434
 435 static gboolean
 436 object_is_live (MonoObject **objp)
 437 {
 438         MonoObject *obj = *objp;
 439         MonoObject *fwd = SGEN_OBJECT_IS_FORWARDED (obj);
 440         if (fwd) {
 441                 *objp = fwd;
 442                 return lookup_hash_entry (fwd) == NULL;
 443         }
 444         if (!mono_sgen_object_is_live (obj))
 445                 return FALSE;
 446         return lookup_hash_entry (obj) == NULL;
 447 }
 448
 449 static DynArray registered_bridges = DYN_ARRAY_PTR_STATIC_INITIALIZER;
 450 static DynArray dfs_stack;
 451
 452 static int dsf1_passes, dsf2_passes;
 453
 454
 455 #undef HANDLE_PTR
 456 #define HANDLE_PTR(ptr,obj)     do {                                    \
 457                 MonoObject *dst = (MonoObject*)*(ptr);                  \
 458                 if (dst && !object_is_live (&dst)) {                    \
 459                         dyn_array_ptr_push (&dfs_stack, obj_entry);     \
 460                         dyn_array_ptr_push (&dfs_stack, get_hash_entry (dst, NULL)); \
 461                 }                                                       \
 462         } while (0)
 463
 464 static void
 465 dfs1 (HashEntry *obj_entry, HashEntry *src)
 466 {
 467         g_assert (dfs_stack.size == 0);
 468
 469         dyn_array_ptr_push (&dfs_stack, src);
 470         dyn_array_ptr_push (&dfs_stack, obj_entry);
 471
 472         do {
 473                 MonoObject *obj;
 474                 char *start;
 475                 ++dsf1_passes;
 476
 477                 obj_entry = dyn_array_ptr_pop (&dfs_stack);
 478                 if (obj_entry) {
 479                         src = dyn_array_ptr_pop (&dfs_stack);
 480
 481                         obj = obj_entry->obj;
 482                         start = (char*)obj;
 483
 484                         if (src) {
 485                                 //g_print ("link %s -> %s\n", mono_sgen_safe_name (src->obj), mono_sgen_safe_name (obj));
 486                                 add_source (obj_entry, src);
 487                         } else {
 488                                 //g_print ("starting with %s\n", mono_sgen_safe_name (obj));
 489                         }
 490
 491                         if (obj_entry->is_visited)
 492                                 continue;
 493
 494                         obj_entry->is_visited = TRUE;
 495
 496                         dyn_array_ptr_push (&dfs_stack, obj_entry);
 497                         /* NULL marks that the next entry is to be finished */
 498                         dyn_array_ptr_push (&dfs_stack, NULL);
 499
 500 #include "sgen-scan-object.h"
 501                 } else {
 502                         obj_entry = dyn_array_ptr_pop (&dfs_stack);
 503
 504                         //g_print ("finish %s\n", mono_sgen_safe_name (obj_entry->obj));
 505                         register_finishing_time (obj_entry, current_time++);
 506                 }
 507         } while (dfs_stack.size > 0);
 508 }
 509
 510 static void
 511 scc_add_xref (SCC *src, SCC *dst)
 512 {
 513         g_assert (src != dst);
 514         g_assert (src->index != dst->index);
 515
 516         if (dyn_array_int_contains (&dst->xrefs, src->index))
 517                 return;
 518         if (src->num_bridge_entries) {
 519                 dyn_array_int_merge_one (&dst->xrefs, src->index);
 520         } else {
 521                 int i;
 522                 dyn_array_int_merge (&dst->xrefs, &src->xrefs);
 523                 for (i = 0; i < dst->xrefs.size; ++i)
 524                         g_assert (DYN_ARRAY_INT_REF (&dst->xrefs, i) != dst->index);
 525         }
 526 }
 527
 528 static void
 529 scc_add_entry (SCC *scc, HashEntry *entry)
 530 {
 531         g_assert (entry->scc_index < 0);
 532         entry->scc_index = scc->index;
 533         if (entry->is_bridge)
 534                 ++scc->num_bridge_entries;
 535 }
 536
 537 static DynArray sccs;
 538 static SCC *current_scc;
 539
 540 static void
 541 dfs2 (HashEntry *entry)
 542 {
 543         int i;
 544
 545         g_assert (dfs_stack.size == 0);
 546
 547         dyn_array_ptr_push (&dfs_stack, entry);
 548
 549         do {
 550                 entry = dyn_array_ptr_pop (&dfs_stack);
 551                 ++dsf2_passes;
 552
 553                 if (entry->scc_index >= 0) {
 554                         if (entry->scc_index != current_scc->index)
 555                                 scc_add_xref (DYN_ARRAY_REF (&sccs, entry->scc_index), current_scc);
 556                         continue;
 557                 }
 558
 559                 scc_add_entry (current_scc, entry);
 560
 561                 for (i = 0; i < entry->srcs.size; ++i)
 562                         dyn_array_ptr_push (&dfs_stack, DYN_ARRAY_PTR_REF (&entry->srcs, i));
 563         } while (dfs_stack.size > 0);
 564 }
 565
 566 static int
 567 compare_hash_entries (const void *ep1, const void *ep2)
 568 {
 569         HashEntry *e1 = *(HashEntry**)ep1;
 570         HashEntry *e2 = *(HashEntry**)ep2;
 571         return e2->finishing_time - e1->finishing_time;
 572 }
 573
 574 gboolean
 575 mono_sgen_is_bridge_object (MonoObject *obj)
 576 {
 577         return bridge_callbacks.is_bridge_object (obj);
 578 }
 579
 580 static unsigned long step_1, step_2, step_3, step_4, step_5, step_6, step_7, step_8;
 581 static int fist_pass_links, second_pass_links, sccs_links;
 582 static int max_sccs_links = 0;
 583
 584 void
 585 mono_sgen_bridge_processing_register_objects (int num_objs, MonoObject **objs)
 586 {
 587         int j = 0;
 588         int i;
 589         SGEN_TV_DECLARE (atv);
 590         SGEN_TV_DECLARE (btv);
 591
 592         fist_pass_links = second_pass_links = sccs_links = 0;
 593         dsf1_passes = dsf2_passes = 0;
 594         SGEN_TV_GETTIME (atv);
 595
 596         g_assert (mono_sgen_need_bridge_processing ());
 597
 598         //g_print ("%d finalized objects\n", num_objs);
 599
 600         /* The collector step checks for bridge objects already, so we don't need to do it again. */
 601         for (i = 0; i < num_objs; ++i) {
 602                 MonoObject *obj = objs [i];
 603                 if (register_bridge_object (obj))
 604                         dyn_array_ptr_push (&registered_bridges, obj);
 605         }
 606
 607         SGEN_TV_GETTIME (btv);
 608         step_1 += SGEN_TV_ELAPSED (atv, btv);
 609 }
 610
 611 void
 612 mono_sgen_bridge_processing_stw_step (void)
 613 {
 614         int i;
 615         SGEN_TV_DECLARE (atv);
 616         SGEN_TV_DECLARE (btv);
 617
 618         if (!registered_bridges.size)
 619                 return;
 620
 621         SGEN_TV_GETTIME (btv);
 622
 623         /* first DFS pass */
 624
 625         dyn_array_ptr_init (&dfs_stack);
 626         dyn_array_int_init (&merge_array);
 627
 628         current_time = 0;
 629         for (i = 0; i < registered_bridges.size; ++i)
 630                 dfs1 (get_hash_entry (DYN_ARRAY_PTR_REF (&registered_bridges, i), NULL), NULL);
 631
 632         SGEN_TV_GETTIME (atv);
 633         step_2 = SGEN_TV_ELAPSED (btv, atv);
 634 }
 635
 636 void
 637 mono_sgen_bridge_processing_finish (void)
 638 {
 639         int i, j;
 640         int num_sccs, num_xrefs;
 641         int max_entries, max_xrefs;
 642         int hash_table_size, sccs_size;
 643         MonoObject *obj;
 644         HashEntry *entry;
 645         int num_registered_bridges;
 646         HashEntry **all_entries;
 647         MonoGCBridgeSCC **api_sccs;
 648         MonoGCBridgeXRef *api_xrefs;
 649         SGEN_TV_DECLARE (atv);
 650         SGEN_TV_DECLARE (btv);
 651
 652         if (!registered_bridges.size)
 653                 return;
 654
 655         SGEN_TV_GETTIME (atv);
 656
 657         /* alloc and fill array of all entries */
 658
 659         all_entries = mono_sgen_alloc_internal_dynamic (sizeof (HashEntry*) * num_hash_entries, INTERNAL_MEM_BRIDGE_DATA);
 660
 661         j = 0;
 662         max_entries = 0;
 663         for (i = 0; i < hash_size; ++i) {
 664                 HashEntry *entry;
 665                 int length = 0;
 666                 for (entry = hash_table [i]; entry != NULL; entry = entry->next) {
 667                         g_assert (entry->finishing_time >= 0);
 668                         all_entries [j++] = entry;
 669                         ++length;
 670                         fist_pass_links += entry->srcs.size;
 671                 }
 672                 if (length > max_entries)
 673                         max_entries = length;
 674         }
 675         g_assert (j == num_hash_entries);
 676         hash_table_size = num_hash_entries;
 677
 678         //g_print ("max hash bucket length %d\n", max_entries);
 679
 680         /* sort array according to decreasing finishing time */
 681
 682         qsort (all_entries, num_hash_entries, sizeof (HashEntry*), compare_hash_entries);
 683
 684         SGEN_TV_GETTIME (btv);
 685         step_3 = SGEN_TV_ELAPSED (atv, btv);
 686
 687         /* second DFS pass */
 688
 689         dyn_array_init (&sccs, sizeof (SCC));
 690         for (i = 0; i < num_hash_entries; ++i) {
 691                 HashEntry *entry = all_entries [i];
 692                 if (entry->scc_index < 0) {
 693                         int index = sccs.size;
 694                         current_scc = dyn_array_add (&sccs);
 695                         current_scc->index = index;
 696                         current_scc->num_bridge_entries = 0;
 697                         current_scc->api_index = -1;
 698                         dyn_array_int_init (&current_scc->xrefs);
 699
 700                         dfs2 (entry);
 701                 }
 702         }
 703
 704         sccs_size = sccs.size;
 705
 706         for (i = 0; i < num_hash_entries; ++i) {
 707                 HashEntry *entry = all_entries [i];
 708                 second_pass_links += entry->srcs.size;
 709         }
 710
 711         SGEN_TV_GETTIME (atv);
 712         step_4 = SGEN_TV_ELAPSED (btv, atv);
 713
 714         //g_print ("%d sccs\n", sccs.size);
 715
 716         dyn_array_uninit (&dfs_stack);
 717
 718         /* init data for callback */
 719
 720         num_sccs = 0;
 721         for (i = 0; i < sccs.size; ++i) {
 722                 SCC *scc = DYN_ARRAY_REF (&sccs, i);
 723                 g_assert (scc->index == i);
 724                 if (scc->num_bridge_entries)
 725                         ++num_sccs;
 726                 sccs_links += scc->xrefs.size;
 727                 max_sccs_links = MAX (max_sccs_links, scc->xrefs.size);
 728         }
 729
 730         api_sccs = mono_sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC*) * num_sccs, INTERNAL_MEM_BRIDGE_DATA);
 731         num_xrefs = 0;
 732         j = 0;
 733         for (i = 0; i < sccs.size; ++i) {
 734                 SCC *scc = DYN_ARRAY_REF (&sccs, i);
 735                 if (!scc->num_bridge_entries)
 736                         continue;
 737
 738                 api_sccs [j] = mono_sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC) + sizeof (MonoObject*) * scc->num_bridge_entries, INTERNAL_MEM_BRIDGE_DATA);
 739                 api_sccs [j]->num_objs = scc->num_bridge_entries;
 740                 scc->num_bridge_entries = 0;
 741                 scc->api_index = j++;
 742
 743                 num_xrefs += scc->xrefs.size;
 744         }
 745
 746         for (i = 0; i < hash_size; ++i) {
 747                 HashEntry *entry;
 748                 for (entry = hash_table [i]; entry != NULL; entry = entry->next) {
 749                         SCC *scc;
 750                         if (!entry->is_bridge)
 751                                 continue;
 752                         scc = DYN_ARRAY_REF (&sccs, entry->scc_index);
 753                         api_sccs [scc->api_index]->objs [scc->num_bridge_entries++] = entry->obj;
 754                 }
 755         }
 756
 757         api_xrefs = mono_sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeXRef) * num_xrefs, INTERNAL_MEM_BRIDGE_DATA);
 758         j = 0;
 759         for (i = 0; i < sccs.size; ++i) {
 760                 int k;
 761                 SCC *scc = DYN_ARRAY_REF (&sccs, i);
 762                 if (!scc->num_bridge_entries)
 763                         continue;
 764                 for (k = 0; k < scc->xrefs.size; ++k) {
 765                         SCC *src_scc = DYN_ARRAY_REF (&sccs, DYN_ARRAY_INT_REF (&scc->xrefs, k));
 766                         if (!src_scc->num_bridge_entries)
 767                                 continue;
 768                         api_xrefs [j].src_scc_index = src_scc->api_index;
 769                         api_xrefs [j].dst_scc_index = scc->api_index;
 770                         ++j;
 771                 }
 772         }
 773
 774         SGEN_TV_GETTIME (btv);
 775         step_5 = SGEN_TV_ELAPSED (atv, btv);
 776
 777         /* free data */
 778
 779         j = 0;
 780         max_entries = max_xrefs = 0;
 781         for (i = 0; i < sccs.size; ++i) {
 782                 SCC *scc = DYN_ARRAY_REF (&sccs, i);
 783                 if (scc->num_bridge_entries)
 784                         ++j;
 785                 if (scc->num_bridge_entries > max_entries)
 786                         max_entries = scc->num_bridge_entries;
 787                 if (scc->xrefs.size > max_xrefs)
 788                         max_xrefs = scc->xrefs.size;
 789                 dyn_array_uninit (&scc->xrefs);
 790
 791         }
 792         dyn_array_uninit (&sccs);
 793
 794         mono_sgen_free_internal_dynamic (all_entries, sizeof (HashEntry*) * num_hash_entries, INTERNAL_MEM_BRIDGE_DATA);
 795
 796         free_data ();
 797         /* Empty the registered bridges array */
 798         num_registered_bridges = registered_bridges.size;
 799         registered_bridges.size = 0;
 800
 801         SGEN_TV_GETTIME (atv);
 802         step_6 = SGEN_TV_ELAPSED (btv, atv);
 803
 804         //g_print ("%d sccs containing bridges - %d max bridge objects - %d max xrefs\n", j, max_entries, max_xrefs);
 805
 806         /* callback */
 807
 808         bridge_callbacks.cross_references (num_sccs, api_sccs, num_xrefs, api_xrefs);
 809
 810         SGEN_TV_GETTIME (btv);
 811         step_7 = SGEN_TV_ELAPSED (atv, btv);
 812
 813         /*Release for finalization those objects we no longer care. */
 814         for (i = 0; i < num_sccs; ++i) {
 815                 if (!api_sccs [i]->objs [0])
 816                         continue;
 817                 for (j = 0; j < api_sccs [i]->num_objs; ++j)
 818                         mono_sgen_mark_bridge_object (api_sccs [i]->objs [j]);
 819         }
 820
 821         /* free callback data */
 822
 823         for (i = 0; i < num_sccs; ++i) {
 824                 mono_sgen_free_internal_dynamic (api_sccs [i],
 825                                 sizeof (MonoGCBridgeSCC) + sizeof (MonoObject*) * api_sccs [i]->num_objs,
 826                                 INTERNAL_MEM_BRIDGE_DATA);
 827         }
 828         mono_sgen_free_internal_dynamic (api_sccs, sizeof (MonoGCBridgeSCC*) * num_sccs, INTERNAL_MEM_BRIDGE_DATA);
 829
 830         mono_sgen_free_internal_dynamic (api_xrefs, sizeof (MonoGCBridgeXRef) * num_xrefs, INTERNAL_MEM_BRIDGE_DATA);
 831
 832         SGEN_TV_GETTIME (atv);
 833         step_8 = SGEN_TV_ELAPSED (btv, atv);
 834
 835         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",
 836                 num_registered_bridges, hash_table_size, sccs.size,
 837                 step_1 / 1000.0f,
 838                 step_2 / 1000.0f,
 839                 step_3 / 1000.0f,
 840                 step_4 / 1000.0f,
 841                 step_5 / 1000.0f,
 842                 step_6 / 1000.0f,
 843                 step_7 / 1000.0f,
 844                 step_8 / 1000.f,
 845                 fist_pass_links, second_pass_links, sccs_links, max_sccs_links,
 846                 dsf1_passes, dsf2_passes);
 847
 848         step_1 = 0; /* We must cleanup since this value is used as an accumulator. */
 849 }
 850
 851 static gboolean
 852 bridge_test_is_bridge_object (MonoObject *obj)
 853 {
 854         return TRUE;
 855 }
 856
 857 static void
 858 bridge_test_cross_reference (int num_sccs, MonoGCBridgeSCC **sccs, int num_xrefs, MonoGCBridgeXRef *xrefs)
 859 {
 860         int i;
 861         for (i = 0; i < num_sccs; ++i) {
 862                 int j;
 863                 g_print ("--- SCC %d\n", i);
 864                 for (j = 0; j < sccs [i]->num_objs; ++j)
 865                         g_print ("  %s\n", mono_sgen_safe_name (sccs [i]->objs [j]));
 866         }
 867         for (i = 0; i < num_xrefs; ++i) {
 868                 g_assert (xrefs [i].src_scc_index >= 0 && xrefs [i].src_scc_index < num_sccs);
 869                 g_assert (xrefs [i].dst_scc_index >= 0 && xrefs [i].dst_scc_index < num_sccs);
 870                 g_print ("%d -> %d\n", xrefs [i].src_scc_index, xrefs [i].dst_scc_index);
 871         }
 872 }
 873
 874
 875 void
 876 mono_sgen_register_test_bridge_callbacks (void)
 877 {
 878         MonoGCBridgeCallbacks callbacks;
 879         callbacks.is_bridge_object = bridge_test_is_bridge_object;
 880         callbacks.cross_references = bridge_test_cross_reference;
 881         mono_gc_register_bridge_callbacks (&callbacks);
 882 }
 883
 884 #endif