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         mword desc = sgen_obj_get_descriptor (start);
 665
 666 #if DUMP_GRAPH
 667         printf ("**scanning %p %s\n", obj, safe_name_bridge (obj));
 668 #endif
 669
 670         #include "sgen-scan-object.h"
 671 }
 672
 673
 674 static void
 675 compute_low_index (ScanData *data, MonoObject *obj)
 676 {
 677         ScanData *other;
 678         ColorData *cd;
 679         obj = bridge_object_forward (obj);
 680
 681         other = find_data (obj);
 682
 683 #if DUMP_GRAPH
 684         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);
 685 #endif
 686         if (!other)
 687                 return;
 688
 689         g_assert (other->state != INITIAL);
 690
 691         if ((other->state == SCANNED || other->state == FINISHED_ON_STACK) && data->low_index > other->low_index)
 692                 data->low_index = other->low_index;
 693
 694         /* Compute the low color */
 695         if (other->color == NULL)
 696                 return;
 697
 698         cd = other->color;
 699         if (!cd->visited) {
 700                 dyn_array_ptr_add (&color_merge_array, other->color);
 701                 cd->visited = TRUE;
 702         }
 703 }
 704
 705 #undef HANDLE_PTR
 706 #define HANDLE_PTR(ptr,obj)     do {                                    \
 707                 MonoObject *dst = (MonoObject*)*(ptr);                  \
 708                 if (dst) compute_low_index (data, dst);                         \
 709         } while (0)
 710
 711 static void
 712 compute_low (ScanData *data)
 713 {
 714         MonoObject *obj = data->obj;
 715         char *start = (char*)obj;
 716         mword desc = sgen_obj_get_descriptor (start);
 717
 718         #include "sgen-scan-object.h"
 719 }
 720
 721 static ColorData*
 722 reduce_color (void)
 723 {
 724         ColorData *color = NULL;
 725         int size = dyn_array_ptr_size (&color_merge_array);
 726
 727         if (size == 0)
 728                 color = NULL;
 729         else if (size == 1) {
 730                 color = dyn_array_ptr_get (&color_merge_array, 0);
 731         } else
 732                 color = new_color (FALSE);
 733
 734         return color;
 735 }
 736
 737 static void
 738 create_scc (ScanData *data)
 739 {
 740         int i;
 741         gboolean found = FALSE;
 742         gboolean found_bridge = FALSE;
 743         ColorData *color_data = NULL;
 744
 745         for (i = dyn_array_ptr_size (&loop_stack) - 1; i >= 0; --i) {
 746                 ScanData *other = dyn_array_ptr_get (&loop_stack, i);
 747                 found_bridge |= other->is_bridge;
 748                 if (found_bridge || other == data)
 749                         break;
 750         }
 751
 752 #if DUMP_GRAPH
 753         printf ("|SCC rooted in %s (%p) has bridge %d\n", safe_name_bridge (data->obj), data->obj, found_bridge);
 754         printf ("\tpoints-to-colors: ");
 755         for (i = 0; i < dyn_array_ptr_size (&color_merge_array); ++i)
 756                 printf ("%p ", dyn_array_ptr_get (&color_merge_array, i));
 757         printf ("\n");
 758
 759         printf ("loop stack: ");
 760         for (i = 0; i < dyn_array_ptr_size (&loop_stack); ++i) {
 761                 ScanData *other = dyn_array_ptr_get (&loop_stack, i);
 762                 printf ("(%d/%d)", other->index, other->low_index);
 763         }
 764         printf ("\n");
 765 #endif
 766
 767         if (found_bridge) {
 768                 color_data = new_color (TRUE);
 769                 ++num_colors_with_bridges;
 770         } else {
 771                 color_data = reduce_color ();
 772         }
 773
 774         while (dyn_array_ptr_size (&loop_stack) > 0) {
 775                 ScanData *other = dyn_array_ptr_pop (&loop_stack);
 776
 777 #if DUMP_GRAPH
 778                 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);
 779 #endif
 780
 781                 other->color = color_data;
 782                 switch (other->state) {
 783                 case FINISHED_ON_STACK:
 784                         other->state = FINISHED_OFF_STACK;
 785                         break;
 786                 case FINISHED_OFF_STACK:
 787                         break;
 788                 default:
 789                         g_error ("Invalid state when building SCC %d", other->state);
 790                 }
 791
 792                 if (other->is_bridge)
 793                         dyn_array_ptr_add (&color_data->bridges, other->obj);
 794
 795                 if (other == data) {
 796                         found = TRUE;
 797                         break;
 798                 }
 799         }
 800         g_assert (found);
 801
 802         for (i = 0; i < dyn_array_ptr_size (&color_merge_array); ++i) {
 803                 ColorData *cd  = dyn_array_ptr_get (&color_merge_array, i);
 804                 g_assert (cd->visited);
 805                 cd->visited = FALSE;
 806         }
 807         dyn_array_ptr_set_size (&color_merge_array, 0);
 808         found_bridge = FALSE;
 809 }
 810
 811 static void
 812 dfs (void)
 813 {
 814         g_assert (dyn_array_ptr_size (&scan_stack) == 1);
 815         g_assert (dyn_array_ptr_size (&loop_stack) == 0);
 816
 817         dyn_array_ptr_set_size (&color_merge_array, 0);
 818
 819         while (dyn_array_ptr_size (&scan_stack) > 0) {
 820                 ScanData *data = dyn_array_ptr_pop (&scan_stack);
 821
 822                 /**
 823                  * Ignore finished objects on stack, they happen due to loops. For example:
 824                  * A -> C
 825                  * A -> B
 826                  * B -> C
 827                  * C -> A
 828                  *
 829                  * We start scanning from A and push C before B. So, after the first iteration, the scan stack will have: A C B.
 830                  * We then visit B, which will find C in its initial state and push again.
 831                  * Finally after finish with C and B, the stack will be left with "A C" and at this point C should be ignored.
 832          *
 833          * The above explains FINISHED_ON_STACK, to explain FINISHED_OFF_STACK, consider if the root was D, which pointed
 834                  * to A and C. A is processed first, leaving C on stack after that in the mentioned state.
 835                  */
 836                 if (data->state == FINISHED_ON_STACK || data->state == FINISHED_OFF_STACK)
 837                         continue;
 838
 839                 if (data->state == INITIAL) {
 840                         g_assert (data->index == -1);
 841                         g_assert (data->low_index == -1);
 842
 843                         data->state = SCANNED;
 844                         data->low_index = data->index = object_index++;
 845                         dyn_array_ptr_push (&scan_stack, data);
 846                         dyn_array_ptr_push (&loop_stack, data);
 847
 848 #if DUMP_GRAPH
 849                         printf ("+scanning %s (%p) index %d color %p\n", safe_name_bridge (data->obj), data->obj, data->index, data->color);
 850 #endif
 851                         /*push all refs */
 852                         push_all (data);
 853                 } else {
 854                         g_assert (data->state == SCANNED);
 855                         data->state = FINISHED_ON_STACK;
 856
 857 #if DUMP_GRAPH
 858                         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);
 859 #endif
 860
 861                         /* Compute low index */
 862                         compute_low (data);
 863
 864 #if DUMP_GRAPH
 865                         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);
 866 #endif
 867                         //SCC root
 868                         if (data->index == data->low_index)
 869                                 create_scc (data);
 870                 }
 871         }
 872 }
 873
 874 static void
 875 register_finalized_object (MonoObject *obj)
 876 {
 877         g_assert (sgen_need_bridge_processing ());
 878         dyn_array_ptr_push (&registered_bridges, obj);
 879 }
 880
 881 static void
 882 reset_data (void)
 883 {
 884         dyn_array_ptr_set_size (&registered_bridges, 0);
 885 }
 886
 887 static void
 888 cleanup (void)
 889 {
 890         dyn_array_ptr_set_size (&scan_stack, 0);
 891         dyn_array_ptr_set_size (&loop_stack, 0);
 892         dyn_array_ptr_set_size (&registered_bridges, 0);
 893         free_object_buckets ();
 894         free_color_buckets ();
 895         reset_cache ();
 896         object_index = 0;
 897         num_colors_with_bridges = 0;
 898 }
 899
 900 #ifdef DUMP_GRAPH
 901 static void
 902 dump_color_table (const char *why, gboolean do_index)
 903 {
 904         ColorBucket *cur;
 905         int i = 0, j;
 906         printf ("colors%s:\n", why);
 907
 908         for (cur = root_color_bucket; cur; cur = cur->next, ++i) {
 909                 ColorData *cd;
 910                 for (cd = &cur->data [0]; cd < cur->next_data; ++cd) {
 911                         if (do_index)
 912                                 printf ("\t%d(%d):", i, cd->api_index);
 913                         else
 914                                 printf ("\t%d: ", i);
 915                         for (j = 0; j < dyn_array_ptr_size (&cd->other_colors); ++j) {
 916                                 printf ("%p ", dyn_array_ptr_get (&cd->other_colors, j));
 917                         }
 918                         if (dyn_array_ptr_size (&cd->bridges)) {
 919                                 printf (" bridges: ");
 920                                 for (j = 0; j < dyn_array_ptr_size (&cd->bridges); ++j) {
 921                                         MonoObject *obj = dyn_array_ptr_get (&cd->bridges, j);
 922                                         ScanData *data = find_or_create_data (obj);
 923                                         printf ("%d ", data->index);
 924                                 }
 925                         }
 926                         printf ("\n");
 927                 }
 928         }
 929
 930 }
 931 #endif
 932
 933 static gint64
 934 step_timer (gint64 *timer)
 935 {
 936         gint64 curtime, diff;
 937
 938         SGEN_TV_GETTIME (curtime);
 939         diff = SGEN_TV_ELAPSED (*timer, curtime);
 940         *timer = curtime;
 941         return diff;
 942 }
 943 static void
 944 processing_stw_step (void)
 945 {
 946         int i;
 947         int bridge_count;
 948         gint64 curtime;
 949
 950         if (!dyn_array_ptr_size (&registered_bridges))
 951                 return;
 952
 953 #if defined (DUMP_GRAPH)
 954         printf ("-----------------\n");
 955 #endif
 956         /*
 957          * bridge_processing_in_progress must be set with the world
 958          * stopped.  If not there would be race conditions.
 959          */
 960         bridge_processing_in_progress = TRUE;
 961
 962         SGEN_TV_GETTIME (curtime);
 963
 964         object_alloc_init ();
 965         color_alloc_init ();
 966
 967         bridge_count = dyn_array_ptr_size (&registered_bridges);
 968         for (i = 0; i < bridge_count ; ++i)
 969                 register_bridge_object (dyn_array_ptr_get (&registered_bridges, i));
 970
 971         setup_time = step_timer (&curtime);
 972
 973         for (i = 0; i < bridge_count; ++i) {
 974                 ScanData *sd = find_data (dyn_array_ptr_get (&registered_bridges, i));
 975                 if (sd->state == INITIAL) {
 976                         dyn_array_ptr_push (&scan_stack, sd);
 977                         dfs ();
 978                 } else {
 979                         g_assert (sd->state == FINISHED_OFF_STACK);
 980                 }
 981         }
 982
 983         tarjan_time = step_timer (&curtime);
 984
 985 #if defined (DUMP_GRAPH)
 986         printf ("----summary----\n");
 987         printf ("bridges:\n");
 988         for (i = 0; i < bridge_count; ++i) {
 989                 ScanData *sd = find_data (dyn_array_ptr_get (&registered_bridges, i));
 990                 printf ("\t%s (%p) index %d color %p\n", safe_name_bridge (sd->obj), sd->obj, sd->index, sd->color);
 991         }
 992
 993         dump_color_table (" after tarjan", FALSE);
 994 #endif
 995
 996         clear_after_processing ();
 997 }
 998
 999
1000 static void
1001 gather_xrefs (ColorData *color)
1002 {
1003         int i;
1004         for (i = 0; i < dyn_array_ptr_size (&color->other_colors); ++i) {
1005                 ColorData *src = dyn_array_ptr_get (&color->other_colors, i);
1006                 if (src->visited)
1007                         continue;
1008                 src->visited = TRUE;
1009                 if (dyn_array_ptr_size (&src->bridges))
1010                         dyn_array_ptr_add (&color_merge_array, src);
1011                 else
1012                         gather_xrefs (src);
1013         }
1014 }
1015
1016 static void
1017 reset_xrefs (ColorData *color)
1018 {
1019         int i;
1020         for (i = 0; i < dyn_array_ptr_size (&color->other_colors); ++i) {
1021                 ColorData *src = dyn_array_ptr_get (&color->other_colors, i);
1022                 if (!src->visited)
1023                         continue;
1024                 src->visited = FALSE;
1025                 if (!dyn_array_ptr_size (&src->bridges))
1026                         reset_xrefs (src);
1027         }
1028 }
1029
1030 static void
1031 processing_build_callback_data (int generation)
1032 {
1033         int j, api_index;
1034         MonoGCBridgeSCC **api_sccs;
1035         MonoGCBridgeXRef *api_xrefs;
1036         gint64 curtime;
1037         ColorBucket *cur;
1038
1039         g_assert (bridge_processor->num_sccs == 0 && bridge_processor->num_xrefs == 0);
1040         g_assert (!bridge_processor->api_sccs && !bridge_processor->api_xrefs);
1041
1042         if (!dyn_array_ptr_size (&registered_bridges))
1043                 return;
1044
1045         SGEN_TV_GETTIME (curtime);
1046
1047         /*create API objects */
1048
1049 #if defined (DUMP_GRAPH)
1050         printf ("***** API *****\n");
1051         printf ("number of SCCs %d\n", num_colors_with_bridges);
1052 #endif
1053
1054         /* This is a straightforward translation from colors to the bridge callback format. */
1055         api_sccs = sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC*) * num_colors_with_bridges, INTERNAL_MEM_BRIDGE_DATA, TRUE);
1056         api_index = xref_count = 0;
1057
1058         for (cur = root_color_bucket; cur; cur = cur->next) {
1059                 ColorData *cd;
1060                 for (cd = &cur->data [0]; cd < cur->next_data; ++cd) {
1061                         int bridges = dyn_array_ptr_size (&cd->bridges);
1062                         if (!bridges)
1063                                 continue;
1064
1065                         api_sccs [api_index] = sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC) + sizeof (MonoObject*) * bridges, INTERNAL_MEM_BRIDGE_DATA, TRUE);
1066                         api_sccs [api_index]->is_alive = FALSE;
1067                         api_sccs [api_index]->num_objs = bridges;
1068
1069                         cd->api_index = api_index;
1070
1071                         for (j = 0; j < bridges; ++j)
1072                                 api_sccs [api_index]->objs [j] = dyn_array_ptr_get (&cd->bridges, j);
1073                         api_index++;
1074                 }
1075         }
1076
1077         scc_setup_time = step_timer (&curtime);
1078
1079         for (cur = root_color_bucket; cur; cur = cur->next) {
1080                 ColorData *cd;
1081                 for (cd = &cur->data [0]; cd < cur->next_data; ++cd) {
1082                         int bridges = dyn_array_ptr_size (&cd->bridges);
1083                         if (!bridges)
1084                                 continue;
1085
1086                         dyn_array_ptr_set_size (&color_merge_array, 0);
1087                         gather_xrefs (cd);
1088                         reset_xrefs (cd);
1089                         dyn_array_ptr_set_all (&cd->other_colors, &color_merge_array);
1090                         xref_count += dyn_array_ptr_size (&cd->other_colors);
1091                 }
1092         }
1093
1094         gather_xref_time = step_timer (&curtime);
1095
1096 #if defined (DUMP_GRAPH)
1097         printf ("TOTAL XREFS %d\n", xref_count);
1098         dump_color_table (" after xref pass", TRUE);
1099 #endif
1100
1101         api_xrefs = sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeXRef) * xref_count, INTERNAL_MEM_BRIDGE_DATA, TRUE);
1102         api_index = 0;
1103         for (cur = root_color_bucket; cur; cur = cur->next) {
1104                 ColorData *src;
1105                 for (src = &cur->data [0]; src < cur->next_data; ++src) {
1106                         int bridges = dyn_array_ptr_size (&src->bridges);
1107                         if (!bridges)
1108                                 continue;
1109
1110                         for (j = 0; j < dyn_array_ptr_size (&src->other_colors); ++j) {
1111                                 ColorData *dest = dyn_array_ptr_get (&src->other_colors, j);
1112                                 g_assert (dyn_array_ptr_size (&dest->bridges)); /* We flattened the color graph, so this must never happen. */
1113
1114                                 api_xrefs [api_index].src_scc_index = src->api_index;
1115                                 api_xrefs [api_index].dst_scc_index = dest->api_index;
1116                                 ++api_index;
1117                         }
1118                 }
1119         }
1120
1121         g_assert (xref_count == api_index);
1122         xref_setup_time = step_timer (&curtime);
1123
1124 #if defined (DUMP_GRAPH)
1125         printf ("---xrefs:\n");
1126         for (i = 0; i < xref_count; ++i)
1127                 printf ("\t%d -> %d\n", api_xrefs [i].src_scc_index, api_xrefs [i].dst_scc_index);
1128 #endif
1129
1130         //FIXME move half of the cleanup to before the bridge callback?
1131         bridge_processor->num_sccs = num_colors_with_bridges;
1132         bridge_processor->api_sccs = api_sccs;
1133         bridge_processor->num_xrefs = xref_count;
1134         bridge_processor->api_xrefs = api_xrefs;
1135 }
1136
1137 static void
1138 processing_after_callback (int generation)
1139 {
1140         gint64 curtime;
1141         int bridge_count = dyn_array_ptr_size (&registered_bridges);
1142         int object_count = object_data_count;
1143         int color_count = color_data_count;
1144         int scc_count = num_colors_with_bridges;
1145
1146         SGEN_TV_GETTIME (curtime);
1147
1148         /* cleanup */
1149         cleanup ();
1150
1151         cleanup_time = step_timer (&curtime);
1152
1153         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",
1154                 bridge_count, object_count, color_count,
1155                 ignored_objects, scc_count, xref_count,
1156                 cache_hits, cache_misses,
1157                 setup_time / 10000.0f,
1158                 tarjan_time / 10000.0f,
1159                 scc_setup_time / 10000.0f,
1160                 gather_xref_time / 10000.0f,
1161                 xref_setup_time / 10000.0f,
1162                 cleanup_time / 10000.0f);
1163
1164         cache_hits = cache_misses = 0;
1165         ignored_objects = 0;
1166         bridge_processing_in_progress = FALSE;
1167 }
1168
1169 static void
1170 describe_pointer (MonoObject *obj)
1171 {
1172         // HashEntry *entry;
1173         int i;
1174
1175         for (i = 0; i < dyn_array_ptr_size (&registered_bridges); ++i) {
1176                 if (obj == dyn_array_ptr_get (&registered_bridges, i)) {
1177                         printf ("Pointer is a registered bridge object.\n");
1178                         break;
1179                 }
1180         }
1181
1182         // entry = sgen_hash_table_lookup (&hash_table, obj);
1183         // if (!entry)
1184         //      return;
1185         //
1186         // printf ("Bridge hash table entry %p:\n", entry);
1187         // printf ("  is bridge: %d\n", (int)entry->is_bridge);
1188         // printf ("  is visited: %d\n", (int)entry->is_visited);
1189 }
1190
1191 void
1192 sgen_tarjan_bridge_init (SgenBridgeProcessor *collector)
1193 {
1194         collector->reset_data = reset_data;
1195         collector->processing_stw_step = processing_stw_step;
1196         collector->processing_build_callback_data = processing_build_callback_data;
1197         collector->processing_after_callback = processing_after_callback;
1198         collector->class_kind = class_kind;
1199         collector->register_finalized_object = register_finalized_object;
1200         collector->describe_pointer = describe_pointer;
1201         collector->enable_accounting = enable_accounting;
1202         // collector->set_dump_prefix = set_dump_prefix;
1203
1204         sgen_register_fixed_internal_mem_type (INTERNAL_MEM_TARJAN_OBJ_BUCKET, BUCKET_SIZE);
1205         g_assert (sizeof (ObjectBucket) <= BUCKET_SIZE);
1206         g_assert (sizeof (ColorBucket) <= BUCKET_SIZE);
1207         bridge_processor = collector;
1208 }
1209
1210 #endif