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, /* 16 bits aligned byte size | 16-48 bit bitmap */
87 DESC_TYPE_COMPLEX, /* index for bitmap into complex_descriptors */
88 DESC_TYPE_VECTOR, /* 10 bits element size | 1 bit kind | 2 bits desc | element desc */
89 DESC_TYPE_LARGE_BITMAP, /* | 29-61 bitmap bits */
90 DESC_TYPE_COMPLEX_ARR, /* index for bitmap into complex_descriptors */
91 DESC_TYPE_COMPLEX_PTRFREE, /*Nothing, used to encode large ptr objects. */
92 /* values for array kind */
93 DESC_TYPE_V_SZARRAY = 0, /*vector with no bounds data */
94 DESC_TYPE_V_ARRAY = 1, /* array with bounds data */
95 /* subtypes for arrays and vectors */
96 DESC_TYPE_V_PTRFREE = 0,/* there are no refs: keep first so it has a zero value */
97 DESC_TYPE_V_REFS, /* all the array elements are refs */
98 DESC_TYPE_V_RUN_LEN, /* elements are run-length encoded as DESC_TYPE_RUN_LENGTH */
99 DESC_TYPE_V_BITMAP /* elements are as the bitmap in DESC_TYPE_SMALL_BITMAP */
102 /* Root bitmap descriptors are simpler: the lower three bits describe the type
103 * and we either have 30/62 bitmap bits or nibble-based run-length,
104 * or a complex descriptor, or a user defined marker function.
107 ROOT_DESC_CONSERVATIVE, /* 0, so matches NULL value */
112 ROOT_DESC_TYPE_MASK = 0x7,
113 ROOT_DESC_TYPE_SHIFT = 3,
116 gsize* sgen_get_complex_descriptor (mword desc) MONO_INTERNAL;
117 void* sgen_get_complex_descriptor_bitmap (mword desc) MONO_INTERNAL;
118 MonoGCRootMarkFunc sgen_get_user_descriptor_func (mword desc) MONO_INTERNAL;
121 static inline gboolean
122 sgen_gc_descr_has_references (mword desc)
124 /*Both string and fixed size objects are encoded using a zero run RUN_LEN*/
125 if ((desc & 0xffff0007) == DESC_TYPE_RUN_LENGTH)
128 /*The array is ptr-free*/
129 if ((desc & 0xC007) == (DESC_TYPE_VECTOR | VECTOR_SUBTYPE_PTRFREE))
132 if ((desc & 0x7) == DESC_TYPE_COMPLEX_PTRFREE)
138 #define SGEN_VTABLE_HAS_REFERENCES(vt) (sgen_gc_descr_has_references ((mword)((MonoVTable*)(vt))->gc_descr))
139 #define SGEN_CLASS_HAS_REFERENCES(c) (sgen_gc_descr_has_references ((mword)(c)->gc_descr))
141 /* helper macros to scan and traverse objects, macros because we resue them in many functions */
142 #define OBJ_RUN_LEN_SIZE(size,desc,obj) do { \
143 (size) = ((desc) & 0xfff8); \
146 #define OBJ_BITMAP_SIZE(size,desc,obj) do { \
147 (size) = ((desc) & 0xfff8); \
151 #define PREFETCH(addr) __builtin_prefetch ((addr))
153 #define PREFETCH(addr)
156 /* code using these macros must define a HANDLE_PTR(ptr) macro that does the work */
157 #define OBJ_RUN_LEN_FOREACH_PTR(desc,obj) do { \
158 if ((desc) & 0xffff0000) { \
159 /* there are pointers */ \
160 void **_objptr_end; \
161 void **_objptr = (void**)(obj); \
162 _objptr += ((desc) >> 16) & 0xff; \
163 _objptr_end = _objptr + (((desc) >> 24) & 0xff); \
164 HANDLE_PTR (_objptr, (obj)); \
166 while (_objptr < _objptr_end) { \
167 HANDLE_PTR (_objptr, (obj)); \
174 #define OBJ_BITMAP_FOREACH_PTR(desc,obj) do { \
175 /* there are pointers */ \
176 void **_objptr = (void**)(obj); \
177 gsize _bmap = (desc) >> 16; \
178 _objptr += OBJECT_HEADER_WORDS; \
180 int _index = __builtin_ctz (_bmap); \
182 _bmap >>= (_index + 1); \
183 HANDLE_PTR (_objptr, (obj)); \
187 int _index = __builtin_ctz (_bmap); \
189 _bmap >>= (_index + 1); \
190 HANDLE_PTR (_objptr, (obj)); \
195 #define OBJ_BITMAP_FOREACH_PTR(desc,obj) do { \
196 /* there are pointers */ \
197 void **_objptr = (void**)(obj); \
198 gsize _bmap = (desc) >> 16; \
199 _objptr += OBJECT_HEADER_WORDS; \
202 HANDLE_PTR (_objptr, (obj)); \
210 /* a bitmap desc means that there are pointer references or we'd have
211 * choosen run-length, instead: add an assert to check.
213 #define OBJ_LARGE_BITMAP_FOREACH_PTR(desc,obj) do { \
214 /* there are pointers */ \
215 void **_objptr = (void**)(obj); \
216 gsize _bmap = (desc) >> LOW_TYPE_BITS; \
217 _objptr += OBJECT_HEADER_WORDS; \
220 HANDLE_PTR (_objptr, (obj)); \
227 #define OBJ_COMPLEX_FOREACH_PTR(vt,obj) do { \
228 /* there are pointers */ \
229 void **_objptr = (void**)(obj); \
230 gsize *bitmap_data = sgen_get_complex_descriptor ((desc)); \
231 int bwords = (*bitmap_data) - 1; \
232 void **start_run = _objptr; \
235 MonoObject *myobj = (MonoObject*)obj; \
236 g_print ("found %d at %p (0x%zx): %s.%s\n", bwords, (obj), (desc), myobj->vtable->klass->name_space, myobj->vtable->klass->name); \
238 while (bwords-- > 0) { \
239 gsize _bmap = *bitmap_data++; \
240 _objptr = start_run; \
241 /*g_print ("bitmap: 0x%x/%d at %p\n", _bmap, bwords, _objptr);*/ \
244 HANDLE_PTR (_objptr, (obj)); \
249 start_run += GC_BITS_PER_WORD; \
253 /* this one is untested */
254 #define OBJ_COMPLEX_ARR_FOREACH_PTR(vt,obj) do { \
255 /* there are pointers */ \
256 gsize *mbitmap_data = sgen_get_complex_descriptor ((vt)->desc); \
257 int mbwords = (*mbitmap_data++) - 1; \
258 int el_size = mono_array_element_size (vt->klass); \
259 char *e_start = (char*)(obj) + G_STRUCT_OFFSET (MonoArray, vector); \
260 char *e_end = e_start + el_size * mono_array_length_fast ((MonoArray*)(obj)); \
262 g_print ("found %d at %p (0x%zx): %s.%s\n", mbwords, (obj), (vt)->desc, vt->klass->name_space, vt->klass->name); \
263 while (e_start < e_end) { \
264 void **_objptr = (void**)e_start; \
265 gsize *bitmap_data = mbitmap_data; \
266 unsigned int bwords = mbwords; \
267 while (bwords-- > 0) { \
268 gsize _bmap = *bitmap_data++; \
269 void **start_run = _objptr; \
270 /*g_print ("bitmap: 0x%x\n", _bmap);*/ \
273 HANDLE_PTR (_objptr, (obj)); \
278 _objptr = start_run + GC_BITS_PER_WORD; \
280 e_start += el_size; \
284 #define OBJ_VECTOR_FOREACH_PTR(desc,obj) do { \
285 /* note: 0xffffc000 excludes DESC_TYPE_V_PTRFREE */ \
286 if ((desc) & 0xffffc000) { \
287 int el_size = ((desc) >> 3) & MAX_ELEMENT_SIZE; \
288 /* there are pointers */ \
289 int etype = (desc) & 0xc000; \
290 if (etype == (DESC_TYPE_V_REFS << 14)) { \
291 void **p = (void**)((char*)(obj) + G_STRUCT_OFFSET (MonoArray, vector)); \
292 void **end_refs = (void**)((char*)p + el_size * mono_array_length_fast ((MonoArray*)(obj))); \
293 /* Note: this code can handle also arrays of struct with only references in them */ \
294 while (p < end_refs) { \
295 HANDLE_PTR (p, (obj)); \
298 } else if (etype == DESC_TYPE_V_RUN_LEN << 14) { \
299 int offset = ((desc) >> 16) & 0xff; \
300 int num_refs = ((desc) >> 24) & 0xff; \
301 char *e_start = (char*)(obj) + G_STRUCT_OFFSET (MonoArray, vector); \
302 char *e_end = e_start + el_size * mono_array_length_fast ((MonoArray*)(obj)); \
303 while (e_start < e_end) { \
304 void **p = (void**)e_start; \
307 for (i = 0; i < num_refs; ++i) { \
308 HANDLE_PTR (p + i, (obj)); \
310 e_start += el_size; \
312 } else if (etype == DESC_TYPE_V_BITMAP << 14) { \
313 char *e_start = (char*)(obj) + G_STRUCT_OFFSET (MonoArray, vector); \
314 char *e_end = e_start + el_size * mono_array_length_fast ((MonoArray*)(obj)); \
315 while (e_start < e_end) { \
316 void **p = (void**)e_start; \
317 gsize _bmap = (desc) >> 16; \
318 /* Note: there is no object header here to skip */ \
321 HANDLE_PTR (p, (obj)); \
326 e_start += el_size; \