X-Git-Url: http://wien.tomnetworks.com/gitweb/?a=blobdiff_plain;f=mono%2Fmetadata%2Fsgen-split-nursery.c;h=60e4621330de173b38df1e4c58eb9f021531f8aa;hb=3252b41ac274aae2c8b32ddfb9d0c17b84e2a593;hp=d839f0cd328423d3db560ca1114ac404ed58eb29;hpb=ec9e715ec2976c4bf37264896de63d1ad3d05b34;p=mono.git diff --git a/mono/metadata/sgen-split-nursery.c b/mono/metadata/sgen-split-nursery.c index d839f0cd328..60e4621330d 100644 --- a/mono/metadata/sgen-split-nursery.c +++ b/mono/metadata/sgen-split-nursery.c @@ -37,6 +37,7 @@ #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. @@ -61,7 +62,7 @@ of objects from the Allocator Space. 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 @@ -75,12 +76,15 @@ are naturally aligned in both ends to that granule to avoid wronly classifying a 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. */ @@ -89,12 +93,90 @@ objects from non-stack roots, specially those found in the remembered set; #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) @@ -117,6 +199,15 @@ mark_bits_in_range (char *space_bitmap, char *start, char *end) 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) { @@ -136,6 +227,7 @@ 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; @@ -146,6 +238,7 @@ fragment_list_split (SgenFragmentAllocator *allocator) return; } } + set_age_in_range (list->fragment_start, list->fragment_end, 0); prev = list; list = list->next; } @@ -153,25 +246,98 @@ fragment_list_split (SgenFragmentAllocator *allocator) } /******************************************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; } @@ -179,24 +345,65 @@ static inline char* 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; } @@ -220,6 +427,7 @@ prepare_to_space (char *to_space_bitmap, int space_bitmap_size) 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; @@ -235,8 +443,19 @@ prepare_to_space (char *to_space_bitmap, int space_bitmap_size) 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; @@ -254,15 +473,56 @@ clear_fragments (void) 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" @@ -270,8 +530,8 @@ init_nursery (SgenFragmentAllocator *allocator, char *start, char *end) 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; @@ -279,10 +539,13 @@ sgen_split_nursery_init (SgenMinorCollector *collector) 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