2 * sgen-gc.c: Simple generational GC.
5 * Paolo Molaro (lupus@ximian.com)
7 * Copyright (C) 2005-2006 Novell, Inc
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.
15 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
16 * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
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.
24 * All the rest of the code is LGPL.
26 * Important: allocation provides always zeroed memory, having to do
27 * a memset after allocation is deadly for performance.
28 * Memory usage at startup is currently as follows:
30 * 64 KB internal space
32 * We should provide a small memory config with half the sizes
34 * We currently try to make as few mono assumptions as possible:
35 * 1) 2-word header with no GC pointers in it (firts vtable, second to store the
37 * 2) gc descriptor is the second word in the vtable (first word in the class)
38 * 3) 8 byte alignment is the minimum and enough (not true for special structures, FIXME)
39 * 4) there is a function to get an object's size and the number of
40 * elements in an array.
41 * 5) we know the special way bounds are allocated for complex arrays
43 * Always try to keep stack usage to a minimum: no recursive behaviour
44 * and no large stack allocs.
46 * General description.
47 * Objects are initially allocated in a nursery using a fast bump-pointer technique.
48 * When the nursery is full we start a nursery collection: this is performed with a
50 * When the old generation is full we start a copying GC of the old generation as well:
51 * this will be changed to mark/compact in the future.
52 * The things that complicate this description are:
53 * *) pinned objects: we can't move them so we need to keep track of them
54 * *) no precise info of the thread stacks and registers: we need to be able to
55 * quickly find the objects that may be referenced conservatively and pin them
56 * (this makes the first issues more important)
57 * *) large objects are too expensive to be dealt with using copying GC: we handle them
58 * with mark/sweep during major collections
59 * *) some objects need to not move even if they are small (interned strings, Type handles):
60 * we use mark/sweep for them, too: they are not allocated in the nursery, but inside
61 * PinnedChunks regions
66 *) change the jit to emit write barrier calls when needed (we
67 can have specialized write barriers): done with icalls, still need to
68 use some specialized barriers
69 *) we could have a function pointer in MonoClass to implement
70 customized write barriers for value types
71 *) the write barrier code could be isolated in a couple of functions: when a
72 thread is stopped if it's inside the barrier it is let go again
73 until we stop outside of them (not really needed, see below GC-safe points)
74 *) investigate the stuff needed to advance a thread to a GC-safe
75 point (single-stepping, read from unmapped memory etc) and implement it
76 Not needed yet: since we treat the objects reachable from the stack/regs as
77 roots, we store the ptr and exec the write barrier so there is no race.
78 We may need this to solve the issue with setting the length of arrays and strings.
79 We may need this also for handling precise info on stacks, even simple things
80 as having uninitialized data on the stack and having to wait for the prolog
81 to zero it. Not an issue for the last frame that we scan conservatively.
82 We could always not trust the value in the slots anyway.
83 *) make the jit info table lock free
84 *) modify the jit to save info about references in stack locations:
85 this can be done just for locals as a start, so that at least
86 part of the stack is handled precisely.
87 *) Make the debug printf stuff thread and signal safe.
88 *) test/fix 64 bit issues
89 *) test/fix endianess issues
91 *) add batch moving profile info
92 *) add more timing info
93 *) there is a possible race when an array or string is created: the vtable is set,
94 but the length is set only later so if the GC needs to scan the object in that window,
95 it won't get the correct size for the object. The object can't have references and it will
96 be pinned, but a free memory fragment may be created that overlaps with it.
97 We should change the array max_length field to be at the same offset as the string length:
98 this way we can have a single special alloc function for them that sets the length.
99 Multi-dim arrays have the same issue for rank == 1 for the bounds data.
100 *) implement a card table as the write barrier instead of remembered sets?
101 *) some sort of blacklist support?
102 *) fin_ready_list is part of the root set, too
103 *) consider lowering the large object min size to 16/32KB or so and benchmark
104 *) once mark-compact is implemented we could still keep the
105 copying collector for the old generation and use it if we think
106 it is better (small heaps and no pinning object in the old
108 *) avoid the memory store from copy_object when not needed.
109 *) optimize the write barriers fastpath to happen in managed code
110 *) add an option to mmap the whole heap in one chunk: it makes for many
111 simplifications in the checks (put the nursery at the top and just use a single
112 check for inclusion/exclusion): the issue this has is that on 32 bit systems it's
113 not flexible (too much of the address space may be used by default or we can't
114 increase the heap as needed) and we'd need a race-free mechanism to return memory
115 back to the system (mprotect(PROT_NONE) will still keep the memory allocated if it
116 was written to, munmap is needed, but the following mmap may not find the same segment
118 *) memzero the fragments after restarting the world and optionally a smaller chunk at a time
119 *) an additional strategy to realloc/expand the nursery when fully pinned is to start
120 allocating objects in the old generation. This means that we can't optimize away write
121 barrier calls in ctors (but that is not valid for other reasons, too).
122 *) add write barriers to the Clone methods
130 #include <semaphore.h>
134 #include <sys/types.h>
135 #include <sys/stat.h>
136 #include <sys/mman.h>
137 #include <sys/time.h>
140 #include "metadata/metadata-internals.h"
141 #include "metadata/class-internals.h"
142 #include "metadata/gc-internal.h"
143 #include "metadata/object-internals.h"
144 #include "metadata/threads.h"
145 #include "metadata/sgen-gc.h"
146 #include "metadata/mono-gc.h"
147 #include "utils/mono-mmap.h"
149 #ifdef HAVE_VALGRIND_MEMCHECK_H
150 #include <valgrind/memcheck.h>
154 * ######################################################################
155 * ######## Types and constants used by the GC.
156 * ######################################################################
158 #if SIZEOF_VOID_P == 4
159 typedef guint32 mword;
161 typedef guint64 mword;
164 static int gc_initialized = 0;
165 static int gc_debug_level = 0;
166 static FILE* gc_debug_file;
169 mono_gc_flush_info (void)
171 fflush (gc_debug_file);
174 #define MAX_DEBUG_LEVEL 9
175 #define DEBUG(level,a) do {if ((level) <= MAX_DEBUG_LEVEL && (level) <= gc_debug_level) a;} while (0)
177 #define TV_DECLARE(name) struct timeval name
178 #define TV_GETTIME(tv) gettimeofday (&(tv), NULL)
179 #define TV_ELAPSED(start,end) (int)((((end).tv_sec - (start).tv_sec) * 1000000) + end.tv_usec - start.tv_usec)
181 #define GC_BITS_PER_WORD (sizeof (mword) * 8)
191 /* each request from the OS ends up in a GCMemSection */
192 typedef struct _GCMemSection GCMemSection;
193 struct _GCMemSection {
197 /* pointer where more data could be allocated if it fits */
201 * scan starts is an array of pointers to objects equally spaced in the allocation area
202 * They let use quickly find pinned objects from pinning pointers.
205 /* in major collections indexes in the pin_queue for objects that pin this section */
208 unsigned short num_scan_start;
212 /* large object space struct: 64+ KB */
213 /* we could make this limit much smaller to avoid memcpy copy
214 * and potentially have more room in the GC descriptor: need to measure
215 * This also means that such small OS objects will need to be
216 * allocated in a different way (using pinned chunks).
217 * We may want to put large but smaller than 64k objects in the fixed space
218 * when we move the object from one generation to another (to limit the
219 * pig in the snake effect).
220 * Note: it may be worth to have an optimized copy function, since we can
221 * assume that objects are aligned and have a multiple of 8 size.
222 * FIXME: This structure needs to be a multiple of 8 bytes in size: this is not
223 * true if MONO_ZERO_LEN_ARRAY is nonzero.
225 typedef struct _LOSObject LOSObject;
228 mword size; /* this is the object size */
229 int dummy; /* to have a sizeof (LOSObject) a multiple of ALLOC_ALIGN and data starting at same alignment */
232 char data [MONO_ZERO_LEN_ARRAY];
235 /* Pinned objects are allocated in the LOS space if bigger than half a page
236 * or from freelists otherwise. We assume that pinned objects are relatively few
237 * and they have a slow dying speed (like interned strings, thread objects).
238 * As such they will be collected only at major collections.
239 * free lists are not global: when we need memory we allocate a PinnedChunk.
240 * Each pinned chunk is made of several pages, the first of wich is used
241 * internally for bookeeping (here think of a page as 4KB). The bookeeping
242 * includes the freelists vectors and info about the object size of each page
243 * in the pinned chunk. So, when needed, a free page is found in a pinned chunk,
244 * a size is assigned to it, the page is divided in the proper chunks and each
245 * chunk is added to the freelist. To not waste space, the remaining space in the
246 * first page is used as objects of size 16 or 32 (need to measure which are more
248 * We use this same structure to allocate memory used internally by the GC, so
249 * we never use malloc/free if we need to alloc during collection: the world is stopped
250 * and malloc/free will deadlock.
251 * When we want to iterate over pinned objects, we just scan a page at a time
252 * linearly according to the size of objects in the page: the next pointer used to link
253 * the items in the freelist uses the same word as the vtable. Since we keep freelists
254 * for each pinned chunk, if the word points outside the pinned chunk it means
256 * We could avoid this expensive scanning in creative ways. We could have a policy
257 * of putting in the pinned space only objects we know about that have no struct fields
258 * with references and we can easily use a even expensive write barrier for them,
259 * since pointer writes on such objects should be rare.
260 * The best compromise is to just alloc interned strings and System.MonoType in them.
261 * It would be nice to allocate MonoThread in it, too: must check that we properly
262 * use write barriers so we don't have to do any expensive scanning of the whole pinned
263 * chunk list during minor collections. We can avoid it now because we alloc in it only
264 * reference-free objects.
266 #define PINNED_FIRST_SLOT_SIZE (sizeof (gpointer) * 4)
267 #define MAX_FREELIST_SIZE 2048
268 #define PINNED_PAGE_SIZE (4096)
269 #define PINNED_CHUNK_MIN_SIZE (4096*8)
270 typedef struct _PinnedChunk PinnedChunk;
271 struct _PinnedChunk {
274 int *page_sizes; /* a 0 means the page is still unused */
277 void *data [1]; /* page sizes and free lists are stored here */
281 * The young generation is divided into fragments. This is because
282 * we can hand one fragments to a thread for lock-less fast alloc and
283 * because the young generation ends up fragmented anyway by pinned objects.
284 * Once a collection is done, a list of fragments is created. When doing
285 * thread local alloc we use smallish nurseries so we allow new threads to
286 * allocate memory from gen0 without triggering a collection. Threads that
287 * are found to allocate lots of memory are given bigger fragments. This
288 * should make the finalizer thread use little nursery memory after a while.
289 * We should start assigning threads very small fragments: if there are many
290 * threads the nursery will be full of reserved space that the threads may not
291 * use at all, slowing down allocation speed.
293 typedef struct _Fragment Fragment;
297 char *fragment_start;
298 char *fragment_limit; /* the current soft limit for allocation */
302 /* the runtime can register areas of memory as roots: we keep two lists of roots,
303 * a pinned root set for conservatively scanned roots and a normal one for
304 * precisely scanned roots (currently implemented as a single list).
306 typedef struct _RootRecord RootRecord;
314 /* for use with write barriers */
315 typedef struct _RememberedSet RememberedSet;
316 struct _RememberedSet {
320 mword data [MONO_ZERO_LEN_ARRAY];
323 /* we have 4 possible values in the low 2 bits */
325 REMSET_LOCATION, /* just a pointer to the exact location */
326 REMSET_RANGE, /* range of pointer fields */
327 REMSET_OBJECT, /* mark all the object for scanning */
328 REMSET_TYPE_MASK = 0x3
331 static __thread RememberedSet *remembered_set MONO_TLS_FAST;
332 static pthread_key_t remembered_set_key;
333 static RememberedSet *global_remset;
334 static int store_to_global_remset = 0;
336 /* FIXME: later choose a size that takes into account the RememberedSet struct
337 * and doesn't waste any alloc paddin space.
339 #define DEFAULT_REMSET_SIZE 1024
340 static RememberedSet* alloc_remset (int size, gpointer id);
342 /* Structure that corresponds to a MonoVTable: desc is a mword so requires
343 * no cast from a pointer to an integer
350 /* these bits are set in the object vtable: we could merge them since an object can be
351 * either pinned or forwarded but not both.
352 * We store them in the vtable slot because the bits are used in the sync block for
353 * other purposes: if we merge them and alloc the sync blocks aligned to 8 bytes, we can change
354 * this and use bit 3 in the syncblock (with the lower two bits both set for forwarded, that
355 * would be an invalid combination for the monitor and hash code).
356 * The values are already shifted.
357 * The forwarding address is stored in the sync block.
359 #define FORWARDED_BIT 1
361 #define VTABLE_BITS_MASK 0x3
363 /* returns NULL if not forwarded, or the forwarded address */
364 #define object_is_forwarded(obj) (((mword*)(obj))[0] & FORWARDED_BIT? (void*)(((mword*)(obj))[1]): NULL)
365 /* set the forwarded address fw_addr for object obj */
366 #define forward_object(obj,fw_addr) do { \
367 ((mword*)(obj))[0] |= FORWARDED_BIT; \
368 ((mword*)(obj))[1] = (mword)(fw_addr); \
371 #define object_is_pinned(obj) (((mword*)(obj))[0] & PINNED_BIT)
372 #define pin_object(obj) do { \
373 ((mword*)(obj))[0] |= PINNED_BIT; \
375 #define unpin_object(obj) do { \
376 ((mword*)(obj))[0] &= ~PINNED_BIT; \
381 * Since we set bits in the vtable, use the macro to load it from the pointer to
382 * an object that is potentially pinned.
384 #define LOAD_VTABLE(addr) ((*(mword*)(addr)) & ~VTABLE_BITS_MASK)
387 safe_name (void* obj)
389 MonoVTable *vt = (MonoVTable*)LOAD_VTABLE (obj);
390 return vt->klass->name;
394 safe_object_get_size (MonoObject* o)
396 MonoClass *klass = ((MonoVTable*)LOAD_VTABLE (o))->klass;
397 if (klass == mono_defaults.string_class) {
398 return sizeof (MonoString) + 2 * mono_string_length ((MonoString*) o) + 2;
399 } else if (klass->rank) {
400 MonoArray *array = (MonoArray*)o;
401 size_t size = sizeof (MonoArray) + mono_array_element_size (klass) * mono_array_length (array);
405 size += sizeof (MonoArrayBounds) * klass->rank;
409 /* from a created object: the class must be inited already */
410 return klass->instance_size;
414 static inline gboolean
415 is_half_constructed (MonoObject *o)
419 klass = ((MonoVTable*)LOAD_VTABLE (o))->klass;
420 if ((klass == mono_defaults.string_class && mono_string_length ((MonoString*)o) == 0) ||
421 (klass->rank && mono_array_length ((MonoArray*)o) == 0))
428 * ######################################################################
429 * ######## Global data.
430 * ######################################################################
432 static LOCK_DECLARE (gc_mutex);
433 static int gc_disabled = 0;
434 static int num_minor_gcs = 0;
435 static int num_major_gcs = 0;
437 /* good sizes are 512KB-1MB: larger ones increase a lot memzeroing time */
438 //#define DEFAULT_NURSERY_SIZE (1024*512*125+4096*118)
439 #define DEFAULT_NURSERY_SIZE (1024*512*2)
440 #define DEFAULT_MAX_SECTION (DEFAULT_NURSERY_SIZE * 16)
441 #define DEFAULT_LOS_COLLECTION_TARGET (DEFAULT_NURSERY_SIZE * 2)
442 /* to quickly find the head of an object pinned by a conservative address
443 * we keep track of the objects allocated for each SCAN_START_SIZE memory
444 * chunk in the nursery or other memory sections. Larger values have less
445 * memory overhead and bigger runtime cost. 4-8 KB are reasonable values.
447 #define SCAN_START_SIZE (4096*2)
448 /* the minimum size of a fragment that we consider useful for allocation */
449 #define FRAGMENT_MIN_SIZE (512)
450 /* This is a fixed value used for pinned chunks, not the system pagesize */
451 #define FREELIST_PAGESIZE 4096
453 static mword pagesize = 4096;
454 static mword nursery_size = DEFAULT_NURSERY_SIZE;
455 static mword next_section_size = DEFAULT_NURSERY_SIZE * 4;
456 static mword max_section_size = DEFAULT_MAX_SECTION;
457 static int section_size_used = 0;
458 static int degraded_mode = 0;
460 static LOSObject *los_object_list = NULL;
461 static mword los_memory_usage = 0;
462 static mword los_num_objects = 0;
463 static mword next_los_collection = 2*1024*1024; /* 2 MB, need to tune */
464 static mword total_alloc = 0;
465 /* use this to tune when to do a major/minor collection */
466 static mword memory_pressure = 0;
468 static GCMemSection *section_list = NULL;
469 static GCMemSection *nursery_section = NULL;
470 static mword lowest_heap_address = ~(mword)0;
471 static mword highest_heap_address = 0;
473 typedef struct _FinalizeEntry FinalizeEntry;
474 struct _FinalizeEntry {
477 void *data; /* can be a disappearing link or the data for the finalizer */
478 /* Note we could use just one pointer if we don't support multiple callbacks
479 * for finalizers and per-finalizer data and if we store the obj pointers
480 * in the link like libgc does
485 * The finalizable hash has the object as the key, the
486 * disappearing_link hash, has the link address as key.
488 static FinalizeEntry **finalizable_hash = NULL;
489 /* objects that are ready to be finalized */
490 static FinalizeEntry *fin_ready_list = NULL;
491 /* disappearing links use the same structure but a different list */
492 static FinalizeEntry **disappearing_link_hash = NULL;
493 static mword disappearing_link_hash_size = 0;
494 static mword finalizable_hash_size = 0;
496 static int num_registered_finalizers = 0;
497 static int num_ready_finalizers = 0;
498 static int num_disappearing_links = 0;
499 static int no_finalize = 0;
501 /* keep each size a multiple of ALLOC_ALIGN */
502 /* on 64 bit systems 8 is likely completely unused. */
503 static const int freelist_sizes [] = {
504 8, 16, 24, 32, 40, 48, 64, 80,
505 96, 128, 160, 192, 224, 256, 320, 384,
506 448, 512, 584, 680, 816, 1024, 1360, 2048};
507 #define FREELIST_NUM_SLOTS (sizeof (freelist_sizes) / sizeof (freelist_sizes [0]))
509 static char* max_pinned_chunk_addr = NULL;
510 static char* min_pinned_chunk_addr = (char*)-1;
511 /* pinned_chunk_list is used for allocations of objects that are never moved */
512 static PinnedChunk *pinned_chunk_list = NULL;
513 /* internal_chunk_list is used for allocating structures needed by the GC */
514 static PinnedChunk *internal_chunk_list = NULL;
517 obj_is_from_pinned_alloc (char *p)
519 PinnedChunk *chunk = pinned_chunk_list;
520 for (; chunk; chunk = chunk->next) {
521 if (p >= (char*)chunk->start_data && p < ((char*)chunk + chunk->num_pages * FREELIST_PAGESIZE))
527 /* registered roots: the key to the hash is the root start address */
528 static RootRecord **roots_hash = NULL;
529 static int roots_hash_size = 0;
530 static mword roots_size = 0; /* amount of memory in the root set */
531 static int num_roots_entries = 0;
534 * The current allocation cursors
535 * We allocate objects in the nursery.
536 * The nursery is the area between nursery_start and nursery_real_end.
537 * nursery_next is the pointer to the space where the next object will be allocated.
538 * nursery_temp_end is the pointer to the end of the temporary space reserved for
539 * the allocation: this allows us to allow allocations inside the fragments of the
540 * nursery (the empty holes between pinned objects) and it allows us to set the
541 * scan starts at reasonable intervals.
542 * nursery_next and nursery_temp_end will become per-thread vars to allow lock-free
544 * nursery_first_pinned_start points to the start of the first pinned object in the nursery
545 * nursery_last_pinned_end points to the end of the last pinned object in the nursery
546 * At the next allocation, the area of the nursery where objects can be present is
547 * between MIN(nursery_first_pinned_start, first_fragment_start) and
548 * MAX(nursery_last_pinned_end, nursery_temp_end)
550 static char *nursery_start = NULL;
551 static char *nursery_next = NULL;
552 static char *nursery_temp_end = NULL;
553 static char *nursery_real_end = NULL;
554 static char *nursery_frag_real_end = NULL;
555 static char *nursery_first_pinned_start = NULL;
556 static char *nursery_last_pinned_end = NULL;
558 /* fragments that are free and ready to be used for allocation */
559 static Fragment *nursery_fragments = NULL;
560 /* freeelist of fragment structures */
561 static Fragment *fragment_freelist = NULL;
564 * used when moving the objects
565 * When the nursery is collected, objects are copied to to_space.
566 * The area between to_space and gray_objects is used as a stack
567 * of objects that need their fields checked for more references
569 * We should optimize somehow this mechanism to avoid rescanning
570 * ptr-free objects. The order is also probably not optimal: need to
571 * test cache misses and other graph traversal orders.
573 static char *to_space = NULL;
574 static char *gray_objects = NULL;
575 static char *to_space_end = NULL;
576 static GCMemSection *to_space_section = NULL;
578 /* objects bigger then this go into the large object space */
579 #define MAX_SMALL_OBJ_SIZE 0xffff
582 * ######################################################################
583 * ######## Macros and function declarations.
584 * ######################################################################
587 #define UPDATE_HEAP_BOUNDARIES(low,high) do { \
588 if ((mword)(low) < lowest_heap_address) \
589 lowest_heap_address = (mword)(low); \
590 if ((mword)(high) > highest_heap_address) \
591 highest_heap_address = (mword)(high); \
595 align_pointer (void *ptr)
597 mword p = (mword)ptr;
598 p += sizeof (gpointer) - 1;
599 p &= ~ (sizeof (gpointer) - 1);
603 /* forward declarations */
604 static void* get_internal_mem (size_t size);
605 static void free_internal_mem (void *addr);
606 static void* get_os_memory (size_t size, int activate);
607 static void free_os_memory (void *addr, size_t size);
608 static void report_internal_mem_usage (void);
610 static int stop_world (void);
611 static int restart_world (void);
612 static void pin_thread_data (void *start_nursery, void *end_nursery);
613 static void scan_from_remsets (void *start_nursery, void *end_nursery);
614 static void find_pinning_ref_from_thread (char *obj, size_t size);
615 static void update_current_thread_stack (void *start);
616 static GCMemSection* alloc_section (size_t size);
617 static void finalize_in_range (char *start, char *end);
618 static void null_link_in_range (char *start, char *end);
619 static gboolean search_fragment_for_size (size_t size);
620 static void mark_pinned_from_addresses (PinnedChunk *chunk, void **start, void **end);
621 static void clear_remsets (void);
622 static void sweep_pinned_objects (void);
623 static void free_large_object (LOSObject *obj);
624 static void free_mem_section (GCMemSection *section);
626 void check_consistency (void);
629 * ######################################################################
630 * ######## GC descriptors
631 * ######################################################################
632 * Used to quickly get the info the GC needs about an object: size and
633 * where the references are held.
635 /* objects are aligned to 8 bytes boundaries
636 * A descriptor is a pointer in MonoVTable, so 32 or 64 bits of size.
637 * The low 3 bits define the type of the descriptor. The other bits
638 * depend on the type.
639 * As a general rule the 13 remaining low bits define the size, either
640 * of the whole object or of the elements in the arrays. While for objects
641 * the size is already in bytes, for arrays we need to shift, because
642 * array elements might be smaller than 8 bytes. In case of arrays, we
643 * use two bits to describe what the additional high bits represents,
644 * so the default behaviour can handle element sizes less than 2048 bytes.
645 * The high 16 bits, if 0 it means the object is pointer-free.
646 * This design should make it easy and fast to skip over ptr-free data.
647 * The first 4 types should cover >95% of the objects.
648 * Note that since the size of objects is limited to 64K, larger objects
649 * will be allocated in the large object heap.
650 * If we want 4-bytes alignment, we need to put vector and small bitmap
654 DESC_TYPE_RUN_LENGTH, /* 16 bits aligned byte size | 1-3 (offset, numptr) bytes tuples */
655 DESC_TYPE_SMALL_BITMAP, /* 16 bits aligned byte size | 16-48 bit bitmap */
656 DESC_TYPE_STRING, /* nothing */
657 DESC_TYPE_COMPLEX, /* index for bitmap into complex_descriptors */
658 DESC_TYPE_VECTOR, /* 10 bits element size | 1 bit array | 2 bits desc | element desc */
659 DESC_TYPE_ARRAY, /* 10 bits element size | 1 bit array | 2 bits desc | element desc */
660 DESC_TYPE_LARGE_BITMAP, /* | 29-61 bitmap bits */
661 DESC_TYPE_COMPLEX_ARR, /* index for bitmap into complex_descriptors */
662 /* subtypes for arrays and vectors */
663 DESC_TYPE_V_PTRFREE = 0,/* there are no refs: keep first so it has a zero value */
664 DESC_TYPE_V_REFS, /* all the array elements are refs */
665 DESC_TYPE_V_RUN_LEN, /* elements are run-length encoded as DESC_TYPE_RUN_LENGTH */
666 DESC_TYPE_V_BITMAP /* elements are as the bitmap in DESC_TYPE_SMALL_BITMAP */
669 #define OBJECT_HEADER_WORDS (sizeof(MonoObject)/sizeof(gpointer))
670 #define LOW_TYPE_BITS 3
671 #define SMALL_BITMAP_SHIFT 16
672 #define SMALL_BITMAP_SIZE (GC_BITS_PER_WORD - SMALL_BITMAP_SHIFT)
673 #define VECTOR_INFO_SHIFT 14
674 #define VECTOR_ELSIZE_SHIFT 3
675 #define LARGE_BITMAP_SIZE (GC_BITS_PER_WORD - LOW_TYPE_BITS)
676 #define MAX_SMALL_SIZE ((1 << SMALL_BITMAP_SHIFT) - 1)
677 #define SMALL_SIZE_MASK 0xfff8
678 #define MAX_ELEMENT_SIZE 0x3ff
679 #define ELEMENT_SIZE_MASK (0x3ff << LOW_TYPE_BITS)
680 #define VECTOR_SUBTYPE_PTRFREE (DESC_TYPE_V_PTRFREE << VECTOR_INFO_SHIFT)
681 #define VECTOR_SUBTYPE_REFS (DESC_TYPE_V_REFS << VECTOR_INFO_SHIFT)
682 #define VECTOR_SUBTYPE_RUN_LEN (DESC_TYPE_V_RUN_LEN << VECTOR_INFO_SHIFT)
683 #define VECTOR_SUBTYPE_BITMAP (DESC_TYPE_V_BITMAP << VECTOR_INFO_SHIFT)
685 #define ALLOC_ALIGN 8
688 /* Root bitmap descriptors are simpler: the lower two bits describe the type
689 * and we either have 30/62 bitmap bits or nibble-based run-length,
690 * or a complex descriptor
693 ROOT_DESC_CONSERVATIVE, /* 0, so matches NULL value */
696 ROOT_DESC_LARGE_BITMAP,
697 ROOT_DESC_TYPE_MASK = 0x3,
698 ROOT_DESC_TYPE_SHIFT = 2,
701 static gsize* complex_descriptors = NULL;
702 static int complex_descriptors_size = 0;
703 static int complex_descriptors_next = 0;
706 alloc_complex_descriptor (gsize *bitmap, int numbits)
708 int nwords = numbits/GC_BITS_PER_WORD + 2;
713 res = complex_descriptors_next;
714 /* linear search, so we don't have duplicates with domain load/unload
715 * this should not be performance critical or we'd have bigger issues
716 * (the number and size of complex descriptors should be small).
718 for (i = 0; i < complex_descriptors_next; ) {
719 if (complex_descriptors [i] == nwords) {
721 for (j = 0; j < nwords - 1; ++j) {
722 if (complex_descriptors [i + 1 + j] != bitmap [j]) {
732 i += complex_descriptors [i];
734 if (complex_descriptors_next + nwords > complex_descriptors_size) {
735 int new_size = complex_descriptors_size * 2 + nwords;
736 complex_descriptors = g_realloc (complex_descriptors, new_size * sizeof (gsize));
737 complex_descriptors_size = new_size;
739 DEBUG (6, fprintf (gc_debug_file, "Complex descriptor %d, size: %d (total desc memory: %d)\n", res, nwords, complex_descriptors_size));
740 complex_descriptors_next += nwords;
741 complex_descriptors [res] = nwords;
742 for (i = 0; i < nwords - 1; ++i) {
743 complex_descriptors [res + 1 + i] = bitmap [i];
744 DEBUG (6, fprintf (gc_debug_file, "\tvalue: %p\n", (void*)complex_descriptors [res + 1 + i]));
751 * Descriptor builders.
754 mono_gc_make_descr_for_string (gsize *bitmap, int numbits)
756 return (void*) DESC_TYPE_STRING;
760 mono_gc_make_descr_for_object (gsize *bitmap, int numbits, size_t obj_size)
762 int first_set = -1, num_set = 0, last_set = -1, i;
764 size_t stored_size = obj_size;
765 stored_size += ALLOC_ALIGN - 1;
766 stored_size &= ~(ALLOC_ALIGN - 1);
767 for (i = 0; i < numbits; ++i) {
768 if (bitmap [i / GC_BITS_PER_WORD] & (1 << (i % GC_BITS_PER_WORD))) {
775 if (stored_size <= MAX_SMALL_OBJ_SIZE) {
776 /* check run-length encoding first: one byte offset, one byte number of pointers
777 * on 64 bit archs, we can have 3 runs, just one on 32.
778 * It may be better to use nibbles.
781 desc = DESC_TYPE_RUN_LENGTH | stored_size;
782 DEBUG (6, fprintf (gc_debug_file, "Ptrfree descriptor %p, size: %zd\n", (void*)desc, stored_size));
784 } else if (first_set < 256 && num_set < 256 && (first_set + num_set == last_set + 1)) {
785 desc = DESC_TYPE_RUN_LENGTH | stored_size | (first_set << 16) | (num_set << 24);
786 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));
789 /* we know the 2-word header is ptr-free */
790 if (last_set < SMALL_BITMAP_SIZE + OBJECT_HEADER_WORDS) {
791 desc = DESC_TYPE_SMALL_BITMAP | stored_size | ((*bitmap >> OBJECT_HEADER_WORDS) << SMALL_BITMAP_SHIFT);
792 DEBUG (6, fprintf (gc_debug_file, "Smallbitmap descriptor %p, size: %zd, last set: %d\n", (void*)desc, stored_size, last_set));
796 /* we know the 2-word header is ptr-free */
797 if (last_set < LARGE_BITMAP_SIZE + OBJECT_HEADER_WORDS) {
798 desc = DESC_TYPE_LARGE_BITMAP | ((*bitmap >> OBJECT_HEADER_WORDS) << LOW_TYPE_BITS);
799 DEBUG (6, fprintf (gc_debug_file, "Largebitmap descriptor %p, size: %zd, last set: %d\n", (void*)desc, stored_size, last_set));
802 /* it's a complex object ... */
803 desc = DESC_TYPE_COMPLEX | (alloc_complex_descriptor (bitmap, last_set + 1) << LOW_TYPE_BITS);
807 /* If the array holds references, numbits == 1 and the first bit is set in elem_bitmap */
809 mono_gc_make_descr_for_array (int vector, gsize *elem_bitmap, int numbits, size_t elem_size)
811 int first_set = -1, num_set = 0, last_set = -1, i;
812 mword desc = vector? DESC_TYPE_VECTOR: DESC_TYPE_ARRAY;
813 for (i = 0; i < numbits; ++i) {
814 if (elem_bitmap [i / GC_BITS_PER_WORD] & (1 << (i % GC_BITS_PER_WORD))) {
821 if (elem_size <= MAX_ELEMENT_SIZE) {
822 desc |= elem_size << VECTOR_ELSIZE_SHIFT;
824 return (void*)(desc | VECTOR_SUBTYPE_PTRFREE);
826 /* Note: we also handle structs with just ref fields */
827 if (num_set * sizeof (gpointer) == elem_size) {
828 return (void*)(desc | VECTOR_SUBTYPE_REFS | ((gssize)(-1) << 16));
830 /* FIXME: try run-len first */
831 /* Note: we can't skip the object header here, because it's not present */
832 if (last_set <= SMALL_BITMAP_SIZE) {
833 return (void*)(desc | VECTOR_SUBTYPE_BITMAP | (*elem_bitmap << 16));
836 /* it's am array of complex structs ... */
837 desc = DESC_TYPE_COMPLEX_ARR;
838 desc |= alloc_complex_descriptor (elem_bitmap, last_set + 1) << LOW_TYPE_BITS;
842 /* helper macros to scan and traverse objects, macros because we resue them in many functions */
843 #define STRING_SIZE(size,str) do { \
844 (size) = sizeof (MonoString) + 2 * (mono_string_length ((MonoString*)(str)) + 1); \
845 (size) += (ALLOC_ALIGN - 1); \
846 (size) &= ~(ALLOC_ALIGN - 1); \
849 #define OBJ_RUN_LEN_SIZE(size,vt,obj) do { \
850 (size) = (vt)->desc & 0xfff8; \
853 #define OBJ_BITMAP_SIZE(size,vt,obj) do { \
854 (size) = (vt)->desc & 0xfff8; \
857 //#define PREFETCH(addr) __asm__ __volatile__ (" prefetchnta %0": : "m"(*(char *)(addr)))
858 #define PREFETCH(addr)
860 /* code using these macros must define a HANDLE_PTR(ptr) macro that does the work */
861 #define OBJ_RUN_LEN_FOREACH_PTR(vt,obj) do { \
862 if ((vt)->desc & 0xffff0000) { \
863 /* there are pointers */ \
864 void **_objptr_end; \
865 void **_objptr = (void**)(obj); \
866 _objptr += ((vt)->desc >> 16) & 0xff; \
867 _objptr_end = _objptr + (((vt)->desc >> 24) & 0xff); \
868 while (_objptr < _objptr_end) { \
869 HANDLE_PTR (_objptr, (obj)); \
875 /* a bitmap desc means that there are pointer references or we'd have
876 * choosen run-length, instead: add an assert to check.
878 #define OBJ_BITMAP_FOREACH_PTR(vt,obj) do { \
879 /* there are pointers */ \
880 void **_objptr = (void**)(obj); \
881 gsize _bmap = (vt)->desc >> 16; \
882 _objptr += OBJECT_HEADER_WORDS; \
885 HANDLE_PTR (_objptr, (obj)); \
892 #define OBJ_LARGE_BITMAP_FOREACH_PTR(vt,obj) do { \
893 /* there are pointers */ \
894 void **_objptr = (void**)(obj); \
895 gsize _bmap = (vt)->desc >> LOW_TYPE_BITS; \
896 _objptr += OBJECT_HEADER_WORDS; \
899 HANDLE_PTR (_objptr, (obj)); \
906 #define OBJ_COMPLEX_FOREACH_PTR(vt,obj) do { \
907 /* there are pointers */ \
908 void **_objptr = (void**)(obj); \
909 gsize *bitmap_data = complex_descriptors + ((vt)->desc >> LOW_TYPE_BITS); \
910 int bwords = (*bitmap_data) - 1; \
911 void **start_run = _objptr; \
914 MonoObject *myobj = (MonoObject*)obj; \
915 g_print ("found %d at %p (0x%zx): %s.%s\n", bwords, (obj), (vt)->desc, myobj->vtable->klass->name_space, myobj->vtable->klass->name); \
917 while (bwords-- > 0) { \
918 gsize _bmap = *bitmap_data++; \
919 _objptr = start_run; \
920 /*g_print ("bitmap: 0x%x/%d at %p\n", _bmap, bwords, _objptr);*/ \
923 HANDLE_PTR (_objptr, (obj)); \
928 start_run += GC_BITS_PER_WORD; \
932 /* this one is untested */
933 #define OBJ_COMPLEX_ARR_FOREACH_PTR(vt,obj) do { \
934 /* there are pointers */ \
935 gsize *mbitmap_data = complex_descriptors + ((vt)->desc >> LOW_TYPE_BITS); \
936 int mbwords = (*mbitmap_data++) - 1; \
937 int el_size = mono_array_element_size (((MonoObject*)(obj))->vtable->klass); \
938 char *e_start = (char*)(obj) + G_STRUCT_OFFSET (MonoArray, vector); \
939 char *e_end = e_start + el_size * mono_array_length ((MonoArray*)(obj)); \
941 MonoObject *myobj = (MonoObject*)start; \
942 g_print ("found %d at %p (0x%zx): %s.%s\n", mbwords, (obj), (vt)->desc, myobj->vtable->klass->name_space, myobj->vtable->klass->name); \
944 while (e_start < e_end) { \
945 void **_objptr = (void**)e_start; \
946 gsize *bitmap_data = mbitmap_data; \
947 unsigned int bwords = mbwords; \
948 while (bwords-- > 0) { \
949 gsize _bmap = *bitmap_data++; \
950 void **start_run = _objptr; \
951 /*g_print ("bitmap: 0x%x\n", _bmap);*/ \
954 HANDLE_PTR (_objptr, (obj)); \
959 _objptr = start_run + GC_BITS_PER_WORD; \
961 e_start += el_size; \
965 #define OBJ_VECTOR_FOREACH_PTR(vt,obj) do { \
966 /* note: 0xffffc000 excludes DESC_TYPE_V_PTRFREE */ \
967 if ((vt)->desc & 0xffffc000) { \
968 int el_size = ((vt)->desc >> 3) & MAX_ELEMENT_SIZE; \
969 /* there are pointers */ \
970 int etype = (vt)->desc & 0xc000; \
971 if (etype == (DESC_TYPE_V_REFS << 14)) { \
972 void **p = (void**)((char*)(obj) + G_STRUCT_OFFSET (MonoArray, vector)); \
973 void **end_refs = (void**)((char*)p + el_size * mono_array_length ((MonoArray*)(obj))); \
974 /* Note: this code can handle also arrays of struct with only references in them */ \
975 while (p < end_refs) { \
976 HANDLE_PTR (p, (obj)); \
979 } else if (etype == DESC_TYPE_V_RUN_LEN << 14) { \
980 int offset = ((vt)->desc >> 16) & 0xff; \
981 int num_refs = ((vt)->desc >> 24) & 0xff; \
982 char *e_start = (char*)(obj) + G_STRUCT_OFFSET (MonoArray, vector); \
983 char *e_end = e_start + el_size * mono_array_length ((MonoArray*)(obj)); \
984 while (e_start < e_end) { \
985 void **p = (void**)e_start; \
988 for (i = 0; i < num_refs; ++i) { \
989 HANDLE_PTR (p + i, (obj)); \
991 e_start += el_size; \
993 } else if (etype == DESC_TYPE_V_BITMAP << 14) { \
994 char *e_start = (char*)(obj) + G_STRUCT_OFFSET (MonoArray, vector); \
995 char *e_end = e_start + el_size * mono_array_length ((MonoArray*)(obj)); \
996 while (e_start < e_end) { \
997 void **p = (void**)e_start; \
998 gsize _bmap = (vt)->desc >> 16; \
999 /* Note: there is no object header here to skip */ \
1001 if ((_bmap & 1)) { \
1002 HANDLE_PTR (p, (obj)); \
1007 e_start += el_size; \
1013 static mword new_obj_references = 0;
1014 static mword obj_references_checked = 0;
1017 #define HANDLE_PTR(ptr,obj) do { \
1018 if (*(ptr) && (char*)*(ptr) >= nursery_start && (char*)*(ptr) < nursery_next) { \
1019 new_obj_references++; \
1020 /*printf ("bogus ptr %p found at %p in object %p (%s.%s)\n", *(ptr), (ptr), o, o->vtable->klass->name_space, o->vtable->klass->name);*/ \
1022 obj_references_checked++; \
1027 * ######################################################################
1028 * ######## Detecting and removing garbage.
1029 * ######################################################################
1030 * This section of code deals with detecting the objects no longer in use
1031 * and reclaiming the memory.
1033 static void __attribute__((noinline))
1034 scan_area (char *start, char *end)
1039 int type_str = 0, type_rlen = 0, type_bitmap = 0, type_vector = 0, type_lbit = 0, type_complex = 0;
1040 new_obj_references = 0;
1041 obj_references_checked = 0;
1042 while (start < end) {
1043 if (!*(void**)start) {
1044 start += sizeof (void*); /* should be ALLOC_ALIGN, really */
1047 vt = (GCVTable*)LOAD_VTABLE (start);
1048 DEBUG (8, fprintf (gc_debug_file, "Scanning object %p, vtable: %p (%s)\n", start, vt, vt->klass->name));
1050 MonoObject *obj = (MonoObject*)start;
1051 g_print ("found at %p (0x%zx): %s.%s\n", start, vt->desc, obj->vtable->klass->name_space, obj->vtable->klass->name);
1053 type = vt->desc & 0x7;
1054 if (type == DESC_TYPE_STRING) {
1055 STRING_SIZE (skip_size, start);
1059 } else if (type == DESC_TYPE_RUN_LENGTH) {
1060 OBJ_RUN_LEN_SIZE (skip_size, vt, start);
1061 g_assert (skip_size);
1062 OBJ_RUN_LEN_FOREACH_PTR (vt,start);
1066 } else if (type == DESC_TYPE_VECTOR) { // includes ARRAY, too
1067 skip_size = (vt->desc >> LOW_TYPE_BITS) & MAX_ELEMENT_SIZE;
1068 skip_size *= mono_array_length ((MonoArray*)start);
1069 skip_size += sizeof (MonoArray);
1070 skip_size += (ALLOC_ALIGN - 1);
1071 skip_size &= ~(ALLOC_ALIGN - 1);
1072 OBJ_VECTOR_FOREACH_PTR (vt, start);
1073 if (type == DESC_TYPE_ARRAY) {
1074 /* account for the bounds */
1079 } else if (type == DESC_TYPE_SMALL_BITMAP) {
1080 OBJ_BITMAP_SIZE (skip_size, vt, start);
1081 g_assert (skip_size);
1082 OBJ_BITMAP_FOREACH_PTR (vt,start);
1086 } else if (type == DESC_TYPE_LARGE_BITMAP) {
1087 skip_size = safe_object_get_size ((MonoObject*)start);
1088 skip_size += (ALLOC_ALIGN - 1);
1089 skip_size &= ~(ALLOC_ALIGN - 1);
1090 OBJ_LARGE_BITMAP_FOREACH_PTR (vt,start);
1094 } else if (type == DESC_TYPE_COMPLEX) {
1095 /* this is a complex object */
1096 skip_size = safe_object_get_size ((MonoObject*)start);
1097 skip_size += (ALLOC_ALIGN - 1);
1098 skip_size &= ~(ALLOC_ALIGN - 1);
1099 OBJ_COMPLEX_FOREACH_PTR (vt, start);
1103 } else if (type == DESC_TYPE_COMPLEX_ARR) {
1104 /* this is an array of complex structs */
1105 skip_size = mono_array_element_size (((MonoVTable*)vt)->klass);
1106 skip_size *= mono_array_length ((MonoArray*)start);
1107 skip_size += sizeof (MonoArray);
1108 skip_size += (ALLOC_ALIGN - 1);
1109 skip_size &= ~(ALLOC_ALIGN - 1);
1110 OBJ_COMPLEX_ARR_FOREACH_PTR (vt, start);
1111 if (type == DESC_TYPE_ARRAY) {
1112 /* account for the bounds */
1121 /*printf ("references to new nursery %p-%p (size: %dk): %d, checked: %d\n", old_start, end, (end-old_start)/1024, new_obj_references, obj_references_checked);
1122 printf ("\tstrings: %d, runl: %d, vector: %d, bitmaps: %d, lbitmaps: %d, complex: %d\n",
1123 type_str, type_rlen, type_vector, type_bitmap, type_lbit, type_complex);*/
1126 static void __attribute__((noinline))
1127 scan_area_for_domain (MonoDomain *domain, char *start, char *end)
1132 while (start < end) {
1133 if (!*(void**)start) {
1134 start += sizeof (void*); /* should be ALLOC_ALIGN, really */
1137 vt = (GCVTable*)LOAD_VTABLE (start);
1138 /* handle threads someway (maybe insert the root domain vtable?) */
1139 if (mono_object_domain (start) == domain && vt->klass != mono_defaults.thread_class) {
1140 DEBUG (1, fprintf (gc_debug_file, "Need to cleanup object %p, (%s)\n", start, safe_name (start)));
1145 type = vt->desc & 0x7;
1146 if (type == DESC_TYPE_STRING) {
1147 STRING_SIZE (skip_size, start);
1148 if (remove) memset (start, 0, skip_size);
1151 } else if (type == DESC_TYPE_RUN_LENGTH) {
1152 OBJ_RUN_LEN_SIZE (skip_size, vt, start);
1153 g_assert (skip_size);
1154 if (remove) memset (start, 0, skip_size);
1157 } else if (type == DESC_TYPE_VECTOR) { // includes ARRAY, too
1158 skip_size = (vt->desc >> LOW_TYPE_BITS) & MAX_ELEMENT_SIZE;
1159 skip_size *= mono_array_length ((MonoArray*)start);
1160 skip_size += sizeof (MonoArray);
1161 skip_size += (ALLOC_ALIGN - 1);
1162 skip_size &= ~(ALLOC_ALIGN - 1);
1163 if (type == DESC_TYPE_ARRAY) {
1164 /* account for the bounds */
1166 if (remove) memset (start, 0, skip_size);
1169 } else if (type == DESC_TYPE_SMALL_BITMAP) {
1170 OBJ_BITMAP_SIZE (skip_size, vt, start);
1171 g_assert (skip_size);
1172 if (remove) memset (start, 0, skip_size);
1175 } else if (type == DESC_TYPE_LARGE_BITMAP) {
1176 skip_size = safe_object_get_size ((MonoObject*)start);
1177 skip_size += (ALLOC_ALIGN - 1);
1178 skip_size &= ~(ALLOC_ALIGN - 1);
1179 if (remove) memset (start, 0, skip_size);
1182 } else if (type == DESC_TYPE_COMPLEX) {
1183 /* this is a complex object */
1184 skip_size = safe_object_get_size ((MonoObject*)start);
1185 skip_size += (ALLOC_ALIGN - 1);
1186 skip_size &= ~(ALLOC_ALIGN - 1);
1187 if (remove) memset (start, 0, skip_size);
1190 } else if (type == DESC_TYPE_COMPLEX_ARR) {
1191 /* this is an array of complex structs */
1192 skip_size = mono_array_element_size (((MonoVTable*)vt)->klass);
1193 skip_size *= mono_array_length ((MonoArray*)start);
1194 skip_size += sizeof (MonoArray);
1195 skip_size += (ALLOC_ALIGN - 1);
1196 skip_size &= ~(ALLOC_ALIGN - 1);
1197 if (type == DESC_TYPE_ARRAY) {
1198 /* account for the bounds */
1200 if (remove) memset (start, 0, skip_size);
1210 * When appdomains are unloaded we can easily remove objects that have finalizers,
1211 * but all the others could still be present in random places on the heap.
1212 * We need a sweep to get rid of them even though it's going to be costly
1214 * The reason we need to remove them is because we access the vtable and class
1215 * structures to know the object size and the reference bitmap: once the domain is
1216 * unloaded the point to random memory.
1219 mono_gc_clear_domain (MonoDomain * domain)
1221 GCMemSection *section;
1223 for (section = section_list; section; section = section->next) {
1224 scan_area_for_domain (domain, section->data, section->end_data);
1226 /* FIXME: handle big and fixed objects (we remove, don't clear in this case) */
1231 add_to_global_remset (gpointer ptr)
1234 DEBUG (8, fprintf (gc_debug_file, "Adding global remset for %p\n", ptr));
1235 if (global_remset->store_next < global_remset->end_set) {
1236 *(global_remset->store_next++) = (mword)ptr;
1239 rs = alloc_remset (global_remset->end_set - global_remset->data, NULL);
1240 rs->next = global_remset;
1242 *(global_remset->store_next++) = (mword)ptr;
1246 * This is how the copying happens from the nursery to the old generation.
1247 * We assume that at this time all the pinned objects have been identified and
1249 * We run scan_object() for each pinned object so that each referenced
1250 * objects if possible are copied. The new gray objects created can have
1251 * scan_object() run on them right away, too.
1252 * Then we run copy_object() for the precisely tracked roots. At this point
1253 * all the roots are either gray or black. We run scan_object() on the gray
1254 * objects until no more gray objects are created.
1255 * At the end of the process we walk again the pinned list and we unmark
1256 * the pinned flag. As we go we also create the list of free space for use
1257 * in the next allocation runs.
1259 * We need to remember objects from the old generation that point to the new one
1260 * (or just addresses?).
1262 * copy_object could be made into a macro once debugged (use inline for now).
1265 static char* __attribute__((noinline))
1266 copy_object (char *obj, char *from_space_start, char *from_space_end)
1268 if (obj >= from_space_start && obj < from_space_end && (obj < to_space || obj >= to_space_end)) {
1272 DEBUG (9, fprintf (gc_debug_file, "Precise copy of %p", obj));
1273 if ((forwarded = object_is_forwarded (obj))) {
1274 g_assert (((MonoVTable*)LOAD_VTABLE(obj))->gc_descr);
1275 DEBUG (9, fprintf (gc_debug_file, " (already forwarded to %p)\n", forwarded));
1278 if (object_is_pinned (obj)) {
1279 g_assert (((MonoVTable*)LOAD_VTABLE(obj))->gc_descr);
1280 DEBUG (9, fprintf (gc_debug_file, " (pinned, no change)\n"));
1283 objsize = safe_object_get_size ((MonoObject*)obj);
1284 objsize += ALLOC_ALIGN - 1;
1285 objsize &= ~(ALLOC_ALIGN - 1);
1286 DEBUG (9, fprintf (gc_debug_file, " (to %p, %s size: %zd)\n", gray_objects, ((MonoObject*)obj)->vtable->klass->name, objsize));
1287 /* FIXME: handle pinned allocs:
1288 * Large objects are simple, at least until we always follow the rule:
1289 * if objsize >= MAX_SMALL_OBJ_SIZE, pin the object and return it.
1290 * At the end of major collections, we walk the los list and if
1291 * the object is pinned, it is marked, otherwise it can be freed.
1293 if (objsize >= MAX_SMALL_OBJ_SIZE || (obj >= min_pinned_chunk_addr && obj < max_pinned_chunk_addr && obj_is_from_pinned_alloc (obj))) {
1294 DEBUG (9, fprintf (gc_debug_file, "Marked LOS/Pinned %p (%s), size: %zd\n", obj, safe_name (obj), objsize));
1298 /* ok, the object is not pinned, we can move it */
1299 /* use a optimized memcpy here */
1304 char* edi = gray_objects;
1305 __asm__ __volatile__(
1307 : "=&c" (ecx), "=&D" (edi), "=&S" (esi)
1308 : "0" (objsize/4), "1" (edi),"2" (esi)
1313 memcpy (gray_objects, obj, objsize);
1315 /* adjust array->bounds */
1316 vt = ((MonoObject*)obj)->vtable;
1317 g_assert (vt->gc_descr);
1318 if (vt->rank && ((MonoArray*)obj)->bounds) {
1319 MonoArray *array = (MonoArray*)gray_objects;
1320 array->bounds = (MonoArrayBounds*)((char*)gray_objects + ((char*)((MonoArray*)obj)->bounds - (char*)obj));
1321 DEBUG (9, fprintf (gc_debug_file, "Array instance %p: size: %zd, rank: %d, length: %d\n", array, objsize, vt->rank, mono_array_length (array)));
1323 /* set the forwarding pointer */
1324 forward_object (obj, gray_objects);
1326 to_space_section->scan_starts [((char*)obj - (char*)to_space_section->data)/SCAN_START_SIZE] = obj;
1327 gray_objects += objsize;
1328 DEBUG (8, g_assert (gray_objects <= to_space_end));
1335 #define HANDLE_PTR(ptr,obj) do { \
1337 void *__old = *(ptr); \
1338 *(ptr) = copy_object (*(ptr), from_start, from_end); \
1339 DEBUG (9, if (__old != *(ptr)) fprintf (gc_debug_file, "Overwrote field at %p with %p (was: %p)\n", (ptr), *(ptr), __old)); \
1340 if (*(ptr) >= (void*)from_start && *(ptr) < (void*)from_end) \
1341 add_to_global_remset ((ptr)); \
1346 * Scan the object pointed to by @start for references to
1347 * other objects between @from_start and @from_end and copy
1348 * them to the gray_objects area.
1349 * Returns a pointer to the end of the object.
1352 scan_object (char *start, char* from_start, char* from_end)
1357 vt = (GCVTable*)LOAD_VTABLE (start);
1358 //type = vt->desc & 0x7;
1360 /* gcc should be smart enough to remove the bounds check, but it isn't:( */
1361 switch (vt->desc & 0x7) {
1362 //if (type == DESC_TYPE_STRING) {
1363 case DESC_TYPE_STRING:
1364 STRING_SIZE (skip_size, start);
1365 return start + skip_size;
1366 //} else if (type == DESC_TYPE_RUN_LENGTH) {
1367 case DESC_TYPE_RUN_LENGTH:
1368 OBJ_RUN_LEN_FOREACH_PTR (vt,start);
1369 OBJ_RUN_LEN_SIZE (skip_size, vt, start);
1370 g_assert (skip_size);
1371 return start + skip_size;
1372 //} else if (type == DESC_TYPE_VECTOR) { // includes ARRAY, too
1373 case DESC_TYPE_ARRAY:
1374 case DESC_TYPE_VECTOR:
1375 OBJ_VECTOR_FOREACH_PTR (vt, start);
1376 skip_size = safe_object_get_size ((MonoObject*)start);
1378 skip_size = (vt->desc >> LOW_TYPE_BITS) & MAX_ELEMENT_SIZE;
1379 skip_size *= mono_array_length ((MonoArray*)start);
1380 skip_size += sizeof (MonoArray);
1382 skip_size += (ALLOC_ALIGN - 1);
1383 skip_size &= ~(ALLOC_ALIGN - 1);
1384 return start + skip_size;
1385 //} else if (type == DESC_TYPE_SMALL_BITMAP) {
1386 case DESC_TYPE_SMALL_BITMAP:
1387 OBJ_BITMAP_FOREACH_PTR (vt,start);
1388 OBJ_BITMAP_SIZE (skip_size, vt, start);
1389 return start + skip_size;
1390 //} else if (type == DESC_TYPE_LARGE_BITMAP) {
1391 case DESC_TYPE_LARGE_BITMAP:
1392 OBJ_LARGE_BITMAP_FOREACH_PTR (vt,start);
1393 skip_size = safe_object_get_size ((MonoObject*)start);
1394 skip_size += (ALLOC_ALIGN - 1);
1395 skip_size &= ~(ALLOC_ALIGN - 1);
1396 return start + skip_size;
1397 //} else if (type == DESC_TYPE_COMPLEX) {
1398 case DESC_TYPE_COMPLEX:
1399 OBJ_COMPLEX_FOREACH_PTR (vt, start);
1400 /* this is a complex object */
1401 skip_size = safe_object_get_size ((MonoObject*)start);
1402 skip_size += (ALLOC_ALIGN - 1);
1403 skip_size &= ~(ALLOC_ALIGN - 1);
1404 return start + skip_size;
1405 //} else if (type == DESC_TYPE_COMPLEX_ARR) {
1406 case DESC_TYPE_COMPLEX_ARR:
1407 OBJ_COMPLEX_ARR_FOREACH_PTR (vt, start);
1408 /* this is an array of complex structs */
1409 skip_size = safe_object_get_size ((MonoObject*)start);
1411 skip_size = mono_array_element_size (((MonoObject*)start)->vtable->klass);
1412 skip_size *= mono_array_length ((MonoArray*)start);
1413 skip_size += sizeof (MonoArray);
1415 skip_size += (ALLOC_ALIGN - 1);
1416 skip_size &= ~(ALLOC_ALIGN - 1);
1417 return start + skip_size;
1419 g_assert_not_reached ();
1424 * Addresses from start to end are already sorted. This function finds the object header
1425 * for each address and pins the object. The addresses must be inside the passed section.
1426 * Return the number of pinned objects.
1429 pin_objects_from_addresses (GCMemSection *section, void **start, void **end, void *start_nursery, void *end_nursery)
1434 void *last_obj = NULL;
1435 size_t last_obj_size = 0;
1438 void **definitely_pinned = start;
1439 while (start < end) {
1441 /* the range check should be reduntant */
1442 if (addr != last && addr >= start_nursery && addr < end_nursery) {
1443 DEBUG (5, fprintf (gc_debug_file, "Considering pinning addr %p\n", addr));
1444 /* multiple pointers to the same object */
1445 if (addr >= last_obj && (char*)addr < (char*)last_obj + last_obj_size) {
1449 idx = ((char*)addr - (char*)section->data) / SCAN_START_SIZE;
1450 search_start = (void*)section->scan_starts [idx];
1451 if (!search_start || search_start > addr) {
1454 search_start = section->scan_starts [idx];
1455 if (search_start && search_start <= addr)
1458 if (!search_start || search_start > addr)
1459 search_start = start_nursery;
1461 if (search_start < last_obj)
1462 search_start = (char*)last_obj + last_obj_size;
1463 /* now addr should be in an object a short distance from search_start
1464 * Note that search_start must point to zeroed mem or point to an object.
1467 if (!*(void**)search_start) {
1468 mword p = (mword)search_start;
1469 p += sizeof (gpointer);
1470 p += ALLOC_ALIGN - 1;
1471 p &= ~(ALLOC_ALIGN - 1);
1472 search_start = (void*)p;
1475 last_obj = search_start;
1476 last_obj_size = safe_object_get_size ((MonoObject*)search_start);
1477 last_obj_size += ALLOC_ALIGN - 1;
1478 last_obj_size &= ~(ALLOC_ALIGN - 1);
1479 DEBUG (8, fprintf (gc_debug_file, "Pinned try match %p (%s), size %zd\n", last_obj, safe_name (last_obj), last_obj_size));
1480 if (addr >= search_start && (char*)addr < (char*)last_obj + last_obj_size) {
1481 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));
1482 pin_object (search_start);
1483 definitely_pinned [count] = search_start;
1487 /* skip to the next object */
1488 search_start = (void*)((char*)search_start + last_obj_size);
1489 } while (search_start <= addr);
1490 /* we either pinned the correct object or we ignored the addr because
1491 * it points to unused zeroed memory.
1497 //printf ("effective pinned: %d (at the end: %d)\n", count, (char*)end_nursery - (char*)last);
1501 static void** pin_queue;
1502 static int pin_queue_size = 0;
1503 static int next_pin_slot = 0;
1508 gap = (gap * 10) / 13;
1509 if (gap == 9 || gap == 10)
1518 compare_addr (const void *a, const void *b)
1520 return *(const void **)a - *(const void **)b;
1524 /* sort the addresses in array in increasing order */
1526 sort_addresses (void **array, int size)
1529 * qsort is slower as predicted.
1530 * qsort (array, size, sizeof (gpointer), compare_addr);
1537 gap = new_gap (gap);
1540 for (i = 0; i < end; i++) {
1542 if (array [i] > array [j]) {
1543 void* val = array [i];
1544 array [i] = array [j];
1549 if (gap == 1 && !swapped)
1555 print_nursery_gaps (void* start_nursery, void *end_nursery)
1558 gpointer first = start_nursery;
1560 for (i = 0; i < next_pin_slot; ++i) {
1561 next = pin_queue [i];
1562 fprintf (gc_debug_file, "Nursery range: %p-%p, size: %zd\n", first, next, (char*)next-(char*)first);
1566 fprintf (gc_debug_file, "Nursery range: %p-%p, size: %zd\n", first, next, (char*)next-(char*)first);
1569 /* reduce the info in the pin queue, removing duplicate pointers and sorting them */
1571 optimize_pin_queue (int start_slot)
1573 void **start, **cur, **end;
1574 /* sort and uniq pin_queue: we just sort and we let the rest discard multiple values */
1575 /* it may be better to keep ranges of pinned memory instead of individually pinning objects */
1576 DEBUG (5, fprintf (gc_debug_file, "Sorting pin queue, size: %d\n", next_pin_slot));
1577 if ((next_pin_slot - start_slot) > 1)
1578 sort_addresses (pin_queue + start_slot, next_pin_slot - start_slot);
1579 start = cur = pin_queue + start_slot;
1580 end = pin_queue + next_pin_slot;
1583 while (*start == *cur && cur < end)
1587 next_pin_slot = start - pin_queue;
1588 DEBUG (5, fprintf (gc_debug_file, "Pin queue reduced to size: %d\n", next_pin_slot));
1589 //DEBUG (6, print_nursery_gaps (start_nursery, end_nursery));
1594 realloc_pin_queue (void)
1596 int new_size = pin_queue_size? pin_queue_size + pin_queue_size/2: 1024;
1597 void **new_pin = get_internal_mem (sizeof (void*) * new_size);
1598 memcpy (new_pin, pin_queue, sizeof (void*) * next_pin_slot);
1599 free_internal_mem (pin_queue);
1600 pin_queue = new_pin;
1601 pin_queue_size = new_size;
1602 DEBUG (4, fprintf (gc_debug_file, "Reallocated pin queue to size: %d\n", new_size));
1606 * Scan the memory between start and end and queue values which could be pointers
1607 * to the area between start_nursery and end_nursery for later consideration.
1608 * Typically used for thread stacks.
1611 conservatively_pin_objects_from (void **start, void **end, void *start_nursery, void *end_nursery)
1614 while (start < end) {
1615 if (*start >= start_nursery && *start < end_nursery) {
1617 * *start can point to the middle of an object
1618 * note: should we handle pointing at the end of an object?
1619 * pinning in C# code disallows pointing at the end of an object
1620 * but there is some small chance that an optimizing C compiler
1621 * may keep the only reference to an object by pointing
1622 * at the end of it. We ignore this small chance for now.
1623 * Pointers to the end of an object are indistinguishable
1624 * from pointers to the start of the next object in memory
1625 * so if we allow that we'd need to pin two objects...
1626 * We queue the pointer in an array, the
1627 * array will then be sorted and uniqued. This way
1628 * we can coalesce several pinning pointers and it should
1629 * be faster since we'd do a memory scan with increasing
1630 * addresses. Note: we can align the address to the allocation
1631 * alignment, so the unique process is more effective.
1633 mword addr = (mword)*start;
1634 addr &= ~(ALLOC_ALIGN - 1);
1635 if (next_pin_slot >= pin_queue_size)
1636 realloc_pin_queue ();
1637 pin_queue [next_pin_slot++] = (void*)addr;
1638 DEBUG (6, if (count) fprintf (gc_debug_file, "Pinning address %p\n", (void*)addr));
1643 DEBUG (7, if (count) fprintf (gc_debug_file, "found %d potential pinned heap pointers\n", count));
1645 #ifdef HAVE_VALGRIND_MEMCHECK_H
1647 * The pinning addresses might come from undefined memory, this is normal. Since they
1648 * are used in lots of functions, we make the memory defined here instead of having
1649 * to add a supression for those functions.
1651 VALGRIND_MAKE_MEM_DEFINED (pin_queue, next_pin_slot * sizeof (pin_queue [0]));
1656 * If generation is 0, just mark objects in the nursery, the others we don't care,
1657 * since they are not going to move anyway.
1658 * There are different areas that are scanned for pinned pointers:
1659 * *) the thread stacks (when jit support is ready only the unmanaged frames)
1660 * *) the pinned handle table
1661 * *) the pinned roots
1663 * Note: when we'll use a write barrier for old to new gen references, we need to
1664 * keep track of old gen objects that point to pinned new gen objects because in that
1665 * case the referenced object will be moved maybe at the next collection, but there
1666 * is no write in the old generation area where the pinned object is referenced
1667 * and we may not consider it as reachable.
1670 mark_pinned_objects (int generation)
1675 * Debugging function: find in the conservative roots where @obj is being pinned.
1678 find_pinning_reference (char *obj, size_t size)
1682 char *endobj = obj + size;
1683 for (i = 0; i < roots_hash_size; ++i) {
1684 for (root = roots_hash [i]; root; root = root->next) {
1685 /* if desc is non-null it has precise info */
1686 if (!root->root_desc) {
1687 char ** start = (char**)root->start_root;
1688 while (start < (char**)root->end_root) {
1689 if (*start >= obj && *start < endobj) {
1690 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));
1697 find_pinning_ref_from_thread (obj, size);
1701 * The first thing we do in a collection is to identify pinned objects.
1702 * This function considers all the areas of memory that need to be
1703 * conservatively scanned.
1706 pin_from_roots (void *start_nursery, void *end_nursery)
1710 DEBUG (3, fprintf (gc_debug_file, "Scanning pinned roots (%d bytes, %d entries)\n", (int)roots_size, num_roots_entries));
1711 /* objects pinned from the API are inside these roots */
1712 for (i = 0; i < roots_hash_size; ++i) {
1713 for (root = roots_hash [i]; root; root = root->next) {
1714 /* if desc is non-null it has precise info */
1715 if (root->root_desc)
1717 DEBUG (6, fprintf (gc_debug_file, "Pinned roots %p-%p\n", root->start_root, root->end_root));
1718 conservatively_pin_objects_from ((void**)root->start_root, (void**)root->end_root, start_nursery, end_nursery);
1721 /* now deal with the thread stacks
1722 * in the future we should be able to conservatively scan only:
1723 * *) the cpu registers
1724 * *) the unmanaged stack frames
1725 * *) the _last_ managed stack frame
1726 * *) pointers slots in managed frames
1728 pin_thread_data (start_nursery, end_nursery);
1732 * The memory area from start_root to end_root contains pointers to objects.
1733 * Their position is precisely described by @desc (this means that the pointer
1734 * can be either NULL or the pointer to the start of an object).
1735 * This functions copies them to to_space updates them.
1738 precisely_scan_objects_from (void** start_root, void** end_root, char* n_start, char *n_end, mword desc)
1740 switch (desc & ROOT_DESC_TYPE_MASK) {
1741 case ROOT_DESC_BITMAP:
1742 desc >>= ROOT_DESC_TYPE_SHIFT;
1744 if ((desc & 1) && *start_root) {
1745 *start_root = copy_object (*start_root, n_start, n_end);
1746 DEBUG (9, fprintf (gc_debug_file, "Overwrote root at %p with %p\n", start_root, *start_root)); \
1752 case ROOT_DESC_RUN_LEN:
1753 case ROOT_DESC_LARGE_BITMAP:
1754 g_assert_not_reached ();
1759 alloc_fragment (void)
1761 Fragment *frag = fragment_freelist;
1763 fragment_freelist = frag->next;
1767 frag = get_internal_mem (sizeof (Fragment));
1773 * Allocate and setup the data structures needed to be able to allocate objects
1774 * in the nursery. The nursery is stored in nursery_section.
1777 alloc_nursery (void)
1779 GCMemSection *section;
1784 if (nursery_section)
1786 DEBUG (2, fprintf (gc_debug_file, "Allocating nursery size: %zd\n", nursery_size));
1787 /* later we will alloc a larger area for the nursery but only activate
1788 * what we need. The rest will be used as expansion if we have too many pinned
1789 * objects in the existing nursery.
1791 /* FIXME: handle OOM */
1792 section = get_internal_mem (sizeof (GCMemSection));
1793 data = get_os_memory (nursery_size, TRUE);
1794 nursery_start = nursery_next = data;
1795 nursery_real_end = data + nursery_size;
1796 nursery_temp_end = data + SCAN_START_SIZE;
1797 UPDATE_HEAP_BOUNDARIES (nursery_start, nursery_real_end);
1798 total_alloc += nursery_size;
1799 DEBUG (4, fprintf (gc_debug_file, "Expanding heap size: %zd, total: %zd\n", nursery_size, total_alloc));
1800 section->data = section->next_data = data;
1801 section->size = nursery_size;
1802 section->end_data = nursery_real_end;
1803 scan_starts = nursery_size / SCAN_START_SIZE;
1804 section->scan_starts = get_internal_mem (sizeof (char*) * scan_starts);
1805 section->num_scan_start = scan_starts;
1807 /* add to the section list */
1808 section->next = section_list;
1809 section_list = section;
1811 nursery_section = section;
1813 /* Setup the single first large fragment */
1814 frag = alloc_fragment ();
1815 frag->fragment_start = nursery_start;
1816 frag->fragment_limit = nursery_start;
1817 frag->fragment_end = nursery_real_end;
1818 nursery_frag_real_end = nursery_real_end;
1819 /* FIXME: frag here is lost */
1823 * Update roots in the old generation. Since we currently don't have the
1824 * info from the write barriers, we just scan all the objects.
1827 scan_old_generation (char *start, char* end)
1829 GCMemSection *section;
1831 LOSObject *big_object;
1834 for (section = section_list; section; section = section->next) {
1835 if (section == nursery_section)
1837 DEBUG (2, fprintf (gc_debug_file, "Scan of old section: %p-%p, size: %d\n", section->data, section->next_data, (int)(section->next_data - section->data)));
1838 /* we have to deal with zeroed holes in old generation (truncated strings ...) */
1840 while (p < section->next_data) {
1845 DEBUG (8, fprintf (gc_debug_file, "Precise old object scan of %p (%s)\n", p, safe_name (p)));
1846 p = scan_object (p, start, end);
1849 /* scan the old object space, too */
1850 for (big_object = los_object_list; big_object; big_object = big_object->next) {
1851 DEBUG (5, fprintf (gc_debug_file, "Scan of big object: %p (%s), size: %zd\n", big_object->data, safe_name (big_object->data), big_object->size));
1852 scan_object (big_object->data, start, end);
1854 /* scan the list of objects ready for finalization */
1855 for (fin = fin_ready_list; fin; fin = fin->next) {
1856 DEBUG (5, fprintf (gc_debug_file, "Scan of fin ready object: %p (%s)\n", fin->object, safe_name (fin->object)));
1857 fin->object = copy_object (fin->object, start, end);
1861 static mword fragment_total = 0;
1863 * We found a fragment of free memory in the nursery: memzero it and if
1864 * it is big enough, add it to the list of fragments that can be used for
1868 add_nursery_frag (size_t frag_size, char* frag_start, char* frag_end)
1871 DEBUG (4, fprintf (gc_debug_file, "Found empty fragment: %p-%p, size: %zd\n", frag_start, frag_end, frag_size));
1872 /* memsetting just the first chunk start is bound to provide better cache locality */
1873 memset (frag_start, 0, frag_size);
1874 /* Not worth dealing with smaller fragments: need to tune */
1875 if (frag_size >= FRAGMENT_MIN_SIZE) {
1876 fragment = alloc_fragment ();
1877 fragment->fragment_start = frag_start;
1878 fragment->fragment_limit = frag_start;
1879 fragment->fragment_end = frag_end;
1880 fragment->next = nursery_fragments;
1881 nursery_fragments = fragment;
1882 fragment_total += frag_size;
1887 scan_needed_big_objects (char *start_addr, char *end_addr)
1889 LOSObject *big_object;
1891 for (big_object = los_object_list; big_object; big_object = big_object->next) {
1892 if (!big_object->scanned && object_is_pinned (big_object->data)) {
1893 DEBUG (5, fprintf (gc_debug_file, "Scan of big object: %p (%s), size: %zd\n", big_object->data, safe_name (big_object->data), big_object->size));
1894 scan_object (big_object->data, start_addr, end_addr);
1895 big_object->scanned = TRUE;
1903 drain_gray_stack (char *start_addr, char *end_addr)
1907 int fin_ready, bigo_scanned_num;
1911 * We copied all the reachable objects. Now it's the time to copy
1912 * the objects that were not referenced by the roots, but by the copied objects.
1913 * we built a stack of objects pointed to by gray_start: they are
1914 * additional roots and we may add more items as we go.
1915 * We loop until gray_start == gray_objects which means no more objects have
1916 * been added. Note this is iterative: no recursion is involved.
1917 * We need to walk the LO list as well in search of marked big objects
1918 * (use a flag since this is needed only on major collections). We need to loop
1919 * here as well, so keep a counter of marked LO (increasing it in copy_object).
1922 gray_start = to_space;
1923 DEBUG (6, fprintf (gc_debug_file, "Precise scan of gray area: %p-%p, size: %d\n", gray_start, gray_objects, (int)(gray_objects - gray_start)));
1924 while (gray_start < gray_objects) {
1925 DEBUG (9, fprintf (gc_debug_file, "Precise gray object scan %p (%s)\n", gray_start, safe_name (gray_start)));
1926 gray_start = scan_object (gray_start, start_addr, end_addr);
1929 DEBUG (2, fprintf (gc_debug_file, "Gray stack scan: %d usecs\n", TV_ELAPSED (btv, atv)));
1930 //scan_old_generation (start_addr, end_addr);
1931 DEBUG (2, fprintf (gc_debug_file, "Old generation done\n"));
1932 /* walk the finalization queue and move also the objects that need to be
1933 * finalized: use the finalized objects as new roots so the objects they depend
1934 * on are also not reclaimed. As with the roots above, only objects in the nursery
1935 * are marked/copied.
1936 * We need a loop here, since objects ready for finalizers may reference other objects
1937 * that are fin-ready. Speedup with a flag?
1940 fin_ready = num_ready_finalizers;
1941 finalize_in_range (start_addr, end_addr);
1942 bigo_scanned_num = scan_needed_big_objects (start_addr, end_addr);
1944 /* drain the new stack that might have been created */
1945 DEBUG (6, fprintf (gc_debug_file, "Precise scan of gray area post fin: %p-%p, size: %d\n", gray_start, gray_objects, (int)(gray_objects - gray_start)));
1946 while (gray_start < gray_objects) {
1947 DEBUG (9, fprintf (gc_debug_file, "Precise gray object scan %p (%s)\n", gray_start, safe_name (gray_start)));
1948 gray_start = scan_object (gray_start, start_addr, end_addr);
1950 } while (fin_ready != num_ready_finalizers || bigo_scanned_num);
1952 DEBUG (2, fprintf (gc_debug_file, "Copied to old space: %d bytes\n", (int)(gray_objects - to_space)));
1953 to_space = gray_start;
1954 to_space_section->next_data = to_space;
1957 * handle disappearing links
1958 * Note we do this after checking the finalization queue because if an object
1959 * survives (at least long enough to be finalized) we don't clear the link.
1960 * This also deals with a possible issue with the monitor reclamation: with the Boehm
1961 * GC a finalized object my lose the monitor because it is cleared before the finalizer is
1964 null_link_in_range (start_addr, end_addr);
1966 DEBUG (2, fprintf (gc_debug_file, "Finalize queue handling scan: %d usecs\n", TV_ELAPSED (atv, btv)));
1969 static int last_num_pinned = 0;
1972 build_nursery_fragments (int start_pin, int end_pin, char *nursery_last_allocated)
1974 char *frag_start, *frag_end;
1978 /* FIXME: handle non-NULL fragment_freelist */
1979 fragment_freelist = nursery_fragments;
1980 nursery_fragments = NULL;
1981 frag_start = nursery_start;
1983 /* clear scan starts */
1984 memset (nursery_section->scan_starts, 0, nursery_section->num_scan_start * sizeof (gpointer));
1985 for (i = start_pin; i < end_pin; ++i) {
1986 frag_end = pin_queue [i];
1987 /* remove the pin bit from pinned objects */
1988 unpin_object (frag_end);
1989 nursery_section->scan_starts [((char*)frag_end - (char*)nursery_section->data)/SCAN_START_SIZE] = frag_end;
1990 frag_size = frag_end - frag_start;
1992 add_nursery_frag (frag_size, frag_start, frag_end);
1993 frag_size = safe_object_get_size ((MonoObject*)pin_queue [i]);
1994 frag_size += ALLOC_ALIGN - 1;
1995 frag_size &= ~(ALLOC_ALIGN - 1);
1996 frag_start = (char*)pin_queue [i] + frag_size;
1998 * pin_queue [i] might point to a half-constructed string or vector whose
1999 * length field is not set. In that case, frag_start points inside the
2000 * (zero initialized) object. Find the end of the object by scanning forward.
2003 if (is_half_constructed (pin_queue [i])) {
2004 /* Can't use nursery_next as the limit as it is modified in collect_nursery () */
2005 while ((frag_start < nursery_last_allocated) && *(mword*)frag_start == 0)
2006 frag_start += sizeof (mword);
2009 nursery_last_pinned_end = frag_start;
2010 frag_end = nursery_real_end;
2011 frag_size = frag_end - frag_start;
2013 add_nursery_frag (frag_size, frag_start, frag_end);
2014 if (!nursery_fragments) {
2015 DEBUG (1, fprintf (gc_debug_file, "Nursery fully pinned (%d)\n", end_pin - start_pin));
2016 for (i = start_pin; i < end_pin; ++i) {
2017 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])));
2023 /* FIXME: later reduce code duplication here with the above
2024 * We don't keep track of section fragments for non-nursery sections yet, so
2028 build_section_fragments (GCMemSection *section)
2031 char *frag_start, *frag_end;
2034 /* clear scan starts */
2035 memset (section->scan_starts, 0, section->num_scan_start * sizeof (gpointer));
2036 frag_start = section->data;
2037 section->next_data = section->data;
2038 for (i = section->pin_queue_start; i < section->pin_queue_end; ++i) {
2039 frag_end = pin_queue [i];
2040 /* remove the pin bit from pinned objects */
2041 unpin_object (frag_end);
2042 if (frag_end >= section->data + section->size) {
2043 frag_end = section->data + section->size;
2045 section->scan_starts [((char*)frag_end - (char*)section->data)/SCAN_START_SIZE] = frag_end;
2047 frag_size = frag_end - frag_start;
2049 memset (frag_start, 0, frag_size);
2050 frag_size = safe_object_get_size ((MonoObject*)pin_queue [i]);
2051 frag_size += ALLOC_ALIGN - 1;
2052 frag_size &= ~(ALLOC_ALIGN - 1);
2053 frag_start = (char*)pin_queue [i] + frag_size;
2054 section->next_data = MAX (section->next_data, frag_start);
2056 frag_end = section->end_data;
2057 frag_size = frag_end - frag_start;
2059 memset (frag_start, 0, frag_size);
2063 scan_from_registered_roots (char *addr_start, char *addr_end)
2067 for (i = 0; i < roots_hash_size; ++i) {
2068 for (root = roots_hash [i]; root; root = root->next) {
2069 /* if desc is non-null it has precise info */
2070 if (!root->root_desc)
2072 DEBUG (6, fprintf (gc_debug_file, "Precise root scan %p-%p (desc: %p)\n", root->start_root, root->end_root, (void*)root->root_desc));
2073 precisely_scan_objects_from ((void**)root->start_root, (void**)root->end_root, addr_start, addr_end, root->root_desc);
2079 * Collect objects in the nursery.
2082 collect_nursery (size_t requested_size)
2084 GCMemSection *section;
2085 size_t max_garbage_amount;
2087 char *nursery_last_allocated;
2088 TV_DECLARE (all_atv);
2089 TV_DECLARE (all_btv);
2094 nursery_last_allocated = nursery_next;
2095 nursery_next = MAX (nursery_next, nursery_last_pinned_end);
2096 /* FIXME: optimize later to use the higher address where an object can be present */
2097 nursery_next = MAX (nursery_next, nursery_real_end);
2099 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)));
2100 max_garbage_amount = nursery_next - nursery_start;
2102 * not enough room in the old generation to store all the possible data from
2103 * the nursery in a single continuous space.
2104 * We reset to_space if we allocated objects in degraded mode.
2106 if (to_space_section)
2107 to_space = gray_objects = to_space_section->next_data;
2108 if ((to_space_end - to_space) < max_garbage_amount) {
2109 section = alloc_section (nursery_section->size * 4);
2110 g_assert (nursery_section->size >= max_garbage_amount);
2111 to_space = gray_objects = section->next_data;
2112 to_space_end = section->end_data;
2113 to_space_section = section;
2115 DEBUG (2, fprintf (gc_debug_file, "To space setup: %p-%p in section %p\n", to_space, to_space_end, to_space_section));
2116 nursery_section->next_data = nursery_next;
2119 mono_stats.minor_gc_count ++;
2120 /* world must be stopped already */
2121 TV_GETTIME (all_atv);
2123 /* pin from pinned handles */
2124 pin_from_roots (nursery_start, nursery_next);
2125 /* identify pinned objects */
2126 optimize_pin_queue (0);
2127 next_pin_slot = pin_objects_from_addresses (nursery_section, pin_queue, pin_queue + next_pin_slot, nursery_start, nursery_next);
2129 DEBUG (2, fprintf (gc_debug_file, "Finding pinned pointers: %d in %d usecs\n", next_pin_slot, TV_ELAPSED (atv, btv)));
2130 DEBUG (4, fprintf (gc_debug_file, "Start scan with %d pinned objects\n", next_pin_slot));
2133 * walk all the roots and copy the young objects to the old generation,
2134 * starting from to_space
2137 scan_from_remsets (nursery_start, nursery_next);
2138 /* we don't have complete write barrier yet, so we scan all the old generation sections */
2140 DEBUG (2, fprintf (gc_debug_file, "Old generation scan: %d usecs\n", TV_ELAPSED (btv, atv)));
2141 /* FIXME: later scan also alloc_pinned objects */
2143 /* the pinned objects are roots */
2144 for (i = 0; i < next_pin_slot; ++i) {
2145 DEBUG (6, fprintf (gc_debug_file, "Precise object scan %d of pinned %p (%s)\n", i, pin_queue [i], safe_name (pin_queue [i])));
2146 scan_object (pin_queue [i], nursery_start, nursery_next);
2148 /* registered roots, this includes static fields */
2149 scan_from_registered_roots (nursery_start, nursery_next);
2151 DEBUG (2, fprintf (gc_debug_file, "Root scan: %d usecs\n", TV_ELAPSED (atv, btv)));
2153 drain_gray_stack (nursery_start, nursery_next);
2155 /* walk the pin_queue, build up the fragment list of free memory, unmark
2156 * pinned objects as we go, memzero() the empty fragments so they are ready for the
2159 build_nursery_fragments (0, next_pin_slot, nursery_last_allocated);
2161 DEBUG (2, fprintf (gc_debug_file, "Fragment creation: %d usecs, %zd bytes available\n", TV_ELAPSED (btv, atv), fragment_total));
2163 TV_GETTIME (all_btv);
2164 mono_stats.minor_gc_time_usecs += TV_ELAPSED (all_atv, all_btv);
2166 /* prepare the pin queue for the next collection */
2167 last_num_pinned = next_pin_slot;
2169 if (fin_ready_list) {
2170 DEBUG (4, fprintf (gc_debug_file, "Finalizer-thread wakeup: ready %d\n", num_ready_finalizers));
2171 mono_gc_finalize_notify ();
2176 major_collection (void)
2178 GCMemSection *section, *prev_section;
2179 LOSObject *bigobj, *prevbo;
2184 TV_DECLARE (all_atv);
2185 TV_DECLARE (all_btv);
2188 /* FIXME: only use these values for the precise scan
2189 * note that to_space pointers should be excluded anyway...
2191 char *heap_start = NULL;
2192 char *heap_end = (char*)-1;
2193 size_t copy_space_required = 0;
2196 DEBUG (1, fprintf (gc_debug_file, "Start major collection %d\n", num_major_gcs));
2198 mono_stats.major_gc_count ++;
2200 * FIXME: implement Mark/Compact
2201 * Until that is done, we can just apply mostly the same alg as for the nursery:
2202 * this means we need a big section to potentially copy all the other sections, so
2203 * it is not ideal specially with large heaps.
2205 if (g_getenv ("MONO_GC_NO_MAJOR")) {
2206 collect_nursery (0);
2209 TV_GETTIME (all_atv);
2210 /* FIXME: make sure the nursery next_data ptr is updated */
2211 nursery_section->next_data = nursery_real_end;
2212 /* we should also coalesce scanning from sections close to each other
2213 * and deal with pointers outside of the sections later.
2215 /* The remsets are not useful for a major collection */
2217 /* world must be stopped already */
2219 DEBUG (6, fprintf (gc_debug_file, "Pinning from sections\n"));
2220 for (section = section_list; section; section = section->next) {
2221 section->pin_queue_start = count = section->pin_queue_end = next_pin_slot;
2222 pin_from_roots (section->data, section->next_data);
2223 if (count != next_pin_slot) {
2225 optimize_pin_queue (count);
2226 DEBUG (6, fprintf (gc_debug_file, "Found %d pinning addresses in section %p (%d-%d)\n", next_pin_slot - count, section, count, next_pin_slot));
2227 reduced_to = pin_objects_from_addresses (section, pin_queue + count, pin_queue + next_pin_slot, section->data, section->next_data);
2228 section->pin_queue_end = next_pin_slot = count + reduced_to;
2230 copy_space_required += (char*)section->next_data - (char*)section->data;
2232 /* identify possible pointers to the insize of large objects */
2233 DEBUG (6, fprintf (gc_debug_file, "Pinning from large objects\n"));
2234 for (bigobj = los_object_list; bigobj; bigobj = bigobj->next) {
2235 count = next_pin_slot;
2236 pin_from_roots (bigobj->data, (char*)bigobj->data + bigobj->size);
2237 /* FIXME: this is only valid until we don't optimize the pin queue midway */
2238 if (next_pin_slot != count) {
2239 next_pin_slot = count;
2240 pin_object (bigobj->data);
2241 DEBUG (6, fprintf (gc_debug_file, "Marked large object %p (%s) size: %zd from roots\n", bigobj->data, safe_name (bigobj->data), bigobj->size));
2244 /* look for pinned addresses for pinned-alloc objects */
2245 DEBUG (6, fprintf (gc_debug_file, "Pinning from pinned-alloc objects\n"));
2246 for (chunk = pinned_chunk_list; chunk; chunk = chunk->next) {
2247 count = next_pin_slot;
2248 pin_from_roots (chunk->start_data, (char*)chunk + chunk->num_pages * FREELIST_PAGESIZE);
2249 /* FIXME: this is only valid until we don't optimize the pin queue midway */
2250 if (next_pin_slot != count) {
2251 mark_pinned_from_addresses (chunk, pin_queue + count, pin_queue + next_pin_slot);
2252 next_pin_slot = count;
2257 DEBUG (2, fprintf (gc_debug_file, "Finding pinned pointers: %d in %d usecs\n", next_pin_slot, TV_ELAPSED (atv, btv)));
2258 DEBUG (4, fprintf (gc_debug_file, "Start scan with %d pinned objects\n", next_pin_slot));
2260 /* allocate the big to space */
2261 DEBUG (4, fprintf (gc_debug_file, "Allocate tospace for size: %zd\n", copy_space_required));
2262 section = alloc_section (copy_space_required);
2263 to_space = gray_objects = section->next_data;
2264 to_space_end = section->end_data;
2265 to_space_section = section;
2267 /* the old generation doesn't need to be scanned (no remembered sets or card
2268 * table needed either): the only objects that must survive are those pinned and
2269 * those referenced by the precise roots.
2270 * mark any section without pinned objects, so we can free it since we will be able to
2271 * move all the objects.
2273 /* the pinned objects are roots (big objects are included in this list, too) */
2274 for (i = 0; i < next_pin_slot; ++i) {
2275 DEBUG (6, fprintf (gc_debug_file, "Precise object scan %d of pinned %p (%s)\n", i, pin_queue [i], safe_name (pin_queue [i])));
2276 scan_object (pin_queue [i], heap_start, heap_end);
2278 /* registered roots, this includes static fields */
2279 scan_from_registered_roots (heap_start, heap_end);
2281 /* scan the list of objects ready for finalization */
2282 for (fin = fin_ready_list; fin; fin = fin->next) {
2283 DEBUG (5, fprintf (gc_debug_file, "Scan of fin ready object: %p (%s)\n", fin->object, safe_name (fin->object)));
2284 fin->object = copy_object (fin->object, heap_start, heap_end);
2287 DEBUG (2, fprintf (gc_debug_file, "Root scan: %d usecs\n", TV_ELAPSED (btv, atv)));
2289 /* we need to go over the big object list to see if any was marked and scan it
2290 * And we need to make this in a loop, considering that objects referenced by finalizable
2291 * objects could reference big objects (this happens in drain_gray_stack ())
2293 scan_needed_big_objects (heap_start, heap_end);
2294 /* all the objects in the heap */
2295 drain_gray_stack (heap_start, heap_end);
2297 /* sweep the big objects list */
2299 for (bigobj = los_object_list; bigobj;) {
2300 if (object_is_pinned (bigobj->data)) {
2301 unpin_object (bigobj->data);
2302 bigobj->scanned = FALSE;
2305 /* not referenced anywhere, so we can free it */
2307 prevbo->next = bigobj->next;
2309 los_object_list = bigobj->next;
2311 bigobj = bigobj->next;
2312 free_large_object (to_free);
2316 bigobj = bigobj->next;
2318 /* unpin objects from the pinned chunks and free the unmarked ones */
2319 sweep_pinned_objects ();
2321 /* free the unused sections */
2322 prev_section = NULL;
2323 for (section = section_list; section;) {
2324 /* to_space doesn't need handling here and the nursery is special */
2325 if (section == to_space_section || section == nursery_section) {
2326 prev_section = section;
2327 section = section->next;
2330 /* no pinning object, so the section is free */
2331 if (section->pin_queue_start == section->pin_queue_end) {
2332 GCMemSection *to_free;
2334 prev_section->next = section->next;
2336 section_list = section->next;
2338 section = section->next;
2339 free_mem_section (to_free);
2342 DEBUG (6, fprintf (gc_debug_file, "Section %p has still pinned objects (%d)\n", section, section->pin_queue_end - section->pin_queue_start));
2343 build_section_fragments (section);
2345 prev_section = section;
2346 section = section->next;
2349 /* walk the pin_queue, build up the fragment list of free memory, unmark
2350 * pinned objects as we go, memzero() the empty fragments so they are ready for the
2353 build_nursery_fragments (nursery_section->pin_queue_start, nursery_section->pin_queue_end, nursery_next);
2355 TV_GETTIME (all_btv);
2356 mono_stats.major_gc_time_usecs += TV_ELAPSED (all_atv, all_btv);
2357 /* prepare the pin queue for the next collection */
2359 if (fin_ready_list) {
2360 DEBUG (4, fprintf (gc_debug_file, "Finalizer-thread wakeup: ready %d\n", num_ready_finalizers));
2361 mono_gc_finalize_notify ();
2366 * Allocate a new section of memory to be used as old generation.
2368 static GCMemSection*
2369 alloc_section (size_t size)
2371 GCMemSection *section;
2374 size_t new_size = next_section_size;
2376 if (size > next_section_size) {
2378 new_size += pagesize - 1;
2379 new_size &= ~(pagesize - 1);
2381 section_size_used++;
2382 if (section_size_used > 3) {
2383 section_size_used = 0;
2384 next_section_size *= 2;
2385 if (next_section_size > max_section_size)
2386 next_section_size = max_section_size;
2388 section = get_internal_mem (sizeof (GCMemSection));
2389 data = get_os_memory (new_size, TRUE);
2390 section->data = section->next_data = data;
2391 section->size = new_size;
2392 section->end_data = data + new_size;
2393 UPDATE_HEAP_BOUNDARIES (data, section->end_data);
2394 total_alloc += new_size;
2395 DEBUG (2, fprintf (gc_debug_file, "Expanding heap size: %zd, total: %zd\n", new_size, total_alloc));
2396 section->data = data;
2397 section->size = new_size;
2398 scan_starts = new_size / SCAN_START_SIZE;
2399 section->scan_starts = get_internal_mem (sizeof (char*) * scan_starts);
2400 section->num_scan_start = scan_starts;
2402 /* add to the section list */
2403 section->next = section_list;
2404 section_list = section;
2410 free_mem_section (GCMemSection *section)
2412 char *data = section->data;
2413 size_t size = section->size;
2414 DEBUG (2, fprintf (gc_debug_file, "Freed section %p, size %zd\n", data, size));
2415 free_os_memory (data, size);
2416 free_internal_mem (section);
2417 total_alloc -= size;
2421 * When deciding if it's better to collect or to expand, keep track
2422 * of how much garbage was reclaimed with the last collection: if it's too
2424 * This is called when we could not allocate a small object.
2426 static void __attribute__((noinline))
2427 minor_collect_or_expand_inner (size_t size)
2429 int do_minor_collection = 1;
2431 if (!nursery_section) {
2435 if (do_minor_collection) {
2437 collect_nursery (size);
2438 DEBUG (2, fprintf (gc_debug_file, "Heap size: %zd, LOS size: %zd\n", total_alloc, los_memory_usage));
2440 /* this also sets the proper pointers for the next allocation */
2441 if (!search_fragment_for_size (size)) {
2443 /* TypeBuilder and MonoMethod are killing mcs with fragmentation */
2444 DEBUG (1, fprintf (gc_debug_file, "nursery collection didn't find enough room for %zd alloc (%d pinned)", size, last_num_pinned));
2445 for (i = 0; i < last_num_pinned; ++i) {
2446 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])));
2451 //report_internal_mem_usage ();
2455 * ######################################################################
2456 * ######## Memory allocation from the OS
2457 * ######################################################################
2458 * This section of code deals with getting memory from the OS and
2459 * allocating memory for GC-internal data structures.
2460 * Internal memory can be handled with a freelist for small objects.
2464 * Allocate a big chunk of memory from the OS (usually 64KB to several megabytes).
2465 * This must not require any lock.
2468 get_os_memory (size_t size, int activate)
2471 unsigned long prot_flags = activate? MONO_MMAP_READ|MONO_MMAP_WRITE: MONO_MMAP_NONE;
2473 prot_flags |= MONO_MMAP_PRIVATE | MONO_MMAP_ANON;
2474 size += pagesize - 1;
2475 size &= ~(pagesize - 1);
2476 ptr = mono_valloc (0, size, prot_flags);
2481 * Free the memory returned by get_os_memory (), returning it to the OS.
2484 free_os_memory (void *addr, size_t size)
2486 munmap (addr, size);
2493 report_pinned_chunk (PinnedChunk *chunk, int seq) {
2495 int i, free_pages, num_free, free_mem;
2497 for (i = 0; i < chunk->num_pages; ++i) {
2498 if (!chunk->page_sizes [i])
2501 printf ("Pinned chunk %d at %p, size: %d, pages: %d, free: %d\n", seq, chunk, chunk->num_pages * FREELIST_PAGESIZE, chunk->num_pages, free_pages);
2502 free_mem = FREELIST_PAGESIZE * free_pages;
2503 for (i = 0; i < FREELIST_NUM_SLOTS; ++i) {
2504 if (!chunk->free_list [i])
2507 p = chunk->free_list [i];
2512 printf ("\tfree list of size %d, %d items\n", freelist_sizes [i], num_free);
2513 free_mem += freelist_sizes [i] * num_free;
2515 printf ("\tfree memory in chunk: %d\n", free_mem);
2522 report_internal_mem_usage (void) {
2525 printf ("Internal memory usage:\n");
2527 for (chunk = internal_chunk_list; chunk; chunk = chunk->next) {
2528 report_pinned_chunk (chunk, i++);
2530 printf ("Pinned memory usage:\n");
2532 for (chunk = pinned_chunk_list; chunk; chunk = chunk->next) {
2533 report_pinned_chunk (chunk, i++);
2538 * the array of pointers from @start to @end contains conservative
2539 * pointers to objects inside @chunk: mark each referenced object
2543 mark_pinned_from_addresses (PinnedChunk *chunk, void **start, void **end)
2545 for (; start < end; start++) {
2546 char *addr = *start;
2547 int offset = (char*)addr - (char*)chunk;
2548 int page = offset / FREELIST_PAGESIZE;
2549 int obj_offset = page == 0? offset - ((char*)chunk->start_data - (char*)chunk): offset % FREELIST_PAGESIZE;
2550 int slot_size = chunk->page_sizes [page];
2552 /* the page is not allocated */
2555 /* would be faster if we restrict the sizes to power of two,
2556 * but that's a waste of memory: need to measure. it could reduce
2557 * fragmentation since there are less pages needed, if for example
2558 * someone interns strings of each size we end up with one page per
2559 * interned string (still this is just ~40 KB): with more fine-grained sizes
2560 * this increases the number of used pages.
2563 obj_offset /= slot_size;
2564 obj_offset *= slot_size;
2565 addr = (char*)chunk->start_data + obj_offset;
2567 obj_offset /= slot_size;
2568 obj_offset *= slot_size;
2569 addr = (char*)chunk + page * FREELIST_PAGESIZE + obj_offset;
2572 /* if the vtable is inside the chunk it's on the freelist, so skip */
2573 if (*ptr && (*ptr < (void*)chunk->start_data || *ptr > (void*)((char*)chunk + chunk->num_pages * FREELIST_PAGESIZE))) {
2575 DEBUG (6, fprintf (gc_debug_file, "Marked pinned object %p (%s) from roots\n", addr, safe_name (addr)));
2581 sweep_pinned_objects (void)
2588 for (chunk = pinned_chunk_list; chunk; chunk = chunk->next) {
2589 end_chunk = (char*)chunk + chunk->num_pages * FREELIST_PAGESIZE;
2590 DEBUG (6, fprintf (gc_debug_file, "Sweeping pinned chunk %p (ranhe: %p-%p)\n", chunk, chunk->start_data, end_chunk));
2591 for (i = 0; i < chunk->num_pages; ++i) {
2592 obj_size = chunk->page_sizes [i];
2595 p = i? (char*)chunk + i * FREELIST_PAGESIZE: chunk->start_data;
2596 endp = i? p + FREELIST_PAGESIZE: (char*)chunk + FREELIST_PAGESIZE;
2597 DEBUG (6, fprintf (gc_debug_file, "Page %d (size: %d, range: %p-%p)\n", i, obj_size, p, endp));
2598 while (p + obj_size <= endp) {
2600 DEBUG (9, fprintf (gc_debug_file, "Considering %p (vtable: %p)\n", ptr, *ptr));
2601 /* if the first word (the vtable) is outside the chunk we have an object */
2602 if (*ptr && (*ptr < (void*)chunk || *ptr >= end_chunk)) {
2603 if (object_is_pinned (ptr)) {
2605 DEBUG (6, fprintf (gc_debug_file, "Unmarked pinned object %p (%s)\n", ptr, safe_name (ptr)));
2607 /* FIXME: add to freelist */
2608 DEBUG (6, fprintf (gc_debug_file, "Going to free unmarked pinned object %p (%s)\n", ptr, safe_name (ptr)));
2618 * Find the slot number in the freelist for memory chunks that
2619 * can contain @size objects.
2622 slot_for_size (size_t size)
2625 /* do a binary search or lookup table later. */
2626 for (slot = 0; slot < FREELIST_NUM_SLOTS; ++slot) {
2627 if (freelist_sizes [slot] >= size)
2630 g_assert_not_reached ();
2635 * Build a free list for @size memory chunks from the memory area between
2636 * start_page and end_page.
2639 build_freelist (PinnedChunk *chunk, int slot, int size, char *start_page, char *end_page)
2643 /*g_print ("building freelist for slot %d, size %d in %p\n", slot, size, chunk);*/
2644 p = (void**)start_page;
2645 end = (void**)(end_page - size);
2646 g_assert (!chunk->free_list [slot]);
2647 chunk->free_list [slot] = p;
2648 while ((char*)p + size <= (char*)end) {
2650 *p = (void*)((char*)p + size);
2654 /*g_print ("%d items created, max: %d\n", count, (end_page - start_page) / size);*/
2658 alloc_pinned_chunk (size_t size)
2663 size += pagesize; /* at least one page */
2664 size += pagesize - 1;
2665 size &= ~(pagesize - 1);
2666 if (size < PINNED_CHUNK_MIN_SIZE * 2)
2667 size = PINNED_CHUNK_MIN_SIZE * 2;
2668 chunk = get_os_memory (size, TRUE);
2669 UPDATE_HEAP_BOUNDARIES (chunk, ((char*)chunk + size));
2670 total_alloc += size;
2672 /* setup the bookeeping fields */
2673 chunk->num_pages = size / FREELIST_PAGESIZE;
2674 offset = G_STRUCT_OFFSET (PinnedChunk, data);
2675 chunk->page_sizes = (void*)((char*)chunk + offset);
2676 offset += sizeof (int) * chunk->num_pages;
2677 offset += ALLOC_ALIGN - 1;
2678 offset &= ~(ALLOC_ALIGN - 1);
2679 chunk->free_list = (void*)((char*)chunk + offset);
2680 offset += sizeof (void*) * FREELIST_NUM_SLOTS;
2681 offset += ALLOC_ALIGN - 1;
2682 offset &= ~(ALLOC_ALIGN - 1);
2683 chunk->start_data = (void*)((char*)chunk + offset);
2685 /* allocate the first page to the freelist */
2686 chunk->page_sizes [0] = PINNED_FIRST_SLOT_SIZE;
2687 build_freelist (chunk, slot_for_size (PINNED_FIRST_SLOT_SIZE), PINNED_FIRST_SLOT_SIZE, chunk->start_data, ((char*)chunk + FREELIST_PAGESIZE));
2688 DEBUG (4, fprintf (gc_debug_file, "Allocated pinned chunk %p, size: %zd\n", chunk, size));
2689 min_pinned_chunk_addr = MIN (min_pinned_chunk_addr, (char*)chunk->start_data);
2690 max_pinned_chunk_addr = MAX (max_pinned_chunk_addr, ((char*)chunk + size));
2694 /* assumes freelist for slot is empty, so try to alloc a new page */
2696 get_chunk_freelist (PinnedChunk *chunk, int slot)
2700 p = chunk->free_list [slot];
2702 chunk->free_list [slot] = *p;
2705 for (i = 0; i < chunk->num_pages; ++i) {
2707 if (chunk->page_sizes [i])
2709 size = freelist_sizes [slot];
2710 chunk->page_sizes [i] = size;
2711 build_freelist (chunk, slot, size, (char*)chunk + FREELIST_PAGESIZE * i, (char*)chunk + FREELIST_PAGESIZE * (i + 1));
2715 p = chunk->free_list [slot];
2717 chunk->free_list [slot] = *p;
2724 alloc_from_freelist (size_t size)
2728 PinnedChunk *pchunk;
2729 slot = slot_for_size (size);
2730 /*g_print ("using slot %d for size %d (slot size: %d)\n", slot, size, freelist_sizes [slot]);*/
2731 g_assert (size <= freelist_sizes [slot]);
2732 for (pchunk = pinned_chunk_list; pchunk; pchunk = pchunk->next) {
2733 void **p = pchunk->free_list [slot];
2735 /*g_print ("found freelist for slot %d in chunk %p, returning %p, next %p\n", slot, pchunk, p, *p);*/
2736 pchunk->free_list [slot] = *p;
2740 for (pchunk = pinned_chunk_list; pchunk; pchunk = pchunk->next) {
2741 res = get_chunk_freelist (pchunk, slot);
2745 pchunk = alloc_pinned_chunk (size);
2746 /* FIXME: handle OOM */
2747 pchunk->next = pinned_chunk_list;
2748 pinned_chunk_list = pchunk;
2749 res = get_chunk_freelist (pchunk, slot);
2753 /* used for the GC-internal data structures */
2754 /* FIXME: add support for bigger sizes by allocating more than one page
2758 get_internal_mem (size_t size)
2760 return calloc (1, size);
2764 PinnedChunk *pchunk;
2765 slot = slot_for_size (size);
2766 g_assert (size <= freelist_sizes [slot]);
2767 for (pchunk = internal_chunk_list; pchunk; pchunk = pchunk->next) {
2768 void **p = pchunk->free_list [slot];
2770 pchunk->free_list [slot] = *p;
2774 for (pchunk = internal_chunk_list; pchunk; pchunk = pchunk->next) {
2775 res = get_chunk_freelist (pchunk, slot);
2779 pchunk = alloc_pinned_chunk (size);
2780 /* FIXME: handle OOM */
2781 pchunk->next = internal_chunk_list;
2782 internal_chunk_list = pchunk;
2783 res = get_chunk_freelist (pchunk, slot);
2789 free_internal_mem (void *addr)
2793 PinnedChunk *pchunk;
2794 for (pchunk = internal_chunk_list; pchunk; pchunk = pchunk->next) {
2795 /*printf ("trying to free %p in %p (pages: %d)\n", addr, pchunk, pchunk->num_pages);*/
2796 if (addr >= (void*)pchunk && (char*)addr < (char*)pchunk + pchunk->num_pages * FREELIST_PAGESIZE) {
2797 int offset = (char*)addr - (char*)pchunk;
2798 int page = offset / FREELIST_PAGESIZE;
2799 int slot = slot_for_size (pchunk->page_sizes [page]);
2801 *p = pchunk->free_list [slot];
2802 pchunk->free_list [slot] = p;
2806 printf ("free of %p failed\n", addr);
2807 g_assert_not_reached ();
2812 * ######################################################################
2813 * ######## Object allocation
2814 * ######################################################################
2815 * This section of code deals with allocating memory for objects.
2816 * There are several ways:
2817 * *) allocate large objects
2818 * *) allocate normal objects
2819 * *) fast lock-free allocation
2820 * *) allocation of pinned objects
2824 free_large_object (LOSObject *obj)
2826 size_t size = obj->size;
2827 DEBUG (4, fprintf (gc_debug_file, "Freed large object %p, size %zd\n", obj->data, obj->size));
2829 los_memory_usage -= size;
2830 size += sizeof (LOSObject);
2831 size += pagesize - 1;
2832 size &= ~(pagesize - 1);
2833 total_alloc -= size;
2835 free_os_memory (obj, size);
2839 * Objects with size >= 64KB are allocated in the large object space.
2840 * They are currently kept track of with a linked list.
2841 * They don't move, so there is no need to pin them during collection
2842 * and we avoid the memcpy overhead.
2844 static void* __attribute__((noinline))
2845 alloc_large_inner (MonoVTable *vtable, size_t size)
2850 int just_did_major_gc = FALSE;
2852 if (los_memory_usage > next_los_collection) {
2853 DEBUG (4, fprintf (gc_debug_file, "Should trigger major collection: req size %zd (los already: %zu, limit: %zu)\n", size, los_memory_usage, next_los_collection));
2854 just_did_major_gc = TRUE;
2856 major_collection ();
2858 /* later increase based on a percent of the heap size */
2859 next_los_collection = los_memory_usage + 5*1024*1024;
2862 alloc_size += sizeof (LOSObject);
2863 alloc_size += pagesize - 1;
2864 alloc_size &= ~(pagesize - 1);
2865 /* FIXME: handle OOM */
2866 obj = get_os_memory (alloc_size, TRUE);
2868 vtslot = (void**)obj->data;
2870 total_alloc += alloc_size;
2871 UPDATE_HEAP_BOUNDARIES (obj->data, (char*)obj->data + size);
2872 obj->next = los_object_list;
2873 los_object_list = obj;
2874 los_memory_usage += size;
2876 DEBUG (4, fprintf (gc_debug_file, "Allocated large object %p, vtable: %p (%s), size: %zd\n", obj->data, vtable, vtable->klass->name, size));
2880 /* check if we have a suitable fragment in nursery_fragments to be able to allocate
2881 * an object of size @size
2882 * Return FALSE if not found (which means we need a collection)
2885 search_fragment_for_size (size_t size)
2887 Fragment *frag, *prev;
2888 DEBUG (4, fprintf (gc_debug_file, "Searching nursery fragment %p, size: %zd\n", nursery_frag_real_end, size));
2890 for (frag = nursery_fragments; frag; frag = frag->next) {
2891 if (size <= (frag->fragment_end - frag->fragment_start)) {
2892 /* remove from the list */
2894 prev->next = frag->next;
2896 nursery_fragments = frag->next;
2897 nursery_next = frag->fragment_start;
2898 nursery_frag_real_end = frag->fragment_end;
2899 nursery_temp_end = MIN (nursery_frag_real_end, nursery_next + size + SCAN_START_SIZE);
2901 DEBUG (4, fprintf (gc_debug_file, "Using nursery fragment %p-%p, size: %zd (req: %zd)\n", nursery_next, nursery_frag_real_end, nursery_frag_real_end - nursery_next, size));
2902 frag->next = fragment_freelist;
2903 fragment_freelist = frag;
2912 * size is already rounded up and we hold the GC lock.
2915 alloc_degraded (MonoVTable *vtable, size_t size)
2917 GCMemSection *section;
2919 for (section = section_list; section; section = section->next) {
2920 if (section != nursery_section && (section->end_data - section->next_data) >= size) {
2921 p = (void**)section->next_data;
2926 section = alloc_section (nursery_section->size * 4);
2927 /* FIXME: handle OOM */
2928 p = (void**)section->next_data;
2930 section->next_data += size;
2931 degraded_mode += size;
2932 DEBUG (3, fprintf (gc_debug_file, "Allocated (degraded) object %p, vtable: %p (%s), size: %zd in section %p\n", p, vtable, vtable->klass->name, size, section));
2938 * Provide a variant that takes just the vtable for small fixed-size objects.
2939 * The aligned size is already computed and stored in vt->gc_descr.
2940 * Note: every SCAN_START_SIZE or so we are given the chance to do some special
2941 * processing. We can keep track of where objects start, for example,
2942 * so when we scan the thread stacks for pinned objects, we can start
2943 * a search for the pinned object in SCAN_START_SIZE chunks.
2946 mono_gc_alloc_obj (MonoVTable *vtable, size_t size)
2948 /* FIXME: handle OOM */
2951 size += ALLOC_ALIGN - 1;
2952 size &= ~(ALLOC_ALIGN - 1);
2954 g_assert (vtable->gc_descr);
2957 p = (void**)nursery_next;
2958 /* FIXME: handle overflow */
2959 nursery_next += size;
2960 if (nursery_next >= nursery_temp_end) {
2961 /* there are two cases: the object is too big or we need to collect */
2962 /* there can be another case (from ORP), if we cooperate with the runtime a bit:
2963 * objects that need finalizers can have the high bit set in their size
2964 * so the above check fails and we can readily add the object to the queue.
2965 * This avoids taking again the GC lock when registering, but this is moot when
2966 * doing thread-local allocation, so it may not be a good idea.
2968 if (size > MAX_SMALL_OBJ_SIZE) {
2969 /* get ready for possible collection */
2970 update_current_thread_stack (&dummy);
2971 nursery_next -= size;
2972 p = alloc_large_inner (vtable, size);
2974 if (nursery_next >= nursery_frag_real_end) {
2975 nursery_next -= size;
2976 /* when running in degraded mode, we continue allocing that way
2977 * for a while, to decrease the number of useless nursery collections.
2979 if (degraded_mode && degraded_mode < DEFAULT_NURSERY_SIZE) {
2980 p = alloc_degraded (vtable, size);
2984 if (!search_fragment_for_size (size)) {
2985 /* get ready for possible collection */
2986 update_current_thread_stack (&dummy);
2987 minor_collect_or_expand_inner (size);
2988 if (degraded_mode) {
2989 p = alloc_degraded (vtable, size);
2994 /* nursery_next changed by minor_collect_or_expand_inner () */
2995 p = (void*)nursery_next;
2996 nursery_next += size;
2997 if (nursery_next > nursery_temp_end) {
3002 /* record the scan start so we can find pinned objects more easily */
3003 nursery_section->scan_starts [((char*)p - (char*)nursery_section->data)/SCAN_START_SIZE] = (char*)p;
3004 /* we just bump nursery_temp_end as well */
3005 nursery_temp_end = MIN (nursery_frag_real_end, nursery_next + SCAN_START_SIZE);
3006 DEBUG (5, fprintf (gc_debug_file, "Expanding local alloc: %p-%p\n", nursery_next, nursery_temp_end));
3010 DEBUG (6, fprintf (gc_debug_file, "Allocated object %p, vtable: %p (%s), size: %zd\n", p, vtable, vtable->klass->name, size));
3019 * To be used for interned strings and possibly MonoThread, reflection handles.
3020 * We may want to explicitly free these objects.
3023 mono_gc_alloc_pinned_obj (MonoVTable *vtable, size_t size)
3025 /* FIXME: handle OOM */
3027 size += ALLOC_ALIGN - 1;
3028 size &= ~(ALLOC_ALIGN - 1);
3030 if (size > MAX_FREELIST_SIZE) {
3031 update_current_thread_stack (&p);
3032 /* large objects are always pinned anyway */
3033 p = alloc_large_inner (vtable, size);
3035 p = alloc_from_freelist (size);
3036 memset (p, 0, size);
3038 DEBUG (6, fprintf (gc_debug_file, "Allocated pinned object %p, vtable: %p (%s), size: %zd\n", p, vtable, vtable->klass->name, size));
3045 * ######################################################################
3046 * ######## Finalization support
3047 * ######################################################################
3051 * this is valid for the nursery: if the object has been forwarded it means it's
3052 * still refrenced from a root. If it is pinned it's still alive as well.
3053 * Return TRUE if @obj is ready to be finalized.
3055 #define object_is_fin_ready(obj) (!object_is_pinned (obj) && !object_is_forwarded (obj))
3058 finalize_in_range (char *start, char *end)
3060 FinalizeEntry *entry, *prev;
3064 for (i = 0; i < finalizable_hash_size; ++i) {
3066 for (entry = finalizable_hash [i]; entry;) {
3067 if ((char*)entry->object >= start && (char*)entry->object < end && ((char*)entry->object < to_space || (char*)entry->object >= to_space_end)) {
3068 if (object_is_fin_ready (entry->object)) {
3070 FinalizeEntry *next;
3071 /* remove and put in fin_ready_list */
3073 prev->next = entry->next;
3075 finalizable_hash [i] = entry->next;
3077 num_ready_finalizers++;
3078 num_registered_finalizers--;
3079 entry->next = fin_ready_list;
3080 fin_ready_list = entry;
3081 /* Make it survive */
3082 from = entry->object;
3083 entry->object = copy_object (entry->object, start, end);
3084 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, num_registered_finalizers));
3088 /* update pointer */
3089 DEBUG (5, fprintf (gc_debug_file, "Updating object for finalization: %p (%s)\n", entry->object, safe_name (entry->object)));
3090 entry->object = copy_object (entry->object, start, end);
3094 entry = entry->next;
3100 null_link_in_range (char *start, char *end)
3102 FinalizeEntry *entry, *prev;
3104 for (i = 0; i < disappearing_link_hash_size; ++i) {
3106 for (entry = disappearing_link_hash [i]; entry;) {
3107 if ((char*)entry->object >= start && (char*)entry->object < end && ((char*)entry->object < to_space || (char*)entry->object >= to_space_end)) {
3108 if (object_is_fin_ready (entry->object)) {
3109 void **p = entry->data;
3112 /* remove from list */
3114 prev->next = entry->next;
3116 disappearing_link_hash [i] = entry->next;
3117 DEBUG (5, fprintf (gc_debug_file, "Dislink nullified at %p to GCed object %p\n", p, entry->object));
3119 free_internal_mem (entry);
3121 num_disappearing_links--;
3125 /* update pointer if it's moved
3126 * FIXME: what if an object is moved earlier?
3128 entry->object = copy_object (entry->object, start, end);
3129 DEBUG (5, fprintf (gc_debug_file, "Updated dislink at %p to %p\n", entry->data, entry->object));
3131 *link = entry->object;
3135 entry = entry->next;
3141 * mono_gc_finalizers_for_domain:
3142 * @domain: the unloading appdomain
3143 * @out_array: output array
3144 * @out_size: size of output array
3146 * Store inside @out_array up to @out_size objects that belong to the unloading
3147 * appdomain @domain. Returns the number of stored items. Can be called repeteadly
3148 * until it returns 0.
3149 * The items are removed from the finalizer data structure, so the caller is supposed
3151 * @out_array should be on the stack to allow the GC to know the objects are still alive.
3154 mono_gc_finalizers_for_domain (MonoDomain *domain, MonoObject **out_array, int out_size)
3156 FinalizeEntry *entry, *prev;
3158 if (no_finalize || !out_size || !out_array)
3162 for (i = 0; i < finalizable_hash_size; ++i) {
3164 for (entry = finalizable_hash [i]; entry;) {
3165 if (mono_object_domain (entry->object) == domain) {
3166 FinalizeEntry *next;
3167 /* remove and put in out_array */
3169 prev->next = entry->next;
3171 finalizable_hash [i] = entry->next;
3173 num_registered_finalizers--;
3174 out_array [count ++] = entry->object;
3175 DEBUG (5, fprintf (gc_debug_file, "Collecting object for finalization: %p (%s) (%d/%d)\n", entry->object, safe_name (entry->object), num_ready_finalizers, num_registered_finalizers));
3177 if (count == out_size) {
3184 entry = entry->next;
3192 rehash_fin_table (void)
3196 FinalizeEntry **new_hash;
3197 FinalizeEntry *entry, *next;
3198 int new_size = g_spaced_primes_closest (num_registered_finalizers);
3200 new_hash = get_internal_mem (new_size * sizeof (FinalizeEntry*));
3201 for (i = 0; i < finalizable_hash_size; ++i) {
3202 for (entry = finalizable_hash [i]; entry; entry = next) {
3203 hash = mono_object_hash (entry->object) % new_size;
3205 entry->next = new_hash [hash];
3206 new_hash [hash] = entry;
3209 free_internal_mem (finalizable_hash);
3210 finalizable_hash = new_hash;
3211 finalizable_hash_size = new_size;
3215 mono_gc_register_for_finalization (MonoObject *obj, void *user_data)
3217 FinalizeEntry *entry, *prev;
3221 hash = mono_object_hash (obj);
3223 if (num_registered_finalizers >= finalizable_hash_size * 2)
3224 rehash_fin_table ();
3225 hash %= finalizable_hash_size;
3227 for (entry = finalizable_hash [hash]; entry; entry = entry->next) {
3228 if (entry->object == obj) {
3230 entry->data = user_data;
3232 /* remove from the list */
3234 prev->next = entry->next;
3236 finalizable_hash [hash] = entry->next;
3237 num_registered_finalizers--;
3238 DEBUG (5, fprintf (gc_debug_file, "Removed finalizer %p for object: %p (%s) (%d)\n", entry, obj, obj->vtable->klass->name, num_registered_finalizers));
3239 free_internal_mem (entry);
3247 /* request to deregister, but already out of the list */
3251 entry = get_internal_mem (sizeof (FinalizeEntry));
3252 entry->object = obj;
3253 entry->data = user_data;
3254 entry->next = finalizable_hash [hash];
3255 finalizable_hash [hash] = entry;
3256 num_registered_finalizers++;
3257 DEBUG (5, fprintf (gc_debug_file, "Added finalizer %p for object: %p (%s) (%d)\n", entry, obj, obj->vtable->klass->name, num_registered_finalizers));
3262 rehash_dislink (void)
3266 FinalizeEntry **new_hash;
3267 FinalizeEntry *entry, *next;
3268 int new_size = g_spaced_primes_closest (num_disappearing_links);
3270 new_hash = get_internal_mem (new_size * sizeof (FinalizeEntry*));
3271 for (i = 0; i < disappearing_link_hash_size; ++i) {
3272 for (entry = disappearing_link_hash [i]; entry; entry = next) {
3273 hash = mono_aligned_addr_hash (entry->data) % new_size;
3275 entry->next = new_hash [hash];
3276 new_hash [hash] = entry;
3279 free_internal_mem (disappearing_link_hash);
3280 disappearing_link_hash = new_hash;
3281 disappearing_link_hash_size = new_size;
3285 mono_gc_register_disappearing_link (MonoObject *obj, void *link)
3287 FinalizeEntry *entry, *prev;
3291 if (num_disappearing_links >= disappearing_link_hash_size * 2)
3293 /* FIXME: add check that link is not in the heap */
3294 hash = mono_aligned_addr_hash (link) % disappearing_link_hash_size;
3295 entry = disappearing_link_hash [hash];
3297 for (; entry; entry = entry->next) {
3298 /* link already added */
3299 if (link == entry->data) {
3300 /* NULL obj means remove */
3303 prev->next = entry->next;
3305 disappearing_link_hash [hash] = entry->next;
3306 num_disappearing_links--;
3307 DEBUG (5, fprintf (gc_debug_file, "Removed dislink %p (%d)\n", entry, num_disappearing_links));
3308 free_internal_mem (entry);
3310 entry->object = obj; /* we allow the change of object */
3317 entry = get_internal_mem (sizeof (FinalizeEntry));
3318 entry->object = obj;
3320 entry->next = disappearing_link_hash [hash];
3321 disappearing_link_hash [hash] = entry;
3322 num_disappearing_links++;
3323 DEBUG (5, fprintf (gc_debug_file, "Added dislink %p for object: %p (%s) at %p\n", entry, obj, obj->vtable->klass->name, link));
3328 mono_gc_invoke_finalizers (void)
3330 FinalizeEntry *entry;
3333 /* FIXME: batch to reduce lock contention */
3334 while (fin_ready_list) {
3336 entry = fin_ready_list;
3338 fin_ready_list = entry->next;
3339 num_ready_finalizers--;
3340 obj = entry->object;
3341 DEBUG (7, fprintf (gc_debug_file, "Finalizing object %p (%s)\n", obj, safe_name (obj)));
3345 void (*callback)(void *, void*) = entry->data;
3347 obj = entry->object;
3349 /* the object is on the stack so it is pinned */
3350 /*g_print ("Calling finalizer for object: %p (%s)\n", entry->object, safe_name (entry->object));*/
3351 callback (obj, NULL);
3352 free_internal_mem (entry);
3359 mono_gc_pending_finalizers (void)
3361 return fin_ready_list != NULL;
3364 /* Negative value to remove */
3366 mono_gc_add_memory_pressure (gint64 value)
3368 /* FIXME: Use interlocked functions */
3370 memory_pressure += value;
3375 * ######################################################################
3376 * ######## registered roots support
3377 * ######################################################################
3385 RootRecord **new_hash;
3386 RootRecord *entry, *next;
3387 int new_size = g_spaced_primes_closest (num_roots_entries);
3389 new_hash = get_internal_mem (new_size * sizeof (RootRecord*));
3390 for (i = 0; i < roots_hash_size; ++i) {
3391 for (entry = roots_hash [i]; entry; entry = next) {
3392 hash = mono_aligned_addr_hash (entry->start_root) % new_size;
3394 entry->next = new_hash [hash];
3395 new_hash [hash] = entry;
3398 free_internal_mem (roots_hash);
3399 roots_hash = new_hash;
3400 roots_hash_size = new_size;
3404 * We do not coalesce roots.
3407 mono_gc_register_root (char *start, size_t size, void *descr)
3409 RootRecord *new_root;
3410 unsigned int hash = mono_aligned_addr_hash (start);
3412 if (num_roots_entries >= roots_hash_size * 2)
3414 hash %= roots_hash_size;
3415 for (new_root = roots_hash [hash]; new_root; new_root = new_root->next) {
3416 /* we allow changing the size and the descriptor (for thread statics etc) */
3417 if (new_root->start_root == start) {
3418 size_t old_size = new_root->end_root - new_root->start_root;
3419 new_root->end_root = new_root->start_root + size;
3420 new_root->root_desc = (mword)descr;
3422 roots_size -= old_size;
3427 new_root = get_internal_mem (sizeof (RootRecord));
3429 new_root->start_root = start;
3430 new_root->end_root = new_root->start_root + size;
3431 new_root->root_desc = (mword)descr;
3433 num_roots_entries++;
3434 new_root->next = roots_hash [hash];
3435 roots_hash [hash] = new_root;
3436 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));
3446 mono_gc_deregister_root (char* addr)
3448 RootRecord *tmp, *prev = NULL;
3449 unsigned int hash = mono_aligned_addr_hash (addr);
3451 hash %= roots_hash_size;
3452 tmp = roots_hash [hash];
3454 if (tmp->start_root == (char*)addr) {
3456 prev->next = tmp->next;
3458 roots_hash [hash] = tmp->next;
3459 roots_size -= (tmp->end_root - tmp->start_root);
3460 num_roots_entries--;
3461 DEBUG (3, fprintf (gc_debug_file, "Removed root %p for range: %p-%p\n", tmp, tmp->start_root, tmp->end_root));
3462 free_internal_mem (tmp);
3472 * ######################################################################
3473 * ######## Thread handling (stop/start code)
3474 * ######################################################################
3477 /* eventually share with MonoThread? */
3478 typedef struct _SgenThreadInfo SgenThreadInfo;
3480 struct _SgenThreadInfo {
3481 SgenThreadInfo *next;
3482 ARCH_THREAD_TYPE id;
3483 unsigned int stop_count; /* to catch duplicate signals */
3488 RememberedSet *remset;
3491 /* FIXME: handle large/small config */
3492 #define THREAD_HASH_SIZE 11
3493 #define HASH_PTHREAD_T(id) (((unsigned int)(id) >> 4) * 2654435761u)
3495 static SgenThreadInfo* thread_table [THREAD_HASH_SIZE];
3497 #if USE_SIGNAL_BASED_START_STOP_WORLD
3499 static sem_t suspend_ack_semaphore;
3500 static unsigned int global_stop_count = 0;
3501 static int suspend_signal_num = SIGPWR;
3502 static int restart_signal_num = SIGXCPU;
3503 static sigset_t suspend_signal_mask;
3504 static mword cur_thread_regs [ARCH_NUM_REGS] = {0};
3506 /* LOCKING: assumes the GC lock is held */
3507 static SgenThreadInfo*
3508 thread_info_lookup (ARCH_THREAD_TYPE id)
3510 unsigned int hash = HASH_PTHREAD_T (id) % THREAD_HASH_SIZE;
3511 SgenThreadInfo *info;
3513 info = thread_table [hash];
3514 while (info && !ARCH_THREAD_EQUALS (info->id, id)) {
3521 update_current_thread_stack (void *start)
3523 void *ptr = cur_thread_regs;
3524 SgenThreadInfo *info = thread_info_lookup (ARCH_GET_THREAD ());
3525 info->stack_start = align_pointer (&ptr);
3526 ARCH_STORE_REGS (ptr);
3530 signal_desc (int signum)
3532 if (signum == suspend_signal_num)
3534 if (signum == restart_signal_num)
3539 /* LOCKING: assumes the GC lock is held */
3541 thread_handshake (int signum)
3543 int count, i, result;
3544 SgenThreadInfo *info;
3545 pthread_t me = pthread_self ();
3548 for (i = 0; i < THREAD_HASH_SIZE; ++i) {
3549 for (info = thread_table [i]; info; info = info->next) {
3550 DEBUG (4, fprintf (gc_debug_file, "considering thread %p for signal %d (%s)\n", info, signum, signal_desc (signum)));
3551 if (ARCH_THREAD_EQUALS (info->id, me)) {
3552 DEBUG (4, fprintf (gc_debug_file, "Skip (equal): %p, %p\n", (void*)me, (void*)info->id));
3555 /*if (signum == suspend_signal_num && info->stop_count == global_stop_count)
3557 result = pthread_kill (info->id, signum);
3559 DEBUG (4, fprintf (gc_debug_file, "thread %p signal sent\n", info));
3562 DEBUG (4, fprintf (gc_debug_file, "thread %p signal failed: %d (%s)\n", (void*)info->id, result, strerror (result)));
3568 for (i = 0; i < count; ++i) {
3569 while ((result = sem_wait (&suspend_ack_semaphore)) != 0) {
3570 if (errno != EINTR) {
3571 g_error ("sem_wait ()");
3578 /* LOCKING: assumes the GC lock is held (by the stopping thread) */
3580 suspend_handler (int sig)
3582 SgenThreadInfo *info;
3585 int old_errno = errno;
3587 id = pthread_self ();
3588 info = thread_info_lookup (id);
3589 stop_count = global_stop_count;
3590 /* duplicate signal */
3591 if (0 && info->stop_count == stop_count) {
3595 /* update the remset info in the thread data structure */
3596 info->remset = remembered_set;
3598 * this includes the register values that the kernel put on the stack.
3599 * Write arch-specific code to only push integer regs and a more accurate
3602 info->stack_start = align_pointer (&id);
3604 /* notify the waiting thread */
3605 sem_post (&suspend_ack_semaphore);
3606 info->stop_count = stop_count;
3608 /* wait until we receive the restart signal */
3611 sigsuspend (&suspend_signal_mask);
3612 } while (info->signal != restart_signal_num);
3614 /* notify the waiting thread */
3615 sem_post (&suspend_ack_semaphore);
3621 restart_handler (int sig)
3623 SgenThreadInfo *info;
3624 int old_errno = errno;
3626 info = thread_info_lookup (pthread_self ());
3627 info->signal = restart_signal_num;
3632 static TV_DECLARE (stop_world_time);
3633 static unsigned long max_pause_usec = 0;
3635 /* LOCKING: assumes the GC lock is held */
3641 global_stop_count++;
3642 DEBUG (3, fprintf (gc_debug_file, "stopping world n %d from %p %p\n", global_stop_count, thread_info_lookup (ARCH_GET_THREAD ()), (gpointer)ARCH_GET_THREAD ()));
3643 TV_GETTIME (stop_world_time);
3644 count = thread_handshake (suspend_signal_num);
3645 DEBUG (3, fprintf (gc_debug_file, "world stopped %d thread(s)\n", count));
3649 /* LOCKING: assumes the GC lock is held */
3651 restart_world (void)
3654 TV_DECLARE (end_sw);
3657 count = thread_handshake (restart_signal_num);
3658 TV_GETTIME (end_sw);
3659 usec = TV_ELAPSED (stop_world_time, end_sw);
3660 max_pause_usec = MAX (usec, max_pause_usec);
3661 DEBUG (2, fprintf (gc_debug_file, "restarted %d thread(s) (pause time: %d usec, max: %d)\n", count, (int)usec, (int)max_pause_usec));
3665 #endif /* USE_SIGNAL_BASED_START_STOP_WORLD */
3668 * Identify objects pinned in a thread stack and its registers.
3671 pin_thread_data (void *start_nursery, void *end_nursery)
3674 SgenThreadInfo *info;
3676 for (i = 0; i < THREAD_HASH_SIZE; ++i) {
3677 for (info = thread_table [i]; info; info = info->next) {
3679 DEBUG (2, fprintf (gc_debug_file, "Skipping dead thread %p, range: %p-%p, size: %zd\n", info, info->stack_start, info->stack_end, (char*)info->stack_end - (char*)info->stack_start));
3682 DEBUG (2, fprintf (gc_debug_file, "Scanning thread %p, range: %p-%p, size: %zd\n", info, info->stack_start, info->stack_end, (char*)info->stack_end - (char*)info->stack_start));
3683 conservatively_pin_objects_from (info->stack_start, info->stack_end, start_nursery, end_nursery);
3686 DEBUG (2, fprintf (gc_debug_file, "Scanning current thread registers\n"));
3687 conservatively_pin_objects_from ((void*)cur_thread_regs, (void*)(cur_thread_regs + ARCH_NUM_REGS), start_nursery, end_nursery);
3691 find_pinning_ref_from_thread (char *obj, size_t size)
3694 SgenThreadInfo *info;
3695 char *endobj = obj + size;
3697 for (i = 0; i < THREAD_HASH_SIZE; ++i) {
3698 for (info = thread_table [i]; info; info = info->next) {
3699 char **start = (char**)info->stack_start;
3702 while (start < (char**)info->stack_end) {
3703 if (*start >= obj && *start < endobj) {
3704 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));
3710 /* FIXME: check register */
3713 /* return TRUE if ptr points inside the managed heap */
3715 ptr_in_heap (void* ptr)
3717 mword p = (mword)ptr;
3718 if (p < lowest_heap_address || p >= highest_heap_address)
3720 /* FIXME: more checks */
3725 handle_remset (mword *p, void *start_nursery, void *end_nursery, gboolean global)
3730 /* FIXME: exclude stack locations */
3731 switch ((*p) & REMSET_TYPE_MASK) {
3732 case REMSET_LOCATION:
3734 if (((void*)ptr < start_nursery || (void*)ptr >= end_nursery) && ptr_in_heap (ptr)) {
3735 *ptr = copy_object (*ptr, start_nursery, end_nursery);
3736 DEBUG (9, fprintf (gc_debug_file, "Overwrote remset at %p with %p\n", ptr, *ptr));
3737 if (!global && *ptr >= start_nursery && *ptr < end_nursery)
3738 add_to_global_remset (ptr);
3740 DEBUG (9, fprintf (gc_debug_file, "Skipping remset at %p holding %p\n", ptr, *ptr));
3744 ptr = (void**)(*p & ~REMSET_TYPE_MASK);
3745 if (((void*)ptr >= start_nursery && (void*)ptr < end_nursery) || !ptr_in_heap (ptr))
3748 while (count-- > 0) {
3749 *ptr = copy_object (*ptr, start_nursery, end_nursery);
3750 DEBUG (9, fprintf (gc_debug_file, "Overwrote remset at %p with %p (count: %d)\n", ptr, *ptr, (int)count));
3751 if (!global && *ptr >= start_nursery && *ptr < end_nursery)
3752 add_to_global_remset (ptr);
3757 ptr = (void**)(*p & ~REMSET_TYPE_MASK);
3758 if (((void*)ptr >= start_nursery && (void*)ptr < end_nursery) || !ptr_in_heap (ptr))
3760 scan_object (*ptr, start_nursery, end_nursery);
3763 g_assert_not_reached ();
3769 scan_from_remsets (void *start_nursery, void *end_nursery)
3772 SgenThreadInfo *info;
3773 RememberedSet *remset, *next;
3776 /* the global one */
3777 for (remset = global_remset; remset; remset = remset->next) {
3778 DEBUG (4, fprintf (gc_debug_file, "Scanning global remset range: %p-%p, size: %zd\n", remset->data, remset->store_next, remset->store_next - remset->data));
3779 for (p = remset->data; p < remset->store_next;) {
3780 p = handle_remset (p, start_nursery, end_nursery, TRUE);
3783 /* the per-thread ones */
3784 for (i = 0; i < THREAD_HASH_SIZE; ++i) {
3785 for (info = thread_table [i]; info; info = info->next) {
3786 for (remset = info->remset; remset; remset = next) {
3787 DEBUG (4, fprintf (gc_debug_file, "Scanning remset for thread %p, range: %p-%p, size: %zd\n", info, remset->data, remset->store_next, remset->store_next - remset->data));
3788 for (p = remset->data; p < remset->store_next;) {
3789 p = handle_remset (p, start_nursery, end_nursery, FALSE);
3791 remset->store_next = remset->data;
3792 next = remset->next;
3793 remset->next = NULL;
3794 if (remset != info->remset) {
3795 DEBUG (4, fprintf (gc_debug_file, "Freed remset at %p\n", remset->data));
3796 free_internal_mem (remset);
3804 * Clear the info in the remembered sets: we're doing a major collection, so
3805 * the per-thread ones are not needed and the global ones will be reconstructed
3809 clear_remsets (void)
3812 SgenThreadInfo *info;
3813 RememberedSet *remset, *next;
3815 /* the global list */
3816 for (remset = global_remset; remset; remset = next) {
3817 remset->store_next = remset->data;
3818 next = remset->next;
3819 remset->next = NULL;
3820 if (remset != global_remset) {
3821 DEBUG (4, fprintf (gc_debug_file, "Freed remset at %p\n", remset->data));
3822 free_internal_mem (remset);
3825 /* the per-thread ones */
3826 for (i = 0; i < THREAD_HASH_SIZE; ++i) {
3827 for (info = thread_table [i]; info; info = info->next) {
3828 for (remset = info->remset; remset; remset = next) {
3829 remset->store_next = remset->data;
3830 next = remset->next;
3831 remset->next = NULL;
3832 if (remset != info->remset) {
3833 DEBUG (1, fprintf (gc_debug_file, "Freed remset at %p\n", remset->data));
3834 free_internal_mem (remset);
3841 /* LOCKING: assumes the GC lock is held */
3842 static SgenThreadInfo*
3843 gc_register_current_thread (void *addr)
3846 SgenThreadInfo* info = malloc (sizeof (SgenThreadInfo));
3849 info->id = ARCH_GET_THREAD ();
3850 info->stop_count = -1;
3853 info->stack_start = NULL;
3855 /* try to get it with attributes first */
3856 #if defined(HAVE_PTHREAD_GETATTR_NP) && defined(HAVE_PTHREAD_ATTR_GETSTACK)
3860 pthread_attr_t attr;
3861 pthread_getattr_np (pthread_self (), &attr);
3862 pthread_attr_getstack (&attr, &sstart, &size);
3863 info->stack_end = (char*)sstart + size;
3864 pthread_attr_destroy (&attr);
3866 #elif defined(HAVE_PTHREAD_GET_STACKSIZE_NP) && defined(HAVE_PTHREAD_GET_STACKADDR_NP)
3867 info->stack_end = (char*)pthread_get_stackaddr_np (pthread_self ());
3870 /* FIXME: we assume the stack grows down */
3871 gsize stack_bottom = (gsize)addr;
3872 stack_bottom += 4095;
3873 stack_bottom &= ~4095;
3874 info->stack_end = (char*)stack_bottom;
3878 /* hash into the table */
3879 hash = HASH_PTHREAD_T (info->id) % THREAD_HASH_SIZE;
3880 info->next = thread_table [hash];
3881 thread_table [hash] = info;
3883 remembered_set = info->remset = alloc_remset (DEFAULT_REMSET_SIZE, info);
3884 pthread_setspecific (remembered_set_key, remembered_set);
3885 DEBUG (3, fprintf (gc_debug_file, "registered thread %p (%p) (hash: %d)\n", info, (gpointer)info->id, hash));
3890 unregister_current_thread (void)
3893 SgenThreadInfo *prev = NULL;
3895 RememberedSet *rset;
3896 ARCH_THREAD_TYPE id = ARCH_GET_THREAD ();
3898 hash = HASH_PTHREAD_T (id) % THREAD_HASH_SIZE;
3899 p = thread_table [hash];
3901 DEBUG (3, fprintf (gc_debug_file, "unregister thread %p (%p)\n", p, (gpointer)p->id));
3902 while (!ARCH_THREAD_EQUALS (p->id, id)) {
3907 thread_table [hash] = p->next;
3909 prev->next = p->next;
3912 /* FIXME: transfer remsets if any */
3914 RememberedSet *next = rset->next;
3915 free_internal_mem (rset);
3922 unregister_thread (void *k)
3925 unregister_current_thread ();
3930 mono_gc_register_thread (void *baseptr)
3932 SgenThreadInfo *info;
3934 info = thread_info_lookup (ARCH_GET_THREAD ());
3936 info = gc_register_current_thread (baseptr);
3938 return info != NULL;
3941 #if USE_PTHREAD_INTERCEPT
3943 #undef pthread_create
3945 #undef pthread_detach
3948 void *(*start_routine) (void *);
3952 } SgenThreadStartInfo;
3955 gc_start_thread (void *arg)
3957 SgenThreadStartInfo *start_info = arg;
3958 SgenThreadInfo* info;
3959 void *t_arg = start_info->arg;
3960 void *(*start_func) (void*) = start_info->start_routine;
3964 info = gc_register_current_thread (&result);
3966 sem_post (&(start_info->registered));
3967 result = start_func (t_arg);
3969 * this is done by the pthread key dtor
3971 unregister_current_thread ();
3979 mono_gc_pthread_create (pthread_t *new_thread, const pthread_attr_t *attr, void *(*start_routine)(void *), void *arg)
3981 SgenThreadStartInfo *start_info;
3984 start_info = malloc (sizeof (SgenThreadStartInfo));
3987 sem_init (&(start_info->registered), 0, 0);
3988 start_info->arg = arg;
3989 start_info->start_routine = start_routine;
3991 result = pthread_create (new_thread, attr, gc_start_thread, start_info);
3993 while (sem_wait (&(start_info->registered)) != 0) {
3994 /*if (EINTR != errno) ABORT("sem_wait failed"); */
3997 sem_destroy (&(start_info->registered));
4003 mono_gc_pthread_join (pthread_t thread, void **retval)
4005 return pthread_join (thread, retval);
4009 mono_gc_pthread_detach (pthread_t thread)
4011 return pthread_detach (thread);
4014 #endif /* USE_PTHREAD_INTERCEPT */
4017 * ######################################################################
4018 * ######## Write barriers
4019 * ######################################################################
4022 static RememberedSet*
4023 alloc_remset (int size, gpointer id) {
4024 RememberedSet* res = get_internal_mem (sizeof (RememberedSet) + (size * sizeof (gpointer)));
4025 res->store_next = res->data;
4026 res->end_set = res->data + size;
4028 DEBUG (4, fprintf (gc_debug_file, "Allocated remset size %d at %p for %p\n", size, res->data, id));
4033 * Note: the write barriers first do the needed GC work and then do the actual store:
4034 * this way the value is visible to the conservative GC scan after the write barrier
4035 * itself. If a GC interrupts the barrier in the middle, value will be kept alive by
4036 * the conservative scan, otherwise by the remembered set scan. FIXME: figure out what
4037 * happens when we need to record which pointers contain references to the new generation.
4038 * The write barrier will be executed, but the pointer is still not stored.
4041 mono_gc_wbarrier_set_field (MonoObject *obj, gpointer field_ptr, MonoObject* value)
4044 if ((char*)field_ptr >= nursery_start && (char*)field_ptr < nursery_real_end) {
4045 *(void**)field_ptr = value;
4048 DEBUG (8, fprintf (gc_debug_file, "Adding remset at %p\n", field_ptr));
4049 rs = remembered_set;
4050 if (rs->store_next < rs->end_set) {
4051 *(rs->store_next++) = (mword)field_ptr;
4052 *(void**)field_ptr = value;
4055 rs = alloc_remset (rs->end_set - rs->data, (void*)1);
4056 rs->next = remembered_set;
4057 remembered_set = rs;
4058 thread_info_lookup (ARCH_GET_THREAD ())->remset = rs;
4059 *(rs->store_next++) = (mword)field_ptr;
4060 *(void**)field_ptr = value;
4064 mono_gc_wbarrier_set_arrayref (MonoArray *arr, gpointer slot_ptr, MonoObject* value)
4066 RememberedSet *rs = remembered_set;
4067 if ((char*)slot_ptr >= nursery_start && (char*)slot_ptr < nursery_real_end) {
4068 *(void**)slot_ptr = value;
4071 DEBUG (8, fprintf (gc_debug_file, "Adding remset at %p\n", slot_ptr));
4072 if (rs->store_next < rs->end_set) {
4073 *(rs->store_next++) = (mword)slot_ptr;
4074 *(void**)slot_ptr = value;
4077 rs = alloc_remset (rs->end_set - rs->data, (void*)1);
4078 rs->next = remembered_set;
4079 remembered_set = rs;
4080 thread_info_lookup (ARCH_GET_THREAD ())->remset = rs;
4081 *(rs->store_next++) = (mword)slot_ptr;
4082 *(void**)slot_ptr = value;
4086 mono_gc_wbarrier_arrayref_copy (MonoArray *arr, gpointer slot_ptr, int count)
4088 RememberedSet *rs = remembered_set;
4089 if ((char*)slot_ptr >= nursery_start && (char*)slot_ptr < nursery_real_end)
4091 DEBUG (8, fprintf (gc_debug_file, "Adding remset at %p, %d\n", slot_ptr, count));
4092 if (rs->store_next + 1 < rs->end_set) {
4093 *(rs->store_next++) = (mword)slot_ptr | REMSET_RANGE;
4094 *(rs->store_next++) = count;
4097 rs = alloc_remset (rs->end_set - rs->data, (void*)1);
4098 rs->next = remembered_set;
4099 remembered_set = rs;
4100 thread_info_lookup (ARCH_GET_THREAD ())->remset = rs;
4101 *(rs->store_next++) = (mword)slot_ptr | REMSET_RANGE;
4102 *(rs->store_next++) = count;
4106 mono_gc_wbarrier_generic_store (gpointer ptr, MonoObject* value)
4108 RememberedSet *rs = remembered_set;
4109 if ((char*)ptr >= nursery_start && (char*)ptr < nursery_real_end) {
4110 DEBUG (8, fprintf (gc_debug_file, "Skipping remset at %p\n", ptr));
4111 *(void**)ptr = value;
4114 DEBUG (8, fprintf (gc_debug_file, "Adding remset at %p\n", ptr));
4115 /* FIXME: ensure it is on the heap */
4116 if (rs->store_next < rs->end_set) {
4117 *(rs->store_next++) = (mword)ptr;
4118 *(void**)ptr = value;
4121 rs = alloc_remset (rs->end_set - rs->data, (void*)1);
4122 rs->next = remembered_set;
4123 remembered_set = rs;
4124 thread_info_lookup (ARCH_GET_THREAD ())->remset = rs;
4125 *(rs->store_next++) = (mword)ptr;
4126 *(void**)ptr = value;
4130 mono_gc_wbarrier_value_copy (gpointer dest, gpointer src, int count, MonoClass *klass)
4132 if ((char*)dest >= nursery_start && (char*)dest < nursery_real_end) {
4135 DEBUG (1, fprintf (gc_debug_file, "Adding value remset at %p, count %d for class %s\n", dest, count, klass->name));
4139 * mono_gc_wbarrier_object:
4141 * Write barrier to call when obj is the result of a clone or copy of an object.
4144 mono_gc_wbarrier_object (MonoObject* obj)
4146 RememberedSet *rs = remembered_set;
4147 DEBUG (1, fprintf (gc_debug_file, "Adding object remset for %p\n", obj));
4148 if (rs->store_next < rs->end_set) {
4149 *(rs->store_next++) = (mword)obj | REMSET_OBJECT;
4152 rs = alloc_remset (rs->end_set - rs->data, (void*)1);
4153 rs->next = remembered_set;
4154 remembered_set = rs;
4155 thread_info_lookup (ARCH_GET_THREAD ())->remset = rs;
4156 *(rs->store_next++) = (mword)obj | REMSET_OBJECT;
4160 * ######################################################################
4161 * ######## Collector debugging
4162 * ######################################################################
4166 find_in_remset_loc (mword *p, char *addr, gboolean *found)
4171 switch ((*p) & REMSET_TYPE_MASK) {
4172 case REMSET_LOCATION:
4173 if (*p == (mword)addr)
4177 ptr = (void**)(*p & ~REMSET_TYPE_MASK);
4179 if ((void**)addr >= ptr && (void**)addr < ptr + count)
4183 ptr = (void**)(*p & ~REMSET_TYPE_MASK);
4184 count = safe_object_get_size ((MonoObject*)ptr);
4185 count += (ALLOC_ALIGN - 1);
4186 count &= (ALLOC_ALIGN - 1);
4187 count /= sizeof (mword);
4188 if ((void**)addr >= ptr && (void**)addr < ptr + count)
4192 g_assert_not_reached ();
4198 * Return whenever ADDR occurs in the remembered sets
4201 find_in_remsets (char *addr)
4204 SgenThreadInfo *info;
4205 RememberedSet *remset;
4207 gboolean found = FALSE;
4209 /* the global one */
4210 for (remset = global_remset; remset; remset = remset->next) {
4211 DEBUG (4, fprintf (gc_debug_file, "Scanning global remset range: %p-%p, size: %zd\n", remset->data, remset->store_next, remset->store_next - remset->data));
4212 for (p = remset->data; p < remset->store_next;) {
4213 p = find_in_remset_loc (p, addr, &found);
4218 /* the per-thread ones */
4219 for (i = 0; i < THREAD_HASH_SIZE; ++i) {
4220 for (info = thread_table [i]; info; info = info->next) {
4221 for (remset = info->remset; remset; remset = remset->next) {
4222 DEBUG (4, fprintf (gc_debug_file, "Scanning remset for thread %p, range: %p-%p, size: %zd\n", info, remset->data, remset->store_next, remset->store_next - remset->data));
4223 for (p = remset->data; p < remset->store_next;) {
4224 p = find_in_remset_loc (p, addr, &found);
4236 #define HANDLE_PTR(ptr,obj) do { \
4237 if (*(ptr) && (char*)*(ptr) >= nursery_start && (char*)*(ptr) < nursery_next) { \
4238 if (!find_in_remsets ((char*)(ptr))) { \
4239 fprintf (gc_debug_file, "Oldspace->newspace reference %p at offset %zd 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); \
4240 g_assert_not_reached (); \
4246 * Check that each object reference inside the area which points into the nursery
4247 * can be found in the remembered sets.
4249 static void __attribute__((noinline))
4250 check_remsets_for_area (char *start, char *end)
4255 int type_str = 0, type_rlen = 0, type_bitmap = 0, type_vector = 0, type_lbit = 0, type_complex = 0;
4256 new_obj_references = 0;
4257 obj_references_checked = 0;
4258 while (start < end) {
4259 if (!*(void**)start) {
4260 start += sizeof (void*); /* should be ALLOC_ALIGN, really */
4263 vt = (GCVTable*)LOAD_VTABLE (start);
4264 DEBUG (8, fprintf (gc_debug_file, "Scanning object %p, vtable: %p (%s)\n", start, vt, vt->klass->name));
4266 MonoObject *obj = (MonoObject*)start;
4267 g_print ("found at %p (0x%lx): %s.%s\n", start, (long)vt->desc, obj->vtable->klass->name_space, obj->vtable->klass->name);
4269 type = vt->desc & 0x7;
4270 if (type == DESC_TYPE_STRING) {
4271 STRING_SIZE (skip_size, start);
4275 } else if (type == DESC_TYPE_RUN_LENGTH) {
4276 OBJ_RUN_LEN_SIZE (skip_size, vt, start);
4277 g_assert (skip_size);
4278 OBJ_RUN_LEN_FOREACH_PTR (vt,start);
4282 } else if (type == DESC_TYPE_VECTOR) { // includes ARRAY, too
4283 skip_size = (vt->desc >> LOW_TYPE_BITS) & MAX_ELEMENT_SIZE;
4284 skip_size *= mono_array_length ((MonoArray*)start);
4285 skip_size += sizeof (MonoArray);
4286 skip_size += (ALLOC_ALIGN - 1);
4287 skip_size &= ~(ALLOC_ALIGN - 1);
4288 OBJ_VECTOR_FOREACH_PTR (vt, start);
4289 if (((MonoArray*)start)->bounds) {
4290 /* account for the bounds */
4291 skip_size += sizeof (MonoArrayBounds) * vt->klass->rank;
4296 } else if (type == DESC_TYPE_SMALL_BITMAP) {
4297 OBJ_BITMAP_SIZE (skip_size, vt, start);
4298 g_assert (skip_size);
4299 OBJ_BITMAP_FOREACH_PTR (vt,start);
4303 } else if (type == DESC_TYPE_LARGE_BITMAP) {
4304 skip_size = safe_object_get_size ((MonoObject*)start);
4305 skip_size += (ALLOC_ALIGN - 1);
4306 skip_size &= ~(ALLOC_ALIGN - 1);
4307 OBJ_LARGE_BITMAP_FOREACH_PTR (vt,start);
4311 } else if (type == DESC_TYPE_COMPLEX) {
4312 /* this is a complex object */
4313 skip_size = safe_object_get_size ((MonoObject*)start);
4314 skip_size += (ALLOC_ALIGN - 1);
4315 skip_size &= ~(ALLOC_ALIGN - 1);
4316 OBJ_COMPLEX_FOREACH_PTR (vt, start);
4320 } else if (type == DESC_TYPE_COMPLEX_ARR) {
4321 /* this is an array of complex structs */
4322 skip_size = mono_array_element_size (((MonoVTable*)vt)->klass);
4323 skip_size *= mono_array_length ((MonoArray*)start);
4324 skip_size += sizeof (MonoArray);
4325 skip_size += (ALLOC_ALIGN - 1);
4326 skip_size &= ~(ALLOC_ALIGN - 1);
4327 OBJ_COMPLEX_ARR_FOREACH_PTR (vt, start);
4328 if (((MonoArray*)start)->bounds) {
4329 /* account for the bounds */
4330 skip_size += sizeof (MonoArrayBounds) * vt->klass->rank;
4342 * Perform consistency check of the heap.
4344 * Assumes the world is stopped.
4347 check_consistency (void)
4349 GCMemSection *section;
4351 // Need to add more checks
4352 // FIXME: Create a general heap enumeration function and use that
4354 DEBUG (1, fprintf (gc_debug_file, "Begin heap consistency check...\n"));
4356 // Check that oldspace->newspace pointers are registered with the collector
4357 for (section = section_list; section; section = section->next) {
4358 if (section->role == MEMORY_ROLE_GEN0)
4360 DEBUG (2, fprintf (gc_debug_file, "Scan of old section: %p-%p, size: %d\n", section->data, section->next_data, (int)(section->next_data - section->data)));
4361 check_remsets_for_area (section->data, section->next_data);
4364 DEBUG (1, fprintf (gc_debug_file, "Heap consistency check done.\n"));
4368 * ######################################################################
4369 * ######## Other mono public interface functions.
4370 * ######################################################################
4374 mono_gc_collect (int generation)
4377 update_current_thread_stack (&generation);
4379 if (generation == 0) {
4380 collect_nursery (0);
4382 major_collection ();
4389 mono_gc_max_generation (void)
4395 mono_gc_collection_count (int generation)
4397 if (generation == 0)
4398 return num_minor_gcs;
4399 return num_major_gcs;
4403 mono_gc_get_used_size (void)
4406 GCMemSection *section;
4408 tot = los_memory_usage;
4409 for (section = section_list; section; section = section->next) {
4410 /* this is approximate... */
4411 tot += section->next_data - section->data;
4413 /* FIXME: account for pinned objects */
4419 mono_gc_get_heap_size (void)
4425 mono_gc_disable (void)
4433 mono_gc_enable (void)
4441 mono_object_is_alive (MonoObject* o)
4447 mono_gc_get_generation (MonoObject *obj)
4449 if ((char*)obj >= nursery_start && (char*)obj < nursery_real_end)
4455 mono_gc_enable_events (void)
4460 mono_gc_weak_link_add (void **link_addr, MonoObject *obj)
4462 mono_gc_register_disappearing_link (obj, link_addr);
4467 mono_gc_weak_link_remove (void **link_addr)
4469 mono_gc_register_disappearing_link (NULL, link_addr);
4474 mono_gc_weak_link_get (void **link_addr)
4480 mono_gc_make_descr_from_bitmap (gsize *bitmap, int numbits)
4482 if (numbits < ((sizeof (*bitmap) * 8) - ROOT_DESC_TYPE_SHIFT)) {
4483 mword desc = ROOT_DESC_BITMAP | (bitmap [0] << ROOT_DESC_TYPE_SHIFT);
4486 /* conservative scanning */
4487 DEBUG (3, fprintf (gc_debug_file, "Conservative root descr for size: %d\n", numbits));
4492 mono_gc_alloc_fixed (size_t size, void *descr)
4494 /* FIXME: do a single allocation */
4495 void *res = calloc (1, size);
4498 if (!mono_gc_register_root (res, size, descr)) {
4506 mono_gc_free_fixed (void* addr)
4508 mono_gc_deregister_root (addr);
4513 mono_gc_is_gc_thread (void)
4517 result = thread_info_lookup (ARCH_GET_THREAD ()) != NULL;
4523 mono_gc_base_init (void)
4526 struct sigaction sinfo;
4528 LOCK_INIT (gc_mutex);
4530 if (gc_initialized) {
4534 pagesize = mono_pagesize ();
4535 gc_debug_file = stderr;
4536 /* format: MONO_GC_DEBUG=l[,filename] where l is a debug level 0-9 */
4537 if ((env = getenv ("MONO_GC_DEBUG"))) {
4538 if (env [0] >= '0' && env [0] <= '9') {
4539 gc_debug_level = atoi (env);
4545 char *rf = g_strdup_printf ("%s.%d", env, getpid ());
4546 gc_debug_file = fopen (rf, "wb");
4548 gc_debug_file = stderr;
4553 sem_init (&suspend_ack_semaphore, 0, 0);
4555 sigfillset (&sinfo.sa_mask);
4556 sinfo.sa_flags = SA_RESTART | SA_SIGINFO;
4557 sinfo.sa_handler = suspend_handler;
4558 if (sigaction (suspend_signal_num, &sinfo, NULL) != 0) {
4559 g_error ("failed sigaction");
4562 sinfo.sa_handler = restart_handler;
4563 if (sigaction (restart_signal_num, &sinfo, NULL) != 0) {
4564 g_error ("failed sigaction");
4567 sigfillset (&suspend_signal_mask);
4568 sigdelset (&suspend_signal_mask, restart_signal_num);
4570 global_remset = alloc_remset (1024, NULL);
4571 global_remset->next = NULL;
4573 pthread_key_create (&remembered_set_key, unregister_thread);
4574 gc_initialized = TRUE;
4576 mono_gc_register_thread (&sinfo);
4580 mono_gc_get_managed_allocator (MonoVTable *vtable, gboolean for_box)
4586 mono_gc_get_managed_allocator_type (MonoMethod *managed_alloc)
4592 mono_gc_get_managed_allocator_by_type (int atype)
4597 #endif /* HAVE_SGEN_GC */