2 * sgen-pinned-allocator.c: Simple generational GC.
5 * Paolo Molaro (lupus@ximian.com)
7 * Copyright 2005-2010 Novell, Inc (http://www.novell.com)
9 * Thread start/stop adapted from Boehm's GC:
10 * Copyright (c) 1994 by Xerox Corporation. All rights reserved.
11 * Copyright (c) 1996 by Silicon Graphics. All rights reserved.
12 * Copyright (c) 1998 by Fergus Henderson. All rights reserved.
13 * Copyright (c) 2000-2004 by Hewlett-Packard Company. All rights reserved.
15 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
16 * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
18 * Permission is hereby granted to use or copy this program
19 * for any purpose, provided the above notices are retained on all copies.
20 * Permission to modify the code and to distribute modified code is granted,
21 * provided the above notices are retained, and a notice that the code was
22 * modified is included with the above copyright notice.
25 * Copyright 2001-2003 Ximian, Inc
26 * Copyright 2003-2010 Novell, Inc.
28 * Permission is hereby granted, free of charge, to any person obtaining
29 * a copy of this software and associated documentation files (the
30 * "Software"), to deal in the Software without restriction, including
31 * without limitation the rights to use, copy, modify, merge, publish,
32 * distribute, sublicense, and/or sell copies of the Software, and to
33 * permit persons to whom the Software is furnished to do so, subject to
34 * the following conditions:
36 * The above copyright notice and this permission notice shall be
37 * included in all copies or substantial portions of the Software.
39 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
40 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
41 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
42 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
43 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
44 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
45 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
52 #include "utils/mono-counters.h"
53 #include "metadata/sgen-gc.h"
54 #include "metadata/sgen-memory-governor.h"
56 /* Pinned objects are allocated in the LOS space if bigger than half a page
57 * or from freelists otherwise. We assume that pinned objects are relatively few
58 * and they have a slow dying speed (like interned strings, thread objects).
59 * As such they will be collected only at major collections.
60 * free lists are not global: when we need memory we allocate a PinnedChunk.
61 * Each pinned chunk is made of several pages, the first of wich is used
62 * internally for bookeeping (here think of a page as 4KB). The bookeeping
63 * includes the freelists vectors and info about the object size of each page
64 * in the pinned chunk. So, when needed, a free page is found in a pinned chunk,
65 * a size is assigned to it, the page is divided in the proper chunks and each
66 * chunk is added to the freelist. To not waste space, the remaining space in the
67 * first page is used as objects of size 16 or 32 (need to measure which are more
69 * We use this same structure to allocate memory used internally by the GC, so
70 * we never use malloc/free if we need to alloc during collection: the world is stopped
71 * and malloc/free will deadlock.
72 * When we want to iterate over pinned objects, we just scan a page at a time
73 * linearly according to the size of objects in the page: the next pointer used to link
74 * the items in the freelist uses the same word as the vtable. Since we keep freelists
75 * for each pinned chunk, if the word points outside the pinned chunk it means
77 * We could avoid this expensive scanning in creative ways. We could have a policy
78 * of putting in the pinned space only objects we know about that have no struct fields
79 * with references and we can easily use a even expensive write barrier for them,
80 * since pointer writes on such objects should be rare.
81 * The best compromise is to just alloc interned strings and System.MonoType in them.
82 * It would be nice to allocate MonoThread in it, too: must check that we properly
83 * use write barriers so we don't have to do any expensive scanning of the whole pinned
84 * chunk list during minor collections. We can avoid it now because we alloc in it only
85 * reference-free objects.
87 struct _SgenPinnedChunk {
90 SgenPinnedAllocator *allocator;
91 int *page_sizes; /* a 0 means the page is still unused */
93 SgenPinnedChunk *free_list_nexts [SGEN_PINNED_FREELIST_NUM_SLOTS];
95 void *data [1]; /* page sizes and free lists are stored here */
98 #define PINNED_FIRST_SLOT_SIZE (sizeof (gpointer) * 4)
99 #define MAX_FREELIST_SIZE 8192
101 /* This is a fixed value used for pinned chunks, not the system pagesize */
102 #define FREELIST_PAGESIZE (16*1024)
104 /* keep each size a multiple of ALLOC_ALIGN */
105 /* on 64 bit systems 8 is likely completely unused. */
106 static const int freelist_sizes [] = {
107 8, 16, 24, 32, 40, 48, 64, 80,
108 96, 128, 160, 192, 224, 256, 320, 384,
109 448, 512, 584, 680, 816, 1024, 1360, 2048,
110 2336, 2728, 3272, 4096, 5456, 8192 };
112 #define LARGE_PINNED_MEM_HEADER_MAGIC 0x7d289f3a
114 typedef struct _LargePinnedMemHeader LargePinnedMemHeader;
115 struct _LargePinnedMemHeader {
121 static long long pinned_chunk_bytes_alloced = 0;
122 static long long large_pinned_bytes_alloced = 0;
124 #ifdef HEAVY_STATISTICS
125 static long long stat_pinned_alloc = 0;
132 report_pinned_chunk (SgenPinnedChunk *chunk, int seq) {
134 int i, free_pages, num_free, free_mem;
136 for (i = 0; i < chunk->num_pages; ++i) {
137 if (!chunk->page_sizes [i])
140 printf ("Pinned chunk %d at %p, size: %d, pages: %d, free: %d\n", seq, chunk, chunk->num_pages * FREELIST_PAGESIZE, chunk->num_pages, free_pages);
141 free_mem = FREELIST_PAGESIZE * free_pages;
142 for (i = 0; i < SGEN_PINNED_FREELIST_NUM_SLOTS; ++i) {
143 if (!chunk->free_list [i])
146 p = chunk->free_list [i];
151 printf ("\tfree list of size %d, %d items\n", freelist_sizes [i], num_free);
152 free_mem += freelist_sizes [i] * num_free;
154 printf ("\tfree memory in chunk: %d\n", free_mem);
161 sgen_report_pinned_mem_usage (SgenPinnedAllocator *alc)
163 SgenPinnedChunk *chunk;
165 for (chunk = alc->chunk_list; chunk; chunk = chunk->block.next)
166 report_pinned_chunk (chunk, i++);
170 * Find the slot number in the freelist for memory chunks that
171 * can contain @size objects.
174 slot_for_size (size_t size)
177 /* do a binary search or lookup table later. */
178 for (slot = 0; slot < SGEN_PINNED_FREELIST_NUM_SLOTS; ++slot) {
179 if (freelist_sizes [slot] >= size)
182 g_assert_not_reached ();
187 * Build a free list for @size memory chunks from the memory area between
188 * start_page and end_page.
191 build_freelist (SgenPinnedAllocator *alc, SgenPinnedChunk *chunk, int slot, int size, char *start_page, char *end_page)
195 /*g_print ("building freelist for slot %d, size %d in %p\n", slot, size, chunk);*/
196 p = (void**)start_page;
197 end = (void**)(end_page - size);
198 g_assert (!chunk->free_list [slot]);
199 chunk->free_list [slot] = p;
200 while ((char*)p + size <= (char*)end) {
202 *p = (void*)((char*)p + size);
206 /*g_print ("%d items created, max: %d\n", count, (end_page - start_page) / size);*/
208 g_assert (!chunk->free_list_nexts [slot]);
209 chunk->free_list_nexts [slot] = alc->free_lists [slot];
210 alc->free_lists [slot] = chunk;
213 static SgenPinnedChunk*
214 alloc_pinned_chunk (SgenPinnedAllocator *alc)
216 SgenPinnedChunk *chunk;
218 int size = SGEN_PINNED_CHUNK_SIZE;
220 chunk = sgen_alloc_os_memory_aligned (size, size, TRUE);
221 chunk->block.role = MEMORY_ROLE_PINNED;
223 sgen_update_heap_boundaries ((mword)chunk, ((mword)chunk + size));
225 pinned_chunk_bytes_alloced += size;
227 /* setup the bookeeping fields */
228 chunk->num_pages = size / FREELIST_PAGESIZE;
229 offset = G_STRUCT_OFFSET (SgenPinnedChunk, data);
230 chunk->page_sizes = (void*)((char*)chunk + offset);
231 offset += sizeof (int) * chunk->num_pages;
232 offset = SGEN_ALIGN_UP (offset);
233 chunk->free_list = (void*)((char*)chunk + offset);
234 offset += sizeof (void*) * SGEN_PINNED_FREELIST_NUM_SLOTS;
235 offset = SGEN_ALIGN_UP (offset);
236 chunk->start_data = (void*)((char*)chunk + offset);
238 /* allocate the first page to the freelist */
239 chunk->page_sizes [0] = PINNED_FIRST_SLOT_SIZE;
240 build_freelist (alc, chunk, slot_for_size (PINNED_FIRST_SLOT_SIZE), PINNED_FIRST_SLOT_SIZE,
241 chunk->start_data, ((char*)chunk + FREELIST_PAGESIZE));
242 sgen_debug_printf (4, "Allocated pinned chunk %p, size: %d\n", chunk, size);
244 chunk->block.next = alc->chunk_list;
245 alc->chunk_list = chunk;
247 chunk->allocator = alc;
252 /* Must be called with an empty freelist for the given slot. */
254 populate_chunk_page (SgenPinnedAllocator *alc, SgenPinnedChunk *chunk, int slot)
256 int size = freelist_sizes [slot];
258 g_assert (!chunk->free_list [slot]);
259 g_assert (!chunk->free_list_nexts [slot]);
260 for (i = 0; i < chunk->num_pages; ++i) {
261 if (chunk->page_sizes [i])
263 chunk->page_sizes [i] = size;
264 build_freelist (alc, chunk, slot, size, (char*)chunk + FREELIST_PAGESIZE * i, (char*)chunk + FREELIST_PAGESIZE * (i + 1));
271 alloc_from_slot (SgenPinnedAllocator *alc, int slot)
273 SgenPinnedChunk *pchunk;
274 size_t size = freelist_sizes [slot];
276 if (alc->delayed_free_lists [slot]) {
279 p = alc->delayed_free_lists [slot];
280 } while (SGEN_CAS_PTR (&alc->delayed_free_lists [slot], *p, p) != p);
286 pchunk = alc->free_lists [slot];
288 void **p = pchunk->free_list [slot];
294 pchunk->free_list [slot] = next;
297 alc->free_lists [slot] = pchunk->free_list_nexts [slot];
298 pchunk->free_list_nexts [slot] = NULL;
305 for (pchunk = alc->chunk_list; pchunk; pchunk = pchunk->block.next) {
306 if (populate_chunk_page (alc, pchunk, slot))
310 pchunk = alloc_pinned_chunk (alc);
311 /* FIXME: handle OOM */
312 if (pchunk->free_list [slot])
314 if (!populate_chunk_page (alc, pchunk, slot))
315 g_assert_not_reached ();
319 /* used for the GC-internal data structures */
321 sgen_alloc_pinned (SgenPinnedAllocator *alc, size_t size)
326 HEAVY_STAT (++stat_pinned_alloc);
328 if (size > freelist_sizes [SGEN_PINNED_FREELIST_NUM_SLOTS - 1]) {
329 LargePinnedMemHeader *mh;
331 size += sizeof (LargePinnedMemHeader);
332 mh = sgen_alloc_os_memory (size, TRUE);
333 mh->magic = LARGE_PINNED_MEM_HEADER_MAGIC;
335 /* FIXME: do a CAS here */
336 large_pinned_bytes_alloced += size;
340 slot = slot_for_size (size);
341 g_assert (size <= freelist_sizes [slot]);
342 res = alloc_from_slot (alc, slot);
348 free_from_slot (SgenPinnedAllocator *alc, void *addr, int slot)
350 SgenPinnedChunk *pchunk = (SgenPinnedChunk*)SGEN_PINNED_CHUNK_FOR_PTR (addr);
354 g_assert (addr >= (void*)pchunk && (char*)addr < (char*)pchunk + pchunk->num_pages * FREELIST_PAGESIZE);
356 next = pchunk->free_list [slot];
358 pchunk->free_list [slot] = p;
361 g_assert (!pchunk->free_list_nexts [slot]);
362 pchunk->free_list_nexts [slot] = alc->free_lists [slot];
363 alc->free_lists [slot] = pchunk;
368 sgen_free_pinned (SgenPinnedAllocator *alc, void *addr, size_t size)
370 LargePinnedMemHeader *mh;
375 if (size <= freelist_sizes [SGEN_PINNED_FREELIST_NUM_SLOTS - 1]) {
376 int slot = slot_for_size (size);
377 free_from_slot (alc, addr, slot);
381 mh = (LargePinnedMemHeader*)((char*)addr - G_STRUCT_OFFSET (LargePinnedMemHeader, data));
382 g_assert (mh->magic == LARGE_PINNED_MEM_HEADER_MAGIC);
383 g_assert (mh->size == size + sizeof (LargePinnedMemHeader));
384 /* FIXME: do a CAS */
385 large_pinned_bytes_alloced -= mh->size;
386 sgen_free_os_memory (mh, mh->size);
390 sgen_init_pinned_allocator (void)
392 g_assert (SGEN_PINNED_FREELIST_NUM_SLOTS == sizeof (freelist_sizes) / sizeof (freelist_sizes [0]));
394 #ifdef HEAVY_STATISTICS
395 mono_counters_register ("Pinned allocs", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_pinned_alloc);
400 sgen_pinned_scan_objects (SgenPinnedAllocator *alc, IterateObjectCallbackFunc callback, void *callback_data)
402 SgenPinnedChunk *chunk;
407 for (chunk = alc->chunk_list; chunk; chunk = chunk->block.next) {
408 end_chunk = (char*)chunk + chunk->num_pages * FREELIST_PAGESIZE;
409 sgen_debug_printf (6, "Scanning pinned chunk %p (range: %p-%p)\n", chunk, chunk->start_data, end_chunk);
410 for (i = 0; i < chunk->num_pages; ++i) {
411 obj_size = chunk->page_sizes [i];
414 p = i? (char*)chunk + i * FREELIST_PAGESIZE: chunk->start_data;
415 endp = i? p + FREELIST_PAGESIZE: (char*)chunk + FREELIST_PAGESIZE;
416 sgen_debug_printf (6, "Page %d (size: %d, range: %p-%p)\n", i, obj_size, p, endp);
417 while (p + obj_size <= endp) {
419 /* if the first word (the vtable) is outside the chunk we have an object */
420 if (*ptr && (*ptr < (void*)chunk || *ptr >= end_chunk))
421 callback ((char*)ptr, obj_size, callback_data);
429 sgen_pinned_update_heap_boundaries (SgenPinnedAllocator *alc)
431 SgenPinnedChunk *chunk;
432 for (chunk = alc->chunk_list; chunk; chunk = chunk->block.next) {
433 char *end_chunk = (char*)chunk + chunk->num_pages * FREELIST_PAGESIZE;
434 sgen_update_heap_boundaries ((mword)chunk, (mword)end_chunk);
439 * the array of pointers from @start to @end contains conservative
440 * pointers to objects inside @chunk: mark each referenced object
444 mark_pinned_from_addresses (SgenPinnedChunk *chunk, void **start, void **end, IterateObjectCallbackFunc callback, void *callback_data)
446 for (; start < end; start++) {
448 int offset = (char*)addr - (char*)chunk;
449 int page = offset / FREELIST_PAGESIZE;
450 int obj_offset = page == 0? offset - ((char*)chunk->start_data - (char*)chunk): offset % FREELIST_PAGESIZE;
451 int slot_size = chunk->page_sizes [page];
453 /* the page is not allocated */
456 /* would be faster if we restrict the sizes to power of two,
457 * but that's a waste of memory: need to measure. it could reduce
458 * fragmentation since there are less pages needed, if for example
459 * someone interns strings of each size we end up with one page per
460 * interned string (still this is just ~40 KB): with more fine-grained sizes
461 * this increases the number of used pages.
464 obj_offset /= slot_size;
465 obj_offset *= slot_size;
466 addr = (char*)chunk->start_data + obj_offset;
468 obj_offset /= slot_size;
469 obj_offset *= slot_size;
470 addr = (char*)chunk + page * FREELIST_PAGESIZE + obj_offset;
473 /* if the vtable is inside the chunk it's on the freelist, so skip */
474 /* FIXME: is it possible that we're pinning objects more than once here? */
475 if (*ptr && (*ptr < (void*)chunk->start_data || *ptr > (void*)((char*)chunk + chunk->num_pages * FREELIST_PAGESIZE)))
476 callback (addr, slot_size, callback_data);
481 sgen_pinned_scan_pinned_objects (SgenPinnedAllocator *alc, IterateObjectCallbackFunc callback, void *callback_data)
483 SgenPinnedChunk *chunk;
485 /* look for pinned addresses for pinned-alloc objects */
486 sgen_debug_printf (6, "Pinning from pinned-alloc objects\n");
487 for (chunk = alc->chunk_list; chunk; chunk = chunk->block.next) {
489 void **pinned = sgen_find_optimized_pin_queue_area (chunk->start_data,
490 (char*)chunk + chunk->num_pages * FREELIST_PAGESIZE, &num_pinned);
492 mark_pinned_from_addresses (chunk, pinned, pinned + num_pinned, callback, callback_data);