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