[Zope3-checkins] CVS: Zope3/src/zodb/btrees - MergeTemplate.c:1.5 interfaces.py:1.7

[Tim Peters]

Update of /cvs-repository/Zope3/src/zodb/btrees
In directory cvs.zope.org:/tmp/cvs-serv17396/src/zodb/btrees

Modified Files:
	MergeTemplate.c interfaces.py 
Log Message:
Fixing a rare BTree conflict resolution error.

+ Transaction T1 deletes some of the keys in bucket B,
  but not all of the keys.

+ Transaction T2 deletes (exactly) the keys in B that
  aren't deleted by T1.

The version of B each transaction sees is then non-empty,
but conflict resolution creates an empty bucket.  However,
conflict resolution doesn't have enough info to unlink an
empty bucket from its containing BTree correctly.

The result is that an empty bucket is left in the BTree,
which violates a BTree invariant.  The most probable
symptom is a segfault, when later & unrelated code tries
to access this bucket:  an empty bucket has NULL
pointers where the vectors of keys and values should be,
and accessing code tries to dereference the NULL pointers.

I don't know that this error has been seen in real life.
It was provoked by a randomized multithreaded simulation
program that was trying to provoke errors.  This error was
provoked frequently by that program; no other kinds of
errors have come out of it.


=== Zope3/src/zodb/btrees/MergeTemplate.c 1.4 => 1.5 ===
--- Zope3/src/zodb/btrees/MergeTemplate.c:1.4	Thu Jan 16 15:10:47 2003
+++ Zope3/src/zodb/btrees/MergeTemplate.c	Fri Jan 17 11:44:33 2003
@@ -185,7 +185,7 @@
         {                       /* Both keys changed */
           TEST_KEY_SET_OR(cmp23, i2.key, i3.key) goto err;
           if (cmp23==0)
-            {                   /* dualing inserts or deletes */
+            {                   /* dueling inserts or deletes */
               merge_error(i1.position, i2.position, i3.position, 4);
               goto err;
             }
@@ -209,7 +209,7 @@
             }
           else
             {                   /* 1<2 and 1<3:  both deleted 1.key */
-               merge_error(i1.position, i2.position, i3.position, 5);
+	      merge_error(i1.position, i2.position, i3.position, 5);
               goto err;
             }
         }
@@ -219,7 +219,7 @@
     {                           /* New inserts */
       TEST_KEY_SET_OR(cmp23, i2.key, i3.key) goto err;
       if (cmp23==0)
-        {                       /* dualing inserts */
+        {                       /* dueling inserts */
           merge_error(i1.position, i2.position, i3.position, 6);
           goto err;
         }
@@ -256,7 +256,7 @@
     }
 
   while (i1.position >= 0 && i3.position >= 0)
-    {                           /* remainer of i1 deleted in i2 */
+    {                           /* remainder of i1 deleted in i2 */
       TEST_KEY_SET_OR(cmp13, i1.key, i3.key) goto err;
       if (cmp13 > 0)
         {                       /* insert i3 */
@@ -293,11 +293,18 @@
       if (i3.next(&i3) < 0) goto err;
     }
 
+  /* If the output bucket is empty, conflict resolution doesn't have
+   * enough info to unlink it from its containing BTree correctly.
+   */
+  if (r->len == 0)
+    {
+      merge_error(-1, -1, -1, 10);
+      goto err;
+    }
+
   finiSetIteration(&i1);
   finiSetIteration(&i2);
   finiSetIteration(&i3);
-
-  /* XXX raise ConflictError here if s1 is empty. */
 
   if (s1->next)
     {


=== Zope3/src/zodb/btrees/interfaces.py 1.6 => 1.7 ===
--- Zope3/src/zodb/btrees/interfaces.py:1.6	Thu Jan 16 15:10:47 2003
+++ Zope3/src/zodb/btrees/interfaces.py	Fri Jan 17 11:44:33 2003
@@ -49,6 +49,12 @@
 
             # 9; i2 and i3 both deleted the same key
             'Conflicting deletes',
+
+            # 10; i2 and i3 deleted all the keys, and didn't insert any,
+            # leaving an empty bucket; conflict resolution doesn't have
+            # enough info to unlink an empty bucket from its containing
+            # BTree correctly
+            'Empty bucket from deleting all keys',
             ]
 
     def __init__(self, p1, p2, p3, reason):