[ZODB-Dev] Odd output from checkbtrees.py

[Paul Winkler]

On Tue, Sep 02, 2003 at 04:08:23PM -0400, Tim Peters wrote:
> [Shane Hathaway]
> >> DCWorkflow doesn't use BTrees.  My guess is that checkbtrees is
> >> actually traversing a single object many times, making it a bug in
> >> checkbtrees.
> 
> [Paul Winkler]
> > Correct. And in fact, there were 2 issues to deal with:
> > 1) obj.__dict__.items() sometimes picks things up
> > through acquisition, as demonstrated by the problem with DCWorkflow
> > transitions (and states, BTW).
> 
> Did you and Dieter resolve your disagreement about this?

We'll find out soon I hope :-) Check my latest reply to Dieter, 
I had in fact made a mistake. There is a problem, but it's not what 
I said it was. It's obj.items that is the problem because it *can* be
acquired.

> Whether or not
> it's possible, I don't think it should matter to solving the problem of
> unbounded searching in checkbtrees.py.

obj.items() does in fact matter to this problem. You can see in
checkbtrees.py that the author expected that accessing obj.items would
sometimes raise an AttributeError; I believe the author forgot that 
items can be acquired.

> > 2) it's possible for an object to contain a reference to itself,
> > e.g. a LocalFS instance has a root attribute that (sometimes?
> > always?) points to itself. So checkbtrees.py was infinitely
> > descending into spam.root.root.root.root...
> 
> This problem seems central to me, and is worse than just objects directly
> referring to themselves.  For example, this little script:
(snip)
> builds a pair of BTrees (t and u), neither of which references itself, but
> both of which reference the other.  This also tricks checkbtrees.py into
> producing unbounded output, and is still a very simple form of what *can* go
> wrong.  A full solution requires remembering every object reachable from the
> root, never visiting an object a second time.

Ick.  Well, maybe I lucked out... I ran my patched checkbtrees.py on a > 2GB
Data.fs and did not have this problem :-)

> The attached implements that, and also strengthens checkbtrees.py by calling
> BTrees.check.check() on the btrees it finds (BTrees.check.check() didn't
> exist at the time checkbtrees.py was written, and finds some kinds of BTree
> corruption the BTree._check() method can't find).
> 
> I'd sure appreciate it if you gave it a try on your problematic .fs file!
> If acquistion still seems to be creating some kind of problem, I'd like to
> understand that better -- but nothing I saw up to this point made it clear
> that it wasn't *just* inadequate cycle detection giving you problems.  The
> main thrust of the attached is to do thorough cycle detection.

If it does so, I think it should solve my problem...
running it now :-)

I actually thought of keeping track of all visited objects but 
naively assumed that this would be undesirably expensive. We'll see.

i-may-not-know-squat-about-btrees-but-i-know-an-infinite-loop-when-it-bites-me-'ly yours,

PW

--

Paul Winkler
http://www.slinkp.com
Look! Up in the sky! It's KILL HAX0R!
(random hero from isometric.spaceninja.com)