[ZODB-Dev] BTree data loss bug under Python 3.x

[Marius Gedminas]

On Fri, May 24, 2013 at 09:31:55PM -0400, Tres Seaver wrote:
> On 05/24/2013 01:28 PM, Marius Gedminas wrote:
> > I was trying to debug a failing ZEO test case
> > (testConcurrentUpdates), and found out it had nothing to do with
> > ZEO.  There's a bug either in BTrees or in ZODB itself that causes
> > data corruption under Python 3.x.
> > 
> > Here's a test case: 
> > https://gist.github.com/mgedmin/5644876#file-zodbfail_simple-py
> 
> Thanks for the detective work!  I can confirm the bug, and that it is in
> the BTrees C extensions (the tests pass after 'rm
> .tox/py32/lib/python3.2/site-packages/BTrees/*.so').

It's the COMPARE macro in _compat.h.  This patch fixes the data corruption:

diff --git a/BTrees/_compat.h b/BTrees/_compat.h
index e004d54..4765df1 100644
--- a/BTrees/_compat.h
+++ b/BTrees/_compat.h
@@ -28,8 +28,8 @@
 #define TEXT_FORMAT PyUnicode_Format
 
 #define COMPARE(lhs, rhs) \
-    PyObject_RichCompareBool((lhs), (rhs), Py_LT) > 0 ? -1 : \
-    (PyObject_RichCompareBool((lhs), (rhs), Py_EQ) > 0 ? 0 : 1)
+    (PyObject_RichCompareBool((lhs), (rhs), Py_LT) > 0 ? -1 : \
+     (PyObject_RichCompareBool((lhs), (rhs), Py_EQ) > 0 ? 0 : 1))
 
 
 #else


I'm now trying to write a failing unit test.  It's a bit difficult to
get access to C macros from Python tests ;-)

COMPARE is used in two places:

    BTrees/objectkeymacros.h-#define TEST_KEY_SET_OR(V, KEY, TARGET) \
    BTrees/objectkeymacros.h:if ( ( (V) = COMPARE((KEY),(TARGET)) ), PyErr_Occurred() )

and

    BTrees/objectvaluemacros.h:#define TEST_VALUE(VALUE, TARGET) COMPARE((VALUE),(TARGET))

We can ignore TEST_KEY_SET_OR, as it works fine there.

TEST_VALUE is used to implement BTree.byValue and bucket merging.  The
bug I was chasing down was caused by bucket mismerges, I think.

It should be easier to write a test for byValue.  In fact there is one,
in test__base.py, but it's not run against real C-implemented BTrees.  I
copied it over into test_OOBTree.py and discovered that it fails
unexpectedly:

diff --git a/BTrees/tests/test_OOBTree.py b/BTrees/tests/test_OOBTree.py
index bc046bc..e813f88 100644
--- a/BTrees/tests/test_OOBTree.py
+++ b/BTrees/tests/test_OOBTree.py
@@ -99,9 +99,15 @@ class OOSetPyTest(ExtendedSetTests, unittest.TestCase):
 
 class OOBTreeTest(BTreeTests, unittest.TestCase):
 
-    def _makeOne(self):
+    def _makeOne(self, *args):
         from BTrees.OOBTree import OOBTree
-        return OOBTree()
+        return OOBTree(*args)
+
+    def test_byValue(self):
+        ITEMS = [(y, x) for x, y in enumerate('abcdefghijklmnopqrstuvwxyz')]
+        tree = self._makeOne(ITEMS)
+        self.assertEqual(list(tree.byValue(22)),
+                         [(y, x) for x, y in ITEMS[22:]])
 
     def testRejectDefaultComparison(self):
         # Check that passing int keys w default comparison fails.
@@ -146,9 +152,9 @@ class OOBTreePyTest(OOBTreeTest):
 # default 'object' comparison semantics.
 #class OOBTreePyTest(BTreeTests, unittest.TestCase):
 
-    def _makeOne(self):
+    def _makeOne(self, *args):
         from BTrees.OOBTree import OOBTreePy
-        return OOBTreePy()
+        return OOBTreePy(*args)
 
 
 

The failure is

AssertionError: Lists differ: [(25, 'z'), (24, 'y'), (23, 'x... != [(22, 'w'), (23, 'x'), (24, 'y...

First differing element 0:
(25, 'z')
(22, 'w')

- [(25, 'z'), (24, 'y'), (23, 'x'), (22, 'w')]
+ [(22, 'w'), (23, 'x'), (24, 'y'), (25, 'z')]

so the C-implemented BTrees return values in descending order, while the base
Python implementation returns them in ascending order.  This happens on Python
2.7 as well, so it's not related to the COMPARE macro bug.

Does anybody know what the API of BTree.byValue() is supposed to be?
The interface just says "Return a sequence of (value, key) pairs, sorted
by value", without clarifying if it means an ascending or a descending
sort.

Marius Gedminas
-- 
If vegetarians eat vegetables, what do humanitarians eat?
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 190 bytes
Desc: Digital signature
URL: <http://mail.zope.org/pipermail/zodb-dev/attachments/20130525/2a05c7ed/attachment.sig>