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