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