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.
48 #define LOS_SECTION_SIZE (1024 * 1024)
51 * This shouldn't be much smaller or larger than MAX_SMALL_OBJ_SIZE.
52 * Must be at least sizeof (LOSSection).
54 #define LOS_CHUNK_SIZE 4096
55 #define LOS_CHUNK_BITS 12
57 /* Largest object that can be allocated in a section. */
58 #define LOS_SECTION_OBJECT_LIMIT (LOS_SECTION_SIZE - LOS_CHUNK_SIZE - sizeof (LOSObject))
59 //#define LOS_SECTION_OBJECT_LIMIT 0
60 #define LOS_SECTION_NUM_CHUNKS ((LOS_SECTION_SIZE >> LOS_CHUNK_BITS) - 1)
62 #define LOS_SECTION_FOR_OBJ(obj) ((LOSSection*)((mword)(obj) & ~(mword)(LOS_SECTION_SIZE - 1)))
63 #define LOS_CHUNK_INDEX(obj,section) (((char*)(obj) - (char*)(section)) >> LOS_CHUNK_BITS)
65 #define LOS_NUM_FAST_SIZES 32
67 typedef struct _LOSObject LOSObject
;
70 mword size
; /* this is the object size */
72 int dummy
; /* to have a sizeof (LOSObject) a multiple of ALLOC_ALIGN and data starting at same alignment */
73 char data
[MONO_ZERO_LEN_ARRAY
];
76 typedef struct _LOSFreeChunks LOSFreeChunks
;
77 struct _LOSFreeChunks
{
78 LOSFreeChunks
*next_size
;
82 typedef struct _LOSSection LOSSection
;
86 unsigned char *free_chunk_map
;
89 static LOSSection
*los_sections
= NULL
;
90 static LOSObject
*los_object_list
= NULL
;
91 static LOSFreeChunks
*los_fast_free_lists
[LOS_NUM_FAST_SIZES
]; /* 0 is for larger sizes */
92 static mword los_memory_usage
= 0;
93 static mword last_los_memory_usage
= 0;
94 static mword los_num_objects
= 0;
95 static int los_num_sections
= 0;
96 static mword next_los_collection
= 2*1024*1024; /* 2 MB, need to tune */
99 //#define LOS_CONSISTENCY_CHECK
103 #define LOS_SEGMENT_SIZE (4096 * 1024)
105 static char *los_segment
= NULL
;
106 static int los_segment_index
= 0;
109 #ifdef LOS_CONSISTENCY_CHECK
111 los_consistency_check (void)
116 mword memory_usage
= 0;
118 for (obj
= los_object_list
; obj
; obj
= obj
->next
) {
119 char *end
= obj
->data
+ obj
->size
;
120 int start_index
, num_chunks
;
122 memory_usage
+= obj
->size
;
124 if (obj
->size
> LOS_SECTION_OBJECT_LIMIT
)
127 section
= LOS_SECTION_FOR_OBJ (obj
);
129 g_assert (end
<= (char*)section
+ LOS_SECTION_SIZE
);
131 start_index
= LOS_CHUNK_INDEX (obj
, section
);
132 num_chunks
= (obj
->size
+ sizeof (LOSObject
) + LOS_CHUNK_SIZE
- 1) >> LOS_CHUNK_BITS
;
133 for (i
= start_index
; i
< start_index
+ num_chunks
; ++i
)
134 g_assert (!section
->free_chunk_map
[i
]);
137 for (i
= 0; i
< LOS_NUM_FAST_SIZES
; ++i
) {
138 LOSFreeChunks
*size_chunks
;
139 for (size_chunks
= los_fast_free_lists
[i
]; size_chunks
; size_chunks
= size_chunks
->next_size
) {
140 LOSSection
*section
= LOS_SECTION_FOR_OBJ (size_chunks
);
141 int j
, num_chunks
, start_index
;
144 g_assert (size_chunks
->size
>= LOS_NUM_FAST_SIZES
* LOS_CHUNK_SIZE
);
146 g_assert (size_chunks
->size
== i
* LOS_CHUNK_SIZE
);
148 num_chunks
= size_chunks
->size
>> LOS_CHUNK_BITS
;
149 start_index
= LOS_CHUNK_INDEX (size_chunks
, section
);
150 for (j
= start_index
; j
< start_index
+ num_chunks
; ++j
)
151 g_assert (section
->free_chunk_map
[j
]);
155 g_assert (los_memory_usage
== memory_usage
);
160 add_free_chunk (LOSFreeChunks
*free_chunks
, size_t size
)
162 int num_chunks
= size
>> LOS_CHUNK_BITS
;
164 free_chunks
->size
= size
;
166 if (num_chunks
>= LOS_NUM_FAST_SIZES
)
168 free_chunks
->next_size
= los_fast_free_lists
[num_chunks
];
169 los_fast_free_lists
[num_chunks
] = free_chunks
;
172 static LOSFreeChunks
*
173 get_from_size_list (LOSFreeChunks
**list
, size_t size
)
175 LOSFreeChunks
*free_chunks
= NULL
;
177 int num_chunks
, i
, start_index
;
179 g_assert ((size
& (LOS_CHUNK_SIZE
- 1)) == 0);
183 if (free_chunks
->size
>= size
)
185 list
= &(*list
)->next_size
;
191 *list
= free_chunks
->next_size
;
193 if (free_chunks
->size
> size
)
194 add_free_chunk ((LOSFreeChunks
*)((char*)free_chunks
+ size
), free_chunks
->size
- size
);
196 num_chunks
= size
>> LOS_CHUNK_BITS
;
198 section
= LOS_SECTION_FOR_OBJ (free_chunks
);
200 start_index
= LOS_CHUNK_INDEX (free_chunks
, section
);
201 for (i
= start_index
; i
< start_index
+ num_chunks
; ++i
) {
202 g_assert (section
->free_chunk_map
[i
]);
203 section
->free_chunk_map
[i
] = 0;
206 section
->num_free_chunks
-= size
>> LOS_CHUNK_BITS
;
207 g_assert (section
->num_free_chunks
>= 0);
213 get_los_section_memory (size_t size
)
216 LOSFreeChunks
*free_chunks
;
219 size
+= LOS_CHUNK_SIZE
- 1;
220 size
&= ~(LOS_CHUNK_SIZE
- 1);
222 num_chunks
= size
>> LOS_CHUNK_BITS
;
224 g_assert (size
> 0 && size
- sizeof (LOSObject
) <= LOS_SECTION_OBJECT_LIMIT
);
225 g_assert (num_chunks
> 0);
228 if (num_chunks
>= LOS_NUM_FAST_SIZES
) {
229 free_chunks
= get_from_size_list (&los_fast_free_lists
[0], size
);
232 for (i
= num_chunks
; i
< LOS_NUM_FAST_SIZES
; ++i
) {
233 free_chunks
= get_from_size_list (&los_fast_free_lists
[i
], size
);
238 free_chunks
= get_from_size_list (&los_fast_free_lists
[0], size
);
242 return (LOSObject
*)free_chunks
;
244 section
= mono_sgen_alloc_os_memory_aligned (LOS_SECTION_SIZE
, LOS_SECTION_SIZE
, TRUE
);
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 int 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
);
299 free_large_object (LOSObject
*obj
)
302 size_t size
= obj
->size
;
303 DEBUG (4, fprintf (gc_debug_file
, "Freed large object %p, size %lu\n", obj
->data
, (unsigned long)obj
->size
));
304 binary_protocol_empty (obj
->data
, obj
->size
);
306 los_memory_usage
-= size
;
312 if (size
> LOS_SECTION_OBJECT_LIMIT
) {
313 size
+= sizeof (LOSObject
);
314 size
+= pagesize
- 1;
315 size
&= ~(pagesize
- 1);
316 mono_sgen_free_os_memory (obj
, size
);
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.
333 static void* __attribute__((noinline
))
334 alloc_large_inner (MonoVTable
*vtable
, size_t size
)
339 g_assert (size
> MAX_SMALL_OBJ_SIZE
);
343 los_segment
= mono_sgen_alloc_os_memory (LOS_SEGMENT_SIZE
, TRUE
);
344 los_segment_index
= ALIGN_UP (los_segment_index
);
346 obj
= (LOSObject
*)(los_segment
+ los_segment_index
);
347 los_segment_index
+= size
+ sizeof (LOSObject
);
348 g_assert (los_segment_index
<= LOS_SEGMENT_SIZE
);
350 if (need_major_collection ()) {
351 DEBUG (4, fprintf (gc_debug_file
, "Should trigger major collection: req size %zd (los already: %lu, limit: %lu)\n", size
, (unsigned long)los_memory_usage
, (unsigned long)next_los_collection
));
353 major_collection ("LOS overflow");
358 obj
= malloc (size
+ sizeof (LOSObject
));
359 memset (obj
, 0, size
+ sizeof (LOSObject
));
361 if (size
> LOS_SECTION_OBJECT_LIMIT
) {
362 size_t alloc_size
= size
;
363 alloc_size
+= sizeof (LOSObject
);
364 alloc_size
+= pagesize
- 1;
365 alloc_size
&= ~(pagesize
- 1);
366 /* FIXME: handle OOM */
367 obj
= mono_sgen_alloc_os_memory (alloc_size
, TRUE
);
369 obj
= get_los_section_memory (size
+ sizeof (LOSObject
));
370 memset (obj
, 0, size
+ sizeof (LOSObject
));
375 g_assert (!((mword
)obj
->data
& (ALLOC_ALIGN
- 1)));
377 vtslot
= (void**)obj
->data
;
379 mono_sgen_update_heap_boundaries ((mword
)obj
->data
, (mword
)obj
->data
+ size
);
380 obj
->next
= los_object_list
;
381 los_object_list
= obj
;
382 los_memory_usage
+= size
;
384 DEBUG (4, fprintf (gc_debug_file
, "Allocated large object %p, vtable: %p (%s), size: %zd\n", obj
->data
, vtable
, vtable
->klass
->name
, size
));
385 binary_protocol_alloc (obj
->data
, vtable
, size
);
387 #ifdef LOS_CONSISTENCY_CHECK
388 los_consistency_check ();
397 LOSSection
*section
, *prev
;
399 int num_sections
= 0;
401 for (i
= 0; i
< LOS_NUM_FAST_SIZES
; ++i
)
402 los_fast_free_lists
[i
] = NULL
;
405 section
= los_sections
;
407 if (section
->num_free_chunks
== LOS_SECTION_NUM_CHUNKS
) {
408 LOSSection
*next
= section
->next
;
413 mono_sgen_free_os_memory (section
, LOS_SECTION_SIZE
);
419 for (i
= 0; i
<= LOS_SECTION_NUM_CHUNKS
; ++i
) {
420 if (section
->free_chunk_map
[i
]) {
422 for (j
= i
+ 1; j
<= LOS_SECTION_NUM_CHUNKS
&& section
->free_chunk_map
[j
]; ++j
)
424 add_free_chunk ((LOSFreeChunks
*)((char*)section
+ (i
<< LOS_CHUNK_BITS
)), (j
- i
) << LOS_CHUNK_BITS
);
430 section
= section
->next
;
435 #ifdef LOS_CONSISTENCY_CHECK
436 los_consistency_check ();
440 g_print ("LOS sections: %d objects: %d usage: %d\n", num_sections, los_num_objects, los_memory_usage);
441 for (i = 0; i < LOS_NUM_FAST_SIZES; ++i) {
443 LOSFreeChunks *free_chunks;
444 for (free_chunks = los_fast_free_lists [i]; free_chunks; free_chunks = free_chunks->next_size)
446 g_print (" %d: %d\n", i, num_chunks);
450 g_assert (los_num_sections
== num_sections
);