Re: test_bsddb blocks testing popitem - reason
It is unfortuantely entirely possible that various berkeleydb libraries have bugs. Since the BerkeleyDB db->del() call isn't returning it is presumably stuck in a lock waiting for who knows what.
Right. But the SAME berkeley db library is being used for my build of both Python 2.4 alpha 0, and 2.3 maintenance branch, both from cvs, and I can't see any difference in what they're doing with bsddb -- so clearly I must be missing something because it's hanging on EVERY attempt to run the unittest w/2.4, but never w/2.3.
The big difference i see between 2.3cvs and 2.4cvs that could "explain" it is that Lib/bsddb/__init__.py has been updated to use a private (in memory, single process only) DBEnv with locking and thread support enabled. That explains why db->del() would be doing locking. But not why it would deadlock. This is also easily reproducable here. No special platform or berkeleydb version should be required. Looking closer I suspect what is happening is that Lib/bsddb/__init__.py implementation is not threadsafe. It wants to maintain the current iterator location using a DBCursor object. However, having an active DBCursor holds a lock in the database. DictMixin's popitem() is effectively: k, v = self.iteritems().next() del self[k] return (k, v) The iteritems() call creates an internal DBCursor object for the iterator. The next() call on the iterator (DBCursor) looks up the value for k. The following delete attempts to delete the record without using the DBCursor; thus the deadlock. If we implement our own popitem() for the bsddb dictionary object (_DBWithCursor) to perform the delete using the cursor this deadlock in the unit tests would go away. That won't stop users from intermixing iteration over a database with modifications to the database; causing their own deadlocks (very unexpected in single threaded code). Proposed fix: It should be possible for the bsddb object to maintain internal state of its own about what key is is on and close any internal DB cursor on all non-cursor database accesses leaving the iteration functions to detect this and reopen and reposition the cursor. Since the basic bsddb interface doesn't allow databases with duplicate keys it shouldn't be too difficult. Its not efficient but a user who cares about efficient use of berkeleydb should use the real DB/DBEnv interface directly. How do python dictionaries deal with modifications to the dictionary intermixed with iteration? Greg
On Monday 27 October 2003 10:40 am, Gregory P. Smith wrote: ...
The big difference i see between 2.3cvs and 2.4cvs that could "explain" it is that Lib/bsddb/__init__.py has been updated to use a private (in memory, single process only) DBEnv with locking and thread support enabled. That explains why db->del() would be doing locking. But not why it would deadlock.
*AH*! I wasn't looking in the right place, silly me. Good job!!! Yes, now that you've pointed it out, the change from 2.3's d = db.DB() to 2.4's e = _openDBEnv() d = db.DB(e) must be the culprit. I still don't quite see how the lock ends up being "held", but, don't mind me -- the intricacy of mixins and wrappings and generators and delegations in those modules is making my head spin anyway, so it's definitely not surprising that I can't quite see what's going on.
How do python dictionaries deal with modifications to the dictionary intermixed with iteration?
In general, Python doesn't deal well with modifications to any iterable in the course of a loop using an iterator on that iterable. The one kind of "modification during the loop" that does work is: for k in somedict: somedict[k] = ...whatever... i.e. one can change the values corresponding to keys, but not change the set of keys in any way -- any changes to the set of keys can cause unending loops or other such misbehavior (not deadlocks nor crashes, though...). However, on a real Python dict, k, v = thedict.iteritems().next() doesn't constitute "a loop" -- the iterator object returned by the iteritems call is dropped since there are no outstanding references to it right after this statement. So, following up with del thedict[k] is quite all right -- the dictionary isn't being "looped on" at that time. Given that in bsddb's case that iteritems() first [and only] next() boils down to a self.first() which in turn does a self.dbc.first() I _still_ don't see exactly what's holding the lock. But the simplest fix would appear to be in __delitem__, i.e., if we have a cursor we should delete through it: def __delitem__(self, key): self._checkOpen() if self.dbc is not None: self.dbc.set(key) self.dbc.delete() else: del self.db[key] ...but this doesn't in fact remove the deadlock on the unit-test for popitem, which just confirms I don't really grasp what's going on, yet!-) Alex
On Mon, Oct 27, 2003 at 11:25:16AM +0100, Alex Martelli wrote:
I still don't quite see how the lock ends up being "held", but, don't mind me -- the intricacy of mixins and wrappings and generators and delegations in those modules is making my head spin anyway, so it's definitely not surprising that I can't quite see what's going on.
BerkeleyDB internally always grabs a read lock (i believe at the page level; i don't think BerkeleyDB does record locking) for any database read when opened with DB_THREAD | DB_INIT_LOCK flags. I believe the problem is that a DBCursor object holds this lock as long as it is open/exists. Other reads can go on happily, but writes must to wait for the read lock to be released before they can proceed.
How do python dictionaries deal with modifications to the dictionary intermixed with iteration?
In general, Python doesn't deal well with modifications to any iterable in the course of a loop using an iterator on that iterable.
The one kind of "modification during the loop" that does work is:
for k in somedict: somedict[k] = ...whatever...
i.e. one can change the values corresponding to keys, but not change the set of keys in any way -- any changes to the set of keys can cause unending loops or other such misbehavior (not deadlocks nor crashes, though...).
However, on a real Python dict, k, v = thedict.iteritems().next() doesn't constitute "a loop" -- the iterator object returned by the iteritems call is dropped since there are no outstanding references to it right after this statement. So, following up with del thedict[k] is quite all right -- the dictionary isn't being "looped on" at that time.
What about the behaviour of multiple iterators for the same dict being used at once (either interleaved or by multiple threads; it shouldn't matter)? I expect that works fine in python. This is something the _DBWithCursor iteration interface does not currently support due to its use of a single DBCursor internally. _DBWithCursor is currently written such that the cursor is never closed once created. This leaves tons of potential for deadlock even in single threaded apps. Reworking _DBWithCursor into a _DBThatUsesCursorsSafely such that each iterator creates its own cursor in an internal pool and other non cursor methods that would write to the db destroy all cursors after saving their current() position so that the iterators can reopen+reposition them is a solution.
Given that in bsddb's case that iteritems() first [and only] next() boils down to a self.first() which in turn does a self.dbc.first() I _still_ don't see exactly what's holding the lock. But the simplest fix would appear to be in __delitem__, i.e., if we have a cursor we should delete through it:
def __delitem__(self, key): self._checkOpen() if self.dbc is not None: self.dbc.set(key) self.dbc.delete() else: del self.db[key]
...but this doesn't in fact remove the deadlock on the unit-test for popitem, which just confirms I don't really grasp what's going on, yet!-)
hmm. i would've expected your __delitem__ to work. Regardless, using the debugger I can stop the deadlock from occurring if i do "self.dbc.close(); self.dbc = None" just before popitem's "del self[k]" Greg
On Monday 27 October 2003 10:56 pm, Gregory P. Smith wrote:
On Mon, Oct 27, 2003 at 11:25:16AM +0100, Alex Martelli wrote:
I still don't quite see how the lock ends up being "held", but, don't mind me -- the intricacy of mixins and wrappings and generators and delegations in those modules is making my head spin anyway, so it's definitely not surprising that I can't quite see what's going on.
BerkeleyDB internally always grabs a read lock (i believe at the page level; i don't think BerkeleyDB does record locking) for any database read when opened with DB_THREAD | DB_INIT_LOCK flags. I believe the problem is that a DBCursor object holds this lock as long as it is open/exists. Other reads can go on happily, but writes must to wait for the read lock to be released before they can proceed.
Aha, much clearer, thanks.
What about the behaviour of multiple iterators for the same dict being used at once (either interleaved or by multiple threads; it shouldn't matter)? I expect that works fine in python.
If the dict is not being modified, or if the only modifications on it are assigning different values for already-existing keys, multiple iterators on the same unchanging dict do work fine in one or more threads. But note that iterators only "read" the dict, don't change it. If any change to the set of keys in the dict happens, all bets are off.
This is something the _DBWithCursor iteration interface does not currently support due to its use of a single DBCursor internally.
_DBWithCursor is currently written such that the cursor is never closed once created. This leaves tons of potential for deadlock even in single threaded apps. Reworking _DBWithCursor into a _DBThatUsesCursorsSafely such that each iterator creates its own cursor in an internal pool and other non cursor methods that would write to the db destroy all cursors after saving their current() position so that the iterators can reopen+reposition them is a solution.
Woof. I think I understand what you're saying. However, writing to a dict (in the sense of changing the sets of keys) while one is iterating on the dict is NOT supported in Python -- basically "undefined behavior" (which does NOT include possibilities of crashes and deadlocks, though). So, maybe, we could get away with something a bit less rich here?
Given that in bsddb's case that iteritems() first [and only] next() boils down to a self.first() which in turn does a self.dbc.first() I _still_ don't see exactly what's holding the lock. But the simplest fix would appear to be in __delitem__, i.e., if we have a cursor we should delete through it:
def __delitem__(self, key): self._checkOpen() if self.dbc is not None: self.dbc.set(key) self.dbc.delete() else: del self.db[key]
...but this doesn't in fact remove the deadlock on the unit-test for popitem, which just confirms I don't really grasp what's going on, yet!-)
hmm. i would've expected your __delitem__ to work. Regardless, using the
Ah! I'll check again -- maybe I did something silly -- but what happens now is that the __delitem__ DOES work, the key does get deleted according to print and printf's I've sprinkled here and there, BUT then right after the key is deleted everything deadlocks anyway (in test_popitem).
debugger I can stop the deadlock from occurring if i do "self.dbc.close(); self.dbc = None" just before popitem's "del self[k]"
So, maybe I _should_ just fix popitem that way and see if all tests pass? I dunno -- it feels a bit like fixing the symptoms and leaving some deep underlying problems intact... Any other opinions? I don't have any strong feelings one way or the other, except that I really think unit-tests SHOULD pass... and indeed that changes should not committed UNLESS unit-tests pass... Alex
On Tue, Oct 28, 2003 at 11:12:21AM +0100, Alex Martelli wrote:
On Monday 27 October 2003 10:56 pm, Gregory P. Smith wrote:
What about the behaviour of multiple iterators for the same dict being used at once (either interleaved or by multiple threads; it shouldn't matter)? I expect that works fine in python.
If the dict is not being modified, or if the only modifications on it are assigning different values for already-existing keys, multiple iterators on the same unchanging dict do work fine in one or more threads. But note that iterators only "read" the dict, don't change it. If any change to the set of keys in the dict happens, all bets are off. ...
This is something the _DBWithCursor iteration interface does not currently support due to its use of a single DBCursor internally.
_DBWithCursor is currently written such that the cursor is never closed once created. This leaves tons of potential for deadlock even in single threaded apps. Reworking _DBWithCursor into a _DBThatUsesCursorsSafely such that each iterator creates its own cursor in an internal pool and other non cursor methods that would write to the db destroy all cursors after saving their current() position so that the iterators can reopen+reposition them is a solution.
Woof. I think I understand what you're saying. However, writing to a dict (in the sense of changing the sets of keys) while one is iterating on the dict is NOT supported in Python -- basically "undefined behavior" (which does NOT include possibilities of crashes and deadlocks, though). So, maybe, we could get away with something a bit less rich here?
I just implemented and committed something about that rich. I believe I could simplify it: have __iter__() and iteritems() return if their cursor was closed out from underneath them instead of the current attempt to reopen a cursor, reposition themselves, and keep going [which could still have unpredictable results since a db modification could rearrange the keys in some types of databases].
So, maybe I _should_ just fix popitem that way and see if all tests pass? I dunno -- it feels a bit like fixing the symptoms and leaving some deep underlying problems intact...
My commit fixed the deadlock problem for the single threaded case and wrote a test case to prove it. I opened a SF bug to track fixing the deadlock possibilities in the multithreaded case (and a memory leak i believe i added). -g
On Sunday 02 November 2003 11:00 am, Gregory P. Smith wrote: ...
So, maybe, we could get away with something a bit less rich here?
I just implemented and committed something about that rich.
Super! I've just updated, built, and re-run all tests (on 2.4), and they all go smoothly.
My commit fixed the deadlock problem for the single threaded case and wrote a test case to prove it. I opened a SF bug to track fixing the deadlock possibilities in the multithreaded case (and a memory leak i believe i added).
OK, I understand this fix isn't the be-all end-all, but still, it makes things much better than they were before. *THANKS*! Alex
participants (3)
-
Alex Martelli -
Barry Warsaw -
Gregory P. Smith