diff options
| author | Finomnis <Finomnis@users.noreply.github.com> | 2024-04-11 00:00:38 +0200 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2024-04-10 22:00:38 +0000 |
| commit | 8c23e178f3838bcdd13662a2ffefd39ec144e869 (patch) | |
| tree | f2d2cefcd6bb2876e74ee6035b5489a4a2d9590f /rtic-time | |
| parent | e4cc5fd17b8a2df332af0ee25c8bd7092e66afb0 (diff) | |
Monotonic rewrite (#874)
* Rework timer_queue and monotonic architecture
Goals:
* make Monotonic purely internal
* make Monotonic purely tick passed, no fugit involved
* create a wrapper struct in the user's code via a macro that then
converts the "now" from the tick based monotonic to a fugit based
timestamp
We need to proxy the delay functions of the timer queue anyway,
so we could simply perform the conversion in those proxy functions.
* Update cargo.lock
* Update readme of rtic-time
* CI: ESP32: Redact esp_image: Too volatile
* Fixup: Changelog double entry rebase mistake
---------
Co-authored-by: Henrik Tjäder <henrik@tjaders.com>
Diffstat (limited to 'rtic-time')
| -rw-r--r-- | rtic-time/CHANGELOG.md | 9 | ||||
| -rw-r--r-- | rtic-time/Cargo.toml | 10 | ||||
| -rw-r--r-- | rtic-time/README.md | 29 | ||||
| -rw-r--r-- | rtic-time/src/lib.rs | 301 | ||||
| -rw-r--r-- | rtic-time/src/monotonic.rs | 240 | ||||
| -rw-r--r-- | rtic-time/src/monotonic/embedded_hal_macros.rs | 77 | ||||
| -rw-r--r-- | rtic-time/src/monotonic/timer_queue_based_monotonic.rs | 113 | ||||
| -rw-r--r-- | rtic-time/src/timer_queue.rs | 281 | ||||
| -rw-r--r-- | rtic-time/src/timer_queue/backend.rs | 44 | ||||
| -rw-r--r-- | rtic-time/src/timer_queue/tick_type.rs | 49 | ||||
| -rw-r--r-- | rtic-time/tests/delay_precision_subtick.rs | 101 | ||||
| -rw-r--r-- | rtic-time/tests/timer_queue.rs | 194 |
12 files changed, 754 insertions, 694 deletions
diff --git a/rtic-time/CHANGELOG.md b/rtic-time/CHANGELOG.md index f3c9792..197c426 100644 --- a/rtic-time/CHANGELOG.md +++ b/rtic-time/CHANGELOG.md @@ -5,11 +5,18 @@ This project adheres to [Semantic Versioning](http://semver.org/). For each category, *Added*, *Changed*, *Fixed* add new entries at the top! -## Unreleased +## Unreleased - v2.0.0 + ### Added ### Changed +- Full rewrite of the `Monotonic` API. + - Now split into multiple traits: + - `Monotonic` - A user-facing trait that defines what the functionality of a monotonic is. + - `TimerQueueBackend` - The set of functionality a backend must provide in order to be used with the `TimerQueue`. + - `TimerQueue` is now purely based on ticks and has no concept of real time. + - The `TimerQueueBasedMonotonic` trait implements a `Monotonic` based on a `TimerQueueBackend`, translating ticks into `Instant` and `Duration`. ### Fixed diff --git a/rtic-time/Cargo.toml b/rtic-time/Cargo.toml index 4ad91cd..93d3224 100644 --- a/rtic-time/Cargo.toml +++ b/rtic-time/Cargo.toml @@ -1,6 +1,6 @@ [package] name = "rtic-time" -version = "1.3.0" +version = "2.0.0" edition = "2021" authors = [ @@ -11,7 +11,7 @@ authors = [ "Per Lindgren <per.lindgren@ltu.se>", ] categories = ["concurrency", "embedded", "no-std", "asynchronous"] -description = "rtic-time lib TODO" +description = "Basic definitions and utilities that can be used to keep track of time" license = "MIT OR Apache-2.0" repository = "https://github.com/rtic-rs/rtic" @@ -21,11 +21,11 @@ repository = "https://github.com/rtic-rs/rtic" critical-section = "1" futures-util = { version = "0.3.25", default-features = false } rtic-common = { version = "1.0.0", path = "../rtic-common" } +embedded-hal = { version = "1.0.0" } +embedded-hal-async = { version = "1.0.0" } +fugit = "0.3.7" [dev-dependencies] -embedded-hal = { version = "1.0" } -embedded-hal-async = { version = "1.0" } -fugit = "0.3.7" parking_lot = "0.12" cassette = "0.2" cooked-waker = "5.0.0" diff --git a/rtic-time/README.md b/rtic-time/README.md new file mode 100644 index 0000000..53c2944 --- /dev/null +++ b/rtic-time/README.md @@ -0,0 +1,29 @@ +# rtic-time + +Basic definitions and utilities that can be used to keep track of time. + +[](https://crates.io/crates/rtic-time) +[](https://docs.rs/rtic-time) +[](https://matrix.to/#/#rtic:matrix.org) + + +## Content + +The main contribution of this crate is to define the [`Monotonic`](https://docs.rs/rtic-time/latest/rtic_time/trait.Monotonic.html) trait. It serves as a standardized interface for libraries to interact with the system's monotonic timers. + +Additionally, this crate provides tools and utilities that help with implementing monotonic timers. + +## Implementations of the `Monotonic` trait + +For implementations of [`Monotonic`](https://docs.rs/rtic-time/latest/rtic_time/trait.Monotonic.html) +on various hardware, see [`rtic-monotonics`](https://docs.rs/rtic-monotonics/). + + +## Chat + +Join us and talk about RTIC in the [Matrix room][matrix-room]. + +Weekly meeting minutes can be found over at [RTIC HackMD][hackmd]. + +[matrix-room]: https://matrix.to/#/#rtic:matrix.org +[hackmd]: https://rtic.rs/meeting diff --git a/rtic-time/src/lib.rs b/rtic-time/src/lib.rs index 9cd20d5..7b051da 100644 --- a/rtic-time/src/lib.rs +++ b/rtic-time/src/lib.rs @@ -5,285 +5,60 @@ #![no_std] #![deny(missing_docs)] -#![allow(incomplete_features)] - -use core::future::{poll_fn, Future}; -use core::pin::Pin; -use core::sync::atomic::{AtomicBool, AtomicUsize, Ordering}; -use core::task::{Poll, Waker}; -use futures_util::{ - future::{select, Either}, - pin_mut, -}; -use linked_list::{Link, LinkedList}; -pub use monotonic::Monotonic; -use rtic_common::dropper::OnDrop; +#![allow(async_fn_in_trait)] pub mod half_period_counter; mod linked_list; -mod monotonic; - -/// Holds a waker and at which time instant this waker shall be awoken. -struct WaitingWaker<Mono: Monotonic> { - waker: Waker, - release_at: Mono::Instant, - was_popped: AtomicBool, -} - -impl<Mono: Monotonic> Clone for WaitingWaker<Mono> { - fn clone(&self) -> Self { - Self { - waker: self.waker.clone(), - release_at: self.release_at, - was_popped: AtomicBool::new(self.was_popped.load(Ordering::Relaxed)), - } - } -} - -impl<Mono: Monotonic> PartialEq for WaitingWaker<Mono> { - fn eq(&self, other: &Self) -> bool { - self.release_at == other.release_at - } -} - -impl<Mono: Monotonic> PartialOrd for WaitingWaker<Mono> { - fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> { - self.release_at.partial_cmp(&other.release_at) - } -} - -/// A generic timer queue for async executors. -/// -/// # Blocking -/// -/// The internal priority queue uses global critical sections to manage access. This means that -/// `await`ing a delay will cause a lock of the entire system for O(n) time. In practice the lock -/// duration is ~10 clock cycles per element in the queue. -/// -/// # Safety -/// -/// This timer queue is based on an intrusive linked list, and by extension the links are strored -/// on the async stacks of callers. The links are deallocated on `drop` or when the wait is -/// complete. -/// -/// Do not call `mem::forget` on an awaited future, or there will be dragons! -pub struct TimerQueue<Mono: Monotonic> { - queue: LinkedList<WaitingWaker<Mono>>, - initialized: AtomicBool, -} +pub mod monotonic; +pub mod timer_queue; /// This indicates that there was a timeout. pub struct TimeoutError; -/// This is needed to make the async closure in `delay_until` accept that we "share" -/// the link possible between threads. -struct LinkPtr<Mono: Monotonic>(*mut Option<linked_list::Link<WaitingWaker<Mono>>>); - -impl<Mono: Monotonic> Clone for LinkPtr<Mono> { - fn clone(&self) -> Self { - LinkPtr(self.0) - } -} - -impl<Mono: Monotonic> LinkPtr<Mono> { - /// This will dereference the pointer stored within and give out an `&mut`. - unsafe fn get(&mut self) -> &mut Option<linked_list::Link<WaitingWaker<Mono>>> { - &mut *self.0 - } -} - -unsafe impl<Mono: Monotonic> Send for LinkPtr<Mono> {} -unsafe impl<Mono: Monotonic> Sync for LinkPtr<Mono> {} - -impl<Mono: Monotonic> TimerQueue<Mono> { - /// Make a new queue. - pub const fn new() -> Self { - Self { - queue: LinkedList::new(), - initialized: AtomicBool::new(false), - } - } - - /// Forwards the `Monotonic::now()` method. - #[inline(always)] - pub fn now(&self) -> Mono::Instant { - Mono::now() - } - - /// Takes the initialized monotonic to initialize the TimerQueue. - pub fn initialize(&self, monotonic: Mono) { - self.initialized.store(true, Ordering::SeqCst); - - // Don't run drop on `Mono` - core::mem::forget(monotonic); - } +/// Re-export for macros +pub use embedded_hal; +/// Re-export for macros +pub use embedded_hal_async; - /// Call this in the interrupt handler of the hardware timer supporting the `Monotonic` +/// # A monotonic clock / counter definition. +/// +/// ## Correctness +/// +/// The trait enforces that proper time-math is implemented between `Instant` and `Duration`. This +/// is a requirement on the time library that the user chooses to use. +pub trait Monotonic { + /// The type for instant, defining an instant in time. /// - /// # Safety + /// **Note:** In all APIs in RTIC that use instants from this monotonic, this type will be used. + type Instant: Ord + + Copy + + core::ops::Add<Self::Duration, Output = Self::Instant> + + core::ops::Sub<Self::Duration, Output = Self::Instant> + + core::ops::Sub<Self::Instant, Output = Self::Duration>; + + /// The type for duration, defining a duration of time. /// - /// It's always safe to call, but it must only be called from the interrupt of the - /// monotonic timer for correct operation. - pub unsafe fn on_monotonic_interrupt(&self) { - Mono::clear_compare_flag(); - Mono::on_interrupt(); - - loop { - let mut release_at = None; - let head = self.queue.pop_if(|head| { - release_at = Some(head.release_at); - - let should_pop = Mono::now() >= head.release_at; - head.was_popped.store(should_pop, Ordering::Relaxed); + /// **Note:** In all APIs in RTIC that use duration from this monotonic, this type will be used. + type Duration: Copy; - should_pop - }); + /// Get the current time. + fn now() -> Self::Instant; - match (head, release_at) { - (Some(link), _) => { - link.waker.wake(); - } - (None, Some(instant)) => { - Mono::enable_timer(); - Mono::set_compare(instant); + /// Delay for some duration of time. + async fn delay(duration: Self::Duration); - if Mono::now() >= instant { - // The time for the next instant passed while handling it, - // continue dequeueing - continue; - } - - break; - } - (None, None) => { - // Queue is empty - Mono::disable_timer(); - - break; - } - } - } - } + /// Delay to some specific time instant. + async fn delay_until(instant: Self::Instant); /// Timeout at a specific time. - pub async fn timeout_at<F: Future>( - &self, - instant: Mono::Instant, + async fn timeout_at<F: core::future::Future>( + instant: Self::Instant, future: F, - ) -> Result<F::Output, TimeoutError> { - let delay = self.delay_until(instant); + ) -> Result<F::Output, TimeoutError>; - pin_mut!(future); - pin_mut!(delay); - - match select(future, delay).await { - Either::Left((r, _)) => Ok(r), - Either::Right(_) => Err(TimeoutError), - } - } - - /// Timeout after at least a specific duration. - #[inline] - pub async fn timeout_after<F: Future>( - &self, - duration: Mono::Duration, + /// Timeout after a specific duration. + async fn timeout_after<F: core::future::Future>( + duration: Self::Duration, future: F, - ) -> Result<F::Output, TimeoutError> { - let now = Mono::now(); - let mut timeout = now + duration; - if now != timeout { - timeout = timeout + Mono::TICK_PERIOD; - } - - // Wait for one period longer, because by definition timers have an uncertainty - // of one period, so waiting for 'at least' needs to compensate for that. - self.timeout_at(timeout, future).await - } - - /// Delay for at least some duration of time. - #[inline] - pub async fn delay(&self, duration: Mono::Duration) { - let now = Mono::now(); - let mut timeout = now + duration; - if now != timeout { - timeout = timeout + Mono::TICK_PERIOD; - } - - // Wait for one period longer, because by definition timers have an uncertainty - // of one period, so waiting for 'at least' needs to compensate for that. - self.delay_until(timeout).await; - } - - /// Delay to some specific time instant. - pub async fn delay_until(&self, instant: Mono::Instant) { - if !self.initialized.load(Ordering::Relaxed) { - panic!( - "The timer queue is not initialized with a monotonic, you need to run `initialize`" - ); - } - - let mut link_ptr: Option<linked_list::Link<WaitingWaker<Mono>>> = None; - - // Make this future `Drop`-safe - // SAFETY(link_ptr): Shadow the original definition of `link_ptr` so we can't abuse it. - let mut link_ptr = - LinkPtr(&mut link_ptr as *mut Option<linked_list::Link<WaitingWaker<Mono>>>); - let mut link_ptr2 = link_ptr.clone(); - - let queue = &self.queue; - let marker = &AtomicUsize::new(0); - - let dropper = OnDrop::new(|| { - queue.delete(marker.load(Ordering::Relaxed)); - }); - - poll_fn(|cx| { - if Mono::now() >= instant { - return Poll::Ready(()); - } - - // SAFETY: This pointer is only dereferenced here and on drop of the future - // which happens outside this `poll_fn`'s stack frame, so this mutable access cannot - // happen at the same time as `dropper` runs. - let link = unsafe { link_ptr2.get() }; - if link.is_none() { - let link_ref = link.insert(Link::new(WaitingWaker { - waker: cx.waker().clone(), - release_at: instant, - was_popped: AtomicBool::new(false), - })); - - // SAFETY(new_unchecked): The address to the link is stable as it is defined - //outside this stack frame. - // SAFETY(insert): `link_ref` lifetime comes from `link_ptr` that is shadowed, and - // we make sure in `dropper` that the link is removed from the queue before - // dropping `link_ptr` AND `dropper` makes sure that the shadowed `link_ptr` lives - // until the end of the stack frame. - let (head_updated, addr) = unsafe { queue.insert(Pin::new_unchecked(link_ref)) }; - - marker.store(addr, Ordering::Relaxed); - - if head_updated { - // Pend the monotonic handler if the queue head was updated. - Mono::pend_interrupt() - } - } - - Poll::Pending - }) - .await; - - // SAFETY: We only run this and dereference the pointer if we have - // exited the `poll_fn` below in the `drop(dropper)` call. The other dereference - // of this pointer is in the `poll_fn`. - if let Some(link) = unsafe { link_ptr.get() } { - if link.val.was_popped.load(Ordering::Relaxed) { - // If it was popped from the queue there is no need to run delete - dropper.defuse(); - } - } else { - // Make sure that our link is deleted from the list before we drop this stack - drop(dropper); - } - } + ) -> Result<F::Output, TimeoutError>; } diff --git a/rtic-time/src/monotonic.rs b/rtic-time/src/monotonic.rs index e6a160d..7c9d915 100644 --- a/rtic-time/src/monotonic.rs +++ b/rtic-time/src/monotonic.rs @@ -1,236 +1,8 @@ -//! A monotonic clock / counter definition. +//! Structs and traits surrounding the [`Monotonic`](crate::Monotonic) trait. -/// # A monotonic clock / counter definition. -/// -/// ## Correctness -/// -/// The trait enforces that proper time-math is implemented between `Instant` and `Duration`. This -/// is a requirement on the time library that the user chooses to use. -pub trait Monotonic { - /// The time at time zero. - const ZERO: Self::Instant; +pub use timer_queue_based_monotonic::{ + TimerQueueBasedDuration, TimerQueueBasedInstant, TimerQueueBasedMonotonic, +}; - /// The duration between two timer ticks. - const TICK_PERIOD: Self::Duration; - - /// The type for instant, defining an instant in time. - /// - /// **Note:** In all APIs in RTIC that use instants from this monotonic, this type will be used. - type Instant: Ord - + Copy - + core::ops::Add<Self::Duration, Output = Self::Instant> - + core::ops::Sub<Self::Duration, Output = Self::Instant> - + core::ops::Sub<Self::Instant, Output = Self::Duration>; - - /// The type for duration, defining an duration of time. - /// - /// **Note:** In all APIs in RTIC that use duration from this monotonic, this type will be used. - type Duration; - - /// Get the current time. - fn now() -> Self::Instant; - - /// Set the compare value of the timer interrupt. - /// - /// **Note:** This method does not need to handle race conditions of the monotonic, the timer - /// queue in RTIC checks this. - fn set_compare(instant: Self::Instant); - - /// This method used to be required by an errata workaround - /// for the nrf52 family, but it has been disabled as the - /// workaround was erroneous. - #[deprecated( - since = "1.2.0", - note = "this method is erroneous and has been disabled" - )] - fn should_dequeue_check(_: Self::Instant) -> bool { - panic!("This method should not be used as it is erroneous.") - } - - /// Clear the compare interrupt flag. - fn clear_compare_flag(); - - /// Pend the timer's interrupt. - fn pend_interrupt(); - - /// Optional. Runs on interrupt before any timer queue handling. - fn on_interrupt() {} - - /// Optional. This is used to save power, this is called when the timer queue is not empty. - /// - /// Enabling and disabling the monotonic needs to propagate to `now` so that an instant - /// based of `now()` is still valid. - /// - /// NOTE: This may be called more than once. - fn enable_timer() {} - - /// Optional. This is used to save power, this is called when the timer queue is empty. - /// - /// Enabling and disabling the monotonic needs to propagate to `now` so that an instant - /// based of `now()` is still valid. - /// - /// NOTE: This may be called more than once. - fn disable_timer() {} -} - -/// Creates impl blocks for [`embedded_hal::delay::DelayNs`][DelayNs], -/// based on [`fugit::ExtU64Ceil`][ExtU64Ceil]. -/// -/// [DelayNs]: https://docs.rs/embedded-hal/latest/embedded_hal/delay/trait.DelayNs.html -/// [ExtU64Ceil]: https://docs.rs/fugit/latest/fugit/trait.ExtU64Ceil.html -#[macro_export] -macro_rules! embedded_hal_delay_impl_fugit64 { - ($t:ty) => { - impl ::embedded_hal::delay::DelayNs for $t { - fn delay_ns(&mut self, ns: u32) { - use ::fugit::ExtU64Ceil; - - let now = Self::now(); - let mut done = now + u64::from(ns).nanos_at_least(); - if now != done { - // Compensate for sub-tick uncertainty - done += Self::TICK_PERIOD; - } - - while Self::now() < done {} - } - - fn delay_us(&mut self, us: u32) { - use ::fugit::ExtU64Ceil; - - let now = Self::now(); - let mut done = now + u64::from(us).micros_at_least(); - if now != done { - // Compensate for sub-tick uncertainty - done += Self::TICK_PERIOD; - } - - while Self::now() < done {} - } - - fn delay_ms(&mut self, ms: u32) { - use ::fugit::ExtU64Ceil; - - let now = Self::now(); - let mut done = now + u64::from(ms).millis_at_least(); - if now != done { - // Compensate for sub-tick uncertainty - done += Self::TICK_PERIOD; - } - - while Self::now() < done {} - } - } - }; -} - -/// Creates impl blocks for [`embedded_hal_async::delay::DelayNs`][DelayNs], -/// based on [`fugit::ExtU64Ceil`][ExtU64Ceil]. -/// -/// [DelayNs]: https://docs.rs/embedded-hal-async/latest/embedded_hal_async/delay/trait.DelayNs.html -/// [ExtU64Ceil]: https://docs.rs/fugit/latest/fugit/trait.ExtU64Ceil.html -#[macro_export] -macro_rules! embedded_hal_async_delay_impl_fugit64 { - ($t:ty) => { - impl ::embedded_hal_async::delay::DelayNs for $t { - #[inline] - async fn delay_ns(&mut self, ns: u32) { - use ::fugit::ExtU64Ceil; - Self::delay(u64::from(ns).nanos_at_least()).await; - } - - #[inline] - async fn delay_us(&mut self, us: u32) { - use ::fugit::ExtU64Ceil; - Self::delay(u64::from(us).micros_at_least()).await; - } - - #[inline] - async fn delay_ms(&mut self, ms: u32) { - use ::fugit::ExtU64Ceil; - Self::delay(u64::from(ms).millis_at_least()).await; - } - } - }; -} - -/// Creates impl blocks for [`embedded_hal::delay::DelayNs`][DelayNs], -/// based on [`fugit::ExtU32Ceil`][ExtU32Ceil]. -/// -/// [DelayNs]: https://docs.rs/embedded-hal/latest/embedded_hal/delay/trait.DelayNs.html -/// [ExtU32Ceil]: https://docs.rs/fugit/latest/fugit/trait.ExtU32Ceil.html -#[macro_export] -macro_rules! embedded_hal_delay_impl_fugit32 { - ($t:ty) => { - impl ::embedded_hal::delay::DelayNs for $t { - fn delay_ns(&mut self, ns: u32) { - use ::fugit::ExtU32Ceil; - - let now = Self::now(); - let mut done = now + ns.nanos_at_least(); - if now != done { - // Compensate for sub-tick uncertainty - done += Self::TICK_PERIOD; - } - - while Self::now() < done {} - } - - fn delay_us(&mut self, us: u32) { - use ::fugit::ExtU32Ceil; - - let now = Self::now(); - let mut done = now + us.micros_at_least(); - if now != done { - // Compensate for sub-tick uncertainty - done += Self::TICK_PERIOD; - } - - while Self::now() < done {} - } - - fn delay_ms(&mut self, ms: u32) { - use ::fugit::ExtU32Ceil; - - let now = Self::now(); - let mut done = now + ms.millis_at_least(); - if now != done { - // Compensate for sub-tick uncertainty - done += Self::TICK_PERIOD; - } - - while Self::now() < done {} - } - } - }; -} - -/// Creates impl blocks for [`embedded_hal_async::delay::DelayNs`][DelayNs], -/// based on [`fugit::ExtU32Ceil`][ExtU32Ceil]. -/// -/// [DelayNs]: https://docs.rs/embedded-hal-async/latest/embedded_hal_async/delay/trait.DelayNs.html -/// [ExtU32Ceil]: https://docs.rs/fugit/latest/fugit/trait.ExtU32Ceil.html -#[macro_export] -macro_rules! embedded_hal_async_delay_impl_fugit32 { - ($t:ty) => { - impl ::embedded_hal_async::delay::DelayNs for $t { - #[inline] - async fn delay_ns(&mut self, ns: u32) { - use ::fugit::ExtU32Ceil; - Self::delay(ns.nanos_at_least()).await; - } - - #[inline] - async fn delay_us(&mut self, us: u32) { - use ::fugit::ExtU32Ceil; - Self::delay(us.micros_at_least()).await; - } - - #[inline] - async fn delay_ms(&mut self, ms: u32) { - use ::fugit::ExtU32Ceil; - Self::delay(ms.millis_at_least()).await; - } - } - }; -} +mod embedded_hal_macros; +mod timer_queue_based_monotonic; diff --git a/rtic-time/src/monotonic/embedded_hal_macros.rs b/rtic-time/src/monotonic/embedded_hal_macros.rs new file mode 100644 index 0000000..25ac791 --- /dev/null +++ b/rtic-time/src/monotonic/embedded_hal_macros.rs @@ -0,0 +1,77 @@ +//! Macros that implement embedded-hal traits for Monotonics + +/// Implements [`embedded_hal::delay::DelayNs`] for a given monotonic. +#[macro_export] +macro_rules! impl_embedded_hal_delay_fugit { + ($t:ty) => { + impl $crate::embedded_hal::delay::DelayNs for $t { + fn delay_ns(&mut self, ns: u32) { + let now = <Self as $crate::Monotonic>::now(); + let mut done = + now + <Self as $crate::Monotonic>::Duration::nanos_at_least(ns.into()); + if now != done { + // Compensate for sub-tick uncertainty + done = done + <Self as $crate::Monotonic>::Duration::from_ticks(1); + } + + while <Self as $crate::Monotonic>::now() < done {} + } + + fn delay_us(&mut self, us: u32) { + let now = <Self as $crate::Monotonic>::now(); + let mut done = + now + <Self as $crate::Monotonic>::Duration::micros_at_least(us.into()); + if now != done { + // Compensate for sub-tick uncertainty + done = done + <Self as $crate::Monotonic>::Duration::from_ticks(1); + } + + while <Self as $crate::Monotonic>::now() < done {} + } + + fn delay_ms(&mut self, ms: u32) { + let now = <Self as $crate::Monotonic>::now(); + let mut done = + now + <Self as $crate::Monotonic>::Duration::millis_at_least(ms.into()); + if now != done { + // Compensate for sub-tick uncertainty + done = done + <Self as $crate::Monotonic>::Duration::from_ticks(1); + } + + while <Self as $crate::Monotonic>::now() < done {} + } + } + }; +} + +/// Implements [`embedded_hal_async::delay::DelayNs`] for a given monotonic. +#[macro_export] +macro_rules! impl_embedded_hal_async_delay_fugit { + ($t:ty) => { + impl $crate::embedded_hal_async::delay::DelayNs for $t { + #[inline] + async fn delay_ns(&mut self, ns: u32) { + <Self as $crate::Monotonic>::delay( + <Self as $crate::Monotonic>::Duration::nanos_at_least(ns.into()), + ) + .await; + } + + #[inline] + async fn delay_us(&mut self, us: u32) { + <Self as $crate::Monotonic>::delay( + <Self as $crate::Monotonic>::Duration::micros_at_least(us.into()), + ) + .await; + } + + #[inline] + async fn delay_ms(&mut self, ms: u32) { + <Self as $crate::Monotonic>::delay( + <Self as $crate::Monotonic>::Duration::millis_at_least(ms.into()), + ) + .await; + } + } + }; +} diff --git a/rtic-time/src/monotonic/timer_queue_based_monotonic.rs b/rtic-time/src/monotonic/timer_queue_based_monotonic.rs new file mode 100644 index 0000000..699958b --- /dev/null +++ b/rtic-time/src/monotonic/timer_queue_based_monotonic.rs @@ -0,0 +1,113 @@ +use crate::{timer_queue::TimerQueueBackend, TimeoutError}; + +use crate::Monotonic; + +/// A [`Monotonic`] that is backed by the [`TimerQueue`](crate::timer_queue::TimerQueue). +pub trait TimerQueueBasedMonotonic { + /// The backend for the timer queue + type Backend: TimerQueueBackend; + + /// The type for instant, defining an instant in time. + /// + /// **Note:** In all APIs in RTIC that use instants from this monotonic, this type will be used. + type Instant: TimerQueueBasedInstant<Ticks = <Self::Backend as TimerQueueBackend>::Ticks> + + core::ops::Add<Self::Duration, Output = Self::Instant> + + core::ops::Sub<Self::Duration, Output = Self::Instant> + + core::ops::Sub<Self::Instant, Output = Self::Duration>; + + /// The type for duration, defining a duration of time. + /// + /// **Note:** In all APIs in RTIC that use duration from this monotonic, this type will be used. + type Duration: TimerQueueBasedDuration<Ticks = <Self::Backend as TimerQueueBackend>::Ticks>; +} + +impl<T: TimerQueueBasedMonotonic> Monotonic for T { + type Instant = T::Instant; + type Duration = T::Duration; + + fn now() -> Self::Instant { + Self::Instant::from_ticks(T::Backend::timer_queue().now()) + } + + async fn delay(duration: Self::Duration) { + T::Backend::timer_queue().delay(duration.ticks()).await + } + + async fn delay_until(instant: Self::Instant) { + T::Backend::timer_queue().delay_until(instant.ticks()).await + } + + async fn timeout_at<F: core::future::Future>( + instant: Self::Instant, + future: F, + ) -> Result<F::Output, TimeoutError> { + T::Backend::timer_queue() + .timeout_at(instant.ticks(), future) + .await + } + + async fn timeout_after<F: core::future::Future>( + duration: Self::Duration, + future: F, + ) -> Result<F::Output, TimeoutError> { + T::Backend::timer_queue() + .timeout_after(duration.ticks(), future) + .await + } +} + +/// An instant that can be used in [`TimerQueueBasedMonotonic`]. +pub trait TimerQueueBasedInstant: Ord + Copy { + /// The internal type of the instant + type Ticks; + /// Convert from ticks to the instant + fn from_ticks(ticks: Self::Ticks) -> Self; + /// Convert the instant to ticks + fn ticks(self) -> Self::Ticks; +} + +/// A duration that can be used in [`TimerQueueBasedMonotonic`]. +pub trait TimerQueueBasedDuration: Copy { + /// The internal type of the duration + type Ticks; + /// Convert the duration to ticks + fn ticks(self) -> Self::Ticks; +} + +impl<const NOM: u32, const DENOM: u32> TimerQueueBasedInstant for fugit::Instant<u64, NOM, DENOM> { + type Ticks = u64; + fn from_ticks(ticks: Self::Ticks) -> Self { + Self::from_ticks(ticks) + } + fn ticks(self) -> Self::Ticks { + Self::ticks(&self) + } +} + +impl<const NOM: u32, const DENOM: u32> TimerQueueBasedInstant for fugit::Instant<u32, NOM, DENOM> { + type Ticks = u32; + fn from_ticks(ticks: Self::Ticks) -> Self { + Self::from_ticks(ticks) + } + fn ticks(self) -> Self::Ticks { + Self::ticks(&self) + } +} + +impl<const NOM: u32, const DENOM: u32> TimerQueueBasedDuration + for fugit::Duration<u64, NOM, DENOM> +{ + type Ticks = u64; + fn ticks(self) -> Self::Ticks { + Self::ticks(&self) + } +} + +impl<const NOM: u32, const DENOM: u32> TimerQueueBasedDuration + for fugit::Duration<u32, NOM, DENOM> +{ + type Ticks = u32; + fn ticks(self) -> Self::Ticks { + Self::ticks(&self) + } +} diff --git a/rtic-time/src/timer_queue.rs b/rtic-time/src/timer_queue.rs new file mode 100644 index 0000000..ea2c806 --- /dev/null +++ b/rtic-time/src/timer_queue.rs @@ -0,0 +1,281 @@ +//! A generic timer queue for async executors. + +use crate::linked_list::{self, Link, LinkedList}; +use crate::TimeoutError; + +use core::future::{poll_fn, Future}; +use core::pin::Pin; +use core::sync::atomic::{AtomicBool, AtomicUsize, Ordering}; +use core::task::{Poll, Waker}; +use futures_util::{ + future::{select, Either}, + pin_mut, +}; +use rtic_common::dropper::OnDrop; + +mod backend; +mod tick_type; +pub use backend::TimerQueueBackend; +pub use tick_type::TimerQueueTicks; + +/// Holds a waker and at which time instant this waker shall be awoken. +struct WaitingWaker<Backend: TimerQueueBackend> { + waker: Waker, + release_at: Backend::Ticks, + was_popped: AtomicBool, +} + +impl<Backend: TimerQueueBackend> Clone for WaitingWaker<Backend> { + fn clone(&self) -> Self { + Self { + waker: self.waker.clone(), + release_at: self.release_at, + was_popped: AtomicBool::new(self.was_popped.load(Ordering::Relaxed)), + } + } +} + +impl<Backend: TimerQueueBackend> PartialEq for WaitingWaker<Backend> { + fn eq(&self, other: &Self) -> bool { + self.release_at == other.release_at + } +} + +impl<Backend: TimerQueueBackend> PartialOrd for WaitingWaker<Backend> { + fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> { + Some(self.release_at.compare(other.release_at)) + } +} + +/// A generic timer queue for async executors. +/// +/// # Blocking +/// +/// The internal priority queue uses global critical sections to manage access. This means that +/// `await`ing a delay will cause a lock of the entire system for O(n) time. In practice the lock +/// duration is ~10 clock cycles per element in the queue. +/// +/// # Safety +/// +/// This timer queue is based on an intrusive linked list, and by extension the links are stored +/// on the async stacks of callers. The links are deallocated on `drop` or when the wait is +/// complete. +/// +/// Do not call `mem::forget` on an awaited future, or there will be dragons! +pub struct TimerQueue<Backend: TimerQueueBackend> { + queue: LinkedList<WaitingWaker<Backend>>, + initialized: AtomicBool, +} + +/// This is needed to make the async closure in `delay_until` accept that we "share" +/// the link possible between threads. +struct LinkPtr<Backend: TimerQueueBackend>(*mut Option<linked_list::Link<WaitingWaker<Backend>>>); + +impl<Backend: TimerQueueBackend> Clone for LinkPtr<Backend> { + fn clone(&self) -> Self { + LinkPtr(self.0) + } +} + +impl<Backend: TimerQueueBackend> LinkPtr<Backend> { + /// This will dereference the pointer stored within and give out an `&mut`. + unsafe fn get(&mut self) -> &mut Option<linked_list::Link<WaitingWaker<Backend>>> { + &mut *self.0 + } +} + +unsafe impl<Backend: TimerQueueBackend> Send for LinkPtr<Backend> {} +unsafe impl<Backend: TimerQueueBackend> Sync for LinkPtr<Backend> {} + +impl<Backend: TimerQueueBackend> TimerQueue<Backend> { + /// Make a new queue. + pub const fn new() -> Self { + Self { + queue: LinkedList::new(), + initialized: AtomicBool::new(false), + } + } + + /// Forwards the `Monotonic::now()` method. + #[inline(always)] + pub fn now(&self) -> Backend::Ticks { + Backend::now() + } + + /// Takes the initialized monotonic to initialize the TimerQueue. + pub fn initialize(&self, backend: Backend) { + self.initialized.store(true, Ordering::SeqCst); + + // Don't run drop on `Mono` + core::mem::forget(backend); + } + + /// Call this in the interrupt handler of the hardware timer supporting the `Monotonic` + /// + /// # Safety + /// + /// It's always safe to call, but it must only be called from the interrupt of the + /// monotonic timer for correct operation. + pub unsafe fn on_monotonic_interrupt(&self) { + Backend::clear_compare_flag(); + Backend::on_interrupt(); + + loop { + let mut release_at = None; + let head = self.queue.pop_if(|head| { + release_at = Some(head.release_at); + + let should_pop = Backend::now().is_at_least(head.release_at); + head.was_popped.store(should_pop, Ordering::Relaxed); + + should_pop + }); + + match (head, release_at) { + (Some(link), _) => { + link.waker.wake(); + } + (None, Some(instant)) => { + Backend::enable_timer(); + Backend::set_compare(instant); + + if Backend::now().is_at_least(instant) { + // The time for the next instant passed while handling it, + // continue dequeueing + continue; + } + + break; + } + (None, None) => { + // Queue is empty + Backend::disable_timer(); + + break; + } + } + } + } + + /// Timeout at a specific time. + pub async fn timeout_at<F: Future>( + &self, + instant: Backend::Ticks, + future: F, + ) -> Result<F::Output, TimeoutError> { + let delay = self.delay_until(instant); + + pin_mut!(future); + pin_mut!(delay); + + match select(future, delay).await { + Either::Left((r, _)) => Ok(r), + Either::Right(_) => Err(TimeoutError), + } + } + + /// Timeout after at least a specific duration. + #[inline] + pub async fn timeout_after<F: Future>( + &self, + duration: Backend::Ticks, + future: F, + ) -> Result<F::Output, TimeoutError> { + let now = Backend::now(); + let mut timeout = now.wrapping_add(duration); + if now != timeout { + timeout = timeout.wrapping_add(Backend::Ticks::ONE_TICK); + } + + // Wait for one period longer, because by definition timers have an uncertainty + // of one period, so waiting for 'at least' needs to compensate for that. + self.timeout_at(timeout, future).await + } + + /// Delay for at least some duration of time. + #[inline] + pub async fn delay(&self, duration: Backend::Ticks) { + let now = Backend::now(); + let mut timeout = now.wrapping_add(duration); + if now != timeout { + timeout = timeout.wrapping_add(Backend::Ticks::ONE_TICK); + } + + // Wait for one period longer, because by definition timers have an uncertainty + // of one period, so waiting for 'at least' needs to compensate for that. + self.delay_until(timeout).await; + } + + /// Delay to some specific time instant. + pub async fn delay_until(&self, instant: Backend::Ticks) { + if !self.initialized.load(Ordering::Relaxed) { + panic!( + "The timer queue is not initialized with a monotonic, you need to run `initialize`" + ); + } + + let mut link_ptr: Option<linked_list::Link<WaitingWaker<Backend>>> = None; + + // Make this future `Drop`-safe + // SAFETY(link_ptr): Shadow the original definition of `link_ptr` so we can't abuse it. + let mut link_ptr = + LinkPtr(&mut link_ptr as *mut Option<linked_list::Link<WaitingWaker<Backend>>>); + let mut link_ptr2 = link_ptr.clone(); + + let queue = &self.queue; + let marker = &AtomicUsize::new(0); + + let dropper = OnDrop::new(|| { + queue.delete(marker.load(Ordering::Relaxed)); + }); + + poll_fn(|cx| { + if Backend::now().is_at_least(instant) { + return Poll::Ready(()); + } + + // SAFETY: This pointer is only dereferenced here and on drop of the future + // which happens outside this `poll_fn`'s stack frame, so this mutable access cannot + // happen at the same time as `dropper` runs. + let link = unsafe { link_ptr2.get() }; + if link.is_none() { + let link_ref = link.insert(Link::new(WaitingWaker { + waker: cx.waker().clone(), + release_at: instant, + was_popped: AtomicBool::new(false), + })); + + // SAFETY(new_unchecked): The address to the link is stable as it is defined + //outside this stack frame. + // SAFETY(insert): `link_ref` lifetime comes from `link_ptr` that is shadowed, and + // we make sure in `dropper` that the link is removed from the queue before + // dropping `link_ptr` AND `dropper` makes sure that the shadowed `link_ptr` lives + // until the end of the stack frame. + let (head_updated, addr) = unsafe { queue.insert(Pin::new_unchecked(link_ref)) }; + + marker.store(addr, Ordering::Relaxed); + + if head_updated { + // Pend the monotonic handler if the queue head was updated. + Backend::pend_interrupt() + } + } + + Poll::Pending + }) + .await; + + // SAFETY: We only run this and dereference the pointer if we have + // exited the `poll_fn` below in the `drop(dropper)` call. The other dereference + // of this pointer is in the `poll_fn`. + if let Some(link) = unsafe { link_ptr.get() } { + if link.val.was_popped.load(Ordering::Relaxed) { + // If it was popped from the queue there is no need to run delete + dropper.defuse(); + } + } else { + // Make sure that our link is deleted from the list before we drop this stack + drop(dropper); + } + } +} diff --git a/rtic-time/src/timer_queue/backend.rs b/rtic-time/src/timer_queue/backend.rs new file mode 100644 index 0000000..5b71b7c --- /dev/null +++ b/rtic-time/src/timer_queue/backend.rs @@ -0,0 +1,44 @@ +use super::{TimerQueue, TimerQueueTicks}; + +/// A backend definition for a monotonic clock/counter. +pub trait TimerQueueBackend: 'static + Sized { + /// The type for ticks. + type Ticks: TimerQueueTicks; + + /// Get the current time. + fn now() -> Self::Ticks; + + /// Set the compare value of the timer interrupt. + /// + /// **Note:** This method does not need to handle race conditions of the monotonic, the timer + /// queue in RTIC checks this. + fn set_compare(instant: Self::Ticks); + + /// Clear the compare interrupt flag. + fn clear_compare_flag(); + + /// Pend the timer's interrupt. + fn pend_interrupt(); + + /// Optional. Runs on interrupt before any timer queue handling. + fn on_interrupt() {} + + /// Optional. This is used to save power, this is called when the timer queue is not empty. + /// + /// Enabling and disabling the monotonic needs to propagate to `now` so that an instant + /// based of `now()` is still valid. + /// + /// NOTE: This may be called more than once. + fn enable_timer() {} + + /// Optional. This is used to save power, this is called when the timer queue is empty. + /// + /// Enabling and disabling the monotonic needs to propagate to `now` so that an instant + /// based of `now()` is still valid. + /// + /// NOTE: This may be called more than once. + fn disable_timer() {} + + /// Returns a reference to the underlying timer queue. + fn timer_queue() -> &'static TimerQueue<Self>; +} diff --git a/rtic-time/src/timer_queue/tick_type.rs b/rtic-time/src/timer_queue/tick_type.rs new file mode 100644 index 0000000..571dfc2 --- /dev/null +++ b/rtic-time/src/timer_queue/tick_type.rs @@ -0,0 +1,49 @@ +use core::cmp; + +/// The ticks of a timer. +pub trait TimerQueueTicks: Copy + PartialEq + Eq { + /// Represents a single tick. + const ONE_TICK: Self; + + /// Compares to another tick count. + /// + /// Takes into account timer wrapping; if the difference is more than + /// half the value range, the result will be flipped. + fn compare(self, other: Self) -> cmp::Ordering; + + /// True if `self` is at the same time as `other` or later. + /// + /// Takes into account timer wrapping; if the difference is more than + /// half the value range, the result will be negated. + fn is_at_least(self, other: Self) -> bool { + match self.compare(other) { + cmp::Ordering::Less => false, + cmp::Ordering::Equal => true, + cmp::Ordering::Greater => true, + } + } + + /// Wrapping addition. + fn wrapping_add(self, other: Self) -> Self; +} + +impl TimerQueueTicks for u32 { + const ONE_TICK: Self = 1; + + fn compare(self, other: Self) -> cmp::Ordering { + (self.wrapping_sub(other) as i32).cmp(&0) + } + fn wrapping_add(self, other: Self) -> Self { + u32::wrapping_add(self, other) + } +} +impl TimerQueueTicks for u64 { + const ONE_TICK: Self = 1; + + fn compare(self, other: Self) -> cmp::Ordering { + (self.wrapping_sub(other) as i64).cmp(&0) + } + fn wrapping_add(self, other: Self) -> Self { + u64::wrapping_add(self, other) + } +} diff --git a/rtic-time/tests/delay_precision_subtick.rs b/rtic-time/tests/delay_precision_subtick.rs index a4ef4bb..a415b65 100644 --- a/rtic-time/tests/delay_precision_subtick.rs +++ b/rtic-time/tests/delay_precision_subtick.rs @@ -15,46 +15,31 @@ use std::{ time::Duration, }; -use ::fugit::ExtU64Ceil; use cooked_waker::{IntoWaker, WakeRef}; +use fugit::ExtU64Ceil; use parking_lot::Mutex; -use rtic_time::{Monotonic, TimeoutError, TimerQueue}; +use rtic_time::{ + monotonic::TimerQueueBasedMonotonic, + timer_queue::{TimerQueue, TimerQueueBackend}, + Monotonic, +}; const SUBTICKS_PER_TICK: u32 = 10; struct SubtickTestTimer; -static TIMER_QUEUE: TimerQueue<SubtickTestTimer> = TimerQueue::new(); +struct SubtickTestTimerBackend; +static TIMER_QUEUE: TimerQueue<SubtickTestTimerBackend> = TimerQueue::new(); static NOW_SUBTICKS: AtomicU64 = AtomicU64::new(0); static COMPARE_TICKS: Mutex<Option<u64>> = Mutex::new(None); -impl Monotonic for SubtickTestTimer { - const ZERO: Self::Instant = Self::Instant::from_ticks(0); - const TICK_PERIOD: Self::Duration = Self::Duration::from_ticks(1); - - type Instant = fugit::Instant<u64, SUBTICKS_PER_TICK, 1000>; - type Duration = fugit::Duration<u64, SUBTICKS_PER_TICK, 1000>; - - fn now() -> Self::Instant { - Self::Instant::from_ticks( - NOW_SUBTICKS.load(Ordering::Relaxed) / u64::from(SUBTICKS_PER_TICK), - ) - } - - fn set_compare(instant: Self::Instant) { - *COMPARE_TICKS.lock() = Some(instant.ticks()); - } - - fn clear_compare_flag() {} - - fn pend_interrupt() { - unsafe { - Self::__tq().on_monotonic_interrupt(); - } +impl SubtickTestTimer { + pub fn init() { + SubtickTestTimerBackend::init(); } } -impl SubtickTestTimer { - pub fn init() { - Self::__tq().initialize(Self) +impl SubtickTestTimerBackend { + fn init() { + Self::timer_queue().initialize(Self) } pub fn tick() -> u64 { @@ -70,7 +55,7 @@ impl SubtickTestTimer { // ); if subticks == 0 && Some(ticks) == *compare { unsafe { - Self::__tq().on_monotonic_interrupt(); + Self::timer_queue().on_monotonic_interrupt(); } } @@ -85,29 +70,41 @@ impl SubtickTestTimer { pub fn now_subticks() -> u64 { NOW_SUBTICKS.load(Ordering::Relaxed) } +} - fn __tq() -> &'static TimerQueue<Self> { - &TIMER_QUEUE +impl TimerQueueBackend for SubtickTestTimerBackend { + type Ticks = u64; + + fn now() -> Self::Ticks { + NOW_SUBTICKS.load(Ordering::Relaxed) / u64::from(SUBTICKS_PER_TICK) } - /// Delay for some duration of time. - #[inline] - pub async fn delay(duration: <Self as Monotonic>::Duration) { - Self::__tq().delay(duration).await; + fn set_compare(instant: Self::Ticks) { + *COMPARE_TICKS.lock() = Some(instant); } - /// Timeout after a specific duration. - #[inline] - pub async fn timeout_after<F: core::future::Future>( - duration: <Self as Monotonic>::Duration, - future: F, - ) -> Result<F::Output, TimeoutError> { - Self::__tq().timeout_after(duration, future).await + fn clear_compare_flag() {} + + fn pend_interrupt() { + unsafe { + Self::timer_queue().on_monotonic_interrupt(); + } } + + fn timer_queue() -> &'static TimerQueue<Self> { + &TIMER_QUEUE + } +} + +impl TimerQueueBasedMonotonic for SubtickTestTimer { + type Backend = SubtickTestTimerBackend; + + type Instant = fugit::Instant<u64, SUBTICKS_PER_TICK, 1000>; + type Duration = fugit::Duration<u64, SUBTICKS_PER_TICK, 1000>; } -rtic_time::embedded_hal_delay_impl_fugit64!(SubtickTestTimer); -rtic_time::embedded_hal_async_delay_impl_fugit64!(SubtickTestTimer); +rtic_time::impl_embedded_hal_delay_fugit!(SubtickTestTimer); +rtic_time::impl_embedded_hal_async_delay_fugit!(SubtickTestTimer); // A simple struct that counts the number of times it is awoken. Can't // be awoken by value (because that would discard the counter), so we @@ -144,7 +141,7 @@ impl<F: FnOnce()> Drop for OnDrop<F> { macro_rules! subtick_test { (@run $start:expr, $actual_duration:expr, $delay_fn:expr) => {{ // forward clock to $start - SubtickTestTimer::forward_to_subtick($start); + SubtickTestTimerBackend::forward_to_subtick($start); // call wait function let delay_fn = $delay_fn; @@ -164,7 +161,7 @@ macro_rules! subtick_test { }; assert_eq!(wakecounter.get(), 0); - SubtickTestTimer::tick(); + SubtickTestTimerBackend::tick(); } let expected_wakeups = { @@ -177,7 +174,7 @@ macro_rules! subtick_test { assert_eq!(wakecounter.get(), expected_wakeups); // Tick again to test that we don't get a second wake - SubtickTestTimer::tick(); + SubtickTestTimerBackend::tick(); assert_eq!(wakecounter.get(), expected_wakeups); assert_eq!( @@ -191,9 +188,9 @@ macro_rules! subtick_test { (@run_blocking $start:expr, $actual_duration:expr, $delay_fn:expr) => {{ // forward clock to $start - SubtickTestTimer::forward_to_subtick($start); + SubtickTestTimerBackend::forward_to_subtick($start); - let t_start = SubtickTestTimer::now_subticks(); + let t_start = SubtickTestTimerBackend::now_subticks(); let finished = AtomicBool::new(false); std::thread::scope(|s|{ @@ -204,13 +201,13 @@ macro_rules! subtick_test { s.spawn(||{ sleep(Duration::from_millis(10)); while !finished.load(Ordering::Relaxed) { - SubtickTestTimer::tick(); + SubtickTestTimerBackend::tick(); sleep(Duration::from_millis(10)); } }); }); - let t_end = SubtickTestTimer::now_subticks(); + let t_end = SubtickTestTimerBackend::now_subticks(); let measured_duration = t_end - t_start; assert_eq!( $actual_duration, diff --git a/rtic-time/tests/timer_queue.rs b/rtic-time/tests/timer_queue.rs index 8bae385..2ef7ce3 100644 --- a/rtic-time/tests/timer_queue.rs +++ b/rtic-time/tests/timer_queue.rs @@ -2,63 +2,24 @@ //! //! To run this test, you need to activate the `critical-section/std` feature. -use std::{ - fmt::Debug, - task::{Poll, Waker}, -}; - use cassette::Cassette; use parking_lot::Mutex; -use rtic_time::{Monotonic, TimerQueue}; - -static NOW: Mutex<Option<Instant>> = Mutex::new(None); - -#[derive(PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Debug)] -pub struct Duration(u64); - -impl Duration { - pub const fn from_ticks(millis: u64) -> Self { - Self(millis) - } - - pub fn as_ticks(&self) -> u64 { - self.0 - } -} - -impl core::ops::Add<Duration> for Duration { - type Output = Duration; - - fn add(self, rhs: Duration) -> Self::Output { - Self(self.0 + rhs.0) - } -} +use rtic_time::timer_queue::{TimerQueue, TimerQueueBackend}; -impl From<Duration> for Instant { - fn from(value: Duration) -> Self { - Instant(value.0) - } -} - -static WAKERS: Mutex<Vec<Waker>> = Mutex::new(Vec::new()); +mod peripheral { + use parking_lot::Mutex; + use std::{ + sync::atomic::{AtomicU64, Ordering}, + task::{Poll, Waker}, + }; -#[derive(PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Debug)] -pub struct Instant(u64); + use super::TestMonoBackend; -impl Instant { - const ZERO: Self = Self(0); + static NOW: AtomicU64 = AtomicU64::new(0); + static WAKERS: Mutex<Vec<Waker>> = Mutex::new(Vec::new()); pub fn tick() -> bool { - // If we've never ticked before, initialize the clock. - if NOW.lock().is_none() { - *NOW.lock() = Some(Instant::ZERO); - } - // We've ticked before, add one to the clock - else { - let now = Instant::now(); - let new_time = now + Duration(1); - *NOW.lock() = Some(new_time); - } + NOW.fetch_add(1, Ordering::Release); let had_wakers = !WAKERS.lock().is_empty(); // Wake up all things waiting for a specific time to happen. @@ -66,22 +27,18 @@ impl Instant { waker.wake_by_ref(); } - let had_interrupt = TestMono::tick(false); + let had_interrupt = TestMonoBackend::tick(false); had_interrupt || had_wakers } - pub fn now() -> Self { - NOW.lock().clone().unwrap_or(Instant::ZERO) + pub fn now() -> u64 { + NOW.load(Ordering::Acquire) } - pub fn elapsed(&self) -> Duration { - Duration(Self::now().0 - self.0) - } - - pub async fn wait_until(time: Instant) { + pub async fn wait_until(time: u64) { core::future::poll_fn(|ctx| { - if Instant::now() >= time { + if now() >= time { Poll::Ready(()) } else { WAKERS.lock().push(ctx.waker().clone()); @@ -92,51 +49,21 @@ impl Instant { } } -impl From<u64> for Instant { - fn from(value: u64) -> Self { - Self(value) - } -} +static COMPARE: Mutex<Option<u64>> = Mutex::new(None); +static TIMER_QUEUE: TimerQueue<TestMonoBackend> = TimerQueue::new(); -impl core::ops::Add<Duration> for Instant { - type Output = Instant; +pub struct TestMonoBackend; - fn add(self, rhs: Duration) -> Self::Output { - Self(self.0 + rhs.0) - } -} - -impl core::ops::Sub<Duration> for Instant { - type Output = Instant; - - fn sub(self, rhs: Duration) -> Self::Output { - Self(self.0 - rhs.0) - } -} - -impl core::ops::Sub<Instant> for Instant { - type Output = Duration; - - fn sub(self, rhs: Instant) -> Self::Output { - Duration(self.0 - rhs.0) - } -} - -static COMPARE: Mutex<Option<Instant>> = Mutex::new(None); -static TIMER_QUEUE: TimerQueue<TestMono> = TimerQueue::new(); - -pub struct TestMono; - -impl TestMono { +impl TestMonoBackend { pub fn tick(force_interrupt: bool) -> bool { - let now = Instant::now(); + let now = peripheral::now(); let compare_reached = Some(now) == Self::compare(); let interrupt = compare_reached || force_interrupt; if interrupt { unsafe { - TestMono::queue().on_monotonic_interrupt(); + TestMonoBackend::timer_queue().on_monotonic_interrupt(); } true } else { @@ -144,35 +71,26 @@ impl TestMono { } } - /// Initialize the monotonic. - pub fn init() { - Self::queue().initialize(Self); - } - - /// Used to access the underlying timer queue - pub fn queue() -> &'static TimerQueue<TestMono> { - &TIMER_QUEUE - } - - pub fn compare() -> Option<Instant> { + pub fn compare() -> Option<u64> { COMPARE.lock().clone() } } -impl Monotonic for TestMono { - const ZERO: Self::Instant = Instant::ZERO; - const TICK_PERIOD: Self::Duration = Duration::from_ticks(1); - - type Instant = Instant; +impl TestMonoBackend { + fn init() { + Self::timer_queue().initialize(Self); + } +} - type Duration = Duration; +impl TimerQueueBackend for TestMonoBackend { + type Ticks = u64; - fn now() -> Self::Instant { - Instant::now() + fn now() -> Self::Ticks { + peripheral::now() } - fn set_compare(instant: Self::Instant) { - let _ = COMPARE.lock().insert(instant); + fn set_compare(instant: Self::Ticks) { + *COMPARE.lock() = Some(instant); } fn clear_compare_flag() {} @@ -180,42 +98,40 @@ impl Monotonic for TestMono { fn pend_interrupt() { Self::tick(true); } + + fn timer_queue() -> &'static TimerQueue<Self> { + &TIMER_QUEUE + } } #[test] fn timer_queue() { - TestMono::init(); - let start = Instant::ZERO; + TestMonoBackend::init(); + let start = 0; let build_delay_test = |pre_delay: Option<u64>, delay: u64| { - let delay = Duration::from_ticks(delay); - let pre_delay = pre_delay.map(Duration::from_ticks); - let total = if let Some(pre_delay) = pre_delay { pre_delay + delay } else { delay }; - let total_millis = total.as_ticks(); async move { // A `pre_delay` simulates a delay in scheduling, // without the `pre_delay` being present in the timer // queue if let Some(pre_delay) = pre_delay { - Instant::wait_until(start + pre_delay).await; + peripheral::wait_until(start + pre_delay).await; } - TestMono::queue().delay(delay).await; + TestMonoBackend::timer_queue().delay(delay).await; - let elapsed = start.elapsed().as_ticks(); - println!("{total_millis} ticks delay reached after {elapsed} ticks"); + let elapsed = peripheral::now() - start; + println!("{total} ticks delay reached after {elapsed} ticks"); // Expect a delay of one longer, to compensate for timer uncertainty - if elapsed != total_millis + 1 { - panic!( - "{total_millis} ticks delay was not on time ({elapsed} ticks passed instead)" - ); + if elapsed != total + 1 { + panic!("{total} ticks delay was not on time ({elapsed} ticks passed instead)"); } } }; @@ -259,31 +175,31 @@ fn timer_queue() { // We only poll the waiting futures if an // interrupt occured or if an artificial delay // has passed. - if Instant::tick() { + if peripheral::tick() { poll!(d1, d2, d3); } - if Instant::now() == 0.into() { + if peripheral::now() == 0 { // First, we want to be waiting for our 300 tick delay - assert_eq!(TestMono::compare(), Some(301.into())); + assert_eq!(TestMonoBackend::compare(), Some(301)); } - if Instant::now() == 100.into() { + if peripheral::now() == 100 { // After 100 ticks, we enqueue a new delay that is supposed to last // until the 200-tick-mark - assert_eq!(TestMono::compare(), Some(201.into())); + assert_eq!(TestMonoBackend::compare(), Some(201)); } - if Instant::now() == 201.into() { + if peripheral::now() == 201 { // After 200 ticks, we dequeue the 200-tick-mark delay and // requeue the 300 tick delay - assert_eq!(TestMono::compare(), Some(301.into())); + assert_eq!(TestMonoBackend::compare(), Some(301)); } - if Instant::now() == 301.into() { + if peripheral::now() == 301 { // After 300 ticks, we dequeue the 300-tick-mark delay and // go to the 400 tick delay that is already enqueued - assert_eq!(TestMono::compare(), Some(401.into())); + assert_eq!(TestMonoBackend::compare(), Some(401)); } } |
