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