mono/metadata/sgen-cardtable.c

   1 /*
   2  * sgen-cardtable.c: Card table implementation for sgen
   3  *
   4  * Author:
   5  *      Rodrigo Kumpera (rkumpera@novell.com)
   6  *
   7  * SGen is licensed under the terms of the MIT X11 license
   8  *
   9  * Copyright 2001-2003 Ximian, Inc
  10  * Copyright 2003-2010 Novell, Inc.
  11  *
  12  * Permission is hereby granted, free of charge, to any person obtaining
  13  * a copy of this software and associated documentation files (the
  14  * "Software"), to deal in the Software without restriction, including
  15  * without limitation the rights to use, copy, modify, merge, publish,
  16  * distribute, sublicense, and/or sell copies of the Software, and to
  17  * permit persons to whom the Software is furnished to do so, subject to
  18  * the following conditions:
  19  *
  20  * The above copyright notice and this permission notice shall be
  21  * included in all copies or substantial portions of the Software.
  22  *
  23  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  24  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  25  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  26  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  27  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  28  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  29  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  30  */
  31
  32 #ifdef SGEN_HAVE_CARDTABLE
  33
  34 //#define CARDTABLE_STATS
  35
  36 #include <unistd.h>
  37 #include <sys/mman.h>
  38 #include <sys/types.h>
  39
  40 guint8 *sgen_cardtable;
  41
  42 /*WARNING: This function returns the number of cards regardless of overflow in case of overlapping cards.*/
  43 static mword
  44 cards_in_range (mword address, mword size)
  45 {
  46         mword end = address + MAX (1, size) - 1;
  47         return (end >> CARD_BITS) - (address >> CARD_BITS) + 1;
  48 }
  49
  50 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
  51
  52 guint8 *sgen_shadow_cardtable;
  53
  54 #define SGEN_SHADOW_CARDTABLE_END (sgen_shadow_cardtable + CARD_COUNT_IN_BYTES)
  55 #define SGEN_CARDTABLE_END (sgen_cardtable + CARD_COUNT_IN_BYTES)
  56
  57 static gboolean
  58 sgen_card_table_region_begin_scanning (mword start, mword end)
  59 {
  60         /*XXX this can be improved to work on words and have a single loop induction var */
  61         while (start <= end) {
  62                 if (sgen_card_table_card_begin_scanning (start))
  63                         return TRUE;
  64                 start += CARD_SIZE_IN_BYTES;
  65         }
  66         return FALSE;
  67 }
  68
  69 #else
  70
  71 static gboolean
  72 sgen_card_table_region_begin_scanning (mword start, mword size)
  73 {
  74         gboolean res = FALSE;
  75         guint8 *card = sgen_card_table_get_card_address (start);
  76         guint8 *end = card + cards_in_range (start, size);
  77
  78         /*XXX this can be improved to work on words and have a branchless body */
  79         while (card != end) {
  80                 if (*card++) {
  81                         res = TRUE;
  82                         break;
  83                 }
  84         }
  85
  86         memset (sgen_card_table_get_card_address (start), 0, size >> CARD_BITS);
  87
  88         return res;
  89 }
  90
  91 #endif
  92
  93 /*FIXME this assumes that major blocks are multiple of 4K which is pretty reasonable */
  94 gboolean
  95 sgen_card_table_get_card_data (guint8 *data_dest, mword address, mword cards)
  96 {
  97         mword *start = (mword*)sgen_card_table_get_card_scan_address (address);
  98         mword *dest = (mword*)data_dest;
  99         mword *end = (mword*)(data_dest + cards);
 100         mword mask = 0;
 101
 102         for (; dest < end; ++dest, ++start) {
 103                 mword v = *start;
 104                 *dest = v;
 105                 mask |= v;
 106
 107 #ifndef SGEN_HAVE_OVERLAPPING_CARDS
 108                 *start = 0;
 109 #endif
 110         }
 111
 112         return mask;
 113 }
 114
 115 static gboolean
 116 sgen_card_table_address_is_marked (mword address)
 117 {
 118         return *sgen_card_table_get_card_address (address) != 0;
 119 }
 120
 121 void
 122 sgen_card_table_mark_address (mword address)
 123 {
 124         *sgen_card_table_get_card_address (address) = 1;
 125 }
 126
 127 void*
 128 sgen_card_table_align_pointer (void *ptr)
 129 {
 130         return (void*)((mword)ptr & ~(CARD_SIZE_IN_BYTES - 1));
 131 }
 132
 133 void
 134 sgen_card_table_mark_range (mword address, mword size)
 135 {
 136         mword end = address + size;
 137         do {
 138                 sgen_card_table_mark_address (address);
 139                 address += CARD_SIZE_IN_BYTES;
 140         } while (address < end);
 141 }
 142
 143 static gboolean
 144 sgen_card_table_is_range_marked (guint8 *cards, mword address, mword size)
 145 {
 146         guint8 *end = cards + cards_in_range (address, size);
 147
 148         /*This is safe since this function is only called by code that only passes continuous card blocks*/
 149         while (cards != end) {
 150                 if (*cards++)
 151                         return TRUE;
 152         }
 153         return FALSE;
 154
 155 }
 156
 157 static void
 158 card_table_init (void)
 159 {
 160         sgen_cardtable = mono_sgen_alloc_os_memory (CARD_COUNT_IN_BYTES, TRUE);
 161
 162 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 163         sgen_shadow_cardtable = mono_sgen_alloc_os_memory (CARD_COUNT_IN_BYTES, TRUE);
 164 #endif
 165 }
 166
 167
 168 void los_scan_card_table (GrayQueue *queue);
 169 void los_iterate_live_block_ranges (sgen_cardtable_block_callback callback);
 170
 171
 172
 173 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 174
 175 static void
 176 move_cards_to_shadow_table (mword start, mword size)
 177 {
 178         guint8 *from = sgen_card_table_get_card_address (start);
 179         guint8 *to = sgen_card_table_get_shadow_card_address (start);
 180         size_t bytes = cards_in_range (start, size);
 181
 182         if (to + bytes > SGEN_SHADOW_CARDTABLE_END) {
 183                 size_t first_chunk = SGEN_SHADOW_CARDTABLE_END - to;
 184                 size_t second_chunk = MIN (CARD_COUNT_IN_BYTES, bytes) - first_chunk;
 185
 186                 memcpy (to, from, first_chunk);
 187                 memcpy (sgen_shadow_cardtable, sgen_cardtable, second_chunk);
 188         } else {
 189                 memcpy (to, from, bytes);
 190         }
 191 }
 192
 193 static void
 194 clear_cards (mword start, mword size)
 195 {
 196         guint8 *addr = sgen_card_table_get_card_address (start);
 197         size_t bytes = cards_in_range (start, size);
 198
 199         if (addr + bytes > SGEN_CARDTABLE_END) {
 200                 size_t first_chunk = SGEN_CARDTABLE_END - addr;
 201
 202                 memset (addr, 0, first_chunk);
 203                 memset (sgen_cardtable, 0, bytes - first_chunk);
 204         } else {
 205                 memset (addr, 0, bytes);
 206         }
 207 }
 208
 209
 210 #else
 211
 212 static void
 213 clear_cards (mword start, mword size)
 214 {
 215         memset (sgen_card_table_get_card_address (start), 0, cards_in_range (start, size));
 216 }
 217
 218
 219 #endif
 220
 221 static void
 222 card_table_clear (void)
 223 {
 224         /*XXX we could do this in 2 ways. using mincore or iterating over all sections/los objects */
 225         if (use_cardtable) {
 226                 major_collector.iterate_live_block_ranges (clear_cards);
 227                 los_iterate_live_block_ranges (clear_cards);
 228         }
 229 }
 230 static void
 231 scan_from_card_tables (void *start_nursery, void *end_nursery, GrayQueue *queue)
 232 {
 233         if (use_cardtable) {
 234 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 235         /*FIXME we should have a bit on each block/los object telling if the object have marked cards.*/
 236         /*First we copy*/
 237         major_collector.iterate_live_block_ranges (move_cards_to_shadow_table);
 238         los_iterate_live_block_ranges (move_cards_to_shadow_table);
 239
 240         /*Then we clear*/
 241         card_table_clear ();
 242 #endif
 243                 major_collector.scan_card_table (queue);
 244                 los_scan_card_table (queue);
 245         }
 246 }
 247
 248 guint8*
 249 mono_gc_get_card_table (int *shift_bits, gpointer *mask)
 250 {
 251         if (!use_cardtable)
 252                 return NULL;
 253
 254         g_assert (sgen_cardtable);
 255         *shift_bits = CARD_BITS;
 256 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 257         *mask = (gpointer)CARD_MASK;
 258 #else
 259         *mask = NULL;
 260 #endif
 261
 262         return sgen_cardtable;
 263 }
 264
 265 #if 0
 266 static void
 267 collect_faulted_cards (void)
 268 {
 269 #define CARD_PAGES (CARD_COUNT_IN_BYTES / 4096)
 270         int i, count = 0;
 271         unsigned char faulted [CARD_PAGES] = { 0 };
 272         mincore (sgen_cardtable, CARD_COUNT_IN_BYTES, faulted);
 273
 274         for (i = 0; i < CARD_PAGES; ++i) {
 275                 if (faulted [i])
 276                         ++count;
 277         }
 278
 279         printf ("TOTAL card pages %d faulted %d\n", CARD_PAGES, count);
 280 }
 281 #endif
 282
 283 void
 284 sgen_cardtable_scan_object (char *obj, mword obj_size, guint8 *cards, SgenGrayQueue *queue)
 285 {
 286         MonoVTable *vt = (MonoVTable*)LOAD_VTABLE (obj);
 287         MonoClass *klass = vt->klass;
 288
 289         if (!klass->has_references)
 290                 return;
 291
 292         if (vt->rank) {
 293                 guint8 *card_data, *card_base;
 294                 guint8 *card_data_end;
 295                 char *obj_start = sgen_card_table_align_pointer (obj);
 296                 char *obj_end = obj + obj_size;
 297                 size_t card_count;
 298                 int extra_idx = 0;
 299
 300                 MonoArray *arr = (MonoArray*)obj;
 301                 mword desc = (mword)klass->element_class->gc_descr;
 302                 int elem_size = mono_array_element_size (klass);
 303
 304 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 305                 guint8 *overflow_scan_end = NULL;
 306 #endif
 307
 308                 if (cards)
 309                         card_data = cards;
 310                 else
 311                         card_data = sgen_card_table_get_card_scan_address ((mword)obj);
 312
 313                 card_base = card_data;
 314                 card_count = cards_in_range ((mword)obj, obj_size);
 315                 card_data_end = card_data + card_count;
 316
 317
 318 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 319                 /*Check for overflow and if so, setup to scan in two steps*/
 320                 if (!cards && card_data_end >= SGEN_SHADOW_CARDTABLE_END) {
 321                         overflow_scan_end = sgen_shadow_cardtable + (card_data_end - SGEN_SHADOW_CARDTABLE_END);
 322                         card_data_end = SGEN_SHADOW_CARDTABLE_END;
 323                 }
 324
 325 LOOP_HEAD:
 326 #endif
 327                 /*FIXME use card skipping code*/
 328                 for (; card_data < card_data_end; ++card_data) {
 329                         int index;
 330                         int idx = (card_data - card_base) + extra_idx;
 331                         char *start = (char*)(obj_start + idx * CARD_SIZE_IN_BYTES);
 332                         char *card_end = start + CARD_SIZE_IN_BYTES;
 333                         char *elem;
 334
 335                         if (!*card_data)
 336                                 continue;
 337
 338                         if (!cards)
 339                                 sgen_card_table_prepare_card_for_scanning (card_data);
 340
 341                         card_end = MIN (card_end, obj_end);
 342
 343                         if (start <= (char*)arr->vector)
 344                                 index = 0;
 345                         else
 346                                 index = ARRAY_OBJ_INDEX (start, obj, elem_size);
 347
 348                         elem = (char*)mono_array_addr_with_size ((MonoArray*)obj, elem_size, index);
 349                         if (klass->element_class->valuetype) {
 350                                 for (; elem < card_end; elem += elem_size)
 351                                         major_collector.minor_scan_vtype (elem, desc, nursery_start, nursery_next, queue);
 352                         } else {
 353                                 for (; elem < card_end; elem += SIZEOF_VOID_P) {
 354                                         gpointer new, old = *(gpointer*)elem;
 355                                         /*XXX it might be faster to do a nursery check here instead as it avoid a call*/
 356                                         if (old) {
 357                                                 major_collector.copy_object ((void**)elem, queue);
 358                                                 new = *(gpointer*)elem;
 359                                                 if (G_UNLIKELY (ptr_in_nursery (new)))
 360                                                         mono_sgen_add_to_global_remset (elem);
 361                                         }
 362                                 }
 363                         }
 364                 }
 365
 366 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 367                 if (overflow_scan_end) {
 368                         extra_idx = card_data - card_base;
 369                         card_base = card_data = sgen_shadow_cardtable;
 370                         card_data_end = overflow_scan_end;
 371                         overflow_scan_end = NULL;
 372                         goto LOOP_HEAD;
 373                 }
 374 #endif
 375
 376         } else {
 377                 if (cards) {
 378                         if (sgen_card_table_is_range_marked (cards, (mword)obj, obj_size))
 379                                 major_collector.minor_scan_object (obj, queue);
 380                 } else if (sgen_card_table_region_begin_scanning ((mword)obj, obj_size)) {
 381                         major_collector.minor_scan_object (obj, queue);
 382                 }
 383         }
 384 }
 385
 386 #ifdef CARDTABLE_STATS
 387
 388 static int total_cards, marked_cards, remarked_cards;
 389
 390 static void
 391 count_marked_cards (mword start, mword size)
 392 {
 393         mword end = start + size;
 394         while (start <= end) {
 395                 ++total_cards;
 396                 if (sgen_card_table_address_is_marked (start))
 397                         ++marked_cards;
 398                 start += CARD_SIZE_IN_BYTES;
 399         }
 400 }
 401
 402 static void
 403 count_remarked_cards (mword start, mword size)
 404 {
 405         mword end = start + size;
 406         while (start <= end) {
 407                 if (sgen_card_table_address_is_marked (start))
 408                         ++remarked_cards;
 409                 start += CARD_SIZE_IN_BYTES;
 410         }
 411 }
 412
 413 #endif
 414
 415 static void
 416 card_tables_collect_stats (gboolean begin)
 417 {
 418 #ifdef CARDTABLE_STATS
 419         if (begin) {
 420                 total_cards = marked_cards = remarked_cards = 0;
 421                 major_collector.iterate_live_block_ranges (count_marked_cards);
 422                 los_iterate_live_block_ranges (count_marked_cards);
 423         } else {
 424                 major_collector.iterate_live_block_ranges (count_marked_cards);
 425                 los_iterate_live_block_ranges (count_remarked_cards);
 426                 printf ("cards total %d marked %d remarked %d\n", total_cards, marked_cards, remarked_cards);
 427         }
 428 #endif
 429 }
 430
 431 #else
 432
 433 void
 434 sgen_card_table_mark_address (mword address)
 435 {
 436         g_assert_not_reached ();
 437 }
 438
 439 void
 440 sgen_card_table_mark_range (mword address, mword size)
 441 {
 442         g_assert_not_reached ();
 443 }
 444
 445 #define sgen_card_table_address_is_marked(p)    FALSE
 446 #define scan_from_card_tables(start,end,queue)
 447 #define card_table_clear()
 448 #define card_table_init()
 449 #define card_tables_collect_stats(begin)
 450
 451 guint8*
 452 mono_gc_get_card_table (int *shift_bits, gpointer *mask)
 453 {
 454         return NULL;
 455 }
 456
 457 #endif