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;
95 #ifdef LOS_CONSISTENCY_CHECK
97 los_consistency_check (void)
102 mword memory_usage = 0;
104 for (obj = los_object_list; obj; obj = obj->next) {
105 char *end = obj->data + obj->size;
106 int start_index, num_chunks;
108 memory_usage += obj->size;
110 if (obj->size > LOS_SECTION_OBJECT_LIMIT)
113 section = LOS_SECTION_FOR_OBJ (obj);
115 g_assert (end <= (char*)section + LOS_SECTION_SIZE);
117 start_index = LOS_CHUNK_INDEX (obj, section);
118 num_chunks = (obj->size + sizeof (LOSObject) + LOS_CHUNK_SIZE - 1) >> LOS_CHUNK_BITS;
119 for (i = start_index; i < start_index + num_chunks; ++i)
120 g_assert (!section->free_chunk_map [i]);
123 for (i = 0; i < LOS_NUM_FAST_SIZES; ++i) {
124 LOSFreeChunks *size_chunks;
125 for (size_chunks = los_fast_free_lists [i]; size_chunks; size_chunks = size_chunks->next_size) {
126 LOSSection *section = LOS_SECTION_FOR_OBJ (size_chunks);
127 int j, num_chunks, start_index;
130 g_assert (size_chunks->size >= LOS_NUM_FAST_SIZES * LOS_CHUNK_SIZE);
132 g_assert (size_chunks->size == i * LOS_CHUNK_SIZE);
134 num_chunks = size_chunks->size >> LOS_CHUNK_BITS;
135 start_index = LOS_CHUNK_INDEX (size_chunks, section);
136 for (j = start_index; j < start_index + num_chunks; ++j)
137 g_assert (section->free_chunk_map [j]);
141 g_assert (los_memory_usage == memory_usage);
146 add_free_chunk (LOSFreeChunks *free_chunks, size_t size)
148 size_t num_chunks = size >> LOS_CHUNK_BITS;
150 free_chunks->size = size;
152 if (num_chunks >= LOS_NUM_FAST_SIZES)
154 free_chunks->next_size = los_fast_free_lists [num_chunks];
155 los_fast_free_lists [num_chunks] = free_chunks;
158 static LOSFreeChunks*
159 get_from_size_list (LOSFreeChunks **list, size_t size)
161 LOSFreeChunks *free_chunks = NULL;
163 size_t i, num_chunks, start_index;
166 g_assert ((size & (LOS_CHUNK_SIZE - 1)) == 0);
170 if (free_chunks->size >= size)
172 list = &(*list)->next_size;
178 *list = free_chunks->next_size;
180 if (free_chunks->size > size)
181 add_free_chunk ((LOSFreeChunks*)((char*)free_chunks + size), free_chunks->size - size);
183 num_chunks = size >> LOS_CHUNK_BITS;
185 section = LOS_SECTION_FOR_OBJ (free_chunks);
187 start_index = LOS_CHUNK_INDEX (free_chunks, section);
188 for (i = start_index; i < start_index + num_chunks; ++i) {
189 g_assert (section->free_chunk_map [i]);
190 section->free_chunk_map [i] = 0;
193 section->num_free_chunks -= size >> LOS_CHUNK_BITS;
194 g_assert (section->num_free_chunks >= 0);
200 get_los_section_memory (size_t size)
203 LOSFreeChunks *free_chunks;
206 size += LOS_CHUNK_SIZE - 1;
207 size &= ~(LOS_CHUNK_SIZE - 1);
209 num_chunks = size >> LOS_CHUNK_BITS;
211 g_assert (size > 0 && size - sizeof (LOSObject) <= LOS_SECTION_OBJECT_LIMIT);
212 g_assert (num_chunks > 0);
215 if (num_chunks >= LOS_NUM_FAST_SIZES) {
216 free_chunks = get_from_size_list (&los_fast_free_lists [0], size);
219 for (i = num_chunks; i < LOS_NUM_FAST_SIZES; ++i) {
220 free_chunks = get_from_size_list (&los_fast_free_lists [i], size);
225 free_chunks = get_from_size_list (&los_fast_free_lists [0], size);
229 return (LOSObject*)free_chunks;
231 if (!sgen_memgov_try_alloc_space (LOS_SECTION_SIZE, SPACE_LOS))
234 section = sgen_alloc_os_memory_aligned (LOS_SECTION_SIZE, LOS_SECTION_SIZE, SGEN_ALLOC_HEAP | SGEN_ALLOC_ACTIVATE, NULL);
239 free_chunks = (LOSFreeChunks*)((char*)section + LOS_CHUNK_SIZE);
240 free_chunks->size = LOS_SECTION_SIZE - LOS_CHUNK_SIZE;
241 free_chunks->next_size = los_fast_free_lists [0];
242 los_fast_free_lists [0] = free_chunks;
244 section->num_free_chunks = LOS_SECTION_NUM_CHUNKS;
246 section->free_chunk_map = (unsigned char*)section + sizeof (LOSSection);
247 g_assert (sizeof (LOSSection) + LOS_SECTION_NUM_CHUNKS + 1 <= LOS_CHUNK_SIZE);
248 section->free_chunk_map [0] = 0;
249 memset (section->free_chunk_map + 1, 1, LOS_SECTION_NUM_CHUNKS);
251 section->next = los_sections;
252 los_sections = section;
260 free_los_section_memory (LOSObject *obj, size_t size)
262 LOSSection *section = LOS_SECTION_FOR_OBJ (obj);
263 size_t num_chunks, i, start_index;
265 size += LOS_CHUNK_SIZE - 1;
266 size &= ~(LOS_CHUNK_SIZE - 1);
268 num_chunks = size >> LOS_CHUNK_BITS;
270 g_assert (size > 0 && size - sizeof (LOSObject) <= LOS_SECTION_OBJECT_LIMIT);
271 g_assert (num_chunks > 0);
273 section->num_free_chunks += num_chunks;
274 g_assert (section->num_free_chunks <= LOS_SECTION_NUM_CHUNKS);
277 * We could free the LOS section here if it's empty, but we
278 * can't unless we also remove its free chunks from the fast
279 * free lists. Instead, we do it in los_sweep().
282 start_index = LOS_CHUNK_INDEX (obj, section);
283 for (i = start_index; i < start_index + num_chunks; ++i) {
284 g_assert (!section->free_chunk_map [i]);
285 section->free_chunk_map [i] = 1;
288 add_free_chunk ((LOSFreeChunks*)obj, size);
294 sgen_los_free_object (LOSObject *obj)
296 SGEN_ASSERT (0, !obj->cardtable_mod_union, "We should never free a LOS object with a mod-union table.");
299 size_t size = obj->size;
300 SGEN_LOG (4, "Freed large object %p, size %lu", obj->data, (unsigned long)obj->size);
301 binary_protocol_empty (obj->data, obj->size);
303 los_memory_usage -= size;
309 if (size > LOS_SECTION_OBJECT_LIMIT) {
311 pagesize = mono_pagesize ();
312 size += sizeof (LOSObject);
313 size += pagesize - 1;
314 size &= ~(pagesize - 1);
315 sgen_free_os_memory (obj, size, SGEN_ALLOC_HEAP);
316 sgen_memgov_release_space (size, SPACE_LOS);
318 free_los_section_memory (obj, size + sizeof (LOSObject));
319 #ifdef LOS_CONSISTENCY_CHECKS
320 los_consistency_check ();
328 * Objects with size >= MAX_SMALL_SIZE are allocated in the large object space.
329 * They are currently kept track of with a linked list.
330 * They don't move, so there is no need to pin them during collection
331 * and we avoid the memcpy overhead.
334 sgen_los_alloc_large_inner (GCVTable *vtable, size_t size)
336 LOSObject *obj = NULL;
339 g_assert (size > SGEN_MAX_SMALL_OBJ_SIZE);
340 g_assert ((size & 1) == 0);
343 * size + sizeof (LOSObject) <= SSIZE_MAX - (mono_pagesize () - 1)
347 * size <= SSIZE_MAX - (mono_pagesize () - 1) - sizeof (LOSObject)
349 if (size > SSIZE_MAX - (mono_pagesize () - 1) - sizeof (LOSObject))
354 los_segment = sgen_alloc_os_memory (LOS_SEGMENT_SIZE, SGEN_ALLOC_HEAP | SGEN_ALLOC_ACTIVATE, NULL);
355 los_segment_index = ALIGN_UP (los_segment_index);
357 obj = (LOSObject*)(los_segment + los_segment_index);
358 los_segment_index += size + sizeof (LOSObject);
359 g_assert (los_segment_index <= LOS_SEGMENT_SIZE);
361 sgen_ensure_free_space (size);
364 obj = malloc (size + sizeof (LOSObject));
365 memset (obj, 0, size + sizeof (LOSObject));
367 if (size > LOS_SECTION_OBJECT_LIMIT) {
368 size_t alloc_size = size;
370 pagesize = mono_pagesize ();
371 alloc_size += sizeof (LOSObject);
372 alloc_size += pagesize - 1;
373 alloc_size &= ~(pagesize - 1);
374 if (sgen_memgov_try_alloc_space (alloc_size, SPACE_LOS)) {
375 obj = sgen_alloc_os_memory (alloc_size, SGEN_ALLOC_HEAP | SGEN_ALLOC_ACTIVATE, NULL);
378 obj = get_los_section_memory (size + sizeof (LOSObject));
380 memset (obj, 0, size + sizeof (LOSObject));
386 g_assert (!((mword)obj->data & (SGEN_ALLOC_ALIGN - 1)));
388 vtslot = (void**)obj->data;
390 sgen_update_heap_boundaries ((mword)obj->data, (mword)obj->data + size);
391 obj->next = los_object_list;
392 los_object_list = obj;
393 los_memory_usage += size;
395 SGEN_LOG (4, "Allocated large object %p, vtable: %p (%s), size: %zd", obj->data, vtable, sgen_client_vtable_get_name (vtable), size);
396 binary_protocol_alloc (obj->data, vtable, size, sgen_client_get_provenance ());
398 #ifdef LOS_CONSISTENCY_CHECK
399 los_consistency_check ();
405 static void sgen_los_unpin_object (char *data);
408 sgen_los_sweep (void)
410 LOSObject *bigobj, *prevbo;
411 LOSSection *section, *prev;
413 int num_sections = 0;
415 /* sweep the big objects list */
417 for (bigobj = los_object_list; bigobj;) {
418 SGEN_ASSERT (0, !SGEN_OBJECT_IS_PINNED (bigobj->data), "Who pinned a LOS object?");
420 if (bigobj->cardtable_mod_union) {
421 sgen_card_table_free_mod_union (bigobj->cardtable_mod_union, bigobj->data, bigobj->size);
422 bigobj->cardtable_mod_union = NULL;
425 if (sgen_los_object_is_pinned (bigobj->data)) {
426 sgen_los_unpin_object (bigobj->data);
427 sgen_update_heap_boundaries ((mword)bigobj->data, (mword)bigobj->data + sgen_los_object_size (bigobj));
430 /* not referenced anywhere, so we can free it */
432 prevbo->next = bigobj->next;
434 los_object_list = bigobj->next;
436 bigobj = bigobj->next;
437 sgen_los_free_object (to_free);
441 bigobj = bigobj->next;
444 /* Try to free memory */
445 for (i = 0; i < LOS_NUM_FAST_SIZES; ++i)
446 los_fast_free_lists [i] = NULL;
449 section = los_sections;
451 if (section->num_free_chunks == LOS_SECTION_NUM_CHUNKS) {
452 LOSSection *next = section->next;
457 sgen_free_os_memory (section, LOS_SECTION_SIZE, SGEN_ALLOC_HEAP);
458 sgen_memgov_release_space (LOS_SECTION_SIZE, SPACE_LOS);
464 for (i = 0; i <= LOS_SECTION_NUM_CHUNKS; ++i) {
465 if (section->free_chunk_map [i]) {
467 for (j = i + 1; j <= LOS_SECTION_NUM_CHUNKS && section->free_chunk_map [j]; ++j)
469 add_free_chunk ((LOSFreeChunks*)((char*)section + (i << LOS_CHUNK_BITS)), (j - i) << LOS_CHUNK_BITS);
475 section = section->next;
480 #ifdef LOS_CONSISTENCY_CHECK
481 los_consistency_check ();
485 g_print ("LOS sections: %d objects: %d usage: %d\n", num_sections, los_num_objects, los_memory_usage);
486 for (i = 0; i < LOS_NUM_FAST_SIZES; ++i) {
488 LOSFreeChunks *free_chunks;
489 for (free_chunks = los_fast_free_lists [i]; free_chunks; free_chunks = free_chunks->next_size)
491 g_print (" %d: %d\n", i, num_chunks);
495 g_assert (los_num_sections == num_sections);
499 sgen_ptr_is_in_los (char *ptr, char **start)
504 for (obj = los_object_list; obj; obj = obj->next) {
505 char *end = obj->data + obj->size;
507 if (ptr >= obj->data && ptr < end) {
516 sgen_los_iterate_objects (IterateObjectCallbackFunc cb, void *user_data)
520 for (obj = los_object_list; obj; obj = obj->next)
521 cb (obj->data, obj->size, user_data);
525 sgen_los_is_valid_object (char *object)
529 for (obj = los_object_list; obj; obj = obj->next) {
530 if (obj->data == object)
537 mono_sgen_los_describe_pointer (char *ptr)
541 for (obj = los_object_list; obj; obj = obj->next) {
542 const char *los_kind;
546 if (obj->data > ptr || obj->data + obj->size <= ptr)
549 size = sgen_los_object_size (obj);
550 pinned = sgen_los_object_is_pinned (obj->data);
552 if (size > LOS_SECTION_OBJECT_LIMIT)
553 los_kind = "huge-los-ptr";
555 los_kind = "los-ptr";
557 if (obj->data == ptr) {
558 SGEN_LOG (0, "%s (size %d pin %d)\n", los_kind, (int)size, pinned ? 1 : 0);
560 SGEN_LOG (0, "%s (interior-ptr offset %zd size %d pin %d)",
561 los_kind, ptr - obj->data, (int)size, pinned ? 1 : 0);
570 sgen_los_iterate_live_block_ranges (sgen_cardtable_block_callback callback)
573 for (obj = los_object_list; obj; obj = obj->next) {
574 GCVTable *vt = (GCVTable*)SGEN_LOAD_VTABLE (obj->data);
575 if (SGEN_VTABLE_HAS_REFERENCES (vt))
576 callback ((mword)obj->data, (mword)obj->size);
581 get_cardtable_mod_union_for_object (LOSObject *obj)
583 guint8 *mod_union = obj->cardtable_mod_union;
587 mod_union = sgen_card_table_alloc_mod_union (obj->data, obj->size);
588 other = SGEN_CAS_PTR ((gpointer*)&obj->cardtable_mod_union, mod_union, NULL);
590 SGEN_ASSERT (0, obj->cardtable_mod_union == mod_union, "Why did CAS not replace?");
593 sgen_card_table_free_mod_union (mod_union, obj->data, obj->size);
598 sgen_los_scan_card_table (gboolean mod_union, ScanCopyContext ctx)
602 for (obj = los_object_list; obj; obj = obj->next) {
605 if (!SGEN_OBJECT_HAS_REFERENCES (obj->data))
609 if (!sgen_los_object_is_pinned (obj->data))
612 cards = get_cardtable_mod_union_for_object (obj);
618 sgen_cardtable_scan_object (obj->data, obj->size, cards, mod_union, ctx);
623 sgen_los_count_cards (long long *num_total_cards, long long *num_marked_cards)
626 long long total_cards = 0;
627 long long marked_cards = 0;
629 for (obj = los_object_list; obj; obj = obj->next) {
631 guint8 *cards = sgen_card_table_get_card_scan_address ((mword) obj->data);
632 guint8 *cards_end = sgen_card_table_get_card_scan_address ((mword) obj->data + obj->size - 1);
633 mword num_cards = (cards_end - cards) + 1;
635 if (!SGEN_OBJECT_HAS_REFERENCES (obj->data))
638 total_cards += num_cards;
639 for (i = 0; i < num_cards; ++i) {
645 *num_total_cards = total_cards;
646 *num_marked_cards = marked_cards;
650 sgen_los_update_cardtable_mod_union (void)
654 for (obj = los_object_list; obj; obj = obj->next) {
655 if (!SGEN_OBJECT_HAS_REFERENCES (obj->data))
657 sgen_card_table_update_mod_union (get_cardtable_mod_union_for_object (obj),
658 obj->data, obj->size, NULL);
663 sgen_los_object_size (LOSObject *obj)
665 return obj->size & ~1L;
669 sgen_los_header_for_object (char *data)
672 return (LOSObject*)(data - (int)(&(((LOSObject*)0)->data)));
674 return (LOSObject*)(data - sizeof (LOSObject));
679 sgen_los_pin_object (char *data)
681 LOSObject *obj = sgen_los_header_for_object (data);
682 obj->size = obj->size | 1;
683 binary_protocol_pin (data, (gpointer)SGEN_LOAD_VTABLE (data), sgen_safe_object_get_size ((GCObject*)data));
687 sgen_los_unpin_object (char *data)
689 LOSObject *obj = sgen_los_header_for_object (data);
690 obj->size = sgen_los_object_size (obj);
694 sgen_los_object_is_pinned (char *data)
696 LOSObject *obj = sgen_los_header_for_object (data);
697 return obj->size & 1;
701 sgen_los_mark_mod_union_card (GCObject *mono_obj, void **ptr)
703 LOSObject *obj = sgen_los_header_for_object ((char*)mono_obj);
704 guint8 *mod_union = get_cardtable_mod_union_for_object (obj);
705 size_t offset = sgen_card_table_get_card_offset ((char*)ptr, (char*)sgen_card_table_align_pointer ((char*)obj));
706 SGEN_ASSERT (0, mod_union, "FIXME: optionally allocate the mod union if it's not here and CAS it in.");
707 SGEN_ASSERT (0, (char*)obj == (char*)sgen_card_table_align_pointer ((char*)obj), "Why are LOS objects not card aligned?");
708 mod_union [offset] = 1;
711 #endif /* HAVE_SGEN_GC */