sched_clock/

lib.rs

//! Representations of time needed by task scheduling algorithms
//!
//! For the purpose of task scheduling, we represent time as a 64-bit signed
//! count of nanoseconds before or after some reference (such as system startup,
//! scheduler startup...). This seems appropriate as of 2019 because:
//!
//! - CPU frequencies are currently capped at a few GHz by thermal limits, and
//!   no known physics can help us evade those limits, so a nanosecond is likely
//!   to remain a few CPU cycles for a while. Which is enough precision for any
//!   practical scheduling purpose, because the scheduler itself will take more
//!   time to execute / have more jitter than that.
//! - 2^63 nanoseconds is a bit less than 300 years, and as of 2019 humans are
//!   not capable of planning work several centuries ahead or work that will
//!   take several centuries to complete. Not to mention that this code will
//!   likely become obsolete on a much smaller timescale, of course.
//!
//! We're largely reimplementing `std::time::{Duration, Instant}` here, because
//! while we like its overall API design...
//!
//! - We do not need the huge dynamic range of std::time (~600 years is enough
//!   for us). And we expect to manipulate time often and under tight
//!   performance constraints, so we need all the extra processing speed and
//!   storage savings that we can get.
//! - We want freedom to switch to OS- or hardware-provided facilities that give
//!   us either more correctness, more speed, or both, whereas the standard
//!   library puts portability and simplicity above everything else.
//! - We find signed durations and instants to be useful and worth supporting.

#![deny(missing_docs)]

pub mod clocks;
pub mod prelude;

use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign};

pub use crate::clocks::{Clock, DefaultClock};

/// Points in time
///
/// Instants (aka timestamps) are encoded as a number of nanoseconds
/// since/before some epoch, and can be measured using a Clock.
///
/// There are many possible choices of epoch, including process startup time,
/// system startup time, and UTC references. The choice of epoch is specific to
/// a given Clock implementation, and _may_ be spelled out in that Clock's
/// documentation when the implementor knows about it.
///
#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct Instant(i64);
//
impl Instant {
    /// Instants are defined relatively to an epoch
    pub const EPOCH: Self = Self(0);

    /// "Minus infinity" instant, as far away in the past as representable
    pub const FOREVER_AGO: Self = Self(i64::min_value());

    /// "Plus infinity" instant, as far away in the future as representable
    pub const SOMEDAY: Self = Self(i64::max_value());
}

/// Algebraic (signed) durations
///
/// Represents a span of wall-clock time, the difference between two instants.
/// May be negative to represent going backwards in time.
///
#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct Duration(i64);
//
impl Duration {
    /// One nanosecond, i.e. one billionth of a second
    pub const NANOSECOND: Self = Self(1);

    /// One microsecond, i.e. one millionth of a second
    pub const MICROSECOND: Self = Self(1000 * Self::NANOSECOND.0);

    /// One millisecond, i.e. one thousandth of a second
    pub const MILLISECOND: Self = Self(1000 * Self::MICROSECOND.0);

    /// One second
    pub const SECOND: Self = Self(1000 * Self::MILLISECOND.0);

    /// One minute
    pub const MINUTE: Self = Self(60 * Self::SECOND.0);

    /// One hour
    pub const HOUR: Self = Self(60 * Self::MINUTE.0);

    // NOTE: We can't go beyond that because...
    //       - Not all days are 24 hours (see: daylight saving times)
    //       - Not all months are 30 days
    //       - The duration of a year is a pain to spell out, and rarely useful

    /// "Infinity" duration, as long as representable
    pub const FOREVER: Self = Self(i64::max_value());

    /// Create a new Duration from a number of nanoseconds
    pub const fn from_nanos(nanos: i64) -> Self {
        Self(nanos)
    }

    /// Turn into a number of signed integer nanoseconds
    pub const fn as_nanos(self) -> i64 {
        self.0
    }
}

// Basic arithmetic operations
impl Add<Duration> for Instant {
    type Output = Instant;

    fn add(self, rhs: Duration) -> Instant {
        Instant(self.0 + rhs.0)
    }
}
//
impl Add<Duration> for Duration {
    type Output = Duration;

    fn add(self, rhs: Duration) -> Duration {
        Duration(self.0 + rhs.0)
    }
}
//
impl Div<i64> for Duration {
    type Output = Duration;

    fn div(self, rhs: i64) -> Duration {
        Duration(self.0 / rhs)
    }
}
//
impl Mul<Duration> for i64 {
    type Output = Duration;

    fn mul(self, rhs: Duration) -> Duration {
        Duration(self * rhs.0)
    }
}
//
impl Mul<i64> for Duration {
    type Output = Duration;

    fn mul(self, rhs: i64) -> Duration {
        Duration(self.0 * rhs)
    }
}
//
impl Neg for Duration {
    type Output = Duration;

    fn neg(self) -> Duration {
        Duration(-self.0)
    }
}
//
impl Sub<Duration> for Instant {
    type Output = Instant;

    fn sub(self, rhs: Duration) -> Instant {
        Instant(self.0 - rhs.0)
    }
}
//
impl Sub<Duration> for Duration {
    type Output = Duration;

    fn sub(self, rhs: Duration) -> Duration {
        Duration(self.0 - rhs.0)
    }
}
//
impl Sub<Instant> for Instant {
    type Output = Duration;

    fn sub(self, rhs: Instant) -> Duration {
        Duration(self.0 - rhs.0)
    }
}

// In-place arithmetic operations
impl AddAssign<Duration> for Instant {
    fn add_assign(&mut self, other: Duration) {
        self.0 += other.0;
    }
}
//
impl AddAssign<Duration> for Duration {
    fn add_assign(&mut self, other: Duration) {
        self.0 += other.0;
    }
}
//
impl DivAssign<i64> for Duration {
    fn div_assign(&mut self, other: i64) {
        self.0 /= other
    }
}
//
impl MulAssign<i64> for Duration {
    fn mul_assign(&mut self, other: i64) {
        self.0 *= other;
    }
}
//
impl SubAssign<Duration> for Duration {
    fn sub_assign(&mut self, other: Duration) {
        self.0 -= other.0;
    }
}
//
impl SubAssign<Duration> for Instant {
    fn sub_assign(&mut self, other: Duration) {
        self.0 -= other.0;
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use quickcheck::{Arbitrary, Gen};
    use quickcheck_macros::quickcheck;
    use std::convert::TryInto;

    /// "Minus infinity" is useful in tests, but I'm not sure if we want to expose it yet
    const MINUS_FOREVER: Duration = Duration(i64::min_value());

    // Traditional special-case testing

    #[test]
    /// Associated consts of Instant
    fn special_instants() {
        // Simple ordering test
        assert!(Instant::FOREVER_AGO < Instant::EPOCH);
        assert!(Instant::FOREVER_AGO < Instant::SOMEDAY);
        assert!(Instant::EPOCH < Instant::SOMEDAY);

        // Relationships between infinite instants and infinite durations
        assert_eq!(Instant::SOMEDAY - Instant::EPOCH, Duration::FOREVER);
        assert_eq!(Instant::FOREVER_AGO - Instant::EPOCH, MINUS_FOREVER);
    }

    #[test]
    /// Associated consts of Duration
    fn special_durations() {
        // We don't really _need_ these properties, but we use them in tests
        assert_eq!(Duration::default(), Duration(0));
        assert_eq!(Duration::NANOSECOND, Duration(1));

        // Nanosecond should validate usual properties
        assert!(Duration::NANOSECOND > Duration(0));
        assert_eq!(Duration::NANOSECOND, Duration::from_nanos(1));
        assert_eq!(Duration::NANOSECOND.as_nanos(), 1);

        // Left-Mul should work and validate usual relationships
        assert_eq!(Duration::MICROSECOND, 1000 * Duration::NANOSECOND);
        assert_eq!(Duration::MILLISECOND, 1000 * Duration::MICROSECOND);
        assert_eq!(Duration::SECOND, 1000 * Duration::MILLISECOND);
        assert_eq!(Duration::MINUTE, 60 * Duration::SECOND);
        assert_eq!(Duration::HOUR, 60 * Duration::MINUTE);

        // Infinity is far, far away
        assert!(Duration::HOUR < Duration::FOREVER);
    }

    // Property-based testing

    impl Arbitrary for Duration {
        fn arbitrary<G: Gen>(g: &mut G) -> Self {
            Duration(<i64 as Arbitrary>::arbitrary::<G>(g))
        }
    }

    impl Arbitrary for Instant {
        fn arbitrary<G: Gen>(g: &mut G) -> Self {
            Instant(<i64 as Arbitrary>::arbitrary::<G>(g))
        }
    }

    #[quickcheck]
    /// Properties shared by all Duration
    fn duration_properties(d: Duration) -> bool {
        // These properties should always hold
        let mut dt0 = d;
        dt0 *= 0;
        let mut dt1 = d;
        dt1 *= 1;
        let mut dd1 = d;
        dd1 /= 1;
        let always_check = d >= MINUS_FOREVER
            && d <= Duration::FOREVER
            && 0 * d == Duration::default()
            && d * 0 == 0 * d
            && dt0 == 0 * d
            && 1 * d == d
            && d * 1 == 1 * d
            && dt1 == 1 * d
            && d / 1 == d
            && dd1 == d / 1
            && Duration::from_nanos(d.as_nanos()) == d;

        // Since -{signed}::min_value() doesn't exist, we must special-case
        // before testing properties of the negation
        if d == MINUS_FOREVER {
            return always_check;
        }
        let mut dtm1 = d;
        dtm1 *= -1;
        let mut ddm1 = d;
        ddm1 /= -1;
        (-d != d || d.as_nanos() == 0)
            && (-1) * d == -d
            && d * (-1) == -d
            && d / (-1) == -d
            && dtm1 == -d
            && ddm1 == -d
            && -(-d) == d
    }

    #[quickcheck]
    /// Properties shared by all (Duration, Duration) pairs
    fn duration_duration_properties(d1: Duration, d2: Duration) -> bool {
        let sum = (i128::from(d1.as_nanos()) + i128::from(d2.as_nanos()))
            .try_into()
            .map(Duration::from_nanos);
        let sum_test = if let Ok(sum) = sum {
            let mut d1p2 = d1;
            d1p2 += d2;
            d1 + d2 == sum && d1p2 == d1 + d2
        } else {
            true
        };

        let diff = (i128::from(d1.as_nanos()) - i128::from(d2.as_nanos()))
            .try_into()
            .map(Duration::from_nanos);
        let diff_test = if let Ok(diff) = diff {
            let mut d1m2 = d1;
            d1m2 -= d2;
            d1 - d2 == diff && d1m2 == d1 - d2
        } else {
            true
        };

        sum_test && diff_test
    }

    #[quickcheck]
    /// Properties shared by all (Duration, i64) pairs
    fn duration_i64_properties(d: Duration, i: i64) -> bool {
        let mul = (i128::from(d.as_nanos()) * i128::from(i))
            .try_into()
            .map(Duration::from_nanos);
        let mul_test = if let Ok(mul) = mul {
            let mut dti = d;
            dti *= i;
            d * i == mul && i * d == d * i && dti == d * i
        } else {
            true
        };

        if i == 0 {
            return mul_test;
        }
        let div = (i128::from(d.as_nanos()) / i128::from(i))
            .try_into()
            .map(Duration::from_nanos);
        let div_test = if let Ok(div) = div {
            let mut doi = d;
            doi /= i;
            d / i == div && doi == d / i
        } else {
            true
        };

        mul_test && div_test
    }

    #[quickcheck]
    /// Properties shared by all Instants
    fn instant_properties(i: Instant) -> bool {
        i >= Instant::FOREVER_AGO && i <= Instant::SOMEDAY
    }

    #[quickcheck]
    /// Properties shared by all (Instant, Duration) pairs
    fn instant_duration_properties(i: Instant, d: Duration) -> bool {
        let sum = (i128::from(i.0) + i128::from(d.as_nanos()))
            .try_into()
            .map(Instant);
        let sum_test = if let Ok(sum) = sum {
            let mut ipd = i;
            ipd += d;
            i + d == sum && ipd == i + d
        } else {
            true
        };

        let diff = (i128::from(i.0) - i128::from(d.as_nanos()))
            .try_into()
            .map(Instant);
        let diff_test = if let Ok(diff) = diff {
            let mut imd = i;
            imd -= d;
            i - d == diff && imd == i - d
        } else {
            true
        };

        sum_test && diff_test
    }

    #[quickcheck]
    /// Properties shared by all (Instant, Instant) pairs
    fn instant_instant_properties(i1: Instant, i2: Instant) -> bool {
        let diff = (i128::from(i1.0) - i128::from(i2.0))
            .try_into()
            .map(Duration::from_nanos);
        if let Ok(diff) = diff {
            i1 - i2 == diff
        } else {
            true
        }
    }
}