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