1# 2# 3# Nim's Runtime Library 4# (c) Copyright 2016 Andreas Rumpf 5# 6# See the file "copying.txt", included in this 7# distribution, for details about the copyright. 8# 9 10# Garbage Collector 11# 12# Refcounting + Mark&Sweep. Complex algorithms avoided. 13# Been there, done that, didn't work. 14 15#[ 16 17A *cell* is anything that is traced by the GC 18(sequences, refs, strings, closures). 19 20The basic algorithm is *Deferrent Reference Counting* with cycle detection. 21References on the stack are not counted for better performance and easier C 22code generation. 23 24Each cell has a header consisting of a RC and a pointer to its type 25descriptor. However the program does not know about these, so they are placed at 26negative offsets. In the GC code the type `PCell` denotes a pointer 27decremented by the right offset, so that the header can be accessed easily. It 28is extremely important that `pointer` is not confused with a `PCell`. 29 30In Nim the compiler cannot always know if a reference 31is stored on the stack or not. This is caused by var parameters. 32Consider this example: 33 34.. code-block:: Nim 35 proc setRef(r: var ref TNode) = 36 new(r) 37 38 proc usage = 39 var 40 r: ref TNode 41 setRef(r) # here we should not update the reference counts, because 42 # r is on the stack 43 setRef(r.left) # here we should update the refcounts! 44 45We have to decide at runtime whether the reference is on the stack or not. 46The generated code looks roughly like this: 47 48.. code-block:: C 49 void setref(TNode** ref) { 50 unsureAsgnRef(ref, newObj(TNode_TI, sizeof(TNode))) 51 } 52 void usage(void) { 53 setRef(&r) 54 setRef(&r->left) 55 } 56 57Note that for systems with a continuous stack (which most systems have) 58the check whether the ref is on the stack is very cheap (only two 59comparisons). 60]# 61 62{.push profiler:off.} 63 64const 65 CycleIncrease = 2 # is a multiplicative increase 66 InitialCycleThreshold = when defined(nimCycleBreaker): high(int) 67 else: 4*1024*1024 # X MB because cycle checking is slow 68 InitialZctThreshold = 500 # we collect garbage if the ZCT's size 69 # reaches this threshold 70 # this seems to be a good value 71 withRealTime = defined(useRealtimeGC) 72 73when withRealTime and not declared(getTicks): 74 include "system/timers" 75when defined(memProfiler): 76 proc nimProfile(requestedSize: int) {.benign.} 77 78when hasThreadSupport: 79 import sharedlist 80 81const 82 rcIncrement = 0b1000 # so that lowest 3 bits are not touched 83 rcBlack = 0b000 # cell is colored black; in use or free 84 rcGray = 0b001 # possible member of a cycle 85 rcWhite = 0b010 # member of a garbage cycle 86 rcPurple = 0b011 # possible root of a cycle 87 ZctFlag = 0b100 # in ZCT 88 rcShift = 3 # shift by rcShift to get the reference counter 89 colorMask = 0b011 90type 91 WalkOp = enum 92 waMarkGlobal, # part of the backup/debug mark&sweep 93 waMarkPrecise, # part of the backup/debug mark&sweep 94 waZctDecRef, waPush 95 #, waDebug 96 97 Finalizer {.compilerproc.} = proc (self: pointer) {.nimcall, benign, raises: [].} 98 # A ref type can have a finalizer that is called before the object's 99 # storage is freed. 100 101 GcStat {.final, pure.} = object 102 stackScans: int # number of performed stack scans (for statistics) 103 cycleCollections: int # number of performed full collections 104 maxThreshold: int # max threshold that has been set 105 maxStackSize: int # max stack size 106 maxStackCells: int # max stack cells in ``decStack`` 107 cycleTableSize: int # max entries in cycle table 108 maxPause: int64 # max measured GC pause in nanoseconds 109 110 GcStack {.final, pure.} = object 111 when nimCoroutines: 112 prev: ptr GcStack 113 next: ptr GcStack 114 maxStackSize: int # Used to track statistics because we can not use 115 # GcStat.maxStackSize when multiple stacks exist. 116 bottom: pointer 117 118 when withRealTime or nimCoroutines: 119 pos: pointer # Used with `withRealTime` only for code clarity, see GC_Step(). 120 when withRealTime: 121 bottomSaved: pointer 122 123 GcHeap {.final, pure.} = object # this contains the zero count and 124 # non-zero count table 125 stack: GcStack 126 when nimCoroutines: 127 activeStack: ptr GcStack # current executing coroutine stack. 128 cycleThreshold: int 129 zctThreshold: int 130 when useCellIds: 131 idGenerator: int 132 zct: CellSeq # the zero count table 133 decStack: CellSeq # cells in the stack that are to decref again 134 tempStack: CellSeq # temporary stack for recursion elimination 135 recGcLock: int # prevent recursion via finalizers; no thread lock 136 when withRealTime: 137 maxPause: Nanos # max allowed pause in nanoseconds; active if > 0 138 region: MemRegion # garbage collected region 139 stat: GcStat 140 marked: CellSet 141 additionalRoots: CellSeq # dummy roots for GC_ref/unref 142 when hasThreadSupport: 143 toDispose: SharedList[pointer] 144 gcThreadId: int 145 146var 147 gch {.rtlThreadVar.}: GcHeap 148 149when not defined(useNimRtl): 150 instantiateForRegion(gch.region) 151 152template gcAssert(cond: bool, msg: string) = 153 when defined(useGcAssert): 154 if not cond: 155 cstderr.rawWrite "[GCASSERT] " 156 cstderr.rawWrite msg 157 when defined(logGC): 158 cstderr.rawWrite "[GCASSERT] statistics:\L" 159 cstderr.rawWrite GC_getStatistics() 160 GC_disable() 161 writeStackTrace() 162 #var x: ptr int 163 #echo x[] 164 quit 1 165 166proc addZCT(s: var CellSeq, c: PCell) {.noinline.} = 167 if (c.refcount and ZctFlag) == 0: 168 c.refcount = c.refcount or ZctFlag 169 add(s, c) 170 171proc cellToUsr(cell: PCell): pointer {.inline.} = 172 # convert object (=pointer to refcount) to pointer to userdata 173 result = cast[pointer](cast[ByteAddress](cell)+%ByteAddress(sizeof(Cell))) 174 175proc usrToCell(usr: pointer): PCell {.inline.} = 176 # convert pointer to userdata to object (=pointer to refcount) 177 result = cast[PCell](cast[ByteAddress](usr)-%ByteAddress(sizeof(Cell))) 178 179proc extGetCellType(c: pointer): PNimType {.compilerproc.} = 180 # used for code generation concerning debugging 181 result = usrToCell(c).typ 182 183proc internRefcount(p: pointer): int {.exportc: "getRefcount".} = 184 result = usrToCell(p).refcount shr rcShift 185 186# this that has to equals zero, otherwise we have to round up UnitsPerPage: 187when BitsPerPage mod (sizeof(int)*8) != 0: 188 {.error: "(BitsPerPage mod BitsPerUnit) should be zero!".} 189 190template color(c): untyped = c.refCount and colorMask 191template setColor(c, col) = 192 when col == rcBlack: 193 c.refcount = c.refcount and not colorMask 194 else: 195 c.refcount = c.refcount and not colorMask or col 196 197when defined(logGC): 198 proc writeCell(msg: cstring, c: PCell) = 199 var kind = -1 200 var typName: cstring = "nil" 201 if c.typ != nil: 202 kind = ord(c.typ.kind) 203 when defined(nimTypeNames): 204 if not c.typ.name.isNil: 205 typName = c.typ.name 206 207 when leakDetector: 208 c_printf("[GC] %s: %p %d %s rc=%ld from %s(%ld)\n", 209 msg, c, kind, typName, c.refcount shr rcShift, c.filename, c.line) 210 else: 211 c_printf("[GC] %s: %p %d %s rc=%ld; thread=%ld\n", 212 msg, c, kind, typName, c.refcount shr rcShift, gch.gcThreadId) 213 214template logCell(msg: cstring, c: PCell) = 215 when defined(logGC): 216 writeCell(msg, c) 217 218template gcTrace(cell, state: untyped) = 219 when traceGC: traceCell(cell, state) 220 221# forward declarations: 222proc collectCT(gch: var GcHeap) {.benign, raises: [].} 223proc isOnStack(p: pointer): bool {.noinline, benign, raises: [].} 224proc forAllChildren(cell: PCell, op: WalkOp) {.benign, raises: [].} 225proc doOperation(p: pointer, op: WalkOp) {.benign, raises: [].} 226proc forAllChildrenAux(dest: pointer, mt: PNimType, op: WalkOp) {.benign, raises: [].} 227# we need the prototype here for debugging purposes 228 229proc incRef(c: PCell) {.inline.} = 230 gcAssert(isAllocatedPtr(gch.region, c), "incRef: interiorPtr") 231 c.refcount = c.refcount +% rcIncrement 232 # and not colorMask 233 logCell("incRef", c) 234 235proc nimGCref(p: pointer) {.compilerproc.} = 236 # we keep it from being collected by pretending it's not even allocated: 237 let c = usrToCell(p) 238 add(gch.additionalRoots, c) 239 incRef(c) 240 241proc rtlAddZCT(c: PCell) {.rtl, inl.} = 242 # we MUST access gch as a global here, because this crosses DLL boundaries! 243 addZCT(gch.zct, c) 244 245proc decRef(c: PCell) {.inline.} = 246 gcAssert(isAllocatedPtr(gch.region, c), "decRef: interiorPtr") 247 gcAssert(c.refcount >=% rcIncrement, "decRef") 248 c.refcount = c.refcount -% rcIncrement 249 if c.refcount <% rcIncrement: 250 rtlAddZCT(c) 251 logCell("decRef", c) 252 253proc nimGCunref(p: pointer) {.compilerproc.} = 254 let cell = usrToCell(p) 255 var L = gch.additionalRoots.len-1 256 var i = L 257 let d = gch.additionalRoots.d 258 while i >= 0: 259 if d[i] == cell: 260 d[i] = d[L] 261 dec gch.additionalRoots.len 262 break 263 dec(i) 264 decRef(usrToCell(p)) 265 266include gc_common 267 268template beforeDealloc(gch: var GcHeap; c: PCell; msg: typed) = 269 when false: 270 for i in 0..gch.decStack.len-1: 271 if gch.decStack.d[i] == c: 272 sysAssert(false, msg) 273 274proc nimGCunrefNoCycle(p: pointer) {.compilerproc, inline.} = 275 sysAssert(allocInv(gch.region), "begin nimGCunrefNoCycle") 276 decRef(usrToCell(p)) 277 sysAssert(allocInv(gch.region), "end nimGCunrefNoCycle 5") 278 279proc nimGCunrefRC1(p: pointer) {.compilerproc, inline.} = 280 decRef(usrToCell(p)) 281 282proc asgnRef(dest: PPointer, src: pointer) {.compilerproc, inline.} = 283 # the code generator calls this proc! 284 gcAssert(not isOnStack(dest), "asgnRef") 285 # BUGFIX: first incRef then decRef! 286 if src != nil: incRef(usrToCell(src)) 287 if dest[] != nil: decRef(usrToCell(dest[])) 288 dest[] = src 289 290proc asgnRefNoCycle(dest: PPointer, src: pointer) {.compilerproc, inline, 291 deprecated: "old compiler compat".} = asgnRef(dest, src) 292 293proc unsureAsgnRef(dest: PPointer, src: pointer) {.compilerproc.} = 294 # unsureAsgnRef updates the reference counters only if dest is not on the 295 # stack. It is used by the code generator if it cannot decide whether a 296 # reference is in the stack or not (this can happen for var parameters). 297 if not isOnStack(dest): 298 if src != nil: incRef(usrToCell(src)) 299 # XXX finally use assembler for the stack checking instead! 300 # the test for '!= nil' is correct, but I got tired of the segfaults 301 # resulting from the crappy stack checking: 302 if cast[int](dest[]) >=% PageSize: decRef(usrToCell(dest[])) 303 else: 304 # can't be an interior pointer if it's a stack location! 305 gcAssert(interiorAllocatedPtr(gch.region, dest) == nil, 306 "stack loc AND interior pointer") 307 dest[] = src 308 309proc initGC() = 310 when not defined(useNimRtl): 311 when traceGC: 312 for i in low(CellState)..high(CellState): init(states[i]) 313 gch.cycleThreshold = InitialCycleThreshold 314 gch.zctThreshold = InitialZctThreshold 315 gch.stat.stackScans = 0 316 gch.stat.cycleCollections = 0 317 gch.stat.maxThreshold = 0 318 gch.stat.maxStackSize = 0 319 gch.stat.maxStackCells = 0 320 gch.stat.cycleTableSize = 0 321 # init the rt 322 init(gch.zct) 323 init(gch.tempStack) 324 init(gch.decStack) 325 init(gch.marked) 326 init(gch.additionalRoots) 327 when hasThreadSupport: 328 init(gch.toDispose) 329 gch.gcThreadId = atomicInc(gHeapidGenerator) - 1 330 gcAssert(gch.gcThreadId >= 0, "invalid computed thread ID") 331 332proc cellsetReset(s: var CellSet) = 333 deinit(s) 334 init(s) 335 336{.push stacktrace:off.} 337 338proc forAllSlotsAux(dest: pointer, n: ptr TNimNode, op: WalkOp) {.benign.} = 339 var d = cast[ByteAddress](dest) 340 case n.kind 341 of nkSlot: forAllChildrenAux(cast[pointer](d +% n.offset), n.typ, op) 342 of nkList: 343 for i in 0..n.len-1: 344 # inlined for speed 345 if n.sons[i].kind == nkSlot: 346 if n.sons[i].typ.kind in {tyRef, tyString, tySequence}: 347 doOperation(cast[PPointer](d +% n.sons[i].offset)[], op) 348 else: 349 forAllChildrenAux(cast[pointer](d +% n.sons[i].offset), 350 n.sons[i].typ, op) 351 else: 352 forAllSlotsAux(dest, n.sons[i], op) 353 of nkCase: 354 var m = selectBranch(dest, n) 355 if m != nil: forAllSlotsAux(dest, m, op) 356 of nkNone: sysAssert(false, "forAllSlotsAux") 357 358proc forAllChildrenAux(dest: pointer, mt: PNimType, op: WalkOp) = 359 var d = cast[ByteAddress](dest) 360 if dest == nil: return # nothing to do 361 if ntfNoRefs notin mt.flags: 362 case mt.kind 363 of tyRef, tyString, tySequence: # leaf: 364 doOperation(cast[PPointer](d)[], op) 365 of tyObject, tyTuple: 366 forAllSlotsAux(dest, mt.node, op) 367 of tyArray, tyArrayConstr, tyOpenArray: 368 for i in 0..(mt.size div mt.base.size)-1: 369 forAllChildrenAux(cast[pointer](d +% i *% mt.base.size), mt.base, op) 370 else: discard 371 372proc forAllChildren(cell: PCell, op: WalkOp) = 373 gcAssert(cell != nil, "forAllChildren: cell is nil") 374 gcAssert(isAllocatedPtr(gch.region, cell), "forAllChildren: pointer not part of the heap") 375 gcAssert(cell.typ != nil, "forAllChildren: cell.typ is nil") 376 gcAssert cell.typ.kind in {tyRef, tySequence, tyString}, "forAllChildren: unknown GC'ed type" 377 let marker = cell.typ.marker 378 if marker != nil: 379 marker(cellToUsr(cell), op.int) 380 else: 381 case cell.typ.kind 382 of tyRef: # common case 383 forAllChildrenAux(cellToUsr(cell), cell.typ.base, op) 384 of tySequence: 385 var d = cast[ByteAddress](cellToUsr(cell)) 386 var s = cast[PGenericSeq](d) 387 if s != nil: 388 for i in 0..s.len-1: 389 forAllChildrenAux(cast[pointer](d +% align(GenericSeqSize, cell.typ.base.align) +% i *% cell.typ.base.size), cell.typ.base, op) 390 else: discard 391 392proc addNewObjToZCT(res: PCell, gch: var GcHeap) {.inline.} = 393 # we check the last 8 entries (cache line) for a slot that could be reused. 394 # In 63% of all cases we succeed here! But we have to optimize the heck 395 # out of this small linear search so that ``newObj`` is not slowed down. 396 # 397 # Slots to try cache hit 398 # 1 32% 399 # 4 59% 400 # 8 63% 401 # 16 66% 402 # all slots 68% 403 var L = gch.zct.len 404 var d = gch.zct.d 405 when true: 406 # loop unrolled for performance: 407 template replaceZctEntry(i: untyped) = 408 c = d[i] 409 if c.refcount >=% rcIncrement: 410 c.refcount = c.refcount and not ZctFlag 411 d[i] = res 412 return 413 if L > 8: 414 var c: PCell 415 replaceZctEntry(L-1) 416 replaceZctEntry(L-2) 417 replaceZctEntry(L-3) 418 replaceZctEntry(L-4) 419 replaceZctEntry(L-5) 420 replaceZctEntry(L-6) 421 replaceZctEntry(L-7) 422 replaceZctEntry(L-8) 423 add(gch.zct, res) 424 else: 425 d[L] = res 426 inc(gch.zct.len) 427 else: 428 for i in countdown(L-1, max(0, L-8)): 429 var c = d[i] 430 if c.refcount >=% rcIncrement: 431 c.refcount = c.refcount and not ZctFlag 432 d[i] = res 433 return 434 add(gch.zct, res) 435 436{.push stackTrace: off, profiler:off.} 437proc gcInvariant*() = 438 sysAssert(allocInv(gch.region), "injected") 439 when declared(markForDebug): 440 markForDebug(gch) 441{.pop.} 442 443template setFrameInfo(c: PCell) = 444 when leakDetector: 445 if framePtr != nil and framePtr.prev != nil: 446 c.filename = framePtr.prev.filename 447 c.line = framePtr.prev.line 448 else: 449 c.filename = nil 450 c.line = 0 451 452proc rawNewObj(typ: PNimType, size: int, gch: var GcHeap): pointer = 453 # generates a new object and sets its reference counter to 0 454 incTypeSize typ, size 455 sysAssert(allocInv(gch.region), "rawNewObj begin") 456 gcAssert(typ.kind in {tyRef, tyString, tySequence}, "newObj: 1") 457 collectCT(gch) 458 var res = cast[PCell](rawAlloc(gch.region, size + sizeof(Cell))) 459 #gcAssert typ.kind in {tyString, tySequence} or size >= typ.base.size, "size too small" 460 gcAssert((cast[ByteAddress](res) and (MemAlign-1)) == 0, "newObj: 2") 461 # now it is buffered in the ZCT 462 res.typ = typ 463 setFrameInfo(res) 464 # refcount is zero, color is black, but mark it to be in the ZCT 465 res.refcount = ZctFlag 466 sysAssert(isAllocatedPtr(gch.region, res), "newObj: 3") 467 # its refcount is zero, so add it to the ZCT: 468 addNewObjToZCT(res, gch) 469 logCell("new cell", res) 470 track("rawNewObj", res, size) 471 gcTrace(res, csAllocated) 472 when useCellIds: 473 inc gch.idGenerator 474 res.id = gch.idGenerator * 1000_000 + gch.gcThreadId 475 result = cellToUsr(res) 476 sysAssert(allocInv(gch.region), "rawNewObj end") 477 478{.pop.} # .stackTrace off 479{.pop.} # .profiler off 480 481proc newObjNoInit(typ: PNimType, size: int): pointer {.compilerRtl.} = 482 result = rawNewObj(typ, size, gch) 483 when defined(memProfiler): nimProfile(size) 484 485proc newObj(typ: PNimType, size: int): pointer {.compilerRtl, noinline.} = 486 result = rawNewObj(typ, size, gch) 487 zeroMem(result, size) 488 when defined(memProfiler): nimProfile(size) 489 490{.push overflowChecks: on.} 491proc newSeq(typ: PNimType, len: int): pointer {.compilerRtl.} = 492 # `newObj` already uses locks, so no need for them here. 493 let size = align(GenericSeqSize, typ.base.align) + len * typ.base.size 494 result = newObj(typ, size) 495 cast[PGenericSeq](result).len = len 496 cast[PGenericSeq](result).reserved = len 497 when defined(memProfiler): nimProfile(size) 498{.pop.} 499 500proc newObjRC1(typ: PNimType, size: int): pointer {.compilerRtl, noinline.} = 501 # generates a new object and sets its reference counter to 1 502 incTypeSize typ, size 503 sysAssert(allocInv(gch.region), "newObjRC1 begin") 504 gcAssert(typ.kind in {tyRef, tyString, tySequence}, "newObj: 1") 505 collectCT(gch) 506 sysAssert(allocInv(gch.region), "newObjRC1 after collectCT") 507 508 var res = cast[PCell](rawAlloc(gch.region, size + sizeof(Cell))) 509 sysAssert(allocInv(gch.region), "newObjRC1 after rawAlloc") 510 sysAssert((cast[ByteAddress](res) and (MemAlign-1)) == 0, "newObj: 2") 511 # now it is buffered in the ZCT 512 res.typ = typ 513 setFrameInfo(res) 514 res.refcount = rcIncrement # refcount is 1 515 sysAssert(isAllocatedPtr(gch.region, res), "newObj: 3") 516 logCell("new cell", res) 517 track("newObjRC1", res, size) 518 gcTrace(res, csAllocated) 519 when useCellIds: 520 inc gch.idGenerator 521 res.id = gch.idGenerator * 1000_000 + gch.gcThreadId 522 result = cellToUsr(res) 523 zeroMem(result, size) 524 sysAssert(allocInv(gch.region), "newObjRC1 end") 525 when defined(memProfiler): nimProfile(size) 526 527{.push overflowChecks: on.} 528proc newSeqRC1(typ: PNimType, len: int): pointer {.compilerRtl.} = 529 let size = align(GenericSeqSize, typ.base.align) + len * typ.base.size 530 result = newObjRC1(typ, size) 531 cast[PGenericSeq](result).len = len 532 cast[PGenericSeq](result).reserved = len 533 when defined(memProfiler): nimProfile(size) 534{.pop.} 535 536proc growObj(old: pointer, newsize: int, gch: var GcHeap): pointer = 537 collectCT(gch) 538 var ol = usrToCell(old) 539 sysAssert(ol.typ != nil, "growObj: 1") 540 gcAssert(ol.typ.kind in {tyString, tySequence}, "growObj: 2") 541 sysAssert(allocInv(gch.region), "growObj begin") 542 543 var res = cast[PCell](rawAlloc(gch.region, newsize + sizeof(Cell))) 544 var elemSize,elemAlign = 1 545 if ol.typ.kind != tyString: 546 elemSize = ol.typ.base.size 547 elemAlign = ol.typ.base.align 548 incTypeSize ol.typ, newsize 549 550 var oldsize = align(GenericSeqSize, elemAlign) + cast[PGenericSeq](old).len * elemSize 551 copyMem(res, ol, oldsize + sizeof(Cell)) 552 zeroMem(cast[pointer](cast[ByteAddress](res) +% oldsize +% sizeof(Cell)), 553 newsize-oldsize) 554 sysAssert((cast[ByteAddress](res) and (MemAlign-1)) == 0, "growObj: 3") 555 # This can be wrong for intermediate temps that are nevertheless on the 556 # heap because of lambda lifting: 557 #gcAssert(res.refcount shr rcShift <=% 1, "growObj: 4") 558 logCell("growObj old cell", ol) 559 logCell("growObj new cell", res) 560 gcTrace(ol, csZctFreed) 561 gcTrace(res, csAllocated) 562 track("growObj old", ol, 0) 563 track("growObj new", res, newsize) 564 when defined(nimIncrSeqV3): 565 # since we steal the old seq's contents, we set the old length to 0. 566 cast[PGenericSeq](old).len = 0 567 elif reallyDealloc: 568 sysAssert(allocInv(gch.region), "growObj before dealloc") 569 if ol.refcount shr rcShift <=% 1: 570 # free immediately to save space: 571 if (ol.refcount and ZctFlag) != 0: 572 var j = gch.zct.len-1 573 var d = gch.zct.d 574 while j >= 0: 575 if d[j] == ol: 576 d[j] = res 577 break 578 dec(j) 579 beforeDealloc(gch, ol, "growObj stack trash") 580 decTypeSize(ol, ol.typ) 581 rawDealloc(gch.region, ol) 582 else: 583 # we split the old refcount in 2 parts. XXX This is still not entirely 584 # correct if the pointer that receives growObj's result is on the stack. 585 # A better fix would be to emit the location specific write barrier for 586 # 'growObj', but this is lots of more work and who knows what new problems 587 # this would create. 588 res.refcount = rcIncrement 589 decRef(ol) 590 else: 591 sysAssert(ol.typ != nil, "growObj: 5") 592 zeroMem(ol, sizeof(Cell)) 593 when useCellIds: 594 inc gch.idGenerator 595 res.id = gch.idGenerator * 1000_000 + gch.gcThreadId 596 result = cellToUsr(res) 597 sysAssert(allocInv(gch.region), "growObj end") 598 when defined(memProfiler): nimProfile(newsize-oldsize) 599 600proc growObj(old: pointer, newsize: int): pointer {.rtl.} = 601 result = growObj(old, newsize, gch) 602 603{.push profiler:off, stackTrace:off.} 604 605# ---------------- cycle collector ------------------------------------------- 606 607proc freeCyclicCell(gch: var GcHeap, c: PCell) = 608 prepareDealloc(c) 609 gcTrace(c, csCycFreed) 610 track("cycle collector dealloc cell", c, 0) 611 logCell("cycle collector dealloc cell", c) 612 when reallyDealloc: 613 sysAssert(allocInv(gch.region), "free cyclic cell") 614 beforeDealloc(gch, c, "freeCyclicCell: stack trash") 615 rawDealloc(gch.region, c) 616 else: 617 gcAssert(c.typ != nil, "freeCyclicCell") 618 zeroMem(c, sizeof(Cell)) 619 620proc sweep(gch: var GcHeap) = 621 for x in allObjects(gch.region): 622 if isCell(x): 623 # cast to PCell is correct here: 624 var c = cast[PCell](x) 625 if c notin gch.marked: freeCyclicCell(gch, c) 626 627proc markS(gch: var GcHeap, c: PCell) = 628 gcAssert isAllocatedPtr(gch.region, c), "markS: foreign heap root detected A!" 629 incl(gch.marked, c) 630 gcAssert gch.tempStack.len == 0, "stack not empty!" 631 forAllChildren(c, waMarkPrecise) 632 while gch.tempStack.len > 0: 633 dec gch.tempStack.len 634 var d = gch.tempStack.d[gch.tempStack.len] 635 gcAssert isAllocatedPtr(gch.region, d), "markS: foreign heap root detected B!" 636 if not containsOrIncl(gch.marked, d): 637 forAllChildren(d, waMarkPrecise) 638 639proc markGlobals(gch: var GcHeap) {.raises: [].} = 640 if gch.gcThreadId == 0: 641 for i in 0 .. globalMarkersLen-1: globalMarkers[i]() 642 for i in 0 .. threadLocalMarkersLen-1: threadLocalMarkers[i]() 643 let d = gch.additionalRoots.d 644 for i in 0 .. gch.additionalRoots.len-1: markS(gch, d[i]) 645 646when logGC: 647 var 648 cycleCheckA: array[100, PCell] 649 cycleCheckALen = 0 650 651 proc alreadySeen(c: PCell): bool = 652 for i in 0 .. cycleCheckALen-1: 653 if cycleCheckA[i] == c: return true 654 if cycleCheckALen == len(cycleCheckA): 655 gcAssert(false, "cycle detection overflow") 656 quit 1 657 cycleCheckA[cycleCheckALen] = c 658 inc cycleCheckALen 659 660 proc debugGraph(s: PCell) = 661 if alreadySeen(s): 662 writeCell("child cell (already seen) ", s) 663 else: 664 writeCell("cell {", s) 665 forAllChildren(s, waDebug) 666 c_printf("}\n") 667 668proc doOperation(p: pointer, op: WalkOp) = 669 if p == nil: return 670 var c: PCell = usrToCell(p) 671 gcAssert(c != nil, "doOperation: 1") 672 # the 'case' should be faster than function pointers because of easy 673 # prediction: 674 case op 675 of waZctDecRef: 676 #if not isAllocatedPtr(gch.region, c): 677 # c_printf("[GC] decref bug: %p", c) 678 gcAssert(isAllocatedPtr(gch.region, c), "decRef: waZctDecRef") 679 gcAssert(c.refcount >=% rcIncrement, "doOperation 2") 680 logCell("decref (from doOperation)", c) 681 track("waZctDecref", p, 0) 682 decRef(c) 683 of waPush: 684 add(gch.tempStack, c) 685 of waMarkGlobal: 686 markS(gch, c) 687 of waMarkPrecise: 688 add(gch.tempStack, c) 689 #of waDebug: debugGraph(c) 690 691proc nimGCvisit(d: pointer, op: int) {.compilerRtl.} = 692 doOperation(d, WalkOp(op)) 693 694proc collectZCT(gch: var GcHeap): bool {.benign, raises: [].} 695 696proc collectCycles(gch: var GcHeap) {.raises: [].} = 697 when hasThreadSupport: 698 for c in gch.toDispose: 699 nimGCunref(c) 700 # ensure the ZCT 'color' is not used: 701 while gch.zct.len > 0: discard collectZCT(gch) 702 cellsetReset(gch.marked) 703 var d = gch.decStack.d 704 for i in 0..gch.decStack.len-1: 705 sysAssert isAllocatedPtr(gch.region, d[i]), "collectCycles" 706 markS(gch, d[i]) 707 markGlobals(gch) 708 sweep(gch) 709 710proc gcMark(gch: var GcHeap, p: pointer) {.inline.} = 711 # the addresses are not as cells on the stack, so turn them to cells: 712 sysAssert(allocInv(gch.region), "gcMark begin") 713 var c = cast[ByteAddress](p) 714 if c >% PageSize: 715 # fast check: does it look like a cell? 716 var objStart = cast[PCell](interiorAllocatedPtr(gch.region, p)) 717 if objStart != nil: 718 # mark the cell: 719 incRef(objStart) 720 add(gch.decStack, objStart) 721 when false: 722 let cell = usrToCell(p) 723 if isAllocatedPtr(gch.region, cell): 724 sysAssert false, "allocated pointer but not interior?" 725 # mark the cell: 726 incRef(cell) 727 add(gch.decStack, cell) 728 sysAssert(allocInv(gch.region), "gcMark end") 729 730#[ 731 This method is conditionally marked with an attribute so that it gets ignored by the LLVM ASAN 732 (Address SANitizer) intrumentation as it will raise false errors due to the implementation of 733 garbage collection that is used by Nim. For more information, please see the documentation of 734 `CLANG_NO_SANITIZE_ADDRESS` in `lib/nimbase.h`. 735 ]# 736proc markStackAndRegisters(gch: var GcHeap) {.noinline, cdecl, 737 codegenDecl: "CLANG_NO_SANITIZE_ADDRESS N_LIB_PRIVATE $# $#$#".} = 738 forEachStackSlot(gch, gcMark) 739 740proc collectZCT(gch: var GcHeap): bool = 741 # Note: Freeing may add child objects to the ZCT! So essentially we do 742 # deep freeing, which is bad for incremental operation. In order to 743 # avoid a deep stack, we move objects to keep the ZCT small. 744 # This is performance critical! 745 const workPackage = 100 746 var L = addr(gch.zct.len) 747 748 when withRealTime: 749 var steps = workPackage 750 var t0: Ticks 751 if gch.maxPause > 0: t0 = getticks() 752 while L[] > 0: 753 var c = gch.zct.d[0] 754 sysAssert(isAllocatedPtr(gch.region, c), "CollectZCT: isAllocatedPtr") 755 # remove from ZCT: 756 gcAssert((c.refcount and ZctFlag) == ZctFlag, "collectZCT") 757 758 c.refcount = c.refcount and not ZctFlag 759 gch.zct.d[0] = gch.zct.d[L[] - 1] 760 dec(L[]) 761 when withRealTime: dec steps 762 if c.refcount <% rcIncrement: 763 # It may have a RC > 0, if it is in the hardware stack or 764 # it has not been removed yet from the ZCT. This is because 765 # ``incref`` does not bother to remove the cell from the ZCT 766 # as this might be too slow. 767 # In any case, it should be removed from the ZCT. But not 768 # freed. **KEEP THIS IN MIND WHEN MAKING THIS INCREMENTAL!** 769 logCell("zct dealloc cell", c) 770 track("zct dealloc cell", c, 0) 771 gcTrace(c, csZctFreed) 772 # We are about to free the object, call the finalizer BEFORE its 773 # children are deleted as well, because otherwise the finalizer may 774 # access invalid memory. This is done by prepareDealloc(): 775 prepareDealloc(c) 776 forAllChildren(c, waZctDecRef) 777 when reallyDealloc: 778 sysAssert(allocInv(gch.region), "collectZCT: rawDealloc") 779 beforeDealloc(gch, c, "collectZCT: stack trash") 780 rawDealloc(gch.region, c) 781 else: 782 sysAssert(c.typ != nil, "collectZCT 2") 783 zeroMem(c, sizeof(Cell)) 784 when withRealTime: 785 if steps == 0: 786 steps = workPackage 787 if gch.maxPause > 0: 788 let duration = getticks() - t0 789 # the GC's measuring is not accurate and needs some cleanup actions 790 # (stack unmarking), so subtract some short amount of time in 791 # order to miss deadlines less often: 792 if duration >= gch.maxPause - 50_000: 793 return false 794 result = true 795 796proc unmarkStackAndRegisters(gch: var GcHeap) = 797 var d = gch.decStack.d 798 for i in 0..gch.decStack.len-1: 799 sysAssert isAllocatedPtr(gch.region, d[i]), "unmarkStackAndRegisters" 800 decRef(d[i]) 801 gch.decStack.len = 0 802 803proc collectCTBody(gch: var GcHeap) {.raises: [].} = 804 when withRealTime: 805 let t0 = getticks() 806 sysAssert(allocInv(gch.region), "collectCT: begin") 807 808 when nimCoroutines: 809 for stack in gch.stack.items(): 810 gch.stat.maxStackSize = max(gch.stat.maxStackSize, stack.stackSize()) 811 else: 812 gch.stat.maxStackSize = max(gch.stat.maxStackSize, stackSize()) 813 sysAssert(gch.decStack.len == 0, "collectCT") 814 prepareForInteriorPointerChecking(gch.region) 815 markStackAndRegisters(gch) 816 gch.stat.maxStackCells = max(gch.stat.maxStackCells, gch.decStack.len) 817 inc(gch.stat.stackScans) 818 if collectZCT(gch): 819 when cycleGC: 820 if getOccupiedMem(gch.region) >= gch.cycleThreshold or alwaysCycleGC: 821 collectCycles(gch) 822 #discard collectZCT(gch) 823 inc(gch.stat.cycleCollections) 824 gch.cycleThreshold = max(InitialCycleThreshold, getOccupiedMem() * 825 CycleIncrease) 826 gch.stat.maxThreshold = max(gch.stat.maxThreshold, gch.cycleThreshold) 827 unmarkStackAndRegisters(gch) 828 sysAssert(allocInv(gch.region), "collectCT: end") 829 830 when withRealTime: 831 let duration = getticks() - t0 832 gch.stat.maxPause = max(gch.stat.maxPause, duration) 833 when defined(reportMissedDeadlines): 834 if gch.maxPause > 0 and duration > gch.maxPause: 835 c_printf("[GC] missed deadline: %ld\n", duration) 836 837proc collectCT(gch: var GcHeap) = 838 if (gch.zct.len >= gch.zctThreshold or (cycleGC and 839 getOccupiedMem(gch.region)>=gch.cycleThreshold) or alwaysGC) and 840 gch.recGcLock == 0: 841 when false: 842 prepareForInteriorPointerChecking(gch.region) 843 cellsetReset(gch.marked) 844 markForDebug(gch) 845 collectCTBody(gch) 846 gch.zctThreshold = max(InitialZctThreshold, gch.zct.len * CycleIncrease) 847 848proc GC_collectZct*() = 849 ## Collect the ZCT (zero count table). Unstable, experimental API for 850 ## testing purposes. 851 ## DO NOT USE! 852 collectCTBody(gch) 853 854when withRealTime: 855 proc toNano(x: int): Nanos {.inline.} = 856 result = x * 1000 857 858 proc GC_setMaxPause*(MaxPauseInUs: int) = 859 gch.maxPause = MaxPauseInUs.toNano 860 861 proc GC_step(gch: var GcHeap, us: int, strongAdvice: bool) = 862 gch.maxPause = us.toNano 863 if (gch.zct.len >= gch.zctThreshold or (cycleGC and 864 getOccupiedMem(gch.region)>=gch.cycleThreshold) or alwaysGC) or 865 strongAdvice: 866 collectCTBody(gch) 867 gch.zctThreshold = max(InitialZctThreshold, gch.zct.len * CycleIncrease) 868 869 proc GC_step*(us: int, strongAdvice = false, stackSize = -1) {.noinline.} = 870 if stackSize >= 0: 871 var stackTop {.volatile.}: pointer 872 gch.getActiveStack().pos = addr(stackTop) 873 874 for stack in gch.stack.items(): 875 stack.bottomSaved = stack.bottom 876 when stackIncreases: 877 stack.bottom = cast[pointer]( 878 cast[ByteAddress](stack.pos) - sizeof(pointer) * 6 - stackSize) 879 else: 880 stack.bottom = cast[pointer]( 881 cast[ByteAddress](stack.pos) + sizeof(pointer) * 6 + stackSize) 882 883 GC_step(gch, us, strongAdvice) 884 885 if stackSize >= 0: 886 for stack in gch.stack.items(): 887 stack.bottom = stack.bottomSaved 888 889when not defined(useNimRtl): 890 proc GC_disable() = 891 inc(gch.recGcLock) 892 proc GC_enable() = 893 when defined(nimDoesntTrackDefects): 894 if gch.recGcLock <= 0: 895 raise newException(AssertionDefect, 896 "API usage error: GC_enable called but GC is already enabled") 897 dec(gch.recGcLock) 898 899 proc GC_setStrategy(strategy: GC_Strategy) = 900 discard 901 902 proc GC_enableMarkAndSweep() = 903 gch.cycleThreshold = InitialCycleThreshold 904 905 proc GC_disableMarkAndSweep() = 906 gch.cycleThreshold = high(typeof(gch.cycleThreshold))-1 907 # set to the max value to suppress the cycle detector 908 909 proc GC_fullCollect() = 910 var oldThreshold = gch.cycleThreshold 911 gch.cycleThreshold = 0 # forces cycle collection 912 collectCT(gch) 913 gch.cycleThreshold = oldThreshold 914 915 proc GC_getStatistics(): string = 916 result = "[GC] total memory: " & $(getTotalMem()) & "\n" & 917 "[GC] occupied memory: " & $(getOccupiedMem()) & "\n" & 918 "[GC] stack scans: " & $gch.stat.stackScans & "\n" & 919 "[GC] stack cells: " & $gch.stat.maxStackCells & "\n" & 920 "[GC] cycle collections: " & $gch.stat.cycleCollections & "\n" & 921 "[GC] max threshold: " & $gch.stat.maxThreshold & "\n" & 922 "[GC] zct capacity: " & $gch.zct.cap & "\n" & 923 "[GC] max cycle table size: " & $gch.stat.cycleTableSize & "\n" & 924 "[GC] max pause time [ms]: " & $(gch.stat.maxPause div 1000_000) & "\n" 925 when nimCoroutines: 926 result.add "[GC] number of stacks: " & $gch.stack.len & "\n" 927 for stack in items(gch.stack): 928 result.add "[GC] stack " & stack.bottom.repr & "[GC] max stack size " & cast[pointer](stack.maxStackSize).repr & "\n" 929 else: 930 # this caused memory leaks, see #10488 ; find a way without `repr` 931 # maybe using a local copy of strutils.toHex or snprintf 932 when defined(logGC): 933 result.add "[GC] stack bottom: " & gch.stack.bottom.repr 934 result.add "[GC] max stack size: " & $gch.stat.maxStackSize & "\n" 935 936{.pop.} # profiler: off, stackTrace: off 937