src/gc/basic/gcx.d

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