[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: mktime() hangs for dates before 1970
From: 
Paul Eggert 
Subject: 
Re: mktime() hangs for dates before 1970 
Date: 
Sat, 29 Jan 2011 15:51:47 0800 
Useragent: 
Mozilla/5.0 (X11; U; Linux i686; enUS; rv:1.9.2.13) Gecko/20101208 Thunderbird/3.1.7 
Thanks for that detailed chasedown of the bug. If I understand
things correctly, the following patch, which I just pushed into
gnulib, should fix it. I see one or two other lessimportant
issues with mktime and look at them next. I'll let you know
when I'm done, and have a mktime.c that it would be helpful if
you could try on your platform.

ChangeLog  32 ++++++++++++
lib/mktime.c  159 +++++++++++++++++++++++++++++++++++++++
2 files changed, 141 insertions(+), 50 deletions()
diff git a/ChangeLog b/ChangeLog
index e842191..362c33f 100644
 a/ChangeLog
+++ b/ChangeLog
@@ 1,3 +1,35 @@
+20110129 Paul Eggert <address@hidden>
+
+ mktime: fix some integer overflow issues and sidestep the rest
+
+ This was prompted by a bug report by Benjamin Lindner for MinGW
+ <http://lists.gnu.org/archive/html/buggnulib/201101/msg00472.html>.
+ His bug is due to signed integer overflow (0  INT_MIN), and I
+ I scanned through mktime.c looking for other integer overflow
+ problems, fixing all the bugs I found.
+
+ Although the C Standard says the resulting code is still not safe
+ in the presence of integer overflow, in practice it should be good
+ enough for all realworld two'scomplement implementations, except
+ for debugging environments that deliberately trap on integer
+ overflow (e.g., gcc ftrapv).
+
+ * lib/mktime.c (WRAPV): New macro.
+ (SHR): Also check that long_int and time_t shift right in the
+ usual way, before using the fastbutunportable method.
+ (TYPE_ONES_COMPLEMENT, TYPE_SIGNED_MAGNITUDE): Remove, no longer
+ used. The code already assumed two's complement, so there's
+ no need to test for alternatives. All uses removed.
+ (TYPE_MAXIMUM): Don't rely here on overflow behavior not defined by
+ the C standard. Problem reported by Rich Felker in
+ <http://lists.gnu.org/archive/html/buggnulib/201101/msg00488.html>.
+ (twos_complement_arithmetic): Also check long_int and time_t.
+ (time_t_avg, time_t_add_ok, time_t_int_add_ok): New functions.
+ (guess_time_tm, ranged_convert, __mktime_internal): Use them.
+ (__mktime_internal): Avoid integer overflow with unary subtraction
+ in two instances where 1  X is an adequate replacement for X,
+ since the calculations are approximate.
+
20110129 Eric Blake <address@hidden>
mktime: avoid infinite loop
diff git a/lib/mktime.c b/lib/mktime.c
index 213dedc..6eb9bfc 100644
 a/lib/mktime.c
+++ b/lib/mktime.c
@@ 25,6 +25,24 @@
# include <config.h>
#endif
+/* Some of the code in this file assumes that signed integer overflow
+ silently wraps around. This assumption can't easily be programmed
+ around, nor can it be checked for portably at compiletime or
+ easily eliminated at runtime.
+
+ Define WRAPV to 1 if the assumption is valid. Otherwise, define it
+ to 0; this forces the use of slower code that, while not guaranteed
+ by the C Standard, works on all production platforms that we know
+ about. */
+#ifndef WRAPV
+# if (__GNUC__ == 4 && 4 <= __GNUC_MINOR__)  4 < __GNUC__
+# pragma GCC optimize ("wrapv")
+# define WRAPV 1
+# else
+# define WRAPV 0
+# endif
+#endif
+
/* Assume that leap seconds are possible, unless told otherwise.
If the host has a `zic' command with a `L leapsecondfilename' option,
then it supports leap seconds; otherwise it probably doesn't. */
@@ 45,6 +63,13 @@
# define mktime my_mktime
#endif /* DEBUG */
+/* A signed type that is at least one bit wider than int. */
+#if INT_MAX <= LONG_MAX / 2
+typedef long int long_int;
+#else
+typedef long long int long_int;
+#endif
+
/* Shift A right by B bits portably, by dividing A by 2**B and
truncating towards minus infinity. A and B should be free of side
effects, and B should be in the range 0 <= B <= INT_BITS  2, where
@@ 55,9 +80,11 @@
implementations (e.g., UNICOS 9.0 on a Cray YMP EL) don't shift
right in the usual way when A < 0, so SHR falls back on division if
ordinary A >> B doesn't seem to be the usual signed shift. */
#define SHR(a, b) \
 (1 >> 1 == 1 \
 ? (a) >> (b) \
+#define SHR(a, b) \
+ ((1 >> 1 == 1 \
+ && (long_int) 1 >> 1 == 1 \
+ && ((time_t) 1 >> 1 == 1  ! TYPE_SIGNED (time_t))) \
+ ? (a) >> (b) \
: (a) / (1 << (b))  ((a) % (1 << (b)) < 0))
/* The extra casts in the following macros work around compiler bugs,
@@ 68,12 +95,8 @@
#define TYPE_IS_INTEGER(t) ((t) 1.5 == 1)
/* 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. */
+ complement, or if T is an unsigned integer type. */
#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))
@@ 85,13 +108,11 @@
#define TYPE_MINIMUM(t) \
((t) (! TYPE_SIGNED (t) \
? (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) << 1) + 1)))
#ifndef TIME_T_MIN
# define TIME_T_MIN TYPE_MINIMUM (time_t)
@@ 105,21 +126,15 @@
#define verify(name, assertion) struct name { char a[(assertion) ? 1 : 1]; }
verify (time_t_is_integer, TYPE_IS_INTEGER (time_t));
verify (twos_complement_arithmetic, TYPE_TWOS_COMPLEMENT (int));
/* The code also assumes that signed integer overflow silently wraps
 around, but this assumption can't be stated without causing a
 diagnostic on some hosts. */
+verify (twos_complement_arithmetic,
+ (TYPE_TWOS_COMPLEMENT (int)
+ && TYPE_TWOS_COMPLEMENT (long_int)
+ && TYPE_TWOS_COMPLEMENT (time_t)));
#define EPOCH_YEAR 1970
#define TM_YEAR_BASE 1900
verify (base_year_is_a_multiple_of_100, TM_YEAR_BASE % 100 == 0);
#if INT_MAX <= LONG_MAX / 2
typedef long int long_int;
#else
typedef long long int long_int;
#endif

/* Return 1 if YEAR + TM_YEAR_BASE is a leap year. */
static inline int
leapyear (long_int year)
@@ 196,6 +211,53 @@ ydhms_diff (long_int year1, long_int yday1, int hour1, int
min1, int sec1,
return seconds;
}
+/* Return the average of A and B, even if A + B would overflow. */
+static time_t
+time_t_avg (time_t a, time_t b)
+{
+ return SHR (a, 1) + SHR (b, 1) + (a & b & 1);
+}
+
+/* Return 1 if A + B does not overflow. If time_t is unsigned and if
+ B's top bit is set, assume that the sum represents A  B, and
+ return 1 if the subtraction does not wrap around. */
+static int
+time_t_add_ok (time_t a, time_t b)
+{
+ if (! TYPE_SIGNED (time_t))
+ {
+ time_t sum = a + b;
+ return (sum < a) == (TIME_T_MIDPOINT <= b);
+ }
+ else if (WRAPV)
+ {
+ time_t sum = a + b;
+ return (sum < a) == (b < 0);
+ }
+ else
+ {
+ time_t avg = time_t_avg (a, b);
+ return TIME_T_MIN / 2 <= avg && avg <= TIME_T_MAX / 2;
+ }
+}
+
+/* Return 1 if A + B does not overflow. */
+static int
+time_t_int_add_ok (time_t a, int b)
+{
+ verify (int_no_wider_than_time_t, INT_MAX <= TIME_T_MAX);
+ if (WRAPV)
+ {
+ time_t sum = a + b;
+ return (sum < a) == (b < 0);
+ }
+ else
+ {
+ int a_odd = a & 1;
+ time_t avg = SHR (a, 1) + (SHR (b, 1) + (a_odd & b));
+ return TIME_T_MIN / 2 <= avg && avg <= TIME_T_MAX / 2;
+ }
+}
/* Return a time_t value corresponding to (YEARYDAY HOUR:MIN:SEC),
assuming that *T corresponds to *TP and that no clock adjustments
@@ 212,9 +274,8 @@ guess_time_tm (long_int year, long_int yday, int hour, int
min, int sec,
time_t d = ydhms_diff (year, yday, hour, min, sec,
tp>tm_year, tp>tm_yday,
tp>tm_hour, tp>tm_min, tp>tm_sec);
 time_t t1 = *t + d;
 if ((t1 < *t) == (TYPE_SIGNED (time_t) ? d < 0 : TIME_T_MAX / 2 < d))
 return t1;
+ if (time_t_add_ok (*t, d))
+ return *t + d;
}
/* Overflow occurred one way or another. Return the nearest result
@@ 246,9 +307,7 @@ ranged_convert (struct tm *(*convert) (const time_t *,
struct tm *),
they differ by 1. */
while (bad != ok + (bad < 0 ? 1 : 1))
{
 time_t mid = *t = (bad < 0
 ? bad + ((ok  bad) >> 1)
 : ok + ((bad  ok) >> 1));
+ time_t mid = *t = time_t_avg (ok, bad);
r = convert (t, tp);
if (r)
ok = mid;
@@ 376,7 +435,7 @@ __mktime_internal (struct tm *tp,
int approx_biennia = SHR (t0, ALOG2_SECONDS_PER_BIENNIUM);
int diff = approx_biennia  approx_requested_biennia;
 int abs_diff = diff < 0 ?  diff : diff;
+ int abs_diff = diff < 0 ? 1  diff : diff;
/* IRIX 4.0.5 cc miscalculates TIME_T_MIN / 3: it erroneously
gives a positive value of 715827882. Setting a variable
@@ 394,7 +453,7 @@ __mktime_internal (struct tm *tp,
time_t repaired_t0 = 1  t0;
approx_biennia = SHR (repaired_t0, ALOG2_SECONDS_PER_BIENNIUM);
diff = approx_biennia  approx_requested_biennia;
 abs_diff = diff < 0 ?  diff : diff;
+ abs_diff = diff < 0 ? 1  diff : diff;
if (overflow_threshold < abs_diff)
return 1;
guessed_offset += repaired_t0  t0;
@@ 462,22 +521,20 @@ __mktime_internal (struct tm *tp,
for (delta = stride; delta < delta_bound; delta += stride)
for (direction = 1; direction <= 1; direction += 2)
 {
 time_t ot = t + delta * direction;
 if ((ot < t) == (direction < 0))
 {
 struct tm otm;
 ranged_convert (convert, &ot, &otm);
 if (otm.tm_isdst == isdst)
 {
 /* We found the desired tm_isdst.
 Extrapolate back to the desired time. */
 t = guess_time_tm (year, yday, hour, min, sec, &ot, &otm);
 ranged_convert (convert, &t, &tm);
 goto offset_found;
 }
 }
 }
+ if (time_t_int_add_ok (t, delta * direction))
+ {
+ time_t ot = t + delta * direction;
+ struct tm otm;
+ ranged_convert (convert, &ot, &otm);
+ if (otm.tm_isdst == isdst)
+ {
+ /* We found the desired tm_isdst.
+ Extrapolate back to the desired time. */
+ t = guess_time_tm (year, yday, hour, min, sec, &ot, &otm);
+ ranged_convert (convert, &t, &tm);
+ goto offset_found;
+ }
+ }
}
offset_found:
@@ 488,11 +545,13 @@ __mktime_internal (struct tm *tp,
/* Adjust time to reflect the tm_sec requested, not the normalized value.
Also, repair any damage from a false match due to a leap second. */
int sec_adjustment = (sec == 0 && tm.tm_sec == 60)  sec;
+ if (! time_t_int_add_ok (t, sec_requested))
+ return 1;
t1 = t + sec_requested;
+ if (! time_t_int_add_ok (t1, sec_adjustment))
+ return 1;
t2 = t1 + sec_adjustment;
 if (((t1 < t) != (sec_requested < 0))
  ((t2 < t1) != (sec_adjustment < 0))
  ! convert (&t2, &tm))
+ if (! convert (&t2, &tm))
return 1;
t = t2;
}
@@ 667,6 +726,6 @@ main (int argc, char **argv)
/*
Local Variables:
compilecommand: "gcc DDEBUG Wall W O g mktime.c o mktime"
+compilecommand: "gcc DDEBUG Wall W O2 g mktime.c o mktime"
End:
*/

1.7.3
 mktime() hangs for dates before 1970, Benjamin Lindner, 2011/01/27
 Re: mktime() hangs for dates before 1970, Paul Eggert, 2011/01/27
 Re: mktime() hangs for dates before 1970, Benjamin Lindner, 2011/01/28
 Re: mktime() hangs for dates before 1970,
Paul Eggert <=
 Re: mktime() hangs for dates before 1970, Paul Eggert, 2011/01/30
 Re: mktime() hangs for dates before 1970, Benjamin Lindner, 2011/01/31
 Re: mktime() hangs for dates before 1970, Ralf Wildenhues, 2011/01/30
 Re: mktime() hangs for dates before 1970, Paul Eggert, 2011/01/30
 Re: mktime() hangs for dates before 1970, Ralf Wildenhues, 2011/01/30
 Re: mktime() hangs for dates before 1970, Paul Eggert, 2011/01/30
 Re: mktime() hangs for dates before 1970, Ralf Wildenhues, 2011/01/30