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