[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)