mono/metadata/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/metadata/gc-internal.h>
  27 #include <mono/metadata/sgen-conf.h>
  28
  29
  30 /*
  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.
  36  */
  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)
  51
  52 #define VECTOR_KIND_SZARRAY  (DESC_TYPE_V_SZARRAY << VECTOR_KIND_SHIFT)
  53 #define VECTOR_KIND_ARRAY  (DESC_TYPE_V_ARRAY << VECTOR_KIND_SHIFT)
  54
  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
  58  * depend on the type.
  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
  71  * inside complex.
  72  */
  73 enum {
  74         /*
  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.
  78          *
  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
  83          * object's class.
  84          */
  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 */
 100 };
 101
 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.
 105  */
 106 enum {
 107         ROOT_DESC_CONSERVATIVE, /* 0, so matches NULL value */
 108         ROOT_DESC_BITMAP,
 109         ROOT_DESC_RUN_LEN,
 110         ROOT_DESC_COMPLEX,
 111         ROOT_DESC_USER,
 112         ROOT_DESC_TYPE_MASK = 0x7,
 113         ROOT_DESC_TYPE_SHIFT = 3,
 114 };
 115
 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;
 119
 120
 121 static inline gboolean
 122 sgen_gc_descr_has_references (mword desc)
 123 {
 124         /*Both string and fixed size objects are encoded using a zero run RUN_LEN*/
 125         if ((desc & 0xffff0007) == DESC_TYPE_RUN_LENGTH)
 126                 return FALSE;
 127
 128         /*The array is ptr-free*/
 129         if ((desc & 0xC007) == (DESC_TYPE_VECTOR | VECTOR_SUBTYPE_PTRFREE))
 130                 return FALSE;
 131
 132         if ((desc & 0x7) == DESC_TYPE_COMPLEX_PTRFREE)
 133                 return FALSE;
 134
 135         return TRUE;
 136 }
 137
 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))
 140 #define SGEN_OBJECT_HAS_REFERENCES(o)   (SGEN_VTABLE_HAS_REFERENCES (SGEN_LOAD_VTABLE ((o))))
 141
 142 /* helper macros to scan and traverse objects, macros because we resue them in many functions */
 143 #define OBJ_RUN_LEN_SIZE(size,desc,obj) do { \
 144                 (size) = ((desc) & 0xfff8);     \
 145     } while (0)
 146
 147 #define OBJ_BITMAP_SIZE(size,desc,obj) do { \
 148                 (size) = ((desc) & 0xfff8);     \
 149     } while (0)
 150
 151 #ifdef __GNUC__
 152 #define PREFETCH(addr)  __builtin_prefetch ((addr))
 153 #else
 154 #define PREFETCH(addr)
 155 #endif
 156
 157 #if defined(__GNUC__) && SIZEOF_VOID_P==4
 158 #define GNUC_BUILTIN_CTZ(bmap)  __builtin_ctz(bmap)
 159 #elif defined(__GNUC__) && SIZEOF_VOID_P==8
 160 #define GNUC_BUILTIN_CTZ(bmap)  __builtin_ctzl(bmap)
 161 #endif
 162
 163 /* code using these macros must define a HANDLE_PTR(ptr) macro that does the work */
 164 #define OBJ_RUN_LEN_FOREACH_PTR(desc,obj)       do {    \
 165                 if ((desc) & 0xffff0000) {      \
 166                         /* there are pointers */        \
 167                         void **_objptr_end;     \
 168                         void **_objptr = (void**)(obj); \
 169                         _objptr += ((desc) >> 16) & 0xff;       \
 170                         _objptr_end = _objptr + (((desc) >> 24) & 0xff);        \
 171                         HANDLE_PTR (_objptr, (obj)); \
 172                         _objptr ++; \
 173                         while (_objptr < _objptr_end) { \
 174                                 HANDLE_PTR (_objptr, (obj));    \
 175                                 _objptr++;      \
 176                         }       \
 177                 }       \
 178         } while (0)
 179
 180 #if defined(__GNUC__)
 181 #define OBJ_BITMAP_FOREACH_PTR(desc,obj)       do {    \
 182                 /* there are pointers */        \
 183                 void **_objptr = (void**)(obj); \
 184                 gsize _bmap = (desc) >> 16;     \
 185                 _objptr += OBJECT_HEADER_WORDS; \
 186                 { \
 187                         int _index = GNUC_BUILTIN_CTZ (_bmap);          \
 188                         _objptr += _index; \
 189                         _bmap >>= (_index + 1);                         \
 190                         HANDLE_PTR (_objptr, (obj));            \
 191                         _objptr ++;                                                     \
 192                         } \
 193                 while (_bmap) { \
 194                         int _index = GNUC_BUILTIN_CTZ (_bmap);          \
 195                         _objptr += _index; \
 196                         _bmap >>= (_index + 1);                         \
 197                         HANDLE_PTR (_objptr, (obj));            \
 198                         _objptr ++;                                                     \
 199                 }                                                                               \
 200         } while (0)
 201 #else
 202 #define OBJ_BITMAP_FOREACH_PTR(desc,obj)       do {    \
 203                 /* there are pointers */        \
 204                 void **_objptr = (void**)(obj); \
 205                 gsize _bmap = (desc) >> 16;     \
 206                 _objptr += OBJECT_HEADER_WORDS; \
 207                 while (_bmap) {                                            \
 208                         if ((_bmap & 1)) {                                                                 \
 209                                 HANDLE_PTR (_objptr, (obj));                               \
 210                         }                                                                                                  \
 211                         _bmap >>= 1;                                                                       \
 212                         ++_objptr;                                                                                 \
 213                 }                                                                                                          \
 214         } while (0)
 215 #endif
 216
 217 /* a bitmap desc means that there are pointer references or we'd have
 218  * choosen run-length, instead: add an assert to check.
 219  */
 220 #define OBJ_LARGE_BITMAP_FOREACH_PTR(desc,obj)  do {    \
 221                 /* there are pointers */        \
 222                 void **_objptr = (void**)(obj); \
 223                 gsize _bmap = (desc) >> LOW_TYPE_BITS;  \
 224                 _objptr += OBJECT_HEADER_WORDS; \
 225                 while (_bmap) { \
 226                         if ((_bmap & 1)) {      \
 227                                 HANDLE_PTR (_objptr, (obj));    \
 228                         }       \
 229                         _bmap >>= 1;    \
 230                         ++_objptr;      \
 231                 }       \
 232         } while (0)
 233
 234 #define OBJ_COMPLEX_FOREACH_PTR(vt,obj) do {    \
 235                 /* there are pointers */        \
 236                 void **_objptr = (void**)(obj); \
 237                 gsize *bitmap_data = sgen_get_complex_descriptor ((desc)); \
 238                 int bwords = (*bitmap_data) - 1;        \
 239                 void **start_run = _objptr;     \
 240                 bitmap_data++;  \
 241                 if (0) {        \
 242                         MonoObject *myobj = (MonoObject*)obj;   \
 243                         g_print ("found %d at %p (0x%zx): %s.%s\n", bwords, (obj), (desc), myobj->vtable->klass->name_space, myobj->vtable->klass->name); \
 244                 }       \
 245                 while (bwords-- > 0) {  \
 246                         gsize _bmap = *bitmap_data++;   \
 247                         _objptr = start_run;    \
 248                         /*g_print ("bitmap: 0x%x/%d at %p\n", _bmap, bwords, _objptr);*/        \
 249                         while (_bmap) { \
 250                                 if ((_bmap & 1)) {      \
 251                                         HANDLE_PTR (_objptr, (obj));    \
 252                                 }       \
 253                                 _bmap >>= 1;    \
 254                                 ++_objptr;      \
 255                         }       \
 256                         start_run += GC_BITS_PER_WORD;  \
 257                 }       \
 258         } while (0)
 259
 260 /* this one is untested */
 261 #define OBJ_COMPLEX_ARR_FOREACH_PTR(vt,obj)     do {    \
 262                 /* there are pointers */        \
 263                 gsize *mbitmap_data = sgen_get_complex_descriptor ((vt)->desc); \
 264                 int mbwords = (*mbitmap_data++) - 1;    \
 265                 int el_size = mono_array_element_size (vt->klass);      \
 266                 char *e_start = (char*)(obj) +  G_STRUCT_OFFSET (MonoArray, vector);    \
 267                 char *e_end = e_start + el_size * mono_array_length_fast ((MonoArray*)(obj));   \
 268                 if (0)                                                  \
 269                         g_print ("found %d at %p (0x%zx): %s.%s\n", mbwords, (obj), (vt)->desc, vt->klass->name_space, vt->klass->name); \
 270                 while (e_start < e_end) {       \
 271                         void **_objptr = (void**)e_start;       \
 272                         gsize *bitmap_data = mbitmap_data;      \
 273                         unsigned int bwords = mbwords;  \
 274                         while (bwords-- > 0) {  \
 275                                 gsize _bmap = *bitmap_data++;   \
 276                                 void **start_run = _objptr;     \
 277                                 /*g_print ("bitmap: 0x%x\n", _bmap);*/  \
 278                                 while (_bmap) { \
 279                                         if ((_bmap & 1)) {      \
 280                                                 HANDLE_PTR (_objptr, (obj));    \
 281                                         }       \
 282                                         _bmap >>= 1;    \
 283                                         ++_objptr;      \
 284                                 }       \
 285                                 _objptr = start_run + GC_BITS_PER_WORD; \
 286                         }       \
 287                         e_start += el_size;     \
 288                 }       \
 289         } while (0)
 290
 291 #define OBJ_VECTOR_FOREACH_PTR(desc,obj)        do {    \
 292                 /* note: 0xffffc000 excludes DESC_TYPE_V_PTRFREE */     \
 293                 if ((desc) & 0xffffc000) {                              \
 294                         int el_size = ((desc) >> 3) & MAX_ELEMENT_SIZE; \
 295                         /* there are pointers */        \
 296                         int etype = (desc) & 0xc000;                    \
 297                         if (etype == (DESC_TYPE_V_REFS << 14)) {        \
 298                                 void **p = (void**)((char*)(obj) + G_STRUCT_OFFSET (MonoArray, vector));        \
 299                                 void **end_refs = (void**)((char*)p + el_size * mono_array_length_fast ((MonoArray*)(obj)));    \
 300                                 /* Note: this code can handle also arrays of struct with only references in them */     \
 301                                 while (p < end_refs) {  \
 302                                         HANDLE_PTR (p, (obj));  \
 303                                         ++p;    \
 304                                 }       \
 305                         } else if (etype == DESC_TYPE_V_RUN_LEN << 14) {        \
 306                                 int offset = ((desc) >> 16) & 0xff;     \
 307                                 int num_refs = ((desc) >> 24) & 0xff;   \
 308                                 char *e_start = (char*)(obj) + G_STRUCT_OFFSET (MonoArray, vector);     \
 309                                 char *e_end = e_start + el_size * mono_array_length_fast ((MonoArray*)(obj));   \
 310                                 while (e_start < e_end) {       \
 311                                         void **p = (void**)e_start;     \
 312                                         int i;  \
 313                                         p += offset;    \
 314                                         for (i = 0; i < num_refs; ++i) {        \
 315                                                 HANDLE_PTR (p + i, (obj));      \
 316                                         }       \
 317                                         e_start += el_size;     \
 318                                 }       \
 319                         } else if (etype == DESC_TYPE_V_BITMAP << 14) { \
 320                                 char *e_start = (char*)(obj) +  G_STRUCT_OFFSET (MonoArray, vector);    \
 321                                 char *e_end = e_start + el_size * mono_array_length_fast ((MonoArray*)(obj));   \
 322                                 while (e_start < e_end) {       \
 323                                         void **p = (void**)e_start;     \
 324                                         gsize _bmap = (desc) >> 16;     \
 325                                         /* Note: there is no object header here to skip */      \
 326                                         while (_bmap) { \
 327                                                 if ((_bmap & 1)) {      \
 328                                                         HANDLE_PTR (p, (obj));  \
 329                                                 }       \
 330                                                 _bmap >>= 1;    \
 331                                                 ++p;    \
 332                                         }       \
 333                                         e_start += el_size;     \
 334                                 }       \
 335                         }       \
 336                 }       \
 337         } while (0)
 338
 339
 340 #endif