2 * Copyright 2001-2003 Ximian, Inc
3 * Copyright 2003-2010 Novell, Inc.
4 * Copyright 2011 Xamarin Inc (http://www.xamarin.com)
6 * Permission is hereby granted, free of charge, to any person obtaining
7 * a copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sublicense, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
14 * The above copyright notice and this permission notice shall be
15 * included in all copies or substantial portions of the Software.
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
21 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
22 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
23 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
25 #ifndef __MONO_SGEN_DESCRIPTOR_H__
26 #define __MONO_SGEN_DESCRIPTOR_H__
28 #include <mono/metadata/gc-internal.h>
29 #include <mono/metadata/sgen-conf.h>
33 * ######################################################################
34 * ######## GC descriptors
35 * ######################################################################
36 * Used to quickly get the info the GC needs about an object: size and
37 * where the references are held.
39 #define OBJECT_HEADER_WORDS (sizeof(MonoObject)/sizeof(gpointer))
40 #define LOW_TYPE_BITS 3
41 #define MAX_RUNLEN_OBJECT_SIZE 0xFFFF
42 #define SMALL_BITMAP_SHIFT 16
43 #define SMALL_BITMAP_SIZE (GC_BITS_PER_WORD - SMALL_BITMAP_SHIFT)
44 #define VECTOR_INFO_SHIFT 14
45 #define VECTOR_KIND_SHIFT 13
46 #define VECTOR_ELSIZE_SHIFT 3
47 #define LARGE_BITMAP_SIZE (GC_BITS_PER_WORD - LOW_TYPE_BITS)
48 #define MAX_ELEMENT_SIZE 0x3ff
49 #define VECTOR_SUBTYPE_PTRFREE (DESC_TYPE_V_PTRFREE << VECTOR_INFO_SHIFT)
50 #define VECTOR_SUBTYPE_REFS (DESC_TYPE_V_REFS << VECTOR_INFO_SHIFT)
51 #define VECTOR_SUBTYPE_RUN_LEN (DESC_TYPE_V_RUN_LEN << VECTOR_INFO_SHIFT)
52 #define VECTOR_SUBTYPE_BITMAP (DESC_TYPE_V_BITMAP << VECTOR_INFO_SHIFT)
54 #define VECTOR_KIND_SZARRAY (DESC_TYPE_V_SZARRAY << VECTOR_KIND_SHIFT)
55 #define VECTOR_KIND_ARRAY (DESC_TYPE_V_ARRAY << VECTOR_KIND_SHIFT)
57 /* objects are aligned to 8 bytes boundaries
58 * A descriptor is a pointer in MonoVTable, so 32 or 64 bits of size.
59 * The low 3 bits define the type of the descriptor. The other bits
61 * As a general rule the 13 remaining low bits define the size, either
62 * of the whole object or of the elements in the arrays. While for objects
63 * the size is already in bytes, for arrays we need to shift, because
64 * array elements might be smaller than 8 bytes. In case of arrays, we
65 * use two bits to describe what the additional high bits represents,
66 * so the default behaviour can handle element sizes less than 2048 bytes.
67 * The high 16 bits, if 0 it means the object is pointer-free.
68 * This design should make it easy and fast to skip over ptr-free data.
69 * The first 4 types should cover >95% of the objects.
70 * Note that since the size of objects is limited to 64K, larger objects
71 * will be allocated in the large object heap.
72 * If we want 4-bytes alignment, we need to put vector and small bitmap
77 * We don't use 0 so that 0 isn't a valid GC descriptor. No
78 * deep reason for this other than to be able to identify a
79 * non-inited descriptor for debugging.
81 * If an object contains no references, its GC descriptor is
82 * always DESC_TYPE_RUN_LENGTH, without a size, no exceptions.
83 * This is so that we can quickly check for that in
84 * copy_object_no_checks(), without having to fetch the
87 DESC_TYPE_RUN_LENGTH = 1, /* 16 bits aligned byte size | 1-3 (offset, numptr) bytes tuples */
88 DESC_TYPE_SMALL_BITMAP, /* 16 bits aligned byte size | 16-48 bit bitmap */
89 DESC_TYPE_COMPLEX, /* index for bitmap into complex_descriptors */
90 DESC_TYPE_VECTOR, /* 10 bits element size | 1 bit kind | 2 bits desc | element desc */
91 DESC_TYPE_LARGE_BITMAP, /* | 29-61 bitmap bits */
92 DESC_TYPE_COMPLEX_ARR, /* index for bitmap into complex_descriptors */
93 DESC_TYPE_COMPLEX_PTRFREE, /*Nothing, used to encode large ptr objects. */
94 /* values for array kind */
95 DESC_TYPE_V_SZARRAY = 0, /*vector with no bounds data */
96 DESC_TYPE_V_ARRAY = 1, /* array with bounds data */
97 /* subtypes for arrays and vectors */
98 DESC_TYPE_V_PTRFREE = 0,/* there are no refs: keep first so it has a zero value */
99 DESC_TYPE_V_REFS, /* all the array elements are refs */
100 DESC_TYPE_V_RUN_LEN, /* elements are run-length encoded as DESC_TYPE_RUN_LENGTH */
101 DESC_TYPE_V_BITMAP /* elements are as the bitmap in DESC_TYPE_SMALL_BITMAP */
104 /* Root bitmap descriptors are simpler: the lower three bits describe the type
105 * and we either have 30/62 bitmap bits or nibble-based run-length,
106 * or a complex descriptor, or a user defined marker function.
109 ROOT_DESC_CONSERVATIVE, /* 0, so matches NULL value */
114 ROOT_DESC_TYPE_MASK = 0x7,
115 ROOT_DESC_TYPE_SHIFT = 3,
118 gsize* sgen_get_complex_descriptor (mword desc) MONO_INTERNAL;
119 void* sgen_get_complex_descriptor_bitmap (mword desc) MONO_INTERNAL;
120 MonoGCRootMarkFunc sgen_get_user_descriptor_func (mword desc) MONO_INTERNAL;
123 static inline gboolean
124 sgen_gc_descr_has_references (mword desc)
126 /*Both string and fixed size objects are encoded using a zero run RUN_LEN*/
127 if ((desc & 0xffff0007) == DESC_TYPE_RUN_LENGTH)
130 /*The array is ptr-free*/
131 if ((desc & 0xC007) == (DESC_TYPE_VECTOR | VECTOR_SUBTYPE_PTRFREE))
134 if ((desc & 0x7) == DESC_TYPE_COMPLEX_PTRFREE)
140 #define SGEN_VTABLE_HAS_REFERENCES(vt) (sgen_gc_descr_has_references ((mword)((MonoVTable*)(vt))->gc_descr))
141 #define SGEN_CLASS_HAS_REFERENCES(c) (sgen_gc_descr_has_references ((mword)(c)->gc_descr))
143 /* helper macros to scan and traverse objects, macros because we resue them in many functions */
144 #define OBJ_RUN_LEN_SIZE(size,desc,obj) do { \
145 (size) = ((desc) & 0xfff8); \
148 #define OBJ_BITMAP_SIZE(size,desc,obj) do { \
149 (size) = ((desc) & 0xfff8); \
153 #define PREFETCH(addr) __builtin_prefetch ((addr))
155 #define PREFETCH(addr)
158 /* code using these macros must define a HANDLE_PTR(ptr) macro that does the work */
159 #define OBJ_RUN_LEN_FOREACH_PTR(desc,obj) do { \
160 if ((desc) & 0xffff0000) { \
161 /* there are pointers */ \
162 void **_objptr_end; \
163 void **_objptr = (void**)(obj); \
164 _objptr += ((desc) >> 16) & 0xff; \
165 _objptr_end = _objptr + (((desc) >> 24) & 0xff); \
166 while (_objptr < _objptr_end) { \
167 HANDLE_PTR (_objptr, (obj)); \
173 #define OBJ_BITMAP_FOREACH_PTR(desc,obj) do { \
174 /* there are pointers */ \
175 void **_objptr = (void**)(obj); \
176 gsize _bmap = (desc) >> 16; \
177 _objptr += OBJECT_HEADER_WORDS; \
180 HANDLE_PTR (_objptr, (obj)); \
187 /* a bitmap desc means that there are pointer references or we'd have
188 * choosen run-length, instead: add an assert to check.
190 #define OBJ_LARGE_BITMAP_FOREACH_PTR(desc,obj) do { \
191 /* there are pointers */ \
192 void **_objptr = (void**)(obj); \
193 gsize _bmap = (desc) >> LOW_TYPE_BITS; \
194 _objptr += OBJECT_HEADER_WORDS; \
197 HANDLE_PTR (_objptr, (obj)); \
204 #define OBJ_COMPLEX_FOREACH_PTR(vt,obj) do { \
205 /* there are pointers */ \
206 void **_objptr = (void**)(obj); \
207 gsize *bitmap_data = sgen_get_complex_descriptor ((desc)); \
208 int bwords = (*bitmap_data) - 1; \
209 void **start_run = _objptr; \
212 MonoObject *myobj = (MonoObject*)obj; \
213 g_print ("found %d at %p (0x%zx): %s.%s\n", bwords, (obj), (desc), myobj->vtable->klass->name_space, myobj->vtable->klass->name); \
215 while (bwords-- > 0) { \
216 gsize _bmap = *bitmap_data++; \
217 _objptr = start_run; \
218 /*g_print ("bitmap: 0x%x/%d at %p\n", _bmap, bwords, _objptr);*/ \
221 HANDLE_PTR (_objptr, (obj)); \
226 start_run += GC_BITS_PER_WORD; \
230 /* this one is untested */
231 #define OBJ_COMPLEX_ARR_FOREACH_PTR(vt,obj) do { \
232 /* there are pointers */ \
233 gsize *mbitmap_data = sgen_get_complex_descriptor ((vt)->desc); \
234 int mbwords = (*mbitmap_data++) - 1; \
235 int el_size = mono_array_element_size (vt->klass); \
236 char *e_start = (char*)(obj) + G_STRUCT_OFFSET (MonoArray, vector); \
237 char *e_end = e_start + el_size * mono_array_length_fast ((MonoArray*)(obj)); \
239 g_print ("found %d at %p (0x%zx): %s.%s\n", mbwords, (obj), (vt)->desc, vt->klass->name_space, vt->klass->name); \
240 while (e_start < e_end) { \
241 void **_objptr = (void**)e_start; \
242 gsize *bitmap_data = mbitmap_data; \
243 unsigned int bwords = mbwords; \
244 while (bwords-- > 0) { \
245 gsize _bmap = *bitmap_data++; \
246 void **start_run = _objptr; \
247 /*g_print ("bitmap: 0x%x\n", _bmap);*/ \
250 HANDLE_PTR (_objptr, (obj)); \
255 _objptr = start_run + GC_BITS_PER_WORD; \
257 e_start += el_size; \
261 #define OBJ_VECTOR_FOREACH_PTR(desc,obj) do { \
262 /* note: 0xffffc000 excludes DESC_TYPE_V_PTRFREE */ \
263 if ((desc) & 0xffffc000) { \
264 int el_size = ((desc) >> 3) & MAX_ELEMENT_SIZE; \
265 /* there are pointers */ \
266 int etype = (desc) & 0xc000; \
267 if (etype == (DESC_TYPE_V_REFS << 14)) { \
268 void **p = (void**)((char*)(obj) + G_STRUCT_OFFSET (MonoArray, vector)); \
269 void **end_refs = (void**)((char*)p + el_size * mono_array_length_fast ((MonoArray*)(obj))); \
270 /* Note: this code can handle also arrays of struct with only references in them */ \
271 while (p < end_refs) { \
272 HANDLE_PTR (p, (obj)); \
275 } else if (etype == DESC_TYPE_V_RUN_LEN << 14) { \
276 int offset = ((desc) >> 16) & 0xff; \
277 int num_refs = ((desc) >> 24) & 0xff; \
278 char *e_start = (char*)(obj) + G_STRUCT_OFFSET (MonoArray, vector); \
279 char *e_end = e_start + el_size * mono_array_length_fast ((MonoArray*)(obj)); \
280 while (e_start < e_end) { \
281 void **p = (void**)e_start; \
284 for (i = 0; i < num_refs; ++i) { \
285 HANDLE_PTR (p + i, (obj)); \
287 e_start += el_size; \
289 } else if (etype == DESC_TYPE_V_BITMAP << 14) { \
290 char *e_start = (char*)(obj) + G_STRUCT_OFFSET (MonoArray, vector); \
291 char *e_end = e_start + el_size * mono_array_length_fast ((MonoArray*)(obj)); \
292 while (e_start < e_end) { \
293 void **p = (void**)e_start; \
294 gsize _bmap = (desc) >> 16; \
295 /* Note: there is no object header here to skip */ \
298 HANDLE_PTR (p, (obj)); \
303 e_start += el_size; \