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