Merge #959

959: Generic, executor-agnostic queue implementation r=ivmarkov a=ivmarkov

Hopefully relatively well documented.

Implementation relies on a fixed-size `SortedLinkedList` from `heapless`. (By default, for up to 128 timer schedules, but we can lower this number to - say - 64.)

As discussed earlier, on queue overflow, the `WakerRegistration` approach is utilized, whereas the waker that is ordered first in the queue is awoken to make room for the incoming one (which might be the waker that would be awoken after all!). Wakers are compared with `Waker::will_wake`, so the queue should actually not fill up that easily, if at all.

I've left provisions for the user to manually instantiate the queue using a dedicated macro - `generic_queue!` so that users willing to adjust the queue size, or users (like me) who have to use the queue in a complex "on-top-of-RTOS-but-the-timer-driver-calling-back-from-ISR" scenario can customize the mutex that protects the queue.

The one thing I'm not completely happy with is the need to call `{ embassy_time::queue::initialize() }` early on before any futures using embassy-time are polled, which is currently on the shoulders of the user. I'm open to any ideas where we can get rid of this and do it on the first call to `_embassy_time_schedule_wake`, without introducing very complex combinations of critical sections, atomics and whatnot.




Co-authored-by: ivmarkov <[email protected]>
Co-authored-by: Dario Nieuwenhuis <[email protected]>

1 files changed, 58 insertions, 0 deletions

diff --git a/embassy-time/src/queue.rs b/embassy-time/src/queue.rs
new file mode 100644
index 000000000..c6f8b440a
--- /dev/null
+++ b/embassy-time/src/queue.rs
@@ -0,0 +1,58 @@
+//! Timer queue implementation
+//!
+//! This module defines the interface a timer queue needs to implement to power the `embassy_time` module.
+//!
+//! # Implementing a timer queue
+//!
+//! - Define a struct `MyTimerQueue`
+//! - Implement [`TimerQueue`] for it
+//! - Register it as the global timer queue with [`timer_queue_impl`](crate::timer_queue_impl).
+//!
+//! # Linkage details
+//!
+//! Check the documentation of the [`driver`](crate::driver) module for more information.
+//!
+//! Similarly to driver, if there is none or multiple timer queues in the crate tree, linking will fail.
+//!
+//! # Example
+//!
+//! ```
+//! use core::task::Waker;
+//!
+//! use embassy_time::Instant;
+//! use embassy_time::queue::{TimerQueue};
+//!
+//! struct MyTimerQueue{}; // not public!
+//! embassy_time::timer_queue_impl!(static QUEUE: MyTimerQueue = MyTimerQueue{});
+//!
+//! impl TimerQueue for MyTimerQueue {
+//!     fn schedule_wake(&'static self, at: Instant, waker: &Waker) {
+//!         todo!()
+//!     }
+//! }
+//! ```
+use core::task::Waker;
+
+use crate::Instant;
+
+/// Timer queue
+pub trait TimerQueue {
+    /// Schedules a waker in the queue to be awoken at moment `at`.
+    /// If this moment is in the past, the waker might be awoken immediately.
+    fn schedule_wake(&'static self, at: Instant, waker: &Waker);
+}
+
+/// Set the TimerQueue implementation.
+///
+/// See the module documentation for an example.
+#[macro_export]
+macro_rules! timer_queue_impl {
+    (static $name:ident: $t: ty = $val:expr) => {
+        static $name: $t = $val;
+
+        #[no_mangle]
+        fn _embassy_time_schedule_wake(at: $crate::Instant, waker: &core::task::Waker) {
+            <$t as $crate::queue::TimerQueue>::schedule_wake(&$name, at, waker);
+        }
+    };
+}