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