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