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)
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.
48 #include "sgen-bridge.h"
49 #include "sgen-hash-table.h"
50 #include "sgen-qsort.h"
51 #include "tabledefs.h"
52 #include "utils/mono-logger-internal.h"
53 #include "utils/mono-time.h"
54 #include "utils/mono-compiler.h"
58 //#define TEST_NEW_XREFS
61 #if !defined(NEW_XREFS) || defined(TEST_NEW_XREFS)
66 #define XREFS new_xrefs
68 #define XREFS old_xrefs
71 #define OPTIMIZATION_COPY
72 #define OPTIMIZATION_FORWARD
73 #define OPTIMIZATION_SINGLETON_DYN_ARRAY
77 int capacity; /* if negative, data points to another DynArray's data */
97 * FIXME: Optimizations:
99 * Don't allocate a scrs array for just one source. Most objects have
100 * just one source, so use the srcs pointer itself.
102 typedef struct _HashEntry {
107 guint32 is_visited : 1;
108 guint32 finishing_time : 31;
109 struct _HashEntry *forwarded_to;
122 } HashEntryWithAccounting;
124 typedef struct _SCC {
127 int num_bridge_entries;
130 * New and old xrefs are typically mutually exclusive. Only when TEST_NEW_XREFS is
131 * enabled we do both, and compare the results. This should only be done for
132 * debugging, obviously.
135 DynIntArray old_xrefs; /* these are incoming, not outgoing */
138 DynIntArray new_xrefs;
142 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);
144 static guint32 current_time;
146 static gboolean bridge_accounting_enabled = FALSE;
148 static SgenBridgeProcessor *bridge_processor;
156 dyn_array_init (DynArray *da)
164 dyn_array_uninit (DynArray *da, int elem_size)
166 if (da->capacity < 0) {
171 if (da->capacity == 0)
174 sgen_free_internal_dynamic (da->data, elem_size * da->capacity, INTERNAL_MEM_BRIDGE_DATA);
179 dyn_array_empty (DynArray *da)
181 if (da->capacity < 0)
188 dyn_array_ensure_capacity (DynArray *da, int capacity, int elem_size)
190 int old_capacity = da->capacity;
193 g_assert (capacity > 0);
195 if (capacity <= old_capacity)
198 if (old_capacity <= 0)
200 while (capacity > da->capacity)
203 new_data = sgen_alloc_internal_dynamic (elem_size * da->capacity, INTERNAL_MEM_BRIDGE_DATA, TRUE);
204 memcpy (new_data, da->data, elem_size * da->size);
205 if (old_capacity > 0)
206 sgen_free_internal_dynamic (da->data, elem_size * old_capacity, INTERNAL_MEM_BRIDGE_DATA);
211 dyn_array_is_copy (DynArray *da)
213 return da->capacity < 0;
217 dyn_array_ensure_independent (DynArray *da, int elem_size)
219 if (!dyn_array_is_copy (da))
221 dyn_array_ensure_capacity (da, da->size, elem_size);
222 g_assert (da->capacity > 0);
226 dyn_array_add (DynArray *da, int elem_size)
230 dyn_array_ensure_capacity (da, da->size + 1, elem_size);
232 p = da->data + da->size * elem_size;
238 dyn_array_copy (DynArray *dst, DynArray *src, int elem_size)
240 dyn_array_uninit (dst, elem_size);
245 dst->size = src->size;
247 dst->data = src->data;
252 dyn_array_int_init (DynIntArray *da)
254 dyn_array_init (&da->array);
258 dyn_array_int_uninit (DynIntArray *da)
260 dyn_array_uninit (&da->array, sizeof (int));
264 dyn_array_int_size (DynIntArray *da)
266 return da->array.size;
271 dyn_array_int_empty (DynIntArray *da)
273 dyn_array_empty (&da->array);
278 dyn_array_int_add (DynIntArray *da, int x)
280 int *p = dyn_array_add (&da->array, sizeof (int));
285 dyn_array_int_get (DynIntArray *da, int x)
287 return ((int*)da->array.data)[x];
292 dyn_array_int_set (DynIntArray *da, int idx, int val)
294 ((int*)da->array.data)[idx] = val;
299 dyn_array_int_ensure_independent (DynIntArray *da)
301 dyn_array_ensure_independent (&da->array, sizeof (int));
305 dyn_array_int_copy (DynIntArray *dst, DynIntArray *src)
307 dyn_array_copy (&dst->array, &src->array, sizeof (int));
311 dyn_array_int_is_copy (DynIntArray *da)
313 return dyn_array_is_copy (&da->array);
319 dyn_array_ptr_init (DynPtrArray *da)
321 dyn_array_init (&da->array);
325 dyn_array_ptr_uninit (DynPtrArray *da)
327 #ifdef OPTIMIZATION_SINGLETON_DYN_ARRAY
328 if (da->array.capacity == 1)
329 dyn_array_ptr_init (da);
332 dyn_array_uninit (&da->array, sizeof (void*));
336 dyn_array_ptr_size (DynPtrArray *da)
338 return da->array.size;
342 dyn_array_ptr_empty (DynPtrArray *da)
344 #ifdef OPTIMIZATION_SINGLETON_DYN_ARRAY
345 if (da->array.capacity == 1)
346 dyn_array_ptr_init (da);
349 dyn_array_empty (&da->array);
353 dyn_array_ptr_get (DynPtrArray *da, int x)
355 #ifdef OPTIMIZATION_SINGLETON_DYN_ARRAY
356 if (da->array.capacity == 1) {
358 return da->array.data;
361 return ((void**)da->array.data)[x];
365 dyn_array_ptr_add (DynPtrArray *da, void *ptr)
369 #ifdef OPTIMIZATION_SINGLETON_DYN_ARRAY
370 if (da->array.capacity == 0) {
371 da->array.capacity = 1;
373 p = (void**)&da->array.data;
374 } else if (da->array.capacity == 1) {
375 void *ptr0 = da->array.data;
377 dyn_array_init (&da->array);
378 p0 = dyn_array_add (&da->array, sizeof (void*));
380 p = dyn_array_add (&da->array, sizeof (void*));
384 p = dyn_array_add (&da->array, sizeof (void*));
389 #define dyn_array_ptr_push dyn_array_ptr_add
392 dyn_array_ptr_pop (DynPtrArray *da)
394 int size = da->array.size;
397 #ifdef OPTIMIZATION_SINGLETON_DYN_ARRAY
398 if (da->array.capacity == 1) {
399 p = dyn_array_ptr_get (da, 0);
400 dyn_array_init (&da->array);
404 g_assert (da->array.capacity > 1);
405 dyn_array_ensure_independent (&da->array, sizeof (void*));
406 p = dyn_array_ptr_get (da, size - 1);
415 dyn_array_scc_init (DynSCCArray *da)
417 dyn_array_init (&da->array);
421 dyn_array_scc_uninit (DynSCCArray *da)
423 dyn_array_uninit (&da->array, sizeof (SCC));
427 dyn_array_scc_size (DynSCCArray *da)
429 return da->array.size;
433 dyn_array_scc_add (DynSCCArray *da)
435 return dyn_array_add (&da->array, sizeof (SCC));
439 dyn_array_scc_get_ptr (DynSCCArray *da, int x)
441 return &((SCC*)da->array.data)[x];
446 static DynIntArray merge_array;
450 dyn_array_int_contains (DynIntArray *da, int x)
453 for (i = 0; i < dyn_array_int_size (da); ++i)
454 if (dyn_array_int_get (da, i) == x)
461 enable_accounting (void)
463 SgenHashTable table = SGEN_HASH_TABLE_INIT (INTERNAL_MEM_BRIDGE_HASH_TABLE, INTERNAL_MEM_BRIDGE_HASH_TABLE_ENTRY, sizeof (HashEntryWithAccounting), mono_aligned_addr_hash, NULL);
464 bridge_accounting_enabled = TRUE;
468 static MonoGCBridgeObjectKind
469 class_kind (MonoClass *class)
471 MonoGCBridgeObjectKind res = bridge_callbacks.bridge_class_kind (class);
473 /* If it's a bridge, nothing we can do about it. */
474 if (res == GC_BRIDGE_TRANSPARENT_BRIDGE_CLASS || res == GC_BRIDGE_OPAQUE_BRIDGE_CLASS)
477 /* Non bridge classes with no pointers will never point to a bridge, so we can savely ignore them. */
478 if (!class->has_references) {
479 SGEN_LOG (6, "class %s is opaque\n", class->name);
480 return GC_BRIDGE_OPAQUE_CLASS;
483 /* Some arrays can be ignored */
484 if (class->rank == 1) {
485 MonoClass *elem_class = class->element_class;
487 /* FIXME the bridge check can be quite expensive, cache it at the class level. */
488 /* An array of a sealed type that is not a bridge will never get to a bridge */
489 if ((elem_class->flags & TYPE_ATTRIBUTE_SEALED) && !elem_class->has_references && !bridge_callbacks.bridge_class_kind (elem_class)) {
490 SGEN_LOG (6, "class %s is opaque\n", class->name);
491 return GC_BRIDGE_OPAQUE_CLASS;
495 return GC_BRIDGE_TRANSPARENT_CLASS;
499 get_hash_entry (MonoObject *obj, gboolean *existing)
501 HashEntry *entry = sgen_hash_table_lookup (&hash_table, obj);
512 memset (&new_entry, 0, sizeof (HashEntry));
514 dyn_array_ptr_init (&new_entry.srcs);
515 new_entry.v.dfs1.finishing_time = 0;
517 sgen_hash_table_replace (&hash_table, obj, &new_entry, NULL);
519 return sgen_hash_table_lookup (&hash_table, obj);
523 add_source (HashEntry *entry, HashEntry *src)
525 dyn_array_ptr_add (&entry->srcs, src);
531 MonoObject *obj G_GNUC_UNUSED;
536 SGEN_HASH_TABLE_FOREACH (&hash_table, obj, entry) {
537 int entry_size = dyn_array_ptr_size (&entry->srcs);
538 total_srcs += entry_size;
539 if (entry_size > max_srcs)
540 max_srcs = entry_size;
541 dyn_array_ptr_uninit (&entry->srcs);
542 } SGEN_HASH_TABLE_FOREACH_END;
544 sgen_hash_table_clean (&hash_table);
546 dyn_array_int_uninit (&merge_array);
547 //g_print ("total srcs %d - max %d\n", total_srcs, max_srcs);
551 register_bridge_object (MonoObject *obj)
553 HashEntry *entry = get_hash_entry (obj, NULL);
554 entry->is_bridge = TRUE;
559 register_finishing_time (HashEntry *entry, guint32 t)
561 g_assert (entry->v.dfs1.finishing_time == 0);
562 /* finishing_time has 31 bits, so it must be within signed int32 range. */
563 g_assert (t > 0 && t <= G_MAXINT32);
564 entry->v.dfs1.finishing_time = t;
567 static int ignored_objects;
570 is_opaque_object (MonoObject *obj)
572 if ((obj->vtable->gc_bits & SGEN_GC_BIT_BRIDGE_OPAQUE_OBJECT) == SGEN_GC_BIT_BRIDGE_OPAQUE_OBJECT) {
573 SGEN_LOG (6, "ignoring %s\n", obj->vtable->klass->name);
581 object_needs_expansion (MonoObject **objp)
583 MonoObject *obj = *objp;
584 MonoObject *fwd = SGEN_OBJECT_IS_FORWARDED (obj);
587 if (is_opaque_object (fwd))
589 return sgen_hash_table_lookup (&hash_table, fwd) != NULL;
591 if (is_opaque_object (obj))
593 if (!sgen_object_is_live (obj))
595 return sgen_hash_table_lookup (&hash_table, obj) != NULL;
599 follow_forward (HashEntry *entry)
601 #ifdef OPTIMIZATION_FORWARD
602 while (entry->v.dfs1.forwarded_to) {
603 HashEntry *next = entry->v.dfs1.forwarded_to;
604 if (next->v.dfs1.forwarded_to)
605 entry->v.dfs1.forwarded_to = next->v.dfs1.forwarded_to;
609 g_assert (!entry->v.dfs1.forwarded_to);
614 static DynPtrArray registered_bridges;
615 static DynPtrArray dfs_stack;
617 static int dfs1_passes, dfs2_passes;
620 * DFS1 maintains a stack, where each two entries are effectively one entry. (FIXME:
621 * Optimize this via pointer tagging.) There are two different types of entries:
623 * entry, src: entry needs to be expanded via scanning, and linked to from src
624 * NULL, entry: entry has already been expanded and needs to be finished
628 #define HANDLE_PTR(ptr,obj) do { \
629 MonoObject *dst = (MonoObject*)*(ptr); \
630 if (dst && object_needs_expansion (&dst)) { \
632 dyn_array_ptr_push (&dfs_stack, obj_entry); \
633 dyn_array_ptr_push (&dfs_stack, follow_forward (get_hash_entry (dst, NULL))); \
638 dfs1 (HashEntry *obj_entry)
641 g_assert (dyn_array_ptr_size (&dfs_stack) == 0);
643 dyn_array_ptr_push (&dfs_stack, NULL);
644 dyn_array_ptr_push (&dfs_stack, obj_entry);
651 obj_entry = dyn_array_ptr_pop (&dfs_stack);
653 /* obj_entry needs to be expanded */
654 src = dyn_array_ptr_pop (&dfs_stack);
657 g_assert (!src->v.dfs1.forwarded_to);
659 obj_entry = follow_forward (obj_entry);
662 g_assert (!obj_entry->v.dfs1.forwarded_to);
663 obj = sgen_hash_table_key_for_value_pointer (obj_entry);
666 if (!obj_entry->v.dfs1.is_visited) {
668 mword desc = sgen_obj_get_descriptor_safe (start);
670 obj_entry->v.dfs1.is_visited = 1;
672 /* push the finishing entry on the stack */
673 dyn_array_ptr_push (&dfs_stack, obj_entry);
674 dyn_array_ptr_push (&dfs_stack, NULL);
676 #include "sgen-scan-object.h"
679 * We can remove non-bridge objects with a single outgoing
680 * link by forwarding links going to it.
682 * This is the first time we've encountered this object, so
683 * no links to it have yet been added. We'll keep it that
684 * way by setting the forward pointer, and instead of
685 * continuing processing this object, we start over with the
686 * object it points to.
688 #ifdef OPTIMIZATION_FORWARD
689 if (!obj_entry->is_bridge && num_links == 1) {
690 HashEntry *dst_entry = dyn_array_ptr_pop (&dfs_stack);
691 HashEntry *obj_entry_again = dyn_array_ptr_pop (&dfs_stack);
692 g_assert (obj_entry_again == obj_entry);
693 g_assert (!dst_entry->v.dfs1.forwarded_to);
694 if (obj_entry != dst_entry) {
695 obj_entry->v.dfs1.forwarded_to = dst_entry;
696 obj_entry = dst_entry;
704 //g_print ("link %s -> %s\n", sgen_safe_name (src->obj), sgen_safe_name (obj));
705 g_assert (!obj_entry->v.dfs1.forwarded_to);
706 add_source (obj_entry, src);
708 //g_print ("starting with %s\n", sgen_safe_name (obj));
711 /* obj_entry needs to be finished */
713 obj_entry = dyn_array_ptr_pop (&dfs_stack);
715 //g_print ("finish %s\n", sgen_safe_name (obj_entry->obj));
716 register_finishing_time (obj_entry, ++current_time);
718 } while (dyn_array_ptr_size (&dfs_stack) > 0);
721 static DynSCCArray sccs;
722 static SCC *current_scc;
725 * At the end of bridge processing we need to end up with an (acyclyc) graph of bridge
726 * object SCCs, where the links between the nodes (each one an SCC) in that graph represent
727 * the presence of a direct or indirect link between those SCCs. An example:
732 * A -> B -> c -> e -> F
734 * A, B, D and F are SCCs that contain bridge objects, c and e don't contain bridge objects.
735 * The graph we need to produce from this is:
742 * Note that we don't need to produce an edge from A to F. It's sufficient that F is
743 * indirectly reachable from A.
745 * The old algorithm would create a set, for each SCC, of bridge SCCs that can reach it,
746 * directly or indirectly, by merging the ones sets for those that reach it directly. The
747 * sets it would build up are these:
756 * The merge operations on these sets turned out to be huge time sinks.
758 * The new algorithm proceeds in two passes: During DFS2, it only builds up the sets of SCCs
759 * that directly point to each SCC:
768 * This is the adjacency list for the SCC graph, in other words. In a separate step
769 * afterwards, it does a depth-first traversal of that graph, for each bridge node, to get
770 * to the final list. It uses a flag to avoid traversing any node twice.
773 scc_add_xref (SCC *src, SCC *dst)
775 g_assert (src != dst);
776 g_assert (src->index != dst->index);
780 * FIXME: Right now we don't even unique the direct ancestors, but just add to the
781 * list. Doing a containment check slows this algorithm down to almost the speed of
782 * the old one. Use the flag instead!
784 dyn_array_int_add (&dst->new_xrefs, src->index);
788 if (dyn_array_int_is_copy (&dst->old_xrefs)) {
790 dyn_array_int_ensure_independent (&dst->old_xrefs);
791 for (i = 0; i < dyn_array_int_size (&dst->old_xrefs); ++i) {
792 int j = dyn_array_int_get (&dst->old_xrefs, i);
793 SCC *bridge_scc = dyn_array_scc_get_ptr (&sccs, j);
794 g_assert (!bridge_scc->flag);
795 bridge_scc->flag = TRUE;
799 if (src->num_bridge_entries) {
803 dyn_array_int_add (&dst->old_xrefs, src->index);
804 #ifdef OPTIMIZATION_COPY
805 } else if (dyn_array_int_size (&dst->old_xrefs) == 0) {
806 dyn_array_int_copy (&dst->old_xrefs, &src->old_xrefs);
810 for (i = 0; i < dyn_array_int_size (&src->old_xrefs); ++i) {
811 int j = dyn_array_int_get (&src->old_xrefs, i);
812 SCC *bridge_scc = dyn_array_scc_get_ptr (&sccs, j);
813 g_assert (bridge_scc->num_bridge_entries);
814 if (!bridge_scc->flag) {
815 bridge_scc->flag = TRUE;
816 dyn_array_int_add (&dst->old_xrefs, j);
824 scc_add_entry (SCC *scc, HashEntry *entry)
826 g_assert (entry->v.dfs2.scc_index < 0);
827 entry->v.dfs2.scc_index = scc->index;
828 if (entry->is_bridge)
829 ++scc->num_bridge_entries;
833 dfs2 (HashEntry *entry)
837 g_assert (dyn_array_ptr_size (&dfs_stack) == 0);
839 dyn_array_ptr_push (&dfs_stack, entry);
842 entry = dyn_array_ptr_pop (&dfs_stack);
845 if (entry->v.dfs2.scc_index >= 0) {
846 if (entry->v.dfs2.scc_index != current_scc->index)
847 scc_add_xref (dyn_array_scc_get_ptr (&sccs, entry->v.dfs2.scc_index), current_scc);
851 scc_add_entry (current_scc, entry);
853 for (i = 0; i < dyn_array_ptr_size (&entry->srcs); ++i)
854 dyn_array_ptr_push (&dfs_stack, dyn_array_ptr_get (&entry->srcs, i));
855 } while (dyn_array_ptr_size (&dfs_stack) > 0);
858 /* If xrefs is a copy then we haven't set a single flag. */
859 if (dyn_array_int_is_copy (¤t_scc->old_xrefs))
861 for (i = 0; i < dyn_array_int_size (¤t_scc->old_xrefs); ++i) {
862 int j = dyn_array_int_get (¤t_scc->old_xrefs, i);
863 SCC *bridge_scc = dyn_array_scc_get_ptr (&sccs, j);
864 g_assert (bridge_scc->flag);
865 bridge_scc->flag = FALSE;
872 gather_xrefs (SCC *scc)
875 for (i = 0; i < dyn_array_int_size (&scc->new_xrefs); ++i) {
876 int index = dyn_array_int_get (&scc->new_xrefs, i);
877 SCC *src = dyn_array_scc_get_ptr (&sccs, index);
881 if (src->num_bridge_entries)
882 dyn_array_int_add (&merge_array, index);
889 reset_flags (SCC *scc)
892 for (i = 0; i < dyn_array_int_size (&scc->new_xrefs); ++i) {
893 int index = dyn_array_int_get (&scc->new_xrefs, i);
894 SCC *src = dyn_array_scc_get_ptr (&sccs, index);
898 if (!src->num_bridge_entries)
904 static char *dump_prefix = NULL;
909 static int counter = 0;
913 size_t prefix_len = strlen (dump_prefix);
914 char *filename = alloca(prefix_len + 64);
918 sprintf (filename, "%s.%d.gexf", dump_prefix, counter++);
919 file = fopen (filename, "w");
922 fprintf (stderr, "Warning: Could not open bridge dump file `%s` for writing: %s\n", filename, strerror (errno));
926 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");
928 fprintf (file, "<graph defaultedgetype=\"directed\">\n"
929 "<attributes class=\"node\">\n"
930 "<attribute id=\"0\" title=\"class\" type=\"string\"/>\n"
931 "<attribute id=\"1\" title=\"bridge\" type=\"boolean\"/>\n"
934 fprintf (file, "<nodes>\n");
935 SGEN_HASH_TABLE_FOREACH (&hash_table, obj, entry) {
936 MonoVTable *vt = (MonoVTable*) SGEN_LOAD_VTABLE (obj);
937 fprintf (file, "<node id=\"%p\"><attvalues><attvalue for=\"0\" value=\"%s.%s\"/><attvalue for=\"1\" value=\"%s\"/></attvalues></node>\n",
938 obj, vt->klass->name_space, vt->klass->name, entry->is_bridge ? "true" : "false");
939 } SGEN_HASH_TABLE_FOREACH_END;
940 fprintf (file, "</nodes>\n");
942 fprintf (file, "<edges>\n");
943 SGEN_HASH_TABLE_FOREACH (&hash_table, obj, entry) {
945 for (i = 0; i < dyn_array_ptr_size (&entry->srcs); ++i) {
946 HashEntry *src = dyn_array_ptr_get (&entry->srcs, i);
947 fprintf (file, "<edge id=\"%d\" source=\"%p\" target=\"%p\"/>\n", edge_id++, sgen_hash_table_key_for_value_pointer (src), obj);
949 } SGEN_HASH_TABLE_FOREACH_END;
950 fprintf (file, "</edges>\n");
952 fprintf (file, "</graph></gexf>\n");
958 set_dump_prefix (const char *prefix)
960 dump_prefix = strdup (prefix);
964 compare_hash_entries (const HashEntry *e1, const HashEntry *e2)
966 /* We can cast to signed int here because finishing_time has only 31 bits. */
967 return (gint32)e2->v.dfs1.finishing_time - (gint32)e1->v.dfs1.finishing_time;
970 DEF_QSORT_INLINE(hash_entries, HashEntry*, compare_hash_entries)
972 static unsigned long step_1, step_2, step_3, step_4, step_5, step_6;
973 static int fist_pass_links, second_pass_links, sccs_links;
974 static int max_sccs_links = 0;
977 register_finalized_object (MonoObject *obj)
979 g_assert (sgen_need_bridge_processing ());
980 dyn_array_ptr_push (®istered_bridges, obj);
986 dyn_array_ptr_empty (®istered_bridges);
990 processing_stw_step (void)
994 MonoObject *obj G_GNUC_UNUSED;
996 SGEN_TV_DECLARE (atv);
997 SGEN_TV_DECLARE (btv);
999 if (!dyn_array_ptr_size (®istered_bridges))
1002 SGEN_TV_GETTIME (btv);
1004 /* first DFS pass */
1006 dyn_array_ptr_init (&dfs_stack);
1007 dyn_array_int_init (&merge_array);
1011 First we insert all bridges into the hash table and then we do dfs1.
1013 It must be done in 2 steps since the bridge arrays doesn't come in reverse topological order,
1014 which means that we can have entry N pointing to entry N + 1.
1016 If we dfs1 entry N before N + 1 is registered we'll not consider N + 1 for this bridge
1017 pass and not create the required xref between the two.
1019 bridge_count = dyn_array_ptr_size (®istered_bridges);
1020 for (i = 0; i < bridge_count ; ++i)
1021 register_bridge_object (dyn_array_ptr_get (®istered_bridges, i));
1023 for (i = 0; i < bridge_count; ++i)
1024 dfs1 (get_hash_entry (dyn_array_ptr_get (®istered_bridges, i), NULL));
1026 /* Remove all forwarded objects. */
1027 SGEN_HASH_TABLE_FOREACH (&hash_table, obj, entry) {
1028 if (entry->v.dfs1.forwarded_to) {
1029 g_assert (dyn_array_ptr_size (&entry->srcs) == 0);
1030 SGEN_HASH_TABLE_FOREACH_REMOVE (TRUE);
1033 } SGEN_HASH_TABLE_FOREACH_END;
1035 SGEN_TV_GETTIME (atv);
1036 step_2 = SGEN_TV_ELAPSED (btv, atv);
1042 static int num_registered_bridges, hash_table_size;
1045 processing_build_callback_data (int generation)
1048 int num_sccs, num_xrefs;
1049 int max_entries, max_xrefs;
1050 MonoObject *obj G_GNUC_UNUSED;
1052 HashEntry **all_entries;
1053 MonoGCBridgeSCC **api_sccs;
1054 MonoGCBridgeXRef *api_xrefs;
1055 SGEN_TV_DECLARE (atv);
1056 SGEN_TV_DECLARE (btv);
1058 g_assert (bridge_processor->num_sccs == 0 && bridge_processor->num_xrefs == 0);
1059 g_assert (!bridge_processor->api_sccs && !bridge_processor->api_xrefs);
1061 if (!dyn_array_ptr_size (®istered_bridges))
1064 g_assert (bridge_processing_in_progress);
1066 SGEN_TV_GETTIME (atv);
1068 /* alloc and fill array of all entries */
1070 all_entries = sgen_alloc_internal_dynamic (sizeof (HashEntry*) * hash_table.num_entries, INTERNAL_MEM_BRIDGE_DATA, TRUE);
1073 SGEN_HASH_TABLE_FOREACH (&hash_table, obj, entry) {
1074 g_assert (entry->v.dfs1.finishing_time > 0);
1075 all_entries [j++] = entry;
1076 fist_pass_links += dyn_array_ptr_size (&entry->srcs);
1077 } SGEN_HASH_TABLE_FOREACH_END;
1078 g_assert (j == hash_table.num_entries);
1079 hash_table_size = hash_table.num_entries;
1081 /* sort array according to decreasing finishing time */
1082 qsort_hash_entries (all_entries, hash_table.num_entries);
1084 SGEN_HASH_TABLE_FOREACH (&hash_table, obj, entry) {
1085 entry->v.dfs2.scc_index = -1;
1086 } SGEN_HASH_TABLE_FOREACH_END;
1088 SGEN_TV_GETTIME (btv);
1089 step_3 = SGEN_TV_ELAPSED (atv, btv);
1091 /* second DFS pass */
1093 dyn_array_scc_init (&sccs);
1094 for (i = 0; i < hash_table.num_entries; ++i) {
1095 HashEntry *entry = all_entries [i];
1096 if (entry->v.dfs2.scc_index < 0) {
1097 int index = dyn_array_scc_size (&sccs);
1098 current_scc = dyn_array_scc_add (&sccs);
1099 current_scc->index = index;
1100 current_scc->num_bridge_entries = 0;
1102 current_scc->flag = FALSE;
1103 dyn_array_int_init (¤t_scc->new_xrefs);
1106 dyn_array_int_init (¤t_scc->old_xrefs);
1108 current_scc->api_index = -1;
1114 * If a node has only one incoming edge, we just copy the source's
1115 * xrefs array, effectively removing the source from the graph.
1116 * This takes care of long linked lists.
1118 if (!current_scc->num_bridge_entries && dyn_array_int_size (¤t_scc->new_xrefs) == 1) {
1120 j = dyn_array_int_get (¤t_scc->new_xrefs, 0);
1121 src = dyn_array_scc_get_ptr (&sccs, j);
1122 if (src->num_bridge_entries)
1123 dyn_array_int_set (¤t_scc->new_xrefs, 0, j);
1125 dyn_array_int_copy (¤t_scc->new_xrefs, &src->new_xrefs);
1132 #ifdef TEST_NEW_XREFS
1133 for (j = 0; j < dyn_array_scc_size (&sccs); ++j) {
1134 SCC *scc = dyn_array_scc_get_ptr (&sccs, j);
1135 g_assert (!scc->flag);
1139 for (i = 0; i < dyn_array_scc_size (&sccs); ++i) {
1140 SCC *scc = dyn_array_scc_get_ptr (&sccs, i);
1141 g_assert (scc->index == i);
1142 if (!scc->num_bridge_entries)
1145 dyn_array_int_empty (&merge_array);
1148 dyn_array_int_copy (&scc->new_xrefs, &merge_array);
1149 dyn_array_int_ensure_independent (&scc->new_xrefs);
1151 #ifdef TEST_NEW_XREFS
1152 for (j = 0; j < dyn_array_scc_size (&sccs); ++j) {
1153 SCC *scc = dyn_array_scc_get_ptr (&sccs, j);
1154 g_assert (!scc->flag);
1159 #ifdef TEST_NEW_XREFS
1160 for (i = 0; i < dyn_array_scc_size (&sccs); ++i) {
1161 SCC *scc = dyn_array_scc_get_ptr (&sccs, i);
1162 g_assert (scc->index == i);
1163 if (!scc->num_bridge_entries)
1166 g_assert (dyn_array_int_size (&scc->new_xrefs) == dyn_array_int_size (&scc->old_xrefs));
1167 for (j = 0; j < dyn_array_int_size (&scc->new_xrefs); ++j)
1168 g_assert (dyn_array_int_contains (&scc->old_xrefs, dyn_array_int_get (&scc->new_xrefs, j)));
1174 * Compute the weight of each object. The weight of an object is its size plus the size of all
1175 * objects it points do. When the an object is pointed by multiple objects we distribute it's weight
1176 * equally among them. This distribution gives a rough estimate of the real impact of making the object
1179 * The reasoning for this model is that complex graphs with single roots will have a bridge with very high
1180 * value in comparison to others.
1182 * The all_entries array has all objects topologically sorted. To correctly propagate the weights it must be
1183 * done in reverse topological order - so we calculate the weight of the pointed-to objects before processing
1184 * pointer-from objects.
1186 * We log those objects in the opposite order for no particular reason. The other constrain is that it should use the same
1187 * direction as the other logging loop that records live/dead information.
1189 if (bridge_accounting_enabled) {
1190 for (i = hash_table.num_entries - 1; i >= 0; --i) {
1192 HashEntryWithAccounting *entry = (HashEntryWithAccounting*)all_entries [i];
1194 entry->weight += (double)sgen_safe_object_get_size (sgen_hash_table_key_for_value_pointer (entry));
1195 w = entry->weight / dyn_array_ptr_size (&entry->entry.srcs);
1196 for (j = 0; j < dyn_array_ptr_size (&entry->entry.srcs); ++j) {
1197 HashEntryWithAccounting *other = (HashEntryWithAccounting *)dyn_array_ptr_get (&entry->entry.srcs, j);
1201 for (i = 0; i < hash_table.num_entries; ++i) {
1202 HashEntryWithAccounting *entry = (HashEntryWithAccounting*)all_entries [i];
1203 if (entry->entry.is_bridge) {
1204 MonoObject *obj = sgen_hash_table_key_for_value_pointer (entry);
1205 MonoClass *klass = ((MonoVTable*)SGEN_LOAD_VTABLE (obj))->klass;
1206 mono_trace (G_LOG_LEVEL_INFO, MONO_TRACE_GC, "OBJECT %s::%s (%p) weight %f", klass->name_space, klass->name, obj, entry->weight);
1211 for (i = 0; i < hash_table.num_entries; ++i) {
1212 HashEntry *entry = all_entries [i];
1213 second_pass_links += dyn_array_ptr_size (&entry->srcs);
1216 SGEN_TV_GETTIME (atv);
1217 step_4 = SGEN_TV_ELAPSED (btv, atv);
1219 //g_print ("%d sccs\n", sccs.size);
1221 dyn_array_ptr_uninit (&dfs_stack);
1223 /* init data for callback */
1226 for (i = 0; i < dyn_array_scc_size (&sccs); ++i) {
1227 SCC *scc = dyn_array_scc_get_ptr (&sccs, i);
1228 g_assert (scc->index == i);
1229 if (scc->num_bridge_entries)
1231 sccs_links += dyn_array_int_size (&scc->XREFS);
1232 max_sccs_links = MAX (max_sccs_links, dyn_array_int_size (&scc->XREFS));
1235 api_sccs = sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC*) * num_sccs, INTERNAL_MEM_BRIDGE_DATA, TRUE);
1238 for (i = 0; i < dyn_array_scc_size (&sccs); ++i) {
1239 SCC *scc = dyn_array_scc_get_ptr (&sccs, i);
1240 if (!scc->num_bridge_entries)
1243 api_sccs [j] = sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC) + sizeof (MonoObject*) * scc->num_bridge_entries, INTERNAL_MEM_BRIDGE_DATA, TRUE);
1244 api_sccs [j]->is_alive = FALSE;
1245 api_sccs [j]->num_objs = scc->num_bridge_entries;
1246 scc->num_bridge_entries = 0;
1247 scc->api_index = j++;
1249 num_xrefs += dyn_array_int_size (&scc->XREFS);
1252 SGEN_HASH_TABLE_FOREACH (&hash_table, obj, entry) {
1253 if (entry->is_bridge) {
1254 SCC *scc = dyn_array_scc_get_ptr (&sccs, entry->v.dfs2.scc_index);
1255 api_sccs [scc->api_index]->objs [scc->num_bridge_entries++] = sgen_hash_table_key_for_value_pointer (entry);
1257 } SGEN_HASH_TABLE_FOREACH_END;
1259 api_xrefs = sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeXRef) * num_xrefs, INTERNAL_MEM_BRIDGE_DATA, TRUE);
1261 for (i = 0; i < dyn_array_scc_size (&sccs); ++i) {
1263 SCC *scc = dyn_array_scc_get_ptr (&sccs, i);
1264 if (!scc->num_bridge_entries)
1266 for (k = 0; k < dyn_array_int_size (&scc->XREFS); ++k) {
1267 SCC *src_scc = dyn_array_scc_get_ptr (&sccs, dyn_array_int_get (&scc->XREFS, k));
1268 if (!src_scc->num_bridge_entries)
1270 api_xrefs [j].src_scc_index = src_scc->api_index;
1271 api_xrefs [j].dst_scc_index = scc->api_index;
1276 SGEN_TV_GETTIME (btv);
1277 step_5 = SGEN_TV_ELAPSED (atv, btv);
1282 max_entries = max_xrefs = 0;
1283 for (i = 0; i < dyn_array_scc_size (&sccs); ++i) {
1284 SCC *scc = dyn_array_scc_get_ptr (&sccs, i);
1285 if (scc->num_bridge_entries)
1287 if (scc->num_bridge_entries > max_entries)
1288 max_entries = scc->num_bridge_entries;
1289 if (dyn_array_int_size (&scc->XREFS) > max_xrefs)
1290 max_xrefs = dyn_array_int_size (&scc->XREFS);
1292 dyn_array_int_uninit (&scc->new_xrefs);
1295 dyn_array_int_uninit (&scc->old_xrefs);
1299 dyn_array_scc_uninit (&sccs);
1301 sgen_free_internal_dynamic (all_entries, sizeof (HashEntry*) * hash_table.num_entries, INTERNAL_MEM_BRIDGE_DATA);
1304 /* Empty the registered bridges array */
1305 num_registered_bridges = dyn_array_ptr_size (®istered_bridges);
1306 dyn_array_ptr_empty (®istered_bridges);
1308 SGEN_TV_GETTIME (atv);
1309 step_6 = SGEN_TV_ELAPSED (btv, atv);
1311 //g_print ("%d sccs containing bridges - %d max bridge objects - %d max xrefs\n", j, max_entries, max_xrefs);
1313 bridge_processor->num_sccs = num_sccs;
1314 bridge_processor->api_sccs = api_sccs;
1315 bridge_processor->num_xrefs = num_xrefs;
1316 bridge_processor->api_xrefs = api_xrefs;
1320 processing_after_callback (int generation)
1323 int num_sccs = bridge_processor->num_sccs;
1324 MonoGCBridgeSCC **api_sccs = bridge_processor->api_sccs;
1326 if (bridge_accounting_enabled) {
1327 for (i = 0; i < num_sccs; ++i) {
1328 for (j = 0; j < api_sccs [i]->num_objs; ++j)
1329 mono_trace (G_LOG_LEVEL_INFO, MONO_TRACE_GC,
1330 "OBJECT %s (%p) SCC [%d] %s",
1331 sgen_safe_name (api_sccs [i]->objs [j]), api_sccs [i]->objs [j],
1333 api_sccs [i]->is_alive ? "ALIVE" : "DEAD");
1337 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",
1338 num_registered_bridges, hash_table_size, dyn_array_scc_size (&sccs),
1345 fist_pass_links, second_pass_links, sccs_links, max_sccs_links,
1346 dfs1_passes, dfs2_passes, ignored_objects);
1348 step_1 = 0; /* We must cleanup since this value is used as an accumulator. */
1349 fist_pass_links = second_pass_links = sccs_links = max_sccs_links = 0;
1350 dfs1_passes = dfs2_passes = ignored_objects = 0;
1354 describe_pointer (MonoObject *obj)
1359 for (i = 0; i < dyn_array_ptr_size (®istered_bridges); ++i) {
1360 if (obj == dyn_array_ptr_get (®istered_bridges, i)) {
1361 printf ("Pointer is a registered bridge object.\n");
1366 entry = sgen_hash_table_lookup (&hash_table, obj);
1370 printf ("Bridge hash table entry %p:\n", entry);
1371 printf (" is bridge: %d\n", (int)entry->is_bridge);
1372 printf (" is visited: %d\n", (int)entry->v.dfs1.is_visited);
1376 sgen_new_bridge_init (SgenBridgeProcessor *collector)
1378 collector->reset_data = reset_data;
1379 collector->processing_stw_step = processing_stw_step;
1380 collector->processing_build_callback_data = processing_build_callback_data;
1381 collector->processing_after_callback = processing_after_callback;
1382 collector->class_kind = class_kind;
1383 collector->register_finalized_object = register_finalized_object;
1384 collector->describe_pointer = describe_pointer;
1385 collector->enable_accounting = enable_accounting;
1386 collector->set_dump_prefix = set_dump_prefix;
1388 bridge_processor = collector;