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