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