#include "metadata/sgen-gc.h"
#include "metadata/sgen-protocol.h"
+#include "utils/mono-memory-model.h"
/*
The nursery is logically divided into 3 spaces: Allocator space and two Survivor spaces.
During a collection when the object scan function see a nursery object it must
determine if the object needs to be evacuated or left in place. Originally, this
-check was done by checking is a forwarding pointer is installed, but now an object
+check was done by checking if a forwarding pointer is installed, but now an object
can be in the To Space, it won't have a forwarding pointer and it must be left in place.
In order to solve that we classify nursery memory been either in the From Space or in
TODO:
-The promotion barrier is statically defined to 50% of the nursery, it should be dinamically adjusted based
on survival rates;
--Objects are aged just one collection, we need to implement multiple cycle aging;
-We apply the same promotion policy to all objects, finalizable ones should age longer in the nursery;
-We apply the same promotion policy to all stages of a collection, maybe we should promote more aggressively
objects from non-stack roots, specially those found in the remembered set;
-Fix our major collection trigger to happen before we do a minor GC and collect the nursery only once.
-Make the serial fragment allocator fast path inlineable
+-Make aging threshold be based on survival rates and survivor occupancy;
+-Change promotion barrier to be size and not address based;
+-Pre allocate memory for young ages to make sure that on overflow only the older suffer;
+-Get rid of par_alloc_buffer_refill_mutex so to the parallel collection of the nursery doesn't suck;
*/
/*FIXME Move this to a separate header. */
#define align_down(ptr, bits) ((void*)(_toi(ptr) & ~make_ptr_mask (bits)))
#define align_up(ptr, bits) ((void*) ((_toi(ptr) + make_ptr_mask (bits)) & ~make_ptr_mask (bits)))
+/*
+Even though the effective max age is 255, aging that much doesn't make sense.
+It might even make sense to use nimbles for age recording.
+*/
+#define MAX_AGE 15
+
+/*
+ * Each age has its allocation buffer. Whenever an object is to be
+ * aged we try to fit it into its new age's allocation buffer. If
+ * that is not possible we get new space from the fragment allocator
+ * and set the allocation buffer to that space (minus the space
+ * required for the object).
+ */
+
+typedef struct {
+ char *next;
+ char *end;
+} AgeAllocationBuffer;
+
/* Limits the ammount of memory the mutator can have. */
static char *promotion_barrier;
+/*
+Promotion age and alloc ratio are the two nursery knobs to control
+how much effort we want to spend on young objects.
+
+Allocation ratio should be the inverse of the expected survivor rate.
+The more objects surviver, the smaller the alloc ratio much be so we can
+age all objects.
+
+Promote age depends on how much effort we want to spend aging objects before
+we promote them to the old generation. If addional ages don't somewhat improve
+mortality, it's better avoid as they increase the cost of minor collections.
+
+*/
+
+
+/*
+If we're evacuating an object with this age or more, promote it.
+Age is the number of surviving collections of an object.
+*/
+static int promote_age = 2;
+
+/*
+Initial ratio of allocation and survivor spaces.
+This should be read as the fraction of the whole nursery dedicated
+for the allocator space.
+*/
+static float alloc_ratio = 60.f/100.f;
+
+
+static char *region_age;
+static int region_age_size;
+static AgeAllocationBuffer age_alloc_buffers [MAX_AGE];
+
/* The collector allocs from here. */
static SgenFragmentAllocator collector_allocator;
+static LOCK_DECLARE (par_alloc_buffer_refill_mutex);
+
+static inline int
+get_object_age (char *object)
+{
+ int idx = (object - sgen_nursery_start) >> SGEN_TO_SPACE_GRANULE_BITS;
+ return region_age [idx];
+}
+
+static inline void
+set_object_age (char *object, int age)
+{
+ int idx = (object - sgen_nursery_start) >> SGEN_TO_SPACE_GRANULE_BITS;
+ region_age [idx] = age;
+}
+
+static void
+set_age_in_range (char *start, char *end, int age)
+{
+ char *region_start;
+ int region_idx, length;
+ region_idx = (start - sgen_nursery_start) >> SGEN_TO_SPACE_GRANULE_BITS;
+ region_start = ®ion_age [region_idx];
+ length = (end - start) >> SGEN_TO_SPACE_GRANULE_BITS;
+ memset (region_start, age, length);
+}
static inline void
mark_bit (char *space_bitmap, char *pos)
mark_bit (space_bitmap, start);
}
+/*
+ * This splits the fragments at the point of the promotion barrier.
+ * Two allocator are actually involved here: The mutator allocator and
+ * the collector allocator. This function is called with the
+ * collector, but it's a copy of the mutator allocator and contains
+ * all the fragments in the nursery. The fragments below the
+ * promotion barrier are left with the mutator allocator and the ones
+ * above are put into the collector allocator.
+ */
static void
fragment_list_split (SgenFragmentAllocator *allocator)
{
list->fragment_end = promotion_barrier;
list->next = list->next_in_order = NULL;
+ set_age_in_range (list->fragment_start, list->fragment_end, 0);
allocator->region_head = allocator->alloc_head = res;
return;
return;
}
}
+ set_age_in_range (list->fragment_start, list->fragment_end, 0);
prev = list;
list = list->next;
}
}
/******************************************Minor Collector API ************************************************/
+
+#define AGE_ALLOC_BUFFER_MIN_SIZE SGEN_TO_SPACE_GRANULE_IN_BYTES
+#define AGE_ALLOC_BUFFER_DESIRED_SIZE (SGEN_TO_SPACE_GRANULE_IN_BYTES * 8)
+
+static char*
+alloc_for_promotion_slow_path (int age, size_t objsize)
+{
+ char *p;
+ size_t allocated_size;
+ size_t aligned_objsize = (size_t)align_up (objsize, SGEN_TO_SPACE_GRANULE_BITS);
+
+ p = sgen_fragment_allocator_serial_range_alloc (
+ &collector_allocator,
+ MAX (aligned_objsize, AGE_ALLOC_BUFFER_DESIRED_SIZE),
+ MAX (aligned_objsize, AGE_ALLOC_BUFFER_MIN_SIZE),
+ &allocated_size);
+ if (p) {
+ set_age_in_range (p, p + allocated_size, age);
+ sgen_clear_range (age_alloc_buffers [age].next, age_alloc_buffers [age].end);
+ age_alloc_buffers [age].next = p + objsize;
+ age_alloc_buffers [age].end = p + allocated_size;
+ }
+ return p;
+}
+
static inline char*
alloc_for_promotion (char *obj, size_t objsize, gboolean has_references)
{
- char *p;
+ char *p = NULL;
+ int age;
- if (objsize > SGEN_MAX_SMALL_OBJ_SIZE)
- g_error ("asked to allocate object size %d\n", objsize);
+ age = get_object_age (obj);
+ if (age >= promote_age)
+ return major_collector.alloc_object (objsize, has_references);
- /*This one will be internally promoted. */
- if (obj >= sgen_nursery_start && obj < promotion_barrier) {
- p = sgen_fragment_allocator_serial_alloc (&collector_allocator, objsize);
+ /* Promote! */
+ ++age;
- /* Have we failed to promote to the nursery, lets just evacuate it to old gen. */
+ p = age_alloc_buffers [age].next;
+ if (G_LIKELY (p + objsize <= age_alloc_buffers [age].end)) {
+ age_alloc_buffers [age].next += objsize;
+ } else {
+ p = alloc_for_promotion_slow_path (age, objsize);
if (!p)
p = major_collector.alloc_object (objsize, has_references);
+ }
+
+ return p;
+}
+
+static char*
+par_alloc_for_promotion_slow_path (int age, size_t objsize)
+{
+ char *p;
+ size_t allocated_size;
+ size_t aligned_objsize = (size_t)align_up (objsize, SGEN_TO_SPACE_GRANULE_BITS);
+
+ mono_mutex_lock (&par_alloc_buffer_refill_mutex);
+
+restart:
+ p = age_alloc_buffers [age].next;
+ if (G_LIKELY (p + objsize <= age_alloc_buffers [age].end)) {
+ if (SGEN_CAS_PTR ((void*)&age_alloc_buffers [age].next, p + objsize, p) != p)
+ goto restart;
} else {
- p = major_collector.alloc_object (objsize, has_references);
+ /* Reclaim remaining space - if we OOMd the nursery nothing to see here. */
+ char *end = age_alloc_buffers [age].end;
+ if (end) {
+ do {
+ p = age_alloc_buffers [age].next;
+ } while (SGEN_CAS_PTR ((void*)&age_alloc_buffers [age].next, end, p) != p);
+ sgen_clear_range (p, end);
+ }
+
+ /* By setting end to NULL we make sure no other thread can advance while we're updating.*/
+ age_alloc_buffers [age].end = NULL;
+ STORE_STORE_FENCE;
+
+ p = sgen_fragment_allocator_par_range_alloc (
+ &collector_allocator,
+ MAX (aligned_objsize, AGE_ALLOC_BUFFER_DESIRED_SIZE),
+ MAX (aligned_objsize, AGE_ALLOC_BUFFER_MIN_SIZE),
+ &allocated_size);
+ if (p) {
+ set_age_in_range (p, p + allocated_size, age);
+ age_alloc_buffers [age].next = p + objsize;
+ STORE_STORE_FENCE; /* Next must arrive before the new value for next. */
+ age_alloc_buffers [age].end = p + allocated_size;
+ }
}
+ mono_mutex_unlock (&par_alloc_buffer_refill_mutex);
return p;
}
par_alloc_for_promotion (char *obj, size_t objsize, gboolean has_references)
{
char *p;
+ int age;
- /*This one will be internally promoted. */
- if (obj >= sgen_nursery_start && obj < promotion_barrier) {
- p = sgen_fragment_allocator_par_alloc (&collector_allocator, objsize);
+ age = get_object_age (obj);
+ if (age >= promote_age)
+ return major_collector.par_alloc_object (objsize, has_references);
+
+restart:
+ p = age_alloc_buffers [age].next;
+
+ LOAD_LOAD_FENCE; /* The read of ->next must happen before ->end */
+
+ if (G_LIKELY (p + objsize <= age_alloc_buffers [age].end)) {
+ if (SGEN_CAS_PTR ((void*)&age_alloc_buffers [age].next, p + objsize, p) != p)
+ goto restart;
+ } else {
+ p = par_alloc_for_promotion_slow_path (age, objsize);
/* Have we failed to promote to the nursery, lets just evacuate it to old gen. */
if (!p)
p = major_collector.par_alloc_object (objsize, has_references);
- } else {
- p = major_collector.par_alloc_object (objsize, has_references);
}
return p;
}
+static char*
+minor_alloc_for_promotion (char *obj, size_t objsize, gboolean has_references)
+{
+ /*
+ We only need to check for a non-nursery object if we're doing a major collection.
+ */
+ if (!sgen_ptr_in_nursery (obj))
+ return major_collector.alloc_object (objsize, has_references);
+
+ return alloc_for_promotion (obj, objsize, has_references);
+}
+
+static char*
+minor_par_alloc_for_promotion (char *obj, size_t objsize, gboolean has_references)
+{
+ /*
+ We only need to check for a non-nursery object if we're doing a major collection.
+ */
+ if (!sgen_ptr_in_nursery (obj))
+ return major_collector.par_alloc_object (objsize, has_references);
+
+ return par_alloc_for_promotion (obj, objsize, has_references);
+}
+
static SgenFragment*
build_fragments_get_exclude_head (void)
{
+ int i;
+ for (i = 0; i < MAX_AGE; ++i) {
+ /*If we OOM'd on the last collection ->end might be null while ->next not.*/
+ if (age_alloc_buffers [i].end)
+ sgen_clear_range (age_alloc_buffers [i].next, age_alloc_buffers [i].end);
+ }
+
return collector_allocator.region_head;
}
SgenFragment **previous, *frag;
memset (to_space_bitmap, 0, space_bitmap_size);
+ memset (age_alloc_buffers, 0, sizeof (age_alloc_buffers));
previous = &collector_allocator.alloc_head;
continue;
}
- sgen_clear_range (frag->fragment_next, start);
- sgen_clear_range (end, frag->fragment_end);
+ /*
+ We need to insert 3 phony objects so the fragments build step can correctly
+ walk the nursery.
+ */
+
+ /* Clean the fragment range. */
+ sgen_clear_range (start, end);
+ /* We need a phony object in between the original fragment start and the effective one. */
+ if (start != frag->fragment_next)
+ sgen_clear_range (frag->fragment_next, start);
+ /* We need an phony object in between the new fragment end and the original fragment end. */
+ if (end != frag->fragment_end)
+ sgen_clear_range (end, frag->fragment_end);
frag->fragment_start = frag->fragment_next = start;
frag->fragment_end = end;
static void
init_nursery (SgenFragmentAllocator *allocator, char *start, char *end)
{
- char *middle = start + (end - start) / 2;
- sgen_fragment_allocator_add (allocator, start, middle);
- sgen_fragment_allocator_add (&collector_allocator, middle, end);
+ int alloc_quote = (int)((end - start) * alloc_ratio);
+ promotion_barrier = align_down (start + alloc_quote, 3);
+ sgen_fragment_allocator_add (allocator, start, promotion_barrier);
+ sgen_fragment_allocator_add (&collector_allocator, promotion_barrier, end);
- promotion_barrier = middle;
+ region_age_size = (end - start) >> SGEN_TO_SPACE_GRANULE_BITS;
+ region_age = g_malloc0 (region_age_size);
+}
+
+static gboolean
+handle_gc_param (const char *opt)
+{
+ if (g_str_has_prefix (opt, "alloc-ratio=")) {
+ const char *arg = strchr (opt, '=') + 1;
+ int percentage = atoi (arg);
+ if (percentage < 1 || percentage > 100) {
+ fprintf (stderr, "alloc-ratio must be an integer in the range 1-100.\n");
+ exit (1);
+ }
+ alloc_ratio = (float)percentage / 100.0f;
+ return TRUE;
+ }
+
+ if (g_str_has_prefix (opt, "promotion-age=")) {
+ const char *arg = strchr (opt, '=') + 1;
+ promote_age = atoi (arg);
+ if (promote_age < 1 || promote_age >= MAX_AGE) {
+ fprintf (stderr, "promotion-age must be an integer in the range 1-%d.\n", MAX_AGE - 1);
+ exit (1);
+ }
+ return TRUE;
+ }
+ return FALSE;
+}
+
+static void
+print_gc_param_usage (void)
+{
+ fprintf (stderr,
+ ""
+ " alloc-ratio=P (where P is a percentage, an integer in 1-100)\n"
+ " promotion-age=P (where P is a number, an integer in 1-%d)\n",
+ MAX_AGE - 1
+ );
}
/******************************************Copy/Scan functins ************************************************/
+#define SGEN_SPLIT_NURSERY
+
#include "sgen-minor-copy-object.h"
#include "sgen-minor-scan-object.h"
void
sgen_split_nursery_init (SgenMinorCollector *collector)
{
- collector->alloc_for_promotion = alloc_for_promotion;
- collector->par_alloc_for_promotion = par_alloc_for_promotion;
+ collector->alloc_for_promotion = minor_alloc_for_promotion;
+ collector->par_alloc_for_promotion = minor_par_alloc_for_promotion;
collector->prepare_to_space = prepare_to_space;
collector->clear_fragments = clear_fragments;
collector->build_fragments_release_exclude_head = build_fragments_release_exclude_head;
collector->build_fragments_finish = build_fragments_finish;
collector->init_nursery = init_nursery;
+ collector->handle_gc_param = handle_gc_param;
+ collector->print_gc_param_usage = print_gc_param_usage;
FILL_MINOR_COLLECTOR_COPY_OBJECT (collector);
FILL_MINOR_COLLECTOR_SCAN_OBJECT (collector);
+ LOCK_INIT (par_alloc_buffer_refill_mutex);
}
-#endif
\ No newline at end of file
+#endif