2 * sgen-bridge.c: Simple generational GC.
4 * Copyright 2011 Novell, Inc (http://www.novell.com)
5 * Copyright 2011 Xamarin Inc (http://www.xamarin.com)
6 * Copyright 2001-2003 Ximian, Inc
7 * Copyright 2003-2010 Novell, Inc.
9 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
18 #include "sgen/sgen-gc.h"
19 #include "sgen-bridge-internals.h"
20 #include "sgen/sgen-hash-table.h"
21 #include "sgen/sgen-qsort.h"
22 #include "utils/mono-logger-internals.h"
25 BRIDGE_PROCESSOR_INVALID,
28 BRIDGE_PROCESSOR_TARJAN,
29 BRIDGE_PROCESSOR_DEFAULT = BRIDGE_PROCESSOR_TARJAN
30 } BridgeProcessorSelection;
32 // Bridge processor type pending / in use
33 static BridgeProcessorSelection bridge_processor_selection = BRIDGE_PROCESSOR_DEFAULT;
34 // Most recently requested callbacks
35 static MonoGCBridgeCallbacks pending_bridge_callbacks;
36 // Currently-in-use callbacks
37 MonoGCBridgeCallbacks bridge_callbacks;
39 // Bridge processor state
40 static SgenBridgeProcessor bridge_processor;
41 // This is used for a special debug feature
42 static SgenBridgeProcessor compare_to_bridge_processor;
44 volatile gboolean bridge_processing_in_progress = FALSE;
46 // FIXME: The current usage pattern for this function is unsafe. Bridge processing could start immediately after unlock
48 mono_gc_wait_for_bridge_processing (void)
50 if (!bridge_processing_in_progress)
53 mono_trace (G_LOG_LEVEL_INFO, MONO_TRACE_GC, "GC_BRIDGE waiting for bridge processing to finish");
60 mono_gc_register_bridge_callbacks (MonoGCBridgeCallbacks *callbacks)
62 if (callbacks->bridge_version != SGEN_BRIDGE_VERSION)
63 g_error ("Invalid bridge callback version. Expected %d but got %d\n", SGEN_BRIDGE_VERSION, callbacks->bridge_version);
65 // Defer assigning to bridge_callbacks until we have the gc lock.
66 // Note: This line is unsafe if we are on a separate thread from the one the runtime was initialized on.
67 pending_bridge_callbacks = *callbacks;
69 // If sgen has started, will assign bridge callbacks and init bridge
73 static BridgeProcessorSelection
74 bridge_processor_name (const char *name)
76 if (!strcmp ("old", name)) {
77 return BRIDGE_PROCESSOR_OLD;
78 } else if (!strcmp ("new", name)) {
79 return BRIDGE_PROCESSOR_NEW;
80 } else if (!strcmp ("tarjan", name)) {
81 return BRIDGE_PROCESSOR_TARJAN;
83 return BRIDGE_PROCESSOR_INVALID;
87 // Initialize a single bridge processor
89 init_bridge_processor (SgenBridgeProcessor *processor, BridgeProcessorSelection selection)
91 memset (processor, 0, sizeof (SgenBridgeProcessor));
94 case BRIDGE_PROCESSOR_OLD:
95 sgen_old_bridge_init (processor);
97 case BRIDGE_PROCESSOR_NEW:
98 sgen_new_bridge_init (processor);
100 case BRIDGE_PROCESSOR_TARJAN:
101 sgen_tarjan_bridge_init (processor);
104 g_assert_not_reached ();
109 * Initializing the sgen bridge consists of setting the bridge callbacks,
110 * and initializing the bridge processor. Init should follow these rules:
112 * - Init happens only after sgen is initialized (because we don't
113 * know which bridge processor to initialize until then, and also
114 * to allow bridge processor init to interact with sgen if it wants)
116 * - Init happens only after mono_gc_register_bridge_callbacks is called
118 * - Init should not happen concurrently with a GC (because a GC will
119 * call sgen_need_bridge_processing at various times)
121 * - Initializing the bridge processor should happen only once
123 * We call sgen_init_bridge when the callbacks are set, and also when sgen
124 * is done initing. Actual initialization then only occurs if it is ready.
129 if (sgen_gc_initialized ()) {
130 // This lock is not initialized until the GC is
133 bridge_callbacks = pending_bridge_callbacks;
135 // If a bridge was registered but there is no bridge processor yet
136 if (bridge_callbacks.cross_references && !bridge_processor.reset_data)
137 init_bridge_processor (&bridge_processor, bridge_processor_selection);
144 sgen_set_bridge_implementation (const char *name)
146 BridgeProcessorSelection selection = bridge_processor_name (name);
148 if (selection == BRIDGE_PROCESSOR_INVALID)
149 g_warning ("Invalid value for bridge processor implementation, valid values are: 'new', 'old' and 'tarjan'.");
150 else if (bridge_processor.reset_data)
151 g_warning ("Cannot set bridge processor implementation once bridge has already started");
153 bridge_processor_selection = selection;
157 sgen_is_bridge_object (GCObject *obj)
159 if ((obj->vtable->gc_bits & SGEN_GC_BIT_BRIDGE_OBJECT) != SGEN_GC_BIT_BRIDGE_OBJECT)
161 return bridge_callbacks.is_bridge_object (obj);
165 sgen_need_bridge_processing (void)
167 return bridge_callbacks.cross_references != NULL;
171 compare_bridge_processors (void)
173 return compare_to_bridge_processor.reset_data != NULL;
176 /* Dispatch wrappers */
178 sgen_bridge_reset_data (void)
180 bridge_processor.reset_data ();
181 if (compare_bridge_processors ())
182 compare_to_bridge_processor.reset_data ();
186 sgen_bridge_processing_stw_step (void)
189 * bridge_processing_in_progress must be set with the world
190 * stopped. If not there would be race conditions.
192 bridge_processing_in_progress = TRUE;
194 bridge_processor.processing_stw_step ();
195 if (compare_bridge_processors ())
196 compare_to_bridge_processor.processing_stw_step ();
200 is_bridge_object_dead (GCObject *obj, void *data)
202 SgenHashTable *table = (SgenHashTable *)data;
203 unsigned char *value = (unsigned char *)sgen_hash_table_lookup (table, obj);
210 null_weak_links_to_dead_objects (SgenBridgeProcessor *processor, int generation)
213 int num_sccs = processor->num_sccs;
214 MonoGCBridgeSCC **api_sccs = processor->api_sccs;
215 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);
217 for (i = 0; i < num_sccs; ++i) {
218 unsigned char alive = api_sccs [i]->is_alive ? 1 : 0;
219 for (j = 0; j < api_sccs [i]->num_objs; ++j) {
220 /* Build hash table for nulling weak links. */
221 sgen_hash_table_replace (&alive_hash, api_sccs [i]->objs [j], &alive, NULL);
223 /* Release for finalization those objects we no longer care. */
224 if (!api_sccs [i]->is_alive)
225 sgen_mark_bridge_object (api_sccs [i]->objs [j]);
229 /* Null weak links to dead objects. */
230 sgen_null_links_if (is_bridge_object_dead, &alive_hash, GENERATION_NURSERY, FALSE);
231 sgen_null_links_if (is_bridge_object_dead, &alive_hash, GENERATION_NURSERY, TRUE);
232 if (generation == GENERATION_OLD) {
233 sgen_null_links_if (is_bridge_object_dead, &alive_hash, GENERATION_OLD, FALSE);
234 sgen_null_links_if (is_bridge_object_dead, &alive_hash, GENERATION_OLD, TRUE);
237 sgen_hash_table_clean (&alive_hash);
241 free_callback_data (SgenBridgeProcessor *processor)
244 int num_sccs = processor->num_sccs;
245 int num_xrefs = processor->num_xrefs;
246 MonoGCBridgeSCC **api_sccs = processor->api_sccs;
247 MonoGCBridgeXRef *api_xrefs = processor->api_xrefs;
249 for (i = 0; i < num_sccs; ++i) {
250 sgen_free_internal_dynamic (api_sccs [i],
251 sizeof (MonoGCBridgeSCC) + sizeof (MonoObject*) * api_sccs [i]->num_objs,
252 INTERNAL_MEM_BRIDGE_DATA);
254 sgen_free_internal_dynamic (api_sccs, sizeof (MonoGCBridgeSCC*) * num_sccs, INTERNAL_MEM_BRIDGE_DATA);
256 sgen_free_internal_dynamic (api_xrefs, sizeof (MonoGCBridgeXRef) * num_xrefs, INTERNAL_MEM_BRIDGE_DATA);
258 processor->num_sccs = 0;
259 processor->api_sccs = NULL;
260 processor->num_xrefs = 0;
261 processor->api_xrefs = NULL;
265 compare_xrefs (const void *a_ptr, const void *b_ptr)
267 const MonoGCBridgeXRef *a = (const MonoGCBridgeXRef *)a_ptr;
268 const MonoGCBridgeXRef *b = (const MonoGCBridgeXRef *)b_ptr;
270 if (a->src_scc_index < b->src_scc_index)
272 if (a->src_scc_index > b->src_scc_index)
275 if (a->dst_scc_index < b->dst_scc_index)
277 if (a->dst_scc_index > b->dst_scc_index)
285 dump_processor_state (SgenBridgeProcessor *p)
290 printf ("SCCS %d\n", p->num_sccs);
291 for (i = 0; i < p->num_sccs; ++i) {
293 MonoGCBridgeSCC *scc = p->api_sccs [i];
294 printf ("\tSCC %d:", i);
295 for (j = 0; j < scc->num_objs; ++j) {
296 MonoObject *obj = scc->objs [j];
302 printf ("XREFS %d\n", p->num_xrefs);
303 for (i = 0; i < p->num_xrefs; ++i)
304 printf ("\t%d -> %d\n", p->api_xrefs [i].src_scc_index, p->api_xrefs [i].dst_scc_index);
306 printf ("-------\n");
311 sgen_compare_bridge_processor_results (SgenBridgeProcessor *a, SgenBridgeProcessor *b)
314 SgenHashTable obj_to_a_scc = SGEN_HASH_TABLE_INIT (INTERNAL_MEM_BRIDGE_DEBUG, INTERNAL_MEM_BRIDGE_DEBUG, sizeof (int), mono_aligned_addr_hash, NULL);
315 SgenHashTable b_scc_to_a_scc = SGEN_HASH_TABLE_INIT (INTERNAL_MEM_BRIDGE_DEBUG, INTERNAL_MEM_BRIDGE_DEBUG, sizeof (int), g_direct_hash, NULL);
316 MonoGCBridgeXRef *a_xrefs, *b_xrefs;
317 size_t xrefs_alloc_size;
319 // dump_processor_state (a);
320 // dump_processor_state (b);
322 if (a->num_sccs != b->num_sccs)
323 g_error ("SCCS count expected %d but got %d", a->num_sccs, b->num_sccs);
324 if (a->num_xrefs != b->num_xrefs)
325 g_error ("SCCS count expected %d but got %d", a->num_xrefs, b->num_xrefs);
328 * First we build a hash of each object in `a` to its respective SCC index within
329 * `a`. Along the way we also assert that no object is more than one SCC.
331 for (i = 0; i < a->num_sccs; ++i) {
333 MonoGCBridgeSCC *scc = a->api_sccs [i];
335 g_assert (scc->num_objs > 0);
337 for (j = 0; j < scc->num_objs; ++j) {
338 GCObject *obj = scc->objs [j];
339 gboolean new_entry = sgen_hash_table_replace (&obj_to_a_scc, obj, &i, NULL);
340 g_assert (new_entry);
345 * Now we check whether each of the objects in `b` are in `a`, and whether the SCCs
346 * of `b` contain the same sets of objects as those of `a`.
348 * While we're doing this, build a hash table to map from `b` SCC indexes to `a` SCC
351 for (i = 0; i < b->num_sccs; ++i) {
352 MonoGCBridgeSCC *scc = b->api_sccs [i];
353 MonoGCBridgeSCC *a_scc;
354 int *a_scc_index_ptr;
359 g_assert (scc->num_objs > 0);
360 a_scc_index_ptr = (int *)sgen_hash_table_lookup (&obj_to_a_scc, scc->objs [0]);
361 g_assert (a_scc_index_ptr);
362 a_scc_index = *a_scc_index_ptr;
364 //g_print ("A SCC %d -> B SCC %d\n", a_scc_index, i);
366 a_scc = a->api_sccs [a_scc_index];
367 g_assert (a_scc->num_objs == scc->num_objs);
369 for (j = 1; j < scc->num_objs; ++j) {
370 a_scc_index_ptr = (int *)sgen_hash_table_lookup (&obj_to_a_scc, scc->objs [j]);
371 g_assert (a_scc_index_ptr);
372 g_assert (*a_scc_index_ptr == a_scc_index);
375 new_entry = sgen_hash_table_replace (&b_scc_to_a_scc, GINT_TO_POINTER (i), &a_scc_index, NULL);
376 g_assert (new_entry);
380 * Finally, check that we have the same xrefs. We do this by making copies of both
381 * xref arrays, and replacing the SCC indexes in the copy for `b` with the
382 * corresponding indexes in `a`. Then we sort both arrays and assert that they're
385 * At the same time, check that no xref is self-referential and that there are no
389 xrefs_alloc_size = a->num_xrefs * sizeof (MonoGCBridgeXRef);
390 a_xrefs = (MonoGCBridgeXRef *)sgen_alloc_internal_dynamic (xrefs_alloc_size, INTERNAL_MEM_BRIDGE_DEBUG, TRUE);
391 b_xrefs = (MonoGCBridgeXRef *)sgen_alloc_internal_dynamic (xrefs_alloc_size, INTERNAL_MEM_BRIDGE_DEBUG, TRUE);
393 memcpy (a_xrefs, a->api_xrefs, xrefs_alloc_size);
394 for (i = 0; i < b->num_xrefs; ++i) {
395 MonoGCBridgeXRef *xref = &b->api_xrefs [i];
398 g_assert (xref->src_scc_index != xref->dst_scc_index);
400 scc_index_ptr = (int *)sgen_hash_table_lookup (&b_scc_to_a_scc, GINT_TO_POINTER (xref->src_scc_index));
401 g_assert (scc_index_ptr);
402 b_xrefs [i].src_scc_index = *scc_index_ptr;
404 scc_index_ptr = (int *)sgen_hash_table_lookup (&b_scc_to_a_scc, GINT_TO_POINTER (xref->dst_scc_index));
405 g_assert (scc_index_ptr);
406 b_xrefs [i].dst_scc_index = *scc_index_ptr;
409 qsort (a_xrefs, a->num_xrefs, sizeof (MonoGCBridgeXRef), compare_xrefs);
410 qsort (b_xrefs, a->num_xrefs, sizeof (MonoGCBridgeXRef), compare_xrefs);
412 for (i = 0; i < a->num_xrefs; ++i) {
413 g_assert (a_xrefs [i].src_scc_index == b_xrefs [i].src_scc_index);
414 g_assert (a_xrefs [i].dst_scc_index == b_xrefs [i].dst_scc_index);
417 sgen_hash_table_clean (&obj_to_a_scc);
418 sgen_hash_table_clean (&b_scc_to_a_scc);
419 sgen_free_internal_dynamic (a_xrefs, xrefs_alloc_size, INTERNAL_MEM_BRIDGE_DEBUG);
420 sgen_free_internal_dynamic (b_xrefs, xrefs_alloc_size, INTERNAL_MEM_BRIDGE_DEBUG);
426 sgen_bridge_processing_finish (int generation)
428 bridge_processor.processing_build_callback_data (generation);
429 if (compare_bridge_processors ())
430 compare_to_bridge_processor.processing_build_callback_data (generation);
432 if (bridge_processor.num_sccs == 0) {
433 g_assert (bridge_processor.num_xrefs == 0);
437 bridge_callbacks.cross_references (bridge_processor.num_sccs, bridge_processor.api_sccs,
438 bridge_processor.num_xrefs, bridge_processor.api_xrefs);
440 if (compare_bridge_processors ())
441 sgen_compare_bridge_processor_results (&bridge_processor, &compare_to_bridge_processor);
443 null_weak_links_to_dead_objects (&bridge_processor, generation);
445 free_callback_data (&bridge_processor);
446 if (compare_bridge_processors ())
447 free_callback_data (&compare_to_bridge_processor);
450 bridge_processor.processing_after_callback (generation);
451 if (compare_bridge_processors ())
452 compare_to_bridge_processor.processing_after_callback (generation);
454 mono_trace (G_LOG_LEVEL_INFO, MONO_TRACE_GC, "GC_BRIDGE: Complete, was running for %.2fms", mono_time_since_last_stw () / 10000.0f);
456 bridge_processing_in_progress = FALSE;
459 MonoGCBridgeObjectKind
460 sgen_bridge_class_kind (MonoClass *klass)
462 return bridge_processor.class_kind (klass);
466 sgen_bridge_register_finalized_object (GCObject *obj)
468 bridge_processor.register_finalized_object (obj);
469 if (compare_bridge_processors ())
470 compare_to_bridge_processor.register_finalized_object (obj);
474 sgen_bridge_describe_pointer (GCObject *obj)
476 if (bridge_processor.describe_pointer)
477 bridge_processor.describe_pointer (obj);
481 set_dump_prefix (const char *prefix)
483 if (!bridge_processor.set_dump_prefix) {
484 fprintf (stderr, "Warning: Bridge implementation does not support dumping - ignoring.\n");
488 bridge_processor.set_dump_prefix (prefix);
491 /* Test support code */
492 static const char *bridge_class;
494 static MonoGCBridgeObjectKind
495 bridge_test_bridge_class_kind (MonoClass *klass)
497 if (!strcmp (bridge_class, klass->name))
498 return GC_BRIDGE_TRANSPARENT_BRIDGE_CLASS;
499 return GC_BRIDGE_TRANSPARENT_CLASS;
503 bridge_test_is_bridge_object (MonoObject *object)
509 bridge_test_cross_reference (int num_sccs, MonoGCBridgeSCC **sccs, int num_xrefs, MonoGCBridgeXRef *xrefs)
512 for (i = 0; i < num_sccs; ++i) {
514 // g_print ("--- SCC %d\n", i);
515 for (j = 0; j < sccs [i]->num_objs; ++j) {
516 // g_print (" %s\n", sgen_safe_name (sccs [i]->objs [j]));
517 if (i & 1) /*retain half of the bridged objects */
518 sccs [i]->is_alive = TRUE;
521 for (i = 0; i < num_xrefs; ++i) {
522 g_assert (xrefs [i].src_scc_index >= 0 && xrefs [i].src_scc_index < num_sccs);
523 g_assert (xrefs [i].dst_scc_index >= 0 && xrefs [i].dst_scc_index < num_sccs);
524 // g_print ("%d -> %d\n", xrefs [i].src_scc_index, xrefs [i].dst_scc_index);
528 static MonoClassField *mono_bridge_test_field;
538 test_scc (MonoGCBridgeSCC *scc, int i)
540 int status = BRIDGE_DEAD;
541 mono_field_get_value (scc->objs [i], mono_bridge_test_field, &status);
546 mark_scc (MonoGCBridgeSCC *scc, int value)
549 for (i = 0; i < scc->num_objs; ++i) {
550 if (!test_scc (scc, i)) {
552 mono_field_set_value (scc->objs [i], mono_bridge_test_field, &status);
558 bridge_test_cross_reference2 (int num_sccs, MonoGCBridgeSCC **sccs, int num_xrefs, MonoGCBridgeXRef *xrefs)
563 if (!mono_bridge_test_field) {
564 mono_bridge_test_field = mono_class_get_field_from_name (mono_object_get_class (sccs[0]->objs [0]), "__test");
565 g_assert (mono_bridge_test_field);
568 /*We mark all objects in a scc with live objects as reachable by scc*/
569 for (i = 0; i < num_sccs; ++i) {
571 gboolean live = FALSE;
572 for (j = 0; j < sccs [i]->num_objs; ++j) {
573 if (test_scc (sccs [i], j)) {
580 for (j = 0; j < sccs [i]->num_objs; ++j) {
581 if (!test_scc (sccs [i], j)) {
582 int status = BRIDGE_SAME_SCC;
583 mono_field_set_value (sccs [i]->objs [j], mono_bridge_test_field, &status);
588 /*Now we mark the transitive closure of reachable objects from the xrefs*/
592 /* Mark all objects that are brought to life due to xrefs*/
593 for (i = 0; i < num_xrefs; ++i) {
594 MonoGCBridgeXRef ref = xrefs [i];
595 if (test_scc (sccs [ref.src_scc_index], 0) && !test_scc (sccs [ref.dst_scc_index], 0)) {
597 mark_scc (sccs [ref.dst_scc_index], BRIDGE_XREF);
602 /* keep everything in memory, all we want to do is test persistence */
603 for (i = 0; i < num_sccs; ++i)
604 sccs [i]->is_alive = TRUE;
607 /* This bridge keeps all peers with __test > 0 */
609 bridge_test_positive_status (int num_sccs, MonoGCBridgeSCC **sccs, int num_xrefs, MonoGCBridgeXRef *xrefs)
613 if (!mono_bridge_test_field) {
614 mono_bridge_test_field = mono_class_get_field_from_name (mono_object_get_class (sccs[0]->objs [0]), "__test");
615 g_assert (mono_bridge_test_field);
618 /*We mark all objects in a scc with live objects as reachable by scc*/
619 for (i = 0; i < num_sccs; ++i) {
621 for (j = 0; j < sccs [i]->num_objs; ++j) {
622 if (test_scc (sccs [i], j)) {
623 sccs [i]->is_alive = TRUE;
632 register_test_bridge_callbacks (const char *bridge_class_name)
634 MonoGCBridgeCallbacks callbacks;
635 callbacks.bridge_version = SGEN_BRIDGE_VERSION;
636 callbacks.bridge_class_kind = bridge_test_bridge_class_kind;
637 callbacks.is_bridge_object = bridge_test_is_bridge_object;
639 switch (bridge_class_name [0]) {
641 bridge_class = bridge_class_name + 1;
642 callbacks.cross_references = bridge_test_cross_reference2;
645 bridge_class = bridge_class_name + 1;
646 callbacks.cross_references = bridge_test_positive_status;
649 bridge_class = bridge_class_name;
650 callbacks.cross_references = bridge_test_cross_reference;
652 mono_gc_register_bridge_callbacks (&callbacks);
656 sgen_bridge_handle_gc_debug (const char *opt)
658 if (g_str_has_prefix (opt, "bridge=")) {
659 opt = strchr (opt, '=') + 1;
660 register_test_bridge_callbacks (g_strdup (opt));
661 } else if (!strcmp (opt, "enable-bridge-accounting")) {
662 bridge_processor.enable_accounting ();
663 } else if (g_str_has_prefix (opt, "bridge-dump=")) {
664 char *prefix = strchr (opt, '=') + 1;
665 set_dump_prefix (prefix);
666 } else if (g_str_has_prefix (opt, "bridge-compare-to=")) {
667 const char *name = strchr (opt, '=') + 1;
668 BridgeProcessorSelection selection = bridge_processor_name (name);
670 if (selection != BRIDGE_PROCESSOR_INVALID) {
671 init_bridge_processor (&compare_to_bridge_processor, selection);
673 g_warning ("Invalid bridge implementation to compare against - ignoring.");
682 sgen_bridge_print_gc_debug_usage (void)
684 fprintf (stderr, " bridge=<class-name>\n");
685 fprintf (stderr, " enable-bridge-accounting\n");
686 fprintf (stderr, " bridge-dump=<filename-prefix>\n");
687 fprintf (stderr, " bridge-compare-to=<implementation>\n");