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