[Zodb-checkins] CVS: Packages/StorageGC - CyclicGC.py:1.12

tim@digicool.com tim@digicool.com
Mon, 23 Apr 2001 16:40:33 -0400 (EDT)


Update of /cvs-repository/Packages/StorageGC
In directory korak:/tmp/cvs-serv12758

Modified Files:
	CyclicGC.py 
Log Message:
Get rid of the ISFREE descriptor slot.  Since that was basically just a
mark bit, the same effect can be gotten via reserving an otherwise
illegal value of the "adjusted refcount" field.  This appears to reduce
descriptor storage to an absolute minimum:  one slot each for the object,
the original refcount, and the adjusted refcount.



--- Updated File CyclicGC.py in package Packages/StorageGC --
--- CyclicGC.py	2001/04/22 21:42:12	1.11
+++ CyclicGC.py	2001/04/23 20:40:32	1.12
@@ -107,9 +107,9 @@
 
 ###########################################################################
 # Indices into object descriptors.
-# An object descriptor is a 4-list of the form [OBJ, RC, ADJRC, ISFREE].
+# An object descriptor is a 3-list of the form [OBJ, RC, ADJRC].
 # A list is used instead of an object to slash the space overhead; a tuple
-# isn't used because we change the ADJRC and ISFREE fields frequently.
+# isn't used because we change the ADJRC field frequently.
 #
 # OBJ
 #     An object as obtained from the storage.
@@ -118,15 +118,16 @@
 # ADJRC
 #     Adjusted refcount:  the refcount after subtracting "internal"
 #     references, i.e. references due to objects in _allobjds.
-# ISFREE
-#     Bool.  During most of the algorithm, true when and only when we have
-#     reason to suspect OBJ is trash; by the time it ends, true when and
-#     only when we *know* OBJ is trash.  But even then, "know" is contigent
-#     upon the refcounts having not changed for the duration.
+#     The special value ADJRC_ISFREE (defined below) is eventually assigned
+#     to descriptors whose objects we can prove are unreachable from outside
+#     the transitive closure of the start set.
 
-NUM_DESCRIPTOR_SLOTS = 4
-OBJ, RC, ADJRC, ISFREE = range(NUM_DESCRIPTOR_SLOTS)
+NUM_DESCRIPTOR_SLOTS = 3
+OBJ, RC, ADJRC = range(NUM_DESCRIPTOR_SLOTS)
 
+# Special value for ADJRC field, impossible for a real refcount.
+ADJRC_ISFREE = -_sys.maxint
+
 FALSE, TRUE = range(2)
 
 class _TopologyError(Exception):
@@ -281,7 +282,6 @@
             d[OBJ]    = obj
             d[RC]     = rc
             d[ADJRC]  = rc
-            d[ISFREE] = FALSE
 
             self._obj2d[obj] = d
             self._allobjds.append(d)
@@ -336,7 +336,7 @@
                     self._increment_children(nottrash, mistakes)
 
             elif adjrc == 0:
-                d[ISFREE] = TRUE  # but not *certain* yet!
+                d[ADJRC] = ADJRC_ISFREE  # but not *certain* yet!
 
             else:
                 # If an adjusted refcount goes negative, the topology of
@@ -350,30 +350,37 @@
 
         # Here's the subtle part:  objects that _propagate_external_refs()
         # have *already* seen, that had an adjusted refcount of 0, were
-        # marked ISFREE.  But if such an object is a child of this obj,
-        # it's reachable from an externally reachable object after all, so
-        # calling it ISFREE was a mistake.  Such objects are pushed on the
-        # "mistakes" stack for the caller to propagate too, and we set
-        # their ISFREE field back to false here.
-
-        # Note:  If a child happens to have a refcount of 0 but is not
-        # ISFREE, that's nothing special:  that just means
-        # _propagate_external_refs() hasn't gotten to it yet, and, since we
-        # incrememt its refcount here, _propagate_external_refs() will
-        # never know it had a zero refcount (so it will never be marked
-        # ISFREE to begin with -- there's no mistake to undo then).
-
-        # Another subtlety:  Since ISFREE is attached to object descriptors,
-        # and there's exactly one descriptor per object, setting ISFREE to
-        # false effectively acts like a mark bit too, which in turn
-        # prevents any object from getting pushed onto the mistakes stack
-        # more than once.
+        # marked ADJRC_ISFREE.  But if such an object is a child of this
+        # obj, it's reachable from an externally reachable object after all,
+        # so calling it ADJRC_ISFREE was a mistake.  Such objects are pushed
+        # on the "mistakes" stack for the caller to propagate too, and we
+        # set their ADJRC field back to 1 here.
+
+        # Note:  If a child happens to have a refcount of 0, that's nothing
+        # special:  that just means _propagate_external_refs() hasn't gotten
+        # to it yet, and, since we incrememt its refcount here,
+        # _propagate_external_refs() will never know it had a zero refcount
+        # (so it will never be marked ADJRC_ISFREE to begin with -- there's
+        # no mistake to undo then).
+
+        # Another subtlety:  Since:
+        # a) only objects already traversed by _propagate_external_refs()
+        #    can be marked ADJRC_ISFREE, and that routine visits each object
+        #    exactly once;
+        # b) only objects marked ADJRC_ISFREE can get pushed on the mistakes
+        #    stack here;
+        # c) when pushing an ADJRC_ISFREE object on the mistakes stack here,
+        #    we take away its ADJRC_ISFREE status
+        # then once an object loses ADJRC_ISFREE status (#c) it can never
+        # regain it (#a), so that #b guarantees an object will never be
+        # pushed on the mistakes stack more than once.  That property is
+        # crucial, else we could be counting some object more than once.
 
         for d in self._get_kids_descriptors(obj):
-            d[ADJRC] += 1
-            if d[ISFREE]:
-                d[ISFREE] = FALSE
+            if d[ADJRC] == ADJRC_ISFREE:
+                d[ADJRC] = 0
                 mistakes.append(d[OBJ])
+            d[ADJRC] += 1
 
     def _extract_garbage(self):
         """Find trash in the transitive closure and pass on to gcTrash().
@@ -384,7 +391,7 @@
 
         result = []
         for d in self._allobjds:
-            if not d[ISFREE]:
+            if d[ADJRC] != ADJRC_ISFREE:
                 continue
             obj = d[OBJ]
             result.append(obj)