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