mono/metadata/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  * SGen is licensed under the terms of the MIT X11 license
   8  *
   9  * Copyright 2001-2003 Ximian, Inc
  10  * Copyright 2003-2010 Novell, Inc.
  11  * Copyright 2011-2012 Xamarin Inc (http://www.xamarin.com)
  12  *
  13  * Permission is hereby granted, free of charge, to any person obtaining
  14  * a copy of this software and associated documentation files (the
  15  * "Software"), to deal in the Software without restriction, including
  16  * without limitation the rights to use, copy, modify, merge, publish,
  17  * distribute, sublicense, and/or sell copies of the Software, and to
  18  * permit persons to whom the Software is furnished to do so, subject to
  19  * the following conditions:
  20  *
  21  * The above copyright notice and this permission notice shall be
  22  * included in all copies or substantial portions of the Software.
  23  *
  24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  31  */
  32
  33 #include "config.h"
  34 #ifdef HAVE_SGEN_GC
  35
  36 #include "metadata/profiler-private.h"
  37
  38 #include "metadata/sgen-gc.h"
  39 #include "metadata/sgen-protocol.h"
  40
  41 /*
  42 The nursery is logically divided into 3 spaces: Allocator space and two Survivor spaces.
  43
  44 Objects are born (allocated by the mutator) in the Allocator Space.
  45
  46 The Survivor spaces are divided in a copying collector style From and To spaces.
  47 The hole of each space switch on each collection.
  48
  49 On each collection we process objects from the nursery this way:
  50 Objects from the Allocator Space are evacuated into the To Space.
  51 Objects from the Survivor From Space are evacuated into the old generation.
  52
  53
  54 The nursery is physically divided in two parts, set by the promotion barrier.
  55
  56 The Allocator Space takes the botton part of the nursery.
  57
  58 The Survivor spaces are intermingled in the top part of the nursery. It's done
  59 this way since the required size for the To Space depends on the survivor rate
  60 of objects from the Allocator Space.
  61
  62 During a collection when the object scan function see a nursery object it must
  63 determine if the object needs to be evacuated or left in place. Originally, this
  64 check was done by checking if a forwarding pointer is installed, but now an object
  65 can be in the To Space, it won't have a forwarding pointer and it must be left in place.
  66
  67 In order to solve that we classify nursery memory been either in the From Space or in
  68 the To Space. Since the Allocator Space has the same behavior as the Survivor From Space
  69 they are unified for this purpoise - a bit confusing at first.
  70
  71 This from/to classification is done on a larger granule than object to make the check efficient
  72 and, due to that, we must make sure that all fragemnts used to allocate memory from the To Space
  73 are naturally aligned in both ends to that granule to avoid wronly classifying a From Space object.
  74
  75 TODO:
  76 -The promotion barrier is statically defined to 50% of the nursery, it should be dinamically adjusted based
  77 on survival rates;
  78 -We apply the same promotion policy to all objects, finalizable ones should age longer in the nursery;
  79 -We apply the same promotion policy to all stages of a collection, maybe we should promote more aggressively
  80 objects from non-stack roots, specially those found in the remembered set;
  81 -Fix our major collection trigger to happen before we do a minor GC and collect the nursery only once.
  82 -Make the serial fragment allocator fast path inlineable
  83 -Make aging threshold be based on survival rates and survivor occupancy;
  84 -Change promotion barrier to be size and not address based;
  85 -Pre allocate memory for young ages to make sure that on overflow only the older suffer;
  86 -Get rid of par_alloc_buffer_refill_mutex so to the parallel collection of the nursery doesn't suck;
  87 */
  88
  89 /*FIXME Move this to a separate header. */
  90 #define _toi(ptr) ((size_t)ptr)
  91 #define make_ptr_mask(bits) ((1 << bits) - 1)
  92 #define align_down(ptr, bits) ((void*)(_toi(ptr) & ~make_ptr_mask (bits)))
  93 #define align_up(ptr, bits) ((void*) ((_toi(ptr) + make_ptr_mask (bits)) & ~make_ptr_mask (bits)))
  94
  95 /*
  96 Even though the effective max age is 255, aging that much doesn't make sense.
  97 It might even make sense to use nimbles for age recording.
  98 */
  99 #define MAX_AGE 15
 100
 101 /*
 102  * Each age has its allocation buffer.  Whenever an object is to be
 103  * aged we try to fit it into its new age's allocation buffer.  If
 104  * that is not possible we get new space from the fragment allocator
 105  * and set the allocation buffer to that space (minus the space
 106  * required for the object).
 107  */
 108
 109 typedef struct {
 110         char *next;
 111         char *end;
 112 } AgeAllocationBuffer;
 113
 114 /* Limits the ammount of memory the mutator can have. */
 115 static char *promotion_barrier;
 116
 117 /*
 118 Promotion age and alloc ratio are the two nursery knobs to control
 119 how much effort we want to spend on young objects.
 120
 121 Allocation ratio should be the inverse of the expected survivor rate.
 122 The more objects surviver, the smaller the alloc ratio much be so we can
 123 age all objects.
 124
 125 Promote age depends on how much effort we want to spend aging objects before
 126 we promote them to the old generation. If addional ages don't somewhat improve
 127 mortality, it's better avoid as they increase the cost of minor collections.
 128
 129 */
 130
 131
 132 /*
 133 If we're evacuating an object with this age or more, promote it.
 134 Age is the number of surviving collections of an object.
 135 */
 136 static int promote_age = 2;
 137
 138 /*
 139 Initial ratio of allocation and survivor spaces.
 140 This should be read as the fraction of the whole nursery dedicated
 141 for the allocator space.
 142 */
 143 static float alloc_ratio = 60.f/100.f;
 144
 145
 146 static char *region_age;
 147 static int region_age_size;
 148 static AgeAllocationBuffer age_alloc_buffers [MAX_AGE];
 149
 150 /* The collector allocs from here. */
 151 static SgenFragmentAllocator collector_allocator;
 152
 153 static LOCK_DECLARE (par_alloc_buffer_refill_mutex);
 154
 155 static inline int
 156 get_object_age (char *object)
 157 {
 158         int idx = (object - sgen_nursery_start) >> SGEN_TO_SPACE_GRANULE_BITS;
 159         return region_age [idx];
 160 }
 161
 162 static inline void
 163 set_object_age (char *object, int age)
 164 {
 165         int idx = (object - sgen_nursery_start) >> SGEN_TO_SPACE_GRANULE_BITS;
 166         region_age [idx] = age;
 167 }
 168
 169 static void
 170 set_age_in_range (char *start, char *end, int age)
 171 {
 172         char *region_start;
 173         int region_idx, length;
 174         region_idx = (start - sgen_nursery_start) >> SGEN_TO_SPACE_GRANULE_BITS;
 175         region_start = &region_age [region_idx];
 176         length = (end - start) >> SGEN_TO_SPACE_GRANULE_BITS;
 177         memset (region_start, age, length);
 178 }
 179
 180 static inline void
 181 mark_bit (char *space_bitmap, char *pos)
 182 {
 183         int idx = (pos - sgen_nursery_start) >> SGEN_TO_SPACE_GRANULE_BITS;
 184         int byte = idx / 8;
 185         int bit = idx & 0x7;
 186
 187         g_assert (byte < sgen_space_bitmap_size);
 188         space_bitmap [byte] |= 1 << bit;
 189 }
 190
 191 static void
 192 mark_bits_in_range (char *space_bitmap, char *start, char *end)
 193 {
 194         start = align_down (start, SGEN_TO_SPACE_GRANULE_BITS);
 195         end = align_up (end, SGEN_TO_SPACE_GRANULE_BITS);
 196
 197         for (;start < end; start += SGEN_TO_SPACE_GRANULE_IN_BYTES)
 198                 mark_bit (space_bitmap, start);
 199 }
 200
 201 /*
 202  * This splits the fragments at the point of the promotion barrier.
 203  * Two allocator are actually involved here: The mutator allocator and
 204  * the collector allocator.  This function is called with the
 205  * collector, but it's a copy of the mutator allocator and contains
 206  * all the fragments in the nursery.  The fragments below the
 207  * promotion barrier are left with the mutator allocator and the ones
 208  * above are put into the collector allocator.
 209  */
 210 static void
 211 fragment_list_split (SgenFragmentAllocator *allocator)
 212 {
 213         SgenFragment *prev = NULL, *list = allocator->region_head;
 214
 215         while (list) {
 216                 if (list->fragment_end > promotion_barrier) {
 217                         if (list->fragment_start < promotion_barrier) {
 218                                 SgenFragment *res = sgen_fragment_allocator_alloc ();
 219
 220                                 res->fragment_start = promotion_barrier;
 221                                 res->fragment_next = promotion_barrier;
 222                                 res->fragment_end = list->fragment_end;
 223                                 res->next = list->next;
 224                                 res->next_in_order = list->next_in_order;
 225                                 g_assert (res->fragment_end > res->fragment_start);
 226
 227                                 list->fragment_end = promotion_barrier;
 228                                 list->next = list->next_in_order = NULL;
 229                                 set_age_in_range (list->fragment_start, list->fragment_end, 0);
 230
 231                                 allocator->region_head = allocator->alloc_head = res;
 232                                 return;
 233                         } else {
 234                                 if (prev)
 235                                         prev->next = prev->next_in_order = NULL;
 236                                 allocator->region_head = allocator->alloc_head = list;
 237                                 return;
 238                         }
 239                 }
 240                 set_age_in_range (list->fragment_start, list->fragment_end, 0);
 241                 prev = list;
 242                 list = list->next;
 243         }
 244         allocator->region_head = allocator->alloc_head = NULL;
 245 }
 246
 247 /******************************************Minor Collector API ************************************************/
 248
 249 #define AGE_ALLOC_BUFFER_MIN_SIZE SGEN_TO_SPACE_GRANULE_IN_BYTES
 250 #define AGE_ALLOC_BUFFER_DESIRED_SIZE (SGEN_TO_SPACE_GRANULE_IN_BYTES * 8)
 251
 252 static char*
 253 alloc_for_promotion_slow_path (int age, size_t objsize)
 254 {
 255         char *p;
 256         size_t allocated_size;
 257         size_t aligned_objsize = (size_t)align_up (objsize, SGEN_TO_SPACE_GRANULE_BITS);
 258
 259         p = sgen_fragment_allocator_serial_range_alloc (
 260                 &collector_allocator,
 261                 MAX (aligned_objsize, AGE_ALLOC_BUFFER_DESIRED_SIZE),
 262                 MAX (aligned_objsize, AGE_ALLOC_BUFFER_MIN_SIZE),
 263                 &allocated_size);
 264         if (p) {
 265                 set_age_in_range (p, p + allocated_size, age);
 266                 sgen_clear_range (age_alloc_buffers [age].next, age_alloc_buffers [age].end);
 267                 age_alloc_buffers [age].next = p + objsize;
 268                 age_alloc_buffers [age].end = p + allocated_size;
 269         }
 270         return p;
 271 }
 272
 273 static inline char*
 274 alloc_for_promotion (char *obj, size_t objsize, gboolean has_references)
 275 {
 276         char *p = NULL;
 277         int age;
 278
 279         age = get_object_age (obj);
 280         if (age >= promote_age)
 281                 return major_collector.alloc_object (objsize, has_references);
 282
 283         /* Promote! */
 284         ++age;
 285
 286         p = age_alloc_buffers [age].next;
 287         if (G_LIKELY (p + objsize <= age_alloc_buffers [age].end)) {
 288         age_alloc_buffers [age].next += objsize;
 289         } else {
 290                 p = alloc_for_promotion_slow_path (age, objsize);
 291                 if (!p)
 292                         p = major_collector.alloc_object (objsize, has_references);
 293         }
 294
 295         return p;
 296 }
 297
 298 static char*
 299 par_alloc_for_promotion_slow_path (int age, size_t objsize)
 300 {
 301         char *p;
 302         size_t allocated_size;
 303         size_t aligned_objsize = (size_t)align_up (objsize, SGEN_TO_SPACE_GRANULE_BITS);
 304
 305         mono_mutex_lock (&par_alloc_buffer_refill_mutex);
 306
 307 restart:
 308         p = age_alloc_buffers [age].next;
 309         if (G_LIKELY (p + objsize <= age_alloc_buffers [age].end)) {
 310                 if (SGEN_CAS_PTR ((void*)&age_alloc_buffers [age].next, p + objsize, p) != p)
 311                         goto restart;
 312         } else {
 313                 /*Reclaim remaining space*/
 314                 char *end = age_alloc_buffers [age].end;
 315                 do {
 316                         p = age_alloc_buffers [age].next;
 317                 } while (SGEN_CAS_PTR ((void*)&age_alloc_buffers [age].next, end, p) != p);
 318                 sgen_clear_range (p, end);
 319
 320                 /* By setting end to NULL we make sure no other thread can advance while we're updating.*/
 321                 age_alloc_buffers [age].end = NULL;
 322                 mono_memory_barrier ();
 323
 324                 p = sgen_fragment_allocator_par_range_alloc (
 325                         &collector_allocator,
 326                         MAX (aligned_objsize, AGE_ALLOC_BUFFER_DESIRED_SIZE),
 327                         MAX (aligned_objsize, AGE_ALLOC_BUFFER_MIN_SIZE),
 328                         &allocated_size);
 329                 if (p) {
 330                         set_age_in_range (p, p + allocated_size, age);
 331                         sgen_clear_range (age_alloc_buffers [age].next, age_alloc_buffers [age].end);
 332                         age_alloc_buffers [age].next = p + objsize;
 333                         age_alloc_buffers [age].end = p + allocated_size;
 334                 }
 335         }
 336
 337         mono_mutex_unlock (&par_alloc_buffer_refill_mutex);
 338         return p;
 339 }
 340
 341 static inline char*
 342 par_alloc_for_promotion (char *obj, size_t objsize, gboolean has_references)
 343 {
 344         char *p;
 345         int age;
 346
 347         age = get_object_age (obj);
 348         if (age >= promote_age)
 349                 return major_collector.par_alloc_object (objsize, has_references);
 350
 351 restart:
 352         p = age_alloc_buffers [age].next;
 353         if (G_LIKELY (p + objsize <= age_alloc_buffers [age].end)) {
 354                 if (SGEN_CAS_PTR ((void*)&age_alloc_buffers [age].next, p + objsize, p) != p)
 355                         goto restart;
 356         } else {
 357                 p = par_alloc_for_promotion_slow_path (age, objsize);
 358
 359                 /* Have we failed to promote to the nursery, lets just evacuate it to old gen. */
 360                 if (!p)
 361                         p = major_collector.par_alloc_object (objsize, has_references);
 362         }
 363
 364         return p;
 365 }
 366
 367 static char*
 368 minor_alloc_for_promotion (char *obj, size_t objsize, gboolean has_references)
 369 {
 370         /*
 371         We only need to check for a non-nursery object if we're doing a major collection.
 372         */
 373         if (!sgen_ptr_in_nursery (obj))
 374                 return major_collector.alloc_object (objsize, has_references);
 375
 376         return alloc_for_promotion (obj, objsize, has_references);
 377 }
 378
 379 static char*
 380 minor_par_alloc_for_promotion (char *obj, size_t objsize, gboolean has_references)
 381 {
 382         /*
 383         We only need to check for a non-nursery object if we're doing a major collection.
 384         */
 385         if (!sgen_ptr_in_nursery (obj))
 386                 return major_collector.par_alloc_object (objsize, has_references);
 387
 388         return par_alloc_for_promotion (obj, objsize, has_references);
 389 }
 390
 391 static SgenFragment*
 392 build_fragments_get_exclude_head (void)
 393 {
 394         int i;
 395         for (i = 0; i < MAX_AGE; ++i)
 396                 sgen_clear_range (age_alloc_buffers [i].next, age_alloc_buffers [i].end);
 397
 398         return collector_allocator.region_head;
 399 }
 400
 401 static void
 402 build_fragments_release_exclude_head (void)
 403 {
 404         sgen_fragment_allocator_release (&collector_allocator);
 405 }
 406
 407 static void
 408 build_fragments_finish (SgenFragmentAllocator *allocator)
 409 {
 410         /* We split the fragment list based on the promotion barrier. */
 411         collector_allocator = *allocator;
 412         fragment_list_split (&collector_allocator);
 413 }
 414
 415 static void
 416 prepare_to_space (char *to_space_bitmap, int space_bitmap_size)
 417 {
 418         SgenFragment **previous, *frag;
 419
 420         memset (to_space_bitmap, 0, space_bitmap_size);
 421         memset (age_alloc_buffers, 0, sizeof (age_alloc_buffers));
 422
 423         previous = &collector_allocator.alloc_head;
 424
 425         for (frag = *previous; frag; frag = *previous) {
 426                 char *start = align_up (frag->fragment_next, SGEN_TO_SPACE_GRANULE_BITS);
 427                 char *end = align_down (frag->fragment_end, SGEN_TO_SPACE_GRANULE_BITS);
 428
 429                 /* Fragment is too small to be usable. */
 430                 if ((end - start) < SGEN_MAX_NURSERY_WASTE) {
 431                         sgen_clear_range (frag->fragment_next, frag->fragment_end);
 432                         frag->fragment_next = frag->fragment_end = frag->fragment_start;
 433                         *previous = frag->next;
 434                         continue;
 435                 }
 436
 437                 /*
 438                 We need to insert 3 phony objects so the fragments build step can correctly
 439                 walk the nursery.
 440                 */
 441
 442                 /* Clean the fragment range. */
 443                 sgen_clear_range (start, end);
 444                 /* We need a phony object in between the original fragment start and the effective one. */
 445                 if (start != frag->fragment_next)
 446                         sgen_clear_range (frag->fragment_next, start);
 447                 /* We need an phony object in between the new fragment end and the original fragment end. */
 448                 if (end != frag->fragment_end)
 449                         sgen_clear_range (end, frag->fragment_end);
 450
 451                 frag->fragment_start = frag->fragment_next = start;
 452                 frag->fragment_end = end;
 453                 mark_bits_in_range (to_space_bitmap, start, end);
 454                 previous = &frag->next;
 455         }
 456 }
 457
 458 static void
 459 clear_fragments (void)
 460 {
 461         sgen_clear_allocator_fragments (&collector_allocator);
 462 }
 463
 464 static void
 465 init_nursery (SgenFragmentAllocator *allocator, char *start, char *end)
 466 {
 467         int alloc_quote = (int)((end - start) * alloc_ratio);
 468         promotion_barrier = align_down (start + alloc_quote, 3);
 469         sgen_fragment_allocator_add (allocator, start, promotion_barrier);
 470         sgen_fragment_allocator_add (&collector_allocator, promotion_barrier, end);
 471
 472         region_age_size = (end - start) >> SGEN_TO_SPACE_GRANULE_BITS;
 473         region_age = g_malloc0 (region_age_size);
 474 }
 475
 476 static gboolean
 477 handle_gc_param (const char *opt)
 478 {
 479         if (g_str_has_prefix (opt, "alloc-ratio=")) {
 480                 const char *arg = strchr (opt, '=') + 1;
 481                 int percentage = atoi (arg);
 482                 if (percentage < 1 || percentage > 100) {
 483                         fprintf (stderr, "alloc-ratio must be an integer in the range 1-100.\n");
 484                         exit (1);
 485                 }
 486                 alloc_ratio = (float)percentage / 100.0f;
 487                 return TRUE;
 488         }
 489
 490         if (g_str_has_prefix (opt, "promotion-age=")) {
 491                 const char *arg = strchr (opt, '=') + 1;
 492                 promote_age = atoi (arg);
 493                 if (promote_age < 1 || promote_age >= MAX_AGE) {
 494                         fprintf (stderr, "promotion-age must be an integer in the range 1-%d.\n", MAX_AGE - 1);
 495                         exit (1);
 496                 }
 497                 return TRUE;
 498         }
 499         return FALSE;
 500 }
 501
 502 static void
 503 print_gc_param_usage (void)
 504 {
 505         fprintf (stderr,
 506                         ""
 507                         "  alloc-ratio=P (where P is a percentage, an integer in 1-100)\n"
 508                         "  promotion-age=P (where P is a number, an integer in 1-%d)\n",
 509                         MAX_AGE - 1
 510                         );
 511 }
 512
 513 /******************************************Copy/Scan functins ************************************************/
 514
 515 #include "sgen-minor-copy-object.h"
 516 #include "sgen-minor-scan-object.h"
 517
 518
 519 void
 520 sgen_split_nursery_init (SgenMinorCollector *collector)
 521 {
 522         collector->alloc_for_promotion = minor_alloc_for_promotion;
 523         collector->par_alloc_for_promotion = minor_par_alloc_for_promotion;
 524
 525         collector->prepare_to_space = prepare_to_space;
 526         collector->clear_fragments = clear_fragments;
 527         collector->build_fragments_get_exclude_head = build_fragments_get_exclude_head;
 528         collector->build_fragments_release_exclude_head = build_fragments_release_exclude_head;
 529         collector->build_fragments_finish = build_fragments_finish;
 530         collector->init_nursery = init_nursery;
 531         collector->handle_gc_param = handle_gc_param;
 532         collector->print_gc_param_usage = print_gc_param_usage;
 533
 534         FILL_MINOR_COLLECTOR_COPY_OBJECT (collector);
 535         FILL_MINOR_COLLECTOR_SCAN_OBJECT (collector);
 536         LOCK_INIT (par_alloc_buffer_refill_mutex);
 537 }
 538
 539
 540 #endif