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