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