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 inn GUILE rational handling

[Bill Schottstaedt]

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

I think it was intended that equal? would use scm_i_fraction_equalp
which reduces both arguments before checking equality.  So the
simplest fix would be to mask off the reduced bit in the cell type
in the check for cell type equality in scm_equalp.  I would hesitate
to remove support for this bit because it will mean you get gcd
on every integer divide!  The current system already slows Guile
down by about 10%.   On the race condition, my vage recollection
is that the "is this safe?" question was mine, and I hoped at that
time that someone who knew about such things would check it
out -- I believe (it's been a long time since I looked at this stuff)
that if that line is not safe, there are a lot more like it scattered
around Guile, so it's scarcely reason to jettison the entire thing.



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

Re: Serious bug inn GUILE rational handling

[Han-Wen Nienhuys]

Bill Schottstaedt escreveu:
>> I have removed support for the reduced bit, and put the reduction in
>> make_fraction.
> 
> I think it was intended that equal? would use scm_i_fraction_equalp
> which reduces both arguments before checking equality.  So the
> simplest fix would be to mask off the reduced bit in the cell type
> in the check for cell type equality in scm_equalp.  I would hesitate
> to remove support for this bit because it will mean you get gcd
> on every integer divide!  The current system already slows Guile

I think thes best quick fix would be to put the bit into the 4th 
double cell word. 

> down by about 10%.   On the race condition, my vage recollection
> is that the "is this safe?" question was mine, and I hoped at that
> time that someone who knew about such things would check it
> out -- I believe (it's been a long time since I looked at this stuff)
> that if that line is not safe, there are a lot more like it scattered
> around Guile, so it's scarcely reason to jettison the entire thing.

In that case, we need to fix the more-like-it stuff.  Can you point out 
some of those cases? 

I'm hesitant to put stuff like this in because 

1. it _is_ a race condition

2. if it is triggered, it will be next to impossible to reproduce. In
effect this would lead to a once in a million inexplicable corruption.
And that's really bad.

The correct solution would be a to use a lock-free instruction to 
swap the old and reduced forms, but I'm not sure if we have those in 
GUILE.

As I explained earlier, the logic for doing reduces or not needs to be
more refined. Any program that does serious arithmetic in fractions 
will likely have exploding memory requirements.

-- 
 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 inn GUILE rational handling

[Han-Wen Nienhuys]

Han-Wen Nienhuys escreveu:
> Bill Schottstaedt escreveu:
>>> I have removed support for the reduced bit, and put the reduction in
>>> make_fraction.
>> I think it was intended that equal? would use scm_i_fraction_equalp
>> which reduces both arguments before checking equality.  So the
>> simplest fix would be to mask off the reduced bit in the cell type
>> in the check for cell type equality in scm_equalp.  I would hesitate
>> to remove support for this bit because it will mean you get gcd
>> on every integer divide!  The current system already slows Guile
> 
> I think thes best quick fix would be to put the bit into the 4th 
> double cell word. 

if the performance regression is serious, then we should do 
this for guile-1.8. 

where is the benchmark to measure this? 

>> down by about 10%.   On the race condition, my vage recollection
>> is that the "is this safe?" question was mine, and I hoped at that
>> time that someone who knew about such things would check it
>> out -- I believe (it's been a long time since I looked at this stuff)
>> that if that line is not safe, there are a lot more like it scattered
>> around Guile, so it's scarcely reason to jettison the entire thing.
> 
> In that case, we need to fix the more-like-it stuff.  Can you point out 
> some of those cases? 
> 
> I'm hesitant to put stuff like this in because 
> 
> 1. it _is_ a race condition

Note that this thing is also racing with any of the arithmetic instructions,
Suppose the reduce happens between
getting SCM_FRACTION_DENOMINATOR and SCM_FRACTION_NUMERATOR in scm_sum ?

Correct macros would extract both num and den atomically 
into temporary values.

> 2. if it is triggered, it will be next to impossible to reproduce. In
> effect this would lead to a once in a million inexplicable corruption.
> And that's really bad.
> 
> The correct solution would be a to use a lock-free instruction to 
> swap the old and reduced forms, but I'm not sure if we have those in 
> GUILE.

We seem to have something like it (FETCH_STORE) but no 
compare-exchange.

Glib's gatomic.c does have an enormous bunch of cmp & exch operations
in assembler for various platforms. 

Would it be an option to link GUILE to glib? 


-- 
 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 inn GUILE rational handling

[Rob Browning]

Han-Wen Nienhuys <hanwen@xs4all.nl> writes:

> We seem to have something like it (FETCH_STORE) but no
> compare-exchange.
>
> Glib's gatomic.c does have an enormous bunch of cmp & exch
> operations in assembler for various platforms.
>
> Would it be an option to link GUILE to glib?

Without having looked carefuly at what might be involved, if we do
decide that we might want atomic operations of some kind, then I think
I'd want to investigate how hard it might be to add the operations
directly to guile.

-- 
Rob Browning
rlb @defaultvalue.org and @debian.org; previously @cs.utexas.edu
GPG starting 2002-11-03 = 14DD 432F AE39 534D B592  F9A0 25C8 D377 8C7E 73A4


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

Re: Serious bug inn GUILE rational handling

[Kevin Ryde]

"Bill Schottstaedt" <bil@ccrma.Stanford.EDU> writes:
>
> On the race condition, my vage recollection
> is that the "is this safe?" question was mine,

Sorry if I tried to claim it when it was yours.  :-)

Han-Wen Nienhuys <hanwen@xs4all.nl> writes:
>
> In that case, we need to fix the more-like-it stuff.  Can you point out 
> some of those cases? 

I don't have any on my crib list, FWIW.  I remember symbol interning
looked worrying, unless that already got some attention.

> Correct macros would extract both num and den atomically 
> into temporary values.

2-word atomic read/write might be possible on i386 with the mmx or
floating point instructions, though a bit painful to setup.  Elsewhere
you could be in the realm of mutexes :(.

> Would it be an option to link GUILE to glib? 

That's the start of a slippery slope.  First it's "oh, lets use a bit
of glib", then it's "oh, gtk does nice menus", then it's "lets get the
gnome widgets", then before you know it your program won't even run
outside 100Mb of gnome desktop!  :-)


_______________________________________________
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 inn GUILE rational handling

[Neil Jerram]

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

> in the check for cell type equality in scm_equalp.  I would hesitate
> to remove support for this bit because it will mean you get gcd
> on every integer divide!  The current system already slows Guile
> down by about 10%. 

Just to check: by "the current system" do you mean CVS after Han-Wen's
fix?

It would be good if you could post benchmark code for this.  It may be
that looking at that code would suggest a way of improving the fix.

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

[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