1#
2#            Nim's Runtime Library
3#        (c) Copyright 2016 Andreas Rumpf
4#
5#    See the file "copying.txt", included in this
6#    distribution, for details about the copyright.
7#
8
9# "Stack GC" for embedded devices or ultra performance requirements.
10
11when defined(memProfiler):
12  proc nimProfile(requestedSize: int) {.benign.}
13
14when defined(useMalloc):
15  proc roundup(x, v: int): int {.inline.} =
16    result = (x + (v-1)) and not (v-1)
17  proc emalloc(size: int): pointer {.importc: "malloc", header: "<stdlib.h>".}
18  proc efree(mem: pointer) {.importc: "free", header: "<stdlib.h>".}
19
20  proc osAllocPages(size: int): pointer {.inline.} =
21    emalloc(size)
22
23  proc osTryAllocPages(size: int): pointer {.inline.} =
24    emalloc(size)
25
26  proc osDeallocPages(p: pointer, size: int) {.inline.} =
27    efree(p)
28
29else:
30  include osalloc
31
32# We manage memory as a thread local stack. Since the allocation pointer
33# is detached from the control flow pointer, this model is vastly more
34# useful than the traditional programming model while almost as safe.
35# Individual objects can also be deleted but no coalescing is performed.
36# Stacks can also be moved from one thread to another.
37
38# We also support 'finalizers'.
39
40type
41  Finalizer {.compilerproc.} = proc (self: pointer) {.nimcall, benign.}
42    # A ref type can have a finalizer that is called before the object's
43    # storage is freed.
44
45  AlignType = BiggestFloat
46  ObjHeader = object
47    typ: PNimType
48    nextFinal: ptr ObjHeader # next object with finalizer
49
50  Chunk = ptr BaseChunk
51  BaseChunk = object
52    next: Chunk
53    size: int
54    head, tail: ptr ObjHeader # first and last object in chunk that
55                              # has a finalizer attached to it
56
57const
58  MaxSmallObject = 128
59
60type
61  FreeEntry = ptr object
62    next: FreeEntry
63  SizedFreeEntry = ptr object
64    next: SizedFreeEntry
65    size: int
66  StackPtr = object
67    bump: pointer
68    remaining: int
69    current: Chunk
70
71  MemRegion* = object
72    remaining: int
73    bump: pointer
74    head, tail: Chunk
75    nextChunkSize, totalSize: int
76    when false:
77      freeLists: array[MaxSmallObject div MemAlign, FreeEntry]
78      holes: SizedFreeEntry
79    when hasThreadSupport:
80      lock: SysLock
81
82  SeqHeader = object # minor hack ahead: Since we know that seqs
83                     # and strings cannot have finalizers, we use the field
84                     # instead for a 'region' field so that they can grow
85                     # and shrink safely.
86    typ: PNimType
87    region: ptr MemRegion
88
89var
90  tlRegion {.threadvar.}: MemRegion
91#  tempStrRegion {.threadvar.}: MemRegion  # not yet used
92
93template withRegion*(r: var MemRegion; body: untyped) =
94  let oldRegion = tlRegion
95  tlRegion = r
96  try:
97    body
98  finally:
99    r = tlRegion
100    tlRegion = oldRegion
101
102template inc(p: pointer, s: int) =
103  p = cast[pointer](cast[int](p) +% s)
104
105template dec(p: pointer, s: int) =
106  p = cast[pointer](cast[int](p) -% s)
107
108template `+!`(p: pointer, s: int): pointer =
109  cast[pointer](cast[int](p) +% s)
110
111template `-!`(p: pointer, s: int): pointer =
112  cast[pointer](cast[int](p) -% s)
113
114const nimMinHeapPages {.intdefine.} = 4
115
116proc allocSlowPath(r: var MemRegion; size: int) =
117  # we need to ensure that the underlying linked list
118  # stays small. Say we want to grab 16GB of RAM with some
119  # exponential growth function. So we allocate 16KB, then
120  # 32 KB, 64 KB, 128KB, 256KB, 512KB, 1MB, 2MB, 4MB,
121  # 8MB, 16MB, 32MB, 64MB, 128MB, 512MB, 1GB, 2GB, 4GB, 8GB,
122  # 16GB --> list contains only 20 elements! That's reasonable.
123  if (r.totalSize and 1) == 0:
124    r.nextChunkSize = if r.totalSize < 64 * 1024: PageSize*nimMinHeapPages
125                      else: r.nextChunkSize*2
126  var s = roundup(size+sizeof(BaseChunk), PageSize)
127  var fresh: Chunk
128  if s > r.nextChunkSize:
129    fresh = cast[Chunk](osAllocPages(s))
130  else:
131    fresh = cast[Chunk](osTryAllocPages(r.nextChunkSize))
132    if fresh == nil:
133      fresh = cast[Chunk](osAllocPages(s))
134      # lowest bit in totalSize is the "don't increase nextChunkSize"
135      inc r.totalSize
136    else:
137      s = r.nextChunkSize
138  fresh.size = s
139  fresh.head = nil
140  fresh.tail = nil
141  fresh.next = nil
142  inc r.totalSize, s
143  let old = r.tail
144  if old == nil:
145    r.head = fresh
146  else:
147    r.tail.next = fresh
148  r.bump = fresh +! sizeof(BaseChunk)
149  r.tail = fresh
150  r.remaining = s - sizeof(BaseChunk)
151
152proc allocFast(r: var MemRegion; size: int): pointer =
153  when false:
154    if size <= MaxSmallObject:
155      var it = r.freeLists[size div MemAlign]
156      if it != nil:
157        r.freeLists[size div MemAlign] = it.next
158        return pointer(it)
159    else:
160      var it = r.holes
161      var prev: SizedFreeEntry = nil
162      while it != nil:
163        if it.size >= size:
164          if prev != nil: prev.next = it.next
165          else: r.holes = it.next
166          return pointer(it)
167        prev = it
168        it = it.next
169  let size = roundup(size, MemAlign)
170  if size > r.remaining:
171    allocSlowPath(r, size)
172  sysAssert(size <= r.remaining, "size <= r.remaining")
173  dec(r.remaining, size)
174  result = r.bump
175  inc r.bump, size
176
177proc runFinalizers(c: Chunk) =
178  var it = c.head
179  while it != nil:
180    # indivually freed objects with finalizer stay in the list, but
181    # their typ is nil then:
182    if it.typ != nil and it.typ.finalizer != nil:
183      (cast[Finalizer](it.typ.finalizer))(it+!sizeof(ObjHeader))
184    it = it.nextFinal
185
186proc runFinalizers(c: Chunk; newbump: pointer) =
187  var it = c.head
188  var prev: ptr ObjHeader = nil
189  while it != nil:
190    let nxt = it.nextFinal
191    if it >= newbump:
192      if it.typ != nil and it.typ.finalizer != nil:
193        (cast[Finalizer](it.typ.finalizer))(it+!sizeof(ObjHeader))
194    elif prev != nil:
195      prev.nextFinal = nil
196    prev = it
197    it = nxt
198
199proc dealloc(r: var MemRegion; p: pointer; size: int) =
200  let it = cast[ptr ObjHeader](p-!sizeof(ObjHeader))
201  if it.typ != nil and it.typ.finalizer != nil:
202    (cast[Finalizer](it.typ.finalizer))(p)
203  it.typ = nil
204  # it is beneficial to not use the free lists here:
205  if r.bump -! size == p:
206    dec r.bump, size
207  when false:
208    if size <= MaxSmallObject:
209      let it = cast[FreeEntry](p)
210      it.next = r.freeLists[size div MemAlign]
211      r.freeLists[size div MemAlign] = it
212    else:
213      let it = cast[SizedFreeEntry](p)
214      it.size = size
215      it.next = r.holes
216      r.holes = it
217
218proc deallocAll(r: var MemRegion; head: Chunk) =
219  var it = head
220  while it != nil:
221    let nxt = it.next
222    runFinalizers(it)
223    dec r.totalSize, it.size
224    osDeallocPages(it, it.size)
225    it = nxt
226
227proc deallocAll*(r: var MemRegion) =
228  deallocAll(r, r.head)
229  zeroMem(addr r, sizeof r)
230
231proc obstackPtr*(r: MemRegion): StackPtr =
232  result.bump = r.bump
233  result.remaining = r.remaining
234  result.current = r.tail
235
236template computeRemaining(r): untyped =
237  r.tail.size -% (cast[int](r.bump) -% cast[int](r.tail))
238
239proc setObstackPtr*(r: var MemRegion; sp: StackPtr) =
240  # free everything after 'sp':
241  if sp.current != nil and sp.current.next != nil:
242    deallocAll(r, sp.current.next)
243    sp.current.next = nil
244    when false:
245      # better leak this memory than be sorry:
246      for i in 0..high(r.freeLists): r.freeLists[i] = nil
247      r.holes = nil
248  if r.tail != nil: runFinalizers(r.tail, sp.bump)
249
250  r.bump = sp.bump
251  r.tail = sp.current
252  r.remaining = sp.remaining
253
254proc obstackPtr*(): StackPtr = tlRegion.obstackPtr()
255proc setObstackPtr*(sp: StackPtr) = tlRegion.setObstackPtr(sp)
256proc deallocAll*() = tlRegion.deallocAll()
257
258proc deallocOsPages(r: var MemRegion) = r.deallocAll()
259
260when false:
261  let obs = obstackPtr()
262  try:
263    body
264  finally:
265    setObstackPtr(obs)
266
267template withScratchRegion*(body: untyped) =
268  let oldRegion = tlRegion
269  tlRegion = MemRegion()
270  try:
271    body
272  finally:
273    deallocAll()
274    tlRegion = oldRegion
275
276when false:
277  proc joinRegion*(dest: var MemRegion; src: MemRegion) =
278    # merging is not hard.
279    if dest.head.isNil:
280      dest.head = src.head
281    else:
282      dest.tail.next = src.head
283    dest.tail = src.tail
284    dest.bump = src.bump
285    dest.remaining = src.remaining
286    dest.nextChunkSize = max(dest.nextChunkSize, src.nextChunkSize)
287    inc dest.totalSize, src.totalSize
288
289proc isOnHeap*(r: MemRegion; p: pointer): bool =
290  # the tail chunk is the largest, so check it first. It's also special
291  # in that contains the current bump pointer:
292  if r.tail >= p and p < r.bump:
293    return true
294  var it = r.head
295  while it != r.tail:
296    if it >= p and p <= it+!it.size: return true
297    it = it.next
298
299proc rawNewObj(r: var MemRegion, typ: PNimType, size: int): pointer =
300  var res = cast[ptr ObjHeader](allocFast(r, size + sizeof(ObjHeader)))
301  res.typ = typ
302  if typ.finalizer != nil:
303    res.nextFinal = r.head.head
304    r.head.head = res
305  result = res +! sizeof(ObjHeader)
306
307proc rawNewSeq(r: var MemRegion, typ: PNimType, size: int): pointer =
308  var res = cast[ptr SeqHeader](allocFast(r, size + sizeof(SeqHeader)))
309  res.typ = typ
310  res.region = addr(r)
311  result = res +! sizeof(SeqHeader)
312
313proc newObj(typ: PNimType, size: int): pointer {.compilerRtl.} =
314  sysAssert typ.kind notin {tySequence, tyString}, "newObj cannot be used to construct seqs"
315  result = rawNewObj(tlRegion, typ, size)
316  zeroMem(result, size)
317  when defined(memProfiler): nimProfile(size)
318
319proc newObjNoInit(typ: PNimType, size: int): pointer {.compilerRtl.} =
320  sysAssert typ.kind notin {tySequence, tyString}, "newObj cannot be used to construct seqs"
321  result = rawNewObj(tlRegion, typ, size)
322  when defined(memProfiler): nimProfile(size)
323
324{.push overflowChecks: on.}
325proc newSeq(typ: PNimType, len: int): pointer {.compilerRtl.} =
326  let size = roundup(align(GenericSeqSize, typ.base.align) + len * typ.base.size, MemAlign)
327  result = rawNewSeq(tlRegion, typ, size)
328  zeroMem(result, size)
329  cast[PGenericSeq](result).len = len
330  cast[PGenericSeq](result).reserved = len
331
332proc newStr(typ: PNimType, len: int; init: bool): pointer {.compilerRtl.} =
333  let size = roundup(len + GenericSeqSize, MemAlign)
334  result = rawNewSeq(tlRegion, typ, size)
335  if init: zeroMem(result, size)
336  cast[PGenericSeq](result).len = 0
337  cast[PGenericSeq](result).reserved = len
338{.pop.}
339
340proc newObjRC1(typ: PNimType, size: int): pointer {.compilerRtl.} =
341  result = rawNewObj(tlRegion, typ, size)
342  zeroMem(result, size)
343
344proc newSeqRC1(typ: PNimType, len: int): pointer {.compilerRtl.} =
345  result = newSeq(typ, len)
346
347proc growObj(regionUnused: var MemRegion; old: pointer, newsize: int): pointer =
348  let sh = cast[ptr SeqHeader](old -! sizeof(SeqHeader))
349  let typ = sh.typ
350  result = rawNewSeq(sh.region[], typ,
351                     roundup(newsize, MemAlign))
352  let elemSize = if typ.kind == tyString: 1 else: typ.base.size
353  let elemAlign = if typ.kind == tyString: 1 else: typ.base.align
354  let oldsize = align(GenericSeqSize, elemAlign) + cast[PGenericSeq](old).len*elemSize
355  zeroMem(result +! oldsize, newsize-oldsize)
356  copyMem(result, old, oldsize)
357  dealloc(sh.region[], old, roundup(oldsize, MemAlign))
358
359proc growObj(old: pointer, newsize: int): pointer {.rtl.} =
360  result = growObj(tlRegion, old, newsize)
361
362proc unsureAsgnRef(dest: PPointer, src: pointer) {.compilerproc, inline.} =
363  dest[] = src
364proc asgnRef(dest: PPointer, src: pointer) {.compilerproc, inline.} =
365  dest[] = src
366proc asgnRefNoCycle(dest: PPointer, src: pointer) {.compilerproc, inline,
367  deprecated: "old compiler compat".} = asgnRef(dest, src)
368
369proc allocImpl(size: Natural): pointer =
370  result = c_malloc(cast[csize_t](size))
371  if result == nil: raiseOutOfMem()
372proc alloc0Impl(size: Natural): pointer =
373  result = alloc(size)
374  zeroMem(result, size)
375proc reallocImpl(p: pointer, newsize: Natural): pointer =
376  result = c_realloc(p, cast[csize_t](newsize))
377  if result == nil: raiseOutOfMem()
378proc realloc0Impl(p: pointer, oldsize, newsize: Natural): pointer =
379  result = c_realloc(p, cast[csize_t](newsize))
380  if result == nil: raiseOutOfMem()
381  if newsize > oldsize:
382    zeroMem(cast[pointer](cast[int](result) + oldsize), newsize - oldsize)
383proc deallocImpl(p: pointer) = c_free(p)
384
385proc alloc0(r: var MemRegion; size: Natural): pointer =
386  # ignore the region. That is correct for the channels module
387  # but incorrect in general. XXX
388  result = alloc0(size)
389
390proc alloc(r: var MemRegion; size: Natural): pointer =
391  # ignore the region. That is correct for the channels module
392  # but incorrect in general. XXX
393  result = alloc(size)
394
395proc dealloc(r: var MemRegion; p: pointer) = dealloc(p)
396
397proc allocSharedImpl(size: Natural): pointer =
398  result = c_malloc(cast[csize_t](size))
399  if result == nil: raiseOutOfMem()
400proc allocShared0Impl(size: Natural): pointer =
401  result = alloc(size)
402  zeroMem(result, size)
403proc reallocSharedImpl(p: pointer, newsize: Natural): pointer =
404  result = c_realloc(p, cast[csize_t](newsize))
405  if result == nil: raiseOutOfMem()
406proc reallocShared0Impl(p: pointer, oldsize, newsize: Natural): pointer =
407  result = c_realloc(p, cast[csize_t](newsize))
408  if result == nil: raiseOutOfMem()
409  if newsize > oldsize:
410    zeroMem(cast[pointer](cast[int](result) + oldsize), newsize - oldsize)
411proc deallocSharedImpl(p: pointer) = c_free(p)
412
413when hasThreadSupport:
414  proc getFreeSharedMem(): int = 0
415  proc getTotalSharedMem(): int = 0
416  proc getOccupiedSharedMem(): int = 0
417
418proc GC_disable() = discard
419proc GC_enable() = discard
420proc GC_fullCollect() = discard
421proc GC_setStrategy(strategy: GC_Strategy) = discard
422proc GC_enableMarkAndSweep() = discard
423proc GC_disableMarkAndSweep() = discard
424proc GC_getStatistics(): string = return ""
425
426proc getOccupiedMem(): int =
427  result = tlRegion.totalSize - tlRegion.remaining
428proc getFreeMem(): int = tlRegion.remaining
429proc getTotalMem(): int =
430  result = tlRegion.totalSize
431
432proc getOccupiedMem*(r: MemRegion): int =
433  result = r.totalSize - r.remaining
434proc getFreeMem*(r: MemRegion): int = r.remaining
435proc getTotalMem*(r: MemRegion): int =
436  result = r.totalSize
437
438proc nimGC_setStackBottom(theStackBottom: pointer) = discard
439
440proc nimGCref(x: pointer) {.compilerproc.} = discard
441proc nimGCunref(x: pointer) {.compilerproc.} = discard
442