Undefined behavior in conv-integer.i.c?

Undefined behavior in conv-integer.i.c?

[Miroslav Lichvar]

Hi,

I was looking at a problem with guile-1.8.8 when compiled with
gcc-6.0. Two of the tests from the test suite were failing with
strange "out of range" errors [1]. After some investigation I think
the bug is that the code in libguile/conv-integer.i.c relies on
overflow of signed integers in the following code (starting on line
77), specifically -TYPE_MIN being less than zero. Adding -fwrapv to
CFLAGS worked as a workaround for me.

          if (mpz_sgn (SCM_I_BIG_MPZ (val)) >= 0)
            {
              if (n < 0)
                goto out_of_range;
            }
          else
            {
              n = -n;
              if (n >= 0)
                goto out_of_range;
            }

Looking at the current guile code, conv-integer.i.c is identical to
what it was in 1.8.8, but interestingly the tests didn't fail for me.
Maybe something else is preventing gcc from using the optimization?

I'm not sure what would be the best way to fix it. Maybe n should
really be unsigned and compared to the maximum values, but what would
be the absolute value of TYPE_MIN if it should work also with other
integer representations than two's complement?

[1] https://bugzilla.redhat.com/attachment.cgi?id=1124252

-- 
Miroslav Lichvar

Re: Undefined behavior in conv-integer.i.c?

[Mark H Weaver]

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

Hi,

Miroslav Lichvar <mlichvar@redhat.com> writes:

> I was looking at a problem with guile-1.8.8 when compiled with
> gcc-6.0. Two of the tests from the test suite were failing with
> strange "out of range" errors [1]. After some investigation I think
> the bug is that the code in libguile/conv-integer.i.c relies on
> overflow of signed integers in the following code (starting on line
> 77), specifically -TYPE_MIN being less than zero. Adding -fwrapv to
> CFLAGS worked as a workaround for me.
>
>           if (mpz_sgn (SCM_I_BIG_MPZ (val)) >= 0)
>             {
>               if (n < 0)
>                 goto out_of_range;
>             }
>           else
>             {
>               n = -n;
>               if (n >= 0)
>                 goto out_of_range;
>             }

Thanks for bringing this to our attention.  I've attached a preliminary
patch to address these issues on the 'stable-2.0' branch.

> Looking at the current guile code, conv-integer.i.c is identical to
> what it was in 1.8.8, but interestingly the tests didn't fail for me.
> Maybe something else is preventing gcc from using the optimization?

The build system of recent Guile 2.0.x automatically adds -fwrapv to
CFLAGS where supported.  However, I hope to remove -fwrapv in the
future, when we gain confidence that no code in Guile depends on it.

> I'm not sure what would be the best way to fix it. Maybe n should
> really be unsigned and compared to the maximum values, but what would
> be the absolute value of TYPE_MIN if it should work also with other
> integer representations than two's complement?

My approach was to compare (abs_n - 1) to -(TYPE_MIN + 1) in the case
where n is negative.

    Thanks,
      Mark



[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: [PATCH] Avoid signed integer overflow in numeric conversions --]
[-- Type: text/x-patch, Size: 2735 bytes --]

From be75e1713caa7b66aedc837a226091f78dfcb8fe Mon Sep 17 00:00:00 2001
From: Mark H Weaver <mhw@netris.org>
Date: Wed, 24 Feb 2016 02:17:43 -0500
Subject: [PATCH] Avoid signed integer overflows in numeric conversions.

* libguile/conv-integer.i.c: Avoid signed overflow.
* libguile/numbers.c (scm_is_signed_integer): Avoid signed overflow.
---
 libguile/conv-integer.i.c | 15 ++++++++++-----
 libguile/numbers.c        | 15 ++++++++++-----
 2 files changed, 20 insertions(+), 10 deletions(-)

diff --git a/libguile/conv-integer.i.c b/libguile/conv-integer.i.c
index 4cf887c..fe2d363 100644
--- a/libguile/conv-integer.i.c
+++ b/libguile/conv-integer.i.c
@@ -64,25 +64,30 @@ SCM_TO_TYPE_PROTO (SCM val)
 	}
       else
 	{
-	  scm_t_intmax n;
+	  scm_t_uintmax abs_n;
+	  TYPE n;
 	  size_t count;
 
 	  if (mpz_sizeinbase (SCM_I_BIG_MPZ (val), 2)
 	      > CHAR_BIT*sizeof (scm_t_uintmax))
 	    goto out_of_range;
 	  
-	  mpz_export (&n, &count, 1, sizeof (scm_t_uintmax), 0, 0,
+	  mpz_export (&abs_n, &count, 1, sizeof (scm_t_uintmax), 0, 0,
 		      SCM_I_BIG_MPZ (val));
 
 	  if (mpz_sgn (SCM_I_BIG_MPZ (val)) >= 0)
 	    {
-	      if (n < 0)
+	      if (abs_n <= TYPE_MAX)
+		n = abs_n;
+	      else
 		goto out_of_range;
 	    }
 	  else
 	    {
-	      n = -n;
-	      if (n >= 0)
+	      /* Carefully avoid signed integer overflow. */
+	      if (TYPE_MIN < 0 && abs_n - 1 <= -(TYPE_MIN + 1))
+		n = -1 - (TYPE)(abs_n - 1);
+	      else
 		goto out_of_range;
 	    }
 
diff --git a/libguile/numbers.c b/libguile/numbers.c
index 1e3fc30..5aaac64 100644
--- a/libguile/numbers.c
+++ b/libguile/numbers.c
@@ -1,4 +1,4 @@
-/* Copyright (C) 1995-2015 Free Software Foundation, Inc.
+/* Copyright (C) 1995-2016 Free Software Foundation, Inc.
  *
  * Portions Copyright 1990, 1991, 1992, 1993 by AT&T Bell Laboratories
  * and Bellcore.  See scm_divide.
@@ -9622,6 +9622,7 @@ scm_is_signed_integer (SCM val, scm_t_intmax min, scm_t_intmax max)
 	}
       else
 	{
+	  scm_t_uintmax abs_n;
 	  scm_t_intmax n;
 	  size_t count;
 
@@ -9629,18 +9630,22 @@ scm_is_signed_integer (SCM val, scm_t_intmax min, scm_t_intmax max)
 	      > CHAR_BIT*sizeof (scm_t_uintmax))
 	    return 0;
 	  
-	  mpz_export (&n, &count, 1, sizeof (scm_t_uintmax), 0, 0,
+	  mpz_export (&abs_n, &count, 1, sizeof (scm_t_uintmax), 0, 0,
 		      SCM_I_BIG_MPZ (val));
 
 	  if (mpz_sgn (SCM_I_BIG_MPZ (val)) >= 0)
 	    {
-	      if (n < 0)
+	      if (abs_n <= max)
+		n = abs_n;
+	      else
 		return 0;
 	    }
 	  else
 	    {
-	      n = -n;
-	      if (n >= 0)
+	      /* Carefully avoid signed integer overflow. */
+	      if (min < 0 && abs_n - 1 <= -(min + 1))
+		n = -1 - (scm_t_intmax)(abs_n - 1);
+	      else
 		return 0;
 	    }
 
-- 
2.6.3

Re: Undefined behavior in conv-integer.i.c?

[Mark H Weaver]

Mark H Weaver <mhw@netris.org> writes:

> Miroslav Lichvar <mlichvar@redhat.com> writes:
>
>> I was looking at a problem with guile-1.8.8 when compiled with
>> gcc-6.0. Two of the tests from the test suite were failing with
>> strange "out of range" errors [1]. After some investigation I think
>> the bug is that the code in libguile/conv-integer.i.c relies on
>> overflow of signed integers in the following code (starting on line
>> 77), specifically -TYPE_MIN being less than zero. Adding -fwrapv to
>> CFLAGS worked as a workaround for me.
>>
>>           if (mpz_sgn (SCM_I_BIG_MPZ (val)) >= 0)
>>             {
>>               if (n < 0)
>>                 goto out_of_range;
>>             }
>>           else
>>             {
>>               n = -n;
>>               if (n >= 0)
>>                 goto out_of_range;
>>             }
>
> Thanks for bringing this to our attention.  I've attached a preliminary
> patch to address these issues on the 'stable-2.0' branch.
>
>> Looking at the current guile code, conv-integer.i.c is identical to
>> what it was in 1.8.8, but interestingly the tests didn't fail for me.
>> Maybe something else is preventing gcc from using the optimization?
>
> The build system of recent Guile 2.0.x automatically adds -fwrapv to
> CFLAGS where supported.  However, I hope to remove -fwrapv in the
> future, when we gain confidence that no code in Guile depends on it.
>
>> I'm not sure what would be the best way to fix it. Maybe n should
>> really be unsigned and compared to the maximum values, but what would
>> be the absolute value of TYPE_MIN if it should work also with other
>> integer representations than two's complement?
>
> My approach was to compare (abs_n - 1) to -(TYPE_MIN + 1) in the case
> where n is negative.

I pushed these fixes as commit 4b60562820d001674ec7124c4a10391ecf7e44c3
to the stable-2.0 branch, which will become guile-2.0.12.

     Thanks,
       Mark