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