aboutsummaryrefslogtreecommitdiff
path: root/rtic-time
diff options
context:
space:
mode:
Diffstat (limited to 'rtic-time')
-rw-r--r--rtic-time/.gitignore6
-rw-r--r--rtic-time/CHANGELOG.md16
-rw-r--r--rtic-time/Cargo.toml22
-rw-r--r--rtic-time/rust-toolchain.toml4
-rw-r--r--rtic-time/src/lib.rs273
-rw-r--r--rtic-time/src/linked_list.rs182
-rw-r--r--rtic-time/src/monotonic.rs60
7 files changed, 563 insertions, 0 deletions
diff --git a/rtic-time/.gitignore b/rtic-time/.gitignore
new file mode 100644
index 0000000..c400256
--- /dev/null
+++ b/rtic-time/.gitignore
@@ -0,0 +1,6 @@
+**/*.rs.bk
+.#*
+.gdb_history
+/target
+Cargo.lock
+*.hex
diff --git a/rtic-time/CHANGELOG.md b/rtic-time/CHANGELOG.md
new file mode 100644
index 0000000..d3a9d84
--- /dev/null
+++ b/rtic-time/CHANGELOG.md
@@ -0,0 +1,16 @@
+# Change Log
+
+All notable changes to this project will be documented in this file.
+This project adheres to [Semantic Versioning](http://semver.org/).
+
+For each category, *Added*, *Changed*, *Fixed* add new entries at the top!
+
+## [Unreleased]
+
+### Added
+
+### Changed
+
+### Fixed
+
+## [v1.0.0] - 2023-xx-xx
diff --git a/rtic-time/Cargo.toml b/rtic-time/Cargo.toml
new file mode 100644
index 0000000..c7d13bb
--- /dev/null
+++ b/rtic-time/Cargo.toml
@@ -0,0 +1,22 @@
+[package]
+name = "rtic-time"
+version = "1.0.0-alpha.0"
+
+edition = "2021"
+authors = [
+ "The Real-Time Interrupt-driven Concurrency developers",
+ "Emil Fresk <emil.fresk@gmail.com>",
+ "Henrik Tjäder <henrik@tjaders.com>",
+ "Jorge Aparicio <jorge@japaric.io>",
+ "Per Lindgren <per.lindgren@ltu.se>",
+]
+categories = ["concurrency", "embedded", "no-std", "asynchronous"]
+description = "rtic-time lib TODO"
+license = "MIT OR Apache-2.0"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
+critical-section = "1"
+futures-util = { version = "0.3.25", default-features = false }
+rtic-common = { version = "1.0.0-alpha.0", path = "../rtic-common" }
diff --git a/rtic-time/rust-toolchain.toml b/rtic-time/rust-toolchain.toml
new file mode 100644
index 0000000..e28b55d
--- /dev/null
+++ b/rtic-time/rust-toolchain.toml
@@ -0,0 +1,4 @@
+[toolchain]
+channel = "nightly"
+components = [ "rust-src", "rustfmt", "llvm-tools-preview" ]
+targets = [ "thumbv6m-none-eabi", "thumbv7m-none-eabi" ]
diff --git a/rtic-time/src/lib.rs b/rtic-time/src/lib.rs
new file mode 100644
index 0000000..78b57a4
--- /dev/null
+++ b/rtic-time/src/lib.rs
@@ -0,0 +1,273 @@
+//! Crate
+
+#![no_std]
+#![deny(missing_docs)]
+//deny_warnings_placeholder_for_ci
+#![allow(incomplete_features)]
+#![feature(async_fn_in_trait)]
+
+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;
+
+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_poped: AtomicBool,
+}
+
+impl<Mono: Monotonic> Clone for WaitingWaker<Mono> {
+ fn clone(&self) -> Self {
+ Self {
+ waker: self.waker.clone(),
+ release_at: self.release_at,
+ was_poped: AtomicBool::new(self.was_poped.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,
+}
+
+/// 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);
+ }
+
+ /// 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) {
+ 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_poped.store(should_pop, Ordering::Relaxed);
+
+ should_pop
+ });
+
+ match (head, release_at) {
+ (Some(link), _) => {
+ link.waker.wake();
+ }
+ (None, Some(instant)) => {
+ Mono::enable_timer();
+ Mono::set_compare(instant);
+
+ 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;
+ }
+ }
+ }
+ }
+
+ /// Timeout at a specific time.
+ pub async fn timeout_at<F: Future>(
+ &self,
+ instant: Mono::Instant,
+ 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 a specific duration.
+ #[inline]
+ pub async fn timeout_after<F: Future>(
+ &self,
+ duration: Mono::Duration,
+ future: F,
+ ) -> Result<F::Output, TimeoutError> {
+ self.timeout_at(Mono::now() + duration, future).await
+ }
+
+ /// Delay for some duration of time.
+ #[inline]
+ pub async fn delay(&self, duration: Mono::Duration) {
+ let now = Mono::now();
+
+ self.delay_until(now + duration).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_poped: 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 (was_empty, addr) = unsafe { queue.insert(Pin::new_unchecked(link_ref)) };
+
+ marker.store(addr, Ordering::Relaxed);
+
+ if was_empty {
+ // Pend the monotonic handler if the queue was empty to setup the timer.
+ 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_poped.load(Ordering::Relaxed) {
+ // If it was poped 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/linked_list.rs b/rtic-time/src/linked_list.rs
new file mode 100644
index 0000000..d4256c9
--- /dev/null
+++ b/rtic-time/src/linked_list.rs
@@ -0,0 +1,182 @@
+//! ...
+
+use core::marker::PhantomPinned;
+use core::pin::Pin;
+use core::sync::atomic::{AtomicPtr, Ordering};
+use critical_section as cs;
+
+/// A sorted linked list for the timer queue.
+pub(crate) struct LinkedList<T> {
+ head: AtomicPtr<Link<T>>,
+}
+
+impl<T> LinkedList<T> {
+ /// Create a new linked list.
+ pub const fn new() -> Self {
+ Self {
+ head: AtomicPtr::new(core::ptr::null_mut()),
+ }
+ }
+}
+
+impl<T: PartialOrd + Clone> LinkedList<T> {
+ /// Pop the first element in the queue if the closure returns true.
+ pub fn pop_if<F: FnOnce(&T) -> bool>(&self, f: F) -> Option<T> {
+ cs::with(|_| {
+ // Make sure all previous writes are visible
+ core::sync::atomic::fence(Ordering::SeqCst);
+
+ let head = self.head.load(Ordering::Relaxed);
+
+ // SAFETY: `as_ref` is safe as `insert` requires a valid reference to a link
+ if let Some(head) = unsafe { head.as_ref() } {
+ if f(&head.val) {
+ // Move head to the next element
+ self.head
+ .store(head.next.load(Ordering::Relaxed), Ordering::Relaxed);
+
+ // We read the value at head
+ let head_val = head.val.clone();
+
+ return Some(head_val);
+ }
+ }
+ None
+ })
+ }
+
+ /// Delete a link at an address.
+ pub fn delete(&self, addr: usize) {
+ cs::with(|_| {
+ // Make sure all previous writes are visible
+ core::sync::atomic::fence(Ordering::SeqCst);
+
+ let head = self.head.load(Ordering::Relaxed);
+
+ // SAFETY: `as_ref` is safe as `insert` requires a valid reference to a link
+ let head_ref = if let Some(head_ref) = unsafe { head.as_ref() } {
+ head_ref
+ } else {
+ // 1. List is empty, do nothing
+ return;
+ };
+
+ if head as *const _ as usize == addr {
+ // 2. Replace head with head.next
+ self.head
+ .store(head_ref.next.load(Ordering::Relaxed), Ordering::Relaxed);
+
+ return;
+ }
+
+ // 3. search list for correct node
+ let mut curr = head_ref;
+ let mut next = head_ref.next.load(Ordering::Relaxed);
+
+ // SAFETY: `as_ref` is safe as `insert` requires a valid reference to a link
+ while let Some(next_link) = unsafe { next.as_ref() } {
+ // Next is not null
+
+ if next as *const _ as usize == addr {
+ curr.next
+ .store(next_link.next.load(Ordering::Relaxed), Ordering::Relaxed);
+
+ return;
+ }
+
+ // Continue searching
+ curr = next_link;
+ next = next_link.next.load(Ordering::Relaxed);
+ }
+ })
+ }
+
+ /// Insert a new link into the linked list.
+ /// The return is (was_empty, address), where the address of the link is for use with `delete`.
+ ///
+ /// SAFETY: The pinned link must live until it is removed from this list.
+ pub unsafe fn insert(&self, val: Pin<&Link<T>>) -> (bool, usize) {
+ cs::with(|_| {
+ // SAFETY: This datastructure does not move the underlying value.
+ let val = val.get_ref();
+ let addr = val as *const _ as usize;
+
+ // Make sure all previous writes are visible
+ core::sync::atomic::fence(Ordering::SeqCst);
+
+ let head = self.head.load(Ordering::Relaxed);
+
+ // 3 cases to handle
+
+ // 1. List is empty, write to head
+ // SAFETY: `as_ref` is safe as `insert` requires a valid reference to a link
+ let head_ref = if let Some(head_ref) = unsafe { head.as_ref() } {
+ head_ref
+ } else {
+ self.head
+ .store(val as *const _ as *mut _, Ordering::Relaxed);
+ return (true, addr);
+ };
+
+ // 2. val needs to go in first
+ if val.val < head_ref.val {
+ // Set current head as next of `val`
+ val.next.store(head, Ordering::Relaxed);
+
+ // `val` is now first in the queue
+ self.head
+ .store(val as *const _ as *mut _, Ordering::Relaxed);
+
+ return (false, addr);
+ }
+
+ // 3. search list for correct place
+ let mut curr = head_ref;
+ let mut next = head_ref.next.load(Ordering::Relaxed);
+
+ // SAFETY: `as_ref` is safe as `insert` requires a valid reference to a link
+ while let Some(next_link) = unsafe { next.as_ref() } {
+ // Next is not null
+
+ if val.val < next_link.val {
+ // Replace next with `val`
+ val.next.store(next, Ordering::Relaxed);
+
+ // Insert `val`
+ curr.next
+ .store(val as *const _ as *mut _, Ordering::Relaxed);
+
+ return (false, addr);
+ }
+
+ // Continue searching
+ curr = next_link;
+ next = next_link.next.load(Ordering::Relaxed);
+ }
+
+ // No next, write link to last position in list
+ curr.next
+ .store(val as *const _ as *mut _, Ordering::Relaxed);
+
+ (false, addr)
+ })
+ }
+}
+
+/// A link in the linked list.
+pub struct Link<T> {
+ pub(crate) val: T,
+ next: AtomicPtr<Link<T>>,
+ _up: PhantomPinned,
+}
+
+impl<T> Link<T> {
+ /// Create a new link.
+ pub const fn new(val: T) -> Self {
+ Self {
+ val,
+ next: AtomicPtr::new(core::ptr::null_mut()),
+ _up: PhantomPinned,
+ }
+ }
+}
diff --git a/rtic-time/src/monotonic.rs b/rtic-time/src/monotonic.rs
new file mode 100644
index 0000000..9b3742f
--- /dev/null
+++ b/rtic-time/src/monotonic.rs
@@ -0,0 +1,60 @@
+//! ...
+
+/// # 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;
+
+ /// 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);
+
+ /// 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() {}
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-12-27 12:03:14 +0000