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;
}
-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 =============================== */
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
+ 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);
+ 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;
+
+ 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;
- (cast(byte*)this)[0 .. Gcx.sizeof] = 0;
stackBottom = cast(char*)&dummy;
- //printf("gcx = %p, self = %x\n", this, self);
+ opts.parse(cstdlib.getenv("D_GC_OPTS"));
+ gcLock = GCLock.classinfo;
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;
-
- 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:
- * 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;
+ });
+ }
+ }
}
projects / software / dgc / cdgc.git / commitdiff