Avoid loading AOT images compiled against Boehm in an SGEN runtime, and vice versa...
[mono.git] / mono / metadata / sgen-gc.c
1 /*
2  * sgen-gc.c: Simple generational GC.
3  *
4  * Author:
5  *      Paolo Molaro (lupus@ximian.com)
6  *
7  * Copyright 2005-2010 Novell, Inc (http://www.novell.com)
8  *
9  * Thread start/stop adapted from Boehm's GC:
10  * Copyright (c) 1994 by Xerox Corporation.  All rights reserved.
11  * Copyright (c) 1996 by Silicon Graphics.  All rights reserved.
12  * Copyright (c) 1998 by Fergus Henderson.  All rights reserved.
13  * Copyright (c) 2000-2004 by Hewlett-Packard Company.  All rights reserved.
14  *
15  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
16  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
17  *
18  * Permission is hereby granted to use or copy this program
19  * for any purpose,  provided the above notices are retained on all copies.
20  * Permission to modify the code and to distribute modified code is granted,
21  * provided the above notices are retained, and a notice that the code was
22  * modified is included with the above copyright notice.
23  *
24  *
25  * Copyright 2001-2003 Ximian, Inc
26  * Copyright 2003-2010 Novell, Inc.
27  * 
28  * Permission is hereby granted, free of charge, to any person obtaining
29  * a copy of this software and associated documentation files (the
30  * "Software"), to deal in the Software without restriction, including
31  * without limitation the rights to use, copy, modify, merge, publish,
32  * distribute, sublicense, and/or sell copies of the Software, and to
33  * permit persons to whom the Software is furnished to do so, subject to
34  * the following conditions:
35  * 
36  * The above copyright notice and this permission notice shall be
37  * included in all copies or substantial portions of the Software.
38  * 
39  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
40  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
41  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
42  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
43  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
44  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
45  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
46  *
47  *
48  * Important: allocation provides always zeroed memory, having to do
49  * a memset after allocation is deadly for performance.
50  * Memory usage at startup is currently as follows:
51  * 64 KB pinned space
52  * 64 KB internal space
53  * size of nursery
54  * We should provide a small memory config with half the sizes
55  *
56  * We currently try to make as few mono assumptions as possible:
57  * 1) 2-word header with no GC pointers in it (first vtable, second to store the
58  *    forwarding ptr)
59  * 2) gc descriptor is the second word in the vtable (first word in the class)
60  * 3) 8 byte alignment is the minimum and enough (not true for special structures (SIMD), FIXME)
61  * 4) there is a function to get an object's size and the number of
62  *    elements in an array.
63  * 5) we know the special way bounds are allocated for complex arrays
64  * 6) we know about proxies and how to treat them when domains are unloaded
65  *
66  * Always try to keep stack usage to a minimum: no recursive behaviour
67  * and no large stack allocs.
68  *
69  * General description.
70  * Objects are initially allocated in a nursery using a fast bump-pointer technique.
71  * When the nursery is full we start a nursery collection: this is performed with a
72  * copying GC.
73  * When the old generation is full we start a copying GC of the old generation as well:
74  * this will be changed to mark&sweep with copying when fragmentation becomes to severe
75  * in the future.  Maybe we'll even do both during the same collection like IMMIX.
76  *
77  * The things that complicate this description are:
78  * *) pinned objects: we can't move them so we need to keep track of them
79  * *) no precise info of the thread stacks and registers: we need to be able to
80  *    quickly find the objects that may be referenced conservatively and pin them
81  *    (this makes the first issues more important)
82  * *) large objects are too expensive to be dealt with using copying GC: we handle them
83  *    with mark/sweep during major collections
84  * *) some objects need to not move even if they are small (interned strings, Type handles):
85  *    we use mark/sweep for them, too: they are not allocated in the nursery, but inside
86  *    PinnedChunks regions
87  */
88
89 /*
90  * TODO:
91
92  *) we could have a function pointer in MonoClass to implement
93   customized write barriers for value types
94
95  *) investigate the stuff needed to advance a thread to a GC-safe
96   point (single-stepping, read from unmapped memory etc) and implement it.
97   This would enable us to inline allocations and write barriers, for example,
98   or at least parts of them, like the write barrier checks.
99   We may need this also for handling precise info on stacks, even simple things
100   as having uninitialized data on the stack and having to wait for the prolog
101   to zero it. Not an issue for the last frame that we scan conservatively.
102   We could always not trust the value in the slots anyway.
103
104  *) modify the jit to save info about references in stack locations:
105   this can be done just for locals as a start, so that at least
106   part of the stack is handled precisely.
107
108  *) test/fix endianess issues
109
110  *) Implement a card table as the write barrier instead of remembered
111     sets?  Card tables are not easy to implement with our current
112     memory layout.  We have several different kinds of major heap
113     objects: Small objects in regular blocks, small objects in pinned
114     chunks and LOS objects.  If we just have a pointer we have no way
115     to tell which kind of object it points into, therefore we cannot
116     know where its card table is.  The least we have to do to make
117     this happen is to get rid of write barriers for indirect stores.
118     (See next item)
119
120  *) Get rid of write barriers for indirect stores.  We can do this by
121     telling the GC to wbarrier-register an object once we do an ldloca
122     or ldelema on it, and to unregister it once it's not used anymore
123     (it can only travel downwards on the stack).  The problem with
124     unregistering is that it needs to happen eventually no matter
125     what, even if exceptions are thrown, the thread aborts, etc.
126     Rodrigo suggested that we could do only the registering part and
127     let the collector find out (pessimistically) when it's safe to
128     unregister, namely when the stack pointer of the thread that
129     registered the object is higher than it was when the registering
130     happened.  This might make for a good first implementation to get
131     some data on performance.
132
133  *) Some sort of blacklist support?  Blacklists is a concept from the
134     Boehm GC: if during a conservative scan we find pointers to an
135     area which we might use as heap, we mark that area as unusable, so
136     pointer retention by random pinning pointers is reduced.
137
138  *) experiment with max small object size (very small right now - 2kb,
139     because it's tied to the max freelist size)
140
141   *) add an option to mmap the whole heap in one chunk: it makes for many
142      simplifications in the checks (put the nursery at the top and just use a single
143      check for inclusion/exclusion): the issue this has is that on 32 bit systems it's
144      not flexible (too much of the address space may be used by default or we can't
145      increase the heap as needed) and we'd need a race-free mechanism to return memory
146      back to the system (mprotect(PROT_NONE) will still keep the memory allocated if it
147      was written to, munmap is needed, but the following mmap may not find the same segment
148      free...)
149
150  *) memzero the major fragments after restarting the world and optionally a smaller
151     chunk at a time
152
153  *) investigate having fragment zeroing threads
154
155  *) separate locks for finalization and other minor stuff to reduce
156     lock contention
157
158  *) try a different copying order to improve memory locality
159
160  *) a thread abort after a store but before the write barrier will
161     prevent the write barrier from executing
162
163  *) specialized dynamically generated markers/copiers
164
165  *) Dynamically adjust TLAB size to the number of threads.  If we have
166     too many threads that do allocation, we might need smaller TLABs,
167     and we might get better performance with larger TLABs if we only
168     have a handful of threads.  We could sum up the space left in all
169     assigned TLABs and if that's more than some percentage of the
170     nursery size, reduce the TLAB size.
171
172  *) Explore placing unreachable objects on unused nursery memory.
173         Instead of memset'ng a region to zero, place an int[] covering it.
174         A good place to start is add_nursery_frag. The tricky thing here is
175         placing those objects atomically outside of a collection.
176
177
178  */
179 #include "config.h"
180 #ifdef HAVE_SGEN_GC
181
182 #include <unistd.h>
183 #include <stdio.h>
184 #include <string.h>
185 #include <semaphore.h>
186 #include <signal.h>
187 #include <errno.h>
188 #include <assert.h>
189 #ifdef __MACH__
190 #undef _XOPEN_SOURCE
191 #endif
192 #include <pthread.h>
193 #ifdef __MACH__
194 #define _XOPEN_SOURCE
195 #endif
196 #include "metadata/metadata-internals.h"
197 #include "metadata/class-internals.h"
198 #include "metadata/gc-internal.h"
199 #include "metadata/object-internals.h"
200 #include "metadata/threads.h"
201 #include "metadata/sgen-gc.h"
202 #include "metadata/sgen-archdep.h"
203 #include "metadata/mono-gc.h"
204 #include "metadata/method-builder.h"
205 #include "metadata/profiler-private.h"
206 #include "metadata/monitor.h"
207 #include "metadata/threadpool-internals.h"
208 #include "metadata/mempool-internals.h"
209 #include "metadata/marshal.h"
210 #include "utils/mono-mmap.h"
211 #include "utils/mono-time.h"
212 #include "utils/mono-semaphore.h"
213 #include "utils/mono-counters.h"
214
215 #include <mono/utils/memcheck.h>
216
217 #if defined(__MACH__)
218 #include "utils/mach-support.h"
219 #endif
220
221 #define OPDEF(a,b,c,d,e,f,g,h,i,j) \
222         a = i,
223
224 enum {
225 #include "mono/cil/opcode.def"
226         CEE_LAST
227 };
228
229 #undef OPDEF
230
231 #undef pthread_create
232 #undef pthread_join
233 #undef pthread_detach
234
235 /*
236  * ######################################################################
237  * ########  Types and constants used by the GC.
238  * ######################################################################
239  */
240
241 static int gc_initialized = 0;
242 /* If set, do a minor collection before every allocation */
243 static gboolean collect_before_allocs = FALSE;
244 /* If set, do a heap consistency check before each minor collection */
245 static gboolean consistency_check_at_minor_collection = FALSE;
246 /* If set, check that there are no references to the domain left at domain unload */
247 static gboolean xdomain_checks = FALSE;
248 /* If not null, dump the heap after each collection into this file */
249 static FILE *heap_dump_file = NULL;
250 /* If set, mark stacks conservatively, even if precise marking is possible */
251 static gboolean conservative_stack_mark = TRUE;
252 /* If set, do a plausibility check on the scan_starts before and after
253    each collection */
254 static gboolean do_scan_starts_check = FALSE;
255
256 #ifdef HEAVY_STATISTICS
257 static long long stat_objects_alloced = 0;
258 static long long stat_bytes_alloced = 0;
259 long long stat_objects_alloced_degraded = 0;
260 long long stat_bytes_alloced_degraded = 0;
261 static long long stat_bytes_alloced_los = 0;
262
263 long long stat_copy_object_called_nursery = 0;
264 long long stat_objects_copied_nursery = 0;
265 long long stat_copy_object_called_major = 0;
266 long long stat_objects_copied_major = 0;
267
268 long long stat_scan_object_called_nursery = 0;
269 long long stat_scan_object_called_major = 0;
270
271 long long stat_nursery_copy_object_failed_from_space = 0;
272 long long stat_nursery_copy_object_failed_forwarded = 0;
273 long long stat_nursery_copy_object_failed_pinned = 0;
274
275 static long long stat_store_remsets = 0;
276 static long long stat_store_remsets_unique = 0;
277 static long long stat_saved_remsets_1 = 0;
278 static long long stat_saved_remsets_2 = 0;
279 static long long stat_global_remsets_added = 0;
280 static long long stat_global_remsets_readded = 0;
281 static long long stat_global_remsets_processed = 0;
282 static long long stat_global_remsets_discarded = 0;
283
284 static long long stat_wasted_fragments_used = 0;
285 static long long stat_wasted_fragments_bytes = 0;
286
287 static int stat_wbarrier_set_field = 0;
288 static int stat_wbarrier_set_arrayref = 0;
289 static int stat_wbarrier_arrayref_copy = 0;
290 static int stat_wbarrier_generic_store = 0;
291 static int stat_wbarrier_generic_store_remset = 0;
292 static int stat_wbarrier_set_root = 0;
293 static int stat_wbarrier_value_copy = 0;
294 static int stat_wbarrier_object_copy = 0;
295 #endif
296
297 static long long time_minor_pre_collection_fragment_clear = 0;
298 static long long time_minor_pinning = 0;
299 static long long time_minor_scan_remsets = 0;
300 static long long time_minor_scan_pinned = 0;
301 static long long time_minor_scan_registered_roots = 0;
302 static long long time_minor_scan_thread_data = 0;
303 static long long time_minor_finish_gray_stack = 0;
304 static long long time_minor_fragment_creation = 0;
305
306 static long long time_major_pre_collection_fragment_clear = 0;
307 static long long time_major_pinning = 0;
308 static long long time_major_scan_pinned = 0;
309 static long long time_major_scan_registered_roots = 0;
310 static long long time_major_scan_thread_data = 0;
311 static long long time_major_scan_alloc_pinned = 0;
312 static long long time_major_scan_finalized = 0;
313 static long long time_major_scan_big_objects = 0;
314 static long long time_major_finish_gray_stack = 0;
315 static long long time_major_free_bigobjs = 0;
316 static long long time_major_los_sweep = 0;
317 static long long time_major_sweep = 0;
318 static long long time_major_fragment_creation = 0;
319
320 #define DEBUG(level,a) do {if (G_UNLIKELY ((level) <= SGEN_MAX_DEBUG_LEVEL && (level) <= gc_debug_level)) a;} while (0)
321
322 static int gc_debug_level = 0;
323 static FILE* gc_debug_file;
324
325 /*
326 void
327 mono_gc_flush_info (void)
328 {
329         fflush (gc_debug_file);
330 }
331 */
332
333 /*
334  * Define this to allow the user to change the nursery size by
335  * specifying its value in the MONO_GC_PARAMS environmental
336  * variable. See mono_gc_base_init for details.
337  */
338 #define USER_CONFIG 1
339
340 #define TV_DECLARE(name) gint64 name
341 #define TV_GETTIME(tv) tv = mono_100ns_ticks ()
342 #define TV_ELAPSED(start,end) (int)((end-start) / 10)
343 #define TV_ELAPSED_MS(start,end) ((TV_ELAPSED((start),(end)) + 500) / 1000)
344
345 #define ALIGN_TO(val,align) ((((guint64)val) + ((align) - 1)) & ~((align) - 1))
346
347 /* The method used to clear the nursery */
348 /* Clearing at nursery collections is the safest, but has bad interactions with caches.
349  * Clearing at TLAB creation is much faster, but more complex and it might expose hard
350  * to find bugs.
351  */
352 typedef enum {
353         CLEAR_AT_GC,
354         CLEAR_AT_TLAB_CREATION
355 } NurseryClearPolicy;
356
357 static NurseryClearPolicy nursery_clear_policy = CLEAR_AT_TLAB_CREATION;
358
359 /*
360  * The young generation is divided into fragments. This is because
361  * we can hand one fragments to a thread for lock-less fast alloc and
362  * because the young generation ends up fragmented anyway by pinned objects.
363  * Once a collection is done, a list of fragments is created. When doing
364  * thread local alloc we use smallish nurseries so we allow new threads to
365  * allocate memory from gen0 without triggering a collection. Threads that
366  * are found to allocate lots of memory are given bigger fragments. This
367  * should make the finalizer thread use little nursery memory after a while.
368  * We should start assigning threads very small fragments: if there are many
369  * threads the nursery will be full of reserved space that the threads may not
370  * use at all, slowing down allocation speed.
371  * Thread local allocation is done from areas of memory Hotspot calls Thread Local 
372  * Allocation Buffers (TLABs).
373  */
374 typedef struct _Fragment Fragment;
375
376 struct _Fragment {
377         Fragment *next;
378         char *fragment_start;
379         char *fragment_limit; /* the current soft limit for allocation */
380         char *fragment_end;
381 };
382
383 /* the runtime can register areas of memory as roots: we keep two lists of roots,
384  * a pinned root set for conservatively scanned roots and a normal one for
385  * precisely scanned roots (currently implemented as a single list).
386  */
387 typedef struct _RootRecord RootRecord;
388 struct _RootRecord {
389         RootRecord *next;
390         char *start_root;
391         char *end_root;
392         mword root_desc;
393 };
394
395 /*
396  * We're never actually using the first element.  It's always set to
397  * NULL to simplify the elimination of consecutive duplicate
398  * entries.
399  */
400 #define STORE_REMSET_BUFFER_SIZE        1024
401
402 typedef struct _GenericStoreRememberedSet GenericStoreRememberedSet;
403 struct _GenericStoreRememberedSet {
404         GenericStoreRememberedSet *next;
405         /* We need one entry less because the first entry of store
406            remset buffers is always a dummy and we don't copy it. */
407         gpointer data [STORE_REMSET_BUFFER_SIZE - 1];
408 };
409
410 /* we have 4 possible values in the low 2 bits */
411 enum {
412         REMSET_LOCATION, /* just a pointer to the exact location */
413         REMSET_RANGE,    /* range of pointer fields */
414         REMSET_OBJECT,   /* mark all the object for scanning */
415         REMSET_VTYPE,    /* a valuetype array described by a gc descriptor and a count */
416         REMSET_TYPE_MASK = 0x3
417 };
418
419 #ifdef HAVE_KW_THREAD
420 static __thread RememberedSet *remembered_set MONO_TLS_FAST;
421 #endif
422 static pthread_key_t remembered_set_key;
423 static RememberedSet *global_remset;
424 static RememberedSet *freed_thread_remsets;
425 static GenericStoreRememberedSet *generic_store_remsets = NULL;
426
427 /*A two slots cache for recently inserted remsets */
428 static gpointer global_remset_cache [2];
429
430 /* FIXME: later choose a size that takes into account the RememberedSet struct
431  * and doesn't waste any alloc paddin space.
432  */
433 #define DEFAULT_REMSET_SIZE 1024
434 static RememberedSet* alloc_remset (int size, gpointer id);
435
436 #define object_is_forwarded     SGEN_OBJECT_IS_FORWARDED
437 #define object_is_pinned        SGEN_OBJECT_IS_PINNED
438 #define pin_object              SGEN_PIN_OBJECT
439 #define unpin_object            SGEN_UNPIN_OBJECT
440
441 #define ptr_in_nursery(p)       (SGEN_PTR_IN_NURSERY ((p), DEFAULT_NURSERY_BITS, nursery_start, nursery_real_end))
442
443 #define LOAD_VTABLE     SGEN_LOAD_VTABLE
444
445 static const char*
446 safe_name (void* obj)
447 {
448         MonoVTable *vt = (MonoVTable*)LOAD_VTABLE (obj);
449         return vt->klass->name;
450 }
451
452 #define safe_object_get_size    mono_sgen_safe_object_get_size
453
454 /*
455  * ######################################################################
456  * ########  Global data.
457  * ######################################################################
458  */
459 static LOCK_DECLARE (gc_mutex);
460 static int gc_disabled = 0;
461 static int num_minor_gcs = 0;
462 static int num_major_gcs = 0;
463
464 #ifdef USER_CONFIG
465
466 /* good sizes are 512KB-1MB: larger ones increase a lot memzeroing time */
467 #define DEFAULT_NURSERY_SIZE (default_nursery_size)
468 static int default_nursery_size = (1 << 22);
469 #ifdef SGEN_ALIGN_NURSERY
470 /* The number of trailing 0 bits in DEFAULT_NURSERY_SIZE */
471 #define DEFAULT_NURSERY_BITS (default_nursery_bits)
472 static int default_nursery_bits = 22;
473 #endif
474
475 #else
476
477 #define DEFAULT_NURSERY_SIZE (4*1024*1024)
478 #ifdef SGEN_ALIGN_NURSERY
479 #define DEFAULT_NURSERY_BITS 22
480 #endif
481
482 #endif
483
484 #ifndef SGEN_ALIGN_NURSERY
485 #define DEFAULT_NURSERY_BITS -1
486 #endif
487
488 #define MIN_MINOR_COLLECTION_ALLOWANCE  (DEFAULT_NURSERY_SIZE * 4)
489
490 #define SCAN_START_SIZE SGEN_SCAN_START_SIZE
491
492 /* the minimum size of a fragment that we consider useful for allocation */
493 #define FRAGMENT_MIN_SIZE (512)
494
495 static mword pagesize = 4096;
496 static mword nursery_size;
497 static int degraded_mode = 0;
498
499 static mword total_alloc = 0;
500 /* use this to tune when to do a major/minor collection */
501 static mword memory_pressure = 0;
502 static mword minor_collection_allowance;
503 static int minor_collection_sections_alloced = 0;
504
505 static GCMemSection *nursery_section = NULL;
506 static mword lowest_heap_address = ~(mword)0;
507 static mword highest_heap_address = 0;
508
509 static LOCK_DECLARE (interruption_mutex);
510
511 typedef struct _FinalizeEntry FinalizeEntry;
512 struct _FinalizeEntry {
513         FinalizeEntry *next;
514         void *object;
515 };
516
517 typedef struct _FinalizeEntryHashTable FinalizeEntryHashTable;
518 struct _FinalizeEntryHashTable {
519         FinalizeEntry **table;
520         mword size;
521         int num_registered;
522 };
523
524 typedef struct _DisappearingLink DisappearingLink;
525 struct _DisappearingLink {
526         DisappearingLink *next;
527         void **link;
528 };
529
530 typedef struct _DisappearingLinkHashTable DisappearingLinkHashTable;
531 struct _DisappearingLinkHashTable {
532         DisappearingLink **table;
533         mword size;
534         int num_links;
535 };
536
537 typedef struct _EphemeronLinkNode EphemeronLinkNode;
538
539 struct _EphemeronLinkNode {
540         EphemeronLinkNode *next;
541         char *array;
542 };
543
544 typedef struct {
545        void *key;
546        void *value;
547 } Ephemeron;
548
549 enum {
550         GENERATION_NURSERY,
551         GENERATION_OLD,
552         GENERATION_MAX
553 };
554
555 int current_collection_generation = -1;
556
557 /*
558  * The link pointer is hidden by negating each bit.  We use the lowest
559  * bit of the link (before negation) to store whether it needs
560  * resurrection tracking.
561  */
562 #define HIDE_POINTER(p,t)       ((gpointer)(~((gulong)(p)|((t)?1:0))))
563 #define REVEAL_POINTER(p)       ((gpointer)((~(gulong)(p))&~3L))
564
565 #define DISLINK_OBJECT(d)       (REVEAL_POINTER (*(d)->link))
566 #define DISLINK_TRACK(d)        ((~(gulong)(*(d)->link)) & 1)
567
568 /*
569  * The finalizable hash has the object as the key, the 
570  * disappearing_link hash, has the link address as key.
571  */
572 static FinalizeEntryHashTable minor_finalizable_hash;
573 static FinalizeEntryHashTable major_finalizable_hash;
574 /* objects that are ready to be finalized */
575 static FinalizeEntry *fin_ready_list = NULL;
576 static FinalizeEntry *critical_fin_list = NULL;
577
578 static DisappearingLinkHashTable minor_disappearing_link_hash;
579 static DisappearingLinkHashTable major_disappearing_link_hash;
580
581 static EphemeronLinkNode *ephemeron_list;
582
583 static int num_ready_finalizers = 0;
584 static int no_finalize = 0;
585
586 enum {
587         ROOT_TYPE_NORMAL = 0, /* "normal" roots */
588         ROOT_TYPE_PINNED = 1, /* roots without a GC descriptor */
589         ROOT_TYPE_WBARRIER = 2, /* roots with a write barrier */
590         ROOT_TYPE_NUM
591 };
592
593 /* registered roots: the key to the hash is the root start address */
594 /* 
595  * Different kinds of roots are kept separate to speed up pin_from_roots () for example.
596  */
597 static RootRecord **roots_hash [ROOT_TYPE_NUM] = { NULL, NULL };
598 static int roots_hash_size [ROOT_TYPE_NUM] = { 0, 0, 0 };
599 static mword roots_size = 0; /* amount of memory in the root set */
600 static int num_roots_entries [ROOT_TYPE_NUM] = { 0, 0, 0 };
601
602 /* 
603  * The current allocation cursors
604  * We allocate objects in the nursery.
605  * The nursery is the area between nursery_start and nursery_real_end.
606  * Allocation is done from a Thread Local Allocation Buffer (TLAB). TLABs are allocated
607  * from nursery fragments.
608  * tlab_next is the pointer to the space inside the TLAB where the next object will 
609  * be allocated.
610  * tlab_temp_end is the pointer to the end of the temporary space reserved for
611  * the allocation: it allows us to set the scan starts at reasonable intervals.
612  * tlab_real_end points to the end of the TLAB.
613  * nursery_frag_real_end points to the end of the currently used nursery fragment.
614  * nursery_first_pinned_start points to the start of the first pinned object in the nursery
615  * nursery_last_pinned_end points to the end of the last pinned object in the nursery
616  * At the next allocation, the area of the nursery where objects can be present is
617  * between MIN(nursery_first_pinned_start, first_fragment_start) and
618  * MAX(nursery_last_pinned_end, nursery_frag_real_end)
619  */
620 static char *nursery_start = NULL;
621
622 #ifdef HAVE_KW_THREAD
623 #define TLAB_ACCESS_INIT
624 #define TLAB_START      tlab_start
625 #define TLAB_NEXT       tlab_next
626 #define TLAB_TEMP_END   tlab_temp_end
627 #define TLAB_REAL_END   tlab_real_end
628 #define REMEMBERED_SET  remembered_set
629 #define STORE_REMSET_BUFFER     store_remset_buffer
630 #define STORE_REMSET_BUFFER_INDEX       store_remset_buffer_index
631 #define IN_CRITICAL_REGION thread_info->in_critical_region
632 #else
633 static pthread_key_t thread_info_key;
634 #define TLAB_ACCESS_INIT        SgenThreadInfo *__thread_info__ = pthread_getspecific (thread_info_key)
635 #define TLAB_START      (__thread_info__->tlab_start)
636 #define TLAB_NEXT       (__thread_info__->tlab_next)
637 #define TLAB_TEMP_END   (__thread_info__->tlab_temp_end)
638 #define TLAB_REAL_END   (__thread_info__->tlab_real_end)
639 #define REMEMBERED_SET  (__thread_info__->remset)
640 #define STORE_REMSET_BUFFER     (__thread_info__->store_remset_buffer)
641 #define STORE_REMSET_BUFFER_INDEX       (__thread_info__->store_remset_buffer_index)
642 #define IN_CRITICAL_REGION (__thread_info__->in_critical_region)
643 #endif
644
645 /* we use the memory barrier only to prevent compiler reordering (a memory constraint may be enough) */
646 #define ENTER_CRITICAL_REGION do {IN_CRITICAL_REGION = 1;mono_memory_barrier ();} while (0)
647 #define EXIT_CRITICAL_REGION  do {IN_CRITICAL_REGION = 0;mono_memory_barrier ();} while (0)
648
649 /*
650  * FIXME: What is faster, a TLS variable pointing to a structure, or separate TLS 
651  * variables for next+temp_end ?
652  */
653 #ifdef HAVE_KW_THREAD
654 static __thread SgenThreadInfo *thread_info;
655 static __thread char *tlab_start;
656 static __thread char *tlab_next;
657 static __thread char *tlab_temp_end;
658 static __thread char *tlab_real_end;
659 static __thread gpointer *store_remset_buffer;
660 static __thread long store_remset_buffer_index;
661 /* Used by the managed allocator/wbarrier */
662 static __thread char **tlab_next_addr;
663 static __thread char *stack_end;
664 static __thread long *store_remset_buffer_index_addr;
665 #endif
666 static char *nursery_next = NULL;
667 static char *nursery_frag_real_end = NULL;
668 static char *nursery_real_end = NULL;
669 static char *nursery_last_pinned_end = NULL;
670
671 /* The size of a TLAB */
672 /* The bigger the value, the less often we have to go to the slow path to allocate a new 
673  * one, but the more space is wasted by threads not allocating much memory.
674  * FIXME: Tune this.
675  * FIXME: Make this self-tuning for each thread.
676  */
677 static guint32 tlab_size = (1024 * 4);
678
679 /*How much space is tolerable to be wasted from the current fragment when allocating a new TLAB*/
680 #define MAX_NURSERY_TLAB_WASTE 512
681
682 /* fragments that are free and ready to be used for allocation */
683 static Fragment *nursery_fragments = NULL;
684 /* freeelist of fragment structures */
685 static Fragment *fragment_freelist = NULL;
686
687 #define MAX_SMALL_OBJ_SIZE      SGEN_MAX_SMALL_OBJ_SIZE
688
689 /* Functions supplied by the runtime to be called by the GC */
690 static MonoGCCallbacks gc_callbacks;
691
692 #define ALLOC_ALIGN             SGEN_ALLOC_ALIGN
693 #define ALLOC_ALIGN_BITS        SGEN_ALLOC_ALIGN_BITS
694
695 #define ALIGN_UP                SGEN_ALIGN_UP
696
697 #define MOVED_OBJECTS_NUM 64
698 static void *moved_objects [MOVED_OBJECTS_NUM];
699 static int moved_objects_idx = 0;
700
701 /*
702  * ######################################################################
703  * ########  Macros and function declarations.
704  * ######################################################################
705  */
706
707 #define ADDR_IN_HEAP_BOUNDARIES(addr) ((p) >= lowest_heap_address && (p) < highest_heap_address)
708
709 inline static void*
710 align_pointer (void *ptr)
711 {
712         mword p = (mword)ptr;
713         p += sizeof (gpointer) - 1;
714         p &= ~ (sizeof (gpointer) - 1);
715         return (void*)p;
716 }
717
718 typedef SgenGrayQueue GrayQueue;
719
720 typedef void (*CopyOrMarkObjectFunc) (void**, GrayQueue*);
721 typedef char* (*ScanObjectFunc) (char*, GrayQueue*);
722
723 /* forward declarations */
724 static int stop_world (void);
725 static int restart_world (void);
726 static void scan_thread_data (void *start_nursery, void *end_nursery, gboolean precise);
727 static void scan_from_remsets (void *start_nursery, void *end_nursery, GrayQueue *queue);
728 static void scan_from_registered_roots (CopyOrMarkObjectFunc copy_func, char *addr_start, char *addr_end, int root_type, GrayQueue *queue);
729 static void scan_finalizer_entries (CopyOrMarkObjectFunc copy_func, FinalizeEntry *list, GrayQueue *queue);
730 static void find_pinning_ref_from_thread (char *obj, size_t size);
731 static void update_current_thread_stack (void *start);
732 static void finalize_in_range (CopyOrMarkObjectFunc copy_func, char *start, char *end, int generation, GrayQueue *queue);
733 static void add_or_remove_disappearing_link (MonoObject *obj, void **link, gboolean track, int generation);
734 static void null_link_in_range (CopyOrMarkObjectFunc copy_func, char *start, char *end, int generation, GrayQueue *queue);
735 static void null_links_for_domain (MonoDomain *domain, int generation);
736 static gboolean search_fragment_for_size (size_t size);
737 static int search_fragment_for_size_range (size_t desired_size, size_t minimum_size);
738 static void clear_nursery_fragments (char *next);
739 static void pin_from_roots (void *start_nursery, void *end_nursery);
740 static int pin_objects_from_addresses (GCMemSection *section, void **start, void **end, void *start_nursery, void *end_nursery, GrayQueue *queue);
741 static void optimize_pin_queue (int start_slot);
742 static void clear_remsets (void);
743 static void clear_tlabs (void);
744 static void sort_addresses (void **array, int size);
745 static void drain_gray_stack (GrayQueue *queue);
746 static void finish_gray_stack (char *start_addr, char *end_addr, int generation, GrayQueue *queue);
747 static gboolean need_major_collection (void);
748 static void major_collection (const char *reason);
749
750 static void mono_gc_register_disappearing_link (MonoObject *obj, void **link, gboolean track);
751
752 void describe_ptr (char *ptr);
753 void check_object (char *start);
754
755 static void check_consistency (void);
756 static void check_major_refs (void);
757 static void check_scan_starts (void);
758 static void check_for_xdomain_refs (void);
759 static void dump_heap (const char *type, int num, const char *reason);
760
761 void mono_gc_scan_for_specific_ref (MonoObject *key);
762
763 static void init_stats (void);
764
765 static int mark_ephemerons_in_range (CopyOrMarkObjectFunc copy_func, char *start, char *end, GrayQueue *queue);
766 static void clear_unreachable_ephemerons (CopyOrMarkObjectFunc copy_func, char *start, char *end, GrayQueue *queue);
767 static void null_ephemerons_for_domain (MonoDomain *domain);
768
769 SgenMajorCollector major;
770
771 #include "sgen-protocol.c"
772 #include "sgen-pinning.c"
773 #include "sgen-pinning-stats.c"
774 #include "sgen-gray.c"
775 #include "sgen-los.c"
776
777 /* Root bitmap descriptors are simpler: the lower three bits describe the type
778  * and we either have 30/62 bitmap bits or nibble-based run-length,
779  * or a complex descriptor, or a user defined marker function.
780  */
781 enum {
782         ROOT_DESC_CONSERVATIVE, /* 0, so matches NULL value */
783         ROOT_DESC_BITMAP,
784         ROOT_DESC_RUN_LEN, 
785         ROOT_DESC_COMPLEX,
786         ROOT_DESC_USER,
787         ROOT_DESC_TYPE_MASK = 0x7,
788         ROOT_DESC_TYPE_SHIFT = 3,
789 };
790
791 #define MAKE_ROOT_DESC(type,val) ((type) | ((val) << ROOT_DESC_TYPE_SHIFT))
792
793 #define MAX_USER_DESCRIPTORS 16
794
795 static gsize* complex_descriptors = NULL;
796 static int complex_descriptors_size = 0;
797 static int complex_descriptors_next = 0;
798 static MonoGCRootMarkFunc user_descriptors [MAX_USER_DESCRIPTORS];
799 static int user_descriptors_next = 0;
800
801 static int
802 alloc_complex_descriptor (gsize *bitmap, int numbits)
803 {
804         int nwords, res, i;
805
806         numbits = ALIGN_TO (numbits, GC_BITS_PER_WORD);
807         nwords = numbits / GC_BITS_PER_WORD + 1;
808
809         LOCK_GC;
810         res = complex_descriptors_next;
811         /* linear search, so we don't have duplicates with domain load/unload
812          * this should not be performance critical or we'd have bigger issues
813          * (the number and size of complex descriptors should be small).
814          */
815         for (i = 0; i < complex_descriptors_next; ) {
816                 if (complex_descriptors [i] == nwords) {
817                         int j, found = TRUE;
818                         for (j = 0; j < nwords - 1; ++j) {
819                                 if (complex_descriptors [i + 1 + j] != bitmap [j]) {
820                                         found = FALSE;
821                                         break;
822                                 }
823                         }
824                         if (found) {
825                                 UNLOCK_GC;
826                                 return i;
827                         }
828                 }
829                 i += complex_descriptors [i];
830         }
831         if (complex_descriptors_next + nwords > complex_descriptors_size) {
832                 int new_size = complex_descriptors_size * 2 + nwords;
833                 complex_descriptors = g_realloc (complex_descriptors, new_size * sizeof (gsize));
834                 complex_descriptors_size = new_size;
835         }
836         DEBUG (6, fprintf (gc_debug_file, "Complex descriptor %d, size: %d (total desc memory: %d)\n", res, nwords, complex_descriptors_size));
837         complex_descriptors_next += nwords;
838         complex_descriptors [res] = nwords;
839         for (i = 0; i < nwords - 1; ++i) {
840                 complex_descriptors [res + 1 + i] = bitmap [i];
841                 DEBUG (6, fprintf (gc_debug_file, "\tvalue: %p\n", (void*)complex_descriptors [res + 1 + i]));
842         }
843         UNLOCK_GC;
844         return res;
845 }
846
847 gsize*
848 mono_sgen_get_complex_descriptor (GCVTable *vt)
849 {
850         return complex_descriptors + (vt->desc >> LOW_TYPE_BITS);
851 }
852
853 /*
854  * Descriptor builders.
855  */
856 void*
857 mono_gc_make_descr_for_string (gsize *bitmap, int numbits)
858 {
859         return (void*) DESC_TYPE_RUN_LENGTH;
860 }
861
862 void*
863 mono_gc_make_descr_for_object (gsize *bitmap, int numbits, size_t obj_size)
864 {
865         int first_set = -1, num_set = 0, last_set = -1, i;
866         mword desc = 0;
867         size_t stored_size = obj_size;
868         for (i = 0; i < numbits; ++i) {
869                 if (bitmap [i / GC_BITS_PER_WORD] & ((gsize)1 << (i % GC_BITS_PER_WORD))) {
870                         if (first_set < 0)
871                                 first_set = i;
872                         last_set = i;
873                         num_set++;
874                 }
875         }
876         /*
877          * We don't encode the size of types that don't contain
878          * references because they might not be aligned, i.e. the
879          * bottom two bits might be set, which would clash with the
880          * bits we need to encode the descriptor type.  Since we don't
881          * use the encoded size to skip objects, other than for
882          * processing remsets, in which case only the positions of
883          * references are relevant, this is not a problem.
884          */
885         if (first_set < 0)
886                 return (void*)DESC_TYPE_RUN_LENGTH;
887         g_assert (!(stored_size & 0x3));
888         if (stored_size <= MAX_SMALL_OBJ_SIZE) {
889                 /* check run-length encoding first: one byte offset, one byte number of pointers
890                  * on 64 bit archs, we can have 3 runs, just one on 32.
891                  * It may be better to use nibbles.
892                  */
893                 if (first_set < 0) {
894                         desc = DESC_TYPE_RUN_LENGTH | (stored_size << 1);
895                         DEBUG (6, fprintf (gc_debug_file, "Ptrfree descriptor %p, size: %zd\n", (void*)desc, stored_size));
896                         return (void*) desc;
897                 } else if (first_set < 256 && num_set < 256 && (first_set + num_set == last_set + 1)) {
898                         desc = DESC_TYPE_RUN_LENGTH | (stored_size << 1) | (first_set << 16) | (num_set << 24);
899                         DEBUG (6, fprintf (gc_debug_file, "Runlen descriptor %p, size: %zd, first set: %d, num set: %d\n", (void*)desc, stored_size, first_set, num_set));
900                         return (void*) desc;
901                 }
902                 /* we know the 2-word header is ptr-free */
903                 if (last_set < SMALL_BITMAP_SIZE + OBJECT_HEADER_WORDS) {
904                         desc = DESC_TYPE_SMALL_BITMAP | (stored_size << 1) | ((*bitmap >> OBJECT_HEADER_WORDS) << SMALL_BITMAP_SHIFT);
905                         DEBUG (6, fprintf (gc_debug_file, "Smallbitmap descriptor %p, size: %zd, last set: %d\n", (void*)desc, stored_size, last_set));
906                         return (void*) desc;
907                 }
908         }
909         /* we know the 2-word header is ptr-free */
910         if (last_set < LARGE_BITMAP_SIZE + OBJECT_HEADER_WORDS) {
911                 desc = DESC_TYPE_LARGE_BITMAP | ((*bitmap >> OBJECT_HEADER_WORDS) << LOW_TYPE_BITS);
912                 DEBUG (6, fprintf (gc_debug_file, "Largebitmap descriptor %p, size: %zd, last set: %d\n", (void*)desc, stored_size, last_set));
913                 return (void*) desc;
914         }
915         /* it's a complex object ... */
916         desc = DESC_TYPE_COMPLEX | (alloc_complex_descriptor (bitmap, last_set + 1) << LOW_TYPE_BITS);
917         return (void*) desc;
918 }
919
920 /* If the array holds references, numbits == 1 and the first bit is set in elem_bitmap */
921 void*
922 mono_gc_make_descr_for_array (int vector, gsize *elem_bitmap, int numbits, size_t elem_size)
923 {
924         int first_set = -1, num_set = 0, last_set = -1, i;
925         mword desc = vector? DESC_TYPE_VECTOR: DESC_TYPE_ARRAY;
926         for (i = 0; i < numbits; ++i) {
927                 if (elem_bitmap [i / GC_BITS_PER_WORD] & ((gsize)1 << (i % GC_BITS_PER_WORD))) {
928                         if (first_set < 0)
929                                 first_set = i;
930                         last_set = i;
931                         num_set++;
932                 }
933         }
934         /* See comment at the definition of DESC_TYPE_RUN_LENGTH. */
935         if (first_set < 0)
936                 return (void*)DESC_TYPE_RUN_LENGTH;
937         if (elem_size <= MAX_ELEMENT_SIZE) {
938                 desc |= elem_size << VECTOR_ELSIZE_SHIFT;
939                 if (!num_set) {
940                         return (void*)(desc | VECTOR_SUBTYPE_PTRFREE);
941                 }
942                 /* Note: we also handle structs with just ref fields */
943                 if (num_set * sizeof (gpointer) == elem_size) {
944                         return (void*)(desc | VECTOR_SUBTYPE_REFS | ((gssize)(-1) << 16));
945                 }
946                 /* FIXME: try run-len first */
947                 /* Note: we can't skip the object header here, because it's not present */
948                 if (last_set <= SMALL_BITMAP_SIZE) {
949                         return (void*)(desc | VECTOR_SUBTYPE_BITMAP | (*elem_bitmap << 16));
950                 }
951         }
952         /* it's am array of complex structs ... */
953         desc = DESC_TYPE_COMPLEX_ARR;
954         desc |= alloc_complex_descriptor (elem_bitmap, last_set + 1) << LOW_TYPE_BITS;
955         return (void*) desc;
956 }
957
958 /* Return the bitmap encoded by a descriptor */
959 gsize*
960 mono_gc_get_bitmap_for_descr (void *descr, int *numbits)
961 {
962         mword d = (mword)descr;
963         gsize *bitmap;
964
965         switch (d & 0x7) {
966         case DESC_TYPE_RUN_LENGTH: {            
967                 int first_set = (d >> 16) & 0xff;
968                 int num_set = (d >> 24) & 0xff;
969                 int i;
970
971                 bitmap = g_new0 (gsize, (first_set + num_set + 7) / 8);
972
973                 for (i = first_set; i < first_set + num_set; ++i)
974                         bitmap [i / GC_BITS_PER_WORD] |= ((gsize)1 << (i % GC_BITS_PER_WORD));
975
976                 *numbits = first_set + num_set;
977
978                 return bitmap;
979         }
980         case DESC_TYPE_SMALL_BITMAP:
981                 bitmap = g_new0 (gsize, 1);
982
983                 bitmap [0] = (d >> SMALL_BITMAP_SHIFT) << OBJECT_HEADER_WORDS;
984
985             *numbits = GC_BITS_PER_WORD;
986                 
987                 return bitmap;
988         default:
989                 g_assert_not_reached ();
990         }
991 }
992
993 static gboolean
994 is_xdomain_ref_allowed (gpointer *ptr, char *obj, MonoDomain *domain)
995 {
996         MonoObject *o = (MonoObject*)(obj);
997         MonoObject *ref = (MonoObject*)*(ptr);
998         int offset = (char*)(ptr) - (char*)o;
999
1000         if (o->vtable->klass == mono_defaults.thread_class && offset == G_STRUCT_OFFSET (MonoThread, internal_thread))
1001                 return TRUE;
1002         if (o->vtable->klass == mono_defaults.internal_thread_class && offset == G_STRUCT_OFFSET (MonoInternalThread, current_appcontext))
1003                 return TRUE;
1004         if (mono_class_has_parent (o->vtable->klass, mono_defaults.real_proxy_class) &&
1005                         offset == G_STRUCT_OFFSET (MonoRealProxy, unwrapped_server))
1006                 return TRUE;
1007         /* Thread.cached_culture_info */
1008         if (!strcmp (ref->vtable->klass->name_space, "System.Globalization") &&
1009                         !strcmp (ref->vtable->klass->name, "CultureInfo") &&
1010                         !strcmp(o->vtable->klass->name_space, "System") &&
1011                         !strcmp(o->vtable->klass->name, "Object[]"))
1012                 return TRUE;
1013         /*
1014          *  at System.IO.MemoryStream.InternalConstructor (byte[],int,int,bool,bool) [0x0004d] in /home/schani/Work/novell/trunk/mcs/class/corlib/System.IO/MemoryStream.cs:121
1015          * at System.IO.MemoryStream..ctor (byte[]) [0x00017] in /home/schani/Work/novell/trunk/mcs/class/corlib/System.IO/MemoryStream.cs:81
1016          * at (wrapper remoting-invoke-with-check) System.IO.MemoryStream..ctor (byte[]) <IL 0x00020, 0xffffffff>
1017          * at System.Runtime.Remoting.Messaging.CADMethodCallMessage.GetArguments () [0x0000d] in /home/schani/Work/novell/trunk/mcs/class/corlib/System.Runtime.Remoting.Messaging/CADMessages.cs:327
1018          * at System.Runtime.Remoting.Messaging.MethodCall..ctor (System.Runtime.Remoting.Messaging.CADMethodCallMessage) [0x00017] in /home/schani/Work/novell/trunk/mcs/class/corlib/System.Runtime.Remoting.Messaging/MethodCall.cs:87
1019          * at System.AppDomain.ProcessMessageInDomain (byte[],System.Runtime.Remoting.Messaging.CADMethodCallMessage,byte[]&,System.Runtime.Remoting.Messaging.CADMethodReturnMessage&) [0x00018] in /home/schani/Work/novell/trunk/mcs/class/corlib/System/AppDomain.cs:1213
1020          * at (wrapper remoting-invoke-with-check) System.AppDomain.ProcessMessageInDomain (byte[],System.Runtime.Remoting.Messaging.CADMethodCallMessage,byte[]&,System.Runtime.Remoting.Messaging.CADMethodReturnMessage&) <IL 0x0003d, 0xffffffff>
1021          * at System.Runtime.Remoting.Channels.CrossAppDomainSink.ProcessMessageInDomain (byte[],System.Runtime.Remoting.Messaging.CADMethodCallMessage) [0x00008] in /home/schani/Work/novell/trunk/mcs/class/corlib/System.Runtime.Remoting.Channels/CrossAppDomainChannel.cs:198
1022          * at (wrapper runtime-invoke) object.runtime_invoke_CrossAppDomainSink/ProcessMessageRes_object_object (object,intptr,intptr,intptr) <IL 0x0004c, 0xffffffff>
1023          */
1024         if (!strcmp (ref->vtable->klass->name_space, "System") &&
1025                         !strcmp (ref->vtable->klass->name, "Byte[]") &&
1026                         !strcmp (o->vtable->klass->name_space, "System.IO") &&
1027                         !strcmp (o->vtable->klass->name, "MemoryStream"))
1028                 return TRUE;
1029         /* append_job() in threadpool.c */
1030         if (!strcmp (ref->vtable->klass->name_space, "System.Runtime.Remoting.Messaging") &&
1031                         !strcmp (ref->vtable->klass->name, "AsyncResult") &&
1032                         !strcmp (o->vtable->klass->name_space, "System") &&
1033                         !strcmp (o->vtable->klass->name, "Object[]") &&
1034                         mono_thread_pool_is_queue_array ((MonoArray*) o))
1035                 return TRUE;
1036         return FALSE;
1037 }
1038
1039 static void
1040 check_reference_for_xdomain (gpointer *ptr, char *obj, MonoDomain *domain)
1041 {
1042         MonoObject *o = (MonoObject*)(obj);
1043         MonoObject *ref = (MonoObject*)*(ptr);
1044         int offset = (char*)(ptr) - (char*)o;
1045         MonoClass *class;
1046         MonoClassField *field;
1047         char *str;
1048
1049         if (!ref || ref->vtable->domain == domain)
1050                 return;
1051         if (is_xdomain_ref_allowed (ptr, obj, domain))
1052                 return;
1053
1054         field = NULL;
1055         for (class = o->vtable->klass; class; class = class->parent) {
1056                 int i;
1057
1058                 for (i = 0; i < class->field.count; ++i) {
1059                         if (class->fields[i].offset == offset) {
1060                                 field = &class->fields[i];
1061                                 break;
1062                         }
1063                 }
1064                 if (field)
1065                         break;
1066         }
1067
1068         if (ref->vtable->klass == mono_defaults.string_class)
1069                 str = mono_string_to_utf8 ((MonoString*)ref);
1070         else
1071                 str = NULL;
1072         g_print ("xdomain reference in %p (%s.%s) at offset %d (%s) to %p (%s.%s) (%s)  -  pointed to by:\n",
1073                         o, o->vtable->klass->name_space, o->vtable->klass->name,
1074                         offset, field ? field->name : "",
1075                         ref, ref->vtable->klass->name_space, ref->vtable->klass->name, str ? str : "");
1076         mono_gc_scan_for_specific_ref (o);
1077         if (str)
1078                 g_free (str);
1079 }
1080
1081 #undef HANDLE_PTR
1082 #define HANDLE_PTR(ptr,obj)     check_reference_for_xdomain ((ptr), (obj), domain)
1083
1084 static void
1085 scan_object_for_xdomain_refs (char *start, mword size, void *data)
1086 {
1087         MonoDomain *domain = ((MonoObject*)start)->vtable->domain;
1088
1089         #include "sgen-scan-object.h"
1090 }
1091
1092 #undef HANDLE_PTR
1093 #define HANDLE_PTR(ptr,obj) do {                \
1094         if ((MonoObject*)*(ptr) == key) {       \
1095         g_print ("found ref to %p in object %p (%s) at offset %td\n",   \
1096                         key, (obj), safe_name ((obj)), ((char*)(ptr) - (char*)(obj))); \
1097         }                                                               \
1098         } while (0)
1099
1100 static void
1101 scan_object_for_specific_ref (char *start, MonoObject *key)
1102 {
1103         #include "sgen-scan-object.h"
1104 }
1105
1106 void
1107 mono_sgen_scan_area_with_callback (char *start, char *end, IterateObjectCallbackFunc callback, void *data)
1108 {
1109         while (start < end) {
1110                 size_t size;
1111                 if (!*(void**)start) {
1112                         start += sizeof (void*); /* should be ALLOC_ALIGN, really */
1113                         continue;
1114                 }
1115
1116                 size = ALIGN_UP (safe_object_get_size ((MonoObject*) start));
1117
1118                 callback (start, size, data);
1119
1120                 start += size;
1121         }
1122 }
1123
1124 static void
1125 scan_object_for_specific_ref_callback (char *obj, size_t size, MonoObject *key)
1126 {
1127         scan_object_for_specific_ref (obj, key);
1128 }
1129
1130 static void
1131 check_root_obj_specific_ref (RootRecord *root, MonoObject *key, MonoObject *obj)
1132 {
1133         if (key != obj)
1134                 return;
1135         g_print ("found ref to %p in root record %p\n", key, root);
1136 }
1137
1138 static MonoObject *check_key = NULL;
1139 static RootRecord *check_root = NULL;
1140
1141 static void
1142 check_root_obj_specific_ref_from_marker (void **obj)
1143 {
1144         check_root_obj_specific_ref (check_root, check_key, *obj);
1145 }
1146
1147 static void
1148 scan_roots_for_specific_ref (MonoObject *key, int root_type)
1149 {
1150         int i;
1151         RootRecord *root;
1152         check_key = key;
1153         for (i = 0; i < roots_hash_size [root_type]; ++i) {
1154                 for (root = roots_hash [root_type][i]; root; root = root->next) {
1155                         void **start_root = (void**)root->start_root;
1156                         mword desc = root->root_desc;
1157
1158                         check_root = root;
1159
1160                         switch (desc & ROOT_DESC_TYPE_MASK) {
1161                         case ROOT_DESC_BITMAP:
1162                                 desc >>= ROOT_DESC_TYPE_SHIFT;
1163                                 while (desc) {
1164                                         if (desc & 1)
1165                                                 check_root_obj_specific_ref (root, key, *start_root);
1166                                         desc >>= 1;
1167                                         start_root++;
1168                                 }
1169                                 return;
1170                         case ROOT_DESC_COMPLEX: {
1171                                 gsize *bitmap_data = complex_descriptors + (desc >> ROOT_DESC_TYPE_SHIFT);
1172                                 int bwords = (*bitmap_data) - 1;
1173                                 void **start_run = start_root;
1174                                 bitmap_data++;
1175                                 while (bwords-- > 0) {
1176                                         gsize bmap = *bitmap_data++;
1177                                         void **objptr = start_run;
1178                                         while (bmap) {
1179                                                 if (bmap & 1)
1180                                                         check_root_obj_specific_ref (root, key, *objptr);
1181                                                 bmap >>= 1;
1182                                                 ++objptr;
1183                                         }
1184                                         start_run += GC_BITS_PER_WORD;
1185                                 }
1186                                 break;
1187                         }
1188                         case ROOT_DESC_USER: {
1189                                 MonoGCRootMarkFunc marker = user_descriptors [desc >> ROOT_DESC_TYPE_SHIFT];
1190                                 marker (start_root, check_root_obj_specific_ref_from_marker);
1191                                 break;
1192                         }
1193                         case ROOT_DESC_RUN_LEN:
1194                                 g_assert_not_reached ();
1195                         default:
1196                                 g_assert_not_reached ();
1197                         }
1198                 }
1199         }
1200         check_key = NULL;
1201         check_root = NULL;
1202 }
1203
1204 void
1205 mono_gc_scan_for_specific_ref (MonoObject *key)
1206 {
1207         LOSObject *bigobj;
1208         RootRecord *root;
1209         int i;
1210
1211         mono_sgen_scan_area_with_callback (nursery_section->data, nursery_section->end_data,
1212                         (IterateObjectCallbackFunc)scan_object_for_specific_ref_callback, key);
1213
1214         major.iterate_objects (TRUE, TRUE, (IterateObjectCallbackFunc)scan_object_for_specific_ref_callback, key);
1215
1216         for (bigobj = los_object_list; bigobj; bigobj = bigobj->next)
1217                 scan_object_for_specific_ref (bigobj->data, key);
1218
1219         scan_roots_for_specific_ref (key, ROOT_TYPE_NORMAL);
1220         scan_roots_for_specific_ref (key, ROOT_TYPE_WBARRIER);
1221
1222         for (i = 0; i < roots_hash_size [ROOT_TYPE_PINNED]; ++i) {
1223                 for (root = roots_hash [ROOT_TYPE_PINNED][i]; root; root = root->next) {
1224                         void **ptr = (void**)root->start_root;
1225
1226                         while (ptr < (void**)root->end_root) {
1227                                 check_root_obj_specific_ref (root, *ptr, key);
1228                                 ++ptr;
1229                         }
1230                 }
1231         }
1232 }
1233
1234 /* Clear all remaining nursery fragments */
1235 static void
1236 clear_nursery_fragments (char *next)
1237 {
1238         Fragment *frag;
1239         if (nursery_clear_policy == CLEAR_AT_TLAB_CREATION) {
1240                 g_assert (next <= nursery_frag_real_end);
1241                 memset (next, 0, nursery_frag_real_end - next);
1242                 for (frag = nursery_fragments; frag; frag = frag->next) {
1243                         memset (frag->fragment_start, 0, frag->fragment_end - frag->fragment_start);
1244                 }
1245         }
1246 }
1247
1248 static gboolean
1249 need_remove_object_for_domain (char *start, MonoDomain *domain)
1250 {
1251         if (mono_object_domain (start) == domain) {
1252                 DEBUG (4, fprintf (gc_debug_file, "Need to cleanup object %p\n", start));
1253                 binary_protocol_cleanup (start, (gpointer)LOAD_VTABLE (start), safe_object_get_size ((MonoObject*)start));
1254                 return TRUE;
1255         }
1256         return FALSE;
1257 }
1258
1259 static void
1260 process_object_for_domain_clearing (char *start, MonoDomain *domain)
1261 {
1262         GCVTable *vt = (GCVTable*)LOAD_VTABLE (start);
1263         if (vt->klass == mono_defaults.internal_thread_class)
1264                 g_assert (mono_object_domain (start) == mono_get_root_domain ());
1265         /* The object could be a proxy for an object in the domain
1266            we're deleting. */
1267         if (mono_class_has_parent (vt->klass, mono_defaults.real_proxy_class)) {
1268                 MonoObject *server = ((MonoRealProxy*)start)->unwrapped_server;
1269
1270                 /* The server could already have been zeroed out, so
1271                    we need to check for that, too. */
1272                 if (server && (!LOAD_VTABLE (server) || mono_object_domain (server) == domain)) {
1273                         DEBUG (4, fprintf (gc_debug_file, "Cleaning up remote pointer in %p to object %p\n",
1274                                         start, server));
1275                         ((MonoRealProxy*)start)->unwrapped_server = NULL;
1276                 }
1277         }
1278 }
1279
1280 static MonoDomain *check_domain = NULL;
1281
1282 static void
1283 check_obj_not_in_domain (void **o)
1284 {
1285         g_assert (((MonoObject*)(*o))->vtable->domain != check_domain);
1286 }
1287
1288 static void
1289 scan_for_registered_roots_in_domain (MonoDomain *domain, int root_type)
1290 {
1291         int i;
1292         RootRecord *root;
1293         check_domain = domain;
1294         for (i = 0; i < roots_hash_size [root_type]; ++i) {
1295                 for (root = roots_hash [root_type][i]; root; root = root->next) {
1296                         void **start_root = (void**)root->start_root;
1297                         mword desc = root->root_desc;
1298
1299                         /* The MonoDomain struct is allowed to hold
1300                            references to objects in its own domain. */
1301                         if (start_root == (void**)domain)
1302                                 continue;
1303
1304                         switch (desc & ROOT_DESC_TYPE_MASK) {
1305                         case ROOT_DESC_BITMAP:
1306                                 desc >>= ROOT_DESC_TYPE_SHIFT;
1307                                 while (desc) {
1308                                         if ((desc & 1) && *start_root)
1309                                                 check_obj_not_in_domain (*start_root);
1310                                         desc >>= 1;
1311                                         start_root++;
1312                                 }
1313                                 break;
1314                         case ROOT_DESC_COMPLEX: {
1315                                 gsize *bitmap_data = complex_descriptors + (desc >> ROOT_DESC_TYPE_SHIFT);
1316                                 int bwords = (*bitmap_data) - 1;
1317                                 void **start_run = start_root;
1318                                 bitmap_data++;
1319                                 while (bwords-- > 0) {
1320                                         gsize bmap = *bitmap_data++;
1321                                         void **objptr = start_run;
1322                                         while (bmap) {
1323                                                 if ((bmap & 1) && *objptr)
1324                                                         check_obj_not_in_domain (*objptr);
1325                                                 bmap >>= 1;
1326                                                 ++objptr;
1327                                         }
1328                                         start_run += GC_BITS_PER_WORD;
1329                                 }
1330                                 break;
1331                         }
1332                         case ROOT_DESC_USER: {
1333                                 MonoGCRootMarkFunc marker = user_descriptors [desc >> ROOT_DESC_TYPE_SHIFT];
1334                                 marker (start_root, check_obj_not_in_domain);
1335                                 break;
1336                         }
1337                         case ROOT_DESC_RUN_LEN:
1338                                 g_assert_not_reached ();
1339                         default:
1340                                 g_assert_not_reached ();
1341                         }
1342                 }
1343         }
1344         check_domain = NULL;
1345 }
1346
1347 static void
1348 check_for_xdomain_refs (void)
1349 {
1350         LOSObject *bigobj;
1351
1352         mono_sgen_scan_area_with_callback (nursery_section->data, nursery_section->end_data,
1353                         (IterateObjectCallbackFunc)scan_object_for_xdomain_refs, NULL);
1354
1355         major.iterate_objects (TRUE, TRUE, (IterateObjectCallbackFunc)scan_object_for_xdomain_refs, NULL);
1356
1357         for (bigobj = los_object_list; bigobj; bigobj = bigobj->next)
1358                 scan_object_for_xdomain_refs (bigobj->data, bigobj->size, NULL);
1359 }
1360
1361 static gboolean
1362 clear_domain_process_object (char *obj, MonoDomain *domain)
1363 {
1364         gboolean remove;
1365
1366         process_object_for_domain_clearing (obj, domain);
1367         remove = need_remove_object_for_domain (obj, domain);
1368
1369         if (remove && ((MonoObject*)obj)->synchronisation) {
1370                 void **dislink = mono_monitor_get_object_monitor_weak_link ((MonoObject*)obj);
1371                 if (dislink)
1372                         mono_gc_register_disappearing_link (NULL, dislink, FALSE);
1373         }
1374
1375         return remove;
1376 }
1377
1378 static void
1379 clear_domain_process_minor_object_callback (char *obj, size_t size, MonoDomain *domain)
1380 {
1381         if (clear_domain_process_object (obj, domain))
1382                 memset (obj, 0, size);
1383 }
1384
1385 static void
1386 clear_domain_process_major_object_callback (char *obj, size_t size, MonoDomain *domain)
1387 {
1388         clear_domain_process_object (obj, domain);
1389 }
1390
1391 static void
1392 clear_domain_free_major_non_pinned_object_callback (char *obj, size_t size, MonoDomain *domain)
1393 {
1394         if (need_remove_object_for_domain (obj, domain))
1395                 major.free_non_pinned_object (obj, size);
1396 }
1397
1398 static void
1399 clear_domain_free_major_pinned_object_callback (char *obj, size_t size, MonoDomain *domain)
1400 {
1401         if (need_remove_object_for_domain (obj, domain))
1402                 major.free_pinned_object (obj, size);
1403 }
1404
1405 /*
1406  * When appdomains are unloaded we can easily remove objects that have finalizers,
1407  * but all the others could still be present in random places on the heap.
1408  * We need a sweep to get rid of them even though it's going to be costly
1409  * with big heaps.
1410  * The reason we need to remove them is because we access the vtable and class
1411  * structures to know the object size and the reference bitmap: once the domain is
1412  * unloaded the point to random memory.
1413  */
1414 void
1415 mono_gc_clear_domain (MonoDomain * domain)
1416 {
1417         LOSObject *bigobj, *prev;
1418         int i;
1419
1420         LOCK_GC;
1421
1422         clear_nursery_fragments (nursery_next);
1423
1424         if (xdomain_checks && domain != mono_get_root_domain ()) {
1425                 scan_for_registered_roots_in_domain (domain, ROOT_TYPE_NORMAL);
1426                 scan_for_registered_roots_in_domain (domain, ROOT_TYPE_WBARRIER);
1427                 check_for_xdomain_refs ();
1428         }
1429
1430         mono_sgen_scan_area_with_callback (nursery_section->data, nursery_section->end_data,
1431                         (IterateObjectCallbackFunc)clear_domain_process_minor_object_callback, domain);
1432
1433         /*Ephemerons and dislinks must be processed before LOS since they might end up pointing
1434         to memory returned to the OS.*/
1435         null_ephemerons_for_domain (domain);
1436
1437         for (i = GENERATION_NURSERY; i < GENERATION_MAX; ++i)
1438                 null_links_for_domain (domain, i);
1439
1440         /* We need two passes over major and large objects because
1441            freeing such objects might give their memory back to the OS
1442            (in the case of large objects) or obliterate its vtable
1443            (pinned objects with major-copying or pinned and non-pinned
1444            objects with major-mark&sweep), but we might need to
1445            dereference a pointer from an object to another object if
1446            the first object is a proxy. */
1447         major.iterate_objects (TRUE, TRUE, (IterateObjectCallbackFunc)clear_domain_process_major_object_callback, domain);
1448         for (bigobj = los_object_list; bigobj; bigobj = bigobj->next)
1449                 clear_domain_process_object (bigobj->data, domain);
1450
1451         prev = NULL;
1452         for (bigobj = los_object_list; bigobj;) {
1453                 if (need_remove_object_for_domain (bigobj->data, domain)) {
1454                         LOSObject *to_free = bigobj;
1455                         if (prev)
1456                                 prev->next = bigobj->next;
1457                         else
1458                                 los_object_list = bigobj->next;
1459                         bigobj = bigobj->next;
1460                         DEBUG (4, fprintf (gc_debug_file, "Freeing large object %p\n",
1461                                         bigobj->data));
1462                         free_large_object (to_free);
1463                         continue;
1464                 }
1465                 prev = bigobj;
1466                 bigobj = bigobj->next;
1467         }
1468         major.iterate_objects (TRUE, FALSE, (IterateObjectCallbackFunc)clear_domain_free_major_non_pinned_object_callback, domain);
1469         major.iterate_objects (FALSE, TRUE, (IterateObjectCallbackFunc)clear_domain_free_major_pinned_object_callback, domain);
1470
1471         UNLOCK_GC;
1472 }
1473
1474 static void
1475 global_remset_cache_clear (void)
1476 {
1477         memset (global_remset_cache, 0, sizeof (global_remset_cache));
1478 }
1479
1480 /*
1481  * Tries to check if a given remset location was already added to the global remset.
1482  * It can
1483  *
1484  * A 2 entry, LRU cache of recently saw location remsets.
1485  *
1486  * It's hand-coded instead of done using loops to reduce the number of memory references on cache hit.
1487  *
1488  * Returns TRUE is the element was added..
1489  */
1490 static gboolean
1491 global_remset_location_was_not_added (gpointer ptr)
1492 {
1493
1494         gpointer first = global_remset_cache [0], second;
1495         if (first == ptr) {
1496                 HEAVY_STAT (++stat_global_remsets_discarded);
1497                 return FALSE;
1498         }
1499
1500         second = global_remset_cache [1];
1501
1502         if (second == ptr) {
1503                 /*Move the second to the front*/
1504                 global_remset_cache [0] = second;
1505                 global_remset_cache [1] = first;
1506
1507                 HEAVY_STAT (++stat_global_remsets_discarded);
1508                 return FALSE;
1509         }
1510
1511         global_remset_cache [0] = second;
1512         global_remset_cache [1] = ptr;
1513         return TRUE;
1514 }
1515
1516 /*
1517  * mono_sgen_add_to_global_remset:
1518  *
1519  *   The global remset contains locations which point into newspace after
1520  * a minor collection. This can happen if the objects they point to are pinned.
1521  */
1522 void
1523 mono_sgen_add_to_global_remset (gpointer ptr)
1524 {
1525         RememberedSet *rs;
1526
1527         g_assert (!ptr_in_nursery (ptr) && ptr_in_nursery (*(gpointer*)ptr));
1528
1529         if (!global_remset_location_was_not_added (ptr))
1530                 return;
1531
1532         DEBUG (8, fprintf (gc_debug_file, "Adding global remset for %p\n", ptr));
1533         binary_protocol_global_remset (ptr, *(gpointer*)ptr, (gpointer)LOAD_VTABLE (*(gpointer*)ptr));
1534
1535         HEAVY_STAT (++stat_global_remsets_added);
1536
1537         /* 
1538          * FIXME: If an object remains pinned, we need to add it at every minor collection.
1539          * To avoid uncontrolled growth of the global remset, only add each pointer once.
1540          */
1541         if (global_remset->store_next + 3 < global_remset->end_set) {
1542                 *(global_remset->store_next++) = (mword)ptr;
1543                 return;
1544         }
1545         rs = alloc_remset (global_remset->end_set - global_remset->data, NULL);
1546         rs->next = global_remset;
1547         global_remset = rs;
1548         *(global_remset->store_next++) = (mword)ptr;
1549
1550         {
1551                 int global_rs_size = 0;
1552
1553                 for (rs = global_remset; rs; rs = rs->next) {
1554                         global_rs_size += rs->store_next - rs->data;
1555                 }
1556                 DEBUG (4, fprintf (gc_debug_file, "Global remset now has size %d\n", global_rs_size));
1557         }
1558 }
1559
1560 /*
1561  * drain_gray_stack:
1562  *
1563  *   Scan objects in the gray stack until the stack is empty. This should be called
1564  * frequently after each object is copied, to achieve better locality and cache
1565  * usage.
1566  */
1567 static void inline
1568 drain_gray_stack (GrayQueue *queue)
1569 {
1570         char *obj;
1571
1572         if (current_collection_generation == GENERATION_NURSERY) {
1573                 for (;;) {
1574                         GRAY_OBJECT_DEQUEUE (queue, obj);
1575                         if (!obj)
1576                                 break;
1577                         DEBUG (9, fprintf (gc_debug_file, "Precise gray object scan %p (%s)\n", obj, safe_name (obj)));
1578                         major.minor_scan_object (obj, queue);
1579                 }
1580         } else {
1581                 for (;;) {
1582                         GRAY_OBJECT_DEQUEUE (queue, obj);
1583                         if (!obj)
1584                                 break;
1585                         DEBUG (9, fprintf (gc_debug_file, "Precise gray object scan %p (%s)\n", obj, safe_name (obj)));
1586                         major.major_scan_object (obj, queue);
1587                 }
1588         }
1589 }
1590
1591 /*
1592  * Addresses from start to end are already sorted. This function finds
1593  * the object header for each address and pins the object. The
1594  * addresses must be inside the passed section.  The (start of the)
1595  * address array is overwritten with the addresses of the actually
1596  * pinned objects.  Return the number of pinned objects.
1597  */
1598 static int
1599 pin_objects_from_addresses (GCMemSection *section, void **start, void **end, void *start_nursery, void *end_nursery, GrayQueue *queue)
1600 {
1601         void *last = NULL;
1602         int count = 0;
1603         void *search_start;
1604         void *last_obj = NULL;
1605         size_t last_obj_size = 0;
1606         void *addr;
1607         int idx;
1608         void **definitely_pinned = start;
1609         while (start < end) {
1610                 addr = *start;
1611                 /* the range check should be reduntant */
1612                 if (addr != last && addr >= start_nursery && addr < end_nursery) {
1613                         DEBUG (5, fprintf (gc_debug_file, "Considering pinning addr %p\n", addr));
1614                         /* multiple pointers to the same object */
1615                         if (addr >= last_obj && (char*)addr < (char*)last_obj + last_obj_size) {
1616                                 start++;
1617                                 continue;
1618                         }
1619                         idx = ((char*)addr - (char*)section->data) / SCAN_START_SIZE;
1620                         g_assert (idx < section->num_scan_start);
1621                         search_start = (void*)section->scan_starts [idx];
1622                         if (!search_start || search_start > addr) {
1623                                 while (idx) {
1624                                         --idx;
1625                                         search_start = section->scan_starts [idx];
1626                                         if (search_start && search_start <= addr)
1627                                                 break;
1628                                 }
1629                                 if (!search_start || search_start > addr)
1630                                         search_start = start_nursery;
1631                         }
1632                         if (search_start < last_obj)
1633                                 search_start = (char*)last_obj + last_obj_size;
1634                         /* now addr should be in an object a short distance from search_start
1635                          * Note that search_start must point to zeroed mem or point to an object.
1636                          */
1637                         do {
1638                                 if (!*(void**)search_start) {
1639                                         search_start = (void*)ALIGN_UP ((mword)search_start + sizeof (gpointer));
1640                                         continue;
1641                                 }
1642                                 last_obj = search_start;
1643                                 last_obj_size = ALIGN_UP (safe_object_get_size ((MonoObject*)search_start));
1644                                 DEBUG (8, fprintf (gc_debug_file, "Pinned try match %p (%s), size %zd\n", last_obj, safe_name (last_obj), last_obj_size));
1645                                 if (addr >= search_start && (char*)addr < (char*)last_obj + last_obj_size) {
1646                                         DEBUG (4, fprintf (gc_debug_file, "Pinned object %p, vtable %p (%s), count %d\n", search_start, *(void**)search_start, safe_name (search_start), count));
1647                                         binary_protocol_pin (search_start, (gpointer)LOAD_VTABLE (search_start), safe_object_get_size (search_start));
1648                                         pin_object (search_start);
1649                                         GRAY_OBJECT_ENQUEUE (queue, search_start);
1650                                         if (heap_dump_file)
1651                                                 mono_sgen_pin_stats_register_object (search_start, last_obj_size);
1652                                         definitely_pinned [count] = search_start;
1653                                         count++;
1654                                         break;
1655                                 }
1656                                 /* skip to the next object */
1657                                 search_start = (void*)((char*)search_start + last_obj_size);
1658                         } while (search_start <= addr);
1659                         /* we either pinned the correct object or we ignored the addr because
1660                          * it points to unused zeroed memory.
1661                          */
1662                         last = addr;
1663                 }
1664                 start++;
1665         }
1666         //printf ("effective pinned: %d (at the end: %d)\n", count, (char*)end_nursery - (char*)last);
1667         return count;
1668 }
1669
1670 void
1671 mono_sgen_pin_objects_in_section (GCMemSection *section, GrayQueue *queue)
1672 {
1673         int num_entries = section->pin_queue_num_entries;
1674         if (num_entries) {
1675                 void **start = section->pin_queue_start;
1676                 int reduced_to;
1677                 reduced_to = pin_objects_from_addresses (section, start, start + num_entries,
1678                                 section->data, section->next_data, queue);
1679                 section->pin_queue_num_entries = reduced_to;
1680                 if (!reduced_to)
1681                         section->pin_queue_start = NULL;
1682         }
1683 }
1684
1685 /* Sort the addresses in array in increasing order.
1686  * Done using a by-the book heap sort. Which has decent and stable performance, is pretty cache efficient.
1687  */
1688 static void
1689 sort_addresses (void **array, int size)
1690 {
1691         int i;
1692         void *tmp;
1693
1694         for (i = 1; i < size; ++i) {
1695                 int child = i;
1696                 while (child > 0) {
1697                         int parent = (child - 1) / 2;
1698
1699                         if (array [parent] >= array [child])
1700                                 break;
1701
1702                         tmp = array [parent];
1703                         array [parent] = array [child];
1704                         array [child] = tmp;
1705
1706                         child = parent;
1707                 }
1708         }
1709
1710         for (i = size - 1; i > 0; --i) {
1711                 int end, root;
1712                 tmp = array [i];
1713                 array [i] = array [0];
1714                 array [0] = tmp;
1715
1716                 end = i - 1;
1717                 root = 0;
1718
1719                 while (root * 2 + 1 <= end) {
1720                         int child = root * 2 + 1;
1721
1722                         if (child < end && array [child] < array [child + 1])
1723                                 ++child;
1724                         if (array [root] >= array [child])
1725                                 break;
1726
1727                         tmp = array [root];
1728                         array [root] = array [child];
1729                         array [child] = tmp;
1730
1731                         root = child;
1732                 }
1733         }
1734 }
1735
1736 static G_GNUC_UNUSED void
1737 print_nursery_gaps (void* start_nursery, void *end_nursery)
1738 {
1739         int i;
1740         gpointer first = start_nursery;
1741         gpointer next;
1742         for (i = 0; i < next_pin_slot; ++i) {
1743                 next = pin_queue [i];
1744                 fprintf (gc_debug_file, "Nursery range: %p-%p, size: %td\n", first, next, (char*)next-(char*)first);
1745                 first = next;
1746         }
1747         next = end_nursery;
1748         fprintf (gc_debug_file, "Nursery range: %p-%p, size: %td\n", first, next, (char*)next-(char*)first);
1749 }
1750
1751 /* reduce the info in the pin queue, removing duplicate pointers and sorting them */
1752 static void
1753 optimize_pin_queue (int start_slot)
1754 {
1755         void **start, **cur, **end;
1756         /* sort and uniq pin_queue: we just sort and we let the rest discard multiple values */
1757         /* it may be better to keep ranges of pinned memory instead of individually pinning objects */
1758         DEBUG (5, fprintf (gc_debug_file, "Sorting pin queue, size: %d\n", next_pin_slot));
1759         if ((next_pin_slot - start_slot) > 1)
1760                 sort_addresses (pin_queue + start_slot, next_pin_slot - start_slot);
1761         start = cur = pin_queue + start_slot;
1762         end = pin_queue + next_pin_slot;
1763         while (cur < end) {
1764                 *start = *cur++;
1765                 while (*start == *cur && cur < end)
1766                         cur++;
1767                 start++;
1768         };
1769         next_pin_slot = start - pin_queue;
1770         DEBUG (5, fprintf (gc_debug_file, "Pin queue reduced to size: %d\n", next_pin_slot));
1771         //DEBUG (6, print_nursery_gaps (start_nursery, end_nursery));
1772         
1773 }
1774
1775 /* 
1776  * Scan the memory between start and end and queue values which could be pointers
1777  * to the area between start_nursery and end_nursery for later consideration.
1778  * Typically used for thread stacks.
1779  */
1780 static void
1781 conservatively_pin_objects_from (void **start, void **end, void *start_nursery, void *end_nursery, int pin_type)
1782 {
1783         int count = 0;
1784         while (start < end) {
1785                 if (*start >= start_nursery && *start < end_nursery) {
1786                         /*
1787                          * *start can point to the middle of an object
1788                          * note: should we handle pointing at the end of an object?
1789                          * pinning in C# code disallows pointing at the end of an object
1790                          * but there is some small chance that an optimizing C compiler
1791                          * may keep the only reference to an object by pointing
1792                          * at the end of it. We ignore this small chance for now.
1793                          * Pointers to the end of an object are indistinguishable
1794                          * from pointers to the start of the next object in memory
1795                          * so if we allow that we'd need to pin two objects...
1796                          * We queue the pointer in an array, the
1797                          * array will then be sorted and uniqued. This way
1798                          * we can coalesce several pinning pointers and it should
1799                          * be faster since we'd do a memory scan with increasing
1800                          * addresses. Note: we can align the address to the allocation
1801                          * alignment, so the unique process is more effective.
1802                          */
1803                         mword addr = (mword)*start;
1804                         addr &= ~(ALLOC_ALIGN - 1);
1805                         if (addr >= (mword)start_nursery && addr < (mword)end_nursery)
1806                                 pin_stage_ptr ((void*)addr);
1807                         if (heap_dump_file)
1808                                 pin_stats_register_address ((char*)addr, pin_type);
1809                         DEBUG (6, if (count) fprintf (gc_debug_file, "Pinning address %p\n", (void*)addr));
1810                         count++;
1811                 }
1812                 start++;
1813         }
1814         DEBUG (7, if (count) fprintf (gc_debug_file, "found %d potential pinned heap pointers\n", count));
1815 }
1816
1817 /*
1818  * Debugging function: find in the conservative roots where @obj is being pinned.
1819  */
1820 static G_GNUC_UNUSED void
1821 find_pinning_reference (char *obj, size_t size)
1822 {
1823         RootRecord *root;
1824         int i;
1825         char *endobj = obj + size;
1826         for (i = 0; i < roots_hash_size [0]; ++i) {
1827                 for (root = roots_hash [0][i]; root; root = root->next) {
1828                         /* if desc is non-null it has precise info */
1829                         if (!root->root_desc) {
1830                                 char ** start = (char**)root->start_root;
1831                                 while (start < (char**)root->end_root) {
1832                                         if (*start >= obj && *start < endobj) {
1833                                                 DEBUG (0, fprintf (gc_debug_file, "Object %p referenced in pinned roots %p-%p (at %p in record %p)\n", obj, root->start_root, root->end_root, start, root));
1834                                         }
1835                                         start++;
1836                                 }
1837                         }
1838                 }
1839         }
1840         find_pinning_ref_from_thread (obj, size);
1841 }
1842
1843 /*
1844  * The first thing we do in a collection is to identify pinned objects.
1845  * This function considers all the areas of memory that need to be
1846  * conservatively scanned.
1847  */
1848 static void
1849 pin_from_roots (void *start_nursery, void *end_nursery)
1850 {
1851         RootRecord *root;
1852         int i;
1853         DEBUG (2, fprintf (gc_debug_file, "Scanning pinned roots (%d bytes, %d/%d entries)\n", (int)roots_size, num_roots_entries [ROOT_TYPE_NORMAL], num_roots_entries [ROOT_TYPE_PINNED]));
1854         /* objects pinned from the API are inside these roots */
1855         for (i = 0; i < roots_hash_size [ROOT_TYPE_PINNED]; ++i) {
1856                 for (root = roots_hash [ROOT_TYPE_PINNED][i]; root; root = root->next) {
1857                         DEBUG (6, fprintf (gc_debug_file, "Pinned roots %p-%p\n", root->start_root, root->end_root));
1858                         conservatively_pin_objects_from ((void**)root->start_root, (void**)root->end_root, start_nursery, end_nursery, PIN_TYPE_OTHER);
1859                 }
1860         }
1861         /* now deal with the thread stacks
1862          * in the future we should be able to conservatively scan only:
1863          * *) the cpu registers
1864          * *) the unmanaged stack frames
1865          * *) the _last_ managed stack frame
1866          * *) pointers slots in managed frames
1867          */
1868         scan_thread_data (start_nursery, end_nursery, FALSE);
1869
1870         evacuate_pin_staging_area ();
1871 }
1872
1873 static CopyOrMarkObjectFunc user_copy_or_mark_func;
1874 static GrayQueue *user_copy_or_mark_queue;
1875
1876 static void
1877 single_arg_user_copy_or_mark (void **obj)
1878 {
1879         user_copy_or_mark_func (obj, user_copy_or_mark_queue);
1880 }
1881
1882 /*
1883  * The memory area from start_root to end_root contains pointers to objects.
1884  * Their position is precisely described by @desc (this means that the pointer
1885  * can be either NULL or the pointer to the start of an object).
1886  * This functions copies them to to_space updates them.
1887  *
1888  * This function is not thread-safe!
1889  */
1890 static void
1891 precisely_scan_objects_from (CopyOrMarkObjectFunc copy_func, void** start_root, void** end_root, char* n_start, char *n_end, mword desc, GrayQueue *queue)
1892 {
1893         switch (desc & ROOT_DESC_TYPE_MASK) {
1894         case ROOT_DESC_BITMAP:
1895                 desc >>= ROOT_DESC_TYPE_SHIFT;
1896                 while (desc) {
1897                         if ((desc & 1) && *start_root) {
1898                                 copy_func (start_root, queue);
1899                                 DEBUG (9, fprintf (gc_debug_file, "Overwrote root at %p with %p\n", start_root, *start_root));
1900                                 drain_gray_stack (queue);
1901                         }
1902                         desc >>= 1;
1903                         start_root++;
1904                 }
1905                 return;
1906         case ROOT_DESC_COMPLEX: {
1907                 gsize *bitmap_data = complex_descriptors + (desc >> ROOT_DESC_TYPE_SHIFT);
1908                 int bwords = (*bitmap_data) - 1;
1909                 void **start_run = start_root;
1910                 bitmap_data++;
1911                 while (bwords-- > 0) {
1912                         gsize bmap = *bitmap_data++;
1913                         void **objptr = start_run;
1914                         while (bmap) {
1915                                 if ((bmap & 1) && *objptr) {
1916                                         copy_func (objptr, queue);
1917                                         DEBUG (9, fprintf (gc_debug_file, "Overwrote root at %p with %p\n", objptr, *objptr));
1918                                         drain_gray_stack (queue);
1919                                 }
1920                                 bmap >>= 1;
1921                                 ++objptr;
1922                         }
1923                         start_run += GC_BITS_PER_WORD;
1924                 }
1925                 break;
1926         }
1927         case ROOT_DESC_USER: {
1928                 MonoGCRootMarkFunc marker = user_descriptors [desc >> ROOT_DESC_TYPE_SHIFT];
1929                 user_copy_or_mark_func = copy_func;
1930                 user_copy_or_mark_queue = queue;
1931                 marker (start_root, single_arg_user_copy_or_mark);
1932                 user_copy_or_mark_func = NULL;
1933                 user_copy_or_mark_queue = NULL;
1934                 break;
1935         }
1936         case ROOT_DESC_RUN_LEN:
1937                 g_assert_not_reached ();
1938         default:
1939                 g_assert_not_reached ();
1940         }
1941 }
1942
1943 void
1944 mono_sgen_update_heap_boundaries (mword low, mword high)
1945 {
1946         mword old;
1947
1948         do {
1949                 old = lowest_heap_address;
1950                 if (low >= old)
1951                         break;
1952         } while (SGEN_CAS_PTR ((gpointer*)&lowest_heap_address, (gpointer)low, (gpointer)old) != (gpointer)old);
1953
1954         do {
1955                 old = highest_heap_address;
1956                 if (high <= old)
1957                         break;
1958         } while (SGEN_CAS_PTR ((gpointer*)&highest_heap_address, (gpointer)high, (gpointer)old) != (gpointer)old);
1959 }
1960
1961 static Fragment*
1962 alloc_fragment (void)
1963 {
1964         Fragment *frag = fragment_freelist;
1965         if (frag) {
1966                 fragment_freelist = frag->next;
1967                 frag->next = NULL;
1968                 return frag;
1969         }
1970         frag = mono_sgen_alloc_internal (INTERNAL_MEM_FRAGMENT);
1971         frag->next = NULL;
1972         return frag;
1973 }
1974
1975 /* size must be a power of 2 */
1976 void*
1977 mono_sgen_alloc_os_memory_aligned (mword size, mword alignment, gboolean activate)
1978 {
1979         /* Allocate twice the memory to be able to put the block on an aligned address */
1980         char *mem = mono_sgen_alloc_os_memory (size + alignment, activate);
1981         char *aligned;
1982
1983         g_assert (mem);
1984
1985         aligned = (char*)((mword)(mem + (alignment - 1)) & ~(alignment - 1));
1986         g_assert (aligned >= mem && aligned + size <= mem + size + alignment && !((mword)aligned & (alignment - 1)));
1987
1988         if (aligned > mem)
1989                 mono_sgen_free_os_memory (mem, aligned - mem);
1990         if (aligned + size < mem + size + alignment)
1991                 mono_sgen_free_os_memory (aligned + size, (mem + size + alignment) - (aligned + size));
1992
1993         return aligned;
1994 }
1995
1996 /*
1997  * Allocate and setup the data structures needed to be able to allocate objects
1998  * in the nursery. The nursery is stored in nursery_section.
1999  */
2000 static void
2001 alloc_nursery (void)
2002 {
2003         GCMemSection *section;
2004         char *data;
2005         int scan_starts;
2006         Fragment *frag;
2007         int alloc_size;
2008
2009         if (nursery_section)
2010                 return;
2011         DEBUG (2, fprintf (gc_debug_file, "Allocating nursery size: %lu\n", (unsigned long)nursery_size));
2012         /* later we will alloc a larger area for the nursery but only activate
2013          * what we need. The rest will be used as expansion if we have too many pinned
2014          * objects in the existing nursery.
2015          */
2016         /* FIXME: handle OOM */
2017         section = mono_sgen_alloc_internal (INTERNAL_MEM_SECTION);
2018
2019         g_assert (nursery_size == DEFAULT_NURSERY_SIZE);
2020         alloc_size = nursery_size;
2021 #ifdef SGEN_ALIGN_NURSERY
2022         data = mono_sgen_alloc_os_memory_aligned (alloc_size, alloc_size, TRUE);
2023 #else
2024         data = mono_sgen_alloc_os_memory (alloc_size, TRUE);
2025 #endif
2026         nursery_start = data;
2027         nursery_real_end = nursery_start + nursery_size;
2028         mono_sgen_update_heap_boundaries ((mword)nursery_start, (mword)nursery_real_end);
2029         nursery_next = nursery_start;
2030         DEBUG (4, fprintf (gc_debug_file, "Expanding nursery size (%p-%p): %lu, total: %lu\n", data, data + alloc_size, (unsigned long)nursery_size, (unsigned long)total_alloc));
2031         section->data = section->next_data = data;
2032         section->size = alloc_size;
2033         section->end_data = nursery_real_end;
2034         scan_starts = (alloc_size + SCAN_START_SIZE - 1) / SCAN_START_SIZE;
2035         section->scan_starts = mono_sgen_alloc_internal_dynamic (sizeof (char*) * scan_starts, INTERNAL_MEM_SCAN_STARTS);
2036         section->num_scan_start = scan_starts;
2037         section->block.role = MEMORY_ROLE_GEN0;
2038         section->block.next = NULL;
2039
2040         nursery_section = section;
2041
2042         /* Setup the single first large fragment */
2043         frag = alloc_fragment ();
2044         frag->fragment_start = nursery_start;
2045         frag->fragment_limit = nursery_start;
2046         frag->fragment_end = nursery_real_end;
2047         nursery_frag_real_end = nursery_real_end;
2048         /* FIXME: frag here is lost */
2049 }
2050
2051 static void
2052 scan_finalizer_entries (CopyOrMarkObjectFunc copy_func, FinalizeEntry *list, GrayQueue *queue)
2053 {
2054         FinalizeEntry *fin;
2055
2056         for (fin = list; fin; fin = fin->next) {
2057                 if (!fin->object)
2058                         continue;
2059                 DEBUG (5, fprintf (gc_debug_file, "Scan of fin ready object: %p (%s)\n", fin->object, safe_name (fin->object)));
2060                 copy_func (&fin->object, queue);
2061         }
2062 }
2063
2064 static mword fragment_total = 0;
2065 /*
2066  * We found a fragment of free memory in the nursery: memzero it and if
2067  * it is big enough, add it to the list of fragments that can be used for
2068  * allocation.
2069  */
2070 static void
2071 add_nursery_frag (size_t frag_size, char* frag_start, char* frag_end)
2072 {
2073         Fragment *fragment;
2074         DEBUG (4, fprintf (gc_debug_file, "Found empty fragment: %p-%p, size: %zd\n", frag_start, frag_end, frag_size));
2075         binary_protocol_empty (frag_start, frag_size);
2076         /* memsetting just the first chunk start is bound to provide better cache locality */
2077         if (nursery_clear_policy == CLEAR_AT_GC)
2078                 memset (frag_start, 0, frag_size);
2079         /* Not worth dealing with smaller fragments: need to tune */
2080         if (frag_size >= FRAGMENT_MIN_SIZE) {
2081                 fragment = alloc_fragment ();
2082                 fragment->fragment_start = frag_start;
2083                 fragment->fragment_limit = frag_start;
2084                 fragment->fragment_end = frag_end;
2085                 fragment->next = nursery_fragments;
2086                 nursery_fragments = fragment;
2087                 fragment_total += frag_size;
2088         } else {
2089                 /* Clear unused fragments, pinning depends on this */
2090                 /*TODO place an int[] here instead of the memset if size justify it*/
2091                 memset (frag_start, 0, frag_size);
2092         }
2093 }
2094
2095 static const char*
2096 generation_name (int generation)
2097 {
2098         switch (generation) {
2099         case GENERATION_NURSERY: return "nursery";
2100         case GENERATION_OLD: return "old";
2101         default: g_assert_not_reached ();
2102         }
2103 }
2104
2105 static DisappearingLinkHashTable*
2106 get_dislink_hash_table (int generation)
2107 {
2108         switch (generation) {
2109         case GENERATION_NURSERY: return &minor_disappearing_link_hash;
2110         case GENERATION_OLD: return &major_disappearing_link_hash;
2111         default: g_assert_not_reached ();
2112         }
2113 }
2114
2115 static FinalizeEntryHashTable*
2116 get_finalize_entry_hash_table (int generation)
2117 {
2118         switch (generation) {
2119         case GENERATION_NURSERY: return &minor_finalizable_hash;
2120         case GENERATION_OLD: return &major_finalizable_hash;
2121         default: g_assert_not_reached ();
2122         }
2123 }
2124
2125 static void
2126 finish_gray_stack (char *start_addr, char *end_addr, int generation, GrayQueue *queue)
2127 {
2128         TV_DECLARE (atv);
2129         TV_DECLARE (btv);
2130         int fin_ready;
2131         int ephemeron_rounds = 0;
2132         CopyOrMarkObjectFunc copy_func = current_collection_generation == GENERATION_NURSERY ? major.copy_object : major.copy_or_mark_object;
2133
2134         /*
2135          * We copied all the reachable objects. Now it's the time to copy
2136          * the objects that were not referenced by the roots, but by the copied objects.
2137          * we built a stack of objects pointed to by gray_start: they are
2138          * additional roots and we may add more items as we go.
2139          * We loop until gray_start == gray_objects which means no more objects have
2140          * been added. Note this is iterative: no recursion is involved.
2141          * We need to walk the LO list as well in search of marked big objects
2142          * (use a flag since this is needed only on major collections). We need to loop
2143          * here as well, so keep a counter of marked LO (increasing it in copy_object).
2144          *   To achieve better cache locality and cache usage, we drain the gray stack 
2145          * frequently, after each object is copied, and just finish the work here.
2146          */
2147         drain_gray_stack (queue);
2148         TV_GETTIME (atv);
2149         DEBUG (2, fprintf (gc_debug_file, "%s generation done\n", generation_name (generation)));
2150         /* walk the finalization queue and move also the objects that need to be
2151          * finalized: use the finalized objects as new roots so the objects they depend
2152          * on are also not reclaimed. As with the roots above, only objects in the nursery
2153          * are marked/copied.
2154          * We need a loop here, since objects ready for finalizers may reference other objects
2155          * that are fin-ready. Speedup with a flag?
2156          */
2157         do {
2158                 /*
2159                  * Walk the ephemeron tables marking all values with reachable keys. This must be completely done
2160                  * before processing finalizable objects to avoid finalizing reachable values.
2161                  *
2162                  * It must be done inside the finalizaters loop since objects must not be removed from CWT tables
2163                  * while they are been finalized.
2164                  */
2165                 int done_with_ephemerons = 0;
2166                 do {
2167                         done_with_ephemerons = mark_ephemerons_in_range (copy_func, start_addr, end_addr, queue);
2168                         drain_gray_stack (queue);
2169                         ++ephemeron_rounds;
2170                 } while (!done_with_ephemerons);
2171
2172                 fin_ready = num_ready_finalizers;
2173                 finalize_in_range (copy_func, start_addr, end_addr, generation, queue);
2174                 if (generation == GENERATION_OLD)
2175                         finalize_in_range (copy_func, nursery_start, nursery_real_end, GENERATION_NURSERY, queue);
2176
2177                 /* drain the new stack that might have been created */
2178                 DEBUG (6, fprintf (gc_debug_file, "Precise scan of gray area post fin\n"));
2179                 drain_gray_stack (queue);
2180         } while (fin_ready != num_ready_finalizers);
2181
2182         /*
2183          * Clear ephemeron pairs with unreachable keys.
2184          * We pass the copy func so we can figure out if an array was promoted or not.
2185          */
2186         clear_unreachable_ephemerons (copy_func, start_addr, end_addr, queue);
2187
2188         TV_GETTIME (btv);
2189         DEBUG (2, fprintf (gc_debug_file, "Finalize queue handling scan for %s generation: %d usecs %d ephemeron roundss\n", generation_name (generation), TV_ELAPSED (atv, btv), ephemeron_rounds));
2190
2191         /*
2192          * handle disappearing links
2193          * Note we do this after checking the finalization queue because if an object
2194          * survives (at least long enough to be finalized) we don't clear the link.
2195          * This also deals with a possible issue with the monitor reclamation: with the Boehm
2196          * GC a finalized object my lose the monitor because it is cleared before the finalizer is
2197          * called.
2198          */
2199         g_assert (gray_object_queue_is_empty (queue));
2200         for (;;) {
2201                 null_link_in_range (copy_func, start_addr, end_addr, generation, queue);
2202                 if (generation == GENERATION_OLD)
2203                         null_link_in_range (copy_func, start_addr, end_addr, GENERATION_NURSERY, queue);
2204                 if (gray_object_queue_is_empty (queue))
2205                         break;
2206                 drain_gray_stack (queue);
2207         }
2208
2209         g_assert (gray_object_queue_is_empty (queue));
2210 }
2211
2212 void
2213 mono_sgen_check_section_scan_starts (GCMemSection *section)
2214 {
2215         int i;
2216         for (i = 0; i < section->num_scan_start; ++i) {
2217                 if (section->scan_starts [i]) {
2218                         guint size = safe_object_get_size ((MonoObject*) section->scan_starts [i]);
2219                         g_assert (size >= sizeof (MonoObject) && size <= MAX_SMALL_OBJ_SIZE);
2220                 }
2221         }
2222 }
2223
2224 static void
2225 check_scan_starts (void)
2226 {
2227         if (!do_scan_starts_check)
2228                 return;
2229         mono_sgen_check_section_scan_starts (nursery_section);
2230         major.check_scan_starts ();
2231 }
2232
2233 static int last_num_pinned = 0;
2234
2235 static void
2236 build_nursery_fragments (void **start, int num_entries)
2237 {
2238         char *frag_start, *frag_end;
2239         size_t frag_size;
2240         int i;
2241
2242         while (nursery_fragments) {
2243                 Fragment *next = nursery_fragments->next;
2244                 nursery_fragments->next = fragment_freelist;
2245                 fragment_freelist = nursery_fragments;
2246                 nursery_fragments = next;
2247         }
2248         frag_start = nursery_start;
2249         fragment_total = 0;
2250         /* clear scan starts */
2251         memset (nursery_section->scan_starts, 0, nursery_section->num_scan_start * sizeof (gpointer));
2252         for (i = 0; i < num_entries; ++i) {
2253                 frag_end = start [i];
2254                 /* remove the pin bit from pinned objects */
2255                 unpin_object (frag_end);
2256                 nursery_section->scan_starts [((char*)frag_end - (char*)nursery_section->data)/SCAN_START_SIZE] = frag_end;
2257                 frag_size = frag_end - frag_start;
2258                 if (frag_size)
2259                         add_nursery_frag (frag_size, frag_start, frag_end);
2260                 frag_size = ALIGN_UP (safe_object_get_size ((MonoObject*)start [i]));
2261                 frag_start = (char*)start [i] + frag_size;
2262         }
2263         nursery_last_pinned_end = frag_start;
2264         frag_end = nursery_real_end;
2265         frag_size = frag_end - frag_start;
2266         if (frag_size)
2267                 add_nursery_frag (frag_size, frag_start, frag_end);
2268         if (!nursery_fragments) {
2269                 DEBUG (1, fprintf (gc_debug_file, "Nursery fully pinned (%d)\n", num_entries));
2270                 for (i = 0; i < num_entries; ++i) {
2271                         DEBUG (3, fprintf (gc_debug_file, "Bastard pinning obj %p (%s), size: %d\n", start [i], safe_name (start [i]), safe_object_get_size (start [i])));
2272                 }
2273                 degraded_mode = 1;
2274         }
2275
2276         nursery_next = nursery_frag_real_end = NULL;
2277
2278         /* Clear TLABs for all threads */
2279         clear_tlabs ();
2280 }
2281
2282 static void
2283 scan_from_registered_roots (CopyOrMarkObjectFunc copy_func, char *addr_start, char *addr_end, int root_type, GrayQueue *queue)
2284 {
2285         int i;
2286         RootRecord *root;
2287         for (i = 0; i < roots_hash_size [root_type]; ++i) {
2288                 for (root = roots_hash [root_type][i]; root; root = root->next) {
2289                         DEBUG (6, fprintf (gc_debug_file, "Precise root scan %p-%p (desc: %p)\n", root->start_root, root->end_root, (void*)root->root_desc));
2290                         precisely_scan_objects_from (copy_func, (void**)root->start_root, (void**)root->end_root, addr_start, addr_end, root->root_desc, queue);
2291                 }
2292         }
2293 }
2294
2295 void
2296 mono_sgen_dump_occupied (char *start, char *end, char *section_start)
2297 {
2298         fprintf (heap_dump_file, "<occupied offset=\"%td\" size=\"%td\"/>\n", start - section_start, end - start);
2299 }
2300
2301 void
2302 mono_sgen_dump_section (GCMemSection *section, const char *type)
2303 {
2304         char *start = section->data;
2305         char *end = section->data + section->size;
2306         char *occ_start = NULL;
2307         GCVTable *vt;
2308         char *old_start = NULL; /* just for debugging */
2309
2310         fprintf (heap_dump_file, "<section type=\"%s\" size=\"%lu\">\n", type, (unsigned long)section->size);
2311
2312         while (start < end) {
2313                 guint size;
2314                 MonoClass *class;
2315
2316                 if (!*(void**)start) {
2317                         if (occ_start) {
2318                                 mono_sgen_dump_occupied (occ_start, start, section->data);
2319                                 occ_start = NULL;
2320                         }
2321                         start += sizeof (void*); /* should be ALLOC_ALIGN, really */
2322                         continue;
2323                 }
2324                 g_assert (start < section->next_data);
2325
2326                 if (!occ_start)
2327                         occ_start = start;
2328
2329                 vt = (GCVTable*)LOAD_VTABLE (start);
2330                 class = vt->klass;
2331
2332                 size = ALIGN_UP (safe_object_get_size ((MonoObject*) start));
2333
2334                 /*
2335                 fprintf (heap_dump_file, "<object offset=\"%d\" class=\"%s.%s\" size=\"%d\"/>\n",
2336                                 start - section->data,
2337                                 vt->klass->name_space, vt->klass->name,
2338                                 size);
2339                 */
2340
2341                 old_start = start;
2342                 start += size;
2343         }
2344         if (occ_start)
2345                 mono_sgen_dump_occupied (occ_start, start, section->data);
2346
2347         fprintf (heap_dump_file, "</section>\n");
2348 }
2349
2350 static void
2351 dump_object (MonoObject *obj, gboolean dump_location)
2352 {
2353         static char class_name [1024];
2354
2355         MonoClass *class = mono_object_class (obj);
2356         int i, j;
2357
2358         /*
2359          * Python's XML parser is too stupid to parse angle brackets
2360          * in strings, so we just ignore them;
2361          */
2362         i = j = 0;
2363         while (class->name [i] && j < sizeof (class_name) - 1) {
2364                 if (!strchr ("<>\"", class->name [i]))
2365                         class_name [j++] = class->name [i];
2366                 ++i;
2367         }
2368         g_assert (j < sizeof (class_name));
2369         class_name [j] = 0;
2370
2371         fprintf (heap_dump_file, "<object class=\"%s.%s\" size=\"%d\"",
2372                         class->name_space, class_name,
2373                         safe_object_get_size (obj));
2374         if (dump_location) {
2375                 const char *location;
2376                 if (ptr_in_nursery (obj))
2377                         location = "nursery";
2378                 else if (safe_object_get_size (obj) <= MAX_SMALL_OBJ_SIZE)
2379                         location = "major";
2380                 else
2381                         location = "LOS";
2382                 fprintf (heap_dump_file, " location=\"%s\"", location);
2383         }
2384         fprintf (heap_dump_file, "/>\n");
2385 }
2386
2387 static void
2388 dump_heap (const char *type, int num, const char *reason)
2389 {
2390         ObjectList *list;
2391         LOSObject *bigobj;
2392
2393         fprintf (heap_dump_file, "<collection type=\"%s\" num=\"%d\"", type, num);
2394         if (reason)
2395                 fprintf (heap_dump_file, " reason=\"%s\"", reason);
2396         fprintf (heap_dump_file, ">\n");
2397         fprintf (heap_dump_file, "<other-mem-usage type=\"mempools\" size=\"%ld\"/>\n", mono_mempool_get_bytes_allocated ());
2398         mono_sgen_dump_internal_mem_usage (heap_dump_file);
2399         fprintf (heap_dump_file, "<pinned type=\"stack\" bytes=\"%zu\"/>\n", pinned_byte_counts [PIN_TYPE_STACK]);
2400         /* fprintf (heap_dump_file, "<pinned type=\"static-data\" bytes=\"%d\"/>\n", pinned_byte_counts [PIN_TYPE_STATIC_DATA]); */
2401         fprintf (heap_dump_file, "<pinned type=\"other\" bytes=\"%zu\"/>\n", pinned_byte_counts [PIN_TYPE_OTHER]);
2402
2403         fprintf (heap_dump_file, "<pinned-objects>\n");
2404         for (list = pinned_objects; list; list = list->next)
2405                 dump_object (list->obj, TRUE);
2406         fprintf (heap_dump_file, "</pinned-objects>\n");
2407
2408         mono_sgen_dump_section (nursery_section, "nursery");
2409
2410         major.dump_heap (heap_dump_file);
2411
2412         fprintf (heap_dump_file, "<los>\n");
2413         for (bigobj = los_object_list; bigobj; bigobj = bigobj->next)
2414                 dump_object ((MonoObject*)bigobj->data, FALSE);
2415         fprintf (heap_dump_file, "</los>\n");
2416
2417         fprintf (heap_dump_file, "</collection>\n");
2418 }
2419
2420 void
2421 mono_sgen_register_moved_object (void *obj, void *destination)
2422 {
2423         g_assert (mono_profiler_events & MONO_PROFILE_GC_MOVES);
2424
2425         /* FIXME: handle this for parallel collector */
2426 #ifdef SGEN_PARALLEL_MARK
2427         g_assert_not_reached ();
2428 #endif
2429         if (moved_objects_idx == MOVED_OBJECTS_NUM) {
2430                 mono_profiler_gc_moves (moved_objects, moved_objects_idx);
2431                 moved_objects_idx = 0;
2432         }
2433         moved_objects [moved_objects_idx++] = obj;
2434         moved_objects [moved_objects_idx++] = destination;
2435 }
2436
2437 static void
2438 init_stats (void)
2439 {
2440         static gboolean inited = FALSE;
2441
2442         if (inited)
2443                 return;
2444
2445         mono_counters_register ("Minor fragment clear", MONO_COUNTER_GC | MONO_COUNTER_LONG, &time_minor_pre_collection_fragment_clear);
2446         mono_counters_register ("Minor pinning", MONO_COUNTER_GC | MONO_COUNTER_LONG, &time_minor_pinning);
2447         mono_counters_register ("Minor scan remsets", MONO_COUNTER_GC | MONO_COUNTER_LONG, &time_minor_scan_remsets);
2448         mono_counters_register ("Minor scan pinned", MONO_COUNTER_GC | MONO_COUNTER_LONG, &time_minor_scan_pinned);
2449         mono_counters_register ("Minor scan registered roots", MONO_COUNTER_GC | MONO_COUNTER_LONG, &time_minor_scan_registered_roots);
2450         mono_counters_register ("Minor scan thread data", MONO_COUNTER_GC | MONO_COUNTER_LONG, &time_minor_scan_thread_data);
2451         mono_counters_register ("Minor finish gray stack", MONO_COUNTER_GC | MONO_COUNTER_LONG, &time_minor_finish_gray_stack);
2452         mono_counters_register ("Minor fragment creation", MONO_COUNTER_GC | MONO_COUNTER_LONG, &time_minor_fragment_creation);
2453
2454         mono_counters_register ("Major fragment clear", MONO_COUNTER_GC | MONO_COUNTER_LONG, &time_major_pre_collection_fragment_clear);
2455         mono_counters_register ("Major pinning", MONO_COUNTER_GC | MONO_COUNTER_LONG, &time_major_pinning);
2456         mono_counters_register ("Major scan pinned", MONO_COUNTER_GC | MONO_COUNTER_LONG, &time_major_scan_pinned);
2457         mono_counters_register ("Major scan registered roots", MONO_COUNTER_GC | MONO_COUNTER_LONG, &time_major_scan_registered_roots);
2458         mono_counters_register ("Major scan thread data", MONO_COUNTER_GC | MONO_COUNTER_LONG, &time_major_scan_thread_data);
2459         mono_counters_register ("Major scan alloc_pinned", MONO_COUNTER_GC | MONO_COUNTER_LONG, &time_major_scan_alloc_pinned);
2460         mono_counters_register ("Major scan finalized", MONO_COUNTER_GC | MONO_COUNTER_LONG, &time_major_scan_finalized);
2461         mono_counters_register ("Major scan big objects", MONO_COUNTER_GC | MONO_COUNTER_LONG, &time_major_scan_big_objects);
2462         mono_counters_register ("Major finish gray stack", MONO_COUNTER_GC | MONO_COUNTER_LONG, &time_major_finish_gray_stack);
2463         mono_counters_register ("Major free big objects", MONO_COUNTER_GC | MONO_COUNTER_LONG, &time_major_free_bigobjs);
2464         mono_counters_register ("Major LOS sweep", MONO_COUNTER_GC | MONO_COUNTER_LONG, &time_major_los_sweep);
2465         mono_counters_register ("Major sweep", MONO_COUNTER_GC | MONO_COUNTER_LONG, &time_major_sweep);
2466         mono_counters_register ("Major fragment creation", MONO_COUNTER_GC | MONO_COUNTER_LONG, &time_major_fragment_creation);
2467
2468 #ifdef HEAVY_STATISTICS
2469         mono_counters_register ("WBarrier set field", MONO_COUNTER_GC | MONO_COUNTER_INT, &stat_wbarrier_set_field);
2470         mono_counters_register ("WBarrier set arrayref", MONO_COUNTER_GC | MONO_COUNTER_INT, &stat_wbarrier_set_arrayref);
2471         mono_counters_register ("WBarrier arrayref copy", MONO_COUNTER_GC | MONO_COUNTER_INT, &stat_wbarrier_arrayref_copy);
2472         mono_counters_register ("WBarrier generic store called", MONO_COUNTER_GC | MONO_COUNTER_INT, &stat_wbarrier_generic_store);
2473         mono_counters_register ("WBarrier generic store stored", MONO_COUNTER_GC | MONO_COUNTER_INT, &stat_wbarrier_generic_store_remset);
2474         mono_counters_register ("WBarrier set root", MONO_COUNTER_GC | MONO_COUNTER_INT, &stat_wbarrier_set_root);
2475         mono_counters_register ("WBarrier value copy", MONO_COUNTER_GC | MONO_COUNTER_INT, &stat_wbarrier_value_copy);
2476         mono_counters_register ("WBarrier object copy", MONO_COUNTER_GC | MONO_COUNTER_INT, &stat_wbarrier_object_copy);
2477
2478         mono_counters_register ("# objects allocated", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_objects_alloced);
2479         mono_counters_register ("bytes allocated", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_bytes_alloced);
2480         mono_counters_register ("# objects allocated degraded", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_objects_alloced_degraded);
2481         mono_counters_register ("bytes allocated degraded", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_bytes_alloced_degraded);
2482         mono_counters_register ("bytes allocated in LOS", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_bytes_alloced_los);
2483
2484         mono_counters_register ("# copy_object() called (nursery)", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_copy_object_called_nursery);
2485         mono_counters_register ("# objects copied (nursery)", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_objects_copied_nursery);
2486         mono_counters_register ("# copy_object() called (major)", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_copy_object_called_major);
2487         mono_counters_register ("# objects copied (major)", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_objects_copied_major);
2488
2489         mono_counters_register ("# scan_object() called (nursery)", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_scan_object_called_nursery);
2490         mono_counters_register ("# scan_object() called (major)", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_scan_object_called_major);
2491
2492         mono_counters_register ("# nursery copy_object() failed from space", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_nursery_copy_object_failed_from_space);
2493         mono_counters_register ("# nursery copy_object() failed forwarded", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_nursery_copy_object_failed_forwarded);
2494         mono_counters_register ("# nursery copy_object() failed pinned", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_nursery_copy_object_failed_pinned);
2495
2496         mono_counters_register ("# wasted fragments used", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_wasted_fragments_used);
2497         mono_counters_register ("bytes in wasted fragments", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_wasted_fragments_bytes);
2498
2499         mono_counters_register ("Store remsets", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_store_remsets);
2500         mono_counters_register ("Unique store remsets", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_store_remsets_unique);
2501         mono_counters_register ("Saved remsets 1", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_saved_remsets_1);
2502         mono_counters_register ("Saved remsets 2", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_saved_remsets_2);
2503         mono_counters_register ("Global remsets added", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_global_remsets_added);
2504         mono_counters_register ("Global remsets re-added", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_global_remsets_readded);
2505         mono_counters_register ("Global remsets processed", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_global_remsets_processed);
2506         mono_counters_register ("Global remsets discarded", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_global_remsets_discarded);
2507 #endif
2508
2509         inited = TRUE;
2510 }
2511
2512 static gboolean
2513 need_major_collection (void)
2514 {
2515         mword los_alloced = los_memory_usage - MIN (last_los_memory_usage, los_memory_usage);
2516         return minor_collection_sections_alloced * major.section_size + los_alloced > minor_collection_allowance;
2517 }
2518
2519 /*
2520  * Collect objects in the nursery.  Returns whether to trigger a major
2521  * collection.
2522  */
2523 static gboolean
2524 collect_nursery (size_t requested_size)
2525 {
2526         size_t max_garbage_amount;
2527         char *orig_nursery_next;
2528         TV_DECLARE (all_atv);
2529         TV_DECLARE (all_btv);
2530         TV_DECLARE (atv);
2531         TV_DECLARE (btv);
2532
2533         current_collection_generation = GENERATION_NURSERY;
2534
2535         binary_protocol_collection (GENERATION_NURSERY);
2536         check_scan_starts ();
2537
2538         degraded_mode = 0;
2539         orig_nursery_next = nursery_next;
2540         nursery_next = MAX (nursery_next, nursery_last_pinned_end);
2541         /* FIXME: optimize later to use the higher address where an object can be present */
2542         nursery_next = MAX (nursery_next, nursery_real_end);
2543
2544         DEBUG (1, fprintf (gc_debug_file, "Start nursery collection %d %p-%p, size: %d\n", num_minor_gcs, nursery_start, nursery_next, (int)(nursery_next - nursery_start)));
2545         max_garbage_amount = nursery_next - nursery_start;
2546         g_assert (nursery_section->size >= max_garbage_amount);
2547
2548         /* world must be stopped already */
2549         TV_GETTIME (all_atv);
2550         TV_GETTIME (atv);
2551
2552         /* Pinning depends on this */
2553         clear_nursery_fragments (orig_nursery_next);
2554
2555         TV_GETTIME (btv);
2556         time_minor_pre_collection_fragment_clear += TV_ELAPSED_MS (atv, btv);
2557
2558         if (xdomain_checks)
2559                 check_for_xdomain_refs ();
2560
2561         nursery_section->next_data = nursery_next;
2562
2563         major.start_nursery_collection ();
2564
2565         gray_object_queue_init (&gray_queue);
2566
2567         num_minor_gcs++;
2568         mono_stats.minor_gc_count ++;
2569
2570         global_remset_cache_clear ();
2571
2572         /* pin from pinned handles */
2573         init_pinning ();
2574         pin_from_roots (nursery_start, nursery_next);
2575         /* identify pinned objects */
2576         optimize_pin_queue (0);
2577         next_pin_slot = pin_objects_from_addresses (nursery_section, pin_queue, pin_queue + next_pin_slot, nursery_start, nursery_next, &gray_queue);
2578         nursery_section->pin_queue_start = pin_queue;
2579         nursery_section->pin_queue_num_entries = next_pin_slot;
2580         TV_GETTIME (atv);
2581         time_minor_pinning += TV_ELAPSED_MS (btv, atv);
2582         DEBUG (2, fprintf (gc_debug_file, "Finding pinned pointers: %d in %d usecs\n", next_pin_slot, TV_ELAPSED (btv, atv)));
2583         DEBUG (4, fprintf (gc_debug_file, "Start scan with %d pinned objects\n", next_pin_slot));
2584
2585         if (consistency_check_at_minor_collection)
2586                 check_consistency ();
2587
2588         /* 
2589          * walk all the roots and copy the young objects to the old generation,
2590          * starting from to_space
2591          */
2592
2593         scan_from_remsets (nursery_start, nursery_next, &gray_queue);
2594         /* we don't have complete write barrier yet, so we scan all the old generation sections */
2595         TV_GETTIME (btv);
2596         time_minor_scan_remsets += TV_ELAPSED_MS (atv, btv);
2597         DEBUG (2, fprintf (gc_debug_file, "Old generation scan: %d usecs\n", TV_ELAPSED (atv, btv)));
2598
2599         drain_gray_stack (&gray_queue);
2600
2601         TV_GETTIME (atv);
2602         time_minor_scan_pinned += TV_ELAPSED_MS (btv, atv);
2603         /* registered roots, this includes static fields */
2604         scan_from_registered_roots (major.copy_object, nursery_start, nursery_next, ROOT_TYPE_NORMAL, &gray_queue);
2605         scan_from_registered_roots (major.copy_object, nursery_start, nursery_next, ROOT_TYPE_WBARRIER, &gray_queue);
2606         TV_GETTIME (btv);
2607         time_minor_scan_registered_roots += TV_ELAPSED_MS (atv, btv);
2608         /* thread data */
2609         scan_thread_data (nursery_start, nursery_next, TRUE);
2610         TV_GETTIME (atv);
2611         time_minor_scan_thread_data += TV_ELAPSED_MS (btv, atv);
2612         btv = atv;
2613
2614         finish_gray_stack (nursery_start, nursery_next, GENERATION_NURSERY, &gray_queue);
2615         TV_GETTIME (atv);
2616         time_minor_finish_gray_stack += TV_ELAPSED_MS (btv, atv);
2617
2618         /* walk the pin_queue, build up the fragment list of free memory, unmark
2619          * pinned objects as we go, memzero() the empty fragments so they are ready for the
2620          * next allocations.
2621          */
2622         build_nursery_fragments (pin_queue, next_pin_slot);
2623         TV_GETTIME (btv);
2624         time_minor_fragment_creation += TV_ELAPSED_MS (atv, btv);
2625         DEBUG (2, fprintf (gc_debug_file, "Fragment creation: %d usecs, %lu bytes available\n", TV_ELAPSED (atv, btv), (unsigned long)fragment_total));
2626
2627         if (consistency_check_at_minor_collection)
2628                 check_major_refs ();
2629
2630         major.finish_nursery_collection ();
2631
2632         TV_GETTIME (all_btv);
2633         mono_stats.minor_gc_time_usecs += TV_ELAPSED (all_atv, all_btv);
2634
2635         if (heap_dump_file)
2636                 dump_heap ("minor", num_minor_gcs - 1, NULL);
2637
2638         /* prepare the pin queue for the next collection */
2639         last_num_pinned = next_pin_slot;
2640         next_pin_slot = 0;
2641         if (fin_ready_list || critical_fin_list) {
2642                 DEBUG (4, fprintf (gc_debug_file, "Finalizer-thread wakeup: ready %d\n", num_ready_finalizers));
2643                 mono_gc_finalize_notify ();
2644         }
2645         pin_stats_reset ();
2646
2647         g_assert (gray_object_queue_is_empty (&gray_queue));
2648
2649         check_scan_starts ();
2650
2651         binary_protocol_flush_buffers ();
2652
2653         current_collection_generation = -1;
2654
2655         return need_major_collection ();
2656 }
2657
2658 static void
2659 major_do_collection (const char *reason)
2660 {
2661         LOSObject *bigobj, *prevbo;
2662         TV_DECLARE (all_atv);
2663         TV_DECLARE (all_btv);
2664         TV_DECLARE (atv);
2665         TV_DECLARE (btv);
2666         /* FIXME: only use these values for the precise scan
2667          * note that to_space pointers should be excluded anyway...
2668          */
2669         char *heap_start = NULL;
2670         char *heap_end = (char*)-1;
2671         int old_num_major_sections = major.get_num_major_sections ();
2672         int num_major_sections, num_major_sections_saved, save_target, allowance_target;
2673         mword los_memory_saved, los_memory_alloced, old_los_memory_usage;
2674
2675         /*
2676          * A domain could have been freed, resulting in
2677          * los_memory_usage being less than last_los_memory_usage.
2678          */
2679         los_memory_alloced = los_memory_usage - MIN (last_los_memory_usage, los_memory_usage);
2680         old_los_memory_usage = los_memory_usage;
2681
2682         //count_ref_nonref_objs ();
2683         //consistency_check ();
2684
2685         binary_protocol_collection (GENERATION_OLD);
2686         check_scan_starts ();
2687         gray_object_queue_init (&gray_queue);
2688
2689         degraded_mode = 0;
2690         DEBUG (1, fprintf (gc_debug_file, "Start major collection %d\n", num_major_gcs));
2691         num_major_gcs++;
2692         mono_stats.major_gc_count ++;
2693
2694         /* world must be stopped already */
2695         TV_GETTIME (all_atv);
2696         TV_GETTIME (atv);
2697
2698         /* Pinning depends on this */
2699         clear_nursery_fragments (nursery_next);
2700
2701         TV_GETTIME (btv);
2702         time_major_pre_collection_fragment_clear += TV_ELAPSED_MS (atv, btv);
2703
2704         if (xdomain_checks)
2705                 check_for_xdomain_refs ();
2706
2707         nursery_section->next_data = nursery_real_end;
2708         /* we should also coalesce scanning from sections close to each other
2709          * and deal with pointers outside of the sections later.
2710          */
2711         /* The remsets are not useful for a major collection */
2712         clear_remsets ();
2713         global_remset_cache_clear ();
2714
2715         TV_GETTIME (atv);
2716         init_pinning ();
2717         DEBUG (6, fprintf (gc_debug_file, "Collecting pinned addresses\n"));
2718         pin_from_roots ((void*)lowest_heap_address, (void*)highest_heap_address);
2719         optimize_pin_queue (0);
2720
2721         /*
2722          * pin_queue now contains all candidate pointers, sorted and
2723          * uniqued.  We must do two passes now to figure out which
2724          * objects are pinned.
2725          *
2726          * The first is to find within the pin_queue the area for each
2727          * section.  This requires that the pin_queue be sorted.  We
2728          * also process the LOS objects and pinned chunks here.
2729          *
2730          * The second, destructive, pass is to reduce the section
2731          * areas to pointers to the actually pinned objects.
2732          */
2733         DEBUG (6, fprintf (gc_debug_file, "Pinning from sections\n"));
2734         /* first pass for the sections */
2735         mono_sgen_find_section_pin_queue_start_end (nursery_section);
2736         major.find_pin_queue_start_ends (&gray_queue);
2737         /* identify possible pointers to the insize of large objects */
2738         DEBUG (6, fprintf (gc_debug_file, "Pinning from large objects\n"));
2739         for (bigobj = los_object_list; bigobj; bigobj = bigobj->next) {
2740                 int dummy;
2741                 if (mono_sgen_find_optimized_pin_queue_area (bigobj->data, (char*)bigobj->data + bigobj->size, &dummy)) {
2742                         pin_object (bigobj->data);
2743                         /* FIXME: only enqueue if object has references */
2744                         GRAY_OBJECT_ENQUEUE (&gray_queue, bigobj->data);
2745                         if (heap_dump_file)
2746                                 mono_sgen_pin_stats_register_object ((char*) bigobj->data, safe_object_get_size ((MonoObject*) bigobj->data));
2747                         DEBUG (6, fprintf (gc_debug_file, "Marked large object %p (%s) size: %lu from roots\n", bigobj->data, safe_name (bigobj->data), (unsigned long)bigobj->size));
2748                 }
2749         }
2750         /* second pass for the sections */
2751         mono_sgen_pin_objects_in_section (nursery_section, &gray_queue);
2752         major.pin_objects (&gray_queue);
2753
2754         TV_GETTIME (btv);
2755         time_major_pinning += TV_ELAPSED_MS (atv, btv);
2756         DEBUG (2, fprintf (gc_debug_file, "Finding pinned pointers: %d in %d usecs\n", next_pin_slot, TV_ELAPSED (atv, btv)));
2757         DEBUG (4, fprintf (gc_debug_file, "Start scan with %d pinned objects\n", next_pin_slot));
2758
2759         major.init_to_space ();
2760
2761         drain_gray_stack (&gray_queue);
2762
2763         TV_GETTIME (atv);
2764         time_major_scan_pinned += TV_ELAPSED_MS (btv, atv);
2765
2766         /* registered roots, this includes static fields */
2767         scan_from_registered_roots (major.copy_or_mark_object, heap_start, heap_end, ROOT_TYPE_NORMAL, &gray_queue);
2768         scan_from_registered_roots (major.copy_or_mark_object, heap_start, heap_end, ROOT_TYPE_WBARRIER, &gray_queue);
2769         TV_GETTIME (btv);
2770         time_major_scan_registered_roots += TV_ELAPSED_MS (atv, btv);
2771
2772         /* Threads */
2773         /* FIXME: This is the wrong place for this, because it does
2774            pinning */
2775         scan_thread_data (heap_start, heap_end, TRUE);
2776         TV_GETTIME (atv);
2777         time_major_scan_thread_data += TV_ELAPSED_MS (btv, atv);
2778
2779         TV_GETTIME (btv);
2780         time_major_scan_alloc_pinned += TV_ELAPSED_MS (atv, btv);
2781
2782         /* scan the list of objects ready for finalization */
2783         scan_finalizer_entries (major.copy_or_mark_object, fin_ready_list, &gray_queue);
2784         scan_finalizer_entries (major.copy_or_mark_object, critical_fin_list, &gray_queue);
2785         TV_GETTIME (atv);
2786         time_major_scan_finalized += TV_ELAPSED_MS (btv, atv);
2787         DEBUG (2, fprintf (gc_debug_file, "Root scan: %d usecs\n", TV_ELAPSED (btv, atv)));
2788
2789         TV_GETTIME (btv);
2790         time_major_scan_big_objects += TV_ELAPSED_MS (atv, btv);
2791
2792         /* all the objects in the heap */
2793         finish_gray_stack (heap_start, heap_end, GENERATION_OLD, &gray_queue);
2794         TV_GETTIME (atv);
2795         time_major_finish_gray_stack += TV_ELAPSED_MS (btv, atv);
2796
2797         /* sweep the big objects list */
2798         prevbo = NULL;
2799         for (bigobj = los_object_list; bigobj;) {
2800                 if (object_is_pinned (bigobj->data)) {
2801                         unpin_object (bigobj->data);
2802                 } else {
2803                         LOSObject *to_free;
2804                         /* not referenced anywhere, so we can free it */
2805                         if (prevbo)
2806                                 prevbo->next = bigobj->next;
2807                         else
2808                                 los_object_list = bigobj->next;
2809                         to_free = bigobj;
2810                         bigobj = bigobj->next;
2811                         free_large_object (to_free);
2812                         continue;
2813                 }
2814                 prevbo = bigobj;
2815                 bigobj = bigobj->next;
2816         }
2817
2818         TV_GETTIME (btv);
2819         time_major_free_bigobjs += TV_ELAPSED_MS (atv, btv);
2820
2821         los_sweep ();
2822
2823         TV_GETTIME (atv);
2824         time_major_los_sweep += TV_ELAPSED_MS (btv, atv);
2825
2826         major.sweep ();
2827
2828         TV_GETTIME (btv);
2829         time_major_sweep += TV_ELAPSED_MS (atv, btv);
2830
2831         /* walk the pin_queue, build up the fragment list of free memory, unmark
2832          * pinned objects as we go, memzero() the empty fragments so they are ready for the
2833          * next allocations.
2834          */
2835         build_nursery_fragments (nursery_section->pin_queue_start, nursery_section->pin_queue_num_entries);
2836
2837         TV_GETTIME (atv);
2838         time_major_fragment_creation += TV_ELAPSED_MS (btv, atv);
2839
2840         TV_GETTIME (all_btv);
2841         mono_stats.major_gc_time_usecs += TV_ELAPSED (all_atv, all_btv);
2842
2843         if (heap_dump_file)
2844                 dump_heap ("major", num_major_gcs - 1, reason);
2845
2846         /* prepare the pin queue for the next collection */
2847         next_pin_slot = 0;
2848         if (fin_ready_list || critical_fin_list) {
2849                 DEBUG (4, fprintf (gc_debug_file, "Finalizer-thread wakeup: ready %d\n", num_ready_finalizers));
2850                 mono_gc_finalize_notify ();
2851         }
2852         pin_stats_reset ();
2853
2854         g_assert (gray_object_queue_is_empty (&gray_queue));
2855
2856         num_major_sections = major.get_num_major_sections ();
2857
2858         num_major_sections_saved = MAX (old_num_major_sections - num_major_sections, 0);
2859         los_memory_saved = MAX (old_los_memory_usage - los_memory_usage, 1);
2860
2861         save_target = ((num_major_sections * major.section_size) + los_memory_saved) / 2;
2862         /*
2863          * We aim to allow the allocation of as many sections as is
2864          * necessary to reclaim save_target sections in the next
2865          * collection.  We assume the collection pattern won't change.
2866          * In the last cycle, we had num_major_sections_saved for
2867          * minor_collection_sections_alloced.  Assuming things won't
2868          * change, this must be the same ratio as save_target for
2869          * allowance_target, i.e.
2870          *
2871          *    num_major_sections_saved            save_target
2872          * --------------------------------- == ----------------
2873          * minor_collection_sections_alloced    allowance_target
2874          *
2875          * hence:
2876          */
2877         allowance_target = (mword)((double)save_target * (double)(minor_collection_sections_alloced * major.section_size + los_memory_alloced) / (double)(num_major_sections_saved * major.section_size + los_memory_saved));
2878
2879         minor_collection_allowance = MAX (MIN (allowance_target, num_major_sections * major.section_size + los_memory_usage), MIN_MINOR_COLLECTION_ALLOWANCE);
2880
2881         minor_collection_sections_alloced = 0;
2882         last_los_memory_usage = los_memory_usage;
2883
2884         major.finish_major_collection ();
2885
2886         check_scan_starts ();
2887
2888         binary_protocol_flush_buffers ();
2889
2890         //consistency_check ();
2891 }
2892
2893 static void
2894 major_collection (const char *reason)
2895 {
2896         if (g_getenv ("MONO_GC_NO_MAJOR")) {
2897                 collect_nursery (0);
2898                 return;
2899         }
2900
2901         current_collection_generation = GENERATION_OLD;
2902         major_do_collection (reason);
2903         current_collection_generation = -1;
2904 }
2905
2906 /*
2907  * When deciding if it's better to collect or to expand, keep track
2908  * of how much garbage was reclaimed with the last collection: if it's too
2909  * little, expand.
2910  * This is called when we could not allocate a small object.
2911  */
2912 static void __attribute__((noinline))
2913 minor_collect_or_expand_inner (size_t size)
2914 {
2915         int do_minor_collection = 1;
2916
2917         g_assert (nursery_section);
2918         if (do_minor_collection) {
2919                 stop_world ();
2920                 if (collect_nursery (size))
2921                         major_collection ("minor overflow");
2922                 DEBUG (2, fprintf (gc_debug_file, "Heap size: %lu, LOS size: %lu\n", (unsigned long)total_alloc, (unsigned long)los_memory_usage));
2923                 restart_world ();
2924                 /* this also sets the proper pointers for the next allocation */
2925                 if (!search_fragment_for_size (size)) {
2926                         int i;
2927                         /* TypeBuilder and MonoMethod are killing mcs with fragmentation */
2928                         DEBUG (1, fprintf (gc_debug_file, "nursery collection didn't find enough room for %zd alloc (%d pinned)\n", size, last_num_pinned));
2929                         for (i = 0; i < last_num_pinned; ++i) {
2930                                 DEBUG (3, fprintf (gc_debug_file, "Bastard pinning obj %p (%s), size: %d\n", pin_queue [i], safe_name (pin_queue [i]), safe_object_get_size (pin_queue [i])));
2931                         }
2932                         degraded_mode = 1;
2933                 }
2934         }
2935         //report_internal_mem_usage ();
2936 }
2937
2938 /*
2939  * ######################################################################
2940  * ########  Memory allocation from the OS
2941  * ######################################################################
2942  * This section of code deals with getting memory from the OS and
2943  * allocating memory for GC-internal data structures.
2944  * Internal memory can be handled with a freelist for small objects.
2945  */
2946
2947 /*
2948  * Debug reporting.
2949  */
2950 G_GNUC_UNUSED static void
2951 report_internal_mem_usage (void)
2952 {
2953         printf ("Internal memory usage:\n");
2954         mono_sgen_report_internal_mem_usage ();
2955         printf ("Pinned memory usage:\n");
2956         major.report_pinned_memory_usage ();
2957 }
2958
2959 /*
2960  * Allocate a big chunk of memory from the OS (usually 64KB to several megabytes).
2961  * This must not require any lock.
2962  */
2963 void*
2964 mono_sgen_alloc_os_memory (size_t size, int activate)
2965 {
2966         void *ptr;
2967         unsigned long prot_flags = activate? MONO_MMAP_READ|MONO_MMAP_WRITE: MONO_MMAP_NONE;
2968
2969         prot_flags |= MONO_MMAP_PRIVATE | MONO_MMAP_ANON;
2970         size += pagesize - 1;
2971         size &= ~(pagesize - 1);
2972         ptr = mono_valloc (0, size, prot_flags);
2973         /* FIXME: CAS */
2974         total_alloc += size;
2975         return ptr;
2976 }
2977
2978 /*
2979  * Free the memory returned by mono_sgen_alloc_os_memory (), returning it to the OS.
2980  */
2981 void
2982 mono_sgen_free_os_memory (void *addr, size_t size)
2983 {
2984         mono_vfree (addr, size);
2985
2986         size += pagesize - 1;
2987         size &= ~(pagesize - 1);
2988         /* FIXME: CAS */
2989         total_alloc -= size;
2990 }
2991
2992 /*
2993  * ######################################################################
2994  * ########  Object allocation
2995  * ######################################################################
2996  * This section of code deals with allocating memory for objects.
2997  * There are several ways:
2998  * *) allocate large objects
2999  * *) allocate normal objects
3000  * *) fast lock-free allocation
3001  * *) allocation of pinned objects
3002  */
3003
3004 static void
3005 setup_fragment (Fragment *frag, Fragment *prev, size_t size)
3006 {
3007         /* remove from the list */
3008         if (prev)
3009                 prev->next = frag->next;
3010         else
3011                 nursery_fragments = frag->next;
3012         nursery_next = frag->fragment_start;
3013         nursery_frag_real_end = frag->fragment_end;
3014
3015         DEBUG (4, fprintf (gc_debug_file, "Using nursery fragment %p-%p, size: %td (req: %zd)\n", nursery_next, nursery_frag_real_end, nursery_frag_real_end - nursery_next, size));
3016         frag->next = fragment_freelist;
3017         fragment_freelist = frag;
3018 }
3019
3020 /* check if we have a suitable fragment in nursery_fragments to be able to allocate
3021  * an object of size @size
3022  * Return FALSE if not found (which means we need a collection)
3023  */
3024 static gboolean
3025 search_fragment_for_size (size_t size)
3026 {
3027         Fragment *frag, *prev;
3028         DEBUG (4, fprintf (gc_debug_file, "Searching nursery fragment %p, size: %zd\n", nursery_frag_real_end, size));
3029
3030         if (nursery_frag_real_end > nursery_next && nursery_clear_policy == CLEAR_AT_TLAB_CREATION)
3031                 /* Clear the remaining space, pinning depends on this */
3032                 memset (nursery_next, 0, nursery_frag_real_end - nursery_next);
3033
3034         prev = NULL;
3035         for (frag = nursery_fragments; frag; frag = frag->next) {
3036                 if (size <= (frag->fragment_end - frag->fragment_start)) {
3037                         setup_fragment (frag, prev, size);
3038                         return TRUE;
3039                 }
3040                 prev = frag;
3041         }
3042         return FALSE;
3043 }
3044
3045 /*
3046  * Same as search_fragment_for_size but if search for @desired_size fails, try to satisfy @minimum_size.
3047  * This improves nursery usage.
3048  */
3049 static int
3050 search_fragment_for_size_range (size_t desired_size, size_t minimum_size)
3051 {
3052         Fragment *frag, *prev, *min_prev;
3053         DEBUG (4, fprintf (gc_debug_file, "Searching nursery fragment %p, desired size: %zd minimum size %zd\n", nursery_frag_real_end, desired_size, minimum_size));
3054
3055         if (nursery_frag_real_end > nursery_next && nursery_clear_policy == CLEAR_AT_TLAB_CREATION)
3056                 /* Clear the remaining space, pinning depends on this */
3057                 memset (nursery_next, 0, nursery_frag_real_end - nursery_next);
3058
3059         min_prev = GINT_TO_POINTER (-1);
3060         prev = NULL;
3061
3062         for (frag = nursery_fragments; frag; frag = frag->next) {
3063                 int frag_size = frag->fragment_end - frag->fragment_start;
3064                 if (desired_size <= frag_size) {
3065                         setup_fragment (frag, prev, desired_size);
3066                         return desired_size;
3067                 }
3068                 if (minimum_size <= frag_size)
3069                         min_prev = prev;
3070
3071                 prev = frag;
3072         }
3073
3074         if (min_prev != GINT_TO_POINTER (-1)) {
3075                 int frag_size;
3076                 if (min_prev)
3077                         frag = min_prev->next;
3078                 else
3079                         frag = nursery_fragments;
3080
3081                 frag_size = frag->fragment_end - frag->fragment_start;
3082                 HEAVY_STAT (++stat_wasted_fragments_used);
3083                 HEAVY_STAT (stat_wasted_fragments_bytes += frag_size);
3084
3085                 setup_fragment (frag, min_prev, minimum_size);
3086                 return frag_size;
3087         }
3088
3089         return 0;
3090 }
3091
3092 static void*
3093 alloc_degraded (MonoVTable *vtable, size_t size)
3094 {
3095         if (need_major_collection ()) {
3096                 stop_world ();
3097                 major_collection ("degraded overflow");
3098                 restart_world ();
3099         }
3100
3101         degraded_mode += size;
3102         return major.alloc_degraded (vtable, size);
3103 }
3104
3105 /*
3106  * Provide a variant that takes just the vtable for small fixed-size objects.
3107  * The aligned size is already computed and stored in vt->gc_descr.
3108  * Note: every SCAN_START_SIZE or so we are given the chance to do some special
3109  * processing. We can keep track of where objects start, for example,
3110  * so when we scan the thread stacks for pinned objects, we can start
3111  * a search for the pinned object in SCAN_START_SIZE chunks.
3112  */
3113 static void*
3114 mono_gc_alloc_obj_nolock (MonoVTable *vtable, size_t size)
3115 {
3116         /* FIXME: handle OOM */
3117         void **p;
3118         char *new_next;
3119         TLAB_ACCESS_INIT;
3120
3121         HEAVY_STAT (++stat_objects_alloced);
3122         if (size <= MAX_SMALL_OBJ_SIZE)
3123                 HEAVY_STAT (stat_bytes_alloced += size);
3124         else
3125                 HEAVY_STAT (stat_bytes_alloced_los += size);
3126
3127         size = ALIGN_UP (size);
3128
3129         g_assert (vtable->gc_descr);
3130
3131         if (G_UNLIKELY (collect_before_allocs)) {
3132                 if (nursery_section) {
3133                         stop_world ();
3134                         collect_nursery (0);
3135                         restart_world ();
3136                         if (!degraded_mode && !search_fragment_for_size (size)) {
3137                                 // FIXME:
3138                                 g_assert_not_reached ();
3139                         }
3140                 }
3141         }
3142
3143         /*
3144          * We must already have the lock here instead of after the
3145          * fast path because we might be interrupted in the fast path
3146          * (after confirming that new_next < TLAB_TEMP_END) by the GC,
3147          * and we'll end up allocating an object in a fragment which
3148          * no longer belongs to us.
3149          *
3150          * The managed allocator does not do this, but it's treated
3151          * specially by the world-stopping code.
3152          */
3153
3154         if (size > MAX_SMALL_OBJ_SIZE) {
3155                 p = alloc_large_inner (vtable, size);
3156         } else {
3157                 /* tlab_next and tlab_temp_end are TLS vars so accessing them might be expensive */
3158
3159                 p = (void**)TLAB_NEXT;
3160                 /* FIXME: handle overflow */
3161                 new_next = (char*)p + size;
3162                 TLAB_NEXT = new_next;
3163
3164                 if (G_LIKELY (new_next < TLAB_TEMP_END)) {
3165                         /* Fast path */
3166
3167                         /* 
3168                          * FIXME: We might need a memory barrier here so the change to tlab_next is 
3169                          * visible before the vtable store.
3170                          */
3171
3172                         DEBUG (6, fprintf (gc_debug_file, "Allocated object %p, vtable: %p (%s), size: %zd\n", p, vtable, vtable->klass->name, size));
3173                         binary_protocol_alloc (p , vtable, size);
3174                         g_assert (*p == NULL);
3175                         *p = vtable;
3176
3177                         g_assert (TLAB_NEXT == new_next);
3178
3179                         return p;
3180                 }
3181
3182                 /* Slow path */
3183
3184                 /* there are two cases: the object is too big or we run out of space in the TLAB */
3185                 /* we also reach here when the thread does its first allocation after a minor 
3186                  * collection, since the tlab_ variables are initialized to NULL.
3187                  * there can be another case (from ORP), if we cooperate with the runtime a bit:
3188                  * objects that need finalizers can have the high bit set in their size
3189                  * so the above check fails and we can readily add the object to the queue.
3190                  * This avoids taking again the GC lock when registering, but this is moot when
3191                  * doing thread-local allocation, so it may not be a good idea.
3192                  */
3193                 g_assert (TLAB_NEXT == new_next);
3194                 if (TLAB_NEXT >= TLAB_REAL_END) {
3195                         /* 
3196                          * Run out of space in the TLAB. When this happens, some amount of space
3197                          * remains in the TLAB, but not enough to satisfy the current allocation
3198                          * request. Currently, we retire the TLAB in all cases, later we could
3199                          * keep it if the remaining space is above a treshold, and satisfy the
3200                          * allocation directly from the nursery.
3201                          */
3202                         TLAB_NEXT -= size;
3203                         /* when running in degraded mode, we continue allocing that way
3204                          * for a while, to decrease the number of useless nursery collections.
3205                          */
3206                         if (degraded_mode && degraded_mode < DEFAULT_NURSERY_SIZE) {
3207                                 p = alloc_degraded (vtable, size);
3208                                 binary_protocol_alloc_degraded (p, vtable, size);
3209                                 return p;
3210                         }
3211
3212                         /*FIXME This codepath is current deadcode since tlab_size > MAX_SMALL_OBJ_SIZE*/
3213                         if (size > tlab_size) {
3214                                 /* Allocate directly from the nursery */
3215                                 if (nursery_next + size >= nursery_frag_real_end) {
3216                                         if (!search_fragment_for_size (size)) {
3217                                                 minor_collect_or_expand_inner (size);
3218                                                 if (degraded_mode) {
3219                                                         p = alloc_degraded (vtable, size);
3220                                                         binary_protocol_alloc_degraded (p, vtable, size);
3221                                                         return p;
3222                                                 }
3223                                         }
3224                                 }
3225
3226                                 p = (void*)nursery_next;
3227                                 nursery_next += size;
3228                                 if (nursery_next > nursery_frag_real_end) {
3229                                         // no space left
3230                                         g_assert (0);
3231                                 }
3232
3233                                 if (nursery_clear_policy == CLEAR_AT_TLAB_CREATION)
3234                                         memset (p, 0, size);
3235                         } else {
3236                                 int alloc_size = tlab_size;
3237                                 int available_in_nursery = nursery_frag_real_end - nursery_next;
3238                                 if (TLAB_START)
3239                                         DEBUG (3, fprintf (gc_debug_file, "Retire TLAB: %p-%p [%ld]\n", TLAB_START, TLAB_REAL_END, (long)(TLAB_REAL_END - TLAB_NEXT - size)));
3240
3241                                 if (alloc_size >= available_in_nursery) {
3242                                         if (available_in_nursery > MAX_NURSERY_TLAB_WASTE && available_in_nursery > size) {
3243                                                 alloc_size = available_in_nursery;
3244                                         } else {
3245                                                 alloc_size = search_fragment_for_size_range (tlab_size, size);
3246                                                 if (!alloc_size) {
3247                                                         alloc_size = tlab_size;
3248                                                         minor_collect_or_expand_inner (tlab_size);
3249                                                         if (degraded_mode) {
3250                                                                 p = alloc_degraded (vtable, size);
3251                                                                 binary_protocol_alloc_degraded (p, vtable, size);
3252                                                                 return p;
3253                                                         }
3254                                                 }
3255                                         }
3256                                 }
3257
3258                                 /* Allocate a new TLAB from the current nursery fragment */
3259                                 TLAB_START = nursery_next;
3260                                 nursery_next += alloc_size;
3261                                 TLAB_NEXT = TLAB_START;
3262                                 TLAB_REAL_END = TLAB_START + alloc_size;
3263                                 TLAB_TEMP_END = TLAB_START + MIN (SCAN_START_SIZE, alloc_size);
3264
3265                                 if (nursery_clear_policy == CLEAR_AT_TLAB_CREATION)
3266                                         memset (TLAB_START, 0, alloc_size);
3267
3268                                 /* Allocate from the TLAB */
3269                                 p = (void*)TLAB_NEXT;
3270                                 TLAB_NEXT += size;
3271                                 g_assert (TLAB_NEXT <= TLAB_REAL_END);
3272
3273                                 nursery_section->scan_starts [((char*)p - (char*)nursery_section->data)/SCAN_START_SIZE] = (char*)p;
3274                         }
3275                 } else {
3276                         /* Reached tlab_temp_end */
3277
3278                         /* record the scan start so we can find pinned objects more easily */
3279                         nursery_section->scan_starts [((char*)p - (char*)nursery_section->data)/SCAN_START_SIZE] = (char*)p;
3280                         /* we just bump tlab_temp_end as well */
3281                         TLAB_TEMP_END = MIN (TLAB_REAL_END, TLAB_NEXT + SCAN_START_SIZE);
3282                         DEBUG (5, fprintf (gc_debug_file, "Expanding local alloc: %p-%p\n", TLAB_NEXT, TLAB_TEMP_END));
3283                 }
3284         }
3285
3286         DEBUG (6, fprintf (gc_debug_file, "Allocated object %p, vtable: %p (%s), size: %zd\n", p, vtable, vtable->klass->name, size));
3287         binary_protocol_alloc (p, vtable, size);
3288         *p = vtable;
3289
3290         return p;
3291 }
3292
3293 static void*
3294 mono_gc_try_alloc_obj_nolock (MonoVTable *vtable, size_t size)
3295 {
3296         void **p;
3297         char *new_next;
3298         TLAB_ACCESS_INIT;
3299
3300         size = ALIGN_UP (size);
3301
3302         g_assert (vtable->gc_descr);
3303         if (size <= MAX_SMALL_OBJ_SIZE) {
3304                 /* tlab_next and tlab_temp_end are TLS vars so accessing them might be expensive */
3305
3306                 p = (void**)TLAB_NEXT;
3307                 /* FIXME: handle overflow */
3308                 new_next = (char*)p + size;
3309                 TLAB_NEXT = new_next;
3310
3311                 if (G_LIKELY (new_next < TLAB_TEMP_END)) {
3312                         /* Fast path */
3313
3314                         /* 
3315                          * FIXME: We might need a memory barrier here so the change to tlab_next is 
3316                          * visible before the vtable store.
3317                          */
3318
3319                         HEAVY_STAT (++stat_objects_alloced);
3320                         HEAVY_STAT (stat_bytes_alloced += size);
3321
3322                         DEBUG (6, fprintf (gc_debug_file, "Allocated object %p, vtable: %p (%s), size: %zd\n", p, vtable, vtable->klass->name, size));
3323                         binary_protocol_alloc (p, vtable, size);
3324                         g_assert (*p == NULL);
3325                         *p = vtable;
3326
3327                         g_assert (TLAB_NEXT == new_next);
3328
3329                         return p;
3330                 }
3331         }
3332         return NULL;
3333 }
3334
3335 void*
3336 mono_gc_alloc_obj (MonoVTable *vtable, size_t size)
3337 {
3338         void *res;
3339 #ifndef DISABLE_CRITICAL_REGION
3340         TLAB_ACCESS_INIT;
3341         ENTER_CRITICAL_REGION;
3342         res = mono_gc_try_alloc_obj_nolock (vtable, size);
3343         if (res) {
3344                 EXIT_CRITICAL_REGION;
3345                 return res;
3346         }
3347         EXIT_CRITICAL_REGION;
3348 #endif
3349         LOCK_GC;
3350         res = mono_gc_alloc_obj_nolock (vtable, size);
3351         UNLOCK_GC;
3352         return res;
3353 }
3354
3355 void*
3356 mono_gc_alloc_vector (MonoVTable *vtable, size_t size, uintptr_t max_length)
3357 {
3358         MonoArray *arr;
3359 #ifndef DISABLE_CRITICAL_REGION
3360         TLAB_ACCESS_INIT;
3361         ENTER_CRITICAL_REGION;
3362         arr = mono_gc_try_alloc_obj_nolock (vtable, size);
3363         if (arr) {
3364                 arr->max_length = max_length;
3365                 EXIT_CRITICAL_REGION;
3366                 return arr;
3367         }
3368         EXIT_CRITICAL_REGION;
3369 #endif
3370
3371         LOCK_GC;
3372
3373         arr = mono_gc_alloc_obj_nolock (vtable, size);
3374         arr->max_length = max_length;
3375
3376         UNLOCK_GC;
3377
3378         return arr;
3379 }
3380
3381 void*
3382 mono_gc_alloc_array (MonoVTable *vtable, size_t size, uintptr_t max_length, uintptr_t bounds_size)
3383 {
3384         MonoArray *arr;
3385         MonoArrayBounds *bounds;
3386
3387         LOCK_GC;
3388
3389         arr = mono_gc_alloc_obj_nolock (vtable, size);
3390         arr->max_length = max_length;
3391
3392         bounds = (MonoArrayBounds*)((char*)arr + size - bounds_size);
3393         arr->bounds = bounds;
3394
3395         UNLOCK_GC;
3396
3397         return arr;
3398 }
3399
3400 void*
3401 mono_gc_alloc_string (MonoVTable *vtable, size_t size, gint32 len)
3402 {
3403         MonoString *str;
3404 #ifndef DISABLE_CRITICAL_REGION
3405         TLAB_ACCESS_INIT;
3406         ENTER_CRITICAL_REGION;
3407         str = mono_gc_try_alloc_obj_nolock (vtable, size);
3408         if (str) {
3409                 str->length = len;
3410                 EXIT_CRITICAL_REGION;
3411                 return str;
3412         }
3413         EXIT_CRITICAL_REGION;
3414 #endif
3415
3416         LOCK_GC;
3417
3418         str = mono_gc_alloc_obj_nolock (vtable, size);
3419         str->length = len;
3420
3421         UNLOCK_GC;
3422
3423         return str;
3424 }
3425
3426 /*
3427  * To be used for interned strings and possibly MonoThread, reflection handles.
3428  * We may want to explicitly free these objects.
3429  */
3430 void*
3431 mono_gc_alloc_pinned_obj (MonoVTable *vtable, size_t size)
3432 {
3433         /* FIXME: handle OOM */
3434         void **p;
3435         size = ALIGN_UP (size);
3436         LOCK_GC;
3437         if (size > MAX_SMALL_OBJ_SIZE) {
3438                 /* large objects are always pinned anyway */
3439                 p = alloc_large_inner (vtable, size);
3440         } else {
3441                 DEBUG (9, g_assert (vtable->klass->inited));
3442                 p = major.alloc_small_pinned_obj (size, vtable->klass->has_references);
3443         }
3444         DEBUG (6, fprintf (gc_debug_file, "Allocated pinned object %p, vtable: %p (%s), size: %zd\n", p, vtable, vtable->klass->name, size));
3445         binary_protocol_alloc_pinned (p, vtable, size);
3446         *p = vtable;
3447         UNLOCK_GC;
3448         return p;
3449 }
3450
3451 /*
3452  * ######################################################################
3453  * ########  Finalization support
3454  * ######################################################################
3455  */
3456
3457 /*
3458  * this is valid for the nursery: if the object has been forwarded it means it's
3459  * still refrenced from a root. If it is pinned it's still alive as well.
3460  * Return TRUE if @obj is ready to be finalized.
3461  */
3462 #define object_is_fin_ready(obj) (!object_is_pinned (obj) && !object_is_forwarded (obj))
3463
3464 static gboolean
3465 is_critical_finalizer (FinalizeEntry *entry)
3466 {
3467         MonoObject *obj;
3468         MonoClass *class;
3469
3470         if (!mono_defaults.critical_finalizer_object)
3471                 return FALSE;
3472
3473         obj = entry->object;
3474         class = ((MonoVTable*)LOAD_VTABLE (obj))->klass;
3475
3476         return mono_class_has_parent (class, mono_defaults.critical_finalizer_object);
3477 }
3478
3479 static void
3480 queue_finalization_entry (FinalizeEntry *entry) {
3481         if (is_critical_finalizer (entry)) {
3482                 entry->next = critical_fin_list;
3483                 critical_fin_list = entry;
3484         } else {
3485                 entry->next = fin_ready_list;
3486                 fin_ready_list = entry;
3487         }
3488 }
3489
3490 /* LOCKING: requires that the GC lock is held */
3491 static void
3492 rehash_fin_table (FinalizeEntryHashTable *hash_table)
3493 {
3494         FinalizeEntry **finalizable_hash = hash_table->table;
3495         mword finalizable_hash_size = hash_table->size;
3496         int i;
3497         unsigned int hash;
3498         FinalizeEntry **new_hash;
3499         FinalizeEntry *entry, *next;
3500         int new_size = g_spaced_primes_closest (hash_table->num_registered);
3501
3502         new_hash = mono_sgen_alloc_internal_dynamic (new_size * sizeof (FinalizeEntry*), INTERNAL_MEM_FIN_TABLE);
3503         for (i = 0; i < finalizable_hash_size; ++i) {
3504                 for (entry = finalizable_hash [i]; entry; entry = next) {
3505                         hash = mono_object_hash (entry->object) % new_size;
3506                         next = entry->next;
3507                         entry->next = new_hash [hash];
3508                         new_hash [hash] = entry;
3509                 }
3510         }
3511         mono_sgen_free_internal_dynamic (finalizable_hash, finalizable_hash_size * sizeof (FinalizeEntry*), INTERNAL_MEM_FIN_TABLE);
3512         hash_table->table = new_hash;
3513         hash_table->size = new_size;
3514 }
3515
3516 /* LOCKING: requires that the GC lock is held */
3517 static void
3518 rehash_fin_table_if_necessary (FinalizeEntryHashTable *hash_table)
3519 {
3520         if (hash_table->num_registered >= hash_table->size * 2)
3521                 rehash_fin_table (hash_table);
3522 }
3523
3524 /* LOCKING: requires that the GC lock is held */
3525 static void
3526 finalize_in_range (CopyOrMarkObjectFunc copy_func, char *start, char *end, int generation, GrayQueue *queue)
3527 {
3528         FinalizeEntryHashTable *hash_table = get_finalize_entry_hash_table (generation);
3529         FinalizeEntry *entry, *prev;
3530         int i;
3531         FinalizeEntry **finalizable_hash = hash_table->table;
3532         mword finalizable_hash_size = hash_table->size;
3533
3534         if (no_finalize)
3535                 return;
3536         for (i = 0; i < finalizable_hash_size; ++i) {
3537                 prev = NULL;
3538                 for (entry = finalizable_hash [i]; entry;) {
3539                         if ((char*)entry->object >= start && (char*)entry->object < end && !major.is_object_live (entry->object)) {
3540                                 gboolean is_fin_ready = object_is_fin_ready (entry->object);
3541                                 char *copy = entry->object;
3542                                 copy_func ((void**)&copy, queue);
3543                                 if (is_fin_ready) {
3544                                         char *from;
3545                                         FinalizeEntry *next;
3546                                         /* remove and put in fin_ready_list */
3547                                         if (prev)
3548                                                 prev->next = entry->next;
3549                                         else
3550                                                 finalizable_hash [i] = entry->next;
3551                                         next = entry->next;
3552                                         num_ready_finalizers++;
3553                                         hash_table->num_registered--;
3554                                         queue_finalization_entry (entry);
3555                                         /* Make it survive */
3556                                         from = entry->object;
3557                                         entry->object = copy;
3558                                         DEBUG (5, fprintf (gc_debug_file, "Queueing object for finalization: %p (%s) (was at %p) (%d/%d)\n", entry->object, safe_name (entry->object), from, num_ready_finalizers, hash_table->num_registered));
3559                                         entry = next;
3560                                         continue;
3561                                 } else {
3562                                         char *from = entry->object;
3563                                         if (hash_table == &minor_finalizable_hash && !ptr_in_nursery (copy)) {
3564                                                 FinalizeEntry *next = entry->next;
3565                                                 unsigned int major_hash;
3566                                                 /* remove from the list */
3567                                                 if (prev)
3568                                                         prev->next = entry->next;
3569                                                 else
3570                                                         finalizable_hash [i] = entry->next;
3571                                                 hash_table->num_registered--;
3572
3573                                                 entry->object = copy;
3574
3575                                                 /* insert it into the major hash */
3576                                                 rehash_fin_table_if_necessary (&major_finalizable_hash);
3577                                                 major_hash = mono_object_hash ((MonoObject*) copy) %
3578                                                         major_finalizable_hash.size;
3579                                                 entry->next = major_finalizable_hash.table [major_hash];
3580                                                 major_finalizable_hash.table [major_hash] = entry;
3581                                                 major_finalizable_hash.num_registered++;
3582
3583                                                 DEBUG (5, fprintf (gc_debug_file, "Promoting finalization of object %p (%s) (was at %p) to major table\n", copy, safe_name (copy), from));
3584
3585                                                 entry = next;
3586                                                 continue;
3587                                         } else {
3588                                                 /* update pointer */
3589                                                 DEBUG (5, fprintf (gc_debug_file, "Updating object for finalization: %p (%s) (was at %p)\n", entry->object, safe_name (entry->object), from));
3590                                                 entry->object = copy;
3591                                         }
3592                                 }
3593                         }
3594                         prev = entry;
3595                         entry = entry->next;
3596                 }
3597         }
3598 }
3599
3600 static int
3601 object_is_reachable (char *object, char *start, char *end)
3602 {
3603         /*This happens for non nursery objects during minor collections. We just treat all objects as alive.*/
3604         if (object < start || object >= end)
3605                 return TRUE;
3606         return !object_is_fin_ready (object) || major.is_object_live (object);
3607 }
3608
3609 /* LOCKING: requires that the GC lock is held */
3610 static void
3611 null_ephemerons_for_domain (MonoDomain *domain)
3612 {
3613         EphemeronLinkNode *current = ephemeron_list, *prev = NULL;
3614
3615         while (current) {
3616                 MonoObject *object = (MonoObject*)current->array;
3617
3618                 if (object && !object->vtable) {
3619                         EphemeronLinkNode *tmp = current;
3620
3621                         if (prev)
3622                                 prev->next = current->next;
3623                         else
3624                                 ephemeron_list = current->next;
3625
3626                         current = current->next;
3627                         mono_sgen_free_internal (tmp, INTERNAL_MEM_EPHEMERON_LINK);
3628                 } else {
3629                         prev = current;
3630                         current = current->next;
3631                 }
3632         }
3633 }
3634
3635 /* LOCKING: requires that the GC lock is held */
3636 static void
3637 clear_unreachable_ephemerons (CopyOrMarkObjectFunc copy_func, char *start, char *end, GrayQueue *queue)
3638 {
3639         int was_in_nursery, was_promoted;
3640         EphemeronLinkNode *current = ephemeron_list, *prev = NULL;
3641         MonoArray *array;
3642         Ephemeron *cur, *array_end;
3643         char *tombstone;
3644
3645         while (current) {
3646                 char *object = current->array;
3647
3648                 if (!object_is_reachable (object, start, end)) {
3649                         EphemeronLinkNode *tmp = current;
3650
3651                         DEBUG (5, fprintf (gc_debug_file, "Dead Ephemeron array at %p\n", object));
3652
3653                         if (prev)
3654                                 prev->next = current->next;
3655                         else
3656                                 ephemeron_list = current->next;
3657
3658                         current = current->next;
3659                         mono_sgen_free_internal (tmp, INTERNAL_MEM_EPHEMERON_LINK);
3660
3661                         continue;
3662                 }
3663
3664                 was_in_nursery = ptr_in_nursery (object);
3665                 copy_func ((void**)&object, queue);
3666                 current->array = object;
3667
3668                 /*The array was promoted, add global remsets for key/values left behind in nursery.*/
3669                 was_promoted = was_in_nursery && !ptr_in_nursery (object);
3670
3671                 DEBUG (5, fprintf (gc_debug_file, "Clearing unreachable entries for ephemeron array at %p\n", object));
3672
3673                 array = (MonoArray*)object;
3674                 cur = mono_array_addr (array, Ephemeron, 0);
3675                 array_end = cur + mono_array_length_fast (array);
3676                 tombstone = (char*)((MonoVTable*)LOAD_VTABLE (object))->domain->ephemeron_tombstone;
3677
3678                 for (; cur < array_end; ++cur) {
3679                         char *key = (char*)cur->key;
3680
3681                         if (!key || key == tombstone)
3682                                 continue;
3683
3684                         DEBUG (5, fprintf (gc_debug_file, "[%td] key %p (%s) value %p (%s)\n", cur - mono_array_addr (array, Ephemeron, 0),
3685                                 key, object_is_reachable (key, start, end) ? "reachable" : "unreachable",
3686                                 cur->value, cur->value && object_is_reachable (cur->value, start, end) ? "reachable" : "unreachable"));
3687
3688                         if (!object_is_reachable (key, start, end)) {
3689                                 cur->key = tombstone;
3690                                 cur->value = NULL;
3691                                 continue;
3692                         }
3693
3694                         if (was_promoted) {
3695                                 if (ptr_in_nursery (key)) {/*key was not promoted*/
3696                                         DEBUG (5, fprintf (gc_debug_file, "\tAdded remset to key %p\n", key));
3697                                         mono_sgen_add_to_global_remset (&cur->key);
3698                                 }
3699                                 if (ptr_in_nursery (cur->value)) {/*value was not promoted*/
3700                                         DEBUG (5, fprintf (gc_debug_file, "\tAdded remset to value %p\n", cur->value));
3701                                         mono_sgen_add_to_global_remset (&cur->value);
3702                                 }
3703                         }
3704                 }
3705                 prev = current;
3706                 current = current->next;
3707         }
3708 }
3709
3710 /* LOCKING: requires that the GC lock is held */
3711 static int
3712 mark_ephemerons_in_range (CopyOrMarkObjectFunc copy_func, char *start, char *end, GrayQueue *queue)
3713 {
3714         int nothing_marked = 1;
3715         EphemeronLinkNode *current = ephemeron_list;
3716         MonoArray *array;
3717         Ephemeron *cur, *array_end;
3718         char *tombstone;
3719
3720         for (current = ephemeron_list; current; current = current->next) {
3721                 char *object = current->array;
3722                 DEBUG (5, fprintf (gc_debug_file, "Ephemeron array at %p\n", object));
3723
3724                 /*We ignore arrays in old gen during minor collections since all objects are promoted by the remset machinery.*/
3725                 if (object < start || object >= end)
3726                         continue;
3727
3728                 /*It has to be alive*/
3729                 if (!object_is_reachable (object, start, end)) {
3730                         DEBUG (5, fprintf (gc_debug_file, "\tnot reachable\n"));
3731                         continue;
3732                 }
3733
3734                 copy_func ((void**)&object, queue);
3735
3736                 array = (MonoArray*)object;
3737                 cur = mono_array_addr (array, Ephemeron, 0);
3738                 array_end = cur + mono_array_length_fast (array);
3739                 tombstone = (char*)((MonoVTable*)LOAD_VTABLE (object))->domain->ephemeron_tombstone;
3740
3741                 for (; cur < array_end; ++cur) {
3742                         char *key = cur->key;
3743
3744                         if (!key || key == tombstone)
3745                                 continue;
3746
3747                         DEBUG (5, fprintf (gc_debug_file, "[%td] key %p (%s) value %p (%s)\n", cur - mono_array_addr (array, Ephemeron, 0),
3748                                 key, object_is_reachable (key, start, end) ? "reachable" : "unreachable",
3749                                 cur->value, cur->value && object_is_reachable (cur->value, start, end) ? "reachable" : "unreachable"));
3750
3751                         if (object_is_reachable (key, start, end)) {
3752                                 char *value = cur->value;
3753
3754                                 copy_func ((void**)&cur->key, queue);
3755                                 if (value) {
3756                                         if (!object_is_reachable (value, start, end))
3757                                                 nothing_marked = 0;
3758                                         copy_func ((void**)&cur->value, queue);
3759                                 }
3760                         }
3761                 }
3762         }
3763
3764         DEBUG (5, fprintf (gc_debug_file, "Ephemeron run finished. Is it done %d\n", nothing_marked));
3765         return nothing_marked;
3766 }
3767
3768 /* LOCKING: requires that the GC lock is held */
3769 static void
3770 null_link_in_range (CopyOrMarkObjectFunc copy_func, char *start, char *end, int generation, GrayQueue *queue)
3771 {
3772         DisappearingLinkHashTable *hash = get_dislink_hash_table (generation);
3773         DisappearingLink **disappearing_link_hash = hash->table;
3774         int disappearing_link_hash_size = hash->size;
3775         DisappearingLink *entry, *prev;
3776         int i;
3777         if (!hash->num_links)
3778                 return;
3779         for (i = 0; i < disappearing_link_hash_size; ++i) {
3780                 prev = NULL;
3781                 for (entry = disappearing_link_hash [i]; entry;) {
3782                         char *object = DISLINK_OBJECT (entry);
3783                         if (object >= start && object < end && !major.is_object_live (object)) {
3784                                 gboolean track = DISLINK_TRACK (entry);
3785                                 if (!track && object_is_fin_ready (object)) {
3786                                         void **p = entry->link;
3787                                         DisappearingLink *old;
3788                                         *p = NULL;
3789                                         /* remove from list */
3790                                         if (prev)
3791                                                 prev->next = entry->next;
3792                                         else
3793                                                 disappearing_link_hash [i] = entry->next;
3794                                         DEBUG (5, fprintf (gc_debug_file, "Dislink nullified at %p to GCed object %p\n", p, object));
3795                                         old = entry->next;
3796                                         mono_sgen_free_internal (entry, INTERNAL_MEM_DISLINK);
3797                                         entry = old;
3798                                         hash->num_links--;
3799                                         continue;
3800                                 } else {
3801                                         char *copy = object;
3802                                         copy_func ((void**)&copy, queue);
3803
3804                                         /* Update pointer if it's moved.  If the object
3805                                          * has been moved out of the nursery, we need to
3806                                          * remove the link from the minor hash table to
3807                                          * the major one.
3808                                          *
3809                                          * FIXME: what if an object is moved earlier?
3810                                          */
3811
3812                                         if (hash == &minor_disappearing_link_hash && !ptr_in_nursery (copy)) {
3813                                                 void **link = entry->link;
3814                                                 DisappearingLink *old;
3815                                                 /* remove from list */
3816                                                 if (prev)
3817                                                         prev->next = entry->next;
3818                                                 else
3819                                                         disappearing_link_hash [i] = entry->next;
3820                                                 old = entry->next;
3821                                                 mono_sgen_free_internal (entry, INTERNAL_MEM_DISLINK);
3822                                                 entry = old;
3823                                                 hash->num_links--;
3824
3825                                                 add_or_remove_disappearing_link ((MonoObject*)copy, link,
3826                                                         track, GENERATION_OLD);
3827
3828                                                 DEBUG (5, fprintf (gc_debug_file, "Upgraded dislink at %p to major because object %p moved to %p\n", link, object, copy));
3829
3830                                                 continue;
3831                                         } else {
3832                                                 /* We set the track resurrection bit to
3833                                                  * FALSE if the object is to be finalized
3834                                                  * so that the object can be collected in
3835                                                  * the next cycle (i.e. after it was
3836                                                  * finalized).
3837                                                  */
3838                                                 *entry->link = HIDE_POINTER (copy,
3839                                                         object_is_fin_ready (object) ? FALSE : track);
3840                                                 DEBUG (5, fprintf (gc_debug_file, "Updated dislink at %p to %p\n", entry->link, DISLINK_OBJECT (entry)));
3841                                         }
3842                                 }
3843                         }
3844                         prev = entry;
3845                         entry = entry->next;
3846                 }
3847         }
3848 }
3849
3850 /* LOCKING: requires that the GC lock is held */
3851 static void
3852 null_links_for_domain (MonoDomain *domain, int generation)
3853 {
3854         DisappearingLinkHashTable *hash = get_dislink_hash_table (generation);
3855         DisappearingLink **disappearing_link_hash = hash->table;
3856         int disappearing_link_hash_size = hash->size;
3857         DisappearingLink *entry, *prev;
3858         int i;
3859         for (i = 0; i < disappearing_link_hash_size; ++i) {
3860                 prev = NULL;
3861                 for (entry = disappearing_link_hash [i]; entry; ) {
3862                         char *object = DISLINK_OBJECT (entry);
3863                         if (object && !((MonoObject*)object)->vtable) {
3864                                 DisappearingLink *next = entry->next;
3865
3866                                 if (prev)
3867                                         prev->next = next;
3868                                 else
3869                                         disappearing_link_hash [i] = next;
3870
3871                                 if (*(entry->link)) {
3872                                         *(entry->link) = NULL;
3873                                         g_warning ("Disappearing link %p not freed", entry->link);
3874                                 } else {
3875                                         mono_sgen_free_internal (entry, INTERNAL_MEM_DISLINK);
3876                                 }
3877
3878                                 entry = next;
3879                                 continue;
3880                         }
3881                         prev = entry;
3882                         entry = entry->next;
3883                 }
3884         }
3885 }
3886
3887 /* LOCKING: requires that the GC lock is held */
3888 static int
3889 finalizers_for_domain (MonoDomain *domain, MonoObject **out_array, int out_size,
3890         FinalizeEntryHashTable *hash_table)
3891 {
3892         FinalizeEntry **finalizable_hash = hash_table->table;
3893         mword finalizable_hash_size = hash_table->size;
3894         FinalizeEntry *entry, *prev;
3895         int i, count;
3896
3897         if (no_finalize || !out_size || !out_array)
3898                 return 0;
3899         count = 0;
3900         for (i = 0; i < finalizable_hash_size; ++i) {
3901                 prev = NULL;
3902                 for (entry = finalizable_hash [i]; entry;) {
3903                         if (mono_object_domain (entry->object) == domain) {
3904                                 FinalizeEntry *next;
3905                                 /* remove and put in out_array */
3906                                 if (prev)
3907                                         prev->next = entry->next;
3908                                 else
3909                                         finalizable_hash [i] = entry->next;
3910                                 next = entry->next;
3911                                 hash_table->num_registered--;
3912                                 out_array [count ++] = entry->object;
3913                                 DEBUG (5, fprintf (gc_debug_file, "Collecting object for finalization: %p (%s) (%d/%d)\n", entry->object, safe_name (entry->object), num_ready_finalizers, hash_table->num_registered));
3914                                 entry = next;
3915                                 if (count == out_size)
3916                                         return count;
3917                                 continue;
3918                         }
3919                         prev = entry;
3920                         entry = entry->next;
3921                 }
3922         }
3923         return count;
3924 }
3925
3926 /**
3927  * mono_gc_finalizers_for_domain:
3928  * @domain: the unloading appdomain
3929  * @out_array: output array
3930  * @out_size: size of output array
3931  *
3932  * Store inside @out_array up to @out_size objects that belong to the unloading
3933  * appdomain @domain. Returns the number of stored items. Can be called repeteadly
3934  * until it returns 0.
3935  * The items are removed from the finalizer data structure, so the caller is supposed
3936  * to finalize them.
3937  * @out_array should be on the stack to allow the GC to know the objects are still alive.
3938  */
3939 int
3940 mono_gc_finalizers_for_domain (MonoDomain *domain, MonoObject **out_array, int out_size)
3941 {
3942         int result;
3943
3944         LOCK_GC;
3945         result = finalizers_for_domain (domain, out_array, out_size, &minor_finalizable_hash);
3946         if (result < out_size) {
3947                 result += finalizers_for_domain (domain, out_array + result, out_size - result,
3948                         &major_finalizable_hash);
3949         }
3950         UNLOCK_GC;
3951
3952         return result;
3953 }
3954
3955 static void
3956 register_for_finalization (MonoObject *obj, void *user_data, int generation)
3957 {
3958         FinalizeEntryHashTable *hash_table = get_finalize_entry_hash_table (generation);
3959         FinalizeEntry **finalizable_hash;
3960         mword finalizable_hash_size;
3961         FinalizeEntry *entry, *prev;
3962         unsigned int hash;
3963         if (no_finalize)
3964                 return;
3965         g_assert (user_data == NULL || user_data == mono_gc_run_finalize);
3966         hash = mono_object_hash (obj);
3967         LOCK_GC;
3968         rehash_fin_table_if_necessary (hash_table);
3969         finalizable_hash = hash_table->table;
3970         finalizable_hash_size = hash_table->size;
3971         hash %= finalizable_hash_size;
3972         prev = NULL;
3973         for (entry = finalizable_hash [hash]; entry; entry = entry->next) {
3974                 if (entry->object == obj) {
3975                         if (!user_data) {
3976                                 /* remove from the list */
3977                                 if (prev)
3978                                         prev->next = entry->next;
3979                                 else
3980                                         finalizable_hash [hash] = entry->next;
3981                                 hash_table->num_registered--;
3982                                 DEBUG (5, fprintf (gc_debug_file, "Removed finalizer %p for object: %p (%s) (%d)\n", entry, obj, obj->vtable->klass->name, hash_table->num_registered));
3983                                 mono_sgen_free_internal (entry, INTERNAL_MEM_FINALIZE_ENTRY);
3984                         }
3985                         UNLOCK_GC;
3986                         return;
3987                 }
3988                 prev = entry;
3989         }
3990         if (!user_data) {
3991                 /* request to deregister, but already out of the list */
3992                 UNLOCK_GC;
3993                 return;
3994         }
3995         entry = mono_sgen_alloc_internal (INTERNAL_MEM_FINALIZE_ENTRY);
3996         entry->object = obj;
3997         entry->next = finalizable_hash [hash];
3998         finalizable_hash [hash] = entry;
3999         hash_table->num_registered++;
4000         DEBUG (5, fprintf (gc_debug_file, "Added finalizer %p for object: %p (%s) (%d) to %s table\n", entry, obj, obj->vtable->klass->name, hash_table->num_registered, generation_name (generation)));
4001         UNLOCK_GC;
4002 }
4003
4004 void
4005 mono_gc_register_for_finalization (MonoObject *obj, void *user_data)
4006 {
4007         if (ptr_in_nursery (obj))
4008                 register_for_finalization (obj, user_data, GENERATION_NURSERY);
4009         else
4010                 register_for_finalization (obj, user_data, GENERATION_OLD);
4011 }
4012
4013 static void
4014 rehash_dislink (DisappearingLinkHashTable *hash_table)
4015 {
4016         DisappearingLink **disappearing_link_hash = hash_table->table;
4017         int disappearing_link_hash_size = hash_table->size;
4018         int i;
4019         unsigned int hash;
4020         DisappearingLink **new_hash;
4021         DisappearingLink *entry, *next;
4022         int new_size = g_spaced_primes_closest (hash_table->num_links);
4023
4024         new_hash = mono_sgen_alloc_internal_dynamic (new_size * sizeof (DisappearingLink*), INTERNAL_MEM_DISLINK_TABLE);
4025         for (i = 0; i < disappearing_link_hash_size; ++i) {
4026                 for (entry = disappearing_link_hash [i]; entry; entry = next) {
4027                         hash = mono_aligned_addr_hash (entry->link) % new_size;
4028                         next = entry->next;
4029                         entry->next = new_hash [hash];
4030                         new_hash [hash] = entry;
4031                 }
4032         }
4033         mono_sgen_free_internal_dynamic (disappearing_link_hash,
4034                         disappearing_link_hash_size * sizeof (DisappearingLink*), INTERNAL_MEM_DISLINK_TABLE);
4035         hash_table->table = new_hash;
4036         hash_table->size = new_size;
4037 }
4038
4039 /* LOCKING: assumes the GC lock is held */
4040 static void
4041 add_or_remove_disappearing_link (MonoObject *obj, void **link, gboolean track, int generation)
4042 {
4043         DisappearingLinkHashTable *hash_table = get_dislink_hash_table (generation);
4044         DisappearingLink *entry, *prev;
4045         unsigned int hash;
4046         DisappearingLink **disappearing_link_hash = hash_table->table;
4047         int disappearing_link_hash_size = hash_table->size;
4048
4049         if (hash_table->num_links >= disappearing_link_hash_size * 2) {
4050                 rehash_dislink (hash_table);
4051                 disappearing_link_hash = hash_table->table;
4052                 disappearing_link_hash_size = hash_table->size;
4053         }
4054         /* FIXME: add check that link is not in the heap */
4055         hash = mono_aligned_addr_hash (link) % disappearing_link_hash_size;
4056         entry = disappearing_link_hash [hash];
4057         prev = NULL;
4058         for (; entry; entry = entry->next) {
4059                 /* link already added */
4060                 if (link == entry->link) {
4061                         /* NULL obj means remove */
4062                         if (obj == NULL) {
4063                                 if (prev)
4064                                         prev->next = entry->next;
4065                                 else
4066                                         disappearing_link_hash [hash] = entry->next;
4067                                 hash_table->num_links--;
4068                                 DEBUG (5, fprintf (gc_debug_file, "Removed dislink %p (%d) from %s table\n", entry, hash_table->num_links, generation_name (generation)));
4069                                 mono_sgen_free_internal (entry, INTERNAL_MEM_DISLINK);
4070                                 *link = NULL;
4071                         } else {
4072                                 *link = HIDE_POINTER (obj, track); /* we allow the change of object */
4073                         }
4074                         return;
4075                 }
4076                 prev = entry;
4077         }
4078         if (obj == NULL)
4079                 return;
4080         entry = mono_sgen_alloc_internal (INTERNAL_MEM_DISLINK);
4081         *link = HIDE_POINTER (obj, track);
4082         entry->link = link;
4083         entry->next = disappearing_link_hash [hash];
4084         disappearing_link_hash [hash] = entry;
4085         hash_table->num_links++;
4086         DEBUG (5, fprintf (gc_debug_file, "Added dislink %p for object: %p (%s) at %p to %s table\n", entry, obj, obj->vtable->klass->name, link, generation_name (generation)));
4087 }
4088
4089 /* LOCKING: assumes the GC lock is held */
4090 static void
4091 mono_gc_register_disappearing_link (MonoObject *obj, void **link, gboolean track)
4092 {
4093         add_or_remove_disappearing_link (NULL, link, FALSE, GENERATION_NURSERY);
4094         add_or_remove_disappearing_link (NULL, link, FALSE, GENERATION_OLD);
4095         if (obj) {
4096                 if (ptr_in_nursery (obj))
4097                         add_or_remove_disappearing_link (obj, link, track, GENERATION_NURSERY);
4098                 else
4099                         add_or_remove_disappearing_link (obj, link, track, GENERATION_OLD);
4100         }
4101 }
4102
4103 int
4104 mono_gc_invoke_finalizers (void)
4105 {
4106         FinalizeEntry *entry = NULL;
4107         gboolean entry_is_critical = FALSE;
4108         int count = 0;
4109         void *obj;
4110         /* FIXME: batch to reduce lock contention */
4111         while (fin_ready_list || critical_fin_list) {
4112                 LOCK_GC;
4113
4114                 if (entry) {
4115                         FinalizeEntry **list = entry_is_critical ? &critical_fin_list : &fin_ready_list;
4116
4117                         /* We have finalized entry in the last
4118                            interation, now we need to remove it from
4119                            the list. */
4120                         if (*list == entry)
4121                                 *list = entry->next;
4122                         else {
4123                                 FinalizeEntry *e = *list;
4124                                 while (e->next != entry)
4125                                         e = e->next;
4126                                 e->next = entry->next;
4127                         }
4128                         mono_sgen_free_internal (entry, INTERNAL_MEM_FINALIZE_ENTRY);
4129                         entry = NULL;
4130                 }
4131
4132                 /* Now look for the first non-null entry. */
4133                 for (entry = fin_ready_list; entry && !entry->object; entry = entry->next)
4134                         ;
4135                 if (entry) {
4136                         entry_is_critical = FALSE;
4137                 } else {
4138                         entry_is_critical = TRUE;
4139                         for (entry = critical_fin_list; entry && !entry->object; entry = entry->next)
4140                                 ;
4141                 }
4142
4143                 if (entry) {
4144                         g_assert (entry->object);
4145                         num_ready_finalizers--;
4146                         obj = entry->object;
4147                         entry->object = NULL;
4148                         DEBUG (7, fprintf (gc_debug_file, "Finalizing object %p (%s)\n", obj, safe_name (obj)));
4149                 }
4150
4151                 UNLOCK_GC;
4152
4153                 if (!entry)
4154                         break;
4155
4156                 g_assert (entry->object == NULL);
4157                 count++;
4158                 /* the object is on the stack so it is pinned */
4159                 /*g_print ("Calling finalizer for object: %p (%s)\n", entry->object, safe_name (entry->object));*/
4160                 mono_gc_run_finalize (obj, NULL);
4161         }
4162         g_assert (!entry);
4163         return count;
4164 }
4165
4166 gboolean
4167 mono_gc_pending_finalizers (void)
4168 {
4169         return fin_ready_list || critical_fin_list;
4170 }
4171
4172 /* Negative value to remove */
4173 void
4174 mono_gc_add_memory_pressure (gint64 value)
4175 {
4176         /* FIXME: Use interlocked functions */
4177         LOCK_GC;
4178         memory_pressure += value;
4179         UNLOCK_GC;
4180 }
4181
4182 void
4183 mono_sgen_register_major_sections_alloced (int num_sections)
4184 {
4185         minor_collection_sections_alloced += num_sections;
4186 }
4187
4188 mword
4189 mono_sgen_get_minor_collection_allowance (void)
4190 {
4191         return minor_collection_allowance;
4192 }
4193
4194 /*
4195  * ######################################################################
4196  * ########  registered roots support
4197  * ######################################################################
4198  */
4199
4200 static void
4201 rehash_roots (gboolean pinned)
4202 {
4203         int i;
4204         unsigned int hash;
4205         RootRecord **new_hash;
4206         RootRecord *entry, *next;
4207         int new_size;
4208
4209         new_size = g_spaced_primes_closest (num_roots_entries [pinned]);
4210         new_hash = mono_sgen_alloc_internal_dynamic (new_size * sizeof (RootRecord*), INTERNAL_MEM_ROOTS_TABLE);
4211         for (i = 0; i < roots_hash_size [pinned]; ++i) {
4212                 for (entry = roots_hash [pinned][i]; entry; entry = next) {
4213                         hash = mono_aligned_addr_hash (entry->start_root) % new_size;
4214                         next = entry->next;
4215                         entry->next = new_hash [hash];
4216                         new_hash [hash] = entry;
4217                 }
4218         }
4219         mono_sgen_free_internal_dynamic (roots_hash [pinned], roots_hash_size [pinned] * sizeof (RootRecord*), INTERNAL_MEM_ROOTS_TABLE);
4220         roots_hash [pinned] = new_hash;
4221         roots_hash_size [pinned] = new_size;
4222 }
4223
4224 static RootRecord*
4225 find_root (int root_type, char *start, guint32 addr_hash)
4226 {
4227         RootRecord *new_root;
4228
4229         guint32 hash = addr_hash % roots_hash_size [root_type];
4230         for (new_root = roots_hash [root_type][hash]; new_root; new_root = new_root->next) {
4231                 /* we allow changing the size and the descriptor (for thread statics etc) */
4232                 if (new_root->start_root == start) {
4233                         return new_root;
4234                 }
4235         }
4236
4237         return NULL;
4238 }
4239
4240 /*
4241  * We do not coalesce roots.
4242  */
4243 static int
4244 mono_gc_register_root_inner (char *start, size_t size, void *descr, int root_type)
4245 {
4246         RootRecord *new_root;
4247         unsigned int hash, addr_hash = mono_aligned_addr_hash (start);
4248         int i;
4249         LOCK_GC;
4250         for (i = 0; i < ROOT_TYPE_NUM; ++i) {
4251                 if (num_roots_entries [i] >= roots_hash_size [i] * 2)
4252                         rehash_roots (i);
4253         }
4254         for (i = 0; i < ROOT_TYPE_NUM; ++i) {
4255                 new_root = find_root (i, start, addr_hash);
4256                 /* we allow changing the size and the descriptor (for thread statics etc) */
4257                 if (new_root) {
4258                         size_t old_size = new_root->end_root - new_root->start_root;
4259                         new_root->end_root = new_root->start_root + size;
4260                         g_assert (((new_root->root_desc != 0) && (descr != NULL)) ||
4261                                           ((new_root->root_desc == 0) && (descr == NULL)));
4262                         new_root->root_desc = (mword)descr;
4263                         roots_size += size;
4264                         roots_size -= old_size;
4265                         UNLOCK_GC;
4266                         return TRUE;
4267                 }
4268         }
4269         new_root = mono_sgen_alloc_internal (INTERNAL_MEM_ROOT_RECORD);
4270         if (new_root) {
4271                 new_root->start_root = start;
4272                 new_root->end_root = new_root->start_root + size;
4273                 new_root->root_desc = (mword)descr;
4274                 roots_size += size;
4275                 hash = addr_hash % roots_hash_size [root_type];
4276                 num_roots_entries [root_type]++;
4277                 new_root->next = roots_hash [root_type] [hash];
4278                 roots_hash [root_type][hash] = new_root;
4279                 DEBUG (3, fprintf (gc_debug_file, "Added root %p for range: %p-%p, descr: %p  (%d/%d bytes)\n", new_root, new_root->start_root, new_root->end_root, descr, (int)size, (int)roots_size));
4280         } else {
4281                 UNLOCK_GC;
4282                 return FALSE;
4283         }
4284         UNLOCK_GC;
4285         return TRUE;
4286 }
4287
4288 int
4289 mono_gc_register_root (char *start, size_t size, void *descr)
4290 {
4291         return mono_gc_register_root_inner (start, size, descr, descr ? ROOT_TYPE_NORMAL : ROOT_TYPE_PINNED);
4292 }
4293
4294 int
4295 mono_gc_register_root_wbarrier (char *start, size_t size, void *descr)
4296 {
4297         return mono_gc_register_root_inner (start, size, descr, ROOT_TYPE_WBARRIER);
4298 }
4299
4300 void
4301 mono_gc_deregister_root (char* addr)
4302 {
4303         RootRecord *tmp, *prev;
4304         unsigned int hash, addr_hash = mono_aligned_addr_hash (addr);
4305         int root_type;
4306
4307         LOCK_GC;
4308         for (root_type = 0; root_type < ROOT_TYPE_NUM; ++root_type) {
4309                 hash = addr_hash % roots_hash_size [root_type];
4310                 tmp = roots_hash [root_type][hash];
4311                 prev = NULL;
4312                 while (tmp) {
4313                         if (tmp->start_root == (char*)addr) {
4314                                 if (prev)
4315                                         prev->next = tmp->next;
4316                                 else
4317                                         roots_hash [root_type][hash] = tmp->next;
4318                                 roots_size -= (tmp->end_root - tmp->start_root);
4319                                 num_roots_entries [root_type]--;
4320                                 DEBUG (3, fprintf (gc_debug_file, "Removed root %p for range: %p-%p\n", tmp, tmp->start_root, tmp->end_root));
4321                                 mono_sgen_free_internal (tmp, INTERNAL_MEM_ROOT_RECORD);
4322                                 break;
4323                         }
4324                         prev = tmp;
4325                         tmp = tmp->next;
4326                 }
4327         }
4328         UNLOCK_GC;
4329 }
4330
4331 /*
4332  * ######################################################################
4333  * ########  Thread handling (stop/start code)
4334  * ######################################################################
4335  */
4336
4337 /* FIXME: handle large/small config */
4338 #define HASH_PTHREAD_T(id) (((unsigned int)(id) >> 4) * 2654435761u)
4339
4340 static SgenThreadInfo* thread_table [THREAD_HASH_SIZE];
4341
4342 #if USE_SIGNAL_BASED_START_STOP_WORLD
4343
4344 static MonoSemType suspend_ack_semaphore;
4345 static MonoSemType *suspend_ack_semaphore_ptr;
4346 static unsigned int global_stop_count = 0;
4347
4348 static sigset_t suspend_signal_mask;
4349 static mword cur_thread_regs [ARCH_NUM_REGS] = {0};
4350
4351 /* LOCKING: assumes the GC lock is held */
4352 SgenThreadInfo**
4353 mono_sgen_get_thread_table (void)
4354 {
4355         return thread_table;
4356 }
4357
4358 SgenThreadInfo*
4359 mono_sgen_thread_info_lookup (ARCH_THREAD_TYPE id)
4360 {
4361         unsigned int hash = HASH_PTHREAD_T (id) % THREAD_HASH_SIZE;
4362         SgenThreadInfo *info;
4363
4364         info = thread_table [hash];
4365         while (info && !ARCH_THREAD_EQUALS (info->id, id)) {
4366                 info = info->next;
4367         }
4368         return info;
4369 }
4370
4371 static void
4372 update_current_thread_stack (void *start)
4373 {
4374         void *ptr = cur_thread_regs;
4375         SgenThreadInfo *info = mono_sgen_thread_info_lookup (ARCH_GET_THREAD ());
4376         
4377         info->stack_start = align_pointer (&ptr);
4378         g_assert (info->stack_start >= info->stack_start_limit && info->stack_start < info->stack_end);
4379         ARCH_STORE_REGS (ptr);
4380         info->stopped_regs = ptr;
4381         if (gc_callbacks.thread_suspend_func)
4382                 gc_callbacks.thread_suspend_func (info->runtime_data, NULL);
4383 }
4384
4385 /*
4386  * Define this and use the "xdomain-checks" MONO_GC_DEBUG option to
4387  * have cross-domain checks in the write barrier.
4388  */
4389 //#define XDOMAIN_CHECKS_IN_WBARRIER
4390
4391 #ifndef SGEN_BINARY_PROTOCOL
4392 #ifndef HEAVY_STATISTICS
4393 #define MANAGED_ALLOCATION
4394 #ifndef XDOMAIN_CHECKS_IN_WBARRIER
4395 #define MANAGED_WBARRIER
4396 #endif
4397 #endif
4398 #endif
4399
4400 static gboolean
4401 is_ip_in_managed_allocator (MonoDomain *domain, gpointer ip);
4402
4403 void
4404 mono_sgen_wait_for_suspend_ack (int count)
4405 {
4406         int i, result;
4407
4408         for (i = 0; i < count; ++i) {
4409                 while ((result = MONO_SEM_WAIT (suspend_ack_semaphore_ptr)) != 0) {
4410                         if (errno != EINTR) {
4411                                 g_error ("sem_wait ()");
4412                         }
4413                 }
4414         }
4415 }
4416
4417 static int
4418 restart_threads_until_none_in_managed_allocator (void)
4419 {
4420         SgenThreadInfo *info;
4421         int i, result, num_threads_died = 0;
4422         int sleep_duration = -1;
4423
4424         for (;;) {
4425                 int restart_count = 0, restarted_count = 0;
4426                 /* restart all threads that stopped in the
4427                    allocator */
4428                 for (i = 0; i < THREAD_HASH_SIZE; ++i) {
4429                         for (info = thread_table [i]; info; info = info->next) {
4430                                 if (info->skip)
4431                                         continue;
4432                                 if (!info->stack_start || info->in_critical_region ||
4433                                                 is_ip_in_managed_allocator (info->stopped_domain, info->stopped_ip)) {
4434                                         binary_protocol_thread_restart ((gpointer)info->id);
4435 #if defined(__MACH__) && MONO_MACH_ARCH_SUPPORTED
4436                                         result = thread_resume (pthread_mach_thread_np (info->id));
4437 #else
4438                                         result = pthread_kill (info->id, restart_signal_num);
4439 #endif
4440                                         if (result == 0) {
4441                                                 ++restart_count;
4442                                         } else {
4443                                                 info->skip = 1;
4444                                         }
4445                                 } else {
4446                                         /* we set the stopped_ip to
4447                                            NULL for threads which
4448                                            we're not restarting so
4449                                            that we can easily identify
4450                                            the others */
4451                                         info->stopped_ip = NULL;
4452                                         info->stopped_domain = NULL;
4453                                 }
4454                         }
4455                 }
4456                 /* if no threads were restarted, we're done */
4457                 if (restart_count == 0)
4458                         break;
4459
4460 #if defined(__MACH__) && MONO_MACH_ARCH_SUPPORTED
4461                 /* mach thread_resume is synchronous so we dont need to wait for them */
4462 #else
4463                 /* wait for the threads to signal their restart */
4464                 mono_sgen_wait_for_suspend_ack (restart_count);
4465 #endif
4466
4467                 if (sleep_duration < 0) {
4468                         sched_yield ();
4469                         sleep_duration = 0;
4470                 } else {
4471                         g_usleep (sleep_duration);
4472                         sleep_duration += 10;
4473                 }
4474
4475                 /* stop them again */
4476                 for (i = 0; i < THREAD_HASH_SIZE; ++i) {
4477                         for (info = thread_table [i]; info; info = info->next) {
4478                                 if (info->skip || info->stopped_ip == NULL)
4479                                         continue;
4480 #if defined(__MACH__) && MONO_MACH_ARCH_SUPPORTED
4481                                 result = thread_suspend (pthread_mach_thread_np (info->id));
4482 #else
4483                                 result = pthread_kill (info->id, suspend_signal_num);
4484 #endif
4485                                 if (result == 0) {
4486                                         ++restarted_count;
4487                                 } else {
4488                                         info->skip = 1;
4489                                 }
4490                         }
4491                 }
4492                 /* some threads might have died */
4493                 num_threads_died += restart_count - restarted_count;
4494 #if defined(__MACH__) && MONO_MACH_ARCH_SUPPORTED
4495                 /* mach thread_resume is synchronous so we dont need to wait for them */
4496 #else
4497                 /* wait for the threads to signal their suspension
4498                    again */
4499                 mono_sgen_wait_for_suspend_ack (restart_count);
4500 #endif
4501         }
4502
4503         return num_threads_died;
4504 }
4505
4506 /* LOCKING: assumes the GC lock is held (by the stopping thread) */
4507 static void
4508 suspend_handler (int sig, siginfo_t *siginfo, void *context)
4509 {
4510         SgenThreadInfo *info;
4511         pthread_t id;
4512         int stop_count;
4513         int old_errno = errno;
4514         gpointer regs [ARCH_NUM_REGS];
4515         gpointer stack_start;
4516
4517         id = pthread_self ();
4518         info = mono_sgen_thread_info_lookup (id);
4519         info->stopped_domain = mono_domain_get ();
4520         info->stopped_ip = (gpointer) ARCH_SIGCTX_IP (context);
4521         stop_count = global_stop_count;
4522         /* duplicate signal */
4523         if (0 && info->stop_count == stop_count) {
4524                 errno = old_errno;
4525                 return;
4526         }
4527 #ifdef HAVE_KW_THREAD
4528         /* update the remset info in the thread data structure */
4529         info->remset = remembered_set;
4530 #endif
4531         stack_start = (char*) ARCH_SIGCTX_SP (context) - REDZONE_SIZE;
4532         /* If stack_start is not within the limits, then don't set it
4533            in info and we will be restarted. */
4534         if (stack_start >= info->stack_start_limit && info->stack_start <= info->stack_end) {
4535                 info->stack_start = stack_start;
4536
4537                 ARCH_COPY_SIGCTX_REGS (regs, context);
4538                 info->stopped_regs = regs;
4539         } else {
4540                 g_assert (!info->stack_start);
4541         }
4542
4543         /* Notify the JIT */
4544         if (gc_callbacks.thread_suspend_func)
4545                 gc_callbacks.thread_suspend_func (info->runtime_data, context);
4546
4547         DEBUG (4, fprintf (gc_debug_file, "Posting suspend_ack_semaphore for suspend from %p %p\n", info, (gpointer)ARCH_GET_THREAD ()));
4548         /* notify the waiting thread */
4549         MONO_SEM_POST (suspend_ack_semaphore_ptr);
4550         info->stop_count = stop_count;
4551
4552         /* wait until we receive the restart signal */
4553         do {
4554                 info->signal = 0;
4555                 sigsuspend (&suspend_signal_mask);
4556         } while (info->signal != restart_signal_num);
4557
4558         DEBUG (4, fprintf (gc_debug_file, "Posting suspend_ack_semaphore for resume from %p %p\n", info, (gpointer)ARCH_GET_THREAD ()));
4559         /* notify the waiting thread */
4560         MONO_SEM_POST (suspend_ack_semaphore_ptr);
4561
4562         errno = old_errno;
4563 }
4564
4565 static void
4566 restart_handler (int sig)
4567 {
4568         SgenThreadInfo *info;
4569         int old_errno = errno;
4570
4571         info = mono_sgen_thread_info_lookup (pthread_self ());
4572         info->signal = restart_signal_num;
4573         DEBUG (4, fprintf (gc_debug_file, "Restart handler in %p %p\n", info, (gpointer)ARCH_GET_THREAD ()));
4574
4575         errno = old_errno;
4576 }
4577
4578 static void
4579 acquire_gc_locks (void)
4580 {
4581         LOCK_INTERRUPTION;
4582 }
4583
4584 static void
4585 release_gc_locks (void)
4586 {
4587         UNLOCK_INTERRUPTION;
4588 }
4589
4590 static TV_DECLARE (stop_world_time);
4591 static unsigned long max_pause_usec = 0;
4592
4593 /* LOCKING: assumes the GC lock is held */
4594 static int
4595 stop_world (void)
4596 {
4597         int count;
4598
4599         acquire_gc_locks ();
4600
4601         update_current_thread_stack (&count);
4602
4603         global_stop_count++;
4604         DEBUG (3, fprintf (gc_debug_file, "stopping world n %d from %p %p\n", global_stop_count, mono_sgen_thread_info_lookup (ARCH_GET_THREAD ()), (gpointer)ARCH_GET_THREAD ()));
4605         TV_GETTIME (stop_world_time);
4606         count = mono_sgen_thread_handshake (suspend_signal_num);
4607         count -= restart_threads_until_none_in_managed_allocator ();
4608         g_assert (count >= 0);
4609         DEBUG (3, fprintf (gc_debug_file, "world stopped %d thread(s)\n", count));
4610         return count;
4611 }
4612
4613 /* LOCKING: assumes the GC lock is held */
4614 static int
4615 restart_world (void)
4616 {
4617         int count, i;
4618         SgenThreadInfo *info;
4619         TV_DECLARE (end_sw);
4620         unsigned long usec;
4621
4622         /* notify the profiler of the leftovers */
4623         if (G_UNLIKELY (mono_profiler_events & MONO_PROFILE_GC_MOVES)) {
4624                 if (moved_objects_idx) {
4625                         mono_profiler_gc_moves (moved_objects, moved_objects_idx);
4626                         moved_objects_idx = 0;
4627                 }
4628         }
4629         for (i = 0; i < THREAD_HASH_SIZE; ++i) {
4630                 for (info = thread_table [i]; info; info = info->next) {
4631                         info->stack_start = NULL;
4632                         info->stopped_regs = NULL;
4633                 }
4634         }
4635
4636         release_gc_locks ();
4637
4638         count = mono_sgen_thread_handshake (restart_signal_num);
4639         TV_GETTIME (end_sw);
4640         usec = TV_ELAPSED (stop_world_time, end_sw);
4641         max_pause_usec = MAX (usec, max_pause_usec);
4642         DEBUG (2, fprintf (gc_debug_file, "restarted %d thread(s) (pause time: %d usec, max: %d)\n", count, (int)usec, (int)max_pause_usec));
4643         return count;
4644 }
4645
4646 #endif /* USE_SIGNAL_BASED_START_STOP_WORLD */
4647
4648 void
4649 mono_gc_set_gc_callbacks (MonoGCCallbacks *callbacks)
4650 {
4651         gc_callbacks = *callbacks;
4652 }
4653
4654 MonoGCCallbacks *
4655 mono_gc_get_gc_callbacks ()
4656 {
4657         return &gc_callbacks;
4658 }
4659
4660 /* Variables holding start/end nursery so it won't have to be passed at every call */
4661 static void *scan_area_arg_start, *scan_area_arg_end;
4662
4663 void
4664 mono_gc_conservatively_scan_area (void *start, void *end)
4665 {
4666         conservatively_pin_objects_from (start, end, scan_area_arg_start, scan_area_arg_end, PIN_TYPE_STACK);
4667 }
4668
4669 void*
4670 mono_gc_scan_object (void *obj)
4671 {
4672         if (current_collection_generation == GENERATION_NURSERY)
4673                 major.copy_object (&obj, &gray_queue);
4674         else
4675                 major.copy_or_mark_object (&obj, &gray_queue);
4676         return obj;
4677 }
4678
4679 /*
4680  * Mark from thread stacks and registers.
4681  */
4682 static void
4683 scan_thread_data (void *start_nursery, void *end_nursery, gboolean precise)
4684 {
4685         int i;
4686         SgenThreadInfo *info;
4687
4688         scan_area_arg_start = start_nursery;
4689         scan_area_arg_end = end_nursery;
4690
4691         for (i = 0; i < THREAD_HASH_SIZE; ++i) {
4692                 for (info = thread_table [i]; info; info = info->next) {
4693                         if (info->skip) {
4694                                 DEBUG (3, fprintf (gc_debug_file, "Skipping dead thread %p, range: %p-%p, size: %td\n", info, info->stack_start, info->stack_end, (char*)info->stack_end - (char*)info->stack_start));
4695                                 continue;
4696                         }
4697                         DEBUG (3, fprintf (gc_debug_file, "Scanning thread %p, range: %p-%p, size: %td, pinned=%d\n", info, info->stack_start, info->stack_end, (char*)info->stack_end - (char*)info->stack_start, next_pin_slot));
4698                         if (gc_callbacks.thread_mark_func && !conservative_stack_mark)
4699                                 gc_callbacks.thread_mark_func (info->runtime_data, info->stack_start, info->stack_end, precise);
4700                         else if (!precise)
4701                                 conservatively_pin_objects_from (info->stack_start, info->stack_end, start_nursery, end_nursery, PIN_TYPE_STACK);
4702
4703                         if (!precise)
4704                                 conservatively_pin_objects_from (info->stopped_regs, info->stopped_regs + ARCH_NUM_REGS,
4705                                                 start_nursery, end_nursery, PIN_TYPE_STACK);
4706                 }
4707         }
4708 }
4709
4710 static void
4711 find_pinning_ref_from_thread (char *obj, size_t size)
4712 {
4713         int i;
4714         SgenThreadInfo *info;
4715         char *endobj = obj + size;
4716
4717         for (i = 0; i < THREAD_HASH_SIZE; ++i) {
4718                 for (info = thread_table [i]; info; info = info->next) {
4719                         char **start = (char**)info->stack_start;
4720                         if (info->skip)
4721                                 continue;
4722                         while (start < (char**)info->stack_end) {
4723                                 if (*start >= obj && *start < endobj) {
4724                                         DEBUG (0, fprintf (gc_debug_file, "Object %p referenced in thread %p (id %p) at %p, stack: %p-%p\n", obj, info, (gpointer)info->id, start, info->stack_start, info->stack_end));
4725                                 }
4726                                 start++;
4727                         }
4728
4729                         /* FIXME: check info->stopped_regs */
4730                 }
4731         }
4732 }
4733
4734 static gboolean
4735 ptr_on_stack (void *ptr)
4736 {
4737         gpointer stack_start = &stack_start;
4738         SgenThreadInfo *info = mono_sgen_thread_info_lookup (ARCH_GET_THREAD ());
4739
4740         if (ptr >= stack_start && ptr < (gpointer)info->stack_end)
4741                 return TRUE;
4742         return FALSE;
4743 }
4744
4745 static mword*
4746 handle_remset (mword *p, void *start_nursery, void *end_nursery, gboolean global, GrayQueue *queue)
4747 {
4748         void **ptr;
4749         mword count;
4750         mword desc;
4751
4752         if (global)
4753                 HEAVY_STAT (++stat_global_remsets_processed);
4754
4755         /* FIXME: exclude stack locations */
4756         switch ((*p) & REMSET_TYPE_MASK) {
4757         case REMSET_LOCATION:
4758                 ptr = (void**)(*p);
4759                 //__builtin_prefetch (ptr);
4760                 if (((void*)ptr < start_nursery || (void*)ptr >= end_nursery)) {
4761                         gpointer old = *ptr;
4762                         major.copy_object (ptr, queue);
4763                         DEBUG (9, fprintf (gc_debug_file, "Overwrote remset at %p with %p\n", ptr, *ptr));
4764                         if (old)
4765                                 binary_protocol_ptr_update (ptr, old, *ptr, (gpointer)LOAD_VTABLE (*ptr), safe_object_get_size (*ptr));
4766                         if (!global && *ptr >= start_nursery && *ptr < end_nursery) {
4767                                 /*
4768                                  * If the object is pinned, each reference to it from nonpinned objects
4769                                  * becomes part of the global remset, which can grow very large.
4770                                  */
4771                                 DEBUG (9, fprintf (gc_debug_file, "Add to global remset because of pinning %p (%p %s)\n", ptr, *ptr, safe_name (*ptr)));
4772                                 mono_sgen_add_to_global_remset (ptr);
4773                         }
4774                 } else {
4775                         DEBUG (9, fprintf (gc_debug_file, "Skipping remset at %p holding %p\n", ptr, *ptr));
4776                 }
4777                 return p + 1;
4778         case REMSET_RANGE:
4779                 ptr = (void**)(*p & ~REMSET_TYPE_MASK);
4780                 if (((void*)ptr >= start_nursery && (void*)ptr < end_nursery))
4781                         return p + 2;
4782                 count = p [1];
4783                 while (count-- > 0) {
4784                         major.copy_object (ptr, queue);
4785                         DEBUG (9, fprintf (gc_debug_file, "Overwrote remset at %p with %p (count: %d)\n", ptr, *ptr, (int)count));
4786                         if (!global && *ptr >= start_nursery && *ptr < end_nursery)
4787                                 mono_sgen_add_to_global_remset (ptr);
4788                         ++ptr;
4789                 }
4790                 return p + 2;
4791         case REMSET_OBJECT:
4792                 ptr = (void**)(*p & ~REMSET_TYPE_MASK);
4793                 if (((void*)ptr >= start_nursery && (void*)ptr < end_nursery))
4794                         return p + 1;
4795                 major.minor_scan_object ((char*)ptr, queue);
4796                 return p + 1;
4797         case REMSET_VTYPE: {
4798                 ptr = (void**)(*p & ~REMSET_TYPE_MASK);
4799                 if (((void*)ptr >= start_nursery && (void*)ptr < end_nursery))
4800                         return p + 3;
4801                 desc = p [1];
4802                 count = p [2];
4803                 while (count-- > 0)
4804                         ptr = (void**) major.minor_scan_vtype ((char*)ptr, desc, start_nursery, end_nursery, queue);
4805                 return p + 3;
4806         }
4807         default:
4808                 g_assert_not_reached ();
4809         }
4810         return NULL;
4811 }
4812
4813 #ifdef HEAVY_STATISTICS
4814 static mword*
4815 collect_store_remsets (RememberedSet *remset, mword *bumper)
4816 {
4817         mword *p = remset->data;
4818         mword last = 0;
4819         mword last1 = 0;
4820         mword last2 = 0;
4821
4822         while (p < remset->store_next) {
4823                 switch ((*p) & REMSET_TYPE_MASK) {
4824                 case REMSET_LOCATION:
4825                         *bumper++ = *p;
4826                         if (*p == last)
4827                                 ++stat_saved_remsets_1;
4828                         last = *p;
4829                         if (*p == last1 || *p == last2) {
4830                                 ++stat_saved_remsets_2;
4831                         } else {
4832                                 last2 = last1;
4833                                 last1 = *p;
4834                         }
4835                         p += 1;
4836                         break;
4837                 case REMSET_RANGE:
4838                         p += 2;
4839                         break;
4840                 case REMSET_OBJECT:
4841                         p += 1;
4842                         break;
4843                 case REMSET_VTYPE:
4844                         p += 3;
4845                         break;
4846                 default:
4847                         g_assert_not_reached ();
4848                 }
4849         }
4850
4851         return bumper;
4852 }
4853
4854 static void
4855 remset_stats (void)
4856 {
4857         RememberedSet *remset;
4858         int size = 0;
4859         SgenThreadInfo *info;
4860         int i;
4861         mword *addresses, *bumper, *p, *r;
4862
4863         for (i = 0; i < THREAD_HASH_SIZE; ++i) {
4864                 for (info = thread_table [i]; info; info = info->next) {
4865                         for (remset = info->remset; remset; remset = remset->next)
4866                                 size += remset->store_next - remset->data;
4867                 }
4868         }
4869         for (remset = freed_thread_remsets; remset; remset = remset->next)
4870                 size += remset->store_next - remset->data;
4871         for (remset = global_remset; remset; remset = remset->next)
4872                 size += remset->store_next - remset->data;
4873
4874         bumper = addresses = mono_sgen_alloc_internal_dynamic (sizeof (mword) * size, INTERNAL_MEM_STATISTICS);
4875
4876         for (i = 0; i < THREAD_HASH_SIZE; ++i) {
4877                 for (info = thread_table [i]; info; info = info->next) {
4878                         for (remset = info->remset; remset; remset = remset->next)
4879                                 bumper = collect_store_remsets (remset, bumper);
4880                 }
4881         }
4882         for (remset = global_remset; remset; remset = remset->next)
4883                 bumper = collect_store_remsets (remset, bumper);
4884         for (remset = freed_thread_remsets; remset; remset = remset->next)
4885                 bumper = collect_store_remsets (remset, bumper);
4886
4887         g_assert (bumper <= addresses + size);
4888
4889         stat_store_remsets += bumper - addresses;
4890
4891         sort_addresses ((void**)addresses, bumper - addresses);
4892         p = addresses;
4893         r = addresses + 1;
4894         while (r < bumper) {
4895                 if (*r != *p)
4896                         *++p = *r;
4897                 ++r;
4898         }
4899
4900         stat_store_remsets_unique += p - addresses;
4901
4902         mono_sgen_free_internal_dynamic (addresses, sizeof (mword) * size, INTERNAL_MEM_STATISTICS);
4903 }
4904 #endif
4905
4906 static void
4907 clear_thread_store_remset_buffer (SgenThreadInfo *info)
4908 {
4909         *info->store_remset_buffer_index_addr = 0;
4910         memset (*info->store_remset_buffer_addr, 0, sizeof (gpointer) * STORE_REMSET_BUFFER_SIZE);
4911 }
4912
4913 static size_t
4914 remset_byte_size (RememberedSet *remset)
4915 {
4916         return sizeof (RememberedSet) + (remset->end_set - remset->data) * sizeof (gpointer);
4917 }
4918
4919 static void
4920 scan_from_remsets (void *start_nursery, void *end_nursery, GrayQueue *queue)
4921 {
4922         int i;
4923         SgenThreadInfo *info;
4924         RememberedSet *remset;
4925         GenericStoreRememberedSet *store_remset;
4926         mword *p, *next_p, *store_pos;
4927
4928 #ifdef HEAVY_STATISTICS
4929         remset_stats ();
4930 #endif
4931
4932         /* the global one */
4933         for (remset = global_remset; remset; remset = remset->next) {
4934                 DEBUG (4, fprintf (gc_debug_file, "Scanning global remset range: %p-%p, size: %td\n", remset->data, remset->store_next, remset->store_next - remset->data));
4935                 store_pos = remset->data;
4936                 for (p = remset->data; p < remset->store_next; p = next_p) {
4937                         void **ptr = (void**)p [0];
4938
4939                         /*Ignore previously processed remset.*/
4940                         if (!global_remset_location_was_not_added (ptr)) {
4941                                 next_p = p + 1;
4942                                 continue;
4943                         }
4944
4945                         next_p = handle_remset (p, start_nursery, end_nursery, TRUE, queue);
4946
4947                         /* 
4948                          * Clear global remsets of locations which no longer point to the 
4949                          * nursery. Otherwise, they could grow indefinitely between major 
4950                          * collections.
4951                          *
4952                          * Since all global remsets are location remsets, we don't need to unmask the pointer.
4953                          */
4954                         if (ptr_in_nursery (*ptr)) {
4955                                 *store_pos ++ = p [0];
4956                                 HEAVY_STAT (++stat_global_remsets_readded);
4957                         }
4958                 }
4959
4960                 /* Truncate the remset */
4961                 remset->store_next = store_pos;
4962         }
4963
4964         /* the generic store ones */
4965         store_remset = generic_store_remsets;
4966         while (store_remset) {
4967                 GenericStoreRememberedSet *next = store_remset->next;
4968
4969                 for (i = 0; i < STORE_REMSET_BUFFER_SIZE - 1; ++i) {
4970                         gpointer addr = store_remset->data [i];
4971                         if (addr)
4972                                 handle_remset ((mword*)&addr, start_nursery, end_nursery, FALSE, queue);
4973                 }
4974
4975                 mono_sgen_free_internal (store_remset, INTERNAL_MEM_STORE_REMSET);
4976
4977                 store_remset = next;
4978         }
4979         generic_store_remsets = NULL;
4980
4981         /* the per-thread ones */
4982         for (i = 0; i < THREAD_HASH_SIZE; ++i) {
4983                 for (info = thread_table [i]; info; info = info->next) {
4984                         RememberedSet *next;
4985                         int j;
4986                         for (remset = info->remset; remset; remset = next) {
4987                                 DEBUG (4, fprintf (gc_debug_file, "Scanning remset for thread %p, range: %p-%p, size: %td\n", info, remset->data, remset->store_next, remset->store_next - remset->data));
4988                                 for (p = remset->data; p < remset->store_next;) {
4989                                         p = handle_remset (p, start_nursery, end_nursery, FALSE, queue);
4990                                 }
4991                                 remset->store_next = remset->data;
4992                                 next = remset->next;
4993                                 remset->next = NULL;
4994                                 if (remset != info->remset) {
4995                                         DEBUG (4, fprintf (gc_debug_file, "Freed remset at %p\n", remset->data));
4996                                         mono_sgen_free_internal_dynamic (remset, remset_byte_size (remset), INTERNAL_MEM_REMSET);
4997                                 }
4998                         }
4999                         for (j = 0; j < *info->store_remset_buffer_index_addr; ++j)
5000                                 handle_remset ((mword*)*info->store_remset_buffer_addr + j + 1, start_nursery, end_nursery, FALSE, queue);
5001                         clear_thread_store_remset_buffer (info);
5002                 }
5003         }
5004
5005         /* the freed thread ones */
5006         while (freed_thread_remsets) {
5007                 RememberedSet *next;
5008                 remset = freed_thread_remsets;
5009                 DEBUG (4, fprintf (gc_debug_file, "Scanning remset for freed thread, range: %p-%p, size: %td\n", remset->data, remset->store_next, remset->store_next - remset->data));
5010                 for (p = remset->data; p < remset->store_next;) {
5011                         p = handle_remset (p, start_nursery, end_nursery, FALSE, queue);
5012                 }
5013                 next = remset->next;
5014                 DEBUG (4, fprintf (gc_debug_file, "Freed remset at %p\n", remset->data));
5015                 mono_sgen_free_internal_dynamic (remset, remset_byte_size (remset), INTERNAL_MEM_REMSET);
5016                 freed_thread_remsets = next;
5017         }
5018 }
5019
5020 /*
5021  * Clear the info in the remembered sets: we're doing a major collection, so
5022  * the per-thread ones are not needed and the global ones will be reconstructed
5023  * during the copy.
5024  */
5025 static void
5026 clear_remsets (void)
5027 {
5028         int i;
5029         SgenThreadInfo *info;
5030         RememberedSet *remset, *next;
5031
5032         /* the global list */
5033         for (remset = global_remset; remset; remset = next) {
5034                 remset->store_next = remset->data;
5035                 next = remset->next;
5036                 remset->next = NULL;
5037                 if (remset != global_remset) {
5038                         DEBUG (4, fprintf (gc_debug_file, "Freed remset at %p\n", remset->data));
5039                         mono_sgen_free_internal_dynamic (remset, remset_byte_size (remset), INTERNAL_MEM_REMSET);
5040                 }
5041         }
5042         /* the generic store ones */
5043         while (generic_store_remsets) {
5044                 GenericStoreRememberedSet *gs_next = generic_store_remsets->next;
5045                 mono_sgen_free_internal (generic_store_remsets, INTERNAL_MEM_STORE_REMSET);
5046                 generic_store_remsets = gs_next;
5047         }
5048         /* the per-thread ones */
5049         for (i = 0; i < THREAD_HASH_SIZE; ++i) {
5050                 for (info = thread_table [i]; info; info = info->next) {
5051                         for (remset = info->remset; remset; remset = next) {
5052                                 remset->store_next = remset->data;
5053                                 next = remset->next;
5054                                 remset->next = NULL;
5055                                 if (remset != info->remset) {
5056                                         DEBUG (3, fprintf (gc_debug_file, "Freed remset at %p\n", remset->data));
5057                                         mono_sgen_free_internal_dynamic (remset, remset_byte_size (remset), INTERNAL_MEM_REMSET);
5058                                 }
5059                         }
5060                         clear_thread_store_remset_buffer (info);
5061                 }
5062         }
5063
5064         /* the freed thread ones */
5065         while (freed_thread_remsets) {
5066                 next = freed_thread_remsets->next;
5067                 DEBUG (4, fprintf (gc_debug_file, "Freed remset at %p\n", freed_thread_remsets->data));
5068                 mono_sgen_free_internal_dynamic (freed_thread_remsets, remset_byte_size (freed_thread_remsets), INTERNAL_MEM_REMSET);
5069                 freed_thread_remsets = next;
5070         }
5071 }
5072
5073 /*
5074  * Clear the thread local TLAB variables for all threads.
5075  */
5076 static void
5077 clear_tlabs (void)
5078 {
5079         SgenThreadInfo *info;
5080         int i;
5081
5082         for (i = 0; i < THREAD_HASH_SIZE; ++i) {
5083                 for (info = thread_table [i]; info; info = info->next) {
5084                         /* A new TLAB will be allocated when the thread does its first allocation */
5085                         *info->tlab_start_addr = NULL;
5086                         *info->tlab_next_addr = NULL;
5087                         *info->tlab_temp_end_addr = NULL;
5088                         *info->tlab_real_end_addr = NULL;
5089                 }
5090         }
5091 }
5092
5093 /* LOCKING: assumes the GC lock is held */
5094 static SgenThreadInfo*
5095 gc_register_current_thread (void *addr)
5096 {
5097         int hash;
5098         SgenThreadInfo* info = malloc (sizeof (SgenThreadInfo));
5099 #ifndef HAVE_KW_THREAD
5100         SgenThreadInfo *__thread_info__ = info;
5101 #endif
5102
5103         if (!info)
5104                 return NULL;
5105
5106         memset (info, 0, sizeof (SgenThreadInfo));
5107 #ifndef HAVE_KW_THREAD
5108         info->tlab_start = info->tlab_next = info->tlab_temp_end = info->tlab_real_end = NULL;
5109
5110         g_assert (!pthread_getspecific (thread_info_key));
5111         pthread_setspecific (thread_info_key, info);
5112 #else
5113         thread_info = info;
5114 #endif
5115
5116         info->id = ARCH_GET_THREAD ();
5117         info->stop_count = -1;
5118         info->skip = 0;
5119         info->signal = 0;
5120         info->stack_start = NULL;
5121         info->tlab_start_addr = &TLAB_START;
5122         info->tlab_next_addr = &TLAB_NEXT;
5123         info->tlab_temp_end_addr = &TLAB_TEMP_END;
5124         info->tlab_real_end_addr = &TLAB_REAL_END;
5125         info->store_remset_buffer_addr = &STORE_REMSET_BUFFER;
5126         info->store_remset_buffer_index_addr = &STORE_REMSET_BUFFER_INDEX;
5127         info->stopped_ip = NULL;
5128         info->stopped_domain = NULL;
5129         info->stopped_regs = NULL;
5130
5131         binary_protocol_thread_register ((gpointer)info->id);
5132
5133 #ifdef HAVE_KW_THREAD
5134         tlab_next_addr = &tlab_next;
5135         store_remset_buffer_index_addr = &store_remset_buffer_index;
5136 #endif
5137
5138         /* try to get it with attributes first */
5139 #if defined(HAVE_PTHREAD_GETATTR_NP) && defined(HAVE_PTHREAD_ATTR_GETSTACK)
5140         {
5141                 size_t size;
5142                 void *sstart;
5143                 pthread_attr_t attr;
5144                 pthread_getattr_np (pthread_self (), &attr);
5145                 pthread_attr_getstack (&attr, &sstart, &size);
5146                 info->stack_start_limit = sstart;
5147                 info->stack_end = (char*)sstart + size;
5148                 pthread_attr_destroy (&attr);
5149         }
5150 #elif defined(HAVE_PTHREAD_GET_STACKSIZE_NP) && defined(HAVE_PTHREAD_GET_STACKADDR_NP)
5151                  info->stack_end = (char*)pthread_get_stackaddr_np (pthread_self ());
5152                  info->stack_start_limit = (char*)info->stack_end - pthread_get_stacksize_np (pthread_self ());
5153 #else
5154         {
5155                 /* FIXME: we assume the stack grows down */
5156                 gsize stack_bottom = (gsize)addr;
5157                 stack_bottom += 4095;
5158                 stack_bottom &= ~4095;
5159                 info->stack_end = (char*)stack_bottom;
5160         }
5161 #endif
5162
5163 #ifdef HAVE_KW_THREAD
5164         stack_end = info->stack_end;
5165 #endif
5166
5167         /* hash into the table */
5168         hash = HASH_PTHREAD_T (info->id) % THREAD_HASH_SIZE;
5169         info->next = thread_table [hash];
5170         thread_table [hash] = info;
5171
5172         info->remset = alloc_remset (DEFAULT_REMSET_SIZE, info);
5173         pthread_setspecific (remembered_set_key, info->remset);
5174 #ifdef HAVE_KW_THREAD
5175         remembered_set = info->remset;
5176 #endif
5177
5178         STORE_REMSET_BUFFER = mono_sgen_alloc_internal (INTERNAL_MEM_STORE_REMSET);
5179         STORE_REMSET_BUFFER_INDEX = 0;
5180
5181         DEBUG (3, fprintf (gc_debug_file, "registered thread %p (%p) (hash: %d)\n", info, (gpointer)info->id, hash));
5182
5183         if (gc_callbacks.thread_attach_func)
5184                 info->runtime_data = gc_callbacks.thread_attach_func ();
5185
5186         return info;
5187 }
5188
5189 static void
5190 add_generic_store_remset_from_buffer (gpointer *buffer)
5191 {
5192         GenericStoreRememberedSet *remset = mono_sgen_alloc_internal (INTERNAL_MEM_STORE_REMSET);
5193         memcpy (remset->data, buffer + 1, sizeof (gpointer) * (STORE_REMSET_BUFFER_SIZE - 1));
5194         remset->next = generic_store_remsets;
5195         generic_store_remsets = remset;
5196 }
5197
5198 static void
5199 unregister_current_thread (void)
5200 {
5201         int hash;
5202         SgenThreadInfo *prev = NULL;
5203         SgenThreadInfo *p;
5204         RememberedSet *rset;
5205         ARCH_THREAD_TYPE id = ARCH_GET_THREAD ();
5206
5207         binary_protocol_thread_unregister ((gpointer)id);
5208
5209         hash = HASH_PTHREAD_T (id) % THREAD_HASH_SIZE;
5210         p = thread_table [hash];
5211         assert (p);
5212         DEBUG (3, fprintf (gc_debug_file, "unregister thread %p (%p)\n", p, (gpointer)p->id));
5213         while (!ARCH_THREAD_EQUALS (p->id, id)) {
5214                 prev = p;
5215                 p = p->next;
5216         }
5217         if (prev == NULL) {
5218                 thread_table [hash] = p->next;
5219         } else {
5220                 prev->next = p->next;
5221         }
5222         if (p->remset) {
5223                 if (freed_thread_remsets) {
5224                         for (rset = p->remset; rset->next; rset = rset->next)
5225                                 ;
5226                         rset->next = freed_thread_remsets;
5227                         freed_thread_remsets = p->remset;
5228                 } else {
5229                         freed_thread_remsets = p->remset;
5230                 }
5231         }
5232         if (*p->store_remset_buffer_index_addr)
5233                 add_generic_store_remset_from_buffer (*p->store_remset_buffer_addr);
5234         mono_sgen_free_internal (*p->store_remset_buffer_addr, INTERNAL_MEM_STORE_REMSET);
5235         free (p);
5236 }
5237
5238 static void
5239 unregister_thread (void *k)
5240 {
5241         g_assert (!mono_domain_get ());
5242         LOCK_GC;
5243         unregister_current_thread ();
5244         UNLOCK_GC;
5245 }
5246
5247 gboolean
5248 mono_gc_register_thread (void *baseptr)
5249 {
5250         SgenThreadInfo *info;
5251
5252         LOCK_GC;
5253         init_stats ();
5254         info = mono_sgen_thread_info_lookup (ARCH_GET_THREAD ());
5255         if (info == NULL)
5256                 info = gc_register_current_thread (baseptr);
5257         UNLOCK_GC;
5258         return info != NULL;
5259 }
5260
5261 #if USE_PTHREAD_INTERCEPT
5262
5263 typedef struct {
5264         void *(*start_routine) (void *);
5265         void *arg;
5266         int flags;
5267         MonoSemType registered;
5268 } SgenThreadStartInfo;
5269
5270 static void*
5271 gc_start_thread (void *arg)
5272 {
5273         SgenThreadStartInfo *start_info = arg;
5274         SgenThreadInfo* info;
5275         void *t_arg = start_info->arg;
5276         void *(*start_func) (void*) = start_info->start_routine;
5277         void *result;
5278         int post_result;
5279
5280         LOCK_GC;
5281         info = gc_register_current_thread (&result);
5282         UNLOCK_GC;
5283         post_result = MONO_SEM_POST (&(start_info->registered));
5284         g_assert (!post_result);
5285         result = start_func (t_arg);
5286         g_assert (!mono_domain_get ());
5287         /*
5288          * this is done by the pthread key dtor
5289         LOCK_GC;
5290         unregister_current_thread ();
5291         UNLOCK_GC;
5292         */
5293
5294         return result;
5295 }
5296
5297 int
5298 mono_gc_pthread_create (pthread_t *new_thread, const pthread_attr_t *attr, void *(*start_routine)(void *), void *arg)
5299 {
5300         SgenThreadStartInfo *start_info;
5301         int result;
5302
5303         start_info = malloc (sizeof (SgenThreadStartInfo));
5304         if (!start_info)
5305                 return ENOMEM;
5306         MONO_SEM_INIT (&(start_info->registered), 0);
5307         start_info->arg = arg;
5308         start_info->start_routine = start_routine;
5309
5310         result = pthread_create (new_thread, attr, gc_start_thread, start_info);
5311         if (result == 0) {
5312                 while (MONO_SEM_WAIT (&(start_info->registered)) != 0) {
5313                         /*if (EINTR != errno) ABORT("sem_wait failed"); */
5314                 }
5315         }
5316         MONO_SEM_DESTROY (&(start_info->registered));
5317         free (start_info);
5318         return result;
5319 }
5320
5321 int
5322 mono_gc_pthread_join (pthread_t thread, void **retval)
5323 {
5324         return pthread_join (thread, retval);
5325 }
5326
5327 int
5328 mono_gc_pthread_detach (pthread_t thread)
5329 {
5330         return pthread_detach (thread);
5331 }
5332
5333 #endif /* USE_PTHREAD_INTERCEPT */
5334
5335 /*
5336  * ######################################################################
5337  * ########  Write barriers
5338  * ######################################################################
5339  */
5340
5341 static RememberedSet*
5342 alloc_remset (int size, gpointer id) {
5343         RememberedSet* res = mono_sgen_alloc_internal_dynamic (sizeof (RememberedSet) + (size * sizeof (gpointer)), INTERNAL_MEM_REMSET);
5344         res->store_next = res->data;
5345         res->end_set = res->data + size;
5346         res->next = NULL;
5347         DEBUG (4, fprintf (gc_debug_file, "Allocated remset size %d at %p for %p\n", size, res->data, id));
5348         return res;
5349 }
5350
5351 /*
5352  * Note: the write barriers first do the needed GC work and then do the actual store:
5353  * this way the value is visible to the conservative GC scan after the write barrier
5354  * itself. If a GC interrupts the barrier in the middle, value will be kept alive by
5355  * the conservative scan, otherwise by the remembered set scan.
5356  */
5357 void
5358 mono_gc_wbarrier_set_field (MonoObject *obj, gpointer field_ptr, MonoObject* value)
5359 {
5360         RememberedSet *rs;
5361         TLAB_ACCESS_INIT;
5362         HEAVY_STAT (++stat_wbarrier_set_field);
5363         if (ptr_in_nursery (field_ptr)) {
5364                 *(void**)field_ptr = value;
5365                 return;
5366         }
5367         DEBUG (8, fprintf (gc_debug_file, "Adding remset at %p\n", field_ptr));
5368         LOCK_GC;
5369         rs = REMEMBERED_SET;
5370         if (rs->store_next < rs->end_set) {
5371                 *(rs->store_next++) = (mword)field_ptr;
5372                 *(void**)field_ptr = value;
5373                 UNLOCK_GC;
5374                 return;
5375         }
5376         rs = alloc_remset (rs->end_set - rs->data, (void*)1);
5377         rs->next = REMEMBERED_SET;
5378         REMEMBERED_SET = rs;
5379 #ifdef HAVE_KW_THREAD
5380         mono_sgen_thread_info_lookup (ARCH_GET_THREAD ())->remset = rs;
5381 #endif
5382         *(rs->store_next++) = (mword)field_ptr;
5383         *(void**)field_ptr = value;
5384         UNLOCK_GC;
5385 }
5386
5387 void
5388 mono_gc_wbarrier_set_arrayref (MonoArray *arr, gpointer slot_ptr, MonoObject* value)
5389 {
5390         RememberedSet *rs;
5391         TLAB_ACCESS_INIT;
5392         HEAVY_STAT (++stat_wbarrier_set_arrayref);
5393         if (ptr_in_nursery (slot_ptr)) {
5394                 *(void**)slot_ptr = value;
5395                 return;
5396         }
5397         DEBUG (8, fprintf (gc_debug_file, "Adding remset at %p\n", slot_ptr));
5398         LOCK_GC;
5399         rs = REMEMBERED_SET;
5400         if (rs->store_next < rs->end_set) {
5401                 *(rs->store_next++) = (mword)slot_ptr;
5402                 *(void**)slot_ptr = value;
5403                 UNLOCK_GC;
5404                 return;
5405         }
5406         rs = alloc_remset (rs->end_set - rs->data, (void*)1);
5407         rs->next = REMEMBERED_SET;
5408         REMEMBERED_SET = rs;
5409 #ifdef HAVE_KW_THREAD
5410         mono_sgen_thread_info_lookup (ARCH_GET_THREAD ())->remset = rs;
5411 #endif
5412         *(rs->store_next++) = (mword)slot_ptr;
5413         *(void**)slot_ptr = value;
5414         UNLOCK_GC;
5415 }
5416
5417 void
5418 mono_gc_wbarrier_arrayref_copy (gpointer dest_ptr, gpointer src_ptr, int count)
5419 {
5420         RememberedSet *rs;
5421         TLAB_ACCESS_INIT;
5422         HEAVY_STAT (++stat_wbarrier_arrayref_copy);
5423         LOCK_GC;
5424         memmove (dest_ptr, src_ptr, count * sizeof (gpointer));
5425         if (ptr_in_nursery (dest_ptr)) {
5426                 UNLOCK_GC;
5427                 return;
5428         }
5429         rs = REMEMBERED_SET;
5430         DEBUG (8, fprintf (gc_debug_file, "Adding remset at %p, %d\n", dest_ptr, count));
5431         if (rs->store_next + 1 < rs->end_set) {
5432                 *(rs->store_next++) = (mword)dest_ptr | REMSET_RANGE;
5433                 *(rs->store_next++) = count;
5434                 UNLOCK_GC;
5435                 return;
5436         }
5437         rs = alloc_remset (rs->end_set - rs->data, (void*)1);
5438         rs->next = REMEMBERED_SET;
5439         REMEMBERED_SET = rs;
5440 #ifdef HAVE_KW_THREAD
5441         mono_sgen_thread_info_lookup (ARCH_GET_THREAD ())->remset = rs;
5442 #endif
5443         *(rs->store_next++) = (mword)dest_ptr | REMSET_RANGE;
5444         *(rs->store_next++) = count;
5445         UNLOCK_GC;
5446 }
5447
5448 static char *found_obj;
5449
5450 static void
5451 find_object_for_ptr_callback (char *obj, size_t size, char *ptr)
5452 {
5453         if (ptr >= obj && ptr < obj + size) {
5454                 g_assert (!found_obj);
5455                 found_obj = obj;
5456         }
5457 }
5458
5459 /* for use in the debugger */
5460 char* find_object_for_ptr (char *ptr);
5461 char*
5462 find_object_for_ptr (char *ptr)
5463 {
5464         LOSObject *bigobj;
5465
5466         if (ptr >= nursery_section->data && ptr < nursery_section->end_data) {
5467                 found_obj = NULL;
5468                 mono_sgen_scan_area_with_callback (nursery_section->data, nursery_section->end_data,
5469                                 (IterateObjectCallbackFunc)find_object_for_ptr_callback, ptr);
5470                 if (found_obj)
5471                         return found_obj;
5472         }
5473
5474         for (bigobj = los_object_list; bigobj; bigobj = bigobj->next) {
5475                 if (ptr >= bigobj->data && ptr < bigobj->data + bigobj->size)
5476                         return bigobj->data;
5477         }
5478
5479         /*
5480          * Very inefficient, but this is debugging code, supposed to
5481          * be called from gdb, so we don't care.
5482          */
5483         found_obj = NULL;
5484         major.iterate_objects (TRUE, TRUE, (IterateObjectCallbackFunc)find_object_for_ptr_callback, ptr);
5485         return found_obj;
5486 }
5487
5488 static void
5489 evacuate_remset_buffer (void)
5490 {
5491         gpointer *buffer;
5492         TLAB_ACCESS_INIT;
5493
5494         buffer = STORE_REMSET_BUFFER;
5495
5496         add_generic_store_remset_from_buffer (buffer);
5497         memset (buffer, 0, sizeof (gpointer) * STORE_REMSET_BUFFER_SIZE);
5498
5499         STORE_REMSET_BUFFER_INDEX = 0;
5500 }
5501
5502 void
5503 mono_gc_wbarrier_generic_nostore (gpointer ptr)
5504 {
5505         gpointer *buffer;
5506         int index;
5507         TLAB_ACCESS_INIT;
5508
5509         HEAVY_STAT (++stat_wbarrier_generic_store);
5510
5511 #ifdef XDOMAIN_CHECKS_IN_WBARRIER
5512         /* FIXME: ptr_in_heap must be called with the GC lock held */
5513         if (xdomain_checks && *(MonoObject**)ptr && ptr_in_heap (ptr)) {
5514                 char *start = find_object_for_ptr (ptr);
5515                 MonoObject *value = *(MonoObject**)ptr;
5516                 LOCK_GC;
5517                 g_assert (start);
5518                 if (start) {
5519                         MonoObject *obj = (MonoObject*)start;
5520                         if (obj->vtable->domain != value->vtable->domain)
5521                                 g_assert (is_xdomain_ref_allowed (ptr, start, obj->vtable->domain));
5522                 }
5523                 UNLOCK_GC;
5524         }
5525 #endif
5526
5527         LOCK_GC;
5528
5529         if (*(gpointer*)ptr)
5530                 binary_protocol_wbarrier (ptr, *(gpointer*)ptr, (gpointer)LOAD_VTABLE (*(gpointer*)ptr));
5531
5532         if (ptr_in_nursery (ptr) || ptr_on_stack (ptr) || !ptr_in_nursery (*(gpointer*)ptr)) {
5533                 DEBUG (8, fprintf (gc_debug_file, "Skipping remset at %p\n", ptr));
5534                 UNLOCK_GC;
5535                 return;
5536         }
5537
5538         buffer = STORE_REMSET_BUFFER;
5539         index = STORE_REMSET_BUFFER_INDEX;
5540         /* This simple optimization eliminates a sizable portion of
5541            entries.  Comparing it to the last but one entry as well
5542            doesn't eliminate significantly more entries. */
5543         if (buffer [index] == ptr) {
5544                 UNLOCK_GC;
5545                 return;
5546         }
5547
5548         DEBUG (8, fprintf (gc_debug_file, "Adding remset at %p\n", ptr));
5549         HEAVY_STAT (++stat_wbarrier_generic_store_remset);
5550
5551         ++index;
5552         if (index >= STORE_REMSET_BUFFER_SIZE) {
5553                 evacuate_remset_buffer ();
5554                 index = STORE_REMSET_BUFFER_INDEX;
5555                 g_assert (index == 0);
5556                 ++index;
5557         }
5558         buffer [index] = ptr;
5559         STORE_REMSET_BUFFER_INDEX = index;
5560
5561         UNLOCK_GC;
5562 }
5563
5564 void
5565 mono_gc_wbarrier_generic_store (gpointer ptr, MonoObject* value)
5566 {
5567         DEBUG (8, fprintf (gc_debug_file, "Wbarrier store at %p to %p (%s)\n", ptr, value, value ? safe_name (value) : "null"));
5568         *(void**)ptr = value;
5569         if (ptr_in_nursery (value))
5570                 mono_gc_wbarrier_generic_nostore (ptr);
5571 }
5572
5573 void mono_gc_wbarrier_value_copy_bitmap (gpointer _dest, gpointer _src, int size, unsigned bitmap)
5574 {
5575         mword *dest = _dest;
5576         mword *src = _src;
5577
5578         while (size) {
5579                 if (bitmap & 0x1)
5580                         mono_gc_wbarrier_generic_store (dest, (MonoObject*)*src);
5581                 else
5582                         *dest = *src;
5583                 ++src;
5584                 ++dest;
5585                 size -= SIZEOF_VOID_P;
5586                 bitmap >>= 1;
5587         }
5588 }
5589
5590
5591 void
5592 mono_gc_wbarrier_value_copy (gpointer dest, gpointer src, int count, MonoClass *klass)
5593 {
5594         RememberedSet *rs;
5595         TLAB_ACCESS_INIT;
5596         HEAVY_STAT (++stat_wbarrier_value_copy);
5597         g_assert (klass->valuetype);
5598         LOCK_GC;
5599         memmove (dest, src, count * mono_class_value_size (klass, NULL));
5600         rs = REMEMBERED_SET;
5601         if (ptr_in_nursery (dest) || ptr_on_stack (dest) || !klass->has_references) {
5602                 UNLOCK_GC;
5603                 return;
5604         }
5605         g_assert (klass->gc_descr_inited);
5606         DEBUG (8, fprintf (gc_debug_file, "Adding value remset at %p, count %d, descr %p for class %s (%p)\n", dest, count, klass->gc_descr, klass->name, klass));
5607
5608         if (rs->store_next + 3 < rs->end_set) {
5609                 *(rs->store_next++) = (mword)dest | REMSET_VTYPE;
5610                 *(rs->store_next++) = (mword)klass->gc_descr;
5611                 *(rs->store_next++) = (mword)count;
5612                 UNLOCK_GC;
5613                 return;
5614         }
5615         rs = alloc_remset (rs->end_set - rs->data, (void*)1);
5616         rs->next = REMEMBERED_SET;
5617         REMEMBERED_SET = rs;
5618 #ifdef HAVE_KW_THREAD
5619         mono_sgen_thread_info_lookup (ARCH_GET_THREAD ())->remset = rs;
5620 #endif
5621         *(rs->store_next++) = (mword)dest | REMSET_VTYPE;
5622         *(rs->store_next++) = (mword)klass->gc_descr;
5623         *(rs->store_next++) = (mword)count;
5624         UNLOCK_GC;
5625 }
5626
5627 /**
5628  * mono_gc_wbarrier_object_copy:
5629  *
5630  * Write barrier to call when obj is the result of a clone or copy of an object.
5631  */
5632 void
5633 mono_gc_wbarrier_object_copy (MonoObject* obj, MonoObject *src)
5634 {
5635         RememberedSet *rs;
5636         int size;
5637
5638         TLAB_ACCESS_INIT;
5639         HEAVY_STAT (++stat_wbarrier_object_copy);
5640         rs = REMEMBERED_SET;
5641         DEBUG (6, fprintf (gc_debug_file, "Adding object remset for %p\n", obj));
5642         size = mono_object_class (obj)->instance_size;
5643         LOCK_GC;
5644         /* do not copy the sync state */
5645         memcpy ((char*)obj + sizeof (MonoObject), (char*)src + sizeof (MonoObject),
5646                         size - sizeof (MonoObject));
5647         if (ptr_in_nursery (obj) || ptr_on_stack (obj)) {
5648                 UNLOCK_GC;
5649                 return;
5650         }
5651         if (rs->store_next < rs->end_set) {
5652                 *(rs->store_next++) = (mword)obj | REMSET_OBJECT;
5653                 UNLOCK_GC;
5654                 return;
5655         }
5656         rs = alloc_remset (rs->end_set - rs->data, (void*)1);
5657         rs->next = REMEMBERED_SET;
5658         REMEMBERED_SET = rs;
5659 #ifdef HAVE_KW_THREAD
5660         mono_sgen_thread_info_lookup (ARCH_GET_THREAD ())->remset = rs;
5661 #endif
5662         *(rs->store_next++) = (mword)obj | REMSET_OBJECT;
5663         UNLOCK_GC;
5664 }
5665
5666 /*
5667  * ######################################################################
5668  * ########  Collector debugging
5669  * ######################################################################
5670  */
5671
5672 const char*descriptor_types [] = {
5673         "run_length",
5674         "small_bitmap",
5675         "string",
5676         "complex",
5677         "vector",
5678         "array",
5679         "large_bitmap",
5680         "complex_arr"
5681 };
5682
5683 void
5684 describe_ptr (char *ptr)
5685 {
5686         MonoVTable *vtable;
5687         mword desc;
5688         int type;
5689
5690         if (ptr_in_nursery (ptr)) {
5691                 printf ("Pointer inside nursery.\n");
5692         } else {
5693                 if (major.ptr_is_in_non_pinned_space (ptr)) {
5694                         printf ("Pointer inside oldspace.\n");
5695                 } else if (major.obj_is_from_pinned_alloc (ptr)) {
5696                         printf ("Pointer is inside a pinned chunk.\n");
5697                 } else {
5698                         printf ("Pointer unknown.\n");
5699                         return;
5700                 }
5701         }
5702
5703         if (object_is_pinned (ptr))
5704                 printf ("Object is pinned.\n");
5705
5706         if (object_is_forwarded (ptr))
5707                 printf ("Object is forwared.\n");
5708
5709         // FIXME: Handle pointers to the inside of objects
5710         vtable = (MonoVTable*)LOAD_VTABLE (ptr);
5711
5712         printf ("VTable: %p\n", vtable);
5713         if (vtable == NULL) {
5714                 printf ("VTable is invalid (empty).\n");
5715                 return;
5716         }
5717         if (ptr_in_nursery (vtable)) {
5718                 printf ("VTable is invalid (points inside nursery).\n");
5719                 return;
5720         }
5721         printf ("Class: %s\n", vtable->klass->name);
5722
5723         desc = ((GCVTable*)vtable)->desc;
5724         printf ("Descriptor: %lx\n", (long)desc);
5725
5726         type = desc & 0x7;
5727         printf ("Descriptor type: %d (%s)\n", type, descriptor_types [type]);
5728 }
5729
5730 static mword*
5731 find_in_remset_loc (mword *p, char *addr, gboolean *found)
5732 {
5733         void **ptr;
5734         mword count, desc;
5735         size_t skip_size;
5736
5737         switch ((*p) & REMSET_TYPE_MASK) {
5738         case REMSET_LOCATION:
5739                 if (*p == (mword)addr)
5740                         *found = TRUE;
5741                 return p + 1;
5742         case REMSET_RANGE:
5743                 ptr = (void**)(*p & ~REMSET_TYPE_MASK);
5744                 count = p [1];
5745                 if ((void**)addr >= ptr && (void**)addr < ptr + count)
5746                         *found = TRUE;
5747                 return p + 2;
5748         case REMSET_OBJECT:
5749                 ptr = (void**)(*p & ~REMSET_TYPE_MASK);
5750                 count = safe_object_get_size ((MonoObject*)ptr); 
5751                 count = ALIGN_UP (count);
5752                 count /= sizeof (mword);
5753                 if ((void**)addr >= ptr && (void**)addr < ptr + count)
5754                         *found = TRUE;
5755                 return p + 1;
5756         case REMSET_VTYPE:
5757                 ptr = (void**)(*p & ~REMSET_TYPE_MASK);
5758                 desc = p [1];
5759                 count = p [2];
5760
5761                 switch (desc & 0x7) {
5762                 case DESC_TYPE_RUN_LENGTH:
5763                         OBJ_RUN_LEN_SIZE (skip_size, desc, ptr);
5764                         break;
5765                 case DESC_TYPE_SMALL_BITMAP:
5766                         OBJ_BITMAP_SIZE (skip_size, desc, start);
5767                         break;
5768                 default:
5769                         // FIXME:
5770                         g_assert_not_reached ();
5771                 }
5772
5773                 /* The descriptor includes the size of MonoObject */
5774                 skip_size -= sizeof (MonoObject);
5775                 skip_size *= count;
5776                 if ((void**)addr >= ptr && (void**)addr < ptr + (skip_size / sizeof (gpointer)))
5777                         *found = TRUE;
5778
5779                 return p + 3;
5780         default:
5781                 g_assert_not_reached ();
5782         }
5783         return NULL;
5784 }
5785
5786 /*
5787  * Return whenever ADDR occurs in the remembered sets
5788  */
5789 static gboolean
5790 find_in_remsets (char *addr)
5791 {
5792         int i;
5793         SgenThreadInfo *info;
5794         RememberedSet *remset;
5795         GenericStoreRememberedSet *store_remset;
5796         mword *p;
5797         gboolean found = FALSE;
5798
5799         /* the global one */
5800         for (remset = global_remset; remset; remset = remset->next) {
5801                 DEBUG (4, fprintf (gc_debug_file, "Scanning global remset range: %p-%p, size: %td\n", remset->data, remset->store_next, remset->store_next - remset->data));
5802                 for (p = remset->data; p < remset->store_next;) {
5803                         p = find_in_remset_loc (p, addr, &found);
5804                         if (found)
5805                                 return TRUE;
5806                 }
5807         }
5808
5809         /* the generic store ones */
5810         for (store_remset = generic_store_remsets; store_remset; store_remset = store_remset->next) {
5811                 for (i = 0; i < STORE_REMSET_BUFFER_SIZE - 1; ++i) {
5812                         if (store_remset->data [i] == addr)
5813                                 return TRUE;
5814                 }
5815         }
5816
5817         /* the per-thread ones */
5818         for (i = 0; i < THREAD_HASH_SIZE; ++i) {
5819                 for (info = thread_table [i]; info; info = info->next) {
5820                         int j;
5821                         for (remset = info->remset; remset; remset = remset->next) {
5822                                 DEBUG (4, fprintf (gc_debug_file, "Scanning remset for thread %p, range: %p-%p, size: %td\n", info, remset->data, remset->store_next, remset->store_next - remset->data));
5823                                 for (p = remset->data; p < remset->store_next;) {
5824                                         p = find_in_remset_loc (p, addr, &found);
5825                                         if (found)
5826                                                 return TRUE;
5827                                 }
5828                         }
5829                         for (j = 0; j < *info->store_remset_buffer_index_addr; ++j) {
5830                                 if ((*info->store_remset_buffer_addr) [j + 1] == addr)
5831                                         return TRUE;
5832                         }
5833                 }
5834         }
5835
5836         /* the freed thread ones */
5837         for (remset = freed_thread_remsets; remset; remset = remset->next) {
5838                 DEBUG (4, fprintf (gc_debug_file, "Scanning remset for freed thread, range: %p-%p, size: %td\n", remset->data, remset->store_next, remset->store_next - remset->data));
5839                 for (p = remset->data; p < remset->store_next;) {
5840                         p = find_in_remset_loc (p, addr, &found);
5841                         if (found)
5842                                 return TRUE;
5843                 }
5844         }
5845
5846         return FALSE;
5847 }
5848
5849 static gboolean missing_remsets;
5850
5851 /*
5852  * We let a missing remset slide if the target object is pinned,
5853  * because the store might have happened but the remset not yet added,
5854  * but in that case the target must be pinned.  We might theoretically
5855  * miss some missing remsets this way, but it's very unlikely.
5856  */
5857 #undef HANDLE_PTR
5858 #define HANDLE_PTR(ptr,obj)     do {    \
5859                 if (*(ptr) && (char*)*(ptr) >= nursery_start && (char*)*(ptr) < nursery_next) { \
5860                 if (!find_in_remsets ((char*)(ptr))) { \
5861                 fprintf (gc_debug_file, "Oldspace->newspace reference %p at offset %td in object %p (%s.%s) not found in remsets.\n", *(ptr), (char*)(ptr) - (char*)(obj), (obj), ((MonoObject*)(obj))->vtable->klass->name_space, ((MonoObject*)(obj))->vtable->klass->name); \
5862                 binary_protocol_missing_remset ((obj), (gpointer)LOAD_VTABLE ((obj)), (char*)(ptr) - (char*)(obj), *(ptr), (gpointer)LOAD_VTABLE(*(ptr)), object_is_pinned (*(ptr))); \
5863                 if (!object_is_pinned (*(ptr)))                         \
5864                         missing_remsets = TRUE;                         \
5865             } \
5866         } \
5867         } while (0)
5868
5869 /*
5870  * Check that each object reference which points into the nursery can
5871  * be found in the remembered sets.
5872  */
5873 static void
5874 check_consistency_callback (char *start, size_t size, void *dummy)
5875 {
5876         GCVTable *vt = (GCVTable*)LOAD_VTABLE (start);
5877         DEBUG (8, fprintf (gc_debug_file, "Scanning object %p, vtable: %p (%s)\n", start, vt, vt->klass->name));
5878
5879 #define SCAN_OBJECT_ACTION
5880 #include "sgen-scan-object.h"
5881 }
5882
5883 /*
5884  * Perform consistency check of the heap.
5885  *
5886  * Assumes the world is stopped.
5887  */
5888 static void
5889 check_consistency (void)
5890 {
5891         LOSObject *bigobj;
5892
5893         // Need to add more checks
5894
5895         missing_remsets = FALSE;
5896
5897         DEBUG (1, fprintf (gc_debug_file, "Begin heap consistency check...\n"));
5898
5899         // Check that oldspace->newspace pointers are registered with the collector
5900         major.iterate_objects (TRUE, TRUE, (IterateObjectCallbackFunc)check_consistency_callback, NULL);
5901
5902         for (bigobj = los_object_list; bigobj; bigobj = bigobj->next)
5903                 check_consistency_callback (bigobj->data, bigobj->size, NULL);
5904
5905         DEBUG (1, fprintf (gc_debug_file, "Heap consistency check done.\n"));
5906
5907 #ifdef SGEN_BINARY_PROTOCOL
5908         if (!binary_protocol_file)
5909 #endif
5910                 g_assert (!missing_remsets);
5911 }
5912
5913
5914 #undef HANDLE_PTR
5915 #define HANDLE_PTR(ptr,obj)     do {                                    \
5916                 if (*(ptr))                                             \
5917                         g_assert (LOAD_VTABLE (*(ptr)));                \
5918         } while (0)
5919
5920 static void
5921 check_major_refs_callback (char *start, size_t size, void *dummy)
5922 {
5923 #define SCAN_OBJECT_ACTION
5924 #include "sgen-scan-object.h"
5925 }
5926
5927 static void
5928 check_major_refs (void)
5929 {
5930         LOSObject *bigobj;
5931
5932         major.iterate_objects (TRUE, TRUE, (IterateObjectCallbackFunc)check_major_refs_callback, NULL);
5933
5934         for (bigobj = los_object_list; bigobj; bigobj = bigobj->next)
5935                 check_major_refs_callback (bigobj->data, bigobj->size, NULL);
5936 }
5937
5938 /* Check that the reference is valid */
5939 #undef HANDLE_PTR
5940 #define HANDLE_PTR(ptr,obj)     do {    \
5941                 if (*(ptr)) {   \
5942                         g_assert (safe_name (*(ptr)) != NULL);  \
5943                 }       \
5944         } while (0)
5945
5946 /*
5947  * check_object:
5948  *
5949  *   Perform consistency check on an object. Currently we only check that the
5950  * reference fields are valid.
5951  */
5952 void
5953 check_object (char *start)
5954 {
5955         if (!start)
5956                 return;
5957
5958 #include "sgen-scan-object.h"
5959 }
5960
5961 /*
5962  * ######################################################################
5963  * ########  Other mono public interface functions.
5964  * ######################################################################
5965  */
5966
5967 void
5968 mono_gc_collect (int generation)
5969 {
5970         LOCK_GC;
5971         stop_world ();
5972         if (generation == 0) {
5973                 collect_nursery (0);
5974         } else {
5975                 major_collection ("user request");
5976         }
5977         restart_world ();
5978         UNLOCK_GC;
5979 }
5980
5981 int
5982 mono_gc_max_generation (void)
5983 {
5984         return 1;
5985 }
5986
5987 int
5988 mono_gc_collection_count (int generation)
5989 {
5990         if (generation == 0)
5991                 return num_minor_gcs;
5992         return num_major_gcs;
5993 }
5994
5995 int64_t
5996 mono_gc_get_used_size (void)
5997 {
5998         gint64 tot = 0;
5999         LOCK_GC;
6000         tot = los_memory_usage;
6001         tot += nursery_section->next_data - nursery_section->data;
6002         tot += major.get_used_size ();
6003         /* FIXME: account for pinned objects */
6004         UNLOCK_GC;
6005         return tot;
6006 }
6007
6008 int64_t
6009 mono_gc_get_heap_size (void)
6010 {
6011         return total_alloc;
6012 }
6013
6014 void
6015 mono_gc_disable (void)
6016 {
6017         LOCK_GC;
6018         gc_disabled++;
6019         UNLOCK_GC;
6020 }
6021
6022 void
6023 mono_gc_enable (void)
6024 {
6025         LOCK_GC;
6026         gc_disabled--;
6027         UNLOCK_GC;
6028 }
6029
6030 int
6031 mono_gc_get_los_limit (void)
6032 {
6033         return MAX_SMALL_OBJ_SIZE;
6034 }
6035
6036 gboolean
6037 mono_object_is_alive (MonoObject* o)
6038 {
6039         return TRUE;
6040 }
6041
6042 int
6043 mono_gc_get_generation (MonoObject *obj)
6044 {
6045         if (ptr_in_nursery (obj))
6046                 return 0;
6047         return 1;
6048 }
6049
6050 void
6051 mono_gc_enable_events (void)
6052 {
6053 }
6054
6055 void
6056 mono_gc_weak_link_add (void **link_addr, MonoObject *obj, gboolean track)
6057 {
6058         LOCK_GC;
6059         mono_gc_register_disappearing_link (obj, link_addr, track);
6060         UNLOCK_GC;
6061 }
6062
6063 void
6064 mono_gc_weak_link_remove (void **link_addr)
6065 {
6066         LOCK_GC;
6067         mono_gc_register_disappearing_link (NULL, link_addr, FALSE);
6068         UNLOCK_GC;
6069 }
6070
6071 MonoObject*
6072 mono_gc_weak_link_get (void **link_addr)
6073 {
6074         if (!*link_addr)
6075                 return NULL;
6076         return (MonoObject*) REVEAL_POINTER (*link_addr);
6077 }
6078
6079 gboolean
6080 mono_gc_ephemeron_array_add (MonoObject *obj)
6081 {
6082         EphemeronLinkNode *node;
6083
6084         LOCK_GC;
6085
6086         node = mono_sgen_alloc_internal (INTERNAL_MEM_EPHEMERON_LINK);
6087         if (!node) {
6088                 UNLOCK_GC;
6089                 return FALSE;
6090         }
6091         node->array = (char*)obj;
6092         node->next = ephemeron_list;
6093         ephemeron_list = node;
6094
6095         DEBUG (5, fprintf (gc_debug_file, "Registered ephemeron array %p\n", obj));
6096
6097         UNLOCK_GC;
6098         return TRUE;
6099 }
6100
6101 void*
6102 mono_gc_make_descr_from_bitmap (gsize *bitmap, int numbits)
6103 {
6104         if (numbits < ((sizeof (*bitmap) * 8) - ROOT_DESC_TYPE_SHIFT)) {
6105                 return (void*)MAKE_ROOT_DESC (ROOT_DESC_BITMAP, bitmap [0]);
6106         } else {
6107                 mword complex = alloc_complex_descriptor (bitmap, numbits);
6108                 return (void*)MAKE_ROOT_DESC (ROOT_DESC_COMPLEX, complex);
6109         }
6110 }
6111
6112 void*
6113 mono_gc_make_root_descr_user (MonoGCRootMarkFunc marker)
6114 {
6115         void *descr;
6116
6117         g_assert (user_descriptors_next < MAX_USER_DESCRIPTORS);
6118         descr = (void*)MAKE_ROOT_DESC (ROOT_DESC_USER, (mword)user_descriptors_next);
6119         user_descriptors [user_descriptors_next ++] = marker;
6120
6121         return descr;
6122 }
6123
6124 void*
6125 mono_gc_alloc_fixed (size_t size, void *descr)
6126 {
6127         /* FIXME: do a single allocation */
6128         void *res = calloc (1, size);
6129         if (!res)
6130                 return NULL;
6131         if (!mono_gc_register_root (res, size, descr)) {
6132                 free (res);
6133                 res = NULL;
6134         }
6135         return res;
6136 }
6137
6138 void
6139 mono_gc_free_fixed (void* addr)
6140 {
6141         mono_gc_deregister_root (addr);
6142         free (addr);
6143 }
6144
6145 void*
6146 mono_gc_invoke_with_gc_lock (MonoGCLockedCallbackFunc func, void *data)
6147 {
6148         void *result;
6149         LOCK_INTERRUPTION;
6150         result = func (data);
6151         UNLOCK_INTERRUPTION;
6152         return result;
6153 }
6154
6155 gboolean
6156 mono_gc_is_gc_thread (void)
6157 {
6158         gboolean result;
6159         LOCK_GC;
6160         result = mono_sgen_thread_info_lookup (ARCH_GET_THREAD ()) != NULL;
6161         UNLOCK_GC;
6162         return result;
6163 }
6164
6165 #ifdef USER_CONFIG
6166
6167 /* Tries to extract a number from the passed string, taking in to account m, k
6168  * and g suffixes */
6169 static gboolean
6170 parse_environment_string_extract_number (gchar *str, glong *out)
6171 {
6172         char *endptr;
6173         int len = strlen (str), shift = 0;
6174         glong val;
6175         gboolean is_suffix = FALSE;
6176         char suffix;
6177
6178         switch (str [len - 1]) {
6179                 case 'g':
6180                 case 'G':
6181                         shift += 10;
6182                 case 'm':
6183                 case 'M':
6184                         shift += 10;
6185                 case 'k':
6186                 case 'K':
6187                         shift += 10;
6188                         is_suffix = TRUE;
6189                         suffix = str [len - 1];
6190                         break;
6191         }
6192
6193         errno = 0;
6194         val = strtol (str, &endptr, 10);
6195
6196         if ((errno == ERANGE && (val == LONG_MAX || val == LONG_MIN))
6197                         || (errno != 0 && val == 0) || (endptr == str))
6198                 return FALSE;
6199
6200         if (is_suffix) {
6201                 if (*(endptr + 1)) /* Invalid string. */
6202                         return FALSE;
6203                 val <<= shift;
6204         }
6205
6206         *out = val;
6207         return TRUE;
6208 }
6209
6210 #endif 
6211
6212 void
6213 mono_gc_base_init (void)
6214 {
6215         char *env;
6216         char **opts, **ptr;
6217         char *major_collector = NULL;
6218         struct sigaction sinfo;
6219
6220         LOCK_INIT (gc_mutex);
6221         LOCK_GC;
6222         if (gc_initialized) {
6223                 UNLOCK_GC;
6224                 return;
6225         }
6226         pagesize = mono_pagesize ();
6227         gc_debug_file = stderr;
6228
6229         LOCK_INIT (interruption_mutex);
6230
6231         if ((env = getenv ("MONO_GC_PARAMS"))) {
6232                 opts = g_strsplit (env, ",", -1);
6233                 for (ptr = opts; *ptr; ++ptr) {
6234                         char *opt = *ptr;
6235 #ifdef USER_CONFIG
6236                         if (g_str_has_prefix (opt, "nursery-size=")) {
6237                                 long val;
6238                                 opt = strchr (opt, '=') + 1;
6239                                 if (*opt && parse_environment_string_extract_number (opt, &val)) {
6240                                         default_nursery_size = val;
6241 #ifdef SGEN_ALIGN_NURSERY
6242                                         if ((val & (val - 1))) {
6243                                                 fprintf (stderr, "The nursery size must be a power of two.\n");
6244                                                 exit (1);
6245                                         }
6246
6247                                         default_nursery_bits = 0;
6248                                         while (1 << (++ default_nursery_bits) != default_nursery_size)
6249                                                 ;
6250 #endif
6251                                 } else {
6252                                         fprintf (stderr, "nursery-size must be an integer.\n");
6253                                         exit (1);
6254                                 }
6255                         } else
6256 #endif
6257                         if (g_str_has_prefix (opt, "major=")) {
6258                                 opt = strchr (opt, '=') + 1;
6259                                 major_collector = g_strdup (opt);
6260                         } else {
6261                                 fprintf (stderr, "MONO_GC_PARAMS must be a comma-delimited list of one or more of the following:\n");
6262                                 fprintf (stderr, "  nursery-size=N (where N is an integer, possibly with a k, m or a g suffix)\n");
6263                                 fprintf (stderr, "  major=COLLECTOR (where collector is `marksweep' or `copying')\n");
6264                                 exit (1);
6265                         }
6266                 }
6267                 g_strfreev (opts);
6268         }
6269
6270         nursery_size = DEFAULT_NURSERY_SIZE;
6271         minor_collection_allowance = MIN_MINOR_COLLECTION_ALLOWANCE;
6272
6273         init_stats ();
6274         mono_sgen_init_internal_allocator ();
6275
6276         mono_sgen_register_fixed_internal_mem_type (INTERNAL_MEM_FRAGMENT, sizeof (Fragment));
6277         mono_sgen_register_fixed_internal_mem_type (INTERNAL_MEM_SECTION, SGEN_SIZEOF_GC_MEM_SECTION);
6278         mono_sgen_register_fixed_internal_mem_type (INTERNAL_MEM_FINALIZE_ENTRY, sizeof (FinalizeEntry));
6279         mono_sgen_register_fixed_internal_mem_type (INTERNAL_MEM_DISLINK, sizeof (DisappearingLink));
6280         mono_sgen_register_fixed_internal_mem_type (INTERNAL_MEM_ROOT_RECORD, sizeof (RootRecord));
6281         mono_sgen_register_fixed_internal_mem_type (INTERNAL_MEM_GRAY_QUEUE, sizeof (GrayQueueSection));
6282         g_assert (sizeof (GenericStoreRememberedSet) == sizeof (gpointer) * STORE_REMSET_BUFFER_SIZE);
6283         mono_sgen_register_fixed_internal_mem_type (INTERNAL_MEM_STORE_REMSET, sizeof (GenericStoreRememberedSet));
6284         mono_sgen_register_fixed_internal_mem_type (INTERNAL_MEM_EPHEMERON_LINK, sizeof (EphemeronLinkNode));
6285
6286         alloc_nursery ();
6287
6288         if (!major_collector || !strcmp (major_collector, "marksweep"))
6289                 mono_sgen_marksweep_init (&major, DEFAULT_NURSERY_BITS, nursery_start, nursery_real_end);
6290         else if (!strcmp (major_collector, "copying"))
6291                 mono_sgen_copying_init (&major, DEFAULT_NURSERY_BITS, nursery_start, nursery_real_end);
6292         else {
6293                 fprintf (stderr, "Unknown major collector `%s'.\n", major_collector);
6294                 exit (1);
6295         }
6296
6297         if (major_collector)
6298                 g_free (major_collector);
6299
6300         if ((env = getenv ("MONO_GC_DEBUG"))) {
6301                 opts = g_strsplit (env, ",", -1);
6302                 for (ptr = opts; ptr && *ptr; ptr ++) {
6303                         char *opt = *ptr;
6304                         if (opt [0] >= '0' && opt [0] <= '9') {
6305                                 gc_debug_level = atoi (opt);
6306                                 opt++;
6307                                 if (opt [0] == ':')
6308                                         opt++;
6309                                 if (opt [0]) {
6310                                         char *rf = g_strdup_printf ("%s.%d", opt, getpid ());
6311                                         gc_debug_file = fopen (rf, "wb");
6312                                         if (!gc_debug_file)
6313                                                 gc_debug_file = stderr;
6314                                         g_free (rf);
6315                                 }
6316                         } else if (!strcmp (opt, "collect-before-allocs")) {
6317                                 collect_before_allocs = TRUE;
6318                         } else if (!strcmp (opt, "check-at-minor-collections")) {
6319                                 consistency_check_at_minor_collection = TRUE;
6320                                 nursery_clear_policy = CLEAR_AT_GC;
6321                         } else if (!strcmp (opt, "xdomain-checks")) {
6322                                 xdomain_checks = TRUE;
6323                         } else if (!strcmp (opt, "clear-at-gc")) {
6324                                 nursery_clear_policy = CLEAR_AT_GC;
6325                         } else if (!strcmp (opt, "conservative-stack-mark")) {
6326                                 conservative_stack_mark = TRUE;
6327                         } else if (!strcmp (opt, "check-scan-starts")) {
6328                                 do_scan_starts_check = TRUE;
6329                         } else if (g_str_has_prefix (opt, "heap-dump=")) {
6330                                 char *filename = strchr (opt, '=') + 1;
6331                                 nursery_clear_policy = CLEAR_AT_GC;
6332                                 heap_dump_file = fopen (filename, "w");
6333                                 if (heap_dump_file)
6334                                         fprintf (heap_dump_file, "<sgen-dump>\n");
6335 #ifdef SGEN_BINARY_PROTOCOL
6336                         } else if (g_str_has_prefix (opt, "binary-protocol=")) {
6337                                 char *filename = strchr (opt, '=') + 1;
6338                                 binary_protocol_file = fopen (filename, "w");
6339 #endif
6340                         } else {
6341                                 fprintf (stderr, "Invalid format for the MONO_GC_DEBUG env variable: '%s'\n", env);
6342                                 fprintf (stderr, "The format is: MONO_GC_DEBUG=[l[:filename]|<option>]+ where l is a debug level 0-9.\n");
6343                                 fprintf (stderr, "Valid options are: collect-before-allocs, check-at-minor-collections, xdomain-checks, clear-at-gc.\n");
6344                                 exit (1);
6345                         }
6346                 }
6347                 g_strfreev (opts);
6348         }
6349
6350         suspend_ack_semaphore_ptr = &suspend_ack_semaphore;
6351         MONO_SEM_INIT (&suspend_ack_semaphore, 0);
6352
6353         sigfillset (&sinfo.sa_mask);
6354         sinfo.sa_flags = SA_RESTART | SA_SIGINFO;
6355         sinfo.sa_sigaction = suspend_handler;
6356         if (sigaction (suspend_signal_num, &sinfo, NULL) != 0) {
6357                 g_error ("failed sigaction");
6358         }
6359
6360         sinfo.sa_handler = restart_handler;
6361         if (sigaction (restart_signal_num, &sinfo, NULL) != 0) {
6362                 g_error ("failed sigaction");
6363         }
6364
6365         sigfillset (&suspend_signal_mask);
6366         sigdelset (&suspend_signal_mask, restart_signal_num);
6367
6368         global_remset = alloc_remset (1024, NULL);
6369         global_remset->next = NULL;
6370
6371         pthread_key_create (&remembered_set_key, unregister_thread);
6372
6373 #ifndef HAVE_KW_THREAD
6374         pthread_key_create (&thread_info_key, NULL);
6375 #endif
6376
6377         gc_initialized = TRUE;
6378         UNLOCK_GC;
6379         mono_gc_register_thread (&sinfo);
6380 }
6381
6382 int
6383 mono_gc_get_suspend_signal (void)
6384 {
6385         return suspend_signal_num;
6386 }
6387
6388 enum {
6389         ATYPE_NORMAL,
6390         ATYPE_VECTOR,
6391         ATYPE_SMALL,
6392         ATYPE_NUM
6393 };
6394
6395 #ifdef HAVE_KW_THREAD
6396 #define EMIT_TLS_ACCESS(mb,dummy,offset)        do {    \
6397         mono_mb_emit_byte ((mb), MONO_CUSTOM_PREFIX);   \
6398         mono_mb_emit_byte ((mb), CEE_MONO_TLS);         \
6399         mono_mb_emit_i4 ((mb), (offset));               \
6400         } while (0)
6401 #else
6402 #define EMIT_TLS_ACCESS(mb,member,dummy)        do {    \
6403         mono_mb_emit_byte ((mb), MONO_CUSTOM_PREFIX);   \
6404         mono_mb_emit_byte ((mb), CEE_MONO_TLS);         \
6405         mono_mb_emit_i4 ((mb), thread_info_key);        \
6406         mono_mb_emit_icon ((mb), G_STRUCT_OFFSET (SgenThreadInfo, member));     \
6407         mono_mb_emit_byte ((mb), CEE_ADD);              \
6408         mono_mb_emit_byte ((mb), CEE_LDIND_I);          \
6409         } while (0)
6410 #endif
6411
6412 #ifdef MANAGED_ALLOCATION
6413 /* FIXME: Do this in the JIT, where specialized allocation sequences can be created
6414  * for each class. This is currently not easy to do, as it is hard to generate basic 
6415  * blocks + branches, but it is easy with the linear IL codebase.
6416  *
6417  * For this to work we'd need to solve the TLAB race, first.  Now we
6418  * require the allocator to be in a few known methods to make sure
6419  * that they are executed atomically via the restart mechanism.
6420  */
6421 static MonoMethod*
6422 create_allocator (int atype)
6423 {
6424         int p_var, size_var;
6425         guint32 slowpath_branch, max_size_branch;
6426         MonoMethodBuilder *mb;
6427         MonoMethod *res;
6428         MonoMethodSignature *csig;
6429         static gboolean registered = FALSE;
6430         int tlab_next_addr_var, new_next_var;
6431         int num_params, i;
6432         const char *name = NULL;
6433         AllocatorWrapperInfo *info;
6434
6435 #ifdef HAVE_KW_THREAD
6436         int tlab_next_addr_offset = -1;
6437         int tlab_temp_end_offset = -1;
6438
6439         MONO_THREAD_VAR_OFFSET (tlab_next_addr, tlab_next_addr_offset);
6440         MONO_THREAD_VAR_OFFSET (tlab_temp_end, tlab_temp_end_offset);
6441
6442         g_assert (tlab_next_addr_offset != -1);
6443         g_assert (tlab_temp_end_offset != -1);
6444 #endif
6445
6446         if (!registered) {
6447                 mono_register_jit_icall (mono_gc_alloc_obj, "mono_gc_alloc_obj", mono_create_icall_signature ("object ptr int"), FALSE);
6448                 mono_register_jit_icall (mono_gc_alloc_vector, "mono_gc_alloc_vector", mono_create_icall_signature ("object ptr int int"), FALSE);
6449                 registered = TRUE;
6450         }
6451
6452         if (atype == ATYPE_SMALL) {
6453                 num_params = 1;
6454                 name = "AllocSmall";
6455         } else if (atype == ATYPE_NORMAL) {
6456                 num_params = 1;
6457                 name = "Alloc";
6458         } else if (atype == ATYPE_VECTOR) {
6459                 num_params = 2;
6460                 name = "AllocVector";
6461         } else {
6462                 g_assert_not_reached ();
6463         }
6464
6465         csig = mono_metadata_signature_alloc (mono_defaults.corlib, num_params);
6466         csig->ret = &mono_defaults.object_class->byval_arg;
6467         for (i = 0; i < num_params; ++i)
6468                 csig->params [i] = &mono_defaults.int_class->byval_arg;
6469
6470         mb = mono_mb_new (mono_defaults.object_class, name, MONO_WRAPPER_ALLOC);
6471         size_var = mono_mb_add_local (mb, &mono_defaults.int32_class->byval_arg);
6472         if (atype == ATYPE_NORMAL || atype == ATYPE_SMALL) {
6473                 /* size = vtable->klass->instance_size; */
6474                 mono_mb_emit_ldarg (mb, 0);
6475                 mono_mb_emit_icon (mb, G_STRUCT_OFFSET (MonoVTable, klass));
6476                 mono_mb_emit_byte (mb, CEE_ADD);
6477                 mono_mb_emit_byte (mb, CEE_LDIND_I);
6478                 mono_mb_emit_icon (mb, G_STRUCT_OFFSET (MonoClass, instance_size));
6479                 mono_mb_emit_byte (mb, CEE_ADD);
6480                 /* FIXME: assert instance_size stays a 4 byte integer */
6481                 mono_mb_emit_byte (mb, CEE_LDIND_U4);
6482                 mono_mb_emit_stloc (mb, size_var);
6483         } else if (atype == ATYPE_VECTOR) {
6484                 MonoExceptionClause *clause;
6485                 int pos, pos_leave;
6486                 MonoClass *oom_exc_class;
6487                 MonoMethod *ctor;
6488
6489                 /* n >  MONO_ARRAY_MAX_INDEX -> OverflowException */
6490                 mono_mb_emit_ldarg (mb, 1);
6491                 mono_mb_emit_icon (mb, MONO_ARRAY_MAX_INDEX);
6492                 pos = mono_mb_emit_short_branch (mb, CEE_BLE_UN_S);
6493                 mono_mb_emit_exception (mb, "OverflowException", NULL);
6494                 mono_mb_patch_short_branch (mb, pos);
6495
6496                 clause = mono_image_alloc0 (mono_defaults.corlib, sizeof (MonoExceptionClause));
6497                 clause->try_offset = mono_mb_get_label (mb);
6498
6499                 /* vtable->klass->sizes.element_size */
6500                 mono_mb_emit_ldarg (mb, 0);
6501                 mono_mb_emit_icon (mb, G_STRUCT_OFFSET (MonoVTable, klass));
6502                 mono_mb_emit_byte (mb, CEE_ADD);
6503                 mono_mb_emit_byte (mb, CEE_LDIND_I);
6504                 mono_mb_emit_icon (mb, G_STRUCT_OFFSET (MonoClass, sizes.element_size));
6505                 mono_mb_emit_byte (mb, CEE_ADD);
6506                 mono_mb_emit_byte (mb, CEE_LDIND_U4);
6507
6508                 /* * n */
6509                 mono_mb_emit_ldarg (mb, 1);
6510                 mono_mb_emit_byte (mb, CEE_MUL_OVF_UN);
6511                 /* + sizeof (MonoArray) */
6512                 mono_mb_emit_icon (mb, sizeof (MonoArray));
6513                 mono_mb_emit_byte (mb, CEE_ADD_OVF_UN);
6514                 mono_mb_emit_stloc (mb, size_var);
6515
6516                 pos_leave = mono_mb_emit_branch (mb, CEE_LEAVE);
6517
6518                 /* catch */
6519                 clause->flags = MONO_EXCEPTION_CLAUSE_NONE;
6520                 clause->try_len = mono_mb_get_pos (mb) - clause->try_offset;
6521                 clause->data.catch_class = mono_class_from_name (mono_defaults.corlib,
6522                                 "System", "OverflowException");
6523                 g_assert (clause->data.catch_class);
6524                 clause->handler_offset = mono_mb_get_label (mb);
6525
6526                 oom_exc_class = mono_class_from_name (mono_defaults.corlib,
6527                                 "System", "OutOfMemoryException");
6528                 g_assert (oom_exc_class);
6529                 ctor = mono_class_get_method_from_name (oom_exc_class, ".ctor", 0);
6530                 g_assert (ctor);
6531
6532                 mono_mb_emit_byte (mb, CEE_POP);
6533                 mono_mb_emit_op (mb, CEE_NEWOBJ, ctor);
6534                 mono_mb_emit_byte (mb, CEE_THROW);
6535
6536                 clause->handler_len = mono_mb_get_pos (mb) - clause->handler_offset;
6537                 mono_mb_set_clauses (mb, 1, clause);
6538                 mono_mb_patch_branch (mb, pos_leave);
6539                 /* end catch */
6540         } else {
6541                 g_assert_not_reached ();
6542         }
6543
6544         /* size += ALLOC_ALIGN - 1; */
6545         mono_mb_emit_ldloc (mb, size_var);
6546         mono_mb_emit_icon (mb, ALLOC_ALIGN - 1);
6547         mono_mb_emit_byte (mb, CEE_ADD);
6548         /* size &= ~(ALLOC_ALIGN - 1); */
6549         mono_mb_emit_icon (mb, ~(ALLOC_ALIGN - 1));
6550         mono_mb_emit_byte (mb, CEE_AND);
6551         mono_mb_emit_stloc (mb, size_var);
6552
6553         /* if (size > MAX_SMALL_OBJ_SIZE) goto slowpath */
6554         if (atype != ATYPE_SMALL) {
6555                 mono_mb_emit_ldloc (mb, size_var);
6556                 mono_mb_emit_icon (mb, MAX_SMALL_OBJ_SIZE);
6557                 max_size_branch = mono_mb_emit_short_branch (mb, MONO_CEE_BGT_S);
6558         }
6559
6560         /*
6561          * We need to modify tlab_next, but the JIT only supports reading, so we read
6562          * another tls var holding its address instead.
6563          */
6564
6565         /* tlab_next_addr (local) = tlab_next_addr (TLS var) */
6566         tlab_next_addr_var = mono_mb_add_local (mb, &mono_defaults.int_class->byval_arg);
6567         EMIT_TLS_ACCESS (mb, tlab_next_addr, tlab_next_addr_offset);
6568         mono_mb_emit_stloc (mb, tlab_next_addr_var);
6569
6570         /* p = (void**)tlab_next; */
6571         p_var = mono_mb_add_local (mb, &mono_defaults.int_class->byval_arg);
6572         mono_mb_emit_ldloc (mb, tlab_next_addr_var);
6573         mono_mb_emit_byte (mb, CEE_LDIND_I);
6574         mono_mb_emit_stloc (mb, p_var);
6575         
6576         /* new_next = (char*)p + size; */
6577         new_next_var = mono_mb_add_local (mb, &mono_defaults.int_class->byval_arg);
6578         mono_mb_emit_ldloc (mb, p_var);
6579         mono_mb_emit_ldloc (mb, size_var);
6580         mono_mb_emit_byte (mb, CEE_CONV_I);
6581         mono_mb_emit_byte (mb, CEE_ADD);
6582         mono_mb_emit_stloc (mb, new_next_var);
6583
6584         /* tlab_next = new_next */
6585         mono_mb_emit_ldloc (mb, tlab_next_addr_var);
6586         mono_mb_emit_ldloc (mb, new_next_var);
6587         mono_mb_emit_byte (mb, CEE_STIND_I);
6588
6589         /* if (G_LIKELY (new_next < tlab_temp_end)) */
6590         mono_mb_emit_ldloc (mb, new_next_var);
6591         EMIT_TLS_ACCESS (mb, tlab_temp_end, tlab_temp_end_offset);
6592         slowpath_branch = mono_mb_emit_short_branch (mb, MONO_CEE_BLT_UN_S);
6593
6594         /* Slowpath */
6595         if (atype != ATYPE_SMALL)
6596                 mono_mb_patch_short_branch (mb, max_size_branch);
6597
6598         mono_mb_emit_byte (mb, MONO_CUSTOM_PREFIX);
6599         mono_mb_emit_byte (mb, CEE_MONO_NOT_TAKEN);
6600
6601         /* FIXME: mono_gc_alloc_obj takes a 'size_t' as an argument, not an int32 */
6602         mono_mb_emit_ldarg (mb, 0);
6603         mono_mb_emit_ldloc (mb, size_var);
6604         if (atype == ATYPE_NORMAL || atype == ATYPE_SMALL) {
6605                 mono_mb_emit_icall (mb, mono_gc_alloc_obj);
6606         } else if (atype == ATYPE_VECTOR) {
6607                 mono_mb_emit_ldarg (mb, 1);
6608                 mono_mb_emit_icall (mb, mono_gc_alloc_vector);
6609         } else {
6610                 g_assert_not_reached ();
6611         }
6612         mono_mb_emit_byte (mb, CEE_RET);
6613
6614         /* Fastpath */
6615         mono_mb_patch_short_branch (mb, slowpath_branch);
6616
6617         /* FIXME: Memory barrier */
6618
6619         /* *p = vtable; */
6620         mono_mb_emit_ldloc (mb, p_var);
6621         mono_mb_emit_ldarg (mb, 0);
6622         mono_mb_emit_byte (mb, CEE_STIND_I);
6623
6624         if (atype == ATYPE_VECTOR) {
6625                 /* arr->max_length = max_length; */
6626                 mono_mb_emit_ldloc (mb, p_var);
6627                 mono_mb_emit_ldflda (mb, G_STRUCT_OFFSET (MonoArray, max_length));
6628                 mono_mb_emit_ldarg (mb, 1);
6629                 mono_mb_emit_byte (mb, CEE_STIND_I);
6630         }
6631
6632         /* return p */
6633         mono_mb_emit_ldloc (mb, p_var);
6634         mono_mb_emit_byte (mb, CEE_RET);
6635
6636         res = mono_mb_create_method (mb, csig, 8);
6637         mono_mb_free (mb);
6638         mono_method_get_header (res)->init_locals = FALSE;
6639
6640         info = mono_image_alloc0 (mono_defaults.corlib, sizeof (AllocatorWrapperInfo));
6641         info->gc_name = "sgen";
6642         info->alloc_type = atype;
6643         mono_marshal_set_wrapper_info (res, info);
6644
6645         return res;
6646 }
6647 #endif
6648
6649 const char *
6650 mono_gc_get_gc_name (void)
6651 {
6652         return "sgen";
6653 }
6654
6655 static MonoMethod* alloc_method_cache [ATYPE_NUM];
6656 static MonoMethod *write_barrier_method;
6657
6658 static gboolean
6659 is_ip_in_managed_allocator (MonoDomain *domain, gpointer ip)
6660 {
6661         MonoJitInfo *ji;
6662         MonoMethod *method;
6663         int i;
6664
6665         if (!ip || !domain)
6666                 return FALSE;
6667         ji = mono_jit_info_table_find (domain, ip);
6668         if (!ji)
6669                 return FALSE;
6670         method = ji->method;
6671
6672         if (method == write_barrier_method)
6673                 return TRUE;
6674         for (i = 0; i < ATYPE_NUM; ++i)
6675                 if (method == alloc_method_cache [i])
6676                         return TRUE;
6677         return FALSE;
6678 }
6679
6680 /*
6681  * Generate an allocator method implementing the fast path of mono_gc_alloc_obj ().
6682  * The signature of the called method is:
6683  *      object allocate (MonoVTable *vtable)
6684  */
6685 MonoMethod*
6686 mono_gc_get_managed_allocator (MonoVTable *vtable, gboolean for_box)
6687 {
6688 #ifdef MANAGED_ALLOCATION
6689         MonoClass *klass = vtable->klass;
6690
6691 #ifdef HAVE_KW_THREAD
6692         int tlab_next_offset = -1;
6693         int tlab_temp_end_offset = -1;
6694         MONO_THREAD_VAR_OFFSET (tlab_next, tlab_next_offset);
6695         MONO_THREAD_VAR_OFFSET (tlab_temp_end, tlab_temp_end_offset);
6696
6697         if (tlab_next_offset == -1 || tlab_temp_end_offset == -1)
6698                 return NULL;
6699 #endif
6700
6701         if (!mono_runtime_has_tls_get ())
6702                 return NULL;
6703         if (klass->instance_size > tlab_size)
6704                 return NULL;
6705         if (klass->has_finalize || klass->marshalbyref || (mono_profiler_get_events () & MONO_PROFILE_ALLOCATIONS))
6706                 return NULL;
6707         if (klass->rank)
6708                 return NULL;
6709         if (klass->byval_arg.type == MONO_TYPE_STRING)
6710                 return NULL;
6711         if (collect_before_allocs)
6712                 return NULL;
6713
6714         if (ALIGN_TO (klass->instance_size, ALLOC_ALIGN) < MAX_SMALL_OBJ_SIZE)
6715                 return mono_gc_get_managed_allocator_by_type (ATYPE_SMALL);
6716         else
6717                 return mono_gc_get_managed_allocator_by_type (ATYPE_NORMAL);
6718 #else
6719         return NULL;
6720 #endif
6721 }
6722
6723 MonoMethod*
6724 mono_gc_get_managed_array_allocator (MonoVTable *vtable, int rank)
6725 {
6726 #ifdef MANAGED_ALLOCATION
6727         MonoClass *klass = vtable->klass;
6728
6729 #ifdef HAVE_KW_THREAD
6730         int tlab_next_offset = -1;
6731         int tlab_temp_end_offset = -1;
6732         MONO_THREAD_VAR_OFFSET (tlab_next, tlab_next_offset);
6733         MONO_THREAD_VAR_OFFSET (tlab_temp_end, tlab_temp_end_offset);
6734
6735         if (tlab_next_offset == -1 || tlab_temp_end_offset == -1)
6736                 return NULL;
6737 #endif
6738
6739         if (rank != 1)
6740                 return NULL;
6741         if (!mono_runtime_has_tls_get ())
6742                 return NULL;
6743         if (mono_profiler_get_events () & MONO_PROFILE_ALLOCATIONS)
6744                 return NULL;
6745         if (collect_before_allocs)
6746                 return NULL;
6747         g_assert (!klass->has_finalize && !klass->marshalbyref);
6748
6749         return mono_gc_get_managed_allocator_by_type (ATYPE_VECTOR);
6750 #else
6751         return NULL;
6752 #endif
6753 }
6754
6755 MonoMethod*
6756 mono_gc_get_managed_allocator_by_type (int atype)
6757 {
6758 #ifdef MANAGED_ALLOCATION
6759         MonoMethod *res;
6760
6761         if (!mono_runtime_has_tls_get ())
6762                 return NULL;
6763
6764         mono_loader_lock ();
6765         res = alloc_method_cache [atype];
6766         if (!res)
6767                 res = alloc_method_cache [atype] = create_allocator (atype);
6768         mono_loader_unlock ();
6769         return res;
6770 #else
6771         return NULL;
6772 #endif
6773 }
6774
6775 guint32
6776 mono_gc_get_managed_allocator_types (void)
6777 {
6778         return ATYPE_NUM;
6779 }
6780
6781
6782 MonoMethod*
6783 mono_gc_get_write_barrier (void)
6784 {
6785         MonoMethod *res;
6786         MonoMethodBuilder *mb;
6787         MonoMethodSignature *sig;
6788 #ifdef MANAGED_WBARRIER
6789         int label_no_wb_1, label_no_wb_2, label_no_wb_3, label_no_wb_4, label_need_wb, label_slow_path;
6790 #ifndef SGEN_ALIGN_NURSERY
6791         int label_continue_1, label_continue_2, label_no_wb_5;
6792         int dereferenced_var;
6793 #endif
6794         int buffer_var, buffer_index_var, dummy_var;
6795
6796 #ifdef HAVE_KW_THREAD
6797         int stack_end_offset = -1, store_remset_buffer_offset = -1;
6798         int store_remset_buffer_index_offset = -1, store_remset_buffer_index_addr_offset = -1;
6799
6800         MONO_THREAD_VAR_OFFSET (stack_end, stack_end_offset);
6801         g_assert (stack_end_offset != -1);
6802         MONO_THREAD_VAR_OFFSET (store_remset_buffer, store_remset_buffer_offset);
6803         g_assert (store_remset_buffer_offset != -1);
6804         MONO_THREAD_VAR_OFFSET (store_remset_buffer_index, store_remset_buffer_index_offset);
6805         g_assert (store_remset_buffer_index_offset != -1);
6806         MONO_THREAD_VAR_OFFSET (store_remset_buffer_index_addr, store_remset_buffer_index_addr_offset);
6807         g_assert (store_remset_buffer_index_addr_offset != -1);
6808 #endif
6809 #endif
6810
6811         // FIXME: Maybe create a separate version for ctors (the branch would be
6812         // correctly predicted more times)
6813         if (write_barrier_method)
6814                 return write_barrier_method;
6815
6816         /* Create the IL version of mono_gc_barrier_generic_store () */
6817         sig = mono_metadata_signature_alloc (mono_defaults.corlib, 1);
6818         sig->ret = &mono_defaults.void_class->byval_arg;
6819         sig->params [0] = &mono_defaults.int_class->byval_arg;
6820
6821         mb = mono_mb_new (mono_defaults.object_class, "wbarrier", MONO_WRAPPER_WRITE_BARRIER);
6822
6823 #ifdef MANAGED_WBARRIER
6824         if (mono_runtime_has_tls_get ()) {
6825 #ifdef SGEN_ALIGN_NURSERY
6826                 // if (ptr_in_nursery (ptr)) return;
6827                 /*
6828                  * Masking out the bits might be faster, but we would have to use 64 bit
6829                  * immediates, which might be slower.
6830                  */
6831                 mono_mb_emit_ldarg (mb, 0);
6832                 mono_mb_emit_icon (mb, DEFAULT_NURSERY_BITS);
6833                 mono_mb_emit_byte (mb, CEE_SHR_UN);
6834                 mono_mb_emit_icon (mb, (mword)nursery_start >> DEFAULT_NURSERY_BITS);
6835                 label_no_wb_1 = mono_mb_emit_branch (mb, CEE_BEQ);
6836
6837                 // if (!ptr_in_nursery (*ptr)) return;
6838                 mono_mb_emit_ldarg (mb, 0);
6839                 mono_mb_emit_byte (mb, CEE_LDIND_I);
6840                 mono_mb_emit_icon (mb, DEFAULT_NURSERY_BITS);
6841                 mono_mb_emit_byte (mb, CEE_SHR_UN);
6842                 mono_mb_emit_icon (mb, (mword)nursery_start >> DEFAULT_NURSERY_BITS);
6843                 label_no_wb_2 = mono_mb_emit_branch (mb, CEE_BNE_UN);
6844 #else
6845
6846                 // if (ptr < (nursery_start)) goto continue;
6847                 mono_mb_emit_ldarg (mb, 0);
6848                 mono_mb_emit_ptr (mb, (gpointer) nursery_start);
6849                 label_continue_1 = mono_mb_emit_branch (mb, CEE_BLT);
6850
6851                 // if (ptr >= nursery_real_end)) goto continue;
6852                 mono_mb_emit_ldarg (mb, 0);
6853                 mono_mb_emit_ptr (mb, (gpointer) nursery_real_end);
6854                 label_continue_2 = mono_mb_emit_branch (mb, CEE_BGE);
6855
6856                 // Otherwise return
6857                 label_no_wb_1 = mono_mb_emit_branch (mb, CEE_BR);
6858
6859                 // continue:
6860                 mono_mb_patch_branch (mb, label_continue_1);
6861                 mono_mb_patch_branch (mb, label_continue_2);
6862
6863                 // Dereference and store in local var
6864                 dereferenced_var = mono_mb_add_local (mb, &mono_defaults.int_class->byval_arg);
6865                 mono_mb_emit_ldarg (mb, 0);
6866                 mono_mb_emit_byte (mb, CEE_LDIND_I);
6867                 mono_mb_emit_stloc (mb, dereferenced_var);
6868
6869                 // if (*ptr < nursery_start) return;
6870                 mono_mb_emit_ldloc (mb, dereferenced_var);
6871                 mono_mb_emit_ptr (mb, (gpointer) nursery_start);
6872                 label_no_wb_2 = mono_mb_emit_branch (mb, CEE_BLT);
6873
6874                 // if (*ptr >= nursery_end) return;
6875                 mono_mb_emit_ldloc (mb, dereferenced_var);
6876                 mono_mb_emit_ptr (mb, (gpointer) nursery_real_end);
6877                 label_no_wb_5 = mono_mb_emit_branch (mb, CEE_BGE);
6878
6879 #endif 
6880                 // if (ptr >= stack_end) goto need_wb;
6881                 mono_mb_emit_ldarg (mb, 0);
6882                 EMIT_TLS_ACCESS (mb, stack_end, stack_end_offset);
6883                 label_need_wb = mono_mb_emit_branch (mb, CEE_BGE_UN);
6884
6885                 // if (ptr >= stack_start) return;
6886                 dummy_var = mono_mb_add_local (mb, &mono_defaults.int_class->byval_arg);
6887                 mono_mb_emit_ldarg (mb, 0);
6888                 mono_mb_emit_ldloc_addr (mb, dummy_var);
6889                 label_no_wb_3 = mono_mb_emit_branch (mb, CEE_BGE_UN);
6890
6891                 // need_wb:
6892                 mono_mb_patch_branch (mb, label_need_wb);
6893
6894                 // buffer = STORE_REMSET_BUFFER;
6895                 buffer_var = mono_mb_add_local (mb, &mono_defaults.int_class->byval_arg);
6896                 EMIT_TLS_ACCESS (mb, store_remset_buffer, store_remset_buffer_offset);
6897                 mono_mb_emit_stloc (mb, buffer_var);
6898
6899                 // buffer_index = STORE_REMSET_BUFFER_INDEX;
6900                 buffer_index_var = mono_mb_add_local (mb, &mono_defaults.int_class->byval_arg);
6901                 EMIT_TLS_ACCESS (mb, store_remset_buffer_index, store_remset_buffer_index_offset);
6902                 mono_mb_emit_stloc (mb, buffer_index_var);
6903
6904                 // if (buffer [buffer_index] == ptr) return;
6905                 mono_mb_emit_ldloc (mb, buffer_var);
6906                 mono_mb_emit_ldloc (mb, buffer_index_var);
6907                 g_assert (sizeof (gpointer) == 4 || sizeof (gpointer) == 8);
6908                 mono_mb_emit_icon (mb, sizeof (gpointer) == 4 ? 2 : 3);
6909                 mono_mb_emit_byte (mb, CEE_SHL);
6910                 mono_mb_emit_byte (mb, CEE_ADD);
6911                 mono_mb_emit_byte (mb, CEE_LDIND_I);
6912                 mono_mb_emit_ldarg (mb, 0);
6913                 label_no_wb_4 = mono_mb_emit_branch (mb, CEE_BEQ);
6914
6915                 // ++buffer_index;
6916                 mono_mb_emit_ldloc (mb, buffer_index_var);
6917                 mono_mb_emit_icon (mb, 1);
6918                 mono_mb_emit_byte (mb, CEE_ADD);
6919                 mono_mb_emit_stloc (mb, buffer_index_var);
6920
6921                 // if (buffer_index >= STORE_REMSET_BUFFER_SIZE) goto slow_path;
6922                 mono_mb_emit_ldloc (mb, buffer_index_var);
6923                 mono_mb_emit_icon (mb, STORE_REMSET_BUFFER_SIZE);
6924                 label_slow_path = mono_mb_emit_branch (mb, CEE_BGE);
6925
6926                 // buffer [buffer_index] = ptr;
6927                 mono_mb_emit_ldloc (mb, buffer_var);
6928                 mono_mb_emit_ldloc (mb, buffer_index_var);
6929                 g_assert (sizeof (gpointer) == 4 || sizeof (gpointer) == 8);
6930                 mono_mb_emit_icon (mb, sizeof (gpointer) == 4 ? 2 : 3);
6931                 mono_mb_emit_byte (mb, CEE_SHL);
6932                 mono_mb_emit_byte (mb, CEE_ADD);
6933                 mono_mb_emit_ldarg (mb, 0);
6934                 mono_mb_emit_byte (mb, CEE_STIND_I);
6935
6936                 // STORE_REMSET_BUFFER_INDEX = buffer_index;
6937                 EMIT_TLS_ACCESS (mb, store_remset_buffer_index_addr, store_remset_buffer_index_addr_offset);
6938                 mono_mb_emit_ldloc (mb, buffer_index_var);
6939                 mono_mb_emit_byte (mb, CEE_STIND_I);
6940
6941                 // return;
6942                 mono_mb_patch_branch (mb, label_no_wb_1);
6943                 mono_mb_patch_branch (mb, label_no_wb_2);
6944                 mono_mb_patch_branch (mb, label_no_wb_3);
6945                 mono_mb_patch_branch (mb, label_no_wb_4);
6946 #ifndef SGEN_ALIGN_NURSERY
6947                 mono_mb_patch_branch (mb, label_no_wb_5);
6948 #endif
6949                 mono_mb_emit_byte (mb, CEE_RET);
6950
6951                 // slow path
6952                 mono_mb_patch_branch (mb, label_slow_path);
6953         }
6954 #endif
6955
6956         mono_mb_emit_ldarg (mb, 0);
6957         mono_mb_emit_icall (mb, mono_gc_wbarrier_generic_nostore);
6958         mono_mb_emit_byte (mb, CEE_RET);
6959
6960         res = mono_mb_create_method (mb, sig, 16);
6961         mono_mb_free (mb);
6962
6963         mono_loader_lock ();
6964         if (write_barrier_method) {
6965                 /* Already created */
6966                 mono_free_method (res);
6967         } else {
6968                 /* double-checked locking */
6969                 mono_memory_barrier ();
6970                 write_barrier_method = res;
6971         }
6972         mono_loader_unlock ();
6973
6974         return write_barrier_method;
6975 }
6976
6977 char*
6978 mono_gc_get_description (void)
6979 {
6980         return g_strdup ("sgen");
6981 }
6982
6983 void
6984 mono_gc_set_desktop_mode (void)
6985 {
6986 }
6987
6988 gboolean
6989 mono_gc_is_moving (void)
6990 {
6991         return TRUE;
6992 }
6993
6994 gboolean
6995 mono_gc_is_disabled (void)
6996 {
6997         return FALSE;
6998 }
6999
7000 gboolean
7001 mono_sgen_is_worker_thread (pthread_t thread)
7002 {
7003         return FALSE;
7004 }
7005
7006 void
7007 mono_sgen_debug_printf (int level, const char *format, ...)
7008 {
7009         va_list ap;
7010
7011         if (level > gc_debug_level)
7012                 return;
7013
7014         va_start (ap, format);
7015         vfprintf (gc_debug_file, format, ap);
7016         va_end (ap);
7017 }
7018
7019 #endif /* HAVE_SGEN_GC */