From 5a5495aac43d75610735f2ca80fb6c8e8f31ed71 Mon Sep 17 00:00:00 2001 From: Dániel Buga Date: Tue, 26 Nov 2024 23:54:21 +0100 Subject: Refactor integrated-timers --- embassy-time-queue-driver/Cargo.toml | 33 ++++++ embassy-time-queue-driver/src/lib.rs | 136 ++++++++++++++++++++++- embassy-time-queue-driver/src/queue_generic.rs | 146 +++++++++++++++++++++++++ 3 files changed, 313 insertions(+), 2 deletions(-) create mode 100644 embassy-time-queue-driver/src/queue_generic.rs (limited to 'embassy-time-queue-driver') diff --git a/embassy-time-queue-driver/Cargo.toml b/embassy-time-queue-driver/Cargo.toml index 9ce9d79bb..599041a3f 100644 --- a/embassy-time-queue-driver/Cargo.toml +++ b/embassy-time-queue-driver/Cargo.toml @@ -20,6 +20,39 @@ categories = [ # This is especially common when mixing crates from crates.io and git. links = "embassy-time-queue" +[dependencies] +critical-section = "1.2.0" +heapless = "0.8" +embassy-executor = { version = "0.6.3", path = "../embassy-executor", optional = true } +embassy-time-driver = { version = "0.1.0", path = "../embassy-time-driver" } + +[features] +#! ### Generic Queue + +## Use the executor-integrated `embassy-time` timer queue. The timer items are stored inside +## the task headers, so you do not need to set a capacity for the queue. +## To use this you must have a time driver provided. +## +## If this feature is not enabled, a generic queue is available with a configurable capacity. +integrated-timers = ["embassy-executor/integrated-timers"] + +#! The following features set how many timers are used for the generic queue. At most one +#! `generic-queue-*` feature can be enabled. If none is enabled, a default of 64 timers is used. +#! +#! When using embassy-time from libraries, you should *not* enable any `generic-queue-*` feature, to allow the +#! end user to pick. + +## Generic Queue with 8 timers +generic-queue-8 = [] +## Generic Queue with 16 timers +generic-queue-16 = [] +## Generic Queue with 32 timers +generic-queue-32 = [] +## Generic Queue with 64 timers +generic-queue-64 = [] +## Generic Queue with 128 timers +generic-queue-128 = [] + [package.metadata.embassy_docs] src_base = "https://github.com/embassy-rs/embassy/blob/embassy-time-queue-driver-v$VERSION/embassy-time-queue-driver/src/" src_base_git = "https://github.com/embassy-rs/embassy/blob/$COMMIT/embassy-time-queue-driver/src/" diff --git a/embassy-time-queue-driver/src/lib.rs b/embassy-time-queue-driver/src/lib.rs index 50736e8c7..c5e989854 100644 --- a/embassy-time-queue-driver/src/lib.rs +++ b/embassy-time-queue-driver/src/lib.rs @@ -6,7 +6,29 @@ //! //! - Define a struct `MyTimerQueue` //! - Implement [`TimerQueue`] for it -//! - Register it as the global timer queue with [`timer_queue_impl`](crate::timer_queue_impl). +//! - Register it as the global timer queue with [`timer_queue_impl`]. +//! - Ensure that you process the timer queue when `schedule_wake` is due. This usually involves +//! waking expired tasks, finding the next expiration time and setting an alarm. +//! +//! If a single global timer queue is sufficient for you, you can use the +//! [`GlobalTimerQueue`] type, which is a wrapper around a global timer queue +//! protected by a critical section. +//! +//! ``` +//! use embassy_time_queue_driver::GlobalTimerQueue; +//! embassy_time_queue_driver::timer_queue_impl!( +//! static TIMER_QUEUE_DRIVER: GlobalTimerQueue +//! = GlobalTimerQueue::new(|next_expiration| todo!("Set an alarm")) +//! ); +//! ``` +//! +//! You can also use the `queue_generic` or the `embassy_executor::raw::timer_queue` modules to +//! implement your own timer queue. These modules contain queue implementations which you can wrap +//! and tailor to your needs. +//! +//! If you are providing an embassy-executor implementation besides a timer queue, you can choose to +//! expose the `integrated-timers` feature in your implementation. This feature stores timer items +//! in the tasks themselves, so you don't need a fixed-size queue or dynamic memory allocation. //! //! ## Example //! @@ -14,7 +36,7 @@ //! use core::task::Waker; //! //! use embassy_time::Instant; -//! use embassy_time::queue::{TimerQueue}; +//! use embassy_time::queue::TimerQueue; //! //! struct MyTimerQueue{}; // not public! //! @@ -26,11 +48,18 @@ //! //! embassy_time_queue_driver::timer_queue_impl!(static QUEUE: MyTimerQueue = MyTimerQueue{}); //! ``` + +pub mod queue_generic; + +use core::cell::RefCell; use core::task::Waker; +use critical_section::Mutex; + /// Timer queue pub trait TimerQueue { /// Schedules a waker in the queue to be awoken at moment `at`. + /// /// If this moment is in the past, the waker might be awoken immediately. fn schedule_wake(&'static self, at: u64, waker: &Waker); } @@ -58,3 +87,106 @@ macro_rules! timer_queue_impl { } }; } + +#[cfg(feature = "integrated-timers")] +type InnerQueue = embassy_executor::raw::timer_queue::TimerQueue; + +#[cfg(not(feature = "integrated-timers"))] +type InnerQueue = queue_generic::Queue; + +/// A timer queue implementation that can be used as a global timer queue. +/// +/// This implementation is not thread-safe, and should be protected by a mutex of some sort. +pub struct GenericTimerQueue bool> { + queue: InnerQueue, + set_alarm: F, +} + +impl bool> GenericTimerQueue { + /// Creates a new timer queue. + /// + /// `set_alarm` is a function that should set the next alarm time. The function should + /// return `true` if the alarm was set, and `false` if the alarm was in the past. + pub const fn new(set_alarm: F) -> Self { + Self { + queue: InnerQueue::new(), + set_alarm, + } + } + + /// Schedules a task to run at a specific time, and returns whether any changes were made. + pub fn schedule_wake(&mut self, at: u64, waker: &core::task::Waker) { + #[cfg(feature = "integrated-timers")] + let waker = embassy_executor::raw::task_from_waker(waker); + + if self.queue.schedule_wake(at, waker) { + self.dispatch() + } + } + + /// Dequeues expired timers and returns the next alarm time. + pub fn next_expiration(&mut self, now: u64) -> u64 { + self.queue.next_expiration(now) + } + + /// Handle the alarm. + /// + /// Call this function when the next alarm is due. + pub fn dispatch(&mut self) { + let mut next_expiration = self.next_expiration(embassy_time_driver::now()); + + while !(self.set_alarm)(next_expiration) { + // next_expiration is in the past, dequeue and find a new expiration + next_expiration = self.next_expiration(next_expiration); + } + } +} + +/// A [`GenericTimerQueue`] protected by a critical section. Directly useable as a [`TimerQueue`]. +pub struct GlobalTimerQueue { + inner: Mutex bool>>>, +} + +impl GlobalTimerQueue { + /// Creates a new timer queue. + /// + /// `set_alarm` is a function that should set the next alarm time. The function should + /// return `true` if the alarm was set, and `false` if the alarm was in the past. + pub const fn new(set_alarm: fn(u64) -> bool) -> Self { + Self { + inner: Mutex::new(RefCell::new(GenericTimerQueue::new(set_alarm))), + } + } + + /// Schedules a task to run at a specific time, and returns whether any changes were made. + pub fn schedule_wake(&self, at: u64, waker: &core::task::Waker) { + critical_section::with(|cs| { + let mut inner = self.inner.borrow_ref_mut(cs); + inner.schedule_wake(at, waker); + }); + } + + /// Dequeues expired timers and returns the next alarm time. + pub fn next_expiration(&self, now: u64) -> u64 { + critical_section::with(|cs| { + let mut inner = self.inner.borrow_ref_mut(cs); + inner.next_expiration(now) + }) + } + + /// Handle the alarm. + /// + /// Call this function when the next alarm is due. + pub fn dispatch(&self) { + critical_section::with(|cs| { + let mut inner = self.inner.borrow_ref_mut(cs); + inner.dispatch() + }) + } +} + +impl TimerQueue for GlobalTimerQueue { + fn schedule_wake(&'static self, at: u64, waker: &Waker) { + GlobalTimerQueue::schedule_wake(self, at, waker) + } +} diff --git a/embassy-time-queue-driver/src/queue_generic.rs b/embassy-time-queue-driver/src/queue_generic.rs new file mode 100644 index 000000000..232035bc6 --- /dev/null +++ b/embassy-time-queue-driver/src/queue_generic.rs @@ -0,0 +1,146 @@ +//! Generic timer queue implementations. +//! +//! Time queue drivers may use this to simplify their implementation. + +use core::cmp::{min, Ordering}; +use core::task::Waker; + +use heapless::Vec; + +#[derive(Debug)] +struct Timer { + at: u64, + waker: Waker, +} + +impl PartialEq for Timer { + fn eq(&self, other: &Self) -> bool { + self.at == other.at + } +} + +impl Eq for Timer {} + +impl PartialOrd for Timer { + fn partial_cmp(&self, other: &Self) -> Option { + self.at.partial_cmp(&other.at) + } +} + +impl Ord for Timer { + fn cmp(&self, other: &Self) -> Ordering { + self.at.cmp(&other.at) + } +} + +/// A timer queue with a pre-determined capacity. +pub struct ConstGenericQueue { + queue: Vec, +} + +impl ConstGenericQueue { + /// Creates a new timer queue. + pub const fn new() -> Self { + Self { queue: Vec::new() } + } + + /// Schedules a task to run at a specific time, and returns whether any changes were made. + /// + /// If this function returns `true`, the called should find the next expiration time and set + /// a new alarm for that time. + pub fn schedule_wake(&mut self, at: u64, waker: &Waker) -> bool { + self.queue + .iter_mut() + .find(|timer| timer.waker.will_wake(waker)) + .map(|timer| { + if timer.at > at { + timer.at = at; + true + } else { + false + } + }) + .unwrap_or_else(|| { + let mut timer = Timer { + waker: waker.clone(), + at, + }; + + loop { + match self.queue.push(timer) { + Ok(()) => break, + Err(e) => timer = e, + } + + self.queue.pop().unwrap().waker.wake(); + } + + true + }) + } + + /// Dequeues expired timers and returns the next alarm time. + pub fn next_expiration(&mut self, now: u64) -> u64 { + let mut next_alarm = u64::MAX; + + let mut i = 0; + while i < self.queue.len() { + let timer = &self.queue[i]; + if timer.at <= now { + let timer = self.queue.swap_remove(i); + timer.waker.wake(); + } else { + next_alarm = min(next_alarm, timer.at); + i += 1; + } + } + + next_alarm + } +} + +#[cfg(feature = "generic-queue-8")] +const QUEUE_SIZE: usize = 8; +#[cfg(feature = "generic-queue-16")] +const QUEUE_SIZE: usize = 16; +#[cfg(feature = "generic-queue-32")] +const QUEUE_SIZE: usize = 32; +#[cfg(feature = "generic-queue-64")] +const QUEUE_SIZE: usize = 64; +#[cfg(feature = "generic-queue-128")] +const QUEUE_SIZE: usize = 128; +#[cfg(not(any( + feature = "generic-queue-8", + feature = "generic-queue-16", + feature = "generic-queue-32", + feature = "generic-queue-64", + feature = "generic-queue-128" +)))] +const QUEUE_SIZE: usize = 64; + +/// A timer queue with a pre-determined capacity. +pub struct Queue { + queue: ConstGenericQueue, +} + +impl Queue { + /// Creates a new timer queue. + pub const fn new() -> Self { + Self { + queue: ConstGenericQueue::new(), + } + } + + /// Schedules a task to run at a specific time, and returns whether any changes were made. + /// + /// If this function returns `true`, the called should find the next expiration time and set + /// a new alarm for that time. + pub fn schedule_wake(&mut self, at: u64, waker: &Waker) -> bool { + self.queue.schedule_wake(at, waker) + } + + /// Dequeues expired timers and returns the next alarm time. + pub fn next_expiration(&mut self, now: u64) -> u64 { + self.queue.next_expiration(now) + } +} -- cgit From 6cc8709ecc9e8f71a13ec62b42be52bc8adf2c7b Mon Sep 17 00:00:00 2001 From: Dániel Buga Date: Sun, 8 Dec 2024 20:05:37 +0100 Subject: Changelog --- embassy-time-queue-driver/CHANGELOG.md | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) create mode 100644 embassy-time-queue-driver/CHANGELOG.md (limited to 'embassy-time-queue-driver') diff --git a/embassy-time-queue-driver/CHANGELOG.md b/embassy-time-queue-driver/CHANGELOG.md new file mode 100644 index 000000000..3b2aa8695 --- /dev/null +++ b/embassy-time-queue-driver/CHANGELOG.md @@ -0,0 +1,16 @@ +# Changelog for embassy-time-queue-driver + +All notable changes to this project will be documented in this file. + +The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/), +and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.html). + +## Unreleased + +- Added `integrated-timers` and `generic-queue-N` features +- Added `queue_generic` module which contains `Queue` (configured via the `generic-queue-N` features) and `ConstGenericQueue`. +- Added `GenericTimerQueue` and `GlobalTimerQueue` structs that can be used to implement timer queues. + +## 0.1.0 - 2024-01-11 + +Initial release -- cgit From d45ea43892198484b5f6dcea4c351dc11d226cc4 Mon Sep 17 00:00:00 2001 From: Dániel Buga Date: Sun, 8 Dec 2024 23:21:53 +0100 Subject: Move integrated timer queue into time-queue-driver --- embassy-time-queue-driver/src/lib.rs | 11 ++-- embassy-time-queue-driver/src/queue_integrated.rs | 78 +++++++++++++++++++++++ 2 files changed, 85 insertions(+), 4 deletions(-) create mode 100644 embassy-time-queue-driver/src/queue_integrated.rs (limited to 'embassy-time-queue-driver') diff --git a/embassy-time-queue-driver/src/lib.rs b/embassy-time-queue-driver/src/lib.rs index c5e989854..0c78921ed 100644 --- a/embassy-time-queue-driver/src/lib.rs +++ b/embassy-time-queue-driver/src/lib.rs @@ -22,9 +22,9 @@ //! ); //! ``` //! -//! You can also use the `queue_generic` or the `embassy_executor::raw::timer_queue` modules to -//! implement your own timer queue. These modules contain queue implementations which you can wrap -//! and tailor to your needs. +//! You can also use the `queue_generic` or the `queue_integrated` modules to implement your own +//! timer queue. These modules contain queue implementations which you can wrap and tailor to +//! your needs. //! //! If you are providing an embassy-executor implementation besides a timer queue, you can choose to //! expose the `integrated-timers` feature in your implementation. This feature stores timer items @@ -49,7 +49,10 @@ //! embassy_time_queue_driver::timer_queue_impl!(static QUEUE: MyTimerQueue = MyTimerQueue{}); //! ``` +#[cfg(not(feature = "integrated-timers"))] pub mod queue_generic; +#[cfg(feature = "integrated-timers")] +pub mod queue_integrated; use core::cell::RefCell; use core::task::Waker; @@ -89,7 +92,7 @@ macro_rules! timer_queue_impl { } #[cfg(feature = "integrated-timers")] -type InnerQueue = embassy_executor::raw::timer_queue::TimerQueue; +type InnerQueue = queue_integrated::TimerQueue; #[cfg(not(feature = "integrated-timers"))] type InnerQueue = queue_generic::Queue; diff --git a/embassy-time-queue-driver/src/queue_integrated.rs b/embassy-time-queue-driver/src/queue_integrated.rs new file mode 100644 index 000000000..cb0f79356 --- /dev/null +++ b/embassy-time-queue-driver/src/queue_integrated.rs @@ -0,0 +1,78 @@ +//! Timer queue operations. +use core::cell::Cell; +use core::cmp::min; + +use embassy_executor::raw::TaskRef; + +/// A timer queue, with items integrated into tasks. +pub struct TimerQueue { + head: Cell>, +} + +impl TimerQueue { + /// Creates a new timer queue. + pub const fn new() -> Self { + Self { head: Cell::new(None) } + } + + /// Schedules a task to run at a specific time. + /// + /// If this function returns `true`, the called should find the next expiration time and set + /// a new alarm for that time. + pub fn schedule_wake(&mut self, at: u64, p: TaskRef) -> bool { + let item = p.timer_queue_item(); + if item.next.get().is_none() { + // If not in the queue, add it and update. + let prev = self.head.replace(Some(p)); + item.next.set(prev); + } else if at <= item.expires_at.get() { + // If expiration is sooner than previously set, update. + } else { + // Task does not need to be updated. + return false; + } + + item.expires_at.set(at); + true + } + + /// Dequeues expired timers and returns the next alarm time. + /// + /// The provided callback will be called for each expired task. Tasks that never expire + /// will be removed, but the callback will not be called. + pub fn next_expiration(&mut self, now: u64) -> u64 { + let mut next_expiration = u64::MAX; + + self.retain(|p| { + let item = p.timer_queue_item(); + let expires = item.expires_at.get(); + + if expires <= now { + // Timer expired, process task. + embassy_executor::raw::wake_task(p); + false + } else { + // Timer didn't yet expire, or never expires. + next_expiration = min(next_expiration, expires); + expires != u64::MAX + } + }); + + next_expiration + } + + fn retain(&self, mut f: impl FnMut(TaskRef) -> bool) { + let mut prev = &self.head; + while let Some(p) = prev.get() { + let item = p.timer_queue_item(); + if f(p) { + // Skip to next + prev = &item.next; + } else { + // Remove it + prev.set(item.next.get()); + item.next.set(None); + } + } + } +} -- cgit From ec96395d084d5edc8be25ddaea8547e2ebd447a6 Mon Sep 17 00:00:00 2001 From: Dániel Buga Date: Mon, 9 Dec 2024 08:43:57 +0100 Subject: Prevent task from respawning while in the timer queue --- embassy-time-queue-driver/src/lib.rs | 14 ++++++++++++++ embassy-time-queue-driver/src/queue_integrated.rs | 20 +++++++++++++++----- 2 files changed, 29 insertions(+), 5 deletions(-) (limited to 'embassy-time-queue-driver') diff --git a/embassy-time-queue-driver/src/lib.rs b/embassy-time-queue-driver/src/lib.rs index 0c78921ed..2d5fd449a 100644 --- a/embassy-time-queue-driver/src/lib.rs +++ b/embassy-time-queue-driver/src/lib.rs @@ -73,6 +73,20 @@ extern "Rust" { /// Schedule the given waker to be woken at `at`. pub fn schedule_wake(at: u64, waker: &Waker) { + #[cfg(feature = "integrated-timers")] + { + use embassy_executor::raw::task_from_waker; + use embassy_executor::raw::timer_queue::TimerEnqueueOperation; + // The very first thing we must do, before we even access the timer queue, is to + // mark the task a TIMER_QUEUED. This ensures that the task that is being scheduled + // can not be respawn while we are accessing the timer queue. + let task = task_from_waker(waker); + if unsafe { task.timer_enqueue() } == TimerEnqueueOperation::Ignore { + // We are not allowed to enqueue the task in the timer queue. This is because the + // task is not spawned, and so it makes no sense to schedule it. + return; + } + } unsafe { _embassy_time_schedule_wake(at, waker) } } diff --git a/embassy-time-queue-driver/src/queue_integrated.rs b/embassy-time-queue-driver/src/queue_integrated.rs index cb0f79356..b905c00c3 100644 --- a/embassy-time-queue-driver/src/queue_integrated.rs +++ b/embassy-time-queue-driver/src/queue_integrated.rs @@ -24,16 +24,21 @@ impl TimerQueue { if item.next.get().is_none() { // If not in the queue, add it and update. let prev = self.head.replace(Some(p)); - item.next.set(prev); + item.next.set(if prev.is_none() { + Some(unsafe { TaskRef::dangling() }) + } else { + prev + }); + item.expires_at.set(at); + true } else if at <= item.expires_at.get() { // If expiration is sooner than previously set, update. + item.expires_at.set(at); + true } else { // Task does not need to be updated. - return false; + false } - - item.expires_at.set(at); - true } /// Dequeues expired timers and returns the next alarm time. @@ -64,6 +69,10 @@ impl TimerQueue { fn retain(&self, mut f: impl FnMut(TaskRef) -> bool) { let mut prev = &self.head; while let Some(p) = prev.get() { + if unsafe { p == TaskRef::dangling() } { + // prev was the last item, stop + break; + } let item = p.timer_queue_item(); if f(p) { // Skip to next @@ -72,6 +81,7 @@ impl TimerQueue { // Remove it prev.set(item.next.get()); item.next.set(None); + unsafe { p.timer_dequeue() }; } } } -- cgit From b268b1795fed58544c166c41842ce0d66328aa3e Mon Sep 17 00:00:00 2001 From: Dario Nieuwenhuis Date: Sun, 8 Dec 2024 23:27:32 +0100 Subject: Merge time-driver and time-queue-driver traits, make HALs own and handle the queue. --- embassy-time-queue-driver/src/lib.rs | 140 ++-------------------- embassy-time-queue-driver/src/queue_integrated.rs | 12 +- 2 files changed, 17 insertions(+), 135 deletions(-) (limited to 'embassy-time-queue-driver') diff --git a/embassy-time-queue-driver/src/lib.rs b/embassy-time-queue-driver/src/lib.rs index 2d5fd449a..ed490a0ef 100644 --- a/embassy-time-queue-driver/src/lib.rs +++ b/embassy-time-queue-driver/src/lib.rs @@ -49,23 +49,18 @@ //! embassy_time_queue_driver::timer_queue_impl!(static QUEUE: MyTimerQueue = MyTimerQueue{}); //! ``` +use core::task::Waker; + #[cfg(not(feature = "integrated-timers"))] pub mod queue_generic; #[cfg(feature = "integrated-timers")] pub mod queue_integrated; -use core::cell::RefCell; -use core::task::Waker; - -use critical_section::Mutex; +#[cfg(feature = "integrated-timers")] +pub use queue_integrated::Queue; -/// Timer queue -pub trait TimerQueue { - /// Schedules a waker in the queue to be awoken at moment `at`. - /// - /// If this moment is in the past, the waker might be awoken immediately. - fn schedule_wake(&'static self, at: u64, waker: &Waker); -} +#[cfg(not(feature = "integrated-timers"))] +pub use queue_generic::Queue; extern "Rust" { fn _embassy_time_schedule_wake(at: u64, waker: &Waker); @@ -73,7 +68,10 @@ extern "Rust" { /// Schedule the given waker to be woken at `at`. pub fn schedule_wake(at: u64, waker: &Waker) { - #[cfg(feature = "integrated-timers")] + // This function is not implemented in embassy-time-driver because it needs access to executor + // internals. The function updates task state, then delegates to the implementation provided + // by the time driver. + #[cfg(not(feature = "_generic-queue"))] { use embassy_executor::raw::task_from_waker; use embassy_executor::raw::timer_queue::TimerEnqueueOperation; @@ -89,121 +87,3 @@ pub fn schedule_wake(at: u64, waker: &Waker) { } unsafe { _embassy_time_schedule_wake(at, waker) } } - -/// Set the TimerQueue implementation. -/// -/// See the module documentation for an example. -#[macro_export] -macro_rules! timer_queue_impl { - (static $name:ident: $t: ty = $val:expr) => { - static $name: $t = $val; - - #[no_mangle] - fn _embassy_time_schedule_wake(at: u64, waker: &core::task::Waker) { - <$t as $crate::TimerQueue>::schedule_wake(&$name, at, waker); - } - }; -} - -#[cfg(feature = "integrated-timers")] -type InnerQueue = queue_integrated::TimerQueue; - -#[cfg(not(feature = "integrated-timers"))] -type InnerQueue = queue_generic::Queue; - -/// A timer queue implementation that can be used as a global timer queue. -/// -/// This implementation is not thread-safe, and should be protected by a mutex of some sort. -pub struct GenericTimerQueue bool> { - queue: InnerQueue, - set_alarm: F, -} - -impl bool> GenericTimerQueue { - /// Creates a new timer queue. - /// - /// `set_alarm` is a function that should set the next alarm time. The function should - /// return `true` if the alarm was set, and `false` if the alarm was in the past. - pub const fn new(set_alarm: F) -> Self { - Self { - queue: InnerQueue::new(), - set_alarm, - } - } - - /// Schedules a task to run at a specific time, and returns whether any changes were made. - pub fn schedule_wake(&mut self, at: u64, waker: &core::task::Waker) { - #[cfg(feature = "integrated-timers")] - let waker = embassy_executor::raw::task_from_waker(waker); - - if self.queue.schedule_wake(at, waker) { - self.dispatch() - } - } - - /// Dequeues expired timers and returns the next alarm time. - pub fn next_expiration(&mut self, now: u64) -> u64 { - self.queue.next_expiration(now) - } - - /// Handle the alarm. - /// - /// Call this function when the next alarm is due. - pub fn dispatch(&mut self) { - let mut next_expiration = self.next_expiration(embassy_time_driver::now()); - - while !(self.set_alarm)(next_expiration) { - // next_expiration is in the past, dequeue and find a new expiration - next_expiration = self.next_expiration(next_expiration); - } - } -} - -/// A [`GenericTimerQueue`] protected by a critical section. Directly useable as a [`TimerQueue`]. -pub struct GlobalTimerQueue { - inner: Mutex bool>>>, -} - -impl GlobalTimerQueue { - /// Creates a new timer queue. - /// - /// `set_alarm` is a function that should set the next alarm time. The function should - /// return `true` if the alarm was set, and `false` if the alarm was in the past. - pub const fn new(set_alarm: fn(u64) -> bool) -> Self { - Self { - inner: Mutex::new(RefCell::new(GenericTimerQueue::new(set_alarm))), - } - } - - /// Schedules a task to run at a specific time, and returns whether any changes were made. - pub fn schedule_wake(&self, at: u64, waker: &core::task::Waker) { - critical_section::with(|cs| { - let mut inner = self.inner.borrow_ref_mut(cs); - inner.schedule_wake(at, waker); - }); - } - - /// Dequeues expired timers and returns the next alarm time. - pub fn next_expiration(&self, now: u64) -> u64 { - critical_section::with(|cs| { - let mut inner = self.inner.borrow_ref_mut(cs); - inner.next_expiration(now) - }) - } - - /// Handle the alarm. - /// - /// Call this function when the next alarm is due. - pub fn dispatch(&self) { - critical_section::with(|cs| { - let mut inner = self.inner.borrow_ref_mut(cs); - inner.dispatch() - }) - } -} - -impl TimerQueue for GlobalTimerQueue { - fn schedule_wake(&'static self, at: u64, waker: &Waker) { - GlobalTimerQueue::schedule_wake(self, at, waker) - } -} diff --git a/embassy-time-queue-driver/src/queue_integrated.rs b/embassy-time-queue-driver/src/queue_integrated.rs index b905c00c3..6bb4c0c1a 100644 --- a/embassy-time-queue-driver/src/queue_integrated.rs +++ b/embassy-time-queue-driver/src/queue_integrated.rs @@ -1,15 +1,16 @@ //! Timer queue operations. use core::cell::Cell; use core::cmp::min; +use core::task::Waker; use embassy_executor::raw::TaskRef; /// A timer queue, with items integrated into tasks. -pub struct TimerQueue { +pub struct Queue { head: Cell>, } -impl TimerQueue { +impl Queue { /// Creates a new timer queue. pub const fn new() -> Self { Self { head: Cell::new(None) } @@ -19,11 +20,12 @@ impl TimerQueue { /// /// If this function returns `true`, the called should find the next expiration time and set /// a new alarm for that time. - pub fn schedule_wake(&mut self, at: u64, p: TaskRef) -> bool { - let item = p.timer_queue_item(); + pub fn schedule_wake(&mut self, at: u64, waker: &Waker) -> bool { + let task = embassy_executor::raw::task_from_waker(waker); + let item = task.timer_queue_item(); if item.next.get().is_none() { // If not in the queue, add it and update. - let prev = self.head.replace(Some(p)); + let prev = self.head.replace(Some(task)); item.next.set(if prev.is_none() { Some(unsafe { TaskRef::dangling() }) } else { -- cgit From 2f2e2c6031a1abaecdac5ed2febe109e647fe6fd Mon Sep 17 00:00:00 2001 From: Dario Nieuwenhuis Date: Mon, 9 Dec 2024 00:28:14 +0100 Subject: Make `integrated-timers` the default, remove Cargo feature. --- embassy-time-queue-driver/Cargo.toml | 29 +++++++++++++++-------------- embassy-time-queue-driver/src/lib.rs | 11 +++++------ 2 files changed, 20 insertions(+), 20 deletions(-) (limited to 'embassy-time-queue-driver') diff --git a/embassy-time-queue-driver/Cargo.toml b/embassy-time-queue-driver/Cargo.toml index 599041a3f..7a10e29b4 100644 --- a/embassy-time-queue-driver/Cargo.toml +++ b/embassy-time-queue-driver/Cargo.toml @@ -23,35 +23,36 @@ links = "embassy-time-queue" [dependencies] critical-section = "1.2.0" heapless = "0.8" -embassy-executor = { version = "0.6.3", path = "../embassy-executor", optional = true } +embassy-executor = { version = "0.6.3", path = "../embassy-executor" } embassy-time-driver = { version = "0.1.0", path = "../embassy-time-driver" } [features] #! ### Generic Queue -## Use the executor-integrated `embassy-time` timer queue. The timer items are stored inside -## the task headers, so you do not need to set a capacity for the queue. -## To use this you must have a time driver provided. -## -## If this feature is not enabled, a generic queue is available with a configurable capacity. -integrated-timers = ["embassy-executor/integrated-timers"] - -#! The following features set how many timers are used for the generic queue. At most one +#! By default this crate uses a timer queue implementation that is faster but depends on `embassy-executor`. +#! It will panic if you try to await any timer when using another executor. +#! +#! Alternatively, you can choose to use a "generic" timer queue implementation that works on any executor. +#! To enable it, enable any of the features below. +#! +#! The features also set how many timers are used for the generic queue. At most one #! `generic-queue-*` feature can be enabled. If none is enabled, a default of 64 timers is used. #! #! When using embassy-time from libraries, you should *not* enable any `generic-queue-*` feature, to allow the #! end user to pick. ## Generic Queue with 8 timers -generic-queue-8 = [] +generic-queue-8 = ["_generic-queue"] ## Generic Queue with 16 timers -generic-queue-16 = [] +generic-queue-16 = ["_generic-queue"] ## Generic Queue with 32 timers -generic-queue-32 = [] +generic-queue-32 = ["_generic-queue"] ## Generic Queue with 64 timers -generic-queue-64 = [] +generic-queue-64 = ["_generic-queue"] ## Generic Queue with 128 timers -generic-queue-128 = [] +generic-queue-128 = ["_generic-queue"] + +_generic-queue = [] [package.metadata.embassy_docs] src_base = "https://github.com/embassy-rs/embassy/blob/embassy-time-queue-driver-v$VERSION/embassy-time-queue-driver/src/" diff --git a/embassy-time-queue-driver/src/lib.rs b/embassy-time-queue-driver/src/lib.rs index ed490a0ef..46dd646ca 100644 --- a/embassy-time-queue-driver/src/lib.rs +++ b/embassy-time-queue-driver/src/lib.rs @@ -51,16 +51,15 @@ use core::task::Waker; -#[cfg(not(feature = "integrated-timers"))] +#[cfg(feature = "_generic-queue")] pub mod queue_generic; -#[cfg(feature = "integrated-timers")] +#[cfg(not(feature = "_generic-queue"))] pub mod queue_integrated; -#[cfg(feature = "integrated-timers")] -pub use queue_integrated::Queue; - -#[cfg(not(feature = "integrated-timers"))] +#[cfg(feature = "_generic-queue")] pub use queue_generic::Queue; +#[cfg(not(feature = "_generic-queue"))] +pub use queue_integrated::Queue; extern "Rust" { fn _embassy_time_schedule_wake(at: u64, waker: &Waker); -- cgit From 0492dba5368e7cb22ede2d41d26d4d0431ba2252 Mon Sep 17 00:00:00 2001 From: Dániel Buga Date: Sun, 15 Dec 2024 19:24:49 +0100 Subject: Update documentation and changelogs --- embassy-time-queue-driver/CHANGELOG.md | 5 ++-- embassy-time-queue-driver/src/lib.rs | 49 ++++------------------------------ 2 files changed, 7 insertions(+), 47 deletions(-) (limited to 'embassy-time-queue-driver') diff --git a/embassy-time-queue-driver/CHANGELOG.md b/embassy-time-queue-driver/CHANGELOG.md index 3b2aa8695..a99f250ed 100644 --- a/embassy-time-queue-driver/CHANGELOG.md +++ b/embassy-time-queue-driver/CHANGELOG.md @@ -7,9 +7,8 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ## Unreleased -- Added `integrated-timers` and `generic-queue-N` features -- Added `queue_generic` module which contains `Queue` (configured via the `generic-queue-N` features) and `ConstGenericQueue`. -- Added `GenericTimerQueue` and `GlobalTimerQueue` structs that can be used to implement timer queues. +- Added `generic-queue-N` features. +- Added `embassy_time_queue_driver::Queue` struct which uses integrated or a generic storage (configured using `generic-queue-N`). ## 0.1.0 - 2024-01-11 diff --git a/embassy-time-queue-driver/src/lib.rs b/embassy-time-queue-driver/src/lib.rs index 46dd646ca..d8b01df3b 100644 --- a/embassy-time-queue-driver/src/lib.rs +++ b/embassy-time-queue-driver/src/lib.rs @@ -2,52 +2,13 @@ #![doc = include_str!("../README.md")] #![warn(missing_docs)] -//! ## Implementing a timer queue +//! This crate is an implementation detail of `embassy-time-driver`. //! -//! - Define a struct `MyTimerQueue` -//! - Implement [`TimerQueue`] for it -//! - Register it as the global timer queue with [`timer_queue_impl`]. -//! - Ensure that you process the timer queue when `schedule_wake` is due. This usually involves -//! waking expired tasks, finding the next expiration time and setting an alarm. +//! As a HAL user, you should only depend on this crate if your application does not use +//! `embassy-executor` and your HAL does not configure a generic queue by itself. //! -//! If a single global timer queue is sufficient for you, you can use the -//! [`GlobalTimerQueue`] type, which is a wrapper around a global timer queue -//! protected by a critical section. -//! -//! ``` -//! use embassy_time_queue_driver::GlobalTimerQueue; -//! embassy_time_queue_driver::timer_queue_impl!( -//! static TIMER_QUEUE_DRIVER: GlobalTimerQueue -//! = GlobalTimerQueue::new(|next_expiration| todo!("Set an alarm")) -//! ); -//! ``` -//! -//! You can also use the `queue_generic` or the `queue_integrated` modules to implement your own -//! timer queue. These modules contain queue implementations which you can wrap and tailor to -//! your needs. -//! -//! If you are providing an embassy-executor implementation besides a timer queue, you can choose to -//! expose the `integrated-timers` feature in your implementation. This feature stores timer items -//! in the tasks themselves, so you don't need a fixed-size queue or dynamic memory allocation. -//! -//! ## Example -//! -//! ``` -//! use core::task::Waker; -//! -//! use embassy_time::Instant; -//! use embassy_time::queue::TimerQueue; -//! -//! struct MyTimerQueue{}; // not public! -//! -//! impl TimerQueue for MyTimerQueue { -//! fn schedule_wake(&'static self, at: u64, waker: &Waker) { -//! todo!() -//! } -//! } -//! -//! embassy_time_queue_driver::timer_queue_impl!(static QUEUE: MyTimerQueue = MyTimerQueue{}); -//! ``` +//! As a HAL implementer, you need to depend on this crate if you want to implement a time driver, +//! but how you should do so is documented in [`embassy_time_driver`]. use core::task::Waker; -- cgit From e77ac50248639e299f93b1820e73c9df9ceb09e6 Mon Sep 17 00:00:00 2001 From: Dániel Buga Date: Sun, 15 Dec 2024 20:27:08 +0100 Subject: Remove critical_section dependency --- embassy-time-queue-driver/Cargo.toml | 1 - 1 file changed, 1 deletion(-) (limited to 'embassy-time-queue-driver') diff --git a/embassy-time-queue-driver/Cargo.toml b/embassy-time-queue-driver/Cargo.toml index 7a10e29b4..208b64668 100644 --- a/embassy-time-queue-driver/Cargo.toml +++ b/embassy-time-queue-driver/Cargo.toml @@ -21,7 +21,6 @@ categories = [ links = "embassy-time-queue" [dependencies] -critical-section = "1.2.0" heapless = "0.8" embassy-executor = { version = "0.6.3", path = "../embassy-executor" } embassy-time-driver = { version = "0.1.0", path = "../embassy-time-driver" } -- cgit From 4df4ffbbd49729cde38a3a4a73cdafd208372a53 Mon Sep 17 00:00:00 2001 From: Dániel Buga Date: Sun, 15 Dec 2024 20:28:12 +0100 Subject: Remove time-driver dependency --- embassy-time-queue-driver/Cargo.toml | 1 - embassy-time-queue-driver/src/lib.rs | 2 +- 2 files changed, 1 insertion(+), 2 deletions(-) (limited to 'embassy-time-queue-driver') diff --git a/embassy-time-queue-driver/Cargo.toml b/embassy-time-queue-driver/Cargo.toml index 208b64668..a104f5c39 100644 --- a/embassy-time-queue-driver/Cargo.toml +++ b/embassy-time-queue-driver/Cargo.toml @@ -23,7 +23,6 @@ links = "embassy-time-queue" [dependencies] heapless = "0.8" embassy-executor = { version = "0.6.3", path = "../embassy-executor" } -embassy-time-driver = { version = "0.1.0", path = "../embassy-time-driver" } [features] #! ### Generic Queue diff --git a/embassy-time-queue-driver/src/lib.rs b/embassy-time-queue-driver/src/lib.rs index d8b01df3b..97c81a124 100644 --- a/embassy-time-queue-driver/src/lib.rs +++ b/embassy-time-queue-driver/src/lib.rs @@ -8,7 +8,7 @@ //! `embassy-executor` and your HAL does not configure a generic queue by itself. //! //! As a HAL implementer, you need to depend on this crate if you want to implement a time driver, -//! but how you should do so is documented in [`embassy_time_driver`]. +//! but how you should do so is documented in `embassy-time-driver`. use core::task::Waker; -- cgit