rt/gc/cdgc/gc.d

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