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

[tim@digicool.com]

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

Modified Files:
	CyclicGC.py 
Log Message:
Much simpler proof that it's safe to skip TopologyError() when gcReferences(x)
returns new stuff across calls.  But reused the "extra" <wink> doc space to
given an example of when it's *not* safe to ignore new refs.
Added a cheap assert of a key invariant.



--- Updated File CyclicGC.py in package Packages/StorageGC --
--- CyclicGC.py	2001/04/23 20:50:08	1.13
+++ CyclicGC.py	2001/04/24 21:21:08	1.14
@@ -322,6 +322,7 @@
 
         for d in self._allobjds:
             adjrc = d[ADJRC]
+            assert adjrc != ADJRC_ISFREE
 
             if adjrc > 0:
                 # This is externally reachable, so must reincrement the
@@ -443,7 +444,7 @@
             # Else this reference popped into existence after we captured
             # the initial refcount info.  So why don't we raise
             # _TopologyError?  I don't think it can hurt!  The ultimate
-            # result is the transitive closure of the root set, less
+            # result is the transitive closure of the start set, less
             # everything reachable starting from outside the TC.  Since
             # we didn't know about this node before, obj is pointing to a
             # child *outside* the TC.  That *can* make something we're
@@ -463,19 +464,22 @@
             # new reference popped up.  But this new pointer goes from
             # inside the TC (obj) to outside the TC (child):  it's going
             # "in the wrong direction" to hurt.
-            # Detail:  A path from something outside the TC to something
-            # inside the TC that contains this new pointer has to get
-            # inside the TC *before* reaching this pointer (because this
-            # pointer *starts* in the TC).  So the endpoint of that pointer
-            # was already reachable from outside the TC, and therefore also
-            # everything in the TC along the path from that endpoint to
-            # obj.  So if such a new path exists, there are no *newly*
-            # reachable objects in the TC from the start of the path up
-            # through and including obj.
-            # What about the path after obj?  Since obj ends in child, if
-            # there's a path from child to something in the TC, that path
-            # still goes from child to something in the TC without the
-            # obj->child pointer, so again the object was reachable before.
+            # Detail:  For something outside the TC to reach something
+            # inside the TC, there must be a pointer P starting outside
+            # and ending inside.  But since the new obj->child pointer
+            # goes the other direction, it's irrelevant to the existence
+            # of any such pointer (P exists whether or not obj->child does).
+            # If the ignored obj->child pointer were *within* the TC, then
+            # we'd be vulnerable; e.g.,
+            #     A <-> B -> C <- D
+            # If the start set is {A}, the TC is {A, B, C}, and of those
+            # only C is reachable from outside, so A<->B is trash.   But if
+            # a new pointer B <- C popped into existence, A<->B would no
+            # longer be trash.  We can't detect that here; we detect that
+            # later, in _extract_garbage(), by ensuring that the refcounts
+            # on trash objects haven't changed since we captured them (in
+            # this specific example, we'll eventually discover that B's
+            # refcount has changed).
         return result
 
     def _get_storage_rc(self, obj):