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