2010-02-10 Geoff Norton <gnorton@novell.com>
[mono.git] / mono / mini / mini-gc.c
1 /*
2  * mini-gc.c: GC interface for the mono JIT
3  *
4  * Author:
5  *   Zoltan Varga (vargaz@gmail.com)
6  *
7  * Copyright 2009 Novell, Inc (http://www.novell.com)
8  */
9
10 #include "config.h"
11 #include "mini-gc.h"
12
13 #if 0
14 //#ifdef HAVE_SGEN_GC
15
16 #include <mono/metadata/gc-internal.h>
17 #include <mono/utils/mono-counters.h>
18
19 #define ALIGN_TO(val,align) ((((guint64)val) + ((align) - 1)) & ~((align) - 1))
20
21 #if 1
22 #define DEBUG(s) do { s; } while (0)
23 #else
24 #define DEBUG(s)
25 #endif
26
27 #if 1
28 #define DEBUG_GC_MAP(s) do { s; fflush (stdout); } while (0)
29 #else
30 #define DEBUG_GC_MAP(s)
31 #endif
32
33 #define GC_BITS_PER_WORD (sizeof (gsize) * 8)
34
35 /*
36  * Per-thread data kept by this module. This is stored in the GC and passed to us as
37  * parameters, instead of being stored in a TLS variable, since during a collection,
38  * only the collection thread is active.
39  */
40 typedef struct {
41         MonoLMF *lmf;
42         MonoContext ctx;
43         gboolean has_context;
44         MonoJitTlsData *jit_tls;
45 } TlsData;
46
47 typedef enum {
48         /* Stack slot doesn't contain a reference */
49         SLOT_NOREF = 0,
50         /* Stack slot contains a reference */
51         SLOT_REF = 1,
52         /* No info, slot needs to be scanned conservatively */
53         SLOT_PIN = 2
54 } StackSlotType;
55
56 /* 
57  * Contains information needed to mark a stack frame.
58  * FIXME: Optimize the memory usage.
59  */
60 typedef struct {
61         /* The frame pointer register */
62         int frame_reg;
63         /* The offset of the local variable area in the stack frame relative to the frame pointer */
64         int locals_offset;
65         /* The size of the locals area. Can't use nslots as it includes padding */
66         int locals_size;
67         /* The number of stack slots */
68         int nslots;
69         /* 
70          * The gc map itself.
71          */
72         StackSlotType *slots;
73         /* A pair of low pc offset-high pc offset for each SLOT_REF value in gc_refs */
74         guint32 live_ranges [MONO_ZERO_LEN_ARRAY];
75 } GCMap;
76
77 /* Statistics */
78 static guint32 gc_maps_size;
79
80 static gpointer
81 thread_attach_func (void)
82 {
83         return g_new0 (TlsData, 1);
84 }
85
86 static void
87 thread_suspend_func (gpointer user_data, void *sigctx)
88 {
89         TlsData *tls = user_data;
90
91         tls->lmf = mono_get_lmf ();
92         if (sigctx) {
93                 mono_arch_sigctx_to_monoctx (sigctx, &tls->ctx);
94                 tls->has_context = TRUE;
95         } else {
96                 tls->has_context = FALSE;
97         }
98         tls->jit_tls = TlsGetValue (mono_jit_tls_id);
99 }
100
101 static int precise_frame_count [2], precise_frame_limit = -1;
102 static gboolean precise_frame_limit_inited;
103
104 #define DEAD_REF ((gpointer)(gssize)0x2a2a2a2a2a2a2a2aULL)
105
106 static void
107 thread_mark_func (gpointer user_data, guint8 *stack_start, guint8 *stack_end, gboolean precise)
108 {
109         TlsData *tls = user_data;
110         MonoJitInfo *ji, res;
111         MonoContext ctx, new_ctx;
112         MonoLMF *lmf = tls->lmf;
113         guint8 *stack_limit;
114         gboolean last = TRUE, managed;
115         GCMap *map;
116         guint8* fp, *locals_start, *locals_end;
117         int i, pc_offset;
118         int scanned = 0, scanned_precisely, scanned_conservatively;
119
120         if (mono_thread_internal_current () == NULL) {
121                 if (!precise)
122                         mono_gc_conservatively_scan_area (stack_start, stack_end);                      
123                 return;
124         }
125
126         /* Number of bytes scanned based on GC map data */
127         scanned = 0;
128         /* Number of bytes scanned precisely based on GC map data */
129         scanned_precisely = 0;
130         /* Number of bytes scanned conservatively based on GC map data */
131         scanned_conservatively = 0;
132
133         /* FIXME: sgen-gc.c calls this multiple times for each major collection from pin_from_roots */
134
135         /* FIXME: Use real gc descriptors instead of bitmaps */
136
137         /* This is one past the last address which we have scanned */
138         stack_limit = stack_start;
139
140         DEBUG (printf ("*** %s stack marking %p-%p ***\n", precise ? "Precise" : "Conservative", stack_start, stack_end));
141
142         if (!tls->has_context) {
143                 memset (&new_ctx, 0, sizeof (ctx));
144
145                 while (TRUE) {
146                         memcpy (&ctx, &new_ctx, sizeof (ctx));
147
148                         g_assert ((guint64)stack_limit % sizeof (gpointer) == 0);
149
150                         // FIXME: This doesn't work with appdomain transitions
151                         ji = mono_find_jit_info (mono_domain_get (), tls->jit_tls, &res, NULL,
152                                                                          &ctx, &new_ctx, NULL, &lmf, NULL, &managed);
153                         if (ji == (gpointer)-1)
154                                 break;
155
156                         /* The last frame can be in any state so mark conservatively */
157                         if (last) {
158                                 last = FALSE;
159                                 continue;
160                         }
161
162                         /* These frames are returned by mono_find_jit_info () two times */
163                         if (!managed)
164                                 continue;
165
166                         /* Scan the frame of this method */
167
168                         /*
169                          * A frame contains the following:
170                          * - saved registers
171                          * - saved args
172                          * - locals
173                          * - spill area
174                          * - localloc-ed memory
175                          * Currently, only the locals are scanned precisely.
176                          */
177
178                         map = ji->gc_info;
179
180                         if (!map) {
181                                 DEBUG (char *fname = mono_method_full_name (ji->method, TRUE); printf ("Mark(%d): No GC map for %s\n", precise, fname); g_free (fname));
182                                 continue;
183                         }
184
185                         /*
186                          * Debugging aid to control the number of frames scanned precisely
187                          */
188                         if (!precise_frame_limit_inited) {
189                                 if (getenv ("MONO_PRECISE_COUNT"))
190                                         precise_frame_limit = atoi (getenv ("MONO_PRECISE_COUNT"));
191                                 precise_frame_limit_inited = TRUE;
192                         }
193                                 
194                         if (precise_frame_limit != -1) {
195                                 if (precise_frame_count [precise] == precise_frame_limit)
196                                         printf ("LAST PRECISE FRAME: %s\n", mono_method_full_name (ji->method, TRUE));
197                                 if (precise_frame_count [precise] > precise_frame_limit)
198                                         continue;
199                         }
200                         precise_frame_count [precise] ++;
201
202 #ifdef __x86_64__
203                         if (map->frame_reg == AMD64_RSP)
204                                 fp = (guint8*)ctx.rsp;
205                         else if (map->frame_reg == AMD64_RBP)
206                                 fp = (guint8*)ctx.rbp;
207                         else
208                                 g_assert_not_reached ();
209 #else
210                         fp = NULL;
211                         g_assert_not_reached ();
212 #endif
213
214                         locals_start = fp + map->locals_offset;
215                         locals_end = locals_start + map->locals_size;
216
217                         pc_offset = (guint8*)MONO_CONTEXT_GET_IP (&ctx) - (guint8*)ji->code_start;
218                         g_assert (pc_offset >= 0);
219
220                         DEBUG (char *fname = mono_method_full_name (ji->method, TRUE); printf ("Mark(%d): %s+0x%x (%p) limit=%p fp=%p locals=%p-%p (%d)\n", precise, fname, pc_offset, (gpointer)MONO_CONTEXT_GET_IP (&ctx), stack_limit, fp, locals_start, locals_end, (int)(locals_end - locals_start)); g_free (fname));
221
222                         /* 
223                          * FIXME: Add a function to mark using a bitmap, to avoid doing a 
224                          * call for each object.
225                          */
226
227                         scanned += locals_end - locals_start;
228
229                         /* Pinning needs to be done first, then the precise scan later */
230
231                         if (!precise) {
232                                 g_assert (locals_start >= stack_limit);
233
234                                 if (locals_start > stack_limit) {
235                                         /* This scans the previously skipped frames as well */
236                                         DEBUG (printf ("\tscan area %p-%p.\n", stack_limit, locals_start));
237                                         mono_gc_conservatively_scan_area (stack_limit, locals_start);
238                                 }
239
240                                 if (map->slots) {
241                                         guint8 *p;
242
243                                         p = locals_start;
244                                         for (i = 0; i < map->nslots; ++i) {
245                                                 if (map->slots [i] == SLOT_PIN) {
246                                                         DEBUG (printf ("\tscan slot %s0x%x(fp)=%p.\n", (guint8*)p > (guint8*)fp ? "" : "-", ABS ((int)((gssize)p - (gssize)fp)), p));
247                                                         mono_gc_conservatively_scan_area (p, p + sizeof (gpointer));
248                                                         scanned_conservatively += sizeof (gpointer);
249                                                 }
250                                                 p += sizeof (gpointer);
251                                         }
252                                 }
253
254                                 stack_limit = locals_end;
255                         } else {
256                                 if (map->slots) {
257                                         int loffset = 0;
258
259                                         for (i = 0; i < map->nslots; ++i) {
260                                                 if (map->slots [i] == SLOT_REF) {
261                                                         MonoObject **ptr = (MonoObject**)(locals_start + (i * sizeof (gpointer)));
262                                                         MonoObject *obj = *ptr;
263
264                                                         if (pc_offset >= map->live_ranges [loffset] && pc_offset < map->live_ranges [loffset + 1] && obj != DEAD_REF) {
265                                                                 if (obj) {
266                                                                         DEBUG (printf ("\tref %s0x%x(fp)=%p: %p ->", (guint8*)ptr >= (guint8*)fp ? "" : "-", ABS ((int)((gssize)ptr - (gssize)fp)), ptr, obj));
267                                                                         *ptr = mono_gc_scan_object (obj);
268                                                                         DEBUG (printf (" %p.\n", *ptr));
269                                                                 } else {
270                                                                         DEBUG (printf ("\tref %s0x%x(fp)=%p: %p.\n", (guint8*)ptr >= (guint8*)fp ? "" : "-", ABS ((int)((gssize)ptr - (gssize)fp)), ptr, obj));
271                                                                 }
272                                                         } else {
273                                                                 DEBUG (printf ("\tref %s0x%x(fp)=%p: dead (%p)\n", (guint8*)ptr >= (guint8*)fp ? "" : "-", ABS ((int)((gssize)ptr - (gssize)fp)), ptr, obj));
274                                                                 /*
275                                                                  * This serves two purposes:
276                                                                  * - fail fast if the live range is incorrect, and
277                                                                  * the JITted code tries to access this object
278                                                                  * - it avoids problems when a dead slot becomes live
279                                                                  * again due to a backward branch 
280                                                                  * (see test_0_liveness_6).
281                                                                  */
282                                                                 *ptr = DEAD_REF;
283                                                         }
284
285                                                         loffset += 2;
286                                                         scanned_precisely += sizeof (gpointer);
287                                                 } else if (map->slots [i] == SLOT_NOREF) {
288                                                         scanned_precisely += sizeof (gpointer);
289                                                 }
290                                         }
291                                 }
292                         }
293                 }
294
295                 if (stack_limit < stack_end && !precise) {
296                         DEBUG (printf ("\tscan area %p-%p.\n", stack_limit, stack_end));
297                         mono_gc_conservatively_scan_area (stack_limit, stack_end);
298                 }
299         } else {
300                 // FIXME:
301                 if (!precise) {
302                         DEBUG (printf ("\tno context, scan area %p-%p.\n", stack_start, stack_end));
303                         mono_gc_conservatively_scan_area (stack_start, stack_end);
304                 }
305         }
306
307         DEBUG (printf ("Marked %d bytes, p=%d,c=%d out of %d.\n", scanned, scanned_precisely, scanned_conservatively, (int)(stack_end - stack_start)));
308
309         //mono_gc_conservatively_scan_area (stack_start, stack_end);
310 }
311
312 #define set_slot(slots, nslots, pos, val) do {  \
313                 g_assert ((pos) < (nslots));               \
314                 (slots) [(pos)] = (val);                           \
315         } while (0)
316
317 void
318 mini_gc_init_gc_map (MonoCompile *cfg)
319 {
320         if (COMPILE_LLVM (cfg))
321                 return;
322
323         /* See mini_gc_create_gc_map () for comments as to why these are needed */
324
325         /* Extend the live ranges using the liveness information */
326         cfg->compute_precise_live_ranges = TRUE;
327         /* Is this still needed ? */
328         cfg->disable_reuse_ref_stack_slots = TRUE;
329         /* 
330          * Initialize all variables holding refs to null in the initlocals bblock, not just
331          *  variables representing IL locals.
332          */
333         cfg->init_ref_vars = TRUE;
334         /* Prevent these initializations from being optimized away */
335         cfg->disable_initlocals_opt_refs = TRUE;
336 }
337
338 void
339 mini_gc_create_gc_map (MonoCompile *cfg)
340 {
341         GCMap *map;
342         int i, nslots, alloc_size, loffset, min_offset, max_offset;
343         StackSlotType *slots = NULL;
344         gboolean norefs = FALSE;
345         guint32 *live_range_start, *live_range_end;
346
347         /*
348          * Since we currently don't use GC safe points, we need to create GC maps which
349          * are precise at every instruction within a method. We use the live ranges
350          * calculated by the JIT in mono_spill_global_vars () for this. Unfortunately by 
351          * default these are not precise enought for several reasons:
352          * - the current calculation of MonoMethodVar->live_range_start/end is incorrect,
353          * it doesn't take into account loops etc. It needs to use the results of the
354          * liveness analysis pass.
355          * - the current liveness analysis pass is too conservative, ie. the live_in/out
356          * sets computed by it are sometimes include too many variables, for example because
357          * of the bogus links between bblocks. This means the live_in/out sets cannot be
358          * used to reliably compute precise live ranges.
359          * - stack slots are shared, which means the live ranges of stack slots have holes
360          * in them.
361          * - the live ranges of variables used in out-of-line bblocks also have holes in
362          * them.
363          * - the live ranges of variables used for handling stack args also have holes in
364          * them:
365          *   if (A)
366      *     x = <ref>
367          *   else
368          *     x = <ref>
369          *   <use x>
370          * Here x is not live between the first and the second assignment.
371          *
372          * To work around these problems, we set a few cfg flags in mini_init_gc_maps ()
373          * which guarantee that the live range of stack slots have no holes, i.e. they hold
374          * a valid value (or null) during their entire live range.
375          * FIXME: This doesn't completely work yet, see test_0_liveness_6 (), where
376          * a variable becomes dead, then alive again.
377          */
378         //NOT_IMPLEMENTED;
379
380         if (!(cfg->comp_done & MONO_COMP_LIVENESS))
381                 /* Without liveness info, the live ranges are not precise enough */
382                 return;
383
384 #ifdef TARGET_AMD64
385         min_offset = ALIGN_TO (cfg->locals_min_stack_offset, sizeof (gpointer));
386         max_offset = cfg->locals_max_stack_offset;
387 #else
388         /* min/max stack offset needs to be computed in mono_arch_allocate_vars () */
389         NOT_IMPLEMENTED;
390 #endif
391
392         for (i = cfg->locals_start; i < cfg->num_varinfo; i++) {
393                 MonoInst *ins = cfg->varinfo [i];
394                 MonoType *t = ins->inst_vtype;
395
396                 if ((MONO_TYPE_ISSTRUCT (t) && ins->klass->has_references))
397                         break;
398                 if (MONO_TYPE_ISSTRUCT (t))
399                         break;
400                 if (t->byref || t->type == MONO_TYPE_PTR)
401                         break;
402                 if (ins && ins->opcode == OP_REGOFFSET && MONO_TYPE_IS_REFERENCE (ins->inst_vtype))
403                         break;
404         }
405
406         if (i == cfg->num_varinfo)
407                 norefs = TRUE;
408
409         if (cfg->verbose_level > 1)
410                 printf ("GC Map for %s: 0x%x-0x%x\n", mono_method_full_name (cfg->method, TRUE), min_offset, max_offset);
411
412         nslots = (max_offset - min_offset) / sizeof (gpointer);
413         if (!norefs) {
414                 alloc_size = nslots * sizeof (StackSlotType);
415                 slots = mono_domain_alloc0 (cfg->domain, alloc_size);
416                 for (i = 0; i < nslots; ++i)
417                         slots [i] = SLOT_NOREF;
418                 gc_maps_size += alloc_size;
419         }
420         live_range_start = g_new (guint32, nslots);
421         live_range_end = g_new (guint32, nslots);
422         loffset = 0;
423
424         for (i = 0; i < nslots; ++i) {
425                 live_range_start [i] = (guint32)-1;
426                 live_range_end [i] = 0;
427         }
428
429         for (i = cfg->locals_start; i < cfg->num_varinfo; i++) {
430                 MonoInst *ins = cfg->varinfo [i];
431                 MonoType *t = ins->inst_vtype;
432                 MonoMethodVar *vmv;
433                 guint32 pos;
434
435                 if (norefs)
436                         continue;
437
438                 vmv = MONO_VARINFO (cfg, i);
439
440                 if (ins->opcode != OP_REGOFFSET)
441                         continue;
442
443                 if (ins->inst_offset % sizeof (gpointer) != 0)
444                         continue;
445
446                 pos = (ins->inst_offset - min_offset) / sizeof (gpointer);
447
448                 if ((MONO_TYPE_ISSTRUCT (t) && !ins->klass->has_references))
449                         continue;
450
451                 if ((MONO_TYPE_ISSTRUCT (t) && ins->klass->has_references)) {
452                         int numbits, j;
453                         gsize *bitmap;
454                         gboolean pin;
455
456                         if (ins->klass->generic_container || mono_class_is_open_constructed_type (t)) {
457                                 /* FIXME: Generic sharing */
458                                 pin = TRUE;
459                         } else {
460                                 mono_class_compute_gc_descriptor (ins->klass);
461
462                                 bitmap = mono_gc_get_bitmap_for_descr (ins->klass->gc_descr, &numbits);
463
464                                 if (bitmap) {
465                                         for (j = 0; j < numbits; ++j) {
466                                                 if (bitmap [j / GC_BITS_PER_WORD] & ((gsize)1 << (j % GC_BITS_PER_WORD))) {
467                                                         /* The descriptor is for the boxed object */
468                                                         set_slot (slots, nslots, (pos + j - (sizeof (MonoObject) / sizeof (gpointer))), SLOT_REF);
469                                                 }
470                                         }
471                                         g_free (bitmap);
472
473                                         if (cfg->verbose_level > 1)
474                                                 printf ("\tvtype at fp+0x%x: %s -> 0x%x\n", (int)ins->inst_offset, mono_type_full_name (ins->inst_vtype), (int)ins->inst_offset);
475
476                                         // FIXME: These have no live range
477                                         pin = TRUE;
478                                 } else {
479                                         // FIXME:
480                                         pin = TRUE;
481                                 }
482                         }
483
484                         if (ins->backend.is_pinvoke)
485                                 pin = TRUE;
486
487                         if (pin) {
488                                 int size;
489
490                                 if (ins->backend.is_pinvoke)
491                                         size = mono_class_native_size (ins->klass, NULL);
492                                 else
493                                         size = mono_class_value_size (ins->klass, NULL);
494                                 for (j = 0; j < size / sizeof (gpointer); ++j)
495                                         set_slot (slots, nslots, pos + j, SLOT_PIN);
496                         }
497                         continue;
498                 }
499
500                 if (ins->inst_offset < min_offset || ins->inst_offset >= max_offset)
501                         /* Vret addr etc. */
502                         continue;
503
504                 if (t->byref || t->type == MONO_TYPE_PTR || t->type == MONO_TYPE_I || t->type == MONO_TYPE_U) {
505                         set_slot (slots, nslots, pos, SLOT_PIN);
506                         continue;
507                 }
508
509                 if (MONO_TYPE_IS_REFERENCE (ins->inst_vtype)) {
510                         if (vmv && !vmv->live_range_start) {
511                                 set_slot (slots, nslots, pos, SLOT_PIN);
512                                 continue;
513                         }
514
515                         if (ins->flags & (MONO_INST_VOLATILE | MONO_INST_INDIRECT)) {
516                                 set_slot (slots, nslots, pos, SLOT_PIN);
517                                 continue;
518                         }
519
520                         set_slot (slots, nslots, pos, SLOT_REF);
521
522                         /* Stack slots holding refs shouldn't be shared */
523                         g_assert (!live_range_end [pos]);
524                         live_range_start [pos] = vmv->live_range_start;
525                         live_range_end [pos] = vmv->live_range_end;
526
527                         if (cfg->verbose_level > 1)
528                                 printf ("\tref at %s0x%x(fp) (slot=%d): %s [0x%x - 0x%x]\n", ins->inst_offset < 0 ? "-" : "", (ins->inst_offset < 0) ? -(int)ins->inst_offset : (int)ins->inst_offset, pos, mono_type_full_name (ins->inst_vtype), vmv->live_range_start, vmv->live_range_end);
529                 }
530         }
531
532         alloc_size = sizeof (GCMap) + (norefs ? 0 : (nslots - MONO_ZERO_LEN_ARRAY) * sizeof (guint32) * 2);
533         map = mono_domain_alloc0 (cfg->domain, alloc_size);
534         gc_maps_size += alloc_size;
535
536         map->frame_reg = cfg->frame_reg;
537         map->locals_offset = min_offset;
538         map->locals_size = ALIGN_TO (max_offset - min_offset, sizeof (gpointer));
539         map->nslots = nslots;
540         map->slots = slots;
541         loffset = 0;
542         if (!norefs) {
543                 for (i = 0; i < nslots; ++i) {
544                         if (map->slots [i] == SLOT_REF) {
545                                 map->live_ranges [loffset ++] = live_range_start [i];
546                                 map->live_ranges [loffset ++] = live_range_end [i];
547                         }
548                 }
549         }
550
551 #if 1
552         {
553                 static int precise_count;
554
555                 if (map->slots) {
556                         precise_count ++;
557                         if (getenv ("MONO_GCMAP_COUNT")) {
558                                 if (precise_count == atoi (getenv ("MONO_GCMAP_COUNT")))
559                                         printf ("LAST: %s\n", mono_method_full_name (cfg->method, TRUE));
560                                 if (precise_count > atoi (getenv ("MONO_GCMAP_COUNT"))) {
561                                         for (i = 0; i < nslots; ++i)
562                                                 map->slots [i] = SLOT_PIN;
563                                 }
564                         }
565                 }
566         }
567 #endif
568
569         cfg->jit_info->gc_info = map;
570
571         g_free (live_range_start);
572         g_free (live_range_end);
573 }
574
575 void
576 mini_gc_init (void)
577 {
578         MonoGCCallbacks cb;
579
580         memset (&cb, 0, sizeof (cb));
581         cb.thread_attach_func = thread_attach_func;
582         cb.thread_suspend_func = thread_suspend_func;
583         /* Comment this out to disable precise stack marking */
584         cb.thread_mark_func = thread_mark_func;
585         mono_gc_set_gc_callbacks (&cb);
586
587         mono_counters_register ("GC Maps size",
588                                                         MONO_COUNTER_GC | MONO_COUNTER_INT, &gc_maps_size);
589 }
590
591 #else
592
593 void
594 mini_gc_init (void)
595 {
596 }
597
598 void
599 mini_gc_init_gc_map (MonoCompile *cfg)
600 {
601 }
602
603 void
604 mini_gc_create_gc_map (MonoCompile *cfg)
605 {
606 }
607
608 #endif