[issue28427] WeakValueDictionary next bug (with multithreading)

[dubiousjim]

dubiousjim added the comment:

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?

--
nosy: +dubiousjim

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28427] WeakValueDictionary next bug (with multithreading)

[Serhiy Storchaka]

Changes by Serhiy Storchaka :


--
pull_requests:  -849

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28427] WeakValueDictionary next bug (with multithreading)

[Larry Hastings]

Larry Hastings added the comment:

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.

--
nosy: +larry

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28427] WeakValueDictionary next bug (with multithreading)

[Donald Stufft]

Changes by Donald Stufft :


--
pull_requests: +849

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28427] WeakValueDictionary next bug (with multithreading)

[Antoine Pitrou]

Antoine Pitrou added the comment:

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...

--
resolution:  -> fixed
stage: patch review -> resolved
status: open -> closed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28427] WeakValueDictionary next bug (with multithreading)

[Roundup Robot]

Roundup Robot added the comment:

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

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28427] WeakValueDictionary next bug (with multithreading)

[Roundup Robot]

Roundup Robot added the comment:

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

--
nosy: +python-dev

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28427] WeakValueDictionary next bug (with multithreading)

[Antoine Pitrou]

Antoine Pitrou added the comment:

The dict implementation in 3.6 has become very complicated, so I'd like someone 
to review the attached 3.6 patch. Serhiy, Inada?

--
nosy: +inada.naoki
Added file: http://bugs.python.org/file45965/issue28427-3.6.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28427] WeakValueDictionary next bug (with multithreading)

[Armin Rigo]

Armin Rigo added the comment:

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().

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28427] WeakValueDictionary next bug (with multithreading)

[Antoine Pitrou]

Antoine Pitrou added the comment:

> 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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28427] WeakValueDictionary next bug (with multithreading)

[Armin Rigo]

Armin Rigo added the comment:

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.)

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28427] WeakValueDictionary next bug (with multithreading)

[Antoine Pitrou]

Antoine Pitrou added the comment:

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().

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28427] WeakValueDictionary next bug (with multithreading)

[Armin Rigo]

Armin Rigo added the comment:

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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28427] WeakValueDictionary next bug (with multithreading)

[Antoine Pitrou]

Changes by Antoine Pitrou :


--
stage:  -> patch review

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28427] WeakValueDictionary next bug (with multithreading)

[Antoine Pitrou]

Antoine Pitrou added the comment:

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.

--
Added file: http://bugs.python.org/file45710/issue28427-atomic.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28427] WeakValueDictionary next bug (with multithreading)

[Antoine Pitrou]

Antoine Pitrou added the comment:

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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28427] WeakValueDictionary next bug (with multithreading)

[Antoine Pitrou]

Antoine Pitrou added the comment:

Here is a pure Python patch.

--
Added file: http://bugs.python.org/file45709/issue28427-3.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28427] WeakValueDictionary next bug (with multithreading)

[Antoine Pitrou]

Antoine Pitrou added the comment:

(or we bite the bullet and add a C helper function for the atomic 
test-and-delete thing)

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28427] WeakValueDictionary next bug (with multithreading)

[Antoine Pitrou]

Antoine Pitrou added the comment:

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.

--
nosy: +pitrou, tim.peters

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28427] WeakValueDictionary next bug (with multithreading)

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

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.

--
components: +Library (Lib)
priority: normal -> critical
Added file: http://bugs.python.org/file45215/issue28427-2.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28427] WeakValueDictionary next bug (with multithreading)

[Armin Rigo]

Armin Rigo added the comment:

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]

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28427] WeakValueDictionary next bug (with multithreading)

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

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.

--
Added file: http://bugs.python.org/file45082/issue28427.py

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28427] WeakValueDictionary next bug (with multithreading)

[Serhiy Storchaka]

Changes by Serhiy Storchaka :


--
keywords: +patch
Added file: http://bugs.python.org/file45083/issue28427.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28427] WeakValueDictionary next bug (with multithreading)

[Serhiy Storchaka]

Changes by Serhiy Storchaka :


--
nosy: +fdrake, serhiy.storchaka
versions: +Python 3.7 -Python 3.3

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28427] WeakValueDictionary next bug (with multithreading)

[Armin Rigo]

New submission from Armin Rigo:

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.

--
files: test.py
messages: 278555
nosy: arigo
priority: normal
severity: normal
status: open
title: WeakValueDictionary next bug (with multithreading)
type: behavior
versions: Python 2.7, Python 3.3, Python 3.5, Python 3.6
Added file: http://bugs.python.org/file45072/test.py

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com