2 * sgen-splliy-nursery.c: 3-space based nursery collector.
5 * Rodrigo Kumpera Kumpera <kumpera@gmail.com>
7 * Copyright 2001-2003 Ximian, Inc
8 * Copyright 2003-2010 Novell, Inc.
9 * Copyright 2011-2012 Xamarin Inc (http://www.xamarin.com)
10 * Copyright (C) 2012 Xamarin Inc
12 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
21 #include "mono/sgen/sgen-gc.h"
22 #include "mono/sgen/sgen-protocol.h"
23 #include "mono/sgen/sgen-layout-stats.h"
24 #include "mono/sgen/sgen-client.h"
25 #include "mono/utils/mono-memory-model.h"
28 The nursery is logically divided into 3 spaces: Allocator space and two Survivor spaces.
30 Objects are born (allocated by the mutator) in the Allocator Space.
32 The Survivor spaces are divided in a copying collector style From and To spaces.
33 The hole of each space switch on each collection.
35 On each collection we process objects from the nursery this way:
36 Objects from the Allocator Space are evacuated into the To Space.
37 Objects from the Survivor From Space are evacuated into the old generation.
40 The nursery is physically divided in two parts, set by the promotion barrier.
42 The Allocator Space takes the botton part of the nursery.
44 The Survivor spaces are intermingled in the top part of the nursery. It's done
45 this way since the required size for the To Space depends on the survivor rate
46 of objects from the Allocator Space.
48 During a collection when the object scan function see a nursery object it must
49 determine if the object needs to be evacuated or left in place. Originally, this
50 check was done by checking if a forwarding pointer is installed, but now an object
51 can be in the To Space, it won't have a forwarding pointer and it must be left in place.
53 In order to solve that we classify nursery memory been either in the From Space or in
54 the To Space. Since the Allocator Space has the same behavior as the Survivor From Space
55 they are unified for this purpoise - a bit confusing at first.
57 This from/to classification is done on a larger granule than object to make the check efficient
58 and, due to that, we must make sure that all fragemnts used to allocate memory from the To Space
59 are naturally aligned in both ends to that granule to avoid wronly classifying a From Space object.
62 -The promotion barrier is statically defined to 50% of the nursery, it should be dinamically adjusted based
64 -We apply the same promotion policy to all objects, finalizable ones should age longer in the nursery;
65 -We apply the same promotion policy to all stages of a collection, maybe we should promote more aggressively
66 objects from non-stack roots, specially those found in the remembered set;
67 -Fix our major collection trigger to happen before we do a minor GC and collect the nursery only once.
68 -Make the serial fragment allocator fast path inlineable
69 -Make aging threshold be based on survival rates and survivor occupancy;
70 -Change promotion barrier to be size and not address based;
71 -Pre allocate memory for young ages to make sure that on overflow only the older suffer;
72 -Get rid of par_alloc_buffer_refill_mutex so to the parallel collection of the nursery doesn't suck;
75 /*FIXME Move this to a separate header. */
76 #define _toi(ptr) ((size_t)ptr)
77 #define make_ptr_mask(bits) ((1 << bits) - 1)
78 #define align_down(ptr, bits) ((void*)(_toi(ptr) & ~make_ptr_mask (bits)))
79 #define align_up(ptr, bits) ((void*) ((_toi(ptr) + make_ptr_mask (bits)) & ~make_ptr_mask (bits)))
82 Even though the effective max age is 255, aging that much doesn't make sense.
83 It might even make sense to use nimbles for age recording.
88 * Each age has its allocation buffer. Whenever an object is to be
89 * aged we try to fit it into its new age's allocation buffer. If
90 * that is not possible we get new space from the fragment allocator
91 * and set the allocation buffer to that space (minus the space
92 * required for the object).
98 } AgeAllocationBuffer;
100 /* Limits the ammount of memory the mutator can have. */
101 static char *promotion_barrier;
104 Promotion age and alloc ratio are the two nursery knobs to control
105 how much effort we want to spend on young objects.
107 Allocation ratio should be the inverse of the expected survivor rate.
108 The more objects surviver, the smaller the alloc ratio much be so we can
111 Promote age depends on how much effort we want to spend aging objects before
112 we promote them to the old generation. If addional ages don't somewhat improve
113 mortality, it's better avoid as they increase the cost of minor collections.
119 If we're evacuating an object with this age or more, promote it.
120 Age is the number of surviving collections of an object.
122 static int promote_age = 2;
125 Initial ratio of allocation and survivor spaces.
126 This should be read as the fraction of the whole nursery dedicated
127 for the allocator space.
129 static float alloc_ratio = 60.f/100.f;
132 static char *region_age;
133 static size_t region_age_size;
134 static AgeAllocationBuffer age_alloc_buffers [MAX_AGE];
136 /* The collector allocs from here. */
137 static SgenFragmentAllocator collector_allocator;
140 get_object_age (GCObject *object)
142 size_t idx = ((char*)object - sgen_nursery_start) >> SGEN_TO_SPACE_GRANULE_BITS;
143 return region_age [idx];
147 set_age_in_range (char *start, char *end, int age)
150 size_t region_idx, length;
151 region_idx = (start - sgen_nursery_start) >> SGEN_TO_SPACE_GRANULE_BITS;
152 region_start = ®ion_age [region_idx];
153 length = (end - start) >> SGEN_TO_SPACE_GRANULE_BITS;
154 memset (region_start, age, length);
158 mark_bit (char *space_bitmap, char *pos)
160 size_t idx = (pos - sgen_nursery_start) >> SGEN_TO_SPACE_GRANULE_BITS;
161 size_t byte = idx / 8;
164 g_assert (byte < sgen_space_bitmap_size);
165 space_bitmap [byte] |= 1 << bit;
169 mark_bits_in_range (char *space_bitmap, char *start, char *end)
171 start = (char *)align_down (start, SGEN_TO_SPACE_GRANULE_BITS);
172 end = (char *)align_up (end, SGEN_TO_SPACE_GRANULE_BITS);
174 for (;start < end; start += SGEN_TO_SPACE_GRANULE_IN_BYTES)
175 mark_bit (space_bitmap, start);
179 * This splits the fragments at the point of the promotion barrier.
180 * Two allocator are actually involved here: The mutator allocator and
181 * the collector allocator. This function is called with the
182 * collector, but it's a copy of the mutator allocator and contains
183 * all the fragments in the nursery. The fragments below the
184 * promotion barrier are left with the mutator allocator and the ones
185 * above are put into the collector allocator.
188 fragment_list_split (SgenFragmentAllocator *allocator)
190 SgenFragment *prev = NULL, *list = allocator->region_head;
193 if (list->fragment_end > promotion_barrier) {
194 if (list->fragment_start < promotion_barrier) {
195 SgenFragment *res = sgen_fragment_allocator_alloc ();
197 res->fragment_start = promotion_barrier;
198 res->fragment_next = promotion_barrier;
199 res->fragment_end = list->fragment_end;
200 res->next = list->next;
201 res->next_in_order = list->next_in_order;
202 g_assert (res->fragment_end > res->fragment_start);
204 list->fragment_end = promotion_barrier;
205 list->next = list->next_in_order = NULL;
206 set_age_in_range (list->fragment_start, list->fragment_end, 0);
208 allocator->region_head = allocator->alloc_head = res;
212 prev->next = prev->next_in_order = NULL;
213 allocator->region_head = allocator->alloc_head = list;
217 set_age_in_range (list->fragment_start, list->fragment_end, 0);
221 allocator->region_head = allocator->alloc_head = NULL;
224 /******************************************Minor Collector API ************************************************/
226 #define AGE_ALLOC_BUFFER_MIN_SIZE SGEN_TO_SPACE_GRANULE_IN_BYTES
227 #define AGE_ALLOC_BUFFER_DESIRED_SIZE (SGEN_TO_SPACE_GRANULE_IN_BYTES * 8)
230 alloc_for_promotion_slow_path (int age, size_t objsize)
233 size_t allocated_size;
234 size_t aligned_objsize = (size_t)align_up (objsize, SGEN_TO_SPACE_GRANULE_BITS);
236 p = (char *)sgen_fragment_allocator_serial_range_alloc (
237 &collector_allocator,
238 MAX (aligned_objsize, AGE_ALLOC_BUFFER_DESIRED_SIZE),
239 MAX (aligned_objsize, AGE_ALLOC_BUFFER_MIN_SIZE),
242 set_age_in_range (p, p + allocated_size, age);
243 sgen_clear_range (age_alloc_buffers [age].next, age_alloc_buffers [age].end);
244 age_alloc_buffers [age].next = p + objsize;
245 age_alloc_buffers [age].end = p + allocated_size;
250 static inline GCObject*
251 alloc_for_promotion (GCVTable vtable, GCObject *obj, size_t objsize, gboolean has_references)
256 age = get_object_age (obj);
257 if (age >= promote_age) {
258 total_promoted_size += objsize;
259 return major_collector.alloc_object (vtable, objsize, has_references);
265 p = age_alloc_buffers [age].next;
266 if (G_LIKELY (p + objsize <= age_alloc_buffers [age].end)) {
267 age_alloc_buffers [age].next += objsize;
269 p = alloc_for_promotion_slow_path (age, objsize);
271 total_promoted_size += objsize;
272 return major_collector.alloc_object (vtable, objsize, has_references);
276 /* FIXME: assumes object layout */
277 *(GCVTable*)p = vtable;
283 minor_alloc_for_promotion (GCVTable vtable, GCObject *obj, size_t objsize, gboolean has_references)
286 We only need to check for a non-nursery object if we're doing a major collection.
288 if (!sgen_ptr_in_nursery (obj))
289 return major_collector.alloc_object (vtable, objsize, has_references);
291 return alloc_for_promotion (vtable, obj, objsize, has_references);
295 build_fragments_get_exclude_head (void)
298 for (i = 0; i < MAX_AGE; ++i) {
299 /*If we OOM'd on the last collection ->end might be null while ->next not.*/
300 if (age_alloc_buffers [i].end)
301 sgen_clear_range (age_alloc_buffers [i].next, age_alloc_buffers [i].end);
304 return collector_allocator.region_head;
308 build_fragments_release_exclude_head (void)
310 sgen_fragment_allocator_release (&collector_allocator);
314 build_fragments_finish (SgenFragmentAllocator *allocator)
316 /* We split the fragment list based on the promotion barrier. */
317 collector_allocator = *allocator;
318 fragment_list_split (&collector_allocator);
322 prepare_to_space (char *to_space_bitmap, size_t space_bitmap_size)
324 SgenFragment **previous, *frag;
326 memset (to_space_bitmap, 0, space_bitmap_size);
327 memset (age_alloc_buffers, 0, sizeof (age_alloc_buffers));
329 previous = &collector_allocator.alloc_head;
331 for (frag = *previous; frag; frag = *previous) {
332 char *start = (char *)align_up (frag->fragment_next, SGEN_TO_SPACE_GRANULE_BITS);
333 char *end = (char *)align_down (frag->fragment_end, SGEN_TO_SPACE_GRANULE_BITS);
335 /* Fragment is too small to be usable. */
336 if ((end - start) < SGEN_MAX_NURSERY_WASTE) {
337 sgen_clear_range (frag->fragment_next, frag->fragment_end);
338 frag->fragment_next = frag->fragment_end = frag->fragment_start;
339 *previous = frag->next;
344 We need to insert 3 phony objects so the fragments build step can correctly
348 /* Clean the fragment range. */
349 sgen_clear_range (start, end);
350 /* We need a phony object in between the original fragment start and the effective one. */
351 if (start != frag->fragment_next)
352 sgen_clear_range (frag->fragment_next, start);
353 /* We need an phony object in between the new fragment end and the original fragment end. */
354 if (end != frag->fragment_end)
355 sgen_clear_range (end, frag->fragment_end);
357 frag->fragment_start = frag->fragment_next = start;
358 frag->fragment_end = end;
359 mark_bits_in_range (to_space_bitmap, start, end);
360 previous = &frag->next;
365 clear_fragments (void)
367 sgen_clear_allocator_fragments (&collector_allocator);
371 init_nursery (SgenFragmentAllocator *allocator, char *start, char *end)
373 int alloc_quote = (int)((end - start) * alloc_ratio);
374 promotion_barrier = (char *)align_down (start + alloc_quote, 3);
375 sgen_fragment_allocator_add (allocator, start, promotion_barrier);
376 sgen_fragment_allocator_add (&collector_allocator, promotion_barrier, end);
378 region_age_size = (end - start) >> SGEN_TO_SPACE_GRANULE_BITS;
379 region_age = (char *)g_malloc0 (region_age_size);
383 handle_gc_param (const char *opt)
385 if (g_str_has_prefix (opt, "alloc-ratio=")) {
386 const char *arg = strchr (opt, '=') + 1;
387 int percentage = atoi (arg);
388 if (percentage < 1 || percentage > 100) {
389 fprintf (stderr, "alloc-ratio must be an integer in the range 1-100.\n");
392 alloc_ratio = (float)percentage / 100.0f;
396 if (g_str_has_prefix (opt, "promotion-age=")) {
397 const char *arg = strchr (opt, '=') + 1;
398 promote_age = atoi (arg);
399 if (promote_age < 1 || promote_age >= MAX_AGE) {
400 fprintf (stderr, "promotion-age must be an integer in the range 1-%d.\n", MAX_AGE - 1);
409 print_gc_param_usage (void)
413 " alloc-ratio=P (where P is a percentage, an integer in 1-100)\n"
414 " promotion-age=P (where P is a number, an integer in 1-%d)\n",
419 /******************************************Copy/Scan functins ************************************************/
421 #define SGEN_SPLIT_NURSERY
423 #define SERIAL_COPY_OBJECT split_nursery_serial_copy_object
424 #define SERIAL_COPY_OBJECT_FROM_OBJ split_nursery_serial_copy_object_from_obj
426 #include "sgen-minor-copy-object.h"
427 #include "sgen-minor-scan-object.h"
430 sgen_split_nursery_init (SgenMinorCollector *collector)
432 collector->is_split = TRUE;
434 collector->alloc_for_promotion = minor_alloc_for_promotion;
436 collector->prepare_to_space = prepare_to_space;
437 collector->clear_fragments = clear_fragments;
438 collector->build_fragments_get_exclude_head = build_fragments_get_exclude_head;
439 collector->build_fragments_release_exclude_head = build_fragments_release_exclude_head;
440 collector->build_fragments_finish = build_fragments_finish;
441 collector->init_nursery = init_nursery;
442 collector->handle_gc_param = handle_gc_param;
443 collector->print_gc_param_usage = print_gc_param_usage;
445 FILL_MINOR_COLLECTOR_COPY_OBJECT (collector);
446 FILL_MINOR_COLLECTOR_SCAN_OBJECT (collector);