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