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.
46 #include "sgen/sgen-gc.h"
47 #include "sgen-bridge-internals.h"
48 #include "sgen/sgen-hash-table.h"
49 #include "sgen/sgen-qsort.h"
50 #include "utils/mono-logger-internals.h"
52 MonoGCBridgeCallbacks bridge_callbacks;
53 static SgenBridgeProcessor bridge_processor;
54 static SgenBridgeProcessor compare_to_bridge_processor;
56 volatile gboolean bridge_processing_in_progress = FALSE;
59 mono_gc_wait_for_bridge_processing (void)
61 if (!bridge_processing_in_progress)
64 mono_trace (G_LOG_LEVEL_INFO, MONO_TRACE_GC, "GC_BRIDGE waiting for bridge processing to finish");
72 mono_gc_register_bridge_callbacks (MonoGCBridgeCallbacks *callbacks)
74 if (callbacks->bridge_version != SGEN_BRIDGE_VERSION)
75 g_error ("Invalid bridge callback version. Expected %d but got %d\n", SGEN_BRIDGE_VERSION, callbacks->bridge_version);
77 bridge_callbacks = *callbacks;
79 if (!bridge_processor.reset_data)
80 sgen_new_bridge_init (&bridge_processor);
84 init_bridge_processor (SgenBridgeProcessor *processor, const char *name)
86 if (!strcmp ("old", name)) {
87 memset (processor, 0, sizeof (SgenBridgeProcessor));
88 sgen_old_bridge_init (processor);
89 } else if (!strcmp ("new", name)) {
90 memset (processor, 0, sizeof (SgenBridgeProcessor));
91 sgen_new_bridge_init (processor);
92 } else if (!strcmp ("tarjan", name)) {
93 memset (processor, 0, sizeof (SgenBridgeProcessor));
94 sgen_tarjan_bridge_init (processor);
102 sgen_set_bridge_implementation (const char *name)
104 if (!init_bridge_processor (&bridge_processor, name))
105 g_warning ("Invalid value for bridge implementation, valid values are: 'new' and 'old'.");
109 sgen_is_bridge_object (GCObject *obj)
111 if ((obj->vtable->gc_bits & SGEN_GC_BIT_BRIDGE_OBJECT) != SGEN_GC_BIT_BRIDGE_OBJECT)
113 return bridge_callbacks.is_bridge_object (obj);
117 sgen_need_bridge_processing (void)
119 return bridge_callbacks.cross_references != NULL;
123 compare_bridge_processors (void)
125 return compare_to_bridge_processor.reset_data != NULL;
128 /* Dispatch wrappers */
130 sgen_bridge_reset_data (void)
132 bridge_processor.reset_data ();
133 if (compare_bridge_processors ())
134 compare_to_bridge_processor.reset_data ();
138 sgen_bridge_processing_stw_step (void)
141 * bridge_processing_in_progress must be set with the world
142 * stopped. If not there would be race conditions.
144 bridge_processing_in_progress = TRUE;
146 bridge_processor.processing_stw_step ();
147 if (compare_bridge_processors ())
148 compare_to_bridge_processor.processing_stw_step ();
152 is_bridge_object_dead (GCObject *obj, void *data)
154 SgenHashTable *table = (SgenHashTable *)data;
155 unsigned char *value = (unsigned char *)sgen_hash_table_lookup (table, obj);
162 null_weak_links_to_dead_objects (SgenBridgeProcessor *processor, int generation)
165 int num_sccs = processor->num_sccs;
166 MonoGCBridgeSCC **api_sccs = processor->api_sccs;
167 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);
169 for (i = 0; i < num_sccs; ++i) {
170 unsigned char alive = api_sccs [i]->is_alive ? 1 : 0;
171 for (j = 0; j < api_sccs [i]->num_objs; ++j) {
172 /* Build hash table for nulling weak links. */
173 sgen_hash_table_replace (&alive_hash, api_sccs [i]->objs [j], &alive, NULL);
175 /* Release for finalization those objects we no longer care. */
176 if (!api_sccs [i]->is_alive)
177 sgen_mark_bridge_object (api_sccs [i]->objs [j]);
181 /* Null weak links to dead objects. */
182 sgen_null_links_if (is_bridge_object_dead, &alive_hash, GENERATION_NURSERY, FALSE);
183 sgen_null_links_if (is_bridge_object_dead, &alive_hash, GENERATION_NURSERY, TRUE);
184 if (generation == GENERATION_OLD) {
185 sgen_null_links_if (is_bridge_object_dead, &alive_hash, GENERATION_OLD, FALSE);
186 sgen_null_links_if (is_bridge_object_dead, &alive_hash, GENERATION_OLD, TRUE);
189 sgen_hash_table_clean (&alive_hash);
193 free_callback_data (SgenBridgeProcessor *processor)
196 int num_sccs = processor->num_sccs;
197 int num_xrefs = processor->num_xrefs;
198 MonoGCBridgeSCC **api_sccs = processor->api_sccs;
199 MonoGCBridgeXRef *api_xrefs = processor->api_xrefs;
201 for (i = 0; i < num_sccs; ++i) {
202 sgen_free_internal_dynamic (api_sccs [i],
203 sizeof (MonoGCBridgeSCC) + sizeof (MonoObject*) * api_sccs [i]->num_objs,
204 INTERNAL_MEM_BRIDGE_DATA);
206 sgen_free_internal_dynamic (api_sccs, sizeof (MonoGCBridgeSCC*) * num_sccs, INTERNAL_MEM_BRIDGE_DATA);
208 sgen_free_internal_dynamic (api_xrefs, sizeof (MonoGCBridgeXRef) * num_xrefs, INTERNAL_MEM_BRIDGE_DATA);
210 processor->num_sccs = 0;
211 processor->api_sccs = NULL;
212 processor->num_xrefs = 0;
213 processor->api_xrefs = NULL;
217 compare_xrefs (const void *a_ptr, const void *b_ptr)
219 const MonoGCBridgeXRef *a = (const MonoGCBridgeXRef *)a_ptr;
220 const MonoGCBridgeXRef *b = (const MonoGCBridgeXRef *)b_ptr;
222 if (a->src_scc_index < b->src_scc_index)
224 if (a->src_scc_index > b->src_scc_index)
227 if (a->dst_scc_index < b->dst_scc_index)
229 if (a->dst_scc_index > b->dst_scc_index)
237 dump_processor_state (SgenBridgeProcessor *p)
242 printf ("SCCS %d\n", p->num_sccs);
243 for (i = 0; i < p->num_sccs; ++i) {
245 MonoGCBridgeSCC *scc = p->api_sccs [i];
246 printf ("\tSCC %d:", i);
247 for (j = 0; j < scc->num_objs; ++j) {
248 MonoObject *obj = scc->objs [j];
254 printf ("XREFS %d\n", p->num_xrefs);
255 for (i = 0; i < p->num_xrefs; ++i)
256 printf ("\t%d -> %d\n", p->api_xrefs [i].src_scc_index, p->api_xrefs [i].dst_scc_index);
258 printf ("-------\n");
263 sgen_compare_bridge_processor_results (SgenBridgeProcessor *a, SgenBridgeProcessor *b)
266 SgenHashTable obj_to_a_scc = SGEN_HASH_TABLE_INIT (INTERNAL_MEM_BRIDGE_DEBUG, INTERNAL_MEM_BRIDGE_DEBUG, sizeof (int), mono_aligned_addr_hash, NULL);
267 SgenHashTable b_scc_to_a_scc = SGEN_HASH_TABLE_INIT (INTERNAL_MEM_BRIDGE_DEBUG, INTERNAL_MEM_BRIDGE_DEBUG, sizeof (int), g_direct_hash, NULL);
268 MonoGCBridgeXRef *a_xrefs, *b_xrefs;
269 size_t xrefs_alloc_size;
271 // dump_processor_state (a);
272 // dump_processor_state (b);
274 if (a->num_sccs != b->num_sccs)
275 g_error ("SCCS count expected %d but got %d", a->num_sccs, b->num_sccs);
276 if (a->num_xrefs != b->num_xrefs)
277 g_error ("SCCS count expected %d but got %d", a->num_xrefs, b->num_xrefs);
280 * First we build a hash of each object in `a` to its respective SCC index within
281 * `a`. Along the way we also assert that no object is more than one SCC.
283 for (i = 0; i < a->num_sccs; ++i) {
285 MonoGCBridgeSCC *scc = a->api_sccs [i];
287 g_assert (scc->num_objs > 0);
289 for (j = 0; j < scc->num_objs; ++j) {
290 GCObject *obj = scc->objs [j];
291 gboolean new_entry = sgen_hash_table_replace (&obj_to_a_scc, obj, &i, NULL);
292 g_assert (new_entry);
297 * Now we check whether each of the objects in `b` are in `a`, and whether the SCCs
298 * of `b` contain the same sets of objects as those of `a`.
300 * While we're doing this, build a hash table to map from `b` SCC indexes to `a` SCC
303 for (i = 0; i < b->num_sccs; ++i) {
304 MonoGCBridgeSCC *scc = b->api_sccs [i];
305 MonoGCBridgeSCC *a_scc;
306 int *a_scc_index_ptr;
311 g_assert (scc->num_objs > 0);
312 a_scc_index_ptr = (int *)sgen_hash_table_lookup (&obj_to_a_scc, scc->objs [0]);
313 g_assert (a_scc_index_ptr);
314 a_scc_index = *a_scc_index_ptr;
316 //g_print ("A SCC %d -> B SCC %d\n", a_scc_index, i);
318 a_scc = a->api_sccs [a_scc_index];
319 g_assert (a_scc->num_objs == scc->num_objs);
321 for (j = 1; j < scc->num_objs; ++j) {
322 a_scc_index_ptr = (int *)sgen_hash_table_lookup (&obj_to_a_scc, scc->objs [j]);
323 g_assert (a_scc_index_ptr);
324 g_assert (*a_scc_index_ptr == a_scc_index);
327 new_entry = sgen_hash_table_replace (&b_scc_to_a_scc, GINT_TO_POINTER (i), &a_scc_index, NULL);
328 g_assert (new_entry);
332 * Finally, check that we have the same xrefs. We do this by making copies of both
333 * xref arrays, and replacing the SCC indexes in the copy for `b` with the
334 * corresponding indexes in `a`. Then we sort both arrays and assert that they're
337 * At the same time, check that no xref is self-referential and that there are no
341 xrefs_alloc_size = a->num_xrefs * sizeof (MonoGCBridgeXRef);
342 a_xrefs = (MonoGCBridgeXRef *)sgen_alloc_internal_dynamic (xrefs_alloc_size, INTERNAL_MEM_BRIDGE_DEBUG, TRUE);
343 b_xrefs = (MonoGCBridgeXRef *)sgen_alloc_internal_dynamic (xrefs_alloc_size, INTERNAL_MEM_BRIDGE_DEBUG, TRUE);
345 memcpy (a_xrefs, a->api_xrefs, xrefs_alloc_size);
346 for (i = 0; i < b->num_xrefs; ++i) {
347 MonoGCBridgeXRef *xref = &b->api_xrefs [i];
350 g_assert (xref->src_scc_index != xref->dst_scc_index);
352 scc_index_ptr = (int *)sgen_hash_table_lookup (&b_scc_to_a_scc, GINT_TO_POINTER (xref->src_scc_index));
353 g_assert (scc_index_ptr);
354 b_xrefs [i].src_scc_index = *scc_index_ptr;
356 scc_index_ptr = (int *)sgen_hash_table_lookup (&b_scc_to_a_scc, GINT_TO_POINTER (xref->dst_scc_index));
357 g_assert (scc_index_ptr);
358 b_xrefs [i].dst_scc_index = *scc_index_ptr;
361 qsort (a_xrefs, a->num_xrefs, sizeof (MonoGCBridgeXRef), compare_xrefs);
362 qsort (b_xrefs, a->num_xrefs, sizeof (MonoGCBridgeXRef), compare_xrefs);
364 for (i = 0; i < a->num_xrefs; ++i) {
365 g_assert (a_xrefs [i].src_scc_index == b_xrefs [i].src_scc_index);
366 g_assert (a_xrefs [i].dst_scc_index == b_xrefs [i].dst_scc_index);
369 sgen_hash_table_clean (&obj_to_a_scc);
370 sgen_hash_table_clean (&b_scc_to_a_scc);
371 sgen_free_internal_dynamic (a_xrefs, xrefs_alloc_size, INTERNAL_MEM_BRIDGE_DEBUG);
372 sgen_free_internal_dynamic (b_xrefs, xrefs_alloc_size, INTERNAL_MEM_BRIDGE_DEBUG);
378 sgen_bridge_processing_finish (int generation)
380 bridge_processor.processing_build_callback_data (generation);
381 if (compare_bridge_processors ())
382 compare_to_bridge_processor.processing_build_callback_data (generation);
384 if (bridge_processor.num_sccs == 0) {
385 g_assert (bridge_processor.num_xrefs == 0);
389 bridge_callbacks.cross_references (bridge_processor.num_sccs, bridge_processor.api_sccs,
390 bridge_processor.num_xrefs, bridge_processor.api_xrefs);
392 if (compare_bridge_processors ())
393 sgen_compare_bridge_processor_results (&bridge_processor, &compare_to_bridge_processor);
395 null_weak_links_to_dead_objects (&bridge_processor, generation);
397 free_callback_data (&bridge_processor);
398 if (compare_bridge_processors ())
399 free_callback_data (&compare_to_bridge_processor);
402 bridge_processor.processing_after_callback (generation);
403 if (compare_bridge_processors ())
404 compare_to_bridge_processor.processing_after_callback (generation);
406 bridge_processing_in_progress = FALSE;
409 MonoGCBridgeObjectKind
410 sgen_bridge_class_kind (MonoClass *klass)
412 return bridge_processor.class_kind (klass);
416 sgen_bridge_register_finalized_object (GCObject *obj)
418 bridge_processor.register_finalized_object (obj);
419 if (compare_bridge_processors ())
420 compare_to_bridge_processor.register_finalized_object (obj);
424 sgen_bridge_describe_pointer (GCObject *obj)
426 if (bridge_processor.describe_pointer)
427 bridge_processor.describe_pointer (obj);
431 set_dump_prefix (const char *prefix)
433 if (!bridge_processor.set_dump_prefix) {
434 fprintf (stderr, "Warning: Bridge implementation does not support dumping - ignoring.\n");
438 bridge_processor.set_dump_prefix (prefix);
441 /* Test support code */
442 static const char *bridge_class;
444 static MonoGCBridgeObjectKind
445 bridge_test_bridge_class_kind (MonoClass *klass)
447 if (!strcmp (bridge_class, klass->name))
448 return GC_BRIDGE_TRANSPARENT_BRIDGE_CLASS;
449 return GC_BRIDGE_TRANSPARENT_CLASS;
453 bridge_test_is_bridge_object (MonoObject *object)
459 bridge_test_cross_reference (int num_sccs, MonoGCBridgeSCC **sccs, int num_xrefs, MonoGCBridgeXRef *xrefs)
462 for (i = 0; i < num_sccs; ++i) {
464 // g_print ("--- SCC %d\n", i);
465 for (j = 0; j < sccs [i]->num_objs; ++j) {
466 // g_print (" %s\n", sgen_safe_name (sccs [i]->objs [j]));
467 if (i & 1) /*retain half of the bridged objects */
468 sccs [i]->is_alive = TRUE;
471 for (i = 0; i < num_xrefs; ++i) {
472 g_assert (xrefs [i].src_scc_index >= 0 && xrefs [i].src_scc_index < num_sccs);
473 g_assert (xrefs [i].dst_scc_index >= 0 && xrefs [i].dst_scc_index < num_sccs);
474 // g_print ("%d -> %d\n", xrefs [i].src_scc_index, xrefs [i].dst_scc_index);
478 static MonoClassField *mono_bridge_test_field;
488 test_scc (MonoGCBridgeSCC *scc, int i)
490 int status = BRIDGE_DEAD;
491 mono_field_get_value (scc->objs [i], mono_bridge_test_field, &status);
496 mark_scc (MonoGCBridgeSCC *scc, int value)
499 for (i = 0; i < scc->num_objs; ++i) {
500 if (!test_scc (scc, i)) {
502 mono_field_set_value (scc->objs [i], mono_bridge_test_field, &status);
508 bridge_test_cross_reference2 (int num_sccs, MonoGCBridgeSCC **sccs, int num_xrefs, MonoGCBridgeXRef *xrefs)
513 if (!mono_bridge_test_field) {
514 mono_bridge_test_field = mono_class_get_field_from_name (mono_object_get_class (sccs[0]->objs [0]), "__test");
515 g_assert (mono_bridge_test_field);
518 /*We mark all objects in a scc with live objects as reachable by scc*/
519 for (i = 0; i < num_sccs; ++i) {
521 gboolean live = FALSE;
522 for (j = 0; j < sccs [i]->num_objs; ++j) {
523 if (test_scc (sccs [i], j)) {
530 for (j = 0; j < sccs [i]->num_objs; ++j) {
531 if (!test_scc (sccs [i], j)) {
532 int status = BRIDGE_SAME_SCC;
533 mono_field_set_value (sccs [i]->objs [j], mono_bridge_test_field, &status);
538 /*Now we mark the transitive closure of reachable objects from the xrefs*/
542 /* Mark all objects that are brought to life due to xrefs*/
543 for (i = 0; i < num_xrefs; ++i) {
544 MonoGCBridgeXRef ref = xrefs [i];
545 if (test_scc (sccs [ref.src_scc_index], 0) && !test_scc (sccs [ref.dst_scc_index], 0)) {
547 mark_scc (sccs [ref.dst_scc_index], BRIDGE_XREF);
552 /* keep everything in memory, all we want to do is test persistence */
553 for (i = 0; i < num_sccs; ++i)
554 sccs [i]->is_alive = TRUE;
558 register_test_bridge_callbacks (const char *bridge_class_name)
560 MonoGCBridgeCallbacks callbacks;
561 callbacks.bridge_version = SGEN_BRIDGE_VERSION;
562 callbacks.bridge_class_kind = bridge_test_bridge_class_kind;
563 callbacks.is_bridge_object = bridge_test_is_bridge_object;
564 callbacks.cross_references = bridge_class_name[0] == '2' ? bridge_test_cross_reference2 : bridge_test_cross_reference;
565 mono_gc_register_bridge_callbacks (&callbacks);
566 bridge_class = bridge_class_name + (bridge_class_name[0] == '2' ? 1 : 0);
570 sgen_bridge_handle_gc_debug (const char *opt)
572 if (g_str_has_prefix (opt, "bridge=")) {
573 opt = strchr (opt, '=') + 1;
574 register_test_bridge_callbacks (g_strdup (opt));
575 } else if (!strcmp (opt, "enable-bridge-accounting")) {
576 bridge_processor.enable_accounting ();
577 } else if (g_str_has_prefix (opt, "bridge-dump=")) {
578 char *prefix = strchr (opt, '=') + 1;
579 set_dump_prefix (prefix);
580 } else if (g_str_has_prefix (opt, "bridge-compare-to=")) {
581 const char *name = strchr (opt, '=') + 1;
582 if (init_bridge_processor (&compare_to_bridge_processor, name)) {
583 if (compare_to_bridge_processor.reset_data == bridge_processor.reset_data) {
584 g_warning ("Cannot compare bridge implementation to itself - ignoring.");
585 memset (&compare_to_bridge_processor, 0, sizeof (SgenBridgeProcessor));
588 g_warning ("Invalid bridge implementation to compare against - ignoring.");
597 sgen_bridge_print_gc_debug_usage (void)
599 fprintf (stderr, " bridge=<class-name>\n");
600 fprintf (stderr, " enable-bridge-accounting\n");
601 fprintf (stderr, " bridge-dump=<filename-prefix>\n");
602 fprintf (stderr, " bridge-compare-to=<implementation>\n");