GC stack scanning cares about interior pointers

10 files changed, 328 insertions, 29 deletions

diff --git a/compiler/c2nim/c2nim.nim b/compiler/c2nim/c2nim.nim
index 6d7a0d6c1..e408467ef 100755
--- a/compiler/c2nim/c2nim.nim
+++ b/compiler/c2nim/c2nim.nim
@@ -44,7 +44,8 @@ proc main(infile, outfile: string, options: PParserOptions) =
   var module = parseUnit(p)
   closeParser(p)
   renderModule(module, outfile)
-  rawMessage(hintSuccessX, [$gLinesCompiled, $(getTime() - start)])
+  rawMessage(hintSuccessX, [$gLinesCompiled, $(getTime() - start), 
+                            formatSize(getTotalMem())])
 
 var
   infile = ""
diff --git a/compiler/c2nim/cparse.nim b/compiler/c2nim/cparse.nim
index f8f58347d..7be9d71c1 100755
--- a/compiler/c2nim/cparse.nim
+++ b/compiler/c2nim/cparse.nim
@@ -1594,7 +1594,7 @@ proc parseSwitch(p: var TParser): PNode =
   eat(p, pxCurlyRi)
 
 proc addStmt(sl, a: PNode) = 
-  # merge type sections is possible:
+  # merge type sections if possible:
   if a.kind != nkTypeSection or sonsLen(sl) == 0 or
       lastSon(sl).kind != nkTypeSection:
     addSon(sl, a)
diff --git a/compiler/msgs.nim b/compiler/msgs.nim
index 08bf74406..50afd47f9 100755
--- a/compiler/msgs.nim
+++ b/compiler/msgs.nim
@@ -344,7 +344,7 @@ const
     warnWriteToForeignHeap: "write to foreign heap [WriteToForeignHeap]",
     warnUser: "$1 [User]", 
     hintSuccess: "operation successful [Success]", 
-    hintSuccessX: "operation successful ($1 lines compiled; $2 sec total) [SuccessX]", 
+    hintSuccessX: "operation successful ($# lines compiled; $# sec total; $#) [SuccessX]", 
     hintLineTooLong: "line too long [LineTooLong]", 
     hintXDeclaredButNotUsed: "\'$1\' is declared but not used [XDeclaredButNotUsed]", 
     hintConvToBaseNotNeeded: "conversion to base object is not needed [ConvToBaseNotNeeded]", 
diff --git a/compiler/nimrod.nim b/compiler/nimrod.nim
index 24dbc0617..a6918ce63 100755
--- a/compiler/nimrod.nim
+++ b/compiler/nimrod.nim
@@ -61,9 +61,9 @@ proc prependCurDir(f: string): string =
   else:
     result = f
 
-proc HandleCmdLine() = 
+proc HandleCmdLine() =
   var start = epochTime()
-  if paramCount() == 0: 
+  if paramCount() == 0:
     writeCommandLineUsage()
   else:
     # Process command line arguments:
@@ -85,13 +85,15 @@ proc HandleCmdLine() =
     ProcessCmdLine(passCmd2)
     MainCommand()
     if gVerbosity >= 2: echo(GC_getStatistics())
+    #echo(GC_getStatistics())
     if msgs.gErrorCounter == 0:
       when hasTinyCBackend:
         if gCmd == cmdRun:
           tccgen.run()
-      if gCmd notin {cmdInterpret, cmdRun}: 
-        rawMessage(hintSuccessX, [$gLinesCompiled, 
-                   formatFloat(epochTime() - start, ffDecimal, 3)])
+      if gCmd notin {cmdInterpret, cmdRun}:
+        rawMessage(hintSuccessX, [$gLinesCompiled,
+                   formatFloat(epochTime() - start, ffDecimal, 3),
+                   formatSize(getTotalMem())])
       if optRun in gGlobalOptions:
         var ex = quoteIfContainsWhite(
             changeFileExt(gProjectFull, "").prependCurDir)
diff --git a/koch.nim b/koch.nim
index 98067404b..bd16dedac 100755
--- a/koch.nim
+++ b/koch.nim
@@ -36,7 +36,7 @@ Possible Commands:
   zip                      builds the installation ZIP package
   inno [options]           builds the Inno Setup installer (for Windows)
   tests                    run the testsuite
-  update                   updates nimrod to the latest version from the repo.	
+  update                   updates nimrod to the latest version from the repo
 Boot options:
   -d:release               produce a release version of the compiler
   -d:tinyc                 include the Tiny C backend (not supported on Windows)
diff --git a/lib/impure/zipfiles.nim b/lib/impure/zipfiles.nim
index 2f0be6b99..1ab51fdd7 100755
--- a/lib/impure/zipfiles.nim
+++ b/lib/impure/zipfiles.nim
@@ -1,7 +1,7 @@
 #
 #
 #            Nimrod's Runtime Library
-#        (c) Copyright 2008 Andreas Rumpf
+#        (c) Copyright 2011 Andreas Rumpf
 #
 #    See the file "copying.txt", included in this
 #    distribution, for details about the copyright.
@@ -145,7 +145,7 @@ iterator walkFiles*(z: var TZipArchive): string =
 
 
 proc extractFile*(z: var TZipArchive, srcFile: string, dest: PStream) =
-  ## extracts a file from the zip archive 'z' to the destination stream.
+  ## extracts a file from the zip archive `z` to the destination stream.
   var strm = getStream(z, srcFile)
   while true:
     if not strm.atEnd:
@@ -155,15 +155,13 @@ proc extractFile*(z: var TZipArchive, srcFile: string, dest: PStream) =
   strm.close()
 
 proc extractFile*(z: var TZipArchive, srcFile: string, dest: string) =
-  ## extracts a file from the zip archive 'z' to the destination filename.
+  ## extracts a file from the zip archive `z` to the destination filename.
   var file = newFileStream(dest, fmReadWrite)
   extractFile(z, srcFile, file)
   file.close()
 
 proc extractAll*(z: var TZipArchive, dest: string) =
-  ## extracts all files from archive 'z' to the destination directory.
+  ## extracts all files from archive `z` to the destination directory.
   for file in walkFiles(z):
-    extractFile(z, file, dest & "/" & extractFilename(file))
+    extractFile(z, file, dest / extractFilename(file))
 
-   
-   
\ No newline at end of file
diff --git a/lib/system/alloc.nim b/lib/system/alloc.nim
index f33d40b0a..9007f4844 100755
--- a/lib/system/alloc.nim
+++ b/lib/system/alloc.nim
@@ -151,14 +151,22 @@ type
     size: int                # remaining size
     acc: int                 # accumulator
     next: PLLChunk           # next low-level chunk; only needed for dealloc
+
+  PAvlNode = ptr TAvlNode
+  TAvlNode {.pure, final.} = object 
+    link: array[0..1, PAvlNode] # Left (0) and right (1) links 
+    key, upperBound: int
+    balance: int            # Balance factor 
     
   TMemRegion {.final, pure.} = object
+    minLargeObj, maxLargeObj: int
+    freeSmallChunks: array[0..SmallChunkSize div MemAlign-1, PSmallChunk]
     llmem: PLLChunk
     currMem, maxMem, freeMem: int # memory sizes (allocated from OS)
     lastSize: int # needed for the case that OS gives us pages linearly 
-    freeSmallChunks: array[0..SmallChunkSize div MemAlign-1, PSmallChunk]
     freeChunksList: PBigChunk # XXX make this a datastructure with O(1) access
     chunkStarts: TIntSet
+    root, freeAvlNodes: PAvlNode
   
 proc incCurrMem(a: var TMemRegion, bytes: int) {.inline.} = 
   inc(a.currMem, bytes)
@@ -191,7 +199,25 @@ proc llAlloc(a: var TMemRegion, size: int): pointer =
   dec(a.llmem.size, size)
   inc(a.llmem.acc, size)
   zeroMem(result, size)
-  
+
+proc allocAvlNode(a: var TMemRegion, key, upperBound: int): PAvlNode =
+  if a.freeAvlNodes != nil:
+    result = a.freeAvlNodes
+    a.freeAvlNodes = a.freeAvlNodes.link[0]
+    result.link[0] = nil
+    result.link[1] = nil
+    result.balance = 0
+  else:
+    result = cast[PAvlNode](llAlloc(a, sizeof(TAvlNode)))
+  result.key = key
+  result.upperBound = upperBound
+
+proc deallocAvlNode(a: var TMemRegion, n: PAvlNode) {.inline.} =
+  n.link[0] = a.freeAvlNodes
+  a.freeAvlNodes = n
+
+include "system/avltree"
+
 proc llDeallocAll(a: var TMemRegion) =
   var it = a.llmem
   while it != nil:
@@ -497,6 +523,7 @@ proc rawAlloc(a: var TMemRegion, requestedSize: int): pointer =
     sysAssert c.size == size, "rawAlloc 12"
     result = addr(c.data)
     sysAssert((cast[TAddress](result) and (MemAlign-1)) == 0, "rawAlloc 13")
+    add(a, cast[TAddress](result), cast[TAddress](result)+%size)
   sysAssert(isAccessible(a, result), "rawAlloc 14")
 
 proc rawAlloc0(a: var TMemRegion, requestedSize: int): pointer =
@@ -534,7 +561,9 @@ proc rawDealloc(a: var TMemRegion, p: pointer) =
     # set to 0xff to check for usage after free bugs:
     when overwriteFree: c_memset(p, -1'i32, c.size -% bigChunkOverhead())
     # free big chunk
-    freeBigChunk(a, cast[PBigChunk](c))
+    var c = cast[PBigChunk](c)
+    del(a, cast[int](addr(c.data)))
+    freeBigChunk(a, c)
 
 proc isAllocatedPtr(a: TMemRegion, p: pointer): bool = 
   if isAccessible(a, p):
@@ -550,6 +579,10 @@ proc isAllocatedPtr(a: TMemRegion, p: pointer): bool =
         var c = cast[PBigChunk](c)
         result = p == addr(c.data) and cast[ptr TFreeCell](p).zeroField >% 1
 
+proc prepareForInteriorPointerChecking(a: var TMemRegion) {.inline.} =
+  a.minLargeObj = lowGauge(a.root)
+  a.maxLargeObj = highGauge(a.root)
+
 proc interiorAllocatedPtr(a: TMemRegion, p: pointer): pointer =
   if isAccessible(a, p):
     var c = pageAddr(p)
@@ -566,6 +599,18 @@ proc interiorAllocatedPtr(a: TMemRegion, p: pointer): pointer =
         var c = cast[PBigChunk](c)
         var d = addr(c.data)
         if p >= d and cast[ptr TFreeCell](d).zeroField >% 1: result = d
+  else:
+    var q = cast[int](p)
+    if q >=% a.minLargeObj and q <=% a.maxLargeObj:
+      # this check is highly effective! Test fails for 99,96% of all checks on
+      # an x86-64.
+      var avlNode = inRange(a.root, q)
+      if avlNode != nil:
+        var k = cast[pointer](avlNode.key)
+        var c = cast[PBigChunk](pageAddr(k))
+        sysAssert(addr(c.data) == k, " k is not the same as addr(c.data)!")
+        if cast[ptr TFreeCell](k).zeroField >% 1:
+          result = k
 
 proc ptrSize(p: pointer): int =
   var x = cast[pointer](cast[TAddress](p) -% sizeof(TFreeCell))
diff --git a/lib/system/avltree.nim b/lib/system/avltree.nim
new file mode 100644
index 000000000..29c49a366
--- /dev/null
+++ b/lib/system/avltree.nim
@@ -0,0 +1,251 @@
+#
+#
+#            Nimrod's Runtime Library
+#        (c) Copyright 2011 Andreas Rumpf
+#
+#    See the file "copying.txt", included in this
+#    distribution, for details about the copyright.
+#
+
+
+## AVL balanced tree based on a C implementation by Julienne Walker
+
+const 
+  HeightLimit = 128        # Tallest allowable tree
+  
+# Two way single rotation 
+
+template singleRot(root, dir: expr): stmt =
+  block:
+    var save = root.link[1-dir]
+    root.link[1-dir] = save.link[dir]
+    save.link[dir] = root
+    root = save
+
+# Two way double rotation 
+
+template doubleRot(root, dir: expr): stmt =
+  block:
+    var save = root.link[1-dir].link[dir]
+    root.link[1-dir].link[dir] = save.link[1-dir]
+    save.link[1-dir] = root.link[1-dir]
+    root.link[1-dir] = save
+    save = root.link[1-dir]
+    root.link[1-dir] = save.link[dir]
+    save.link[dir] = root
+    root = save
+
+# Adjust balance before double rotation 
+
+template adjustBalance(root, dir, bal: expr): stmt = 
+  block:
+    var n = root.link[dir]
+    var nn = n.link[1-dir]
+    if nn.balance == 0:
+      root.balance = 0
+      n.balance = 0
+    elif nn.balance == bal:
+      root.balance = -bal
+      n.balance = 0
+    else:
+      # nn->balance == -bal 
+      root.balance = 0
+      n.balance = bal
+    nn.balance = 0
+
+# Rebalance after insertion 
+
+template insertBalance(root, dir: expr): stmt = 
+  block:
+    var n = root.link[dir]
+    var bal = if dir == 0: -1 else: +1
+    if n.balance == bal:
+      root.balance = 0
+      n.balance = 0
+      singleRot(root, 1-dir)
+    else: 
+      # n->balance == -bal 
+      adjustBalance(root, dir, bal)
+      doubleRot(root, 1-dir)
+
+# Rebalance after deletion 
+
+template removeBalance(root, dir, done: expr): stmt =
+  block:
+    var n = root.link[1-dir]
+    var bal = if dir == 0: -1 else: + 1
+    if n.balance == - bal: 
+      root.balance = 0
+      n.balance = 0
+      singleRot(root, dir)
+    elif n.balance == bal: 
+      adjustBalance(root, 1-dir, - bal)
+      doubleRot(root, dir)
+    else: 
+      # n->balance == 0 
+      root.balance = -bal
+      n.balance = bal
+      singleRot(root, dir)
+      done = true
+
+proc find(root: PAvlNode, key: int): PAvlNode = 
+  var it = root
+  while it != nil:
+    if it.key == key: return it
+    it = it.link[ord(it.key < key)]
+
+proc inRange(root: PAvlNode, key: int): PAvlNode =
+  var it = root
+  while it != nil:
+    if it.key <= key and key <= it.upperBound: return it
+    it = it.link[ord(it.key < key)]
+
+proc contains(root: PAvlNode, key: int): bool {.inline.} =
+  result = find(root, key) != nil
+
+proc maxheight(n: PAvlNode): int =
+  if n != nil:
+    result = max(maxheight(n.link[0]), maxheight(n.link[1])) + 1
+
+proc minheight(n: PAvlNode): int =
+  if n != nil:
+    result = min(minheight(n.link[0]), minheight(n.link[1])) + 1
+
+proc lowGauge(n: PAvlNode): int =
+  var it = n
+  while it != nil:
+    result = it.key
+    it = it.link[0]
+  
+proc highGauge(n: PAvlNode): int =
+  result = -1
+  var it = n
+  while it != nil:
+    result = it.upperBound
+    it = it.link[1]
+
+proc add(a: var TMemRegion, key, upperBound: int) = 
+  # Empty tree case
+  if a.root == nil:
+    a.root = allocAvlNode(a, key, upperBound)
+  else:
+    var head: TAvlNode # Temporary tree root
+    var s, t, p, q: PAvlNode
+    # Iterator and save pointer 
+    var dir: int
+    # Set up false root to ease maintenance:
+    t = addr(head)
+    t.link[1] = a.root
+    # Search down the tree, saving rebalance points
+    s = t.link[1]
+    p = s
+    while true:
+      dir = ord(p.key < key)
+      q = p.link[dir]
+      if q == nil: break 
+      if q.balance != 0:
+        t = p
+        s = q
+      p = q
+    q = allocAvlNode(a, key, upperBound)
+    p.link[dir] = q
+    # Update balance factors
+    p = s
+    while p != q:
+      dir = ord(p.key < key)
+      if dir == 0: dec p.balance
+      else: inc p.balance
+      p = p.link[dir]
+    q = s
+    # Save rebalance point for parent fix 
+    # Rebalance if necessary 
+    if abs(s.balance) > 1:
+      dir = ord(s.key < key)
+      insertBalance(s, dir)
+    # Fix parent
+    if q == head.link[1]: a.root = s
+    else: t.link[ord(q == t.link[1])] = s
+
+proc del(a: var TMemRegion, key: int) =
+  if a.root == nil: return
+  var
+    upd: array[0..HeightLimit-1, int]
+    up: array[0..HeightLimit-1, PAvlNode]
+  var top = 0
+  var it = a.root
+  # Search down tree and save path
+  while true:
+    if it == nil: return
+    elif it.key == key: break 
+    # Push direction and node onto stack 
+    upd[top] = ord(it.key < key)
+    up[top] = it
+    it = it.link[upd[top]]
+    inc top
+  # Remove the node 
+  if it.link[0] == nil or it.link[1] == nil: 
+    # Which child is not null? 
+    var dir = ord(it.link[0] == nil)
+    # Fix parent 
+    if top != 0: up[top - 1].link[upd[top - 1]] = it.link[dir]
+    else: a.root = it.link[dir]
+    deallocAvlNode(a, it)
+  else:
+    # Find the inorder successor 
+    var heir = it.link[1]
+    # Save this path too 
+    upd[top] = 1
+    up[top] = it
+    inc top
+    while heir.link[0] != nil: 
+      upd[top] = 0
+      up[top] = heir
+      inc top
+      heir = heir.link[0]
+    swap(it.key, heir.key)
+    swap(it.upperBound, heir.upperBound)
+    
+    # Unlink successor and fix parent 
+    up[top - 1].link[ord(up[top - 1] == it)] = heir.link[1]
+    deallocAvlNode(a, heir)
+  # Walk back up the search path
+  dec top
+  var done = false
+  while top >= 0 and not done:
+    # Update balance factors
+    if upd[top] != 0: dec up[top].balance
+    else: inc up[top].balance
+    # Terminate or rebalance as necessary 
+    if abs(up[top].balance) == 1: 
+      break
+    elif abs(up[top].balance) > 1: 
+      removeBalance(up[top], upd[top], done)
+      # Fix parent
+      if top != 0: up[top-1].link[upd[top-1]] = up[top]
+      else: a.root = up[0]
+    dec top
+
+when isMainModule:
+  import math
+  var
+    r: PAvlNode
+    s: seq[int]
+  const N = 1000_000
+  newSeq s, N
+
+  for i in 0..N-1:
+    var key = i #random(10_000)
+    s[i] = key
+    r.add(key, 12_000_000)
+  for i in 0..N-1:
+    var key = s[i]
+    doAssert inRange(r, key+1000) != nil
+    doAssert key in r
+  echo "Min-Height: ", minheight(r), " max-height: ", maxheight(r)
+  for i in 0..N-1:
+    var key = s[i]
+    del r, key
+    doAssert key notin r
+    
+  doAssert r == nil
+
diff --git a/lib/system/gc.nim b/lib/system/gc.nim
index f13015573..c477cadef 100755
--- a/lib/system/gc.nim
+++ b/lib/system/gc.nim
@@ -561,18 +561,17 @@ proc gcMark(gch: var TGcHeap, p: pointer) {.inline.} =
   var c = cast[TAddress](cell)
   if c >% PageSize and (c and (MemAlign-1)) == 0:
     # fast check: does it look like a cell?
-    if isAllocatedPtr(gch.region, cell): 
+    var objStart = cast[PCell](interiorAllocatedPtr(gch.region, cell))
+    if objStart != nil:
       # mark the cell:
-      cell.refcount = cell.refcount +% rcIncrement
-      add(gch.decStack, cell)
+      objStart.refcount = objStart.refcount +% rcIncrement
+      add(gch.decStack, objStart)
     when false:
-      # Care for string->cstring and seq->openArray conversions.
-      # Now the codegen deals with it, it generated ``nimKeepAlive`` calls.
-      var b = cast[PCell](c -% sizeof(TGenericSeq))
-      if isAllocatedPtr(gch.region, b):
+      if isAllocatedPtr(gch.region, cell):
+        sysAssert false, "allocated pointer but not interior?"
         # mark the cell:
-        b.refcount = b.refcount +% rcIncrement
-        add(gch.decStack, b)
+        cell.refcount = cell.refcount +% rcIncrement
+        add(gch.decStack, cell)
 
 proc nimKeepAlive(p: PGenericSeq) {.compilerRtl, noinline.} =
   var c = usrToCell(p)
@@ -778,6 +777,7 @@ proc collectCT(gch: var TGcHeap) =
       gch.recGcLock == 0:
     gch.stat.maxStackSize = max(gch.stat.maxStackSize, stackSize())
     sysAssert(gch.decStack.len == 0, "collectCT")
+    prepareForInteriorPointerChecking(gch.region)
     markStackAndRegisters(gch)
     markThreadStacks(gch)
     gch.stat.maxStackCells = max(gch.stat.maxStackCells, gch.decStack.len)
diff --git a/todo.txt b/todo.txt
index 2d38c4f01..d9718fe0b 100755
--- a/todo.txt
+++ b/todo.txt
@@ -1,8 +1,9 @@
 version 0.8.14
 ==============
 
-- GC should care about interior pointers on the stack
+- add critbits module to stdlib
 - BUG: type TX = TTable[string, int]
+- BUG: c2nim: int x[20];
 - warning for implicit openArray -> varargs conversion
 - implement explicit varargs; **but** ``len(varargs)`` problem remains! 
   --> solve by implicit conversion from varargs to openarray
@@ -33,6 +34,7 @@ version 0.9.0
 - optional indentation for 'case' statement; hm, keep in mind other syntax
   changes that people want; may turn out to be a bad idea
 - activate more thread tests
+- optimize method dispatchers
 
 Bugs
 ----