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 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 168
 169 static void
 170 move_cards_to_shadow_table (mword start, mword size)
 171 {
 172         guint8 *from = sgen_card_table_get_card_address (start);
 173         guint8 *to = sgen_card_table_get_shadow_card_address (start);
 174         size_t bytes = cards_in_range (start, size);
 175
 176         if (to + bytes > SGEN_SHADOW_CARDTABLE_END) {
 177                 size_t first_chunk = SGEN_SHADOW_CARDTABLE_END - to;
 178                 size_t second_chunk = MIN (CARD_COUNT_IN_BYTES, bytes) - first_chunk;
 179
 180                 memcpy (to, from, first_chunk);
 181                 memcpy (sgen_shadow_cardtable, sgen_cardtable, second_chunk);
 182         } else {
 183                 memcpy (to, from, bytes);
 184         }
 185 }
 186
 187 static void
 188 clear_cards (mword start, mword size)
 189 {
 190         guint8 *addr = sgen_card_table_get_card_address (start);
 191         size_t bytes = cards_in_range (start, size);
 192
 193         if (addr + bytes > SGEN_CARDTABLE_END) {
 194                 size_t first_chunk = SGEN_CARDTABLE_END - addr;
 195
 196                 memset (addr, 0, first_chunk);
 197                 memset (sgen_cardtable, 0, bytes - first_chunk);
 198         } else {
 199                 memset (addr, 0, bytes);
 200         }
 201 }
 202
 203
 204 #else
 205
 206 static void
 207 clear_cards (mword start, mword size)
 208 {
 209         memset (sgen_card_table_get_card_address (start), 0, cards_in_range (start, size));
 210 }
 211
 212
 213 #endif
 214
 215 static void
 216 card_table_clear (void)
 217 {
 218         /*XXX we could do this in 2 ways. using mincore or iterating over all sections/los objects */
 219         if (use_cardtable) {
 220                 major_collector.iterate_live_block_ranges (clear_cards);
 221                 mono_sgen_los_iterate_live_block_ranges (clear_cards);
 222         }
 223 }
 224 static void
 225 scan_from_card_tables (void *start_nursery, void *end_nursery, GrayQueue *queue)
 226 {
 227         if (use_cardtable) {
 228 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 229         /*FIXME we should have a bit on each block/los object telling if the object have marked cards.*/
 230         /*First we copy*/
 231         major_collector.iterate_live_block_ranges (move_cards_to_shadow_table);
 232         mono_sgen_los_iterate_live_block_ranges (move_cards_to_shadow_table);
 233
 234         /*Then we clear*/
 235         card_table_clear ();
 236 #endif
 237                 major_collector.scan_card_table (queue);
 238                 mono_sgen_los_scan_card_table (queue);
 239         }
 240 }
 241
 242 guint8*
 243 mono_gc_get_card_table (int *shift_bits, gpointer *mask)
 244 {
 245         if (!use_cardtable)
 246                 return NULL;
 247
 248         g_assert (sgen_cardtable);
 249         *shift_bits = CARD_BITS;
 250 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 251         *mask = (gpointer)CARD_MASK;
 252 #else
 253         *mask = NULL;
 254 #endif
 255
 256         return sgen_cardtable;
 257 }
 258
 259 #if 0
 260 static void
 261 collect_faulted_cards (void)
 262 {
 263 #define CARD_PAGES (CARD_COUNT_IN_BYTES / 4096)
 264         int i, count = 0;
 265         unsigned char faulted [CARD_PAGES] = { 0 };
 266         mincore (sgen_cardtable, CARD_COUNT_IN_BYTES, faulted);
 267
 268         for (i = 0; i < CARD_PAGES; ++i) {
 269                 if (faulted [i])
 270                         ++count;
 271         }
 272
 273         printf ("TOTAL card pages %d faulted %d\n", CARD_PAGES, count);
 274 }
 275 #endif
 276
 277 void
 278 sgen_cardtable_scan_object (char *obj, mword obj_size, guint8 *cards, SgenGrayQueue *queue)
 279 {
 280         MonoVTable *vt = (MonoVTable*)LOAD_VTABLE (obj);
 281         MonoClass *klass = vt->klass;
 282
 283         if (!klass->has_references)
 284                 return;
 285
 286         if (vt->rank) {
 287                 guint8 *card_data, *card_base;
 288                 guint8 *card_data_end;
 289                 char *obj_start = sgen_card_table_align_pointer (obj);
 290                 char *obj_end = obj + obj_size;
 291                 size_t card_count;
 292                 int extra_idx = 0;
 293
 294                 MonoArray *arr = (MonoArray*)obj;
 295                 mword desc = (mword)klass->element_class->gc_descr;
 296                 int elem_size = mono_array_element_size (klass);
 297
 298 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 299                 guint8 *overflow_scan_end = NULL;
 300 #endif
 301
 302                 if (cards)
 303                         card_data = cards;
 304                 else
 305                         card_data = sgen_card_table_get_card_scan_address ((mword)obj);
 306
 307                 card_base = card_data;
 308                 card_count = cards_in_range ((mword)obj, obj_size);
 309                 card_data_end = card_data + card_count;
 310
 311
 312 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 313                 /*Check for overflow and if so, setup to scan in two steps*/
 314                 if (!cards && card_data_end >= SGEN_SHADOW_CARDTABLE_END) {
 315                         overflow_scan_end = sgen_shadow_cardtable + (card_data_end - SGEN_SHADOW_CARDTABLE_END);
 316                         card_data_end = SGEN_SHADOW_CARDTABLE_END;
 317                 }
 318
 319 LOOP_HEAD:
 320 #endif
 321                 /*FIXME use card skipping code*/
 322                 for (; card_data < card_data_end; ++card_data) {
 323                         int index;
 324                         int idx = (card_data - card_base) + extra_idx;
 325                         char *start = (char*)(obj_start + idx * CARD_SIZE_IN_BYTES);
 326                         char *card_end = start + CARD_SIZE_IN_BYTES;
 327                         char *elem;
 328
 329                         if (!*card_data)
 330                                 continue;
 331
 332                         if (!cards)
 333                                 sgen_card_table_prepare_card_for_scanning (card_data);
 334
 335                         card_end = MIN (card_end, obj_end);
 336
 337                         if (start <= (char*)arr->vector)
 338                                 index = 0;
 339                         else
 340                                 index = ARRAY_OBJ_INDEX (start, obj, elem_size);
 341
 342                         elem = (char*)mono_array_addr_with_size ((MonoArray*)obj, elem_size, index);
 343                         if (klass->element_class->valuetype) {
 344                                 for (; elem < card_end; elem += elem_size)
 345                                         major_collector.minor_scan_vtype (elem, desc, nursery_start, nursery_next, queue);
 346                         } else {
 347                                 for (; elem < card_end; elem += SIZEOF_VOID_P) {
 348                                         gpointer new, old = *(gpointer*)elem;
 349                                         /*XXX it might be faster to do a nursery check here instead as it avoid a call*/
 350                                         if (old) {
 351                                                 major_collector.copy_object ((void**)elem, queue);
 352                                                 new = *(gpointer*)elem;
 353                                                 if (G_UNLIKELY (ptr_in_nursery (new)))
 354                                                         mono_sgen_add_to_global_remset (elem);
 355                                         }
 356                                 }
 357                         }
 358                 }
 359
 360 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 361                 if (overflow_scan_end) {
 362                         extra_idx = card_data - card_base;
 363                         card_base = card_data = sgen_shadow_cardtable;
 364                         card_data_end = overflow_scan_end;
 365                         overflow_scan_end = NULL;
 366                         goto LOOP_HEAD;
 367                 }
 368 #endif
 369
 370         } else {
 371                 if (cards) {
 372                         if (sgen_card_table_is_range_marked (cards, (mword)obj, obj_size))
 373                                 major_collector.minor_scan_object (obj, queue);
 374                 } else if (sgen_card_table_region_begin_scanning ((mword)obj, obj_size)) {
 375                         major_collector.minor_scan_object (obj, queue);
 376                 }
 377         }
 378 }
 379
 380 #ifdef CARDTABLE_STATS
 381
 382 static int total_cards, marked_cards, remarked_cards;
 383
 384 static void
 385 count_marked_cards (mword start, mword size)
 386 {
 387         mword end = start + size;
 388         while (start <= end) {
 389                 ++total_cards;
 390                 if (sgen_card_table_address_is_marked (start))
 391                         ++marked_cards;
 392                 start += CARD_SIZE_IN_BYTES;
 393         }
 394 }
 395
 396 static void
 397 count_remarked_cards (mword start, mword size)
 398 {
 399         mword end = start + size;
 400         while (start <= end) {
 401                 if (sgen_card_table_address_is_marked (start))
 402                         ++remarked_cards;
 403                 start += CARD_SIZE_IN_BYTES;
 404         }
 405 }
 406
 407 #endif
 408
 409 static void
 410 card_tables_collect_stats (gboolean begin)
 411 {
 412 #ifdef CARDTABLE_STATS
 413         if (begin) {
 414                 total_cards = marked_cards = remarked_cards = 0;
 415                 major_collector.iterate_live_block_ranges (count_marked_cards);
 416                 los_iterate_live_block_ranges (count_marked_cards);
 417         } else {
 418                 major_collector.iterate_live_block_ranges (count_marked_cards);
 419                 los_iterate_live_block_ranges (count_remarked_cards);
 420                 printf ("cards total %d marked %d remarked %d\n", total_cards, marked_cards, remarked_cards);
 421         }
 422 #endif
 423 }
 424
 425 #else
 426
 427 void
 428 sgen_card_table_mark_address (mword address)
 429 {
 430         g_assert_not_reached ();
 431 }
 432
 433 void
 434 sgen_card_table_mark_range (mword address, mword size)
 435 {
 436         g_assert_not_reached ();
 437 }
 438
 439 #define sgen_card_table_address_is_marked(p)    FALSE
 440 #define scan_from_card_tables(start,end,queue)
 441 #define card_table_clear()
 442 #define card_table_init()
 443 #define card_tables_collect_stats(begin)
 444
 445 guint8*
 446 mono_gc_get_card_table (int *shift_bits, gpointer *mask)
 447 {
 448         return NULL;
 449 }
 450
 451 #endif