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