mono/metadata/sgen-nursery-allocator.c

   1 /*
   2  * sgen-nursery-allocator.c: Nursery allocation code.
   3  *
   4  * Copyright 2009-2010 Novell, Inc.
   5  *           2011 Rodrigo Kumpera
   6  *
   7  * Copyright 2011 Xamarin Inc  (http://www.xamarin.com)
   8  * Copyright (C) 2012 Xamarin Inc
   9  *
  10  * This library is free software; you can redistribute it and/or
  11  * modify it under the terms of the GNU Library General Public
  12  * License 2.0 as published by the Free Software Foundation;
  13  *
  14  * This library is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  17  * Library General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU Library General Public
  20  * License 2.0 along with this library; if not, write to the Free
  21  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  22  */
  23
  24 /*
  25  * The young generation is divided into fragments. This is because
  26  * we can hand one fragments to a thread for lock-less fast alloc and
  27  * because the young generation ends up fragmented anyway by pinned objects.
  28  * Once a collection is done, a list of fragments is created. When doing
  29  * thread local alloc we use smallish nurseries so we allow new threads to
  30  * allocate memory from gen0 without triggering a collection. Threads that
  31  * are found to allocate lots of memory are given bigger fragments. This
  32  * should make the finalizer thread use little nursery memory after a while.
  33  * We should start assigning threads very small fragments: if there are many
  34  * threads the nursery will be full of reserved space that the threads may not
  35  * use at all, slowing down allocation speed.
  36  * Thread local allocation is done from areas of memory Hotspot calls Thread Local
  37  * Allocation Buffers (TLABs).
  38  */
  39 #include "config.h"
  40 #ifdef HAVE_SGEN_GC
  41
  42 #ifdef HAVE_UNISTD_H
  43 #include <unistd.h>
  44 #endif
  45 #ifdef HAVE_PTHREAD_H
  46 #include <pthread.h>
  47 #endif
  48 #ifdef HAVE_SEMAPHORE_H
  49 #include <semaphore.h>
  50 #endif
  51 #include <stdio.h>
  52 #include <string.h>
  53 #include <errno.h>
  54 #include <assert.h>
  55 #ifdef __MACH__
  56 #undef _XOPEN_SOURCE
  57 #endif
  58 #ifdef __MACH__
  59 #define _XOPEN_SOURCE
  60 #endif
  61
  62 #include "metadata/sgen-gc.h"
  63 #include "metadata/metadata-internals.h"
  64 #include "metadata/class-internals.h"
  65 #include "metadata/gc-internal.h"
  66 #include "metadata/object-internals.h"
  67 #include "metadata/threads.h"
  68 #include "metadata/sgen-cardtable.h"
  69 #include "metadata/sgen-protocol.h"
  70 #include "metadata/sgen-archdep.h"
  71 #include "metadata/sgen-bridge.h"
  72 #include "metadata/sgen-memory-governor.h"
  73 #include "metadata/sgen-pinning.h"
  74 #include "metadata/mono-gc.h"
  75 #include "metadata/method-builder.h"
  76 #include "metadata/profiler-private.h"
  77 #include "metadata/monitor.h"
  78 #include "metadata/threadpool-internals.h"
  79 #include "metadata/mempool-internals.h"
  80 #include "metadata/marshal.h"
  81 #include "utils/mono-mmap.h"
  82 #include "utils/mono-time.h"
  83 #include "utils/mono-semaphore.h"
  84 #include "utils/mono-counters.h"
  85 #include "utils/mono-proclib.h"
  86 #include "utils/mono-threads.h"
  87
  88 /* Enable it so nursery allocation diagnostic data is collected */
  89 //#define NALLOC_DEBUG 1
  90
  91 /* The mutator allocs from here. */
  92 SgenFragmentAllocator mutator_allocator;
  93
  94 /* freeelist of fragment structures */
  95 static SgenFragment *fragment_freelist = NULL;
  96
  97 /* Allocator cursors */
  98 static char *nursery_last_pinned_end = NULL;
  99
 100 char *sgen_nursery_start;
 101 char *sgen_nursery_end;
 102
 103 #ifdef USER_CONFIG
 104 size_t sgen_nursery_size = (1 << 22);
 105 #ifdef SGEN_ALIGN_NURSERY
 106 int sgen_nursery_bits = 22;
 107 #endif
 108 #endif
 109
 110 char *sgen_space_bitmap;
 111 size_t sgen_space_bitmap_size;
 112
 113 #ifdef HEAVY_STATISTICS
 114
 115 static gint32 stat_wasted_bytes_trailer = 0;
 116 static gint32 stat_wasted_bytes_small_areas = 0;
 117 static gint32 stat_wasted_bytes_discarded_fragments = 0;
 118 static gint32 stat_nursery_alloc_requests = 0;
 119 static gint32 stat_alloc_iterations = 0;
 120 static gint32 stat_alloc_retries = 0;
 121
 122 static gint32 stat_nursery_alloc_range_requests = 0;
 123 static gint32 stat_alloc_range_iterations = 0;
 124 static gint32 stat_alloc_range_retries = 0;
 125
 126 #endif
 127
 128 /************************************Nursery allocation debugging *********************************************/
 129
 130 #ifdef NALLOC_DEBUG
 131
 132 enum {
 133         FIXED_ALLOC = 1,
 134         RANGE_ALLOC,
 135         PINNING,
 136         BLOCK_ZEROING,
 137         CLEAR_NURSERY_FRAGS
 138 };
 139
 140 typedef struct {
 141         char *address;
 142         size_t size;
 143         int reason;
 144         int seq;
 145         MonoNativeThreadId tid;
 146 } AllocRecord;
 147
 148 #define ALLOC_RECORD_COUNT 128000
 149
 150
 151 static AllocRecord *alloc_records;
 152 static volatile int next_record;
 153 static volatile int alloc_count;
 154
 155 void dump_alloc_records (void);
 156 void verify_alloc_records (void);
 157
 158 static const char*
 159 get_reason_name (AllocRecord *rec)
 160 {
 161         switch (rec->reason) {
 162         case FIXED_ALLOC: return "fixed-alloc";
 163         case RANGE_ALLOC: return "range-alloc";
 164         case PINNING: return "pinning";
 165         case BLOCK_ZEROING: return "block-zeroing";
 166         case CLEAR_NURSERY_FRAGS: return "clear-nursery-frag";
 167         default: return "invalid";
 168         }
 169 }
 170
 171 static void
 172 reset_alloc_records (void)
 173 {
 174         next_record = 0;
 175         alloc_count = 0;
 176 }
 177
 178 static void
 179 add_alloc_record (char *addr, size_t size, int reason)
 180 {
 181         int idx = InterlockedIncrement (&next_record) - 1;
 182         alloc_records [idx].address = addr;
 183         alloc_records [idx].size = size;
 184         alloc_records [idx].reason = reason;
 185         alloc_records [idx].seq = idx;
 186         alloc_records [idx].tid = mono_native_thread_id_get ();
 187 }
 188
 189 static int
 190 comp_alloc_record (const void *_a, const void *_b)
 191 {
 192         const AllocRecord *a = _a;
 193         const AllocRecord *b = _b;
 194         if (a->address == b->address)
 195                 return a->seq - b->seq;
 196         return a->address - b->address;
 197 }
 198
 199 #define rec_end(REC) ((REC)->address + (REC)->size)
 200
 201 void
 202 dump_alloc_records (void)
 203 {
 204         int i;
 205         sgen_qsort (alloc_records, next_record, sizeof (AllocRecord), comp_alloc_record);
 206
 207         printf ("------------------------------------DUMP RECORDS----------------------------\n");
 208         for (i = 0; i < next_record; ++i) {
 209                 AllocRecord *rec = alloc_records + i;
 210                 printf ("obj [%p, %p] size %d reason %s seq %d tid %x\n", rec->address, rec_end (rec), (int)rec->size, get_reason_name (rec), rec->seq, (size_t)rec->tid);
 211         }
 212 }
 213
 214 void
 215 verify_alloc_records (void)
 216 {
 217         int i;
 218         int total = 0;
 219         int holes = 0;
 220         int max_hole = 0;
 221         AllocRecord *prev = NULL;
 222
 223         sgen_qsort (alloc_records, next_record, sizeof (AllocRecord), comp_alloc_record);
 224         printf ("------------------------------------DUMP RECORDS- %d %d---------------------------\n", next_record, alloc_count);
 225         for (i = 0; i < next_record; ++i) {
 226                 AllocRecord *rec = alloc_records + i;
 227                 int hole_size = 0;
 228                 total += rec->size;
 229                 if (prev) {
 230                         if (rec_end (prev) > rec->address)
 231                                 printf ("WE GOT OVERLAPPING objects %p and %p\n", prev->address, rec->address);
 232                         if ((rec->address - rec_end (prev)) >= 8)
 233                                 ++holes;
 234                         hole_size = rec->address - rec_end (prev);
 235                         max_hole = MAX (max_hole, hole_size);
 236                 }
 237                 printf ("obj [%p, %p] size %d hole to prev %d reason %s seq %d tid %zx\n", rec->address, rec_end (rec), (int)rec->size, hole_size, get_reason_name (rec), rec->seq, (size_t)rec->tid);
 238                 prev = rec;
 239         }
 240         printf ("SUMMARY total alloc'd %d holes %d max_hole %d\n", total, holes, max_hole);
 241 }
 242
 243 #endif
 244
 245 /*********************************************************************************/
 246
 247
 248 static inline gpointer
 249 mask (gpointer n, uintptr_t bit)
 250 {
 251         return (gpointer)(((uintptr_t)n) | bit);
 252 }
 253
 254 static inline gpointer
 255 unmask (gpointer p)
 256 {
 257         return (gpointer)((uintptr_t)p & ~(uintptr_t)0x3);
 258 }
 259
 260 static inline uintptr_t
 261 get_mark (gpointer n)
 262 {
 263         return (uintptr_t)n & 0x1;
 264 }
 265
 266 /*MUST be called with world stopped*/
 267 SgenFragment*
 268 sgen_fragment_allocator_alloc (void)
 269 {
 270         SgenFragment *frag = fragment_freelist;
 271         if (frag) {
 272                 fragment_freelist = frag->next_in_order;
 273                 frag->next = frag->next_in_order = NULL;
 274                 return frag;
 275         }
 276         frag = sgen_alloc_internal (INTERNAL_MEM_FRAGMENT);
 277         frag->next = frag->next_in_order = NULL;
 278         return frag;
 279 }
 280
 281 void
 282 sgen_fragment_allocator_add (SgenFragmentAllocator *allocator, char *start, char *end)
 283 {
 284         SgenFragment *fragment;
 285
 286         fragment = sgen_fragment_allocator_alloc ();
 287         fragment->fragment_start = start;
 288         fragment->fragment_next = start;
 289         fragment->fragment_end = end;
 290         fragment->next_in_order = fragment->next = unmask (allocator->region_head);
 291
 292         allocator->region_head = allocator->alloc_head = fragment;
 293         g_assert (fragment->fragment_end > fragment->fragment_start);
 294 }
 295
 296 void
 297 sgen_fragment_allocator_release (SgenFragmentAllocator *allocator)
 298 {
 299         SgenFragment *last = allocator->region_head;
 300         if (!last)
 301                 return;
 302
 303         /* Find the last fragment in insert order */
 304         for (; last->next_in_order; last = last->next_in_order) ;
 305
 306         last->next_in_order = fragment_freelist;
 307         fragment_freelist = allocator->region_head;
 308         allocator->alloc_head = allocator->region_head = NULL;
 309 }
 310
 311 static SgenFragment**
 312 find_previous_pointer_fragment (SgenFragmentAllocator *allocator, SgenFragment *frag)
 313 {
 314         SgenFragment **prev;
 315         SgenFragment *cur, *next;
 316 #ifdef NALLOC_DEBUG
 317         int count = 0;
 318 #endif
 319
 320 try_again:
 321         prev = &allocator->alloc_head;
 322 #ifdef NALLOC_DEBUG
 323         if (count++ > 5)
 324                 printf ("retry count for fppf is %d\n", count);
 325 #endif
 326
 327         cur = unmask (*prev);
 328
 329         while (1) {
 330                 if (cur == NULL)
 331                         return NULL;
 332                 next = cur->next;
 333
 334                 /*
 335                  * We need to make sure that we dereference prev below
 336                  * after reading cur->next above, so we need a read
 337                  * barrier.
 338                  */
 339                 mono_memory_read_barrier ();
 340
 341                 if (*prev != cur)
 342                         goto try_again;
 343
 344                 if (!get_mark (next)) {
 345                         if (cur == frag)
 346                                 return prev;
 347                         prev = &cur->next;
 348                 } else {
 349                         next = unmask (next);
 350                         if (InterlockedCompareExchangePointer ((volatile gpointer*)prev, next, cur) != cur)
 351                                 goto try_again;
 352                         /*we must make sure that the next from cur->next happens after*/
 353                         mono_memory_write_barrier ();
 354                 }
 355
 356                 cur = mono_lls_pointer_unmask (next);
 357         }
 358         return NULL;
 359 }
 360
 361 static gboolean
 362 claim_remaining_size (SgenFragment *frag, char *alloc_end)
 363 {
 364         /* All space used, nothing to claim. */
 365         if (frag->fragment_end <= alloc_end)
 366                 return FALSE;
 367
 368         /* Try to alloc all the remaining space. */
 369         return InterlockedCompareExchangePointer ((volatile gpointer*)&frag->fragment_next, frag->fragment_end, alloc_end) == alloc_end;
 370 }
 371
 372 static void*
 373 par_alloc_from_fragment (SgenFragmentAllocator *allocator, SgenFragment *frag, size_t size)
 374 {
 375         char *p = frag->fragment_next;
 376         char *end = p + size;
 377
 378         if (end > frag->fragment_end)
 379                 return NULL;
 380
 381         /* p = frag->fragment_next must happen before */
 382         mono_memory_barrier ();
 383
 384         if (InterlockedCompareExchangePointer ((volatile gpointer*)&frag->fragment_next, end, p) != p)
 385                 return NULL;
 386
 387         if (frag->fragment_end - end < SGEN_MAX_NURSERY_WASTE) {
 388                 SgenFragment *next, **prev_ptr;
 389
 390                 /*
 391                  * Before we clean the remaining nursery, we must claim the remaining space
 392                  * as it could end up been used by the range allocator since it can end up
 393                  * allocating from this dying fragment as it doesn't respect SGEN_MAX_NURSERY_WASTE
 394                  * when doing second chance allocation.
 395                  */
 396                 if ((sgen_get_nursery_clear_policy () == CLEAR_AT_TLAB_CREATION || sgen_get_nursery_clear_policy () == CLEAR_AT_TLAB_CREATION_DEBUG) && claim_remaining_size (frag, end)) {
 397                         sgen_clear_range (end, frag->fragment_end);
 398                         HEAVY_STAT (InterlockedExchangeAdd (&stat_wasted_bytes_trailer, frag->fragment_end - end));
 399 #ifdef NALLOC_DEBUG
 400                         add_alloc_record (end, frag->fragment_end - end, BLOCK_ZEROING);
 401 #endif
 402                 }
 403
 404                 prev_ptr = find_previous_pointer_fragment (allocator, frag);
 405
 406                 /*Use Michaels linked list remove*/
 407
 408                 /*prev_ptr will be null if the fragment was removed concurrently */
 409                 while (prev_ptr) {
 410                         next = frag->next;
 411
 412                         /*already deleted*/
 413                         if (!get_mark (next)) {
 414                                 /*frag->next read must happen before the first CAS*/
 415                                 mono_memory_write_barrier ();
 416
 417                                 /*Fail if the next node is removed concurrently and its CAS wins */
 418                                 if (InterlockedCompareExchangePointer ((volatile gpointer*)&frag->next, mask (next, 1), next) != next) {
 419                                         continue;
 420                                 }
 421                         }
 422
 423                         /* The second CAS must happen after the first CAS or frag->next. */
 424                         mono_memory_write_barrier ();
 425
 426                         /* Fail if the previous node was deleted and its CAS wins */
 427                         if (InterlockedCompareExchangePointer ((volatile gpointer*)prev_ptr, unmask (next), frag) != frag) {
 428                                 prev_ptr = find_previous_pointer_fragment (allocator, frag);
 429                                 continue;
 430                         }
 431                         break;
 432                 }
 433         }
 434
 435         return p;
 436 }
 437
 438 static void*
 439 serial_alloc_from_fragment (SgenFragment **previous, SgenFragment *frag, size_t size)
 440 {
 441         char *p = frag->fragment_next;
 442         char *end = p + size;
 443
 444         if (end > frag->fragment_end)
 445                 return NULL;
 446
 447         frag->fragment_next = end;
 448
 449         if (frag->fragment_end - end < SGEN_MAX_NURSERY_WASTE) {
 450                 *previous = frag->next;
 451
 452                 /* Clear the remaining space, pinning depends on this. FIXME move this to use phony arrays */
 453                 memset (end, 0, frag->fragment_end - end);
 454
 455                 *previous = frag->next;
 456         }
 457
 458         return p;
 459 }
 460
 461 void*
 462 sgen_fragment_allocator_par_alloc (SgenFragmentAllocator *allocator, size_t size)
 463 {
 464         SgenFragment *frag;
 465
 466 #ifdef NALLOC_DEBUG
 467         InterlockedIncrement (&alloc_count);
 468 #endif
 469
 470 restart:
 471         for (frag = unmask (allocator->alloc_head); unmask (frag); frag = unmask (frag->next)) {
 472                 HEAVY_STAT (InterlockedIncrement (&stat_alloc_iterations));
 473
 474                 if (size <= (size_t)(frag->fragment_end - frag->fragment_next)) {
 475                         void *p = par_alloc_from_fragment (allocator, frag, size);
 476                         if (!p) {
 477                                 HEAVY_STAT (InterlockedIncrement (&stat_alloc_retries));
 478                                 goto restart;
 479                         }
 480 #ifdef NALLOC_DEBUG
 481                         add_alloc_record (p, size, FIXED_ALLOC);
 482 #endif
 483                         return p;
 484                 }
 485         }
 486         return NULL;
 487 }
 488
 489 void*
 490 sgen_fragment_allocator_serial_alloc (SgenFragmentAllocator *allocator, size_t size)
 491 {
 492         SgenFragment *frag;
 493         SgenFragment **previous;
 494 #ifdef NALLOC_DEBUG
 495         InterlockedIncrement (&alloc_count);
 496 #endif
 497
 498         previous = &allocator->alloc_head;
 499
 500         for (frag = *previous; frag; frag = *previous) {
 501                 char *p = serial_alloc_from_fragment (previous, frag, size);
 502
 503                 HEAVY_STAT (InterlockedIncrement (&stat_alloc_iterations));
 504
 505                 if (p) {
 506 #ifdef NALLOC_DEBUG
 507                         add_alloc_record (p, size, FIXED_ALLOC);
 508 #endif
 509                         return p;
 510                 }
 511                 previous = &frag->next;
 512         }
 513         return NULL;
 514 }
 515
 516 void*
 517 sgen_fragment_allocator_serial_range_alloc (SgenFragmentAllocator *allocator, size_t desired_size, size_t minimum_size, size_t *out_alloc_size)
 518 {
 519         SgenFragment *frag, **previous, *min_frag = NULL, **prev_min_frag = NULL;
 520         size_t current_minimum = minimum_size;
 521
 522 #ifdef NALLOC_DEBUG
 523         InterlockedIncrement (&alloc_count);
 524 #endif
 525
 526         previous = &allocator->alloc_head;
 527
 528         for (frag = *previous; frag; frag = *previous) {
 529                 size_t frag_size = frag->fragment_end - frag->fragment_next;
 530
 531                 HEAVY_STAT (InterlockedIncrement (&stat_alloc_range_iterations));
 532
 533                 if (desired_size <= frag_size) {
 534                         void *p;
 535                         *out_alloc_size = desired_size;
 536
 537                         p = serial_alloc_from_fragment (previous, frag, desired_size);
 538 #ifdef NALLOC_DEBUG
 539                         add_alloc_record (p, desired_size, RANGE_ALLOC);
 540 #endif
 541                         return p;
 542                 }
 543                 if (current_minimum <= frag_size) {
 544                         min_frag = frag;
 545                         prev_min_frag = previous;
 546                         current_minimum = frag_size;
 547                 }
 548                 previous = &frag->next;
 549         }
 550
 551         if (min_frag) {
 552                 void *p;
 553                 size_t frag_size = min_frag->fragment_end - min_frag->fragment_next;
 554                 *out_alloc_size = frag_size;
 555
 556                 p = serial_alloc_from_fragment (prev_min_frag, min_frag, frag_size);
 557
 558 #ifdef NALLOC_DEBUG
 559                 add_alloc_record (p, frag_size, RANGE_ALLOC);
 560 #endif
 561                 return p;
 562         }
 563
 564         return NULL;
 565 }
 566
 567 void*
 568 sgen_fragment_allocator_par_range_alloc (SgenFragmentAllocator *allocator, size_t desired_size, size_t minimum_size, size_t *out_alloc_size)
 569 {
 570         SgenFragment *frag, *min_frag;
 571         size_t current_minimum;
 572
 573 restart:
 574         min_frag = NULL;
 575         current_minimum = minimum_size;
 576
 577 #ifdef NALLOC_DEBUG
 578         InterlockedIncrement (&alloc_count);
 579 #endif
 580
 581         for (frag = unmask (allocator->alloc_head); frag; frag = unmask (frag->next)) {
 582                 size_t frag_size = frag->fragment_end - frag->fragment_next;
 583
 584                 HEAVY_STAT (InterlockedIncrement (&stat_alloc_range_iterations));
 585
 586                 if (desired_size <= frag_size) {
 587                         void *p;
 588                         *out_alloc_size = desired_size;
 589
 590                         p = par_alloc_from_fragment (allocator, frag, desired_size);
 591                         if (!p) {
 592                                 HEAVY_STAT (InterlockedIncrement (&stat_alloc_range_retries));
 593                                 goto restart;
 594                         }
 595 #ifdef NALLOC_DEBUG
 596                         add_alloc_record (p, desired_size, RANGE_ALLOC);
 597 #endif
 598                         return p;
 599                 }
 600                 if (current_minimum <= frag_size) {
 601                         min_frag = frag;
 602                         current_minimum = frag_size;
 603                 }
 604         }
 605
 606         /* The second fragment_next read should be ordered in respect to the first code block */
 607         mono_memory_barrier ();
 608
 609         if (min_frag) {
 610                 void *p;
 611                 size_t frag_size;
 612
 613                 frag_size = min_frag->fragment_end - min_frag->fragment_next;
 614                 if (frag_size < minimum_size)
 615                         goto restart;
 616
 617                 *out_alloc_size = frag_size;
 618
 619                 mono_memory_barrier ();
 620                 p = par_alloc_from_fragment (allocator, min_frag, frag_size);
 621
 622                 /*XXX restarting here is quite dubious given this is already second chance allocation. */
 623                 if (!p) {
 624                         HEAVY_STAT (InterlockedIncrement (&stat_alloc_retries));
 625                         goto restart;
 626                 }
 627 #ifdef NALLOC_DEBUG
 628                 add_alloc_record (p, frag_size, RANGE_ALLOC);
 629 #endif
 630                 return p;
 631         }
 632
 633         return NULL;
 634 }
 635
 636 void
 637 sgen_clear_allocator_fragments (SgenFragmentAllocator *allocator)
 638 {
 639         SgenFragment *frag;
 640
 641         for (frag = unmask (allocator->alloc_head); frag; frag = unmask (frag->next)) {
 642                 SGEN_LOG (4, "Clear nursery frag %p-%p", frag->fragment_next, frag->fragment_end);
 643                 sgen_clear_range (frag->fragment_next, frag->fragment_end);
 644 #ifdef NALLOC_DEBUG
 645                 add_alloc_record (frag->fragment_next, frag->fragment_end - frag->fragment_next, CLEAR_NURSERY_FRAGS);
 646 #endif
 647         }
 648 }
 649
 650 /* Clear all remaining nursery fragments */
 651 void
 652 sgen_clear_nursery_fragments (void)
 653 {
 654         if (sgen_get_nursery_clear_policy () == CLEAR_AT_TLAB_CREATION || sgen_get_nursery_clear_policy () == CLEAR_AT_TLAB_CREATION_DEBUG) {
 655                 sgen_clear_allocator_fragments (&mutator_allocator);
 656                 sgen_minor_collector.clear_fragments ();
 657         }
 658 }
 659
 660 /*
 661  * Mark a given range of memory as invalid.
 662  *
 663  * This can be done either by zeroing memory or by placing
 664  * a phony byte[] array. This keeps the heap forward walkable.
 665  *
 666  * This function ignores calls with a zero range, even if
 667  * both start and end are NULL.
 668  */
 669 void
 670 sgen_clear_range (char *start, char *end)
 671 {
 672         MonoArray *o;
 673         size_t size = end - start;
 674
 675         if ((start && !end) || (start > end))
 676                 g_error ("Invalid range [%p %p]", start, end);
 677
 678         if (size < sizeof (MonoArray)) {
 679                 memset (start, 0, size);
 680                 return;
 681         }
 682
 683         o = (MonoArray*)start;
 684         o->obj.vtable = sgen_get_array_fill_vtable ();
 685         /* Mark this as not a real object */
 686         o->obj.synchronisation = GINT_TO_POINTER (-1);
 687         o->bounds = NULL;
 688         o->max_length = (mono_array_size_t)(size - sizeof (MonoArray));
 689         sgen_set_nursery_scan_start (start);
 690         g_assert (start + sgen_safe_object_get_size ((MonoObject*)o) == end);
 691 }
 692
 693 void
 694 sgen_nursery_allocator_prepare_for_pinning (void)
 695 {
 696         sgen_clear_allocator_fragments (&mutator_allocator);
 697         sgen_minor_collector.clear_fragments ();
 698 }
 699
 700 static mword fragment_total = 0;
 701 /*
 702  * We found a fragment of free memory in the nursery: memzero it and if
 703  * it is big enough, add it to the list of fragments that can be used for
 704  * allocation.
 705  */
 706 static void
 707 add_nursery_frag (SgenFragmentAllocator *allocator, size_t frag_size, char* frag_start, char* frag_end)
 708 {
 709         SGEN_LOG (4, "Found empty fragment: %p-%p, size: %zd", frag_start, frag_end, frag_size);
 710         binary_protocol_empty (frag_start, frag_size);
 711         MONO_GC_NURSERY_SWEPT ((mword)frag_start, frag_end - frag_start);
 712         /* Not worth dealing with smaller fragments: need to tune */
 713         if (frag_size >= SGEN_MAX_NURSERY_WASTE) {
 714                 /* memsetting just the first chunk start is bound to provide better cache locality */
 715                 if (sgen_get_nursery_clear_policy () == CLEAR_AT_GC)
 716                         memset (frag_start, 0, frag_size);
 717                 else if (sgen_get_nursery_clear_policy () == CLEAR_AT_TLAB_CREATION_DEBUG)
 718                         memset (frag_start, 0xff, frag_size);
 719
 720 #ifdef NALLOC_DEBUG
 721                 /* XXX convert this into a flight record entry
 722                 printf ("\tfragment [%p %p] size %zd\n", frag_start, frag_end, frag_size);
 723                 */
 724 #endif
 725                 sgen_fragment_allocator_add (allocator, frag_start, frag_end);
 726                 fragment_total += frag_size;
 727         } else {
 728                 /* Clear unused fragments, pinning depends on this */
 729                 sgen_clear_range (frag_start, frag_end);
 730                 HEAVY_STAT (InterlockedExchangeAdd (&stat_wasted_bytes_small_areas, frag_size));
 731         }
 732 }
 733
 734 static void
 735 fragment_list_reverse (SgenFragmentAllocator *allocator)
 736 {
 737         SgenFragment *prev = NULL, *list = allocator->region_head;
 738         while (list) {
 739                 SgenFragment *next = list->next;
 740                 list->next = prev;
 741                 list->next_in_order = prev;
 742                 prev = list;
 743                 list = next;
 744         }
 745
 746         allocator->region_head = allocator->alloc_head = prev;
 747 }
 748
 749 mword
 750 sgen_build_nursery_fragments (GCMemSection *nursery_section, SgenGrayQueue *unpin_queue)
 751 {
 752         char *frag_start, *frag_end;
 753         size_t frag_size;
 754         SgenFragment *frags_ranges;
 755         void **pin_start, **pin_entry, **pin_end;
 756
 757 #ifdef NALLOC_DEBUG
 758         reset_alloc_records ();
 759 #endif
 760         /*The mutator fragments are done. We no longer need them. */
 761         sgen_fragment_allocator_release (&mutator_allocator);
 762
 763         frag_start = sgen_nursery_start;
 764         fragment_total = 0;
 765
 766         /* The current nursery might give us a fragment list to exclude [start, next[*/
 767         frags_ranges = sgen_minor_collector.build_fragments_get_exclude_head ();
 768
 769         /* clear scan starts */
 770         memset (nursery_section->scan_starts, 0, nursery_section->num_scan_start * sizeof (gpointer));
 771
 772         pin_start = pin_entry = sgen_pinning_get_entry (nursery_section->pin_queue_first_entry);
 773         pin_end = sgen_pinning_get_entry (nursery_section->pin_queue_last_entry);
 774
 775         while (pin_entry < pin_end || frags_ranges) {
 776                 char *addr0, *addr1;
 777                 size_t size;
 778
 779                 addr0 = addr1 = sgen_nursery_end;
 780                 if (pin_entry < pin_end)
 781                         addr0 = *pin_entry;
 782                 if (frags_ranges)
 783                         addr1 = frags_ranges->fragment_start;
 784
 785                 if (addr0 < addr1) {
 786                         if (unpin_queue)
 787                                 GRAY_OBJECT_ENQUEUE (unpin_queue, addr0, sgen_obj_get_descriptor_safe (addr0));
 788                         else
 789                                 SGEN_UNPIN_OBJECT (addr0);
 790                         size = SGEN_ALIGN_UP (sgen_safe_object_get_size ((MonoObject*)addr0));
 791                         CANARIFY_SIZE (size);
 792                         sgen_set_nursery_scan_start (addr0);
 793                         frag_end = addr0;
 794                         ++pin_entry;
 795                 } else {
 796                         frag_end = addr1;
 797                         size = frags_ranges->fragment_next - addr1;
 798                         frags_ranges = frags_ranges->next_in_order;
 799                 }
 800
 801                 frag_size = frag_end - frag_start;
 802
 803                 if (size == 0)
 804                         continue;
 805
 806                 g_assert (frag_size >= 0);
 807                 g_assert (size > 0);
 808                 if (frag_size && size)
 809                         add_nursery_frag (&mutator_allocator, frag_size, frag_start, frag_end);
 810
 811                 frag_size = size;
 812 #ifdef NALLOC_DEBUG
 813                 add_alloc_record (*pin_entry, frag_size, PINNING);
 814 #endif
 815                 frag_start = frag_end + frag_size;
 816         }
 817
 818         nursery_last_pinned_end = frag_start;
 819         frag_end = sgen_nursery_end;
 820         frag_size = frag_end - frag_start;
 821         if (frag_size)
 822                 add_nursery_frag (&mutator_allocator, frag_size, frag_start, frag_end);
 823
 824         /* Now it's safe to release the fragments exclude list. */
 825         sgen_minor_collector.build_fragments_release_exclude_head ();
 826
 827         /* First we reorder the fragment list to be in ascending address order. This makes H/W prefetchers happier. */
 828         fragment_list_reverse (&mutator_allocator);
 829
 830         /*The collector might want to do something with the final nursery fragment list.*/
 831         sgen_minor_collector.build_fragments_finish (&mutator_allocator);
 832
 833         if (!unmask (mutator_allocator.alloc_head)) {
 834                 SGEN_LOG (1, "Nursery fully pinned");
 835                 for (pin_entry = pin_start; pin_entry < pin_end; ++pin_entry) {
 836                         void *p = *pin_entry;
 837                         SGEN_LOG (3, "Bastard pinning obj %p (%s), size: %zd", p, sgen_safe_name (p), sgen_safe_object_get_size (p));
 838                 }
 839         }
 840         return fragment_total;
 841 }
 842
 843 char *
 844 sgen_nursery_alloc_get_upper_alloc_bound (void)
 845 {
 846         /*FIXME we need to calculate the collector upper bound as well, but this must be done in the previous GC. */
 847         return sgen_nursery_end;
 848 }
 849
 850 /*** Nursery memory allocation ***/
 851 void
 852 sgen_nursery_retire_region (void *address, ptrdiff_t size)
 853 {
 854         HEAVY_STAT (InterlockedExchangeAdd (&stat_wasted_bytes_discarded_fragments, size));
 855 }
 856
 857 gboolean
 858 sgen_can_alloc_size (size_t size)
 859 {
 860         SgenFragment *frag;
 861
 862         if (!SGEN_CAN_ALIGN_UP (size))
 863                 return FALSE;
 864
 865         size = SGEN_ALIGN_UP (size);
 866
 867         for (frag = unmask (mutator_allocator.alloc_head); frag; frag = unmask (frag->next)) {
 868                 if ((size_t)(frag->fragment_end - frag->fragment_next) >= size)
 869                         return TRUE;
 870         }
 871         return FALSE;
 872 }
 873
 874 void*
 875 sgen_nursery_alloc (size_t size)
 876 {
 877         SGEN_ASSERT (1, size >= sizeof (MonoObject) && size <= (SGEN_MAX_SMALL_OBJ_SIZE + CANARY_SIZE), "Invalid nursery object size");
 878
 879         SGEN_LOG (4, "Searching nursery for size: %zd", size);
 880         size = SGEN_ALIGN_UP (size);
 881
 882         HEAVY_STAT (InterlockedIncrement (&stat_nursery_alloc_requests));
 883
 884         return sgen_fragment_allocator_par_alloc (&mutator_allocator, size);
 885 }
 886
 887 void*
 888 sgen_nursery_alloc_range (size_t desired_size, size_t minimum_size, size_t *out_alloc_size)
 889 {
 890         SGEN_LOG (4, "Searching for byte range desired size: %zd minimum size %zd", desired_size, minimum_size);
 891
 892         HEAVY_STAT (InterlockedIncrement (&stat_nursery_alloc_range_requests));
 893
 894         return sgen_fragment_allocator_par_range_alloc (&mutator_allocator, desired_size, minimum_size, out_alloc_size);
 895 }
 896
 897 /*** Initialization ***/
 898
 899 #ifdef HEAVY_STATISTICS
 900
 901 void
 902 sgen_nursery_allocator_init_heavy_stats (void)
 903 {
 904         mono_counters_register ("bytes wasted trailer fragments", MONO_COUNTER_GC | MONO_COUNTER_INT, &stat_wasted_bytes_trailer);
 905         mono_counters_register ("bytes wasted small areas", MONO_COUNTER_GC | MONO_COUNTER_INT, &stat_wasted_bytes_small_areas);
 906         mono_counters_register ("bytes wasted discarded fragments", MONO_COUNTER_GC | MONO_COUNTER_INT, &stat_wasted_bytes_discarded_fragments);
 907
 908         mono_counters_register ("# nursery alloc requests", MONO_COUNTER_GC | MONO_COUNTER_INT, &stat_nursery_alloc_requests);
 909         mono_counters_register ("# nursery alloc iterations", MONO_COUNTER_GC | MONO_COUNTER_INT, &stat_alloc_iterations);
 910         mono_counters_register ("# nursery alloc retries", MONO_COUNTER_GC | MONO_COUNTER_INT, &stat_alloc_retries);
 911
 912         mono_counters_register ("# nursery alloc range requests", MONO_COUNTER_GC | MONO_COUNTER_INT, &stat_nursery_alloc_range_requests);
 913         mono_counters_register ("# nursery alloc range iterations", MONO_COUNTER_GC | MONO_COUNTER_INT, &stat_alloc_range_iterations);
 914         mono_counters_register ("# nursery alloc range restries", MONO_COUNTER_GC | MONO_COUNTER_INT, &stat_alloc_range_retries);
 915 }
 916
 917 #endif
 918
 919 void
 920 sgen_init_nursery_allocator (void)
 921 {
 922         sgen_register_fixed_internal_mem_type (INTERNAL_MEM_FRAGMENT, sizeof (SgenFragment));
 923 #ifdef NALLOC_DEBUG
 924         alloc_records = sgen_alloc_os_memory (sizeof (AllocRecord) * ALLOC_RECORD_COUNT, SGEN_ALLOC_INTERNAL | SGEN_ALLOC_ACTIVATE, "debugging memory");
 925 #endif
 926 }
 927
 928 void
 929 sgen_nursery_alloc_prepare_for_minor (void)
 930 {
 931         sgen_minor_collector.prepare_to_space (sgen_space_bitmap, sgen_space_bitmap_size);
 932 }
 933
 934 void
 935 sgen_nursery_alloc_prepare_for_major (void)
 936 {
 937         sgen_minor_collector.prepare_to_space (sgen_space_bitmap, sgen_space_bitmap_size);
 938 }
 939
 940 void
 941 sgen_nursery_allocator_set_nursery_bounds (char *start, char *end)
 942 {
 943         sgen_nursery_start = start;
 944         sgen_nursery_end = end;
 945
 946         /*
 947          * This will not divide evenly for tiny nurseries (<4kb), so we make sure to be on
 948          * the right side of things and round up.  We could just do a MIN(1,x) instead,
 949          * since the nursery size must be a power of 2.
 950          */
 951         sgen_space_bitmap_size = (end - start + SGEN_TO_SPACE_GRANULE_IN_BYTES * 8 - 1) / (SGEN_TO_SPACE_GRANULE_IN_BYTES * 8);
 952         sgen_space_bitmap = g_malloc0 (sgen_space_bitmap_size);
 953
 954         /* Setup the single first large fragment */
 955         sgen_minor_collector.init_nursery (&mutator_allocator, start, end);
 956 }
 957
 958 #endif