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