From 535c80e61f17e4ee4605e00623aabeda2181352d Mon Sep 17 00:00:00 2001 From: James Munns Date: Thu, 20 Mar 2025 09:47:56 +0100 Subject: Add initial DRS scheduler placeholder * Start hacking in cordyceps This adds a third kind of runqueue, for now it should work the same as the current "atomics" runqueue, but uses a cordyceps TransferStack instead of the existing home-rolled linked list. * Clean up, use new cordyceps feature * A bit more cleanup * Update docs to be more clear --- embassy-executor/Cargo.toml | 9 ++++ embassy-executor/src/raw/mod.rs | 64 +++++++++++++++++++++-- embassy-executor/src/raw/run_queue_drs_atomics.rs | 47 +++++++++++++++++ 3 files changed, 116 insertions(+), 4 deletions(-) create mode 100644 embassy-executor/src/raw/run_queue_drs_atomics.rs (limited to 'embassy-executor') diff --git a/embassy-executor/Cargo.toml b/embassy-executor/Cargo.toml index 41636a26f..1cd732dfa 100644 --- a/embassy-executor/Cargo.toml +++ b/embassy-executor/Cargo.toml @@ -76,6 +76,12 @@ js-sys = { version = "0.3", optional = true } # arch-avr dependencies avr-device = { version = "0.7.0", optional = true } +[dependencies.cordyceps] +version = "0.3" +git = "https://github.com/hawkw/mycelium" +rev = "aaad19480d175bfc290f1d4dc2d435c6eb3d9fc5" +optional = true + [dev-dependencies] critical-section = { version = "1.1", features = ["std"] } trybuild = "1.0" @@ -125,3 +131,6 @@ trace = ["_any_trace"] ## Enable support for rtos-trace framework rtos-trace = ["_any_trace", "metadata-name", "dep:rtos-trace", "dep:embassy-time-driver"] _any_trace = [] + +## Enable "Deadline Rank Scheduler" +drs-scheduler = ["dep:cordyceps"] diff --git a/embassy-executor/src/raw/mod.rs b/embassy-executor/src/raw/mod.rs index 4280c5750..894a996ec 100644 --- a/embassy-executor/src/raw/mod.rs +++ b/embassy-executor/src/raw/mod.rs @@ -7,7 +7,14 @@ //! Using this module requires respecting subtle safety contracts. If you can, prefer using the safe //! [executor wrappers](crate::Executor) and the [`embassy_executor::task`](embassy_executor_macros::task) macro, which are fully safe. -#[cfg_attr(target_has_atomic = "ptr", path = "run_queue_atomics.rs")] +#[cfg_attr( + all(not(feature = "drs-scheduler"), target_has_atomic = "ptr"), + path = "run_queue_atomics.rs", +)] +#[cfg_attr( + all(feature = "drs-scheduler", target_has_atomic = "ptr"), + path = "run_queue_drs_atomics.rs", +)] #[cfg_attr(not(target_has_atomic = "ptr"), path = "run_queue_critical_section.rs")] mod run_queue; @@ -33,6 +40,8 @@ use core::marker::PhantomData; use core::mem; use core::pin::Pin; use core::ptr::NonNull; +#[cfg(feature = "drs-scheduler")] +use core::ptr::addr_of_mut; #[cfg(not(feature = "arch-avr"))] use core::sync::atomic::AtomicPtr; use core::sync::atomic::Ordering; @@ -42,7 +51,9 @@ use embassy_executor_timer_queue::TimerQueueItem; #[cfg(feature = "arch-avr")] use portable_atomic::AtomicPtr; -use self::run_queue::{RunQueue, RunQueueItem}; +use self::run_queue::RunQueue; +#[cfg(not(feature = "drs-scheduler"))] +use self::run_queue::RunQueueItem; use self::state::State; use self::util::{SyncUnsafeCell, UninitCell}; pub use self::waker::task_from_waker; @@ -54,6 +65,9 @@ extern "Rust" fn __embassy_time_queue_item_from_waker(waker: &Waker) -> &'static unsafe { task_from_waker(waker).timer_queue_item() } } +#[cfg(feature = "drs-scheduler")] +use cordyceps::{stack, Linked}; + /// Raw task header for use in task pointers. /// /// A task can be in one of the following states: @@ -93,9 +107,29 @@ extern "Rust" fn __embassy_time_queue_item_from_waker(waker: &Waker) -> &'static /// - 4: A run-queued task exits - `TaskStorage::poll -> Poll::Ready` /// - 5: Task is dequeued. The task's future is not polled, because exiting the task replaces its `poll_fn`. /// - 6: A task is waken when it is not spawned - `wake_task -> State::run_enqueue` +#[cfg_attr(feature = "drs-scheduler", repr(C))] pub(crate) struct TaskHeader { - pub(crate) state: State, + // TODO(AJM): Make a decision whether we want to support the spicier "pointer recast"/"type punning" + // method of implementing the `cordyceps::Linked` trait or not. + // + // Currently, I do the safer version with `addr_of_mut!`, which doesn't REQUIRE that the first + // element is the `links` field, at the potential cost of a little extra pointer math. + // + // The optimizer *might* (total guess) notice that we are always doing an offset of zero in the + // call to `addr_of_mut` in the `impl Linked for TaskHeader` below, and get the best of both worlds, + // but right now this is maybe a little over cautious. + // + // See https://docs.rs/cordyceps/latest/cordyceps/trait.Linked.html#implementing-linkedlinks for + // more context on the choices here. + #[cfg(feature = "drs-scheduler")] + pub(crate) links: stack::Links, + + // TODO(AJM): We could potentially replace RunQueueItem for other runqueue impls, though + // right now cordyceps doesn't work on non-atomic systems + #[cfg(not(feature = "drs-scheduler"))] pub(crate) run_queue_item: RunQueueItem, + + pub(crate) state: State, pub(crate) executor: AtomicPtr, poll_fn: SyncUnsafeCell>, @@ -108,6 +142,25 @@ pub(crate) struct TaskHeader { all_tasks_next: AtomicPtr, } +#[cfg(feature = "drs-scheduler")] +unsafe impl Linked> for TaskHeader { + type Handle = TaskRef; + + fn into_ptr(r: Self::Handle) -> NonNull { + r.ptr.cast() + } + + unsafe fn from_ptr(ptr: NonNull) -> Self::Handle { + let ptr: NonNull = ptr; + TaskRef { ptr } + } + + unsafe fn links(ptr: NonNull) -> NonNull> { + let ptr: *mut TaskHeader = ptr.as_ptr(); + NonNull::new_unchecked(addr_of_mut!((*ptr).links)) + } +} + /// This is essentially a `&'static TaskStorage` where the type of the future has been erased. #[derive(Debug, Clone, Copy, PartialEq)] pub struct TaskRef { @@ -198,8 +251,11 @@ impl TaskStorage { pub const fn new() -> Self { Self { raw: TaskHeader { - state: State::new(), + #[cfg(not(feature = "drs-scheduler"))] run_queue_item: RunQueueItem::new(), + #[cfg(feature = "drs-scheduler")] + links: stack::Links::new(), + state: State::new(), executor: AtomicPtr::new(core::ptr::null_mut()), // Note: this is lazily initialized so that a static `TaskStorage` will go in `.bss` poll_fn: SyncUnsafeCell::new(None), diff --git a/embassy-executor/src/raw/run_queue_drs_atomics.rs b/embassy-executor/src/raw/run_queue_drs_atomics.rs new file mode 100644 index 000000000..53ada1b14 --- /dev/null +++ b/embassy-executor/src/raw/run_queue_drs_atomics.rs @@ -0,0 +1,47 @@ +use super::{TaskHeader, TaskRef}; +use cordyceps::TransferStack; + + +/// Atomic task queue using a very, very simple lock-free linked-list queue: +/// +/// To enqueue a task, task.next is set to the old head, and head is atomically set to task. +/// +/// Dequeuing is done in batches: the queue is emptied by atomically replacing head with +/// null. Then the batch is iterated following the next pointers until null is reached. +/// +/// Note that batches will be iterated in the reverse order as they were enqueued. This is OK +/// for our purposes: it can't create fairness problems since the next batch won't run until the +/// current batch is completely processed, so even if a task enqueues itself instantly (for example +/// by waking its own waker) can't prevent other tasks from running. +pub(crate) struct RunQueue { + stack: TransferStack, +} + +impl RunQueue { + pub const fn new() -> Self { + Self { + stack: TransferStack::new(), + } + } + + /// Enqueues an item. Returns true if the queue was empty. + /// + /// # Safety + /// + /// `item` must NOT be already enqueued in any queue. + #[inline(always)] + pub(crate) unsafe fn enqueue(&self, task: TaskRef, _: super::state::Token) -> bool { + self.stack.push_was_empty(task) + } + + /// Empty the queue, then call `on_task` for each task that was in the queue. + /// NOTE: It is OK for `on_task` to enqueue more tasks. In this case they're left in the queue + /// and will be processed by the *next* call to `dequeue_all`, *not* the current one. + pub(crate) fn dequeue_all(&self, on_task: impl Fn(TaskRef)) { + let taken = self.stack.take_all(); + for taskref in taken { + taskref.header().state.run_dequeue(); + on_task(taskref); + } + } +} -- cgit From 1f50e4d496458dbc7fccd9d028217ebfa7735471 Mon Sep 17 00:00:00 2001 From: James Munns Date: Thu, 20 Mar 2025 14:32:14 +0100 Subject: Implement Deadline Ranked Scheduling This implements a minimal version of Deadline Rank Scheduling, as well as ways to access and set Deadlines. This still needs some UX improvements, but is likely Enough for testing. --- embassy-executor/Cargo.toml | 3 +- embassy-executor/src/raw/mod.rs | 12 ++ embassy-executor/src/raw/run_queue_drs_atomics.rs | 141 +++++++++++++++++++++- 3 files changed, 150 insertions(+), 6 deletions(-) (limited to 'embassy-executor') diff --git a/embassy-executor/Cargo.toml b/embassy-executor/Cargo.toml index 1cd732dfa..db664a819 100644 --- a/embassy-executor/Cargo.toml +++ b/embassy-executor/Cargo.toml @@ -89,7 +89,6 @@ embassy-sync = { path = "../embassy-sync" } rustversion = "1.0.21" [features] - ## Enable nightly-only features nightly = ["embassy-executor-macros/nightly"] @@ -133,4 +132,4 @@ rtos-trace = ["_any_trace", "metadata-name", "dep:rtos-trace", "dep:embassy-time _any_trace = [] ## Enable "Deadline Rank Scheduler" -drs-scheduler = ["dep:cordyceps"] +drs-scheduler = ["dep:cordyceps", "dep:embassy-time-driver"] diff --git a/embassy-executor/src/raw/mod.rs b/embassy-executor/src/raw/mod.rs index 894a996ec..9b8a4ea8a 100644 --- a/embassy-executor/src/raw/mod.rs +++ b/embassy-executor/src/raw/mod.rs @@ -68,6 +68,9 @@ extern "Rust" fn __embassy_time_queue_item_from_waker(waker: &Waker) -> &'static #[cfg(feature = "drs-scheduler")] use cordyceps::{stack, Linked}; +#[cfg(feature = "drs-scheduler")] +pub use run_queue::Deadline; + /// Raw task header for use in task pointers. /// /// A task can be in one of the following states: @@ -124,6 +127,9 @@ pub(crate) struct TaskHeader { #[cfg(feature = "drs-scheduler")] pub(crate) links: stack::Links, + #[cfg(feature = "drs-scheduler")] + pub(crate) deadline: SyncUnsafeCell, + // TODO(AJM): We could potentially replace RunQueueItem for other runqueue impls, though // right now cordyceps doesn't work on non-atomic systems #[cfg(not(feature = "drs-scheduler"))] @@ -255,6 +261,8 @@ impl TaskStorage { run_queue_item: RunQueueItem::new(), #[cfg(feature = "drs-scheduler")] links: stack::Links::new(), + #[cfg(feature = "drs-scheduler")] + deadline: SyncUnsafeCell::new(0u64), state: State::new(), executor: AtomicPtr::new(core::ptr::null_mut()), // Note: this is lazily initialized so that a static `TaskStorage` will go in `.bss` @@ -352,6 +360,10 @@ impl AvailableTask { self.task.raw.poll_fn.set(Some(TaskStorage::::poll)); self.task.future.write_in_place(future); + // TODO(AJM): Some other way of setting this? Just a placeholder + #[cfg(feature = "drs-scheduler")] + self.task.raw.deadline.set(u64::MAX); + let task = TaskRef::new(self.task); SpawnToken::new(task) diff --git a/embassy-executor/src/raw/run_queue_drs_atomics.rs b/embassy-executor/src/raw/run_queue_drs_atomics.rs index 53ada1b14..69b7b3bf0 100644 --- a/embassy-executor/src/raw/run_queue_drs_atomics.rs +++ b/embassy-executor/src/raw/run_queue_drs_atomics.rs @@ -1,6 +1,7 @@ use super::{TaskHeader, TaskRef}; -use cordyceps::TransferStack; - +use cordyceps::{SortedList, TransferStack}; +use core::future::{Future, poll_fn}; +use core::task::Poll; /// Atomic task queue using a very, very simple lock-free linked-list queue: /// @@ -38,10 +39,142 @@ impl RunQueue { /// NOTE: It is OK for `on_task` to enqueue more tasks. In this case they're left in the queue /// and will be processed by the *next* call to `dequeue_all`, *not* the current one. pub(crate) fn dequeue_all(&self, on_task: impl Fn(TaskRef)) { - let taken = self.stack.take_all(); - for taskref in taken { + let mut sorted = SortedList::::new(|lhs, rhs| unsafe { + // TODO: Do we need any kind of access control here? Not if we say that + // tasks can only set their own priority, which they can't do if we're in + // the scheduler + lhs.deadline.get().cmp(&rhs.deadline.get()) + }); + + loop { + // For each loop, grab any newly pended items + let taken = self.stack.take_all(); + + // Sort these into the list - this is potentially expensive! We do an + // insertion sort of new items, which iterates the linked list. + // + // Something on the order of `O(n * m)`, where `n` is the number + // of new tasks, and `m` is the number of already pending tasks. + sorted.extend(taken); + + // Pop the task with the SOONEST deadline. If there are no tasks + // pending, then we are done. + let Some(taskref) = sorted.pop_front() else { + return; + }; + + // We got one task, mark it as dequeued, and process the task. taskref.header().state.run_dequeue(); on_task(taskref); } } } + +/// A type for interacting with the deadline of the current task +pub struct Deadline { + /// Deadline value in ticks, same time base and ticks as `embassy-time` + pub instant_ticks: u64, +} + +impl Deadline { + /// Set the current task's deadline at exactly `instant_ticks` + /// + /// This method is a future in order to access the currently executing task's + /// header which contains the deadline. + /// + /// Analogous to `Timer::at`. + /// + /// TODO: Should we check/panic if the deadline is in the past? + #[must_use = "Setting deadline must be polled to be effective"] + pub fn set_current_task_deadline(instant_ticks: u64) -> impl Future { + poll_fn(move |cx| { + let task = super::task_from_waker(cx.waker()); + // SAFETY: A task can only modify its own deadline, while the task is being + // polled, meaning that there cannot be concurrent access to the deadline. + unsafe { + task.header().deadline.set(instant_ticks); + } + Poll::Ready(()) + }) + } + + /// Set the current task's deadline `duration_ticks` in the future from when + /// this future is polled. + /// + /// This method is a future in order to access the currently executing task's + /// header which contains the deadline + /// + /// Analogous to `Timer::after` + /// + /// TODO: Do we want to return what the deadline is? + #[must_use = "Setting deadline must be polled to be effective"] + pub fn set_current_task_deadline_after(duration_ticks: u64) -> impl Future { + poll_fn(move |cx| { + let task = super::task_from_waker(cx.waker()); + let now = embassy_time_driver::now(); + + // Since ticks is a u64, saturating add is PROBABLY overly cautious, leave + // it for now, we can probably make this wrapping_add for performance + // reasons later. + let deadline = now.saturating_add(duration_ticks); + + // SAFETY: A task can only modify its own deadline, while the task is being + // polled, meaning that there cannot be concurrent access to the deadline. + unsafe { + task.header().deadline.set(deadline); + } + Poll::Ready(()) + }) + } + + /// Set the current task's deadline `increment_ticks` from the previous deadline. + /// + /// Note that by default (unless otherwise set), tasks start life with the deadline + /// u64::MAX, which means this method will have no effect. + /// + /// This method is a future in order to access the currently executing task's + /// header which contains the deadline + /// + /// Analogous to one increment of `Ticker::every().next()`. + /// + /// TODO: Do we want to return what the deadline is? + #[must_use = "Setting deadline must be polled to be effective"] + pub fn increment_current_task_deadline(increment_ticks: u64) -> impl Future { + poll_fn(move |cx| { + let task = super::task_from_waker(cx.waker()); + + // SAFETY: A task can only modify its own deadline, while the task is being + // polled, meaning that there cannot be concurrent access to the deadline. + unsafe { + // Get the last value + let last = task.header().deadline.get(); + + // Since ticks is a u64, saturating add is PROBABLY overly cautious, leave + // it for now, we can probably make this wrapping_add for performance + // reasons later. + let deadline = last.saturating_add(increment_ticks); + + // Store the new value + task.header().deadline.set(deadline); + } + Poll::Ready(()) + }) + } + + /// Get the current task's deadline as a tick value. + /// + /// This method is a future in order to access the currently executing task's + /// header which contains the deadline + pub fn get_current_task_deadline() -> impl Future { + poll_fn(move |cx| { + let task = super::task_from_waker(cx.waker()); + + // SAFETY: A task can only modify its own deadline, while the task is being + // polled, meaning that there cannot be concurrent access to the deadline. + let deadline = unsafe { + task.header().deadline.get() + }; + Poll::Ready(Self { instant_ticks: deadline }) + }) + } +} -- cgit From 8c70aafd4be63ff7af895f116444fb81438ae6e0 Mon Sep 17 00:00:00 2001 From: James Munns Date: Tue, 1 Apr 2025 18:35:41 +0200 Subject: Make some things more consistent --- embassy-executor/Cargo.toml | 4 +- embassy-executor/src/raw/mod.rs | 53 ++--------------------- embassy-executor/src/raw/run_queue_drs_atomics.rs | 31 +++++++++++-- 3 files changed, 34 insertions(+), 54 deletions(-) (limited to 'embassy-executor') diff --git a/embassy-executor/Cargo.toml b/embassy-executor/Cargo.toml index db664a819..80b5867c9 100644 --- a/embassy-executor/Cargo.toml +++ b/embassy-executor/Cargo.toml @@ -77,9 +77,11 @@ js-sys = { version = "0.3", optional = true } avr-device = { version = "0.7.0", optional = true } [dependencies.cordyceps] +# note: targeting v0.3.3, to be released when +# https://github.com/hawkw/mycelium/pull/520 is merged version = "0.3" git = "https://github.com/hawkw/mycelium" -rev = "aaad19480d175bfc290f1d4dc2d435c6eb3d9fc5" +rev = "9649db0525b9972b95937d83d52d3f51cc486281" optional = true [dev-dependencies] diff --git a/embassy-executor/src/raw/mod.rs b/embassy-executor/src/raw/mod.rs index 9b8a4ea8a..2e5941ef7 100644 --- a/embassy-executor/src/raw/mod.rs +++ b/embassy-executor/src/raw/mod.rs @@ -40,7 +40,6 @@ use core::marker::PhantomData; use core::mem; use core::pin::Pin; use core::ptr::NonNull; -#[cfg(feature = "drs-scheduler")] use core::ptr::addr_of_mut; #[cfg(not(feature = "arch-avr"))] use core::sync::atomic::AtomicPtr; @@ -51,9 +50,7 @@ use embassy_executor_timer_queue::TimerQueueItem; #[cfg(feature = "arch-avr")] use portable_atomic::AtomicPtr; -use self::run_queue::RunQueue; -#[cfg(not(feature = "drs-scheduler"))] -use self::run_queue::RunQueueItem; +use self::run_queue::{RunQueue, RunQueueItem}; use self::state::State; use self::util::{SyncUnsafeCell, UninitCell}; pub use self::waker::task_from_waker; @@ -65,9 +62,6 @@ extern "Rust" fn __embassy_time_queue_item_from_waker(waker: &Waker) -> &'static unsafe { task_from_waker(waker).timer_queue_item() } } -#[cfg(feature = "drs-scheduler")] -use cordyceps::{stack, Linked}; - #[cfg(feature = "drs-scheduler")] pub use run_queue::Deadline; @@ -110,31 +104,14 @@ pub use run_queue::Deadline; /// - 4: A run-queued task exits - `TaskStorage::poll -> Poll::Ready` /// - 5: Task is dequeued. The task's future is not polled, because exiting the task replaces its `poll_fn`. /// - 6: A task is waken when it is not spawned - `wake_task -> State::run_enqueue` -#[cfg_attr(feature = "drs-scheduler", repr(C))] pub(crate) struct TaskHeader { - // TODO(AJM): Make a decision whether we want to support the spicier "pointer recast"/"type punning" - // method of implementing the `cordyceps::Linked` trait or not. - // - // Currently, I do the safer version with `addr_of_mut!`, which doesn't REQUIRE that the first - // element is the `links` field, at the potential cost of a little extra pointer math. - // - // The optimizer *might* (total guess) notice that we are always doing an offset of zero in the - // call to `addr_of_mut` in the `impl Linked for TaskHeader` below, and get the best of both worlds, - // but right now this is maybe a little over cautious. - // - // See https://docs.rs/cordyceps/latest/cordyceps/trait.Linked.html#implementing-linkedlinks for - // more context on the choices here. - #[cfg(feature = "drs-scheduler")] - pub(crate) links: stack::Links, + pub(crate) run_queue_item: RunQueueItem, #[cfg(feature = "drs-scheduler")] + /// Deadline Rank Scheduler Deadline. This field should not be accessed outside the context of + /// the task itself as it being polled by the executor. pub(crate) deadline: SyncUnsafeCell, - // TODO(AJM): We could potentially replace RunQueueItem for other runqueue impls, though - // right now cordyceps doesn't work on non-atomic systems - #[cfg(not(feature = "drs-scheduler"))] - pub(crate) run_queue_item: RunQueueItem, - pub(crate) state: State, pub(crate) executor: AtomicPtr, poll_fn: SyncUnsafeCell>, @@ -148,25 +125,6 @@ pub(crate) struct TaskHeader { all_tasks_next: AtomicPtr, } -#[cfg(feature = "drs-scheduler")] -unsafe impl Linked> for TaskHeader { - type Handle = TaskRef; - - fn into_ptr(r: Self::Handle) -> NonNull { - r.ptr.cast() - } - - unsafe fn from_ptr(ptr: NonNull) -> Self::Handle { - let ptr: NonNull = ptr; - TaskRef { ptr } - } - - unsafe fn links(ptr: NonNull) -> NonNull> { - let ptr: *mut TaskHeader = ptr.as_ptr(); - NonNull::new_unchecked(addr_of_mut!((*ptr).links)) - } -} - /// This is essentially a `&'static TaskStorage` where the type of the future has been erased. #[derive(Debug, Clone, Copy, PartialEq)] pub struct TaskRef { @@ -257,11 +215,8 @@ impl TaskStorage { pub const fn new() -> Self { Self { raw: TaskHeader { - #[cfg(not(feature = "drs-scheduler"))] run_queue_item: RunQueueItem::new(), #[cfg(feature = "drs-scheduler")] - links: stack::Links::new(), - #[cfg(feature = "drs-scheduler")] deadline: SyncUnsafeCell::new(0u64), state: State::new(), executor: AtomicPtr::new(core::ptr::null_mut()), diff --git a/embassy-executor/src/raw/run_queue_drs_atomics.rs b/embassy-executor/src/raw/run_queue_drs_atomics.rs index 69b7b3bf0..047265954 100644 --- a/embassy-executor/src/raw/run_queue_drs_atomics.rs +++ b/embassy-executor/src/raw/run_queue_drs_atomics.rs @@ -2,6 +2,29 @@ use super::{TaskHeader, TaskRef}; use cordyceps::{SortedList, TransferStack}; use core::future::{Future, poll_fn}; use core::task::Poll; +use core::ptr::{addr_of_mut, NonNull}; +use cordyceps::sorted_list::Links; +use cordyceps::Linked; + +pub(crate) type RunQueueItem = Links; + +unsafe impl Linked> for super::TaskHeader { + type Handle = TaskRef; + + fn into_ptr(r: Self::Handle) -> NonNull { + r.ptr.cast() + } + + unsafe fn from_ptr(ptr: NonNull) -> Self::Handle { + let ptr: NonNull = ptr; + TaskRef { ptr } + } + + unsafe fn links(ptr: NonNull) -> NonNull> { + let ptr: *mut TaskHeader = ptr.as_ptr(); + NonNull::new_unchecked(addr_of_mut!((*ptr).run_queue_item)) + } +} /// Atomic task queue using a very, very simple lock-free linked-list queue: /// @@ -39,10 +62,10 @@ impl RunQueue { /// NOTE: It is OK for `on_task` to enqueue more tasks. In this case they're left in the queue /// and will be processed by the *next* call to `dequeue_all`, *not* the current one. pub(crate) fn dequeue_all(&self, on_task: impl Fn(TaskRef)) { - let mut sorted = SortedList::::new(|lhs, rhs| unsafe { - // TODO: Do we need any kind of access control here? Not if we say that - // tasks can only set their own priority, which they can't do if we're in - // the scheduler + // SAFETY: `deadline` can only be set through the `Deadline` interface, which + // only allows access to this value while the given task is being polled. + // This acts as mutual exclusion for access. + let mut sorted = SortedList::::new_custom(|lhs, rhs| unsafe { lhs.deadline.get().cmp(&rhs.deadline.get()) }); -- cgit From ba0426f767bb602750bed4fae87a156b661c0e92 Mon Sep 17 00:00:00 2001 From: James Munns Date: Tue, 1 Apr 2025 18:50:12 +0200 Subject: Combine DRS and non-DRS atomic scheduler, using cordyceps --- embassy-executor/src/raw/deadline.rs | 111 ++++++++++++ embassy-executor/src/raw/mod.rs | 18 +- embassy-executor/src/raw/run_queue_atomics.rs | 110 +++++++----- embassy-executor/src/raw/run_queue_drs_atomics.rs | 203 ---------------------- 4 files changed, 186 insertions(+), 256 deletions(-) create mode 100644 embassy-executor/src/raw/deadline.rs delete mode 100644 embassy-executor/src/raw/run_queue_drs_atomics.rs (limited to 'embassy-executor') diff --git a/embassy-executor/src/raw/deadline.rs b/embassy-executor/src/raw/deadline.rs new file mode 100644 index 000000000..3f60936cc --- /dev/null +++ b/embassy-executor/src/raw/deadline.rs @@ -0,0 +1,111 @@ +use core::future::{poll_fn, Future}; +use core::task::Poll; + +/// A type for interacting with the deadline of the current task +pub struct Deadline { + /// Deadline value in ticks, same time base and ticks as `embassy-time` + pub instant_ticks: u64, +} + +impl Deadline { + /// Set the current task's deadline at exactly `instant_ticks` + /// + /// This method is a future in order to access the currently executing task's + /// header which contains the deadline. + /// + /// Analogous to `Timer::at`. + /// + /// TODO: Should we check/panic if the deadline is in the past? + #[must_use = "Setting deadline must be polled to be effective"] + pub fn set_current_task_deadline(instant_ticks: u64) -> impl Future { + poll_fn(move |cx| { + let task = super::task_from_waker(cx.waker()); + // SAFETY: A task can only modify its own deadline, while the task is being + // polled, meaning that there cannot be concurrent access to the deadline. + unsafe { + task.header().deadline.set(instant_ticks); + } + Poll::Ready(()) + }) + } + + /// Set the current task's deadline `duration_ticks` in the future from when + /// this future is polled. + /// + /// This method is a future in order to access the currently executing task's + /// header which contains the deadline + /// + /// Analogous to `Timer::after` + /// + /// TODO: Do we want to return what the deadline is? + #[must_use = "Setting deadline must be polled to be effective"] + pub fn set_current_task_deadline_after(duration_ticks: u64) -> impl Future { + poll_fn(move |cx| { + let task = super::task_from_waker(cx.waker()); + let now = embassy_time_driver::now(); + + // Since ticks is a u64, saturating add is PROBABLY overly cautious, leave + // it for now, we can probably make this wrapping_add for performance + // reasons later. + let deadline = now.saturating_add(duration_ticks); + + // SAFETY: A task can only modify its own deadline, while the task is being + // polled, meaning that there cannot be concurrent access to the deadline. + unsafe { + task.header().deadline.set(deadline); + } + Poll::Ready(()) + }) + } + + /// Set the current task's deadline `increment_ticks` from the previous deadline. + /// + /// Note that by default (unless otherwise set), tasks start life with the deadline + /// u64::MAX, which means this method will have no effect. + /// + /// This method is a future in order to access the currently executing task's + /// header which contains the deadline + /// + /// Analogous to one increment of `Ticker::every().next()`. + /// + /// TODO: Do we want to return what the deadline is? + #[must_use = "Setting deadline must be polled to be effective"] + pub fn increment_current_task_deadline(increment_ticks: u64) -> impl Future { + poll_fn(move |cx| { + let task = super::task_from_waker(cx.waker()); + + // SAFETY: A task can only modify its own deadline, while the task is being + // polled, meaning that there cannot be concurrent access to the deadline. + unsafe { + // Get the last value + let last = task.header().deadline.get(); + + // Since ticks is a u64, saturating add is PROBABLY overly cautious, leave + // it for now, we can probably make this wrapping_add for performance + // reasons later. + let deadline = last.saturating_add(increment_ticks); + + // Store the new value + task.header().deadline.set(deadline); + } + Poll::Ready(()) + }) + } + + /// Get the current task's deadline as a tick value. + /// + /// This method is a future in order to access the currently executing task's + /// header which contains the deadline + pub fn get_current_task_deadline() -> impl Future { + poll_fn(move |cx| { + let task = super::task_from_waker(cx.waker()); + + // SAFETY: A task can only modify its own deadline, while the task is being + // polled, meaning that there cannot be concurrent access to the deadline. + let deadline = unsafe { task.header().deadline.get() }; + Poll::Ready(Self { + instant_ticks: deadline, + }) + }) + } +} diff --git a/embassy-executor/src/raw/mod.rs b/embassy-executor/src/raw/mod.rs index 2e5941ef7..0dd247d30 100644 --- a/embassy-executor/src/raw/mod.rs +++ b/embassy-executor/src/raw/mod.rs @@ -7,14 +7,7 @@ //! Using this module requires respecting subtle safety contracts. If you can, prefer using the safe //! [executor wrappers](crate::Executor) and the [`embassy_executor::task`](embassy_executor_macros::task) macro, which are fully safe. -#[cfg_attr( - all(not(feature = "drs-scheduler"), target_has_atomic = "ptr"), - path = "run_queue_atomics.rs", -)] -#[cfg_attr( - all(feature = "drs-scheduler", target_has_atomic = "ptr"), - path = "run_queue_drs_atomics.rs", -)] +#[cfg_attr(target_has_atomic = "ptr", path = "run_queue_atomics.rs")] #[cfg_attr(not(target_has_atomic = "ptr"), path = "run_queue_critical_section.rs")] mod run_queue; @@ -35,6 +28,9 @@ pub(crate) mod util; #[cfg_attr(feature = "turbowakers", path = "waker_turbo.rs")] mod waker; +#[cfg(feature = "drs-scheduler")] +mod deadline; + use core::future::Future; use core::marker::PhantomData; use core::mem; @@ -50,6 +46,9 @@ use embassy_executor_timer_queue::TimerQueueItem; #[cfg(feature = "arch-avr")] use portable_atomic::AtomicPtr; +#[cfg(feature = "drs-scheduler")] +pub use deadline::Deadline; + use self::run_queue::{RunQueue, RunQueueItem}; use self::state::State; use self::util::{SyncUnsafeCell, UninitCell}; @@ -62,9 +61,6 @@ extern "Rust" fn __embassy_time_queue_item_from_waker(waker: &Waker) -> &'static unsafe { task_from_waker(waker).timer_queue_item() } } -#[cfg(feature = "drs-scheduler")] -pub use run_queue::Deadline; - /// Raw task header for use in task pointers. /// /// A task can be in one of the following states: diff --git a/embassy-executor/src/raw/run_queue_atomics.rs b/embassy-executor/src/raw/run_queue_atomics.rs index ce511d79a..bc5d38250 100644 --- a/embassy-executor/src/raw/run_queue_atomics.rs +++ b/embassy-executor/src/raw/run_queue_atomics.rs @@ -1,19 +1,36 @@ -use core::ptr; -use core::ptr::NonNull; -use core::sync::atomic::{AtomicPtr, Ordering}; +use core::ptr::{addr_of_mut, NonNull}; + +use cordyceps::sorted_list::Links; +use cordyceps::{Linked, SortedList, TransferStack}; use super::{TaskHeader, TaskRef}; -use crate::raw::util::SyncUnsafeCell; -pub(crate) struct RunQueueItem { - next: SyncUnsafeCell>, -} +/// Use `cordyceps::sorted_list::Links` as the singly linked list +/// for RunQueueItems. +pub(crate) type RunQueueItem = Links; -impl RunQueueItem { - pub const fn new() -> Self { - Self { - next: SyncUnsafeCell::new(None), - } +/// Implements the `Linked` trait, allowing for singly linked list usage +/// of any of cordyceps' `TransferStack` (used for the atomic runqueue), +/// `SortedList` (used with the DRS scheduler), or `Stack`, which is +/// popped atomically from the `TransferStack`. +unsafe impl Linked> for TaskHeader { + type Handle = TaskRef; + + // Convert a TaskRef into a TaskHeader ptr + fn into_ptr(r: TaskRef) -> NonNull { + r.ptr + } + + // Convert a TaskHeader into a TaskRef + unsafe fn from_ptr(ptr: NonNull) -> TaskRef { + TaskRef { ptr } + } + + // Given a pointer to a TaskHeader, obtain a pointer to the Links structure, + // which can be used to traverse to other TaskHeader nodes in the linked list + unsafe fn links(ptr: NonNull) -> NonNull> { + let ptr: *mut TaskHeader = ptr.as_ptr(); + NonNull::new_unchecked(addr_of_mut!((*ptr).run_queue_item)) } } @@ -29,13 +46,13 @@ impl RunQueueItem { /// current batch is completely processed, so even if a task enqueues itself instantly (for example /// by waking its own waker) can't prevent other tasks from running. pub(crate) struct RunQueue { - head: AtomicPtr, + stack: TransferStack, } impl RunQueue { pub const fn new() -> Self { Self { - head: AtomicPtr::new(ptr::null_mut()), + stack: TransferStack::new(), } } @@ -46,43 +63,52 @@ impl RunQueue { /// `item` must NOT be already enqueued in any queue. #[inline(always)] pub(crate) unsafe fn enqueue(&self, task: TaskRef, _: super::state::Token) -> bool { - let mut was_empty = false; - - self.head - .fetch_update(Ordering::SeqCst, Ordering::SeqCst, |prev| { - was_empty = prev.is_null(); - unsafe { - // safety: the pointer is either null or valid - let prev = NonNull::new(prev).map(|ptr| TaskRef::from_ptr(ptr.as_ptr())); - // safety: there are no concurrent accesses to `next` - task.header().run_queue_item.next.set(prev); - } - Some(task.as_ptr() as *mut _) - }) - .ok(); - - was_empty + self.stack.push_was_empty(task) } /// Empty the queue, then call `on_task` for each task that was in the queue. /// NOTE: It is OK for `on_task` to enqueue more tasks. In this case they're left in the queue /// and will be processed by the *next* call to `dequeue_all`, *not* the current one. + #[cfg(not(feature = "drs-scheduler"))] pub(crate) fn dequeue_all(&self, on_task: impl Fn(TaskRef)) { - // Atomically empty the queue. - let ptr = self.head.swap(ptr::null_mut(), Ordering::AcqRel); + let taken = self.stack.take_all(); + for taskref in taken { + taskref.header().state.run_dequeue(); + on_task(taskref); + } + } + + /// Empty the queue, then call `on_task` for each task that was in the queue. + /// NOTE: It is OK for `on_task` to enqueue more tasks. In this case they're left in the queue + /// and will be processed by the *next* call to `dequeue_all`, *not* the current one. + #[cfg(feature = "drs-scheduler")] + pub(crate) fn dequeue_all(&self, on_task: impl Fn(TaskRef)) { + // SAFETY: `deadline` can only be set through the `Deadline` interface, which + // only allows access to this value while the given task is being polled. + // This acts as mutual exclusion for access. + let mut sorted = + SortedList::::new_custom(|lhs, rhs| unsafe { lhs.deadline.get().cmp(&rhs.deadline.get()) }); + + loop { + // For each loop, grab any newly pended items + let taken = self.stack.take_all(); - // safety: the pointer is either null or valid - let mut next = unsafe { NonNull::new(ptr).map(|ptr| TaskRef::from_ptr(ptr.as_ptr())) }; + // Sort these into the list - this is potentially expensive! We do an + // insertion sort of new items, which iterates the linked list. + // + // Something on the order of `O(n * m)`, where `n` is the number + // of new tasks, and `m` is the number of already pending tasks. + sorted.extend(taken); - // Iterate the linked list of tasks that were previously in the queue. - while let Some(task) = next { - // If the task re-enqueues itself, the `next` pointer will get overwritten. - // Therefore, first read the next pointer, and only then process the task. - // safety: there are no concurrent accesses to `next` - next = unsafe { task.header().run_queue_item.next.get() }; + // Pop the task with the SOONEST deadline. If there are no tasks + // pending, then we are done. + let Some(taskref) = sorted.pop_front() else { + return; + }; - task.header().state.run_dequeue(); - on_task(task); + // We got one task, mark it as dequeued, and process the task. + taskref.header().state.run_dequeue(); + on_task(taskref); } } } diff --git a/embassy-executor/src/raw/run_queue_drs_atomics.rs b/embassy-executor/src/raw/run_queue_drs_atomics.rs deleted file mode 100644 index 047265954..000000000 --- a/embassy-executor/src/raw/run_queue_drs_atomics.rs +++ /dev/null @@ -1,203 +0,0 @@ -use super::{TaskHeader, TaskRef}; -use cordyceps::{SortedList, TransferStack}; -use core::future::{Future, poll_fn}; -use core::task::Poll; -use core::ptr::{addr_of_mut, NonNull}; -use cordyceps::sorted_list::Links; -use cordyceps::Linked; - -pub(crate) type RunQueueItem = Links; - -unsafe impl Linked> for super::TaskHeader { - type Handle = TaskRef; - - fn into_ptr(r: Self::Handle) -> NonNull { - r.ptr.cast() - } - - unsafe fn from_ptr(ptr: NonNull) -> Self::Handle { - let ptr: NonNull = ptr; - TaskRef { ptr } - } - - unsafe fn links(ptr: NonNull) -> NonNull> { - let ptr: *mut TaskHeader = ptr.as_ptr(); - NonNull::new_unchecked(addr_of_mut!((*ptr).run_queue_item)) - } -} - -/// Atomic task queue using a very, very simple lock-free linked-list queue: -/// -/// To enqueue a task, task.next is set to the old head, and head is atomically set to task. -/// -/// Dequeuing is done in batches: the queue is emptied by atomically replacing head with -/// null. Then the batch is iterated following the next pointers until null is reached. -/// -/// Note that batches will be iterated in the reverse order as they were enqueued. This is OK -/// for our purposes: it can't create fairness problems since the next batch won't run until the -/// current batch is completely processed, so even if a task enqueues itself instantly (for example -/// by waking its own waker) can't prevent other tasks from running. -pub(crate) struct RunQueue { - stack: TransferStack, -} - -impl RunQueue { - pub const fn new() -> Self { - Self { - stack: TransferStack::new(), - } - } - - /// Enqueues an item. Returns true if the queue was empty. - /// - /// # Safety - /// - /// `item` must NOT be already enqueued in any queue. - #[inline(always)] - pub(crate) unsafe fn enqueue(&self, task: TaskRef, _: super::state::Token) -> bool { - self.stack.push_was_empty(task) - } - - /// Empty the queue, then call `on_task` for each task that was in the queue. - /// NOTE: It is OK for `on_task` to enqueue more tasks. In this case they're left in the queue - /// and will be processed by the *next* call to `dequeue_all`, *not* the current one. - pub(crate) fn dequeue_all(&self, on_task: impl Fn(TaskRef)) { - // SAFETY: `deadline` can only be set through the `Deadline` interface, which - // only allows access to this value while the given task is being polled. - // This acts as mutual exclusion for access. - let mut sorted = SortedList::::new_custom(|lhs, rhs| unsafe { - lhs.deadline.get().cmp(&rhs.deadline.get()) - }); - - loop { - // For each loop, grab any newly pended items - let taken = self.stack.take_all(); - - // Sort these into the list - this is potentially expensive! We do an - // insertion sort of new items, which iterates the linked list. - // - // Something on the order of `O(n * m)`, where `n` is the number - // of new tasks, and `m` is the number of already pending tasks. - sorted.extend(taken); - - // Pop the task with the SOONEST deadline. If there are no tasks - // pending, then we are done. - let Some(taskref) = sorted.pop_front() else { - return; - }; - - // We got one task, mark it as dequeued, and process the task. - taskref.header().state.run_dequeue(); - on_task(taskref); - } - } -} - -/// A type for interacting with the deadline of the current task -pub struct Deadline { - /// Deadline value in ticks, same time base and ticks as `embassy-time` - pub instant_ticks: u64, -} - -impl Deadline { - /// Set the current task's deadline at exactly `instant_ticks` - /// - /// This method is a future in order to access the currently executing task's - /// header which contains the deadline. - /// - /// Analogous to `Timer::at`. - /// - /// TODO: Should we check/panic if the deadline is in the past? - #[must_use = "Setting deadline must be polled to be effective"] - pub fn set_current_task_deadline(instant_ticks: u64) -> impl Future { - poll_fn(move |cx| { - let task = super::task_from_waker(cx.waker()); - // SAFETY: A task can only modify its own deadline, while the task is being - // polled, meaning that there cannot be concurrent access to the deadline. - unsafe { - task.header().deadline.set(instant_ticks); - } - Poll::Ready(()) - }) - } - - /// Set the current task's deadline `duration_ticks` in the future from when - /// this future is polled. - /// - /// This method is a future in order to access the currently executing task's - /// header which contains the deadline - /// - /// Analogous to `Timer::after` - /// - /// TODO: Do we want to return what the deadline is? - #[must_use = "Setting deadline must be polled to be effective"] - pub fn set_current_task_deadline_after(duration_ticks: u64) -> impl Future { - poll_fn(move |cx| { - let task = super::task_from_waker(cx.waker()); - let now = embassy_time_driver::now(); - - // Since ticks is a u64, saturating add is PROBABLY overly cautious, leave - // it for now, we can probably make this wrapping_add for performance - // reasons later. - let deadline = now.saturating_add(duration_ticks); - - // SAFETY: A task can only modify its own deadline, while the task is being - // polled, meaning that there cannot be concurrent access to the deadline. - unsafe { - task.header().deadline.set(deadline); - } - Poll::Ready(()) - }) - } - - /// Set the current task's deadline `increment_ticks` from the previous deadline. - /// - /// Note that by default (unless otherwise set), tasks start life with the deadline - /// u64::MAX, which means this method will have no effect. - /// - /// This method is a future in order to access the currently executing task's - /// header which contains the deadline - /// - /// Analogous to one increment of `Ticker::every().next()`. - /// - /// TODO: Do we want to return what the deadline is? - #[must_use = "Setting deadline must be polled to be effective"] - pub fn increment_current_task_deadline(increment_ticks: u64) -> impl Future { - poll_fn(move |cx| { - let task = super::task_from_waker(cx.waker()); - - // SAFETY: A task can only modify its own deadline, while the task is being - // polled, meaning that there cannot be concurrent access to the deadline. - unsafe { - // Get the last value - let last = task.header().deadline.get(); - - // Since ticks is a u64, saturating add is PROBABLY overly cautious, leave - // it for now, we can probably make this wrapping_add for performance - // reasons later. - let deadline = last.saturating_add(increment_ticks); - - // Store the new value - task.header().deadline.set(deadline); - } - Poll::Ready(()) - }) - } - - /// Get the current task's deadline as a tick value. - /// - /// This method is a future in order to access the currently executing task's - /// header which contains the deadline - pub fn get_current_task_deadline() -> impl Future { - poll_fn(move |cx| { - let task = super::task_from_waker(cx.waker()); - - // SAFETY: A task can only modify its own deadline, while the task is being - // polled, meaning that there cannot be concurrent access to the deadline. - let deadline = unsafe { - task.header().deadline.get() - }; - Poll::Ready(Self { instant_ticks: deadline }) - }) - } -} -- cgit From ed2e51bfa4f92b422233343a0c5b1af98fb36537 Mon Sep 17 00:00:00 2001 From: James Munns Date: Tue, 1 Apr 2025 19:32:12 +0200 Subject: Dependency enablement trickery --- embassy-executor/Cargo.toml | 18 ++++++++++++------ embassy-executor/src/raw/deadline.rs | 2 ++ embassy-executor/src/raw/mod.rs | 11 +++++++---- embassy-executor/src/raw/run_queue_atomics.rs | 19 ++++++++++++++++--- 4 files changed, 37 insertions(+), 13 deletions(-) (limited to 'embassy-executor') diff --git a/embassy-executor/Cargo.toml b/embassy-executor/Cargo.toml index 80b5867c9..06e12ae7e 100644 --- a/embassy-executor/Cargo.toml +++ b/embassy-executor/Cargo.toml @@ -46,7 +46,7 @@ flavors = [ [package.metadata.docs.rs] default-target = "thumbv7em-none-eabi" targets = ["thumbv7em-none-eabi"] -features = ["defmt", "arch-cortex-m", "executor-thread", "executor-interrupt"] +features = ["defmt", "arch-cortex-m", "executor-thread", "executor-interrupt", "drs-scheduler"] [dependencies] defmt = { version = "1.0.1", optional = true } @@ -76,13 +76,17 @@ js-sys = { version = "0.3", optional = true } # arch-avr dependencies avr-device = { version = "0.7.0", optional = true } -[dependencies.cordyceps] -# note: targeting v0.3.3, to be released when +# Note: this is ONLY a dependency when the target has atomics, this is +# used for `run_queue_atomics`. We need to be conditional because +# cordyceps *requires* the use of atomics, so we pull it in when +# `run_queue_atomics` would be enabled, and NOT when `run_queue_critical_section` +# would be enabled. +[target.'cfg(target_has_atomic="ptr")'.dependencies.cordyceps] +# TODO: targeting v0.3.3, to be released when # https://github.com/hawkw/mycelium/pull/520 is merged version = "0.3" git = "https://github.com/hawkw/mycelium" rev = "9649db0525b9972b95937d83d52d3f51cc486281" -optional = true [dev-dependencies] critical-section = { version = "1.1", features = ["std"] } @@ -133,5 +137,7 @@ trace = ["_any_trace"] rtos-trace = ["_any_trace", "metadata-name", "dep:rtos-trace", "dep:embassy-time-driver"] _any_trace = [] -## Enable "Deadline Rank Scheduler" -drs-scheduler = ["dep:cordyceps", "dep:embassy-time-driver"] +## Enable "Deadline Rank Sorted" Scheduler, using soft-realtime "deadlines" to prioritize +## tasks based on the remaining time before their deadline. Adds some overhead. Requires +## hardware atomic support +drs-scheduler = ["dep:embassy-time-driver"] diff --git a/embassy-executor/src/raw/deadline.rs b/embassy-executor/src/raw/deadline.rs index 3f60936cc..c8cc94c52 100644 --- a/embassy-executor/src/raw/deadline.rs +++ b/embassy-executor/src/raw/deadline.rs @@ -2,6 +2,8 @@ use core::future::{poll_fn, Future}; use core::task::Poll; /// A type for interacting with the deadline of the current task +/// +/// Requires the `drs-scheduler` feature pub struct Deadline { /// Deadline value in ticks, same time base and ticks as `embassy-time` pub instant_ticks: u64, diff --git a/embassy-executor/src/raw/mod.rs b/embassy-executor/src/raw/mod.rs index 0dd247d30..f4fbe1bfc 100644 --- a/embassy-executor/src/raw/mod.rs +++ b/embassy-executor/src/raw/mod.rs @@ -101,14 +101,14 @@ extern "Rust" fn __embassy_time_queue_item_from_waker(waker: &Waker) -> &'static /// - 5: Task is dequeued. The task's future is not polled, because exiting the task replaces its `poll_fn`. /// - 6: A task is waken when it is not spawned - `wake_task -> State::run_enqueue` pub(crate) struct TaskHeader { + pub(crate) state: State, pub(crate) run_queue_item: RunQueueItem, - #[cfg(feature = "drs-scheduler")] /// Deadline Rank Scheduler Deadline. This field should not be accessed outside the context of /// the task itself as it being polled by the executor. + #[cfg(feature = "drs-scheduler")] pub(crate) deadline: SyncUnsafeCell, - pub(crate) state: State, pub(crate) executor: AtomicPtr, poll_fn: SyncUnsafeCell>, @@ -211,10 +211,12 @@ impl TaskStorage { pub const fn new() -> Self { Self { raw: TaskHeader { + state: State::new(), run_queue_item: RunQueueItem::new(), + // NOTE: The deadline is set to zero to allow the initializer to reside in `.bss`. This + // will be lazily initalized in `initialize_impl` #[cfg(feature = "drs-scheduler")] deadline: SyncUnsafeCell::new(0u64), - state: State::new(), executor: AtomicPtr::new(core::ptr::null_mut()), // Note: this is lazily initialized so that a static `TaskStorage` will go in `.bss` poll_fn: SyncUnsafeCell::new(None), @@ -311,7 +313,8 @@ impl AvailableTask { self.task.raw.poll_fn.set(Some(TaskStorage::::poll)); self.task.future.write_in_place(future); - // TODO(AJM): Some other way of setting this? Just a placeholder + // By default, deadlines are set to the maximum value, so that any task WITH + // a set deadline will ALWAYS be scheduled BEFORE a task WITHOUT a set deadline #[cfg(feature = "drs-scheduler")] self.task.raw.deadline.set(u64::MAX); diff --git a/embassy-executor/src/raw/run_queue_atomics.rs b/embassy-executor/src/raw/run_queue_atomics.rs index bc5d38250..3715fc658 100644 --- a/embassy-executor/src/raw/run_queue_atomics.rs +++ b/embassy-executor/src/raw/run_queue_atomics.rs @@ -66,6 +66,8 @@ impl RunQueue { self.stack.push_was_empty(task) } + /// # Standard atomic runqueue + /// /// Empty the queue, then call `on_task` for each task that was in the queue. /// NOTE: It is OK for `on_task` to enqueue more tasks. In this case they're left in the queue /// and will be processed by the *next* call to `dequeue_all`, *not* the current one. @@ -78,9 +80,20 @@ impl RunQueue { } } - /// Empty the queue, then call `on_task` for each task that was in the queue. - /// NOTE: It is OK for `on_task` to enqueue more tasks. In this case they're left in the queue - /// and will be processed by the *next* call to `dequeue_all`, *not* the current one. + /// # Deadline Ranked Sorted Scheduler + /// + /// This algorithm will loop until all enqueued tasks are processed. + /// + /// Before polling a task, all currently enqueued tasks will be popped from the + /// runqueue, and will be added to the working `sorted` list, a linked-list that + /// sorts tasks by their deadline, with nearest deadline items in the front, and + /// furthest deadline items in the back. + /// + /// After popping and sorting all pending tasks, the SOONEST task will be popped + /// from the front of the queue, and polled by calling `on_task` on it. + /// + /// This process will repeat until the local `sorted` queue AND the global + /// runqueue are both empty, at which point this function will return. #[cfg(feature = "drs-scheduler")] pub(crate) fn dequeue_all(&self, on_task: impl Fn(TaskRef)) { // SAFETY: `deadline` can only be set through the `Deadline` interface, which -- cgit From 2a068c528383b3ddc1213b9a5da5445498962bd2 Mon Sep 17 00:00:00 2001 From: James Munns Date: Tue, 1 Apr 2025 19:41:19 +0200 Subject: Conditional import --- embassy-executor/src/raw/run_queue_atomics.rs | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'embassy-executor') diff --git a/embassy-executor/src/raw/run_queue_atomics.rs b/embassy-executor/src/raw/run_queue_atomics.rs index 3715fc658..a63f0d116 100644 --- a/embassy-executor/src/raw/run_queue_atomics.rs +++ b/embassy-executor/src/raw/run_queue_atomics.rs @@ -1,7 +1,9 @@ use core::ptr::{addr_of_mut, NonNull}; use cordyceps::sorted_list::Links; -use cordyceps::{Linked, SortedList, TransferStack}; +#[cfg(feature = "drs-scheduler")] +use cordyceps::SortedList; +use cordyceps::{Linked, TransferStack}; use super::{TaskHeader, TaskRef}; -- cgit From 08a57b1cb0c3c4a40bd03e6e6ea1c97777300cf4 Mon Sep 17 00:00:00 2001 From: James Munns Date: Wed, 2 Apr 2025 23:30:40 +0200 Subject: Update with changes from the PR --- embassy-executor/Cargo.toml | 5 ++--- embassy-executor/src/raw/run_queue_atomics.rs | 2 +- 2 files changed, 3 insertions(+), 4 deletions(-) (limited to 'embassy-executor') diff --git a/embassy-executor/Cargo.toml b/embassy-executor/Cargo.toml index 06e12ae7e..ab95b2939 100644 --- a/embassy-executor/Cargo.toml +++ b/embassy-executor/Cargo.toml @@ -82,11 +82,10 @@ avr-device = { version = "0.7.0", optional = true } # `run_queue_atomics` would be enabled, and NOT when `run_queue_critical_section` # would be enabled. [target.'cfg(target_has_atomic="ptr")'.dependencies.cordyceps] -# TODO: targeting v0.3.3, to be released when -# https://github.com/hawkw/mycelium/pull/520 is merged +# TODO: targeting v0.3.3, to be released soon version = "0.3" git = "https://github.com/hawkw/mycelium" -rev = "9649db0525b9972b95937d83d52d3f51cc486281" +rev = "1dad987b483078b248ac3e2e7a75f1ff2b463cc4" [dev-dependencies] critical-section = { version = "1.1", features = ["std"] } diff --git a/embassy-executor/src/raw/run_queue_atomics.rs b/embassy-executor/src/raw/run_queue_atomics.rs index a63f0d116..08765e06b 100644 --- a/embassy-executor/src/raw/run_queue_atomics.rs +++ b/embassy-executor/src/raw/run_queue_atomics.rs @@ -102,7 +102,7 @@ impl RunQueue { // only allows access to this value while the given task is being polled. // This acts as mutual exclusion for access. let mut sorted = - SortedList::::new_custom(|lhs, rhs| unsafe { lhs.deadline.get().cmp(&rhs.deadline.get()) }); + SortedList::::new_with_cmp(|lhs, rhs| unsafe { lhs.deadline.get().cmp(&rhs.deadline.get()) }); loop { // For each loop, grab any newly pended items -- cgit From b65a3a301a29c737f336ca344f671d4e9793fda8 Mon Sep 17 00:00:00 2001 From: James Munns Date: Thu, 3 Apr 2025 10:27:26 +0200 Subject: Clean up some TODOs --- embassy-executor/src/raw/deadline.rs | 62 ++++++++++++++++++++++++++++++------ embassy-executor/src/raw/mod.rs | 2 +- 2 files changed, 53 insertions(+), 11 deletions(-) (limited to 'embassy-executor') diff --git a/embassy-executor/src/raw/deadline.rs b/embassy-executor/src/raw/deadline.rs index c8cc94c52..0b88ee2d6 100644 --- a/embassy-executor/src/raw/deadline.rs +++ b/embassy-executor/src/raw/deadline.rs @@ -10,6 +10,16 @@ pub struct Deadline { } impl Deadline { + /// Sentinel value representing an "unset" deadline, which has lower priority + /// than any other set deadline value + pub const UNSET_DEADLINE_TICKS: u64 = u64::MAX; + + /// Does the given Deadline represent an "unset" deadline? + #[inline] + pub fn is_unset(&self) -> bool { + self.instant_ticks == Self::UNSET_DEADLINE_TICKS + } + /// Set the current task's deadline at exactly `instant_ticks` /// /// This method is a future in order to access the currently executing task's @@ -17,7 +27,7 @@ impl Deadline { /// /// Analogous to `Timer::at`. /// - /// TODO: Should we check/panic if the deadline is in the past? + /// This method does NOT check whether the deadline has already passed. #[must_use = "Setting deadline must be polled to be effective"] pub fn set_current_task_deadline(instant_ticks: u64) -> impl Future { poll_fn(move |cx| { @@ -32,16 +42,16 @@ impl Deadline { } /// Set the current task's deadline `duration_ticks` in the future from when - /// this future is polled. + /// this future is polled. This deadline is saturated to the max tick value. /// /// This method is a future in order to access the currently executing task's - /// header which contains the deadline + /// header which contains the deadline. /// - /// Analogous to `Timer::after` + /// Analogous to `Timer::after`. /// - /// TODO: Do we want to return what the deadline is? + /// Returns the deadline that was set. #[must_use = "Setting deadline must be polled to be effective"] - pub fn set_current_task_deadline_after(duration_ticks: u64) -> impl Future { + pub fn set_current_task_deadline_after(duration_ticks: u64) -> impl Future { poll_fn(move |cx| { let task = super::task_from_waker(cx.waker()); let now = embassy_time_driver::now(); @@ -56,12 +66,16 @@ impl Deadline { unsafe { task.header().deadline.set(deadline); } - Poll::Ready(()) + Poll::Ready(Deadline { + instant_ticks: deadline, + }) }) } /// Set the current task's deadline `increment_ticks` from the previous deadline. /// + /// This deadline is saturated to the max tick value. + /// /// Note that by default (unless otherwise set), tasks start life with the deadline /// u64::MAX, which means this method will have no effect. /// @@ -70,9 +84,9 @@ impl Deadline { /// /// Analogous to one increment of `Ticker::every().next()`. /// - /// TODO: Do we want to return what the deadline is? + /// Returns the deadline that was set. #[must_use = "Setting deadline must be polled to be effective"] - pub fn increment_current_task_deadline(increment_ticks: u64) -> impl Future { + pub fn increment_current_task_deadline(increment_ticks: u64) -> impl Future { poll_fn(move |cx| { let task = super::task_from_waker(cx.waker()); @@ -89,8 +103,11 @@ impl Deadline { // Store the new value task.header().deadline.set(deadline); + + Poll::Ready(Deadline { + instant_ticks: deadline, + }) } - Poll::Ready(()) }) } @@ -110,4 +127,29 @@ impl Deadline { }) }) } + + /// Clear the current task's deadline, returning the previous value. + /// + /// This sets the deadline to the default value of `u64::MAX`, meaning all + /// tasks with set deadlines will be scheduled BEFORE this task. + pub fn clear_current_task_deadline() -> impl Future { + poll_fn(move |cx| { + let task = super::task_from_waker(cx.waker()); + + // SAFETY: A task can only modify its own deadline, while the task is being + // polled, meaning that there cannot be concurrent access to the deadline. + let deadline = unsafe { + // get the old value + let d = task.header().deadline.get(); + // Store the default value + task.header().deadline.set(Self::UNSET_DEADLINE_TICKS); + // return the old value + d + }; + + Poll::Ready(Self { + instant_ticks: deadline, + }) + }) + } } diff --git a/embassy-executor/src/raw/mod.rs b/embassy-executor/src/raw/mod.rs index f4fbe1bfc..a0890a864 100644 --- a/embassy-executor/src/raw/mod.rs +++ b/embassy-executor/src/raw/mod.rs @@ -316,7 +316,7 @@ impl AvailableTask { // By default, deadlines are set to the maximum value, so that any task WITH // a set deadline will ALWAYS be scheduled BEFORE a task WITHOUT a set deadline #[cfg(feature = "drs-scheduler")] - self.task.raw.deadline.set(u64::MAX); + self.task.raw.deadline.set(deadline::Deadline::UNSET_DEADLINE_TICKS); let task = TaskRef::new(self.task); -- cgit From b1b2955b604f558d8bd2fcca07b8fd8da3e236fa Mon Sep 17 00:00:00 2001 From: James Munns Date: Tue, 8 Apr 2025 10:05:55 +0200 Subject: Switch to released version of `cordyceps`, add error if used w/o atomics --- embassy-executor/Cargo.toml | 5 +---- embassy-executor/src/raw/deadline.rs | 3 +++ 2 files changed, 4 insertions(+), 4 deletions(-) (limited to 'embassy-executor') diff --git a/embassy-executor/Cargo.toml b/embassy-executor/Cargo.toml index ab95b2939..e740f9ccf 100644 --- a/embassy-executor/Cargo.toml +++ b/embassy-executor/Cargo.toml @@ -82,10 +82,7 @@ avr-device = { version = "0.7.0", optional = true } # `run_queue_atomics` would be enabled, and NOT when `run_queue_critical_section` # would be enabled. [target.'cfg(target_has_atomic="ptr")'.dependencies.cordyceps] -# TODO: targeting v0.3.3, to be released soon -version = "0.3" -git = "https://github.com/hawkw/mycelium" -rev = "1dad987b483078b248ac3e2e7a75f1ff2b463cc4" +version = "0.3.3" [dev-dependencies] critical-section = { version = "1.1", features = ["std"] } diff --git a/embassy-executor/src/raw/deadline.rs b/embassy-executor/src/raw/deadline.rs index 0b88ee2d6..da07d1aac 100644 --- a/embassy-executor/src/raw/deadline.rs +++ b/embassy-executor/src/raw/deadline.rs @@ -1,6 +1,9 @@ use core::future::{poll_fn, Future}; use core::task::Poll; +#[cfg(not(target_has_atomic = "ptr"))] +compile_error!("The `drs-scheduler` feature is currently only supported on targets with atomics."); + /// A type for interacting with the deadline of the current task /// /// Requires the `drs-scheduler` feature -- cgit From 3929142f4c08028ea1982e79fd912e1a44900892 Mon Sep 17 00:00:00 2001 From: James Munns Date: Tue, 8 Apr 2025 10:11:07 +0200 Subject: One more must_use --- embassy-executor/src/raw/deadline.rs | 1 + embassy-executor/src/raw/mod.rs | 3 ++- 2 files changed, 3 insertions(+), 1 deletion(-) (limited to 'embassy-executor') diff --git a/embassy-executor/src/raw/deadline.rs b/embassy-executor/src/raw/deadline.rs index da07d1aac..ae6394822 100644 --- a/embassy-executor/src/raw/deadline.rs +++ b/embassy-executor/src/raw/deadline.rs @@ -135,6 +135,7 @@ impl Deadline { /// /// This sets the deadline to the default value of `u64::MAX`, meaning all /// tasks with set deadlines will be scheduled BEFORE this task. + #[must_use = "Clearing deadline must be polled to be effective"] pub fn clear_current_task_deadline() -> impl Future { poll_fn(move |cx| { let task = super::task_from_waker(cx.waker()); diff --git a/embassy-executor/src/raw/mod.rs b/embassy-executor/src/raw/mod.rs index a0890a864..21dc67b7e 100644 --- a/embassy-executor/src/raw/mod.rs +++ b/embassy-executor/src/raw/mod.rs @@ -36,7 +36,6 @@ use core::marker::PhantomData; use core::mem; use core::pin::Pin; use core::ptr::NonNull; -use core::ptr::addr_of_mut; #[cfg(not(feature = "arch-avr"))] use core::sync::atomic::AtomicPtr; use core::sync::atomic::Ordering; @@ -48,6 +47,8 @@ use portable_atomic::AtomicPtr; #[cfg(feature = "drs-scheduler")] pub use deadline::Deadline; +#[cfg(feature = "arch-avr")] +use portable_atomic::AtomicPtr; use self::run_queue::{RunQueue, RunQueueItem}; use self::state::State; -- cgit From 0e28ba1091257111f71b76a664d7038dbfcf9b5e Mon Sep 17 00:00:00 2001 From: James Munns Date: Wed, 16 Apr 2025 15:59:28 +0200 Subject: "Deadline Rank Sorted Scheduler" -> "Earliest Deadline First Scheduler" --- embassy-executor/Cargo.toml | 7 ++++--- embassy-executor/src/raw/deadline.rs | 4 ++-- embassy-executor/src/raw/mod.rs | 14 +++++++------- embassy-executor/src/raw/run_queue_atomics.rs | 8 ++++---- 4 files changed, 17 insertions(+), 16 deletions(-) (limited to 'embassy-executor') diff --git a/embassy-executor/Cargo.toml b/embassy-executor/Cargo.toml index e740f9ccf..17315eaa3 100644 --- a/embassy-executor/Cargo.toml +++ b/embassy-executor/Cargo.toml @@ -46,7 +46,7 @@ flavors = [ [package.metadata.docs.rs] default-target = "thumbv7em-none-eabi" targets = ["thumbv7em-none-eabi"] -features = ["defmt", "arch-cortex-m", "executor-thread", "executor-interrupt", "drs-scheduler"] +features = ["defmt", "arch-cortex-m", "executor-thread", "executor-interrupt", "edf-scheduler"] [dependencies] defmt = { version = "1.0.1", optional = true } @@ -91,6 +91,7 @@ embassy-sync = { path = "../embassy-sync" } rustversion = "1.0.21" [features] + ## Enable nightly-only features nightly = ["embassy-executor-macros/nightly"] @@ -133,7 +134,7 @@ trace = ["_any_trace"] rtos-trace = ["_any_trace", "metadata-name", "dep:rtos-trace", "dep:embassy-time-driver"] _any_trace = [] -## Enable "Deadline Rank Sorted" Scheduler, using soft-realtime "deadlines" to prioritize +## Enable "Earliest Deadline First" Scheduler, using soft-realtime "deadlines" to prioritize ## tasks based on the remaining time before their deadline. Adds some overhead. Requires ## hardware atomic support -drs-scheduler = ["dep:embassy-time-driver"] +edf-scheduler = ["dep:embassy-time-driver"] diff --git a/embassy-executor/src/raw/deadline.rs b/embassy-executor/src/raw/deadline.rs index ae6394822..006c7caf1 100644 --- a/embassy-executor/src/raw/deadline.rs +++ b/embassy-executor/src/raw/deadline.rs @@ -2,11 +2,11 @@ use core::future::{poll_fn, Future}; use core::task::Poll; #[cfg(not(target_has_atomic = "ptr"))] -compile_error!("The `drs-scheduler` feature is currently only supported on targets with atomics."); +compile_error!("The `edf-scheduler` feature is currently only supported on targets with atomics."); /// A type for interacting with the deadline of the current task /// -/// Requires the `drs-scheduler` feature +/// Requires the `edf-scheduler` feature pub struct Deadline { /// Deadline value in ticks, same time base and ticks as `embassy-time` pub instant_ticks: u64, diff --git a/embassy-executor/src/raw/mod.rs b/embassy-executor/src/raw/mod.rs index 21dc67b7e..96e7fda74 100644 --- a/embassy-executor/src/raw/mod.rs +++ b/embassy-executor/src/raw/mod.rs @@ -28,7 +28,7 @@ pub(crate) mod util; #[cfg_attr(feature = "turbowakers", path = "waker_turbo.rs")] mod waker; -#[cfg(feature = "drs-scheduler")] +#[cfg(feature = "edf-scheduler")] mod deadline; use core::future::Future; @@ -45,7 +45,7 @@ use embassy_executor_timer_queue::TimerQueueItem; #[cfg(feature = "arch-avr")] use portable_atomic::AtomicPtr; -#[cfg(feature = "drs-scheduler")] +#[cfg(feature = "edf-scheduler")] pub use deadline::Deadline; #[cfg(feature = "arch-avr")] use portable_atomic::AtomicPtr; @@ -105,9 +105,9 @@ pub(crate) struct TaskHeader { pub(crate) state: State, pub(crate) run_queue_item: RunQueueItem, - /// Deadline Rank Scheduler Deadline. This field should not be accessed outside the context of - /// the task itself as it being polled by the executor. - #[cfg(feature = "drs-scheduler")] + /// Earliest Deadline First scheduler Deadline. This field should not be accessed + /// outside the context of the task itself as it being polled by the executor. + #[cfg(feature = "edf-scheduler")] pub(crate) deadline: SyncUnsafeCell, pub(crate) executor: AtomicPtr, @@ -216,7 +216,7 @@ impl TaskStorage { run_queue_item: RunQueueItem::new(), // NOTE: The deadline is set to zero to allow the initializer to reside in `.bss`. This // will be lazily initalized in `initialize_impl` - #[cfg(feature = "drs-scheduler")] + #[cfg(feature = "edf-scheduler")] deadline: SyncUnsafeCell::new(0u64), executor: AtomicPtr::new(core::ptr::null_mut()), // Note: this is lazily initialized so that a static `TaskStorage` will go in `.bss` @@ -316,7 +316,7 @@ impl AvailableTask { // By default, deadlines are set to the maximum value, so that any task WITH // a set deadline will ALWAYS be scheduled BEFORE a task WITHOUT a set deadline - #[cfg(feature = "drs-scheduler")] + #[cfg(feature = "edf-scheduler")] self.task.raw.deadline.set(deadline::Deadline::UNSET_DEADLINE_TICKS); let task = TaskRef::new(self.task); diff --git a/embassy-executor/src/raw/run_queue_atomics.rs b/embassy-executor/src/raw/run_queue_atomics.rs index 08765e06b..65a9b7859 100644 --- a/embassy-executor/src/raw/run_queue_atomics.rs +++ b/embassy-executor/src/raw/run_queue_atomics.rs @@ -1,7 +1,7 @@ use core::ptr::{addr_of_mut, NonNull}; use cordyceps::sorted_list::Links; -#[cfg(feature = "drs-scheduler")] +#[cfg(feature = "edf-scheduler")] use cordyceps::SortedList; use cordyceps::{Linked, TransferStack}; @@ -73,7 +73,7 @@ impl RunQueue { /// Empty the queue, then call `on_task` for each task that was in the queue. /// NOTE: It is OK for `on_task` to enqueue more tasks. In this case they're left in the queue /// and will be processed by the *next* call to `dequeue_all`, *not* the current one. - #[cfg(not(feature = "drs-scheduler"))] + #[cfg(not(feature = "edf-scheduler"))] pub(crate) fn dequeue_all(&self, on_task: impl Fn(TaskRef)) { let taken = self.stack.take_all(); for taskref in taken { @@ -82,7 +82,7 @@ impl RunQueue { } } - /// # Deadline Ranked Sorted Scheduler + /// # Earliest Deadline First Scheduler /// /// This algorithm will loop until all enqueued tasks are processed. /// @@ -96,7 +96,7 @@ impl RunQueue { /// /// This process will repeat until the local `sorted` queue AND the global /// runqueue are both empty, at which point this function will return. - #[cfg(feature = "drs-scheduler")] + #[cfg(feature = "edf-scheduler")] pub(crate) fn dequeue_all(&self, on_task: impl Fn(TaskRef)) { // SAFETY: `deadline` can only be set through the `Deadline` interface, which // only allows access to this value while the given task is being polled. -- cgit From 7af8f35a50c631802615044e12cc9c74614f78bb Mon Sep 17 00:00:00 2001 From: James Munns Date: Tue, 3 Jun 2025 16:34:12 +0200 Subject: There can be only one (run queue) --- embassy-executor/Cargo.toml | 20 +-- embassy-executor/src/raw/deadline.rs | 3 - embassy-executor/src/raw/mod.rs | 2 - embassy-executor/src/raw/run_queue.rs | 151 +++++++++++++++++++++ embassy-executor/src/raw/run_queue_atomics.rs | 129 ------------------ .../src/raw/run_queue_critical_section.rs | 74 ---------- 6 files changed, 162 insertions(+), 217 deletions(-) create mode 100644 embassy-executor/src/raw/run_queue.rs delete mode 100644 embassy-executor/src/raw/run_queue_atomics.rs delete mode 100644 embassy-executor/src/raw/run_queue_critical_section.rs (limited to 'embassy-executor') diff --git a/embassy-executor/Cargo.toml b/embassy-executor/Cargo.toml index 17315eaa3..34468e4f9 100644 --- a/embassy-executor/Cargo.toml +++ b/embassy-executor/Cargo.toml @@ -76,13 +76,16 @@ js-sys = { version = "0.3", optional = true } # arch-avr dependencies avr-device = { version = "0.7.0", optional = true } -# Note: this is ONLY a dependency when the target has atomics, this is -# used for `run_queue_atomics`. We need to be conditional because -# cordyceps *requires* the use of atomics, so we pull it in when -# `run_queue_atomics` would be enabled, and NOT when `run_queue_critical_section` -# would be enabled. -[target.'cfg(target_has_atomic="ptr")'.dependencies.cordyceps] -version = "0.3.3" + +[dependencies.cordyceps] +# version = "0.3.3" +# todo: update after https://github.com/hawkw/mycelium/pull/537 is merged +git = "https://github.com/hawkw/mycelium" +rev = "86c428eecfd37ee24dd81f14c4a9f5c8ecefcf17" + +# Note: this is ONLY a dependency when the target does NOT have atomics +[target.'cfg(not(target_has_atomic="ptr"))'.dependencies.mutex] +version = "1.0" [dev-dependencies] critical-section = { version = "1.1", features = ["std"] } @@ -135,6 +138,5 @@ rtos-trace = ["_any_trace", "metadata-name", "dep:rtos-trace", "dep:embassy-time _any_trace = [] ## Enable "Earliest Deadline First" Scheduler, using soft-realtime "deadlines" to prioritize -## tasks based on the remaining time before their deadline. Adds some overhead. Requires -## hardware atomic support +## tasks based on the remaining time before their deadline. Adds some overhead. edf-scheduler = ["dep:embassy-time-driver"] diff --git a/embassy-executor/src/raw/deadline.rs b/embassy-executor/src/raw/deadline.rs index 006c7caf1..0fb22a7ce 100644 --- a/embassy-executor/src/raw/deadline.rs +++ b/embassy-executor/src/raw/deadline.rs @@ -1,9 +1,6 @@ use core::future::{poll_fn, Future}; use core::task::Poll; -#[cfg(not(target_has_atomic = "ptr"))] -compile_error!("The `edf-scheduler` feature is currently only supported on targets with atomics."); - /// A type for interacting with the deadline of the current task /// /// Requires the `edf-scheduler` feature diff --git a/embassy-executor/src/raw/mod.rs b/embassy-executor/src/raw/mod.rs index 96e7fda74..cc43690cb 100644 --- a/embassy-executor/src/raw/mod.rs +++ b/embassy-executor/src/raw/mod.rs @@ -7,8 +7,6 @@ //! Using this module requires respecting subtle safety contracts. If you can, prefer using the safe //! [executor wrappers](crate::Executor) and the [`embassy_executor::task`](embassy_executor_macros::task) macro, which are fully safe. -#[cfg_attr(target_has_atomic = "ptr", path = "run_queue_atomics.rs")] -#[cfg_attr(not(target_has_atomic = "ptr"), path = "run_queue_critical_section.rs")] mod run_queue; #[cfg_attr(all(cortex_m, target_has_atomic = "32"), path = "state_atomics_arm.rs")] diff --git a/embassy-executor/src/raw/run_queue.rs b/embassy-executor/src/raw/run_queue.rs new file mode 100644 index 000000000..f630041e0 --- /dev/null +++ b/embassy-executor/src/raw/run_queue.rs @@ -0,0 +1,151 @@ +use core::ptr::{addr_of_mut, NonNull}; + +use cordyceps::sorted_list::Links; +use cordyceps::Linked; +#[cfg(feature = "edf-scheduler")] +use cordyceps::SortedList; + +#[cfg(target_has_atomic = "ptr")] +type TransferStack = cordyceps::TransferStack; + +#[cfg(not(target_has_atomic = "ptr"))] +type TransferStack = cordyceps::TransferStack; + +use super::{TaskHeader, TaskRef}; + +/// Use `cordyceps::sorted_list::Links` as the singly linked list +/// for RunQueueItems. +pub(crate) type RunQueueItem = Links; + +/// Implements the `Linked` trait, allowing for singly linked list usage +/// of any of cordyceps' `TransferStack` (used for the atomic runqueue), +/// `SortedList` (used with the DRS scheduler), or `Stack`, which is +/// popped atomically from the `TransferStack`. +unsafe impl Linked> for TaskHeader { + type Handle = TaskRef; + + // Convert a TaskRef into a TaskHeader ptr + fn into_ptr(r: TaskRef) -> NonNull { + r.ptr + } + + // Convert a TaskHeader into a TaskRef + unsafe fn from_ptr(ptr: NonNull) -> TaskRef { + TaskRef { ptr } + } + + // Given a pointer to a TaskHeader, obtain a pointer to the Links structure, + // which can be used to traverse to other TaskHeader nodes in the linked list + unsafe fn links(ptr: NonNull) -> NonNull> { + let ptr: *mut TaskHeader = ptr.as_ptr(); + NonNull::new_unchecked(addr_of_mut!((*ptr).run_queue_item)) + } +} + +/// Atomic task queue using a very, very simple lock-free linked-list queue: +/// +/// To enqueue a task, task.next is set to the old head, and head is atomically set to task. +/// +/// Dequeuing is done in batches: the queue is emptied by atomically replacing head with +/// null. Then the batch is iterated following the next pointers until null is reached. +/// +/// Note that batches will be iterated in the reverse order as they were enqueued. This is OK +/// for our purposes: it can't create fairness problems since the next batch won't run until the +/// current batch is completely processed, so even if a task enqueues itself instantly (for example +/// by waking its own waker) can't prevent other tasks from running. +pub(crate) struct RunQueue { + stack: TransferStack, +} + +impl RunQueue { + pub const fn new() -> Self { + Self { + stack: TransferStack::new(), + } + } + + /// Enqueues an item. Returns true if the queue was empty. + /// + /// # Safety + /// + /// `item` must NOT be already enqueued in any queue. + #[inline(always)] + pub(crate) unsafe fn enqueue(&self, task: TaskRef, _: super::state::Token) -> bool { + self.stack.push_was_empty(task) + } + + /// # Standard atomic runqueue + /// + /// Empty the queue, then call `on_task` for each task that was in the queue. + /// NOTE: It is OK for `on_task` to enqueue more tasks. In this case they're left in the queue + /// and will be processed by the *next* call to `dequeue_all`, *not* the current one. + #[cfg(not(feature = "edf-scheduler"))] + pub(crate) fn dequeue_all(&self, on_task: impl Fn(TaskRef)) { + let taken = self.stack.take_all(); + for taskref in taken { + run_dequeue(&taskref); + on_task(taskref); + } + } + + /// # Earliest Deadline First Scheduler + /// + /// This algorithm will loop until all enqueued tasks are processed. + /// + /// Before polling a task, all currently enqueued tasks will be popped from the + /// runqueue, and will be added to the working `sorted` list, a linked-list that + /// sorts tasks by their deadline, with nearest deadline items in the front, and + /// furthest deadline items in the back. + /// + /// After popping and sorting all pending tasks, the SOONEST task will be popped + /// from the front of the queue, and polled by calling `on_task` on it. + /// + /// This process will repeat until the local `sorted` queue AND the global + /// runqueue are both empty, at which point this function will return. + #[cfg(feature = "edf-scheduler")] + pub(crate) fn dequeue_all(&self, on_task: impl Fn(TaskRef)) { + // SAFETY: `deadline` can only be set through the `Deadline` interface, which + // only allows access to this value while the given task is being polled. + // This acts as mutual exclusion for access. + let mut sorted = + SortedList::::new_with_cmp(|lhs, rhs| unsafe { lhs.deadline.get().cmp(&rhs.deadline.get()) }); + + loop { + // For each loop, grab any newly pended items + let taken = self.stack.take_all(); + + // Sort these into the list - this is potentially expensive! We do an + // insertion sort of new items, which iterates the linked list. + // + // Something on the order of `O(n * m)`, where `n` is the number + // of new tasks, and `m` is the number of already pending tasks. + sorted.extend(taken); + + // Pop the task with the SOONEST deadline. If there are no tasks + // pending, then we are done. + let Some(taskref) = sorted.pop_front() else { + return; + }; + + // We got one task, mark it as dequeued, and process the task. + run_dequeue(&taskref); + on_task(taskref); + } + } +} + +/// atomic state does not require a cs... +#[cfg(target_has_atomic = "ptr")] +#[inline(always)] +fn run_dequeue(taskref: &TaskRef) { + taskref.header().state.run_dequeue(); +} + +/// ...while non-atomic state does +#[cfg(not(target_has_atomic = "ptr"))] +#[inline(always)] +fn run_dequeue(taskref: &TaskRef) { + critical_section::with(|cs| { + taskref.header().state.run_dequeue(cs); + }) +} diff --git a/embassy-executor/src/raw/run_queue_atomics.rs b/embassy-executor/src/raw/run_queue_atomics.rs deleted file mode 100644 index 65a9b7859..000000000 --- a/embassy-executor/src/raw/run_queue_atomics.rs +++ /dev/null @@ -1,129 +0,0 @@ -use core::ptr::{addr_of_mut, NonNull}; - -use cordyceps::sorted_list::Links; -#[cfg(feature = "edf-scheduler")] -use cordyceps::SortedList; -use cordyceps::{Linked, TransferStack}; - -use super::{TaskHeader, TaskRef}; - -/// Use `cordyceps::sorted_list::Links` as the singly linked list -/// for RunQueueItems. -pub(crate) type RunQueueItem = Links; - -/// Implements the `Linked` trait, allowing for singly linked list usage -/// of any of cordyceps' `TransferStack` (used for the atomic runqueue), -/// `SortedList` (used with the DRS scheduler), or `Stack`, which is -/// popped atomically from the `TransferStack`. -unsafe impl Linked> for TaskHeader { - type Handle = TaskRef; - - // Convert a TaskRef into a TaskHeader ptr - fn into_ptr(r: TaskRef) -> NonNull { - r.ptr - } - - // Convert a TaskHeader into a TaskRef - unsafe fn from_ptr(ptr: NonNull) -> TaskRef { - TaskRef { ptr } - } - - // Given a pointer to a TaskHeader, obtain a pointer to the Links structure, - // which can be used to traverse to other TaskHeader nodes in the linked list - unsafe fn links(ptr: NonNull) -> NonNull> { - let ptr: *mut TaskHeader = ptr.as_ptr(); - NonNull::new_unchecked(addr_of_mut!((*ptr).run_queue_item)) - } -} - -/// Atomic task queue using a very, very simple lock-free linked-list queue: -/// -/// To enqueue a task, task.next is set to the old head, and head is atomically set to task. -/// -/// Dequeuing is done in batches: the queue is emptied by atomically replacing head with -/// null. Then the batch is iterated following the next pointers until null is reached. -/// -/// Note that batches will be iterated in the reverse order as they were enqueued. This is OK -/// for our purposes: it can't create fairness problems since the next batch won't run until the -/// current batch is completely processed, so even if a task enqueues itself instantly (for example -/// by waking its own waker) can't prevent other tasks from running. -pub(crate) struct RunQueue { - stack: TransferStack, -} - -impl RunQueue { - pub const fn new() -> Self { - Self { - stack: TransferStack::new(), - } - } - - /// Enqueues an item. Returns true if the queue was empty. - /// - /// # Safety - /// - /// `item` must NOT be already enqueued in any queue. - #[inline(always)] - pub(crate) unsafe fn enqueue(&self, task: TaskRef, _: super::state::Token) -> bool { - self.stack.push_was_empty(task) - } - - /// # Standard atomic runqueue - /// - /// Empty the queue, then call `on_task` for each task that was in the queue. - /// NOTE: It is OK for `on_task` to enqueue more tasks. In this case they're left in the queue - /// and will be processed by the *next* call to `dequeue_all`, *not* the current one. - #[cfg(not(feature = "edf-scheduler"))] - pub(crate) fn dequeue_all(&self, on_task: impl Fn(TaskRef)) { - let taken = self.stack.take_all(); - for taskref in taken { - taskref.header().state.run_dequeue(); - on_task(taskref); - } - } - - /// # Earliest Deadline First Scheduler - /// - /// This algorithm will loop until all enqueued tasks are processed. - /// - /// Before polling a task, all currently enqueued tasks will be popped from the - /// runqueue, and will be added to the working `sorted` list, a linked-list that - /// sorts tasks by their deadline, with nearest deadline items in the front, and - /// furthest deadline items in the back. - /// - /// After popping and sorting all pending tasks, the SOONEST task will be popped - /// from the front of the queue, and polled by calling `on_task` on it. - /// - /// This process will repeat until the local `sorted` queue AND the global - /// runqueue are both empty, at which point this function will return. - #[cfg(feature = "edf-scheduler")] - pub(crate) fn dequeue_all(&self, on_task: impl Fn(TaskRef)) { - // SAFETY: `deadline` can only be set through the `Deadline` interface, which - // only allows access to this value while the given task is being polled. - // This acts as mutual exclusion for access. - let mut sorted = - SortedList::::new_with_cmp(|lhs, rhs| unsafe { lhs.deadline.get().cmp(&rhs.deadline.get()) }); - - loop { - // For each loop, grab any newly pended items - let taken = self.stack.take_all(); - - // Sort these into the list - this is potentially expensive! We do an - // insertion sort of new items, which iterates the linked list. - // - // Something on the order of `O(n * m)`, where `n` is the number - // of new tasks, and `m` is the number of already pending tasks. - sorted.extend(taken); - - // Pop the task with the SOONEST deadline. If there are no tasks - // pending, then we are done. - let Some(taskref) = sorted.pop_front() else { - return; - }; - - // We got one task, mark it as dequeued, and process the task. - taskref.header().state.run_dequeue(); - on_task(taskref); - } - } -} diff --git a/embassy-executor/src/raw/run_queue_critical_section.rs b/embassy-executor/src/raw/run_queue_critical_section.rs deleted file mode 100644 index 86c4085ed..000000000 --- a/embassy-executor/src/raw/run_queue_critical_section.rs +++ /dev/null @@ -1,74 +0,0 @@ -use core::cell::Cell; - -use critical_section::{CriticalSection, Mutex}; - -use super::TaskRef; - -pub(crate) struct RunQueueItem { - next: Mutex>>, -} - -impl RunQueueItem { - pub const fn new() -> Self { - Self { - next: Mutex::new(Cell::new(None)), - } - } -} - -/// Atomic task queue using a very, very simple lock-free linked-list queue: -/// -/// To enqueue a task, task.next is set to the old head, and head is atomically set to task. -/// -/// Dequeuing is done in batches: the queue is emptied by atomically replacing head with -/// null. Then the batch is iterated following the next pointers until null is reached. -/// -/// Note that batches will be iterated in the reverse order as they were enqueued. This is OK -/// for our purposes: it can't create fairness problems since the next batch won't run until the -/// current batch is completely processed, so even if a task enqueues itself instantly (for example -/// by waking its own waker) can't prevent other tasks from running. -pub(crate) struct RunQueue { - head: Mutex>>, -} - -impl RunQueue { - pub const fn new() -> Self { - Self { - head: Mutex::new(Cell::new(None)), - } - } - - /// Enqueues an item. Returns true if the queue was empty. - /// - /// # Safety - /// - /// `item` must NOT be already enqueued in any queue. - #[inline(always)] - pub(crate) unsafe fn enqueue(&self, task: TaskRef, cs: CriticalSection<'_>) -> bool { - let prev = self.head.borrow(cs).replace(Some(task)); - task.header().run_queue_item.next.borrow(cs).set(prev); - - prev.is_none() - } - - /// Empty the queue, then call `on_task` for each task that was in the queue. - /// NOTE: It is OK for `on_task` to enqueue more tasks. In this case they're left in the queue - /// and will be processed by the *next* call to `dequeue_all`, *not* the current one. - pub(crate) fn dequeue_all(&self, on_task: impl Fn(TaskRef)) { - // Atomically empty the queue. - let mut next = critical_section::with(|cs| self.head.borrow(cs).take()); - - // Iterate the linked list of tasks that were previously in the queue. - while let Some(task) = next { - // If the task re-enqueues itself, the `next` pointer will get overwritten. - // Therefore, first read the next pointer, and only then process the task. - - critical_section::with(|cs| { - next = task.header().run_queue_item.next.borrow(cs).get(); - task.header().state.run_dequeue(cs); - }); - - on_task(task); - } - } -} -- cgit From d88ea8dd2adefba42489173d5119e888ffa73f07 Mon Sep 17 00:00:00 2001 From: James Munns Date: Wed, 4 Jun 2025 12:22:32 +0200 Subject: Update with cordyceps changes --- embassy-executor/Cargo.toml | 2 +- embassy-executor/src/raw/run_queue.rs | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) (limited to 'embassy-executor') diff --git a/embassy-executor/Cargo.toml b/embassy-executor/Cargo.toml index 34468e4f9..0ea18acbc 100644 --- a/embassy-executor/Cargo.toml +++ b/embassy-executor/Cargo.toml @@ -81,7 +81,7 @@ avr-device = { version = "0.7.0", optional = true } # version = "0.3.3" # todo: update after https://github.com/hawkw/mycelium/pull/537 is merged git = "https://github.com/hawkw/mycelium" -rev = "86c428eecfd37ee24dd81f14c4a9f5c8ecefcf17" +rev = "e21f9756e7d787a023f2ef1bc7f2159cc7dd26e0" # Note: this is ONLY a dependency when the target does NOT have atomics [target.'cfg(not(target_has_atomic="ptr"))'.dependencies.mutex] diff --git a/embassy-executor/src/raw/run_queue.rs b/embassy-executor/src/raw/run_queue.rs index f630041e0..c6c7d7109 100644 --- a/embassy-executor/src/raw/run_queue.rs +++ b/embassy-executor/src/raw/run_queue.rs @@ -9,7 +9,7 @@ use cordyceps::SortedList; type TransferStack = cordyceps::TransferStack; #[cfg(not(target_has_atomic = "ptr"))] -type TransferStack = cordyceps::TransferStack; +type TransferStack = cordyceps::MutexTransferStack; use super::{TaskHeader, TaskRef}; -- cgit From db063945e76a9b62672377ed71e6e833a295a054 Mon Sep 17 00:00:00 2001 From: James Munns Date: Wed, 2 Jul 2025 13:48:32 +0200 Subject: Inline the "MutexTransferStack" impl as it is unclear whether it will be merged upstream --- embassy-executor/Cargo.toml | 6 ++---- embassy-executor/src/raw/run_queue.rs | 31 ++++++++++++++++++++++++++++++- 2 files changed, 32 insertions(+), 5 deletions(-) (limited to 'embassy-executor') diff --git a/embassy-executor/Cargo.toml b/embassy-executor/Cargo.toml index 0ea18acbc..01c028704 100644 --- a/embassy-executor/Cargo.toml +++ b/embassy-executor/Cargo.toml @@ -78,10 +78,8 @@ avr-device = { version = "0.7.0", optional = true } [dependencies.cordyceps] -# version = "0.3.3" -# todo: update after https://github.com/hawkw/mycelium/pull/537 is merged -git = "https://github.com/hawkw/mycelium" -rev = "e21f9756e7d787a023f2ef1bc7f2159cc7dd26e0" +version = "0.3.4" +features = ["no-cache-pad"] # Note: this is ONLY a dependency when the target does NOT have atomics [target.'cfg(not(target_has_atomic="ptr"))'.dependencies.mutex] diff --git a/embassy-executor/src/raw/run_queue.rs b/embassy-executor/src/raw/run_queue.rs index c6c7d7109..5fd703aad 100644 --- a/embassy-executor/src/raw/run_queue.rs +++ b/embassy-executor/src/raw/run_queue.rs @@ -9,7 +9,7 @@ use cordyceps::SortedList; type TransferStack = cordyceps::TransferStack; #[cfg(not(target_has_atomic = "ptr"))] -type TransferStack = cordyceps::MutexTransferStack; +type TransferStack = MutexTransferStack; use super::{TaskHeader, TaskRef}; @@ -149,3 +149,32 @@ fn run_dequeue(taskref: &TaskRef) { taskref.header().state.run_dequeue(cs); }) } + +/// A wrapper type that acts like TransferStack by wrapping a normal Stack in a CS mutex +#[cfg(not(target_has_atomic="ptr"))] +struct MutexTransferStack>> { + inner: mutex::BlockingMutex>, +} + +#[cfg(not(target_has_atomic="ptr"))] +impl>> MutexTransferStack { + const fn new() -> Self { + Self { + inner: mutex::BlockingMutex::new(cordyceps::Stack::new()), + } + } + + fn push_was_empty(&self, item: T::Handle) -> bool { + self.inner.with_lock(|stack| { + let is_empty = stack.is_empty(); + stack.push(item); + is_empty + }) + } + + fn take_all(&self) -> cordyceps::Stack { + self.inner.with_lock(|stack| { + stack.take_all() + }) + } +} -- cgit From cf171ad6d9c0a7487400beb9e4a436e5c1b64e19 Mon Sep 17 00:00:00 2001 From: James Munns Date: Thu, 3 Jul 2025 09:11:32 +0200 Subject: fmt --- embassy-executor/src/raw/run_queue.rs | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-) (limited to 'embassy-executor') diff --git a/embassy-executor/src/raw/run_queue.rs b/embassy-executor/src/raw/run_queue.rs index 5fd703aad..b4b22819f 100644 --- a/embassy-executor/src/raw/run_queue.rs +++ b/embassy-executor/src/raw/run_queue.rs @@ -151,12 +151,12 @@ fn run_dequeue(taskref: &TaskRef) { } /// A wrapper type that acts like TransferStack by wrapping a normal Stack in a CS mutex -#[cfg(not(target_has_atomic="ptr"))] +#[cfg(not(target_has_atomic = "ptr"))] struct MutexTransferStack>> { inner: mutex::BlockingMutex>, } -#[cfg(not(target_has_atomic="ptr"))] +#[cfg(not(target_has_atomic = "ptr"))] impl>> MutexTransferStack { const fn new() -> Self { Self { @@ -173,8 +173,6 @@ impl>> MutexTransferStack { } fn take_all(&self) -> cordyceps::Stack { - self.inner.with_lock(|stack| { - stack.take_all() - }) + self.inner.with_lock(|stack| stack.take_all()) } } -- cgit From 20b56b0fe0570f0d1e8c61d23d067627a4dfc165 Mon Sep 17 00:00:00 2001 From: James Munns Date: Tue, 15 Jul 2025 13:33:51 +0200 Subject: Update to use critical-section::Mutex instead of mutex::BlockingMutex This allows the scheduler to better collaborate with existing critical sections --- embassy-executor/Cargo.toml | 4 ---- embassy-executor/src/raw/run_queue.rs | 28 +++++++++++++++++----------- 2 files changed, 17 insertions(+), 15 deletions(-) (limited to 'embassy-executor') diff --git a/embassy-executor/Cargo.toml b/embassy-executor/Cargo.toml index 01c028704..290e67bce 100644 --- a/embassy-executor/Cargo.toml +++ b/embassy-executor/Cargo.toml @@ -81,10 +81,6 @@ avr-device = { version = "0.7.0", optional = true } version = "0.3.4" features = ["no-cache-pad"] -# Note: this is ONLY a dependency when the target does NOT have atomics -[target.'cfg(not(target_has_atomic="ptr"))'.dependencies.mutex] -version = "1.0" - [dev-dependencies] critical-section = { version = "1.1", features = ["std"] } trybuild = "1.0" diff --git a/embassy-executor/src/raw/run_queue.rs b/embassy-executor/src/raw/run_queue.rs index b4b22819f..9acb9dd28 100644 --- a/embassy-executor/src/raw/run_queue.rs +++ b/embassy-executor/src/raw/run_queue.rs @@ -70,8 +70,12 @@ impl RunQueue { /// /// `item` must NOT be already enqueued in any queue. #[inline(always)] - pub(crate) unsafe fn enqueue(&self, task: TaskRef, _: super::state::Token) -> bool { - self.stack.push_was_empty(task) + pub(crate) unsafe fn enqueue(&self, task: TaskRef, _tok: super::state::Token) -> bool { + self.stack.push_was_empty( + task, + #[cfg(not(target_has_atomic = "ptr"))] + _tok, + ) } /// # Standard atomic runqueue @@ -153,26 +157,28 @@ fn run_dequeue(taskref: &TaskRef) { /// A wrapper type that acts like TransferStack by wrapping a normal Stack in a CS mutex #[cfg(not(target_has_atomic = "ptr"))] struct MutexTransferStack>> { - inner: mutex::BlockingMutex>, + inner: critical_section::Mutex>>, } #[cfg(not(target_has_atomic = "ptr"))] impl>> MutexTransferStack { const fn new() -> Self { Self { - inner: mutex::BlockingMutex::new(cordyceps::Stack::new()), + inner: critical_section::Mutex::new(core::cell::RefCell::new(cordyceps::Stack::new())), } } - fn push_was_empty(&self, item: T::Handle) -> bool { - self.inner.with_lock(|stack| { - let is_empty = stack.is_empty(); - stack.push(item); - is_empty - }) + fn push_was_empty(&self, item: T::Handle, token: super::state::Token) -> bool { + let mut guard = self.inner.borrow_ref_mut(token); + let is_empty = guard.is_empty(); + guard.push(item); + is_empty } fn take_all(&self) -> cordyceps::Stack { - self.inner.with_lock(|stack| stack.take_all()) + critical_section::with(|cs| { + let mut guard = self.inner.borrow_ref_mut(cs); + guard.take_all() + }) } } -- cgit From 38e5e2e9ceb9a34badfdfc57477f0dba23c64ced Mon Sep 17 00:00:00 2001 From: James Munns Date: Tue, 15 Jul 2025 14:51:08 +0200 Subject: Replace use of RefCell with UnsafeCell --- embassy-executor/src/raw/run_queue.rs | 21 +++++++++++++++++---- 1 file changed, 17 insertions(+), 4 deletions(-) (limited to 'embassy-executor') diff --git a/embassy-executor/src/raw/run_queue.rs b/embassy-executor/src/raw/run_queue.rs index 9acb9dd28..97d26a18a 100644 --- a/embassy-executor/src/raw/run_queue.rs +++ b/embassy-executor/src/raw/run_queue.rs @@ -157,19 +157,26 @@ fn run_dequeue(taskref: &TaskRef) { /// A wrapper type that acts like TransferStack by wrapping a normal Stack in a CS mutex #[cfg(not(target_has_atomic = "ptr"))] struct MutexTransferStack>> { - inner: critical_section::Mutex>>, + inner: critical_section::Mutex>>, } #[cfg(not(target_has_atomic = "ptr"))] impl>> MutexTransferStack { const fn new() -> Self { Self { - inner: critical_section::Mutex::new(core::cell::RefCell::new(cordyceps::Stack::new())), + inner: critical_section::Mutex::new(core::cell::UnsafeCell::new(cordyceps::Stack::new())), } } + /// Push an item to the transfer stack, returning whether the stack was previously empty fn push_was_empty(&self, item: T::Handle, token: super::state::Token) -> bool { - let mut guard = self.inner.borrow_ref_mut(token); + /// SAFETY: The critical-section mutex guarantees that there is no *concurrent* access + /// for the lifetime of the token, but does NOT protect against re-entrant access. + /// However, we never *return* the reference, nor do we recurse (or call another method + /// like `take_all`) that could ever allow for re-entrant aliasing. Therefore, the + /// presence of the critical section is sufficient to guarantee exclusive access to + /// the `inner` field for the purposes of this function + let mut guard = unsafe { &mut *self.inner.borrow(token).get() }; let is_empty = guard.is_empty(); guard.push(item); is_empty @@ -177,7 +184,13 @@ impl>> MutexTransferStack { fn take_all(&self) -> cordyceps::Stack { critical_section::with(|cs| { - let mut guard = self.inner.borrow_ref_mut(cs); + /// SAFETY: The critical-section mutex guarantees that there is no *concurrent* access + /// for the lifetime of the token, but does NOT protect against re-entrant access. + /// However, we never *return* the reference, nor do we recurse (or call another method + /// like `push_was_empty`) that could ever allow for re-entrant aliasing. Therefore, the + /// presence of the critical section is sufficient to guarantee exclusive access to + /// the `inner` field for the purposes of this function + let mut guard = unsafe { &mut *self.inner.borrow(cs).get() }; guard.take_all() }) } -- cgit From 4479f5bbfce9002b965f9e3e189cdd5c61096eff Mon Sep 17 00:00:00 2001 From: James Munns Date: Tue, 15 Jul 2025 14:54:20 +0200 Subject: Regular comments not doc comments --- embassy-executor/src/raw/run_queue.rs | 24 ++++++++++++------------ 1 file changed, 12 insertions(+), 12 deletions(-) (limited to 'embassy-executor') diff --git a/embassy-executor/src/raw/run_queue.rs b/embassy-executor/src/raw/run_queue.rs index 97d26a18a..1eb5775d8 100644 --- a/embassy-executor/src/raw/run_queue.rs +++ b/embassy-executor/src/raw/run_queue.rs @@ -170,12 +170,12 @@ impl>> MutexTransferStack { /// Push an item to the transfer stack, returning whether the stack was previously empty fn push_was_empty(&self, item: T::Handle, token: super::state::Token) -> bool { - /// SAFETY: The critical-section mutex guarantees that there is no *concurrent* access - /// for the lifetime of the token, but does NOT protect against re-entrant access. - /// However, we never *return* the reference, nor do we recurse (or call another method - /// like `take_all`) that could ever allow for re-entrant aliasing. Therefore, the - /// presence of the critical section is sufficient to guarantee exclusive access to - /// the `inner` field for the purposes of this function + // SAFETY: The critical-section mutex guarantees that there is no *concurrent* access + // for the lifetime of the token, but does NOT protect against re-entrant access. + // However, we never *return* the reference, nor do we recurse (or call another method + // like `take_all`) that could ever allow for re-entrant aliasing. Therefore, the + // presence of the critical section is sufficient to guarantee exclusive access to + // the `inner` field for the purposes of this function. let mut guard = unsafe { &mut *self.inner.borrow(token).get() }; let is_empty = guard.is_empty(); guard.push(item); @@ -184,12 +184,12 @@ impl>> MutexTransferStack { fn take_all(&self) -> cordyceps::Stack { critical_section::with(|cs| { - /// SAFETY: The critical-section mutex guarantees that there is no *concurrent* access - /// for the lifetime of the token, but does NOT protect against re-entrant access. - /// However, we never *return* the reference, nor do we recurse (or call another method - /// like `push_was_empty`) that could ever allow for re-entrant aliasing. Therefore, the - /// presence of the critical section is sufficient to guarantee exclusive access to - /// the `inner` field for the purposes of this function + // SAFETY: The critical-section mutex guarantees that there is no *concurrent* access + // for the lifetime of the token, but does NOT protect against re-entrant access. + // However, we never *return* the reference, nor do we recurse (or call another method + // like `push_was_empty`) that could ever allow for re-entrant aliasing. Therefore, the + // presence of the critical section is sufficient to guarantee exclusive access to + // the `inner` field for the purposes of this function. let mut guard = unsafe { &mut *self.inner.borrow(cs).get() }; guard.take_all() }) -- cgit From b5c9e721009fd4331cdc1ce58a07698eb54f2959 Mon Sep 17 00:00:00 2001 From: James Munns Date: Tue, 15 Jul 2025 14:58:41 +0200 Subject: Rename, remove excess mut --- embassy-executor/src/raw/run_queue.rs | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) (limited to 'embassy-executor') diff --git a/embassy-executor/src/raw/run_queue.rs b/embassy-executor/src/raw/run_queue.rs index 1eb5775d8..97060f4b9 100644 --- a/embassy-executor/src/raw/run_queue.rs +++ b/embassy-executor/src/raw/run_queue.rs @@ -176,9 +176,9 @@ impl>> MutexTransferStack { // like `take_all`) that could ever allow for re-entrant aliasing. Therefore, the // presence of the critical section is sufficient to guarantee exclusive access to // the `inner` field for the purposes of this function. - let mut guard = unsafe { &mut *self.inner.borrow(token).get() }; - let is_empty = guard.is_empty(); - guard.push(item); + let inner = unsafe { &mut *self.inner.borrow(token).get() }; + let is_empty = inner.is_empty(); + inner.push(item); is_empty } @@ -190,8 +190,8 @@ impl>> MutexTransferStack { // like `push_was_empty`) that could ever allow for re-entrant aliasing. Therefore, the // presence of the critical section is sufficient to guarantee exclusive access to // the `inner` field for the purposes of this function. - let mut guard = unsafe { &mut *self.inner.borrow(cs).get() }; - guard.take_all() + let inner = unsafe { &mut *self.inner.borrow(cs).get() }; + inner.take_all() }) } } -- cgit From 3f606b28f3b32e9e3b9a9f136eeef52828a78512 Mon Sep 17 00:00:00 2001 From: Dion Dokter Date: Tue, 15 Jul 2025 13:40:30 +0200 Subject: Change deadline to use internal atomics --- embassy-executor/src/raw/deadline.rs | 101 +++++++++++++++++----------------- embassy-executor/src/raw/mod.rs | 4 +- embassy-executor/src/raw/run_queue.rs | 8 +-- 3 files changed, 55 insertions(+), 58 deletions(-) (limited to 'embassy-executor') diff --git a/embassy-executor/src/raw/deadline.rs b/embassy-executor/src/raw/deadline.rs index 0fb22a7ce..a61852612 100644 --- a/embassy-executor/src/raw/deadline.rs +++ b/embassy-executor/src/raw/deadline.rs @@ -1,15 +1,41 @@ use core::future::{poll_fn, Future}; +use core::sync::atomic::{AtomicU32, Ordering}; use core::task::Poll; /// A type for interacting with the deadline of the current task /// /// Requires the `edf-scheduler` feature pub struct Deadline { - /// Deadline value in ticks, same time base and ticks as `embassy-time` - pub instant_ticks: u64, + instant_ticks_hi: AtomicU32, + instant_ticks_lo: AtomicU32, } impl Deadline { + pub(crate) const fn new(instant_ticks: u64) -> Self { + Self { + instant_ticks_hi: AtomicU32::new((instant_ticks >> 32) as u32), + instant_ticks_lo: AtomicU32::new(instant_ticks as u32), + } + } + + pub(crate) const fn new_unset() -> Self { + Self::new(Self::UNSET_DEADLINE_TICKS) + } + + pub(crate) fn set(&self, instant_ticks: u64) { + self.instant_ticks_hi + .store((instant_ticks >> 32) as u32, Ordering::Relaxed); + self.instant_ticks_lo.store(instant_ticks as u32, Ordering::Relaxed); + } + + /// Deadline value in ticks, same time base and ticks as `embassy-time` + pub fn instant_ticks(&self) -> u64 { + let hi = self.instant_ticks_hi.load(Ordering::Relaxed) as u64; + let lo = self.instant_ticks_lo.load(Ordering::Relaxed) as u64; + + (hi << 32) | lo + } + /// Sentinel value representing an "unset" deadline, which has lower priority /// than any other set deadline value pub const UNSET_DEADLINE_TICKS: u64 = u64::MAX; @@ -17,7 +43,7 @@ impl Deadline { /// Does the given Deadline represent an "unset" deadline? #[inline] pub fn is_unset(&self) -> bool { - self.instant_ticks == Self::UNSET_DEADLINE_TICKS + self.instant_ticks() == Self::UNSET_DEADLINE_TICKS } /// Set the current task's deadline at exactly `instant_ticks` @@ -32,11 +58,7 @@ impl Deadline { pub fn set_current_task_deadline(instant_ticks: u64) -> impl Future { poll_fn(move |cx| { let task = super::task_from_waker(cx.waker()); - // SAFETY: A task can only modify its own deadline, while the task is being - // polled, meaning that there cannot be concurrent access to the deadline. - unsafe { - task.header().deadline.set(instant_ticks); - } + task.header().deadline.set(instant_ticks); Poll::Ready(()) }) } @@ -61,14 +83,9 @@ impl Deadline { // reasons later. let deadline = now.saturating_add(duration_ticks); - // SAFETY: A task can only modify its own deadline, while the task is being - // polled, meaning that there cannot be concurrent access to the deadline. - unsafe { - task.header().deadline.set(deadline); - } - Poll::Ready(Deadline { - instant_ticks: deadline, - }) + task.header().deadline.set(deadline); + + Poll::Ready(Deadline::new(deadline)) }) } @@ -90,24 +107,18 @@ impl Deadline { poll_fn(move |cx| { let task = super::task_from_waker(cx.waker()); - // SAFETY: A task can only modify its own deadline, while the task is being - // polled, meaning that there cannot be concurrent access to the deadline. - unsafe { - // Get the last value - let last = task.header().deadline.get(); + // Get the last value + let last = task.header().deadline.instant_ticks(); - // Since ticks is a u64, saturating add is PROBABLY overly cautious, leave - // it for now, we can probably make this wrapping_add for performance - // reasons later. - let deadline = last.saturating_add(increment_ticks); + // Since ticks is a u64, saturating add is PROBABLY overly cautious, leave + // it for now, we can probably make this wrapping_add for performance + // reasons later. + let deadline = last.saturating_add(increment_ticks); - // Store the new value - task.header().deadline.set(deadline); + // Store the new value + task.header().deadline.set(deadline); - Poll::Ready(Deadline { - instant_ticks: deadline, - }) - } + Poll::Ready(Deadline::new(deadline)) }) } @@ -119,12 +130,8 @@ impl Deadline { poll_fn(move |cx| { let task = super::task_from_waker(cx.waker()); - // SAFETY: A task can only modify its own deadline, while the task is being - // polled, meaning that there cannot be concurrent access to the deadline. - let deadline = unsafe { task.header().deadline.get() }; - Poll::Ready(Self { - instant_ticks: deadline, - }) + let deadline = task.header().deadline.instant_ticks(); + Poll::Ready(Self::new(deadline)) }) } @@ -137,20 +144,12 @@ impl Deadline { poll_fn(move |cx| { let task = super::task_from_waker(cx.waker()); - // SAFETY: A task can only modify its own deadline, while the task is being - // polled, meaning that there cannot be concurrent access to the deadline. - let deadline = unsafe { - // get the old value - let d = task.header().deadline.get(); - // Store the default value - task.header().deadline.set(Self::UNSET_DEADLINE_TICKS); - // return the old value - d - }; - - Poll::Ready(Self { - instant_ticks: deadline, - }) + // get the old value + let deadline = task.header().deadline.instant_ticks(); + // Store the default value + task.header().deadline.set(Self::UNSET_DEADLINE_TICKS); + + Poll::Ready(Self::new(deadline)) }) } } diff --git a/embassy-executor/src/raw/mod.rs b/embassy-executor/src/raw/mod.rs index cc43690cb..be2c5ee28 100644 --- a/embassy-executor/src/raw/mod.rs +++ b/embassy-executor/src/raw/mod.rs @@ -106,7 +106,7 @@ pub(crate) struct TaskHeader { /// Earliest Deadline First scheduler Deadline. This field should not be accessed /// outside the context of the task itself as it being polled by the executor. #[cfg(feature = "edf-scheduler")] - pub(crate) deadline: SyncUnsafeCell, + pub(crate) deadline: Deadline, pub(crate) executor: AtomicPtr, poll_fn: SyncUnsafeCell>, @@ -215,7 +215,7 @@ impl TaskStorage { // NOTE: The deadline is set to zero to allow the initializer to reside in `.bss`. This // will be lazily initalized in `initialize_impl` #[cfg(feature = "edf-scheduler")] - deadline: SyncUnsafeCell::new(0u64), + deadline: Deadline::new_unset(), executor: AtomicPtr::new(core::ptr::null_mut()), // Note: this is lazily initialized so that a static `TaskStorage` will go in `.bss` poll_fn: SyncUnsafeCell::new(None), diff --git a/embassy-executor/src/raw/run_queue.rs b/embassy-executor/src/raw/run_queue.rs index 97060f4b9..e8a046a48 100644 --- a/embassy-executor/src/raw/run_queue.rs +++ b/embassy-executor/src/raw/run_queue.rs @@ -108,11 +108,9 @@ impl RunQueue { /// runqueue are both empty, at which point this function will return. #[cfg(feature = "edf-scheduler")] pub(crate) fn dequeue_all(&self, on_task: impl Fn(TaskRef)) { - // SAFETY: `deadline` can only be set through the `Deadline` interface, which - // only allows access to this value while the given task is being polled. - // This acts as mutual exclusion for access. - let mut sorted = - SortedList::::new_with_cmp(|lhs, rhs| unsafe { lhs.deadline.get().cmp(&rhs.deadline.get()) }); + let mut sorted = SortedList::::new_with_cmp(|lhs, rhs| { + lhs.deadline.instant_ticks().cmp(&rhs.deadline.instant_ticks()) + }); loop { // For each loop, grab any newly pended items -- cgit From d6d4df1c768f8ae43ad1339b74d351f4cbad0386 Mon Sep 17 00:00:00 2001 From: Dion Dokter Date: Tue, 15 Jul 2025 14:30:02 +0200 Subject: Add some docs --- embassy-executor/src/raw/deadline.rs | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) (limited to 'embassy-executor') diff --git a/embassy-executor/src/raw/deadline.rs b/embassy-executor/src/raw/deadline.rs index a61852612..cbb379b82 100644 --- a/embassy-executor/src/raw/deadline.rs +++ b/embassy-executor/src/raw/deadline.rs @@ -4,7 +4,11 @@ use core::task::Poll; /// A type for interacting with the deadline of the current task /// -/// Requires the `edf-scheduler` feature +/// Requires the `edf-scheduler` feature. +/// +/// Note: Interacting with the deadline should be done locally in a task. +/// In theory you could try to set or read the deadline from another task, +/// but that will result in weird (though not unsound) behavior. pub struct Deadline { instant_ticks_hi: AtomicU32, instant_ticks_lo: AtomicU32, -- cgit From 52d178560501a464dba67da89a1570ae9a2cf66c Mon Sep 17 00:00:00 2001 From: diondokter Date: Fri, 29 Aug 2025 14:36:17 +0200 Subject: Introduce metadata-deadline and let the EDF scheduler use it --- embassy-executor/Cargo.toml | 4 +++- embassy-executor/src/metadata.rs | 13 +++++++++++++ embassy-executor/src/raw/deadline.rs | 18 +++++++++--------- embassy-executor/src/raw/mod.rs | 19 +++++++------------ embassy-executor/src/raw/run_queue.rs | 5 ++++- 5 files changed, 36 insertions(+), 23 deletions(-) (limited to 'embassy-executor') diff --git a/embassy-executor/Cargo.toml b/embassy-executor/Cargo.toml index 290e67bce..2de36d22d 100644 --- a/embassy-executor/Cargo.toml +++ b/embassy-executor/Cargo.toml @@ -118,6 +118,8 @@ arch-spin = ["_arch"] ## Enable the `name` field in task metadata. metadata-name = ["embassy-executor-macros/metadata-name"] +## Enable the `deadline` field in task metadata. +metadata-deadline = [] #! ### Executor @@ -133,4 +135,4 @@ _any_trace = [] ## Enable "Earliest Deadline First" Scheduler, using soft-realtime "deadlines" to prioritize ## tasks based on the remaining time before their deadline. Adds some overhead. -edf-scheduler = ["dep:embassy-time-driver"] +edf-scheduler = ["dep:embassy-time-driver", "metadata-deadline"] diff --git a/embassy-executor/src/metadata.rs b/embassy-executor/src/metadata.rs index f92c9b37c..fd8095629 100644 --- a/embassy-executor/src/metadata.rs +++ b/embassy-executor/src/metadata.rs @@ -12,6 +12,8 @@ use crate::raw; pub struct Metadata { #[cfg(feature = "metadata-name")] name: Mutex>>, + #[cfg(feature = "metadata-deadline")] + deadline: raw::Deadline, } impl Metadata { @@ -19,6 +21,10 @@ impl Metadata { Self { #[cfg(feature = "metadata-name")] name: Mutex::new(Cell::new(None)), + // NOTE: The deadline is set to zero to allow the initializer to reside in `.bss`. This + // will be lazily initalized in `initialize_impl` + #[cfg(feature = "metadata-deadline")] + deadline: raw::Deadline::new_unset(), } } @@ -52,4 +58,11 @@ impl Metadata { pub fn set_name(&self, name: &'static str) { critical_section::with(|cs| self.name.borrow(cs).set(Some(name))) } + + /// Earliest Deadline First scheduler Deadline. This field should not be accessed + /// outside the context of the task itself as it being polled by the executor. + #[cfg(feature = "metadata-deadline")] + pub fn deadline(&self) -> &raw::Deadline { + &self.deadline + } } diff --git a/embassy-executor/src/raw/deadline.rs b/embassy-executor/src/raw/deadline.rs index cbb379b82..5b585195d 100644 --- a/embassy-executor/src/raw/deadline.rs +++ b/embassy-executor/src/raw/deadline.rs @@ -62,7 +62,7 @@ impl Deadline { pub fn set_current_task_deadline(instant_ticks: u64) -> impl Future { poll_fn(move |cx| { let task = super::task_from_waker(cx.waker()); - task.header().deadline.set(instant_ticks); + task.header().metadata.deadline().set(instant_ticks); Poll::Ready(()) }) } @@ -87,7 +87,7 @@ impl Deadline { // reasons later. let deadline = now.saturating_add(duration_ticks); - task.header().deadline.set(deadline); + task.header().metadata.deadline().set(deadline); Poll::Ready(Deadline::new(deadline)) }) @@ -109,10 +109,10 @@ impl Deadline { #[must_use = "Setting deadline must be polled to be effective"] pub fn increment_current_task_deadline(increment_ticks: u64) -> impl Future { poll_fn(move |cx| { - let task = super::task_from_waker(cx.waker()); + let task_header = super::task_from_waker(cx.waker()).header(); // Get the last value - let last = task.header().deadline.instant_ticks(); + let last = task_header.metadata.deadline().instant_ticks(); // Since ticks is a u64, saturating add is PROBABLY overly cautious, leave // it for now, we can probably make this wrapping_add for performance @@ -120,7 +120,7 @@ impl Deadline { let deadline = last.saturating_add(increment_ticks); // Store the new value - task.header().deadline.set(deadline); + task_header.metadata.deadline().set(deadline); Poll::Ready(Deadline::new(deadline)) }) @@ -134,7 +134,7 @@ impl Deadline { poll_fn(move |cx| { let task = super::task_from_waker(cx.waker()); - let deadline = task.header().deadline.instant_ticks(); + let deadline = task.header().metadata.deadline().instant_ticks(); Poll::Ready(Self::new(deadline)) }) } @@ -146,12 +146,12 @@ impl Deadline { #[must_use = "Clearing deadline must be polled to be effective"] pub fn clear_current_task_deadline() -> impl Future { poll_fn(move |cx| { - let task = super::task_from_waker(cx.waker()); + let task_header = super::task_from_waker(cx.waker()).header(); // get the old value - let deadline = task.header().deadline.instant_ticks(); + let deadline = task_header.metadata.deadline().instant_ticks(); // Store the default value - task.header().deadline.set(Self::UNSET_DEADLINE_TICKS); + task_header.metadata.deadline().set(Self::UNSET_DEADLINE_TICKS); Poll::Ready(Self::new(deadline)) }) diff --git a/embassy-executor/src/raw/mod.rs b/embassy-executor/src/raw/mod.rs index be2c5ee28..f93bfdef9 100644 --- a/embassy-executor/src/raw/mod.rs +++ b/embassy-executor/src/raw/mod.rs @@ -26,7 +26,7 @@ pub(crate) mod util; #[cfg_attr(feature = "turbowakers", path = "waker_turbo.rs")] mod waker; -#[cfg(feature = "edf-scheduler")] +#[cfg(feature = "metadata-deadline")] mod deadline; use core::future::Future; @@ -43,7 +43,7 @@ use embassy_executor_timer_queue::TimerQueueItem; #[cfg(feature = "arch-avr")] use portable_atomic::AtomicPtr; -#[cfg(feature = "edf-scheduler")] +#[cfg(feature = "metadata-deadline")] pub use deadline::Deadline; #[cfg(feature = "arch-avr")] use portable_atomic::AtomicPtr; @@ -103,11 +103,6 @@ pub(crate) struct TaskHeader { pub(crate) state: State, pub(crate) run_queue_item: RunQueueItem, - /// Earliest Deadline First scheduler Deadline. This field should not be accessed - /// outside the context of the task itself as it being polled by the executor. - #[cfg(feature = "edf-scheduler")] - pub(crate) deadline: Deadline, - pub(crate) executor: AtomicPtr, poll_fn: SyncUnsafeCell>, @@ -212,10 +207,6 @@ impl TaskStorage { raw: TaskHeader { state: State::new(), run_queue_item: RunQueueItem::new(), - // NOTE: The deadline is set to zero to allow the initializer to reside in `.bss`. This - // will be lazily initalized in `initialize_impl` - #[cfg(feature = "edf-scheduler")] - deadline: Deadline::new_unset(), executor: AtomicPtr::new(core::ptr::null_mut()), // Note: this is lazily initialized so that a static `TaskStorage` will go in `.bss` poll_fn: SyncUnsafeCell::new(None), @@ -315,7 +306,11 @@ impl AvailableTask { // By default, deadlines are set to the maximum value, so that any task WITH // a set deadline will ALWAYS be scheduled BEFORE a task WITHOUT a set deadline #[cfg(feature = "edf-scheduler")] - self.task.raw.deadline.set(deadline::Deadline::UNSET_DEADLINE_TICKS); + self.task + .raw + .metadata + .deadline() + .set(deadline::Deadline::UNSET_DEADLINE_TICKS); let task = TaskRef::new(self.task); diff --git a/embassy-executor/src/raw/run_queue.rs b/embassy-executor/src/raw/run_queue.rs index e8a046a48..978ca082a 100644 --- a/embassy-executor/src/raw/run_queue.rs +++ b/embassy-executor/src/raw/run_queue.rs @@ -109,7 +109,10 @@ impl RunQueue { #[cfg(feature = "edf-scheduler")] pub(crate) fn dequeue_all(&self, on_task: impl Fn(TaskRef)) { let mut sorted = SortedList::::new_with_cmp(|lhs, rhs| { - lhs.deadline.instant_ticks().cmp(&rhs.deadline.instant_ticks()) + lhs.metadata + .deadline() + .instant_ticks() + .cmp(&rhs.metadata.deadline().instant_ticks()) }); loop { -- cgit From a853bbe2a4dbb64c2e691ddcb258b2530d2b5af5 Mon Sep 17 00:00:00 2001 From: Dion Dokter Date: Fri, 29 Aug 2025 15:16:31 +0200 Subject: Happy CI :) --- embassy-executor/CHANGELOG.md | 1 + embassy-executor/src/raw/mod.rs | 5 +---- 2 files changed, 2 insertions(+), 4 deletions(-) (limited to 'embassy-executor') diff --git a/embassy-executor/CHANGELOG.md b/embassy-executor/CHANGELOG.md index dd462608b..03d60208e 100644 --- a/embassy-executor/CHANGELOG.md +++ b/embassy-executor/CHANGELOG.md @@ -11,6 +11,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - Added new metadata API for tasks. - Main task automatically gets a name of `main` when the `metadata-name` feature is enabled. - Upgraded rtos-trace +- Added optional "earliest deadline first" EDF scheduling ## 0.9.1 - 2025-08-31 diff --git a/embassy-executor/src/raw/mod.rs b/embassy-executor/src/raw/mod.rs index f93bfdef9..86ee86842 100644 --- a/embassy-executor/src/raw/mod.rs +++ b/embassy-executor/src/raw/mod.rs @@ -39,12 +39,9 @@ use core::sync::atomic::AtomicPtr; use core::sync::atomic::Ordering; use core::task::{Context, Poll, Waker}; -use embassy_executor_timer_queue::TimerQueueItem; -#[cfg(feature = "arch-avr")] -use portable_atomic::AtomicPtr; - #[cfg(feature = "metadata-deadline")] pub use deadline::Deadline; +use embassy_executor_timer_queue::TimerQueueItem; #[cfg(feature = "arch-avr")] use portable_atomic::AtomicPtr; -- cgit From adb0c3e947dc72027a121a74a700df10fc9e2337 Mon Sep 17 00:00:00 2001 From: Dion Dokter Date: Mon, 1 Sep 2025 11:17:14 +0200 Subject: Add more metadata --- embassy-executor/Cargo.toml | 1 + 1 file changed, 1 insertion(+) (limited to 'embassy-executor') diff --git a/embassy-executor/Cargo.toml b/embassy-executor/Cargo.toml index 2de36d22d..e7136466d 100644 --- a/embassy-executor/Cargo.toml +++ b/embassy-executor/Cargo.toml @@ -24,6 +24,7 @@ build = [ {target = "thumbv7em-none-eabi", features = ["arch-cortex-m", "executor-thread"]}, {target = "thumbv7em-none-eabi", features = ["arch-cortex-m", "executor-interrupt"]}, {target = "thumbv7em-none-eabi", features = ["arch-cortex-m", "executor-interrupt", "executor-thread"]}, + {target = "thumbv7em-none-eabi", features = ["arch-cortex-m", "executor-interrupt", "executor-thread", "edf-scheduler"]}, {target = "armv7a-none-eabi", features = ["arch-cortex-ar", "executor-thread"]}, {target = "armv7r-none-eabi", features = ["arch-cortex-ar", "executor-thread"]}, {target = "armv7r-none-eabihf", features = ["arch-cortex-ar", "executor-thread"]}, -- cgit From 401fac6ea95b6dd16492d784f99f07fb9a1b318b Mon Sep 17 00:00:00 2001 From: Dion Dokter Date: Mon, 8 Sep 2025 11:40:34 +0200 Subject: Make requested API changes --- embassy-executor/Cargo.toml | 10 ++-- embassy-executor/src/metadata.rs | 64 ++++++++++++++++++-- embassy-executor/src/raw/deadline.rs | 109 ---------------------------------- embassy-executor/src/raw/mod.rs | 6 +- embassy-executor/src/raw/run_queue.rs | 6 +- 5 files changed, 71 insertions(+), 124 deletions(-) (limited to 'embassy-executor') diff --git a/embassy-executor/Cargo.toml b/embassy-executor/Cargo.toml index e7136466d..66352a00e 100644 --- a/embassy-executor/Cargo.toml +++ b/embassy-executor/Cargo.toml @@ -119,8 +119,6 @@ arch-spin = ["_arch"] ## Enable the `name` field in task metadata. metadata-name = ["embassy-executor-macros/metadata-name"] -## Enable the `deadline` field in task metadata. -metadata-deadline = [] #! ### Executor @@ -131,9 +129,13 @@ executor-interrupt = [] ## Enable tracing hooks trace = ["_any_trace"] ## Enable support for rtos-trace framework -rtos-trace = ["_any_trace", "metadata-name", "dep:rtos-trace", "dep:embassy-time-driver"] +rtos-trace = ["_any_trace", "metadata-name", "dep:rtos-trace", "embassy-time-driver"] _any_trace = [] ## Enable "Earliest Deadline First" Scheduler, using soft-realtime "deadlines" to prioritize ## tasks based on the remaining time before their deadline. Adds some overhead. -edf-scheduler = ["dep:embassy-time-driver", "metadata-deadline"] +scheduler-deadline = [] + +## Enable the embassy_time_driver dependency. +## This can unlock extra APIs, for example for the `sheduler-deadline` +embassy-time-driver = ["dep:embassy-time-driver"] diff --git a/embassy-executor/src/metadata.rs b/embassy-executor/src/metadata.rs index fd8095629..81c5afafb 100644 --- a/embassy-executor/src/metadata.rs +++ b/embassy-executor/src/metadata.rs @@ -7,12 +7,14 @@ use core::task::Poll; use critical_section::Mutex; use crate::raw; +#[cfg(feature = "scheduler-deadline")] +use crate::raw::Deadline; /// Metadata associated with a task. pub struct Metadata { #[cfg(feature = "metadata-name")] name: Mutex>>, - #[cfg(feature = "metadata-deadline")] + #[cfg(feature = "scheduler-deadline")] deadline: raw::Deadline, } @@ -23,7 +25,7 @@ impl Metadata { name: Mutex::new(Cell::new(None)), // NOTE: The deadline is set to zero to allow the initializer to reside in `.bss`. This // will be lazily initalized in `initialize_impl` - #[cfg(feature = "metadata-deadline")] + #[cfg(feature = "scheduler-deadline")] deadline: raw::Deadline::new_unset(), } } @@ -59,10 +61,62 @@ impl Metadata { critical_section::with(|cs| self.name.borrow(cs).set(Some(name))) } - /// Earliest Deadline First scheduler Deadline. This field should not be accessed - /// outside the context of the task itself as it being polled by the executor. - #[cfg(feature = "metadata-deadline")] + /// Get this task's deadline. + #[cfg(feature = "scheduler-deadline")] pub fn deadline(&self) -> &raw::Deadline { &self.deadline } + + /// Set this task's deadline. + /// + /// This method does NOT check whether the deadline has already passed. + #[cfg(feature = "scheduler-deadline")] + pub fn set_deadline(&self, instant_ticks: u64) { + self.deadline.set(instant_ticks); + } + + /// Remove this task's deadline. + /// This brings it back to the defaul where it's not scheduled ahead of other tasks. + #[cfg(feature = "scheduler-deadline")] + pub fn unset_deadline(&self) { + self.deadline.set(Deadline::UNSET_DEADLINE_TICKS); + } + + /// Set this task's deadline `duration_ticks` in the future from when + /// this future is polled. This deadline is saturated to the max tick value. + /// + /// Analogous to `Timer::after`. + #[cfg(all(feature = "scheduler-deadline", feature = "embassy-time-driver"))] + pub fn set_deadline_after(&self, duration_ticks: u64) { + let now = embassy_time_driver::now(); + + // Since ticks is a u64, saturating add is PROBABLY overly cautious, leave + // it for now, we can probably make this wrapping_add for performance + // reasons later. + let deadline = now.saturating_add(duration_ticks); + + self.set_deadline(deadline); + } + + /// Set the this task's deadline `increment_ticks` from the previous deadline. + /// + /// This deadline is saturated to the max tick value. + /// + /// Note that by default (unless otherwise set), tasks start life with the deadline + /// not set, which means this method will have no effect. + /// + /// Analogous to one increment of `Ticker::every().next()`. + /// + /// Returns the deadline that was set. + #[cfg(feature = "scheduler-deadline")] + pub fn increment_deadline(&self, duration_ticks: u64) { + let last = self.deadline().instant_ticks(); + + // Since ticks is a u64, saturating add is PROBABLY overly cautious, leave + // it for now, we can probably make this wrapping_add for performance + // reasons later. + let deadline = last.saturating_add(duration_ticks); + + self.set_deadline(deadline); + } } diff --git a/embassy-executor/src/raw/deadline.rs b/embassy-executor/src/raw/deadline.rs index 5b585195d..d08dd06ed 100644 --- a/embassy-executor/src/raw/deadline.rs +++ b/embassy-executor/src/raw/deadline.rs @@ -1,6 +1,4 @@ -use core::future::{poll_fn, Future}; use core::sync::atomic::{AtomicU32, Ordering}; -use core::task::Poll; /// A type for interacting with the deadline of the current task /// @@ -49,111 +47,4 @@ impl Deadline { pub fn is_unset(&self) -> bool { self.instant_ticks() == Self::UNSET_DEADLINE_TICKS } - - /// Set the current task's deadline at exactly `instant_ticks` - /// - /// This method is a future in order to access the currently executing task's - /// header which contains the deadline. - /// - /// Analogous to `Timer::at`. - /// - /// This method does NOT check whether the deadline has already passed. - #[must_use = "Setting deadline must be polled to be effective"] - pub fn set_current_task_deadline(instant_ticks: u64) -> impl Future { - poll_fn(move |cx| { - let task = super::task_from_waker(cx.waker()); - task.header().metadata.deadline().set(instant_ticks); - Poll::Ready(()) - }) - } - - /// Set the current task's deadline `duration_ticks` in the future from when - /// this future is polled. This deadline is saturated to the max tick value. - /// - /// This method is a future in order to access the currently executing task's - /// header which contains the deadline. - /// - /// Analogous to `Timer::after`. - /// - /// Returns the deadline that was set. - #[must_use = "Setting deadline must be polled to be effective"] - pub fn set_current_task_deadline_after(duration_ticks: u64) -> impl Future { - poll_fn(move |cx| { - let task = super::task_from_waker(cx.waker()); - let now = embassy_time_driver::now(); - - // Since ticks is a u64, saturating add is PROBABLY overly cautious, leave - // it for now, we can probably make this wrapping_add for performance - // reasons later. - let deadline = now.saturating_add(duration_ticks); - - task.header().metadata.deadline().set(deadline); - - Poll::Ready(Deadline::new(deadline)) - }) - } - - /// Set the current task's deadline `increment_ticks` from the previous deadline. - /// - /// This deadline is saturated to the max tick value. - /// - /// Note that by default (unless otherwise set), tasks start life with the deadline - /// u64::MAX, which means this method will have no effect. - /// - /// This method is a future in order to access the currently executing task's - /// header which contains the deadline - /// - /// Analogous to one increment of `Ticker::every().next()`. - /// - /// Returns the deadline that was set. - #[must_use = "Setting deadline must be polled to be effective"] - pub fn increment_current_task_deadline(increment_ticks: u64) -> impl Future { - poll_fn(move |cx| { - let task_header = super::task_from_waker(cx.waker()).header(); - - // Get the last value - let last = task_header.metadata.deadline().instant_ticks(); - - // Since ticks is a u64, saturating add is PROBABLY overly cautious, leave - // it for now, we can probably make this wrapping_add for performance - // reasons later. - let deadline = last.saturating_add(increment_ticks); - - // Store the new value - task_header.metadata.deadline().set(deadline); - - Poll::Ready(Deadline::new(deadline)) - }) - } - - /// Get the current task's deadline as a tick value. - /// - /// This method is a future in order to access the currently executing task's - /// header which contains the deadline - pub fn get_current_task_deadline() -> impl Future { - poll_fn(move |cx| { - let task = super::task_from_waker(cx.waker()); - - let deadline = task.header().metadata.deadline().instant_ticks(); - Poll::Ready(Self::new(deadline)) - }) - } - - /// Clear the current task's deadline, returning the previous value. - /// - /// This sets the deadline to the default value of `u64::MAX`, meaning all - /// tasks with set deadlines will be scheduled BEFORE this task. - #[must_use = "Clearing deadline must be polled to be effective"] - pub fn clear_current_task_deadline() -> impl Future { - poll_fn(move |cx| { - let task_header = super::task_from_waker(cx.waker()).header(); - - // get the old value - let deadline = task_header.metadata.deadline().instant_ticks(); - // Store the default value - task_header.metadata.deadline().set(Self::UNSET_DEADLINE_TICKS); - - Poll::Ready(Self::new(deadline)) - }) - } } diff --git a/embassy-executor/src/raw/mod.rs b/embassy-executor/src/raw/mod.rs index 86ee86842..6a9dd9749 100644 --- a/embassy-executor/src/raw/mod.rs +++ b/embassy-executor/src/raw/mod.rs @@ -26,7 +26,7 @@ pub(crate) mod util; #[cfg_attr(feature = "turbowakers", path = "waker_turbo.rs")] mod waker; -#[cfg(feature = "metadata-deadline")] +#[cfg(feature = "scheduler-deadline")] mod deadline; use core::future::Future; @@ -39,7 +39,7 @@ use core::sync::atomic::AtomicPtr; use core::sync::atomic::Ordering; use core::task::{Context, Poll, Waker}; -#[cfg(feature = "metadata-deadline")] +#[cfg(feature = "scheduler-deadline")] pub use deadline::Deadline; use embassy_executor_timer_queue::TimerQueueItem; #[cfg(feature = "arch-avr")] @@ -302,7 +302,7 @@ impl AvailableTask { // By default, deadlines are set to the maximum value, so that any task WITH // a set deadline will ALWAYS be scheduled BEFORE a task WITHOUT a set deadline - #[cfg(feature = "edf-scheduler")] + #[cfg(feature = "scheduler-deadline")] self.task .raw .metadata diff --git a/embassy-executor/src/raw/run_queue.rs b/embassy-executor/src/raw/run_queue.rs index 978ca082a..29c977226 100644 --- a/embassy-executor/src/raw/run_queue.rs +++ b/embassy-executor/src/raw/run_queue.rs @@ -2,7 +2,7 @@ use core::ptr::{addr_of_mut, NonNull}; use cordyceps::sorted_list::Links; use cordyceps::Linked; -#[cfg(feature = "edf-scheduler")] +#[cfg(feature = "scheduler-deadline")] use cordyceps::SortedList; #[cfg(target_has_atomic = "ptr")] @@ -83,7 +83,7 @@ impl RunQueue { /// Empty the queue, then call `on_task` for each task that was in the queue. /// NOTE: It is OK for `on_task` to enqueue more tasks. In this case they're left in the queue /// and will be processed by the *next* call to `dequeue_all`, *not* the current one. - #[cfg(not(feature = "edf-scheduler"))] + #[cfg(not(feature = "scheduler-deadline"))] pub(crate) fn dequeue_all(&self, on_task: impl Fn(TaskRef)) { let taken = self.stack.take_all(); for taskref in taken { @@ -106,7 +106,7 @@ impl RunQueue { /// /// This process will repeat until the local `sorted` queue AND the global /// runqueue are both empty, at which point this function will return. - #[cfg(feature = "edf-scheduler")] + #[cfg(feature = "scheduler-deadline")] pub(crate) fn dequeue_all(&self, on_task: impl Fn(TaskRef)) { let mut sorted = SortedList::::new_with_cmp(|lhs, rhs| { lhs.metadata -- cgit From 09701a339d9085d86a69bf271299d7b59eda9fdc Mon Sep 17 00:00:00 2001 From: Dion Dokter Date: Mon, 8 Sep 2025 12:33:04 +0200 Subject: Fix example --- embassy-executor/src/raw/deadline.rs | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'embassy-executor') diff --git a/embassy-executor/src/raw/deadline.rs b/embassy-executor/src/raw/deadline.rs index d08dd06ed..f6d016ae7 100644 --- a/embassy-executor/src/raw/deadline.rs +++ b/embassy-executor/src/raw/deadline.rs @@ -2,7 +2,7 @@ use core::sync::atomic::{AtomicU32, Ordering}; /// A type for interacting with the deadline of the current task /// -/// Requires the `edf-scheduler` feature. +/// Requires the `scheduler-deadline` feature. /// /// Note: Interacting with the deadline should be done locally in a task. /// In theory you could try to set or read the deadline from another task, -- cgit From 2e21dcf2e61440db8c56a421a87c7a6bd22424d0 Mon Sep 17 00:00:00 2001 From: Dion Dokter Date: Mon, 8 Sep 2025 13:20:47 +0200 Subject: Fix metadata --- embassy-executor/Cargo.toml | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'embassy-executor') diff --git a/embassy-executor/Cargo.toml b/embassy-executor/Cargo.toml index 66352a00e..fb4c4d579 100644 --- a/embassy-executor/Cargo.toml +++ b/embassy-executor/Cargo.toml @@ -24,7 +24,7 @@ build = [ {target = "thumbv7em-none-eabi", features = ["arch-cortex-m", "executor-thread"]}, {target = "thumbv7em-none-eabi", features = ["arch-cortex-m", "executor-interrupt"]}, {target = "thumbv7em-none-eabi", features = ["arch-cortex-m", "executor-interrupt", "executor-thread"]}, - {target = "thumbv7em-none-eabi", features = ["arch-cortex-m", "executor-interrupt", "executor-thread", "edf-scheduler"]}, + {target = "thumbv7em-none-eabi", features = ["arch-cortex-m", "executor-interrupt", "executor-thread", "scheduler-deadline", "embassy-time-driver"]}, {target = "armv7a-none-eabi", features = ["arch-cortex-ar", "executor-thread"]}, {target = "armv7r-none-eabi", features = ["arch-cortex-ar", "executor-thread"]}, {target = "armv7r-none-eabihf", features = ["arch-cortex-ar", "executor-thread"]}, @@ -47,7 +47,7 @@ flavors = [ [package.metadata.docs.rs] default-target = "thumbv7em-none-eabi" targets = ["thumbv7em-none-eabi"] -features = ["defmt", "arch-cortex-m", "executor-thread", "executor-interrupt", "edf-scheduler"] +features = ["defmt", "arch-cortex-m", "executor-thread", "executor-interrupt", "scheduler-deadline", "embassy-time-driver"] [dependencies] defmt = { version = "1.0.1", optional = true } -- cgit From e1209c5563576d18c4d033b015c9a5dd6145d581 Mon Sep 17 00:00:00 2001 From: Dario Nieuwenhuis Date: Thu, 11 Sep 2025 15:40:33 +0200 Subject: executor: make Deadline actually private. --- embassy-executor/Cargo.toml | 2 +- embassy-executor/src/metadata.rs | 8 ++++---- embassy-executor/src/raw/deadline.rs | 14 ++++---------- embassy-executor/src/raw/mod.rs | 8 ++------ embassy-executor/src/raw/run_queue.rs | 8 ++------ 5 files changed, 13 insertions(+), 27 deletions(-) (limited to 'embassy-executor') diff --git a/embassy-executor/Cargo.toml b/embassy-executor/Cargo.toml index fb4c4d579..0ac666f80 100644 --- a/embassy-executor/Cargo.toml +++ b/embassy-executor/Cargo.toml @@ -36,7 +36,7 @@ build = [ [package.metadata.embassy_docs] src_base = "https://github.com/embassy-rs/embassy/blob/embassy-executor-v$VERSION/embassy-executor/src/" src_base_git = "https://github.com/embassy-rs/embassy/blob/$COMMIT/embassy-executor/src/" -features = ["defmt"] +features = ["defmt", "scheduler-deadline"] flavors = [ { name = "std", target = "x86_64-unknown-linux-gnu", features = ["arch-std", "executor-thread"] }, { name = "wasm", target = "wasm32-unknown-unknown", features = ["arch-wasm", "executor-thread"] }, diff --git a/embassy-executor/src/metadata.rs b/embassy-executor/src/metadata.rs index 81c5afafb..4220048a6 100644 --- a/embassy-executor/src/metadata.rs +++ b/embassy-executor/src/metadata.rs @@ -63,8 +63,8 @@ impl Metadata { /// Get this task's deadline. #[cfg(feature = "scheduler-deadline")] - pub fn deadline(&self) -> &raw::Deadline { - &self.deadline + pub fn deadline(&self) -> u64 { + self.deadline.instant_ticks() } /// Set this task's deadline. @@ -79,7 +79,7 @@ impl Metadata { /// This brings it back to the defaul where it's not scheduled ahead of other tasks. #[cfg(feature = "scheduler-deadline")] pub fn unset_deadline(&self) { - self.deadline.set(Deadline::UNSET_DEADLINE_TICKS); + self.deadline.set(Deadline::UNSET_TICKS); } /// Set this task's deadline `duration_ticks` in the future from when @@ -110,7 +110,7 @@ impl Metadata { /// Returns the deadline that was set. #[cfg(feature = "scheduler-deadline")] pub fn increment_deadline(&self, duration_ticks: u64) { - let last = self.deadline().instant_ticks(); + let last = self.deadline(); // Since ticks is a u64, saturating add is PROBABLY overly cautious, leave // it for now, we can probably make this wrapping_add for performance diff --git a/embassy-executor/src/raw/deadline.rs b/embassy-executor/src/raw/deadline.rs index f6d016ae7..cc89fadb0 100644 --- a/embassy-executor/src/raw/deadline.rs +++ b/embassy-executor/src/raw/deadline.rs @@ -7,7 +7,7 @@ use core::sync::atomic::{AtomicU32, Ordering}; /// Note: Interacting with the deadline should be done locally in a task. /// In theory you could try to set or read the deadline from another task, /// but that will result in weird (though not unsound) behavior. -pub struct Deadline { +pub(crate) struct Deadline { instant_ticks_hi: AtomicU32, instant_ticks_lo: AtomicU32, } @@ -21,7 +21,7 @@ impl Deadline { } pub(crate) const fn new_unset() -> Self { - Self::new(Self::UNSET_DEADLINE_TICKS) + Self::new(Self::UNSET_TICKS) } pub(crate) fn set(&self, instant_ticks: u64) { @@ -31,7 +31,7 @@ impl Deadline { } /// Deadline value in ticks, same time base and ticks as `embassy-time` - pub fn instant_ticks(&self) -> u64 { + pub(crate) fn instant_ticks(&self) -> u64 { let hi = self.instant_ticks_hi.load(Ordering::Relaxed) as u64; let lo = self.instant_ticks_lo.load(Ordering::Relaxed) as u64; @@ -40,11 +40,5 @@ impl Deadline { /// Sentinel value representing an "unset" deadline, which has lower priority /// than any other set deadline value - pub const UNSET_DEADLINE_TICKS: u64 = u64::MAX; - - /// Does the given Deadline represent an "unset" deadline? - #[inline] - pub fn is_unset(&self) -> bool { - self.instant_ticks() == Self::UNSET_DEADLINE_TICKS - } + pub(crate) const UNSET_TICKS: u64 = u64::MAX; } diff --git a/embassy-executor/src/raw/mod.rs b/embassy-executor/src/raw/mod.rs index 6a9dd9749..51a363385 100644 --- a/embassy-executor/src/raw/mod.rs +++ b/embassy-executor/src/raw/mod.rs @@ -40,7 +40,7 @@ use core::sync::atomic::Ordering; use core::task::{Context, Poll, Waker}; #[cfg(feature = "scheduler-deadline")] -pub use deadline::Deadline; +pub(crate) use deadline::Deadline; use embassy_executor_timer_queue::TimerQueueItem; #[cfg(feature = "arch-avr")] use portable_atomic::AtomicPtr; @@ -303,11 +303,7 @@ impl AvailableTask { // By default, deadlines are set to the maximum value, so that any task WITH // a set deadline will ALWAYS be scheduled BEFORE a task WITHOUT a set deadline #[cfg(feature = "scheduler-deadline")] - self.task - .raw - .metadata - .deadline() - .set(deadline::Deadline::UNSET_DEADLINE_TICKS); + self.task.raw.metadata.unset_deadline(); let task = TaskRef::new(self.task); diff --git a/embassy-executor/src/raw/run_queue.rs b/embassy-executor/src/raw/run_queue.rs index 29c977226..d98c26f73 100644 --- a/embassy-executor/src/raw/run_queue.rs +++ b/embassy-executor/src/raw/run_queue.rs @@ -108,12 +108,8 @@ impl RunQueue { /// runqueue are both empty, at which point this function will return. #[cfg(feature = "scheduler-deadline")] pub(crate) fn dequeue_all(&self, on_task: impl Fn(TaskRef)) { - let mut sorted = SortedList::::new_with_cmp(|lhs, rhs| { - lhs.metadata - .deadline() - .instant_ticks() - .cmp(&rhs.metadata.deadline().instant_ticks()) - }); + let mut sorted = + SortedList::::new_with_cmp(|lhs, rhs| lhs.metadata.deadline().cmp(&rhs.metadata.deadline())); loop { // For each loop, grab any newly pended items -- cgit