mono/metadata/sgen-los.c

   1 /*
   2  * sgen-los.c: Simple generational GC.
   3  *
   4  * Author:
   5  *      Paolo Molaro (lupus@ximian.com)
   6  *
   7  * Copyright 2005-2010 Novell, Inc (http://www.novell.com)
   8  *
   9  * Thread start/stop adapted from Boehm's GC:
  10  * Copyright (c) 1994 by Xerox Corporation.  All rights reserved.
  11  * Copyright (c) 1996 by Silicon Graphics.  All rights reserved.
  12  * Copyright (c) 1998 by Fergus Henderson.  All rights reserved.
  13  * Copyright (c) 2000-2004 by Hewlett-Packard Company.  All rights reserved.
  14  *
  15  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
  16  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
  17  *
  18  * Permission is hereby granted to use or copy this program
  19  * for any purpose,  provided the above notices are retained on all copies.
  20  * Permission to modify the code and to distribute modified code is granted,
  21  * provided the above notices are retained, and a notice that the code was
  22  * modified is included with the above copyright notice.
  23  *
  24  *
  25  * Copyright 2001-2003 Ximian, Inc
  26  * Copyright 2003-2010 Novell, Inc.
  27  *
  28  * Permission is hereby granted, free of charge, to any person obtaining
  29  * a copy of this software and associated documentation files (the
  30  * "Software"), to deal in the Software without restriction, including
  31  * without limitation the rights to use, copy, modify, merge, publish,
  32  * distribute, sublicense, and/or sell copies of the Software, and to
  33  * permit persons to whom the Software is furnished to do so, subject to
  34  * the following conditions:
  35  *
  36  * The above copyright notice and this permission notice shall be
  37  * included in all copies or substantial portions of the Software.
  38  *
  39  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  40  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  41  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  42  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  43  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  44  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  45  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  46  */
  47
  48 #define LOS_SECTION_SIZE        (1024 * 1024)
  49
  50 /*
  51  * This shouldn't be much smaller or larger than MAX_SMALL_OBJ_SIZE.
  52  * Must be at least sizeof (LOSSection).
  53  */
  54 #define LOS_CHUNK_SIZE          4096
  55 #define LOS_CHUNK_BITS          12
  56
  57 /* Largest object that can be allocated in a section. */
  58 #define LOS_SECTION_OBJECT_LIMIT        (LOS_SECTION_SIZE - LOS_CHUNK_SIZE - sizeof (LOSObject))
  59 //#define LOS_SECTION_OBJECT_LIMIT      0
  60 #define LOS_SECTION_NUM_CHUNKS          ((LOS_SECTION_SIZE >> LOS_CHUNK_BITS) - 1)
  61
  62 #define LOS_SECTION_FOR_OBJ(obj)        ((LOSSection*)((mword)(obj) & ~(mword)(LOS_SECTION_SIZE - 1)))
  63 #define LOS_CHUNK_INDEX(obj,section)    (((char*)(obj) - (char*)(section)) >> LOS_CHUNK_BITS)
  64
  65 #define LOS_NUM_FAST_SIZES              32
  66
  67 typedef struct _LOSObject LOSObject;
  68 struct _LOSObject {
  69         LOSObject *next;
  70         mword size; /* this is the object size */
  71         guint16 huge_object;
  72         int dummy; /* to have a sizeof (LOSObject) a multiple of ALLOC_ALIGN  and data starting at same alignment */
  73         char data [MONO_ZERO_LEN_ARRAY];
  74 };
  75
  76 typedef struct _LOSFreeChunks LOSFreeChunks;
  77 struct _LOSFreeChunks {
  78         LOSFreeChunks *next_size;
  79         size_t size;
  80 };
  81
  82 typedef struct _LOSSection LOSSection;
  83 struct _LOSSection {
  84         LOSSection *next;
  85         int num_free_chunks;
  86         unsigned char *free_chunk_map;
  87 };
  88
  89 static LOSSection *los_sections = NULL;
  90 static LOSObject *los_object_list = NULL;
  91 static LOSFreeChunks *los_fast_free_lists [LOS_NUM_FAST_SIZES]; /* 0 is for larger sizes */
  92 static mword los_memory_usage = 0;
  93 static mword last_los_memory_usage = 0;
  94 static mword los_num_objects = 0;
  95 static int los_num_sections = 0;
  96 static mword next_los_collection = 2*1024*1024; /* 2 MB, need to tune */
  97
  98 //#define USE_MALLOC
  99 //#define LOS_CONSISTENCY_CHECK
 100 //#define LOS_DUMMY
 101
 102 #ifdef LOS_DUMMY
 103 #define LOS_SEGMENT_SIZE        (4096 * 1024)
 104
 105 static char *los_segment = NULL;
 106 static int los_segment_index = 0;
 107 #endif
 108
 109 #ifdef LOS_CONSISTENCY_CHECK
 110 static void
 111 los_consistency_check (void)
 112 {
 113         LOSSection *section;
 114         LOSObject *obj;
 115         int i;
 116         mword memory_usage = 0;
 117
 118         for (obj = los_object_list; obj; obj = obj->next) {
 119                 char *end = obj->data + obj->size;
 120                 int start_index, num_chunks;
 121
 122                 memory_usage += obj->size;
 123
 124                 if (obj->size > LOS_SECTION_OBJECT_LIMIT)
 125                         continue;
 126
 127                 section = LOS_SECTION_FOR_OBJ (obj);
 128
 129                 g_assert (end <= (char*)section + LOS_SECTION_SIZE);
 130
 131                 start_index = LOS_CHUNK_INDEX (obj, section);
 132                 num_chunks = (obj->size + sizeof (LOSObject) + LOS_CHUNK_SIZE - 1) >> LOS_CHUNK_BITS;
 133                 for (i = start_index; i < start_index + num_chunks; ++i)
 134                         g_assert (!section->free_chunk_map [i]);
 135         }
 136
 137         for (i = 0; i < LOS_NUM_FAST_SIZES; ++i) {
 138                 LOSFreeChunks *size_chunks;
 139                 for (size_chunks = los_fast_free_lists [i]; size_chunks; size_chunks = size_chunks->next_size) {
 140                         LOSSection *section = LOS_SECTION_FOR_OBJ (size_chunks);
 141                         int j, num_chunks, start_index;
 142
 143                         if (i == 0)
 144                                 g_assert (size_chunks->size >= LOS_NUM_FAST_SIZES * LOS_CHUNK_SIZE);
 145                         else
 146                                 g_assert (size_chunks->size == i * LOS_CHUNK_SIZE);
 147
 148                         num_chunks = size_chunks->size >> LOS_CHUNK_BITS;
 149                         start_index = LOS_CHUNK_INDEX (size_chunks, section);
 150                         for (j = start_index; j < start_index + num_chunks; ++j)
 151                                 g_assert (section->free_chunk_map [j]);
 152                 }
 153         }
 154
 155         g_assert (los_memory_usage == memory_usage);
 156 }
 157 #endif
 158
 159 static void
 160 add_free_chunk (LOSFreeChunks *free_chunks, size_t size)
 161 {
 162         int num_chunks = size >> LOS_CHUNK_BITS;
 163
 164         free_chunks->size = size;
 165
 166         if (num_chunks >= LOS_NUM_FAST_SIZES)
 167                 num_chunks = 0;
 168         free_chunks->next_size = los_fast_free_lists [num_chunks];
 169         los_fast_free_lists [num_chunks] = free_chunks;
 170 }
 171
 172 static LOSFreeChunks*
 173 get_from_size_list (LOSFreeChunks **list, size_t size)
 174 {
 175         LOSFreeChunks *free_chunks = NULL;
 176         LOSSection *section;
 177         int num_chunks, i, start_index;
 178
 179         g_assert ((size & (LOS_CHUNK_SIZE - 1)) == 0);
 180
 181         while (*list) {
 182                 free_chunks = *list;
 183                 if (free_chunks->size >= size)
 184                         break;
 185                 list = &(*list)->next_size;
 186         }
 187
 188         if (!*list)
 189                 return NULL;
 190
 191         *list = free_chunks->next_size;
 192
 193         if (free_chunks->size > size)
 194                 add_free_chunk ((LOSFreeChunks*)((char*)free_chunks + size), free_chunks->size - size);
 195
 196         num_chunks = size >> LOS_CHUNK_BITS;
 197
 198         section = LOS_SECTION_FOR_OBJ (free_chunks);
 199
 200         start_index = LOS_CHUNK_INDEX (free_chunks, section);
 201         for (i = start_index; i < start_index + num_chunks; ++i) {
 202                 g_assert (section->free_chunk_map [i]);
 203                 section->free_chunk_map [i] = 0;
 204         }
 205
 206         section->num_free_chunks -= size >> LOS_CHUNK_BITS;
 207         g_assert (section->num_free_chunks >= 0);
 208
 209         return free_chunks;
 210 }
 211
 212 static LOSObject*
 213 get_los_section_memory (size_t size)
 214 {
 215         LOSSection *section;
 216         LOSFreeChunks *free_chunks;
 217         int num_chunks;
 218
 219         size += LOS_CHUNK_SIZE - 1;
 220         size &= ~(LOS_CHUNK_SIZE - 1);
 221
 222         num_chunks = size >> LOS_CHUNK_BITS;
 223
 224         g_assert (size > 0 && size - sizeof (LOSObject) <= LOS_SECTION_OBJECT_LIMIT);
 225         g_assert (num_chunks > 0);
 226
 227  retry:
 228         if (num_chunks >= LOS_NUM_FAST_SIZES) {
 229                 free_chunks = get_from_size_list (&los_fast_free_lists [0], size);
 230         } else {
 231                 int i;
 232                 for (i = num_chunks; i < LOS_NUM_FAST_SIZES; ++i) {
 233                         free_chunks = get_from_size_list (&los_fast_free_lists [i], size);
 234                         if (free_chunks)
 235                                 break;
 236                 }
 237                 if (!free_chunks)
 238                         free_chunks = get_from_size_list (&los_fast_free_lists [0], size);
 239         }
 240
 241         if (free_chunks)
 242                 return (LOSObject*)free_chunks;
 243
 244         section = mono_sgen_alloc_os_memory_aligned (LOS_SECTION_SIZE, LOS_SECTION_SIZE, TRUE);
 245
 246         free_chunks = (LOSFreeChunks*)((char*)section + LOS_CHUNK_SIZE);
 247         free_chunks->size = LOS_SECTION_SIZE - LOS_CHUNK_SIZE;
 248         free_chunks->next_size = los_fast_free_lists [0];
 249         los_fast_free_lists [0] = free_chunks;
 250
 251         section->num_free_chunks = LOS_SECTION_NUM_CHUNKS;
 252
 253         section->free_chunk_map = (unsigned char*)section + sizeof (LOSSection);
 254         g_assert (sizeof (LOSSection) + LOS_SECTION_NUM_CHUNKS + 1 <= LOS_CHUNK_SIZE);
 255         section->free_chunk_map [0] = 0;
 256         memset (section->free_chunk_map + 1, 1, LOS_SECTION_NUM_CHUNKS);
 257
 258         section->next = los_sections;
 259         los_sections = section;
 260
 261         ++los_num_sections;
 262
 263         goto retry;
 264 }
 265
 266 static void
 267 free_los_section_memory (LOSObject *obj, size_t size)
 268 {
 269         LOSSection *section = LOS_SECTION_FOR_OBJ (obj);
 270         int num_chunks, i, start_index;
 271
 272         size += LOS_CHUNK_SIZE - 1;
 273         size &= ~(LOS_CHUNK_SIZE - 1);
 274
 275         num_chunks = size >> LOS_CHUNK_BITS;
 276
 277         g_assert (size > 0 && size - sizeof (LOSObject) <= LOS_SECTION_OBJECT_LIMIT);
 278         g_assert (num_chunks > 0);
 279
 280         section->num_free_chunks += num_chunks;
 281         g_assert (section->num_free_chunks <= LOS_SECTION_NUM_CHUNKS);
 282
 283         /*
 284          * We could free the LOS section here if it's empty, but we
 285          * can't unless we also remove its free chunks from the fast
 286          * free lists.  Instead, we do it in los_sweep().
 287          */
 288
 289         start_index = LOS_CHUNK_INDEX (obj, section);
 290         for (i = start_index; i < start_index + num_chunks; ++i) {
 291                 g_assert (!section->free_chunk_map [i]);
 292                 section->free_chunk_map [i] = 1;
 293         }
 294
 295         add_free_chunk ((LOSFreeChunks*)obj, size);
 296 }
 297
 298 static void
 299 free_large_object (LOSObject *obj)
 300 {
 301 #ifndef LOS_DUMMY
 302         size_t size = obj->size;
 303         DEBUG (4, fprintf (gc_debug_file, "Freed large object %p, size %lu\n", obj->data, (unsigned long)obj->size));
 304         binary_protocol_empty (obj->data, obj->size);
 305
 306         los_memory_usage -= size;
 307         los_num_objects--;
 308
 309 #ifdef USE_MALLOC
 310         free (obj);
 311 #else
 312         if (size > LOS_SECTION_OBJECT_LIMIT) {
 313                 size += sizeof (LOSObject);
 314                 size += pagesize - 1;
 315                 size &= ~(pagesize - 1);
 316                 mono_sgen_free_os_memory (obj, size);
 317         } else {
 318                 free_los_section_memory (obj, size + sizeof (LOSObject));
 319 #ifdef LOS_CONSISTENCY_CHECKS
 320                 los_consistency_check ();
 321 #endif
 322         }
 323 #endif
 324 #endif
 325 }
 326
 327 /*
 328  * Objects with size >= MAX_SMALL_SIZE are allocated in the large object space.
 329  * They are currently kept track of with a linked list.
 330  * They don't move, so there is no need to pin them during collection
 331  * and we avoid the memcpy overhead.
 332  */
 333 static void* __attribute__((noinline))
 334 alloc_large_inner (MonoVTable *vtable, size_t size)
 335 {
 336         LOSObject *obj;
 337         void **vtslot;
 338
 339         g_assert (size > MAX_SMALL_OBJ_SIZE);
 340
 341 #ifdef LOS_DUMMY
 342         if (!los_segment)
 343                 los_segment = mono_sgen_alloc_os_memory (LOS_SEGMENT_SIZE, TRUE);
 344         los_segment_index = ALIGN_UP (los_segment_index);
 345
 346         obj = (LOSObject*)(los_segment + los_segment_index);
 347         los_segment_index += size + sizeof (LOSObject);
 348         g_assert (los_segment_index <= LOS_SEGMENT_SIZE);
 349 #else
 350         if (need_major_collection ()) {
 351                 DEBUG (4, fprintf (gc_debug_file, "Should trigger major collection: req size %zd (los already: %lu, limit: %lu)\n", size, (unsigned long)los_memory_usage, (unsigned long)next_los_collection));
 352                 stop_world ();
 353                 major_collection ("LOS overflow");
 354                 restart_world ();
 355         }
 356
 357 #ifdef USE_MALLOC
 358         obj = malloc (size + sizeof (LOSObject));
 359         memset (obj, 0, size + sizeof (LOSObject));
 360 #else
 361         if (size > LOS_SECTION_OBJECT_LIMIT) {
 362                 size_t alloc_size = size;
 363                 alloc_size += sizeof (LOSObject);
 364                 alloc_size += pagesize - 1;
 365                 alloc_size &= ~(pagesize - 1);
 366                 /* FIXME: handle OOM */
 367                 obj = mono_sgen_alloc_os_memory (alloc_size, TRUE);
 368                 obj->huge_object = TRUE;
 369         } else {
 370                 obj = get_los_section_memory (size + sizeof (LOSObject));
 371                 memset (obj, 0, size + sizeof (LOSObject));
 372         }
 373 #endif
 374 #endif
 375
 376         g_assert (!((mword)obj->data & (ALLOC_ALIGN - 1)));
 377         obj->size = size;
 378         vtslot = (void**)obj->data;
 379         *vtslot = vtable;
 380         mono_sgen_update_heap_boundaries ((mword)obj->data, (mword)obj->data + size);
 381         obj->next = los_object_list;
 382         los_object_list = obj;
 383         los_memory_usage += size;
 384         los_num_objects++;
 385         DEBUG (4, fprintf (gc_debug_file, "Allocated large object %p, vtable: %p (%s), size: %zd\n", obj->data, vtable, vtable->klass->name, size));
 386         binary_protocol_alloc (obj->data, vtable, size);
 387
 388 #ifdef LOS_CONSISTENCY_CHECK
 389         los_consistency_check ();
 390 #endif
 391
 392         return obj->data;
 393 }
 394
 395 static void
 396 los_sweep (void)
 397 {
 398         LOSSection *section, *prev;
 399         int i;
 400         int num_sections = 0;
 401
 402         for (i = 0; i < LOS_NUM_FAST_SIZES; ++i)
 403                 los_fast_free_lists [i] = NULL;
 404
 405         prev = NULL;
 406         section = los_sections;
 407         while (section) {
 408                 if (section->num_free_chunks == LOS_SECTION_NUM_CHUNKS) {
 409                         LOSSection *next = section->next;
 410                         if (prev)
 411                                 prev->next = next;
 412                         else
 413                                 los_sections = next;
 414                         mono_sgen_free_os_memory (section, LOS_SECTION_SIZE);
 415                         section = next;
 416                         --los_num_sections;
 417                         continue;
 418                 }
 419
 420                 for (i = 0; i <= LOS_SECTION_NUM_CHUNKS; ++i) {
 421                         if (section->free_chunk_map [i]) {
 422                                 int j;
 423                                 for (j = i + 1; j <= LOS_SECTION_NUM_CHUNKS && section->free_chunk_map [j]; ++j)
 424                                         ;
 425                                 add_free_chunk ((LOSFreeChunks*)((char*)section + (i << LOS_CHUNK_BITS)), (j - i) << LOS_CHUNK_BITS);
 426                                 i = j - 1;
 427                         }
 428                 }
 429
 430                 prev = section;
 431                 section = section->next;
 432
 433                 ++num_sections;
 434         }
 435
 436 #ifdef LOS_CONSISTENCY_CHECK
 437         los_consistency_check ();
 438 #endif
 439
 440         /*
 441         g_print ("LOS sections: %d  objects: %d  usage: %d\n", num_sections, los_num_objects, los_memory_usage);
 442         for (i = 0; i < LOS_NUM_FAST_SIZES; ++i) {
 443                 int num_chunks = 0;
 444                 LOSFreeChunks *free_chunks;
 445                 for (free_chunks = los_fast_free_lists [i]; free_chunks; free_chunks = free_chunks->next_size)
 446                         ++num_chunks;
 447                 g_print ("  %d: %d\n", i, num_chunks);
 448         }
 449         */
 450
 451         g_assert (los_num_sections == num_sections);
 452 }
 453
 454 #ifdef SGEN_HAVE_CARDTABLE
 455
 456 static void
 457 los_iterate_live_block_ranges (sgen_cardtable_block_callback callback)
 458 {
 459         LOSObject *obj;
 460         for (obj = los_object_list; obj; obj = obj->next) {
 461                 MonoVTable *vt = (MonoVTable*)LOAD_VTABLE (obj->data);
 462                 if (vt->klass->has_references)
 463                         callback ((mword)obj->data, (mword)obj->size);
 464         }
 465 }
 466
 467 #define ARRAY_OBJ_INDEX(ptr,array,elem_size) (((char*)(ptr) - ((char*)(array) + G_STRUCT_OFFSET (MonoArray, vector))) / (elem_size))
 468
 469 static void __attribute__((noinline))
 470 los_scan_card_table (GrayQueue *queue)
 471 {
 472         LOSObject *obj;
 473
 474         for (obj = los_object_list; obj; obj = obj->next) {
 475                 sgen_cardtable_scan_object (obj->data, obj->size, NULL, queue);
 476         }
 477 }
 478
 479 #endif