Issue1854

classification
Title: set().pop() race condition
Type: behaviour Severity: critical
Components: Core Versions: 2.5.2
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: fwierzbicki Nosy List: ajdavis, fwierzbicki
Priority: high Keywords:

Created on 2012-03-16.20:14:25 by ajdavis, last changed 2012-06-07.18:20:27 by fwierzbicki.

Messages
msg6805 (view) Author: A. Jesse Jiryu Davis (ajdavis) Date: 2012-03-16.20:16:52
Docs say:

Jython implements dict and set by using Java’s ConcurrentHashMap. This means you can just use these standard Python types, and still get high performance concurrency. (They are also atomic like in CPython, as we will describe.)

However, I'm looking at the source code in 2.5.2 in PySet.java and BaseSet.java, and it doesn't use ConcurrentHashMap. Perhaps it ought to. In fact there's a race condition in pop(), where many threads can all pop the same object from the set. Set uses an iterator to get the first object, then removes the object. In between those two operations is a critical section not protected by a lock.

While testing PyMongo 2.2 (which I'm developing -- it'll be released shortly) I saw this race condition causing bugs in tests with about 40 threads all popping from the set concurrently. Many of them got the same object.
msg7043 (view) Author: Frank Wierzbicki (fwierzbicki) Date: 2012-04-10.17:46:20
Sorry for the slow response - is there any chance that you have a simple test that will show the race condition? That would help us a bunch in assessing the trouble.
msg7044 (view) Author: A. Jesse Jiryu Davis (ajdavis) Date: 2012-04-10.23:56:55
$ cat jython-set-screw.py 
import threading
nthreads = 200
s = set(range(200))
threads = [threading.Thread(target=s.pop) for i in range(nthreads)]
for t in threads: t.start()
assert not len(s), "%d items left over" % len(s)

$ python --version
Python 2.7.1
$ python jython-set-screw.py
$ ./jython2.5.2/bin/jython --version
Jython 2.5.2
$ ./jython2.5.2/bin/jython jython-set-screw.py
Traceback (most recent call last):
  File "jython-set-screw.py", line 6, in <module>
    assert not len(s), "%d items left over" % len(s)
AssertionError: 2 items left over
msg7120 (view) Author: A. Jesse Jiryu Davis (ajdavis) Date: 2012-05-21.15:58:55
I see that in 2.7a1 you've added a 'synchronized' to Pyset.set_pop(),
I think that fixes the bug. I notice that, predictably, I had a bug in
my test script: I didn't join all the threads before asserting the set
was empty. So with this test script, 2.5.2 often fails and 2.7a1
always passes:

import threading
nthreads = 200
s = set(range(nthreads))
threads = [threading.Thread(target=s.pop) for i in range(nthreads)]
for t in threads: t.start()
for t in threads: t.join()
assert not len(s), "%d items left over" % len(s)

On Tue, Apr 10, 2012 at 7:56 PM, A. Jesse Jiryu Davis
<report@bugs.jython.org> wrote:
>
> A. Jesse Jiryu Davis <jesse@10gen.com> added the comment:
>
> $ cat jython-set-screw.py
> import threading
> nthreads = 200
> s = set(range(200))
> threads = [threading.Thread(target=s.pop) for i in range(nthreads)]
> for t in threads: t.start()
> assert not len(s), "%d items left over" % len(s)
>
> $ python --version
> Python 2.7.1
> $ python jython-set-screw.py
> $ ./jython2.5.2/bin/jython --version
> Jython 2.5.2
> $ ./jython2.5.2/bin/jython jython-set-screw.py
> Traceback (most recent call last):
>  File "jython-set-screw.py", line 6, in <module>
>    assert not len(s), "%d items left over" % len(s)
> AssertionError: 2 items left over
>
> _______________________________________
> Jython tracker <report@bugs.jython.org>
> <http://bugs.jython.org/issue1854>
> _______________________________________
msg7121 (view) Author: Frank Wierzbicki (fwierzbicki) Date: 2012-05-21.17:05:45
This is fixed in the latest 2.5 in our repo - I'll be putting out a 2.5.3b2 this week which will contain the fix.
msg7122 (view) Author: Frank Wierzbicki (fwierzbicki) Date: 2012-05-21.17:06:29
I'll close this when 2.5.3b2 comes out.
History
Date User Action Args
2012-06-07 18:20:27fwierzbickisetstatus: open -> closed
2012-05-21 17:06:38fwierzbickisetresolution: accepted -> fixed
2012-05-21 17:06:29fwierzbickisetpriority: high
assignee: fwierzbicki
resolution: accepted
messages: + msg7122
2012-05-21 17:05:45fwierzbickisetmessages: + msg7121
2012-05-21 15:58:56ajdavissetmessages: + msg7120
2012-04-10 23:56:55ajdavissetmessages: + msg7044
2012-04-10 17:46:21fwierzbickisetmessages: + msg7043
2012-03-16 21:11:33fwierzbickisetnosy: + fwierzbicki
2012-03-16 20:16:53ajdavissetmessages: + msg6805
2012-03-16 20:14:25ajdaviscreate