First set of licensing changes
[mono.git] / mono / metadata / sgen-bridge.c
1 /*
2  * sgen-bridge.c: Simple generational GC.
3  *
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.
8  *
9  * Licensed under the MIT license. See LICENSE file in the project root for full license information.
10  */
11
12 #include "config.h"
13
14 #ifdef HAVE_SGEN_GC
15
16 #include <stdlib.h>
17
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"
23
24 MonoGCBridgeCallbacks bridge_callbacks;
25 static SgenBridgeProcessor bridge_processor;
26 static SgenBridgeProcessor compare_to_bridge_processor;
27
28 volatile gboolean bridge_processing_in_progress = FALSE;
29
30 void
31 mono_gc_wait_for_bridge_processing (void)
32 {
33         if (!bridge_processing_in_progress)
34                 return;
35
36         mono_trace (G_LOG_LEVEL_INFO, MONO_TRACE_GC, "GC_BRIDGE waiting for bridge processing to finish");
37
38         sgen_gc_lock ();
39         sgen_gc_unlock ();
40 }
41
42
43 void
44 mono_gc_register_bridge_callbacks (MonoGCBridgeCallbacks *callbacks)
45 {
46         if (callbacks->bridge_version != SGEN_BRIDGE_VERSION)
47                 g_error ("Invalid bridge callback version. Expected %d but got %d\n", SGEN_BRIDGE_VERSION, callbacks->bridge_version);
48
49         bridge_callbacks = *callbacks;
50
51         if (!bridge_processor.reset_data)
52                 sgen_new_bridge_init (&bridge_processor);
53 }
54
55 static gboolean
56 init_bridge_processor (SgenBridgeProcessor *processor, const char *name)
57 {
58         if (!strcmp ("old", name)) {
59                 memset (processor, 0, sizeof (SgenBridgeProcessor));
60                 sgen_old_bridge_init (processor);
61         } else if (!strcmp ("new", name)) {
62                 memset (processor, 0, sizeof (SgenBridgeProcessor));
63                 sgen_new_bridge_init (processor);
64         } else if (!strcmp ("tarjan", name)) {
65                 memset (processor, 0, sizeof (SgenBridgeProcessor));
66                 sgen_tarjan_bridge_init (processor);
67         } else {
68                 return FALSE;
69         }
70         return TRUE;
71 }
72
73 void
74 sgen_set_bridge_implementation (const char *name)
75 {
76         if (!init_bridge_processor (&bridge_processor, name))
77                 g_warning ("Invalid value for bridge implementation, valid values are: 'new' and 'old'.");
78 }
79
80 gboolean
81 sgen_is_bridge_object (GCObject *obj)
82 {
83         if ((obj->vtable->gc_bits & SGEN_GC_BIT_BRIDGE_OBJECT) != SGEN_GC_BIT_BRIDGE_OBJECT)
84                 return FALSE;
85         return bridge_callbacks.is_bridge_object (obj);
86 }
87
88 gboolean
89 sgen_need_bridge_processing (void)
90 {
91         return bridge_callbacks.cross_references != NULL;
92 }
93
94 static gboolean
95 compare_bridge_processors (void)
96 {
97         return compare_to_bridge_processor.reset_data != NULL;
98 }
99
100 /* Dispatch wrappers */
101 void
102 sgen_bridge_reset_data (void)
103 {
104         bridge_processor.reset_data ();
105         if (compare_bridge_processors ())
106                 compare_to_bridge_processor.reset_data ();
107 }
108
109 void
110 sgen_bridge_processing_stw_step (void)
111 {
112         /*
113          * bridge_processing_in_progress must be set with the world
114          * stopped.  If not there would be race conditions.
115          */
116         bridge_processing_in_progress = TRUE;
117
118         bridge_processor.processing_stw_step ();
119         if (compare_bridge_processors ())
120                 compare_to_bridge_processor.processing_stw_step ();
121 }
122
123 static gboolean
124 is_bridge_object_dead (GCObject *obj, void *data)
125 {
126         SgenHashTable *table = (SgenHashTable *)data;
127         unsigned char *value = (unsigned char *)sgen_hash_table_lookup (table, obj);
128         if (!value)
129                 return FALSE;
130         return !*value;
131 }
132
133 static void
134 null_weak_links_to_dead_objects (SgenBridgeProcessor *processor, int generation)
135 {
136         int i, j;
137         int num_sccs = processor->num_sccs;
138         MonoGCBridgeSCC **api_sccs = processor->api_sccs;
139         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);
140
141         for (i = 0; i < num_sccs; ++i) {
142                 unsigned char alive = api_sccs [i]->is_alive ? 1 : 0;
143                 for (j = 0; j < api_sccs [i]->num_objs; ++j) {
144                         /* Build hash table for nulling weak links. */
145                         sgen_hash_table_replace (&alive_hash, api_sccs [i]->objs [j], &alive, NULL);
146
147                         /* Release for finalization those objects we no longer care. */
148                         if (!api_sccs [i]->is_alive)
149                                 sgen_mark_bridge_object (api_sccs [i]->objs [j]);
150                 }
151         }
152
153         /* Null weak links to dead objects. */
154         sgen_null_links_if (is_bridge_object_dead, &alive_hash, GENERATION_NURSERY, FALSE);
155         sgen_null_links_if (is_bridge_object_dead, &alive_hash, GENERATION_NURSERY, TRUE);
156         if (generation == GENERATION_OLD) {
157                 sgen_null_links_if (is_bridge_object_dead, &alive_hash, GENERATION_OLD, FALSE);
158                 sgen_null_links_if (is_bridge_object_dead, &alive_hash, GENERATION_OLD, TRUE);
159         }
160
161         sgen_hash_table_clean (&alive_hash);
162 }
163
164 static void
165 free_callback_data (SgenBridgeProcessor *processor)
166 {
167         int i;
168         int num_sccs = processor->num_sccs;
169         int num_xrefs = processor->num_xrefs;
170         MonoGCBridgeSCC **api_sccs = processor->api_sccs;
171         MonoGCBridgeXRef *api_xrefs = processor->api_xrefs;
172
173         for (i = 0; i < num_sccs; ++i) {
174                 sgen_free_internal_dynamic (api_sccs [i],
175                                 sizeof (MonoGCBridgeSCC) + sizeof (MonoObject*) * api_sccs [i]->num_objs,
176                                 INTERNAL_MEM_BRIDGE_DATA);
177         }
178         sgen_free_internal_dynamic (api_sccs, sizeof (MonoGCBridgeSCC*) * num_sccs, INTERNAL_MEM_BRIDGE_DATA);
179
180         sgen_free_internal_dynamic (api_xrefs, sizeof (MonoGCBridgeXRef) * num_xrefs, INTERNAL_MEM_BRIDGE_DATA);
181
182         processor->num_sccs = 0;
183         processor->api_sccs = NULL;
184         processor->num_xrefs = 0;
185         processor->api_xrefs = NULL;
186 }
187
188 static int
189 compare_xrefs (const void *a_ptr, const void *b_ptr)
190 {
191         const MonoGCBridgeXRef *a = (const MonoGCBridgeXRef *)a_ptr;
192         const MonoGCBridgeXRef *b = (const MonoGCBridgeXRef *)b_ptr;
193
194         if (a->src_scc_index < b->src_scc_index)
195                 return -1;
196         if (a->src_scc_index > b->src_scc_index)
197                 return 1;
198
199         if (a->dst_scc_index < b->dst_scc_index)
200                 return -1;
201         if (a->dst_scc_index > b->dst_scc_index)
202                 return 1;
203
204         return 0;
205 }
206
207 /*
208 static void
209 dump_processor_state (SgenBridgeProcessor *p)
210 {
211         int i;
212
213         printf ("------\n");
214         printf ("SCCS %d\n", p->num_sccs);
215         for (i = 0; i < p->num_sccs; ++i) {
216                 int j;
217                 MonoGCBridgeSCC *scc = p->api_sccs [i];
218                 printf ("\tSCC %d:", i);
219                 for (j = 0; j < scc->num_objs; ++j) {
220                         MonoObject *obj = scc->objs [j];
221                         printf (" %p", obj);
222                 }
223                 printf ("\n");
224         }
225
226         printf ("XREFS %d\n", p->num_xrefs);
227         for (i = 0; i < p->num_xrefs; ++i)
228                 printf ("\t%d -> %d\n", p->api_xrefs [i].src_scc_index, p->api_xrefs [i].dst_scc_index);
229
230         printf ("-------\n");
231 }
232 */
233
234 static gboolean
235 sgen_compare_bridge_processor_results (SgenBridgeProcessor *a, SgenBridgeProcessor *b)
236 {
237         int i;
238         SgenHashTable obj_to_a_scc = SGEN_HASH_TABLE_INIT (INTERNAL_MEM_BRIDGE_DEBUG, INTERNAL_MEM_BRIDGE_DEBUG, sizeof (int), mono_aligned_addr_hash, NULL);
239         SgenHashTable b_scc_to_a_scc = SGEN_HASH_TABLE_INIT (INTERNAL_MEM_BRIDGE_DEBUG, INTERNAL_MEM_BRIDGE_DEBUG, sizeof (int), g_direct_hash, NULL);
240         MonoGCBridgeXRef *a_xrefs, *b_xrefs;
241         size_t xrefs_alloc_size;
242
243         // dump_processor_state (a);
244         // dump_processor_state (b);
245
246         if (a->num_sccs != b->num_sccs)
247                 g_error ("SCCS count expected %d but got %d", a->num_sccs, b->num_sccs);
248         if (a->num_xrefs != b->num_xrefs)
249                 g_error ("SCCS count expected %d but got %d", a->num_xrefs, b->num_xrefs);
250
251         /*
252          * First we build a hash of each object in `a` to its respective SCC index within
253          * `a`.  Along the way we also assert that no object is more than one SCC.
254          */
255         for (i = 0; i < a->num_sccs; ++i) {
256                 int j;
257                 MonoGCBridgeSCC *scc = a->api_sccs [i];
258
259                 g_assert (scc->num_objs > 0);
260
261                 for (j = 0; j < scc->num_objs; ++j) {
262                         GCObject *obj = scc->objs [j];
263                         gboolean new_entry = sgen_hash_table_replace (&obj_to_a_scc, obj, &i, NULL);
264                         g_assert (new_entry);
265                 }
266         }
267
268         /*
269          * Now we check whether each of the objects in `b` are in `a`, and whether the SCCs
270          * of `b` contain the same sets of objects as those of `a`.
271          *
272          * While we're doing this, build a hash table to map from `b` SCC indexes to `a` SCC
273          * indexes.
274          */
275         for (i = 0; i < b->num_sccs; ++i) {
276                 MonoGCBridgeSCC *scc = b->api_sccs [i];
277                 MonoGCBridgeSCC *a_scc;
278                 int *a_scc_index_ptr;
279                 int a_scc_index;
280                 int j;
281                 gboolean new_entry;
282
283                 g_assert (scc->num_objs > 0);
284                 a_scc_index_ptr = (int *)sgen_hash_table_lookup (&obj_to_a_scc, scc->objs [0]);
285                 g_assert (a_scc_index_ptr);
286                 a_scc_index = *a_scc_index_ptr;
287
288                 //g_print ("A SCC %d -> B SCC %d\n", a_scc_index, i);
289
290                 a_scc = a->api_sccs [a_scc_index];
291                 g_assert (a_scc->num_objs == scc->num_objs);
292
293                 for (j = 1; j < scc->num_objs; ++j) {
294                         a_scc_index_ptr = (int *)sgen_hash_table_lookup (&obj_to_a_scc, scc->objs [j]);
295                         g_assert (a_scc_index_ptr);
296                         g_assert (*a_scc_index_ptr == a_scc_index);
297                 }
298
299                 new_entry = sgen_hash_table_replace (&b_scc_to_a_scc, GINT_TO_POINTER (i), &a_scc_index, NULL);
300                 g_assert (new_entry);
301         }
302
303         /*
304          * Finally, check that we have the same xrefs.  We do this by making copies of both
305          * xref arrays, and replacing the SCC indexes in the copy for `b` with the
306          * corresponding indexes in `a`.  Then we sort both arrays and assert that they're
307          * the same.
308          *
309          * At the same time, check that no xref is self-referential and that there are no
310          * duplicate ones.
311          */
312
313         xrefs_alloc_size = a->num_xrefs * sizeof (MonoGCBridgeXRef);
314         a_xrefs = (MonoGCBridgeXRef *)sgen_alloc_internal_dynamic (xrefs_alloc_size, INTERNAL_MEM_BRIDGE_DEBUG, TRUE);
315         b_xrefs = (MonoGCBridgeXRef *)sgen_alloc_internal_dynamic (xrefs_alloc_size, INTERNAL_MEM_BRIDGE_DEBUG, TRUE);
316
317         memcpy (a_xrefs, a->api_xrefs, xrefs_alloc_size);
318         for (i = 0; i < b->num_xrefs; ++i) {
319                 MonoGCBridgeXRef *xref = &b->api_xrefs [i];
320                 int *scc_index_ptr;
321
322                 g_assert (xref->src_scc_index != xref->dst_scc_index);
323
324                 scc_index_ptr = (int *)sgen_hash_table_lookup (&b_scc_to_a_scc, GINT_TO_POINTER (xref->src_scc_index));
325                 g_assert (scc_index_ptr);
326                 b_xrefs [i].src_scc_index = *scc_index_ptr;
327
328                 scc_index_ptr = (int *)sgen_hash_table_lookup (&b_scc_to_a_scc, GINT_TO_POINTER (xref->dst_scc_index));
329                 g_assert (scc_index_ptr);
330                 b_xrefs [i].dst_scc_index = *scc_index_ptr;
331         }
332
333         qsort (a_xrefs, a->num_xrefs, sizeof (MonoGCBridgeXRef), compare_xrefs);
334         qsort (b_xrefs, a->num_xrefs, sizeof (MonoGCBridgeXRef), compare_xrefs);
335
336         for (i = 0; i < a->num_xrefs; ++i) {
337                 g_assert (a_xrefs [i].src_scc_index == b_xrefs [i].src_scc_index);
338                 g_assert (a_xrefs [i].dst_scc_index == b_xrefs [i].dst_scc_index);
339         }
340
341         sgen_hash_table_clean (&obj_to_a_scc);
342         sgen_hash_table_clean (&b_scc_to_a_scc);
343         sgen_free_internal_dynamic (a_xrefs, xrefs_alloc_size, INTERNAL_MEM_BRIDGE_DEBUG);
344         sgen_free_internal_dynamic (b_xrefs, xrefs_alloc_size, INTERNAL_MEM_BRIDGE_DEBUG);
345
346         return TRUE;
347 }
348
349 void
350 sgen_bridge_processing_finish (int generation)
351 {
352         bridge_processor.processing_build_callback_data (generation);
353         if (compare_bridge_processors ())
354                 compare_to_bridge_processor.processing_build_callback_data (generation);
355
356         if (bridge_processor.num_sccs == 0) {
357                 g_assert (bridge_processor.num_xrefs == 0);
358                 goto after_callback;
359         }
360
361         bridge_callbacks.cross_references (bridge_processor.num_sccs, bridge_processor.api_sccs,
362                         bridge_processor.num_xrefs, bridge_processor.api_xrefs);
363
364         if (compare_bridge_processors ())
365                 sgen_compare_bridge_processor_results (&bridge_processor, &compare_to_bridge_processor);
366
367         null_weak_links_to_dead_objects (&bridge_processor, generation);
368
369         free_callback_data (&bridge_processor);
370         if (compare_bridge_processors ())
371                 free_callback_data (&compare_to_bridge_processor);
372
373  after_callback:
374         bridge_processor.processing_after_callback (generation);
375         if (compare_bridge_processors ())
376                 compare_to_bridge_processor.processing_after_callback (generation);
377
378         bridge_processing_in_progress = FALSE;
379 }
380
381 MonoGCBridgeObjectKind
382 sgen_bridge_class_kind (MonoClass *klass)
383 {
384         return bridge_processor.class_kind (klass);
385 }
386
387 void
388 sgen_bridge_register_finalized_object (GCObject *obj)
389 {
390         bridge_processor.register_finalized_object (obj);
391         if (compare_bridge_processors ())
392                 compare_to_bridge_processor.register_finalized_object (obj);
393 }
394
395 void
396 sgen_bridge_describe_pointer (GCObject *obj)
397 {
398         if (bridge_processor.describe_pointer)
399                 bridge_processor.describe_pointer (obj);
400 }
401
402 static void
403 set_dump_prefix (const char *prefix)
404 {
405         if (!bridge_processor.set_dump_prefix) {
406                 fprintf (stderr, "Warning: Bridge implementation does not support dumping - ignoring.\n");
407                 return;
408         }
409
410         bridge_processor.set_dump_prefix (prefix);
411 }
412
413 /* Test support code */
414 static const char *bridge_class;
415
416 static MonoGCBridgeObjectKind
417 bridge_test_bridge_class_kind (MonoClass *klass)
418 {
419         if (!strcmp (bridge_class, klass->name))
420                 return GC_BRIDGE_TRANSPARENT_BRIDGE_CLASS;
421         return GC_BRIDGE_TRANSPARENT_CLASS;
422 }
423
424 static gboolean
425 bridge_test_is_bridge_object (MonoObject *object)
426 {
427         return TRUE;
428 }
429
430 static void
431 bridge_test_cross_reference (int num_sccs, MonoGCBridgeSCC **sccs, int num_xrefs, MonoGCBridgeXRef *xrefs)
432 {
433         int i;
434         for (i = 0; i < num_sccs; ++i) {
435                 int j;
436         //      g_print ("--- SCC %d\n", i);
437                 for (j = 0; j < sccs [i]->num_objs; ++j) {
438         //              g_print ("  %s\n", sgen_safe_name (sccs [i]->objs [j]));
439                         if (i & 1) /*retain half of the bridged objects */
440                                 sccs [i]->is_alive = TRUE;
441                 }
442         }
443         for (i = 0; i < num_xrefs; ++i) {
444                 g_assert (xrefs [i].src_scc_index >= 0 && xrefs [i].src_scc_index < num_sccs);
445                 g_assert (xrefs [i].dst_scc_index >= 0 && xrefs [i].dst_scc_index < num_sccs);
446         //      g_print ("%d -> %d\n", xrefs [i].src_scc_index, xrefs [i].dst_scc_index);
447         }
448 }
449
450 static MonoClassField *mono_bridge_test_field;
451
452 enum {
453         BRIDGE_DEAD,
454         BRIDGE_ROOT,
455         BRIDGE_SAME_SCC,
456         BRIDGE_XREF,
457 };
458
459 static gboolean
460 test_scc (MonoGCBridgeSCC *scc, int i)
461 {
462         int status = BRIDGE_DEAD;
463         mono_field_get_value (scc->objs [i], mono_bridge_test_field, &status);
464         return status > 0;
465 }
466
467 static void
468 mark_scc (MonoGCBridgeSCC *scc, int value)
469 {
470         int i;
471         for (i = 0; i < scc->num_objs; ++i) {
472                 if (!test_scc (scc, i)) {
473                         int status = value;
474                         mono_field_set_value (scc->objs [i], mono_bridge_test_field, &status);
475                 }
476         }
477 }
478
479 static void
480 bridge_test_cross_reference2 (int num_sccs, MonoGCBridgeSCC **sccs, int num_xrefs, MonoGCBridgeXRef *xrefs)
481 {
482         int i;
483         gboolean modified;
484
485         if (!mono_bridge_test_field) {
486                 mono_bridge_test_field = mono_class_get_field_from_name (mono_object_get_class (sccs[0]->objs [0]), "__test");
487                 g_assert (mono_bridge_test_field);
488         }
489
490         /*We mark all objects in a scc with live objects as reachable by scc*/
491         for (i = 0; i < num_sccs; ++i) {
492                 int j;
493                 gboolean live = FALSE;
494                 for (j = 0; j < sccs [i]->num_objs; ++j) {
495                         if (test_scc (sccs [i], j)) {
496                                 live = TRUE;
497                                 break;
498                         }
499                 }
500                 if (!live)
501                         continue;
502                 for (j = 0; j < sccs [i]->num_objs; ++j) {
503                         if (!test_scc (sccs [i], j)) {
504                                 int status = BRIDGE_SAME_SCC;
505                                 mono_field_set_value (sccs [i]->objs [j], mono_bridge_test_field, &status);
506                         }
507                 }
508         }
509
510         /*Now we mark the transitive closure of reachable objects from the xrefs*/
511         modified = TRUE;
512         while (modified) {
513                 modified = FALSE;
514                 /* Mark all objects that are brought to life due to xrefs*/
515                 for (i = 0; i < num_xrefs; ++i) {
516                         MonoGCBridgeXRef ref = xrefs [i];
517                         if (test_scc (sccs [ref.src_scc_index], 0) && !test_scc (sccs [ref.dst_scc_index], 0)) {
518                                 modified = TRUE;
519                                 mark_scc (sccs [ref.dst_scc_index], BRIDGE_XREF);
520                         }
521                 }
522         }
523
524         /* keep everything in memory, all we want to do is test persistence */
525         for (i = 0; i < num_sccs; ++i)
526                 sccs [i]->is_alive = TRUE;
527 }
528
529 static void
530 register_test_bridge_callbacks (const char *bridge_class_name)
531 {
532         MonoGCBridgeCallbacks callbacks;
533         callbacks.bridge_version = SGEN_BRIDGE_VERSION;
534         callbacks.bridge_class_kind = bridge_test_bridge_class_kind;
535         callbacks.is_bridge_object = bridge_test_is_bridge_object;
536         callbacks.cross_references = bridge_class_name[0] == '2' ? bridge_test_cross_reference2 : bridge_test_cross_reference;
537         mono_gc_register_bridge_callbacks (&callbacks);
538         bridge_class = bridge_class_name + (bridge_class_name[0] == '2' ? 1 : 0);
539 }
540
541 gboolean
542 sgen_bridge_handle_gc_debug (const char *opt)
543 {
544         if (g_str_has_prefix (opt, "bridge=")) {
545                 opt = strchr (opt, '=') + 1;
546                 register_test_bridge_callbacks (g_strdup (opt));
547         } else if (!strcmp (opt, "enable-bridge-accounting")) {
548                 bridge_processor.enable_accounting ();
549         } else if (g_str_has_prefix (opt, "bridge-dump=")) {
550                 char *prefix = strchr (opt, '=') + 1;
551                 set_dump_prefix (prefix);
552         } else if (g_str_has_prefix (opt, "bridge-compare-to=")) {
553                 const char *name = strchr (opt, '=') + 1;
554                 if (init_bridge_processor (&compare_to_bridge_processor, name)) {
555                         if (compare_to_bridge_processor.reset_data == bridge_processor.reset_data) {
556                                 g_warning ("Cannot compare bridge implementation to itself - ignoring.");
557                                 memset (&compare_to_bridge_processor, 0, sizeof (SgenBridgeProcessor));
558                         }
559                 } else {
560                         g_warning ("Invalid bridge implementation to compare against - ignoring.");
561                 }
562         } else {
563                 return FALSE;
564         }
565         return TRUE;
566 }
567
568 void
569 sgen_bridge_print_gc_debug_usage (void)
570 {
571         fprintf (stderr, "  bridge=<class-name>\n");
572         fprintf (stderr, "  enable-bridge-accounting\n");
573         fprintf (stderr, "  bridge-dump=<filename-prefix>\n");
574         fprintf (stderr, "  bridge-compare-to=<implementation>\n");
575 }
576
577 #endif