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