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 array cards scanned ", MONO_COUNTER_GC | MONO_COUNTER_LONG, &los_array_cards);
 189         mono_counters_register ("los array remsets", MONO_COUNTER_GC | MONO_COUNTER_LONG, &los_array_remsets);
 190         mono_counters_register ("cardtable scanned objects", MONO_COUNTER_GC | MONO_COUNTER_LONG, &scanned_objects);
 191         mono_counters_register ("cardtable large objects", MONO_COUNTER_GC | MONO_COUNTER_LONG, &large_objects);
 192         mono_counters_register ("cardtable bloby objects", MONO_COUNTER_GC | MONO_COUNTER_LONG, &bloby_objects);
 193 #endif
 194         mono_counters_register ("cardtable major scan time", MONO_COUNTER_GC | MONO_COUNTER_LONG, &major_card_scan_time);
 195         mono_counters_register ("cardtable los scan time", MONO_COUNTER_GC | MONO_COUNTER_LONG, &los_card_scan_time);
 196 }
 197
 198 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 199
 200 static void
 201 move_cards_to_shadow_table (mword start, mword size)
 202 {
 203         guint8 *from = sgen_card_table_get_card_address (start);
 204         guint8 *to = sgen_card_table_get_shadow_card_address (start);
 205         size_t bytes = cards_in_range (start, size);
 206
 207         if (to + bytes > SGEN_SHADOW_CARDTABLE_END) {
 208                 size_t first_chunk = SGEN_SHADOW_CARDTABLE_END - to;
 209                 size_t second_chunk = MIN (CARD_COUNT_IN_BYTES, bytes) - first_chunk;
 210
 211                 memcpy (to, from, first_chunk);
 212                 memcpy (sgen_shadow_cardtable, sgen_cardtable, second_chunk);
 213         } else {
 214                 memcpy (to, from, bytes);
 215         }
 216 }
 217
 218 static void
 219 clear_cards (mword start, mword size)
 220 {
 221         guint8 *addr = sgen_card_table_get_card_address (start);
 222         size_t bytes = cards_in_range (start, size);
 223
 224         if (addr + bytes > SGEN_CARDTABLE_END) {
 225                 size_t first_chunk = SGEN_CARDTABLE_END - addr;
 226
 227                 memset (addr, 0, first_chunk);
 228                 memset (sgen_cardtable, 0, bytes - first_chunk);
 229         } else {
 230                 memset (addr, 0, bytes);
 231         }
 232 }
 233
 234
 235 #else
 236
 237 static void
 238 clear_cards (mword start, mword size)
 239 {
 240         memset (sgen_card_table_get_card_address (start), 0, cards_in_range (start, size));
 241 }
 242
 243
 244 #endif
 245
 246 static void
 247 card_table_clear (void)
 248 {
 249         /*XXX we could do this in 2 ways. using mincore or iterating over all sections/los objects */
 250         if (use_cardtable) {
 251                 major_collector.iterate_live_block_ranges (clear_cards);
 252                 mono_sgen_los_iterate_live_block_ranges (clear_cards);
 253         }
 254 }
 255 static void
 256 scan_from_card_tables (void *start_nursery, void *end_nursery, GrayQueue *queue)
 257 {
 258         if (use_cardtable) {
 259                 TV_DECLARE (atv);
 260                 TV_DECLARE (btv);
 261
 262 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 263         /*FIXME we should have a bit on each block/los object telling if the object have marked cards.*/
 264         /*First we copy*/
 265         major_collector.iterate_live_block_ranges (move_cards_to_shadow_table);
 266         mono_sgen_los_iterate_live_block_ranges (move_cards_to_shadow_table);
 267
 268         /*Then we clear*/
 269         card_table_clear ();
 270 #endif
 271                 TV_GETTIME (atv);
 272                 major_collector.scan_card_table (queue);
 273                 TV_GETTIME (btv);
 274                 last_major_scan_time = TV_ELAPSED_MS (atv, btv);
 275                 major_card_scan_time += last_major_scan_time;
 276                 mono_sgen_los_scan_card_table (queue);
 277                 TV_GETTIME (atv);
 278                 last_los_scan_time = TV_ELAPSED_MS (btv, atv);
 279                 los_card_scan_time += last_los_scan_time;
 280         }
 281 }
 282
 283 guint8*
 284 mono_gc_get_card_table (int *shift_bits, gpointer *mask)
 285 {
 286         if (!use_cardtable)
 287                 return NULL;
 288
 289         g_assert (sgen_cardtable);
 290         *shift_bits = CARD_BITS;
 291 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 292         *mask = (gpointer)CARD_MASK;
 293 #else
 294         *mask = NULL;
 295 #endif
 296
 297         return sgen_cardtable;
 298 }
 299
 300 #if 0
 301 static void
 302 collect_faulted_cards (void)
 303 {
 304 #define CARD_PAGES (CARD_COUNT_IN_BYTES / 4096)
 305         int i, count = 0;
 306         unsigned char faulted [CARD_PAGES] = { 0 };
 307         mincore (sgen_cardtable, CARD_COUNT_IN_BYTES, faulted);
 308
 309         for (i = 0; i < CARD_PAGES; ++i) {
 310                 if (faulted [i])
 311                         ++count;
 312         }
 313
 314         printf ("TOTAL card pages %d faulted %d\n", CARD_PAGES, count);
 315 }
 316 #endif
 317
 318 #define MWORD_MASK (sizeof (mword) - 1)
 319
 320 static inline int
 321 find_card_offset (mword card)
 322 {
 323 /*XXX Use assembly as this generates some pretty bad code */
 324 #if defined(__i386__) && defined(__GNUC__)
 325         return  (__builtin_ffs (card) - 1) / 8;
 326 #elif defined(__x86_64__) && defined(__GNUC__)
 327         return (__builtin_ffsll (card) - 1) / 8;
 328 #elif defined(__s390x__)
 329         return (__builtin_ffsll (GUINT64_TO_LE(card)) - 1) / 8;
 330 #else
 331         // FIXME:
 332         g_assert_not_reached ();
 333         /*
 334         int i;
 335         guint8 *ptr = (guint *) &card;
 336         for (i = 0; i < sizeof (mword); ++i) {
 337                 if (ptr[i])
 338                         return i;
 339         }
 340         */
 341         return 0;
 342 #endif
 343 }
 344
 345 static guint8*
 346 find_next_card (guint8 *card_data, guint8 *end)
 347 {
 348         mword *cards, *cards_end;
 349         mword card;
 350
 351         while ((((mword)card_data) & MWORD_MASK) && card_data < end) {
 352                 if (*card_data)
 353                         return card_data;
 354                 ++card_data;
 355         }
 356
 357         if (card_data == end)
 358                 return end;
 359
 360         cards = (mword*)card_data;
 361         cards_end = (mword*)((mword)end & ~MWORD_MASK);
 362         while (cards < cards_end) {
 363                 card = *cards;
 364                 if (card)
 365                         return (guint8*)cards + find_card_offset (card);
 366                 ++cards;
 367         }
 368
 369         card_data = (guint8*)cards_end;
 370         while (card_data < end) {
 371                 if (*card_data)
 372                         return card_data;
 373                 ++card_data;
 374         }
 375
 376         return end;
 377 }
 378
 379 void
 380 sgen_cardtable_scan_object (char *obj, mword obj_size, guint8 *cards, SgenGrayQueue *queue)
 381 {
 382         MonoVTable *vt = (MonoVTable*)LOAD_VTABLE (obj);
 383         MonoClass *klass = vt->klass;
 384         CopyOrMarkObjectFunc copy_func = mono_sgen_get_copy_object ();
 385
 386         HEAVY_STAT (++large_objects);
 387
 388         if (!SGEN_VTABLE_HAS_REFERENCES (vt))
 389                 return;
 390
 391         if (vt->rank) {
 392                 guint8 *card_data, *card_base;
 393                 guint8 *card_data_end;
 394                 char *obj_start = sgen_card_table_align_pointer (obj);
 395                 char *obj_end = obj + obj_size;
 396                 size_t card_count;
 397                 int extra_idx = 0;
 398
 399                 MonoArray *arr = (MonoArray*)obj;
 400                 mword desc = (mword)klass->element_class->gc_descr;
 401                 int elem_size = mono_array_element_size (klass);
 402
 403 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 404                 guint8 *overflow_scan_end = NULL;
 405 #endif
 406
 407                 if (cards)
 408                         card_data = cards;
 409                 else
 410                         card_data = sgen_card_table_get_card_scan_address ((mword)obj);
 411
 412                 card_base = card_data;
 413                 card_count = cards_in_range ((mword)obj, obj_size);
 414                 card_data_end = card_data + card_count;
 415
 416
 417 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 418                 /*Check for overflow and if so, setup to scan in two steps*/
 419                 if (!cards && card_data_end >= SGEN_SHADOW_CARDTABLE_END) {
 420                         overflow_scan_end = sgen_shadow_cardtable + (card_data_end - SGEN_SHADOW_CARDTABLE_END);
 421                         card_data_end = SGEN_SHADOW_CARDTABLE_END;
 422                 }
 423
 424 LOOP_HEAD:
 425 #endif
 426
 427                 card_data = find_next_card (card_data, card_data_end);
 428                 for (; card_data < card_data_end; card_data = find_next_card (card_data + 1, card_data_end)) {
 429                         int index;
 430                         int idx = (card_data - card_base) + extra_idx;
 431                         char *start = (char*)(obj_start + idx * CARD_SIZE_IN_BYTES);
 432                         char *card_end = start + CARD_SIZE_IN_BYTES;
 433                         char *elem;
 434
 435                         HEAVY_STAT (++los_marked_cards);
 436
 437                         if (!cards)
 438                                 sgen_card_table_prepare_card_for_scanning (card_data);
 439
 440                         card_end = MIN (card_end, obj_end);
 441
 442                         if (start <= (char*)arr->vector)
 443                                 index = 0;
 444                         else
 445                                 index = ARRAY_OBJ_INDEX (start, obj, elem_size);
 446
 447                         elem = (char*)mono_array_addr_with_size ((MonoArray*)obj, elem_size, index);
 448                         if (klass->element_class->valuetype) {
 449                                 for (; elem < card_end; elem += elem_size)
 450                                         major_collector.minor_scan_vtype (elem, desc, queue);
 451                         } else {
 452                                 HEAVY_STAT (++los_array_cards);
 453                                 for (; elem < card_end; elem += SIZEOF_VOID_P) {
 454                                         gpointer new, old = *(gpointer*)elem;
 455                                         if (G_UNLIKELY (ptr_in_nursery (old))) {
 456                                                 HEAVY_STAT (++los_array_remsets);
 457                                                 copy_func ((void**)elem, queue);
 458                                                 new = *(gpointer*)elem;
 459                                                 if (G_UNLIKELY (ptr_in_nursery (new)))
 460                                                         mono_sgen_add_to_global_remset (elem);
 461                                         }
 462                                 }
 463                         }
 464                 }
 465
 466 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 467                 if (overflow_scan_end) {
 468                         extra_idx = card_data - card_base;
 469                         card_base = card_data = sgen_shadow_cardtable;
 470                         card_data_end = overflow_scan_end;
 471                         overflow_scan_end = NULL;
 472                         goto LOOP_HEAD;
 473                 }
 474 #endif
 475
 476         } else {
 477                 HEAVY_STAT (++bloby_objects);
 478                 if (cards) {
 479                         if (sgen_card_table_is_range_marked (cards, (mword)obj, obj_size))
 480                                 major_collector.minor_scan_object (obj, queue);
 481                 } else if (sgen_card_table_region_begin_scanning ((mword)obj, obj_size)) {
 482                         major_collector.minor_scan_object (obj, queue);
 483                 }
 484         }
 485 }
 486
 487 #ifdef CARDTABLE_STATS
 488
 489 typedef struct {
 490         int total, marked, remarked;
 491 } card_stats;
 492
 493 static card_stats major_stats, los_stats;
 494 static card_stats *cur_stats;
 495
 496 static void
 497 count_marked_cards (mword start, mword size)
 498 {
 499         mword end = start + size;
 500         while (start <= end) {
 501                 ++cur_stats->total;
 502                 if (sgen_card_table_address_is_marked (start))
 503                         ++cur_stats->marked;
 504                 start += CARD_SIZE_IN_BYTES;
 505         }
 506 }
 507
 508 static void
 509 count_remarked_cards (mword start, mword size)
 510 {
 511         mword end = start + size;
 512         while (start <= end) {
 513                 if (sgen_card_table_address_is_marked (start))
 514                         ++cur_stats->remarked;
 515                 start += CARD_SIZE_IN_BYTES;
 516         }
 517 }
 518
 519 #endif
 520
 521 static void
 522 card_tables_collect_stats (gboolean begin)
 523 {
 524 #ifdef CARDTABLE_STATS
 525         if (begin) {
 526                 memset (&major_stats, 0, sizeof (card_stats));
 527                 memset (&los_stats, 0, sizeof (card_stats));
 528                 cur_stats = &major_stats;
 529                 major_collector.iterate_live_block_ranges (count_marked_cards);
 530                 cur_stats = &los_stats;
 531                 mono_sgen_los_iterate_live_block_ranges (count_marked_cards);
 532         } else {
 533                 cur_stats = &major_stats;
 534                 major_collector.iterate_live_block_ranges (count_marked_cards);
 535                 cur_stats = &los_stats;
 536                 mono_sgen_los_iterate_live_block_ranges (count_remarked_cards);
 537                 printf ("cards major (t %d m %d r %d)  los (t %d m %d r %d) major_scan %lld los_scan %lld\n",
 538                         major_stats.total, major_stats.marked, major_stats.remarked,
 539                         los_stats.total, los_stats.marked, los_stats.remarked,
 540                         last_major_scan_time, last_los_scan_time);
 541         }
 542 #endif
 543 }
 544
 545 #else
 546
 547 void
 548 sgen_card_table_mark_address (mword address)
 549 {
 550         g_assert_not_reached ();
 551 }
 552
 553 void
 554 sgen_card_table_mark_range (mword address, mword size)
 555 {
 556         g_assert_not_reached ();
 557 }
 558
 559 #define sgen_card_table_address_is_marked(p)    FALSE
 560 #define scan_from_card_tables(start,end,queue)
 561 #define card_table_clear()
 562 #define card_table_init()
 563 #define card_tables_collect_stats(begin)
 564
 565 guint8*
 566 mono_gc_get_card_table (int *shift_bits, gpointer *mask)
 567 {
 568         return NULL;
 569 }
 570
 571 #endif