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 #ifdef SGEN_DEBUG_INTERNAL_ALLOC
 134 extern pthread_t main_gc_thread;
 135 #endif
 136
 137 /*
 138  * Debug reporting.
 139  */
 140 static void
 141 report_pinned_chunk (SgenPinnedChunk *chunk, int seq) {
 142         void **p;
 143         int i, free_pages, num_free, free_mem;
 144         free_pages = 0;
 145         for (i = 0; i < chunk->num_pages; ++i) {
 146                 if (!chunk->page_sizes [i])
 147                         free_pages++;
 148         }
 149         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);
 150         free_mem = FREELIST_PAGESIZE * free_pages;
 151         for (i = 0; i < SGEN_INTERNAL_FREELIST_NUM_SLOTS; ++i) {
 152                 if (!chunk->free_list [i])
 153                         continue;
 154                 num_free = 0;
 155                 p = chunk->free_list [i];
 156                 while (p) {
 157                         num_free++;
 158                         p = *p;
 159                 }
 160                 printf ("\tfree list of size %d, %d items\n", freelist_sizes [i], num_free);
 161                 free_mem += freelist_sizes [i] * num_free;
 162         }
 163         printf ("\tfree memory in chunk: %d\n", free_mem);
 164 }
 165
 166 /*
 167  * Debug reporting.
 168  */
 169 void
 170 mono_sgen_report_internal_mem_usage_full (SgenInternalAllocator *alc)
 171 {
 172         SgenPinnedChunk *chunk;
 173         int i = 0;
 174         for (chunk = alc->chunk_list; chunk; chunk = chunk->block.next)
 175                 report_pinned_chunk (chunk, i++);
 176 }
 177
 178 void
 179 mono_sgen_report_internal_mem_usage (void)
 180 {
 181         mono_sgen_report_internal_mem_usage_full (&unmanaged_allocator);
 182 }
 183
 184 /*
 185  * Find the slot number in the freelist for memory chunks that
 186  * can contain @size objects.
 187  */
 188 static int
 189 slot_for_size (size_t size)
 190 {
 191         int slot;
 192         /* do a binary search or lookup table later. */
 193         for (slot = 0; slot < SGEN_INTERNAL_FREELIST_NUM_SLOTS; ++slot) {
 194                 if (freelist_sizes [slot] >= size)
 195                         return slot;
 196         }
 197         g_assert_not_reached ();
 198         return -1;
 199 }
 200
 201 void
 202 mono_sgen_register_fixed_internal_mem_type (int type, size_t size)
 203 {
 204         int slot;
 205
 206         g_assert (type >= 0 && type < INTERNAL_MEM_MAX);
 207         g_assert (fixed_type_freelist_slots [type] == -1);
 208
 209         slot = slot_for_size (size);
 210         g_assert (slot >= 0);
 211
 212         fixed_type_freelist_slots [type] = slot;
 213 }
 214
 215 /*
 216  * Build a free list for @size memory chunks from the memory area between
 217  * start_page and end_page.
 218  */
 219 static void
 220 build_freelist (SgenInternalAllocator *alc, SgenPinnedChunk *chunk, int slot, int size, char *start_page, char *end_page)
 221 {
 222         void **p, **end;
 223         int count = 0;
 224         /*g_print ("building freelist for slot %d, size %d in %p\n", slot, size, chunk);*/
 225         p = (void**)start_page;
 226         end = (void**)(end_page - size);
 227         g_assert (!chunk->free_list [slot]);
 228         chunk->free_list [slot] = p;
 229         while ((char*)p + size <= (char*)end) {
 230                 count++;
 231                 *p = (void*)((char*)p + size);
 232                 p = *p;
 233         }
 234         *p = NULL;
 235         /*g_print ("%d items created, max: %d\n", count, (end_page - start_page) / size);*/
 236
 237         g_assert (!chunk->free_list_nexts [slot]);
 238         chunk->free_list_nexts [slot] = alc->free_lists [slot];
 239         alc->free_lists [slot] = chunk;
 240 }
 241
 242 static SgenPinnedChunk*
 243 alloc_pinned_chunk (SgenInternalAllocator *alc, gboolean managed)
 244 {
 245         SgenPinnedChunk *chunk;
 246         int offset;
 247         int size = SGEN_PINNED_CHUNK_SIZE;
 248
 249         chunk = mono_sgen_alloc_os_memory_aligned (size, size, TRUE);
 250         chunk->block.role = managed ? MEMORY_ROLE_PINNED : MEMORY_ROLE_INTERNAL;
 251
 252         if (managed)
 253                 mono_sgen_update_heap_boundaries ((mword)chunk, ((mword)chunk + size));
 254
 255         pinned_chunk_bytes_alloced += size;
 256
 257         /* setup the bookeeping fields */
 258         chunk->num_pages = size / FREELIST_PAGESIZE;
 259         offset = G_STRUCT_OFFSET (SgenPinnedChunk, data);
 260         chunk->page_sizes = (void*)((char*)chunk + offset);
 261         offset += sizeof (int) * chunk->num_pages;
 262         offset = SGEN_ALIGN_UP (offset);
 263         chunk->free_list = (void*)((char*)chunk + offset);
 264         offset += sizeof (void*) * SGEN_INTERNAL_FREELIST_NUM_SLOTS;
 265         offset = SGEN_ALIGN_UP (offset);
 266         chunk->start_data = (void*)((char*)chunk + offset);
 267
 268         /* allocate the first page to the freelist */
 269         chunk->page_sizes [0] = PINNED_FIRST_SLOT_SIZE;
 270         build_freelist (alc, chunk, slot_for_size (PINNED_FIRST_SLOT_SIZE), PINNED_FIRST_SLOT_SIZE,
 271                         chunk->start_data, ((char*)chunk + FREELIST_PAGESIZE));
 272         mono_sgen_debug_printf (4, "Allocated pinned chunk %p, size: %d\n", chunk, size);
 273
 274         chunk->block.next = alc->chunk_list;
 275         alc->chunk_list = chunk;
 276
 277         chunk->allocator = alc;
 278
 279         return chunk;
 280 }
 281
 282 /* Must be called with an empty freelist for the given slot. */
 283 static gboolean
 284 populate_chunk_page (SgenInternalAllocator *alc, SgenPinnedChunk *chunk, int slot)
 285 {
 286         int size = freelist_sizes [slot];
 287         int i;
 288         g_assert (!chunk->free_list [slot]);
 289         g_assert (!chunk->free_list_nexts [slot]);
 290         for (i = 0; i < chunk->num_pages; ++i) {
 291                 if (chunk->page_sizes [i])
 292                         continue;
 293                 chunk->page_sizes [i] = size;
 294                 build_freelist (alc, chunk, slot, size, (char*)chunk + FREELIST_PAGESIZE * i, (char*)chunk + FREELIST_PAGESIZE * (i + 1));
 295                 return TRUE;
 296         }
 297         return FALSE;
 298 }
 299
 300 static void*
 301 alloc_from_slot (SgenInternalAllocator *alc, int slot, int type)
 302 {
 303         SgenPinnedChunk *pchunk;
 304         size_t size = freelist_sizes [slot];
 305
 306 #ifdef SGEN_DEBUG_INTERNAL_ALLOC
 307         if (type == INTERNAL_MEM_MS_BLOCK_INFO) {
 308                 g_assert (alc == &unmanaged_allocator);
 309         } else {
 310                 if (main_gc_thread)
 311                         g_assert (pthread_self () == alc->thread);
 312         }
 313 #endif
 314
 315         alc->small_internal_mem_bytes [type] += size;
 316
 317         if (alc->delayed_free_lists [slot]) {
 318                 void **p;
 319                 do {
 320                         p = alc->delayed_free_lists [slot];
 321                 } while (SGEN_CAS_PTR (&alc->delayed_free_lists [slot], *p, p) != p);
 322                 memset (p, 0, size);
 323                 return p;
 324         }
 325
 326  restart:
 327         pchunk = alc->free_lists [slot];
 328         if (pchunk) {
 329                 void **p = pchunk->free_list [slot];
 330                 void *next;
 331
 332                 g_assert (p);
 333
 334                 next = *p;
 335                 pchunk->free_list [slot] = next;
 336
 337                 if (!next) {
 338                         alc->free_lists [slot] = pchunk->free_list_nexts [slot];
 339                         pchunk->free_list_nexts [slot] = NULL;
 340                 }
 341
 342                 memset (p, 0, size);
 343                 return p;
 344         }
 345
 346         for (pchunk = alc->chunk_list; pchunk; pchunk = pchunk->block.next) {
 347                 if (populate_chunk_page (alc, pchunk, slot))
 348                         goto restart;
 349         }
 350
 351         pchunk = alloc_pinned_chunk (alc, type == INTERNAL_MEM_MANAGED);
 352         /* FIXME: handle OOM */
 353         if (pchunk->free_list [slot])
 354                 goto restart;
 355         if (!populate_chunk_page (alc, pchunk, slot))
 356                 g_assert_not_reached ();
 357         goto restart;
 358 }
 359
 360 /* used for the GC-internal data structures */
 361 void*
 362 mono_sgen_alloc_internal_full (SgenInternalAllocator *alc, size_t size, int type)
 363 {
 364         int slot;
 365         void *res = NULL;
 366
 367         g_assert (fixed_type_freelist_slots [type] == -1);
 368
 369         HEAVY_STAT (++stat_internal_alloc);
 370
 371         if (size > freelist_sizes [SGEN_INTERNAL_FREELIST_NUM_SLOTS - 1]) {
 372                 LargeInternalMemHeader *mh;
 373
 374                 size += sizeof (LargeInternalMemHeader);
 375                 mh = mono_sgen_alloc_os_memory (size, TRUE);
 376                 mh->magic = LARGE_INTERNAL_MEM_HEADER_MAGIC;
 377                 mh->size = size;
 378                 /* FIXME: do a CAS here */
 379                 large_internal_bytes_alloced += size;
 380                 return mh->data;
 381         }
 382
 383         slot = slot_for_size (size);
 384         g_assert (size <= freelist_sizes [slot]);
 385         res = alloc_from_slot (alc, slot, type);
 386
 387         return res;
 388 }
 389
 390 void*
 391 mono_sgen_alloc_internal_fixed (SgenInternalAllocator *allocator, int type)
 392 {
 393         int slot = fixed_type_freelist_slots [type];
 394         g_assert (slot >= 0);
 395         return alloc_from_slot (allocator, slot, type);
 396 }
 397
 398 void*
 399 mono_sgen_alloc_internal (int type)
 400 {
 401         return mono_sgen_alloc_internal_fixed (&unmanaged_allocator, type);
 402 }
 403
 404 void*
 405 mono_sgen_alloc_internal_dynamic (size_t size, int type)
 406 {
 407         return mono_sgen_alloc_internal_full (&unmanaged_allocator, size, type);
 408 }
 409
 410 static void
 411 free_from_slot (SgenInternalAllocator *alc, void *addr, int slot, int type)
 412 {
 413         SgenPinnedChunk *pchunk = (SgenPinnedChunk*)SGEN_PINNED_CHUNK_FOR_PTR (addr);
 414         void **p = addr;
 415         void *next;
 416
 417 #ifdef SGEN_DEBUG_INTERNAL_ALLOC
 418         if (alc->thread)
 419                 g_assert (pthread_self () == alc->thread);
 420         else if (main_gc_thread)
 421                 g_assert (pthread_self () == main_gc_thread);
 422 #endif
 423
 424         g_assert (addr >= (void*)pchunk && (char*)addr < (char*)pchunk + pchunk->num_pages * FREELIST_PAGESIZE);
 425         if (type == INTERNAL_MEM_MANAGED)
 426                 g_assert (pchunk->block.role == MEMORY_ROLE_PINNED);
 427         else
 428                 g_assert (pchunk->block.role == MEMORY_ROLE_INTERNAL);
 429
 430         next = pchunk->free_list [slot];
 431         *p = next;
 432         pchunk->free_list [slot] = p;
 433
 434         if (!next) {
 435                 g_assert (!pchunk->free_list_nexts [slot]);
 436                 pchunk->free_list_nexts [slot] = alc->free_lists [slot];
 437                 alc->free_lists [slot] = pchunk;
 438         }
 439
 440         alc->small_internal_mem_bytes [type] -= freelist_sizes [slot];
 441 }
 442
 443 void
 444 mono_sgen_free_internal_full (SgenInternalAllocator *alc, void *addr, size_t size, int type)
 445 {
 446         LargeInternalMemHeader *mh;
 447
 448         g_assert (fixed_type_freelist_slots [type] == -1);
 449
 450         if (!addr)
 451                 return;
 452
 453         if (size <= freelist_sizes [SGEN_INTERNAL_FREELIST_NUM_SLOTS - 1]) {
 454                 int slot = slot_for_size (size);
 455                 free_from_slot (alc, addr, slot, type);
 456                 return;
 457         }
 458
 459         mh = (LargeInternalMemHeader*)((char*)addr - G_STRUCT_OFFSET (LargeInternalMemHeader, data));
 460         g_assert (mh->magic == LARGE_INTERNAL_MEM_HEADER_MAGIC);
 461         g_assert (mh->size == size + sizeof (LargeInternalMemHeader));
 462         /* FIXME: do a CAS */
 463         large_internal_bytes_alloced -= mh->size;
 464         mono_sgen_free_os_memory (mh, mh->size);
 465 }
 466
 467 void
 468 mono_sgen_free_internal_fixed (SgenInternalAllocator *allocator, void *addr, int type)
 469 {
 470         int slot = fixed_type_freelist_slots [type];
 471         g_assert (slot >= 0);
 472
 473         free_from_slot (allocator, addr, slot, type);
 474 }
 475
 476 void
 477 mono_sgen_free_internal (void *addr, int type)
 478 {
 479         mono_sgen_free_internal_fixed (&unmanaged_allocator, addr, type);
 480 }
 481
 482 void
 483 mono_sgen_free_internal_dynamic (void *addr, size_t size, int type)
 484 {
 485         mono_sgen_free_internal_full (&unmanaged_allocator, addr, size, type);
 486 }
 487
 488 void
 489 mono_sgen_free_internal_delayed (void *addr, int type, SgenInternalAllocator *thread_allocator)
 490 {
 491         SgenPinnedChunk *pchunk = (SgenPinnedChunk*)SGEN_PINNED_CHUNK_FOR_PTR (addr);
 492         SgenInternalAllocator *alc = pchunk->allocator;
 493         int slot;
 494         void *next;
 495
 496         if (alc == thread_allocator) {
 497                 mono_sgen_free_internal_fixed (alc, addr, type);
 498                 return;
 499         }
 500
 501         slot = fixed_type_freelist_slots [type];
 502         g_assert (slot >= 0);
 503
 504         do {
 505                 next = alc->delayed_free_lists [slot];
 506                 *(void**)addr = next;
 507         } while (SGEN_CAS_PTR (&alc->delayed_free_lists [slot], addr, next) != next);
 508 }
 509
 510 void
 511 mono_sgen_dump_internal_mem_usage (FILE *heap_dump_file)
 512 {
 513         static char const *internal_mem_names [] = { "managed", "pin-queue", "fragment", "section", "scan-starts",
 514                                                      "fin-table", "finalize-entry", "dislink-table",
 515                                                      "dislink", "roots-table", "root-record", "statistics",
 516                                                      "remset", "gray-queue", "store-remset", "marksweep-tables",
 517                                                      "marksweep-block-info", "ephemeron-link", "worker-data",
 518                                                      "bridge-data" };
 519
 520         int i;
 521
 522         fprintf (heap_dump_file, "<other-mem-usage type=\"large-internal\" size=\"%lld\"/>\n", large_internal_bytes_alloced);
 523         fprintf (heap_dump_file, "<other-mem-usage type=\"pinned-chunks\" size=\"%lld\"/>\n", pinned_chunk_bytes_alloced);
 524         for (i = 0; i < INTERNAL_MEM_MAX; ++i) {
 525                 fprintf (heap_dump_file, "<other-mem-usage type=\"%s\" size=\"%ld\"/>\n",
 526                                 internal_mem_names [i], unmanaged_allocator.small_internal_mem_bytes [i]);
 527         }
 528 }
 529
 530 void
 531 mono_sgen_init_internal_allocator (void)
 532 {
 533         int i;
 534
 535         g_assert (SGEN_INTERNAL_FREELIST_NUM_SLOTS == sizeof (freelist_sizes) / sizeof (freelist_sizes [0]));
 536
 537         for (i = 0; i < INTERNAL_MEM_MAX; ++i)
 538                 fixed_type_freelist_slots [i] = -1;
 539
 540 #ifdef HEAVY_STATISTICS
 541         mono_counters_register ("Internal allocs", MONO_COUNTER_GC | MONO_COUNTER_LONG, &stat_internal_alloc);
 542 #endif
 543 }
 544
 545 SgenInternalAllocator*
 546 mono_sgen_get_unmanaged_allocator (void)
 547 {
 548         return &unmanaged_allocator;
 549 }
 550
 551 void
 552 mono_sgen_internal_scan_objects (SgenInternalAllocator *alc, IterateObjectCallbackFunc callback, void *callback_data)
 553 {
 554         SgenPinnedChunk *chunk;
 555         int i, obj_size;
 556         char *p, *endp;
 557         void **ptr;
 558         void *end_chunk;
 559         for (chunk = alc->chunk_list; chunk; chunk = chunk->block.next) {
 560                 end_chunk = (char*)chunk + chunk->num_pages * FREELIST_PAGESIZE;
 561                 mono_sgen_debug_printf (6, "Scanning pinned chunk %p (range: %p-%p)\n", chunk, chunk->start_data, end_chunk);
 562                 for (i = 0; i < chunk->num_pages; ++i) {
 563                         obj_size = chunk->page_sizes [i];
 564                         if (!obj_size)
 565                                 continue;
 566                         p = i? (char*)chunk + i * FREELIST_PAGESIZE: chunk->start_data;
 567                         endp = i? p + FREELIST_PAGESIZE: (char*)chunk + FREELIST_PAGESIZE;
 568                         mono_sgen_debug_printf (6, "Page %d (size: %d, range: %p-%p)\n", i, obj_size, p, endp);
 569                         while (p + obj_size <= endp) {
 570                                 ptr = (void**)p;
 571                                 /* if the first word (the vtable) is outside the chunk we have an object */
 572                                 if (*ptr && (*ptr < (void*)chunk || *ptr >= end_chunk))
 573                                         callback ((char*)ptr, obj_size, callback_data);
 574                                 p += obj_size;
 575                         }
 576                 }
 577         }
 578 }
 579
 580 void
 581 mono_sgen_internal_update_heap_boundaries (SgenInternalAllocator *alc)
 582 {
 583         SgenPinnedChunk *chunk;
 584         for (chunk = alc->chunk_list; chunk; chunk = chunk->block.next) {
 585                 char *end_chunk = (char*)chunk + chunk->num_pages * FREELIST_PAGESIZE;
 586                 mono_sgen_update_heap_boundaries ((mword)chunk, (mword)end_chunk);
 587         }
 588 }
 589
 590 /*
 591  * the array of pointers from @start to @end contains conservative
 592  * pointers to objects inside @chunk: mark each referenced object
 593  * with the PIN bit.
 594  */
 595 static void
 596 mark_pinned_from_addresses (SgenPinnedChunk *chunk, void **start, void **end, IterateObjectCallbackFunc callback, void *callback_data)
 597 {
 598         for (; start < end; start++) {
 599                 char *addr = *start;
 600                 int offset = (char*)addr - (char*)chunk;
 601                 int page = offset / FREELIST_PAGESIZE;
 602                 int obj_offset = page == 0? offset - ((char*)chunk->start_data - (char*)chunk): offset % FREELIST_PAGESIZE;
 603                 int slot_size = chunk->page_sizes [page];
 604                 void **ptr;
 605                 /* the page is not allocated */
 606                 if (!slot_size)
 607                         continue;
 608                 /* would be faster if we restrict the sizes to power of two,
 609                  * but that's a waste of memory: need to measure. it could reduce
 610                  * fragmentation since there are less pages needed, if for example
 611                  * someone interns strings of each size we end up with one page per
 612                  * interned string (still this is just ~40 KB): with more fine-grained sizes
 613                  * this increases the number of used pages.
 614                  */
 615                 if (page == 0) {
 616                         obj_offset /= slot_size;
 617                         obj_offset *= slot_size;
 618                         addr = (char*)chunk->start_data + obj_offset;
 619                 } else {
 620                         obj_offset /= slot_size;
 621                         obj_offset *= slot_size;
 622                         addr = (char*)chunk + page * FREELIST_PAGESIZE + obj_offset;
 623                 }
 624                 ptr = (void**)addr;
 625                 /* if the vtable is inside the chunk it's on the freelist, so skip */
 626                 /* FIXME: is it possible that we're pinning objects more than once here? */
 627                 if (*ptr && (*ptr < (void*)chunk->start_data || *ptr > (void*)((char*)chunk + chunk->num_pages * FREELIST_PAGESIZE)))
 628                         callback (addr, slot_size, callback_data);
 629         }
 630 }
 631
 632 void
 633 mono_sgen_internal_scan_pinned_objects (SgenInternalAllocator *alc, IterateObjectCallbackFunc callback, void *callback_data)
 634 {
 635         SgenPinnedChunk *chunk;
 636
 637         /* look for pinned addresses for pinned-alloc objects */
 638         mono_sgen_debug_printf (6, "Pinning from pinned-alloc objects\n");
 639         for (chunk = alc->chunk_list; chunk; chunk = chunk->block.next) {
 640                 int num_pinned;
 641                 void **pinned = mono_sgen_find_optimized_pin_queue_area (chunk->start_data,
 642                                 (char*)chunk + chunk->num_pages * FREELIST_PAGESIZE, &num_pinned);
 643                 if (num_pinned)
 644                         mark_pinned_from_addresses (chunk, pinned, pinned + num_pinned, callback, callback_data);
 645         }
 646 }
 647
 648 #endif