2 * sgen-bridge.c: Simple generational GC.
4 * Copyright 2011 Novell, Inc (http://www.novell.com)
5 * Copyright 2011 Xamarin Inc (http://www.xamarin.com)
6 * Copyright 2001-2003 Ximian, Inc
7 * Copyright 2003-2010 Novell, Inc.
9 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
19 #include "sgen/sgen-gc.h"
20 #include "sgen-bridge-internals.h"
21 #include "sgen/sgen-hash-table.h"
22 #include "sgen/sgen-qsort.h"
23 #include "sgen/sgen-client.h"
24 #include "tabledefs.h"
25 #include "utils/mono-logger-internals.h"
27 #define OPTIMIZATION_COPY
28 #define OPTIMIZATION_FORWARD
29 #define OPTIMIZATION_SINGLETON_DYN_ARRAY
30 #include "sgen-dynarray.h"
34 //#define TEST_NEW_XREFS
37 #if !defined(NEW_XREFS) || defined(TEST_NEW_XREFS)
42 #define XREFS new_xrefs
44 #define XREFS old_xrefs
48 * Bridge data for a single managed object
50 * FIXME: Optimizations:
52 * Don't allocate a srcs array for just one source. Most objects have
53 * just one source, so use the srcs pointer itself.
55 typedef struct _HashEntry
{
60 guint32 is_visited
: 1;
61 guint32 finishing_time
: 31;
62 struct _HashEntry
*forwarded_to
;
65 // Index in sccs array of SCC this object was folded into
70 // "Source" managed objects pointing at this destination
77 } HashEntryWithAccounting
;
79 // The graph of managed objects/HashEntries is reduced to a graph of strongly connected components
84 // How many bridged objects does this SCC hold references to?
85 int num_bridge_entries
;
90 * Index in global sccs array of SCCs holding pointers to this SCC
92 * New and old xrefs are typically mutually exclusive. Only when TEST_NEW_XREFS is
93 * enabled we do both, and compare the results. This should only be done for
94 * debugging, obviously.
97 DynIntArray old_xrefs
; /* these are incoming, not outgoing */
100 DynIntArray new_xrefs
;
104 static char *dump_prefix
= NULL
;
106 // Maps managed objects to corresponding HashEntry stricts
107 static SgenHashTable hash_table
= SGEN_HASH_TABLE_INIT (INTERNAL_MEM_BRIDGE_HASH_TABLE
, INTERNAL_MEM_BRIDGE_HASH_TABLE_ENTRY
, sizeof (HashEntry
), mono_aligned_addr_hash
, NULL
);
109 static guint32 current_time
;
111 static gboolean bridge_accounting_enabled
= FALSE
;
113 static SgenBridgeProcessor
*bridge_processor
;
120 dyn_array_scc_init (DynSCCArray
*da
)
122 dyn_array_init (&da
->array
);
126 dyn_array_scc_uninit (DynSCCArray
*da
)
128 dyn_array_uninit (&da
->array
, sizeof (SCC
));
132 dyn_array_scc_size (DynSCCArray
*da
)
134 return da
->array
.size
;
138 dyn_array_scc_add (DynSCCArray
*da
)
140 return (SCC
*)dyn_array_add (&da
->array
, sizeof (SCC
));
144 dyn_array_scc_get_ptr (DynSCCArray
*da
, int x
)
146 return &((SCC
*)da
->array
.data
)[x
];
151 static DynIntArray merge_array
;
155 dyn_array_int_contains (DynIntArray
*da
, int x
)
158 for (i
= 0; i
< dyn_array_int_size (da
); ++i
)
159 if (dyn_array_int_get (da
, i
) == x
)
166 set_config (const SgenBridgeProcessorConfig
*config
)
168 if (config
->accounting
) {
169 SgenHashTable table
= SGEN_HASH_TABLE_INIT (INTERNAL_MEM_BRIDGE_HASH_TABLE
, INTERNAL_MEM_BRIDGE_HASH_TABLE_ENTRY
, sizeof (HashEntryWithAccounting
), mono_aligned_addr_hash
, NULL
);
170 bridge_accounting_enabled
= TRUE
;
173 if (config
->dump_prefix
) {
174 dump_prefix
= strdup (config
->dump_prefix
);
178 static MonoGCBridgeObjectKind
179 class_kind (MonoClass
*klass
)
181 MonoGCBridgeObjectKind res
= bridge_callbacks
.bridge_class_kind (klass
);
183 /* If it's a bridge, nothing we can do about it. */
184 if (res
== GC_BRIDGE_TRANSPARENT_BRIDGE_CLASS
|| res
== GC_BRIDGE_OPAQUE_BRIDGE_CLASS
)
187 /* Non bridge classes with no pointers will never point to a bridge, so we can savely ignore them. */
188 if (!klass
->has_references
) {
189 SGEN_LOG (6, "class %s is opaque\n", klass
->name
);
190 return GC_BRIDGE_OPAQUE_CLASS
;
193 /* Some arrays can be ignored */
194 if (klass
->rank
== 1) {
195 MonoClass
*elem_class
= klass
->element_class
;
197 /* FIXME the bridge check can be quite expensive, cache it at the class level. */
198 /* An array of a sealed type that is not a bridge will never get to a bridge */
199 if ((elem_class
->flags
& TYPE_ATTRIBUTE_SEALED
) && !elem_class
->has_references
&& !bridge_callbacks
.bridge_class_kind (elem_class
)) {
200 SGEN_LOG (6, "class %s is opaque\n", klass
->name
);
201 return GC_BRIDGE_OPAQUE_CLASS
;
205 return GC_BRIDGE_TRANSPARENT_CLASS
;
209 get_hash_entry (MonoObject
*obj
, gboolean
*existing
)
211 HashEntry
*entry
= (HashEntry
*)sgen_hash_table_lookup (&hash_table
, obj
);
222 memset (&new_entry
, 0, sizeof (HashEntry
));
224 dyn_array_ptr_init (&new_entry
.srcs
);
225 new_entry
.v
.dfs1
.finishing_time
= 0;
227 sgen_hash_table_replace (&hash_table
, obj
, &new_entry
, NULL
);
229 return (HashEntry
*)sgen_hash_table_lookup (&hash_table
, obj
);
233 add_source (HashEntry
*entry
, HashEntry
*src
)
235 dyn_array_ptr_add (&entry
->srcs
, src
);
241 MonoObject
*obj G_GNUC_UNUSED
;
246 SGEN_HASH_TABLE_FOREACH (&hash_table
, MonoObject
*, obj
, HashEntry
*, entry
) {
247 int entry_size
= dyn_array_ptr_size (&entry
->srcs
);
248 total_srcs
+= entry_size
;
249 if (entry_size
> max_srcs
)
250 max_srcs
= entry_size
;
251 dyn_array_ptr_uninit (&entry
->srcs
);
252 } SGEN_HASH_TABLE_FOREACH_END
;
254 sgen_hash_table_clean (&hash_table
);
256 dyn_array_int_uninit (&merge_array
);
257 //g_print ("total srcs %d - max %d\n", total_srcs, max_srcs);
261 register_bridge_object (MonoObject
*obj
)
263 HashEntry
*entry
= get_hash_entry (obj
, NULL
);
264 entry
->is_bridge
= TRUE
;
269 register_finishing_time (HashEntry
*entry
, guint32 t
)
271 g_assert (entry
->v
.dfs1
.finishing_time
== 0);
272 /* finishing_time has 31 bits, so it must be within signed int32 range. */
273 g_assert (t
> 0 && t
<= G_MAXINT32
);
274 entry
->v
.dfs1
.finishing_time
= t
;
277 static int ignored_objects
;
280 is_opaque_object (MonoObject
*obj
)
282 if ((obj
->vtable
->gc_bits
& SGEN_GC_BIT_BRIDGE_OPAQUE_OBJECT
) == SGEN_GC_BIT_BRIDGE_OPAQUE_OBJECT
) {
283 SGEN_LOG (6, "ignoring %s\n", obj
->vtable
->klass
->name
);
291 object_needs_expansion (MonoObject
**objp
)
293 MonoObject
*obj
= *objp
;
294 MonoObject
*fwd
= SGEN_OBJECT_IS_FORWARDED (obj
);
297 if (is_opaque_object (fwd
))
299 return sgen_hash_table_lookup (&hash_table
, fwd
) != NULL
;
301 if (is_opaque_object (obj
))
303 if (!sgen_object_is_live (obj
))
305 return sgen_hash_table_lookup (&hash_table
, obj
) != NULL
;
309 follow_forward (HashEntry
*entry
)
311 #ifdef OPTIMIZATION_FORWARD
312 while (entry
->v
.dfs1
.forwarded_to
) {
313 HashEntry
*next
= entry
->v
.dfs1
.forwarded_to
;
314 if (next
->v
.dfs1
.forwarded_to
)
315 entry
->v
.dfs1
.forwarded_to
= next
->v
.dfs1
.forwarded_to
;
319 g_assert (!entry
->v
.dfs1
.forwarded_to
);
324 static DynPtrArray registered_bridges
;
325 static DynPtrArray dfs_stack
;
327 static int dfs1_passes
, dfs2_passes
;
330 * DFS1 maintains a stack, where each two entries are effectively one entry. (FIXME:
331 * Optimize this via pointer tagging.) There are two different types of entries:
333 * entry, src: entry needs to be expanded via scanning, and linked to from src
334 * NULL, entry: entry has already been expanded and needs to be finished
338 #define HANDLE_PTR(ptr,obj) do { \
339 GCObject *dst = (GCObject*)*(ptr); \
340 if (dst && object_needs_expansion (&dst)) { \
342 dyn_array_ptr_push (&dfs_stack, obj_entry); \
343 dyn_array_ptr_push (&dfs_stack, follow_forward (get_hash_entry (dst, NULL))); \
348 dfs1 (HashEntry
*obj_entry
)
351 g_assert (dyn_array_ptr_size (&dfs_stack
) == 0);
353 dyn_array_ptr_push (&dfs_stack
, NULL
);
354 dyn_array_ptr_push (&dfs_stack
, obj_entry
);
361 obj_entry
= (HashEntry
*)dyn_array_ptr_pop (&dfs_stack
);
363 /* obj_entry needs to be expanded */
364 src
= (HashEntry
*)dyn_array_ptr_pop (&dfs_stack
);
367 g_assert (!src
->v
.dfs1
.forwarded_to
);
369 obj_entry
= follow_forward (obj_entry
);
372 g_assert (!obj_entry
->v
.dfs1
.forwarded_to
);
373 obj
= sgen_hash_table_key_for_value_pointer (obj_entry
);
376 if (!obj_entry
->v
.dfs1
.is_visited
) {
378 mword desc
= sgen_obj_get_descriptor_safe (obj
);
380 obj_entry
->v
.dfs1
.is_visited
= 1;
382 /* push the finishing entry on the stack */
383 dyn_array_ptr_push (&dfs_stack
, obj_entry
);
384 dyn_array_ptr_push (&dfs_stack
, NULL
);
386 #include "sgen/sgen-scan-object.h"
389 * We can remove non-bridge objects with a single outgoing
390 * link by forwarding links going to it.
392 * This is the first time we've encountered this object, so
393 * no links to it have yet been added. We'll keep it that
394 * way by setting the forward pointer, and instead of
395 * continuing processing this object, we start over with the
396 * object it points to.
398 #ifdef OPTIMIZATION_FORWARD
399 if (!obj_entry
->is_bridge
&& num_links
== 1) {
400 HashEntry
*dst_entry
= (HashEntry
*)dyn_array_ptr_pop (&dfs_stack
);
401 HashEntry
*obj_entry_again
= (HashEntry
*)dyn_array_ptr_pop (&dfs_stack
);
402 g_assert (obj_entry_again
== obj_entry
);
403 g_assert (!dst_entry
->v
.dfs1
.forwarded_to
);
404 if (obj_entry
!= dst_entry
) {
405 obj_entry
->v
.dfs1
.forwarded_to
= dst_entry
;
406 obj_entry
= dst_entry
;
414 //g_print ("link %s -> %s\n", sgen_safe_name (src->obj), sgen_safe_name (obj));
415 g_assert (!obj_entry
->v
.dfs1
.forwarded_to
);
416 add_source (obj_entry
, src
);
418 //g_print ("starting with %s\n", sgen_safe_name (obj));
421 /* obj_entry needs to be finished */
423 obj_entry
= (HashEntry
*)dyn_array_ptr_pop (&dfs_stack
);
425 //g_print ("finish %s\n", sgen_safe_name (obj_entry->obj));
426 register_finishing_time (obj_entry
, ++current_time
);
428 } while (dyn_array_ptr_size (&dfs_stack
) > 0);
431 static DynSCCArray sccs
;
432 static SCC
*current_scc
;
435 * At the end of bridge processing we need to end up with an (acyclyc) graph of bridge
436 * object SCCs, where the links between the nodes (each one an SCC) in that graph represent
437 * the presence of a direct or indirect link between those SCCs. An example:
442 * A -> B -> c -> e -> F
444 * A, B, D and F are SCCs that contain bridge objects, c and e don't contain bridge objects.
445 * The graph we need to produce from this is:
452 * Note that we don't need to produce an edge from A to F. It's sufficient that F is
453 * indirectly reachable from A.
455 * The old algorithm would create a set, for each SCC, of bridge SCCs that can reach it,
456 * directly or indirectly, by merging the ones sets for those that reach it directly. The
457 * sets it would build up are these:
466 * The merge operations on these sets turned out to be huge time sinks.
468 * The new algorithm proceeds in two passes: During DFS2, it only builds up the sets of SCCs
469 * that directly point to each SCC:
478 * This is the adjacency list for the SCC graph, in other words. In a separate step
479 * afterwards, it does a depth-first traversal of that graph, for each bridge node, to get
480 * to the final list. It uses a flag to avoid traversing any node twice.
483 scc_add_xref (SCC
*src
, SCC
*dst
)
485 g_assert (src
!= dst
);
486 g_assert (src
->index
!= dst
->index
);
490 * FIXME: Right now we don't even unique the direct ancestors, but just add to the
491 * list. Doing a containment check slows this algorithm down to almost the speed of
492 * the old one. Use the flag instead!
494 dyn_array_int_add (&dst
->new_xrefs
, src
->index
);
498 if (dyn_array_int_is_copy (&dst
->old_xrefs
)) {
500 dyn_array_int_ensure_independent (&dst
->old_xrefs
);
501 for (i
= 0; i
< dyn_array_int_size (&dst
->old_xrefs
); ++i
) {
502 int j
= dyn_array_int_get (&dst
->old_xrefs
, i
);
503 SCC
*bridge_scc
= dyn_array_scc_get_ptr (&sccs
, j
);
504 g_assert (!bridge_scc
->flag
);
505 bridge_scc
->flag
= TRUE
;
509 if (src
->num_bridge_entries
) {
513 dyn_array_int_add (&dst
->old_xrefs
, src
->index
);
514 #ifdef OPTIMIZATION_COPY
515 } else if (dyn_array_int_size (&dst
->old_xrefs
) == 0) {
516 dyn_array_int_copy (&dst
->old_xrefs
, &src
->old_xrefs
);
520 for (i
= 0; i
< dyn_array_int_size (&src
->old_xrefs
); ++i
) {
521 int j
= dyn_array_int_get (&src
->old_xrefs
, i
);
522 SCC
*bridge_scc
= dyn_array_scc_get_ptr (&sccs
, j
);
523 g_assert (bridge_scc
->num_bridge_entries
);
524 if (!bridge_scc
->flag
) {
525 bridge_scc
->flag
= TRUE
;
526 dyn_array_int_add (&dst
->old_xrefs
, j
);
534 scc_add_entry (SCC
*scc
, HashEntry
*entry
)
536 g_assert (entry
->v
.dfs2
.scc_index
< 0);
537 entry
->v
.dfs2
.scc_index
= scc
->index
;
538 if (entry
->is_bridge
)
539 ++scc
->num_bridge_entries
;
543 dfs2 (HashEntry
*entry
)
547 g_assert (dyn_array_ptr_size (&dfs_stack
) == 0);
549 dyn_array_ptr_push (&dfs_stack
, entry
);
552 entry
= (HashEntry
*)dyn_array_ptr_pop (&dfs_stack
);
555 if (entry
->v
.dfs2
.scc_index
>= 0) {
556 if (entry
->v
.dfs2
.scc_index
!= current_scc
->index
)
557 scc_add_xref (dyn_array_scc_get_ptr (&sccs
, entry
->v
.dfs2
.scc_index
), current_scc
);
561 scc_add_entry (current_scc
, entry
);
563 for (i
= 0; i
< dyn_array_ptr_size (&entry
->srcs
); ++i
)
564 dyn_array_ptr_push (&dfs_stack
, dyn_array_ptr_get (&entry
->srcs
, i
));
565 } while (dyn_array_ptr_size (&dfs_stack
) > 0);
568 /* If xrefs is a copy then we haven't set a single flag. */
569 if (dyn_array_int_is_copy (¤t_scc
->old_xrefs
))
571 for (i
= 0; i
< dyn_array_int_size (¤t_scc
->old_xrefs
); ++i
) {
572 int j
= dyn_array_int_get (¤t_scc
->old_xrefs
, i
);
573 SCC
*bridge_scc
= dyn_array_scc_get_ptr (&sccs
, j
);
574 g_assert (bridge_scc
->flag
);
575 bridge_scc
->flag
= FALSE
;
582 gather_xrefs (SCC
*scc
)
585 for (i
= 0; i
< dyn_array_int_size (&scc
->new_xrefs
); ++i
) {
586 int index
= dyn_array_int_get (&scc
->new_xrefs
, i
);
587 SCC
*src
= dyn_array_scc_get_ptr (&sccs
, index
);
591 if (src
->num_bridge_entries
)
592 dyn_array_int_add (&merge_array
, index
);
599 reset_flags (SCC
*scc
)
602 for (i
= 0; i
< dyn_array_int_size (&scc
->new_xrefs
); ++i
) {
603 int index
= dyn_array_int_get (&scc
->new_xrefs
, i
);
604 SCC
*src
= dyn_array_scc_get_ptr (&sccs
, index
);
608 if (!src
->num_bridge_entries
)
617 static int counter
= 0;
621 size_t prefix_len
= strlen (dump_prefix
);
622 char *filename
= (char *)alloca (prefix_len
+ 64);
626 sprintf (filename
, "%s.%d.gexf", dump_prefix
, counter
++);
627 file
= fopen (filename
, "w");
630 fprintf (stderr
, "Warning: Could not open bridge dump file `%s` for writing: %s\n", filename
, strerror (errno
));
634 fprintf (file
, "<gexf xmlns=\"http://www.gexf.net/1.2draft\" xmlns:xsi=\"http://www.w3.org/2001/XMLSchema-instance\" xsi:schemaLocation=\"http://www.gexf.net/1.2draft http://www.gexf.net/1.2draft/gexf.xsd\" version=\"1.2\">\n");
636 fprintf (file
, "<graph defaultedgetype=\"directed\">\n"
637 "<attributes class=\"node\">\n"
638 "<attribute id=\"0\" title=\"class\" type=\"string\"/>\n"
639 "<attribute id=\"1\" title=\"bridge\" type=\"boolean\"/>\n"
642 fprintf (file
, "<nodes>\n");
643 SGEN_HASH_TABLE_FOREACH (&hash_table
, MonoObject
*, obj
, HashEntry
*, entry
) {
644 MonoVTable
*vt
= SGEN_LOAD_VTABLE (obj
);
645 fprintf (file
, "<node id=\"%p\"><attvalues><attvalue for=\"0\" value=\"%s.%s\"/><attvalue for=\"1\" value=\"%s\"/></attvalues></node>\n",
646 obj
, vt
->klass
->name_space
, vt
->klass
->name
, entry
->is_bridge
? "true" : "false");
647 } SGEN_HASH_TABLE_FOREACH_END
;
648 fprintf (file
, "</nodes>\n");
650 fprintf (file
, "<edges>\n");
651 SGEN_HASH_TABLE_FOREACH (&hash_table
, MonoObject
*, obj
, HashEntry
*, entry
) {
653 for (i
= 0; i
< dyn_array_ptr_size (&entry
->srcs
); ++i
) {
654 HashEntry
*src
= (HashEntry
*)dyn_array_ptr_get (&entry
->srcs
, i
);
655 fprintf (file
, "<edge id=\"%d\" source=\"%p\" target=\"%p\"/>\n", edge_id
++, sgen_hash_table_key_for_value_pointer (src
), obj
);
657 } SGEN_HASH_TABLE_FOREACH_END
;
658 fprintf (file
, "</edges>\n");
660 fprintf (file
, "</graph></gexf>\n");
666 compare_hash_entries (const HashEntry
*e1
, const HashEntry
*e2
)
668 /* We can cast to signed int here because finishing_time has only 31 bits. */
669 return (gint32
)e2
->v
.dfs1
.finishing_time
- (gint32
)e1
->v
.dfs1
.finishing_time
;
672 DEF_QSORT_INLINE(hash_entries
, HashEntry
*, compare_hash_entries
)
674 static gint64 step_1
, step_2
, step_3
, step_4
, step_5
, step_6
;
675 static int fist_pass_links
, second_pass_links
, sccs_links
;
676 static int max_sccs_links
= 0;
679 register_finalized_object (GCObject
*obj
)
681 g_assert (sgen_need_bridge_processing ());
682 dyn_array_ptr_push (®istered_bridges
, obj
);
688 dyn_array_ptr_empty (®istered_bridges
);
692 processing_stw_step (void)
696 MonoObject
*obj G_GNUC_UNUSED
;
698 SGEN_TV_DECLARE (atv
);
699 SGEN_TV_DECLARE (btv
);
701 if (!dyn_array_ptr_size (®istered_bridges
))
704 SGEN_TV_GETTIME (btv
);
708 dyn_array_ptr_init (&dfs_stack
);
709 dyn_array_int_init (&merge_array
);
713 First we insert all bridges into the hash table and then we do dfs1.
715 It must be done in 2 steps since the bridge arrays doesn't come in reverse topological order,
716 which means that we can have entry N pointing to entry N + 1.
718 If we dfs1 entry N before N + 1 is registered we'll not consider N + 1 for this bridge
719 pass and not create the required xref between the two.
721 bridge_count
= dyn_array_ptr_size (®istered_bridges
);
722 for (i
= 0; i
< bridge_count
; ++i
)
723 register_bridge_object ((MonoObject
*)dyn_array_ptr_get (®istered_bridges
, i
));
725 for (i
= 0; i
< bridge_count
; ++i
)
726 dfs1 (get_hash_entry ((MonoObject
*)dyn_array_ptr_get (®istered_bridges
, i
), NULL
));
728 /* Remove all forwarded objects. */
729 SGEN_HASH_TABLE_FOREACH (&hash_table
, MonoObject
*, obj
, HashEntry
*, entry
) {
730 if (entry
->v
.dfs1
.forwarded_to
) {
731 g_assert (dyn_array_ptr_size (&entry
->srcs
) == 0);
732 SGEN_HASH_TABLE_FOREACH_REMOVE (TRUE
);
735 } SGEN_HASH_TABLE_FOREACH_END
;
737 SGEN_TV_GETTIME (atv
);
738 step_2
= SGEN_TV_ELAPSED (btv
, atv
);
744 static int num_registered_bridges
, hash_table_size
;
747 processing_build_callback_data (int generation
)
750 int num_sccs
, num_xrefs
;
751 int max_entries
, max_xrefs
;
752 MonoObject
*obj G_GNUC_UNUSED
;
754 HashEntry
**all_entries
;
755 MonoGCBridgeSCC
**api_sccs
;
756 MonoGCBridgeXRef
*api_xrefs
;
757 SGEN_TV_DECLARE (atv
);
758 SGEN_TV_DECLARE (btv
);
760 g_assert (bridge_processor
->num_sccs
== 0 && bridge_processor
->num_xrefs
== 0);
761 g_assert (!bridge_processor
->api_sccs
&& !bridge_processor
->api_xrefs
);
763 if (!dyn_array_ptr_size (®istered_bridges
))
766 g_assert (bridge_processing_in_progress
);
768 SGEN_TV_GETTIME (atv
);
770 /* alloc and fill array of all entries */
772 all_entries
= (HashEntry
**)sgen_alloc_internal_dynamic (sizeof (HashEntry
*) * hash_table
.num_entries
, INTERNAL_MEM_BRIDGE_DATA
, TRUE
);
775 SGEN_HASH_TABLE_FOREACH (&hash_table
, MonoObject
*, obj
, HashEntry
*, entry
) {
776 g_assert (entry
->v
.dfs1
.finishing_time
> 0);
777 all_entries
[j
++] = entry
;
778 fist_pass_links
+= dyn_array_ptr_size (&entry
->srcs
);
779 } SGEN_HASH_TABLE_FOREACH_END
;
780 g_assert (j
== hash_table
.num_entries
);
781 hash_table_size
= hash_table
.num_entries
;
783 /* sort array according to decreasing finishing time */
784 qsort_hash_entries (all_entries
, hash_table
.num_entries
);
786 SGEN_HASH_TABLE_FOREACH (&hash_table
, MonoObject
*, obj
, HashEntry
*, entry
) {
787 entry
->v
.dfs2
.scc_index
= -1;
788 } SGEN_HASH_TABLE_FOREACH_END
;
790 SGEN_TV_GETTIME (btv
);
791 step_3
= SGEN_TV_ELAPSED (atv
, btv
);
793 /* second DFS pass */
795 dyn_array_scc_init (&sccs
);
796 for (i
= 0; i
< hash_table
.num_entries
; ++i
) {
797 HashEntry
*entry
= all_entries
[i
];
798 if (entry
->v
.dfs2
.scc_index
< 0) {
799 int index
= dyn_array_scc_size (&sccs
);
800 current_scc
= dyn_array_scc_add (&sccs
);
801 current_scc
->index
= index
;
802 current_scc
->num_bridge_entries
= 0;
804 current_scc
->flag
= FALSE
;
805 dyn_array_int_init (¤t_scc
->new_xrefs
);
808 dyn_array_int_init (¤t_scc
->old_xrefs
);
810 current_scc
->api_index
= -1;
816 * If a node has only one incoming edge, we just copy the source's
817 * xrefs array, effectively removing the source from the graph.
818 * This takes care of long linked lists.
820 if (!current_scc
->num_bridge_entries
&& dyn_array_int_size (¤t_scc
->new_xrefs
) == 1) {
822 j
= dyn_array_int_get (¤t_scc
->new_xrefs
, 0);
823 src
= dyn_array_scc_get_ptr (&sccs
, j
);
824 if (src
->num_bridge_entries
)
825 dyn_array_int_set (¤t_scc
->new_xrefs
, 0, j
);
827 dyn_array_int_copy (¤t_scc
->new_xrefs
, &src
->new_xrefs
);
834 #ifdef TEST_NEW_XREFS
835 for (j
= 0; j
< dyn_array_scc_size (&sccs
); ++j
) {
836 SCC
*scc
= dyn_array_scc_get_ptr (&sccs
, j
);
837 g_assert (!scc
->flag
);
841 for (i
= 0; i
< dyn_array_scc_size (&sccs
); ++i
) {
842 SCC
*scc
= dyn_array_scc_get_ptr (&sccs
, i
);
843 g_assert (scc
->index
== i
);
844 if (!scc
->num_bridge_entries
)
847 dyn_array_int_empty (&merge_array
);
850 dyn_array_int_copy (&scc
->new_xrefs
, &merge_array
);
851 dyn_array_int_ensure_independent (&scc
->new_xrefs
);
853 #ifdef TEST_NEW_XREFS
854 for (j
= 0; j
< dyn_array_scc_size (&sccs
); ++j
) {
855 SCC
*scc
= dyn_array_scc_get_ptr (&sccs
, j
);
856 g_assert (!scc
->flag
);
861 #ifdef TEST_NEW_XREFS
862 for (i
= 0; i
< dyn_array_scc_size (&sccs
); ++i
) {
863 SCC
*scc
= dyn_array_scc_get_ptr (&sccs
, i
);
864 g_assert (scc
->index
== i
);
865 if (!scc
->num_bridge_entries
)
868 g_assert (dyn_array_int_size (&scc
->new_xrefs
) == dyn_array_int_size (&scc
->old_xrefs
));
869 for (j
= 0; j
< dyn_array_int_size (&scc
->new_xrefs
); ++j
)
870 g_assert (dyn_array_int_contains (&scc
->old_xrefs
, dyn_array_int_get (&scc
->new_xrefs
, j
)));
876 * Compute the weight of each object. The weight of an object is its size plus the size of all
877 * objects it points do. When the an object is pointed by multiple objects we distribute it's weight
878 * equally among them. This distribution gives a rough estimate of the real impact of making the object
881 * The reasoning for this model is that complex graphs with single roots will have a bridge with very high
882 * value in comparison to others.
884 * The all_entries array has all objects topologically sorted. To correctly propagate the weights it must be
885 * done in reverse topological order - so we calculate the weight of the pointed-to objects before processing
886 * pointer-from objects.
888 * We log those objects in the opposite order for no particular reason. The other constrain is that it should use the same
889 * direction as the other logging loop that records live/dead information.
891 if (bridge_accounting_enabled
) {
892 for (i
= hash_table
.num_entries
- 1; i
>= 0; --i
) {
894 HashEntryWithAccounting
*entry
= (HashEntryWithAccounting
*)all_entries
[i
];
896 entry
->weight
+= (double)sgen_safe_object_get_size (sgen_hash_table_key_for_value_pointer (entry
));
897 w
= entry
->weight
/ dyn_array_ptr_size (&entry
->entry
.srcs
);
898 for (j
= 0; j
< dyn_array_ptr_size (&entry
->entry
.srcs
); ++j
) {
899 HashEntryWithAccounting
*other
= (HashEntryWithAccounting
*)dyn_array_ptr_get (&entry
->entry
.srcs
, j
);
903 for (i
= 0; i
< hash_table
.num_entries
; ++i
) {
904 HashEntryWithAccounting
*entry
= (HashEntryWithAccounting
*)all_entries
[i
];
905 if (entry
->entry
.is_bridge
) {
906 MonoObject
*obj
= sgen_hash_table_key_for_value_pointer (entry
);
907 MonoClass
*klass
= SGEN_LOAD_VTABLE (obj
)->klass
;
908 mono_trace (G_LOG_LEVEL_INFO
, MONO_TRACE_GC
, "OBJECT %s::%s (%p) weight %f", klass
->name_space
, klass
->name
, obj
, entry
->weight
);
913 for (i
= 0; i
< hash_table
.num_entries
; ++i
) {
914 HashEntry
*entry
= all_entries
[i
];
915 second_pass_links
+= dyn_array_ptr_size (&entry
->srcs
);
918 SGEN_TV_GETTIME (atv
);
919 step_4
= SGEN_TV_ELAPSED (btv
, atv
);
921 //g_print ("%d sccs\n", sccs.size);
923 dyn_array_ptr_uninit (&dfs_stack
);
925 /* init data for callback */
928 for (i
= 0; i
< dyn_array_scc_size (&sccs
); ++i
) {
929 SCC
*scc
= dyn_array_scc_get_ptr (&sccs
, i
);
930 g_assert (scc
->index
== i
);
931 if (scc
->num_bridge_entries
)
933 sccs_links
+= dyn_array_int_size (&scc
->XREFS
);
934 max_sccs_links
= MAX (max_sccs_links
, dyn_array_int_size (&scc
->XREFS
));
937 api_sccs
= (MonoGCBridgeSCC
**)sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC
*) * num_sccs
, INTERNAL_MEM_BRIDGE_DATA
, TRUE
);
940 for (i
= 0; i
< dyn_array_scc_size (&sccs
); ++i
) {
941 SCC
*scc
= dyn_array_scc_get_ptr (&sccs
, i
);
942 if (!scc
->num_bridge_entries
)
945 api_sccs
[j
] = (MonoGCBridgeSCC
*)sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC
) + sizeof (MonoObject
*) * scc
->num_bridge_entries
, INTERNAL_MEM_BRIDGE_DATA
, TRUE
);
946 api_sccs
[j
]->is_alive
= FALSE
;
947 api_sccs
[j
]->num_objs
= scc
->num_bridge_entries
;
948 scc
->num_bridge_entries
= 0;
949 scc
->api_index
= j
++;
951 num_xrefs
+= dyn_array_int_size (&scc
->XREFS
);
954 SGEN_HASH_TABLE_FOREACH (&hash_table
, MonoObject
*, obj
, HashEntry
*, entry
) {
955 if (entry
->is_bridge
) {
956 SCC
*scc
= dyn_array_scc_get_ptr (&sccs
, entry
->v
.dfs2
.scc_index
);
957 api_sccs
[scc
->api_index
]->objs
[scc
->num_bridge_entries
++] = sgen_hash_table_key_for_value_pointer (entry
);
959 } SGEN_HASH_TABLE_FOREACH_END
;
961 api_xrefs
= (MonoGCBridgeXRef
*)sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeXRef
) * num_xrefs
, INTERNAL_MEM_BRIDGE_DATA
, TRUE
);
963 for (i
= 0; i
< dyn_array_scc_size (&sccs
); ++i
) {
965 SCC
*scc
= dyn_array_scc_get_ptr (&sccs
, i
);
966 if (!scc
->num_bridge_entries
)
968 for (k
= 0; k
< dyn_array_int_size (&scc
->XREFS
); ++k
) {
969 SCC
*src_scc
= dyn_array_scc_get_ptr (&sccs
, dyn_array_int_get (&scc
->XREFS
, k
));
970 if (!src_scc
->num_bridge_entries
)
972 api_xrefs
[j
].src_scc_index
= src_scc
->api_index
;
973 api_xrefs
[j
].dst_scc_index
= scc
->api_index
;
978 SGEN_TV_GETTIME (btv
);
979 step_5
= SGEN_TV_ELAPSED (atv
, btv
);
984 max_entries
= max_xrefs
= 0;
985 for (i
= 0; i
< dyn_array_scc_size (&sccs
); ++i
) {
986 SCC
*scc
= dyn_array_scc_get_ptr (&sccs
, i
);
987 if (scc
->num_bridge_entries
)
989 if (scc
->num_bridge_entries
> max_entries
)
990 max_entries
= scc
->num_bridge_entries
;
991 if (dyn_array_int_size (&scc
->XREFS
) > max_xrefs
)
992 max_xrefs
= dyn_array_int_size (&scc
->XREFS
);
994 dyn_array_int_uninit (&scc
->new_xrefs
);
997 dyn_array_int_uninit (&scc
->old_xrefs
);
1001 dyn_array_scc_uninit (&sccs
);
1003 sgen_free_internal_dynamic (all_entries
, sizeof (HashEntry
*) * hash_table
.num_entries
, INTERNAL_MEM_BRIDGE_DATA
);
1006 /* Empty the registered bridges array */
1007 num_registered_bridges
= dyn_array_ptr_size (®istered_bridges
);
1008 dyn_array_ptr_empty (®istered_bridges
);
1010 SGEN_TV_GETTIME (atv
);
1011 step_6
= SGEN_TV_ELAPSED (btv
, atv
);
1013 //g_print ("%d sccs containing bridges - %d max bridge objects - %d max xrefs\n", j, max_entries, max_xrefs);
1015 bridge_processor
->num_sccs
= num_sccs
;
1016 bridge_processor
->api_sccs
= api_sccs
;
1017 bridge_processor
->num_xrefs
= num_xrefs
;
1018 bridge_processor
->api_xrefs
= api_xrefs
;
1022 processing_after_callback (int generation
)
1025 int num_sccs
= bridge_processor
->num_sccs
;
1026 MonoGCBridgeSCC
**api_sccs
= bridge_processor
->api_sccs
;
1028 if (bridge_accounting_enabled
) {
1029 for (i
= 0; i
< num_sccs
; ++i
) {
1030 for (j
= 0; j
< api_sccs
[i
]->num_objs
; ++j
) {
1031 GCVTable vtable
= SGEN_LOAD_VTABLE (api_sccs
[i
]->objs
[j
]);
1032 mono_trace (G_LOG_LEVEL_INFO
, MONO_TRACE_GC
,
1033 "OBJECT %s (%p) SCC [%d] %s",
1034 sgen_client_vtable_get_namespace (vtable
), sgen_client_vtable_get_name (vtable
), api_sccs
[i
]->objs
[j
],
1036 api_sccs
[i
]->is_alive
? "ALIVE" : "DEAD");
1041 mono_trace (G_LOG_LEVEL_INFO
, MONO_TRACE_GC
, "GC_NEW_BRIDGE num-objects %d num_hash_entries %d sccs size %d init %.2fms df1 %.2fms sort %.2fms dfs2 %.2fms setup-cb %.2fms free-data %.2fms links %d/%d/%d/%d dfs passes %d/%d ignored %d",
1042 num_registered_bridges
, hash_table_size
, dyn_array_scc_size (&sccs
),
1049 fist_pass_links
, second_pass_links
, sccs_links
, max_sccs_links
,
1050 dfs1_passes
, dfs2_passes
, ignored_objects
);
1052 step_1
= 0; /* We must cleanup since this value is used as an accumulator. */
1053 fist_pass_links
= second_pass_links
= sccs_links
= max_sccs_links
= 0;
1054 dfs1_passes
= dfs2_passes
= ignored_objects
= 0;
1058 describe_pointer (GCObject
*obj
)
1063 for (i
= 0; i
< dyn_array_ptr_size (®istered_bridges
); ++i
) {
1064 if (obj
== dyn_array_ptr_get (®istered_bridges
, i
)) {
1065 printf ("Pointer is a registered bridge object.\n");
1070 entry
= (HashEntry
*)sgen_hash_table_lookup (&hash_table
, obj
);
1074 printf ("Bridge hash table entry %p:\n", entry
);
1075 printf (" is bridge: %d\n", (int)entry
->is_bridge
);
1076 printf (" is visited: %d\n", (int)entry
->v
.dfs1
.is_visited
);
1080 sgen_new_bridge_init (SgenBridgeProcessor
*collector
)
1082 collector
->reset_data
= reset_data
;
1083 collector
->processing_stw_step
= processing_stw_step
;
1084 collector
->processing_build_callback_data
= processing_build_callback_data
;
1085 collector
->processing_after_callback
= processing_after_callback
;
1086 collector
->class_kind
= class_kind
;
1087 collector
->register_finalized_object
= register_finalized_object
;
1088 collector
->describe_pointer
= describe_pointer
;
1089 collector
->set_config
= set_config
;
1091 bridge_processor
= collector
;