diff options
Diffstat (limited to 'lib/system/gc.nim')
| -rw-r--r-- | lib/system/gc.nim | 325 |
1 files changed, 169 insertions, 156 deletions
diff --git a/lib/system/gc.nim b/lib/system/gc.nim index 5405948eb..bd8c7a5da 100644 --- a/lib/system/gc.nim +++ b/lib/system/gc.nim @@ -1,7 +1,7 @@ # # # Nimrod's Runtime Library -# (c) Copyright 2012 Andreas Rumpf +# (c) Copyright 2013 Andreas Rumpf # # See the file "copying.txt", included in this # distribution, for details about the copyright. @@ -18,6 +18,9 @@ # for soft real time applications (like games). {.push profiler:off.} +# XXX there is still a slight chance of leaking cycles as we don't add cycle +# candidates in 'incRef' + const CycleIncrease = 2 # is a multiplicative increase InitialCycleThreshold = 4*1024*1024 # X MB because cycle checking is slow @@ -33,19 +36,17 @@ when defined(memProfiler): const rcIncrement = 0b1000 # so that lowest 3 bits are not touched - # NOTE: Most colors are currently unused rcBlack = 0b000 # cell is colored black; in use or free rcGray = 0b001 # possible member of a cycle rcWhite = 0b010 # member of a garbage cycle rcPurple = 0b011 # possible root of a cycle - rcZct = 0b100 # in ZCT - rcRed = 0b101 # Candidate cycle undergoing sigma-computation - rcOrange = 0b110 # Candidate cycle awaiting epoch boundary + ZctFlag = 0b100 # in ZCT rcShift = 3 # shift by rcShift to get the reference counter - colorMask = 0b111 + colorMask = 0b011 type TWalkOp = enum - waZctDecRef, waPush, waCycleDecRef + waZctDecRef, waPush, waCycleDecRef, waMarkGray, waScan, waScanBlack, + waCollectWhite TFinalizer {.compilerproc.} = proc (self: pointer) {.nimcall.} # A ref type can have a finalizer that is called before the object's @@ -88,9 +89,15 @@ template release(gch: TGcHeap) = when hasThreadSupport and hasSharedHeap: releaseSys(HeapLock) +template gcAssert(cond: bool, msg: string) = + when defined(useGcAssert): + if not cond: + echo "[GCASSERT] ", msg + quit 1 + proc addZCT(s: var TCellSeq, c: PCell) {.noinline.} = - if (c.refcount and rcZct) == 0: - c.refcount = c.refcount and not colorMask or rcZct + if (c.refcount and ZctFlag) == 0: + c.refcount = c.refcount or ZctFlag add(s, c) proc cellToUsr(cell: PCell): pointer {.inline.} = @@ -115,68 +122,22 @@ proc internRefcount(p: pointer): int {.exportc: "getRefcount".} = when BitsPerPage mod (sizeof(int)*8) != 0: {.error: "(BitsPerPage mod BitsPerUnit) should be zero!".} -when debugGC: - proc writeCell(msg: CString, c: PCell) = - var kind = -1 - if c.typ != nil: kind = ord(c.typ.kind) - when leakDetector: - c_fprintf(c_stdout, "[GC] %s: %p %d rc=%ld from %s(%ld)\n", - msg, c, kind, c.refcount shr rcShift, c.filename, c.line) - else: - c_fprintf(c_stdout, "[GC] %s: %p %d rc=%ld\n", - msg, c, kind, c.refcount shr rcShift) - -when traceGC: - # traceGC is a special switch to enable extensive debugging - type - TCellState = enum - csAllocated, csZctFreed, csCycFreed - var - states: array[TCellState, TCellSet] - - proc traceCell(c: PCell, state: TCellState) = - case state - of csAllocated: - if c in states[csAllocated]: - writeCell("attempt to alloc an already allocated cell", c) - sysAssert(false, "traceCell 1") - excl(states[csCycFreed], c) - excl(states[csZctFreed], c) - of csZctFreed: - if c in states[csZctFreed]: - writeCell("attempt to free zct cell twice", c) - sysAssert(false, "traceCell 2") - if c in states[csCycFreed]: - writeCell("attempt to free with zct, but already freed with cyc", c) - sysAssert(false, "traceCell 3") - if c notin states[csAllocated]: - writeCell("attempt to free not an allocated cell", c) - sysAssert(false, "traceCell 4") - excl(states[csAllocated], c) - of csCycFreed: - if c notin states[csAllocated]: - writeCell("attempt to free a not allocated cell", c) - sysAssert(false, "traceCell 5") - if c in states[csCycFreed]: - writeCell("attempt to free cyc cell twice", c) - sysAssert(false, "traceCell 6") - if c in states[csZctFreed]: - writeCell("attempt to free with cyc, but already freed with zct", c) - sysAssert(false, "traceCell 7") - excl(states[csAllocated], c) - incl(states[state], c) - - proc writeLeakage() = - var z = 0 - var y = 0 - var e = 0 - for c in elements(states[csAllocated]): - inc(e) - if c in states[csZctFreed]: inc(z) - elif c in states[csCycFreed]: inc(y) - else: writeCell("leak", c) - cfprintf(cstdout, "Allocations: %ld; ZCT freed: %ld; CYC freed: %ld\n", - e, z, y) +template color(c): expr = c.refCount and colorMask +template setColor(c, col) = + when col == rcBlack: + c.refcount = c.refCount and not colorMask + else: + c.refcount = c.refCount and not colorMask or col + +proc writeCell(msg: CString, c: PCell) = + var kind = -1 + if c.typ != nil: kind = ord(c.typ.kind) + when leakDetector: + c_fprintf(c_stdout, "[GC] %s: %p %d rc=%ld from %s(%ld)\n", + msg, c, kind, c.refcount shr rcShift, c.filename, c.line) + else: + c_fprintf(c_stdout, "[GC] %s: %p %d rc=%ld; color=%ld\n", + msg, c, kind, c.refcount shr rcShift, c.color) template gcTrace(cell, state: expr): stmt {.immediate.} = when traceGC: traceCell(cell, state) @@ -213,7 +174,9 @@ proc rtlAddCycleRoot(c: PCell) {.rtl, inl.} = # we MUST access gch as a global here, because this crosses DLL boundaries! when hasThreadSupport and hasSharedHeap: AcquireSys(HeapLock) - incl(gch.cycleRoots, c) + if c.color != rcPurple: + c.setColor(rcPurple) + incl(gch.cycleRoots, c) when hasThreadSupport and hasSharedHeap: ReleaseSys(HeapLock) @@ -226,20 +189,22 @@ proc rtlAddZCT(c: PCell) {.rtl, inl.} = ReleaseSys(HeapLock) proc decRef(c: PCell) {.inline.} = - sysAssert(isAllocatedPtr(gch.region, c), "decRef: interiorPtr") - sysAssert(c.refcount >=% rcIncrement, "decRef") + gcAssert(isAllocatedPtr(gch.region, c), "decRef: interiorPtr") + gcAssert(c.refcount >=% rcIncrement, "decRef") if --c.refcount: rtlAddZCT(c) elif canBeCycleRoot(c): # unfortunately this is necessary here too, because a cycle might just # have been broken up and we could recycle it. - rtlAddCycleRoot(c) + rtlAddCycleRoot(c) + #writeCell("decRef", c) proc incRef(c: PCell) {.inline.} = - sysAssert(isAllocatedPtr(gch.region, c), "incRef: interiorPtr") - ++c.refcount - if canBeCycleRoot(c): - rtlAddCycleRoot(c) + gcAssert(isAllocatedPtr(gch.region, c), "incRef: interiorPtr") + c.refcount = c.refCount +% rcIncrement and not colorMask + #writeCell("incRef", c) + #if canBeCycleRoot(c): + # rtlAddCycleRoot(c) proc nimGCref(p: pointer) {.compilerProc, inline.} = incRef(usrToCell(p)) proc nimGCunref(p: pointer) {.compilerProc, inline.} = decRef(usrToCell(p)) @@ -247,7 +212,7 @@ proc nimGCunref(p: pointer) {.compilerProc, inline.} = decRef(usrToCell(p)) proc nimGCunrefNoCycle(p: pointer) {.compilerProc, inline.} = sysAssert(allocInv(gch.region), "begin nimGCunrefNoCycle") var c = usrToCell(p) - sysAssert(isAllocatedPtr(gch.region, c), "nimGCunrefNoCycle: isAllocatedPtr") + gcAssert(isAllocatedPtr(gch.region, c), "nimGCunrefNoCycle: isAllocatedPtr") if --c.refcount: rtlAddZCT(c) sysAssert(allocInv(gch.region), "end nimGCunrefNoCycle 2") @@ -255,7 +220,7 @@ proc nimGCunrefNoCycle(p: pointer) {.compilerProc, inline.} = proc asgnRef(dest: ppointer, src: pointer) {.compilerProc, inline.} = # the code generator calls this proc! - sysAssert(not isOnStack(dest), "asgnRef") + gcAssert(not isOnStack(dest), "asgnRef") # BUGFIX: first incRef then decRef! if src != nil: incRef(usrToCell(src)) if dest[] != nil: decRef(usrToCell(dest[])) @@ -285,14 +250,14 @@ proc unsureAsgnRef(dest: ppointer, src: pointer) {.compilerProc.} = if cast[int](dest[]) >=% PageSize: decRef(usrToCell(dest[])) else: # can't be an interior pointer if it's a stack location! - sysAssert(interiorAllocatedPtr(gch.region, dest)==nil, - "stack loc AND interior pointer") + gcAssert(interiorAllocatedPtr(gch.region, dest) == nil, + "stack loc AND interior pointer") dest[] = src proc initGC() = when not defined(useNimRtl): when traceGC: - for i in low(TCellState)..high(TCellState): Init(states[i]) + for i in low(TCellState)..high(TCellState): init(states[i]) gch.cycleThreshold = InitialCycleThreshold gch.stat.stackScans = 0 gch.stat.cycleCollections = 0 @@ -303,8 +268,8 @@ proc initGC() = # init the rt init(gch.zct) init(gch.tempStack) - Init(gch.cycleRoots) - Init(gch.decStack) + init(gch.cycleRoots) + init(gch.decStack) proc forAllSlotsAux(dest: pointer, n: ptr TNimNode, op: TWalkOp) = var d = cast[TAddress](dest) @@ -341,9 +306,9 @@ proc forAllChildrenAux(dest: Pointer, mt: PNimType, op: TWalkOp) = else: nil proc forAllChildren(cell: PCell, op: TWalkOp) = - sysAssert(cell != nil, "forAllChildren: 1") - sysAssert(cell.typ != nil, "forAllChildren: 2") - sysAssert cell.typ.kind in {tyRef, tySequence, tyString}, "forAllChildren: 3" + gcAssert(cell != nil, "forAllChildren: 1") + gcAssert(cell.typ != nil, "forAllChildren: 2") + gcAssert cell.typ.kind in {tyRef, tySequence, tyString}, "forAllChildren: 3" let marker = cell.typ.marker if marker != nil: marker(cellToUsr(cell), op.int) @@ -378,7 +343,7 @@ proc addNewObjToZCT(res: PCell, gch: var TGcHeap) {.inline.} = template replaceZctEntry(i: expr) = c = d[i] if c.refcount >=% rcIncrement: - c.refcount = c.refcount and not colorMask + c.refcount = c.refcount and not ZctFlag d[i] = res return if L > 8: @@ -399,7 +364,7 @@ proc addNewObjToZCT(res: PCell, gch: var TGcHeap) {.inline.} = for i in countdown(L-1, max(0, L-8)): var c = d[i] if c.refcount >=% rcIncrement: - c.refcount = c.refcount and not colorMask + c.refcount = c.refcount and not ZctFlag d[i] = res return add(gch.zct, res) @@ -407,18 +372,19 @@ proc addNewObjToZCT(res: PCell, gch: var TGcHeap) {.inline.} = proc rawNewObj(typ: PNimType, size: int, gch: var TGcHeap): pointer = # generates a new object and sets its reference counter to 0 acquire(gch) - sysAssert(typ.kind in {tyRef, tyString, tySequence}, "newObj: 1") + gcAssert(typ.kind in {tyRef, tyString, tySequence}, "newObj: 1") collectCT(gch) sysAssert(allocInv(gch.region), "rawNewObj begin") var res = cast[PCell](rawAlloc(gch.region, size + sizeof(TCell))) - sysAssert((cast[TAddress](res) and (MemAlign-1)) == 0, "newObj: 2") + gcAssert((cast[TAddress](res) and (MemAlign-1)) == 0, "newObj: 2") # now it is buffered in the ZCT res.typ = typ when leakDetector and not hasThreadSupport: if framePtr != nil and framePtr.prev != nil: res.filename = framePtr.prev.filename res.line = framePtr.prev.line - res.refcount = rcZct # refcount is zero, but mark it to be in the ZCT + # refcount is zero, color is black, but mark it to be in the ZCT + res.refcount = ZctFlag sysAssert(isAllocatedPtr(gch.region, res), "newObj: 3") # its refcount is zero, so add it to the ZCT: addNewObjToZCT(res, gch) @@ -447,7 +413,7 @@ proc newObjRC1(typ: PNimType, size: int): pointer {.compilerRtl.} = # generates a new object and sets its reference counter to 1 sysAssert(allocInv(gch.region), "newObjRC1 begin") acquire(gch) - sysAssert(typ.kind in {tyRef, tyString, tySequence}, "newObj: 1") + gcAssert(typ.kind in {tyRef, tyString, tySequence}, "newObj: 1") collectCT(gch) sysAssert(allocInv(gch.region), "newObjRC1 after collectCT") @@ -482,7 +448,7 @@ proc growObj(old: pointer, newsize: int, gch: var TGcHeap): pointer = collectCT(gch) var ol = usrToCell(old) sysAssert(ol.typ != nil, "growObj: 1") - sysAssert(ol.typ.kind in {tyString, tySequence}, "growObj: 2") + gcAssert(ol.typ.kind in {tyString, tySequence}, "growObj: 2") sysAssert(allocInv(gch.region), "growObj begin") var res = cast[PCell](rawAlloc(gch.region, newsize + sizeof(TCell))) @@ -499,7 +465,7 @@ proc growObj(old: pointer, newsize: int, gch: var TGcHeap): pointer = # add(gch.zct, res) #else: # XXX: what to do here? # decRef(ol) - if (ol.refcount and colorMask) == rcZct: + if (ol.refcount and ZctFlag) != 0: var j = gch.zct.len-1 var d = gch.zct.d while j >= 0: @@ -529,74 +495,122 @@ proc growObj(old: pointer, newsize: int): pointer {.rtl.} = # ---------------- cycle collector ------------------------------------------- +proc freeCyclicCell(gch: var TGcHeap, c: PCell) = + prepareDealloc(c) + gcTrace(c, csCycFreed) + when logGC: writeCell("cycle collector dealloc cell", c) + when reallyDealloc: rawDealloc(gch.region, c) + else: + gcAssert(c.typ != nil, "freeCyclicCell") + zeroMem(c, sizeof(TCell)) + +proc markGray(s: PCell) = + if s.color != rcGray: + setColor(s, rcGray) + forAllChildren(s, waMarkGray) + +proc scanBlack(s: PCell) = + s.setColor(rcBlack) + forAllChildren(s, waScanBlack) + +proc scan(s: PCell) = + if s.color == rcGray: + if s.refcount >=% rcIncrement: + scanBlack(s) + else: + s.setColor(rcWhite) + forAllChildren(s, waScan) + +proc collectWhite(s: PCell) = + if s.color == rcWhite and s notin gch.cycleRoots: + s.setcolor(rcBlack) + forAllChildren(s, waCollectWhite) + freeCyclicCell(gch, s) + +proc MarkRoots(gch: var TGcHeap) = + var tabSize = 0 + for s in elements(gch.cycleRoots): + #writeCell("markRoot", s) + inc tabSize + if s.color == rcPurple and s.refCount >=% rcIncrement: + markGray(s) + else: + excl(gch.cycleRoots, s) + # (s.color == rcBlack and rc == 0) as 1 condition: + if s.refcount == 0: + freeCyclicCell(gch, s) + gch.stat.cycleTableSize = max(gch.stat.cycleTableSize, tabSize) + proc doOperation(p: pointer, op: TWalkOp) = if p == nil: return var c: PCell = usrToCell(p) - sysAssert(c != nil, "doOperation: 1") - case op # faster than function pointers because of easy prediction + gcAssert(c != nil, "doOperation: 1") + # the 'case' should be faster than function pointers because of easy + # prediction: + case op of waZctDecRef: #if not isAllocatedPtr(gch.region, c): # return # c_fprintf(c_stdout, "[GC] decref bug: %p", c) - sysAssert(isAllocatedPtr(gch.region, c), "decRef: waZctDecRef") - sysAssert(c.refcount >=% rcIncrement, "doOperation 2") - c.refcount = c.refcount -% rcIncrement + gcAssert(isAllocatedPtr(gch.region, c), "decRef: waZctDecRef") + gcAssert(c.refcount >=% rcIncrement, "doOperation 2") + #c.refcount = c.refcount -% rcIncrement when logGC: writeCell("decref (from doOperation)", c) - if c.refcount <% rcIncrement: addZCT(gch.zct, c) + decRef(c) + #if c.refcount <% rcIncrement: addZCT(gch.zct, c) of waPush: add(gch.tempStack, c) of waCycleDecRef: - sysAssert(c.refcount >=% rcIncrement, "doOperation 3") + gcAssert(c.refcount >=% rcIncrement, "doOperation 3") + c.refcount = c.refcount -% rcIncrement + of waMarkGray: + gcAssert(c.refcount >=% rcIncrement, "waMarkGray") c.refcount = c.refcount -% rcIncrement + markGray(c) + of waScan: scan(c) + of waScanBlack: + c.refcount = c.refcount +% rcIncrement + if c.color != rcBlack: + scanBlack(c) + of waCollectWhite: collectWhite(c) proc nimGCvisit(d: pointer, op: int) {.compilerRtl.} = doOperation(d, TWalkOp(op)) -# we now use a much simpler and non-recursive algorithm for cycle removal +proc CollectZCT(gch: var TGcHeap): bool + +proc collectRoots(gch: var TGcHeap) = + for s in elements(gch.cycleRoots): + excl(gch.cycleRoots, s) + collectWhite(s) + proc collectCycles(gch: var TGcHeap) = - var tabSize = 0 - for c in elements(gch.cycleRoots): - inc(tabSize) - forallChildren(c, waCycleDecRef) - if tabSize == 0: return - gch.stat.cycleTableSize = max(gch.stat.cycleTableSize, tabSize) + # ensure the ZCT 'color' is not used: + while gch.zct.len > 0: discard collectZCT(gch) + markRoots(gch) + # scanRoots: + for s in elements(gch.cycleRoots): scan(s) + collectRoots(gch) - # restore reference counts (a depth-first traversal is needed): - var marker: TCellSet - Init(marker) - for c in elements(gch.cycleRoots): - if c.refcount >=% rcIncrement: - if not containsOrIncl(marker, c): - gch.tempStack.len = 0 - forAllChildren(c, waPush) - while gch.tempStack.len > 0: - dec(gch.tempStack.len) - var d = gch.tempStack.d[gch.tempStack.len] - d.refcount = d.refcount +% rcIncrement - if d in gch.cycleRoots and not containsOrIncl(marker, d): - forAllChildren(d, waPush) - Deinit(marker) - # remove cycles: - for c in elements(gch.cycleRoots): - if c.refcount <% rcIncrement: - gch.tempStack.len = 0 - forAllChildren(c, waPush) - while gch.tempStack.len > 0: - dec(gch.tempStack.len) - var d = gch.tempStack.d[gch.tempStack.len] - if d.refcount <% rcIncrement: - if d notin gch.cycleRoots: # d is leaf of c and not part of cycle - addZCT(gch.zct, d) - when logGC: writeCell("add to ZCT (from cycle collector)", d) - prepareDealloc(c) - gcTrace(c, csCycFreed) - when logGC: writeCell("cycle collector dealloc cell", c) - when reallyDealloc: rawDealloc(gch.region, c) - else: - sysAssert(c.typ != nil, "collectCycles") - zeroMem(c, sizeof(TCell)) Deinit(gch.cycleRoots) Init(gch.cycleRoots) + # alive cycles need to be kept in 'cycleRoots' if they are referenced + # from the stack; otherwise the write barrier will add the cycle root again + # anyway: + when false: + var d = gch.decStack.d + var cycleRootsLen = 0 + for i in 0..gch.decStack.len-1: + var c = d[i] + gcAssert isAllocatedPtr(gch.region, c), "addBackStackRoots" + gcAssert c.refcount >=% rcIncrement, "addBackStackRoots: dead cell" + if canBeCycleRoot(c): + #if c notin gch.cycleRoots: + inc cycleRootsLen + incl(gch.cycleRoots, c) + gcAssert c.typ != nil, "addBackStackRoots 2" + if cycleRootsLen != 0: + cfprintf(cstdout, "cycle roots: %ld\n", cycleRootsLen) proc gcMark(gch: var TGcHeap, p: pointer) {.inline.} = # the addresses are not as cells on the stack, so turn them to cells: @@ -778,9 +792,9 @@ proc CollectZCT(gch: var TGcHeap): bool = var c = gch.zct.d[0] sysAssert(isAllocatedPtr(gch.region, c), "CollectZCT: isAllocatedPtr") # remove from ZCT: - sysAssert((c.refcount and rcZct) == rcZct, "collectZCT") + gcAssert((c.refcount and ZctFlag) == ZctFlag, "collectZCT") - c.refcount = c.refcount and not colorMask + c.refcount = c.refcount and not ZctFlag gch.zct.d[0] = gch.zct.d[L[] - 1] dec(L[]) when withRealtime: dec steps @@ -809,22 +823,22 @@ proc CollectZCT(gch: var TGcHeap): bool = if gch.maxPause > 0: let duration = getticks() - t0 # the GC's measuring is not accurate and needs some cleanup actions - # (stack unmarking), so subtract some short amount of time in to + # (stack unmarking), so subtract some short amount of time in # order to miss deadlines less often: if duration >= gch.maxPause - 50_000: return false result = true -proc unmarkStackAndRegisters(gch: var TGcHeap) = +proc unmarkStackAndRegisters(gch: var TGcHeap) = var d = gch.decStack.d for i in 0..gch.decStack.len-1: sysAssert isAllocatedPtr(gch.region, d[i]), "unmarkStackAndRegisters" - # decRef(d[i]) inlined: cannot create a cycle and must not acquire lock - var c = d[i] + decRef(d[i]) + #var c = d[i] # XXX no need for an atomic dec here: - if --c.refcount: - addZCT(gch.zct, c) - sysAssert c.typ != nil, "unmarkStackAndRegisters 2" + #if --c.refcount: + # addZCT(gch.zct, c) + #sysAssert c.typ != nil, "unmarkStackAndRegisters 2" gch.decStack.len = 0 proc collectCTBody(gch: var TGcHeap) = @@ -843,7 +857,7 @@ proc collectCTBody(gch: var TGcHeap) = when cycleGC: if getOccupiedMem(gch.region) >= gch.cycleThreshold or alwaysCycleGC: collectCycles(gch) - discard collectZCT(gch) + #discard collectZCT(gch) inc(gch.stat.cycleCollections) gch.cycleThreshold = max(InitialCycleThreshold, getOccupiedMem() * cycleIncrease) @@ -929,7 +943,6 @@ when not defined(useNimRtl): "[GC] max cycle table size: " & $gch.stat.cycleTableSize & "\n" & "[GC] max stack size: " & $gch.stat.maxStackSize & "\n" & "[GC] max pause time [ms]: " & $(gch.stat.maxPause div 1000_000) - when traceGC: writeLeakage() GC_enable() {.pop.} |