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/sgen/sgen-conf.h>
29 * ######################################################################
30 * ######## GC descriptors
31 * ######################################################################
32 * Used to quickly get the info the GC needs about an object: size and
33 * where the references are held.
35 #define OBJECT_HEADER_WORDS (SGEN_CLIENT_OBJECT_HEADER_SIZE / sizeof(gpointer))
36 #define LOW_TYPE_BITS 3
37 #define DESC_TYPE_MASK ((1 << LOW_TYPE_BITS) - 1)
38 #define MAX_RUNLEN_OBJECT_SIZE 0xFFFF
39 #define VECTOR_INFO_SHIFT 14
40 #define VECTOR_KIND_SHIFT 13
41 #define VECTOR_ELSIZE_SHIFT 3
42 #define VECTOR_BITMAP_SHIFT 16
43 #define VECTOR_BITMAP_SIZE (GC_BITS_PER_WORD - VECTOR_BITMAP_SHIFT)
44 #define BITMAP_NUM_BITS (GC_BITS_PER_WORD - LOW_TYPE_BITS)
45 #define MAX_ELEMENT_SIZE 0x3ff
46 #define VECTOR_SUBTYPE_PTRFREE (DESC_TYPE_V_PTRFREE << VECTOR_INFO_SHIFT)
47 #define VECTOR_SUBTYPE_REFS (DESC_TYPE_V_REFS << VECTOR_INFO_SHIFT)
48 #define VECTOR_SUBTYPE_BITMAP (DESC_TYPE_V_BITMAP << VECTOR_INFO_SHIFT)
50 #define VECTOR_KIND_SZARRAY (DESC_TYPE_V_SZARRAY << VECTOR_KIND_SHIFT)
51 #define VECTOR_KIND_ARRAY (DESC_TYPE_V_ARRAY << VECTOR_KIND_SHIFT)
54 * Objects are aligned to 8 bytes boundaries.
56 * A descriptor is a pointer in GCVTable, so 32 or 64 bits of size.
57 * The low 3 bits define the type of the descriptor. The other bits
60 * It's important to be able to quickly identify two properties of classes from their
61 * descriptors: whether they are small enough to live in the regular major heap (size <=
62 * SGEN_MAX_SMALL_OBJ_SIZE), and whether they contain references.
64 * To that end we have three descriptor types that only apply to small classes: RUN_LENGTH,
65 * BITMAP, and SMALL_PTRFREE. We also have the type COMPLEX_PTRFREE, which applies to
66 * classes that are either not small or of unknown size (those being strings and arrays).
67 * The lowest two bits of the SMALL_PTRFREE and COMPLEX_PTRFREE tags are the same, so we can
68 * quickly check for references.
70 * As a general rule the 13 remaining low bits define the size, either
71 * of the whole object or of the elements in the arrays. While for objects
72 * the size is already in bytes, for arrays we need to shift, because
73 * array elements might be smaller than 8 bytes. In case of arrays, we
74 * use two bits to describe what the additional high bits represents,
75 * so the default behaviour can handle element sizes less than 2048 bytes.
76 * The high 16 bits, if 0 it means the object is pointer-free.
77 * This design should make it easy and fast to skip over ptr-free data.
78 * The first 4 types should cover >95% of the objects.
79 * Note that since the size of objects is limited to 64K, larger objects
80 * will be allocated in the large object heap.
81 * If we want 4-bytes alignment, we need to put vector and small bitmap
84 * We don't use 0 so that 0 isn't a valid GC descriptor. No deep reason for this other than
85 * to be able to identify a non-inited descriptor for debugging.
88 /* Keep in sync with `descriptor_types` in sgen-debug.c! */
89 DESC_TYPE_RUN_LENGTH = 1, /* 16 bits aligned byte size | 1-3 (offset, numptr) bytes tuples */
90 DESC_TYPE_BITMAP = 2, /* | 29-61 bitmap bits */
91 DESC_TYPE_SMALL_PTRFREE = 3,
92 DESC_TYPE_MAX_SMALL_OBJ = 3,
93 DESC_TYPE_COMPLEX = 4, /* index for bitmap into complex_descriptors */
94 DESC_TYPE_VECTOR = 5, /* 10 bits element size | 1 bit kind | 2 bits desc | element desc */
95 DESC_TYPE_COMPLEX_ARR = 6, /* index for bitmap into complex_descriptors */
96 DESC_TYPE_COMPLEX_PTRFREE = 7, /* Nothing, used to encode large ptr objects and strings. */
99 DESC_TYPE_PTRFREE_MASK = 3,
100 DESC_TYPE_PTRFREE_BITS = 3
103 /* values for array kind */
105 DESC_TYPE_V_SZARRAY = 0, /*vector with no bounds data */
106 DESC_TYPE_V_ARRAY = 1, /* array with bounds data */
109 /* subtypes for arrays and vectors */
111 DESC_TYPE_V_PTRFREE = 0,/* there are no refs: keep first so it has a zero value */
112 DESC_TYPE_V_REFS, /* all the array elements are refs */
113 DESC_TYPE_V_RUN_LEN, /* elements are run-length encoded as DESC_TYPE_RUN_LENGTH */
114 DESC_TYPE_V_BITMAP /* elements are as the bitmap in DESC_TYPE_SMALL_BITMAP */
117 #define SGEN_DESC_STRING (DESC_TYPE_COMPLEX_PTRFREE | (1 << LOW_TYPE_BITS))
119 /* Root bitmap descriptors are simpler: the lower three bits describe the type
120 * and we either have 30/62 bitmap bits or nibble-based run-length,
121 * or a complex descriptor, or a user defined marker function.
124 ROOT_DESC_CONSERVATIVE, /* 0, so matches NULL value */
129 ROOT_DESC_TYPE_MASK = 0x7,
130 ROOT_DESC_TYPE_SHIFT = 3,
133 typedef void (*SgenUserMarkFunc) (GCObject **addr, void *gc_data);
134 typedef void (*SgenUserRootMarkFunc) (void *addr, SgenUserMarkFunc mark_func, void *gc_data);
136 SgenDescriptor sgen_make_user_root_descriptor (SgenUserRootMarkFunc marker);
138 gsize* sgen_get_complex_descriptor (SgenDescriptor desc);
139 void* sgen_get_complex_descriptor_bitmap (SgenDescriptor desc);
140 SgenUserRootMarkFunc sgen_get_user_descriptor_func (SgenDescriptor desc);
142 void sgen_init_descriptors (void);
144 #ifdef HEAVY_STATISTICS
145 void sgen_descriptor_count_scanned_object (SgenDescriptor desc);
146 void sgen_descriptor_count_copied_object (SgenDescriptor desc);
149 static inline gboolean
150 sgen_gc_descr_has_references (SgenDescriptor desc)
152 /* This covers SMALL_PTRFREE and COMPLEX_PTRFREE */
153 if ((desc & DESC_TYPE_PTRFREE_MASK) == DESC_TYPE_PTRFREE_BITS)
156 /*The array is ptr-free*/
157 if ((desc & 0xC007) == (DESC_TYPE_VECTOR | VECTOR_SUBTYPE_PTRFREE))
163 #define SGEN_VTABLE_HAS_REFERENCES(vt) (sgen_gc_descr_has_references (sgen_vtable_get_descriptor ((vt))))
164 #define SGEN_OBJECT_HAS_REFERENCES(o) (SGEN_VTABLE_HAS_REFERENCES (SGEN_LOAD_VTABLE ((o))))
166 /* helper macros to scan and traverse objects, macros because we resue them in many functions */
168 #define PREFETCH_READ(addr) __builtin_prefetch ((addr), 0, 1)
169 #define PREFETCH_WRITE(addr) __builtin_prefetch ((addr), 1, 1)
171 #define PREFETCH_READ(addr)
172 #define PREFETCH_WRITE(addr)
175 #if defined(__GNUC__) && SIZEOF_VOID_P==4
176 #define GNUC_BUILTIN_CTZ(bmap) __builtin_ctz(bmap)
177 #elif defined(__GNUC__) && SIZEOF_VOID_P==8
178 #define GNUC_BUILTIN_CTZ(bmap) __builtin_ctzl(bmap)
181 /* code using these macros must define a HANDLE_PTR(ptr) macro that does the work */
182 #define OBJ_RUN_LEN_FOREACH_PTR(desc,obj) do { \
183 if ((desc) & 0xffff0000) { \
184 /* there are pointers */ \
185 void **_objptr_end; \
186 void **_objptr = (void**)(obj); \
187 _objptr += ((desc) >> 16) & 0xff; \
188 _objptr_end = _objptr + (((desc) >> 24) & 0xff); \
189 while (_objptr < _objptr_end) { \
190 HANDLE_PTR ((GCObject**)_objptr, (obj)); \
196 /* a bitmap desc means that there are pointer references or we'd have
197 * choosen run-length, instead: add an assert to check.
200 #define OBJ_BITMAP_FOREACH_PTR(desc,obj) do { \
201 /* there are pointers */ \
202 void **_objptr = (void**)(obj); \
203 gsize _bmap = (desc) >> LOW_TYPE_BITS; \
204 _objptr += OBJECT_HEADER_WORDS; \
206 int _index = GNUC_BUILTIN_CTZ (_bmap); \
208 _bmap >>= (_index + 1); \
209 HANDLE_PTR ((GCObject**)_objptr, (obj)); \
214 #define OBJ_BITMAP_FOREACH_PTR(desc,obj) do { \
215 /* there are pointers */ \
216 void **_objptr = (void**)(obj); \
217 gsize _bmap = (desc) >> LOW_TYPE_BITS; \
218 _objptr += OBJECT_HEADER_WORDS; \
221 HANDLE_PTR ((GCObject**)_objptr, (obj)); \
229 #define OBJ_COMPLEX_FOREACH_PTR(vt,obj) do { \
230 /* there are pointers */ \
231 void **_objptr = (void**)(obj); \
232 gsize *bitmap_data = sgen_get_complex_descriptor ((desc)); \
233 gsize bwords = (*bitmap_data) - 1; \
234 void **start_run = _objptr; \
236 while (bwords-- > 0) { \
237 gsize _bmap = *bitmap_data++; \
238 _objptr = start_run; \
239 /*g_print ("bitmap: 0x%x/%d at %p\n", _bmap, bwords, _objptr);*/ \
242 HANDLE_PTR ((GCObject**)_objptr, (obj)); \
247 start_run += GC_BITS_PER_WORD; \
251 /* this one is untested */
252 #define OBJ_COMPLEX_ARR_FOREACH_PTR(desc,obj) do { \
253 /* there are pointers */ \
254 GCVTable vt = SGEN_LOAD_VTABLE (obj); \
255 gsize *mbitmap_data = sgen_get_complex_descriptor ((desc)); \
256 gsize mbwords = (*mbitmap_data++) - 1; \
257 gsize el_size = sgen_client_array_element_size (vt); \
258 char *e_start = sgen_client_array_data_start ((GCObject*)(obj)); \
259 char *e_end = e_start + el_size * sgen_client_array_length ((GCObject*)(obj)); \
260 while (e_start < e_end) { \
261 void **_objptr = (void**)e_start; \
262 gsize *bitmap_data = mbitmap_data; \
263 gsize bwords = mbwords; \
264 while (bwords-- > 0) { \
265 gsize _bmap = *bitmap_data++; \
266 void **start_run = _objptr; \
267 /*g_print ("bitmap: 0x%x\n", _bmap);*/ \
270 HANDLE_PTR ((GCObject**)_objptr, (obj)); \
275 _objptr = start_run + GC_BITS_PER_WORD; \
277 e_start += el_size; \
281 #define OBJ_VECTOR_FOREACH_PTR(desc,obj) do { \
282 /* note: 0xffffc000 excludes DESC_TYPE_V_PTRFREE */ \
283 if ((desc) & 0xffffc000) { \
284 int el_size = ((desc) >> 3) & MAX_ELEMENT_SIZE; \
285 /* there are pointers */ \
286 int etype = (desc) & 0xc000; \
287 if (etype == (DESC_TYPE_V_REFS << 14)) { \
288 void **p = (void**)sgen_client_array_data_start ((GCObject*)(obj)); \
289 void **end_refs = (void**)((char*)p + el_size * sgen_client_array_length ((GCObject*)(obj))); \
290 /* Note: this code can handle also arrays of struct with only references in them */ \
291 while (p < end_refs) { \
292 HANDLE_PTR ((GCObject**)p, (obj)); \
295 } else if (etype == DESC_TYPE_V_RUN_LEN << 14) { \
296 int offset = ((desc) >> 16) & 0xff; \
297 int num_refs = ((desc) >> 24) & 0xff; \
298 char *e_start = sgen_client_array_data_start ((GCObject*)(obj)); \
299 char *e_end = e_start + el_size * sgen_client_array_length ((GCObject*)(obj)); \
300 while (e_start < e_end) { \
301 void **p = (void**)e_start; \
304 for (i = 0; i < num_refs; ++i) { \
305 HANDLE_PTR ((GCObject**)p + i, (obj)); \
307 e_start += el_size; \
309 } else if (etype == DESC_TYPE_V_BITMAP << 14) { \
310 char *e_start = sgen_client_array_data_start ((GCObject*)(obj)); \
311 char *e_end = e_start + el_size * sgen_client_array_length ((GCObject*)(obj)); \
312 while (e_start < e_end) { \
313 void **p = (void**)e_start; \
314 gsize _bmap = (desc) >> 16; \
315 /* Note: there is no object header here to skip */ \
318 HANDLE_PTR ((GCObject**)p, (obj)); \
323 e_start += el_size; \