3 * GC descriptors describe object layout.
5 * Copyright 2001-2003 Ximian, Inc
6 * Copyright 2003-2010 Novell, Inc.
7 * Copyright 2011 Xamarin Inc (http://www.xamarin.com)
8 * Copyright (C) 2012 Xamarin Inc
10 * Licensed under the MIT license. See LICENSE file in the project root for full license information.
21 #ifdef HAVE_SEMAPHORE_H
22 #include <semaphore.h>
35 #include "mono/sgen/sgen-gc.h"
36 #include "mono/sgen/gc-internal-agnostic.h"
37 #include "mono/sgen/sgen-array-list.h"
39 #define MAX_USER_DESCRIPTORS 16
41 #define MAKE_ROOT_DESC(type,val) ((type) | ((val) << ROOT_DESC_TYPE_SHIFT))
43 static SgenArrayList complex_descriptors
= SGEN_ARRAY_LIST_INIT (NULL
, NULL
, NULL
, INTERNAL_MEM_COMPLEX_DESCRIPTORS
);
44 static SgenUserRootMarkFunc user_descriptors
[MAX_USER_DESCRIPTORS
];
45 static int user_descriptors_next
= 0;
46 static SgenDescriptor all_ref_root_descrs
[32];
48 #ifdef HEAVY_STATISTICS
49 static guint64 stat_scanned_count_per_descriptor
[DESC_TYPE_MAX
];
50 static guint64 stat_copied_count_per_descriptor
[DESC_TYPE_MAX
];
54 alloc_complex_descriptor (gsize
*bitmap
, int numbits
)
57 volatile gpointer
*slot
;
60 SGEN_ASSERT (0, sizeof (gsize
) == sizeof (mword
), "We expect gsize and mword to have same size");
62 numbits
= ALIGN_TO (numbits
, GC_BITS_PER_WORD
);
63 nwords
= numbits
/ GC_BITS_PER_WORD
+ 1;
66 /* linear search, so we don't have duplicates with domain load/unload
67 * this should not be performance critical or we'd have bigger issues
68 * (the number and size of complex descriptors should be small).
70 SGEN_ARRAY_LIST_FOREACH_SLOT (&complex_descriptors
, slot
) {
71 gsize first_word
= *(gsize
*)slot
;
72 if (first_word
== 0) {
73 /* Unused slots should be 0 so we simply skip them */
75 } else if (first_word
== nwords
) {
77 for (j
= 0; j
< nwords
- 1; ++j
) {
78 if (((gsize
*)slot
) [j
+ 1] != bitmap
[j
]) {
88 /* Skip the bitmap words */
89 __index
+= (guint32
)(first_word
- 1);
90 __offset
+= (guint32
)(first_word
- 1);
91 } SGEN_ARRAY_LIST_END_FOREACH_SLOT
;
93 res
= sgen_array_list_alloc_block (&complex_descriptors
, nwords
);
95 SGEN_LOG (6, "Complex descriptor %d, size: %d (total desc memory: %d)", res
, nwords
, complex_descriptors
.capacity
);
96 descriptor
= (gsize
*)sgen_array_list_get_slot (&complex_descriptors
, res
);
97 descriptor
[0] = nwords
;
98 for (i
= 0; i
< nwords
- 1; ++i
) {
99 descriptor
[1 + i
] = bitmap
[i
];
100 SGEN_LOG (6, "\tvalue: %p", (void*)descriptor
[1 + i
]);
107 sgen_get_complex_descriptor (SgenDescriptor desc
)
109 return (gsize
*) sgen_array_list_get_slot (&complex_descriptors
, desc
>> LOW_TYPE_BITS
);
113 * Descriptor builders.
116 mono_gc_make_descr_for_object (gsize
*bitmap
, int numbits
, size_t obj_size
)
118 int first_set
= -1, num_set
= 0, last_set
= -1, i
;
119 SgenDescriptor desc
= 0;
120 size_t stored_size
= SGEN_ALIGN_UP (obj_size
);
122 for (i
= 0; i
< numbits
; ++i
) {
123 if (bitmap
[i
/ GC_BITS_PER_WORD
] & ((gsize
)1 << (i
% GC_BITS_PER_WORD
))) {
132 SGEN_LOG (6, "Ptrfree descriptor %p, size: %ld", (void*)desc
, (long)stored_size
);
133 if (stored_size
<= MAX_RUNLEN_OBJECT_SIZE
&& stored_size
<= SGEN_MAX_SMALL_OBJ_SIZE
)
134 return DESC_TYPE_SMALL_PTRFREE
| stored_size
;
135 return DESC_TYPE_COMPLEX_PTRFREE
;
138 g_assert (!(stored_size
& 0x7));
140 SGEN_ASSERT (5, stored_size
== SGEN_ALIGN_UP (stored_size
), "Size is not aligned");
142 /* we know the 2-word header is ptr-free */
143 if (last_set
< BITMAP_NUM_BITS
+ OBJECT_HEADER_WORDS
&& stored_size
<= SGEN_MAX_SMALL_OBJ_SIZE
) {
144 desc
= DESC_TYPE_BITMAP
| ((*bitmap
>> OBJECT_HEADER_WORDS
) << LOW_TYPE_BITS
);
145 SGEN_LOG (6, "Largebitmap descriptor %p, size: %ld, last set: %d", (void*)desc
, (long)stored_size
, last_set
);
149 if (stored_size
<= MAX_RUNLEN_OBJECT_SIZE
&& stored_size
<= SGEN_MAX_SMALL_OBJ_SIZE
) {
150 /* check run-length encoding first: one byte offset, one byte number of pointers
151 * on 64 bit archs, we can have 3 runs, just one on 32.
152 * It may be better to use nibbles.
154 if (first_set
< 256 && num_set
< 256 && (first_set
+ num_set
== last_set
+ 1)) {
155 desc
= DESC_TYPE_RUN_LENGTH
| stored_size
| (first_set
<< 16) | (num_set
<< 24);
156 SGEN_LOG (6, "Runlen descriptor %p, size: %ld, first set: %d, num set: %d", (void*)desc
, (long)stored_size
, first_set
, num_set
);
161 /* it's a complex object ... */
162 desc
= DESC_TYPE_COMPLEX
| (alloc_complex_descriptor (bitmap
, last_set
+ 1) << LOW_TYPE_BITS
);
166 /* If the array holds references, numbits == 1 and the first bit is set in elem_bitmap */
168 mono_gc_make_descr_for_array (int vector
, gsize
*elem_bitmap
, int numbits
, size_t elem_size
)
170 int first_set
= -1, num_set
= 0, last_set
= -1, i
;
171 SgenDescriptor desc
= DESC_TYPE_VECTOR
| (vector
? VECTOR_KIND_SZARRAY
: VECTOR_KIND_ARRAY
);
172 for (i
= 0; i
< numbits
; ++i
) {
173 if (elem_bitmap
[i
/ GC_BITS_PER_WORD
] & ((gsize
)1 << (i
% GC_BITS_PER_WORD
))) {
182 if (elem_size
<= MAX_ELEMENT_SIZE
)
183 return desc
| VECTOR_SUBTYPE_PTRFREE
| (elem_size
<< VECTOR_ELSIZE_SHIFT
);
184 return DESC_TYPE_COMPLEX_PTRFREE
;
187 if (elem_size
<= MAX_ELEMENT_SIZE
) {
188 desc
|= elem_size
<< VECTOR_ELSIZE_SHIFT
;
190 return desc
| VECTOR_SUBTYPE_PTRFREE
;
192 /* Note: we also handle structs with just ref fields */
193 if (num_set
* sizeof (gpointer
) == elem_size
) {
194 return desc
| VECTOR_SUBTYPE_REFS
| ((gsize
)(-1) << 16);
196 /* FIXME: try run-len first */
197 /* Note: we can't skip the object header here, because it's not present */
198 if (last_set
< VECTOR_BITMAP_SIZE
) {
199 return desc
| VECTOR_SUBTYPE_BITMAP
| (*elem_bitmap
<< 16);
202 /* it's am array of complex structs ... */
203 desc
= DESC_TYPE_COMPLEX_ARR
;
204 desc
|= alloc_complex_descriptor (elem_bitmap
, last_set
+ 1) << LOW_TYPE_BITS
;
208 /* Return the bitmap encoded by a descriptor */
210 mono_gc_get_bitmap_for_descr (SgenDescriptor descr
, int *numbits
)
212 SgenDescriptor d
= (SgenDescriptor
)descr
;
215 switch (d
& DESC_TYPE_MASK
) {
216 case DESC_TYPE_RUN_LENGTH
: {
217 int first_set
= (d
>> 16) & 0xff;
218 int num_set
= (d
>> 24) & 0xff;
221 bitmap
= g_new0 (gsize
, (first_set
+ num_set
+ 7) / 8);
223 for (i
= first_set
; i
< first_set
+ num_set
; ++i
)
224 bitmap
[i
/ GC_BITS_PER_WORD
] |= ((gsize
)1 << (i
% GC_BITS_PER_WORD
));
226 *numbits
= first_set
+ num_set
;
231 case DESC_TYPE_BITMAP
: {
232 gsize bmap
= (d
>> LOW_TYPE_BITS
) << OBJECT_HEADER_WORDS
;
234 bitmap
= g_new0 (gsize
, 1);
244 case DESC_TYPE_COMPLEX
: {
245 gsize
*bitmap_data
= sgen_get_complex_descriptor (d
);
246 int bwords
= (int)(*bitmap_data
) - 1;//Max scalar object size is 1Mb, which means up to 32k descriptor words
249 bitmap
= g_new0 (gsize
, bwords
);
250 *numbits
= bwords
* GC_BITS_PER_WORD
;
252 for (i
= 0; i
< bwords
; ++i
) {
253 bitmap
[i
] = bitmap_data
[i
+ 1];
260 g_assert_not_reached ();
265 * mono_gc_make_descr_from_bitmap:
268 mono_gc_make_descr_from_bitmap (gsize
*bitmap
, int numbits
)
271 return MAKE_ROOT_DESC (ROOT_DESC_BITMAP
, 0);
272 } else if (numbits
< ((sizeof (*bitmap
) * 8) - ROOT_DESC_TYPE_SHIFT
)) {
273 return MAKE_ROOT_DESC (ROOT_DESC_BITMAP
, bitmap
[0]);
275 SgenDescriptor
complex = alloc_complex_descriptor (bitmap
, numbits
);
276 return MAKE_ROOT_DESC (ROOT_DESC_COMPLEX
, complex);
281 mono_gc_make_vector_descr (void)
283 return MAKE_ROOT_DESC (ROOT_DESC_VECTOR
, 0);
287 mono_gc_make_root_descr_all_refs (int numbits
)
290 SgenDescriptor descr
;
291 int num_bytes
= numbits
/ 8;
293 if (numbits
< 32 && all_ref_root_descrs
[numbits
])
294 return all_ref_root_descrs
[numbits
];
296 gc_bitmap
= (gsize
*)g_malloc0 (ALIGN_TO (ALIGN_TO (numbits
, 8) + 1, sizeof (gsize
)));
297 memset (gc_bitmap
, 0xff, num_bytes
);
298 if (numbits
< ((sizeof (*gc_bitmap
) * 8) - ROOT_DESC_TYPE_SHIFT
))
299 gc_bitmap
[0] = GUINT64_TO_LE(gc_bitmap
[0]);
300 else if (numbits
&& num_bytes
% (sizeof (*gc_bitmap
)))
301 gc_bitmap
[num_bytes
/ 8] = GUINT64_TO_LE(gc_bitmap
[num_bytes
/ 8]);
303 gc_bitmap
[numbits
/ 8] = (1 << (numbits
% 8)) - 1;
304 descr
= mono_gc_make_descr_from_bitmap (gc_bitmap
, numbits
);
308 all_ref_root_descrs
[numbits
] = descr
;
314 sgen_make_user_root_descriptor (SgenUserRootMarkFunc marker
)
316 SgenDescriptor descr
;
318 g_assert (user_descriptors_next
< MAX_USER_DESCRIPTORS
);
319 descr
= MAKE_ROOT_DESC (ROOT_DESC_USER
, (SgenDescriptor
)user_descriptors_next
);
320 user_descriptors
[user_descriptors_next
++] = marker
;
326 sgen_get_complex_descriptor_bitmap (SgenDescriptor desc
)
328 return (void*) sgen_array_list_get_slot (&complex_descriptors
, desc
>> ROOT_DESC_TYPE_SHIFT
);
332 sgen_get_user_descriptor_func (SgenDescriptor desc
)
334 return user_descriptors
[desc
>> ROOT_DESC_TYPE_SHIFT
];
337 #ifdef HEAVY_STATISTICS
339 sgen_descriptor_count_scanned_object (SgenDescriptor desc
)
341 int type
= desc
& DESC_TYPE_MASK
;
342 SGEN_ASSERT (0, type
, "Descriptor type can't be zero");
343 ++stat_scanned_count_per_descriptor
[type
- 1];
347 sgen_descriptor_count_copied_object (SgenDescriptor desc
)
349 int type
= desc
& DESC_TYPE_MASK
;
350 SGEN_ASSERT (0, type
, "Descriptor type can't be zero");
351 ++stat_copied_count_per_descriptor
[type
- 1];
356 sgen_init_descriptors (void)
358 #ifdef HEAVY_STATISTICS
359 mono_counters_register ("# scanned RUN_LENGTH", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &stat_scanned_count_per_descriptor
[DESC_TYPE_RUN_LENGTH
- 1]);
360 mono_counters_register ("# scanned SMALL_PTRFREE", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &stat_scanned_count_per_descriptor
[DESC_TYPE_SMALL_PTRFREE
- 1]);
361 mono_counters_register ("# scanned COMPLEX", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &stat_scanned_count_per_descriptor
[DESC_TYPE_COMPLEX
- 1]);
362 mono_counters_register ("# scanned VECTOR", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &stat_scanned_count_per_descriptor
[DESC_TYPE_VECTOR
- 1]);
363 mono_counters_register ("# scanned BITMAP", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &stat_scanned_count_per_descriptor
[DESC_TYPE_BITMAP
- 1]);
364 mono_counters_register ("# scanned COMPLEX_ARR", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &stat_scanned_count_per_descriptor
[DESC_TYPE_COMPLEX_ARR
- 1]);
365 mono_counters_register ("# scanned COMPLEX_PTRFREE", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &stat_scanned_count_per_descriptor
[DESC_TYPE_COMPLEX_PTRFREE
- 1]);
367 mono_counters_register ("# copied RUN_LENGTH", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &stat_copied_count_per_descriptor
[DESC_TYPE_RUN_LENGTH
- 1]);
368 mono_counters_register ("# copied SMALL_PTRFREE", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &stat_copied_count_per_descriptor
[DESC_TYPE_SMALL_PTRFREE
- 1]);
369 mono_counters_register ("# copied COMPLEX", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &stat_copied_count_per_descriptor
[DESC_TYPE_COMPLEX
- 1]);
370 mono_counters_register ("# copied VECTOR", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &stat_copied_count_per_descriptor
[DESC_TYPE_VECTOR
- 1]);
371 mono_counters_register ("# copied BITMAP", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &stat_copied_count_per_descriptor
[DESC_TYPE_BITMAP
- 1]);
372 mono_counters_register ("# copied COMPLEX_ARR", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &stat_copied_count_per_descriptor
[DESC_TYPE_COMPLEX_ARR
- 1]);
373 mono_counters_register ("# copied COMPLEX_PTRFREE", MONO_COUNTER_GC
| MONO_COUNTER_ULONG
, &stat_copied_count_per_descriptor
[DESC_TYPE_COMPLEX_PTRFREE
- 1]);