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