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 * This library is free software; you can redistribute it and/or
11 * modify it under the terms of the GNU Library General Public
12 * License 2.0 as published by the Free Software Foundation;
14 * This library is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 * Library General Public License for more details.
19 * You should have received a copy of the GNU Library General Public
20 * License 2.0 along with this library; if not, write to the Free
21 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
23 #ifndef __MONO_SGEN_DESCRIPTOR_H__
24 #define __MONO_SGEN_DESCRIPTOR_H__
26 #include <mono/metadata/gc-internal.h>
27 #include <mono/metadata/sgen-conf.h>
31 * ######################################################################
32 * ######## GC descriptors
33 * ######################################################################
34 * Used to quickly get the info the GC needs about an object: size and
35 * where the references are held.
37 #define OBJECT_HEADER_WORDS (sizeof(MonoObject)/sizeof(gpointer))
38 #define LOW_TYPE_BITS 3
39 #define MAX_RUNLEN_OBJECT_SIZE 0xFFFF
40 #define SMALL_BITMAP_SHIFT 16
41 #define SMALL_BITMAP_SIZE (GC_BITS_PER_WORD - SMALL_BITMAP_SHIFT)
42 #define VECTOR_INFO_SHIFT 14
43 #define VECTOR_KIND_SHIFT 13
44 #define VECTOR_ELSIZE_SHIFT 3
45 #define LARGE_BITMAP_SIZE (GC_BITS_PER_WORD - LOW_TYPE_BITS)
46 #define MAX_ELEMENT_SIZE 0x3ff
47 #define VECTOR_SUBTYPE_PTRFREE (DESC_TYPE_V_PTRFREE << VECTOR_INFO_SHIFT)
48 #define VECTOR_SUBTYPE_REFS (DESC_TYPE_V_REFS << VECTOR_INFO_SHIFT)
49 #define VECTOR_SUBTYPE_RUN_LEN (DESC_TYPE_V_RUN_LEN << VECTOR_INFO_SHIFT)
50 #define VECTOR_SUBTYPE_BITMAP (DESC_TYPE_V_BITMAP << VECTOR_INFO_SHIFT)
52 #define VECTOR_KIND_SZARRAY (DESC_TYPE_V_SZARRAY << VECTOR_KIND_SHIFT)
53 #define VECTOR_KIND_ARRAY (DESC_TYPE_V_ARRAY << VECTOR_KIND_SHIFT)
55 /* objects are aligned to 8 bytes boundaries
56 * A descriptor is a pointer in MonoVTable, so 32 or 64 bits of size.
57 * The low 3 bits define the type of the descriptor. The other bits
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
75 * We don't use 0 so that 0 isn't a valid GC descriptor. No
76 * deep reason for this other than to be able to identify a
77 * non-inited descriptor for debugging.
79 * If an object contains no references, its GC descriptor is
80 * always DESC_TYPE_RUN_LENGTH, without a size, no exceptions.
81 * This is so that we can quickly check for that in
82 * copy_object_no_checks(), without having to fetch the
85 DESC_TYPE_RUN_LENGTH = 1, /* 16 bits aligned byte size | 1-3 (offset, numptr) bytes tuples */
86 DESC_TYPE_SMALL_BITMAP = 2, /* 16 bits aligned byte size | 16-48 bit bitmap */
87 DESC_TYPE_COMPLEX = 3, /* index for bitmap into complex_descriptors */
88 DESC_TYPE_VECTOR = 4, /* 10 bits element size | 1 bit kind | 2 bits desc | element desc */
89 DESC_TYPE_LARGE_BITMAP = 5, /* | 29-61 bitmap bits */
90 DESC_TYPE_COMPLEX_ARR = 6, /* index for bitmap into complex_descriptors */
91 DESC_TYPE_COMPLEX_PTRFREE = 7, /*Nothing, used to encode large ptr objects. */
93 /* values for array kind */
94 DESC_TYPE_V_SZARRAY = 0, /*vector with no bounds data */
95 DESC_TYPE_V_ARRAY = 1, /* array with bounds data */
96 /* subtypes for arrays and vectors */
97 DESC_TYPE_V_PTRFREE = 0,/* there are no refs: keep first so it has a zero value */
98 DESC_TYPE_V_REFS, /* all the array elements are refs */
99 DESC_TYPE_V_RUN_LEN, /* elements are run-length encoded as DESC_TYPE_RUN_LENGTH */
100 DESC_TYPE_V_BITMAP /* elements are as the bitmap in DESC_TYPE_SMALL_BITMAP */
103 /* Root bitmap descriptors are simpler: the lower three bits describe the type
104 * and we either have 30/62 bitmap bits or nibble-based run-length,
105 * or a complex descriptor, or a user defined marker function.
108 ROOT_DESC_CONSERVATIVE, /* 0, so matches NULL value */
113 ROOT_DESC_TYPE_MASK = 0x7,
114 ROOT_DESC_TYPE_SHIFT = 3,
117 gsize* sgen_get_complex_descriptor (mword desc) MONO_INTERNAL;
118 void* sgen_get_complex_descriptor_bitmap (mword desc) MONO_INTERNAL;
119 MonoGCRootMarkFunc sgen_get_user_descriptor_func (mword desc) MONO_INTERNAL;
121 void sgen_init_descriptors (void) MONO_INTERNAL;
123 #ifdef HEAVY_STATISTICS
124 void sgen_descriptor_count_scanned_object (mword desc) MONO_INTERNAL;
127 static inline gboolean
128 sgen_gc_descr_has_references (mword desc)
130 /*Both string and fixed size objects are encoded using a zero run RUN_LEN*/
131 if ((desc & 0xffff0007) == DESC_TYPE_RUN_LENGTH)
134 /*The array is ptr-free*/
135 if ((desc & 0xC007) == (DESC_TYPE_VECTOR | VECTOR_SUBTYPE_PTRFREE))
138 if ((desc & 0x7) == DESC_TYPE_COMPLEX_PTRFREE)
144 #define SGEN_VTABLE_HAS_REFERENCES(vt) (sgen_gc_descr_has_references ((mword)((MonoVTable*)(vt))->gc_descr))
145 #define SGEN_CLASS_HAS_REFERENCES(c) (sgen_gc_descr_has_references ((mword)(c)->gc_descr))
146 #define SGEN_OBJECT_HAS_REFERENCES(o) (SGEN_VTABLE_HAS_REFERENCES (SGEN_LOAD_VTABLE ((o))))
148 /* helper macros to scan and traverse objects, macros because we resue them in many functions */
149 #define OBJ_RUN_LEN_SIZE(size,desc,obj) do { \
150 (size) = ((desc) & 0xfff8); \
153 #define OBJ_BITMAP_SIZE(size,desc,obj) do { \
154 (size) = ((desc) & 0xfff8); \
158 #define PREFETCH(addr) __builtin_prefetch ((addr))
160 #define PREFETCH(addr)
163 #if defined(__GNUC__) && SIZEOF_VOID_P==4
164 #define GNUC_BUILTIN_CTZ(bmap) __builtin_ctz(bmap)
165 #elif defined(__GNUC__) && SIZEOF_VOID_P==8
166 #define GNUC_BUILTIN_CTZ(bmap) __builtin_ctzl(bmap)
169 /* code using these macros must define a HANDLE_PTR(ptr) macro that does the work */
170 #define OBJ_RUN_LEN_FOREACH_PTR(desc,obj) do { \
171 if ((desc) & 0xffff0000) { \
172 /* there are pointers */ \
173 void **_objptr_end; \
174 void **_objptr = (void**)(obj); \
175 _objptr += ((desc) >> 16) & 0xff; \
176 _objptr_end = _objptr + (((desc) >> 24) & 0xff); \
177 while (_objptr < _objptr_end) { \
178 HANDLE_PTR (_objptr, (obj)); \
184 #if defined(__GNUC__)
185 #define OBJ_BITMAP_FOREACH_PTR(desc,obj) do { \
186 /* there are pointers */ \
187 void **_objptr = (void**)(obj); \
188 gsize _bmap = (desc) >> 16; \
189 _objptr += OBJECT_HEADER_WORDS; \
191 int _index = GNUC_BUILTIN_CTZ (_bmap); \
193 _bmap >>= (_index + 1); \
194 HANDLE_PTR (_objptr, (obj)); \
199 #define OBJ_BITMAP_FOREACH_PTR(desc,obj) do { \
200 /* there are pointers */ \
201 void **_objptr = (void**)(obj); \
202 gsize _bmap = (desc) >> 16; \
203 _objptr += OBJECT_HEADER_WORDS; \
206 HANDLE_PTR (_objptr, (obj)); \
214 /* a bitmap desc means that there are pointer references or we'd have
215 * choosen run-length, instead: add an assert to check.
217 #define OBJ_LARGE_BITMAP_FOREACH_PTR(desc,obj) do { \
218 /* there are pointers */ \
219 void **_objptr = (void**)(obj); \
220 gsize _bmap = (desc) >> LOW_TYPE_BITS; \
221 _objptr += OBJECT_HEADER_WORDS; \
224 HANDLE_PTR (_objptr, (obj)); \
231 #define OBJ_COMPLEX_FOREACH_PTR(vt,obj) do { \
232 /* there are pointers */ \
233 void **_objptr = (void**)(obj); \
234 gsize *bitmap_data = sgen_get_complex_descriptor ((desc)); \
235 gsize bwords = (*bitmap_data) - 1; \
236 void **start_run = _objptr; \
239 MonoObject *myobj = (MonoObject*)obj; \
240 g_print ("found %d at %p (0x%zx): %s.%s\n", bwords, (obj), (desc), myobj->vtable->klass->name_space, myobj->vtable->klass->name); \
242 while (bwords-- > 0) { \
243 gsize _bmap = *bitmap_data++; \
244 _objptr = start_run; \
245 /*g_print ("bitmap: 0x%x/%d at %p\n", _bmap, bwords, _objptr);*/ \
248 HANDLE_PTR (_objptr, (obj)); \
253 start_run += GC_BITS_PER_WORD; \
257 /* this one is untested */
258 #define OBJ_COMPLEX_ARR_FOREACH_PTR(desc,obj) do { \
259 /* there are pointers */ \
260 GCVTable *vt = (GCVTable*)SGEN_LOAD_VTABLE (obj); \
261 gsize *mbitmap_data = sgen_get_complex_descriptor ((desc)); \
262 gsize mbwords = (*mbitmap_data++) - 1; \
263 gsize el_size = mono_array_element_size (vt->klass); \
264 char *e_start = (char*)(obj) + G_STRUCT_OFFSET (MonoArray, vector); \
265 char *e_end = e_start + el_size * mono_array_length_fast ((MonoArray*)(obj)); \
267 g_print ("found %d at %p (0x%zx): %s.%s\n", mbwords, (obj), (desc), (vt)->klass->name_space, (vt)->klass->name); \
268 while (e_start < e_end) { \
269 void **_objptr = (void**)e_start; \
270 gsize *bitmap_data = mbitmap_data; \
271 gsize bwords = mbwords; \
272 while (bwords-- > 0) { \
273 gsize _bmap = *bitmap_data++; \
274 void **start_run = _objptr; \
275 /*g_print ("bitmap: 0x%x\n", _bmap);*/ \
278 HANDLE_PTR (_objptr, (obj)); \
283 _objptr = start_run + GC_BITS_PER_WORD; \
285 e_start += el_size; \
289 #define OBJ_VECTOR_FOREACH_PTR(desc,obj) do { \
290 /* note: 0xffffc000 excludes DESC_TYPE_V_PTRFREE */ \
291 if ((desc) & 0xffffc000) { \
292 int el_size = ((desc) >> 3) & MAX_ELEMENT_SIZE; \
293 /* there are pointers */ \
294 int etype = (desc) & 0xc000; \
295 if (etype == (DESC_TYPE_V_REFS << 14)) { \
296 void **p = (void**)((char*)(obj) + G_STRUCT_OFFSET (MonoArray, vector)); \
297 void **end_refs = (void**)((char*)p + el_size * mono_array_length_fast ((MonoArray*)(obj))); \
298 /* Note: this code can handle also arrays of struct with only references in them */ \
299 while (p < end_refs) { \
300 HANDLE_PTR (p, (obj)); \
303 } else if (etype == DESC_TYPE_V_RUN_LEN << 14) { \
304 int offset = ((desc) >> 16) & 0xff; \
305 int num_refs = ((desc) >> 24) & 0xff; \
306 char *e_start = (char*)(obj) + G_STRUCT_OFFSET (MonoArray, vector); \
307 char *e_end = e_start + el_size * mono_array_length_fast ((MonoArray*)(obj)); \
308 while (e_start < e_end) { \
309 void **p = (void**)e_start; \
312 for (i = 0; i < num_refs; ++i) { \
313 HANDLE_PTR (p + i, (obj)); \
315 e_start += el_size; \
317 } else if (etype == DESC_TYPE_V_BITMAP << 14) { \
318 char *e_start = (char*)(obj) + G_STRUCT_OFFSET (MonoArray, vector); \
319 char *e_end = e_start + el_size * mono_array_length_fast ((MonoArray*)(obj)); \
320 while (e_start < e_end) { \
321 void **p = (void**)e_start; \
322 gsize _bmap = (desc) >> 16; \
323 /* Note: there is no object header here to skip */ \
326 HANDLE_PTR (p, (obj)); \
331 e_start += el_size; \