aboutsummaryrefslogtreecommitdiff
path: root/embassy-time-queue-utils
diff options
context:
space:
mode:
Diffstat (limited to 'embassy-time-queue-utils')
-rw-r--r--embassy-time-queue-utils/CHANGELOG.md13
-rw-r--r--embassy-time-queue-utils/Cargo.toml13
-rw-r--r--embassy-time-queue-utils/src/queue_generic.rs2
-rw-r--r--embassy-time-queue-utils/src/queue_integrated.rs121
4 files changed, 110 insertions, 39 deletions
diff --git a/embassy-time-queue-utils/CHANGELOG.md b/embassy-time-queue-utils/CHANGELOG.md
index ae4714f62..03d89f9a7 100644
--- a/embassy-time-queue-utils/CHANGELOG.md
+++ b/embassy-time-queue-utils/CHANGELOG.md
@@ -5,6 +5,19 @@ All notable changes to this project will be documented in this file.
5The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/), 5The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/),
6and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.html). 6and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.html).
7 7
8<!-- next-header -->
9## Unreleased - ReleaseDate
10
11## 0.3.0 - 2025-08-26
12
13## 0.2.1 - 2025-08-26
14
15- Removed the embassy-executor dependency
16
17## 0.2.0 - 2025-08-04
18
19Bumped embassy-executor
20
8## 0.1.0 - 2024-01-11 21## 0.1.0 - 2024-01-11
9 22
10Initial release 23Initial release
diff --git a/embassy-time-queue-utils/Cargo.toml b/embassy-time-queue-utils/Cargo.toml
index 48be12118..13da62874 100644
--- a/embassy-time-queue-utils/Cargo.toml
+++ b/embassy-time-queue-utils/Cargo.toml
@@ -1,6 +1,6 @@
1[package] 1[package]
2name = "embassy-time-queue-utils" 2name = "embassy-time-queue-utils"
3version = "0.1.0" 3version = "0.3.0"
4edition = "2021" 4edition = "2021"
5description = "Timer queue driver trait for embassy-time" 5description = "Timer queue driver trait for embassy-time"
6repository = "https://github.com/embassy-rs/embassy" 6repository = "https://github.com/embassy-rs/embassy"
@@ -22,7 +22,7 @@ links = "embassy-time-queue"
22 22
23[dependencies] 23[dependencies]
24heapless = "0.8" 24heapless = "0.8"
25embassy-executor = { version = "0.7.0", path = "../embassy-executor" } 25embassy-executor-timer-queue = { version = "0.1", path = "../embassy-executor-timer-queue", features = ["timer-item-size-6-words"] }
26 26
27[features] 27[features]
28#! ### Generic Queue 28#! ### Generic Queue
@@ -52,6 +52,15 @@ generic-queue-128 = ["_generic-queue"]
52 52
53_generic-queue = [] 53_generic-queue = []
54 54
55[package.metadata.embassy]
56build = [
57 {target = "thumbv6m-none-eabi", features = []},
58 {target = "thumbv6m-none-eabi", features = ["generic-queue-8"]},
59 # Xtensa builds
60 {group = "xtensa", build-std = ["core", "alloc"], target = "xtensa-esp32s2-none-elf", features = []},
61 {group = "xtensa", build-std = ["core", "alloc"], target = "xtensa-esp32s2-none-elf", features = ["generic-queue-8"]},
62]
63
55[package.metadata.embassy_docs] 64[package.metadata.embassy_docs]
56src_base = "https://github.com/embassy-rs/embassy/blob/embassy-time-queue-utils-v$VERSION/embassy-time-queue-utils/src/" 65src_base = "https://github.com/embassy-rs/embassy/blob/embassy-time-queue-utils-v$VERSION/embassy-time-queue-utils/src/"
57src_base_git = "https://github.com/embassy-rs/embassy/blob/$COMMIT/embassy-time-queue-utils/src/" 66src_base_git = "https://github.com/embassy-rs/embassy/blob/$COMMIT/embassy-time-queue-utils/src/"
diff --git a/embassy-time-queue-utils/src/queue_generic.rs b/embassy-time-queue-utils/src/queue_generic.rs
index 232035bc6..bff7a4735 100644
--- a/embassy-time-queue-utils/src/queue_generic.rs
+++ b/embassy-time-queue-utils/src/queue_generic.rs
@@ -34,6 +34,7 @@ impl Ord for Timer {
34} 34}
35 35
36/// A timer queue with a pre-determined capacity. 36/// A timer queue with a pre-determined capacity.
37#[derive(Debug)]
37pub struct ConstGenericQueue<const QUEUE_SIZE: usize> { 38pub struct ConstGenericQueue<const QUEUE_SIZE: usize> {
38 queue: Vec<Timer, QUEUE_SIZE>, 39 queue: Vec<Timer, QUEUE_SIZE>,
39} 40}
@@ -119,6 +120,7 @@ const QUEUE_SIZE: usize = 128;
119const QUEUE_SIZE: usize = 64; 120const QUEUE_SIZE: usize = 64;
120 121
121/// A timer queue with a pre-determined capacity. 122/// A timer queue with a pre-determined capacity.
123#[derive(Debug)]
122pub struct Queue { 124pub struct Queue {
123 queue: ConstGenericQueue<QUEUE_SIZE>, 125 queue: ConstGenericQueue<QUEUE_SIZE>,
124} 126}
diff --git a/embassy-time-queue-utils/src/queue_integrated.rs b/embassy-time-queue-utils/src/queue_integrated.rs
index 246cf1d63..2731d1ac6 100644
--- a/embassy-time-queue-utils/src/queue_integrated.rs
+++ b/embassy-time-queue-utils/src/queue_integrated.rs
@@ -1,15 +1,50 @@
1//! Timer queue operations. 1//! Timer queue operations.
2use core::cell::Cell; 2use core::cell::Cell;
3use core::cmp::min; 3use core::cmp::min;
4use core::ptr::NonNull;
4use core::task::Waker; 5use core::task::Waker;
5 6
6use embassy_executor::raw::TaskRef; 7use embassy_executor_timer_queue::TimerQueueItem;
8
9/// An item in the timer queue.
10#[derive(Default)]
11struct QueueItem {
12 /// The next item in the queue.
13 ///
14 /// If this field contains `Some`, the item is in the queue. The last item in the queue has a
15 /// value of `Some(dangling_pointer)`
16 pub next: Cell<Option<NonNull<QueueItem>>>,
17
18 /// The time at which this item expires.
19 pub expires_at: u64,
20
21 /// The registered waker. If Some, the item is enqueued in the timer queue.
22 pub waker: Option<Waker>,
23}
24
25unsafe impl Sync for QueueItem {}
7 26
8/// A timer queue, with items integrated into tasks. 27/// A timer queue, with items integrated into tasks.
28///
29/// # Safety
30///
31/// **This Queue is only safe when there is a single integrated queue in the system.**
32///
33/// If there are multiple integrated queues, additional checks are necessary to ensure that a Waker
34/// is not attempted to be enqueued in multiple queues.
9pub struct Queue { 35pub struct Queue {
10 head: Cell<Option<TaskRef>>, 36 head: Cell<Option<NonNull<QueueItem>>>,
11} 37}
12 38
39impl core::fmt::Debug for Queue {
40 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
41 f.debug_struct("Queue").finish()
42 }
43}
44
45unsafe impl Send for Queue {}
46unsafe impl Sync for Queue {}
47
13impl Queue { 48impl Queue {
14 /// Creates a new timer queue. 49 /// Creates a new timer queue.
15 pub const fn new() -> Self { 50 pub const fn new() -> Self {
@@ -21,25 +56,41 @@ impl Queue {
21 /// If this function returns `true`, the called should find the next expiration time and set 56 /// If this function returns `true`, the called should find the next expiration time and set
22 /// a new alarm for that time. 57 /// a new alarm for that time.
23 pub fn schedule_wake(&mut self, at: u64, waker: &Waker) -> bool { 58 pub fn schedule_wake(&mut self, at: u64, waker: &Waker) -> bool {
24 let task = embassy_executor::raw::task_from_waker(waker); 59 let item = unsafe {
25 let item = task.timer_queue_item(); 60 // Safety: the `&mut self`, along with the Safety note of the Queue, are sufficient to
26 if item.next.get().is_none() { 61 // ensure that this function creates the only mutable reference to the queue item.
27 // If not in the queue, add it and update. 62 TimerQueueItem::from_embassy_waker(waker)
28 let prev = self.head.replace(Some(task)); 63 };
29 item.next.set(if prev.is_none() { 64 let item = unsafe { item.as_mut::<QueueItem>() };
30 Some(unsafe { TaskRef::dangling() }) 65 match item.waker.as_ref() {
31 } else { 66 Some(_) if at <= item.expires_at => {
32 prev 67 // If expiration is sooner than previously set, update.
33 }); 68 item.expires_at = at;
34 item.expires_at.set(at); 69 // The waker is always stored in its own queue item, so we don't need to update it.
35 true 70
36 } else if at <= item.expires_at.get() { 71 // Trigger a queue update in case this item can be immediately dequeued.
37 // If expiration is sooner than previously set, update. 72 true
38 item.expires_at.set(at); 73 }
39 true 74 Some(_) => {
40 } else { 75 // Queue item does not need to be updated, the task will be scheduled to be woken
41 // Task does not need to be updated. 76 // before the new expiration.
42 false 77 false
78 }
79 None => {
80 // If not in the queue, add it and update.
81 let mut item_ptr = NonNull::from(item);
82 let prev = self.head.replace(Some(item_ptr));
83
84 let item = unsafe { item_ptr.as_mut() };
85
86 item.expires_at = at;
87 item.waker = Some(waker.clone());
88 item.next.set(prev);
89 // The default implementation doesn't care about the
90 // opaque payload, leave it unchanged.
91
92 true
93 }
43 } 94 }
44 } 95 }
45 96
@@ -50,33 +101,29 @@ impl Queue {
50 pub fn next_expiration(&mut self, now: u64) -> u64 { 101 pub fn next_expiration(&mut self, now: u64) -> u64 {
51 let mut next_expiration = u64::MAX; 102 let mut next_expiration = u64::MAX;
52 103
53 self.retain(|p| { 104 self.retain(|item| {
54 let item = p.timer_queue_item(); 105 if item.expires_at <= now {
55 let expires = item.expires_at.get();
56
57 if expires <= now {
58 // Timer expired, process task. 106 // Timer expired, process task.
59 embassy_executor::raw::wake_task(p); 107 if let Some(waker) = item.waker.take() {
108 waker.wake();
109 }
60 false 110 false
61 } else { 111 } else {
62 // Timer didn't yet expire, or never expires. 112 // Timer didn't yet expire, or never expires.
63 next_expiration = min(next_expiration, expires); 113 next_expiration = min(next_expiration, item.expires_at);
64 expires != u64::MAX 114 item.expires_at != u64::MAX
65 } 115 }
66 }); 116 });
67 117
68 next_expiration 118 next_expiration
69 } 119 }
70 120
71 fn retain(&self, mut f: impl FnMut(TaskRef) -> bool) { 121 fn retain(&mut self, mut f: impl FnMut(&mut QueueItem) -> bool) {
72 let mut prev = &self.head; 122 let mut prev = &self.head;
73 while let Some(p) = prev.get() { 123 while let Some(mut p) = prev.get() {
74 if unsafe { p == TaskRef::dangling() } { 124 let mut item = unsafe { p.as_mut() };
75 // prev was the last item, stop 125
76 break; 126 if f(&mut item) {
77 }
78 let item = p.timer_queue_item();
79 if f(p) {
80 // Skip to next 127 // Skip to next
81 prev = &item.next; 128 prev = &item.next;
82 } else { 129 } else {