mono/metadata/sgen-tarjan-bridge.c

   1 /**
   2  * \file
   3  * Tarjan-based bridge implementation.
   4  *
   5  * Copyright 2011 Novell, Inc (http://www.novell.com)
   6  * Copyright 2014 Xamarin Inc (http://www.xamarin.com)
   7  *
   8  *
   9  * Copyright 2001-2003 Ximian, Inc
  10  * Copyright 2003-2010 Novell, Inc.
  11  *
  12  * Licensed under the MIT license. See LICENSE file in the project root for full license information.
  13  */
  14
  15 #include "config.h"
  16
  17 #ifdef HAVE_SGEN_GC
  18
  19 #include <stdlib.h>
  20
  21 #include "sgen/sgen-gc.h"
  22 #include "sgen-bridge-internals.h"
  23 #include "tabledefs.h"
  24 #include "utils/mono-logger-internals.h"
  25
  26 #include "sgen-dynarray.h"
  27
  28 /*
  29  * See comments in sgen-bridge.h
  30  *
  31  * This bridge implementation is based on the tarjan algorithm for strongly
  32  * connected components. It has two elements:
  33  *
  34  *   - Standard tarjan SCC algorithm to convert graph to SCC forest
  35  *
  36  *   - "Colors": We reduce the SCC forest to bridged-SCCs-only by using a
  37  *     "color" algorithm devised by Kumpera. Consider the set of bridged SCCs
  38  *     which is reachable from a given object. We call each such unique set a
  39  *     "color". We compute the set of colors and which colors contain links to
  40  *     which colors. The color graph then becomes the reduced SCC graph.
  41  */
  42
  43 // Is this class bridged or not, and should its dependencies be scanned or not?
  44 // The result of this callback will be cached for use by is_opaque_object later.
  45 static MonoGCBridgeObjectKind
  46 class_kind (MonoClass *klass)
  47 {
  48         MonoGCBridgeObjectKind res = bridge_callbacks.bridge_class_kind (klass);
  49
  50         /* If it's a bridge, nothing we can do about it. */
  51         if (res == GC_BRIDGE_TRANSPARENT_BRIDGE_CLASS || res == GC_BRIDGE_OPAQUE_BRIDGE_CLASS)
  52                 return res;
  53
  54         /* Non bridge classes with no pointers will never point to a bridge, so we can savely ignore them. */
  55         if (!klass->has_references) {
  56                 SGEN_LOG (6, "class %s is opaque\n", klass->name);
  57                 return GC_BRIDGE_OPAQUE_CLASS;
  58         }
  59
  60         /* Some arrays can be ignored */
  61         if (klass->rank == 1) {
  62                 MonoClass *elem_class = klass->element_class;
  63
  64                 /* FIXME the bridge check can be quite expensive, cache it at the class level. */
  65                 /* An array of a sealed type that is not a bridge will never get to a bridge */
  66                 if ((mono_class_get_flags (elem_class) & TYPE_ATTRIBUTE_SEALED) && !elem_class->has_references && !bridge_callbacks.bridge_class_kind (elem_class)) {
  67                         SGEN_LOG (6, "class %s is opaque\n", klass->name);
  68                         return GC_BRIDGE_OPAQUE_CLASS;
  69                 }
  70         }
  71
  72         return GC_BRIDGE_TRANSPARENT_CLASS;
  73 }
  74
  75 //enable usage logging
  76 // #define DUMP_GRAPH 1
  77
  78 /* Used in bridgeless_color_is_heavy:
  79  * The idea here is as long as the reference fanin and fanout on a node are both 2 or greater, then
  80  * removing that node will result in a net increase in edge count. So the question is which node
  81  * removals are counterproductive (i.e., how many edges saved balances out one node added).
  82  * The number of edges saved by preserving a node is (fanin*fanout - fanin - fanout).
  83  *
  84  * With all that in mind:
  85  *
  86  * - HEAVY_REFS_MIN is the number that *both* fanin and fanout must meet to preserve the node.
  87  * - HEAVY_COMBINED_REFS_MIN is the number (fanin*fanout) must meet to preserve the node.
  88  *
  89  * Note HEAVY_COMBINED_REFS_MIN must be <= 2*INCOMING_COLORS_MAX, or we won't know the true fanin.
  90  */
  91
  92 #define HEAVY_REFS_MIN 2
  93 #define HEAVY_COMBINED_REFS_MIN 60
  94
  95 /* Used in ColorData:
  96  * The higher INCOMING_COLORS_BITS is the higher HEAVY_COMBINED_REFS_MIN can be (see above).
  97  * However, API_INDEX_BITS + INCOMING_COLORS_BITS must be equal to 31, and if API_INDEX_BITS is too
  98  * low then terrible things will happen if too many colors are generated. (The number of colors we
  99  * will ever attempt to generate is currently naturally limited by the JNI GREF limit.)
 100  */
 101
 102 #define API_INDEX_BITS        26
 103 #define INCOMING_COLORS_BITS  5
 104
 105 #define API_INDEX_MAX         ((1<<API_INDEX_BITS)-1)
 106 #define INCOMING_COLORS_MAX   ((1<<INCOMING_COLORS_BITS)-1)
 107
 108 // ScanData state
 109 enum {
 110         INITIAL,
 111         SCANNED,
 112         FINISHED_ON_STACK,
 113         FINISHED_OFF_STACK
 114 };
 115
 116 /*
 117 Optimizations:
 118         We can split this data structure in two, those with bridges and those without
 119         (and only bridgeless need to record incoming_colors)
 120 */
 121 typedef struct {
 122         // Colors (ColorDatas) linked to by objects with this color
 123         DynPtrArray other_colors;
 124         // Bridge objects (GCObjects) held by objects with this color
 125         DynPtrArray bridges;
 126         // Index of this color's MonoGCBridgeSCC in the array passed to the client (or -1 for none)
 127         signed api_index         : API_INDEX_BITS;
 128         // Count of colors that list this color in their other_colors
 129         unsigned incoming_colors : INCOMING_COLORS_BITS;
 130         unsigned visited : 1;
 131 } ColorData;
 132
 133 // Represents one managed object. Equivalent of new/old bridge "HashEntry"
 134 typedef struct _ScanData {
 135         // FIXME this can be eliminated; if we have a ScanData we generally looked it up from its GCObject
 136         GCObject *obj;
 137         // We use the sgen lock_word in GCObject to store a pointer to the ScanData. Cache the original here to restore later:
 138         mword lock_word;
 139
 140         ColorData *color;
 141         // Tarjan algorithm index (order visited)
 142         int index;
 143         // Tarjan index of lowest-index object known reachable from here
 144         signed low_index : 27;
 145
 146         // See "ScanData state" enum above
 147         unsigned state : 2;
 148         unsigned is_bridge : 1;
 149         // Similar to lock_word, we use these bits in the GCObject as scratch space then restore them when done
 150         unsigned obj_state : 2;
 151 } ScanData;
 152
 153 /* Should color be made visible to client even though it has no bridges?
 154  * True if we predict the number of reduced edges to be enough to justify the extra node.
 155  */
 156 static inline gboolean
 157 bridgeless_color_is_heavy (ColorData *data) {
 158         int fanin = data->incoming_colors;
 159         int fanout = dyn_array_ptr_size (&data->other_colors);
 160         return fanin > HEAVY_REFS_MIN && fanout > HEAVY_REFS_MIN
 161                 && fanin*fanout >= HEAVY_COMBINED_REFS_MIN;
 162 }
 163
 164 // Should color be made visible to client?
 165 static inline gboolean
 166 color_visible_to_client (ColorData *data) {
 167         return dyn_array_ptr_size (&data->bridges) || bridgeless_color_is_heavy (data);
 168 }
 169
 170 // Stacks of ScanData objects used for tarjan algorithm.
 171 // The Tarjan algorithm is normally defined recursively; here scan_stack simulates the call stack of a recursive algorithm,
 172 // and loop_stack is the stack structure used by the algorithm itself.
 173 static DynPtrArray scan_stack, loop_stack;
 174
 175 // GCObjects on which register_finalized_object has been called
 176 static DynPtrArray registered_bridges;
 177
 178 // As we traverse the graph, which ColorData objects are accessible from our current position?
 179 static DynPtrArray color_merge_array;
 180 // Running hash of the contents of the color_merge_array.
 181 static unsigned int color_merge_array_hash;
 182
 183 static void color_merge_array_empty (void)
 184 {
 185         dyn_array_ptr_empty (&color_merge_array);
 186         color_merge_array_hash = 0;
 187 }
 188
 189 static int ignored_objects;
 190 static int object_index;
 191 static int num_colors_with_bridges;
 192 static int num_sccs;
 193 static int xref_count;
 194
 195 static size_t setup_time, tarjan_time, scc_setup_time, gather_xref_time, xref_setup_time, cleanup_time;
 196 static SgenBridgeProcessor *bridge_processor;
 197
 198 #define BUCKET_SIZE 8184
 199
 200 //ScanData buckets
 201 #define NUM_SCAN_ENTRIES ((BUCKET_SIZE - SIZEOF_VOID_P * 2) / sizeof (ScanData))
 202
 203 typedef struct _ObjectBucket ObjectBucket;
 204 struct _ObjectBucket {
 205         ObjectBucket *next;
 206         ScanData *next_data;
 207         ScanData data [NUM_SCAN_ENTRIES];
 208 };
 209
 210 static ObjectBucket *root_object_bucket;
 211 static ObjectBucket *cur_object_bucket;
 212 static int object_data_count;
 213
 214 // Arenas to allocate ScanData from
 215 static ObjectBucket*
 216 new_object_bucket (void)
 217 {
 218         ObjectBucket *res = (ObjectBucket *)sgen_alloc_internal (INTERNAL_MEM_TARJAN_OBJ_BUCKET);
 219         res->next_data = &res->data [0];
 220         return res;
 221 }
 222
 223 static void
 224 object_alloc_init (void)
 225 {
 226         root_object_bucket = cur_object_bucket = new_object_bucket ();
 227 }
 228
 229 static ScanData*
 230 alloc_object_data (void)
 231 {
 232         ScanData *res;
 233 retry:
 234
 235         /* next_data points to the first free entry */
 236         res = cur_object_bucket->next_data;
 237         if (res >= &cur_object_bucket->data [NUM_SCAN_ENTRIES]) {
 238                 ObjectBucket *b = new_object_bucket ();
 239                 cur_object_bucket->next = b;
 240                 cur_object_bucket = b;
 241                 goto retry;
 242         }
 243         cur_object_bucket->next_data = res + 1;
 244         object_data_count++;
 245         return res;
 246 }
 247
 248 static void
 249 free_object_buckets (void)
 250 {
 251         ObjectBucket *cur = root_object_bucket;
 252
 253         object_data_count = 0;
 254
 255         while (cur) {
 256                 ObjectBucket *tmp = cur->next;
 257                 sgen_free_internal (cur, INTERNAL_MEM_TARJAN_OBJ_BUCKET);
 258                 cur = tmp;
 259         }
 260
 261         root_object_bucket = cur_object_bucket = NULL;
 262 }
 263
 264 //ColorData buckets
 265 #define NUM_COLOR_ENTRIES ((BUCKET_SIZE - SIZEOF_VOID_P * 2) / sizeof (ColorData))
 266
 267 // Arenas for ColorDatas, same as ObjectBucket except items-per-bucket differs
 268 typedef struct _ColorBucket ColorBucket;
 269 struct _ColorBucket {
 270         ColorBucket *next;
 271         ColorData *next_data;
 272         ColorData data [NUM_COLOR_ENTRIES];
 273 };
 274
 275 static ColorBucket *root_color_bucket;
 276 static ColorBucket *cur_color_bucket;
 277 static int color_data_count;
 278
 279
 280 static ColorBucket*
 281 new_color_bucket (void)
 282 {
 283         ColorBucket *res = (ColorBucket *)sgen_alloc_internal (INTERNAL_MEM_TARJAN_OBJ_BUCKET);
 284         res->next_data = &res->data [0];
 285         return res;
 286 }
 287
 288 static void
 289 color_alloc_init (void)
 290 {
 291         root_color_bucket = cur_color_bucket = new_color_bucket ();
 292 }
 293
 294 static ColorData*
 295 alloc_color_data (void)
 296 {
 297         ColorData *res;
 298 retry:
 299
 300         /* next_data points to the first free entry */
 301         res = cur_color_bucket->next_data;
 302         if (res >= &cur_color_bucket->data [NUM_COLOR_ENTRIES]) {
 303                 ColorBucket *b = new_color_bucket ();
 304                 cur_color_bucket->next = b;
 305                 cur_color_bucket = b;
 306                 goto retry;
 307         }
 308         cur_color_bucket->next_data = res + 1;
 309         color_data_count++;
 310         return res;
 311 }
 312
 313 static void
 314 free_color_buckets (void)
 315 {
 316         ColorBucket *cur, *tmp;
 317
 318         color_data_count = 0;
 319
 320         for (cur = root_color_bucket; cur; cur = tmp) {
 321                 ColorData *cd;
 322                 for (cd = &cur->data [0]; cd < cur->next_data; ++cd) {
 323                         dyn_array_ptr_uninit (&cd->other_colors);
 324                         dyn_array_ptr_uninit (&cd->bridges);
 325                 }
 326                 tmp = cur->next;
 327                 sgen_free_internal (cur, INTERNAL_MEM_TARJAN_OBJ_BUCKET);
 328         }
 329         root_color_bucket = cur_color_bucket = NULL;
 330 }
 331
 332
 333 static ScanData*
 334 create_data (GCObject *obj)
 335 {
 336         mword *o = (mword*)obj;
 337         ScanData *res = alloc_object_data ();
 338         res->obj = obj;
 339         res->color = NULL;
 340         res->index = res->low_index = -1;
 341         res->state = INITIAL;
 342         res->is_bridge = FALSE;
 343         res->obj_state = o [0] & SGEN_VTABLE_BITS_MASK;
 344         res->lock_word = o [1];
 345
 346         o [0] |= SGEN_VTABLE_BITS_MASK;
 347         o [1] = (mword)res;
 348         return res;
 349 }
 350
 351 static ScanData*
 352 find_data (GCObject *obj)
 353 {
 354         ScanData *a = NULL;
 355         mword *o = (mword*)obj;
 356         if ((o [0] & SGEN_VTABLE_BITS_MASK) == SGEN_VTABLE_BITS_MASK)
 357                 a = (ScanData*)o [1];
 358         return a;
 359 }
 360
 361 static void
 362 clear_after_processing (void)
 363 {
 364         ObjectBucket *cur;
 365
 366         for (cur = root_object_bucket; cur; cur = cur->next) {
 367                 ScanData *sd;
 368                 for (sd = &cur->data [0]; sd < cur->next_data; ++sd) {
 369                         mword *o = (mword*)sd->obj;
 370                         o [0] &= ~SGEN_VTABLE_BITS_MASK;
 371                         o [0] |= sd->obj_state;
 372                         o [1] = sd->lock_word;
 373                 }
 374         }
 375 }
 376
 377 static GCObject*
 378 bridge_object_forward (GCObject *obj)
 379 {
 380         GCObject *fwd;
 381         mword *o = (mword*)obj;
 382         if ((o [0] & SGEN_VTABLE_BITS_MASK) == SGEN_VTABLE_BITS_MASK)
 383                 return obj;
 384
 385         fwd = SGEN_OBJECT_IS_FORWARDED (obj);
 386         return fwd ? fwd : obj;
 387 }
 388
 389 #ifdef DUMP_GRAPH
 390 static const char*
 391 safe_name_bridge (GCObject *obj)
 392 {
 393         GCVTable vt = SGEN_LOAD_VTABLE (obj);
 394         return vt->klass->name;
 395 }
 396
 397 static ScanData*
 398 find_or_create_data (GCObject *obj)
 399 {
 400         ScanData *entry = find_data (obj);
 401         if (!entry)
 402                 entry = create_data (obj);
 403         return entry;
 404 }
 405 #endif
 406
 407 //----------
 408 typedef struct {
 409         ColorData *color;
 410         unsigned int hash;
 411 } HashEntry;
 412
 413 /*
 414 The merge cache maps an ordered list of ColorDatas [the color_merge_array] to a single ColorData.
 415
 416 About cache bucket tuning: We tried 2/32, 2/128, 4/32, 4/128, 6/128 and 8/128.
 417
 418 The performance cost between 4/128 and 8/128 is so small since cache movement happens completely in the same cacheline,
 419 making the extra space pretty much free.
 420
 421 The cost between 32 and 128 itens is minimal too, it's mostly a fixed, setup cost.
 422
 423 Memory wise, 4/32 takes 512 and 8/128 takes 8k, so it's quite reasonable.
 424 */
 425
 426 #define ELEMENTS_PER_BUCKET 8
 427 #define COLOR_CACHE_SIZE 128
 428 static HashEntry merge_cache [COLOR_CACHE_SIZE][ELEMENTS_PER_BUCKET];
 429 static unsigned int hash_perturb;
 430
 431 // If true, disable an optimization where sometimes SCC nodes are merged without a perfect check
 432 static gboolean scc_precise_merge;
 433
 434 static unsigned int
 435 mix_hash (uintptr_t source)
 436 {
 437         unsigned int hash = source;
 438
 439         // The full hash determines whether two colors can be merged-- sometimes exclusively.
 440         // This value changes every GC, so XORing it in before performing the hash will make the
 441         // chance that two different colors will produce the same hash on successive GCs very low.
 442         hash = hash ^ hash_perturb;
 443
 444         // Actual hash
 445         hash = (((hash * 215497) >> 16) ^ ((hash * 1823231) + hash));
 446
 447         // Mix in highest bits on 64-bit systems only
 448         if (sizeof (source) > 4)
 449                 hash = hash ^ (source >> 32);
 450
 451         return hash;
 452 }
 453
 454 static void
 455 reset_cache (void)
 456 {
 457         memset (merge_cache, 0, sizeof (merge_cache));
 458
 459         // When using the precise merge debug option, we do not want the inconsistency caused by hash_perturb.
 460         if (!scc_precise_merge)
 461                 ++hash_perturb;
 462 }
 463
 464
 465 static gboolean
 466 dyn_array_ptr_contains (DynPtrArray *da, void *x)
 467 {
 468         int i;
 469         for (i = 0; i < dyn_array_ptr_size (da); ++i)
 470                 if (dyn_array_ptr_get (da, i) == x)
 471                         return TRUE;
 472         return FALSE;
 473 }
 474
 475 static gboolean
 476 match_colors_estimate (DynPtrArray *a, DynPtrArray *b)
 477 {
 478         return dyn_array_ptr_size (a) == dyn_array_ptr_size (b);
 479 }
 480
 481
 482 static gboolean
 483 match_colors (DynPtrArray *a, DynPtrArray *b)
 484 {
 485         int i;
 486         if (dyn_array_ptr_size (a) != dyn_array_ptr_size (b))
 487                 return FALSE;
 488
 489         for (i = 0; i < dyn_array_ptr_size (a); ++i) {
 490                 if (!dyn_array_ptr_contains (b, dyn_array_ptr_get (a, i)))
 491                         return FALSE;
 492         }
 493         return TRUE;
 494 }
 495
 496 // If scc_precise_merge, "semihits" refers to find_in_cache calls aborted because the merge array was too large.
 497 // Otherwise "semihits" refers to cache hits where the match was only estimated.
 498 static int cache_hits, cache_semihits, cache_misses;
 499
 500 // The cache contains only non-bridged colors.
 501 static ColorData*
 502 find_in_cache (int *insert_index)
 503 {
 504         HashEntry *bucket;
 505         int i, size, index;
 506
 507         size = dyn_array_ptr_size (&color_merge_array);
 508
 509         /* Color equality checking is very expensive with a lot of elements, so when there are many
 510          * elements we switch to a cheap comparison method which allows false positives. When false
 511          * positives occur the worst that can happen is two items will be inappropriately merged
 512          * and memory will be retained longer than it should be. We assume that will correct itself
 513          * on the next GC (the hash_perturb mechanism increases the probability of this).
 514          *
 515          * Because this has *some* potential to create problems, if the user set the debug option
 516          * 'enable-tarjan-precise-merge' we bail out early (and never merge SCCs with >3 colors).
 517          */
 518         gboolean color_merge_array_large = size > 3;
 519         if (scc_precise_merge && color_merge_array_large) {
 520                 ++cache_semihits;
 521                 return NULL;
 522         }
 523
 524         unsigned int hash = color_merge_array_hash;
 525         if (!hash) // 0 is used to indicate an empty bucket entry
 526                 hash = 1;
 527
 528         index = hash & (COLOR_CACHE_SIZE - 1);
 529         bucket = merge_cache [index];
 530         for (i = 0; i < ELEMENTS_PER_BUCKET; ++i) {
 531                 if (bucket [i].hash != hash)
 532                         continue;
 533
 534                 if (color_merge_array_large) {
 535                         if (match_colors_estimate (&bucket [i].color->other_colors, &color_merge_array)) {
 536                                 ++cache_semihits;
 537                                 return bucket [i].color;
 538                         }
 539                 } else {
 540                         if (match_colors (&bucket [i].color->other_colors, &color_merge_array)) {
 541                                 ++cache_hits;
 542                                 return bucket [i].color;
 543                         }
 544                 }
 545         }
 546
 547         //move elements to the back
 548         for (i = ELEMENTS_PER_BUCKET - 1; i > 0; --i)
 549                 bucket [i] = bucket [i - 1];
 550         ++cache_misses;
 551         *insert_index = index;
 552         bucket [0].hash = hash;
 553         return NULL;
 554 }
 555
 556 // A color is needed for an SCC. If the SCC has bridges, the color MUST be newly allocated.
 557 // If the SCC lacks bridges, the allocator MAY use the cache to merge it with an existing one.
 558 static ColorData*
 559 new_color (gboolean has_bridges)
 560 {
 561         int cacheSlot = -1;
 562         ColorData *cd;
 563         /* XXX Try to find an equal one and return it */
 564         if (!has_bridges) {
 565                 cd = find_in_cache (&cacheSlot);
 566                 if (cd)
 567                         return cd;
 568         }
 569
 570         cd = alloc_color_data ();
 571         cd->api_index = -1;
 572         dyn_array_ptr_set_all (&cd->other_colors, &color_merge_array);
 573
 574         // Inform targets
 575         for (int i = 0; i < dyn_array_ptr_size (&color_merge_array); ++i) {
 576                 ColorData *points_to = (ColorData *)dyn_array_ptr_get (&color_merge_array, i);
 577                 points_to->incoming_colors = MIN (points_to->incoming_colors + 1, INCOMING_COLORS_MAX);
 578         }
 579
 580         /* if cacheSlot >= 0, it means we prepared a given slot to receive the new color */
 581         if (cacheSlot >= 0)
 582                 merge_cache [cacheSlot][0].color = cd;
 583
 584         return cd;
 585 }
 586
 587
 588 static void
 589 register_bridge_object (GCObject *obj)
 590 {
 591         create_data (obj)->is_bridge = TRUE;
 592 }
 593
 594 static gboolean
 595 is_opaque_object (GCObject *obj)
 596 {
 597         MonoVTable *vt = 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 // Called during DFS; visits one child. If it is a candidate to be scanned, pushes it to the stacks.
 607 static void
 608 push_object (GCObject *obj)
 609 {
 610         ScanData *data;
 611         obj = bridge_object_forward (obj);
 612
 613 #if DUMP_GRAPH
 614         printf ("\t= pushing %p %s -> ", obj, safe_name_bridge (obj));
 615 #endif
 616
 617         /* Object types we can ignore */
 618         if (is_opaque_object (obj)) {
 619 #if DUMP_GRAPH
 620                 printf ("opaque\n");
 621 #endif
 622                 return;
 623         }
 624
 625         data = find_data (obj);
 626
 627         /* Already marked - XXX must be done this way as the bridge themselves are alive. */
 628         if (data && data->state != INITIAL) {
 629 #if DUMP_GRAPH
 630                 printf ("already marked\n");
 631 #endif
 632                 return;
 633         }
 634
 635         /* We only care about dead objects */
 636         if (!data && sgen_object_is_live (obj)) {
 637 #if DUMP_GRAPH
 638                 printf ("alive\n");
 639 #endif
 640                 return;
 641         }
 642
 643 #if DUMP_GRAPH
 644         printf ("pushed!\n");
 645 #endif
 646
 647         if (!data)
 648                 data = create_data (obj);
 649         g_assert (data->state == INITIAL);
 650         g_assert (data->index == -1);
 651         dyn_array_ptr_push (&scan_stack, data);
 652 }
 653
 654 #undef HANDLE_PTR
 655 #define HANDLE_PTR(ptr,obj)     do {                                    \
 656                 GCObject *dst = (GCObject*)*(ptr);                      \
 657                 if (dst) push_object (dst);                     \
 658         } while (0)
 659
 660 // dfs () function's queue-children-of-object operation.
 661 static void
 662 push_all (ScanData *data)
 663 {
 664         GCObject *obj = data->obj;
 665         char *start = (char*)obj;
 666         mword desc = sgen_obj_get_descriptor_safe (obj);
 667
 668 #if DUMP_GRAPH
 669         printf ("+scanning %s (%p) index %d color %p\n", safe_name_bridge (data->obj), data->obj, data->index, data->color);
 670 #endif
 671
 672         #include "sgen/sgen-scan-object.h"
 673 }
 674
 675
 676 static void
 677 compute_low_index (ScanData *data, GCObject *obj)
 678 {
 679         ScanData *other;
 680         ColorData *cd;
 681
 682         obj = bridge_object_forward (obj);
 683         other = find_data (obj);
 684
 685 #if DUMP_GRAPH
 686         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);
 687 #endif
 688         if (!other)
 689                 return;
 690
 691         g_assert (other->state != INITIAL);
 692
 693         if ((other->state == SCANNED || other->state == FINISHED_ON_STACK) && data->low_index > other->low_index)
 694                 data->low_index = other->low_index;
 695
 696         /* Compute the low color */
 697         if (other->color == NULL)
 698                 return;
 699
 700         cd = other->color;
 701         if (!cd->visited) {
 702                 color_merge_array_hash += mix_hash ((uintptr_t) other->color);
 703                 dyn_array_ptr_add (&color_merge_array, other->color);
 704                 cd->visited = TRUE;
 705         }
 706 }
 707
 708 #undef HANDLE_PTR
 709 #define HANDLE_PTR(ptr,obj)     do {                                    \
 710                 GCObject *dst = (GCObject*)*(ptr);                      \
 711                 if (dst) compute_low_index (data, dst);                         \
 712         } while (0)
 713
 714 static void
 715 compute_low (ScanData *data)
 716 {
 717         GCObject *obj = data->obj;
 718         char *start = (char*)obj;
 719         mword desc = sgen_obj_get_descriptor_safe (obj);
 720
 721         #include "sgen/sgen-scan-object.h"
 722 }
 723
 724 // A non-bridged object needs a single color describing the current merge array.
 725 static ColorData*
 726 reduce_color (void)
 727 {
 728         ColorData *color = NULL;
 729         int size = dyn_array_ptr_size (&color_merge_array);
 730
 731         // Merge array is empty-- this SCC points to no bridged colors.
 732         // This SCC can be ignored completely.
 733         if (size == 0)
 734                 color = NULL;
 735
 736         // Merge array has one item-- this SCC points to a single bridged color.
 737         // This SCC can be forwarded to the pointed-to color.
 738         else if (size == 1) {
 739                 color = (ColorData *)dyn_array_ptr_get (&color_merge_array, 0);
 740
 741         // This SCC gets to talk to the color allocator.
 742         } else
 743                 color = new_color (FALSE);
 744
 745         return color;
 746 }
 747
 748 static void
 749 create_scc (ScanData *data)
 750 {
 751         int i;
 752         gboolean found = FALSE;
 753         gboolean found_bridge = FALSE;
 754         ColorData *color_data = NULL;
 755
 756         for (i = dyn_array_ptr_size (&loop_stack) - 1; i >= 0; --i) {
 757                 ScanData *other = (ScanData *)dyn_array_ptr_get (&loop_stack, i);
 758                 found_bridge |= other->is_bridge;
 759                 if (found_bridge || other == data)
 760                         break;
 761         }
 762
 763 #if DUMP_GRAPH
 764         printf ("|SCC rooted in %s (%p) has bridge %d\n", safe_name_bridge (data->obj), data->obj, found_bridge);
 765         printf ("\tpoints-to-colors: ");
 766         for (int i = 0; i < dyn_array_ptr_size (&color_merge_array); ++i)
 767                 printf ("%p ", dyn_array_ptr_get (&color_merge_array, i));
 768         printf ("\n");
 769
 770         printf ("loop stack: ");
 771         for (int i = 0; i < dyn_array_ptr_size (&loop_stack); ++i) {
 772                 ScanData *other = dyn_array_ptr_get (&loop_stack, i);
 773                 printf ("(%d/%d)", other->index, other->low_index);
 774         }
 775         printf ("\n");
 776 #endif
 777
 778         if (found_bridge) {
 779                 color_data = new_color (TRUE);
 780                 ++num_colors_with_bridges;
 781         } else {
 782                 color_data = reduce_color ();
 783         }
 784
 785         while (dyn_array_ptr_size (&loop_stack) > 0) {
 786                 ScanData *other = (ScanData *)dyn_array_ptr_pop (&loop_stack);
 787
 788 #if DUMP_GRAPH
 789                 printf ("\tmember %s (%p) index %d low-index %d color %p state %d\n", safe_name_bridge (other->obj), other->obj, other->index, other->low_index, other->color, other->state);
 790 #endif
 791
 792                 other->color = color_data;
 793                 switch (other->state) {
 794                 case FINISHED_ON_STACK:
 795                         other->state = FINISHED_OFF_STACK;
 796                         break;
 797                 case FINISHED_OFF_STACK:
 798                         break;
 799                 default:
 800                         g_error ("Invalid state when building SCC %d", other->state);
 801                 }
 802
 803                 if (other->is_bridge)
 804                         dyn_array_ptr_add (&color_data->bridges, other->obj);
 805
 806                 if (other == data) {
 807                         found = TRUE;
 808                         break;
 809                 }
 810         }
 811         g_assert (found);
 812
 813         for (i = 0; i < dyn_array_ptr_size (&color_merge_array); ++i) {
 814                 ColorData *cd  = (ColorData *)dyn_array_ptr_get (&color_merge_array, i);
 815                 g_assert (cd->visited);
 816                 cd->visited = FALSE;
 817         }
 818         color_merge_array_empty ();
 819         found_bridge = FALSE;
 820 }
 821
 822 static void
 823 dfs (void)
 824 {
 825         g_assert (dyn_array_ptr_size (&scan_stack) == 1);
 826         g_assert (dyn_array_ptr_size (&loop_stack) == 0);
 827
 828         color_merge_array_empty ();
 829
 830         while (dyn_array_ptr_size (&scan_stack) > 0) {
 831                 ScanData *data = (ScanData *)dyn_array_ptr_pop (&scan_stack);
 832
 833                 /**
 834                  * Ignore finished objects on stack, they happen due to loops. For example:
 835                  * A -> C
 836                  * A -> B
 837                  * B -> C
 838                  * C -> A
 839                  *
 840                  * We start scanning from A and push C before B. So, after the first iteration, the scan stack will have: A C B.
 841                  * We then visit B, which will find C in its initial state and push again.
 842                  * Finally after finish with C and B, the stack will be left with "A C" and at this point C should be ignored.
 843          *
 844          * The above explains FINISHED_ON_STACK, to explain FINISHED_OFF_STACK, consider if the root was D, which pointed
 845                  * to A and C. A is processed first, leaving C on stack after that in the mentioned state.
 846                  */
 847                 if (data->state == FINISHED_ON_STACK || data->state == FINISHED_OFF_STACK)
 848                         continue;
 849
 850                 if (data->state == INITIAL) {
 851                         g_assert (data->index == -1);
 852                         g_assert (data->low_index == -1);
 853
 854                         data->state = SCANNED;
 855                         data->low_index = data->index = object_index++;
 856                         dyn_array_ptr_push (&scan_stack, data);
 857                         dyn_array_ptr_push (&loop_stack, data);
 858
 859 #if DUMP_GRAPH
 860                         printf ("+scanning %s (%p) index %d color %p\n", safe_name_bridge (data->obj), data->obj, data->index, data->color);
 861 #endif
 862                         /*push all refs */
 863                         push_all (data);
 864                 } else {
 865                         g_assert (data->state == SCANNED);
 866                         data->state = FINISHED_ON_STACK;
 867
 868 #if DUMP_GRAPH
 869                         printf ("-finishing %s (%p) index %d low-index %d color %p\n", safe_name_bridge (data->obj), data->obj, data->index, data->low_index, data->color);
 870 #endif
 871
 872                         /* Compute low index */
 873                         compute_low (data);
 874
 875 #if DUMP_GRAPH
 876                         printf ("-finished %s (%p) index %d low-index %d color %p\n", safe_name_bridge (data->obj), data->obj, data->index, data->low_index, data->color);
 877 #endif
 878                         //SCC root
 879                         if (data->index == data->low_index)
 880                                 create_scc (data);
 881                 }
 882         }
 883 }
 884
 885 static void
 886 register_finalized_object (GCObject *obj)
 887 {
 888         g_assert (sgen_need_bridge_processing ());
 889         dyn_array_ptr_push (&registered_bridges, obj);
 890 }
 891
 892 static void
 893 reset_data (void)
 894 {
 895         dyn_array_ptr_empty (&registered_bridges);
 896 }
 897
 898 static void
 899 cleanup (void)
 900 {
 901         dyn_array_ptr_empty (&scan_stack);
 902         dyn_array_ptr_empty (&loop_stack);
 903         dyn_array_ptr_empty (&registered_bridges);
 904         free_object_buckets ();
 905         free_color_buckets ();
 906         reset_cache ();
 907         object_index = 0;
 908         num_colors_with_bridges = 0;
 909 }
 910
 911 #ifdef DUMP_GRAPH
 912 static void
 913 dump_color_table (const char *why, gboolean do_index)
 914 {
 915         ColorBucket *cur;
 916         int i = 0, j;
 917         printf ("colors%s:\n", why);
 918
 919         for (cur = root_color_bucket; cur; cur = cur->next, ++i) {
 920                 ColorData *cd;
 921                 for (cd = &cur->data [0]; cd < cur->next_data; ++cd) {
 922                         if (do_index)
 923                                 printf ("\t%d(%d):", i, cd->api_index);
 924                         else
 925                                 printf ("\t%d: ", i);
 926                         for (j = 0; j < dyn_array_ptr_size (&cd->other_colors); ++j) {
 927                                 printf ("%p ", dyn_array_ptr_get (&cd->other_colors, j));
 928                         }
 929                         if (dyn_array_ptr_size (&cd->bridges)) {
 930                                 printf (" bridges: ");
 931                                 for (j = 0; j < dyn_array_ptr_size (&cd->bridges); ++j) {
 932                                         GCObject *obj = dyn_array_ptr_get (&cd->bridges, j);
 933                                         ScanData *data = find_or_create_data (obj);
 934                                         printf ("%d ", data->index);
 935                                 }
 936                         }
 937                         printf ("\n");
 938                 }
 939         }
 940
 941 }
 942 #endif
 943
 944 static gint64
 945 step_timer (gint64 *timer)
 946 {
 947         gint64 curtime, diff;
 948
 949         SGEN_TV_GETTIME (curtime);
 950         diff = SGEN_TV_ELAPSED (*timer, curtime);
 951         *timer = curtime;
 952         return diff;
 953 }
 954 static void
 955 processing_stw_step (void)
 956 {
 957         int i;
 958         int bridge_count;
 959         gint64 curtime;
 960
 961         if (!dyn_array_ptr_size (&registered_bridges))
 962                 return;
 963
 964 #if defined (DUMP_GRAPH)
 965         printf ("-----------------\n");
 966 #endif
 967
 968         SGEN_TV_GETTIME (curtime);
 969
 970         object_alloc_init ();
 971         color_alloc_init ();
 972
 973         bridge_count = dyn_array_ptr_size (&registered_bridges);
 974         for (i = 0; i < bridge_count ; ++i)
 975                 register_bridge_object ((GCObject *)dyn_array_ptr_get (&registered_bridges, i));
 976
 977         setup_time = step_timer (&curtime);
 978
 979         for (i = 0; i < bridge_count; ++i) {
 980                 ScanData *sd = find_data ((GCObject *)dyn_array_ptr_get (&registered_bridges, i));
 981                 if (sd->state == INITIAL) {
 982                         dyn_array_ptr_push (&scan_stack, sd);
 983                         dfs ();
 984                 } else {
 985                         g_assert (sd->state == FINISHED_OFF_STACK);
 986                 }
 987         }
 988
 989         tarjan_time = step_timer (&curtime);
 990
 991 #if defined (DUMP_GRAPH)
 992         printf ("----summary----\n");
 993         printf ("bridges:\n");
 994         for (int i = 0; i < bridge_count; ++i) {
 995                 ScanData *sd = find_data (dyn_array_ptr_get (&registered_bridges, i));
 996                 printf ("\t%s (%p) index %d color %p\n", safe_name_bridge (sd->obj), sd->obj, sd->index, sd->color);
 997         }
 998
 999         dump_color_table (" after tarjan", FALSE);
1000 #endif
1001
1002         clear_after_processing ();
1003 }
1004
1005
1006 static void
1007 gather_xrefs (ColorData *color)
1008 {
1009         int i;
1010         for (i = 0; i < dyn_array_ptr_size (&color->other_colors); ++i) {
1011                 ColorData *src = (ColorData *)dyn_array_ptr_get (&color->other_colors, i);
1012                 if (src->visited)
1013                         continue;
1014                 src->visited = TRUE;
1015                 if (color_visible_to_client (src))
1016                         dyn_array_ptr_add (&color_merge_array, src);
1017                 else
1018                         gather_xrefs (src);
1019         }
1020 }
1021
1022 static void
1023 reset_xrefs (ColorData *color)
1024 {
1025         int i;
1026         for (i = 0; i < dyn_array_ptr_size (&color->other_colors); ++i) {
1027                 ColorData *src = (ColorData *)dyn_array_ptr_get (&color->other_colors, i);
1028                 if (!src->visited)
1029                         continue;
1030                 src->visited = FALSE;
1031                 if (!color_visible_to_client (src))
1032                         reset_xrefs (src);
1033         }
1034 }
1035
1036 static void
1037 processing_build_callback_data (int generation)
1038 {
1039         int j;
1040         gint64 curtime;
1041         ColorBucket *cur;
1042
1043         g_assert (bridge_processor->num_sccs == 0 && bridge_processor->num_xrefs == 0);
1044         g_assert (!bridge_processor->api_sccs && !bridge_processor->api_xrefs);
1045
1046         if (!dyn_array_ptr_size (&registered_bridges))
1047                 return;
1048
1049         SGEN_TV_GETTIME (curtime);
1050
1051         /*create API objects */
1052
1053 #if defined (DUMP_GRAPH)
1054         printf ("***** API *****\n");
1055         printf ("number of SCCs %d\n", num_colors_with_bridges);
1056 #endif
1057
1058         // Count the number of SCCs visible to the client
1059         num_sccs = 0;
1060         for (cur = root_color_bucket; cur; cur = cur->next) {
1061                 ColorData *cd;
1062                 for (cd = &cur->data [0]; cd < cur->next_data; ++cd) {
1063                         if (color_visible_to_client (cd))
1064                                 num_sccs++;
1065                 }
1066         }
1067
1068         /* This is a straightforward translation from colors to the bridge callback format. */
1069         MonoGCBridgeSCC **api_sccs = (MonoGCBridgeSCC **)sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC*) * num_sccs, INTERNAL_MEM_BRIDGE_DATA, TRUE);
1070         int api_index = 0;
1071         xref_count = 0;
1072
1073         // Convert visible SCCs, along with their bridged object list, to MonoGCBridgeSCCs in the client's SCC list
1074         for (cur = root_color_bucket; cur; cur = cur->next) {
1075                 ColorData *cd;
1076                 for (cd = &cur->data [0]; cd < cur->next_data; ++cd) {
1077                         int bridges = dyn_array_ptr_size (&cd->bridges);
1078                         if (!(bridges || bridgeless_color_is_heavy (cd)))
1079                                 continue;
1080
1081                         api_sccs [api_index] = (MonoGCBridgeSCC *)sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC) + sizeof (MonoObject*) * bridges, INTERNAL_MEM_BRIDGE_DATA, TRUE);
1082                         api_sccs [api_index]->is_alive = FALSE;
1083                         api_sccs [api_index]->num_objs = bridges;
1084
1085                         cd->api_index = api_index;
1086
1087                         for (j = 0; j < bridges; ++j)
1088                                 api_sccs [api_index]->objs [j] = (MonoObject *)dyn_array_ptr_get (&cd->bridges, j);
1089
1090                         g_assert(api_index < API_INDEX_MAX);
1091                         api_index++;
1092                 }
1093         }
1094
1095         scc_setup_time = step_timer (&curtime);
1096
1097         // Eliminate non-visible SCCs from the SCC list and redistribute xrefs
1098         for (cur = root_color_bucket; cur; cur = cur->next) {
1099                 ColorData *cd;
1100                 for (cd = &cur->data [0]; cd < cur->next_data; ++cd) {
1101                         if (!color_visible_to_client (cd))
1102                                 continue;
1103
1104                         color_merge_array_empty ();
1105                         gather_xrefs (cd);
1106                         reset_xrefs (cd);
1107                         dyn_array_ptr_set_all (&cd->other_colors, &color_merge_array);
1108                         xref_count += dyn_array_ptr_size (&cd->other_colors);
1109                 }
1110         }
1111
1112         gather_xref_time = step_timer (&curtime);
1113
1114 #if defined (DUMP_GRAPH)
1115         printf ("TOTAL XREFS %d\n", xref_count);
1116         dump_color_table (" after xref pass", TRUE);
1117 #endif
1118
1119         // Write out xrefs array
1120         MonoGCBridgeXRef *api_xrefs = (MonoGCBridgeXRef *)sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeXRef) * xref_count, INTERNAL_MEM_BRIDGE_DATA, TRUE);
1121         int xref_index = 0;
1122         for (cur = root_color_bucket; cur; cur = cur->next) {
1123                 ColorData *src;
1124                 for (src = &cur->data [0]; src < cur->next_data; ++src) {
1125                         if (!color_visible_to_client (src))
1126                                 continue;
1127
1128                         for (j = 0; j < dyn_array_ptr_size (&src->other_colors); ++j) {
1129                                 ColorData *dest = (ColorData *)dyn_array_ptr_get (&src->other_colors, j);
1130                                 g_assert (color_visible_to_client (dest)); /* Supposedly we already eliminated all xrefs to non-visible objects. */
1131
1132                                 api_xrefs [xref_index].src_scc_index = src->api_index;
1133                                 api_xrefs [xref_index].dst_scc_index = dest->api_index;
1134
1135                                 ++xref_index;
1136                         }
1137                 }
1138         }
1139
1140         g_assert (xref_count == xref_index);
1141         xref_setup_time = step_timer (&curtime);
1142
1143 #if defined (DUMP_GRAPH)
1144         printf ("---xrefs:\n");
1145         for (int i = 0; i < xref_count; ++i)
1146                 printf ("\t%d -> %d\n", api_xrefs [i].src_scc_index, api_xrefs [i].dst_scc_index);
1147 #endif
1148
1149         //FIXME move half of the cleanup to before the bridge callback?
1150         bridge_processor->num_sccs = num_sccs;
1151         bridge_processor->api_sccs = api_sccs;
1152         bridge_processor->num_xrefs = xref_count;
1153         bridge_processor->api_xrefs = api_xrefs;
1154 }
1155
1156 static void
1157 processing_after_callback (int generation)
1158 {
1159         gint64 curtime;
1160         int bridge_count = dyn_array_ptr_size (&registered_bridges);
1161         int object_count = object_data_count;
1162         int color_count = color_data_count;
1163         int colors_with_bridges_count = num_colors_with_bridges;
1164
1165         SGEN_TV_GETTIME (curtime);
1166
1167         /* cleanup */
1168         cleanup ();
1169
1170         cleanup_time = step_timer (&curtime);
1171
1172         mono_trace (G_LOG_LEVEL_INFO, MONO_TRACE_GC, "GC_TAR_BRIDGE bridges %d objects %d opaque %d colors %d colors-bridged %d colors-visible %d xref %d cache-hit %d cache-%s %d cache-miss %d setup %.2fms tarjan %.2fms scc-setup %.2fms gather-xref %.2fms xref-setup %.2fms cleanup %.2fms",
1173                 bridge_count, object_count, ignored_objects,
1174                 color_count, colors_with_bridges_count, num_sccs, xref_count,
1175                 cache_hits, (scc_precise_merge ? "abstain" : "semihit"), cache_semihits, cache_misses,
1176                 setup_time / 10000.0f,
1177                 tarjan_time / 10000.0f,
1178                 scc_setup_time / 10000.0f,
1179                 gather_xref_time / 10000.0f,
1180                 xref_setup_time / 10000.0f,
1181                 cleanup_time / 10000.0f);
1182
1183         cache_hits = cache_semihits = cache_misses = 0;
1184         ignored_objects = 0;
1185 }
1186
1187 static void
1188 describe_pointer (GCObject *obj)
1189 {
1190         // HashEntry *entry;
1191         int i;
1192
1193         for (i = 0; i < dyn_array_ptr_size (&registered_bridges); ++i) {
1194                 if (obj == dyn_array_ptr_get (&registered_bridges, i)) {
1195                         printf ("Pointer is a registered bridge object.\n");
1196                         break;
1197                 }
1198         }
1199
1200         // entry = sgen_hash_table_lookup (&hash_table, obj);
1201         // if (!entry)
1202         //      return;
1203         //
1204         // printf ("Bridge hash table entry %p:\n", entry);
1205         // printf ("  is bridge: %d\n", (int)entry->is_bridge);
1206         // printf ("  is visited: %d\n", (int)entry->is_visited);
1207 }
1208
1209 static void
1210 set_config (const SgenBridgeProcessorConfig *config)
1211 {
1212         if (config->scc_precise_merge) {
1213                 hash_perturb = 0;
1214                 scc_precise_merge = TRUE;
1215         }
1216 }
1217
1218 void
1219 sgen_tarjan_bridge_init (SgenBridgeProcessor *collector)
1220 {
1221         collector->reset_data = reset_data;
1222         collector->processing_stw_step = processing_stw_step;
1223         collector->processing_build_callback_data = processing_build_callback_data;
1224         collector->processing_after_callback = processing_after_callback;
1225         collector->class_kind = class_kind;
1226         collector->register_finalized_object = register_finalized_object;
1227         collector->describe_pointer = describe_pointer;
1228         collector->set_config = set_config;
1229
1230         sgen_register_fixed_internal_mem_type (INTERNAL_MEM_TARJAN_OBJ_BUCKET, BUCKET_SIZE);
1231         g_assert (sizeof (ObjectBucket) <= BUCKET_SIZE);
1232         g_assert (sizeof (ColorBucket) <= BUCKET_SIZE);
1233         g_assert (API_INDEX_BITS + INCOMING_COLORS_BITS <= 31);
1234         bridge_processor = collector;
1235 }
1236
1237 #endif