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 #ifdef HAVE_SGEN_GC
  49
  50 #include "metadata/sgen-gc.h"
  51 #include "metadata/sgen-protocol.h"
  52 #include "metadata/sgen-cardtable.h"
  53 #include "utils/mono-mmap.h"
  54
  55 #define LOS_SECTION_SIZE        (1024 * 1024)
  56
  57 /*
  58  * This shouldn't be much smaller or larger than MAX_SMALL_OBJ_SIZE.
  59  * Must be at least sizeof (LOSSection).
  60  */
  61 #define LOS_CHUNK_SIZE          4096
  62 #define LOS_CHUNK_BITS          12
  63
  64 /* Largest object that can be allocated in a section. */
  65 #define LOS_SECTION_OBJECT_LIMIT        (LOS_SECTION_SIZE - LOS_CHUNK_SIZE - sizeof (LOSObject))
  66 //#define LOS_SECTION_OBJECT_LIMIT      0
  67 #define LOS_SECTION_NUM_CHUNKS          ((LOS_SECTION_SIZE >> LOS_CHUNK_BITS) - 1)
  68
  69 #define LOS_SECTION_FOR_OBJ(obj)        ((LOSSection*)((mword)(obj) & ~(mword)(LOS_SECTION_SIZE - 1)))
  70 #define LOS_CHUNK_INDEX(obj,section)    (((char*)(obj) - (char*)(section)) >> LOS_CHUNK_BITS)
  71
  72 #define LOS_NUM_FAST_SIZES              32
  73
  74 typedef struct _LOSFreeChunks LOSFreeChunks;
  75 struct _LOSFreeChunks {
  76         LOSFreeChunks *next_size;
  77         size_t size;
  78 };
  79
  80 typedef struct _LOSSection LOSSection;
  81 struct _LOSSection {
  82         LOSSection *next;
  83         int num_free_chunks;
  84         unsigned char *free_chunk_map;
  85 };
  86
  87 LOSObject *los_object_list = NULL;
  88 mword los_memory_usage = 0;
  89
  90 static LOSSection *los_sections = NULL;
  91 static LOSFreeChunks *los_fast_free_lists [LOS_NUM_FAST_SIZES]; /* 0 is for larger sizes */
  92 static mword los_num_objects = 0;
  93 static int los_num_sections = 0;
  94 static mword next_los_collection = 2*1024*1024; /* 2 MB, need to tune */
  95
  96 //#define USE_MALLOC
  97 //#define LOS_CONSISTENCY_CHECK
  98 //#define LOS_DUMMY
  99
 100 #ifdef LOS_DUMMY
 101 #define LOS_SEGMENT_SIZE        (4096 * 1024)
 102
 103 static char *los_segment = NULL;
 104 static int los_segment_index = 0;
 105 #endif
 106
 107 #ifdef LOS_CONSISTENCY_CHECK
 108 static void
 109 los_consistency_check (void)
 110 {
 111         LOSSection *section;
 112         LOSObject *obj;
 113         int i;
 114         mword memory_usage = 0;
 115
 116         for (obj = los_object_list; obj; obj = obj->next) {
 117                 char *end = obj->data + obj->size;
 118                 int start_index, num_chunks;
 119
 120                 memory_usage += obj->size;
 121
 122                 if (obj->size > LOS_SECTION_OBJECT_LIMIT)
 123                         continue;
 124
 125                 section = LOS_SECTION_FOR_OBJ (obj);
 126
 127                 g_assert (end <= (char*)section + LOS_SECTION_SIZE);
 128
 129                 start_index = LOS_CHUNK_INDEX (obj, section);
 130                 num_chunks = (obj->size + sizeof (LOSObject) + LOS_CHUNK_SIZE - 1) >> LOS_CHUNK_BITS;
 131                 for (i = start_index; i < start_index + num_chunks; ++i)
 132                         g_assert (!section->free_chunk_map [i]);
 133         }
 134
 135         for (i = 0; i < LOS_NUM_FAST_SIZES; ++i) {
 136                 LOSFreeChunks *size_chunks;
 137                 for (size_chunks = los_fast_free_lists [i]; size_chunks; size_chunks = size_chunks->next_size) {
 138                         LOSSection *section = LOS_SECTION_FOR_OBJ (size_chunks);
 139                         int j, num_chunks, start_index;
 140
 141                         if (i == 0)
 142                                 g_assert (size_chunks->size >= LOS_NUM_FAST_SIZES * LOS_CHUNK_SIZE);
 143                         else
 144                                 g_assert (size_chunks->size == i * LOS_CHUNK_SIZE);
 145
 146                         num_chunks = size_chunks->size >> LOS_CHUNK_BITS;
 147                         start_index = LOS_CHUNK_INDEX (size_chunks, section);
 148                         for (j = start_index; j < start_index + num_chunks; ++j)
 149                                 g_assert (section->free_chunk_map [j]);
 150                 }
 151         }
 152
 153         g_assert (los_memory_usage == memory_usage);
 154 }
 155 #endif
 156
 157 static void
 158 add_free_chunk (LOSFreeChunks *free_chunks, size_t size)
 159 {
 160         int num_chunks = size >> LOS_CHUNK_BITS;
 161
 162         free_chunks->size = size;
 163
 164         if (num_chunks >= LOS_NUM_FAST_SIZES)
 165                 num_chunks = 0;
 166         free_chunks->next_size = los_fast_free_lists [num_chunks];
 167         los_fast_free_lists [num_chunks] = free_chunks;
 168 }
 169
 170 static LOSFreeChunks*
 171 get_from_size_list (LOSFreeChunks **list, size_t size)
 172 {
 173         LOSFreeChunks *free_chunks = NULL;
 174         LOSSection *section;
 175         int num_chunks, i, start_index;
 176
 177         g_assert ((size & (LOS_CHUNK_SIZE - 1)) == 0);
 178
 179         while (*list) {
 180                 free_chunks = *list;
 181                 if (free_chunks->size >= size)
 182                         break;
 183                 list = &(*list)->next_size;
 184         }
 185
 186         if (!*list)
 187                 return NULL;
 188
 189         *list = free_chunks->next_size;
 190
 191         if (free_chunks->size > size)
 192                 add_free_chunk ((LOSFreeChunks*)((char*)free_chunks + size), free_chunks->size - size);
 193
 194         num_chunks = size >> LOS_CHUNK_BITS;
 195
 196         section = LOS_SECTION_FOR_OBJ (free_chunks);
 197
 198         start_index = LOS_CHUNK_INDEX (free_chunks, section);
 199         for (i = start_index; i < start_index + num_chunks; ++i) {
 200                 g_assert (section->free_chunk_map [i]);
 201                 section->free_chunk_map [i] = 0;
 202         }
 203
 204         section->num_free_chunks -= size >> LOS_CHUNK_BITS;
 205         g_assert (section->num_free_chunks >= 0);
 206
 207         return free_chunks;
 208 }
 209
 210 static LOSObject*
 211 get_los_section_memory (size_t size)
 212 {
 213         LOSSection *section;
 214         LOSFreeChunks *free_chunks;
 215         int num_chunks;
 216
 217         size += LOS_CHUNK_SIZE - 1;
 218         size &= ~(LOS_CHUNK_SIZE - 1);
 219
 220         num_chunks = size >> LOS_CHUNK_BITS;
 221
 222         g_assert (size > 0 && size - sizeof (LOSObject) <= LOS_SECTION_OBJECT_LIMIT);
 223         g_assert (num_chunks > 0);
 224
 225  retry:
 226         if (num_chunks >= LOS_NUM_FAST_SIZES) {
 227                 free_chunks = get_from_size_list (&los_fast_free_lists [0], size);
 228         } else {
 229                 int i;
 230                 for (i = num_chunks; i < LOS_NUM_FAST_SIZES; ++i) {
 231                         free_chunks = get_from_size_list (&los_fast_free_lists [i], size);
 232                         if (free_chunks)
 233                                 break;
 234                 }
 235                 if (!free_chunks)
 236                         free_chunks = get_from_size_list (&los_fast_free_lists [0], size);
 237         }
 238
 239         if (free_chunks)
 240                 return (LOSObject*)free_chunks;
 241
 242         if (!mono_sgen_try_alloc_space (LOS_SECTION_SIZE, SPACE_LOS))
 243                 return NULL;
 244
 245         section = mono_sgen_alloc_os_memory_aligned (LOS_SECTION_SIZE, LOS_SECTION_SIZE, TRUE);
 246
 247         free_chunks = (LOSFreeChunks*)((char*)section + LOS_CHUNK_SIZE);
 248         free_chunks->size = LOS_SECTION_SIZE - LOS_CHUNK_SIZE;
 249         free_chunks->next_size = los_fast_free_lists [0];
 250         los_fast_free_lists [0] = free_chunks;
 251
 252         section->num_free_chunks = LOS_SECTION_NUM_CHUNKS;
 253
 254         section->free_chunk_map = (unsigned char*)section + sizeof (LOSSection);
 255         g_assert (sizeof (LOSSection) + LOS_SECTION_NUM_CHUNKS + 1 <= LOS_CHUNK_SIZE);
 256         section->free_chunk_map [0] = 0;
 257         memset (section->free_chunk_map + 1, 1, LOS_SECTION_NUM_CHUNKS);
 258
 259         section->next = los_sections;
 260         los_sections = section;
 261
 262         ++los_num_sections;
 263
 264         goto retry;
 265 }
 266
 267 static void
 268 free_los_section_memory (LOSObject *obj, size_t size)
 269 {
 270         LOSSection *section = LOS_SECTION_FOR_OBJ (obj);
 271         int num_chunks, i, start_index;
 272
 273         size += LOS_CHUNK_SIZE - 1;
 274         size &= ~(LOS_CHUNK_SIZE - 1);
 275
 276         num_chunks = size >> LOS_CHUNK_BITS;
 277
 278         g_assert (size > 0 && size - sizeof (LOSObject) <= LOS_SECTION_OBJECT_LIMIT);
 279         g_assert (num_chunks > 0);
 280
 281         section->num_free_chunks += num_chunks;
 282         g_assert (section->num_free_chunks <= LOS_SECTION_NUM_CHUNKS);
 283
 284         /*
 285          * We could free the LOS section here if it's empty, but we
 286          * can't unless we also remove its free chunks from the fast
 287          * free lists.  Instead, we do it in los_sweep().
 288          */
 289
 290         start_index = LOS_CHUNK_INDEX (obj, section);
 291         for (i = start_index; i < start_index + num_chunks; ++i) {
 292                 g_assert (!section->free_chunk_map [i]);
 293                 section->free_chunk_map [i] = 1;
 294         }
 295
 296         add_free_chunk ((LOSFreeChunks*)obj, size);
 297 }
 298
 299 static int pagesize;
 300
 301 void
 302 mono_sgen_los_free_object (LOSObject *obj)
 303 {
 304 #ifndef LOS_DUMMY
 305         size_t size = obj->size;
 306         DEBUG (4, fprintf (gc_debug_file, "Freed large object %p, size %lu\n", obj->data, (unsigned long)obj->size));
 307         binary_protocol_empty (obj->data, obj->size);
 308
 309         los_memory_usage -= size;
 310         los_num_objects--;
 311
 312 #ifdef USE_MALLOC
 313         free (obj);
 314 #else
 315         if (size > LOS_SECTION_OBJECT_LIMIT) {
 316                 if (!pagesize)
 317                         pagesize = mono_pagesize ();
 318                 size += sizeof (LOSObject);
 319                 size += pagesize - 1;
 320                 size &= ~(pagesize - 1);
 321                 mono_sgen_free_os_memory (obj, size);
 322                 mono_sgen_release_space (size, SPACE_LOS);
 323         } else {
 324                 free_los_section_memory (obj, size + sizeof (LOSObject));
 325 #ifdef LOS_CONSISTENCY_CHECKS
 326                 los_consistency_check ();
 327 #endif
 328         }
 329 #endif
 330 #endif
 331 }
 332
 333 /*
 334  * Objects with size >= MAX_SMALL_SIZE are allocated in the large object space.
 335  * They are currently kept track of with a linked list.
 336  * They don't move, so there is no need to pin them during collection
 337  * and we avoid the memcpy overhead.
 338  */
 339 void*
 340 mono_sgen_los_alloc_large_inner (MonoVTable *vtable, size_t size)
 341 {
 342         LOSObject *obj = NULL;
 343         void **vtslot;
 344
 345         g_assert (size > SGEN_MAX_SMALL_OBJ_SIZE);
 346
 347 #ifdef LOS_DUMMY
 348         if (!los_segment)
 349                 los_segment = mono_sgen_alloc_os_memory (LOS_SEGMENT_SIZE, TRUE);
 350         los_segment_index = ALIGN_UP (los_segment_index);
 351
 352         obj = (LOSObject*)(los_segment + los_segment_index);
 353         los_segment_index += size + sizeof (LOSObject);
 354         g_assert (los_segment_index <= LOS_SEGMENT_SIZE);
 355 #else
 356         if (mono_sgen_need_major_collection (size)) {
 357                 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));
 358                 sgen_collect_major_no_lock ("LOS overflow");
 359         }
 360
 361 #ifdef USE_MALLOC
 362         obj = malloc (size + sizeof (LOSObject));
 363         memset (obj, 0, size + sizeof (LOSObject));
 364 #else
 365         if (size > LOS_SECTION_OBJECT_LIMIT) {
 366                 size_t alloc_size = size;
 367                 if (!pagesize)
 368                         pagesize = mono_pagesize ();
 369                 alloc_size += sizeof (LOSObject);
 370                 alloc_size += pagesize - 1;
 371                 alloc_size &= ~(pagesize - 1);
 372                 if (mono_sgen_try_alloc_space (alloc_size, SPACE_LOS)) {
 373                         obj = mono_sgen_alloc_os_memory (alloc_size, TRUE);
 374                         obj->huge_object = TRUE;
 375                 }
 376         } else {
 377                 obj = get_los_section_memory (size + sizeof (LOSObject));
 378                 if (obj)
 379                         memset (obj, 0, size + sizeof (LOSObject));
 380         }
 381 #endif
 382 #endif
 383         if (!obj)
 384                 return NULL;
 385         g_assert (!((mword)obj->data & (SGEN_ALLOC_ALIGN - 1)));
 386         obj->size = size;
 387         vtslot = (void**)obj->data;
 388         *vtslot = vtable;
 389         mono_sgen_update_heap_boundaries ((mword)obj->data, (mword)obj->data + size);
 390         obj->next = los_object_list;
 391         los_object_list = obj;
 392         los_memory_usage += size;
 393         los_num_objects++;
 394         DEBUG (4, fprintf (gc_debug_file, "Allocated large object %p, vtable: %p (%s), size: %zd\n", obj->data, vtable, vtable->klass->name, size));
 395         binary_protocol_alloc (obj->data, vtable, size);
 396
 397 #ifdef LOS_CONSISTENCY_CHECK
 398         los_consistency_check ();
 399 #endif
 400
 401         return obj->data;
 402 }
 403
 404 void
 405 mono_sgen_los_sweep (void)
 406 {
 407         LOSSection *section, *prev;
 408         int i;
 409         int num_sections = 0;
 410
 411         for (i = 0; i < LOS_NUM_FAST_SIZES; ++i)
 412                 los_fast_free_lists [i] = NULL;
 413
 414         prev = NULL;
 415         section = los_sections;
 416         while (section) {
 417                 if (section->num_free_chunks == LOS_SECTION_NUM_CHUNKS) {
 418                         LOSSection *next = section->next;
 419                         if (prev)
 420                                 prev->next = next;
 421                         else
 422                                 los_sections = next;
 423                         mono_sgen_free_os_memory (section, LOS_SECTION_SIZE);
 424                         mono_sgen_release_space (LOS_SECTION_SIZE, SPACE_LOS);
 425                         section = next;
 426                         --los_num_sections;
 427                         continue;
 428                 }
 429
 430                 for (i = 0; i <= LOS_SECTION_NUM_CHUNKS; ++i) {
 431                         if (section->free_chunk_map [i]) {
 432                                 int j;
 433                                 for (j = i + 1; j <= LOS_SECTION_NUM_CHUNKS && section->free_chunk_map [j]; ++j)
 434                                         ;
 435                                 add_free_chunk ((LOSFreeChunks*)((char*)section + (i << LOS_CHUNK_BITS)), (j - i) << LOS_CHUNK_BITS);
 436                                 i = j - 1;
 437                         }
 438                 }
 439
 440                 prev = section;
 441                 section = section->next;
 442
 443                 ++num_sections;
 444         }
 445
 446 #ifdef LOS_CONSISTENCY_CHECK
 447         los_consistency_check ();
 448 #endif
 449
 450         /*
 451         g_print ("LOS sections: %d  objects: %d  usage: %d\n", num_sections, los_num_objects, los_memory_usage);
 452         for (i = 0; i < LOS_NUM_FAST_SIZES; ++i) {
 453                 int num_chunks = 0;
 454                 LOSFreeChunks *free_chunks;
 455                 for (free_chunks = los_fast_free_lists [i]; free_chunks; free_chunks = free_chunks->next_size)
 456                         ++num_chunks;
 457                 g_print ("  %d: %d\n", i, num_chunks);
 458         }
 459         */
 460
 461         g_assert (los_num_sections == num_sections);
 462 }
 463
 464 gboolean
 465 mono_sgen_ptr_is_in_los (char *ptr, char **start)
 466 {
 467         LOSObject *obj;
 468
 469         *start = NULL;
 470         for (obj = los_object_list; obj; obj = obj->next) {
 471                 char *end = obj->data + obj->size;
 472
 473                 if (ptr >= obj->data && ptr < end) {
 474                         *start = obj->data;
 475                         return TRUE;
 476                 }
 477         }
 478         return FALSE;
 479 }
 480
 481 void
 482 mono_sgen_los_iterate_objects (IterateObjectCallbackFunc cb, void *user_data)
 483 {
 484         LOSObject *obj;
 485
 486         for (obj = los_object_list; obj; obj = obj->next)
 487                 cb (obj->data, obj->size, user_data);
 488 }
 489
 490 void
 491 mono_sgen_los_iterate_live_block_ranges (sgen_cardtable_block_callback callback)
 492 {
 493         LOSObject *obj;
 494         for (obj = los_object_list; obj; obj = obj->next) {
 495                 MonoVTable *vt = (MonoVTable*)SGEN_LOAD_VTABLE (obj->data);
 496                 if (vt->klass->has_references)
 497                         callback ((mword)obj->data, (mword)obj->size);
 498         }
 499 }
 500
 501 void
 502 mono_sgen_los_scan_card_table (SgenGrayQueue *queue)
 503 {
 504         LOSObject *obj;
 505
 506         for (obj = los_object_list; obj; obj = obj->next) {
 507                 sgen_cardtable_scan_object (obj->data, obj->size, NULL, queue);
 508         }
 509 }
 510
 511 #endif /* HAVE_SGEN_GC */