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