mono/metadata/sgen-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 "utils/mono-logger-internal.h"
  49 #include "utils/mono-time.h"
  50
  51
  52 typedef struct {
  53         int size;
  54         int elem_size;
  55         int capacity;
  56         char *data;
  57 } DynArray;
  58
  59 #define DYN_ARRAY_REF(da,i)     ((void*)((da)->data + (i) * (da)->elem_size))
  60 #define DYN_ARRAY_PTR_REF(da,i) (((void**)(da)->data) [(i)])
  61 #define DYN_ARRAY_INT_REF(da,i) (((int*)(da)->data) [(i)])
  62 #define DYN_ARRAY_PTR_STATIC_INITIALIZER { 0, sizeof (void*), 0, NULL }
  63 #define DYN_ARRAY_INT_STATIC_INITIALIZER { 0, sizeof (int), 0, NULL }
  64
  65 static void
  66 dyn_array_init (DynArray *da, int elem_size)
  67 {
  68         da->size = 0;
  69         da->elem_size = elem_size;
  70         da->capacity = 0;
  71         da->data = NULL;
  72 }
  73
  74 static void
  75 dyn_array_ptr_init (DynArray *da)
  76 {
  77         dyn_array_init (da, sizeof (void*));
  78 }
  79
  80 static void
  81 dyn_array_int_init (DynArray *da)
  82 {
  83         dyn_array_init (da, sizeof (int));
  84 }
  85
  86 static void
  87 dyn_array_uninit (DynArray *da)
  88 {
  89         if (da->capacity <= 0)
  90                 return;
  91
  92         mono_sgen_free_internal_dynamic (da->data, da->elem_size * da->capacity, INTERNAL_MEM_BRIDGE_DATA);
  93         da->data = NULL;
  94 }
  95
  96 static void
  97 dyn_array_ensure_capacity (DynArray *da, int capacity)
  98 {
  99         int old_capacity = da->capacity;
 100         char *new_data;
 101
 102         if (capacity <= old_capacity)
 103                 return;
 104
 105         if (da->capacity == 0)
 106                 da->capacity = 2;
 107         while (capacity > da->capacity)
 108                 da->capacity *= 2;
 109
 110         new_data = mono_sgen_alloc_internal_dynamic (da->elem_size * da->capacity, INTERNAL_MEM_BRIDGE_DATA);
 111         memcpy (new_data, da->data, da->elem_size * da->size);
 112         mono_sgen_free_internal_dynamic (da->data, da->elem_size * old_capacity, INTERNAL_MEM_BRIDGE_DATA);
 113         da->data = new_data;
 114 }
 115
 116 static void*
 117 dyn_array_add (DynArray *da)
 118 {
 119         void *p;
 120
 121         dyn_array_ensure_capacity (da, da->size + 1);
 122
 123         p = DYN_ARRAY_REF (da, da->size);
 124         ++da->size;
 125         return p;
 126 }
 127
 128 static void
 129 dyn_array_ptr_add (DynArray *da, void *ptr)
 130 {
 131         void **p = dyn_array_add (da);
 132         *p = ptr;
 133 }
 134
 135 #define dyn_array_ptr_push dyn_array_ptr_add
 136
 137 static void*
 138 dyn_array_ptr_pop (DynArray *da)
 139 {
 140         void *p;
 141         g_assert (da->size > 0);
 142         p = DYN_ARRAY_PTR_REF (da, da->size - 1);
 143         --da->size;
 144         return p;
 145 }
 146
 147 static void
 148 dyn_array_int_add (DynArray *da, int x)
 149 {
 150         int *p = dyn_array_add (da);
 151         *p = x;
 152 }
 153
 154 /*
 155 static gboolean
 156 dyn_array_ptr_contains (DynArray *da, void *ptr)
 157 {
 158         int i;
 159         for (i = 0; i < da->size; ++i)
 160                 if (DYN_ARRAY_PTR_REF (da, i) == ptr)
 161                         return TRUE;
 162         return FALSE;
 163 }
 164 */
 165
 166 static gboolean
 167 dyn_array_int_contains (DynArray *da, int x)
 168 {
 169         int i;
 170         for (i = 0; i < da->size; ++i)
 171                 if (DYN_ARRAY_INT_REF (da, i) == x)
 172                         return TRUE;
 173         return FALSE;
 174 }
 175
 176 static DynArray merge_array;
 177
 178 static void
 179 dyn_array_int_merge (DynArray *dst, DynArray *src)
 180 {
 181         int i, j;
 182
 183         dyn_array_ensure_capacity (&merge_array, dst->size + src->size);
 184         merge_array.size = 0;
 185
 186         for (i = j = 0; i < dst->size || j < src->size; ) {
 187                 if (i < dst->size && j < src->size) {
 188                         int a = DYN_ARRAY_INT_REF (dst, i);
 189                         int b = DYN_ARRAY_INT_REF (src, j);
 190                         if (a < b) {
 191                                 dyn_array_int_add (&merge_array, a);
 192                                 ++i;
 193                         } else if (a == b) {
 194                                 dyn_array_int_add (&merge_array, a);
 195                                 ++i;
 196                                 ++j;
 197                         } else {
 198                                 dyn_array_int_add (&merge_array, b);
 199                                 ++j;
 200                         }
 201                 } else if (i < dst->size) {
 202                         dyn_array_int_add (&merge_array, DYN_ARRAY_INT_REF (dst, i));
 203                         ++i;
 204                 } else {
 205                         dyn_array_int_add (&merge_array, DYN_ARRAY_INT_REF (src, j));
 206                         ++j;
 207                 }
 208         }
 209
 210         if (merge_array.size > dst->size) {
 211                 dyn_array_ensure_capacity (dst, merge_array.size);
 212                 memcpy (DYN_ARRAY_REF (dst, 0), DYN_ARRAY_REF (&merge_array, 0), merge_array.size * merge_array.elem_size);
 213                 dst->size = merge_array.size;
 214         }
 215 }
 216
 217 static void
 218 dyn_array_int_merge_one (DynArray *array, int value)
 219 {
 220         int i;
 221         int tmp;
 222         int end = array->size;
 223
 224         for (i = 0; i < end; ++i) {
 225                 if (DYN_ARRAY_INT_REF (array, i) == value)
 226                         return;
 227                 else if (DYN_ARRAY_INT_REF (array, i) > value)
 228                         break;
 229         }
 230
 231         dyn_array_ensure_capacity (array, array->size + 1);
 232
 233         if (i < end) {
 234                 tmp = DYN_ARRAY_INT_REF (array, i);
 235                 for (; i <= end; ++i) {
 236                         DYN_ARRAY_INT_REF (array, i) = value;
 237                         value = tmp;
 238                         tmp = DYN_ARRAY_INT_REF (array, i + 1);
 239                 }
 240                 DYN_ARRAY_INT_REF (array, end + 1) = tmp;
 241         } else {
 242                 DYN_ARRAY_INT_REF (array, end) = value;
 243         }
 244         ++array->size;
 245 }
 246
 247 /*
 248  * FIXME: Optimizations:
 249  *
 250  * Don't allocate a scrs array for just one source.  Most objects have
 251  * just one source, so use the srcs pointer itself.
 252  */
 253 typedef struct _HashEntry {
 254         MonoObject *obj;        /* This is a duplicate - it's already stored in the hash table */
 255
 256         gboolean is_bridge;
 257         gboolean is_visited;
 258
 259         int finishing_time;
 260
 261         DynArray srcs;
 262
 263         int scc_index;
 264 } HashEntry;
 265
 266 typedef struct _SCC {
 267         int index;
 268         int api_index;
 269         int num_bridge_entries;
 270         DynArray xrefs;         /* these are incoming, not outgoing */
 271 } SCC;
 272
 273 static SgenHashTable hash_table = SGEN_HASH_TABLE_INIT (INTERNAL_MEM_BRIDGE_DATA, INTERNAL_MEM_BRIDGE_DATA, sizeof (HashEntry), mono_aligned_addr_hash, 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         if (callbacks->bridge_version != MONO_SGEN_BRIDGE_VERSION)
 283                 g_error ("Invalid bridge callback version. Expected %d but got %d\n", MONO_SGEN_BRIDGE_VERSION, callbacks->bridge_version);
 284
 285         bridge_callbacks = *callbacks;
 286 }
 287
 288 gboolean
 289 mono_sgen_is_bridge_object (MonoObject *obj)
 290 {
 291         if ((obj->vtable->gc_bits & SGEN_GC_BIT_BRIDGE_OBJECT) != SGEN_GC_BIT_BRIDGE_OBJECT)
 292                 return FALSE;
 293         return bridge_callbacks.is_bridge_object (obj);
 294 }
 295
 296 gboolean
 297 mono_sgen_is_bridge_class (MonoClass *class)
 298 {
 299         return bridge_callbacks.is_bridge_class (class);
 300 }
 301
 302 gboolean
 303 mono_sgen_need_bridge_processing (void)
 304 {
 305         return bridge_callbacks.cross_references != NULL;
 306 }
 307
 308 static HashEntry*
 309 get_hash_entry (MonoObject *obj, gboolean *existing)
 310 {
 311         HashEntry *entry = mono_sgen_hash_table_lookup (&hash_table, obj);
 312         HashEntry new_entry;
 313
 314         if (entry) {
 315                 if (existing)
 316                         *existing = TRUE;
 317                 return entry;
 318         }
 319         if (existing)
 320                 *existing = FALSE;
 321
 322         memset (&new_entry, 0, sizeof (HashEntry));
 323
 324         new_entry.obj = obj;
 325         dyn_array_ptr_init (&new_entry.srcs);
 326         new_entry.finishing_time = -1;
 327         new_entry.scc_index = -1;
 328
 329         mono_sgen_hash_table_replace (&hash_table, obj, &new_entry);
 330
 331         return mono_sgen_hash_table_lookup (&hash_table, obj);
 332 }
 333
 334 static void
 335 add_source (HashEntry *entry, HashEntry *src)
 336 {
 337         dyn_array_ptr_add (&entry->srcs, src);
 338 }
 339
 340 static void
 341 free_data (void)
 342 {
 343         MonoObject *obj;
 344         HashEntry *entry;
 345         int total_srcs = 0;
 346         int max_srcs = 0;
 347
 348         SGEN_HASH_TABLE_FOREACH (&hash_table, obj, entry) {
 349                 total_srcs += entry->srcs.size;
 350                 if (entry->srcs.size > max_srcs)
 351                         max_srcs = entry->srcs.size;
 352                 dyn_array_uninit (&entry->srcs);
 353         } SGEN_HASH_TABLE_FOREACH_END;
 354
 355         mono_sgen_hash_table_clean (&hash_table);
 356
 357         dyn_array_uninit (&merge_array);
 358         //g_print ("total srcs %d - max %d\n", total_srcs, max_srcs);
 359 }
 360
 361 static HashEntry*
 362 register_bridge_object (MonoObject *obj)
 363 {
 364         HashEntry *entry = get_hash_entry (obj, NULL);
 365         entry->is_bridge = TRUE;
 366         return entry;
 367 }
 368
 369 static void
 370 register_finishing_time (HashEntry *entry, int t)
 371 {
 372         g_assert (entry->finishing_time < 0);
 373         entry->finishing_time = t;
 374 }
 375
 376 static gboolean
 377 object_is_live (MonoObject **objp)
 378 {
 379         MonoObject *obj = *objp;
 380         MonoObject *fwd = SGEN_OBJECT_IS_FORWARDED (obj);
 381         if (fwd) {
 382                 *objp = fwd;
 383                 return mono_sgen_hash_table_lookup (&hash_table, fwd) == NULL;
 384         }
 385         if (!mono_sgen_object_is_live (obj))
 386                 return FALSE;
 387         return mono_sgen_hash_table_lookup (&hash_table, obj) == NULL;
 388 }
 389
 390 static DynArray registered_bridges = DYN_ARRAY_PTR_STATIC_INITIALIZER;
 391 static DynArray dfs_stack;
 392
 393 static int dsf1_passes, dsf2_passes;
 394
 395
 396 #undef HANDLE_PTR
 397 #define HANDLE_PTR(ptr,obj)     do {                                    \
 398                 MonoObject *dst = (MonoObject*)*(ptr);                  \
 399                 if (dst && !object_is_live (&dst)) {                    \
 400                         dyn_array_ptr_push (&dfs_stack, obj_entry);     \
 401                         dyn_array_ptr_push (&dfs_stack, get_hash_entry (dst, NULL)); \
 402                 }                                                       \
 403         } while (0)
 404
 405 static void
 406 dfs1 (HashEntry *obj_entry, HashEntry *src)
 407 {
 408         g_assert (dfs_stack.size == 0);
 409
 410         dyn_array_ptr_push (&dfs_stack, src);
 411         dyn_array_ptr_push (&dfs_stack, obj_entry);
 412
 413         do {
 414                 MonoObject *obj;
 415                 char *start;
 416                 ++dsf1_passes;
 417
 418                 obj_entry = dyn_array_ptr_pop (&dfs_stack);
 419                 if (obj_entry) {
 420                         src = dyn_array_ptr_pop (&dfs_stack);
 421
 422                         obj = obj_entry->obj;
 423                         start = (char*)obj;
 424
 425                         if (src) {
 426                                 //g_print ("link %s -> %s\n", mono_sgen_safe_name (src->obj), mono_sgen_safe_name (obj));
 427                                 add_source (obj_entry, src);
 428                         } else {
 429                                 //g_print ("starting with %s\n", mono_sgen_safe_name (obj));
 430                         }
 431
 432                         if (obj_entry->is_visited)
 433                                 continue;
 434
 435                         obj_entry->is_visited = TRUE;
 436
 437                         dyn_array_ptr_push (&dfs_stack, obj_entry);
 438                         /* NULL marks that the next entry is to be finished */
 439                         dyn_array_ptr_push (&dfs_stack, NULL);
 440
 441 #include "sgen-scan-object.h"
 442                 } else {
 443                         obj_entry = dyn_array_ptr_pop (&dfs_stack);
 444
 445                         //g_print ("finish %s\n", mono_sgen_safe_name (obj_entry->obj));
 446                         register_finishing_time (obj_entry, current_time++);
 447                 }
 448         } while (dfs_stack.size > 0);
 449 }
 450
 451 static void
 452 scc_add_xref (SCC *src, SCC *dst)
 453 {
 454         g_assert (src != dst);
 455         g_assert (src->index != dst->index);
 456
 457         if (dyn_array_int_contains (&dst->xrefs, src->index))
 458                 return;
 459         if (src->num_bridge_entries) {
 460                 dyn_array_int_merge_one (&dst->xrefs, src->index);
 461         } else {
 462                 int i;
 463                 dyn_array_int_merge (&dst->xrefs, &src->xrefs);
 464                 for (i = 0; i < dst->xrefs.size; ++i)
 465                         g_assert (DYN_ARRAY_INT_REF (&dst->xrefs, i) != dst->index);
 466         }
 467 }
 468
 469 static void
 470 scc_add_entry (SCC *scc, HashEntry *entry)
 471 {
 472         g_assert (entry->scc_index < 0);
 473         entry->scc_index = scc->index;
 474         if (entry->is_bridge)
 475                 ++scc->num_bridge_entries;
 476 }
 477
 478 static DynArray sccs;
 479 static SCC *current_scc;
 480
 481 static void
 482 dfs2 (HashEntry *entry)
 483 {
 484         int i;
 485
 486         g_assert (dfs_stack.size == 0);
 487
 488         dyn_array_ptr_push (&dfs_stack, entry);
 489
 490         do {
 491                 entry = dyn_array_ptr_pop (&dfs_stack);
 492                 ++dsf2_passes;
 493
 494                 if (entry->scc_index >= 0) {
 495                         if (entry->scc_index != current_scc->index)
 496                                 scc_add_xref (DYN_ARRAY_REF (&sccs, entry->scc_index), current_scc);
 497                         continue;
 498                 }
 499
 500                 scc_add_entry (current_scc, entry);
 501
 502                 for (i = 0; i < entry->srcs.size; ++i)
 503                         dyn_array_ptr_push (&dfs_stack, DYN_ARRAY_PTR_REF (&entry->srcs, i));
 504         } while (dfs_stack.size > 0);
 505 }
 506
 507 static int
 508 compare_hash_entries (const void *ep1, const void *ep2)
 509 {
 510         HashEntry *e1 = *(HashEntry**)ep1;
 511         HashEntry *e2 = *(HashEntry**)ep2;
 512         return e2->finishing_time - e1->finishing_time;
 513 }
 514
 515 static unsigned long step_1, step_2, step_3, step_4, step_5, step_6, step_7, step_8;
 516 static int fist_pass_links, second_pass_links, sccs_links;
 517 static int max_sccs_links = 0;
 518
 519 void
 520 mono_sgen_bridge_register_finalized_object (MonoObject *obj)
 521 {
 522         g_assert (mono_sgen_need_bridge_processing ());
 523         dyn_array_ptr_push (&registered_bridges, obj);
 524 }
 525
 526 void
 527 mono_sgen_bridge_reset_data (void)
 528 {
 529         registered_bridges.size = 0;
 530 }
 531
 532 void
 533 mono_sgen_bridge_processing_stw_step (void)
 534 {
 535         int i;
 536         SGEN_TV_DECLARE (atv);
 537         SGEN_TV_DECLARE (btv);
 538
 539         if (!registered_bridges.size)
 540                 return;
 541
 542         SGEN_TV_GETTIME (btv);
 543
 544         /* first DFS pass */
 545
 546         dyn_array_ptr_init (&dfs_stack);
 547         dyn_array_int_init (&merge_array);
 548
 549         current_time = 0;
 550         for (i = 0; i < registered_bridges.size; ++i)
 551                 dfs1 (register_bridge_object (DYN_ARRAY_PTR_REF (&registered_bridges, i)), NULL);
 552
 553         SGEN_TV_GETTIME (atv);
 554         step_2 = SGEN_TV_ELAPSED (btv, atv);
 555 }
 556
 557 void
 558 mono_sgen_bridge_processing_finish (void)
 559 {
 560         int i, j;
 561         int num_sccs, num_xrefs;
 562         int max_entries, max_xrefs;
 563         int hash_table_size, sccs_size;
 564         MonoObject *obj;
 565         HashEntry *entry;
 566         int num_registered_bridges;
 567         HashEntry **all_entries;
 568         MonoGCBridgeSCC **api_sccs;
 569         MonoGCBridgeXRef *api_xrefs;
 570         SGEN_TV_DECLARE (atv);
 571         SGEN_TV_DECLARE (btv);
 572
 573         if (!registered_bridges.size)
 574                 return;
 575
 576         SGEN_TV_GETTIME (atv);
 577
 578         /* alloc and fill array of all entries */
 579
 580         all_entries = mono_sgen_alloc_internal_dynamic (sizeof (HashEntry*) * hash_table.num_entries, INTERNAL_MEM_BRIDGE_DATA);
 581
 582         j = 0;
 583         SGEN_HASH_TABLE_FOREACH (&hash_table, obj, entry) {
 584                 g_assert (entry->finishing_time >= 0);
 585                 all_entries [j++] = entry;
 586                 fist_pass_links += entry->srcs.size;
 587         } SGEN_HASH_TABLE_FOREACH_END;
 588         g_assert (j == hash_table.num_entries);
 589         hash_table_size = hash_table.num_entries;
 590
 591         /* sort array according to decreasing finishing time */
 592
 593         qsort (all_entries, hash_table.num_entries, sizeof (HashEntry*), compare_hash_entries);
 594
 595         SGEN_TV_GETTIME (btv);
 596         step_3 = SGEN_TV_ELAPSED (atv, btv);
 597
 598         /* second DFS pass */
 599
 600         dyn_array_init (&sccs, sizeof (SCC));
 601         for (i = 0; i < hash_table.num_entries; ++i) {
 602                 HashEntry *entry = all_entries [i];
 603                 if (entry->scc_index < 0) {
 604                         int index = sccs.size;
 605                         current_scc = dyn_array_add (&sccs);
 606                         current_scc->index = index;
 607                         current_scc->num_bridge_entries = 0;
 608                         current_scc->api_index = -1;
 609                         dyn_array_int_init (&current_scc->xrefs);
 610
 611                         dfs2 (entry);
 612                 }
 613         }
 614
 615         sccs_size = sccs.size;
 616
 617         for (i = 0; i < hash_table.num_entries; ++i) {
 618                 HashEntry *entry = all_entries [i];
 619                 second_pass_links += entry->srcs.size;
 620         }
 621
 622         SGEN_TV_GETTIME (atv);
 623         step_4 = SGEN_TV_ELAPSED (btv, atv);
 624
 625         //g_print ("%d sccs\n", sccs.size);
 626
 627         dyn_array_uninit (&dfs_stack);
 628
 629         /* init data for callback */
 630
 631         num_sccs = 0;
 632         for (i = 0; i < sccs.size; ++i) {
 633                 SCC *scc = DYN_ARRAY_REF (&sccs, i);
 634                 g_assert (scc->index == i);
 635                 if (scc->num_bridge_entries)
 636                         ++num_sccs;
 637                 sccs_links += scc->xrefs.size;
 638                 max_sccs_links = MAX (max_sccs_links, scc->xrefs.size);
 639         }
 640
 641         api_sccs = mono_sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC*) * num_sccs, INTERNAL_MEM_BRIDGE_DATA);
 642         num_xrefs = 0;
 643         j = 0;
 644         for (i = 0; i < sccs.size; ++i) {
 645                 SCC *scc = DYN_ARRAY_REF (&sccs, i);
 646                 if (!scc->num_bridge_entries)
 647                         continue;
 648
 649                 api_sccs [j] = mono_sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC) + sizeof (MonoObject*) * scc->num_bridge_entries, INTERNAL_MEM_BRIDGE_DATA);
 650                 api_sccs [j]->num_objs = scc->num_bridge_entries;
 651                 scc->num_bridge_entries = 0;
 652                 scc->api_index = j++;
 653
 654                 num_xrefs += scc->xrefs.size;
 655         }
 656
 657         SGEN_HASH_TABLE_FOREACH (&hash_table, obj, entry) {
 658                 if (entry->is_bridge) {
 659                         SCC *scc = DYN_ARRAY_REF (&sccs, entry->scc_index);
 660                         api_sccs [scc->api_index]->objs [scc->num_bridge_entries++] = entry->obj;
 661                 }
 662         } SGEN_HASH_TABLE_FOREACH_END;
 663
 664         api_xrefs = mono_sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeXRef) * num_xrefs, INTERNAL_MEM_BRIDGE_DATA);
 665         j = 0;
 666         for (i = 0; i < sccs.size; ++i) {
 667                 int k;
 668                 SCC *scc = DYN_ARRAY_REF (&sccs, i);
 669                 if (!scc->num_bridge_entries)
 670                         continue;
 671                 for (k = 0; k < scc->xrefs.size; ++k) {
 672                         SCC *src_scc = DYN_ARRAY_REF (&sccs, DYN_ARRAY_INT_REF (&scc->xrefs, k));
 673                         if (!src_scc->num_bridge_entries)
 674                                 continue;
 675                         api_xrefs [j].src_scc_index = src_scc->api_index;
 676                         api_xrefs [j].dst_scc_index = scc->api_index;
 677                         ++j;
 678                 }
 679         }
 680
 681         SGEN_TV_GETTIME (btv);
 682         step_5 = SGEN_TV_ELAPSED (atv, btv);
 683
 684         /* free data */
 685
 686         j = 0;
 687         max_entries = max_xrefs = 0;
 688         for (i = 0; i < sccs.size; ++i) {
 689                 SCC *scc = DYN_ARRAY_REF (&sccs, i);
 690                 if (scc->num_bridge_entries)
 691                         ++j;
 692                 if (scc->num_bridge_entries > max_entries)
 693                         max_entries = scc->num_bridge_entries;
 694                 if (scc->xrefs.size > max_xrefs)
 695                         max_xrefs = scc->xrefs.size;
 696                 dyn_array_uninit (&scc->xrefs);
 697
 698         }
 699         dyn_array_uninit (&sccs);
 700
 701         mono_sgen_free_internal_dynamic (all_entries, sizeof (HashEntry*) * hash_table.num_entries, INTERNAL_MEM_BRIDGE_DATA);
 702
 703         free_data ();
 704         /* Empty the registered bridges array */
 705         num_registered_bridges = registered_bridges.size;
 706         registered_bridges.size = 0;
 707
 708         SGEN_TV_GETTIME (atv);
 709         step_6 = SGEN_TV_ELAPSED (btv, atv);
 710
 711         //g_print ("%d sccs containing bridges - %d max bridge objects - %d max xrefs\n", j, max_entries, max_xrefs);
 712
 713         /* callback */
 714
 715         bridge_callbacks.cross_references (num_sccs, api_sccs, num_xrefs, api_xrefs);
 716
 717 /*Release for finalization those objects we no longer care. */
 718         SGEN_TV_GETTIME (btv);
 719         step_7 = SGEN_TV_ELAPSED (atv, btv);
 720
 721         for (i = 0; i < num_sccs; ++i) {
 722                 if (!api_sccs [i]->objs [0])
 723                         continue;
 724                 for (j = 0; j < api_sccs [i]->num_objs; ++j)
 725                         mono_sgen_mark_bridge_object (api_sccs [i]->objs [j]);
 726         }
 727
 728         /* free callback data */
 729
 730         for (i = 0; i < num_sccs; ++i) {
 731                 mono_sgen_free_internal_dynamic (api_sccs [i],
 732                                 sizeof (MonoGCBridgeSCC) + sizeof (MonoObject*) * api_sccs [i]->num_objs,
 733                                 INTERNAL_MEM_BRIDGE_DATA);
 734         }
 735         mono_sgen_free_internal_dynamic (api_sccs, sizeof (MonoGCBridgeSCC*) * num_sccs, INTERNAL_MEM_BRIDGE_DATA);
 736
 737         mono_sgen_free_internal_dynamic (api_xrefs, sizeof (MonoGCBridgeXRef) * num_xrefs, INTERNAL_MEM_BRIDGE_DATA);
 738
 739         SGEN_TV_GETTIME (atv);
 740         step_8 = SGEN_TV_ELAPSED (btv, atv);
 741
 742         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",
 743                 num_registered_bridges, hash_table_size, sccs.size,
 744                 step_1 / 1000.0f,
 745                 step_2 / 1000.0f,
 746                 step_3 / 1000.0f,
 747                 step_4 / 1000.0f,
 748                 step_5 / 1000.0f,
 749                 step_6 / 1000.0f,
 750                 step_7 / 1000.0f,
 751                 step_8 / 1000.f,
 752                 fist_pass_links, second_pass_links, sccs_links, max_sccs_links,
 753                 dsf1_passes, dsf2_passes);
 754
 755         step_1 = 0; /* We must cleanup since this value is used as an accumulator. */
 756 }
 757
 758 static const char *bridge_class;
 759
 760 static gboolean
 761 bridge_test_is_bridge_class (MonoClass *class)
 762 {
 763         return !strcmp (bridge_class, class->name);
 764 }
 765
 766 static gboolean
 767 bridge_test_is_bridge_object (MonoObject *object)
 768 {
 769         return TRUE;
 770 }
 771
 772 static void
 773 bridge_test_cross_reference (int num_sccs, MonoGCBridgeSCC **sccs, int num_xrefs, MonoGCBridgeXRef *xrefs)
 774 {
 775         int i;
 776         for (i = 0; i < num_sccs; ++i) {
 777                 int j;
 778         //      g_print ("--- SCC %d\n", i);
 779                 for (j = 0; j < sccs [i]->num_objs; ++j) {
 780         //              g_print ("  %s\n", mono_sgen_safe_name (sccs [i]->objs [j]));
 781                         if (i & 1) /*retain half of the bridged objects */
 782                                 sccs [i]->objs [0] = NULL;
 783                 }
 784         }
 785         for (i = 0; i < num_xrefs; ++i) {
 786                 g_assert (xrefs [i].src_scc_index >= 0 && xrefs [i].src_scc_index < num_sccs);
 787                 g_assert (xrefs [i].dst_scc_index >= 0 && xrefs [i].dst_scc_index < num_sccs);
 788         //      g_print ("%d -> %d\n", xrefs [i].src_scc_index, xrefs [i].dst_scc_index);
 789         }
 790 }
 791
 792
 793 void
 794 mono_sgen_register_test_bridge_callbacks (const char *bridge_class_name)
 795 {
 796         MonoGCBridgeCallbacks callbacks;
 797         callbacks.bridge_version = MONO_SGEN_BRIDGE_VERSION;
 798         callbacks.is_bridge_class = bridge_test_is_bridge_class;
 799         callbacks.is_bridge_object = bridge_test_is_bridge_object;
 800         callbacks.cross_references = bridge_test_cross_reference;
 801         mono_gc_register_bridge_callbacks (&callbacks);
 802         bridge_class = bridge_class_name;
 803 }
 804
 805 #endif