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 "sgen-hash-table.h"
  49 #include "utils/mono-logger-internal.h"
  50 #include "utils/mono-time.h"
  51
  52
  53 typedef struct {
  54         int size;
  55         int elem_size;
  56         int capacity;
  57         char *data;
  58 } DynArray;
  59
  60 #define DYN_ARRAY_REF(da,i)     ((void*)((da)->data + (i) * (da)->elem_size))
  61 #define DYN_ARRAY_PTR_REF(da,i) (((void**)(da)->data) [(i)])
  62 #define DYN_ARRAY_INT_REF(da,i) (((int*)(da)->data) [(i)])
  63 #define DYN_ARRAY_PTR_STATIC_INITIALIZER { 0, sizeof (void*), 0, NULL }
  64 #define DYN_ARRAY_INT_STATIC_INITIALIZER { 0, sizeof (int), 0, NULL }
  65
  66 static void
  67 dyn_array_init (DynArray *da, int elem_size)
  68 {
  69         da->size = 0;
  70         da->elem_size = elem_size;
  71         da->capacity = 0;
  72         da->data = NULL;
  73 }
  74
  75 static void
  76 dyn_array_ptr_init (DynArray *da)
  77 {
  78         dyn_array_init (da, sizeof (void*));
  79 }
  80
  81 static void
  82 dyn_array_int_init (DynArray *da)
  83 {
  84         dyn_array_init (da, sizeof (int));
  85 }
  86
  87 static void
  88 dyn_array_uninit (DynArray *da)
  89 {
  90         if (da->capacity <= 0)
  91                 return;
  92
  93         sgen_free_internal_dynamic (da->data, da->elem_size * da->capacity, INTERNAL_MEM_BRIDGE_DATA);
  94         da->data = NULL;
  95 }
  96
  97 static void
  98 dyn_array_ensure_capacity (DynArray *da, int capacity)
  99 {
 100         int old_capacity = da->capacity;
 101         char *new_data;
 102
 103         if (capacity <= old_capacity)
 104                 return;
 105
 106         if (da->capacity == 0)
 107                 da->capacity = 2;
 108         while (capacity > da->capacity)
 109                 da->capacity *= 2;
 110
 111         new_data = sgen_alloc_internal_dynamic (da->elem_size * da->capacity, INTERNAL_MEM_BRIDGE_DATA, TRUE);
 112         memcpy (new_data, da->data, da->elem_size * da->size);
 113         sgen_free_internal_dynamic (da->data, da->elem_size * old_capacity, INTERNAL_MEM_BRIDGE_DATA);
 114         da->data = new_data;
 115 }
 116
 117 static void*
 118 dyn_array_add (DynArray *da)
 119 {
 120         void *p;
 121
 122         dyn_array_ensure_capacity (da, da->size + 1);
 123
 124         p = DYN_ARRAY_REF (da, da->size);
 125         ++da->size;
 126         return p;
 127 }
 128
 129 static void
 130 dyn_array_ptr_add (DynArray *da, void *ptr)
 131 {
 132         void **p = dyn_array_add (da);
 133         *p = ptr;
 134 }
 135
 136 #define dyn_array_ptr_push dyn_array_ptr_add
 137
 138 static void*
 139 dyn_array_ptr_pop (DynArray *da)
 140 {
 141         void *p;
 142         g_assert (da->size > 0);
 143         p = DYN_ARRAY_PTR_REF (da, da->size - 1);
 144         --da->size;
 145         return p;
 146 }
 147
 148 static void
 149 dyn_array_int_add (DynArray *da, int x)
 150 {
 151         int *p = dyn_array_add (da);
 152         *p = x;
 153 }
 154
 155 /*
 156 static gboolean
 157 dyn_array_ptr_contains (DynArray *da, void *ptr)
 158 {
 159         int i;
 160         for (i = 0; i < da->size; ++i)
 161                 if (DYN_ARRAY_PTR_REF (da, i) == ptr)
 162                         return TRUE;
 163         return FALSE;
 164 }
 165 */
 166
 167 static gboolean
 168 dyn_array_int_contains (DynArray *da, int x)
 169 {
 170         int i;
 171         for (i = 0; i < da->size; ++i)
 172                 if (DYN_ARRAY_INT_REF (da, i) == x)
 173                         return TRUE;
 174         return FALSE;
 175 }
 176
 177 static DynArray merge_array;
 178
 179 static void
 180 dyn_array_int_merge (DynArray *dst, DynArray *src)
 181 {
 182         int i, j;
 183
 184         dyn_array_ensure_capacity (&merge_array, dst->size + src->size);
 185         merge_array.size = 0;
 186
 187         for (i = j = 0; i < dst->size || j < src->size; ) {
 188                 if (i < dst->size && j < src->size) {
 189                         int a = DYN_ARRAY_INT_REF (dst, i);
 190                         int b = DYN_ARRAY_INT_REF (src, j);
 191                         if (a < b) {
 192                                 dyn_array_int_add (&merge_array, a);
 193                                 ++i;
 194                         } else if (a == b) {
 195                                 dyn_array_int_add (&merge_array, a);
 196                                 ++i;
 197                                 ++j;
 198                         } else {
 199                                 dyn_array_int_add (&merge_array, b);
 200                                 ++j;
 201                         }
 202                 } else if (i < dst->size) {
 203                         dyn_array_int_add (&merge_array, DYN_ARRAY_INT_REF (dst, i));
 204                         ++i;
 205                 } else {
 206                         dyn_array_int_add (&merge_array, DYN_ARRAY_INT_REF (src, j));
 207                         ++j;
 208                 }
 209         }
 210
 211         if (merge_array.size > dst->size) {
 212                 dyn_array_ensure_capacity (dst, merge_array.size);
 213                 memcpy (DYN_ARRAY_REF (dst, 0), DYN_ARRAY_REF (&merge_array, 0), merge_array.size * merge_array.elem_size);
 214                 dst->size = merge_array.size;
 215         }
 216 }
 217
 218 static void
 219 dyn_array_int_merge_one (DynArray *array, int value)
 220 {
 221         int i;
 222         int tmp;
 223         int end = array->size;
 224
 225         for (i = 0; i < end; ++i) {
 226                 if (DYN_ARRAY_INT_REF (array, i) == value)
 227                         return;
 228                 else if (DYN_ARRAY_INT_REF (array, i) > value)
 229                         break;
 230         }
 231
 232         dyn_array_ensure_capacity (array, array->size + 1);
 233
 234         if (i < end) {
 235                 tmp = DYN_ARRAY_INT_REF (array, i);
 236                 for (; i <= end; ++i) {
 237                         DYN_ARRAY_INT_REF (array, i) = value;
 238                         value = tmp;
 239                         tmp = DYN_ARRAY_INT_REF (array, i + 1);
 240                 }
 241                 DYN_ARRAY_INT_REF (array, end + 1) = tmp;
 242         } else {
 243                 DYN_ARRAY_INT_REF (array, end) = value;
 244         }
 245         ++array->size;
 246 }
 247
 248 /*
 249  * FIXME: Optimizations:
 250  *
 251  * Don't allocate a scrs array for just one source.  Most objects have
 252  * just one source, so use the srcs pointer itself.
 253  */
 254 typedef struct _HashEntry {
 255         MonoObject *obj;        /* This is a duplicate - it's already stored in the hash table */
 256
 257         gboolean is_bridge;
 258         gboolean is_visited;
 259
 260         int finishing_time;
 261
 262         DynArray srcs;
 263
 264         int scc_index;
 265 } HashEntry;
 266
 267 typedef struct _SCC {
 268         int index;
 269         int api_index;
 270         int num_bridge_entries;
 271         DynArray xrefs;         /* these are incoming, not outgoing */
 272 } SCC;
 273
 274 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);
 275
 276 static MonoGCBridgeCallbacks bridge_callbacks;
 277
 278 static int current_time;
 279
 280 gboolean bridge_processing_in_progress = FALSE;
 281
 282 void
 283 mono_gc_wait_for_bridge_processing (void)
 284 {
 285         if (!bridge_processing_in_progress)
 286                 return;
 287
 288         mono_trace (G_LOG_LEVEL_INFO, MONO_TRACE_GC, "GC_BRIDGE waiting for bridge processing to finish");
 289
 290         sgen_gc_lock ();
 291         sgen_gc_unlock ();
 292 }
 293
 294 void
 295 mono_gc_register_bridge_callbacks (MonoGCBridgeCallbacks *callbacks)
 296 {
 297         if (callbacks->bridge_version != SGEN_BRIDGE_VERSION)
 298                 g_error ("Invalid bridge callback version. Expected %d but got %d\n", SGEN_BRIDGE_VERSION, callbacks->bridge_version);
 299
 300         bridge_callbacks = *callbacks;
 301 }
 302
 303 gboolean
 304 sgen_is_bridge_object (MonoObject *obj)
 305 {
 306         if ((obj->vtable->gc_bits & SGEN_GC_BIT_BRIDGE_OBJECT) != SGEN_GC_BIT_BRIDGE_OBJECT)
 307                 return FALSE;
 308         return bridge_callbacks.is_bridge_object (obj);
 309 }
 310
 311 gboolean
 312 sgen_is_bridge_class (MonoClass *class)
 313 {
 314         return bridge_callbacks.is_bridge_class (class);
 315 }
 316
 317 gboolean
 318 sgen_need_bridge_processing (void)
 319 {
 320         return bridge_callbacks.cross_references != NULL;
 321 }
 322
 323 static HashEntry*
 324 get_hash_entry (MonoObject *obj, gboolean *existing)
 325 {
 326         HashEntry *entry = sgen_hash_table_lookup (&hash_table, obj);
 327         HashEntry new_entry;
 328
 329         if (entry) {
 330                 if (existing)
 331                         *existing = TRUE;
 332                 return entry;
 333         }
 334         if (existing)
 335                 *existing = FALSE;
 336
 337         memset (&new_entry, 0, sizeof (HashEntry));
 338
 339         new_entry.obj = obj;
 340         dyn_array_ptr_init (&new_entry.srcs);
 341         new_entry.finishing_time = -1;
 342         new_entry.scc_index = -1;
 343
 344         sgen_hash_table_replace (&hash_table, obj, &new_entry, NULL);
 345
 346         return sgen_hash_table_lookup (&hash_table, obj);
 347 }
 348
 349 static void
 350 add_source (HashEntry *entry, HashEntry *src)
 351 {
 352         dyn_array_ptr_add (&entry->srcs, src);
 353 }
 354
 355 static void
 356 free_data (void)
 357 {
 358         MonoObject *obj;
 359         HashEntry *entry;
 360         int total_srcs = 0;
 361         int max_srcs = 0;
 362
 363         SGEN_HASH_TABLE_FOREACH (&hash_table, obj, entry) {
 364                 total_srcs += entry->srcs.size;
 365                 if (entry->srcs.size > max_srcs)
 366                         max_srcs = entry->srcs.size;
 367                 dyn_array_uninit (&entry->srcs);
 368         } SGEN_HASH_TABLE_FOREACH_END;
 369
 370         sgen_hash_table_clean (&hash_table);
 371
 372         dyn_array_uninit (&merge_array);
 373         //g_print ("total srcs %d - max %d\n", total_srcs, max_srcs);
 374 }
 375
 376 static HashEntry*
 377 register_bridge_object (MonoObject *obj)
 378 {
 379         HashEntry *entry = get_hash_entry (obj, NULL);
 380         entry->is_bridge = TRUE;
 381         return entry;
 382 }
 383
 384 static void
 385 register_finishing_time (HashEntry *entry, int t)
 386 {
 387         g_assert (entry->finishing_time < 0);
 388         entry->finishing_time = t;
 389 }
 390
 391 static gboolean
 392 object_is_live (MonoObject **objp)
 393 {
 394         MonoObject *obj = *objp;
 395         MonoObject *fwd = SGEN_OBJECT_IS_FORWARDED (obj);
 396         if (fwd) {
 397                 *objp = fwd;
 398                 return sgen_hash_table_lookup (&hash_table, fwd) == NULL;
 399         }
 400         if (!sgen_object_is_live (obj))
 401                 return FALSE;
 402         return sgen_hash_table_lookup (&hash_table, obj) == NULL;
 403 }
 404
 405 static DynArray registered_bridges = DYN_ARRAY_PTR_STATIC_INITIALIZER;
 406 static DynArray dfs_stack;
 407
 408 static int dsf1_passes, dsf2_passes;
 409
 410
 411 #undef HANDLE_PTR
 412 #define HANDLE_PTR(ptr,obj)     do {                                    \
 413                 MonoObject *dst = (MonoObject*)*(ptr);                  \
 414                 if (dst && !object_is_live (&dst)) {                    \
 415                         dyn_array_ptr_push (&dfs_stack, obj_entry);     \
 416                         dyn_array_ptr_push (&dfs_stack, get_hash_entry (dst, NULL)); \
 417                 }                                                       \
 418         } while (0)
 419
 420 static void
 421 dfs1 (HashEntry *obj_entry, HashEntry *src)
 422 {
 423         g_assert (dfs_stack.size == 0);
 424
 425         dyn_array_ptr_push (&dfs_stack, src);
 426         dyn_array_ptr_push (&dfs_stack, obj_entry);
 427
 428         do {
 429                 MonoObject *obj;
 430                 char *start;
 431                 ++dsf1_passes;
 432
 433                 obj_entry = dyn_array_ptr_pop (&dfs_stack);
 434                 if (obj_entry) {
 435                         src = dyn_array_ptr_pop (&dfs_stack);
 436
 437                         obj = obj_entry->obj;
 438                         start = (char*)obj;
 439
 440                         if (src) {
 441                                 //g_print ("link %s -> %s\n", sgen_safe_name (src->obj), sgen_safe_name (obj));
 442                                 add_source (obj_entry, src);
 443                         } else {
 444                                 //g_print ("starting with %s\n", sgen_safe_name (obj));
 445                         }
 446
 447                         if (obj_entry->is_visited)
 448                                 continue;
 449
 450                         obj_entry->is_visited = TRUE;
 451
 452                         dyn_array_ptr_push (&dfs_stack, obj_entry);
 453                         /* NULL marks that the next entry is to be finished */
 454                         dyn_array_ptr_push (&dfs_stack, NULL);
 455
 456 #include "sgen-scan-object.h"
 457                 } else {
 458                         obj_entry = dyn_array_ptr_pop (&dfs_stack);
 459
 460                         //g_print ("finish %s\n", sgen_safe_name (obj_entry->obj));
 461                         register_finishing_time (obj_entry, current_time++);
 462                 }
 463         } while (dfs_stack.size > 0);
 464 }
 465
 466 static void
 467 scc_add_xref (SCC *src, SCC *dst)
 468 {
 469         g_assert (src != dst);
 470         g_assert (src->index != dst->index);
 471
 472         if (dyn_array_int_contains (&dst->xrefs, src->index))
 473                 return;
 474         if (src->num_bridge_entries) {
 475                 dyn_array_int_merge_one (&dst->xrefs, src->index);
 476         } else {
 477                 int i;
 478                 dyn_array_int_merge (&dst->xrefs, &src->xrefs);
 479                 for (i = 0; i < dst->xrefs.size; ++i)
 480                         g_assert (DYN_ARRAY_INT_REF (&dst->xrefs, i) != dst->index);
 481         }
 482 }
 483
 484 static void
 485 scc_add_entry (SCC *scc, HashEntry *entry)
 486 {
 487         g_assert (entry->scc_index < 0);
 488         entry->scc_index = scc->index;
 489         if (entry->is_bridge)
 490                 ++scc->num_bridge_entries;
 491 }
 492
 493 static DynArray sccs;
 494 static SCC *current_scc;
 495
 496 static void
 497 dfs2 (HashEntry *entry)
 498 {
 499         int i;
 500
 501         g_assert (dfs_stack.size == 0);
 502
 503         dyn_array_ptr_push (&dfs_stack, entry);
 504
 505         do {
 506                 entry = dyn_array_ptr_pop (&dfs_stack);
 507                 ++dsf2_passes;
 508
 509                 if (entry->scc_index >= 0) {
 510                         if (entry->scc_index != current_scc->index)
 511                                 scc_add_xref (DYN_ARRAY_REF (&sccs, entry->scc_index), current_scc);
 512                         continue;
 513                 }
 514
 515                 scc_add_entry (current_scc, entry);
 516
 517                 for (i = 0; i < entry->srcs.size; ++i)
 518                         dyn_array_ptr_push (&dfs_stack, DYN_ARRAY_PTR_REF (&entry->srcs, i));
 519         } while (dfs_stack.size > 0);
 520 }
 521
 522 static int
 523 compare_hash_entries (const void *ep1, const void *ep2)
 524 {
 525         HashEntry *e1 = *(HashEntry**)ep1;
 526         HashEntry *e2 = *(HashEntry**)ep2;
 527         return e2->finishing_time - e1->finishing_time;
 528 }
 529
 530 static unsigned long step_1, step_2, step_3, step_4, step_5, step_6, step_7, step_8;
 531 static int fist_pass_links, second_pass_links, sccs_links;
 532 static int max_sccs_links = 0;
 533
 534 void
 535 sgen_bridge_register_finalized_object (MonoObject *obj)
 536 {
 537         g_assert (sgen_need_bridge_processing ());
 538         dyn_array_ptr_push (&registered_bridges, obj);
 539 }
 540
 541 void
 542 sgen_bridge_reset_data (void)
 543 {
 544         registered_bridges.size = 0;
 545 }
 546
 547 void
 548 sgen_bridge_processing_stw_step (void)
 549 {
 550         int i;
 551         SGEN_TV_DECLARE (atv);
 552         SGEN_TV_DECLARE (btv);
 553
 554         if (!registered_bridges.size)
 555                 return;
 556
 557         /*
 558          * bridge_processing_in_progress must be set with the world
 559          * stopped.  If not there would be race conditions.
 560          */
 561         bridge_processing_in_progress = TRUE;
 562
 563         SGEN_TV_GETTIME (btv);
 564
 565         /* first DFS pass */
 566
 567         dyn_array_ptr_init (&dfs_stack);
 568         dyn_array_int_init (&merge_array);
 569
 570         current_time = 0;
 571         /*
 572         First we insert all bridges into the hash table and then we do dfs1.
 573
 574         It must be done in 2 steps since the bridge arrays doesn't come in reverse topological order,
 575         which means that we can have entry N pointing to entry N + 1.
 576
 577         If we dfs1 entry N before N + 1 is registered we'll not consider N + 1 for this bridge
 578         pass and not create the required xref between the two.
 579         */
 580         for (i = 0; i < registered_bridges.size; ++i)
 581                 register_bridge_object (DYN_ARRAY_PTR_REF (&registered_bridges, i));
 582
 583         for (i = 0; i < registered_bridges.size; ++i)
 584                 dfs1 (get_hash_entry (DYN_ARRAY_PTR_REF (&registered_bridges, i), NULL), NULL);
 585
 586         SGEN_TV_GETTIME (atv);
 587         step_2 = SGEN_TV_ELAPSED (btv, atv);
 588 }
 589
 590 static mono_bool
 591 is_bridge_object_alive (MonoObject *obj, void *data)
 592 {
 593         SgenHashTable *table = data;
 594         unsigned char *value = sgen_hash_table_lookup (table, obj);
 595         if (!value)
 596                 return TRUE;
 597         return *value;
 598 }
 599
 600 void
 601 sgen_bridge_processing_finish (int generation)
 602 {
 603         int i, j;
 604         int num_sccs, num_xrefs;
 605         int max_entries, max_xrefs;
 606         int hash_table_size, sccs_size;
 607         MonoObject *obj;
 608         HashEntry *entry;
 609         int num_registered_bridges;
 610         HashEntry **all_entries;
 611         MonoGCBridgeSCC **api_sccs;
 612         MonoGCBridgeXRef *api_xrefs;
 613         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);
 614         SGEN_TV_DECLARE (atv);
 615         SGEN_TV_DECLARE (btv);
 616
 617         if (!registered_bridges.size)
 618                 return;
 619
 620         g_assert (bridge_processing_in_progress);
 621
 622         SGEN_TV_GETTIME (atv);
 623
 624         /* alloc and fill array of all entries */
 625
 626         all_entries = sgen_alloc_internal_dynamic (sizeof (HashEntry*) * hash_table.num_entries, INTERNAL_MEM_BRIDGE_DATA, TRUE);
 627
 628         j = 0;
 629         SGEN_HASH_TABLE_FOREACH (&hash_table, obj, entry) {
 630                 g_assert (entry->finishing_time >= 0);
 631                 all_entries [j++] = entry;
 632                 fist_pass_links += entry->srcs.size;
 633         } SGEN_HASH_TABLE_FOREACH_END;
 634         g_assert (j == hash_table.num_entries);
 635         hash_table_size = hash_table.num_entries;
 636
 637         /* sort array according to decreasing finishing time */
 638
 639         sgen_qsort (all_entries, hash_table.num_entries, sizeof (HashEntry*), compare_hash_entries);
 640
 641         SGEN_TV_GETTIME (btv);
 642         step_3 = SGEN_TV_ELAPSED (atv, btv);
 643
 644         /* second DFS pass */
 645
 646         dyn_array_init (&sccs, sizeof (SCC));
 647         for (i = 0; i < hash_table.num_entries; ++i) {
 648                 HashEntry *entry = all_entries [i];
 649                 if (entry->scc_index < 0) {
 650                         int index = sccs.size;
 651                         current_scc = dyn_array_add (&sccs);
 652                         current_scc->index = index;
 653                         current_scc->num_bridge_entries = 0;
 654                         current_scc->api_index = -1;
 655                         dyn_array_int_init (&current_scc->xrefs);
 656
 657                         dfs2 (entry);
 658                 }
 659         }
 660
 661         sccs_size = sccs.size;
 662
 663         for (i = 0; i < hash_table.num_entries; ++i) {
 664                 HashEntry *entry = all_entries [i];
 665                 second_pass_links += entry->srcs.size;
 666         }
 667
 668         SGEN_TV_GETTIME (atv);
 669         step_4 = SGEN_TV_ELAPSED (btv, atv);
 670
 671         //g_print ("%d sccs\n", sccs.size);
 672
 673         dyn_array_uninit (&dfs_stack);
 674
 675         /* init data for callback */
 676
 677         num_sccs = 0;
 678         for (i = 0; i < sccs.size; ++i) {
 679                 SCC *scc = DYN_ARRAY_REF (&sccs, i);
 680                 g_assert (scc->index == i);
 681                 if (scc->num_bridge_entries)
 682                         ++num_sccs;
 683                 sccs_links += scc->xrefs.size;
 684                 max_sccs_links = MAX (max_sccs_links, scc->xrefs.size);
 685         }
 686
 687         api_sccs = sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC*) * num_sccs, INTERNAL_MEM_BRIDGE_DATA, TRUE);
 688         num_xrefs = 0;
 689         j = 0;
 690         for (i = 0; i < sccs.size; ++i) {
 691                 SCC *scc = DYN_ARRAY_REF (&sccs, i);
 692                 if (!scc->num_bridge_entries)
 693                         continue;
 694
 695                 api_sccs [j] = sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC) + sizeof (MonoObject*) * scc->num_bridge_entries, INTERNAL_MEM_BRIDGE_DATA, TRUE);
 696                 api_sccs [j]->is_alive = FALSE;
 697                 api_sccs [j]->num_objs = scc->num_bridge_entries;
 698                 scc->num_bridge_entries = 0;
 699                 scc->api_index = j++;
 700
 701                 num_xrefs += scc->xrefs.size;
 702         }
 703
 704         SGEN_HASH_TABLE_FOREACH (&hash_table, obj, entry) {
 705                 if (entry->is_bridge) {
 706                         SCC *scc = DYN_ARRAY_REF (&sccs, entry->scc_index);
 707                         api_sccs [scc->api_index]->objs [scc->num_bridge_entries++] = entry->obj;
 708                 }
 709         } SGEN_HASH_TABLE_FOREACH_END;
 710
 711         api_xrefs = sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeXRef) * num_xrefs, INTERNAL_MEM_BRIDGE_DATA, TRUE);
 712         j = 0;
 713         for (i = 0; i < sccs.size; ++i) {
 714                 int k;
 715                 SCC *scc = DYN_ARRAY_REF (&sccs, i);
 716                 if (!scc->num_bridge_entries)
 717                         continue;
 718                 for (k = 0; k < scc->xrefs.size; ++k) {
 719                         SCC *src_scc = DYN_ARRAY_REF (&sccs, DYN_ARRAY_INT_REF (&scc->xrefs, k));
 720                         if (!src_scc->num_bridge_entries)
 721                                 continue;
 722                         api_xrefs [j].src_scc_index = src_scc->api_index;
 723                         api_xrefs [j].dst_scc_index = scc->api_index;
 724                         ++j;
 725                 }
 726         }
 727
 728         SGEN_TV_GETTIME (btv);
 729         step_5 = SGEN_TV_ELAPSED (atv, btv);
 730
 731         /* free data */
 732
 733         j = 0;
 734         max_entries = max_xrefs = 0;
 735         for (i = 0; i < sccs.size; ++i) {
 736                 SCC *scc = DYN_ARRAY_REF (&sccs, i);
 737                 if (scc->num_bridge_entries)
 738                         ++j;
 739                 if (scc->num_bridge_entries > max_entries)
 740                         max_entries = scc->num_bridge_entries;
 741                 if (scc->xrefs.size > max_xrefs)
 742                         max_xrefs = scc->xrefs.size;
 743                 dyn_array_uninit (&scc->xrefs);
 744
 745         }
 746         dyn_array_uninit (&sccs);
 747
 748         sgen_free_internal_dynamic (all_entries, sizeof (HashEntry*) * hash_table.num_entries, INTERNAL_MEM_BRIDGE_DATA);
 749
 750         free_data ();
 751         /* Empty the registered bridges array */
 752         num_registered_bridges = registered_bridges.size;
 753         registered_bridges.size = 0;
 754
 755         SGEN_TV_GETTIME (atv);
 756         step_6 = SGEN_TV_ELAPSED (btv, atv);
 757
 758         //g_print ("%d sccs containing bridges - %d max bridge objects - %d max xrefs\n", j, max_entries, max_xrefs);
 759
 760         /* callback */
 761
 762         bridge_callbacks.cross_references (num_sccs, api_sccs, num_xrefs, api_xrefs);
 763
 764         /* Release for finalization those objects we no longer care. */
 765         SGEN_TV_GETTIME (btv);
 766         step_7 = SGEN_TV_ELAPSED (atv, btv);
 767
 768         for (i = 0; i < num_sccs; ++i) {
 769                 unsigned char alive = api_sccs [i]->is_alive ? 1 : 0;
 770                 for (j = 0; j < api_sccs [i]->num_objs; ++j) {
 771                         /* Build hash table for nulling weak links. */
 772                         sgen_hash_table_replace (&alive_hash, api_sccs [i]->objs [j], &alive, NULL);
 773
 774                         /* Release for finalization those objects we no longer care. */
 775                         if (!api_sccs [i]->is_alive)
 776                                 sgen_mark_bridge_object (api_sccs [i]->objs [j]);
 777                 }
 778         }
 779
 780         /* Null weak links to dead objects. */
 781         sgen_null_links_with_predicate (GENERATION_NURSERY, is_bridge_object_alive, &alive_hash);
 782         if (generation == GENERATION_OLD)
 783                 sgen_null_links_with_predicate (GENERATION_OLD, is_bridge_object_alive, &alive_hash);
 784
 785         sgen_hash_table_clean (&alive_hash);
 786
 787         /* free callback data */
 788
 789         for (i = 0; i < num_sccs; ++i) {
 790                 sgen_free_internal_dynamic (api_sccs [i],
 791                                 sizeof (MonoGCBridgeSCC) + sizeof (MonoObject*) * api_sccs [i]->num_objs,
 792                                 INTERNAL_MEM_BRIDGE_DATA);
 793         }
 794         sgen_free_internal_dynamic (api_sccs, sizeof (MonoGCBridgeSCC*) * num_sccs, INTERNAL_MEM_BRIDGE_DATA);
 795
 796         sgen_free_internal_dynamic (api_xrefs, sizeof (MonoGCBridgeXRef) * num_xrefs, INTERNAL_MEM_BRIDGE_DATA);
 797
 798         SGEN_TV_GETTIME (atv);
 799         step_8 = SGEN_TV_ELAPSED (btv, atv);
 800
 801         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",
 802                 num_registered_bridges, hash_table_size, sccs.size,
 803                 step_1 / 1000.0f,
 804                 step_2 / 1000.0f,
 805                 step_3 / 1000.0f,
 806                 step_4 / 1000.0f,
 807                 step_5 / 1000.0f,
 808                 step_6 / 1000.0f,
 809                 step_7 / 1000.0f,
 810                 step_8 / 1000.f,
 811                 fist_pass_links, second_pass_links, sccs_links, max_sccs_links,
 812                 dsf1_passes, dsf2_passes);
 813
 814         step_1 = 0; /* We must cleanup since this value is used as an accumulator. */
 815
 816         bridge_processing_in_progress = FALSE;
 817 }
 818
 819 void
 820 sgen_bridge_describe_pointer (MonoObject *obj)
 821 {
 822         HashEntry *entry;
 823         int i;
 824
 825         for (i = 0; i < registered_bridges.size; ++i) {
 826                 if (obj == DYN_ARRAY_PTR_REF (&registered_bridges, i)) {
 827                         printf ("Pointer is a registered bridge object.\n");
 828                         break;
 829                 }
 830         }
 831
 832         entry = sgen_hash_table_lookup (&hash_table, obj);
 833         if (!entry)
 834                 return;
 835
 836         printf ("Bridge hash table entry %p:\n", entry);
 837         printf ("  is bridge: %d\n", (int)entry->is_bridge);
 838         printf ("  is visited: %d\n", (int)entry->is_visited);
 839 }
 840
 841 static const char *bridge_class;
 842
 843 static gboolean
 844 bridge_test_is_bridge_class (MonoClass *class)
 845 {
 846         return !strcmp (bridge_class, class->name);
 847 }
 848
 849 static gboolean
 850 bridge_test_is_bridge_object (MonoObject *object)
 851 {
 852         return TRUE;
 853 }
 854
 855 static void
 856 bridge_test_cross_reference (int num_sccs, MonoGCBridgeSCC **sccs, int num_xrefs, MonoGCBridgeXRef *xrefs)
 857 {
 858         int i;
 859         for (i = 0; i < num_sccs; ++i) {
 860                 int j;
 861         //      g_print ("--- SCC %d\n", i);
 862                 for (j = 0; j < sccs [i]->num_objs; ++j) {
 863         //              g_print ("  %s\n", sgen_safe_name (sccs [i]->objs [j]));
 864                         if (i & 1) /*retain half of the bridged objects */
 865                                 sccs [i]->is_alive = TRUE;
 866                 }
 867         }
 868         for (i = 0; i < num_xrefs; ++i) {
 869                 g_assert (xrefs [i].src_scc_index >= 0 && xrefs [i].src_scc_index < num_sccs);
 870                 g_assert (xrefs [i].dst_scc_index >= 0 && xrefs [i].dst_scc_index < num_sccs);
 871         //      g_print ("%d -> %d\n", xrefs [i].src_scc_index, xrefs [i].dst_scc_index);
 872         }
 873 }
 874
 875 static MonoClassField *mono_bridge_test_field;
 876
 877 enum {
 878         BRIDGE_DEAD,
 879         BRIDGE_ROOT,
 880         BRIDGE_SAME_SCC,
 881         BRIDGE_XREF,
 882 };
 883
 884 static gboolean
 885 test_scc (MonoGCBridgeSCC *scc, int i)
 886 {
 887         int status = BRIDGE_DEAD;
 888         mono_field_get_value (scc->objs [i], mono_bridge_test_field, &status);
 889         return status > 0;
 890 }
 891
 892 static void
 893 mark_scc (MonoGCBridgeSCC *scc, int value)
 894 {
 895         int i;
 896         for (i = 0; i < scc->num_objs; ++i) {
 897                 if (!test_scc (scc, i)) {
 898                         int status = value;
 899                         mono_field_set_value (scc->objs [i], mono_bridge_test_field, &status);
 900                 }
 901         }
 902 }
 903
 904 static void
 905 bridge_test_cross_reference2 (int num_sccs, MonoGCBridgeSCC **sccs, int num_xrefs, MonoGCBridgeXRef *xrefs)
 906 {
 907         int i;
 908         gboolean modified;
 909
 910         if (!mono_bridge_test_field) {
 911                 mono_bridge_test_field = mono_class_get_field_from_name (mono_object_get_class (sccs[0]->objs [0]), "__test");
 912                 g_assert (mono_bridge_test_field);
 913         }
 914
 915         /*We mark all objects in a scc with live objects as reachable by scc*/
 916         for (i = 0; i < num_sccs; ++i) {
 917                 int j;
 918                 gboolean live = FALSE;
 919                 for (j = 0; j < sccs [i]->num_objs; ++j) {
 920                         if (test_scc (sccs [i], j)) {
 921                                 live = TRUE;
 922                                 break;
 923                         }
 924                 }
 925                 if (!live)
 926                         continue;
 927                 for (j = 0; j < sccs [i]->num_objs; ++j) {
 928                         if (!test_scc (sccs [i], j)) {
 929                                 int status = BRIDGE_SAME_SCC;
 930                                 mono_field_set_value (sccs [i]->objs [j], mono_bridge_test_field, &status);
 931                         }
 932                 }
 933         }
 934
 935         /*Now we mark the transitive closure of reachable objects from the xrefs*/
 936         modified = TRUE;
 937         while (modified) {
 938                 modified = FALSE;
 939                 /* Mark all objects that are brought to life due to xrefs*/
 940                 for (i = 0; i < num_xrefs; ++i) {
 941                         MonoGCBridgeXRef ref = xrefs [i];
 942                         if (test_scc (sccs [ref.src_scc_index], 0) && !test_scc (sccs [ref.dst_scc_index], 0)) {
 943                                 modified = TRUE;
 944                                 mark_scc (sccs [ref.dst_scc_index], BRIDGE_XREF);
 945                         }
 946                 }
 947         }
 948
 949         /* keep everything in memory, all we want to do is test persistence */
 950         for (i = 0; i < num_sccs; ++i)
 951                 sccs [i]->is_alive = TRUE;
 952 }
 953
 954 void
 955 sgen_register_test_bridge_callbacks (const char *bridge_class_name)
 956 {
 957         MonoGCBridgeCallbacks callbacks;
 958         callbacks.bridge_version = SGEN_BRIDGE_VERSION;
 959         callbacks.is_bridge_class = bridge_test_is_bridge_class;
 960         callbacks.is_bridge_object = bridge_test_is_bridge_object;
 961         callbacks.cross_references = bridge_class_name[0] == '2' ? bridge_test_cross_reference2 : bridge_test_cross_reference;
 962         mono_gc_register_bridge_callbacks (&callbacks);
 963         bridge_class = bridge_class_name + (bridge_class_name[0] == '2' ? 1 : 0);
 964 }
 965
 966 #endif