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