classification
Title: BoundedSemaphore.release() subject to races
Type: behavior Stage: resolved
Components: Library (Lib) Versions: Python 3.5
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: haypo, pitrou, python-dev, sbt, tim.peters
Priority: normal Keywords: patch

Created on 2013-10-04 00:00 by tim.peters, last changed 2013-10-09 18:30 by python-dev. This issue is now closed.

Files
File name Uploaded Description Edit
sema tim.peters, 2013-10-04 00:00 review
boundsem.patch tim.peters, 2013-10-07 00:36 review
boundsem2.patch tim.peters, 2013-10-07 03:04 review
Messages (14)
msg198928 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2013-10-04 00:00
I'm sure this flaw exists on more than just the current default branch, but didn't check.

BoundedSemaphore.release() doesn't quite do what it thinks it's doing.  By eyeball, the code obviously suffers from a small timing hole:  multiple threads releasing at the same time can all see "self._value >= self._initial_value" as false before any of them actually releases the semaphore.  So the value of ._value can become arbitrarily higher than ._initial_value.

This is hard to provoke.  The attached patch adds a TESTWAIT Event to BoundedSemaphore so that the new file (unbounded.py) can demonstrate the race reliably.  The patch doesn't fix anything - it's just a way to demonstrate the problem.  At the end, unbounded.py prints

bs._value is 2

That should be "impossible" for a BoundedSemaphore(1).
msg198948 - (view) Author: Richard Oudkerk (sbt) * (Python committer) Date: 2013-10-04 13:36
Is BoundedSemaphore really supposed to be "robust" in the face of too many releases, or does it just provide a sanity check?

I think that releasing a bounded semaphore too many times is a programmer error, and the exception is just a debugging aid for the programmer.  Raising an exception 99% of the time should be sufficient for that purpose.
msg198959 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2013-10-04 17:29
Richard, that's a strange argument ;-)  Since, e.g., a BoundedSemaphore(1) is semantically equivalent to a mutex, it's like saying some_mutex.release() usually raises an exception if the mutex isn't held at the time - but maybe it won't.  If the docs _say_ it's not reliable, fair enough.  But they don't say that.  When a thread gimmick is _intended_ to be probabilistic, the docs say so (e.g., Queue.qsize()).

Probably would have been better if a bounded=False optional argument to Semaphore.__init__() had been added, rather than creating a new BoundedSemaphore class.  But, as is, it could easily be made reliable:

1. Change Semaphore's condition variable to use an RLock (instead of the current Lock).

2. Stuff the body of BoundedSemaphore.release() in a `with self._cond:` block.

Curiously, there doesn't appear to be a test that BoundedSemaphore.release ever raises ValueError.  So I'll readily agree that nobody ever took this seriously ;-)
msg199122 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2013-10-07 00:36
Attached patch, which closes the timing hole, and adds a new basic sanity test.
msg199125 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2013-10-07 03:04
New patch makes the test case do what I intended it to do ;-)
msg199180 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-10-08 08:50
The implementation is a bit weird. Why take the lock a second time instead of simply reimplementing the release() method?
(it's a 5-liner)

By the way, Semaphore.acquire could probably use Condition.wait_for.
msg199219 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2013-10-08 16:58
This is the "right" way to do it:  the subclass wants to extend the behavior of the base class .release(), not to replace it.  Calling the base class .release() is the natural and obvious way to do that.  It's also utterly normal for a lock used by multiple methods to be acquired & released multiple times - that's what an RLock is for.  What's odd to my eyes is that Semaphore - before the patch - went out of its way to _not_ use an RLock in its condition variable (Conditions use an RLock by default, for good reasons).

About acquire(), this is a bugfix - I'm not looking here to change code that isn't broken ;-)
msg199223 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-10-08 17:32
Le mardi 08 octobre 2013 à 16:58 +0000, Tim Peters a écrit :
> Tim Peters added the comment:
> 
> This is the "right" way to do it:  the subclass wants to extend the
> behavior of the base class .release(), not to replace it.  Calling the
> base class .release() is the natural and obvious way to do that.

Well... IMOHO it would be "natural and obvious" if those were in
different modules written by different developers.
Here I think that "practicality beats purity", though.
(although I'm not sure the person who originally wrote that sentence can
really be trusted ;-))

> About acquire(), this is a bugfix - I'm not looking here to change
> code that isn't broken ;-)

Agreed. Just wanted to mention it before I'd totally forget about it.
msg199237 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2013-10-08 18:58
Antoine, how strongly do you feel about this?  I confess I don't get it.  Copy+paste code duplication doesn't help any of readability, correctness, or ease of future maintenance, so I guess it's some micro-efficiency concern.  Really?! ;-)

Note that the patch doesn't _introduce_ calling the base class .release() - the code always did that.  All it does is put the pre-existing code in a `with:` block.  Minimal change.  Yes, the pre-existing code had to be indented, but no non-whitespace character changed.

Of course in this case it's trivial either way.  So if I have to duplicate the code to get your blessing, fine.  On the other hand, since it _is_ trivial either way, I'd rather not bother ;-)
msg199238 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-10-08 19:03
> Antoine, how strongly do you feel about this?  I confess I don't get
> it.  Copy+paste code duplication doesn't help any of readability,
> correctness, or ease of future maintenance, so I guess it's some
> micro-efficiency concern.  Really?! ;-)

Not very strongly, admittedly. It's just that I find the double locking
a bit silly while we control both implementations :-)
msg199239 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-10-08 19:03
(of course, you can go ahead and commit your version)
msg199273 - (view) Author: Roundup Robot (python-dev) Date: 2013-10-09 02:30
New changeset e06edc0c7a49 by Tim Peters in branch '3.3':
Issue 19158:  a rare race in BoundedSemaphore could allow .release() too often.
http://hg.python.org/cpython/rev/e06edc0c7a49

New changeset 7c56bf5afee6 by Tim Peters in branch 'default':
Issue 19158:  a rare race in BoundedSemaphore could allow .release() too often.
http://hg.python.org/cpython/rev/7c56bf5afee6

New changeset cb4fd7515cb4 by Tim Peters in branch '2.7':
Issue 19158:  a rare race in BoundedSemaphore could allow .release() too often.
http://hg.python.org/cpython/rev/cb4fd7515cb4
msg199278 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2013-10-09 08:12
You should mention the change in Misc/NEWS.
msg199325 - (view) Author: Roundup Robot (python-dev) Date: 2013-10-09 18:30
New changeset 369fabf9b2ba by Tim Peters in branch '3.3':
Issue 19158:  a rare race in BoundedSemaphore could allow .release() too often.
http://hg.python.org/cpython/rev/369fabf9b2ba

New changeset 9ddc33174ddf by Tim Peters in branch 'default':
Issue 19158:  a rare race in BoundedSemaphore could allow .release() too often.
http://hg.python.org/cpython/rev/9ddc33174ddf

New changeset 2ce77d9ed4b0 by Tim Peters in branch '2.7':
Issue 19158:  a rare race in BoundedSemaphore could allow .release() too often.
http://hg.python.org/cpython/rev/2ce77d9ed4b0
History
Date User Action Args
2013-10-09 18:30:24python-devsetmessages: + msg199325
2013-10-09 08:12:13hayposetmessages: + msg199278
2013-10-09 02:31:49tim.peterssetstatus: open -> closed
resolution: fixed
stage: patch review -> resolved
2013-10-09 02:30:14python-devsetnosy: + python-dev
messages: + msg199273
2013-10-08 19:03:28pitrousetmessages: + msg199239
2013-10-08 19:03:04pitrousetmessages: + msg199238
2013-10-08 18:58:36tim.peterssetmessages: + msg199237
2013-10-08 17:32:55pitrousetmessages: + msg199223
2013-10-08 16:58:13tim.peterssetmessages: + msg199219
2013-10-08 08:50:44pitrousetnosy: + pitrou
messages: + msg199180
2013-10-07 03:04:19tim.peterssetfiles: + boundsem2.patch

messages: + msg199125
2013-10-07 00:56:10hayposetnosy: + haypo
2013-10-07 00:36:52tim.peterssetfiles: + boundsem.patch
keywords: + patch
messages: + msg199122

stage: needs patch -> patch review
2013-10-04 17:29:17tim.peterssetmessages: + msg198959
2013-10-04 13:36:30sbtsetnosy: + sbt
messages: + msg198948
2013-10-04 00:00:16tim.peterscreate