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