]> git.llucax.com Git - software/dgc/cdgc.git/blobdiff - rt/gc/cdgc/gc.d
projects / software / dgc / cdgc.git / blobdiff
? search:
summary | shortlog | log | commit | commitdiff | tree
raw | inline | side by side
Unify GC class and Gcx struct
[software/dgc/cdgc.git] / rt / gc / cdgc / gc.d
diff --git a/rt/gc/cdgc/gc.d b/rt/gc/cdgc/gc.d
index 83a96b22d7014997f664ae6eadef37befdacc9a0..a8c7360cf11016be2770a9d5c56fb45bb23f8828 100644 (file)
--- a/rt/gc/cdgc/gc.d
+++ b/rt/gc/cdgc/gc.d
@@ -44,7 +44,7 @@ version = STACKGROWSDOWN;       // growing the stack means subtracting from the
 
 import rt.gc.cdgc.bits: GCBits;
 import rt.gc.cdgc.stats: GCStats, Stats;
 
 import rt.gc.cdgc.bits: GCBits;
 import rt.gc.cdgc.stats: GCStats, Stats;
-import rt.gc.cdgc.dynarray: DynArray;
+import dynarray = rt.gc.cdgc.dynarray;
 import alloc = rt.gc.cdgc.alloc;
 import opts = rt.gc.cdgc.opts;
 
 import alloc = rt.gc.cdgc.alloc;
 import opts = rt.gc.cdgc.opts;
 
@@ -129,7 +129,56 @@ private
 }
 
 
 }
 
 
-alias GC gc_t;
+enum
+{
+    PAGESIZE =    4096,
+    POOLSIZE =   (4096*256),
+}
+
+
+enum
+{
+    B_16,
+    B_32,
+    B_64,
+    B_128,
+    B_256,
+    B_512,
+    B_1024,
+    B_2048,
+    B_PAGE,             // start of large alloc
+    B_PAGEPLUS,         // continuation of large alloc
+    B_FREE,             // free page
+    B_MAX
+}
+
+
+alias ubyte Bins;
+
+
+struct List
+{
+    List *next;
+}
+
+
+struct Range
+{
+    void *pbot;
+    void *ptop;
+    int opCmp(in Range other)
+    {
+        if (pbot < other.pbot)
+            return -1;
+        else
+        return cast(int)(pbot > other.pbot);
+    }
+}
+
+
+const uint binsize[B_MAX] = [ 16,32,64,128,256,512,1024,2048,4096 ];
+const uint notbinsize[B_MAX] = [ ~(16u-1),~(32u-1),~(64u-1),~(128u-1),~(256u-1),
+                                ~(512u-1),~(1024u-1),~(2048u-1),~(4096u-1) ];
 
 
 /* ============================ GC =============================== */
 
 
 /* ============================ GC =============================== */
@@ -138,2370 +187,2278 @@ alias GC gc_t;
 class GCLock { }                // just a dummy so we can get a global lock
 
 
 class GCLock { }                // just a dummy so we can get a global lock
 
 
-Stats stats;
-
-class GC
+struct GC
 {
 {
-    Gcx *gcx;                   // implementation
     static ClassInfo gcLock;    // global lock
 
     static ClassInfo gcLock;    // global lock
 
+    void *p_cache;
+    size_t size_cache;
 
 
-    void initialize()
-    {
-        opts.parse(cstdlib.getenv("D_GC_OPTS"));
-        gcLock = GCLock.classinfo;
-        gcx = cast(Gcx*) cstdlib.calloc(1, Gcx.sizeof);
-        if (!gcx)
-            onOutOfMemoryError();
-        gcx.initialize();
-        setStackBottom(rt_stackBottom());
-        stats = Stats(this);
-    }
+    uint noStack;       // !=0 means don't scan stack
+    uint anychanges;
+    void *stackBottom;
+    uint inited;
+    int disabled;       // turn off collections if >0
 
 
+    byte *minAddr;      // min(baseAddr)
+    byte *maxAddr;      // max(topAddr)
 
 
-    /**
-     *
-     */
-    void enable()
+    List *bucket[B_MAX];        // free list for each size
+
+    dynarray.DynArray!(void*) roots;
+    dynarray.DynArray!(Range) ranges;
+    dynarray.DynArray!(Pool) pools;
+
+    Stats stats;
+
+
+    invariant
     {
     {
-        if (!thread_needLock())
-        {
-            assert(gcx.disabled > 0);
-            gcx.disabled--;
-        }
-        else synchronized (gcLock)
+        if (inited)
         {
         {
-            assert(gcx.disabled > 0);
-            gcx.disabled--;
+        //printf("Gcx.invariant(): this = %p\n", this);
+            size_t i;
+
+            for (i = 0; i < pools.length; i++)
+            {
+                Pool* pool = pools[i];
+                pool.Invariant();
+                if (i == 0)
+                {
+                    assert(minAddr == pool.baseAddr);
+                }
+                if (i + 1 < pools.length)
+                {
+                    assert(*pool < pools[i + 1]);
+                }
+                else if (i + 1 == pools.length)
+                {
+                    assert(maxAddr == pool.topAddr);
+                }
+            }
+
+            roots.Invariant();
+            ranges.Invariant();
+
+            for (i = 0; i < ranges.length; i++)
+            {
+                assert(ranges[i].pbot);
+                assert(ranges[i].ptop);
+                assert(ranges[i].pbot <= ranges[i].ptop);
+            }
+
+            for (i = 0; i < B_PAGE; i++)
+            {
+                for (List *list = bucket[i]; list; list = list.next)
+                {
+                }
+            }
         }
     }
 
 
     /**
         }
     }
 
 
     /**
-     *
+     * Find Pool that pointer is in.
+     * Return null if not in a Pool.
+     * Assume pools is sorted.
      */
      */
-    void disable()
+    Pool *findPool(void *p)
     {
     {
-        if (!thread_needLock())
-        {
-            gcx.disabled++;
-        }
-        else synchronized (gcLock)
+        if (p >= minAddr && p < maxAddr)
         {
         {
-            gcx.disabled++;
+            if (pools.length == 1)
+            {
+                return pools[0];
+            }
+
+            for (size_t i = 0; i < pools.length; i++)
+            {
+                Pool* pool = pools[i];
+                if (p < pool.topAddr)
+                {
+                    if (pool.baseAddr <= p)
+                        return pool;
+                    break;
+                }
+            }
         }
         }
+        return null;
     }
 
 
     /**
     }
 
 
     /**
-     *
+     * Find base address of block containing pointer p.
+     * Returns null if not a gc'd pointer
      */
      */
-    uint getAttr(void* p)
+    void* findBase(void *p)
     {
     {
-        if (!p)
-        {
-            return 0;
-        }
+        Pool *pool;
 
 
-        uint go()
+        pool = findPool(p);
+        if (pool)
         {
         {
-            Pool* pool = gcx.findPool(p);
-            uint  old_attrs = 0;
+            size_t offset = cast(size_t)(p - pool.baseAddr);
+            size_t pn = offset / PAGESIZE;
+            Bins   bin = cast(Bins)pool.pagetable[pn];
 
 
-            if (pool)
+            // Adjust bit to be at start of allocated memory block
+            if (bin <= B_PAGE)
             {
             {
-                auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
-
-                old_attrs = gcx.getAttr(pool, bit_i);
+                return pool.baseAddr + (offset & notbinsize[bin]);
             }
             }
-            return old_attrs;
-        }
+            else if (bin == B_PAGEPLUS)
+            {
+                do
+                {
+                    --pn, offset -= PAGESIZE;
+                } while (cast(Bins)pool.pagetable[pn] == B_PAGEPLUS);
 
 
-        if (!thread_needLock())
-        {
-            return go();
-        }
-        else synchronized (gcLock)
-        {
-            return go();
+                return pool.baseAddr + (offset & (offset.max ^ (PAGESIZE-1)));
+            }
+            else
+            {
+                // we are in a B_FREE page
+                return null;
+            }
         }
         }
+        return null;
     }
 
 
     /**
     }
 
 
     /**
-     *
+     * Find size of pointer p.
+     * Returns 0 if not a gc'd pointer
      */
      */
-    uint setAttr(void* p, uint mask)
+    size_t findSize(void *p)
     {
     {
-        if (!p)
-        {
-            return 0;
-        }
+        Pool*  pool;
+        size_t size = 0;
 
 
-        uint go()
+        pool = findPool(p);
+        if (pool)
         {
         {
-            Pool* pool = gcx.findPool(p);
-            uint  old_attrs = 0;
+            size_t pagenum;
+            Bins   bin;
 
 
-            if (pool)
+            pagenum = cast(size_t)(p - pool.baseAddr) / PAGESIZE;
+            bin = cast(Bins)pool.pagetable[pagenum];
+            size = binsize[bin];
+            if (bin == B_PAGE)
             {
             {
-                auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
+                ubyte* pt;
+                size_t i;
 
 
-                old_attrs = gcx.getAttr(pool, bit_i);
-                gcx.setAttr(pool, bit_i, mask);
+                pt = &pool.pagetable[0];
+                for (i = pagenum + 1; i < pool.npages; i++)
+                {
+                    if (pt[i] != B_PAGEPLUS)
+                        break;
+                }
+                size = (i - pagenum) * PAGESIZE;
             }
             }
-            return old_attrs;
-        }
-
-        if (!thread_needLock())
-        {
-            return go();
-        }
-        else synchronized (gcLock)
-        {
-            return go();
         }
         }
+        return size;
     }
 
 
     /**
      *
      */
     }
 
 
     /**
      *
      */
-    uint clrAttr(void* p, uint mask)
+    BlkInfo getInfo(void* p)
     {
     {
-        if (!p)
-        {
-            return 0;
-        }
+        Pool*   pool;
+        BlkInfo info;
 
 
-        uint go()
+        pool = findPool(p);
+        if (pool)
         {
         {
-            Pool* pool = gcx.findPool(p);
-            uint  old_attrs = 0;
-
-            if (pool)
-            {
-                auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
+            size_t offset = cast(size_t)(p - pool.baseAddr);
+            size_t pn = offset / PAGESIZE;
+            Bins   bin = cast(Bins)pool.pagetable[pn];
 
 
-                old_attrs = gcx.getAttr(pool, bit_i);
-                gcx.clrAttr(pool, bit_i, mask);
-            }
-            return old_attrs;
-        }
-
-        if (!thread_needLock())
-        {
-            return go();
-        }
-        else synchronized (gcLock)
-        {
-            return go();
-        }
-    }
-
-
-    /**
-     *
-     */
-    void *malloc(size_t size, uint attrs, PointerMap ptrmap)
-    {
-        if (!size)
-        {
-            return null;
-        }
-
-        if (!thread_needLock())
-        {
-            return mallocNoSync(size, attrs, ptrmap.bits.ptr);
-        }
-        else synchronized (gcLock)
-        {
-            return mallocNoSync(size, attrs, ptrmap.bits.ptr);
-        }
-    }
-
-
-    //
-    //
-    //
-    private void *mallocNoSync(size_t size, uint attrs, size_t* pm_bitmask)
-    {
-        assert(size != 0);
-
-        stats.malloc_started(size, attrs, pm_bitmask);
-        scope (exit)
-            stats.malloc_finished(p);
-
-        void *p = null;
-        Bins bin;
+            ////////////////////////////////////////////////////////////////////
+            // findAddr
+            ////////////////////////////////////////////////////////////////////
 
 
-        assert(gcx);
+            if (bin <= B_PAGE)
+            {
+                info.base = pool.baseAddr + (offset & notbinsize[bin]);
+            }
+            else if (bin == B_PAGEPLUS)
+            {
+                do
+                {
+                    --pn, offset -= PAGESIZE;
+                }
+                while (cast(Bins)pool.pagetable[pn] == B_PAGEPLUS);
 
 
-        if (opts.options.sentinel)
-            size += SENTINEL_EXTRA;
+                info.base = pool.baseAddr + (offset & (offset.max ^ (PAGESIZE-1)));
 
 
-        bool has_pm = has_pointermap(attrs);
-        if (has_pm)
-            size += size_t.sizeof;
+                // fix bin for use by size calc below
+                bin = cast(Bins)pool.pagetable[pn];
+            }
 
 
-        // Compute size bin
-        // Cache previous binsize lookup - Dave Fladebo.
-        static size_t lastsize = -1;
-        static Bins lastbin;
-        if (size == lastsize)
-            bin = lastbin;
-        else
-        {
-            bin = gcx.findBin(size);
-            lastsize = size;
-            lastbin = bin;
-        }
+            ////////////////////////////////////////////////////////////////////
+            // findSize
+            ////////////////////////////////////////////////////////////////////
 
 
-        size_t capacity; // to figure out where to store the bitmask
-        if (bin < B_PAGE)
-        {
-            p = gcx.bucket[bin];
-            if (p is null)
+            info.size = binsize[bin];
+            if (bin == B_PAGE)
             {
             {
-                if (!gcx.allocPage(bin) && !gcx.disabled)   // try to find a new page
-                {
-                    if (!thread_needLock())
-                    {
-                        /* Then we haven't locked it yet. Be sure
-                         * and lock for a collection, since a finalizer
-                         * may start a new thread.
-                         */
-                        synchronized (gcLock)
-                        {
-                            gcx.fullcollectshell();
-                        }
-                    }
-                    else if (!gcx.fullcollectshell())       // collect to find a new page
-                    {
-                        //gcx.newPool(1);
-                    }
-                }
-                if (!gcx.bucket[bin] && !gcx.allocPage(bin))
+                ubyte* pt;
+                size_t i;
+
+                pt = &pool.pagetable[0];
+                for (i = pn + 1; i < pool.npages; i++)
                 {
                 {
-                    gcx.newPool(1);         // allocate new pool to find a new page
-                    int result = gcx.allocPage(bin);
-                    if (!result)
-                        onOutOfMemoryError();
+                    if (pt[i] != B_PAGEPLUS)
+                        break;
                 }
                 }
-                p = gcx.bucket[bin];
+                info.size = (i - pn) * PAGESIZE;
             }
             }
-            capacity = binsize[bin];
-
-            // Return next item from free list
-            gcx.bucket[bin] = (cast(List*)p).next;
-            if (!(attrs & BlkAttr.NO_SCAN))
-                memset(p + size, 0, capacity - size);
-            if (opts.options.mem_stomp)
-                memset(p, 0xF0, size);
-        }
-        else
-        {
-            p = gcx.bigAlloc(size);
-            if (!p)
-                onOutOfMemoryError();
-            // Round the size up to the number of pages needed to store it
-            size_t npages = (size + PAGESIZE - 1) / PAGESIZE;
-            capacity = npages * PAGESIZE;
-        }
-
-        // Store the bit mask AFTER SENTINEL_POST
-        // TODO: store it BEFORE, so the bitmask is protected too
-        if (has_pm) {
-            auto end_of_blk = cast(size_t**)(p + capacity - size_t.sizeof);
-            *end_of_blk = pm_bitmask;
-            size -= size_t.sizeof;
-        }
-
-        if (opts.options.sentinel) {
-            size -= SENTINEL_EXTRA;
-            p = sentinel_add(p);
-            sentinel_init(p, size);
-        }
 
 
-        if (attrs)
-        {
-            Pool *pool = gcx.findPool(p);
-            assert(pool);
+            ////////////////////////////////////////////////////////////////////
+            // getAttr
+            ////////////////////////////////////////////////////////////////////
 
 
-            gcx.setAttr(pool, cast(size_t)(p - pool.baseAddr) / 16, attrs);
+            info.attr = getAttr(pool, cast(size_t)(offset / 16));
+            if (!(info.attr & BlkAttr.NO_SCAN))
+                info.size -= (size_t*).sizeof;  // bitmask
         }
         }
-        return p;
+        return info;
     }
 
 
     /**
     }
 
 
     /**
-     *
+     * Compute bin for size.
      */
      */
-    void *calloc(size_t size, uint attrs, PointerMap ptrmap)
+    static Bins findBin(size_t size)
     {
     {
-        if (!size)
-        {
-            return null;
-        }
-
-        if (!thread_needLock())
+        Bins bin;
+        if (size <= 256)
         {
         {
-            return callocNoSync(size, attrs, ptrmap.bits.ptr);
+            if (size <= 64)
+            {
+                if (size <= 16)
+                    bin = B_16;
+                else if (size <= 32)
+                    bin = B_32;
+                else
+                    bin = B_64;
+            }
+            else
+            {
+                if (size <= 128)
+                    bin = B_128;
+                else
+                    bin = B_256;
+            }
         }
         }
-        else synchronized (gcLock)
+        else
         {
         {
-            return callocNoSync(size, attrs, ptrmap.bits.ptr);
+            if (size <= 1024)
+            {
+                if (size <= 512)
+                    bin = B_512;
+                else
+                    bin = B_1024;
+            }
+            else
+            {
+                if (size <= 2048)
+                    bin = B_2048;
+                else
+                    bin = B_PAGE;
+            }
         }
         }
+        return bin;
     }
 
 
     }
 
 
-    //
-    //
-    //
-    private void *callocNoSync(size_t size, uint attrs, size_t* pm_bitmask)
+    /**
+     * Allocate a new pool of at least size bytes.
+     * Sort it into pools.
+     * Mark all memory in the pool as B_FREE.
+     * Return the actual number of bytes reserved or 0 on error.
+     */
+    size_t reserveNoSync(size_t size)
     {
         assert(size != 0);
     {
         assert(size != 0);
+        size_t npages = (size + PAGESIZE - 1) / PAGESIZE;
+        Pool*  pool = newPool(npages);
 
 
-        void *p = mallocNoSync(size, attrs, pm_bitmask);
-        memset(p, 0, size);
-        return p;
+        if (!pool)
+            return 0;
+        return pool.npages * PAGESIZE;
     }
 
 
     /**
     }
 
 
     /**
-     *
+     * Minimizes physical memory usage by returning free pools to the OS.
      */
      */
-    void *realloc(void *p, size_t size, uint attrs, PointerMap ptrmap)
+    void minimizeNoSync()
     {
     {
-        if (!thread_needLock())
-        {
-            return reallocNoSync(p, size, attrs, ptrmap.bits.ptr);
-        }
-        else synchronized (gcLock)
+        size_t n;
+        size_t pn;
+        Pool*  pool;
+
+        for (n = 0; n < pools.length; n++)
         {
         {
-            return reallocNoSync(p, size, attrs, ptrmap.bits.ptr);
+            pool = pools[n];
+            for (pn = 0; pn < pool.npages; pn++)
+            {
+                if (cast(Bins)pool.pagetable[pn] != B_FREE)
+                    break;
+            }
+            if (pn < pool.npages)
+                continue;
+            pool.Dtor();
+            pools.remove_at(n);
+            n--;
         }
         }
+        minAddr = pools[0].baseAddr;
+        maxAddr = pools[pools.length - 1].topAddr;
     }
 
 
     }
 
 
-    //
-    //
-    //
-    private void *reallocNoSync(void *p, size_t size, uint attrs,
-            size_t* pm_bitmask)
-    {
-        if (!size)
-        {
-            if (p)
-            {
-                freeNoSync(p);
-                p = null;
-            }
-        }
-        else if (!p)
-        {
-            p = mallocNoSync(size, attrs, pm_bitmask);
-        }
-        else
-        {
-            Pool* pool = gcx.findPool(p);
-            if (pool is null)
-                return null;
+    /**
+     * Allocate a chunk of memory that is larger than a page.
+     * Return null if out of memory.
+     */
+    void *bigAlloc(size_t size)
+    {
+        Pool*  pool;
+        size_t npages;
+        size_t n;
+        size_t pn;
+        size_t freedpages;
+        void*  p;
+        int    state;
 
 
-            // Set or retrieve attributes as appropriate
-            auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
-            if (attrs) {
-                gcx.clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
-                gcx.setAttr(pool, bit_i, attrs);
-            }
-            else
-                attrs = gcx.getAttr(pool, bit_i);
+        npages = (size + PAGESIZE - 1) / PAGESIZE;
 
 
-            void* blk_base_addr = gcx.findBase(p);
-            size_t blk_size = gcx.findSize(p);
-            bool has_pm = has_pointermap(attrs);
-            size_t pm_bitmask_size = 0;
-            if (has_pm) {
-                pm_bitmask_size = size_t.sizeof;
-                // Retrieve pointer map bit mask if appropriate
-                if (pm_bitmask is null) {
-                    auto end_of_blk = cast(size_t**)(blk_base_addr +
-                            blk_size - size_t.sizeof);
-                    pm_bitmask = *end_of_blk;
-                }
+        for (state = 0; ; )
+        {
+            // This code could use some refinement when repeatedly
+            // allocating very large arrays.
+
+            for (n = 0; n < pools.length; n++)
+            {
+                pool = pools[n];
+                pn = pool.allocPages(npages);
+                if (pn != OPFAIL)
+                    goto L1;
             }
 
             }
 
-            if (opts.options.sentinel)
+            // Failed
+            switch (state)
             {
             {
-                sentinel_Invariant(p);
-                size_t sentinel_stored_size = *sentinel_size(p);
-                if (sentinel_stored_size != size)
+            case 0:
+                if (disabled)
                 {
                 {
-                    void* p2 = mallocNoSync(size, attrs, pm_bitmask);
-                    if (sentinel_stored_size < size)
-                        size = sentinel_stored_size;
-                    cstring.memcpy(p2, p, size);
-                    p = p2;
+                    state = 1;
+                    continue;
                 }
                 }
-            }
-            else
-            {
-                size += pm_bitmask_size;
-                if (blk_size >= PAGESIZE && size >= PAGESIZE)
+                // Try collecting
+                freedpages = fullcollectshell();
+                if (freedpages >= pools.length * ((POOLSIZE / PAGESIZE) / 4))
                 {
                 {
-                    auto psz = blk_size / PAGESIZE;
-                    auto newsz = (size + PAGESIZE - 1) / PAGESIZE;
-                    if (newsz == psz)
-                        return p;
-
-                    auto pagenum = (p - pool.baseAddr) / PAGESIZE;
-
-                    if (newsz < psz)
-                    {
-                        // Shrink in place
-                        synchronized (gcLock)
-                        {
-                            if (opts.options.mem_stomp)
-                                memset(p + size - pm_bitmask_size, 0xF2,
-                                        blk_size - size - pm_bitmask_size);
-                            pool.freePages(pagenum + newsz, psz - newsz);
-                        }
-                        if (has_pm) {
-                            auto end_of_blk = cast(size_t**)(
-                                    blk_base_addr + (PAGESIZE * newsz) -
-                                    pm_bitmask_size);
-                            *end_of_blk = pm_bitmask;
-                        }
-                        return p;
-                    }
-                    else if (pagenum + newsz <= pool.npages)
-                    {
-                        // Attempt to expand in place
-                        synchronized (gcLock)
-                        {
-                            for (size_t i = pagenum + psz; 1;)
-                            {
-                                if (i == pagenum + newsz)
-                                {
-                                    if (opts.options.mem_stomp)
-                                        memset(p + blk_size - pm_bitmask_size,
-                                                0xF0, size - blk_size
-                                                - pm_bitmask_size);
-                                    memset(pool.pagetable + pagenum +
-                                            psz, B_PAGEPLUS, newsz - psz);
-                                    if (has_pm) {
-                                        auto end_of_blk = cast(size_t**)(
-                                                blk_base_addr +
-                                                (PAGESIZE * newsz) -
-                                                pm_bitmask_size);
-                                        *end_of_blk = pm_bitmask;
-                                    }
-                                    return p;
-                                }
-                                if (i == pool.npages)
-                                {
-                                    break;
-                                }
-                                if (pool.pagetable[i] != B_FREE)
-                                    break;
-                                i++;
-                            }
-                        }
-                    }
+                    state = 1;
+                    continue;
                 }
                 }
-                // if new size is bigger or less than half
-                if (blk_size < size || blk_size > size * 2)
+                // Release empty pools to prevent bloat
+                minimize();
+                // Allocate new pool
+                pool = newPool(npages);
+                if (!pool)
                 {
                 {
-                    size -= pm_bitmask_size;
-                    blk_size -= pm_bitmask_size;
-                    void* p2 = mallocNoSync(size, attrs, pm_bitmask);
-                    if (blk_size < size)
-                        size = blk_size;
-                    cstring.memcpy(p2, p, size);
-                    p = p2;
+                    state = 2;
+                    continue;
                 }
                 }
+                pn = pool.allocPages(npages);
+                assert(pn != OPFAIL);
+                goto L1;
+            case 1:
+                // Release empty pools to prevent bloat
+                minimize();
+                // Allocate new pool
+                pool = newPool(npages);
+                if (!pool)
+                    goto Lnomemory;
+                pn = pool.allocPages(npages);
+                assert(pn != OPFAIL);
+                goto L1;
+            case 2:
+                goto Lnomemory;
+            default:
+                assert(false);
             }
         }
             }
         }
+
+      L1:
+        pool.pagetable[pn] = B_PAGE;
+        if (npages > 1)
+            memset(&pool.pagetable[pn + 1], B_PAGEPLUS, npages - 1);
+        p = pool.baseAddr + pn * PAGESIZE;
+        memset(cast(char *)p + size, 0, npages * PAGESIZE - size);
+        if (opts.options.mem_stomp)
+            memset(p, 0xF1, size);
         return p;
         return p;
+
+      Lnomemory:
+        return null; // let mallocNoSync handle the error
     }
 
 
     /**
     }
 
 
     /**
-     * Attempt to in-place enlarge the memory block pointed to by p by at least
-     * minbytes beyond its current capacity, up to a maximum of maxsize.  This
-     * does not attempt to move the memory block (like realloc() does).
-     *
-     * Returns:
-     *  0 if could not extend p,
-     *  total size of entire memory block if successful.
+     * Allocate a new pool with at least npages in it.
+     * Sort it into pools.
+     * Return null if failed.
      */
      */
-    size_t extend(void* p, size_t minsize, size_t maxsize)
+    Pool *newPool(size_t npages)
     {
     {
-        if (!thread_needLock())
+        // Minimum of POOLSIZE
+        if (npages < POOLSIZE/PAGESIZE)
+            npages = POOLSIZE/PAGESIZE;
+        else if (npages > POOLSIZE/PAGESIZE)
         {
         {
-            return extendNoSync(p, minsize, maxsize);
+            // Give us 150% of requested size, so there's room to extend
+            auto n = npages + (npages >> 1);
+            if (n < size_t.max/PAGESIZE)
+                npages = n;
         }
         }
-        else synchronized (gcLock)
+
+        // Allocate successively larger pools up to 8 megs
+        if (pools.length)
         {
         {
-            return extendNoSync(p, minsize, maxsize);
+            size_t n = pools.length;
+            if (n > 8)
+                n = 8;                  // cap pool size at 8 megs
+            n *= (POOLSIZE / PAGESIZE);
+            if (npages < n)
+                npages = n;
         }
         }
-    }
 
 
+        Pool p;
+        p.initialize(npages);
+        if (!p.baseAddr)
+        {
+            p.Dtor();
+            return null;
+        }
 
 
-    //
-    //
-    //
-    private size_t extendNoSync(void* p, size_t minsize, size_t maxsize)
-    in
-    {
-        assert( minsize <= maxsize );
-    }
-    body
-    {
-        if (opts.options.sentinel)
-            return 0;
-
-        Pool* pool = gcx.findPool(p);
-        if (pool is null)
-            return 0;
-
-        // Retrieve attributes
-        auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
-        uint attrs = gcx.getAttr(pool, bit_i);
-
-        void* blk_base_addr = gcx.findBase(p);
-        size_t blk_size = gcx.findSize(p);
-        bool has_pm = has_pointermap(attrs);
-        size_t* pm_bitmask = null;
-        size_t pm_bitmask_size = 0;
-        if (has_pm) {
-            pm_bitmask_size = size_t.sizeof;
-            // Retrieve pointer map bit mask
-            auto end_of_blk = cast(size_t**)(blk_base_addr +
-                    blk_size - size_t.sizeof);
-            pm_bitmask = *end_of_blk;
-
-            minsize += size_t.sizeof;
-            maxsize += size_t.sizeof;
-        }
-
-        if (blk_size < PAGESIZE)
-            return 0; // cannot extend buckets
-
-        auto psz = blk_size / PAGESIZE;
-        auto minsz = (minsize + PAGESIZE - 1) / PAGESIZE;
-        auto maxsz = (maxsize + PAGESIZE - 1) / PAGESIZE;
-
-        auto pagenum = (p - pool.baseAddr) / PAGESIZE;
-
-        size_t sz;
-        for (sz = 0; sz < maxsz; sz++)
-        {
-            auto i = pagenum + psz + sz;
-            if (i == pool.npages)
-                break;
-            if (pool.pagetable[i] != B_FREE)
-            {
-                if (sz < minsz)
-                    return 0;
-                break;
-            }
-        }
-        if (sz < minsz)
-            return 0;
-
-        size_t new_size = (psz + sz) * PAGESIZE;
-
-        if (opts.options.mem_stomp)
-            memset(p + blk_size - pm_bitmask_size, 0xF0,
-                    new_size - blk_size - pm_bitmask_size);
-        memset(pool.pagetable + pagenum + psz, B_PAGEPLUS, sz);
-        gcx.p_cache = null;
-        gcx.size_cache = 0;
-
-        if (has_pm) {
-            new_size -= size_t.sizeof;
-            auto end_of_blk = cast(size_t**)(blk_base_addr + new_size);
-            *end_of_blk = pm_bitmask;
-        }
-        return new_size;
+        Pool* pool = pools.insert_sorted(p);
+        if (pool)
+        {
+            minAddr = pools[0].baseAddr;
+            maxAddr = pools[pools.length - 1].topAddr;
+        }
+        return pool;
     }
 
 
     /**
     }
 
 
     /**
-     *
+     * Allocate a page of bin's.
+     * Returns:
+     *  0       failed
      */
      */
-    size_t reserve(size_t size)
+    int allocPage(Bins bin)
     {
     {
-        if (!size)
-        {
-            return 0;
-        }
+        Pool*  pool;
+        size_t n;
+        size_t pn;
+        byte*  p;
+        byte*  ptop;
 
 
-        if (!thread_needLock())
-        {
-            return reserveNoSync(size);
-        }
-        else synchronized (gcLock)
+        for (n = 0; n < pools.length; n++)
         {
         {
-            return reserveNoSync(size);
+            pool = pools[n];
+            pn = pool.allocPages(1);
+            if (pn != OPFAIL)
+                goto L1;
         }
         }
-    }
+        return 0;               // failed
 
 
+      L1:
+        pool.pagetable[pn] = cast(ubyte)bin;
 
 
-    //
-    //
-    //
-    private size_t reserveNoSync(size_t size)
-    {
-        assert(size != 0);
-        assert(gcx);
+        // Convert page to free list
+        size_t size = binsize[bin];
+        List **b = &bucket[bin];
 
 
-        return gcx.reserve(size);
+        p = pool.baseAddr + pn * PAGESIZE;
+        ptop = p + PAGESIZE;
+        for (; p < ptop; p += size)
+        {
+            (cast(List *)p).next = *b;
+            *b = cast(List *)p;
+        }
+        return 1;
     }
 
 
     /**
     }
 
 
     /**
-     *
+     * Marks a range of memory using the conservative bit mask.  Used for
+     * the stack, for the data segment, and additional memory ranges.
      */
      */
-    void free(void *p)
+    void mark_conservative(void* pbot, void* ptop)
     {
     {
-        if (!p)
-        {
-            return;
-        }
-
-        if (!thread_needLock())
-        {
-            return freeNoSync(p);
-        }
-        else synchronized (gcLock)
-        {
-            return freeNoSync(p);
-        }
+        mark(pbot, ptop, PointerMap.init.bits.ptr);
     }
 
 
     }
 
 
-    //
-    //
-    //
-    private void freeNoSync(void *p)
+    /**
+     * Search a range of memory values and mark any pointers into the GC pool.
+     */
+    void mark(void *pbot, void *ptop, size_t* pm_bitmask)
     {
     {
-        assert (p);
+        const BITS_PER_WORD = size_t.sizeof * 8;
 
 
-        Pool*  pool;
-        size_t pagenum;
-        Bins   bin;
-        size_t bit_i;
+        void **p1 = cast(void **)pbot;
+        void **p2 = cast(void **)ptop;
+        size_t pcache = 0;
+        uint changes = 0;
 
 
-        // Find which page it is in
-        pool = gcx.findPool(p);
-        if (!pool)                              // if not one of ours
-            return;                             // ignore
-        if (opts.options.sentinel) {
-            sentinel_Invariant(p);
-            p = sentinel_sub(p);
-        }
-        pagenum = cast(size_t)(p - pool.baseAddr) / PAGESIZE;
-        bit_i = cast(size_t)(p - pool.baseAddr) / 16;
-        gcx.clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
+        size_t type_size = pm_bitmask[0];
+        size_t* pm_bits = pm_bitmask + 1;
 
 
-        bin = cast(Bins)pool.pagetable[pagenum];
-        if (bin == B_PAGE)              // if large alloc
-        {
-            // Free pages
-            size_t npages = 1;
-            size_t n = pagenum;
-            while (++n < pool.npages && pool.pagetable[n] == B_PAGEPLUS)
-                npages++;
-            if (opts.options.mem_stomp)
-                memset(p, 0xF2, npages * PAGESIZE);
-            pool.freePages(pagenum, npages);
-        }
-        else
-        {
-            // Add to free list
-            List *list = cast(List*)p;
+        //printf("marking range: %p -> %p\n", pbot, ptop);
+        for (; p1 + type_size <= p2; p1 += type_size) {
+            for (size_t n = 0; n < type_size; n++) {
+                // scan bit set for this word
+                if (!(pm_bits[n / BITS_PER_WORD] & (1 << (n % BITS_PER_WORD))))
+                    continue;
 
 
-            if (opts.options.mem_stomp)
-                memset(p, 0xF2, binsize[bin]);
+                void* p = *(p1 + n);
 
 
-            list.next = gcx.bucket[bin];
-            gcx.bucket[bin] = list;
-        }
-    }
+                if (p < minAddr || p >= maxAddr)
+                    continue;
 
 
+                if ((cast(size_t)p & ~(PAGESIZE-1)) == pcache)
+                    continue;
 
 
-    /**
-     * Determine the base address of the block containing p.  If p is not a gc
-     * allocated pointer, return null.
-     */
-    void* addrOf(void *p)
-    {
-        if (!p)
-        {
-            return null;
-        }
+                Pool* pool = findPool(p);
+                if (pool)
+                {
+                    size_t offset = cast(size_t)(p - pool.baseAddr);
+                    size_t bit_i;
+                    size_t pn = offset / PAGESIZE;
+                    Bins   bin = cast(Bins)pool.pagetable[pn];
 
 
-        if (!thread_needLock())
-        {
-            return addrOfNoSync(p);
-        }
-        else synchronized (gcLock)
-        {
-            return addrOfNoSync(p);
-        }
-    }
+                    // Adjust bit to be at start of allocated memory block
+                    if (bin <= B_PAGE)
+                        bit_i = (offset & notbinsize[bin]) >> 4;
+                    else if (bin == B_PAGEPLUS)
+                    {
+                        do
+                        {
+                            --pn;
+                        }
+                        while (cast(Bins)pool.pagetable[pn] == B_PAGEPLUS);
+                        bit_i = pn * (PAGESIZE / 16);
+                    }
+                    else
+                    {
+                        // Don't mark bits in B_FREE pages
+                        continue;
+                    }
 
 
+                    if (bin >= B_PAGE) // Cache B_PAGE and B_PAGEPLUS lookups
+                        pcache = cast(size_t)p & ~(PAGESIZE-1);
 
 
-    //
-    //
-    //
-    void* addrOfNoSync(void *p)
-    {
-        if (!p)
-        {
-            return null;
+                    if (!pool.mark.test(bit_i))
+                    {
+                        pool.mark.set(bit_i);
+                        if (!pool.noscan.test(bit_i))
+                        {
+                            pool.scan.set(bit_i);
+                            changes = 1;
+                        }
+                    }
+                }
+            }
         }
         }
-
-        return gcx.findBase(p);
+        anychanges |= changes;
     }
 
     }
 
-
     /**
     /**
-     * Determine the allocated size of pointer p.  If p is an interior pointer
-     * or not a gc allocated pointer, return 0.
+     * Return number of full pages free'd.
      */
      */
-    size_t sizeOf(void *p)
+    size_t fullcollectshell()
     {
     {
-        if (!p)
-        {
-            return 0;
-        }
+        stats.collection_started();
+        scope (exit)
+            stats.collection_finished();
 
 
-        if (!thread_needLock())
+        // The purpose of the 'shell' is to ensure all the registers
+        // get put on the stack so they'll be scanned
+        void *sp;
+        size_t result;
+        version (GNU)
         {
         {
-            return sizeOfNoSync(p);
+            gcc.builtins.__builtin_unwind_init();
+            sp = & sp;
         }
         }
-        else synchronized (gcLock)
+        else version(LDC)
         {
         {
-            return sizeOfNoSync(p);
+            version(X86)
+            {
+                uint eax,ecx,edx,ebx,ebp,esi,edi;
+                asm
+                {
+                    mov eax[EBP], EAX      ;
+                    mov ecx[EBP], ECX      ;
+                    mov edx[EBP], EDX      ;
+                    mov ebx[EBP], EBX      ;
+                    mov ebp[EBP], EBP      ;
+                    mov esi[EBP], ESI      ;
+                    mov edi[EBP], EDI      ;
+                    mov  sp[EBP], ESP      ;
+                }
+            }
+            else version (X86_64)
+            {
+                ulong rax,rbx,rcx,rdx,rbp,rsi,rdi,r8,r9,r10,r11,r12,r13,r14,r15;
+                asm
+                {
+                    movq rax[RBP], RAX      ;
+                    movq rbx[RBP], RBX      ;
+                    movq rcx[RBP], RCX      ;
+                    movq rdx[RBP], RDX      ;
+                    movq rbp[RBP], RBP      ;
+                    movq rsi[RBP], RSI      ;
+                    movq rdi[RBP], RDI      ;
+                    movq r8 [RBP], R8       ;
+                    movq r9 [RBP], R9       ;
+                    movq r10[RBP], R10      ;
+                    movq r11[RBP], R11      ;
+                    movq r12[RBP], R12      ;
+                    movq r13[RBP], R13      ;
+                    movq r14[RBP], R14      ;
+                    movq r15[RBP], R15      ;
+                    movq  sp[RBP], RSP      ;
+                }
+            }
+            else
+            {
+                static assert( false, "Architecture not supported." );
+            }
         }
         }
-    }
-
-
-    //
-    //
-    //
-    private size_t sizeOfNoSync(void *p)
-    {
-        assert (p);
-
-        if (opts.options.sentinel)
-            p = sentinel_sub(p);
-
-        Pool* pool = gcx.findPool(p);
-        if (pool is null)
-            return 0;
-
-        auto biti = cast(size_t)(p - pool.baseAddr) / 16;
-        uint attrs = gcx.getAttr(pool, biti);
-
-        size_t size = gcx.findSize(p);
-        size_t pm_bitmask_size = 0;
-        if (has_pointermap(attrs))
-            pm_bitmask_size = size_t.sizeof;
-
-        if (opts.options.sentinel) {
-            // Check for interior pointer
-            // This depends on:
-            // 1) size is a power of 2 for less than PAGESIZE values
-            // 2) base of memory pool is aligned on PAGESIZE boundary
-            if (cast(size_t)p & (size - 1) & (PAGESIZE - 1))
-                return 0;
-            return size - SENTINEL_EXTRA - pm_bitmask_size;
+        else
+        {
+        asm
+        {
+            pushad              ;
+            mov sp[EBP],ESP     ;
         }
         }
-        else {
-            if (p == gcx.p_cache)
-                return gcx.size_cache;
-
-            // Check for interior pointer
-            // This depends on:
-            // 1) size is a power of 2 for less than PAGESIZE values
-            // 2) base of memory pool is aligned on PAGESIZE boundary
-            if (cast(size_t)p & (size - 1) & (PAGESIZE - 1))
-                return 0;
-
-            gcx.p_cache = p;
-            gcx.size_cache = size - pm_bitmask_size;
-
-            return gcx.size_cache;
         }
         }
-    }
-
-
-    /**
-     * Determine the base address of the block containing p.  If p is not a gc
-     * allocated pointer, return null.
-     */
-    BlkInfo query(void *p)
-    {
-        if (!p)
+        result = fullcollect(sp);
+        version (GNU)
         {
         {
-            BlkInfo i;
-            return  i;
+            // nothing to do
         }
         }
-
-        if (!thread_needLock())
+        else version(LDC)
         {
         {
-            return queryNoSync(p);
+            // nothing to do
         }
         }
-        else synchronized (gcLock)
+        else
         {
         {
-            return queryNoSync(p);
+        asm
+        {
+            popad               ;
         }
         }
-    }
-
-
-    //
-    //
-    //
-    BlkInfo queryNoSync(void *p)
-    {
-        assert(p);
-
-        return gcx.getInfo(p);
+        }
+        return result;
     }
 
 
     /**
     }
 
 
     /**
-     * Verify that pointer p:
-     *  1) belongs to this memory pool
-     *  2) points to the start of an allocated piece of memory
-     *  3) is not on a free list
+     *
      */
      */
-    void check(void *p)
+    size_t fullcollect(void *stackTop)
     {
     {
-        if (!p)
-        {
-            return;
-        }
+        size_t n;
+        Pool*  pool;
 
 
-        if (!thread_needLock())
-        {
-            checkNoSync(p);
-        }
-        else synchronized (gcLock)
-        {
-            checkNoSync(p);
-        }
-    }
+        debug(COLLECT_PRINTF) printf("Gcx.fullcollect()\n");
 
 
+        thread_suspendAll();
+        stats.world_stopped();
 
 
-    //
-    //
-    //
-    private void checkNoSync(void *p)
-    {
-        assert(p);
+        p_cache = null;
+        size_cache = 0;
 
 
-        if (opts.options.sentinel)
-            sentinel_Invariant(p);
-        debug (PTRCHECK)
+        anychanges = 0;
+        for (n = 0; n < pools.length; n++)
         {
         {
-            Pool*  pool;
-            size_t pagenum;
-            Bins   bin;
-            size_t size;
-
-            if (opts.options.sentinel)
-                p = sentinel_sub(p);
-            pool = gcx.findPool(p);
-            assert(pool);
-            pagenum = cast(size_t)(p - pool.baseAddr) / PAGESIZE;
-            bin = cast(Bins)pool.pagetable[pagenum];
-            assert(bin <= B_PAGE);
-            size = binsize[bin];
-            assert((cast(size_t)p & (size - 1)) == 0);
-
-            debug (PTRCHECK2)
-            {
-                if (bin < B_PAGE)
-                {
-                    // Check that p is not on a free list
-                    List *list;
-
-                    for (list = gcx.bucket[bin]; list; list = list.next)
-                    {
-                        assert(cast(void*)list != p);
-                    }
-                }
-            }
+            pool = pools[n];
+            pool.mark.zero();
+            pool.scan.zero();
+            pool.freebits.zero();
         }
         }
-    }
-
 
 
-    //
-    //
-    //
-    private void setStackBottom(void *p)
-    {
-        version (STACKGROWSDOWN)
+        // Mark each free entry, so it doesn't get scanned
+        for (n = 0; n < B_PAGE; n++)
         {
         {
-            //p = (void *)((uint *)p + 4);
-            if (p > gcx.stackBottom)
+            for (List *list = bucket[n]; list; list = list.next)
             {
             {
-                gcx.stackBottom = p;
+                pool = findPool(list);
+                assert(pool);
+                pool.freebits.set(cast(size_t)(cast(byte*)list - pool.baseAddr) / 16);
             }
         }
             }
         }
-        else
+
+        for (n = 0; n < pools.length; n++)
         {
         {
-            //p = (void *)((uint *)p - 4);
-            if (p < gcx.stackBottom)
-            {
-                gcx.stackBottom = cast(char*)p;
-            }
+            pool = pools[n];
+            pool.mark.copy(&pool.freebits);
         }
         }
-    }
 
 
+        rt_scanStaticData( &mark_conservative );
 
 
-    /**
-     * add p to list of roots
-     */
-    void addRoot(void *p)
-    {
-        if (!p)
+        if (!noStack)
         {
         {
-            return;
+            // Scan stacks and registers for each paused thread
+            thread_scanAll( &mark_conservative, stackTop );
         }
 
         }
 
-        if (!thread_needLock())
-        {
-            if (roots.append(p) is null)
-                onOutOfMemoryError();
-        }
-        else synchronized (gcLock)
+        // Scan roots
+        debug(COLLECT_PRINTF) printf("scan roots[]\n");
+        mark_conservative(roots.ptr, roots.ptr + roots.length);
+
+        // Scan ranges
+        debug(COLLECT_PRINTF) printf("scan ranges[]\n");
+        for (n = 0; n < ranges.length; n++)
         {
         {
-            if (roots.append(p) is null)
-                onOutOfMemoryError();
+            debug(COLLECT_PRINTF) printf("\t%x .. %x\n", ranges[n].pbot, ranges[n].ptop);
+            mark_conservative(ranges[n].pbot, ranges[n].ptop);
         }
         }
-    }
-
 
 
-    /**
-     * remove p from list of roots
-     */
-    void removeRoot(void *p)
-    {
-        if (!p)
-        {
-            return;
-        }
-
-        bool r;
-        if (!thread_needLock())
-        {
-            r = roots.remove(p);
-        }
-        else synchronized (gcLock)
+        debug(COLLECT_PRINTF) printf("\tscan heap\n");
+        while (anychanges)
         {
         {
-            r = roots.remove(p);
-        }
-        assert (r);
-    }
+            anychanges = 0;
+            for (n = 0; n < pools.length; n++)
+            {
+                uint *bbase;
+                uint *b;
+                uint *btop;
 
 
+                pool = pools[n];
 
 
-    /**
-     * add range to scan for roots
-     */
-    void addRange(void *p, size_t sz)
-    {
-        if (!p || !sz)
-        {
-            return;
-        }
+                bbase = pool.scan.base();
+                btop = bbase + pool.scan.nwords;
+                for (b = bbase; b < btop;)
+                {
+                    Bins   bin;
+                    size_t pn;
+                    size_t u;
+                    size_t bitm;
+                    byte*  o;
 
 
-        if (!thread_needLock())
-        {
-            if (ranges.append(Range(p, p+sz)) is null)
-                onOutOfMemoryError();
-        }
-        else synchronized (gcLock)
-        {
-            if (ranges.append(Range(p, p+sz)) is null)
-                onOutOfMemoryError();
-        }
-    }
+                    bitm = *b;
+                    if (!bitm)
+                    {
+                        b++;
+                        continue;
+                    }
+                    *b = 0;
 
 
+                    o = pool.baseAddr + (b - bbase) * 32 * 16;
+                    if (!(bitm & 0xFFFF))
+                    {
+                        bitm >>= 16;
+                        o += 16 * 16;
+                    }
+                    for (; bitm; o += 16, bitm >>= 1)
+                    {
+                        if (!(bitm & 1))
+                            continue;
 
 
-    /**
-     * remove range
-     */
-    void removeRange(void *p)
-    {
-        if (!p)
-        {
-            return;
-        }
+                        pn = cast(size_t)(o - pool.baseAddr) / PAGESIZE;
+                        bin = cast(Bins)pool.pagetable[pn];
+                        if (bin < B_PAGE) {
+                            if (opts.options.conservative)
+                                mark_conservative(o, o + binsize[bin]);
+                            else {
+                                auto end_of_blk = cast(size_t**)(o +
+                                        binsize[bin] - size_t.sizeof);
+                                size_t* pm_bitmask = *end_of_blk;
+                                mark(o, end_of_blk, pm_bitmask);
+                            }
+                        }
+                        else if (bin == B_PAGE || bin == B_PAGEPLUS)
+                        {
+                            if (bin == B_PAGEPLUS)
+                            {
+                                while (pool.pagetable[pn - 1] != B_PAGE)
+                                    pn--;
+                            }
+                            u = 1;
+                            while (pn + u < pool.npages &&
+                                    pool.pagetable[pn + u] == B_PAGEPLUS)
+                                u++;
 
 
-        bool r;
-        if (!thread_needLock())
-        {
-            r = ranges.remove(Range(p, null));
-        }
-        else synchronized (gcLock)
-        {
-            r = ranges.remove(Range(p, null));
+                            size_t blk_size = u * PAGESIZE;
+                            if (opts.options.conservative)
+                                mark_conservative(o, o + blk_size);
+                            else {
+                                auto end_of_blk = cast(size_t**)(o + blk_size -
+                                        size_t.sizeof);
+                                size_t* pm_bitmask = *end_of_blk;
+                                mark(o, end_of_blk, pm_bitmask);
+                            }
+                        }
+                    }
+                }
+            }
         }
         }
-        assert (r);
-    }
-
-
-    /**
-     * do full garbage collection
-     */
-    void fullCollect()
-    {
 
 
-        if (!thread_needLock())
-        {
-            gcx.fullcollectshell();
-        }
-        else synchronized (gcLock)
-        {
-            gcx.fullcollectshell();
-        }
+        thread_resumeAll();
+        stats.world_started();
 
 
-        version (none)
+        // Free up everything not marked
+        debug(COLLECT_PRINTF) printf("\tfree'ing\n");
+        size_t freedpages = 0;
+        size_t freed = 0;
+        for (n = 0; n < pools.length; n++)
         {
         {
-            GCStats stats;
-            getStats(stats);
-        }
-
-    }
+            pool = pools[n];
+            uint*  bbase = pool.mark.base();
+            size_t pn;
+            for (pn = 0; pn < pool.npages; pn++, bbase += PAGESIZE / (32 * 16))
+            {
+                Bins bin = cast(Bins)pool.pagetable[pn];
 
 
+                if (bin < B_PAGE)
+                {
+                    auto size = binsize[bin];
+                    byte* p = pool.baseAddr + pn * PAGESIZE;
+                    byte* ptop = p + PAGESIZE;
+                    size_t bit_i = pn * (PAGESIZE/16);
+                    size_t bit_stride = size / 16;
 
 
-    /**
-     * do full garbage collection ignoring roots
-     */
-    void fullCollectNoStack()
+    version(none) // BUG: doesn't work because freebits() must also be cleared
     {
     {
-        if (!thread_needLock())
-        {
-            gcx.noStack++;
-            gcx.fullcollectshell();
-            gcx.noStack--;
-        }
-        else synchronized (gcLock)
-        {
-            gcx.noStack++;
-            gcx.fullcollectshell();
-            gcx.noStack--;
-        }
-    }
+                    // If free'd entire page
+                    if (bbase[0] == 0 && bbase[1] == 0 && bbase[2] == 0 &&
+                            bbase[3] == 0 && bbase[4] == 0 && bbase[5] == 0 &&
+                            bbase[6] == 0 && bbase[7] == 0)
+                    {
+                        for (; p < ptop; p += size, bit_i += bit_stride)
+                        {
+                            if (pool.finals.nbits && pool.finals.testClear(bit_i)) {
+                                if (opts.options.sentinel)
+                                    rt_finalize(cast(List *)sentinel_add(p), false/*noStack > 0*/);
+                                else
+                                    rt_finalize(cast(List *)p, false/*noStack > 0*/);
+                            }
+                            this.clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
 
 
+                            List *list = cast(List *)p;
 
 
-    /**
-     * minimize free space usage
-     */
-    void minimize()
-    {
-        if (!thread_needLock())
-        {
-            gcx.minimize();
-        }
-        else synchronized (gcLock)
-        {
-            gcx.minimize();
-        }
+                            if (opts.options.mem_stomp)
+                                memset(p, 0xF3, size);
+                        }
+                        pool.pagetable[pn] = B_FREE;
+                        freed += PAGESIZE;
+                        continue;
+                    }
     }
     }
+                    for (; p < ptop; p += size, bit_i += bit_stride)
+                    {
+                        if (!pool.mark.test(bit_i))
+                        {
+                            if (opts.options.sentinel)
+                                sentinel_Invariant(sentinel_add(p));
 
 
+                            pool.freebits.set(bit_i);
+                            if (pool.finals.nbits && pool.finals.testClear(bit_i)) {
+                                if (opts.options.sentinel)
+                                    rt_finalize(cast(List *)sentinel_add(p), false/*noStack > 0*/);
+                                else
+                                    rt_finalize(cast(List *)p, false/*noStack > 0*/);
+                            }
+                            clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
 
 
-    /**
-     * Retrieve statistics about garbage collection.
-     * Useful for debugging and tuning.
-     */
-    void getStats(out GCStats stats)
-    {
-        if (!thread_needLock())
-        {
-            getStatsNoSync(stats);
-        }
-        else synchronized (gcLock)
-        {
-            getStatsNoSync(stats);
-        }
-    }
-
+                            List *list = cast(List *)p;
 
 
-    //
-    //
-    //
-    private void getStatsNoSync(out GCStats stats)
-    {
-        size_t psize = 0;
-        size_t usize = 0;
-        size_t flsize = 0;
+                            if (opts.options.mem_stomp)
+                                memset(p, 0xF3, size);
 
 
-        size_t n;
-        size_t bsize = 0;
+                            freed += size;
+                        }
+                    }
+                }
+                else if (bin == B_PAGE)
+                {
+                    size_t bit_i = pn * (PAGESIZE / 16);
+                    if (!pool.mark.test(bit_i))
+                    {
+                        byte *p = pool.baseAddr + pn * PAGESIZE;
+                        if (opts.options.sentinel)
+                            sentinel_Invariant(sentinel_add(p));
+                        if (pool.finals.nbits && pool.finals.testClear(bit_i)) {
+                            if (opts.options.sentinel)
+                                rt_finalize(sentinel_add(p), false/*noStack > 0*/);
+                            else
+                                rt_finalize(p, false/*noStack > 0*/);
+                        }
+                        clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
 
 
-        memset(&stats, 0, GCStats.sizeof);
+                        debug(COLLECT_PRINTF) printf("\tcollecting big %x\n", p);
+                        pool.pagetable[pn] = B_FREE;
+                        freedpages++;
+                        if (opts.options.mem_stomp)
+                            memset(p, 0xF3, PAGESIZE);
+                        while (pn + 1 < pool.npages && pool.pagetable[pn + 1] == B_PAGEPLUS)
+                        {
+                            pn++;
+                            pool.pagetable[pn] = B_FREE;
+                            freedpages++;
 
 
-        for (n = 0; n < pools.length; n++)
-        {
-            Pool* pool = pools[n];
-            psize += pool.npages * PAGESIZE;
-            for (size_t j = 0; j < pool.npages; j++)
-            {
-                Bins bin = cast(Bins)pool.pagetable[j];
-                if (bin == B_FREE)
-                    stats.freeblocks++;
-                else if (bin == B_PAGE)
-                    stats.pageblocks++;
-                else if (bin < B_PAGE)
-                    bsize += PAGESIZE;
+                            if (opts.options.mem_stomp)
+                            {
+                                p += PAGESIZE;
+                                memset(p, 0xF3, PAGESIZE);
+                            }
+                        }
+                    }
+                }
             }
         }
 
             }
         }
 
-        for (n = 0; n < B_PAGE; n++)
-        {
-            for (List *list = gcx.bucket[n]; list; list = list.next)
-                flsize += binsize[n];
-        }
-
-        usize = bsize - flsize;
-
-        stats.poolsize = psize;
-        stats.usedsize = bsize - flsize;
-        stats.freelistsize = flsize;
-    }
-
-    /******************* weak-reference support *********************/
-
-    // call locked if necessary
-    private T locked(T)(in T delegate() code)
-    {
-        if (thread_needLock)
-            synchronized(gcLock) return code();
-        else
-           return code();
-    }
-
-    private struct WeakPointer
-    {
-        Object reference;
+        // Zero buckets
+        bucket[] = null;
 
 
-        void ondestroy(Object r)
+        // Free complete pages, rebuild free list
+        debug(COLLECT_PRINTF) printf("\tfree complete pages\n");
+        size_t recoveredpages = 0;
+        for (n = 0; n < pools.length; n++)
         {
         {
-            assert(r is reference);
-            // lock for memory consistency (parallel readers)
-            // also ensures that weakpointerDestroy can be called while another
-            // thread is freeing the reference with "delete"
-            locked!(void)({ reference = null; });
-        }
-    }
-
-    /**
-     * Create a weak pointer to the given object.
-     * Returns a pointer to an opaque struct allocated in C memory.
-     */
-    void* weakpointerCreate( Object r )
-    {
-        if (r)
-       {
-            // must be allocated in C memory
-            // 1. to hide the reference from the GC
-            // 2. the GC doesn't scan delegates added by rt_attachDisposeEvent
-            //    for references
-            auto wp = cast(WeakPointer*)(cstdlib.malloc(WeakPointer.sizeof));
-            if (!wp)
-                onOutOfMemoryError();
-            wp.reference = r;
-            rt_attachDisposeEvent(r, &wp.ondestroy);
-            return wp;
-        }
-        return null;
-    }
-
-    /**
-     * Destroy a weak pointer returned by weakpointerCreate().
-     * If null is passed, nothing happens.
-     */
-    void weakpointerDestroy( void* p )
-    {
-        if (p)
-       {
-            auto wp = cast(WeakPointer*)p;
-            // must be extra careful about the GC or parallel threads
-            // finalizing the reference at the same time
-            locked!(void)({
-                   if (wp.reference)
-                       rt_detachDisposeEvent(wp.reference, &wp.ondestroy);
-                  });
-            cstdlib.free(wp);
-        }
-    }
-
-    /**
-     * Query a weak pointer and return either the object passed to
-     * weakpointerCreate, or null if it was free'd in the meantime.
-     * If null is passed, null is returned.
-     */
-    Object weakpointerGet( void* p )
-    {
-        if (p)
-       {
-            // NOTE: could avoid the lock by using Fawzi style GC counters but
-            // that'd require core.sync.Atomic and lots of care about memory
-            // consistency it's an optional optimization see
-            // http://dsource.org/projects/tango/browser/trunk/user/tango/core/Lifetime.d?rev=5100#L158
-            return locked!(Object)({
-                  return (cast(WeakPointer*)p).reference;
-                  });
-            }
-    }
-}
-
-
-/* ============================ Gcx =============================== */
-
-enum
-{
-    PAGESIZE =    4096,
-    POOLSIZE =   (4096*256),
-}
-
-
-enum
-{
-    B_16,
-    B_32,
-    B_64,
-    B_128,
-    B_256,
-    B_512,
-    B_1024,
-    B_2048,
-    B_PAGE,             // start of large alloc
-    B_PAGEPLUS,         // continuation of large alloc
-    B_FREE,             // free page
-    B_MAX
-}
-
-
-alias ubyte Bins;
-
-
-struct List
-{
-    List *next;
-}
-
-
-struct Range
-{
-    void *pbot;
-    void *ptop;
-    int opCmp(in Range other)
-    {
-        if (pbot < other.pbot)
-            return -1;
-        else
-        return cast(int)(pbot > other.pbot);
-    }
-}
+            pool = pools[n];
+            for (size_t pn = 0; pn < pool.npages; pn++)
+            {
+                Bins   bin = cast(Bins)pool.pagetable[pn];
+                size_t bit_i;
+                size_t u;
 
 
+                if (bin < B_PAGE)
+                {
+                    size_t size = binsize[bin];
+                    size_t bit_stride = size / 16;
+                    size_t bit_base = pn * (PAGESIZE / 16);
+                    size_t bit_top = bit_base + (PAGESIZE / 16);
+                    byte*  p;
 
 
-const uint binsize[B_MAX] = [ 16,32,64,128,256,512,1024,2048,4096 ];
-const uint notbinsize[B_MAX] = [ ~(16u-1),~(32u-1),~(64u-1),~(128u-1),~(256u-1),
-                                ~(512u-1),~(1024u-1),~(2048u-1),~(4096u-1) ];
+                    bit_i = bit_base;
+                    for (; bit_i < bit_top; bit_i += bit_stride)
+                    {
+                        if (!pool.freebits.test(bit_i))
+                            goto Lnotfree;
+                    }
+                    pool.pagetable[pn] = B_FREE;
+                    recoveredpages++;
+                    continue;
 
 
-DynArray!(void*) roots;
+                 Lnotfree:
+                    p = pool.baseAddr + pn * PAGESIZE;
+                    for (u = 0; u < PAGESIZE; u += size)
+                    {
+                        bit_i = bit_base + u / 16;
+                        if (pool.freebits.test(bit_i))
+                        {
+                            List *list = cast(List *)(p + u);
+                            // avoid unnecessary writes
+                            if (list.next != bucket[bin])
+                                list.next = bucket[bin];
+                            bucket[bin] = list;
+                        }
+                    }
+                }
+            }
+        }
 
 
-DynArray!(Range) ranges;
+        debug(COLLECT_PRINTF) printf("recovered pages = %d\n", recoveredpages);
+        debug(COLLECT_PRINTF) printf("\tfree'd %u bytes, %u pages from %u pools\n", freed, freedpages, pools.length);
 
 
-DynArray!(Pool) pools;
+        return freedpages + recoveredpages;
+    }
 
 
 
 
-/* ============================ Gcx =============================== */
+    /**
+     *
+     */
+    uint getAttr(Pool* pool, size_t bit_i)
+    in
+    {
+        assert( pool );
+    }
+    body
+    {
+        uint attrs;
 
 
+        if (pool.finals.nbits &&
+            pool.finals.test(bit_i))
+            attrs |= BlkAttr.FINALIZE;
+        if (pool.noscan.test(bit_i))
+            attrs |= BlkAttr.NO_SCAN;
+//        if (pool.nomove.nbits &&
+//            pool.nomove.test(bit_i))
+//            attrs |= BlkAttr.NO_MOVE;
+        return attrs;
+    }
 
 
-struct Gcx
-{
 
 
-    void *p_cache;
-    size_t size_cache;
+    /**
+     *
+     */
+    void setAttr(Pool* pool, size_t bit_i, uint mask)
+    in
+    {
+        assert( pool );
+    }
+    body
+    {
+        if (mask & BlkAttr.FINALIZE)
+        {
+            if (!pool.finals.nbits)
+                pool.finals.alloc(pool.mark.nbits);
+            pool.finals.set(bit_i);
+        }
+        if (mask & BlkAttr.NO_SCAN)
+        {
+            pool.noscan.set(bit_i);
+        }
+//        if (mask & BlkAttr.NO_MOVE)
+//        {
+//            if (!pool.nomove.nbits)
+//                pool.nomove.alloc(pool.mark.nbits);
+//            pool.nomove.set(bit_i);
+//        }
+    }
 
 
-    uint noStack;       // !=0 means don't scan stack
-    uint anychanges;
-    void *stackBottom;
-    uint inited;
-    int disabled;       // turn off collections if >0
 
 
-    byte *minAddr;      // min(baseAddr)
-    byte *maxAddr;      // max(topAddr)
+    /**
+     *
+     */
+    void clrAttr(Pool* pool, size_t bit_i, uint mask)
+    in
+    {
+        assert( pool );
+    }
+    body
+    {
+        if (mask & BlkAttr.FINALIZE && pool.finals.nbits)
+            pool.finals.clear(bit_i);
+        if (mask & BlkAttr.NO_SCAN)
+            pool.noscan.clear(bit_i);
+//        if (mask & BlkAttr.NO_MOVE && pool.nomove.nbits)
+//            pool.nomove.clear(bit_i);
+    }
 
 
-    List *bucket[B_MAX];        // free list for each size
 
 
     void initialize()
     {
         int dummy;
 
 
     void initialize()
     {
         int dummy;
-        (cast(byte*)this)[0 .. Gcx.sizeof] = 0;
         stackBottom = cast(char*)&dummy;
         stackBottom = cast(char*)&dummy;
-        //printf("gcx = %p, self = %x\n", this, self);
+        opts.parse(cstdlib.getenv("D_GC_OPTS"));
+        gcLock = GCLock.classinfo;
         inited = 1;
         inited = 1;
+        setStackBottom(rt_stackBottom());
+        stats = Stats(this);
     }
 
 
     }
 
 
-    void Invariant() { }
-
-
-    invariant
+    /**
+     *
+     */
+    void enable()
     {
     {
-        if (inited)
+        if (!thread_needLock())
         {
         {
-        //printf("Gcx.invariant(): this = %p\n", this);
-            size_t i;
-
-            for (i = 0; i < pools.length; i++)
-            {
-                Pool* pool = pools[i];
-                pool.Invariant();
-                if (i == 0)
-                {
-                    assert(minAddr == pool.baseAddr);
-                }
-                if (i + 1 < pools.length)
-                {
-                    assert(*pool < pools[i + 1]);
-                }
-                else if (i + 1 == pools.length)
-                {
-                    assert(maxAddr == pool.topAddr);
-                }
-            }
-
-            roots.Invariant();
-            ranges.Invariant();
-
-            for (i = 0; i < ranges.length; i++)
-            {
-                assert(ranges[i].pbot);
-                assert(ranges[i].ptop);
-                assert(ranges[i].pbot <= ranges[i].ptop);
-            }
-
-            for (i = 0; i < B_PAGE; i++)
-            {
-                for (List *list = bucket[i]; list; list = list.next)
-                {
-                }
-            }
+            assert(this.disabled > 0);
+            this.disabled--;
+        }
+        else synchronized (gcLock)
+        {
+            assert(this.disabled > 0);
+            this.disabled--;
         }
     }
 
 
     /**
         }
     }
 
 
     /**
-     * Find Pool that pointer is in.
-     * Return null if not in a Pool.
-     * Assume pools is sorted.
+     *
      */
      */
-    Pool *findPool(void *p)
+    void disable()
     {
     {
-        if (p >= minAddr && p < maxAddr)
+        if (!thread_needLock())
         {
         {
-            if (pools.length == 1)
-            {
-                return pools[0];
-            }
-
-            for (size_t i = 0; i < pools.length; i++)
-            {
-                Pool* pool = pools[i];
-                if (p < pool.topAddr)
-                {
-                    if (pool.baseAddr <= p)
-                        return pool;
-                    break;
-                }
-            }
+            this.disabled++;
+        }
+        else synchronized (gcLock)
+        {
+            this.disabled++;
         }
         }
-        return null;
     }
 
 
     /**
     }
 
 
     /**
-     * Find base address of block containing pointer p.
-     * Returns null if not a gc'd pointer
+     *
      */
      */
-    void* findBase(void *p)
+    uint getAttr(void* p)
     {
     {
-        Pool *pool;
+        if (!p)
+        {
+            return 0;
+        }
 
 
-        pool = findPool(p);
-        if (pool)
+        uint go()
         {
         {
-            size_t offset = cast(size_t)(p - pool.baseAddr);
-            size_t pn = offset / PAGESIZE;
-            Bins   bin = cast(Bins)pool.pagetable[pn];
+            Pool* pool = this.findPool(p);
+            uint  old_attrs = 0;
 
 
-            // Adjust bit to be at start of allocated memory block
-            if (bin <= B_PAGE)
-            {
-                return pool.baseAddr + (offset & notbinsize[bin]);
-            }
-            else if (bin == B_PAGEPLUS)
+            if (pool)
             {
             {
-                do
-                {
-                    --pn, offset -= PAGESIZE;
-                } while (cast(Bins)pool.pagetable[pn] == B_PAGEPLUS);
+                auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
 
 
-                return pool.baseAddr + (offset & (offset.max ^ (PAGESIZE-1)));
-            }
-            else
-            {
-                // we are in a B_FREE page
-                return null;
+                old_attrs = this.getAttr(pool, bit_i);
             }
             }
+            return old_attrs;
         }
         }
-        return null;
-    }
-
-
-    /**
-     * Find size of pointer p.
-     * Returns 0 if not a gc'd pointer
-     */
-    size_t findSize(void *p)
-    {
-        Pool*  pool;
-        size_t size = 0;
 
 
-        pool = findPool(p);
-        if (pool)
+        if (!thread_needLock())
         {
         {
-            size_t pagenum;
-            Bins   bin;
-
-            pagenum = cast(size_t)(p - pool.baseAddr) / PAGESIZE;
-            bin = cast(Bins)pool.pagetable[pagenum];
-            size = binsize[bin];
-            if (bin == B_PAGE)
-            {
-                ubyte* pt;
-                size_t i;
-
-                pt = &pool.pagetable[0];
-                for (i = pagenum + 1; i < pool.npages; i++)
-                {
-                    if (pt[i] != B_PAGEPLUS)
-                        break;
-                }
-                size = (i - pagenum) * PAGESIZE;
-            }
+            return go();
+        }
+        else synchronized (gcLock)
+        {
+            return go();
         }
         }
-        return size;
     }
 
 
     /**
      *
      */
     }
 
 
     /**
      *
      */
-    BlkInfo getInfo(void* p)
+    uint setAttr(void* p, uint mask)
     {
     {
-        Pool*   pool;
-        BlkInfo info;
-
-        pool = findPool(p);
-        if (pool)
+        if (!p)
         {
         {
-            size_t offset = cast(size_t)(p - pool.baseAddr);
-            size_t pn = offset / PAGESIZE;
-            Bins   bin = cast(Bins)pool.pagetable[pn];
-
-            ////////////////////////////////////////////////////////////////////
-            // findAddr
-            ////////////////////////////////////////////////////////////////////
-
-            if (bin <= B_PAGE)
-            {
-                info.base = pool.baseAddr + (offset & notbinsize[bin]);
-            }
-            else if (bin == B_PAGEPLUS)
-            {
-                do
-                {
-                    --pn, offset -= PAGESIZE;
-                }
-                while (cast(Bins)pool.pagetable[pn] == B_PAGEPLUS);
-
-                info.base = pool.baseAddr + (offset & (offset.max ^ (PAGESIZE-1)));
-
-                // fix bin for use by size calc below
-                bin = cast(Bins)pool.pagetable[pn];
-            }
+            return 0;
+        }
 
 
-            ////////////////////////////////////////////////////////////////////
-            // findSize
-            ////////////////////////////////////////////////////////////////////
+        uint go()
+        {
+            Pool* pool = this.findPool(p);
+            uint  old_attrs = 0;
 
 
-            info.size = binsize[bin];
-            if (bin == B_PAGE)
+            if (pool)
             {
             {
-                ubyte* pt;
-                size_t i;
+                auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
 
 
-                pt = &pool.pagetable[0];
-                for (i = pn + 1; i < pool.npages; i++)
-                {
-                    if (pt[i] != B_PAGEPLUS)
-                        break;
-                }
-                info.size = (i - pn) * PAGESIZE;
+                old_attrs = this.getAttr(pool, bit_i);
+                this.setAttr(pool, bit_i, mask);
             }
             }
+            return old_attrs;
+        }
 
 
-            ////////////////////////////////////////////////////////////////////
-            // getAttr
-            ////////////////////////////////////////////////////////////////////
-
-            info.attr = getAttr(pool, cast(size_t)(offset / 16));
-            if (!(info.attr & BlkAttr.NO_SCAN))
-                info.size -= (size_t*).sizeof;  // bitmask
+        if (!thread_needLock())
+        {
+            return go();
+        }
+        else synchronized (gcLock)
+        {
+            return go();
         }
         }
-        return info;
     }
 
 
     /**
     }
 
 
     /**
-     * Compute bin for size.
+     *
      */
      */
-    static Bins findBin(size_t size)
+    uint clrAttr(void* p, uint mask)
     {
     {
-        Bins bin;
-        if (size <= 256)
+        if (!p)
         {
         {
-            if (size <= 64)
-            {
-                if (size <= 16)
-                    bin = B_16;
-                else if (size <= 32)
-                    bin = B_32;
-                else
-                    bin = B_64;
-            }
-            else
-            {
-                if (size <= 128)
-                    bin = B_128;
-                else
-                    bin = B_256;
-            }
+            return 0;
         }
         }
-        else
+
+        uint go()
         {
         {
-            if (size <= 1024)
-            {
-                if (size <= 512)
-                    bin = B_512;
-                else
-                    bin = B_1024;
-            }
-            else
+            Pool* pool = this.findPool(p);
+            uint  old_attrs = 0;
+
+            if (pool)
             {
             {
-                if (size <= 2048)
-                    bin = B_2048;
-                else
-                    bin = B_PAGE;
+                auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
+
+                old_attrs = this.getAttr(pool, bit_i);
+                this.clrAttr(pool, bit_i, mask);
             }
             }
+            return old_attrs;
+        }
+
+        if (!thread_needLock())
+        {
+            return go();
+        }
+        else synchronized (gcLock)
+        {
+            return go();
         }
         }
-        return bin;
     }
 
 
     /**
     }
 
 
     /**
-     * Allocate a new pool of at least size bytes.
-     * Sort it into pools.
-     * Mark all memory in the pool as B_FREE.
-     * Return the actual number of bytes reserved or 0 on error.
+     *
      */
      */
-    size_t reserve(size_t size)
+    void *malloc(size_t size, uint attrs, PointerMap ptrmap)
     {
     {
-        size_t npages = (size + PAGESIZE - 1) / PAGESIZE;
-        Pool*  pool = newPool(npages);
+        if (!size)
+        {
+            return null;
+        }
 
 
-        if (!pool)
-            return 0;
-        return pool.npages * PAGESIZE;
+        if (!thread_needLock())
+        {
+            return mallocNoSync(size, attrs, ptrmap.bits.ptr);
+        }
+        else synchronized (gcLock)
+        {
+            return mallocNoSync(size, attrs, ptrmap.bits.ptr);
+        }
     }
 
 
     }
 
 
-    /**
-     * Minimizes physical memory usage by returning free pools to the OS.
-     */
-    void minimize()
+    //
+    //
+    //
+    private void *mallocNoSync(size_t size, uint attrs, size_t* pm_bitmask)
     {
     {
-        size_t n;
-        size_t pn;
-        Pool*  pool;
+        assert(size != 0);
 
 
-        for (n = 0; n < pools.length; n++)
+        stats.malloc_started(size, attrs, pm_bitmask);
+        scope (exit)
+            stats.malloc_finished(p);
+
+        void *p = null;
+        Bins bin;
+
+        if (opts.options.sentinel)
+            size += SENTINEL_EXTRA;
+
+        bool has_pm = has_pointermap(attrs);
+        if (has_pm)
+            size += size_t.sizeof;
+
+        // Compute size bin
+        // Cache previous binsize lookup - Dave Fladebo.
+        static size_t lastsize = -1;
+        static Bins lastbin;
+        if (size == lastsize)
+            bin = lastbin;
+        else
         {
         {
-            pool = pools[n];
-            for (pn = 0; pn < pool.npages; pn++)
+            bin = this.findBin(size);
+            lastsize = size;
+            lastbin = bin;
+        }
+
+        size_t capacity; // to figure out where to store the bitmask
+        if (bin < B_PAGE)
+        {
+            p = this.bucket[bin];
+            if (p is null)
             {
             {
-                if (cast(Bins)pool.pagetable[pn] != B_FREE)
-                    break;
+                if (!this.allocPage(bin) && !this.disabled)   // try to find a new page
+                {
+                    if (!thread_needLock())
+                    {
+                        /* Then we haven't locked it yet. Be sure
+                         * and lock for a collection, since a finalizer
+                         * may start a new thread.
+                         */
+                        synchronized (gcLock)
+                        {
+                            this.fullcollectshell();
+                        }
+                    }
+                    else if (!this.fullcollectshell())       // collect to find a new page
+                    {
+                        //this.newPool(1);
+                    }
+                }
+                if (!this.bucket[bin] && !this.allocPage(bin))
+                {
+                    this.newPool(1);         // allocate new pool to find a new page
+                    int result = this.allocPage(bin);
+                    if (!result)
+                        onOutOfMemoryError();
+                }
+                p = this.bucket[bin];
             }
             }
-            if (pn < pool.npages)
-                continue;
-            pool.Dtor();
-            pools.remove_at(n);
-            n--;
+            capacity = binsize[bin];
+
+            // Return next item from free list
+            this.bucket[bin] = (cast(List*)p).next;
+            if (!(attrs & BlkAttr.NO_SCAN))
+                memset(p + size, 0, capacity - size);
+            if (opts.options.mem_stomp)
+                memset(p, 0xF0, size);
         }
         }
-        minAddr = pools[0].baseAddr;
-        maxAddr = pools[pools.length - 1].topAddr;
+        else
+        {
+            p = this.bigAlloc(size);
+            if (!p)
+                onOutOfMemoryError();
+            // Round the size up to the number of pages needed to store it
+            size_t npages = (size + PAGESIZE - 1) / PAGESIZE;
+            capacity = npages * PAGESIZE;
+        }
+
+        // Store the bit mask AFTER SENTINEL_POST
+        // TODO: store it BEFORE, so the bitmask is protected too
+        if (has_pm) {
+            auto end_of_blk = cast(size_t**)(p + capacity - size_t.sizeof);
+            *end_of_blk = pm_bitmask;
+            size -= size_t.sizeof;
+        }
+
+        if (opts.options.sentinel) {
+            size -= SENTINEL_EXTRA;
+            p = sentinel_add(p);
+            sentinel_init(p, size);
+        }
+
+        if (attrs)
+        {
+            Pool *pool = this.findPool(p);
+            assert(pool);
+
+            this.setAttr(pool, cast(size_t)(p - pool.baseAddr) / 16, attrs);
+        }
+        return p;
     }
 
 
     /**
     }
 
 
     /**
-     * Allocate a chunk of memory that is larger than a page.
-     * Return null if out of memory.
+     *
      */
      */
-    void *bigAlloc(size_t size)
+    void *calloc(size_t size, uint attrs, PointerMap ptrmap)
     {
     {
-        Pool*  pool;
-        size_t npages;
-        size_t n;
-        size_t pn;
-        size_t freedpages;
-        void*  p;
-        int    state;
-
-        npages = (size + PAGESIZE - 1) / PAGESIZE;
+        if (!size)
+        {
+            return null;
+        }
 
 
-        for (state = 0; ; )
+        if (!thread_needLock())
         {
         {
-            // This code could use some refinement when repeatedly
-            // allocating very large arrays.
+            return callocNoSync(size, attrs, ptrmap.bits.ptr);
+        }
+        else synchronized (gcLock)
+        {
+            return callocNoSync(size, attrs, ptrmap.bits.ptr);
+        }
+    }
 
 
-            for (n = 0; n < pools.length; n++)
-            {
-                pool = pools[n];
-                pn = pool.allocPages(npages);
-                if (pn != OPFAIL)
-                    goto L1;
-            }
 
 
-            // Failed
-            switch (state)
-            {
-            case 0:
-                if (disabled)
-                {
-                    state = 1;
-                    continue;
-                }
-                // Try collecting
-                freedpages = fullcollectshell();
-                if (freedpages >= pools.length * ((POOLSIZE / PAGESIZE) / 4))
-                {
-                    state = 1;
-                    continue;
-                }
-                // Release empty pools to prevent bloat
-                minimize();
-                // Allocate new pool
-                pool = newPool(npages);
-                if (!pool)
-                {
-                    state = 2;
-                    continue;
-                }
-                pn = pool.allocPages(npages);
-                assert(pn != OPFAIL);
-                goto L1;
-            case 1:
-                // Release empty pools to prevent bloat
-                minimize();
-                // Allocate new pool
-                pool = newPool(npages);
-                if (!pool)
-                    goto Lnomemory;
-                pn = pool.allocPages(npages);
-                assert(pn != OPFAIL);
-                goto L1;
-            case 2:
-                goto Lnomemory;
-            default:
-                assert(false);
-            }
-        }
+    //
+    //
+    //
+    private void *callocNoSync(size_t size, uint attrs, size_t* pm_bitmask)
+    {
+        assert(size != 0);
 
 
-      L1:
-        pool.pagetable[pn] = B_PAGE;
-        if (npages > 1)
-            memset(&pool.pagetable[pn + 1], B_PAGEPLUS, npages - 1);
-        p = pool.baseAddr + pn * PAGESIZE;
-        memset(cast(char *)p + size, 0, npages * PAGESIZE - size);
-        if (opts.options.mem_stomp)
-            memset(p, 0xF1, size);
+        void *p = mallocNoSync(size, attrs, pm_bitmask);
+        memset(p, 0, size);
         return p;
         return p;
-
-      Lnomemory:
-        return null; // let mallocNoSync handle the error
     }
 
 
     /**
     }
 
 
     /**
-     * Allocate a new pool with at least npages in it.
-     * Sort it into pools.
-     * Return null if failed.
+     *
      */
      */
-    Pool *newPool(size_t npages)
+    void *realloc(void *p, size_t size, uint attrs, PointerMap ptrmap)
     {
     {
-        // Minimum of POOLSIZE
-        if (npages < POOLSIZE/PAGESIZE)
-            npages = POOLSIZE/PAGESIZE;
-        else if (npages > POOLSIZE/PAGESIZE)
+        if (!thread_needLock())
         {
         {
-            // Give us 150% of requested size, so there's room to extend
-            auto n = npages + (npages >> 1);
-            if (n < size_t.max/PAGESIZE)
-                npages = n;
+            return reallocNoSync(p, size, attrs, ptrmap.bits.ptr);
         }
         }
-
-        // Allocate successively larger pools up to 8 megs
-        if (pools.length)
+        else synchronized (gcLock)
         {
         {
-            size_t n = pools.length;
-            if (n > 8)
-                n = 8;                  // cap pool size at 8 megs
-            n *= (POOLSIZE / PAGESIZE);
-            if (npages < n)
-                npages = n;
+            return reallocNoSync(p, size, attrs, ptrmap.bits.ptr);
         }
         }
+    }
 
 
-        Pool p;
-        p.initialize(npages);
-        if (!p.baseAddr)
+
+    //
+    //
+    //
+    private void *reallocNoSync(void *p, size_t size, uint attrs,
+            size_t* pm_bitmask)
+    {
+        if (!size)
         {
         {
-            p.Dtor();
-            return null;
+            if (p)
+            {
+                freeNoSync(p);
+                p = null;
+            }
         }
         }
-
-        Pool* pool = pools.insert_sorted(p);
-        if (pool)
+        else if (!p)
         {
         {
-            minAddr = pools[0].baseAddr;
-            maxAddr = pools[pools.length - 1].topAddr;
+            p = mallocNoSync(size, attrs, pm_bitmask);
+        }
+        else
+        {
+            Pool* pool = this.findPool(p);
+            if (pool is null)
+                return null;
+
+            // Set or retrieve attributes as appropriate
+            auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
+            if (attrs) {
+                this.clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
+                this.setAttr(pool, bit_i, attrs);
+            }
+            else
+                attrs = this.getAttr(pool, bit_i);
+
+            void* blk_base_addr = this.findBase(p);
+            size_t blk_size = this.findSize(p);
+            bool has_pm = has_pointermap(attrs);
+            size_t pm_bitmask_size = 0;
+            if (has_pm) {
+                pm_bitmask_size = size_t.sizeof;
+                // Retrieve pointer map bit mask if appropriate
+                if (pm_bitmask is null) {
+                    auto end_of_blk = cast(size_t**)(blk_base_addr +
+                            blk_size - size_t.sizeof);
+                    pm_bitmask = *end_of_blk;
+                }
+            }
+
+            if (opts.options.sentinel)
+            {
+                sentinel_Invariant(p);
+                size_t sentinel_stored_size = *sentinel_size(p);
+                if (sentinel_stored_size != size)
+                {
+                    void* p2 = mallocNoSync(size, attrs, pm_bitmask);
+                    if (sentinel_stored_size < size)
+                        size = sentinel_stored_size;
+                    cstring.memcpy(p2, p, size);
+                    p = p2;
+                }
+            }
+            else
+            {
+                size += pm_bitmask_size;
+                if (blk_size >= PAGESIZE && size >= PAGESIZE)
+                {
+                    auto psz = blk_size / PAGESIZE;
+                    auto newsz = (size + PAGESIZE - 1) / PAGESIZE;
+                    if (newsz == psz)
+                        return p;
+
+                    auto pagenum = (p - pool.baseAddr) / PAGESIZE;
+
+                    if (newsz < psz)
+                    {
+                        // Shrink in place
+                        synchronized (gcLock)
+                        {
+                            if (opts.options.mem_stomp)
+                                memset(p + size - pm_bitmask_size, 0xF2,
+                                        blk_size - size - pm_bitmask_size);
+                            pool.freePages(pagenum + newsz, psz - newsz);
+                        }
+                        if (has_pm) {
+                            auto end_of_blk = cast(size_t**)(
+                                    blk_base_addr + (PAGESIZE * newsz) -
+                                    pm_bitmask_size);
+                            *end_of_blk = pm_bitmask;
+                        }
+                        return p;
+                    }
+                    else if (pagenum + newsz <= pool.npages)
+                    {
+                        // Attempt to expand in place
+                        synchronized (gcLock)
+                        {
+                            for (size_t i = pagenum + psz; 1;)
+                            {
+                                if (i == pagenum + newsz)
+                                {
+                                    if (opts.options.mem_stomp)
+                                        memset(p + blk_size - pm_bitmask_size,
+                                                0xF0, size - blk_size
+                                                - pm_bitmask_size);
+                                    memset(pool.pagetable + pagenum +
+                                            psz, B_PAGEPLUS, newsz - psz);
+                                    if (has_pm) {
+                                        auto end_of_blk = cast(size_t**)(
+                                                blk_base_addr +
+                                                (PAGESIZE * newsz) -
+                                                pm_bitmask_size);
+                                        *end_of_blk = pm_bitmask;
+                                    }
+                                    return p;
+                                }
+                                if (i == pool.npages)
+                                {
+                                    break;
+                                }
+                                if (pool.pagetable[i] != B_FREE)
+                                    break;
+                                i++;
+                            }
+                        }
+                    }
+                }
+                // if new size is bigger or less than half
+                if (blk_size < size || blk_size > size * 2)
+                {
+                    size -= pm_bitmask_size;
+                    blk_size -= pm_bitmask_size;
+                    void* p2 = mallocNoSync(size, attrs, pm_bitmask);
+                    if (blk_size < size)
+                        size = blk_size;
+                    cstring.memcpy(p2, p, size);
+                    p = p2;
+                }
+            }
         }
         }
-        return pool;
+        return p;
     }
 
 
     /**
     }
 
 
     /**
-     * Allocate a page of bin's.
+     * Attempt to in-place enlarge the memory block pointed to by p by at least
+     * minbytes beyond its current capacity, up to a maximum of maxsize.  This
+     * does not attempt to move the memory block (like realloc() does).
+     *
      * Returns:
      * Returns:
-     *  0       failed
+     *  0 if could not extend p,
+     *  total size of entire memory block if successful.
      */
      */
-    int allocPage(Bins bin)
+    size_t extend(void* p, size_t minsize, size_t maxsize)
     {
     {
-        Pool*  pool;
-        size_t n;
-        size_t pn;
-        byte*  p;
-        byte*  ptop;
-
-        for (n = 0; n < pools.length; n++)
+        if (!thread_needLock())
         {
         {
-            pool = pools[n];
-            pn = pool.allocPages(1);
-            if (pn != OPFAIL)
-                goto L1;
+            return extendNoSync(p, minsize, maxsize);
         }
         }
-        return 0;               // failed
-
-      L1:
-        pool.pagetable[pn] = cast(ubyte)bin;
-
-        // Convert page to free list
-        size_t size = binsize[bin];
-        List **b = &bucket[bin];
-
-        p = pool.baseAddr + pn * PAGESIZE;
-        ptop = p + PAGESIZE;
-        for (; p < ptop; p += size)
+        else synchronized (gcLock)
         {
         {
-            (cast(List *)p).next = *b;
-            *b = cast(List *)p;
+            return extendNoSync(p, minsize, maxsize);
         }
         }
-        return 1;
     }
 
 
     }
 
 
-    /**
-     * Marks a range of memory using the conservative bit mask.  Used for
-     * the stack, for the data segment, and additional memory ranges.
-     */
-    void mark_conservative(void* pbot, void* ptop)
+    //
+    //
+    //
+    private size_t extendNoSync(void* p, size_t minsize, size_t maxsize)
+    in
     {
     {
-        mark(pbot, ptop, PointerMap.init.bits.ptr);
+        assert( minsize <= maxsize );
     }
     }
-
-
-    /**
-     * Search a range of memory values and mark any pointers into the GC pool.
-     */
-    void mark(void *pbot, void *ptop, size_t* pm_bitmask)
+    body
     {
     {
-        const BITS_PER_WORD = size_t.sizeof * 8;
+        if (opts.options.sentinel)
+            return 0;
 
 
-        void **p1 = cast(void **)pbot;
-        void **p2 = cast(void **)ptop;
-        size_t pcache = 0;
-        uint changes = 0;
+        Pool* pool = this.findPool(p);
+        if (pool is null)
+            return 0;
 
 
-        size_t type_size = pm_bitmask[0];
-        size_t* pm_bits = pm_bitmask + 1;
+        // Retrieve attributes
+        auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
+        uint attrs = this.getAttr(pool, bit_i);
 
 
-        //printf("marking range: %p -> %p\n", pbot, ptop);
-        for (; p1 + type_size <= p2; p1 += type_size) {
-            for (size_t n = 0; n < type_size; n++) {
-                // scan bit set for this word
-                if (!(pm_bits[n / BITS_PER_WORD] & (1 << (n % BITS_PER_WORD))))
-                    continue;
+        void* blk_base_addr = this.findBase(p);
+        size_t blk_size = this.findSize(p);
+        bool has_pm = has_pointermap(attrs);
+        size_t* pm_bitmask = null;
+        size_t pm_bitmask_size = 0;
+        if (has_pm) {
+            pm_bitmask_size = size_t.sizeof;
+            // Retrieve pointer map bit mask
+            auto end_of_blk = cast(size_t**)(blk_base_addr +
+                    blk_size - size_t.sizeof);
+            pm_bitmask = *end_of_blk;
 
 
-                void* p = *(p1 + n);
+            minsize += size_t.sizeof;
+            maxsize += size_t.sizeof;
+        }
 
 
-                if (p < minAddr || p >= maxAddr)
-                    continue;
+        if (blk_size < PAGESIZE)
+            return 0; // cannot extend buckets
 
 
-                if ((cast(size_t)p & ~(PAGESIZE-1)) == pcache)
-                    continue;
+        auto psz = blk_size / PAGESIZE;
+        auto minsz = (minsize + PAGESIZE - 1) / PAGESIZE;
+        auto maxsz = (maxsize + PAGESIZE - 1) / PAGESIZE;
 
 
-                Pool* pool = findPool(p);
-                if (pool)
-                {
-                    size_t offset = cast(size_t)(p - pool.baseAddr);
-                    size_t bit_i;
-                    size_t pn = offset / PAGESIZE;
-                    Bins   bin = cast(Bins)pool.pagetable[pn];
+        auto pagenum = (p - pool.baseAddr) / PAGESIZE;
 
 
-                    // Adjust bit to be at start of allocated memory block
-                    if (bin <= B_PAGE)
-                        bit_i = (offset & notbinsize[bin]) >> 4;
-                    else if (bin == B_PAGEPLUS)
-                    {
-                        do
-                        {
-                            --pn;
-                        }
-                        while (cast(Bins)pool.pagetable[pn] == B_PAGEPLUS);
-                        bit_i = pn * (PAGESIZE / 16);
-                    }
-                    else
-                    {
-                        // Don't mark bits in B_FREE pages
-                        continue;
-                    }
+        size_t sz;
+        for (sz = 0; sz < maxsz; sz++)
+        {
+            auto i = pagenum + psz + sz;
+            if (i == pool.npages)
+                break;
+            if (pool.pagetable[i] != B_FREE)
+            {
+                if (sz < minsz)
+                    return 0;
+                break;
+            }
+        }
+        if (sz < minsz)
+            return 0;
 
 
-                    if (bin >= B_PAGE) // Cache B_PAGE and B_PAGEPLUS lookups
-                        pcache = cast(size_t)p & ~(PAGESIZE-1);
+        size_t new_size = (psz + sz) * PAGESIZE;
 
 
-                    if (!pool.mark.test(bit_i))
-                    {
-                        pool.mark.set(bit_i);
-                        if (!pool.noscan.test(bit_i))
-                        {
-                            pool.scan.set(bit_i);
-                            changes = 1;
-                        }
-                    }
-                }
-            }
+        if (opts.options.mem_stomp)
+            memset(p + blk_size - pm_bitmask_size, 0xF0,
+                    new_size - blk_size - pm_bitmask_size);
+        memset(pool.pagetable + pagenum + psz, B_PAGEPLUS, sz);
+        this.p_cache = null;
+        this.size_cache = 0;
+
+        if (has_pm) {
+            new_size -= size_t.sizeof;
+            auto end_of_blk = cast(size_t**)(blk_base_addr + new_size);
+            *end_of_blk = pm_bitmask;
         }
         }
-        anychanges |= changes;
+        return new_size;
     }
 
     }
 
+
     /**
     /**
-     * Return number of full pages free'd.
+     *
      */
      */
-    size_t fullcollectshell()
+    size_t reserve(size_t size)
     {
     {
-        stats.collection_started();
-        scope (exit)
-            stats.collection_finished();
+        if (!size)
+        {
+            return 0;
+        }
 
 
-        // The purpose of the 'shell' is to ensure all the registers
-        // get put on the stack so they'll be scanned
-        void *sp;
-        size_t result;
-        version (GNU)
+        if (!thread_needLock())
         {
         {
-            gcc.builtins.__builtin_unwind_init();
-            sp = & sp;
+            return reserveNoSync(size);
         }
         }
-        else version(LDC)
+        else synchronized (gcLock)
         {
         {
-            version(X86)
-            {
-                uint eax,ecx,edx,ebx,ebp,esi,edi;
-                asm
-                {
-                    mov eax[EBP], EAX      ;
-                    mov ecx[EBP], ECX      ;
-                    mov edx[EBP], EDX      ;
-                    mov ebx[EBP], EBX      ;
-                    mov ebp[EBP], EBP      ;
-                    mov esi[EBP], ESI      ;
-                    mov edi[EBP], EDI      ;
-                    mov  sp[EBP], ESP      ;
-                }
-            }
-            else version (X86_64)
-            {
-                ulong rax,rbx,rcx,rdx,rbp,rsi,rdi,r8,r9,r10,r11,r12,r13,r14,r15;
-                asm
-                {
-                    movq rax[RBP], RAX      ;
-                    movq rbx[RBP], RBX      ;
-                    movq rcx[RBP], RCX      ;
-                    movq rdx[RBP], RDX      ;
-                    movq rbp[RBP], RBP      ;
-                    movq rsi[RBP], RSI      ;
-                    movq rdi[RBP], RDI      ;
-                    movq r8 [RBP], R8       ;
-                    movq r9 [RBP], R9       ;
-                    movq r10[RBP], R10      ;
-                    movq r11[RBP], R11      ;
-                    movq r12[RBP], R12      ;
-                    movq r13[RBP], R13      ;
-                    movq r14[RBP], R14      ;
-                    movq r15[RBP], R15      ;
-                    movq  sp[RBP], RSP      ;
-                }
-            }
-            else
-            {
-                static assert( false, "Architecture not supported." );
-            }
+            return reserveNoSync(size);
+        }
+    }
+
+
+    /**
+     *
+     */
+    void free(void *p)
+    {
+        if (!p)
+        {
+            return;
         }
         }
-        else
+
+        if (!thread_needLock())
         {
         {
-        asm
+            return freeNoSync(p);
+        }
+        else synchronized (gcLock)
         {
         {
-            pushad              ;
-            mov sp[EBP],ESP     ;
+            return freeNoSync(p);
         }
         }
+    }
+
+
+    //
+    //
+    //
+    private void freeNoSync(void *p)
+    {
+        assert (p);
+
+        Pool*  pool;
+        size_t pagenum;
+        Bins   bin;
+        size_t bit_i;
+
+        // Find which page it is in
+        pool = this.findPool(p);
+        if (!pool)                              // if not one of ours
+            return;                             // ignore
+        if (opts.options.sentinel) {
+            sentinel_Invariant(p);
+            p = sentinel_sub(p);
         }
         }
-        result = fullcollect(sp);
-        version (GNU)
+        pagenum = cast(size_t)(p - pool.baseAddr) / PAGESIZE;
+        bit_i = cast(size_t)(p - pool.baseAddr) / 16;
+        this.clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
+
+        bin = cast(Bins)pool.pagetable[pagenum];
+        if (bin == B_PAGE)              // if large alloc
         {
         {
-            // nothing to do
+            // Free pages
+            size_t npages = 1;
+            size_t n = pagenum;
+            while (++n < pool.npages && pool.pagetable[n] == B_PAGEPLUS)
+                npages++;
+            if (opts.options.mem_stomp)
+                memset(p, 0xF2, npages * PAGESIZE);
+            pool.freePages(pagenum, npages);
         }
         }
-        else version(LDC)
+        else
         {
         {
-            // nothing to do
+            // Add to free list
+            List *list = cast(List*)p;
+
+            if (opts.options.mem_stomp)
+                memset(p, 0xF2, binsize[bin]);
+
+            list.next = this.bucket[bin];
+            this.bucket[bin] = list;
         }
         }
-        else
+    }
+
+
+    /**
+     * Determine the base address of the block containing p.  If p is not a gc
+     * allocated pointer, return null.
+     */
+    void* addrOf(void *p)
+    {
+        if (!p)
         {
         {
-        asm
+            return null;
+        }
+
+        if (!thread_needLock())
         {
         {
-            popad               ;
+            return addrOfNoSync(p);
         }
         }
+        else synchronized (gcLock)
+        {
+            return addrOfNoSync(p);
         }
         }
-        return result;
+    }
+
+
+    //
+    //
+    //
+    void* addrOfNoSync(void *p)
+    {
+        if (!p)
+        {
+            return null;
+        }
+
+        return this.findBase(p);
     }
 
 
     /**
     }
 
 
     /**
-     *
+     * Determine the allocated size of pointer p.  If p is an interior pointer
+     * or not a gc allocated pointer, return 0.
      */
      */
-    size_t fullcollect(void *stackTop)
+    size_t sizeOf(void *p)
     {
     {
-        size_t n;
-        Pool*  pool;
+        if (!p)
+        {
+            return 0;
+        }
 
 
-        debug(COLLECT_PRINTF) printf("Gcx.fullcollect()\n");
+        if (!thread_needLock())
+        {
+            return sizeOfNoSync(p);
+        }
+        else synchronized (gcLock)
+        {
+            return sizeOfNoSync(p);
+        }
+    }
 
 
-        thread_suspendAll();
-        stats.world_stopped();
 
 
-        p_cache = null;
-        size_cache = 0;
+    //
+    //
+    //
+    private size_t sizeOfNoSync(void *p)
+    {
+        assert (p);
 
 
-        anychanges = 0;
-        for (n = 0; n < pools.length; n++)
-        {
-            pool = pools[n];
-            pool.mark.zero();
-            pool.scan.zero();
-            pool.freebits.zero();
+        if (opts.options.sentinel)
+            p = sentinel_sub(p);
+
+        Pool* pool = this.findPool(p);
+        if (pool is null)
+            return 0;
+
+        auto biti = cast(size_t)(p - pool.baseAddr) / 16;
+        uint attrs = this.getAttr(pool, biti);
+
+        size_t size = this.findSize(p);
+        size_t pm_bitmask_size = 0;
+        if (has_pointermap(attrs))
+            pm_bitmask_size = size_t.sizeof;
+
+        if (opts.options.sentinel) {
+            // Check for interior pointer
+            // This depends on:
+            // 1) size is a power of 2 for less than PAGESIZE values
+            // 2) base of memory pool is aligned on PAGESIZE boundary
+            if (cast(size_t)p & (size - 1) & (PAGESIZE - 1))
+                return 0;
+            return size - SENTINEL_EXTRA - pm_bitmask_size;
         }
         }
+        else {
+            if (p == this.p_cache)
+                return this.size_cache;
 
 
-        // Mark each free entry, so it doesn't get scanned
-        for (n = 0; n < B_PAGE; n++)
+            // Check for interior pointer
+            // This depends on:
+            // 1) size is a power of 2 for less than PAGESIZE values
+            // 2) base of memory pool is aligned on PAGESIZE boundary
+            if (cast(size_t)p & (size - 1) & (PAGESIZE - 1))
+                return 0;
+
+            this.p_cache = p;
+            this.size_cache = size - pm_bitmask_size;
+
+            return this.size_cache;
+        }
+    }
+
+
+    /**
+     * Determine the base address of the block containing p.  If p is not a gc
+     * allocated pointer, return null.
+     */
+    BlkInfo query(void *p)
+    {
+        if (!p)
         {
         {
-            for (List *list = bucket[n]; list; list = list.next)
-            {
-                pool = findPool(list);
-                assert(pool);
-                pool.freebits.set(cast(size_t)(cast(byte*)list - pool.baseAddr) / 16);
-            }
+            BlkInfo i;
+            return  i;
         }
 
         }
 
-        for (n = 0; n < pools.length; n++)
+        if (!thread_needLock())
         {
         {
-            pool = pools[n];
-            pool.mark.copy(&pool.freebits);
+            return queryNoSync(p);
         }
         }
+        else synchronized (gcLock)
+        {
+            return queryNoSync(p);
+        }
+    }
 
 
-        rt_scanStaticData( &mark_conservative );
 
 
-        if (!noStack)
+    //
+    //
+    //
+    BlkInfo queryNoSync(void *p)
+    {
+        assert(p);
+
+        return this.getInfo(p);
+    }
+
+
+    /**
+     * Verify that pointer p:
+     *  1) belongs to this memory pool
+     *  2) points to the start of an allocated piece of memory
+     *  3) is not on a free list
+     */
+    void check(void *p)
+    {
+        if (!p)
         {
         {
-            // Scan stacks and registers for each paused thread
-            thread_scanAll( &mark_conservative, stackTop );
+            return;
         }
 
         }
 
-        // Scan roots
-        debug(COLLECT_PRINTF) printf("scan roots[]\n");
-        mark_conservative(roots.ptr, roots.ptr + roots.length);
-
-        // Scan ranges
-        debug(COLLECT_PRINTF) printf("scan ranges[]\n");
-        for (n = 0; n < ranges.length; n++)
+        if (!thread_needLock())
         {
         {
-            debug(COLLECT_PRINTF) printf("\t%x .. %x\n", ranges[n].pbot, ranges[n].ptop);
-            mark_conservative(ranges[n].pbot, ranges[n].ptop);
+            checkNoSync(p);
         }
         }
+        else synchronized (gcLock)
+        {
+            checkNoSync(p);
+        }
+    }
 
 
-        debug(COLLECT_PRINTF) printf("\tscan heap\n");
-        while (anychanges)
+
+    //
+    //
+    //
+    private void checkNoSync(void *p)
+    {
+        assert(p);
+
+        if (opts.options.sentinel)
+            sentinel_Invariant(p);
+        debug (PTRCHECK)
         {
         {
-            anychanges = 0;
-            for (n = 0; n < pools.length; n++)
-            {
-                uint *bbase;
-                uint *b;
-                uint *btop;
+            Pool*  pool;
+            size_t pagenum;
+            Bins   bin;
+            size_t size;
 
 
-                pool = pools[n];
+            if (opts.options.sentinel)
+                p = sentinel_sub(p);
+            pool = this.findPool(p);
+            assert(pool);
+            pagenum = cast(size_t)(p - pool.baseAddr) / PAGESIZE;
+            bin = cast(Bins)pool.pagetable[pagenum];
+            assert(bin <= B_PAGE);
+            size = binsize[bin];
+            assert((cast(size_t)p & (size - 1)) == 0);
 
 
-                bbase = pool.scan.base();
-                btop = bbase + pool.scan.nwords;
-                for (b = bbase; b < btop;)
+            debug (PTRCHECK2)
+            {
+                if (bin < B_PAGE)
                 {
                 {
-                    Bins   bin;
-                    size_t pn;
-                    size_t u;
-                    size_t bitm;
-                    byte*  o;
-
-                    bitm = *b;
-                    if (!bitm)
-                    {
-                        b++;
-                        continue;
-                    }
-                    *b = 0;
+                    // Check that p is not on a free list
+                    List *list;
 
 
-                    o = pool.baseAddr + (b - bbase) * 32 * 16;
-                    if (!(bitm & 0xFFFF))
-                    {
-                        bitm >>= 16;
-                        o += 16 * 16;
-                    }
-                    for (; bitm; o += 16, bitm >>= 1)
+                    for (list = this.bucket[bin]; list; list = list.next)
                     {
                     {
-                        if (!(bitm & 1))
-                            continue;
-
-                        pn = cast(size_t)(o - pool.baseAddr) / PAGESIZE;
-                        bin = cast(Bins)pool.pagetable[pn];
-                        if (bin < B_PAGE) {
-                            if (opts.options.conservative)
-                                mark_conservative(o, o + binsize[bin]);
-                            else {
-                                auto end_of_blk = cast(size_t**)(o +
-                                        binsize[bin] - size_t.sizeof);
-                                size_t* pm_bitmask = *end_of_blk;
-                                mark(o, end_of_blk, pm_bitmask);
-                            }
-                        }
-                        else if (bin == B_PAGE || bin == B_PAGEPLUS)
-                        {
-                            if (bin == B_PAGEPLUS)
-                            {
-                                while (pool.pagetable[pn - 1] != B_PAGE)
-                                    pn--;
-                            }
-                            u = 1;
-                            while (pn + u < pool.npages &&
-                                    pool.pagetable[pn + u] == B_PAGEPLUS)
-                                u++;
-
-                            size_t blk_size = u * PAGESIZE;
-                            if (opts.options.conservative)
-                                mark_conservative(o, o + blk_size);
-                            else {
-                                auto end_of_blk = cast(size_t**)(o + blk_size -
-                                        size_t.sizeof);
-                                size_t* pm_bitmask = *end_of_blk;
-                                mark(o, end_of_blk, pm_bitmask);
-                            }
-                        }
+                        assert(cast(void*)list != p);
                     }
                 }
             }
         }
                     }
                 }
             }
         }
+    }
 
 
-        thread_resumeAll();
-        stats.world_started();
 
 
-        // Free up everything not marked
-        debug(COLLECT_PRINTF) printf("\tfree'ing\n");
-        size_t freedpages = 0;
-        size_t freed = 0;
-        for (n = 0; n < pools.length; n++)
+    //
+    //
+    //
+    private void setStackBottom(void *p)
+    {
+        version (STACKGROWSDOWN)
         {
         {
-            pool = pools[n];
-            uint*  bbase = pool.mark.base();
-            size_t pn;
-            for (pn = 0; pn < pool.npages; pn++, bbase += PAGESIZE / (32 * 16))
+            //p = (void *)((uint *)p + 4);
+            if (p > this.stackBottom)
             {
             {
-                Bins bin = cast(Bins)pool.pagetable[pn];
+                this.stackBottom = p;
+            }
+        }
+        else
+        {
+            //p = (void *)((uint *)p - 4);
+            if (p < this.stackBottom)
+            {
+                this.stackBottom = cast(char*)p;
+            }
+        }
+    }
 
 
-                if (bin < B_PAGE)
-                {
-                    auto size = binsize[bin];
-                    byte* p = pool.baseAddr + pn * PAGESIZE;
-                    byte* ptop = p + PAGESIZE;
-                    size_t bit_i = pn * (PAGESIZE/16);
-                    size_t bit_stride = size / 16;
 
 
-    version(none) // BUG: doesn't work because freebits() must also be cleared
+    /**
+     * add p to list of roots
+     */
+    void addRoot(void *p)
     {
     {
-                    // If free'd entire page
-                    if (bbase[0] == 0 && bbase[1] == 0 && bbase[2] == 0 &&
-                            bbase[3] == 0 && bbase[4] == 0 && bbase[5] == 0 &&
-                            bbase[6] == 0 && bbase[7] == 0)
-                    {
-                        for (; p < ptop; p += size, bit_i += bit_stride)
-                        {
-                            if (pool.finals.nbits && pool.finals.testClear(bit_i)) {
-                                if (opts.options.sentinel)
-                                    rt_finalize(cast(List *)sentinel_add(p), false/*noStack > 0*/);
-                                else
-                                    rt_finalize(cast(List *)p, false/*noStack > 0*/);
-                            }
-                            gcx.clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
-
-                            List *list = cast(List *)p;
+        if (!p)
+        {
+            return;
+        }
 
 
-                            if (opts.options.mem_stomp)
-                                memset(p, 0xF3, size);
-                        }
-                        pool.pagetable[pn] = B_FREE;
-                        freed += PAGESIZE;
-                        continue;
-                    }
+        if (!thread_needLock())
+        {
+            if (roots.append(p) is null)
+                onOutOfMemoryError();
+        }
+        else synchronized (gcLock)
+        {
+            if (roots.append(p) is null)
+                onOutOfMemoryError();
+        }
     }
     }
-                    for (; p < ptop; p += size, bit_i += bit_stride)
-                    {
-                        if (!pool.mark.test(bit_i))
-                        {
-                            if (opts.options.sentinel)
-                                sentinel_Invariant(sentinel_add(p));
 
 
-                            pool.freebits.set(bit_i);
-                            if (pool.finals.nbits && pool.finals.testClear(bit_i)) {
-                                if (opts.options.sentinel)
-                                    rt_finalize(cast(List *)sentinel_add(p), false/*noStack > 0*/);
-                                else
-                                    rt_finalize(cast(List *)p, false/*noStack > 0*/);
-                            }
-                            clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
 
 
-                            List *list = cast(List *)p;
+    /**
+     * remove p from list of roots
+     */
+    void removeRoot(void *p)
+    {
+        if (!p)
+        {
+            return;
+        }
 
 
-                            if (opts.options.mem_stomp)
-                                memset(p, 0xF3, size);
+        bool r;
+        if (!thread_needLock())
+        {
+            r = roots.remove(p);
+        }
+        else synchronized (gcLock)
+        {
+            r = roots.remove(p);
+        }
+        assert (r);
+    }
 
 
-                            freed += size;
-                        }
-                    }
-                }
-                else if (bin == B_PAGE)
-                {
-                    size_t bit_i = pn * (PAGESIZE / 16);
-                    if (!pool.mark.test(bit_i))
-                    {
-                        byte *p = pool.baseAddr + pn * PAGESIZE;
-                        if (opts.options.sentinel)
-                            sentinel_Invariant(sentinel_add(p));
-                        if (pool.finals.nbits && pool.finals.testClear(bit_i)) {
-                            if (opts.options.sentinel)
-                                rt_finalize(sentinel_add(p), false/*noStack > 0*/);
-                            else
-                                rt_finalize(p, false/*noStack > 0*/);
-                        }
-                        clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
 
 
-                        debug(COLLECT_PRINTF) printf("\tcollecting big %x\n", p);
-                        pool.pagetable[pn] = B_FREE;
-                        freedpages++;
-                        if (opts.options.mem_stomp)
-                            memset(p, 0xF3, PAGESIZE);
-                        while (pn + 1 < pool.npages && pool.pagetable[pn + 1] == B_PAGEPLUS)
-                        {
-                            pn++;
-                            pool.pagetable[pn] = B_FREE;
-                            freedpages++;
+    /**
+     * add range to scan for roots
+     */
+    void addRange(void *p, size_t sz)
+    {
+        if (!p || !sz)
+        {
+            return;
+        }
 
 
-                            if (opts.options.mem_stomp)
-                            {
-                                p += PAGESIZE;
-                                memset(p, 0xF3, PAGESIZE);
-                            }
-                        }
-                    }
-                }
-            }
+        if (!thread_needLock())
+        {
+            if (ranges.append(Range(p, p+sz)) is null)
+                onOutOfMemoryError();
+        }
+        else synchronized (gcLock)
+        {
+            if (ranges.append(Range(p, p+sz)) is null)
+                onOutOfMemoryError();
         }
         }
+    }
 
 
-        // Zero buckets
-        bucket[] = null;
 
 
-        // Free complete pages, rebuild free list
-        debug(COLLECT_PRINTF) printf("\tfree complete pages\n");
-        size_t recoveredpages = 0;
-        for (n = 0; n < pools.length; n++)
+    /**
+     * remove range
+     */
+    void removeRange(void *p)
+    {
+        if (!p)
+        {
+            return;
+        }
+
+        bool r;
+        if (!thread_needLock())
         {
         {
-            pool = pools[n];
-            for (size_t pn = 0; pn < pool.npages; pn++)
-            {
-                Bins   bin = cast(Bins)pool.pagetable[pn];
-                size_t bit_i;
-                size_t u;
+            r = ranges.remove(Range(p, null));
+        }
+        else synchronized (gcLock)
+        {
+            r = ranges.remove(Range(p, null));
+        }
+        assert (r);
+    }
 
 
-                if (bin < B_PAGE)
-                {
-                    size_t size = binsize[bin];
-                    size_t bit_stride = size / 16;
-                    size_t bit_base = pn * (PAGESIZE / 16);
-                    size_t bit_top = bit_base + (PAGESIZE / 16);
-                    byte*  p;
 
 
-                    bit_i = bit_base;
-                    for (; bit_i < bit_top; bit_i += bit_stride)
-                    {
-                        if (!pool.freebits.test(bit_i))
-                            goto Lnotfree;
-                    }
-                    pool.pagetable[pn] = B_FREE;
-                    recoveredpages++;
-                    continue;
+    /**
+     * do full garbage collection
+     */
+    void fullCollect()
+    {
 
 
-                 Lnotfree:
-                    p = pool.baseAddr + pn * PAGESIZE;
-                    for (u = 0; u < PAGESIZE; u += size)
-                    {
-                        bit_i = bit_base + u / 16;
-                        if (pool.freebits.test(bit_i))
-                        {
-                            List *list = cast(List *)(p + u);
-                            // avoid unnecessary writes
-                            if (list.next != bucket[bin])
-                                list.next = bucket[bin];
-                            bucket[bin] = list;
-                        }
-                    }
-                }
-            }
+        if (!thread_needLock())
+        {
+            this.fullcollectshell();
+        }
+        else synchronized (gcLock)
+        {
+            this.fullcollectshell();
         }
 
         }
 
-        debug(COLLECT_PRINTF) printf("recovered pages = %d\n", recoveredpages);
-        debug(COLLECT_PRINTF) printf("\tfree'd %u bytes, %u pages from %u pools\n", freed, freedpages, pools.length);
+        version (none)
+        {
+            GCStats stats;
+            getStats(stats);
+        }
 
 
-        return freedpages + recoveredpages;
     }
 
 
     /**
     }
 
 
     /**
-     *
+     * do full garbage collection ignoring roots
      */
      */
-    uint getAttr(Pool* pool, size_t bit_i)
-    in
+    void fullCollectNoStack()
     {
     {
-        assert( pool );
+        if (!thread_needLock())
+        {
+            this.noStack++;
+            this.fullcollectshell();
+            this.noStack--;
+        }
+        else synchronized (gcLock)
+        {
+            this.noStack++;
+            this.fullcollectshell();
+            this.noStack--;
+        }
     }
     }
-    body
-    {
-        uint attrs;
 
 
-        if (pool.finals.nbits &&
-            pool.finals.test(bit_i))
-            attrs |= BlkAttr.FINALIZE;
-        if (pool.noscan.test(bit_i))
-            attrs |= BlkAttr.NO_SCAN;
-//        if (pool.nomove.nbits &&
-//            pool.nomove.test(bit_i))
-//            attrs |= BlkAttr.NO_MOVE;
-        return attrs;
+
+    /**
+     * minimize free space usage
+     */
+    void minimize()
+    {
+        if (!thread_needLock())
+        {
+            this.minimizeNoSync();
+        }
+        else synchronized (gcLock)
+        {
+            this.minimizeNoSync();
+        }
     }
 
 
     /**
     }
 
 
     /**
-     *
+     * Retrieve statistics about garbage collection.
+     * Useful for debugging and tuning.
      */
      */
-    void setAttr(Pool* pool, size_t bit_i, uint mask)
-    in
+    void getStats(out GCStats stats)
     {
     {
-        assert( pool );
+        if (!thread_needLock())
+        {
+            getStatsNoSync(stats);
+        }
+        else synchronized (gcLock)
+        {
+            getStatsNoSync(stats);
+        }
     }
     }
-    body
+
+
+    //
+    //
+    //
+    private void getStatsNoSync(out GCStats stats)
     {
     {
-        if (mask & BlkAttr.FINALIZE)
+        size_t psize = 0;
+        size_t usize = 0;
+        size_t flsize = 0;
+
+        size_t n;
+        size_t bsize = 0;
+
+        memset(&stats, 0, GCStats.sizeof);
+
+        for (n = 0; n < pools.length; n++)
         {
         {
-            if (!pool.finals.nbits)
-                pool.finals.alloc(pool.mark.nbits);
-            pool.finals.set(bit_i);
+            Pool* pool = pools[n];
+            psize += pool.npages * PAGESIZE;
+            for (size_t j = 0; j < pool.npages; j++)
+            {
+                Bins bin = cast(Bins)pool.pagetable[j];
+                if (bin == B_FREE)
+                    stats.freeblocks++;
+                else if (bin == B_PAGE)
+                    stats.pageblocks++;
+                else if (bin < B_PAGE)
+                    bsize += PAGESIZE;
+            }
         }
         }
-        if (mask & BlkAttr.NO_SCAN)
+
+        for (n = 0; n < B_PAGE; n++)
         {
         {
-            pool.noscan.set(bit_i);
+            for (List *list = this.bucket[n]; list; list = list.next)
+                flsize += binsize[n];
         }
         }
-//        if (mask & BlkAttr.NO_MOVE)
-//        {
-//            if (!pool.nomove.nbits)
-//                pool.nomove.alloc(pool.mark.nbits);
-//            pool.nomove.set(bit_i);
-//        }
+
+        usize = bsize - flsize;
+
+        stats.poolsize = psize;
+        stats.usedsize = bsize - flsize;
+        stats.freelistsize = flsize;
+    }
+
+    /******************* weak-reference support *********************/
+
+    // call locked if necessary
+    private T locked(T)(in T delegate() code)
+    {
+        if (thread_needLock)
+            synchronized(gcLock) return code();
+        else
+           return code();
     }
 
     }
 
+    private struct WeakPointer
+    {
+        Object reference;
+
+        void ondestroy(Object r)
+        {
+            assert(r is reference);
+            // lock for memory consistency (parallel readers)
+            // also ensures that weakpointerDestroy can be called while another
+            // thread is freeing the reference with "delete"
+            locked!(void)({ reference = null; });
+        }
+    }
 
     /**
 
     /**
-     *
+     * Create a weak pointer to the given object.
+     * Returns a pointer to an opaque struct allocated in C memory.
      */
      */
-    void clrAttr(Pool* pool, size_t bit_i, uint mask)
-    in
+    void* weakpointerCreate( Object r )
     {
     {
-        assert( pool );
+        if (r)
+       {
+            // must be allocated in C memory
+            // 1. to hide the reference from the GC
+            // 2. the GC doesn't scan delegates added by rt_attachDisposeEvent
+            //    for references
+            auto wp = cast(WeakPointer*)(cstdlib.malloc(WeakPointer.sizeof));
+            if (!wp)
+                onOutOfMemoryError();
+            wp.reference = r;
+            rt_attachDisposeEvent(r, &wp.ondestroy);
+            return wp;
+        }
+        return null;
     }
     }
-    body
+
+    /**
+     * Destroy a weak pointer returned by weakpointerCreate().
+     * If null is passed, nothing happens.
+     */
+    void weakpointerDestroy( void* p )
     {
     {
-        if (mask & BlkAttr.FINALIZE && pool.finals.nbits)
-            pool.finals.clear(bit_i);
-        if (mask & BlkAttr.NO_SCAN)
-            pool.noscan.clear(bit_i);
-//        if (mask & BlkAttr.NO_MOVE && pool.nomove.nbits)
-//            pool.nomove.clear(bit_i);
+        if (p)
+       {
+            auto wp = cast(WeakPointer*)p;
+            // must be extra careful about the GC or parallel threads
+            // finalizing the reference at the same time
+            locked!(void)({
+                   if (wp.reference)
+                       rt_detachDisposeEvent(wp.reference, &wp.ondestroy);
+                  });
+            cstdlib.free(wp);
+        }
     }
 
     }
 
+    /**
+     * Query a weak pointer and return either the object passed to
+     * weakpointerCreate, or null if it was free'd in the meantime.
+     * If null is passed, null is returned.
+     */
+    Object weakpointerGet( void* p )
+    {
+        if (p)
+       {
+            // NOTE: could avoid the lock by using Fawzi style GC counters but
+            // that'd require core.sync.Atomic and lots of care about memory
+            // consistency it's an optional optimization see
+            // http://dsource.org/projects/tango/browser/trunk/user/tango/core/Lifetime.d?rev=5100#L158
+            return locked!(Object)({
+                  return (cast(WeakPointer*)p).reference;
+                  });
+            }
+    }
 }
 
 
 }
 
 
Concurrent D Garbage Collector