Fix roslyn install with AOT disabled.
[mono-project.git] / mono / sgen / sgen-descriptor.h
blob54e1b7681fbe3fbb48a3c5385888b8b0d3567922
1 /*
2 * sgen-descriptor.h: GC descriptors describe object layout.
4 * Copyright 2001-2003 Ximian, Inc
5 * Copyright 2003-2010 Novell, Inc.
6 * 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.
12 #ifndef __MONO_SGEN_DESCRIPTOR_H__
13 #define __MONO_SGEN_DESCRIPTOR_H__
15 #include <mono/sgen/sgen-conf.h>
18 * ######################################################################
19 * ######## GC descriptors
20 * ######################################################################
21 * Used to quickly get the info the GC needs about an object: size and
22 * where the references are held.
24 #define OBJECT_HEADER_WORDS (SGEN_CLIENT_OBJECT_HEADER_SIZE / sizeof(gpointer))
25 #define LOW_TYPE_BITS 3
26 #define DESC_TYPE_MASK ((1 << LOW_TYPE_BITS) - 1)
27 #define MAX_RUNLEN_OBJECT_SIZE 0xFFFF
28 #define VECTOR_INFO_SHIFT 14
29 #define VECTOR_KIND_SHIFT 13
30 #define VECTOR_ELSIZE_SHIFT 3
31 #define VECTOR_BITMAP_SHIFT 16
32 #define VECTOR_BITMAP_SIZE (GC_BITS_PER_WORD - VECTOR_BITMAP_SHIFT)
33 #define BITMAP_NUM_BITS (GC_BITS_PER_WORD - LOW_TYPE_BITS)
34 #define MAX_ELEMENT_SIZE 0x3ff
35 #define VECTOR_SUBTYPE_PTRFREE (DESC_TYPE_V_PTRFREE << VECTOR_INFO_SHIFT)
36 #define VECTOR_SUBTYPE_REFS (DESC_TYPE_V_REFS << VECTOR_INFO_SHIFT)
37 #define VECTOR_SUBTYPE_BITMAP (DESC_TYPE_V_BITMAP << VECTOR_INFO_SHIFT)
39 #define VECTOR_KIND_SZARRAY (DESC_TYPE_V_SZARRAY << VECTOR_KIND_SHIFT)
40 #define VECTOR_KIND_ARRAY (DESC_TYPE_V_ARRAY << VECTOR_KIND_SHIFT)
43 * Objects are aligned to 8 bytes boundaries.
45 * A descriptor is a pointer in GCVTable, so 32 or 64 bits of size.
46 * The low 3 bits define the type of the descriptor. The other bits
47 * depend on the type.
49 * It's important to be able to quickly identify two properties of classes from their
50 * descriptors: whether they are small enough to live in the regular major heap (size <=
51 * SGEN_MAX_SMALL_OBJ_SIZE), and whether they contain references.
53 * To that end we have three descriptor types that only apply to small classes: RUN_LENGTH,
54 * BITMAP, and SMALL_PTRFREE. We also have the type COMPLEX_PTRFREE, which applies to
55 * classes that are either not small or of unknown size (those being strings and arrays).
56 * The lowest two bits of the SMALL_PTRFREE and COMPLEX_PTRFREE tags are the same, so we can
57 * quickly check for references.
59 * As a general rule the 13 remaining low bits define the size, either
60 * of the whole object or of the elements in the arrays. While for objects
61 * the size is already in bytes, for arrays we need to shift, because
62 * array elements might be smaller than 8 bytes. In case of arrays, we
63 * use two bits to describe what the additional high bits represents,
64 * so the default behaviour can handle element sizes less than 2048 bytes.
65 * The high 16 bits, if 0 it means the object is pointer-free.
66 * This design should make it easy and fast to skip over ptr-free data.
67 * The first 4 types should cover >95% of the objects.
68 * Note that since the size of objects is limited to 64K, larger objects
69 * will be allocated in the large object heap.
70 * If we want 4-bytes alignment, we need to put vector and small bitmap
71 * inside complex.
73 * We don't use 0 so that 0 isn't a valid GC descriptor. No deep reason for this other than
74 * to be able to identify a non-inited descriptor for debugging.
76 enum {
77 /* Keep in sync with `descriptor_types` in sgen-debug.c! */
78 DESC_TYPE_RUN_LENGTH = 1, /* 16 bits aligned byte size | 1-3 (offset, numptr) bytes tuples */
79 DESC_TYPE_BITMAP = 2, /* | 29-61 bitmap bits */
80 DESC_TYPE_SMALL_PTRFREE = 3,
81 DESC_TYPE_MAX_SMALL_OBJ = 3,
82 DESC_TYPE_COMPLEX = 4, /* index for bitmap into complex_descriptors */
83 DESC_TYPE_VECTOR = 5, /* 10 bits element size | 1 bit kind | 2 bits desc | element desc */
84 DESC_TYPE_COMPLEX_ARR = 6, /* index for bitmap into complex_descriptors */
85 DESC_TYPE_COMPLEX_PTRFREE = 7, /* Nothing, used to encode large ptr objects and strings. */
86 DESC_TYPE_MAX = 7,
88 DESC_TYPE_PTRFREE_MASK = 3,
89 DESC_TYPE_PTRFREE_BITS = 3
92 /* values for array kind */
93 enum {
94 DESC_TYPE_V_SZARRAY = 0, /*vector with no bounds data */
95 DESC_TYPE_V_ARRAY = 1, /* array with bounds data */
98 /* subtypes for arrays and vectors */
99 enum {
100 DESC_TYPE_V_PTRFREE = 0,/* there are no refs: keep first so it has a zero value */
101 DESC_TYPE_V_REFS, /* all the array elements are refs */
102 DESC_TYPE_V_RUN_LEN, /* elements are run-length encoded as DESC_TYPE_RUN_LENGTH */
103 DESC_TYPE_V_BITMAP /* elements are as the bitmap in DESC_TYPE_SMALL_BITMAP */
106 #define SGEN_DESC_STRING (DESC_TYPE_COMPLEX_PTRFREE | (1 << LOW_TYPE_BITS))
108 /* Root bitmap descriptors are simpler: the lower three bits describe the type
109 * and we either have 30/62 bitmap bits or nibble-based run-length,
110 * or a complex descriptor, or a user defined marker function.
112 enum {
113 ROOT_DESC_CONSERVATIVE, /* 0, so matches NULL value */
114 ROOT_DESC_BITMAP,
115 ROOT_DESC_RUN_LEN,
116 ROOT_DESC_COMPLEX,
117 ROOT_DESC_USER,
118 ROOT_DESC_TYPE_MASK = 0x7,
119 ROOT_DESC_TYPE_SHIFT = 3,
122 typedef void (*SgenUserMarkFunc) (GCObject **addr, void *gc_data);
123 typedef void (*SgenUserRootMarkFunc) (void *addr, SgenUserMarkFunc mark_func, void *gc_data);
125 SgenDescriptor sgen_make_user_root_descriptor (SgenUserRootMarkFunc marker);
127 gsize* sgen_get_complex_descriptor (SgenDescriptor desc);
128 void* sgen_get_complex_descriptor_bitmap (SgenDescriptor desc);
129 SgenUserRootMarkFunc sgen_get_user_descriptor_func (SgenDescriptor desc);
131 void sgen_init_descriptors (void);
133 #ifdef HEAVY_STATISTICS
134 void sgen_descriptor_count_scanned_object (SgenDescriptor desc);
135 void sgen_descriptor_count_copied_object (SgenDescriptor desc);
136 #endif
138 static inline gboolean
139 sgen_gc_descr_has_references (SgenDescriptor desc)
141 /* This covers SMALL_PTRFREE and COMPLEX_PTRFREE */
142 if ((desc & DESC_TYPE_PTRFREE_MASK) == DESC_TYPE_PTRFREE_BITS)
143 return FALSE;
145 /*The array is ptr-free*/
146 if ((desc & 0xC007) == (DESC_TYPE_VECTOR | VECTOR_SUBTYPE_PTRFREE))
147 return FALSE;
149 return TRUE;
152 #define SGEN_VTABLE_HAS_REFERENCES(vt) (sgen_gc_descr_has_references (sgen_vtable_get_descriptor ((vt))))
153 #define SGEN_OBJECT_HAS_REFERENCES(o) (SGEN_VTABLE_HAS_REFERENCES (SGEN_LOAD_VTABLE ((o))))
155 /* helper macros to scan and traverse objects, macros because we resue them in many functions */
156 #ifdef __GNUC__
157 #define PREFETCH_READ(addr) __builtin_prefetch ((addr), 0, 1)
158 #define PREFETCH_WRITE(addr) __builtin_prefetch ((addr), 1, 1)
159 #else
160 #define PREFETCH_READ(addr)
161 #define PREFETCH_WRITE(addr)
162 #endif
164 #if defined(__GNUC__) && SIZEOF_VOID_P==4
165 #define GNUC_BUILTIN_CTZ(bmap) __builtin_ctz(bmap)
166 #elif defined(__GNUC__) && SIZEOF_VOID_P==8
167 #define GNUC_BUILTIN_CTZ(bmap) __builtin_ctzl(bmap)
168 #endif
170 /* code using these macros must define a HANDLE_PTR(ptr) macro that does the work */
171 #define OBJ_RUN_LEN_FOREACH_PTR(desc,obj) do { \
172 if ((desc) & 0xffff0000) { \
173 /* there are pointers */ \
174 void **_objptr_end; \
175 void **_objptr = (void**)(obj); \
176 _objptr += ((desc) >> 16) & 0xff; \
177 _objptr_end = _objptr + (((desc) >> 24) & 0xff); \
178 while (_objptr < _objptr_end) { \
179 HANDLE_PTR ((GCObject**)_objptr, (obj)); \
180 _objptr++; \
181 }; \
183 } while (0)
185 /* a bitmap desc means that there are pointer references or we'd have
186 * choosen run-length, instead: add an assert to check.
188 #ifdef __GNUC__
189 #define OBJ_BITMAP_FOREACH_PTR(desc,obj) do { \
190 /* there are pointers */ \
191 void **_objptr = (void**)(obj); \
192 gsize _bmap = (desc) >> LOW_TYPE_BITS; \
193 _objptr += OBJECT_HEADER_WORDS; \
194 do { \
195 int _index = GNUC_BUILTIN_CTZ (_bmap); \
196 _objptr += _index; \
197 _bmap >>= (_index + 1); \
198 HANDLE_PTR ((GCObject**)_objptr, (obj)); \
199 ++_objptr; \
200 } while (_bmap); \
201 } while (0)
202 #else
203 #define OBJ_BITMAP_FOREACH_PTR(desc,obj) do { \
204 /* there are pointers */ \
205 void **_objptr = (void**)(obj); \
206 gsize _bmap = (desc) >> LOW_TYPE_BITS; \
207 _objptr += OBJECT_HEADER_WORDS; \
208 do { \
209 if ((_bmap & 1)) { \
210 HANDLE_PTR ((GCObject**)_objptr, (obj)); \
212 _bmap >>= 1; \
213 ++_objptr; \
214 } while (_bmap); \
215 } while (0)
216 #endif
218 #define OBJ_COMPLEX_FOREACH_PTR(desc,obj) do { \
219 /* there are pointers */ \
220 void **_objptr = (void**)(obj); \
221 gsize *bitmap_data = sgen_get_complex_descriptor ((desc)); \
222 gsize bwords = (*bitmap_data) - 1; \
223 void **start_run = _objptr; \
224 bitmap_data++; \
225 while (bwords-- > 0) { \
226 gsize _bmap = *bitmap_data++; \
227 _objptr = start_run; \
228 /*g_print ("bitmap: 0x%x/%d at %p\n", _bmap, bwords, _objptr);*/ \
229 while (_bmap) { \
230 if ((_bmap & 1)) { \
231 HANDLE_PTR ((GCObject**)_objptr, (obj)); \
233 _bmap >>= 1; \
234 ++_objptr; \
236 start_run += GC_BITS_PER_WORD; \
238 } while (0)
240 /* this one is untested */
241 #define OBJ_COMPLEX_ARR_FOREACH_PTR(desc,obj) do { \
242 /* there are pointers */ \
243 GCVTable vt = SGEN_LOAD_VTABLE (obj); \
244 gsize *mbitmap_data = sgen_get_complex_descriptor ((desc)); \
245 gsize mbwords = (*mbitmap_data++) - 1; \
246 gsize el_size = sgen_client_array_element_size (vt); \
247 char *e_start = sgen_client_array_data_start ((GCObject*)(obj)); \
248 char *e_end = e_start + el_size * sgen_client_array_length ((GCObject*)(obj)); \
249 while (e_start < e_end) { \
250 void **_objptr = (void**)e_start; \
251 gsize *bitmap_data = mbitmap_data; \
252 gsize bwords = mbwords; \
253 while (bwords-- > 0) { \
254 gsize _bmap = *bitmap_data++; \
255 void **start_run = _objptr; \
256 /*g_print ("bitmap: 0x%x\n", _bmap);*/ \
257 while (_bmap) { \
258 if ((_bmap & 1)) { \
259 HANDLE_PTR ((GCObject**)_objptr, (obj)); \
261 _bmap >>= 1; \
262 ++_objptr; \
264 _objptr = start_run + GC_BITS_PER_WORD; \
266 e_start += el_size; \
268 } while (0)
270 #define OBJ_VECTOR_FOREACH_PTR(desc,obj) do { \
271 /* note: 0xffffc000 excludes DESC_TYPE_V_PTRFREE */ \
272 if ((desc) & 0xffffc000) { \
273 int el_size = ((desc) >> 3) & MAX_ELEMENT_SIZE; \
274 /* there are pointers */ \
275 int etype = (desc) & 0xc000; \
276 if (etype == (DESC_TYPE_V_REFS << 14)) { \
277 void **p = (void**)sgen_client_array_data_start ((GCObject*)(obj)); \
278 void **end_refs = (void**)((char*)p + el_size * sgen_client_array_length ((GCObject*)(obj))); \
279 /* Note: this code can handle also arrays of struct with only references in them */ \
280 while (p < end_refs) { \
281 HANDLE_PTR ((GCObject**)p, (obj)); \
282 ++p; \
284 } else if (etype == DESC_TYPE_V_RUN_LEN << 14) { \
285 int offset = ((desc) >> 16) & 0xff; \
286 int num_refs = ((desc) >> 24) & 0xff; \
287 char *e_start = sgen_client_array_data_start ((GCObject*)(obj)); \
288 char *e_end = e_start + el_size * sgen_client_array_length ((GCObject*)(obj)); \
289 while (e_start < e_end) { \
290 void **p = (void**)e_start; \
291 int i; \
292 p += offset; \
293 for (i = 0; i < num_refs; ++i) { \
294 HANDLE_PTR ((GCObject**)p + i, (obj)); \
296 e_start += el_size; \
298 } else if (etype == DESC_TYPE_V_BITMAP << 14) { \
299 char *e_start = sgen_client_array_data_start ((GCObject*)(obj)); \
300 char *e_end = e_start + el_size * sgen_client_array_length ((GCObject*)(obj)); \
301 while (e_start < e_end) { \
302 void **p = (void**)e_start; \
303 gsize _bmap = (desc) >> 16; \
304 /* Note: there is no object header here to skip */ \
305 while (_bmap) { \
306 if ((_bmap & 1)) { \
307 HANDLE_PTR ((GCObject**)p, (obj)); \
309 _bmap >>= 1; \
310 ++p; \
312 e_start += el_size; \
316 } while (0)
319 #endif