3 * Card table implementation for sgen
6 * Rodrigo Kumpera (rkumpera@novell.com)
8 * Copyright 2001-2003 Ximian, Inc
9 * Copyright 2003-2010 Novell, Inc.
10 * Copyright 2011 Xamarin Inc (http://www.xamarin.com)
11 * Copyright (C) 2012 Xamarin Inc
13 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
21 #include "mono/sgen/sgen-gc.h"
22 #include "mono/sgen/sgen-cardtable.h"
23 #include "mono/sgen/sgen-memory-governor.h"
24 #include "mono/sgen/sgen-protocol.h"
25 #include "mono/sgen/sgen-layout-stats.h"
26 #include "mono/sgen/sgen-client.h"
27 #include "mono/sgen/gc-internal-agnostic.h"
28 #include "mono/utils/mono-memory-model.h"
30 //#define CARDTABLE_STATS
35 #ifdef HAVE_SYS_MMAN_H
38 #include <sys/types.h>
40 guint8
*sgen_cardtable
;
42 static gboolean need_mod_union
;
44 #ifdef HEAVY_STATISTICS
46 guint64 scanned_cards
;
47 guint64 scanned_objects
;
48 guint64 remarked_cards
;
49 static guint64 large_objects
;
50 static guint64 bloby_objects
;
54 sgen_card_table_number_of_cards_in_range (mword address
, mword size
)
56 mword end
= address
+ MAX (1, size
) - 1;
57 return (end
>> CARD_BITS
) - (address
>> CARD_BITS
) + 1;
61 sgen_card_table_wbarrier_set_field (GCObject
*obj
, gpointer field_ptr
, GCObject
* value
)
63 *(void**)field_ptr
= value
;
64 if (need_mod_union
|| sgen_ptr_in_nursery (value
))
65 sgen_card_table_mark_address ((mword
)field_ptr
);
66 sgen_dummy_use (value
);
70 sgen_card_table_wbarrier_arrayref_copy (gpointer dest_ptr
, gpointer src_ptr
, int count
)
72 gpointer
*dest
= (gpointer
*)dest_ptr
;
73 gpointer
*src
= (gpointer
*)src_ptr
;
75 /*overlapping that required backward copying*/
76 if (src
< dest
&& (src
+ count
) > dest
) {
77 gpointer
*start
= dest
;
81 for (; dest
>= start
; --src
, --dest
) {
82 gpointer value
= *src
;
83 SGEN_UPDATE_REFERENCE_ALLOW_NULL (dest
, value
);
84 if (need_mod_union
|| sgen_ptr_in_nursery (value
))
85 sgen_card_table_mark_address ((mword
)dest
);
86 sgen_dummy_use (value
);
89 gpointer
*end
= dest
+ count
;
90 for (; dest
< end
; ++src
, ++dest
) {
91 gpointer value
= *src
;
92 SGEN_UPDATE_REFERENCE_ALLOW_NULL (dest
, value
);
93 if (need_mod_union
|| sgen_ptr_in_nursery (value
))
94 sgen_card_table_mark_address ((mword
)dest
);
95 sgen_dummy_use (value
);
101 sgen_card_table_wbarrier_value_copy (gpointer dest
, gpointer src
, int count
, size_t element_size
)
103 size_t size
= count
* element_size
;
106 ENTER_CRITICAL_REGION
;
108 mono_gc_memmove_atomic (dest
, src
, size
);
109 sgen_card_table_mark_range ((mword
)dest
, size
);
111 EXIT_CRITICAL_REGION
;
115 sgen_card_table_wbarrier_object_copy (GCObject
* obj
, GCObject
*src
)
117 size_t size
= sgen_client_par_object_get_size (SGEN_LOAD_VTABLE_UNCHECKED (obj
), obj
);
120 ENTER_CRITICAL_REGION
;
122 mono_gc_memmove_aligned ((char*)obj
+ SGEN_CLIENT_OBJECT_HEADER_SIZE
, (char*)src
+ SGEN_CLIENT_OBJECT_HEADER_SIZE
,
123 size
- SGEN_CLIENT_OBJECT_HEADER_SIZE
);
124 sgen_card_table_mark_range ((mword
)obj
, size
);
126 EXIT_CRITICAL_REGION
;
130 sgen_card_table_wbarrier_generic_nostore (gpointer ptr
)
132 sgen_card_table_mark_address ((mword
)ptr
);
136 sgen_card_table_wbarrier_range_copy (gpointer _dest
, gpointer _src
, int size
)
138 GCObject
**dest
= (GCObject
**)_dest
;
139 GCObject
**src
= (GCObject
**)_src
;
141 size_t nursery_bits
= sgen_nursery_bits
;
142 char *start
= sgen_nursery_start
;
143 G_GNUC_UNUSED
char *end
= sgen_nursery_end
;
146 * It's cardtable theory time!
147 * Our cardtable scanning code supports marking any card that an object/valuetype belongs to.
148 * This function is supposed to be used to copy a range that fully belongs to a single type.
149 * It must not be used, for example, to copy 2 adjacent VTs in an array.
151 volatile guint8
*card_address
= (volatile guint8
*)sgen_card_table_get_card_address ((mword
)dest
);
153 GCObject
*value
= *src
;
155 if (SGEN_PTR_IN_NURSERY (value
, nursery_bits
, start
, end
) || sgen_concurrent_collection_in_progress
) {
157 sgen_dummy_use (value
);
161 size
-= SIZEOF_VOID_P
;
165 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
167 guint8
*sgen_shadow_cardtable
;
169 #define SGEN_CARDTABLE_END (sgen_cardtable + CARD_COUNT_IN_BYTES)
172 sgen_card_table_region_begin_scanning (mword start
, mword size
)
174 mword end
= start
+ size
;
175 /*XXX this can be improved to work on words and have a single loop induction var */
176 while (start
< end
) {
177 if (sgen_card_table_card_begin_scanning (start
))
179 start
+= CARD_SIZE_IN_BYTES
;
187 sgen_card_table_region_begin_scanning (mword start
, mword size
)
189 gboolean res
= FALSE
;
190 guint8
*card
= sgen_card_table_get_card_address (start
);
191 guint8
*end
= card
+ sgen_card_table_number_of_cards_in_range (start
, size
);
193 /*XXX this can be improved to work on words and have a branchless body */
194 while (card
!= end
) {
201 memset (sgen_card_table_get_card_address (start
), 0, size
>> CARD_BITS
);
208 /*FIXME this assumes that major blocks are multiple of 4K which is pretty reasonable */
210 sgen_card_table_get_card_data (guint8
*data_dest
, mword address
, mword cards
)
212 mword
*start
= (mword
*)sgen_card_table_get_card_scan_address (address
);
213 mword
*dest
= (mword
*)data_dest
;
214 mword
*end
= (mword
*)(data_dest
+ cards
);
217 for (; dest
< end
; ++dest
, ++start
) {
222 #ifndef SGEN_HAVE_OVERLAPPING_CARDS
231 sgen_card_table_align_pointer (void *ptr
)
233 return (void*)((mword
)ptr
& ~(CARD_SIZE_IN_BYTES
- 1));
237 sgen_card_table_mark_range (mword address
, mword size
)
239 mword num_cards
= sgen_card_table_number_of_cards_in_range (address
, size
);
240 guint8
*start
= sgen_card_table_get_card_address (address
);
242 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
244 * FIXME: There's a theoretical bug here, namely that the card table is allocated so
245 * far toward the end of the address space that start + num_cards overflows.
247 guint8
*end
= start
+ num_cards
;
248 SGEN_ASSERT (0, num_cards
<= CARD_COUNT_IN_BYTES
, "How did we get an object larger than the card table?");
249 if (end
> SGEN_CARDTABLE_END
) {
250 memset (start
, 1, SGEN_CARDTABLE_END
- start
);
251 memset (sgen_cardtable
, 1, end
- SGEN_CARDTABLE_END
);
256 memset (start
, 1, num_cards
);
260 sgen_card_table_is_range_marked (guint8
*cards
, mword address
, mword size
)
262 guint8
*end
= cards
+ sgen_card_table_number_of_cards_in_range (address
, size
);
264 /*This is safe since this function is only called by code that only passes continuous card blocks*/
265 while (cards
!= end
) {
274 sgen_card_table_record_pointer (gpointer address
)
276 *sgen_card_table_get_card_address ((mword
)address
) = 1;
280 sgen_card_table_find_address (char *addr
)
282 return sgen_card_table_address_is_marked ((mword
)addr
);
286 sgen_card_table_find_address_with_cards (char *cards_start
, guint8
*cards
, char *addr
)
288 cards_start
= (char *)sgen_card_table_align_pointer (cards_start
);
289 return cards
[(addr
- cards_start
) >> CARD_BITS
];
293 update_mod_union (guint8
*dest
, guint8
*start_card
, size_t num_cards
)
296 /* Marking from another thread can happen while we mark here */
297 for (i
= 0; i
< num_cards
; ++i
) {
304 sgen_card_table_alloc_mod_union (char *obj
, mword obj_size
)
306 size_t num_cards
= sgen_card_table_number_of_cards_in_range ((mword
) obj
, obj_size
);
307 guint8
*mod_union
= (guint8
*)sgen_alloc_internal_dynamic (num_cards
, INTERNAL_MEM_CARDTABLE_MOD_UNION
, TRUE
);
308 memset (mod_union
, 0, num_cards
);
313 sgen_card_table_free_mod_union (guint8
*mod_union
, char *obj
, mword obj_size
)
315 size_t num_cards
= sgen_card_table_number_of_cards_in_range ((mword
) obj
, obj_size
);
316 sgen_free_internal_dynamic (mod_union
, num_cards
, INTERNAL_MEM_CARDTABLE_MOD_UNION
);
320 sgen_card_table_update_mod_union_from_cards (guint8
*dest
, guint8
*start_card
, size_t num_cards
)
322 SGEN_ASSERT (0, dest
, "Why don't we have a mod union?");
323 update_mod_union (dest
, start_card
, num_cards
);
327 sgen_card_table_update_mod_union (guint8
*dest
, char *obj
, mword obj_size
, size_t *out_num_cards
)
329 guint8
*start_card
= sgen_card_table_get_card_address ((mword
)obj
);
330 #ifndef SGEN_HAVE_OVERLAPPING_CARDS
331 guint8
*end_card
= sgen_card_table_get_card_address ((mword
)obj
+ obj_size
- 1) + 1;
335 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
338 rest
= num_cards
= sgen_card_table_number_of_cards_in_range ((mword
) obj
, obj_size
);
340 while (start_card
+ rest
> SGEN_CARDTABLE_END
) {
341 size_t count
= SGEN_CARDTABLE_END
- start_card
;
342 sgen_card_table_update_mod_union_from_cards (dest
, start_card
, count
);
345 start_card
= sgen_cardtable
;
349 num_cards
= end_card
- start_card
;
352 sgen_card_table_update_mod_union_from_cards (dest
, start_card
, num_cards
);
355 *out_num_cards
= num_cards
;
358 /* Preclean cards and saves the cards that need to be scanned afterwards in cards_preclean */
360 sgen_card_table_preclean_mod_union (guint8
*cards
, guint8
*cards_preclean
, size_t num_cards
)
364 memcpy (cards_preclean
, cards
, num_cards
);
365 for (i
= 0; i
< num_cards
; i
++) {
366 if (cards_preclean
[i
]) {
371 * When precleaning we need to make sure the card cleaning
372 * takes place before the object is scanned. If we don't
373 * do this we could finish scanning the object and, before
374 * the cleaning of the card takes place, another thread
375 * could dirty the object, mark the mod_union card only for
376 * us to clean it back, without scanning the object again.
378 mono_memory_barrier ();
381 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
384 move_cards_to_shadow_table (mword start
, mword size
)
386 guint8
*from
= sgen_card_table_get_card_address (start
);
387 guint8
*to
= sgen_card_table_get_shadow_card_address (start
);
388 size_t bytes
= sgen_card_table_number_of_cards_in_range (start
, size
);
390 if (bytes
>= CARD_COUNT_IN_BYTES
) {
391 memcpy (sgen_shadow_cardtable
, sgen_cardtable
, CARD_COUNT_IN_BYTES
);
392 } else if (to
+ bytes
> SGEN_SHADOW_CARDTABLE_END
) {
393 size_t first_chunk
= SGEN_SHADOW_CARDTABLE_END
- to
;
394 size_t second_chunk
= MIN (CARD_COUNT_IN_BYTES
, bytes
) - first_chunk
;
396 memcpy (to
, from
, first_chunk
);
397 memcpy (sgen_shadow_cardtable
, sgen_cardtable
, second_chunk
);
399 memcpy (to
, from
, bytes
);
404 clear_cards (mword start
, mword size
)
406 guint8
*addr
= sgen_card_table_get_card_address (start
);
407 size_t bytes
= sgen_card_table_number_of_cards_in_range (start
, size
);
409 if (bytes
>= CARD_COUNT_IN_BYTES
) {
410 memset (sgen_cardtable
, 0, CARD_COUNT_IN_BYTES
);
411 } else if (addr
+ bytes
> SGEN_CARDTABLE_END
) {
412 size_t first_chunk
= SGEN_CARDTABLE_END
- addr
;
414 memset (addr
, 0, first_chunk
);
415 memset (sgen_cardtable
, 0, bytes
- first_chunk
);
417 memset (addr
, 0, bytes
);
425 clear_cards (mword start
, mword size
)
427 memset (sgen_card_table_get_card_address (start
), 0, sgen_card_table_number_of_cards_in_range (start
, size
));
434 sgen_card_table_clear_cards (void)
436 /*XXX we could do this in 2 ways. using mincore or iterating over all sections/los objects */
437 sgen_major_collector_iterate_block_ranges (clear_cards
);
438 sgen_los_iterate_live_block_ranges (clear_cards
);
439 sgen_wbroots_iterate_live_block_ranges (clear_cards
);
443 sgen_card_table_start_scan_remsets (void)
445 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
446 /*FIXME we should have a bit on each block/los object telling if the object have marked cards.*/
448 sgen_major_collector_iterate_block_ranges (move_cards_to_shadow_table
);
449 sgen_los_iterate_live_block_ranges (move_cards_to_shadow_table
);
450 sgen_wbroots_iterate_live_block_ranges (move_cards_to_shadow_table
);
453 sgen_card_table_clear_cards ();
458 sgen_get_card_table_configuration (int *shift_bits
, gpointer
*mask
)
460 #ifndef MANAGED_WBARRIER
466 *shift_bits
= CARD_BITS
;
467 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
468 *mask
= (gpointer
)CARD_MASK
;
473 return sgen_cardtable
;
479 sgen_card_table_dump_obj_card (GCObject
*object
, size_t size
, void *dummy
)
481 guint8
*start
= sgen_card_table_get_card_scan_address (object
);
482 guint8
*end
= start
+ sgen_card_table_number_of_cards_in_range (object
, size
);
484 printf ("--obj %p %d cards [%p %p]--", object
, size
, start
, end
);
485 for (; start
< end
; ++start
) {
487 printf ("\n\t[%p] ", start
);
488 printf ("%x ", *start
);
501 #define MWORD_MASK (sizeof (mword) - 1)
504 find_card_offset (mword card
)
506 /*XXX Use assembly as this generates some pretty bad code */
507 #if (defined(__i386__) || defined(__arm__)) && defined(__GNUC__)
508 return (__builtin_ffs (card
) - 1) / 8;
509 #elif (defined(__x86_64__) || defined(__aarch64__)) && defined(__GNUC__)
510 return (__builtin_ffsll (card
) - 1) / 8;
511 #elif defined(__s390x__)
512 return (__builtin_ffsll (GUINT64_TO_LE(card
)) - 1) / 8;
515 guint8
*ptr
= (guint8
*) &card
;
516 for (i
= 0; i
< sizeof (mword
); ++i
) {
525 sgen_find_next_card (guint8
*card_data
, guint8
*end
)
527 mword
*cards
, *cards_end
;
530 while ((((mword
)card_data
) & MWORD_MASK
) && card_data
< end
) {
536 if (card_data
== end
)
539 cards
= (mword
*)card_data
;
540 cards_end
= (mword
*)((mword
)end
& ~MWORD_MASK
);
541 while (cards
< cards_end
) {
544 return (guint8
*)cards
+ find_card_offset (card
);
548 card_data
= (guint8
*)cards_end
;
549 while (card_data
< end
) {
559 sgen_cardtable_scan_object (GCObject
*obj
, mword block_obj_size
, guint8
*cards
, ScanCopyContext ctx
)
561 HEAVY_STAT (++large_objects
);
563 if (sgen_client_cardtable_scan_object (obj
, cards
, ctx
))
566 HEAVY_STAT (++bloby_objects
);
568 if (sgen_card_table_is_range_marked (cards
, (mword
)obj
, block_obj_size
))
569 ctx
.ops
->scan_object (obj
, sgen_obj_get_descriptor (obj
), ctx
.queue
);
570 } else if (sgen_card_table_region_begin_scanning ((mword
)obj
, block_obj_size
)) {
571 ctx
.ops
->scan_object (obj
, sgen_obj_get_descriptor (obj
), ctx
.queue
);
574 sgen_binary_protocol_card_scan (obj
, sgen_safe_object_get_size (obj
));
578 sgen_card_table_init (SgenRememberedSet
*remset
)
580 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
);
582 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
583 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
);
586 #ifdef HEAVY_STATISTICS
587 mono_counters_register ("marked cards", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &marked_cards
);
588 mono_counters_register ("scanned cards", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &scanned_cards
);
589 mono_counters_register ("remarked cards", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &remarked_cards
);
591 mono_counters_register ("cardtable scanned objects", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &scanned_objects
);
592 mono_counters_register ("cardtable large objects", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &large_objects
);
593 mono_counters_register ("cardtable bloby objects", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &bloby_objects
);
596 remset
->wbarrier_set_field
= sgen_card_table_wbarrier_set_field
;
597 remset
->wbarrier_arrayref_copy
= sgen_card_table_wbarrier_arrayref_copy
;
598 remset
->wbarrier_value_copy
= sgen_card_table_wbarrier_value_copy
;
599 remset
->wbarrier_object_copy
= sgen_card_table_wbarrier_object_copy
;
600 remset
->wbarrier_generic_nostore
= sgen_card_table_wbarrier_generic_nostore
;
601 remset
->record_pointer
= sgen_card_table_record_pointer
;
603 remset
->start_scan_remsets
= sgen_card_table_start_scan_remsets
;
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
;
609 remset
->wbarrier_range_copy
= sgen_card_table_wbarrier_range_copy
;
611 need_mod_union
= sgen_get_major_collector ()->is_concurrent
;
614 #endif /*HAVE_SGEN_GC*/