GC bug in guile 2.0.1 (hashtab implementation)

GC bug in guile 2.0.1 (hashtab implementation)

[michaelawells]

[-- Attachment #1: Type: text/plain, Size: 2493 bytes --]

	
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 = SCM_BOOL_F, ls = SCM_SIMPLE_VECTOR_REF (buckets, i);
> 	   !scm_is_null (ls);
> 	   prev = ls, ls = SCM_CDR (ls))
> 	{
> 	  SCM handle;
> 
> 	  if (!scm_is_pair (ls))
> 	    SCM_WRONG_TYPE_ARG (SCM_ARG3, buckets);
> 
> 	  handle = 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 != 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



 
	  

[-- Attachment #2: Type: text/html, Size: 7737 bytes --]

Re: GC bug in guile 2.0.1 (hashtab implementation)

[Andy Wingo]

On Tue 24 May 2011 23:25, michaelawells <michaelawells@gmail.com> writes:

> 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".

Thanks very much for this detailed report.  I have now pushed a fix,
along the lines that you suggested.  Cheers!

Andy
-- 
http://wingolog.org/