[Zodb-checkins] SVN: ZODB/branches/3.9/src/ Bugs Fixed:
Jim Fulton
jim at zope.com
Thu Oct 22 10:30:54 EDT 2009
Log message for revision 105216:
Bugs Fixed:
2 BTree bugs, introduced by a bug fix in 3.9.0c2, sometimes caused
deletion of keys to be improperly handled, resulting in data being
available via iteraation but not item access.
Changed:
U ZODB/branches/3.9/src/BTrees/BTreeTemplate.c
U ZODB/branches/3.9/src/BTrees/MergeTemplate.c
U ZODB/branches/3.9/src/BTrees/tests/testBTrees.py
U ZODB/branches/3.9/src/BTrees/tests/testConflict.py
U ZODB/branches/3.9/src/CHANGES.txt
U ZODB/branches/3.9/src/ZODB/POSException.py
-=-
Modified: ZODB/branches/3.9/src/BTrees/BTreeTemplate.c
===================================================================
--- ZODB/branches/3.9/src/BTrees/BTreeTemplate.c 2009-10-22 14:13:18 UTC (rev 105215)
+++ ZODB/branches/3.9/src/BTrees/BTreeTemplate.c 2009-10-22 14:30:54 UTC (rev 105216)
@@ -720,6 +720,7 @@
COPY_KEY(d->key, bucket->keys[0]);
INCREF_KEY(d->key);
PER_UNUSE(bucket);
+ if (PER_CHANGED(self) < 0) goto Error;
}
}
Modified: ZODB/branches/3.9/src/BTrees/MergeTemplate.c
===================================================================
--- ZODB/branches/3.9/src/BTrees/MergeTemplate.c 2009-10-22 14:13:18 UTC (rev 105215)
+++ ZODB/branches/3.9/src/BTrees/MergeTemplate.c 2009-10-22 14:30:54 UTC (rev 105216)
@@ -160,6 +160,15 @@
}
else if (set || (TEST_VALUE(i1.value, i2.value) == 0))
{ /* deleted in i3 */
+ if (i3.position == 1)
+ {
+ /* Deleted the first item. This will modify the
+ parent node, so we don't know if merging will be
+ safe
+ */
+ merge_error(i1.position, i2.position, i3.position, 13);
+ goto err;
+ }
if (i1.next(&i1) < 0) goto err;
if (i2.next(&i2) < 0) goto err;
}
@@ -178,6 +187,15 @@
}
else if (set || (TEST_VALUE(i1.value, i3.value) == 0))
{ /* deleted in i2 */
+ if (i2.position == 1)
+ {
+ /* Deleted the first item. This will modify the
+ parent node, so we don't know if merging will be
+ safe
+ */
+ merge_error(i1.position, i2.position, i3.position, 13);
+ goto err;
+ }
if (i1.next(&i1) < 0) goto err;
if (i3.next(&i3) < 0) goto err;
}
Modified: ZODB/branches/3.9/src/BTrees/tests/testBTrees.py
===================================================================
--- ZODB/branches/3.9/src/BTrees/tests/testBTrees.py 2009-10-22 14:13:18 UTC (rev 105215)
+++ ZODB/branches/3.9/src/BTrees/tests/testBTrees.py 2009-10-22 14:30:54 UTC (rev 105216)
@@ -1975,7 +1975,11 @@
with bucket children.
"""
- tree = self.t_class()
+ from ZODB.MappingStorage import DB
+ db = DB()
+ conn = db.open()
+
+ tree = conn.root.tree = self.t_class()
i = 0
# Grow the btree until we have multiple buckets
@@ -1986,12 +1990,17 @@
if len(data) >= 3:
break
+ transaction.commit()
+
# Now, delete the internal key and make sure it's really gone
key = data[1]
del tree[key]
data = tree.__getstate__()[0]
self.assert_(data[1] != key)
+ # The tree should have changed:
+ self.assert_(tree._p_changed)
+
# Grow the btree until we have multiple levels
while 1:
i += 1
@@ -2007,6 +2016,9 @@
data = tree.__getstate__()[0]
self.assert_(data[1] != key)
+ transaction.abort()
+ db.close()
+
class InternalKeysSetTest:
"""There must not be any internal keys not in the TreeSet
"""
Modified: ZODB/branches/3.9/src/BTrees/tests/testConflict.py
===================================================================
--- ZODB/branches/3.9/src/BTrees/tests/testConflict.py 2009-10-22 14:13:18 UTC (rev 105215)
+++ ZODB/branches/3.9/src/BTrees/tests/testConflict.py 2009-10-22 14:30:54 UTC (rev 105216)
@@ -49,6 +49,7 @@
n = 'fs_tmp__%s' % os.getpid()
self.storage = FileStorage(n)
self.db = DB(self.storage)
+ return self.db
class MappingBase(Base):
""" Tests common to mappings (buckets, btrees) """
@@ -102,11 +103,11 @@
def testMergeDelete(self):
base, b1, b2, bm, e1, e2, items = self._setupConflict()
- del b1[items[0][0]]
+ del b1[items[1][0]]
del b2[items[5][0]]
del b1[items[-1][0]]
del b2[items[-2][0]]
- del bm[items[0][0]]
+ del bm[items[1][0]]
del bm[items[5][0]]
del bm[items[-1][0]]
del bm[items[-2][0]]
@@ -114,11 +115,11 @@
def testMergeDeleteAndUpdate(self):
base, b1, b2, bm, e1, e2, items = self._setupConflict()
- del b1[items[0][0]]
+ del b1[items[1][0]]
b2[items[5][0]]=1
del b1[items[-1][0]]
b2[items[-2][0]]=2
- del bm[items[0][0]]
+ del bm[items[1][0]]
bm[items[5][0]]=1
del bm[items[-1][0]]
bm[items[-2][0]]=2
@@ -237,11 +238,11 @@
def testMergeDelete(self):
base, b1, b2, bm, e1, e2, items = self._setupConflict()
- b1.remove(items[0])
+ b1.remove(items[1])
b2.remove(items[5])
b1.remove(items[-1])
b2.remove(items[-2])
- bm.remove(items[0])
+ bm.remove(items[1])
bm.remove(items[5])
bm.remove(items[-1])
bm.remove(items[-2])
@@ -331,9 +332,9 @@
assert merged == expected, message
class NastyConfict(Base, TestCase):
- def setUp(self):
- self.t = OOBTree()
+ t_type = OOBTree
+
# This tests a problem that cropped up while trying to write
# testBucketSplitConflict (below): conflict resolution wasn't
# working at all in non-trivial cases. Symptoms varied from
@@ -765,7 +766,69 @@
else:
self.fail("expected ConflictError")
+ def testConflictOfInsertAndDeleteOfFirstBucketItem(self):
+ """
+ Recently, BTrees became careful about removing internal keys
+ (keys in internal aka BTree nodes) when they were deleted from
+ buckets. This poses a problem for conflict resolution.
+ We want to guard against a case in which the first key in a
+ bucket is removed in one transaction while a key is added
+ after that key but before the next key in another transaction
+ with the result that the added key is unreachble
+
+ original:
+
+ Bucket(...), k1, Bucket((k1, v1), (k3, v3), ...)
+
+ tran1
+
+ Bucket(...), k3, Bucket(k3, v3), ...)
+
+ tran2
+
+ Bucket(...), k1, Bucket((k1, v1), (k2, v2), (k3, v3), ...)
+
+ where k1 < k2 < k3
+
+ We don't want:
+
+ Bucket(...), k3, Bucket((k2, v2), (k3, v3), ...)
+
+ as k2 would be unfindable, so we want a conflict.
+
+ """
+ mytype = self.t_type
+ db = self.openDB()
+ tm1 = transaction.TransactionManager()
+ conn1 = db.open(tm1)
+ conn1.root.t = t = mytype()
+ for i in range(0, 200, 2):
+ t[i] = i
+ tm1.commit()
+ k = t.__getstate__()[0][1]
+ assert t.__getstate__()[0][2].keys()[0] == k
+
+ tm2 = transaction.TransactionManager()
+ conn2 = db.open(tm2)
+
+ t[k+1] = k+1
+ del conn2.root.t[k]
+ for i in range(200,300):
+ conn2.root.t[i] = i
+
+ tm1.commit()
+ self.assertRaises(ConflictError, tm2.commit)
+ tm2.abort()
+
+ k = t.__getstate__()[0][1]
+ t[k+1] = k+1
+ del conn2.root.t[k]
+
+ tm2.commit()
+ self.assertRaises(ConflictError, tm1.commit)
+ tm1.abort()
+
def test_suite():
suite = TestSuite()
Modified: ZODB/branches/3.9/src/CHANGES.txt
===================================================================
--- ZODB/branches/3.9/src/CHANGES.txt 2009-10-22 14:13:18 UTC (rev 105215)
+++ ZODB/branches/3.9/src/CHANGES.txt 2009-10-22 14:30:54 UTC (rev 105216)
@@ -2,6 +2,16 @@
Change History
================
+3.9.3 (2009-10-??)
+==================
+
+Bugs Fixed
+----------
+
+- 2 BTree bugs, introduced by a bug fix in 3.9.0c2, sometimes caused
+ deletion of keys to be improperly handled, resulting in data being
+ available via iteraation but not item access.
+
3.9.2 (2009-10-13)
==================
Modified: ZODB/branches/3.9/src/ZODB/POSException.py
===================================================================
--- ZODB/branches/3.9/src/ZODB/POSException.py 2009-10-22 14:13:18 UTC (rev 105215)
+++ ZODB/branches/3.9/src/ZODB/POSException.py 2009-10-22 14:30:54 UTC (rev 105216)
@@ -214,6 +214,9 @@
# 12; i2 or i3 was empty
'Empty bucket in a transaction',
+
+ # 13; delete of first key, which causes change to parent node
+ 'Delete of first key',
]
def __init__(self, p1, p2, p3, reason):
More information about the Zodb-checkins
mailing list