#
#
#            Nim's Runtime Library
#        (c) Copyright 2015 Andreas Rumpf
#
#    See the file "copying.txt", included in this
#    distribution, for details about the copyright.
#

# Nim high-level memory manager: It supports Boehm's GC, Go's GC, no GC and the
# native Nim GC. The native Nim GC is the default.

#{.push checks:on, assertions:on.}
{.push checks:off.}

const
  debugGC = false # we wish to debug the GC...
  logGC = false
  traceGC = false # extensive debugging
  alwaysCycleGC = false
  alwaysGC = defined(fulldebug) # collect after every memory
                                # allocation (for debugging)
  leakDetector = false
  overwriteFree = false
  trackAllocationSource = leakDetector

  cycleGC = true # (de)activate the cycle GC
  reallyDealloc = true # for debugging purposes this can be set to false
  reallyOsDealloc = true
  coalescRight = true
  coalescLeft = true
  logAlloc = false
  useCellIds = defined(corruption)

type
  PPointer = ptr pointer
  TByteArray = array[0..1000_0000, byte]
  PByte = ptr TByteArray
  PString = ptr string

# Page size of the system; in most cases 4096 bytes. For exotic OS or
# CPU this needs to be changed:
const
  PageShift = 12
  PageSize = 1 shl PageShift
  PageMask = PageSize-1

  MemAlign = 8 # also minimal allocatable memory block

  BitsPerPage = PageSize div MemAlign
  UnitsPerPage = BitsPerPage div (sizeof(int)*8)
    # how many ints do we need to describe a page:
    # on 32 bit systems this is only 16 (!)

  TrunkShift = 9
  BitsPerTrunk = 1 shl TrunkShift # needs to be power of 2 and divisible by 64
  TrunkMask = BitsPerTrunk - 1
  IntsPerTrunk = BitsPerTrunk div (sizeof(int)*8)
  IntShift = 5 + ord(sizeof(int) == 8) # 5 or 6, depending on int width
  IntMask = 1 shl IntShift - 1

proc raiseOutOfMem() {.noinline.} =
  if outOfMemHook != nil: outOfMemHook()
  echo("out of memory")
  quit(1)

when defined(boehmgc):
  when defined(windows):
    const boehmLib = "boehmgc.dll"
  elif defined(macosx):
    const boehmLib = "libgc.dylib"
  else:
    const boehmLib = "libgc.so.1"

  proc boehmGCinit {.importc: "GC_init", dynlib: boehmLib.}
  proc boehmGC_disable {.importc: "GC_disable", dynlib: boehmLib.}
  proc boehmGC_enable {.importc: "GC_enable", dynlib: boehmLib.}
  proc boehmGCincremental {.
    importc: "GC_enable_incremental", dynlib: boehmLib.}
  proc boehmGCfullCollect {.importc: "GC_gcollect", dynlib: boehmLib.}
  proc boehmAlloc(size: int): pointer {.
    importc: "GC_malloc", dynlib: boehmLib.}
  proc boehmAllocAtomic(size: int): pointer {.
    importc: "GC_malloc_atomic", dynlib: boehmLib.}
  proc boehmRealloc(p: pointer, size: int): pointer {.
    importc: "GC_realloc", dynlib: boehmLib.}
  proc boehmDealloc(p: pointer) {.importc: "GC_free", dynlib: boehmLib.}

  proc boehmGetHeapSize: int {.importc: "GC_get_heap_size", dynlib: boehmLib.}
    ## Return the number of bytes in the heap.  Excludes collector private
    ## data structures. Includes empty blocks and fragmentation loss.
    ## Includes some pages that were allocated but never written.

  proc boehmGetFreeBytes: int {.importc: "GC_get_free_bytes", dynlib: boehmLib.}
    ## Return a lower bound on the number of free bytes in the heap.

  proc boehmGetBytesSinceGC: int {.importc: "GC_get_bytes_since_gc",
    dynlib: boehmLib.}
    ## Return the number of bytes allocated since the last collection.

  proc boehmGetTotalBytes: int {.importc: "GC_get_total_bytes",
    dynlib: boehmLib.}
    ## Return the total number of bytes allocated in this process.
    ## Never decreases.

  proc allocAtomic(size: int): pointer =
    result = boehmAllocAtomic(size)
    zeroMem(result, size)

  when not defined(useNimRtl):

    proc alloc(size: Natural): pointer =
      result = boehmAlloc(size)
      if result == nil: raiseOutOfMem()
    proc alloc0(size: Natural): pointer =
      result = alloc(size)
      zeroMem(result, size)
    proc realloc(p: pointer, newsize: Natural): pointer =
      result = boehmRealloc(p, newsize)
      if result == nil: raiseOutOfMem()
    proc dealloc(p: pointer) = boehmDealloc(p)

    proc allocShared(size: Natural): pointer =
      result = boehmAlloc(size)
      if result == nil: raiseOutOfMem()
    proc allocShared0(size: Natural): pointer =
      result = alloc(size)
      zeroMem(result, size)
    proc reallocShared(p: pointer, newsize: Natural): pointer =
      result = boehmRealloc(p, newsize)
      if result == nil: raiseOutOfMem()
    proc deallocShared(p: pointer) = boehmDealloc(p)

    when hasThreadSupport:
      proc getFreeSharedMem(): int =
        boehmGetFreeBytes()
      proc getTotalSharedMem(): int =
        boehmGetHeapSize()
      proc getOccupiedSharedMem(): int =
        getTotalSharedMem() - getFreeSharedMem()

    #boehmGCincremental()

    proc GC_disable() = boehmGC_disable()
    proc GC_enable() = boehmGC_enable()
    proc GC_fullCollect() = boehmGCfullCollect()
    proc GC_setStrategy(strategy: GC_Strategy) = discard
    proc GC_enableMarkAndSweep() = discard
    proc GC_disableMarkAndSweep() = discard
    proc GC_getStatistics(): string = return ""
    proc setupForeignThreadGc*() = discard

    proc getOccupiedMem(): int = return boehmGetHeapSize()-boehmGetFreeBytes()
    proc getFreeMem(): int = return boehmGetFreeBytes()
    proc getTotalMem(): int = return boehmGetHeapSize()

    proc setStackBottom(theStackBottom: pointer) = discard

  proc initGC() =
    when defined(macosx): boehmGCinit()

  proc newObj(typ: PNimType, size: int): pointer {.compilerproc.} =
    if ntfNoRefs in typ.flags: result = allocAtomic(size)
    else: result = alloc(size)
  proc newSeq(typ: PNimType, len: int): pointer {.compilerproc.} =
    result = newObj(typ, addInt(mulInt(len, typ.base.size), GenericSeqSize))
    cast[PGenericSeq](result).len = len
    cast[PGenericSeq](result).reserved = len

  proc growObj(old: pointer, newsize: int): pointer =
    result = realloc(old, newsize)

  proc nimGCref(p: pointer) {.compilerproc, inline.} = discard
  proc nimGCunref(p: pointer) {.compilerproc, inline.} = discard

  proc unsureAsgnRef(dest: PPointer, src: pointer) {.compilerproc, inline.} =
    dest[] = src
  proc asgnRef(dest: PPointer, src: pointer) {.compilerproc, inline.} =
    dest[] = src
  proc asgnRefNoCycle(dest: PPointer, src: pointer) {.compilerproc, inline.} =
    dest[] = src

  type
    TMemRegion = object {.final, pure.}

  proc alloc(r: var TMemRegion, size: int): pointer =
    result = boehmAlloc(size)
    if result == nil: raiseOutOfMem()
  proc alloc0(r: var TMemRegion, size: int): pointer =
    result = alloc(size)
    zeroMem(result, size)
  proc dealloc(r: var TMemRegion, p: pointer) = boehmDealloc(p)
  proc deallocOsPages(r: var TMemRegion) {.inline.} = discard
  proc deallocOsPages() {.inline.} = discard

  include "system/cellsets"

elif defined(gogc):
  when defined(windows):
    const goLib = "libgo.dll"
  elif defined(macosx):
    const goLib = "libgo.dylib"
  else:
    const goLib = "libgo.so"

  proc `div`[T: SomeUnsignedInt](x, y: T): T {.magic: "DivU", noSideEffect.}
  proc `-`[T: SomeUnsignedInt](x, y: T): T {.magic: "SubU", noSideEffect.}

  proc roundup(x, v: int): int {.inline.} =
    result = (x + (v-1)) and not (v-1)

  proc initGC() = discard
  # runtime_setgcpercent is only available in GCC 5
  proc GC_disable() = discard
  proc GC_enable() = discard
  proc goRuntimeGC(force: int32) {.importc: "runtime_gc", dynlib: goLib.}
  proc GC_fullCollect() = goRuntimeGC(2)
  proc GC_setStrategy(strategy: GC_Strategy) = discard
  proc GC_enableMarkAndSweep() = discard
  proc GC_disableMarkAndSweep() = discard

  const
    goNumSizeClasses = 67

  type
    cbool {.importc: "_Bool", nodecl.} = bool

    goMStats_inner_struct = object
        size: uint32
        nmalloc: uint64
        nfree: uint64

    goMStats = object
        # General statistics.
        alloc: uint64            # bytes allocated and still in use
        total_alloc: uint64      # bytes allocated (even if freed)
        sys: uint64              # bytes obtained from system (should be sum of xxx_sys below, no locking, approximate)
        nlookup: uint64          # number of pointer lookups
        nmalloc: uint64          # number of mallocs
        nfree: uint64            # number of frees
        # Statistics about malloc heap.
        # protected by mheap.Lock
        heap_alloc: uint64       # bytes allocated and still in use
        heap_sys: uint64         # bytes obtained from system
        heap_idle: uint64        # bytes in idle spans
        heap_inuse: uint64       # bytes in non-idle spans
        heap_released: uint64    # bytes released to the OS
        heap_objects: uint64 # total number of allocated objects
        # Statistics about allocation of low-level fixed-size structures.
        # Protected by FixAlloc locks.
        stacks_inuse: uint64     # bootstrap stacks
        stacks_sys: uint64
        mspan_inuse: uint64      # MSpan structures
        mspan_sys: uint64
        mcache_inuse: uint64     # MCache structures
        mcache_sys: uint64
        buckhash_sys: uint64     # profiling bucket hash table
        gc_sys: uint64
        other_sys: uint64
        # Statistics about garbage collector.
        # Protected by mheap or stopping the world during GC.
        next_gc: uint64          # next GC (in heap_alloc time)
        last_gc: uint64          # last GC (in absolute time)
        pause_total_ns: uint64
        pause_ns: array[256, uint64]
        numgc: uint32
        enablegc: cbool
        debuggc: cbool
        # Statistics about allocation size classes.
        by_size: array[goNumSizeClasses, goMStats_inner_struct]

  proc goRuntime_ReadMemStats(a2: ptr goMStats) {.cdecl, importc: "runtime_ReadMemStats", codegenDecl: "$1 $2$3 __asm__ (\"runtime.ReadMemStats\");\n$1 $2$3", dynlib: goLib.}

  proc GC_getStatistics(): string =
    var mstats: goMStats
    goRuntime_ReadMemStats(addr mstats)
    result = "[GC] total allocated memory: " & $(mstats.total_alloc) & "\n" &
             "[GC] total memory obtained from system: " & $(mstats.sys) & "\n" &
             "[GC] occupied memory: " & $(mstats.alloc) & "\n" &
             "[GC] number of pointer lookups: " & $(mstats.nlookup) & "\n" &
             "[GC] number of mallocs: " & $(mstats.nmalloc) & "\n" &
             "[GC] number of frees: " & $(mstats.nfree) & "\n" &
             "[GC] heap objects: " & $(mstats.heap_objects) & "\n" &
             "[GC] numgc: " & $(mstats.numgc) & "\n" &
             "[GC] enablegc: " & $(mstats.enablegc) & "\n" &
             "[GC] debuggc: " & $(mstats.debuggc) & "\n" &
             "[GC] total pause time [ms]: " & $(mstats.pause_total_ns div 1000_000)
  proc setupForeignThreadGc*() = discard

  proc getOccupiedMem(): int =
    var mstats: goMStats
    goRuntime_ReadMemStats(addr mstats)
    result = int(mstats.alloc)

  proc getFreeMem(): int =
    var mstats: goMStats
    goRuntime_ReadMemStats(addr mstats)
    result = int(mstats.sys - mstats.alloc)

  proc getTotalMem(): int =
    var mstats: goMStats
    goRuntime_ReadMemStats(addr mstats)
    result = int(mstats.sys)

  proc setStackBottom(theStackBottom: pointer) = discard

  proc alloc(size: Natural): pointer =
    result = cmalloc(size)
    if result == nil: raiseOutOfMem()

  proc alloc0(size: Natural): pointer =
    result = alloc(size)
    zeroMem(result, size)

  proc realloc(p: pointer, newsize: Natural): pointer =
    result = crealloc(p, newsize)
    if result == nil: raiseOutOfMem()

  proc dealloc(p: pointer) = cfree(p)

  proc allocShared(size: Natural): pointer =
    result = cmalloc(size)
    if result == nil: raiseOutOfMem()

  proc allocShared0(size: Natural): pointer =
    result = alloc(size)
    zeroMem(result, size)

  proc reallocShared(p: pointer, newsize: Natural): pointer =
    result = crealloc(p, newsize)
    if result == nil: raiseOutOfMem()

  proc deallocShared(p: pointer) = cfree(p)

  when hasThreadSupport:
    proc getFreeSharedMem(): int = discard
    proc getTotalSharedMem(): int = discard
    proc getOccupiedSharedMem(): int = discard

  const goFlagNoZero: uint32 = 1 shl 3
  proc goRuntimeMallocGC(size: uint, typ: uint, flag: uint32): pointer {.importc: "runtime_mallocgc", dynlib: goLib.}
  proc goFree(v: pointer) {.importc: "__go_free", dynlib: goLib.}

  proc newObj(typ: PNimType, size: int): pointer {.compilerproc.} =
    result = goRuntimeMallocGC(roundup(size, sizeof(pointer)).uint, 0.uint, 0.uint32)

  proc newObjNoInit(typ: PNimType, size: int): pointer =
    result = goRuntimeMallocGC(roundup(size, sizeof(pointer)).uint, 0.uint, goFlagNoZero)

  proc newSeq(typ: PNimType, len: int): pointer {.compilerproc.} =
    result = newObj(typ, len * typ.base.size + GenericSeqSize)
    cast[PGenericSeq](result).len = len
    cast[PGenericSeq](result).reserved = len
    cast[PGenericSeq](result).elemSize = typ.base.size

  proc growObj(old: pointer, newsize: int): pointer =
    # the Go GC doesn't have a realloc
    var
      oldsize = cast[PGenericSeq](old).len * cast[PGenericSeq](old).elemSize + GenericSeqSize
    result = goRuntimeMallocGC(roundup(newsize, sizeof(pointer)).uint, 0.uint, goFlagNoZero)
    copyMem(result, old, oldsize)
    zeroMem(cast[pointer](cast[ByteAddress](result) +% oldsize), newsize - oldsize)
    goFree(old)

  proc nimGCref(p: pointer) {.compilerproc, inline.} = discard
  proc nimGCunref(p: pointer) {.compilerproc, inline.} = discard

  proc unsureAsgnRef(dest: PPointer, src: pointer) {.compilerproc, inline.} =
    dest[] = src
  proc asgnRef(dest: PPointer, src: pointer) {.compilerproc, inline.} =
    dest[] = src
  proc asgnRefNoCycle(dest: PPointer, src: pointer) {.compilerproc, inline.} =
    dest[] = src

  type
    TMemRegion = object {.final, pure.}

  proc alloc(r: var TMemRegion, size: int): pointer =
    result = alloc(size)
  proc alloc0(r: var TMemRegion, size: int): pointer =
    result = alloc0(size)
  proc dealloc(r: var TMemRegion, p: pointer) = dealloc(p)
  proc deallocOsPages(r: var TMemRegion) {.inline.} = discard
  proc deallocOsPages() {.inline.} = discard

elif defined(nogc) and defined(useMalloc):

  when not defined(useNimRtl):
    proc alloc(size: Natural): pointer =
      result = cmalloc(size)
      if result == nil: raiseOutOfMem()
    proc alloc0(size: Natural): pointer =
      result = alloc(size)
      zeroMem(result, size)
    proc realloc(p: pointer, newsize: Natural): pointer =
      result = crealloc(p, newsize)
      if result == nil: raiseOutOfMem()
    proc dealloc(p: pointer) = cfree(p)

    proc allocShared(size: Natural): pointer =
      result = cmalloc(size)
      if result == nil: raiseOutOfMem()
    proc allocShared0(size: Natural): pointer =
      result = alloc(size)
      zeroMem(result, size)
    proc reallocShared(p: pointer, newsize: Natural): pointer =
      result = crealloc(p, newsize)
      if result == nil: raiseOutOfMem()
    proc deallocShared(p: pointer) = cfree(p)

    proc GC_disable() = discard
    proc GC_enable() = discard
    proc GC_fullCollect() = discard
    proc GC_setStrategy(strategy: GC_Strategy) = discard
    proc GC_enableMarkAndSweep() = discard
    proc GC_disableMarkAndSweep() = discard
    proc GC_getStatistics(): string = return ""
    proc setupForeignThreadGc*() = discard

    proc getOccupiedMem(): int = discard
    proc getFreeMem(): int = discard
    proc getTotalMem(): int = discard

    proc setStackBottom(theStackBottom: pointer) = discard

  proc initGC() = discard

  proc newObj(typ: PNimType, size: int): pointer {.compilerproc.} =
    result = alloc(size)
  proc newSeq(typ: PNimType, len: int): pointer {.compilerproc.} =
    result = newObj(typ, addInt(mulInt(len, typ.base.size), GenericSeqSize))
    cast[PGenericSeq](result).len = len
    cast[PGenericSeq](result).reserved = len
  proc newObjNoInit(typ: PNimType, size: int): pointer =
    result = alloc(size)

  proc growObj(old: pointer, newsize: int): pointer =
    result = realloc(old, newsize)

  proc nimGCref(p: pointer) {.compilerproc, inline.} = discard
  proc nimGCunref(p: pointer) {.compilerproc, inline.} = discard

  proc unsureAsgnRef(dest: PPointer, src: pointer) {.compilerproc, inline.} =
    dest[] = src
  proc asgnRef(dest: PPointer, src: pointer) {.compilerproc, inline.} =
    dest[] = src
  proc asgnRefNoCycle(dest: PPointer, src: pointer) {.compilerproc, inline.} =
    dest[] = src

  type
    TMemRegion = object {.final, pure.}

  proc alloc(r: var TMemRegion, size: int): pointer =
    result = alloc(size)
  proc alloc0(r: var TMemRegion, size: int): pointer =
    result = alloc0(size)
  proc dealloc(r: var TMemRegion, p: pointer) = dealloc(p)
  proc deallocOsPages(r: var TMemRegion) {.inline.} = discard
  proc deallocOsPages() {.inline.} = discard

elif defined(nogc):
  # Even though we don't want the GC, we cannot simply use C's memory manager
  # because Nim's runtime wants ``realloc`` to zero out the additional
  # space which C's ``realloc`` does not. And we cannot get the old size of an
  # object, because C does not support this operation... Even though every
  # possible implementation has to have a way to determine the object's size.
  # C just sucks.
  when appType == "lib":
    {.warning: "nogc in a library context may not work".}

  include "system/alloc"

  proc initGC() = discard
  proc GC_disable() = discard
  proc GC_enable() = discard
  proc GC_fullCollect() = discard
  proc GC_setStrategy(strategy: GC_Strategy) = discard
  proc GC_enableMarkAndSweep() = discard
  proc GC_disableMarkAndSweep() = discard
  proc GC_getStatistics(): string = return ""
  proc setupForeignThreadGc*() = discard


  proc newObj(typ: PNimType, size: int): pointer {.compilerproc.} =
    result = alloc0(size)

  proc newObjNoInit(typ: PNimType, size: int): pointer =
    result = alloc(size)

  proc newSeq(typ: PNimType, len: int): pointer {.compilerproc.} =
    result = newObj(typ, addInt(mulInt(len, typ.base.size), GenericSeqSize))
    cast[PGenericSeq](result).len = len
    cast[PGenericSeq](result).reserved = len
  proc growObj(old: pointer, newsize: int): pointer =
    result = realloc(old, newsize)

  proc setStackBottom(theStackBottom: pointer) = discard
  proc nimGCref(p: pointer) {.compilerproc, inline.} = discard
  proc nimGCunref(p: pointer) {.compilerproc, inline.} = discard

  proc unsureAsgnRef(dest: PPointer, src: pointer) {.compilerproc, inline.} =
    dest[] = src
  proc asgnRef(dest: PPointer, src: pointer) {.compilerproc, inline.} =
    dest[] = src
  proc asgnRefNoCycle(dest: PPointer, src: pointer) {.compilerproc, inline.} =
    dest[] = src

  var allocator {.rtlThreadVar.}: TMemRegion
  instantiateForRegion(allocator)

  include "system/cellsets"

else:
  include "system/alloc"

  include "system/cellsets"
  when not leakDetector:
    sysAssert(sizeof(TCell) == sizeof(TFreeCell), "sizeof TFreeCell")
  when compileOption("gc", "v2"):
    include "system/gc2"
  elif defined(gcMarkAndSweep):
    # XXX use 'compileOption' here
    include "system/gc_ms"
  elif defined(gcGenerational):
    include "system/gc"
  else:
    include "system/gc"

{.pop.}