1#
2#
3#            Nim's Runtime Library
4#        (c) Copyright 2015 Rokas Kupstys
5#
6#    See the file "copying.txt", included in this
7#    distribution, for details about the copyright.
8#
9
10type
11  ForeignCell* = object
12    data*: pointer
13    owner: ptr GcHeap
14
15proc protect*(x: pointer): ForeignCell =
16  nimGCref(x)
17  result.data = x
18  result.owner = addr(gch)
19
20when defined(nimTypeNames):
21  type InstancesInfo = array[400, (cstring, int, int)]
22  proc sortInstances(a: var InstancesInfo; n: int) =
23    # we use shellsort here; fast and simple
24    var h = 1
25    while true:
26      h = 3 * h + 1
27      if h > n: break
28    while true:
29      h = h div 3
30      for i in countup(h, n - 1):
31        var v = a[i]
32        var j = i
33        while a[j - h][2] < v[2]:
34          a[j] = a[j - h]
35          j = j - h
36          if j < h: break
37        a[j] = v
38      if h == 1: break
39
40  iterator dumpHeapInstances*(): tuple[name: cstring; count: int; sizes: int] =
41    ## Iterate over summaries of types on heaps.
42    ## This data may be inaccurate if allocations
43    ## are made by the iterator body.
44    if strDesc.nextType == nil:
45      strDesc.nextType = nimTypeRoot
46      strDesc.name = "string"
47      nimTypeRoot = addr strDesc
48    var it = nimTypeRoot
49    while it != nil:
50      if (it.instances > 0 or it.sizes != 0):
51        yield (it.name, it.instances, it.sizes)
52      it = it.nextType
53
54  proc dumpNumberOfInstances* =
55    var a: InstancesInfo
56    var n = 0
57    var totalAllocated = 0
58    for it in dumpHeapInstances():
59      a[n] = it
60      inc n
61      inc totalAllocated, it.sizes
62    sortInstances(a, n)
63    for i in 0 .. n-1:
64      c_fprintf(cstdout, "[Heap] %s: #%ld; bytes: %ld\n", a[i][0], a[i][1], a[i][2])
65    c_fprintf(cstdout, "[Heap] total number of bytes: %ld\n", totalAllocated)
66    when defined(nimTypeNames):
67      let (allocs, deallocs) = getMemCounters()
68      c_fprintf(cstdout, "[Heap] allocs/deallocs: %ld/%ld\n", allocs, deallocs)
69
70  when defined(nimGcRefLeak):
71    proc oomhandler() =
72      c_fprintf(cstdout, "[Heap] ROOTS: #%ld\n", gch.additionalRoots.len)
73      writeLeaks()
74
75    outOfMemHook = oomhandler
76
77template decTypeSize(cell, t) =
78  when defined(nimTypeNames):
79    if t.kind in {tyString, tySequence}:
80      let cap = cast[PGenericSeq](cellToUsr(cell)).space
81      let size =
82        if t.kind == tyString:
83          cap + 1 + GenericSeqSize
84        else:
85          align(GenericSeqSize, t.base.align) + cap * t.base.size
86      atomicDec t.sizes, size+sizeof(Cell)
87    else:
88      atomicDec t.sizes, t.base.size+sizeof(Cell)
89    atomicDec t.instances
90
91template incTypeSize(typ, size) =
92  when defined(nimTypeNames):
93    atomicInc typ.instances
94    atomicInc typ.sizes, size+sizeof(Cell)
95
96proc dispose*(x: ForeignCell) =
97  when hasThreadSupport:
98    # if we own it we can free it directly:
99    if x.owner == addr(gch):
100      nimGCunref(x.data)
101    else:
102      x.owner.toDispose.add(x.data)
103  else:
104    nimGCunref(x.data)
105
106proc isNotForeign*(x: ForeignCell): bool =
107  ## returns true if 'x' belongs to the calling thread.
108  ## No deep copy has to be performed then.
109  x.owner == addr(gch)
110
111when nimCoroutines:
112  iterator items(first: var GcStack): ptr GcStack =
113    var item = addr(first)
114    while true:
115      yield item
116      item = item.next
117      if item == addr(first):
118        break
119
120  proc append(first: var GcStack, stack: ptr GcStack) =
121    ## Append stack to the ring of stacks.
122    first.prev.next = stack
123    stack.prev = first.prev
124    first.prev = stack
125    stack.next = addr(first)
126
127  proc append(first: var GcStack): ptr GcStack =
128    ## Allocate new GcStack object, append it to the ring of stacks and return it.
129    result = cast[ptr GcStack](alloc0(sizeof(GcStack)))
130    first.append(result)
131
132  proc remove(first: var GcStack, stack: ptr GcStack) =
133    ## Remove stack from ring of stacks.
134    gcAssert(addr(first) != stack, "Main application stack can not be removed")
135    if addr(first) == stack or stack == nil:
136      return
137    stack.prev.next = stack.next
138    stack.next.prev = stack.prev
139    dealloc(stack)
140
141  proc remove(stack: ptr GcStack) =
142    gch.stack.remove(stack)
143
144  proc find(first: var GcStack, bottom: pointer): ptr GcStack =
145    ## Find stack struct based on bottom pointer. If `bottom` is nil then main
146    ## thread stack is is returned.
147    if bottom == nil:
148      return addr(gch.stack)
149
150    for stack in first.items():
151      if stack.bottom == bottom:
152        return stack
153
154  proc len(stack: var GcStack): int =
155    for _ in stack.items():
156      result = result + 1
157else:
158  # This iterator gets optimized out in forEachStackSlot().
159  iterator items(first: var GcStack): ptr GcStack = yield addr(first)
160  proc len(stack: var GcStack): int = 1
161
162when defined(nimdoc):
163  proc setupForeignThreadGc*() {.gcsafe.} =
164    ## Call this if you registered a callback that will be run from a thread not
165    ## under your control. This has a cheap thread-local guard, so the GC for
166    ## this thread will only be initialized once per thread, no matter how often
167    ## it is called.
168    ##
169    ## This function is available only when `--threads:on` and `--tlsEmulation:off`
170    ## switches are used
171    discard
172
173  proc tearDownForeignThreadGc*() {.gcsafe.} =
174    ## Call this to tear down the GC, previously initialized by `setupForeignThreadGc`.
175    ## If GC has not been previously initialized, or has already been torn down, the
176    ## call does nothing.
177    ##
178    ## This function is available only when `--threads:on` and `--tlsEmulation:off`
179    ## switches are used
180    discard
181elif declared(threadType):
182  proc setupForeignThreadGc*() {.gcsafe.} =
183    if threadType == ThreadType.None:
184      var stackTop {.volatile.}: pointer
185      nimGC_setStackBottom(addr(stackTop))
186      initGC()
187      threadType = ThreadType.ForeignThread
188
189  proc tearDownForeignThreadGc*() {.gcsafe.} =
190    if threadType != ThreadType.ForeignThread:
191      return
192    when declared(deallocOsPages): deallocOsPages()
193    threadType = ThreadType.None
194    when declared(gch): zeroMem(addr gch, sizeof(gch))
195
196else:
197  template setupForeignThreadGc*() =
198    {.error: "setupForeignThreadGc is available only when ``--threads:on`` and ``--tlsEmulation:off`` are used".}
199
200  template tearDownForeignThreadGc*() =
201    {.error: "tearDownForeignThreadGc is available only when ``--threads:on`` and ``--tlsEmulation:off`` are used".}
202
203# ----------------- stack management --------------------------------------
204#  inspired from Smart Eiffel
205
206when defined(emscripten) or defined(wasm):
207  const stackIncreases = true
208elif defined(sparc):
209  const stackIncreases = false
210elif defined(hppa) or defined(hp9000) or defined(hp9000s300) or
211     defined(hp9000s700) or defined(hp9000s800) or defined(hp9000s820):
212  const stackIncreases = true
213else:
214  const stackIncreases = false
215
216proc stackSize(stack: ptr GcStack): int {.noinline.} =
217  when nimCoroutines:
218    var pos = stack.pos
219  else:
220    var pos {.volatile, noinit.}: pointer
221    pos = addr(pos)
222
223  if pos != nil:
224    when stackIncreases:
225      result = cast[ByteAddress](pos) -% cast[ByteAddress](stack.bottom)
226    else:
227      result = cast[ByteAddress](stack.bottom) -% cast[ByteAddress](pos)
228  else:
229    result = 0
230
231proc stackSize(): int {.noinline.} =
232  result = 0
233  for stack in gch.stack.items():
234    result = result + stack.stackSize()
235
236when nimCoroutines:
237  proc setPosition(stack: ptr GcStack, position: pointer) =
238    stack.pos = position
239    stack.maxStackSize = max(stack.maxStackSize, stack.stackSize())
240
241  proc setPosition(stack: var GcStack, position: pointer) =
242    setPosition(addr(stack), position)
243
244  proc getActiveStack(gch: var GcHeap): ptr GcStack =
245    return gch.activeStack
246
247  proc isActiveStack(stack: ptr GcStack): bool =
248    return gch.activeStack == stack
249else:
250  # Stack positions do not need to be tracked if coroutines are not used.
251  proc setPosition(stack: ptr GcStack, position: pointer) = discard
252  proc setPosition(stack: var GcStack, position: pointer) = discard
253  # There is just one stack - main stack of the thread. It is active always.
254  proc getActiveStack(gch: var GcHeap): ptr GcStack = addr(gch.stack)
255  proc isActiveStack(stack: ptr GcStack): bool = true
256
257{.push stack_trace: off.}
258when nimCoroutines:
259  proc GC_addStack(bottom: pointer) {.cdecl, dynlib, exportc.} =
260    # c_fprintf(stdout, "GC_addStack: %p;\n", bottom)
261    var stack = gch.stack.append()
262    stack.bottom = bottom
263    stack.setPosition(bottom)
264
265  proc GC_removeStack(bottom: pointer) {.cdecl, dynlib, exportc.} =
266    # c_fprintf(stdout, "GC_removeStack: %p;\n", bottom)
267    gch.stack.find(bottom).remove()
268
269  proc GC_setActiveStack(bottom: pointer) {.cdecl, dynlib, exportc.} =
270    ## Sets active stack and updates current stack position.
271    # c_fprintf(stdout, "GC_setActiveStack: %p;\n", bottom)
272    var sp {.volatile.}: pointer
273    gch.activeStack = gch.stack.find(bottom)
274    gch.activeStack.setPosition(addr(sp))
275
276  proc GC_getActiveStack() : pointer {.cdecl, exportc.} =
277    return gch.activeStack.bottom
278
279when not defined(useNimRtl):
280  proc nimGC_setStackBottom(theStackBottom: pointer) =
281    # Initializes main stack of the thread.
282    when nimCoroutines:
283      if gch.stack.next == nil:
284        # Main stack was not initialized yet
285        gch.stack.next = addr(gch.stack)
286        gch.stack.prev = addr(gch.stack)
287        gch.stack.bottom = theStackBottom
288        gch.stack.maxStackSize = 0
289        gch.activeStack = addr(gch.stack)
290
291    if gch.stack.bottom == nil:
292      # This branch will not be called when -d:nimCoroutines - it is fine,
293      # because same thing is done just above.
294      #c_fprintf(stdout, "stack bottom: %p;\n", theStackBottom)
295      # the first init must be the one that defines the stack bottom:
296      gch.stack.bottom = theStackBottom
297    elif theStackBottom != gch.stack.bottom:
298      var a = cast[ByteAddress](theStackBottom) # and not PageMask - PageSize*2
299      var b = cast[ByteAddress](gch.stack.bottom)
300      #c_fprintf(stdout, "old: %p new: %p;\n",gch.stack.bottom,theStackBottom)
301      when stackIncreases:
302        gch.stack.bottom = cast[pointer](min(a, b))
303      else:
304        gch.stack.bottom = cast[pointer](max(a, b))
305
306    when nimCoroutines:
307      if theStackBottom != nil: gch.stack.bottom = theStackBottom
308
309    gch.stack.setPosition(theStackBottom)
310{.pop.}
311
312proc isOnStack(p: pointer): bool =
313  var stackTop {.volatile, noinit.}: pointer
314  stackTop = addr(stackTop)
315  var a = cast[ByteAddress](gch.getActiveStack().bottom)
316  var b = cast[ByteAddress](stackTop)
317  when not stackIncreases:
318    swap(a, b)
319  var x = cast[ByteAddress](p)
320  result = a <=% x and x <=% b
321
322when defined(sparc): # For SPARC architecture.
323  when nimCoroutines:
324    {.error: "Nim coroutines are not supported on this platform."}
325
326  template forEachStackSlot(gch, gcMark: untyped) {.dirty.} =
327    when defined(sparcv9):
328      asm  """"flushw \n" """
329    else:
330      asm  """"ta      0x3   ! ST_FLUSH_WINDOWS\n" """
331
332    var
333      max = gch.stack.bottom
334      sp: PPointer
335      stackTop: array[0..1, pointer]
336    sp = addr(stackTop[0])
337    # Addresses decrease as the stack grows.
338    while sp <= max:
339      gcMark(gch, sp[])
340      sp = cast[PPointer](cast[ByteAddress](sp) +% sizeof(pointer))
341
342elif defined(ELATE):
343  {.error: "stack marking code is to be written for this architecture".}
344
345elif stackIncreases:
346  # ---------------------------------------------------------------------------
347  # Generic code for architectures where addresses increase as the stack grows.
348  # ---------------------------------------------------------------------------
349  when defined(emscripten) or defined(wasm):
350    var
351      jmpbufSize {.importc: "sizeof(jmp_buf)", nodecl.}: int
352        # a little hack to get the size of a JmpBuf in the generated C code
353        # in a platform independent way
354
355  template forEachStackSlotAux(gch, gcMark: untyped) {.dirty.} =
356    for stack in gch.stack.items():
357      var max = cast[ByteAddress](gch.stack.bottom)
358      var sp = cast[ByteAddress](addr(registers)) -% sizeof(pointer)
359      while sp >=% max:
360        gcMark(gch, cast[PPointer](sp)[])
361        sp = sp -% sizeof(pointer)
362
363  template forEachStackSlot(gch, gcMark: untyped) {.dirty.} =
364    when defined(emscripten) or defined(wasm):
365      var registers: cint
366      forEachStackSlotAux(gch, gcMark)
367    else:
368      var registers {.noinit.}: C_JmpBuf
369      if c_setjmp(registers) == 0'i32: # To fill the C stack with registers.
370        forEachStackSlotAux(gch, gcMark)
371
372else:
373  # ---------------------------------------------------------------------------
374  # Generic code for architectures where addresses decrease as the stack grows.
375  # ---------------------------------------------------------------------------
376  template forEachStackSlot(gch, gcMark: untyped) {.dirty.} =
377    # We use a jmp_buf buffer that is in the C stack.
378    # Used to traverse the stack and registers assuming
379    # that 'setjmp' will save registers in the C stack.
380    type PStackSlice = ptr array[0..7, pointer]
381    var registers {.noinit.}: C_JmpBuf
382    # Update position of stack gc is executing in.
383    gch.getActiveStack().setPosition(addr(registers))
384    if c_setjmp(registers) == 0'i32: # To fill the C stack with registers.
385      for stack in gch.stack.items():
386        var max = cast[ByteAddress](stack.bottom)
387        var sp = cast[ByteAddress](addr(registers))
388        when defined(amd64):
389          if stack.isActiveStack():
390            # words within the jmp_buf structure may not be properly aligned.
391            let regEnd = sp +% sizeof(registers)
392            while sp <% regEnd:
393              gcMark(gch, cast[PPointer](sp)[])
394              gcMark(gch, cast[PPointer](sp +% sizeof(pointer) div 2)[])
395              sp = sp +% sizeof(pointer)
396        # Make sure sp is word-aligned
397        sp = sp and not (sizeof(pointer) - 1)
398        # loop unrolled:
399        while sp <% max - 8*sizeof(pointer):
400          gcMark(gch, cast[PStackSlice](sp)[0])
401          gcMark(gch, cast[PStackSlice](sp)[1])
402          gcMark(gch, cast[PStackSlice](sp)[2])
403          gcMark(gch, cast[PStackSlice](sp)[3])
404          gcMark(gch, cast[PStackSlice](sp)[4])
405          gcMark(gch, cast[PStackSlice](sp)[5])
406          gcMark(gch, cast[PStackSlice](sp)[6])
407          gcMark(gch, cast[PStackSlice](sp)[7])
408          sp = sp +% sizeof(pointer)*8
409        # last few entries:
410        while sp <=% max:
411          gcMark(gch, cast[PPointer](sp)[])
412          sp = sp +% sizeof(pointer)
413
414# ----------------------------------------------------------------------------
415# end of non-portable code
416# ----------------------------------------------------------------------------
417
418proc prepareDealloc(cell: PCell) {.raises: [].} =
419  when declared(useMarkForDebug):
420    when useMarkForDebug:
421      gcAssert(cell notin gch.marked, "Cell still alive!")
422  let t = cell.typ
423  if t.finalizer != nil:
424    # the finalizer could invoke something that
425    # allocates memory; this could trigger a garbage
426    # collection. Since we are already collecting we
427    # prevent recursive entering here by a lock.
428    # XXX: we should set the cell's children to nil!
429    inc(gch.recGcLock)
430    (cast[Finalizer](t.finalizer))(cellToUsr(cell))
431    dec(gch.recGcLock)
432  decTypeSize(cell, t)
433
434proc deallocHeap*(runFinalizers = true; allowGcAfterwards = true) =
435  ## Frees the thread local heap. Runs every finalizer if `runFinalizers`
436  ## is true. If `allowGcAfterwards` is true, a minimal amount of allocation
437  ## happens to ensure the GC can continue to work after the call
438  ## to `deallocHeap`.
439  template deallocCell(x) =
440    if isCell(x):
441      # cast to PCell is correct here:
442      prepareDealloc(cast[PCell](x))
443
444  if runFinalizers:
445    when not declared(allObjectsAsProc):
446      for x in allObjects(gch.region):
447        deallocCell(x)
448    else:
449      var spaceIter: ObjectSpaceIter
450      while true:
451        let x = allObjectsAsProc(gch.region, addr spaceIter)
452        if spaceIter.state < 0: break
453        deallocCell(x)
454
455  deallocOsPages(gch.region)
456  zeroMem(addr gch.region, sizeof(gch.region))
457  if allowGcAfterwards:
458    initGC()
459
460type
461  GlobalMarkerProc = proc () {.nimcall, benign, raises: [].}
462var
463  globalMarkersLen {.exportc.}: int
464  globalMarkers {.exportc.}: array[0..3499, GlobalMarkerProc]
465  threadLocalMarkersLen {.exportc.}: int
466  threadLocalMarkers {.exportc.}: array[0..3499, GlobalMarkerProc]
467  gHeapidGenerator: int
468
469proc nimRegisterGlobalMarker(markerProc: GlobalMarkerProc) {.compilerproc.} =
470  if globalMarkersLen <= high(globalMarkers):
471    globalMarkers[globalMarkersLen] = markerProc
472    inc globalMarkersLen
473  else:
474    cstderr.rawWrite("[GC] cannot register global variable; too many global variables")
475    quit 1
476
477proc nimRegisterThreadLocalMarker(markerProc: GlobalMarkerProc) {.compilerproc.} =
478  if threadLocalMarkersLen <= high(threadLocalMarkers):
479    threadLocalMarkers[threadLocalMarkersLen] = markerProc
480    inc threadLocalMarkersLen
481  else:
482    cstderr.rawWrite("[GC] cannot register thread local variable; too many thread local variables")
483    quit 1
484