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 "utils/mono-logger-internal.h"
49 #include "utils/mono-time.h"
59 #define DYN_ARRAY_REF(da,i) ((void*)((da)->data + (i) * (da)->elem_size))
60 #define DYN_ARRAY_PTR_REF(da,i) (((void**)(da)->data) [(i)])
61 #define DYN_ARRAY_INT_REF(da,i) (((int*)(da)->data) [(i)])
62 #define DYN_ARRAY_PTR_STATIC_INITIALIZER { 0, sizeof (void*), 0, NULL }
63 #define DYN_ARRAY_INT_STATIC_INITIALIZER { 0, sizeof (int), 0, NULL }
66 dyn_array_init (DynArray *da, int elem_size)
69 da->elem_size = elem_size;
75 dyn_array_ptr_init (DynArray *da)
77 dyn_array_init (da, sizeof (void*));
81 dyn_array_int_init (DynArray *da)
83 dyn_array_init (da, sizeof (int));
87 dyn_array_uninit (DynArray *da)
89 if (da->capacity <= 0)
92 mono_sgen_free_internal_dynamic (da->data, da->elem_size * da->capacity, INTERNAL_MEM_BRIDGE_DATA);
97 dyn_array_ensure_capacity (DynArray *da, int capacity)
99 int old_capacity = da->capacity;
102 if (capacity <= old_capacity)
105 if (da->capacity == 0)
107 while (capacity > da->capacity)
110 new_data = mono_sgen_alloc_internal_dynamic (da->elem_size * da->capacity, INTERNAL_MEM_BRIDGE_DATA);
111 memcpy (new_data, da->data, da->elem_size * da->size);
112 mono_sgen_free_internal_dynamic (da->data, da->elem_size * old_capacity, INTERNAL_MEM_BRIDGE_DATA);
117 dyn_array_add (DynArray *da)
121 dyn_array_ensure_capacity (da, da->size + 1);
123 p = DYN_ARRAY_REF (da, da->size);
129 dyn_array_ptr_add (DynArray *da, void *ptr)
131 void **p = dyn_array_add (da);
135 #define dyn_array_ptr_push dyn_array_ptr_add
138 dyn_array_ptr_pop (DynArray *da)
141 g_assert (da->size > 0);
142 p = DYN_ARRAY_PTR_REF (da, da->size - 1);
148 dyn_array_int_add (DynArray *da, int x)
150 int *p = dyn_array_add (da);
156 dyn_array_ptr_contains (DynArray *da, void *ptr)
159 for (i = 0; i < da->size; ++i)
160 if (DYN_ARRAY_PTR_REF (da, i) == ptr)
167 dyn_array_int_contains (DynArray *da, int x)
170 for (i = 0; i < da->size; ++i)
171 if (DYN_ARRAY_INT_REF (da, i) == x)
176 static DynArray merge_array;
179 dyn_array_int_merge (DynArray *dst, DynArray *src)
183 dyn_array_ensure_capacity (&merge_array, dst->size + src->size);
184 merge_array.size = 0;
186 for (i = j = 0; i < dst->size || j < src->size; ) {
187 if (i < dst->size && j < src->size) {
188 int a = DYN_ARRAY_INT_REF (dst, i);
189 int b = DYN_ARRAY_INT_REF (src, j);
191 dyn_array_int_add (&merge_array, a);
194 dyn_array_int_add (&merge_array, a);
198 dyn_array_int_add (&merge_array, b);
201 } else if (i < dst->size) {
202 dyn_array_int_add (&merge_array, DYN_ARRAY_INT_REF (dst, i));
205 dyn_array_int_add (&merge_array, DYN_ARRAY_INT_REF (src, j));
210 if (merge_array.size > dst->size) {
211 dyn_array_ensure_capacity (dst, merge_array.size);
212 memcpy (DYN_ARRAY_REF (dst, 0), DYN_ARRAY_REF (&merge_array, 0), merge_array.size * merge_array.elem_size);
213 dst->size = merge_array.size;
218 dyn_array_int_merge_one (DynArray *array, int value)
222 int end = array->size;
224 for (i = 0; i < end; ++i) {
225 if (DYN_ARRAY_INT_REF (array, i) == value)
227 else if (DYN_ARRAY_INT_REF (array, i) > value)
231 dyn_array_ensure_capacity (array, array->size + 1);
234 tmp = DYN_ARRAY_INT_REF (array, i);
235 for (; i <= end; ++i) {
236 DYN_ARRAY_INT_REF (array, i) = value;
238 tmp = DYN_ARRAY_INT_REF (array, i + 1);
240 DYN_ARRAY_INT_REF (array, end + 1) = tmp;
242 DYN_ARRAY_INT_REF (array, end) = value;
248 * FIXME: Optimizations:
250 * Don't allocate a scrs array for just one source. Most objects have
251 * just one source, so use the srcs pointer itself.
253 typedef struct _HashEntry {
254 MonoObject *obj; /* This is a duplicate - it's already stored in the hash table */
266 typedef struct _SCC {
269 int num_bridge_entries;
270 DynArray xrefs; /* these are incoming, not outgoing */
273 static SgenHashTable hash_table = SGEN_HASH_TABLE_INIT (INTERNAL_MEM_BRIDGE_DATA, INTERNAL_MEM_BRIDGE_DATA, sizeof (HashEntry), mono_aligned_addr_hash, NULL);
275 static MonoGCBridgeCallbacks bridge_callbacks;
277 static int current_time;
280 mono_gc_register_bridge_callbacks (MonoGCBridgeCallbacks *callbacks)
282 if (callbacks->bridge_version != MONO_SGEN_BRIDGE_VERSION) {
283 fprintf (stderr, "Invalid bridge callback version. Expected %d but got %d\n", MONO_SGEN_BRIDGE_VERSION, callbacks->bridge_version);
286 bridge_callbacks = *callbacks;
290 mono_sgen_is_bridge_object (MonoObject *obj)
292 return (obj->vtable->gc_bits & SGEN_GC_BIT_BRIDGE_OBJECT) == SGEN_GC_BIT_BRIDGE_OBJECT;
296 mono_sgen_is_bridge_class (MonoClass *class)
298 return bridge_callbacks.is_bridge_class (class);
302 mono_sgen_need_bridge_processing (void)
304 return bridge_callbacks.cross_references != NULL;
308 get_hash_entry (MonoObject *obj, gboolean *existing)
310 HashEntry *entry = mono_sgen_hash_table_lookup (&hash_table, obj);
321 memset (&new_entry, 0, sizeof (HashEntry));
324 dyn_array_ptr_init (&new_entry.srcs);
325 new_entry.finishing_time = -1;
326 new_entry.scc_index = -1;
328 mono_sgen_hash_table_replace (&hash_table, obj, &new_entry);
330 return mono_sgen_hash_table_lookup (&hash_table, obj);
334 add_source (HashEntry *entry, HashEntry *src)
336 dyn_array_ptr_add (&entry->srcs, src);
347 SGEN_HASH_TABLE_FOREACH (&hash_table, obj, entry) {
348 total_srcs += entry->srcs.size;
349 if (entry->srcs.size > max_srcs)
350 max_srcs = entry->srcs.size;
351 dyn_array_uninit (&entry->srcs);
352 } SGEN_HASH_TABLE_FOREACH_END;
354 mono_sgen_hash_table_clean (&hash_table);
356 dyn_array_uninit (&merge_array);
357 //g_print ("total srcs %d - max %d\n", total_srcs, max_srcs);
361 register_bridge_object (MonoObject *obj)
363 HashEntry *entry = get_hash_entry (obj, NULL);
364 entry->is_bridge = TRUE;
369 register_finishing_time (HashEntry *entry, int t)
371 g_assert (entry->finishing_time < 0);
372 entry->finishing_time = t;
376 object_is_live (MonoObject **objp)
378 MonoObject *obj = *objp;
379 MonoObject *fwd = SGEN_OBJECT_IS_FORWARDED (obj);
382 return mono_sgen_hash_table_lookup (&hash_table, fwd) == NULL;
384 if (!mono_sgen_object_is_live (obj))
386 return mono_sgen_hash_table_lookup (&hash_table, obj) == NULL;
389 static DynArray registered_bridges = DYN_ARRAY_PTR_STATIC_INITIALIZER;
390 static DynArray dfs_stack;
392 static int dsf1_passes, dsf2_passes;
396 #define HANDLE_PTR(ptr,obj) do { \
397 MonoObject *dst = (MonoObject*)*(ptr); \
398 if (dst && !object_is_live (&dst)) { \
399 dyn_array_ptr_push (&dfs_stack, obj_entry); \
400 dyn_array_ptr_push (&dfs_stack, get_hash_entry (dst, NULL)); \
405 dfs1 (HashEntry *obj_entry, HashEntry *src)
407 g_assert (dfs_stack.size == 0);
409 dyn_array_ptr_push (&dfs_stack, src);
410 dyn_array_ptr_push (&dfs_stack, obj_entry);
417 obj_entry = dyn_array_ptr_pop (&dfs_stack);
419 src = dyn_array_ptr_pop (&dfs_stack);
421 obj = obj_entry->obj;
425 //g_print ("link %s -> %s\n", mono_sgen_safe_name (src->obj), mono_sgen_safe_name (obj));
426 add_source (obj_entry, src);
428 //g_print ("starting with %s\n", mono_sgen_safe_name (obj));
431 if (obj_entry->is_visited)
434 obj_entry->is_visited = TRUE;
436 dyn_array_ptr_push (&dfs_stack, obj_entry);
437 /* NULL marks that the next entry is to be finished */
438 dyn_array_ptr_push (&dfs_stack, NULL);
440 #include "sgen-scan-object.h"
442 obj_entry = dyn_array_ptr_pop (&dfs_stack);
444 //g_print ("finish %s\n", mono_sgen_safe_name (obj_entry->obj));
445 register_finishing_time (obj_entry, current_time++);
447 } while (dfs_stack.size > 0);
451 scc_add_xref (SCC *src, SCC *dst)
453 g_assert (src != dst);
454 g_assert (src->index != dst->index);
456 if (dyn_array_int_contains (&dst->xrefs, src->index))
458 if (src->num_bridge_entries) {
459 dyn_array_int_merge_one (&dst->xrefs, src->index);
462 dyn_array_int_merge (&dst->xrefs, &src->xrefs);
463 for (i = 0; i < dst->xrefs.size; ++i)
464 g_assert (DYN_ARRAY_INT_REF (&dst->xrefs, i) != dst->index);
469 scc_add_entry (SCC *scc, HashEntry *entry)
471 g_assert (entry->scc_index < 0);
472 entry->scc_index = scc->index;
473 if (entry->is_bridge)
474 ++scc->num_bridge_entries;
477 static DynArray sccs;
478 static SCC *current_scc;
481 dfs2 (HashEntry *entry)
485 g_assert (dfs_stack.size == 0);
487 dyn_array_ptr_push (&dfs_stack, entry);
490 entry = dyn_array_ptr_pop (&dfs_stack);
493 if (entry->scc_index >= 0) {
494 if (entry->scc_index != current_scc->index)
495 scc_add_xref (DYN_ARRAY_REF (&sccs, entry->scc_index), current_scc);
499 scc_add_entry (current_scc, entry);
501 for (i = 0; i < entry->srcs.size; ++i)
502 dyn_array_ptr_push (&dfs_stack, DYN_ARRAY_PTR_REF (&entry->srcs, i));
503 } while (dfs_stack.size > 0);
507 compare_hash_entries (const void *ep1, const void *ep2)
509 HashEntry *e1 = *(HashEntry**)ep1;
510 HashEntry *e2 = *(HashEntry**)ep2;
511 return e2->finishing_time - e1->finishing_time;
514 static unsigned long step_1, step_2, step_3, step_4, step_5, step_6, step_7, step_8;
515 static int fist_pass_links, second_pass_links, sccs_links;
516 static int max_sccs_links = 0;
519 mono_sgen_bridge_register_finalized_object (MonoObject *obj)
521 g_assert (mono_sgen_need_bridge_processing ());
522 dyn_array_ptr_push (®istered_bridges, obj);
526 mono_sgen_bridge_reset_data (void)
528 registered_bridges.size = 0;
532 mono_sgen_bridge_processing_stw_step (void)
535 SGEN_TV_DECLARE (atv);
536 SGEN_TV_DECLARE (btv);
538 if (!registered_bridges.size)
541 SGEN_TV_GETTIME (btv);
545 dyn_array_ptr_init (&dfs_stack);
546 dyn_array_int_init (&merge_array);
549 for (i = 0; i < registered_bridges.size; ++i)
550 dfs1 (register_bridge_object (DYN_ARRAY_PTR_REF (®istered_bridges, i)), NULL);
552 SGEN_TV_GETTIME (atv);
553 step_2 = SGEN_TV_ELAPSED (btv, atv);
557 mono_sgen_bridge_processing_finish (void)
560 int num_sccs, num_xrefs;
561 int max_entries, max_xrefs;
562 int hash_table_size, sccs_size;
565 int num_registered_bridges;
566 HashEntry **all_entries;
567 MonoGCBridgeSCC **api_sccs;
568 MonoGCBridgeXRef *api_xrefs;
569 SGEN_TV_DECLARE (atv);
570 SGEN_TV_DECLARE (btv);
572 if (!registered_bridges.size)
575 SGEN_TV_GETTIME (atv);
577 /* alloc and fill array of all entries */
579 all_entries = mono_sgen_alloc_internal_dynamic (sizeof (HashEntry*) * hash_table.num_entries, INTERNAL_MEM_BRIDGE_DATA);
582 SGEN_HASH_TABLE_FOREACH (&hash_table, obj, entry) {
583 g_assert (entry->finishing_time >= 0);
584 all_entries [j++] = entry;
585 fist_pass_links += entry->srcs.size;
586 } SGEN_HASH_TABLE_FOREACH_END;
587 g_assert (j == hash_table.num_entries);
588 hash_table_size = hash_table.num_entries;
590 /* sort array according to decreasing finishing time */
592 qsort (all_entries, hash_table.num_entries, sizeof (HashEntry*), compare_hash_entries);
594 SGEN_TV_GETTIME (btv);
595 step_3 = SGEN_TV_ELAPSED (atv, btv);
597 /* second DFS pass */
599 dyn_array_init (&sccs, sizeof (SCC));
600 for (i = 0; i < hash_table.num_entries; ++i) {
601 HashEntry *entry = all_entries [i];
602 if (entry->scc_index < 0) {
603 int index = sccs.size;
604 current_scc = dyn_array_add (&sccs);
605 current_scc->index = index;
606 current_scc->num_bridge_entries = 0;
607 current_scc->api_index = -1;
608 dyn_array_int_init (¤t_scc->xrefs);
614 sccs_size = sccs.size;
616 for (i = 0; i < hash_table.num_entries; ++i) {
617 HashEntry *entry = all_entries [i];
618 second_pass_links += entry->srcs.size;
621 SGEN_TV_GETTIME (atv);
622 step_4 = SGEN_TV_ELAPSED (btv, atv);
624 //g_print ("%d sccs\n", sccs.size);
626 dyn_array_uninit (&dfs_stack);
628 /* init data for callback */
631 for (i = 0; i < sccs.size; ++i) {
632 SCC *scc = DYN_ARRAY_REF (&sccs, i);
633 g_assert (scc->index == i);
634 if (scc->num_bridge_entries)
636 sccs_links += scc->xrefs.size;
637 max_sccs_links = MAX (max_sccs_links, scc->xrefs.size);
640 api_sccs = mono_sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC*) * num_sccs, INTERNAL_MEM_BRIDGE_DATA);
643 for (i = 0; i < sccs.size; ++i) {
644 SCC *scc = DYN_ARRAY_REF (&sccs, i);
645 if (!scc->num_bridge_entries)
648 api_sccs [j] = mono_sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeSCC) + sizeof (MonoObject*) * scc->num_bridge_entries, INTERNAL_MEM_BRIDGE_DATA);
649 api_sccs [j]->num_objs = scc->num_bridge_entries;
650 scc->num_bridge_entries = 0;
651 scc->api_index = j++;
653 num_xrefs += scc->xrefs.size;
656 SGEN_HASH_TABLE_FOREACH (&hash_table, obj, entry) {
657 if (entry->is_bridge) {
658 SCC *scc = DYN_ARRAY_REF (&sccs, entry->scc_index);
659 api_sccs [scc->api_index]->objs [scc->num_bridge_entries++] = entry->obj;
661 } SGEN_HASH_TABLE_FOREACH_END;
663 api_xrefs = mono_sgen_alloc_internal_dynamic (sizeof (MonoGCBridgeXRef) * num_xrefs, INTERNAL_MEM_BRIDGE_DATA);
665 for (i = 0; i < sccs.size; ++i) {
667 SCC *scc = DYN_ARRAY_REF (&sccs, i);
668 if (!scc->num_bridge_entries)
670 for (k = 0; k < scc->xrefs.size; ++k) {
671 SCC *src_scc = DYN_ARRAY_REF (&sccs, DYN_ARRAY_INT_REF (&scc->xrefs, k));
672 if (!src_scc->num_bridge_entries)
674 api_xrefs [j].src_scc_index = src_scc->api_index;
675 api_xrefs [j].dst_scc_index = scc->api_index;
680 SGEN_TV_GETTIME (btv);
681 step_5 = SGEN_TV_ELAPSED (atv, btv);
686 max_entries = max_xrefs = 0;
687 for (i = 0; i < sccs.size; ++i) {
688 SCC *scc = DYN_ARRAY_REF (&sccs, i);
689 if (scc->num_bridge_entries)
691 if (scc->num_bridge_entries > max_entries)
692 max_entries = scc->num_bridge_entries;
693 if (scc->xrefs.size > max_xrefs)
694 max_xrefs = scc->xrefs.size;
695 dyn_array_uninit (&scc->xrefs);
698 dyn_array_uninit (&sccs);
700 mono_sgen_free_internal_dynamic (all_entries, sizeof (HashEntry*) * hash_table.num_entries, INTERNAL_MEM_BRIDGE_DATA);
703 /* Empty the registered bridges array */
704 num_registered_bridges = registered_bridges.size;
705 registered_bridges.size = 0;
707 SGEN_TV_GETTIME (atv);
708 step_6 = SGEN_TV_ELAPSED (btv, atv);
710 //g_print ("%d sccs containing bridges - %d max bridge objects - %d max xrefs\n", j, max_entries, max_xrefs);
714 bridge_callbacks.cross_references (num_sccs, api_sccs, num_xrefs, api_xrefs);
716 /*Release for finalization those objects we no longer care. */
717 SGEN_TV_GETTIME (btv);
718 step_7 = SGEN_TV_ELAPSED (atv, btv);
720 for (i = 0; i < num_sccs; ++i) {
721 if (!api_sccs [i]->objs [0])
723 for (j = 0; j < api_sccs [i]->num_objs; ++j)
724 mono_sgen_mark_bridge_object (api_sccs [i]->objs [j]);
727 /* free callback data */
729 for (i = 0; i < num_sccs; ++i) {
730 mono_sgen_free_internal_dynamic (api_sccs [i],
731 sizeof (MonoGCBridgeSCC) + sizeof (MonoObject*) * api_sccs [i]->num_objs,
732 INTERNAL_MEM_BRIDGE_DATA);
734 mono_sgen_free_internal_dynamic (api_sccs, sizeof (MonoGCBridgeSCC*) * num_sccs, INTERNAL_MEM_BRIDGE_DATA);
736 mono_sgen_free_internal_dynamic (api_xrefs, sizeof (MonoGCBridgeXRef) * num_xrefs, INTERNAL_MEM_BRIDGE_DATA);
738 SGEN_TV_GETTIME (atv);
739 step_8 = SGEN_TV_ELAPSED (btv, atv);
741 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",
742 num_registered_bridges, hash_table_size, sccs.size,
751 fist_pass_links, second_pass_links, sccs_links, max_sccs_links,
752 dsf1_passes, dsf2_passes);
754 step_1 = 0; /* We must cleanup since this value is used as an accumulator. */
757 static const char *bridge_class;
760 bridge_test_is_bridge_class (MonoClass *class)
762 return !strcmp (bridge_class, class->name);
766 bridge_test_cross_reference (int num_sccs, MonoGCBridgeSCC **sccs, int num_xrefs, MonoGCBridgeXRef *xrefs)
769 for (i = 0; i < num_sccs; ++i) {
771 // g_print ("--- SCC %d\n", i);
772 for (j = 0; j < sccs [i]->num_objs; ++j) {
773 // g_print (" %s\n", mono_sgen_safe_name (sccs [i]->objs [j]));
774 if (i & 1) /*retain half of the bridged objects */
775 sccs [i]->objs [0] = NULL;
778 for (i = 0; i < num_xrefs; ++i) {
779 g_assert (xrefs [i].src_scc_index >= 0 && xrefs [i].src_scc_index < num_sccs);
780 g_assert (xrefs [i].dst_scc_index >= 0 && xrefs [i].dst_scc_index < num_sccs);
781 // g_print ("%d -> %d\n", xrefs [i].src_scc_index, xrefs [i].dst_scc_index);
787 mono_sgen_register_test_bridge_callbacks (const char *bridge_class_name)
789 MonoGCBridgeCallbacks callbacks;
790 callbacks.bridge_version = MONO_SGEN_BRIDGE_VERSION;
791 callbacks.is_bridge_class = bridge_test_is_bridge_class;
792 callbacks.cross_references = bridge_test_cross_reference;
793 mono_gc_register_bridge_callbacks (&callbacks);
794 bridge_class = bridge_class_name;