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 typedef struct _LargePinnedMemHeader LargePinnedMemHeader;
 115 struct _LargePinnedMemHeader {
 116         guint32 magic;
 117         size_t size;
 118         double data[0];
 119 };
 120
 121 static long long pinned_chunk_bytes_alloced = 0;
 122 static long long large_pinned_bytes_alloced = 0;
 123
 124 #ifdef HEAVY_STATISTICS
 125 static long long stat_pinned_alloc = 0;
 126 #endif
 127
 128 /*
 129  * Debug reporting.
 130  */
 131 static void
 132 report_pinned_chunk (SgenPinnedChunk *chunk, int seq) {
 133         void **p;
 134         int i, free_pages, num_free, free_mem;
 135         free_pages = 0;
 136         for (i = 0; i < chunk->num_pages; ++i) {
 137                 if (!chunk->page_sizes [i])
 138                         free_pages++;
 139         }
 140         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);
 141         free_mem = FREELIST_PAGESIZE * free_pages;
 142         for (i = 0; i < SGEN_PINNED_FREELIST_NUM_SLOTS; ++i) {
 143                 if (!chunk->free_list [i])
 144                         continue;
 145                 num_free = 0;
 146                 p = chunk->free_list [i];
 147                 while (p) {
 148                         num_free++;
 149                         p = *p;
 150                 }
 151                 printf ("\tfree list of size %d, %d items\n", freelist_sizes [i], num_free);
 152                 free_mem += freelist_sizes [i] * num_free;
 153         }
 154         printf ("\tfree memory in chunk: %d\n", free_mem);
 155 }
 156
 157 /*
 158  * Debug reporting.
 159  */
 160 void
 161 sgen_report_pinned_mem_usage (SgenPinnedAllocator *alc)
 162 {
 163         SgenPinnedChunk *chunk;
 164         int i = 0;
 165         for (chunk = alc->chunk_list; chunk; chunk = chunk->block.next)
 166                 report_pinned_chunk (chunk, i++);
 167 }
 168
 169 /*
 170  * Find the slot number in the freelist for memory chunks that
 171  * can contain @size objects.
 172  */
 173 static int
 174 slot_for_size (size_t size)
 175 {
 176         int slot;
 177         /* do a binary search or lookup table later. */
 178         for (slot = 0; slot < SGEN_PINNED_FREELIST_NUM_SLOTS; ++slot) {
 179                 if (freelist_sizes [slot] >= size)
 180                         return slot;
 181         }
 182         g_assert_not_reached ();
 183         return -1;
 184 }
 185
 186 /*
 187  * Build a free list for @size memory chunks from the memory area between
 188  * start_page and end_page.
 189  */
 190 static void
 191 build_freelist (SgenPinnedAllocator *alc, SgenPinnedChunk *chunk, int slot, int size, char *start_page, char *end_page)
 192 {
 193         void **p, **end;
 194         int count = 0;
 195         /*g_print ("building freelist for slot %d, size %d in %p\n", slot, size, chunk);*/
 196         p = (void**)start_page;
 197         end = (void**)(end_page - size);
 198         g_assert (!chunk->free_list [slot]);
 199         chunk->free_list [slot] = p;
 200         while ((char*)p + size <= (char*)end) {
 201                 count++;
 202                 *p = (void*)((char*)p + size);
 203                 p = *p;
 204         }
 205         *p = NULL;
 206         /*g_print ("%d items created, max: %d\n", count, (end_page - start_page) / size);*/
 207
 208         g_assert (!chunk->free_list_nexts [slot]);
 209         chunk->free_list_nexts [slot] = alc->free_lists [slot];
 210         alc->free_lists [slot] = chunk;
 211 }
 212
 213 static SgenPinnedChunk*
 214 alloc_pinned_chunk (SgenPinnedAllocator *alc)
 215 {
 216         SgenPinnedChunk *chunk;
 217         int offset;
 218         int size = SGEN_PINNED_CHUNK_SIZE;
 219
 220         chunk = sgen_alloc_os_memory_aligned (size, size, TRUE);
 221         chunk->block.role = MEMORY_ROLE_PINNED;
 222
 223         sgen_update_heap_boundaries ((mword)chunk, ((mword)chunk + size));
 224
 225         pinned_chunk_bytes_alloced += size;
 226
 227         /* setup the bookeeping fields */
 228         chunk->num_pages = size / FREELIST_PAGESIZE;
 229         offset = G_STRUCT_OFFSET (SgenPinnedChunk, data);
 230         chunk->page_sizes = (void*)((char*)chunk + offset);
 231         offset += sizeof (int) * chunk->num_pages;
 232         offset = SGEN_ALIGN_UP (offset);
 233         chunk->free_list = (void*)((char*)chunk + offset);
 234         offset += sizeof (void*) * SGEN_PINNED_FREELIST_NUM_SLOTS;
 235         offset = SGEN_ALIGN_UP (offset);
 236         chunk->start_data = (void*)((char*)chunk + offset);
 237
 238         /* allocate the first page to the freelist */
 239         chunk->page_sizes [0] = PINNED_FIRST_SLOT_SIZE;
 240         build_freelist (alc, chunk, slot_for_size (PINNED_FIRST_SLOT_SIZE), PINNED_FIRST_SLOT_SIZE,
 241                         chunk->start_data, ((char*)chunk + FREELIST_PAGESIZE));
 242         sgen_debug_printf (4, "Allocated pinned chunk %p, size: %d\n", chunk, size);
 243
 244         chunk->block.next = alc->chunk_list;
 245         alc->chunk_list = chunk;
 246
 247         chunk->allocator = alc;
 248
 249         return chunk;
 250 }
 251
 252 /* Must be called with an empty freelist for the given slot. */
 253 static gboolean
 254 populate_chunk_page (SgenPinnedAllocator *alc, SgenPinnedChunk *chunk, int slot)
 255 {
 256         int size = freelist_sizes [slot];
 257         int i;
 258         g_assert (!chunk->free_list [slot]);
 259         g_assert (!chunk->free_list_nexts [slot]);
 260         for (i = 0; i < chunk->num_pages; ++i) {
 261                 if (chunk->page_sizes [i])
 262                         continue;
 263                 chunk->page_sizes [i] = size;
 264                 build_freelist (alc, chunk, slot, size, (char*)chunk + FREELIST_PAGESIZE * i, (char*)chunk + FREELIST_PAGESIZE * (i + 1));
 265                 return TRUE;
 266         }
 267         return FALSE;
 268 }
 269
 270 static void*
 271 alloc_from_slot (SgenPinnedAllocator *alc, int slot)
 272 {
 273         SgenPinnedChunk *pchunk;
 274         size_t size = freelist_sizes [slot];
 275
 276         if (alc->delayed_free_lists [slot]) {
 277                 void **p;
 278                 do {
 279                         p = alc->delayed_free_lists [slot];
 280                 } while (SGEN_CAS_PTR (&alc->delayed_free_lists [slot], *p, p) != p);
 281                 memset (p, 0, size);
 282                 return p;
 283         }
 284
 285  restart:
 286         pchunk = alc->free_lists [slot];
 287         if (pchunk) {
 288                 void **p = pchunk->free_list [slot];
 289                 void *next;
 290
 291                 g_assert (p);
 292
 293                 next = *p;
 294                 pchunk->free_list [slot] = next;
 295
 296                 if (!next) {
 297                         alc->free_lists [slot] = pchunk->free_list_nexts [slot];
 298                         pchunk->free_list_nexts [slot] = NULL;
 299                 }
 300
 301                 memset (p, 0, size);
 302                 return p;
 303         }
 304
 305         for (pchunk = alc->chunk_list; pchunk; pchunk = pchunk->block.next) {
 306                 if (populate_chunk_page (alc, pchunk, slot))
 307                         goto restart;
 308         }
 309
 310         pchunk = alloc_pinned_chunk (alc);
 311         /* FIXME: handle OOM */
 312         if (pchunk->free_list [slot])
 313                 goto restart;
 314         if (!populate_chunk_page (alc, pchunk, slot))
 315                 g_assert_not_reached ();
 316         goto restart;
 317 }
 318
 319 /* used for the GC-internal data structures */
 320 void*
 321 sgen_alloc_pinned (SgenPinnedAllocator *alc, size_t size)
 322 {
 323         int slot;
 324         void *res = NULL;
 325
 326         HEAVY_STAT (++stat_pinned_alloc);
 327
 328         if (size > freelist_sizes [SGEN_PINNED_FREELIST_NUM_SLOTS - 1]) {
 329                 LargePinnedMemHeader *mh;
 330
 331                 size += sizeof (LargePinnedMemHeader);
 332                 mh = sgen_alloc_os_memory (size, TRUE);
 333                 mh->magic = LARGE_PINNED_MEM_HEADER_MAGIC;
 334                 mh->size = size;
 335                 /* FIXME: do a CAS here */
 336                 large_pinned_bytes_alloced += size;
 337                 return mh->data;
 338         }
 339
 340         slot = slot_for_size (size);
 341         g_assert (size <= freelist_sizes [slot]);
 342         res = alloc_from_slot (alc, slot);
 343
 344         return res;
 345 }
 346
 347 static void
 348 free_from_slot (SgenPinnedAllocator *alc, void *addr, int slot)
 349 {
 350         SgenPinnedChunk *pchunk = (SgenPinnedChunk*)SGEN_PINNED_CHUNK_FOR_PTR (addr);
 351         void **p = addr;
 352         void *next;
 353
 354         g_assert (addr >= (void*)pchunk && (char*)addr < (char*)pchunk + pchunk->num_pages * FREELIST_PAGESIZE);
 355
 356         next = pchunk->free_list [slot];
 357         *p = next;
 358         pchunk->free_list [slot] = p;
 359
 360         if (!next) {
 361                 g_assert (!pchunk->free_list_nexts [slot]);
 362                 pchunk->free_list_nexts [slot] = alc->free_lists [slot];
 363                 alc->free_lists [slot] = pchunk;
 364         }
 365 }
 366
 367 void
 368 sgen_free_pinned (SgenPinnedAllocator *alc, void *addr, size_t size)
 369 {
 370         LargePinnedMemHeader *mh;
 371
 372         if (!addr)
 373                 return;
 374
 375         if (size <= freelist_sizes [SGEN_PINNED_FREELIST_NUM_SLOTS - 1]) {
 376                 int slot = slot_for_size (size);
 377                 free_from_slot (alc, addr, slot);
 378                 return;
 379         }
 380
 381         mh = (LargePinnedMemHeader*)((char*)addr - G_STRUCT_OFFSET (LargePinnedMemHeader, data));
 382         g_assert (mh->magic == LARGE_PINNED_MEM_HEADER_MAGIC);
 383         g_assert (mh->size == size + sizeof (LargePinnedMemHeader));
 384         /* FIXME: do a CAS */
 385         large_pinned_bytes_alloced -= mh->size;
 386         sgen_free_os_memory (mh, mh->size);
 387 }
 388
 389 void
 390 sgen_init_pinned_allocator (void)
 391 {
 392         g_assert (SGEN_PINNED_FREELIST_NUM_SLOTS == sizeof (freelist_sizes) / sizeof (freelist_sizes [0]));
 393
 394 #ifdef HEAVY_STATISTICS
 395         mono_counters_register ("Pinned allocs", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_pinned_alloc);
 396 #endif
 397 }
 398
 399 void
 400 sgen_pinned_scan_objects (SgenPinnedAllocator *alc, IterateObjectCallbackFunc callback, void *callback_data)
 401 {
 402         SgenPinnedChunk *chunk;
 403         int i, obj_size;
 404         char *p, *endp;
 405         void **ptr;
 406         void *end_chunk;
 407         for (chunk = alc->chunk_list; chunk; chunk = chunk->block.next) {
 408                 end_chunk = (char*)chunk + chunk->num_pages * FREELIST_PAGESIZE;
 409                 sgen_debug_printf (6, "Scanning pinned chunk %p (range: %p-%p)\n", chunk, chunk->start_data, end_chunk);
 410                 for (i = 0; i < chunk->num_pages; ++i) {
 411                         obj_size = chunk->page_sizes [i];
 412                         if (!obj_size)
 413                                 continue;
 414                         p = i? (char*)chunk + i * FREELIST_PAGESIZE: chunk->start_data;
 415                         endp = i? p + FREELIST_PAGESIZE: (char*)chunk + FREELIST_PAGESIZE;
 416                         sgen_debug_printf (6, "Page %d (size: %d, range: %p-%p)\n", i, obj_size, p, endp);
 417                         while (p + obj_size <= endp) {
 418                                 ptr = (void**)p;
 419                                 /* if the first word (the vtable) is outside the chunk we have an object */
 420                                 if (*ptr && (*ptr < (void*)chunk || *ptr >= end_chunk))
 421                                         callback ((char*)ptr, obj_size, callback_data);
 422                                 p += obj_size;
 423                         }
 424                 }
 425         }
 426 }
 427
 428 void
 429 sgen_pinned_update_heap_boundaries (SgenPinnedAllocator *alc)
 430 {
 431         SgenPinnedChunk *chunk;
 432         for (chunk = alc->chunk_list; chunk; chunk = chunk->block.next) {
 433                 char *end_chunk = (char*)chunk + chunk->num_pages * FREELIST_PAGESIZE;
 434                 sgen_update_heap_boundaries ((mword)chunk, (mword)end_chunk);
 435         }
 436 }
 437
 438 /*
 439  * the array of pointers from @start to @end contains conservative
 440  * pointers to objects inside @chunk: mark each referenced object
 441  * with the PIN bit.
 442  */
 443 static void
 444 mark_pinned_from_addresses (SgenPinnedChunk *chunk, void **start, void **end, IterateObjectCallbackFunc callback, void *callback_data)
 445 {
 446         for (; start < end; start++) {
 447                 char *addr = *start;
 448                 int offset = (char*)addr - (char*)chunk;
 449                 int page = offset / FREELIST_PAGESIZE;
 450                 int obj_offset = page == 0? offset - ((char*)chunk->start_data - (char*)chunk): offset % FREELIST_PAGESIZE;
 451                 int slot_size = chunk->page_sizes [page];
 452                 void **ptr;
 453                 /* the page is not allocated */
 454                 if (!slot_size)
 455                         continue;
 456                 /* would be faster if we restrict the sizes to power of two,
 457                  * but that's a waste of memory: need to measure. it could reduce
 458                  * fragmentation since there are less pages needed, if for example
 459                  * someone interns strings of each size we end up with one page per
 460                  * interned string (still this is just ~40 KB): with more fine-grained sizes
 461                  * this increases the number of used pages.
 462                  */
 463                 if (page == 0) {
 464                         obj_offset /= slot_size;
 465                         obj_offset *= slot_size;
 466                         addr = (char*)chunk->start_data + obj_offset;
 467                 } else {
 468                         obj_offset /= slot_size;
 469                         obj_offset *= slot_size;
 470                         addr = (char*)chunk + page * FREELIST_PAGESIZE + obj_offset;
 471                 }
 472                 ptr = (void**)addr;
 473                 /* if the vtable is inside the chunk it's on the freelist, so skip */
 474                 /* FIXME: is it possible that we're pinning objects more than once here? */
 475                 if (*ptr && (*ptr < (void*)chunk->start_data || *ptr > (void*)((char*)chunk + chunk->num_pages * FREELIST_PAGESIZE)))
 476                         callback (addr, slot_size, callback_data);
 477         }
 478 }
 479
 480 void
 481 sgen_pinned_scan_pinned_objects (SgenPinnedAllocator *alc, IterateObjectCallbackFunc callback, void *callback_data)
 482 {
 483         SgenPinnedChunk *chunk;
 484
 485         /* look for pinned addresses for pinned-alloc objects */
 486         sgen_debug_printf (6, "Pinning from pinned-alloc objects\n");
 487         for (chunk = alc->chunk_list; chunk; chunk = chunk->block.next) {
 488                 int num_pinned;
 489                 void **pinned = sgen_find_optimized_pin_queue_area (chunk->start_data,
 490                                 (char*)chunk + chunk->num_pages * FREELIST_PAGESIZE, &num_pinned);
 491                 if (num_pinned)
 492                         mark_pinned_from_addresses (chunk, pinned, pinned + num_pinned, callback, callback_data);
 493         }
 494 }
 495
 496 #endif