Don't install callbacks on values of TripleDict, MonoDict

[nbruin]

In #11521 trac_11521_callback.patch a callback was installed on a weakref value of a TripleDict:

 _cache[key] = KeyedRef(H, _cache.eraser, (id(X),id(Y),id(category)))

That's not safe: If the value under that key gets changed while the value remains in memory, the callback will be executed and remove an entry that now has an unrelated value!

So: Either prove that the value under this key will not change for the lifetime of H (keep in mind that cyclic references can extend the lifetime of an otherwise unreachable object essentially indefinitely, so the proof needs to include that all key components survive H, otherwise those ids could get reused) or provide a more selective callback (for instance, ensure that the value is still as expected before deleting).

Note: The patch trac_14159_safer_callback.patch follows the second approach, so that a memory leak remains fixed.

Another point is that the API of _cache.eraser isn't really published, so this behaviour is probably better encapsulated in a method on the dict itself.

See #12313 comment 317 for a situation that likely implicates these callbacks (someone has to hold strong references to these keys in order to set the dict, so the absence of the keys suggests a spurious execution of this kind of callback)

Apply

• attachment: trac_14159_weak_value_triple_dict.patch
• attachment: trac_14159_use_cdef_get.patch

Depends on #13387
Depends on #14254

CC: @simon-king-jena @jpflori

Component: memleak

Author: Simon King

Reviewer: Nils Bruin

Merged: sage-5.10.beta0

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

[simon-king-jena]

comment:1

What do you mean by "value under that key"?

Ah! You mean this situation: T[a,b,c]=v and later T[a,b,c]=w. Then v might become garbage collected and its callback would remove w from the dictionary.

Indeed, this would be bad.

Potential solutions (two alternatives):

1. The callback shall test whether the value in the entry to be deleted coincides with the value that is being garbage collected.

2. If an existing entry is overwritten by __setitem__ then its callback will be removed.

[nbruin]

comment:2

Replying to @simon-king-jena:

2. If an existing entry is overwritten by __setitem__ then its callback will be removed.

I guess you could reach into the KeyedRef object and invalidate the key to prevent action on callback. Doing so would complicate all our dict setting and deleting, so I think that is not an attractive option.

Just deleting the KeyedRef object won't guarantee it will go away: someone else may be holding a reference to the KeyedRef object as well.

So probably there needs to be an additional option on ...DictEraser objects to check that the value is as expected (or write yet another callback class, but that sounds like a waste).

And then ...Dict would grow an extra set_weak_value to install the appropriate KeyedRef on the value, because letting other code instantiate eraser objects is scary.

It feels like horrible feature creep, but I guess you have a good use case (can you come up with an alternative solution?)

[simon-king-jena]

comment:3

Replying to @nbruin:

Replying to @simon-king-jena:

2. If an existing entry is overwritten by __setitem__ then its callback will be removed.

I guess you could reach into the KeyedRef object and invalidate the key to prevent action on callback. Doing so would complicate all our dict setting and deleting, so I think that is not an attractive option.

So, what about the first option? It would make sure that an entry will only be deleted if the value is identical with the object whose callback is being called.

[nbruin]

comment:4

Replying to @simon-king-jena:

So, what about the first option? It would make sure that an entry will only be deleted if the value is identical with the object whose callback is being called.

Yes, sorry for not being clear about it. That's what the second part of the reply expands on.

[simon-king-jena]

comment:5

Replying to @nbruin:

Replying to @simon-king-jena:

So, what about the first option? It would make sure that an entry will only be deleted if the value is identical with the object whose callback is being called.

Yes, sorry for not being clear about it. That's what the second part of the reply expands on.

Sorry, I don't see the relation with suggestion 1.

So probably there needs to be an additional option on ...DictEraser objects to check that the value
is as expected

Why? The callback would be checking that the value is identical with the object pointed to by the weak reference. This should be cheap enough to be done by default.

[simon-king-jena]

comment:6

I thought that the following would expose the problem, but it doesn't:

sage: from sage.structure.coerce_dict import TripleDict
sage: import gc
sage: class Foo: pass
sage: 
sage: a = 1
sage: b = 2
sage: c = 3
sage: v = Foo()
sage: w = Foo()
sage: T = TripleDict(13)
sage: T[a,b,c] = v
sage: T[a,b,c] = w
sage: del v
sage: _ = gc.collect()
sage: len([x for x in gc.get_objects() if isinstance(x,Foo)])
1

So, v got collected and thus the callback was executed. However:

sage: id(T[a,b,c])
85762632
sage: id(w)
85762632

The entry that was previously holding v did not get deleted when v's callback was called.

So, are we really in trouble?

[nbruin]

comment:7

You have to make sure that the weakref object lives to see the death of v (and ensure that you make such a weakref in the first place!)

sage: from sage.structure.coerce_dict import TripleDict
sage: import gc
sage: import weakref
sage: class Foo: pass
sage: 
sage: a = 1
sage: b = 2
sage: c = 3
sage: v = Foo()
sage: w = Foo()
sage: T = TripleDict(13)
sage: T[a,b,c] = weakref.KeyedRef(v,T.eraser,(id(a),id(b),id(c)))
sage: h=T[a,b,c]
sage: T[a,b,c] = w
sage: del v
sage: _ = gc.collect()
sage: len([x for x in gc.get_objects() if isinstance(x,Foo)])
1
sage: T[a,b,c] == w
KeyError: (1, 2, 3)

I admit, the weakref surviving outside the dict is not a terribly likely event, but from your code at #11521 it wasn't entirely clear to me that you can absolutely rule it out.

[simon-king-jena]

comment:8

Replying to @nbruin:

You have to make sure that the weakref object lives to see the death of v (and ensure that you make such a weakref in the first place!)

Apparently I had wrong memories about my code, then. I had in mind that the TripleDict has a weak reference with callback to the value.

sage: from sage.structure.coerce_dict import TripleDict
sage: import gc
sage: import weakref
sage: class Foo: pass
sage: 
sage: a = 1
sage: b = 2
sage: c = 3
sage: v = Foo()
sage: w = Foo()
sage: T = TripleDict(13)
sage: T[a,b,c] = weakref.KeyedRef(v,T.eraser,(id(a),id(b),id(c)))
sage: h=T[a,b,c]
sage: T[a,b,c] = w
sage: del v
sage: _ = gc.collect()
sage: len([x for x in gc.get_objects() if isinstance(x,Foo)])
1
sage: T[a,b,c] == w
KeyError: (1, 2, 3)

I admit, the weakref surviving outside the dict is not a terribly likely event, but from your code at #11521 it wasn't entirely clear to me that you can absolutely rule it out.

Hm. This particular TripleDict is only used by hom, and hom doe not override an existing entry. So, this particular case should be safe. However, it still seems reasonable to me to let the callback check whether the to-be-deleted value did not change.

[nbruin]

comment:9

Replying to @simon-king-jena:

Hm. This particular TripleDict is only used by hom, and hom doe not override an existing entry. So, this particular case should be safe. However, it still seems reasonable to me to let the callback check whether the to-be-deleted value did not change.

I was fully expecting that to be true, but I could not come up with an explanation for the bug Jeroen reported at #12313, where the line in

 _cache[key] = KeyedRef(H, _cache.eraser, (id(X),id(Y),id(category)))

leads to a key error in TripleDict.set in the line:

r1,r2,r3 = <tuple>(self._refcache[h1,h2,h3])

The only thing I could think of for that line to fail is:

• This KeyedRef object W is constructed
• _cache.set(k1,k2,k3,W) is called with k1=id(X),k2=id(Y),k3=id(category). Note that the caller is holding strong references to (X,Y,category).
• In order to end up in the line r1,r2,r3 = <tuple>(self._refcache[h1,h2,h3]), the key triple (k1,k2,k3) must be present in this TripleDict and hence in self._refcache
• Yet, we get a KeyError. Calling self._refcache[h1,h2,h3] requires the construction of a new tuple (h1,h2,h3), which could trigger a GC and hence a callback that would remove entries. So the only explanation I see is that we're getting a callback with key (k1,k2,k3) due to a GC triggered by this tuple allocation.
• However, this callback cannot result from any of X,Y,category getting collected, because someone is holding strong references to them. Hence such a callback must be coming from somewhere else.
• The code pointed to (ironically the same code that triggers this TripleDict operation) is an example of code that installs such callbacks. So a possible scenario is that a statement
  _cache.set(k1,k2,k3,Wold)
  was executed before, that Wold is still hanging around in memory and that it finally gets removed due to this poorly timed garbage collection and consequently that the keytriple (k1,k2,k3) receives a callback, even though they are pointing to (or are about to be pointing to -- we don't know what happened in between) another, unrelated value.

In this scenario, values in this Hom dictionary do get changed.

We need to ensure that TripleDict cannot trigger GC at that point anyway (and that is what #13387 does as a side-effect), because all kinds of other bad things could happen as well. However, given that it needs such a complicated explanation, I would hope we can verify my assumptions, because otherwise my fix might not be sufficient.

Hence the formulation of the ticket: If you can prove that installing this callback is safe, I have no problem with it.

[nbruin]

comment:10

Ouch, I looked at that code and you're correct: That doesn't overwrite the value at all (it's really a cache). Incidentally, at that code:

    try:
        H = _cache[key]()
    except KeyError:
        H = None
    if H is not None:
        # Are domain or codomain breaking the unique parent condition?
        if H.domain() is X and H.codomain() is Y:
            return H

Since X,Y are part of key, which is looked up by identity, the "domain" and "codomain" test should really be superfluous. So perhaps we want

if H is not None:
   assert H.domain() is X and H.codomain() is Y
   return H

since something is going very wrong if this is not the case! (H would not be allowed to sit there in the dict).

Furthermore, H has strong references to X,Y,category in the form of H.domain(), H.codomain() and H.homset_category(), so if H is alive then so must the keys. Which means that the callback on H must happen (or be purged) before those on X,Y etc., or at least in the same GC.
so their ids can't get reused until their callbacks have happened or have been discarded.

I think that only leaves the possibility that _cache got silently corrupted due to a GC at an inopportune time before this particular error. We cannot rule that out, but it's extremely unlikely: It requires a bucket to be rather full and buckets are typically not full at all (ideally only one entry).

On the other hand, since this is a global _cache, it does get to hold quite a few keys, so it's quite likely that it underwent a resize operation, where a corruption was much more likely to happen.

It's rather difficult to do an accurate postmortem with so little data.

[nbruin]

patch that got misplaced on #12313

[simon-king-jena]

comment:11

Attachment: trac_12313-revert_callback_from_11521.patch.gz

Thank you for moving the patch to the right location (I forgot about the existence of this ticket...).

[simon-king-jena]

Author: Simon King