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