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