2 * sgen-major-copying.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.
50 #include "utils/mono-counters.h"
51 #include "metadata/object-internals.h"
52 #include "metadata/profiler-private.h"
54 #include "metadata/sgen-gc.h"
55 #include "metadata/sgen-protocol.h"
59 #define MAJOR_SECTION_SIZE SGEN_PINNED_CHUNK_SIZE
60 #define BLOCK_FOR_OBJECT(o) SGEN_PINNED_CHUNK_FOR_PTR ((o))
61 #define MAJOR_SECTION_FOR_OBJECT(o) ((GCMemSection*)BLOCK_FOR_OBJECT ((o)))
63 #define MAJOR_OBJ_IS_IN_TO_SPACE(o) (MAJOR_SECTION_FOR_OBJECT ((o))->is_to_space)
65 static int num_major_sections
= 0;
67 static GCMemSection
*section_list
= NULL
;
69 static SgenInternalAllocator pinned_allocator
;
72 * used when moving the objects
74 static char *to_space_bumper
= NULL
;
75 static char *to_space_top
= NULL
;
76 static GCMemSection
*to_space_section
= NULL
;
78 /* we get this at init */
79 static int nursery_bits
;
80 static char *nursery_start
;
81 static char *nursery_end
;
83 #define ptr_in_nursery(p) (SGEN_PTR_IN_NURSERY ((p), nursery_bits, nursery_start, nursery_end))
85 #ifdef HEAVY_STATISTICS
86 static long stat_major_copy_object_failed_forwarded
= 0;
87 static long stat_major_copy_object_failed_pinned
= 0;
88 static long stat_major_copy_object_failed_large_pinned
= 0;
89 static long stat_major_copy_object_failed_to_space
= 0;
93 major_alloc_heap (mword nursery_size
, mword nursery_align
, int the_nursery_bits
)
96 nursery_start
= mono_sgen_alloc_os_memory_aligned (nursery_size
, nursery_align
, TRUE
);
98 nursery_start
= mono_sgen_alloc_os_memory (nursery_size
, TRUE
);
100 nursery_end
= nursery_start
+ nursery_size
;
101 nursery_bits
= the_nursery_bits
;
103 return nursery_start
;
107 obj_is_from_pinned_alloc (char *p
)
109 return BLOCK_FOR_OBJECT (p
)->role
== MEMORY_ROLE_PINNED
;
113 free_pinned_object (char *obj
, size_t size
)
115 mono_sgen_free_internal_full (&pinned_allocator
, obj
, size
, INTERNAL_MEM_MANAGED
);
119 * Allocate a new section of memory to be used as old generation.
122 alloc_major_section (void)
124 GCMemSection
*section
;
127 section
= mono_sgen_alloc_os_memory_aligned (MAJOR_SECTION_SIZE
, MAJOR_SECTION_SIZE
, TRUE
);
128 section
->next_data
= section
->data
= (char*)section
+ SGEN_SIZEOF_GC_MEM_SECTION
;
129 g_assert (!((mword
)section
->data
& 7));
130 section
->size
= MAJOR_SECTION_SIZE
- SGEN_SIZEOF_GC_MEM_SECTION
;
131 section
->end_data
= section
->data
+ section
->size
;
132 mono_sgen_update_heap_boundaries ((mword
)section
->data
, (mword
)section
->end_data
);
133 DEBUG (3, fprintf (gc_debug_file
, "New major heap section: (%p-%p), total: %zd\n", section
->data
, section
->end_data
, total_alloc
));
134 scan_starts
= (section
->size
+ SGEN_SCAN_START_SIZE
- 1) / SGEN_SCAN_START_SIZE
;
135 section
->scan_starts
= mono_sgen_alloc_internal_dynamic (sizeof (char*) * scan_starts
, INTERNAL_MEM_SCAN_STARTS
);
136 section
->num_scan_start
= scan_starts
;
137 section
->block
.role
= MEMORY_ROLE_GEN1
;
138 section
->is_to_space
= TRUE
;
140 /* add to the section list */
141 section
->block
.next
= section_list
;
142 section_list
= section
;
144 ++num_major_sections
;
150 free_major_section (GCMemSection
*section
)
152 DEBUG (3, fprintf (gc_debug_file
, "Freed major section %p (%p-%p)\n", section
, section
->data
, section
->end_data
));
153 mono_sgen_free_internal_dynamic (section
->scan_starts
,
154 (section
->size
+ SGEN_SCAN_START_SIZE
- 1) / SGEN_SCAN_START_SIZE
* sizeof (char*), INTERNAL_MEM_SCAN_STARTS
);
155 mono_sgen_free_os_memory (section
, MAJOR_SECTION_SIZE
);
157 --num_major_sections
;
161 new_to_space_section (void)
163 /* FIXME: if the current to_space_section is empty, we don't
164 have to allocate a new one */
166 to_space_section
= alloc_major_section ();
167 to_space_bumper
= to_space_section
->next_data
;
168 to_space_top
= to_space_section
->end_data
;
172 to_space_set_next_data (void)
174 g_assert (to_space_bumper
>= to_space_section
->next_data
&& to_space_bumper
<= to_space_section
->end_data
);
175 to_space_section
->next_data
= to_space_bumper
;
179 to_space_expand (void)
181 if (to_space_section
) {
182 g_assert (to_space_top
== to_space_section
->end_data
);
183 to_space_set_next_data ();
186 new_to_space_section ();
190 major_alloc_object (int size
, gboolean has_references
)
192 char *dest
= to_space_bumper
;
193 /* Make sure we have enough space available */
194 if (dest
+ size
> to_space_top
) {
196 (dest
) = to_space_bumper
;
197 DEBUG (8, g_assert (dest
+ size
<= to_space_top
));
199 to_space_bumper
+= size
;
200 DEBUG (8, g_assert (to_space_bumper
<= to_space_top
));
201 to_space_section
->scan_starts
[(dest
- (char*)to_space_section
->data
)/SGEN_SCAN_START_SIZE
] = dest
;
206 unset_to_space (void)
208 /* between collections the to_space_bumper is invalidated
209 because degraded allocations might occur, so we set it to
210 NULL, just to make it explicit */
211 to_space_bumper
= NULL
;
213 /* don't unset to_space_section if we implement the FIXME in
214 new_to_space_section */
215 to_space_section
= NULL
;
219 major_is_object_live (char *obj
)
224 if (ptr_in_nursery (obj
))
227 objsize
= SGEN_ALIGN_UP (mono_sgen_safe_object_get_size ((MonoObject
*)obj
));
230 if (objsize
> SGEN_MAX_SMALL_OBJ_SIZE
)
234 if (obj_is_from_pinned_alloc (obj
))
237 /* now we know it's in a major heap section */
238 return MAJOR_SECTION_FOR_OBJECT (obj
)->is_to_space
;
241 /* size is a multiple of ALLOC_ALIGN */
243 major_alloc_small_pinned_obj (size_t size
, gboolean has_references
)
245 return mono_sgen_alloc_internal_full (&pinned_allocator
, size
, INTERNAL_MEM_MANAGED
);
249 * size is already rounded up and we hold the GC lock.
252 major_alloc_degraded (MonoVTable
*vtable
, size_t size
)
254 GCMemSection
*section
;
256 g_assert (size
<= SGEN_MAX_SMALL_OBJ_SIZE
);
257 HEAVY_STAT (++stat_objects_alloced_degraded
);
258 HEAVY_STAT (stat_bytes_alloced_degraded
+= size
);
259 for (section
= section_list
; section
; section
= section
->block
.next
) {
260 if ((section
->end_data
- section
->next_data
) >= size
) {
261 p
= (void**)section
->next_data
;
266 section
= alloc_major_section ();
267 section
->is_to_space
= FALSE
;
268 /* FIXME: handle OOM */
269 p
= (void**)section
->next_data
;
270 mono_sgen_register_major_sections_alloced (1);
272 section
->next_data
+= size
;
273 DEBUG (3, fprintf (gc_debug_file
, "Allocated (degraded) object %p, vtable: %p (%s), size: %zd in section %p\n", p
, vtable
, vtable
->klass
->name
, size
, section
));
278 #include "sgen-major-copy-object.h"
281 major_copy_or_mark_object (void **obj_slot
, SgenGrayQueue
*queue
)
284 char *obj
= *obj_slot
;
287 DEBUG (9, g_assert (current_collection_generation
== GENERATION_OLD
));
289 HEAVY_STAT (++stat_copy_object_called_major
);
291 DEBUG (9, fprintf (gc_debug_file
, "Precise copy of %p from %p", obj
, obj_slot
));
294 * obj must belong to one of:
299 * 4. a non-to-space section of the major heap
300 * 5. a to-space section of the major heap
302 * In addition, objects in 1, 2 and 4 might also be pinned.
303 * Objects in 1 and 4 might be forwarded.
305 * Before we can copy the object we must make sure that we are
306 * allowed to, i.e. that the object not pinned, not already
307 * forwarded and doesn't belong to the LOS, a pinned chunk, or
308 * a to-space section.
310 * We are usually called for to-space objects (5) when we have
311 * two remset entries for the same reference. The first entry
312 * copies the object and updates the reference and the second
313 * calls us with the updated reference that points into
314 * to-space. There might also be other circumstances where we
315 * get to-space objects.
318 if ((forwarded
= SGEN_OBJECT_IS_FORWARDED (obj
))) {
319 DEBUG (9, g_assert (((MonoVTable
*)SGEN_LOAD_VTABLE(obj
))->gc_descr
));
320 DEBUG (9, fprintf (gc_debug_file
, " (already forwarded to %p)\n", forwarded
));
321 HEAVY_STAT (++stat_major_copy_object_failed_forwarded
);
322 *obj_slot
= forwarded
;
325 if (SGEN_OBJECT_IS_PINNED (obj
)) {
326 DEBUG (9, g_assert (((MonoVTable
*)SGEN_LOAD_VTABLE(obj
))->gc_descr
));
327 DEBUG (9, fprintf (gc_debug_file
, " (pinned, no change)\n"));
328 HEAVY_STAT (++stat_major_copy_object_failed_pinned
);
332 if (ptr_in_nursery (obj
))
336 * At this point we know obj is not pinned, not forwarded and
337 * belongs to 2, 3, 4, or 5.
339 * LOS object (2) are simple, at least until we always follow
340 * the rule: if objsize > SGEN_MAX_SMALL_OBJ_SIZE, pin the
341 * object and return it. At the end of major collections, we
342 * walk the los list and if the object is pinned, it is
343 * marked, otherwise it can be freed.
345 * Pinned chunks (3) and major heap sections (4, 5) both
346 * reside in blocks, which are always aligned, so once we've
347 * eliminated LOS objects, we can just access the block and
348 * see whether it's a pinned chunk or a major heap section.
351 objsize
= SGEN_ALIGN_UP (mono_sgen_safe_object_get_size ((MonoObject
*)obj
));
353 if (G_UNLIKELY (objsize
> SGEN_MAX_SMALL_OBJ_SIZE
|| obj_is_from_pinned_alloc (obj
))) {
354 if (SGEN_OBJECT_IS_PINNED (obj
))
356 DEBUG (9, fprintf (gc_debug_file
, " (marked LOS/Pinned %p (%s), size: %zd)\n", obj
, safe_name (obj
), objsize
));
357 binary_protocol_pin (obj
, (gpointer
)SGEN_LOAD_VTABLE (obj
), mono_sgen_safe_object_get_size ((MonoObject
*)obj
));
358 SGEN_PIN_OBJECT (obj
);
359 GRAY_OBJECT_ENQUEUE (queue
, obj
);
360 HEAVY_STAT (++stat_major_copy_object_failed_large_pinned
);
365 * Now we know the object is in a major heap section. All we
366 * need to do is check whether it's already in to-space (5) or
369 if (MAJOR_OBJ_IS_IN_TO_SPACE (obj
)) {
370 DEBUG (9, g_assert (objsize
<= SGEN_MAX_SMALL_OBJ_SIZE
));
371 DEBUG (9, fprintf (gc_debug_file
, " (already copied)\n"));
372 HEAVY_STAT (++stat_major_copy_object_failed_to_space
);
377 HEAVY_STAT (++stat_objects_copied_major
);
379 *obj_slot
= copy_object_no_checks (obj
, queue
);
382 #include "sgen-major-scan-object.h"
384 /* FIXME: later reduce code duplication here with build_nursery_fragments().
385 * We don't keep track of section fragments for non-nursery sections yet, so
389 build_section_fragments (GCMemSection
*section
)
392 char *frag_start
, *frag_end
;
395 /* clear scan starts */
396 memset (section
->scan_starts
, 0, section
->num_scan_start
* sizeof (gpointer
));
397 frag_start
= section
->data
;
398 section
->next_data
= section
->data
;
399 for (i
= 0; i
< section
->pin_queue_num_entries
; ++i
) {
400 frag_end
= section
->pin_queue_start
[i
];
401 /* remove the pin bit from pinned objects */
402 SGEN_UNPIN_OBJECT (frag_end
);
403 if (frag_end
>= section
->data
+ section
->size
) {
404 frag_end
= section
->data
+ section
->size
;
406 section
->scan_starts
[((char*)frag_end
- (char*)section
->data
)/SGEN_SCAN_START_SIZE
] = frag_end
;
408 frag_size
= frag_end
- frag_start
;
410 binary_protocol_empty (frag_start
, frag_size
);
411 memset (frag_start
, 0, frag_size
);
413 frag_size
= SGEN_ALIGN_UP (mono_sgen_safe_object_get_size ((MonoObject
*)section
->pin_queue_start
[i
]));
414 frag_start
= (char*)section
->pin_queue_start
[i
] + frag_size
;
415 section
->next_data
= MAX (section
->next_data
, frag_start
);
417 frag_end
= section
->end_data
;
418 frag_size
= frag_end
- frag_start
;
420 binary_protocol_empty (frag_start
, frag_size
);
421 memset (frag_start
, 0, frag_size
);
426 sweep_pinned_objects_callback (char *ptr
, size_t size
, void *data
)
428 if (SGEN_OBJECT_IS_PINNED (ptr
)) {
429 SGEN_UNPIN_OBJECT (ptr
);
430 DEBUG (6, fprintf (gc_debug_file
, "Unmarked pinned object %p (%s)\n", ptr
, safe_name (ptr
)));
432 DEBUG (6, fprintf (gc_debug_file
, "Freeing unmarked pinned object %p (%s)\n", ptr
, safe_name (ptr
)));
433 free_pinned_object (ptr
, size
);
438 sweep_pinned_objects (void)
440 mono_sgen_internal_scan_objects (&pinned_allocator
, sweep_pinned_objects_callback
, NULL
);
444 major_iterate_objects (gboolean non_pinned
, gboolean pinned
, IterateObjectCallbackFunc callback
, void *data
)
447 GCMemSection
*section
;
448 for (section
= section_list
; section
; section
= section
->block
.next
)
449 mono_sgen_scan_area_with_callback (section
->data
, section
->end_data
, callback
, data
);
452 mono_sgen_internal_scan_objects (&pinned_allocator
, callback
, data
);
456 major_free_non_pinned_object (char *obj
, size_t size
)
458 memset (obj
, 0, size
);
462 pin_pinned_object_callback (void *addr
, size_t slot_size
, SgenGrayQueue
*queue
)
464 binary_protocol_pin (addr
, (gpointer
)SGEN_LOAD_VTABLE (addr
), mono_sgen_safe_object_get_size ((MonoObject
*)addr
));
465 if (!SGEN_OBJECT_IS_PINNED (addr
))
466 mono_sgen_pin_stats_register_object ((char*) addr
, mono_sgen_safe_object_get_size ((MonoObject
*) addr
));
467 SGEN_PIN_OBJECT (addr
);
468 GRAY_OBJECT_ENQUEUE (queue
, addr
);
469 DEBUG (6, fprintf (gc_debug_file
, "Marked pinned object %p (%s) from roots\n", addr
, safe_name (addr
)));
473 major_find_pin_queue_start_ends (SgenGrayQueue
*queue
)
475 GCMemSection
*section
;
477 for (section
= section_list
; section
; section
= section
->block
.next
)
478 mono_sgen_find_section_pin_queue_start_end (section
);
479 mono_sgen_internal_scan_pinned_objects (&pinned_allocator
, (IterateObjectCallbackFunc
)pin_pinned_object_callback
, queue
);
483 major_pin_objects (SgenGrayQueue
*queue
)
485 GCMemSection
*section
;
487 for (section
= section_list
; section
; section
= section
->block
.next
)
488 mono_sgen_pin_objects_in_section (section
, queue
);
492 major_init_to_space (void)
494 new_to_space_section ();
500 GCMemSection
*section
, *prev_section
;
502 to_space_set_next_data ();
505 /* unpin objects from the pinned chunks and free the unmarked ones */
506 sweep_pinned_objects ();
508 /* free the unused sections */
510 for (section
= section_list
; section
;) {
511 /* to_space doesn't need handling here */
512 if (section
->is_to_space
) {
513 section
->is_to_space
= FALSE
;
514 prev_section
= section
;
515 section
= section
->block
.next
;
518 /* no pinning object, so the section is free */
519 if (!section
->pin_queue_num_entries
) {
520 GCMemSection
*to_free
;
521 g_assert (!section
->pin_queue_start
);
523 prev_section
->block
.next
= section
->block
.next
;
525 section_list
= section
->block
.next
;
527 section
= section
->block
.next
;
528 free_major_section (to_free
);
531 DEBUG (6, fprintf (gc_debug_file
, "Section %p has still pinned objects (%d)\n", section
, section
->pin_queue_num_entries
));
532 build_section_fragments (section
);
534 prev_section
= section
;
535 section
= section
->block
.next
;
540 major_check_scan_starts (void)
542 GCMemSection
*section
;
543 for (section
= section_list
; section
; section
= section
->block
.next
)
544 mono_sgen_check_section_scan_starts (section
);
548 major_dump_heap (FILE *heap_dump_file
)
550 GCMemSection
*section
;
551 for (section
= section_list
; section
; section
= section
->block
.next
)
552 mono_sgen_dump_section (section
, "old");
553 /* FIXME: dump pinned sections, too */
557 major_get_used_size (void)
560 GCMemSection
*section
;
561 for (section
= section_list
; section
; section
= section
->block
.next
) {
562 /* this is approximate... */
563 tot
+= section
->next_data
- section
->data
;
568 /* only valid during minor collections */
569 static int old_num_major_sections
;
572 major_start_nursery_collection (void)
574 old_num_major_sections
= num_major_sections
;
576 if (!to_space_section
) {
577 new_to_space_section ();
579 /* we might have done degraded allocation since the
581 g_assert (to_space_bumper
<= to_space_section
->next_data
);
582 to_space_bumper
= to_space_section
->next_data
;
584 to_space_section
->is_to_space
= TRUE
;
589 major_finish_nursery_collection (void)
591 GCMemSection
*section
;
592 int sections_alloced
;
594 to_space_set_next_data ();
596 for (section
= section_list
; section
; section
= section
->block
.next
)
597 section
->is_to_space
= FALSE
;
599 sections_alloced
= num_major_sections
- old_num_major_sections
;
600 mono_sgen_register_major_sections_alloced (sections_alloced
);
604 major_finish_major_collection (void)
609 major_ptr_is_in_non_pinned_space (char *ptr
)
611 GCMemSection
*section
;
612 for (section
= section_list
; section
;) {
613 if (ptr
>= section
->data
&& ptr
< section
->data
+ section
->size
)
615 section
= section
->block
.next
;
621 major_report_pinned_memory_usage (void)
623 mono_sgen_report_internal_mem_usage_full (&pinned_allocator
);
627 get_num_major_sections (void)
629 return num_major_sections
;
633 mono_sgen_copying_init (SgenMajorCollector
*collector
)
635 #ifdef HEAVY_STATISTICS
636 mono_counters_register ("# major copy_object() failed forwarded", MONO_COUNTER_GC
| MONO_COUNTER_LONG
, &stat_major_copy_object_failed_forwarded
);
637 mono_counters_register ("# major copy_object() failed pinned", MONO_COUNTER_GC
| MONO_COUNTER_LONG
, &stat_major_copy_object_failed_pinned
);
638 mono_counters_register ("# major copy_object() failed large or pinned chunk", MONO_COUNTER_GC
| MONO_COUNTER_LONG
, &stat_major_copy_object_failed_large_pinned
);
639 mono_counters_register ("# major copy_object() failed to space", MONO_COUNTER_GC
| MONO_COUNTER_LONG
, &stat_major_copy_object_failed_to_space
);
642 collector
->section_size
= MAJOR_SECTION_SIZE
;
643 collector
->is_parallel
= FALSE
;
645 collector
->alloc_heap
= major_alloc_heap
;
646 collector
->is_object_live
= major_is_object_live
;
647 collector
->alloc_small_pinned_obj
= major_alloc_small_pinned_obj
;
648 collector
->alloc_degraded
= major_alloc_degraded
;
649 collector
->copy_or_mark_object
= major_copy_or_mark_object
;
650 collector
->alloc_object
= major_alloc_object
;
651 collector
->free_pinned_object
= free_pinned_object
;
652 collector
->iterate_objects
= major_iterate_objects
;
653 collector
->free_non_pinned_object
= major_free_non_pinned_object
;
654 collector
->find_pin_queue_start_ends
= major_find_pin_queue_start_ends
;
655 collector
->pin_objects
= major_pin_objects
;
656 collector
->init_to_space
= major_init_to_space
;
657 collector
->sweep
= major_sweep
;
658 collector
->check_scan_starts
= major_check_scan_starts
;
659 collector
->dump_heap
= major_dump_heap
;
660 collector
->get_used_size
= major_get_used_size
;
661 collector
->start_nursery_collection
= major_start_nursery_collection
;
662 collector
->finish_nursery_collection
= major_finish_nursery_collection
;
663 collector
->finish_major_collection
= major_finish_major_collection
;
664 collector
->ptr_is_in_non_pinned_space
= major_ptr_is_in_non_pinned_space
;
665 collector
->obj_is_from_pinned_alloc
= obj_is_from_pinned_alloc
;
666 collector
->report_pinned_memory_usage
= major_report_pinned_memory_usage
;
667 collector
->get_num_major_sections
= get_num_major_sections
;
668 collector
->handle_gc_param
= NULL
;
669 collector
->print_gc_param_usage
= NULL
;
671 FILL_COLLECTOR_COPY_OBJECT (collector
);
672 FILL_COLLECTOR_SCAN_OBJECT (collector
);