3 * Simple generational GC.
5 * Copyright 2011 Novell, Inc (http://www.novell.com)
6 * Copyright 2011 Xamarin Inc (http://www.xamarin.com)
7 * Copyright 2001-2003 Ximian, Inc
8 * Copyright 2003-2010 Novell, Inc.
10 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
15 #if defined (HAVE_SGEN_GC) && !defined (DISABLE_SGEN_GC_BRIDGE)
20 #include "sgen/sgen-gc.h"
21 #include "sgen-bridge-internals.h"
22 #include "sgen/sgen-hash-table.h"
23 #include "sgen/sgen-qsort.h"
24 #include "sgen/sgen-client.h"
25 #include "tabledefs.h"
26 #include "utils/mono-logger-internals.h"
28 #define OPTIMIZATION_COPY
29 #define OPTIMIZATION_FORWARD
30 #define OPTIMIZATION_SINGLETON_DYN_ARRAY
31 #include "sgen-dynarray.h"
35 //#define TEST_NEW_XREFS
38 #if !defined(NEW_XREFS) || defined(TEST_NEW_XREFS)
43 #define XREFS new_xrefs
45 #define XREFS old_xrefs
49 * Bridge data for a single managed object
51 * FIXME: Optimizations:
53 * Don't allocate a srcs array for just one source. Most objects have
54 * just one source, so use the srcs pointer itself.
56 typedef struct _HashEntry
{
61 guint32 is_visited
: 1;
62 guint32 finishing_time
: 31;
63 struct _HashEntry
*forwarded_to
;
66 // Index in sccs array of SCC this object was folded into
71 // "Source" managed objects pointing at this destination
78 } HashEntryWithAccounting
;
80 // The graph of managed objects/HashEntries is reduced to a graph of strongly connected components
85 // How many bridged objects does this SCC hold references to?
86 int num_bridge_entries
;
91 * Index in global sccs array of SCCs holding pointers to this SCC
93 * New and old xrefs are typically mutually exclusive. Only when TEST_NEW_XREFS is
94 * enabled we do both, and compare the results. This should only be done for
95 * debugging, obviously.
98 DynIntArray old_xrefs
; /* these are incoming, not outgoing */
101 DynIntArray new_xrefs
;
105 static char *dump_prefix
= NULL
;
107 // Maps managed objects to corresponding HashEntry stricts
108 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
);
110 static guint32 current_time
;
112 static gboolean bridge_accounting_enabled
= FALSE
;
114 static SgenBridgeProcessor
*bridge_processor
;
121 dyn_array_scc_init (DynSCCArray
*da
)
123 dyn_array_init (&da
->array
);
127 dyn_array_scc_uninit (DynSCCArray
*da
)
129 dyn_array_uninit (&da
->array
, sizeof (SCC
));
133 dyn_array_scc_size (DynSCCArray
*da
)
135 return da
->array
.size
;
139 dyn_array_scc_add (DynSCCArray
*da
)
141 return (SCC
*)dyn_array_add (&da
->array
, sizeof (SCC
));
145 dyn_array_scc_get_ptr (DynSCCArray
*da
, int x
)
147 return &((SCC
*)da
->array
.data
)[x
];
152 static DynIntArray merge_array
;
156 dyn_array_int_contains (DynIntArray
*da
, int x
)
159 for (i
= 0; i
< dyn_array_int_size (da
); ++i
)
160 if (dyn_array_int_get (da
, i
) == x
)
167 set_config (const SgenBridgeProcessorConfig
*config
)
169 if (config
->accounting
) {
170 SgenHashTable table
= SGEN_HASH_TABLE_INIT (INTERNAL_MEM_BRIDGE_HASH_TABLE
, INTERNAL_MEM_BRIDGE_HASH_TABLE_ENTRY
, sizeof (HashEntryWithAccounting
), mono_aligned_addr_hash
, NULL
);
171 bridge_accounting_enabled
= TRUE
;
174 if (config
->dump_prefix
) {
175 dump_prefix
= strdup (config
->dump_prefix
);
179 static MonoGCBridgeObjectKind
180 class_kind (MonoClass
*klass
)
182 MonoGCBridgeObjectKind res
= mono_bridge_callbacks
.bridge_class_kind (klass
);
184 /* If it's a bridge, nothing we can do about it. */
185 if (res
== GC_BRIDGE_TRANSPARENT_BRIDGE_CLASS
|| res
== GC_BRIDGE_OPAQUE_BRIDGE_CLASS
)
188 /* Non bridge classes with no pointers will never point to a bridge, so we can savely ignore them. */
189 if (!m_class_has_references (klass
)) {
190 SGEN_LOG (6, "class %s is opaque\n", m_class_get_name (klass
));
191 return GC_BRIDGE_OPAQUE_CLASS
;
194 /* Some arrays can be ignored */
195 if (m_class_get_rank (klass
) == 1) {
196 MonoClass
*elem_class
= m_class_get_element_class (klass
);
198 /* FIXME the bridge check can be quite expensive, cache it at the class level. */
199 /* An array of a sealed type that is not a bridge will never get to a bridge */
200 if ((mono_class_get_flags (elem_class
) & TYPE_ATTRIBUTE_SEALED
) && !m_class_has_references (elem_class
) && !mono_bridge_callbacks
.bridge_class_kind (elem_class
)) {
201 SGEN_LOG (6, "class %s is opaque\n", m_class_get_name (klass
));
202 return GC_BRIDGE_OPAQUE_CLASS
;
206 return GC_BRIDGE_TRANSPARENT_CLASS
;
210 get_hash_entry (MonoObject
*obj
, gboolean
*existing
)
212 HashEntry
*entry
= (HashEntry
*)sgen_hash_table_lookup (&hash_table
, obj
);
223 memset (&new_entry
, 0, sizeof (HashEntry
));
225 dyn_array_ptr_init (&new_entry
.srcs
);
226 new_entry
.v
.dfs1
.finishing_time
= 0;
228 sgen_hash_table_replace (&hash_table
, obj
, &new_entry
, NULL
);
230 return (HashEntry
*)sgen_hash_table_lookup (&hash_table
, obj
);
234 add_source (HashEntry
*entry
, HashEntry
*src
)
236 dyn_array_ptr_add (&entry
->srcs
, src
);
242 MonoObject
*obj G_GNUC_UNUSED
;
247 SGEN_HASH_TABLE_FOREACH (&hash_table
, MonoObject
*, obj
, HashEntry
*, entry
) {
248 int entry_size
= dyn_array_ptr_size (&entry
->srcs
);
249 total_srcs
+= entry_size
;
250 if (entry_size
> max_srcs
)
251 max_srcs
= entry_size
;
252 dyn_array_ptr_uninit (&entry
->srcs
);
253 } SGEN_HASH_TABLE_FOREACH_END
;
255 sgen_hash_table_clean (&hash_table
);
257 dyn_array_int_uninit (&merge_array
);
258 //g_print ("total srcs %d - max %d\n", total_srcs, max_srcs);
262 register_bridge_object (MonoObject
*obj
)
264 HashEntry
*entry
= get_hash_entry (obj
, NULL
);
265 entry
->is_bridge
= TRUE
;
270 register_finishing_time (HashEntry
*entry
, guint32 t
)
272 g_assert (entry
->v
.dfs1
.finishing_time
== 0);
273 /* finishing_time has 31 bits, so it must be within signed int32 range. */
274 g_assert (t
> 0 && t
<= G_MAXINT32
);
275 entry
->v
.dfs1
.finishing_time
= t
;
278 static int ignored_objects
;
281 is_opaque_object (MonoObject
*obj
)
283 if ((obj
->vtable
->gc_bits
& SGEN_GC_BIT_BRIDGE_OPAQUE_OBJECT
) == SGEN_GC_BIT_BRIDGE_OPAQUE_OBJECT
) {
284 SGEN_LOG (6, "ignoring %s\n", m_class_get_name (mono_object_class (obj
)));
292 object_needs_expansion (MonoObject
**objp
)
294 MonoObject
*obj
= *objp
;
295 MonoObject
*fwd
= SGEN_OBJECT_IS_FORWARDED (obj
);
298 if (is_opaque_object (fwd
))
300 return sgen_hash_table_lookup (&hash_table
, fwd
) != NULL
;
302 if (is_opaque_object (obj
))
304 if (!sgen_object_is_live (obj
))
306 return sgen_hash_table_lookup (&hash_table
, obj
) != NULL
;
310 follow_forward (HashEntry
*entry
)
312 #ifdef OPTIMIZATION_FORWARD
313 while (entry
->v
.dfs1
.forwarded_to
) {
314 HashEntry
*next
= entry
->v
.dfs1
.forwarded_to
;
315 if (next
->v
.dfs1
.forwarded_to
)
316 entry
->v
.dfs1
.forwarded_to
= next
->v
.dfs1
.forwarded_to
;
320 g_assert (!entry
->v
.dfs1
.forwarded_to
);
325 static DynPtrArray registered_bridges
;
326 static DynPtrArray dfs_stack
;
328 static int dfs1_passes
, dfs2_passes
;
331 * DFS1 maintains a stack, where each two entries are effectively one entry. (FIXME:
332 * Optimize this via pointer tagging.) There are two different types of entries:
334 * entry, src: entry needs to be expanded via scanning, and linked to from src
335 * NULL, entry: entry has already been expanded and needs to be finished
339 #define HANDLE_PTR(ptr,obj) do { \
340 GCObject *dst = (GCObject*)*(ptr); \
341 if (dst && object_needs_expansion (&dst)) { \
343 dyn_array_ptr_push (&dfs_stack, obj_entry); \
344 dyn_array_ptr_push (&dfs_stack, follow_forward (get_hash_entry (dst, NULL))); \
349 dfs1 (HashEntry
*obj_entry
)
352 g_assert (dyn_array_ptr_size (&dfs_stack
) == 0);
354 dyn_array_ptr_push (&dfs_stack
, NULL
);
355 dyn_array_ptr_push (&dfs_stack
, obj_entry
);
362 obj_entry
= (HashEntry
*)dyn_array_ptr_pop (&dfs_stack
);
364 /* obj_entry needs to be expanded */
365 src
= (HashEntry
*)dyn_array_ptr_pop (&dfs_stack
);
368 g_assert (!src
->v
.dfs1
.forwarded_to
);
370 obj_entry
= follow_forward (obj_entry
);
373 g_assert (!obj_entry
->v
.dfs1
.forwarded_to
);
374 obj
= sgen_hash_table_key_for_value_pointer (obj_entry
);
377 if (!obj_entry
->v
.dfs1
.is_visited
) {
379 mword desc
= sgen_obj_get_descriptor_safe (obj
);
381 obj_entry
->v
.dfs1
.is_visited
= 1;
383 /* push the finishing entry on the stack */
384 dyn_array_ptr_push (&dfs_stack
, obj_entry
);
385 dyn_array_ptr_push (&dfs_stack
, NULL
);
387 #include "sgen/sgen-scan-object.h"
390 * We can remove non-bridge objects with a single outgoing
391 * link by forwarding links going to it.
393 * This is the first time we've encountered this object, so
394 * no links to it have yet been added. We'll keep it that
395 * way by setting the forward pointer, and instead of
396 * continuing processing this object, we start over with the
397 * object it points to.
399 #ifdef OPTIMIZATION_FORWARD
400 if (!obj_entry
->is_bridge
&& num_links
== 1) {
401 HashEntry
*dst_entry
= (HashEntry
*)dyn_array_ptr_pop (&dfs_stack
);
402 HashEntry
*obj_entry_again
= (HashEntry
*)dyn_array_ptr_pop (&dfs_stack
);
403 g_assert (obj_entry_again
== obj_entry
);
404 g_assert (!dst_entry
->v
.dfs1
.forwarded_to
);
405 if (obj_entry
!= dst_entry
) {
406 obj_entry
->v
.dfs1
.forwarded_to
= dst_entry
;
407 obj_entry
= dst_entry
;
415 //g_print ("link %s -> %s\n", sgen_safe_name (src->obj), sgen_safe_name (obj));
416 g_assert (!obj_entry
->v
.dfs1
.forwarded_to
);
417 add_source (obj_entry
, src
);
419 //g_print ("starting with %s\n", sgen_safe_name (obj));
422 /* obj_entry needs to be finished */
424 obj_entry
= (HashEntry
*)dyn_array_ptr_pop (&dfs_stack
);
426 //g_print ("finish %s\n", sgen_safe_name (obj_entry->obj));
427 register_finishing_time (obj_entry
, ++current_time
);
429 } while (dyn_array_ptr_size (&dfs_stack
) > 0);
432 static DynSCCArray sccs
;
433 static SCC
*current_scc
;
436 * At the end of bridge processing we need to end up with an (acyclyc) graph of bridge
437 * object SCCs, where the links between the nodes (each one an SCC) in that graph represent
438 * the presence of a direct or indirect link between those SCCs. An example:
443 * A -> B -> c -> e -> F
445 * A, B, D and F are SCCs that contain bridge objects, c and e don't contain bridge objects.
446 * The graph we need to produce from this is:
453 * Note that we don't need to produce an edge from A to F. It's sufficient that F is
454 * indirectly reachable from A.
456 * The old algorithm would create a set, for each SCC, of bridge SCCs that can reach it,
457 * directly or indirectly, by merging the ones sets for those that reach it directly. The
458 * sets it would build up are these:
467 * The merge operations on these sets turned out to be huge time sinks.
469 * The new algorithm proceeds in two passes: During DFS2, it only builds up the sets of SCCs
470 * that directly point to each SCC:
479 * This is the adjacency list for the SCC graph, in other words. In a separate step
480 * afterwards, it does a depth-first traversal of that graph, for each bridge node, to get
481 * to the final list. It uses a flag to avoid traversing any node twice.
484 scc_add_xref (SCC
*src
, SCC
*dst
)
486 g_assert (src
!= dst
);
487 g_assert (src
->index
!= dst
->index
);
491 * FIXME: Right now we don't even unique the direct ancestors, but just add to the
492 * list. Doing a containment check slows this algorithm down to almost the speed of
493 * the old one. Use the flag instead!
495 dyn_array_int_add (&dst
->new_xrefs
, src
->index
);
499 if (dyn_array_int_is_copy (&dst
->old_xrefs
)) {
501 dyn_array_int_ensure_independent (&dst
->old_xrefs
);
502 for (i
= 0; i
< dyn_array_int_size (&dst
->old_xrefs
); ++i
) {
503 int j
= dyn_array_int_get (&dst
->old_xrefs
, i
);
504 SCC
*bridge_scc
= dyn_array_scc_get_ptr (&sccs
, j
);
505 g_assert (!bridge_scc
->flag
);
506 bridge_scc
->flag
= TRUE
;
510 if (src
->num_bridge_entries
) {
514 dyn_array_int_add (&dst
->old_xrefs
, src
->index
);
515 #ifdef OPTIMIZATION_COPY
516 } else if (dyn_array_int_size (&dst
->old_xrefs
) == 0) {
517 dyn_array_int_copy (&dst
->old_xrefs
, &src
->old_xrefs
);
521 for (i
= 0; i
< dyn_array_int_size (&src
->old_xrefs
); ++i
) {
522 int j
= dyn_array_int_get (&src
->old_xrefs
, i
);
523 SCC
*bridge_scc
= dyn_array_scc_get_ptr (&sccs
, j
);
524 g_assert (bridge_scc
->num_bridge_entries
);
525 if (!bridge_scc
->flag
) {
526 bridge_scc
->flag
= TRUE
;
527 dyn_array_int_add (&dst
->old_xrefs
, j
);
535 scc_add_entry (SCC
*scc
, HashEntry
*entry
)
537 g_assert (entry
->v
.dfs2
.scc_index
< 0);
538 entry
->v
.dfs2
.scc_index
= scc
->index
;
539 if (entry
->is_bridge
)
540 ++scc
->num_bridge_entries
;
544 dfs2 (HashEntry
*entry
)
548 g_assert (dyn_array_ptr_size (&dfs_stack
) == 0);
550 dyn_array_ptr_push (&dfs_stack
, entry
);
553 entry
= (HashEntry
*)dyn_array_ptr_pop (&dfs_stack
);
556 if (entry
->v
.dfs2
.scc_index
>= 0) {
557 if (entry
->v
.dfs2
.scc_index
!= current_scc
->index
)
558 scc_add_xref (dyn_array_scc_get_ptr (&sccs
, entry
->v
.dfs2
.scc_index
), current_scc
);
562 scc_add_entry (current_scc
, entry
);
564 for (i
= 0; i
< dyn_array_ptr_size (&entry
->srcs
); ++i
)
565 dyn_array_ptr_push (&dfs_stack
, dyn_array_ptr_get (&entry
->srcs
, i
));
566 } while (dyn_array_ptr_size (&dfs_stack
) > 0);
569 /* If xrefs is a copy then we haven't set a single flag. */
570 if (dyn_array_int_is_copy (¤t_scc
->old_xrefs
))
572 for (i
= 0; i
< dyn_array_int_size (¤t_scc
->old_xrefs
); ++i
) {
573 int j
= dyn_array_int_get (¤t_scc
->old_xrefs
, i
);
574 SCC
*bridge_scc
= dyn_array_scc_get_ptr (&sccs
, j
);
575 g_assert (bridge_scc
->flag
);
576 bridge_scc
->flag
= FALSE
;
583 gather_xrefs (SCC
*scc
)
586 for (i
= 0; i
< dyn_array_int_size (&scc
->new_xrefs
); ++i
) {
587 int index
= dyn_array_int_get (&scc
->new_xrefs
, i
);
588 SCC
*src
= dyn_array_scc_get_ptr (&sccs
, index
);
592 if (src
->num_bridge_entries
)
593 dyn_array_int_add (&merge_array
, index
);
600 reset_flags (SCC
*scc
)
603 for (i
= 0; i
< dyn_array_int_size (&scc
->new_xrefs
); ++i
) {
604 int index
= dyn_array_int_get (&scc
->new_xrefs
, i
);
605 SCC
*src
= dyn_array_scc_get_ptr (&sccs
, index
);
609 if (!src
->num_bridge_entries
)
618 static int counter
= 0;
622 size_t prefix_len
= strlen (dump_prefix
);
623 char *filename
= g_newa (char, prefix_len
+ 64);
627 sprintf (filename
, "%s.%d.gexf", dump_prefix
, counter
++);
628 file
= fopen (filename
, "w");
631 fprintf (stderr
, "Warning: Could not open bridge dump file `%s` for writing: %s\n", filename
, strerror (errno
));
635 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");
637 fprintf (file
, "<graph defaultedgetype=\"directed\">\n"
638 "<attributes class=\"node\">\n"
639 "<attribute id=\"0\" title=\"class\" type=\"string\"/>\n"
640 "<attribute id=\"1\" title=\"bridge\" type=\"boolean\"/>\n"
643 fprintf (file
, "<nodes>\n");
644 SGEN_HASH_TABLE_FOREACH (&hash_table
, MonoObject
*, obj
, HashEntry
*, entry
) {
645 MonoVTable
*vt
= SGEN_LOAD_VTABLE (obj
);
646 fprintf (file
, "<node id=\"%p\"><attvalues><attvalue for=\"0\" value=\"%s.%s\"/><attvalue for=\"1\" value=\"%s\"/></attvalues></node>\n",
647 obj
, m_class_get_name_space (vt
->klass
), m_class_get_name (vt
->klass
), entry
->is_bridge
? "true" : "false");
648 } SGEN_HASH_TABLE_FOREACH_END
;
649 fprintf (file
, "</nodes>\n");
651 fprintf (file
, "<edges>\n");
652 SGEN_HASH_TABLE_FOREACH (&hash_table
, MonoObject
*, obj
, HashEntry
*, entry
) {
654 for (i
= 0; i
< dyn_array_ptr_size (&entry
->srcs
); ++i
) {
655 HashEntry
*src
= (HashEntry
*)dyn_array_ptr_get (&entry
->srcs
, i
);
656 fprintf (file
, "<edge id=\"%d\" source=\"%p\" target=\"%p\"/>\n", edge_id
++, sgen_hash_table_key_for_value_pointer (src
), obj
);
658 } SGEN_HASH_TABLE_FOREACH_END
;
659 fprintf (file
, "</edges>\n");
661 fprintf (file
, "</graph></gexf>\n");
667 compare_hash_entries (const HashEntry
*e1
, const HashEntry
*e2
)
669 /* We can cast to signed int here because finishing_time has only 31 bits. */
670 return (gint32
)e2
->v
.dfs1
.finishing_time
- (gint32
)e1
->v
.dfs1
.finishing_time
;
673 DEF_QSORT_INLINE(hash_entries
, HashEntry
*, compare_hash_entries
)
675 static gint64 step_1
, step_2
, step_3
, step_4
, step_5
, step_6
;
676 static int fist_pass_links
, second_pass_links
, sccs_links
;
677 static int max_sccs_links
= 0;
680 register_finalized_object (GCObject
*obj
)
682 g_assert (sgen_need_bridge_processing ());
683 dyn_array_ptr_push (®istered_bridges
, obj
);
689 dyn_array_ptr_empty (®istered_bridges
);
693 processing_stw_step (void)
697 MonoObject
*obj G_GNUC_UNUSED
;
699 SGEN_TV_DECLARE (atv
);
700 SGEN_TV_DECLARE (btv
);
702 if (!dyn_array_ptr_size (®istered_bridges
))
705 SGEN_TV_GETTIME (btv
);
709 dyn_array_ptr_init (&dfs_stack
);
710 dyn_array_int_init (&merge_array
);
714 First we insert all bridges into the hash table and then we do dfs1.
716 It must be done in 2 steps since the bridge arrays doesn't come in reverse topological order,
717 which means that we can have entry N pointing to entry N + 1.
719 If we dfs1 entry N before N + 1 is registered we'll not consider N + 1 for this bridge
720 pass and not create the required xref between the two.
722 bridge_count
= dyn_array_ptr_size (®istered_bridges
);
723 for (i
= 0; i
< bridge_count
; ++i
)
724 register_bridge_object ((MonoObject
*)dyn_array_ptr_get (®istered_bridges
, i
));
726 for (i
= 0; i
< bridge_count
; ++i
)
727 dfs1 (get_hash_entry ((MonoObject
*)dyn_array_ptr_get (®istered_bridges
, i
), NULL
));
729 /* Remove all forwarded objects. */
730 SGEN_HASH_TABLE_FOREACH (&hash_table
, MonoObject
*, obj
, HashEntry
*, entry
) {
731 if (entry
->v
.dfs1
.forwarded_to
) {
732 g_assert (dyn_array_ptr_size (&entry
->srcs
) == 0);
733 SGEN_HASH_TABLE_FOREACH_REMOVE (TRUE
);
736 } SGEN_HASH_TABLE_FOREACH_END
;
738 SGEN_TV_GETTIME (atv
);
739 step_2
= SGEN_TV_ELAPSED (btv
, atv
);
745 static int num_registered_bridges
, hash_table_size
;
748 processing_build_callback_data (int generation
)
751 int num_sccs
, num_xrefs
;
752 int max_entries
, max_xrefs
;
753 MonoObject
*obj G_GNUC_UNUSED
;
755 HashEntry
**all_entries
;
756 MonoGCBridgeSCC
**api_sccs
;
757 MonoGCBridgeXRef
*api_xrefs
;
758 SGEN_TV_DECLARE (atv
);
759 SGEN_TV_DECLARE (btv
);
761 g_assert (bridge_processor
->num_sccs
== 0 && bridge_processor
->num_xrefs
== 0);
762 g_assert (!bridge_processor
->api_sccs
&& !bridge_processor
->api_xrefs
);
764 if (!dyn_array_ptr_size (®istered_bridges
))
767 g_assert (mono_bridge_processing_in_progress
);
769 SGEN_TV_GETTIME (atv
);
771 /* alloc and fill array of all entries */
773 all_entries
= (HashEntry
**)sgen_alloc_internal_dynamic (sizeof (HashEntry
*) * hash_table
.num_entries
, INTERNAL_MEM_BRIDGE_DATA
, TRUE
);
776 SGEN_HASH_TABLE_FOREACH (&hash_table
, MonoObject
*, obj
, HashEntry
*, entry
) {
777 g_assert (entry
->v
.dfs1
.finishing_time
> 0);
778 all_entries
[j
++] = entry
;
779 fist_pass_links
+= dyn_array_ptr_size (&entry
->srcs
);
780 } SGEN_HASH_TABLE_FOREACH_END
;
781 g_assert (j
== hash_table
.num_entries
);
782 hash_table_size
= hash_table
.num_entries
;
784 /* sort array according to decreasing finishing time */
785 qsort_hash_entries (all_entries
, hash_table
.num_entries
);
787 SGEN_HASH_TABLE_FOREACH (&hash_table
, MonoObject
*, obj
, HashEntry
*, entry
) {
788 entry
->v
.dfs2
.scc_index
= -1;
789 } SGEN_HASH_TABLE_FOREACH_END
;
791 SGEN_TV_GETTIME (btv
);
792 step_3
= SGEN_TV_ELAPSED (atv
, btv
);
794 /* second DFS pass */
796 dyn_array_scc_init (&sccs
);
797 for (i
= 0; i
< hash_table
.num_entries
; ++i
) {
798 HashEntry
*entry
= all_entries
[i
];
799 if (entry
->v
.dfs2
.scc_index
< 0) {
800 int index
= dyn_array_scc_size (&sccs
);
801 current_scc
= dyn_array_scc_add (&sccs
);
802 current_scc
->index
= index
;
803 current_scc
->num_bridge_entries
= 0;
805 current_scc
->flag
= FALSE
;
806 dyn_array_int_init (¤t_scc
->new_xrefs
);
809 dyn_array_int_init (¤t_scc
->old_xrefs
);
811 current_scc
->api_index
= -1;
817 * If a node has only one incoming edge, we just copy the source's
818 * xrefs array, effectively removing the source from the graph.
819 * This takes care of long linked lists.
821 if (!current_scc
->num_bridge_entries
&& dyn_array_int_size (¤t_scc
->new_xrefs
) == 1) {
823 j
= dyn_array_int_get (¤t_scc
->new_xrefs
, 0);
824 src
= dyn_array_scc_get_ptr (&sccs
, j
);
825 if (src
->num_bridge_entries
)
826 dyn_array_int_set (¤t_scc
->new_xrefs
, 0, j
);
828 dyn_array_int_copy (¤t_scc
->new_xrefs
, &src
->new_xrefs
);
835 #ifdef TEST_NEW_XREFS
836 for (j
= 0; j
< dyn_array_scc_size (&sccs
); ++j
) {
837 SCC
*scc
= dyn_array_scc_get_ptr (&sccs
, j
);
838 g_assert (!scc
->flag
);
842 for (i
= 0; i
< dyn_array_scc_size (&sccs
); ++i
) {
843 SCC
*scc
= dyn_array_scc_get_ptr (&sccs
, i
);
844 g_assert (scc
->index
== i
);
845 if (!scc
->num_bridge_entries
)
848 dyn_array_int_empty (&merge_array
);
851 dyn_array_int_copy (&scc
->new_xrefs
, &merge_array
);
852 dyn_array_int_ensure_independent (&scc
->new_xrefs
);
854 #ifdef TEST_NEW_XREFS
855 for (j
= 0; j
< dyn_array_scc_size (&sccs
); ++j
) {
856 SCC
*scc
= dyn_array_scc_get_ptr (&sccs
, j
);
857 g_assert (!scc
->flag
);
862 #ifdef TEST_NEW_XREFS
863 for (i
= 0; i
< dyn_array_scc_size (&sccs
); ++i
) {
864 SCC
*scc
= dyn_array_scc_get_ptr (&sccs
, i
);
865 g_assert (scc
->index
== i
);
866 if (!scc
->num_bridge_entries
)
869 g_assert (dyn_array_int_size (&scc
->new_xrefs
) == dyn_array_int_size (&scc
->old_xrefs
));
870 for (j
= 0; j
< dyn_array_int_size (&scc
->new_xrefs
); ++j
)
871 g_assert (dyn_array_int_contains (&scc
->old_xrefs
, dyn_array_int_get (&scc
->new_xrefs
, j
)));
877 * Compute the weight of each object. The weight of an object is its size plus the size of all
878 * objects it points do. When the an object is pointed by multiple objects we distribute it's weight
879 * equally among them. This distribution gives a rough estimate of the real impact of making the object
882 * The reasoning for this model is that complex graphs with single roots will have a bridge with very high
883 * value in comparison to others.
885 * The all_entries array has all objects topologically sorted. To correctly propagate the weights it must be
886 * done in reverse topological order - so we calculate the weight of the pointed-to objects before processing
887 * pointer-from objects.
889 * We log those objects in the opposite order for no particular reason. The other constrain is that it should use the same
890 * direction as the other logging loop that records live/dead information.
892 if (bridge_accounting_enabled
) {
893 for (i
= hash_table
.num_entries
- 1; i
>= 0; --i
) {
895 HashEntryWithAccounting
*entry
= (HashEntryWithAccounting
*)all_entries
[i
];
897 entry
->weight
+= (double)sgen_safe_object_get_size (sgen_hash_table_key_for_value_pointer (entry
));
898 w
= entry
->weight
/ dyn_array_ptr_size (&entry
->entry
.srcs
);
899 for (j
= 0; j
< dyn_array_ptr_size (&entry
->entry
.srcs
); ++j
) {
900 HashEntryWithAccounting
*other
= (HashEntryWithAccounting
*)dyn_array_ptr_get (&entry
->entry
.srcs
, j
);
904 for (i
= 0; i
< hash_table
.num_entries
; ++i
) {
905 HashEntryWithAccounting
*entry
= (HashEntryWithAccounting
*)all_entries
[i
];
906 if (entry
->entry
.is_bridge
) {
907 MonoObject
*obj
= sgen_hash_table_key_for_value_pointer (entry
);
908 MonoClass
*klass
= SGEN_LOAD_VTABLE (obj
)->klass
;
909 mono_trace (G_LOG_LEVEL_INFO
, MONO_TRACE_GC
, "OBJECT %s::%s (%p) weight %f", m_class_get_name_space (klass
), m_class_get_name (klass
), obj
, entry
->weight
);
914 for (i
= 0; i
< hash_table
.num_entries
; ++i
) {
915 HashEntry
*entry
= all_entries
[i
];
916 second_pass_links
+= dyn_array_ptr_size (&entry
->srcs
);
919 SGEN_TV_GETTIME (atv
);
920 step_4
= SGEN_TV_ELAPSED (btv
, atv
);
922 //g_print ("%d sccs\n", sccs.size);
924 dyn_array_ptr_uninit (&dfs_stack
);
926 /* init data for callback */
929 for (i
= 0; i
< dyn_array_scc_size (&sccs
); ++i
) {
930 SCC
*scc
= dyn_array_scc_get_ptr (&sccs
, i
);
931 g_assert (scc
->index
== i
);
932 if (scc
->num_bridge_entries
)
934 sccs_links
+= dyn_array_int_size (&scc
->XREFS
);
935 max_sccs_links
= MAX (max_sccs_links
, dyn_array_int_size (&scc
->XREFS
));
938 api_sccs
= (MonoGCBridgeSCC
**)sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC
*) * num_sccs
, INTERNAL_MEM_BRIDGE_DATA
, TRUE
);
941 for (i
= 0; i
< dyn_array_scc_size (&sccs
); ++i
) {
942 SCC
*scc
= dyn_array_scc_get_ptr (&sccs
, i
);
943 if (!scc
->num_bridge_entries
)
946 api_sccs
[j
] = (MonoGCBridgeSCC
*)sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC
) + sizeof (MonoObject
*) * scc
->num_bridge_entries
, INTERNAL_MEM_BRIDGE_DATA
, TRUE
);
947 api_sccs
[j
]->is_alive
= FALSE
;
948 api_sccs
[j
]->num_objs
= scc
->num_bridge_entries
;
949 scc
->num_bridge_entries
= 0;
950 scc
->api_index
= j
++;
952 num_xrefs
+= dyn_array_int_size (&scc
->XREFS
);
955 SGEN_HASH_TABLE_FOREACH (&hash_table
, MonoObject
*, obj
, HashEntry
*, entry
) {
956 if (entry
->is_bridge
) {
957 SCC
*scc
= dyn_array_scc_get_ptr (&sccs
, entry
->v
.dfs2
.scc_index
);
958 api_sccs
[scc
->api_index
]->objs
[scc
->num_bridge_entries
++] = sgen_hash_table_key_for_value_pointer (entry
);
960 } SGEN_HASH_TABLE_FOREACH_END
;
962 api_xrefs
= (MonoGCBridgeXRef
*)sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeXRef
) * num_xrefs
, INTERNAL_MEM_BRIDGE_DATA
, TRUE
);
964 for (i
= 0; i
< dyn_array_scc_size (&sccs
); ++i
) {
966 SCC
*scc
= dyn_array_scc_get_ptr (&sccs
, i
);
967 if (!scc
->num_bridge_entries
)
969 for (k
= 0; k
< dyn_array_int_size (&scc
->XREFS
); ++k
) {
970 SCC
*src_scc
= dyn_array_scc_get_ptr (&sccs
, dyn_array_int_get (&scc
->XREFS
, k
));
971 if (!src_scc
->num_bridge_entries
)
973 api_xrefs
[j
].src_scc_index
= src_scc
->api_index
;
974 api_xrefs
[j
].dst_scc_index
= scc
->api_index
;
979 SGEN_TV_GETTIME (btv
);
980 step_5
= SGEN_TV_ELAPSED (atv
, btv
);
985 max_entries
= max_xrefs
= 0;
986 for (i
= 0; i
< dyn_array_scc_size (&sccs
); ++i
) {
987 SCC
*scc
= dyn_array_scc_get_ptr (&sccs
, i
);
988 if (scc
->num_bridge_entries
)
990 if (scc
->num_bridge_entries
> max_entries
)
991 max_entries
= scc
->num_bridge_entries
;
992 if (dyn_array_int_size (&scc
->XREFS
) > max_xrefs
)
993 max_xrefs
= dyn_array_int_size (&scc
->XREFS
);
995 dyn_array_int_uninit (&scc
->new_xrefs
);
998 dyn_array_int_uninit (&scc
->old_xrefs
);
1002 dyn_array_scc_uninit (&sccs
);
1004 sgen_free_internal_dynamic (all_entries
, sizeof (HashEntry
*) * hash_table
.num_entries
, INTERNAL_MEM_BRIDGE_DATA
);
1007 /* Empty the registered bridges array */
1008 num_registered_bridges
= dyn_array_ptr_size (®istered_bridges
);
1009 dyn_array_ptr_empty (®istered_bridges
);
1011 SGEN_TV_GETTIME (atv
);
1012 step_6
= SGEN_TV_ELAPSED (btv
, atv
);
1014 //g_print ("%d sccs containing bridges - %d max bridge objects - %d max xrefs\n", j, max_entries, max_xrefs);
1016 bridge_processor
->num_sccs
= num_sccs
;
1017 bridge_processor
->api_sccs
= api_sccs
;
1018 bridge_processor
->num_xrefs
= num_xrefs
;
1019 bridge_processor
->api_xrefs
= api_xrefs
;
1023 processing_after_callback (int generation
)
1026 int num_sccs
= bridge_processor
->num_sccs
;
1027 MonoGCBridgeSCC
**api_sccs
= bridge_processor
->api_sccs
;
1029 if (bridge_accounting_enabled
) {
1030 for (i
= 0; i
< num_sccs
; ++i
) {
1031 for (j
= 0; j
< api_sccs
[i
]->num_objs
; ++j
) {
1032 GCVTable vtable
= SGEN_LOAD_VTABLE (api_sccs
[i
]->objs
[j
]);
1033 mono_trace (G_LOG_LEVEL_INFO
, MONO_TRACE_GC
,
1034 "OBJECT %s.%s (%p) SCC [%d] %s",
1035 sgen_client_vtable_get_namespace (vtable
), sgen_client_vtable_get_name (vtable
), api_sccs
[i
]->objs
[j
],
1037 api_sccs
[i
]->is_alive
? "ALIVE" : "DEAD");
1042 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",
1043 num_registered_bridges
, hash_table_size
, dyn_array_scc_size (&sccs
),
1050 fist_pass_links
, second_pass_links
, sccs_links
, max_sccs_links
,
1051 dfs1_passes
, dfs2_passes
, ignored_objects
);
1053 step_1
= 0; /* We must cleanup since this value is used as an accumulator. */
1054 fist_pass_links
= second_pass_links
= sccs_links
= max_sccs_links
= 0;
1055 dfs1_passes
= dfs2_passes
= ignored_objects
= 0;
1059 describe_pointer (GCObject
*obj
)
1064 for (i
= 0; i
< dyn_array_ptr_size (®istered_bridges
); ++i
) {
1065 if (obj
== dyn_array_ptr_get (®istered_bridges
, i
)) {
1066 printf ("Pointer is a registered bridge object.\n");
1071 entry
= (HashEntry
*)sgen_hash_table_lookup (&hash_table
, obj
);
1075 printf ("Bridge hash table entry %p:\n", entry
);
1076 printf (" is bridge: %d\n", (int)entry
->is_bridge
);
1077 printf (" is visited: %d\n", (int)entry
->v
.dfs1
.is_visited
);
1081 sgen_new_bridge_init (SgenBridgeProcessor
*collector
)
1083 collector
->reset_data
= reset_data
;
1084 collector
->processing_stw_step
= processing_stw_step
;
1085 collector
->processing_build_callback_data
= processing_build_callback_data
;
1086 collector
->processing_after_callback
= processing_after_callback
;
1087 collector
->class_kind
= class_kind
;
1088 collector
->register_finalized_object
= register_finalized_object
;
1089 collector
->describe_pointer
= describe_pointer
;
1090 collector
->set_config
= set_config
;
1092 bridge_processor
= collector
;