Merge branch 'devel' into sighashes

7 files changed, 201 insertions, 73 deletions

diff --git a/lib/system/alloc.nim b/lib/system/alloc.nim
index 745bbbf62..3a8e8a1b6 100644
--- a/lib/system/alloc.nim
+++ b/lib/system/alloc.nim
@@ -15,6 +15,10 @@
 
 include osalloc
 
+template track(op, address, size) =
+  when defined(memTracker):
+    memTrackerOp(op, address, size)
+
 # We manage *chunks* of memory. Each chunk is a multiple of the page size.
 # Each chunk starts at an address that is divisible by the page size. Chunks
 # that are bigger than ``ChunkOsReturn`` are returned back to the operating
@@ -645,6 +649,7 @@ proc alloc(allocator: var MemRegion, size: Natural): pointer =
   cast[ptr FreeCell](result).zeroField = 1 # mark it as used
   sysAssert(not isAllocatedPtr(allocator, result), "alloc")
   result = cast[pointer](cast[ByteAddress](result) +% sizeof(FreeCell))
+  track("alloc", result, size)
 
 proc alloc0(allocator: var MemRegion, size: Natural): pointer =
   result = alloc(allocator, size)
@@ -658,6 +663,7 @@ proc dealloc(allocator: var MemRegion, p: pointer) =
   sysAssert(cast[ptr FreeCell](x).zeroField == 1, "dealloc 2")
   rawDealloc(allocator, x)
   sysAssert(not isAllocatedPtr(allocator, x), "dealloc 3")
+  track("dealloc", p, 0)
 
 proc realloc(allocator: var MemRegion, p: pointer, newsize: Natural): pointer =
   if newsize > 0:
diff --git a/lib/system/deepcopy.nim b/lib/system/deepcopy.nim
index 38cc8cbf3..c137b3cf6 100644
--- a/lib/system/deepcopy.nim
+++ b/lib/system/deepcopy.nim
@@ -7,18 +7,66 @@
 #    distribution, for details about the copyright.
 #
 
-proc genericDeepCopyAux(dest, src: pointer, mt: PNimType) {.benign.}
-proc genericDeepCopyAux(dest, src: pointer, n: ptr TNimNode) {.benign.} =
+type
+  PtrTable = ptr object
+    counter, max: int
+    data: array[0..0xff_ffff, (pointer, pointer)]
+
+template hashPtr(key: pointer): int = cast[int](key) shr 8
+template allocPtrTable: untyped =
+  cast[PtrTable](alloc0(sizeof(int)*2 + sizeof(pointer)*2*cap))
+
+proc rehash(t: PtrTable): PtrTable =
+  let cap = (t.max+1) * 2
+  result = allocPtrTable()
+  result.counter = t.counter
+  result.max = cap-1
+  for i in 0..t.max:
+    let k = t.data[i][0]
+    if k != nil:
+      var h = hashPtr(k)
+      while result.data[h and result.max][0] != nil: inc h
+      result.data[h and result.max] = t.data[i]
+  dealloc t
+
+proc initPtrTable(): PtrTable =
+  const cap = 32
+  result = allocPtrTable()
+  result.counter = 0
+  result.max = cap-1
+
+template deinit(t: PtrTable) = dealloc(t)
+
+proc get(t: PtrTable; key: pointer): pointer =
+  var h = hashPtr(key)
+  while true:
+    let k = t.data[h and t.max][0]
+    if k == nil: break
+    if k == key:
+      return t.data[h and t.max][1]
+    inc h
+
+proc put(t: var PtrTable; key, val: pointer) =
+  if (t.max+1) * 2 < t.counter * 3: t = rehash(t)
+  var h = hashPtr(key)
+  while t.data[h and t.max][0] != nil: inc h
+  t.data[h and t.max] = (key, val)
+  inc t.counter
+
+proc genericDeepCopyAux(dest, src: pointer, mt: PNimType;
+                        tab: var PtrTable) {.benign.}
+proc genericDeepCopyAux(dest, src: pointer, n: ptr TNimNode;
+                        tab: var PtrTable) {.benign.} =
   var
     d = cast[ByteAddress](dest)
     s = cast[ByteAddress](src)
   case n.kind
   of nkSlot:
     genericDeepCopyAux(cast[pointer](d +% n.offset),
-                       cast[pointer](s +% n.offset), n.typ)
+                       cast[pointer](s +% n.offset), n.typ, tab)
   of nkList:
     for i in 0..n.len-1:
-      genericDeepCopyAux(dest, src, n.sons[i])
+      genericDeepCopyAux(dest, src, n.sons[i], tab)
   of nkCase:
     var dd = selectBranch(dest, n)
     var m = selectBranch(src, n)
@@ -29,10 +77,10 @@ proc genericDeepCopyAux(dest, src: pointer, n: ptr TNimNode) {.benign.} =
     copyMem(cast[pointer](d +% n.offset), cast[pointer](s +% n.offset),
             n.typ.size)
     if m != nil:
-      genericDeepCopyAux(dest, src, m)
+      genericDeepCopyAux(dest, src, m, tab)
   of nkNone: sysAssert(false, "genericDeepCopyAux")
 
-proc genericDeepCopyAux(dest, src: pointer, mt: PNimType) =
+proc genericDeepCopyAux(dest, src: pointer, mt: PNimType; tab: var PtrTable) =
   var
     d = cast[ByteAddress](dest)
     s = cast[ByteAddress](src)
@@ -60,22 +108,22 @@ proc genericDeepCopyAux(dest, src: pointer, mt: PNimType) =
         cast[pointer](dst +% i*% mt.base.size +% GenericSeqSize),
         cast[pointer](cast[ByteAddress](s2) +% i *% mt.base.size +%
                      GenericSeqSize),
-        mt.base)
+        mt.base, tab)
   of tyObject:
     # we need to copy m_type field for tyObject, as it could be empty for
     # sequence reallocations:
     if mt.base != nil:
-      genericDeepCopyAux(dest, src, mt.base)
+      genericDeepCopyAux(dest, src, mt.base, tab)
     else:
       var pint = cast[ptr PNimType](dest)
       pint[] = cast[ptr PNimType](src)[]
-    genericDeepCopyAux(dest, src, mt.node)
+    genericDeepCopyAux(dest, src, mt.node, tab)
   of tyTuple:
-    genericDeepCopyAux(dest, src, mt.node)
+    genericDeepCopyAux(dest, src, mt.node, tab)
   of tyArray, tyArrayConstr:
     for i in 0..(mt.size div mt.base.size)-1:
       genericDeepCopyAux(cast[pointer](d +% i*% mt.base.size),
-                         cast[pointer](s +% i*% mt.base.size), mt.base)
+                         cast[pointer](s +% i*% mt.base.size), mt.base, tab)
   of tyRef:
     let s2 = cast[PPointer](src)[]
     if s2 == nil:
@@ -84,30 +132,29 @@ proc genericDeepCopyAux(dest, src: pointer, mt: PNimType) =
       let z = mt.base.deepcopy(s2)
       unsureAsgnRef(cast[PPointer](dest), z)
     else:
-      # we modify the header of the cell temporarily; instead of the type
-      # field we store a forwarding pointer. XXX This is bad when the cloning
-      # fails due to OOM etc.
-      when declared(usrToCell):
-        # unfortunately we only have cycle detection for our native GCs.
-        let x = usrToCell(s2)
-        let forw = cast[int](x.typ)
-        if (forw and 1) == 1:
-          # we stored a forwarding pointer, so let's use that:
-          let z = cast[pointer](forw and not 1)
-          unsureAsgnRef(cast[PPointer](dest), z)
-        else:
+      let z = tab.get(s2)
+      if z == nil:
+        when declared(usrToCell):
+          let x = usrToCell(s2)
           let realType = x.typ
           let z = newObj(realType, realType.base.size)
           unsureAsgnRef(cast[PPointer](dest), z)
-          x.typ = cast[PNimType](cast[int](z) or 1)
-          genericDeepCopyAux(z, s2, realType.base)
-          x.typ = realType
+          tab.put(s2, z)
+          genericDeepCopyAux(z, s2, realType.base, tab)
+        else:
+          when false:
+            # addition check disabled
+            let x = usrToCell(s2)
+            let realType = x.typ
+            sysAssert realType == mt, " types do differ"
+          # this version should work for any possible GC:
+          let size = if mt.base.kind == tyObject: cast[ptr PNimType](s2)[].size else: mt.base.size
+          let z = newObj(mt, size)
+          unsureAsgnRef(cast[PPointer](dest), z)
+          tab.put(s2, z)
+          genericDeepCopyAux(z, s2, mt.base, tab)
       else:
-        let size = if mt.base.kind == tyObject: cast[ptr PNimType](s2)[].size
-                   else: mt.base.size
-        let z = newObj(mt, size)
         unsureAsgnRef(cast[PPointer](dest), z)
-        genericDeepCopyAux(z, s2, mt.base)
   of tyPtr:
     # no cycle check here, but also not really required
     let s2 = cast[PPointer](src)[]
@@ -120,7 +167,9 @@ proc genericDeepCopyAux(dest, src: pointer, mt: PNimType) =
 
 proc genericDeepCopy(dest, src: pointer, mt: PNimType) {.compilerProc.} =
   GC_disable()
-  genericDeepCopyAux(dest, src, mt)
+  var tab = initPtrTable()
+  genericDeepCopyAux(dest, src, mt, tab)
+  deinit tab
   GC_enable()
 
 proc genericSeqDeepCopy(dest, src: pointer, mt: PNimType) {.compilerProc.} =
diff --git a/lib/system/excpt.nim b/lib/system/excpt.nim
index dcf41b67d..d00ab64b1 100644
--- a/lib/system/excpt.nim
+++ b/lib/system/excpt.nim
@@ -339,6 +339,8 @@ when not defined(noSignalHandler):
           action("unknown signal\n")
 
     # print stack trace and quit
+    when defined(memtracker):
+      logPendingOps()
     when hasSomeStackTrace:
       GC_disable()
       var buf = newStringOfCap(2000)
diff --git a/lib/system/gc.nim b/lib/system/gc.nim
index 11897ce80..7fb4c7ac7 100644
--- a/lib/system/gc.nim
+++ b/lib/system/gc.nim
@@ -445,6 +445,15 @@ proc gcInvariant*() =
     markForDebug(gch)
 {.pop.}
 
+template setFrameInfo(c: PCell) =
+  when leakDetector:
+    if framePtr != nil and framePtr.prev != nil:
+      c.filename = framePtr.prev.filename
+      c.line = framePtr.prev.line
+    else:
+      c.filename = nil
+      c.line = 0
+
 proc rawNewObj(typ: PNimType, size: int, gch: var GcHeap): pointer =
   # generates a new object and sets its reference counter to 0
   sysAssert(allocInv(gch.region), "rawNewObj begin")
@@ -455,19 +464,14 @@ proc rawNewObj(typ: PNimType, size: int, gch: var GcHeap): pointer =
   gcAssert((cast[ByteAddress](res) and (MemAlign-1)) == 0, "newObj: 2")
   # now it is buffered in the ZCT
   res.typ = typ
-  when leakDetector:
-    res.filename = nil
-    res.line = 0
-    when not hasThreadSupport:
-      if framePtr != nil and framePtr.prev != nil:
-        res.filename = framePtr.prev.filename
-        res.line = framePtr.prev.line
+  setFrameInfo(res)
   # refcount is zero, color is black, but mark it to be in the ZCT
   res.refcount = ZctFlag
   sysAssert(isAllocatedPtr(gch.region, res), "newObj: 3")
   # its refcount is zero, so add it to the ZCT:
   addNewObjToZCT(res, gch)
   when logGC: writeCell("new cell", res)
+  track("rawNewObj", res, size)
   gcTrace(res, csAllocated)
   release(gch)
   when useCellIds:
@@ -509,16 +513,11 @@ proc newObjRC1(typ: PNimType, size: int): pointer {.compilerRtl.} =
   sysAssert((cast[ByteAddress](res) and (MemAlign-1)) == 0, "newObj: 2")
   # now it is buffered in the ZCT
   res.typ = typ
-  when leakDetector:
-    res.filename = nil
-    res.line = 0
-    when not hasThreadSupport:
-      if framePtr != nil and framePtr.prev != nil:
-        res.filename = framePtr.prev.filename
-        res.line = framePtr.prev.line
+  setFrameInfo(res)
   res.refcount = rcIncrement # refcount is 1
   sysAssert(isAllocatedPtr(gch.region, res), "newObj: 3")
   when logGC: writeCell("new cell", res)
+  track("newObjRC1", res, size)
   gcTrace(res, csAllocated)
   release(gch)
   when useCellIds:
@@ -561,6 +560,8 @@ proc growObj(old: pointer, newsize: int, gch: var GcHeap): pointer =
     writeCell("growObj new cell", res)
   gcTrace(ol, csZctFreed)
   gcTrace(res, csAllocated)
+  track("growObj old", ol, 0)
+  track("growObj new", res, newsize)
   when reallyDealloc:
     sysAssert(allocInv(gch.region), "growObj before dealloc")
     if ol.refcount shr rcShift <=% 1:
@@ -604,6 +605,7 @@ proc growObj(old: pointer, newsize: int): pointer {.rtl.} =
 proc freeCyclicCell(gch: var GcHeap, c: PCell) =
   prepareDealloc(c)
   gcTrace(c, csCycFreed)
+  track("cycle collector dealloc cell", c, 0)
   when logGC: writeCell("cycle collector dealloc cell", c)
   when reallyDealloc:
     sysAssert(allocInv(gch.region), "free cyclic cell")
@@ -673,6 +675,7 @@ proc doOperation(p: pointer, op: WalkOp) =
     gcAssert(c.refcount >=% rcIncrement, "doOperation 2")
     #c.refcount = c.refcount -% rcIncrement
     when logGC: writeCell("decref (from doOperation)", c)
+    track("waZctDecref", p, 0)
     decRef(c)
     #if c.refcount <% rcIncrement: addZCT(gch.zct, c)
   of waPush:
@@ -765,6 +768,7 @@ proc collectZCT(gch: var GcHeap): bool =
       # In any case, it should be removed from the ZCT. But not
       # freed. **KEEP THIS IN MIND WHEN MAKING THIS INCREMENTAL!**
       when logGC: writeCell("zct dealloc cell", c)
+      track("zct dealloc cell", c, 0)
       gcTrace(c, csZctFreed)
       # We are about to free the object, call the finalizer BEFORE its
       # children are deleted as well, because otherwise the finalizer may
diff --git a/lib/system/hti.nim b/lib/system/hti.nim
index 892a209df..d5cca7c1c 100644
--- a/lib/system/hti.nim
+++ b/lib/system/hti.nim
@@ -86,6 +86,8 @@ type
     finalizer: pointer # the finalizer for the type
     marker: proc (p: pointer, op: int) {.nimcall, benign.} # marker proc for GC
     deepcopy: proc (p: pointer): pointer {.nimcall, benign.}
+    when defined(nimTypeNames):
+      name: cstring
   PNimType = ptr TNimType
 
 # node.len may be the ``first`` element of a set
diff --git a/lib/system/memtracker.nim b/lib/system/memtracker.nim
new file mode 100644
index 000000000..a9767bbca
--- /dev/null
+++ b/lib/system/memtracker.nim
@@ -0,0 +1,70 @@
+#
+#
+#            Nim's Runtime Library
+#        (c) Copyright 2016 Andreas Rumpf
+#
+#    See the file "copying.txt", included in this
+#    distribution, for details about the copyright.
+#
+
+## Memory tracking support for Nim.
+
+when not defined(memTracker):
+  {.error: "Memory tracking support is turned off! Enable memory tracking by passing `--memtracker:on` to the compiler (see the Nim Compiler User Guide for more options).".}
+
+when defined(noSignalHandler):
+  {.error: "Memory tracking works better with the default signal handler.".}
+
+# We don't want to memtrack the tracking code ...
+{.push memtracker: off.}
+
+type
+  LogEntry* = object
+    op*: cstring
+    address*: pointer
+    size*: int
+    file*: cstring
+    line*: int
+  TrackLog* = object
+    count*: int
+    disabled: bool
+    data*: array[4000, LogEntry]
+  TrackLogger* = proc (log: TrackLog) {.nimcall, tags: [], locks: 0.}
+
+var
+  gLog*: TrackLog
+  gLogger*: TrackLogger = proc (log: TrackLog) = discard
+
+proc setTrackLogger*(logger: TrackLogger) =
+  gLogger = logger
+
+proc addEntry(entry: LogEntry) =
+  if not gLog.disabled:
+    if gLog.count > high(gLog.data):
+      gLogger(gLog)
+      gLog.count = 0
+    gLog.data[gLog.count] = entry
+    inc gLog.count
+
+proc memTrackerWrite(address: pointer; size: int; file: cstring; line: int) {.compilerProc.} =
+  addEntry LogEntry(op: "write", address: address,
+      size: size, file: file, line: line)
+
+proc memTrackerOp*(op: cstring; address: pointer; size: int) =
+  addEntry LogEntry(op: op, address: address, size: size,
+      file: "", line: 0)
+
+proc memTrackerDisable*() =
+  gLog.disabled = true
+
+proc memTrackerEnable*() =
+  gLog.disabled = false
+
+proc logPendingOps() {.noconv.} =
+  # forward declared and called from Nim's signal handler.
+  gLogger(gLog)
+  gLog.count = 0
+
+addQuitProc logPendingOps
+
+{.pop.}
diff --git a/lib/system/sysstr.nim b/lib/system/sysstr.nim
index 3a93221e0..11034006a 100644
--- a/lib/system/sysstr.nim
+++ b/lib/system/sysstr.nim
@@ -263,27 +263,32 @@ proc setLengthSeq(seq: PGenericSeq, elemSize, newLen: int): PGenericSeq {.
   result.len = newLen
 
 # --------------- other string routines ----------------------------------
-proc nimIntToStr(x: int): string {.compilerRtl.} =
-  result = newString(sizeof(x)*4)
+proc add*(result: var string; x: int64) =
+  let base = result.len
+  setLen(result, base + sizeof(x)*4)
   var i = 0
   var y = x
   while true:
     var d = y div 10
-    result[i] = chr(abs(int(y - d*10)) + ord('0'))
+    result[base+i] = chr(abs(int(y - d*10)) + ord('0'))
     inc(i)
     y = d
     if y == 0: break
   if x < 0:
-    result[i] = '-'
+    result[base+i] = '-'
     inc(i)
-  setLen(result, i)
+  setLen(result, base+i)
   # mirror the string:
   for j in 0..i div 2 - 1:
-    swap(result[j], result[i-j-1])
+    swap(result[base+j], result[base+i-j-1])
 
-proc nimFloatToStr(f: float): string {.compilerproc.} =
+proc nimIntToStr(x: int): string {.compilerRtl.} =
+  result = newStringOfCap(sizeof(x)*4)
+  result.add x
+
+proc add*(result: var string; x: float) =
   var buf: array[0..64, char]
-  var n: int = c_sprintf(buf, "%.16g", f)
+  var n: int = c_sprintf(buf, "%.16g", x)
   var hasDot = false
   for i in 0..n-1:
     if buf[i] == ',':
@@ -298,14 +303,18 @@ proc nimFloatToStr(f: float): string {.compilerproc.} =
   # On Windows nice numbers like '1.#INF', '-1.#INF' or '1.#NAN' are produced.
   # We want to get rid of these here:
   if buf[n-1] in {'n', 'N'}:
-    result = "nan"
+    result.add "nan"
   elif buf[n-1] == 'F':
     if buf[0] == '-':
-      result = "-inf"
+      result.add "-inf"
     else:
-      result = "inf"
+      result.add "inf"
   else:
-    result = $buf
+    result.add buf
+
+proc nimFloatToStr(f: float): string {.compilerproc.} =
+  result = newStringOfCap(8)
+  result.add f
 
 proc c_strtod(buf: cstring, endptr: ptr cstring): float64 {.
   importc: "strtod", header: "<stdlib.h>", noSideEffect.}
@@ -469,22 +478,8 @@ proc nimParseBiggestFloat(s: string, number: var BiggestFloat,
   number = c_strtod(t, nil)
 
 proc nimInt64ToStr(x: int64): string {.compilerRtl.} =
-  result = newString(sizeof(x)*4)
-  var i = 0
-  var y = x
-  while true:
-    var d = y div 10
-    result[i] = chr(abs(int(y - d*10)) + ord('0'))
-    inc(i)
-    y = d
-    if y == 0: break
-  if x < 0:
-    result[i] = '-'
-    inc(i)
-  setLen(result, i)
-  # mirror the string:
-  for j in 0..i div 2 - 1:
-    swap(result[j], result[i-j-1])
+  result = newStringOfCap(sizeof(x)*4)
+  result.add x
 
 proc nimBoolToStr(x: bool): string {.compilerRtl.} =
   return if x: "true" else: "false"