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