summary refs log tree commit diff stats
path: root/lib/system/cellsets.nim
diff options
context:
space:
mode:
Diffstat (limited to 'lib/system/cellsets.nim')
-rw-r--r--[-rwxr-xr-x]lib/system/cellsets.nim248
1 files changed, 160 insertions, 88 deletions
diff --git a/lib/system/cellsets.nim b/lib/system/cellsets.nim
index 0ce83864c..92036c226 100755..100644
--- a/lib/system/cellsets.nim
+++ b/lib/system/cellsets.nim
@@ -1,81 +1,100 @@
 #
 #
-#            Nimrod's Runtime Library
-#        (c) Copyright 2009 Andreas Rumpf
+#            Nim's Runtime Library
+#        (c) Copyright 2013 Andreas Rumpf
 #
 #    See the file "copying.txt", included in this
 #    distribution, for details about the copyright.
 #
 
-# Efficient set of pointers for the GC (and repr)
+
+#[
+
+Efficient set of pointers for the GC (and repr)
+-----------------------------------------------
+
+The GC depends on an extremely efficient datastructure for storing a
+set of pointers - this is called a `CellSet` in the source code.
+Inserting, deleting and searching are done in constant time. However,
+modifying a `CellSet` during traversal leads to undefined behaviour.
+
+All operations on a CellSet have to perform efficiently. Because a Cellset can
+become huge a hash table alone is not suitable for this.
+
+We use a mixture of bitset and hash table for this. The hash table maps *pages*
+to a page descriptor. The page descriptor contains a bit for any possible cell
+address within this page. So including a cell is done as follows:
+
+- Find the page descriptor for the page the cell belongs to.
+- Set the appropriate bit in the page descriptor indicating that the
+  cell points to the start of a memory block.
+
+Removing a cell is analogous - the bit has to be set to zero.
+Single page descriptors are never deleted from the hash table. This is not
+needed as the data structures needs to be rebuilt periodically anyway.
+
+Complete traversal is done in this way::
+
+  for each page descriptor d:
+    for each bit in d:
+      if bit == 1:
+        traverse the pointer belonging to this bit
+
+]#
+
+when defined(gcOrc) or defined(gcArc) or defined(gcAtomicArc):
+  type
+    PCell = Cell
+
+  when not declaredInScope(PageShift):
+    include bitmasks
+
+else:
+  type
+    RefCount = int
+
+    Cell {.pure.} = object
+      refcount: RefCount  # the refcount and some flags
+      typ: PNimType
+      when trackAllocationSource:
+        filename: cstring
+        line: int
+      when useCellIds:
+        id: int
+
+    PCell = ptr Cell
 
 type
-  TCell {.pure.} = object
-    refcount: int  # the refcount and some flags
-    typ: PNimType
-    when debugGC:
-      filename: cstring
-      line: int
-
-  PCell = ptr TCell
-
-  PPageDesc = ptr TPageDesc
-  TBitIndex = range[0..UnitsPerPage-1]
-  TPageDesc {.final, pure.} = object
+  PPageDesc = ptr PageDesc
+  BitIndex = range[0..UnitsPerPage-1]
+  PageDesc {.final, pure.} = object
     next: PPageDesc # all nodes are connected with this pointer
-    key: TAddress   # start address at bit 0
-    bits: array[TBitIndex, int] # a bit vector
+    key: uint   # start address at bit 0
+    bits: array[BitIndex, int] # a bit vector
 
-  PPageDescArray = ptr array[0..1000_000, PPageDesc]
-  TCellSet {.final, pure.} = object
+  PPageDescArray = ptr UncheckedArray[PPageDesc]
+  CellSet {.final, pure.} = object
     counter, max: int
     head: PPageDesc
     data: PPageDescArray
 
-  PCellArray = ptr array[0..100_000_000, PCell]
-  TCellSeq {.final, pure.} = object
-    len, cap: int
-    d: PCellArray
+when defined(gcOrc) or defined(gcArc) or defined(gcAtomicArc):
+  discard
+else:
+  include cellseqs_v1
 
 # ------------------- cell set handling ---------------------------------------
 
-proc contains(s: TCellSeq, c: PCell): bool {.inline.} =
-  for i in 0 .. s.len-1:
-    if s.d[i] == c: return True
-  return False
-
-proc add(s: var TCellSeq, c: PCell) {.inline.} =
-  if s.len >= s.cap:
-    s.cap = s.cap * 3 div 2
-    var d = cast[PCellArray](alloc(s.cap * sizeof(PCell)))
-    copyMem(d, s.d, s.len * sizeof(PCell))
-    dealloc(s.d)
-    s.d = d
-    # XXX: realloc?
-  s.d[s.len] = c
-  inc(s.len)
-
-proc init(s: var TCellSeq, cap: int = 1024) =
-  s.len = 0
-  s.cap = cap
-  s.d = cast[PCellArray](alloc0(cap * sizeof(PCell)))
-
-proc deinit(s: var TCellSeq) = 
-  dealloc(s.d)
-  s.d = nil
-  s.len = 0
-  s.cap = 0
-
 const
   InitCellSetSize = 1024 # must be a power of two!
 
-proc Init(s: var TCellSet) =
+proc init(s: var CellSet) =
   s.data = cast[PPageDescArray](alloc0(InitCellSetSize * sizeof(PPageDesc)))
   s.max = InitCellSetSize-1
   s.counter = 0
   s.head = nil
 
-proc Deinit(s: var TCellSet) =
+proc deinit(s: var CellSet) =
   var it = s.head
   while it != nil:
     var n = it.next
@@ -91,33 +110,33 @@ proc nextTry(h, maxHash: int): int {.inline.} =
   # For any initial h in range(maxHash), repeating that maxHash times
   # generates each int in range(maxHash) exactly once (see any text on
   # random-number generation for proof).
-  
-proc CellSetGet(t: TCellSet, key: TAddress): PPageDesc =
+
+proc cellSetGet(t: CellSet, key: uint): PPageDesc =
   var h = cast[int](key) and t.max
   while t.data[h] != nil:
     if t.data[h].key == key: return t.data[h]
     h = nextTry(h, t.max)
   return nil
 
-proc CellSetRawInsert(t: TCellSet, data: PPageDescArray, desc: PPageDesc) =
+proc cellSetRawInsert(t: CellSet, data: PPageDescArray, desc: PPageDesc) =
   var h = cast[int](desc.key) and t.max
   while data[h] != nil:
-    assert(data[h] != desc)
+    sysAssert(data[h] != desc, "CellSetRawInsert 1")
     h = nextTry(h, t.max)
-  assert(data[h] == nil)
+  sysAssert(data[h] == nil, "CellSetRawInsert 2")
   data[h] = desc
 
-proc CellSetEnlarge(t: var TCellSet) =
+proc cellSetEnlarge(t: var CellSet) =
   var oldMax = t.max
   t.max = ((t.max+1)*2)-1
   var n = cast[PPageDescArray](alloc0((t.max + 1) * sizeof(PPageDesc)))
-  for i in 0 .. oldmax:
+  for i in 0 .. oldMax:
     if t.data[i] != nil:
-      CellSetRawInsert(t, n, t.data[i])
+      cellSetRawInsert(t, n, t.data[i])
   dealloc(t.data)
   t.data = n
 
-proc CellSetPut(t: var TCellSet, key: TAddress): PPageDesc =
+proc cellSetPut(t: var CellSet, key: uint): PPageDesc =
   var h = cast[int](key) and t.max
   while true:
     var x = t.data[h]
@@ -126,13 +145,13 @@ proc CellSetPut(t: var TCellSet, key: TAddress): PPageDesc =
     h = nextTry(h, t.max)
 
   if ((t.max+1)*2 < t.counter*3) or ((t.max+1)-t.counter < 4):
-    CellSetEnlarge(t)
+    cellSetEnlarge(t)
   inc(t.counter)
   h = cast[int](key) and t.max
   while t.data[h] != nil: h = nextTry(h, t.max)
-  assert(t.data[h] == nil)
+  sysAssert(t.data[h] == nil, "CellSetPut")
   # the new page descriptor goes into result
-  result = cast[PPageDesc](alloc0(sizeof(TPageDesc)))
+  result = cast[PPageDesc](alloc0(sizeof(PageDesc)))
   result.next = t.head
   result.key = key
   t.head = result
@@ -140,57 +159,110 @@ proc CellSetPut(t: var TCellSet, key: TAddress): PPageDesc =
 
 # ---------- slightly higher level procs --------------------------------------
 
-proc contains(s: TCellSet, cell: PCell): bool =
-  var u = cast[TAddress](cell)
-  var t = CellSetGet(s, u shr PageShift)
+proc contains(s: CellSet, cell: PCell): bool =
+  var u = cast[uint](cell)
+  var t = cellSetGet(s, u shr PageShift)
   if t != nil:
-    u = (u %% PageSize) /% MemAlign
+    u = (u mod PageSize) div MemAlign
     result = (t.bits[u shr IntShift] and (1 shl (u and IntMask))) != 0
   else:
     result = false
 
-proc incl(s: var TCellSet, cell: PCell) {.noinline.} =
-  var u = cast[TAddress](cell)
-  var t = CellSetPut(s, u shr PageShift)
-  u = (u %% PageSize) /% MemAlign
+proc incl(s: var CellSet, cell: PCell) =
+  var u = cast[uint](cell)
+  var t = cellSetPut(s, u shr PageShift)
+  u = (u mod PageSize) div MemAlign
   t.bits[u shr IntShift] = t.bits[u shr IntShift] or (1 shl (u and IntMask))
 
-proc excl(s: var TCellSet, cell: PCell) =
-  var u = cast[TAddress](cell)
-  var t = CellSetGet(s, u shr PageShift)
+proc excl(s: var CellSet, cell: PCell) =
+  var u = cast[uint](cell)
+  var t = cellSetGet(s, u shr PageShift)
   if t != nil:
-    u = (u %% PageSize) /% MemAlign
+    u = (u mod PageSize) div MemAlign
     t.bits[u shr IntShift] = (t.bits[u shr IntShift] and
                               not (1 shl (u and IntMask)))
 
-proc containsOrIncl(s: var TCellSet, cell: PCell): bool = 
-  var u = cast[TAddress](cell)
-  var t = CellSetGet(s, u shr PageShift)
+proc containsOrIncl(s: var CellSet, cell: PCell): bool =
+  var u = cast[uint](cell)
+  var t = cellSetGet(s, u shr PageShift)
   if t != nil:
-    u = (u %% PageSize) /% MemAlign
+    u = (u mod PageSize) div MemAlign
     result = (t.bits[u shr IntShift] and (1 shl (u and IntMask))) != 0
-    if not result: 
+    if not result:
       t.bits[u shr IntShift] = t.bits[u shr IntShift] or
           (1 shl (u and IntMask))
-  else: 
-    Incl(s, cell)
+  else:
+    incl(s, cell)
     result = false
 
-iterator elements(t: TCellSet): PCell {.inline.} =
+iterator elements(t: CellSet): PCell {.inline.} =
   # while traversing it is forbidden to add pointers to the tree!
   var r = t.head
   while r != nil:
-    var i = 0
-    while i <= high(r.bits):
+    var i: uint = 0
+    while int(i) <= high(r.bits):
       var w = r.bits[i] # taking a copy of r.bits[i] here is correct, because
       # modifying operations are not allowed during traversation
-      var j = 0
+      var j: uint = 0
       while w != 0:         # test all remaining bits for zero
         if (w and 1) != 0:  # the bit is set!
           yield cast[PCell]((r.key shl PageShift) or
-                              (i shl IntShift +% j) *% MemAlign)
+                              (i shl IntShift + j) * MemAlign)
         inc(j)
         w = w shr 1
       inc(i)
     r = r.next
 
+when false:
+  type
+    CellSetIter = object
+      p: PPageDesc
+      i, w, j: int
+
+  proc next(it: var CellSetIter): PCell =
+    while true:
+      while it.w != 0:         # test all remaining bits for zero
+        if (it.w and 1) != 0:  # the bit is set!
+          result = cast[PCell]((it.p.key shl PageShift) or
+                               (it.i shl IntShift +% it.j) *% MemAlign)
+
+          inc(it.j)
+          it.w = it.w shr 1
+          return
+        else:
+          inc(it.j)
+          it.w = it.w shr 1
+      # load next w:
+      if it.i >= high(it.p.bits):
+        it.i = 0
+        it.j = 0
+        it.p = it.p.next
+        if it.p == nil: return nil
+      else:
+        inc it.i
+      it.w = it.p.bits[i]
+
+  proc init(it: var CellSetIter; t: CellSet): PCell =
+    it.p = t.head
+    it.i = -1
+    it.w = 0
+    result = it.next
+
+iterator elementsExcept(t, s: CellSet): PCell {.inline.} =
+  var r = t.head
+  while r != nil:
+    let ss = cellSetGet(s, r.key)
+    var i:uint = 0
+    while int(i) <= high(r.bits):
+      var w = r.bits[i]
+      if ss != nil:
+        w = w and not ss.bits[i]
+      var j:uint = 0
+      while w != 0:
+        if (w and 1) != 0:
+          yield cast[PCell]((r.key shl PageShift) or
+                              (i shl IntShift + j) * MemAlign)
+        inc(j)
+        w = w shr 1
+      inc(i)
+    r = r.next