src/gc/basic/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 module gc.gcx;
  28
  29 // D Programming Language Garbage Collector implementation
  30
  31 /************** Debugging ***************************/
  32
  33 //debug = PRINTF;               // turn on printf's
  34 //debug = COLLECT_PRINTF;       // turn on printf's
  35 //debug = THREADINVARIANT;      // check thread integrity
  36 //debug = LOGGING;              // log allocations / frees
  37 //debug = MEMSTOMP;             // stomp on memory
  38 //debug = SENTINEL;             // add underrun/overrrun protection
  39 //debug = PTRCHECK;             // more pointer checking
  40 //debug = PTRCHECK2;            // thorough but slow pointer checking
  41
  42 /*************** Configuration *********************/
  43
  44 version = STACKGROWSDOWN;       // growing the stack means subtracting from the stack pointer
  45                                 // (use for Intel X86 CPUs)
  46                                 // else growing the stack means adding to the stack pointer
  47 version = MULTI_THREADED;       // produce multithreaded version
  48
  49 /***************************************************/
  50
  51 private import gcbits;
  52 private import gcstats;
  53 private import gcalloc;
  54
  55 private import cstdlib = stdc.stdlib : calloc, free, malloc, realloc;
  56 private import stdc.string;
  57
  58 debug private import stdc.stdio;
  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     private import gcc.builtins; // for __builtin_unwind_init
  67 }
  68
  69
  70 private
  71 {
  72     enum BlkAttr : uint
  73     {
  74         FINALIZE = 0b0000_0001,
  75         NO_SCAN  = 0b0000_0010,
  76         NO_MOVE  = 0b0000_0100,
  77         ALL_BITS = 0b1111_1111
  78     }
  79
  80     struct BlkInfo
  81     {
  82         void*  base;
  83         size_t size;
  84         uint   attr;
  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                     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             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             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                 memset(p + size, 0, binsize[bin] - size);
 504             //debug(PRINTF) printf("\tmalloc => %x\n", p);
 505             debug (MEMSTOMP) 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         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                     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) 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) memset(p + psize, 0xF0, size - psize);
 665                                     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                     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) memset(p + psize, 0xF0, (psz + sz) * PAGESIZE - psize);
 791         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) 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) 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         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             {   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                 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             {   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                 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             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             memset(&pool.pagetable[pn + 1], B_PAGEPLUS, npages - 1);
1969         p = pool.baseAddr + pn * PAGESIZE;
1970         memset(cast(char *)p + size, 0, npages * PAGESIZE - size);
1971         debug (MEMSTOMP) 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             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
2184         {
2185         asm
2186         {
2187             pushad              ;
2188             mov sp[EBP],ESP     ;
2189         }
2190         }
2191         result = fullcollect(sp);
2192         version (GNU)
2193         {
2194             // nothing to do
2195         }
2196         else
2197         {
2198         asm
2199         {
2200             popad               ;
2201         }
2202         }
2203         return result;
2204     }
2205
2206
2207     /**
2208      *
2209      */
2210     size_t fullcollect(void *stackTop)
2211     {
2212         size_t n;
2213         Pool*  pool;
2214
2215         debug(COLLECT_PRINTF) printf("Gcx.fullcollect()\n");
2216
2217         thread_suspendAll();
2218
2219         p_cache = null;
2220         size_cache = 0;
2221
2222         anychanges = 0;
2223         for (n = 0; n < npools; n++)
2224         {
2225             pool = pooltable[n];
2226             pool.mark.zero();
2227             pool.scan.zero();
2228             pool.freebits.zero();
2229         }
2230
2231         // Mark each free entry, so it doesn't get scanned
2232         for (n = 0; n < B_PAGE; n++)
2233         {
2234             for (List *list = bucket[n]; list; list = list.next)
2235             {
2236                 pool = findPool(list);
2237                 assert(pool);
2238                 pool.freebits.set(cast(size_t)(cast(byte*)list - pool.baseAddr) / 16);
2239             }
2240         }
2241
2242         for (n = 0; n < npools; n++)
2243         {
2244             pool = pooltable[n];
2245             pool.mark.copy(&pool.freebits);
2246         }
2247
2248         rt_scanStaticData( &mark );
2249
2250         version (MULTI_THREADED)
2251         {
2252             if (!noStack)
2253             {
2254                 // Scan stacks and registers for each paused thread
2255                 thread_scanAll( &mark, stackTop );
2256             }
2257         }
2258         else
2259         {
2260             if (!noStack)
2261             {
2262                 // Scan stack for main thread
2263                 debug(PRINTF) printf(" scan stack bot = %x, top = %x\n", stackTop, stackBottom);
2264                 version (STACKGROWSDOWN)
2265                     mark(stackTop, stackBottom);
2266                 else
2267                     mark(stackBottom, stackTop);
2268             }
2269         }
2270
2271         // Scan roots[]
2272         debug(COLLECT_PRINTF) printf("scan roots[]\n");
2273         mark(roots, roots + nroots);
2274
2275         // Scan ranges[]
2276         debug(COLLECT_PRINTF) printf("scan ranges[]\n");
2277         //log++;
2278         for (n = 0; n < nranges; n++)
2279         {
2280             debug(COLLECT_PRINTF) printf("\t%x .. %x\n", ranges[n].pbot, ranges[n].ptop);
2281             mark(ranges[n].pbot, ranges[n].ptop);
2282         }
2283         //log--;
2284
2285         debug(COLLECT_PRINTF) printf("\tscan heap\n");
2286         while (anychanges)
2287         {
2288             anychanges = 0;
2289             for (n = 0; n < npools; n++)
2290             {
2291                 uint *bbase;
2292                 uint *b;
2293                 uint *btop;
2294
2295                 pool = pooltable[n];
2296
2297                 bbase = pool.scan.base();
2298                 btop = bbase + pool.scan.nwords;
2299                 for (b = bbase; b < btop;)
2300                 {   Bins   bin;
2301                     size_t pn;
2302                     size_t u;
2303                     size_t bitm;
2304                     byte*  o;
2305
2306                     bitm = *b;
2307                     if (!bitm)
2308                     {   b++;
2309                         continue;
2310                     }
2311                     *b = 0;
2312
2313                     o = pool.baseAddr + (b - bbase) * 32 * 16;
2314                     if (!(bitm & 0xFFFF))
2315                     {
2316                         bitm >>= 16;
2317                         o += 16 * 16;
2318                     }
2319                     for (; bitm; o += 16, bitm >>= 1)
2320                     {
2321                         if (!(bitm & 1))
2322                             continue;
2323
2324                         pn = cast(size_t)(o - pool.baseAddr) / PAGESIZE;
2325                         bin = cast(Bins)pool.pagetable[pn];
2326                         if (bin < B_PAGE)
2327                         {
2328                             mark(o, o + binsize[bin]);
2329                         }
2330                         else if (bin == B_PAGE || bin == B_PAGEPLUS)
2331                         {
2332                             if (bin == B_PAGEPLUS)
2333                             {
2334                                 while (pool.pagetable[pn - 1] != B_PAGE)
2335                                     pn--;
2336                             }
2337                             u = 1;
2338                             while (pn + u < pool.ncommitted && pool.pagetable[pn + u] == B_PAGEPLUS)
2339                                 u++;
2340                             mark(o, o + u * PAGESIZE);
2341                         }
2342                     }
2343                 }
2344             }
2345         }
2346
2347         thread_resumeAll();
2348
2349         // Free up everything not marked
2350         debug(COLLECT_PRINTF) printf("\tfree'ing\n");
2351         size_t freedpages = 0;
2352         size_t freed = 0;
2353         for (n = 0; n < npools; n++)
2354         {   size_t pn;
2355             size_t ncommitted;
2356             uint*  bbase;
2357
2358             pool = pooltable[n];
2359             bbase = pool.mark.base();
2360             ncommitted = pool.ncommitted;
2361             for (pn = 0; pn < ncommitted; pn++, bbase += PAGESIZE / (32 * 16))
2362             {
2363                 Bins bin = cast(Bins)pool.pagetable[pn];
2364
2365                 if (bin < B_PAGE)
2366                 {   byte* p;
2367                     byte* ptop;
2368                     size_t biti;
2369                     size_t bitstride;
2370                     auto   size = binsize[bin];
2371
2372                     p = pool.baseAddr + pn * PAGESIZE;
2373                     ptop = p + PAGESIZE;
2374                     biti = pn * (PAGESIZE/16);
2375                     bitstride = size / 16;
2376
2377     version(none) // BUG: doesn't work because freebits() must also be cleared
2378     {
2379                     // If free'd entire page
2380                     if (bbase[0] == 0 && bbase[1] == 0 && bbase[2] == 0 && bbase[3] == 0 &&
2381                         bbase[4] == 0 && bbase[5] == 0 && bbase[6] == 0 && bbase[7] == 0)
2382                     {
2383                         for (; p < ptop; p += size, biti += bitstride)
2384                         {
2385                             if (pool.finals.nbits && pool.finals.testClear(biti))
2386                                 rt_finalize(cast(List *)sentinel_add(p), false/*noStack > 0*/);
2387                             gcx.clrBits(pool, biti, BlkAttr.ALL_BITS);
2388
2389                             List *list = cast(List *)p;
2390                             //debug(PRINTF) printf("\tcollecting %x\n", list);
2391                             log_free(sentinel_add(list));
2392
2393                             debug (MEMSTOMP) memset(p, 0xF3, size);
2394                         }
2395                         pool.pagetable[pn] = B_FREE;
2396                         freed += PAGESIZE;
2397                         //debug(PRINTF) printf("freeing entire page %d\n", pn);
2398                         continue;
2399                     }
2400     }
2401                     for (; p < ptop; p += size, biti += bitstride)
2402                     {
2403                         if (!pool.mark.test(biti))
2404                         {
2405                             sentinel_Invariant(sentinel_add(p));
2406
2407                             pool.freebits.set(biti);
2408                             if (pool.finals.nbits && pool.finals.testClear(biti))
2409                                 rt_finalize(cast(List *)sentinel_add(p), false/*noStack > 0*/);
2410                             clrBits(pool, biti, BlkAttr.ALL_BITS);
2411
2412                             List *list = cast(List *)p;
2413                             debug(PRINTF) printf("\tcollecting %x\n", list);
2414                             log_free(sentinel_add(list));
2415
2416                             debug (MEMSTOMP) memset(p, 0xF3, size);
2417
2418                             freed += size;
2419                         }
2420                     }
2421                 }
2422                 else if (bin == B_PAGE)
2423                 {   size_t biti = pn * (PAGESIZE / 16);
2424
2425                     if (!pool.mark.test(biti))
2426                     {   byte *p = pool.baseAddr + pn * PAGESIZE;
2427
2428                         sentinel_Invariant(sentinel_add(p));
2429                         if (pool.finals.nbits && pool.finals.testClear(biti))
2430                             rt_finalize(sentinel_add(p), false/*noStack > 0*/);
2431                         clrBits(pool, biti, BlkAttr.ALL_BITS);
2432
2433                         debug(COLLECT_PRINTF) printf("\tcollecting big %x\n", p);
2434                         log_free(sentinel_add(p));
2435                         pool.pagetable[pn] = B_FREE;
2436                         freedpages++;
2437                         debug (MEMSTOMP) memset(p, 0xF3, PAGESIZE);
2438                         while (pn + 1 < ncommitted && pool.pagetable[pn + 1] == B_PAGEPLUS)
2439                         {
2440                             pn++;
2441                             pool.pagetable[pn] = B_FREE;
2442                             freedpages++;
2443
2444                             debug (MEMSTOMP)
2445                             {   p += PAGESIZE;
2446                                 memset(p, 0xF3, PAGESIZE);
2447                             }
2448                         }
2449                     }
2450                 }
2451             }
2452         }
2453
2454         // Zero buckets
2455         bucket[] = null;
2456
2457         // Free complete pages, rebuild free list
2458         debug(COLLECT_PRINTF) printf("\tfree complete pages\n");
2459         size_t recoveredpages = 0;
2460         for (n = 0; n < npools; n++)
2461         {   size_t pn;
2462             size_t ncommitted;
2463
2464             pool = pooltable[n];
2465             ncommitted = pool.ncommitted;
2466             for (pn = 0; pn < ncommitted; pn++)
2467             {
2468                 Bins   bin = cast(Bins)pool.pagetable[pn];
2469                 size_t biti;
2470                 size_t u;
2471
2472                 if (bin < B_PAGE)
2473                 {
2474                     size_t size = binsize[bin];
2475                     size_t bitstride = size / 16;
2476                     size_t bitbase = pn * (PAGESIZE / 16);
2477                     size_t bittop = bitbase + (PAGESIZE / 16);
2478                     byte*  p;
2479
2480                     biti = bitbase;
2481                     for (biti = bitbase; biti < bittop; biti += bitstride)
2482                     {   if (!pool.freebits.test(biti))
2483                             goto Lnotfree;
2484                     }
2485                     pool.pagetable[pn] = B_FREE;
2486                     recoveredpages++;
2487                     continue;
2488
2489                  Lnotfree:
2490                     p = pool.baseAddr + pn * PAGESIZE;
2491                     for (u = 0; u < PAGESIZE; u += size)
2492                     {   biti = bitbase + u / 16;
2493                         if (pool.freebits.test(biti))
2494                         {   List *list;
2495
2496                             list = cast(List *)(p + u);
2497                             if (list.next != bucket[bin])       // avoid unnecessary writes
2498                                 list.next = bucket[bin];
2499                             bucket[bin] = list;
2500                         }
2501                     }
2502                 }
2503             }
2504         }
2505
2506         debug(COLLECT_PRINTF) printf("recovered pages = %d\n", recoveredpages);
2507         debug(COLLECT_PRINTF) printf("\tfree'd %u bytes, %u pages from %u pools\n", freed, freedpages, npools);
2508
2509         return freedpages + recoveredpages;
2510     }
2511
2512
2513     /**
2514      *
2515      */
2516     uint getBits(Pool* pool, size_t biti)
2517     in
2518     {
2519         assert( pool );
2520     }
2521     body
2522     {
2523         uint bits;
2524
2525         if (pool.finals.nbits &&
2526             pool.finals.test(biti))
2527             bits |= BlkAttr.FINALIZE;
2528         if (pool.noscan.test(biti))
2529             bits |= BlkAttr.NO_SCAN;
2530 //        if (pool.nomove.nbits &&
2531 //            pool.nomove.test(biti))
2532 //            bits |= BlkAttr.NO_MOVE;
2533         return bits;
2534     }
2535
2536
2537     /**
2538      *
2539      */
2540     void setBits(Pool* pool, size_t biti, uint mask)
2541     in
2542     {
2543         assert( pool );
2544     }
2545     body
2546     {
2547         if (mask & BlkAttr.FINALIZE)
2548         {
2549             if (!pool.finals.nbits)
2550                 pool.finals.alloc(pool.mark.nbits);
2551             pool.finals.set(biti);
2552         }
2553         if (mask & BlkAttr.NO_SCAN)
2554         {
2555             pool.noscan.set(biti);
2556         }
2557 //        if (mask & BlkAttr.NO_MOVE)
2558 //        {
2559 //            if (!pool.nomove.nbits)
2560 //                pool.nomove.alloc(pool.mark.nbits);
2561 //            pool.nomove.set(biti);
2562 //        }
2563     }
2564
2565
2566     /**
2567      *
2568      */
2569     void clrBits(Pool* pool, size_t biti, uint mask)
2570     in
2571     {
2572         assert( pool );
2573     }
2574     body
2575     {
2576         if (mask & BlkAttr.FINALIZE && pool.finals.nbits)
2577             pool.finals.clear(biti);
2578         if (mask & BlkAttr.NO_SCAN)
2579             pool.noscan.clear(biti);
2580 //        if (mask & BlkAttr.NO_MOVE && pool.nomove.nbits)
2581 //            pool.nomove.clear(biti);
2582     }
2583
2584
2585     /***** Leak Detector ******/
2586
2587
2588     debug (LOGGING)
2589     {
2590         LogArray current;
2591         LogArray prev;
2592
2593
2594         void log_init()
2595         {
2596             //debug(PRINTF) printf("+log_init()\n");
2597             current.reserve(1000);
2598             prev.reserve(1000);
2599             //debug(PRINTF) printf("-log_init()\n");
2600         }
2601
2602
2603         void log_malloc(void *p, size_t size)
2604         {
2605             //debug(PRINTF) printf("+log_malloc(p = %x, size = %d)\n", p, size);
2606             Log log;
2607
2608             log.p = p;
2609             log.size = size;
2610             log.line = GC.line;
2611             log.file = GC.file;
2612             log.parent = null;
2613
2614             GC.line = 0;
2615             GC.file = null;
2616
2617             current.push(log);
2618             //debug(PRINTF) printf("-log_malloc()\n");
2619         }
2620
2621
2622         void log_free(void *p)
2623         {
2624             //debug(PRINTF) printf("+log_free(%x)\n", p);
2625             size_t i;
2626
2627             i = current.find(p);
2628             if (i == OPFAIL)
2629             {
2630                 debug(PRINTF) printf("free'ing unallocated memory %x\n", p);
2631             }
2632             else
2633                 current.remove(i);
2634             //debug(PRINTF) printf("-log_free()\n");
2635         }
2636
2637
2638         void log_collect()
2639         {
2640             //debug(PRINTF) printf("+log_collect()\n");
2641             // Print everything in current that is not in prev
2642
2643             debug(PRINTF) printf("New pointers this cycle: --------------------------------\n");
2644             size_t used = 0;
2645             for (size_t i = 0; i < current.dim; i++)
2646             {
2647                 size_t j;
2648
2649                 j = prev.find(current.data[i].p);
2650                 if (j == OPFAIL)
2651                     current.data[i].print();
2652                 else
2653                     used++;
2654             }
2655
2656             debug(PRINTF) printf("All roots this cycle: --------------------------------\n");
2657             for (size_t i = 0; i < current.dim; i++)
2658             {
2659                 void *p;
2660                 size_t j;
2661
2662                 p = current.data[i].p;
2663                 if (!findPool(current.data[i].parent))
2664                 {
2665                     j = prev.find(current.data[i].p);
2666                     if (j == OPFAIL)
2667                         debug(PRINTF) printf("N");
2668                     else
2669                         debug(PRINTF) printf(" ");;
2670                     current.data[i].print();
2671                 }
2672             }
2673
2674             debug(PRINTF) printf("Used = %d-------------------------------------------------\n", used);
2675             prev.copy(&current);
2676
2677             debug(PRINTF) printf("-log_collect()\n");
2678         }
2679
2680
2681         void log_parent(void *p, void *parent)
2682         {
2683             //debug(PRINTF) printf("+log_parent()\n");
2684             size_t i;
2685
2686             i = current.find(p);
2687             if (i == OPFAIL)
2688             {
2689                 debug(PRINTF) printf("parent'ing unallocated memory %x, parent = %x\n", p, parent);
2690                 Pool *pool;
2691                 pool = findPool(p);
2692                 assert(pool);
2693                 size_t offset = cast(size_t)(p - pool.baseAddr);
2694                 size_t biti;
2695                 size_t pn = offset / PAGESIZE;
2696                 Bins bin = cast(Bins)pool.pagetable[pn];
2697                 biti = (offset & notbinsize[bin]);
2698                 debug(PRINTF) printf("\tbin = %d, offset = x%x, biti = x%x\n", bin, offset, biti);
2699             }
2700             else
2701             {
2702                 current.data[i].parent = parent;
2703             }
2704             //debug(PRINTF) printf("-log_parent()\n");
2705         }
2706
2707     }
2708     else
2709     {
2710         void log_init() { }
2711         void log_malloc(void *p, size_t size) { }
2712         void log_free(void *p) { }
2713         void log_collect() { }
2714         void log_parent(void *p, void *parent) { }
2715     }
2716 }
2717
2718
2719 /* ============================ Pool  =============================== */
2720
2721
2722 struct Pool
2723 {
2724     byte* baseAddr;
2725     byte* topAddr;
2726     GCBits mark;        // entries already scanned, or should not be scanned
2727     GCBits scan;        // entries that need to be scanned
2728     GCBits freebits;    // entries that are on the free list
2729     GCBits finals;      // entries that need finalizer run on them
2730     GCBits noscan;      // entries that should not be scanned
2731
2732     size_t npages;
2733     size_t ncommitted;    // ncommitted <= npages
2734     ubyte* pagetable;
2735
2736
2737     void initialize(size_t npages)
2738     {
2739         size_t poolsize;
2740
2741         //debug(PRINTF) printf("Pool::Pool(%u)\n", npages);
2742         poolsize = npages * PAGESIZE;
2743         assert(poolsize >= POOLSIZE);
2744         baseAddr = cast(byte *)os_mem_map(poolsize);
2745
2746         // Some of the code depends on page alignment of memory pools
2747         assert((cast(size_t)baseAddr & (PAGESIZE - 1)) == 0);
2748
2749         if (!baseAddr)
2750         {
2751             //debug(PRINTF) printf("GC fail: poolsize = x%x, errno = %d\n", poolsize, errno);
2752             //debug(PRINTF) printf("message = '%s'\n", sys_errlist[errno]);
2753
2754             npages = 0;
2755             poolsize = 0;
2756         }
2757         //assert(baseAddr);
2758         topAddr = baseAddr + poolsize;
2759
2760         mark.alloc(cast(size_t)poolsize / 16);
2761         scan.alloc(cast(size_t)poolsize / 16);
2762         freebits.alloc(cast(size_t)poolsize / 16);
2763         noscan.alloc(cast(size_t)poolsize / 16);
2764
2765         pagetable = cast(ubyte*)cstdlib.malloc(npages);
2766         if (!pagetable)
2767             onOutOfMemoryError();
2768         memset(pagetable, B_UNCOMMITTED, npages);
2769
2770         this.npages = npages;
2771         ncommitted = 0;
2772     }
2773
2774
2775     void Dtor()
2776     {
2777         if (baseAddr)
2778         {
2779             int result;
2780
2781             if (ncommitted)
2782             {
2783                 result = os_mem_decommit(baseAddr, 0, ncommitted * PAGESIZE);
2784                 assert(result == 0);
2785                 ncommitted = 0;
2786             }
2787
2788             if (npages)
2789             {
2790                 result = os_mem_unmap(baseAddr, npages * PAGESIZE);
2791                 assert(result == 0);
2792                 npages = 0;
2793             }
2794
2795             baseAddr = null;
2796             topAddr = null;
2797         }
2798         if (pagetable)
2799             cstdlib.free(pagetable);
2800
2801         mark.Dtor();
2802         scan.Dtor();
2803         freebits.Dtor();
2804         finals.Dtor();
2805         noscan.Dtor();
2806     }
2807
2808
2809     void Invariant() { }
2810
2811
2812     invariant()
2813     {
2814         //mark.Invariant();
2815         //scan.Invariant();
2816         //freebits.Invariant();
2817         //finals.Invariant();
2818         //noscan.Invariant();
2819
2820         if (baseAddr)
2821         {
2822             //if (baseAddr + npages * PAGESIZE != topAddr)
2823                 //printf("baseAddr = %p, npages = %d, topAddr = %p\n", baseAddr, npages, topAddr);
2824             assert(baseAddr + npages * PAGESIZE == topAddr);
2825             assert(ncommitted <= npages);
2826         }
2827
2828         for (size_t i = 0; i < npages; i++)
2829         {   Bins bin = cast(Bins)pagetable[i];
2830
2831             assert(bin < B_MAX);
2832         }
2833     }
2834
2835
2836     /**
2837      * Allocate n pages from Pool.
2838      * Returns OPFAIL on failure.
2839      */
2840     size_t allocPages(size_t n)
2841     {
2842         size_t i;
2843         size_t n2;
2844
2845         //debug(PRINTF) printf("Pool::allocPages(n = %d)\n", n);
2846         n2 = n;
2847         for (i = 0; i < ncommitted; i++)
2848         {
2849             if (pagetable[i] == B_FREE)
2850             {
2851                 if (--n2 == 0)
2852                 {   //debug(PRINTF) printf("\texisting pn = %d\n", i - n + 1);
2853                     return i - n + 1;
2854                 }
2855             }
2856             else
2857                 n2 = n;
2858         }
2859         return extendPages(n);
2860     }
2861
2862     /**
2863      * Extend Pool by n pages.
2864      * Returns OPFAIL on failure.
2865      */
2866     size_t extendPages(size_t n)
2867     {
2868         //debug(PRINTF) printf("Pool::extendPages(n = %d)\n", n);
2869         if (ncommitted + n <= npages)
2870         {
2871             size_t tocommit;
2872
2873             tocommit = (n + (COMMITSIZE/PAGESIZE) - 1) & ~(COMMITSIZE/PAGESIZE - 1);
2874             if (ncommitted + tocommit > npages)
2875                 tocommit = npages - ncommitted;
2876             //debug(PRINTF) printf("\tlooking to commit %d more pages\n", tocommit);
2877             //fflush(stdout);
2878             if (os_mem_commit(baseAddr, ncommitted * PAGESIZE, tocommit * PAGESIZE) == 0)
2879             {
2880                 memset(pagetable + ncommitted, B_FREE, tocommit);
2881                 auto i = ncommitted;
2882                 ncommitted += tocommit;
2883
2884                 while (i && pagetable[i - 1] == B_FREE)
2885                     i--;
2886
2887                 return i;
2888             }
2889             //debug(PRINTF) printf("\tfailed to commit %d pages\n", tocommit);
2890         }
2891
2892         return OPFAIL;
2893     }
2894
2895
2896     /**
2897      * Free npages pages starting with pagenum.
2898      */
2899     void freePages(size_t pagenum, size_t npages)
2900     {
2901         memset(&pagetable[pagenum], B_FREE, npages);
2902     }
2903
2904
2905     /**
2906      * Used for sorting pooltable[]
2907      */
2908     int opCmp(Pool *p2)
2909     {
2910         if (baseAddr < p2.baseAddr)
2911             return -1;
2912         else
2913         return cast(int)(baseAddr > p2.baseAddr);
2914     }
2915 }
2916
2917
2918 /* ============================ SENTINEL =============================== */
2919
2920
2921 version (SENTINEL)
2922 {
2923     const size_t SENTINEL_PRE = cast(size_t) 0xF4F4F4F4F4F4F4F4UL; // 32 or 64 bits
2924     const ubyte SENTINEL_POST = 0xF5;           // 8 bits
2925     const uint SENTINEL_EXTRA = 2 * size_t.sizeof + 1;
2926
2927
2928     size_t* sentinel_size(void *p)  { return &(cast(size_t *)p)[-2]; }
2929     size_t* sentinel_pre(void *p)   { return &(cast(size_t *)p)[-1]; }
2930     ubyte* sentinel_post(void *p) { return &(cast(ubyte *)p)[*sentinel_size(p)]; }
2931
2932
2933     void sentinel_init(void *p, size_t size)
2934     {
2935         *sentinel_size(p) = size;
2936         *sentinel_pre(p) = SENTINEL_PRE;
2937         *sentinel_post(p) = SENTINEL_POST;
2938     }
2939
2940
2941     void sentinel_Invariant(void *p)
2942     {
2943         assert(*sentinel_pre(p) == SENTINEL_PRE);
2944         assert(*sentinel_post(p) == SENTINEL_POST);
2945     }
2946
2947
2948     void *sentinel_add(void *p)
2949     {
2950         return p + 2 * size_t.sizeof;
2951     }
2952
2953
2954     void *sentinel_sub(void *p)
2955     {
2956         return p - 2 * size_t.sizeof;
2957     }
2958 }
2959 else
2960 {
2961     const uint SENTINEL_EXTRA = 0;
2962
2963
2964     void sentinel_init(void *p, size_t size)
2965     {
2966     }
2967
2968
2969     void sentinel_Invariant(void *p)
2970     {
2971     }
2972
2973
2974     void *sentinel_add(void *p)
2975     {
2976         return p;
2977     }
2978
2979
2980     void *sentinel_sub(void *p)
2981     {
2982         return p;
2983     }
2984 }