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 #else
 329         // FIXME:
 330         g_assert_not_reached ();
 331         /*
 332         int i;
 333         guint8 *ptr = &card;
 334         for (i = 0; i < sizeof (mword); ++i) {
 335                 if (card [i])
 336                         return i;
 337         }
 338         */
 339         return 0;
 340 #endif
 341 }
 342
 343 static guint8*
 344 find_next_card (guint8 *card_data, guint8 *end)
 345 {
 346         mword *cards, *cards_end;
 347         mword card;
 348
 349         while ((((mword)card_data) & MWORD_MASK) && card_data < end) {
 350                 if (*card_data)
 351                         return card_data;
 352                 ++card_data;
 353         }
 354
 355         if (card_data == end)
 356                 return end;
 357
 358         cards = (mword*)card_data;
 359         cards_end = (mword*)((mword)end & ~MWORD_MASK);
 360         while (cards < cards_end) {
 361                 card = *cards;
 362                 if (card)
 363                         return (guint8*)cards + find_card_offset (card);
 364                 ++cards;
 365         }
 366
 367         card_data = (guint8*)cards_end;
 368         while (card_data < end) {
 369                 if (*card_data)
 370                         return card_data;
 371                 ++card_data;
 372         }
 373
 374         return end;
 375 }
 376
 377 void
 378 sgen_cardtable_scan_object (char *obj, mword obj_size, guint8 *cards, SgenGrayQueue *queue)
 379 {
 380         MonoVTable *vt = (MonoVTable*)LOAD_VTABLE (obj);
 381         MonoClass *klass = vt->klass;
 382
 383         HEAVY_STAT (++large_objects);
 384
 385         if (!SGEN_VTABLE_HAS_REFERENCES (vt))
 386                 return;
 387
 388         if (vt->rank) {
 389                 guint8 *card_data, *card_base;
 390                 guint8 *card_data_end;
 391                 char *obj_start = sgen_card_table_align_pointer (obj);
 392                 char *obj_end = obj + obj_size;
 393                 size_t card_count;
 394                 int extra_idx = 0;
 395
 396                 MonoArray *arr = (MonoArray*)obj;
 397                 mword desc = (mword)klass->element_class->gc_descr;
 398                 int elem_size = mono_array_element_size (klass);
 399
 400 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 401                 guint8 *overflow_scan_end = NULL;
 402 #endif
 403
 404                 if (cards)
 405                         card_data = cards;
 406                 else
 407                         card_data = sgen_card_table_get_card_scan_address ((mword)obj);
 408
 409                 card_base = card_data;
 410                 card_count = cards_in_range ((mword)obj, obj_size);
 411                 card_data_end = card_data + card_count;
 412
 413
 414 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 415                 /*Check for overflow and if so, setup to scan in two steps*/
 416                 if (!cards && card_data_end >= SGEN_SHADOW_CARDTABLE_END) {
 417                         overflow_scan_end = sgen_shadow_cardtable + (card_data_end - SGEN_SHADOW_CARDTABLE_END);
 418                         card_data_end = SGEN_SHADOW_CARDTABLE_END;
 419                 }
 420
 421 LOOP_HEAD:
 422 #endif
 423
 424                 card_data = find_next_card (card_data, card_data_end);
 425                 for (; card_data < card_data_end; card_data = find_next_card (card_data + 1, card_data_end)) {
 426                         int index;
 427                         int idx = (card_data - card_base) + extra_idx;
 428                         char *start = (char*)(obj_start + idx * CARD_SIZE_IN_BYTES);
 429                         char *card_end = start + CARD_SIZE_IN_BYTES;
 430                         char *elem;
 431
 432                         HEAVY_STAT (++los_marked_cards);
 433
 434                         if (!cards)
 435                                 sgen_card_table_prepare_card_for_scanning (card_data);
 436
 437                         card_end = MIN (card_end, obj_end);
 438
 439                         if (start <= (char*)arr->vector)
 440                                 index = 0;
 441                         else
 442                                 index = ARRAY_OBJ_INDEX (start, obj, elem_size);
 443
 444                         elem = (char*)mono_array_addr_with_size ((MonoArray*)obj, elem_size, index);
 445                         if (klass->element_class->valuetype) {
 446                                 for (; elem < card_end; elem += elem_size)
 447                                         major_collector.minor_scan_vtype (elem, desc, nursery_start, nursery_next, queue);
 448                         } else {
 449                                 HEAVY_STAT (++los_array_cards);
 450                                 for (; elem < card_end; elem += SIZEOF_VOID_P) {
 451                                         gpointer new, old = *(gpointer*)elem;
 452                                         if (G_UNLIKELY (ptr_in_nursery (old))) {
 453                                                 HEAVY_STAT (++los_array_remsets);
 454                                                 major_collector.copy_object ((void**)elem, queue);
 455                                                 new = *(gpointer*)elem;
 456                                                 if (G_UNLIKELY (ptr_in_nursery (new)))
 457                                                         mono_sgen_add_to_global_remset (queue->allocator, elem);
 458                                         }
 459                                 }
 460                         }
 461                 }
 462
 463 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
 464                 if (overflow_scan_end) {
 465                         extra_idx = card_data - card_base;
 466                         card_base = card_data = sgen_shadow_cardtable;
 467                         card_data_end = overflow_scan_end;
 468                         overflow_scan_end = NULL;
 469                         goto LOOP_HEAD;
 470                 }
 471 #endif
 472
 473         } else {
 474                 HEAVY_STAT (++bloby_objects);
 475                 if (cards) {
 476                         if (sgen_card_table_is_range_marked (cards, (mword)obj, obj_size))
 477                                 major_collector.minor_scan_object (obj, queue);
 478                 } else if (sgen_card_table_region_begin_scanning ((mword)obj, obj_size)) {
 479                         major_collector.minor_scan_object (obj, queue);
 480                 }
 481         }
 482 }
 483
 484 #ifdef CARDTABLE_STATS
 485
 486 typedef struct {
 487         int total, marked, remarked;
 488 } card_stats;
 489
 490 static card_stats major_stats, los_stats;
 491 static card_stats *cur_stats;
 492
 493 static void
 494 count_marked_cards (mword start, mword size)
 495 {
 496         mword end = start + size;
 497         while (start <= end) {
 498                 ++cur_stats->total;
 499                 if (sgen_card_table_address_is_marked (start))
 500                         ++cur_stats->marked;
 501                 start += CARD_SIZE_IN_BYTES;
 502         }
 503 }
 504
 505 static void
 506 count_remarked_cards (mword start, mword size)
 507 {
 508         mword end = start + size;
 509         while (start <= end) {
 510                 if (sgen_card_table_address_is_marked (start))
 511                         ++cur_stats->remarked;
 512                 start += CARD_SIZE_IN_BYTES;
 513         }
 514 }
 515
 516 #endif
 517
 518 static void
 519 card_tables_collect_stats (gboolean begin)
 520 {
 521 #ifdef CARDTABLE_STATS
 522         if (begin) {
 523                 memset (&major_stats, 0, sizeof (card_stats));
 524                 memset (&los_stats, 0, sizeof (card_stats));
 525                 cur_stats = &major_stats;
 526                 major_collector.iterate_live_block_ranges (count_marked_cards);
 527                 cur_stats = &los_stats;
 528                 mono_sgen_los_iterate_live_block_ranges (count_marked_cards);
 529         } else {
 530                 cur_stats = &major_stats;
 531                 major_collector.iterate_live_block_ranges (count_marked_cards);
 532                 cur_stats = &los_stats;
 533                 mono_sgen_los_iterate_live_block_ranges (count_remarked_cards);
 534                 printf ("cards major (t %d m %d r %d)  los (t %d m %d r %d) major_scan %lld los_scan %lld\n",
 535                         major_stats.total, major_stats.marked, major_stats.remarked,
 536                         los_stats.total, los_stats.marked, los_stats.remarked,
 537                         last_major_scan_time, last_los_scan_time);
 538         }
 539 #endif
 540 }
 541
 542 #else
 543
 544 void
 545 sgen_card_table_mark_address (mword address)
 546 {
 547         g_assert_not_reached ();
 548 }
 549
 550 void
 551 sgen_card_table_mark_range (mword address, mword size)
 552 {
 553         g_assert_not_reached ();
 554 }
 555
 556 #define sgen_card_table_address_is_marked(p)    FALSE
 557 #define scan_from_card_tables(start,end,queue)
 558 #define card_table_clear()
 559 #define card_table_init()
 560 #define card_tables_collect_stats(begin)
 561
 562 guint8*
 563 mono_gc_get_card_table (int *shift_bits, gpointer *mask)
 564 {
 565         return NULL;
 566 }
 567
 568 #endif