# # # Nim's Runtime Library # (c) Copyright 2017 Andreas Rumpf # # See the file "copying.txt", included in this # distribution, for details about the copyright. # # Garbage Collector # # The basic algorithm is an incremental mark # and sweep GC to free cycles. It is hard realtime in that if you play # according to its rules, no deadline will ever be missed. # Since this kind of collector is very bad at recycling dead objects # early, Nim's codegen emits ``nimEscape`` calls at strategic # places. For this to work even 'unsureAsgnRef' needs to mark things # so that only return values need to be considered in ``nimEscape``. {.push profiler:off.} const CycleIncrease = 2 # is a multiplicative increase InitialCycleThreshold = 512*1024 # start collecting after 500KB 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) {.benign.} when hasThreadSupport: include sharedlist type ObjectSpaceIter = object state: range[-1..0] iterToProc(allObjects, ptr ObjectSpaceIter, allObjectsAsProc) const escapedBit = 0b1000 # so that lowest 3 bits are not touched rcBlackOrig = 0b000 rcWhiteOrig = 0b001 rcGrey = 0b010 # traditional color for incremental mark&sweep rcUnused = 0b011 colorMask = 0b011 type WalkOp = enum waMarkGlobal, # part of the backup mark&sweep waMarkGrey, waZctDecRef, waDebug Phase {.pure.} = enum None, Marking, Sweeping Finalizer {.compilerproc.} = proc (self: pointer) {.nimcall, benign.} # A ref type can have a finalizer that is called before the object's # storage is freed. GcStat = object stackScans: int # number of performed stack scans (for statistics) completedCollections: 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 GcStack {.final, pure.} = object when nimCoroutines: prev: ptr GcStack next: ptr GcStack maxStackSize: int # Used to track statistics because we can not use # GcStat.maxStackSize when multiple stacks exist. bottom: pointer when withRealTime or nimCoroutines: pos: pointer # Used with `withRealTime` only for code clarity, see GC_Step(). when withRealTime: bottomSaved: pointer GcHeap = object # this contains the zero count and # non-zero count table black, red: int # either 0 or 1. stack: GcStack when nimCoroutines: activeStack: ptr GcStack # current executing coroutine stack. phase: Phase cycleThreshold: int when useCellIds: idGenerator: int greyStack: CellSeq recGcLock: int # prevent recursion via finalizers; no thread lock when withRealTime: maxPause: Nanos # max allowed pause in nanoseconds; active if > 0 region: MemRegion # garbage collected region stat: GcStat additionalRoots: CellSeq # explicit roots for GC_ref/unref spaceIter: ObjectSpaceIter pDumpHeapFile: pointer # File that is used for GC_dumpHeap when hasThreadSupport: toDispose: SharedList[pointer] var gch {.rtlThreadVar.}: GcHeap when not defined(useNimRtl): instantiateForRegion(gch.region) template acquire(gch: GcHeap) = when hasThreadSupport and hasSharedHeap: acquireSys(HeapLock) template release(gch: GcHeap) = when hasThreadSupport and hasSharedHeap: releaseSys(HeapLock) proc initGC() = when not defined(useNimRtl): gch.red = (1-gch.black) gch.cycleThreshold = InitialCycleThreshold gch.stat.stackScans = 0 gch.stat.completedCollections = 0 gch.stat.maxThreshold = 0 gch.stat.maxStackSize = 0 gch.stat.maxStackCells = 0 gch.stat.cycleTableSize = 0 # init the rt init(gch.additionalRoots) init(gch.greyStack) when hasThreadSupport: init(gch.toDispose) # Which color to use for new objects is tricky: When we're marking, # they have to be *white* so that everything is marked that is only # reachable from them. However, when we are sweeping, they have to # be black, so that we don't free them prematuredly. In order to save # a comparison gch.phase == Phase.Marking, we use the pseudo-color # 'red' for new objects. template allocColor(): untyped = gch.red template gcAssert(cond: bool, msg: string) = when defined(useGcAssert): if not cond: echo "[GCASSERT] ", msg GC_disable() writeStackTrace() quit 1 proc cellToUsr(cell: PCell): pointer {.inline.} = # convert object (=pointer to refcount) to pointer to userdata result = cast[pointer](cast[ByteAddress](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))) 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 = 0 # 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!".} template color(c): untyped = c.refCount and colorMask template setColor(c, col) = c.refcount = c.refcount and not colorMask or col template markAsEscaped(c: PCell) = c.refcount = c.refcount or escapedBit template didEscape(c: PCell): bool = (c.refCount and escapedBit) != 0 proc writeCell(file: File; msg: cstring, c: PCell) = var kind = -1 if c.typ != nil: kind = ord(c.typ.kind) let col = if c.color == rcGrey: 'g' elif c.color == gch.black: 'b' else: 'w' when useCellIds: let id = c.id else: let id = c when leakDetector: c_fprintf(file, "%s %p %d escaped=%ld color=%c from %s(%ld)\n", msg, id, kind, didEscape(c), col, c.filename, c.line) else: c_fprintf(file, "%s %p %d escaped=%ld color=%c\n", msg, id, kind, didEscape(c), col) proc writeCell(msg: cstring, c: PCell) = stdout.writeCell(msg, c) proc myastToStr[T](x: T): string {.magic: "AstToStr", noSideEffect.} template gcTrace(cell, state: untyped) = when traceGC: writeCell(myastToStr(state), cell) # 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.} # we need the prototype here for debugging purposes proc rtlAddCycleRoot(c: PCell) {.rtl, inl.} = # we MUST access gch as a global here, because this crosses DLL boundaries! discard proc nimGCref(p: pointer) {.compilerProc.} = let cell = usrToCell(p) markAsEscaped(cell) add(gch.additionalRoots, cell) proc nimGCunref(p: pointer) {.compilerProc.} = let cell = usrToCell(p) var L = gch.additionalRoots.len-1 var i = L let d = gch.additionalRoots.d while i >= 0: if d[i] == cell: d[i] = d[L] dec gch.additionalRoots.len break dec(i) proc nimGCunrefNoCycle(p: pointer) {.compilerProc, inline.} = discard "can we do some freeing here?" proc nimGCunrefRC1(p: pointer) {.compilerProc, inline.} = discard "can we do some freeing here?" template markGrey(x: PCell) = if x.color != 1-gch.black and gch.phase == Phase.Marking: if not isAllocatedPtr(gch.region, x): c_fprintf(stdout, "[GC] markGrey proc: %p\n", x) #GC_dumpHeap() sysAssert(false, "wtf") x.setColor(rcGrey) add(gch.greyStack, x) proc GC_addCycleRoot*[T](p: ref T) {.inline.} = ## adds 'p' to the cycle candidate set for the cycle collector. It is ## necessary if you used the 'acyclic' pragma for optimization ## purposes and need to break cycles manually. discard template asgnRefImpl = gcAssert(not isOnStack(dest), "asgnRef") # BUGFIX: first incRef then decRef! if src != nil: let s = usrToCell(src) markAsEscaped(s) markGrey(s) dest[] = src proc asgnRef(dest: PPointer, src: pointer) {.compilerProc, inline.} = # the code generator calls this proc! asgnRefImpl() proc asgnRefNoCycle(dest: PPointer, src: pointer) {.compilerProc, inline.} = asgnRefImpl() proc unsureAsgnRef(dest: PPointer, src: pointer) {.compilerProc.} = # unsureAsgnRef marks 'src' as grey 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 src != nil: let s = usrToCell(src) markAsEscaped(s) if not isOnStack(dest): markGrey(s) dest[] = src type GlobalMarkerProc = proc () {.nimcall, benign.} var globalMarkersLen: int globalMarkers: array[0.. 7_000, GlobalMarkerProc] proc nimRegisterGlobalMarker(markerProc: GlobalMarkerProc) {.compilerProc.} = if globalMarkersLen <= high(globalMarkers): globalMarkers[globalMarkersLen] = markerProc inc globalMarkersLen else: echo "[GC] cannot register global variable; too many global variables" quit 1 proc forAllSlotsAux(dest: pointer, n: ptr TNimNode, op: WalkOp) {.benign.} = var d = cast[ByteAddress](dest) case n.kind of nkSlot: forAllChildrenAux(cast[pointer](d +% n.offset), n.typ, op) of nkList: for i in 0..n.len-1: 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: WalkOp) = var d = cast[ByteAddress](dest) if dest == nil: return # nothing to do if ntfNoRefs notin mt.flags: case mt.kind of tyRef, tyOptAsRef, 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: discard proc forAllChildren(cell: PCell, op: WalkOp) = gcAssert(cell != nil, "forAllChildren: 1") gcAssert(isAllocatedPtr(gch.region, cell), "forAllChildren: 2") gcAssert(cell.typ != nil, "forAllChildren: 3") gcAssert cell.typ.kind in {tyRef, tyOptAsRef, tySequence, tyString}, "forAllChildren: 4" let marker = cell.typ.marker if marker != nil: marker(cellToUsr(cell), op.int) else: case cell.typ.kind of tyRef, tyOptAsRef: # common case forAllChildrenAux(cellToUsr(cell), cell.typ.base, op) of tySequence: var d = cast[ByteAddress](cellToUsr(cell)) var s = cast[PGenericSeq](d) if s != nil: for i in 0..s.len-1: forAllChildrenAux(cast[pointer](d +% i *% cell.typ.base.size +% GenericSeqSize), cell.typ.base, op) else: discard {.push stackTrace: off, profiler:off.} proc gcInvariant*() = sysAssert(allocInv(gch.region), "injected") when declared(markForDebug): markForDebug(gch) {.pop.} include gc_common proc rawNewObj(typ: PNimType, size: int, gch: var GcHeap): pointer = # generates a new object and sets its reference counter to 0 sysAssert(allocInv(gch.region), "rawNewObj begin") gcAssert(typ.kind in {tyRef, tyOptAsRef, tyString, tySequence}, "newObj: 1") collectCT(gch) var res = cast[PCell](rawAlloc(gch.region, size + sizeof(Cell))) gcAssert((cast[ByteAddress](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 # refcount is zero, color is black, but mark it to be in the ZCT res.refcount = allocColor() sysAssert(isAllocatedPtr(gch.region, res), "newObj: 3") when logGC: writeCell("new cell", res) gcTrace(res, csAllocated) when useCellIds: inc gch.idGenerator res.id = gch.idGenerator result = cellToUsr(res) sysAssert(allocInv(gch.region), "rawNewObj end") {.pop.} proc newObjNoInit(typ: PNimType, size: int): pointer {.compilerRtl.} = result = rawNewObj(typ, size, gch) when defined(memProfiler): nimProfile(size) proc newObj(typ: PNimType, size:
#? stdtmpl(subsChar = '%', metaChar = '#', emit = "outfile.write")
#import strutils
#
#proc htmlQuote*(raw: string): string =
# result = raw.multiReplace(
# ("&", "&"),
# ("\"", """),
# ("'", "'"),
# ("<", "<"),
# (">", ">")
# )
#
#end proc
#proc generateHtmlBegin*(outfile: File) =
<!DOCTYPE html>
<html>
<head>
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Testament Test Results</title>
<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/2.2.0/jquery.min.js" integrity="sha256-ihAoc6M/JPfrIiIeayPE9xjin4UWjsx2mjW/rtmxLM4=" crossorigin="anonymous"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/twitter-bootstrap/3.3.7/js/bootstrap.min.js" integrity="sha256-U5ZEeKfGNOja007MMD3YBI0A3OSZOQbeG6z2f2Y0hu8=" crossorigin="anonymous"></script>
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/twitter-bootstrap/3.3.7/css/bootstrap.min.css" integrity="sha256-916EbMg70RQy9LHiGkXzG8hSg9EdNy97GazNG/aiY1w=" crossorigin="anonymous" />
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/twitter-bootstrap/3.3.7/css/bootstrap-theme.min.css" integrity="sha256-ZT4HPpdCOt2lvDkXokHuhJfdOKSPFLzeAJik5U/Q+l4=" crossorigin="anonymous" />
<script>
/**
* Callback function that is executed for each Element in an array.
* @callback executeForElement
* @param {Element} elem Element to operate on
*/
/**
*
* @param {number} index
* @param {Element[]} elemArray
* @param {executeForElement} executeOnItem
*/
function executeAllAsync(elemArray, index, executeOnItem) {
for (var i = 0; index < elemArray.length && i < 100; i++ , index++) {
var item = elemArray[index];
executeOnItem(item);
}
if (index < elemArray.length) {
setTimeout(executeAllAsync, 0, elemArray, index, executeOnItem);
}
}
/** @param {Element} elem */
function executeShowOnElement(elem) {
while (elem.classList.contains("hidden")) {
elem.classList.remove("hidden");
}
}
/** @param {Element} elem */
function executeHideOnElement(elem) {
if (!elem.classList.contains("hidden")) {
elem.classList.add("hidden");
}
}
/** @param {Element} elem */
function executeExpandOnElement(elem) {
$(elem).collapse("show");
}
/** @param {Element} elem */
function executeCollapseOnElement(elem) {
$(elem).collapse("hide");
}
/**
* @param {string} [category] Optional bootstrap panel context class (danger, warning, info, success)
* @param {executeForElement} executeOnEachPanel
*/
function wholePanelAll(category, executeOnEachPanel) {
var selector = "div.panel";
if (typeof category === "string" && category) {
selector += "-" + category;
}
var jqPanels = $(selector);
/** @type {Element[]} */
var elemArray = jqPanels.toArray();
setTimeout(executeAllAsync, 0, elemArray, 0, executeOnEachPanel);
}
/**
* @param {string} [category] Optional bootstrap panel context class (danger, warning, info, success)
* @param {executeForElement} executeOnEachPanel
*/
function panelBodyAll(category, executeOnEachPanelBody) {
var selector = "div.panel";
if (typeof category === "string" && category) {
selector += "-" + category;
}
var jqPanels = $(selector);
var jqPanelBodies = $("div.panel-body", jqPanels);
/** @type {Element[]} */
var elemArray = jqPanelBodies.toArray();
setTimeout(executeAllAsync, 0, elemArray, 0, executeOnEachPanelBody);
}
/**
* @param {string} [category] Optional bootstrap panel context class (danger, warning, info, success)
*/
function showAll(category) {
wholePanelAll(category, executeShowOnElement);
}
/**
* @param {string} [category] Optional bootstrap panel context class (danger, warning, info, success)
*/
function hideAll(category) {
wholePanelAll(category, executeHideOnElement);
}
/**
* @param {string} [category] Optional bootstrap panel context class (danger, warning, info, success)
*/
function expandAll(category) {
panelBodyAll(category, executeExpandOnElement);
}
/**
* @param {string} [category] Optional bootstrap panel context class (danger, warning, info, success)
*/
function collapseAll(category) {
panelBodyAll(category, executeCollapseOnElement);
}
</script>
</head>
<body>
<div class="container">
<h1>Testament Test Results <small>Nim Tester</small></h1>
#end proc
#proc generateHtmlAllTestsBegin*(outfile: File, machine, commit, branch: string,
# totalCount: BiggestInt,
# successCount: BiggestInt, successPercentage: string,
# ignoredCount: BiggestInt, ignoredPercentage: string,
# failedCount: BiggestInt, failedPercentage: string, onlyFailing = false) =
<dl class="dl-horizontal">
<dt>Hostname</dt>
<dd>%machine</dd>
<dt>Git Commit</dt>
<dd><code>%commit</code></dd>
<dt title="Git Branch reference">Branch ref.</dt>
<dd>%branch</dd>
</dl>
<dl class="dl-horizontal">
<dt>All Tests</dt>
<dd>
<span class="glyphicon glyphicon-th-list"></span>
%totalCount
</dd>
<dt>Successful Tests</dt>
<dd>
<span class="glyphicon glyphicon-ok-sign"></span>
%successCount (%successPercentage)
</dd>
<dt>Skipped Tests</dt>
<dd>
<span class="glyphicon glyphicon-question-sign"></span>
%ignoredCount (%ignoredPercentage)
</dd>
<dt>Failed Tests</dt>
<dd>
<span class="glyphicon glyphicon-exclamation-sign"></span>
%failedCount (%failedPercentage)
</dd>
</dl>
<div class="table-responsive">
<table class="table table-condensed">
# if not onlyFailing:
<tr>
<th class="text-right" style="vertical-align:middle">All Tests</th>
<td>
<div class="btn-group">
<button class="btn btn-default" type="button" onclick="showAll();">Show All</button>
<button class="btn btn-default" type="button" onclick="hideAll();">Hide All</button>
<button class="btn btn-default" type="button" onclick="expandAll();">Expand All</button>
<button class="btn btn-default" type="button" onclick="collapseAll();">Collapse All</button>
</div>
</td>
</tr>