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 "utils/mono-logger-internal.h"
51 #include "utils/mono-time.h"
52 #include "utils/mono-compiler.h"
54 MonoGCBridgeCallbacks bridge_callbacks;
55 static SgenBridgeProcessor bridge_processor;
56 static SgenBridgeProcessor compare_to_bridge_processor;
58 gboolean bridge_processing_in_progress = FALSE;
61 mono_gc_wait_for_bridge_processing (void)
63 if (!bridge_processing_in_progress)
66 mono_trace (G_LOG_LEVEL_INFO, MONO_TRACE_GC, "GC_BRIDGE waiting for bridge processing to finish");
74 mono_gc_register_bridge_callbacks (MonoGCBridgeCallbacks *callbacks)
76 if (callbacks->bridge_version != SGEN_BRIDGE_VERSION)
77 g_error ("Invalid bridge callback version. Expected %d but got %d\n", SGEN_BRIDGE_VERSION, callbacks->bridge_version);
79 bridge_callbacks = *callbacks;
81 if (!bridge_processor.reset_data)
82 sgen_old_bridge_init (&bridge_processor);
86 init_bridge_processor (SgenBridgeProcessor *processor, const char *name)
88 if (!strcmp ("old", name)) {
89 memset (processor, 0, sizeof (SgenBridgeProcessor));
90 sgen_old_bridge_init (processor);
91 } else if (!strcmp ("new", name)) {
92 memset (processor, 0, sizeof (SgenBridgeProcessor));
93 sgen_new_bridge_init (processor);
94 } else if (!strcmp ("tarjan", name)) {
95 memset (processor, 0, sizeof (SgenBridgeProcessor));
96 sgen_tarjan_bridge_init (processor);
104 sgen_set_bridge_implementation (const char *name)
106 if (!init_bridge_processor (&bridge_processor, name))
107 g_warning ("Invalid value for bridge implementation, valid values are: 'new' and 'old'.");
111 sgen_is_bridge_object (MonoObject *obj)
113 if ((obj->vtable->gc_bits & SGEN_GC_BIT_BRIDGE_OBJECT) != SGEN_GC_BIT_BRIDGE_OBJECT)
115 return bridge_callbacks.is_bridge_object (obj);
119 sgen_need_bridge_processing (void)
121 return bridge_callbacks.cross_references != NULL;
125 compare_bridge_processors (void)
127 return compare_to_bridge_processor.reset_data != NULL;
130 /* Dispatch wrappers */
132 sgen_bridge_reset_data (void)
134 bridge_processor.reset_data ();
135 if (compare_bridge_processors ())
136 compare_to_bridge_processor.reset_data ();
140 sgen_bridge_processing_stw_step (void)
143 * bridge_processing_in_progress must be set with the world
144 * stopped. If not there would be race conditions.
146 bridge_processing_in_progress = TRUE;
148 bridge_processor.processing_stw_step ();
149 if (compare_bridge_processors ())
150 compare_to_bridge_processor.processing_stw_step ();
154 is_bridge_object_alive (MonoObject *obj, void *data)
156 SgenHashTable *table = data;
157 unsigned char *value = sgen_hash_table_lookup (table, obj);
164 null_weak_links_to_dead_objects (SgenBridgeProcessor *processor, int generation)
167 int num_sccs = processor->num_sccs;
168 MonoGCBridgeSCC **api_sccs = processor->api_sccs;
169 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);
171 for (i = 0; i < num_sccs; ++i) {
172 unsigned char alive = api_sccs [i]->is_alive ? 1 : 0;
173 for (j = 0; j < api_sccs [i]->num_objs; ++j) {
174 /* Build hash table for nulling weak links. */
175 sgen_hash_table_replace (&alive_hash, api_sccs [i]->objs [j], &alive, NULL);
177 /* Release for finalization those objects we no longer care. */
178 if (!api_sccs [i]->is_alive)
179 sgen_mark_bridge_object (api_sccs [i]->objs [j]);
183 /* Null weak links to dead objects. */
184 sgen_null_links_with_predicate (GENERATION_NURSERY, is_bridge_object_alive, &alive_hash);
185 if (generation == GENERATION_OLD)
186 sgen_null_links_with_predicate (GENERATION_OLD, is_bridge_object_alive, &alive_hash);
188 sgen_hash_table_clean (&alive_hash);
192 free_callback_data (SgenBridgeProcessor *processor)
195 int num_sccs = processor->num_sccs;
196 int num_xrefs = processor->num_xrefs;
197 MonoGCBridgeSCC **api_sccs = processor->api_sccs;
198 MonoGCBridgeXRef *api_xrefs = processor->api_xrefs;
200 for (i = 0; i < num_sccs; ++i) {
201 sgen_free_internal_dynamic (api_sccs [i],
202 sizeof (MonoGCBridgeSCC) + sizeof (MonoObject*) * api_sccs [i]->num_objs,
203 INTERNAL_MEM_BRIDGE_DATA);
205 sgen_free_internal_dynamic (api_sccs, sizeof (MonoGCBridgeSCC*) * num_sccs, INTERNAL_MEM_BRIDGE_DATA);
207 sgen_free_internal_dynamic (api_xrefs, sizeof (MonoGCBridgeXRef) * num_xrefs, INTERNAL_MEM_BRIDGE_DATA);
209 processor->num_sccs = 0;
210 processor->api_sccs = NULL;
211 processor->num_xrefs = 0;
212 processor->api_xrefs = NULL;
216 sgen_bridge_processing_finish (int generation)
218 bridge_processor.processing_build_callback_data (generation);
219 if (compare_bridge_processors ())
220 compare_to_bridge_processor.processing_build_callback_data (generation);
222 if (bridge_processor.num_sccs == 0) {
223 g_assert (bridge_processor.num_xrefs == 0);
227 bridge_callbacks.cross_references (bridge_processor.num_sccs, bridge_processor.api_sccs,
228 bridge_processor.num_xrefs, bridge_processor.api_xrefs);
230 if (compare_bridge_processors ())
231 sgen_compare_bridge_processor_results (&bridge_processor, &compare_to_bridge_processor);
233 null_weak_links_to_dead_objects (&bridge_processor, generation);
235 free_callback_data (&bridge_processor);
236 if (compare_bridge_processors ())
237 free_callback_data (&compare_to_bridge_processor);
240 bridge_processor.processing_after_callback (generation);
241 if (compare_bridge_processors ())
242 compare_to_bridge_processor.processing_after_callback (generation);
244 bridge_processing_in_progress = FALSE;
247 MonoGCBridgeObjectKind
248 sgen_bridge_class_kind (MonoClass *class)
250 return bridge_processor.class_kind (class);
254 sgen_bridge_register_finalized_object (MonoObject *obj)
256 bridge_processor.register_finalized_object (obj);
257 if (compare_bridge_processors ())
258 compare_to_bridge_processor.register_finalized_object (obj);
262 sgen_bridge_describe_pointer (MonoObject *obj)
264 if (bridge_processor.describe_pointer)
265 bridge_processor.describe_pointer (obj);
269 set_dump_prefix (const char *prefix)
271 if (!bridge_processor.set_dump_prefix) {
272 fprintf (stderr, "Warning: Bridge implementation does not support dumping - ignoring.\n");
276 bridge_processor.set_dump_prefix (prefix);
279 /* Test support code */
280 static const char *bridge_class;
282 static MonoGCBridgeObjectKind
283 bridge_test_bridge_class_kind (MonoClass *class)
285 if (!strcmp (bridge_class, class->name))
286 return GC_BRIDGE_TRANSPARENT_BRIDGE_CLASS;
287 return GC_BRIDGE_TRANSPARENT_CLASS;
291 bridge_test_is_bridge_object (MonoObject *object)
297 bridge_test_cross_reference (int num_sccs, MonoGCBridgeSCC **sccs, int num_xrefs, MonoGCBridgeXRef *xrefs)
300 for (i = 0; i < num_sccs; ++i) {
302 // g_print ("--- SCC %d\n", i);
303 for (j = 0; j < sccs [i]->num_objs; ++j) {
304 // g_print (" %s\n", sgen_safe_name (sccs [i]->objs [j]));
305 if (i & 1) /*retain half of the bridged objects */
306 sccs [i]->is_alive = TRUE;
309 for (i = 0; i < num_xrefs; ++i) {
310 g_assert (xrefs [i].src_scc_index >= 0 && xrefs [i].src_scc_index < num_sccs);
311 g_assert (xrefs [i].dst_scc_index >= 0 && xrefs [i].dst_scc_index < num_sccs);
312 // g_print ("%d -> %d\n", xrefs [i].src_scc_index, xrefs [i].dst_scc_index);
316 static MonoClassField *mono_bridge_test_field;
326 test_scc (MonoGCBridgeSCC *scc, int i)
328 int status = BRIDGE_DEAD;
329 mono_field_get_value (scc->objs [i], mono_bridge_test_field, &status);
334 mark_scc (MonoGCBridgeSCC *scc, int value)
337 for (i = 0; i < scc->num_objs; ++i) {
338 if (!test_scc (scc, i)) {
340 mono_field_set_value (scc->objs [i], mono_bridge_test_field, &status);
346 bridge_test_cross_reference2 (int num_sccs, MonoGCBridgeSCC **sccs, int num_xrefs, MonoGCBridgeXRef *xrefs)
351 if (!mono_bridge_test_field) {
352 mono_bridge_test_field = mono_class_get_field_from_name (mono_object_get_class (sccs[0]->objs [0]), "__test");
353 g_assert (mono_bridge_test_field);
356 /*We mark all objects in a scc with live objects as reachable by scc*/
357 for (i = 0; i < num_sccs; ++i) {
359 gboolean live = FALSE;
360 for (j = 0; j < sccs [i]->num_objs; ++j) {
361 if (test_scc (sccs [i], j)) {
368 for (j = 0; j < sccs [i]->num_objs; ++j) {
369 if (!test_scc (sccs [i], j)) {
370 int status = BRIDGE_SAME_SCC;
371 mono_field_set_value (sccs [i]->objs [j], mono_bridge_test_field, &status);
376 /*Now we mark the transitive closure of reachable objects from the xrefs*/
380 /* Mark all objects that are brought to life due to xrefs*/
381 for (i = 0; i < num_xrefs; ++i) {
382 MonoGCBridgeXRef ref = xrefs [i];
383 if (test_scc (sccs [ref.src_scc_index], 0) && !test_scc (sccs [ref.dst_scc_index], 0)) {
385 mark_scc (sccs [ref.dst_scc_index], BRIDGE_XREF);
390 /* keep everything in memory, all we want to do is test persistence */
391 for (i = 0; i < num_sccs; ++i)
392 sccs [i]->is_alive = TRUE;
396 register_test_bridge_callbacks (const char *bridge_class_name)
398 MonoGCBridgeCallbacks callbacks;
399 callbacks.bridge_version = SGEN_BRIDGE_VERSION;
400 callbacks.bridge_class_kind = bridge_test_bridge_class_kind;
401 callbacks.is_bridge_object = bridge_test_is_bridge_object;
402 callbacks.cross_references = bridge_class_name[0] == '2' ? bridge_test_cross_reference2 : bridge_test_cross_reference;
403 mono_gc_register_bridge_callbacks (&callbacks);
404 bridge_class = bridge_class_name + (bridge_class_name[0] == '2' ? 1 : 0);
408 sgen_bridge_handle_gc_debug (const char *opt)
410 if (g_str_has_prefix (opt, "bridge=")) {
411 opt = strchr (opt, '=') + 1;
412 register_test_bridge_callbacks (g_strdup (opt));
413 } else if (!strcmp (opt, "enable-bridge-accounting")) {
414 bridge_processor.enable_accounting ();
415 } else if (g_str_has_prefix (opt, "bridge-dump=")) {
416 char *prefix = strchr (opt, '=') + 1;
417 set_dump_prefix (prefix);
418 } else if (g_str_has_prefix (opt, "bridge-compare-to=")) {
419 const char *name = strchr (opt, '=') + 1;
420 if (init_bridge_processor (&compare_to_bridge_processor, name)) {
421 if (compare_to_bridge_processor.reset_data == bridge_processor.reset_data) {
422 g_warning ("Cannot compare bridge implementation to itself - ignoring.");
423 memset (&compare_to_bridge_processor, 0, sizeof (SgenBridgeProcessor));
426 g_warning ("Invalid bridge implementation to compare against - ignoring.");
435 sgen_bridge_print_gc_debug_usage (void)
437 fprintf (stderr, " bridge=<class-name>\n");
438 fprintf (stderr, " enable-bridge-accounting\n");
439 fprintf (stderr, " bridge-dump=<filename-prefix>\n");
440 fprintf (stderr, " bridge-compare-to=<implementation>\n");