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