mono/metadata/sgen-marksweep.c

   1 /*
   2  * sgen-marksweep.c: The Mark & Sweep major collector.
   3  *
   4  * Author:
   5  *      Mark Probst <mark.probst@gmail.com>
   6  *
   7  * Copyright 2009-2010 Novell, Inc.
   8  * Copyright (C) 2012 Xamarin Inc
   9  *
  10  * This library is free software; you can redistribute it and/or
  11  * modify it under the terms of the GNU Library General Public
  12  * License 2.0 as published by the Free Software Foundation;
  13  *
  14  * This library is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  17  * Library General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU Library General Public
  20  * License 2.0 along with this library; if not, write to the Free
  21  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  22  */
  23
  24 #include "config.h"
  25
  26 #ifdef HAVE_SGEN_GC
  27
  28 #include <math.h>
  29 #include <errno.h>
  30
  31 #include "utils/mono-counters.h"
  32 #include "utils/mono-semaphore.h"
  33 #include "utils/mono-time.h"
  34 #include "metadata/object-internals.h"
  35 #include "metadata/profiler-private.h"
  36
  37 #include "metadata/sgen-gc.h"
  38 #include "metadata/sgen-protocol.h"
  39 #include "metadata/sgen-cardtable.h"
  40 #include "metadata/sgen-memory-governor.h"
  41 #include "metadata/sgen-layout-stats.h"
  42 #include "metadata/gc-internal.h"
  43 #include "metadata/sgen-pointer-queue.h"
  44 #include "metadata/sgen-pinning.h"
  45 #include "metadata/sgen-workers.h"
  46
  47 #define SGEN_HAVE_CONCURRENT_MARK
  48
  49 #define MS_BLOCK_SIZE   (16*1024)
  50 #define MS_BLOCK_SIZE_SHIFT     14
  51 #define MAJOR_SECTION_SIZE      MS_BLOCK_SIZE
  52 #define CARDS_PER_BLOCK (MS_BLOCK_SIZE / CARD_SIZE_IN_BYTES)
  53
  54 /*
  55  * Don't allocate single blocks, but alloc a contingent of this many
  56  * blocks in one swoop.  This must be a power of two.
  57  */
  58 #define MS_BLOCK_ALLOC_NUM      32
  59
  60 #define BLOCK_INFO_IN_HEADER    1       /* BOOL FASTENABLE */
  61 #if !BLOCK_INFO_IN_HEADER
  62 #undef BLOCK_INFO_IN_HEADER
  63 #endif
  64
  65 /*
  66  * Number of bytes before the first object in a block.  At the start
  67  * of a block is the MSBlockHeader, then opional padding, then come
  68  * the objects, so this must be >= sizeof (MSBlockHeader).
  69  */
  70 #define MS_BLOCK_SKIP   ((sizeof (MSBlockHeader) + 15) & ~15)
  71
  72 #define MS_BLOCK_FREE   (MS_BLOCK_SIZE - MS_BLOCK_SKIP)
  73
  74 #define MS_NUM_MARK_WORDS       ((MS_BLOCK_SIZE / SGEN_ALLOC_ALIGN + sizeof (mword) * 8 - 1) / (sizeof (mword) * 8))
  75
  76 typedef struct _MSBlockInfo MSBlockInfo;
  77 struct _MSBlockInfo {
  78         int obj_size;
  79         int obj_size_index;
  80         unsigned int pinned : 1;
  81         unsigned int has_references : 1;
  82         unsigned int has_pinned : 1;    /* means cannot evacuate */
  83         unsigned int is_to_space : 1;
  84         unsigned int swept : 1;
  85 #ifndef BLOCK_INFO_IN_HEADER
  86         char *block;
  87 #endif
  88         void **free_list;
  89         MSBlockInfo *next_free;
  90         size_t pin_queue_first_entry;
  91         size_t pin_queue_last_entry;
  92 #ifdef SGEN_HAVE_CONCURRENT_MARK
  93         guint8 *cardtable_mod_union;
  94 #endif
  95         mword mark_words [MS_NUM_MARK_WORDS];
  96 };
  97
  98 #ifdef BLOCK_INFO_IN_HEADER
  99 #define MS_BLOCK_FOR_BLOCK_INFO(b)      ((char*)(b))
 100 #else
 101 #define MS_BLOCK_FOR_BLOCK_INFO(b)      ((b)->block)
 102 #endif
 103
 104 #define MS_BLOCK_OBJ(b,i)               (MS_BLOCK_FOR_BLOCK_INFO(b) + MS_BLOCK_SKIP + (b)->obj_size * (i))
 105 #define MS_BLOCK_OBJ_FOR_SIZE(b,i,obj_size)             (MS_BLOCK_FOR_BLOCK_INFO(b) + MS_BLOCK_SKIP + (obj_size) * (i))
 106 #define MS_BLOCK_DATA_FOR_OBJ(o)        ((char*)((mword)(o) & ~(mword)(MS_BLOCK_SIZE - 1)))
 107
 108 typedef struct {
 109 #ifdef BLOCK_INFO_IN_HEADER
 110         MSBlockInfo info;
 111 #else
 112         MSBlockInfo *info;
 113 #endif
 114 } MSBlockHeader;
 115
 116 #ifdef BLOCK_INFO_IN_HEADER
 117 #define MS_BLOCK_FOR_OBJ(o)             (&((MSBlockHeader*)MS_BLOCK_DATA_FOR_OBJ ((o)))->info)
 118 #else
 119 #define MS_BLOCK_FOR_OBJ(o)             (((MSBlockHeader*)MS_BLOCK_DATA_FOR_OBJ ((o)))->info)
 120 #endif
 121
 122 /* object index will always be small */
 123 #define MS_BLOCK_OBJ_INDEX(o,b) ((int)(((char*)(o) - (MS_BLOCK_FOR_BLOCK_INFO(b) + MS_BLOCK_SKIP)) / (b)->obj_size))
 124
 125 //casting to int is fine since blocks are 32k
 126 #define MS_CALC_MARK_BIT(w,b,o)         do {                            \
 127                 int i = ((int)((char*)(o) - MS_BLOCK_DATA_FOR_OBJ ((o)))) >> SGEN_ALLOC_ALIGN_BITS; \
 128                 if (sizeof (mword) == 4) {                              \
 129                         (w) = i >> 5;                                   \
 130                         (b) = i & 31;                                   \
 131                 } else {                                                \
 132                         (w) = i >> 6;                                   \
 133                         (b) = i & 63;                                   \
 134                 }                                                       \
 135         } while (0)
 136
 137 #define MS_MARK_BIT(bl,w,b)     ((bl)->mark_words [(w)] & (ONE_P << (b)))
 138 #define MS_SET_MARK_BIT(bl,w,b) ((bl)->mark_words [(w)] |= (ONE_P << (b)))
 139
 140 #define MS_OBJ_ALLOCED(o,b)     (*(void**)(o) && (*(char**)(o) < MS_BLOCK_FOR_BLOCK_INFO (b) || *(char**)(o) >= MS_BLOCK_FOR_BLOCK_INFO (b) + MS_BLOCK_SIZE))
 141
 142 #define MS_BLOCK_OBJ_SIZE_FACTOR        (sqrt (2.0))
 143
 144 /*
 145  * This way we can lookup block object size indexes for sizes up to
 146  * 256 bytes with a single load.
 147  */
 148 #define MS_NUM_FAST_BLOCK_OBJ_SIZE_INDEXES      32
 149
 150 static int *block_obj_sizes;
 151 static int num_block_obj_sizes;
 152 static int fast_block_obj_size_indexes [MS_NUM_FAST_BLOCK_OBJ_SIZE_INDEXES];
 153
 154 #define MS_BLOCK_FLAG_PINNED    1
 155 #define MS_BLOCK_FLAG_REFS      2
 156
 157 #define MS_BLOCK_TYPE_MAX       4
 158
 159 static gboolean *evacuate_block_obj_sizes;
 160 static float evacuation_threshold = 0.666f;
 161 #ifdef SGEN_HAVE_CONCURRENT_MARK
 162 static float concurrent_evacuation_threshold = 0.666f;
 163 static gboolean want_evacuation = FALSE;
 164 #endif
 165
 166 static gboolean lazy_sweep = TRUE;
 167 static gboolean have_swept;
 168
 169 #ifdef SGEN_HAVE_CONCURRENT_MARK
 170 static gboolean concurrent_mark;
 171 #endif
 172
 173 #define BLOCK_IS_TAGGED_HAS_REFERENCES(bl)      SGEN_POINTER_IS_TAGGED_1 ((bl))
 174 #define BLOCK_TAG_HAS_REFERENCES(bl)            SGEN_POINTER_TAG_1 ((bl))
 175 #define BLOCK_UNTAG_HAS_REFERENCES(bl)          SGEN_POINTER_UNTAG_1 ((bl))
 176
 177 #define BLOCK_TAG(bl)   ((bl)->has_references ? BLOCK_TAG_HAS_REFERENCES ((bl)) : (bl))
 178
 179 /* all allocated blocks in the system */
 180 static SgenPointerQueue allocated_blocks;
 181
 182 /* non-allocated block free-list */
 183 static void *empty_blocks = NULL;
 184 static size_t num_empty_blocks = 0;
 185
 186 #define FOREACH_BLOCK(bl)       { size_t __index; for (__index = 0; __index < allocated_blocks.next_slot; ++__index) { (bl) = BLOCK_UNTAG_HAS_REFERENCES (allocated_blocks.data [__index]);
 187 #define FOREACH_BLOCK_HAS_REFERENCES(bl,hr)     { size_t __index; for (__index = 0; __index < allocated_blocks.next_slot; ++__index) { (bl) = allocated_blocks.data [__index]; (hr) = BLOCK_IS_TAGGED_HAS_REFERENCES ((bl)); (bl) = BLOCK_UNTAG_HAS_REFERENCES ((bl));
 188 #define END_FOREACH_BLOCK       } }
 189 #define DELETE_BLOCK_IN_FOREACH()       (allocated_blocks.data [__index] = NULL)
 190
 191 static size_t num_major_sections = 0;
 192 /* one free block list for each block object size */
 193 static MSBlockInfo **free_block_lists [MS_BLOCK_TYPE_MAX];
 194
 195 static long long stat_major_blocks_alloced = 0;
 196 static long long stat_major_blocks_freed = 0;
 197 static long long stat_major_blocks_lazy_swept = 0;
 198 static long long stat_major_objects_evacuated = 0;
 199
 200 #if SIZEOF_VOID_P != 8
 201 static long long stat_major_blocks_freed_ideal = 0;
 202 static long long stat_major_blocks_freed_less_ideal = 0;
 203 static long long stat_major_blocks_freed_individual = 0;
 204 static long long stat_major_blocks_alloced_less_ideal = 0;
 205 #endif
 206
 207 #ifdef SGEN_COUNT_NUMBER_OF_MAJOR_OBJECTS_MARKED
 208 static long long num_major_objects_marked = 0;
 209 #define INC_NUM_MAJOR_OBJECTS_MARKED()  (++num_major_objects_marked)
 210 #else
 211 #define INC_NUM_MAJOR_OBJECTS_MARKED()
 212 #endif
 213
 214 #ifdef SGEN_HEAVY_BINARY_PROTOCOL
 215 static mono_mutex_t scanned_objects_list_lock;
 216 static SgenPointerQueue scanned_objects_list;
 217
 218 static void
 219 add_scanned_object (void *ptr)
 220 {
 221         if (!binary_protocol_is_enabled ())
 222                 return;
 223
 224         mono_mutex_lock (&scanned_objects_list_lock);
 225         sgen_pointer_queue_add (&scanned_objects_list, ptr);
 226         mono_mutex_unlock (&scanned_objects_list_lock);
 227 }
 228 #endif
 229
 230 static void
 231 sweep_block (MSBlockInfo *block, gboolean during_major_collection);
 232
 233 static int
 234 ms_find_block_obj_size_index (size_t size)
 235 {
 236         int i;
 237         SGEN_ASSERT (9, size <= SGEN_MAX_SMALL_OBJ_SIZE, "size %d is bigger than max small object size %d", size, SGEN_MAX_SMALL_OBJ_SIZE);
 238         for (i = 0; i < num_block_obj_sizes; ++i)
 239                 if (block_obj_sizes [i] >= size)
 240                         return i;
 241         g_error ("no object of size %d\n", size);
 242 }
 243
 244 #define FREE_BLOCKS_FROM(lists,p,r)     (lists [((p) ? MS_BLOCK_FLAG_PINNED : 0) | ((r) ? MS_BLOCK_FLAG_REFS : 0)])
 245 #define FREE_BLOCKS(p,r)                (FREE_BLOCKS_FROM (free_block_lists, (p), (r)))
 246
 247 #define MS_BLOCK_OBJ_SIZE_INDEX(s)                              \
 248         (((s)+7)>>3 < MS_NUM_FAST_BLOCK_OBJ_SIZE_INDEXES ?      \
 249          fast_block_obj_size_indexes [((s)+7)>>3] :             \
 250          ms_find_block_obj_size_index ((s)))
 251
 252 static void*
 253 major_alloc_heap (mword nursery_size, mword nursery_align, int the_nursery_bits)
 254 {
 255         char *start;
 256         if (nursery_align)
 257                 start = sgen_alloc_os_memory_aligned (nursery_size, nursery_align, SGEN_ALLOC_HEAP | SGEN_ALLOC_ACTIVATE, "nursery");
 258         else
 259                 start = sgen_alloc_os_memory (nursery_size, SGEN_ALLOC_HEAP | SGEN_ALLOC_ACTIVATE, "nursery");
 260
 261         return start;
 262 }
 263
 264 static void
 265 update_heap_boundaries_for_block (MSBlockInfo *block)
 266 {
 267         sgen_update_heap_boundaries ((mword)MS_BLOCK_FOR_BLOCK_INFO (block), (mword)MS_BLOCK_FOR_BLOCK_INFO (block) + MS_BLOCK_SIZE);
 268 }
 269
 270 static void*
 271 ms_get_empty_block (void)
 272 {
 273         char *p;
 274         int i;
 275         void *block, *empty, *next;
 276
 277  retry:
 278         if (!empty_blocks) {
 279                 /*
 280                  * We try allocating MS_BLOCK_ALLOC_NUM blocks first.  If that's
 281                  * unsuccessful, we halve the number of blocks and try again, until we're at
 282                  * 1.  If that doesn't work, either, we assert.
 283                  */
 284                 int alloc_num = MS_BLOCK_ALLOC_NUM;
 285                 for (;;) {
 286                         p = sgen_alloc_os_memory_aligned (MS_BLOCK_SIZE * alloc_num, MS_BLOCK_SIZE, SGEN_ALLOC_HEAP | SGEN_ALLOC_ACTIVATE,
 287                                         alloc_num == 1 ? "major heap section" : NULL);
 288                         if (p)
 289                                 break;
 290                         alloc_num >>= 1;
 291                 }
 292
 293                 for (i = 0; i < alloc_num; ++i) {
 294                         block = p;
 295                         /*
 296                          * We do the free list update one after the
 297                          * other so that other threads can use the new
 298                          * blocks as quickly as possible.
 299                          */
 300                         do {
 301                                 empty = empty_blocks;
 302                                 *(void**)block = empty;
 303                         } while (SGEN_CAS_PTR ((gpointer*)&empty_blocks, block, empty) != empty);
 304                         p += MS_BLOCK_SIZE;
 305                 }
 306
 307                 SGEN_ATOMIC_ADD_P (num_empty_blocks, alloc_num);
 308
 309                 stat_major_blocks_alloced += alloc_num;
 310 #if SIZEOF_VOID_P != 8
 311                 if (alloc_num != MS_BLOCK_ALLOC_NUM)
 312                         stat_major_blocks_alloced_less_ideal += alloc_num;
 313 #endif
 314         }
 315
 316         do {
 317                 empty = empty_blocks;
 318                 if (!empty)
 319                         goto retry;
 320                 block = empty;
 321                 next = *(void**)block;
 322         } while (SGEN_CAS_PTR (&empty_blocks, next, empty) != empty);
 323
 324         SGEN_ATOMIC_ADD_P (num_empty_blocks, -1);
 325
 326         *(void**)block = NULL;
 327
 328         g_assert (!((mword)block & (MS_BLOCK_SIZE - 1)));
 329
 330         return block;
 331 }
 332
 333 static void
 334 ms_free_block (void *block)
 335 {
 336         void *empty;
 337
 338         sgen_memgov_release_space (MS_BLOCK_SIZE, SPACE_MAJOR);
 339         memset (block, 0, MS_BLOCK_SIZE);
 340
 341         do {
 342                 empty = empty_blocks;
 343                 *(void**)block = empty;
 344         } while (SGEN_CAS_PTR (&empty_blocks, block, empty) != empty);
 345
 346         SGEN_ATOMIC_ADD_P (num_empty_blocks, 1);
 347 }
 348
 349 //#define MARKSWEEP_CONSISTENCY_CHECK
 350
 351 #ifdef MARKSWEEP_CONSISTENCY_CHECK
 352 static void
 353 check_block_free_list (MSBlockInfo *block, int size, gboolean pinned)
 354 {
 355         MSBlockInfo *b;
 356
 357         for (; block; block = block->next_free) {
 358                 g_assert (block->obj_size == size);
 359                 g_assert ((pinned && block->pinned) || (!pinned && !block->pinned));
 360
 361                 /* blocks in the free lists must have at least
 362                    one free slot */
 363                 if (block->swept)
 364                         g_assert (block->free_list);
 365
 366                 /* the block must be in the allocated_blocks array */
 367                 g_assert (sgen_pointer_queue_find (&allocated_blocks, BLOCK_TAG (block)) != (size_t)-1);
 368         }
 369 }
 370
 371 static void
 372 check_empty_blocks (void)
 373 {
 374         void *p;
 375         size_t i = 0;
 376         for (p = empty_blocks; p; p = *(void**)p)
 377                 ++i;
 378         g_assert (i == num_empty_blocks);
 379 }
 380
 381 static void
 382 consistency_check (void)
 383 {
 384         MSBlockInfo *block;
 385         int i;
 386
 387         /* check all blocks */
 388         FOREACH_BLOCK (block) {
 389                 int count = MS_BLOCK_FREE / block->obj_size;
 390                 int num_free = 0;
 391                 void **free;
 392
 393                 /* check block header */
 394                 g_assert (((MSBlockHeader*)block->block)->info == block);
 395
 396                 /* count number of free slots */
 397                 for (i = 0; i < count; ++i) {
 398                         void **obj = (void**) MS_BLOCK_OBJ (block, i);
 399                         if (!MS_OBJ_ALLOCED (obj, block))
 400                                 ++num_free;
 401                 }
 402
 403                 /* check free list */
 404                 for (free = block->free_list; free; free = (void**)*free) {
 405                         g_assert (MS_BLOCK_FOR_OBJ (free) == block);
 406                         --num_free;
 407                 }
 408                 g_assert (num_free == 0);
 409
 410                 /* check all mark words are zero */
 411                 if (block->swept) {
 412                         for (i = 0; i < MS_NUM_MARK_WORDS; ++i)
 413                                 g_assert (block->mark_words [i] == 0);
 414                 }
 415         } END_FOREACH_BLOCK;
 416
 417         /* check free blocks */
 418         for (i = 0; i < num_block_obj_sizes; ++i) {
 419                 int j;
 420                 for (j = 0; j < MS_BLOCK_TYPE_MAX; ++j)
 421                         check_block_free_list (free_block_lists [j][i], block_obj_sizes [i], j & MS_BLOCK_FLAG_PINNED);
 422         }
 423
 424         check_empty_blocks ();
 425 }
 426 #endif
 427
 428 static gboolean
 429 ms_alloc_block (int size_index, gboolean pinned, gboolean has_references)
 430 {
 431         int size = block_obj_sizes [size_index];
 432         int count = MS_BLOCK_FREE / size;
 433         MSBlockInfo *info;
 434         MSBlockInfo **free_blocks = FREE_BLOCKS (pinned, has_references);
 435         char *obj_start;
 436         int i;
 437
 438         if (!sgen_memgov_try_alloc_space (MS_BLOCK_SIZE, SPACE_MAJOR))
 439                 return FALSE;
 440
 441 #ifdef BLOCK_INFO_IN_HEADER
 442         info = (MSBlockInfo*)ms_get_empty_block ();
 443 #else
 444         {
 445                 MSBlockHeader *header;
 446                 info = sgen_alloc_internal (INTERNAL_MEM_MS_BLOCK_INFO);
 447                 info->block = ms_get_empty_block ();
 448                 header = (MSBlockHeader*)info->block;
 449                 header->info = info;
 450         }
 451 #endif
 452
 453         SGEN_ASSERT (9, count >= 2, "block with %d objects, it must hold at least 2", count);
 454
 455         info->obj_size = size;
 456         info->obj_size_index = size_index;
 457         info->pinned = pinned;
 458         info->has_references = has_references;
 459         info->has_pinned = pinned;
 460         /*
 461          * Blocks that are to-space are not evacuated from.  During an major collection
 462          * blocks are allocated for two reasons: evacuating objects from the nursery and
 463          * evacuating them from major blocks marked for evacuation.  In both cases we don't
 464          * want further evacuation.
 465          */
 466         info->is_to_space = (sgen_get_current_collection_generation () == GENERATION_OLD);
 467         info->swept = 1;
 468 #ifdef SGEN_HAVE_CONCURRENT_MARK
 469         info->cardtable_mod_union = NULL;
 470 #endif
 471
 472         update_heap_boundaries_for_block (info);
 473
 474         /* build free list */
 475         obj_start = MS_BLOCK_FOR_BLOCK_INFO (info) + MS_BLOCK_SKIP;
 476         info->free_list = (void**)obj_start;
 477         /* we're skipping the last one - it must be nulled */
 478         for (i = 0; i < count - 1; ++i) {
 479                 char *next_obj_start = obj_start + size;
 480                 *(void**)obj_start = next_obj_start;
 481                 obj_start = next_obj_start;
 482         }
 483         /* the last one */
 484         *(void**)obj_start = NULL;
 485
 486         info->next_free = free_blocks [size_index];
 487         free_blocks [size_index] = info;
 488
 489         sgen_pointer_queue_add (&allocated_blocks, BLOCK_TAG (info));
 490
 491         ++num_major_sections;
 492         return TRUE;
 493 }
 494
 495 static gboolean
 496 obj_is_from_pinned_alloc (char *ptr)
 497 {
 498         MSBlockInfo *block;
 499
 500         FOREACH_BLOCK (block) {
 501                 if (ptr >= MS_BLOCK_FOR_BLOCK_INFO (block) && ptr <= MS_BLOCK_FOR_BLOCK_INFO (block) + MS_BLOCK_SIZE)
 502                         return block->pinned;
 503         } END_FOREACH_BLOCK;
 504         return FALSE;
 505 }
 506
 507 static void*
 508 unlink_slot_from_free_list_uncontested (MSBlockInfo **free_blocks, int size_index)
 509 {
 510         MSBlockInfo *block;
 511         void *obj;
 512
 513         block = free_blocks [size_index];
 514         SGEN_ASSERT (9, block, "no free block to unlink from free_blocks %p size_index %d", free_blocks, size_index);
 515
 516         if (G_UNLIKELY (!block->swept)) {
 517                 stat_major_blocks_lazy_swept ++;
 518                 sweep_block (block, FALSE);
 519         }
 520
 521         obj = block->free_list;
 522         SGEN_ASSERT (9, obj, "block %p in free list had no available object to alloc from", block);
 523
 524         block->free_list = *(void**)obj;
 525         if (!block->free_list) {
 526                 free_blocks [size_index] = block->next_free;
 527                 block->next_free = NULL;
 528         }
 529
 530         return obj;
 531 }
 532
 533 static void*
 534 alloc_obj (MonoVTable *vtable, size_t size, gboolean pinned, gboolean has_references)
 535 {
 536         int size_index = MS_BLOCK_OBJ_SIZE_INDEX (size);
 537         MSBlockInfo **free_blocks = FREE_BLOCKS (pinned, has_references);
 538         void *obj;
 539
 540         if (!free_blocks [size_index]) {
 541                 if (G_UNLIKELY (!ms_alloc_block (size_index, pinned, has_references)))
 542                         return NULL;
 543         }
 544
 545         obj = unlink_slot_from_free_list_uncontested (free_blocks, size_index);
 546
 547         *(MonoVTable**)obj = vtable;
 548
 549         return obj;
 550 }
 551
 552 static void*
 553 major_alloc_object (MonoVTable *vtable, size_t size, gboolean has_references)
 554 {
 555         return alloc_obj (vtable, size, FALSE, has_references);
 556 }
 557
 558 /*
 559  * We're not freeing the block if it's empty.  We leave that work for
 560  * the next major collection.
 561  *
 562  * This is just called from the domain clearing code, which runs in a
 563  * single thread and has the GC lock, so we don't need an extra lock.
 564  */
 565 static void
 566 free_object (char *obj, size_t size, gboolean pinned)
 567 {
 568         MSBlockInfo *block = MS_BLOCK_FOR_OBJ (obj);
 569         int word, bit;
 570
 571         if (!block->swept)
 572                 sweep_block (block, FALSE);
 573         SGEN_ASSERT (9, (pinned && block->pinned) || (!pinned && !block->pinned), "free-object pinning mixup object %p pinned %d block %p pinned %d", obj, pinned, block, block->pinned);
 574         SGEN_ASSERT (9, MS_OBJ_ALLOCED (obj, block), "object %p is already free", obj);
 575         MS_CALC_MARK_BIT (word, bit, obj);
 576         SGEN_ASSERT (9, !MS_MARK_BIT (block, word, bit), "object %p has mark bit set");
 577         if (!block->free_list) {
 578                 MSBlockInfo **free_blocks = FREE_BLOCKS (pinned, block->has_references);
 579                 int size_index = MS_BLOCK_OBJ_SIZE_INDEX (size);
 580                 SGEN_ASSERT (9, !block->next_free, "block %p doesn't have a free-list of object but belongs to a free-list of blocks");
 581                 block->next_free = free_blocks [size_index];
 582                 free_blocks [size_index] = block;
 583         }
 584         memset (obj, 0, size);
 585         *(void**)obj = block->free_list;
 586         block->free_list = (void**)obj;
 587 }
 588
 589 static void
 590 major_free_non_pinned_object (char *obj, size_t size)
 591 {
 592         free_object (obj, size, FALSE);
 593 }
 594
 595 /* size is a multiple of SGEN_ALLOC_ALIGN */
 596 static void*
 597 major_alloc_small_pinned_obj (MonoVTable *vtable, size_t size, gboolean has_references)
 598 {
 599         void *res;
 600
 601         res = alloc_obj (vtable, size, TRUE, has_references);
 602          /*If we failed to alloc memory, we better try releasing memory
 603           *as pinned alloc is requested by the runtime.
 604           */
 605          if (!res) {
 606                 sgen_perform_collection (0, GENERATION_OLD, "pinned alloc failure", TRUE);
 607                 res = alloc_obj (vtable, size, TRUE, has_references);
 608          }
 609          return res;
 610 }
 611
 612 static void
 613 free_pinned_object (char *obj, size_t size)
 614 {
 615         free_object (obj, size, TRUE);
 616 }
 617
 618 /*
 619  * size is already rounded up and we hold the GC lock.
 620  */
 621 static void*
 622 major_alloc_degraded (MonoVTable *vtable, size_t size)
 623 {
 624         void *obj;
 625         size_t old_num_sections;
 626
 627         old_num_sections = num_major_sections;
 628
 629         obj = alloc_obj (vtable, size, FALSE, SGEN_VTABLE_HAS_REFERENCES (vtable));
 630         if (G_LIKELY (obj)) {
 631                 HEAVY_STAT (++stat_objects_alloced_degraded);
 632                 HEAVY_STAT (stat_bytes_alloced_degraded += size);
 633                 g_assert (num_major_sections >= old_num_sections);
 634                 sgen_register_major_sections_alloced (num_major_sections - old_num_sections);
 635         }
 636         return obj;
 637 }
 638
 639 /*
 640  * obj is some object.  If it's not in the major heap (i.e. if it's in
 641  * the nursery or LOS), return FALSE.  Otherwise return whether it's
 642  * been marked or copied.
 643  */
 644 static gboolean
 645 major_is_object_live (char *obj)
 646 {
 647         MSBlockInfo *block;
 648         int word, bit;
 649         mword objsize;
 650
 651         if (sgen_ptr_in_nursery (obj))
 652                 return FALSE;
 653
 654         objsize = SGEN_ALIGN_UP (sgen_safe_object_get_size ((MonoObject*)obj));
 655
 656         /* LOS */
 657         if (objsize > SGEN_MAX_SMALL_OBJ_SIZE)
 658                 return FALSE;
 659
 660         /* now we know it's in a major block */
 661         block = MS_BLOCK_FOR_OBJ (obj);
 662         SGEN_ASSERT (9, !block->pinned, "block %p is pinned, BTW why is this bad?");
 663         MS_CALC_MARK_BIT (word, bit, obj);
 664         return MS_MARK_BIT (block, word, bit) ? TRUE : FALSE;
 665 }
 666
 667 static gboolean
 668 major_ptr_is_in_non_pinned_space (char *ptr, char **start)
 669 {
 670         MSBlockInfo *block;
 671
 672         FOREACH_BLOCK (block) {
 673                 if (ptr >= MS_BLOCK_FOR_BLOCK_INFO (block) && ptr <= MS_BLOCK_FOR_BLOCK_INFO (block) + MS_BLOCK_SIZE) {
 674                         int count = MS_BLOCK_FREE / block->obj_size;
 675                         int i;
 676
 677                         *start = NULL;
 678                         for (i = 0; i <= count; ++i) {
 679                                 if (ptr >= MS_BLOCK_OBJ (block, i) && ptr < MS_BLOCK_OBJ (block, i + 1)) {
 680                                         *start = MS_BLOCK_OBJ (block, i);
 681                                         break;
 682                                 }
 683                         }
 684                         return !block->pinned;
 685                 }
 686         } END_FOREACH_BLOCK;
 687         return FALSE;
 688 }
 689
 690 static void
 691 major_iterate_objects (IterateObjectsFlags flags, IterateObjectCallbackFunc callback, void *data)
 692 {
 693         gboolean sweep = flags & ITERATE_OBJECTS_SWEEP;
 694         gboolean non_pinned = flags & ITERATE_OBJECTS_NON_PINNED;
 695         gboolean pinned = flags & ITERATE_OBJECTS_PINNED;
 696         MSBlockInfo *block;
 697
 698         FOREACH_BLOCK (block) {
 699                 int count = MS_BLOCK_FREE / block->obj_size;
 700                 int i;
 701
 702                 if (block->pinned && !pinned)
 703                         continue;
 704                 if (!block->pinned && !non_pinned)
 705                         continue;
 706                 if (sweep && lazy_sweep) {
 707                         sweep_block (block, FALSE);
 708                         SGEN_ASSERT (0, block->swept, "Block must be swept after sweeping");
 709                 }
 710
 711                 for (i = 0; i < count; ++i) {
 712                         void **obj = (void**) MS_BLOCK_OBJ (block, i);
 713                         if (!block->swept) {
 714                                 int word, bit;
 715                                 MS_CALC_MARK_BIT (word, bit, obj);
 716                                 if (!MS_MARK_BIT (block, word, bit))
 717                                         continue;
 718                         }
 719                         if (MS_OBJ_ALLOCED (obj, block))
 720                                 callback ((char*)obj, block->obj_size, data);
 721                 }
 722         } END_FOREACH_BLOCK;
 723 }
 724
 725 static gboolean
 726 major_is_valid_object (char *object)
 727 {
 728         MSBlockInfo *block;
 729
 730         FOREACH_BLOCK (block) {
 731                 int idx;
 732                 char *obj;
 733
 734                 if ((MS_BLOCK_FOR_BLOCK_INFO (block) > object) || ((MS_BLOCK_FOR_BLOCK_INFO (block) + MS_BLOCK_SIZE) <= object))
 735                         continue;
 736
 737                 idx = MS_BLOCK_OBJ_INDEX (object, block);
 738                 obj = (char*)MS_BLOCK_OBJ (block, idx);
 739                 if (obj != object)
 740                         return FALSE;
 741                 return MS_OBJ_ALLOCED (obj, block);
 742         } END_FOREACH_BLOCK;
 743
 744         return FALSE;
 745 }
 746
 747
 748 static MonoVTable*
 749 major_describe_pointer (char *ptr)
 750 {
 751         MSBlockInfo *block;
 752
 753         FOREACH_BLOCK (block) {
 754                 int idx;
 755                 char *obj;
 756                 gboolean live;
 757                 MonoVTable *vtable;
 758                 int w, b;
 759                 gboolean marked;
 760
 761                 if ((MS_BLOCK_FOR_BLOCK_INFO (block) > ptr) || ((MS_BLOCK_FOR_BLOCK_INFO (block) + MS_BLOCK_SIZE) <= ptr))
 762                         continue;
 763
 764                 SGEN_LOG (0, "major-ptr (block %p sz %d pin %d ref %d)\n",
 765                         MS_BLOCK_FOR_BLOCK_INFO (block), block->obj_size, block->pinned, block->has_references);
 766
 767                 idx = MS_BLOCK_OBJ_INDEX (ptr, block);
 768                 obj = (char*)MS_BLOCK_OBJ (block, idx);
 769                 live = MS_OBJ_ALLOCED (obj, block);
 770                 vtable = live ? (MonoVTable*)SGEN_LOAD_VTABLE (obj) : NULL;
 771
 772                 MS_CALC_MARK_BIT (w, b, obj);
 773                 marked = MS_MARK_BIT (block, w, b);
 774
 775                 if (obj == ptr) {
 776                         SGEN_LOG (0, "\t(");
 777                         if (live)
 778                                 SGEN_LOG (0, "object");
 779                         else
 780                                 SGEN_LOG (0, "dead-object");
 781                 } else {
 782                         if (live)
 783                                 SGEN_LOG (0, "interior-ptr offset %td", ptr - obj);
 784                         else
 785                                 SGEN_LOG (0, "dead-interior-ptr offset %td", ptr - obj);
 786                 }
 787
 788                 SGEN_LOG (0, " marked %d)\n", marked ? 1 : 0);
 789
 790                 return vtable;
 791         } END_FOREACH_BLOCK;
 792
 793         return NULL;
 794 }
 795
 796 static void
 797 major_check_scan_starts (void)
 798 {
 799 }
 800
 801 static void
 802 major_dump_heap (FILE *heap_dump_file)
 803 {
 804         MSBlockInfo *block;
 805         int *slots_available = alloca (sizeof (int) * num_block_obj_sizes);
 806         int *slots_used = alloca (sizeof (int) * num_block_obj_sizes);
 807         int i;
 808
 809         for (i = 0; i < num_block_obj_sizes; ++i)
 810                 slots_available [i] = slots_used [i] = 0;
 811
 812         FOREACH_BLOCK (block) {
 813                 int index = ms_find_block_obj_size_index (block->obj_size);
 814                 int count = MS_BLOCK_FREE / block->obj_size;
 815
 816                 slots_available [index] += count;
 817                 for (i = 0; i < count; ++i) {
 818                         if (MS_OBJ_ALLOCED (MS_BLOCK_OBJ (block, i), block))
 819                                 ++slots_used [index];
 820                 }
 821         } END_FOREACH_BLOCK;
 822
 823         fprintf (heap_dump_file, "<occupancies>\n");
 824         for (i = 0; i < num_block_obj_sizes; ++i) {
 825                 fprintf (heap_dump_file, "<occupancy size=\"%d\" available=\"%d\" used=\"%d\" />\n",
 826                                 block_obj_sizes [i], slots_available [i], slots_used [i]);
 827         }
 828         fprintf (heap_dump_file, "</occupancies>\n");
 829
 830         FOREACH_BLOCK (block) {
 831                 int count = MS_BLOCK_FREE / block->obj_size;
 832                 int i;
 833                 int start = -1;
 834
 835                 fprintf (heap_dump_file, "<section type=\"%s\" size=\"%zu\">\n", "old", (size_t)MS_BLOCK_FREE);
 836
 837                 for (i = 0; i <= count; ++i) {
 838                         if ((i < count) && MS_OBJ_ALLOCED (MS_BLOCK_OBJ (block, i), block)) {
 839                                 if (start < 0)
 840                                         start = i;
 841                         } else {
 842                                 if (start >= 0) {
 843                                         sgen_dump_occupied (MS_BLOCK_OBJ (block, start), MS_BLOCK_OBJ (block, i), MS_BLOCK_FOR_BLOCK_INFO (block));
 844                                         start = -1;
 845                                 }
 846                         }
 847                 }
 848
 849                 fprintf (heap_dump_file, "</section>\n");
 850         } END_FOREACH_BLOCK;
 851 }
 852
 853 #define LOAD_VTABLE     SGEN_LOAD_VTABLE
 854
 855 #ifdef SGEN_MARK_ON_ENQUEUE
 856 #define MS_MARK_OBJECT_AND_ENQUEUE_CHECKED(obj,desc,block,queue) do {   \
 857                 int __word, __bit;                                      \
 858                 MS_CALC_MARK_BIT (__word, __bit, (obj));                \
 859                 if (!MS_MARK_BIT ((block), __word, __bit) && MS_OBJ_ALLOCED ((obj), (block))) { \
 860                         MS_SET_MARK_BIT ((block), __word, __bit);       \
 861                         if (sgen_gc_descr_has_references (desc))                        \
 862                                 GRAY_OBJECT_ENQUEUE ((queue), (obj), (desc)); \
 863                         binary_protocol_mark ((obj), (gpointer)LOAD_VTABLE ((obj)), sgen_safe_object_get_size ((MonoObject*)(obj))); \
 864                         INC_NUM_MAJOR_OBJECTS_MARKED ();                \
 865                 }                                                       \
 866         } while (0)
 867 #define MS_MARK_OBJECT_AND_ENQUEUE(obj,desc,block,queue) do {           \
 868                 int __word, __bit;                                      \
 869                 MS_CALC_MARK_BIT (__word, __bit, (obj));                \
 870                 SGEN_ASSERT (9, MS_OBJ_ALLOCED ((obj), (block)), "object %p not allocated", obj); \
 871                 if (!MS_MARK_BIT ((block), __word, __bit)) {            \
 872                         MS_SET_MARK_BIT ((block), __word, __bit);       \
 873                         if (sgen_gc_descr_has_references (desc))                        \
 874                                 GRAY_OBJECT_ENQUEUE ((queue), (obj), (desc)); \
 875                         binary_protocol_mark ((obj), (gpointer)LOAD_VTABLE ((obj)), sgen_safe_object_get_size ((MonoObject*)(obj))); \
 876                         INC_NUM_MAJOR_OBJECTS_MARKED ();                \
 877                 }                                                       \
 878         } while (0)
 879 #else
 880 #define MS_MARK_OBJECT_AND_ENQUEUE_CHECKED(obj,desc,block,queue) do {   \
 881                 int __word, __bit;                                      \
 882                 SGEN_ASSERT (9, sgen_get_current_collection_generation () == GENERATION_OLD, "Can't majorly enqueue objects when doing minor collection"); \
 883                 MS_CALC_MARK_BIT (__word, __bit, (obj));                \
 884                 if (MS_OBJ_ALLOCED ((obj), (block))) { \
 885                         if (sgen_gc_descr_has_references (desc)) {                                              \
 886                                 GRAY_OBJECT_ENQUEUE ((queue), (obj), (desc)); \
 887                         } else {                                        \
 888                                 MS_SET_MARK_BIT ((block), __word, __bit); \
 889                                 binary_protocol_mark ((obj), (gpointer)LOAD_VTABLE ((obj)), sgen_safe_object_get_size ((MonoObject*)(obj))); \
 890                         }                                               \
 891                         INC_NUM_MAJOR_OBJECTS_MARKED ();                \
 892                 }                                                       \
 893         } while (0)
 894 #define MS_MARK_OBJECT_AND_ENQUEUE(obj,desc,block,queue) do {           \
 895                 int __word, __bit;                                      \
 896                 SGEN_ASSERT (9, sgen_get_current_collection_generation () == GENERATION_OLD, "Can't majorly enqueue objects when doing minor collection"); \
 897                 MS_CALC_MARK_BIT (__word, __bit, (obj));                \
 898                 SGEN_ASSERT (9, MS_OBJ_ALLOCED ((obj), (block)), "object %p not allocated", obj);       \
 899                 {               \
 900                         if (sgen_gc_descr_has_references (desc)) {                      \
 901                                 GRAY_OBJECT_ENQUEUE ((queue), (obj), (desc)); \
 902                         } else {                                        \
 903                                 MS_SET_MARK_BIT ((block), __word, __bit); \
 904                                 binary_protocol_mark ((obj), (gpointer)LOAD_VTABLE ((obj)), sgen_safe_object_get_size ((MonoObject*)(obj))); \
 905                         }                                               \
 906                         INC_NUM_MAJOR_OBJECTS_MARKED ();                \
 907                 }                                                       \
 908         } while (0)
 909 #endif
 910
 911 static void
 912 pin_major_object (char *obj, SgenGrayQueue *queue)
 913 {
 914         MSBlockInfo *block;
 915
 916 #ifdef SGEN_HAVE_CONCURRENT_MARK
 917         if (concurrent_mark)
 918                 g_assert_not_reached ();
 919 #endif
 920
 921         block = MS_BLOCK_FOR_OBJ (obj);
 922         block->has_pinned = TRUE;
 923         MS_MARK_OBJECT_AND_ENQUEUE (obj, sgen_obj_get_descriptor (obj), block, queue);
 924 }
 925
 926 #include "sgen-major-copy-object.h"
 927
 928 #ifdef SGEN_HAVE_CONCURRENT_MARK
 929 static void
 930 major_copy_or_mark_object_with_evacuation_concurrent (void **ptr, void *obj, SgenGrayQueue *queue)
 931 {
 932         SGEN_ASSERT (9, sgen_concurrent_collection_in_progress (), "Why are we scanning concurrently when there's no concurrent collection on?");
 933         SGEN_ASSERT (9, !sgen_workers_are_working () || sgen_is_worker_thread (mono_native_thread_id_get ()), "We must not scan from two threads at the same time!");
 934
 935         g_assert (!SGEN_OBJECT_IS_FORWARDED (obj));
 936
 937         if (!sgen_ptr_in_nursery (obj)) {
 938                 mword objsize;
 939
 940                 objsize = SGEN_ALIGN_UP (sgen_safe_object_get_size ((MonoObject*)obj));
 941
 942                 if (objsize <= SGEN_MAX_SMALL_OBJ_SIZE) {
 943                         MSBlockInfo *block = MS_BLOCK_FOR_OBJ (obj);
 944                         MS_MARK_OBJECT_AND_ENQUEUE (obj, sgen_obj_get_descriptor (obj), block, queue);
 945                 } else {
 946                         if (sgen_los_object_is_pinned (obj))
 947                                 return;
 948
 949 #ifdef ENABLE_DTRACE
 950                         if (G_UNLIKELY (MONO_GC_OBJ_PINNED_ENABLED ())) {
 951                                 MonoVTable *vt = (MonoVTable*)SGEN_LOAD_VTABLE (obj);
 952                                 MONO_GC_OBJ_PINNED ((mword)obj, sgen_safe_object_get_size (obj), vt->klass->name_space, vt->klass->name, GENERATION_OLD);
 953                         }
 954 #endif
 955
 956                         sgen_los_pin_object (obj);
 957                         if (SGEN_OBJECT_HAS_REFERENCES (obj))
 958                                 GRAY_OBJECT_ENQUEUE (queue, obj, sgen_obj_get_descriptor (obj));
 959                         INC_NUM_MAJOR_OBJECTS_MARKED ();
 960                 }
 961         }
 962 }
 963 #endif
 964
 965 static long long
 966 major_get_and_reset_num_major_objects_marked (void)
 967 {
 968 #ifdef SGEN_COUNT_NUMBER_OF_MAJOR_OBJECTS_MARKED
 969         long long num = num_major_objects_marked;
 970         num_major_objects_marked = 0;
 971         return num;
 972 #else
 973         return 0;
 974 #endif
 975 }
 976
 977 #define USE_PREFETCH_QUEUE      0       /* BOOL FASTENABLE */
 978 #if !USE_PREFETCH_QUEUE
 979 #undef USE_PREFETCH_QUEUE
 980 #endif
 981
 982 #define DESCRIPTOR_FAST_PATH    1       /* BOOL FASTENABLE */
 983 #if !DESCRIPTOR_FAST_PATH
 984 #undef DESCRIPTOR_FAST_PATH
 985 #endif
 986
 987 #ifdef HEAVY_STATISTICS
 988 static long long stat_optimized_copy;
 989 static long long stat_optimized_copy_nursery;
 990 static long long stat_optimized_copy_nursery_forwarded;
 991 static long long stat_optimized_copy_nursery_pinned;
 992 #ifdef SGEN_MARK_ON_ENQUEUE
 993 static long long stat_optimized_copy_major;
 994 static long long stat_optimized_copy_major_small_fast;
 995 static long long stat_optimized_copy_major_small_slow;
 996 static long long stat_optimized_copy_major_large;
 997 #endif
 998 static long long stat_optimized_copy_major_forwarded;
 999 static long long stat_optimized_copy_major_small_evacuate;
1000 static long long stat_optimized_major_scan;
1001 static long long stat_optimized_major_scan_no_refs;
1002 #ifdef DESCRIPTOR_FAST_PATH
1003 static long long stat_optimized_major_scan_fast;
1004 static long long stat_optimized_major_scan_slow;
1005 #endif
1006
1007 static long long stat_drain_prefetch_fills;
1008 static long long stat_drain_prefetch_fill_failures;
1009 static long long stat_drain_loops;
1010 #endif
1011
1012 static inline void
1013 sgen_gray_object_dequeue_fast (SgenGrayQueue *queue, char** obj, mword *desc) {
1014         GrayQueueEntry *cursor = queue->prefetch_cursor;
1015         GrayQueueEntry *const end = queue->prefetch + SGEN_GRAY_QUEUE_PREFETCH_SIZE;
1016         *obj = cursor->obj;
1017 #ifdef SGEN_GRAY_QUEUE_HAVE_DESCRIPTORS
1018         *desc = cursor->desc;
1019         GRAY_OBJECT_DEQUEUE (queue, &cursor->obj, &cursor->desc);
1020 #else
1021         GRAY_OBJECT_DEQUEUE (queue, &cursor->obj, NULL);
1022 #endif
1023
1024 #if !defined (SGEN_MARK_ON_ENQUEUE) && defined (BLOCK_INFO_IN_HEADER)
1025         {
1026                 int word, bit;
1027                 MSBlockInfo *block = (MSBlockInfo*)MS_BLOCK_DATA_FOR_OBJ (cursor->obj);
1028                 MS_CALC_MARK_BIT (word, bit, cursor->obj);
1029                 PREFETCH_WRITE (&block->mark_words [word]);
1030         }
1031 #endif
1032
1033         PREFETCH_READ (cursor->obj);
1034         ++cursor;
1035         if (cursor == end)
1036                 cursor = queue->prefetch;
1037         queue->prefetch_cursor = cursor;
1038 }
1039
1040 static void major_scan_object_with_evacuation (char *start, mword desc, SgenGrayQueue *queue);
1041
1042 #define COPY_OR_MARK_FUNCTION_NAME      major_copy_or_mark_object_no_evacuation
1043 #define SCAN_OBJECT_FUNCTION_NAME       major_scan_object_no_evacuation
1044 #define DRAIN_GRAY_STACK_FUNCTION_NAME  drain_gray_stack_no_evacuation
1045 #include "sgen-marksweep-drain-gray-stack.h"
1046
1047 #define COPY_OR_MARK_WITH_EVACUATION
1048 #define COPY_OR_MARK_FUNCTION_NAME      major_copy_or_mark_object_with_evacuation
1049 #define SCAN_OBJECT_FUNCTION_NAME       major_scan_object_with_evacuation
1050 #define DRAIN_GRAY_STACK_FUNCTION_NAME  drain_gray_stack_with_evacuation
1051 #include "sgen-marksweep-drain-gray-stack.h"
1052
1053 static gboolean
1054 drain_gray_stack (ScanCopyContext ctx)
1055 {
1056         gboolean evacuation = FALSE;
1057         int i;
1058         for (i = 0; i < num_block_obj_sizes; ++i) {
1059                 if (evacuate_block_obj_sizes [i]) {
1060                         evacuation = TRUE;
1061                         break;
1062                 }
1063         }
1064
1065         if (evacuation)
1066                 return drain_gray_stack_with_evacuation (ctx);
1067         else
1068                 return drain_gray_stack_no_evacuation (ctx);
1069 }
1070
1071 #ifdef SGEN_HAVE_CONCURRENT_MARK
1072 #include "sgen-marksweep-scan-object-concurrent.h"
1073 #endif
1074
1075 static void
1076 major_copy_or_mark_object_canonical (void **ptr, SgenGrayQueue *queue)
1077 {
1078         major_copy_or_mark_object_with_evacuation (ptr, *ptr, queue);
1079 }
1080
1081 #ifdef SGEN_HAVE_CONCURRENT_MARK
1082 static void
1083 major_copy_or_mark_object_concurrent_canonical (void **ptr, SgenGrayQueue *queue)
1084 {
1085         major_copy_or_mark_object_with_evacuation_concurrent (ptr, *ptr, queue);
1086 }
1087 #endif
1088
1089 static void
1090 mark_pinned_objects_in_block (MSBlockInfo *block, SgenGrayQueue *queue)
1091 {
1092         void **entry, **end;
1093         int last_index = -1;
1094
1095         if (block->pin_queue_first_entry == block->pin_queue_last_entry)
1096                 return;
1097
1098         block->has_pinned = TRUE;
1099
1100         entry = sgen_pinning_get_entry (block->pin_queue_first_entry);
1101         end = sgen_pinning_get_entry (block->pin_queue_last_entry);
1102
1103         for (; entry < end; ++entry) {
1104                 int index = MS_BLOCK_OBJ_INDEX (*entry, block);
1105                 char *obj;
1106                 SGEN_ASSERT (9, index >= 0 && index < MS_BLOCK_FREE / block->obj_size, "invalid object %p index %d max-index %d", *entry, index, MS_BLOCK_FREE / block->obj_size);
1107                 if (index == last_index)
1108                         continue;
1109                 obj = MS_BLOCK_OBJ (block, index);
1110                 MS_MARK_OBJECT_AND_ENQUEUE_CHECKED (obj, sgen_obj_get_descriptor (obj), block, queue);
1111                 last_index = index;
1112         }
1113 }
1114
1115 static inline void
1116 sweep_block_for_size (MSBlockInfo *block, int count, int obj_size)
1117 {
1118         int obj_index;
1119
1120         for (obj_index = 0; obj_index < count; ++obj_index) {
1121                 int word, bit;
1122                 void *obj = MS_BLOCK_OBJ_FOR_SIZE (block, obj_index, obj_size);
1123
1124                 MS_CALC_MARK_BIT (word, bit, obj);
1125                 if (MS_MARK_BIT (block, word, bit)) {
1126                         SGEN_ASSERT (9, MS_OBJ_ALLOCED (obj, block), "object %p not allocated", obj);
1127                 } else {
1128                         /* an unmarked object */
1129                         if (MS_OBJ_ALLOCED (obj, block)) {
1130                                 /*
1131                                  * FIXME: Merge consecutive
1132                                  * slots for lower reporting
1133                                  * overhead.  Maybe memset
1134                                  * will also benefit?
1135                                  */
1136                                 binary_protocol_empty (obj, obj_size);
1137                                 MONO_GC_MAJOR_SWEPT ((mword)obj, obj_size);
1138                                 memset (obj, 0, obj_size);
1139                         }
1140                         *(void**)obj = block->free_list;
1141                         block->free_list = obj;
1142                 }
1143         }
1144 }
1145
1146 /*
1147  * sweep_block:
1148  *
1149  *   Traverse BLOCK, freeing and zeroing unused objects.
1150  */
1151 static void
1152 sweep_block (MSBlockInfo *block, gboolean during_major_collection)
1153 {
1154         int count;
1155         void *reversed = NULL;
1156
1157         if (!during_major_collection)
1158                 g_assert (!sgen_concurrent_collection_in_progress ());
1159
1160         if (block->swept)
1161                 return;
1162
1163         count = MS_BLOCK_FREE / block->obj_size;
1164
1165         block->free_list = NULL;
1166
1167         /* Use inline instances specialized to constant sizes, this allows the compiler to replace the memset calls with inline code */
1168         // FIXME: Add more sizes
1169         switch (block->obj_size) {
1170         case 16:
1171                 sweep_block_for_size (block, count, 16);
1172                 break;
1173         default:
1174                 sweep_block_for_size (block, count, block->obj_size);
1175                 break;
1176         }
1177
1178         /* reset mark bits */
1179         memset (block->mark_words, 0, sizeof (mword) * MS_NUM_MARK_WORDS);
1180
1181         /* Reverse free list so that it's in address order */
1182         reversed = NULL;
1183         while (block->free_list) {
1184                 void *next = *(void**)block->free_list;
1185                 *(void**)block->free_list = reversed;
1186                 reversed = block->free_list;
1187                 block->free_list = next;
1188         }
1189         block->free_list = reversed;
1190
1191         block->swept = 1;
1192 }
1193
1194 static inline int
1195 bitcount (mword d)
1196 {
1197         int count = 0;
1198
1199 #ifdef __GNUC__
1200         if (sizeof (mword) == sizeof (unsigned long))
1201                 count += __builtin_popcountl (d);
1202         else
1203                 count += __builtin_popcount (d);
1204 #else
1205         while (d) {
1206                 count ++;
1207                 d &= (d - 1);
1208         }
1209 #endif
1210         return count;
1211 }
1212
1213 static void
1214 ms_sweep (void)
1215 {
1216         int i;
1217         MSBlockInfo *block;
1218
1219         /* statistics for evacuation */
1220         int *slots_available = alloca (sizeof (int) * num_block_obj_sizes);
1221         int *slots_used = alloca (sizeof (int) * num_block_obj_sizes);
1222         int *num_blocks = alloca (sizeof (int) * num_block_obj_sizes);
1223
1224 #ifdef SGEN_HAVE_CONCURRENT_MARK
1225         mword total_evacuate_heap = 0;
1226         mword total_evacuate_saved = 0;
1227 #endif
1228
1229         for (i = 0; i < num_block_obj_sizes; ++i)
1230                 slots_available [i] = slots_used [i] = num_blocks [i] = 0;
1231
1232         /* clear all the free lists */
1233         for (i = 0; i < MS_BLOCK_TYPE_MAX; ++i) {
1234                 MSBlockInfo **free_blocks = free_block_lists [i];
1235                 int j;
1236                 for (j = 0; j < num_block_obj_sizes; ++j)
1237                         free_blocks [j] = NULL;
1238         }
1239
1240         /* traverse all blocks, free and zero unmarked objects */
1241         FOREACH_BLOCK (block) {
1242                 int count;
1243                 gboolean have_live = FALSE;
1244                 gboolean has_pinned;
1245                 gboolean have_free = FALSE;
1246                 int obj_size_index;
1247                 int nused = 0;
1248
1249                 obj_size_index = block->obj_size_index;
1250
1251                 has_pinned = block->has_pinned;
1252                 block->has_pinned = block->pinned;
1253
1254                 block->is_to_space = FALSE;
1255                 block->swept = 0;
1256
1257                 count = MS_BLOCK_FREE / block->obj_size;
1258
1259 #ifdef SGEN_HAVE_CONCURRENT_MARK
1260                 if (block->cardtable_mod_union) {
1261                         sgen_free_internal_dynamic (block->cardtable_mod_union, CARDS_PER_BLOCK, INTERNAL_MEM_CARDTABLE_MOD_UNION);
1262                         block->cardtable_mod_union = NULL;
1263                 }
1264 #endif
1265
1266                 /* Count marked objects in the block */
1267                 for (i = 0; i < MS_NUM_MARK_WORDS; ++i) {
1268                         nused += bitcount (block->mark_words [i]);
1269                 }
1270                 if (nused) {
1271                         have_live = TRUE;
1272                 }
1273                 if (nused < count)
1274                         have_free = TRUE;
1275
1276                 if (!lazy_sweep)
1277                         sweep_block (block, TRUE);
1278
1279                 if (have_live) {
1280                         if (!has_pinned) {
1281                                 ++num_blocks [obj_size_index];
1282                                 slots_used [obj_size_index] += nused;
1283                                 slots_available [obj_size_index] += count;
1284                         }
1285
1286                         /*
1287                          * If there are free slots in the block, add
1288                          * the block to the corresponding free list.
1289                          */
1290                         if (have_free) {
1291                                 MSBlockInfo **free_blocks = FREE_BLOCKS (block->pinned, block->has_references);
1292                                 int index = MS_BLOCK_OBJ_SIZE_INDEX (block->obj_size);
1293                                 block->next_free = free_blocks [index];
1294                                 free_blocks [index] = block;
1295                         }
1296
1297                         update_heap_boundaries_for_block (block);
1298                 } else {
1299                         /*
1300                          * Blocks without live objects are removed from the
1301                          * block list and freed.
1302                          */
1303                         DELETE_BLOCK_IN_FOREACH ();
1304
1305                         binary_protocol_empty (MS_BLOCK_OBJ (block, 0), (char*)MS_BLOCK_OBJ (block, count) - (char*)MS_BLOCK_OBJ (block, 0));
1306 #if defined (FIXED_HEAP) || defined (BLOCK_INFO_IN_HEADER)
1307                         ms_free_block (block);
1308 #else
1309                         ms_free_block (block->block);
1310                         sgen_free_internal (block, INTERNAL_MEM_MS_BLOCK_INFO);
1311 #endif
1312
1313                         --num_major_sections;
1314                 }
1315         } END_FOREACH_BLOCK;
1316         sgen_pointer_queue_remove_nulls (&allocated_blocks);
1317
1318         for (i = 0; i < num_block_obj_sizes; ++i) {
1319                 float usage = (float)slots_used [i] / (float)slots_available [i];
1320                 if (num_blocks [i] > 5 && usage < evacuation_threshold) {
1321                         evacuate_block_obj_sizes [i] = TRUE;
1322                         /*
1323                         g_print ("slot size %d - %d of %d used\n",
1324                                         block_obj_sizes [i], slots_used [i], slots_available [i]);
1325                         */
1326                 } else {
1327                         evacuate_block_obj_sizes [i] = FALSE;
1328                 }
1329 #ifdef SGEN_HAVE_CONCURRENT_MARK
1330                 {
1331                         mword total_bytes = block_obj_sizes [i] * slots_available [i];
1332                         total_evacuate_heap += total_bytes;
1333                         if (evacuate_block_obj_sizes [i])
1334                                 total_evacuate_saved += total_bytes - block_obj_sizes [i] * slots_used [i];
1335                 }
1336 #endif
1337         }
1338
1339 #ifdef SGEN_HAVE_CONCURRENT_MARK
1340         want_evacuation = (float)total_evacuate_saved / (float)total_evacuate_heap > (1 - concurrent_evacuation_threshold);
1341 #endif
1342
1343         have_swept = TRUE;
1344 }
1345
1346 static void
1347 major_sweep (void)
1348 {
1349         ms_sweep ();
1350 }
1351
1352 static int count_pinned_ref;
1353 static int count_pinned_nonref;
1354 static int count_nonpinned_ref;
1355 static int count_nonpinned_nonref;
1356
1357 static void
1358 count_nonpinned_callback (char *obj, size_t size, void *data)
1359 {
1360         MonoVTable *vtable = (MonoVTable*)LOAD_VTABLE (obj);
1361
1362         if (vtable->klass->has_references)
1363                 ++count_nonpinned_ref;
1364         else
1365                 ++count_nonpinned_nonref;
1366 }
1367
1368 static void
1369 count_pinned_callback (char *obj, size_t size, void *data)
1370 {
1371         MonoVTable *vtable = (MonoVTable*)LOAD_VTABLE (obj);
1372
1373         if (vtable->klass->has_references)
1374                 ++count_pinned_ref;
1375         else
1376                 ++count_pinned_nonref;
1377 }
1378
1379 static G_GNUC_UNUSED void
1380 count_ref_nonref_objs (void)
1381 {
1382         int total;
1383
1384         count_pinned_ref = 0;
1385         count_pinned_nonref = 0;
1386         count_nonpinned_ref = 0;
1387         count_nonpinned_nonref = 0;
1388
1389         major_iterate_objects (ITERATE_OBJECTS_SWEEP_NON_PINNED, count_nonpinned_callback, NULL);
1390         major_iterate_objects (ITERATE_OBJECTS_SWEEP_PINNED, count_pinned_callback, NULL);
1391
1392         total = count_pinned_nonref + count_nonpinned_nonref + count_pinned_ref + count_nonpinned_ref;
1393
1394         g_print ("ref: %d pinned %d non-pinned   non-ref: %d pinned %d non-pinned  --  %.1f\n",
1395                         count_pinned_ref, count_nonpinned_ref,
1396                         count_pinned_nonref, count_nonpinned_nonref,
1397                         (count_pinned_nonref + count_nonpinned_nonref) * 100.0 / total);
1398 }
1399
1400 static int
1401 ms_calculate_block_obj_sizes (double factor, int *arr)
1402 {
1403         double target_size = sizeof (MonoObject);
1404         int num_sizes = 0;
1405         int last_size = 0;
1406
1407         do {
1408                 int target_count = (int)ceil (MS_BLOCK_FREE / target_size);
1409                 int size = MIN ((MS_BLOCK_FREE / target_count) & ~(SGEN_ALLOC_ALIGN - 1), SGEN_MAX_SMALL_OBJ_SIZE);
1410
1411                 if (size != last_size) {
1412                         if (arr)
1413                                 arr [num_sizes] = size;
1414                         ++num_sizes;
1415                         last_size = size;
1416                 }
1417
1418                 target_size *= factor;
1419         } while (last_size < SGEN_MAX_SMALL_OBJ_SIZE);
1420
1421         return num_sizes;
1422 }
1423
1424 /* only valid during minor collections */
1425 static mword old_num_major_sections;
1426
1427 static void
1428 major_start_nursery_collection (void)
1429 {
1430 #ifdef MARKSWEEP_CONSISTENCY_CHECK
1431         consistency_check ();
1432 #endif
1433
1434         old_num_major_sections = num_major_sections;
1435 }
1436
1437 static void
1438 major_finish_nursery_collection (void)
1439 {
1440 #ifdef MARKSWEEP_CONSISTENCY_CHECK
1441         consistency_check ();
1442 #endif
1443         sgen_register_major_sections_alloced (num_major_sections - old_num_major_sections);
1444 }
1445
1446 static void
1447 major_start_major_collection (void)
1448 {
1449         int i;
1450
1451         /* clear the free lists */
1452         for (i = 0; i < num_block_obj_sizes; ++i) {
1453                 if (!evacuate_block_obj_sizes [i])
1454                         continue;
1455
1456                 free_block_lists [0][i] = NULL;
1457                 free_block_lists [MS_BLOCK_FLAG_REFS][i] = NULL;
1458         }
1459
1460         // Sweep all unswept blocks
1461         if (lazy_sweep) {
1462                 MSBlockInfo *block;
1463
1464                 MONO_GC_SWEEP_BEGIN (GENERATION_OLD, TRUE);
1465
1466                 FOREACH_BLOCK (block) {
1467                         sweep_block (block, TRUE);
1468                 } END_FOREACH_BLOCK;
1469
1470                 MONO_GC_SWEEP_END (GENERATION_OLD, TRUE);
1471         }
1472 }
1473
1474 static void
1475 major_finish_major_collection (ScannedObjectCounts *counts)
1476 {
1477 #ifdef SGEN_HEAVY_BINARY_PROTOCOL
1478         if (binary_protocol_is_enabled ()) {
1479                 counts->num_scanned_objects = scanned_objects_list.next_slot;
1480
1481                 sgen_pointer_queue_sort_uniq (&scanned_objects_list);
1482                 counts->num_unique_scanned_objects = scanned_objects_list.next_slot;
1483
1484                 sgen_pointer_queue_clear (&scanned_objects_list);
1485         }
1486 #endif
1487 }
1488
1489 #if SIZEOF_VOID_P != 8
1490 static int
1491 compare_pointers (const void *va, const void *vb) {
1492         char *a = *(char**)va, *b = *(char**)vb;
1493         if (a < b)
1494                 return -1;
1495         if (a > b)
1496                 return 1;
1497         return 0;
1498 }
1499 #endif
1500
1501 static void
1502 major_have_computer_minor_collection_allowance (void)
1503 {
1504         size_t section_reserve = sgen_get_minor_collection_allowance () / MS_BLOCK_SIZE;
1505
1506         g_assert (have_swept);
1507
1508 #if SIZEOF_VOID_P != 8
1509         {
1510                 int i, num_empty_blocks_orig, num_blocks, arr_length;
1511                 void *block;
1512                 void **empty_block_arr;
1513                 void **rebuild_next;
1514
1515 #ifdef TARGET_WIN32
1516                 /*
1517                  * sgen_free_os_memory () asserts in mono_vfree () because windows doesn't like freeing the middle of
1518                  * a VirtualAlloc ()-ed block.
1519                  */
1520                 return;
1521 #endif
1522
1523                 if (num_empty_blocks <= section_reserve)
1524                         return;
1525                 SGEN_ASSERT (0, num_empty_blocks > 0, "section reserve can't be negative");
1526
1527                 num_empty_blocks_orig = num_empty_blocks;
1528                 empty_block_arr = (void**)sgen_alloc_internal_dynamic (sizeof (void*) * num_empty_blocks_orig,
1529                                 INTERNAL_MEM_MS_BLOCK_INFO_SORT, FALSE);
1530                 if (!empty_block_arr)
1531                         goto fallback;
1532
1533                 i = 0;
1534                 for (block = empty_blocks; block; block = *(void**)block)
1535                         empty_block_arr [i++] = block;
1536                 SGEN_ASSERT (0, i == num_empty_blocks, "empty block count wrong");
1537
1538                 sgen_qsort (empty_block_arr, num_empty_blocks, sizeof (void*), compare_pointers);
1539
1540                 /*
1541                  * We iterate over the free blocks, trying to find MS_BLOCK_ALLOC_NUM
1542                  * contiguous ones.  If we do, we free them.  If that's not enough to get to
1543                  * section_reserve, we halve the number of contiguous blocks we're looking
1544                  * for and have another go, until we're done with looking for pairs of
1545                  * blocks, at which point we give up and go to the fallback.
1546                  */
1547                 arr_length = num_empty_blocks_orig;
1548                 num_blocks = MS_BLOCK_ALLOC_NUM;
1549                 while (num_empty_blocks > section_reserve && num_blocks > 1) {
1550                         int first = -1;
1551                         int dest = 0;
1552
1553                         dest = 0;
1554                         for (i = 0; i < arr_length; ++i) {
1555                                 int d = dest;
1556                                 void *block = empty_block_arr [i];
1557                                 SGEN_ASSERT (0, block, "we're not shifting correctly");
1558                                 if (i != dest) {
1559                                         empty_block_arr [dest] = block;
1560                                         /*
1561                                          * This is not strictly necessary, but we're
1562                                          * cautious.
1563                                          */
1564                                         empty_block_arr [i] = NULL;
1565                                 }
1566                                 ++dest;
1567
1568                                 if (first < 0) {
1569                                         first = d;
1570                                         continue;
1571                                 }
1572
1573                                 SGEN_ASSERT (0, first >= 0 && d > first, "algorithm is wrong");
1574
1575                                 if ((char*)block != ((char*)empty_block_arr [d-1]) + MS_BLOCK_SIZE) {
1576                                         first = d;
1577                                         continue;
1578                                 }
1579
1580                                 if (d + 1 - first == num_blocks) {
1581                                         /*
1582                                          * We found num_blocks contiguous blocks.  Free them
1583                                          * and null their array entries.  As an optimization
1584                                          * we could, instead of nulling the entries, shift
1585                                          * the following entries over to the left, while
1586                                          * we're iterating.
1587                                          */
1588                                         int j;
1589                                         sgen_free_os_memory (empty_block_arr [first], MS_BLOCK_SIZE * num_blocks, SGEN_ALLOC_HEAP);
1590                                         for (j = first; j <= d; ++j)
1591                                                 empty_block_arr [j] = NULL;
1592                                         dest = first;
1593                                         first = -1;
1594
1595                                         num_empty_blocks -= num_blocks;
1596
1597                                         stat_major_blocks_freed += num_blocks;
1598                                         if (num_blocks == MS_BLOCK_ALLOC_NUM)
1599                                                 stat_major_blocks_freed_ideal += num_blocks;
1600                                         else
1601                                                 stat_major_blocks_freed_less_ideal += num_blocks;
1602
1603                                 }
1604                         }
1605
1606                         SGEN_ASSERT (0, dest <= i && dest <= arr_length, "array length is off");
1607                         arr_length = dest;
1608                         SGEN_ASSERT (0, arr_length == num_empty_blocks, "array length is off");
1609
1610                         num_blocks >>= 1;
1611                 }
1612
1613                 /* rebuild empty_blocks free list */
1614                 rebuild_next = (void**)&empty_blocks;
1615                 for (i = 0; i < arr_length; ++i) {
1616                         void *block = empty_block_arr [i];
1617                         SGEN_ASSERT (0, block, "we're missing blocks");
1618                         *rebuild_next = block;
1619                         rebuild_next = (void**)block;
1620                 }
1621                 *rebuild_next = NULL;
1622
1623                 /* free array */
1624                 sgen_free_internal_dynamic (empty_block_arr, sizeof (void*) * num_empty_blocks_orig, INTERNAL_MEM_MS_BLOCK_INFO_SORT);
1625         }
1626
1627         SGEN_ASSERT (0, num_empty_blocks >= 0, "we freed more blocks than we had in the first place?");
1628
1629  fallback:
1630         /*
1631          * This is our threshold.  If there's not more empty than used blocks, we won't
1632          * release uncontiguous blocks, in fear of fragmenting the address space.
1633          */
1634         if (num_empty_blocks <= num_major_sections)
1635                 return;
1636 #endif
1637
1638         while (num_empty_blocks > section_reserve) {
1639                 void *next = *(void**)empty_blocks;
1640                 sgen_free_os_memory (empty_blocks, MS_BLOCK_SIZE, SGEN_ALLOC_HEAP);
1641                 empty_blocks = next;
1642                 /*
1643                  * Needs not be atomic because this is running
1644                  * single-threaded.
1645                  */
1646                 --num_empty_blocks;
1647
1648                 ++stat_major_blocks_freed;
1649 #if SIZEOF_VOID_P != 8
1650                 ++stat_major_blocks_freed_individual;
1651 #endif
1652         }
1653 }
1654
1655 static void
1656 major_find_pin_queue_start_ends (SgenGrayQueue *queue)
1657 {
1658         MSBlockInfo *block;
1659
1660         FOREACH_BLOCK (block) {
1661                 sgen_find_optimized_pin_queue_area (MS_BLOCK_FOR_BLOCK_INFO (block) + MS_BLOCK_SKIP, MS_BLOCK_FOR_BLOCK_INFO (block) + MS_BLOCK_SIZE,
1662                                 &block->pin_queue_first_entry, &block->pin_queue_last_entry);
1663         } END_FOREACH_BLOCK;
1664 }
1665
1666 static void
1667 major_pin_objects (SgenGrayQueue *queue)
1668 {
1669         MSBlockInfo *block;
1670
1671         FOREACH_BLOCK (block) {
1672                 mark_pinned_objects_in_block (block, queue);
1673         } END_FOREACH_BLOCK;
1674 }
1675
1676 static void
1677 major_init_to_space (void)
1678 {
1679 }
1680
1681 static void
1682 major_report_pinned_memory_usage (void)
1683 {
1684         g_assert_not_reached ();
1685 }
1686
1687 static gint64
1688 major_get_used_size (void)
1689 {
1690         gint64 size = 0;
1691         MSBlockInfo *block;
1692
1693         FOREACH_BLOCK (block) {
1694                 int count = MS_BLOCK_FREE / block->obj_size;
1695                 void **iter;
1696                 size += count * block->obj_size;
1697                 for (iter = block->free_list; iter; iter = (void**)*iter)
1698                         size -= block->obj_size;
1699         } END_FOREACH_BLOCK;
1700
1701         return size;
1702 }
1703
1704 static size_t
1705 get_num_major_sections (void)
1706 {
1707         return num_major_sections;
1708 }
1709
1710 static gboolean
1711 major_handle_gc_param (const char *opt)
1712 {
1713         if (g_str_has_prefix (opt, "evacuation-threshold=")) {
1714                 const char *arg = strchr (opt, '=') + 1;
1715                 int percentage = atoi (arg);
1716                 if (percentage < 0 || percentage > 100) {
1717                         fprintf (stderr, "evacuation-threshold must be an integer in the range 0-100.\n");
1718                         exit (1);
1719                 }
1720                 evacuation_threshold = (float)percentage / 100.0f;
1721                 return TRUE;
1722         } else if (!strcmp (opt, "lazy-sweep")) {
1723                 lazy_sweep = TRUE;
1724                 return TRUE;
1725         } else if (!strcmp (opt, "no-lazy-sweep")) {
1726                 lazy_sweep = FALSE;
1727                 return TRUE;
1728         }
1729
1730         return FALSE;
1731 }
1732
1733 static void
1734 major_print_gc_param_usage (void)
1735 {
1736         fprintf (stderr,
1737                         ""
1738                         "  evacuation-threshold=P (where P is a percentage, an integer in 0-100)\n"
1739                         "  (no-)lazy-sweep\n"
1740                         );
1741 }
1742
1743 static void
1744 major_iterate_live_block_ranges (sgen_cardtable_block_callback callback)
1745 {
1746         MSBlockInfo *block;
1747         gboolean has_references;
1748
1749         FOREACH_BLOCK_HAS_REFERENCES (block, has_references) {
1750                 if (has_references)
1751                         callback ((mword)MS_BLOCK_FOR_BLOCK_INFO (block), MS_BLOCK_SIZE);
1752         } END_FOREACH_BLOCK;
1753 }
1754
1755 #ifdef HEAVY_STATISTICS
1756 extern long long marked_cards;
1757 extern long long scanned_cards;
1758 extern long long scanned_objects;
1759 extern long long remarked_cards;
1760 #endif
1761
1762 #define CARD_WORDS_PER_BLOCK (CARDS_PER_BLOCK / SIZEOF_VOID_P)
1763 /*
1764  * MS blocks are 16K aligned.
1765  * Cardtables are 4K aligned, at least.
1766  * This means that the cardtable of a given block is 32 bytes aligned.
1767  */
1768 static guint8*
1769 initial_skip_card (guint8 *card_data)
1770 {
1771         mword *cards = (mword*)card_data;
1772         mword card;
1773         int i;
1774         for (i = 0; i < CARD_WORDS_PER_BLOCK; ++i) {
1775                 card = cards [i];
1776                 if (card)
1777                         break;
1778         }
1779
1780         if (i == CARD_WORDS_PER_BLOCK)
1781                 return card_data + CARDS_PER_BLOCK;
1782
1783 #if defined(__i386__) && defined(__GNUC__)
1784         return card_data + i * 4 +  (__builtin_ffs (card) - 1) / 8;
1785 #elif defined(__x86_64__) && defined(__GNUC__)
1786         return card_data + i * 8 +  (__builtin_ffsll (card) - 1) / 8;
1787 #elif defined(__s390x__) && defined(__GNUC__)
1788         return card_data + i * 8 +  (__builtin_ffsll (GUINT64_TO_LE(card)) - 1) / 8;
1789 #else
1790         for (i = i * SIZEOF_VOID_P; i < CARDS_PER_BLOCK; ++i) {
1791                 if (card_data [i])
1792                         return &card_data [i];
1793         }
1794         return card_data;
1795 #endif
1796 }
1797
1798
1799 static G_GNUC_UNUSED guint8*
1800 skip_card (guint8 *card_data, guint8 *card_data_end)
1801 {
1802         while (card_data < card_data_end && !*card_data)
1803                 ++card_data;
1804         return card_data;
1805 }
1806
1807 #define MS_BLOCK_OBJ_INDEX_FAST(o,b,os) (((char*)(o) - ((b) + MS_BLOCK_SKIP)) / (os))
1808 #define MS_BLOCK_OBJ_FAST(b,os,i)                       ((b) + MS_BLOCK_SKIP + (os) * (i))
1809 #define MS_OBJ_ALLOCED_FAST(o,b)                (*(void**)(o) && (*(char**)(o) < (b) || *(char**)(o) >= (b) + MS_BLOCK_SIZE))
1810
1811 static void
1812 major_scan_card_table (gboolean mod_union, SgenGrayQueue *queue)
1813 {
1814         MSBlockInfo *block;
1815         gboolean has_references;
1816         ScanObjectFunc scan_func = sgen_get_current_object_ops ()->scan_object;
1817
1818 #ifdef SGEN_HAVE_CONCURRENT_MARK
1819         if (!concurrent_mark)
1820                 g_assert (!mod_union);
1821 #else
1822         g_assert (!mod_union);
1823 #endif
1824
1825         FOREACH_BLOCK_HAS_REFERENCES (block, has_references) {
1826                 int block_obj_size;
1827                 char *block_start;
1828
1829                 if (!has_references)
1830                         continue;
1831
1832                 block_obj_size = block->obj_size;
1833                 block_start = MS_BLOCK_FOR_BLOCK_INFO (block);
1834
1835                 if (block_obj_size >= CARD_SIZE_IN_BYTES) {
1836                         guint8 *cards;
1837 #ifndef SGEN_HAVE_OVERLAPPING_CARDS
1838                         guint8 cards_data [CARDS_PER_BLOCK];
1839 #endif
1840                         char *obj, *end, *base;
1841
1842                         if (mod_union) {
1843 #ifdef SGEN_HAVE_CONCURRENT_MARK
1844                                 cards = block->cardtable_mod_union;
1845                                 /*
1846                                  * This happens when the nursery
1847                                  * collection that precedes finishing
1848                                  * the concurrent collection allocates
1849                                  * new major blocks.
1850                                  */
1851                                 if (!cards)
1852                                         continue;
1853 #endif
1854                         } else {
1855                         /*We can avoid the extra copy since the remark cardtable was cleaned before */
1856 #ifdef SGEN_HAVE_OVERLAPPING_CARDS
1857                                 cards = sgen_card_table_get_card_scan_address ((mword)block_start);
1858 #else
1859                                 cards = cards_data;
1860                                 if (!sgen_card_table_get_card_data (cards_data, (mword)block_start, CARDS_PER_BLOCK))
1861                                         continue;
1862 #endif
1863                         }
1864
1865                         obj = (char*)MS_BLOCK_OBJ_FAST (block_start, block_obj_size, 0);
1866                         end = block_start + MS_BLOCK_SIZE;
1867                         base = sgen_card_table_align_pointer (obj);
1868
1869                         while (obj < end) {
1870                                 size_t card_offset;
1871
1872                                 if (!block->swept)
1873                                         sweep_block (block, FALSE);
1874
1875                                 if (!MS_OBJ_ALLOCED_FAST (obj, block_start))
1876                                         goto next_large;
1877
1878                                 if (mod_union) {
1879                                         /* FIXME: do this more efficiently */
1880                                         int w, b;
1881                                         MS_CALC_MARK_BIT (w, b, obj);
1882                                         if (!MS_MARK_BIT (block, w, b))
1883                                                 goto next_large;
1884                                 }
1885
1886                                 card_offset = (obj - base) >> CARD_BITS;
1887                                 sgen_cardtable_scan_object (obj, block_obj_size, cards + card_offset, mod_union, queue);
1888
1889                         next_large:
1890                                 obj += block_obj_size;
1891                         }
1892                 } else {
1893                         guint8 *card_data, *card_base;
1894                         guint8 *card_data_end;
1895
1896                         /*
1897                          * This is safe in face of card aliasing for the following reason:
1898                          *
1899                          * Major blocks are 16k aligned, or 32 cards aligned.
1900                          * Cards aliasing happens in powers of two, so as long as major blocks are aligned to their
1901                          * sizes, they won't overflow the cardtable overlap modulus.
1902                          */
1903                         if (mod_union) {
1904 #ifdef SGEN_HAVE_CONCURRENT_MARK
1905                                 card_data = card_base = block->cardtable_mod_union;
1906                                 /*
1907                                  * This happens when the nursery
1908                                  * collection that precedes finishing
1909                                  * the concurrent collection allocates
1910                                  * new major blocks.
1911                                  */
1912                                 if (!card_data)
1913                                         continue;
1914 #else
1915                                 g_assert_not_reached ();
1916                                 card_data = NULL;
1917 #endif
1918                         } else {
1919                                 card_data = card_base = sgen_card_table_get_card_scan_address ((mword)block_start);
1920                         }
1921                         card_data_end = card_data + CARDS_PER_BLOCK;
1922
1923                         for (card_data = initial_skip_card (card_data); card_data < card_data_end; ++card_data) { //card_data = skip_card (card_data + 1, card_data_end)) {
1924                                 size_t index;
1925                                 size_t idx = card_data - card_base;
1926                                 char *start = (char*)(block_start + idx * CARD_SIZE_IN_BYTES);
1927                                 char *end = start + CARD_SIZE_IN_BYTES;
1928                                 char *first_obj, *obj;
1929
1930                                 HEAVY_STAT (++scanned_cards);
1931
1932                                 if (!*card_data)
1933                                         continue;
1934
1935                                 if (!block->swept)
1936                                         sweep_block (block, FALSE);
1937
1938                                 HEAVY_STAT (++marked_cards);
1939
1940                                 sgen_card_table_prepare_card_for_scanning (card_data);
1941
1942                                 if (idx == 0)
1943                                         index = 0;
1944                                 else
1945                                         index = MS_BLOCK_OBJ_INDEX_FAST (start, block_start, block_obj_size);
1946
1947                                 obj = first_obj = (char*)MS_BLOCK_OBJ_FAST (block_start, block_obj_size, index);
1948                                 while (obj < end) {
1949                                         if (!MS_OBJ_ALLOCED_FAST (obj, block_start))
1950                                                 goto next_small;
1951
1952                                         if (mod_union) {
1953                                                 /* FIXME: do this more efficiently */
1954                                                 int w, b;
1955                                                 MS_CALC_MARK_BIT (w, b, obj);
1956                                                 if (!MS_MARK_BIT (block, w, b))
1957                                                         goto next_small;
1958                                         }
1959
1960                                         HEAVY_STAT (++scanned_objects);
1961                                         scan_func (obj, sgen_obj_get_descriptor (obj), queue);
1962                                 next_small:
1963                                         obj += block_obj_size;
1964                                 }
1965                                 HEAVY_STAT (if (*card_data) ++remarked_cards);
1966                                 binary_protocol_card_scan (first_obj, obj - first_obj);
1967                         }
1968                 }
1969         } END_FOREACH_BLOCK;
1970 }
1971
1972 static void
1973 major_count_cards (long long *num_total_cards, long long *num_marked_cards)
1974 {
1975         MSBlockInfo *block;
1976         gboolean has_references;
1977         long long total_cards = 0;
1978         long long marked_cards = 0;
1979
1980         FOREACH_BLOCK_HAS_REFERENCES (block, has_references) {
1981                 guint8 *cards = sgen_card_table_get_card_scan_address ((mword) MS_BLOCK_FOR_BLOCK_INFO (block));
1982                 int i;
1983
1984                 if (!has_references)
1985                         continue;
1986
1987                 total_cards += CARDS_PER_BLOCK;
1988                 for (i = 0; i < CARDS_PER_BLOCK; ++i) {
1989                         if (cards [i])
1990                                 ++marked_cards;
1991                 }
1992         } END_FOREACH_BLOCK;
1993
1994         *num_total_cards = total_cards;
1995         *num_marked_cards = marked_cards;
1996 }
1997
1998 #ifdef SGEN_HAVE_CONCURRENT_MARK
1999 static void
2000 update_cardtable_mod_union (void)
2001 {
2002         MSBlockInfo *block;
2003
2004         FOREACH_BLOCK (block) {
2005                 size_t num_cards;
2006
2007                 block->cardtable_mod_union = sgen_card_table_update_mod_union (block->cardtable_mod_union,
2008                                 MS_BLOCK_FOR_BLOCK_INFO (block), MS_BLOCK_SIZE, &num_cards);
2009
2010                 SGEN_ASSERT (0, num_cards == CARDS_PER_BLOCK, "Number of cards calculation is wrong");
2011         } END_FOREACH_BLOCK;
2012 }
2013
2014 static guint8*
2015 major_get_cardtable_mod_union_for_object (char *obj)
2016 {
2017         MSBlockInfo *block = MS_BLOCK_FOR_OBJ (obj);
2018         return &block->cardtable_mod_union [(obj - (char*)sgen_card_table_align_pointer (MS_BLOCK_FOR_BLOCK_INFO (block))) >> CARD_BITS];
2019 }
2020 #endif
2021
2022 static void
2023 alloc_free_block_lists (MSBlockInfo ***lists)
2024 {
2025         int i;
2026         for (i = 0; i < MS_BLOCK_TYPE_MAX; ++i)
2027                 lists [i] = sgen_alloc_internal_dynamic (sizeof (MSBlockInfo*) * num_block_obj_sizes, INTERNAL_MEM_MS_TABLES, TRUE);
2028 }
2029
2030 #undef pthread_create
2031
2032 static void
2033 post_param_init (SgenMajorCollector *collector)
2034 {
2035         collector->sweeps_lazily = lazy_sweep;
2036 }
2037
2038 #ifdef SGEN_HAVE_CONCURRENT_MARK
2039 static void
2040 sgen_marksweep_init_internal (SgenMajorCollector *collector, gboolean is_concurrent)
2041 #else // SGEN_HAVE_CONCURRENT_MARK
2042 #error unknown configuration
2043 #endif // SGEN_HAVE_CONCURRENT_MARK
2044 {
2045         int i;
2046
2047         sgen_register_fixed_internal_mem_type (INTERNAL_MEM_MS_BLOCK_INFO, sizeof (MSBlockInfo));
2048
2049         num_block_obj_sizes = ms_calculate_block_obj_sizes (MS_BLOCK_OBJ_SIZE_FACTOR, NULL);
2050         block_obj_sizes = sgen_alloc_internal_dynamic (sizeof (int) * num_block_obj_sizes, INTERNAL_MEM_MS_TABLES, TRUE);
2051         ms_calculate_block_obj_sizes (MS_BLOCK_OBJ_SIZE_FACTOR, block_obj_sizes);
2052
2053         evacuate_block_obj_sizes = sgen_alloc_internal_dynamic (sizeof (gboolean) * num_block_obj_sizes, INTERNAL_MEM_MS_TABLES, TRUE);
2054         for (i = 0; i < num_block_obj_sizes; ++i)
2055                 evacuate_block_obj_sizes [i] = FALSE;
2056
2057         /*
2058         {
2059                 int i;
2060                 g_print ("block object sizes:\n");
2061                 for (i = 0; i < num_block_obj_sizes; ++i)
2062                         g_print ("%d\n", block_obj_sizes [i]);
2063         }
2064         */
2065
2066         alloc_free_block_lists (free_block_lists);
2067
2068         for (i = 0; i < MS_NUM_FAST_BLOCK_OBJ_SIZE_INDEXES; ++i)
2069                 fast_block_obj_size_indexes [i] = ms_find_block_obj_size_index (i * 8);
2070         for (i = 0; i < MS_NUM_FAST_BLOCK_OBJ_SIZE_INDEXES * 8; ++i)
2071                 g_assert (MS_BLOCK_OBJ_SIZE_INDEX (i) == ms_find_block_obj_size_index (i));
2072
2073         mono_counters_register ("# major blocks allocated", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_major_blocks_alloced);
2074         mono_counters_register ("# major blocks freed", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_major_blocks_freed);
2075         mono_counters_register ("# major blocks lazy swept", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_major_blocks_lazy_swept);
2076         mono_counters_register ("# major objects evacuated", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_major_objects_evacuated);
2077 #if SIZEOF_VOID_P != 8
2078         mono_counters_register ("# major blocks freed ideally", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_major_blocks_freed_ideal);
2079         mono_counters_register ("# major blocks freed less ideally", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_major_blocks_freed_less_ideal);
2080         mono_counters_register ("# major blocks freed individually", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_major_blocks_freed_individual);
2081         mono_counters_register ("# major blocks allocated less ideally", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_major_blocks_alloced_less_ideal);
2082 #endif
2083
2084         collector->section_size = MAJOR_SECTION_SIZE;
2085
2086 #ifdef SGEN_HAVE_CONCURRENT_MARK
2087         concurrent_mark = is_concurrent;
2088         if (is_concurrent) {
2089                 collector->is_concurrent = TRUE;
2090                 collector->want_synchronous_collection = &want_evacuation;
2091         } else
2092 #endif
2093         {
2094                 collector->is_concurrent = FALSE;
2095                 collector->want_synchronous_collection = NULL;
2096         }
2097         collector->get_and_reset_num_major_objects_marked = major_get_and_reset_num_major_objects_marked;
2098         collector->supports_cardtable = TRUE;
2099
2100         collector->have_swept = &have_swept;
2101
2102         collector->alloc_heap = major_alloc_heap;
2103         collector->is_object_live = major_is_object_live;
2104         collector->alloc_small_pinned_obj = major_alloc_small_pinned_obj;
2105         collector->alloc_degraded = major_alloc_degraded;
2106
2107         collector->alloc_object = major_alloc_object;
2108         collector->free_pinned_object = free_pinned_object;
2109         collector->iterate_objects = major_iterate_objects;
2110         collector->free_non_pinned_object = major_free_non_pinned_object;
2111         collector->find_pin_queue_start_ends = major_find_pin_queue_start_ends;
2112         collector->pin_objects = major_pin_objects;
2113         collector->pin_major_object = pin_major_object;
2114         collector->scan_card_table = major_scan_card_table;
2115         collector->iterate_live_block_ranges = (void*)(void*) major_iterate_live_block_ranges;
2116 #ifdef SGEN_HAVE_CONCURRENT_MARK
2117         if (is_concurrent) {
2118                 collector->update_cardtable_mod_union = update_cardtable_mod_union;
2119                 collector->get_cardtable_mod_union_for_object = major_get_cardtable_mod_union_for_object;
2120         }
2121 #endif
2122         collector->init_to_space = major_init_to_space;
2123         collector->sweep = major_sweep;
2124         collector->check_scan_starts = major_check_scan_starts;
2125         collector->dump_heap = major_dump_heap;
2126         collector->get_used_size = major_get_used_size;
2127         collector->start_nursery_collection = major_start_nursery_collection;
2128         collector->finish_nursery_collection = major_finish_nursery_collection;
2129         collector->start_major_collection = major_start_major_collection;
2130         collector->finish_major_collection = major_finish_major_collection;
2131         collector->have_computed_minor_collection_allowance = major_have_computer_minor_collection_allowance;
2132         collector->ptr_is_in_non_pinned_space = major_ptr_is_in_non_pinned_space;
2133         collector->obj_is_from_pinned_alloc = obj_is_from_pinned_alloc;
2134         collector->report_pinned_memory_usage = major_report_pinned_memory_usage;
2135         collector->get_num_major_sections = get_num_major_sections;
2136         collector->handle_gc_param = major_handle_gc_param;
2137         collector->print_gc_param_usage = major_print_gc_param_usage;
2138         collector->post_param_init = post_param_init;
2139         collector->is_valid_object = major_is_valid_object;
2140         collector->describe_pointer = major_describe_pointer;
2141         collector->count_cards = major_count_cards;
2142
2143         collector->major_ops.copy_or_mark_object = major_copy_or_mark_object_canonical;
2144         collector->major_ops.scan_object = major_scan_object_with_evacuation;
2145 #ifdef SGEN_HAVE_CONCURRENT_MARK
2146         if (is_concurrent) {
2147                 collector->major_concurrent_ops.copy_or_mark_object = major_copy_or_mark_object_concurrent_canonical;
2148                 collector->major_concurrent_ops.scan_object = major_scan_object_concurrent;
2149                 collector->major_concurrent_ops.scan_vtype = major_scan_vtype_concurrent;
2150         }
2151 #endif
2152
2153 #if !defined (FIXED_HEAP) && !defined (SGEN_PARALLEL_MARK)
2154         /* FIXME: this will not work with evacuation or the split nursery. */
2155         if (!is_concurrent)
2156                 collector->drain_gray_stack = drain_gray_stack;
2157
2158 #ifdef HEAVY_STATISTICS
2159         mono_counters_register ("Optimized copy", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_optimized_copy);
2160         mono_counters_register ("Optimized copy nursery", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_optimized_copy_nursery);
2161         mono_counters_register ("Optimized copy nursery forwarded", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_optimized_copy_nursery_forwarded);
2162         mono_counters_register ("Optimized copy nursery pinned", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_optimized_copy_nursery_pinned);
2163 #ifdef SGEN_MARK_ON_ENQUEUE
2164         mono_counters_register ("Optimized copy major", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_optimized_copy_major);
2165         mono_counters_register ("Optimized copy major small fast", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_optimized_copy_major_small_fast);
2166         mono_counters_register ("Optimized copy major small slow", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_optimized_copy_major_small_slow);
2167         mono_counters_register ("Optimized copy major large", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_optimized_copy_major_large);
2168 #endif
2169         mono_counters_register ("Optimized major scan", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_optimized_major_scan);
2170         mono_counters_register ("Optimized major scan no refs", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_optimized_major_scan_no_refs);
2171 #ifdef DESCRIPTOR_FAST_PATH
2172         mono_counters_register ("Optimized major scan slow", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_optimized_major_scan_slow);
2173         mono_counters_register ("Optimized major scan fast", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_optimized_major_scan_fast);
2174 #endif
2175
2176         mono_counters_register ("Gray stack drain loops", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_drain_loops);
2177         mono_counters_register ("Gray stack prefetch fills", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_drain_prefetch_fills);
2178         mono_counters_register ("Gray stack prefetch failures", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_drain_prefetch_fill_failures);
2179 #endif
2180 #endif
2181
2182 #ifdef SGEN_HEAVY_BINARY_PROTOCOL
2183         mono_mutex_init (&scanned_objects_list_lock);
2184 #endif
2185
2186         SGEN_ASSERT (0, SGEN_MAX_SMALL_OBJ_SIZE <= MS_BLOCK_FREE / 2, "MAX_SMALL_OBJ_SIZE must be at most MS_BLOCK_FREE / 2");
2187
2188         /*cardtable requires major pages to be 8 cards aligned*/
2189         g_assert ((MS_BLOCK_SIZE % (8 * CARD_SIZE_IN_BYTES)) == 0);
2190 }
2191
2192 #ifdef SGEN_HAVE_CONCURRENT_MARK
2193 void
2194 sgen_marksweep_init (SgenMajorCollector *collector)
2195 {
2196         sgen_marksweep_init_internal (collector, FALSE);
2197 }
2198
2199 void
2200 sgen_marksweep_conc_init (SgenMajorCollector *collector)
2201 {
2202         sgen_marksweep_init_internal (collector, TRUE);
2203 }
2204 #endif
2205
2206 #endif