bug#7928: mktime test in configure: UB resulting in infinite loop

[Rich Felker]

The configure test for mktime (m4/mktime.m4) contains the following
code:

  for (;;)
{
  t = (time_t_max << 1) + 1;
  if (t <= time_t_max)
break;
  time_t_max = t;
}

This code has undefined behavior on signed integer overflow; at least
some versions of gcc, and any sane compiler, will optimize out the
exit condition since algebraically 2x+1>x for any nonnegative x. The
result is an infinite loop and failure of the test after the 60-second
timeout.

Finding the max possible value for a signed integer type is actually a
very hard problem in C. As far as I know it's impossible at
compile-time and might even be impossible at runtime unless you make
some assumptions (either the absence of padding bits, or the
well-definedness of converting larger/unsigned types to signed types).
The approach I would take is just:

  time_t_max = (time_t)1 << 8*sizeof(time_t)-2;

If this test comes from higher-up (gnulib?) please forward my bug
report to the relevant upstream.

bug#7928: mktime test in configure: UB resulting in infinite loop

[Eric Blake]

[adding bug-gnulib, as requested]

On 01/26/2011 10:21 PM, Rich Felker wrote:
> The configure test for mktime (m4/mktime.m4) contains the following
> code:
> 
>   for (;;)
> {
>   t = (time_t_max << 1) + 1;
>   if (t <= time_t_max)
> break;
>   time_t_max = t;
> }
> 
> This code has undefined behavior on signed integer overflow; at least
> some versions of gcc, and any sane compiler, will optimize out the
> exit condition since algebraically 2x+1>x for any nonnegative x. The
> result is an infinite loop and failure of the test after the 60-second
> timeout.

Thanks for the report.

> Finding the max possible value for a signed integer type is actually a
> very hard problem in C. As far as I know it's impossible at
> compile-time and might even be impossible at runtime unless you make
> some assumptions (either the absence of padding bits, or the
> well-definedness of converting larger/unsigned types to signed types).

Agreed that padding bits make it impossible - but in reality, how many
porting targets have such a signed type?  Here's what we do in gnulib's
"intprops.h" for a compile-time designation that's accurate for every
integer type on every platform that gnulib targets:

/* True if negative values of the signed integer type T use two's
   complement, ones' complement, or signed magnitude representation,
   respectively.  Much GNU code assumes two's complement, but some
   people like to be portable to all possible C hosts.  */
# define TYPE_TWOS_COMPLEMENT(t) ((t) ~ (t) 0 == (t) -1)
# define TYPE_ONES_COMPLEMENT(t) ((t) ~ (t) 0 == 0)
# define TYPE_SIGNED_MAGNITUDE(t) ((t) ~ (t) 0 < (t) -1)

/* True if the arithmetic type T is signed.  */
# define TYPE_SIGNED(t) (! ((t) 0 < (t) -1))

/* The maximum and minimum values for the integer type T.  These
   macros have undefined behavior if T is signed and has padding bits.
   If this is a problem for you, please let us know how to fix it for
   your host.  */
# define TYPE_MINIMUM(t) \
  ((t) (! TYPE_SIGNED (t) \
? (t) 0 \
: TYPE_SIGNED_MAGNITUDE (t) \
? ~ (t) 0 \
: ~ (t) 0 << (sizeof (t) * CHAR_BIT - 1)))
# define TYPE_MAXIMUM(t) \
  ((t) (! TYPE_SIGNED (t) \
? (t) -1 \
: ~ (~ (t) 0 << (sizeof (t) * CHAR_BIT - 1

and no one has complained yet, so we might as well just use this same
logic in m4/mktime.m4.

> The approach I would take is just:
> 
>   time_t_max = (time_t)1 << 8*sizeof(time_t)-2;

8 is a magic number; it would be better to use CHAR_BIT, as was done in
intprops.h.

> If this test comes from higher-up (gnulib?) please forward my bug
> report to the relevant upstream.

Forwarded; and the patch should be applied shortly.

-- 
Eric Blake   ebl...@redhat.com+1-801-349-2682
Libvirt virtualization library http://libvirt.org



signature.asc
Description: OpenPGP digital signature

bug#7928: mktime test in configure: UB resulting in infinite loop

[Rich Felker]

On Thu, Jan 27, 2011 at 08:14:56AM -0700, Eric Blake wrote:
> # define TYPE_MINIMUM(t) \
>   ((t) (! TYPE_SIGNED (t) \
> ? (t) 0 \
> : TYPE_SIGNED_MAGNITUDE (t) \
> ? ~ (t) 0 \
> : ~ (t) 0 << (sizeof (t) * CHAR_BIT - 1)))
> # define TYPE_MAXIMUM(t) \
>   ((t) (! TYPE_SIGNED (t) \
> ? (t) -1 \
> : ~ (~ (t) 0 << (sizeof (t) * CHAR_BIT - 1

The last line of this macro has UB due to signed integer overflow in
the << operation. Replace it with

(( (t)1 << CHAR_BIT*sizeof(time_t)-2 ) - 1) * 2 + 1

Which for a 32-bit type would expand as:

(0x4000 - 1) * 2 + 1
0x3fff *2 + 1
0x7ffe + 1
0x7fff

With no overflows.

> and no one has complained yet, so we might as well just use this same
> logic in m4/mktime.m4.

Well apparently no one complained about the overflow in coreutils
either. Perhaps later gcc versions are more forgiving; I found it
building on a system where I have to use gcc 3.2.3, which, being one
of the earlier versions to utilize the UB of signed overflow, might be
less diplomatic about it. Anyway to avoid future trouble, I would
strive to remove all signed overflow UB from the tests even if it
doesn't presently hurt anyone.

> 8 is a magic number; it would be better to use CHAR_BIT, as was done in
> intprops.h.

As you wish. This code (coreutils) is sufficiently POSIX-like-system
dependent that I thought using POSIX's requirement CHAR_BIT==8 was
reasonable.

> > If this test comes from higher-up (gnulib?) please forward my bug
> > report to the relevant upstream.
> 
> Forwarded; and the patch should be applied shortly.

Thanks!

Rich

bug#7928: mktime test in configure: UB resulting in infinite loop

[Eric Blake]

On 01/27/2011 10:57 AM, Paul Eggert wrote:
 # define TYPE_MAXIMUM(t) \
   ((t) (! TYPE_SIGNED (t) \
 ? (t) -1 \
 : ~ (~ (t) 0 << (sizeof (t) * CHAR_BIT - 1
>> The last line of this macro has UB due to signed integer overflow in
>> the << operation.
> 
> No it doesn't.  ~ (t) 0 evaluates to -1, and -1 << 31 does not
> overflow.

C99 states this (6.5.7 paragraph 4)

The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits
are filled with  zeros. If E1 has an unsigned type, the value of the
result is E1 × 2^E2 , reduced modulo one more than the maximum value
representable in the result type. If E1 has a signed type and
nonnegative value, and E1 × 2^E2 is representable in the result type,
then that is the resulting value; otherwise, the behavior is undefined.

In other words, the problem is not about overflow, but about undefined
behavior.

-- 
Eric Blake   ebl...@redhat.com+1-801-349-2682
Libvirt virtualization library http://libvirt.org



signature.asc
Description: OpenPGP digital signature

bug#7928: mktime test in configure: UB resulting in infinite loop

[Paul Eggert]

On 01/27/11 09:28, Rich Felker wrote:
> On Thu, Jan 27, 2011 at 08:14:56AM -0700, Eric Blake wrote:
>> > # define TYPE_MINIMUM(t) \
>> >   ((t) (! TYPE_SIGNED (t) \
>> > ? (t) 0 \
>> > : TYPE_SIGNED_MAGNITUDE (t) \
>> > ? ~ (t) 0 \
>> > : ~ (t) 0 << (sizeof (t) * CHAR_BIT - 1)))
>> > # define TYPE_MAXIMUM(t) \
>> >   ((t) (! TYPE_SIGNED (t) \
>> > ? (t) -1 \
>> > : ~ (~ (t) 0 << (sizeof (t) * CHAR_BIT - 1
> The last line of this macro has UB due to signed integer overflow in
> the << operation.

No it doesn't.  ~ (t) 0 evaluates to -1, and -1 << 31 does not
overflow.

bug#7928: mktime test in configure: UB resulting in infinite loop

[Bruno Haible]

Rich Felker wrote:
> > # define TYPE_MAXIMUM(t) \
> >   ((t) (! TYPE_SIGNED (t) \
> > ? (t) -1 \
> > : ~ (~ (t) 0 << (sizeof (t) * CHAR_BIT - 1
> 
> The last line of this macro has UB due to signed integer overflow in
> the << operation.

No there is no overflow here. The ~ operator has higher syntactic precedence
than the << operator, therefore the expression in the last line consists of
4 steps:
  1. Take a zero.
  2. Invert all bits.
  3. Shift left by n-1 bits.
  4. Invert all bits.

Taking  as
reference, in all three cases (two's complement, one's complement, signed
magnitude) the results are:
  - after step 1: 000...00
  - after step 2: 111...11
  - after step 3: 100...00 (and no overflow here, in two's complement)
  - after step 4: 011...11

ISO C 99 says about the << operator:
  "The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated
   bits are filled with zeros. If E1 has an unsigned type, the value of
   the result is E1 × 2^E2 , reduced modulo one more than the maximum
   value representable in the result type. If E1 has a signed type and
   nonnegative value, and E1 × 2^E2 is representable in the result type,
   then that is the resulting value; otherwise, the behavior is undefined."

If you take the first sentence as a mandatory description of what <<
does, then ~ (~ (t) 0 << (sizeof (t) * CHAR_BIT - 1)) is the bit pattern
011...11 on all systems and with all compilers.

If you take the last sentence as more relevant than the first one, then
any shift of any negative value is undefined behaviour.

Do you mean to say that GCC produces undefined behaviour for shifts of
negative values, even those where the result is negative (no overflow)?
I've never seen a sign of that.

Bruno

bug#7928: mktime test in configure: UB resulting in infinite loop

[Paul Eggert]

On 01/27/11 10:15, Eric Blake wrote:
> In other words, the problem is not about overflow, but about undefined
> behavior.

You're right that the behavior is not defined, but this should
not be a problem in practice, any more than the * CHAR_BIT business
should be a problem in practice (that also relies a not-guaranteed-
by-the-standard assumption).

Currently the code assumes that if time_t values are signed,
then they use either two's complement, ones' complement,
or signed magnitude representation internally, that left shift
shifts those bits left, and that there are no padding bits.  The
assumptions about left-shift and no padding bits are not guaranteed
by the C standard, but they are portable in practice, even when using
the latest GCC with all the optimization bells and whistles enabled.

It's unlikely that GCC will ever break expressions
like -1 << 1 merely because the C standard lets it do that.