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