mono/metadata/sgen-internal.c

   1 /*
   2  * sgen-gc.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 #ifdef HAVE_SGEN_GC
  49
  50 #include "utils/mono-counters.h"
  51 #include "metadata/sgen-gc.h"
  52
  53 /* Pinned objects are allocated in the LOS space if bigger than half a page
  54  * or from freelists otherwise. We assume that pinned objects are relatively few
  55  * and they have a slow dying speed (like interned strings, thread objects).
  56  * As such they will be collected only at major collections.
  57  * free lists are not global: when we need memory we allocate a PinnedChunk.
  58  * Each pinned chunk is made of several pages, the first of wich is used
  59  * internally for bookeeping (here think of a page as 4KB). The bookeeping
  60  * includes the freelists vectors and info about the object size of each page
  61  * in the pinned chunk. So, when needed, a free page is found in a pinned chunk,
  62  * a size is assigned to it, the page is divided in the proper chunks and each
  63  * chunk is added to the freelist. To not waste space, the remaining space in the
  64  * first page is used as objects of size 16 or 32 (need to measure which are more
  65  * common).
  66  * We use this same structure to allocate memory used internally by the GC, so
  67  * we never use malloc/free if we need to alloc during collection: the world is stopped
  68  * and malloc/free will deadlock.
  69  * When we want to iterate over pinned objects, we just scan a page at a time
  70  * linearly according to the size of objects in the page: the next pointer used to link
  71  * the items in the freelist uses the same word as the vtable. Since we keep freelists
  72  * for each pinned chunk, if the word points outside the pinned chunk it means
  73  * it is an object.
  74  * We could avoid this expensive scanning in creative ways. We could have a policy
  75  * of putting in the pinned space only objects we know about that have no struct fields
  76  * with references and we can easily use a even expensive write barrier for them,
  77  * since pointer writes on such objects should be rare.
  78  * The best compromise is to just alloc interned strings and System.MonoType in them.
  79  * It would be nice to allocate MonoThread in it, too: must check that we properly
  80  * use write barriers so we don't have to do any expensive scanning of the whole pinned
  81  * chunk list during minor collections. We can avoid it now because we alloc in it only
  82  * reference-free objects.
  83  */
  84 struct _SgenPinnedChunk {
  85         SgenBlock block;
  86         int num_pages;
  87         SgenInternalAllocator *allocator;
  88         int *page_sizes; /* a 0 means the page is still unused */
  89         void **free_list;
  90         SgenPinnedChunk *free_list_nexts [SGEN_INTERNAL_FREELIST_NUM_SLOTS];
  91         void *start_data;
  92         void *data [1]; /* page sizes and free lists are stored here */
  93 };
  94
  95 #define PINNED_FIRST_SLOT_SIZE (sizeof (gpointer) * 4)
  96 #define MAX_FREELIST_SIZE 8192
  97
  98 /* This is a fixed value used for pinned chunks, not the system pagesize */
  99 #define FREELIST_PAGESIZE (16*1024)
 100
 101 /* keep each size a multiple of ALLOC_ALIGN */
 102 /* on 64 bit systems 8 is likely completely unused. */
 103 static const int freelist_sizes [] = {
 104            8,   16,   24,   32,   40,   48,   64,   80,
 105           96,  128,  160,  192,  224,  256,  320,  384,
 106          448,  512,  584,  680,  816, 1024, 1360, 2048,
 107         2336, 2728, 3272, 4096, 5456, 8192 };
 108
 109 /*
 110  * Slot indexes for the fixed INTERNAL_MEM_XXX types.  -1 if that type
 111  * is dynamic.
 112  */
 113 static int fixed_type_freelist_slots [INTERNAL_MEM_MAX];
 114
 115 static SgenInternalAllocator unmanaged_allocator;
 116
 117 #define LARGE_INTERNAL_MEM_HEADER_MAGIC 0x7d289f3a
 118
 119 typedef struct _LargeInternalMemHeader LargeInternalMemHeader;
 120 struct _LargeInternalMemHeader {
 121         guint32 magic;
 122         size_t size;
 123         double data[0];
 124 };
 125
 126 static long long pinned_chunk_bytes_alloced = 0;
 127 static long long large_internal_bytes_alloced = 0;
 128
 129 #ifdef HEAVY_STATISTICS
 130 static long long stat_internal_alloc = 0;
 131 #endif
 132
 133 /*
 134  * Debug reporting.
 135  */
 136 static void
 137 report_pinned_chunk (SgenPinnedChunk *chunk, int seq) {
 138         void **p;
 139         int i, free_pages, num_free, free_mem;
 140         free_pages = 0;
 141         for (i = 0; i < chunk->num_pages; ++i) {
 142                 if (!chunk->page_sizes [i])
 143                         free_pages++;
 144         }
 145         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);
 146         free_mem = FREELIST_PAGESIZE * free_pages;
 147         for (i = 0; i < SGEN_INTERNAL_FREELIST_NUM_SLOTS; ++i) {
 148                 if (!chunk->free_list [i])
 149                         continue;
 150                 num_free = 0;
 151                 p = chunk->free_list [i];
 152                 while (p) {
 153                         num_free++;
 154                         p = *p;
 155                 }
 156                 printf ("\tfree list of size %d, %d items\n", freelist_sizes [i], num_free);
 157                 free_mem += freelist_sizes [i] * num_free;
 158         }
 159         printf ("\tfree memory in chunk: %d\n", free_mem);
 160 }
 161
 162 /*
 163  * Debug reporting.
 164  */
 165 void
 166 mono_sgen_report_internal_mem_usage_full (SgenInternalAllocator *alc)
 167 {
 168         SgenPinnedChunk *chunk;
 169         int i = 0;
 170         for (chunk = alc->chunk_list; chunk; chunk = chunk->block.next)
 171                 report_pinned_chunk (chunk, i++);
 172 }
 173
 174 void
 175 mono_sgen_report_internal_mem_usage (void)
 176 {
 177         mono_sgen_report_internal_mem_usage_full (&unmanaged_allocator);
 178 }
 179
 180 /*
 181  * Find the slot number in the freelist for memory chunks that
 182  * can contain @size objects.
 183  */
 184 static int
 185 slot_for_size (size_t size)
 186 {
 187         int slot;
 188         /* do a binary search or lookup table later. */
 189         for (slot = 0; slot < SGEN_INTERNAL_FREELIST_NUM_SLOTS; ++slot) {
 190                 if (freelist_sizes [slot] >= size)
 191                         return slot;
 192         }
 193         g_assert_not_reached ();
 194         return -1;
 195 }
 196
 197 void
 198 mono_sgen_register_fixed_internal_mem_type (int type, size_t size)
 199 {
 200         int slot;
 201
 202         g_assert (type >= 0 && type < INTERNAL_MEM_MAX);
 203         g_assert (fixed_type_freelist_slots [type] == -1);
 204
 205         slot = slot_for_size (size);
 206         g_assert (slot >= 0);
 207
 208         fixed_type_freelist_slots [type] = slot;
 209 }
 210
 211 /*
 212  * Build a free list for @size memory chunks from the memory area between
 213  * start_page and end_page.
 214  */
 215 static void
 216 build_freelist (SgenInternalAllocator *alc, SgenPinnedChunk *chunk, int slot, int size, char *start_page, char *end_page)
 217 {
 218         void **p, **end;
 219         int count = 0;
 220         /*g_print ("building freelist for slot %d, size %d in %p\n", slot, size, chunk);*/
 221         p = (void**)start_page;
 222         end = (void**)(end_page - size);
 223         g_assert (!chunk->free_list [slot]);
 224         chunk->free_list [slot] = p;
 225         while ((char*)p + size <= (char*)end) {
 226                 count++;
 227                 *p = (void*)((char*)p + size);
 228                 p = *p;
 229         }
 230         *p = NULL;
 231         /*g_print ("%d items created, max: %d\n", count, (end_page - start_page) / size);*/
 232
 233         g_assert (!chunk->free_list_nexts [slot]);
 234         chunk->free_list_nexts [slot] = alc->free_lists [slot];
 235         alc->free_lists [slot] = chunk;
 236 }
 237
 238 static SgenPinnedChunk*
 239 alloc_pinned_chunk (SgenInternalAllocator *alc, gboolean managed)
 240 {
 241         SgenPinnedChunk *chunk;
 242         int offset;
 243         int size = SGEN_PINNED_CHUNK_SIZE;
 244
 245         chunk = mono_sgen_alloc_os_memory_aligned (size, size, TRUE);
 246         chunk->block.role = managed ? MEMORY_ROLE_PINNED : MEMORY_ROLE_INTERNAL;
 247
 248         if (managed)
 249                 mono_sgen_update_heap_boundaries ((mword)chunk, ((mword)chunk + size));
 250
 251         pinned_chunk_bytes_alloced += size;
 252
 253         /* setup the bookeeping fields */
 254         chunk->num_pages = size / FREELIST_PAGESIZE;
 255         offset = G_STRUCT_OFFSET (SgenPinnedChunk, data);
 256         chunk->page_sizes = (void*)((char*)chunk + offset);
 257         offset += sizeof (int) * chunk->num_pages;
 258         offset = SGEN_ALIGN_UP (offset);
 259         chunk->free_list = (void*)((char*)chunk + offset);
 260         offset += sizeof (void*) * SGEN_INTERNAL_FREELIST_NUM_SLOTS;
 261         offset = SGEN_ALIGN_UP (offset);
 262         chunk->start_data = (void*)((char*)chunk + offset);
 263
 264         /* allocate the first page to the freelist */
 265         chunk->page_sizes [0] = PINNED_FIRST_SLOT_SIZE;
 266         build_freelist (alc, chunk, slot_for_size (PINNED_FIRST_SLOT_SIZE), PINNED_FIRST_SLOT_SIZE,
 267                         chunk->start_data, ((char*)chunk + FREELIST_PAGESIZE));
 268         mono_sgen_debug_printf (4, "Allocated pinned chunk %p, size: %d\n", chunk, size);
 269
 270         chunk->block.next = alc->chunk_list;
 271         alc->chunk_list = chunk;
 272
 273         chunk->allocator = alc;
 274
 275         return chunk;
 276 }
 277
 278 /* Must be called with an empty freelist for the given slot. */
 279 static gboolean
 280 populate_chunk_page (SgenInternalAllocator *alc, SgenPinnedChunk *chunk, int slot)
 281 {
 282         int size = freelist_sizes [slot];
 283         int i;
 284         g_assert (!chunk->free_list [slot]);
 285         g_assert (!chunk->free_list_nexts [slot]);
 286         for (i = 0; i < chunk->num_pages; ++i) {
 287                 if (chunk->page_sizes [i])
 288                         continue;
 289                 chunk->page_sizes [i] = size;
 290                 build_freelist (alc, chunk, slot, size, (char*)chunk + FREELIST_PAGESIZE * i, (char*)chunk + FREELIST_PAGESIZE * (i + 1));
 291                 return TRUE;
 292         }
 293         return FALSE;
 294 }
 295
 296 static void*
 297 alloc_from_slot (SgenInternalAllocator *alc, int slot, int type)
 298 {
 299         SgenPinnedChunk *pchunk;
 300         size_t size = freelist_sizes [slot];
 301
 302         alc->small_internal_mem_bytes [type] += size;
 303
 304         if (alc->delayed_free_lists [slot]) {
 305                 void **p;
 306                 do {
 307                         p = alc->delayed_free_lists [slot];
 308                 } while (SGEN_CAS_PTR (&alc->delayed_free_lists [slot], *p, p) != p);
 309                 memset (p, 0, size);
 310                 return p;
 311         }
 312
 313  restart:
 314         pchunk = alc->free_lists [slot];
 315         if (pchunk) {
 316                 void **p = pchunk->free_list [slot];
 317                 void *next;
 318
 319                 g_assert (p);
 320
 321                 next = *p;
 322                 pchunk->free_list [slot] = next;
 323
 324                 if (!next) {
 325                         alc->free_lists [slot] = pchunk->free_list_nexts [slot];
 326                         pchunk->free_list_nexts [slot] = NULL;
 327                 }
 328
 329                 memset (p, 0, size);
 330                 return p;
 331         }
 332
 333         for (pchunk = alc->chunk_list; pchunk; pchunk = pchunk->block.next) {
 334                 if (populate_chunk_page (alc, pchunk, slot))
 335                         goto restart;
 336         }
 337
 338         pchunk = alloc_pinned_chunk (alc, type == INTERNAL_MEM_MANAGED);
 339         /* FIXME: handle OOM */
 340         if (pchunk->free_list [slot])
 341                 goto restart;
 342         if (!populate_chunk_page (alc, pchunk, slot))
 343                 g_assert_not_reached ();
 344         goto restart;
 345 }
 346
 347 /* used for the GC-internal data structures */
 348 void*
 349 mono_sgen_alloc_internal_full (SgenInternalAllocator *alc, size_t size, int type)
 350 {
 351         int slot;
 352         void *res = NULL;
 353
 354         g_assert (fixed_type_freelist_slots [type] == -1);
 355
 356         HEAVY_STAT (++stat_internal_alloc);
 357
 358         if (size > freelist_sizes [SGEN_INTERNAL_FREELIST_NUM_SLOTS - 1]) {
 359                 LargeInternalMemHeader *mh;
 360
 361                 size += sizeof (LargeInternalMemHeader);
 362                 mh = mono_sgen_alloc_os_memory (size, TRUE);
 363                 mh->magic = LARGE_INTERNAL_MEM_HEADER_MAGIC;
 364                 mh->size = size;
 365                 /* FIXME: do a CAS here */
 366                 large_internal_bytes_alloced += size;
 367                 return mh->data;
 368         }
 369
 370         slot = slot_for_size (size);
 371         g_assert (size <= freelist_sizes [slot]);
 372         res = alloc_from_slot (alc, slot, type);
 373
 374         return res;
 375 }
 376
 377 void*
 378 mono_sgen_alloc_internal_fixed (SgenInternalAllocator *allocator, int type)
 379 {
 380         int slot = fixed_type_freelist_slots [type];
 381         g_assert (slot >= 0);
 382         return alloc_from_slot (allocator, slot, type);
 383 }
 384
 385 void*
 386 mono_sgen_alloc_internal (int type)
 387 {
 388         return mono_sgen_alloc_internal_fixed (&unmanaged_allocator, type);
 389 }
 390
 391 void*
 392 mono_sgen_alloc_internal_dynamic (size_t size, int type)
 393 {
 394         return mono_sgen_alloc_internal_full (&unmanaged_allocator, size, type);
 395 }
 396
 397 static void
 398 free_from_slot (SgenInternalAllocator *alc, void *addr, int slot, int type)
 399 {
 400         SgenPinnedChunk *pchunk = (SgenPinnedChunk*)SGEN_PINNED_CHUNK_FOR_PTR (addr);
 401         void **p = addr;
 402         void *next;
 403
 404         g_assert (addr >= (void*)pchunk && (char*)addr < (char*)pchunk + pchunk->num_pages * FREELIST_PAGESIZE);
 405         if (type == INTERNAL_MEM_MANAGED)
 406                 g_assert (pchunk->block.role == MEMORY_ROLE_PINNED);
 407         else
 408                 g_assert (pchunk->block.role == MEMORY_ROLE_INTERNAL);
 409
 410         next = pchunk->free_list [slot];
 411         *p = next;
 412         pchunk->free_list [slot] = p;
 413
 414         if (!next) {
 415                 g_assert (!pchunk->free_list_nexts [slot]);
 416                 pchunk->free_list_nexts [slot] = alc->free_lists [slot];
 417                 alc->free_lists [slot] = pchunk;
 418         }
 419
 420         alc->small_internal_mem_bytes [type] -= freelist_sizes [slot];
 421 }
 422
 423 void
 424 mono_sgen_free_internal_full (SgenInternalAllocator *alc, void *addr, size_t size, int type)
 425 {
 426         LargeInternalMemHeader *mh;
 427
 428         g_assert (fixed_type_freelist_slots [type] == -1);
 429
 430         if (!addr)
 431                 return;
 432
 433         if (size <= freelist_sizes [SGEN_INTERNAL_FREELIST_NUM_SLOTS - 1]) {
 434                 int slot = slot_for_size (size);
 435                 free_from_slot (alc, addr, slot, type);
 436                 return;
 437         }
 438
 439         mh = (LargeInternalMemHeader*)((char*)addr - G_STRUCT_OFFSET (LargeInternalMemHeader, data));
 440         g_assert (mh->magic == LARGE_INTERNAL_MEM_HEADER_MAGIC);
 441         g_assert (mh->size == size + sizeof (LargeInternalMemHeader));
 442         /* FIXME: do a CAS */
 443         large_internal_bytes_alloced -= mh->size;
 444         mono_sgen_free_os_memory (mh, mh->size);
 445 }
 446
 447 void
 448 mono_sgen_free_internal_fixed (SgenInternalAllocator *allocator, void *addr, int type)
 449 {
 450         int slot = fixed_type_freelist_slots [type];
 451         g_assert (slot >= 0);
 452
 453         free_from_slot (allocator, addr, slot, type);
 454 }
 455
 456 void
 457 mono_sgen_free_internal (void *addr, int type)
 458 {
 459         mono_sgen_free_internal_fixed (&unmanaged_allocator, addr, type);
 460 }
 461
 462 void
 463 mono_sgen_free_internal_dynamic (void *addr, size_t size, int type)
 464 {
 465         mono_sgen_free_internal_full (&unmanaged_allocator, addr, size, type);
 466 }
 467
 468 void
 469 mono_sgen_free_internal_delayed (void *addr, int type, SgenInternalAllocator *thread_allocator)
 470 {
 471         SgenPinnedChunk *pchunk = (SgenPinnedChunk*)SGEN_PINNED_CHUNK_FOR_PTR (addr);
 472         SgenInternalAllocator *alc = pchunk->allocator;
 473         int slot;
 474         void *next;
 475
 476         if (alc == thread_allocator) {
 477                 mono_sgen_free_internal_fixed (alc, addr, type);
 478                 return;
 479         }
 480
 481         slot = fixed_type_freelist_slots [type];
 482         g_assert (slot >= 0);
 483
 484         do {
 485                 next = alc->delayed_free_lists [slot];
 486                 *(void**)addr = next;
 487         } while (SGEN_CAS_PTR (&alc->delayed_free_lists [slot], addr, next) != next);
 488 }
 489
 490 void
 491 mono_sgen_dump_internal_mem_usage (FILE *heap_dump_file)
 492 {
 493         static char const *internal_mem_names [] = { "managed", "pin-queue", "fragment", "section", "scan-starts",
 494                                                      "fin-table", "finalize-entry", "dislink-table",
 495                                                      "dislink", "roots-table", "root-record", "statistics",
 496                                                      "remset", "gray-queue", "store-remset", "marksweep-tables",
 497                                                      "marksweep-block-info", "ephemeron-link" };
 498
 499         int i;
 500
 501         fprintf (heap_dump_file, "<other-mem-usage type=\"large-internal\" size=\"%lld\"/>\n", large_internal_bytes_alloced);
 502         fprintf (heap_dump_file, "<other-mem-usage type=\"pinned-chunks\" size=\"%lld\"/>\n", pinned_chunk_bytes_alloced);
 503         for (i = 0; i < INTERNAL_MEM_MAX; ++i) {
 504                 fprintf (heap_dump_file, "<other-mem-usage type=\"%s\" size=\"%ld\"/>\n",
 505                                 internal_mem_names [i], unmanaged_allocator.small_internal_mem_bytes [i]);
 506         }
 507 }
 508
 509 void
 510 mono_sgen_init_internal_allocator (void)
 511 {
 512         int i;
 513
 514         g_assert (SGEN_INTERNAL_FREELIST_NUM_SLOTS == sizeof (freelist_sizes) / sizeof (freelist_sizes [0]));
 515
 516         for (i = 0; i < INTERNAL_MEM_MAX; ++i)
 517                 fixed_type_freelist_slots [i] = -1;
 518
 519 #ifdef HEAVY_STATISTICS
 520         mono_counters_register ("Internal allocs", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_internal_alloc);
 521 #endif
 522 }
 523
 524 SgenInternalAllocator*
 525 mono_sgen_get_unmanaged_allocator (void)
 526 {
 527         return &unmanaged_allocator;
 528 }
 529
 530 void
 531 mono_sgen_internal_scan_objects (SgenInternalAllocator *alc, IterateObjectCallbackFunc callback, void *callback_data)
 532 {
 533         SgenPinnedChunk *chunk;
 534         int i, obj_size;
 535         char *p, *endp;
 536         void **ptr;
 537         void *end_chunk;
 538         for (chunk = alc->chunk_list; chunk; chunk = chunk->block.next) {
 539                 end_chunk = (char*)chunk + chunk->num_pages * FREELIST_PAGESIZE;
 540                 mono_sgen_debug_printf (6, "Scanning pinned chunk %p (range: %p-%p)\n", chunk, chunk->start_data, end_chunk);
 541                 for (i = 0; i < chunk->num_pages; ++i) {
 542                         obj_size = chunk->page_sizes [i];
 543                         if (!obj_size)
 544                                 continue;
 545                         p = i? (char*)chunk + i * FREELIST_PAGESIZE: chunk->start_data;
 546                         endp = i? p + FREELIST_PAGESIZE: (char*)chunk + FREELIST_PAGESIZE;
 547                         mono_sgen_debug_printf (6, "Page %d (size: %d, range: %p-%p)\n", i, obj_size, p, endp);
 548                         while (p + obj_size <= endp) {
 549                                 ptr = (void**)p;
 550                                 /* if the first word (the vtable) is outside the chunk we have an object */
 551                                 if (*ptr && (*ptr < (void*)chunk || *ptr >= end_chunk))
 552                                         callback ((char*)ptr, obj_size, callback_data);
 553                                 p += obj_size;
 554                         }
 555                 }
 556         }
 557 }
 558
 559 void
 560 mono_sgen_internal_update_heap_boundaries (SgenInternalAllocator *alc)
 561 {
 562         SgenPinnedChunk *chunk;
 563         for (chunk = alc->chunk_list; chunk; chunk = chunk->block.next) {
 564                 char *end_chunk = (char*)chunk + chunk->num_pages * FREELIST_PAGESIZE;
 565                 mono_sgen_update_heap_boundaries ((mword)chunk, (mword)end_chunk);
 566         }
 567 }
 568
 569 /*
 570  * the array of pointers from @start to @end contains conservative
 571  * pointers to objects inside @chunk: mark each referenced object
 572  * with the PIN bit.
 573  */
 574 static void
 575 mark_pinned_from_addresses (SgenPinnedChunk *chunk, void **start, void **end, IterateObjectCallbackFunc callback, void *callback_data)
 576 {
 577         for (; start < end; start++) {
 578                 char *addr = *start;
 579                 int offset = (char*)addr - (char*)chunk;
 580                 int page = offset / FREELIST_PAGESIZE;
 581                 int obj_offset = page == 0? offset - ((char*)chunk->start_data - (char*)chunk): offset % FREELIST_PAGESIZE;
 582                 int slot_size = chunk->page_sizes [page];
 583                 void **ptr;
 584                 /* the page is not allocated */
 585                 if (!slot_size)
 586                         continue;
 587                 /* would be faster if we restrict the sizes to power of two,
 588                  * but that's a waste of memory: need to measure. it could reduce
 589                  * fragmentation since there are less pages needed, if for example
 590                  * someone interns strings of each size we end up with one page per
 591                  * interned string (still this is just ~40 KB): with more fine-grained sizes
 592                  * this increases the number of used pages.
 593                  */
 594                 if (page == 0) {
 595                         obj_offset /= slot_size;
 596                         obj_offset *= slot_size;
 597                         addr = (char*)chunk->start_data + obj_offset;
 598                 } else {
 599                         obj_offset /= slot_size;
 600                         obj_offset *= slot_size;
 601                         addr = (char*)chunk + page * FREELIST_PAGESIZE + obj_offset;
 602                 }
 603                 ptr = (void**)addr;
 604                 /* if the vtable is inside the chunk it's on the freelist, so skip */
 605                 /* FIXME: is it possible that we're pinning objects more than once here? */
 606                 if (*ptr && (*ptr < (void*)chunk->start_data || *ptr > (void*)((char*)chunk + chunk->num_pages * FREELIST_PAGESIZE)))
 607                         callback (addr, slot_size, callback_data);
 608         }
 609 }
 610
 611 void
 612 mono_sgen_internal_scan_pinned_objects (SgenInternalAllocator *alc, IterateObjectCallbackFunc callback, void *callback_data)
 613 {
 614         SgenPinnedChunk *chunk;
 615
 616         /* look for pinned addresses for pinned-alloc objects */
 617         mono_sgen_debug_printf (6, "Pinning from pinned-alloc objects\n");
 618         for (chunk = alc->chunk_list; chunk; chunk = chunk->block.next) {
 619                 int num_pinned;
 620                 void **pinned = mono_sgen_find_optimized_pin_queue_area (chunk->start_data,
 621                                 (char*)chunk + chunk->num_pages * FREELIST_PAGESIZE, &num_pinned);
 622                 if (num_pinned)
 623                         mark_pinned_from_addresses (chunk, pinned, pinned + num_pinned, callback, callback_data);
 624         }
 625 }
 626
 627 #endif