[ZODB-Dev] BTrees q [Fwd: [Zope-dev] More Transience weirdness in2.7.1b1]

[Tim Peters]

[Dieter Maurer]
> I see only a single possibility: loading "currentbucket->next" brings a
> bad state into memory, one with "currentbucket->next->len <= 0".

I'm afraid that wouldn't do it either.  For reasons to become clearer, this
code was designed to work correctly even if len == 0.  I think it works OK
for len < 0 too, but more by likely accident than by design (len < 0 should
be impossible; len == 0 can actually happen, although that may not be
obvious at first).

> Reason: "list" will access the "keys" iterator with successive indexes.
> Therefore, "delta" will be "1" for each access. As long as "currentoffset
> < currentbucket->len - 1", the exception cannot be raised (unless
> "currentoffset" had been negative to start with). Otherwise,
> "currentoffset" is set to "0" and we move on to the next bucket.

That's the rub.  When currentoffset gets set to 0, we go back to the top of
the loop.  Say the next bucket does have len 0.  Then max gets set to 0-0-1
== -1.  delta <= max can't be true then, so we simply move on to yet the
next bucket, and neither pseudoindex nor delta change (we add max+1 to them,
which is 0).  So long as we keep hitting empty buckets, we stay in the loop.
Eventually we hit the last bucket in the range, or a NULL, and then jump to
no_match.  The check in question doesn't get executed in any of these cases.

If len < 0, then max becomes a negative number, and nearly the same analysis
applies:  we again stay in the loop, skipping over all buckets where len <=
0.  A slight difference is that pseudoindex and delta do change on each loop
trip then, but getting ever-more positive (due to subtracting a negative
max+1 from them).

However, what you describe could happen if the very first bucket has len <=
0, the first time it's seen.  delta is 0 then on the first call to
BTreeItems_seek() (because Chris's range searches start with None,
currentoffset and pseudoindex are initialized to 0), so both search loops
are skipped, and we get to the "size changed" check.

That's a variant of what happened in Steve Alexander's formerly segfaulting
case.  There he emptied a bucket, and while that bucket is removed from the
BTree because of getting emptied, the BTreeItems object still pointed to it!
There's no guarantee that the first and last buckets found when the
BTreeItems object was created will remain in the tree during iteration, so
this code had to be made robust against them disappearing, or becoming
empty, during iteration.  For that reason the len==0 case was excruciatingly
analyzed a long time ago.

Note that if the BTree is empty to begin with, the BTreeItems object
constructed has currentbucket initialized to NULL, and so BTreeItems_seek()
goes immediately to no_match without executing any of this code.

> When the exception is raised, then we have "0 >= currentbucket->len".
>
> Maybe, something destroyed the bucket content?

It's a pretty safe bet something destroyed something <wink>.