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 typedef struct {
 102         char *next;
 103         char *end;
 104 } AgeAllocationBuffer;
 105
 106 /* Limits the ammount of memory the mutator can have. */
 107 static char *promotion_barrier;
 108
 109 /*
 110 Promotion age and alloc ratio are the two nursery knobs to control
 111 how much effort we want to spend on young objects.
 112
 113 Allocation ratio should be the inverse of the expected survivor rate.
 114 The more objects surviver, the smaller the alloc ratio much be so we can
 115 age all objects.
 116
 117 Promote age depends on how much effort we want to spend aging objects before
 118 we promote them to the old generation. If addional ages don't somewhat improve
 119 mortality, it's better avoid as they increase the cost of minor collections.
 120
 121 */
 122
 123
 124 /*
 125 If we're evacuating an object with this age or more, promote it.
 126 Age is the number of surviving collections of an object.
 127 */
 128 static int promote_age = 2;
 129
 130 /*
 131 Initial ratio of allocation and survivor spaces.
 132 This should be read as the fraction of the whole nursery dedicated
 133 for the allocator space.
 134 */
 135 static float alloc_ratio = 60.f/100.f;
 136
 137
 138 static char *region_age;
 139 static int region_age_size;
 140 static AgeAllocationBuffer age_alloc_buffers [MAX_AGE];
 141
 142 /* The collector allocs from here. */
 143 static SgenFragmentAllocator collector_allocator;
 144
 145 static LOCK_DECLARE (par_alloc_buffer_refill_mutex);
 146
 147 static inline int
 148 get_object_age (char *object)
 149 {
 150         int idx = (object - sgen_nursery_start) >> SGEN_TO_SPACE_GRANULE_BITS;
 151         return region_age [idx];
 152 }
 153
 154 static inline void
 155 set_object_age (char *object, int age)
 156 {
 157         int idx = (object - sgen_nursery_start) >> SGEN_TO_SPACE_GRANULE_BITS;
 158         region_age [idx] = age;
 159 }
 160
 161 static void
 162 set_age_in_range (char *start, char *end, int age)
 163 {
 164         char *region_start;
 165         int region_idx, length;
 166         region_idx = (start - sgen_nursery_start) >> SGEN_TO_SPACE_GRANULE_BITS;
 167         region_start = &region_age [region_idx];
 168         length = (end - start) >> SGEN_TO_SPACE_GRANULE_BITS;
 169         memset (region_start, age, length);
 170 }
 171
 172 static inline void
 173 mark_bit (char *space_bitmap, char *pos)
 174 {
 175         int idx = (pos - sgen_nursery_start) >> SGEN_TO_SPACE_GRANULE_BITS;
 176         int byte = idx / 8;
 177         int bit = idx & 0x7;
 178
 179         g_assert (byte < sgen_space_bitmap_size);
 180         space_bitmap [byte] |= 1 << bit;
 181 }
 182
 183 static void
 184 mark_bits_in_range (char *space_bitmap, char *start, char *end)
 185 {
 186         start = align_down (start, SGEN_TO_SPACE_GRANULE_BITS);
 187         end = align_up (end, SGEN_TO_SPACE_GRANULE_BITS);
 188
 189         for (;start < end; start += SGEN_TO_SPACE_GRANULE_IN_BYTES)
 190                 mark_bit (space_bitmap, start);
 191 }
 192
 193 static void
 194 fragment_list_split (SgenFragmentAllocator *allocator)
 195 {
 196         SgenFragment *prev = NULL, *list = allocator->region_head;
 197
 198         while (list) {
 199                 if (list->fragment_end > promotion_barrier) {
 200                         if (list->fragment_start < promotion_barrier) {
 201                                 SgenFragment *res = sgen_fragment_allocator_alloc ();
 202
 203                                 res->fragment_start = promotion_barrier;
 204                                 res->fragment_next = promotion_barrier;
 205                                 res->fragment_end = list->fragment_end;
 206                                 res->next = list->next;
 207                                 res->next_in_order = list->next_in_order;
 208                                 g_assert (res->fragment_end > res->fragment_start);
 209
 210                                 list->fragment_end = promotion_barrier;
 211                                 list->next = list->next_in_order = NULL;
 212                                 set_age_in_range (list->fragment_start, list->fragment_end, 0);
 213
 214                                 allocator->region_head = allocator->alloc_head = res;
 215                                 return;
 216                         } else {
 217                                 if (prev)
 218                                         prev->next = prev->next_in_order = NULL;
 219                                 allocator->region_head = allocator->alloc_head = list;
 220                                 return;
 221                         }
 222                 }
 223                 set_age_in_range (list->fragment_start, list->fragment_end, 0);
 224                 prev = list;
 225                 list = list->next;
 226         }
 227         allocator->region_head = allocator->alloc_head = NULL;
 228 }
 229
 230 /******************************************Minor Collector API ************************************************/
 231
 232 #define AGE_ALLOC_BUFFER_MIN_SIZE SGEN_TO_SPACE_GRANULE_IN_BYTES
 233 #define AGE_ALLOC_BUFFER_DESIRED_SIZE (SGEN_TO_SPACE_GRANULE_IN_BYTES * 8)
 234
 235 static char*
 236 alloc_for_promotion_slow_path (int age, size_t objsize)
 237 {
 238         char *p;
 239         size_t allocated_size;
 240         size_t aligned_objsize = (size_t)align_up (objsize, SGEN_TO_SPACE_GRANULE_BITS);
 241
 242         p = sgen_fragment_allocator_serial_range_alloc (
 243                 &collector_allocator,
 244                 MAX (aligned_objsize, AGE_ALLOC_BUFFER_DESIRED_SIZE),
 245                 MAX (aligned_objsize, AGE_ALLOC_BUFFER_MIN_SIZE),
 246                 &allocated_size);
 247         if (p) {
 248                 set_age_in_range (p, p + allocated_size, age);
 249                 sgen_clear_range (age_alloc_buffers [age].next, age_alloc_buffers [age].end);
 250                 age_alloc_buffers [age].next = p + objsize;
 251                 age_alloc_buffers [age].end = p + allocated_size;
 252         }
 253         return p;
 254 }
 255
 256 static inline char*
 257 alloc_for_promotion (char *obj, size_t objsize, gboolean has_references)
 258 {
 259         char *p = NULL;
 260         int age;
 261
 262         age = get_object_age (obj);
 263         if (age >= promote_age)
 264                 return major_collector.alloc_object (objsize, has_references);
 265
 266         /* Promote! */
 267         ++age;
 268
 269         p = age_alloc_buffers [age].next;
 270         if (G_LIKELY (p + objsize <= age_alloc_buffers [age].end)) {
 271         age_alloc_buffers [age].next += objsize;
 272         } else {
 273                 p = alloc_for_promotion_slow_path (age, objsize);
 274                 if (!p)
 275                         p = major_collector.alloc_object (objsize, has_references);
 276         }
 277
 278         return p;
 279 }
 280
 281 static char*
 282 par_alloc_for_promotion_slow_path (int age, size_t objsize)
 283 {
 284         char *p;
 285         size_t allocated_size;
 286         size_t aligned_objsize = (size_t)align_up (objsize, SGEN_TO_SPACE_GRANULE_BITS);
 287
 288         mono_mutex_lock (&par_alloc_buffer_refill_mutex);
 289
 290 restart:
 291         p = age_alloc_buffers [age].next;
 292         if (G_LIKELY (p + objsize <= age_alloc_buffers [age].end)) {
 293                 if (SGEN_CAS_PTR ((void*)&age_alloc_buffers [age].next, p + objsize, p) != p)
 294                         goto restart;
 295         } else {
 296                 /*Reclaim remaining space*/
 297                 char *end = age_alloc_buffers [age].end;
 298                 do {
 299                         p = age_alloc_buffers [age].next;
 300                 } while (SGEN_CAS_PTR ((void*)&age_alloc_buffers [age].next, end, p) != p);
 301                 sgen_clear_range (p, end);
 302
 303                 /* By setting end to NULL we make sure no other thread can advance while we're updating.*/
 304                 age_alloc_buffers [age].end = NULL;
 305                 mono_memory_barrier ();
 306
 307                 p = sgen_fragment_allocator_par_range_alloc (
 308                         &collector_allocator,
 309                         MAX (aligned_objsize, AGE_ALLOC_BUFFER_DESIRED_SIZE),
 310                         MAX (aligned_objsize, AGE_ALLOC_BUFFER_MIN_SIZE),
 311                         &allocated_size);
 312                 if (p) {
 313                         set_age_in_range (p, p + allocated_size, age);
 314                         sgen_clear_range (age_alloc_buffers [age].next, age_alloc_buffers [age].end);
 315                         age_alloc_buffers [age].next = p + objsize;
 316                         age_alloc_buffers [age].end = p + allocated_size;
 317                 }
 318         }
 319
 320         mono_mutex_unlock (&par_alloc_buffer_refill_mutex);
 321         return p;
 322 }
 323
 324 static inline char*
 325 par_alloc_for_promotion (char *obj, size_t objsize, gboolean has_references)
 326 {
 327         char *p;
 328         int age;
 329
 330         age = get_object_age (obj);
 331         if (age >= promote_age)
 332                 return major_collector.par_alloc_object (objsize, has_references);
 333
 334 restart:
 335         p = age_alloc_buffers [age].next;
 336         if (G_LIKELY (p + objsize <= age_alloc_buffers [age].end)) {
 337                 if (SGEN_CAS_PTR ((void*)&age_alloc_buffers [age].next, p + objsize, p) != p)
 338                         goto restart;
 339         } else {
 340                 p = par_alloc_for_promotion_slow_path (age, objsize);
 341
 342                 /* Have we failed to promote to the nursery, lets just evacuate it to old gen. */
 343                 if (!p)
 344                         p = major_collector.par_alloc_object (objsize, has_references);
 345         }
 346
 347         return p;
 348 }
 349
 350 static char*
 351 minor_alloc_for_promotion (char *obj, size_t objsize, gboolean has_references)
 352 {
 353         /*
 354         We only need to check for a non-nursery object if we're doing a major collection.
 355         */
 356         if (!sgen_ptr_in_nursery (obj))
 357                 return major_collector.alloc_object (objsize, has_references);
 358
 359         return alloc_for_promotion (obj, objsize, has_references);
 360 }
 361
 362 static char*
 363 minor_par_alloc_for_promotion (char *obj, size_t objsize, gboolean has_references)
 364 {
 365         /*
 366         We only need to check for a non-nursery object if we're doing a major collection.
 367         */
 368         if (!sgen_ptr_in_nursery (obj))
 369                 return major_collector.par_alloc_object (objsize, has_references);
 370
 371         return par_alloc_for_promotion (obj, objsize, has_references);
 372 }
 373
 374 static SgenFragment*
 375 build_fragments_get_exclude_head (void)
 376 {
 377         int i;
 378         for (i = 0; i < MAX_AGE; ++i)
 379                 sgen_clear_range (age_alloc_buffers [i].next, age_alloc_buffers [i].end);
 380
 381         return collector_allocator.region_head;
 382 }
 383
 384 static void
 385 build_fragments_release_exclude_head (void)
 386 {
 387         sgen_fragment_allocator_release (&collector_allocator);
 388 }
 389
 390 static void
 391 build_fragments_finish (SgenFragmentAllocator *allocator)
 392 {
 393         /* We split the fragment list based on the promotion barrier. */
 394         collector_allocator = *allocator;
 395         fragment_list_split (&collector_allocator);
 396 }
 397
 398 static void
 399 prepare_to_space (char *to_space_bitmap, int space_bitmap_size)
 400 {
 401         SgenFragment **previous, *frag;
 402
 403         memset (to_space_bitmap, 0, space_bitmap_size);
 404         memset (age_alloc_buffers, 0, sizeof (age_alloc_buffers));
 405
 406         previous = &collector_allocator.alloc_head;
 407
 408         for (frag = *previous; frag; frag = *previous) {
 409                 char *start = align_up (frag->fragment_next, SGEN_TO_SPACE_GRANULE_BITS);
 410                 char *end = align_down (frag->fragment_end, SGEN_TO_SPACE_GRANULE_BITS);
 411
 412                 /* Fragment is too small to be usable. */
 413                 if ((end - start) < SGEN_MAX_NURSERY_WASTE) {
 414                         sgen_clear_range (frag->fragment_next, frag->fragment_end);
 415                         frag->fragment_next = frag->fragment_end = frag->fragment_start;
 416                         *previous = frag->next;
 417                         continue;
 418                 }
 419
 420                 /*
 421                 We need to insert 3 phony objects so the fragments build step can correctly
 422                 walk the nursery.
 423                 */
 424
 425                 /* Clean the fragment range. */
 426                 sgen_clear_range (start, end);
 427                 /* We need a phony object in between the original fragment start and the effective one. */
 428                 if (start != frag->fragment_next)
 429                         sgen_clear_range (frag->fragment_next, start);
 430                 /* We need an phony object in between the new fragment end and the original fragment end. */
 431                 if (end != frag->fragment_end)
 432                         sgen_clear_range (end, frag->fragment_end);
 433
 434                 frag->fragment_start = frag->fragment_next = start;
 435                 frag->fragment_end = end;
 436                 mark_bits_in_range (to_space_bitmap, start, end);
 437                 previous = &frag->next;
 438         }
 439 }
 440
 441 static void
 442 clear_fragments (void)
 443 {
 444         sgen_clear_allocator_fragments (&collector_allocator);
 445 }
 446
 447 static void
 448 init_nursery (SgenFragmentAllocator *allocator, char *start, char *end)
 449 {
 450         int alloc_quote = (int)((end - start) * alloc_ratio);
 451         promotion_barrier = align_down (start + alloc_quote, 3);
 452         sgen_fragment_allocator_add (allocator, start, promotion_barrier);
 453         sgen_fragment_allocator_add (&collector_allocator, promotion_barrier, end);
 454
 455         region_age_size = (end - start) >> SGEN_TO_SPACE_GRANULE_BITS;
 456         region_age = g_malloc0 (region_age_size);
 457 }
 458
 459 static gboolean
 460 handle_gc_param (const char *opt)
 461 {
 462         if (g_str_has_prefix (opt, "alloc-ratio=")) {
 463                 const char *arg = strchr (opt, '=') + 1;
 464                 int percentage = atoi (arg);
 465                 if (percentage < 1 || percentage > 100) {
 466                         fprintf (stderr, "alloc-ratio must be an integer in the range 1-100.\n");
 467                         exit (1);
 468                 }
 469                 alloc_ratio = (float)percentage / 100.0f;
 470                 return TRUE;
 471         }
 472
 473         if (g_str_has_prefix (opt, "promotion-age=")) {
 474                 const char *arg = strchr (opt, '=') + 1;
 475                 promote_age = atoi (arg);
 476                 if (promote_age < 1 || promote_age >= MAX_AGE) {
 477                         fprintf (stderr, "promotion-age must be an integer in the range 1-%d.\n", MAX_AGE - 1);
 478                         exit (1);
 479                 }
 480                 return TRUE;
 481         }
 482         return FALSE;
 483 }
 484
 485 static void
 486 print_gc_param_usage (void)
 487 {
 488         fprintf (stderr,
 489                         ""
 490                         "  alloc-ratio=P (where P is a percentage, an integer in 1-100)\n"
 491                         "  promotion-age=P (where P is a number, an integer in 1-%d)\n",
 492                         MAX_AGE - 1
 493                         );
 494 }
 495
 496 /******************************************Copy/Scan functins ************************************************/
 497
 498 #include "sgen-minor-copy-object.h"
 499 #include "sgen-minor-scan-object.h"
 500
 501
 502 void
 503 sgen_split_nursery_init (SgenMinorCollector *collector)
 504 {
 505         collector->alloc_for_promotion = minor_alloc_for_promotion;
 506         collector->par_alloc_for_promotion = minor_par_alloc_for_promotion;
 507
 508         collector->prepare_to_space = prepare_to_space;
 509         collector->clear_fragments = clear_fragments;
 510         collector->build_fragments_get_exclude_head = build_fragments_get_exclude_head;
 511         collector->build_fragments_release_exclude_head = build_fragments_release_exclude_head;
 512         collector->build_fragments_finish = build_fragments_finish;
 513         collector->init_nursery = init_nursery;
 514         collector->handle_gc_param = handle_gc_param;
 515         collector->print_gc_param_usage = print_gc_param_usage;
 516
 517         FILL_MINOR_COLLECTOR_COPY_OBJECT (collector);
 518         FILL_MINOR_COLLECTOR_SCAN_OBJECT (collector);
 519         LOCK_INIT (par_alloc_buffer_refill_mutex);
 520 }
 521
 522
 523 #endif