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 * This library is free software; you can redistribute it and/or
13 * modify it under the terms of the GNU Library General Public
14 * License 2.0 as published by the Free Software Foundation;
16 * This library is distributed in the hope that it will be useful,
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 * Library General Public License for more details.
21 * You should have received a copy of the GNU Library General Public
22 * License 2.0 along with this library; if not, write to the Free
23 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
32 #include "mono/sgen/sgen-gc.h"
33 #include "mono/sgen/sgen-protocol.h"
34 #include "mono/sgen/sgen-layout-stats.h"
35 #include "mono/sgen/sgen-client.h"
36 #include "mono/utils/mono-memory-model.h"
39 The nursery is logically divided into 3 spaces: Allocator space and two Survivor spaces.
41 Objects are born (allocated by the mutator) in the Allocator Space.
43 The Survivor spaces are divided in a copying collector style From and To spaces.
44 The hole of each space switch on each collection.
46 On each collection we process objects from the nursery this way:
47 Objects from the Allocator Space are evacuated into the To Space.
48 Objects from the Survivor From Space are evacuated into the old generation.
51 The nursery is physically divided in two parts, set by the promotion barrier.
53 The Allocator Space takes the botton part of the nursery.
55 The Survivor spaces are intermingled in the top part of the nursery. It's done
56 this way since the required size for the To Space depends on the survivor rate
57 of objects from the Allocator Space.
59 During a collection when the object scan function see a nursery object it must
60 determine if the object needs to be evacuated or left in place. Originally, this
61 check was done by checking if a forwarding pointer is installed, but now an object
62 can be in the To Space, it won't have a forwarding pointer and it must be left in place.
64 In order to solve that we classify nursery memory been either in the From Space or in
65 the To Space. Since the Allocator Space has the same behavior as the Survivor From Space
66 they are unified for this purpoise - a bit confusing at first.
68 This from/to classification is done on a larger granule than object to make the check efficient
69 and, due to that, we must make sure that all fragemnts used to allocate memory from the To Space
70 are naturally aligned in both ends to that granule to avoid wronly classifying a From Space object.
73 -The promotion barrier is statically defined to 50% of the nursery, it should be dinamically adjusted based
75 -We apply the same promotion policy to all objects, finalizable ones should age longer in the nursery;
76 -We apply the same promotion policy to all stages of a collection, maybe we should promote more aggressively
77 objects from non-stack roots, specially those found in the remembered set;
78 -Fix our major collection trigger to happen before we do a minor GC and collect the nursery only once.
79 -Make the serial fragment allocator fast path inlineable
80 -Make aging threshold be based on survival rates and survivor occupancy;
81 -Change promotion barrier to be size and not address based;
82 -Pre allocate memory for young ages to make sure that on overflow only the older suffer;
83 -Get rid of par_alloc_buffer_refill_mutex so to the parallel collection of the nursery doesn't suck;
86 /*FIXME Move this to a separate header. */
87 #define _toi(ptr) ((size_t)ptr)
88 #define make_ptr_mask(bits) ((1 << bits) - 1)
89 #define align_down(ptr, bits) ((void*)(_toi(ptr) & ~make_ptr_mask (bits)))
90 #define align_up(ptr, bits) ((void*) ((_toi(ptr) + make_ptr_mask (bits)) & ~make_ptr_mask (bits)))
93 Even though the effective max age is 255, aging that much doesn't make sense.
94 It might even make sense to use nimbles for age recording.
99 * Each age has its allocation buffer. Whenever an object is to be
100 * aged we try to fit it into its new age's allocation buffer. If
101 * that is not possible we get new space from the fragment allocator
102 * and set the allocation buffer to that space (minus the space
103 * required for the object).
109 } AgeAllocationBuffer;
111 /* Limits the ammount of memory the mutator can have. */
112 static char *promotion_barrier;
115 Promotion age and alloc ratio are the two nursery knobs to control
116 how much effort we want to spend on young objects.
118 Allocation ratio should be the inverse of the expected survivor rate.
119 The more objects surviver, the smaller the alloc ratio much be so we can
122 Promote age depends on how much effort we want to spend aging objects before
123 we promote them to the old generation. If addional ages don't somewhat improve
124 mortality, it's better avoid as they increase the cost of minor collections.
130 If we're evacuating an object with this age or more, promote it.
131 Age is the number of surviving collections of an object.
133 static int promote_age = 2;
136 Initial ratio of allocation and survivor spaces.
137 This should be read as the fraction of the whole nursery dedicated
138 for the allocator space.
140 static float alloc_ratio = 60.f/100.f;
143 static char *region_age;
144 static size_t region_age_size;
145 static AgeAllocationBuffer age_alloc_buffers [MAX_AGE];
147 /* The collector allocs from here. */
148 static SgenFragmentAllocator collector_allocator;
151 get_object_age (GCObject *object)
153 size_t idx = ((char*)object - sgen_nursery_start) >> SGEN_TO_SPACE_GRANULE_BITS;
154 return region_age [idx];
158 set_age_in_range (char *start, char *end, int age)
161 size_t region_idx, length;
162 region_idx = (start - sgen_nursery_start) >> SGEN_TO_SPACE_GRANULE_BITS;
163 region_start = ®ion_age [region_idx];
164 length = (end - start) >> SGEN_TO_SPACE_GRANULE_BITS;
165 memset (region_start, age, length);
169 mark_bit (char *space_bitmap, char *pos)
171 size_t idx = (pos - sgen_nursery_start) >> SGEN_TO_SPACE_GRANULE_BITS;
172 size_t byte = idx / 8;
175 g_assert (byte < sgen_space_bitmap_size);
176 space_bitmap [byte] |= 1 << bit;
180 mark_bits_in_range (char *space_bitmap, char *start, char *end)
182 start = align_down (start, SGEN_TO_SPACE_GRANULE_BITS);
183 end = align_up (end, SGEN_TO_SPACE_GRANULE_BITS);
185 for (;start < end; start += SGEN_TO_SPACE_GRANULE_IN_BYTES)
186 mark_bit (space_bitmap, start);
190 * This splits the fragments at the point of the promotion barrier.
191 * Two allocator are actually involved here: The mutator allocator and
192 * the collector allocator. This function is called with the
193 * collector, but it's a copy of the mutator allocator and contains
194 * all the fragments in the nursery. The fragments below the
195 * promotion barrier are left with the mutator allocator and the ones
196 * above are put into the collector allocator.
199 fragment_list_split (SgenFragmentAllocator *allocator)
201 SgenFragment *prev = NULL, *list = allocator->region_head;
204 if (list->fragment_end > promotion_barrier) {
205 if (list->fragment_start < promotion_barrier) {
206 SgenFragment *res = sgen_fragment_allocator_alloc ();
208 res->fragment_start = promotion_barrier;
209 res->fragment_next = promotion_barrier;
210 res->fragment_end = list->fragment_end;
211 res->next = list->next;
212 res->next_in_order = list->next_in_order;
213 g_assert (res->fragment_end > res->fragment_start);
215 list->fragment_end = promotion_barrier;
216 list->next = list->next_in_order = NULL;
217 set_age_in_range (list->fragment_start, list->fragment_end, 0);
219 allocator->region_head = allocator->alloc_head = res;
223 prev->next = prev->next_in_order = NULL;
224 allocator->region_head = allocator->alloc_head = list;
228 set_age_in_range (list->fragment_start, list->fragment_end, 0);
232 allocator->region_head = allocator->alloc_head = NULL;
235 /******************************************Minor Collector API ************************************************/
237 #define AGE_ALLOC_BUFFER_MIN_SIZE SGEN_TO_SPACE_GRANULE_IN_BYTES
238 #define AGE_ALLOC_BUFFER_DESIRED_SIZE (SGEN_TO_SPACE_GRANULE_IN_BYTES * 8)
241 alloc_for_promotion_slow_path (int age, size_t objsize)
244 size_t allocated_size;
245 size_t aligned_objsize = (size_t)align_up (objsize, SGEN_TO_SPACE_GRANULE_BITS);
247 p = sgen_fragment_allocator_serial_range_alloc (
248 &collector_allocator,
249 MAX (aligned_objsize, AGE_ALLOC_BUFFER_DESIRED_SIZE),
250 MAX (aligned_objsize, AGE_ALLOC_BUFFER_MIN_SIZE),
253 set_age_in_range (p, p + allocated_size, age);
254 sgen_clear_range (age_alloc_buffers [age].next, age_alloc_buffers [age].end);
255 age_alloc_buffers [age].next = p + objsize;
256 age_alloc_buffers [age].end = p + allocated_size;
261 static inline GCObject*
262 alloc_for_promotion (GCVTable vtable, GCObject *obj, size_t objsize, gboolean has_references)
267 age = get_object_age (obj);
268 if (age >= promote_age)
269 return major_collector.alloc_object (vtable, objsize, has_references);
274 p = age_alloc_buffers [age].next;
275 if (G_LIKELY (p + objsize <= age_alloc_buffers [age].end)) {
276 age_alloc_buffers [age].next += objsize;
278 p = alloc_for_promotion_slow_path (age, objsize);
280 return major_collector.alloc_object (vtable, objsize, has_references);
283 /* FIXME: assumes object layout */
284 *(GCVTable*)p = vtable;
290 minor_alloc_for_promotion (GCVTable vtable, GCObject *obj, size_t objsize, gboolean has_references)
293 We only need to check for a non-nursery object if we're doing a major collection.
295 if (!sgen_ptr_in_nursery (obj))
296 return major_collector.alloc_object (vtable, objsize, has_references);
298 return alloc_for_promotion (vtable, obj, objsize, has_references);
302 build_fragments_get_exclude_head (void)
305 for (i = 0; i < MAX_AGE; ++i) {
306 /*If we OOM'd on the last collection ->end might be null while ->next not.*/
307 if (age_alloc_buffers [i].end)
308 sgen_clear_range (age_alloc_buffers [i].next, age_alloc_buffers [i].end);
311 return collector_allocator.region_head;
315 build_fragments_release_exclude_head (void)
317 sgen_fragment_allocator_release (&collector_allocator);
321 build_fragments_finish (SgenFragmentAllocator *allocator)
323 /* We split the fragment list based on the promotion barrier. */
324 collector_allocator = *allocator;
325 fragment_list_split (&collector_allocator);
329 prepare_to_space (char *to_space_bitmap, size_t space_bitmap_size)
331 SgenFragment **previous, *frag;
333 memset (to_space_bitmap, 0, space_bitmap_size);
334 memset (age_alloc_buffers, 0, sizeof (age_alloc_buffers));
336 previous = &collector_allocator.alloc_head;
338 for (frag = *previous; frag; frag = *previous) {
339 char *start = align_up (frag->fragment_next, SGEN_TO_SPACE_GRANULE_BITS);
340 char *end = align_down (frag->fragment_end, SGEN_TO_SPACE_GRANULE_BITS);
342 /* Fragment is too small to be usable. */
343 if ((end - start) < SGEN_MAX_NURSERY_WASTE) {
344 sgen_clear_range (frag->fragment_next, frag->fragment_end);
345 frag->fragment_next = frag->fragment_end = frag->fragment_start;
346 *previous = frag->next;
351 We need to insert 3 phony objects so the fragments build step can correctly
355 /* Clean the fragment range. */
356 sgen_clear_range (start, end);
357 /* We need a phony object in between the original fragment start and the effective one. */
358 if (start != frag->fragment_next)
359 sgen_clear_range (frag->fragment_next, start);
360 /* We need an phony object in between the new fragment end and the original fragment end. */
361 if (end != frag->fragment_end)
362 sgen_clear_range (end, frag->fragment_end);
364 frag->fragment_start = frag->fragment_next = start;
365 frag->fragment_end = end;
366 mark_bits_in_range (to_space_bitmap, start, end);
367 previous = &frag->next;
372 clear_fragments (void)
374 sgen_clear_allocator_fragments (&collector_allocator);
378 init_nursery (SgenFragmentAllocator *allocator, char *start, char *end)
380 int alloc_quote = (int)((end - start) * alloc_ratio);
381 promotion_barrier = align_down (start + alloc_quote, 3);
382 sgen_fragment_allocator_add (allocator, start, promotion_barrier);
383 sgen_fragment_allocator_add (&collector_allocator, promotion_barrier, end);
385 region_age_size = (end - start) >> SGEN_TO_SPACE_GRANULE_BITS;
386 region_age = g_malloc0 (region_age_size);
390 handle_gc_param (const char *opt)
392 if (g_str_has_prefix (opt, "alloc-ratio=")) {
393 const char *arg = strchr (opt, '=') + 1;
394 int percentage = atoi (arg);
395 if (percentage < 1 || percentage > 100) {
396 fprintf (stderr, "alloc-ratio must be an integer in the range 1-100.\n");
399 alloc_ratio = (float)percentage / 100.0f;
403 if (g_str_has_prefix (opt, "promotion-age=")) {
404 const char *arg = strchr (opt, '=') + 1;
405 promote_age = atoi (arg);
406 if (promote_age < 1 || promote_age >= MAX_AGE) {
407 fprintf (stderr, "promotion-age must be an integer in the range 1-%d.\n", MAX_AGE - 1);
416 print_gc_param_usage (void)
420 " alloc-ratio=P (where P is a percentage, an integer in 1-100)\n"
421 " promotion-age=P (where P is a number, an integer in 1-%d)\n",
426 /******************************************Copy/Scan functins ************************************************/
428 #define SGEN_SPLIT_NURSERY
430 #define SERIAL_COPY_OBJECT split_nursery_serial_copy_object
431 #define SERIAL_COPY_OBJECT_FROM_OBJ split_nursery_serial_copy_object_from_obj
433 #include "sgen-minor-copy-object.h"
434 #include "sgen-minor-scan-object.h"
437 sgen_split_nursery_init (SgenMinorCollector *collector)
439 collector->is_split = TRUE;
441 collector->alloc_for_promotion = minor_alloc_for_promotion;
443 collector->prepare_to_space = prepare_to_space;
444 collector->clear_fragments = clear_fragments;
445 collector->build_fragments_get_exclude_head = build_fragments_get_exclude_head;
446 collector->build_fragments_release_exclude_head = build_fragments_release_exclude_head;
447 collector->build_fragments_finish = build_fragments_finish;
448 collector->init_nursery = init_nursery;
449 collector->handle_gc_param = handle_gc_param;
450 collector->print_gc_param_usage = print_gc_param_usage;
452 FILL_MINOR_COLLECTOR_COPY_OBJECT (collector);
453 FILL_MINOR_COLLECTOR_SCAN_OBJECT (collector);