Serious bug in GUILE rational handling.

Serious bug in GUILE rational handling.

[Han-Wen Nienhuys]

Hello,

scm_equal_p inspects SCM_CELL_TYPE() of a rational. Cell type is also used
to hold the reduced bit. This leads to interesting behavior,

guile> (define x 1/2)
guile> (define y 1/2)
guile> (denominator x)
2
guile> (equal? x y)
#f
guile> 


This took a lot of effort to debug; printing the rational while
debugging would alter the reduction bit, making the problem go away,
suggesting memory corruption rather than a programming error.

Furthermore, I think

  if (!(SCM_FRACTION_REDUCED (z)))
    {
      SCM divisor;
      divisor = scm_gcd (SCM_FRACTION_NUMERATOR (z), SCM_FRACTION_DENOMINATOR (z));
      if (!(scm_is_eq (divisor, SCM_I_MAKINUM(1))))
	{
	  /* is this safe? */
	  SCM_FRACTION_SET_NUMERATOR (z, scm_divide (SCM_FRACTION_NUMERATOR (z), divisor));
	  SCM_FRACTION_SET_DENOMINATOR (z, scm_divide (SCM_FRACTION_DENOMINATOR (z), divisor));
	}
      SCM_FRACTION_REDUCED_SET (z);
    }

introduces a race condition.

Suppose another thread triggers scm_i_fraction_reduce at the same
time, and reads the partial result of the first scm_i_fraction_reduce.
This is really insidious, as the corruption would happen upon reading
the data, and will show up somewhere completely different.

I have removed support for the reduced bit, and put the reduction in
make_fraction.

I am about to commit these changes to CVS, and will also commit them
to the GUILE 1.8 branch.  I would appreciate it if a GUILE 1.8.2 would
be released ASAP.  I need working rational numbers in GUILE for
LilyPond 2.11.x, and it would be nice if I didn't have to force my
users to run GUILE from CVS.

--
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

Re: Serious bug in GUILE rational handling.

[Han-Wen Nienhuys]

Han-Wen Nienhuys escreveu:
> I am about to commit these changes to CVS, and will also commit them
> to the GUILE 1.8 branch.  I would appreciate it if a GUILE 1.8.2 would
> be released ASAP.  I need working rational numbers in GUILE for
> LilyPond 2.11.x, and it would be nice if I didn't have to force my
> users to run GUILE from CVS.

Note that something is wrong with GUILE 1.8 CVS, as running make check says. 

Running popen.test
ERROR: In procedure display:
ERROR: Wrong type argument in position 2: #<closed: file 0>
FAIL: check-guile
==================================
1 of 1 tests failed
Please report to bug-guile@gnu.org
==================================


(this is after applying my changes, but it is extremely unlikely that
I have caused popen to fall over.)

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

Re: Serious bug in GUILE rational handling.

[Kevin Ryde]

Han-Wen Nienhuys <hanwen@xs4all.nl> writes:
>
> Running popen.test
> ERROR: In procedure display:
> ERROR: Wrong type argument in position 2: #<closed: file 0>

I noticed that too, but haven't debugged it yet.  It's possible it's
only a bogosity in the test of course ... possibly introduced by me ...

> (this is after applying my changes, but it is extremely unlikely that
> I have caused popen to fall over.)

It pre-dates whatever you just changed :-).


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

Re: Serious bug in GUILE rational handling.

[Kevin Ryde]

Han-Wen Nienhuys <hanwen@xs4all.nl> writes:
>
> This took a lot of effort to debug; printing the rational while
> debugging would alter the reduction bit, making the problem go away,
> suggesting memory corruption rather than a programming error.

Nasty.

> Suppose another thread triggers scm_i_fraction_reduce at the same
> time, and reads the partial result of the first scm_i_fraction_reduce.
> This is really insidious, as the corruption would happen upon reading
> the data, and will show up somewhere completely different.

Yep.  I think I might have raised that when fractions were introduced,
then promptly never did anything about it.  My best idea at the time
was if fractions are stored unreduced then gc would be a good
thread-safe place to look for reductions to save space.

I don't know if reduced or unreduced is a better representation.  My
guess would be that gcds are so horrendously expensive that unreduced
is often what you want, if it's do-able.  Reducing lazily sounds like
the best of both worlds, but as you point out would need multithread
protection.

> I am about to commit these changes to CVS, and will also commit them
> to the GUILE 1.8 branch.

Do you have a test case for numbers.test?  Not that I doubt the fix,
just to illustrate what now works.

I took the liberty of adding a NEWS entry too.


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

Re: Serious bug in GUILE rational handling.

[Kevin Ryde]

Han-Wen Nienhuys <hanwen@xs4all.nl> writes:
>
> I need working rational numbers in GUILE for
> LilyPond 2.11.x, and it would be nice if I didn't have to force my
> users to run GUILE from CVS.

Are you able to use `eqv?' in the afflicted spots?  I think it works
ok.  Or I guess you could set! in a new equal? which called eqv?.
(Not pretty, but it might keep 1.8.1 usable.)


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

Re: Serious bug in GUILE rational handling.

[Han-Wen Nienhuys]

Kevin Ryde escreveu:
>> Suppose another thread triggers scm_i_fraction_reduce at the same
>> time, and reads the partial result of the first scm_i_fraction_reduce.
>> This is really insidious, as the corruption would happen upon reading
>> the data, and will show up somewhere completely different.
> 
> Yep.  I think I might have raised that when fractions were introduced,
> then promptly never did anything about it.  My best idea at the time
> was if fractions are stored unreduced then gc would be a good
> thread-safe place to look for reductions to save space.
> 
> I don't know if reduced or unreduced is a better representation.  My
> guess would be that gcds are so horrendously expensive that unreduced
> is often what you want, if it's do-able.  Reducing lazily sounds like
> the best of both worlds, but as you point out would need multithread
> protection.

Is there any data to back this up?  Once the numbers get beyond the
size of fixnum (and that can happen in just a couple of additions), we
have extra allocation overhead of 2 double cells per fraction (for
mpz), and from then on each addition will double the memory use.

Without reduction, doing a significant loop in fractional arithmetic
would make GUILE go trashing.  Have a look at the memory footprint of 

  (apply + (map (lambda (x)  1/10000) (iota 10000)))

At the least, a reduction should happen before trying to make a fraction 
that exceeds fixnum for numerator and/or denominator.  

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

Re: Serious bug in GUILE rational handling.

[Han-Wen Nienhuys]

Kevin Ryde escreveu:
>> I am about to commit these changes to CVS, and will also commit them
>> to the GUILE 1.8 branch.
> 
> Do you have a test case for numbers.test?  Not that I doubt the fix,
> just to illustrate what now works.

I've added one (CVS HEAD)

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

Re: Serious bug in GUILE rational handling.

[Kevin Ryde]

Han-Wen Nienhuys <hanwen@xs4all.nl> writes:
>
> I've added one (CVS HEAD)

You can put tests in the branch for bugs fixed in the branch.


Oh, and the popen.test was indeed my fault, indirectly.  I stuck in a
configure test for pipe(), because it doesn't exist on mingw, and that
unintentionally enabled this bit of scm_display, write and write_char

	  scm_prin1 (obj, port, 0);
	#ifdef HAVE_PIPE
	# ifdef EPIPE
	  if (EPIPE == errno)
	    scm_close_port (port);
	# endif
	#endif

I've commented that out in the three places.  I'm pretty sure it's not
reliable to test errno at that point.  I think popen.test had an EPIPE
left from a long previous operation for instance, and it made
scm_display close the check-guile.log file port. :(

I can't tell where those lines came from, they're there in 1.6, but
disabled on account of no HAVE_PIPE.  Shows what you get for changing
the configury I guess ...


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

Re: Serious bug in GUILE rational handling.

[Kevin Ryde]

Han-Wen Nienhuys <hanwen@xs4all.nl> writes:
>
> Is there any data to back this up?

Err, umm, I think there's sensible uses that don't need reduction.
Anything that only compares values, or that rounds to int or float
before printing say.


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

Re: Serious bug in GUILE rational handling

[Bill Schottstaedt]

I was talking about the original ratio implementation.  Much to my
surprise, I found no consistent timing difference before and after
the reduction change.  



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

Re: Serious bug in GUILE rational handling

[Neil Jerram]

"Bill Schottstaedt" <bil@ccrma.Stanford.EDU> writes:

> I was talking about the original ratio implementation.  Much to my
> surprise, I found no consistent timing difference before and after
> the reduction change.  

That's good news, then.  Thanks for making the measurements.

Regards,
     Neil



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

Re: Serious bug in GUILE rational handling.

[Carl Witty]

On Sun, 2006-12-24 at 10:21 +1100, Kevin Ryde wrote:
> I don't know if reduced or unreduced is a better representation.  My
> guess would be that gcds are so horrendously expensive that unreduced
> is often what you want, if it's do-able.  Reducing lazily sounds like
> the best of both worlds, but as you point out would need multithread
> protection.

This was discussed three years ago (my contribution to the discussion
was
http://lists.gnu.org/archive/html/guile-devel/2003-12/msg00013.html).

Carl Witty




_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel