fix allocator corruption for large sizes (#7338)

* fix allocator corruption for large sizes
* allow large chunks to coalesce and added test case
* use correct constants in MaxBigChunkSize

5 files changed, 92 insertions, 41 deletions

diff --git a/lib/system/alloc.nim b/lib/system/alloc.nim
index 4291013a2..6aef4f411 100644
--- a/lib/system/alloc.nim
+++ b/lib/system/alloc.nim
@@ -29,7 +29,9 @@ const
   FliOffset = 6
   RealFli = MaxFli - FliOffset
 
-  HugeChunkSize = int high(int32) - 1 # 2 GB, depends on TLSF's impl
+  # size of chunks in last matrix bin
+  MaxBigChunkSize = 1 shl MaxFli - 1 shl (MaxFli-MaxLog2Sli-1)
+  HugeChunkSize = MaxBigChunkSize + 1
 
 type
   PTrunk = ptr Trunk
@@ -154,10 +156,11 @@ proc mappingSearch(r, fl, sl: var int) {.inline.} =
   # PageSize alignment:
   let t = roundup((1 shl (msbit(uint32 r) - MaxLog2Sli)), PageSize) - 1
   r = r + t
+  r = r and not t
+  r = min(r, MaxBigChunkSize)
   fl = msbit(uint32 r)
   sl = (r shr (fl - MaxLog2Sli)) - MaxSli
   dec fl, FliOffset
-  r = r and not t
   sysAssert((r and PageMask) == 0, "mappingSearch: still not aligned")
 
 # See http://www.gii.upv.es/tlsf/files/papers/tlsf_desc.pdf for details of
@@ -518,55 +521,61 @@ proc updatePrevSize(a: var MemRegion, c: PBigChunk,
   if isAccessible(a, ri):
     ri.prevSize = prevSize or (ri.prevSize and 1)
 
+proc splitChunk2(a: var MemRegion, c: PBigChunk, size: int): PBigChunk =
+  result = cast[PBigChunk](cast[ByteAddress](c) +% size)
+  result.size = c.size - size
+  track("result.origSize", addr result.origSize, sizeof(int))
+  # XXX check if these two nil assignments are dead code given
+  # addChunkToMatrix's implementation:
+  result.next = nil
+  result.prev = nil
+  # size and not used:
+  result.prevSize = size
+  sysAssert((size and 1) == 0, "splitChunk 2")
+  sysAssert((size and PageMask) == 0,
+      "splitChunk: size is not a multiple of the PageSize")
+  updatePrevSize(a, c, result.size)
+  c.size = size
+  incl(a, a.chunkStarts, pageIndex(result))
+
+proc splitChunk(a: var MemRegion, c: PBigChunk, size: int) =
+  let rest = splitChunk2(a, c, size)
+  addChunkToMatrix(a, rest)
+
 proc freeBigChunk(a: var MemRegion, c: PBigChunk) =
   var c = c
   sysAssert(c.size >= PageSize, "freeBigChunk")
   inc(a.freeMem, c.size)
-  when coalescRight:
-    var ri = cast[PChunk](cast[ByteAddress](c) +% c.size)
-    sysAssert((cast[ByteAddress](ri) and PageMask) == 0, "freeBigChunk 2")
-    if isAccessible(a, ri) and chunkUnused(ri):
-      sysAssert(not isSmallChunk(ri), "freeBigChunk 3")
-      if not isSmallChunk(ri):
-        removeChunkFromMatrix(a, cast[PBigChunk](ri))
-        inc(c.size, ri.size)
-        excl(a.chunkStarts, pageIndex(ri))
+  c.prevSize = c.prevSize and not 1  # set 'used' to false
   when coalescLeft:
-    let prevSize = c.prevSize and not 1
+    let prevSize = c.prevSize
     if prevSize != 0:
       var le = cast[PChunk](cast[ByteAddress](c) -% prevSize)
       sysAssert((cast[ByteAddress](le) and PageMask) == 0, "freeBigChunk 4")
       if isAccessible(a, le) and chunkUnused(le):
         sysAssert(not isSmallChunk(le), "freeBigChunk 5")
-        if not isSmallChunk(le):
+        if not isSmallChunk(le) and le.size < MaxBigChunkSize:
           removeChunkFromMatrix(a, cast[PBigChunk](le))
           inc(le.size, c.size)
           excl(a.chunkStarts, pageIndex(c))
           c = cast[PBigChunk](le)
-
-  incl(a, a.chunkStarts, pageIndex(c))
-  updatePrevSize(a, c, c.size)
+          if c.size > MaxBigChunkSize:
+            let rest = splitChunk2(a, c, MaxBigChunkSize)
+            addChunkToMatrix(a, c)
+            c = rest
+  when coalescRight:
+    var ri = cast[PChunk](cast[ByteAddress](c) +% c.size)
+    sysAssert((cast[ByteAddress](ri) and PageMask) == 0, "freeBigChunk 2")
+    if isAccessible(a, ri) and chunkUnused(ri):
+      sysAssert(not isSmallChunk(ri), "freeBigChunk 3")
+      if not isSmallChunk(ri) and c.size < MaxBigChunkSize:
+        removeChunkFromMatrix(a, cast[PBigChunk](ri))
+        inc(c.size, ri.size)
+        excl(a.chunkStarts, pageIndex(ri))
+        if c.size > MaxBigChunkSize:
+          let rest = splitChunk2(a, c, MaxBigChunkSize)
+          addChunkToMatrix(a, rest)
   addChunkToMatrix(a, c)
-  # set 'used' to false:
-  c.prevSize = c.prevSize and not 1
-
-proc splitChunk(a: var MemRegion, c: PBigChunk, size: int) =
-  var rest = cast[PBigChunk](cast[ByteAddress](c) +% size)
-  rest.size = c.size - size
-  track("rest.origSize", addr rest.origSize, sizeof(int))
-  # XXX check if these two nil assignments are dead code given
-  # addChunkToMatrix's implementation:
-  rest.next = nil
-  rest.prev = nil
-  # size and not used:
-  rest.prevSize = size
-  sysAssert((size and 1) == 0, "splitChunk 2")
-  sysAssert((size and PageMask) == 0,
-      "splitChunk: size is not a multiple of the PageSize")
-  updatePrevSize(a, c, rest.size)
-  c.size = size
-  incl(a, a.chunkStarts, pageIndex(rest))
-  addChunkToMatrix(a, rest)
 
 proc getBigChunk(a: var MemRegion, size: int): PBigChunk =
   sysAssert(size > 0, "getBigChunk 2")
diff --git a/tests/system/alloc.nim b/tests/system/talloc.nim
index 7abefec2a..18396041d 100644
--- a/tests/system/alloc.nim
+++ b/tests/system/talloc.nim
@@ -8,7 +8,7 @@ x.dealloc()
 
 x = createU(int, 3)
 assert x != nil
-x.free()
+x.dealloc()
 
 x = create(int, 4)
 assert cast[ptr array[4, int]](x)[0] == 0
@@ -18,7 +18,7 @@ assert cast[ptr array[4, int]](x)[3] == 0
 
 x = x.resize(4)
 assert x != nil
-x.free()
+x.dealloc()
 
 x = cast[ptr int](allocShared(100))
 assert x != nil
@@ -26,7 +26,7 @@ deallocShared(x)
 
 x = createSharedU(int, 3)
 assert x != nil
-x.freeShared()
+x.deallocShared()
 
 x = createShared(int, 3)
 assert x != nil
@@ -37,7 +37,7 @@ assert cast[ptr array[3, int]](x)[2] == 0
 assert x != nil
 x = cast[ptr int](x.resizeShared(2))
 assert x != nil
-x.freeShared()
+x.deallocShared()
 
 x = create(int, 10)
 assert x != nil
@@ -49,4 +49,9 @@ x = createShared(int, 1)
 assert x != nil
 x = x.resizeShared(1)
 assert x != nil
-x.freeShared()
+x.deallocShared()
+
+x = cast[ptr int](alloc0(125 shl 23))
+dealloc(x)
+x = cast[ptr int](alloc0(126 shl 23))
+dealloc(x)
diff --git a/tests/system/talloc2.nim b/tests/system/talloc2.nim
new file mode 100644
index 000000000..c8cab78a1
--- /dev/null
+++ b/tests/system/talloc2.nim
@@ -0,0 +1,37 @@
+const
+  nmax = 2*1024*1024*1024
+
+proc test(n: int) =
+  var a = alloc0(9999)
+  var t = cast[ptr UncheckedArray[int8]](alloc(n))
+  var b = alloc0(9999)
+  t[0] = 1
+  t[1] = 2
+  t[n-2] = 3
+  t[n-1] = 4
+  dealloc(a)
+  dealloc(t)
+  dealloc(b)
+
+# allocator adds 48 bytes to BigChunk
+# BigChunk allocator edges at 2^n * (1 - s) for s = [1..32]/64
+proc test2(n: int) =
+  let d = n div 256  # cover edges and more
+  for i in countdown(128,1):
+    for j in [-4096, -64, -49, -48, -47, -32, 0, 4096]:
+      let b = n + j - i*d
+      if b>0 and b<=nmax:
+        test(b)
+        #echo b, ": ", getTotalMem(), " ", getOccupiedMem(), " ", getFreeMem()
+
+proc test3 =
+  var n = 1
+  while n <= nmax:
+    test2(n)
+    n *= 2
+  n = nmax
+  while n >= 1:
+    test2(n)
+    n = n div 2
+
+test3()
diff --git a/tests/system/io.nim b/tests/system/tio.nim
index 3d4df806b..3d4df806b 100644
--- a/tests/system/io.nim
+++ b/tests/system/tio.nim
diff --git a/tests/system/params.nim b/tests/system/tparams.nim
index 1358212f2..1358212f2 100644
--- a/tests/system/params.nim
+++ b/tests/system/tparams.nim