2 * sgen-los.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 "metadata/sgen-gc.h"
53 #include "metadata/sgen-protocol.h"
54 #include "metadata/sgen-cardtable.h"
55 #include "metadata/sgen-memory-governor.h"
56 #include "utils/mono-mmap.h"
58 #define LOS_SECTION_SIZE (1024 * 1024)
61 * This shouldn't be much smaller or larger than MAX_SMALL_OBJ_SIZE.
62 * Must be at least sizeof (LOSSection).
64 #define LOS_CHUNK_SIZE 4096
65 #define LOS_CHUNK_BITS 12
67 /* Largest object that can be allocated in a section. */
68 #define LOS_SECTION_OBJECT_LIMIT (LOS_SECTION_SIZE - LOS_CHUNK_SIZE - sizeof (LOSObject))
69 //#define LOS_SECTION_OBJECT_LIMIT 0
70 #define LOS_SECTION_NUM_CHUNKS ((LOS_SECTION_SIZE >> LOS_CHUNK_BITS) - 1)
72 #define LOS_SECTION_FOR_OBJ(obj) ((LOSSection*)((mword)(obj) & ~(mword)(LOS_SECTION_SIZE - 1)))
73 #define LOS_CHUNK_INDEX(obj,section) (((char*)(obj) - (char*)(section)) >> LOS_CHUNK_BITS)
75 #define LOS_NUM_FAST_SIZES 32
77 typedef struct _LOSFreeChunks LOSFreeChunks;
78 struct _LOSFreeChunks {
79 LOSFreeChunks *next_size;
83 typedef struct _LOSSection LOSSection;
87 unsigned char *free_chunk_map;
90 LOSObject *los_object_list = NULL;
91 mword los_memory_usage = 0;
93 static LOSSection *los_sections = NULL;
94 static LOSFreeChunks *los_fast_free_lists [LOS_NUM_FAST_SIZES]; /* 0 is for larger sizes */
95 static mword los_num_objects = 0;
96 static int los_num_sections = 0;
97 static mword next_los_collection = 2*1024*1024; /* 2 MB, need to tune */
100 //#define LOS_CONSISTENCY_CHECK
104 #define LOS_SEGMENT_SIZE (4096 * 1024)
106 static char *los_segment = NULL;
107 static int los_segment_index = 0;
110 #ifdef LOS_CONSISTENCY_CHECK
112 los_consistency_check (void)
117 mword memory_usage = 0;
119 for (obj = los_object_list; obj; obj = obj->next) {
120 char *end = obj->data + obj->size;
121 int start_index, num_chunks;
123 memory_usage += obj->size;
125 if (obj->size > LOS_SECTION_OBJECT_LIMIT)
128 section = LOS_SECTION_FOR_OBJ (obj);
130 g_assert (end <= (char*)section + LOS_SECTION_SIZE);
132 start_index = LOS_CHUNK_INDEX (obj, section);
133 num_chunks = (obj->size + sizeof (LOSObject) + LOS_CHUNK_SIZE - 1) >> LOS_CHUNK_BITS;
134 for (i = start_index; i < start_index + num_chunks; ++i)
135 g_assert (!section->free_chunk_map [i]);
138 for (i = 0; i < LOS_NUM_FAST_SIZES; ++i) {
139 LOSFreeChunks *size_chunks;
140 for (size_chunks = los_fast_free_lists [i]; size_chunks; size_chunks = size_chunks->next_size) {
141 LOSSection *section = LOS_SECTION_FOR_OBJ (size_chunks);
142 int j, num_chunks, start_index;
145 g_assert (size_chunks->size >= LOS_NUM_FAST_SIZES * LOS_CHUNK_SIZE);
147 g_assert (size_chunks->size == i * LOS_CHUNK_SIZE);
149 num_chunks = size_chunks->size >> LOS_CHUNK_BITS;
150 start_index = LOS_CHUNK_INDEX (size_chunks, section);
151 for (j = start_index; j < start_index + num_chunks; ++j)
152 g_assert (section->free_chunk_map [j]);
156 g_assert (los_memory_usage == memory_usage);
161 add_free_chunk (LOSFreeChunks *free_chunks, size_t size)
163 int num_chunks = size >> LOS_CHUNK_BITS;
165 free_chunks->size = size;
167 if (num_chunks >= LOS_NUM_FAST_SIZES)
169 free_chunks->next_size = los_fast_free_lists [num_chunks];
170 los_fast_free_lists [num_chunks] = free_chunks;
173 static LOSFreeChunks*
174 get_from_size_list (LOSFreeChunks **list, size_t size)
176 LOSFreeChunks *free_chunks = NULL;
178 int num_chunks, i, start_index;
180 g_assert ((size & (LOS_CHUNK_SIZE - 1)) == 0);
184 if (free_chunks->size >= size)
186 list = &(*list)->next_size;
192 *list = free_chunks->next_size;
194 if (free_chunks->size > size)
195 add_free_chunk ((LOSFreeChunks*)((char*)free_chunks + size), free_chunks->size - size);
197 num_chunks = size >> LOS_CHUNK_BITS;
199 section = LOS_SECTION_FOR_OBJ (free_chunks);
201 start_index = LOS_CHUNK_INDEX (free_chunks, section);
202 for (i = start_index; i < start_index + num_chunks; ++i) {
203 g_assert (section->free_chunk_map [i]);
204 section->free_chunk_map [i] = 0;
207 section->num_free_chunks -= size >> LOS_CHUNK_BITS;
208 g_assert (section->num_free_chunks >= 0);
214 get_los_section_memory (size_t size)
217 LOSFreeChunks *free_chunks;
220 size += LOS_CHUNK_SIZE - 1;
221 size &= ~(LOS_CHUNK_SIZE - 1);
223 num_chunks = size >> LOS_CHUNK_BITS;
225 g_assert (size > 0 && size - sizeof (LOSObject) <= LOS_SECTION_OBJECT_LIMIT);
226 g_assert (num_chunks > 0);
229 if (num_chunks >= LOS_NUM_FAST_SIZES) {
230 free_chunks = get_from_size_list (&los_fast_free_lists [0], size);
233 for (i = num_chunks; i < LOS_NUM_FAST_SIZES; ++i) {
234 free_chunks = get_from_size_list (&los_fast_free_lists [i], size);
239 free_chunks = get_from_size_list (&los_fast_free_lists [0], size);
243 return (LOSObject*)free_chunks;
245 if (!sgen_memgov_try_alloc_space (LOS_SECTION_SIZE, SPACE_LOS))
248 section = sgen_alloc_os_memory_aligned (LOS_SECTION_SIZE, LOS_SECTION_SIZE, TRUE);
253 free_chunks = (LOSFreeChunks*)((char*)section + LOS_CHUNK_SIZE);
254 free_chunks->size = LOS_SECTION_SIZE - LOS_CHUNK_SIZE;
255 free_chunks->next_size = los_fast_free_lists [0];
256 los_fast_free_lists [0] = free_chunks;
258 section->num_free_chunks = LOS_SECTION_NUM_CHUNKS;
260 section->free_chunk_map = (unsigned char*)section + sizeof (LOSSection);
261 g_assert (sizeof (LOSSection) + LOS_SECTION_NUM_CHUNKS + 1 <= LOS_CHUNK_SIZE);
262 section->free_chunk_map [0] = 0;
263 memset (section->free_chunk_map + 1, 1, LOS_SECTION_NUM_CHUNKS);
265 section->next = los_sections;
266 los_sections = section;
274 free_los_section_memory (LOSObject *obj, size_t size)
276 LOSSection *section = LOS_SECTION_FOR_OBJ (obj);
277 int num_chunks, i, start_index;
279 size += LOS_CHUNK_SIZE - 1;
280 size &= ~(LOS_CHUNK_SIZE - 1);
282 num_chunks = size >> LOS_CHUNK_BITS;
284 g_assert (size > 0 && size - sizeof (LOSObject) <= LOS_SECTION_OBJECT_LIMIT);
285 g_assert (num_chunks > 0);
287 section->num_free_chunks += num_chunks;
288 g_assert (section->num_free_chunks <= LOS_SECTION_NUM_CHUNKS);
291 * We could free the LOS section here if it's empty, but we
292 * can't unless we also remove its free chunks from the fast
293 * free lists. Instead, we do it in los_sweep().
296 start_index = LOS_CHUNK_INDEX (obj, section);
297 for (i = start_index; i < start_index + num_chunks; ++i) {
298 g_assert (!section->free_chunk_map [i]);
299 section->free_chunk_map [i] = 1;
302 add_free_chunk ((LOSFreeChunks*)obj, size);
308 sgen_los_free_object (LOSObject *obj)
311 size_t size = obj->size;
312 DEBUG (4, fprintf (gc_debug_file, "Freed large object %p, size %lu\n", obj->data, (unsigned long)obj->size));
313 binary_protocol_empty (obj->data, obj->size);
315 los_memory_usage -= size;
321 if (size > LOS_SECTION_OBJECT_LIMIT) {
323 pagesize = mono_pagesize ();
324 size += sizeof (LOSObject);
325 size += pagesize - 1;
326 size &= ~(pagesize - 1);
327 sgen_free_os_memory (obj, size);
328 sgen_memgov_release_space (size, SPACE_LOS);
330 free_los_section_memory (obj, size + sizeof (LOSObject));
331 #ifdef LOS_CONSISTENCY_CHECKS
332 los_consistency_check ();
340 * Objects with size >= MAX_SMALL_SIZE are allocated in the large object space.
341 * They are currently kept track of with a linked list.
342 * They don't move, so there is no need to pin them during collection
343 * and we avoid the memcpy overhead.
346 sgen_los_alloc_large_inner (MonoVTable *vtable, size_t size)
348 LOSObject *obj = NULL;
351 g_assert (size > SGEN_MAX_SMALL_OBJ_SIZE);
355 los_segment = sgen_alloc_os_memory (LOS_SEGMENT_SIZE, TRUE);
356 los_segment_index = ALIGN_UP (los_segment_index);
358 obj = (LOSObject*)(los_segment + los_segment_index);
359 los_segment_index += size + sizeof (LOSObject);
360 g_assert (los_segment_index <= LOS_SEGMENT_SIZE);
362 sgen_ensure_free_space (size);
365 obj = malloc (size + sizeof (LOSObject));
366 memset (obj, 0, size + sizeof (LOSObject));
368 if (size > LOS_SECTION_OBJECT_LIMIT) {
369 size_t alloc_size = size;
371 pagesize = mono_pagesize ();
372 alloc_size += sizeof (LOSObject);
373 alloc_size += pagesize - 1;
374 alloc_size &= ~(pagesize - 1);
375 if (sgen_memgov_try_alloc_space (alloc_size, SPACE_LOS)) {
376 obj = sgen_alloc_os_memory (alloc_size, TRUE);
378 obj->huge_object = TRUE;
381 obj = get_los_section_memory (size + sizeof (LOSObject));
383 memset (obj, 0, size + sizeof (LOSObject));
389 g_assert (!((mword)obj->data & (SGEN_ALLOC_ALIGN - 1)));
391 vtslot = (void**)obj->data;
393 sgen_update_heap_boundaries ((mword)obj->data, (mword)obj->data + size);
394 obj->next = los_object_list;
395 los_object_list = obj;
396 los_memory_usage += size;
398 DEBUG (4, fprintf (gc_debug_file, "Allocated large object %p, vtable: %p (%s), size: %zd\n", obj->data, vtable, vtable->klass->name, size));
399 binary_protocol_alloc (obj->data, vtable, size);
401 #ifdef LOS_CONSISTENCY_CHECK
402 los_consistency_check ();
409 sgen_los_sweep (void)
411 LOSSection *section, *prev;
413 int num_sections = 0;
415 for (i = 0; i < LOS_NUM_FAST_SIZES; ++i)
416 los_fast_free_lists [i] = NULL;
419 section = los_sections;
421 if (section->num_free_chunks == LOS_SECTION_NUM_CHUNKS) {
422 LOSSection *next = section->next;
427 sgen_free_os_memory (section, LOS_SECTION_SIZE);
428 sgen_memgov_release_space (LOS_SECTION_SIZE, SPACE_LOS);
434 for (i = 0; i <= LOS_SECTION_NUM_CHUNKS; ++i) {
435 if (section->free_chunk_map [i]) {
437 for (j = i + 1; j <= LOS_SECTION_NUM_CHUNKS && section->free_chunk_map [j]; ++j)
439 add_free_chunk ((LOSFreeChunks*)((char*)section + (i << LOS_CHUNK_BITS)), (j - i) << LOS_CHUNK_BITS);
445 section = section->next;
450 #ifdef LOS_CONSISTENCY_CHECK
451 los_consistency_check ();
455 g_print ("LOS sections: %d objects: %d usage: %d\n", num_sections, los_num_objects, los_memory_usage);
456 for (i = 0; i < LOS_NUM_FAST_SIZES; ++i) {
458 LOSFreeChunks *free_chunks;
459 for (free_chunks = los_fast_free_lists [i]; free_chunks; free_chunks = free_chunks->next_size)
461 g_print (" %d: %d\n", i, num_chunks);
465 g_assert (los_num_sections == num_sections);
469 sgen_ptr_is_in_los (char *ptr, char **start)
474 for (obj = los_object_list; obj; obj = obj->next) {
475 char *end = obj->data + obj->size;
477 if (ptr >= obj->data && ptr < end) {
486 sgen_los_iterate_objects (IterateObjectCallbackFunc cb, void *user_data)
490 for (obj = los_object_list; obj; obj = obj->next)
491 cb (obj->data, obj->size, user_data);
495 sgen_los_is_valid_object (char *object)
499 for (obj = los_object_list; obj; obj = obj->next) {
500 if (obj->data == object)
507 mono_sgen_los_describe_pointer (char *ptr)
511 for (obj = los_object_list; obj; obj = obj->next) {
513 if (obj->data > ptr || obj->data + obj->size <= ptr)
516 if (obj->size > LOS_SECTION_OBJECT_LIMIT)
517 fprintf (gc_debug_file, "huge-los-ptr ");
519 fprintf (gc_debug_file, "los-ptr ");
521 vtable = (MonoVTable*)SGEN_LOAD_VTABLE (obj->data);
523 if (obj->data == ptr)
524 fprintf (gc_debug_file, "(object %s.%s size %d)",
525 vtable->klass->name_space, vtable->klass->name, (int)obj->size);
527 fprintf (gc_debug_file, "(interior-ptr offset %td of %p (%s.%s) size %d)",
528 ptr - obj->data, obj->data,
529 vtable->klass->name_space, vtable->klass->name, (int)obj->size);
537 sgen_los_iterate_live_block_ranges (sgen_cardtable_block_callback callback)
540 for (obj = los_object_list; obj; obj = obj->next) {
541 MonoVTable *vt = (MonoVTable*)SGEN_LOAD_VTABLE (obj->data);
542 if (SGEN_VTABLE_HAS_REFERENCES (vt))
543 callback ((mword)obj->data, (mword)obj->size);
547 #ifdef SGEN_HAVE_CARDTABLE
549 sgen_los_scan_card_table (SgenGrayQueue *queue)
553 for (obj = los_object_list; obj; obj = obj->next) {
554 sgen_cardtable_scan_object (obj->data, obj->size, NULL, queue);
559 #endif /* HAVE_SGEN_GC */