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  *
   7  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
   8  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
   9  *
  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.
  15  *
  16  *
  17  * Copyright 2001-2003 Ximian, Inc
  18  * Copyright 2003-2010 Novell, Inc.
  19  *
  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:
  27  *
  28  * The above copyright notice and this permission notice shall be
  29  * included in all copies or substantial portions of the Software.
  30  *
  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.
  38  */
  39
  40 #include "config.h"
  41
  42 #ifdef HAVE_SGEN_GC
  43
  44 #include <stdlib.h>
  45
  46 #include "sgen-gc.h"
  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"
  53
  54 MonoGCBridgeCallbacks bridge_callbacks;
  55 static SgenBridgeProcessor bridge_processor;
  56 static SgenBridgeProcessor compare_to_bridge_processor;
  57
  58 gboolean bridge_processing_in_progress = FALSE;
  59
  60 void
  61 mono_gc_wait_for_bridge_processing (void)
  62 {
  63         if (!bridge_processing_in_progress)
  64                 return;
  65
  66         mono_trace (G_LOG_LEVEL_INFO, MONO_TRACE_GC, "GC_BRIDGE waiting for bridge processing to finish");
  67
  68         sgen_gc_lock ();
  69         sgen_gc_unlock ();
  70 }
  71
  72
  73 void
  74 mono_gc_register_bridge_callbacks (MonoGCBridgeCallbacks *callbacks)
  75 {
  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);
  78
  79         bridge_callbacks = *callbacks;
  80
  81         if (!bridge_processor.reset_data)
  82                 sgen_old_bridge_init (&bridge_processor);
  83 }
  84
  85 static gboolean
  86 init_bridge_processor (SgenBridgeProcessor *processor, const char *name)
  87 {
  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);
  97         } else {
  98                 return FALSE;
  99         }
 100         return TRUE;
 101 }
 102
 103 void
 104 sgen_set_bridge_implementation (const char *name)
 105 {
 106         if (!init_bridge_processor (&bridge_processor, name))
 107                 g_warning ("Invalid value for bridge implementation, valid values are: 'new' and 'old'.");
 108 }
 109
 110 gboolean
 111 sgen_is_bridge_object (GCObject *gc_obj)
 112 {
 113         MonoObject *obj = (MonoObject*)gc_obj;
 114         if ((obj->vtable->gc_bits & SGEN_GC_BIT_BRIDGE_OBJECT) != SGEN_GC_BIT_BRIDGE_OBJECT)
 115                 return FALSE;
 116         return bridge_callbacks.is_bridge_object (obj);
 117 }
 118
 119 gboolean
 120 sgen_need_bridge_processing (void)
 121 {
 122         return bridge_callbacks.cross_references != NULL;
 123 }
 124
 125 static gboolean
 126 compare_bridge_processors (void)
 127 {
 128         return compare_to_bridge_processor.reset_data != NULL;
 129 }
 130
 131 /* Dispatch wrappers */
 132 void
 133 sgen_bridge_reset_data (void)
 134 {
 135         bridge_processor.reset_data ();
 136         if (compare_bridge_processors ())
 137                 compare_to_bridge_processor.reset_data ();
 138 }
 139
 140 void
 141 sgen_bridge_processing_stw_step (void)
 142 {
 143         /*
 144          * bridge_processing_in_progress must be set with the world
 145          * stopped.  If not there would be race conditions.
 146          */
 147         bridge_processing_in_progress = TRUE;
 148
 149         bridge_processor.processing_stw_step ();
 150         if (compare_bridge_processors ())
 151                 compare_to_bridge_processor.processing_stw_step ();
 152 }
 153
 154 static mono_bool
 155 is_bridge_object_alive (GCObject *obj, void *data)
 156 {
 157         SgenHashTable *table = data;
 158         unsigned char *value = sgen_hash_table_lookup (table, obj);
 159         if (!value)
 160                 return TRUE;
 161         return *value;
 162 }
 163
 164 static void
 165 null_weak_links_to_dead_objects (SgenBridgeProcessor *processor, int generation)
 166 {
 167         int i, j;
 168         int num_sccs = processor->num_sccs;
 169         MonoGCBridgeSCC **api_sccs = processor->api_sccs;
 170         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
 172         for (i = 0; i < num_sccs; ++i) {
 173                 unsigned char alive = api_sccs [i]->is_alive ? 1 : 0;
 174                 for (j = 0; j < api_sccs [i]->num_objs; ++j) {
 175                         /* Build hash table for nulling weak links. */
 176                         sgen_hash_table_replace (&alive_hash, api_sccs [i]->objs [j], &alive, NULL);
 177
 178                         /* Release for finalization those objects we no longer care. */
 179                         if (!api_sccs [i]->is_alive)
 180                                 sgen_mark_bridge_object ((GCObject*)api_sccs [i]->objs [j]);
 181                 }
 182         }
 183
 184         /* Null weak links to dead objects. */
 185         sgen_null_links_with_predicate (GENERATION_NURSERY, is_bridge_object_alive, &alive_hash);
 186         if (generation == GENERATION_OLD)
 187                 sgen_null_links_with_predicate (GENERATION_OLD, is_bridge_object_alive, &alive_hash);
 188
 189         sgen_hash_table_clean (&alive_hash);
 190 }
 191
 192 static void
 193 free_callback_data (SgenBridgeProcessor *processor)
 194 {
 195         int i;
 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;
 200
 201         for (i = 0; i < num_sccs; ++i) {
 202                 sgen_free_internal_dynamic (api_sccs [i],
 203                                 sizeof (MonoGCBridgeSCC) + sizeof (GCObject*) * api_sccs [i]->num_objs,
 204                                 INTERNAL_MEM_BRIDGE_DATA);
 205         }
 206         sgen_free_internal_dynamic (api_sccs, sizeof (MonoGCBridgeSCC*) * num_sccs, INTERNAL_MEM_BRIDGE_DATA);
 207
 208         sgen_free_internal_dynamic (api_xrefs, sizeof (MonoGCBridgeXRef) * num_xrefs, INTERNAL_MEM_BRIDGE_DATA);
 209
 210         processor->num_sccs = 0;
 211         processor->api_sccs = NULL;
 212         processor->num_xrefs = 0;
 213         processor->api_xrefs = NULL;
 214 }
 215
 216 void
 217 sgen_bridge_processing_finish (int generation)
 218 {
 219         bridge_processor.processing_build_callback_data (generation);
 220         if (compare_bridge_processors ())
 221                 compare_to_bridge_processor.processing_build_callback_data (generation);
 222
 223         if (bridge_processor.num_sccs == 0) {
 224                 g_assert (bridge_processor.num_xrefs == 0);
 225                 goto after_callback;
 226         }
 227
 228         bridge_callbacks.cross_references (bridge_processor.num_sccs, bridge_processor.api_sccs,
 229                         bridge_processor.num_xrefs, bridge_processor.api_xrefs);
 230
 231         if (compare_bridge_processors ())
 232                 sgen_compare_bridge_processor_results (&bridge_processor, &compare_to_bridge_processor);
 233
 234         null_weak_links_to_dead_objects (&bridge_processor, generation);
 235
 236         free_callback_data (&bridge_processor);
 237         if (compare_bridge_processors ())
 238                 free_callback_data (&compare_to_bridge_processor);
 239
 240  after_callback:
 241         bridge_processor.processing_after_callback (generation);
 242         if (compare_bridge_processors ())
 243                 compare_to_bridge_processor.processing_after_callback (generation);
 244
 245         bridge_processing_in_progress = FALSE;
 246 }
 247
 248 MonoGCBridgeObjectKind
 249 sgen_bridge_class_kind (MonoClass *class)
 250 {
 251         return bridge_processor.class_kind (class);
 252 }
 253
 254 void
 255 sgen_bridge_register_finalized_object (GCObject *obj)
 256 {
 257         bridge_processor.register_finalized_object (obj);
 258         if (compare_bridge_processors ())
 259                 compare_to_bridge_processor.register_finalized_object (obj);
 260 }
 261
 262 void
 263 sgen_bridge_describe_pointer (GCObject *obj)
 264 {
 265         if (bridge_processor.describe_pointer)
 266                 bridge_processor.describe_pointer (obj);
 267 }
 268
 269 static void
 270 set_dump_prefix (const char *prefix)
 271 {
 272         if (!bridge_processor.set_dump_prefix) {
 273                 fprintf (stderr, "Warning: Bridge implementation does not support dumping - ignoring.\n");
 274                 return;
 275         }
 276
 277         bridge_processor.set_dump_prefix (prefix);
 278 }
 279
 280 /* Test support code */
 281 static const char *bridge_class;
 282
 283 static MonoGCBridgeObjectKind
 284 bridge_test_bridge_class_kind (MonoClass *class)
 285 {
 286         if (!strcmp (bridge_class, class->name))
 287                 return GC_BRIDGE_TRANSPARENT_BRIDGE_CLASS;
 288         return GC_BRIDGE_TRANSPARENT_CLASS;
 289 }
 290
 291 static gboolean
 292 bridge_test_is_bridge_object (MonoObject *object)
 293 {
 294         return TRUE;
 295 }
 296
 297 static void
 298 bridge_test_cross_reference (int num_sccs, MonoGCBridgeSCC **sccs, int num_xrefs, MonoGCBridgeXRef *xrefs)
 299 {
 300         int i;
 301         for (i = 0; i < num_sccs; ++i) {
 302                 int j;
 303         //      g_print ("--- SCC %d\n", i);
 304                 for (j = 0; j < sccs [i]->num_objs; ++j) {
 305         //              g_print ("  %s\n", sgen_safe_name (sccs [i]->objs [j]));
 306                         if (i & 1) /*retain half of the bridged objects */
 307                                 sccs [i]->is_alive = TRUE;
 308                 }
 309         }
 310         for (i = 0; i < num_xrefs; ++i) {
 311                 g_assert (xrefs [i].src_scc_index >= 0 && xrefs [i].src_scc_index < num_sccs);
 312                 g_assert (xrefs [i].dst_scc_index >= 0 && xrefs [i].dst_scc_index < num_sccs);
 313         //      g_print ("%d -> %d\n", xrefs [i].src_scc_index, xrefs [i].dst_scc_index);
 314         }
 315 }
 316
 317 static MonoClassField *mono_bridge_test_field;
 318
 319 enum {
 320         BRIDGE_DEAD,
 321         BRIDGE_ROOT,
 322         BRIDGE_SAME_SCC,
 323         BRIDGE_XREF,
 324 };
 325
 326 static gboolean
 327 test_scc (MonoGCBridgeSCC *scc, int i)
 328 {
 329         int status = BRIDGE_DEAD;
 330         mono_field_get_value (scc->objs [i], mono_bridge_test_field, &status);
 331         return status > 0;
 332 }
 333
 334 static void
 335 mark_scc (MonoGCBridgeSCC *scc, int value)
 336 {
 337         int i;
 338         for (i = 0; i < scc->num_objs; ++i) {
 339                 if (!test_scc (scc, i)) {
 340                         int status = value;
 341                         mono_field_set_value (scc->objs [i], mono_bridge_test_field, &status);
 342                 }
 343         }
 344 }
 345
 346 static void
 347 bridge_test_cross_reference2 (int num_sccs, MonoGCBridgeSCC **sccs, int num_xrefs, MonoGCBridgeXRef *xrefs)
 348 {
 349         int i;
 350         gboolean modified;
 351
 352         if (!mono_bridge_test_field) {
 353                 mono_bridge_test_field = mono_class_get_field_from_name (mono_object_get_class (sccs[0]->objs [0]), "__test");
 354                 g_assert (mono_bridge_test_field);
 355         }
 356
 357         /*We mark all objects in a scc with live objects as reachable by scc*/
 358         for (i = 0; i < num_sccs; ++i) {
 359                 int j;
 360                 gboolean live = FALSE;
 361                 for (j = 0; j < sccs [i]->num_objs; ++j) {
 362                         if (test_scc (sccs [i], j)) {
 363                                 live = TRUE;
 364                                 break;
 365                         }
 366                 }
 367                 if (!live)
 368                         continue;
 369                 for (j = 0; j < sccs [i]->num_objs; ++j) {
 370                         if (!test_scc (sccs [i], j)) {
 371                                 int status = BRIDGE_SAME_SCC;
 372                                 mono_field_set_value (sccs [i]->objs [j], mono_bridge_test_field, &status);
 373                         }
 374                 }
 375         }
 376
 377         /*Now we mark the transitive closure of reachable objects from the xrefs*/
 378         modified = TRUE;
 379         while (modified) {
 380                 modified = FALSE;
 381                 /* Mark all objects that are brought to life due to xrefs*/
 382                 for (i = 0; i < num_xrefs; ++i) {
 383                         MonoGCBridgeXRef ref = xrefs [i];
 384                         if (test_scc (sccs [ref.src_scc_index], 0) && !test_scc (sccs [ref.dst_scc_index], 0)) {
 385                                 modified = TRUE;
 386                                 mark_scc (sccs [ref.dst_scc_index], BRIDGE_XREF);
 387                         }
 388                 }
 389         }
 390
 391         /* keep everything in memory, all we want to do is test persistence */
 392         for (i = 0; i < num_sccs; ++i)
 393                 sccs [i]->is_alive = TRUE;
 394 }
 395
 396 static void
 397 register_test_bridge_callbacks (const char *bridge_class_name)
 398 {
 399         MonoGCBridgeCallbacks callbacks;
 400         callbacks.bridge_version = SGEN_BRIDGE_VERSION;
 401         callbacks.bridge_class_kind = bridge_test_bridge_class_kind;
 402         callbacks.is_bridge_object = bridge_test_is_bridge_object;
 403         callbacks.cross_references = bridge_class_name[0] == '2' ? bridge_test_cross_reference2 : bridge_test_cross_reference;
 404         mono_gc_register_bridge_callbacks (&callbacks);
 405         bridge_class = bridge_class_name + (bridge_class_name[0] == '2' ? 1 : 0);
 406 }
 407
 408 gboolean
 409 sgen_bridge_handle_gc_debug (const char *opt)
 410 {
 411         if (g_str_has_prefix (opt, "bridge=")) {
 412                 opt = strchr (opt, '=') + 1;
 413                 register_test_bridge_callbacks (g_strdup (opt));
 414         } else if (!strcmp (opt, "enable-bridge-accounting")) {
 415                 bridge_processor.enable_accounting ();
 416         } else if (g_str_has_prefix (opt, "bridge-dump=")) {
 417                 char *prefix = strchr (opt, '=') + 1;
 418                 set_dump_prefix (prefix);
 419         } else if (g_str_has_prefix (opt, "bridge-compare-to=")) {
 420                 const char *name = strchr (opt, '=') + 1;
 421                 if (init_bridge_processor (&compare_to_bridge_processor, name)) {
 422                         if (compare_to_bridge_processor.reset_data == bridge_processor.reset_data) {
 423                                 g_warning ("Cannot compare bridge implementation to itself - ignoring.");
 424                                 memset (&compare_to_bridge_processor, 0, sizeof (SgenBridgeProcessor));
 425                         }
 426                 } else {
 427                         g_warning ("Invalid bridge implementation to compare against - ignoring.");
 428                 }
 429         } else {
 430                 return FALSE;
 431         }
 432         return TRUE;
 433 }
 434
 435 void
 436 sgen_bridge_print_gc_debug_usage (void)
 437 {
 438         fprintf (stderr, "  bridge=<class-name>\n");
 439         fprintf (stderr, "  enable-bridge-accounting\n");
 440         fprintf (stderr, "  bridge-dump=<filename-prefix>\n");
 441         fprintf (stderr, "  bridge-compare-to=<implementation>\n");
 442 }
 443
 444 #endif