9 files changed, 513 insertions, 301 deletions

diff --git a/embassy-executor/src/raw/deadline.rs b/embassy-executor/src/raw/deadline.rs
new file mode 100644
index 000000000..cc89fadb0
--- /dev/null
+++ b/embassy-executor/src/raw/deadline.rs
@@ -0,0 +1,44 @@
+use core::sync::atomic::{AtomicU32, Ordering};
+
+/// A type for interacting with the deadline of the current task
+///
+/// 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,
+/// but that will result in weird (though not unsound) behavior.
+pub(crate) struct Deadline {
+    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_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(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;
+
+        (hi << 32) | lo
+    }
+
+    /// Sentinel value representing an "unset" deadline, which has lower priority
+    /// than any other set deadline value
+    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 88d839e07..9f36c60bc 100644
--- a/embassy-executor/src/raw/mod.rs
+++ b/embassy-executor/src/raw/mod.rs
@@ -7,22 +7,28 @@
 //! 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 = "8"), path = "state_atomics_arm.rs")]
-#[cfg_attr(all(not(cortex_m), target_has_atomic = "8"), path = "state_atomics.rs")]
-#[cfg_attr(not(target_has_atomic = "8"), path = "state_critical_section.rs")]
+#[cfg_attr(all(cortex_m, target_has_atomic = "32"), path = "state_atomics_arm.rs")]
+#[cfg_attr(
+    all(not(cortex_m), any(target_has_atomic = "8", target_has_atomic = "32")),
+    path = "state_atomics.rs"
+)]
+#[cfg_attr(
+    not(any(target_has_atomic = "8", target_has_atomic = "32")),
+    path = "state_critical_section.rs"
+)]
 mod state;
 
-pub mod timer_queue;
-#[cfg(feature = "trace")]
-mod trace;
+#[cfg(feature = "_any_trace")]
+pub mod trace;
 pub(crate) mod util;
 #[cfg_attr(feature = "turbowakers", path = "waker_turbo.rs")]
 mod waker;
 
+#[cfg(feature = "scheduler-deadline")]
+mod deadline;
+
 use core::future::Future;
 use core::marker::PhantomData;
 use core::mem;
@@ -31,8 +37,11 @@ use core::ptr::NonNull;
 #[cfg(not(feature = "arch-avr"))]
 use core::sync::atomic::AtomicPtr;
 use core::sync::atomic::Ordering;
-use core::task::{Context, Poll};
+use core::task::{Context, Poll, Waker};
 
+#[cfg(feature = "scheduler-deadline")]
+pub(crate) use deadline::Deadline;
+use embassy_executor_timer_queue::TimerQueueItem;
 #[cfg(feature = "arch-avr")]
 use portable_atomic::AtomicPtr;
 
@@ -41,6 +50,12 @@ use self::state::State;
 use self::util::{SyncUnsafeCell, UninitCell};
 pub use self::waker::task_from_waker;
 use super::SpawnToken;
+use crate::{Metadata, SpawnError};
+
+#[no_mangle]
+extern "Rust" fn __embassy_time_queue_item_from_waker(waker: &Waker) -> &'static mut TimerQueueItem {
+    unsafe { task_from_waker(waker).timer_queue_item() }
+}
 
 /// Raw task header for use in task pointers.
 ///
@@ -84,15 +99,21 @@ use super::SpawnToken;
 pub(crate) struct TaskHeader {
     pub(crate) state: State,
     pub(crate) run_queue_item: RunQueueItem,
+
     pub(crate) executor: AtomicPtr<SyncExecutor>,
     poll_fn: SyncUnsafeCell<Option<unsafe fn(TaskRef)>>,
 
     /// Integrated timer queue storage. This field should not be accessed outside of the timer queue.
-    pub(crate) timer_queue_item: timer_queue::TimerQueueItem,
+    pub(crate) timer_queue_item: TimerQueueItem,
+
+    pub(crate) metadata: Metadata,
+
+    #[cfg(feature = "rtos-trace")]
+    all_tasks_next: AtomicPtr<TaskHeader>,
 }
 
 /// This is essentially a `&'static TaskStorage<F>` where the type of the future has been erased.
-#[derive(Clone, Copy, PartialEq)]
+#[derive(Debug, Clone, Copy, PartialEq)]
 pub struct TaskRef {
     ptr: NonNull<TaskHeader>,
 }
@@ -114,29 +135,27 @@ impl TaskRef {
         }
     }
 
-    /// # Safety
-    ///
-    /// The result of this function must only be compared
-    /// for equality, or stored, but not used.
-    pub const unsafe fn dangling() -> Self {
-        Self {
-            ptr: NonNull::dangling(),
-        }
-    }
-
     pub(crate) fn header(self) -> &'static TaskHeader {
         unsafe { self.ptr.as_ref() }
     }
 
+    pub(crate) fn metadata(self) -> &'static Metadata {
+        unsafe { &self.ptr.as_ref().metadata }
+    }
+
     /// Returns a reference to the executor that the task is currently running on.
     pub unsafe fn executor(self) -> Option<&'static Executor> {
         let executor = self.header().executor.load(Ordering::Relaxed);
         executor.as_ref().map(|e| Executor::wrap(e))
     }
 
-    /// Returns a reference to the timer queue item.
-    pub fn timer_queue_item(&self) -> &'static timer_queue::TimerQueueItem {
-        &self.header().timer_queue_item
+    /// Returns a mutable reference to the timer queue item.
+    ///
+    /// Safety
+    ///
+    /// This function must only be called in the context of the integrated timer queue.
+    pub unsafe fn timer_queue_item(mut self) -> &'static mut TimerQueueItem {
+        unsafe { &mut self.ptr.as_mut().timer_queue_item }
     }
 
     /// The returned pointer is valid for the entire TaskStorage.
@@ -144,10 +163,10 @@ impl TaskRef {
         self.ptr.as_ptr()
     }
 
-    /// Get the ID for a task
-    #[cfg(feature = "trace")]
-    pub fn as_id(self) -> u32 {
-        self.ptr.as_ptr() as u32
+    /// Returns the task ID.
+    /// This can be used in combination with rtos-trace to match task names with IDs
+    pub fn id(&self) -> u32 {
+        self.as_ptr() as u32
     }
 }
 
@@ -189,7 +208,10 @@ impl<F: Future + 'static> TaskStorage<F> {
                 // Note: this is lazily initialized so that a static `TaskStorage` will go in `.bss`
                 poll_fn: SyncUnsafeCell::new(None),
 
-                timer_queue_item: timer_queue::TimerQueueItem::new(),
+                timer_queue_item: TimerQueueItem::new(),
+                metadata: Metadata::new(),
+                #[cfg(feature = "rtos-trace")]
+                all_tasks_next: AtomicPtr::new(core::ptr::null_mut()),
             },
             future: UninitCell::uninit(),
         }
@@ -208,11 +230,11 @@ impl<F: Future + 'static> TaskStorage<F> {
     ///
     /// Once the task has finished running, you may spawn it again. It is allowed to spawn it
     /// on a different executor.
-    pub fn spawn(&'static self, future: impl FnOnce() -> F) -> SpawnToken<impl Sized> {
+    pub fn spawn(&'static self, future: impl FnOnce() -> F) -> Result<SpawnToken<impl Sized>, SpawnError> {
         let task = AvailableTask::claim(self);
         match task {
-            Some(task) => task.initialize(future),
-            None => SpawnToken::new_failed(),
+            Some(task) => Ok(task.initialize(future)),
+            None => Err(SpawnError::Busy),
         }
     }
 
@@ -224,7 +246,7 @@ impl<F: Future + 'static> TaskStorage<F> {
         let mut cx = Context::from_waker(&waker);
         match future.poll(&mut cx) {
             Poll::Ready(_) => {
-                #[cfg(feature = "trace")]
+                #[cfg(feature = "_any_trace")]
                 let exec_ptr: *const SyncExecutor = this.raw.executor.load(Ordering::Relaxed);
 
                 // As the future has finished and this function will not be called
@@ -239,7 +261,7 @@ impl<F: Future + 'static> TaskStorage<F> {
                 // after we're done with it.
                 this.raw.state.despawn();
 
-                #[cfg(feature = "trace")]
+                #[cfg(feature = "_any_trace")]
                 trace::task_end(exec_ptr, &p);
             }
             Poll::Pending => {}
@@ -274,6 +296,7 @@ impl<F: Future + 'static> AvailableTask<F> {
 
     fn initialize_impl<S>(self, future: impl FnOnce() -> F) -> SpawnToken<S> {
         unsafe {
+            self.task.raw.metadata.reset();
             self.task.raw.poll_fn.set(Some(TaskStorage::<F>::poll));
             self.task.future.write_in_place(future);
 
@@ -340,10 +363,10 @@ impl<F: Future + 'static, const N: usize> TaskPool<F, N> {
         }
     }
 
-    fn spawn_impl<T>(&'static self, future: impl FnOnce() -> F) -> SpawnToken<T> {
+    fn spawn_impl<T>(&'static self, future: impl FnOnce() -> F) -> Result<SpawnToken<T>, SpawnError> {
         match self.pool.iter().find_map(AvailableTask::claim) {
-            Some(task) => task.initialize_impl::<T>(future),
-            None => SpawnToken::new_failed(),
+            Some(task) => Ok(task.initialize_impl::<T>(future)),
+            None => Err(SpawnError::Busy),
         }
     }
 
@@ -354,7 +377,7 @@ impl<F: Future + 'static, const N: usize> TaskPool<F, N> {
     /// This will loop over the pool and spawn the task in the first storage that
     /// is currently free. If none is free, a "poisoned" SpawnToken is returned,
     /// which will cause [`Spawner::spawn()`](super::Spawner::spawn) to return the error.
-    pub fn spawn(&'static self, future: impl FnOnce() -> F) -> SpawnToken<impl Sized> {
+    pub fn spawn(&'static self, future: impl FnOnce() -> F) -> Result<SpawnToken<impl Sized>, SpawnError> {
         self.spawn_impl::<F>(future)
     }
 
@@ -367,7 +390,7 @@ impl<F: Future + 'static, const N: usize> TaskPool<F, N> {
     /// SAFETY: `future` must be a closure of the form `move || my_async_fn(args)`, where `my_async_fn`
     /// is an `async fn`, NOT a hand-written `Future`.
     #[doc(hidden)]
-    pub unsafe fn _spawn_async_fn<FutFn>(&'static self, future: FutFn) -> SpawnToken<impl Sized>
+    pub unsafe fn _spawn_async_fn<FutFn>(&'static self, future: FutFn) -> Result<SpawnToken<impl Sized>, SpawnError>
     where
         FutFn: FnOnce() -> F,
     {
@@ -412,7 +435,7 @@ impl SyncExecutor {
     /// - `task` must NOT be already enqueued (in this executor or another one).
     #[inline(always)]
     unsafe fn enqueue(&self, task: TaskRef, l: state::Token) {
-        #[cfg(feature = "trace")]
+        #[cfg(feature = "_any_trace")]
         trace::task_ready_begin(self, &task);
 
         if self.run_queue.enqueue(task, l) {
@@ -425,7 +448,7 @@ impl SyncExecutor {
             .executor
             .store((self as *const Self).cast_mut(), Ordering::Relaxed);
 
-        #[cfg(feature = "trace")]
+        #[cfg(feature = "_any_trace")]
         trace::task_new(self, &task);
 
         state::locked(|l| {
@@ -437,23 +460,23 @@ impl SyncExecutor {
     ///
     /// Same as [`Executor::poll`], plus you must only call this on the thread this executor was created.
     pub(crate) unsafe fn poll(&'static self) {
-        #[cfg(feature = "trace")]
+        #[cfg(feature = "_any_trace")]
         trace::poll_start(self);
 
         self.run_queue.dequeue_all(|p| {
             let task = p.header();
 
-            #[cfg(feature = "trace")]
+            #[cfg(feature = "_any_trace")]
             trace::task_exec_begin(self, &p);
 
             // Run the task
             task.poll_fn.get().unwrap_unchecked()(p);
 
-            #[cfg(feature = "trace")]
+            #[cfg(feature = "_any_trace")]
             trace::task_exec_end(self, &p);
         });
 
-        #[cfg(feature = "trace")]
+        #[cfg(feature = "_any_trace")]
         trace::executor_idle(self)
     }
 }
diff --git a/embassy-executor/src/raw/run_queue.rs b/embassy-executor/src/raw/run_queue.rs
new file mode 100644
index 000000000..b8b052310
--- /dev/null
+++ b/embassy-executor/src/raw/run_queue.rs
@@ -0,0 +1,213 @@
+use core::ptr::{addr_of_mut, NonNull};
+
+use cordyceps::sorted_list::Links;
+use cordyceps::Linked;
+#[cfg(any(feature = "scheduler-priority", feature = "scheduler-deadline"))]
+use cordyceps::SortedList;
+
+#[cfg(target_has_atomic = "ptr")]
+type TransferStack<T> = cordyceps::TransferStack<T>;
+
+#[cfg(not(target_has_atomic = "ptr"))]
+type TransferStack<T> = MutexTransferStack<T>;
+
+use super::{TaskHeader, TaskRef};
+
+/// Use `cordyceps::sorted_list::Links` as the singly linked list
+/// for RunQueueItems.
+pub(crate) type RunQueueItem = Links<TaskHeader>;
+
+/// 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<Links<TaskHeader>> for TaskHeader {
+    type Handle = TaskRef;
+
+    // Convert a TaskRef into a TaskHeader ptr
+    fn into_ptr(r: TaskRef) -> NonNull<TaskHeader> {
+        r.ptr
+    }
+
+    // Convert a TaskHeader into a TaskRef
+    unsafe fn from_ptr(ptr: NonNull<TaskHeader>) -> 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<TaskHeader>) -> NonNull<Links<TaskHeader>> {
+        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<TaskHeader>,
+}
+
+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, _tok: super::state::Token) -> bool {
+        self.stack.push_was_empty(
+            task,
+            #[cfg(not(target_has_atomic = "ptr"))]
+            _tok,
+        )
+    }
+
+    /// # 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(any(feature = "scheduler-priority", feature = "scheduler-deadline")))]
+    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(any(feature = "scheduler-priority", feature = "scheduler-deadline"))]
+    pub(crate) fn dequeue_all(&self, on_task: impl Fn(TaskRef)) {
+        let mut sorted = SortedList::<TaskHeader>::new_with_cmp(|lhs, rhs| {
+            // compare by priority first
+            #[cfg(feature = "scheduler-priority")]
+            {
+                let lp = lhs.metadata.priority();
+                let rp = rhs.metadata.priority();
+                if lp != rp {
+                    return lp.cmp(&rp).reverse();
+                }
+            }
+            // compare deadlines in case of tie.
+            #[cfg(feature = "scheduler-deadline")]
+            {
+                let ld = lhs.metadata.deadline();
+                let rd = rhs.metadata.deadline();
+                if ld != rd {
+                    return ld.cmp(&rd);
+                }
+            }
+            core::cmp::Ordering::Equal
+        });
+
+        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);
+    })
+}
+
+/// A wrapper type that acts like TransferStack by wrapping a normal Stack in a CS mutex
+#[cfg(not(target_has_atomic = "ptr"))]
+struct MutexTransferStack<T: Linked<cordyceps::stack::Links<T>>> {
+    inner: critical_section::Mutex<core::cell::UnsafeCell<cordyceps::Stack<T>>>,
+}
+
+#[cfg(not(target_has_atomic = "ptr"))]
+impl<T: Linked<cordyceps::stack::Links<T>>> MutexTransferStack<T> {
+    const fn new() -> Self {
+        Self {
+            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 {
+        // 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 inner = unsafe { &mut *self.inner.borrow(token).get() };
+        let is_empty = inner.is_empty();
+        inner.push(item);
+        is_empty
+    }
+
+    fn take_all(&self) -> cordyceps::Stack<T> {
+        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.
+            let inner = unsafe { &mut *self.inner.borrow(cs).get() };
+            inner.take_all()
+        })
+    }
+}
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 ce511d79a..000000000
--- a/embassy-executor/src/raw/run_queue_atomics.rs
+++ /dev/null
@@ -1,88 +0,0 @@
-use core::ptr;
-use core::ptr::NonNull;
-use core::sync::atomic::{AtomicPtr, Ordering};
-
-use super::{TaskHeader, TaskRef};
-use crate::raw::util::SyncUnsafeCell;
-
-pub(crate) struct RunQueueItem {
-    next: SyncUnsafeCell<Option<TaskRef>>,
-}
-
-impl RunQueueItem {
-    pub const fn new() -> Self {
-        Self {
-            next: SyncUnsafeCell::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: AtomicPtr<TaskHeader>,
-}
-
-impl RunQueue {
-    pub const fn new() -> Self {
-        Self {
-            head: AtomicPtr::new(ptr::null_mut()),
-        }
-    }
-
-    /// 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 {
-        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
-    }
-
-    /// 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 ptr = self.head.swap(ptr::null_mut(), Ordering::AcqRel);
-
-        // safety: the pointer is either null or valid
-        let mut next = unsafe { NonNull::new(ptr).map(|ptr| TaskRef::from_ptr(ptr.as_ptr())) };
-
-        // 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() };
-
-            task.header().state.run_dequeue();
-            on_task(task);
-        }
-    }
-}
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<Cell<Option<TaskRef>>>,
-}
-
-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<Cell<Option<TaskRef>>>,
-}
-
-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);
-        }
-    }
-}
diff --git a/embassy-executor/src/raw/state_atomics.rs b/embassy-executor/src/raw/state_atomics.rs
index b6576bfc2..6675875be 100644
--- a/embassy-executor/src/raw/state_atomics.rs
+++ b/embassy-executor/src/raw/state_atomics.rs
@@ -1,4 +1,15 @@
-use core::sync::atomic::{AtomicU32, Ordering};
+// Prefer pointer-width atomic operations, as narrower ones may be slower.
+#[cfg(all(target_pointer_width = "32", target_has_atomic = "32"))]
+type AtomicState = core::sync::atomic::AtomicU32;
+#[cfg(not(all(target_pointer_width = "32", target_has_atomic = "32")))]
+type AtomicState = core::sync::atomic::AtomicU8;
+
+#[cfg(all(target_pointer_width = "32", target_has_atomic = "32"))]
+type StateBits = u32;
+#[cfg(not(all(target_pointer_width = "32", target_has_atomic = "32")))]
+type StateBits = u8;
+
+use core::sync::atomic::Ordering;
 
 #[derive(Clone, Copy)]
 pub(crate) struct Token(());
@@ -11,18 +22,18 @@ pub(crate) fn locked<R>(f: impl FnOnce(Token) -> R) -> R {
 }
 
 /// Task is spawned (has a future)
-pub(crate) const STATE_SPAWNED: u32 = 1 << 0;
+pub(crate) const STATE_SPAWNED: StateBits = 1 << 0;
 /// Task is in the executor run queue
-pub(crate) const STATE_RUN_QUEUED: u32 = 1 << 1;
+pub(crate) const STATE_RUN_QUEUED: StateBits = 1 << 1;
 
 pub(crate) struct State {
-    state: AtomicU32,
+    state: AtomicState,
 }
 
 impl State {
     pub const fn new() -> State {
         Self {
-            state: AtomicU32::new(0),
+            state: AtomicState::new(0),
         }
     }
 
diff --git a/embassy-executor/src/raw/state_critical_section.rs b/embassy-executor/src/raw/state_critical_section.rs
index 6b627ff79..b69a6ac66 100644
--- a/embassy-executor/src/raw/state_critical_section.rs
+++ b/embassy-executor/src/raw/state_critical_section.rs
@@ -3,13 +3,18 @@ use core::cell::Cell;
 pub(crate) use critical_section::{with as locked, CriticalSection as Token};
 use critical_section::{CriticalSection, Mutex};
 
+#[cfg(target_arch = "avr")]
+type StateBits = u8;
+#[cfg(not(target_arch = "avr"))]
+type StateBits = usize;
+
 /// Task is spawned (has a future)
-pub(crate) const STATE_SPAWNED: u32 = 1 << 0;
+pub(crate) const STATE_SPAWNED: StateBits = 1 << 0;
 /// Task is in the executor run queue
-pub(crate) const STATE_RUN_QUEUED: u32 = 1 << 1;
+pub(crate) const STATE_RUN_QUEUED: StateBits = 1 << 1;
 
 pub(crate) struct State {
-    state: Mutex<Cell<u32>>,
+    state: Mutex<Cell<StateBits>>,
 }
 
 impl State {
@@ -19,11 +24,11 @@ impl State {
         }
     }
 
-    fn update<R>(&self, f: impl FnOnce(&mut u32) -> R) -> R {
+    fn update<R>(&self, f: impl FnOnce(&mut StateBits) -> R) -> R {
         critical_section::with(|cs| self.update_with_cs(cs, f))
     }
 
-    fn update_with_cs<R>(&self, cs: CriticalSection<'_>, f: impl FnOnce(&mut u32) -> R) -> R {
+    fn update_with_cs<R>(&self, cs: CriticalSection<'_>, f: impl FnOnce(&mut StateBits) -> R) -> R {
         let s = self.state.borrow(cs);
         let mut val = s.get();
         let r = f(&mut val);
diff --git a/embassy-executor/src/raw/timer_queue.rs b/embassy-executor/src/raw/timer_queue.rs
deleted file mode 100644
index e52453be4..000000000
--- a/embassy-executor/src/raw/timer_queue.rs
+++ /dev/null
@@ -1,73 +0,0 @@
-//! Timer queue operations.
-
-use core::cell::Cell;
-
-use super::TaskRef;
-
-#[cfg(feature = "_timer-item-payload")]
-macro_rules! define_opaque {
-    ($size:tt) => {
-        /// An opaque data type.
-        #[repr(align($size))]
-        pub struct OpaqueData {
-            data: [u8; $size],
-        }
-
-        impl OpaqueData {
-            const fn new() -> Self {
-                Self { data: [0; $size] }
-            }
-
-            /// Access the data as a reference to a type `T`.
-            ///
-            /// Safety:
-            ///
-            /// The caller must ensure that the size of the type `T` is less than, or equal to
-            /// the size of the payload, and must ensure that the alignment of the type `T` is
-            /// less than, or equal to the alignment of the payload.
-            ///
-            /// The type must be valid when zero-initialized.
-            pub unsafe fn as_ref<T>(&self) -> &T {
-                &*(self.data.as_ptr() as *const T)
-            }
-        }
-    };
-}
-
-#[cfg(feature = "timer-item-payload-size-1")]
-define_opaque!(1);
-#[cfg(feature = "timer-item-payload-size-2")]
-define_opaque!(2);
-#[cfg(feature = "timer-item-payload-size-4")]
-define_opaque!(4);
-#[cfg(feature = "timer-item-payload-size-8")]
-define_opaque!(8);
-
-/// An item in the timer queue.
-pub struct TimerQueueItem {
-    /// The next item in the queue.
-    ///
-    /// If this field contains `Some`, the item is in the queue. The last item in the queue has a
-    /// value of `Some(dangling_pointer)`
-    pub next: Cell<Option<TaskRef>>,
-
-    /// The time at which this item expires.
-    pub expires_at: Cell<u64>,
-
-    /// Some implementation-defined, zero-initialized piece of data.
-    #[cfg(feature = "_timer-item-payload")]
-    pub payload: OpaqueData,
-}
-
-unsafe impl Sync for TimerQueueItem {}
-
-impl TimerQueueItem {
-    pub(crate) const fn new() -> Self {
-        Self {
-            next: Cell::new(None),
-            expires_at: Cell::new(0),
-            #[cfg(feature = "_timer-item-payload")]
-            payload: OpaqueData::new(),
-        }
-    }
-}
diff --git a/embassy-executor/src/raw/trace.rs b/embassy-executor/src/raw/trace.rs
index aba519c8f..b3086948c 100644
--- a/embassy-executor/src/raw/trace.rs
+++ b/embassy-executor/src/raw/trace.rs
@@ -81,9 +81,94 @@
 
 #![allow(unused)]
 
-use crate::raw::{SyncExecutor, TaskRef};
+use core::cell::UnsafeCell;
+use core::sync::atomic::{AtomicPtr, AtomicUsize, Ordering};
 
-#[cfg(not(feature = "rtos-trace"))]
+#[cfg(feature = "rtos-trace")]
+use rtos_trace::TaskInfo;
+
+use crate::raw::{SyncExecutor, TaskHeader, TaskRef};
+use crate::spawner::{SpawnError, SpawnToken, Spawner};
+
+/// Global task tracker instance
+///
+/// This static provides access to the global task tracker which maintains
+/// a list of all tasks in the system. It's automatically updated by the
+/// task lifecycle hooks in the trace module.
+#[cfg(feature = "rtos-trace")]
+pub(crate) static TASK_TRACKER: TaskTracker = TaskTracker::new();
+
+/// A thread-safe tracker for all tasks in the system
+///
+/// This struct uses an intrusive linked list approach to track all tasks
+/// without additional memory allocations. It maintains a global list of
+/// tasks that can be traversed to find all currently existing tasks.
+#[cfg(feature = "rtos-trace")]
+pub(crate) struct TaskTracker {
+    head: AtomicPtr<TaskHeader>,
+}
+
+#[cfg(feature = "rtos-trace")]
+impl TaskTracker {
+    /// Creates a new empty task tracker
+    ///
+    /// Initializes a tracker with no tasks in its list.
+    pub const fn new() -> Self {
+        Self {
+            head: AtomicPtr::new(core::ptr::null_mut()),
+        }
+    }
+
+    /// Adds a task to the tracker
+    ///
+    /// This method inserts a task at the head of the intrusive linked list.
+    /// The operation is thread-safe and lock-free, using atomic operations
+    /// to ensure consistency even when called from different contexts.
+    ///
+    /// # Arguments
+    /// * `task` - The task reference to add to the tracker
+    pub fn add(&self, task: TaskRef) {
+        let task_ptr = task.as_ptr();
+
+        loop {
+            let current_head = self.head.load(Ordering::Acquire);
+            unsafe {
+                (*task_ptr).all_tasks_next.store(current_head, Ordering::Relaxed);
+            }
+
+            if self
+                .head
+                .compare_exchange(current_head, task_ptr.cast_mut(), Ordering::Release, Ordering::Relaxed)
+                .is_ok()
+            {
+                break;
+            }
+        }
+    }
+
+    /// Performs an operation on each task in the tracker
+    ///
+    /// This method traverses the entire list of tasks and calls the provided
+    /// function for each task. This allows inspecting or processing all tasks
+    /// in the system without modifying the tracker's structure.
+    ///
+    /// # Arguments
+    /// * `f` - A function to call for each task in the tracker
+    pub fn for_each<F>(&self, mut f: F)
+    where
+        F: FnMut(TaskRef),
+    {
+        let mut current = self.head.load(Ordering::Acquire);
+        while !current.is_null() {
+            let task = unsafe { TaskRef::from_ptr(current) };
+            f(task);
+
+            current = unsafe { (*current).all_tasks_next.load(Ordering::Acquire) };
+        }
+    }
+}
+
+#[cfg(feature = "trace")]
 extern "Rust" {
     /// This callback is called when the executor begins polling. This will always
     /// be paired with a later call to `_embassy_trace_executor_idle`.
@@ -145,7 +230,7 @@ extern "Rust" {
 
 #[inline]
 pub(crate) fn poll_start(executor: &SyncExecutor) {
-    #[cfg(not(feature = "rtos-trace"))]
+    #[cfg(feature = "trace")]
     unsafe {
         _embassy_trace_poll_start(executor as *const _ as u32)
     }
@@ -153,18 +238,31 @@ pub(crate) fn poll_start(executor: &SyncExecutor) {
 
 #[inline]
 pub(crate) fn task_new(executor: &SyncExecutor, task: &TaskRef) {
-    #[cfg(not(feature = "rtos-trace"))]
+    #[cfg(feature = "trace")]
     unsafe {
         _embassy_trace_task_new(executor as *const _ as u32, task.as_ptr() as u32)
     }
 
     #[cfg(feature = "rtos-trace")]
-    rtos_trace::trace::task_new(task.as_ptr() as u32);
+    {
+        rtos_trace::trace::task_new(task.as_ptr() as u32);
+        let name = task.metadata().name().unwrap_or("unnamed task\0");
+        let info = rtos_trace::TaskInfo {
+            name,
+            priority: 0,
+            stack_base: 0,
+            stack_size: 0,
+        };
+        rtos_trace::trace::task_send_info(task.id(), info);
+    }
+
+    #[cfg(feature = "rtos-trace")]
+    TASK_TRACKER.add(*task);
 }
 
 #[inline]
 pub(crate) fn task_end(executor: *const SyncExecutor, task: &TaskRef) {
-    #[cfg(not(feature = "rtos-trace"))]
+    #[cfg(feature = "trace")]
     unsafe {
         _embassy_trace_task_end(executor as u32, task.as_ptr() as u32)
     }
@@ -172,7 +270,7 @@ pub(crate) fn task_end(executor: *const SyncExecutor, task: &TaskRef) {
 
 #[inline]
 pub(crate) fn task_ready_begin(executor: &SyncExecutor, task: &TaskRef) {
-    #[cfg(not(feature = "rtos-trace"))]
+    #[cfg(feature = "trace")]
     unsafe {
         _embassy_trace_task_ready_begin(executor as *const _ as u32, task.as_ptr() as u32)
     }
@@ -182,7 +280,7 @@ pub(crate) fn task_ready_begin(executor: &SyncExecutor, task: &TaskRef) {
 
 #[inline]
 pub(crate) fn task_exec_begin(executor: &SyncExecutor, task: &TaskRef) {
-    #[cfg(not(feature = "rtos-trace"))]
+    #[cfg(feature = "trace")]
     unsafe {
         _embassy_trace_task_exec_begin(executor as *const _ as u32, task.as_ptr() as u32)
     }
@@ -192,7 +290,7 @@ pub(crate) fn task_exec_begin(executor: &SyncExecutor, task: &TaskRef) {
 
 #[inline]
 pub(crate) fn task_exec_end(executor: &SyncExecutor, task: &TaskRef) {
-    #[cfg(not(feature = "rtos-trace"))]
+    #[cfg(feature = "trace")]
     unsafe {
         _embassy_trace_task_exec_end(executor as *const _ as u32, task.as_ptr() as u32)
     }
@@ -202,7 +300,7 @@ pub(crate) fn task_exec_end(executor: &SyncExecutor, task: &TaskRef) {
 
 #[inline]
 pub(crate) fn executor_idle(executor: &SyncExecutor) {
-    #[cfg(not(feature = "rtos-trace"))]
+    #[cfg(feature = "trace")]
     unsafe {
         _embassy_trace_executor_idle(executor as *const _ as u32)
     }
@@ -210,10 +308,63 @@ pub(crate) fn executor_idle(executor: &SyncExecutor) {
     rtos_trace::trace::system_idle();
 }
 
+/// Returns an iterator over all active tasks in the system
+///
+/// This function provides a convenient way to iterate over all tasks
+/// that are currently tracked in the system. The returned iterator
+/// yields each task in the global task tracker.
+///
+/// # Returns
+/// An iterator that yields `TaskRef` items for each task
+#[cfg(feature = "rtos-trace")]
+fn get_all_active_tasks() -> impl Iterator<Item = TaskRef> + 'static {
+    struct TaskIterator<'a> {
+        tracker: &'a TaskTracker,
+        current: *mut TaskHeader,
+    }
+
+    impl<'a> Iterator for TaskIterator<'a> {
+        type Item = TaskRef;
+
+        fn next(&mut self) -> Option<Self::Item> {
+            if self.current.is_null() {
+                return None;
+            }
+
+            let task = unsafe { TaskRef::from_ptr(self.current) };
+            self.current = unsafe { (*self.current).all_tasks_next.load(Ordering::Acquire) };
+
+            Some(task)
+        }
+    }
+
+    TaskIterator {
+        tracker: &TASK_TRACKER,
+        current: TASK_TRACKER.head.load(Ordering::Acquire),
+    }
+}
+
+/// Perform an action on each active task
+#[cfg(feature = "rtos-trace")]
+fn with_all_active_tasks<F>(f: F)
+where
+    F: FnMut(TaskRef),
+{
+    TASK_TRACKER.for_each(f);
+}
+
 #[cfg(feature = "rtos-trace")]
 impl rtos_trace::RtosTraceOSCallbacks for crate::raw::SyncExecutor {
     fn task_list() {
-        // We don't know what tasks exist, so we can't send them.
+        with_all_active_tasks(|task| {
+            let info = rtos_trace::TaskInfo {
+                name: task.metadata().name().unwrap_or("unnamed task\0"),
+                priority: 0,
+                stack_base: 0,
+                stack_size: 0,
+            };
+            rtos_trace::trace::task_send_info(task.id(), info);
+        });
     }
     fn time() -> u64 {
         const fn gcd(a: u64, b: u64) -> u64 {