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