mono/metadata/sgen-pinned-allocator.c

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