First set of licensing changes
[mono.git] / mono / sgen / sgen-cardtable.c
1 /*
2  * sgen-cardtable.c: Card table implementation for sgen
3  *
4  * Author:
5  *      Rodrigo Kumpera (rkumpera@novell.com)
6  *
7  * Copyright 2001-2003 Ximian, Inc
8  * Copyright 2003-2010 Novell, Inc.
9  * Copyright 2011 Xamarin Inc (http://www.xamarin.com)
10  * Copyright (C) 2012 Xamarin Inc
11  *
12  * Licensed under the MIT license. See LICENSE file in the project root for full license information.
13  */
14
15 #include "config.h"
16 #ifdef HAVE_SGEN_GC
17
18 #include <string.h>
19
20 #include "mono/sgen/sgen-gc.h"
21 #include "mono/sgen/sgen-cardtable.h"
22 #include "mono/sgen/sgen-memory-governor.h"
23 #include "mono/sgen/sgen-protocol.h"
24 #include "mono/sgen/sgen-layout-stats.h"
25 #include "mono/sgen/sgen-client.h"
26 #include "mono/sgen/gc-internal-agnostic.h"
27 #include "mono/utils/mono-memory-model.h"
28
29 //#define CARDTABLE_STATS
30
31 #ifdef HAVE_UNISTD_H
32 #include <unistd.h>
33 #endif
34 #ifdef HAVE_SYS_MMAN_H
35 #include <sys/mman.h>
36 #endif
37 #include <sys/types.h>
38
39 guint8 *sgen_cardtable;
40
41 static gboolean need_mod_union;
42
43 #ifdef HEAVY_STATISTICS
44 guint64 marked_cards;
45 guint64 scanned_cards;
46 guint64 scanned_objects;
47 guint64 remarked_cards;
48 static guint64 large_objects;
49 static guint64 bloby_objects;
50 #endif
51 static guint64 major_card_scan_time;
52 static guint64 los_card_scan_time;
53
54 static guint64 last_major_scan_time;
55 static guint64 last_los_scan_time;
56
57 static void sgen_card_tables_collect_stats (gboolean begin);
58
59 mword
60 sgen_card_table_number_of_cards_in_range (mword address, mword size)
61 {
62         mword end = address + MAX (1, size) - 1;
63         return (end >> CARD_BITS) - (address >> CARD_BITS) + 1;
64 }
65
66 static void
67 sgen_card_table_wbarrier_set_field (GCObject *obj, gpointer field_ptr, GCObject* value)
68 {
69         *(void**)field_ptr = value;
70         if (need_mod_union || sgen_ptr_in_nursery (value))
71                 sgen_card_table_mark_address ((mword)field_ptr);
72         sgen_dummy_use (value);
73 }
74
75 static void
76 sgen_card_table_wbarrier_arrayref_copy (gpointer dest_ptr, gpointer src_ptr, int count)
77 {
78         gpointer *dest = (gpointer *)dest_ptr;
79         gpointer *src = (gpointer *)src_ptr;
80
81         /*overlapping that required backward copying*/
82         if (src < dest && (src + count) > dest) {
83                 gpointer *start = dest;
84                 dest += count - 1;
85                 src += count - 1;
86
87                 for (; dest >= start; --src, --dest) {
88                         gpointer value = *src;
89                         SGEN_UPDATE_REFERENCE_ALLOW_NULL (dest, value);
90                         if (need_mod_union || sgen_ptr_in_nursery (value))
91                                 sgen_card_table_mark_address ((mword)dest);
92                         sgen_dummy_use (value);
93                 }
94         } else {
95                 gpointer *end = dest + count;
96                 for (; dest < end; ++src, ++dest) {
97                         gpointer value = *src;
98                         SGEN_UPDATE_REFERENCE_ALLOW_NULL (dest, value);
99                         if (need_mod_union || sgen_ptr_in_nursery (value))
100                                 sgen_card_table_mark_address ((mword)dest);
101                         sgen_dummy_use (value);
102                 }
103         }       
104 }
105
106 static void
107 sgen_card_table_wbarrier_value_copy (gpointer dest, gpointer src, int count, size_t element_size)
108 {
109         size_t size = count * element_size;
110
111         TLAB_ACCESS_INIT;
112         ENTER_CRITICAL_REGION;
113
114         mono_gc_memmove_atomic (dest, src, size);
115         sgen_card_table_mark_range ((mword)dest, size);
116
117         EXIT_CRITICAL_REGION;
118 }
119
120 static void
121 sgen_card_table_wbarrier_object_copy (GCObject* obj, GCObject *src)
122 {
123         size_t size = sgen_client_par_object_get_size (SGEN_LOAD_VTABLE_UNCHECKED (obj), obj);
124
125         TLAB_ACCESS_INIT;
126         ENTER_CRITICAL_REGION;
127
128         mono_gc_memmove_aligned ((char*)obj + SGEN_CLIENT_OBJECT_HEADER_SIZE, (char*)src + SGEN_CLIENT_OBJECT_HEADER_SIZE,
129                         size - SGEN_CLIENT_OBJECT_HEADER_SIZE);
130         sgen_card_table_mark_range ((mword)obj, size);
131
132         EXIT_CRITICAL_REGION;
133 }
134
135 static void
136 sgen_card_table_wbarrier_generic_nostore (gpointer ptr)
137 {
138         sgen_card_table_mark_address ((mword)ptr);      
139 }
140
141 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
142
143 guint8 *sgen_shadow_cardtable;
144
145 #define SGEN_CARDTABLE_END (sgen_cardtable + CARD_COUNT_IN_BYTES)
146
147 static gboolean
148 sgen_card_table_region_begin_scanning (mword start, mword size)
149 {
150         mword end = start + size;
151         /*XXX this can be improved to work on words and have a single loop induction var */
152         while (start < end) {
153                 if (sgen_card_table_card_begin_scanning (start))
154                         return TRUE;
155                 start += CARD_SIZE_IN_BYTES;
156         }
157         return FALSE;
158 }
159
160 #else
161
162 static gboolean
163 sgen_card_table_region_begin_scanning (mword start, mword size)
164 {
165         gboolean res = FALSE;
166         guint8 *card = sgen_card_table_get_card_address (start);
167         guint8 *end = card + sgen_card_table_number_of_cards_in_range (start, size);
168
169         /*XXX this can be improved to work on words and have a branchless body */
170         while (card != end) {
171                 if (*card++) {
172                         res = TRUE;
173                         break;
174                 }
175         }
176
177         memset (sgen_card_table_get_card_address (start), 0, size >> CARD_BITS);
178
179         return res;
180 }
181
182 #endif
183
184 /*FIXME this assumes that major blocks are multiple of 4K which is pretty reasonable */
185 gboolean
186 sgen_card_table_get_card_data (guint8 *data_dest, mword address, mword cards)
187 {
188         mword *start = (mword*)sgen_card_table_get_card_scan_address (address);
189         mword *dest = (mword*)data_dest;
190         mword *end = (mword*)(data_dest + cards);
191         mword mask = 0;
192
193         for (; dest < end; ++dest, ++start) {
194                 mword v = *start;
195                 *dest = v;
196                 mask |= v;
197
198 #ifndef SGEN_HAVE_OVERLAPPING_CARDS
199                 *start = 0;
200 #endif
201         }
202
203         return mask != 0;
204 }
205
206 void*
207 sgen_card_table_align_pointer (void *ptr)
208 {
209         return (void*)((mword)ptr & ~(CARD_SIZE_IN_BYTES - 1));
210 }
211
212 void
213 sgen_card_table_mark_range (mword address, mword size)
214 {
215         mword num_cards = sgen_card_table_number_of_cards_in_range (address, size);
216         guint8 *start = sgen_card_table_get_card_address (address);
217
218 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
219         /*
220          * FIXME: There's a theoretical bug here, namely that the card table is allocated so
221          * far toward the end of the address space that start + num_cards overflows.
222          */
223         guint8 *end = start + num_cards;
224         SGEN_ASSERT (0, num_cards <= CARD_COUNT_IN_BYTES, "How did we get an object larger than the card table?");
225         if (end > SGEN_CARDTABLE_END) {
226                 memset (start, 1, SGEN_CARDTABLE_END - start);
227                 memset (sgen_cardtable, 1, end - SGEN_CARDTABLE_END);
228                 return;
229         }
230 #endif
231
232         memset (start, 1, num_cards);
233 }
234
235 static gboolean
236 sgen_card_table_is_range_marked (guint8 *cards, mword address, mword size)
237 {
238         guint8 *end = cards + sgen_card_table_number_of_cards_in_range (address, size);
239
240         /*This is safe since this function is only called by code that only passes continuous card blocks*/
241         while (cards != end) {
242                 if (*cards++)
243                         return TRUE;
244         }
245         return FALSE;
246
247 }
248
249 static void
250 sgen_card_table_record_pointer (gpointer address)
251 {
252         *sgen_card_table_get_card_address ((mword)address) = 1;
253 }
254
255 static gboolean
256 sgen_card_table_find_address (char *addr)
257 {
258         return sgen_card_table_address_is_marked ((mword)addr);
259 }
260
261 static gboolean
262 sgen_card_table_find_address_with_cards (char *cards_start, guint8 *cards, char *addr)
263 {
264         cards_start = (char *)sgen_card_table_align_pointer (cards_start);
265         return cards [(addr - cards_start) >> CARD_BITS];
266 }
267
268 static void
269 update_mod_union (guint8 *dest, guint8 *start_card, size_t num_cards)
270 {
271         int i;
272         /* Marking from another thread can happen while we mark here */
273         for (i = 0; i < num_cards; ++i) {
274                 if (start_card [i])
275                         dest [i] = 1;
276         }
277 }
278
279 guint8*
280 sgen_card_table_alloc_mod_union (char *obj, mword obj_size)
281 {
282         size_t num_cards = sgen_card_table_number_of_cards_in_range ((mword) obj, obj_size);
283         guint8 *mod_union = (guint8 *)sgen_alloc_internal_dynamic (num_cards, INTERNAL_MEM_CARDTABLE_MOD_UNION, TRUE);
284         memset (mod_union, 0, num_cards);
285         return mod_union;
286 }
287
288 void
289 sgen_card_table_free_mod_union (guint8 *mod_union, char *obj, mword obj_size)
290 {
291         size_t num_cards = sgen_card_table_number_of_cards_in_range ((mword) obj, obj_size);
292         sgen_free_internal_dynamic (mod_union, num_cards, INTERNAL_MEM_CARDTABLE_MOD_UNION);
293 }
294
295 void
296 sgen_card_table_update_mod_union_from_cards (guint8 *dest, guint8 *start_card, size_t num_cards)
297 {
298         SGEN_ASSERT (0, dest, "Why don't we have a mod union?");
299         update_mod_union (dest, start_card, num_cards);
300 }
301
302 void
303 sgen_card_table_update_mod_union (guint8 *dest, char *obj, mword obj_size, size_t *out_num_cards)
304 {
305         guint8 *start_card = sgen_card_table_get_card_address ((mword)obj);
306 #ifndef SGEN_HAVE_OVERLAPPING_CARDS
307         guint8 *end_card = sgen_card_table_get_card_address ((mword)obj + obj_size - 1) + 1;
308 #endif
309         size_t num_cards;
310
311 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
312         size_t rest;
313
314         rest = num_cards = sgen_card_table_number_of_cards_in_range ((mword) obj, obj_size);
315
316         while (start_card + rest > SGEN_CARDTABLE_END) {
317                 size_t count = SGEN_CARDTABLE_END - start_card;
318                 sgen_card_table_update_mod_union_from_cards (dest, start_card, count);
319                 dest += count;
320                 rest -= count;
321                 start_card = sgen_cardtable;
322         }
323         num_cards = rest;
324 #else
325         num_cards = end_card - start_card;
326 #endif
327
328         sgen_card_table_update_mod_union_from_cards (dest, start_card, num_cards);
329
330         if (out_num_cards)
331                 *out_num_cards = num_cards;
332 }
333
334 /* Preclean cards and saves the cards that need to be scanned afterwards in cards_preclean */
335 void
336 sgen_card_table_preclean_mod_union (guint8 *cards, guint8 *cards_preclean, size_t num_cards)
337 {
338         size_t i;
339
340         memcpy (cards_preclean, cards, num_cards);
341         for (i = 0; i < num_cards; i++) {
342                 if (cards_preclean [i]) {
343                         cards [i] = 0;
344                 }
345         }
346         /*
347          * When precleaning we need to make sure the card cleaning
348          * takes place before the object is scanned. If we don't
349          * do this we could finish scanning the object and, before
350          * the cleaning of the card takes place, another thread
351          * could dirty the object, mark the mod_union card only for
352          * us to clean it back, without scanning the object again.
353          */
354         mono_memory_barrier ();
355 }
356
357 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
358
359 static void
360 move_cards_to_shadow_table (mword start, mword size)
361 {
362         guint8 *from = sgen_card_table_get_card_address (start);
363         guint8 *to = sgen_card_table_get_shadow_card_address (start);
364         size_t bytes = sgen_card_table_number_of_cards_in_range (start, size);
365
366         if (bytes >= CARD_COUNT_IN_BYTES) {
367                 memcpy (sgen_shadow_cardtable, sgen_cardtable, CARD_COUNT_IN_BYTES);
368         } else if (to + bytes > SGEN_SHADOW_CARDTABLE_END) {
369                 size_t first_chunk = SGEN_SHADOW_CARDTABLE_END - to;
370                 size_t second_chunk = MIN (CARD_COUNT_IN_BYTES, bytes) - first_chunk;
371
372                 memcpy (to, from, first_chunk);
373                 memcpy (sgen_shadow_cardtable, sgen_cardtable, second_chunk);
374         } else {
375                 memcpy (to, from, bytes);
376         }
377 }
378
379 static void
380 clear_cards (mword start, mword size)
381 {
382         guint8 *addr = sgen_card_table_get_card_address (start);
383         size_t bytes = sgen_card_table_number_of_cards_in_range (start, size);
384
385         if (bytes >= CARD_COUNT_IN_BYTES) {
386                 memset (sgen_cardtable, 0, CARD_COUNT_IN_BYTES);
387         } else if (addr + bytes > SGEN_CARDTABLE_END) {
388                 size_t first_chunk = SGEN_CARDTABLE_END - addr;
389
390                 memset (addr, 0, first_chunk);
391                 memset (sgen_cardtable, 0, bytes - first_chunk);
392         } else {
393                 memset (addr, 0, bytes);
394         }
395 }
396
397
398 #else
399
400 static void
401 clear_cards (mword start, mword size)
402 {
403         memset (sgen_card_table_get_card_address (start), 0, sgen_card_table_number_of_cards_in_range (start, size));
404 }
405
406
407 #endif
408
409 static void
410 sgen_card_table_clear_cards (void)
411 {
412         /*XXX we could do this in 2 ways. using mincore or iterating over all sections/los objects */
413         sgen_major_collector_iterate_live_block_ranges (clear_cards);
414         sgen_los_iterate_live_block_ranges (clear_cards);
415 }
416
417 static void
418 sgen_card_table_finish_minor_collection (void)
419 {
420         sgen_card_tables_collect_stats (FALSE);
421 }
422
423 static void
424 sgen_card_table_scan_remsets (ScanCopyContext ctx)
425 {
426         SGEN_TV_DECLARE (atv);
427         SGEN_TV_DECLARE (btv);
428
429         sgen_card_tables_collect_stats (TRUE);
430
431 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
432         /*FIXME we should have a bit on each block/los object telling if the object have marked cards.*/
433         /*First we copy*/
434         sgen_major_collector_iterate_live_block_ranges (move_cards_to_shadow_table);
435         sgen_los_iterate_live_block_ranges (move_cards_to_shadow_table);
436
437         /*Then we clear*/
438         sgen_card_table_clear_cards ();
439 #endif
440         SGEN_TV_GETTIME (atv);
441         sgen_get_major_collector ()->scan_card_table (CARDTABLE_SCAN_GLOBAL, ctx);
442         SGEN_TV_GETTIME (btv);
443         last_major_scan_time = SGEN_TV_ELAPSED (atv, btv); 
444         major_card_scan_time += last_major_scan_time;
445         sgen_los_scan_card_table (CARDTABLE_SCAN_GLOBAL, ctx);
446         SGEN_TV_GETTIME (atv);
447         last_los_scan_time = SGEN_TV_ELAPSED (btv, atv);
448         los_card_scan_time += last_los_scan_time;
449 }
450
451 guint8*
452 sgen_get_card_table_configuration (int *shift_bits, gpointer *mask)
453 {
454 #ifndef MANAGED_WBARRIER
455         return NULL;
456 #else
457         if (!sgen_cardtable)
458                 return NULL;
459
460         *shift_bits = CARD_BITS;
461 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
462         *mask = (gpointer)CARD_MASK;
463 #else
464         *mask = NULL;
465 #endif
466
467         return sgen_cardtable;
468 #endif
469 }
470
471 #if 0
472 void
473 sgen_card_table_dump_obj_card (GCObject *object, size_t size, void *dummy)
474 {
475         guint8 *start = sgen_card_table_get_card_scan_address (object);
476         guint8 *end = start + sgen_card_table_number_of_cards_in_range (object, size);
477         int cnt = 0;
478         printf ("--obj %p %d cards [%p %p]--", object, size, start, end);
479         for (; start < end; ++start) {
480                 if (cnt == 0)
481                         printf ("\n\t[%p] ", start);
482                 printf ("%x ", *start);
483                 ++cnt;
484                 if (cnt == 8)
485                         cnt = 0;
486         }
487         printf ("\n");
488 }
489 #endif
490
491 void
492 sgen_cardtable_scan_object (GCObject *obj, mword block_obj_size, guint8 *cards, ScanCopyContext ctx)
493 {
494         HEAVY_STAT (++large_objects);
495
496         if (sgen_client_cardtable_scan_object (obj, block_obj_size, cards, ctx))
497                 return;
498
499         HEAVY_STAT (++bloby_objects);
500         if (cards) {
501                 if (sgen_card_table_is_range_marked (cards, (mword)obj, block_obj_size))
502                         ctx.ops->scan_object (obj, sgen_obj_get_descriptor (obj), ctx.queue);
503         } else if (sgen_card_table_region_begin_scanning ((mword)obj, block_obj_size)) {
504                 ctx.ops->scan_object (obj, sgen_obj_get_descriptor (obj), ctx.queue);
505         }
506
507         binary_protocol_card_scan (obj, sgen_safe_object_get_size (obj));
508 }
509
510 #ifdef CARDTABLE_STATS
511
512 typedef struct {
513         int total, marked, remarked, gc_marked; 
514 } card_stats;
515
516 static card_stats major_stats, los_stats;
517 static card_stats *cur_stats;
518
519 static void
520 count_marked_cards (mword start, mword size)
521 {
522         mword end = start + size;
523         while (start <= end) {
524                 guint8 card = *sgen_card_table_get_card_address (start);
525                 ++cur_stats->total;
526                 if (card)
527                         ++cur_stats->marked;
528                 if (card == 2)
529                         ++cur_stats->gc_marked;
530                 start += CARD_SIZE_IN_BYTES;
531         }
532 }
533
534 static void
535 count_remarked_cards (mword start, mword size)
536 {
537         mword end = start + size;
538         while (start <= end) {
539                 if (sgen_card_table_address_is_marked (start)) {
540                         ++cur_stats->remarked;
541                         *sgen_card_table_get_card_address (start) = 2;
542                 }
543                 start += CARD_SIZE_IN_BYTES;
544         }
545 }
546
547 #endif
548
549 static void
550 sgen_card_tables_collect_stats (gboolean begin)
551 {
552 #ifdef CARDTABLE_STATS
553         if (begin) {
554                 memset (&major_stats, 0, sizeof (card_stats));
555                 memset (&los_stats, 0, sizeof (card_stats));
556                 cur_stats = &major_stats;
557                 sgen_major_collector_iterate_live_block_ranges (count_marked_cards);
558                 cur_stats = &los_stats;
559                 sgen_los_iterate_live_block_ranges (count_marked_cards);
560         } else {
561                 cur_stats = &major_stats;
562                 sgen_major_collector_iterate_live_block_ranges (count_remarked_cards);
563                 cur_stats = &los_stats;
564                 sgen_los_iterate_live_block_ranges (count_remarked_cards);
565                 printf ("cards major (t %d m %d g %d r %d)  los (t %d m %d g %d r %d) major_scan %.2fms los_scan %.2fms\n", 
566                         major_stats.total, major_stats.marked, major_stats.gc_marked, major_stats.remarked,
567                         los_stats.total, los_stats.marked, los_stats.gc_marked, los_stats.remarked,
568                         last_major_scan_time / 10000.0f, last_los_scan_time / 10000.0f);
569         }
570 #endif
571 }
572
573 void
574 sgen_card_table_init (SgenRememberedSet *remset)
575 {
576         sgen_cardtable = (guint8 *)sgen_alloc_os_memory (CARD_COUNT_IN_BYTES, (SgenAllocFlags)(SGEN_ALLOC_INTERNAL | SGEN_ALLOC_ACTIVATE), "card table");
577
578 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
579         sgen_shadow_cardtable = (guint8 *)sgen_alloc_os_memory (CARD_COUNT_IN_BYTES, (SgenAllocFlags)(SGEN_ALLOC_INTERNAL | SGEN_ALLOC_ACTIVATE), "shadow card table");
580 #endif
581
582 #ifdef HEAVY_STATISTICS
583         mono_counters_register ("marked cards", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &marked_cards);
584         mono_counters_register ("scanned cards", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &scanned_cards);
585         mono_counters_register ("remarked cards", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &remarked_cards);
586
587         mono_counters_register ("cardtable scanned objects", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &scanned_objects);
588         mono_counters_register ("cardtable large objects", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &large_objects);
589         mono_counters_register ("cardtable bloby objects", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &bloby_objects);
590 #endif
591         mono_counters_register ("cardtable major scan time", MONO_COUNTER_GC | MONO_COUNTER_ULONG | MONO_COUNTER_TIME, &major_card_scan_time);
592         mono_counters_register ("cardtable los scan time", MONO_COUNTER_GC | MONO_COUNTER_ULONG | MONO_COUNTER_TIME, &los_card_scan_time);
593
594
595         remset->wbarrier_set_field = sgen_card_table_wbarrier_set_field;
596         remset->wbarrier_arrayref_copy = sgen_card_table_wbarrier_arrayref_copy;
597         remset->wbarrier_value_copy = sgen_card_table_wbarrier_value_copy;
598         remset->wbarrier_object_copy = sgen_card_table_wbarrier_object_copy;
599         remset->wbarrier_generic_nostore = sgen_card_table_wbarrier_generic_nostore;
600         remset->record_pointer = sgen_card_table_record_pointer;
601
602         remset->scan_remsets = sgen_card_table_scan_remsets;
603
604         remset->finish_minor_collection = sgen_card_table_finish_minor_collection;
605         remset->clear_cards = sgen_card_table_clear_cards;
606
607         remset->find_address = sgen_card_table_find_address;
608         remset->find_address_with_cards = sgen_card_table_find_address_with_cards;
609
610         need_mod_union = sgen_get_major_collector ()->is_concurrent;
611 }
612
613 #endif /*HAVE_SGEN_GC*/