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