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