3 files changed, 122 insertions, 12 deletions
diff --git a/library/std/src/time.rs b/library/std/src/time.rs
index 6d70c7270d3..ec105f231e5 100644
--- a/library/std/src/time.rs
+++ b/library/std/src/time.rs
@@ -12,15 +12,14 @@
 
 #![stable(feature = "time", since = "1.3.0")]
 
+mod monotonic;
 #[cfg(test)]
 mod tests;
 
-use crate::cmp;
 use crate::error::Error;
 use crate::fmt;
 use crate::ops::{Add, AddAssign, Sub, SubAssign};
 use crate::sys::time;
-use crate::sys_common::mutex::StaticMutex;
 use crate::sys_common::FromInner;
 
 #[stable(feature = "time", since = "1.3.0")]
@@ -249,14 +248,7 @@ impl Instant {
             return Instant(os_now);
         }
 
-        static LOCK: StaticMutex = StaticMutex::new();
-        static mut LAST_NOW: time::Instant = time::Instant::zero();
-        unsafe {
-            let _lock = LOCK.lock();
-            let now = cmp::max(LAST_NOW, os_now);
-            LAST_NOW = now;
-            Instant(now)
-        }
+        Instant(monotonic::monotonize(os_now))
     }
 
     /// Returns the amount of time elapsed from another instant to this one.
diff --git a/library/std/src/time/monotonic.rs b/library/std/src/time/monotonic.rs
new file mode 100644
index 00000000000..4f79b670a3a
--- /dev/null
+++ b/library/std/src/time/monotonic.rs
@@ -0,0 +1,93 @@
+use crate::sys::time;
+
+#[inline]
+pub(super) fn monotonize(raw: time::Instant) -> time::Instant {
+    inner::monotonize(raw)
+}
+
+#[cfg(all(target_has_atomic = "64", not(target_has_atomic = "128")))]
+pub mod inner {
+    use crate::sync::atomic::AtomicU64;
+    use crate::sync::atomic::Ordering::*;
+    use crate::sys::time;
+    use crate::time::Duration;
+
+    const ZERO: time::Instant = time::Instant::zero();
+
+    // bits 30 and 31 are never used since the seconds part never exceeds 10^9
+    const UNINITIALIZED: u64 = 0xff00_0000;
+    static MONO: AtomicU64 = AtomicU64::new(UNINITIALIZED);
+
+    #[inline]
+    pub(super) fn monotonize(raw: time::Instant) -> time::Instant {
+        let delta = raw.checked_sub_instant(&ZERO).unwrap();
+        let secs = delta.as_secs();
+        // occupies no more than 30 bits (10^9 seconds)
+        let nanos = delta.subsec_nanos() as u64;
+
+        // This wraps around every 136 years (2^32 seconds).
+        // To detect backsliding we use wrapping arithmetic and declare forward steps smaller
+        // than 2^31 seconds as expected and everything else as a backslide which will be
+        // monotonized.
+        // This could be a problem for programs that call instants at intervals greater
+        // than 68 years. Interstellar probes may want to ensure that actually_monotonic() is true.
+        let packed = (secs << 32) | nanos;
+        let old = MONO.load(Relaxed);
+
+        if packed == UNINITIALIZED || packed.wrapping_sub(old) < u64::MAX / 2 {
+            MONO.store(packed, Relaxed);
+            raw
+        } else {
+            // Backslide occurred. We reconstruct monotonized time by assuming the clock will never
+            // backslide more than 2`32 seconds which means we can reuse the upper 32bits from
+            // the seconds.
+            let secs = (secs & 0xffff_ffff << 32) | old >> 32;
+            let nanos = old as u32;
+            ZERO.checked_add_duration(&Duration::new(secs, nanos)).unwrap()
+        }
+    }
+}
+
+#[cfg(target_has_atomic = "128")]
+pub mod inner {
+    use crate::sync::atomic::AtomicU128;
+    use crate::sync::atomic::Ordering::*;
+    use crate::sys::time;
+    use crate::time::Duration;
+
+    const ZERO: time::Instant = time::Instant::zero();
+    static MONO: AtomicU128 = AtomicU128::new(0);
+
+    #[inline]
+    pub(super) fn monotonize(raw: time::Instant) -> time::Instant {
+        let delta = raw.checked_sub_instant(&ZERO).unwrap();
+        // Split into seconds and nanos since Duration doesn't have a
+        // constructor that takes an u128
+        let secs = delta.as_secs() as u128;
+        let nanos = delta.subsec_nanos() as u128;
+        let timestamp: u128 = secs << 64 | nanos;
+        let timestamp = MONO.fetch_max(timestamp, Relaxed).max(timestamp);
+        let secs = (timestamp >> 64) as u64;
+        let nanos = timestamp as u32;
+        ZERO.checked_add_duration(&Duration::new(secs, nanos)).unwrap()
+    }
+}
+
+#[cfg(not(any(target_has_atomic = "64", target_has_atomic = "128")))]
+pub mod inner {
+    use crate::cmp;
+    use crate::sys::time;
+    use crate::sys_common::mutex::StaticMutex;
+
+    #[inline]
+    pub(super) fn monotonize(os_now: time::Instant) -> time::Instant {
+        static LOCK: StaticMutex = StaticMutex::new();
+        static mut LAST_NOW: time::Instant = time::Instant::zero();
+        unsafe {
+            let _lock = LOCK.lock();
+            let now = cmp::max(LAST_NOW, os_now);
+            LAST_NOW = now;
+            now
+        }
+    }
+}
diff --git a/library/std/src/time/tests.rs b/library/std/src/time/tests.rs
index 20c813fdc70..c5c8f192768 100644
--- a/library/std/src/time/tests.rs
+++ b/library/std/src/time/tests.rs
@@ -13,8 +13,33 @@ macro_rules! assert_almost_eq {
 #[test]
 fn instant_monotonic() {
     let a = Instant::now();
-    let b = Instant::now();
-    assert!(b >= a);
+    loop {
+        let b = Instant::now();
+        assert!(b >= a);
+        if b > a {
+            break;
+        }
+    }
+}
+
+#[test]
+fn instant_monotonic_concurrent() -> crate::thread::Result<()> {
+    let threads: Vec<_> = (0..8)
+        .map(|_| {
+            crate::thread::spawn(|| {
+                let mut old = Instant::now();
+                for _ in 0..5_000_000 {
+                    let new = Instant::now();
+                    assert!(new >= old);
+                    old = new;
+                }
+            })
+        })
+        .collect();
+    for t in threads {
+        t.join()?;
+    }
+    Ok(())
 }
 
 #[test]