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