3 * Tarjan-based bridge implementation.
5 * Copyright 2011 Novell, Inc (http://www.novell.com)
6 * Copyright 2014 Xamarin Inc (http://www.xamarin.com)
9 * Copyright 2001-2003 Ximian, Inc
10 * Copyright 2003-2010 Novell, Inc.
12 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
17 #if defined (HAVE_SGEN_GC) && !defined (DISABLE_SGEN_GC_BRIDGE)
21 #include "sgen/sgen-gc.h"
22 #include "sgen-bridge-internals.h"
23 #include "tabledefs.h"
24 #include "utils/mono-logger-internals.h"
26 #include "sgen-dynarray.h"
29 * See comments in sgen-bridge.h
31 * This bridge implementation is based on the tarjan algorithm for strongly
32 * connected components. It has two elements:
34 * - Standard tarjan SCC algorithm to convert graph to SCC forest
36 * - "Colors": We reduce the SCC forest to bridged-SCCs-only by using a
37 * "color" algorithm devised by Kumpera. Consider the set of bridged SCCs
38 * which is reachable from a given object. We call each such unique set a
39 * "color". We compute the set of colors and which colors contain links to
40 * which colors. The color graph then becomes the reduced SCC graph.
43 // Is this class bridged or not, and should its dependencies be scanned or not?
44 // The result of this callback will be cached for use by is_opaque_object later.
45 static MonoGCBridgeObjectKind
46 class_kind (MonoClass
*klass
)
48 MonoGCBridgeObjectKind res
= mono_bridge_callbacks
.bridge_class_kind (klass
);
50 /* If it's a bridge, nothing we can do about it. */
51 if (res
== GC_BRIDGE_TRANSPARENT_BRIDGE_CLASS
|| res
== GC_BRIDGE_OPAQUE_BRIDGE_CLASS
)
54 /* Non bridge classes with no pointers will never point to a bridge, so we can savely ignore them. */
55 if (!m_class_has_references (klass
)) {
56 SGEN_LOG (6, "class %s is opaque\n", m_class_get_name (klass
));
57 return GC_BRIDGE_OPAQUE_CLASS
;
60 /* Some arrays can be ignored */
61 if (m_class_get_rank (klass
) == 1) {
62 MonoClass
*elem_class
= m_class_get_element_class (klass
);
64 /* FIXME the bridge check can be quite expensive, cache it at the class level. */
65 /* An array of a sealed type that is not a bridge will never get to a bridge */
66 if ((mono_class_get_flags (elem_class
) & TYPE_ATTRIBUTE_SEALED
) && !m_class_has_references (elem_class
) && !mono_bridge_callbacks
.bridge_class_kind (elem_class
)) {
67 SGEN_LOG (6, "class %s is opaque\n", m_class_get_name (klass
));
68 return GC_BRIDGE_OPAQUE_CLASS
;
72 return GC_BRIDGE_TRANSPARENT_CLASS
;
75 //enable usage logging
76 // #define DUMP_GRAPH 1
78 /* Used in bridgeless_color_is_heavy:
79 * The idea here is as long as the reference fanin and fanout on a node are both 2 or greater, then
80 * removing that node will result in a net increase in edge count. So the question is which node
81 * removals are counterproductive (i.e., how many edges saved balances out one node added).
82 * The number of edges saved by preserving a node is (fanin*fanout - fanin - fanout).
84 * With all that in mind:
86 * - HEAVY_REFS_MIN is the number that *both* fanin and fanout must meet to preserve the node.
87 * - HEAVY_COMBINED_REFS_MIN is the number (fanin*fanout) must meet to preserve the node.
89 * Note HEAVY_COMBINED_REFS_MIN must be <= 2*INCOMING_COLORS_MAX, or we won't know the true fanin.
92 #define HEAVY_REFS_MIN 2
93 #define HEAVY_COMBINED_REFS_MIN 60
96 * The higher INCOMING_COLORS_BITS is the higher HEAVY_COMBINED_REFS_MIN can be (see above).
97 * However, API_INDEX_BITS + INCOMING_COLORS_BITS must be equal to 31, and if API_INDEX_BITS is too
98 * low then terrible things will happen if too many colors are generated. (The number of colors we
99 * will ever attempt to generate is currently naturally limited by the JNI GREF limit.)
102 #define API_INDEX_BITS 26
103 #define INCOMING_COLORS_BITS 5
105 #define API_INDEX_MAX ((1<<API_INDEX_BITS)-1)
106 #define INCOMING_COLORS_MAX ((1<<INCOMING_COLORS_BITS)-1)
118 We can split this data structure in two, those with bridges and those without
119 (and only bridgeless need to record incoming_colors)
122 // Colors (ColorDatas) linked to by objects with this color
123 DynPtrArray other_colors
;
124 // Bridge objects (GCObjects) held by objects with this color
126 // Index of this color's MonoGCBridgeSCC in the array passed to the client (or -1 for none)
127 signed api_index
: API_INDEX_BITS
;
128 // Count of colors that list this color in their other_colors
129 unsigned incoming_colors
: INCOMING_COLORS_BITS
;
130 unsigned visited
: 1;
133 // Represents one managed object. Equivalent of new/old bridge "HashEntry"
134 typedef struct _ScanData
{
135 // FIXME this can be eliminated; if we have a ScanData we generally looked it up from its GCObject
137 // We use the sgen lock_word in GCObject to store a pointer to the ScanData. Cache the original here to restore later:
141 // Tarjan algorithm index (order visited)
143 // Tarjan index of lowest-index object known reachable from here
144 signed low_index
: 27;
146 // See "ScanData state" enum above
148 unsigned is_bridge
: 1;
149 // Similar to lock_word, we use these bits in the GCObject as scratch space then restore them when done
150 unsigned obj_state
: 2;
153 /* Should color be made visible to client even though it has no bridges?
154 * True if we predict the number of reduced edges to be enough to justify the extra node.
156 static inline gboolean
157 bridgeless_color_is_heavy (ColorData
*data
) {
158 int fanin
= data
->incoming_colors
;
159 int fanout
= dyn_array_ptr_size (&data
->other_colors
);
160 return fanin
> HEAVY_REFS_MIN
&& fanout
> HEAVY_REFS_MIN
161 && fanin
*fanout
>= HEAVY_COMBINED_REFS_MIN
;
164 // Should color be made visible to client?
165 static inline gboolean
166 color_visible_to_client (ColorData
*data
) {
167 return dyn_array_ptr_size (&data
->bridges
) || bridgeless_color_is_heavy (data
);
170 // Stacks of ScanData objects used for tarjan algorithm.
171 // The Tarjan algorithm is normally defined recursively; here scan_stack simulates the call stack of a recursive algorithm,
172 // and loop_stack is the stack structure used by the algorithm itself.
173 static DynPtrArray scan_stack
, loop_stack
;
175 // GCObjects on which register_finalized_object has been called
176 static DynPtrArray registered_bridges
;
178 // As we traverse the graph, which ColorData objects are accessible from our current position?
179 static DynPtrArray color_merge_array
;
180 // Running hash of the contents of the color_merge_array.
181 static unsigned int color_merge_array_hash
;
183 static void color_merge_array_empty (void)
185 dyn_array_ptr_empty (&color_merge_array
);
186 color_merge_array_hash
= 0;
189 static int ignored_objects
;
190 static int object_index
;
191 static int num_colors_with_bridges
;
193 static int xref_count
;
195 static size_t setup_time
, tarjan_time
, scc_setup_time
, gather_xref_time
, xref_setup_time
, cleanup_time
;
196 static SgenBridgeProcessor
*bridge_processor
;
198 #define BUCKET_SIZE 8184
201 #define NUM_SCAN_ENTRIES ((BUCKET_SIZE - SIZEOF_VOID_P * 2) / sizeof (ScanData))
203 typedef struct _ObjectBucket ObjectBucket
;
204 struct _ObjectBucket
{
207 ScanData data
[NUM_SCAN_ENTRIES
];
210 static ObjectBucket
*root_object_bucket
;
211 static ObjectBucket
*cur_object_bucket
;
212 static int object_data_count
;
214 // Arenas to allocate ScanData from
216 new_object_bucket (void)
218 ObjectBucket
*res
= (ObjectBucket
*)sgen_alloc_internal (INTERNAL_MEM_TARJAN_OBJ_BUCKET
);
219 res
->next_data
= &res
->data
[0];
224 object_alloc_init (void)
226 root_object_bucket
= cur_object_bucket
= new_object_bucket ();
230 alloc_object_data (void)
235 /* next_data points to the first free entry */
236 res
= cur_object_bucket
->next_data
;
237 if (res
>= &cur_object_bucket
->data
[NUM_SCAN_ENTRIES
]) {
238 ObjectBucket
*b
= new_object_bucket ();
239 cur_object_bucket
->next
= b
;
240 cur_object_bucket
= b
;
243 cur_object_bucket
->next_data
= res
+ 1;
249 free_object_buckets (void)
251 ObjectBucket
*cur
= root_object_bucket
;
253 object_data_count
= 0;
256 ObjectBucket
*tmp
= cur
->next
;
257 sgen_free_internal (cur
, INTERNAL_MEM_TARJAN_OBJ_BUCKET
);
261 root_object_bucket
= cur_object_bucket
= NULL
;
265 #define NUM_COLOR_ENTRIES ((BUCKET_SIZE - SIZEOF_VOID_P * 2) / sizeof (ColorData))
267 // Arenas for ColorDatas, same as ObjectBucket except items-per-bucket differs
268 typedef struct _ColorBucket ColorBucket
;
269 struct _ColorBucket
{
271 ColorData
*next_data
;
272 ColorData data
[NUM_COLOR_ENTRIES
];
275 static ColorBucket
*root_color_bucket
;
276 static ColorBucket
*cur_color_bucket
;
277 static int color_data_count
;
281 new_color_bucket (void)
283 ColorBucket
*res
= (ColorBucket
*)sgen_alloc_internal (INTERNAL_MEM_TARJAN_OBJ_BUCKET
);
284 res
->next_data
= &res
->data
[0];
289 color_alloc_init (void)
291 root_color_bucket
= cur_color_bucket
= new_color_bucket ();
295 alloc_color_data (void)
300 /* next_data points to the first free entry */
301 res
= cur_color_bucket
->next_data
;
302 if (res
>= &cur_color_bucket
->data
[NUM_COLOR_ENTRIES
]) {
303 ColorBucket
*b
= new_color_bucket ();
304 cur_color_bucket
->next
= b
;
305 cur_color_bucket
= b
;
308 cur_color_bucket
->next_data
= res
+ 1;
314 free_color_buckets (void)
316 ColorBucket
*cur
, *tmp
;
318 color_data_count
= 0;
320 for (cur
= root_color_bucket
; cur
; cur
= tmp
) {
322 for (cd
= &cur
->data
[0]; cd
< cur
->next_data
; ++cd
) {
323 dyn_array_ptr_uninit (&cd
->other_colors
);
324 dyn_array_ptr_uninit (&cd
->bridges
);
327 sgen_free_internal (cur
, INTERNAL_MEM_TARJAN_OBJ_BUCKET
);
329 root_color_bucket
= cur_color_bucket
= NULL
;
334 create_data (GCObject
*obj
)
336 mword
*o
= (mword
*)obj
;
337 ScanData
*res
= alloc_object_data ();
340 res
->index
= res
->low_index
= -1;
341 res
->state
= INITIAL
;
342 res
->is_bridge
= FALSE
;
343 res
->obj_state
= o
[0] & SGEN_VTABLE_BITS_MASK
;
344 res
->lock_word
= o
[1];
346 o
[0] |= SGEN_VTABLE_BITS_MASK
;
352 find_data (GCObject
*obj
)
355 mword
*o
= (mword
*)obj
;
356 if ((o
[0] & SGEN_VTABLE_BITS_MASK
) == SGEN_VTABLE_BITS_MASK
)
357 a
= (ScanData
*)o
[1];
362 clear_after_processing (void)
366 for (cur
= root_object_bucket
; cur
; cur
= cur
->next
) {
368 for (sd
= &cur
->data
[0]; sd
< cur
->next_data
; ++sd
) {
369 mword
*o
= (mword
*)sd
->obj
;
370 o
[0] &= ~SGEN_VTABLE_BITS_MASK
;
371 o
[0] |= sd
->obj_state
;
372 o
[1] = sd
->lock_word
;
378 bridge_object_forward (GCObject
*obj
)
381 mword
*o
= (mword
*)obj
;
382 if ((o
[0] & SGEN_VTABLE_BITS_MASK
) == SGEN_VTABLE_BITS_MASK
)
385 fwd
= SGEN_OBJECT_IS_FORWARDED (obj
);
386 return fwd
? fwd
: obj
;
391 safe_name_bridge (GCObject
*obj
)
393 GCVTable vt
= SGEN_LOAD_VTABLE (obj
);
394 return vt
->klass
->name
;
398 find_or_create_data (GCObject
*obj
)
400 ScanData
*entry
= find_data (obj
);
402 entry
= create_data (obj
);
414 The merge cache maps an ordered list of ColorDatas [the color_merge_array] to a single ColorData.
416 About cache bucket tuning: We tried 2/32, 2/128, 4/32, 4/128, 6/128 and 8/128.
418 The performance cost between 4/128 and 8/128 is so small since cache movement happens completely in the same cacheline,
419 making the extra space pretty much free.
421 The cost between 32 and 128 itens is minimal too, it's mostly a fixed, setup cost.
423 Memory wise, 4/32 takes 512 and 8/128 takes 8k, so it's quite reasonable.
426 #define ELEMENTS_PER_BUCKET 8
427 #define COLOR_CACHE_SIZE 128
428 static HashEntry merge_cache
[COLOR_CACHE_SIZE
][ELEMENTS_PER_BUCKET
];
429 static unsigned int hash_perturb
;
431 // If true, disable an optimization where sometimes SCC nodes are merged without a perfect check
432 static gboolean scc_precise_merge
;
435 mix_hash (uintptr_t source
)
437 unsigned int hash
= source
;
439 // The full hash determines whether two colors can be merged-- sometimes exclusively.
440 // This value changes every GC, so XORing it in before performing the hash will make the
441 // chance that two different colors will produce the same hash on successive GCs very low.
442 hash
= hash
^ hash_perturb
;
445 hash
= (((hash
* 215497) >> 16) ^ ((hash
* 1823231) + hash
));
447 // Mix in highest bits on 64-bit systems only
448 if (sizeof (source
) > 4)
449 hash
= hash
^ (source
>> 32);
457 memset (merge_cache
, 0, sizeof (merge_cache
));
459 // When using the precise merge debug option, we do not want the inconsistency caused by hash_perturb.
460 if (!scc_precise_merge
)
466 dyn_array_ptr_contains (DynPtrArray
*da
, void *x
)
469 for (i
= 0; i
< dyn_array_ptr_size (da
); ++i
)
470 if (dyn_array_ptr_get (da
, i
) == x
)
476 match_colors_estimate (DynPtrArray
*a
, DynPtrArray
*b
)
478 return dyn_array_ptr_size (a
) == dyn_array_ptr_size (b
);
483 match_colors (DynPtrArray
*a
, DynPtrArray
*b
)
486 if (dyn_array_ptr_size (a
) != dyn_array_ptr_size (b
))
489 for (i
= 0; i
< dyn_array_ptr_size (a
); ++i
) {
490 if (!dyn_array_ptr_contains (b
, dyn_array_ptr_get (a
, i
)))
496 // If scc_precise_merge, "semihits" refers to find_in_cache calls aborted because the merge array was too large.
497 // Otherwise "semihits" refers to cache hits where the match was only estimated.
498 static int cache_hits
, cache_semihits
, cache_misses
;
500 // The cache contains only non-bridged colors.
502 find_in_cache (int *insert_index
)
507 size
= dyn_array_ptr_size (&color_merge_array
);
509 /* Color equality checking is very expensive with a lot of elements, so when there are many
510 * elements we switch to a cheap comparison method which allows false positives. When false
511 * positives occur the worst that can happen is two items will be inappropriately merged
512 * and memory will be retained longer than it should be. We assume that will correct itself
513 * on the next GC (the hash_perturb mechanism increases the probability of this).
515 * Because this has *some* potential to create problems, if the user set the debug option
516 * 'enable-tarjan-precise-merge' we bail out early (and never merge SCCs with >3 colors).
518 gboolean color_merge_array_large
= size
> 3;
519 if (scc_precise_merge
&& color_merge_array_large
) {
524 unsigned int hash
= color_merge_array_hash
;
525 if (!hash
) // 0 is used to indicate an empty bucket entry
528 index
= hash
& (COLOR_CACHE_SIZE
- 1);
529 bucket
= merge_cache
[index
];
530 for (i
= 0; i
< ELEMENTS_PER_BUCKET
; ++i
) {
531 if (bucket
[i
].hash
!= hash
)
534 if (color_merge_array_large
) {
535 if (match_colors_estimate (&bucket
[i
].color
->other_colors
, &color_merge_array
)) {
537 return bucket
[i
].color
;
540 if (match_colors (&bucket
[i
].color
->other_colors
, &color_merge_array
)) {
542 return bucket
[i
].color
;
547 //move elements to the back
548 for (i
= ELEMENTS_PER_BUCKET
- 1; i
> 0; --i
)
549 bucket
[i
] = bucket
[i
- 1];
551 *insert_index
= index
;
552 bucket
[0].hash
= hash
;
556 // A color is needed for an SCC. If the SCC has bridges, the color MUST be newly allocated.
557 // If the SCC lacks bridges, the allocator MAY use the cache to merge it with an existing one.
559 new_color (gboolean has_bridges
)
563 /* XXX Try to find an equal one and return it */
565 cd
= find_in_cache (&cacheSlot
);
570 cd
= alloc_color_data ();
572 dyn_array_ptr_set_all (&cd
->other_colors
, &color_merge_array
);
575 for (int i
= 0; i
< dyn_array_ptr_size (&color_merge_array
); ++i
) {
576 ColorData
*points_to
= (ColorData
*)dyn_array_ptr_get (&color_merge_array
, i
);
577 points_to
->incoming_colors
= MIN (points_to
->incoming_colors
+ 1, INCOMING_COLORS_MAX
);
580 /* if cacheSlot >= 0, it means we prepared a given slot to receive the new color */
582 merge_cache
[cacheSlot
][0].color
= cd
;
589 register_bridge_object (GCObject
*obj
)
591 create_data (obj
)->is_bridge
= TRUE
;
595 is_opaque_object (GCObject
*obj
)
597 MonoVTable
*vt
= SGEN_LOAD_VTABLE (obj
);
598 if ((vt
->gc_bits
& SGEN_GC_BIT_BRIDGE_OPAQUE_OBJECT
) == SGEN_GC_BIT_BRIDGE_OPAQUE_OBJECT
) {
599 SGEN_LOG (6, "ignoring %s\n", m_class_get_name (vt
->klass
));
606 // Called during DFS; visits one child. If it is a candidate to be scanned, pushes it to the stacks.
608 push_object (GCObject
*obj
)
611 obj
= bridge_object_forward (obj
);
614 printf ("\t= pushing %p %s -> ", obj
, safe_name_bridge (obj
));
617 /* Object types we can ignore */
618 if (is_opaque_object (obj
)) {
625 data
= find_data (obj
);
627 /* Already marked - XXX must be done this way as the bridge themselves are alive. */
628 if (data
&& data
->state
!= INITIAL
) {
630 printf ("already marked\n");
635 /* We only care about dead objects */
636 if (!data
&& sgen_object_is_live (obj
)) {
644 printf ("pushed!\n");
648 data
= create_data (obj
);
649 g_assert (data
->state
== INITIAL
);
650 g_assert (data
->index
== -1);
651 dyn_array_ptr_push (&scan_stack
, data
);
655 #define HANDLE_PTR(ptr,obj) do { \
656 GCObject *dst = (GCObject*)*(ptr); \
657 if (dst) push_object (dst); \
660 // dfs () function's queue-children-of-object operation.
662 push_all (ScanData
*data
)
664 GCObject
*obj
= data
->obj
;
665 char *start
= (char*)obj
;
666 mword desc
= sgen_obj_get_descriptor_safe (obj
);
669 printf ("+scanning %s (%p) index %d color %p\n", safe_name_bridge (data
->obj
), data
->obj
, data
->index
, data
->color
);
672 #include "sgen/sgen-scan-object.h"
677 compute_low_index (ScanData
*data
, GCObject
*obj
)
682 obj
= bridge_object_forward (obj
);
683 other
= find_data (obj
);
686 printf ("\tcompute low %p ->%p (%s) %p (%d / %d)\n", data
->obj
, obj
, safe_name_bridge (obj
), other
, other
? other
->index
: -2, other
? other
->low_index
: -2);
691 g_assert (other
->state
!= INITIAL
);
693 if ((other
->state
== SCANNED
|| other
->state
== FINISHED_ON_STACK
) && data
->low_index
> other
->low_index
)
694 data
->low_index
= other
->low_index
;
696 /* Compute the low color */
697 if (other
->color
== NULL
)
702 color_merge_array_hash
+= mix_hash ((uintptr_t) other
->color
);
703 dyn_array_ptr_add (&color_merge_array
, other
->color
);
709 #define HANDLE_PTR(ptr,obj) do { \
710 GCObject *dst = (GCObject*)*(ptr); \
711 if (dst) compute_low_index (data, dst); \
715 compute_low (ScanData
*data
)
717 GCObject
*obj
= data
->obj
;
718 char *start
= (char*)obj
;
719 mword desc
= sgen_obj_get_descriptor_safe (obj
);
721 #include "sgen/sgen-scan-object.h"
724 // A non-bridged object needs a single color describing the current merge array.
728 ColorData
*color
= NULL
;
729 int size
= dyn_array_ptr_size (&color_merge_array
);
731 // Merge array is empty-- this SCC points to no bridged colors.
732 // This SCC can be ignored completely.
736 // Merge array has one item-- this SCC points to a single bridged color.
737 // This SCC can be forwarded to the pointed-to color.
738 else if (size
== 1) {
739 color
= (ColorData
*)dyn_array_ptr_get (&color_merge_array
, 0);
741 // This SCC gets to talk to the color allocator.
743 color
= new_color (FALSE
);
749 create_scc (ScanData
*data
)
752 gboolean found
= FALSE
;
753 gboolean found_bridge
= FALSE
;
754 ColorData
*color_data
= NULL
;
756 for (i
= dyn_array_ptr_size (&loop_stack
) - 1; i
>= 0; --i
) {
757 ScanData
*other
= (ScanData
*)dyn_array_ptr_get (&loop_stack
, i
);
758 found_bridge
|= other
->is_bridge
;
759 if (found_bridge
|| other
== data
)
764 printf ("|SCC rooted in %s (%p) has bridge %d\n", safe_name_bridge (data
->obj
), data
->obj
, found_bridge
);
765 printf ("\tpoints-to-colors: ");
766 for (int i
= 0; i
< dyn_array_ptr_size (&color_merge_array
); ++i
)
767 printf ("%p ", dyn_array_ptr_get (&color_merge_array
, i
));
770 printf ("loop stack: ");
771 for (int i
= 0; i
< dyn_array_ptr_size (&loop_stack
); ++i
) {
772 ScanData
*other
= dyn_array_ptr_get (&loop_stack
, i
);
773 printf ("(%d/%d)", other
->index
, other
->low_index
);
779 color_data
= new_color (TRUE
);
780 ++num_colors_with_bridges
;
782 color_data
= reduce_color ();
785 while (dyn_array_ptr_size (&loop_stack
) > 0) {
786 ScanData
*other
= (ScanData
*)dyn_array_ptr_pop (&loop_stack
);
789 printf ("\tmember %s (%p) index %d low-index %d color %p state %d\n", safe_name_bridge (other
->obj
), other
->obj
, other
->index
, other
->low_index
, other
->color
, other
->state
);
792 other
->color
= color_data
;
793 switch (other
->state
) {
794 case FINISHED_ON_STACK
:
795 other
->state
= FINISHED_OFF_STACK
;
797 case FINISHED_OFF_STACK
:
800 g_error ("Invalid state when building SCC %d", other
->state
);
803 if (other
->is_bridge
)
804 dyn_array_ptr_add (&color_data
->bridges
, other
->obj
);
813 for (i
= 0; i
< dyn_array_ptr_size (&color_merge_array
); ++i
) {
814 ColorData
*cd
= (ColorData
*)dyn_array_ptr_get (&color_merge_array
, i
);
815 g_assert (cd
->visited
);
818 color_merge_array_empty ();
819 found_bridge
= FALSE
;
825 g_assert (dyn_array_ptr_size (&scan_stack
) == 1);
826 g_assert (dyn_array_ptr_size (&loop_stack
) == 0);
828 color_merge_array_empty ();
830 while (dyn_array_ptr_size (&scan_stack
) > 0) {
831 ScanData
*data
= (ScanData
*)dyn_array_ptr_pop (&scan_stack
);
834 * Ignore finished objects on stack, they happen due to loops. For example:
840 * We start scanning from A and push C before B. So, after the first iteration, the scan stack will have: A C B.
841 * We then visit B, which will find C in its initial state and push again.
842 * Finally after finish with C and B, the stack will be left with "A C" and at this point C should be ignored.
844 * The above explains FINISHED_ON_STACK, to explain FINISHED_OFF_STACK, consider if the root was D, which pointed
845 * to A and C. A is processed first, leaving C on stack after that in the mentioned state.
847 if (data
->state
== FINISHED_ON_STACK
|| data
->state
== FINISHED_OFF_STACK
)
850 if (data
->state
== INITIAL
) {
851 g_assert (data
->index
== -1);
852 g_assert (data
->low_index
== -1);
854 data
->state
= SCANNED
;
855 data
->low_index
= data
->index
= object_index
++;
856 dyn_array_ptr_push (&scan_stack
, data
);
857 dyn_array_ptr_push (&loop_stack
, data
);
860 printf ("+scanning %s (%p) index %d color %p\n", safe_name_bridge (data
->obj
), data
->obj
, data
->index
, data
->color
);
865 g_assert (data
->state
== SCANNED
);
866 data
->state
= FINISHED_ON_STACK
;
869 printf ("-finishing %s (%p) index %d low-index %d color %p\n", safe_name_bridge (data
->obj
), data
->obj
, data
->index
, data
->low_index
, data
->color
);
872 /* Compute low index */
876 printf ("-finished %s (%p) index %d low-index %d color %p\n", safe_name_bridge (data
->obj
), data
->obj
, data
->index
, data
->low_index
, data
->color
);
879 if (data
->index
== data
->low_index
)
886 register_finalized_object (GCObject
*obj
)
888 g_assert (sgen_need_bridge_processing ());
889 dyn_array_ptr_push (®istered_bridges
, obj
);
895 dyn_array_ptr_empty (®istered_bridges
);
901 dyn_array_ptr_empty (&scan_stack
);
902 dyn_array_ptr_empty (&loop_stack
);
903 dyn_array_ptr_empty (®istered_bridges
);
904 free_object_buckets ();
905 free_color_buckets ();
908 num_colors_with_bridges
= 0;
913 dump_color_table (const char *why
, gboolean do_index
)
917 printf ("colors%s:\n", why
);
919 for (cur
= root_color_bucket
; cur
; cur
= cur
->next
, ++i
) {
921 for (cd
= &cur
->data
[0]; cd
< cur
->next_data
; ++cd
) {
923 printf ("\t%d(%d):", i
, cd
->api_index
);
925 printf ("\t%d: ", i
);
926 for (j
= 0; j
< dyn_array_ptr_size (&cd
->other_colors
); ++j
) {
927 printf ("%p ", dyn_array_ptr_get (&cd
->other_colors
, j
));
929 if (dyn_array_ptr_size (&cd
->bridges
)) {
930 printf (" bridges: ");
931 for (j
= 0; j
< dyn_array_ptr_size (&cd
->bridges
); ++j
) {
932 GCObject
*obj
= dyn_array_ptr_get (&cd
->bridges
, j
);
933 ScanData
*data
= find_or_create_data (obj
);
934 printf ("%d ", data
->index
);
945 step_timer (gint64
*timer
)
947 gint64 curtime
, diff
;
949 SGEN_TV_GETTIME (curtime
);
950 diff
= SGEN_TV_ELAPSED (*timer
, curtime
);
955 processing_stw_step (void)
961 if (!dyn_array_ptr_size (®istered_bridges
))
964 #if defined (DUMP_GRAPH)
965 printf ("-----------------\n");
968 SGEN_TV_GETTIME (curtime
);
970 object_alloc_init ();
973 bridge_count
= dyn_array_ptr_size (®istered_bridges
);
974 for (i
= 0; i
< bridge_count
; ++i
)
975 register_bridge_object ((GCObject
*)dyn_array_ptr_get (®istered_bridges
, i
));
977 setup_time
= step_timer (&curtime
);
979 for (i
= 0; i
< bridge_count
; ++i
) {
980 ScanData
*sd
= find_data ((GCObject
*)dyn_array_ptr_get (®istered_bridges
, i
));
981 if (sd
->state
== INITIAL
) {
982 dyn_array_ptr_push (&scan_stack
, sd
);
985 g_assert (sd
->state
== FINISHED_OFF_STACK
);
989 tarjan_time
= step_timer (&curtime
);
991 #if defined (DUMP_GRAPH)
992 printf ("----summary----\n");
993 printf ("bridges:\n");
994 for (int i
= 0; i
< bridge_count
; ++i
) {
995 ScanData
*sd
= find_data (dyn_array_ptr_get (®istered_bridges
, i
));
996 printf ("\t%s (%p) index %d color %p\n", safe_name_bridge (sd
->obj
), sd
->obj
, sd
->index
, sd
->color
);
999 dump_color_table (" after tarjan", FALSE
);
1002 clear_after_processing ();
1007 gather_xrefs (ColorData
*color
)
1010 for (i
= 0; i
< dyn_array_ptr_size (&color
->other_colors
); ++i
) {
1011 ColorData
*src
= (ColorData
*)dyn_array_ptr_get (&color
->other_colors
, i
);
1014 src
->visited
= TRUE
;
1015 if (color_visible_to_client (src
))
1016 dyn_array_ptr_add (&color_merge_array
, src
);
1023 reset_xrefs (ColorData
*color
)
1026 for (i
= 0; i
< dyn_array_ptr_size (&color
->other_colors
); ++i
) {
1027 ColorData
*src
= (ColorData
*)dyn_array_ptr_get (&color
->other_colors
, i
);
1030 src
->visited
= FALSE
;
1031 if (!color_visible_to_client (src
))
1037 processing_build_callback_data (int generation
)
1043 g_assert (bridge_processor
->num_sccs
== 0 && bridge_processor
->num_xrefs
== 0);
1044 g_assert (!bridge_processor
->api_sccs
&& !bridge_processor
->api_xrefs
);
1046 if (!dyn_array_ptr_size (®istered_bridges
))
1049 SGEN_TV_GETTIME (curtime
);
1051 /*create API objects */
1053 #if defined (DUMP_GRAPH)
1054 printf ("***** API *****\n");
1055 printf ("number of SCCs %d\n", num_colors_with_bridges
);
1058 // Count the number of SCCs visible to the client
1060 for (cur
= root_color_bucket
; cur
; cur
= cur
->next
) {
1062 for (cd
= &cur
->data
[0]; cd
< cur
->next_data
; ++cd
) {
1063 if (color_visible_to_client (cd
))
1068 /* This is a straightforward translation from colors to the bridge callback format. */
1069 MonoGCBridgeSCC
**api_sccs
= (MonoGCBridgeSCC
**)sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC
*) * num_sccs
, INTERNAL_MEM_BRIDGE_DATA
, TRUE
);
1073 // Convert visible SCCs, along with their bridged object list, to MonoGCBridgeSCCs in the client's SCC list
1074 for (cur
= root_color_bucket
; cur
; cur
= cur
->next
) {
1076 for (cd
= &cur
->data
[0]; cd
< cur
->next_data
; ++cd
) {
1077 int bridges
= dyn_array_ptr_size (&cd
->bridges
);
1078 if (!(bridges
|| bridgeless_color_is_heavy (cd
)))
1081 api_sccs
[api_index
] = (MonoGCBridgeSCC
*)sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC
) + sizeof (MonoObject
*) * bridges
, INTERNAL_MEM_BRIDGE_DATA
, TRUE
);
1082 api_sccs
[api_index
]->is_alive
= FALSE
;
1083 api_sccs
[api_index
]->num_objs
= bridges
;
1085 cd
->api_index
= api_index
;
1087 for (j
= 0; j
< bridges
; ++j
)
1088 api_sccs
[api_index
]->objs
[j
] = (MonoObject
*)dyn_array_ptr_get (&cd
->bridges
, j
);
1090 g_assert(api_index
< API_INDEX_MAX
);
1095 scc_setup_time
= step_timer (&curtime
);
1097 // Eliminate non-visible SCCs from the SCC list and redistribute xrefs
1098 for (cur
= root_color_bucket
; cur
; cur
= cur
->next
) {
1100 for (cd
= &cur
->data
[0]; cd
< cur
->next_data
; ++cd
) {
1101 if (!color_visible_to_client (cd
))
1104 color_merge_array_empty ();
1107 dyn_array_ptr_set_all (&cd
->other_colors
, &color_merge_array
);
1108 xref_count
+= dyn_array_ptr_size (&cd
->other_colors
);
1112 gather_xref_time
= step_timer (&curtime
);
1114 #if defined (DUMP_GRAPH)
1115 printf ("TOTAL XREFS %d\n", xref_count
);
1116 dump_color_table (" after xref pass", TRUE
);
1119 // Write out xrefs array
1120 MonoGCBridgeXRef
*api_xrefs
= (MonoGCBridgeXRef
*)sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeXRef
) * xref_count
, INTERNAL_MEM_BRIDGE_DATA
, TRUE
);
1122 for (cur
= root_color_bucket
; cur
; cur
= cur
->next
) {
1124 for (src
= &cur
->data
[0]; src
< cur
->next_data
; ++src
) {
1125 if (!color_visible_to_client (src
))
1128 for (j
= 0; j
< dyn_array_ptr_size (&src
->other_colors
); ++j
) {
1129 ColorData
*dest
= (ColorData
*)dyn_array_ptr_get (&src
->other_colors
, j
);
1130 g_assert (color_visible_to_client (dest
)); /* Supposedly we already eliminated all xrefs to non-visible objects. */
1132 api_xrefs
[xref_index
].src_scc_index
= src
->api_index
;
1133 api_xrefs
[xref_index
].dst_scc_index
= dest
->api_index
;
1140 g_assertf (xref_count
== xref_index
, "xref_count is %d but we added %d xrefs", xref_count
, xref_index
);
1141 xref_setup_time
= step_timer (&curtime
);
1143 #if defined (DUMP_GRAPH)
1144 printf ("---xrefs:\n");
1145 for (int i
= 0; i
< xref_count
; ++i
)
1146 printf ("\t%d -> %d\n", api_xrefs
[i
].src_scc_index
, api_xrefs
[i
].dst_scc_index
);
1149 //FIXME move half of the cleanup to before the bridge callback?
1150 bridge_processor
->num_sccs
= num_sccs
;
1151 bridge_processor
->api_sccs
= api_sccs
;
1152 bridge_processor
->num_xrefs
= xref_count
;
1153 bridge_processor
->api_xrefs
= api_xrefs
;
1157 processing_after_callback (int generation
)
1160 int bridge_count
= dyn_array_ptr_size (®istered_bridges
);
1161 int object_count
= object_data_count
;
1162 int color_count
= color_data_count
;
1163 int colors_with_bridges_count
= num_colors_with_bridges
;
1165 SGEN_TV_GETTIME (curtime
);
1170 cleanup_time
= step_timer (&curtime
);
1172 mono_trace (G_LOG_LEVEL_INFO
, MONO_TRACE_GC
, "GC_TAR_BRIDGE bridges %d objects %d opaque %d colors %d colors-bridged %d colors-visible %d xref %d cache-hit %d cache-%s %d cache-miss %d setup %.2fms tarjan %.2fms scc-setup %.2fms gather-xref %.2fms xref-setup %.2fms cleanup %.2fms",
1173 bridge_count
, object_count
, ignored_objects
,
1174 color_count
, colors_with_bridges_count
, num_sccs
, xref_count
,
1175 cache_hits
, (scc_precise_merge
? "abstain" : "semihit"), cache_semihits
, cache_misses
,
1176 setup_time
/ 10000.0f
,
1177 tarjan_time
/ 10000.0f
,
1178 scc_setup_time
/ 10000.0f
,
1179 gather_xref_time
/ 10000.0f
,
1180 xref_setup_time
/ 10000.0f
,
1181 cleanup_time
/ 10000.0f
);
1183 cache_hits
= cache_semihits
= cache_misses
= 0;
1184 ignored_objects
= 0;
1188 describe_pointer (GCObject
*obj
)
1190 // HashEntry *entry;
1193 for (i
= 0; i
< dyn_array_ptr_size (®istered_bridges
); ++i
) {
1194 if (obj
== dyn_array_ptr_get (®istered_bridges
, i
)) {
1195 printf ("Pointer is a registered bridge object.\n");
1200 // entry = sgen_hash_table_lookup (&hash_table, obj);
1204 // printf ("Bridge hash table entry %p:\n", entry);
1205 // printf (" is bridge: %d\n", (int)entry->is_bridge);
1206 // printf (" is visited: %d\n", (int)entry->is_visited);
1210 set_config (const SgenBridgeProcessorConfig
*config
)
1212 if (config
->scc_precise_merge
) {
1214 scc_precise_merge
= TRUE
;
1219 sgen_tarjan_bridge_init (SgenBridgeProcessor
*collector
)
1221 collector
->reset_data
= reset_data
;
1222 collector
->processing_stw_step
= processing_stw_step
;
1223 collector
->processing_build_callback_data
= processing_build_callback_data
;
1224 collector
->processing_after_callback
= processing_after_callback
;
1225 collector
->class_kind
= class_kind
;
1226 collector
->register_finalized_object
= register_finalized_object
;
1227 collector
->describe_pointer
= describe_pointer
;
1228 collector
->set_config
= set_config
;
1230 sgen_register_fixed_internal_mem_type (INTERNAL_MEM_TARJAN_OBJ_BUCKET
, BUCKET_SIZE
);
1231 g_assert (sizeof (ObjectBucket
) <= BUCKET_SIZE
);
1232 g_assert (sizeof (ColorBucket
) <= BUCKET_SIZE
);
1233 g_assert (API_INDEX_BITS
+ INCOMING_COLORS_BITS
<= 31);
1234 bridge_processor
= collector
;