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.
38 #include "mono/sgen/sgen-gc.h"
39 #include "mono/sgen/sgen-protocol.h"
40 #include "mono/sgen/sgen-cardtable.h"
41 #include "mono/sgen/sgen-memory-governor.h"
42 #include "mono/sgen/sgen-client.h"
44 #define LOS_SECTION_SIZE (1024 * 1024)
47 * This shouldn't be much smaller or larger than MAX_SMALL_OBJ_SIZE.
48 * Must be at least sizeof (LOSSection).
50 #define LOS_CHUNK_SIZE 4096
51 #define LOS_CHUNK_BITS 12
53 /* Largest object that can be allocated in a section. */
54 #define LOS_SECTION_OBJECT_LIMIT (LOS_SECTION_SIZE - LOS_CHUNK_SIZE - sizeof (LOSObject))
55 //#define LOS_SECTION_OBJECT_LIMIT 0
56 #define LOS_SECTION_NUM_CHUNKS ((LOS_SECTION_SIZE >> LOS_CHUNK_BITS) - 1)
58 #define LOS_SECTION_FOR_OBJ(obj) ((LOSSection*)((mword)(obj) & ~(mword)(LOS_SECTION_SIZE - 1)))
59 #define LOS_CHUNK_INDEX(obj,section) (((char*)(obj) - (char*)(section)) >> LOS_CHUNK_BITS)
61 #define LOS_NUM_FAST_SIZES 32
63 typedef struct _LOSFreeChunks LOSFreeChunks;
64 struct _LOSFreeChunks {
65 LOSFreeChunks *next_size;
69 typedef struct _LOSSection LOSSection;
72 size_t num_free_chunks;
73 unsigned char *free_chunk_map;
76 LOSObject *los_object_list = NULL;
77 mword los_memory_usage = 0;
79 static LOSSection *los_sections = NULL;
80 static LOSFreeChunks *los_fast_free_lists [LOS_NUM_FAST_SIZES]; /* 0 is for larger sizes */
81 static mword los_num_objects = 0;
82 static int los_num_sections = 0;
85 //#define LOS_CONSISTENCY_CHECK
89 #define LOS_SEGMENT_SIZE (4096 * 1024)
91 static char *los_segment = NULL;
92 static int los_segment_index = 0;
96 sgen_los_object_size (LOSObject *obj)
98 return obj->size & ~1L;
101 #ifdef LOS_CONSISTENCY_CHECK
103 los_consistency_check (void)
108 mword memory_usage = 0;
110 for (obj = los_object_list; obj; obj = obj->next) {
111 mword obj_size = sgen_los_object_size (obj);
112 char *end = obj->data + obj_size;
113 int start_index, num_chunks;
115 memory_usage += obj_size;
117 if (obj_size > LOS_SECTION_OBJECT_LIMIT)
120 section = LOS_SECTION_FOR_OBJ (obj);
122 g_assert (end <= (char*)section + LOS_SECTION_SIZE);
124 start_index = LOS_CHUNK_INDEX (obj, section);
125 num_chunks = (obj_size + sizeof (LOSObject) + LOS_CHUNK_SIZE - 1) >> LOS_CHUNK_BITS;
126 for (i = start_index; i < start_index + num_chunks; ++i)
127 g_assert (!section->free_chunk_map [i]);
130 for (i = 0; i < LOS_NUM_FAST_SIZES; ++i) {
131 LOSFreeChunks *size_chunks;
132 for (size_chunks = los_fast_free_lists [i]; size_chunks; size_chunks = size_chunks->next_size) {
133 LOSSection *section = LOS_SECTION_FOR_OBJ (size_chunks);
134 int j, num_chunks, start_index;
137 g_assert (size_chunks->size >= LOS_NUM_FAST_SIZES * LOS_CHUNK_SIZE);
139 g_assert (size_chunks->size == i * LOS_CHUNK_SIZE);
141 num_chunks = size_chunks->size >> LOS_CHUNK_BITS;
142 start_index = LOS_CHUNK_INDEX (size_chunks, section);
143 for (j = start_index; j < start_index + num_chunks; ++j)
144 g_assert (section->free_chunk_map [j]);
148 g_assert (los_memory_usage == memory_usage);
153 add_free_chunk (LOSFreeChunks *free_chunks, size_t size)
155 size_t num_chunks = size >> LOS_CHUNK_BITS;
157 free_chunks->size = size;
159 if (num_chunks >= LOS_NUM_FAST_SIZES)
161 free_chunks->next_size = los_fast_free_lists [num_chunks];
162 los_fast_free_lists [num_chunks] = free_chunks;
165 static LOSFreeChunks*
166 get_from_size_list (LOSFreeChunks **list, size_t size)
168 LOSFreeChunks *free_chunks = NULL;
170 size_t i, num_chunks, start_index;
173 g_assert ((size & (LOS_CHUNK_SIZE - 1)) == 0);
177 if (free_chunks->size >= size)
179 list = &(*list)->next_size;
185 *list = free_chunks->next_size;
187 if (free_chunks->size > size)
188 add_free_chunk ((LOSFreeChunks*)((char*)free_chunks + size), free_chunks->size - size);
190 num_chunks = size >> LOS_CHUNK_BITS;
192 section = LOS_SECTION_FOR_OBJ (free_chunks);
194 start_index = LOS_CHUNK_INDEX (free_chunks, section);
195 for (i = start_index; i < start_index + num_chunks; ++i) {
196 g_assert (section->free_chunk_map [i]);
197 section->free_chunk_map [i] = 0;
200 section->num_free_chunks -= size >> LOS_CHUNK_BITS;
201 g_assert (section->num_free_chunks >= 0);
207 get_los_section_memory (size_t size)
210 LOSFreeChunks *free_chunks;
213 size += LOS_CHUNK_SIZE - 1;
214 size &= ~(LOS_CHUNK_SIZE - 1);
216 num_chunks = size >> LOS_CHUNK_BITS;
218 g_assert (size > 0 && size - sizeof (LOSObject) <= LOS_SECTION_OBJECT_LIMIT);
219 g_assert (num_chunks > 0);
222 if (num_chunks >= LOS_NUM_FAST_SIZES) {
223 free_chunks = get_from_size_list (&los_fast_free_lists [0], size);
226 for (i = num_chunks; i < LOS_NUM_FAST_SIZES; ++i) {
227 free_chunks = get_from_size_list (&los_fast_free_lists [i], size);
232 free_chunks = get_from_size_list (&los_fast_free_lists [0], size);
236 return (LOSObject*)free_chunks;
238 if (!sgen_memgov_try_alloc_space (LOS_SECTION_SIZE, SPACE_LOS))
241 section = (LOSSection *)sgen_alloc_os_memory_aligned (LOS_SECTION_SIZE, LOS_SECTION_SIZE, (SgenAllocFlags)(SGEN_ALLOC_HEAP | SGEN_ALLOC_ACTIVATE), NULL);
246 free_chunks = (LOSFreeChunks*)((char*)section + LOS_CHUNK_SIZE);
247 free_chunks->size = LOS_SECTION_SIZE - LOS_CHUNK_SIZE;
248 free_chunks->next_size = los_fast_free_lists [0];
249 los_fast_free_lists [0] = free_chunks;
251 section->num_free_chunks = LOS_SECTION_NUM_CHUNKS;
253 section->free_chunk_map = (unsigned char*)section + sizeof (LOSSection);
254 g_assert (sizeof (LOSSection) + LOS_SECTION_NUM_CHUNKS + 1 <= LOS_CHUNK_SIZE);
255 section->free_chunk_map [0] = 0;
256 memset (section->free_chunk_map + 1, 1, LOS_SECTION_NUM_CHUNKS);
258 section->next = los_sections;
259 los_sections = section;
267 free_los_section_memory (LOSObject *obj, size_t size)
269 LOSSection *section = LOS_SECTION_FOR_OBJ (obj);
270 size_t num_chunks, i, start_index;
272 size += LOS_CHUNK_SIZE - 1;
273 size &= ~(LOS_CHUNK_SIZE - 1);
275 num_chunks = size >> LOS_CHUNK_BITS;
277 g_assert (size > 0 && size - sizeof (LOSObject) <= LOS_SECTION_OBJECT_LIMIT);
278 g_assert (num_chunks > 0);
280 section->num_free_chunks += num_chunks;
281 g_assert (section->num_free_chunks <= LOS_SECTION_NUM_CHUNKS);
284 * We could free the LOS section here if it's empty, but we
285 * can't unless we also remove its free chunks from the fast
286 * free lists. Instead, we do it in los_sweep().
289 start_index = LOS_CHUNK_INDEX (obj, section);
290 for (i = start_index; i < start_index + num_chunks; ++i) {
291 g_assert (!section->free_chunk_map [i]);
292 section->free_chunk_map [i] = 1;
295 add_free_chunk ((LOSFreeChunks*)obj, size);
301 sgen_los_free_object (LOSObject *obj)
303 SGEN_ASSERT (0, !obj->cardtable_mod_union, "We should never free a LOS object with a mod-union table.");
306 mword size = sgen_los_object_size (obj);
307 SGEN_LOG (4, "Freed large object %p, size %lu", obj->data, (unsigned long)size);
308 binary_protocol_empty (obj->data, size);
310 los_memory_usage -= size;
316 if (size > LOS_SECTION_OBJECT_LIMIT) {
318 pagesize = mono_pagesize ();
319 size += sizeof (LOSObject);
320 size += pagesize - 1;
321 size &= ~(pagesize - 1);
322 sgen_free_os_memory (obj, size, SGEN_ALLOC_HEAP);
323 sgen_memgov_release_space (size, SPACE_LOS);
325 free_los_section_memory (obj, size + sizeof (LOSObject));
326 #ifdef LOS_CONSISTENCY_CHECKS
327 los_consistency_check ();
335 * Objects with size >= MAX_SMALL_SIZE are allocated in the large object space.
336 * They are currently kept track of with a linked list.
337 * They don't move, so there is no need to pin them during collection
338 * and we avoid the memcpy overhead.
341 sgen_los_alloc_large_inner (GCVTable vtable, size_t size)
343 LOSObject *obj = NULL;
346 g_assert (size > SGEN_MAX_SMALL_OBJ_SIZE);
347 g_assert ((size & 1) == 0);
350 * size + sizeof (LOSObject) <= SSIZE_MAX - (mono_pagesize () - 1)
354 * size <= SSIZE_MAX - (mono_pagesize () - 1) - sizeof (LOSObject)
356 if (size > SSIZE_MAX - (mono_pagesize () - 1) - sizeof (LOSObject))
361 los_segment = sgen_alloc_os_memory (LOS_SEGMENT_SIZE, SGEN_ALLOC_HEAP | SGEN_ALLOC_ACTIVATE, NULL);
362 los_segment_index = ALIGN_UP (los_segment_index);
364 obj = (LOSObject*)(los_segment + los_segment_index);
365 los_segment_index += size + sizeof (LOSObject);
366 g_assert (los_segment_index <= LOS_SEGMENT_SIZE);
368 sgen_ensure_free_space (size);
371 obj = malloc (size + sizeof (LOSObject));
372 memset (obj, 0, size + sizeof (LOSObject));
374 if (size > LOS_SECTION_OBJECT_LIMIT) {
375 size_t alloc_size = size;
377 pagesize = mono_pagesize ();
378 alloc_size += sizeof (LOSObject);
379 alloc_size += pagesize - 1;
380 alloc_size &= ~(pagesize - 1);
381 if (sgen_memgov_try_alloc_space (alloc_size, SPACE_LOS)) {
382 obj = (LOSObject *)sgen_alloc_os_memory (alloc_size, (SgenAllocFlags)(SGEN_ALLOC_HEAP | SGEN_ALLOC_ACTIVATE), NULL);
385 obj = get_los_section_memory (size + sizeof (LOSObject));
387 memset (obj, 0, size + sizeof (LOSObject));
393 g_assert (!((mword)obj->data & (SGEN_ALLOC_ALIGN - 1)));
395 vtslot = (void**)obj->data;
397 sgen_update_heap_boundaries ((mword)obj->data, (mword)obj->data + size);
398 obj->next = los_object_list;
399 los_object_list = obj;
400 los_memory_usage += size;
402 SGEN_LOG (4, "Allocated large object %p, vtable: %p (%s), size: %zd", obj->data, vtable, sgen_client_vtable_get_name (vtable), size);
403 binary_protocol_alloc (obj->data, vtable, size, sgen_client_get_provenance ());
405 #ifdef LOS_CONSISTENCY_CHECK
406 los_consistency_check ();
412 static void sgen_los_unpin_object (GCObject *data);
415 sgen_los_sweep (void)
417 LOSObject *bigobj, *prevbo;
418 LOSSection *section, *prev;
420 int num_sections = 0;
422 /* sweep the big objects list */
424 for (bigobj = los_object_list; bigobj;) {
425 SGEN_ASSERT (0, !SGEN_OBJECT_IS_PINNED (bigobj->data), "Who pinned a LOS object?");
427 if (bigobj->cardtable_mod_union) {
428 sgen_card_table_free_mod_union (bigobj->cardtable_mod_union, (char*)bigobj->data, sgen_los_object_size (bigobj));
429 bigobj->cardtable_mod_union = NULL;
432 if (sgen_los_object_is_pinned (bigobj->data)) {
433 sgen_los_unpin_object (bigobj->data);
434 sgen_update_heap_boundaries ((mword)bigobj->data, (mword)bigobj->data + sgen_los_object_size (bigobj));
437 /* not referenced anywhere, so we can free it */
439 prevbo->next = bigobj->next;
441 los_object_list = bigobj->next;
443 bigobj = bigobj->next;
444 sgen_los_free_object (to_free);
448 bigobj = bigobj->next;
451 /* Try to free memory */
452 for (i = 0; i < LOS_NUM_FAST_SIZES; ++i)
453 los_fast_free_lists [i] = NULL;
456 section = los_sections;
458 if (section->num_free_chunks == LOS_SECTION_NUM_CHUNKS) {
459 LOSSection *next = section->next;
464 sgen_free_os_memory (section, LOS_SECTION_SIZE, SGEN_ALLOC_HEAP);
465 sgen_memgov_release_space (LOS_SECTION_SIZE, SPACE_LOS);
471 for (i = 0; i <= LOS_SECTION_NUM_CHUNKS; ++i) {
472 if (section->free_chunk_map [i]) {
474 for (j = i + 1; j <= LOS_SECTION_NUM_CHUNKS && section->free_chunk_map [j]; ++j)
476 add_free_chunk ((LOSFreeChunks*)((char*)section + (i << LOS_CHUNK_BITS)), (j - i) << LOS_CHUNK_BITS);
482 section = section->next;
487 #ifdef LOS_CONSISTENCY_CHECK
488 los_consistency_check ();
492 g_print ("LOS sections: %d objects: %d usage: %d\n", num_sections, los_num_objects, los_memory_usage);
493 for (i = 0; i < LOS_NUM_FAST_SIZES; ++i) {
495 LOSFreeChunks *free_chunks;
496 for (free_chunks = los_fast_free_lists [i]; free_chunks; free_chunks = free_chunks->next_size)
498 g_print (" %d: %d\n", i, num_chunks);
502 g_assert (los_num_sections == num_sections);
506 sgen_ptr_is_in_los (char *ptr, char **start)
511 for (obj = los_object_list; obj; obj = obj->next) {
512 char *end = (char*)obj->data + sgen_los_object_size (obj);
514 if (ptr >= (char*)obj->data && ptr < end) {
515 *start = (char*)obj->data;
523 sgen_los_iterate_objects (IterateObjectCallbackFunc cb, void *user_data)
527 for (obj = los_object_list; obj; obj = obj->next)
528 cb (obj->data, sgen_los_object_size (obj), user_data);
532 sgen_los_is_valid_object (char *object)
536 for (obj = los_object_list; obj; obj = obj->next) {
537 if ((char*)obj->data == object)
544 mono_sgen_los_describe_pointer (char *ptr)
548 for (obj = los_object_list; obj; obj = obj->next) {
549 const char *los_kind;
553 if ((char*)obj->data > ptr || (char*)obj->data + sgen_los_object_size (obj) <= ptr)
556 size = sgen_los_object_size (obj);
557 pinned = sgen_los_object_is_pinned (obj->data);
559 if (size > LOS_SECTION_OBJECT_LIMIT)
560 los_kind = "huge-los-ptr";
562 los_kind = "los-ptr";
564 if ((char*)obj->data == ptr) {
565 SGEN_LOG (0, "%s (size %d pin %d)\n", los_kind, (int)size, pinned ? 1 : 0);
567 SGEN_LOG (0, "%s (interior-ptr offset %zd size %d pin %d)",
568 los_kind, ptr - (char*)obj->data, (int)size, pinned ? 1 : 0);
577 sgen_los_iterate_live_block_ranges (sgen_cardtable_block_callback callback)
580 for (obj = los_object_list; obj; obj = obj->next) {
581 GCVTable vt = SGEN_LOAD_VTABLE (obj->data);
582 if (SGEN_VTABLE_HAS_REFERENCES (vt))
583 callback ((mword)obj->data, sgen_los_object_size (obj));
588 get_cardtable_mod_union_for_object (LOSObject *obj)
590 mword size = sgen_los_object_size (obj);
591 guint8 *mod_union = obj->cardtable_mod_union;
595 mod_union = sgen_card_table_alloc_mod_union ((char*)obj->data, size);
596 other = (guint8 *)SGEN_CAS_PTR ((gpointer*)&obj->cardtable_mod_union, mod_union, NULL);
598 SGEN_ASSERT (0, obj->cardtable_mod_union == mod_union, "Why did CAS not replace?");
601 sgen_card_table_free_mod_union (mod_union, (char*)obj->data, size);
606 sgen_los_scan_card_table (gboolean mod_union, ScanCopyContext ctx)
610 for (obj = los_object_list; obj; obj = obj->next) {
613 if (!SGEN_OBJECT_HAS_REFERENCES (obj->data))
617 if (!sgen_los_object_is_pinned (obj->data))
620 cards = get_cardtable_mod_union_for_object (obj);
626 sgen_cardtable_scan_object (obj->data, sgen_los_object_size (obj), cards, mod_union, ctx);
631 sgen_los_count_cards (long long *num_total_cards, long long *num_marked_cards)
634 long long total_cards = 0;
635 long long marked_cards = 0;
637 for (obj = los_object_list; obj; obj = obj->next) {
639 guint8 *cards = sgen_card_table_get_card_scan_address ((mword) obj->data);
640 guint8 *cards_end = sgen_card_table_get_card_scan_address ((mword) obj->data + sgen_los_object_size (obj) - 1);
641 mword num_cards = (cards_end - cards) + 1;
643 if (!SGEN_OBJECT_HAS_REFERENCES (obj->data))
646 total_cards += num_cards;
647 for (i = 0; i < num_cards; ++i) {
653 *num_total_cards = total_cards;
654 *num_marked_cards = marked_cards;
658 sgen_los_update_cardtable_mod_union (void)
662 for (obj = los_object_list; obj; obj = obj->next) {
663 if (!SGEN_OBJECT_HAS_REFERENCES (obj->data))
665 sgen_card_table_update_mod_union (get_cardtable_mod_union_for_object (obj),
666 (char*)obj->data, sgen_los_object_size (obj), NULL);
671 sgen_los_header_for_object (GCObject *data)
674 return (LOSObject*)((char*)data - (int)(&(((LOSObject*)0)->data)));
676 return (LOSObject*)((char*)data - sizeof (LOSObject));
681 sgen_los_pin_object (GCObject *data)
683 LOSObject *obj = sgen_los_header_for_object (data);
684 obj->size = obj->size | 1;
685 binary_protocol_pin (data, (gpointer)SGEN_LOAD_VTABLE (data), sgen_safe_object_get_size (data));
689 sgen_los_unpin_object (GCObject *data)
691 LOSObject *obj = sgen_los_header_for_object (data);
692 obj->size = sgen_los_object_size (obj);
696 sgen_los_object_is_pinned (GCObject *data)
698 LOSObject *obj = sgen_los_header_for_object (data);
699 return obj->size & 1;
703 sgen_los_mark_mod_union_card (GCObject *mono_obj, void **ptr)
705 LOSObject *obj = sgen_los_header_for_object (mono_obj);
706 guint8 *mod_union = get_cardtable_mod_union_for_object (obj);
707 size_t offset = sgen_card_table_get_card_offset ((char*)ptr, (char*)sgen_card_table_align_pointer ((char*)obj));
708 SGEN_ASSERT (0, mod_union, "FIXME: optionally allocate the mod union if it's not here and CAS it in.");
709 SGEN_ASSERT (0, (char*)obj == (char*)sgen_card_table_align_pointer ((char*)obj), "Why are LOS objects not card aligned?");
710 mod_union [offset] = 1;
713 #endif /* HAVE_SGEN_GC */