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

From: [email-masked] (GNU bug Tracking System)
Date: Sun, 30 Jan 2011 07:57:02 +0000

Your bug report

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

which was filed against the coreutils package, has been closed.

The explanation is attached below, along with your original report.
If you require more details, please reply to [email-masked].

-- 
7928: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=7928
GNU Bug Tracking System
Contact [email-masked] with problems

Subject: Re: bug#7928: mktime test in configure: UB resulting in infinite loop
From: Paul Eggert <[email-masked]>
To: Rich Felker <[email-masked]>
Cc: [email-masked], [email-masked], Eric Blake <[email-masked]>
Date: Sun, 30 Jan 2011 00:04:50 -0800
List-Id: <debbugs-submit.debbugs.gnu.org>

On 01/27/2011 11:42 PM, Paul Eggert wrote:
> If it could be done just as clearly by other means, that would
> be OK too.

To try to do that, I installed the following:

---
 ChangeLog            |   13 +++++++++++++
 lib/intprops.h       |    4 ++--
 lib/mktime.c         |    2 +-
 lib/strtol.c         |    4 ++--
 m4/mktime.m4         |    7 ++++---
 m4/nanosleep.m4      |    4 ++--
 m4/parse-datetime.m4 |    8 +++++---
 m4/stdint.m4         |    8 +++++---
 8 files changed, 34 insertions(+), 16 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index fdaf383..ded04f7 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,18 @@
 2011-01-29  Paul Eggert  <[email-masked]>
 
+	TYPE_MAXIMUM: avoid theoretically undefined behavior
+	* lib/intprops.h (TYPE_MINIMUM, TYPE_MAXIMUM): Do not shift a
+	negative number, which the C Standard says has undefined behavior.
+	In practice this is not a problem, but might as well do it by the book.
+	Reported by Rich Felker and Eric Blake; see
+	<http://lists.gnu.org/archive/html/bug-gnulib/2011-01/msg00493.html>.
+	* lib/strtol.c (TYPE_MINIMUM, TYPE_MAXIMUM): Likewise.
+	* m4/mktime.m4 (AC_FUNC_MKTIME): Likewise.
+	* m4/nanosleep.m4 (gl_FUNC_NANOSLEEP): Likewise.
+	* m4/parse-datetime.m4 (gl_PARSE_DATETIME): Likewise.
+	* m4/stdint.m4 (gl_STDINT_H): Likewise.
+	* lib/mktime.c (TYPE_MAXIMUM): Redo slightly to match the others.
+
 	mktime: #undef mktime before #defining it
 	* lib/mktime.c (mktime) [DEBUG]: #undef mktime before #defining it.
 
diff --git a/lib/intprops.h b/lib/intprops.h
index 511a5aa..58b1b3f 100644
--- a/lib/intprops.h
+++ b/lib/intprops.h
@@ -49,11 +49,11 @@
         ? (t) 0 \
         : TYPE_SIGNED_MAGNITUDE (t) \
         ? ~ (t) 0 \
-        : ~ (t) 0 << (sizeof (t) * CHAR_BIT - 1)))
+        : ~ TYPE_MAXIMUM (t)))
 # define TYPE_MAXIMUM(t) \
   ((t) (! TYPE_SIGNED (t) \
         ? (t) -1 \
-        : ~ (~ (t) 0 << (sizeof (t) * CHAR_BIT - 1))))
+        : ((((t) 1 << (sizeof (t) * CHAR_BIT - 2)) - 1) * 2 + 1)))
 
 /* Return zero if T can be determined to be an unsigned type.
    Otherwise, return 1.
diff --git a/lib/mktime.c b/lib/mktime.c
index d35bdd0..2486514 100644
--- a/lib/mktime.c
+++ b/lib/mktime.c
@@ -113,7 +113,7 @@ typedef long long int long_int;
 #define TYPE_MAXIMUM(t) \
   ((t) (! TYPE_SIGNED (t) \
         ? (t) -1 \
-        : (((((t) 1 << (sizeof (t) * CHAR_BIT - 2)) - 1) << 1) + 1)))
+        : ((((t) 1 << (sizeof (t) * CHAR_BIT - 2)) - 1) * 2 + 1)))
 
 #ifndef TIME_T_MIN
 # define TIME_T_MIN TYPE_MINIMUM (time_t)
diff --git a/lib/strtol.c b/lib/strtol.c
index 747d70e..b6a761e 100644
--- a/lib/strtol.c
+++ b/lib/strtol.c
@@ -141,11 +141,11 @@
          ? (t) 0 \
          : TYPE_SIGNED_MAGNITUDE (t) \
          ? ~ (t) 0 \
-         : ~ (t) 0 << (sizeof (t) * CHAR_BIT - 1)))
+         : ~ TYPE_MAXIMUM (t)))
 # define TYPE_MAXIMUM(t) \
    ((t) (! TYPE_SIGNED (t) \
          ? (t) -1 \
-         : ~ (~ (t) 0 << (sizeof (t) * CHAR_BIT - 1))))
+         : ((((t) 1 << (sizeof (t) * CHAR_BIT - 2)) - 1) * 2 + 1)))
 
 # ifndef ULLONG_MAX
 #  define ULLONG_MAX TYPE_MAXIMUM (unsigned long long)
diff --git a/m4/mktime.m4 b/m4/mktime.m4
index 7836b76..56b2416 100644
--- a/m4/mktime.m4
+++ b/m4/mktime.m4
@@ -1,4 +1,4 @@
-# serial 18
+# serial 19
 dnl Copyright (C) 2002-2003, 2005-2007, 2009-2011 Free Software Foundation,
 dnl Inc.
 dnl This file is free software; the Free Software Foundation
@@ -175,12 +175,13 @@ main ()
 
   time_t_max = (! time_t_signed
                 ? (time_t) -1
-                : ~ (~ (time_t) 0 << (sizeof (time_t) * CHAR_BIT - 1)));
+                : ((((time_t) 1 << (sizeof (time_t) * CHAR_BIT - 2)) - 1)
+                   * 2 + 1));
   time_t_min = (! time_t_signed
                 ? (time_t) 0
                 : time_t_signed_magnitude
                 ? ~ (time_t) 0
-                : ~ (time_t) 0 << (sizeof (time_t) * CHAR_BIT - 1));
+                : ~ time_t_max);
 
   delta = time_t_max / 997; /* a suitable prime number */
   for (i = 0; i < N_STRINGS; i++)
diff --git a/m4/nanosleep.m4 b/m4/nanosleep.m4
index 233f1c1..34493bb 100644
--- a/m4/nanosleep.m4
+++ b/m4/nanosleep.m4
@@ -1,4 +1,4 @@
-# serial 32
+# serial 33
 
 dnl From Jim Meyering.
 dnl Check for the nanosleep function.
@@ -58,7 +58,7 @@ AC_DEFUN([gl_FUNC_NANOSLEEP],
           #define TYPE_MAXIMUM(t) \
             ((t) (! TYPE_SIGNED (t) \
                   ? (t) -1 \
-                  : ~ (~ (t) 0 << (sizeof (t) * CHAR_BIT - 1))))
+                  : ((((t) 1 << (sizeof (t) * CHAR_BIT - 2)) - 1) * 2 + 1)))
 
           static void
           check_for_SIGALRM (int sig)
diff --git a/m4/parse-datetime.m4 b/m4/parse-datetime.m4
index 2341de9..e665ef3 100644
--- a/m4/parse-datetime.m4
+++ b/m4/parse-datetime.m4
@@ -1,4 +1,4 @@
-# parse-datetime.m4 serial 18
+# parse-datetime.m4 serial 19
 dnl Copyright (C) 2002-2006, 2008-2011 Free Software Foundation, Inc.
 dnl This file is free software; the Free Software Foundation
 dnl gives unlimited permission to copy and/or distribute it,
@@ -41,9 +41,11 @@ AC_DEFUN([gl_PARSE_DATETIME],
 #include <time.h> /* for time_t */
 #include <limits.h> /* for CHAR_BIT, LONG_MIN, LONG_MAX */
 #define TYPE_MINIMUM(t) \
-  ((t) ((t) 0 < (t) -1 ? (t) 0 : ~ (t) 0 << (sizeof (t) * CHAR_BIT - 1)))
+  ((t) ((t) 0 < (t) -1 ? (t) 0 : ~ TYPE_MAXIMUM (t)))
 #define TYPE_MAXIMUM(t) \
-  ((t) ((t) 0 < (t) -1 ? (t) -1 : ~ (~ (t) 0 << (sizeof (t) * CHAR_BIT - 1))))
+  ((t) ((t) 0 < (t) -1 \
+        ? (t) -1 \
+        : ((((t) 1 << (sizeof (t) * CHAR_BIT - 2)) - 1) * 2 + 1)))
 typedef int verify_min[2 * (LONG_MIN <= TYPE_MINIMUM (time_t)) - 1];
 typedef int verify_max[2 * (TYPE_MAXIMUM (time_t) <= LONG_MAX) - 1];
        ]])],
diff --git a/m4/stdint.m4 b/m4/stdint.m4
index 43e1f70..26654c6 100644
--- a/m4/stdint.m4
+++ b/m4/stdint.m4
@@ -1,4 +1,4 @@
-# stdint.m4 serial 36
+# stdint.m4 serial 37
 dnl Copyright (C) 2001-2011 Free Software Foundation, Inc.
 dnl This file is free software; the Free Software Foundation
 dnl gives unlimited permission to copy and/or distribute it,
@@ -145,9 +145,11 @@ uintmax_t j = UINTMAX_MAX;
 
 #include <limits.h> /* for CHAR_BIT */
 #define TYPE_MINIMUM(t) \
-  ((t) ((t) 0 < (t) -1 ? (t) 0 : ~ (t) 0 << (sizeof (t) * CHAR_BIT - 1)))
+  ((t) ((t) 0 < (t) -1 ? (t) 0 : ~ TYPE_MAXIMUM (t)))
 #define TYPE_MAXIMUM(t) \
-  ((t) ((t) 0 < (t) -1 ? (t) -1 : ~ (~ (t) 0 << (sizeof (t) * CHAR_BIT - 1))))
+  ((t) ((t) 0 < (t) -1 \
+        ? (t) -1 \
+        : ((((t) 1 << (sizeof (t) * CHAR_BIT - 2)) - 1) * 2 + 1)))
 struct s {
   int check_PTRDIFF:
       PTRDIFF_MIN == TYPE_MINIMUM (ptrdiff_t)
-- 
1.7.3

Subject: mktime test in configure: UB resulting in infinite loop
From: Rich Felker <[email-masked]>
To: [email-masked]
Date: Thu, 27 Jan 2011 00:21:59 -0500
List-Id: <debbugs-submit.debbugs.gnu.org>

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.