bug#10836: guardians and weak references

bug#10836: guardians and weak references

[Andy Wingo]

Hi,

  scheme@(guile-user)> (define x (list 1))
  scheme@(guile-user)> (define g (make-guardian))
  scheme@(guile-user)> (define p (make-object-property ))
  scheme@(guile-user)> (g x)
  scheme@(guile-user)> (set! (p x) 100)
  $1 = 100
  scheme@(guile-user)> (p x)
  $2 = 100
  scheme@(guile-user)> (set! x #f)
  scheme@(guile-user)> (gc) (gc) (gc)
  scheme@(guile-user)> (g)
  $3 = (1)
  scheme@(guile-user)> (p $3)
  $4 = #f
  scheme@(guile-user)> 

The problem: weak references are dropped at finalization time, when
guardians do their magic.  If the guardian resuscitates the value, weak
references (like those in the object property) are lost.  This is in
contradiction to what the manual says on the subject:

     Being an element in a weak vector, a key in a hash table with weak
     keys, or a value in a hash table with weak values does not prevent
     an object from being returned by a guardian.  But as long as an
     object can be returned from a guardian it will not be removed from
     such a weak vector or hash table.  In other words, a weak link
     does not prevent an object from being considered collectable, but
     being inside a guardian prevents a weak link from being broken.

Andy
-- 
http://wingolog.org/

bug#10836: guardians and weak references

[Andy Wingo]

On Fri 17 Feb 2012 15:52, Andy Wingo <wingo@pobox.com> writes:

>   (define x (list 1))
>   (define g (make-guardian))
>   (define p (make-object-property ))
>   (g x)
>   (set! (p x) 100)
>   $1 = 100
>   (p x)
>   $2 = 100
>   (set! x #f)
>   (gc) (gc) (gc)
>   (g)
>   $3 = (1)
>   (p $3)
>   $4 = #f
>
> The problem: weak references are dropped at finalization time, when
> guardians do their magic.  If the guardian resuscitates the value, weak
> references (like those in the object property) are lost.  This is in
> contradiction to what the manual says on the subject:
>
>      Being an element in a weak vector, a key in a hash table with weak
>      keys, or a value in a hash table with weak values does not prevent
>      an object from being returned by a guardian.  But as long as an
>      object can be returned from a guardian it will not be removed from
>      such a weak vector or hash table.  In other words, a weak link
>      does not prevent an object from being considered collectable, but
>      being inside a guardian prevents a weak link from being broken.

I have looked at this issue in depth.  Disappearing links are indeed
broken at finalization time (when the object is still reachable, from
the finalizer itself).

I tried reimplementing weak tables using finalizers.  (The finalizers
remove elements from the table).  As long as we ensure that the
guardian's finalizers run first, which is possible for Guile to do, that
does fix this bug.

However, using finalizers has the downside that it introduces races with
custom hash/equality predicates.  Consider:

  * Add an entry X -> Y to a weak-key table.

  * X becomes unreachable.  Libgc enqueues a finalizer.

  * Lookup the handle for (X -> Y), but using a custom predicate that
    relies on some aspect of X that is not its identity.  Keep X
    around.

  * The finalizer runs, removing the entry from the table.

  * Add an entry of a somehow equivalent X -> Y to a weak-key table.

  * A future lookup of X fails to return the same handle as before.

Disappearing links avoid this race, it seems, because they disappear
synchronously with the observable unreachability of the object, not
asynchronously (via finalizers).

This synchronicity is reflected in the use of the alloc-lock -- you can
only access disappearing links from within the global allocator lock.
OTOH finalizers can take more fine-grained mutexen on the structures
they manipulate, scaling better but at the cost of introducing
noticeable asynchrony.

I actually saw this bug, in which two symbols had the same characters
but different identities, with the race condition outlined above (lookup
vs finalizer).

Not sure what to do here.

Andy
-- 
http://wingolog.org/

bug#10836: guardians and weak references

[Mark H Weaver]

Andy Wingo <wingo@pobox.com> writes:
> I tried reimplementing weak tables using finalizers.  (The finalizers
> remove elements from the table).  As long as we ensure that the
> guardian's finalizers run first, which is possible for Guile to do, that
> does fix this bug.
>
> However, using finalizers has the downside that it introduces races with
> custom hash/equality predicates.  Consider:
>
>   * Add an entry X -> Y to a weak-key table.
>
>   * X becomes unreachable.  Libgc enqueues a finalizer.
>
>   * Lookup the handle for (X -> Y), but using a custom predicate that
>     relies on some aspect of X that is not its identity.  Keep X
>     around.

Is there a need for weak-key tables that use something other than 'eq?'
as the predicate?  It's not clear to me that any other predicate makes
sense for a weak-key table.  To my mind, the idea is that we can safely
delete table entries if and only if we can prove that they could not be
looked up anyway.  This fits in very nicely with the concept of garbage
collection.

On the other hand, even for 'eq?' weak-key tables, there's another way
to retrieve entries without the key: the table iterators 'hash-fold' et
al.  I guess this introduces the same race for _any_ kind of hash table.

      Mark

bug#10836: guardians and weak references

[Andy Wingo]

Hi Mark,

Thanks for your thoughts :-)

On Wed 29 Feb 2012 02:22, Mark H Weaver <mhw@netris.org> writes:

> Is there a need for weak-key tables that use something other than 'eq?'
> as the predicate?

There are two examples in Guile.  One is (ice-9 poe), and the other is
the symbol table.

> It's not clear to me that any other predicate makes
> sense for a weak-key table.

It wasn't clear to me either, but given those two examples, it makes me
hesitant to remove that functionality.

> On the other hand, even for 'eq?' weak-key tables, there's another way
> to retrieve entries without the key: the table iterators 'hash-fold' et
> al.  I guess this introduces the same race for _any_ kind of hash table.

Yes.  I am wondering whether or not to expose this choice to the user --
they could choose to have the associations present after finalization
(i.e., after a guardian has resurrected an object), or they could choose
to see updates atomically (avoiding this race).  There is a relevant
thread on the libgc list:

  http://thread.gmane.org/gmane.comp.programming.garbage-collection.boehmgc/4787/focus=4793

Regards,

Andy
-- 
http://wingolog.org/

bug#10836: guardians and weak references

[Ludovic Courtès]

Hi!

Andy Wingo <wingo@pobox.com> skribis:

> However, using finalizers has the downside that it introduces races with
> custom hash/equality predicates.

This sounds similar to <http://savannah.gnu.org/bugs/?29616>.

Back then, e9bac3be613f549b932d58913307ae18c89b9ffe fixed it by calling
the custom ‘assoc’ with the allocation lock released (this was with
disappearing links, not finalizers.)

Ludo’.