infinite loop in time2sub
i recently upgraded Android's copy of tzcode to be closer to tzcode2013d. with Android's signed 32-bit time_t i'm seeing a change in behavior for out-of-range dates. previously given something like this, mktime would return an error, but now it hangs in the binary search in time2sub. struct tm t; memset(&t, 0, sizeof(tm)); t.tm_year = 200; t.tm_mon = 2; t.tm_mday = 10; changing the if (t == lo) { ++t; if (t <= lo) return WRONG; ++lo; } else if (t == hi) { --t; if (t >= hi) return WRONG; --hi; } back to if (t == lo) { if (t == TIME_T_MAX) return WRONG; ++t; ++lo; } else if (t == hi) { if (t == TIME_T_MIN) return WRONG; --t; --hi; } fixes things. looking at the git history in https://github.com/eggert/tz.gitit looks like the old code, found in Android up to and including jb-mr2 (but no longer in AOSP ToT), was never in upstream tzcode. here's where the upstream tzcode's overflow checks were introduced: commit 46fa7e98177cae664f673c6034c9ac74d0ccd0ec Author: Arthur David Olson <olsona@elsie> Date: Tue Aug 9 09:55:06 2005 -0400 overflow work SCCS-file: localtime.c SCCS-SID: 7.96 diff --git a/localtime.c b/localtime.c index 1c3e9b0..d3edb5a 100644 --- a/localtime.c +++ b/localtime.c @@ -1616,9 +1616,13 @@ const int do_norm_secs; if (dir != 0) { if (t == lo) { ++t; + if (t <= lo) + return WRONG; ++lo; } else if (t == hi) { --t; + if (t >= hi) + return WRONG; --hi; } if (lo > hi) looking at the Android AOSP git history, it looks like we found and fixed this bug years ago but never talked to upstream about it: commit 2093d350be21ff086f9e145404877941b9a42c5c Author: David 'Digit' Turner <digit@google.com> Date: Wed Sep 9 17:41:59 2009 -0700 Fix an infinite loop in time2sub. The problem is that time_t is signed, and the original code relied on the fact that (X + c < X) in case of overflow for c >= 0. Unfortunately, this condition is only guaranteed by the standard for unsigned arithmetic, and the gcc 4.4.0 optimizer did completely remove the corresponding test from the code. This resulted in a missing boundary check, and an infinite loop. The problem is solved by testing explicitely for TIME_T_MIN and TIME_T_MAX in the loop that uses this. Also fix increment_overflow and long_increment_overflow which were buggy for exactly the same reasons. Note: a similar fix is needed for system/core/libcutils diff --git a/libc/tzcode/localtime.c b/libc/tzcode/localtime.c index 9c5f218..83c1011 100644 --- a/libc/tzcode/localtime.c +++ b/libc/tzcode/localtime.c @@ -75,6 +75,31 @@ static __inline__ void _tzUnlock(void) pthread_mutex_unlock(&_tzMutex); } +/* Complex computations to determine the min/max of time_t depending + * on TYPE_BIT / TYPE_SIGNED / TYPE_INTEGRAL. + * These macros cannot be used in pre-processor directives, so we + * let the C compiler do the work, which makes things a bit funky. + */ +static const time_t TIME_T_MAX = + TYPE_INTEGRAL(time_t) ? + ( TYPE_SIGNED(time_t) ? + ~((time_t)1 << (TYPE_BIT(time_t)-1)) + : + ~(time_t)0 + ) + : /* if time_t is a floating point number */ + ( sizeof(time_t) > sizeof(float) ? (time_t)DBL_MAX : (time_t)FLT_MAX ); + +static const time_t TIME_T_MIN = + TYPE_INTEGRAL(time_t) ? + ( TYPE_SIGNED(time_t) ? + ((time_t)1 << (TYPE_BIT(time_t)-1)) + : + 0 + ) + : + ( sizeof(time_t) > sizeof(float) ? (time_t)DBL_MIN : (time_t)FLT_MIN ); + #ifndef WILDABBR /* ** Someone might make incorrect use of a time zone abbreviation: @@ -1683,11 +1708,16 @@ increment_overflow(number, delta) int * number; int delta; { - int number0; + unsigned number0 = (unsigned)*number; + unsigned number1 = (unsigned)(number0 + delta); + + *number = (int)number1; - number0 = *number; - *number += delta; - return (*number < number0) != (delta < 0); + if (delta >= 0) { + return ((int)number1 < (int)number0); + } else { + return ((int)number1 > (int)number0); + } } static int @@ -1695,11 +1725,16 @@ long_increment_overflow(number, delta) long * number; int delta; { - long number0; + unsigned long number0 = (unsigned long)*number; + unsigned long number1 = (unsigned long)(number0 + delta); + + *number = (long)number1; - number0 = *number; - *number += delta; - return (*number < number0) != (delta < 0); + if (delta >= 0) { + return ((long)number1 < (long)number0); + } else { + return ((long)number1 > (long)number0); + } } static int @@ -1868,14 +1903,14 @@ const int do_norm_secs; } else dir = tmcomp(&mytm, &yourtm); if (dir != 0) { if (t == lo) { - ++t; - if (t <= lo) + if (t == TIME_T_MAX) return WRONG; + ++t; ++lo; } else if (t == hi) { - --t; - if (t >= hi) + if (t == TIME_T_MIN) return WRONG; + --t; --hi; } if (lo > hi) right now i'm going to work around this by building the tzcode part of the C library with -fno-strict-overflow (because i don't know how many other places are relying on this unspecified behavior), but i'll apply whatever patch goes into upstream as soon as it's available. --elliott
On 08/22/13 11:35, enh wrote:
looking at the Android AOSP git history, it looks like we found and fixed this bug years ago but never talked to upstream about it:
Thanks for the heads-up. If I understand all those patches aright, the following patch (which I've pushed to the experimental github repository) should fix things. I've fixed some other integer-overflow issues in the past few months, but I missed this one (and there are probably others I've missed).
From 943a6621866e9d6e654f5cfe1494378c1fb8957a Mon Sep 17 00:00:00 2001 From: Paul Eggert <eggert@cs.ucla.edu> Date: Thu, 22 Aug 2013 12:47:51 -0700 Subject: [PATCH] * localtime.c: Fix another integer overflow bug in mktime.
(time2sub): Avoid undefined behavior on time_t overflow. Reported by Elliott Hughes in <http://mm.icann.org/pipermail/tz/2013-August/019580.html>. --- localtime.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/localtime.c b/localtime.c index f58b20a..a0a4e5e 100644 --- a/localtime.c +++ b/localtime.c @@ -1789,14 +1789,14 @@ time2sub(struct tm *const tmp, } else dir = tmcomp(&mytm, &yourtm); if (dir != 0) { if (t == lo) { - ++t; - if (t <= lo) + if (t == time_t_max) return WRONG; + ++t; ++lo; } else if (t == hi) { - --t; - if (t >= hi) + if (t == time_t_min) return WRONG; + --t; --hi; } if (lo > hi) -- 1.7.11.7
that passes my test and GCC's -Wstrict-overflow=5 no longer complains about those two lines (though it does still have several other complaints about localtime.c). committed to Android's C library as 713fe6463e6ff8cb9689aa8ead88c885d25d03aa ( https://android-review.googlesource.com/#/c/64140/). thanks! On Thu, Aug 22, 2013 at 12:53 PM, Paul Eggert <eggert@cs.ucla.edu> wrote:
On 08/22/13 11:35, enh wrote:
looking at the Android AOSP git history, it looks like we found and fixed this bug years ago but never talked to upstream about it:
Thanks for the heads-up. If I understand all those patches aright, the following patch (which I've pushed to the experimental github repository) should fix things. I've fixed some other integer-overflow issues in the past few months, but I missed this one (and there are probably others I've missed).
From 943a6621866e9d6e654f5cfe1494378c1fb8957a Mon Sep 17 00:00:00 2001 From: Paul Eggert <eggert@cs.ucla.edu> Date: Thu, 22 Aug 2013 12:47:51 -0700 Subject: [PATCH] * localtime.c: Fix another integer overflow bug in mktime.
(time2sub): Avoid undefined behavior on time_t overflow. Reported by Elliott Hughes in <http://mm.icann.org/pipermail/tz/2013-August/019580.html>. --- localtime.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-)
diff --git a/localtime.c b/localtime.c index f58b20a..a0a4e5e 100644 --- a/localtime.c +++ b/localtime.c @@ -1789,14 +1789,14 @@ time2sub(struct tm *const tmp, } else dir = tmcomp(&mytm, &yourtm); if (dir != 0) { if (t == lo) { - ++t; - if (t <= lo) + if (t == time_t_max) return WRONG; + ++t; ++lo; } else if (t == hi) { - --t; - if (t >= hi) + if (t == time_t_min) return WRONG; + --t; --hi; } if (lo > hi) -- 1.7.11.7
-- Elliott Hughes - http://who/enh - http://jessies.org/~enh/ Java i18n/JNI/NIO, or bionic questions? Mail me/drop by/add me as a reviewer.
participants (2)
-
enh -
Paul Eggert