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
  43 #ifdef HEAVY_STATISTICS
  44 long long marked_cards;
  45 long long scanned_cards;
  46 long long scanned_objects;
  47
  48 static long long los_marked_cards;
  49 static long long large_objects;
  50 static long long bloby_objects;
  51 static long long los_array_cards;
  52 static long long los_array_remsets;
  53
  54 #endif
  55 static long long major_card_scan_time;
  56 static long long los_card_scan_time;
  57
  58 static long long last_major_scan_time;
  59 static long long last_los_scan_time;
  60 /*WARNING: This function returns the number of cards regardless of overflow in case of overlapping cards.*/
  61 static mword
  62 cards_in_range (mword address, mword size)
  63 {
  64         mword end = address + MAX (1, size) - 1;
  65         return (end >> CARD_BITS) - (address >> CARD_BITS) + 1;
  66 }
  67
  68 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
  69
  70 guint8 *sgen_shadow_cardtable;
  71
  72 #define SGEN_SHADOW_CARDTABLE_END (sgen_shadow_cardtable + CARD_COUNT_IN_BYTES)
  73 #define SGEN_CARDTABLE_END (sgen_cardtable + CARD_COUNT_IN_BYTES)
  74
  75 static gboolean
  76 sgen_card_table_region_begin_scanning (mword start, mword end)
  77 {
  78         /*XXX this can be improved to work on words and have a single loop induction var */
  79         while (start <= end) {
  80                 if (sgen_card_table_card_begin_scanning (start))
  81                         return TRUE;
  82                 start += CARD_SIZE_IN_BYTES;
  83         }
  84         return FALSE;
  85 }
  86
  87 #else
  88
  89 static gboolean
  90 sgen_card_table_region_begin_scanning (mword start, mword size)
  91 {
  92         gboolean res = FALSE;
  93         guint8 *card = sgen_card_table_get_card_address (start);
  94         guint8 *end = card + cards_in_range (start, size);
  95
  96         /*XXX this can be improved to work on words and have a branchless body */
  97         while (card != end) {
  98                 if (*card++) {
  99                         res = TRUE;
 100                         break;
 101                 }
 102         }
 103
 104         memset (sgen_card_table_get_card_address (start), 0, size >> CARD_BITS);
 105
 106         return res;
 107 }
 108
 109 #endif
 110
 111 /*FIXME this assumes that major blocks are multiple of 4K which is pretty reasonable */
 112 gboolean
 113 sgen_card_table_get_card_data (guint8 *data_dest, mword address, mword cards)
 114 {
 115         mword *start = (mword*)sgen_card_table_get_card_scan_address (address);
 116         mword *dest = (mword*)data_dest;
 117         mword *end = (mword*)(data_dest + cards);
 118         mword mask = 0;
 119
 120         for (; dest < end; ++dest, ++start) {
 121                 mword v = *start;
 122                 *dest = v;
 123                 mask |= v;
 124
 125 #ifndef SGEN_HAVE_OVERLAPPING_CARDS
 126                 *start = 0;
 127 #endif
 128         }
 129
 130         return mask;
 131 }
 132
 133 static gboolean
 134 sgen_card_table_address_is_marked (mword address)
 135 {
 136         return *sgen_card_table_get_card_address (address) != 0;
 137 }
 138
 139 void
 140 sgen_card_table_mark_address (mword address)
 141 {
 142         *sgen_card_table_get_card_address (address) = 1;
 143 }
 144
 145 void*
 146 sgen_card_table_align_pointer (void *ptr)
 147 {
 148         return (void*)((mword)ptr & ~(CARD_SIZE_IN_BYTES - 1));
 149 }
 150
 151 void
 152 sgen_card_table_mark_range (mword address, mword size)
 153 {
 154         mword end = address + size;
 155         do {
 156                 sgen_card_table_mark_address (address);
 157                 address += CARD_SIZE_IN_BYTES;
 158         } while (address < end);
 159 }
 160
 161 static gboolean
 162 sgen_card_table_is_range_marked (guint8 *cards, mword address, mword size)
 163 {
 164         guint8 *end = cards + cards_in_range (address, size);
 165
 166         /*This is safe since this function is only called by code that only passes continuous card blocks*/
 167         while (cards != end) {
 168                 if (*cards++)
 169                         return TRUE;
 170         }
 171         return FALSE;
 172
 173 }
 174
 175 static void
 176 card_table_init (void)
 177 {
 178         sgen_cardtable = mono_sgen_alloc_os_memory (CARD_COUNT_IN_BYTES, TRUE);
 179
 180 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 181         sgen_shadow_cardtable = mono_sgen_alloc_os_memory (CARD_COUNT_IN_BYTES, TRUE);
 182 #endif
 183
 184 #ifdef HEAVY_STATISTICS
 185         mono_counters_register ("marked cards", MONO_COUNTER_GC | MONO_COUNTER_LONG, &marked_cards);
 186         mono_counters_register ("scanned cards", MONO_COUNTER_GC | MONO_COUNTER_LONG, &scanned_cards);
 187         mono_counters_register ("los marked cards", MONO_COUNTER_GC | MONO_COUNTER_LONG, &los_marked_cards);
 188         mono_counters_register ("los scanned cards", MONO_COUNTER_GC | MONO_COUNTER_LONG, &los_scanned_cards);
 189         mono_counters_register ("los array cards scanned ", MONO_COUNTER_GC | MONO_COUNTER_LONG, &los_array_cards);
 190         mono_counters_register ("los array remsets", MONO_COUNTER_GC | MONO_COUNTER_LONG, &los_array_remsets);
 191         mono_counters_register ("cardtable scanned objects", MONO_COUNTER_GC | MONO_COUNTER_LONG, &scanned_objects);
 192         mono_counters_register ("cardtable large objects", MONO_COUNTER_GC | MONO_COUNTER_LONG, &large_objects);
 193         mono_counters_register ("cardtable bloby objects", MONO_COUNTER_GC | MONO_COUNTER_LONG, &bloby_objects);
 194 #endif
 195         mono_counters_register ("cardtable major scan time", MONO_COUNTER_GC | MONO_COUNTER_LONG, &major_card_scan_time);
 196         mono_counters_register ("cardtable los scan time", MONO_COUNTER_GC | MONO_COUNTER_LONG, &los_card_scan_time);
 197 }
 198
 199 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 200
 201 static void
 202 move_cards_to_shadow_table (mword start, mword size)
 203 {
 204         guint8 *from = sgen_card_table_get_card_address (start);
 205         guint8 *to = sgen_card_table_get_shadow_card_address (start);
 206         size_t bytes = cards_in_range (start, size);
 207
 208         if (to + bytes > SGEN_SHADOW_CARDTABLE_END) {
 209                 size_t first_chunk = SGEN_SHADOW_CARDTABLE_END - to;
 210                 size_t second_chunk = MIN (CARD_COUNT_IN_BYTES, bytes) - first_chunk;
 211
 212                 memcpy (to, from, first_chunk);
 213                 memcpy (sgen_shadow_cardtable, sgen_cardtable, second_chunk);
 214         } else {
 215                 memcpy (to, from, bytes);
 216         }
 217 }
 218
 219 static void
 220 clear_cards (mword start, mword size)
 221 {
 222         guint8 *addr = sgen_card_table_get_card_address (start);
 223         size_t bytes = cards_in_range (start, size);
 224
 225         if (addr + bytes > SGEN_CARDTABLE_END) {
 226                 size_t first_chunk = SGEN_CARDTABLE_END - addr;
 227
 228                 memset (addr, 0, first_chunk);
 229                 memset (sgen_cardtable, 0, bytes - first_chunk);
 230         } else {
 231                 memset (addr, 0, bytes);
 232         }
 233 }
 234
 235
 236 #else
 237
 238 static void
 239 clear_cards (mword start, mword size)
 240 {
 241         memset (sgen_card_table_get_card_address (start), 0, cards_in_range (start, size));
 242 }
 243
 244
 245 #endif
 246
 247 static void
 248 card_table_clear (void)
 249 {
 250         /*XXX we could do this in 2 ways. using mincore or iterating over all sections/los objects */
 251         if (use_cardtable) {
 252                 major_collector.iterate_live_block_ranges (clear_cards);
 253                 mono_sgen_los_iterate_live_block_ranges (clear_cards);
 254         }
 255 }
 256 static void
 257 scan_from_card_tables (void *start_nursery, void *end_nursery, GrayQueue *queue)
 258 {
 259         if (use_cardtable) {
 260                 TV_DECLARE (atv);
 261                 TV_DECLARE (btv);
 262
 263 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 264         /*FIXME we should have a bit on each block/los object telling if the object have marked cards.*/
 265         /*First we copy*/
 266         major_collector.iterate_live_block_ranges (move_cards_to_shadow_table);
 267         mono_sgen_los_iterate_live_block_ranges (move_cards_to_shadow_table);
 268
 269         /*Then we clear*/
 270         card_table_clear ();
 271 #endif
 272                 TV_GETTIME (atv);
 273                 major_collector.scan_card_table (queue);
 274                 TV_GETTIME (btv);
 275                 last_major_scan_time = TV_ELAPSED_MS (atv, btv);
 276                 major_card_scan_time += last_major_scan_time;
 277                 mono_sgen_los_scan_card_table (queue);
 278                 TV_GETTIME (atv);
 279                 last_los_scan_time = TV_ELAPSED_MS (btv, atv);
 280                 los_card_scan_time += last_los_scan_time;
 281         }
 282 }
 283
 284 guint8*
 285 mono_gc_get_card_table (int *shift_bits, gpointer *mask)
 286 {
 287         if (!use_cardtable)
 288                 return NULL;
 289
 290         g_assert (sgen_cardtable);
 291         *shift_bits = CARD_BITS;
 292 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 293         *mask = (gpointer)CARD_MASK;
 294 #else
 295         *mask = NULL;
 296 #endif
 297
 298         return sgen_cardtable;
 299 }
 300
 301 #if 0
 302 static void
 303 collect_faulted_cards (void)
 304 {
 305 #define CARD_PAGES (CARD_COUNT_IN_BYTES / 4096)
 306         int i, count = 0;
 307         unsigned char faulted [CARD_PAGES] = { 0 };
 308         mincore (sgen_cardtable, CARD_COUNT_IN_BYTES, faulted);
 309
 310         for (i = 0; i < CARD_PAGES; ++i) {
 311                 if (faulted [i])
 312                         ++count;
 313         }
 314
 315         printf ("TOTAL card pages %d faulted %d\n", CARD_PAGES, count);
 316 }
 317 #endif
 318
 319 void
 320 sgen_cardtable_scan_object (char *obj, mword obj_size, guint8 *cards, SgenGrayQueue *queue)
 321 {
 322         MonoVTable *vt = (MonoVTable*)LOAD_VTABLE (obj);
 323         MonoClass *klass = vt->klass;
 324
 325         HEAVY_STAT (++large_objects);
 326
 327         if (!SGEN_VTABLE_HAS_REFERENCES (vt))
 328                 return;
 329
 330         if (vt->rank) {
 331                 guint8 *card_data, *card_base;
 332                 guint8 *card_data_end;
 333                 char *obj_start = sgen_card_table_align_pointer (obj);
 334                 char *obj_end = obj + obj_size;
 335                 size_t card_count;
 336                 int extra_idx = 0;
 337
 338                 MonoArray *arr = (MonoArray*)obj;
 339                 mword desc = (mword)klass->element_class->gc_descr;
 340                 int elem_size = mono_array_element_size (klass);
 341
 342 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 343                 guint8 *overflow_scan_end = NULL;
 344 #endif
 345
 346                 if (cards)
 347                         card_data = cards;
 348                 else
 349                         card_data = sgen_card_table_get_card_scan_address ((mword)obj);
 350
 351                 card_base = card_data;
 352                 card_count = cards_in_range ((mword)obj, obj_size);
 353                 card_data_end = card_data + card_count;
 354
 355
 356 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 357                 /*Check for overflow and if so, setup to scan in two steps*/
 358                 if (!cards && card_data_end >= SGEN_SHADOW_CARDTABLE_END) {
 359                         overflow_scan_end = sgen_shadow_cardtable + (card_data_end - SGEN_SHADOW_CARDTABLE_END);
 360                         card_data_end = SGEN_SHADOW_CARDTABLE_END;
 361                 }
 362
 363 LOOP_HEAD:
 364 #endif
 365                 /*FIXME use card skipping code*/
 366                 for (; card_data < card_data_end; ++card_data) {
 367                         int index;
 368                         int idx = (card_data - card_base) + extra_idx;
 369                         char *start = (char*)(obj_start + idx * CARD_SIZE_IN_BYTES);
 370                         char *card_end = start + CARD_SIZE_IN_BYTES;
 371                         char *elem;
 372
 373                         if (!*card_data)
 374                                 continue;
 375
 376                         HEAVY_STAT (++los_marked_cards);
 377                         if (!cards)
 378                                 sgen_card_table_prepare_card_for_scanning (card_data);
 379
 380                         card_end = MIN (card_end, obj_end);
 381
 382                         if (start <= (char*)arr->vector)
 383                                 index = 0;
 384                         else
 385                                 index = ARRAY_OBJ_INDEX (start, obj, elem_size);
 386
 387                         elem = (char*)mono_array_addr_with_size ((MonoArray*)obj, elem_size, index);
 388                         if (klass->element_class->valuetype) {
 389                                 for (; elem < card_end; elem += elem_size)
 390                                         major_collector.minor_scan_vtype (elem, desc, nursery_start, nursery_next, queue);
 391                         } else {
 392                                 HEAVY_STAT (++los_array_cards);
 393                                 for (; elem < card_end; elem += SIZEOF_VOID_P) {
 394                                         gpointer new, old = *(gpointer*)elem;
 395                                         /*XXX it might be faster to do a nursery check here instead as it avoid a call*/
 396                                         if (old) {
 397                                                 HEAVY_STAT (++los_array_remsets);
 398                                                 major_collector.copy_object ((void**)elem, queue);
 399                                                 new = *(gpointer*)elem;
 400                                                 if (G_UNLIKELY (ptr_in_nursery (new)))
 401                                                         mono_sgen_add_to_global_remset (elem);
 402                                         }
 403                                 }
 404                         }
 405                 }
 406
 407 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 408                 if (overflow_scan_end) {
 409                         extra_idx = card_data - card_base;
 410                         card_base = card_data = sgen_shadow_cardtable;
 411                         card_data_end = overflow_scan_end;
 412                         overflow_scan_end = NULL;
 413                         goto LOOP_HEAD;
 414                 }
 415 #endif
 416
 417         } else {
 418                 HEAVY_STAT (++bloby_objects);
 419                 if (cards) {
 420                         if (sgen_card_table_is_range_marked (cards, (mword)obj, obj_size))
 421                                 major_collector.minor_scan_object (obj, queue);
 422                 } else if (sgen_card_table_region_begin_scanning ((mword)obj, obj_size)) {
 423                         major_collector.minor_scan_object (obj, queue);
 424                 }
 425         }
 426 }
 427
 428 #ifdef CARDTABLE_STATS
 429
 430 typedef struct {
 431         int total, marked, remarked;
 432 } card_stats;
 433
 434 static card_stats major_stats, los_stats;
 435 static card_stats *cur_stats;
 436
 437 static void
 438 count_marked_cards (mword start, mword size)
 439 {
 440         mword end = start + size;
 441         while (start <= end) {
 442                 ++cur_stats->total;
 443                 if (sgen_card_table_address_is_marked (start))
 444                         ++cur_stats->marked;
 445                 start += CARD_SIZE_IN_BYTES;
 446         }
 447 }
 448
 449 static void
 450 count_remarked_cards (mword start, mword size)
 451 {
 452         mword end = start + size;
 453         while (start <= end) {
 454                 if (sgen_card_table_address_is_marked (start))
 455                         ++cur_stats->remarked;
 456                 start += CARD_SIZE_IN_BYTES;
 457         }
 458 }
 459
 460 #endif
 461
 462 static void
 463 card_tables_collect_stats (gboolean begin)
 464 {
 465 #ifdef CARDTABLE_STATS
 466         if (begin) {
 467                 memset (&major_stats, 0, sizeof (card_stats));
 468                 memset (&los_stats, 0, sizeof (card_stats));
 469                 cur_stats = &major_stats;
 470                 major_collector.iterate_live_block_ranges (count_marked_cards);
 471                 cur_stats = &los_stats;
 472                 mono_sgen_los_iterate_live_block_ranges (count_marked_cards);
 473         } else {
 474                 cur_stats = &major_stats;
 475                 major_collector.iterate_live_block_ranges (count_marked_cards);
 476                 cur_stats = &los_stats;
 477                 mono_sgen_los_iterate_live_block_ranges (count_remarked_cards);
 478                 printf ("cards major (t %d m %d r %d)  los (t %d m %d r %d) major_scan %lld los_scan %lld\n",
 479                         major_stats.total, major_stats.marked, major_stats.remarked,
 480                         los_stats.total, los_stats.marked, los_stats.remarked,
 481                         last_major_scan_time, last_los_scan_time);
 482         }
 483 #endif
 484 }
 485
 486 #else
 487
 488 void
 489 sgen_card_table_mark_address (mword address)
 490 {
 491         g_assert_not_reached ();
 492 }
 493
 494 void
 495 sgen_card_table_mark_range (mword address, mword size)
 496 {
 497         g_assert_not_reached ();
 498 }
 499
 500 #define sgen_card_table_address_is_marked(p)    FALSE
 501 #define scan_from_card_tables(start,end,queue)
 502 #define card_table_clear()
 503 #define card_table_init()
 504 #define card_tables_collect_stats(begin)
 505
 506 guint8*
 507 mono_gc_get_card_table (int *shift_bits, gpointer *mask)
 508 {
 509         return NULL;
 510 }
 511
 512 #endif