mono/sgen/sgen-split-nursery.c

   1 /*
   2  * sgen-splliy-nursery.c: 3-space based nursery collector.
   3  *
   4  * Author:
   5  *      Rodrigo Kumpera Kumpera <kumpera@gmail.com>
   6  *
   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
  11  *
  12  * Licensed under the MIT license. See LICENSE file in the project root for full license information.
  13  */
  14
  15 #include "config.h"
  16 #ifdef HAVE_SGEN_GC
  17
  18 #include <string.h>
  19 #include <stdlib.h>
  20
  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"
  26
  27 /*
  28 The nursery is logically divided into 3 spaces: Allocator space and two Survivor spaces.
  29
  30 Objects are born (allocated by the mutator) in the Allocator Space.
  31
  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.
  34
  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.
  38
  39
  40 The nursery is physically divided in two parts, set by the promotion barrier.
  41
  42 The Allocator Space takes the botton part of the nursery.
  43
  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.
  47
  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.
  52
  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.
  56
  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.
  60
  61 TODO:
  62 -The promotion barrier is statically defined to 50% of the nursery, it should be dinamically adjusted based
  63 on survival rates;
  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;
  73 */
  74
  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)))
  80
  81 /*
  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.
  84 */
  85 #define MAX_AGE 15
  86
  87 /*
  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).
  93  */
  94
  95 typedef struct {
  96         char *next;
  97         char *end;
  98 } AgeAllocationBuffer;
  99
 100 /* Limits the ammount of memory the mutator can have. */
 101 static char *promotion_barrier;
 102
 103 /*
 104 Promotion age and alloc ratio are the two nursery knobs to control
 105 how much effort we want to spend on young objects.
 106
 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
 109 age all objects.
 110
 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.
 114
 115 */
 116
 117
 118 /*
 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.
 121 */
 122 static int promote_age = 2;
 123
 124 /*
 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.
 128 */
 129 static float alloc_ratio = 60.f/100.f;
 130
 131
 132 static char *region_age;
 133 static size_t region_age_size;
 134 static AgeAllocationBuffer age_alloc_buffers [MAX_AGE];
 135
 136 /* The collector allocs from here. */
 137 static SgenFragmentAllocator collector_allocator;
 138
 139 static inline int
 140 get_object_age (GCObject *object)
 141 {
 142         size_t idx = ((char*)object - sgen_nursery_start) >> SGEN_TO_SPACE_GRANULE_BITS;
 143         return region_age [idx];
 144 }
 145
 146 static void
 147 set_age_in_range (char *start, char *end, int age)
 148 {
 149         char *region_start;
 150         size_t region_idx, length;
 151         region_idx = (start - sgen_nursery_start) >> SGEN_TO_SPACE_GRANULE_BITS;
 152         region_start = &region_age [region_idx];
 153         length = (end - start) >> SGEN_TO_SPACE_GRANULE_BITS;
 154         memset (region_start, age, length);
 155 }
 156
 157 static inline void
 158 mark_bit (char *space_bitmap, char *pos)
 159 {
 160         size_t idx = (pos - sgen_nursery_start) >> SGEN_TO_SPACE_GRANULE_BITS;
 161         size_t byte = idx / 8;
 162         int bit = idx & 0x7;
 163
 164         g_assert (byte < sgen_space_bitmap_size);
 165         space_bitmap [byte] |= 1 << bit;
 166 }
 167
 168 static void
 169 mark_bits_in_range (char *space_bitmap, char *start, char *end)
 170 {
 171         start = (char *)align_down (start, SGEN_TO_SPACE_GRANULE_BITS);
 172         end = (char *)align_up (end, SGEN_TO_SPACE_GRANULE_BITS);
 173
 174         for (;start < end; start += SGEN_TO_SPACE_GRANULE_IN_BYTES)
 175                 mark_bit (space_bitmap, start);
 176 }
 177
 178 /*
 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.
 186  */
 187 static void
 188 fragment_list_split (SgenFragmentAllocator *allocator)
 189 {
 190         SgenFragment *prev = NULL, *list = allocator->region_head;
 191
 192         while (list) {
 193                 if (list->fragment_end > promotion_barrier) {
 194                         if (list->fragment_start < promotion_barrier) {
 195                                 SgenFragment *res = sgen_fragment_allocator_alloc ();
 196
 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);
 203
 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);
 207
 208                                 allocator->region_head = allocator->alloc_head = res;
 209                                 return;
 210                         } else {
 211                                 if (prev)
 212                                         prev->next = prev->next_in_order = NULL;
 213                                 allocator->region_head = allocator->alloc_head = list;
 214                                 return;
 215                         }
 216                 }
 217                 set_age_in_range (list->fragment_start, list->fragment_end, 0);
 218                 prev = list;
 219                 list = list->next;
 220         }
 221         allocator->region_head = allocator->alloc_head = NULL;
 222 }
 223
 224 /******************************************Minor Collector API ************************************************/
 225
 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)
 228
 229 static char*
 230 alloc_for_promotion_slow_path (int age, size_t objsize)
 231 {
 232         char *p;
 233         size_t allocated_size;
 234         size_t aligned_objsize = (size_t)align_up (objsize, SGEN_TO_SPACE_GRANULE_BITS);
 235
 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),
 240                 &allocated_size);
 241         if (p) {
 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;
 246         }
 247         return p;
 248 }
 249
 250 static inline GCObject*
 251 alloc_for_promotion (GCVTable vtable, GCObject *obj, size_t objsize, gboolean has_references)
 252 {
 253         char *p = NULL;
 254         int age;
 255
 256         age = get_object_age (obj);
 257         if (age >= promote_age)
 258                 return major_collector.alloc_object (vtable, objsize, has_references);
 259
 260         /* Promote! */
 261         ++age;
 262
 263         p = age_alloc_buffers [age].next;
 264         if (G_LIKELY (p + objsize <= age_alloc_buffers [age].end)) {
 265         age_alloc_buffers [age].next += objsize;
 266         } else {
 267                 p = alloc_for_promotion_slow_path (age, objsize);
 268                 if (!p)
 269                         return major_collector.alloc_object (vtable, objsize, has_references);
 270         }
 271
 272         /* FIXME: assumes object layout */
 273         *(GCVTable*)p = vtable;
 274
 275         return (GCObject*)p;
 276 }
 277
 278 static GCObject*
 279 minor_alloc_for_promotion (GCVTable vtable, GCObject *obj, size_t objsize, gboolean has_references)
 280 {
 281         /*
 282         We only need to check for a non-nursery object if we're doing a major collection.
 283         */
 284         if (!sgen_ptr_in_nursery (obj))
 285                 return major_collector.alloc_object (vtable, objsize, has_references);
 286
 287         return alloc_for_promotion (vtable, obj, objsize, has_references);
 288 }
 289
 290 static SgenFragment*
 291 build_fragments_get_exclude_head (void)
 292 {
 293         int i;
 294         for (i = 0; i < MAX_AGE; ++i) {
 295                 /*If we OOM'd on the last collection ->end might be null while ->next not.*/
 296                 if (age_alloc_buffers [i].end)
 297                         sgen_clear_range (age_alloc_buffers [i].next, age_alloc_buffers [i].end);
 298         }
 299
 300         return collector_allocator.region_head;
 301 }
 302
 303 static void
 304 build_fragments_release_exclude_head (void)
 305 {
 306         sgen_fragment_allocator_release (&collector_allocator);
 307 }
 308
 309 static void
 310 build_fragments_finish (SgenFragmentAllocator *allocator)
 311 {
 312         /* We split the fragment list based on the promotion barrier. */
 313         collector_allocator = *allocator;
 314         fragment_list_split (&collector_allocator);
 315 }
 316
 317 static void
 318 prepare_to_space (char *to_space_bitmap, size_t space_bitmap_size)
 319 {
 320         SgenFragment **previous, *frag;
 321
 322         memset (to_space_bitmap, 0, space_bitmap_size);
 323         memset (age_alloc_buffers, 0, sizeof (age_alloc_buffers));
 324
 325         previous = &collector_allocator.alloc_head;
 326
 327         for (frag = *previous; frag; frag = *previous) {
 328                 char *start = (char *)align_up (frag->fragment_next, SGEN_TO_SPACE_GRANULE_BITS);
 329                 char *end = (char *)align_down (frag->fragment_end, SGEN_TO_SPACE_GRANULE_BITS);
 330
 331                 /* Fragment is too small to be usable. */
 332                 if ((end - start) < SGEN_MAX_NURSERY_WASTE) {
 333                         sgen_clear_range (frag->fragment_next, frag->fragment_end);
 334                         frag->fragment_next = frag->fragment_end = frag->fragment_start;
 335                         *previous = frag->next;
 336                         continue;
 337                 }
 338
 339                 /*
 340                 We need to insert 3 phony objects so the fragments build step can correctly
 341                 walk the nursery.
 342                 */
 343
 344                 /* Clean the fragment range. */
 345                 sgen_clear_range (start, end);
 346                 /* We need a phony object in between the original fragment start and the effective one. */
 347                 if (start != frag->fragment_next)
 348                         sgen_clear_range (frag->fragment_next, start);
 349                 /* We need an phony object in between the new fragment end and the original fragment end. */
 350                 if (end != frag->fragment_end)
 351                         sgen_clear_range (end, frag->fragment_end);
 352
 353                 frag->fragment_start = frag->fragment_next = start;
 354                 frag->fragment_end = end;
 355                 mark_bits_in_range (to_space_bitmap, start, end);
 356                 previous = &frag->next;
 357         }
 358 }
 359
 360 static void
 361 clear_fragments (void)
 362 {
 363         sgen_clear_allocator_fragments (&collector_allocator);
 364 }
 365
 366 static void
 367 init_nursery (SgenFragmentAllocator *allocator, char *start, char *end)
 368 {
 369         int alloc_quote = (int)((end - start) * alloc_ratio);
 370         promotion_barrier = (char *)align_down (start + alloc_quote, 3);
 371         sgen_fragment_allocator_add (allocator, start, promotion_barrier);
 372         sgen_fragment_allocator_add (&collector_allocator, promotion_barrier, end);
 373
 374         region_age_size = (end - start) >> SGEN_TO_SPACE_GRANULE_BITS;
 375         region_age = (char *)g_malloc0 (region_age_size);
 376 }
 377
 378 static gboolean
 379 handle_gc_param (const char *opt)
 380 {
 381         if (g_str_has_prefix (opt, "alloc-ratio=")) {
 382                 const char *arg = strchr (opt, '=') + 1;
 383                 int percentage = atoi (arg);
 384                 if (percentage < 1 || percentage > 100) {
 385                         fprintf (stderr, "alloc-ratio must be an integer in the range 1-100.\n");
 386                         exit (1);
 387                 }
 388                 alloc_ratio = (float)percentage / 100.0f;
 389                 return TRUE;
 390         }
 391
 392         if (g_str_has_prefix (opt, "promotion-age=")) {
 393                 const char *arg = strchr (opt, '=') + 1;
 394                 promote_age = atoi (arg);
 395                 if (promote_age < 1 || promote_age >= MAX_AGE) {
 396                         fprintf (stderr, "promotion-age must be an integer in the range 1-%d.\n", MAX_AGE - 1);
 397                         exit (1);
 398                 }
 399                 return TRUE;
 400         }
 401         return FALSE;
 402 }
 403
 404 static void
 405 print_gc_param_usage (void)
 406 {
 407         fprintf (stderr,
 408                         ""
 409                         "  alloc-ratio=P (where P is a percentage, an integer in 1-100)\n"
 410                         "  promotion-age=P (where P is a number, an integer in 1-%d)\n",
 411                         MAX_AGE - 1
 412                         );
 413 }
 414
 415 /******************************************Copy/Scan functins ************************************************/
 416
 417 #define SGEN_SPLIT_NURSERY
 418
 419 #define SERIAL_COPY_OBJECT split_nursery_serial_copy_object
 420 #define SERIAL_COPY_OBJECT_FROM_OBJ split_nursery_serial_copy_object_from_obj
 421
 422 #include "sgen-minor-copy-object.h"
 423 #include "sgen-minor-scan-object.h"
 424
 425 void
 426 sgen_split_nursery_init (SgenMinorCollector *collector)
 427 {
 428         collector->is_split = TRUE;
 429
 430         collector->alloc_for_promotion = minor_alloc_for_promotion;
 431
 432         collector->prepare_to_space = prepare_to_space;
 433         collector->clear_fragments = clear_fragments;
 434         collector->build_fragments_get_exclude_head = build_fragments_get_exclude_head;
 435         collector->build_fragments_release_exclude_head = build_fragments_release_exclude_head;
 436         collector->build_fragments_finish = build_fragments_finish;
 437         collector->init_nursery = init_nursery;
 438         collector->handle_gc_param = handle_gc_param;
 439         collector->print_gc_param_usage = print_gc_param_usage;
 440
 441         FILL_MINOR_COLLECTOR_COPY_OBJECT (collector);
 442         FILL_MINOR_COLLECTOR_SCAN_OBJECT (collector);
 443 }
 444
 445
 446 #endif