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