From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: michaelawells Newsgroups: gmane.lisp.guile.bugs Subject: GC bug in guile 2.0.1 (hashtab implementation) Date: Tue, 24 May 2011 16:25:15 -0500 Message-ID: <48057312-D657-4AFF-9199-C2ECEF18CF57@gmail.com> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 (Apple Message framework v1084) Content-Type: multipart/alternative; boundary=Apple-Mail-2--599882542 X-Trace: dough.gmane.org 1306272332 10317 80.91.229.12 (24 May 2011 21:25:32 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Tue, 24 May 2011 21:25:32 +0000 (UTC) To: bug-guile@gnu.org, Andy Wingo Original-X-From: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Tue May 24 23:25:28 2011 Return-path: Envelope-to: guile-bugs@m.gmane.org Original-Received: from lists.gnu.org ([140.186.70.17]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1QOz6U-0003tp-GL for guile-bugs@m.gmane.org; Tue, 24 May 2011 23:25:26 +0200 Original-Received: from localhost ([::1]:36531 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QOz6U-0002K5-1q for guile-bugs@m.gmane.org; Tue, 24 May 2011 17:25:26 -0400 Original-Received: from eggs.gnu.org ([140.186.70.92]:56186) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QOz6Q-0002Jv-SI for bug-guile@gnu.org; Tue, 24 May 2011 17:25:24 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1QOz6P-0000KG-NN for bug-guile@gnu.org; Tue, 24 May 2011 17:25:22 -0400 Original-Received: from mail-iw0-f169.google.com ([209.85.214.169]:60794) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QOz6P-0000K0-B2 for bug-guile@gnu.org; Tue, 24 May 2011 17:25:21 -0400 Original-Received: by iwg8 with SMTP id 8so7828502iwg.0 for ; Tue, 24 May 2011 14:25:20 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:from:content-type:subject:date:message-id:to :mime-version:x-mailer; bh=avLR74E1Pj2gq/9/YLOwyWTvXSKRwjh1cIMN6BjsG64=; b=O8+H+HhXEA8KfN82W8ELXZCsV8tVVCckVrHC/WdO7N1b9zHsTqmiJSiXk3n7tfIaNk e7XzqnYuyTZZ6kGIDofbYbOVHOdieLpi83aRYRwS/OW/Sz2ZOVbmdFwTKMU+Eoyk1suf w/U8Gpg3+QcL77kEB6dyapSohRpwv4T8wEJeU= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=from:content-type:subject:date:message-id:to:mime-version:x-mailer; b=Q9Xezjs1Wqg2NYbcf0kESHvoLLadsDPrYzuMO+epSbxnS+2J5IjuaSqroDkyZEFTNJ ic2nJU0r/w800wufSfxm7pea3z33ZhAkmH3Pjsf3OKRaxtXlI2w/uJds/Yg2pSicqIaz 8MCX/Am4XaFnF7JCcvEt5PyjNpShZ8QXENrpA= Original-Received: by 10.42.133.8 with SMTP id f8mr12378006ict.176.1306272319970; Tue, 24 May 2011 14:25:19 -0700 (PDT) Original-Received: from [192.168.2.102] (adsl-99-11-51-29.dsl.chcgil.sbcglobal.net [99.11.51.29]) by mx.google.com with ESMTPS id w5sm16669icv.8.2011.05.24.14.25.16 (version=TLSv1/SSLv3 cipher=OTHER); Tue, 24 May 2011 14:25:17 -0700 (PDT) X-Mailer: Apple Mail (2.1084) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 2) X-Received-From: 209.85.214.169 X-BeenThere: bug-guile@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Bug reports for GUILE, GNU's Ubiquitous Extension Language" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Original-Sender: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.bugs:5616 Archived-At: --Apple-Mail-2--599882542 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=us-ascii =09 I've isolated a bug in the implementation of "scm_internal_hash_fold" in = Guile 2.0.1, which causes an assertion failure in = "vacuum_weak_hash_table". As is frequently the case with GC issues, the bug is intermittent and = difficult to reproduce. "scm_internal_hash_fold" is not widely used, so = this problem may not occur for many users. (Calling the scheme function = "flush-all-ports" does result in the execution of = "scm_internal_hash_fold".) In addition to iterating through a hash table, the code in = "scm_internal_hash_fold" also attempts to remove deletable weak entries = from weak hash tables. In some cases, this function does not actually delete the entry from the = hash table, but it does decrement the size of the hash table. When = "vacuum_weak_hash_table" is called again on the same hash table, it = actually deletes the deletable entries, and decrements the size of the = hash table. When the number of deleted entries exceeds the number of = entries in the hash table, the assertion fails. Offending code from "scm_internal_hash_fold": > for (prev =3D SCM_BOOL_F, ls =3D SCM_SIMPLE_VECTOR_REF (buckets, i); > !scm_is_null (ls); > prev =3D ls, ls =3D SCM_CDR (ls)) > { > SCM handle; >=20 > if (!scm_is_pair (ls)) > SCM_WRONG_TYPE_ARG (SCM_ARG3, buckets); >=20 > handle =3D SCM_CAR (ls); > if (!scm_is_pair (handle)) > SCM_WRONG_TYPE_ARG (SCM_ARG3, buckets); >=20 > if (SCM_HASHTABLE_WEAK_P (table)) > { > if (SCM_WEAK_PAIR_DELETED_P (handle)) > { > /* We hit a weak pair whose car/cdr has become > unreachable: unlink it from the bucket. */ > if (prev !=3D SCM_BOOL_F) > SCM_SETCDR (prev, SCM_CDR (ls)); /* LINE A */ > else > SCM_SIMPLE_VECTOR_SET (buckets, i, SCM_CDR (ls)); = /* LINE B */ >=20 > /* Update the item count. */ > SCM_HASHTABLE_DECREMENT (table); >=20 > continue; > } > } If the first entry in a bucket is deletable, LINE B is executed. If the = next item in the bucket is also deletable, LINE A is executed. In this = case, LINE A does not remove the deletable item from the bucket, which = causes the failure. One solution to this problem is to remove the code which "fixes" weak = hash tables from "scm_internal_hash_fold". "vacuum_weak_hash_table" = will eventually "fix" the table. I hope I've provided enough information. Please let me know I further = clarification is needed. Thanks, Michael Wells =20 =20= --Apple-Mail-2--599882542 Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=us-ascii =
I've isolated a bug in the implementation of = "scm_internal_hash_fold" in Guile 2.0.1, which causes an assertion = failure in "vacuum_weak_hash_table".

As is = frequently the case with GC issues, the bug is intermittent and = difficult to reproduce.  "scm_internal_hash_fold" is not widely = used, so this problem may not occur for many users.  (Calling the = scheme function "flush-all-ports" does result in the execution of = "scm_internal_hash_fold".)

In addition to = iterating through a hash table, the code in "scm_internal_hash_fold" = also attempts to remove deletable weak entries from weak hash = tables.

In some cases, this function does not = actually delete the entry from the hash table, but it does decrement the = size of the hash table.  When "vacuum_weak_hash_table" is called = again on the same hash table, it actually deletes the deletable entries, = and decrements the size of the hash table.  When the number of = deleted entries exceeds the number of entries in the hash table, the = assertion fails.

Offending code = from "scm_internal_hash_fold":
for = (prev =3D SCM_BOOL_F, ls =3D SCM_SIMPLE_VECTOR_REF (buckets, = i);
  !scm_is_null (ls);
  prev =3D ls, ls =3D = SCM_CDR (ls))
{
 SCM handle;

 if (!scm_is_pair = (ls))
   SCM_WRONG_TYPE_ARG (SCM_ARG3, = buckets);

 handle =3D SCM_CAR (ls);
 if (!scm_is_pair = (handle))
   SCM_WRONG_TYPE_ARG (SCM_ARG3, = buckets);

 if (SCM_HASHTABLE_WEAK_P = (table))
   {
     if = (SCM_WEAK_PAIR_DELETED_P (handle))
= {
 /* We hit a weak = pair whose car/cdr has become
=   =   unreachable: unlink it from the bucket. =  */
 if (prev !=3D = SCM_BOOL_F)
   SCM_SETCDR = (prev, SCM_CDR (ls));  /* LINE A */
= =  else
  =  SCM_SIMPLE_VECTOR_SET (buckets, i, SCM_CDR (ls));  /* LINE B = */

               =    /* Update the item count.  */
       =            SCM_HASHTABLE_DECREMENT = (table);

=  continue;
}
  =  }

If the first entry in a = bucket is deletable, LINE B is executed.  If the next item in the = bucket is also deletable, LINE A is executed.  In this case, LINE A = does not remove the deletable item from the bucket, which causes the = failure.

One solution to this problem is to = remove the code which "fixes" weak hash tables from = "scm_internal_hash_fold".  "vacuum_weak_hash_table" will eventually = "fix" the table.

I hope I've provided enough = information.  Please let me know I further clarification is = needed.

Thanks,
Michael = Wells



 
<= div>
=   
= --Apple-Mail-2--599882542--