Do not advance decay epoch when time goes backwards.

Instead, move the epoch backward in time.  Additionally, add
nstime_monotonic() and use it in debug builds to assert that time only
goes backward if nstime_update() is using a non-monotonic time source.

6 files changed, 63 insertions, 6 deletions

diff --git a/include/jemalloc/internal/nstime.h b/include/jemalloc/internal/nstime.h
index c892bac8..93b27dc8 100644
--- a/include/jemalloc/internal/nstime.h
+++ b/include/jemalloc/internal/nstime.h
@@ -31,9 +31,12 @@ void	nstime_imultiply(nstime_t *time, uint64_t multiplier);
 void	nstime_idivide(nstime_t *time, uint64_t divisor);
 uint64_t	nstime_divide(const nstime_t *time, const nstime_t *divisor);
 #ifdef JEMALLOC_JET
+typedef bool (nstime_monotonic_t)(void);
+extern nstime_monotonic_t *nstime_monotonic;
 typedef bool (nstime_update_t)(nstime_t *);
 extern nstime_update_t *nstime_update;
 #else
+bool	nstime_monotonic(void);
 bool	nstime_update(nstime_t *time);
 #endif
 
diff --git a/include/jemalloc/internal/private_symbols.txt b/include/jemalloc/internal/private_symbols.txt
index c59f82be..cd6681c8 100644
--- a/include/jemalloc/internal/private_symbols.txt
+++ b/include/jemalloc/internal/private_symbols.txt
@@ -360,6 +360,7 @@ nstime_idivide
 nstime_imultiply
 nstime_init
 nstime_init2
+nstime_monotonic
 nstime_ns
 nstime_nsec
 nstime_sec
diff --git a/src/arena.c b/src/arena.c
index 8f2e5d84..dc04acc4 100644
--- a/src/arena.c
+++ b/src/arena.c
@@ -1406,10 +1406,23 @@ arena_maybe_purge_decay(tsdn_t *tsdn, arena_t *arena)
 		return;
 	}
 
-	nstime_copy(&time, &arena->decay.epoch);
-	if (unlikely(nstime_update(&time))) {
-		/* Time went backwards.  Force an epoch advance. */
-		nstime_copy(&time, &arena->decay.deadline);
+	nstime_init(&time, 0);
+	nstime_update(&time);
+	if (unlikely(!nstime_monotonic() && nstime_compare(&arena->decay.epoch,
+	    &time) > 0)) {
+		/*
+		 * Time went backwards.  Move the epoch back in time, with the
+		 * expectation that time typically flows forward for long enough
+		 * periods of time that epochs complete.  Unfortunately,
+		 * this strategy is susceptible to clock jitter triggering
+		 * premature epoch advances, but clock jitter estimation and
+		 * compensation isn't feasible here because calls into this code
+		 * are event-driven.
+		 */
+		nstime_copy(&arena->decay.epoch, &time);
+	} else {
+		/* Verify that time does not go backwards. */
+		assert(nstime_compare(&arena->decay.epoch, &time) <= 0);
 	}
 
 	if (arena_decay_deadline_reached(arena, &time))
diff --git a/src/nstime.c b/src/nstime.c
index cfb1c8e1..c420c88d 100644
--- a/src/nstime.c
+++ b/src/nstime.c
@@ -98,6 +98,7 @@ nstime_divide(const nstime_t *time, const nstime_t *divisor)
 }
 
 #ifdef _WIN32
+#  define NSTIME_MONOTONIC true
 static void
 nstime_get(nstime_t *time)
 {
@@ -110,6 +111,7 @@ nstime_get(nstime_t *time)
 	nstime_init(time, ticks_100ns * 100);
 }
 #elif JEMALLOC_HAVE_CLOCK_MONOTONIC_RAW
+#  define NSTIME_MONOTONIC true
 static void
 nstime_get(nstime_t *time)
 {
@@ -119,6 +121,7 @@ nstime_get(nstime_t *time)
 	nstime_init2(time, ts.tv_sec, ts.tv_nsec);
 }
 #elif JEMALLOC_HAVE_CLOCK_MONOTONIC
+#  define NSTIME_MONOTONIC true
 static void
 nstime_get(nstime_t *time)
 {
@@ -128,6 +131,7 @@ nstime_get(nstime_t *time)
 	nstime_init2(time, ts.tv_sec, ts.tv_nsec);
 }
 #elif JEMALLOC_HAVE_MACH_ABSOLUTE_TIME
+#  define NSTIME_MONOTONIC true
 static void
 nstime_get(nstime_t *time)
 {
@@ -135,6 +139,7 @@ nstime_get(nstime_t *time)
 	nstime_init(time, mach_absolute_time());
 }
 #else
+#  define NSTIME_MONOTONIC false
 static void
 nstime_get(nstime_t *time)
 {
@@ -146,6 +151,23 @@ nstime_get(nstime_t *time)
 #endif
 
 #ifdef JEMALLOC_JET
+#undef nstime_monotonic
+#define	nstime_monotonic JEMALLOC_N(n_nstime_monotonic)
+#endif
+bool
+nstime_monotonic(void)
+{
+
+	return (NSTIME_MONOTONIC);
+#undef NSTIME_MONOTONIC
+}
+#ifdef JEMALLOC_JET
+#undef nstime_monotonic
+#define	nstime_monotonic JEMALLOC_N(nstime_monotonic)
+nstime_monotonic_t *nstime_monotonic = JEMALLOC_N(n_nstime_monotonic);
+#endif
+
+#ifdef JEMALLOC_JET
 #undef nstime_update
 #define	nstime_update JEMALLOC_N(n_nstime_update)
 #endif
diff --git a/test/unit/decay.c b/test/unit/decay.c
index 70a2e67a..b7e4e25e 100644
--- a/test/unit/decay.c
+++ b/test/unit/decay.c
@@ -2,6 +2,7 @@
 
 const char *malloc_conf = "purge:decay,decay_time:1";
 
+static nstime_monotonic_t *nstime_monotonic_orig;
 static nstime_update_t *nstime_update_orig;
 
 static unsigned nupdates_mock;
@@ -9,6 +10,13 @@ static nstime_t time_mock;
 static bool nonmonotonic_mock;
 
 static bool
+nstime_monotonic_mock(void)
+{
+
+	return (false);
+}
+
+static bool
 nstime_update_mock(nstime_t *time)
 {
 
@@ -318,7 +326,9 @@ TEST_BEGIN(test_decay_nonmonotonic)
 	nstime_update(&time_mock);
 	nonmonotonic_mock = true;
 
+	nstime_monotonic_orig = nstime_monotonic;
 	nstime_update_orig = nstime_update;
+	nstime_monotonic = nstime_monotonic_mock;
 	nstime_update = nstime_update_mock;
 
 	for (i = 0; i < NPS; i++) {
@@ -342,8 +352,9 @@ TEST_BEGIN(test_decay_nonmonotonic)
 	    config_stats ? 0 : ENOENT, "Unexpected mallctl result");
 
 	if (config_stats)
-		assert_u64_gt(npurge1, npurge0, "Expected purging to occur");
+		assert_u64_eq(npurge0, npurge1, "Unexpected purging occurred");
 
+	nstime_monotonic = nstime_monotonic_orig;
 	nstime_update = nstime_update_orig;
 #undef NPS
 }
diff --git a/test/unit/nstime.c b/test/unit/nstime.c
index cd7d9a6d..0368bc26 100644
--- a/test/unit/nstime.c
+++ b/test/unit/nstime.c
@@ -176,6 +176,13 @@ TEST_BEGIN(test_nstime_divide)
 }
 TEST_END
 
+TEST_BEGIN(test_nstime_monotonic)
+{
+
+	nstime_monotonic();
+}
+TEST_END
+
 TEST_BEGIN(test_nstime_update)
 {
 	nstime_t nst;
@@ -198,7 +205,6 @@ TEST_BEGIN(test_nstime_update)
 		assert_d_eq(nstime_compare(&nst, &nst0), 0,
 		    "Time should not have been modified");
 	}
-
 }
 TEST_END
 
@@ -216,5 +222,6 @@ main(void)
 	    test_nstime_imultiply,
 	    test_nstime_idivide,
 	    test_nstime_divide,
+	    test_nstime_monotonic,
 	    test_nstime_update));
 }