mono/sgen/sgen-descriptor.h

   1 /*
   2  * sgen-descriptor.h: GC descriptors describe object layout.
   3
   4  * Copyright 2001-2003 Ximian, Inc
   5  * Copyright 2003-2010 Novell, Inc.
   6  * Copyright 2011 Xamarin Inc (http://www.xamarin.com)
   7  *
   8  * Copyright (C) 2012 Xamarin Inc
   9  *
  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;
  13  *
  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.
  18  *
  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.
  22  */
  23 #ifndef __MONO_SGEN_DESCRIPTOR_H__
  24 #define __MONO_SGEN_DESCRIPTOR_H__
  25
  26 #include <mono/sgen/sgen-conf.h>
  27
  28 /*
  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.
  34  */
  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)
  49
  50 #define VECTOR_KIND_SZARRAY  (DESC_TYPE_V_SZARRAY << VECTOR_KIND_SHIFT)
  51 #define VECTOR_KIND_ARRAY  (DESC_TYPE_V_ARRAY << VECTOR_KIND_SHIFT)
  52
  53 /*
  54  * Objects are aligned to 8 bytes boundaries.
  55  *
  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
  58  * depend on the type.
  59  *
  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.
  63  *
  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.
  69  *
  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
  82  * inside complex.
  83  *
  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.
  86  */
  87 enum {
  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. */
  97         DESC_TYPE_MAX = 7,
  98
  99         DESC_TYPE_PTRFREE_MASK = 3,
 100         DESC_TYPE_PTRFREE_BITS = 3
 101 };
 102
 103 /* values for array kind */
 104 enum {
 105         DESC_TYPE_V_SZARRAY = 0, /*vector with no bounds data */
 106         DESC_TYPE_V_ARRAY = 1, /* array with bounds data */
 107 };
 108
 109 /* subtypes for arrays and vectors */
 110 enum {
 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 */
 115 };
 116
 117 #define SGEN_DESC_STRING        (DESC_TYPE_COMPLEX_PTRFREE | (1 << LOW_TYPE_BITS))
 118
 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.
 122  */
 123 enum {
 124         ROOT_DESC_CONSERVATIVE, /* 0, so matches NULL value */
 125         ROOT_DESC_BITMAP,
 126         ROOT_DESC_RUN_LEN,
 127         ROOT_DESC_COMPLEX,
 128         ROOT_DESC_USER,
 129         ROOT_DESC_TYPE_MASK = 0x7,
 130         ROOT_DESC_TYPE_SHIFT = 3,
 131 };
 132
 133 typedef void (*SgenUserMarkFunc)     (GCObject **addr, void *gc_data);
 134 typedef void (*SgenUserRootMarkFunc) (void *addr, SgenUserMarkFunc mark_func, void *gc_data);
 135
 136 SgenDescriptor sgen_make_user_root_descriptor (SgenUserRootMarkFunc marker);
 137
 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);
 141
 142 void sgen_init_descriptors (void);
 143
 144 #ifdef HEAVY_STATISTICS
 145 void sgen_descriptor_count_scanned_object (SgenDescriptor desc);
 146 void sgen_descriptor_count_copied_object (SgenDescriptor desc);
 147 #endif
 148
 149 static inline gboolean
 150 sgen_gc_descr_has_references (SgenDescriptor desc)
 151 {
 152         /* This covers SMALL_PTRFREE and COMPLEX_PTRFREE */
 153         if ((desc & DESC_TYPE_PTRFREE_MASK) == DESC_TYPE_PTRFREE_BITS)
 154                 return FALSE;
 155
 156         /*The array is ptr-free*/
 157         if ((desc & 0xC007) == (DESC_TYPE_VECTOR | VECTOR_SUBTYPE_PTRFREE))
 158                 return FALSE;
 159
 160         return TRUE;
 161 }
 162
 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))))
 165
 166 /* helper macros to scan and traverse objects, macros because we resue them in many functions */
 167 #ifdef __GNUC__
 168 #define PREFETCH_READ(addr)     __builtin_prefetch ((addr), 0, 1)
 169 #define PREFETCH_WRITE(addr)    __builtin_prefetch ((addr), 1, 1)
 170 #else
 171 #define PREFETCH_READ(addr)
 172 #define PREFETCH_WRITE(addr)
 173 #endif
 174
 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)
 179 #endif
 180
 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)); \
 191                                 _objptr++;      \
 192                         };      \
 193                 }       \
 194         } while (0)
 195
 196 /* a bitmap desc means that there are pointer references or we'd have
 197  * choosen run-length, instead: add an assert to check.
 198  */
 199 #ifdef __GNUC__
 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;                 \
 205                 do {                                            \
 206                         int _index = GNUC_BUILTIN_CTZ (_bmap);  \
 207                         _objptr += _index;                      \
 208                         _bmap >>= (_index + 1);                 \
 209                         HANDLE_PTR ((GCObject**)_objptr, (obj));        \
 210                         ++_objptr;                              \
 211                 } while (_bmap);                                \
 212         } while (0)
 213 #else
 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; \
 219                 do {    \
 220                         if ((_bmap & 1)) {      \
 221                                 HANDLE_PTR ((GCObject**)_objptr, (obj));        \
 222                         }       \
 223                         _bmap >>= 1;    \
 224                         ++_objptr;      \
 225                 } while (_bmap);        \
 226         } while (0)
 227 #endif
 228
 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;     \
 235                 bitmap_data++;  \
 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);*/        \
 240                         while (_bmap) { \
 241                                 if ((_bmap & 1)) {      \
 242                                         HANDLE_PTR ((GCObject**)_objptr, (obj));        \
 243                                 }       \
 244                                 _bmap >>= 1;    \
 245                                 ++_objptr;      \
 246                         }       \
 247                         start_run += GC_BITS_PER_WORD;  \
 248                 }       \
 249         } while (0)
 250
 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);*/  \
 268                                 while (_bmap) { \
 269                                         if ((_bmap & 1)) {      \
 270                                                 HANDLE_PTR ((GCObject**)_objptr, (obj));        \
 271                                         }       \
 272                                         _bmap >>= 1;    \
 273                                         ++_objptr;      \
 274                                 }       \
 275                                 _objptr = start_run + GC_BITS_PER_WORD; \
 276                         }       \
 277                         e_start += el_size;     \
 278                 }       \
 279         } while (0)
 280
 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));      \
 293                                         ++p;    \
 294                                 }       \
 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;     \
 302                                         int i;  \
 303                                         p += offset;    \
 304                                         for (i = 0; i < num_refs; ++i) {        \
 305                                                 HANDLE_PTR ((GCObject**)p + i, (obj));  \
 306                                         }       \
 307                                         e_start += el_size;     \
 308                                 }       \
 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 */      \
 316                                         while (_bmap) { \
 317                                                 if ((_bmap & 1)) {      \
 318                                                         HANDLE_PTR ((GCObject**)p, (obj));      \
 319                                                 }       \
 320                                                 _bmap >>= 1;    \
 321                                                 ++p;    \
 322                                         }       \
 323                                         e_start += el_size;     \
 324                                 }       \
 325                         }       \
 326                 }       \
 327         } while (0)
 328
 329
 330 #endif