mono/sgen/sgen-alloc.c

   1 /*
   2  * sgen-alloc.c: Object allocation routines + managed allocators
   3  *
   4  * Author:
   5  *      Paolo Molaro (lupus@ximian.com)
   6  *  Rodrigo Kumpera (kumpera@gmail.com)
   7  *
   8  * Copyright 2005-2011 Novell, Inc (http://www.novell.com)
   9  * Copyright 2011 Xamarin Inc (http://www.xamarin.com)
  10  * Copyright 2011 Xamarin, Inc.
  11  * Copyright (C) 2012 Xamarin Inc
  12  *
  13  * Licensed under the MIT license. See LICENSE file in the project root for full license information.
  14  */
  15
  16 /*
  17  * ######################################################################
  18  * ########  Object allocation
  19  * ######################################################################
  20  * This section of code deals with allocating memory for objects.
  21  * There are several ways:
  22  * *) allocate large objects
  23  * *) allocate normal objects
  24  * *) fast lock-free allocation
  25  * *) allocation of pinned objects
  26  */
  27
  28 #include "config.h"
  29 #ifdef HAVE_SGEN_GC
  30
  31 #include <string.h>
  32
  33 #include "mono/sgen/sgen-gc.h"
  34 #include "mono/sgen/sgen-protocol.h"
  35 #include "mono/sgen/sgen-memory-governor.h"
  36 #include "mono/sgen/sgen-client.h"
  37 #include "mono/utils/mono-memory-model.h"
  38
  39 #define ALIGN_UP                SGEN_ALIGN_UP
  40 #define ALLOC_ALIGN             SGEN_ALLOC_ALIGN
  41 #define MAX_SMALL_OBJ_SIZE      SGEN_MAX_SMALL_OBJ_SIZE
  42
  43 #ifdef HEAVY_STATISTICS
  44 static guint64 stat_objects_alloced = 0;
  45 static guint64 stat_bytes_alloced = 0;
  46 static guint64 stat_bytes_alloced_los = 0;
  47
  48 #endif
  49
  50 /*
  51  * Allocation is done from a Thread Local Allocation Buffer (TLAB). TLABs are allocated
  52  * from nursery fragments.
  53  * tlab_next is the pointer to the space inside the TLAB where the next object will
  54  * be allocated.
  55  * tlab_temp_end is the pointer to the end of the temporary space reserved for
  56  * the allocation: it allows us to set the scan starts at reasonable intervals.
  57  * tlab_real_end points to the end of the TLAB.
  58  */
  59
  60 /*
  61  * FIXME: What is faster, a TLS variable pointing to a structure, or separate TLS
  62  * variables for next+temp_end ?
  63  */
  64 #ifdef HAVE_KW_THREAD
  65 static __thread char *tlab_start;
  66 static __thread char *tlab_next;
  67 static __thread char *tlab_temp_end;
  68 static __thread char *tlab_real_end;
  69 /* Used by the managed allocator/wbarrier */
  70 static __thread char **tlab_next_addr MONO_ATTR_USED;
  71 #endif
  72
  73 #ifdef HAVE_KW_THREAD
  74 #define TLAB_START      tlab_start
  75 #define TLAB_NEXT       tlab_next
  76 #define TLAB_TEMP_END   tlab_temp_end
  77 #define TLAB_REAL_END   tlab_real_end
  78 #else
  79 #define TLAB_START      (__thread_info__->tlab_start)
  80 #define TLAB_NEXT       (__thread_info__->tlab_next)
  81 #define TLAB_TEMP_END   (__thread_info__->tlab_temp_end)
  82 #define TLAB_REAL_END   (__thread_info__->tlab_real_end)
  83 #endif
  84
  85 static GCObject*
  86 alloc_degraded (GCVTable vtable, size_t size, gboolean for_mature)
  87 {
  88         GCObject *p;
  89
  90         if (!for_mature) {
  91                 sgen_client_degraded_allocation (size);
  92                 SGEN_ATOMIC_ADD_P (degraded_mode, size);
  93                 sgen_ensure_free_space (size, GENERATION_OLD);
  94         } else {
  95                 if (sgen_need_major_collection (size))
  96                         sgen_perform_collection (size, GENERATION_OLD, "mature allocation failure", !for_mature);
  97         }
  98
  99
 100         p = major_collector.alloc_degraded (vtable, size);
 101
 102         if (!for_mature)
 103                 binary_protocol_alloc_degraded (p, vtable, size, sgen_client_get_provenance ());
 104
 105         return p;
 106 }
 107
 108 static void
 109 zero_tlab_if_necessary (void *p, size_t size)
 110 {
 111         if (nursery_clear_policy == CLEAR_AT_TLAB_CREATION || nursery_clear_policy == CLEAR_AT_TLAB_CREATION_DEBUG) {
 112                 memset (p, 0, size);
 113         } else {
 114                 /*
 115                  * This function is called for all allocations in
 116                  * TLABs.  TLABs originate from fragments, which are
 117                  * initialized to be faux arrays.  The remainder of
 118                  * the fragments are zeroed out at initialization for
 119                  * CLEAR_AT_GC, so here we just need to make sure that
 120                  * the array header is zeroed.  Since we don't know
 121                  * whether we're called for the start of a fragment or
 122                  * for somewhere in between, we zero in any case, just
 123                  * to make sure.
 124                  */
 125                 sgen_client_zero_array_fill_header (p, size);
 126         }
 127 }
 128
 129 /*
 130  * Provide a variant that takes just the vtable for small fixed-size objects.
 131  * The aligned size is already computed and stored in vt->gc_descr.
 132  * Note: every SGEN_SCAN_START_SIZE or so we are given the chance to do some special
 133  * processing. We can keep track of where objects start, for example,
 134  * so when we scan the thread stacks for pinned objects, we can start
 135  * a search for the pinned object in SGEN_SCAN_START_SIZE chunks.
 136  */
 137 GCObject*
 138 sgen_alloc_obj_nolock (GCVTable vtable, size_t size)
 139 {
 140         /* FIXME: handle OOM */
 141         void **p;
 142         char *new_next;
 143         size_t real_size = size;
 144         TLAB_ACCESS_INIT;
 145
 146         CANARIFY_SIZE(size);
 147
 148         HEAVY_STAT (++stat_objects_alloced);
 149         if (real_size <= SGEN_MAX_SMALL_OBJ_SIZE)
 150                 HEAVY_STAT (stat_bytes_alloced += size);
 151         else
 152                 HEAVY_STAT (stat_bytes_alloced_los += size);
 153
 154         size = ALIGN_UP (size);
 155
 156         SGEN_ASSERT (6, sgen_vtable_get_descriptor (vtable), "VTable without descriptor");
 157
 158         if (G_UNLIKELY (has_per_allocation_action)) {
 159                 static int alloc_count;
 160                 int current_alloc = InterlockedIncrement (&alloc_count);
 161
 162                 if (collect_before_allocs) {
 163                         if (((current_alloc % collect_before_allocs) == 0) && nursery_section) {
 164                                 sgen_perform_collection (0, GENERATION_NURSERY, "collect-before-alloc-triggered", TRUE);
 165                                 if (!degraded_mode && sgen_can_alloc_size (size) && real_size <= SGEN_MAX_SMALL_OBJ_SIZE) {
 166                                         // FIXME:
 167                                         g_assert_not_reached ();
 168                                 }
 169                         }
 170                 } else if (verify_before_allocs) {
 171                         if ((current_alloc % verify_before_allocs) == 0)
 172                                 sgen_check_whole_heap_stw ();
 173                 }
 174         }
 175
 176         /*
 177          * We must already have the lock here instead of after the
 178          * fast path because we might be interrupted in the fast path
 179          * (after confirming that new_next < TLAB_TEMP_END) by the GC,
 180          * and we'll end up allocating an object in a fragment which
 181          * no longer belongs to us.
 182          *
 183          * The managed allocator does not do this, but it's treated
 184          * specially by the world-stopping code.
 185          */
 186
 187         if (real_size > SGEN_MAX_SMALL_OBJ_SIZE) {
 188                 p = (void **)sgen_los_alloc_large_inner (vtable, ALIGN_UP (real_size));
 189         } else {
 190                 /* tlab_next and tlab_temp_end are TLS vars so accessing them might be expensive */
 191
 192                 p = (void**)TLAB_NEXT;
 193                 /* FIXME: handle overflow */
 194                 new_next = (char*)p + size;
 195                 TLAB_NEXT = new_next;
 196
 197                 if (G_LIKELY (new_next < TLAB_TEMP_END)) {
 198                         /* Fast path */
 199
 200                         /*
 201                          * FIXME: We might need a memory barrier here so the change to tlab_next is
 202                          * visible before the vtable store.
 203                          */
 204
 205                         CANARIFY_ALLOC(p,real_size);
 206                         SGEN_LOG (6, "Allocated object %p, vtable: %p (%s), size: %zd", p, vtable, sgen_client_vtable_get_name (vtable), size);
 207                         binary_protocol_alloc (p , vtable, size, sgen_client_get_provenance ());
 208                         g_assert (*p == NULL);
 209                         mono_atomic_store_seq (p, vtable);
 210
 211                         return (GCObject*)p;
 212                 }
 213
 214                 /* Slow path */
 215
 216                 /* there are two cases: the object is too big or we run out of space in the TLAB */
 217                 /* we also reach here when the thread does its first allocation after a minor
 218                  * collection, since the tlab_ variables are initialized to NULL.
 219                  * there can be another case (from ORP), if we cooperate with the runtime a bit:
 220                  * objects that need finalizers can have the high bit set in their size
 221                  * so the above check fails and we can readily add the object to the queue.
 222                  * This avoids taking again the GC lock when registering, but this is moot when
 223                  * doing thread-local allocation, so it may not be a good idea.
 224                  */
 225                 if (TLAB_NEXT >= TLAB_REAL_END) {
 226                         int available_in_tlab;
 227                         /*
 228                          * Run out of space in the TLAB. When this happens, some amount of space
 229                          * remains in the TLAB, but not enough to satisfy the current allocation
 230                          * request. Currently, we retire the TLAB in all cases, later we could
 231                          * keep it if the remaining space is above a treshold, and satisfy the
 232                          * allocation directly from the nursery.
 233                          */
 234                         TLAB_NEXT -= size;
 235                         /* when running in degraded mode, we continue allocing that way
 236                          * for a while, to decrease the number of useless nursery collections.
 237                          */
 238                         if (degraded_mode && degraded_mode < DEFAULT_NURSERY_SIZE)
 239                                 return alloc_degraded (vtable, size, FALSE);
 240
 241                         available_in_tlab = (int)(TLAB_REAL_END - TLAB_NEXT);//We'll never have tlabs > 2Gb
 242                         if (size > tlab_size || available_in_tlab > SGEN_MAX_NURSERY_WASTE) {
 243                                 /* Allocate directly from the nursery */
 244                                 p = (void **)sgen_nursery_alloc (size);
 245                                 if (!p) {
 246                                         /*
 247                                          * We couldn't allocate from the nursery, so we try
 248                                          * collecting.  Even after the collection, we might
 249                                          * still not have enough memory to allocate the
 250                                          * object.  The reason will most likely be that we've
 251                                          * run out of memory, but there is the theoretical
 252                                          * possibility that other threads might have consumed
 253                                          * the freed up memory ahead of us.
 254                                          *
 255                                          * What we do in this case is allocate degraded, i.e.,
 256                                          * from the major heap.
 257                                          *
 258                                          * Ideally we'd like to detect the case of other
 259                                          * threads allocating ahead of us and loop (if we
 260                                          * always loop we will loop endlessly in the case of
 261                                          * OOM).
 262                                          */
 263                                         sgen_ensure_free_space (real_size, GENERATION_NURSERY);
 264                                         if (!degraded_mode)
 265                                                 p = (void **)sgen_nursery_alloc (size);
 266                                 }
 267                                 if (!p)
 268                                         return alloc_degraded (vtable, size, FALSE);
 269
 270                                 zero_tlab_if_necessary (p, size);
 271                         } else {
 272                                 size_t alloc_size = 0;
 273                                 if (TLAB_START)
 274                                         SGEN_LOG (3, "Retire TLAB: %p-%p [%ld]", TLAB_START, TLAB_REAL_END, (long)(TLAB_REAL_END - TLAB_NEXT - size));
 275                                 sgen_nursery_retire_region (p, available_in_tlab);
 276
 277                                 p = (void **)sgen_nursery_alloc_range (tlab_size, size, &alloc_size);
 278                                 if (!p) {
 279                                         /* See comment above in similar case. */
 280                                         sgen_ensure_free_space (tlab_size, GENERATION_NURSERY);
 281                                         if (!degraded_mode)
 282                                                 p = (void **)sgen_nursery_alloc_range (tlab_size, size, &alloc_size);
 283                                 }
 284                                 if (!p)
 285                                         return alloc_degraded (vtable, size, FALSE);
 286
 287                                 /* Allocate a new TLAB from the current nursery fragment */
 288                                 TLAB_START = (char*)p;
 289                                 TLAB_NEXT = TLAB_START;
 290                                 TLAB_REAL_END = TLAB_START + alloc_size;
 291                                 TLAB_TEMP_END = TLAB_START + MIN (SGEN_SCAN_START_SIZE, alloc_size);
 292
 293                                 zero_tlab_if_necessary (TLAB_START, alloc_size);
 294
 295                                 /* Allocate from the TLAB */
 296                                 p = (void **)TLAB_NEXT;
 297                                 TLAB_NEXT += size;
 298                                 sgen_set_nursery_scan_start ((char*)p);
 299                         }
 300                 } else {
 301                         /* Reached tlab_temp_end */
 302
 303                         /* record the scan start so we can find pinned objects more easily */
 304                         sgen_set_nursery_scan_start ((char*)p);
 305                         /* we just bump tlab_temp_end as well */
 306                         TLAB_TEMP_END = MIN (TLAB_REAL_END, TLAB_NEXT + SGEN_SCAN_START_SIZE);
 307                         SGEN_LOG (5, "Expanding local alloc: %p-%p", TLAB_NEXT, TLAB_TEMP_END);
 308                 }
 309                 CANARIFY_ALLOC(p,real_size);
 310         }
 311
 312         if (G_LIKELY (p)) {
 313                 SGEN_LOG (6, "Allocated object %p, vtable: %p (%s), size: %zd", p, vtable, sgen_client_vtable_get_name (vtable), size);
 314                 binary_protocol_alloc (p, vtable, size, sgen_client_get_provenance ());
 315                 mono_atomic_store_seq (p, vtable);
 316         }
 317
 318         return (GCObject*)p;
 319 }
 320
 321 GCObject*
 322 sgen_try_alloc_obj_nolock (GCVTable vtable, size_t size)
 323 {
 324         void **p;
 325         char *new_next;
 326         size_t real_size = size;
 327         TLAB_ACCESS_INIT;
 328
 329         CANARIFY_SIZE(size);
 330
 331         size = ALIGN_UP (size);
 332         SGEN_ASSERT (9, real_size >= SGEN_CLIENT_MINIMUM_OBJECT_SIZE, "Object too small");
 333
 334         SGEN_ASSERT (6, sgen_vtable_get_descriptor (vtable), "VTable without descriptor");
 335
 336         if (real_size > SGEN_MAX_SMALL_OBJ_SIZE)
 337                 return NULL;
 338
 339         if (G_UNLIKELY (size > tlab_size)) {
 340                 /* Allocate directly from the nursery */
 341                 p = (void **)sgen_nursery_alloc (size);
 342                 if (!p)
 343                         return NULL;
 344                 sgen_set_nursery_scan_start ((char*)p);
 345
 346                 /*FIXME we should use weak memory ops here. Should help specially on x86. */
 347                 zero_tlab_if_necessary (p, size);
 348         } else {
 349                 int available_in_tlab;
 350                 char *real_end;
 351                 /* tlab_next and tlab_temp_end are TLS vars so accessing them might be expensive */
 352
 353                 p = (void**)TLAB_NEXT;
 354                 /* FIXME: handle overflow */
 355                 new_next = (char*)p + size;
 356
 357                 real_end = TLAB_REAL_END;
 358                 available_in_tlab = (int)(real_end - (char*)p);//We'll never have tlabs > 2Gb
 359
 360                 if (G_LIKELY (new_next < real_end)) {
 361                         TLAB_NEXT = new_next;
 362
 363                         /* Second case, we overflowed temp end */
 364                         if (G_UNLIKELY (new_next >= TLAB_TEMP_END)) {
 365                                 sgen_set_nursery_scan_start (new_next);
 366                                 /* we just bump tlab_temp_end as well */
 367                                 TLAB_TEMP_END = MIN (TLAB_REAL_END, TLAB_NEXT + SGEN_SCAN_START_SIZE);
 368                                 SGEN_LOG (5, "Expanding local alloc: %p-%p", TLAB_NEXT, TLAB_TEMP_END);
 369                         }
 370                 } else if (available_in_tlab > SGEN_MAX_NURSERY_WASTE) {
 371                         /* Allocate directly from the nursery */
 372                         p = (void **)sgen_nursery_alloc (size);
 373                         if (!p)
 374                                 return NULL;
 375
 376                         zero_tlab_if_necessary (p, size);
 377                 } else {
 378                         size_t alloc_size = 0;
 379
 380                         sgen_nursery_retire_region (p, available_in_tlab);
 381                         new_next = (char *)sgen_nursery_alloc_range (tlab_size, size, &alloc_size);
 382                         p = (void**)new_next;
 383                         if (!p)
 384                                 return NULL;
 385
 386                         TLAB_START = (char*)new_next;
 387                         TLAB_NEXT = new_next + size;
 388                         TLAB_REAL_END = new_next + alloc_size;
 389                         TLAB_TEMP_END = new_next + MIN (SGEN_SCAN_START_SIZE, alloc_size);
 390                         sgen_set_nursery_scan_start ((char*)p);
 391
 392                         zero_tlab_if_necessary (new_next, alloc_size);
 393                 }
 394         }
 395
 396         HEAVY_STAT (++stat_objects_alloced);
 397         HEAVY_STAT (stat_bytes_alloced += size);
 398
 399         CANARIFY_ALLOC(p,real_size);
 400         SGEN_LOG (6, "Allocated object %p, vtable: %p (%s), size: %zd", p, vtable, sgen_client_vtable_get_name (vtable), size);
 401         binary_protocol_alloc (p, vtable, size, sgen_client_get_provenance ());
 402         g_assert (*p == NULL); /* FIXME disable this in non debug builds */
 403
 404         mono_atomic_store_seq (p, vtable);
 405
 406         return (GCObject*)p;
 407 }
 408
 409 GCObject*
 410 sgen_alloc_obj (GCVTable vtable, size_t size)
 411 {
 412         GCObject *res;
 413         TLAB_ACCESS_INIT;
 414
 415         if (!SGEN_CAN_ALIGN_UP (size))
 416                 return NULL;
 417
 418         if (G_UNLIKELY (has_per_allocation_action)) {
 419                 static int alloc_count;
 420                 int current_alloc = InterlockedIncrement (&alloc_count);
 421
 422                 if (verify_before_allocs) {
 423                         if ((current_alloc % verify_before_allocs) == 0)
 424                                 sgen_check_whole_heap_stw ();
 425                 }
 426                 if (collect_before_allocs) {
 427                         if (((current_alloc % collect_before_allocs) == 0) && nursery_section) {
 428                                 LOCK_GC;
 429                                 sgen_perform_collection (0, GENERATION_NURSERY, "collect-before-alloc-triggered", TRUE);
 430                                 UNLOCK_GC;
 431                         }
 432                 }
 433         }
 434
 435         ENTER_CRITICAL_REGION;
 436         res = sgen_try_alloc_obj_nolock (vtable, size);
 437         if (res) {
 438                 EXIT_CRITICAL_REGION;
 439                 return res;
 440         }
 441         EXIT_CRITICAL_REGION;
 442
 443         LOCK_GC;
 444         res = sgen_alloc_obj_nolock (vtable, size);
 445         UNLOCK_GC;
 446         return res;
 447 }
 448
 449 /*
 450  * To be used for interned strings and possibly MonoThread, reflection handles.
 451  * We may want to explicitly free these objects.
 452  */
 453 GCObject*
 454 sgen_alloc_obj_pinned (GCVTable vtable, size_t size)
 455 {
 456         GCObject *p;
 457
 458         if (!SGEN_CAN_ALIGN_UP (size))
 459                 return NULL;
 460         size = ALIGN_UP (size);
 461
 462         LOCK_GC;
 463
 464         if (size > SGEN_MAX_SMALL_OBJ_SIZE) {
 465                 /* large objects are always pinned anyway */
 466                 p = (GCObject *)sgen_los_alloc_large_inner (vtable, size);
 467         } else {
 468                 SGEN_ASSERT (9, sgen_client_vtable_is_inited (vtable), "class %s:%s is not initialized", sgen_client_vtable_get_namespace (vtable), sgen_client_vtable_get_name (vtable));
 469                 p = major_collector.alloc_small_pinned_obj (vtable, size, SGEN_VTABLE_HAS_REFERENCES (vtable));
 470         }
 471         if (G_LIKELY (p)) {
 472                 SGEN_LOG (6, "Allocated pinned object %p, vtable: %p (%s), size: %zd", p, vtable, sgen_client_vtable_get_name (vtable), size);
 473                 binary_protocol_alloc_pinned (p, vtable, size, sgen_client_get_provenance ());
 474         }
 475         UNLOCK_GC;
 476         return p;
 477 }
 478
 479 GCObject*
 480 sgen_alloc_obj_mature (GCVTable vtable, size_t size)
 481 {
 482         GCObject *res;
 483
 484         if (!SGEN_CAN_ALIGN_UP (size))
 485                 return NULL;
 486         size = ALIGN_UP (size);
 487
 488         LOCK_GC;
 489         res = alloc_degraded (vtable, size, TRUE);
 490         UNLOCK_GC;
 491
 492         return res;
 493 }
 494
 495 void
 496 sgen_init_tlab_info (SgenThreadInfo* info)
 497 {
 498 #ifndef HAVE_KW_THREAD
 499         SgenThreadInfo *__thread_info__ = info;
 500 #endif
 501
 502         info->tlab_start_addr = &TLAB_START;
 503         info->tlab_next_addr = &TLAB_NEXT;
 504         info->tlab_temp_end_addr = &TLAB_TEMP_END;
 505         info->tlab_real_end_addr = &TLAB_REAL_END;
 506
 507 #ifdef HAVE_KW_THREAD
 508         tlab_next_addr = &tlab_next;
 509 #endif
 510 }
 511
 512 /*
 513  * Clear the thread local TLAB variables for all threads.
 514  */
 515 void
 516 sgen_clear_tlabs (void)
 517 {
 518         FOREACH_THREAD (info) {
 519                 /* A new TLAB will be allocated when the thread does its first allocation */
 520                 *info->tlab_start_addr = NULL;
 521                 *info->tlab_next_addr = NULL;
 522                 *info->tlab_temp_end_addr = NULL;
 523                 *info->tlab_real_end_addr = NULL;
 524         } FOREACH_THREAD_END
 525 }
 526
 527 void
 528 sgen_init_allocator (void)
 529 {
 530 #if defined(HAVE_KW_THREAD) && !defined(SGEN_WITHOUT_MONO)
 531         int tlab_next_addr_offset = -1;
 532         int tlab_temp_end_offset = -1;
 533
 534
 535         MONO_THREAD_VAR_OFFSET (tlab_next_addr, tlab_next_addr_offset);
 536         MONO_THREAD_VAR_OFFSET (tlab_temp_end, tlab_temp_end_offset);
 537
 538         mono_tls_key_set_offset (TLS_KEY_SGEN_TLAB_NEXT_ADDR, tlab_next_addr_offset);
 539         mono_tls_key_set_offset (TLS_KEY_SGEN_TLAB_TEMP_END, tlab_temp_end_offset);
 540 #endif
 541
 542 #ifdef HEAVY_STATISTICS
 543         mono_counters_register ("# objects allocated", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_objects_alloced);
 544         mono_counters_register ("bytes allocated", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_bytes_alloced);
 545         mono_counters_register ("bytes allocated in LOS", MONO_COUNTER_GC | MONO_COUNTER_ULONG, &stat_bytes_alloced_los);
 546 #endif
 547 }
 548
 549 #endif /*HAVE_SGEN_GC*/