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