2 * sgen-cardtable.c: Card table implementation for sgen
5 * Rodrigo Kumpera (rkumpera@novell.com)
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
12 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
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"
29 //#define CARDTABLE_STATS
34 #ifdef HAVE_SYS_MMAN_H
37 #include <sys/types.h>
39 guint8
*sgen_cardtable
;
41 static gboolean need_mod_union
;
43 #ifdef HEAVY_STATISTICS
45 guint64 scanned_cards
;
46 guint64 scanned_objects
;
47 guint64 remarked_cards
;
48 static guint64 large_objects
;
49 static guint64 bloby_objects
;
51 static guint64 major_card_scan_time
;
52 static guint64 los_card_scan_time
;
54 static guint64 last_major_scan_time
;
55 static guint64 last_los_scan_time
;
57 static void sgen_card_tables_collect_stats (gboolean begin
);
60 sgen_card_table_number_of_cards_in_range (mword address
, mword size
)
62 mword end
= address
+ MAX (1, size
) - 1;
63 return (end
>> CARD_BITS
) - (address
>> CARD_BITS
) + 1;
67 sgen_card_table_wbarrier_set_field (GCObject
*obj
, gpointer field_ptr
, GCObject
* value
)
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
);
76 sgen_card_table_wbarrier_arrayref_copy (gpointer dest_ptr
, gpointer src_ptr
, int count
)
78 gpointer
*dest
= (gpointer
*)dest_ptr
;
79 gpointer
*src
= (gpointer
*)src_ptr
;
81 /*overlapping that required backward copying*/
82 if (src
< dest
&& (src
+ count
) > dest
) {
83 gpointer
*start
= dest
;
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
);
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
);
107 sgen_card_table_wbarrier_value_copy (gpointer dest
, gpointer src
, int count
, size_t element_size
)
109 size_t size
= count
* element_size
;
112 ENTER_CRITICAL_REGION
;
114 mono_gc_memmove_atomic (dest
, src
, size
);
115 sgen_card_table_mark_range ((mword
)dest
, size
);
117 EXIT_CRITICAL_REGION
;
121 sgen_card_table_wbarrier_object_copy (GCObject
* obj
, GCObject
*src
)
123 size_t size
= sgen_client_par_object_get_size (SGEN_LOAD_VTABLE_UNCHECKED (obj
), obj
);
126 ENTER_CRITICAL_REGION
;
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
);
132 EXIT_CRITICAL_REGION
;
136 sgen_card_table_wbarrier_generic_nostore (gpointer ptr
)
138 sgen_card_table_mark_address ((mword
)ptr
);
141 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
143 guint8
*sgen_shadow_cardtable
;
145 #define SGEN_CARDTABLE_END (sgen_cardtable + CARD_COUNT_IN_BYTES)
148 sgen_card_table_region_begin_scanning (mword start
, mword size
)
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
))
155 start
+= CARD_SIZE_IN_BYTES
;
163 sgen_card_table_region_begin_scanning (mword start
, mword size
)
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
);
169 /*XXX this can be improved to work on words and have a branchless body */
170 while (card
!= end
) {
177 memset (sgen_card_table_get_card_address (start
), 0, size
>> CARD_BITS
);
184 /*FIXME this assumes that major blocks are multiple of 4K which is pretty reasonable */
186 sgen_card_table_get_card_data (guint8
*data_dest
, mword address
, mword cards
)
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
);
193 for (; dest
< end
; ++dest
, ++start
) {
198 #ifndef SGEN_HAVE_OVERLAPPING_CARDS
207 sgen_card_table_align_pointer (void *ptr
)
209 return (void*)((mword
)ptr
& ~(CARD_SIZE_IN_BYTES
- 1));
213 sgen_card_table_mark_range (mword address
, mword size
)
215 mword num_cards
= sgen_card_table_number_of_cards_in_range (address
, size
);
216 guint8
*start
= sgen_card_table_get_card_address (address
);
218 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
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.
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
);
232 memset (start
, 1, num_cards
);
236 sgen_card_table_is_range_marked (guint8
*cards
, mword address
, mword size
)
238 guint8
*end
= cards
+ sgen_card_table_number_of_cards_in_range (address
, size
);
240 /*This is safe since this function is only called by code that only passes continuous card blocks*/
241 while (cards
!= end
) {
250 sgen_card_table_record_pointer (gpointer address
)
252 *sgen_card_table_get_card_address ((mword
)address
) = 1;
256 sgen_card_table_find_address (char *addr
)
258 return sgen_card_table_address_is_marked ((mword
)addr
);
262 sgen_card_table_find_address_with_cards (char *cards_start
, guint8
*cards
, char *addr
)
264 cards_start
= (char *)sgen_card_table_align_pointer (cards_start
);
265 return cards
[(addr
- cards_start
) >> CARD_BITS
];
269 update_mod_union (guint8
*dest
, guint8
*start_card
, size_t num_cards
)
272 /* Marking from another thread can happen while we mark here */
273 for (i
= 0; i
< num_cards
; ++i
) {
280 sgen_card_table_alloc_mod_union (char *obj
, mword obj_size
)
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
);
289 sgen_card_table_free_mod_union (guint8
*mod_union
, char *obj
, mword obj_size
)
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
);
296 sgen_card_table_update_mod_union_from_cards (guint8
*dest
, guint8
*start_card
, size_t num_cards
)
298 SGEN_ASSERT (0, dest
, "Why don't we have a mod union?");
299 update_mod_union (dest
, start_card
, num_cards
);
303 sgen_card_table_update_mod_union (guint8
*dest
, char *obj
, mword obj_size
, size_t *out_num_cards
)
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;
311 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
314 rest
= num_cards
= sgen_card_table_number_of_cards_in_range ((mword
) obj
, obj_size
);
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
);
321 start_card
= sgen_cardtable
;
325 num_cards
= end_card
- start_card
;
328 sgen_card_table_update_mod_union_from_cards (dest
, start_card
, num_cards
);
331 *out_num_cards
= num_cards
;
334 /* Preclean cards and saves the cards that need to be scanned afterwards in cards_preclean */
336 sgen_card_table_preclean_mod_union (guint8
*cards
, guint8
*cards_preclean
, size_t num_cards
)
340 memcpy (cards_preclean
, cards
, num_cards
);
341 for (i
= 0; i
< num_cards
; i
++) {
342 if (cards_preclean
[i
]) {
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.
354 mono_memory_barrier ();
357 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
360 move_cards_to_shadow_table (mword start
, mword size
)
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
);
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
;
372 memcpy (to
, from
, first_chunk
);
373 memcpy (sgen_shadow_cardtable
, sgen_cardtable
, second_chunk
);
375 memcpy (to
, from
, bytes
);
380 clear_cards (mword start
, mword size
)
382 guint8
*addr
= sgen_card_table_get_card_address (start
);
383 size_t bytes
= sgen_card_table_number_of_cards_in_range (start
, size
);
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
;
390 memset (addr
, 0, first_chunk
);
391 memset (sgen_cardtable
, 0, bytes
- first_chunk
);
393 memset (addr
, 0, bytes
);
401 clear_cards (mword start
, mword size
)
403 memset (sgen_card_table_get_card_address (start
), 0, sgen_card_table_number_of_cards_in_range (start
, size
));
410 sgen_card_table_clear_cards (void)
412 /*XXX we could do this in 2 ways. using mincore or iterating over all sections/los objects */
413 sgen_major_collector_iterate_block_ranges (clear_cards
);
414 sgen_los_iterate_live_block_ranges (clear_cards
);
418 sgen_card_table_finish_minor_collection (void)
420 sgen_card_tables_collect_stats (FALSE
);
424 sgen_card_table_scan_remsets (ScanCopyContext ctx
)
426 SGEN_TV_DECLARE (atv
);
427 SGEN_TV_DECLARE (btv
);
429 sgen_card_tables_collect_stats (TRUE
);
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.*/
434 sgen_major_collector_iterate_block_ranges (move_cards_to_shadow_table
);
435 sgen_los_iterate_live_block_ranges (move_cards_to_shadow_table
);
438 sgen_card_table_clear_cards ();
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
;
452 sgen_get_card_table_configuration (int *shift_bits
, gpointer
*mask
)
454 #ifndef MANAGED_WBARRIER
460 *shift_bits
= CARD_BITS
;
461 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
462 *mask
= (gpointer
)CARD_MASK
;
467 return sgen_cardtable
;
473 sgen_card_table_dump_obj_card (GCObject
*object
, size_t size
, void *dummy
)
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
);
478 printf ("--obj %p %d cards [%p %p]--", object
, size
, start
, end
);
479 for (; start
< end
; ++start
) {
481 printf ("\n\t[%p] ", start
);
482 printf ("%x ", *start
);
492 sgen_cardtable_scan_object (GCObject
*obj
, mword block_obj_size
, guint8
*cards
, ScanCopyContext ctx
)
494 HEAVY_STAT (++large_objects
);
496 if (sgen_client_cardtable_scan_object (obj
, block_obj_size
, cards
, ctx
))
499 HEAVY_STAT (++bloby_objects
);
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
);
507 binary_protocol_card_scan (obj
, sgen_safe_object_get_size (obj
));
510 #ifdef CARDTABLE_STATS
513 int total
, marked
, remarked
, gc_marked
;
516 static card_stats major_stats
, los_stats
;
517 static card_stats
*cur_stats
;
520 count_marked_cards (mword start
, mword size
)
522 mword end
= start
+ size
;
523 while (start
<= end
) {
524 guint8 card
= *sgen_card_table_get_card_address (start
);
529 ++cur_stats
->gc_marked
;
530 start
+= CARD_SIZE_IN_BYTES
;
535 count_remarked_cards (mword start
, mword size
)
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;
543 start
+= CARD_SIZE_IN_BYTES
;
550 sgen_card_tables_collect_stats (gboolean begin
)
552 #ifdef CARDTABLE_STATS
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
);
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
);
574 sgen_card_table_init (SgenRememberedSet
*remset
)
576 sgen_cardtable
= (guint8
*)sgen_alloc_os_memory (CARD_COUNT_IN_BYTES
, (SgenAllocFlags
)(SGEN_ALLOC_INTERNAL
| SGEN_ALLOC_ACTIVATE
), "card table", MONO_MEM_ACCOUNT_SGEN_CARD_TABLE
);
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", MONO_MEM_ACCOUNT_SGEN_SHADOW_CARD_TABLE
);
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
);
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
);
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
);
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
;
602 remset
->scan_remsets
= sgen_card_table_scan_remsets
;
604 remset
->finish_minor_collection
= sgen_card_table_finish_minor_collection
;
605 remset
->clear_cards
= sgen_card_table_clear_cards
;
607 remset
->find_address
= sgen_card_table_find_address
;
608 remset
->find_address_with_cards
= sgen_card_table_find_address_with_cards
;
610 need_mod_union
= sgen_get_major_collector ()->is_concurrent
;
613 #endif /*HAVE_SGEN_GC*/