diff options
| -rw-r--r-- | compiler/ccgexprs.nim | 40 | ||||
| -rw-r--r-- | compiler/ccgtypes.nim | 5 | ||||
| -rw-r--r-- | compiler/liftdestructors.nim | 7 | ||||
| -rw-r--r-- | compiler/lineinfos.nim | 2 | ||||
| -rw-r--r-- | compiler/sempass2.nim | 10 | ||||
| -rw-r--r-- | lib/pure/asyncfutures.nim | 2 | ||||
| -rw-r--r-- | lib/system/cyclebreaker.nim | 227 | ||||
| -rw-r--r-- | lib/system/cyclicrefs_v2.nim | 18 | ||||
| -rw-r--r-- | lib/system/refs_v2.nim | 9 | ||||
| -rw-r--r-- | tests/arc/tasyncawait.nim | 19 |
10 files changed, 298 insertions, 41 deletions
diff --git a/compiler/ccgexprs.nim b/compiler/ccgexprs.nim index 4cf6f36db..2d1005f5e 100644 --- a/compiler/ccgexprs.nim +++ b/compiler/ccgexprs.nim @@ -1606,10 +1606,33 @@ proc genRepr(p: BProc, e: PNode, d: var TLoc) = a.storage) gcUsage(p.config, e) +proc rdMType(p: BProc; a: TLoc; nilCheck: var Rope): Rope = + result = rdLoc(a) + var t = skipTypes(a.t, abstractInst) + while t.kind in {tyVar, tyLent, tyPtr, tyRef}: + if t.kind notin {tyVar, tyLent}: nilCheck = result + if t.kind notin {tyVar, tyLent} or not p.module.compileToCpp: + result = "(*$1)" % [result] + t = skipTypes(t.lastSon, abstractInst) + discard getTypeDesc(p.module, t) + if not p.module.compileToCpp: + while t.kind == tyObject and t[0] != nil: + result.add(".Sup") + t = skipTypes(t[0], skipPtrs) + result.add ".m_type" + proc genGetTypeInfo(p: BProc, e: PNode, d: var TLoc) = discard cgsym(p.module, "TNimType") let t = e[1].typ - putIntoDest(p, d, e, genTypeInfo(p.module, t, e.info)) + if isFinal(t) or e[0].sym.name.s != "getDynamicTypeInfo": + # ordinary static type information + putIntoDest(p, d, e, genTypeInfo(p.module, t, e.info)) + else: + var a: TLoc + initLocExpr(p, e[1], a) + var nilCheck = Rope(nil) + # use the dynamic type stored at offset 0: + putIntoDest(p, d, e, rdMType(p, a, nilCheck)) template genDollar(p: BProc, n: PNode, d: var TLoc, frmt: string) = var a: TLoc @@ -2113,21 +2136,6 @@ proc genEnumToStr(p: BProc, e: PNode, d: var TLoc) = n[0] = newSymNode(toStrProc) expr(p, n, d) -proc rdMType(p: BProc; a: TLoc; nilCheck: var Rope): Rope = - result = rdLoc(a) - var t = skipTypes(a.t, abstractInst) - while t.kind in {tyVar, tyLent, tyPtr, tyRef}: - if t.kind notin {tyVar, tyLent}: nilCheck = result - if t.kind notin {tyVar, tyLent} or not p.module.compileToCpp: - result = "(*$1)" % [result] - t = skipTypes(t.lastSon, abstractInst) - discard getTypeDesc(p.module, t) - if not p.module.compileToCpp: - while t.kind == tyObject and t[0] != nil: - result.add(".Sup") - t = skipTypes(t[0], skipPtrs) - result.add ".m_type" - proc genMagicExpr(p: BProc, e: PNode, d: var TLoc, op: TMagic) = case op of mOr, mAnd: genAndOr(p, e, d, op) diff --git a/compiler/ccgtypes.nim b/compiler/ccgtypes.nim index 926cf2f08..dbdd0a6c7 100644 --- a/compiler/ccgtypes.nim +++ b/compiler/ccgtypes.nim @@ -1291,6 +1291,11 @@ proc genHook(m: BModule; t: PType; info: TLineInfo; op: TTypeAttachedOp): Rope = genProc(m, theProc) result = theProc.loc.r else: + if op == attachedTrace and m.config.selectedGC == gcOrc and + containsGarbageCollectedRef(t): + when false: + # re-enable this check + internalError(m.config, info, "no attached trace proc found") result = rope("NIM_NIL") proc genTypeInfoV2(m: BModule, t, origType: PType, name: Rope; info: TLineInfo) = diff --git a/compiler/liftdestructors.nim b/compiler/liftdestructors.nim index 377ba149a..9a91ec2e9 100644 --- a/compiler/liftdestructors.nim +++ b/compiler/liftdestructors.nim @@ -484,10 +484,10 @@ proc atomicRefOp(c: var TLiftCtx; t: PType; body, x, y: PNode) = if isFinal(elemType): let typInfo = genBuiltin(c.g, mGetTypeInfo, "getTypeInfo", newNodeIT(nkType, x.info, elemType)) typInfo.typ = getSysType(c.g, c.info, tyPointer) - body.add callCodegenProc(c.g, "nimTraceRef", c.info, x, typInfo, y) + body.add callCodegenProc(c.g, "nimTraceRef", c.info, genAddrOf(x), typInfo, y) else: # If the ref is polymorphic we have to account for this - body.add callCodegenProc(c.g, "nimTraceRefDyn", c.info, x, y) + body.add callCodegenProc(c.g, "nimTraceRefDyn", c.info, genAddrOf(x), y) of attachedDispose: # this is crucial! dispose is like =destroy but we don't follow refs # as that is dealt within the cycle collector. @@ -530,7 +530,7 @@ proc atomicClosureOp(c: var TLiftCtx; t: PType; body, x, y: PNode) = body.add genIf(c, cond, actions) of attachedDeepCopy: assert(false, "cannot happen") of attachedTrace: - body.add callCodegenProc(c.g, "nimTraceRefDyn", c.info, xenv, y) + body.add callCodegenProc(c.g, "nimTraceRefDyn", c.info, genAddrOf(xenv), y) of attachedDispose: # this is crucial! dispose is like =destroy but we don't follow refs # as that is dealt within the cycle collector. @@ -778,7 +778,6 @@ proc produceSym(g: ModuleGraph; c: PContext; typ: PType; kind: TTypeAttachedOp; # register this operation already: typ.attachedOps[kind] = result - if kind == attachedSink and typ.attachedOps[attachedDestructor] != nil and sfOverriden in typ.attachedOps[attachedDestructor].flags: ## compiler can use a combination of `=destroy` and memCopy for sink op diff --git a/compiler/lineinfos.nim b/compiler/lineinfos.nim index 680b193f9..f7f3b7706 100644 --- a/compiler/lineinfos.nim +++ b/compiler/lineinfos.nim @@ -36,7 +36,7 @@ type warnUnusedImportX, warnInheritFromException, warnEachIdentIsTuple, - warnProveInit, warnProveField, warnProveIndex, + warnProveInit, warnProveField, warnProveIndex, warnStaticIndexCheck, warnGcUnsafe, warnGcUnsafe2, warnUninit, warnGcMem, warnDestructor, warnLockLevel, warnResultShadowed, warnInconsistentSpacing, warnCaseTransition, warnCycleCreated, warnUser, diff --git a/compiler/sempass2.nim b/compiler/sempass2.nim index 5d4ad658c..d5514d8d1 100644 --- a/compiler/sempass2.nim +++ b/compiler/sempass2.nim @@ -696,8 +696,16 @@ proc checkRange(c: PEffects; value: PNode; typ: PType) = checkLe(c, value, highBound) proc createTypeBoundOps(tracked: PEffects, typ: PType; info: TLineInfo) = + if typ == nil: return + let realType = typ.skipTypes(abstractInst) + when false: + # XXX fix this in liftdestructors instead + if realType.kind == tyRef and + optSeqDestructors in tracked.config.globalOptions: + createTypeBoundOps(tracked.graph, tracked.c, realType.lastSon, info) + createTypeBoundOps(tracked.graph, tracked.c, typ, info) - if (typ != nil and tfHasAsgn in typ.flags) or + if (tfHasAsgn in typ.flags) or optSeqDestructors in tracked.config.globalOptions: tracked.owner.flags.incl sfInjectDestructors diff --git a/lib/pure/asyncfutures.nim b/lib/pure/asyncfutures.nim index 7aac192d2..236a829e3 100644 --- a/lib/pure/asyncfutures.nim +++ b/lib/pure/asyncfutures.nim @@ -382,7 +382,7 @@ proc read*[T](future: Future[T] | FutureVar[T]): T = injectStacktrace(fut) raise fut.error when T isnot void: - return fut.value + result = fut.value else: # TODO: Make a custom exception type for this? raise newException(ValueError, "Future still in progress.") diff --git a/lib/system/cyclebreaker.nim b/lib/system/cyclebreaker.nim new file mode 100644 index 000000000..e036acb53 --- /dev/null +++ b/lib/system/cyclebreaker.nim @@ -0,0 +1,227 @@ +# +# +# Nim's Runtime Library +# (c) Copyright 2020 Andreas Rumpf +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +#[ +A Cycle breaker for Nim +----------------------- + +Instead of "collecting" cycles with all of its pitfalls we will break cycles. +We exploit that every 'ref' can be 'nil' for this and so get away without +a distinction between weak and strong pointers. The required runtime +mechanisms are the same though: We need to be able to traverse the graph. +This design has the tremendous benefit that it doesn't require a dedicated +'rawDispose' operation and that it plays well with Nim's cost model. +The cost of freeing a subgraph with cycles is 2 * N rather than N, that's all. + +Cycles do not have to be prepared via .acyclic, there are not multiple +pointless traversals, only a single proc, `breakCycles` is exposed as a +separate module. + +Algorithm +--------- + +We traverse the graph and notice the nodes we've already traversed. If we +marked the node already, we set the pointer that leads to this node to 'nil' +and decrement the reference count of the cell we pointed at. + +We notice that multiple paths to the same object do not mean +we found a cycle, it only means the node is shared. + + + a -------> b <----- c + | ^ ^ + +----------+ | + | | + +-------------------+ + +If we simply remove all links to already processed nodes we end up with: + + a -------> b c + | ^ + + | + | | + +-------------------+ + +That seems acceptable, no leak is produced. This implies that the standard +depth-first traversal suffices. + +]# +const + colGreen = 0b000 + colYellow = 0b001 + colRed = 0b010 + rcShift = 3 # shift by rcShift to get the reference counter + colorMask = 0b011 + +type + TraceProc = proc (p, env: pointer) {.nimcall, benign.} + DisposeProc = proc (p: pointer) {.nimcall, benign.} + +template color(c): untyped = c.rc and colorMask +template setColor(c, col) = + c.rc = c.rc and not colorMask or col + +proc nimIncRefCyclic(p: pointer) {.compilerRtl, inl.} = + let h = head(p) + inc h.rc, rcIncrement + +type + CellTuple = (ptr pointer, PNimType) + CellArray = ptr UncheckedArray[CellTuple] + CellSeq = object + len, cap: int + d: CellArray + + GcEnv = object + traceStack: CellSeq + +# ------------------- cell seq handling -------------------------------------- + +proc add(s: var CellSeq, c: ptr pointer; t: PNimType) {.inline.} = + if s.len >= s.cap: + s.cap = s.cap * 3 div 2 + when defined(useMalloc): + var d = cast[CellArray](c_malloc(uint(s.cap * sizeof(CellTuple)))) + else: + var d = cast[CellArray](alloc(s.cap * sizeof(CellTuple))) + copyMem(d, s.d, s.len * sizeof(CellTuple)) + when defined(useMalloc): + c_free(s.d) + else: + dealloc(s.d) + s.d = d + # XXX: realloc? + s.d[s.len] = (c, t) + inc(s.len) + +proc init(s: var CellSeq, cap: int = 1024) = + s.len = 0 + s.cap = cap + when defined(useMalloc): + s.d = cast[CellArray](c_malloc(uint(s.cap * sizeof(CellTuple)))) + else: + s.d = cast[CellArray](alloc(s.cap * sizeof(CellTuple))) + +proc deinit(s: var CellSeq) = + when defined(useMalloc): + c_free(s.d) + else: + dealloc(s.d) + s.d = nil + s.len = 0 + s.cap = 0 + +proc pop(s: var CellSeq): (ptr pointer, PNimType) = + result = s.d[s.len-1] + dec s.len + +# ---------------------------------------------------------------------------- + +proc trace(p: pointer; desc: PNimType; j: var GcEnv) {.inline.} = + when false: + cprintf("[Trace] desc: %p %p\n", desc, p) + cprintf("[Trace] trace: %p\n", desc.traceImpl) + if desc.traceImpl != nil: + cast[TraceProc](desc.traceImpl)(p, addr(j)) + +proc nimTraceRef(q: pointer; desc: PNimType; env: pointer) {.compilerRtl.} = + let p = cast[ptr pointer](q) + when traceCollector: + cprintf("[Trace] raw: %p\n", p) + cprintf("[Trace] deref: %p\n", p[]) + if p[] != nil: + var j = cast[ptr GcEnv](env) + j.traceStack.add(p, desc) + +proc nimTraceRefDyn(q: pointer; env: pointer) {.compilerRtl.} = + let p = cast[ptr pointer](q) + when traceCollector: + cprintf("[TraceDyn] raw: %p\n", p) + cprintf("[TraceDyn] deref: %p\n", p[]) + if p[] != nil: + var j = cast[ptr GcEnv](env) + j.traceStack.add(p, cast[ptr PNimType](p[])[]) + +var markerGeneration: int + +proc breakCycles(s: Cell; desc: PNimType) = + let markerColor = if (markerGeneration and 1) == 0: colRed + else: colYellow + atomicInc markerGeneration + when traceCollector: + cprintf("[BreakCycles] starting: %p %s RC %ld trace proc %p\n", + s, desc.name, s.rc shr rcShift, desc.traceImpl) + + var j: GcEnv + init j.traceStack + s.setColor markerColor + trace(s +! sizeof(RefHeader), desc, j) + + while j.traceStack.len > 0: + let (u, desc) = j.traceStack.pop() + let p = u[] + let t = head(p) + if t.color != markerColor: + t.setColor markerColor + trace(p, desc, j) + when traceCollector: + cprintf("[BreakCycles] followed: %p RC %ld\n", t, t.rc shr rcShift) + else: + if (t.rc shr rcShift) > 0: + dec t.rc, rcIncrement + # mark as a link that the produced destructor does not have to follow: + u[] = nil + when traceCollector: + cprintf("[BreakCycles] niled out: %p RC %ld\n", t, t.rc shr rcShift) + else: + # anyhow as a link that the produced destructor does not have to follow: + u[] = nil + cprintf("[Bug] %p %s RC %ld\n", t, desc.name, t.rc shr rcShift) + deinit j.traceStack + +proc thinout*[T](x: ref T) {.inline.} = + ## turn the subgraph starting with `x` into its spanning tree by + ## `nil`'ing out any pointers that would harm the spanning tree + ## structure. Any back pointers that introduced cycles + ## and thus would keep the graph from being freed are `nil`'ed. + ## This is a form of cycle collection that works well with Nim's ARC + ## and its associated cost model. + proc getDynamicTypeInfo[T](x: T): PNimType {.magic: "GetTypeInfo", noSideEffect, locks: 0.} + + breakCycles(head(cast[pointer](x)), getDynamicTypeInfo(x[])) + +proc thinout*[T: proc](x: T) {.inline.} = + proc rawEnv[T: proc](x: T): pointer {.noSideEffect, inline.} = + {.emit: """ + `result` = `x`.ClE_0; + """.} + + let p = rawEnv(x) + breakCycles(head(p), cast[ptr PNimType](p)[]) + +proc nimDecRefIsLastCyclicDyn(p: pointer): bool {.compilerRtl, inl.} = + if p != nil: + var cell = head(p) + if (cell.rc and not rcMask) == 0: + result = true + #cprintf("[DESTROY] %p\n", p) + else: + dec cell.rc, rcIncrement + # According to Lins it's correct to do nothing else here. + #cprintf("[DeCREF] %p\n", p) + +proc nimDecRefIsLastCyclicStatic(p: pointer; desc: PNimType): bool {.compilerRtl, inl.} = + if p != nil: + var cell = head(p) + if (cell.rc and not rcMask) == 0: + result = true + #cprintf("[DESTROY] %p %s\n", p, desc.name) + else: + dec cell.rc, rcIncrement + #cprintf("[DeCREF] %p %s %ld\n", p, desc.name, cell.rc) diff --git a/lib/system/cyclicrefs_v2.nim b/lib/system/cyclicrefs_v2.nim index 4fbb4fc94..0dd669925 100644 --- a/lib/system/cyclicrefs_v2.nim +++ b/lib/system/cyclicrefs_v2.nim @@ -43,6 +43,7 @@ proc markCyclic*[T](x: ref T) {.inline.} = ## Experimental API. Do not use! let h = head(cast[pointer](x)) h.setColor colYellow + type CellTuple = (Cell, PNimType) CellArray = ptr UncheckedArray[CellTuple] @@ -153,18 +154,19 @@ proc scanGreen(s: Cell; desc: PNimType; j: var GcEnv) = when traceCollector: cprintf("[Cycle inc] %p %ld color %ld\n", t, t.rc shr rcShift, t.color) -proc nimTraceRef(p: pointer; desc: PNimType; env: pointer) {.compilerRtl.} = - if p != nil: - var t = head(p) +proc nimTraceRef(q: pointer; desc: PNimType; env: pointer) {.compilerRtl.} = + let p = cast[ptr pointer](q) + if p[] != nil: var j = cast[ptr GcEnv](env) + var t = head(p[]) j.traceStack.add(t, desc) -proc nimTraceRefDyn(p: pointer; env: pointer) {.compilerRtl.} = - if p != nil: - let desc = cast[ptr PNimType](p)[] - var t = head(p) +proc nimTraceRefDyn(q: pointer; env: pointer) {.compilerRtl.} = + let p = cast[ptr pointer](q) + if p[] != nil: var j = cast[ptr GcEnv](env) - j.traceStack.add(t, desc) + var t = head(p[]) + j.traceStack.add(t, cast[ptr PNimType](p[])[]) proc scan(s: Cell; desc: PNimType; j: var GcEnv) = when traceCollector: diff --git a/lib/system/refs_v2.nim b/lib/system/refs_v2.nim index f6f3ba01c..9527db1e3 100644 --- a/lib/system/refs_v2.nim +++ b/lib/system/refs_v2.nim @@ -70,7 +70,7 @@ proc nimNewObj(size: int): pointer {.compilerRtl.} = else: result = alloc0(s) +! sizeof(RefHeader) when traceCollector: - cprintf("[Allocated] %p\n", result -! sizeof(RefHeader)) + cprintf("[Allocated] %p result: %p\n", result -! sizeof(RefHeader), result) proc nimNewObjUninit(size: int): pointer {.compilerRtl.} = # Same as 'newNewObj' but do not initialize the memory to zero. @@ -87,7 +87,7 @@ proc nimNewObjUninit(size: int): pointer {.compilerRtl.} = orig.rc = 0 result = orig +! sizeof(RefHeader) when traceCollector: - cprintf("[Allocated] %p\n", result -! sizeof(RefHeader)) + cprintf("[Allocated] %p result: %p\n", result -! sizeof(RefHeader), result) proc nimDecWeakRef(p: pointer) {.compilerRtl, inl.} = dec head(p).rc, rcIncrement @@ -128,7 +128,10 @@ proc nimDestroyAndDispose(p: pointer) {.compilerRtl, raises: [].} = nimRawDispose(p) when defined(gcOrc): - include cyclicrefs_v2 + when defined(nimThinout): + include cyclebreaker + else: + include cyclicrefs_v2 proc nimDecRefIsLast(p: pointer): bool {.compilerRtl, inl.} = if p != nil: diff --git a/tests/arc/tasyncawait.nim b/tests/arc/tasyncawait.nim index 89e924104..6b5b301a6 100644 --- a/tests/arc/tasyncawait.nim +++ b/tests/arc/tasyncawait.nim @@ -1,5 +1,5 @@ discard """ - output: "5000" + outputsub: "result: 5000" cmd: "nim c --gc:arc $file" """ @@ -59,11 +59,16 @@ proc createServer(port: Port) {.async.} = while true: asyncCheck readMessages(await accept(server)) -asyncCheck createServer(Port(10335)) -asyncCheck launchSwarm(Port(10335)) -while true: - poll() - if clientCount == swarmSize: break +proc main = + asyncCheck createServer(Port(10335)) + asyncCheck launchSwarm(Port(10335)) + while true: + poll() + if clientCount == swarmSize: break + +let mem = getOccupiedMem() +main() assert msgCount == swarmSize * messagesToSend -echo msgCount +echo "result: ", msgCount +echo "memory: ", formatSize(getOccupiedMem() - mem) |