mono/sgen/sgen-gc.c

   1 /*
   2  * sgen-gc.c: Simple generational GC.
   3  *
   4  * Author:
   5  *      Paolo Molaro (lupus@ximian.com)
   6  *  Rodrigo Kumpera (kumpera@gmail.com)
   7  *
   8  * Copyright 2005-2011 Novell, Inc (http://www.novell.com)
   9  * Copyright 2011 Xamarin Inc (http://www.xamarin.com)
  10  *
  11  * Thread start/stop adapted from Boehm's GC:
  12  * Copyright (c) 1994 by Xerox Corporation.  All rights reserved.
  13  * Copyright (c) 1996 by Silicon Graphics.  All rights reserved.
  14  * Copyright (c) 1998 by Fergus Henderson.  All rights reserved.
  15  * Copyright (c) 2000-2004 by Hewlett-Packard Company.  All rights reserved.
  16  * Copyright 2001-2003 Ximian, Inc
  17  * Copyright 2003-2010 Novell, Inc.
  18  * Copyright 2011 Xamarin, Inc.
  19  * Copyright (C) 2012 Xamarin Inc
  20  *
  21  * Licensed under the MIT license. See LICENSE file in the project root for full license information.
  22  *
  23  * Important: allocation provides always zeroed memory, having to do
  24  * a memset after allocation is deadly for performance.
  25  * Memory usage at startup is currently as follows:
  26  * 64 KB pinned space
  27  * 64 KB internal space
  28  * size of nursery
  29  * We should provide a small memory config with half the sizes
  30  *
  31  * We currently try to make as few mono assumptions as possible:
  32  * 1) 2-word header with no GC pointers in it (first vtable, second to store the
  33  *    forwarding ptr)
  34  * 2) gc descriptor is the second word in the vtable (first word in the class)
  35  * 3) 8 byte alignment is the minimum and enough (not true for special structures (SIMD), FIXME)
  36  * 4) there is a function to get an object's size and the number of
  37  *    elements in an array.
  38  * 5) we know the special way bounds are allocated for complex arrays
  39  * 6) we know about proxies and how to treat them when domains are unloaded
  40  *
  41  * Always try to keep stack usage to a minimum: no recursive behaviour
  42  * and no large stack allocs.
  43  *
  44  * General description.
  45  * Objects are initially allocated in a nursery using a fast bump-pointer technique.
  46  * When the nursery is full we start a nursery collection: this is performed with a
  47  * copying GC.
  48  * When the old generation is full we start a copying GC of the old generation as well:
  49  * this will be changed to mark&sweep with copying when fragmentation becomes to severe
  50  * in the future.  Maybe we'll even do both during the same collection like IMMIX.
  51  *
  52  * The things that complicate this description are:
  53  * *) pinned objects: we can't move them so we need to keep track of them
  54  * *) no precise info of the thread stacks and registers: we need to be able to
  55  *    quickly find the objects that may be referenced conservatively and pin them
  56  *    (this makes the first issues more important)
  57  * *) large objects are too expensive to be dealt with using copying GC: we handle them
  58  *    with mark/sweep during major collections
  59  * *) some objects need to not move even if they are small (interned strings, Type handles):
  60  *    we use mark/sweep for them, too: they are not allocated in the nursery, but inside
  61  *    PinnedChunks regions
  62  */
  63
  64 /*
  65  * TODO:
  66
  67  *) we could have a function pointer in MonoClass to implement
  68   customized write barriers for value types
  69
  70  *) investigate the stuff needed to advance a thread to a GC-safe
  71   point (single-stepping, read from unmapped memory etc) and implement it.
  72   This would enable us to inline allocations and write barriers, for example,
  73   or at least parts of them, like the write barrier checks.
  74   We may need this also for handling precise info on stacks, even simple things
  75   as having uninitialized data on the stack and having to wait for the prolog
  76   to zero it. Not an issue for the last frame that we scan conservatively.
  77   We could always not trust the value in the slots anyway.
  78
  79  *) modify the jit to save info about references in stack locations:
  80   this can be done just for locals as a start, so that at least
  81   part of the stack is handled precisely.
  82
  83  *) test/fix endianess issues
  84
  85  *) Implement a card table as the write barrier instead of remembered
  86     sets?  Card tables are not easy to implement with our current
  87     memory layout.  We have several different kinds of major heap
  88     objects: Small objects in regular blocks, small objects in pinned
  89     chunks and LOS objects.  If we just have a pointer we have no way
  90     to tell which kind of object it points into, therefore we cannot
  91     know where its card table is.  The least we have to do to make
  92     this happen is to get rid of write barriers for indirect stores.
  93     (See next item)
  94
  95  *) Get rid of write barriers for indirect stores.  We can do this by
  96     telling the GC to wbarrier-register an object once we do an ldloca
  97     or ldelema on it, and to unregister it once it's not used anymore
  98     (it can only travel downwards on the stack).  The problem with
  99     unregistering is that it needs to happen eventually no matter
 100     what, even if exceptions are thrown, the thread aborts, etc.
 101     Rodrigo suggested that we could do only the registering part and
 102     let the collector find out (pessimistically) when it's safe to
 103     unregister, namely when the stack pointer of the thread that
 104     registered the object is higher than it was when the registering
 105     happened.  This might make for a good first implementation to get
 106     some data on performance.
 107
 108  *) Some sort of blacklist support?  Blacklists is a concept from the
 109     Boehm GC: if during a conservative scan we find pointers to an
 110     area which we might use as heap, we mark that area as unusable, so
 111     pointer retention by random pinning pointers is reduced.
 112
 113  *) experiment with max small object size (very small right now - 2kb,
 114     because it's tied to the max freelist size)
 115
 116   *) add an option to mmap the whole heap in one chunk: it makes for many
 117      simplifications in the checks (put the nursery at the top and just use a single
 118      check for inclusion/exclusion): the issue this has is that on 32 bit systems it's
 119      not flexible (too much of the address space may be used by default or we can't
 120      increase the heap as needed) and we'd need a race-free mechanism to return memory
 121      back to the system (mprotect(PROT_NONE) will still keep the memory allocated if it
 122      was written to, munmap is needed, but the following mmap may not find the same segment
 123      free...)
 124
 125  *) memzero the major fragments after restarting the world and optionally a smaller
 126     chunk at a time
 127
 128  *) investigate having fragment zeroing threads
 129
 130  *) separate locks for finalization and other minor stuff to reduce
 131     lock contention
 132
 133  *) try a different copying order to improve memory locality
 134
 135  *) a thread abort after a store but before the write barrier will
 136     prevent the write barrier from executing
 137
 138  *) specialized dynamically generated markers/copiers
 139
 140  *) Dynamically adjust TLAB size to the number of threads.  If we have
 141     too many threads that do allocation, we might need smaller TLABs,
 142     and we might get better performance with larger TLABs if we only
 143     have a handful of threads.  We could sum up the space left in all
 144     assigned TLABs and if that's more than some percentage of the
 145     nursery size, reduce the TLAB size.
 146
 147  *) Explore placing unreachable objects on unused nursery memory.
 148         Instead of memset'ng a region to zero, place an int[] covering it.
 149         A good place to start is add_nursery_frag. The tricky thing here is
 150         placing those objects atomically outside of a collection.
 151
 152  *) Allocation should use asymmetric Dekker synchronization:
 153         http://blogs.oracle.com/dave/resource/Asymmetric-Dekker-Synchronization.txt
 154         This should help weak consistency archs.
 155  */
 156 #include "config.h"
 157 #ifdef HAVE_SGEN_GC
 158
 159 #ifdef __MACH__
 160 #undef _XOPEN_SOURCE
 161 #define _XOPEN_SOURCE
 162 #define _DARWIN_C_SOURCE
 163 #endif
 164
 165 #ifdef HAVE_UNISTD_H
 166 #include <unistd.h>
 167 #endif
 168 #ifdef HAVE_PTHREAD_H
 169 #include <pthread.h>
 170 #endif
 171 #ifdef HAVE_PTHREAD_NP_H
 172 #include <pthread_np.h>
 173 #endif
 174 #include <stdio.h>
 175 #include <string.h>
 176 #include <errno.h>
 177 #include <assert.h>
 178 #include <stdlib.h>
 179
 180 #include "mono/sgen/sgen-gc.h"
 181 #include "mono/sgen/sgen-cardtable.h"
 182 #include "mono/sgen/sgen-protocol.h"
 183 #include "mono/sgen/sgen-memory-governor.h"
 184 #include "mono/sgen/sgen-hash-table.h"
 185 #include "mono/sgen/sgen-cardtable.h"
 186 #include "mono/sgen/sgen-pinning.h"
 187 #include "mono/sgen/sgen-workers.h"
 188 #include "mono/sgen/sgen-client.h"
 189 #include "mono/sgen/sgen-pointer-queue.h"
 190 #include "mono/sgen/gc-internal-agnostic.h"
 191 #include "mono/utils/mono-proclib.h"
 192 #include "mono/utils/mono-memory-model.h"
 193 #include "mono/utils/hazard-pointer.h"
 194
 195 #include <mono/utils/memcheck.h>
 196
 197 #undef pthread_create
 198 #undef pthread_join
 199 #undef pthread_detach
 200
 201 /*
 202  * ######################################################################
 203  * ########  Types and constants used by the GC.
 204  * ######################################################################
 205  */
 206
 207 /* 0 means not initialized, 1 is initialized, -1 means in progress */
 208 static int gc_initialized = 0;
 209 /* If set, check if we need to do something every X allocations */
 210 gboolean has_per_allocation_action;
 211 /* If set, do a heap check every X allocation */
 212 guint32 verify_before_allocs = 0;
 213 /* If set, do a minor collection before every X allocation */
 214 guint32 collect_before_allocs = 0;
 215 /* If set, do a whole heap check before each collection */
 216 static gboolean whole_heap_check_before_collection = FALSE;
 217 /* If set, do a heap consistency check before each minor collection */
 218 static gboolean consistency_check_at_minor_collection = FALSE;
 219 /* If set, do a mod union consistency check before each finishing collection pause */
 220 static gboolean mod_union_consistency_check = FALSE;
 221 /* If set, check whether mark bits are consistent after major collections */
 222 static gboolean check_mark_bits_after_major_collection = FALSE;
 223 /* If set, check that all nursery objects are pinned/not pinned, depending on context */
 224 static gboolean check_nursery_objects_pinned = FALSE;
 225 /* If set, do a few checks when the concurrent collector is used */
 226 static gboolean do_concurrent_checks = FALSE;
 227 /* If set, do a plausibility check on the scan_starts before and after
 228    each collection */
 229 static gboolean do_scan_starts_check = FALSE;
 230
 231 static gboolean disable_minor_collections = FALSE;
 232 static gboolean disable_major_collections = FALSE;
 233 static gboolean do_verify_nursery = FALSE;
 234 static gboolean do_dump_nursery_content = FALSE;
 235 static gboolean enable_nursery_canaries = FALSE;
 236
 237 static gboolean precleaning_enabled = TRUE;
 238
 239 #ifdef HEAVY_STATISTICS
 240 guint64 stat_objects_alloced_degraded = 0;
 241 guint64 stat_bytes_alloced_degraded = 0;
 242
 243 guint64 stat_copy_object_called_nursery = 0;
 244 guint64 stat_objects_copied_nursery = 0;
 245 guint64 stat_copy_object_called_major = 0;
 246 guint64 stat_objects_copied_major = 0;
 247
 248 guint64 stat_scan_object_called_nursery = 0;
 249 guint64 stat_scan_object_called_major = 0;
 250
 251 guint64 stat_slots_allocated_in_vain;
 252
 253 guint64 stat_nursery_copy_object_failed_from_space = 0;
 254 guint64 stat_nursery_copy_object_failed_forwarded = 0;
 255 guint64 stat_nursery_copy_object_failed_pinned = 0;
 256 guint64 stat_nursery_copy_object_failed_to_space = 0;
 257
 258 static guint64 stat_wbarrier_add_to_global_remset = 0;
 259 static guint64 stat_wbarrier_arrayref_copy = 0;
 260 static guint64 stat_wbarrier_generic_store = 0;
 261 static guint64 stat_wbarrier_generic_store_atomic = 0;
 262 static guint64 stat_wbarrier_set_root = 0;
 263 #endif
 264
 265 static guint64 stat_pinned_objects = 0;
 266
 267 static guint64 time_minor_pre_collection_fragment_clear = 0;
 268 static guint64 time_minor_pinning = 0;
 269 static guint64 time_minor_scan_remsets = 0;
 270 static guint64 time_minor_scan_pinned = 0;
 271 static guint64 time_minor_scan_roots = 0;
 272 static guint64 time_minor_finish_gray_stack = 0;
 273 static guint64 time_minor_fragment_creation = 0;
 274
 275 static guint64 time_major_pre_collection_fragment_clear = 0;
 276 static guint64 time_major_pinning = 0;
 277 static guint64 time_major_scan_pinned = 0;
 278 static guint64 time_major_scan_roots = 0;
 279 static guint64 time_major_scan_mod_union = 0;
 280 static guint64 time_major_finish_gray_stack = 0;
 281 static guint64 time_major_free_bigobjs = 0;
 282 static guint64 time_major_los_sweep = 0;
 283 static guint64 time_major_sweep = 0;
 284 static guint64 time_major_fragment_creation = 0;
 285
 286 static guint64 time_max = 0;
 287
 288 static SGEN_TV_DECLARE (time_major_conc_collection_start);
 289 static SGEN_TV_DECLARE (time_major_conc_collection_end);
 290
 291 static SGEN_TV_DECLARE (last_minor_collection_start_tv);
 292 static SGEN_TV_DECLARE (last_minor_collection_end_tv);
 293
 294 int gc_debug_level = 0;
 295 FILE* gc_debug_file;
 296
 297 /*
 298 void
 299 mono_gc_flush_info (void)
 300 {
 301         fflush (gc_debug_file);
 302 }
 303 */
 304
 305 #define TV_DECLARE SGEN_TV_DECLARE
 306 #define TV_GETTIME SGEN_TV_GETTIME
 307 #define TV_ELAPSED SGEN_TV_ELAPSED
 308
 309 static SGEN_TV_DECLARE (sgen_init_timestamp);
 310
 311 NurseryClearPolicy nursery_clear_policy = CLEAR_AT_TLAB_CREATION;
 312
 313 #define object_is_forwarded     SGEN_OBJECT_IS_FORWARDED
 314 #define object_is_pinned        SGEN_OBJECT_IS_PINNED
 315 #define pin_object              SGEN_PIN_OBJECT
 316
 317 #define ptr_in_nursery sgen_ptr_in_nursery
 318
 319 #define LOAD_VTABLE     SGEN_LOAD_VTABLE
 320
 321 gboolean
 322 nursery_canaries_enabled (void)
 323 {
 324         return enable_nursery_canaries;
 325 }
 326
 327 #define safe_object_get_size    sgen_safe_object_get_size
 328
 329 /*
 330  * ######################################################################
 331  * ########  Global data.
 332  * ######################################################################
 333  */
 334 MonoCoopMutex gc_mutex;
 335
 336 #define SCAN_START_SIZE SGEN_SCAN_START_SIZE
 337
 338 size_t degraded_mode = 0;
 339
 340 static mword bytes_pinned_from_failed_allocation = 0;
 341
 342 GCMemSection *nursery_section = NULL;
 343 static volatile mword lowest_heap_address = ~(mword)0;
 344 static volatile mword highest_heap_address = 0;
 345
 346 MonoCoopMutex sgen_interruption_mutex;
 347
 348 int current_collection_generation = -1;
 349 static volatile gboolean concurrent_collection_in_progress = FALSE;
 350
 351 /* objects that are ready to be finalized */
 352 static SgenPointerQueue fin_ready_queue = SGEN_POINTER_QUEUE_INIT (INTERNAL_MEM_FINALIZE_READY);
 353 static SgenPointerQueue critical_fin_queue = SGEN_POINTER_QUEUE_INIT (INTERNAL_MEM_FINALIZE_READY);
 354
 355 /* registered roots: the key to the hash is the root start address */
 356 /*
 357  * Different kinds of roots are kept separate to speed up pin_from_roots () for example.
 358  */
 359 SgenHashTable roots_hash [ROOT_TYPE_NUM] = {
 360         SGEN_HASH_TABLE_INIT (INTERNAL_MEM_ROOTS_TABLE, INTERNAL_MEM_ROOT_RECORD, sizeof (RootRecord), sgen_aligned_addr_hash, NULL),
 361         SGEN_HASH_TABLE_INIT (INTERNAL_MEM_ROOTS_TABLE, INTERNAL_MEM_ROOT_RECORD, sizeof (RootRecord), sgen_aligned_addr_hash, NULL),
 362         SGEN_HASH_TABLE_INIT (INTERNAL_MEM_ROOTS_TABLE, INTERNAL_MEM_ROOT_RECORD, sizeof (RootRecord), sgen_aligned_addr_hash, NULL)
 363 };
 364 static mword roots_size = 0; /* amount of memory in the root set */
 365
 366 /* The size of a TLAB */
 367 /* The bigger the value, the less often we have to go to the slow path to allocate a new
 368  * one, but the more space is wasted by threads not allocating much memory.
 369  * FIXME: Tune this.
 370  * FIXME: Make this self-tuning for each thread.
 371  */
 372 guint32 tlab_size = (1024 * 4);
 373
 374 #define MAX_SMALL_OBJ_SIZE      SGEN_MAX_SMALL_OBJ_SIZE
 375
 376 #define ALLOC_ALIGN             SGEN_ALLOC_ALIGN
 377
 378 #define ALIGN_UP                SGEN_ALIGN_UP
 379
 380 #ifdef SGEN_DEBUG_INTERNAL_ALLOC
 381 MonoNativeThreadId main_gc_thread = NULL;
 382 #endif
 383
 384 /*Object was pinned during the current collection*/
 385 static mword objects_pinned;
 386
 387 /*
 388  * ######################################################################
 389  * ########  Macros and function declarations.
 390  * ######################################################################
 391  */
 392
 393 typedef SgenGrayQueue GrayQueue;
 394
 395 /* forward declarations */
 396 static void scan_from_registered_roots (char *addr_start, char *addr_end, int root_type, ScanCopyContext ctx);
 397
 398 static void pin_from_roots (void *start_nursery, void *end_nursery, ScanCopyContext ctx);
 399 static void finish_gray_stack (int generation, ScanCopyContext ctx);
 400
 401
 402 SgenMajorCollector major_collector;
 403 SgenMinorCollector sgen_minor_collector;
 404 /* FIXME: get rid of this */
 405 static GrayQueue gray_queue;
 406
 407 static SgenRememberedSet remset;
 408
 409 /* The gray queue to use from the main collection thread. */
 410 #define WORKERS_DISTRIBUTE_GRAY_QUEUE   (&gray_queue)
 411
 412 /*
 413  * The gray queue a worker job must use.  If we're not parallel or
 414  * concurrent, we use the main gray queue.
 415  */
 416 static SgenGrayQueue*
 417 sgen_workers_get_job_gray_queue (WorkerData *worker_data)
 418 {
 419         return worker_data ? &worker_data->private_gray_queue : WORKERS_DISTRIBUTE_GRAY_QUEUE;
 420 }
 421
 422 static void
 423 gray_queue_redirect (SgenGrayQueue *queue)
 424 {
 425         gboolean wake = FALSE;
 426
 427         for (;;) {
 428                 GrayQueueSection *section = sgen_gray_object_dequeue_section (queue);
 429                 if (!section)
 430                         break;
 431                 sgen_section_gray_queue_enqueue ((SgenSectionGrayQueue *)queue->alloc_prepare_data, section);
 432                 wake = TRUE;
 433         }
 434
 435         if (wake) {
 436                 g_assert (concurrent_collection_in_progress);
 437                 sgen_workers_ensure_awake ();
 438         }
 439 }
 440
 441 static void
 442 gray_queue_enable_redirect (SgenGrayQueue *queue)
 443 {
 444         if (!concurrent_collection_in_progress)
 445                 return;
 446
 447         sgen_gray_queue_set_alloc_prepare (queue, gray_queue_redirect, sgen_workers_get_distribute_section_gray_queue ());
 448         gray_queue_redirect (queue);
 449 }
 450
 451 void
 452 sgen_scan_area_with_callback (char *start, char *end, IterateObjectCallbackFunc callback, void *data, gboolean allow_flags, gboolean fail_on_canaries)
 453 {
 454         while (start < end) {
 455                 size_t size;
 456                 char *obj;
 457
 458                 if (!*(void**)start) {
 459                         start += sizeof (void*); /* should be ALLOC_ALIGN, really */
 460                         continue;
 461                 }
 462
 463                 if (allow_flags) {
 464                         if (!(obj = (char *)SGEN_OBJECT_IS_FORWARDED (start)))
 465                                 obj = start;
 466                 } else {
 467                         obj = start;
 468                 }
 469
 470                 if (!sgen_client_object_is_array_fill ((GCObject*)obj)) {
 471                         CHECK_CANARY_FOR_OBJECT ((GCObject*)obj, fail_on_canaries);
 472                         size = ALIGN_UP (safe_object_get_size ((GCObject*)obj));
 473                         callback ((GCObject*)obj, size, data);
 474                         CANARIFY_SIZE (size);
 475                 } else {
 476                         size = ALIGN_UP (safe_object_get_size ((GCObject*)obj));
 477                 }
 478
 479                 start += size;
 480         }
 481 }
 482
 483 /*
 484  * sgen_add_to_global_remset:
 485  *
 486  *   The global remset contains locations which point into newspace after
 487  * a minor collection. This can happen if the objects they point to are pinned.
 488  *
 489  * LOCKING: If called from a parallel collector, the global remset
 490  * lock must be held.  For serial collectors that is not necessary.
 491  */
 492 void
 493 sgen_add_to_global_remset (gpointer ptr, GCObject *obj)
 494 {
 495         SGEN_ASSERT (5, sgen_ptr_in_nursery (obj), "Target pointer of global remset must be in the nursery");
 496
 497         HEAVY_STAT (++stat_wbarrier_add_to_global_remset);
 498
 499         if (!major_collector.is_concurrent) {
 500                 SGEN_ASSERT (5, current_collection_generation != -1, "Global remsets can only be added during collections");
 501         } else {
 502                 if (current_collection_generation == -1)
 503                         SGEN_ASSERT (5, sgen_concurrent_collection_in_progress (), "Global remsets outside of collection pauses can only be added by the concurrent collector");
 504         }
 505
 506         if (!object_is_pinned (obj))
 507                 SGEN_ASSERT (5, sgen_minor_collector.is_split || sgen_concurrent_collection_in_progress (), "Non-pinned objects can only remain in nursery if it is a split nursery");
 508         else if (sgen_cement_lookup_or_register (obj))
 509                 return;
 510
 511         remset.record_pointer (ptr);
 512
 513         sgen_pin_stats_register_global_remset (obj);
 514
 515         SGEN_LOG (8, "Adding global remset for %p", ptr);
 516         binary_protocol_global_remset (ptr, obj, (gpointer)SGEN_LOAD_VTABLE (obj));
 517 }
 518
 519 /*
 520  * sgen_drain_gray_stack:
 521  *
 522  *   Scan objects in the gray stack until the stack is empty. This should be called
 523  * frequently after each object is copied, to achieve better locality and cache
 524  * usage.
 525  *
 526  */
 527 gboolean
 528 sgen_drain_gray_stack (ScanCopyContext ctx)
 529 {
 530         ScanObjectFunc scan_func = ctx.ops->scan_object;
 531         GrayQueue *queue = ctx.queue;
 532
 533         if (ctx.ops->drain_gray_stack)
 534                 return ctx.ops->drain_gray_stack (queue);
 535
 536         for (;;) {
 537                 GCObject *obj;
 538                 SgenDescriptor desc;
 539                 GRAY_OBJECT_DEQUEUE (queue, &obj, &desc);
 540                 if (!obj)
 541                         return TRUE;
 542                 SGEN_LOG (9, "Precise gray object scan %p (%s)", obj, sgen_client_vtable_get_name (SGEN_LOAD_VTABLE (obj)));
 543                 scan_func (obj, desc, queue);
 544         }
 545         return FALSE;
 546 }
 547
 548 /*
 549  * Addresses in the pin queue are already sorted. This function finds
 550  * the object header for each address and pins the object. The
 551  * addresses must be inside the nursery section.  The (start of the)
 552  * address array is overwritten with the addresses of the actually
 553  * pinned objects.  Return the number of pinned objects.
 554  */
 555 static int
 556 pin_objects_from_nursery_pin_queue (gboolean do_scan_objects, ScanCopyContext ctx)
 557 {
 558         GCMemSection *section = nursery_section;
 559         void **start =  sgen_pinning_get_entry (section->pin_queue_first_entry);
 560         void **end = sgen_pinning_get_entry (section->pin_queue_last_entry);
 561         void *start_nursery = section->data;
 562         void *end_nursery = section->next_data;
 563         void *last = NULL;
 564         int count = 0;
 565         void *search_start;
 566         void *addr;
 567         void *pinning_front = start_nursery;
 568         size_t idx;
 569         void **definitely_pinned = start;
 570         ScanObjectFunc scan_func = ctx.ops->scan_object;
 571         SgenGrayQueue *queue = ctx.queue;
 572
 573         sgen_nursery_allocator_prepare_for_pinning ();
 574
 575         while (start < end) {
 576                 GCObject *obj_to_pin = NULL;
 577                 size_t obj_to_pin_size = 0;
 578                 SgenDescriptor desc;
 579
 580                 addr = *start;
 581
 582                 SGEN_ASSERT (0, addr >= start_nursery && addr < end_nursery, "Potential pinning address out of range");
 583                 SGEN_ASSERT (0, addr >= last, "Pin queue not sorted");
 584
 585                 if (addr == last) {
 586                         ++start;
 587                         continue;
 588                 }
 589
 590                 SGEN_LOG (5, "Considering pinning addr %p", addr);
 591                 /* We've already processed everything up to pinning_front. */
 592                 if (addr < pinning_front) {
 593                         start++;
 594                         continue;
 595                 }
 596
 597                 /*
 598                  * Find the closest scan start <= addr.  We might search backward in the
 599                  * scan_starts array because entries might be NULL.  In the worst case we
 600                  * start at start_nursery.
 601                  */
 602                 idx = ((char*)addr - (char*)section->data) / SCAN_START_SIZE;
 603                 SGEN_ASSERT (0, idx < section->num_scan_start, "Scan start index out of range");
 604                 search_start = (void*)section->scan_starts [idx];
 605                 if (!search_start || search_start > addr) {
 606                         while (idx) {
 607                                 --idx;
 608                                 search_start = section->scan_starts [idx];
 609                                 if (search_start && search_start <= addr)
 610                                         break;
 611                         }
 612                         if (!search_start || search_start > addr)
 613                                 search_start = start_nursery;
 614                 }
 615
 616                 /*
 617                  * If the pinning front is closer than the scan start we found, start
 618                  * searching at the front.
 619                  */
 620                 if (search_start < pinning_front)
 621                         search_start = pinning_front;
 622
 623                 /*
 624                  * Now addr should be in an object a short distance from search_start.
 625                  *
 626                  * search_start must point to zeroed mem or point to an object.
 627                  */
 628                 do {
 629                         size_t obj_size, canarified_obj_size;
 630
 631                         /* Skip zeros. */
 632                         if (!*(void**)search_start) {
 633                                 search_start = (void*)ALIGN_UP ((mword)search_start + sizeof (gpointer));
 634                                 /* The loop condition makes sure we don't overrun addr. */
 635                                 continue;
 636                         }
 637
 638                         canarified_obj_size = obj_size = ALIGN_UP (safe_object_get_size ((GCObject*)search_start));
 639
 640                         /*
 641                          * Filler arrays are marked by an invalid sync word.  We don't
 642                          * consider them for pinning.  They are not delimited by canaries,
 643                          * either.
 644                          */
 645                         if (!sgen_client_object_is_array_fill ((GCObject*)search_start)) {
 646                                 CHECK_CANARY_FOR_OBJECT (search_start, TRUE);
 647                                 CANARIFY_SIZE (canarified_obj_size);
 648
 649                                 if (addr >= search_start && (char*)addr < (char*)search_start + obj_size) {
 650                                         /* This is the object we're looking for. */
 651                                         obj_to_pin = (GCObject*)search_start;
 652                                         obj_to_pin_size = canarified_obj_size;
 653                                         break;
 654                                 }
 655                         }
 656
 657                         /* Skip to the next object */
 658                         search_start = (void*)((char*)search_start + canarified_obj_size);
 659                 } while (search_start <= addr);
 660
 661                 /* We've searched past the address we were looking for. */
 662                 if (!obj_to_pin) {
 663                         pinning_front = search_start;
 664                         goto next_pin_queue_entry;
 665                 }
 666
 667                 /*
 668                  * We've found an object to pin.  It might still be a dummy array, but we
 669                  * can advance the pinning front in any case.
 670                  */
 671                 pinning_front = (char*)obj_to_pin + obj_to_pin_size;
 672
 673                 /*
 674                  * If this is a dummy array marking the beginning of a nursery
 675                  * fragment, we don't pin it.
 676                  */
 677                 if (sgen_client_object_is_array_fill (obj_to_pin))
 678                         goto next_pin_queue_entry;
 679
 680                 /*
 681                  * Finally - pin the object!
 682                  */
 683                 desc = sgen_obj_get_descriptor_safe (obj_to_pin);
 684                 if (do_scan_objects) {
 685                         scan_func (obj_to_pin, desc, queue);
 686                 } else {
 687                         SGEN_LOG (4, "Pinned object %p, vtable %p (%s), count %d\n",
 688                                         obj_to_pin, *(void**)obj_to_pin, sgen_client_vtable_get_name (SGEN_LOAD_VTABLE (obj_to_pin)), count);
 689                         binary_protocol_pin (obj_to_pin,
 690                                         (gpointer)LOAD_VTABLE (obj_to_pin),
 691                                         safe_object_get_size (obj_to_pin));
 692
 693                         pin_object (obj_to_pin);
 694                         GRAY_OBJECT_ENQUEUE (queue, obj_to_pin, desc);
 695                         sgen_pin_stats_register_object (obj_to_pin, GENERATION_NURSERY);
 696                         definitely_pinned [count] = obj_to_pin;
 697                         count++;
 698                 }
 699                 if (concurrent_collection_in_progress)
 700                         sgen_pinning_register_pinned_in_nursery (obj_to_pin);
 701
 702         next_pin_queue_entry:
 703                 last = addr;
 704                 ++start;
 705         }
 706         sgen_client_nursery_objects_pinned (definitely_pinned, count);
 707         stat_pinned_objects += count;
 708         return count;
 709 }
 710
 711 static void
 712 pin_objects_in_nursery (gboolean do_scan_objects, ScanCopyContext ctx)
 713 {
 714         size_t reduced_to;
 715
 716         if (nursery_section->pin_queue_first_entry == nursery_section->pin_queue_last_entry)
 717                 return;
 718
 719         reduced_to = pin_objects_from_nursery_pin_queue (do_scan_objects, ctx);
 720         nursery_section->pin_queue_last_entry = nursery_section->pin_queue_first_entry + reduced_to;
 721 }
 722
 723 /*
 724  * This function is only ever called (via `collector_pin_object()` in `sgen-copy-object.h`)
 725  * when we can't promote an object because we're out of memory.
 726  */
 727 void
 728 sgen_pin_object (GCObject *object, GrayQueue *queue)
 729 {
 730         SGEN_ASSERT (0, sgen_ptr_in_nursery (object), "We're only supposed to use this for pinning nursery objects when out of memory.");
 731
 732         /*
 733          * All pinned objects are assumed to have been staged, so we need to stage as well.
 734          * Also, the count of staged objects shows that "late pinning" happened.
 735          */
 736         sgen_pin_stage_ptr (object);
 737
 738         SGEN_PIN_OBJECT (object);
 739         binary_protocol_pin (object, (gpointer)LOAD_VTABLE (object), safe_object_get_size (object));
 740
 741         ++objects_pinned;
 742         sgen_pin_stats_register_object (object, GENERATION_NURSERY);
 743
 744         GRAY_OBJECT_ENQUEUE (queue, object, sgen_obj_get_descriptor_safe (object));
 745 }
 746
 747 /* Sort the addresses in array in increasing order.
 748  * Done using a by-the book heap sort. Which has decent and stable performance, is pretty cache efficient.
 749  */
 750 void
 751 sgen_sort_addresses (void **array, size_t size)
 752 {
 753         size_t i;
 754         void *tmp;
 755
 756         for (i = 1; i < size; ++i) {
 757                 size_t child = i;
 758                 while (child > 0) {
 759                         size_t parent = (child - 1) / 2;
 760
 761                         if (array [parent] >= array [child])
 762                                 break;
 763
 764                         tmp = array [parent];
 765                         array [parent] = array [child];
 766                         array [child] = tmp;
 767
 768                         child = parent;
 769                 }
 770         }
 771
 772         for (i = size - 1; i > 0; --i) {
 773                 size_t end, root;
 774                 tmp = array [i];
 775                 array [i] = array [0];
 776                 array [0] = tmp;
 777
 778                 end = i - 1;
 779                 root = 0;
 780
 781                 while (root * 2 + 1 <= end) {
 782                         size_t child = root * 2 + 1;
 783
 784                         if (child < end && array [child] < array [child + 1])
 785                                 ++child;
 786                         if (array [root] >= array [child])
 787                                 break;
 788
 789                         tmp = array [root];
 790                         array [root] = array [child];
 791                         array [child] = tmp;
 792
 793                         root = child;
 794                 }
 795         }
 796 }
 797
 798 /*
 799  * Scan the memory between start and end and queue values which could be pointers
 800  * to the area between start_nursery and end_nursery for later consideration.
 801  * Typically used for thread stacks.
 802  */
 803 void
 804 sgen_conservatively_pin_objects_from (void **start, void **end, void *start_nursery, void *end_nursery, int pin_type)
 805 {
 806         int count = 0;
 807
 808         SGEN_ASSERT (0, ((mword)start & (SIZEOF_VOID_P - 1)) == 0, "Why are we scanning for references in unaligned memory ?");
 809
 810 #if defined(VALGRIND_MAKE_MEM_DEFINED_IF_ADDRESSABLE) && !defined(_WIN64)
 811         VALGRIND_MAKE_MEM_DEFINED_IF_ADDRESSABLE (start, (char*)end - (char*)start);
 812 #endif
 813
 814         while (start < end) {
 815                 /*
 816                  * *start can point to the middle of an object
 817                  * note: should we handle pointing at the end of an object?
 818                  * pinning in C# code disallows pointing at the end of an object
 819                  * but there is some small chance that an optimizing C compiler
 820                  * may keep the only reference to an object by pointing
 821                  * at the end of it. We ignore this small chance for now.
 822                  * Pointers to the end of an object are indistinguishable
 823                  * from pointers to the start of the next object in memory
 824                  * so if we allow that we'd need to pin two objects...
 825                  * We queue the pointer in an array, the
 826                  * array will then be sorted and uniqued. This way
 827                  * we can coalesce several pinning pointers and it should
 828                  * be faster since we'd do a memory scan with increasing
 829                  * addresses. Note: we can align the address to the allocation
 830                  * alignment, so the unique process is more effective.
 831                  */
 832                 mword addr = (mword)*start;
 833                 addr &= ~(ALLOC_ALIGN - 1);
 834                 if (addr >= (mword)start_nursery && addr < (mword)end_nursery) {
 835                         SGEN_LOG (6, "Pinning address %p from %p", (void*)addr, start);
 836                         sgen_pin_stage_ptr ((void*)addr);
 837                         binary_protocol_pin_stage (start, (void*)addr);
 838                         sgen_pin_stats_register_address ((char*)addr, pin_type);
 839                         count++;
 840                 }
 841                 start++;
 842         }
 843         if (count)
 844                 SGEN_LOG (7, "found %d potential pinned heap pointers", count);
 845 }
 846
 847 /*
 848  * The first thing we do in a collection is to identify pinned objects.
 849  * This function considers all the areas of memory that need to be
 850  * conservatively scanned.
 851  */
 852 static void
 853 pin_from_roots (void *start_nursery, void *end_nursery, ScanCopyContext ctx)
 854 {
 855         void **start_root;
 856         RootRecord *root;
 857         SGEN_LOG (2, "Scanning pinned roots (%d bytes, %d/%d entries)", (int)roots_size, roots_hash [ROOT_TYPE_NORMAL].num_entries, roots_hash [ROOT_TYPE_PINNED].num_entries);
 858         /* objects pinned from the API are inside these roots */
 859         SGEN_HASH_TABLE_FOREACH (&roots_hash [ROOT_TYPE_PINNED], void **, start_root, RootRecord *, root) {
 860                 SGEN_LOG (6, "Pinned roots %p-%p", start_root, root->end_root);
 861                 sgen_conservatively_pin_objects_from (start_root, (void**)root->end_root, start_nursery, end_nursery, PIN_TYPE_OTHER);
 862         } SGEN_HASH_TABLE_FOREACH_END;
 863         /* now deal with the thread stacks
 864          * in the future we should be able to conservatively scan only:
 865          * *) the cpu registers
 866          * *) the unmanaged stack frames
 867          * *) the _last_ managed stack frame
 868          * *) pointers slots in managed frames
 869          */
 870         sgen_client_scan_thread_data (start_nursery, end_nursery, FALSE, ctx);
 871 }
 872
 873 static void
 874 single_arg_user_copy_or_mark (GCObject **obj, void *gc_data)
 875 {
 876         ScanCopyContext *ctx = (ScanCopyContext *)gc_data;
 877         ctx->ops->copy_or_mark_object (obj, ctx->queue);
 878 }
 879
 880 /*
 881  * The memory area from start_root to end_root contains pointers to objects.
 882  * Their position is precisely described by @desc (this means that the pointer
 883  * can be either NULL or the pointer to the start of an object).
 884  * This functions copies them to to_space updates them.
 885  *
 886  * This function is not thread-safe!
 887  */
 888 static void
 889 precisely_scan_objects_from (void** start_root, void** end_root, char* n_start, char *n_end, SgenDescriptor desc, ScanCopyContext ctx)
 890 {
 891         CopyOrMarkObjectFunc copy_func = ctx.ops->copy_or_mark_object;
 892         SgenGrayQueue *queue = ctx.queue;
 893
 894         switch (desc & ROOT_DESC_TYPE_MASK) {
 895         case ROOT_DESC_BITMAP:
 896                 desc >>= ROOT_DESC_TYPE_SHIFT;
 897                 while (desc) {
 898                         if ((desc & 1) && *start_root) {
 899                                 copy_func ((GCObject**)start_root, queue);
 900                                 SGEN_LOG (9, "Overwrote root at %p with %p", start_root, *start_root);
 901                         }
 902                         desc >>= 1;
 903                         start_root++;
 904                 }
 905                 return;
 906         case ROOT_DESC_COMPLEX: {
 907                 gsize *bitmap_data = (gsize *)sgen_get_complex_descriptor_bitmap (desc);
 908                 gsize bwords = (*bitmap_data) - 1;
 909                 void **start_run = start_root;
 910                 bitmap_data++;
 911                 while (bwords-- > 0) {
 912                         gsize bmap = *bitmap_data++;
 913                         void **objptr = start_run;
 914                         while (bmap) {
 915                                 if ((bmap & 1) && *objptr) {
 916                                         copy_func ((GCObject**)objptr, queue);
 917                                         SGEN_LOG (9, "Overwrote root at %p with %p", objptr, *objptr);
 918                                 }
 919                                 bmap >>= 1;
 920                                 ++objptr;
 921                         }
 922                         start_run += GC_BITS_PER_WORD;
 923                 }
 924                 break;
 925         }
 926         case ROOT_DESC_USER: {
 927                 SgenUserRootMarkFunc marker = sgen_get_user_descriptor_func (desc);
 928                 marker (start_root, single_arg_user_copy_or_mark, &ctx);
 929                 break;
 930         }
 931         case ROOT_DESC_RUN_LEN:
 932                 g_assert_not_reached ();
 933         default:
 934                 g_assert_not_reached ();
 935         }
 936 }
 937
 938 static void
 939 reset_heap_boundaries (void)
 940 {
 941         lowest_heap_address = ~(mword)0;
 942         highest_heap_address = 0;
 943 }
 944
 945 void
 946 sgen_update_heap_boundaries (mword low, mword high)
 947 {
 948         mword old;
 949
 950         do {
 951                 old = lowest_heap_address;
 952                 if (low >= old)
 953                         break;
 954         } while (SGEN_CAS_PTR ((gpointer*)&lowest_heap_address, (gpointer)low, (gpointer)old) != (gpointer)old);
 955
 956         do {
 957                 old = highest_heap_address;
 958                 if (high <= old)
 959                         break;
 960         } while (SGEN_CAS_PTR ((gpointer*)&highest_heap_address, (gpointer)high, (gpointer)old) != (gpointer)old);
 961 }
 962
 963 /*
 964  * Allocate and setup the data structures needed to be able to allocate objects
 965  * in the nursery. The nursery is stored in nursery_section.
 966  */
 967 static void
 968 alloc_nursery (void)
 969 {
 970         GCMemSection *section;
 971         char *data;
 972         size_t scan_starts;
 973         size_t alloc_size;
 974
 975         if (nursery_section)
 976                 return;
 977         SGEN_LOG (2, "Allocating nursery size: %zu", (size_t)sgen_nursery_size);
 978         /* later we will alloc a larger area for the nursery but only activate
 979          * what we need. The rest will be used as expansion if we have too many pinned
 980          * objects in the existing nursery.
 981          */
 982         /* FIXME: handle OOM */
 983         section = (GCMemSection *)sgen_alloc_internal (INTERNAL_MEM_SECTION);
 984
 985         alloc_size = sgen_nursery_size;
 986
 987         /* If there isn't enough space even for the nursery we should simply abort. */
 988         g_assert (sgen_memgov_try_alloc_space (alloc_size, SPACE_NURSERY));
 989
 990         data = (char *)major_collector.alloc_heap (alloc_size, alloc_size, DEFAULT_NURSERY_BITS);
 991         sgen_update_heap_boundaries ((mword)data, (mword)(data + sgen_nursery_size));
 992         SGEN_LOG (4, "Expanding nursery size (%p-%p): %lu, total: %lu", data, data + alloc_size, (unsigned long)sgen_nursery_size, (unsigned long)sgen_gc_get_total_heap_allocation ());
 993         section->data = section->next_data = data;
 994         section->size = alloc_size;
 995         section->end_data = data + sgen_nursery_size;
 996         scan_starts = (alloc_size + SCAN_START_SIZE - 1) / SCAN_START_SIZE;
 997         section->scan_starts = (char **)sgen_alloc_internal_dynamic (sizeof (char*) * scan_starts, INTERNAL_MEM_SCAN_STARTS, TRUE);
 998         section->num_scan_start = scan_starts;
 999
1000         nursery_section = section;
1001
1002         sgen_nursery_allocator_set_nursery_bounds (data, data + sgen_nursery_size);
1003 }
1004
1005 FILE *
1006 mono_gc_get_logfile (void)
1007 {
1008         return gc_debug_file;
1009 }
1010
1011 static void
1012 scan_finalizer_entries (SgenPointerQueue *fin_queue, ScanCopyContext ctx)
1013 {
1014         CopyOrMarkObjectFunc copy_func = ctx.ops->copy_or_mark_object;
1015         SgenGrayQueue *queue = ctx.queue;
1016         size_t i;
1017
1018         for (i = 0; i < fin_queue->next_slot; ++i) {
1019                 GCObject *obj = (GCObject *)fin_queue->data [i];
1020                 if (!obj)
1021                         continue;
1022                 SGEN_LOG (5, "Scan of fin ready object: %p (%s)\n", obj, sgen_client_vtable_get_name (SGEN_LOAD_VTABLE (obj)));
1023                 copy_func ((GCObject**)&fin_queue->data [i], queue);
1024         }
1025 }
1026
1027 static const char*
1028 generation_name (int generation)
1029 {
1030         switch (generation) {
1031         case GENERATION_NURSERY: return "nursery";
1032         case GENERATION_OLD: return "old";
1033         default: g_assert_not_reached ();
1034         }
1035 }
1036
1037 const char*
1038 sgen_generation_name (int generation)
1039 {
1040         return generation_name (generation);
1041 }
1042
1043 static void
1044 finish_gray_stack (int generation, ScanCopyContext ctx)
1045 {
1046         TV_DECLARE (atv);
1047         TV_DECLARE (btv);
1048         int done_with_ephemerons, ephemeron_rounds = 0;
1049         char *start_addr = generation == GENERATION_NURSERY ? sgen_get_nursery_start () : NULL;
1050         char *end_addr = generation == GENERATION_NURSERY ? sgen_get_nursery_end () : (char*)-1;
1051         SgenGrayQueue *queue = ctx.queue;
1052
1053         binary_protocol_finish_gray_stack_start (sgen_timestamp (), generation);
1054         /*
1055          * We copied all the reachable objects. Now it's the time to copy
1056          * the objects that were not referenced by the roots, but by the copied objects.
1057          * we built a stack of objects pointed to by gray_start: they are
1058          * additional roots and we may add more items as we go.
1059          * We loop until gray_start == gray_objects which means no more objects have
1060          * been added. Note this is iterative: no recursion is involved.
1061          * We need to walk the LO list as well in search of marked big objects
1062          * (use a flag since this is needed only on major collections). We need to loop
1063          * here as well, so keep a counter of marked LO (increasing it in copy_object).
1064          *   To achieve better cache locality and cache usage, we drain the gray stack
1065          * frequently, after each object is copied, and just finish the work here.
1066          */
1067         sgen_drain_gray_stack (ctx);
1068         TV_GETTIME (atv);
1069         SGEN_LOG (2, "%s generation done", generation_name (generation));
1070
1071         /*
1072         Reset bridge data, we might have lingering data from a previous collection if this is a major
1073         collection trigged by minor overflow.
1074
1075         We must reset the gathered bridges since their original block might be evacuated due to major
1076         fragmentation in the meanwhile and the bridge code should not have to deal with that.
1077         */
1078         if (sgen_client_bridge_need_processing ())
1079                 sgen_client_bridge_reset_data ();
1080
1081         /*
1082          * Mark all strong toggleref objects. This must be done before we walk ephemerons or finalizers
1083          * to ensure they see the full set of live objects.
1084          */
1085         sgen_client_mark_togglerefs (start_addr, end_addr, ctx);
1086
1087         /*
1088          * Walk the ephemeron tables marking all values with reachable keys. This must be completely done
1089          * before processing finalizable objects and non-tracking weak links to avoid finalizing/clearing
1090          * objects that are in fact reachable.
1091          */
1092         done_with_ephemerons = 0;
1093         do {
1094                 done_with_ephemerons = sgen_client_mark_ephemerons (ctx);
1095                 sgen_drain_gray_stack (ctx);
1096                 ++ephemeron_rounds;
1097         } while (!done_with_ephemerons);
1098
1099         if (sgen_client_bridge_need_processing ()) {
1100                 /*Make sure the gray stack is empty before we process bridge objects so we get liveness right*/
1101                 sgen_drain_gray_stack (ctx);
1102                 sgen_collect_bridge_objects (generation, ctx);
1103                 if (generation == GENERATION_OLD)
1104                         sgen_collect_bridge_objects (GENERATION_NURSERY, ctx);
1105
1106                 /*
1107                 Do the first bridge step here, as the collector liveness state will become useless after that.
1108
1109                 An important optimization is to only proccess the possibly dead part of the object graph and skip
1110                 over all live objects as we transitively know everything they point must be alive too.
1111
1112                 The above invariant is completely wrong if we let the gray queue be drained and mark/copy everything.
1113
1114                 This has the unfortunate side effect of making overflow collections perform the first step twice, but
1115                 given we now have heuristics that perform major GC in anticipation of minor overflows this should not
1116                 be a big deal.
1117                 */
1118                 sgen_client_bridge_processing_stw_step ();
1119         }
1120
1121         /*
1122         Make sure we drain the gray stack before processing disappearing links and finalizers.
1123         If we don't make sure it is empty we might wrongly see a live object as dead.
1124         */
1125         sgen_drain_gray_stack (ctx);
1126
1127         /*
1128         We must clear weak links that don't track resurrection before processing object ready for
1129         finalization so they can be cleared before that.
1130         */
1131         sgen_null_link_in_range (generation, ctx, FALSE);
1132         if (generation == GENERATION_OLD)
1133                 sgen_null_link_in_range (GENERATION_NURSERY, ctx, FALSE);
1134
1135
1136         /* walk the finalization queue and move also the objects that need to be
1137          * finalized: use the finalized objects as new roots so the objects they depend
1138          * on are also not reclaimed. As with the roots above, only objects in the nursery
1139          * are marked/copied.
1140          */
1141         sgen_finalize_in_range (generation, ctx);
1142         if (generation == GENERATION_OLD)
1143                 sgen_finalize_in_range (GENERATION_NURSERY, ctx);
1144         /* drain the new stack that might have been created */
1145         SGEN_LOG (6, "Precise scan of gray area post fin");
1146         sgen_drain_gray_stack (ctx);
1147
1148         /*
1149          * This must be done again after processing finalizable objects since CWL slots are cleared only after the key is finalized.
1150          */
1151         done_with_ephemerons = 0;
1152         do {
1153                 done_with_ephemerons = sgen_client_mark_ephemerons (ctx);
1154                 sgen_drain_gray_stack (ctx);
1155                 ++ephemeron_rounds;
1156         } while (!done_with_ephemerons);
1157
1158         sgen_client_clear_unreachable_ephemerons (ctx);
1159
1160         /*
1161          * We clear togglerefs only after all possible chances of revival are done.
1162          * This is semantically more inline with what users expect and it allows for
1163          * user finalizers to correctly interact with TR objects.
1164         */
1165         sgen_client_clear_togglerefs (start_addr, end_addr, ctx);
1166
1167         TV_GETTIME (btv);
1168         SGEN_LOG (2, "Finalize queue handling scan for %s generation: %lld usecs %d ephemeron rounds", generation_name (generation), (long long)TV_ELAPSED (atv, btv), ephemeron_rounds);
1169
1170         /*
1171          * handle disappearing links
1172          * Note we do this after checking the finalization queue because if an object
1173          * survives (at least long enough to be finalized) we don't clear the link.
1174          * This also deals with a possible issue with the monitor reclamation: with the Boehm
1175          * GC a finalized object my lose the monitor because it is cleared before the finalizer is
1176          * called.
1177          */
1178         g_assert (sgen_gray_object_queue_is_empty (queue));
1179         for (;;) {
1180                 sgen_null_link_in_range (generation, ctx, TRUE);
1181                 if (generation == GENERATION_OLD)
1182                         sgen_null_link_in_range (GENERATION_NURSERY, ctx, TRUE);
1183                 if (sgen_gray_object_queue_is_empty (queue))
1184                         break;
1185                 sgen_drain_gray_stack (ctx);
1186         }
1187
1188         g_assert (sgen_gray_object_queue_is_empty (queue));
1189
1190         sgen_gray_object_queue_trim_free_list (queue);
1191         binary_protocol_finish_gray_stack_end (sgen_timestamp (), generation);
1192 }
1193
1194 void
1195 sgen_check_section_scan_starts (GCMemSection *section)
1196 {
1197         size_t i;
1198         for (i = 0; i < section->num_scan_start; ++i) {
1199                 if (section->scan_starts [i]) {
1200                         mword size = safe_object_get_size ((GCObject*) section->scan_starts [i]);
1201                         SGEN_ASSERT (0, size >= SGEN_CLIENT_MINIMUM_OBJECT_SIZE && size <= MAX_SMALL_OBJ_SIZE, "Weird object size at scan starts.");
1202                 }
1203         }
1204 }
1205
1206 static void
1207 check_scan_starts (void)
1208 {
1209         if (!do_scan_starts_check)
1210                 return;
1211         sgen_check_section_scan_starts (nursery_section);
1212         major_collector.check_scan_starts ();
1213 }
1214
1215 static void
1216 scan_from_registered_roots (char *addr_start, char *addr_end, int root_type, ScanCopyContext ctx)
1217 {
1218         void **start_root;
1219         RootRecord *root;
1220         SGEN_HASH_TABLE_FOREACH (&roots_hash [root_type], void **, start_root, RootRecord *, root) {
1221                 SGEN_LOG (6, "Precise root scan %p-%p (desc: %p)", start_root, root->end_root, (void*)root->root_desc);
1222                 precisely_scan_objects_from (start_root, (void**)root->end_root, addr_start, addr_end, root->root_desc, ctx);
1223         } SGEN_HASH_TABLE_FOREACH_END;
1224 }
1225
1226 static void
1227 init_stats (void)
1228 {
1229         static gboolean inited = FALSE;
1230
1231         if (inited)
1232                 return;
1233
1234         mono_counters_register ("Collection max time",  MONO_COUNTER_GC | MONO_COUNTER_ULONG | MONO_COUNTER_TIME | MONO_COUNTER_MONOTONIC, &time_max);
1235
1236         mono_counters_register ("Minor fragment clear", MONO_COUNTER_GC | MONO_COUNTER_ULONG | MONO_COUNTER_TIME, &time_minor_pre_collection_fragment_clear);
1237         mono_counters_register ("Minor pinning", MONO_COUNTER_GC | MONO_COUNTER_ULONG | MONO_COUNTER_TIME, &time_minor_pinning);
1238         mono_counters_register ("Minor scan remembered set", MONO_COUNTER_GC | MONO_COUNTER_ULONG | MONO_COUNTER_TIME, &time_minor_scan_remsets);
1239         mono_counters_register ("Minor scan pinned", MONO_COUNTER_GC | MONO_COUNTER_ULONG | MONO_COUNTER_TIME, &time_minor_scan_pinned);
1240         mono_counters_register ("Minor scan roots", MONO_COUNTER_GC | MONO_COUNTER_ULONG | MONO_COUNTER_TIME, &time_minor_scan_roots);
1241         mono_counters_register ("Minor fragment creation", MONO_COUNTER_GC | MONO_COUNTER_ULONG | MONO_COUNTER_TIME, &time_minor_fragment_creation);
1242
1243         mono_counters_register ("Major fragment clear", MONO_COUNTER_GC | MONO_COUNTER_ULONG | MONO_COUNTER_TIME, &time_major_pre_collection_fragment_clear);
1244         mono_counters_register ("Major pinning", MONO_COUNTER_GC | MONO_COUNTER_ULONG | MONO_COUNTER_TIME, &time_major_pinning);
1245         mono_counters_register ("Major scan pinned", MONO_COUNTER_GC | MONO_COUNTER_ULONG | MONO_COUNTER_TIME, &time_major_scan_pinned);
1246         mono_counters_register ("Major scan roots", MONO_COUNTER_GC | MONO_COUNTER_ULONG | MONO_COUNTER_TIME, &time_major_scan_roots);
1247         mono_counters_register ("Major scan mod union", MONO_COUNTER_GC | MONO_COUNTER_ULONG | MONO_COUNTER_TIME, &time_major_scan_mod_union);
1248         mono_counters_register ("Major finish gray stack", MONO_COUNTER_GC | MONO_COUNTER_ULONG | MONO_COUNTER_TIME, &time_major_finish_gray_stack);
1249         mono_counters_register ("Major free big objects", MONO_COUNTER_GC | MONO_COUNTER_ULONG | MONO_COUNTER_TIME, &time_major_free_bigobjs);
1250         mono_counters_register ("Major LOS sweep", MONO_COUNTER_GC | MONO_COUNTER_ULONG | MONO_COUNTER_TIME, &time_major_los_sweep);
1251         mono_counters_register ("Major sweep", MONO_COUNTER_GC | MONO_COUNTER_ULONG | MONO_COUNTER_TIME, &time_major_sweep);
1252         mono_counters_register ("Major fragment creation", MONO_COUNTER_GC | MONO_COUNTER_ULONG | MONO_COUNTER_TIME, &time_major_fragment_creation);
1253
1254         mono_counters_register ("Number of pinned objects", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_pinned_objects);
1255
1256 #ifdef HEAVY_STATISTICS
1257         mono_counters_register ("WBarrier remember pointer", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_wbarrier_add_to_global_remset);
1258         mono_counters_register ("WBarrier arrayref copy", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_wbarrier_arrayref_copy);
1259         mono_counters_register ("WBarrier generic store called", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_wbarrier_generic_store);
1260         mono_counters_register ("WBarrier generic atomic store called", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_wbarrier_generic_store_atomic);
1261         mono_counters_register ("WBarrier set root", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_wbarrier_set_root);
1262
1263         mono_counters_register ("# objects allocated degraded", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_objects_alloced_degraded);
1264         mono_counters_register ("bytes allocated degraded", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_bytes_alloced_degraded);
1265
1266         mono_counters_register ("# copy_object() called (nursery)", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_copy_object_called_nursery);
1267         mono_counters_register ("# objects copied (nursery)", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_objects_copied_nursery);
1268         mono_counters_register ("# copy_object() called (major)", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_copy_object_called_major);
1269         mono_counters_register ("# objects copied (major)", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_objects_copied_major);
1270
1271         mono_counters_register ("# scan_object() called (nursery)", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_scan_object_called_nursery);
1272         mono_counters_register ("# scan_object() called (major)", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_scan_object_called_major);
1273
1274         mono_counters_register ("Slots allocated in vain", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_slots_allocated_in_vain);
1275
1276         mono_counters_register ("# nursery copy_object() failed from space", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_nursery_copy_object_failed_from_space);
1277         mono_counters_register ("# nursery copy_object() failed forwarded", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_nursery_copy_object_failed_forwarded);
1278         mono_counters_register ("# nursery copy_object() failed pinned", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_nursery_copy_object_failed_pinned);
1279         mono_counters_register ("# nursery copy_object() failed to space", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_nursery_copy_object_failed_to_space);
1280
1281         sgen_nursery_allocator_init_heavy_stats ();
1282 #endif
1283
1284         inited = TRUE;
1285 }
1286
1287
1288 static void
1289 reset_pinned_from_failed_allocation (void)
1290 {
1291         bytes_pinned_from_failed_allocation = 0;
1292 }
1293
1294 void
1295 sgen_set_pinned_from_failed_allocation (mword objsize)
1296 {
1297         bytes_pinned_from_failed_allocation += objsize;
1298 }
1299
1300 gboolean
1301 sgen_collection_is_concurrent (void)
1302 {
1303         switch (current_collection_generation) {
1304         case GENERATION_NURSERY:
1305                 return FALSE;
1306         case GENERATION_OLD:
1307                 return concurrent_collection_in_progress;
1308         default:
1309                 g_error ("Invalid current generation %d", current_collection_generation);
1310         }
1311         return FALSE;
1312 }
1313
1314 gboolean
1315 sgen_concurrent_collection_in_progress (void)
1316 {
1317         return concurrent_collection_in_progress;
1318 }
1319
1320 typedef struct {
1321         SgenThreadPoolJob job;
1322         SgenObjectOperations *ops;
1323 } ScanJob;
1324
1325 static void
1326 job_remembered_set_scan (void *worker_data_untyped, SgenThreadPoolJob *job)
1327 {
1328         WorkerData *worker_data = (WorkerData *)worker_data_untyped;
1329         ScanJob *job_data = (ScanJob*)job;
1330         ScanCopyContext ctx = CONTEXT_FROM_OBJECT_OPERATIONS (job_data->ops, sgen_workers_get_job_gray_queue (worker_data));
1331         remset.scan_remsets (ctx);
1332 }
1333
1334 typedef struct {
1335         SgenThreadPoolJob job;
1336         SgenObjectOperations *ops;
1337         char *heap_start;
1338         char *heap_end;
1339         int root_type;
1340 } ScanFromRegisteredRootsJob;
1341
1342 static void
1343 job_scan_from_registered_roots (void *worker_data_untyped, SgenThreadPoolJob *job)
1344 {
1345         WorkerData *worker_data = (WorkerData *)worker_data_untyped;
1346         ScanFromRegisteredRootsJob *job_data = (ScanFromRegisteredRootsJob*)job;
1347         ScanCopyContext ctx = CONTEXT_FROM_OBJECT_OPERATIONS (job_data->ops, sgen_workers_get_job_gray_queue (worker_data));
1348
1349         scan_from_registered_roots (job_data->heap_start, job_data->heap_end, job_data->root_type, ctx);
1350 }
1351
1352 typedef struct {
1353         SgenThreadPoolJob job;
1354         SgenObjectOperations *ops;
1355         char *heap_start;
1356         char *heap_end;
1357 } ScanThreadDataJob;
1358
1359 static void
1360 job_scan_thread_data (void *worker_data_untyped, SgenThreadPoolJob *job)
1361 {
1362         WorkerData *worker_data = (WorkerData *)worker_data_untyped;
1363         ScanThreadDataJob *job_data = (ScanThreadDataJob*)job;
1364         ScanCopyContext ctx = CONTEXT_FROM_OBJECT_OPERATIONS (job_data->ops, sgen_workers_get_job_gray_queue (worker_data));
1365
1366         sgen_client_scan_thread_data (job_data->heap_start, job_data->heap_end, TRUE, ctx);
1367 }
1368
1369 typedef struct {
1370         SgenThreadPoolJob job;
1371         SgenObjectOperations *ops;
1372         SgenPointerQueue *queue;
1373 } ScanFinalizerEntriesJob;
1374
1375 static void
1376 job_scan_finalizer_entries (void *worker_data_untyped, SgenThreadPoolJob *job)
1377 {
1378         WorkerData *worker_data = (WorkerData *)worker_data_untyped;
1379         ScanFinalizerEntriesJob *job_data = (ScanFinalizerEntriesJob*)job;
1380         ScanCopyContext ctx = CONTEXT_FROM_OBJECT_OPERATIONS (job_data->ops, sgen_workers_get_job_gray_queue (worker_data));
1381
1382         scan_finalizer_entries (job_data->queue, ctx);
1383 }
1384
1385 static void
1386 job_scan_major_mod_union_card_table (void *worker_data_untyped, SgenThreadPoolJob *job)
1387 {
1388         WorkerData *worker_data = (WorkerData *)worker_data_untyped;
1389         ScanJob *job_data = (ScanJob*)job;
1390         ScanCopyContext ctx = CONTEXT_FROM_OBJECT_OPERATIONS (job_data->ops, sgen_workers_get_job_gray_queue (worker_data));
1391
1392         g_assert (concurrent_collection_in_progress);
1393         major_collector.scan_card_table (CARDTABLE_SCAN_MOD_UNION, ctx);
1394 }
1395
1396 static void
1397 job_scan_los_mod_union_card_table (void *worker_data_untyped, SgenThreadPoolJob *job)
1398 {
1399         WorkerData *worker_data = (WorkerData *)worker_data_untyped;
1400         ScanJob *job_data = (ScanJob*)job;
1401         ScanCopyContext ctx = CONTEXT_FROM_OBJECT_OPERATIONS (job_data->ops, sgen_workers_get_job_gray_queue (worker_data));
1402
1403         g_assert (concurrent_collection_in_progress);
1404         sgen_los_scan_card_table (CARDTABLE_SCAN_MOD_UNION, ctx);
1405 }
1406
1407 static void
1408 job_mod_union_preclean (void *worker_data_untyped, SgenThreadPoolJob *job)
1409 {
1410         WorkerData *worker_data = (WorkerData *)worker_data_untyped;
1411         ScanJob *job_data = (ScanJob*)job;
1412         ScanCopyContext ctx = CONTEXT_FROM_OBJECT_OPERATIONS (job_data->ops, sgen_workers_get_job_gray_queue (worker_data));
1413
1414         g_assert (concurrent_collection_in_progress);
1415
1416         major_collector.scan_card_table (CARDTABLE_SCAN_MOD_UNION_PRECLEAN, ctx);
1417         sgen_los_scan_card_table (CARDTABLE_SCAN_MOD_UNION_PRECLEAN, ctx);
1418
1419         sgen_scan_pin_queue_objects (ctx);
1420 }
1421
1422 static void
1423 init_gray_queue (gboolean use_workers)
1424 {
1425         if (use_workers)
1426                 sgen_workers_init_distribute_gray_queue ();
1427         sgen_gray_object_queue_init (&gray_queue, NULL);
1428 }
1429
1430 static void
1431 enqueue_scan_from_roots_jobs (char *heap_start, char *heap_end, SgenObjectOperations *ops, gboolean enqueue)
1432 {
1433         ScanFromRegisteredRootsJob *scrrj;
1434         ScanThreadDataJob *stdj;
1435         ScanFinalizerEntriesJob *sfej;
1436
1437         /* registered roots, this includes static fields */
1438
1439         scrrj = (ScanFromRegisteredRootsJob*)sgen_thread_pool_job_alloc ("scan from registered roots normal", job_scan_from_registered_roots, sizeof (ScanFromRegisteredRootsJob));
1440         scrrj->ops = ops;
1441         scrrj->heap_start = heap_start;
1442         scrrj->heap_end = heap_end;
1443         scrrj->root_type = ROOT_TYPE_NORMAL;
1444         sgen_workers_enqueue_job (&scrrj->job, enqueue);
1445
1446         scrrj = (ScanFromRegisteredRootsJob*)sgen_thread_pool_job_alloc ("scan from registered roots wbarrier", job_scan_from_registered_roots, sizeof (ScanFromRegisteredRootsJob));
1447         scrrj->ops = ops;
1448         scrrj->heap_start = heap_start;
1449         scrrj->heap_end = heap_end;
1450         scrrj->root_type = ROOT_TYPE_WBARRIER;
1451         sgen_workers_enqueue_job (&scrrj->job, enqueue);
1452
1453         /* Threads */
1454
1455         stdj = (ScanThreadDataJob*)sgen_thread_pool_job_alloc ("scan thread data", job_scan_thread_data, sizeof (ScanThreadDataJob));
1456         stdj->heap_start = heap_start;
1457         stdj->heap_end = heap_end;
1458         sgen_workers_enqueue_job (&stdj->job, enqueue);
1459
1460         /* Scan the list of objects ready for finalization. */
1461
1462         sfej = (ScanFinalizerEntriesJob*)sgen_thread_pool_job_alloc ("scan finalizer entries", job_scan_finalizer_entries, sizeof (ScanFinalizerEntriesJob));
1463         sfej->queue = &fin_ready_queue;
1464         sfej->ops = ops;
1465         sgen_workers_enqueue_job (&sfej->job, enqueue);
1466
1467         sfej = (ScanFinalizerEntriesJob*)sgen_thread_pool_job_alloc ("scan critical finalizer entries", job_scan_finalizer_entries, sizeof (ScanFinalizerEntriesJob));
1468         sfej->queue = &critical_fin_queue;
1469         sfej->ops = ops;
1470         sgen_workers_enqueue_job (&sfej->job, enqueue);
1471 }
1472
1473 /*
1474  * Perform a nursery collection.
1475  *
1476  * Return whether any objects were late-pinned due to being out of memory.
1477  */
1478 static gboolean
1479 collect_nursery (const char *reason, gboolean is_overflow, SgenGrayQueue *unpin_queue, gboolean finish_up_concurrent_mark)
1480 {
1481         gboolean needs_major;
1482         size_t max_garbage_amount;
1483         char *nursery_next;
1484         mword fragment_total;
1485         ScanJob *sj;
1486         SgenObjectOperations *object_ops = &sgen_minor_collector.serial_ops;
1487         ScanCopyContext ctx = CONTEXT_FROM_OBJECT_OPERATIONS (object_ops, &gray_queue);
1488         TV_DECLARE (atv);
1489         TV_DECLARE (btv);
1490
1491         if (disable_minor_collections)
1492                 return TRUE;
1493
1494         TV_GETTIME (last_minor_collection_start_tv);
1495         atv = last_minor_collection_start_tv;
1496
1497         binary_protocol_collection_begin (gc_stats.minor_gc_count, GENERATION_NURSERY);
1498
1499         if (do_verify_nursery || do_dump_nursery_content)
1500                 sgen_debug_verify_nursery (do_dump_nursery_content);
1501
1502         current_collection_generation = GENERATION_NURSERY;
1503
1504         SGEN_ASSERT (0, !sgen_collection_is_concurrent (), "Why is the nursery collection concurrent?");
1505
1506         reset_pinned_from_failed_allocation ();
1507
1508         check_scan_starts ();
1509
1510         sgen_nursery_alloc_prepare_for_minor ();
1511
1512         degraded_mode = 0;
1513         objects_pinned = 0;
1514         nursery_next = sgen_nursery_alloc_get_upper_alloc_bound ();
1515         /* FIXME: optimize later to use the higher address where an object can be present */
1516         nursery_next = MAX (nursery_next, sgen_get_nursery_end ());
1517
1518         SGEN_LOG (1, "Start nursery collection %d %p-%p, size: %d", gc_stats.minor_gc_count, sgen_get_nursery_start (), nursery_next, (int)(nursery_next - sgen_get_nursery_start ()));
1519         max_garbage_amount = nursery_next - sgen_get_nursery_start ();
1520         g_assert (nursery_section->size >= max_garbage_amount);
1521
1522         /* world must be stopped already */
1523         TV_GETTIME (btv);
1524         time_minor_pre_collection_fragment_clear += TV_ELAPSED (atv, btv);
1525
1526         sgen_client_pre_collection_checks ();
1527
1528         nursery_section->next_data = nursery_next;
1529
1530         major_collector.start_nursery_collection ();
1531
1532         sgen_memgov_minor_collection_start ();
1533
1534         init_gray_queue (FALSE);
1535
1536         gc_stats.minor_gc_count ++;
1537
1538         if (whole_heap_check_before_collection) {
1539                 sgen_clear_nursery_fragments ();
1540                 sgen_check_whole_heap (finish_up_concurrent_mark);
1541         }
1542         if (consistency_check_at_minor_collection)
1543                 sgen_check_consistency ();
1544
1545         sgen_process_fin_stage_entries ();
1546
1547         /* pin from pinned handles */
1548         sgen_init_pinning ();
1549         sgen_client_binary_protocol_mark_start (GENERATION_NURSERY);
1550         pin_from_roots (sgen_get_nursery_start (), nursery_next, ctx);
1551         /* pin cemented objects */
1552         sgen_pin_cemented_objects ();
1553         /* identify pinned objects */
1554         sgen_optimize_pin_queue ();
1555         sgen_pinning_setup_section (nursery_section);
1556
1557         pin_objects_in_nursery (FALSE, ctx);
1558         sgen_pinning_trim_queue_to_section (nursery_section);
1559
1560         TV_GETTIME (atv);
1561         time_minor_pinning += TV_ELAPSED (btv, atv);
1562         SGEN_LOG (2, "Finding pinned pointers: %zd in %lld usecs", sgen_get_pinned_count (), (long long)TV_ELAPSED (btv, atv));
1563         SGEN_LOG (4, "Start scan with %zd pinned objects", sgen_get_pinned_count ());
1564
1565         sj = (ScanJob*)sgen_thread_pool_job_alloc ("scan remset", job_remembered_set_scan, sizeof (ScanJob));
1566         sj->ops = object_ops;
1567         sgen_workers_enqueue_job (&sj->job, FALSE);
1568
1569         /* we don't have complete write barrier yet, so we scan all the old generation sections */
1570         TV_GETTIME (btv);
1571         time_minor_scan_remsets += TV_ELAPSED (atv, btv);
1572         SGEN_LOG (2, "Old generation scan: %lld usecs", (long long)TV_ELAPSED (atv, btv));
1573
1574         sgen_pin_stats_report ();
1575
1576         /* FIXME: Why do we do this at this specific, seemingly random, point? */
1577         sgen_client_collecting_minor (&fin_ready_queue, &critical_fin_queue);
1578
1579         TV_GETTIME (atv);
1580         time_minor_scan_pinned += TV_ELAPSED (btv, atv);
1581
1582         enqueue_scan_from_roots_jobs (sgen_get_nursery_start (), nursery_next, object_ops, FALSE);
1583
1584         TV_GETTIME (btv);
1585         time_minor_scan_roots += TV_ELAPSED (atv, btv);
1586
1587         finish_gray_stack (GENERATION_NURSERY, ctx);
1588
1589         TV_GETTIME (atv);
1590         time_minor_finish_gray_stack += TV_ELAPSED (btv, atv);
1591         sgen_client_binary_protocol_mark_end (GENERATION_NURSERY);
1592
1593         if (objects_pinned) {
1594                 sgen_optimize_pin_queue ();
1595                 sgen_pinning_setup_section (nursery_section);
1596         }
1597
1598         /* walk the pin_queue, build up the fragment list of free memory, unmark
1599          * pinned objects as we go, memzero() the empty fragments so they are ready for the
1600          * next allocations.
1601          */
1602         sgen_client_binary_protocol_reclaim_start (GENERATION_NURSERY);
1603         fragment_total = sgen_build_nursery_fragments (nursery_section, unpin_queue);
1604         if (!fragment_total)
1605                 degraded_mode = 1;
1606
1607         /* Clear TLABs for all threads */
1608         sgen_clear_tlabs ();
1609
1610         sgen_client_binary_protocol_reclaim_end (GENERATION_NURSERY);
1611         TV_GETTIME (btv);
1612         time_minor_fragment_creation += TV_ELAPSED (atv, btv);
1613         SGEN_LOG (2, "Fragment creation: %lld usecs, %lu bytes available", (long long)TV_ELAPSED (atv, btv), (unsigned long)fragment_total);
1614
1615         if (consistency_check_at_minor_collection)
1616                 sgen_check_major_refs ();
1617
1618         major_collector.finish_nursery_collection ();
1619
1620         TV_GETTIME (last_minor_collection_end_tv);
1621         gc_stats.minor_gc_time += TV_ELAPSED (last_minor_collection_start_tv, last_minor_collection_end_tv);
1622
1623         sgen_debug_dump_heap ("minor", gc_stats.minor_gc_count - 1, NULL);
1624
1625         /* prepare the pin queue for the next collection */
1626         sgen_finish_pinning ();
1627         if (sgen_have_pending_finalizers ()) {
1628                 SGEN_LOG (4, "Finalizer-thread wakeup");
1629                 sgen_client_finalize_notify ();
1630         }
1631         sgen_pin_stats_reset ();
1632         /* clear cemented hash */
1633         sgen_cement_clear_below_threshold ();
1634
1635         g_assert (sgen_gray_object_queue_is_empty (&gray_queue));
1636
1637         remset.finish_minor_collection ();
1638
1639         check_scan_starts ();
1640
1641         binary_protocol_flush_buffers (FALSE);
1642
1643         sgen_memgov_minor_collection_end (reason, is_overflow);
1644
1645         /*objects are late pinned because of lack of memory, so a major is a good call*/
1646         needs_major = objects_pinned > 0;
1647         current_collection_generation = -1;
1648         objects_pinned = 0;
1649
1650         binary_protocol_collection_end (gc_stats.minor_gc_count - 1, GENERATION_NURSERY, 0, 0);
1651
1652         if (check_nursery_objects_pinned && !sgen_minor_collector.is_split)
1653                 sgen_check_nursery_objects_pinned (unpin_queue != NULL);
1654
1655         return needs_major;
1656 }
1657
1658 typedef enum {
1659         COPY_OR_MARK_FROM_ROOTS_SERIAL,
1660         COPY_OR_MARK_FROM_ROOTS_START_CONCURRENT,
1661         COPY_OR_MARK_FROM_ROOTS_FINISH_CONCURRENT
1662 } CopyOrMarkFromRootsMode;
1663
1664 static void
1665 major_copy_or_mark_from_roots (size_t *old_next_pin_slot, CopyOrMarkFromRootsMode mode, SgenObjectOperations *object_ops)
1666 {
1667         LOSObject *bigobj;
1668         TV_DECLARE (atv);
1669         TV_DECLARE (btv);
1670         /* FIXME: only use these values for the precise scan
1671          * note that to_space pointers should be excluded anyway...
1672          */
1673         char *heap_start = NULL;
1674         char *heap_end = (char*)-1;
1675         ScanCopyContext ctx = CONTEXT_FROM_OBJECT_OPERATIONS (object_ops, WORKERS_DISTRIBUTE_GRAY_QUEUE);
1676         gboolean concurrent = mode != COPY_OR_MARK_FROM_ROOTS_SERIAL;
1677
1678         SGEN_ASSERT (0, !!concurrent == !!concurrent_collection_in_progress, "We've been called with the wrong mode.");
1679
1680         if (mode == COPY_OR_MARK_FROM_ROOTS_START_CONCURRENT) {
1681                 /*This cleans up unused fragments */
1682                 sgen_nursery_allocator_prepare_for_pinning ();
1683
1684                 if (do_concurrent_checks)
1685                         sgen_debug_check_nursery_is_clean ();
1686         } else {
1687                 /* The concurrent collector doesn't touch the nursery. */
1688                 sgen_nursery_alloc_prepare_for_major ();
1689         }
1690
1691         init_gray_queue (mode == COPY_OR_MARK_FROM_ROOTS_START_CONCURRENT);
1692
1693         TV_GETTIME (atv);
1694
1695         /* Pinning depends on this */
1696         sgen_clear_nursery_fragments ();
1697
1698         if (whole_heap_check_before_collection)
1699                 sgen_check_whole_heap (mode == COPY_OR_MARK_FROM_ROOTS_FINISH_CONCURRENT);
1700
1701         TV_GETTIME (btv);
1702         time_major_pre_collection_fragment_clear += TV_ELAPSED (atv, btv);
1703
1704         if (!sgen_collection_is_concurrent ())
1705                 nursery_section->next_data = sgen_get_nursery_end ();
1706         /* we should also coalesce scanning from sections close to each other
1707          * and deal with pointers outside of the sections later.
1708          */
1709
1710         objects_pinned = 0;
1711
1712         sgen_client_pre_collection_checks ();
1713
1714         if (mode != COPY_OR_MARK_FROM_ROOTS_START_CONCURRENT) {
1715                 /* Remsets are not useful for a major collection */
1716                 remset.clear_cards ();
1717         }
1718
1719         sgen_process_fin_stage_entries ();
1720
1721         TV_GETTIME (atv);
1722         sgen_init_pinning ();
1723         SGEN_LOG (6, "Collecting pinned addresses");
1724         pin_from_roots ((void*)lowest_heap_address, (void*)highest_heap_address, ctx);
1725         if (mode == COPY_OR_MARK_FROM_ROOTS_FINISH_CONCURRENT) {
1726                 /* Pin cemented objects that were forced */
1727                 sgen_pin_cemented_objects ();
1728         }
1729         sgen_optimize_pin_queue ();
1730         if (mode == COPY_OR_MARK_FROM_ROOTS_START_CONCURRENT) {
1731                 /*
1732                  * Cemented objects that are in the pinned list will be marked. When
1733                  * marking concurrently we won't mark mod-union cards for these objects.
1734                  * Instead they will remain cemented until the next major collection,
1735                  * when we will recheck if they are still pinned in the roots.
1736                  */
1737                 sgen_cement_force_pinned ();
1738         }
1739
1740         sgen_client_collecting_major_1 ();
1741
1742         /*
1743          * pin_queue now contains all candidate pointers, sorted and
1744          * uniqued.  We must do two passes now to figure out which
1745          * objects are pinned.
1746          *
1747          * The first is to find within the pin_queue the area for each
1748          * section.  This requires that the pin_queue be sorted.  We
1749          * also process the LOS objects and pinned chunks here.
1750          *
1751          * The second, destructive, pass is to reduce the section
1752          * areas to pointers to the actually pinned objects.
1753          */
1754         SGEN_LOG (6, "Pinning from sections");
1755         /* first pass for the sections */
1756         sgen_find_section_pin_queue_start_end (nursery_section);
1757         /* identify possible pointers to the insize of large objects */
1758         SGEN_LOG (6, "Pinning from large objects");
1759         for (bigobj = los_object_list; bigobj; bigobj = bigobj->next) {
1760                 size_t dummy;
1761                 if (sgen_find_optimized_pin_queue_area ((char*)bigobj->data, (char*)bigobj->data + sgen_los_object_size (bigobj), &dummy, &dummy)) {
1762                         binary_protocol_pin (bigobj->data, (gpointer)LOAD_VTABLE (bigobj->data), safe_object_get_size (bigobj->data));
1763
1764                         if (sgen_los_object_is_pinned (bigobj->data)) {
1765                                 SGEN_ASSERT (0, mode == COPY_OR_MARK_FROM_ROOTS_FINISH_CONCURRENT, "LOS objects can only be pinned here after concurrent marking.");
1766                                 continue;
1767                         }
1768                         sgen_los_pin_object (bigobj->data);
1769                         if (SGEN_OBJECT_HAS_REFERENCES (bigobj->data))
1770                                 GRAY_OBJECT_ENQUEUE (WORKERS_DISTRIBUTE_GRAY_QUEUE, bigobj->data, sgen_obj_get_descriptor ((GCObject*)bigobj->data));
1771                         sgen_pin_stats_register_object (bigobj->data, GENERATION_OLD);
1772                         SGEN_LOG (6, "Marked large object %p (%s) size: %lu from roots", bigobj->data,
1773                                         sgen_client_vtable_get_name (SGEN_LOAD_VTABLE (bigobj->data)),
1774                                         (unsigned long)sgen_los_object_size (bigobj));
1775
1776                         sgen_client_pinned_los_object (bigobj->data);
1777                 }
1778         }
1779
1780         pin_objects_in_nursery (mode == COPY_OR_MARK_FROM_ROOTS_START_CONCURRENT, ctx);
1781         if (check_nursery_objects_pinned && !sgen_minor_collector.is_split)
1782                 sgen_check_nursery_objects_pinned (mode != COPY_OR_MARK_FROM_ROOTS_START_CONCURRENT);
1783
1784         major_collector.pin_objects (WORKERS_DISTRIBUTE_GRAY_QUEUE);
1785         if (old_next_pin_slot)
1786                 *old_next_pin_slot = sgen_get_pinned_count ();
1787
1788         TV_GETTIME (btv);
1789         time_major_pinning += TV_ELAPSED (atv, btv);
1790         SGEN_LOG (2, "Finding pinned pointers: %zd in %lld usecs", sgen_get_pinned_count (), (long long)TV_ELAPSED (atv, btv));
1791         SGEN_LOG (4, "Start scan with %zd pinned objects", sgen_get_pinned_count ());
1792
1793         major_collector.init_to_space ();
1794
1795         SGEN_ASSERT (0, sgen_workers_all_done (), "Why are the workers not done when we start or finish a major collection?");
1796         if (mode == COPY_OR_MARK_FROM_ROOTS_FINISH_CONCURRENT) {
1797                 if (sgen_workers_have_idle_work ()) {
1798                         /*
1799                          * We force the finish of the worker with the new object ops context
1800                          * which can also do copying. We need to have finished pinning.
1801                          */
1802                         sgen_workers_start_all_workers (object_ops, NULL);
1803                         sgen_workers_join ();
1804                 }
1805         }
1806
1807 #ifdef SGEN_DEBUG_INTERNAL_ALLOC
1808         main_gc_thread = mono_native_thread_self ();
1809 #endif
1810
1811         sgen_client_collecting_major_2 ();
1812
1813         TV_GETTIME (atv);
1814         time_major_scan_pinned += TV_ELAPSED (btv, atv);
1815
1816         sgen_client_collecting_major_3 (&fin_ready_queue, &critical_fin_queue);
1817
1818         enqueue_scan_from_roots_jobs (heap_start, heap_end, object_ops, FALSE);
1819
1820         TV_GETTIME (btv);
1821         time_major_scan_roots += TV_ELAPSED (atv, btv);
1822
1823         /*
1824          * We start the concurrent worker after pinning and after we scanned the roots
1825          * in order to make sure that the worker does not finish before handling all
1826          * the roots.
1827          */
1828         if (mode == COPY_OR_MARK_FROM_ROOTS_START_CONCURRENT) {
1829                 if (precleaning_enabled) {
1830                         ScanJob *sj;
1831                         /* Mod union preclean job */
1832                         sj = (ScanJob*)sgen_thread_pool_job_alloc ("preclean mod union cardtable", job_mod_union_preclean, sizeof (ScanJob));
1833                         sj->ops = object_ops;
1834                         sgen_workers_start_all_workers (object_ops, &sj->job);
1835                 } else {
1836                         sgen_workers_start_all_workers (object_ops, NULL);
1837                 }
1838                 gray_queue_enable_redirect (WORKERS_DISTRIBUTE_GRAY_QUEUE);
1839         }
1840
1841         if (mode == COPY_OR_MARK_FROM_ROOTS_FINISH_CONCURRENT) {
1842                 ScanJob *sj;
1843
1844                 /* Mod union card table */
1845                 sj = (ScanJob*)sgen_thread_pool_job_alloc ("scan mod union cardtable", job_scan_major_mod_union_card_table, sizeof (ScanJob));
1846                 sj->ops = object_ops;
1847                 sgen_workers_enqueue_job (&sj->job, FALSE);
1848
1849                 sj = (ScanJob*)sgen_thread_pool_job_alloc ("scan LOS mod union cardtable", job_scan_los_mod_union_card_table, sizeof (ScanJob));
1850                 sj->ops = object_ops;
1851                 sgen_workers_enqueue_job (&sj->job, FALSE);
1852
1853                 TV_GETTIME (atv);
1854                 time_major_scan_mod_union += TV_ELAPSED (btv, atv);
1855         }
1856
1857         sgen_pin_stats_report ();
1858 }
1859
1860 static void
1861 major_finish_copy_or_mark (CopyOrMarkFromRootsMode mode)
1862 {
1863         if (mode == COPY_OR_MARK_FROM_ROOTS_START_CONCURRENT) {
1864                 sgen_finish_pinning ();
1865
1866                 sgen_pin_stats_reset ();
1867
1868                 if (do_concurrent_checks)
1869                         sgen_debug_check_nursery_is_clean ();
1870         }
1871 }
1872
1873 static void
1874 major_start_collection (const char *reason, gboolean concurrent, size_t *old_next_pin_slot)
1875 {
1876         SgenObjectOperations *object_ops;
1877
1878         binary_protocol_collection_begin (gc_stats.major_gc_count, GENERATION_OLD);
1879
1880         current_collection_generation = GENERATION_OLD;
1881
1882         g_assert (sgen_section_gray_queue_is_empty (sgen_workers_get_distribute_section_gray_queue ()));
1883
1884         if (!concurrent)
1885                 sgen_cement_reset ();
1886
1887         if (concurrent) {
1888                 g_assert (major_collector.is_concurrent);
1889                 concurrent_collection_in_progress = TRUE;
1890
1891                 object_ops = &major_collector.major_ops_concurrent_start;
1892         } else {
1893                 object_ops = &major_collector.major_ops_serial;
1894         }
1895
1896         reset_pinned_from_failed_allocation ();
1897
1898         sgen_memgov_major_collection_start (concurrent, reason);
1899
1900         //count_ref_nonref_objs ();
1901         //consistency_check ();
1902
1903         check_scan_starts ();
1904
1905         degraded_mode = 0;
1906         SGEN_LOG (1, "Start major collection %d", gc_stats.major_gc_count);
1907         gc_stats.major_gc_count ++;
1908
1909         if (major_collector.start_major_collection)
1910                 major_collector.start_major_collection ();
1911
1912         major_copy_or_mark_from_roots (old_next_pin_slot, concurrent ? COPY_OR_MARK_FROM_ROOTS_START_CONCURRENT : COPY_OR_MARK_FROM_ROOTS_SERIAL, object_ops);
1913         major_finish_copy_or_mark (concurrent ? COPY_OR_MARK_FROM_ROOTS_START_CONCURRENT : COPY_OR_MARK_FROM_ROOTS_SERIAL);
1914 }
1915
1916 static void
1917 major_finish_collection (const char *reason, gboolean is_overflow, size_t old_next_pin_slot, gboolean forced)
1918 {
1919         ScannedObjectCounts counts;
1920         SgenObjectOperations *object_ops;
1921         mword fragment_total;
1922         TV_DECLARE (atv);
1923         TV_DECLARE (btv);
1924
1925         TV_GETTIME (btv);
1926
1927         if (concurrent_collection_in_progress) {
1928                 object_ops = &major_collector.major_ops_concurrent_finish;
1929
1930                 major_copy_or_mark_from_roots (NULL, COPY_OR_MARK_FROM_ROOTS_FINISH_CONCURRENT, object_ops);
1931
1932                 major_finish_copy_or_mark (COPY_OR_MARK_FROM_ROOTS_FINISH_CONCURRENT);
1933
1934 #ifdef SGEN_DEBUG_INTERNAL_ALLOC
1935                 main_gc_thread = NULL;
1936 #endif
1937         } else {
1938                 object_ops = &major_collector.major_ops_serial;
1939         }
1940
1941         g_assert (sgen_section_gray_queue_is_empty (sgen_workers_get_distribute_section_gray_queue ()));
1942
1943         /* all the objects in the heap */
1944         finish_gray_stack (GENERATION_OLD, CONTEXT_FROM_OBJECT_OPERATIONS (object_ops, &gray_queue));
1945         TV_GETTIME (atv);
1946         time_major_finish_gray_stack += TV_ELAPSED (btv, atv);
1947
1948         SGEN_ASSERT (0, sgen_workers_all_done (), "Can't have workers working after joining");
1949
1950         if (objects_pinned) {
1951                 g_assert (!concurrent_collection_in_progress);
1952
1953                 /*
1954                  * This is slow, but we just OOM'd.
1955                  *
1956                  * See comment at `sgen_pin_queue_clear_discarded_entries` for how the pin
1957                  * queue is laid out at this point.
1958                  */
1959                 sgen_pin_queue_clear_discarded_entries (nursery_section, old_next_pin_slot);
1960                 /*
1961                  * We need to reestablish all pinned nursery objects in the pin queue
1962                  * because they're needed for fragment creation.  Unpinning happens by
1963                  * walking the whole queue, so it's not necessary to reestablish where major
1964                  * heap block pins are - all we care is that they're still in there
1965                  * somewhere.
1966                  */
1967                 sgen_optimize_pin_queue ();
1968                 sgen_find_section_pin_queue_start_end (nursery_section);
1969                 objects_pinned = 0;
1970         }
1971
1972         reset_heap_boundaries ();
1973         sgen_update_heap_boundaries ((mword)sgen_get_nursery_start (), (mword)sgen_get_nursery_end ());
1974
1975         /* walk the pin_queue, build up the fragment list of free memory, unmark
1976          * pinned objects as we go, memzero() the empty fragments so they are ready for the
1977          * next allocations.
1978          */
1979         fragment_total = sgen_build_nursery_fragments (nursery_section, NULL);
1980         if (!fragment_total)
1981                 degraded_mode = 1;
1982         SGEN_LOG (4, "Free space in nursery after major %ld", (long)fragment_total);
1983
1984         if (do_concurrent_checks && concurrent_collection_in_progress)
1985                 sgen_debug_check_nursery_is_clean ();
1986
1987         /* prepare the pin queue for the next collection */
1988         sgen_finish_pinning ();
1989
1990         /* Clear TLABs for all threads */
1991         sgen_clear_tlabs ();
1992
1993         sgen_pin_stats_reset ();
1994
1995         sgen_cement_clear_below_threshold ();
1996
1997         if (check_mark_bits_after_major_collection)
1998                 sgen_check_heap_marked (concurrent_collection_in_progress);
1999
2000         TV_GETTIME (btv);
2001         time_major_fragment_creation += TV_ELAPSED (atv, btv);
2002
2003         binary_protocol_sweep_begin (GENERATION_OLD, !major_collector.sweeps_lazily);
2004         sgen_memgov_major_pre_sweep ();
2005
2006         TV_GETTIME (atv);
2007         time_major_free_bigobjs += TV_ELAPSED (btv, atv);
2008
2009         sgen_los_sweep ();
2010
2011         TV_GETTIME (btv);
2012         time_major_los_sweep += TV_ELAPSED (atv, btv);
2013
2014         major_collector.sweep ();
2015
2016         binary_protocol_sweep_end (GENERATION_OLD, !major_collector.sweeps_lazily);
2017
2018         TV_GETTIME (atv);
2019         time_major_sweep += TV_ELAPSED (btv, atv);
2020
2021         sgen_debug_dump_heap ("major", gc_stats.major_gc_count - 1, reason);
2022
2023         if (sgen_have_pending_finalizers ()) {
2024                 SGEN_LOG (4, "Finalizer-thread wakeup");
2025                 sgen_client_finalize_notify ();
2026         }
2027
2028         g_assert (sgen_gray_object_queue_is_empty (&gray_queue));
2029
2030         sgen_memgov_major_collection_end (forced, concurrent_collection_in_progress, reason, is_overflow);
2031         current_collection_generation = -1;
2032
2033         memset (&counts, 0, sizeof (ScannedObjectCounts));
2034         major_collector.finish_major_collection (&counts);
2035
2036         g_assert (sgen_section_gray_queue_is_empty (sgen_workers_get_distribute_section_gray_queue ()));
2037
2038         SGEN_ASSERT (0, sgen_workers_all_done (), "Can't have workers working after major collection has finished");
2039         if (concurrent_collection_in_progress)
2040                 concurrent_collection_in_progress = FALSE;
2041
2042         check_scan_starts ();
2043
2044         binary_protocol_flush_buffers (FALSE);
2045
2046         //consistency_check ();
2047
2048         binary_protocol_collection_end (gc_stats.major_gc_count - 1, GENERATION_OLD, counts.num_scanned_objects, counts.num_unique_scanned_objects);
2049 }
2050
2051 static gboolean
2052 major_do_collection (const char *reason, gboolean is_overflow, gboolean forced)
2053 {
2054         TV_DECLARE (time_start);
2055         TV_DECLARE (time_end);
2056         size_t old_next_pin_slot;
2057
2058         if (disable_major_collections)
2059                 return FALSE;
2060
2061         if (major_collector.get_and_reset_num_major_objects_marked) {
2062                 long long num_marked = major_collector.get_and_reset_num_major_objects_marked ();
2063                 g_assert (!num_marked);
2064         }
2065
2066         /* world must be stopped already */
2067         TV_GETTIME (time_start);
2068
2069         major_start_collection (reason, FALSE, &old_next_pin_slot);
2070         major_finish_collection (reason, is_overflow, old_next_pin_slot, forced);
2071
2072         TV_GETTIME (time_end);
2073         gc_stats.major_gc_time += TV_ELAPSED (time_start, time_end);
2074
2075         /* FIXME: also report this to the user, preferably in gc-end. */
2076         if (major_collector.get_and_reset_num_major_objects_marked)
2077                 major_collector.get_and_reset_num_major_objects_marked ();
2078
2079         return bytes_pinned_from_failed_allocation > 0;
2080 }
2081
2082 static void
2083 major_start_concurrent_collection (const char *reason)
2084 {
2085         TV_DECLARE (time_start);
2086         TV_DECLARE (time_end);
2087         long long num_objects_marked;
2088
2089         if (disable_major_collections)
2090                 return;
2091
2092         TV_GETTIME (time_start);
2093         SGEN_TV_GETTIME (time_major_conc_collection_start);
2094
2095         num_objects_marked = major_collector.get_and_reset_num_major_objects_marked ();
2096         g_assert (num_objects_marked == 0);
2097
2098         binary_protocol_concurrent_start ();
2099
2100         // FIXME: store reason and pass it when finishing
2101         major_start_collection (reason, TRUE, NULL);
2102
2103         gray_queue_redirect (&gray_queue);
2104
2105         num_objects_marked = major_collector.get_and_reset_num_major_objects_marked ();
2106
2107         TV_GETTIME (time_end);
2108         gc_stats.major_gc_time += TV_ELAPSED (time_start, time_end);
2109
2110         current_collection_generation = -1;
2111 }
2112
2113 /*
2114  * Returns whether the major collection has finished.
2115  */
2116 static gboolean
2117 major_should_finish_concurrent_collection (void)
2118 {
2119         SGEN_ASSERT (0, sgen_gray_object_queue_is_empty (&gray_queue), "Why is the gray queue not empty before we have started doing anything?");
2120         return sgen_workers_all_done ();
2121 }
2122
2123 static void
2124 major_update_concurrent_collection (void)
2125 {
2126         TV_DECLARE (total_start);
2127         TV_DECLARE (total_end);
2128
2129         TV_GETTIME (total_start);
2130
2131         binary_protocol_concurrent_update ();
2132
2133         major_collector.update_cardtable_mod_union ();
2134         sgen_los_update_cardtable_mod_union ();
2135
2136         TV_GETTIME (total_end);
2137         gc_stats.major_gc_time += TV_ELAPSED (total_start, total_end);
2138 }
2139
2140 static void
2141 major_finish_concurrent_collection (gboolean forced)
2142 {
2143         TV_DECLARE (total_start);
2144         TV_DECLARE (total_end);
2145
2146         TV_GETTIME (total_start);
2147
2148         binary_protocol_concurrent_finish ();
2149
2150         /*
2151          * We need to stop all workers since we're updating the cardtable below.
2152          * The workers will be resumed with a finishing pause context to avoid
2153          * additional cardtable and object scanning.
2154          */
2155         sgen_workers_stop_all_workers ();
2156
2157         SGEN_TV_GETTIME (time_major_conc_collection_end);
2158         gc_stats.major_gc_time_concurrent += SGEN_TV_ELAPSED (time_major_conc_collection_start, time_major_conc_collection_end);
2159
2160         major_collector.update_cardtable_mod_union ();
2161         sgen_los_update_cardtable_mod_union ();
2162
2163         if (mod_union_consistency_check)
2164                 sgen_check_mod_union_consistency ();
2165
2166         current_collection_generation = GENERATION_OLD;
2167         sgen_cement_reset ();
2168         major_finish_collection ("finishing", FALSE, -1, forced);
2169
2170         if (whole_heap_check_before_collection)
2171                 sgen_check_whole_heap (FALSE);
2172
2173         TV_GETTIME (total_end);
2174         gc_stats.major_gc_time += TV_ELAPSED (total_start, total_end) - TV_ELAPSED (last_minor_collection_start_tv, last_minor_collection_end_tv);
2175
2176         current_collection_generation = -1;
2177 }
2178
2179 /*
2180  * Ensure an allocation request for @size will succeed by freeing enough memory.
2181  *
2182  * LOCKING: The GC lock MUST be held.
2183  */
2184 void
2185 sgen_ensure_free_space (size_t size, int generation)
2186 {
2187         int generation_to_collect = -1;
2188         const char *reason = NULL;
2189
2190         if (generation == GENERATION_OLD) {
2191                 if (sgen_need_major_collection (size)) {
2192                         reason = "LOS overflow";
2193                         generation_to_collect = GENERATION_OLD;
2194                 }
2195         } else {
2196                 if (degraded_mode) {
2197                         if (sgen_need_major_collection (size)) {
2198                                 reason = "Degraded mode overflow";
2199                                 generation_to_collect = GENERATION_OLD;
2200                         }
2201                 } else if (sgen_need_major_collection (size)) {
2202                         reason = concurrent_collection_in_progress ? "Forced finish concurrent collection" : "Minor allowance";
2203                         generation_to_collect = GENERATION_OLD;
2204                 } else {
2205                         generation_to_collect = GENERATION_NURSERY;
2206                         reason = "Nursery full";
2207                 }
2208         }
2209
2210         if (generation_to_collect == -1) {
2211                 if (concurrent_collection_in_progress && sgen_workers_all_done ()) {
2212                         generation_to_collect = GENERATION_OLD;
2213                         reason = "Finish concurrent collection";
2214                 }
2215         }
2216
2217         if (generation_to_collect == -1)
2218                 return;
2219         sgen_perform_collection (size, generation_to_collect, reason, FALSE);
2220 }
2221
2222 /*
2223  * LOCKING: Assumes the GC lock is held.
2224  */
2225 void
2226 sgen_perform_collection (size_t requested_size, int generation_to_collect, const char *reason, gboolean wait_to_finish)
2227 {
2228         TV_DECLARE (gc_total_start);
2229         TV_DECLARE (gc_total_end);
2230         int overflow_generation_to_collect = -1;
2231         int oldest_generation_collected = generation_to_collect;
2232         const char *overflow_reason = NULL;
2233         gboolean finish_concurrent = concurrent_collection_in_progress && (major_should_finish_concurrent_collection () || generation_to_collect == GENERATION_OLD);
2234
2235         binary_protocol_collection_requested (generation_to_collect, requested_size, wait_to_finish ? 1 : 0);
2236
2237         SGEN_ASSERT (0, generation_to_collect == GENERATION_NURSERY || generation_to_collect == GENERATION_OLD, "What generation is this?");
2238
2239         sgen_stop_world (generation_to_collect);
2240
2241         TV_GETTIME (gc_total_start);
2242
2243         // FIXME: extract overflow reason
2244         // FIXME: minor overflow for concurrent case
2245         if (generation_to_collect == GENERATION_NURSERY && !finish_concurrent) {
2246                 if (concurrent_collection_in_progress)
2247                         major_update_concurrent_collection ();
2248
2249                 if (collect_nursery (reason, FALSE, NULL, FALSE) && !concurrent_collection_in_progress) {
2250                         overflow_generation_to_collect = GENERATION_OLD;
2251                         overflow_reason = "Minor overflow";
2252                 }
2253         } else if (finish_concurrent) {
2254                 major_finish_concurrent_collection (wait_to_finish);
2255                 oldest_generation_collected = GENERATION_OLD;
2256         } else {
2257                 SGEN_ASSERT (0, generation_to_collect == GENERATION_OLD, "We should have handled nursery collections above");
2258                 if (major_collector.is_concurrent && !wait_to_finish) {
2259                         collect_nursery ("Concurrent start", FALSE, NULL, FALSE);
2260                         major_start_concurrent_collection (reason);
2261                         oldest_generation_collected = GENERATION_NURSERY;
2262                 } else if (major_do_collection (reason, FALSE, wait_to_finish)) {
2263                         overflow_generation_to_collect = GENERATION_NURSERY;
2264                         overflow_reason = "Excessive pinning";
2265                 }
2266         }
2267
2268         if (overflow_generation_to_collect != -1) {
2269                 SGEN_ASSERT (0, !concurrent_collection_in_progress, "We don't yet support overflow collections with the concurrent collector");
2270
2271                 /*
2272                  * We need to do an overflow collection, either because we ran out of memory
2273                  * or the nursery is fully pinned.
2274                  */
2275
2276                 if (overflow_generation_to_collect == GENERATION_NURSERY)
2277                         collect_nursery (overflow_reason, TRUE, NULL, FALSE);
2278                 else
2279                         major_do_collection (overflow_reason, TRUE, wait_to_finish);
2280
2281                 oldest_generation_collected = MAX (oldest_generation_collected, overflow_generation_to_collect);
2282         }
2283
2284         SGEN_LOG (2, "Heap size: %lu, LOS size: %lu", (unsigned long)sgen_gc_get_total_heap_allocation (), (unsigned long)los_memory_usage);
2285
2286         /* this also sets the proper pointers for the next allocation */
2287         if (generation_to_collect == GENERATION_NURSERY && !sgen_can_alloc_size (requested_size)) {
2288                 /* TypeBuilder and MonoMethod are killing mcs with fragmentation */
2289                 SGEN_LOG (1, "nursery collection didn't find enough room for %zd alloc (%zd pinned)", requested_size, sgen_get_pinned_count ());
2290                 sgen_dump_pin_queue ();
2291                 degraded_mode = 1;
2292         }
2293
2294         g_assert (sgen_gray_object_queue_is_empty (&gray_queue));
2295
2296         TV_GETTIME (gc_total_end);
2297         time_max = MAX (time_max, TV_ELAPSED (gc_total_start, gc_total_end));
2298
2299         sgen_restart_world (oldest_generation_collected);
2300 }
2301
2302 /*
2303  * ######################################################################
2304  * ########  Memory allocation from the OS
2305  * ######################################################################
2306  * This section of code deals with getting memory from the OS and
2307  * allocating memory for GC-internal data structures.
2308  * Internal memory can be handled with a freelist for small objects.
2309  */
2310
2311 /*
2312  * Debug reporting.
2313  */
2314 G_GNUC_UNUSED static void
2315 report_internal_mem_usage (void)
2316 {
2317         printf ("Internal memory usage:\n");
2318         sgen_report_internal_mem_usage ();
2319         printf ("Pinned memory usage:\n");
2320         major_collector.report_pinned_memory_usage ();
2321 }
2322
2323 /*
2324  * ######################################################################
2325  * ########  Finalization support
2326  * ######################################################################
2327  */
2328
2329 /*
2330  * If the object has been forwarded it means it's still referenced from a root.
2331  * If it is pinned it's still alive as well.
2332  * A LOS object is only alive if we have pinned it.
2333  * Return TRUE if @obj is ready to be finalized.
2334  */
2335 static inline gboolean
2336 sgen_is_object_alive (GCObject *object)
2337 {
2338         if (ptr_in_nursery (object))
2339                 return sgen_nursery_is_object_alive (object);
2340
2341         return sgen_major_is_object_alive (object);
2342 }
2343
2344 /*
2345  * This function returns true if @object is either alive and belongs to the
2346  * current collection - major collections are full heap, so old gen objects
2347  * are never alive during a minor collection.
2348  */
2349 static inline int
2350 sgen_is_object_alive_and_on_current_collection (GCObject *object)
2351 {
2352         if (ptr_in_nursery (object))
2353                 return sgen_nursery_is_object_alive (object);
2354
2355         if (current_collection_generation == GENERATION_NURSERY)
2356                 return FALSE;
2357
2358         return sgen_major_is_object_alive (object);
2359 }
2360
2361
2362 gboolean
2363 sgen_gc_is_object_ready_for_finalization (GCObject *object)
2364 {
2365         return !sgen_is_object_alive (object);
2366 }
2367
2368 void
2369 sgen_queue_finalization_entry (GCObject *obj)
2370 {
2371         gboolean critical = sgen_client_object_has_critical_finalizer (obj);
2372
2373         sgen_pointer_queue_add (critical ? &critical_fin_queue : &fin_ready_queue, obj);
2374
2375         sgen_client_object_queued_for_finalization (obj);
2376 }
2377
2378 gboolean
2379 sgen_object_is_live (GCObject *obj)
2380 {
2381         return sgen_is_object_alive_and_on_current_collection (obj);
2382 }
2383
2384 /*
2385  * `System.GC.WaitForPendingFinalizers` first checks `sgen_have_pending_finalizers()` to
2386  * determine whether it can exit quickly.  The latter must therefore only return FALSE if
2387  * all finalizers have really finished running.
2388  *
2389  * `sgen_gc_invoke_finalizers()` first dequeues a finalizable object, and then finalizes it.
2390  * This means that just checking whether the queues are empty leaves the possibility that an
2391  * object might have been dequeued but not yet finalized.  That's why we need the additional
2392  * flag `pending_unqueued_finalizer`.
2393  */
2394
2395 static volatile gboolean pending_unqueued_finalizer = FALSE;
2396
2397 int
2398 sgen_gc_invoke_finalizers (void)
2399 {
2400         int count = 0;
2401
2402         g_assert (!pending_unqueued_finalizer);
2403
2404         /* FIXME: batch to reduce lock contention */
2405         while (sgen_have_pending_finalizers ()) {
2406                 GCObject *obj;
2407
2408                 LOCK_GC;
2409
2410                 /*
2411                  * We need to set `pending_unqueued_finalizer` before dequeing the
2412                  * finalizable object.
2413                  */
2414                 if (!sgen_pointer_queue_is_empty (&fin_ready_queue)) {
2415                         pending_unqueued_finalizer = TRUE;
2416                         mono_memory_write_barrier ();
2417                         obj = (GCObject *)sgen_pointer_queue_pop (&fin_ready_queue);
2418                 } else if (!sgen_pointer_queue_is_empty (&critical_fin_queue)) {
2419                         pending_unqueued_finalizer = TRUE;
2420                         mono_memory_write_barrier ();
2421                         obj = (GCObject *)sgen_pointer_queue_pop (&critical_fin_queue);
2422                 } else {
2423                         obj = NULL;
2424                 }
2425
2426                 if (obj)
2427                         SGEN_LOG (7, "Finalizing object %p (%s)", obj, sgen_client_vtable_get_name (SGEN_LOAD_VTABLE (obj)));
2428
2429                 UNLOCK_GC;
2430
2431                 if (!obj)
2432                         break;
2433
2434                 count++;
2435                 /* the object is on the stack so it is pinned */
2436                 /*g_print ("Calling finalizer for object: %p (%s)\n", obj, sgen_client_object_safe_name (obj));*/
2437                 sgen_client_run_finalize (obj);
2438         }
2439
2440         if (pending_unqueued_finalizer) {
2441                 mono_memory_write_barrier ();
2442                 pending_unqueued_finalizer = FALSE;
2443         }
2444
2445         return count;
2446 }
2447
2448 gboolean
2449 sgen_have_pending_finalizers (void)
2450 {
2451         return pending_unqueued_finalizer || !sgen_pointer_queue_is_empty (&fin_ready_queue) || !sgen_pointer_queue_is_empty (&critical_fin_queue);
2452 }
2453
2454 /*
2455  * ######################################################################
2456  * ########  registered roots support
2457  * ######################################################################
2458  */
2459
2460 /*
2461  * We do not coalesce roots.
2462  */
2463 int
2464 sgen_register_root (char *start, size_t size, SgenDescriptor descr, int root_type, int source, const char *msg)
2465 {
2466         RootRecord new_root;
2467         int i;
2468         LOCK_GC;
2469         for (i = 0; i < ROOT_TYPE_NUM; ++i) {
2470                 RootRecord *root = (RootRecord *)sgen_hash_table_lookup (&roots_hash [i], start);
2471                 /* we allow changing the size and the descriptor (for thread statics etc) */
2472                 if (root) {
2473                         size_t old_size = root->end_root - start;
2474                         root->end_root = start + size;
2475                         SGEN_ASSERT (0, !!root->root_desc == !!descr, "Can't change whether a root is precise or conservative.");
2476                         SGEN_ASSERT (0, root->source == source, "Can't change a root's source identifier.");
2477                         SGEN_ASSERT (0, !!root->msg == !!msg, "Can't change a root's message.");
2478                         root->root_desc = descr;
2479                         roots_size += size;
2480                         roots_size -= old_size;
2481                         UNLOCK_GC;
2482                         return TRUE;
2483                 }
2484         }
2485
2486         new_root.end_root = start + size;
2487         new_root.root_desc = descr;
2488         new_root.source = source;
2489         new_root.msg = msg;
2490
2491         sgen_hash_table_replace (&roots_hash [root_type], start, &new_root, NULL);
2492         roots_size += size;
2493
2494         SGEN_LOG (3, "Added root for range: %p-%p, descr: %llx  (%d/%d bytes)", start, new_root.end_root, (long long)descr, (int)size, (int)roots_size);
2495
2496         UNLOCK_GC;
2497         return TRUE;
2498 }
2499
2500 void
2501 sgen_deregister_root (char* addr)
2502 {
2503         int root_type;
2504         RootRecord root;
2505
2506         LOCK_GC;
2507         for (root_type = 0; root_type < ROOT_TYPE_NUM; ++root_type) {
2508                 if (sgen_hash_table_remove (&roots_hash [root_type], addr, &root))
2509                         roots_size -= (root.end_root - addr);
2510         }
2511         UNLOCK_GC;
2512 }
2513
2514 /*
2515  * ######################################################################
2516  * ########  Thread handling (stop/start code)
2517  * ######################################################################
2518  */
2519
2520 int
2521 sgen_get_current_collection_generation (void)
2522 {
2523         return current_collection_generation;
2524 }
2525
2526 void*
2527 sgen_thread_register (SgenThreadInfo* info, void *stack_bottom_fallback)
2528 {
2529 #ifndef HAVE_KW_THREAD
2530         info->tlab_start = info->tlab_next = info->tlab_temp_end = info->tlab_real_end = NULL;
2531 #endif
2532
2533         sgen_init_tlab_info (info);
2534
2535         sgen_client_thread_register (info, stack_bottom_fallback);
2536
2537         return info;
2538 }
2539
2540 void
2541 sgen_thread_unregister (SgenThreadInfo *p)
2542 {
2543         sgen_client_thread_unregister (p);
2544 }
2545
2546 /*
2547  * ######################################################################
2548  * ########  Write barriers
2549  * ######################################################################
2550  */
2551
2552 /*
2553  * Note: the write barriers first do the needed GC work and then do the actual store:
2554  * this way the value is visible to the conservative GC scan after the write barrier
2555  * itself. If a GC interrupts the barrier in the middle, value will be kept alive by
2556  * the conservative scan, otherwise by the remembered set scan.
2557  */
2558
2559 void
2560 mono_gc_wbarrier_arrayref_copy (gpointer dest_ptr, gpointer src_ptr, int count)
2561 {
2562         HEAVY_STAT (++stat_wbarrier_arrayref_copy);
2563         /*This check can be done without taking a lock since dest_ptr array is pinned*/
2564         if (ptr_in_nursery (dest_ptr) || count <= 0) {
2565                 mono_gc_memmove_aligned (dest_ptr, src_ptr, count * sizeof (gpointer));
2566                 return;
2567         }
2568
2569 #ifdef SGEN_HEAVY_BINARY_PROTOCOL
2570         if (binary_protocol_is_heavy_enabled ()) {
2571                 int i;
2572                 for (i = 0; i < count; ++i) {
2573                         gpointer dest = (gpointer*)dest_ptr + i;
2574                         gpointer obj = *((gpointer*)src_ptr + i);
2575                         if (obj)
2576                                 binary_protocol_wbarrier (dest, obj, (gpointer)LOAD_VTABLE (obj));
2577                 }
2578         }
2579 #endif
2580
2581         remset.wbarrier_arrayref_copy (dest_ptr, src_ptr, count);
2582 }
2583
2584 void
2585 mono_gc_wbarrier_generic_nostore (gpointer ptr)
2586 {
2587         gpointer obj;
2588
2589         HEAVY_STAT (++stat_wbarrier_generic_store);
2590
2591         sgen_client_wbarrier_generic_nostore_check (ptr);
2592
2593         obj = *(gpointer*)ptr;
2594         if (obj)
2595                 binary_protocol_wbarrier (ptr, obj, (gpointer)LOAD_VTABLE (obj));
2596
2597         /*
2598          * We need to record old->old pointer locations for the
2599          * concurrent collector.
2600          */
2601         if (!ptr_in_nursery (obj) && !concurrent_collection_in_progress) {
2602                 SGEN_LOG (8, "Skipping remset at %p", ptr);
2603                 return;
2604         }
2605
2606         SGEN_LOG (8, "Adding remset at %p", ptr);
2607
2608         remset.wbarrier_generic_nostore (ptr);
2609 }
2610
2611 void
2612 mono_gc_wbarrier_generic_store (gpointer ptr, GCObject* value)
2613 {
2614         SGEN_LOG (8, "Wbarrier store at %p to %p (%s)", ptr, value, value ? sgen_client_vtable_get_name (SGEN_LOAD_VTABLE (value)) : "null");
2615         SGEN_UPDATE_REFERENCE_ALLOW_NULL (ptr, value);
2616         if (ptr_in_nursery (value) || concurrent_collection_in_progress)
2617                 mono_gc_wbarrier_generic_nostore (ptr);
2618         sgen_dummy_use (value);
2619 }
2620
2621 /* Same as mono_gc_wbarrier_generic_store () but performs the store
2622  * as an atomic operation with release semantics.
2623  */
2624 void
2625 mono_gc_wbarrier_generic_store_atomic (gpointer ptr, GCObject *value)
2626 {
2627         HEAVY_STAT (++stat_wbarrier_generic_store_atomic);
2628
2629         SGEN_LOG (8, "Wbarrier atomic store at %p to %p (%s)", ptr, value, value ? sgen_client_vtable_get_name (SGEN_LOAD_VTABLE (value)) : "null");
2630
2631         InterlockedWritePointer ((volatile gpointer *)ptr, value);
2632
2633         if (ptr_in_nursery (value) || concurrent_collection_in_progress)
2634                 mono_gc_wbarrier_generic_nostore (ptr);
2635
2636         sgen_dummy_use (value);
2637 }
2638
2639 void
2640 sgen_wbarrier_value_copy_bitmap (gpointer _dest, gpointer _src, int size, unsigned bitmap)
2641 {
2642         GCObject **dest = (GCObject **)_dest;
2643         GCObject **src = (GCObject **)_src;
2644
2645         while (size) {
2646                 if (bitmap & 0x1)
2647                         mono_gc_wbarrier_generic_store (dest, *src);
2648                 else
2649                         *dest = *src;
2650                 ++src;
2651                 ++dest;
2652                 size -= SIZEOF_VOID_P;
2653                 bitmap >>= 1;
2654         }
2655 }
2656
2657 /*
2658  * ######################################################################
2659  * ########  Other mono public interface functions.
2660  * ######################################################################
2661  */
2662
2663 void
2664 sgen_gc_collect (int generation)
2665 {
2666         LOCK_GC;
2667         if (generation > 1)
2668                 generation = 1;
2669         sgen_perform_collection (0, generation, "user request", TRUE);
2670         UNLOCK_GC;
2671 }
2672
2673 int
2674 sgen_gc_collection_count (int generation)
2675 {
2676         if (generation == 0)
2677                 return gc_stats.minor_gc_count;
2678         return gc_stats.major_gc_count;
2679 }
2680
2681 size_t
2682 sgen_gc_get_used_size (void)
2683 {
2684         gint64 tot = 0;
2685         LOCK_GC;
2686         tot = los_memory_usage;
2687         tot += nursery_section->next_data - nursery_section->data;
2688         tot += major_collector.get_used_size ();
2689         /* FIXME: account for pinned objects */
2690         UNLOCK_GC;
2691         return tot;
2692 }
2693
2694 void
2695 sgen_env_var_error (const char *env_var, const char *fallback, const char *description_format, ...)
2696 {
2697         va_list ap;
2698
2699         va_start (ap, description_format);
2700
2701         fprintf (stderr, "Warning: In environment variable `%s': ", env_var);
2702         vfprintf (stderr, description_format, ap);
2703         if (fallback)
2704                 fprintf (stderr, " - %s", fallback);
2705         fprintf (stderr, "\n");
2706
2707         va_end (ap);
2708 }
2709
2710 static gboolean
2711 parse_double_in_interval (const char *env_var, const char *opt_name, const char *opt, double min, double max, double *result)
2712 {
2713         char *endptr;
2714         double val = strtod (opt, &endptr);
2715         if (endptr == opt) {
2716                 sgen_env_var_error (env_var, "Using default value.", "`%s` must be a number.", opt_name);
2717                 return FALSE;
2718         }
2719         else if (val < min || val > max) {
2720                 sgen_env_var_error (env_var, "Using default value.", "`%s` must be between %.2f - %.2f.", opt_name, min, max);
2721                 return FALSE;
2722         }
2723         *result = val;
2724         return TRUE;
2725 }
2726
2727 void
2728 sgen_gc_init (void)
2729 {
2730         const char *env;
2731         char **opts, **ptr;
2732         char *major_collector_opt = NULL;
2733         char *minor_collector_opt = NULL;
2734         size_t max_heap = 0;
2735         size_t soft_limit = 0;
2736         int result;
2737         gboolean debug_print_allowance = FALSE;
2738         double allowance_ratio = 0, save_target = 0;
2739         gboolean cement_enabled = TRUE;
2740
2741         do {
2742                 result = InterlockedCompareExchange (&gc_initialized, -1, 0);
2743                 switch (result) {
2744                 case 1:
2745                         /* already inited */
2746                         return;
2747                 case -1:
2748                         /* being inited by another thread */
2749                         mono_thread_info_usleep (1000);
2750                         break;
2751                 case 0:
2752                         /* we will init it */
2753                         break;
2754                 default:
2755                         g_assert_not_reached ();
2756                 }
2757         } while (result != 0);
2758
2759         SGEN_TV_GETTIME (sgen_init_timestamp);
2760
2761 #ifdef SGEN_WITHOUT_MONO
2762         mono_thread_smr_init ();
2763 #endif
2764
2765         mono_coop_mutex_init (&gc_mutex);
2766
2767         gc_debug_file = stderr;
2768
2769         mono_coop_mutex_init (&sgen_interruption_mutex);
2770
2771         if ((env = g_getenv (MONO_GC_PARAMS_NAME))) {
2772                 opts = g_strsplit (env, ",", -1);
2773                 for (ptr = opts; *ptr; ++ptr) {
2774                         char *opt = *ptr;
2775                         if (g_str_has_prefix (opt, "major=")) {
2776                                 opt = strchr (opt, '=') + 1;
2777                                 major_collector_opt = g_strdup (opt);
2778                         } else if (g_str_has_prefix (opt, "minor=")) {
2779                                 opt = strchr (opt, '=') + 1;
2780                                 minor_collector_opt = g_strdup (opt);
2781                         }
2782                 }
2783         } else {
2784                 opts = NULL;
2785         }
2786
2787         init_stats ();
2788         sgen_init_internal_allocator ();
2789         sgen_init_nursery_allocator ();
2790         sgen_init_fin_weak_hash ();
2791         sgen_init_hash_table ();
2792         sgen_init_descriptors ();
2793         sgen_init_gray_queues ();
2794         sgen_init_allocator ();
2795         sgen_init_gchandles ();
2796
2797         sgen_register_fixed_internal_mem_type (INTERNAL_MEM_SECTION, SGEN_SIZEOF_GC_MEM_SECTION);
2798         sgen_register_fixed_internal_mem_type (INTERNAL_MEM_GRAY_QUEUE, sizeof (GrayQueueSection));
2799
2800         sgen_client_init ();
2801
2802         if (!minor_collector_opt) {
2803                 sgen_simple_nursery_init (&sgen_minor_collector);
2804         } else {
2805                 if (!strcmp (minor_collector_opt, "simple")) {
2806                 use_simple_nursery:
2807                         sgen_simple_nursery_init (&sgen_minor_collector);
2808                 } else if (!strcmp (minor_collector_opt, "split")) {
2809                         sgen_split_nursery_init (&sgen_minor_collector);
2810                 } else {
2811                         sgen_env_var_error (MONO_GC_PARAMS_NAME, "Using `simple` instead.", "Unknown minor collector `%s'.", minor_collector_opt);
2812                         goto use_simple_nursery;
2813                 }
2814         }
2815
2816         if (!major_collector_opt || !strcmp (major_collector_opt, "marksweep")) {
2817         use_marksweep_major:
2818                 sgen_marksweep_init (&major_collector);
2819         } else if (!major_collector_opt || !strcmp (major_collector_opt, "marksweep-conc")) {
2820                 sgen_marksweep_conc_init (&major_collector);
2821         } else {
2822                 sgen_env_var_error (MONO_GC_PARAMS_NAME, "Using `marksweep` instead.", "Unknown major collector `%s'.", major_collector_opt);
2823                 goto use_marksweep_major;
2824         }
2825
2826         sgen_nursery_size = DEFAULT_NURSERY_SIZE;
2827
2828         if (opts) {
2829                 gboolean usage_printed = FALSE;
2830
2831                 for (ptr = opts; *ptr; ++ptr) {
2832                         char *opt = *ptr;
2833                         if (!strcmp (opt, ""))
2834                                 continue;
2835                         if (g_str_has_prefix (opt, "major="))
2836                                 continue;
2837                         if (g_str_has_prefix (opt, "minor="))
2838                                 continue;
2839                         if (g_str_has_prefix (opt, "max-heap-size=")) {
2840                                 size_t page_size = mono_pagesize ();
2841                                 size_t max_heap_candidate = 0;
2842                                 opt = strchr (opt, '=') + 1;
2843                                 if (*opt && mono_gc_parse_environment_string_extract_number (opt, &max_heap_candidate)) {
2844                                         max_heap = (max_heap_candidate + page_size - 1) & ~(size_t)(page_size - 1);
2845                                         if (max_heap != max_heap_candidate)
2846                                                 sgen_env_var_error (MONO_GC_PARAMS_NAME, "Rounding up.", "`max-heap-size` size must be a multiple of %d.", page_size);
2847                                 } else {
2848                                         sgen_env_var_error (MONO_GC_PARAMS_NAME, NULL, "`max-heap-size` must be an integer.");
2849                                 }
2850                                 continue;
2851                         }
2852                         if (g_str_has_prefix (opt, "soft-heap-limit=")) {
2853                                 opt = strchr (opt, '=') + 1;
2854                                 if (*opt && mono_gc_parse_environment_string_extract_number (opt, &soft_limit)) {
2855                                         if (soft_limit <= 0) {
2856                                                 sgen_env_var_error (MONO_GC_PARAMS_NAME, NULL, "`soft-heap-limit` must be positive.");
2857                                                 soft_limit = 0;
2858                                         }
2859                                 } else {
2860                                         sgen_env_var_error (MONO_GC_PARAMS_NAME, NULL, "`soft-heap-limit` must be an integer.");
2861                                 }
2862                                 continue;
2863                         }
2864
2865 #ifdef USER_CONFIG
2866                         if (g_str_has_prefix (opt, "nursery-size=")) {
2867                                 size_t val;
2868                                 opt = strchr (opt, '=') + 1;
2869                                 if (*opt && mono_gc_parse_environment_string_extract_number (opt, &val)) {
2870                                         if ((val & (val - 1))) {
2871                                                 sgen_env_var_error (MONO_GC_PARAMS_NAME, "Using default value.", "`nursery-size` must be a power of two.");
2872                                                 continue;
2873                                         }
2874
2875                                         if (val < SGEN_MAX_NURSERY_WASTE) {
2876                                                 sgen_env_var_error (MONO_GC_PARAMS_NAME, "Using default value.",
2877                                                                 "`nursery-size` must be at least %d bytes.", SGEN_MAX_NURSERY_WASTE);
2878                                                 continue;
2879                                         }
2880
2881                                         sgen_nursery_size = val;
2882                                         sgen_nursery_bits = 0;
2883                                         while (ONE_P << (++ sgen_nursery_bits) != sgen_nursery_size)
2884                                                 ;
2885                                 } else {
2886                                         sgen_env_var_error (MONO_GC_PARAMS_NAME, "Using default value.", "`nursery-size` must be an integer.");
2887                                         continue;
2888                                 }
2889                                 continue;
2890                         }
2891 #endif
2892                         if (g_str_has_prefix (opt, "save-target-ratio=")) {
2893                                 double val;
2894                                 opt = strchr (opt, '=') + 1;
2895                                 if (parse_double_in_interval (MONO_GC_PARAMS_NAME, "save-target-ratio", opt,
2896                                                 SGEN_MIN_SAVE_TARGET_RATIO, SGEN_MAX_SAVE_TARGET_RATIO, &val)) {
2897                                         save_target = val;
2898                                 }
2899                                 continue;
2900                         }
2901                         if (g_str_has_prefix (opt, "default-allowance-ratio=")) {
2902                                 double val;
2903                                 opt = strchr (opt, '=') + 1;
2904                                 if (parse_double_in_interval (MONO_GC_PARAMS_NAME, "default-allowance-ratio", opt,
2905                                                 SGEN_MIN_ALLOWANCE_NURSERY_SIZE_RATIO, SGEN_MIN_ALLOWANCE_NURSERY_SIZE_RATIO, &val)) {
2906                                         allowance_ratio = val;
2907                                 }
2908                                 continue;
2909                         }
2910
2911                         if (!strcmp (opt, "cementing")) {
2912                                 cement_enabled = TRUE;
2913                                 continue;
2914                         }
2915                         if (!strcmp (opt, "no-cementing")) {
2916                                 cement_enabled = FALSE;
2917                                 continue;
2918                         }
2919
2920                         if (!strcmp (opt, "precleaning")) {
2921                                 precleaning_enabled = TRUE;
2922                                 continue;
2923                         }
2924                         if (!strcmp (opt, "no-precleaning")) {
2925                                 precleaning_enabled = FALSE;
2926                                 continue;
2927                         }
2928
2929                         if (major_collector.handle_gc_param && major_collector.handle_gc_param (opt))
2930                                 continue;
2931
2932                         if (sgen_minor_collector.handle_gc_param && sgen_minor_collector.handle_gc_param (opt))
2933                                 continue;
2934
2935                         if (sgen_client_handle_gc_param (opt))
2936                                 continue;
2937
2938                         sgen_env_var_error (MONO_GC_PARAMS_NAME, "Ignoring.", "Unknown option `%s`.", opt);
2939
2940                         if (usage_printed)
2941                                 continue;
2942
2943                         fprintf (stderr, "\n%s must be a comma-delimited list of one or more of the following:\n", MONO_GC_PARAMS_NAME);
2944                         fprintf (stderr, "  max-heap-size=N (where N is an integer, possibly with a k, m or a g suffix)\n");
2945                         fprintf (stderr, "  soft-heap-limit=n (where N is an integer, possibly with a k, m or a g suffix)\n");
2946                         fprintf (stderr, "  nursery-size=N (where N is an integer, possibly with a k, m or a g suffix)\n");
2947                         fprintf (stderr, "  major=COLLECTOR (where COLLECTOR is `marksweep', `marksweep-conc', `marksweep-par')\n");
2948                         fprintf (stderr, "  minor=COLLECTOR (where COLLECTOR is `simple' or `split')\n");
2949                         fprintf (stderr, "  wbarrier=WBARRIER (where WBARRIER is `remset' or `cardtable')\n");
2950                         fprintf (stderr, "  [no-]cementing\n");
2951                         if (major_collector.print_gc_param_usage)
2952                                 major_collector.print_gc_param_usage ();
2953                         if (sgen_minor_collector.print_gc_param_usage)
2954                                 sgen_minor_collector.print_gc_param_usage ();
2955                         sgen_client_print_gc_params_usage ();
2956                         fprintf (stderr, " Experimental options:\n");
2957                         fprintf (stderr, "  save-target-ratio=R (where R must be between %.2f - %.2f).\n", SGEN_MIN_SAVE_TARGET_RATIO, SGEN_MAX_SAVE_TARGET_RATIO);
2958                         fprintf (stderr, "  default-allowance-ratio=R (where R must be between %.2f - %.2f).\n", SGEN_MIN_ALLOWANCE_NURSERY_SIZE_RATIO, SGEN_MAX_ALLOWANCE_NURSERY_SIZE_RATIO);
2959                         fprintf (stderr, "\n");
2960
2961                         usage_printed = TRUE;
2962                 }
2963                 g_strfreev (opts);
2964         }
2965
2966         if (major_collector_opt)
2967                 g_free (major_collector_opt);
2968
2969         if (minor_collector_opt)
2970                 g_free (minor_collector_opt);
2971
2972         alloc_nursery ();
2973
2974         sgen_pinning_init ();
2975         sgen_cement_init (cement_enabled);
2976
2977         if ((env = g_getenv (MONO_GC_DEBUG_NAME))) {
2978                 gboolean usage_printed = FALSE;
2979
2980                 opts = g_strsplit (env, ",", -1);
2981                 for (ptr = opts; ptr && *ptr; ptr ++) {
2982                         char *opt = *ptr;
2983                         if (!strcmp (opt, ""))
2984                                 continue;
2985                         if (opt [0] >= '0' && opt [0] <= '9') {
2986                                 gc_debug_level = atoi (opt);
2987                                 opt++;
2988                                 if (opt [0] == ':')
2989                                         opt++;
2990                                 if (opt [0]) {
2991                                         char *rf = g_strdup_printf ("%s.%d", opt, mono_process_current_pid ());
2992                                         gc_debug_file = fopen (rf, "wb");
2993                                         if (!gc_debug_file)
2994                                                 gc_debug_file = stderr;
2995                                         g_free (rf);
2996                                 }
2997                         } else if (!strcmp (opt, "print-allowance")) {
2998                                 debug_print_allowance = TRUE;
2999                         } else if (!strcmp (opt, "print-pinning")) {
3000                                 sgen_pin_stats_enable ();
3001                         } else if (!strcmp (opt, "verify-before-allocs")) {
3002                                 verify_before_allocs = 1;
3003                                 has_per_allocation_action = TRUE;
3004                         } else if (g_str_has_prefix (opt, "verify-before-allocs=")) {
3005                                 char *arg = strchr (opt, '=') + 1;
3006                                 verify_before_allocs = atoi (arg);
3007                                 has_per_allocation_action = TRUE;
3008                         } else if (!strcmp (opt, "collect-before-allocs")) {
3009                                 collect_before_allocs = 1;
3010                                 has_per_allocation_action = TRUE;
3011                         } else if (g_str_has_prefix (opt, "collect-before-allocs=")) {
3012                                 char *arg = strchr (opt, '=') + 1;
3013                                 has_per_allocation_action = TRUE;
3014                                 collect_before_allocs = atoi (arg);
3015                         } else if (!strcmp (opt, "verify-before-collections")) {
3016                                 whole_heap_check_before_collection = TRUE;
3017                         } else if (!strcmp (opt, "check-at-minor-collections")) {
3018                                 consistency_check_at_minor_collection = TRUE;
3019                                 nursery_clear_policy = CLEAR_AT_GC;
3020                         } else if (!strcmp (opt, "mod-union-consistency-check")) {
3021                                 if (!major_collector.is_concurrent) {
3022                                         sgen_env_var_error (MONO_GC_DEBUG_NAME, "Ignoring.", "`mod-union-consistency-check` only works with concurrent major collector.");
3023                                         continue;
3024                                 }
3025                                 mod_union_consistency_check = TRUE;
3026                         } else if (!strcmp (opt, "check-mark-bits")) {
3027                                 check_mark_bits_after_major_collection = TRUE;
3028                         } else if (!strcmp (opt, "check-nursery-pinned")) {
3029                                 check_nursery_objects_pinned = TRUE;
3030                         } else if (!strcmp (opt, "clear-at-gc")) {
3031                                 nursery_clear_policy = CLEAR_AT_GC;
3032                         } else if (!strcmp (opt, "clear-nursery-at-gc")) {
3033                                 nursery_clear_policy = CLEAR_AT_GC;
3034                         } else if (!strcmp (opt, "clear-at-tlab-creation")) {
3035                                 nursery_clear_policy = CLEAR_AT_TLAB_CREATION;
3036                         } else if (!strcmp (opt, "debug-clear-at-tlab-creation")) {
3037                                 nursery_clear_policy = CLEAR_AT_TLAB_CREATION_DEBUG;
3038                         } else if (!strcmp (opt, "check-scan-starts")) {
3039                                 do_scan_starts_check = TRUE;
3040                         } else if (!strcmp (opt, "verify-nursery-at-minor-gc")) {
3041                                 do_verify_nursery = TRUE;
3042                         } else if (!strcmp (opt, "check-concurrent")) {
3043                                 if (!major_collector.is_concurrent) {
3044                                         sgen_env_var_error (MONO_GC_DEBUG_NAME, "Ignoring.", "`check-concurrent` only works with concurrent major collectors.");
3045                                         continue;
3046                                 }
3047                                 nursery_clear_policy = CLEAR_AT_GC;
3048                                 do_concurrent_checks = TRUE;
3049                         } else if (!strcmp (opt, "dump-nursery-at-minor-gc")) {
3050                                 do_dump_nursery_content = TRUE;
3051                         } else if (!strcmp (opt, "disable-minor")) {
3052                                 disable_minor_collections = TRUE;
3053                         } else if (!strcmp (opt, "disable-major")) {
3054                                 disable_major_collections = TRUE;
3055                         } else if (g_str_has_prefix (opt, "heap-dump=")) {
3056                                 char *filename = strchr (opt, '=') + 1;
3057                                 nursery_clear_policy = CLEAR_AT_GC;
3058                                 sgen_debug_enable_heap_dump (filename);
3059                         } else if (g_str_has_prefix (opt, "binary-protocol=")) {
3060                                 char *filename = strchr (opt, '=') + 1;
3061                                 char *colon = strrchr (filename, ':');
3062                                 size_t limit = 0;
3063                                 if (colon) {
3064                                         if (!mono_gc_parse_environment_string_extract_number (colon + 1, &limit)) {
3065                                                 sgen_env_var_error (MONO_GC_DEBUG_NAME, "Ignoring limit.", "Binary protocol file size limit must be an integer.");
3066                                                 limit = -1;
3067                                         }
3068                                         *colon = '\0';
3069                                 }
3070                                 binary_protocol_init (filename, (long long)limit);
3071                         } else if (!strcmp (opt, "nursery-canaries")) {
3072                                 do_verify_nursery = TRUE;
3073                                 enable_nursery_canaries = TRUE;
3074                         } else if (!sgen_client_handle_gc_debug (opt)) {
3075                                 sgen_env_var_error (MONO_GC_DEBUG_NAME, "Ignoring.", "Unknown option `%s`.", opt);
3076
3077                                 if (usage_printed)
3078                                         continue;
3079
3080                                 fprintf (stderr, "\n%s must be of the format [<l>[:<filename>]|<option>]+ where <l> is a debug level 0-9.\n", MONO_GC_DEBUG_NAME);
3081                                 fprintf (stderr, "Valid <option>s are:\n");
3082                                 fprintf (stderr, "  collect-before-allocs[=<n>]\n");
3083                                 fprintf (stderr, "  verify-before-allocs[=<n>]\n");
3084                                 fprintf (stderr, "  check-at-minor-collections\n");
3085                                 fprintf (stderr, "  check-mark-bits\n");
3086                                 fprintf (stderr, "  check-nursery-pinned\n");
3087                                 fprintf (stderr, "  verify-before-collections\n");
3088                                 fprintf (stderr, "  verify-nursery-at-minor-gc\n");
3089                                 fprintf (stderr, "  dump-nursery-at-minor-gc\n");
3090                                 fprintf (stderr, "  disable-minor\n");
3091                                 fprintf (stderr, "  disable-major\n");
3092                                 fprintf (stderr, "  check-concurrent\n");
3093                                 fprintf (stderr, "  clear-[nursery-]at-gc\n");
3094                                 fprintf (stderr, "  clear-at-tlab-creation\n");
3095                                 fprintf (stderr, "  debug-clear-at-tlab-creation\n");
3096                                 fprintf (stderr, "  check-scan-starts\n");
3097                                 fprintf (stderr, "  print-allowance\n");
3098                                 fprintf (stderr, "  print-pinning\n");
3099                                 fprintf (stderr, "  heap-dump=<filename>\n");
3100                                 fprintf (stderr, "  binary-protocol=<filename>[:<file-size-limit>]\n");
3101                                 fprintf (stderr, "  nursery-canaries\n");
3102                                 sgen_client_print_gc_debug_usage ();
3103                                 fprintf (stderr, "\n");
3104
3105                                 usage_printed = TRUE;
3106                         }
3107                 }
3108                 g_strfreev (opts);
3109         }
3110
3111         if (check_mark_bits_after_major_collection)
3112                 nursery_clear_policy = CLEAR_AT_GC;
3113
3114         if (major_collector.post_param_init)
3115                 major_collector.post_param_init (&major_collector);
3116
3117         if (major_collector.needs_thread_pool)
3118                 sgen_workers_init (1);
3119
3120         sgen_memgov_init (max_heap, soft_limit, debug_print_allowance, allowance_ratio, save_target);
3121
3122         memset (&remset, 0, sizeof (remset));
3123
3124         sgen_card_table_init (&remset);
3125
3126         sgen_register_root (NULL, 0, sgen_make_user_root_descriptor (sgen_mark_normal_gc_handles), ROOT_TYPE_NORMAL, MONO_ROOT_SOURCE_GC_HANDLE, "normal gc handles");
3127
3128         gc_initialized = 1;
3129 }
3130
3131 NurseryClearPolicy
3132 sgen_get_nursery_clear_policy (void)
3133 {
3134         return nursery_clear_policy;
3135 }
3136
3137 void
3138 sgen_gc_lock (void)
3139 {
3140         mono_coop_mutex_lock (&gc_mutex);
3141 }
3142
3143 void
3144 sgen_gc_unlock (void)
3145 {
3146         mono_coop_mutex_unlock (&gc_mutex);
3147 }
3148
3149 void
3150 sgen_major_collector_iterate_live_block_ranges (sgen_cardtable_block_callback callback)
3151 {
3152         major_collector.iterate_live_block_ranges (callback);
3153 }
3154
3155 void
3156 sgen_major_collector_iterate_block_ranges (sgen_cardtable_block_callback callback)
3157 {
3158         major_collector.iterate_block_ranges (callback);
3159 }
3160
3161 SgenMajorCollector*
3162 sgen_get_major_collector (void)
3163 {
3164         return &major_collector;
3165 }
3166
3167 SgenRememberedSet*
3168 sgen_get_remset (void)
3169 {
3170         return &remset;
3171 }
3172
3173 static void
3174 count_cards (long long *major_total, long long *major_marked, long long *los_total, long long *los_marked)
3175 {
3176         sgen_get_major_collector ()->count_cards (major_total, major_marked);
3177         sgen_los_count_cards (los_total, los_marked);
3178 }
3179
3180 static gboolean world_is_stopped = FALSE;
3181
3182 /* LOCKING: assumes the GC lock is held */
3183 void
3184 sgen_stop_world (int generation)
3185 {
3186         long long major_total = -1, major_marked = -1, los_total = -1, los_marked = -1;
3187
3188         SGEN_ASSERT (0, !world_is_stopped, "Why are we stopping a stopped world?");
3189
3190         binary_protocol_world_stopping (generation, sgen_timestamp (), (gpointer) (gsize) mono_native_thread_id_get ());
3191
3192         sgen_client_stop_world (generation);
3193
3194         world_is_stopped = TRUE;
3195
3196         if (binary_protocol_is_heavy_enabled ())
3197                 count_cards (&major_total, &major_marked, &los_total, &los_marked);
3198         binary_protocol_world_stopped (generation, sgen_timestamp (), major_total, major_marked, los_total, los_marked);
3199 }
3200
3201 /* LOCKING: assumes the GC lock is held */
3202 void
3203 sgen_restart_world (int generation)
3204 {
3205         long long major_total = -1, major_marked = -1, los_total = -1, los_marked = -1;
3206         gint64 stw_time;
3207
3208         SGEN_ASSERT (0, world_is_stopped, "Why are we restarting a running world?");
3209
3210         if (binary_protocol_is_heavy_enabled ())
3211                 count_cards (&major_total, &major_marked, &los_total, &los_marked);
3212         binary_protocol_world_restarting (generation, sgen_timestamp (), major_total, major_marked, los_total, los_marked);
3213
3214         world_is_stopped = FALSE;
3215
3216         sgen_client_restart_world (generation, &stw_time);
3217
3218         binary_protocol_world_restarted (generation, sgen_timestamp ());
3219
3220         if (sgen_client_bridge_need_processing ())
3221                 sgen_client_bridge_processing_finish (generation);
3222
3223         sgen_memgov_collection_end (generation, stw_time);
3224 }
3225
3226 gboolean
3227 sgen_is_world_stopped (void)
3228 {
3229         return world_is_stopped;
3230 }
3231
3232 void
3233 sgen_check_whole_heap_stw (void)
3234 {
3235         sgen_stop_world (0);
3236         sgen_clear_nursery_fragments ();
3237         sgen_check_whole_heap (FALSE);
3238         sgen_restart_world (0);
3239 }
3240
3241 gint64
3242 sgen_timestamp (void)
3243 {
3244         SGEN_TV_DECLARE (timestamp);
3245         SGEN_TV_GETTIME (timestamp);
3246         return SGEN_TV_ELAPSED (sgen_init_timestamp, timestamp);
3247 }
3248
3249 #endif /* HAVE_SGEN_GC */