Category refinement sometimes changes the hash of parents

[vbraun]

Some objects with dynamical classes use hash(self.__class__). Since this is not an invariant of dynamical classes bad things will happen.

One such instance is that, under some circumstances, a WeakValueDictionary remove callback is being called but cannot find the object in the dictionary since the hash changed.

Apply

• attachment: trac_14471_dynamic_class_hash.patch
• attachment: trac_14471-review.patch
• attachment: trac_14471-pdf-fix.patch

CC: @simon-king-jena @nbruin @nthiery @hivert

Component: memleak

Author: Volker Braun

Reviewer: Simon King

Merged: sage-5.12.beta0

Issue created by migration from https://trac.sagemath.org/ticket/14471

[vbraun]

Attachment: trac_14471_demonstrate.patch.gz

Initial patch

[vbraun]

Description changed:

--- 
+++ 
@@ -1,4 +1,4 @@
-Under some circumstances the WeakValueDictionary remove callback is being called when the internal dictionary is in a bad state. The attached patch to demonstrate the issue just calls `hasattr` from the displayhook, which ends up generating weak references somewhere. The exact place for where the exception occurs depends on the garbage collector, but I always do get some unwanted exceptions with it.
+Under some circumstances the WeakValueDictionary remove callback is being called when the internal dictionary is in a bad state. The attached patch [attachment: trac_14471_demonstrate.patch](https://github.com/sagemath/sage-prod/files/10657635/trac_14471_demonstrate.patch.gz) to demonstrate the issue just calls `hasattr` from the displayhook, which ends up generating weak references somewhere. The exact place for where the exception occurs depends on the garbage collector, but I always do get some unwanted exceptions with it.
 
 ```
 sage -t devel/sage/sage/matrix/matrix0.pyx
@@ -13,4 +13,3 @@
     Exception KeyError: (((<class 'sage.categories.algebras.Algebras'>, Callable function ring with arguments (x, y)), ()),) in <function remove at 0x18d8758> ignored
     True
 ```
-

[vbraun]

Initial patch

[vbraun]

comment:2

Attachment: debug_ignored_exceptions.patch.gz

The attachment: debug_ignored_exceptions.patch is a backport from Python-3.3 to give better diagnosis of ignored exceptions. With it, I get

    Exception ignored in: <function remove at 0x2472938>
    Traceback (most recent call last):
      File "/home/vbraun/opt/sage-5.9.beta5/local/lib/python/weakref.py", line 51, in remove
        del self.data[wr.key]
    KeyError: (((<class 'sage.categories.algebras.Algebras'>, Callable function ring with arguments (x, y)), ()),)

so the KeyError really comes from the WeakValueDictionary remove callback.

[vbraun]

comment:3

Adding some debugging in remove() shows that the wr.key is still in self.dict.keys() but del self.dict[wr.key] fails with a KeyError. Presumably because the whole thing is running during the garbage collection cycle. I tried #14159 but it didn't change anything.

I haven't figured out exactly which cache in the Sage library is the culprit, maybe Simon knows?

[nbruin]

comment:4

WeakValueDict is a standard python library class, not one of our own brew. So once we can put the finger on the bug we should likely report upstream. See also #13394, although I doubt the issue pointed out there is what is at play here.

My first guess would be that the cache at play is a "cached_method" or a "cached_function" cache, probably the one from UniqueRepresentation, but I'm not entirely sure. The entries in:

super(MatrixSpace,sage.matrix.matrix_space.MatrixSpace).__classcall__.get_cache().keys()

aren't quite of the shape you're finding.

A quick analysis; This is WeakValueDictionary.__init__:

    def __init__(self, *args, **kw):
        def remove(wr, selfref=ref(self)):
            self = selfref()
            if self is not None:
                del self.data[wr.key]
        self._remove = remove
        UserDict.UserDict.__init__(self, *args, **kw)

As you can see, remove only stores a link to the dictionary via a weak reference, so that the dictionary can get deallocated before the callback (and the callback finds that the dict doesn't exist anymore and simply does nothing). So that's correct.

We also see that remove only removes the key. It doesn't check whether the value is still what it's supposed to be and it also doesn't check if the key is still there in the first place. That would be safe if there's a guarantee that as soon as a value gets removed from the dictionary, the KeyedRef gets removed as well (in which case the callback dies without getting executed).

The bug we're seeing indicates that we end up with:

• weakvaluedict[key]=value
• key:KeyedRef(value) pair gets removed from dict - this should more or less atomically destroy the KeyedRef(value).
• somehow, the callback from the KeyedRef(value) stored gets called before it gets destroyed.

Since the KeyedRef(value) should really only be referenced from the weakvaluedict, it's a bit hard to let it survive: As soon it gets decreffed it should get deallocated.

My guess is that this happens IN cyclic garbage removal, where callbacks do get separated from deletions. Python tries hard to avoid calling such callbacks unnecessarily or in situations where it's unsafe to do so, but perhaps cleaning up extremely complicated cyclic structures (which we do create) could fool the detection.

If this is right, then these keyerrors should be relatively harmless: They would be happening on a dictionary that is slated for demolition anyway. That would suggest we could just catch and ignore the keyerror in the WeakValueDictionary removal function. It would be good to identify the scenario that justifies doing so, however.

[vbraun]

comment:5

I agree and verified with gc.get_referrers that it is sage.structure.unique_representation.CachedRepresentation.__classcall__.cache

If I change the remove() callback to

                import sys
                print >> sys.stderr, 'removing', wr.key in self.data.keys()
                del self.data[wr.key]
                print >> sys.stderr, 'finished removing'

then I get

    ...
    removing True
    finished removing
    removing True
    Exception KeyError: (((<class 'sage.categories.algebras.Algebras'>, Callable function ring with arguments (x, y)), ()),) in <function remove at 0x1acf758> ignored
    removing True
    finished removing
    removing True
    finished removing
    ...

So the weakvaluedict (self.data) is in a bad state...

[nbruin]

comment:6

Replying to @vbraun:

So the weakvaluedict (self.data) is in a bad state...

self.data is a normal dict. Your example doesn't quite show the dict is in a "bad state". It shows that between testing whether the key is in the dict and doing the delete, the key has been removed. That's not quite the same as self.data beng corrupted.

Something is going wrong of course, though. Something seems to be mutating self.data in between. The only methods that seem to be mutating the underlying self.data for a WeakValueDictionary are __setitem__, popitem, pop, setdefault, update (and of course __delitem__ and clear it inherits from UserDict). Perhaps I don't have enough imagination, but indeed the only scenario in which I could see one of those happening during a callback is when a GC gets triggered and basically the whole dict gets cleaned up.

Some of the "iterator" methods on WeakValueDict don't quite seem safe to me, by the way. The iteritems method, for instance, iterates over self.data.itervalues(), but self.data can be mutated outside of your control due to GC callbacks, and iterators over a mutating dict are generally not safe.
I doubt that's what's hurting us here, though.

[vbraun]

comment:7

Replying to @nbruin:

Replying to @vbraun:

So the weakvaluedict (self.data) is in a bad state...

self.data is a normal dict. Your example doesn't quite show the dict is in a "bad state".

Fair enough, but even after I catch the KeyError the wr.key in self.data.keys() is still True. So the self.data dict is in a weird place for sure.

I agree that this smells like something else is mutating self.data in-between. It is possible that deallocation somewhere triggers a call to CachedRepresentation, but I don't see where that would be the case.

[vbraun]

gdb/cython backtrace