2 * sgen-tarjan-bridge.c: Tarjan-based bridge implementation.
4 * Copyright 2011 Novell, Inc (http://www.novell.com)
5 * Copyright 2014 Xamarin Inc (http://www.xamarin.com)
7 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
8 * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
10 * Permission is hereby granted to use or copy this program
11 * for any purpose, provided the above notices are retained on all copies.
12 * Permission to modify the code and to distribute modified code is granted,
13 * provided the above notices are retained, and a notice that the code was
14 * modified is included with the above copyright notice.
17 * Copyright 2001-2003 Ximian, Inc
18 * Copyright 2003-2010 Novell, Inc.
20 * Permission is hereby granted, free of charge, to any person obtaining
21 * a copy of this software and associated documentation files (the
22 * "Software"), to deal in the Software without restriction, including
23 * without limitation the rights to use, copy, modify, merge, publish,
24 * distribute, sublicense, and/or sell copies of the Software, and to
25 * permit persons to whom the Software is furnished to do so, subject to
26 * the following conditions:
28 * The above copyright notice and this permission notice shall be
29 * included in all copies or substantial portions of the Software.
31 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
32 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
33 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
34 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
35 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
36 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
37 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
46 #include "sgen/sgen-gc.h"
47 #include "sgen-bridge-internals.h"
48 #include "sgen/sgen-hash-table.h"
49 #include "sgen/sgen-qsort.h"
50 #include "tabledefs.h"
51 #include "utils/mono-logger-internals.h"
68 dyn_array_uninit (DynArray *da, int elem_size)
70 if (da->capacity <= 0)
73 sgen_free_internal_dynamic (da->data, elem_size * da->capacity, INTERNAL_MEM_BRIDGE_DATA);
78 dyn_array_ensure_capacity (DynArray *da, int capacity, int elem_size)
80 int old_capacity = da->capacity;
83 if (capacity <= old_capacity)
86 if (da->capacity == 0)
88 while (capacity > da->capacity)
91 new_data = sgen_alloc_internal_dynamic (elem_size * da->capacity, INTERNAL_MEM_BRIDGE_DATA, TRUE);
93 memcpy (new_data, da->data, elem_size * da->size);
94 sgen_free_internal_dynamic (da->data, elem_size * old_capacity, INTERNAL_MEM_BRIDGE_DATA);
100 dyn_array_add (DynArray *da, int elem_size)
104 dyn_array_ensure_capacity (da, da->size + 1, elem_size);
106 p = da->data + da->size * elem_size;
114 dyn_array_ptr_uninit (DynPtrArray *da)
116 dyn_array_uninit (&da->array, sizeof (void*));
120 dyn_array_ptr_size (DynPtrArray *da)
122 return da->array.size;
126 dyn_array_ptr_set_size (DynPtrArray *da, int size)
128 da->array.size = size;
132 dyn_array_ptr_get (DynPtrArray *da, int x)
134 return ((void**)da->array.data)[x];
138 dyn_array_ptr_add (DynPtrArray *da, void *ptr)
140 void **p = dyn_array_add (&da->array, sizeof (void*));
144 #define dyn_array_ptr_push dyn_array_ptr_add
147 dyn_array_ptr_pop (DynPtrArray *da)
150 int size = da->array.size;
152 p = dyn_array_ptr_get (da, size - 1);
158 dyn_array_ptr_ensure_capacity (DynPtrArray *da, int capacity)
160 dyn_array_ensure_capacity (&da->array, capacity, sizeof (void*));
165 dyn_array_ptr_set_all (DynPtrArray *dst, DynPtrArray *src)
167 if (src->array.size > 0) {
168 dyn_array_ptr_ensure_capacity (dst, src->array.size);
169 memcpy (dst->array.data, src->array.data, src->array.size * sizeof (void*));
171 dst->array.size = src->array.size;
175 enable_accounting (void)
177 // bridge_accounting_enabled = TRUE;
178 // 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);
181 static MonoGCBridgeObjectKind
182 class_kind (MonoClass *klass)
184 MonoGCBridgeObjectKind res = bridge_callbacks.bridge_class_kind (klass);
186 /* If it's a bridge, nothing we can do about it. */
187 if (res == GC_BRIDGE_TRANSPARENT_BRIDGE_CLASS || res == GC_BRIDGE_OPAQUE_BRIDGE_CLASS)
190 /* Non bridge classes with no pointers will never point to a bridge, so we can savely ignore them. */
191 if (!klass->has_references) {
192 SGEN_LOG (6, "class %s is opaque\n", klass->name);
193 return GC_BRIDGE_OPAQUE_CLASS;
196 /* Some arrays can be ignored */
197 if (klass->rank == 1) {
198 MonoClass *elem_class = klass->element_class;
200 /* FIXME the bridge check can be quite expensive, cache it at the class level. */
201 /* An array of a sealed type that is not a bridge will never get to a bridge */
202 if ((elem_class->flags & TYPE_ATTRIBUTE_SEALED) && !elem_class->has_references && !bridge_callbacks.bridge_class_kind (elem_class)) {
203 SGEN_LOG (6, "class %s is opaque\n", klass->name);
204 return GC_BRIDGE_OPAQUE_CLASS;
208 return GC_BRIDGE_TRANSPARENT_CLASS;
211 //enable unsage logging
212 // #define DUMP_GRAPH 1
223 We can split this data structure in two, those with bridges and those without
226 DynPtrArray other_colors;
229 unsigned visited : 1;
234 GCObject *obj; //XXX this can be eliminated.
242 unsigned is_bridge : 1;
243 unsigned obj_state : 2;
249 static DynPtrArray scan_stack, loop_stack, registered_bridges;
250 static DynPtrArray color_merge_array;
252 static int ignored_objects;
253 static int object_index;
254 static int num_colors_with_bridges;
255 static int xref_count;
257 static size_t setup_time, tarjan_time, scc_setup_time, gather_xref_time, xref_setup_time, cleanup_time;
258 static SgenBridgeProcessor *bridge_processor;
260 #define BUCKET_SIZE 8184
263 #define NUM_SCAN_ENTRIES ((BUCKET_SIZE - SIZEOF_VOID_P * 2) / sizeof (ScanData))
265 typedef struct _ObjectBucket ObjectBucket;
266 struct _ObjectBucket {
269 ScanData data [NUM_SCAN_ENTRIES];
272 static ObjectBucket *root_object_bucket;
273 static ObjectBucket *cur_object_bucket;
274 static int object_data_count;
277 new_object_bucket (void)
279 ObjectBucket *res = sgen_alloc_internal (INTERNAL_MEM_TARJAN_OBJ_BUCKET);
280 res->next_data = &res->data [0];
285 object_alloc_init (void)
287 root_object_bucket = cur_object_bucket = new_object_bucket ();
291 alloc_object_data (void)
296 /* next_data points to the first free entry */
297 res = cur_object_bucket->next_data;
298 if (res >= &cur_object_bucket->data [NUM_SCAN_ENTRIES]) {
299 ObjectBucket *b = new_object_bucket ();
300 cur_object_bucket->next = b;
301 cur_object_bucket = b;
304 cur_object_bucket->next_data = res + 1;
310 free_object_buckets (void)
312 ObjectBucket *cur = root_object_bucket;
314 object_data_count = 0;
317 ObjectBucket *tmp = cur->next;
318 sgen_free_internal (cur, INTERNAL_MEM_TARJAN_OBJ_BUCKET);
322 root_object_bucket = cur_object_bucket = NULL;
326 #define NUM_COLOR_ENTRIES ((BUCKET_SIZE - SIZEOF_VOID_P * 2) / sizeof (ColorData))
328 typedef struct _ColorBucket ColorBucket;
329 struct _ColorBucket {
331 ColorData *next_data;
332 ColorData data [NUM_COLOR_ENTRIES];
335 static ColorBucket *root_color_bucket;
336 static ColorBucket *cur_color_bucket;
337 static int color_data_count;
341 new_color_bucket (void)
343 ColorBucket *res = sgen_alloc_internal (INTERNAL_MEM_TARJAN_OBJ_BUCKET);
344 res->next_data = &res->data [0];
349 color_alloc_init (void)
351 root_color_bucket = cur_color_bucket = new_color_bucket ();
355 alloc_color_data (void)
360 /* next_data points to the first free entry */
361 res = cur_color_bucket->next_data;
362 if (res >= &cur_color_bucket->data [NUM_COLOR_ENTRIES]) {
363 ColorBucket *b = new_color_bucket ();
364 cur_color_bucket->next = b;
365 cur_color_bucket = b;
368 cur_color_bucket->next_data = res + 1;
374 free_color_buckets (void)
376 ColorBucket *cur, *tmp;
378 color_data_count = 0;
380 for (cur = root_color_bucket; cur; cur = tmp) {
382 for (cd = &cur->data [0]; cd < cur->next_data; ++cd) {
383 dyn_array_ptr_uninit (&cd->other_colors);
384 dyn_array_ptr_uninit (&cd->bridges);
387 sgen_free_internal (cur, INTERNAL_MEM_TARJAN_OBJ_BUCKET);
389 root_color_bucket = cur_color_bucket = NULL;
394 create_data (GCObject *obj)
396 mword *o = (mword*)obj;
397 ScanData *res = alloc_object_data ();
400 res->index = res->low_index = -1;
401 res->obj_state = o [0] & SGEN_VTABLE_BITS_MASK;
402 res->lock_word = o [1];
404 o [0] |= SGEN_VTABLE_BITS_MASK;
410 find_data (GCObject *obj)
413 mword *o = (mword*)obj;
414 if ((o [0] & SGEN_VTABLE_BITS_MASK) == SGEN_VTABLE_BITS_MASK)
415 a = (ScanData*)o [1];
420 clear_after_processing (void)
424 for (cur = root_object_bucket; cur; cur = cur->next) {
426 for (sd = &cur->data [0]; sd < cur->next_data; ++sd) {
427 mword *o = (mword*)sd->obj;
428 o [0] &= ~SGEN_VTABLE_BITS_MASK;
429 o [0] |= sd->obj_state;
430 o [1] = sd->lock_word;
436 bridge_object_forward (GCObject *obj)
439 mword *o = (mword*)obj;
440 if ((o [0] & SGEN_VTABLE_BITS_MASK) == SGEN_VTABLE_BITS_MASK)
443 fwd = SGEN_OBJECT_IS_FORWARDED (obj);
444 return fwd ? fwd : obj;
449 safe_name_bridge (GCObject *obj)
451 GCVTable vt = SGEN_LOAD_VTABLE (obj);
452 return vt->klass->name;
456 find_or_create_data (GCObject *obj)
458 ScanData *entry = find_data (obj);
460 entry = create_data (obj);
472 We tried 2/32, 2/128, 4/32, 4/128, 6/128 and 8/128.
474 The performance cost between 4/128 and 8/128 is so small since cache movement happens completely in the same cacheline,
475 making the extra space pretty much free.
477 The cost between 32 and 128 itens is minimal too, it's mostly a fixed, setup cost.
479 Memory wise, 4/32 takes 512 and 8/128 takes 8k, so it's quite reasonable.
482 #define ELEMENTS_PER_BUCKET 8
483 #define COLOR_CACHE_SIZE 128
484 static HashEntry merge_cache [COLOR_CACHE_SIZE][ELEMENTS_PER_BUCKET];
487 mix_hash (size_t hash)
489 return (int)(((hash * 215497) >> 16) ^ ((hash * 1823231) + hash));
495 memset (merge_cache, 0, sizeof (merge_cache));
500 dyn_array_ptr_contains (DynPtrArray *da, void *x)
503 for (i = 0; i < dyn_array_ptr_size (da); ++i)
504 if (dyn_array_ptr_get (da, i) == x)
510 match_colors (DynPtrArray *a, DynPtrArray *b)
513 if (dyn_array_ptr_size (a) != dyn_array_ptr_size (b))
516 for (i = 0; i < dyn_array_ptr_size (a); ++i) {
517 if (!dyn_array_ptr_contains (b, dyn_array_ptr_get (a, i)))
523 static int cache_hits, cache_misses;
526 find_in_cache (int *insert_index)
529 int i, hash, size, index;
531 size = dyn_array_ptr_size (&color_merge_array);
532 /* Cache checking is very ineficient with a lot of elements*/
537 for (i = 0 ; i < size; ++i)
538 hash += mix_hash ((size_t)dyn_array_ptr_get (&color_merge_array, i));
542 index = hash & (COLOR_CACHE_SIZE - 1);
543 bucket = merge_cache [index];
544 for (i = 0; i < ELEMENTS_PER_BUCKET; ++i) {
545 if (bucket [i].hash != hash)
547 if (match_colors (&bucket [i].color->other_colors, &color_merge_array)) {
549 return bucket [i].color;
553 //move elements to the back
554 for (i = ELEMENTS_PER_BUCKET - 1; i > 0; --i)
555 bucket [i] = bucket [i - 1];
557 *insert_index = index;
558 bucket [0].hash = hash;
563 new_color (gboolean force_new)
567 /* XXX Try to find an equal one and return it */
569 cd = find_in_cache (&i);
574 cd = alloc_color_data ();
576 dyn_array_ptr_set_all (&cd->other_colors, &color_merge_array);
577 /* if i >= 0, it means we prepared a given slot to receive the new color */
579 merge_cache [i][0].color = cd;
586 register_bridge_object (GCObject *obj)
588 create_data (obj)->is_bridge = TRUE;
592 is_opaque_object (GCObject *obj)
594 MonoVTable *vt = SGEN_LOAD_VTABLE (obj);
595 if ((vt->gc_bits & SGEN_GC_BIT_BRIDGE_OPAQUE_OBJECT) == SGEN_GC_BIT_BRIDGE_OPAQUE_OBJECT) {
596 SGEN_LOG (6, "ignoring %s\n", vt->klass->name);
604 push_object (GCObject *obj)
607 obj = bridge_object_forward (obj);
610 printf ("\t= pushing %p %s -> ", obj, safe_name_bridge (obj));
613 /* Object types we can ignore */
614 if (is_opaque_object (obj)) {
621 data = find_data (obj);
623 /* Already marked - XXX must be done this way as the bridge themselves are alive. */
624 if (data && data->state != INITIAL) {
626 printf ("already marked\n");
631 /* We only care about dead objects */
632 if (!data && sgen_object_is_live (obj)) {
640 printf ("pushed!\n");
644 data = create_data (obj);
645 g_assert (data->state == INITIAL);
646 g_assert (data->index == -1);
647 dyn_array_ptr_push (&scan_stack, data);
651 #define HANDLE_PTR(ptr,obj) do { \
652 GCObject *dst = (GCObject*)*(ptr); \
653 if (dst) push_object (dst); \
657 push_all (ScanData *data)
659 GCObject *obj = data->obj;
660 char *start = (char*)obj;
661 mword desc = sgen_obj_get_descriptor_safe (obj);
664 printf ("**scanning %p %s\n", obj, safe_name_bridge (obj));
667 #include "sgen/sgen-scan-object.h"
672 compute_low_index (ScanData *data, GCObject *obj)
676 obj = bridge_object_forward (obj);
678 other = find_data (obj);
681 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 g_assert (other->state != INITIAL);
688 if ((other->state == SCANNED || other->state == FINISHED_ON_STACK) && data->low_index > other->low_index)
689 data->low_index = other->low_index;
691 /* Compute the low color */
692 if (other->color == NULL)
697 dyn_array_ptr_add (&color_merge_array, other->color);
703 #define HANDLE_PTR(ptr,obj) do { \
704 GCObject *dst = (GCObject*)*(ptr); \
705 if (dst) compute_low_index (data, dst); \
709 compute_low (ScanData *data)
711 GCObject *obj = data->obj;
712 char *start = (char*)obj;
713 mword desc = sgen_obj_get_descriptor_safe (obj);
715 #include "sgen/sgen-scan-object.h"
721 ColorData *color = NULL;
722 int size = dyn_array_ptr_size (&color_merge_array);
726 else if (size == 1) {
727 color = dyn_array_ptr_get (&color_merge_array, 0);
729 color = new_color (FALSE);
735 create_scc (ScanData *data)
738 gboolean found = FALSE;
739 gboolean found_bridge = FALSE;
740 ColorData *color_data = NULL;
742 for (i = dyn_array_ptr_size (&loop_stack) - 1; i >= 0; --i) {
743 ScanData *other = dyn_array_ptr_get (&loop_stack, i);
744 found_bridge |= other->is_bridge;
745 if (found_bridge || other == data)
750 printf ("|SCC rooted in %s (%p) has bridge %d\n", safe_name_bridge (data->obj), data->obj, found_bridge);
751 printf ("\tpoints-to-colors: ");
752 for (i = 0; i < dyn_array_ptr_size (&color_merge_array); ++i)
753 printf ("%p ", dyn_array_ptr_get (&color_merge_array, i));
756 printf ("loop stack: ");
757 for (i = 0; i < dyn_array_ptr_size (&loop_stack); ++i) {
758 ScanData *other = dyn_array_ptr_get (&loop_stack, i);
759 printf ("(%d/%d)", other->index, other->low_index);
765 color_data = new_color (TRUE);
766 ++num_colors_with_bridges;
768 color_data = reduce_color ();
771 while (dyn_array_ptr_size (&loop_stack) > 0) {
772 ScanData *other = dyn_array_ptr_pop (&loop_stack);
775 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);
778 other->color = color_data;
779 switch (other->state) {
780 case FINISHED_ON_STACK:
781 other->state = FINISHED_OFF_STACK;
783 case FINISHED_OFF_STACK:
786 g_error ("Invalid state when building SCC %d", other->state);
789 if (other->is_bridge)
790 dyn_array_ptr_add (&color_data->bridges, other->obj);
799 for (i = 0; i < dyn_array_ptr_size (&color_merge_array); ++i) {
800 ColorData *cd = dyn_array_ptr_get (&color_merge_array, i);
801 g_assert (cd->visited);
804 dyn_array_ptr_set_size (&color_merge_array, 0);
805 found_bridge = FALSE;
811 g_assert (dyn_array_ptr_size (&scan_stack) == 1);
812 g_assert (dyn_array_ptr_size (&loop_stack) == 0);
814 dyn_array_ptr_set_size (&color_merge_array, 0);
816 while (dyn_array_ptr_size (&scan_stack) > 0) {
817 ScanData *data = dyn_array_ptr_pop (&scan_stack);
820 * Ignore finished objects on stack, they happen due to loops. For example:
826 * We start scanning from A and push C before B. So, after the first iteration, the scan stack will have: A C B.
827 * We then visit B, which will find C in its initial state and push again.
828 * Finally after finish with C and B, the stack will be left with "A C" and at this point C should be ignored.
830 * The above explains FINISHED_ON_STACK, to explain FINISHED_OFF_STACK, consider if the root was D, which pointed
831 * to A and C. A is processed first, leaving C on stack after that in the mentioned state.
833 if (data->state == FINISHED_ON_STACK || data->state == FINISHED_OFF_STACK)
836 if (data->state == INITIAL) {
837 g_assert (data->index == -1);
838 g_assert (data->low_index == -1);
840 data->state = SCANNED;
841 data->low_index = data->index = object_index++;
842 dyn_array_ptr_push (&scan_stack, data);
843 dyn_array_ptr_push (&loop_stack, data);
846 printf ("+scanning %s (%p) index %d color %p\n", safe_name_bridge (data->obj), data->obj, data->index, data->color);
851 g_assert (data->state == SCANNED);
852 data->state = FINISHED_ON_STACK;
855 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);
858 /* Compute low index */
862 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);
865 if (data->index == data->low_index)
872 register_finalized_object (GCObject *obj)
874 g_assert (sgen_need_bridge_processing ());
875 dyn_array_ptr_push (®istered_bridges, obj);
881 dyn_array_ptr_set_size (®istered_bridges, 0);
887 dyn_array_ptr_set_size (&scan_stack, 0);
888 dyn_array_ptr_set_size (&loop_stack, 0);
889 dyn_array_ptr_set_size (®istered_bridges, 0);
890 free_object_buckets ();
891 free_color_buckets ();
894 num_colors_with_bridges = 0;
899 dump_color_table (const char *why, gboolean do_index)
903 printf ("colors%s:\n", why);
905 for (cur = root_color_bucket; cur; cur = cur->next, ++i) {
907 for (cd = &cur->data [0]; cd < cur->next_data; ++cd) {
909 printf ("\t%d(%d):", i, cd->api_index);
911 printf ("\t%d: ", i);
912 for (j = 0; j < dyn_array_ptr_size (&cd->other_colors); ++j) {
913 printf ("%p ", dyn_array_ptr_get (&cd->other_colors, j));
915 if (dyn_array_ptr_size (&cd->bridges)) {
916 printf (" bridges: ");
917 for (j = 0; j < dyn_array_ptr_size (&cd->bridges); ++j) {
918 GCObject *obj = dyn_array_ptr_get (&cd->bridges, j);
919 ScanData *data = find_or_create_data (obj);
920 printf ("%d ", data->index);
931 step_timer (gint64 *timer)
933 gint64 curtime, diff;
935 SGEN_TV_GETTIME (curtime);
936 diff = SGEN_TV_ELAPSED (*timer, curtime);
941 processing_stw_step (void)
947 if (!dyn_array_ptr_size (®istered_bridges))
950 #if defined (DUMP_GRAPH)
951 printf ("-----------------\n");
954 * bridge_processing_in_progress must be set with the world
955 * stopped. If not there would be race conditions.
957 bridge_processing_in_progress = TRUE;
959 SGEN_TV_GETTIME (curtime);
961 object_alloc_init ();
964 bridge_count = dyn_array_ptr_size (®istered_bridges);
965 for (i = 0; i < bridge_count ; ++i)
966 register_bridge_object (dyn_array_ptr_get (®istered_bridges, i));
968 setup_time = step_timer (&curtime);
970 for (i = 0; i < bridge_count; ++i) {
971 ScanData *sd = find_data (dyn_array_ptr_get (®istered_bridges, i));
972 if (sd->state == INITIAL) {
973 dyn_array_ptr_push (&scan_stack, sd);
976 g_assert (sd->state == FINISHED_OFF_STACK);
980 tarjan_time = step_timer (&curtime);
982 #if defined (DUMP_GRAPH)
983 printf ("----summary----\n");
984 printf ("bridges:\n");
985 for (i = 0; i < bridge_count; ++i) {
986 ScanData *sd = find_data (dyn_array_ptr_get (®istered_bridges, i));
987 printf ("\t%s (%p) index %d color %p\n", safe_name_bridge (sd->obj), sd->obj, sd->index, sd->color);
990 dump_color_table (" after tarjan", FALSE);
993 clear_after_processing ();
998 gather_xrefs (ColorData *color)
1001 for (i = 0; i < dyn_array_ptr_size (&color->other_colors); ++i) {
1002 ColorData *src = dyn_array_ptr_get (&color->other_colors, i);
1005 src->visited = TRUE;
1006 if (dyn_array_ptr_size (&src->bridges))
1007 dyn_array_ptr_add (&color_merge_array, src);
1014 reset_xrefs (ColorData *color)
1017 for (i = 0; i < dyn_array_ptr_size (&color->other_colors); ++i) {
1018 ColorData *src = dyn_array_ptr_get (&color->other_colors, i);
1021 src->visited = FALSE;
1022 if (!dyn_array_ptr_size (&src->bridges))
1028 processing_build_callback_data (int generation)
1031 MonoGCBridgeSCC **api_sccs;
1032 MonoGCBridgeXRef *api_xrefs;
1036 g_assert (bridge_processor->num_sccs == 0 && bridge_processor->num_xrefs == 0);
1037 g_assert (!bridge_processor->api_sccs && !bridge_processor->api_xrefs);
1039 if (!dyn_array_ptr_size (®istered_bridges))
1042 SGEN_TV_GETTIME (curtime);
1044 /*create API objects */
1046 #if defined (DUMP_GRAPH)
1047 printf ("***** API *****\n");
1048 printf ("number of SCCs %d\n", num_colors_with_bridges);
1051 /* This is a straightforward translation from colors to the bridge callback format. */
1052 api_sccs = sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC*) * num_colors_with_bridges, INTERNAL_MEM_BRIDGE_DATA, TRUE);
1053 api_index = xref_count = 0;
1055 for (cur = root_color_bucket; cur; cur = cur->next) {
1057 for (cd = &cur->data [0]; cd < cur->next_data; ++cd) {
1058 int bridges = dyn_array_ptr_size (&cd->bridges);
1062 api_sccs [api_index] = sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC) + sizeof (MonoObject*) * bridges, INTERNAL_MEM_BRIDGE_DATA, TRUE);
1063 api_sccs [api_index]->is_alive = FALSE;
1064 api_sccs [api_index]->num_objs = bridges;
1066 cd->api_index = api_index;
1068 for (j = 0; j < bridges; ++j)
1069 api_sccs [api_index]->objs [j] = dyn_array_ptr_get (&cd->bridges, j);
1074 scc_setup_time = step_timer (&curtime);
1076 for (cur = root_color_bucket; cur; cur = cur->next) {
1078 for (cd = &cur->data [0]; cd < cur->next_data; ++cd) {
1079 int bridges = dyn_array_ptr_size (&cd->bridges);
1083 dyn_array_ptr_set_size (&color_merge_array, 0);
1086 dyn_array_ptr_set_all (&cd->other_colors, &color_merge_array);
1087 xref_count += dyn_array_ptr_size (&cd->other_colors);
1091 gather_xref_time = step_timer (&curtime);
1093 #if defined (DUMP_GRAPH)
1094 printf ("TOTAL XREFS %d\n", xref_count);
1095 dump_color_table (" after xref pass", TRUE);
1098 api_xrefs = sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeXRef) * xref_count, INTERNAL_MEM_BRIDGE_DATA, TRUE);
1100 for (cur = root_color_bucket; cur; cur = cur->next) {
1102 for (src = &cur->data [0]; src < cur->next_data; ++src) {
1103 int bridges = dyn_array_ptr_size (&src->bridges);
1107 for (j = 0; j < dyn_array_ptr_size (&src->other_colors); ++j) {
1108 ColorData *dest = dyn_array_ptr_get (&src->other_colors, j);
1109 g_assert (dyn_array_ptr_size (&dest->bridges)); /* We flattened the color graph, so this must never happen. */
1111 api_xrefs [api_index].src_scc_index = src->api_index;
1112 api_xrefs [api_index].dst_scc_index = dest->api_index;
1118 g_assert (xref_count == api_index);
1119 xref_setup_time = step_timer (&curtime);
1121 #if defined (DUMP_GRAPH)
1122 printf ("---xrefs:\n");
1123 for (i = 0; i < xref_count; ++i)
1124 printf ("\t%d -> %d\n", api_xrefs [i].src_scc_index, api_xrefs [i].dst_scc_index);
1127 //FIXME move half of the cleanup to before the bridge callback?
1128 bridge_processor->num_sccs = num_colors_with_bridges;
1129 bridge_processor->api_sccs = api_sccs;
1130 bridge_processor->num_xrefs = xref_count;
1131 bridge_processor->api_xrefs = api_xrefs;
1135 processing_after_callback (int generation)
1138 int bridge_count = dyn_array_ptr_size (®istered_bridges);
1139 int object_count = object_data_count;
1140 int color_count = color_data_count;
1141 int scc_count = num_colors_with_bridges;
1143 SGEN_TV_GETTIME (curtime);
1148 cleanup_time = step_timer (&curtime);
1150 mono_trace (G_LOG_LEVEL_INFO, MONO_TRACE_GC, "GC_TAR_BRIDGE bridges %d objects %d colors %d ignored %d sccs %d xref %d cache %d/%d setup %.2fms tarjan %.2fms scc-setup %.2fms gather-xref %.2fms xref-setup %.2fms cleanup %.2fms",
1151 bridge_count, object_count, color_count,
1152 ignored_objects, scc_count, xref_count,
1153 cache_hits, cache_misses,
1154 setup_time / 10000.0f,
1155 tarjan_time / 10000.0f,
1156 scc_setup_time / 10000.0f,
1157 gather_xref_time / 10000.0f,
1158 xref_setup_time / 10000.0f,
1159 cleanup_time / 10000.0f);
1161 cache_hits = cache_misses = 0;
1162 ignored_objects = 0;
1163 bridge_processing_in_progress = FALSE;
1167 describe_pointer (GCObject *obj)
1169 // HashEntry *entry;
1172 for (i = 0; i < dyn_array_ptr_size (®istered_bridges); ++i) {
1173 if (obj == dyn_array_ptr_get (®istered_bridges, i)) {
1174 printf ("Pointer is a registered bridge object.\n");
1179 // entry = sgen_hash_table_lookup (&hash_table, obj);
1183 // printf ("Bridge hash table entry %p:\n", entry);
1184 // printf (" is bridge: %d\n", (int)entry->is_bridge);
1185 // printf (" is visited: %d\n", (int)entry->is_visited);
1189 sgen_tarjan_bridge_init (SgenBridgeProcessor *collector)
1191 collector->reset_data = reset_data;
1192 collector->processing_stw_step = processing_stw_step;
1193 collector->processing_build_callback_data = processing_build_callback_data;
1194 collector->processing_after_callback = processing_after_callback;
1195 collector->class_kind = class_kind;
1196 collector->register_finalized_object = register_finalized_object;
1197 collector->describe_pointer = describe_pointer;
1198 collector->enable_accounting = enable_accounting;
1199 // collector->set_dump_prefix = set_dump_prefix;
1201 sgen_register_fixed_internal_mem_type (INTERNAL_MEM_TARJAN_OBJ_BUCKET, BUCKET_SIZE);
1202 g_assert (sizeof (ObjectBucket) <= BUCKET_SIZE);
1203 g_assert (sizeof (ColorBucket) <= BUCKET_SIZE);
1204 bridge_processor = collector;