mono/metadata/sgen-los.c

   1 /*
   2  * sgen-los.c: Large objects space.
   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  * Copyright 2001-2003 Ximian, Inc
  15  * Copyright 2003-2010 Novell, Inc.
  16  * Copyright (C) 2012 Xamarin Inc
  17  *
  18  * This library is free software; you can redistribute it and/or
  19  * modify it under the terms of the GNU Library General Public
  20  * License 2.0 as published by the Free Software Foundation;
  21  *
  22  * This library is distributed in the hope that it will be useful,
  23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  25  * Library General Public License for more details.
  26  *
  27  * You should have received a copy of the GNU Library General Public
  28  * License 2.0 along with this library; if not, write to the Free
  29  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  30  */
  31
  32 #include "config.h"
  33
  34 #ifdef HAVE_SGEN_GC
  35
  36 #include "metadata/sgen-gc.h"
  37 #include "metadata/sgen-protocol.h"
  38 #include "metadata/sgen-cardtable.h"
  39 #include "metadata/sgen-memory-governor.h"
  40 #include "utils/mono-mmap.h"
  41
  42 #define LOS_SECTION_SIZE        (1024 * 1024)
  43
  44 /*
  45  * This shouldn't be much smaller or larger than MAX_SMALL_OBJ_SIZE.
  46  * Must be at least sizeof (LOSSection).
  47  */
  48 #define LOS_CHUNK_SIZE          4096
  49 #define LOS_CHUNK_BITS          12
  50
  51 /* Largest object that can be allocated in a section. */
  52 #define LOS_SECTION_OBJECT_LIMIT        (LOS_SECTION_SIZE - LOS_CHUNK_SIZE - sizeof (LOSObject))
  53 //#define LOS_SECTION_OBJECT_LIMIT      0
  54 #define LOS_SECTION_NUM_CHUNKS          ((LOS_SECTION_SIZE >> LOS_CHUNK_BITS) - 1)
  55
  56 #define LOS_SECTION_FOR_OBJ(obj)        ((LOSSection*)((mword)(obj) & ~(mword)(LOS_SECTION_SIZE - 1)))
  57 #define LOS_CHUNK_INDEX(obj,section)    (((char*)(obj) - (char*)(section)) >> LOS_CHUNK_BITS)
  58
  59 #define LOS_NUM_FAST_SIZES              32
  60
  61 typedef struct _LOSFreeChunks LOSFreeChunks;
  62 struct _LOSFreeChunks {
  63         LOSFreeChunks *next_size;
  64         size_t size;
  65 };
  66
  67 typedef struct _LOSSection LOSSection;
  68 struct _LOSSection {
  69         LOSSection *next;
  70         int num_free_chunks;
  71         unsigned char *free_chunk_map;
  72 };
  73
  74 LOSObject *los_object_list = NULL;
  75 mword los_memory_usage = 0;
  76
  77 static LOSSection *los_sections = NULL;
  78 static LOSFreeChunks *los_fast_free_lists [LOS_NUM_FAST_SIZES]; /* 0 is for larger sizes */
  79 static mword los_num_objects = 0;
  80 static int los_num_sections = 0;
  81
  82 //#define USE_MALLOC
  83 //#define LOS_CONSISTENCY_CHECK
  84 //#define LOS_DUMMY
  85
  86 #ifdef LOS_DUMMY
  87 #define LOS_SEGMENT_SIZE        (4096 * 1024)
  88
  89 static char *los_segment = NULL;
  90 static int los_segment_index = 0;
  91 #endif
  92
  93 #ifdef LOS_CONSISTENCY_CHECK
  94 static void
  95 los_consistency_check (void)
  96 {
  97         LOSSection *section;
  98         LOSObject *obj;
  99         int i;
 100         mword memory_usage = 0;
 101
 102         for (obj = los_object_list; obj; obj = obj->next) {
 103                 char *end = obj->data + obj->size;
 104                 int start_index, num_chunks;
 105
 106                 memory_usage += obj->size;
 107
 108                 if (obj->size > LOS_SECTION_OBJECT_LIMIT)
 109                         continue;
 110
 111                 section = LOS_SECTION_FOR_OBJ (obj);
 112
 113                 g_assert (end <= (char*)section + LOS_SECTION_SIZE);
 114
 115                 start_index = LOS_CHUNK_INDEX (obj, section);
 116                 num_chunks = (obj->size + sizeof (LOSObject) + LOS_CHUNK_SIZE - 1) >> LOS_CHUNK_BITS;
 117                 for (i = start_index; i < start_index + num_chunks; ++i)
 118                         g_assert (!section->free_chunk_map [i]);
 119         }
 120
 121         for (i = 0; i < LOS_NUM_FAST_SIZES; ++i) {
 122                 LOSFreeChunks *size_chunks;
 123                 for (size_chunks = los_fast_free_lists [i]; size_chunks; size_chunks = size_chunks->next_size) {
 124                         LOSSection *section = LOS_SECTION_FOR_OBJ (size_chunks);
 125                         int j, num_chunks, start_index;
 126
 127                         if (i == 0)
 128                                 g_assert (size_chunks->size >= LOS_NUM_FAST_SIZES * LOS_CHUNK_SIZE);
 129                         else
 130                                 g_assert (size_chunks->size == i * LOS_CHUNK_SIZE);
 131
 132                         num_chunks = size_chunks->size >> LOS_CHUNK_BITS;
 133                         start_index = LOS_CHUNK_INDEX (size_chunks, section);
 134                         for (j = start_index; j < start_index + num_chunks; ++j)
 135                                 g_assert (section->free_chunk_map [j]);
 136                 }
 137         }
 138
 139         g_assert (los_memory_usage == memory_usage);
 140 }
 141 #endif
 142
 143 static void
 144 add_free_chunk (LOSFreeChunks *free_chunks, size_t size)
 145 {
 146         int num_chunks = size >> LOS_CHUNK_BITS;
 147
 148         free_chunks->size = size;
 149
 150         if (num_chunks >= LOS_NUM_FAST_SIZES)
 151                 num_chunks = 0;
 152         free_chunks->next_size = los_fast_free_lists [num_chunks];
 153         los_fast_free_lists [num_chunks] = free_chunks;
 154 }
 155
 156 static LOSFreeChunks*
 157 get_from_size_list (LOSFreeChunks **list, size_t size)
 158 {
 159         LOSFreeChunks *free_chunks = NULL;
 160         LOSSection *section;
 161         int num_chunks, i, start_index;
 162
 163         g_assert ((size & (LOS_CHUNK_SIZE - 1)) == 0);
 164
 165         while (*list) {
 166                 free_chunks = *list;
 167                 if (free_chunks->size >= size)
 168                         break;
 169                 list = &(*list)->next_size;
 170         }
 171
 172         if (!*list)
 173                 return NULL;
 174
 175         *list = free_chunks->next_size;
 176
 177         if (free_chunks->size > size)
 178                 add_free_chunk ((LOSFreeChunks*)((char*)free_chunks + size), free_chunks->size - size);
 179
 180         num_chunks = size >> LOS_CHUNK_BITS;
 181
 182         section = LOS_SECTION_FOR_OBJ (free_chunks);
 183
 184         start_index = LOS_CHUNK_INDEX (free_chunks, section);
 185         for (i = start_index; i < start_index + num_chunks; ++i) {
 186                 g_assert (section->free_chunk_map [i]);
 187                 section->free_chunk_map [i] = 0;
 188         }
 189
 190         section->num_free_chunks -= size >> LOS_CHUNK_BITS;
 191         g_assert (section->num_free_chunks >= 0);
 192
 193         return free_chunks;
 194 }
 195
 196 static LOSObject*
 197 get_los_section_memory (size_t size)
 198 {
 199         LOSSection *section;
 200         LOSFreeChunks *free_chunks;
 201         int num_chunks;
 202
 203         size += LOS_CHUNK_SIZE - 1;
 204         size &= ~(LOS_CHUNK_SIZE - 1);
 205
 206         num_chunks = size >> LOS_CHUNK_BITS;
 207
 208         g_assert (size > 0 && size - sizeof (LOSObject) <= LOS_SECTION_OBJECT_LIMIT);
 209         g_assert (num_chunks > 0);
 210
 211  retry:
 212         if (num_chunks >= LOS_NUM_FAST_SIZES) {
 213                 free_chunks = get_from_size_list (&los_fast_free_lists [0], size);
 214         } else {
 215                 int i;
 216                 for (i = num_chunks; i < LOS_NUM_FAST_SIZES; ++i) {
 217                         free_chunks = get_from_size_list (&los_fast_free_lists [i], size);
 218                         if (free_chunks)
 219                                 break;
 220                 }
 221                 if (!free_chunks)
 222                         free_chunks = get_from_size_list (&los_fast_free_lists [0], size);
 223         }
 224
 225         if (free_chunks)
 226                 return (LOSObject*)free_chunks;
 227
 228         if (!sgen_memgov_try_alloc_space (LOS_SECTION_SIZE, SPACE_LOS))
 229                 return NULL;
 230
 231         section = sgen_alloc_os_memory_aligned (LOS_SECTION_SIZE, LOS_SECTION_SIZE, SGEN_ALLOC_HEAP | SGEN_ALLOC_ACTIVATE, NULL);
 232
 233         if (!section)
 234                 return NULL;
 235
 236         free_chunks = (LOSFreeChunks*)((char*)section + LOS_CHUNK_SIZE);
 237         free_chunks->size = LOS_SECTION_SIZE - LOS_CHUNK_SIZE;
 238         free_chunks->next_size = los_fast_free_lists [0];
 239         los_fast_free_lists [0] = free_chunks;
 240
 241         section->num_free_chunks = LOS_SECTION_NUM_CHUNKS;
 242
 243         section->free_chunk_map = (unsigned char*)section + sizeof (LOSSection);
 244         g_assert (sizeof (LOSSection) + LOS_SECTION_NUM_CHUNKS + 1 <= LOS_CHUNK_SIZE);
 245         section->free_chunk_map [0] = 0;
 246         memset (section->free_chunk_map + 1, 1, LOS_SECTION_NUM_CHUNKS);
 247
 248         section->next = los_sections;
 249         los_sections = section;
 250
 251         ++los_num_sections;
 252
 253         goto retry;
 254 }
 255
 256 static void
 257 free_los_section_memory (LOSObject *obj, size_t size)
 258 {
 259         LOSSection *section = LOS_SECTION_FOR_OBJ (obj);
 260         int num_chunks, i, start_index;
 261
 262         size += LOS_CHUNK_SIZE - 1;
 263         size &= ~(LOS_CHUNK_SIZE - 1);
 264
 265         num_chunks = size >> LOS_CHUNK_BITS;
 266
 267         g_assert (size > 0 && size - sizeof (LOSObject) <= LOS_SECTION_OBJECT_LIMIT);
 268         g_assert (num_chunks > 0);
 269
 270         section->num_free_chunks += num_chunks;
 271         g_assert (section->num_free_chunks <= LOS_SECTION_NUM_CHUNKS);
 272
 273         /*
 274          * We could free the LOS section here if it's empty, but we
 275          * can't unless we also remove its free chunks from the fast
 276          * free lists.  Instead, we do it in los_sweep().
 277          */
 278
 279         start_index = LOS_CHUNK_INDEX (obj, section);
 280         for (i = start_index; i < start_index + num_chunks; ++i) {
 281                 g_assert (!section->free_chunk_map [i]);
 282                 section->free_chunk_map [i] = 1;
 283         }
 284
 285         add_free_chunk ((LOSFreeChunks*)obj, size);
 286 }
 287
 288 static int pagesize;
 289
 290 void
 291 sgen_los_free_object (LOSObject *obj)
 292 {
 293 #ifndef LOS_DUMMY
 294         size_t size = obj->size;
 295         SGEN_LOG (4, "Freed large object %p, size %lu", obj->data, (unsigned long)obj->size);
 296         binary_protocol_empty (obj->data, obj->size);
 297
 298         los_memory_usage -= size;
 299         los_num_objects--;
 300
 301 #ifdef USE_MALLOC
 302         free (obj);
 303 #else
 304         if (size > LOS_SECTION_OBJECT_LIMIT) {
 305                 if (!pagesize)
 306                         pagesize = mono_pagesize ();
 307                 size += sizeof (LOSObject);
 308                 size += pagesize - 1;
 309                 size &= ~(pagesize - 1);
 310                 sgen_free_os_memory (obj, size, SGEN_ALLOC_HEAP);
 311                 sgen_memgov_release_space (size, SPACE_LOS);
 312         } else {
 313                 free_los_section_memory (obj, size + sizeof (LOSObject));
 314 #ifdef LOS_CONSISTENCY_CHECKS
 315                 los_consistency_check ();
 316 #endif
 317         }
 318 #endif
 319 #endif
 320 }
 321
 322 /*
 323  * Objects with size >= MAX_SMALL_SIZE are allocated in the large object space.
 324  * They are currently kept track of with a linked list.
 325  * They don't move, so there is no need to pin them during collection
 326  * and we avoid the memcpy overhead.
 327  */
 328 void*
 329 sgen_los_alloc_large_inner (MonoVTable *vtable, size_t size)
 330 {
 331         LOSObject *obj = NULL;
 332         void **vtslot;
 333
 334         g_assert (size > SGEN_MAX_SMALL_OBJ_SIZE);
 335         g_assert ((size & 1) == 0);
 336
 337         /*
 338          * size + sizeof (LOSObject) <= SIZE_MAX - (mono_pagesize () - 1)
 339          *
 340          * therefore:
 341          *
 342          * size <= SIZE_MAX - (mono_pagesize () - 1) - sizeof (LOSObject)
 343          */
 344         if (size > SIZE_MAX - (mono_pagesize () - 1) - sizeof (LOSObject))
 345                 return NULL;
 346
 347 #ifdef LOS_DUMMY
 348         if (!los_segment)
 349                 los_segment = sgen_alloc_os_memory (LOS_SEGMENT_SIZE, SGEN_ALLOC_HEAP | SGEN_ALLOC_ACTIVATE, NULL);
 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         sgen_ensure_free_space (size);
 357
 358 #ifdef USE_MALLOC
 359         obj = malloc (size + sizeof (LOSObject));
 360         memset (obj, 0, size + sizeof (LOSObject));
 361 #else
 362         if (size > LOS_SECTION_OBJECT_LIMIT) {
 363                 size_t alloc_size = size;
 364                 if (!pagesize)
 365                         pagesize = mono_pagesize ();
 366                 alloc_size += sizeof (LOSObject);
 367                 alloc_size += pagesize - 1;
 368                 alloc_size &= ~(pagesize - 1);
 369                 if (sgen_memgov_try_alloc_space (alloc_size, SPACE_LOS)) {
 370                         obj = sgen_alloc_os_memory (alloc_size, SGEN_ALLOC_HEAP | SGEN_ALLOC_ACTIVATE, NULL);
 371                 }
 372         } else {
 373                 obj = get_los_section_memory (size + sizeof (LOSObject));
 374                 if (obj)
 375                         memset (obj, 0, size + sizeof (LOSObject));
 376         }
 377 #endif
 378 #endif
 379         if (!obj)
 380                 return NULL;
 381         g_assert (!((mword)obj->data & (SGEN_ALLOC_ALIGN - 1)));
 382         obj->size = size;
 383         vtslot = (void**)obj->data;
 384         *vtslot = vtable;
 385         sgen_update_heap_boundaries ((mword)obj->data, (mword)obj->data + size);
 386         obj->next = los_object_list;
 387         los_object_list = obj;
 388         los_memory_usage += size;
 389         los_num_objects++;
 390         SGEN_LOG (4, "Allocated large object %p, vtable: %p (%s), size: %zd", obj->data, vtable, vtable->klass->name, size);
 391         binary_protocol_alloc (obj->data, vtable, size);
 392
 393 #ifdef LOS_CONSISTENCY_CHECK
 394         los_consistency_check ();
 395 #endif
 396
 397         return obj->data;
 398 }
 399
 400 void
 401 sgen_los_sweep (void)
 402 {
 403         LOSSection *section, *prev;
 404         int i;
 405         int num_sections = 0;
 406
 407         for (i = 0; i < LOS_NUM_FAST_SIZES; ++i)
 408                 los_fast_free_lists [i] = NULL;
 409
 410         prev = NULL;
 411         section = los_sections;
 412         while (section) {
 413                 if (section->num_free_chunks == LOS_SECTION_NUM_CHUNKS) {
 414                         LOSSection *next = section->next;
 415                         if (prev)
 416                                 prev->next = next;
 417                         else
 418                                 los_sections = next;
 419                         sgen_free_os_memory (section, LOS_SECTION_SIZE, SGEN_ALLOC_HEAP);
 420                         sgen_memgov_release_space (LOS_SECTION_SIZE, SPACE_LOS);
 421                         section = next;
 422                         --los_num_sections;
 423                         continue;
 424                 }
 425
 426                 for (i = 0; i <= LOS_SECTION_NUM_CHUNKS; ++i) {
 427                         if (section->free_chunk_map [i]) {
 428                                 int j;
 429                                 for (j = i + 1; j <= LOS_SECTION_NUM_CHUNKS && section->free_chunk_map [j]; ++j)
 430                                         ;
 431                                 add_free_chunk ((LOSFreeChunks*)((char*)section + (i << LOS_CHUNK_BITS)), (j - i) << LOS_CHUNK_BITS);
 432                                 i = j - 1;
 433                         }
 434                 }
 435
 436                 prev = section;
 437                 section = section->next;
 438
 439                 ++num_sections;
 440         }
 441
 442 #ifdef LOS_CONSISTENCY_CHECK
 443         los_consistency_check ();
 444 #endif
 445
 446         /*
 447         g_print ("LOS sections: %d  objects: %d  usage: %d\n", num_sections, los_num_objects, los_memory_usage);
 448         for (i = 0; i < LOS_NUM_FAST_SIZES; ++i) {
 449                 int num_chunks = 0;
 450                 LOSFreeChunks *free_chunks;
 451                 for (free_chunks = los_fast_free_lists [i]; free_chunks; free_chunks = free_chunks->next_size)
 452                         ++num_chunks;
 453                 g_print ("  %d: %d\n", i, num_chunks);
 454         }
 455         */
 456
 457         g_assert (los_num_sections == num_sections);
 458 }
 459
 460 gboolean
 461 sgen_ptr_is_in_los (char *ptr, char **start)
 462 {
 463         LOSObject *obj;
 464
 465         *start = NULL;
 466         for (obj = los_object_list; obj; obj = obj->next) {
 467                 char *end = obj->data + obj->size;
 468
 469                 if (ptr >= obj->data && ptr < end) {
 470                         *start = obj->data;
 471                         return TRUE;
 472                 }
 473         }
 474         return FALSE;
 475 }
 476
 477 void
 478 sgen_los_iterate_objects (IterateObjectCallbackFunc cb, void *user_data)
 479 {
 480         LOSObject *obj;
 481
 482         for (obj = los_object_list; obj; obj = obj->next)
 483                 cb (obj->data, obj->size, user_data);
 484 }
 485
 486 gboolean
 487 sgen_los_is_valid_object (char *object)
 488 {
 489         LOSObject *obj;
 490
 491         for (obj = los_object_list; obj; obj = obj->next) {
 492                 if (obj->data == object)
 493                         return TRUE;
 494         }
 495         return FALSE;
 496 }
 497
 498 gboolean
 499 mono_sgen_los_describe_pointer (char *ptr)
 500 {
 501         LOSObject *obj;
 502
 503         for (obj = los_object_list; obj; obj = obj->next) {
 504                 MonoVTable *vtable;
 505                 const char *los_kind;
 506                 mword size;
 507                 gboolean pinned;
 508
 509                 if (obj->data > ptr || obj->data + obj->size <= ptr)
 510                         continue;
 511
 512                 size = sgen_los_object_size (obj);
 513                 pinned = sgen_los_object_is_pinned (obj->data);
 514
 515                 if (size > LOS_SECTION_OBJECT_LIMIT)
 516                         los_kind = "huge-los-ptr";
 517                 else
 518                         los_kind = "los-ptr";
 519
 520                 vtable = (MonoVTable*)SGEN_LOAD_VTABLE (obj->data);
 521
 522                 if (obj->data == ptr) {
 523                         SGEN_LOG (0, "%s (size %d pin %d)\n", los_kind, (int)size, pinned ? 1 : 0);
 524                 } else {
 525                         SGEN_LOG (0, "%s (interior-ptr offset %td size %d pin %d)",
 526                                           los_kind, ptr - obj->data, (int)size, pinned ? 1 : 0);
 527                 }
 528
 529                 return TRUE;
 530         }
 531         return FALSE;
 532 }
 533
 534 void
 535 sgen_los_iterate_live_block_ranges (sgen_cardtable_block_callback callback)
 536 {
 537         LOSObject *obj;
 538         for (obj = los_object_list; obj; obj = obj->next) {
 539                 MonoVTable *vt = (MonoVTable*)SGEN_LOAD_VTABLE (obj->data);
 540                 if (SGEN_VTABLE_HAS_REFERENCES (vt))
 541                         callback ((mword)obj->data, (mword)obj->size);
 542         }
 543 }
 544
 545 void
 546 sgen_los_scan_card_table (gboolean mod_union, SgenGrayQueue *queue)
 547 {
 548         LOSObject *obj;
 549
 550         for (obj = los_object_list; obj; obj = obj->next) {
 551                 guint8 *cards = NULL;
 552                 if (mod_union) {
 553                         cards = obj->cardtable_mod_union;
 554                         g_assert (cards);
 555                 }
 556
 557                 sgen_cardtable_scan_object (obj->data, obj->size, cards, mod_union, queue);
 558         }
 559 }
 560
 561 void
 562 sgen_los_update_cardtable_mod_union (void)
 563 {
 564         LOSObject *obj;
 565
 566         for (obj = los_object_list; obj; obj = obj->next) {
 567                 obj->cardtable_mod_union = sgen_card_table_update_mod_union (obj->cardtable_mod_union,
 568                                 obj->data, obj->size, NULL);
 569         }
 570 }
 571
 572 mword
 573 sgen_los_object_size (LOSObject *obj)
 574 {
 575         return obj->size & ~1L;
 576 }
 577
 578 LOSObject*
 579 sgen_los_header_for_object (char *data)
 580 {
 581 #if _MSC_VER
 582         return (LOSObject*)(data - (int)(&(((LOSObject*)0)->data)));
 583 #else
 584         return (LOSObject*)(data - sizeof (LOSObject));
 585 #endif
 586 }
 587
 588 void
 589 sgen_los_pin_object (char *data)
 590 {
 591         LOSObject *obj = sgen_los_header_for_object (data);
 592         obj->size = obj->size | 1;
 593         binary_protocol_pin (data, (gpointer)SGEN_LOAD_VTABLE (data), sgen_safe_object_get_size ((MonoObject*)data));
 594 }
 595
 596 void
 597 sgen_los_unpin_object (char *data)
 598 {
 599         LOSObject *obj = sgen_los_header_for_object (data);
 600         obj->size = sgen_los_object_size (obj);
 601 }
 602
 603 gboolean
 604 sgen_los_object_is_pinned (char *data)
 605 {
 606         LOSObject *obj = sgen_los_header_for_object (data);
 607         return obj->size & 1;
 608 }
 609
 610 #endif /* HAVE_SGEN_GC */