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.
47 #include "sgen-bridge.h"
48 #include "sgen-hash-table.h"
49 #include "sgen-qsort.h"
50 #include "tabledefs.h"
51 #include "utils/mono-logger-internal.h"
52 #include "utils/mono-time.h"
53 #include "utils/mono-compiler.h"
78 * FIXME: Optimizations:
80 * Don't allocate a scrs array for just one source. Most objects have
81 * just one source, so use the srcs pointer itself.
83 typedef struct _HashEntry {
84 MonoObject *obj; /* This is a duplicate - it's already stored in the hash table */
99 } HashEntryWithAccounting;
101 typedef struct _SCC {
104 int num_bridge_entries;
105 DynIntArray xrefs; /* these are incoming, not outgoing */
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 int current_time;
112 static gboolean bridge_accounting_enabled = FALSE;
121 dyn_array_init (DynArray *da)
129 dyn_array_uninit (DynArray *da, int elem_size)
131 if (da->capacity <= 0)
134 sgen_free_internal_dynamic (da->data, elem_size * da->capacity, INTERNAL_MEM_BRIDGE_DATA);
139 dyn_array_ensure_capacity (DynArray *da, int capacity, int elem_size)
141 int old_capacity = da->capacity;
144 if (capacity <= old_capacity)
147 if (da->capacity == 0)
149 while (capacity > da->capacity)
152 new_data = sgen_alloc_internal_dynamic (elem_size * da->capacity, INTERNAL_MEM_BRIDGE_DATA, TRUE);
153 memcpy (new_data, da->data, elem_size * da->size);
154 sgen_free_internal_dynamic (da->data, elem_size * old_capacity, INTERNAL_MEM_BRIDGE_DATA);
159 dyn_array_add (DynArray *da, int elem_size)
163 dyn_array_ensure_capacity (da, da->size + 1, elem_size);
165 p = da->data + da->size * elem_size;
172 dyn_array_int_init (DynIntArray *da)
174 dyn_array_init (&da->array);
178 dyn_array_int_uninit (DynIntArray *da)
180 dyn_array_uninit (&da->array, sizeof (int));
184 dyn_array_int_size (DynIntArray *da)
186 return da->array.size;
190 dyn_array_int_set_size (DynIntArray *da, int size)
192 da->array.size = size;
196 dyn_array_int_add (DynIntArray *da, int x)
198 int *p = dyn_array_add (&da->array, sizeof (int));
203 dyn_array_int_get (DynIntArray *da, int x)
205 return ((int*)da->array.data)[x];
209 dyn_array_int_set (DynIntArray *da, int idx, int val)
211 ((int*)da->array.data)[idx] = val;
215 dyn_array_int_ensure_capacity (DynIntArray *da, int capacity)
217 dyn_array_ensure_capacity (&da->array, capacity, sizeof (int));
221 dyn_array_int_set_all (DynIntArray *dst, DynIntArray *src)
223 dyn_array_int_ensure_capacity (dst, src->array.size);
224 memcpy (dst->array.data, src->array.data, src->array.size * sizeof (int));
225 dst->array.size = src->array.size;
231 dyn_array_ptr_init (DynPtrArray *da)
233 dyn_array_init (&da->array);
237 dyn_array_ptr_uninit (DynPtrArray *da)
239 dyn_array_uninit (&da->array, sizeof (void*));
243 dyn_array_ptr_size (DynPtrArray *da)
245 return da->array.size;
249 dyn_array_ptr_set_size (DynPtrArray *da, int size)
251 da->array.size = size;
255 dyn_array_ptr_get (DynPtrArray *da, int x)
257 return ((void**)da->array.data)[x];
261 dyn_array_ptr_add (DynPtrArray *da, void *ptr)
263 void **p = dyn_array_add (&da->array, sizeof (void*));
267 #define dyn_array_ptr_push dyn_array_ptr_add
270 dyn_array_ptr_pop (DynPtrArray *da)
273 int size = da->array.size;
275 p = dyn_array_ptr_get (da, size - 1);
283 dyn_array_scc_init (DynSCCArray *da)
285 dyn_array_init (&da->array);
289 dyn_array_scc_uninit (DynSCCArray *da)
291 dyn_array_uninit (&da->array, sizeof (SCC));
295 dyn_array_scc_size (DynSCCArray *da)
297 return da->array.size;
301 dyn_array_scc_add (DynSCCArray *da)
303 return dyn_array_add (&da->array, sizeof (SCC));
307 dyn_array_scc_get_ptr (DynSCCArray *da, int x)
309 return &((SCC*)da->array.data)[x];
314 static DynIntArray merge_array;
317 dyn_array_int_contains (DynIntArray *da, int x)
320 for (i = 0; i < dyn_array_int_size (da); ++i)
321 if (dyn_array_int_get (da, i) == x)
328 dyn_array_int_merge (DynIntArray *dst, DynIntArray *src)
332 dyn_array_int_ensure_capacity (&merge_array, dyn_array_int_size (dst) + dyn_array_int_size (src));
333 dyn_array_int_set_size (&merge_array, 0);
335 for (i = j = 0; i < dyn_array_int_size (dst) || j < dyn_array_int_size (src); ) {
336 if (i < dyn_array_int_size (dst) && j < dyn_array_int_size (src)) {
337 int a = dyn_array_int_get (dst, i);
338 int b = dyn_array_int_get (src, j);
340 dyn_array_int_add (&merge_array, a);
343 dyn_array_int_add (&merge_array, a);
347 dyn_array_int_add (&merge_array, b);
350 } else if (i < dyn_array_int_size (dst)) {
351 dyn_array_int_add (&merge_array, dyn_array_int_get (dst, i));
354 dyn_array_int_add (&merge_array, dyn_array_int_get (src, j));
359 if (dyn_array_int_size (&merge_array) > dyn_array_int_size (dst)) {
360 dyn_array_int_set_all (dst, &merge_array);
365 dyn_array_int_merge_one (DynIntArray *array, int value)
369 int size = dyn_array_int_size (array);
371 for (i = 0; i < size; ++i) {
372 if (dyn_array_int_get (array, i) == value)
374 else if (dyn_array_int_get (array, i) > value)
378 dyn_array_int_ensure_capacity (array, size + 1);
381 tmp = dyn_array_int_get (array, i);
382 for (; i < size; ++i) {
383 dyn_array_int_set (array, i, value);
385 tmp = dyn_array_int_get (array, i + 1);
387 dyn_array_int_set (array, size, value);
389 dyn_array_int_set (array, size, value);
392 dyn_array_int_set_size (array, size + 1);
397 enable_accounting (void)
399 bridge_accounting_enabled = TRUE;
400 hash_table = (SgenHashTable)SGEN_HASH_TABLE_INIT (INTERNAL_MEM_BRIDGE_HASH_TABLE, INTERNAL_MEM_BRIDGE_HASH_TABLE_ENTRY, sizeof (HashEntryWithAccounting), mono_aligned_addr_hash, NULL);
403 static MonoGCBridgeObjectKind
404 class_kind (MonoClass *class)
406 MonoGCBridgeObjectKind res = bridge_callbacks.bridge_class_kind (class);
408 /* If it's a bridge, nothing we can do about it. */
409 if (res == GC_BRIDGE_TRANSPARENT_BRIDGE_CLASS || res == GC_BRIDGE_OPAQUE_BRIDGE_CLASS)
412 /* Non bridge classes with no pointers will never point to a bridge, so we can savely ignore them. */
413 if (!class->has_references) {
414 SGEN_LOG (6, "class %s is opaque\n", class->name);
415 return GC_BRIDGE_OPAQUE_CLASS;
418 /* Some arrays can be ignored */
419 if (class->rank == 1) {
420 MonoClass *elem_class = class->element_class;
422 /* FIXME the bridge check can be quite expensive, cache it at the class level. */
423 /* An array of a sealed type that is not a bridge will never get to a bridge */
424 if ((elem_class->flags & TYPE_ATTRIBUTE_SEALED) && !elem_class->has_references && !bridge_callbacks.bridge_class_kind (elem_class)) {
425 SGEN_LOG (6, "class %s is opaque\n", class->name);
426 return GC_BRIDGE_OPAQUE_CLASS;
430 return GC_BRIDGE_TRANSPARENT_CLASS;
434 get_hash_entry (MonoObject *obj, gboolean *existing)
436 HashEntry *entry = sgen_hash_table_lookup (&hash_table, obj);
447 memset (&new_entry, 0, sizeof (HashEntry));
450 dyn_array_ptr_init (&new_entry.srcs);
451 new_entry.finishing_time = -1;
452 new_entry.scc_index = -1;
454 sgen_hash_table_replace (&hash_table, obj, &new_entry, NULL);
456 return sgen_hash_table_lookup (&hash_table, obj);
460 add_source (HashEntry *entry, HashEntry *src)
462 dyn_array_ptr_add (&entry->srcs, src);
473 SGEN_HASH_TABLE_FOREACH (&hash_table, obj, entry) {
474 int entry_size = dyn_array_ptr_size (&entry->srcs);
475 total_srcs += entry_size;
476 if (entry_size > max_srcs)
477 max_srcs = entry_size;
478 dyn_array_ptr_uninit (&entry->srcs);
479 } SGEN_HASH_TABLE_FOREACH_END;
481 sgen_hash_table_clean (&hash_table);
483 dyn_array_int_uninit (&merge_array);
484 //g_print ("total srcs %d - max %d\n", total_srcs, max_srcs);
488 register_bridge_object (MonoObject *obj)
490 HashEntry *entry = get_hash_entry (obj, NULL);
491 entry->is_bridge = TRUE;
496 register_finishing_time (HashEntry *entry, int t)
498 g_assert (entry->finishing_time < 0);
499 entry->finishing_time = t;
502 static int ignored_objects;
505 is_opaque_object (MonoObject *obj)
507 if ((obj->vtable->gc_bits & SGEN_GC_BIT_BRIDGE_OPAQUE_OBJECT) == SGEN_GC_BIT_BRIDGE_OPAQUE_OBJECT) {
508 SGEN_LOG (6, "ignoring %s\n", obj->vtable->klass->name);
516 object_is_live (MonoObject **objp)
518 MonoObject *obj = *objp;
519 MonoObject *fwd = SGEN_OBJECT_IS_FORWARDED (obj);
522 if (is_opaque_object (fwd))
524 return sgen_hash_table_lookup (&hash_table, fwd) == NULL;
526 if (is_opaque_object (obj))
528 if (!sgen_object_is_live (obj))
530 return sgen_hash_table_lookup (&hash_table, obj) == NULL;
533 static DynPtrArray registered_bridges;
534 static DynPtrArray dfs_stack;
536 static int dfs1_passes, dfs2_passes;
540 #define HANDLE_PTR(ptr,obj) do { \
541 MonoObject *dst = (MonoObject*)*(ptr); \
542 if (dst && !object_is_live (&dst)) { \
543 dyn_array_ptr_push (&dfs_stack, obj_entry); \
544 dyn_array_ptr_push (&dfs_stack, get_hash_entry (dst, NULL)); \
549 dfs1 (HashEntry *obj_entry)
552 g_assert (dyn_array_ptr_size (&dfs_stack) == 0);
554 dyn_array_ptr_push (&dfs_stack, NULL);
555 dyn_array_ptr_push (&dfs_stack, obj_entry);
562 obj_entry = dyn_array_ptr_pop (&dfs_stack);
564 src = dyn_array_ptr_pop (&dfs_stack);
566 obj = obj_entry->obj;
570 //g_print ("link %s -> %s\n", sgen_safe_name (src->obj), sgen_safe_name (obj));
571 add_source (obj_entry, src);
573 //g_print ("starting with %s\n", sgen_safe_name (obj));
576 if (obj_entry->is_visited)
579 obj_entry->is_visited = TRUE;
581 dyn_array_ptr_push (&dfs_stack, obj_entry);
582 /* NULL marks that the next entry is to be finished */
583 dyn_array_ptr_push (&dfs_stack, NULL);
585 #include "sgen-scan-object.h"
587 obj_entry = dyn_array_ptr_pop (&dfs_stack);
589 //g_print ("finish %s\n", sgen_safe_name (obj_entry->obj));
590 register_finishing_time (obj_entry, current_time++);
592 } while (dyn_array_ptr_size (&dfs_stack) > 0);
596 scc_add_xref (SCC *src, SCC *dst)
598 g_assert (src != dst);
599 g_assert (src->index != dst->index);
601 if (dyn_array_int_contains (&dst->xrefs, src->index))
603 if (src->num_bridge_entries) {
604 dyn_array_int_merge_one (&dst->xrefs, src->index);
607 dyn_array_int_merge (&dst->xrefs, &src->xrefs);
608 for (i = 0; i < dyn_array_int_size (&dst->xrefs); ++i)
609 g_assert (dyn_array_int_get (&dst->xrefs, i) != dst->index);
614 scc_add_entry (SCC *scc, HashEntry *entry)
616 g_assert (entry->scc_index < 0);
617 entry->scc_index = scc->index;
618 if (entry->is_bridge)
619 ++scc->num_bridge_entries;
622 static DynSCCArray sccs;
623 static SCC *current_scc;
626 dfs2 (HashEntry *entry)
630 g_assert (dyn_array_ptr_size (&dfs_stack) == 0);
632 dyn_array_ptr_push (&dfs_stack, entry);
635 entry = dyn_array_ptr_pop (&dfs_stack);
638 if (entry->scc_index >= 0) {
639 if (entry->scc_index != current_scc->index)
640 scc_add_xref (dyn_array_scc_get_ptr (&sccs, entry->scc_index), current_scc);
644 scc_add_entry (current_scc, entry);
646 for (i = 0; i < dyn_array_ptr_size (&entry->srcs); ++i)
647 dyn_array_ptr_push (&dfs_stack, dyn_array_ptr_get (&entry->srcs, i));
648 } while (dyn_array_ptr_size (&dfs_stack) > 0);
652 compare_hash_entries (const HashEntry *e1, const HashEntry *e2)
654 return e2->finishing_time - e1->finishing_time;
657 DEF_QSORT_INLINE(hash_entries, HashEntry*, compare_hash_entries)
659 static unsigned long step_1, step_2, step_3, step_4, step_5, step_6, step_7, step_8;
660 static int fist_pass_links, second_pass_links, sccs_links;
661 static int max_sccs_links = 0;
664 register_finalized_object (MonoObject *obj)
666 g_assert (sgen_need_bridge_processing ());
667 dyn_array_ptr_push (®istered_bridges, obj);
673 dyn_array_ptr_set_size (®istered_bridges, 0);
677 processing_stw_step (void)
681 SGEN_TV_DECLARE (atv);
682 SGEN_TV_DECLARE (btv);
684 if (!dyn_array_ptr_size (®istered_bridges))
688 * bridge_processing_in_progress must be set with the world
689 * stopped. If not there would be race conditions.
691 bridge_processing_in_progress = TRUE;
693 SGEN_TV_GETTIME (btv);
697 dyn_array_ptr_init (&dfs_stack);
698 dyn_array_int_init (&merge_array);
702 First we insert all bridges into the hash table and then we do dfs1.
704 It must be done in 2 steps since the bridge arrays doesn't come in reverse topological order,
705 which means that we can have entry N pointing to entry N + 1.
707 If we dfs1 entry N before N + 1 is registered we'll not consider N + 1 for this bridge
708 pass and not create the required xref between the two.
710 bridge_count = dyn_array_ptr_size (®istered_bridges);
711 for (i = 0; i < bridge_count ; ++i)
712 register_bridge_object (dyn_array_ptr_get (®istered_bridges, i));
714 for (i = 0; i < bridge_count; ++i)
715 dfs1 (get_hash_entry (dyn_array_ptr_get (®istered_bridges, i), NULL));
717 SGEN_TV_GETTIME (atv);
718 step_2 = SGEN_TV_ELAPSED (btv, atv);
722 is_bridge_object_alive (MonoObject *obj, void *data)
724 SgenHashTable *table = data;
725 unsigned char *value = sgen_hash_table_lookup (table, obj);
732 processing_finish (int generation)
735 int num_sccs, num_xrefs;
736 int max_entries, max_xrefs;
737 int hash_table_size, sccs_size;
740 int num_registered_bridges;
741 HashEntry **all_entries;
742 MonoGCBridgeSCC **api_sccs;
743 MonoGCBridgeXRef *api_xrefs;
744 SgenHashTable alive_hash = SGEN_HASH_TABLE_INIT (INTERNAL_MEM_BRIDGE_ALIVE_HASH_TABLE, INTERNAL_MEM_BRIDGE_ALIVE_HASH_TABLE_ENTRY, 1, mono_aligned_addr_hash, NULL);
745 SGEN_TV_DECLARE (atv);
746 SGEN_TV_DECLARE (btv);
748 if (!dyn_array_ptr_size (®istered_bridges))
751 g_assert (bridge_processing_in_progress);
753 SGEN_TV_GETTIME (atv);
755 /* alloc and fill array of all entries */
757 all_entries = sgen_alloc_internal_dynamic (sizeof (HashEntry*) * hash_table.num_entries, INTERNAL_MEM_BRIDGE_DATA, TRUE);
760 SGEN_HASH_TABLE_FOREACH (&hash_table, obj, entry) {
761 g_assert (entry->finishing_time >= 0);
762 all_entries [j++] = entry;
763 fist_pass_links += dyn_array_ptr_size (&entry->srcs);
764 } SGEN_HASH_TABLE_FOREACH_END;
765 g_assert (j == hash_table.num_entries);
766 hash_table_size = hash_table.num_entries;
768 /* sort array according to decreasing finishing time */
769 qsort_hash_entries (all_entries, hash_table.num_entries);
771 SGEN_TV_GETTIME (btv);
772 step_3 = SGEN_TV_ELAPSED (atv, btv);
774 /* second DFS pass */
776 dyn_array_scc_init (&sccs);
777 for (i = 0; i < hash_table.num_entries; ++i) {
778 HashEntry *entry = all_entries [i];
779 if (entry->scc_index < 0) {
780 int index = dyn_array_scc_size (&sccs);
781 current_scc = dyn_array_scc_add (&sccs);
782 current_scc->index = index;
783 current_scc->num_bridge_entries = 0;
784 current_scc->api_index = -1;
785 dyn_array_int_init (¤t_scc->xrefs);
792 * Compute the weight of each object. The weight of an object is its size plus the size of all
793 * objects it points do. When the an object is pointed by multiple objects we distribute it's weight
794 * equally among them. This distribution gives a rough estimate of the real impact of making the object
797 * The reasoning for this model is that complex graphs with single roots will have a bridge with very high
798 * value in comparison to others.
800 * The all_entries array has all objects topologically sorted. To correctly propagate the weights it must be
801 * done in reverse topological order - so we calculate the weight of the pointed-to objects before processing
802 * pointer-from objects.
804 * We log those objects in the opposite order for no particular reason. The other constrain is that it should use the same
805 * direction as the other logging loop that records live/dead information.
807 if (bridge_accounting_enabled) {
808 for (i = hash_table.num_entries - 1; i >= 0; --i) {
810 HashEntryWithAccounting *entry = (HashEntryWithAccounting*)all_entries [i];
812 entry->weight += (double)sgen_safe_object_get_size (entry->entry.obj);
813 w = entry->weight / dyn_array_ptr_size (&entry->entry.srcs);
814 for (j = 0; j < dyn_array_ptr_size (&entry->entry.srcs); ++j) {
815 HashEntryWithAccounting *other = (HashEntryWithAccounting *)dyn_array_ptr_get (&entry->entry.srcs, j);
819 for (i = 0; i < hash_table.num_entries; ++i) {
820 HashEntryWithAccounting *entry = (HashEntryWithAccounting*)all_entries [i];
821 if (entry->entry.is_bridge) {
822 MonoClass *klass = ((MonoVTable*)SGEN_LOAD_VTABLE (entry->entry.obj))->klass;
823 mono_trace (G_LOG_LEVEL_INFO, MONO_TRACE_GC, "OBJECT %s::%s (%p) weight %f", klass->name_space, klass->name, entry->entry.obj, entry->weight);
828 sccs_size = dyn_array_scc_size (&sccs);
830 for (i = 0; i < hash_table.num_entries; ++i) {
831 HashEntry *entry = all_entries [i];
832 second_pass_links += dyn_array_ptr_size (&entry->srcs);
835 SGEN_TV_GETTIME (atv);
836 step_4 = SGEN_TV_ELAPSED (btv, atv);
838 //g_print ("%d sccs\n", sccs.size);
840 dyn_array_ptr_uninit (&dfs_stack);
842 /* init data for callback */
845 for (i = 0; i < dyn_array_scc_size (&sccs); ++i) {
846 SCC *scc = dyn_array_scc_get_ptr (&sccs, i);
847 g_assert (scc->index == i);
848 if (scc->num_bridge_entries)
850 sccs_links += dyn_array_int_size (&scc->xrefs);
851 max_sccs_links = MAX (max_sccs_links, dyn_array_int_size (&scc->xrefs));
854 api_sccs = sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC*) * num_sccs, INTERNAL_MEM_BRIDGE_DATA, TRUE);
857 for (i = 0; i < dyn_array_scc_size (&sccs); ++i) {
858 SCC *scc = dyn_array_scc_get_ptr (&sccs, i);
859 if (!scc->num_bridge_entries)
862 api_sccs [j] = sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC) + sizeof (MonoObject*) * scc->num_bridge_entries, INTERNAL_MEM_BRIDGE_DATA, TRUE);
863 api_sccs [j]->is_alive = FALSE;
864 api_sccs [j]->num_objs = scc->num_bridge_entries;
865 scc->num_bridge_entries = 0;
866 scc->api_index = j++;
868 num_xrefs += dyn_array_int_size (&scc->xrefs);
871 SGEN_HASH_TABLE_FOREACH (&hash_table, obj, entry) {
872 if (entry->is_bridge) {
873 SCC *scc = dyn_array_scc_get_ptr (&sccs, entry->scc_index);
874 api_sccs [scc->api_index]->objs [scc->num_bridge_entries++] = entry->obj;
876 } SGEN_HASH_TABLE_FOREACH_END;
878 api_xrefs = sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeXRef) * num_xrefs, INTERNAL_MEM_BRIDGE_DATA, TRUE);
880 for (i = 0; i < dyn_array_scc_size (&sccs); ++i) {
882 SCC *scc = dyn_array_scc_get_ptr (&sccs, i);
883 if (!scc->num_bridge_entries)
885 for (k = 0; k < dyn_array_int_size (&scc->xrefs); ++k) {
886 SCC *src_scc = dyn_array_scc_get_ptr (&sccs, dyn_array_int_get (&scc->xrefs, k));
887 if (!src_scc->num_bridge_entries)
889 api_xrefs [j].src_scc_index = src_scc->api_index;
890 api_xrefs [j].dst_scc_index = scc->api_index;
895 SGEN_TV_GETTIME (btv);
896 step_5 = SGEN_TV_ELAPSED (atv, btv);
901 max_entries = max_xrefs = 0;
902 for (i = 0; i < dyn_array_scc_size (&sccs); ++i) {
903 SCC *scc = dyn_array_scc_get_ptr (&sccs, i);
904 if (scc->num_bridge_entries)
906 if (scc->num_bridge_entries > max_entries)
907 max_entries = scc->num_bridge_entries;
908 if (dyn_array_int_size (&scc->xrefs) > max_xrefs)
909 max_xrefs = dyn_array_int_size (&scc->xrefs);
910 dyn_array_int_uninit (&scc->xrefs);
913 dyn_array_scc_uninit (&sccs);
915 sgen_free_internal_dynamic (all_entries, sizeof (HashEntry*) * hash_table.num_entries, INTERNAL_MEM_BRIDGE_DATA);
918 /* Empty the registered bridges array */
919 num_registered_bridges = dyn_array_ptr_size (®istered_bridges);
920 dyn_array_ptr_set_size (®istered_bridges, 0);
922 SGEN_TV_GETTIME (atv);
923 step_6 = SGEN_TV_ELAPSED (btv, atv);
925 //g_print ("%d sccs containing bridges - %d max bridge objects - %d max xrefs\n", j, max_entries, max_xrefs);
929 bridge_callbacks.cross_references (num_sccs, api_sccs, num_xrefs, api_xrefs);
931 /* Release for finalization those objects we no longer care. */
932 SGEN_TV_GETTIME (btv);
933 step_7 = SGEN_TV_ELAPSED (atv, btv);
935 for (i = 0; i < num_sccs; ++i) {
936 unsigned char alive = api_sccs [i]->is_alive ? 1 : 0;
937 for (j = 0; j < api_sccs [i]->num_objs; ++j) {
938 /* Build hash table for nulling weak links. */
939 sgen_hash_table_replace (&alive_hash, api_sccs [i]->objs [j], &alive, NULL);
941 /* Release for finalization those objects we no longer care. */
942 if (!api_sccs [i]->is_alive)
943 sgen_mark_bridge_object (api_sccs [i]->objs [j]);
947 /* Null weak links to dead objects. */
948 sgen_null_links_with_predicate (GENERATION_NURSERY, is_bridge_object_alive, &alive_hash);
949 if (generation == GENERATION_OLD)
950 sgen_null_links_with_predicate (GENERATION_OLD, is_bridge_object_alive, &alive_hash);
952 sgen_hash_table_clean (&alive_hash);
954 if (bridge_accounting_enabled) {
955 for (i = 0; i < num_sccs; ++i) {
956 for (j = 0; j < api_sccs [i]->num_objs; ++j)
957 mono_trace (G_LOG_LEVEL_INFO, MONO_TRACE_GC,
958 "OBJECT %s (%p) SCC [%d] %s",
959 sgen_safe_name (api_sccs [i]->objs [j]), api_sccs [i]->objs [j],
961 api_sccs [i]->is_alive ? "ALIVE" : "DEAD");
965 /* free callback data */
967 for (i = 0; i < num_sccs; ++i) {
968 sgen_free_internal_dynamic (api_sccs [i],
969 sizeof (MonoGCBridgeSCC) + sizeof (MonoObject*) * api_sccs [i]->num_objs,
970 INTERNAL_MEM_BRIDGE_DATA);
972 sgen_free_internal_dynamic (api_sccs, sizeof (MonoGCBridgeSCC*) * num_sccs, INTERNAL_MEM_BRIDGE_DATA);
974 sgen_free_internal_dynamic (api_xrefs, sizeof (MonoGCBridgeXRef) * num_xrefs, INTERNAL_MEM_BRIDGE_DATA);
976 SGEN_TV_GETTIME (atv);
977 step_8 = SGEN_TV_ELAPSED (btv, atv);
979 mono_trace (G_LOG_LEVEL_INFO, MONO_TRACE_GC, "GC_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 user-cb %.2fms clenanup %.2fms links %d/%d/%d/%d dfs passes %d/%d ignored %d",
980 num_registered_bridges, hash_table_size, dyn_array_scc_size (&sccs),
989 fist_pass_links, second_pass_links, sccs_links, max_sccs_links,
990 dfs1_passes, dfs2_passes, ignored_objects);
992 step_1 = 0; /* We must cleanup since this value is used as an accumulator. */
993 fist_pass_links = second_pass_links = sccs_links = max_sccs_links = 0;
994 dfs1_passes = dfs2_passes = ignored_objects = 0;
996 bridge_processing_in_progress = FALSE;
1000 describe_pointer (MonoObject *obj)
1005 for (i = 0; i < dyn_array_ptr_size (®istered_bridges); ++i) {
1006 if (obj == dyn_array_ptr_get (®istered_bridges, i)) {
1007 printf ("Pointer is a registered bridge object.\n");
1012 entry = sgen_hash_table_lookup (&hash_table, obj);
1016 printf ("Bridge hash table entry %p:\n", entry);
1017 printf (" is bridge: %d\n", (int)entry->is_bridge);
1018 printf (" is visited: %d\n", (int)entry->is_visited);
1022 sgen_new_bridge_init (SgenBridgeProcessor *collector)
1024 collector->reset_data = reset_data;
1025 collector->processing_stw_step = processing_stw_step;
1026 collector->processing_finish = processing_finish;
1027 collector->class_kind = class_kind;
1028 collector->register_finalized_object = register_finalized_object;
1029 collector->describe_pointer = describe_pointer;
1030 collector->enable_accounting = enable_accounting;