GNU logs - #10836, boring messages

Message sent to bug-guile@HIDDEN:

Subject: bug#10836: guardians and weak references
Resent-From: Andy Wingo <wingo@HIDDEN>
Original-Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Resent-CC: bug-guile@HIDDEN
Resent-Date: Fri, 17 Feb 2012 14:55:02 +0000
Resent-Message-ID: <handler.10836.B.132949046822964 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
To: 10836 <at> debbugs.gnu.org
DomainKey-Signature: a=rsa-sha1; c=nofws; d=pobox.com; h=from:to:subject
	:date:message-id:mime-version:content-type; q=dns; s=sasl; b=aya
	EoqS2YB5TptUeMWBPG1lpcKib+n+YnKH72y91PwNmzljOIdZkBi/GedgR7qoqddW
	Map6G/m/Ej4u/JStEn6J7kx+WPuV9woukxgpHs1e36FuTWyZhe/S0Q39SJF6cser
	G/zW49ujHO1wJ4btIYHLrOWIDRKIlWs6hTVo1m+s=
From: Andy Wingo <wingo@HIDDEN>
Date: Fri, 17 Feb 2012 15:52:02 +0100
Message-ID: <87ipj5o6lp.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.3 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Precedence: list
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org

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/

Message sent:

Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-Mailer: MIME-tools 5.428 (Entity 5.428)
Content-Type: text/plain; charset=utf-8
X-Loop: help-debbugs@HIDDEN
From: help-debbugs@HIDDEN (GNU bug Tracking System)
To: Andy Wingo <wingo@HIDDEN>
Subject: bug#10836: Acknowledgement (guardians and weak references)
Message-ID: <handler.10836.B.132949046822964.ack <at> debbugs.gnu.org>
References: <87ipj5o6lp.fsf@HIDDEN>
X-Gnu-PR-Message: ack 10836
X-Gnu-PR-Package: guile
Reply-To: 10836 <at> debbugs.gnu.org
Date: Fri, 17 Feb 2012 14:55:03 +0000

Thank you for filing a new bug report with debbugs.gnu.org.

This is an automatically generated reply to let you know your message
has been received.

Your message is being forwarded to the package maintainers and other
interested parties for their attention; they will reply in due course.

Your message has been sent to the package maintainer(s):
 bug-guile@HIDDEN

If you wish to submit further information on this problem, please
send it to 10836 <at> debbugs.gnu.org.

Please do not send mail to help-debbugs@HIDDEN unless you wish
to report a problem with the Bug-tracking system.

--=20
10836: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D10836
GNU Bug Tracking System
Contact help-debbugs@HIDDEN with problems

Message sent to bug-guile@HIDDEN:

Subject: bug#10836: guardians and weak references
Resent-From: Andy Wingo <wingo@HIDDEN>
Original-Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Resent-CC: bug-guile@HIDDEN
Resent-Date: Sun, 19 Feb 2012 21:06:02 +0000
Resent-Message-ID: <handler.10836.B10836.132968552628189 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
To: 10836 <at> debbugs.gnu.org
DomainKey-Signature: a=rsa-sha1; c=nofws; d=pobox.com; h=from:to:subject
	:references:date:in-reply-to:message-id:mime-version
	:content-type; q=dns; s=sasl; b=k/An8VWjgrlOyUWamJqaCa6B9lM3gR8x
	Cyr2PLAFNR7nTMZZ0ehanru3TXml8GU2+Mklggl3r/XpvxFodjcitIzsDat1pGZV
	W5oyXY90AZTJ5L4afwR22CembVA9w4iSp4+FN7/oUuU7RCdeaJVGGMU+RNBdjVNW
	/fuvFFzt1vE=
From: Andy Wingo <wingo@HIDDEN>
References: <87ipj5o6lp.fsf@HIDDEN>
Date: Sun, 19 Feb 2012 22:03:11 +0100
In-Reply-To: <87ipj5o6lp.fsf@HIDDEN> (Andy Wingo's message of "Fri, 17 Feb
	2012 15:52:02 +0100")
Message-ID: <87haym1qpc.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.3 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Precedence: list
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org

On Fri 17 Feb 2012 15:52, Andy Wingo <wingo@HIDDEN> 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/

Message sent to bug-guile@HIDDEN:

Subject: bug#10836: guardians and weak references
Resent-From: Mark H Weaver <mhw@HIDDEN>
Original-Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Resent-CC: bug-guile@HIDDEN
Resent-Date: Wed, 29 Feb 2012 01:26:02 +0000
Resent-Message-ID: <handler.10836.B10836.133047870420356 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
To: Andy Wingo <wingo@HIDDEN>
Cc: 10836 <at> debbugs.gnu.org
From: Mark H Weaver <mhw@HIDDEN>
References: <87ipj5o6lp.fsf@HIDDEN> <87haym1qpc.fsf@HIDDEN>
Date: Tue, 28 Feb 2012 20:22:28 -0500
In-Reply-To: <87haym1qpc.fsf@HIDDEN> (Andy Wingo's message of "Sun, 19 Feb
	2012 22:03:11 +0100")
Message-ID: <87399u8mcr.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.0.92 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain
Precedence: list
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org

Andy Wingo <wingo@HIDDEN> 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

Message sent to bug-guile@HIDDEN:

X-Loop: help-debbugs@HIDDEN
Subject: bug#10836: guardians and weak references
Resent-From: Andy Wingo <wingo@HIDDEN>
Original-Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Resent-CC: bug-guile@HIDDEN
Resent-Date: Wed, 29 Feb 2012 09:28:01 +0000
Resent-Message-ID: <handler.10836.B10836.13305076284117 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
X-GNU-PR-Message: followup 10836
X-GNU-PR-Package: guile
X-GNU-PR-Keywords: 
To: Mark H Weaver <mhw@HIDDEN>
Cc: 10836 <at> debbugs.gnu.org
Received: via spool by 10836-submit <at> debbugs.gnu.org id=B10836.13305076284117
          (code B ref 10836); Wed, 29 Feb 2012 09:28:01 +0000
Received: (at 10836) by debbugs.gnu.org; 29 Feb 2012 09:27:08 +0000
Received: from localhost ([127.0.0.1]:55139 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1S2foM-00013k-N6
	for submit <at> debbugs.gnu.org; Wed, 29 Feb 2012 04:27:08 -0500
Received: from a-pb-sasl-sd.pobox.com ([74.115.168.62]:53642
	helo=sasl.smtp.pobox.com) by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <wingo@HIDDEN>) id 1S2fnv-000139-Cf
	for 10836 <at> debbugs.gnu.org; Wed, 29 Feb 2012 04:26:50 -0500
Received: from sasl.smtp.pobox.com (unknown [127.0.0.1])
	by a-pb-sasl-sd.pobox.com (Postfix) with ESMTP id EE78084AB;
	Wed, 29 Feb 2012 04:26:16 -0500 (EST)
DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=pobox.com; h=from:to:cc
	:subject:references:date:in-reply-to:message-id:mime-version
	:content-type; s=sasl; bh=a3o+GittMiDZ6lxEzodVgAXMuM0=; b=MylV0Y
	pqg3buJZqyRvtCT/uPAh0iE9zklZbcv9XfEvBaRhON24Aix7f2oD5fCmGg8ACQ3E
	ahdNHVPjIP2PosOgALo0x0pnQdvUVBKyBEwpbZDtECdkyhGV1s5mQXAK4RQOSfmp
	NLTz2CSmRwDTNSsjgLZzVtIjzU/YarouE6FRI=
DomainKey-Signature: a=rsa-sha1; c=nofws; d=pobox.com; h=from:to:cc
	:subject:references:date:in-reply-to:message-id:mime-version
	:content-type; q=dns; s=sasl; b=nmgqJdoztbXLKbyOc/c0SjgSR7gIXPc5
	ZpdVEb6ioB96KhS8frYFDkVXMsmj/tYjdXDGRi0G6ZSU42mQc7LmX9zIVo5+uqY5
	R/iEZdw3WHLt/p6N7nbNLOCvvmuHSVqZCjI/rjdyHWvcX/nDX7NOgp7+qan95db6
	oQ0saGVG20g=
Received: from a-pb-sasl-sd.pobox.com (unknown [127.0.0.1])
	by a-pb-sasl-sd.pobox.com (Postfix) with ESMTP id DB5AA84A1;
	Wed, 29 Feb 2012 04:26:16 -0500 (EST)
Received: from badger (unknown [85.50.113.138]) (using TLSv1 with cipher
	DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by
	a-pb-sasl-sd.pobox.com (Postfix) with ESMTPSA id 4652784A0;
	Wed, 29 Feb 2012 04:26:16 -0500 (EST)
From: Andy Wingo <wingo@HIDDEN>
References: <87ipj5o6lp.fsf@HIDDEN> <87haym1qpc.fsf@HIDDEN>
	<87399u8mcr.fsf@HIDDEN>
Date: Wed, 29 Feb 2012 10:26:12 +0100
In-Reply-To: <87399u8mcr.fsf@HIDDEN> (Mark H. Weaver's message of "Tue,
	28 Feb 2012 20:22:28 -0500")
Message-ID: <87ehtedm8b.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.3 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Pobox-Relay-ID: 6E25BA0A-62B7-11E1-8FE8-65B1DE995924-02397024!a-pb-sasl-sd.pobox.com
X-Spam-Score: -1.9 (-)
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: -1.9 (-)

Hi Mark,

Thanks for your thoughts :-)

On Wed 29 Feb 2012 02:22, Mark H Weaver <mhw@HIDDEN> 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/

Message sent to bug-guile@HIDDEN:

X-Loop: help-debbugs@HIDDEN
Subject: bug#10836: guardians and weak references
Resent-From: ludo@HIDDEN (Ludovic =?UTF-8?Q?Court=C3=A8s?=)
Original-Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Resent-CC: bug-guile@HIDDEN
Resent-Date: Thu, 12 Apr 2012 20:24:02 +0000
Resent-Message-ID: <handler.10836.B10836.133426222617510 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
X-GNU-PR-Message: followup 10836
X-GNU-PR-Package: guile
X-GNU-PR-Keywords: 
To: Andy Wingo <wingo@HIDDEN>
Cc: 10836 <at> debbugs.gnu.org
Received: via spool by 10836-submit <at> debbugs.gnu.org id=B10836.133426222617510
          (code B ref 10836); Thu, 12 Apr 2012 20:24:02 +0000
Received: (at 10836) by debbugs.gnu.org; 12 Apr 2012 20:23:46 +0000
Received: from localhost ([127.0.0.1]:54921 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1SIQYU-0004YN-69
	for submit <at> debbugs.gnu.org; Thu, 12 Apr 2012 16:23:46 -0400
Received: from xanadu.aquilenet.fr ([88.191.123.111]:39617)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <ludo@HIDDEN>) id 1SIQYS-0004YE-2W
	for 10836 <at> debbugs.gnu.org; Thu, 12 Apr 2012 16:23:44 -0400
Received: from localhost (xanadu.aquilenet.fr [127.0.0.1])
	by xanadu.aquilenet.fr (Postfix) with ESMTP id 53A0B1A64;
	Thu, 12 Apr 2012 22:22:28 +0200 (CEST)
Received: from xanadu.aquilenet.fr ([127.0.0.1])
	by localhost (xanadu.aquilenet.fr [127.0.0.1]) (amavisd-new, port 10024)
	with ESMTP id ahXHRoiUwPbn; Thu, 12 Apr 2012 22:22:28 +0200 (CEST)
Received: from pluto (reverse-83.fdn.fr [80.67.176.83])
	by xanadu.aquilenet.fr (Postfix) with ESMTPSA id B7FC91207;
	Thu, 12 Apr 2012 22:22:27 +0200 (CEST)
From: ludo@HIDDEN (Ludovic =?UTF-8?Q?Court=C3=A8s?=)
References: <87ipj5o6lp.fsf@HIDDEN> <87haym1qpc.fsf@HIDDEN>
Date: Thu, 12 Apr 2012 22:22:27 +0200
In-Reply-To: <87haym1qpc.fsf@HIDDEN> (Andy Wingo's message of "Sun, 19 Feb
	2012 22:03:11 +0100")
Message-ID: <87aa2g1z0c.fsf@HIDDEN>
User-Agent: Gnus/5.110018 (No Gnus v0.18) Emacs/24.0.93 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
X-Spam-Score: -0.7 (/)
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: -0.7 (/)

Hi!

Andy Wingo <wingo@HIDDEN> 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 =E2=80=98assoc=E2=80=99 with the allocation lock released (this =
was with
disappearing links, not finalizers.)

Ludo=E2=80=99.

Last modified: Mon, 25 Nov 2019 12:00:02 UTC

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997 nCipher Corporation Ltd, 1994-97 Ian Jackson.