mono/sgen/sgen-split-nursery.c

   1 /**
   2  * \file
   3  * 3-space based nursery collector.
   4  *
   5  * Author:
   6  *      Rodrigo Kumpera Kumpera <kumpera@gmail.com>
   7  *
   8  * Copyright 2001-2003 Ximian, Inc
   9  * Copyright 2003-2010 Novell, Inc.
  10  * Copyright 2011-2012 Xamarin Inc (http://www.xamarin.com)
  11  * Copyright (C) 2012 Xamarin Inc
  12  *
  13  * Licensed under the MIT license. See LICENSE file in the project root for full license information.
  14  */
  15
  16 #include "config.h"
  17 #ifdef HAVE_SGEN_GC
  18
  19 #include <string.h>
  20 #include <stdlib.h>
  21
  22 #include "mono/sgen/sgen-gc.h"
  23 #include "mono/sgen/sgen-protocol.h"
  24 #include "mono/sgen/sgen-layout-stats.h"
  25 #include "mono/sgen/sgen-client.h"
  26 #include "mono/utils/mono-memory-model.h"
  27
  28 /*
  29 The nursery is logically divided into 3 spaces: Allocator space and two Survivor spaces.
  30
  31 Objects are born (allocated by the mutator) in the Allocator Space.
  32
  33 The Survivor spaces are divided in a copying collector style From and To spaces.
  34 The hole of each space switch on each collection.
  35
  36 On each collection we process objects from the nursery this way:
  37 Objects from the Allocator Space are evacuated into the To Space.
  38 Objects from the Survivor From Space are evacuated into the old generation.
  39
  40
  41 The nursery is physically divided in two parts, set by the promotion barrier.
  42
  43 The Allocator Space takes the botton part of the nursery.
  44
  45 The Survivor spaces are intermingled in the top part of the nursery. It's done
  46 this way since the required size for the To Space depends on the survivor rate
  47 of objects from the Allocator Space.
  48
  49 During a collection when the object scan function see a nursery object it must
  50 determine if the object needs to be evacuated or left in place. Originally, this
  51 check was done by checking if a forwarding pointer is installed, but now an object
  52 can be in the To Space, it won't have a forwarding pointer and it must be left in place.
  53
  54 In order to solve that we classify nursery memory been either in the From Space or in
  55 the To Space. Since the Allocator Space has the same behavior as the Survivor From Space
  56 they are unified for this purpoise - a bit confusing at first.
  57
  58 This from/to classification is done on a larger granule than object to make the check efficient
  59 and, due to that, we must make sure that all fragemnts used to allocate memory from the To Space
  60 are naturally aligned in both ends to that granule to avoid wronly classifying a From Space object.
  61
  62 TODO:
  63 -The promotion barrier is statically defined to 50% of the nursery, it should be dinamically adjusted based
  64 on survival rates;
  65 -We apply the same promotion policy to all objects, finalizable ones should age longer in the nursery;
  66 -We apply the same promotion policy to all stages of a collection, maybe we should promote more aggressively
  67 objects from non-stack roots, specially those found in the remembered set;
  68 -Fix our major collection trigger to happen before we do a minor GC and collect the nursery only once.
  69 -Make the serial fragment allocator fast path inlineable
  70 -Make aging threshold be based on survival rates and survivor occupancy;
  71 -Change promotion barrier to be size and not address based;
  72 -Pre allocate memory for young ages to make sure that on overflow only the older suffer;
  73 -Get rid of par_alloc_buffer_refill_mutex so to the parallel collection of the nursery doesn't suck;
  74 */
  75
  76 /*FIXME Move this to a separate header. */
  77 #define _toi(ptr) ((size_t)ptr)
  78 #define make_ptr_mask(bits) ((1 << bits) - 1)
  79 #define align_down(ptr, bits) ((void*)(_toi(ptr) & ~make_ptr_mask (bits)))
  80 #define align_up(ptr, bits) ((void*) ((_toi(ptr) + make_ptr_mask (bits)) & ~make_ptr_mask (bits)))
  81
  82 /*
  83 Even though the effective max age is 255, aging that much doesn't make sense.
  84 It might even make sense to use nimbles for age recording.
  85 */
  86 #define MAX_AGE 15
  87
  88 /*
  89  * Each age has its allocation buffer.  Whenever an object is to be
  90  * aged we try to fit it into its new age's allocation buffer.  If
  91  * that is not possible we get new space from the fragment allocator
  92  * and set the allocation buffer to that space (minus the space
  93  * required for the object).
  94  */
  95
  96 typedef struct {
  97         char *next;
  98         char *end;
  99 } AgeAllocationBuffer;
 100
 101 /* Limits the ammount of memory the mutator can have. */
 102 static char *promotion_barrier;
 103
 104 /*
 105 Promotion age and alloc ratio are the two nursery knobs to control
 106 how much effort we want to spend on young objects.
 107
 108 Allocation ratio should be the inverse of the expected survivor rate.
 109 The more objects surviver, the smaller the alloc ratio much be so we can
 110 age all objects.
 111
 112 Promote age depends on how much effort we want to spend aging objects before
 113 we promote them to the old generation. If addional ages don't somewhat improve
 114 mortality, it's better avoid as they increase the cost of minor collections.
 115
 116 */
 117
 118
 119 /*
 120 If we're evacuating an object with this age or more, promote it.
 121 Age is the number of surviving collections of an object.
 122 */
 123 static int promote_age = 2;
 124
 125 /*
 126 Initial ratio of allocation and survivor spaces.
 127 This should be read as the fraction of the whole nursery dedicated
 128 for the allocator space.
 129 */
 130 static float alloc_ratio = 60.f/100.f;
 131
 132
 133 static char *region_age;
 134 static size_t region_age_size;
 135 static AgeAllocationBuffer age_alloc_buffers [MAX_AGE];
 136
 137 /* The collector allocs from here. */
 138 static SgenFragmentAllocator collector_allocator;
 139
 140 static inline int
 141 get_object_age (GCObject *object)
 142 {
 143         size_t idx = ((char*)object - sgen_nursery_start) >> SGEN_TO_SPACE_GRANULE_BITS;
 144         return region_age [idx];
 145 }
 146
 147 static void
 148 set_age_in_range (char *start, char *end, int age)
 149 {
 150         char *region_start;
 151         size_t region_idx, length;
 152         region_idx = (start - sgen_nursery_start) >> SGEN_TO_SPACE_GRANULE_BITS;
 153         region_start = &region_age [region_idx];
 154         length = (end - start) >> SGEN_TO_SPACE_GRANULE_BITS;
 155         memset (region_start, age, length);
 156 }
 157
 158 static inline void
 159 mark_bit (char *space_bitmap, char *pos)
 160 {
 161         size_t idx = (pos - sgen_nursery_start) >> SGEN_TO_SPACE_GRANULE_BITS;
 162         size_t byte = idx / 8;
 163         int bit = idx & 0x7;
 164
 165         g_assert (byte < sgen_space_bitmap_size);
 166         space_bitmap [byte] |= 1 << bit;
 167 }
 168
 169 static void
 170 mark_bits_in_range (char *space_bitmap, char *start, char *end)
 171 {
 172         start = (char *)align_down (start, SGEN_TO_SPACE_GRANULE_BITS);
 173         end = (char *)align_up (end, SGEN_TO_SPACE_GRANULE_BITS);
 174
 175         for (;start < end; start += SGEN_TO_SPACE_GRANULE_IN_BYTES)
 176                 mark_bit (space_bitmap, start);
 177 }
 178
 179 /*
 180  * This splits the fragments at the point of the promotion barrier.
 181  * Two allocator are actually involved here: The mutator allocator and
 182  * the collector allocator.  This function is called with the
 183  * collector, but it's a copy of the mutator allocator and contains
 184  * all the fragments in the nursery.  The fragments below the
 185  * promotion barrier are left with the mutator allocator and the ones
 186  * above are put into the collector allocator.
 187  */
 188 static void
 189 fragment_list_split (SgenFragmentAllocator *allocator)
 190 {
 191         SgenFragment *prev = NULL, *list = allocator->region_head;
 192
 193         while (list) {
 194                 if (list->fragment_end > promotion_barrier) {
 195                         if (list->fragment_start < promotion_barrier) {
 196                                 SgenFragment *res = sgen_fragment_allocator_alloc ();
 197
 198                                 res->fragment_start = promotion_barrier;
 199                                 res->fragment_next = promotion_barrier;
 200                                 res->fragment_end = list->fragment_end;
 201                                 res->next = list->next;
 202                                 res->next_in_order = list->next_in_order;
 203                                 g_assert (res->fragment_end > res->fragment_start);
 204
 205                                 list->fragment_end = promotion_barrier;
 206                                 list->next = list->next_in_order = NULL;
 207                                 set_age_in_range (list->fragment_start, list->fragment_end, 0);
 208
 209                                 allocator->region_head = allocator->alloc_head = res;
 210                                 return;
 211                         } else {
 212                                 if (prev)
 213                                         prev->next = prev->next_in_order = NULL;
 214                                 allocator->region_head = allocator->alloc_head = list;
 215                                 return;
 216                         }
 217                 }
 218                 set_age_in_range (list->fragment_start, list->fragment_end, 0);
 219                 prev = list;
 220                 list = list->next;
 221         }
 222         allocator->region_head = allocator->alloc_head = NULL;
 223 }
 224
 225 /******************************************Minor Collector API ************************************************/
 226
 227 #define AGE_ALLOC_BUFFER_MIN_SIZE SGEN_TO_SPACE_GRANULE_IN_BYTES
 228 #define AGE_ALLOC_BUFFER_DESIRED_SIZE (SGEN_TO_SPACE_GRANULE_IN_BYTES * 8)
 229
 230 static char*
 231 alloc_for_promotion_slow_path (int age, size_t objsize)
 232 {
 233         char *p;
 234         size_t allocated_size;
 235         size_t aligned_objsize = (size_t)align_up (objsize, SGEN_TO_SPACE_GRANULE_BITS);
 236
 237         p = (char *)sgen_fragment_allocator_serial_range_alloc (
 238                 &collector_allocator,
 239                 MAX (aligned_objsize, AGE_ALLOC_BUFFER_DESIRED_SIZE),
 240                 MAX (aligned_objsize, AGE_ALLOC_BUFFER_MIN_SIZE),
 241                 &allocated_size);
 242         if (p) {
 243                 set_age_in_range (p, p + allocated_size, age);
 244                 sgen_clear_range (age_alloc_buffers [age].next, age_alloc_buffers [age].end);
 245                 age_alloc_buffers [age].next = p + objsize;
 246                 age_alloc_buffers [age].end = p + allocated_size;
 247         }
 248         return p;
 249 }
 250
 251 static inline GCObject*
 252 alloc_for_promotion (GCVTable vtable, GCObject *obj, size_t objsize, gboolean has_references)
 253 {
 254         char *p = NULL;
 255         int age;
 256
 257         age = get_object_age (obj);
 258         if (age >= promote_age) {
 259                 total_promoted_size += objsize;
 260                 return major_collector.alloc_object (vtable, objsize, has_references);
 261         }
 262
 263         /* Promote! */
 264         ++age;
 265
 266         p = age_alloc_buffers [age].next;
 267         if (G_LIKELY (p + objsize <= age_alloc_buffers [age].end)) {
 268         age_alloc_buffers [age].next += objsize;
 269         } else {
 270                 p = alloc_for_promotion_slow_path (age, objsize);
 271                 if (!p) {
 272                         total_promoted_size += objsize;
 273                         return major_collector.alloc_object (vtable, objsize, has_references);
 274                 }
 275         }
 276
 277         /* FIXME: assumes object layout */
 278         *(GCVTable*)p = vtable;
 279
 280         return (GCObject*)p;
 281 }
 282
 283 static GCObject*
 284 minor_alloc_for_promotion (GCVTable vtable, GCObject *obj, size_t objsize, gboolean has_references)
 285 {
 286         /*
 287         We only need to check for a non-nursery object if we're doing a major collection.
 288         */
 289         if (!sgen_ptr_in_nursery (obj))
 290                 return major_collector.alloc_object (vtable, objsize, has_references);
 291
 292         return alloc_for_promotion (vtable, obj, objsize, has_references);
 293 }
 294
 295 static SgenFragment*
 296 build_fragments_get_exclude_head (void)
 297 {
 298         int i;
 299         for (i = 0; i < MAX_AGE; ++i) {
 300                 /*If we OOM'd on the last collection ->end might be null while ->next not.*/
 301                 if (age_alloc_buffers [i].end)
 302                         sgen_clear_range (age_alloc_buffers [i].next, age_alloc_buffers [i].end);
 303         }
 304
 305         return collector_allocator.region_head;
 306 }
 307
 308 static void
 309 build_fragments_release_exclude_head (void)
 310 {
 311         sgen_fragment_allocator_release (&collector_allocator);
 312 }
 313
 314 static void
 315 build_fragments_finish (SgenFragmentAllocator *allocator)
 316 {
 317         /* We split the fragment list based on the promotion barrier. */
 318         collector_allocator = *allocator;
 319         fragment_list_split (&collector_allocator);
 320 }
 321
 322 static void
 323 prepare_to_space (char *to_space_bitmap, size_t space_bitmap_size)
 324 {
 325         SgenFragment **previous, *frag;
 326
 327         memset (to_space_bitmap, 0, space_bitmap_size);
 328         memset (age_alloc_buffers, 0, sizeof (age_alloc_buffers));
 329
 330         previous = &collector_allocator.alloc_head;
 331
 332         for (frag = *previous; frag; frag = *previous) {
 333                 char *start = (char *)align_up (frag->fragment_next, SGEN_TO_SPACE_GRANULE_BITS);
 334                 char *end = (char *)align_down (frag->fragment_end, SGEN_TO_SPACE_GRANULE_BITS);
 335
 336                 /* Fragment is too small to be usable. */
 337                 if ((end - start) < SGEN_MAX_NURSERY_WASTE) {
 338                         sgen_clear_range (frag->fragment_next, frag->fragment_end);
 339                         frag->fragment_next = frag->fragment_end = frag->fragment_start;
 340                         *previous = frag->next;
 341                         continue;
 342                 }
 343
 344                 /*
 345                 We need to insert 3 phony objects so the fragments build step can correctly
 346                 walk the nursery.
 347                 */
 348
 349                 /* Clean the fragment range. */
 350                 sgen_clear_range (start, end);
 351                 /* We need a phony object in between the original fragment start and the effective one. */
 352                 if (start != frag->fragment_next)
 353                         sgen_clear_range (frag->fragment_next, start);
 354                 /* We need an phony object in between the new fragment end and the original fragment end. */
 355                 if (end != frag->fragment_end)
 356                         sgen_clear_range (end, frag->fragment_end);
 357
 358                 frag->fragment_start = frag->fragment_next = start;
 359                 frag->fragment_end = end;
 360                 mark_bits_in_range (to_space_bitmap, start, end);
 361                 previous = &frag->next;
 362         }
 363 }
 364
 365 static void
 366 clear_fragments (void)
 367 {
 368         sgen_clear_allocator_fragments (&collector_allocator);
 369 }
 370
 371 static void
 372 init_nursery (SgenFragmentAllocator *allocator, char *start, char *end)
 373 {
 374         int alloc_quote = (int)((end - start) * alloc_ratio);
 375         promotion_barrier = (char *)align_down (start + alloc_quote, 3);
 376         sgen_fragment_allocator_add (allocator, start, promotion_barrier);
 377         sgen_fragment_allocator_add (&collector_allocator, promotion_barrier, end);
 378
 379         region_age_size = (end - start) >> SGEN_TO_SPACE_GRANULE_BITS;
 380         region_age = (char *)g_malloc0 (region_age_size);
 381 }
 382
 383 static gboolean
 384 handle_gc_param (const char *opt)
 385 {
 386         if (g_str_has_prefix (opt, "alloc-ratio=")) {
 387                 const char *arg = strchr (opt, '=') + 1;
 388                 int percentage = atoi (arg);
 389                 if (percentage < 1 || percentage > 100) {
 390                         fprintf (stderr, "alloc-ratio must be an integer in the range 1-100.\n");
 391                         exit (1);
 392                 }
 393                 alloc_ratio = (float)percentage / 100.0f;
 394                 return TRUE;
 395         }
 396
 397         if (g_str_has_prefix (opt, "promotion-age=")) {
 398                 const char *arg = strchr (opt, '=') + 1;
 399                 promote_age = atoi (arg);
 400                 if (promote_age < 1 || promote_age >= MAX_AGE) {
 401                         fprintf (stderr, "promotion-age must be an integer in the range 1-%d.\n", MAX_AGE - 1);
 402                         exit (1);
 403                 }
 404                 return TRUE;
 405         }
 406         return FALSE;
 407 }
 408
 409 static void
 410 print_gc_param_usage (void)
 411 {
 412         fprintf (stderr,
 413                         ""
 414                         "  alloc-ratio=P (where P is a percentage, an integer in 1-100)\n"
 415                         "  promotion-age=P (where P is a number, an integer in 1-%d)\n",
 416                         MAX_AGE - 1
 417                         );
 418 }
 419
 420 /******************************************Copy/Scan functins ************************************************/
 421
 422 #define collector_pin_object(obj, queue) sgen_pin_object (obj, queue);
 423 #define COLLECTOR_SERIAL_ALLOC_FOR_PROMOTION alloc_for_promotion
 424
 425 #include "sgen-copy-object.h"
 426
 427 #define SGEN_SPLIT_NURSERY
 428
 429 #include "sgen-minor-copy-object.h"
 430 #include "sgen-minor-scan-object.h"
 431
 432 static void
 433 fill_serial_ops (SgenObjectOperations *ops)
 434 {
 435         ops->copy_or_mark_object = SERIAL_COPY_OBJECT;
 436         FILL_MINOR_COLLECTOR_SCAN_OBJECT (ops);
 437 }
 438
 439 #define SGEN_CONCURRENT_MAJOR
 440
 441 #include "sgen-minor-copy-object.h"
 442 #include "sgen-minor-scan-object.h"
 443
 444 static void
 445 fill_serial_with_concurrent_major_ops (SgenObjectOperations *ops)
 446 {
 447         ops->copy_or_mark_object = SERIAL_COPY_OBJECT;
 448         FILL_MINOR_COLLECTOR_SCAN_OBJECT (ops);
 449 }
 450
 451 void
 452 sgen_split_nursery_init (SgenMinorCollector *collector)
 453 {
 454         collector->is_split = TRUE;
 455         collector->is_parallel = FALSE;
 456
 457         collector->alloc_for_promotion = minor_alloc_for_promotion;
 458
 459         collector->prepare_to_space = prepare_to_space;
 460         collector->clear_fragments = clear_fragments;
 461         collector->build_fragments_get_exclude_head = build_fragments_get_exclude_head;
 462         collector->build_fragments_release_exclude_head = build_fragments_release_exclude_head;
 463         collector->build_fragments_finish = build_fragments_finish;
 464         collector->init_nursery = init_nursery;
 465         collector->handle_gc_param = handle_gc_param;
 466         collector->print_gc_param_usage = print_gc_param_usage;
 467
 468         fill_serial_ops (&collector->serial_ops);
 469         fill_serial_with_concurrent_major_ops (&collector->serial_ops_with_concurrent_major);
 470 }
 471
 472
 473 #endif