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