X-Git-Url: https://git.llucax.com/software/dgc/cdgc.git/blobdiff_plain/f9b8f3cb780edcdceda2027e96f69a2244c9cc29..53daba87c2208fcced6c7704dd31932a8a56467b:/rt/gc/cdgc/gc.d diff --git a/rt/gc/cdgc/gc.d b/rt/gc/cdgc/gc.d index 2282ada..59d9f55 100644 --- a/rt/gc/cdgc/gc.d +++ b/rt/gc/cdgc/gc.d @@ -45,7 +45,7 @@ version = STACKGROWSDOWN; // growing the stack means subtracting from the import rt.gc.cdgc.bits: GCBits; import rt.gc.cdgc.stats: GCStats, Stats; import dynarray = rt.gc.cdgc.dynarray; -import alloc = rt.gc.cdgc.alloc; +import os = rt.gc.cdgc.os; import opts = rt.gc.cdgc.opts; import cstdlib = tango.stdc.stdlib; @@ -155,7 +155,8 @@ alias ubyte Bins; struct List { - List *next; + List* next; + Pool* pool; } @@ -210,7 +211,7 @@ struct GC dynarray.DynArray!(void*) roots; dynarray.DynArray!(Range) ranges; - dynarray.DynArray!(Pool) pools; + dynarray.DynArray!(Pool*) pools; Stats stats; } @@ -236,7 +237,7 @@ bool Invariant() if (i == 0) assert(gc.min_addr == pool.baseAddr); if (i + 1 < gc.pools.length) - assert(*pool < gc.pools[i + 1]); + assert(*pool < *gc.pools[i + 1]); else if (i + 1 == gc.pools.length) assert(gc.max_addr == pool.topAddr); } @@ -250,10 +251,14 @@ bool Invariant() 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) - { + for (size_t i = 0; i < B_PAGE; i++) { + for (List *list = gc.free_list[i]; list; list = list.next) { + assert (list.pool !is null); + auto p = cast(byte*) list; + assert (p >= list.pool.baseAddr); + assert (p < list.pool.topAddr); } + } } return true; } @@ -264,105 +269,32 @@ bool Invariant() * Return null if not in a Pool. * Assume pools is sorted. */ -Pool *findPool(void *p) -{ - if (p >= gc.min_addr && p < gc.max_addr) - { - if (gc.pools.length == 1) - { - return gc.pools[0]; - } - - for (size_t i = 0; i < gc.pools.length; i++) - { - Pool* pool = gc.pools[i]; - if (p < pool.topAddr) - { - if (pool.baseAddr <= p) - return pool; - break; - } - } - } - return null; -} - - -/** - * Find base address of block containing pointer p. - * Returns null if not a gc'd pointer - */ -void* findBase(void *p) +Pool* findPool(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))); - } + 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 - { - // we are in a B_FREE page - return null; - } + return pool; } + // Not found 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; -} - - /** * Determine the base address of the block containing p. If p is not a gc * allocated pointer, return null. @@ -370,65 +302,28 @@ size_t findSize(void *p) BlkInfo getInfo(void* p) { assert (p !is null); - - Pool* pool; + Pool* pool = findPool(p); + if (pool is null) + return BlkInfo.init; 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; + info.base = pool.findBase(p); + if (info.base is null) + return BlkInfo.init; + info.size = pool.findSize(info.base); + info.attr = getAttr(pool, cast(size_t)(info.base - pool.baseAddr) / 16u); + 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; } - - //////////////////////////////////////////////////////////////////// - // getAttr - //////////////////////////////////////////////////////////////////// - - info.attr = getAttr(pool, cast(size_t)(offset / 16)); - if (!(info.attr & BlkAttr.NO_SCAN)) - info.size -= (size_t*).sizeof; // bitmask + } + 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; } @@ -437,7 +332,7 @@ BlkInfo getInfo(void* p) /** * Compute bin for size. */ -static Bins findBin(size_t size) +Bins findBin(size_t size) { Bins bin; if (size <= 256) @@ -505,7 +400,7 @@ void minimize() { size_t n; size_t pn; - Pool* pool; + Pool* pool; for (n = 0; n < gc.pools.length; n++) { @@ -518,6 +413,7 @@ void minimize() if (pn < pool.npages) continue; pool.Dtor(); + cstdlib.free(pool); gc.pools.remove_at(n); n--; } @@ -530,9 +426,8 @@ void minimize() * Allocate a chunk of memory that is larger than a page. * Return null if out of memory. */ -void *bigAlloc(size_t size) +void* bigAlloc(size_t size, out Pool* pool) { - Pool* pool; size_t npages; size_t n; size_t pn; @@ -644,20 +539,24 @@ Pool *newPool(size_t npages) npages = n; } - Pool p; - p.initialize(npages); - if (!p.baseAddr) + auto pool = cast(Pool*) cstdlib.calloc(1, Pool.sizeof); + if (pool is null) + return null; + pool.initialize(npages); + if (!pool.baseAddr) { - p.Dtor(); + pool.Dtor(); return null; } - Pool* pool = gc.pools.insert_sorted(p); - if (pool) - { - gc.min_addr = gc.pools[0].baseAddr; - gc.max_addr = gc.pools[gc.pools.length - 1].topAddr; + 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; return pool; } @@ -689,33 +588,26 @@ int allocPage(Bins bin) // Convert page to free list size_t size = binsize[bin]; - List **b = &gc.free_list[bin]; + auto list_head = &gc.free_list[bin]; p = pool.baseAddr + pn * PAGESIZE; ptop = p + PAGESIZE; for (; p < ptop; p += size) { - (cast(List *)p).next = *b; - *b = cast(List *)p; + List* l = cast(List *) p; + l.next = *list_head; + l.pool = pool; + *list_head = l; } return 1; } /** - * Marks a range of memory using the conservative bit mask. Used for - * the stack, for the data segment, and additional memory ranges. - */ -void mark_conservative(void* pbot, void* ptop) -{ - mark(pbot, ptop, PointerMap.init.bits.ptr); -} - - -/** - * Search a range of memory values and mark any pointers into the GC pool. + * Search a range of memory values and mark any pointers into the GC pool using + * type information (bitmask of pointer locations). */ -void mark(void *pbot, void *ptop, size_t* pm_bitmask) +void mark_range(void *pbot, void *ptop, size_t* pm_bitmask) { // TODO: make our own assert because assert uses the GC assert (pbot <= ptop); @@ -725,16 +617,18 @@ void mark(void *pbot, void *ptop, size_t* pm_bitmask) void **p1 = cast(void **)pbot; void **p2 = cast(void **)ptop; size_t pcache = 0; - uint changes = 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 (!(pm_bits[n / BITS_PER_WORD] & (1 << (n % BITS_PER_WORD)))) + if (has_type_info && + !(pm_bits[n / BITS_PER_WORD] & (1 << (n % BITS_PER_WORD)))) continue; void* p = *(p1 + n); @@ -749,13 +643,17 @@ void mark(void *pbot, void *ptop, size_t* pm_bitmask) if (pool) { size_t offset = cast(size_t)(p - pool.baseAddr); - size_t bit_i; + 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]) >> 4; + bit_i = (offset & notbinsize[bin]) / 16; else if (bin == B_PAGEPLUS) { do @@ -765,14 +663,8 @@ void mark(void *pbot, void *ptop, size_t* pm_bitmask) while (cast(Bins)pool.pagetable[pn] == B_PAGEPLUS); bit_i = pn * (PAGESIZE / 16); } - else - { - // Don't mark bits in B_FREE pages + 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(bit_i)) { @@ -780,7 +672,7 @@ void mark(void *pbot, void *ptop, size_t* pm_bitmask) if (!pool.noscan.test(bit_i)) { pool.scan.set(bit_i); - changes = 1; + changes = true; } } } @@ -886,79 +778,119 @@ size_t fullcollectshell() */ size_t fullcollect(void *stackTop) { - size_t n; - Pool* pool; - debug(COLLECT_PRINTF) printf("Gcx.fullcollect()\n"); + // 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(); - gc.p_cache = null; - gc.size_cache = 0; + if (opts.options.fork) { + 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, fallback to stop-the-world + opts.options.fork = false; + 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(); + int status = void; + os.pid_t wait_pid = os.waitpid(child_pid, &status, 0); + assert (wait_pid == child_pid); + return sweep(); + } + + } + + // if we reach here, we are using the standard stop-the-world collection + mark(stackTop); + thread_resumeAll(); + gc.stats.world_started(); + + return sweep(); +} + + +/** + * + */ +void mark(void *stackTop) +{ + debug(COLLECT_PRINTF) printf("\tmark()\n"); gc.any_changes = false; - for (n = 0; n < gc.pools.length; n++) + for (size_t n = 0; n < gc.pools.length; n++) { - pool = gc.pools[n]; + Pool* pool = gc.pools[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 (size_t n = 0; n < B_PAGE; n++) { for (List *list = gc.free_list[n]; list; list = list.next) { - pool = findPool(list); - assert(pool); - pool.freebits.set(cast(size_t)(cast(byte*)list - pool.baseAddr) / 16); + Pool* pool = list.pool; + auto ptr = cast(byte*) list; + assert (pool); + assert (pool.baseAddr <= ptr); + assert (ptr < pool.topAddr); + size_t bit_i = cast(size_t)(ptr - pool.baseAddr) / 16; + pool.freebits.set(bit_i); } } - for (n = 0; n < gc.pools.length; n++) + for (size_t n = 0; n < gc.pools.length; n++) { - pool = gc.pools[n]; + Pool* pool = gc.pools[n]; pool.mark.copy(&pool.freebits); } - void mark_conservative_dg(void* pbot, void* ptop) + /// Marks a range of memory in conservative mode. + void mark_conservative_range(void* pbot, void* ptop) { - mark_conservative(pbot, ptop); + mark_range(pbot, ptop, PointerMap.init.bits.ptr); } - rt_scanStaticData(&mark_conservative_dg); + rt_scanStaticData(&mark_conservative_range); if (!gc.no_stack) { // Scan stacks and registers for each paused thread - thread_scanAll(&mark_conservative_dg, stackTop); + thread_scanAll(&mark_conservative_range, stackTop); } // Scan roots debug(COLLECT_PRINTF) printf("scan roots[]\n"); - mark_conservative(gc.roots.ptr, gc.roots.ptr + gc.roots.length); + mark_conservative_range(gc.roots.ptr, gc.roots.ptr + gc.roots.length); // Scan ranges debug(COLLECT_PRINTF) printf("scan ranges[]\n"); - for (n = 0; n < gc.ranges.length; n++) + for (size_t n = 0; n < gc.ranges.length; n++) { debug(COLLECT_PRINTF) printf("\t%x .. %x\n", gc.ranges[n].pbot, gc.ranges[n].ptop); - mark_conservative(gc.ranges[n].pbot, gc.ranges[n].ptop); + 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 (n = 0; n < gc.pools.length; n++) + for (size_t n = 0; n < gc.pools.length; n++) { uint *bbase; uint *b; uint *btop; - pool = gc.pools[n]; + Pool* pool = gc.pools[n]; bbase = pool.scan.base(); btop = bbase + pool.scan.nwords; @@ -993,12 +925,12 @@ size_t fullcollect(void *stackTop) bin = cast(Bins)pool.pagetable[pn]; if (bin < B_PAGE) { if (opts.options.conservative) - mark_conservative(o, o + binsize[bin]); + 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(o, end_of_blk, pm_bitmask); + mark_range(o, end_of_blk, pm_bitmask); } } else if (bin == B_PAGE || bin == B_PAGEPLUS) @@ -1015,29 +947,36 @@ size_t fullcollect(void *stackTop) size_t blk_size = u * PAGESIZE; if (opts.options.conservative) - mark_conservative(o, o + blk_size); + 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(o, end_of_blk, pm_bitmask); + mark_range(o, end_of_blk, pm_bitmask); } } } } } } +} - thread_resumeAll(); - gc.stats.world_started(); +/** + * + */ +size_t sweep() +{ // Free up everything not marked - debug(COLLECT_PRINTF) printf("\tfree'ing\n"); + debug(COLLECT_PRINTF) printf("\tsweep\n"); + gc.p_cache = null; + gc.size_cache = 0; size_t freedpages = 0; size_t freed = 0; - for (n = 0; n < gc.pools.length; n++) + for (size_t n = 0; n < gc.pools.length; n++) { - pool = gc.pools[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)) @@ -1063,14 +1002,12 @@ version(none) // BUG: doesn't work because freebits() must also be cleared { if (pool.finals.nbits && pool.finals.testClear(bit_i)) { if (opts.options.sentinel) - rt_finalize(cast(List *)sentinel_add(p), false/*gc.no_stack > 0*/); + rt_finalize(sentinel_add(p), false/*gc.no_stack > 0*/); else - rt_finalize(cast(List *)p, false/*gc.no_stack > 0*/); + rt_finalize(p, false/*gc.no_stack > 0*/); } clrAttr(pool, bit_i, BlkAttr.ALL_BITS); - List *list = cast(List *)p; - if (opts.options.mem_stomp) memset(p, 0xF3, size); } @@ -1089,14 +1026,12 @@ version(none) // BUG: doesn't work because freebits() must also be cleared pool.freebits.set(bit_i); if (pool.finals.nbits && pool.finals.testClear(bit_i)) { if (opts.options.sentinel) - rt_finalize(cast(List *)sentinel_add(p), false/*gc.no_stack > 0*/); + rt_finalize(sentinel_add(p), false/*gc.no_stack > 0*/); else - rt_finalize(cast(List *)p, false/*gc.no_stack > 0*/); + rt_finalize(p, false/*gc.no_stack > 0*/); } clrAttr(pool, bit_i, BlkAttr.ALL_BITS); - List *list = cast(List *)p; - if (opts.options.mem_stomp) memset(p, 0xF3, size); @@ -1148,9 +1083,9 @@ version(none) // BUG: doesn't work because freebits() must also be cleared // Free complete pages, rebuild free list debug(COLLECT_PRINTF) printf("\tfree complete pages\n"); size_t recoveredpages = 0; - for (n = 0; n < gc.pools.length; n++) + for (size_t n = 0; n < gc.pools.length; n++) { - pool = gc.pools[n]; + Pool* pool = gc.pools[n]; for (size_t pn = 0; pn < pool.npages; pn++) { Bins bin = cast(Bins)pool.pagetable[pn]; @@ -1182,10 +1117,14 @@ version(none) // BUG: doesn't work because freebits() must also be cleared bit_i = bit_base + u / 16; if (pool.freebits.test(bit_i)) { - List *list = cast(List *)(p + u); - // avoid unnecessary writes + 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; } } @@ -1278,6 +1217,9 @@ 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; gc.lock = GCLock.classinfo; gc.inited = 1; setStackBottom(rt_stackBottom()); @@ -1319,7 +1261,8 @@ private void *malloc(size_t size, uint attrs, size_t* pm_bitmask) lastbin = bin; } - size_t capacity; // to figure out where to store the bitmask + Pool* pool = void; + size_t capacity = void; // to figure out where to store the bitmask if (bin < B_PAGE) { p = gc.free_list[bin]; @@ -1346,6 +1289,7 @@ private void *malloc(size_t size, uint attrs, size_t* pm_bitmask) 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(); @@ -1355,7 +1299,11 @@ private void *malloc(size_t size, uint attrs, size_t* pm_bitmask) capacity = binsize[bin]; // Return next item from free list - gc.free_list[bin] = (cast(List*)p).next; + 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; if (!(attrs & BlkAttr.NO_SCAN)) memset(p + size, 0, capacity - size); if (opts.options.mem_stomp) @@ -1363,9 +1311,10 @@ private void *malloc(size_t size, uint attrs, size_t* pm_bitmask) } else { - p = bigAlloc(size); + p = bigAlloc(size, pool); if (!p) onOutOfMemoryError(); + assert (pool !is null); // Round the size up to the number of pages needed to store it size_t npages = (size + PAGESIZE - 1) / PAGESIZE; capacity = npages * PAGESIZE; @@ -1386,12 +1335,8 @@ private void *malloc(size_t size, uint attrs, size_t* pm_bitmask) } if (attrs) - { - Pool *pool = findPool(p); - assert(pool); - setAttr(pool, cast(size_t)(p - pool.baseAddr) / 16, attrs); - } + return p; } @@ -1442,8 +1387,8 @@ private void *realloc(void *p, size_t size, uint attrs, else attrs = getAttr(pool, bit_i); - void* blk_base_addr = findBase(p); - size_t blk_size = findSize(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) { @@ -1488,10 +1433,13 @@ private void *realloc(void *p, size_t size, uint attrs, 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); + // 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 + (PAGESIZE * newsz) - - pm_bitmask_size); + auto end_of_blk = cast(size_t**)(blk_base_addr + + new_blk_size - pm_bitmask_size); *end_of_blk = pm_bitmask; } return p; @@ -1509,10 +1457,14 @@ private void *realloc(void *p, size_t size, uint attrs, - pm_bitmask_size); memset(pool.pagetable + pagenum + psz, B_PAGEPLUS, newsz - psz); + auto new_blk_size = (PAGESIZE * newsz); + // 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 + - (PAGESIZE * newsz) - + blk_base_addr + new_blk_size - pm_bitmask_size); *end_of_blk = pm_bitmask; } @@ -1572,8 +1524,8 @@ body auto bit_i = cast(size_t)(p - pool.baseAddr) / 16; uint attrs = getAttr(pool, bit_i); - void* blk_base_addr = findBase(p); - size_t blk_size = findSize(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 = null; size_t pm_bitmask_size = 0; @@ -1621,6 +1573,9 @@ body memset(pool.pagetable + pagenum + psz, B_PAGEPLUS, sz); gc.p_cache = null; gc.size_cache = 0; + // 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); if (has_pm) { new_size -= size_t.sizeof; @@ -1666,16 +1621,19 @@ private void free(void *p) if (opts.options.mem_stomp) memset(p, 0xF2, npages * PAGESIZE); pool.freePages(pagenum, npages); + // just in case we were caching this pointer + pool.clear_cache(p); } else { // Add to free list - List *list = cast(List*)p; + 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; } } @@ -1699,7 +1657,7 @@ private size_t sizeOf(void *p) auto biti = cast(size_t)(p - pool.baseAddr) / 16; uint attrs = getAttr(pool, biti); - size_t size = findSize(p); + size_t size = pool.findSize(p); size_t pm_bitmask_size = 0; if (has_pointermap(attrs)) pm_bitmask_size = size_t.sizeof; @@ -1766,9 +1724,7 @@ private void checkNoSync(void *p) if (bin < B_PAGE) { // Check that p is not on a free list - List *list; - - for (list = gc.free_list[bin]; list; list = list.next) + for (List* list = gc.free_list[bin]; list; list = list.next) { assert(cast(void*)list != p); } @@ -1834,7 +1790,7 @@ private GCStats getStats() for (n = 0; n < B_PAGE; n++) { - for (List *list = gc.free_list[n]; list; list = list.next) + for (List* list = gc.free_list[n]; list; list = list.next) flsize += binsize[n]; } @@ -1941,12 +1897,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); @@ -1956,13 +1929,20 @@ 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, vis); // ditto + scan.alloc(nbits); // only used in the mark phase + finals.alloc(nbits); // mark phase *MUST* have a snapshot + noscan.alloc(nbits); // ditto pagetable = cast(ubyte*) cstdlib.malloc(npages); if (!pagetable) @@ -1981,7 +1961,7 @@ struct Pool if (npages) { - result = alloc.os_mem_unmap(baseAddr, npages * PAGESIZE); + result = os.dealloc(baseAddr, npages * PAGESIZE); assert(result); npages = 0; } @@ -1993,9 +1973,12 @@ struct Pool if (pagetable) cstdlib.free(pagetable); - mark.Dtor(); + os.Vis vis = os.Vis.PRIV; + if (opts.options.fork) + vis = os.Vis.SHARED; + mark.Dtor(vis); + freebits.Dtor(vis); scan.Dtor(); - freebits.Dtor(); finals.Dtor(); noscan.Dtor(); } @@ -2063,6 +2046,52 @@ struct Pool } + /** + * 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 */ @@ -2099,8 +2128,9 @@ void sentinel_init(void *p, size_t size) void sentinel_Invariant(void *p) { - assert(*sentinel_pre(p) == SENTINEL_PRE); - assert(*sentinel_post(p) == SENTINEL_POST); + if (*sentinel_pre(p) != SENTINEL_PRE || + *sentinel_post(p) != SENTINEL_POST) + cstdlib.abort(); } @@ -2333,7 +2363,10 @@ void* gc_addrOf(void* p) return null; return locked!(void*, () { assert (Invariant()); scope (exit) assert (Invariant()); - return findBase(p); + Pool* pool = findPool(p); + if (pool is null) + return null; + return pool.findBase(p); })(); }