/************** Debugging ***************************/
//debug = COLLECT_PRINTF; // turn on printf's
-//debug = LOGGING; // log allocations / frees
-//debug = MEMSTOMP; // stomp on memory
-//debug = SENTINEL; // add underrun/overrrun protection
//debug = PTRCHECK; // more pointer checking
//debug = PTRCHECK2; // thorough but slow pointer checking
/***************************************************/
import rt.gc.cdgc.bits: GCBits;
-import rt.gc.cdgc.stats: GCStats;
+import rt.gc.cdgc.stats: GCStats, Stats;
+import dynarray = rt.gc.cdgc.dynarray;
import alloc = rt.gc.cdgc.alloc;
+import opts = rt.gc.cdgc.opts;
import cstdlib = tango.stdc.stdlib;
import cstring = tango.stdc.string;
+/*
+ * This is a small optimization that proved it's usefulness. For small chunks
+ * or memory memset() seems to be slower (probably because of the call) that
+ * simply doing a simple loop to set the memory.
+ */
+void memset(void* dst, int c, size_t n)
+{
+ // This number (32) has been determined empirically
+ if (n > 32) {
+ cstring.memset(dst, c, n);
+ return;
+ }
+ auto p = cast(ubyte*)(dst);
+ while (n-- > 0)
+ *p++ = c;
+}
version (GNU)
{
static import gcc.builtins; // for __builtin_unwind_int
}
-
struct BlkInfo
{
void* base;
uint attr;
}
-private
+package enum BlkAttr : uint
{
- enum BlkAttr : uint
- {
- FINALIZE = 0b0000_0001,
- NO_SCAN = 0b0000_0010,
- NO_MOVE = 0b0000_0100,
- ALL_BITS = 0b1111_1111
- }
-
- extern (C) void* rt_stackBottom();
- extern (C) void* rt_stackTop();
+ FINALIZE = 0b0000_0001,
+ NO_SCAN = 0b0000_0010,
+ NO_MOVE = 0b0000_0100,
+ ALL_BITS = 0b1111_1111
+}
- extern (C) void rt_finalize( void* p, bool det = true );
+package bool has_pointermap(uint attrs)
+{
+ return !opts.options.conservative && !(attrs & BlkAttr.NO_SCAN);
+}
+private
+{
alias void delegate(Object) DEvent;
- extern (C) void rt_attachDisposeEvent(Object h, DEvent e);
- extern (C) bool rt_detachDisposeEvent(Object h, DEvent e);
-
-
alias void delegate( void*, void* ) scanFn;
+ enum { OPFAIL = ~cast(size_t)0 }
- extern (C) void rt_scanStaticData( scanFn scan );
-
- extern (C) bool thread_needLock();
- extern (C) void thread_suspendAll();
- extern (C) void thread_resumeAll();
+ extern (C)
+ {
+ version (DigitalMars) version(OSX)
+ oid _d_osx_image_init();
- extern (C) void thread_scanAll( scanFn fn, void* curStackTop = null );
+ void* rt_stackBottom();
+ void* rt_stackTop();
+ void rt_finalize( void* p, bool det = true );
+ void rt_attachDisposeEvent(Object h, DEvent e);
+ bool rt_detachDisposeEvent(Object h, DEvent e);
+ void rt_scanStaticData( scanFn scan );
- extern (C) void onOutOfMemoryError();
+ void thread_init();
+ bool thread_needLock();
+ void thread_suspendAll();
+ void thread_resumeAll();
+ void thread_scanAll( scanFn fn, void* curStackTop = null );
- enum
- {
- OPFAIL = ~cast(size_t)0
+ void onOutOfMemoryError();
}
}
-alias GC gc_t;
-
-
-/* ======================= Leak Detector =========================== */
+enum
+{
+ PAGESIZE = 4096,
+ POOLSIZE = (4096*256),
+}
-debug (LOGGING)
+enum
{
- struct Log
- {
- void* p;
- size_t size;
- size_t line;
- char* file;
- void* parent;
+ 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
+}
- void print()
- {
- printf(" p = %x, size = %d, parent = %x ", p, size, parent);
- if (file)
- {
- printf("%s(%u)", file, line);
- }
- printf("\n");
- }
- }
+alias ubyte Bins;
- struct LogArray
- {
- size_t dim;
- size_t allocdim;
- Log *data;
- void Dtor()
- {
- if (data)
- cstdlib.free(data);
- data = null;
- }
+struct List
+{
+ List *next;
+}
- void reserve(size_t nentries)
- {
- assert(dim <= allocdim);
- if (allocdim - dim < nentries)
- {
- allocdim = (dim + nentries) * 2;
- assert(dim + nentries <= allocdim);
- if (!data)
- {
- data = cast(Log*) cstdlib.malloc(allocdim * Log.sizeof);
- if (!data && allocdim)
- onOutOfMemoryError();
- }
- else
- {
- Log *newdata = cast(Log*) cstdlib.malloc(
- allocdim * Log.sizeof);
- if (!newdata && allocdim)
- onOutOfMemoryError();
- cstring.memcpy(newdata, data, dim * Log.sizeof);
- cstdlib.free(data);
- data = newdata;
- }
- }
- }
+struct Range
+{
+ void *pbot;
+ void *ptop;
+ int opCmp(in Range other)
+ {
+ if (pbot < other.pbot)
+ return -1;
+ else
+ return cast(int)(pbot > other.pbot);
+ }
+}
- void push(Log log)
- {
- reserve(1);
- data[dim++] = log;
- }
- void remove(size_t i)
- {
- cstring.memmove(data + i, data + i + 1, (dim - i) * Log.sizeof);
- dim--;
- }
+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) ];
- size_t find(void *p)
- {
- for (size_t i = 0; i < dim; i++)
- {
- if (data[i].p == p)
- return i;
- }
- return OPFAIL; // not found
- }
+/* ============================ GC =============================== */
- void copy(LogArray *from)
- {
- reserve(from.dim - dim);
- assert(from.dim <= allocdim);
- cstring.memcpy(data, from.data, from.dim * Log.sizeof);
- dim = from.dim;
- }
- }
-}
+class GCLock {} // just a dummy so we can get a global lock
-/* ============================ GC =============================== */
+struct GC
+{
+ // global lock
+ ClassInfo lock;
+ void* p_cache;
+ size_t size_cache;
-class GCLock { } // just a dummy so we can get a global lock
+ // !=0 means don't scan stack
+ uint no_stack;
+ bool any_changes;
+ void* stack_bottom;
+ uint inited;
+ /// Turn off collections if > 0
+ int disabled;
+ /// min(pool.baseAddr)
+ byte *min_addr;
+ /// max(pool.topAddr)
+ byte *max_addr;
-const uint GCVERSION = 1; // increment every time we change interface
- // to GC.
+ /// Free list for each size
+ List*[B_MAX] free_list;
-class GC
-{
- // For passing to debug code
- static size_t line;
- static char* file;
+ dynarray.DynArray!(void*) roots;
+ dynarray.DynArray!(Range) ranges;
+ dynarray.DynArray!(Pool) pools;
- uint gcversion = GCVERSION;
+ Stats stats;
+}
- Gcx *gcx; // implementation
- static ClassInfo gcLock; // global lock
+// call locked if necessary
+private T locked(T, alias Code)()
+{
+ if (thread_needLock())
+ synchronized (gc.lock) return Code();
+ else
+ return Code();
+}
+private GC* gc;
- void initialize()
- {
- gcLock = GCLock.classinfo;
- gcx = cast(Gcx*) cstdlib.calloc(1, Gcx.sizeof);
- if (!gcx)
- onOutOfMemoryError();
- gcx.initialize();
- setStackBottom(rt_stackBottom());
+bool Invariant()
+{
+ assert (gc !is null);
+ if (gc.inited) {
+ for (size_t i = 0; i < gc.pools.length; i++) {
+ Pool* pool = gc.pools[i];
+ pool.Invariant();
+ if (i == 0)
+ assert(gc.min_addr == pool.baseAddr);
+ if (i + 1 < gc.pools.length)
+ assert(*pool < gc.pools[i + 1]);
+ else if (i + 1 == gc.pools.length)
+ assert(gc.max_addr == pool.topAddr);
+ }
+
+ gc.roots.Invariant();
+ gc.ranges.Invariant();
+
+ for (size_t i = 0; i < gc.ranges.length; i++) {
+ assert(gc.ranges[i].pbot);
+ assert(gc.ranges[i].ptop);
+ assert(gc.ranges[i].pbot <= gc.ranges[i].ptop);
+ }
+
+ for (size_t i = 0; i < B_PAGE; i++)
+ for (List *list = gc.free_list[i]; list; list = list.next)
+ {
+ }
}
+ return true;
+}
- void Dtor()
+/**
+ * Find Pool that pointer is in.
+ * Return null if not in a Pool.
+ * Assume pools is sorted.
+ */
+Pool *findPool(void *p)
+{
+ if (p >= gc.min_addr && p < gc.max_addr)
{
- if (gcx)
+ if (gc.pools.length == 1)
+ {
+ return gc.pools[0];
+ }
+
+ for (size_t i = 0; i < gc.pools.length; i++)
{
- gcx.Dtor();
- cstdlib.free(gcx);
- gcx = null;
+ Pool* pool = gc.pools[i];
+ if (p < pool.topAddr)
+ {
+ if (pool.baseAddr <= p)
+ return pool;
+ break;
+ }
}
}
+ return null;
+}
- /**
- *
- */
- void enable()
+/**
+ * Determine the base address of the block containing p. If p is not a gc
+ * allocated pointer, return null.
+ */
+BlkInfo getInfo(void* p)
+{
+ assert (p !is null);
+ Pool* pool = findPool(p);
+ if (pool is null)
+ return BlkInfo.init;
+ BlkInfo info;
+ info.base = pool.findBase(p);
+ info.size = pool.findSize(info.base);
+ info.attr = getAttr(pool, cast(size_t)(info.base - pool.baseAddr) / 16u);
+ if (!opts.options.conservative && !(info.attr & BlkAttr.NO_SCAN))
+ info.size -= size_t.sizeof; // PointerMap bitmask
+ return info;
+}
+
+
+/**
+ * Compute bin for size.
+ */
+static Bins findBin(size_t size)
+{
+ Bins bin;
+ if (size <= 256)
{
- if (!thread_needLock())
+ if (size <= 64)
{
- assert(gcx.disabled > 0);
- gcx.disabled--;
+ if (size <= 16)
+ bin = B_16;
+ else if (size <= 32)
+ bin = B_32;
+ else
+ bin = B_64;
}
- else synchronized (gcLock)
+ else
{
- assert(gcx.disabled > 0);
- gcx.disabled--;
+ if (size <= 128)
+ bin = B_128;
+ else
+ bin = B_256;
}
}
-
-
- /**
- *
- */
- void disable()
+ else
{
- if (!thread_needLock())
+ if (size <= 1024)
{
- gcx.disabled++;
+ if (size <= 512)
+ bin = B_512;
+ else
+ bin = B_1024;
}
- else synchronized (gcLock)
+ else
{
- gcx.disabled++;
+ if (size <= 2048)
+ bin = B_2048;
+ else
+ bin = B_PAGE;
}
}
+ return bin;
+}
- /**
- *
- */
- uint getAttr(void* p)
- {
- if (!p)
- {
- return 0;
- }
+/**
+ * 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)
+{
+ assert(size != 0);
+ size_t npages = (size + PAGESIZE - 1) / PAGESIZE;
+ Pool* pool = newPool(npages);
- uint go()
- {
- Pool* pool = gcx.findPool(p);
- uint oldb = 0;
+ if (!pool)
+ return 0;
+ return pool.npages * PAGESIZE;
+}
- if (pool)
- {
- auto biti = cast(size_t)(p - pool.baseAddr) / 16;
- oldb = gcx.getBits(pool, biti);
- }
- return oldb;
- }
+/**
+ * Minimizes physical memory usage by returning free pools to the OS.
+ */
+void minimize()
+{
+ size_t n;
+ size_t pn;
+ Pool* pool;
- if (!thread_needLock())
- {
- return go();
- }
- else synchronized (gcLock)
+ for (n = 0; n < gc.pools.length; n++)
+ {
+ pool = gc.pools[n];
+ for (pn = 0; pn < pool.npages; pn++)
{
- return go();
+ if (cast(Bins)pool.pagetable[pn] != B_FREE)
+ break;
}
+ if (pn < pool.npages)
+ continue;
+ pool.Dtor();
+ gc.pools.remove_at(n);
+ n--;
}
+ gc.min_addr = gc.pools[0].baseAddr;
+ gc.max_addr = gc.pools[gc.pools.length - 1].topAddr;
+}
- /**
- *
- */
- uint setAttr(void* p, uint mask)
+/**
+ * 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;
+
+ npages = (size + PAGESIZE - 1) / PAGESIZE;
+
+ for (state = 0; ; )
{
- if (!p)
+ // This code could use some refinement when repeatedly
+ // allocating very large arrays.
+
+ for (n = 0; n < gc.pools.length; n++)
{
- return 0;
+ pool = gc.pools[n];
+ pn = pool.allocPages(npages);
+ if (pn != OPFAIL)
+ goto L1;
}
- uint go()
+ // Failed
+ switch (state)
{
- Pool* pool = gcx.findPool(p);
- uint oldb = 0;
-
- if (pool)
+ case 0:
+ if (gc.disabled)
{
- auto biti = cast(size_t)(p - pool.baseAddr) / 16;
-
- oldb = gcx.getBits(pool, biti);
- gcx.setBits(pool, biti, mask);
+ state = 1;
+ continue;
}
- return oldb;
- }
+ // Try collecting
+ freedpages = fullcollectshell();
+ if (freedpages >= gc.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);
+ }
+ }
+
+ 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
+}
- if (!thread_needLock())
- {
- return go();
- }
- else synchronized (gcLock)
- {
- return go();
- }
+
+/**
+ * Allocate a new pool with at least npages in it.
+ * Sort it into pools.
+ * Return null if failed.
+ */
+Pool *newPool(size_t npages)
+{
+ // Minimum of POOLSIZE
+ if (npages < POOLSIZE/PAGESIZE)
+ npages = POOLSIZE/PAGESIZE;
+ else if (npages > POOLSIZE/PAGESIZE)
+ {
+ // 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;
}
+ // Allocate successively larger pools up to 8 megs
+ if (gc.pools.length)
+ {
+ size_t n = gc.pools.length;
+ if (n > 8)
+ n = 8; // cap pool size at 8 megs
+ n *= (POOLSIZE / PAGESIZE);
+ if (npages < n)
+ npages = n;
+ }
- /**
- *
- */
- uint clrAttr(void* p, uint mask)
+ Pool p;
+ p.initialize(npages);
+ if (!p.baseAddr)
{
- if (!p)
- {
- return 0;
- }
+ p.Dtor();
+ return null;
+ }
- uint go()
- {
- Pool* pool = gcx.findPool(p);
- uint oldb = 0;
+ Pool* pool = gc.pools.insert_sorted(p);
+ if (pool)
+ {
+ gc.min_addr = gc.pools[0].baseAddr;
+ gc.max_addr = gc.pools[gc.pools.length - 1].topAddr;
+ }
+ return pool;
+}
- if (pool)
- {
- auto biti = cast(size_t)(p - pool.baseAddr) / 16;
- oldb = gcx.getBits(pool, biti);
- gcx.clrBits(pool, biti, mask);
- }
- return oldb;
- }
+/**
+ * Allocate a page of bin's.
+ * Returns:
+ * 0 failed
+ */
+int allocPage(Bins bin)
+{
+ Pool* pool;
+ size_t n;
+ size_t pn;
+ byte* p;
+ byte* ptop;
- if (!thread_needLock())
- {
- return go();
- }
- else synchronized (gcLock)
- {
- return go();
- }
+ for (n = 0; n < gc.pools.length; n++)
+ {
+ pool = gc.pools[n];
+ pn = pool.allocPages(1);
+ if (pn != OPFAIL)
+ goto L1;
}
+ return 0; // failed
+ L1:
+ pool.pagetable[pn] = cast(ubyte)bin;
- /**
- *
- */
- void *malloc(size_t size, uint bits = 0)
- {
- if (!size)
- {
- return null;
- }
+ // Convert page to free list
+ size_t size = binsize[bin];
+ List **b = &gc.free_list[bin];
- if (!thread_needLock())
- {
- return mallocNoSync(size, bits);
- }
- else synchronized (gcLock)
- {
- return mallocNoSync(size, bits);
- }
+ p = pool.baseAddr + pn * PAGESIZE;
+ ptop = p + PAGESIZE;
+ for (; p < ptop; p += size)
+ {
+ (cast(List *)p).next = *b;
+ *b = cast(List *)p;
}
+ return 1;
+}
- //
- //
- //
- private void *mallocNoSync(size_t size, uint bits = 0)
- {
- assert(size != 0);
+/**
+ * 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)
+{
+ mark(pbot, ptop, PointerMap.init.bits.ptr);
+}
- void *p = null;
- Bins bin;
- assert(gcx);
+/**
+ * Search a range of memory values and mark any pointers into the GC pool.
+ */
+void mark(void *pbot, void *ptop, size_t* pm_bitmask)
+{
+ // TODO: make our own assert because assert uses the GC
+ assert (pbot <= ptop);
- size += SENTINEL_EXTRA;
+ const BITS_PER_WORD = size_t.sizeof * 8;
- // 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;
- }
+ void **p1 = cast(void **)pbot;
+ void **p2 = cast(void **)ptop;
+ size_t pcache = 0;
+ uint changes = 0;
- if (bin < B_PAGE)
- {
- p = gcx.bucket[bin];
- if (p is null)
- {
- 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))
- {
- gcx.newPool(1); // allocate new pool to find a new page
- int result = gcx.allocPage(bin);
- if (!result)
- onOutOfMemoryError();
- }
- p = gcx.bucket[bin];
- }
-
- // Return next item from free list
- gcx.bucket[bin] = (cast(List*)p).next;
- if( !(bits & BlkAttr.NO_SCAN) )
- cstring.memset(p + size, 0, binsize[bin] - size);
- debug (MEMSTOMP) cstring.memset(p, 0xF0, size);
- }
- else
- {
- p = gcx.bigAlloc(size);
- if (!p)
- onOutOfMemoryError();
- }
- size -= SENTINEL_EXTRA;
- p = sentinel_add(p);
- sentinel_init(p, size);
- gcx.log_malloc(p, size);
-
- if (bits)
- {
- Pool *pool = gcx.findPool(p);
- assert(pool);
-
- gcx.setBits(pool, cast(size_t)(p - pool.baseAddr) / 16, bits);
- }
- return p;
- }
-
-
- /**
- *
- */
- void *calloc(size_t size, uint bits = 0)
- {
- if (!size)
- {
- return null;
- }
-
- if (!thread_needLock())
- {
- return callocNoSync(size, bits);
- }
- else synchronized (gcLock)
- {
- return callocNoSync(size, bits);
- }
- }
+ size_t type_size = pm_bitmask[0];
+ size_t* pm_bits = pm_bitmask + 1;
+ //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;
- //
- //
- //
- private void *callocNoSync(size_t size, uint bits = 0)
- {
- assert(size != 0);
-
- void *p = mallocNoSync(size, bits);
- cstring.memset(p, 0, size);
- return p;
- }
-
+ void* p = *(p1 + n);
- /**
- *
- */
- void *realloc(void *p, size_t size, uint bits = 0)
- {
- if (!thread_needLock())
- {
- return reallocNoSync(p, size, bits);
- }
- else synchronized (gcLock)
- {
- return reallocNoSync(p, size, bits);
- }
- }
+ if (p < gc.min_addr || p >= gc.max_addr)
+ continue;
+ if ((cast(size_t)p & ~(PAGESIZE-1)) == pcache)
+ continue;
- //
- //
- //
- private void *reallocNoSync(void *p, size_t size, uint bits = 0)
- {
- if (!size)
- {
- if (p)
+ Pool* pool = findPool(p);
+ if (pool)
{
- freeNoSync(p);
- p = null;
- }
- }
- else if (!p)
- {
- p = mallocNoSync(size, bits);
- }
- else
- {
- void *p2;
- size_t psize;
+ 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];
- version (SENTINEL)
- {
- sentinel_Invariant(p);
- psize = *sentinel_size(p);
- if (psize != size)
+ // 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)
{
- if (psize)
+ do
{
- Pool *pool = gcx.findPool(p);
-
- if (pool)
- {
- auto biti = cast(size_t)(p - pool.baseAddr) / 16;
-
- if (bits)
- {
- gcx.clrBits(pool, biti, BlkAttr.ALL_BITS);
- gcx.setBits(pool, biti, bits);
- }
- else
- {
- bits = gcx.getBits(pool, biti);
- }
- }
+ --pn;
}
- p2 = mallocNoSync(size, bits);
- if (psize < size)
- size = psize;
- cstring.memcpy(p2, p, size);
- p = p2;
+ while (cast(Bins)pool.pagetable[pn] == B_PAGEPLUS);
+ bit_i = pn * (PAGESIZE / 16);
}
- }
- else
- {
- psize = gcx.findSize(p); // find allocated size
- if (psize >= PAGESIZE && size >= PAGESIZE)
+ else
{
- auto psz = psize / PAGESIZE;
- auto newsz = (size + PAGESIZE - 1) / PAGESIZE;
- if (newsz == psz)
- return p;
+ // Don't mark bits in B_FREE pages
+ continue;
+ }
- auto pool = gcx.findPool(p);
- auto pagenum = (p - pool.baseAddr) / PAGESIZE;
+ if (bin >= B_PAGE) // Cache B_PAGE and B_PAGEPLUS lookups
+ pcache = cast(size_t)p & ~(PAGESIZE-1);
- if (newsz < psz)
- {
- // Shrink in place
- synchronized (gcLock)
- {
- debug (MEMSTOMP)
- cstring.memset(p + size, 0xF2, psize - size);
- pool.freePages(pagenum + newsz, psz - newsz);
- }
- 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)
- {
- debug (MEMSTOMP)
- cstring.memset(p + psize, 0xF0,
- size - psize);
- cstring.memset(pool.pagetable + pagenum +
- psz, B_PAGEPLUS, newsz - psz);
- return p;
- }
- if (i == pool.npages)
- {
- break;
- }
- if (pool.pagetable[i] != B_FREE)
- break;
- i++;
- }
- }
- }
- }
- if (psize < size || // if new size is bigger
- psize > size * 2) // or less than half
+ if (!pool.mark.test(bit_i))
{
- if (psize)
+ pool.mark.set(bit_i);
+ if (!pool.noscan.test(bit_i))
{
- Pool *pool = gcx.findPool(p);
-
- if (pool)
- {
- auto biti = cast(size_t)(p - pool.baseAddr) / 16;
-
- if (bits)
- {
- gcx.clrBits(pool, biti, BlkAttr.ALL_BITS);
- gcx.setBits(pool, biti, bits);
- }
- else
- {
- bits = gcx.getBits(pool, biti);
- }
- }
+ pool.scan.set(bit_i);
+ changes = 1;
}
- p2 = mallocNoSync(size, bits);
- if (psize < size)
- size = psize;
- cstring.memcpy(p2, p, size);
- p = p2;
}
}
}
- return p;
- }
-
-
- /**
- * 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.
- */
- size_t extend(void* p, size_t minsize, size_t maxsize)
- {
- if (!thread_needLock())
- {
- return extendNoSync(p, minsize, maxsize);
- }
- else synchronized (gcLock)
- {
- return extendNoSync(p, minsize, maxsize);
- }
}
+ if (changes)
+ gc.any_changes = true;
+}
+/**
+ * Return number of full pages free'd.
+ */
+size_t fullcollectshell()
+{
+ gc.stats.collection_started();
+ scope (exit)
+ gc.stats.collection_finished();
- //
- //
- //
- private size_t extendNoSync(void* p, size_t minsize, size_t maxsize)
- in
+ // 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)
{
- assert( minsize <= maxsize );
+ gcc.builtins.__builtin_unwind_init();
+ sp = & sp;
}
- body
+ else version(LDC)
{
- version (SENTINEL)
+ version(X86)
{
- return 0;
- }
- auto psize = gcx.findSize(p); // find allocated size
- if (psize < PAGESIZE)
- return 0; // cannot extend buckets
-
- auto psz = psize / PAGESIZE;
- auto minsz = (minsize + PAGESIZE - 1) / PAGESIZE;
- auto maxsz = (maxsize + PAGESIZE - 1) / PAGESIZE;
-
- auto pool = gcx.findPool(p);
- 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)
+ uint eax,ecx,edx,ebx,ebp,esi,edi;
+ asm
{
- if (sz < minsz)
- return 0;
- break;
+ 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 ;
}
}
- if (sz < minsz)
- return 0;
- debug (MEMSTOMP)
- cstring.memset(p + psize, 0xF0, (psz + sz) * PAGESIZE - psize);
- cstring.memset(pool.pagetable + pagenum + psz, B_PAGEPLUS, sz);
- gcx.p_cache = null;
- gcx.size_cache = 0;
- return (psz + sz) * PAGESIZE;
- }
-
-
- /**
- *
- */
- size_t reserve(size_t size)
- {
- if (!size)
- {
- return 0;
- }
-
- if (!thread_needLock())
+ else version (X86_64)
{
- return reserveNoSync(size);
+ 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 synchronized (gcLock)
+ else
{
- return reserveNoSync(size);
+ static assert( false, "Architecture not supported." );
}
}
-
-
- //
- //
- //
- private size_t reserveNoSync(size_t size)
+ else
{
- assert(size != 0);
- assert(gcx);
-
- return gcx.reserve(size);
- }
-
-
- /**
- *
- */
- void free(void *p)
+ asm
{
- if (!p)
- {
- return;
- }
-
- if (!thread_needLock())
- {
- return freeNoSync(p);
- }
- else synchronized (gcLock)
- {
- return freeNoSync(p);
- }
+ pushad ;
+ mov sp[EBP],ESP ;
}
-
-
- //
- //
- //
- private void freeNoSync(void *p)
- {
- assert (p);
-
- Pool* pool;
- size_t pagenum;
- Bins bin;
- size_t biti;
-
- // Find which page it is in
- pool = gcx.findPool(p);
- if (!pool) // if not one of ours
- return; // ignore
- sentinel_Invariant(p);
- p = sentinel_sub(p);
- pagenum = cast(size_t)(p - pool.baseAddr) / PAGESIZE;
- biti = cast(size_t)(p - pool.baseAddr) / 16;
- gcx.clrBits(pool, biti, BlkAttr.ALL_BITS);
-
- 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++;
- debug (MEMSTOMP) cstring.memset(p, 0xF2, npages * PAGESIZE);
- pool.freePages(pagenum, npages);
- }
- else
- {
- // Add to free list
- List *list = cast(List*)p;
-
- debug (MEMSTOMP) cstring.memset(p, 0xF2, binsize[bin]);
-
- list.next = gcx.bucket[bin];
- gcx.bucket[bin] = list;
- }
- gcx.log_free(sentinel_add(p));
}
-
-
- /**
- * Determine the base address of the block containing p. If p is not a gc
- * allocated pointer, return null.
- */
- void* addrOf(void *p)
+ result = fullcollect(sp);
+ version (GNU)
{
- if (!p)
- {
- return null;
- }
-
- if (!thread_needLock())
- {
- return addrOfNoSync(p);
- }
- else synchronized (gcLock)
- {
- return addrOfNoSync(p);
- }
+ // nothing to do
}
-
-
- //
- //
- //
- void* addrOfNoSync(void *p)
+ else version(LDC)
{
- if (!p)
- {
- return null;
- }
-
- return gcx.findBase(p);
+ // nothing to do
}
-
-
- /**
- * Determine the allocated size of pointer p. If p is an interior pointer
- * or not a gc allocated pointer, return 0.
- */
- size_t sizeOf(void *p)
+ else
{
- if (!p)
- {
- return 0;
- }
-
- if (!thread_needLock())
- {
- return sizeOfNoSync(p);
- }
- else synchronized (gcLock)
- {
- return sizeOfNoSync(p);
- }
+ asm
+ {
+ popad ;
}
+ }
+ return result;
+}
- //
- //
- //
- private size_t sizeOfNoSync(void *p)
- {
- assert (p);
+/**
+ *
+ */
+size_t fullcollect(void *stackTop)
+{
+ size_t n;
+ Pool* pool;
- version (SENTINEL)
- {
- p = sentinel_sub(p);
- size_t size = gcx.findSize(p);
-
- // 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))
- size = 0;
- return size ? size - SENTINEL_EXTRA : 0;
- }
- else
- {
- if (p == gcx.p_cache)
- return gcx.size_cache;
+ debug(COLLECT_PRINTF) printf("Gcx.fullcollect()\n");
- size_t size = gcx.findSize(p);
+ thread_suspendAll();
+ gc.stats.world_stopped();
- // 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))
- size = 0;
- else
- {
- gcx.p_cache = p;
- gcx.size_cache = size;
- }
+ gc.p_cache = null;
+ gc.size_cache = 0;
- return size;
- }
+ gc.any_changes = false;
+ for (n = 0; n < gc.pools.length; n++)
+ {
+ pool = gc.pools[n];
+ pool.mark.zero();
+ pool.scan.zero();
+ pool.freebits.zero();
}
-
- /**
- * Determine the base address of the block containing p. If p is not a gc
- * allocated pointer, return null.
- */
- BlkInfo query(void *p)
+ // Mark each free entry, so it doesn't get scanned
+ for (n = 0; n < B_PAGE; n++)
{
- if (!p)
- {
- BlkInfo i;
- return i;
- }
-
- if (!thread_needLock())
- {
- return queryNoSync(p);
- }
- else synchronized (gcLock)
+ for (List *list = gc.free_list[n]; list; list = list.next)
{
- return queryNoSync(p);
+ pool = findPool(list);
+ assert(pool);
+ pool.freebits.set(cast(size_t)(cast(byte*)list - pool.baseAddr) / 16);
}
}
-
- //
- //
- //
- BlkInfo queryNoSync(void *p)
+ for (n = 0; n < gc.pools.length; n++)
{
- assert(p);
-
- return gcx.getInfo(p);
+ pool = gc.pools[n];
+ pool.mark.copy(&pool.freebits);
}
-
- /**
- * 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)
+ void mark_conservative_dg(void* pbot, void* ptop)
{
- if (!p)
- {
- return;
- }
-
- if (!thread_needLock())
- {
- checkNoSync(p);
- }
- else synchronized (gcLock)
- {
- checkNoSync(p);
- }
+ mark_conservative(pbot, ptop);
}
+ rt_scanStaticData(&mark_conservative_dg);
- //
- //
- //
- private void checkNoSync(void *p)
+ if (!gc.no_stack)
{
- assert(p);
-
- sentinel_Invariant(p);
- debug (PTRCHECK)
- {
- Pool* pool;
- size_t pagenum;
- Bins bin;
- size_t size;
-
- 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);
- }
- }
- }
- }
+ // Scan stacks and registers for each paused thread
+ thread_scanAll(&mark_conservative_dg, stackTop);
}
+ // Scan roots
+ debug(COLLECT_PRINTF) printf("scan roots[]\n");
+ mark_conservative(gc.roots.ptr, gc.roots.ptr + gc.roots.length);
- //
- //
- //
- private void setStackBottom(void *p)
- {
- version (STACKGROWSDOWN)
- {
- //p = (void *)((uint *)p + 4);
- if (p > gcx.stackBottom)
- {
- gcx.stackBottom = p;
- }
- }
- else
- {
- //p = (void *)((uint *)p - 4);
- if (p < gcx.stackBottom)
- {
- gcx.stackBottom = cast(char*)p;
- }
- }
- }
-
-
- /**
- * add p to list of roots
- */
- void addRoot(void *p)
- {
- if (!p)
- {
- return;
- }
-
- if (!thread_needLock())
- {
- gcx.addRoot(p);
- }
- else synchronized (gcLock)
- {
- gcx.addRoot(p);
- }
- }
-
-
- /**
- * remove p from list of roots
- */
- void removeRoot(void *p)
- {
- if (!p)
- {
- return;
- }
-
- if (!thread_needLock())
- {
- gcx.removeRoot(p);
- }
- else synchronized (gcLock)
- {
- gcx.removeRoot(p);
- }
- }
-
-
- /**
- * add range to scan for roots
- */
- void addRange(void *p, size_t sz)
- {
- if (!p || !sz)
- {
- return;
- }
-
- if (!thread_needLock())
- {
- gcx.addRange(p, p + sz);
- }
- else synchronized (gcLock)
- {
- gcx.addRange(p, p + sz);
- }
- }
-
-
- /**
- * remove range
- */
- void removeRange(void *p)
- {
- if (!p)
- {
- return;
- }
-
- if (!thread_needLock())
- {
- gcx.removeRange(p);
- }
- else synchronized (gcLock)
- {
- gcx.removeRange(p);
- }
- }
-
-
- /**
- * do full garbage collection
- */
- void fullCollect()
- {
-
- if (!thread_needLock())
- {
- gcx.fullcollectshell();
- }
- else synchronized (gcLock)
- {
- gcx.fullcollectshell();
- }
-
- version (none)
- {
- GCStats stats;
- getStats(stats);
- }
-
- gcx.log_collect();
- }
-
-
- /**
- * do full garbage collection ignoring roots
- */
- void fullCollectNoStack()
- {
- if (!thread_needLock())
- {
- gcx.noStack++;
- gcx.fullcollectshell();
- gcx.noStack--;
- }
- else synchronized (gcLock)
- {
- gcx.noStack++;
- gcx.fullcollectshell();
- gcx.noStack--;
- }
- }
-
-
- /**
- * minimize free space usage
- */
- void minimize()
- {
- if (!thread_needLock())
- {
- gcx.minimize();
- }
- else synchronized (gcLock)
- {
- gcx.minimize();
- }
- }
-
-
- /**
- * 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);
- }
- }
-
-
- //
- //
- //
- private void getStatsNoSync(out GCStats stats)
- {
- size_t psize = 0;
- size_t usize = 0;
- size_t flsize = 0;
-
- size_t n;
- size_t bsize = 0;
-
- cstring.memset(&stats, 0, GCStats.sizeof);
-
- for (n = 0; n < gcx.npools; n++)
- {
- Pool *pool = gcx.pooltable[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;
- }
- }
-
- 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;
-
- 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* 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;
-}
-
-
-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) ];
-
-/* ============================ Gcx =============================== */
-
-
-struct Gcx
-{
-
- void *p_cache;
- size_t size_cache;
-
- size_t nroots;
- size_t rootdim;
- void **roots;
-
- size_t nranges;
- size_t rangedim;
- Range *ranges;
-
- uint noStack; // !=0 means don't scan stack
- uint log; // turn on logging
- uint anychanges;
- void *stackBottom;
- uint inited;
- int disabled; // turn off collections if >0
-
- byte *minAddr; // min(baseAddr)
- byte *maxAddr; // max(topAddr)
-
- size_t npools;
- Pool **pooltable;
-
- List *bucket[B_MAX]; // free list for each size
-
-
- void initialize()
- {
- int dummy;
- (cast(byte*)this)[0 .. Gcx.sizeof] = 0;
- stackBottom = cast(char*)&dummy;
- log_init();
- //printf("gcx = %p, self = %x\n", this, self);
- inited = 1;
- }
-
-
- void Dtor()
- {
- inited = 0;
-
- for (size_t i = 0; i < npools; i++)
- {
- Pool *pool = pooltable[i];
- pool.Dtor();
- cstdlib.free(pool);
- }
- if (pooltable)
- cstdlib.free(pooltable);
-
- if (roots)
- cstdlib.free(roots);
-
- if (ranges)
- cstdlib.free(ranges);
- }
-
-
- void Invariant() { }
-
-
- invariant
- {
- if (inited)
- {
- //printf("Gcx.invariant(): this = %p\n", this);
- size_t i;
-
- for (i = 0; i < npools; i++)
- {
- Pool *pool = pooltable[i];
- pool.Invariant();
- if (i == 0)
- {
- assert(minAddr == pool.baseAddr);
- }
- if (i + 1 < npools)
- {
- assert(pool.opCmp(pooltable[i + 1]) < 0);
- }
- else if (i + 1 == npools)
- {
- assert(maxAddr == pool.topAddr);
- }
- }
-
- if (roots)
- {
- assert(rootdim != 0);
- assert(nroots <= rootdim);
- }
-
- if (ranges)
- {
- assert(rangedim != 0);
- assert(nranges <= rangedim);
-
- for (i = 0; i < nranges; 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)
- {
- }
- }
- }
- }
-
-
- /**
- *
- */
- void addRoot(void *p)
- {
- if (nroots == rootdim)
- {
- size_t newdim = rootdim * 2 + 16;
- void** newroots;
-
- newroots = cast(void**) cstdlib.malloc(newdim * newroots[0].sizeof);
- if (!newroots)
- onOutOfMemoryError();
- if (roots)
- {
- cstring.memcpy(newroots, roots, nroots * newroots[0].sizeof);
- cstdlib.free(roots);
- }
- roots = newroots;
- rootdim = newdim;
- }
- roots[nroots] = p;
- nroots++;
- }
-
-
- /**
- *
- */
- void removeRoot(void *p)
- {
- for (size_t i = nroots; i--;)
- {
- if (roots[i] == p)
- {
- nroots--;
- cstring.memmove(roots + i, roots + i + 1,
- (nroots - i) * roots[0].sizeof);
- return;
- }
- }
- assert(0);
- }
-
-
- /**
- *
- */
- void addRange(void *pbot, void *ptop)
- {
- if (nranges == rangedim)
- {
- size_t newdim = rangedim * 2 + 16;
- Range *newranges;
-
- newranges = cast(Range*) cstdlib.malloc(newdim * Range.sizeof);
- if (!newranges)
- onOutOfMemoryError();
- if (ranges)
- {
- cstring.memcpy(newranges, ranges, nranges * Range.sizeof);
- cstdlib.free(ranges);
- }
- ranges = newranges;
- rangedim = newdim;
- }
- ranges[nranges].pbot = pbot;
- ranges[nranges].ptop = ptop;
- nranges++;
- }
-
-
- /**
- *
- */
- void removeRange(void *pbot)
- {
- for (size_t i = nranges; i--;)
- {
- if (ranges[i].pbot == pbot)
- {
- nranges--;
- cstring.memmove(ranges + i, ranges + i + 1,
- (nranges - i) * ranges[0].sizeof);
- return;
- }
- }
-
- // This is a fatal error, but ignore it.
- // The problem is that we can get a Close() call on a thread
- // other than the one the range was allocated on.
- //assert(zero);
- }
-
-
- /**
- * Find Pool that pointer is in.
- * Return null if not in a Pool.
- * Assume pooltable[] is sorted.
- */
- Pool *findPool(void *p)
- {
- if (p >= minAddr && p < maxAddr)
- {
- if (npools == 1)
- {
- return pooltable[0];
- }
-
- for (size_t i = 0; i < npools; i++)
- {
- Pool *pool;
-
- pool = pooltable[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
- */
- void* findBase(void *p)
- {
- Pool *pool;
-
- pool = findPool(p);
- if (pool)
- {
- size_t offset = cast(size_t)(p - pool.baseAddr);
- size_t pn = offset / PAGESIZE;
- Bins bin = cast(Bins)pool.pagetable[pn];
-
- // 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)
- {
- do
- {
- --pn, offset -= PAGESIZE;
- } while (cast(Bins)pool.pagetable[pn] == B_PAGEPLUS);
-
- 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
- */
- size_t findSize(void *p)
- {
- Pool* pool;
- size_t size = 0;
-
- pool = findPool(p);
- if (pool)
- {
- 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 size;
- }
-
-
- /**
- *
- */
- BlkInfo getInfo(void* p)
- {
- Pool* pool;
- BlkInfo info;
-
- pool = findPool(p);
- if (pool)
- {
- 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];
- }
-
- ////////////////////////////////////////////////////////////////////
- // findSize
- ////////////////////////////////////////////////////////////////////
-
- info.size = binsize[bin];
- if (bin == B_PAGE)
- {
- ubyte* pt;
- size_t i;
-
- pt = &pool.pagetable[0];
- for (i = pn + 1; i < pool.npages; i++)
- {
- if (pt[i] != B_PAGEPLUS)
- break;
- }
- info.size = (i - pn) * PAGESIZE;
- }
-
- ////////////////////////////////////////////////////////////////////
- // getBits
- ////////////////////////////////////////////////////////////////////
-
- info.attr = getBits(pool, cast(size_t)(offset / 16));
- }
- return info;
- }
-
-
- /**
- * Compute bin for size.
- */
- static Bins findBin(size_t size)
- {
- Bins bin;
- if (size <= 256)
- {
- 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
- {
- 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;
- }
-
-
- /**
- * Allocate a new pool of at least size bytes.
- * Sort it into pooltable[].
- * 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)
- {
- size_t npages = (size + PAGESIZE - 1) / PAGESIZE;
- Pool* pool = newPool(npages);
-
- if (!pool)
- return 0;
- return pool.npages * PAGESIZE;
- }
-
-
- /**
- * Minimizes physical memory usage by returning free pools to the OS.
- */
- void minimize()
- {
- size_t n;
- size_t pn;
- Pool* pool;
-
- for (n = 0; n < npools; n++)
- {
- pool = pooltable[n];
- for (pn = 0; pn < pool.npages; pn++)
- {
- if (cast(Bins)pool.pagetable[pn] != B_FREE)
- break;
- }
- if (pn < pool.npages)
- {
- n++;
- continue;
- }
- pool.Dtor();
- cstdlib.free(pool);
- cstring.memmove(pooltable + n,
- pooltable + n + 1,
- (--npools - n) * (Pool*).sizeof);
- minAddr = pooltable[0].baseAddr;
- maxAddr = pooltable[npools - 1].topAddr;
- }
- }
-
-
- /**
- * 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;
-
- npages = (size + PAGESIZE - 1) / PAGESIZE;
-
- for (state = 0; ; )
- {
- // This code could use some refinement when repeatedly
- // allocating very large arrays.
-
- for (n = 0; n < npools; n++)
- {
- pool = pooltable[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 >= npools * ((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);
- }
- }
-
- L1:
- pool.pagetable[pn] = B_PAGE;
- if (npages > 1)
- cstring.memset(&pool.pagetable[pn + 1], B_PAGEPLUS, npages - 1);
- p = pool.baseAddr + pn * PAGESIZE;
- cstring.memset(cast(char *)p + size, 0, npages * PAGESIZE - size);
- debug (MEMSTOMP) cstring.memset(p, 0xF1, size);
- return p;
-
- Lnomemory:
- return null; // let mallocNoSync handle the error
- }
-
-
- /**
- * Allocate a new pool with at least npages in it.
- * Sort it into pooltable[].
- * Return null if failed.
- */
- Pool *newPool(size_t npages)
- {
- Pool* pool;
- Pool** newpooltable;
- size_t newnpools;
- size_t i;
-
- // Minimum of POOLSIZE
- if (npages < POOLSIZE/PAGESIZE)
- npages = POOLSIZE/PAGESIZE;
- else if (npages > POOLSIZE/PAGESIZE)
- {
- // 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;
- }
-
- // Allocate successively larger pools up to 8 megs
- if (npools)
- {
- size_t n = npools;
- if (n > 8)
- n = 8; // cap pool size at 8 megs
- n *= (POOLSIZE / PAGESIZE);
- if (npages < n)
- npages = n;
- }
-
- pool = cast(Pool *) cstdlib.calloc(1, Pool.sizeof);
- if (pool)
- {
- pool.initialize(npages);
- if (!pool.baseAddr)
- goto Lerr;
-
- newnpools = npools + 1;
- newpooltable = cast(Pool **) cstdlib.realloc(pooltable,
- newnpools * (Pool *).sizeof);
- if (!newpooltable)
- goto Lerr;
-
- // Sort pool into newpooltable[]
- for (i = 0; i < npools; i++)
- {
- if (pool.opCmp(newpooltable[i]) < 0)
- break;
- }
- cstring.memmove(newpooltable + i + 1, newpooltable + i,
- (npools - i) * (Pool *).sizeof);
- newpooltable[i] = pool;
-
- pooltable = newpooltable;
- npools = newnpools;
-
- minAddr = pooltable[0].baseAddr;
- maxAddr = pooltable[npools - 1].topAddr;
- }
- return pool;
-
- Lerr:
- pool.Dtor();
- cstdlib.free(pool);
- return null;
- }
-
-
- /**
- * Allocate a page of bin's.
- * Returns:
- * 0 failed
- */
- int allocPage(Bins bin)
+ // Scan ranges
+ debug(COLLECT_PRINTF) printf("scan ranges[]\n");
+ for (n = 0; n < gc.ranges.length; n++)
{
- Pool* pool;
- size_t n;
- size_t pn;
- byte* p;
- byte* ptop;
+ debug(COLLECT_PRINTF) printf("\t%x .. %x\n", gc.ranges[n].pbot, gc.ranges[n].ptop);
+ mark_conservative(gc.ranges[n].pbot, gc.ranges[n].ptop);
+ }
- for (n = 0; n < npools; n++)
+ debug(COLLECT_PRINTF) printf("\tscan heap\n");
+ while (gc.any_changes)
+ {
+ gc.any_changes = false;
+ for (n = 0; n < gc.pools.length; n++)
{
- pool = pooltable[n];
- pn = pool.allocPages(1);
- if (pn != OPFAIL)
- goto L1;
- }
- return 0; // failed
+ uint *bbase;
+ uint *b;
+ uint *btop;
+
+ pool = gc.pools[n];
- L1:
- pool.pagetable[pn] = cast(ubyte)bin;
+ 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;
- // Convert page to free list
- size_t size = binsize[bin];
- List **b = &bucket[bin];
+ bitm = *b;
+ if (!bitm)
+ {
+ b++;
+ continue;
+ }
+ *b = 0;
- p = pool.baseAddr + pn * PAGESIZE;
- ptop = p + PAGESIZE;
- for (; p < ptop; p += size)
- {
- (cast(List *)p).next = *b;
- *b = cast(List *)p;
+ 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;
+
+ 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);
+ }
+ }
+ }
+ }
}
- return 1;
}
+ thread_resumeAll();
+ gc.stats.world_started();
- /**
- * Search a range of memory values and mark any pointers into the GC pool.
- */
- void mark(void *pbot, void *ptop)
+ // Free up everything not marked
+ debug(COLLECT_PRINTF) printf("\tfree'ing\n");
+ size_t freedpages = 0;
+ size_t freed = 0;
+ for (n = 0; n < gc.pools.length; n++)
{
- void **p1 = cast(void **)pbot;
- void **p2 = cast(void **)ptop;
- size_t pcache = 0;
- uint changes = 0;
-
- //printf("marking range: %p -> %p\n", pbot, ptop);
- for (; p1 < p2; p1++)
+ pool = gc.pools[n];
+ uint* bbase = pool.mark.base();
+ size_t pn;
+ for (pn = 0; pn < pool.npages; pn++, bbase += PAGESIZE / (32 * 16))
{
- Pool *pool;
- byte *p = cast(byte *)(*p1);
+ Bins bin = cast(Bins)pool.pagetable[pn];
- if (p >= minAddr && p < maxAddr)
+ if (bin < B_PAGE)
{
- if ((cast(size_t)p & ~(PAGESIZE-1)) == pcache)
- continue;
+ 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;
- pool = findPool(p);
- if (pool)
+version(none) // BUG: doesn't work because freebits() must also be cleared
+{
+ // 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)
{
- size_t offset = cast(size_t)(p - pool.baseAddr);
- size_t biti;
- size_t pn = offset / PAGESIZE;
- Bins bin = cast(Bins)pool.pagetable[pn];
-
- // Adjust bit to be at start of allocated memory block
- if (bin <= B_PAGE)
- biti = (offset & notbinsize[bin]) >> 4;
- else if (bin == B_PAGEPLUS)
+ for (; p < ptop; p += size, bit_i += bit_stride)
{
- do
- {
- --pn;
+ if (pool.finals.nbits && pool.finals.testClear(bit_i)) {
+ if (opts.options.sentinel)
+ rt_finalize(cast(List *)sentinel_add(p), false/*gc.no_stack > 0*/);
+ else
+ rt_finalize(cast(List *)p, false/*gc.no_stack > 0*/);
}
- while (cast(Bins)pool.pagetable[pn] == B_PAGEPLUS);
- biti = pn * (PAGESIZE / 16);
+ clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
+
+ List *list = cast(List *)p;
+
+ if (opts.options.mem_stomp)
+ memset(p, 0xF3, size);
}
- else
+ pool.pagetable[pn] = B_FREE;
+ freed += PAGESIZE;
+ continue;
+ }
+}
+ for (; p < ptop; p += size, bit_i += bit_stride)
+ {
+ if (!pool.mark.test(bit_i))
{
- // Don't mark bits in B_FREE pages
- continue;
- }
+ 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/*gc.no_stack > 0*/);
+ else
+ rt_finalize(cast(List *)p, false/*gc.no_stack > 0*/);
+ }
+ clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
+
+ List *list = cast(List *)p;
- if (bin >= B_PAGE) // Cache B_PAGE and B_PAGEPLUS lookups
- pcache = cast(size_t)p & ~(PAGESIZE-1);
+ if (opts.options.mem_stomp)
+ memset(p, 0xF3, size);
+
+ 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/*gc.no_stack > 0*/);
+ else
+ rt_finalize(p, false/*gc.no_stack > 0*/);
+ }
+ clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
- if (!pool.mark.test(biti))
+ 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)
{
- pool.mark.set(biti);
- if (!pool.noscan.test(biti))
+ pn++;
+ pool.pagetable[pn] = B_FREE;
+ freedpages++;
+
+ if (opts.options.mem_stomp)
{
- pool.scan.set(biti);
- changes = 1;
+ p += PAGESIZE;
+ memset(p, 0xF3, PAGESIZE);
}
- log_parent(sentinel_add(pool.baseAddr + biti * 16), sentinel_add(pbot));
}
}
}
}
- anychanges |= changes;
}
+ // Zero buckets
+ gc.free_list[] = null;
- /**
- * Return number of full pages free'd.
- */
- size_t fullcollectshell()
+ // Free complete pages, rebuild free list
+ debug(COLLECT_PRINTF) printf("\tfree complete pages\n");
+ size_t recoveredpages = 0;
+ for (n = 0; n < gc.pools.length; n++)
{
- // 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)
+ pool = gc.pools[n];
+ for (size_t pn = 0; pn < pool.npages; pn++)
{
- gcc.builtins.__builtin_unwind_init();
- sp = & sp;
- }
- else version(LDC)
- {
- version(X86)
+ Bins bin = cast(Bins)pool.pagetable[pn];
+ size_t bit_i;
+ size_t u;
+
+ if (bin < B_PAGE)
{
- uint eax,ecx,edx,ebx,ebp,esi,edi;
- asm
+ 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)
{
- 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 ;
+ if (!pool.freebits.test(bit_i))
+ goto Lnotfree;
}
- }
- else version (X86_64)
- {
- ulong rax,rbx,rcx,rdx,rbp,rsi,rdi,r8,r9,r10,r11,r12,r13,r14,r15;
- asm
+ pool.pagetable[pn] = B_FREE;
+ recoveredpages++;
+ continue;
+
+ Lnotfree:
+ p = pool.baseAddr + pn * PAGESIZE;
+ for (u = 0; u < PAGESIZE; u += size)
{
- 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 ;
+ bit_i = bit_base + u / 16;
+ if (pool.freebits.test(bit_i))
+ {
+ List *list = cast(List *)(p + u);
+ // avoid unnecessary writes
+ if (list.next != gc.free_list[bin])
+ list.next = gc.free_list[bin];
+ gc.free_list[bin] = list;
+ }
}
}
- else
- {
- static assert( false, "Architecture not supported." );
- }
- }
- else
- {
- asm
- {
- pushad ;
- mov sp[EBP],ESP ;
- }
- }
- result = fullcollect(sp);
- version (GNU)
- {
- // nothing to do
- }
- else version(LDC)
- {
- // nothing to do
- }
- else
- {
- asm
- {
- popad ;
}
- }
- return result;
}
+ 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, gc.pools.length);
- /**
- *
- */
- size_t fullcollect(void *stackTop)
+ return freedpages + recoveredpages;
+}
+
+
+/**
+ *
+ */
+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;
+}
+
+
+/**
+ *
+ */
+void setAttr(Pool* pool, size_t bit_i, uint mask)
+in
+{
+ assert( pool );
+}
+body
+{
+ if (mask & BlkAttr.FINALIZE)
{
- size_t n;
- Pool* pool;
+ 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);
+// }
+}
+
+
+/**
+ *
+ */
+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);
+}
- debug(COLLECT_PRINTF) printf("Gcx.fullcollect()\n");
- thread_suspendAll();
- p_cache = null;
- size_cache = 0;
+void initialize()
+{
+ int dummy;
+ gc.stack_bottom = cast(char*)&dummy;
+ opts.parse(cstdlib.getenv("D_GC_OPTS"));
+ gc.lock = GCLock.classinfo;
+ gc.inited = 1;
+ setStackBottom(rt_stackBottom());
+ gc.stats = Stats(gc);
+}
- anychanges = 0;
- for (n = 0; n < npools; n++)
- {
- pool = pooltable[n];
- pool.mark.zero();
- pool.scan.zero();
- pool.freebits.zero();
- }
- // Mark each free entry, so it doesn't get scanned
- for (n = 0; n < B_PAGE; n++)
- {
- 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);
- }
- }
+//
+//
+//
+private void *malloc(size_t size, uint attrs, size_t* pm_bitmask)
+{
+ assert(size != 0);
- for (n = 0; n < npools; n++)
- {
- pool = pooltable[n];
- pool.mark.copy(&pool.freebits);
- }
+ gc.stats.malloc_started(size, attrs, pm_bitmask);
+ scope (exit)
+ gc.stats.malloc_finished(p);
- rt_scanStaticData( &mark );
+ void *p = null;
+ Bins bin;
- if (!noStack)
- {
- // Scan stacks and registers for each paused thread
- thread_scanAll( &mark, stackTop );
- }
+ if (opts.options.sentinel)
+ size += SENTINEL_EXTRA;
- // Scan roots[]
- debug(COLLECT_PRINTF) printf("scan roots[]\n");
- mark(roots, roots + nroots);
+ bool has_pm = has_pointermap(attrs);
+ if (has_pm)
+ size += size_t.sizeof;
- // Scan ranges[]
- debug(COLLECT_PRINTF) printf("scan ranges[]\n");
- //log++;
- for (n = 0; n < nranges; n++)
- {
- debug(COLLECT_PRINTF) printf("\t%x .. %x\n", ranges[n].pbot, ranges[n].ptop);
- mark(ranges[n].pbot, ranges[n].ptop);
- }
- //log--;
+ // Compute size bin
+ // Cache previous binsize lookup - Dave Fladebo.
+ static size_t lastsize = -1;
+ static Bins lastbin;
+ if (size == lastsize)
+ bin = lastbin;
+ else
+ {
+ bin = findBin(size);
+ lastsize = size;
+ lastbin = bin;
+ }
- debug(COLLECT_PRINTF) printf("\tscan heap\n");
- while (anychanges)
+ size_t capacity; // to figure out where to store the bitmask
+ if (bin < B_PAGE)
+ {
+ p = gc.free_list[bin];
+ if (p is null)
{
- anychanges = 0;
- for (n = 0; n < npools; n++)
+ if (!allocPage(bin) && !gc.disabled) // try to find a new page
{
- uint *bbase;
- uint *b;
- uint *btop;
-
- pool = pooltable[n];
-
- bbase = pool.scan.base();
- btop = bbase + pool.scan.nwords;
- for (b = bbase; b < btop;)
+ if (!thread_needLock())
{
- Bins bin;
- size_t pn;
- size_t u;
- size_t bitm;
- byte* o;
-
- 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)
+ /* Then we haven't locked it yet. Be sure
+ * and gc.lock for a collection, since a finalizer
+ * may start a new thread.
+ */
+ synchronized (gc.lock)
{
- if (!(bitm & 1))
- continue;
-
- pn = cast(size_t)(o - pool.baseAddr) / PAGESIZE;
- bin = cast(Bins)pool.pagetable[pn];
- if (bin < B_PAGE)
- {
- mark(o, o + binsize[bin]);
- }
- 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++;
- mark(o, o + u * PAGESIZE);
- }
+ fullcollectshell();
}
}
+ else if (!fullcollectshell()) // collect to find a new page
+ {
+ //newPool(1);
+ }
+ }
+ if (!gc.free_list[bin] && !allocPage(bin))
+ {
+ newPool(1); // allocate new pool to find a new page
+ int result = allocPage(bin);
+ if (!result)
+ onOutOfMemoryError();
}
+ p = gc.free_list[bin];
}
+ capacity = binsize[bin];
- thread_resumeAll();
+ // Return next item from free list
+ gc.free_list[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 = 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;
+ }
- // Free up everything not marked
- debug(COLLECT_PRINTF) printf("\tfree'ing\n");
- size_t freedpages = 0;
- size_t freed = 0;
- for (n = 0; n < npools; n++)
- {
- pool = pooltable[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];
+ // 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 (bin < B_PAGE)
- {
- auto size = binsize[bin];
- byte* p = pool.baseAddr + pn * PAGESIZE;
- byte* ptop = p + PAGESIZE;
- size_t biti = pn * (PAGESIZE/16);
- size_t bitstride = size / 16;
+ if (opts.options.sentinel) {
+ size -= SENTINEL_EXTRA;
+ p = sentinel_add(p);
+ sentinel_init(p, size);
+ }
- version(none) // BUG: doesn't work because freebits() must also be cleared
+ if (attrs)
{
- // 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, biti += bitstride)
- {
- if (pool.finals.nbits && pool.finals.testClear(biti))
- rt_finalize(cast(List *)sentinel_add(p), false/*noStack > 0*/);
- gcx.clrBits(pool, biti, BlkAttr.ALL_BITS);
+ Pool *pool = findPool(p);
+ assert(pool);
- List *list = cast(List *)p;
- log_free(sentinel_add(list));
-
- debug (MEMSTOMP) cstring.memset(p, 0xF3, size);
- }
- pool.pagetable[pn] = B_FREE;
- freed += PAGESIZE;
- continue;
- }
+ setAttr(pool, cast(size_t)(p - pool.baseAddr) / 16, attrs);
}
- for (; p < ptop; p += size, biti += bitstride)
- {
- if (!pool.mark.test(biti))
- {
- sentinel_Invariant(sentinel_add(p));
+ return p;
+}
- pool.freebits.set(biti);
- if (pool.finals.nbits && pool.finals.testClear(biti))
- rt_finalize(cast(List *)sentinel_add(p), false/*noStack > 0*/);
- clrBits(pool, biti, BlkAttr.ALL_BITS);
- List *list = cast(List *)p;
- log_free(sentinel_add(list));
+//
+//
+//
+private void *calloc(size_t size, uint attrs, size_t* pm_bitmask)
+{
+ assert(size != 0);
- debug (MEMSTOMP) cstring.memset(p, 0xF3, size);
+ void *p = malloc(size, attrs, pm_bitmask);
+ memset(p, 0, size);
+ return p;
+}
- freed += size;
- }
- }
- }
- else if (bin == B_PAGE)
- {
- size_t biti = pn * (PAGESIZE / 16);
- if (!pool.mark.test(biti))
- {
- byte *p = pool.baseAddr + pn * PAGESIZE;
- sentinel_Invariant(sentinel_add(p));
- if (pool.finals.nbits && pool.finals.testClear(biti))
- rt_finalize(sentinel_add(p), false/*noStack > 0*/);
- clrBits(pool, biti, BlkAttr.ALL_BITS);
- debug(COLLECT_PRINTF) printf("\tcollecting big %x\n", p);
- log_free(sentinel_add(p));
- pool.pagetable[pn] = B_FREE;
- freedpages++;
- debug (MEMSTOMP) cstring.memset(p, 0xF3, PAGESIZE);
- while (pn + 1 < pool.npages && pool.pagetable[pn + 1] == B_PAGEPLUS)
- {
- pn++;
- pool.pagetable[pn] = B_FREE;
- freedpages++;
-
- debug (MEMSTOMP)
- {
- p += PAGESIZE;
- cstring.memset(p, 0xF3, PAGESIZE);
- }
- }
- }
- }
- }
+//
+//
+//
+private void *realloc(void *p, size_t size, uint attrs,
+ size_t* pm_bitmask)
+{
+ if (!size)
+ {
+ if (p)
+ {
+ free(p);
+ p = null;
}
+ }
+ else if (!p)
+ {
+ p = malloc(size, attrs, pm_bitmask);
+ }
+ else
+ {
+ Pool* pool = findPool(p);
+ if (pool is null)
+ return null;
- // Zero buckets
- bucket[] = null;
+ // Set or retrieve attributes as appropriate
+ auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
+ if (attrs) {
+ clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
+ setAttr(pool, bit_i, attrs);
+ }
+ else
+ attrs = getAttr(pool, bit_i);
+
+ void* blk_base_addr = pool.findBase(p);
+ size_t blk_size = pool.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;
+ }
+ }
- // Free complete pages, rebuild free list
- debug(COLLECT_PRINTF) printf("\tfree complete pages\n");
- size_t recoveredpages = 0;
- for (n = 0; n < npools; n++)
+ if (opts.options.sentinel)
{
- pool = pooltable[n];
- for (size_t pn = 0; pn < pool.npages; pn++)
+ sentinel_Invariant(p);
+ size_t sentinel_stored_size = *sentinel_size(p);
+ if (sentinel_stored_size != size)
{
- Bins bin = cast(Bins)pool.pagetable[pn];
- size_t biti;
- size_t u;
+ void* p2 = malloc(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;
- if (bin < B_PAGE)
+ auto pagenum = (p - pool.baseAddr) / PAGESIZE;
+
+ if (newsz < psz)
{
- size_t size = binsize[bin];
- size_t bitstride = size / 16;
- size_t bitbase = pn * (PAGESIZE / 16);
- size_t bittop = bitbase + (PAGESIZE / 16);
- byte* p;
-
- biti = bitbase;
- for (biti = bitbase; biti < bittop; biti += bitstride)
- {
- if (!pool.freebits.test(biti))
- goto Lnotfree;
+ // Shrink in place
+ 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;
}
- pool.pagetable[pn] = B_FREE;
- recoveredpages++;
- continue;
-
- Lnotfree:
- p = pool.baseAddr + pn * PAGESIZE;
- for (u = 0; u < PAGESIZE; u += size)
+ return p;
+ }
+ else if (pagenum + newsz <= pool.npages)
+ {
+ // Attempt to expand in place
+ for (size_t i = pagenum + psz; 1;)
{
- biti = bitbase + u / 16;
- if (pool.freebits.test(biti))
+ 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)
{
- List *list = cast(List *)(p + u);
- if (list.next != bucket[bin]) // avoid unnecessary writes
- list.next = bucket[bin];
- bucket[bin] = list;
+ 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 = malloc(size, attrs, pm_bitmask);
+ if (blk_size < size)
+ size = blk_size;
+ cstring.memcpy(p2, p, size);
+ p = p2;
+ }
}
+ }
+ return p;
+}
+
+
+/**
+ * Attempt to in-place enlarge the memory block pointed to by p by at least
+ * min_size beyond its current capacity, up to a maximum of max_size. 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.
+ */
+private size_t extend(void* p, size_t minsize, size_t maxsize)
+in
+{
+ assert( minsize <= maxsize );
+}
+body
+{
+ if (opts.options.sentinel)
+ return 0;
- 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, npools);
+ Pool* pool = findPool(p);
+ if (pool is null)
+ return 0;
- return freedpages + recoveredpages;
- }
+ // Retrieve attributes
+ auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
+ uint attrs = getAttr(pool, bit_i);
+ void* blk_base_addr = pool.findBase(p);
+ size_t blk_size = pool.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;
- /**
- *
- */
- uint getBits(Pool* pool, size_t biti)
- in
- {
- assert( pool );
+ minsize += size_t.sizeof;
+ maxsize += size_t.sizeof;
}
- body
- {
- uint bits;
- if (pool.finals.nbits &&
- pool.finals.test(biti))
- bits |= BlkAttr.FINALIZE;
- if (pool.noscan.test(biti))
- bits |= BlkAttr.NO_SCAN;
-// if (pool.nomove.nbits &&
-// pool.nomove.test(biti))
-// bits |= BlkAttr.NO_MOVE;
- return bits;
- }
+ 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;
- /**
- *
- */
- void setBits(Pool* pool, size_t biti, uint mask)
- in
- {
- assert( pool );
- }
- body
+ auto pagenum = (p - pool.baseAddr) / PAGESIZE;
+
+ size_t sz;
+ for (sz = 0; sz < maxsz; sz++)
{
- if (mask & BlkAttr.FINALIZE)
+ auto i = pagenum + psz + sz;
+ if (i == pool.npages)
+ break;
+ if (pool.pagetable[i] != B_FREE)
{
- if (!pool.finals.nbits)
- pool.finals.alloc(pool.mark.nbits);
- pool.finals.set(biti);
+ if (sz < minsz)
+ return 0;
+ break;
}
- if (mask & BlkAttr.NO_SCAN)
- {
- pool.noscan.set(biti);
- }
-// if (mask & BlkAttr.NO_MOVE)
-// {
-// if (!pool.nomove.nbits)
-// pool.nomove.alloc(pool.mark.nbits);
-// pool.nomove.set(biti);
-// }
}
+ if (sz < minsz)
+ return 0;
+ size_t new_size = (psz + sz) * PAGESIZE;
- /**
- *
- */
- void clrBits(Pool* pool, size_t biti, uint mask)
- in
- {
- assert( pool );
+ 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);
+ gc.p_cache = null;
+ gc.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;
}
- body
- {
- if (mask & BlkAttr.FINALIZE && pool.finals.nbits)
- pool.finals.clear(biti);
- if (mask & BlkAttr.NO_SCAN)
- pool.noscan.clear(biti);
-// if (mask & BlkAttr.NO_MOVE && pool.nomove.nbits)
-// pool.nomove.clear(biti);
+ return new_size;
+}
+
+
+//
+//
+//
+private void free(void *p)
+{
+ assert (p);
+
+ Pool* pool;
+ size_t pagenum;
+ Bins bin;
+ size_t bit_i;
+
+ // Find which page it is in
+ pool = 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;
+ clrAttr(pool, bit_i, BlkAttr.ALL_BITS);
+ 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;
- /***** Leak Detector ******/
+ if (opts.options.mem_stomp)
+ memset(p, 0xF2, binsize[bin]);
+ list.next = gc.free_list[bin];
+ gc.free_list[bin] = list;
+ }
+}
- debug (LOGGING)
- {
- LogArray current;
- LogArray prev;
+/**
+ * Determine the allocated size of pointer p. If p is an interior pointer
+ * or not a gc allocated pointer, return 0.
+ */
+private size_t sizeOf(void *p)
+{
+ assert (p);
- void log_init()
- {
- current.reserve(1000);
- prev.reserve(1000);
- }
+ if (opts.options.sentinel)
+ p = sentinel_sub(p);
+ Pool* pool = findPool(p);
+ if (pool is null)
+ return 0;
- void log_malloc(void *p, size_t size)
- {
- Log log;
+ auto biti = cast(size_t)(p - pool.baseAddr) / 16;
+ uint attrs = getAttr(pool, biti);
- log.p = p;
- log.size = size;
- log.line = GC.line;
- log.file = GC.file;
- log.parent = null;
+ size_t size = pool.findSize(p);
+ size_t pm_bitmask_size = 0;
+ if (has_pointermap(attrs))
+ pm_bitmask_size = size_t.sizeof;
- GC.line = 0;
- GC.file = null;
+ 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 == gc.p_cache)
+ return gc.size_cache;
- current.push(log);
- }
+ // 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;
+ gc.p_cache = p;
+ gc.size_cache = size - pm_bitmask_size;
- void log_free(void *p)
- {
- size_t i;
+ return gc.size_cache;
+ }
+}
- i = current.find(p);
- if (i != OPFAIL)
- current.remove(i);
- }
+/**
+ * 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
+ */
+private void checkNoSync(void *p)
+{
+ assert(p);
- void log_collect()
- {
- // Print everything in current that is not in prev
- size_t used = 0;
- for (size_t i = 0; i < current.dim; i++)
- {
- size_t j;
+ if (opts.options.sentinel)
+ sentinel_Invariant(p);
+ debug (PTRCHECK)
+ {
+ Pool* pool;
+ size_t pagenum;
+ Bins bin;
+ size_t size;
- j = prev.find(current.data[i].p);
- if (j == OPFAIL)
- current.data[i].print();
- else
- used++;
- }
+ if (opts.options.sentinel)
+ p = sentinel_sub(p);
+ pool = 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);
- for (size_t i = 0; i < current.dim; i++)
+ debug (PTRCHECK2)
+ {
+ if (bin < B_PAGE)
{
- void *p;
- size_t j;
+ // Check that p is not on a free list
+ List *list;
- p = current.data[i].p;
- if (!findPool(current.data[i].parent))
+ for (list = gc.free_list[bin]; list; list = list.next)
{
- j = prev.find(current.data[i].p);
- current.data[i].print();
+ assert(cast(void*)list != p);
}
}
-
- prev.copy(¤t);
}
+ }
+}
- void log_parent(void *p, void *parent)
+//
+//
+//
+private void setStackBottom(void *p)
+{
+ version (STACKGROWSDOWN)
+ {
+ //p = (void *)((uint *)p + 4);
+ if (p > gc.stack_bottom)
+ {
+ gc.stack_bottom = p;
+ }
+ }
+ else
+ {
+ //p = (void *)((uint *)p - 4);
+ if (p < gc.stack_bottom)
{
- size_t i;
+ gc.stack_bottom = cast(char*)p;
+ }
+ }
+}
- i = current.find(p);
- if (i == OPFAIL)
- {
- Pool *pool;
- pool = findPool(p);
- assert(pool);
- size_t offset = cast(size_t)(p - pool.baseAddr);
- size_t biti;
- size_t pn = offset / PAGESIZE;
- Bins bin = cast(Bins)pool.pagetable[pn];
- biti = (offset & notbinsize[bin]);
- }
- else
- current.data[i].parent = parent;
+
+/**
+ * Retrieve statistics about garbage collection.
+ * Useful for debugging and tuning.
+ */
+private GCStats getStats()
+{
+ GCStats stats;
+ size_t psize = 0;
+ size_t usize = 0;
+ size_t flsize = 0;
+
+ size_t n;
+ size_t bsize = 0;
+
+ for (n = 0; n < gc.pools.length; n++)
+ {
+ Pool* pool = gc.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;
}
+ }
+ for (n = 0; n < B_PAGE; n++)
+ {
+ for (List *list = gc.free_list[n]; list; list = list.next)
+ flsize += binsize[n];
}
- else
+
+ usize = bsize - flsize;
+
+ stats.poolsize = psize;
+ stats.usedsize = bsize - flsize;
+ stats.freelistsize = flsize;
+ return stats;
+}
+
+/******************* weak-reference support *********************/
+
+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"
+ return 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)
{
- void log_init() { }
- void log_malloc(void *p, size_t size) { }
- void log_free(void *p) { }
- void log_collect() { }
- void log_parent(void *p, void *parent) { }
+ auto wp = cast(WeakPointer*)p;
+ // must be extra careful about the GC or parallel threads
+ // finalizing the reference at the same time
+ return 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;
+ })();
+ }
+}
+
/* ============================ Pool =============================== */
pagetable = cast(ubyte*) cstdlib.malloc(npages);
if (!pagetable)
onOutOfMemoryError();
- cstring.memset(pagetable, B_FREE, npages);
+ memset(pagetable, B_FREE, npages);
this.npages = npages;
}
baseAddr = null;
topAddr = null;
}
+ // See Gcx.Dtor() for the rationale of the null check.
if (pagetable)
cstdlib.free(pagetable);
}
- void Invariant() { }
+ bool Invariant()
+ {
+ return true;
+ }
invariant
*/
void freePages(size_t pagenum, size_t npages)
{
- cstring.memset(&pagetable[pagenum], B_FREE, npages);
+ memset(&pagetable[pagenum], B_FREE, npages);
+ }
+
+
+ /**
+ * Find base address of block containing pointer p.
+ * Returns null if the pointer doesn't belong to this pool
+ */
+ void* findBase(void *p)
+ {
+ size_t offset = cast(size_t)(p - this.baseAddr);
+ size_t pagenum = offset / PAGESIZE;
+ Bins bin = cast(Bins)this.pagetable[pagenum];
+ // Adjust bit to be at start of allocated memory block
+ if (bin <= B_PAGE)
+ return this.baseAddr + (offset & notbinsize[bin]);
+ if (bin == B_PAGEPLUS) {
+ do {
+ --pagenum, offset -= PAGESIZE;
+ } while (cast(Bins)this.pagetable[pagenum] == B_PAGEPLUS);
+ return this.baseAddr + (offset & (offset.max ^ (PAGESIZE-1)));
+ }
+ // we are in a B_FREE page
+ return null;
+ }
+
+
+ /**
+ * Find size of pointer p.
+ * Returns 0 if p doesn't belong to this pool if if it's block size is less
+ * than a PAGE.
+ */
+ size_t findSize(void *p)
+ {
+ size_t pagenum = cast(size_t)(p - this.baseAddr) / PAGESIZE;
+ Bins bin = cast(Bins)this.pagetable[pagenum];
+ if (bin != B_PAGE)
+ return binsize[bin];
+ for (size_t i = pagenum + 1; i < this.npages; i++)
+ if (this.pagetable[i] != B_PAGEPLUS)
+ return (i - pagenum) * PAGESIZE;
+ return (this.npages - pagenum) * PAGESIZE;
}
/**
- * Used for sorting pooltable[]
+ * Used for sorting pools
*/
- int opCmp(Pool *p2)
+ int opCmp(in Pool other)
{
- if (baseAddr < p2.baseAddr)
+ if (baseAddr < other.baseAddr)
return -1;
else
- return cast(int)(baseAddr > p2.baseAddr);
+ return cast(int)(baseAddr > other.baseAddr);
}
}
/* ============================ SENTINEL =============================== */
-version (SENTINEL)
+const size_t SENTINEL_PRE = cast(size_t) 0xF4F4F4F4F4F4F4F4UL; // 32 or 64 bits
+const ubyte SENTINEL_POST = 0xF5; // 8 bits
+const uint SENTINEL_EXTRA = 2 * size_t.sizeof + 1;
+
+
+size_t* sentinel_size(void *p) { return &(cast(size_t *)p)[-2]; }
+size_t* sentinel_pre(void *p) { return &(cast(size_t *)p)[-1]; }
+ubyte* sentinel_post(void *p) { return &(cast(ubyte *)p)[*sentinel_size(p)]; }
+
+
+void sentinel_init(void *p, size_t size)
{
- const size_t SENTINEL_PRE = cast(size_t) 0xF4F4F4F4F4F4F4F4UL; // 32 or 64 bits
- const ubyte SENTINEL_POST = 0xF5; // 8 bits
- const uint SENTINEL_EXTRA = 2 * size_t.sizeof + 1;
+ *sentinel_size(p) = size;
+ *sentinel_pre(p) = SENTINEL_PRE;
+ *sentinel_post(p) = SENTINEL_POST;
+}
- size_t* sentinel_size(void *p) { return &(cast(size_t *)p)[-2]; }
- size_t* sentinel_pre(void *p) { return &(cast(size_t *)p)[-1]; }
- ubyte* sentinel_post(void *p) { return &(cast(ubyte *)p)[*sentinel_size(p)]; }
+void sentinel_Invariant(void *p)
+{
+ assert(*sentinel_pre(p) == SENTINEL_PRE);
+ assert(*sentinel_post(p) == SENTINEL_POST);
+}
- void sentinel_init(void *p, size_t size)
- {
- *sentinel_size(p) = size;
- *sentinel_pre(p) = SENTINEL_PRE;
- *sentinel_post(p) = SENTINEL_POST;
- }
+void *sentinel_add(void *p)
+{
+ return p + 2 * size_t.sizeof;
+}
- void sentinel_Invariant(void *p)
- {
- assert(*sentinel_pre(p) == SENTINEL_PRE);
- assert(*sentinel_post(p) == SENTINEL_POST);
- }
+void *sentinel_sub(void *p)
+{
+ return p - 2 * size_t.sizeof;
+}
- void *sentinel_add(void *p)
- {
- return p + 2 * size_t.sizeof;
- }
+/* ============================ C Public Interface ======================== */
- void *sentinel_sub(void *p)
- {
- return p - 2 * size_t.sizeof;
- }
+
+private int _termCleanupLevel=1;
+
+extern (C):
+
+/// sets the cleanup level done by gc
+/// 0: none
+/// 1: fullCollect
+/// 2: fullCollect ignoring stack roots (might crash daemonThreads)
+/// result !=0 if the value was invalid
+int gc_setTermCleanupLevel(int cLevel)
+{
+ if (cLevel<0 || cLevel>2) return cLevel;
+ _termCleanupLevel=cLevel;
+ return 0;
}
-else
+
+/// returns the cleanup level done by gc
+int gc_getTermCleanupLevel()
{
- const uint SENTINEL_EXTRA = 0;
+ return _termCleanupLevel;
+}
+void gc_init()
+{
+ scope (exit) assert (Invariant());
+ gc = cast(GC*) cstdlib.calloc(1, GC.sizeof);
+ *gc = GC.init;
+ initialize();
+ version (DigitalMars) version(OSX) {
+ _d_osx_image_init();
+ }
+ // NOTE: The GC must initialize the thread library
+ // before its first collection.
+ thread_init();
+}
- void sentinel_init(void *p, size_t size)
- {
+void gc_term()
+{
+ assert (Invariant());
+ if (_termCleanupLevel<1) {
+ // no cleanup
+ } else if (_termCleanupLevel==2){
+ // a more complete cleanup
+ // NOTE: There may be daemons threads still running when this routine is
+ // called. If so, cleaning memory out from under then is a good
+ // way to make them crash horribly.
+ // Often this probably doesn't matter much since the app is
+ // supposed to be shutting down anyway, but for example tests might
+ // crash (and be considerd failed even if the test was ok).
+ // thus this is not the default and should be enabled by
+ // I'm disabling cleanup for now until I can think about it some
+ // more.
+ //
+ // not really a 'collect all' -- still scans static data area, roots,
+ // and ranges.
+ return locked!(void, () {
+ gc.no_stack++;
+ fullcollectshell();
+ gc.no_stack--;
+ })();
+ } else {
+ // default (safe) clenup
+ return locked!(void, () {
+ fullcollectshell();
+ })();
}
+}
+void gc_enable()
+{
+ return locked!(void, () {
+ assert (Invariant()); scope (exit) assert (Invariant());
+ assert (gc.disabled > 0);
+ gc.disabled--;
+ })();
+}
- void sentinel_Invariant(void *p)
- {
- }
+void gc_disable()
+{
+ return locked!(void, () {
+ assert (Invariant()); scope (exit) assert (Invariant());
+ gc.disabled++;
+ })();
+}
+void gc_collect()
+{
+ return locked!(void, () {
+ assert (Invariant()); scope (exit) assert (Invariant());
+ fullcollectshell();
+ })();
+}
- void *sentinel_add(void *p)
- {
- return p;
- }
+void gc_minimize()
+{
+ return locked!(void, () {
+ assert (Invariant()); scope (exit) assert (Invariant());
+ minimize();
+ })();
+}
- void *sentinel_sub(void *p)
- {
- return p;
- }
+uint gc_getAttr(void* p)
+{
+ if (p is null)
+ return 0;
+ return locked!(uint, () {
+ assert (Invariant()); scope (exit) assert (Invariant());
+ Pool* pool = findPool(p);
+ if (pool is null)
+ return 0u;
+ auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
+ return getAttr(pool, bit_i);
+ })();
}
+uint gc_setAttr(void* p, uint attrs)
+{
+ if (p is null)
+ return 0;
+ return locked!(uint, () {
+ assert (Invariant()); scope (exit) assert (Invariant());
+ Pool* pool = findPool(p);
+ if (pool is null)
+ return 0u;
+ auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
+ uint old_attrs = getAttr(pool, bit_i);
+ setAttr(pool, bit_i, attrs);
+ return old_attrs;
+ })();
+}
+
+uint gc_clrAttr(void* p, uint attrs)
+{
+ if (p is null)
+ return 0;
+ return locked!(uint, () {
+ assert (Invariant()); scope (exit) assert (Invariant());
+ Pool* pool = findPool(p);
+ if (pool is null)
+ return 0u;
+ auto bit_i = cast(size_t)(p - pool.baseAddr) / 16;
+ uint old_attrs = getAttr(pool, bit_i);
+ clrAttr(pool, bit_i, attrs);
+ return old_attrs;
+ })();
+}
+
+void* gc_malloc(size_t size, uint attrs = 0,
+ PointerMap ptrmap = PointerMap.init)
+{
+ if (size == 0)
+ return null;
+ return locked!(void*, () {
+ assert (Invariant()); scope (exit) assert (Invariant());
+ return malloc(size, attrs, ptrmap.bits.ptr);
+ })();
+}
+
+void* gc_calloc(size_t size, uint attrs = 0,
+ PointerMap ptrmap = PointerMap.init)
+{
+ if (size == 0)
+ return null;
+ return locked!(void*, () {
+ assert (Invariant()); scope (exit) assert (Invariant());
+ return calloc(size, attrs, ptrmap.bits.ptr);
+ })();
+}
+
+void* gc_realloc(void* p, size_t size, uint attrs = 0,
+ PointerMap ptrmap = PointerMap.init)
+{
+ return locked!(void*, () {
+ assert (Invariant()); scope (exit) assert (Invariant());
+ return realloc(p, size, attrs, ptrmap.bits.ptr);
+ })();
+}
+
+size_t gc_extend(void* p, size_t min_size, size_t max_size)
+{
+ return locked!(size_t, () {
+ assert (Invariant()); scope (exit) assert (Invariant());
+ return extend(p, min_size, max_size);
+ })();
+}
+
+size_t gc_reserve(size_t size)
+{
+ if (size == 0)
+ return 0;
+ return locked!(size_t, () {
+ assert (Invariant()); scope (exit) assert (Invariant());
+ return reserve(size);
+ })();
+}
+
+void gc_free(void* p)
+{
+ if (p is null)
+ return;
+ return locked!(void, () {
+ assert (Invariant()); scope (exit) assert (Invariant());
+ free(p);
+ })();
+}
+
+void* gc_addrOf(void* p)
+{
+ if (p is null)
+ return null;
+ return locked!(void*, () {
+ assert (Invariant()); scope (exit) assert (Invariant());
+ Pool* pool = findPool(p);
+ if (pool is null)
+ return null;
+ return pool.findBase(p);
+ })();
+}
+
+size_t gc_sizeOf(void* p)
+{
+ if (p is null)
+ return 0;
+ return locked!(size_t, () {
+ assert (Invariant()); scope (exit) assert (Invariant());
+ return sizeOf(p);
+ })();
+}
+
+BlkInfo gc_query(void* p)
+{
+ if (p is null)
+ return BlkInfo.init;
+ return locked!(BlkInfo, () {
+ assert (Invariant()); scope (exit) assert (Invariant());
+ return getInfo(p);
+ })();
+}
+
+// NOTE: This routine is experimental. The stats or function name may change
+// before it is made officially available.
+GCStats gc_stats()
+{
+ return locked!(GCStats, () {
+ assert (Invariant()); scope (exit) assert (Invariant());
+ return getStats();
+ })();
+}
+
+void gc_addRoot(void* p)
+{
+ if (p is null)
+ return;
+ return locked!(void, () {
+ assert (Invariant()); scope (exit) assert (Invariant());
+ if (gc.roots.append(p) is null)
+ onOutOfMemoryError();
+ })();
+}
+
+void gc_addRange(void* p, size_t size)
+{
+ if (p is null || size == 0)
+ return;
+ return locked!(void, () {
+ assert (Invariant()); scope (exit) assert (Invariant());
+ if (gc.ranges.append(Range(p, p + size)) is null)
+ onOutOfMemoryError();
+ })();
+}
+
+void gc_removeRoot(void* p)
+{
+ if (p is null)
+ return;
+ return locked!(void, () {
+ assert (Invariant()); scope (exit) assert (Invariant());
+ bool r = gc.roots.remove(p);
+ assert (r);
+ })();
+}
+
+void gc_removeRange(void* p)
+{
+ if (p is null)
+ return;
+ return locked!(void, () {
+ assert (Invariant()); scope (exit) assert (Invariant());
+ bool r = gc.ranges.remove(Range(p, null));
+ assert (r);
+ })();
+}
+
+void* gc_weakpointerCreate(Object r)
+{
+ // weakpointers do their own locking
+ return weakpointerCreate(r);
+}
+
+void gc_weakpointerDestroy(void* wp)
+{
+ // weakpointers do their own locking
+ weakpointerDestroy(wp);
+}
+
+Object gc_weakpointerGet(void* wp)
+{
+ // weakpointers do their own locking
+ return weakpointerGet(wp);
+}
+
+
+// vim: set et sw=4 sts=4 :
projects / software / dgc / cdgc.git / blobdiff