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.
47 #include "sgen-bridge.h"
48 #include "sgen-hash-table.h"
49 #include "sgen-qsort.h"
50 #include "tabledefs.h"
51 #include "utils/mono-logger-internal.h"
52 #include "utils/mono-time.h"
53 #include "utils/mono-compiler.h"
71 dyn_array_uninit (DynArray *da, int elem_size)
73 if (da->capacity <= 0)
76 sgen_free_internal_dynamic (da->data, elem_size * da->capacity, INTERNAL_MEM_BRIDGE_DATA);
81 dyn_array_ensure_capacity (DynArray *da, int capacity, int elem_size)
83 int old_capacity = da->capacity;
86 if (capacity <= old_capacity)
89 if (da->capacity == 0)
91 while (capacity > da->capacity)
94 new_data = sgen_alloc_internal_dynamic (elem_size * da->capacity, INTERNAL_MEM_BRIDGE_DATA, TRUE);
96 memcpy (new_data, da->data, elem_size * da->size);
97 sgen_free_internal_dynamic (da->data, elem_size * old_capacity, INTERNAL_MEM_BRIDGE_DATA);
103 dyn_array_add (DynArray *da, int elem_size)
107 dyn_array_ensure_capacity (da, da->size + 1, elem_size);
109 p = da->data + da->size * elem_size;
117 dyn_array_ptr_uninit (DynPtrArray *da)
119 dyn_array_uninit (&da->array, sizeof (void*));
123 dyn_array_ptr_size (DynPtrArray *da)
125 return da->array.size;
129 dyn_array_ptr_set_size (DynPtrArray *da, int size)
131 da->array.size = size;
135 dyn_array_ptr_get (DynPtrArray *da, int x)
137 return ((void**)da->array.data)[x];
141 dyn_array_ptr_add (DynPtrArray *da, void *ptr)
143 void **p = dyn_array_add (&da->array, sizeof (void*));
147 #define dyn_array_ptr_push dyn_array_ptr_add
150 dyn_array_ptr_pop (DynPtrArray *da)
153 int size = da->array.size;
155 p = dyn_array_ptr_get (da, size - 1);
161 dyn_array_ptr_ensure_capacity (DynPtrArray *da, int capacity)
163 dyn_array_ensure_capacity (&da->array, capacity, sizeof (void*));
168 dyn_array_ptr_set_all (DynPtrArray *dst, DynPtrArray *src)
170 if (src->array.size > 0) {
171 dyn_array_ptr_ensure_capacity (dst, src->array.size);
172 memcpy (dst->array.data, src->array.data, src->array.size * sizeof (void*));
174 dst->array.size = src->array.size;
178 enable_accounting (void)
180 // bridge_accounting_enabled = TRUE;
181 // 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);
184 static MonoGCBridgeObjectKind
185 class_kind (MonoClass *class)
187 MonoGCBridgeObjectKind res = bridge_callbacks.bridge_class_kind (class);
189 /* If it's a bridge, nothing we can do about it. */
190 if (res == GC_BRIDGE_TRANSPARENT_BRIDGE_CLASS || res == GC_BRIDGE_OPAQUE_BRIDGE_CLASS)
193 /* Non bridge classes with no pointers will never point to a bridge, so we can savely ignore them. */
194 if (!class->has_references) {
195 SGEN_LOG (6, "class %s is opaque\n", class->name);
196 return GC_BRIDGE_OPAQUE_CLASS;
199 /* Some arrays can be ignored */
200 if (class->rank == 1) {
201 MonoClass *elem_class = class->element_class;
203 /* FIXME the bridge check can be quite expensive, cache it at the class level. */
204 /* An array of a sealed type that is not a bridge will never get to a bridge */
205 if ((elem_class->flags & TYPE_ATTRIBUTE_SEALED) && !elem_class->has_references && !bridge_callbacks.bridge_class_kind (elem_class)) {
206 SGEN_LOG (6, "class %s is opaque\n", class->name);
207 return GC_BRIDGE_OPAQUE_CLASS;
211 return GC_BRIDGE_TRANSPARENT_CLASS;
214 //enable unsage logging
215 // #define DUMP_GRAPH 1
226 We can split this data structure in two, those with bridges and those without
229 DynPtrArray other_colors;
232 unsigned visited : 1;
237 MonoObject *obj; //XXX this can be eliminated.
245 unsigned is_bridge : 1;
246 unsigned obj_state : 2;
252 static DynPtrArray scan_stack, loop_stack, registered_bridges;
253 static DynPtrArray color_merge_array;
255 static int ignored_objects;
256 static int object_index;
257 static int num_colors_with_bridges;
258 static int xref_count;
260 static size_t setup_time, tarjan_time, scc_setup_time, gather_xref_time, xref_setup_time, cleanup_time;
261 static SgenBridgeProcessor *bridge_processor;
263 #define BUCKET_SIZE 8184
266 #define NUM_SCAN_ENTRIES ((BUCKET_SIZE - SIZEOF_VOID_P * 2) / sizeof (ScanData))
268 typedef struct _ObjectBucket ObjectBucket;
269 struct _ObjectBucket {
272 ScanData data [NUM_SCAN_ENTRIES];
275 static ObjectBucket *root_object_bucket;
276 static ObjectBucket *cur_object_bucket;
277 static int object_data_count;
280 new_object_bucket (void)
282 ObjectBucket *res = sgen_alloc_internal (INTERNAL_MEM_TARJAN_OBJ_BUCKET);
283 res->next_data = &res->data [0];
288 object_alloc_init (void)
290 root_object_bucket = cur_object_bucket = new_object_bucket ();
294 alloc_object_data (void)
299 /* next_data points to the first free entry */
300 res = cur_object_bucket->next_data;
301 if (res >= &cur_object_bucket->data [NUM_SCAN_ENTRIES]) {
302 ObjectBucket *b = new_object_bucket ();
303 cur_object_bucket->next = b;
304 cur_object_bucket = b;
307 cur_object_bucket->next_data = res + 1;
313 free_object_buckets (void)
315 ObjectBucket *cur = root_object_bucket;
317 object_data_count = 0;
320 ObjectBucket *tmp = cur->next;
321 sgen_free_internal (cur, INTERNAL_MEM_TARJAN_OBJ_BUCKET);
325 root_object_bucket = cur_object_bucket = NULL;
329 #define NUM_COLOR_ENTRIES ((BUCKET_SIZE - SIZEOF_VOID_P * 2) / sizeof (ColorData))
331 typedef struct _ColorBucket ColorBucket;
332 struct _ColorBucket {
334 ColorData *next_data;
335 ColorData data [NUM_COLOR_ENTRIES];
338 static ColorBucket *root_color_bucket;
339 static ColorBucket *cur_color_bucket;
340 static int color_data_count;
344 new_color_bucket (void)
346 ColorBucket *res = sgen_alloc_internal (INTERNAL_MEM_TARJAN_OBJ_BUCKET);
347 res->next_data = &res->data [0];
352 color_alloc_init (void)
354 root_color_bucket = cur_color_bucket = new_color_bucket ();
358 alloc_color_data (void)
363 /* next_data points to the first free entry */
364 res = cur_color_bucket->next_data;
365 if (res >= &cur_color_bucket->data [NUM_COLOR_ENTRIES]) {
366 ColorBucket *b = new_color_bucket ();
367 cur_color_bucket->next = b;
368 cur_color_bucket = b;
371 cur_color_bucket->next_data = res + 1;
377 free_color_buckets (void)
379 ColorBucket *cur, *tmp;
381 color_data_count = 0;
383 for (cur = root_color_bucket; cur; cur = tmp) {
385 for (cd = &cur->data [0]; cd < cur->next_data; ++cd) {
386 dyn_array_ptr_uninit (&cd->other_colors);
387 dyn_array_ptr_uninit (&cd->bridges);
390 sgen_free_internal (cur, INTERNAL_MEM_TARJAN_OBJ_BUCKET);
392 root_color_bucket = cur_color_bucket = NULL;
397 create_data (MonoObject *obj)
399 mword *o = (mword*)obj;
400 ScanData *res = alloc_object_data ();
403 res->index = res->low_index = -1;
404 res->obj_state = o [0] & SGEN_VTABLE_BITS_MASK;
405 res->lock_word = o [1];
407 o [0] |= SGEN_VTABLE_BITS_MASK;
413 find_data (MonoObject *obj)
416 mword *o = (mword*)obj;
417 if ((o [0] & SGEN_VTABLE_BITS_MASK) == SGEN_VTABLE_BITS_MASK)
418 a = (ScanData*)o [1];
423 clear_after_processing (void)
427 for (cur = root_object_bucket; cur; cur = cur->next) {
429 for (sd = &cur->data [0]; sd < cur->next_data; ++sd) {
430 mword *o = (mword*)sd->obj;
431 o [0] &= ~SGEN_VTABLE_BITS_MASK;
432 o [0] |= sd->obj_state;
433 o [1] = sd->lock_word;
439 bridge_object_forward (MonoObject *obj)
442 mword *o = (mword*)obj;
443 if ((o [0] & SGEN_VTABLE_BITS_MASK) == SGEN_VTABLE_BITS_MASK)
446 fwd = SGEN_OBJECT_IS_FORWARDED (obj);
447 return fwd ? fwd : obj;
452 safe_name_bridge (MonoObject *obj)
454 MonoVTable *vt = (MonoVTable*)SGEN_LOAD_VTABLE (obj);
455 return vt->klass->name;
459 find_or_create_data (MonoObject *obj)
461 ScanData *entry = find_data (obj);
463 entry = create_data (obj);
475 We tried 2/32, 2/128, 4/32, 4/128, 6/128 and 8/128.
477 The performance cost between 4/128 and 8/128 is so small since cache movement happens completely in the same cacheline,
478 making the extra space pretty much free.
480 The cost between 32 and 128 itens is minimal too, it's mostly a fixed, setup cost.
482 Memory wise, 4/32 takes 512 and 8/128 takes 8k, so it's quite reasonable.
485 #define ELEMENTS_PER_BUCKET 8
486 #define COLOR_CACHE_SIZE 128
487 static HashEntry merge_cache [COLOR_CACHE_SIZE][ELEMENTS_PER_BUCKET];
490 mix_hash (size_t hash)
492 return (int)(((hash * 215497) >> 16) ^ ((hash * 1823231) + hash));
498 memset (merge_cache, 0, sizeof (merge_cache));
503 dyn_array_ptr_contains (DynPtrArray *da, void *x)
506 for (i = 0; i < dyn_array_ptr_size (da); ++i)
507 if (dyn_array_ptr_get (da, i) == x)
513 match_colors (DynPtrArray *a, DynPtrArray *b)
516 if (dyn_array_ptr_size (a) != dyn_array_ptr_size (b))
519 for (i = 0; i < dyn_array_ptr_size (a); ++i) {
520 if (!dyn_array_ptr_contains (b, dyn_array_ptr_get (a, i)))
526 static int cache_hits, cache_misses;
529 find_in_cache (int *insert_index)
532 int i, hash, size, index;
534 size = dyn_array_ptr_size (&color_merge_array);
535 /* Cache checking is very ineficient with a lot of elements*/
540 for (i = 0 ; i < size; ++i)
541 hash += mix_hash ((size_t)dyn_array_ptr_get (&color_merge_array, i));
545 index = hash & (COLOR_CACHE_SIZE - 1);
546 bucket = merge_cache [index];
547 for (i = 0; i < ELEMENTS_PER_BUCKET; ++i) {
548 if (bucket [i].hash != hash)
550 if (match_colors (&bucket [i].color->other_colors, &color_merge_array)) {
552 return bucket [i].color;
556 //move elements to the back
557 for (i = ELEMENTS_PER_BUCKET - 1; i > 0; --i)
558 bucket [i] = bucket [i - 1];
560 *insert_index = index;
561 bucket [0].hash = hash;
566 new_color (gboolean force_new)
570 /* XXX Try to find an equal one and return it */
572 cd = find_in_cache (&i);
577 cd = alloc_color_data ();
579 dyn_array_ptr_set_all (&cd->other_colors, &color_merge_array);
580 /* if i >= 0, it means we prepared a given slot to receive the new color */
582 merge_cache [i][0].color = cd;
589 register_bridge_object (MonoObject *obj)
591 create_data (obj)->is_bridge = TRUE;
595 is_opaque_object (MonoObject *obj)
597 MonoVTable *vt = (MonoVTable*)SGEN_LOAD_VTABLE (obj);
598 if ((vt->gc_bits & SGEN_GC_BIT_BRIDGE_OPAQUE_OBJECT) == SGEN_GC_BIT_BRIDGE_OPAQUE_OBJECT) {
599 SGEN_LOG (6, "ignoring %s\n", vt->klass->name);
607 push_object (MonoObject *obj)
610 obj = bridge_object_forward (obj);
613 printf ("\t= pushing %p %s -> ", obj, safe_name_bridge (obj));
616 /* Object types we can ignore */
617 if (is_opaque_object (obj)) {
624 data = find_data (obj);
626 /* Already marked - XXX must be done this way as the bridge themselves are alive. */
627 if (data && data->state != INITIAL) {
629 printf ("already marked\n");
634 /* We only care about dead objects */
635 if (!data && sgen_object_is_live (obj)) {
643 printf ("pushed!\n");
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);
654 #define HANDLE_PTR(ptr,obj) do { \
655 MonoObject *dst = (MonoObject*)*(ptr); \
656 if (dst) push_object (dst); \
660 push_all (ScanData *data)
662 MonoObject *obj = data->obj;
663 char *start = (char*)obj;
664 mword desc = sgen_obj_get_descriptor_safe (start);
667 printf ("**scanning %p %s\n", obj, safe_name_bridge (obj));
670 #include "sgen-scan-object.h"
675 compute_low_index (ScanData *data, MonoObject *obj)
679 obj = bridge_object_forward (obj);
681 other = find_data (obj);
684 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);
689 g_assert (other->state != INITIAL);
691 if ((other->state == SCANNED || other->state == FINISHED_ON_STACK) && data->low_index > other->low_index)
692 data->low_index = other->low_index;
694 /* Compute the low color */
695 if (other->color == NULL)
700 dyn_array_ptr_add (&color_merge_array, other->color);
706 #define HANDLE_PTR(ptr,obj) do { \
707 MonoObject *dst = (MonoObject*)*(ptr); \
708 if (dst) compute_low_index (data, dst); \
712 compute_low (ScanData *data)
714 MonoObject *obj = data->obj;
715 char *start = (char*)obj;
716 mword desc = sgen_obj_get_descriptor_safe (start);
718 #include "sgen-scan-object.h"
724 ColorData *color = NULL;
725 int size = dyn_array_ptr_size (&color_merge_array);
729 else if (size == 1) {
730 color = dyn_array_ptr_get (&color_merge_array, 0);
732 color = new_color (FALSE);
738 create_scc (ScanData *data)
741 gboolean found = FALSE;
742 gboolean found_bridge = FALSE;
743 ColorData *color_data = NULL;
745 for (i = dyn_array_ptr_size (&loop_stack) - 1; i >= 0; --i) {
746 ScanData *other = dyn_array_ptr_get (&loop_stack, i);
747 found_bridge |= other->is_bridge;
748 if (found_bridge || other == data)
753 printf ("|SCC rooted in %s (%p) has bridge %d\n", safe_name_bridge (data->obj), data->obj, found_bridge);
754 printf ("\tpoints-to-colors: ");
755 for (i = 0; i < dyn_array_ptr_size (&color_merge_array); ++i)
756 printf ("%p ", dyn_array_ptr_get (&color_merge_array, i));
759 printf ("loop stack: ");
760 for (i = 0; i < dyn_array_ptr_size (&loop_stack); ++i) {
761 ScanData *other = dyn_array_ptr_get (&loop_stack, i);
762 printf ("(%d/%d)", other->index, other->low_index);
768 color_data = new_color (TRUE);
769 ++num_colors_with_bridges;
771 color_data = reduce_color ();
774 while (dyn_array_ptr_size (&loop_stack) > 0) {
775 ScanData *other = dyn_array_ptr_pop (&loop_stack);
778 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);
781 other->color = color_data;
782 switch (other->state) {
783 case FINISHED_ON_STACK:
784 other->state = FINISHED_OFF_STACK;
786 case FINISHED_OFF_STACK:
789 g_error ("Invalid state when building SCC %d", other->state);
792 if (other->is_bridge)
793 dyn_array_ptr_add (&color_data->bridges, other->obj);
802 for (i = 0; i < dyn_array_ptr_size (&color_merge_array); ++i) {
803 ColorData *cd = dyn_array_ptr_get (&color_merge_array, i);
804 g_assert (cd->visited);
807 dyn_array_ptr_set_size (&color_merge_array, 0);
808 found_bridge = FALSE;
814 g_assert (dyn_array_ptr_size (&scan_stack) == 1);
815 g_assert (dyn_array_ptr_size (&loop_stack) == 0);
817 dyn_array_ptr_set_size (&color_merge_array, 0);
819 while (dyn_array_ptr_size (&scan_stack) > 0) {
820 ScanData *data = dyn_array_ptr_pop (&scan_stack);
823 * Ignore finished objects on stack, they happen due to loops. For example:
829 * We start scanning from A and push C before B. So, after the first iteration, the scan stack will have: A C B.
830 * We then visit B, which will find C in its initial state and push again.
831 * Finally after finish with C and B, the stack will be left with "A C" and at this point C should be ignored.
833 * The above explains FINISHED_ON_STACK, to explain FINISHED_OFF_STACK, consider if the root was D, which pointed
834 * to A and C. A is processed first, leaving C on stack after that in the mentioned state.
836 if (data->state == FINISHED_ON_STACK || data->state == FINISHED_OFF_STACK)
839 if (data->state == INITIAL) {
840 g_assert (data->index == -1);
841 g_assert (data->low_index == -1);
843 data->state = SCANNED;
844 data->low_index = data->index = object_index++;
845 dyn_array_ptr_push (&scan_stack, data);
846 dyn_array_ptr_push (&loop_stack, data);
849 printf ("+scanning %s (%p) index %d color %p\n", safe_name_bridge (data->obj), data->obj, data->index, data->color);
854 g_assert (data->state == SCANNED);
855 data->state = FINISHED_ON_STACK;
858 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);
861 /* Compute low index */
865 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);
868 if (data->index == data->low_index)
875 register_finalized_object (MonoObject *obj)
877 g_assert (sgen_need_bridge_processing ());
878 dyn_array_ptr_push (®istered_bridges, obj);
884 dyn_array_ptr_set_size (®istered_bridges, 0);
890 dyn_array_ptr_set_size (&scan_stack, 0);
891 dyn_array_ptr_set_size (&loop_stack, 0);
892 dyn_array_ptr_set_size (®istered_bridges, 0);
893 free_object_buckets ();
894 free_color_buckets ();
897 num_colors_with_bridges = 0;
902 dump_color_table (const char *why, gboolean do_index)
906 printf ("colors%s:\n", why);
908 for (cur = root_color_bucket; cur; cur = cur->next, ++i) {
910 for (cd = &cur->data [0]; cd < cur->next_data; ++cd) {
912 printf ("\t%d(%d):", i, cd->api_index);
914 printf ("\t%d: ", i);
915 for (j = 0; j < dyn_array_ptr_size (&cd->other_colors); ++j) {
916 printf ("%p ", dyn_array_ptr_get (&cd->other_colors, j));
918 if (dyn_array_ptr_size (&cd->bridges)) {
919 printf (" bridges: ");
920 for (j = 0; j < dyn_array_ptr_size (&cd->bridges); ++j) {
921 MonoObject *obj = dyn_array_ptr_get (&cd->bridges, j);
922 ScanData *data = find_or_create_data (obj);
923 printf ("%d ", data->index);
934 step_timer (gint64 *timer)
936 gint64 curtime, diff;
938 SGEN_TV_GETTIME (curtime);
939 diff = SGEN_TV_ELAPSED (*timer, curtime);
944 processing_stw_step (void)
950 if (!dyn_array_ptr_size (®istered_bridges))
953 #if defined (DUMP_GRAPH)
954 printf ("-----------------\n");
957 * bridge_processing_in_progress must be set with the world
958 * stopped. If not there would be race conditions.
960 bridge_processing_in_progress = TRUE;
962 SGEN_TV_GETTIME (curtime);
964 object_alloc_init ();
967 bridge_count = dyn_array_ptr_size (®istered_bridges);
968 for (i = 0; i < bridge_count ; ++i)
969 register_bridge_object (dyn_array_ptr_get (®istered_bridges, i));
971 setup_time = step_timer (&curtime);
973 for (i = 0; i < bridge_count; ++i) {
974 ScanData *sd = find_data (dyn_array_ptr_get (®istered_bridges, i));
975 if (sd->state == INITIAL) {
976 dyn_array_ptr_push (&scan_stack, sd);
979 g_assert (sd->state == FINISHED_OFF_STACK);
983 tarjan_time = step_timer (&curtime);
985 #if defined (DUMP_GRAPH)
986 printf ("----summary----\n");
987 printf ("bridges:\n");
988 for (i = 0; i < bridge_count; ++i) {
989 ScanData *sd = find_data (dyn_array_ptr_get (®istered_bridges, i));
990 printf ("\t%s (%p) index %d color %p\n", safe_name_bridge (sd->obj), sd->obj, sd->index, sd->color);
993 dump_color_table (" after tarjan", FALSE);
996 clear_after_processing ();
1001 gather_xrefs (ColorData *color)
1004 for (i = 0; i < dyn_array_ptr_size (&color->other_colors); ++i) {
1005 ColorData *src = dyn_array_ptr_get (&color->other_colors, i);
1008 src->visited = TRUE;
1009 if (dyn_array_ptr_size (&src->bridges))
1010 dyn_array_ptr_add (&color_merge_array, src);
1017 reset_xrefs (ColorData *color)
1020 for (i = 0; i < dyn_array_ptr_size (&color->other_colors); ++i) {
1021 ColorData *src = dyn_array_ptr_get (&color->other_colors, i);
1024 src->visited = FALSE;
1025 if (!dyn_array_ptr_size (&src->bridges))
1031 processing_build_callback_data (int generation)
1034 MonoGCBridgeSCC **api_sccs;
1035 MonoGCBridgeXRef *api_xrefs;
1039 g_assert (bridge_processor->num_sccs == 0 && bridge_processor->num_xrefs == 0);
1040 g_assert (!bridge_processor->api_sccs && !bridge_processor->api_xrefs);
1042 if (!dyn_array_ptr_size (®istered_bridges))
1045 SGEN_TV_GETTIME (curtime);
1047 /*create API objects */
1049 #if defined (DUMP_GRAPH)
1050 printf ("***** API *****\n");
1051 printf ("number of SCCs %d\n", num_colors_with_bridges);
1054 /* This is a straightforward translation from colors to the bridge callback format. */
1055 api_sccs = sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC*) * num_colors_with_bridges, INTERNAL_MEM_BRIDGE_DATA, TRUE);
1056 api_index = xref_count = 0;
1058 for (cur = root_color_bucket; cur; cur = cur->next) {
1060 for (cd = &cur->data [0]; cd < cur->next_data; ++cd) {
1061 int bridges = dyn_array_ptr_size (&cd->bridges);
1065 api_sccs [api_index] = sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC) + sizeof (MonoObject*) * bridges, INTERNAL_MEM_BRIDGE_DATA, TRUE);
1066 api_sccs [api_index]->is_alive = FALSE;
1067 api_sccs [api_index]->num_objs = bridges;
1069 cd->api_index = api_index;
1071 for (j = 0; j < bridges; ++j)
1072 api_sccs [api_index]->objs [j] = dyn_array_ptr_get (&cd->bridges, j);
1077 scc_setup_time = step_timer (&curtime);
1079 for (cur = root_color_bucket; cur; cur = cur->next) {
1081 for (cd = &cur->data [0]; cd < cur->next_data; ++cd) {
1082 int bridges = dyn_array_ptr_size (&cd->bridges);
1086 dyn_array_ptr_set_size (&color_merge_array, 0);
1089 dyn_array_ptr_set_all (&cd->other_colors, &color_merge_array);
1090 xref_count += dyn_array_ptr_size (&cd->other_colors);
1094 gather_xref_time = step_timer (&curtime);
1096 #if defined (DUMP_GRAPH)
1097 printf ("TOTAL XREFS %d\n", xref_count);
1098 dump_color_table (" after xref pass", TRUE);
1101 api_xrefs = sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeXRef) * xref_count, INTERNAL_MEM_BRIDGE_DATA, TRUE);
1103 for (cur = root_color_bucket; cur; cur = cur->next) {
1105 for (src = &cur->data [0]; src < cur->next_data; ++src) {
1106 int bridges = dyn_array_ptr_size (&src->bridges);
1110 for (j = 0; j < dyn_array_ptr_size (&src->other_colors); ++j) {
1111 ColorData *dest = dyn_array_ptr_get (&src->other_colors, j);
1112 g_assert (dyn_array_ptr_size (&dest->bridges)); /* We flattened the color graph, so this must never happen. */
1114 api_xrefs [api_index].src_scc_index = src->api_index;
1115 api_xrefs [api_index].dst_scc_index = dest->api_index;
1121 g_assert (xref_count == api_index);
1122 xref_setup_time = step_timer (&curtime);
1124 #if defined (DUMP_GRAPH)
1125 printf ("---xrefs:\n");
1126 for (i = 0; i < xref_count; ++i)
1127 printf ("\t%d -> %d\n", api_xrefs [i].src_scc_index, api_xrefs [i].dst_scc_index);
1130 //FIXME move half of the cleanup to before the bridge callback?
1131 bridge_processor->num_sccs = num_colors_with_bridges;
1132 bridge_processor->api_sccs = api_sccs;
1133 bridge_processor->num_xrefs = xref_count;
1134 bridge_processor->api_xrefs = api_xrefs;
1138 processing_after_callback (int generation)
1141 int bridge_count = dyn_array_ptr_size (®istered_bridges);
1142 int object_count = object_data_count;
1143 int color_count = color_data_count;
1144 int scc_count = num_colors_with_bridges;
1146 SGEN_TV_GETTIME (curtime);
1151 cleanup_time = step_timer (&curtime);
1153 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",
1154 bridge_count, object_count, color_count,
1155 ignored_objects, scc_count, xref_count,
1156 cache_hits, cache_misses,
1157 setup_time / 10000.0f,
1158 tarjan_time / 10000.0f,
1159 scc_setup_time / 10000.0f,
1160 gather_xref_time / 10000.0f,
1161 xref_setup_time / 10000.0f,
1162 cleanup_time / 10000.0f);
1164 cache_hits = cache_misses = 0;
1165 ignored_objects = 0;
1166 bridge_processing_in_progress = FALSE;
1170 describe_pointer (MonoObject *obj)
1172 // HashEntry *entry;
1175 for (i = 0; i < dyn_array_ptr_size (®istered_bridges); ++i) {
1176 if (obj == dyn_array_ptr_get (®istered_bridges, i)) {
1177 printf ("Pointer is a registered bridge object.\n");
1182 // entry = sgen_hash_table_lookup (&hash_table, obj);
1186 // printf ("Bridge hash table entry %p:\n", entry);
1187 // printf (" is bridge: %d\n", (int)entry->is_bridge);
1188 // printf (" is visited: %d\n", (int)entry->is_visited);
1192 sgen_tarjan_bridge_init (SgenBridgeProcessor *collector)
1194 collector->reset_data = reset_data;
1195 collector->processing_stw_step = processing_stw_step;
1196 collector->processing_build_callback_data = processing_build_callback_data;
1197 collector->processing_after_callback = processing_after_callback;
1198 collector->class_kind = class_kind;
1199 collector->register_finalized_object = register_finalized_object;
1200 collector->describe_pointer = describe_pointer;
1201 collector->enable_accounting = enable_accounting;
1202 // collector->set_dump_prefix = set_dump_prefix;
1204 sgen_register_fixed_internal_mem_type (INTERNAL_MEM_TARJAN_OBJ_BUCKET, BUCKET_SIZE);
1205 g_assert (sizeof (ObjectBucket) <= BUCKET_SIZE);
1206 g_assert (sizeof (ColorBucket) <= BUCKET_SIZE);
1207 bridge_processor = collector;