gc/gc.d

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