* Fix the singlethreaded deadlocks occurring in the simple bsddb interface.

* Add support for multiple iterator/generator objects at once on the simple
  bsddb _DBWithCursor interface.

2 files changed, 154 insertions, 8 deletions

diff --git a/Lib/bsddb/__init__.py b/Lib/bsddb/__init__.py
index 51cc454..778ad29 100644
--- a/Lib/bsddb/__init__.py
+++ b/Lib/bsddb/__init__.py
@@ -70,20 +70,74 @@ import UserDict
 class _iter_mixin(UserDict.DictMixin):
     def __iter__(self):
         try:
-            yield self.first()[0]
-            next = self.next
+            cur = self.db.cursor()
+            self._iter_cursors[str(cur)] = cur
+
+            # since we're only returning keys, we call the cursor
+            # methods with flags=0, dlen=0, dofs=0
+            curkey = cur.first(0,0,0)[0]
+            yield curkey
+
+            next = cur.next
             while 1:
-                yield next()[0]
+                try:
+                    curkey = next(0,0,0)[0]
+                    yield curkey
+                except _bsddb.DBCursorClosedError:
+                    # our cursor object was closed since we last yielded
+                    # create a new one and attempt to reposition to the
+                    # right place
+                    cur = self.db.cursor()
+                    self._iter_cursors[str(cur)] = cur
+                    # FIXME-20031101-greg: race condition.  cursor could
+                    # be closed by another thread before this set call.
+                    try:
+                        cur.set(curkey,0,0,0)
+                    except _bsddb.DBCursorClosedError:
+                        # halt iteration on race condition...
+                        raise _bsddb.DBNotFoundError
+                    next = cur.next
         except _bsddb.DBNotFoundError:
+            try:
+                del self._iter_cursors[str(cur)]
+            except KeyError:
+                pass
             return
 
     def iteritems(self):
         try:
-            yield self.first()
-            next = self.next
+            cur = self.db.cursor()
+            self._iter_cursors[str(cur)] = cur
+
+            kv = cur.first()
+            curkey = kv[0]
+            yield kv
+
+            next = cur.next
             while 1:
-                yield next()
+                try:
+                    kv = next()
+                    curkey = kv[0]
+                    yield kv
+                except _bsddb.DBCursorClosedError:
+                    # our cursor object was closed since we last yielded
+                    # create a new one and attempt to reposition to the
+                    # right place
+                    cur = self.db.cursor()
+                    self._iter_cursors[str(cur)] = cur
+                    # FIXME-20031101-greg: race condition.  cursor could
+                    # be closed by another thread before this set call.
+                    try:
+                        cur.set(curkey,0,0,0)
+                    except _bsddb.DBCursorClosedError:
+                        # halt iteration on race condition...
+                        raise _bsddb.DBNotFoundError
+                    next = cur.next
         except _bsddb.DBNotFoundError:
+            try:
+                del self._iter_cursors[str(cur)]
+            except KeyError:
+                pass
             return
 """
 else:
@@ -97,15 +151,53 @@ class _DBWithCursor(_iter_mixin):
     """
     def __init__(self, db):
         self.db = db
-        self.dbc = None
         self.db.set_get_returns_none(0)
 
+        # FIXME-20031101-greg: I believe there is still the potential
+        # for deadlocks in a multithreaded environment if someone
+        # attempts to use the any of the cursor interfaces in one
+        # thread while doing a put or delete in another thread.  The
+        # reason is that _checkCursor and _closeCursors are not atomic
+        # operations.  Doing our own locking around self.dbc,
+        # self.saved_dbc_key and self._iter_cursors could prevent this.
+        # TODO: A test case demonstrating the problem needs to be written.
+
+        # self.dbc is a DBCursor object used to implement the
+        # first/next/previous/last/set_location methods.
+        self.dbc = None
+        self.saved_dbc_key = None
+
+        # a collection of all DBCursor objects currently allocated
+        # by the _iter_mixin interface.
+        self._iter_cursors = {}
+
+
     def __del__(self):
         self.close()
 
+    def _get_dbc(self):
+        return self.dbc
+
     def _checkCursor(self):
         if self.dbc is None:
             self.dbc = self.db.cursor()
+            if self.saved_dbc_key is not None:
+                self.dbc.set(self.saved_dbc_key)
+                self.saved_dbc_key = None
+
+    # This method is needed for all non-cursor DB calls to avoid
+    # BerkeleyDB deadlocks (due to being opened with DB_INIT_LOCK
+    # and DB_THREAD to be thread safe) when intermixing database
+    # operations that use the cursor internally with those that don't.
+    def _closeCursors(self, save=True):
+        if self.dbc:
+            c = self.dbc
+            self.dbc = None
+            if save:
+                self.saved_dbc_key = c.current(0,0,0)[0]
+            c.close()
+            del c
+        map(lambda c: c.close(), self._iter_cursors.values())
 
     def _checkOpen(self):
         if self.db is None:
@@ -124,13 +216,16 @@ class _DBWithCursor(_iter_mixin):
 
     def __setitem__(self, key, value):
         self._checkOpen()
+        self._closeCursors()
         self.db[key] = value
 
     def __delitem__(self, key):
         self._checkOpen()
+        self._closeCursors()
         del self.db[key]
 
     def close(self):
+        self._closeCursors(save=False)
         if self.dbc is not None:
             self.dbc.close()
         v = 0
diff --git a/Lib/test/test_bsddb.py b/Lib/test/test_bsddb.py
index 73a2d96..ff8c355 100755
--- a/Lib/test/test_bsddb.py
+++ b/Lib/test/test_bsddb.py
@@ -2,7 +2,7 @@
 """Test script for the bsddb C module by Roger E. Masse
    Adapted to unittest format and expanded scope by Raymond Hettinger
 """
-import os
+import os, sys
 import bsddb
 import dbhash # Just so we know it's imported
 import unittest
@@ -93,6 +93,57 @@ class TestBSDDB(unittest.TestCase):
         self.f.clear()
         self.assertEqual(len(self.f), 0)
 
+    def test__no_deadlock_first(self, debug=0):
+        # do this so that testers can see what function we're in in
+        # verbose mode when we deadlock.
+        sys.stdout.flush()
+
+        # in pybsddb's _DBWithCursor this causes an internal DBCursor
+        # object is created.  Other test_ methods in this class could
+        # inadvertently cause the deadlock but an explicit test is needed.
+        if debug: print "A"
+        k,v = self.f.first()
+        if debug: print "B", k
+        self.f[k] = "deadlock.  do not pass go.  do not collect $200."
+        if debug: print "C"
+        # if the bsddb implementation leaves the DBCursor open during
+        # the database write and locking+threading support is enabled
+        # the cursor's read lock will deadlock the write lock request..
+
+        # test the iterator interface (if present)
+        if hasattr(self, 'iteritems'):
+            if debug: print "D"
+            k,v = self.f.iteritems()
+            if debug: print "E"
+            self.f[k] = "please don't deadlock"
+            if debug: print "F"
+            while 1:
+                try:
+                    k,v = self.f.iteritems()
+                except StopIteration:
+                    break
+            if debug: print "F2"
+
+            i = iter(self.f)
+            if debug: print "G"
+            while i:
+                try:
+                    if debug: print "H"
+                    k = i.next()
+                    if debug: print "I"
+                    self.f[k] = "deadlocks-r-us"
+                    if debug: print "J"
+                except StopIteration:
+                    i = None
+            if debug: print "K"
+
+        # test the legacy cursor interface mixed with writes
+        self.assert_(self.f.first()[0] in self.d)
+        k = self.f.next()[0]
+        self.assert_(k in self.d)
+        self.f[k] = "be gone with ye deadlocks"
+        self.assert_(self.f[k], "be gone with ye deadlocks")
+
     def test_popitem(self):
         k, v = self.f.popitem()
         self.assert_(k in self.d)