X-Git-Url: https://git.llucax.com/software/dgc/cdgc.git/blobdiff_plain/58601dba4eeea662fb023c1f8c491bf4f6bb0668..7b736090719c6f08e286b246d9b7509413716fcf:/rt/gc/cdgc/gc.d diff --git a/rt/gc/cdgc/gc.d b/rt/gc/cdgc/gc.d index 6ed0b1d..2ec72c4 100644 --- a/rt/gc/cdgc/gc.d +++ b/rt/gc/cdgc/gc.d @@ -31,8 +31,6 @@ module rt.gc.cdgc.gc; /************** Debugging ***************************/ //debug = COLLECT_PRINTF; // turn on printf's -//debug = MEMSTOMP; // stomp on memory -//debug = SENTINEL; // add underrun/overrrun protection //debug = PTRCHECK; // more pointer checking //debug = PTRCHECK2; // thorough but slow pointer checking @@ -45,12 +43,32 @@ version = STACKGROWSDOWN; // growing the stack means subtracting from the /***************************************************/ import rt.gc.cdgc.bits: GCBits; -import rt.gc.cdgc.stats: GCStats; -import alloc = rt.gc.cdgc.alloc; +import rt.gc.cdgc.stats: GCStats, Stats; +import dynarray = rt.gc.cdgc.dynarray; +import os = rt.gc.cdgc.os; +import opts = rt.gc.cdgc.opts; import cstdlib = tango.stdc.stdlib; import cstring = tango.stdc.string; +import cstdio = tango.stdc.stdio; +debug(COLLECT_PRINTF) alias cstdio.printf printf; +/* + * 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) { @@ -61,7 +79,6 @@ version (GNU) static import gcc.builtins; // for __builtin_unwind_int } - struct BlkInfo { void* base; @@ -69,2417 +86,1897 @@ struct BlkInfo uint attr; } +package enum BlkAttr : uint +{ + FINALIZE = 0b0000_0001, + NO_SCAN = 0b0000_0010, + NO_MOVE = 0b0000_0100, + ALL_BITS = 0b1111_1111 +} + +package bool has_pointermap(uint attrs) +{ + return !opts.options.conservative && !(attrs & BlkAttr.NO_SCAN); +} + +private size_t round_up(size_t n, size_t to) +{ + return (n + to - 1) / to; +} + private { - enum BlkAttr : uint + alias void delegate(Object) DEvent; + alias void delegate( void*, void* ) scanFn; + enum { OPFAIL = ~cast(size_t)0 } + + extern (C) { - FINALIZE = 0b0000_0001, - NO_SCAN = 0b0000_0010, - NO_MOVE = 0b0000_0100, - ALL_BITS = 0b1111_1111 + version (DigitalMars) version(OSX) + oid _d_osx_image_init(); + + 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 ); + + void thread_init(); + bool thread_needLock(); + void thread_suspendAll(); + void thread_resumeAll(); + void thread_scanAll( scanFn fn, void* curStackTop = null ); + + void onOutOfMemoryError(); } +} - extern (C) void* rt_stackBottom(); - extern (C) void* rt_stackTop(); - extern (C) void rt_finalize( void* p, bool det = true ); +enum +{ + PAGESIZE = 4096, + POOLSIZE = (4096*256), +} - alias void delegate(Object) DEvent; - extern (C) void rt_attachDisposeEvent(Object h, DEvent e); - extern (C) bool rt_detachDisposeEvent(Object h, DEvent e); +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 void delegate( void*, void* ) scanFn; - extern (C) void rt_scanStaticData( scanFn scan ); +alias ubyte Bins; - extern (C) bool thread_needLock(); - extern (C) void thread_suspendAll(); - extern (C) void thread_resumeAll(); - extern (C) void thread_scanAll( scanFn fn, void* curStackTop = null ); +struct List +{ + List* next; + Pool* pool; +} - extern (C) void onOutOfMemoryError(); - enum +struct Range +{ + void *pbot; + void *ptop; + int opCmp(in Range other) { - OPFAIL = ~cast(size_t)0 + if (pbot < other.pbot) + return -1; + else + return cast(int)(pbot > other.pbot); } } -alias GC gc_t; +const uint binsize[B_MAX] = [ 16,32,64,128,256,512,1024,2048,4096 ]; +const uint notbinsize[B_MAX] = [ ~(16u-1),~(32u-1),~(64u-1),~(128u-1),~(256u-1), + ~(512u-1),~(1024u-1),~(2048u-1),~(4096u-1) ]; /* ============================ GC =============================== */ -class GCLock { } // just a dummy so we can get a global lock +class GCLock {} // just a dummy so we can get a global lock + + +struct GC +{ + // global lock + ClassInfo lock; + + void* p_cache; + size_t size_cache; + + // !=0 means don't scan stack + uint no_stack; + bool any_changes; + void* stack_bottom; + uint inited; + /// Turn off collections if > 0 + int disabled; + + // PID of the fork()ed process doing the mark() (0 if is not running) + int mark_proc_pid; + + /// min(pool.baseAddr) + byte *min_addr; + /// max(pool.topAddr) + byte *max_addr; + /// Total heap memory + size_t total_mem; + /// Free heap memory + size_t free_mem; -const uint GCVERSION = 1; // increment every time we change interface - // to GC. + /// Free list for each size + List*[B_MAX] free_list; -class GC + dynarray.DynArray!(void*) roots; + dynarray.DynArray!(Range) ranges; + dynarray.DynArray!(Pool*) pools; + + Stats stats; +} + +// call locked if necessary +private T locked(T, alias Code)() { - // For passing to debug code - static size_t line; - static char* file; + if (thread_needLock()) + synchronized (gc.lock) return Code(); + else + return Code(); +} - uint gcversion = GCVERSION; +private GC* gc; - Gcx *gcx; // implementation - static ClassInfo gcLock; // global lock +bool collect_in_progress() +{ + return gc.mark_proc_pid != 0; +} - 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) { + size_t total_mem = 0; + size_t free_mem = 0; + 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); + total_mem += pool.npages * PAGESIZE; + for (size_t pn = 0; pn < pool.npages; ++pn) + if (pool.pagetable[pn] == B_FREE) + free_mem += PAGESIZE; + } + + 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) { + auto pool = list.pool; + assert (pool !is null); + auto p = cast(byte*) list; + assert (p >= pool.baseAddr); + assert (p < pool.topAddr); + assert (pool.freebits.test((p - pool.baseAddr) / 16)); + free_mem += binsize[i]; + } + } + assert (gc.total_mem == total_mem); + assert (gc.free_mem == free_mem); } + return true; +} - /** - * - */ - void enable() +/** + * 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) + return null; + if (gc.pools.length == 0) + return null; + if (gc.pools.length == 1) + return gc.pools[0]; + /// The pooltable[] is sorted by address, so do a binary search + size_t low = 0; + size_t high = gc.pools.length - 1; + while (low <= high) { + size_t mid = (low + high) / 2; + auto pool = gc.pools[mid]; + if (p < pool.baseAddr) + high = mid - 1; + else if (p >= pool.topAddr) + low = mid + 1; + else + return pool; + } + // Not found + return null; +} + + +/** + * 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); + if (info.base is null) + return BlkInfo.init; + info.size = pool.findSize(info.base); + size_t bit_i = (info.base - pool.baseAddr) / 16; + info.attr = getAttr(pool, bit_i); + if (has_pointermap(info.attr)) { + info.size -= size_t.sizeof; // PointerMap bitmask + // Points to the PointerMap bitmask pointer, not user data + if (p >= (info.base + info.size)) { + return BlkInfo.init; + } + } + if (opts.options.sentinel) { + info.base = sentinel_add(info.base); + // points to sentinel data, not user data + if (p < info.base || p >= sentinel_post(info.base)) + return BlkInfo.init; + info.size -= SENTINEL_EXTRA; + } + return info; +} + + +/** + * Compute bin for size. + */ +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 = round_up(size, 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. + * + * If full is false, keep some pools alive if the resulting free memory would + * be too small. + */ +void minimize(bool full = true) +{ + // The shared mark bits of the freed pool might be used by the mark process + if (collect_in_progress()) + return; - if (!thread_needLock()) - { - return go(); - } - else synchronized (gcLock) + if (gc.pools.length == 0) + return; + + for (size_t n = 0; n < gc.pools.length; n++) + { + Pool* pool = gc.pools[n]; + size_t pn; + for (pn = 0; pn < pool.npages; pn++) { - return go(); + if (cast(Bins)pool.pagetable[pn] != B_FREE) + break; } + if (pn < pool.npages) + continue; + // Free pool + size_t pool_size = pool.npages * PAGESIZE; + if (!full) { + double percent_free = (gc.free_mem - pool_size) * 100.0 / + (gc.total_mem - pool_size); + if (percent_free < opts.options.min_free) + continue; // not enough free, don't remove this pool + } + gc.total_mem -= pool_size; + gc.free_mem -= pool_size; + pool.Dtor(); + cstdlib.free(pool); + 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 npages, out Pool* pool, size_t* pn, bool* collected) +{ + *collected = false; + // This code could use some refinement when repeatedly + // allocating very large arrays. + + void* find_block() { - if (!p) + for (size_t n = 0; n < gc.pools.length; n++) { - return 0; + pool = gc.pools[n]; + *pn = pool.allocPages(npages); + if (*pn != OPFAIL) + return pool.baseAddr + *pn * PAGESIZE; } + return null; + } - uint go() - { - Pool* pool = gcx.findPool(p); - uint oldb = 0; + void* alloc_more() + { + // Allocate new pool + pool = newPool(npages); + if (!pool) + return null; // let malloc handle the error + *pn = pool.allocPages(npages); + assert(*pn != OPFAIL); + return pool.baseAddr + *pn * PAGESIZE; + } - if (pool) - { - auto biti = cast(size_t)(p - pool.baseAddr) / 16; + if (void* p = find_block()) + return p; - oldb = gcx.getBits(pool, biti); - gcx.setBits(pool, biti, mask); - } - return oldb; - } + if (gc.disabled) + return alloc_more(); - if (!thread_needLock()) - { - return go(); - } - else synchronized (gcLock) - { - return go(); - } + // Try collecting + size_t freedpages = fullcollectshell(); + *collected = true; + if (freedpages >= npages) { + if (void* p = find_block()) + return p; } + return alloc_more(); +} - /** - * - */ - uint clrAttr(void* p, uint mask) - { - if (!p) - { - return 0; - } - uint go() - { - Pool* pool = gcx.findPool(p); - uint oldb = 0; +/** + * 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; + } - if (pool) - { - auto biti = cast(size_t)(p - pool.baseAddr) / 16; + // 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; + } - oldb = gcx.getBits(pool, biti); - gcx.clrBits(pool, biti, mask); - } - return oldb; - } + auto pool = cast(Pool*) cstdlib.calloc(1, Pool.sizeof); + if (pool is null) + return null; + pool.initialize(npages); + if (!pool.baseAddr) + { + pool.Dtor(); + return null; + } - if (!thread_needLock()) - { - return go(); - } - else synchronized (gcLock) - { - return go(); - } + auto inserted_pool = *gc.pools.insert_sorted!("*a < *b")(pool); + if (inserted_pool is null) { + pool.Dtor(); + return null; } + assert (inserted_pool is pool); + gc.min_addr = gc.pools[0].baseAddr; + gc.max_addr = gc.pools[gc.pools.length - 1].topAddr; + size_t pool_size = pool.topAddr - pool.baseAddr; + gc.total_mem += pool_size; + gc.free_mem += pool_size; + return pool; +} - /** - * - */ - void *malloc(size_t size, uint bits = 0) - { - if (!size) - { - return null; - } +/** + * Allocate a page of bin's. + * Returns: + * 0 failed + */ +int allocPage(Bins bin) +{ + Pool* pool; + size_t pn; - if (!thread_needLock()) - { - return mallocNoSync(size, bits); - } - else synchronized (gcLock) - { - return mallocNoSync(size, bits); - } + for (size_t 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; + // Convert page to free list + size_t size = binsize[bin]; + auto list_head = &gc.free_list[bin]; - // - // - // - private void *mallocNoSync(size_t size, uint bits = 0) + byte* p = pool.baseAddr + pn * PAGESIZE; + byte* ptop = p + PAGESIZE; + size_t bit_i = pn * (PAGESIZE / 16); + pool.freebits.set_group(bit_i, PAGESIZE / 16); + for (; p < ptop; p += size) { - assert(size != 0); + List* l = cast(List *) p; + l.next = *list_head; + l.pool = pool; + *list_head = l; + } + return 1; +} - void *p = null; - Bins bin; - assert(gcx); +/** + * Search a range of memory values and mark any pointers into the GC pool using + * type information (bitmask of pointer locations). + */ +void mark_range(void *pbot, void *ptop, size_t* pm_bitmask) +{ + // TODO: make our own assert because assert uses the GC + assert (pbot <= ptop); + + const BITS_PER_WORD = size_t.sizeof * 8; + + void **p1 = cast(void **)pbot; + void **p2 = cast(void **)ptop; + size_t pcache = 0; + bool changes = false; + + size_t type_size = pm_bitmask[0]; + size_t* pm_bits = pm_bitmask + 1; + bool has_type_info = type_size != 1 || pm_bits[0] != 1 || pm_bits[1] != 0; + + //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 (has_type_info && + !(pm_bits[n / BITS_PER_WORD] & (1 << (n % BITS_PER_WORD)))) + continue; - size += SENTINEL_EXTRA; + void* p = *(p1 + n); - // 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; - } + if (p < gc.min_addr || p >= gc.max_addr) + continue; - if (bin < B_PAGE) - { - p = gcx.bucket[bin]; - if (p is null) + if ((cast(size_t)p & ~(PAGESIZE-1)) == pcache) + continue; + + Pool* pool = findPool(p); + if (pool) { - if (!gcx.allocPage(bin) && !gcx.disabled) // try to find a new page + size_t offset = cast(size_t)(p - pool.baseAddr); + size_t bit_i = void; + size_t pn = offset / PAGESIZE; + Bins bin = cast(Bins)pool.pagetable[pn]; + + // Cache B_PAGE, B_PAGEPLUS and B_FREE lookups + if (bin >= B_PAGE) + pcache = cast(size_t)p & ~(PAGESIZE-1); + + // Adjust bit to be at start of allocated memory block + if (bin <= B_PAGE) + bit_i = (offset & notbinsize[bin]) / 16; + else if (bin == B_PAGEPLUS) { - 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 + do { - //gcx.newPool(1); + --pn; } + while (cast(Bins)pool.pagetable[pn] == B_PAGEPLUS); + bit_i = pn * (PAGESIZE / 16); } - if (!gcx.bucket[bin] && !gcx.allocPage(bin)) + else // Don't mark bits in B_FREE pages + continue; + + if (!pool.mark.test(bit_i)) { - gcx.newPool(1); // allocate new pool to find a new page - int result = gcx.allocPage(bin); - if (!result) - onOutOfMemoryError(); + pool.mark.set(bit_i); + if (!pool.noscan.test(bit_i)) + { + pool.scan.set(bit_i); + changes = true; + } } - 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); - - if (bits) - { - Pool *pool = gcx.findPool(p); - assert(pool); - - gcx.setBits(pool, cast(size_t)(p - pool.baseAddr) / 16, bits); } - return p; } + 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(); - /** - * - */ - void *calloc(size_t size, uint bits = 0) + // The purpose of the 'shell' is to ensure all the registers + // get put on the stack so they'll be scanned + void *sp; + size_t result; + version (GNU) { - if (!size) + gcc.builtins.__builtin_unwind_init(); + sp = & sp; + } + else version(LDC) + { + version(X86) { - return null; - } - - if (!thread_needLock()) + uint eax,ecx,edx,ebx,ebp,esi,edi; + asm + { + mov eax[EBP], EAX ; + mov ecx[EBP], ECX ; + mov edx[EBP], EDX ; + mov ebx[EBP], EBX ; + mov ebp[EBP], EBP ; + mov esi[EBP], ESI ; + mov edi[EBP], EDI ; + mov sp[EBP], ESP ; + } + } + else version (X86_64) { - return callocNoSync(size, bits); + 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 callocNoSync(size, bits); + 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; +} + + +/** + * + */ +size_t fullcollect(void *stackTop) +{ + debug(COLLECT_PRINTF) printf("Gcx.fullcollect()\n"); + + // If eager allocation is used, we need to check first if there is a mark + // process running. If there isn't, we start a new one (see the next code + // block). If there is, we check if it's still running or already finished. + // If it's still running, we tell the caller process no memory has been + // recovered (it will allocated more to fulfill the current request). If + // the mark process is done, we lunch the sweep phase and hope enough + // memory is freed (if that not the case, the caller will allocate more + // memory and the next time it's exhausted it will run a new collection). + if (opts.options.eager_alloc) { + if (collect_in_progress()) { + os.WRes r = os.wait_pid(gc.mark_proc_pid, false); // don't block + assert (r != os.WRes.ERROR); + switch (r) { + case os.WRes.DONE: + debug(COLLECT_PRINTF) printf("\t\tmark proc DONE\n"); + gc.mark_proc_pid = 0; + return sweep(); + case os.WRes.RUNNING: + debug(COLLECT_PRINTF) printf("\t\tmark proc RUNNING\n"); + return 0; + case os.WRes.ERROR: + debug(COLLECT_PRINTF) printf("\t\tmark proc ERROR\n"); + disable_fork(); // Try to keep going without forking + break; + } + } + } + + // We always need to stop the world to make threads save the CPU registers + // in the stack and prepare themselves for thread_scanAll() + thread_suspendAll(); + gc.stats.world_stopped(); + + // If forking is enabled, we fork() and start a new mark phase in the + // child. The parent process will tell the caller that no memory could be + // recycled if eager allocation is used, allowing the mutator to keep going + // almost instantly (at the expense of more memory consumption because + // a new allocation will be triggered to fulfill the current request). If + // no eager allocation is used, the parent will wait for the mark phase to + // finish before returning control to the mutator, but other threads are + // restarted and may run in parallel with the mark phase (unless they + // allocate or use the GC themselves, in which case the global GC lock will + // stop them). + if (opts.options.fork) { + cstdio.fflush(null); // avoid duplicated FILE* output + os.pid_t child_pid = os.fork(); + assert (child_pid != -1); // don't accept errors in non-release mode + switch (child_pid) { + case -1: // if fork() fails, fall-back to stop-the-world + disable_fork(); + break; + case 0: // child process (i.e. the collectors mark phase) + mark(stackTop); + cstdlib.exit(0); + break; // bogus, will never reach here + default: // parent process (i.e. the mutator) + // start the world again and wait for the mark phase to finish + thread_resumeAll(); + gc.stats.world_started(); + if (opts.options.eager_alloc) { + gc.mark_proc_pid = child_pid; + return 0; + } + os.WRes r = os.wait_pid(child_pid); // block until it finishes + assert (r == os.WRes.DONE); + debug(COLLECT_PRINTF) printf("\t\tmark proc DONE (block)\n"); + if (r == os.WRes.DONE) + return sweep(); + debug(COLLECT_PRINTF) printf("\tmark() proc ERROR\n"); + // If there was some error, try to keep going without forking + disable_fork(); + // Re-suspend the threads to do the marking in this process + thread_suspendAll(); + gc.stats.world_stopped(); } + } + // If we reach here, we are using the standard stop-the-world collection, + // either because fork was disabled in the first place, or because it was + // disabled because of some error. + mark(stackTop); + thread_resumeAll(); + gc.stats.world_started(); + + return sweep(); +} + + +/** + * + */ +void mark(void *stackTop) +{ + debug(COLLECT_PRINTF) printf("\tmark()\n"); + + gc.any_changes = false; - // - // - // - private void *callocNoSync(size_t size, uint bits = 0) + for (size_t n = 0; n < gc.pools.length; n++) { - assert(size != 0); + Pool* pool = gc.pools[n]; + pool.mark.copy(&pool.freebits); + pool.scan.zero(); + } - void *p = mallocNoSync(size, bits); - cstring.memset(p, 0, size); - return p; + /// Marks a range of memory in conservative mode. + void mark_conservative_range(void* pbot, void* ptop) + { + mark_range(pbot, ptop, PointerMap.init.bits.ptr); } + rt_scanStaticData(&mark_conservative_range); - /** - * - */ - void *realloc(void *p, size_t size, uint bits = 0) + if (!gc.no_stack) { - if (!thread_needLock()) - { - return reallocNoSync(p, size, bits); - } - else synchronized (gcLock) - { - return reallocNoSync(p, size, bits); - } + // Scan stacks and registers for each paused thread + thread_scanAll(&mark_conservative_range, stackTop); } + // Scan roots + debug(COLLECT_PRINTF) printf("scan roots[]\n"); + mark_conservative_range(gc.roots.ptr, gc.roots.ptr + gc.roots.length); - // - // - // - private void *reallocNoSync(void *p, size_t size, uint bits = 0) + // Scan ranges + debug(COLLECT_PRINTF) printf("scan ranges[]\n"); + for (size_t n = 0; n < gc.ranges.length; n++) { - if (!size) - { - if (p) - { - freeNoSync(p); - p = null; - } - } - else if (!p) - { - p = mallocNoSync(size, bits); - } - else + debug(COLLECT_PRINTF) printf("\t%x .. %x\n", gc.ranges[n].pbot, gc.ranges[n].ptop); + mark_conservative_range(gc.ranges[n].pbot, gc.ranges[n].ptop); + } + + debug(COLLECT_PRINTF) printf("\tscan heap\n"); + while (gc.any_changes) + { + gc.any_changes = false; + for (size_t n = 0; n < gc.pools.length; n++) { - void *p2; - size_t psize; + uint *bbase; + uint *b; + uint *btop; + + Pool* pool = gc.pools[n]; - version (SENTINEL) + bbase = pool.scan.base(); + btop = bbase + pool.scan.nwords; + for (b = bbase; b < btop;) { - sentinel_Invariant(p); - psize = *sentinel_size(p); - if (psize != size) + Bins bin; + size_t pn; + size_t u; + size_t bitm; + byte* o; + + bitm = *b; + if (!bitm) { - if (psize) - { - Pool *pool = gcx.findPool(p); + b++; + continue; + } + *b = 0; - if (pool) - { - auto biti = cast(size_t)(p - pool.baseAddr) / 16; + 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; - if (bits) - { - gcx.clrBits(pool, biti, BlkAttr.ALL_BITS); - gcx.setBits(pool, biti, bits); - } - else - { - bits = gcx.getBits(pool, biti); - } + pn = cast(size_t)(o - pool.baseAddr) / PAGESIZE; + bin = cast(Bins)pool.pagetable[pn]; + if (bin < B_PAGE) { + if (opts.options.conservative) + mark_conservative_range(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_range(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_range(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_range(o, end_of_blk, pm_bitmask); } } - p2 = mallocNoSync(size, bits); - if (psize < size) - size = psize; - cstring.memcpy(p2, p, size); - p = p2; } } - else - { - psize = gcx.findSize(p); // find allocated size - if (psize >= PAGESIZE && size >= PAGESIZE) - { - auto psz = psize / PAGESIZE; - auto newsz = (size + PAGESIZE - 1) / PAGESIZE; - if (newsz == psz) - return p; + } + } +} + + +/** + * + */ +size_t sweep() +{ + // Free up everything not marked + debug(COLLECT_PRINTF) printf("\tsweep\n"); + gc.p_cache = null; + gc.size_cache = 0; + gc.free_mem = 0; // will be recalculated + size_t freedpages = 0; + size_t freed = 0; + for (size_t n = 0; n < gc.pools.length; n++) + { + Pool* pool = gc.pools[n]; + pool.clear_cache(); + 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]; - auto pool = gcx.findPool(p); - auto pagenum = (p - pool.baseAddr) / PAGESIZE; + if (bin < B_PAGE) + { + auto size = binsize[bin]; + byte* p = pool.baseAddr + pn * PAGESIZE; + byte* ptop = p + PAGESIZE; + size_t bit_i = pn * (PAGESIZE/16); + size_t bit_stride = size / 16; - if (newsz < psz) +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) + { + for (; p < ptop; p += size, bit_i += bit_stride) { - // Shrink in place - synchronized (gcLock) - { - debug (MEMSTOMP) - cstring.memset(p + size, 0xF2, psize - size); - pool.freePages(pagenum + newsz, psz - newsz); + if (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*/); } - return p; + clrAttr(pool, bit_i, BlkAttr.ALL_BITS); + + if (opts.options.mem_stomp) + memset(p, 0xF3, size); } - else if (pagenum + newsz <= pool.npages) + pool.pagetable[pn] = B_FREE; + freed += PAGESIZE; + continue; + } +} + for (; p < ptop; p += size, bit_i += bit_stride) + { + if (!pool.mark.test(bit_i)) { - // 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 (opts.options.sentinel) + sentinel_Invariant(sentinel_add(p)); + + pool.freebits.set(bit_i); + if (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 (opts.options.mem_stomp) + memset(p, 0xF3, size); + + freed += size; } } - if (psize < size || // if new size is bigger - psize > size * 2) // or less than half + } + else if (bin == B_PAGE) + { + size_t bit_stride = PAGESIZE / 16; + size_t bit_i = pn * bit_stride; + if (!pool.mark.test(bit_i)) { - if (psize) + byte *p = pool.baseAddr + pn * PAGESIZE; + if (opts.options.sentinel) + sentinel_Invariant(sentinel_add(p)); + if (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); + + debug(COLLECT_PRINTF) printf("\tcollecting big %p\n", p); + pool.pagetable[pn] = B_FREE; + pool.freebits.set_group(bit_i, PAGESIZE / 16); + freedpages++; + gc.free_mem += PAGESIZE; + if (opts.options.mem_stomp) + memset(p, 0xF3, PAGESIZE); + while (pn + 1 < pool.npages && pool.pagetable[pn + 1] == B_PAGEPLUS) { - Pool *pool = gcx.findPool(p); + pn++; + pool.pagetable[pn] = B_FREE; + bit_i += bit_stride; + pool.freebits.set_group(bit_i, PAGESIZE / 16); + freedpages++; + gc.free_mem += PAGESIZE; - if (pool) + if (opts.options.mem_stomp) { - 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); - } + p += PAGESIZE; + memset(p, 0xF3, PAGESIZE); } } - p2 = mallocNoSync(size, bits); - if (psize < size) - size = psize; - cstring.memcpy(p2, p, size); - p = p2; } } + else if (bin == B_FREE) { + gc.free_mem += PAGESIZE; + } } - return p; } + // Zero buckets + gc.free_list[] = null; - /** - * 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) + // Free complete pages, rebuild free list + debug(COLLECT_PRINTF) printf("\tfree complete pages\n"); + size_t recoveredpages = 0; + for (size_t n = 0; n < gc.pools.length; n++) { - if (!thread_needLock()) - { - return extendNoSync(p, minsize, maxsize); - } - else synchronized (gcLock) + Pool* pool = gc.pools[n]; + for (size_t pn = 0; pn < pool.npages; pn++) { - return extendNoSync(p, minsize, maxsize); + Bins bin = cast(Bins)pool.pagetable[pn]; + size_t bit_i; + size_t u; + + if (bin < B_PAGE) + { + size_t size = binsize[bin]; + size_t bit_stride = size / 16; + size_t bit_base = pn * (PAGESIZE / 16); + size_t bit_top = bit_base + (PAGESIZE / 16); + byte* p; + + bit_i = bit_base; + for (; bit_i < bit_top; bit_i += bit_stride) + { + if (!pool.freebits.test(bit_i)) + goto Lnotfree; + } + pool.pagetable[pn] = B_FREE; + pool.freebits.set_group(bit_base, PAGESIZE / 16); + recoveredpages++; + gc.free_mem += PAGESIZE; + continue; + + Lnotfree: + p = pool.baseAddr + pn * PAGESIZE; + for (u = 0; u < PAGESIZE; u += size) + { + bit_i = bit_base + u / 16; + if (pool.freebits.test(bit_i)) + { + assert ((p+u) >= pool.baseAddr); + assert ((p+u) < pool.topAddr); + List* list = cast(List*) (p + u); + // avoid unnecesary writes (it really saves time) + if (list.next != gc.free_list[bin]) + list.next = gc.free_list[bin]; + if (list.pool != pool) + list.pool = pool; + gc.free_list[bin] = list; + gc.free_mem += binsize[bin]; + } + } + } } } + 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); + + return freedpages + recoveredpages; +} + + +/** + * + */ +uint getAttr(Pool* pool, size_t bit_i) +in +{ + assert( pool ); +} +body +{ + uint attrs; + if (pool.finals.test(bit_i)) + attrs |= BlkAttr.FINALIZE; + if (pool.noscan.test(bit_i)) + attrs |= BlkAttr.NO_SCAN; +// if (pool.nomove.test(bit_i)) +// attrs |= BlkAttr.NO_MOVE; + return attrs; +} + - // - // - // - private size_t extendNoSync(void* p, size_t minsize, size_t maxsize) - in +/** + * + */ +void setAttr(Pool* pool, size_t bit_i, uint mask) +in +{ + assert( pool ); +} +body +{ + if (mask & BlkAttr.FINALIZE) { - assert( minsize <= maxsize ); + pool.finals.set(bit_i); } - body + if (mask & BlkAttr.NO_SCAN) { - version (SENTINEL) - { - return 0; - } - auto psize = gcx.findSize(p); // find allocated size - if (psize < PAGESIZE) - return 0; // cannot extend buckets + 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); +// } +} - 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; +/** + * + */ +void clrAttr(Pool* pool, size_t bit_i, uint mask) +in +{ + assert( pool ); +} +body +{ + if (mask & BlkAttr.FINALIZE) + 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); +} - size_t sz; - for (sz = 0; sz < maxsz; sz++) - { - auto i = pagenum + psz + sz; - if (i == pool.npages) - break; - if (pool.pagetable[i] != B_FREE) - { - if (sz < minsz) - return 0; - break; - } - } - if (sz < minsz) - return 0; - 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; - } +void disable_fork() +{ + // we have to disable both options, as eager_alloc assumes fork is enabled + opts.options.fork = false; + opts.options.eager_alloc = false; +} - /** - * - */ - size_t reserve(size_t size) - { - if (!size) - { - return 0; - } - if (!thread_needLock()) - { - return reserveNoSync(size); - } - else synchronized (gcLock) - { - return reserveNoSync(size); - } +void initialize() +{ + int dummy; + gc.stack_bottom = cast(char*)&dummy; + opts.parse(cstdlib.getenv("D_GC_OPTS")); + // If we are going to fork, make sure we have the needed OS support + if (opts.options.fork) + opts.options.fork = os.HAVE_SHARED && os.HAVE_FORK; + // Eager allocation is only possible when forking + if (!opts.options.fork) + opts.options.eager_alloc = false; + gc.lock = GCLock.classinfo; + gc.inited = 1; + setStackBottom(rt_stackBottom()); + gc.stats = Stats(gc); + if (opts.options.prealloc_npools) { + size_t pages = round_up(opts.options.prealloc_psize, PAGESIZE); + for (size_t i = 0; i < opts.options.prealloc_npools; ++i) + newPool(pages); } +} - // - // - // - private size_t reserveNoSync(size_t size) - { - assert(size != 0); - assert(gcx); +// +// +// +private void *malloc(size_t size, uint attrs, size_t* pm_bitmask) +{ + assert(size != 0); - return gcx.reserve(size); - } + gc.stats.malloc_started(size, attrs, pm_bitmask); + scope (exit) + gc.stats.malloc_finished(p); + void *p = null; + Bins bin; - /** - * - */ - void free(void *p) + if (opts.options.sentinel) + size += SENTINEL_EXTRA; + + bool has_pm = has_pointermap(attrs); + if (has_pm) + size += size_t.sizeof; + + // Compute size bin + // Cache previous binsize lookup - Dave Fladebo. + static size_t lastsize = -1; + static Bins lastbin; + if (size == lastsize) + bin = lastbin; + else { - if (!p) - { - return; - } + bin = findBin(size); + lastsize = size; + lastbin = bin; + } - if (!thread_needLock()) - { - return freeNoSync(p); - } - else synchronized (gcLock) + Pool* pool = void; + size_t bit_i = void; + size_t capacity = void; // to figure out where to store the bitmask + bool collected = false; + if (bin < B_PAGE) + { + p = gc.free_list[bin]; + if (p is null) { - return freeNoSync(p); - } - } + if (!allocPage(bin) && !gc.disabled) // try to find a new page + { + if (!thread_needLock()) + { + /* 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) + { + fullcollectshell(); + } + } + else if (!fullcollectshell()) // collect to find a new page + { + //newPool(1); + } + collected = true; + } + if (!gc.free_list[bin] && !allocPage(bin)) + { + newPool(1); // allocate new pool to find a new page + // TODO: hint allocPage() to use the pool we just created + int result = allocPage(bin); + if (!result) + onOutOfMemoryError(); + } + p = gc.free_list[bin]; + } + capacity = binsize[bin]; + + // Return next item from free list + List* list = cast(List*) p; + assert ((cast(byte*)list) >= list.pool.baseAddr); + assert ((cast(byte*)list) < list.pool.topAddr); + gc.free_list[bin] = list.next; + pool = list.pool; + bit_i = (p - pool.baseAddr) / 16; + assert (pool.freebits.test(bit_i)); + pool.freebits.clear(bit_i); + if (!(attrs & BlkAttr.NO_SCAN)) + memset(p + size, 0, capacity - size); + if (opts.options.mem_stomp) + memset(p, 0xF0, size); + } + else + { + size_t pn; + size_t npages = round_up(size, PAGESIZE); + p = bigAlloc(npages, pool, &pn, &collected); + if (!p) + onOutOfMemoryError(); + assert (pool !is null); + capacity = npages * PAGESIZE; + bit_i = pn * (PAGESIZE / 16); + pool.freebits.clear(bit_i); + 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); - // - // - // - private void freeNoSync(void *p) - { - assert (p); + } - Pool* pool; - size_t pagenum; - Bins bin; - size_t biti; + // 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; + } - // 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); + if (opts.options.sentinel) { + size -= SENTINEL_EXTRA; + p = sentinel_add(p); + sentinel_init(p, size); + } - 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); + if (attrs) { + setAttr(pool, bit_i, attrs); + assert (bin >= B_PAGE || !pool.freebits.test(bit_i)); + } + + gc.free_mem -= capacity; + if (collected) { + // If there is not enough free memory, allocate a new pool big enough + // to have at least the min_free% of the total heap free. If there is + // too much free memory, try to free some empty pools. + double percent_free = gc.free_mem * 100.0 / gc.total_mem; + if (percent_free < opts.options.min_free) { + auto pool_size = gc.total_mem * 1.0 / opts.options.min_free + - gc.free_mem; + newPool(round_up(cast(size_t)pool_size, PAGESIZE)); } else - { - // Add to free list - List *list = cast(List*)p; + minimize(false); + } - debug (MEMSTOMP) cstring.memset(p, 0xF2, binsize[bin]); + return p; +} - list.next = gcx.bucket[bin]; - gcx.bucket[bin] = list; - } - } +// +// +// +private void *calloc(size_t size, uint attrs, size_t* pm_bitmask) +{ + assert(size != 0); - /** - * Determine the base address of the block containing p. If p is not a gc - * allocated pointer, return null. - */ - void* addrOf(void *p) - { - if (!p) - { - return null; - } - - if (!thread_needLock()) - { - return addrOfNoSync(p); - } - else synchronized (gcLock) - { - return addrOfNoSync(p); - } - } - - - // - // - // - void* addrOfNoSync(void *p) - { - if (!p) - { - return null; - } - - return gcx.findBase(p); - } - + void *p = malloc(size, attrs, pm_bitmask); + memset(p, 0, size); + return p; +} - /** - * 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) - { - if (!p) - { - return 0; - } - if (!thread_needLock()) - { - return sizeOfNoSync(p); - } - else synchronized (gcLock) - { - return sizeOfNoSync(p); - } +// +// +// +private void *realloc(void *p, size_t size, uint attrs, + size_t* pm_bitmask) +{ + if (!size) { + if (p) + free(p); + return null; } + if (p is null) + return malloc(size, attrs, pm_bitmask); - // - // - // - private size_t sizeOfNoSync(void *p) - { - assert (p); - - 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; - - 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; - else - { - gcx.p_cache = p; - gcx.size_cache = size; - } + Pool* pool = findPool(p); + if (pool is null) + return null; - return size; - } + // 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); - - /** - * Determine the base address of the block containing p. If p is not a gc - * allocated pointer, return null. - */ - BlkInfo query(void *p) - { - if (!p) - { - BlkInfo i; - return i; - } - - if (!thread_needLock()) - { - return queryNoSync(p); + 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; } - else synchronized (gcLock) - { - return queryNoSync(p); - } - } - - - // - // - // - BlkInfo queryNoSync(void *p) - { - assert(p); - - return gcx.getInfo(p); } - - /** - * Verify that pointer p: - * 1) belongs to this memory pool - * 2) points to the start of an allocated piece of memory - * 3) is not on a free list - */ - void check(void *p) - { - if (!p) - { - return; - } - - if (!thread_needLock()) - { - checkNoSync(p); - } - else synchronized (gcLock) - { - checkNoSync(p); + if (opts.options.sentinel) { + sentinel_Invariant(p); + size_t sentinel_stored_size = *sentinel_size(p); + if (sentinel_stored_size != size) { + void* p2 = malloc(size, attrs, pm_bitmask); + if (sentinel_stored_size < size) + size = sentinel_stored_size; + cstring.memcpy(p2, p, size); + p = p2; } + return p; } + size += pm_bitmask_size; + if (blk_size >= PAGESIZE && size >= PAGESIZE) { + auto psz = blk_size / PAGESIZE; + auto newsz = round_up(size, PAGESIZE); + if (newsz == psz) + return p; - // - // - // - private void checkNoSync(void *p) - { - 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; + auto pagenum = (p - pool.baseAddr) / PAGESIZE; - for (list = gcx.bucket[bin]; list; list = list.next) - { - assert(cast(void*)list != p); + if (newsz < psz) { + // 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); + auto new_blk_size = (PAGESIZE * newsz); + gc.free_mem += blk_size - new_blk_size; + // update the size cache, assuming that is very likely the + // size of this block will be queried in the near future + pool.update_cache(p, new_blk_size); + if (has_pm) { + auto end_of_blk = cast(size_t**)(blk_base_addr + + new_blk_size - pm_bitmask_size); + *end_of_blk = pm_bitmask; + } + return p; + } + + if (pagenum + newsz <= pool.npages) { + // Attempt to expand in place + for (size_t i = pagenum + psz; 1;) { + if (i == pagenum + newsz) { + if (opts.options.mem_stomp) + memset(p + blk_size - pm_bitmask_size, 0xF0, + size - blk_size - pm_bitmask_size); + memset(pool.pagetable + pagenum + psz, B_PAGEPLUS, + newsz - psz); + auto new_blk_size = (PAGESIZE * newsz); + gc.free_mem -= new_blk_size - blk_size; + // update the size cache, assuming that is very + // likely the size of this block will be queried in + // the near future + pool.update_cache(p, new_blk_size); + if (has_pm) { + auto end_of_blk = cast(size_t**)( + blk_base_addr + new_blk_size - pm_bitmask_size); + *end_of_blk = pm_bitmask; } + return p; } + if (i == pool.npages) + break; + if (pool.pagetable[i] != B_FREE) + break; + i++; } } } - - // - // - // - 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); - } + // 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; } - - /** - * do full garbage collection - */ - void fullCollect() - { - - if (!thread_needLock()) - { - gcx.fullcollectshell(); - } - else synchronized (gcLock) - { - gcx.fullcollectshell(); - } - - version (none) - { - GCStats stats; - getStats(stats); - } - - } + return p; +} - /** - * 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--; - } - } +/** + * 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; + Pool* pool = findPool(p); + if (pool is null) + return 0; - /** - * minimize free space usage - */ - void minimize() - { - if (!thread_needLock()) - { - gcx.minimize(); - } - else synchronized (gcLock) - { - gcx.minimize(); - } - } + // 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; - /** - * 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); - } + minsize += size_t.sizeof; + maxsize += size_t.sizeof; } + if (blk_size < PAGESIZE) + return 0; // cannot extend buckets - // - // - // - 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 *********************/ + auto psz = blk_size / PAGESIZE; + auto minsz = round_up(minsize, PAGESIZE); + auto maxsz = round_up(maxsize, PAGESIZE); - // call locked if necessary - private T locked(T)(in T delegate() code) - { - if (thread_needLock) - synchronized(gcLock) return code(); - else - return code(); - } + auto pagenum = (p - pool.baseAddr) / PAGESIZE; - private struct WeakPointer + size_t sz; + for (sz = 0; sz < maxsz; sz++) { - Object reference; - - void ondestroy(Object r) + auto i = pagenum + psz + sz; + if (i == pool.npages) + break; + if (pool.pagetable[i] != B_FREE) { - 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; }); + if (sz < minsz) + return 0; + break; } } + if (sz < minsz) + return 0; - /** - * 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; - } + size_t new_size = (psz + sz) * PAGESIZE; - /** - * 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); - } - } + 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; + gc.free_mem -= new_size - blk_size; + // update the size cache, assuming that is very likely the size of this + // block will be queried in the near future + pool.update_cache(p, new_size); - /** - * 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; - }); - } + if (has_pm) { + new_size -= size_t.sizeof; + auto end_of_blk = cast(size_t**)(blk_base_addr + new_size); + *end_of_blk = pm_bitmask; } + return new_size; } -/* ============================ Gcx =============================== */ - -enum +// +// +// +private void free(void *p) { - PAGESIZE = 4096, - POOLSIZE = (4096*256), + 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; + pool.freebits.set_group(bit_i, PAGESIZE / 16); + while (++n < pool.npages && pool.pagetable[n] == B_PAGEPLUS) + npages++; + size_t size = npages * PAGESIZE; + if (opts.options.mem_stomp) + memset(p, 0xF2, size); + pool.freePages(pagenum, npages); + gc.free_mem += size; + // just in case we were caching this pointer + pool.clear_cache(p); + } + else + { + // Add to free list + List* list = cast(List*) p; + + if (opts.options.mem_stomp) + memset(p, 0xF2, binsize[bin]); + + list.next = gc.free_list[bin]; + list.pool = pool; + gc.free_list[bin] = list; + pool.freebits.set(bit_i); + gc.free_mem += binsize[bin]; + } + double percent_free = gc.free_mem * 100.0 / gc.total_mem; + if (percent_free > opts.options.min_free) + minimize(false); } -enum +/** + * 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) { - 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; - //printf("gcx = %p, self = %x\n", this, self); - inited = 1; - } - - - 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) - { - Pool* pool; - size_t n; - size_t pn; - byte* p; - byte* ptop; - - for (n = 0; n < npools; n++) - { - pool = pooltable[n]; - pn = pool.allocPages(1); - if (pn != OPFAIL) - goto L1; - } - return 0; // failed - - L1: - pool.pagetable[pn] = cast(ubyte)bin; - - // Convert page to free list - size_t size = binsize[bin]; - List **b = &bucket[bin]; - - p = pool.baseAddr + pn * PAGESIZE; - ptop = p + PAGESIZE; - for (; p < ptop; p += size) - { - (cast(List *)p).next = *b; - *b = cast(List *)p; - } - return 1; - } - - - /** - * Search a range of memory values and mark any pointers into the GC pool. - */ - void mark(void *pbot, void *ptop) - { - 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 *pool; - byte *p = cast(byte *)(*p1); - - if (p >= minAddr && p < maxAddr) - { - if ((cast(size_t)p & ~(PAGESIZE-1)) == pcache) - continue; - - pool = findPool(p); - if (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]; - - // Adjust bit to be at start of allocated memory block - if (bin <= B_PAGE) - biti = (offset & notbinsize[bin]) >> 4; - else if (bin == B_PAGEPLUS) - { - do - { - --pn; - } - while (cast(Bins)pool.pagetable[pn] == B_PAGEPLUS); - biti = pn * (PAGESIZE / 16); - } - else - { - // Don't mark bits in B_FREE pages - continue; - } - - if (bin >= B_PAGE) // Cache B_PAGE and B_PAGEPLUS lookups - pcache = cast(size_t)p & ~(PAGESIZE-1); - - if (!pool.mark.test(biti)) - { - pool.mark.set(biti); - if (!pool.noscan.test(biti)) - { - pool.scan.set(biti); - changes = 1; - } - } - } - } - } - anychanges |= changes; - } - - - /** - * Return number of full pages free'd. - */ - size_t fullcollectshell() - { - // 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) - { - gcc.builtins.__builtin_unwind_init(); - sp = & sp; - } - else version(LDC) - { - version(X86) - { - uint eax,ecx,edx,ebx,ebp,esi,edi; - asm - { - mov eax[EBP], EAX ; - mov ecx[EBP], ECX ; - mov edx[EBP], EDX ; - mov ebx[EBP], EBX ; - mov ebp[EBP], EBP ; - mov esi[EBP], ESI ; - mov edi[EBP], EDI ; - mov sp[EBP], ESP ; - } - } - else version (X86_64) - { - ulong rax,rbx,rcx,rdx,rbp,rsi,rdi,r8,r9,r10,r11,r12,r13,r14,r15; - asm - { - movq rax[RBP], RAX ; - movq rbx[RBP], RBX ; - movq rcx[RBP], RCX ; - movq rdx[RBP], RDX ; - movq rbp[RBP], RBP ; - movq rsi[RBP], RSI ; - movq rdi[RBP], RDI ; - movq r8 [RBP], R8 ; - movq r9 [RBP], R9 ; - movq r10[RBP], R10 ; - movq r11[RBP], R11 ; - movq r12[RBP], R12 ; - movq r13[RBP], R13 ; - movq r14[RBP], R14 ; - movq r15[RBP], R15 ; - movq sp[RBP], RSP ; - } - } - else - { - static assert( false, "Architecture not supported." ); - } - } - 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; - } - - - /** - * - */ - size_t fullcollect(void *stackTop) - { - size_t n; - Pool* pool; - - debug(COLLECT_PRINTF) printf("Gcx.fullcollect()\n"); - - thread_suspendAll(); - - p_cache = null; - size_cache = 0; - - 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); - } - } - - for (n = 0; n < npools; n++) - { - pool = pooltable[n]; - pool.mark.copy(&pool.freebits); - } - - rt_scanStaticData( &mark ); - - if (!noStack) - { - // Scan stacks and registers for each paused thread - thread_scanAll( &mark, stackTop ); - } - - // Scan roots[] - debug(COLLECT_PRINTF) printf("scan roots[]\n"); - mark(roots, roots + nroots); - - // 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--; - - debug(COLLECT_PRINTF) printf("\tscan heap\n"); - while (anychanges) - { - anychanges = 0; - for (n = 0; n < npools; n++) - { - uint *bbase; - uint *b; - uint *btop; - - pool = pooltable[n]; - - 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; - - bitm = *b; - if (!bitm) - { - b++; - continue; - } - *b = 0; - - o = pool.baseAddr + (b - bbase) * 32 * 16; - if (!(bitm & 0xFFFF)) - { - bitm >>= 16; - o += 16 * 16; - } - for (; bitm; o += 16, bitm >>= 1) - { - if (!(bitm & 1)) - continue; - - 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); - } - } - } - } - } - - thread_resumeAll(); + assert (p); - // 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]; + if (opts.options.sentinel) + p = sentinel_sub(p); - 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; + Pool* pool = findPool(p); + if (pool is null) + return 0; - 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) - { - 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); + auto biti = cast(size_t)(p - pool.baseAddr) / 16; + uint attrs = getAttr(pool, biti); - List *list = cast(List *)p; + size_t size = pool.findSize(p); + size_t pm_bitmask_size = 0; + if (has_pointermap(attrs)) + pm_bitmask_size = size_t.sizeof; - debug (MEMSTOMP) cstring.memset(p, 0xF3, size); - } - pool.pagetable[pn] = B_FREE; - freed += PAGESIZE; - continue; - } + 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; } - for (; p < ptop; p += size, biti += bitstride) - { - if (!pool.mark.test(biti)) - { - sentinel_Invariant(sentinel_add(p)); + else { + if (p == gc.p_cache) + return gc.size_cache; - 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); + // 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; - List *list = cast(List *)p; + gc.p_cache = p; + gc.size_cache = size - pm_bitmask_size; - debug (MEMSTOMP) cstring.memset(p, 0xF3, size); + return gc.size_cache; + } +} - 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); - 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); - } - } - } - } - } - } +/** + * 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); + + if (opts.options.sentinel) + sentinel_Invariant(p); + debug (PTRCHECK) + { + Pool* pool; + size_t pagenum; + Bins bin; + size_t size; - // Zero buckets - bucket[] = null; + 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); - // Free complete pages, rebuild free list - debug(COLLECT_PRINTF) printf("\tfree complete pages\n"); - size_t recoveredpages = 0; - for (n = 0; n < npools; n++) + debug (PTRCHECK2) { - pool = pooltable[n]; - for (size_t pn = 0; pn < pool.npages; pn++) + if (bin < B_PAGE) { - Bins bin = cast(Bins)pool.pagetable[pn]; - size_t biti; - size_t u; - - if (bin < B_PAGE) + // Check that p is not on a free list + for (List* list = gc.free_list[bin]; list; list = list.next) { - 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; - } - pool.pagetable[pn] = B_FREE; - recoveredpages++; - continue; - - Lnotfree: - p = pool.baseAddr + pn * PAGESIZE; - for (u = 0; u < PAGESIZE; u += size) - { - biti = bitbase + u / 16; - if (pool.freebits.test(biti)) - { - List *list = cast(List *)(p + u); - if (list.next != bucket[bin]) // avoid unnecessary writes - list.next = bucket[bin]; - bucket[bin] = list; - } - } + assert(cast(void*)list != p); } } } - - 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); - - return freedpages + recoveredpages; } +} - /** - * - */ - uint getBits(Pool* pool, size_t biti) - in +// +// +// +private void setStackBottom(void *p) +{ + version (STACKGROWSDOWN) { - assert( pool ); + //p = (void *)((uint *)p + 4); + if (p > gc.stack_bottom) + { + gc.stack_bottom = p; + } } - body + else { - 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; + //p = (void *)((uint *)p - 4); + if (p < gc.stack_bottom) + { + gc.stack_bottom = cast(char*)p; + } } +} - /** - * - */ - void setBits(Pool* pool, size_t biti, uint mask) - in - { - assert( pool ); - } - body +/** + * 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++) { - if (mask & BlkAttr.FINALIZE) - { - if (!pool.finals.nbits) - pool.finals.alloc(pool.mark.nbits); - pool.finals.set(biti); - } - if (mask & BlkAttr.NO_SCAN) + Pool* pool = gc.pools[n]; + psize += pool.npages * PAGESIZE; + for (size_t j = 0; j < pool.npages; j++) { - pool.noscan.set(biti); + Bins bin = cast(Bins)pool.pagetable[j]; + if (bin == B_FREE) + stats.freeblocks++; + else if (bin == B_PAGE) + stats.pageblocks++; + else if (bin < B_PAGE) + bsize += PAGESIZE; } -// if (mask & BlkAttr.NO_MOVE) -// { -// if (!pool.nomove.nbits) -// pool.nomove.alloc(pool.mark.nbits); -// pool.nomove.set(biti); -// } } + for (n = 0; n < B_PAGE; n++) + { + for (List* list = gc.free_list[n]; list; list = list.next) + flsize += binsize[n]; + } - /** - * - */ - void clrBits(Pool* pool, size_t biti, uint mask) - in + 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( pool ); + 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; } - body + return null; +} + +/** + * Destroy a weak pointer returned by weakpointerCreate(). + * If null is passed, nothing happens. + */ +void weakpointerDestroy( void* p ) +{ + if (p) { - 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); + 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; + })(); + } } @@ -2499,12 +1996,29 @@ struct Pool size_t npages; ubyte* pagetable; + /// Cache for findSize() + size_t cached_size; + void* cached_ptr; + + void clear_cache(void* ptr = null) + { + if (ptr is null || ptr is this.cached_ptr) { + this.cached_ptr = null; + this.cached_size = 0; + } + } + + void update_cache(void* ptr, size_t size) + { + this.cached_ptr = ptr; + this.cached_size = size; + } void initialize(size_t npages) { size_t poolsize = npages * PAGESIZE; assert(poolsize >= POOLSIZE); - baseAddr = cast(byte *) alloc.os_mem_map(poolsize); + baseAddr = cast(byte *) os.alloc(poolsize); // Some of the code depends on page alignment of memory pools assert((cast(size_t)baseAddr & (PAGESIZE - 1)) == 0); @@ -2514,18 +2028,32 @@ struct Pool npages = 0; poolsize = 0; } - //assert(baseAddr); topAddr = baseAddr + poolsize; - mark.alloc(cast(size_t)poolsize / 16); - scan.alloc(cast(size_t)poolsize / 16); - freebits.alloc(cast(size_t)poolsize / 16); - noscan.alloc(cast(size_t)poolsize / 16); + size_t nbits = cast(size_t)poolsize / 16; + + // if the GC will run in parallel in a fork()ed process, we need to + // share the mark bits + os.Vis vis = os.Vis.PRIV; + if (opts.options.fork) + vis = os.Vis.SHARED; + mark.alloc(nbits, vis); // shared between mark and sweep + freebits.alloc(nbits); // not used by the mark phase + scan.alloc(nbits); // only used in the mark phase + finals.alloc(nbits); // not used by the mark phase + noscan.alloc(nbits); // mark phase *MUST* have a snapshot + + // all is free when we start + freebits.set_all(); + + // avoid accidental sweeping of new pools while using eager allocation + if (collect_in_progress()) + mark.set_all(); pagetable = cast(ubyte*) cstdlib.malloc(npages); if (!pagetable) onOutOfMemoryError(); - cstring.memset(pagetable, B_FREE, npages); + memset(pagetable, B_FREE, npages); this.npages = npages; } @@ -2539,7 +2067,7 @@ struct Pool if (npages) { - result = alloc.os_mem_unmap(baseAddr, npages * PAGESIZE); + result = os.dealloc(baseAddr, npages * PAGESIZE); assert(result); npages = 0; } @@ -2551,15 +2079,21 @@ struct Pool if (pagetable) cstdlib.free(pagetable); - mark.Dtor(); - scan.Dtor(); + os.Vis vis = os.Vis.PRIV; + if (opts.options.fork) + vis = os.Vis.SHARED; + mark.Dtor(vis); freebits.Dtor(); + scan.Dtor(); finals.Dtor(); noscan.Dtor(); } - void Invariant() { } + bool Invariant() + { + return true; + } invariant @@ -2614,19 +2148,65 @@ struct Pool */ void freePages(size_t pagenum, size_t npages) { - cstring.memset(&pagetable[pagenum], B_FREE, npages); + memset(&pagetable[pagenum], B_FREE, npages); } /** - * Used for sorting pooltable[] + * 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]; + if (this.cached_ptr == p) + return this.cached_size; + size_t i = pagenum + 1; + for (; i < this.npages; i++) + if (this.pagetable[i] != B_PAGEPLUS) + break; + this.cached_ptr = p; + this.cached_size = (i - pagenum) * PAGESIZE; + return this.cached_size; + } + + + /** + * 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); } } @@ -2634,69 +2214,358 @@ struct Pool /* ============================ 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) +{ + if (*sentinel_pre(p) != SENTINEL_PRE || + *sentinel_post(p) != SENTINEL_POST) + cstdlib.abort(); +} - 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); }