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

From: Eric Blake <[email-masked]>
Date: Thu, 27 Jan 2011 08:14:56 -0700

[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   [email-masked]    +1-801-349-2682
Libvirt virtualization library http://libvirt.org