rt/gc/cdgc/gc.d

   1 /**
   2  * This module contains the garbage collector implementation.
   3  *
   4  * Copyright: Copyright (C) 2001-2007 Digital Mars, www.digitalmars.com.
   5  *            All rights reserved.
   6  * License:
   7  *  This software is provided 'as-is', without any express or implied
   8  *  warranty. In no event will the authors be held liable for any damages
   9  *  arising from the use of this software.
  10  *
  11  *  Permission is granted to anyone to use this software for any purpose,
  12  *  including commercial applications, and to alter it and redistribute it
  13  *  freely, in both source and binary form, subject to the following
  14  *  restrictions:
  15  *
  16  *  o  The origin of this software must not be misrepresented; you must not
  17  *     claim that you wrote the original software. If you use this software
  18  *     in a product, an acknowledgment in the product documentation would be
  19  *     appreciated but is not required.
  20  *  o  Altered source versions must be plainly marked as such, and must not
  21  *     be misrepresented as being the original software.
  22  *  o  This notice may not be removed or altered from any source
  23  *     distribution.
  24  * Authors:   Walter Bright, David Friedman, Sean Kelly
  25  */
  26
  27 module rt.gc.cdgc.gc;
  28
  29 // D Programming Language Garbage Collector implementation
  30
  31 /************** Debugging ***************************/
  32
  33 //debug = COLLECT_PRINTF;       // turn on printf's
  34 //debug = PTRCHECK;             // more pointer checking
  35 //debug = PTRCHECK2;            // thorough but slow pointer checking
  36
  37 /*************** Configuration *********************/
  38
  39 version = STACKGROWSDOWN;       // growing the stack means subtracting from the stack pointer
  40                                 // (use for Intel X86 CPUs)
  41                                 // else growing the stack means adding to the stack pointer
  42
  43 /***************************************************/
  44
  45 import rt.gc.cdgc.bits: GCBits;
  46 import rt.gc.cdgc.stats: GCStats, Stats;
  47 import dynarray = rt.gc.cdgc.dynarray;
  48 import os = rt.gc.cdgc.os;
  49 import opts = rt.gc.cdgc.opts;
  50
  51 import cstdlib = tango.stdc.stdlib;
  52 import cstring = tango.stdc.string;
  53 import cstdio = tango.stdc.stdio;
  54 debug(COLLECT_PRINTF) alias cstdio.printf printf;
  55
  56 /*
  57  * This is a small optimization that proved it's usefulness. For small chunks
  58  * or memory memset() seems to be slower (probably because of the call) that
  59  * simply doing a simple loop to set the memory.
  60  */
  61 void memset(void* dst, int c, size_t n)
  62 {
  63     // This number (32) has been determined empirically
  64     if (n > 32) {
  65         cstring.memset(dst, c, n);
  66         return;
  67     }
  68     auto p = cast(ubyte*)(dst);
  69     while (n-- > 0)
  70         *p++ = c;
  71 }
  72
  73 version (GNU)
  74 {
  75     // BUG: The following import will likely not work, since the gcc
  76     //      subdirectory is elsewhere.  Instead, perhaps the functions
  77     //      could be declared directly or some other resolution could
  78     //      be found.
  79     static import gcc.builtins; // for __builtin_unwind_int
  80 }
  81
  82 struct BlkInfo
  83 {
  84     void*  base;
  85     size_t size;
  86     uint   attr;
  87 }
  88
  89 package enum BlkAttr : uint
  90 {
  91     FINALIZE = 0b0000_0001,
  92     NO_SCAN  = 0b0000_0010,
  93     NO_MOVE  = 0b0000_0100,
  94     ALL_BITS = 0b1111_1111
  95 }
  96
  97 package bool has_pointermap(uint attrs)
  98 {
  99     return !opts.options.conservative && !(attrs & BlkAttr.NO_SCAN);
 100 }
 101
 102 private size_t round_up(size_t n, size_t to)
 103 {
 104     return (n + to - 1) / to;
 105 }
 106
 107 private
 108 {
 109     alias void delegate(Object) DEvent;
 110     alias void delegate( void*, void* ) scanFn;
 111     enum { OPFAIL = ~cast(size_t)0 }
 112
 113     extern (C)
 114     {
 115         version (DigitalMars) version(OSX)
 116             oid _d_osx_image_init();
 117
 118         void* rt_stackBottom();
 119         void* rt_stackTop();
 120         void rt_finalize( void* p, bool det = true );
 121         void rt_attachDisposeEvent(Object h, DEvent e);
 122         bool rt_detachDisposeEvent(Object h, DEvent e);
 123         void rt_scanStaticData( scanFn scan );
 124
 125         void thread_init();
 126         bool thread_needLock();
 127         void thread_suspendAll();
 128         void thread_resumeAll();
 129         void thread_scanAll( scanFn fn, void* curStackTop = null );
 130
 131         void onOutOfMemoryError();
 132     }
 133 }
 134
 135
 136 enum
 137 {
 138     PAGESIZE =    4096,
 139     POOLSIZE =   (4096*256),
 140 }
 141
 142
 143 enum
 144 {
 145     B_16,
 146     B_32,
 147     B_64,
 148     B_128,
 149     B_256,
 150     B_512,
 151     B_1024,
 152     B_2048,
 153     B_PAGE,             // start of large alloc
 154     B_PAGEPLUS,         // continuation of large alloc
 155     B_FREE,             // free page
 156     B_MAX
 157 }
 158
 159
 160 alias ubyte Bins;
 161
 162
 163 struct List
 164 {
 165     List* next;
 166     Pool* pool;
 167 }
 168
 169
 170 struct Range
 171 {
 172     void *pbot;
 173     void *ptop;
 174     int opCmp(in Range other)
 175     {
 176         if (pbot < other.pbot)
 177             return -1;
 178         else
 179         return cast(int)(pbot > other.pbot);
 180     }
 181 }
 182
 183
 184 const uint binsize[B_MAX] = [ 16,32,64,128,256,512,1024,2048,4096 ];
 185 const uint notbinsize[B_MAX] = [ ~(16u-1),~(32u-1),~(64u-1),~(128u-1),~(256u-1),
 186                                 ~(512u-1),~(1024u-1),~(2048u-1),~(4096u-1) ];
 187
 188
 189 /* ============================ GC =============================== */
 190
 191
 192 class GCLock {} // just a dummy so we can get a global lock
 193
 194
 195 struct GC
 196 {
 197     // global lock
 198     ClassInfo lock;
 199
 200     void* p_cache;
 201     size_t size_cache;
 202
 203     // !=0 means don't scan stack
 204     uint no_stack;
 205     bool any_changes;
 206     void* stack_bottom;
 207     uint inited;
 208     /// Turn off collections if > 0
 209     int disabled;
 210
 211     // PID of the fork()ed process doing the mark() (0 if is not running)
 212     int mark_proc_pid;
 213
 214     /// min(pool.baseAddr)
 215     byte *min_addr;
 216     /// max(pool.topAddr)
 217     byte *max_addr;
 218
 219     /// Total heap memory
 220     size_t total_mem;
 221     /// Free heap memory
 222     size_t free_mem;
 223
 224     /// Free list for each size
 225     List*[B_MAX] free_list;
 226
 227     dynarray.DynArray!(void*) roots;
 228     dynarray.DynArray!(Range) ranges;
 229     dynarray.DynArray!(Pool*) pools;
 230
 231     Stats stats;
 232 }
 233
 234 // call locked if necessary
 235 private T locked(T, alias Code)()
 236 {
 237     if (thread_needLock())
 238         synchronized (gc.lock) return Code();
 239     else
 240        return Code();
 241 }
 242
 243 private GC* gc;
 244
 245
 246 bool collect_in_progress()
 247 {
 248     return gc.mark_proc_pid != 0;
 249 }
 250
 251
 252 bool Invariant()
 253 {
 254     assert (gc !is null);
 255     if (gc.inited) {
 256         size_t total_mem = 0;
 257         size_t free_mem = 0;
 258         for (size_t i = 0; i < gc.pools.length; i++) {
 259             Pool* pool = gc.pools[i];
 260             pool.Invariant();
 261             if (i == 0)
 262                 assert(gc.min_addr == pool.baseAddr);
 263             if (i + 1 < gc.pools.length)
 264                 assert(*pool < *gc.pools[i + 1]);
 265             else if (i + 1 == gc.pools.length)
 266                 assert(gc.max_addr == pool.topAddr);
 267             total_mem += pool.npages * PAGESIZE;
 268             for (size_t pn = 0; pn < pool.npages; ++pn)
 269                 if (pool.pagetable[pn] == B_FREE)
 270                     free_mem += PAGESIZE;
 271         }
 272
 273         gc.roots.Invariant();
 274         gc.ranges.Invariant();
 275
 276         for (size_t i = 0; i < gc.ranges.length; i++) {
 277             assert(gc.ranges[i].pbot);
 278             assert(gc.ranges[i].ptop);
 279             assert(gc.ranges[i].pbot <= gc.ranges[i].ptop);
 280         }
 281
 282         for (size_t i = 0; i < B_PAGE; i++) {
 283             for (List *list = gc.free_list[i]; list; list = list.next) {
 284                 auto pool = list.pool;
 285                 assert (pool !is null);
 286                 auto p = cast(byte*) list;
 287                 assert (p >= pool.baseAddr);
 288                 assert (p < pool.topAddr);
 289                 assert (pool.freebits.test((p - pool.baseAddr) / 16));
 290                 free_mem += binsize[i];
 291             }
 292         }
 293         assert (gc.total_mem == total_mem);
 294         assert (gc.free_mem == free_mem);
 295     }
 296     return true;
 297 }
 298
 299
 300 /**
 301  * Find Pool that pointer is in.
 302  * Return null if not in a Pool.
 303  * Assume pools is sorted.
 304  */
 305 Pool* findPool(void* p)
 306 {
 307     if (p < gc.min_addr || p >= gc.max_addr)
 308         return null;
 309     if (gc.pools.length == 0)
 310         return null;
 311     if (gc.pools.length == 1)
 312         return gc.pools[0];
 313     /// The pooltable[] is sorted by address, so do a binary search
 314     size_t low = 0;
 315     size_t high = gc.pools.length - 1;
 316     while (low <= high) {
 317         size_t mid = (low + high) / 2;
 318         auto pool = gc.pools[mid];
 319         if (p < pool.baseAddr)
 320             high = mid - 1;
 321         else if (p >= pool.topAddr)
 322             low = mid + 1;
 323         else
 324             return pool;
 325     }
 326     // Not found
 327     return null;
 328 }
 329
 330
 331 /**
 332  * Determine the base address of the block containing p.  If p is not a gc
 333  * allocated pointer, return null.
 334  */
 335 BlkInfo getInfo(void* p)
 336 {
 337     assert (p !is null);
 338     Pool* pool = findPool(p);
 339     if (pool is null)
 340         return BlkInfo.init;
 341     BlkInfo info;
 342     info.base = pool.findBase(p);
 343     if (info.base is null)
 344         return BlkInfo.init;
 345     info.size = pool.findSize(info.base);
 346     size_t bit_i = (info.base - pool.baseAddr) / 16;
 347     info.attr = getAttr(pool, bit_i);
 348     if (has_pointermap(info.attr)) {
 349         info.size -= size_t.sizeof; // PointerMap bitmask
 350         // Points to the PointerMap bitmask pointer, not user data
 351         if (p >= (info.base + info.size)) {
 352             return BlkInfo.init;
 353         }
 354     }
 355     if (opts.options.sentinel) {
 356         info.base = sentinel_add(info.base);
 357         // points to sentinel data, not user data
 358         if (p < info.base || p >= sentinel_post(info.base))
 359             return BlkInfo.init;
 360         info.size -= SENTINEL_EXTRA;
 361     }
 362     return info;
 363 }
 364
 365
 366 /**
 367  * Compute bin for size.
 368  */
 369 Bins findBin(size_t size)
 370 {
 371     Bins bin;
 372     if (size <= 256)
 373     {
 374         if (size <= 64)
 375         {
 376             if (size <= 16)
 377                 bin = B_16;
 378             else if (size <= 32)
 379                 bin = B_32;
 380             else
 381                 bin = B_64;
 382         }
 383         else
 384         {
 385             if (size <= 128)
 386                 bin = B_128;
 387             else
 388                 bin = B_256;
 389         }
 390     }
 391     else
 392     {
 393         if (size <= 1024)
 394         {
 395             if (size <= 512)
 396                 bin = B_512;
 397             else
 398                 bin = B_1024;
 399         }
 400         else
 401         {
 402             if (size <= 2048)
 403                 bin = B_2048;
 404             else
 405                 bin = B_PAGE;
 406         }
 407     }
 408     return bin;
 409 }
 410
 411
 412 /**
 413  * Allocate a new pool of at least size bytes.
 414  * Sort it into pools.
 415  * Mark all memory in the pool as B_FREE.
 416  * Return the actual number of bytes reserved or 0 on error.
 417  */
 418 size_t reserve(size_t size)
 419 {
 420     assert(size != 0);
 421     size_t npages = round_up(size, PAGESIZE);
 422     Pool*  pool = newPool(npages);
 423
 424     if (!pool)
 425         return 0;
 426     return pool.npages * PAGESIZE;
 427 }
 428
 429
 430 /**
 431  * Minimizes physical memory usage by returning free pools to the OS.
 432  *
 433  * If full is false, keep some pools alive if the resulting free memory would
 434  * be too small.
 435  */
 436 void minimize(bool full = true)
 437 {
 438     // The shared mark bits of the freed pool might be used by the mark process
 439     if (collect_in_progress())
 440         return;
 441
 442     if (gc.pools.length == 0)
 443         return;
 444
 445     for (size_t n = 0; n < gc.pools.length; n++)
 446     {
 447         Pool* pool = gc.pools[n];
 448         size_t pn;
 449         for (pn = 0; pn < pool.npages; pn++)
 450         {
 451             if (cast(Bins)pool.pagetable[pn] != B_FREE)
 452                 break;
 453         }
 454         if (pn < pool.npages)
 455             continue;
 456         // Free pool
 457         size_t pool_size = pool.npages * PAGESIZE;
 458         if (!full) {
 459             double percent_free = (gc.free_mem - pool_size) * 100.0 /
 460                     (gc.total_mem - pool_size);
 461             if (percent_free < opts.options.min_free)
 462                 continue; // not enough free, don't remove this pool
 463         }
 464         gc.total_mem -= pool_size;
 465         gc.free_mem -= pool_size;
 466         pool.Dtor();
 467         cstdlib.free(pool);
 468         gc.pools.remove_at(n);
 469         n--;
 470     }
 471     gc.min_addr = gc.pools[0].baseAddr;
 472     gc.max_addr = gc.pools[gc.pools.length - 1].topAddr;
 473 }
 474
 475
 476 /**
 477  * Allocate a chunk of memory that is larger than a page.
 478  * Return null if out of memory.
 479  */
 480 void* bigAlloc(size_t npages, out Pool* pool, size_t* pn, bool* collected)
 481 {
 482     *collected = false;
 483     // This code could use some refinement when repeatedly
 484     // allocating very large arrays.
 485
 486     void* find_block()
 487     {
 488         for (size_t n = 0; n < gc.pools.length; n++)
 489         {
 490             pool = gc.pools[n];
 491             *pn = pool.allocPages(npages);
 492             if (*pn != OPFAIL)
 493                 return pool.baseAddr + *pn * PAGESIZE;
 494         }
 495         return null;
 496     }
 497
 498     void* alloc_more()
 499     {
 500         // Allocate new pool
 501         pool = newPool(npages);
 502         if (!pool)
 503             return null; // let malloc handle the error
 504         *pn = pool.allocPages(npages);
 505         assert(*pn != OPFAIL);
 506         return pool.baseAddr + *pn * PAGESIZE;
 507     }
 508
 509     if (void* p = find_block())
 510         return p;
 511
 512     if (gc.disabled)
 513         return alloc_more();
 514
 515     // Try collecting
 516     size_t freedpages = fullcollectshell();
 517     *collected = true;
 518     if (freedpages >= npages) {
 519         if (void* p = find_block())
 520             return p;
 521     }
 522
 523     return alloc_more();
 524 }
 525
 526
 527 /**
 528  * Allocate a new pool with at least npages in it.
 529  * Sort it into pools.
 530  * Return null if failed.
 531  */
 532 Pool *newPool(size_t npages)
 533 {
 534     // Minimum of POOLSIZE
 535     if (npages < POOLSIZE/PAGESIZE)
 536         npages = POOLSIZE/PAGESIZE;
 537     else if (npages > POOLSIZE/PAGESIZE)
 538     {
 539         // Give us 150% of requested size, so there's room to extend
 540         auto n = npages + (npages >> 1);
 541         if (n < size_t.max/PAGESIZE)
 542             npages = n;
 543     }
 544
 545     // Allocate successively larger pools up to 8 megs
 546     if (gc.pools.length)
 547     {
 548         size_t n = gc.pools.length;
 549         if (n > 8)
 550             n = 8;                  // cap pool size at 8 megs
 551         n *= (POOLSIZE / PAGESIZE);
 552         if (npages < n)
 553             npages = n;
 554     }
 555
 556     auto pool = cast(Pool*) cstdlib.calloc(1, Pool.sizeof);
 557     if (pool is null)
 558         return null;
 559     pool.initialize(npages);
 560     if (!pool.baseAddr)
 561     {
 562         pool.Dtor();
 563         return null;
 564     }
 565
 566     auto inserted_pool = *gc.pools.insert_sorted!("*a < *b")(pool);
 567     if (inserted_pool is null) {
 568         pool.Dtor();
 569         return null;
 570     }
 571     assert (inserted_pool is pool);
 572     gc.min_addr = gc.pools[0].baseAddr;
 573     gc.max_addr = gc.pools[gc.pools.length - 1].topAddr;
 574     size_t pool_size = pool.topAddr - pool.baseAddr;
 575     gc.total_mem += pool_size;
 576     gc.free_mem += pool_size;
 577     return pool;
 578 }
 579
 580
 581 /**
 582  * Allocate a page of bin's.
 583  * Returns:
 584  *  0       failed
 585  */
 586 int allocPage(Bins bin)
 587 {
 588     Pool*  pool;
 589     size_t pn;
 590
 591     for (size_t n = 0; n < gc.pools.length; n++)
 592     {
 593         pool = gc.pools[n];
 594         pn = pool.allocPages(1);
 595         if (pn != OPFAIL)
 596             goto L1;
 597     }
 598     return 0;               // failed
 599
 600   L1:
 601     pool.pagetable[pn] = cast(ubyte)bin;
 602
 603     // Convert page to free list
 604     size_t size = binsize[bin];
 605     auto list_head = &gc.free_list[bin];
 606
 607     byte* p = pool.baseAddr + pn * PAGESIZE;
 608     byte*  ptop = p + PAGESIZE;
 609     size_t bit_i = pn * (PAGESIZE / 16);
 610     pool.freebits.set_group(bit_i, PAGESIZE / 16);
 611     for (; p < ptop; p += size)
 612     {
 613         List* l = cast(List *) p;
 614         l.next = *list_head;
 615         l.pool = pool;
 616         *list_head = l;
 617     }
 618     return 1;
 619 }
 620
 621
 622 /**
 623  * Search a range of memory values and mark any pointers into the GC pool using
 624  * type information (bitmask of pointer locations).
 625  */
 626 void mark_range(void *pbot, void *ptop, size_t* pm_bitmask)
 627 {
 628     // TODO: make our own assert because assert uses the GC
 629     assert (pbot <= ptop);
 630
 631     const BITS_PER_WORD = size_t.sizeof * 8;
 632
 633     void **p1 = cast(void **)pbot;
 634     void **p2 = cast(void **)ptop;
 635     size_t pcache = 0;
 636     bool changes = false;
 637
 638     size_t type_size = pm_bitmask[0];
 639     size_t* pm_bits = pm_bitmask + 1;
 640     bool has_type_info = type_size != 1 || pm_bits[0] != 1 || pm_bits[1] != 0;
 641
 642     //printf("marking range: %p -> %p\n", pbot, ptop);
 643     for (; p1 + type_size <= p2; p1 += type_size) {
 644         for (size_t n = 0; n < type_size; n++) {
 645             // scan bit set for this word
 646             if (has_type_info &&
 647                     !(pm_bits[n / BITS_PER_WORD] & (1 << (n % BITS_PER_WORD))))
 648                 continue;
 649
 650             void* p = *(p1 + n);
 651
 652             if (p < gc.min_addr || p >= gc.max_addr)
 653                 continue;
 654
 655             if ((cast(size_t)p & ~(PAGESIZE-1)) == pcache)
 656                 continue;
 657
 658             Pool* pool = findPool(p);
 659             if (pool)
 660             {
 661                 size_t offset = cast(size_t)(p - pool.baseAddr);
 662                 size_t bit_i = void;
 663                 size_t pn = offset / PAGESIZE;
 664                 Bins   bin = cast(Bins)pool.pagetable[pn];
 665
 666                 // Cache B_PAGE, B_PAGEPLUS and B_FREE lookups
 667                 if (bin >= B_PAGE)
 668                     pcache = cast(size_t)p & ~(PAGESIZE-1);
 669
 670                 // Adjust bit to be at start of allocated memory block
 671                 if (bin <= B_PAGE)
 672                     bit_i = (offset & notbinsize[bin]) / 16;
 673                 else if (bin == B_PAGEPLUS)
 674                 {
 675                     do
 676                     {
 677                         --pn;
 678                     }
 679                     while (cast(Bins)pool.pagetable[pn] == B_PAGEPLUS);
 680                     bit_i = pn * (PAGESIZE / 16);
 681                 }
 682                 else // Don't mark bits in B_FREE pages
 683                     continue;
 684
 685                 if (!pool.mark.test(bit_i))
 686                 {
 687                     pool.mark.set(bit_i);
 688                     if (!pool.noscan.test(bit_i))
 689                     {
 690                         pool.scan.set(bit_i);
 691                         changes = true;
 692                     }
 693                 }
 694             }
 695         }
 696     }
 697     if (changes)
 698         gc.any_changes = true;
 699 }
 700
 701 /**
 702  * Return number of full pages free'd.
 703  */
 704 size_t fullcollectshell(bool early = false)
 705 {
 706     gc.stats.collection_started();
 707     scope (exit)
 708         gc.stats.collection_finished();
 709
 710     // The purpose of the 'shell' is to ensure all the registers
 711     // get put on the stack so they'll be scanned
 712     void *sp;
 713     size_t result;
 714     version (GNU)
 715     {
 716         gcc.builtins.__builtin_unwind_init();
 717         sp = & sp;
 718     }
 719     else version(LDC)
 720     {
 721         version(X86)
 722         {
 723             uint eax,ecx,edx,ebx,ebp,esi,edi;
 724             asm
 725             {
 726                 mov eax[EBP], EAX      ;
 727                 mov ecx[EBP], ECX      ;
 728                 mov edx[EBP], EDX      ;
 729                 mov ebx[EBP], EBX      ;
 730                 mov ebp[EBP], EBP      ;
 731                 mov esi[EBP], ESI      ;
 732                 mov edi[EBP], EDI      ;
 733                 mov  sp[EBP], ESP      ;
 734             }
 735         }
 736         else version (X86_64)
 737         {
 738             ulong rax,rbx,rcx,rdx,rbp,rsi,rdi,r8,r9,r10,r11,r12,r13,r14,r15;
 739             asm
 740             {
 741                 movq rax[RBP], RAX      ;
 742                 movq rbx[RBP], RBX      ;
 743                 movq rcx[RBP], RCX      ;
 744                 movq rdx[RBP], RDX      ;
 745                 movq rbp[RBP], RBP      ;
 746                 movq rsi[RBP], RSI      ;
 747                 movq rdi[RBP], RDI      ;
 748                 movq r8 [RBP], R8       ;
 749                 movq r9 [RBP], R9       ;
 750                 movq r10[RBP], R10      ;
 751                 movq r11[RBP], R11      ;
 752                 movq r12[RBP], R12      ;
 753                 movq r13[RBP], R13      ;
 754                 movq r14[RBP], R14      ;
 755                 movq r15[RBP], R15      ;
 756                 movq  sp[RBP], RSP      ;
 757             }
 758         }
 759         else
 760         {
 761             static assert( false, "Architecture not supported." );
 762         }
 763     }
 764     else
 765     {
 766     asm
 767     {
 768         pushad              ;
 769         mov sp[EBP],ESP     ;
 770     }
 771     }
 772     result = fullcollect(sp, early);
 773     version (GNU)
 774     {
 775         // nothing to do
 776     }
 777     else version(LDC)
 778     {
 779         // nothing to do
 780     }
 781     else
 782     {
 783     asm
 784     {
 785         popad               ;
 786     }
 787     }
 788     return result;
 789 }
 790
 791
 792 /**
 793  *
 794  */
 795 size_t fullcollect(void *stackTop, bool early = false)
 796 {
 797     debug(COLLECT_PRINTF) printf("Gcx.fullcollect(early=%d)\n",
 798             cast(int) early);
 799
 800     // We will block the mutator only if eager allocation is not used and this
 801     // is not an early collection.
 802     bool block = !opts.options.eager_alloc && !early;
 803
 804     // If there is a mark process running, check if it already finished.  If
 805     // that is the case, we lunch the sweep phase and hope enough memory is
 806     // freed.  If it's still running, either we block until the mark phase is
 807     // done (and then sweep to finish the collection), or we tell the caller
 808     // process no memory has been recovered (it will allocated more to fulfill
 809     // the current request if eager allocation is used) and let the mark phase
 810     // keep running in parallel.
 811     if (collect_in_progress()) {
 812         os.WRes r = os.wait_pid(gc.mark_proc_pid, block);
 813         assert (r != os.WRes.ERROR);
 814         switch (r) {
 815             case os.WRes.DONE:
 816                 debug(COLLECT_PRINTF) printf("\t\tmark proc DONE (block=%d)\n",
 817                         cast(int) block);
 818                 gc.mark_proc_pid = 0;
 819                 return sweep();
 820             case os.WRes.RUNNING:
 821                 debug(COLLECT_PRINTF) printf("\t\tmark proc RUNNING\n");
 822                 if (!block)
 823                     return 0;
 824                 // Something went wrong, if block is true, wait() should never
 825                 // returned RUNNING.
 826                 goto case os.WRes.ERROR;
 827             case os.WRes.ERROR:
 828                 debug(COLLECT_PRINTF) printf("\t\tmark proc ERROR\n");
 829                 disable_fork(); // Try to keep going without forking
 830                 break;
 831         }
 832     }
 833
 834     // We always need to stop the world to make threads save the CPU registers
 835     // in the stack and prepare themselves for thread_scanAll()
 836     thread_suspendAll();
 837     gc.stats.world_stopped();
 838
 839     // If forking is enabled, we fork() and start a new mark phase in the
 840     // child. If the collection should not block, the parent process tells the
 841     // caller no memory could be recycled immediately (if eager allocation is
 842     // used, and this collection was triggered by an allocation, the caller
 843     // should allocate more memory to fulfill the request). If the collection
 844     // should block, the parent will wait for the mark phase to finish before
 845     // returning control to the mutator, but other threads are restarted and
 846     // may run in parallel with the mark phase (unless they allocate or use the
 847     // GC themselves, in which case the global GC lock will stop them).
 848     if (opts.options.fork) {
 849         cstdio.fflush(null); // avoid duplicated FILE* output
 850         os.pid_t child_pid = os.fork();
 851         assert (child_pid != -1); // don't accept errors in non-release mode
 852         switch (child_pid) {
 853         case -1: // if fork() fails, fall-back to stop-the-world
 854             disable_fork();
 855             break;
 856         case 0: // child process (i.e. the collectors mark phase)
 857             mark(stackTop);
 858             cstdlib.exit(0);
 859             break; // bogus, will never reach here
 860         default: // parent process (i.e. the mutator)
 861             thread_resumeAll();
 862             gc.stats.world_started();
 863             if (!block) {
 864                 gc.mark_proc_pid = child_pid;
 865                 return 0;
 866             }
 867             os.WRes r = os.wait_pid(child_pid); // block until it finishes
 868             assert (r == os.WRes.DONE);
 869             debug(COLLECT_PRINTF) printf("\t\tmark proc DONE (block=%d)\n",
 870                     cast(int) block);
 871             if (r == os.WRes.DONE)
 872                 return sweep();
 873             debug(COLLECT_PRINTF) printf("\tmark() proc ERROR\n");
 874             // If there was some error, try to keep going without forking
 875             disable_fork();
 876             // Re-suspend the threads to do the marking in this process
 877             thread_suspendAll();
 878             gc.stats.world_stopped();
 879         }
 880
 881     }
 882
 883     // If we reach here, we are using the standard stop-the-world collection,
 884     // either because fork was disabled in the first place, or because it was
 885     // disabled because of some error.
 886     mark(stackTop);
 887     thread_resumeAll();
 888     gc.stats.world_started();
 889
 890     return sweep();
 891 }
 892
 893
 894 /**
 895  *
 896  */
 897 void mark(void *stackTop)
 898 {
 899     debug(COLLECT_PRINTF) printf("\tmark()\n");
 900
 901     gc.any_changes = false;
 902
 903     for (size_t n = 0; n < gc.pools.length; n++)
 904     {
 905         Pool* pool = gc.pools[n];
 906         pool.mark.copy(&pool.freebits);
 907         pool.scan.zero();
 908     }
 909
 910     /// Marks a range of memory in conservative mode.
 911     void mark_conservative_range(void* pbot, void* ptop)
 912     {
 913         mark_range(pbot, ptop, PointerMap.init.bits.ptr);
 914     }
 915
 916     rt_scanStaticData(&mark_conservative_range);
 917
 918     if (!gc.no_stack)
 919     {
 920         // Scan stacks and registers for each paused thread
 921         thread_scanAll(&mark_conservative_range, stackTop);
 922     }
 923
 924     // Scan roots
 925     debug(COLLECT_PRINTF) printf("scan roots[]\n");
 926     mark_conservative_range(gc.roots.ptr, gc.roots.ptr + gc.roots.length);
 927
 928     // Scan ranges
 929     debug(COLLECT_PRINTF) printf("scan ranges[]\n");
 930     for (size_t n = 0; n < gc.ranges.length; n++)
 931     {
 932         debug(COLLECT_PRINTF) printf("\t%x .. %x\n", gc.ranges[n].pbot, gc.ranges[n].ptop);
 933         mark_conservative_range(gc.ranges[n].pbot, gc.ranges[n].ptop);
 934     }
 935
 936     debug(COLLECT_PRINTF) printf("\tscan heap\n");
 937     while (gc.any_changes)
 938     {
 939         gc.any_changes = false;
 940         for (size_t n = 0; n < gc.pools.length; n++)
 941         {
 942             uint *bbase;
 943             uint *b;
 944             uint *btop;
 945
 946             Pool* pool = gc.pools[n];
 947
 948             bbase = pool.scan.base();
 949             btop = bbase + pool.scan.nwords;
 950             for (b = bbase; b < btop;)
 951             {
 952                 Bins   bin;
 953                 size_t pn;
 954                 size_t u;
 955                 size_t bitm;
 956                 byte*  o;
 957
 958                 bitm = *b;
 959                 if (!bitm)
 960                 {
 961                     b++;
 962                     continue;
 963                 }
 964                 *b = 0;
 965
 966                 o = pool.baseAddr + (b - bbase) * 32 * 16;
 967                 if (!(bitm & 0xFFFF))
 968                 {
 969                     bitm >>= 16;
 970                     o += 16 * 16;
 971                 }
 972                 for (; bitm; o += 16, bitm >>= 1)
 973                 {
 974                     if (!(bitm & 1))
 975                         continue;
 976
 977                     pn = cast(size_t)(o - pool.baseAddr) / PAGESIZE;
 978                     bin = cast(Bins)pool.pagetable[pn];
 979                     if (bin < B_PAGE) {
 980                         if (opts.options.conservative)
 981                             mark_conservative_range(o, o + binsize[bin]);
 982                         else {
 983                             auto end_of_blk = cast(size_t**)(o +
 984                                     binsize[bin] - size_t.sizeof);
 985                             size_t* pm_bitmask = *end_of_blk;
 986                             mark_range(o, end_of_blk, pm_bitmask);
 987                         }
 988                     }
 989                     else if (bin == B_PAGE || bin == B_PAGEPLUS)
 990                     {
 991                         if (bin == B_PAGEPLUS)
 992                         {
 993                             while (pool.pagetable[pn - 1] != B_PAGE)
 994                                 pn--;
 995                         }
 996                         u = 1;
 997                         while (pn + u < pool.npages &&
 998                                 pool.pagetable[pn + u] == B_PAGEPLUS)
 999                             u++;
1000
1001                         size_t blk_size = u * PAGESIZE;
1002                         if (opts.options.conservative)
1003                             mark_conservative_range(o, o + blk_size);
1004                         else {
1005                             auto end_of_blk = cast(size_t**)(o + blk_size -
1006                                     size_t.sizeof);
1007                             size_t* pm_bitmask = *end_of_blk;
1008                             mark_range(o, end_of_blk, pm_bitmask);
1009                         }
1010                     }
1011                 }
1012             }
1013         }
1014     }
1015 }
1016
1017
1018 /**
1019  *
1020  */
1021 size_t sweep()
1022 {
1023     // Free up everything not marked
1024     debug(COLLECT_PRINTF) printf("\tsweep\n");
1025     gc.p_cache = null;
1026     gc.size_cache = 0;
1027     gc.free_mem = 0; // will be recalculated
1028     size_t freedpages = 0;
1029     size_t freed = 0;
1030     for (size_t n = 0; n < gc.pools.length; n++)
1031     {
1032         Pool* pool = gc.pools[n];
1033         pool.clear_cache();
1034         uint*  bbase = pool.mark.base();
1035         size_t pn;
1036         for (pn = 0; pn < pool.npages; pn++, bbase += PAGESIZE / (32 * 16))
1037         {
1038             Bins bin = cast(Bins)pool.pagetable[pn];
1039
1040             if (bin < B_PAGE)
1041             {
1042                 auto size = binsize[bin];
1043                 byte* p = pool.baseAddr + pn * PAGESIZE;
1044                 byte* ptop = p + PAGESIZE;
1045                 size_t bit_i = pn * (PAGESIZE/16);
1046                 size_t bit_stride = size / 16;
1047
1048 version(none) // BUG: doesn't work because freebits() must also be cleared
1049 {
1050                 // If free'd entire page
1051                 if (bbase[0] == 0 && bbase[1] == 0 && bbase[2] == 0 &&
1052                         bbase[3] == 0 && bbase[4] == 0 && bbase[5] == 0 &&
1053                         bbase[6] == 0 && bbase[7] == 0)
1054                 {
1055                     for (; p < ptop; p += size, bit_i += bit_stride)
1056                     {
1057                         if (pool.finals.testClear(bit_i)) {
1058                             if (opts.options.sentinel)
1059                                 rt_finalize(sentinel_add(p), false/*gc.no_stack > 0*/);
1060                             else
1061                                 rt_finalize(p, false/*gc.no_stack > 0*/);
1062                         }
1063                         clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
1064
1065                         if (opts.options.mem_stomp)
1066                             memset(p, 0xF3, size);
1067                     }
1068                     pool.pagetable[pn] = B_FREE;
1069                     freed += PAGESIZE;
1070                     continue;
1071                 }
1072 }
1073                 for (; p < ptop; p += size, bit_i += bit_stride)
1074                 {
1075                     if (!pool.mark.test(bit_i))
1076                     {
1077                         if (opts.options.sentinel)
1078                             sentinel_Invariant(sentinel_add(p));
1079
1080                         pool.freebits.set(bit_i);
1081                         if (pool.finals.testClear(bit_i)) {
1082                             if (opts.options.sentinel)
1083                                 rt_finalize(sentinel_add(p), false/*gc.no_stack > 0*/);
1084                             else
1085                                 rt_finalize(p, false/*gc.no_stack > 0*/);
1086                         }
1087                         clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
1088
1089                         if (opts.options.mem_stomp)
1090                             memset(p, 0xF3, size);
1091
1092                         freed += size;
1093                     }
1094                 }
1095             }
1096             else if (bin == B_PAGE)
1097             {
1098                 size_t bit_stride = PAGESIZE / 16;
1099                 size_t bit_i = pn * bit_stride;
1100                 if (!pool.mark.test(bit_i))
1101                 {
1102                     byte *p = pool.baseAddr + pn * PAGESIZE;
1103                     if (opts.options.sentinel)
1104                         sentinel_Invariant(sentinel_add(p));
1105                     if (pool.finals.testClear(bit_i)) {
1106                         if (opts.options.sentinel)
1107                             rt_finalize(sentinel_add(p), false/*gc.no_stack > 0*/);
1108                         else
1109                             rt_finalize(p, false/*gc.no_stack > 0*/);
1110                     }
1111                     clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
1112
1113                     debug(COLLECT_PRINTF) printf("\tcollecting big %p\n", p);
1114                     pool.pagetable[pn] = B_FREE;
1115                     pool.freebits.set_group(bit_i, PAGESIZE / 16);
1116                     freedpages++;
1117                     gc.free_mem += PAGESIZE;
1118                     if (opts.options.mem_stomp)
1119                         memset(p, 0xF3, PAGESIZE);
1120                     while (pn + 1 < pool.npages && pool.pagetable[pn + 1] == B_PAGEPLUS)
1121                     {
1122                         pn++;
1123                         pool.pagetable[pn] = B_FREE;
1124                         bit_i += bit_stride;
1125                         pool.freebits.set_group(bit_i, PAGESIZE / 16);
1126                         freedpages++;
1127                         gc.free_mem += PAGESIZE;
1128
1129                         if (opts.options.mem_stomp)
1130                         {
1131                             p += PAGESIZE;
1132                             memset(p, 0xF3, PAGESIZE);
1133                         }
1134                     }
1135                 }
1136             }
1137             else if (bin == B_FREE) {
1138                 gc.free_mem += PAGESIZE;
1139             }
1140         }
1141     }
1142
1143     // Zero buckets
1144     gc.free_list[] = null;
1145
1146     // Free complete pages, rebuild free list
1147     debug(COLLECT_PRINTF) printf("\tfree complete pages\n");
1148     size_t recoveredpages = 0;
1149     for (size_t n = 0; n < gc.pools.length; n++)
1150     {
1151         Pool* pool = gc.pools[n];
1152         for (size_t pn = 0; pn < pool.npages; pn++)
1153         {
1154             Bins   bin = cast(Bins)pool.pagetable[pn];
1155             size_t bit_i;
1156             size_t u;
1157
1158             if (bin < B_PAGE)
1159             {
1160                 size_t size = binsize[bin];
1161                 size_t bit_stride = size / 16;
1162                 size_t bit_base = pn * (PAGESIZE / 16);
1163                 size_t bit_top = bit_base + (PAGESIZE / 16);
1164                 byte*  p;
1165
1166                 bit_i = bit_base;
1167                 for (; bit_i < bit_top; bit_i += bit_stride)
1168                 {
1169                     if (!pool.freebits.test(bit_i))
1170                         goto Lnotfree;
1171                 }
1172                 pool.pagetable[pn] = B_FREE;
1173                 pool.freebits.set_group(bit_base, PAGESIZE / 16);
1174                 recoveredpages++;
1175                 gc.free_mem += PAGESIZE;
1176                 continue;
1177
1178              Lnotfree:
1179                 p = pool.baseAddr + pn * PAGESIZE;
1180                 for (u = 0; u < PAGESIZE; u += size)
1181                 {
1182                     bit_i = bit_base + u / 16;
1183                     if (pool.freebits.test(bit_i))
1184                     {
1185                         assert ((p+u) >= pool.baseAddr);
1186                         assert ((p+u) < pool.topAddr);
1187                         List* list = cast(List*) (p + u);
1188                         // avoid unnecesary writes (it really saves time)
1189                         if (list.next != gc.free_list[bin])
1190                             list.next = gc.free_list[bin];
1191                         if (list.pool != pool)
1192                             list.pool = pool;
1193                         gc.free_list[bin] = list;
1194                         gc.free_mem += binsize[bin];
1195                     }
1196                 }
1197             }
1198         }
1199     }
1200
1201     debug(COLLECT_PRINTF) printf("recovered pages = %d\n", recoveredpages);
1202     debug(COLLECT_PRINTF) printf("\tfree'd %u bytes, %u pages from %u pools\n", freed, freedpages, gc.pools.length);
1203
1204     return freedpages + recoveredpages;
1205 }
1206
1207
1208 /**
1209  *
1210  */
1211 uint getAttr(Pool* pool, size_t bit_i)
1212 in
1213 {
1214     assert( pool );
1215 }
1216 body
1217 {
1218     uint attrs;
1219     if (pool.finals.test(bit_i))
1220         attrs |= BlkAttr.FINALIZE;
1221     if (pool.noscan.test(bit_i))
1222         attrs |= BlkAttr.NO_SCAN;
1223 //        if (pool.nomove.test(bit_i))
1224 //            attrs |= BlkAttr.NO_MOVE;
1225     return attrs;
1226 }
1227
1228
1229 /**
1230  *
1231  */
1232 void setAttr(Pool* pool, size_t bit_i, uint mask)
1233 in
1234 {
1235     assert( pool );
1236 }
1237 body
1238 {
1239     if (mask & BlkAttr.FINALIZE)
1240     {
1241         pool.finals.set(bit_i);
1242     }
1243     if (mask & BlkAttr.NO_SCAN)
1244     {
1245         pool.noscan.set(bit_i);
1246     }
1247 //        if (mask & BlkAttr.NO_MOVE)
1248 //        {
1249 //            if (!pool.nomove.nbits)
1250 //                pool.nomove.alloc(pool.mark.nbits);
1251 //            pool.nomove.set(bit_i);
1252 //        }
1253 }
1254
1255
1256 /**
1257  *
1258  */
1259 void clrAttr(Pool* pool, size_t bit_i, uint mask)
1260 in
1261 {
1262     assert( pool );
1263 }
1264 body
1265 {
1266     if (mask & BlkAttr.FINALIZE)
1267         pool.finals.clear(bit_i);
1268     if (mask & BlkAttr.NO_SCAN)
1269         pool.noscan.clear(bit_i);
1270 //        if (mask & BlkAttr.NO_MOVE && pool.nomove.nbits)
1271 //            pool.nomove.clear(bit_i);
1272 }
1273
1274
1275 void disable_fork()
1276 {
1277     // we have to disable all options that assume fork is enabled
1278     opts.options.fork = false;
1279     opts.options.eager_alloc = false;
1280     opts.options.early_collect = false;
1281 }
1282
1283
1284 void initialize()
1285 {
1286     int dummy;
1287     gc.stack_bottom = cast(char*)&dummy;
1288     opts.parse(cstdlib.getenv("D_GC_OPTS"));
1289     // If we are going to fork, make sure we have the needed OS support
1290     if (opts.options.fork)
1291         opts.options.fork = os.HAVE_SHARED && os.HAVE_FORK;
1292     // Disable fork()-related options if we don't have it
1293     if (!opts.options.fork)
1294         disable_fork();
1295     gc.lock = GCLock.classinfo;
1296     gc.inited = 1;
1297     setStackBottom(rt_stackBottom());
1298     gc.stats = Stats(gc);
1299     if (opts.options.prealloc_npools) {
1300         size_t pages = round_up(opts.options.prealloc_psize, PAGESIZE);
1301         for (size_t i = 0; i < opts.options.prealloc_npools; ++i)
1302             newPool(pages);
1303     }
1304 }
1305
1306
1307 // Launch a parallel collection if we don't have enough free memory available
1308 // (we have less than min_free% of the total heap free).
1309 void early_collect()
1310 {
1311     if (!opts.options.early_collect || collect_in_progress())
1312         return;
1313     double percent_free = gc.free_mem * 100.0 / gc.total_mem;
1314     if (percent_free < opts.options.min_free)
1315         fullcollectshell(true);
1316 }
1317
1318
1319 //
1320 //
1321 //
1322 private void *malloc(size_t size, uint attrs, size_t* pm_bitmask)
1323 {
1324     assert(size != 0);
1325
1326     gc.stats.malloc_started(size, attrs, pm_bitmask);
1327     scope (exit)
1328         gc.stats.malloc_finished(p);
1329
1330     void *p = null;
1331     Bins bin;
1332
1333     if (opts.options.sentinel)
1334         size += SENTINEL_EXTRA;
1335
1336     bool has_pm = has_pointermap(attrs);
1337     if (has_pm)
1338         size += size_t.sizeof;
1339
1340     // Compute size bin
1341     // Cache previous binsize lookup - Dave Fladebo.
1342     static size_t lastsize = -1;
1343     static Bins lastbin;
1344     if (size == lastsize)
1345         bin = lastbin;
1346     else
1347     {
1348         bin = findBin(size);
1349         lastsize = size;
1350         lastbin = bin;
1351     }
1352
1353     Pool* pool = void;
1354     size_t bit_i = void;
1355     size_t capacity = void; // to figure out where to store the bitmask
1356     bool collected = false;
1357     if (bin < B_PAGE)
1358     {
1359         p = gc.free_list[bin];
1360         if (p is null)
1361         {
1362             if (!allocPage(bin) && !gc.disabled)   // try to find a new page
1363             {
1364                 if (!thread_needLock())
1365                 {
1366                     /* Then we haven't locked it yet. Be sure
1367                      * and gc.lock for a collection, since a finalizer
1368                      * may start a new thread.
1369                      */
1370                     synchronized (gc.lock)
1371                     {
1372                         fullcollectshell();
1373                     }
1374                 }
1375                 else if (!fullcollectshell())       // collect to find a new page
1376                 {
1377                     //newPool(1);
1378                 }
1379                 collected = true;
1380             }
1381             if (!gc.free_list[bin] && !allocPage(bin))
1382             {
1383                 newPool(1);         // allocate new pool to find a new page
1384                 // TODO: hint allocPage() to use the pool we just created
1385                 int result = allocPage(bin);
1386                 if (!result)
1387                     onOutOfMemoryError();
1388             }
1389             p = gc.free_list[bin];
1390         }
1391         capacity = binsize[bin];
1392
1393         // Return next item from free list
1394         List* list = cast(List*) p;
1395         assert ((cast(byte*)list) >= list.pool.baseAddr);
1396         assert ((cast(byte*)list) < list.pool.topAddr);
1397         gc.free_list[bin] = list.next;
1398         pool = list.pool;
1399         bit_i = (p - pool.baseAddr) / 16;
1400         assert (pool.freebits.test(bit_i));
1401         pool.freebits.clear(bit_i);
1402         if (!(attrs & BlkAttr.NO_SCAN))
1403             memset(p + size, 0, capacity - size);
1404         if (opts.options.mem_stomp)
1405             memset(p, 0xF0, size);
1406     }
1407     else
1408     {
1409         size_t pn;
1410         size_t npages = round_up(size, PAGESIZE);
1411         p = bigAlloc(npages, pool, &pn, &collected);
1412         if (!p)
1413             onOutOfMemoryError();
1414         assert (pool !is null);
1415
1416         capacity = npages * PAGESIZE;
1417         bit_i = pn * (PAGESIZE / 16);
1418         pool.freebits.clear(bit_i);
1419         pool.pagetable[pn] = B_PAGE;
1420         if (npages > 1)
1421             memset(&pool.pagetable[pn + 1], B_PAGEPLUS, npages - 1);
1422         p = pool.baseAddr + pn * PAGESIZE;
1423         memset(cast(char *)p + size, 0, npages * PAGESIZE - size);
1424         if (opts.options.mem_stomp)
1425             memset(p, 0xF1, size);
1426
1427     }
1428
1429     // Store the bit mask AFTER SENTINEL_POST
1430     // TODO: store it BEFORE, so the bitmask is protected too
1431     if (has_pm) {
1432         auto end_of_blk = cast(size_t**)(p + capacity - size_t.sizeof);
1433         *end_of_blk = pm_bitmask;
1434         size -= size_t.sizeof;
1435     }
1436
1437     if (opts.options.sentinel) {
1438         size -= SENTINEL_EXTRA;
1439         p = sentinel_add(p);
1440         sentinel_init(p, size);
1441     }
1442
1443     if (attrs) {
1444         setAttr(pool, bit_i, attrs);
1445         assert (bin >= B_PAGE || !pool.freebits.test(bit_i));
1446     }
1447
1448     gc.free_mem -= capacity;
1449     if (collected) {
1450         // If there is not enough free memory (after a collection), allocate
1451         // a new pool big enough to have at least the min_free% of the total
1452         // heap free. If the collection left too much free memory, try to free
1453         // some empty pools.
1454         double percent_free = gc.free_mem * 100.0 / gc.total_mem;
1455         if (percent_free < opts.options.min_free) {
1456             auto pool_size = gc.total_mem * 1.0 / opts.options.min_free
1457                     - gc.free_mem;
1458             newPool(round_up(cast(size_t)pool_size, PAGESIZE));
1459         }
1460         else
1461             minimize(false);
1462     }
1463     else
1464         early_collect();
1465
1466     return p;
1467 }
1468
1469
1470 //
1471 //
1472 //
1473 private void *calloc(size_t size, uint attrs, size_t* pm_bitmask)
1474 {
1475     assert(size != 0);
1476
1477     void *p = malloc(size, attrs, pm_bitmask);
1478     memset(p, 0, size);
1479     return p;
1480 }
1481
1482
1483 //
1484 //
1485 //
1486 private void *realloc(void *p, size_t size, uint attrs,
1487         size_t* pm_bitmask)
1488 {
1489     if (!size) {
1490         if (p)
1491             free(p);
1492         return null;
1493     }
1494
1495     if (p is null)
1496         return malloc(size, attrs, pm_bitmask);
1497
1498     Pool* pool = findPool(p);
1499     if (pool is null)
1500         return null;
1501
1502     // Set or retrieve attributes as appropriate
1503     auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
1504     if (attrs) {
1505         clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
1506         setAttr(pool, bit_i, attrs);
1507     }
1508     else
1509         attrs = getAttr(pool, bit_i);
1510
1511     void* blk_base_addr = pool.findBase(p);
1512     size_t blk_size = pool.findSize(p);
1513     bool has_pm = has_pointermap(attrs);
1514     size_t pm_bitmask_size = 0;
1515     if (has_pm) {
1516         pm_bitmask_size = size_t.sizeof;
1517         // Retrieve pointer map bit mask if appropriate
1518         if (pm_bitmask is null) {
1519             auto end_of_blk = cast(size_t**)(
1520                     blk_base_addr + blk_size - size_t.sizeof);
1521             pm_bitmask = *end_of_blk;
1522         }
1523     }
1524
1525     if (opts.options.sentinel) {
1526         sentinel_Invariant(p);
1527         size_t sentinel_stored_size = *sentinel_size(p);
1528         if (sentinel_stored_size != size) {
1529             void* p2 = malloc(size, attrs, pm_bitmask);
1530             if (sentinel_stored_size < size)
1531                 size = sentinel_stored_size;
1532             cstring.memcpy(p2, p, size);
1533             p = p2;
1534         }
1535         return p;
1536     }
1537
1538     size += pm_bitmask_size;
1539     if (blk_size >= PAGESIZE && size >= PAGESIZE) {
1540         auto psz = blk_size / PAGESIZE;
1541         auto newsz = round_up(size, PAGESIZE);
1542         if (newsz == psz)
1543             return p;
1544
1545         auto pagenum = (p - pool.baseAddr) / PAGESIZE;
1546
1547         if (newsz < psz) {
1548             // Shrink in place
1549             if (opts.options.mem_stomp)
1550                 memset(p + size - pm_bitmask_size, 0xF2,
1551                         blk_size - size - pm_bitmask_size);
1552             pool.freePages(pagenum + newsz, psz - newsz);
1553             auto new_blk_size = (PAGESIZE * newsz);
1554             gc.free_mem += blk_size - new_blk_size;
1555             // update the size cache, assuming that is very likely the
1556             // size of this block will be queried in the near future
1557             pool.update_cache(p, new_blk_size);
1558             if (has_pm) {
1559                 auto end_of_blk = cast(size_t**)(blk_base_addr +
1560                         new_blk_size - pm_bitmask_size);
1561                 *end_of_blk = pm_bitmask;
1562             }
1563             return p;
1564         }
1565
1566         if (pagenum + newsz <= pool.npages) {
1567             // Attempt to expand in place
1568             for (size_t i = pagenum + psz; 1;) {
1569                 if (i == pagenum + newsz) {
1570                     if (opts.options.mem_stomp)
1571                         memset(p + blk_size - pm_bitmask_size, 0xF0,
1572                                 size - blk_size - pm_bitmask_size);
1573                     memset(pool.pagetable + pagenum + psz, B_PAGEPLUS,
1574                             newsz - psz);
1575                     auto new_blk_size = (PAGESIZE * newsz);
1576                     gc.free_mem -= new_blk_size - blk_size;
1577                     // update the size cache, assuming that is very
1578                     // likely the size of this block will be queried in
1579                     // the near future
1580                     pool.update_cache(p, new_blk_size);
1581                     if (has_pm) {
1582                         auto end_of_blk = cast(size_t**)(
1583                                 blk_base_addr + new_blk_size - pm_bitmask_size);
1584                         *end_of_blk = pm_bitmask;
1585                     }
1586                     early_collect();
1587                     return p;
1588                 }
1589                 if (i == pool.npages)
1590                     break;
1591                 if (pool.pagetable[i] != B_FREE)
1592                     break;
1593                 i++;
1594             }
1595         }
1596     }
1597
1598     // if new size is bigger or less than half
1599     if (blk_size < size || blk_size > size * 2) {
1600         size -= pm_bitmask_size;
1601         blk_size -= pm_bitmask_size;
1602         void* p2 = malloc(size, attrs, pm_bitmask);
1603         if (blk_size < size)
1604             size = blk_size;
1605         cstring.memcpy(p2, p, size);
1606         p = p2;
1607     }
1608
1609     return p;
1610 }
1611
1612
1613 /**
1614  * Attempt to in-place enlarge the memory block pointed to by p by at least
1615  * min_size beyond its current capacity, up to a maximum of max_size.  This
1616  * does not attempt to move the memory block (like realloc() does).
1617  *
1618  * Returns:
1619  *  0 if could not extend p,
1620  *  total size of entire memory block if successful.
1621  */
1622 private size_t extend(void* p, size_t minsize, size_t maxsize)
1623 in
1624 {
1625     assert( minsize <= maxsize );
1626 }
1627 body
1628 {
1629     if (opts.options.sentinel)
1630         return 0;
1631
1632     Pool* pool = findPool(p);
1633     if (pool is null)
1634         return 0;
1635
1636     // Retrieve attributes
1637     auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
1638     uint attrs = getAttr(pool, bit_i);
1639
1640     void* blk_base_addr = pool.findBase(p);
1641     size_t blk_size = pool.findSize(p);
1642     bool has_pm = has_pointermap(attrs);
1643     size_t* pm_bitmask = null;
1644     size_t pm_bitmask_size = 0;
1645     if (has_pm) {
1646         pm_bitmask_size = size_t.sizeof;
1647         // Retrieve pointer map bit mask
1648         auto end_of_blk = cast(size_t**)(blk_base_addr +
1649                 blk_size - size_t.sizeof);
1650         pm_bitmask = *end_of_blk;
1651
1652         minsize += size_t.sizeof;
1653         maxsize += size_t.sizeof;
1654     }
1655
1656     if (blk_size < PAGESIZE)
1657         return 0; // cannot extend buckets
1658
1659     auto psz = blk_size / PAGESIZE;
1660     auto minsz = round_up(minsize, PAGESIZE);
1661     auto maxsz = round_up(maxsize, PAGESIZE);
1662
1663     auto pagenum = (p - pool.baseAddr) / PAGESIZE;
1664
1665     size_t sz;
1666     for (sz = 0; sz < maxsz; sz++)
1667     {
1668         auto i = pagenum + psz + sz;
1669         if (i == pool.npages)
1670             break;
1671         if (pool.pagetable[i] != B_FREE)
1672         {
1673             if (sz < minsz)
1674                 return 0;
1675             break;
1676         }
1677     }
1678     if (sz < minsz)
1679         return 0;
1680
1681     size_t new_size = (psz + sz) * PAGESIZE;
1682
1683     if (opts.options.mem_stomp)
1684         memset(p + blk_size - pm_bitmask_size, 0xF0,
1685                 new_size - blk_size - pm_bitmask_size);
1686     memset(pool.pagetable + pagenum + psz, B_PAGEPLUS, sz);
1687     gc.p_cache = null;
1688     gc.size_cache = 0;
1689     gc.free_mem -= new_size - blk_size;
1690     // update the size cache, assuming that is very likely the size of this
1691     // block will be queried in the near future
1692     pool.update_cache(p, new_size);
1693
1694     if (has_pm) {
1695         new_size -= size_t.sizeof;
1696         auto end_of_blk = cast(size_t**)(blk_base_addr + new_size);
1697         *end_of_blk = pm_bitmask;
1698     }
1699
1700     early_collect();
1701
1702     return new_size;
1703 }
1704
1705
1706 //
1707 //
1708 //
1709 private void free(void *p)
1710 {
1711     assert (p);
1712
1713     Pool*  pool;
1714     size_t pagenum;
1715     Bins   bin;
1716     size_t bit_i;
1717
1718     // Find which page it is in
1719     pool = findPool(p);
1720     if (!pool)                              // if not one of ours
1721         return;                             // ignore
1722     if (opts.options.sentinel) {
1723         sentinel_Invariant(p);
1724         p = sentinel_sub(p);
1725     }
1726     pagenum = cast(size_t)(p - pool.baseAddr) / PAGESIZE;
1727     bit_i = cast(size_t)(p - pool.baseAddr) / 16;
1728     clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
1729
1730     bin = cast(Bins)pool.pagetable[pagenum];
1731     if (bin == B_PAGE)              // if large alloc
1732     {
1733         // Free pages
1734         size_t npages = 1;
1735         size_t n = pagenum;
1736         pool.freebits.set_group(bit_i, PAGESIZE / 16);
1737         while (++n < pool.npages && pool.pagetable[n] == B_PAGEPLUS)
1738             npages++;
1739         size_t size = npages * PAGESIZE;
1740         if (opts.options.mem_stomp)
1741             memset(p, 0xF2, size);
1742         pool.freePages(pagenum, npages);
1743         gc.free_mem += size;
1744         // just in case we were caching this pointer
1745         pool.clear_cache(p);
1746     }
1747     else
1748     {
1749         // Add to free list
1750         List* list = cast(List*) p;
1751
1752         if (opts.options.mem_stomp)
1753             memset(p, 0xF2, binsize[bin]);
1754
1755         list.next = gc.free_list[bin];
1756         list.pool = pool;
1757         gc.free_list[bin] = list;
1758         pool.freebits.set(bit_i);
1759         gc.free_mem += binsize[bin];
1760     }
1761     double percent_free = gc.free_mem * 100.0 / gc.total_mem;
1762     if (percent_free > opts.options.min_free)
1763         minimize(false);
1764 }
1765
1766
1767 /**
1768  * Determine the allocated size of pointer p.  If p is an interior pointer
1769  * or not a gc allocated pointer, return 0.
1770  */
1771 private size_t sizeOf(void *p)
1772 {
1773     assert (p);
1774
1775     if (opts.options.sentinel)
1776         p = sentinel_sub(p);
1777
1778     Pool* pool = findPool(p);
1779     if (pool is null)
1780         return 0;
1781
1782     auto biti = cast(size_t)(p - pool.baseAddr) / 16;
1783     uint attrs = getAttr(pool, biti);
1784
1785     size_t size = pool.findSize(p);
1786     size_t pm_bitmask_size = 0;
1787     if (has_pointermap(attrs))
1788         pm_bitmask_size = size_t.sizeof;
1789
1790     if (opts.options.sentinel) {
1791         // Check for interior pointer
1792         // This depends on:
1793         // 1) size is a power of 2 for less than PAGESIZE values
1794         // 2) base of memory pool is aligned on PAGESIZE boundary
1795         if (cast(size_t)p & (size - 1) & (PAGESIZE - 1))
1796             return 0;
1797         return size - SENTINEL_EXTRA - pm_bitmask_size;
1798     }
1799     else {
1800         if (p == gc.p_cache)
1801             return gc.size_cache;
1802
1803         // Check for interior pointer
1804         // This depends on:
1805         // 1) size is a power of 2 for less than PAGESIZE values
1806         // 2) base of memory pool is aligned on PAGESIZE boundary
1807         if (cast(size_t)p & (size - 1) & (PAGESIZE - 1))
1808             return 0;
1809
1810         gc.p_cache = p;
1811         gc.size_cache = size - pm_bitmask_size;
1812
1813         return gc.size_cache;
1814     }
1815 }
1816
1817
1818 /**
1819  * Verify that pointer p:
1820  *  1) belongs to this memory pool
1821  *  2) points to the start of an allocated piece of memory
1822  *  3) is not on a free list
1823  */
1824 private void checkNoSync(void *p)
1825 {
1826     assert(p);
1827
1828     if (opts.options.sentinel)
1829         sentinel_Invariant(p);
1830     debug (PTRCHECK)
1831     {
1832         Pool*  pool;
1833         size_t pagenum;
1834         Bins   bin;
1835         size_t size;
1836
1837         if (opts.options.sentinel)
1838             p = sentinel_sub(p);
1839         pool = findPool(p);
1840         assert(pool);
1841         pagenum = cast(size_t)(p - pool.baseAddr) / PAGESIZE;
1842         bin = cast(Bins)pool.pagetable[pagenum];
1843         assert(bin <= B_PAGE);
1844         size = binsize[bin];
1845         assert((cast(size_t)p & (size - 1)) == 0);
1846
1847         debug (PTRCHECK2)
1848         {
1849             if (bin < B_PAGE)
1850             {
1851                 // Check that p is not on a free list
1852                 for (List* list = gc.free_list[bin]; list; list = list.next)
1853                 {
1854                     assert(cast(void*)list != p);
1855                 }
1856             }
1857         }
1858     }
1859 }
1860
1861
1862 //
1863 //
1864 //
1865 private void setStackBottom(void *p)
1866 {
1867     version (STACKGROWSDOWN)
1868     {
1869         //p = (void *)((uint *)p + 4);
1870         if (p > gc.stack_bottom)
1871         {
1872             gc.stack_bottom = p;
1873         }
1874     }
1875     else
1876     {
1877         //p = (void *)((uint *)p - 4);
1878         if (p < gc.stack_bottom)
1879         {
1880             gc.stack_bottom = cast(char*)p;
1881         }
1882     }
1883 }
1884
1885
1886 /**
1887  * Retrieve statistics about garbage collection.
1888  * Useful for debugging and tuning.
1889  */
1890 private GCStats getStats()
1891 {
1892     GCStats stats;
1893     size_t psize = 0;
1894     size_t usize = 0;
1895     size_t flsize = 0;
1896
1897     size_t n;
1898     size_t bsize = 0;
1899
1900     for (n = 0; n < gc.pools.length; n++)
1901     {
1902         Pool* pool = gc.pools[n];
1903         psize += pool.npages * PAGESIZE;
1904         for (size_t j = 0; j < pool.npages; j++)
1905         {
1906             Bins bin = cast(Bins)pool.pagetable[j];
1907             if (bin == B_FREE)
1908                 stats.freeblocks++;
1909             else if (bin == B_PAGE)
1910                 stats.pageblocks++;
1911             else if (bin < B_PAGE)
1912                 bsize += PAGESIZE;
1913         }
1914     }
1915
1916     for (n = 0; n < B_PAGE; n++)
1917     {
1918         for (List* list = gc.free_list[n]; list; list = list.next)
1919             flsize += binsize[n];
1920     }
1921
1922     usize = bsize - flsize;
1923
1924     stats.poolsize = psize;
1925     stats.usedsize = bsize - flsize;
1926     stats.freelistsize = flsize;
1927     return stats;
1928 }
1929
1930 /******************* weak-reference support *********************/
1931
1932 private struct WeakPointer
1933 {
1934     Object reference;
1935
1936     void ondestroy(Object r)
1937     {
1938         assert(r is reference);
1939         // lock for memory consistency (parallel readers)
1940         // also ensures that weakpointerDestroy can be called while another
1941         // thread is freeing the reference with "delete"
1942         return locked!(void, () {
1943             reference = null;
1944         })();
1945     }
1946 }
1947
1948 /**
1949  * Create a weak pointer to the given object.
1950  * Returns a pointer to an opaque struct allocated in C memory.
1951  */
1952 void* weakpointerCreate( Object r )
1953 {
1954     if (r)
1955     {
1956         // must be allocated in C memory
1957         // 1. to hide the reference from the GC
1958         // 2. the GC doesn't scan delegates added by rt_attachDisposeEvent
1959         //    for references
1960         auto wp = cast(WeakPointer*)(cstdlib.malloc(WeakPointer.sizeof));
1961         if (!wp)
1962             onOutOfMemoryError();
1963         wp.reference = r;
1964         rt_attachDisposeEvent(r, &wp.ondestroy);
1965         return wp;
1966     }
1967     return null;
1968 }
1969
1970 /**
1971  * Destroy a weak pointer returned by weakpointerCreate().
1972  * If null is passed, nothing happens.
1973  */
1974 void weakpointerDestroy( void* p )
1975 {
1976     if (p)
1977     {
1978         auto wp = cast(WeakPointer*)p;
1979         // must be extra careful about the GC or parallel threads
1980         // finalizing the reference at the same time
1981         return locked!(void, () {
1982             if (wp.reference)
1983                 rt_detachDisposeEvent(wp.reference, &wp.ondestroy);
1984         })();
1985         cstdlib.free(wp);
1986     }
1987 }
1988
1989 /**
1990  * Query a weak pointer and return either the object passed to
1991  * weakpointerCreate, or null if it was free'd in the meantime.
1992  * If null is passed, null is returned.
1993  */
1994 Object weakpointerGet( void* p )
1995 {
1996     if (p)
1997     {
1998         // NOTE: could avoid the lock by using Fawzi style GC counters but
1999         // that'd require core.sync.Atomic and lots of care about memory
2000         // consistency it's an optional optimization see
2001         // http://dsource.org/projects/tango/browser/trunk/user/tango/core/Lifetime.d?rev=5100#L158
2002         return locked!(Object, () {
2003             return (cast(WeakPointer*)p).reference;
2004         })();
2005         }
2006 }
2007
2008
2009 /* ============================ Pool  =============================== */
2010
2011
2012 struct Pool
2013 {
2014     byte* baseAddr;
2015     byte* topAddr;
2016     GCBits mark;     // entries already scanned, or should not be scanned
2017     GCBits scan;     // entries that need to be scanned
2018     GCBits freebits; // entries that are on the free list
2019     GCBits finals;   // entries that need finalizer run on them
2020     GCBits noscan;   // entries that should not be scanned
2021
2022     size_t npages;
2023     ubyte* pagetable;
2024
2025     /// Cache for findSize()
2026     size_t cached_size;
2027     void* cached_ptr;
2028
2029     void clear_cache(void* ptr = null)
2030     {
2031         if (ptr is null || ptr is this.cached_ptr) {
2032             this.cached_ptr = null;
2033             this.cached_size = 0;
2034         }
2035     }
2036
2037     void update_cache(void* ptr, size_t size)
2038     {
2039         this.cached_ptr = ptr;
2040         this.cached_size = size;
2041     }
2042
2043     void initialize(size_t npages)
2044     {
2045         size_t poolsize = npages * PAGESIZE;
2046         assert(poolsize >= POOLSIZE);
2047         baseAddr = cast(byte *) os.alloc(poolsize);
2048
2049         // Some of the code depends on page alignment of memory pools
2050         assert((cast(size_t)baseAddr & (PAGESIZE - 1)) == 0);
2051
2052         if (!baseAddr)
2053         {
2054             npages = 0;
2055             poolsize = 0;
2056         }
2057         topAddr = baseAddr + poolsize;
2058
2059         size_t nbits = cast(size_t)poolsize / 16;
2060
2061         // if the GC will run in parallel in a fork()ed process, we need to
2062         // share the mark bits
2063         os.Vis vis = os.Vis.PRIV;
2064         if (opts.options.fork)
2065             vis = os.Vis.SHARED;
2066         mark.alloc(nbits, vis); // shared between mark and sweep
2067         freebits.alloc(nbits); // not used by the mark phase
2068         scan.alloc(nbits); // only used in the mark phase
2069         finals.alloc(nbits); // not used by the mark phase
2070         noscan.alloc(nbits); // mark phase *MUST* have a snapshot
2071
2072         // all is free when we start
2073         freebits.set_all();
2074
2075         // avoid accidental sweeping of new pools while using eager allocation
2076         if (collect_in_progress())
2077             mark.set_all();
2078
2079         pagetable = cast(ubyte*) cstdlib.malloc(npages);
2080         if (!pagetable)
2081             onOutOfMemoryError();
2082         memset(pagetable, B_FREE, npages);
2083
2084         this.npages = npages;
2085     }
2086
2087
2088     void Dtor()
2089     {
2090         if (baseAddr)
2091         {
2092             int result;
2093
2094             if (npages)
2095             {
2096                 result = os.dealloc(baseAddr, npages * PAGESIZE);
2097                 assert(result);
2098                 npages = 0;
2099             }
2100
2101             baseAddr = null;
2102             topAddr = null;
2103         }
2104         // See Gcx.Dtor() for the rationale of the null check.
2105         if (pagetable)
2106             cstdlib.free(pagetable);
2107
2108         os.Vis vis = os.Vis.PRIV;
2109         if (opts.options.fork)
2110             vis = os.Vis.SHARED;
2111         mark.Dtor(vis);
2112         freebits.Dtor();
2113         scan.Dtor();
2114         finals.Dtor();
2115         noscan.Dtor();
2116     }
2117
2118
2119     bool Invariant()
2120     {
2121         return true;
2122     }
2123
2124
2125     invariant
2126     {
2127         //mark.Invariant();
2128         //scan.Invariant();
2129         //freebits.Invariant();
2130         //finals.Invariant();
2131         //noscan.Invariant();
2132
2133         if (baseAddr)
2134         {
2135             //if (baseAddr + npages * PAGESIZE != topAddr)
2136                 //printf("baseAddr = %p, npages = %d, topAddr = %p\n", baseAddr, npages, topAddr);
2137             assert(baseAddr + npages * PAGESIZE == topAddr);
2138         }
2139
2140         for (size_t i = 0; i < npages; i++)
2141         {
2142             Bins bin = cast(Bins)pagetable[i];
2143             assert(bin < B_MAX);
2144         }
2145     }
2146
2147
2148     /**
2149      * Allocate n pages from Pool.
2150      * Returns OPFAIL on failure.
2151      */
2152     size_t allocPages(size_t n)
2153     {
2154         size_t i;
2155         size_t n2;
2156
2157         n2 = n;
2158         for (i = 0; i < npages; i++)
2159         {
2160             if (pagetable[i] == B_FREE)
2161             {
2162                 if (--n2 == 0)
2163                     return i - n + 1;
2164             }
2165             else
2166                 n2 = n;
2167         }
2168         return OPFAIL;
2169     }
2170
2171
2172     /**
2173      * Free npages pages starting with pagenum.
2174      */
2175     void freePages(size_t pagenum, size_t npages)
2176     {
2177         memset(&pagetable[pagenum], B_FREE, npages);
2178     }
2179
2180
2181     /**
2182      * Find base address of block containing pointer p.
2183      * Returns null if the pointer doesn't belong to this pool
2184      */
2185     void* findBase(void *p)
2186     {
2187         size_t offset = cast(size_t)(p - this.baseAddr);
2188         size_t pagenum = offset / PAGESIZE;
2189         Bins bin = cast(Bins)this.pagetable[pagenum];
2190         // Adjust bit to be at start of allocated memory block
2191         if (bin <= B_PAGE)
2192             return this.baseAddr + (offset & notbinsize[bin]);
2193         if (bin == B_PAGEPLUS) {
2194             do {
2195                 --pagenum, offset -= PAGESIZE;
2196             } while (cast(Bins)this.pagetable[pagenum] == B_PAGEPLUS);
2197             return this.baseAddr + (offset & (offset.max ^ (PAGESIZE-1)));
2198         }
2199         // we are in a B_FREE page
2200         return null;
2201     }
2202
2203
2204     /**
2205      * Find size of pointer p.
2206      * Returns 0 if p doesn't belong to this pool if if it's block size is less
2207      * than a PAGE.
2208      */
2209     size_t findSize(void *p)
2210     {
2211         size_t pagenum = cast(size_t)(p - this.baseAddr) / PAGESIZE;
2212         Bins bin = cast(Bins)this.pagetable[pagenum];
2213         if (bin != B_PAGE)
2214             return binsize[bin];
2215         if (this.cached_ptr == p)
2216             return this.cached_size;
2217         size_t i = pagenum + 1;
2218         for (; i < this.npages; i++)
2219             if (this.pagetable[i] != B_PAGEPLUS)
2220                 break;
2221         this.cached_ptr = p;
2222         this.cached_size = (i - pagenum) * PAGESIZE;
2223         return this.cached_size;
2224     }
2225
2226
2227     /**
2228      * Used for sorting pools
2229      */
2230     int opCmp(in Pool other)
2231     {
2232         if (baseAddr < other.baseAddr)
2233             return -1;
2234         else
2235         return cast(int)(baseAddr > other.baseAddr);
2236     }
2237 }
2238
2239
2240 /* ============================ SENTINEL =============================== */
2241
2242
2243 const size_t SENTINEL_PRE = cast(size_t) 0xF4F4F4F4F4F4F4F4UL; // 32 or 64 bits
2244 const ubyte SENTINEL_POST = 0xF5;           // 8 bits
2245 const uint SENTINEL_EXTRA = 2 * size_t.sizeof + 1;
2246
2247
2248 size_t* sentinel_size(void *p)  { return &(cast(size_t *)p)[-2]; }
2249 size_t* sentinel_pre(void *p)   { return &(cast(size_t *)p)[-1]; }
2250 ubyte* sentinel_post(void *p) { return &(cast(ubyte *)p)[*sentinel_size(p)]; }
2251
2252
2253 void sentinel_init(void *p, size_t size)
2254 {
2255     *sentinel_size(p) = size;
2256     *sentinel_pre(p) = SENTINEL_PRE;
2257     *sentinel_post(p) = SENTINEL_POST;
2258 }
2259
2260
2261 void sentinel_Invariant(void *p)
2262 {
2263     if (*sentinel_pre(p) != SENTINEL_PRE ||
2264             *sentinel_post(p) != SENTINEL_POST)
2265         cstdlib.abort();
2266 }
2267
2268
2269 void *sentinel_add(void *p)
2270 {
2271     return p + 2 * size_t.sizeof;
2272 }
2273
2274
2275 void *sentinel_sub(void *p)
2276 {
2277     return p - 2 * size_t.sizeof;
2278 }
2279
2280
2281
2282 /* ============================ C Public Interface ======================== */
2283
2284
2285 private int _termCleanupLevel=1;
2286
2287 extern (C):
2288
2289 /// sets the cleanup level done by gc
2290 /// 0: none
2291 /// 1: fullCollect
2292 /// 2: fullCollect ignoring stack roots (might crash daemonThreads)
2293 /// result !=0 if the value was invalid
2294 int gc_setTermCleanupLevel(int cLevel)
2295 {
2296     if (cLevel<0 || cLevel>2) return cLevel;
2297     _termCleanupLevel=cLevel;
2298     return 0;
2299 }
2300
2301 /// returns the cleanup level done by gc
2302 int gc_getTermCleanupLevel()
2303 {
2304     return _termCleanupLevel;
2305 }
2306
2307 void gc_init()
2308 {
2309     scope (exit) assert (Invariant());
2310     gc = cast(GC*) cstdlib.calloc(1, GC.sizeof);
2311     *gc = GC.init;
2312     initialize();
2313     version (DigitalMars) version(OSX) {
2314         _d_osx_image_init();
2315     }
2316     // NOTE: The GC must initialize the thread library
2317     //       before its first collection.
2318     thread_init();
2319 }
2320
2321 void gc_term()
2322 {
2323     assert (Invariant());
2324     if (_termCleanupLevel<1) {
2325         // no cleanup
2326     } else if (_termCleanupLevel==2){
2327         // a more complete cleanup
2328         // NOTE: There may be daemons threads still running when this routine is
2329         //       called.  If so, cleaning memory out from under then is a good
2330         //       way to make them crash horribly.
2331         //       Often this probably doesn't matter much since the app is
2332         //       supposed to be shutting down anyway, but for example tests might
2333         //       crash (and be considerd failed even if the test was ok).
2334         //       thus this is not the default and should be enabled by
2335         //       I'm disabling cleanup for now until I can think about it some
2336         //       more.
2337         //
2338         // not really a 'collect all' -- still scans static data area, roots,
2339         // and ranges.
2340         return locked!(void, () {
2341             gc.no_stack++;
2342             fullcollectshell();
2343             gc.no_stack--;
2344         })();
2345     } else {
2346         // default (safe) clenup
2347         return locked!(void, () {
2348             fullcollectshell();
2349         })();
2350     }
2351 }
2352
2353 void gc_enable()
2354 {
2355     return locked!(void, () {
2356         assert (Invariant()); scope (exit) assert (Invariant());
2357         assert (gc.disabled > 0);
2358         gc.disabled--;
2359     })();
2360 }
2361
2362 void gc_disable()
2363 {
2364     return locked!(void, () {
2365         assert (Invariant()); scope (exit) assert (Invariant());
2366         gc.disabled++;
2367     })();
2368 }
2369
2370 void gc_collect()
2371 {
2372     return locked!(void, () {
2373         assert (Invariant()); scope (exit) assert (Invariant());
2374         fullcollectshell();
2375     })();
2376 }
2377
2378
2379 void gc_minimize()
2380 {
2381     return locked!(void, () {
2382         assert (Invariant()); scope (exit) assert (Invariant());
2383         minimize();
2384     })();
2385 }
2386
2387 uint gc_getAttr(void* p)
2388 {
2389     if (p is null)
2390         return 0;
2391     return locked!(uint, () {
2392         assert (Invariant()); scope (exit) assert (Invariant());
2393         Pool* pool = findPool(p);
2394         if (pool is null)
2395             return 0u;
2396         auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
2397         return getAttr(pool, bit_i);
2398     })();
2399 }
2400
2401 uint gc_setAttr(void* p, uint attrs)
2402 {
2403     if (p is null)
2404         return 0;
2405     return locked!(uint, () {
2406         assert (Invariant()); scope (exit) assert (Invariant());
2407         Pool* pool = findPool(p);
2408         if (pool is null)
2409             return 0u;
2410         auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
2411         uint old_attrs = getAttr(pool, bit_i);
2412         setAttr(pool, bit_i, attrs);
2413         return old_attrs;
2414     })();
2415 }
2416
2417 uint gc_clrAttr(void* p, uint attrs)
2418 {
2419     if (p is null)
2420         return 0;
2421     return locked!(uint, () {
2422         assert (Invariant()); scope (exit) assert (Invariant());
2423         Pool* pool = findPool(p);
2424         if (pool is null)
2425             return 0u;
2426         auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
2427         uint old_attrs = getAttr(pool, bit_i);
2428         clrAttr(pool, bit_i, attrs);
2429         return old_attrs;
2430     })();
2431 }
2432
2433 void* gc_malloc(size_t size, uint attrs = 0,
2434         PointerMap ptrmap = PointerMap.init)
2435 {
2436     if (size == 0)
2437         return null;
2438     return locked!(void*, () {
2439         assert (Invariant()); scope (exit) assert (Invariant());
2440         return malloc(size, attrs, ptrmap.bits.ptr);
2441     })();
2442 }
2443
2444 void* gc_calloc(size_t size, uint attrs = 0,
2445         PointerMap ptrmap = PointerMap.init)
2446 {
2447     if (size == 0)
2448         return null;
2449     return locked!(void*, () {
2450         assert (Invariant()); scope (exit) assert (Invariant());
2451         return calloc(size, attrs, ptrmap.bits.ptr);
2452     })();
2453 }
2454
2455 void* gc_realloc(void* p, size_t size, uint attrs = 0,
2456         PointerMap ptrmap = PointerMap.init)
2457 {
2458     return locked!(void*, () {
2459         assert (Invariant()); scope (exit) assert (Invariant());
2460         return realloc(p, size, attrs, ptrmap.bits.ptr);
2461     })();
2462 }
2463
2464 size_t gc_extend(void* p, size_t min_size, size_t max_size)
2465 {
2466     return locked!(size_t, () {
2467         assert (Invariant()); scope (exit) assert (Invariant());
2468         return extend(p, min_size, max_size);
2469     })();
2470 }
2471
2472 size_t gc_reserve(size_t size)
2473 {
2474     if (size == 0)
2475         return 0;
2476     return locked!(size_t, () {
2477         assert (Invariant()); scope (exit) assert (Invariant());
2478         return reserve(size);
2479     })();
2480 }
2481
2482 void gc_free(void* p)
2483 {
2484     if (p is null)
2485         return;
2486     return locked!(void, () {
2487         assert (Invariant()); scope (exit) assert (Invariant());
2488         free(p);
2489     })();
2490 }
2491
2492 void* gc_addrOf(void* p)
2493 {
2494     if (p is null)
2495         return null;
2496     return locked!(void*, () {
2497         assert (Invariant()); scope (exit) assert (Invariant());
2498         Pool* pool = findPool(p);
2499         if (pool is null)
2500             return null;
2501         return pool.findBase(p);
2502     })();
2503 }
2504
2505 size_t gc_sizeOf(void* p)
2506 {
2507     if (p is null)
2508         return 0;
2509     return locked!(size_t, () {
2510         assert (Invariant()); scope (exit) assert (Invariant());
2511         return sizeOf(p);
2512     })();
2513 }
2514
2515 BlkInfo gc_query(void* p)
2516 {
2517     if (p is null)
2518         return BlkInfo.init;
2519     return locked!(BlkInfo, () {
2520         assert (Invariant()); scope (exit) assert (Invariant());
2521         return getInfo(p);
2522     })();
2523 }
2524
2525 // NOTE: This routine is experimental.  The stats or function name may change
2526 //       before it is made officially available.
2527 GCStats gc_stats()
2528 {
2529     return locked!(GCStats, () {
2530         assert (Invariant()); scope (exit) assert (Invariant());
2531         return getStats();
2532     })();
2533 }
2534
2535 void gc_addRoot(void* p)
2536 {
2537     if (p is null)
2538         return;
2539     return locked!(void, () {
2540         assert (Invariant()); scope (exit) assert (Invariant());
2541         if (gc.roots.append(p) is null)
2542             onOutOfMemoryError();
2543     })();
2544 }
2545
2546 void gc_addRange(void* p, size_t size)
2547 {
2548     if (p is null || size == 0)
2549         return;
2550     return locked!(void, () {
2551         assert (Invariant()); scope (exit) assert (Invariant());
2552         if (gc.ranges.append(Range(p, p + size)) is null)
2553             onOutOfMemoryError();
2554     })();
2555 }
2556
2557 void gc_removeRoot(void* p)
2558 {
2559     if (p is null)
2560         return;
2561     return locked!(void, () {
2562         assert (Invariant()); scope (exit) assert (Invariant());
2563         bool r = gc.roots.remove(p);
2564         assert (r);
2565     })();
2566 }
2567
2568 void gc_removeRange(void* p)
2569 {
2570     if (p is null)
2571         return;
2572     return locked!(void, () {
2573         assert (Invariant()); scope (exit) assert (Invariant());
2574         bool r = gc.ranges.remove(Range(p, null));
2575         assert (r);
2576     })();
2577 }
2578
2579 void* gc_weakpointerCreate(Object r)
2580 {
2581     // weakpointers do their own locking
2582     return weakpointerCreate(r);
2583 }
2584
2585 void gc_weakpointerDestroy(void* wp)
2586 {
2587     // weakpointers do their own locking
2588     weakpointerDestroy(wp);
2589 }
2590
2591 Object gc_weakpointerGet(void* wp)
2592 {
2593     // weakpointers do their own locking
2594     return weakpointerGet(wp);
2595 }
2596
2597
2598 // vim: set et sw=4 sts=4 :