diff options
Diffstat (limited to 'lib/system/gc.nim')
| -rw-r--r-- | lib/system/gc.nim | 140 |
1 files changed, 81 insertions, 59 deletions
diff --git a/lib/system/gc.nim b/lib/system/gc.nim index 304eda19a..9289c7f55 100644 --- a/lib/system/gc.nim +++ b/lib/system/gc.nim @@ -12,6 +12,55 @@ # Refcounting + Mark&Sweep. Complex algorithms avoided. # Been there, done that, didn't work. +#[ + +A *cell* is anything that is traced by the GC +(sequences, refs, strings, closures). + +The basic algorithm is *Deferrent Reference Counting* with cycle detection. +References on the stack are not counted for better performance and easier C +code generation. + +Each cell has a header consisting of a RC and a pointer to its type +descriptor. However the program does not know about these, so they are placed at +negative offsets. In the GC code the type `PCell` denotes a pointer +decremented by the right offset, so that the header can be accessed easily. It +is extremely important that `pointer` is not confused with a `PCell`. + +In Nim the compiler cannot always know if a reference +is stored on the stack or not. This is caused by var parameters. +Consider this example: + + ```Nim + proc setRef(r: var ref TNode) = + new(r) + + proc usage = + var + r: ref TNode + setRef(r) # here we should not update the reference counts, because + # r is on the stack + setRef(r.left) # here we should update the refcounts! + ``` + +We have to decide at runtime whether the reference is on the stack or not. +The generated code looks roughly like this: + + ```C + void setref(TNode** ref) { + unsureAsgnRef(ref, newObj(TNode_TI, sizeof(TNode))) + } + void usage(void) { + setRef(&r) + setRef(&r->left) + } + ``` + +Note that for systems with a continuous stack (which most systems have) +the check whether the ref is on the stack is very cheap (only two +comparisons). +]# + {.push profiler:off.} const @@ -29,7 +78,7 @@ when defined(memProfiler): proc nimProfile(requestedSize: int) {.benign.} when hasThreadSupport: - import sharedlist + import std/sharedlist const rcIncrement = 0b1000 # so that lowest 3 bits are not touched @@ -47,7 +96,7 @@ type waZctDecRef, waPush #, waDebug - Finalizer {.compilerproc.} = proc (self: pointer) {.nimcall, benign.} + Finalizer {.compilerproc.} = proc (self: pointer) {.nimcall, benign, raises: [].} # A ref type can have a finalizer that is called before the object's # storage is freed. @@ -114,7 +163,7 @@ template gcAssert(cond: bool, msg: string) = writeStackTrace() #var x: ptr int #echo x[] - quit 1 + rawQuit 1 proc addZCT(s: var CellSeq, c: PCell) {.noinline.} = if (c.refcount and ZctFlag) == 0: @@ -123,11 +172,11 @@ proc addZCT(s: var CellSeq, c: PCell) {.noinline.} = proc cellToUsr(cell: PCell): pointer {.inline.} = # convert object (=pointer to refcount) to pointer to userdata - result = cast[pointer](cast[ByteAddress](cell)+%ByteAddress(sizeof(Cell))) + result = cast[pointer](cast[int](cell)+%ByteAddress(sizeof(Cell))) proc usrToCell(usr: pointer): PCell {.inline.} = # convert pointer to userdata to object (=pointer to refcount) - result = cast[PCell](cast[ByteAddress](usr)-%ByteAddress(sizeof(Cell))) + result = cast[PCell](cast[int](usr)-%ByteAddress(sizeof(Cell))) proc extGetCellType(c: pointer): PNimType {.compilerproc.} = # used for code generation concerning debugging @@ -172,11 +221,11 @@ template gcTrace(cell, state: untyped) = when traceGC: traceCell(cell, state) # forward declarations: -proc collectCT(gch: var GcHeap) {.benign.} -proc isOnStack(p: pointer): bool {.noinline, benign.} -proc forAllChildren(cell: PCell, op: WalkOp) {.benign.} -proc doOperation(p: pointer, op: WalkOp) {.benign.} -proc forAllChildrenAux(dest: pointer, mt: PNimType, op: WalkOp) {.benign.} +proc collectCT(gch: var GcHeap) {.benign, raises: [].} +proc isOnStack(p: pointer): bool {.noinline, benign, raises: [].} +proc forAllChildren(cell: PCell, op: WalkOp) {.benign, raises: [].} +proc doOperation(p: pointer, op: WalkOp) {.benign, raises: [].} +proc forAllChildrenAux(dest: pointer, mt: PNimType, op: WalkOp) {.benign, raises: [].} # we need the prototype here for debugging purposes proc incRef(c: PCell) {.inline.} = @@ -289,7 +338,7 @@ proc cellsetReset(s: var CellSet) = {.push stacktrace:off.} proc forAllSlotsAux(dest: pointer, n: ptr TNimNode, op: WalkOp) {.benign.} = - var d = cast[ByteAddress](dest) + var d = cast[int](dest) case n.kind of nkSlot: forAllChildrenAux(cast[pointer](d +% n.offset), n.typ, op) of nkList: @@ -309,7 +358,7 @@ proc forAllSlotsAux(dest: pointer, n: ptr TNimNode, op: WalkOp) {.benign.} = of nkNone: sysAssert(false, "forAllSlotsAux") proc forAllChildrenAux(dest: pointer, mt: PNimType, op: WalkOp) = - var d = cast[ByteAddress](dest) + var d = cast[int](dest) if dest == nil: return # nothing to do if ntfNoRefs notin mt.flags: case mt.kind @@ -335,7 +384,7 @@ proc forAllChildren(cell: PCell, op: WalkOp) = of tyRef: # common case forAllChildrenAux(cellToUsr(cell), cell.typ.base, op) of tySequence: - var d = cast[ByteAddress](cellToUsr(cell)) + var d = cast[int](cellToUsr(cell)) var s = cast[PGenericSeq](d) if s != nil: for i in 0..s.len-1: @@ -410,7 +459,7 @@ proc rawNewObj(typ: PNimType, size: int, gch: var GcHeap): pointer = collectCT(gch) var res = cast[PCell](rawAlloc(gch.region, size + sizeof(Cell))) #gcAssert typ.kind in {tyString, tySequence} or size >= typ.base.size, "size too small" - gcAssert((cast[ByteAddress](res) and (MemAlign-1)) == 0, "newObj: 2") + gcAssert((cast[int](res) and (MemAlign-1)) == 0, "newObj: 2") # now it is buffered in the ZCT res.typ = typ setFrameInfo(res) @@ -435,7 +484,7 @@ proc newObjNoInit(typ: PNimType, size: int): pointer {.compilerRtl.} = result = rawNewObj(typ, size, gch) when defined(memProfiler): nimProfile(size) -proc newObj(typ: PNimType, size: int): pointer {.compilerRtl.} = +proc newObj(typ: PNimType, size: int): pointer {.compilerRtl, noinline.} = result = rawNewObj(typ, size, gch) zeroMem(result, size) when defined(memProfiler): nimProfile(size) @@ -450,7 +499,7 @@ proc newSeq(typ: PNimType, len: int): pointer {.compilerRtl.} = when defined(memProfiler): nimProfile(size) {.pop.} -proc newObjRC1(typ: PNimType, size: int): pointer {.compilerRtl.} = +proc newObjRC1(typ: PNimType, size: int): pointer {.compilerRtl, noinline.} = # generates a new object and sets its reference counter to 1 incTypeSize typ, size sysAssert(allocInv(gch.region), "newObjRC1 begin") @@ -460,7 +509,7 @@ proc newObjRC1(typ: PNimType, size: int): pointer {.compilerRtl.} = var res = cast[PCell](rawAlloc(gch.region, size + sizeof(Cell))) sysAssert(allocInv(gch.region), "newObjRC1 after rawAlloc") - sysAssert((cast[ByteAddress](res) and (MemAlign-1)) == 0, "newObj: 2") + sysAssert((cast[int](res) and (MemAlign-1)) == 0, "newObj: 2") # now it is buffered in the ZCT res.typ = typ setFrameInfo(res) @@ -502,9 +551,9 @@ proc growObj(old: pointer, newsize: int, gch: var GcHeap): pointer = var oldsize = align(GenericSeqSize, elemAlign) + cast[PGenericSeq](old).len * elemSize copyMem(res, ol, oldsize + sizeof(Cell)) - zeroMem(cast[pointer](cast[ByteAddress](res) +% oldsize +% sizeof(Cell)), + zeroMem(cast[pointer](cast[int](res) +% oldsize +% sizeof(Cell)), newsize-oldsize) - sysAssert((cast[ByteAddress](res) and (MemAlign-1)) == 0, "growObj: 3") + sysAssert((cast[int](res) and (MemAlign-1)) == 0, "growObj: 3") # This can be wrong for intermediate temps that are nevertheless on the # heap because of lambda lifting: #gcAssert(res.refcount shr rcShift <=% 1, "growObj: 4") @@ -514,35 +563,8 @@ proc growObj(old: pointer, newsize: int, gch: var GcHeap): pointer = gcTrace(res, csAllocated) track("growObj old", ol, 0) track("growObj new", res, newsize) - when defined(nimIncrSeqV3): - # since we steal the old seq's contents, we set the old length to 0. - cast[PGenericSeq](old).len = 0 - elif reallyDealloc: - sysAssert(allocInv(gch.region), "growObj before dealloc") - if ol.refcount shr rcShift <=% 1: - # free immediately to save space: - if (ol.refcount and ZctFlag) != 0: - var j = gch.zct.len-1 - var d = gch.zct.d - while j >= 0: - if d[j] == ol: - d[j] = res - break - dec(j) - beforeDealloc(gch, ol, "growObj stack trash") - decTypeSize(ol, ol.typ) - rawDealloc(gch.region, ol) - else: - # we split the old refcount in 2 parts. XXX This is still not entirely - # correct if the pointer that receives growObj's result is on the stack. - # A better fix would be to emit the location specific write barrier for - # 'growObj', but this is lots of more work and who knows what new problems - # this would create. - res.refcount = rcIncrement - decRef(ol) - else: - sysAssert(ol.typ != nil, "growObj: 5") - zeroMem(ol, sizeof(Cell)) + # since we steal the old seq's contents, we set the old length to 0. + cast[PGenericSeq](old).len = 0 when useCellIds: inc gch.idGenerator res.id = gch.idGenerator * 1000_000 + gch.gcThreadId @@ -589,7 +611,7 @@ proc markS(gch: var GcHeap, c: PCell) = if not containsOrIncl(gch.marked, d): forAllChildren(d, waMarkPrecise) -proc markGlobals(gch: var GcHeap) = +proc markGlobals(gch: var GcHeap) {.raises: [].} = if gch.gcThreadId == 0: for i in 0 .. globalMarkersLen-1: globalMarkers[i]() for i in 0 .. threadLocalMarkersLen-1: threadLocalMarkers[i]() @@ -606,7 +628,7 @@ when logGC: if cycleCheckA[i] == c: return true if cycleCheckALen == len(cycleCheckA): gcAssert(false, "cycle detection overflow") - quit 1 + rawQuit 1 cycleCheckA[cycleCheckALen] = c inc cycleCheckALen @@ -644,9 +666,9 @@ proc doOperation(p: pointer, op: WalkOp) = proc nimGCvisit(d: pointer, op: int) {.compilerRtl.} = doOperation(d, WalkOp(op)) -proc collectZCT(gch: var GcHeap): bool {.benign.} +proc collectZCT(gch: var GcHeap): bool {.benign, raises: [].} -proc collectCycles(gch: var GcHeap) = +proc collectCycles(gch: var GcHeap) {.raises: [].} = when hasThreadSupport: for c in gch.toDispose: nimGCunref(c) @@ -663,16 +685,16 @@ proc collectCycles(gch: var GcHeap) = proc gcMark(gch: var GcHeap, p: pointer) {.inline.} = # the addresses are not as cells on the stack, so turn them to cells: sysAssert(allocInv(gch.region), "gcMark begin") - var cell = usrToCell(p) - var c = cast[ByteAddress](cell) + var c = cast[int](p) if c >% PageSize: # fast check: does it look like a cell? - var objStart = cast[PCell](interiorAllocatedPtr(gch.region, cell)) + var objStart = cast[PCell](interiorAllocatedPtr(gch.region, p)) if objStart != nil: # mark the cell: incRef(objStart) add(gch.decStack, objStart) when false: + let cell = usrToCell(p) if isAllocatedPtr(gch.region, cell): sysAssert false, "allocated pointer but not interior?" # mark the cell: @@ -753,7 +775,7 @@ proc unmarkStackAndRegisters(gch: var GcHeap) = decRef(d[i]) gch.decStack.len = 0 -proc collectCTBody(gch: var GcHeap) = +proc collectCTBody(gch: var GcHeap) {.raises: [].} = when withRealTime: let t0 = getticks() sysAssert(allocInv(gch.region), "collectCT: begin") @@ -828,10 +850,10 @@ when withRealTime: stack.bottomSaved = stack.bottom when stackIncreases: stack.bottom = cast[pointer]( - cast[ByteAddress](stack.pos) - sizeof(pointer) * 6 - stackSize) + cast[int](stack.pos) - sizeof(pointer) * 6 - stackSize) else: stack.bottom = cast[pointer]( - cast[ByteAddress](stack.pos) + sizeof(pointer) * 6 + stackSize) + cast[int](stack.pos) + sizeof(pointer) * 6 + stackSize) GC_step(gch, us, strongAdvice) @@ -856,7 +878,7 @@ when not defined(useNimRtl): gch.cycleThreshold = InitialCycleThreshold proc GC_disableMarkAndSweep() = - gch.cycleThreshold = high(gch.cycleThreshold)-1 + gch.cycleThreshold = high(typeof(gch.cycleThreshold))-1 # set to the max value to suppress the cycle detector proc GC_fullCollect() = |