mono/metadata/sgen-tarjan-bridge.c

   1 /*
   2  * sgen-tarjan-bridge.c: Tarjan-based bridge implementation.
   3  *
   4  * Copyright 2011 Novell, Inc (http://www.novell.com)
   5  * Copyright 2014 Xamarin Inc (http://www.xamarin.com)
   6  *
   7  *
   8  * Copyright 2001-2003 Ximian, Inc
   9  * Copyright 2003-2010 Novell, Inc.
  10  *
  11  * Licensed under the MIT license. See LICENSE file in the project root for full license information.
  12  */
  13
  14 #include "config.h"
  15
  16 #ifdef HAVE_SGEN_GC
  17
  18 #include <stdlib.h>
  19
  20 #include "sgen/sgen-gc.h"
  21 #include "sgen-bridge-internals.h"
  22 #include "tabledefs.h"
  23 #include "utils/mono-logger-internals.h"
  24
  25 #include "sgen-dynarray.h"
  26
  27 /*
  28  * See comments in sgen-bridge.h
  29  *
  30  * This bridge implementation is based on the tarjan algorithm for strongly
  31  * connected components. It has two elements:
  32  *
  33  *   - Standard tarjan SCC algorithm to convert graph to SCC forest
  34  *
  35  *   - "Colors": We reduce the SCC forest to bridged-SCCs-only by using a
  36  *     "color" algorithm devised by Kumpera. Consider the set of bridged SCCs
  37  *     which is reachable from a given object. We call each such unique set a
  38  *     "color". We compute the set of colors and which colors contain links to
  39  *     which colors. The color graph then becomes the reduced SCC graph.
  40  */
  41
  42 static void
  43 enable_accounting (void)
  44 {
  45         // bridge_accounting_enabled = TRUE;
  46         // 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);
  47 }
  48
  49 // Is this class bridged or not, and should its dependencies be scanned or not?
  50 // The result of this callback will be cached for use by is_opaque_object later.
  51 static MonoGCBridgeObjectKind
  52 class_kind (MonoClass *klass)
  53 {
  54         MonoGCBridgeObjectKind res = bridge_callbacks.bridge_class_kind (klass);
  55
  56         /* If it's a bridge, nothing we can do about it. */
  57         if (res == GC_BRIDGE_TRANSPARENT_BRIDGE_CLASS || res == GC_BRIDGE_OPAQUE_BRIDGE_CLASS)
  58                 return res;
  59
  60         /* Non bridge classes with no pointers will never point to a bridge, so we can savely ignore them. */
  61         if (!klass->has_references) {
  62                 SGEN_LOG (6, "class %s is opaque\n", klass->name);
  63                 return GC_BRIDGE_OPAQUE_CLASS;
  64         }
  65
  66         /* Some arrays can be ignored */
  67         if (klass->rank == 1) {
  68                 MonoClass *elem_class = klass->element_class;
  69
  70                 /* FIXME the bridge check can be quite expensive, cache it at the class level. */
  71                 /* An array of a sealed type that is not a bridge will never get to a bridge */
  72                 if ((elem_class->flags & TYPE_ATTRIBUTE_SEALED) && !elem_class->has_references && !bridge_callbacks.bridge_class_kind (elem_class)) {
  73                         SGEN_LOG (6, "class %s is opaque\n", klass->name);
  74                         return GC_BRIDGE_OPAQUE_CLASS;
  75                 }
  76         }
  77
  78         return GC_BRIDGE_TRANSPARENT_CLASS;
  79 }
  80
  81 //enable usage logging
  82 // #define DUMP_GRAPH 1
  83
  84 // ScanData state
  85 enum {
  86         INITIAL,
  87         SCANNED,
  88         FINISHED_ON_STACK,
  89         FINISHED_OFF_STACK
  90 };
  91
  92 /*
  93 Optimizations:
  94         We can split this data structure in two, those with bridges and those without
  95 */
  96 typedef struct {
  97     // Colors (ColorDatas) linked to by objects with this color
  98         DynPtrArray other_colors;
  99     // Bridge objects (GCObjects) held by objects with this color
 100         DynPtrArray bridges;
 101         int api_index    : 31;
 102         unsigned visited : 1;
 103 } ColorData;
 104
 105 // Represents one managed object. Equivalent of new/old bridge "HashEntry"
 106 typedef struct _ScanData {
 107         // FIXME this can be eliminated; if we have a ScanData we generally looked it up from its GCObject
 108         GCObject *obj;
 109         // We use the sgen lock_word in GCObject to store a pointer to the ScanData. Cache the original here to restore later:
 110         mword lock_word;
 111
 112         ColorData *color;
 113         // Tarjan algorithm index (order visited)
 114         int index;
 115         // Tarjan index of lowest-index object known reachable from here
 116         int low_index : 27;
 117
 118         // See "ScanData state" enum above
 119         unsigned state : 2;
 120         unsigned is_bridge : 1;
 121         // Similar to lock_word, we use these bits in the GCObject as scratch space then restore them when done
 122         unsigned obj_state : 2;
 123 } ScanData;
 124
 125 // Should color be made visible to client even though it has no bridges?
 126 static inline gboolean bridgeless_color_is_heavy (ColorData *data) {
 127    return TRUE;
 128 }
 129
 130 // Should color be made visible to client?
 131 static inline gboolean color_visible_to_client (ColorData *data) {
 132    return dyn_array_ptr_size (&data->bridges) || bridgeless_color_is_heavy (data);
 133 }
 134
 135 // Stacks of ScanData objects used for tarjan algorithm.
 136 // The Tarjan algorithm is normally defined recursively; here scan_stack simulates the call stack of a recursive algorithm,
 137 // and loop_stack is the stack structure used by the algorithm itself.
 138 static DynPtrArray scan_stack, loop_stack;
 139
 140 // GCObjects on which register_finalized_object has been called
 141 static DynPtrArray registered_bridges;
 142
 143 // ColorData objects
 144 static DynPtrArray color_merge_array;
 145
 146 static int ignored_objects;
 147 static int object_index;
 148 static int num_colors_with_bridges;
 149 static int xref_count;
 150
 151 static size_t setup_time, tarjan_time, scc_setup_time, gather_xref_time, xref_setup_time, cleanup_time;
 152 static SgenBridgeProcessor *bridge_processor;
 153
 154 #define BUCKET_SIZE 8184
 155
 156 //ScanData buckets
 157 #define NUM_SCAN_ENTRIES ((BUCKET_SIZE - SIZEOF_VOID_P * 2) / sizeof (ScanData))
 158
 159 typedef struct _ObjectBucket ObjectBucket;
 160 struct _ObjectBucket {
 161         ObjectBucket *next;
 162         ScanData *next_data;
 163         ScanData data [NUM_SCAN_ENTRIES];
 164 };
 165
 166 static ObjectBucket *root_object_bucket;
 167 static ObjectBucket *cur_object_bucket;
 168 static int object_data_count;
 169
 170 // Arenas to allocate ScanData from
 171 static ObjectBucket*
 172 new_object_bucket (void)
 173 {
 174         ObjectBucket *res = (ObjectBucket *)sgen_alloc_internal (INTERNAL_MEM_TARJAN_OBJ_BUCKET);
 175         res->next_data = &res->data [0];
 176         return res;
 177 }
 178
 179 static void
 180 object_alloc_init (void)
 181 {
 182         root_object_bucket = cur_object_bucket = new_object_bucket ();
 183 }
 184
 185 static ScanData*
 186 alloc_object_data (void)
 187 {
 188         ScanData *res;
 189 retry:
 190
 191         /* next_data points to the first free entry */
 192         res = cur_object_bucket->next_data;
 193         if (res >= &cur_object_bucket->data [NUM_SCAN_ENTRIES]) {
 194                 ObjectBucket *b = new_object_bucket ();
 195                 cur_object_bucket->next = b;
 196                 cur_object_bucket = b;
 197                 goto retry;
 198         }
 199         cur_object_bucket->next_data = res + 1;
 200         object_data_count++;
 201         return res;
 202 }
 203
 204 static void
 205 free_object_buckets (void)
 206 {
 207         ObjectBucket *cur = root_object_bucket;
 208
 209         object_data_count = 0;
 210
 211         while (cur) {
 212                 ObjectBucket *tmp = cur->next;
 213                 sgen_free_internal (cur, INTERNAL_MEM_TARJAN_OBJ_BUCKET);
 214                 cur = tmp;
 215         }
 216
 217         root_object_bucket = cur_object_bucket = NULL;
 218 }
 219
 220 //ColorData buckets
 221 #define NUM_COLOR_ENTRIES ((BUCKET_SIZE - SIZEOF_VOID_P * 2) / sizeof (ColorData))
 222
 223 // Arenas for ColorDatas, same as ObjectBucket except items-per-bucket differs
 224 typedef struct _ColorBucket ColorBucket;
 225 struct _ColorBucket {
 226         ColorBucket *next;
 227         ColorData *next_data;
 228         ColorData data [NUM_COLOR_ENTRIES];
 229 };
 230
 231 static ColorBucket *root_color_bucket;
 232 static ColorBucket *cur_color_bucket;
 233 static int color_data_count;
 234
 235
 236 static ColorBucket*
 237 new_color_bucket (void)
 238 {
 239         ColorBucket *res = (ColorBucket *)sgen_alloc_internal (INTERNAL_MEM_TARJAN_OBJ_BUCKET);
 240         res->next_data = &res->data [0];
 241         return res;
 242 }
 243
 244 static void
 245 color_alloc_init (void)
 246 {
 247         root_color_bucket = cur_color_bucket = new_color_bucket ();
 248 }
 249
 250 static ColorData*
 251 alloc_color_data (void)
 252 {
 253         ColorData *res;
 254 retry:
 255
 256         /* next_data points to the first free entry */
 257         res = cur_color_bucket->next_data;
 258         if (res >= &cur_color_bucket->data [NUM_COLOR_ENTRIES]) {
 259                 ColorBucket *b = new_color_bucket ();
 260                 cur_color_bucket->next = b;
 261                 cur_color_bucket = b;
 262                 goto retry;
 263         }
 264         cur_color_bucket->next_data = res + 1;
 265         color_data_count++;
 266         return res;
 267 }
 268
 269 static void
 270 free_color_buckets (void)
 271 {
 272         ColorBucket *cur, *tmp;
 273
 274         color_data_count = 0;
 275
 276         for (cur = root_color_bucket; cur; cur = tmp) {
 277                 ColorData *cd;
 278                 for (cd = &cur->data [0]; cd < cur->next_data; ++cd) {
 279                         dyn_array_ptr_uninit (&cd->other_colors);
 280                         dyn_array_ptr_uninit (&cd->bridges);
 281                 }
 282                 tmp = cur->next;
 283                 sgen_free_internal (cur, INTERNAL_MEM_TARJAN_OBJ_BUCKET);
 284         }
 285         root_color_bucket = cur_color_bucket = NULL;
 286 }
 287
 288
 289 static ScanData*
 290 create_data (GCObject *obj)
 291 {
 292         mword *o = (mword*)obj;
 293         ScanData *res = alloc_object_data ();
 294         res->obj = obj;
 295         res->color = NULL;
 296         res->index = res->low_index = -1;
 297         res->state = INITIAL;
 298         res->is_bridge = FALSE;
 299         res->obj_state = o [0] & SGEN_VTABLE_BITS_MASK;
 300         res->lock_word = o [1];
 301
 302         o [0] |= SGEN_VTABLE_BITS_MASK;
 303         o [1] = (mword)res;
 304         return res;
 305 }
 306
 307 static ScanData*
 308 find_data (GCObject *obj)
 309 {
 310         ScanData *a = NULL;
 311         mword *o = (mword*)obj;
 312         if ((o [0] & SGEN_VTABLE_BITS_MASK) == SGEN_VTABLE_BITS_MASK)
 313                 a = (ScanData*)o [1];
 314         return a;
 315 }
 316
 317 static void
 318 clear_after_processing (void)
 319 {
 320         ObjectBucket *cur;
 321
 322         for (cur = root_object_bucket; cur; cur = cur->next) {
 323                 ScanData *sd;
 324                 for (sd = &cur->data [0]; sd < cur->next_data; ++sd) {
 325                         mword *o = (mword*)sd->obj;
 326                         o [0] &= ~SGEN_VTABLE_BITS_MASK;
 327                         o [0] |= sd->obj_state;
 328                         o [1] = sd->lock_word;
 329                 }
 330         }
 331 }
 332
 333 static GCObject*
 334 bridge_object_forward (GCObject *obj)
 335 {
 336         GCObject *fwd;
 337         mword *o = (mword*)obj;
 338         if ((o [0] & SGEN_VTABLE_BITS_MASK) == SGEN_VTABLE_BITS_MASK)
 339                 return obj;
 340
 341         fwd = SGEN_OBJECT_IS_FORWARDED (obj);
 342         return fwd ? fwd : obj;
 343 }
 344
 345 #ifdef DUMP_GRAPH
 346 static const char*
 347 safe_name_bridge (GCObject *obj)
 348 {
 349         GCVTable vt = SGEN_LOAD_VTABLE (obj);
 350         return vt->klass->name;
 351 }
 352
 353 static ScanData*
 354 find_or_create_data (GCObject *obj)
 355 {
 356         ScanData *entry = find_data (obj);
 357         if (!entry)
 358                 entry = create_data (obj);
 359         return entry;
 360 }
 361 #endif
 362
 363 //----------
 364 typedef struct {
 365         ColorData *color;
 366         int hash;
 367 } HashEntry;
 368
 369 /*
 370 The merge cache maps an ordered list of ColorDatas [the color_merge_array] to a single ColorData.
 371
 372 About cache bucket tuning: We tried 2/32, 2/128, 4/32, 4/128, 6/128 and 8/128.
 373
 374 The performance cost between 4/128 and 8/128 is so small since cache movement happens completely in the same cacheline,
 375 making the extra space pretty much free.
 376
 377 The cost between 32 and 128 itens is minimal too, it's mostly a fixed, setup cost.
 378
 379 Memory wise, 4/32 takes 512 and 8/128 takes 8k, so it's quite reasonable.
 380 */
 381
 382 #define ELEMENTS_PER_BUCKET 8
 383 #define COLOR_CACHE_SIZE 128
 384 static HashEntry merge_cache [COLOR_CACHE_SIZE][ELEMENTS_PER_BUCKET];
 385
 386 static int
 387 mix_hash (size_t hash)
 388 {
 389         return (int)(((hash * 215497) >> 16) ^ ((hash * 1823231) + hash));
 390 }
 391
 392 static void
 393 reset_cache (void)
 394 {
 395         memset (merge_cache, 0, sizeof (merge_cache));
 396 }
 397
 398
 399 static gboolean
 400 dyn_array_ptr_contains (DynPtrArray *da, void *x)
 401 {
 402         int i;
 403         for (i = 0; i < dyn_array_ptr_size (da); ++i)
 404                 if (dyn_array_ptr_get (da, i) == x)
 405                         return TRUE;
 406         return FALSE;
 407 }
 408
 409 static gboolean
 410 match_colors (DynPtrArray *a, DynPtrArray *b)
 411 {
 412         int i;
 413         if (dyn_array_ptr_size (a) != dyn_array_ptr_size (b))
 414                 return FALSE;
 415
 416         for (i = 0; i < dyn_array_ptr_size (a); ++i) {
 417                 if (!dyn_array_ptr_contains (b, dyn_array_ptr_get (a, i)))
 418                         return FALSE;
 419         }
 420         return TRUE;
 421 }
 422
 423 static int cache_hits, cache_misses, cache_abstains;
 424
 425 // The cache contains only non-bridged colors.
 426 static ColorData*
 427 find_in_cache (int *insert_index)
 428 {
 429         HashEntry *bucket;
 430         int i, hash, size, index;
 431
 432         size = dyn_array_ptr_size (&color_merge_array);
 433         /* Cache checking is very ineficient with a lot of elements*/
 434         if (size > 3) {
 435                 ++cache_abstains;
 436                 return NULL;
 437         }
 438
 439         hash = 0;
 440         for (i = 0 ; i < size; ++i)
 441                 hash += mix_hash ((size_t)dyn_array_ptr_get (&color_merge_array, i));
 442         if (!hash)
 443                 hash = 1;
 444
 445         index = hash & (COLOR_CACHE_SIZE - 1);
 446         bucket = merge_cache [index];
 447         for (i = 0; i < ELEMENTS_PER_BUCKET; ++i) {
 448                 if (bucket [i].hash != hash)
 449                         continue;
 450                 if (match_colors (&bucket [i].color->other_colors, &color_merge_array)) {
 451                         ++cache_hits;
 452                         return bucket [i].color;
 453                 }
 454         }
 455
 456         //move elements to the back
 457         for (i = ELEMENTS_PER_BUCKET - 1; i > 0; --i)
 458                 bucket [i] = bucket [i - 1];
 459         ++cache_misses;
 460         *insert_index = index;
 461         bucket [0].hash = hash;
 462         return NULL;
 463 }
 464
 465 // A color is needed for an SCC. If the SCC has bridges, the color MUST be newly allocated.
 466 // If the SCC lacks bridges, the allocator MAY use the cache to merge it with an existing one.
 467 static ColorData*
 468 new_color (gboolean has_bridges)
 469 {
 470         int i = -1;
 471         ColorData *cd;
 472         /* XXX Try to find an equal one and return it */
 473         if (!has_bridges) {
 474                 cd = find_in_cache (&i);
 475                 if (cd)
 476                         return cd;
 477         }
 478
 479         cd = alloc_color_data ();
 480         cd->api_index = -1;
 481         dyn_array_ptr_set_all (&cd->other_colors, &color_merge_array);
 482         /* if i >= 0, it means we prepared a given slot to receive the new color */
 483         if (i >= 0)
 484                 merge_cache [i][0].color = cd;
 485
 486         return cd;
 487 }
 488
 489
 490 static void
 491 register_bridge_object (GCObject *obj)
 492 {
 493         create_data (obj)->is_bridge = TRUE;
 494 }
 495
 496 static gboolean
 497 is_opaque_object (GCObject *obj)
 498 {
 499         MonoVTable *vt = SGEN_LOAD_VTABLE (obj);
 500         if ((vt->gc_bits & SGEN_GC_BIT_BRIDGE_OPAQUE_OBJECT) == SGEN_GC_BIT_BRIDGE_OPAQUE_OBJECT) {
 501                 SGEN_LOG (6, "ignoring %s\n", vt->klass->name);
 502                 ++ignored_objects;
 503                 return TRUE;
 504         }
 505         return FALSE;
 506 }
 507
 508 // Called during DFS; visits one child. If it is a candidate to be scanned, pushes it to the stacks.
 509 static void
 510 push_object (GCObject *obj)
 511 {
 512         ScanData *data;
 513         obj = bridge_object_forward (obj);
 514
 515 #if DUMP_GRAPH
 516         printf ("\t= pushing %p %s -> ", obj, safe_name_bridge (obj));
 517 #endif
 518
 519         /* Object types we can ignore */
 520         if (is_opaque_object (obj)) {
 521 #if DUMP_GRAPH
 522                 printf ("opaque\n");
 523 #endif
 524                 return;
 525         }
 526
 527         data = find_data (obj);
 528
 529         /* Already marked - XXX must be done this way as the bridge themselves are alive. */
 530         if (data && data->state != INITIAL) {
 531 #if DUMP_GRAPH
 532                 printf ("already marked\n");
 533 #endif
 534                 return;
 535         }
 536
 537         /* We only care about dead objects */
 538         if (!data && sgen_object_is_live (obj)) {
 539 #if DUMP_GRAPH
 540                 printf ("alive\n");
 541 #endif
 542                 return;
 543         }
 544
 545 #if DUMP_GRAPH
 546         printf ("pushed!\n");
 547 #endif
 548
 549         if (!data)
 550                 data = create_data (obj);
 551         g_assert (data->state == INITIAL);
 552         g_assert (data->index == -1);
 553         dyn_array_ptr_push (&scan_stack, data);
 554 }
 555
 556 #undef HANDLE_PTR
 557 #define HANDLE_PTR(ptr,obj)     do {                                    \
 558                 GCObject *dst = (GCObject*)*(ptr);                      \
 559                 if (dst) push_object (dst);                     \
 560         } while (0)
 561
 562 // dfs () function's queue-children-of-object operation.
 563 static void
 564 push_all (ScanData *data)
 565 {
 566         GCObject *obj = data->obj;
 567         char *start = (char*)obj;
 568         mword desc = sgen_obj_get_descriptor_safe (obj);
 569
 570 #if DUMP_GRAPH
 571         printf ("+scanning %s (%p) index %d color %p\n", safe_name_bridge (data->obj), data->obj, data->index, data->color);
 572 #endif
 573
 574         #include "sgen/sgen-scan-object.h"
 575 }
 576
 577
 578 static void
 579 compute_low_index (ScanData *data, GCObject *obj)
 580 {
 581         ScanData *other;
 582         ColorData *cd;
 583
 584         obj = bridge_object_forward (obj);
 585         other = find_data (obj);
 586
 587 #if DUMP_GRAPH
 588         printf ("\tcompute low %p ->%p (%s) %p (%d / %d)\n", data->obj, obj, safe_name_bridge (obj), other, other ? other->index : -2, other ? other->low_index : -2);
 589 #endif
 590         if (!other)
 591                 return;
 592
 593         g_assert (other->state != INITIAL);
 594
 595         if ((other->state == SCANNED || other->state == FINISHED_ON_STACK) && data->low_index > other->low_index)
 596                 data->low_index = other->low_index;
 597
 598         /* Compute the low color */
 599         if (other->color == NULL)
 600                 return;
 601
 602         cd = other->color;
 603         if (!cd->visited) {
 604                 dyn_array_ptr_add (&color_merge_array, other->color);
 605                 cd->visited = TRUE;
 606         }
 607 }
 608
 609 #undef HANDLE_PTR
 610 #define HANDLE_PTR(ptr,obj)     do {                                    \
 611                 GCObject *dst = (GCObject*)*(ptr);                      \
 612                 if (dst) compute_low_index (data, dst);                         \
 613         } while (0)
 614
 615 static void
 616 compute_low (ScanData *data)
 617 {
 618         GCObject *obj = data->obj;
 619         char *start = (char*)obj;
 620         mword desc = sgen_obj_get_descriptor_safe (obj);
 621
 622         #include "sgen/sgen-scan-object.h"
 623 }
 624
 625 // A non-bridged object needs a single color describing the current merge array.
 626 static ColorData*
 627 reduce_color (void)
 628 {
 629         ColorData *color = NULL;
 630         int size = dyn_array_ptr_size (&color_merge_array);
 631
 632         // Merge array is empty-- this SCC points to no bridged colors.
 633         // This SCC can be ignored completely.
 634         if (size == 0)
 635                 color = NULL;
 636
 637         // Merge array has one item-- this SCC points to a single bridged color.
 638         // This SCC can be forwarded to the pointed-to color.
 639         else if (size == 1) {
 640                 color = (ColorData *)dyn_array_ptr_get (&color_merge_array, 0);
 641
 642         // This SCC gets to talk to the color allocator.
 643         } else
 644                 color = new_color (FALSE);
 645
 646         return color;
 647 }
 648
 649 static void
 650 create_scc (ScanData *data)
 651 {
 652         int i;
 653         gboolean found = FALSE;
 654         gboolean found_bridge = FALSE;
 655         ColorData *color_data = NULL;
 656
 657         for (i = dyn_array_ptr_size (&loop_stack) - 1; i >= 0; --i) {
 658                 ScanData *other = (ScanData *)dyn_array_ptr_get (&loop_stack, i);
 659                 found_bridge |= other->is_bridge;
 660                 if (found_bridge || other == data)
 661                         break;
 662         }
 663
 664 #if DUMP_GRAPH
 665         printf ("|SCC rooted in %s (%p) has bridge %d\n", safe_name_bridge (data->obj), data->obj, found_bridge);
 666         printf ("\tpoints-to-colors: ");
 667         for (int i = 0; i < dyn_array_ptr_size (&color_merge_array); ++i)
 668                 printf ("%p ", dyn_array_ptr_get (&color_merge_array, i));
 669         printf ("\n");
 670
 671         printf ("loop stack: ");
 672         for (int i = 0; i < dyn_array_ptr_size (&loop_stack); ++i) {
 673                 ScanData *other = dyn_array_ptr_get (&loop_stack, i);
 674                 printf ("(%d/%d)", other->index, other->low_index);
 675         }
 676         printf ("\n");
 677 #endif
 678
 679         if (found_bridge) {
 680                 color_data = new_color (TRUE);
 681                 ++num_colors_with_bridges;
 682         } else {
 683                 color_data = reduce_color ();
 684         }
 685
 686         while (dyn_array_ptr_size (&loop_stack) > 0) {
 687                 ScanData *other = (ScanData *)dyn_array_ptr_pop (&loop_stack);
 688
 689 #if DUMP_GRAPH
 690                 printf ("\tmember %s (%p) index %d low-index %d color %p state %d\n", safe_name_bridge (other->obj), other->obj, other->index, other->low_index, other->color, other->state);
 691 #endif
 692
 693                 other->color = color_data;
 694                 switch (other->state) {
 695                 case FINISHED_ON_STACK:
 696                         other->state = FINISHED_OFF_STACK;
 697                         break;
 698                 case FINISHED_OFF_STACK:
 699                         break;
 700                 default:
 701                         g_error ("Invalid state when building SCC %d", other->state);
 702                 }
 703
 704                 if (other->is_bridge)
 705                         dyn_array_ptr_add (&color_data->bridges, other->obj);
 706
 707                 if (other == data) {
 708                         found = TRUE;
 709                         break;
 710                 }
 711         }
 712         g_assert (found);
 713
 714         for (i = 0; i < dyn_array_ptr_size (&color_merge_array); ++i) {
 715                 ColorData *cd  = (ColorData *)dyn_array_ptr_get (&color_merge_array, i);
 716                 g_assert (cd->visited);
 717                 cd->visited = FALSE;
 718         }
 719         dyn_array_ptr_empty (&color_merge_array);
 720         found_bridge = FALSE;
 721 }
 722
 723 static void
 724 dfs (void)
 725 {
 726         g_assert (dyn_array_ptr_size (&scan_stack) == 1);
 727         g_assert (dyn_array_ptr_size (&loop_stack) == 0);
 728
 729         dyn_array_ptr_empty (&color_merge_array);
 730
 731         while (dyn_array_ptr_size (&scan_stack) > 0) {
 732                 ScanData *data = (ScanData *)dyn_array_ptr_pop (&scan_stack);
 733
 734                 /**
 735                  * Ignore finished objects on stack, they happen due to loops. For example:
 736                  * A -> C
 737                  * A -> B
 738                  * B -> C
 739                  * C -> A
 740                  *
 741                  * We start scanning from A and push C before B. So, after the first iteration, the scan stack will have: A C B.
 742                  * We then visit B, which will find C in its initial state and push again.
 743                  * Finally after finish with C and B, the stack will be left with "A C" and at this point C should be ignored.
 744          *
 745          * The above explains FINISHED_ON_STACK, to explain FINISHED_OFF_STACK, consider if the root was D, which pointed
 746                  * to A and C. A is processed first, leaving C on stack after that in the mentioned state.
 747                  */
 748                 if (data->state == FINISHED_ON_STACK || data->state == FINISHED_OFF_STACK)
 749                         continue;
 750
 751                 if (data->state == INITIAL) {
 752                         g_assert (data->index == -1);
 753                         g_assert (data->low_index == -1);
 754
 755                         data->state = SCANNED;
 756                         data->low_index = data->index = object_index++;
 757                         dyn_array_ptr_push (&scan_stack, data);
 758                         dyn_array_ptr_push (&loop_stack, data);
 759
 760 #if DUMP_GRAPH
 761                         printf ("+scanning %s (%p) index %d color %p\n", safe_name_bridge (data->obj), data->obj, data->index, data->color);
 762 #endif
 763                         /*push all refs */
 764                         push_all (data);
 765                 } else {
 766                         g_assert (data->state == SCANNED);
 767                         data->state = FINISHED_ON_STACK;
 768
 769 #if DUMP_GRAPH
 770                         printf ("-finishing %s (%p) index %d low-index %d color %p\n", safe_name_bridge (data->obj), data->obj, data->index, data->low_index, data->color);
 771 #endif
 772
 773                         /* Compute low index */
 774                         compute_low (data);
 775
 776 #if DUMP_GRAPH
 777                         printf ("-finished %s (%p) index %d low-index %d color %p\n", safe_name_bridge (data->obj), data->obj, data->index, data->low_index, data->color);
 778 #endif
 779                         //SCC root
 780                         if (data->index == data->low_index)
 781                                 create_scc (data);
 782                 }
 783         }
 784 }
 785
 786 static void
 787 register_finalized_object (GCObject *obj)
 788 {
 789         g_assert (sgen_need_bridge_processing ());
 790         dyn_array_ptr_push (&registered_bridges, obj);
 791 }
 792
 793 static void
 794 reset_data (void)
 795 {
 796         dyn_array_ptr_empty (&registered_bridges);
 797 }
 798
 799 static void
 800 cleanup (void)
 801 {
 802         dyn_array_ptr_empty (&scan_stack);
 803         dyn_array_ptr_empty (&loop_stack);
 804         dyn_array_ptr_empty (&registered_bridges);
 805         free_object_buckets ();
 806         free_color_buckets ();
 807         reset_cache ();
 808         object_index = 0;
 809         num_colors_with_bridges = 0;
 810 }
 811
 812 #ifdef DUMP_GRAPH
 813 static void
 814 dump_color_table (const char *why, gboolean do_index)
 815 {
 816         ColorBucket *cur;
 817         int i = 0, j;
 818         printf ("colors%s:\n", why);
 819
 820         for (cur = root_color_bucket; cur; cur = cur->next, ++i) {
 821                 ColorData *cd;
 822                 for (cd = &cur->data [0]; cd < cur->next_data; ++cd) {
 823                         if (do_index)
 824                                 printf ("\t%d(%d):", i, cd->api_index);
 825                         else
 826                                 printf ("\t%d: ", i);
 827                         for (j = 0; j < dyn_array_ptr_size (&cd->other_colors); ++j) {
 828                                 printf ("%p ", dyn_array_ptr_get (&cd->other_colors, j));
 829                         }
 830                         if (dyn_array_ptr_size (&cd->bridges)) {
 831                                 printf (" bridges: ");
 832                                 for (j = 0; j < dyn_array_ptr_size (&cd->bridges); ++j) {
 833                                         GCObject *obj = dyn_array_ptr_get (&cd->bridges, j);
 834                                         ScanData *data = find_or_create_data (obj);
 835                                         printf ("%d ", data->index);
 836                                 }
 837                         }
 838                         printf ("\n");
 839                 }
 840         }
 841
 842 }
 843 #endif
 844
 845 static gint64
 846 step_timer (gint64 *timer)
 847 {
 848         gint64 curtime, diff;
 849
 850         SGEN_TV_GETTIME (curtime);
 851         diff = SGEN_TV_ELAPSED (*timer, curtime);
 852         *timer = curtime;
 853         return diff;
 854 }
 855 static void
 856 processing_stw_step (void)
 857 {
 858         int i;
 859         int bridge_count;
 860         gint64 curtime;
 861
 862         if (!dyn_array_ptr_size (&registered_bridges))
 863                 return;
 864
 865 #if defined (DUMP_GRAPH)
 866         printf ("-----------------\n");
 867 #endif
 868
 869         SGEN_TV_GETTIME (curtime);
 870
 871         object_alloc_init ();
 872         color_alloc_init ();
 873
 874         bridge_count = dyn_array_ptr_size (&registered_bridges);
 875         for (i = 0; i < bridge_count ; ++i)
 876                 register_bridge_object ((GCObject *)dyn_array_ptr_get (&registered_bridges, i));
 877
 878         setup_time = step_timer (&curtime);
 879
 880         for (i = 0; i < bridge_count; ++i) {
 881                 ScanData *sd = find_data ((GCObject *)dyn_array_ptr_get (&registered_bridges, i));
 882                 if (sd->state == INITIAL) {
 883                         dyn_array_ptr_push (&scan_stack, sd);
 884                         dfs ();
 885                 } else {
 886                         g_assert (sd->state == FINISHED_OFF_STACK);
 887                 }
 888         }
 889
 890         tarjan_time = step_timer (&curtime);
 891
 892 #if defined (DUMP_GRAPH)
 893         printf ("----summary----\n");
 894         printf ("bridges:\n");
 895         for (int i = 0; i < bridge_count; ++i) {
 896                 ScanData *sd = find_data (dyn_array_ptr_get (&registered_bridges, i));
 897                 printf ("\t%s (%p) index %d color %p\n", safe_name_bridge (sd->obj), sd->obj, sd->index, sd->color);
 898         }
 899
 900         dump_color_table (" after tarjan", FALSE);
 901 #endif
 902
 903         clear_after_processing ();
 904 }
 905
 906
 907 static void
 908 gather_xrefs (ColorData *color)
 909 {
 910         int i;
 911         for (i = 0; i < dyn_array_ptr_size (&color->other_colors); ++i) {
 912                 ColorData *src = (ColorData *)dyn_array_ptr_get (&color->other_colors, i);
 913                 if (src->visited)
 914                         continue;
 915                 src->visited = TRUE;
 916                 if (color_visible_to_client (src))
 917                         dyn_array_ptr_add (&color_merge_array, src);
 918                 else
 919                         gather_xrefs (src);
 920         }
 921 }
 922
 923 static void
 924 reset_xrefs (ColorData *color)
 925 {
 926         int i;
 927         for (i = 0; i < dyn_array_ptr_size (&color->other_colors); ++i) {
 928                 ColorData *src = (ColorData *)dyn_array_ptr_get (&color->other_colors, i);
 929                 if (!src->visited)
 930                         continue;
 931                 src->visited = FALSE;
 932                 if (!color_visible_to_client (src))
 933                         reset_xrefs (src);
 934         }
 935 }
 936
 937 static void
 938 processing_build_callback_data (int generation)
 939 {
 940         int j, api_index;
 941         MonoGCBridgeSCC **api_sccs;
 942         MonoGCBridgeXRef *api_xrefs;
 943         gint64 curtime;
 944         ColorBucket *cur;
 945
 946         g_assert (bridge_processor->num_sccs == 0 && bridge_processor->num_xrefs == 0);
 947         g_assert (!bridge_processor->api_sccs && !bridge_processor->api_xrefs);
 948
 949         if (!dyn_array_ptr_size (&registered_bridges))
 950                 return;
 951
 952         SGEN_TV_GETTIME (curtime);
 953
 954         /*create API objects */
 955
 956 #if defined (DUMP_GRAPH)
 957         printf ("***** API *****\n");
 958         printf ("number of SCCs %d\n", num_colors_with_bridges);
 959 #endif
 960
 961         // Count the number of SCCs visible to the client
 962         int num_sccs = 0;
 963         for (cur = root_color_bucket; cur; cur = cur->next) {
 964                 ColorData *cd;
 965                 for (cd = &cur->data [0]; cd < cur->next_data; ++cd) {
 966                         if (color_visible_to_client (cd))
 967                                 num_sccs++;
 968                 }
 969         }
 970
 971         /* This is a straightforward translation from colors to the bridge callback format. */
 972         api_sccs = (MonoGCBridgeSCC **)sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC*) * num_sccs, INTERNAL_MEM_BRIDGE_DATA, TRUE);
 973         api_index = xref_count = 0;
 974
 975         // Convert visible SCCs, along with their bridged object list, to MonoGCBridgeSCCs in the client's SCC list
 976         for (cur = root_color_bucket; cur; cur = cur->next) {
 977                 ColorData *cd;
 978                 for (cd = &cur->data [0]; cd < cur->next_data; ++cd) {
 979                         int bridges = dyn_array_ptr_size (&cd->bridges);
 980                         if (!(bridges || bridgeless_color_is_heavy (cd)))
 981                                 continue;
 982
 983                         api_sccs [api_index] = (MonoGCBridgeSCC *)sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC) + sizeof (MonoObject*) * bridges, INTERNAL_MEM_BRIDGE_DATA, TRUE);
 984                         api_sccs [api_index]->is_alive = FALSE;
 985                         api_sccs [api_index]->num_objs = bridges;
 986
 987                         cd->api_index = api_index;
 988
 989                         for (j = 0; j < bridges; ++j)
 990                                 api_sccs [api_index]->objs [j] = (MonoObject *)dyn_array_ptr_get (&cd->bridges, j);
 991                         api_index++;
 992                 }
 993         }
 994
 995         scc_setup_time = step_timer (&curtime);
 996
 997         // Eliminate non-visible SCCs from the SCC list and redistribute xrefs
 998         for (cur = root_color_bucket; cur; cur = cur->next) {
 999                 ColorData *cd;
1000                 for (cd = &cur->data [0]; cd < cur->next_data; ++cd) {
1001                         if (!color_visible_to_client (cd))
1002                                 continue;
1003
1004                         dyn_array_ptr_empty (&color_merge_array);
1005                         gather_xrefs (cd);
1006                         reset_xrefs (cd);
1007                         dyn_array_ptr_set_all (&cd->other_colors, &color_merge_array);
1008                         xref_count += dyn_array_ptr_size (&cd->other_colors);
1009                 }
1010         }
1011
1012         gather_xref_time = step_timer (&curtime);
1013
1014 #if defined (DUMP_GRAPH)
1015         printf ("TOTAL XREFS %d\n", xref_count);
1016         dump_color_table (" after xref pass", TRUE);
1017 #endif
1018
1019         // Write out xrefs array
1020         api_xrefs = (MonoGCBridgeXRef *)sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeXRef) * xref_count, INTERNAL_MEM_BRIDGE_DATA, TRUE);
1021         api_index = 0;
1022         for (cur = root_color_bucket; cur; cur = cur->next) {
1023                 ColorData *src;
1024                 for (src = &cur->data [0]; src < cur->next_data; ++src) {
1025                         if (!color_visible_to_client (src))
1026                                 continue;
1027
1028                         for (j = 0; j < dyn_array_ptr_size (&src->other_colors); ++j) {
1029                                 ColorData *dest = (ColorData *)dyn_array_ptr_get (&src->other_colors, j);
1030                                 g_assert (color_visible_to_client (dest)); /* Supposedly we already eliminated all xrefs to non-visible objects. */
1031
1032                                 api_xrefs [api_index].src_scc_index = src->api_index;
1033                                 api_xrefs [api_index].dst_scc_index = dest->api_index;
1034                                 ++api_index;
1035                         }
1036                 }
1037         }
1038
1039         g_assert (xref_count == api_index);
1040         xref_setup_time = step_timer (&curtime);
1041
1042 #if defined (DUMP_GRAPH)
1043         printf ("---xrefs:\n");
1044         for (int i = 0; i < xref_count; ++i)
1045                 printf ("\t%d -> %d\n", api_xrefs [i].src_scc_index, api_xrefs [i].dst_scc_index);
1046 #endif
1047
1048         //FIXME move half of the cleanup to before the bridge callback?
1049         bridge_processor->num_sccs = num_sccs;
1050         bridge_processor->api_sccs = api_sccs;
1051         bridge_processor->num_xrefs = xref_count;
1052         bridge_processor->api_xrefs = api_xrefs;
1053 }
1054
1055 static void
1056 processing_after_callback (int generation)
1057 {
1058         gint64 curtime;
1059         int bridge_count = dyn_array_ptr_size (&registered_bridges);
1060         int object_count = object_data_count;
1061         int color_count = color_data_count;
1062         int scc_count = num_colors_with_bridges;
1063
1064         SGEN_TV_GETTIME (curtime);
1065
1066         /* cleanup */
1067         cleanup ();
1068
1069         cleanup_time = step_timer (&curtime);
1070
1071         mono_trace (G_LOG_LEVEL_INFO, MONO_TRACE_GC, "GC_TAR_BRIDGE bridges %d objects %d colors %d ignored %d sccs %d xref %d cache %d/%d/%d setup %.2fms tarjan %.2fms scc-setup %.2fms gather-xref %.2fms xref-setup %.2fms cleanup %.2fms",
1072                 bridge_count, object_count, color_count,
1073                 ignored_objects, scc_count, xref_count,
1074                 cache_hits, cache_misses, cache_abstains,
1075                 setup_time / 10000.0f,
1076                 tarjan_time / 10000.0f,
1077                 scc_setup_time / 10000.0f,
1078                 gather_xref_time / 10000.0f,
1079                 xref_setup_time / 10000.0f,
1080                 cleanup_time / 10000.0f);
1081
1082         cache_hits = cache_misses = cache_abstains = 0;
1083         ignored_objects = 0;
1084 }
1085
1086 static void
1087 describe_pointer (GCObject *obj)
1088 {
1089         // HashEntry *entry;
1090         int i;
1091
1092         for (i = 0; i < dyn_array_ptr_size (&registered_bridges); ++i) {
1093                 if (obj == dyn_array_ptr_get (&registered_bridges, i)) {
1094                         printf ("Pointer is a registered bridge object.\n");
1095                         break;
1096                 }
1097         }
1098
1099         // entry = sgen_hash_table_lookup (&hash_table, obj);
1100         // if (!entry)
1101         //      return;
1102         //
1103         // printf ("Bridge hash table entry %p:\n", entry);
1104         // printf ("  is bridge: %d\n", (int)entry->is_bridge);
1105         // printf ("  is visited: %d\n", (int)entry->is_visited);
1106 }
1107
1108 void
1109 sgen_tarjan_bridge_init (SgenBridgeProcessor *collector)
1110 {
1111         collector->reset_data = reset_data;
1112         collector->processing_stw_step = processing_stw_step;
1113         collector->processing_build_callback_data = processing_build_callback_data;
1114         collector->processing_after_callback = processing_after_callback;
1115         collector->class_kind = class_kind;
1116         collector->register_finalized_object = register_finalized_object;
1117         collector->describe_pointer = describe_pointer;
1118         collector->enable_accounting = enable_accounting;
1119         // collector->set_dump_prefix = set_dump_prefix;
1120
1121         sgen_register_fixed_internal_mem_type (INTERNAL_MEM_TARJAN_OBJ_BUCKET, BUCKET_SIZE);
1122         g_assert (sizeof (ObjectBucket) <= BUCKET_SIZE);
1123         g_assert (sizeof (ColorBucket) <= BUCKET_SIZE);
1124         bridge_processor = collector;
1125 }
1126
1127 #endif