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
  54 typedef struct {
  55         int size;
  56         int capacity;
  57         char *data;
  58 } DynArray;
  59
  60 /*Specializations*/
  61
  62 typedef struct {
  63         DynArray array;
  64 } DynPtrArray;
  65
  66 /* private */
  67
  68 static void
  69 dyn_array_uninit (DynArray *da, int elem_size)
  70 {
  71         if (da->capacity <= 0)
  72                 return;
  73
  74         sgen_free_internal_dynamic (da->data, elem_size * da->capacity, INTERNAL_MEM_BRIDGE_DATA);
  75         da->data = NULL;
  76 }
  77
  78 static void
  79 dyn_array_ensure_capacity (DynArray *da, int capacity, int elem_size)
  80 {
  81         int old_capacity = da->capacity;
  82         char *new_data;
  83
  84         if (capacity <= old_capacity)
  85                 return;
  86
  87         if (da->capacity == 0)
  88                 da->capacity = 2;
  89         while (capacity > da->capacity)
  90                 da->capacity *= 2;
  91
  92         new_data = sgen_alloc_internal_dynamic (elem_size * da->capacity, INTERNAL_MEM_BRIDGE_DATA, TRUE);
  93         if (da->data) {
  94                 memcpy (new_data, da->data, elem_size * da->size);
  95                 sgen_free_internal_dynamic (da->data, elem_size * old_capacity, INTERNAL_MEM_BRIDGE_DATA);
  96         }
  97         da->data = new_data;
  98 }
  99
 100 static void*
 101 dyn_array_add (DynArray *da, int elem_size)
 102 {
 103         void *p;
 104
 105         dyn_array_ensure_capacity (da, da->size + 1, elem_size);
 106
 107         p = da->data + da->size * elem_size;
 108         ++da->size;
 109         return p;
 110 }
 111
 112 /* ptr */
 113
 114 static void
 115 dyn_array_ptr_uninit (DynPtrArray *da)
 116 {
 117         dyn_array_uninit (&da->array, sizeof (void*));
 118 }
 119
 120 static int
 121 dyn_array_ptr_size (DynPtrArray *da)
 122 {
 123         return da->array.size;
 124 }
 125
 126 static void
 127 dyn_array_ptr_set_size (DynPtrArray *da, int size)
 128 {
 129         da->array.size = size;
 130 }
 131
 132 static void*
 133 dyn_array_ptr_get (DynPtrArray *da, int x)
 134 {
 135         return ((void**)da->array.data)[x];
 136 }
 137
 138 static void
 139 dyn_array_ptr_add (DynPtrArray *da, void *ptr)
 140 {
 141         void **p = dyn_array_add (&da->array, sizeof (void*));
 142         *p = ptr;
 143 }
 144
 145 #define dyn_array_ptr_push dyn_array_ptr_add
 146
 147 static void*
 148 dyn_array_ptr_pop (DynPtrArray *da)
 149 {
 150         void *p;
 151         int size = da->array.size;
 152         g_assert (size > 0);
 153         p = dyn_array_ptr_get (da, size - 1);
 154         --da->array.size;
 155         return p;
 156 }
 157
 158 static void
 159 dyn_array_ptr_ensure_capacity (DynPtrArray *da, int capacity)
 160 {
 161         dyn_array_ensure_capacity (&da->array, capacity, sizeof (void*));
 162 }
 163
 164
 165 static void
 166 dyn_array_ptr_set_all (DynPtrArray *dst, DynPtrArray *src)
 167 {
 168         if (src->array.size > 0) {
 169                 dyn_array_ptr_ensure_capacity (dst, src->array.size);
 170                 memcpy (dst->array.data, src->array.data, src->array.size * sizeof (void*));
 171         }
 172         dst->array.size = src->array.size;
 173 }
 174
 175 static void
 176 enable_accounting (void)
 177 {
 178         // bridge_accounting_enabled = TRUE;
 179         // 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);
 180 }
 181
 182 static MonoGCBridgeObjectKind
 183 class_kind (MonoClass *class)
 184 {
 185         MonoGCBridgeObjectKind res = bridge_callbacks.bridge_class_kind (class);
 186
 187         /* If it's a bridge, nothing we can do about it. */
 188         if (res == GC_BRIDGE_TRANSPARENT_BRIDGE_CLASS || res == GC_BRIDGE_OPAQUE_BRIDGE_CLASS)
 189                 return res;
 190
 191         /* Non bridge classes with no pointers will never point to a bridge, so we can savely ignore them. */
 192         if (!class->has_references) {
 193                 SGEN_LOG (6, "class %s is opaque\n", class->name);
 194                 return GC_BRIDGE_OPAQUE_CLASS;
 195         }
 196
 197         /* Some arrays can be ignored */
 198         if (class->rank == 1) {
 199                 MonoClass *elem_class = class->element_class;
 200
 201                 /* FIXME the bridge check can be quite expensive, cache it at the class level. */
 202                 /* An array of a sealed type that is not a bridge will never get to a bridge */
 203                 if ((elem_class->flags & TYPE_ATTRIBUTE_SEALED) && !elem_class->has_references && !bridge_callbacks.bridge_class_kind (elem_class)) {
 204                         SGEN_LOG (6, "class %s is opaque\n", class->name);
 205                         return GC_BRIDGE_OPAQUE_CLASS;
 206                 }
 207         }
 208
 209         return GC_BRIDGE_TRANSPARENT_CLASS;
 210 }
 211
 212 //enable unsage logging
 213 // #define DUMP_GRAPH 1
 214
 215 enum {
 216         INITIAL,
 217         SCANNED,
 218         FINISHED_ON_STACK,
 219         FINISHED_OFF_STACK
 220 };
 221
 222 /*
 223 Optimizations:
 224         We can split this data structure in two, those with bridges and those without
 225 */
 226 typedef struct {
 227         DynPtrArray other_colors;
 228         DynPtrArray bridges;
 229         int api_index    : 31;
 230         unsigned visited : 1;
 231 } ColorData;
 232
 233
 234 typedef struct {
 235         GCObject *obj; //XXX this can be eliminated.
 236         mword lock_word;
 237
 238         ColorData *color;
 239         int index;
 240         int low_index : 27;
 241
 242         unsigned state : 2;
 243         unsigned is_bridge : 1;
 244         unsigned obj_state : 2;
 245 } ScanData;
 246
 247
 248
 249
 250 static DynPtrArray scan_stack, loop_stack, registered_bridges;
 251 static DynPtrArray color_merge_array;
 252
 253 static int ignored_objects;
 254 static int object_index;
 255 static int num_colors_with_bridges;
 256 static int xref_count;
 257
 258 static size_t setup_time, tarjan_time, scc_setup_time, gather_xref_time, xref_setup_time, cleanup_time;
 259 static SgenBridgeProcessor *bridge_processor;
 260
 261 #define BUCKET_SIZE 8184
 262
 263 //ScanData buckets
 264 #define NUM_SCAN_ENTRIES ((BUCKET_SIZE - SIZEOF_VOID_P * 2) / sizeof (ScanData))
 265
 266 typedef struct _ObjectBucket ObjectBucket;
 267 struct _ObjectBucket {
 268         ObjectBucket *next;
 269         ScanData *next_data;
 270         ScanData data [NUM_SCAN_ENTRIES];
 271 };
 272
 273 static ObjectBucket *root_object_bucket;
 274 static ObjectBucket *cur_object_bucket;
 275 static int object_data_count;
 276
 277 static ObjectBucket*
 278 new_object_bucket (void)
 279 {
 280         ObjectBucket *res = sgen_alloc_internal (INTERNAL_MEM_TARJAN_OBJ_BUCKET);
 281         res->next_data = &res->data [0];
 282         return res;
 283 }
 284
 285 static void
 286 object_alloc_init (void)
 287 {
 288         root_object_bucket = cur_object_bucket = new_object_bucket ();
 289 }
 290
 291 static ScanData*
 292 alloc_object_data (void)
 293 {
 294         ScanData *res;
 295 retry:
 296
 297         /* next_data points to the first free entry */
 298         res = cur_object_bucket->next_data;
 299         if (res >= &cur_object_bucket->data [NUM_SCAN_ENTRIES]) {
 300                 ObjectBucket *b = new_object_bucket ();
 301                 cur_object_bucket->next = b;
 302                 cur_object_bucket = b;
 303                 goto retry;
 304         }
 305         cur_object_bucket->next_data = res + 1;
 306         object_data_count++;
 307         return res;
 308 }
 309
 310 static void
 311 free_object_buckets (void)
 312 {
 313         ObjectBucket *cur = root_object_bucket;
 314
 315         object_data_count = 0;
 316
 317         while (cur) {
 318                 ObjectBucket *tmp = cur->next;
 319                 sgen_free_internal (cur, INTERNAL_MEM_TARJAN_OBJ_BUCKET);
 320                 cur = tmp;
 321         }
 322
 323         root_object_bucket = cur_object_bucket = NULL;
 324 }
 325
 326 //ColorData buckets
 327 #define NUM_COLOR_ENTRIES ((BUCKET_SIZE - SIZEOF_VOID_P * 2) / sizeof (ColorData))
 328
 329 typedef struct _ColorBucket ColorBucket;
 330 struct _ColorBucket {
 331         ColorBucket *next;
 332         ColorData *next_data;
 333         ColorData data [NUM_COLOR_ENTRIES];
 334 };
 335
 336 static ColorBucket *root_color_bucket;
 337 static ColorBucket *cur_color_bucket;
 338 static int color_data_count;
 339
 340
 341 static ColorBucket*
 342 new_color_bucket (void)
 343 {
 344         ColorBucket *res = sgen_alloc_internal (INTERNAL_MEM_TARJAN_OBJ_BUCKET);
 345         res->next_data = &res->data [0];
 346         return res;
 347 }
 348
 349 static void
 350 color_alloc_init (void)
 351 {
 352         root_color_bucket = cur_color_bucket = new_color_bucket ();
 353 }
 354
 355 static ColorData*
 356 alloc_color_data (void)
 357 {
 358         ColorData *res;
 359 retry:
 360
 361         /* next_data points to the first free entry */
 362         res = cur_color_bucket->next_data;
 363         if (res >= &cur_color_bucket->data [NUM_COLOR_ENTRIES]) {
 364                 ColorBucket *b = new_color_bucket ();
 365                 cur_color_bucket->next = b;
 366                 cur_color_bucket = b;
 367                 goto retry;
 368         }
 369         cur_color_bucket->next_data = res + 1;
 370         color_data_count++;
 371         return res;
 372 }
 373
 374 static void
 375 free_color_buckets (void)
 376 {
 377         ColorBucket *cur, *tmp;
 378
 379         color_data_count = 0;
 380
 381         for (cur = root_color_bucket; cur; cur = tmp) {
 382                 ColorData *cd;
 383                 for (cd = &cur->data [0]; cd < cur->next_data; ++cd) {
 384                         dyn_array_ptr_uninit (&cd->other_colors);
 385                         dyn_array_ptr_uninit (&cd->bridges);
 386                 }
 387                 tmp = cur->next;
 388                 sgen_free_internal (cur, INTERNAL_MEM_TARJAN_OBJ_BUCKET);
 389         }
 390         root_color_bucket = cur_color_bucket = NULL;
 391 }
 392
 393
 394 static ScanData*
 395 create_data (GCObject *obj)
 396 {
 397         mword *o = (mword*)obj;
 398         ScanData *res = alloc_object_data ();
 399         res->obj = obj;
 400         res->color = NULL;
 401         res->index = res->low_index = -1;
 402         res->obj_state = o [0] & SGEN_VTABLE_BITS_MASK;
 403         res->lock_word = o [1];
 404
 405         o [0] |= SGEN_VTABLE_BITS_MASK;
 406         o [1] = (mword)res;
 407         return res;
 408 }
 409
 410 static ScanData*
 411 find_data (GCObject *obj)
 412 {
 413         ScanData *a = NULL;
 414         mword *o = (mword*)obj;
 415         if ((o [0] & SGEN_VTABLE_BITS_MASK) == SGEN_VTABLE_BITS_MASK)
 416                 a = (ScanData*)o [1];
 417         return a;
 418 }
 419
 420 static void
 421 clear_after_processing (void)
 422 {
 423         ObjectBucket *cur;
 424
 425         for (cur = root_object_bucket; cur; cur = cur->next) {
 426                 ScanData *sd;
 427                 for (sd = &cur->data [0]; sd < cur->next_data; ++sd) {
 428                         mword *o = (mword*)sd->obj;
 429                         o [0] &= ~SGEN_VTABLE_BITS_MASK;
 430                         o [0] |= sd->obj_state;
 431                         o [1] = sd->lock_word;
 432                 }
 433         }
 434 }
 435
 436 static GCObject*
 437 bridge_object_forward (GCObject *obj)
 438 {
 439         GCObject *fwd;
 440         mword *o = (mword*)obj;
 441         if ((o [0] & SGEN_VTABLE_BITS_MASK) == SGEN_VTABLE_BITS_MASK)
 442                 return obj;
 443
 444         fwd = SGEN_OBJECT_IS_FORWARDED (obj);
 445         return fwd ? fwd : obj;
 446 }
 447
 448 #ifdef DUMP_GRAPH
 449 static const char*
 450 safe_name_bridge (GCObject *obj)
 451 {
 452         GCVTable *vt = (GCVTable*)SGEN_LOAD_VTABLE (obj);
 453         return vt->klass->name;
 454 }
 455
 456 static ScanData*
 457 find_or_create_data (GCObject *obj)
 458 {
 459         ScanData *entry = find_data (obj);
 460         if (!entry)
 461                 entry = create_data (obj);
 462         return entry;
 463 }
 464 #endif
 465
 466 //----------
 467 typedef struct {
 468         ColorData *color;
 469         int hash;
 470 } HashEntry;
 471
 472 /*
 473 We tried 2/32, 2/128, 4/32, 4/128, 6/128 and 8/128.
 474
 475 The performance cost between 4/128 and 8/128 is so small since cache movement happens completely in the same cacheline,
 476 making the extra space pretty much free.
 477
 478 The cost between 32 and 128 itens is minimal too, it's mostly a fixed, setup cost.
 479
 480 Memory wise, 4/32 takes 512 and 8/128 takes 8k, so it's quite reasonable.
 481 */
 482
 483 #define ELEMENTS_PER_BUCKET 8
 484 #define COLOR_CACHE_SIZE 128
 485 static HashEntry merge_cache [COLOR_CACHE_SIZE][ELEMENTS_PER_BUCKET];
 486
 487 static int
 488 mix_hash (size_t hash)
 489 {
 490         return (int)(((hash * 215497) >> 16) ^ ((hash * 1823231) + hash));
 491 }
 492
 493 static void
 494 reset_cache (void)
 495 {
 496         memset (merge_cache, 0, sizeof (merge_cache));
 497 }
 498
 499
 500 static gboolean
 501 dyn_array_ptr_contains (DynPtrArray *da, void *x)
 502 {
 503         int i;
 504         for (i = 0; i < dyn_array_ptr_size (da); ++i)
 505                 if (dyn_array_ptr_get (da, i) == x)
 506                         return TRUE;
 507         return FALSE;
 508 }
 509
 510 static gboolean
 511 match_colors (DynPtrArray *a, DynPtrArray *b)
 512 {
 513         int i;
 514         if (dyn_array_ptr_size (a) != dyn_array_ptr_size (b))
 515                 return FALSE;
 516
 517         for (i = 0; i < dyn_array_ptr_size (a); ++i) {
 518                 if (!dyn_array_ptr_contains (b, dyn_array_ptr_get (a, i)))
 519                         return FALSE;
 520         }
 521         return TRUE;
 522 }
 523
 524 static int cache_hits, cache_misses;
 525
 526 static ColorData*
 527 find_in_cache (int *insert_index)
 528 {
 529         HashEntry *bucket;
 530         int i, hash, size, index;
 531
 532         size = dyn_array_ptr_size (&color_merge_array);
 533         /* Cache checking is very ineficient with a lot of elements*/
 534         if (size > 3)
 535                 return NULL;
 536
 537         hash = 0;
 538         for (i = 0 ; i < size; ++i)
 539                 hash += mix_hash ((size_t)dyn_array_ptr_get (&color_merge_array, i));
 540         if (!hash)
 541                 hash = 1;
 542
 543         index = hash & (COLOR_CACHE_SIZE - 1);
 544         bucket = merge_cache [index];
 545         for (i = 0; i < ELEMENTS_PER_BUCKET; ++i) {
 546                 if (bucket [i].hash != hash)
 547                         continue;
 548                 if (match_colors (&bucket [i].color->other_colors, &color_merge_array)) {
 549                         ++cache_hits;
 550                         return bucket [i].color;
 551                 }
 552         }
 553
 554         //move elements to the back
 555         for (i = ELEMENTS_PER_BUCKET - 1; i > 0; --i)
 556                 bucket [i] = bucket [i - 1];
 557         ++cache_misses;
 558         *insert_index = index;
 559         bucket [0].hash = hash;
 560         return NULL;
 561 }
 562
 563 static ColorData*
 564 new_color (gboolean force_new)
 565 {
 566         int i = -1;
 567         ColorData *cd;
 568         /* XXX Try to find an equal one and return it */
 569         if (!force_new) {
 570                 cd = find_in_cache (&i);
 571                 if (cd)
 572                         return cd;
 573         }
 574
 575         cd = alloc_color_data ();
 576         cd->api_index = -1;
 577         dyn_array_ptr_set_all (&cd->other_colors, &color_merge_array);
 578         /* if i >= 0, it means we prepared a given slot to receive the new color */
 579         if (i >= 0)
 580                 merge_cache [i][0].color = cd;
 581
 582         return cd;
 583 }
 584
 585
 586 static void
 587 register_bridge_object (GCObject *obj)
 588 {
 589         create_data (obj)->is_bridge = TRUE;
 590 }
 591
 592 static gboolean
 593 is_opaque_object (GCObject *obj)
 594 {
 595         MonoVTable *vt = (MonoVTable*)SGEN_LOAD_VTABLE (obj);
 596         if ((vt->gc_bits & SGEN_GC_BIT_BRIDGE_OPAQUE_OBJECT) == SGEN_GC_BIT_BRIDGE_OPAQUE_OBJECT) {
 597                 SGEN_LOG (6, "ignoring %s\n", vt->klass->name);
 598                 ++ignored_objects;
 599                 return TRUE;
 600         }
 601         return FALSE;
 602 }
 603
 604 static void
 605 push_object (GCObject *obj)
 606 {
 607         ScanData *data;
 608         obj = bridge_object_forward (obj);
 609
 610 #if DUMP_GRAPH
 611         printf ("\t= pushing %p %s -> ", obj, safe_name_bridge (obj));
 612 #endif
 613
 614         /* Object types we can ignore */
 615         if (is_opaque_object (obj)) {
 616 #if DUMP_GRAPH
 617                 printf ("opaque\n");
 618 #endif
 619                 return;
 620         }
 621
 622         data = find_data (obj);
 623
 624         /* Already marked - XXX must be done this way as the bridge themselves are alive. */
 625         if (data && data->state != INITIAL) {
 626 #if DUMP_GRAPH
 627                 printf ("already marked\n");
 628 #endif
 629                 return;
 630         }
 631
 632         /* We only care about dead objects */
 633         if (!data && sgen_object_is_live (obj)) {
 634 #if DUMP_GRAPH
 635                 printf ("alive\n");
 636 #endif
 637                 return;
 638         }
 639
 640 #if DUMP_GRAPH
 641         printf ("pushed!\n");
 642 #endif
 643
 644         if (!data)
 645                 data = create_data (obj);
 646         g_assert (data->state == INITIAL);
 647         g_assert (data->index == -1);
 648         dyn_array_ptr_push (&scan_stack, data);
 649 }
 650
 651 #undef HANDLE_PTR
 652 #define HANDLE_PTR(ptr,obj)     do {                                    \
 653                 GCObject *dst = (GCObject*)*(ptr);                      \
 654                 if (dst) push_object (dst);                     \
 655         } while (0)
 656
 657 static void
 658 push_all (ScanData *data)
 659 {
 660         GCObject *obj = data->obj;
 661         char *start = (char*)obj;
 662         mword desc = sgen_obj_get_descriptor_safe (start);
 663
 664 #if DUMP_GRAPH
 665         printf ("**scanning %p %s\n", obj, safe_name_bridge (obj));
 666 #endif
 667
 668         #include "sgen-scan-object.h"
 669 }
 670
 671
 672 static void
 673 compute_low_index (ScanData *data, GCObject *obj)
 674 {
 675         ScanData *other;
 676         ColorData *cd;
 677         obj = bridge_object_forward (obj);
 678
 679         other = find_data (obj);
 680
 681 #if DUMP_GRAPH
 682         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);
 683 #endif
 684         if (!other)
 685                 return;
 686
 687         g_assert (other->state != INITIAL);
 688
 689         if ((other->state == SCANNED || other->state == FINISHED_ON_STACK) && data->low_index > other->low_index)
 690                 data->low_index = other->low_index;
 691
 692         /* Compute the low color */
 693         if (other->color == NULL)
 694                 return;
 695
 696         cd = other->color;
 697         if (!cd->visited) {
 698                 dyn_array_ptr_add (&color_merge_array, other->color);
 699                 cd->visited = TRUE;
 700         }
 701 }
 702
 703 #undef HANDLE_PTR
 704 #define HANDLE_PTR(ptr,obj)     do {                                    \
 705                 GCObject *dst = (GCObject*)*(ptr);                      \
 706                 if (dst) compute_low_index (data, dst);                         \
 707         } while (0)
 708
 709 static void
 710 compute_low (ScanData *data)
 711 {
 712         GCObject *obj = data->obj;
 713         char *start = (char*)obj;
 714         mword desc = sgen_obj_get_descriptor_safe (start);
 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 (GCObject *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                                         GCObject *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 (GCObject *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