# # # 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: gch.toDispose = initSharedList[pointer]() # 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(des
#
#
#            Nim's Runtime Library
#        (c) Copyright 2010 Andreas Rumpf
#
#    See the file "copying.txt", included in this
#    distribution, for details about the copyright.
#

## This module implements a base64 encoder and decoder.

const 
  cb64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"

template encodeInternal(s: expr, lineLen: int, newLine: string): stmt {.immediate.} = 
  ## encodes `s` into base64 representation. After `lineLen` characters, a 
  ## `newline` is added.
  var total = ((len(s) + 2) div 3) * 4
  var numLines = (total + lineLen - 1) div lineLen
  if numLines > 0: inc(total, (numLines-1) * newLine.len)

  result = newString(total)
  var i = 0
  var r = 0
  var currLine = 0
  while i < s.len - 2:
    var a = ord(s[i])
    var b = ord(s[i+1])
    var c = ord(s[i+2])
    result[r] = cb64[a shr 2]
    result[r+1] = cb64[((a and 3) shl 4) or ((b and 0xF0) shr 4)]
    result[r+2] = cb64[((b and 0x0F) shl 2) or ((c and 0xC0) shr 6)] 
    result[r+3] = cb64[c and 0x3F] 
    inc(r, 4)
    inc(i, 3)
    inc(currLine, 4)
    if currLine >= lineLen and i != s.len-2: 
      for x in items(newLine): 
        result[r] = x
        inc(r)
      currLine = 0

  if i < s.len-1:
    var a = ord(s[i])
    var b = ord(s[i+1])
    result[r] = cb64[a shr 2]
    result[r+1] = cb64[((a and 3) shl 4) or ((b and 0xF0) shr 4)]
    result[r+2] = cb64[((b and 0x0F) shl 2)] 
    result[r+3] = '='
    if r+4