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