WeakValueDictionary next bug (with multithreading)

[arigo]

BPO	28427
Nosy	@tim-one, @freddrake, @arigo, @pitrou, @larryhastings, @methane, @serhiy-storchaka
Files	test.py issue28427.py issue28427.patch: Patch that fixes a part of the bug issue28427-2.patch issue28427-3.patch issue28427-atomic.patch issue28427-3.6.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2016-12-27.14:11:09.208>
created_at = <Date 2016-10-13.10:36:29.136>
labels = ['3.7', 'type-bug', 'library']
title = 'WeakValueDictionary next bug (with multithreading)'
updated_at = <Date 2017-08-02.14:08:14.442>
user = 'https://github.com/arigo'

bugs.python.org fields:

activity = <Date 2017-08-02.14:08:14.442>
actor = 'dubiousjim'
assignee = 'none'
closed = True
closed_date = <Date 2016-12-27.14:11:09.208>
closer = 'pitrou'
components = ['Library (Lib)']
creation = <Date 2016-10-13.10:36:29.136>
creator = 'arigo'
dependencies = []
files = ['45072', '45082', '45083', '45215', '45709', '45710', '45965']
hgrepos = []
issue_num = 28427
keywords = ['patch']
message_count = 20.0
messages = ['278555', '278587', '278637', '279380', '282053', '282054', '282087', '282088', '282089', '282407', '282409', '282428', '282432', '282434', '283625', '284096', '284100', '284101', '298283', '299659']
nosy_count = 9.0
nosy_names = ['tim.peters', 'fdrake', 'arigo', 'pitrou', 'larry', 'methane', 'python-dev', 'serhiy.storchaka', 'dubiousjim']
pr_nums = []
priority = 'critical'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue28427'
versions = ['Python 2.7', 'Python 3.5', 'Python 3.6', 'Python 3.7']

[arigo]

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.

[serhiy-storchaka]

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.

[arigo]

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]

[serhiy-storchaka]

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.

[pitrou]

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.

[pitrou]

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

[pitrou]

Here is a pure Python patch.

[pitrou]

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.

[pitrou]

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.

[arigo]

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

[pitrou]

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

[arigo]

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. ('bpo-28427-atomic.patch' does not help for that, but I might have missed a different case where it does help.)