2 * sgen-los.c: Large objects space.
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.
14 * Copyright 2001-2003 Ximian, Inc
15 * Copyright 2003-2010 Novell, Inc.
16 * Copyright (C) 2012 Xamarin Inc
18 * This library is free software; you can redistribute it and/or
19 * modify it under the terms of the GNU Library General Public
20 * License 2.0 as published by the Free Software Foundation;
22 * This library is distributed in the hope that it will be useful,
23 * but WITHOUT ANY WARRANTY; without even the implied warranty of
24 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
25 * Library General Public License for more details.
27 * You should have received a copy of the GNU Library General Public
28 * License 2.0 along with this library; if not, write to the Free
29 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
36 #include "metadata/sgen-gc.h"
37 #include "metadata/sgen-protocol.h"
38 #include "metadata/sgen-cardtable.h"
39 #include "metadata/sgen-memory-governor.h"
40 #include "utils/mono-mmap.h"
41 #include "utils/mono-compiler.h"
43 #define LOS_SECTION_SIZE (1024 * 1024)
46 * This shouldn't be much smaller or larger than MAX_SMALL_OBJ_SIZE.
47 * Must be at least sizeof (LOSSection).
49 #define LOS_CHUNK_SIZE 4096
50 #define LOS_CHUNK_BITS 12
52 /* Largest object that can be allocated in a section. */
53 #define LOS_SECTION_OBJECT_LIMIT (LOS_SECTION_SIZE - LOS_CHUNK_SIZE - sizeof (LOSObject))
54 //#define LOS_SECTION_OBJECT_LIMIT 0
55 #define LOS_SECTION_NUM_CHUNKS ((LOS_SECTION_SIZE >> LOS_CHUNK_BITS) - 1)
57 #define LOS_SECTION_FOR_OBJ(obj) ((LOSSection*)((mword)(obj) & ~(mword)(LOS_SECTION_SIZE - 1)))
58 #define LOS_CHUNK_INDEX(obj,section) (((char*)(obj) - (char*)(section)) >> LOS_CHUNK_BITS)
60 #define LOS_NUM_FAST_SIZES 32
62 typedef struct _LOSFreeChunks LOSFreeChunks;
63 struct _LOSFreeChunks {
64 LOSFreeChunks *next_size;
68 typedef struct _LOSSection LOSSection;
71 size_t num_free_chunks;
72 unsigned char *free_chunk_map;
75 LOSObject *los_object_list = NULL;
76 mword los_memory_usage = 0;
78 static LOSSection *los_sections = NULL;
79 static LOSFreeChunks *los_fast_free_lists [LOS_NUM_FAST_SIZES]; /* 0 is for larger sizes */
80 static mword los_num_objects = 0;
81 static int los_num_sections = 0;
84 //#define LOS_CONSISTENCY_CHECK
88 #define LOS_SEGMENT_SIZE (4096 * 1024)
90 static char *los_segment = NULL;
91 static int los_segment_index = 0;
94 #ifdef LOS_CONSISTENCY_CHECK
96 los_consistency_check (void)
101 mword memory_usage = 0;
103 for (obj = los_object_list; obj; obj = obj->next) {
104 char *end = obj->data + obj->size;
105 int start_index, num_chunks;
107 memory_usage += obj->size;
109 if (obj->size > LOS_SECTION_OBJECT_LIMIT)
112 section = LOS_SECTION_FOR_OBJ (obj);
114 g_assert (end <= (char*)section + LOS_SECTION_SIZE);
116 start_index = LOS_CHUNK_INDEX (obj, section);
117 num_chunks = (obj->size + sizeof (LOSObject) + LOS_CHUNK_SIZE - 1) >> LOS_CHUNK_BITS;
118 for (i = start_index; i < start_index + num_chunks; ++i)
119 g_assert (!section->free_chunk_map [i]);
122 for (i = 0; i < LOS_NUM_FAST_SIZES; ++i) {
123 LOSFreeChunks *size_chunks;
124 for (size_chunks = los_fast_free_lists [i]; size_chunks; size_chunks = size_chunks->next_size) {
125 LOSSection *section = LOS_SECTION_FOR_OBJ (size_chunks);
126 int j, num_chunks, start_index;
129 g_assert (size_chunks->size >= LOS_NUM_FAST_SIZES * LOS_CHUNK_SIZE);
131 g_assert (size_chunks->size == i * LOS_CHUNK_SIZE);
133 num_chunks = size_chunks->size >> LOS_CHUNK_BITS;
134 start_index = LOS_CHUNK_INDEX (size_chunks, section);
135 for (j = start_index; j < start_index + num_chunks; ++j)
136 g_assert (section->free_chunk_map [j]);
140 g_assert (los_memory_usage == memory_usage);
145 add_free_chunk (LOSFreeChunks *free_chunks, size_t size)
147 size_t num_chunks = size >> LOS_CHUNK_BITS;
149 free_chunks->size = size;
151 if (num_chunks >= LOS_NUM_FAST_SIZES)
153 free_chunks->next_size = los_fast_free_lists [num_chunks];
154 los_fast_free_lists [num_chunks] = free_chunks;
157 static LOSFreeChunks*
158 get_from_size_list (LOSFreeChunks **list, size_t size)
160 LOSFreeChunks *free_chunks = NULL;
162 size_t i, num_chunks, start_index;
165 g_assert ((size & (LOS_CHUNK_SIZE - 1)) == 0);
169 if (free_chunks->size >= size)
171 list = &(*list)->next_size;
177 *list = free_chunks->next_size;
179 if (free_chunks->size > size)
180 add_free_chunk ((LOSFreeChunks*)((char*)free_chunks + size), free_chunks->size - size);
182 num_chunks = size >> LOS_CHUNK_BITS;
184 section = LOS_SECTION_FOR_OBJ (free_chunks);
186 start_index = LOS_CHUNK_INDEX (free_chunks, section);
187 for (i = start_index; i < start_index + num_chunks; ++i) {
188 g_assert (section->free_chunk_map [i]);
189 section->free_chunk_map [i] = 0;
192 section->num_free_chunks -= size >> LOS_CHUNK_BITS;
193 g_assert (section->num_free_chunks >= 0);
199 get_los_section_memory (size_t size)
202 LOSFreeChunks *free_chunks;
205 size += LOS_CHUNK_SIZE - 1;
206 size &= ~(LOS_CHUNK_SIZE - 1);
208 num_chunks = size >> LOS_CHUNK_BITS;
210 g_assert (size > 0 && size - sizeof (LOSObject) <= LOS_SECTION_OBJECT_LIMIT);
211 g_assert (num_chunks > 0);
214 if (num_chunks >= LOS_NUM_FAST_SIZES) {
215 free_chunks = get_from_size_list (&los_fast_free_lists [0], size);
218 for (i = num_chunks; i < LOS_NUM_FAST_SIZES; ++i) {
219 free_chunks = get_from_size_list (&los_fast_free_lists [i], size);
224 free_chunks = get_from_size_list (&los_fast_free_lists [0], size);
228 return (LOSObject*)free_chunks;
230 if (!sgen_memgov_try_alloc_space (LOS_SECTION_SIZE, SPACE_LOS))
233 section = sgen_alloc_os_memory_aligned (LOS_SECTION_SIZE, LOS_SECTION_SIZE, SGEN_ALLOC_HEAP | SGEN_ALLOC_ACTIVATE, NULL);
238 free_chunks = (LOSFreeChunks*)((char*)section + LOS_CHUNK_SIZE);
239 free_chunks->size = LOS_SECTION_SIZE - LOS_CHUNK_SIZE;
240 free_chunks->next_size = los_fast_free_lists [0];
241 los_fast_free_lists [0] = free_chunks;
243 section->num_free_chunks = LOS_SECTION_NUM_CHUNKS;
245 section->free_chunk_map = (unsigned char*)section + sizeof (LOSSection);
246 g_assert (sizeof (LOSSection) + LOS_SECTION_NUM_CHUNKS + 1 <= LOS_CHUNK_SIZE);
247 section->free_chunk_map [0] = 0;
248 memset (section->free_chunk_map + 1, 1, LOS_SECTION_NUM_CHUNKS);
250 section->next = los_sections;
251 los_sections = section;
259 free_los_section_memory (LOSObject *obj, size_t size)
261 LOSSection *section = LOS_SECTION_FOR_OBJ (obj);
262 size_t num_chunks, i, start_index;
264 size += LOS_CHUNK_SIZE - 1;
265 size &= ~(LOS_CHUNK_SIZE - 1);
267 num_chunks = size >> LOS_CHUNK_BITS;
269 g_assert (size > 0 && size - sizeof (LOSObject) <= LOS_SECTION_OBJECT_LIMIT);
270 g_assert (num_chunks > 0);
272 section->num_free_chunks += num_chunks;
273 g_assert (section->num_free_chunks <= LOS_SECTION_NUM_CHUNKS);
276 * We could free the LOS section here if it's empty, but we
277 * can't unless we also remove its free chunks from the fast
278 * free lists. Instead, we do it in los_sweep().
281 start_index = LOS_CHUNK_INDEX (obj, section);
282 for (i = start_index; i < start_index + num_chunks; ++i) {
283 g_assert (!section->free_chunk_map [i]);
284 section->free_chunk_map [i] = 1;
287 add_free_chunk ((LOSFreeChunks*)obj, size);
293 sgen_los_free_object (LOSObject *obj)
296 size_t size = obj->size;
297 SGEN_LOG (4, "Freed large object %p, size %lu", obj->data, (unsigned long)obj->size);
298 binary_protocol_empty (obj->data, obj->size);
300 los_memory_usage -= size;
306 if (size > LOS_SECTION_OBJECT_LIMIT) {
308 pagesize = mono_pagesize ();
309 size += sizeof (LOSObject);
310 size += pagesize - 1;
311 size &= ~(pagesize - 1);
312 sgen_free_os_memory (obj, size, SGEN_ALLOC_HEAP);
313 sgen_memgov_release_space (size, SPACE_LOS);
315 free_los_section_memory (obj, size + sizeof (LOSObject));
316 #ifdef LOS_CONSISTENCY_CHECKS
317 los_consistency_check ();
325 * Objects with size >= MAX_SMALL_SIZE are allocated in the large object space.
326 * They are currently kept track of with a linked list.
327 * They don't move, so there is no need to pin them during collection
328 * and we avoid the memcpy overhead.
331 sgen_los_alloc_large_inner (MonoVTable *vtable, size_t size)
333 LOSObject *obj = NULL;
336 g_assert (size > SGEN_MAX_SMALL_OBJ_SIZE);
337 g_assert ((size & 1) == 0);
340 * size + sizeof (LOSObject) <= SSIZE_MAX - (mono_pagesize () - 1)
344 * size <= SSIZE_MAX - (mono_pagesize () - 1) - sizeof (LOSObject)
346 if (size > SSIZE_MAX - (mono_pagesize () - 1) - sizeof (LOSObject))
351 los_segment = sgen_alloc_os_memory (LOS_SEGMENT_SIZE, SGEN_ALLOC_HEAP | SGEN_ALLOC_ACTIVATE, NULL);
352 los_segment_index = ALIGN_UP (los_segment_index);
354 obj = (LOSObject*)(los_segment + los_segment_index);
355 los_segment_index += size + sizeof (LOSObject);
356 g_assert (los_segment_index <= LOS_SEGMENT_SIZE);
358 sgen_ensure_free_space (size);
361 obj = malloc (size + sizeof (LOSObject));
362 memset (obj, 0, size + sizeof (LOSObject));
364 if (size > LOS_SECTION_OBJECT_LIMIT) {
365 size_t alloc_size = size;
367 pagesize = mono_pagesize ();
368 alloc_size += sizeof (LOSObject);
369 alloc_size += pagesize - 1;
370 alloc_size &= ~(pagesize - 1);
371 if (sgen_memgov_try_alloc_space (alloc_size, SPACE_LOS)) {
372 obj = sgen_alloc_os_memory (alloc_size, SGEN_ALLOC_HEAP | SGEN_ALLOC_ACTIVATE, NULL);
375 obj = get_los_section_memory (size + sizeof (LOSObject));
377 memset (obj, 0, size + sizeof (LOSObject));
383 g_assert (!((mword)obj->data & (SGEN_ALLOC_ALIGN - 1)));
385 vtslot = (void**)obj->data;
387 sgen_update_heap_boundaries ((mword)obj->data, (mword)obj->data + size);
388 obj->next = los_object_list;
389 los_object_list = obj;
390 los_memory_usage += size;
392 SGEN_LOG (4, "Allocated large object %p, vtable: %p (%s), size: %zd", obj->data, vtable, vtable->klass->name, size);
393 binary_protocol_alloc (obj->data, vtable, size);
395 #ifdef LOS_CONSISTENCY_CHECK
396 los_consistency_check ();
403 sgen_los_sweep (void)
405 LOSSection *section, *prev;
407 int num_sections = 0;
409 for (i = 0; i < LOS_NUM_FAST_SIZES; ++i)
410 los_fast_free_lists [i] = NULL;
413 section = los_sections;
415 if (section->num_free_chunks == LOS_SECTION_NUM_CHUNKS) {
416 LOSSection *next = section->next;
421 sgen_free_os_memory (section, LOS_SECTION_SIZE, SGEN_ALLOC_HEAP);
422 sgen_memgov_release_space (LOS_SECTION_SIZE, SPACE_LOS);
428 for (i = 0; i <= LOS_SECTION_NUM_CHUNKS; ++i) {
429 if (section->free_chunk_map [i]) {
431 for (j = i + 1; j <= LOS_SECTION_NUM_CHUNKS && section->free_chunk_map [j]; ++j)
433 add_free_chunk ((LOSFreeChunks*)((char*)section + (i << LOS_CHUNK_BITS)), (j - i) << LOS_CHUNK_BITS);
439 section = section->next;
444 #ifdef LOS_CONSISTENCY_CHECK
445 los_consistency_check ();
449 g_print ("LOS sections: %d objects: %d usage: %d\n", num_sections, los_num_objects, los_memory_usage);
450 for (i = 0; i < LOS_NUM_FAST_SIZES; ++i) {
452 LOSFreeChunks *free_chunks;
453 for (free_chunks = los_fast_free_lists [i]; free_chunks; free_chunks = free_chunks->next_size)
455 g_print (" %d: %d\n", i, num_chunks);
459 g_assert (los_num_sections == num_sections);
463 sgen_ptr_is_in_los (char *ptr, char **start)
468 for (obj = los_object_list; obj; obj = obj->next) {
469 char *end = obj->data + obj->size;
471 if (ptr >= obj->data && ptr < end) {
480 sgen_los_iterate_objects (IterateObjectCallbackFunc cb, void *user_data)
484 for (obj = los_object_list; obj; obj = obj->next)
485 cb (obj->data, obj->size, user_data);
489 sgen_los_is_valid_object (char *object)
493 for (obj = los_object_list; obj; obj = obj->next) {
494 if (obj->data == object)
501 mono_sgen_los_describe_pointer (char *ptr)
505 for (obj = los_object_list; obj; obj = obj->next) {
506 const char *los_kind;
510 if (obj->data > ptr || obj->data + obj->size <= ptr)
513 size = sgen_los_object_size (obj);
514 pinned = sgen_los_object_is_pinned (obj->data);
516 if (size > LOS_SECTION_OBJECT_LIMIT)
517 los_kind = "huge-los-ptr";
519 los_kind = "los-ptr";
521 if (obj->data == ptr) {
522 SGEN_LOG (0, "%s (size %d pin %d)\n", los_kind, (int)size, pinned ? 1 : 0);
524 SGEN_LOG (0, "%s (interior-ptr offset %td size %d pin %d)",
525 los_kind, ptr - obj->data, (int)size, pinned ? 1 : 0);
534 sgen_los_iterate_live_block_ranges (sgen_cardtable_block_callback callback)
537 for (obj = los_object_list; obj; obj = obj->next) {
538 MonoVTable *vt = (MonoVTable*)SGEN_LOAD_VTABLE (obj->data);
539 if (SGEN_VTABLE_HAS_REFERENCES (vt))
540 callback ((mword)obj->data, (mword)obj->size);
545 sgen_los_scan_card_table (gboolean mod_union, SgenGrayQueue *queue)
549 for (obj = los_object_list; obj; obj = obj->next) {
552 if (!SGEN_OBJECT_HAS_REFERENCES (obj->data))
556 cards = obj->cardtable_mod_union;
562 sgen_cardtable_scan_object (obj->data, obj->size, cards, mod_union, queue);
567 sgen_los_count_cards (long long *num_total_cards, long long *num_marked_cards)
570 long long total_cards = 0;
571 long long marked_cards = 0;
573 for (obj = los_object_list; obj; obj = obj->next) {
575 guint8 *cards = sgen_card_table_get_card_scan_address ((mword) obj->data);
576 guint8 *cards_end = sgen_card_table_get_card_scan_address ((mword) obj->data + obj->size - 1);
577 mword num_cards = (cards_end - cards) + 1;
579 if (!SGEN_OBJECT_HAS_REFERENCES (obj->data))
582 total_cards += num_cards;
583 for (i = 0; i < num_cards; ++i) {
589 *num_total_cards = total_cards;
590 *num_marked_cards = marked_cards;
594 sgen_los_update_cardtable_mod_union (void)
598 for (obj = los_object_list; obj; obj = obj->next) {
599 if (!SGEN_OBJECT_HAS_REFERENCES (obj->data))
601 obj->cardtable_mod_union = sgen_card_table_update_mod_union (obj->cardtable_mod_union,
602 obj->data, obj->size, NULL);
607 sgen_los_object_size (LOSObject *obj)
609 return obj->size & ~1L;
613 sgen_los_header_for_object (char *data)
616 return (LOSObject*)(data - (int)(&(((LOSObject*)0)->data)));
618 return (LOSObject*)(data - sizeof (LOSObject));
623 sgen_los_pin_object (char *data)
625 LOSObject *obj = sgen_los_header_for_object (data);
626 obj->size = obj->size | 1;
627 binary_protocol_pin (data, (gpointer)SGEN_LOAD_VTABLE (data), sgen_safe_object_get_size ((MonoObject*)data));
631 sgen_los_unpin_object (char *data)
633 LOSObject *obj = sgen_los_header_for_object (data);
634 obj->size = sgen_los_object_size (obj);
638 sgen_los_object_is_pinned (char *data)
640 LOSObject *obj = sgen_los_header_for_object (data);
641 return obj->size & 1;
644 #endif /* HAVE_SGEN_GC */