* - tour - touring some programming systems

diff options

author	elioat <elioat@tilde.institute>	2025-01-05 09:03:18 -0500
committer	elioat <elioat@tilde.institute>	2025-01-05 09:03:18 -0500
commit	96f437b1c5717dcb84e569095baa43dac4591d63 (patch)
tree	c71077d320e38a93c415ccf7b10f60bf1e13d146 /js/magic-bird/imgs/extracted-1688-map/MapParts/hills/28.png
parent	6a6f3b37c77a851abad21655a05707b747321beb (diff)
download	tour-96f437b1c5717dcb84e569095baa43dac4591d63.tar.gz

Diffstat (limited to 'js/magic-bird/imgs/extracted-1688-map/MapParts/hills/28.png')

0 files changed, 0 insertions, 0 deletions

153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232

494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569

852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968

# # # Nim's Runtime Library # (c) Copyright 2012 Andreas Rumpf # # See the file "copying.txt", included in this # distribution, for details about the copyright. # # Garbage Collector # # The basic algorithm is *Deferrent Reference Counting* with cycle detection. # This is achieved by combining a Deutsch-Bobrow garbage collector # together with Christoper's partial mark-sweep garbage collector. # # Special care has been taken to avoid recursion as far as possible to avoid # stack overflows when traversing deep datastructures. It is well-suited # for soft real time applications (like games). {.push profiler:off.} const CycleIncrease = 2 # is a multiplicative increase InitialCycleThreshold = 4*1024*1024 # X MB because cycle checking is slow ZctThreshold = 500 # we collect garbage if the ZCT's size # reaches this threshold # this seems to be a good value withRealTime = defined(useRealtimeGC) when withRealTime and not declared(getTicks): include "system/timers" when defined(memProfiler): proc nimProfile(requestedSize: int) const rcShift = 6 # the reference count is shifted so we can use # the least significat bits for additinal flags: rcAlive = 0b00000 # object is reachable. # color *black* in the original paper rcCycleCandidate = 0b00001 # possible root of a cycle. *purple* rcDecRefApplied = 0b00010 # the first dec-ref phase of the # collector was already applied to this # object. *gray* rcMaybeDead = 0b00011 # this object is a candidate for deletion # during the collect cycles algorithm. # *white*. rcReallyDead = 0b00100 # this is proved to be garbage rcRetiredBuffer = 0b00101 # this is a seq or string buffer that # was replaced by a resize operation. # see growObj for details rcColorMask = TRefCount(0b00111) rcZct = 0b01000 # already added to ZCT rcInCycleRoots = 0b10000 # already buffered as cycle candidate rcHasStackRef = 0b100000 # the object had a stack ref in the last # cycle collection rcMarkBit = rcHasStackRef # this is currently used for leak detection # when traceGC is on rcBufferedAnywhere = rcZct or rcInCycleRoots rcIncrement = 1 shl rcShift # don't touch the color bits const NewObjectsAreCycleRoots = true # the alternative is to use the old strategy of adding cycle roots # in incRef (in the compiler itself, this doesn't change much) IncRefRemovesCandidates = false # this is safe only if we can reliably track the fact that the object # has stack references. This could be easily done by adding another bit # to the refcount field and setting it up in unmarkStackAndRegisters. # The bit must also be set for new objects that are not rc1 and it must be # examined in the decref loop in collectCycles. # XXX: not implemented yet as tests didn't show any improvement from this MarkingSkipsAcyclicObjects = true # Acyclic objects can be safely ignored in the mark and scan phases, # because they cannot contribute to the internal count. # XXX: if we generate specialized `markCyclic` and `markAcyclic` # procs we can further optimize this as there won't be need for any # checks in the code MinimumStackMarking = false # Try to scan only the user stack and ignore the part of the stack # belonging to the GC itself. see setStackTop for further info. # XXX: still has problems in release mode in the compiler itself. # investigate how it affects growObj CollectCyclesStats = false type TWalkOp = enum waPush TFinalizer {.compilerproc.} = proc (self: pointer) {.nimcall.} # A ref type can have a finalizer that is called before the object's # storage is freed. TGcStat {.final, pure.} = object stackScans: int # number of performed stack scans (for statistics) cycleCollections: int # number of performed full collections maxThreshold: int # max threshold that has been set maxStackSize: int # max stack size maxStackCells: int # max stack cells in ``decStack`` cycleTableSize: int # max entries in cycle table maxPause: int64 # max measured GC pause in nanoseconds TGcHeap {.final, pure.} = object # this contains the zero count and # non-zero count table stackBottom: pointer stackTop: pointer cycleThreshold: int zct: TCellSeq # the zero count table decStack: TCellSeq # cells in the stack that are to decref again cycleRoots: TCellSeq tempStack: TCellSeq # temporary stack for recursion elimination freeStack: TCellSeq # objects ready to be freed recGcLock: int # prevent recursion via finalizers; no thread lock cycleRootsTrimIdx: int # Trimming is a light-weight collection of the # cycle roots table that uses a cheap linear scan # to find only possitively dead objects. # One strategy is to perform it only for new objects # allocated between the invocations of CollectZCT. # This index indicates the start of the range of # such new objects within the table. when withRealTime: maxPause: TNanos # max allowed pause in nanoseconds; active if > 0 region: TMemRegion # garbage collected region stat: TGcStat var gch* {.rtlThreadVar.}: TGcHeap when not defined(useNimRtl): InstantiateForRegion(gch.region) template acquire(gch: TGcHeap) = when hasThreadSupport and hasSharedHeap: AcquireSys(HeapLock) template release(gch: TGcHeap) = when hasThreadSupport and hasSharedHeap: releaseSys(HeapLock) template setColor(c: PCell, color) = c.refcount = (c.refcount and not rcColorMask) or color template color(c: PCell): expr = c.refcount and rcColorMask template isBitDown(c: PCell, bit): expr = (c.refcount and bit) == 0 template isBitUp(c: PCell, bit): expr = (c.refcount and bit) != 0 template setBit(c: PCell, bit): expr = c.refcount = c.refcount or bit template isDead(c: Pcell): expr = c.isBitUp(rcReallyDead) # also covers rcRetiredBuffer template clearBit(c: PCell, bit): expr = c.refcount = c.refcount and (not TRefCount(bit)) when debugGC: var gcCollectionIdx = 0 proc colorStr(c: PCell): cstring = let color = c.color case color of rcAlive: return "alive" of rcMaybeDead: return "maybedead" of rcCycleCandidate: return "candidate" of rcDecRefApplied: return "marked" of rcRetiredBuffer: return "retired" of rcReallyDead: return "dead" else: return "unknown?" proc inCycleRootsStr(c: PCell): cstring = if c.isBitUp(rcInCycleRoots): result = "cycleroot" else: result = "" proc inZctStr(c: PCell): cstring = if c.isBitUp(rcZct): result = "zct" else: result = "" proc writeCell*(msg: CString, c: PCell, force = false) = var kind = -1 if c.typ != nil: kind = ord(c.typ.kind) when trackAllocationSource: c_fprintf(c_stdout, "[GC %d] %s: %p %d rc=%ld %s %s %s from %s(%ld)\n", gcCollectionIdx, msg, c, kind, c.refcount shr rcShift, c.colorStr, c.inCycleRootsStr, c.inZctStr, c.filename, c.line) else: c_fprintf(c_stdout, "[GC] %s: %p %d rc=%ld\n", msg, c, kind, c.refcount shr rcShift) proc addZCT(zct: var TCellSeq, c: PCell) {.noinline.} = if c.isBitDown(rcZct): c.setBit rcZct zct.add c template setStackTop(gch) = # This must be called immediately after we enter the GC code # to minimize the size of the scanned stack. The stack consumed # by the GC procs may amount to 200-400 bytes depending on the # build settings and this contributes to false-positives # in the conservative stack marking when MinimumStackMarking: var stackTop {.volatile.}: pointer gch.stackTop = addr(stackTop) template addCycleRoot(cycleRoots: var TCellSeq, c: PCell) = if c.color != rcCycleCandidate: c.setColor rcCycleCandidate # the object may be buffered already. for example, consider: # decref; incref; decref if c.isBitDown(rcInCycleRoots): c.setBit rcInCycleRoots cycleRoots.add c proc cellToUsr(cell: PCell): pointer {.inline.} = # convert object (=pointer to refcount) to pointer to userdata result = cast[pointer](cast[TAddress](cell)+%TAddress(sizeof(TCell))) proc usrToCell*(usr: pointer): PCell {.inline.} = # convert pointer to userdata to object (=pointer to refcount) result = cast[PCell](cast[TAddress](usr)-%TAddress(sizeof(TCell))) proc canbeCycleRoot(c: PCell): bool {.inline.} = result = ntfAcyclic notin c.typ.flags proc extGetCellType(c: pointer): PNimType {.compilerproc.} = # used for code generation concerning debugging result = usrToCell(c).typ proc internRefcount(p: pointer): int {.exportc: "getRefcount".} = result = int(usrToCell(p).refcount) shr rcShift # this that has to equals zero, otherwise we have to round up UnitsPerPage: when BitsPerPage mod (sizeof(int)*8) != 0: {.error: "(BitsPerPage mod BitsPerUnit) should be zero!".} # forward declarations: proc collectCT(gch: var TGcHeap) proc IsOnStack*(p: pointer): bool {.noinline.} proc forAllChildren(cell: PCell, op: TWalkOp) proc doOperation(p: pointer, op: TWalkOp) proc forAllChildrenAux(dest: Pointer, mt: PNimType, op: TWalkOp) # we need the prototype here for debugging purposes proc prepareDealloc(cell: PCell) = if cell.typ.finalizer != nil: # the finalizer could invoke something that # allocates memory; this could trigger a garbage # collection. Since we are already collecting we # prevend recursive entering here by a lock. # XXX: we should set the cell's children to nil! inc(gch.recGcLock) (cast[TFinalizer](cell.typ.finalizer))(cellToUsr(cell)) dec(gch.recGcLock) when traceGC: # traceGC is a special switch to enable extensive debugging type TCellState = enum csAllocated, csFreed 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[csFreed], c) # writecell("allocated", c) of csFreed: if c in states[csFreed]: writeCell("attempt to free a cell twice", c) sysAssert(false, "traceCell 2") if c notin states[csAllocated]: writeCell("attempt to free not an allocated cell", c) sysAssert(false, "traceCell 3") excl(states[csAllocated], c) # writecell("freed", c) incl(states[state], c) proc computeCellWeight(c: PCell): int = var x: TCellSet x.init let startLen = gch.tempStack.len c.forAllChildren waPush while startLen != gch.tempStack.len: dec gch.tempStack.len var c = gch.tempStack.d[gch.tempStack.len] if c in states[csFreed]: continue inc result if c notin x: x.incl c c.forAllChildren waPush template markChildrenRec(cell) = let startLen = gch.tempStack.len cell.forAllChildren waPush let isMarked = cell.isBitUp(rcMarkBit) while startLen != gch.tempStack.len: dec gch.tempStack.len var c = gch.tempStack.d[gch.tempStack.len] if c in states[csFreed]: continue if c.isBitDown(rcMarkBit): c.setBit rcMarkBit c.forAllChildren waPush if c.isBitUp(rcMarkBit) and not isMarked: writecell("cyclic cell", cell) cprintf "Weight %d\n", cell.computeCellWeight proc writeLeakage(onlyRoots: bool) = if onlyRoots: for c in elements(states[csAllocated]): if c notin states[csFreed]: markChildrenRec(c) var f = 0 var a = 0 for c in elements(states[csAllocated]): inc a if c in states[csFreed]: inc f elif c.isBitDown(rcMarkBit): writeCell("leak", c) cprintf "Weight %d\n", c.computeCellWeight cfprintf(cstdout, "Allocations: %ld; freed: %ld\n", a, f) template gcTrace(cell, state: expr): stmt {.immediate.} = when logGC: writeCell($state, cell) when traceGC: traceCell(cell, state) template WithHeapLock(blk: stmt): stmt = when hasThreadSupport and hasSharedHeap: AcquireSys(HeapLock) blk when hasThreadSupport and hasSharedHeap: ReleaseSys(HeapLock) proc rtlAddCycleRoot(c: PCell) {.rtl, inl.} = # we MUST access gch as a global here, because this crosses DLL boundaries! WithHeapLock: addCycleRoot(gch.cycleRoots, c) proc rtlAddZCT(c: PCell) {.rtl, inl.} = # we MUST access gch as a global here, because this crosses DLL boundaries! WithHeapLock: addZCT(gch.zct, c) type TCyclicMode = enum Cyclic, Acyclic, MaybeCyclic TReleaseType = enum AddToZTC FreeImmediately THeapType = enum LocalHeap SharedHeap template `++` (rc: TRefCount, heapType: THeapType): stmt = when heapType == SharedHeap: discard atomicInc(rc, rcIncrement) else: inc rc, rcIncrement template `--`(rc: TRefCount): expr = dec rc, rcIncrement rc <% rcIncrement template `--` (rc: TRefCount, heapType: THeapType): expr = (when heapType == SharedHeap: atomicDec(rc, rcIncrement) <% rcIncrement else: --rc) template doDecRef(cc: PCell, heapType = LocalHeap, cycleFlag = MaybeCyclic): stmt = var c = cc sysAssert(isAllocatedPtr(gch.region, c), "decRef: interiorPtr") # XXX: move this elesewhere sysAssert(c.refcount >=% rcIncrement, "decRef") if c.refcount--(heapType): # this is the last reference from the heap # add to a zero-count-table that will be matched against stack pointers rtlAddZCT(c) else: when cycleFlag != Acyclic: if cycleFlag == Cyclic or canBeCycleRoot(c): # a cycle may have been broken rtlAddCycleRoot(c) template doIncRef(cc: PCell, heapType = LocalHeap, cycleFlag = MaybeCyclic): stmt = var c = cc c.refcount++(heapType) when cycleFlag != Acyclic: when NewObjectsAreCycleRoots: if canbeCycleRoot(c): addCycleRoot(gch.cycleRoots, c) elif IncRefRemovesCandidates: c.setColor rcAlive # XXX: this is not really atomic enough! proc nimGCref(p: pointer) {.compilerProc, inline.} = doIncRef(usrToCell(p)) proc nimGCunref(p: pointer) {.compilerProc, inline.} = doDecRef(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") if c.refcount--(LocalHeap): rtlAddZCT(c) sysAssert(allocInv(gch.region), "end nimGCunrefNoCycle 2") sysAssert(allocInv(gch.region), "end nimGCunrefNoCycle 5") template doAsgnRef(dest: ppointer, src: pointer, heapType = LocalHeap, cycleFlag = MaybeCyclic): stmt = sysAssert(not isOnStack(dest), "asgnRef") # BUGFIX: first incRef then decRef! if src != nil: doIncRef(usrToCell(src), heapType, cycleFlag) if dest[] != nil: doDecRef(usrToCell(dest[]), heapType, cycleFlag) dest[] = src proc asgnRef(dest: ppointer, src: pointer) {.compilerProc, inline.} = # the code generator calls this proc! doAsgnRef(dest, src, LocalHeap, MaybeCyclic) proc asgnRefNoCycle(dest: ppointer, src: pointer) {.compilerProc, inline.} = # the code generator calls this proc if it is known at compile time that no # cycle is possible. doAsgnRef(dest, src, LocalHeap, Acyclic) proc unsureAsgnRef(dest: ppointer, src: pointer) {.compilerProc.} = # unsureAsgnRef updates the reference counters only if dest is not on the # stack. It is used by the code generator if it cannot decide wether a # reference is in the stack or not (this can happen for var parameters). if not IsOnStack(dest): if src != nil: doIncRef(usrToCell(src)) # XXX we must detect a shared heap here # better idea may be to just eliminate the need for unsureAsgnRef # # XXX finally use assembler for the stack checking instead! # the test for '!= nil' is correct, but I got tired of the segfaults # resulting from the crappy stack checking: if cast[int](dest[]) >=% PageSize: doDecRef(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") dest[] = src when hasThreadSupport and hasSharedHeap: # shared heap version of the above procs proc asgnRefSh(dest: ppointer, src: pointer) {.compilerProc, inline.} = doAsgnRef(dest, src, SharedHeap, MaybeCyclic) proc asgnRefNoCycleSh(dest: ppointer, src: pointer) {.compilerProc, inline.} = doAsgnRef(dest, src, SharedHeap, Acyclic) proc initGC() = when not defined(useNimRtl): when traceGC: for i in low(TCellState)..high(TCellState): Init(states[i]) gch.cycleThreshold = InitialCycleThreshold gch.stat.stackScans = 0 gch.stat.cycleCollections = 0 gch.stat.maxThreshold = 0 gch.stat.maxStackSize = 0 gch.stat.maxStackCells = 0 gch.stat.cycleTableSize = 0 # init the rt init(gch.zct) init(gch.tempStack) init(gch.freeStack) Init(gch.cycleRoots) Init(gch.decStack) proc forAllSlotsAux(dest: pointer, n: ptr TNimNode, op: TWalkOp) = var d = cast[TAddress](dest) case n.kind of nkSlot: forAllChildrenAux(cast[pointer](d +% n.offset), n.typ, op) of nkList: for i in 0..n.len-1: # inlined for speed if n.sons[i].kind == nkSlot: if n.sons[i].typ.kind in {tyRef, tyString, tySequence}: doOperation(cast[ppointer](d +% n.sons[i].offset)[], op) else: forAllChildrenAux(cast[pointer](d +% n.sons[i].offset), n.sons[i].typ, op) else: forAllSlotsAux(dest, n.sons[i], op) of nkCase: var m = selectBranch(dest, n) if m != nil: forAllSlotsAux(dest, m, op) of nkNone: sysAssert(false, "forAllSlotsAux") proc forAllChildrenAux(dest: Pointer, mt: PNimType, op: TWalkOp) = var d = cast[TAddress](dest) if dest == nil: return # nothing to do if ntfNoRefs notin mt.flags: case mt.Kind of tyRef, tyString, tySequence: # leaf: doOperation(cast[ppointer](d)[], op) of tyObject, tyTuple: forAllSlotsAux(dest, mt.node, op) of tyArray, tyArrayConstr, tyOpenArray: for i in 0..(mt.size div mt.base.size)-1: forAllChildrenAux(cast[pointer](d +% i *% mt.base.size), mt.base, op) 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" let marker = cell.typ.marker if marker != nil: marker(cellToUsr(cell), op.int) else: case cell.typ.Kind of tyRef: # common case forAllChildrenAux(cellToUsr(cell), cell.typ.base, op) of tySequence: var d = cast[TAddress](cellToUsr(cell)) var s = cast[PGenericSeq](d) if s != nil: let baseAddr = d +% GenericSeqSize for i in 0..s.len-1: forAllChildrenAux(cast[pointer](baseAddr +% i *% cell.typ.base.size), cell.typ.base, op) else: nil proc addNewObjToZCT(res: PCell, gch: var TGcHeap) {.inline.} = # we check the last 8 entries (cache line) for a slot that could be reused. # In 63% of all cases we succeed here! But we have to optimize the heck # out of this small linear search so that ``newObj`` is not slowed down. # # Slots to try cache hit # 1 32% # 4 59% # 8 63% # 16 66% # all slots 68% var L = gch.zct.len var d = gch.zct.d when true: # loop unrolled for performance: template replaceZctEntry(i: expr) = c = d[i] if c.refcount >=% rcIncrement: c.clearBit(rcZct) d[i] = res return if L > 8: var c: PCell replaceZctEntry(L-1) replaceZctEntry(L-2) replaceZctEntry(L-3) replaceZctEntry(L-4) replaceZctEntry(L-5) replaceZctEntry(L-6) replaceZctEntry(L-7) replaceZctEntry(L-8) add(gch.zct, res) else: d[L] = res inc(gch.zct.len) else: for i in countdown(L-1, max(0, L-8)): var c = d[i] if c.refcount >=% rcIncrement: c.clearBit(rcZct) d[i] = res return add(gch.zct, res) proc rawNewObj(typ: PNimType, size: int, gch: var TGcHeap, rc1: bool): pointer = # generates a new object and sets its reference counter to 0 acquire(gch) sysAssert(allocInv(gch.region), "rawNewObj begin") sysAssert(typ.kind in {tyRef, tyString, tySequence}, "newObj: 1") collectCT(gch) sysAssert(allocInv(gch.region), "rawNewObj after collect") var res = cast[PCell](rawAlloc(gch.region, size + sizeof(TCell))) sysAssert(allocInv(gch.region), "rawNewObj after rawAlloc") sysAssert((cast[TAddress](res) and (MemAlign-1)) == 0, "newObj: 2") res.typ = typ when trackAllocationSource and not hasThreadSupport: if framePtr != nil and framePtr.prev != nil and framePtr.prev.prev != nil: res.filename = framePtr.prev.prev.filename res.line = framePtr.prev.prev.line else: res.filename = "nofile" if rc1: res.refcount = rcIncrement # refcount is 1 else: # its refcount is zero, so add it to the ZCT: res.refcount = rcZct addNewObjToZCT(res, gch) if NewObjectsAreCycleRoots and canBeCycleRoot(res): res.setBit(rcInCycleRoots) res.setColor rcCycleCandidate gch.cycleRoots.add res sysAssert(isAllocatedPtr(gch.region, res), "newObj: 3") when logGC: writeCell("new cell", res) gcTrace(res, csAllocated) release(gch) result = cellToUsr(res) zeroMem(result, size) when defined(memProfiler): nimProfile(size) sysAssert(allocInv(gch.region), "rawNewObj end") {.pop.} proc freeCell(gch: var TGcHeap, c: PCell) = # prepareDealloc(c) gcTrace(c, csFreed) when reallyDealloc: rawDealloc(gch.region, c) else: sysAssert(c.typ != nil, "collectCycles") zeroMem(c, sizeof(TCell)) template eraseAt(cells: var TCellSeq, at: int): stmt = cells.d[at] = cells.d[cells.len - 1] dec cells.len template trimAt(roots: var TCellSeq, at: int): stmt = # This will remove a cycle root candidate during trimming. # a candidate is removed either because it received a refup and # it's no longer a candidate or because it received further refdowns # and now it's dead for sure. let c = roots.d[at] c.clearBit(rcInCycleRoots) roots.eraseAt(at) if c.isBitUp(rcReallyDead) and c.refcount <% rcIncrement: # This case covers both dead objects and retired buffers # That's why we must also check the refcount (it may be # kept possitive by stack references). freeCell(gch, c) proc newObj(typ: PNimType, size: int): pointer {.compilerRtl.} = setStackTop(gch) result = rawNewObj(typ, size, gch, false) proc newSeq(typ: PNimType, len: int): pointer {.compilerRtl.} = setStackTop(gch) # `rawNewObj` already uses locks, so no need for them here. let size = addInt(mulInt(len, typ.base.size), GenericSeqSize) result = rawNewObj(typ, size, gch, false) cast[PGenericSeq](result).len = len cast[PGenericSeq](result).reserved = len proc newObjRC1(typ: PNimType, size: int): pointer {.compilerRtl.} = setStackTop(gch) result = rawNewObj(typ, size, gch, true) proc newSeqRC1(typ: PNimType, len: int): pointer {.compilerRtl.} = setStackTop(gch) let size = addInt(mulInt(len, typ.base.size), GenericSeqSize) result = rawNewObj(typ, size, gch, true) cast[PGenericSeq](result).len = len cast[PGenericSeq](result).reserved = len proc growObj(old: pointer, newsize: int, gch: var TGcHeap): pointer = acquire(gch) collectCT(gch) var ol = usrToCell(old) sysAssert(ol.typ != nil, "growObj: 1") sysAssert(ol.typ.kind in {tyString, tySequence}, "growObj: 2") sysAssert(allocInv(gch.region), "growObj begin") var res = cast[PCell](rawAlloc(gch.region, newsize + sizeof(TCell))) var elemSize = if ol.typ.kind != tyString: ol.typ.base.size else: 1 var oldsize = cast[PGenericSeq](old).len*elemSize + GenericSeqSize # XXX: This should happen outside # call user-defined move code # call user-defined default constructor copyMem(res, ol, oldsize + sizeof(TCell)) zeroMem(cast[pointer](cast[TAddress](res)+% oldsize +% sizeof(TCell)), newsize-oldsize) sysAssert((cast[TAddress](res) and (MemAlign-1)) == 0, "growObj: 3") sysAssert(res.refcount shr rcShift <=% 1, "growObj: 4") when false: if ol.isBitUp(rcZct): var j = gch.zct.len-1 var d = gch.zct.d while j >= 0: if d[j] == ol: d[j] = res break dec(j) if ol.isBitUp(rcInCycleRoots): for i in 0 .. <gch.cycleRoots.len: if gch.cycleRoots.d[i] == ol: eraseAt(gch.cycleRoots, i) freeCell(gch, ol) else: # the new buffer inherits the GC state of the old one if res.isBitUp(rcZct): gch.zct.add res if res.isBitUp(rcInCycleRoots): gch.cycleRoots.add res # Pay attention to what's going on here! We're not releasing the old memory. # This is because at this point there may be an interior pointer pointing # into this buffer somewhere on the stack (due to `var` parameters now and # and `let` and `var:var` stack locations in the future). # We'll release the memory in the next GC cycle. If we release it here, # we cannot guarantee that no memory will be corrupted when only safe # language features are used. Accessing the memory after the seq/string # has been invalidated may still result in logic errors in the user code. # We may improve on that by protecting the page in debug builds or # by providing a warning when we detect a stack pointer into it. let bufferFlags = ol.refcount and rcBufferedAnywhere if bufferFlags == 0: # we need this in order to collect it safely later ol.refcount = rcRetiredBuffer or rcZct gch.zct.add ol else: ol.refcount = rcRetiredBuffer or bufferFlags when logGC: writeCell("growObj old cell", ol) writeCell("growObj new cell", res) gcTrace(res, csAllocated) release(gch) result = cellToUsr(res) sysAssert(allocInv(gch.region), "growObj end") when defined(memProfiler): nimProfile(newsize-oldsize) proc growObj(old: pointer, newsize: int): pointer {.rtl.} = setStackTop(gch) result = growObj(old, newsize, gch) {.push profiler:off.} # ---------------- cycle collector ------------------------------------------- proc doOperation(p: pointer, op: TWalkOp) = if p == nil: return var c: PCell = usrToCell(p) sysAssert(c != nil, "doOperation: 1") gch.tempStack.add c proc nimGCvisit(d: pointer, op: int) {.compilerRtl.} = doOperation(d, TWalkOp(op)) type TRecursionType = enum FromChildren, FromRoot proc CollectZCT(gch: var TGcHeap): bool template pseudoRecursion(typ: TRecursionType, body: stmt): stmt = # proc trimCycleRoots(gch: var TGcHeap, startIdx = gch.cycleRootsTrimIdx) = var i = startIdx while i < gch.cycleRoots.len: if gch.cycleRoots.d[i].color != rcCycleCandidate: gch.cycleRoots.trimAt i else: inc i gch.cycleRootsTrimIdx = gch.cycleRoots.len # we now use a much simpler and non-recursive algorithm for cycle removal proc collectCycles(gch: var TGcHeap) = if gch.cycleRoots.len == 0: return gch.stat.cycleTableSize = max(gch.stat.cycleTableSize, gch.cycleRoots.len) when CollectCyclesStats: let l0 = gch.cycleRoots.len let tStart = getTicks() var decrefs = 0 increfs = 0 collected = 0 maybedeads = 0 template ignoreObject(c: PCell): expr = # This controls which objects will be ignored in the mark and scan stages (when MarkingSkipsAcyclicObjects: not canbeCycleRoot(c) else: false) # not canbeCycleRoot(c) # false # c.isBitUp(rcHasStackRef) template earlyMarkAliveRec(cell) = let startLen = gch.tempStack.len cell.setColor rcAlive cell.forAllChildren waPush while startLen != gch.tempStack.len: dec gch.tempStack.len var c = gch.tempStack.d[gch.tempStack.len] if c.color != rcAlive: c.setColor rcAlive c.forAllChildren waPush template earlyMarkAlive(stackRoots) = # This marks all objects reachable from the stack as alive before any # of the other stages is executed. Such objects cannot be garbage and # they don't need to participate in the recursive decref/incref. for i in 0 .. <stackRoots.len: var c = stackRoots.d[i] # c.setBit rcHasStackRef earlyMarkAliveRec(c) earlyMarkAlive(gch.decStack) when CollectCyclesStats: let tAfterEarlyMarkAlive = getTicks() template recursiveDecRef(cell) = let startLen = gch.tempStack.len cell.setColor rcDecRefApplied cell.forAllChildren waPush while startLen != gch.tempStack.len: dec gch.tempStack.len var c = gch.tempStack.d[gch.tempStack.len] if ignoreObject(c): continue sysAssert(c.refcount >=% rcIncrement, "recursive dec ref") dec c.refcount, rcIncrement inc decrefs if c.color != rcDecRefApplied: c.setColor rcDecRefApplied c.forAllChildren waPush template markRoots(roots) = var i = 0 while i < roots.len: if roots.d[i].color == rcCycleCandidate: recursiveDecRef(roots.d[i]) inc i else: roots.trimAt i markRoots(gch.cycleRoots) when CollectCyclesStats: let tAfterMark = getTicks() c_printf "COLLECT CYCLES %d: %d/%d\n", gcCollectionIdx, gch.cycleRoots.len, l0 template recursiveMarkAlive(cell) = let startLen = gch.tempStack.len cell.setColor rcAlive cell.forAllChildren waPush while startLen != gch.tempStack.len: dec gch.tempStack.len var c = gch.tempStack.d[gch.tempStack.len] if ignoreObject(c): continue inc c.refcount, rcIncrement inc increfs if c.color != rcAlive: c.setColor rcAlive c.forAllChildren waPush template scanRoots(roots) = for i in 0 .. <roots.len: let startLen = gch.tempStack.len gch.tempStack.add roots.d[i] while startLen != gch.tempStack.len: dec gch.tempStack.len var c = gch.tempStack.d[gch.tempStack.len] if ignoreObject(c): continue if c.color == rcDecRefApplied: if c.refcount >=% rcIncrement: recursiveMarkAlive(c) else: # note that this is not necessarily the ultimate # destiny of the object. we may still mark it alive # later if we encounter another node from where it's # reachable. c.setColor rcMaybeDead inc maybedeads c.forAllChildren waPush scanRoots(gch.cycleRoots) when CollectCyclesStats: let tAfterScan = getTicks() template collectDead(roots) = for i in 0 .. <roots.len: var c = roots.d[i] c.clearBit(rcInCycleRoots) let startLen = gch.tempStack.len gch.tempStack.add c while startLen != gch.tempStack.len: dec gch.tempStack.len var c = gch.tempStack.d[gch.tempStack.len] when MarkingSkipsAcyclicObjects: if not canbeCycleRoot(c): # This is an acyclic object reachable from a dead cyclic object # We must do a normal decref here that may add the acyclic object # to the ZCT doDecRef(c, LocalHeap, Cyclic) continue if c.color == rcMaybeDead and not c.isBitUp(rcInCycleRoots): c.setColor(rcReallyDead) inc collected c.forAllChildren waPush # we need to postpone the actual deallocation in order to allow # the finalizers to run while the data structures are still intact gch.freeStack.add c prepareDealloc(c) for i in 0 .. <gch.freeStack.len: freeCell(gch, gch.freeStack.d[i]) collectDead(gch.cycleRoots) when CollectCyclesStats: let tFinal = getTicks() cprintf "times:\n early mark alive: %d ms\n mark: %d ms\n scan: %d ms\n collect: %d ms\n decrefs: %d\n increfs: %d\n marked dead: %d\n collected: %d\n", (tAfterEarlyMarkAlive - tStart) div 1_000_000, (tAfterMark - tAfterEarlyMarkAlive) div 1_000_000, (tAfterScan - tAfterMark) div 1_000_000, (tFinal - tAfterScan) div 1_000_000, decrefs, increfs, maybedeads, collected Deinit(gch.cycleRoots) Init(gch.cycleRoots) Deinit(gch.freeStack) Init(gch.freeStack) when MarkingSkipsAcyclicObjects: # Collect the acyclic objects that became unreachable due to collected # cyclic objects. discard CollectZCT(gch) # CollectZCT may add new cycle candidates and we may decide to loop here # if gch.cycleRoots.len > 0: repeat var gcDebugging* = false var seqdbg* : proc (s: PGenericSeq) {.cdecl.} proc gcMark(gch: var TGcHeap, 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[TAddress](cell) if c >% PageSize: # fast check: does it look like a cell? var objStart = cast[PCell](interiorAllocatedPtr(gch.region, cell)) if objStart != nil: # mark the cell: if objStart.color != rcReallyDead: if gcDebugging: # writeCell("marking ", objStart) else: inc objStart.refcount, rcIncrement gch.decStack.add objStart else: # With incremental clean-up, objects spend some time # in various lists before being deallocated. # We just found a reference on the stack to an object, # which we have previously labeled as unreachable. # This is either a bug in the GC or a pure accidental # coincidence due to the conservative stack marking. when debugGC: # writeCell("marking dead object", objStart) when false: if isAllocatedPtr(gch.region, cell): sysAssert false, "allocated pointer but not interior?" # mark the cell: inc cell.refcount, rcIncrement add(gch.decStack, cell) sysAssert(allocInv(gch.region), "gcMark end") proc markThreadStacks(gch: var TGcHeap) = when hasThreadSupport and hasSharedHeap: {.error: "not fully implemented".} var it = threadList while it != nil: # mark registers: for i in 0 .. high(it.registers): gcMark(gch, it.registers[i]) var sp = cast[TAddress](it.stackBottom) var max = cast[TAddress](it.stackTop) # XXX stack direction? # XXX unroll this loop: while sp <=% max: gcMark(gch, cast[ppointer](sp)[]) sp = sp +% sizeof(pointer) it = it.next # ----------------- stack management -------------------------------------- # inspired from Smart Eiffel when defined(sparc): const stackIncreases = false elif defined(hppa) or defined(hp9000) or defined(hp9000s300) or defined(hp9000s700) or defined(hp9000s800) or defined(hp9000s820): const stackIncreases = true else: const stackIncreases = false when not defined(useNimRtl): {.push stack_trace: off.} proc setStackBottom(theStackBottom: pointer) = #c_fprintf(c_stdout, "stack bottom: %p;\n", theStackBottom) # the first init must be the one that defines the stack bottom: if gch.stackBottom == nil: gch.stackBottom = theStackBottom else: var a = cast[TAddress](theStackBottom) # and not PageMask - PageSize*2 var b = cast[TAddress](gch.stackBottom) #c_fprintf(c_stdout, "old: %p new: %p;\n",gch.stackBottom,theStackBottom) when stackIncreases: gch.stackBottom = cast[pointer](min(a, b)) else: gch.stackBottom = cast[pointer](max(a, b)) {.pop.} proc stackSize(): int {.noinline.} = var stackTop {.volatile.}: pointer result = abs(cast[int](addr(stackTop)) - cast[int](gch.stackBottom)) var jmpbufSize {.importc: "sizeof(jmp_buf)", nodecl.}: int # a little hack to get the size of a TJmpBuf in the generated C code # in a platform independant way when defined(sparc): # For SPARC architecture. proc isOnStack(p: pointer): bool = var stackTop {.volatile.}: pointer stackTop = addr(stackTop) var b = cast[TAddress](gch.stackBottom) var a = cast[TAddress](stackTop) var x = cast[TAddress](p) result = a <=% x and x <=% b proc markStackAndRegisters(gch: var TGcHeap) {.noinline, cdecl.} = when defined(sparcv9): asm """"flushw \n" """ else: asm """"ta 0x3 ! ST_FLUSH_WINDOWS\n" """ var max = gch.stackBottom sp: PPointer stackTop: array[0..1, pointer] sp = addr(stackTop[0]) # Addresses decrease as the stack grows. while sp <= max: gcMark(gch, sp[]) sp = cast[ppointer](cast[TAddress](sp) +% sizeof(pointer)) elif defined(ELATE): {.error: "stack marking code is to be written for this architecture".} elif stackIncreases: # --------------------------------------------------------------------------- # Generic code for architectures where addresses increase as the stack grows. # --------------------------------------------------------------------------- proc isOnStack(p: pointer): bool = var stackTop {.volatile.}: pointer stackTop = addr(stackTop) var a = cast[TAddress](gch.stackBottom) var b = cast[TAddress](stackTop) var x = cast[TAddress](p) result = a <=% x and x <=% b proc markStackAndRegisters(gch: var TGcHeap) {.noinline, cdecl.} = var registers: C_JmpBuf if c_setjmp(registers) == 0'i32: # To fill the C stack with registers. var max = cast[TAddress](gch.stackBottom) var sp = cast[TAddress](addr(registers)) +% jmpbufSize -% sizeof(pointer) # sp will traverse the JMP_BUF as well (jmp_buf size is added, # otherwise sp would be below the registers structure). while sp >=% max: gcMark(gch, cast[ppointer](sp)[]) sp = sp -% sizeof(pointer) else: # --------------------------------------------------------------------------- # Generic code for architectures where addresses decrease as the stack grows. # --------------------------------------------------------------------------- proc isOnStack(p: pointer): bool = var stackTop {.volatile.}: pointer stackTop = addr(stackTop) var b = cast[TAddress](gch.stackBottom) var a = cast[TAddress](stackTop) var x = cast[TAddress](p) result = a <=% x and x <=% b proc markStackAndRegisters(gch: var TGcHeap) {.noinline, cdecl.} = # We use a jmp_buf buffer that is in the C stack. # Used to traverse the stack and registers assuming # that 'setjmp' will save registers in the C stack. type PStackSlice = ptr array [0..7, pointer] var registers: C_JmpBuf if c_setjmp(registers) == 0'i32: # To fill the C stack with registers. when MinimumStackMarking: # mark the registers var jmpbufPtr = cast[TAddress](addr(registers)) var jmpbufEnd = jmpbufPtr +% jmpbufSize while jmpbufPtr <=% jmpbufEnd: gcMark(gch, cast[ppointer](jmpbufPtr)[]) jmpbufPtr = jmpbufPtr +% sizeof(pointer) var sp = cast[TAddress](gch.stackTop) else: var sp = cast[TAddress](addr(registers)) # mark the user stack var max = cast[TAddress](gch.stackBottom) # loop unrolled: while sp <% max - 8*sizeof(pointer): gcMark(gch, cast[PStackSlice](sp)[0]) gcMark(gch, cast[PStackSlice](sp)[1]) gcMark(gch, cast[PStackSlice](sp)[2]) gcMark(gch, cast[PStackSlice](sp)[3]) gcMark(gch, cast[PStackSlice](sp)[4]) gcMark(gch, cast[PStackSlice](sp)[5]) gcMark(gch, cast[PStackSlice](sp)[6]) gcMark(gch, cast[PStackSlice](sp)[7]) sp = sp +% sizeof(pointer)*8 # last few entries: while sp <=% max: gcMark(gch, cast[ppointer](sp)[]) sp = sp +% sizeof(pointer) # ---------------------------------------------------------------------------- # end of non-portable code # ---------------------------------------------------------------------------- proc releaseCell(gch: var TGcHeap, cell: PCell) = if cell.color != rcReallyDead: prepareDealloc(cell) cell.setColor rcReallyDead let l1 = gch.tempStack.len cell.forAllChildren waPush let l2 = gch.tempStack.len for i in l1 .. <l2: var cc = gch.tempStack.d[i] if cc.refcount--(LocalHeap): releaseCell(gch, cc) else: if canbeCycleRoot(cc): addCycleRoot(gch.cycleRoots, cc) gch.tempStack.len = l1 if cell.isBitDown(rcBufferedAnywhere): freeCell(gch, cell) # else: # This object is either buffered in the cycleRoots list and we'll leave # it there to be collected in the next collectCycles or it's pending in # the ZCT: # (e.g. we are now cleaning the 15th object, but this one is 18th in the # list. Note that this can happen only if we reached this point by the # recursion). # We can ignore it now as the ZCT cleaner will reach it soon. proc CollectZCT(gch: var TGcHeap): bool = const workPackage = 100 var L = addr(gch.zct.len) when withRealtime: var steps = workPackage var t0: TTicks if gch.maxPause > 0: t0 = getticks() while L[] > 0: var c = gch.zct.d[0] sysAssert c.isBitUp(rcZct), "CollectZCT: rcZct missing!" sysAssert(isAllocatedPtr(gch.region, c), "CollectZCT: isAllocatedPtr") # remove from ZCT: c.clearBit(rcZct) gch.zct.d[0] = gch.zct.d[L[] - 1] dec(L[]) when withRealtime: dec steps if c.refcount <% rcIncrement: # It may have a RC > 0, if it is in the hardware stack or # it has not been removed yet from the ZCT. This is because # ``incref`` does not bother to remove the cell from the ZCT # as this might be too slow. # In any case, it should be removed from the ZCT. But not # freed. **KEEP THIS IN MIND WHEN MAKING THIS INCREMENTAL!** if c.color == rcRetiredBuffer: if c.isBitDown(rcInCycleRoots): freeCell(gch, c) else: # if c.color == rcReallyDead: writeCell("ReallyDead in ZCT?", c) releaseCell(gch, c) when withRealtime: if steps == 0: steps = workPackage 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 # order to miss deadlines less often: if duration >= gch.maxPause - 50_000: return false result = true gch.trimCycleRoots #deInit(gch.zct) #init(gch.zct) proc unmarkStackAndRegisters(gch: var TGcHeap) = var d = gch.decStack.d for i in 0 .. <gch.decStack.len: sysAssert isAllocatedPtr(gch.region, d[i]), "unmarkStackAndRegisters" # XXX: just call doDecRef? var c = d[i] sysAssert c.typ != nil, "unmarkStackAndRegisters 2" if c.color == rcRetiredBuffer: continue # XXX no need for an atomic dec here: if c.refcount--(LocalHeap): # the object survived only because of a stack reference # it still doesn't have heap refernces addZCT(gch.zct, c) if canbeCycleRoot(c): # any cyclic object reachable from the stack can be turned into # a leak if it's orphaned through the stack reference # that's because the write-barrier won't be executed for stack # locations addCycleRoot(gch.cycleRoots, c) gch.decStack.len = 0 proc collectCTBody(gch: var TGcHeap) = when withRealtime: let t0 = getticks() when debugGC: inc gcCollectionIdx sysAssert(allocInv(gch.region), "collectCT: begin") gch.stat.maxStackSize = max(gch.stat.maxStackSize, stackSize()) sysAssert(gch.decStack.len == 0, "collectCT") prepareForInteriorPointerChecking(gch.region) markStackAndRegisters(gch) markThreadStacks(gch) gch.stat.maxStackCells = max(gch.stat.maxStackCells, gch.decStack.len) inc(gch.stat.stackScans) if collectZCT(gch): when cycleGC: if getOccupiedMem(gch.region) >= gch.cycleThreshold or alwaysCycleGC: collectCycles(gch) sysAssert gch.zct.len == 0, "zct is not null after collect cycles" inc(gch.stat.cycleCollections) gch.cycleThreshold = max(InitialCycleThreshold, getOccupiedMem() * cycleIncrease) gch.stat.maxThreshold = max(gch.stat.maxThreshold, gch.cycleThreshold) unmarkStackAndRegisters(gch) sysAssert(allocInv(gch.region), "collectCT: end") when withRealtime: let duration = getticks() - t0 gch.stat.maxPause = max(gch.stat.maxPause, duration) when defined(reportMissedDeadlines): if gch.maxPause > 0 and duration > gch.maxPause: c_fprintf(c_stdout, "[GC] missed deadline: %ld\n", duration) proc collectCT(gch: var TGcHeap) = if (gch.zct.len >= ZctThreshold or (cycleGC and getOccupiedMem(gch.region)>=gch.cycleThreshold) or alwaysGC) and gch.recGcLock == 0: collectCTBody(gch) when withRealtime: proc toNano(x: int): TNanos {.inline.} = result = x * 1000 proc GC_setMaxPause*(MaxPauseInUs: int) = gch.maxPause = MaxPauseInUs.toNano proc GC_step(gch: var TGcHeap, us: int, strongAdvice: bool) = acquire(gch) gch.maxPause = us.toNano if (gch.zct.len >= ZctThreshold or (cycleGC and getOccupiedMem(gch.region)>=gch.cycleThreshold) or alwaysGC) or strongAdvice: collectCTBody(gch) release(gch) proc GC_step*(us: int, strongAdvice = false) = GC_step(gch, us, strongAdvice) when not defined(useNimRtl): proc GC_disable() = when hasThreadSupport and hasSharedHeap: discard atomicInc(gch.recGcLock, 1) else: inc(gch.recGcLock) proc GC_enable() = if gch.recGcLock > 0: when hasThreadSupport and hasSharedHeap: discard atomicDec(gch.recGcLock, 1) else: dec(gch.recGcLock) proc GC_setStrategy(strategy: TGC_Strategy) = case strategy of gcThroughput: nil of gcResponsiveness: nil of gcOptimizeSpace: nil of gcOptimizeTime: nil proc GC_enableMarkAndSweep() = gch.cycleThreshold = InitialCycleThreshold proc GC_disableMarkAndSweep() = gch.cycleThreshold = high(gch.cycleThreshold)-1 # set to the max value to suppress the cycle detector proc GC_fullCollect() = setStackTop(gch) acquire(gch) var oldThreshold = gch.cycleThreshold gch.cycleThreshold = 0 # forces cycle collection collectCT(gch) gch.cycleThreshold = oldThreshold release(gch) proc GC_getStatistics(): string = GC_disable() result = "[GC] total memory: " & $(getTotalMem()) & "\n" & "[GC] occupied memory: " & $(getOccupiedMem()) & "\n" & "[GC] stack scans: " & $gch.stat.stackScans & "\n" & "[GC] stack cells: " & $gch.stat.maxStackCells & "\n" & "[GC] cycle collections: " & $gch.stat.cycleCollections & "\n" & "[GC] max threshold: " & $gch.stat.maxThreshold & "\n" & "[GC] zct capacity: " & $gch.zct.cap & "\n" & "[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(true) GC_enable() {.pop.}


context:
space:
mode: