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