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-executor/src/raw/timer_queue.rs | 89 +++++++++++++++++++++------------ 1 file changed, 57 insertions(+), 32 deletions(-) (limited to 'embassy-executor/src/raw/timer_queue.rs') diff --git a/embassy-executor/src/raw/timer_queue.rs b/embassy-executor/src/raw/timer_queue.rs index 94a5f340b..953bf014f 100644 --- a/embassy-executor/src/raw/timer_queue.rs +++ b/embassy-executor/src/raw/timer_queue.rs @@ -1,75 +1,100 @@ +//! Timer queue operations. use core::cmp::min; +use super::util::SyncUnsafeCell; use super::TaskRef; -use crate::raw::util::SyncUnsafeCell; pub(crate) struct TimerQueueItem { next: SyncUnsafeCell>, + expires_at: SyncUnsafeCell, } impl TimerQueueItem { pub const fn new() -> Self { Self { next: SyncUnsafeCell::new(None), + expires_at: SyncUnsafeCell::new(0), } } } -pub(crate) struct TimerQueue { +/// A timer queue, with items integrated into tasks. +pub struct TimerQueue { head: SyncUnsafeCell>, } impl TimerQueue { + /// Creates a new timer queue. pub const fn new() -> Self { Self { head: SyncUnsafeCell::new(None), } } - pub(crate) unsafe fn update(&self, p: TaskRef) { - let task = p.header(); - if task.expires_at.get() != u64::MAX { + /// 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 { + unsafe { + let task = p.header(); + let item = &task.timer_queue_item; if task.state.timer_enqueue() { - task.timer_queue_item.next.set(self.head.get()); - self.head.set(Some(p)); + // 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 } } - pub(crate) unsafe fn next_expiration(&self) -> u64 { - let mut res = u64::MAX; - self.retain(|p| { - let task = p.header(); - let expires = task.expires_at.get(); - res = min(res, expires); - expires != u64::MAX - }); - res - } + /// 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; - pub(crate) unsafe fn dequeue_expired(&self, now: u64, on_task: impl Fn(TaskRef)) { self.retain(|p| { let task = p.header(); - if task.expires_at.get() <= now { - on_task(p); + let item = &task.timer_queue_item; + let expires = unsafe { item.expires_at.get() }; + + if expires <= now { + // Timer expired, process task. + super::wake_task(p); false } else { - true + // Timer didn't yet expire, or never expires. + next_expiration = min(next_expiration, expires); + expires != u64::MAX } }); + + next_expiration } - pub(crate) unsafe fn retain(&self, mut f: impl FnMut(TaskRef) -> bool) { - let mut prev = &self.head; - while let Some(p) = prev.get() { - let task = p.header(); - if f(p) { - // Skip to next - prev = &task.timer_queue_item.next; - } else { - // Remove it - prev.set(task.timer_queue_item.next.get()); - task.state.timer_dequeue(); + fn retain(&self, mut f: impl FnMut(TaskRef) -> bool) { + unsafe { + let mut prev = &self.head; + while let Some(p) = prev.get() { + let task = p.header(); + let item = &task.timer_queue_item; + if f(p) { + // Skip to next + prev = &item.next; + } else { + // Remove it + prev.set(item.next.get()); + task.state.timer_dequeue(); + } } } } -- cgit From 12f58fbcfd3f10b43795936127a890c6a0f8f280 Mon Sep 17 00:00:00 2001 From: Dániel Buga Date: Sun, 8 Dec 2024 23:04:43 +0100 Subject: Remove TIMER_QUEUED state --- embassy-executor/src/raw/timer_queue.rs | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'embassy-executor/src/raw/timer_queue.rs') diff --git a/embassy-executor/src/raw/timer_queue.rs b/embassy-executor/src/raw/timer_queue.rs index 953bf014f..513397090 100644 --- a/embassy-executor/src/raw/timer_queue.rs +++ b/embassy-executor/src/raw/timer_queue.rs @@ -39,7 +39,7 @@ impl TimerQueue { unsafe { let task = p.header(); let item = &task.timer_queue_item; - if task.state.timer_enqueue() { + 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); @@ -93,7 +93,7 @@ impl TimerQueue { } else { // Remove it prev.set(item.next.get()); - task.state.timer_dequeue(); + item.next.set(None); } } } -- cgit From dc18ee29a0f93ce34892731ee0580a3e9e3f2298 Mon Sep 17 00:00:00 2001 From: Dániel Buga Date: Sun, 8 Dec 2024 23:07:35 +0100 Subject: Do not access task header --- embassy-executor/src/raw/timer_queue.rs | 14 ++++++-------- 1 file changed, 6 insertions(+), 8 deletions(-) (limited to 'embassy-executor/src/raw/timer_queue.rs') diff --git a/embassy-executor/src/raw/timer_queue.rs b/embassy-executor/src/raw/timer_queue.rs index 513397090..e0a22f4d4 100644 --- a/embassy-executor/src/raw/timer_queue.rs +++ b/embassy-executor/src/raw/timer_queue.rs @@ -4,13 +4,14 @@ use core::cmp::min; use super::util::SyncUnsafeCell; use super::TaskRef; -pub(crate) struct TimerQueueItem { +/// An item in the timer queue. +pub struct TimerQueueItem { next: SyncUnsafeCell>, expires_at: SyncUnsafeCell, } impl TimerQueueItem { - pub const fn new() -> Self { + pub(crate) const fn new() -> Self { Self { next: SyncUnsafeCell::new(None), expires_at: SyncUnsafeCell::new(0), @@ -37,8 +38,7 @@ impl TimerQueue { /// a new alarm for that time. pub fn schedule_wake(&mut self, at: u64, p: TaskRef) -> bool { unsafe { - let task = p.header(); - let item = &task.timer_queue_item; + 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)); @@ -63,8 +63,7 @@ impl TimerQueue { let mut next_expiration = u64::MAX; self.retain(|p| { - let task = p.header(); - let item = &task.timer_queue_item; + let item = p.timer_queue_item(); let expires = unsafe { item.expires_at.get() }; if expires <= now { @@ -85,8 +84,7 @@ impl TimerQueue { unsafe { let mut prev = &self.head; while let Some(p) = prev.get() { - let task = p.header(); - let item = &task.timer_queue_item; + let item = p.timer_queue_item(); if f(p) { // Skip to next prev = &item.next; -- 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-executor/src/raw/timer_queue.rs | 96 ++++----------------------------- 1 file changed, 11 insertions(+), 85 deletions(-) (limited to 'embassy-executor/src/raw/timer_queue.rs') diff --git a/embassy-executor/src/raw/timer_queue.rs b/embassy-executor/src/raw/timer_queue.rs index e0a22f4d4..46e346c1b 100644 --- a/embassy-executor/src/raw/timer_queue.rs +++ b/embassy-executor/src/raw/timer_queue.rs @@ -1,99 +1,25 @@ //! Timer queue operations. -use core::cmp::min; -use super::util::SyncUnsafeCell; +use core::cell::Cell; + use super::TaskRef; /// An item in the timer queue. pub struct TimerQueueItem { - next: SyncUnsafeCell>, - expires_at: SyncUnsafeCell, -} + /// The next item in the queue. + pub next: Cell>, -impl TimerQueueItem { - pub(crate) const fn new() -> Self { - Self { - next: SyncUnsafeCell::new(None), - expires_at: SyncUnsafeCell::new(0), - } - } + /// The time at which this item expires. + pub expires_at: Cell, } -/// A timer queue, with items integrated into tasks. -pub struct TimerQueue { - head: SyncUnsafeCell>, -} +unsafe impl Sync for TimerQueueItem {} -impl TimerQueue { - /// Creates a new timer queue. - pub const fn new() -> Self { +impl TimerQueueItem { + pub(crate) const fn new() -> Self { Self { - head: SyncUnsafeCell::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 { - unsafe { - 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 = unsafe { item.expires_at.get() }; - - if expires <= now { - // Timer expired, process task. - super::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) { - unsafe { - 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); - } - } + next: Cell::new(None), + expires_at: Cell::new(0), } } } -- 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-executor/src/raw/timer_queue.rs | 15 ++++++++++++++- 1 file changed, 14 insertions(+), 1 deletion(-) (limited to 'embassy-executor/src/raw/timer_queue.rs') diff --git a/embassy-executor/src/raw/timer_queue.rs b/embassy-executor/src/raw/timer_queue.rs index 46e346c1b..c36708401 100644 --- a/embassy-executor/src/raw/timer_queue.rs +++ b/embassy-executor/src/raw/timer_queue.rs @@ -7,6 +7,9 @@ use super::TaskRef; /// An item in the timer queue. pub struct TimerQueueItem { /// The next item in the queue. + /// + /// If this field contains `Some`, the item is in the queue. The last item in the queue has a + /// value of `Some(dangling_pointer)` pub next: Cell>, /// The time at which this item expires. @@ -19,7 +22,17 @@ impl TimerQueueItem { pub(crate) const fn new() -> Self { Self { next: Cell::new(None), - expires_at: Cell::new(0), + expires_at: Cell::new(u64::MAX), } } } + +/// The operation to perform after `timer_enqueue` is called. +#[derive(Debug, Copy, Clone, PartialEq)] +#[cfg_attr(feature = "defmt", derive(defmt::Format))] +pub enum TimerEnqueueOperation { + /// Enqueue the task. + Enqueue, + /// Update the task's expiration time. + Ignore, +} -- cgit From e861344b179b3e955ac47f1985b7f97fdfb93892 Mon Sep 17 00:00:00 2001 From: Dániel Buga Date: Sun, 15 Dec 2024 17:44:42 +0100 Subject: Fix comments and tweak task exit --- embassy-executor/src/raw/timer_queue.rs | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) (limited to 'embassy-executor/src/raw/timer_queue.rs') diff --git a/embassy-executor/src/raw/timer_queue.rs b/embassy-executor/src/raw/timer_queue.rs index c36708401..cd9a73822 100644 --- a/embassy-executor/src/raw/timer_queue.rs +++ b/embassy-executor/src/raw/timer_queue.rs @@ -30,9 +30,10 @@ impl TimerQueueItem { /// The operation to perform after `timer_enqueue` is called. #[derive(Debug, Copy, Clone, PartialEq)] #[cfg_attr(feature = "defmt", derive(defmt::Format))] +#[must_use] pub enum TimerEnqueueOperation { - /// Enqueue the task. + /// Enqueue the task (or update its expiration time). Enqueue, - /// Update the task's expiration time. + /// The task must not be enqueued in the timer queue. Ignore, } -- cgit From a10290b28e41922b0f53aafbcc82c49ee3f4e22f Mon Sep 17 00:00:00 2001 From: Dániel Buga Date: Mon, 16 Dec 2024 09:15:15 +0100 Subject: Zero-inizialize expires_at --- embassy-executor/src/raw/timer_queue.rs | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'embassy-executor/src/raw/timer_queue.rs') diff --git a/embassy-executor/src/raw/timer_queue.rs b/embassy-executor/src/raw/timer_queue.rs index cd9a73822..2ba0e00a9 100644 --- a/embassy-executor/src/raw/timer_queue.rs +++ b/embassy-executor/src/raw/timer_queue.rs @@ -22,7 +22,7 @@ impl TimerQueueItem { pub(crate) const fn new() -> Self { Self { next: Cell::new(None), - expires_at: Cell::new(u64::MAX), + expires_at: Cell::new(0), } } } -- cgit