[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
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [PATCH] timespec-sub: fix overflow bug; add tests,
Paul Eggert <=