bug-gnulib
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[PATCH] timespec-sub: fix overflow bug; add tests


From: Paul Eggert
Subject: [PATCH] timespec-sub: fix overflow bug; add tests
Date: Thu, 5 Nov 2015 18:27:58 -0800

* lib/timespec-add.c (timespec_add):
* lib/timespec-sub.c (timespec_sub):
Work even if time_t is narrower than int (a theoretical
possibility).  Redo code for a bit more clarity.
* lib/timespec-sub.c (timespec_sub):
Fix off-by-2 bug if a.tv_sec == TYPE_MINIMUM (time_t) and 0 < b.tv_sec.
* modules/timespec-tests, tests/test-timespec.c: New files.
---
 ChangeLog              |   9 +++
 lib/timespec-add.c     |  27 ++++----
 lib/timespec-sub.c     |  27 ++++----
 modules/timespec-tests |  16 +++++
 tests/test-timespec.c  | 167 +++++++++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 222 insertions(+), 24 deletions(-)
 create mode 100644 modules/timespec-tests
 create mode 100644 tests/test-timespec.c

diff --git a/ChangeLog b/ChangeLog
index 336cd3d..82534cb 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,14 @@
 2015-11-05  Paul Eggert  <address@hidden>
 
+       timespec-sub: fix overflow bug; add tests
+       * lib/timespec-add.c (timespec_add):
+       * lib/timespec-sub.c (timespec_sub):
+       Work even if time_t is narrower than int (a theoretical
+       possibility).  Redo code for a bit more clarity.
+       * lib/timespec-sub.c (timespec_sub):
+       Fix off-by-2 bug if a.tv_sec == TYPE_MINIMUM (time_t) and 0 < b.tv_sec.
+       * modules/timespec-tests, tests/test-timespec.c: New files.
+
        intprops-test: suppress -Woverlength-strings
        Problem reported by Pádraig Brady in:
        http://lists.gnu.org/archive/html/bug-gnulib/2015-11/msg00008.html
diff --git a/lib/timespec-add.c b/lib/timespec-add.c
index 255489e..e8f6aac 100644
--- a/lib/timespec-add.c
+++ b/lib/timespec-add.c
@@ -33,36 +33,39 @@ timespec_add (struct timespec a, struct timespec b)
   int ns = a.tv_nsec + b.tv_nsec;
   int nsd = ns - TIMESPEC_RESOLUTION;
   int rns = ns;
+  time_t tmin = TYPE_MINIMUM (time_t);
+  time_t tmax = TYPE_MAXIMUM (time_t);
 
   if (0 <= nsd)
     {
       rns = nsd;
-      if (rs == TYPE_MAXIMUM (time_t))
-        {
-          if (0 <= bs)
-            goto high_overflow;
-          bs++;
-        }
-      else
+      if (bs < tmax)
+        bs++;
+      else if (rs < 0)
         rs++;
+      else
+        goto high_overflow;
     }
 
-  if (INT_ADD_OVERFLOW (rs, bs))
+  /* INT_ADD_WRAPV is not appropriate since time_t might be unsigned.
+     In theory time_t might be narrower than int, so plain
+     INT_ADD_OVERFLOW does not suffice.  */
+  if (! INT_ADD_OVERFLOW (rs, bs) && tmin <= rs + bs && rs + bs <= tmax)
+    rs += bs;
+  else
     {
       if (rs < 0)
         {
-          rs = TYPE_MINIMUM (time_t);
+          rs = tmin;
           rns = 0;
         }
       else
         {
         high_overflow:
-          rs = TYPE_MAXIMUM (time_t);
+          rs = tmax;
           rns = TIMESPEC_RESOLUTION - 1;
         }
     }
-  else
-    rs += bs;
 
   return make_timespec (rs, rns);
 }
diff --git a/lib/timespec-sub.c b/lib/timespec-sub.c
index c574375..392ec15 100644
--- a/lib/timespec-sub.c
+++ b/lib/timespec-sub.c
@@ -33,36 +33,39 @@ timespec_sub (struct timespec a, struct timespec b)
   time_t bs = b.tv_sec;
   int ns = a.tv_nsec - b.tv_nsec;
   int rns = ns;
+  time_t tmin = TYPE_MINIMUM (time_t);
+  time_t tmax = TYPE_MAXIMUM (time_t);
 
   if (ns < 0)
     {
       rns = ns + TIMESPEC_RESOLUTION;
-      if (rs == TYPE_MINIMUM (time_t))
-        {
-          if (bs <= 0)
-            goto low_overflow;
-          bs--;
-        }
-      else
+      if (bs < tmax)
+        bs++;
+      else if (- TYPE_SIGNED (time_t) < rs)
         rs--;
+      else
+        goto low_overflow;
     }
 
-  if (INT_SUBTRACT_OVERFLOW (rs, bs))
+  /* INT_SUBTRACT_WRAPV is not appropriate since time_t might be unsigned.
+     In theory time_t might be narrower than int, so plain
+     INT_SUBTRACT_OVERFLOW does not suffice.  */
+  if (! INT_SUBTRACT_OVERFLOW (rs, bs) && tmin <= rs - bs && rs - bs <= tmax)
+    rs -= bs;
+  else
     {
       if (rs < 0)
         {
         low_overflow:
-          rs = TYPE_MINIMUM (time_t);
+          rs = tmin;
           rns = 0;
         }
       else
         {
-          rs = TYPE_MAXIMUM (time_t);
+          rs = tmax;
           rns = TIMESPEC_RESOLUTION - 1;
         }
     }
-  else
-    rs -= bs;
 
   return make_timespec (rs, rns);
 }
diff --git a/modules/timespec-tests b/modules/timespec-tests
new file mode 100644
index 0000000..ecd0dae
--- /dev/null
+++ b/modules/timespec-tests
@@ -0,0 +1,16 @@
+Files:
+tests/test-timespec.c
+tests/macros.h
+
+Depends-on:
+dtotimespec
+intprops
+stdbool
+timespec-add
+timespec-sub
+
+configure.ac:
+
+Makefile.am:
+TESTS += test-timespec
+check_PROGRAMS += test-timespec
diff --git a/tests/test-timespec.c b/tests/test-timespec.c
new file mode 100644
index 0000000..839906c
--- /dev/null
+++ b/tests/test-timespec.c
@@ -0,0 +1,167 @@
+/* Test timespec functions.
+   Copyright 2015 Free Software Foundation, Inc.
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+/* Written by Paul Eggert.  */
+
+#include <config.h>
+
+#include "timespec.h"
+
+#include "intprops.h"
+#include "macros.h"
+
+#include <stdbool.h>
+#include <limits.h>
+
+static struct { int s; int ns; } const prototype[] =
+  {
+    { INT_MIN, 0 },
+    { INT_MIN, 1 },
+    { INT_MIN, TIMESPEC_RESOLUTION - 1 },
+    { INT_MIN + 1, 0 },
+    { INT_MIN + 1, 1 },
+    { INT_MIN + 1, TIMESPEC_RESOLUTION - 1 },
+    { -1, 0 },
+    { -1, 1 },
+    { -1, TIMESPEC_RESOLUTION - 1 },
+    { 0, 0 },
+    { 0, 1 },
+    { 0, TIMESPEC_RESOLUTION - 1 },
+    { 1, 0 },
+    { 1, 1 },
+    { 1, TIMESPEC_RESOLUTION - 1 },
+    { 1234567890, 0 },
+    { 1234567890, 1 },
+    { 1234567890, TIMESPEC_RESOLUTION - 1 },
+    { INT_MAX - 1, 0 },
+    { INT_MAX - 1, 1 },
+    { INT_MAX - 1, TIMESPEC_RESOLUTION - 1 },
+    { INT_MAX, 0 },
+    { INT_MAX, 1 },
+    { INT_MAX, TIMESPEC_RESOLUTION - 1 },
+    { INT_MAX, 2 * TIMESPEC_RESOLUTION }
+  };
+enum { nprototypes = sizeof prototype / sizeof *prototype };
+
+static bool
+valid (struct timespec a)
+{
+  return 0 <= a.tv_nsec && a.tv_nsec < TIMESPEC_RESOLUTION;
+}
+
+static int
+sign (int i)
+{
+  return i < 0 ? -1 : 0 < i;
+}
+
+static int
+cmp (struct timespec a, struct timespec b)
+{
+  return sign (timespec_cmp (a, b));
+}
+
+static bool
+eq (struct timespec a, struct timespec b)
+{
+  return timespec_cmp (a, b) == 0;
+}
+
+static bool
+extremal (struct timespec a)
+{
+  return ((a.tv_sec == TYPE_MINIMUM (time_t) && a.tv_nsec == 0)
+         || (a.tv_sec == TYPE_MAXIMUM (time_t)
+             && a.tv_nsec == TIMESPEC_RESOLUTION - 1));
+}
+
+int
+main (void)
+{
+  int i, j, k;
+  struct timespec test[nprototypes + 1];
+  int ntests;
+  int computed_resolution = 1;
+  struct timespec prevroundtrip;
+
+  test[0] = make_timespec (TYPE_MINIMUM (time_t), -1);
+  ntests = 1;
+  for (i = 0; i < nprototypes; i++)
+    {
+      int s = prototype[i].s;
+      if (TYPE_SIGNED (time_t) || 0 <= s)
+       {
+         time_t t = (s <= INT_MIN + 1 ? s - INT_MIN + TYPE_MINIMUM (time_t)
+                     : INT_MAX - 1 <= s ? s - INT_MAX + TYPE_MAXIMUM (time_t)
+                     : s);
+         test[ntests++] = make_timespec (t, prototype[i].ns);
+       }
+    }
+
+  for (i = 0; i < LOG10_TIMESPEC_RESOLUTION; i++)
+    computed_resolution *= 10;
+  ASSERT (computed_resolution == TIMESPEC_RESOLUTION);
+
+  for (i = 0; i < ntests; i++)
+    {
+      struct timespec a = test[i];
+
+      struct timespec roundtrip = dtotimespec (timespectod (a));
+      if (i != 0)
+        ASSERT (cmp (prevroundtrip, roundtrip) <= 0);
+      prevroundtrip = roundtrip;
+
+      ASSERT (sign (timespec_sign (a)) == cmp (a, make_timespec (0, 0)));
+
+      if (valid (a))
+       for (j = 0; j < ntests; j++)
+         {
+           struct timespec b = test[j];
+           if (valid (b))
+             {
+               struct timespec sum = timespec_add (a, b);
+               struct timespec diff = timespec_sub (a, b);
+               struct timespec rdiff = timespec_sub (b, a);
+               ASSERT (cmp (a, b) == sign (i - j));
+               ASSERT (eq (sum, timespec_add (b, a)));
+               if (! extremal (sum))
+                 {
+                   ASSERT (eq (a, timespec_sub (sum, b)));
+                   ASSERT (eq (b, timespec_sub (sum, a)));
+
+                   for (k = 0; k < ntests; k++)
+                     {
+                       struct timespec c = test[j];
+                       if (valid (c))
+                         {
+                           struct timespec sumbc = timespec_add (b, c);
+                           if (! extremal (sumbc))
+                             ASSERT (eq (timespec_add (a, sumbc),
+                                         timespec_add (sum, c)));
+                         }
+                     }
+                 }
+               if (! extremal (diff))
+                 ASSERT (eq (a, timespec_add (diff, b)));
+               if (! extremal (rdiff))
+                 ASSERT (eq (b, timespec_add (rdiff, a)));
+
+             }
+         }
+    }
+
+  return 0;
+}
-- 
2.1.0




reply via email to

[Prev in Thread] Current Thread [Next in Thread]