mono/metadata/sgen-pinned-allocator.c

   1 /*
   2  * sgen-pinned-allocator.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 "utils/mono-counters.h"
  53 #include "metadata/sgen-gc.h"
  54 #include "metadata/sgen-memory-governor.h"
  55
  56 /* Pinned objects are allocated in the LOS space if bigger than half a page
  57  * or from freelists otherwise. We assume that pinned objects are relatively few
  58  * and they have a slow dying speed (like interned strings, thread objects).
  59  * As such they will be collected only at major collections.
  60  * free lists are not global: when we need memory we allocate a PinnedChunk.
  61  * Each pinned chunk is made of several pages, the first of wich is used
  62  * internally for bookeeping (here think of a page as 4KB). The bookeeping
  63  * includes the freelists vectors and info about the object size of each page
  64  * in the pinned chunk. So, when needed, a free page is found in a pinned chunk,
  65  * a size is assigned to it, the page is divided in the proper chunks and each
  66  * chunk is added to the freelist. To not waste space, the remaining space in the
  67  * first page is used as objects of size 16 or 32 (need to measure which are more
  68  * common).
  69  * We use this same structure to allocate memory used internally by the GC, so
  70  * we never use malloc/free if we need to alloc during collection: the world is stopped
  71  * and malloc/free will deadlock.
  72  * When we want to iterate over pinned objects, we just scan a page at a time
  73  * linearly according to the size of objects in the page: the next pointer used to link
  74  * the items in the freelist uses the same word as the vtable. Since we keep freelists
  75  * for each pinned chunk, if the word points outside the pinned chunk it means
  76  * it is an object.
  77  * We could avoid this expensive scanning in creative ways. We could have a policy
  78  * of putting in the pinned space only objects we know about that have no struct fields
  79  * with references and we can easily use a even expensive write barrier for them,
  80  * since pointer writes on such objects should be rare.
  81  * The best compromise is to just alloc interned strings and System.MonoType in them.
  82  * It would be nice to allocate MonoThread in it, too: must check that we properly
  83  * use write barriers so we don't have to do any expensive scanning of the whole pinned
  84  * chunk list during minor collections. We can avoid it now because we alloc in it only
  85  * reference-free objects.
  86  */
  87 struct _SgenPinnedChunk {
  88         SgenBlock block;
  89         int num_pages;
  90         SgenPinnedAllocator *allocator;
  91         int *page_sizes; /* a 0 means the page is still unused */
  92         void **free_list;
  93         SgenPinnedChunk *free_list_nexts [SGEN_PINNED_FREELIST_NUM_SLOTS];
  94         void *start_data;
  95         void *data [1]; /* page sizes and free lists are stored here */
  96 };
  97
  98 #define PINNED_FIRST_SLOT_SIZE (sizeof (gpointer) * 4)
  99 #define MAX_FREELIST_SIZE 8192
 100
 101 /* This is a fixed value used for pinned chunks, not the system pagesize */
 102 #define FREELIST_PAGESIZE (16*1024)
 103
 104 /* keep each size a multiple of ALLOC_ALIGN */
 105 /* on 64 bit systems 8 is likely completely unused. */
 106 static const int freelist_sizes [] = {
 107            8,   16,   24,   32,   40,   48,   64,   80,
 108           96,  128,  160,  192,  224,  256,  320,  384,
 109          448,  512,  584,  680,  816, 1024, 1360, 2048,
 110         2336, 2728, 3272, 4096, 5456, 8192 };
 111
 112 #define LARGE_PINNED_MEM_HEADER_MAGIC   0x7d289f3a
 113
 114 /* FIXME: Do we even need these anymore?  Large objects are always
 115    allocated in the LOS. */
 116 typedef struct _LargePinnedMemHeader LargePinnedMemHeader;
 117 struct _LargePinnedMemHeader {
 118         guint32 magic;
 119         size_t size;
 120         double data[0];
 121 };
 122
 123 static long long pinned_chunk_bytes_alloced = 0;
 124 static long long large_pinned_bytes_alloced = 0;
 125
 126 #ifdef HEAVY_STATISTICS
 127 static long long stat_pinned_alloc = 0;
 128 #endif
 129
 130 /*
 131  * Debug reporting.
 132  */
 133 static void
 134 report_pinned_chunk (SgenPinnedChunk *chunk, int seq) {
 135         void **p;
 136         int i, free_pages, num_free, free_mem;
 137         free_pages = 0;
 138         for (i = 0; i < chunk->num_pages; ++i) {
 139                 if (!chunk->page_sizes [i])
 140                         free_pages++;
 141         }
 142         printf ("Pinned chunk %d at %p, size: %d, pages: %d, free: %d\n", seq, chunk, chunk->num_pages * FREELIST_PAGESIZE, chunk->num_pages, free_pages);
 143         free_mem = FREELIST_PAGESIZE * free_pages;
 144         for (i = 0; i < SGEN_PINNED_FREELIST_NUM_SLOTS; ++i) {
 145                 if (!chunk->free_list [i])
 146                         continue;
 147                 num_free = 0;
 148                 p = chunk->free_list [i];
 149                 while (p) {
 150                         num_free++;
 151                         p = *p;
 152                 }
 153                 printf ("\tfree list of size %d, %d items\n", freelist_sizes [i], num_free);
 154                 free_mem += freelist_sizes [i] * num_free;
 155         }
 156         printf ("\tfree memory in chunk: %d\n", free_mem);
 157 }
 158
 159 /*
 160  * Debug reporting.
 161  */
 162 void
 163 sgen_report_pinned_mem_usage (SgenPinnedAllocator *alc)
 164 {
 165         SgenPinnedChunk *chunk;
 166         int i = 0;
 167         for (chunk = alc->chunk_list; chunk; chunk = chunk->block.next)
 168                 report_pinned_chunk (chunk, i++);
 169 }
 170
 171 /*
 172  * Find the slot number in the freelist for memory chunks that
 173  * can contain @size objects.
 174  */
 175 static int
 176 slot_for_size (size_t size)
 177 {
 178         int slot;
 179         /* do a binary search or lookup table later. */
 180         for (slot = 0; slot < SGEN_PINNED_FREELIST_NUM_SLOTS; ++slot) {
 181                 if (freelist_sizes [slot] >= size)
 182                         return slot;
 183         }
 184         g_assert_not_reached ();
 185         return -1;
 186 }
 187
 188 /*
 189  * Build a free list for @size memory chunks from the memory area between
 190  * start_page and end_page.
 191  */
 192 static void
 193 build_freelist (SgenPinnedAllocator *alc, SgenPinnedChunk *chunk, int slot, int size, char *start_page, char *end_page)
 194 {
 195         void **p, **end;
 196         int count = 0;
 197         /*g_print ("building freelist for slot %d, size %d in %p\n", slot, size, chunk);*/
 198         p = (void**)start_page;
 199         end = (void**)(end_page - size);
 200         g_assert (!chunk->free_list [slot]);
 201         chunk->free_list [slot] = p;
 202         while ((char*)p + size <= (char*)end) {
 203                 count++;
 204                 *p = (void*)((char*)p + size);
 205                 p = *p;
 206         }
 207         *p = NULL;
 208         /*g_print ("%d items created, max: %d\n", count, (end_page - start_page) / size);*/
 209
 210         g_assert (!chunk->free_list_nexts [slot]);
 211         chunk->free_list_nexts [slot] = alc->free_lists [slot];
 212         alc->free_lists [slot] = chunk;
 213 }
 214
 215 static SgenPinnedChunk*
 216 alloc_pinned_chunk (SgenPinnedAllocator *alc)
 217 {
 218         SgenPinnedChunk *chunk;
 219         int offset;
 220         int size = SGEN_PINNED_CHUNK_SIZE;
 221
 222         chunk = sgen_alloc_os_memory_aligned (size, size, SGEN_ALLOC_HEAP | SGEN_ALLOC_ACTIVATE, "pinned chunk");
 223         chunk->block.role = MEMORY_ROLE_PINNED;
 224
 225         sgen_update_heap_boundaries ((mword)chunk, ((mword)chunk + size));
 226
 227         pinned_chunk_bytes_alloced += size;
 228
 229         /* setup the bookeeping fields */
 230         chunk->num_pages = size / FREELIST_PAGESIZE;
 231         offset = G_STRUCT_OFFSET (SgenPinnedChunk, data);
 232         chunk->page_sizes = (void*)((char*)chunk + offset);
 233         offset += sizeof (int) * chunk->num_pages;
 234         offset = SGEN_ALIGN_UP (offset);
 235         chunk->free_list = (void*)((char*)chunk + offset);
 236         offset += sizeof (void*) * SGEN_PINNED_FREELIST_NUM_SLOTS;
 237         offset = SGEN_ALIGN_UP (offset);
 238         chunk->start_data = (void*)((char*)chunk + offset);
 239
 240         /* allocate the first page to the freelist */
 241         chunk->page_sizes [0] = PINNED_FIRST_SLOT_SIZE;
 242         build_freelist (alc, chunk, slot_for_size (PINNED_FIRST_SLOT_SIZE), PINNED_FIRST_SLOT_SIZE,
 243                         chunk->start_data, ((char*)chunk + FREELIST_PAGESIZE));
 244         sgen_debug_printf (4, "Allocated pinned chunk %p, size: %d\n", chunk, size);
 245
 246         chunk->block.next = alc->chunk_list;
 247         alc->chunk_list = chunk;
 248
 249         chunk->allocator = alc;
 250
 251         return chunk;
 252 }
 253
 254 /* Must be called with an empty freelist for the given slot. */
 255 static gboolean
 256 populate_chunk_page (SgenPinnedAllocator *alc, SgenPinnedChunk *chunk, int slot)
 257 {
 258         int size = freelist_sizes [slot];
 259         int i;
 260         g_assert (!chunk->free_list [slot]);
 261         g_assert (!chunk->free_list_nexts [slot]);
 262         for (i = 0; i < chunk->num_pages; ++i) {
 263                 if (chunk->page_sizes [i])
 264                         continue;
 265                 chunk->page_sizes [i] = size;
 266                 build_freelist (alc, chunk, slot, size, (char*)chunk + FREELIST_PAGESIZE * i, (char*)chunk + FREELIST_PAGESIZE * (i + 1));
 267                 return TRUE;
 268         }
 269         return FALSE;
 270 }
 271
 272 static void*
 273 alloc_from_slot (SgenPinnedAllocator *alc, int slot)
 274 {
 275         SgenPinnedChunk *pchunk;
 276         size_t size = freelist_sizes [slot];
 277
 278         if (alc->delayed_free_lists [slot]) {
 279                 void **p;
 280                 do {
 281                         p = alc->delayed_free_lists [slot];
 282                 } while (SGEN_CAS_PTR (&alc->delayed_free_lists [slot], *p, p) != p);
 283                 memset (p, 0, size);
 284                 return p;
 285         }
 286
 287  restart:
 288         pchunk = alc->free_lists [slot];
 289         if (pchunk) {
 290                 void **p = pchunk->free_list [slot];
 291                 void *next;
 292
 293                 g_assert (p);
 294
 295                 next = *p;
 296                 pchunk->free_list [slot] = next;
 297
 298                 if (!next) {
 299                         alc->free_lists [slot] = pchunk->free_list_nexts [slot];
 300                         pchunk->free_list_nexts [slot] = NULL;
 301                 }
 302
 303                 memset (p, 0, size);
 304                 return p;
 305         }
 306
 307         for (pchunk = alc->chunk_list; pchunk; pchunk = pchunk->block.next) {
 308                 if (populate_chunk_page (alc, pchunk, slot))
 309                         goto restart;
 310         }
 311
 312         pchunk = alloc_pinned_chunk (alc);
 313         /* FIXME: handle OOM */
 314         if (pchunk->free_list [slot])
 315                 goto restart;
 316         if (!populate_chunk_page (alc, pchunk, slot))
 317                 g_assert_not_reached ();
 318         goto restart;
 319 }
 320
 321 /* used for the GC-internal data structures */
 322 void*
 323 sgen_alloc_pinned (SgenPinnedAllocator *alc, size_t size)
 324 {
 325         int slot;
 326         void *res = NULL;
 327
 328         HEAVY_STAT (++stat_pinned_alloc);
 329
 330         if (size > freelist_sizes [SGEN_PINNED_FREELIST_NUM_SLOTS - 1]) {
 331                 LargePinnedMemHeader *mh;
 332
 333                 size += sizeof (LargePinnedMemHeader);
 334                 mh = sgen_alloc_os_memory (size, SGEN_ALLOC_HEAP | SGEN_ALLOC_ACTIVATE, "large pinned object");
 335                 mh->magic = LARGE_PINNED_MEM_HEADER_MAGIC;
 336                 mh->size = size;
 337                 /* FIXME: do a CAS here */
 338                 large_pinned_bytes_alloced += size;
 339                 return mh->data;
 340         }
 341
 342         slot = slot_for_size (size);
 343         g_assert (size <= freelist_sizes [slot]);
 344         res = alloc_from_slot (alc, slot);
 345
 346         return res;
 347 }
 348
 349 static void
 350 free_from_slot (SgenPinnedAllocator *alc, void *addr, int slot)
 351 {
 352         SgenPinnedChunk *pchunk = (SgenPinnedChunk*)SGEN_PINNED_CHUNK_FOR_PTR (addr);
 353         void **p = addr;
 354         void *next;
 355
 356         g_assert (addr >= (void*)pchunk && (char*)addr < (char*)pchunk + pchunk->num_pages * FREELIST_PAGESIZE);
 357
 358         next = pchunk->free_list [slot];
 359         *p = next;
 360         pchunk->free_list [slot] = p;
 361
 362         if (!next) {
 363                 g_assert (!pchunk->free_list_nexts [slot]);
 364                 pchunk->free_list_nexts [slot] = alc->free_lists [slot];
 365                 alc->free_lists [slot] = pchunk;
 366         }
 367 }
 368
 369 void
 370 sgen_free_pinned (SgenPinnedAllocator *alc, void *addr, size_t size)
 371 {
 372         LargePinnedMemHeader *mh;
 373
 374         if (!addr)
 375                 return;
 376
 377         if (size <= freelist_sizes [SGEN_PINNED_FREELIST_NUM_SLOTS - 1]) {
 378                 int slot = slot_for_size (size);
 379                 free_from_slot (alc, addr, slot);
 380                 return;
 381         }
 382
 383         mh = (LargePinnedMemHeader*)((char*)addr - G_STRUCT_OFFSET (LargePinnedMemHeader, data));
 384         g_assert (mh->magic == LARGE_PINNED_MEM_HEADER_MAGIC);
 385         g_assert (mh->size == size + sizeof (LargePinnedMemHeader));
 386         /* FIXME: do a CAS */
 387         large_pinned_bytes_alloced -= mh->size;
 388         sgen_free_os_memory (mh, mh->size, SGEN_ALLOC_HEAP);
 389 }
 390
 391 void
 392 sgen_init_pinned_allocator (void)
 393 {
 394         g_assert (SGEN_PINNED_FREELIST_NUM_SLOTS == sizeof (freelist_sizes) / sizeof (freelist_sizes [0]));
 395
 396 #ifdef HEAVY_STATISTICS
 397         mono_counters_register ("Pinned allocs", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_pinned_alloc);
 398 #endif
 399 }
 400
 401 void
 402 sgen_pinned_scan_objects (SgenPinnedAllocator *alc, IterateObjectCallbackFunc callback, void *callback_data)
 403 {
 404         SgenPinnedChunk *chunk;
 405         int i, obj_size;
 406         char *p, *endp;
 407         void **ptr;
 408         void *end_chunk;
 409         for (chunk = alc->chunk_list; chunk; chunk = chunk->block.next) {
 410                 end_chunk = (char*)chunk + chunk->num_pages * FREELIST_PAGESIZE;
 411                 sgen_debug_printf (6, "Scanning pinned chunk %p (range: %p-%p)\n", chunk, chunk->start_data, end_chunk);
 412                 for (i = 0; i < chunk->num_pages; ++i) {
 413                         obj_size = chunk->page_sizes [i];
 414                         if (!obj_size)
 415                                 continue;
 416                         p = i? (char*)chunk + i * FREELIST_PAGESIZE: chunk->start_data;
 417                         endp = i? p + FREELIST_PAGESIZE: (char*)chunk + FREELIST_PAGESIZE;
 418                         sgen_debug_printf (6, "Page %d (size: %d, range: %p-%p)\n", i, obj_size, p, endp);
 419                         while (p + obj_size <= endp) {
 420                                 ptr = (void**)p;
 421                                 /* if the first word (the vtable) is outside the chunk we have an object */
 422                                 if (*ptr && (*ptr < (void*)chunk || *ptr >= end_chunk))
 423                                         callback ((char*)ptr, obj_size, callback_data);
 424                                 p += obj_size;
 425                         }
 426                 }
 427         }
 428 }
 429
 430 void
 431 sgen_pinned_update_heap_boundaries (SgenPinnedAllocator *alc)
 432 {
 433         SgenPinnedChunk *chunk;
 434         for (chunk = alc->chunk_list; chunk; chunk = chunk->block.next) {
 435                 char *end_chunk = (char*)chunk + chunk->num_pages * FREELIST_PAGESIZE;
 436                 sgen_update_heap_boundaries ((mword)chunk, (mword)end_chunk);
 437         }
 438 }
 439
 440 /*
 441  * the array of pointers from @start to @end contains conservative
 442  * pointers to objects inside @chunk: mark each referenced object
 443  * with the PIN bit.
 444  */
 445 static void
 446 mark_pinned_from_addresses (SgenPinnedChunk *chunk, void **start, void **end, IterateObjectCallbackFunc callback, void *callback_data)
 447 {
 448         for (; start < end; start++) {
 449                 char *addr = *start;
 450                 int offset = (char*)addr - (char*)chunk;
 451                 int page = offset / FREELIST_PAGESIZE;
 452                 int obj_offset = page == 0? offset - ((char*)chunk->start_data - (char*)chunk): offset % FREELIST_PAGESIZE;
 453                 int slot_size = chunk->page_sizes [page];
 454                 void **ptr;
 455                 /* the page is not allocated */
 456                 if (!slot_size)
 457                         continue;
 458                 /* would be faster if we restrict the sizes to power of two,
 459                  * but that's a waste of memory: need to measure. it could reduce
 460                  * fragmentation since there are less pages needed, if for example
 461                  * someone interns strings of each size we end up with one page per
 462                  * interned string (still this is just ~40 KB): with more fine-grained sizes
 463                  * this increases the number of used pages.
 464                  */
 465                 if (page == 0) {
 466                         obj_offset /= slot_size;
 467                         obj_offset *= slot_size;
 468                         addr = (char*)chunk->start_data + obj_offset;
 469                 } else {
 470                         obj_offset /= slot_size;
 471                         obj_offset *= slot_size;
 472                         addr = (char*)chunk + page * FREELIST_PAGESIZE + obj_offset;
 473                 }
 474                 ptr = (void**)addr;
 475                 /* if the vtable is inside the chunk it's on the freelist, so skip */
 476                 /* FIXME: is it possible that we're pinning objects more than once here? */
 477                 if (*ptr && (*ptr < (void*)chunk->start_data || *ptr > (void*)((char*)chunk + chunk->num_pages * FREELIST_PAGESIZE)))
 478                         callback (addr, slot_size, callback_data);
 479         }
 480 }
 481
 482 void
 483 sgen_pinned_scan_pinned_objects (SgenPinnedAllocator *alc, IterateObjectCallbackFunc callback, void *callback_data)
 484 {
 485         SgenPinnedChunk *chunk;
 486
 487         /* look for pinned addresses for pinned-alloc objects */
 488         sgen_debug_printf (6, "Pinning from pinned-alloc objects\n");
 489         for (chunk = alc->chunk_list; chunk; chunk = chunk->block.next) {
 490                 int num_pinned;
 491                 void **pinned = sgen_find_optimized_pin_queue_area (chunk->start_data,
 492                                 (char*)chunk + chunk->num_pages * FREELIST_PAGESIZE, &num_pinned);
 493                 if (num_pinned)
 494                         mark_pinned_from_addresses (chunk, pinned, pinned + num_pinned, callback, callback_data);
 495         }
 496 }
 497
 498 #endif