- //p = (void *)((uint *)p - 4);
- if (p < gcx.stackBottom)
- {
- //debug(PRINTF) printf("setStackBottom(%x)\n", p);
- 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;
- }
-
- //debug(PRINTF) printf("+GC.addRange(pbot = x%x, ptop = x%x)\n", pbot, ptop);
- if (!thread_needLock())
- {
- gcx.addRange(p, p + sz);
- }
- else synchronized (gcLock)
- {
- gcx.addRange(p, p + sz);
- }
- //debug(PRINTF) printf("-GC.addRange()\n");
- }
-
-
- /**
- * 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()
- {
- debug(PRINTF) printf("GC.fullCollect()\n");
-
- if (!thread_needLock())
- {
- gcx.fullcollectshell();
- }
- else synchronized (gcLock)
- {
- gcx.fullcollectshell();
- }
-
- version (none)
- {
- GCStats stats;
-
- getStats(stats);
- debug(PRINTF) printf("poolsize = %x, usedsize = %x, freelistsize = %x\n",
- stats.poolsize, stats.usedsize, stats.freelistsize);
- }
-
- 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;
-
- //debug(PRINTF) printf("getStats()\n");
- .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++)
- {
- //debug(PRINTF) printf("bin %d\n", n);
- for (List *list = gcx.bucket[n]; list; list = list.next)
- {
- //debug(PRINTF) printf("\tlist %x\n", list);
- 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*)(libc.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);
- });
- .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();
- .free(pool);
- }
- if (pooltable)
- .free(pooltable);
-
- if (roots)
- .free(roots);
-
- if (ranges)
- .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**) .malloc(newdim * newroots[0].sizeof);
- if (!newroots)
- onOutOfMemoryError();
- if (roots)
- { .memcpy(newroots, roots, nroots * newroots[0].sizeof);
- .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--;
- .memmove(roots + i, roots + i + 1, (nroots - i) * roots[0].sizeof);
- return;
- }
- }
- assert(0);
- }
-
-
- /**
- *
- */
- void addRange(void *pbot, void *ptop)
- {
- debug (PRINTF) printf("%x.Gcx::addRange(%x, %x), nranges = %d\n", this,
- pbot, ptop, nranges);
- if (nranges == rangedim)
- {
- size_t newdim = rangedim * 2 + 16;
- Range *newranges;
-
- newranges = cast(Range*) .malloc(newdim * newranges[0].sizeof);
- if (!newranges)
- onOutOfMemoryError();
- if (ranges)
- { .memcpy(newranges, ranges, nranges * newranges[0].sizeof);
- .free(ranges);
- }
- ranges = newranges;
- rangedim = newdim;
- }
- ranges[nranges].pbot = pbot;
- ranges[nranges].ptop = ptop;
- nranges++;
- }
-
-
- /**
- *
- */
- void removeRange(void *pbot)
- {
- debug (PRINTF) printf("%x.Gcx.removeRange(%x), nranges = %d\n", this,
- pbot, nranges);
- for (size_t i = nranges; i--;)
- {
- if (ranges[i].pbot == pbot)
- {
- nranges--;
- .memmove(ranges + i, ranges + i + 1, (nranges - i) * ranges[0].sizeof);
- return;
- }
- }
- debug(PRINTF) printf("Wrong thread\n");
-
- // 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();
- .free(pool);
- .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)
- .memset(&pool.pagetable[pn + 1], B_PAGEPLUS, npages - 1);
- p = pool.baseAddr + pn * PAGESIZE;
- .memset(cast(char *)p + size, 0, npages * PAGESIZE - size);
- debug (MEMSTOMP) .memset(p, 0xF1, size);
- //debug(PRINTF) printf("\tp = %x\n", p);
- 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;
-
- //debug(PRINTF) printf("************Gcx::newPool(npages = %d)****************\n", 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 (npools)
- { size_t n;
-
- n = npools;
- if (n > 8)
- n = 8; // cap pool size at 8 megs
- n *= (POOLSIZE / PAGESIZE);
- if (npages < n)
- npages = n;
- }
-
- pool = cast(Pool *) .calloc(1, Pool.sizeof);
- if (pool)
- {
- pool.initialize(npages);
- if (!pool.baseAddr)
- goto Lerr;
-
- newnpools = npools + 1;
- newpooltable = cast(Pool **) .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;
- }
- .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();
- .free(pool);
- return null;
- }
-
-
- /**
- * 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;
-
- //debug(PRINTF) printf("Gcx::allocPage(bin = %d)\n", bin);
- for (n = 0; n < npools; n++)
- {
- pool = pooltable[n];
- pn = pool.allocPages(1);
- if (pn != OPFAIL)
- goto L1;
- }
- return 0; // failed
projects / software / dgc / cdgc.git / blobdiff