[tz] infinite loop in time2sub

enh enh at google.com
Thu Aug 22 18:35:32 UTC 2013


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 at 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 at 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mm.icann.org/pipermail/tz/attachments/20130822/d6bb65ed/attachment.htm>


More information about the tz mailing list