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