classification
Title: WeakValueDictionary next bug (with multithreading)
Type: behavior Stage: resolved
Components: Library (Lib) Versions: Python 3.7, Python 3.6, Python 3.5, Python 2.7
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: arigo, dubiousjim, fdrake, inada.naoki, larry, pitrou, python-dev, serhiy.storchaka, tim.peters
Priority: critical Keywords: patch

Created on 2016-10-13 10:36 by arigo, last changed 2017-08-02 14:08 by dubiousjim. This issue is now closed.

Files
File name Uploaded Description Edit
test.py arigo, 2016-10-13 10:36
issue28427.py serhiy.storchaka, 2016-10-13 18:22
issue28427.patch serhiy.storchaka, 2016-10-13 18:24 Patch that fixes a part of the bug review
issue28427-2.patch serhiy.storchaka, 2016-10-25 09:51 review
issue28427-3.patch pitrou, 2016-11-30 17:23 review
issue28427-atomic.patch pitrou, 2016-11-30 18:05
issue28427-3.6.patch pitrou, 2016-12-19 14:23
Messages (20)
msg278555 - (view) Author: Armin Rigo (arigo) * (Python committer) Date: 2016-10-13 10:36
Follow-up on http://bugs.python.org/issue19542.

Another crash of using WeakValueDictionary() in a thread-local fashion inside a multi-threaded program.  I must admit I'm not exactly sure why this occurs, but it is definitely showing an issue: two threads independently create their own WeakValueDictionary() and try to set one item in it.  The problem I get is that the "assert 42 in d" sometimes fails, even though 42 was set in that WeakValueDictionary on the previous line and the value is still alive.  This only occurs if there is a cycle of references involving the value.  See attached file.

Reproduced on Python 2.7, 3.3, 3.5, 3.6-debug.
msg278587 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-10-13 18:22
Here is simpler reproducer for Python 3. One thread updates WeakValueDictionary in a loop, other threads runs garbage collecting in a loop. Values are collected asynchronously and this can cause removing new value by old key. Following patch fixes this example (or at least makes race condition much less likely). But it doesn't fix the entire issue. If add list(d) after setting a new value, the example fails again.
msg278637 - (view) Author: Armin Rigo (arigo) * (Python committer) Date: 2016-10-14 07:57
I'll admit I don't know how to properly fix this issue.  What I came up with so far would need an atomic compare_and_delete operation on the dictionary self.data, so that we can do atomically:

+                elif self.data[wr.key] is wr:
                     del self.data[wr.key]
msg279380 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-10-25 09:51
Following patch fixes more cases. But I don't think it fixes race conditions, it just makes them less likely.

Increased priority because this bug makes weakref.WeakValueDictionary unusable in multithread program.
msg282053 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2016-11-29 23:38
One possibility would be to always delay removals (always put them in _pending_removals).
We would then have to enforce removals from time to time, but synchronously.
msg282054 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2016-11-29 23:39
(or we bite the bullet and add a C helper function for the atomic test-and-delete thing)
msg282087 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2016-11-30 17:23
Here is a pure Python patch.
msg282088 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2016-11-30 17:24
Note the issue with this patch is that it may keep keys (with dead values) alive longer than necessary:
- this may prevent memory consumption from decreasing
- this may keep alive some system resources

This is ok when keys are small simple objects (strings or tuples), though.
msg282089 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2016-11-30 18:05
Here is a patch showing the "atomic C function" approach.  It will avoid the aforementioned memory growth in the common case, in exchange for a small bit of additional C code.
msg282407 - (view) Author: Armin Rigo (arigo) * (Python committer) Date: 2016-12-05 09:58
issue28427-atomic.patch: is it still necessary to modify weakref.py so much, then?

What I had in mind was a C function with Python signature "del_if_equal(dict, key, value)"; the C function doesn't need to know about weakrefs and checking if they are dead.  The C function would simply call PyObject_GetItem() and PyObject_DelItem()---without releasing the GIL in the middle.
msg282409 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2016-12-05 10:22
Hi Armin,

> is it still necessary to modify weakref.py so much, then?

Not sure. I'll take a look again. Modifying __len__() at least is necessary, as the previous version took into account the length of _pending_removals (and could therefore return wrong results). I'm inclined to be a bit defensive here.

> The C function would simply call PyObject_GetItem() and PyObject_DelItem()---without releasing the GIL in the middle.

If you implement it like that, and the dictionary has non-trivial keys with a user-defined __hash__, then the GIL can be released at the beginning of PyObject_DelItem().
msg282428 - (view) Author: Armin Rigo (arigo) * (Python committer) Date: 2016-12-05 16:23
I think the issue of __len__() is a different matter.  More below.

>> The C function would simply call PyObject_GetItem() and
>> PyObject_DelItem()---without releasing the GIL in the middle.
>
> If you implement it like that, and the dictionary has non-trivial
> keys with a user-defined __hash__, then the GIL can be released
> at the beginning of PyObject_DelItem().

Right, I see your point: your version will, in any case, remove only a dead weakref as a dictionary value.  +1

Now about __len__() returning a wrong result: it is a more complicated issue, I fear.  I already patched weakref.py inside PyPy in order to pass a unit test inside CPython's test suite.  This patch is to change __len__ to look like this:

    def __len__(self):
        # PyPy change: we can't rely on len(self.data) at all, because
        # the weakref callbacks may be called at an unknown later time.
        result = 0
        for wr in self.data.values():
            result += (wr() is not None)
        return result

The problem is the delay between the death of a weakref and the actual invocation of the callback, which is systematic on PyPy but can be observed on CPython in some cases too.  It means that code like this may fail:

     if list(d) == []:
         assert len(d) == 0

because list(d) might indeed be empty, but some callbacks have not been called so far and so any simple formula in __len__() will fail to account for that.  ('issue28427-atomic.patch' does not help for that, but I might have missed a different case where it does help.)
msg282432 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2016-12-05 16:38
> Now about __len__() returning a wrong result: it is a more complicated issue, I fear.  I already patched weakref.py inside PyPy in order to pass a unit test inside CPython's test suite.  This patch is to change __len__ to look like this: [...]

Thanks for the explanation. Yes, you are right on the principle. But there is also a general expectation that len() on an in-memory container is a O(1) operation, not O(n) - this change would break that expectation quite heavily.

I don't know how to fix len() without losing O(1) performance. It seems we're in a bit of a quandary on this topic. However, we can still fix the other issues.
msg282434 - (view) Author: Armin Rigo (arigo) * (Python committer) Date: 2016-12-05 16:50
Agreed about fixing the other issues.  I'm still unclear that we need anything more than just the _remove_dead_weakref function to do that, but also, I don't see a particular problem with adding self._commit_removals() a bit everywhere.

About the O(1) expectation for len(): it's still unclear if it is better to give a precise answer or if an over-estimate is usually enough.  I can see of no reasonable use for a precise answer---e.g. code like this

    while len(d) > 0:
        do_stuff(d.popitem())

is broken anyway, because a weakref might really die between len(d) and d.popitem().  But on the other hand it makes tests behave strangely.  Maybe the correct answer is that such tests are wrong---then I'd be happy to revert the PyPy-specific change to __len__() and fix the test instead.  Or maybe weakdicts should always raise in __len__(), and instead have a method .length_upper_bound().
msg283625 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2016-12-19 14:23
The dict implementation in 3.6 has become very complicated, so I'd like someone to review the attached 3.6 patch. Serhiy, Inada?
msg284096 - (view) Author: Roundup Robot (python-dev) Date: 2016-12-27 13:37
New changeset b8b0718d424f by Antoine Pitrou in branch '3.5':
Issue #28427: old keys should not remove new values from
https://hg.python.org/cpython/rev/b8b0718d424f

New changeset 97d6616b2d22 by Antoine Pitrou in branch '3.6':
Issue #28427: old keys should not remove new values from
https://hg.python.org/cpython/rev/97d6616b2d22

New changeset e5ce7bdf9e99 by Antoine Pitrou in branch 'default':
Issue #28427: old keys should not remove new values from
https://hg.python.org/cpython/rev/e5ce7bdf9e99
msg284100 - (view) Author: Roundup Robot (python-dev) Date: 2016-12-27 14:09
New changeset 9acdcafd1418 by Antoine Pitrou in branch '2.7':
Issue #28427: old keys should not remove new values from
https://hg.python.org/cpython/rev/9acdcafd1418
msg284101 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2016-12-27 14:11
I've pushed the fixes now.  It does introduce a small amount of additional code duplication in dictobject.c, but nothing unmanageable.

Sidenote: all branches now have a different version of dict object each, which makes maintenance really painful...
msg298283 - (view) Author: Larry Hastings (larry) * (Python committer) Date: 2017-07-13 12:43
I tested this in a freshly-built 3.4.6.  Although it reproduced the behavior you're complaining about--it threw the assert in Armin's test.py, and Serhiy's issue28427.py prints an admonishing FAIL--neither test *crashes* CPython.  So I'm not convinced either of these is a *security* risk.  This is a bug, and 3.4 isn't open for bugfixes, so I don't plan to accept a backport for this in 3.4.

If this is a crashing bug, please tell me how to reproduce the crashing bug with 3.4.6.
msg299659 - (view) Author: (dubiousjim) Date: 2017-08-02 14:08
In response to Issue #7105, self._pending_removals was added to WeakValueDictionaries (and also WeakKeyDictionaries, but they're not relevant to what I'm about to discuss). This was in changesets 58194 to tip and 58195 to 3.1, back in Jan 2010. In those changesets, the implementation of WeakValueDictionary.setdefault acquired a check on self._pending_removals, but only after the key lookup had failed. (See lines starting 5.127 in both those changesets.)

In changeset 87778, in Dec 2013, this same patch was backported to 2.7.

More recently, in response to the issue discussed above (Issue #28427), similar checks were added to WeakValueDictionary.get, but now BEFORE the  key lookup. This was in changesets 105851 to 3.5, 105852 to 3.6, 105853 to tip, and 105854 to 2.7, in Dec 2016. Notably, in the last changeset, the check on self._pending_removals on WeakValueDictionary.setdefault is also moved to the top of the function, before the key lookup is attempted. This parallels the change being made to WeakValueDictionary.get.

However, that change to WeakValueDictionary.setdefault was only made to the 2.7 branch. If it's correct, then why wasn't the same also done for 3.5, 3.6, and tip?
History
Date User Action Args
2017-08-02 14:08:14dubiousjimsetnosy: + dubiousjim
messages: + msg299659
2017-07-13 13:01:59serhiy.storchakasetpull_requests: - pull_request849
2017-07-13 12:43:33larrysetnosy: + larry
messages: + msg298283
2017-03-31 16:36:09dstufftsetpull_requests: + pull_request849
2016-12-27 14:11:09pitrousetstatus: open -> closed
resolution: fixed
messages: + msg284101

stage: patch review -> resolved
2016-12-27 14:09:49python-devsetmessages: + msg284100
2016-12-27 13:37:26python-devsetnosy: + python-dev
messages: + msg284096
2016-12-19 14:23:12pitrousetfiles: + issue28427-3.6.patch
nosy: + inada.naoki
messages: + msg283625

2016-12-05 16:50:49arigosetmessages: + msg282434
2016-12-05 16:38:44pitrousetmessages: + msg282432
2016-12-05 16:23:19arigosetmessages: + msg282428
2016-12-05 10:22:08pitrousetmessages: + msg282409
2016-12-05 09:58:46arigosetmessages: + msg282407
2016-11-30 18:05:15pitrousetstage: patch review
2016-11-30 18:05:09pitrousetfiles: + issue28427-atomic.patch

messages: + msg282089
2016-11-30 17:24:15pitrousetmessages: + msg282088
2016-11-30 17:23:09pitrousetfiles: + issue28427-3.patch

messages: + msg282087
2016-11-29 23:39:52pitrousetmessages: + msg282054
2016-11-29 23:38:59pitrousetnosy: + pitrou, tim.peters
messages: + msg282053
2016-10-25 09:51:55serhiy.storchakasetpriority: normal -> critical
files: + issue28427-2.patch
messages: + msg279380

components: + Library (Lib)
2016-10-14 07:57:22arigosetmessages: + msg278637
2016-10-13 18:24:07serhiy.storchakasetfiles: + issue28427.patch
keywords: + patch
2016-10-13 18:22:38serhiy.storchakasetfiles: + issue28427.py

messages: + msg278587
2016-10-13 12:39:01serhiy.storchakasetnosy: + fdrake, serhiy.storchaka

versions: + Python 3.7, - Python 3.3
2016-10-13 10:36:29arigocreate