X-Git-Url: http://wien.tomnetworks.com/gitweb/?a=blobdiff_plain;f=mono%2Fmetadata%2Fsgen-gc.c;h=1691c436563372acfe47dd352e95481e9d9e59a6;hb=a9122365b94e9e2c0bddc52211998bebca49cb09;hp=1852431527c2b408e6b7be963d91318489f1fdb1;hpb=e891d748c06c562fa91f9ae5e97d7f452d56403d;p=mono.git diff --git a/mono/metadata/sgen-gc.c b/mono/metadata/sgen-gc.c index 1852431527c..1691c436563 100644 --- a/mono/metadata/sgen-gc.c +++ b/mono/metadata/sgen-gc.c @@ -169,6 +169,12 @@ assigned TLABs and if that's more than some percentage of the nursery size, reduce the TLAB size. + *) Explore placing unreachable objects on unused nursery memory. + Instead of memset'ng a region to zero, place an int[] covering it. + A good place to start is add_nursery_frag. The tricky thing here is + placing those objects atomically outside of a collection. + + */ #include "config.h" #ifdef HAVE_SGEN_GC @@ -280,6 +286,9 @@ static long long stat_global_remsets_readded = 0; static long long stat_global_remsets_processed = 0; static long long stat_global_remsets_discarded = 0; +static long long stat_wasted_fragments_used = 0; +static long long stat_wasted_fragments_bytes = 0; + static int stat_wbarrier_set_field = 0; static int stat_wbarrier_set_arrayref = 0; static int stat_wbarrier_arrayref_copy = 0; @@ -936,6 +945,9 @@ static char *nursery_last_pinned_end = NULL; */ static guint32 tlab_size = (1024 * 4); +/*How much space is tolerable to be wasted from the current fragment when allocating a new TLAB*/ +#define MAX_NURSERY_TLAB_WASTE 512 + /* fragments that are free and ready to be used for allocation */ static Fragment *nursery_fragments = NULL; /* freeelist of fragment structures */ @@ -1002,6 +1014,7 @@ static void add_or_remove_disappearing_link (MonoObject *obj, void **link, gbool static void null_link_in_range (CopyOrMarkObjectFunc copy_func, char *start, char *end, int generation); static void null_links_for_domain (MonoDomain *domain, int generation); static gboolean search_fragment_for_size (size_t size); +static int search_fragment_for_size_range (size_t desired_size, size_t minimum_size); static void build_nursery_fragments (int start_pin, int end_pin); static void clear_nursery_fragments (char *next); static void pin_from_roots (void *start_nursery, void *end_nursery); @@ -2447,41 +2460,54 @@ new_gap (int gap) return gap; } -#if 0 -static int -compare_addr (const void *a, const void *b) -{ - return *(const void **)a - *(const void **)b; -} -#endif - -/* sort the addresses in array in increasing order */ +/* Sort the addresses in array in increasing order. + * Done using a by-the book heap sort. Which has decent and stable performance, is pretty cache efficient. + */ static void sort_addresses (void **array, int size) { - /* - * qsort is slower as predicted. - * qsort (array, size, sizeof (gpointer), compare_addr); - * return; - */ - int gap = size; - int swapped, end; - while (TRUE) { - int i; - gap = new_gap (gap); - swapped = FALSE; - end = size - gap; - for (i = 0; i < end; i++) { - int j = i + gap; - if (array [i] > array [j]) { - void* val = array [i]; - array [i] = array [j]; - array [j] = val; - swapped = TRUE; - } + int i; + void *tmp; + + for (i = 1; i < size; ++i) { + int child = i; + while (child > 0) { + int parent = (child - 1) / 2; + + if (array [parent] >= array [child]) + break; + + tmp = array [parent]; + array [parent] = array [child]; + array [child] = tmp; + + child = parent; + } + } + + for (i = size - 1; i > 0; --i) { + int end, root; + tmp = array [i]; + array [i] = array [0]; + array [0] = tmp; + + end = i - 1; + root = 0; + + while (root * 2 + 1 <= end) { + int child = root * 2 + 1; + + if (child < end && array [child] < array [child + 1]) + ++child; + if (array [root] >= array [child]) + break; + + tmp = array [root]; + array [root] = array [child]; + array [child] = tmp; + + root = child; } - if (gap == 1 && !swapped) - break; } } @@ -2806,6 +2832,7 @@ add_nursery_frag (size_t frag_size, char* frag_start, char* frag_end) fragment_total += frag_size; } else { /* Clear unused fragments, pinning depends on this */ + /*TODO place an int[] here instead of the memset if size justify it*/ memset (frag_start, 0, frag_size); } } @@ -3206,6 +3233,9 @@ init_stats (void) mono_counters_register ("# nursery copy_object() failed forwarded", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_nursery_copy_object_failed_forwarded); mono_counters_register ("# nursery copy_object() failed pinned", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_nursery_copy_object_failed_pinned); + mono_counters_register ("# wasted fragments used", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_wasted_fragments_used); + mono_counters_register ("bytes in wasted fragments", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_wasted_fragments_bytes); + mono_counters_register ("Store remsets", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_store_remsets); mono_counters_register ("Unique store remsets", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_store_remsets_unique); mono_counters_register ("Saved remsets 1", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_saved_remsets_1); @@ -3974,6 +4004,22 @@ alloc_large_inner (MonoVTable *vtable, size_t size) return obj->data; } +static void +setup_fragment (Fragment *frag, Fragment *prev, size_t size) +{ + /* remove from the list */ + if (prev) + prev->next = frag->next; + else + nursery_fragments = frag->next; + nursery_next = frag->fragment_start; + nursery_frag_real_end = frag->fragment_end; + + 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)); + frag->next = fragment_freelist; + fragment_freelist = frag; +} + /* check if we have a suitable fragment in nursery_fragments to be able to allocate * an object of size @size * Return FALSE if not found (which means we need a collection) @@ -3991,17 +4037,7 @@ search_fragment_for_size (size_t size) prev = NULL; for (frag = nursery_fragments; frag; frag = frag->next) { if (size <= (frag->fragment_end - frag->fragment_start)) { - /* remove from the list */ - if (prev) - prev->next = frag->next; - else - nursery_fragments = frag->next; - nursery_next = frag->fragment_start; - nursery_frag_real_end = frag->fragment_end; - - 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)); - frag->next = fragment_freelist; - fragment_freelist = frag; + setup_fragment (frag, prev, size); return TRUE; } prev = frag; @@ -4009,6 +4045,53 @@ search_fragment_for_size (size_t size) return FALSE; } +/* + * Same as search_fragment_for_size but if search for @desired_size fails, try to satisfy @minimum_size. + * This improves nursery usage. + */ +static int +search_fragment_for_size_range (size_t desired_size, size_t minimum_size) +{ + Fragment *frag, *prev, *min_prev; + DEBUG (4, fprintf (gc_debug_file, "Searching nursery fragment %p, desired size: %zd minimum size %zd\n", nursery_frag_real_end, desired_size, minimum_size)); + + if (nursery_frag_real_end > nursery_next && nursery_clear_policy == CLEAR_AT_TLAB_CREATION) + /* Clear the remaining space, pinning depends on this */ + memset (nursery_next, 0, nursery_frag_real_end - nursery_next); + + min_prev = GINT_TO_POINTER (-1); + prev = NULL; + + for (frag = nursery_fragments; frag; frag = frag->next) { + int frag_size = frag->fragment_end - frag->fragment_start; + if (desired_size <= frag_size) { + setup_fragment (frag, prev, desired_size); + return desired_size; + } + if (minimum_size <= frag_size) + min_prev = prev; + + prev = frag; + } + + if (min_prev != GINT_TO_POINTER (-1)) { + int frag_size; + if (min_prev) + frag = min_prev->next; + else + frag = nursery_fragments; + + frag_size = frag->fragment_end - frag->fragment_start; + HEAVY_STAT (++stat_wasted_fragments_used); + HEAVY_STAT (stat_wasted_fragments_bytes += frag_size); + + setup_fragment (frag, min_prev, minimum_size); + return frag_size; + } + + return 0; +} + /* * Provide a variant that takes just the vtable for small fixed-size objects. * The aligned size is already computed and stored in vt->gc_descr. @@ -4023,7 +4106,6 @@ mono_gc_alloc_obj_nolock (MonoVTable *vtable, size_t size) /* FIXME: handle OOM */ void **p; char *new_next; - gboolean res; TLAB_ACCESS_INIT; HEAVY_STAT (++stat_objects_alloced); @@ -4117,6 +4199,7 @@ mono_gc_alloc_obj_nolock (MonoVTable *vtable, size_t size) return p; } + /*FIXME This codepath is current deadcode since tlab_size > MAX_SMALL_OBJ_SIZE*/ if (size > tlab_size) { /* Allocate directly from the nursery */ if (nursery_next + size >= nursery_frag_real_end) { @@ -4139,29 +4222,36 @@ mono_gc_alloc_obj_nolock (MonoVTable *vtable, size_t size) if (nursery_clear_policy == CLEAR_AT_TLAB_CREATION) memset (p, 0, size); } else { + int alloc_size = tlab_size; + int available_in_nursery = nursery_frag_real_end - nursery_next; if (TLAB_START) DEBUG (3, fprintf (gc_debug_file, "Retire TLAB: %p-%p [%ld]\n", TLAB_START, TLAB_REAL_END, (long)(TLAB_REAL_END - TLAB_NEXT - size))); - if (nursery_next + tlab_size >= nursery_frag_real_end) { - res = search_fragment_for_size (tlab_size); - if (!res) { - minor_collect_or_expand_inner (tlab_size); - if (degraded_mode) { - p = alloc_degraded (vtable, size); - return p; + if (alloc_size >= available_in_nursery) { + if (available_in_nursery > MAX_NURSERY_TLAB_WASTE && available_in_nursery > size) { + alloc_size = available_in_nursery; + } else { + alloc_size = search_fragment_for_size_range (tlab_size, size); + if (!alloc_size) { + alloc_size = tlab_size; + minor_collect_or_expand_inner (tlab_size); + if (degraded_mode) { + p = alloc_degraded (vtable, size); + return p; + } } } } /* Allocate a new TLAB from the current nursery fragment */ TLAB_START = nursery_next; - nursery_next += tlab_size; + nursery_next += alloc_size; TLAB_NEXT = TLAB_START; - TLAB_REAL_END = TLAB_START + tlab_size; - TLAB_TEMP_END = TLAB_START + MIN (SCAN_START_SIZE, tlab_size); + TLAB_REAL_END = TLAB_START + alloc_size; + TLAB_TEMP_END = TLAB_START + MIN (SCAN_START_SIZE, alloc_size); if (nursery_clear_policy == CLEAR_AT_TLAB_CREATION) - memset (TLAB_START, 0, tlab_size); + memset (TLAB_START, 0, alloc_size); /* Allocate from the TLAB */ p = (void*)TLAB_NEXT;