[ZODB-Dev] Re: BTrees q [Fwd: [Zope-dev] More Transience weirdness in 2.7.1b1]

[Chris McDonough]

Chris asks a lot of questions below and has few answers.

On Wed, 2004-06-02 at 22:21, Tim Peters wrote:
> It's more of a required invariant for sane operation, and tons of code
> cooperates in ensuring its truth, including that the BTree code never
> creates a bucket with length 0 (well, not that you can see:  it unlinks any
> empty buckets that may occur before it returns).  So it's something I'd like
> to assert instead.  Alas, user code can break the invariant, so it has to be
> checked.  This check wasn't always there.  It was introduced after Steve
> Alexander provoked segfaults with code like this:
> 
>     thekeys = somebtree.keys()
>     while True:
>         del somebtree[thekeys[0]]
> 
> That leaves "currentoffset" and "pseudoindex" at 0 the whole time, but
> eventually empties the first bucket entirely, leaving a currentoffset of 0
> pointing at a then-deallocated key.  testDamagedIterator() was added when
> this was fixed (== when the currentoffset check was added), to ensure that
> such code raises the "changed size" exception instead.

Would it make sense to change the exception raised there in the mainline
code to include the values of currentoffset, currentbucket->len, delta,
and pseudoindex?  I can't imagine that this code gets hit very often,
and having those values in the actual exception message would make it
possible to get some insight into the bucket state without requiring
someone to run a debug version of BTrees to capture the info.

> > Since you are just iterating it, no such change could be occurring
> > (unless the reference is shared between threads somehow),
> 
> It's tempting to believe it's even worse than that:  the Python GIL is held
> for the duration of the list() call, so it "should be" that no other
> Python-created thread *can* be running in the same process until the list()
> call completes.  Alas, ZODB's C-level ThreadLock objects release the GIL
> when you try to acquire one,

Not that I have any clue about this stuff, but do you know why
ThreadLocks do this?  Do Python RLocks do this?

>  and I suppose it's possible that persistent
> loads needed to suck up buckets end up doing that in some convoluted way.
> 
> > so I suspect foul play.
> 
> Or Chris redefined list() to "lambda x: x" <wink>.

You caught me. ;-)  No, I actually looked out of paranoia.  I don't
redefine "list" anywhere.  It's possible that at some point before this
code ran some freak did "__builtins__['list'] = my_cooler_list_func",
but somehow I feel silly asking Steve to make sure of it; I guess I
should. ;-)  (FWIW, Tres has threatened to do this for hasattr given
that it silently swallows all exceptions!  We'll see if he pulls the
trigger ;-)

> > It might be iteresting to instrument the BTreeItemsTemplate.c in the
> > BTreeItems_seek() function to spew the values of i, currentoffset and
> > currentbucket->len when it blows up. Then you could see whether it dies
> > at the beginning, end or somewhere in the middle and what bucket and
> > index it is on when it does.
> 
> Yup.  Would also be good to get a debugger stack trace at this point.  I'm
> assuming the exception occurs during the list() call because nothing else
> makes sense; however, it doesn't make sense that the exception occurs during
> the list() call either, so all assumptions are suspect.

You wouldn't be able to tell me how to get a stack trace out of this
code in the circumstance that the exception is raised, would you?  Is
this something that can be put into the code itself and printed
conditionally or does it need to happen via gdb interactively?

> > ...
> > Interesting that restarting Zope cured this error. There must be some
> > inconsistency in the cached state then.
> 
> Note that the consistency check here is within a single bucket, i.e. within
> a single persistent object.

Could the 

>   Almost all potential problems with BTrees have
> to do with the *mutual* consistency of multiple bucket and parent nodes, in
> how they relate to each other.  But this check is purely local.  Even if the
> BTree is insane as a whole, a single bucket within it can't get inconsistent
> with itself.

That's pretty depressing.

It makes me want to think that the only thing that can be happening here
is memory corruption of some kind (whether due to hw failure or compiler
wrongness).  Steve has said that the machine runs fine though; it's
apparently old but trustworthy.  If it were hardware I'd suspect it
would be flaking out otherwise too.  I've asked him to try to run the
code on a different box.

> Now if the cache had a bucket of, say, length 20 when list() began, and
> *while* the list() call was iterating over the bucket its guts magically got
> replaced by a bucket of, say, length 10, then we could get this exception.
> ZODB doesn't act on invalidations until a transaction boundary, though.

Unless a ReadConflictError is raised, right?  In that case, the object
is put into the invalid objects list right away.

Is it possible that the list() implementation (or the BTreesItem_seek
code itself, or the other BTrees code that calls into it) could swallow
a conflict error (maybe it calls into hasattr! ;-)?  Might that provoke
insanity in the index state as it attempts to walk over the set of
buckets that make up the items (each one of which I presume is an
independent persistent object)?

I suggest this because this code is really the only "in the wild" code I
know of that tries to use ZODB as if it's OK to actually do a lot of
concurrent reading and writing of the same data structures.

- C