From e65e532c2a342f77080ac6fc8e5be11aa7d82575 Mon Sep 17 00:00:00 2001 From: Emil Fresk Date: Sun, 29 Jan 2023 20:16:23 +0100 Subject: Move common data structures to `rtic-common` --- rtic-common/.gitignore | 2 + rtic-common/CHANGELOG.md | 16 ++ rtic-common/Cargo.toml | 13 ++ rtic-common/src/lib.rs | 8 + rtic-common/src/wait_queue.rs | 271 ++++++++++++++++++++++++++++++++++ rtic-common/src/waker_registration.rs | 66 +++++++++ 6 files changed, 376 insertions(+) create mode 100644 rtic-common/.gitignore create mode 100644 rtic-common/CHANGELOG.md create mode 100644 rtic-common/Cargo.toml create mode 100644 rtic-common/src/lib.rs create mode 100644 rtic-common/src/wait_queue.rs create mode 100644 rtic-common/src/waker_registration.rs (limited to 'rtic-common') diff --git a/rtic-common/.gitignore b/rtic-common/.gitignore new file mode 100644 index 0000000..1e7caa9 --- /dev/null +++ b/rtic-common/.gitignore @@ -0,0 +1,2 @@ +Cargo.lock +target/ diff --git a/rtic-common/CHANGELOG.md b/rtic-common/CHANGELOG.md new file mode 100644 index 0000000..d3a9d84 --- /dev/null +++ b/rtic-common/CHANGELOG.md @@ -0,0 +1,16 @@ +# Change Log + +All notable changes to this project will be documented in this file. +This project adheres to [Semantic Versioning](http://semver.org/). + +For each category, *Added*, *Changed*, *Fixed* add new entries at the top! + +## [Unreleased] + +### Added + +### Changed + +### Fixed + +## [v1.0.0] - 2023-xx-xx diff --git a/rtic-common/Cargo.toml b/rtic-common/Cargo.toml new file mode 100644 index 0000000..258caae --- /dev/null +++ b/rtic-common/Cargo.toml @@ -0,0 +1,13 @@ +[package] +name = "rtic-common" +version = "1.0.0" +edition = "2021" + +# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html + +[dependencies] +critical-section = "1" + +[features] +default = [] +testing = ["critical-section/std"] diff --git a/rtic-common/src/lib.rs b/rtic-common/src/lib.rs new file mode 100644 index 0000000..3c75856 --- /dev/null +++ b/rtic-common/src/lib.rs @@ -0,0 +1,8 @@ +//! Crate + +#![no_std] +#![deny(missing_docs)] +//deny_warnings_placeholder_for_ci + +pub mod wait_queue; +pub mod waker_registration; diff --git a/rtic-common/src/wait_queue.rs b/rtic-common/src/wait_queue.rs new file mode 100644 index 0000000..ba8ff54 --- /dev/null +++ b/rtic-common/src/wait_queue.rs @@ -0,0 +1,271 @@ +//! ... + +use core::marker::PhantomPinned; +use core::pin::Pin; +use core::ptr::null_mut; +use core::sync::atomic::{AtomicBool, AtomicPtr, Ordering}; +use core::task::Waker; +use critical_section as cs; + +/// A helper definition of a wait queue. +pub type WaitQueue = LinkedList; + +/// A FIFO linked list for a wait queue. +pub struct LinkedList { + head: AtomicPtr>, // UnsafeCell<*mut Link> + tail: AtomicPtr>, +} + +impl LinkedList { + /// Create a new linked list. + pub const fn new() -> Self { + Self { + head: AtomicPtr::new(null_mut()), + tail: AtomicPtr::new(null_mut()), + } + } +} + +impl LinkedList { + const R: Ordering = Ordering::Relaxed; + + /// Pop the first element in the queue. + pub fn pop(&self) -> Option { + cs::with(|_| { + // Make sure all previous writes are visible + core::sync::atomic::fence(Ordering::SeqCst); + + let head = self.head.load(Self::R); + + // SAFETY: `as_ref` is safe as `insert` requires a valid reference to a link + if let Some(head_ref) = unsafe { head.as_ref() } { + // Move head to the next element + self.head.store(head_ref.next.load(Self::R), Self::R); + + // We read the value at head + let head_val = head_ref.val.clone(); + + let tail = self.tail.load(Self::R); + if head == tail { + // The queue is empty + self.tail.store(null_mut(), Self::R); + } + + if let Some(next_ref) = unsafe { head_ref.next.load(Self::R).as_ref() } { + next_ref.prev.store(null_mut(), Self::R); + } + + // Clear the pointers in the node. + head_ref.next.store(null_mut(), Self::R); + head_ref.prev.store(null_mut(), Self::R); + head_ref.is_poped.store(true, Self::R); + + return Some(head_val); + } + + None + }) + } + + /// Put an element at the back of the queue. + pub fn push(&self, link: Pin<&mut Link>) { + cs::with(|_| { + // Make sure all previous writes are visible + core::sync::atomic::fence(Ordering::SeqCst); + + let tail = self.tail.load(Self::R); + + // SAFETY: This datastructure does not move the underlying value. + let link = unsafe { link.get_unchecked_mut() }; + + if let Some(tail_ref) = unsafe { tail.as_ref() } { + // Queue is not empty + link.prev.store(tail, Self::R); + self.tail.store(link, Self::R); + tail_ref.next.store(link, Self::R); + } else { + // Queue is empty + self.tail.store(link, Self::R); + self.head.store(link, Self::R); + } + }); + } + + /// Check if the queue is empty. + pub fn is_empty(&self) -> bool { + self.head.load(Self::R).is_null() + } +} + +/// A link in the linked list. +pub struct Link { + pub(crate) val: T, + next: AtomicPtr>, + prev: AtomicPtr>, + is_poped: AtomicBool, + _up: PhantomPinned, +} + +impl Link { + const R: Ordering = Ordering::Relaxed; + + /// Create a new link. + pub const fn new(val: T) -> Self { + Self { + val, + next: AtomicPtr::new(null_mut()), + prev: AtomicPtr::new(null_mut()), + is_poped: AtomicBool::new(false), + _up: PhantomPinned, + } + } + + /// Return true if this link has been poped from the list. + pub fn is_poped(&self) -> bool { + self.is_poped.load(Self::R) + } + + /// Remove this link from a linked list. + pub fn remove_from_list(&mut self, list: &LinkedList) { + cs::with(|_| { + // Make sure all previous writes are visible + core::sync::atomic::fence(Ordering::SeqCst); + + let prev = self.prev.load(Self::R); + let next = self.next.load(Self::R); + self.is_poped.store(true, Self::R); + + match unsafe { (prev.as_ref(), next.as_ref()) } { + (None, None) => { + // Not in the list or alone in the list, check if list head == node address + let sp = self as *const _; + + if sp == list.head.load(Ordering::Relaxed) { + list.head.store(null_mut(), Self::R); + list.tail.store(null_mut(), Self::R); + } + } + (None, Some(next_ref)) => { + // First in the list + next_ref.prev.store(null_mut(), Self::R); + list.head.store(next, Self::R); + } + (Some(prev_ref), None) => { + // Last in the list + prev_ref.next.store(null_mut(), Self::R); + list.tail.store(prev, Self::R); + } + (Some(prev_ref), Some(next_ref)) => { + // Somewhere in the list + + // Connect the `prev.next` and `next.prev` with each other to remove the node + prev_ref.next.store(next, Self::R); + next_ref.prev.store(prev, Self::R); + } + } + }) + } +} + +#[cfg(test)] +impl LinkedList { + fn print(&self) { + cs::with(|_| { + // Make sure all previous writes are visible + core::sync::atomic::fence(Ordering::SeqCst); + + let mut head = self.head.load(Self::R); + let tail = self.tail.load(Self::R); + + println!( + "List - h = 0x{:x}, t = 0x{:x}", + head as usize, tail as usize + ); + + let mut i = 0; + + // SAFETY: `as_ref` is safe as `insert` requires a valid reference to a link + while let Some(head_ref) = unsafe { head.as_ref() } { + println!( + " {}: {:?}, s = 0x{:x}, n = 0x{:x}, p = 0x{:x}", + i, + head_ref.val, + head as usize, + head_ref.next.load(Ordering::Relaxed) as usize, + head_ref.prev.load(Ordering::Relaxed) as usize + ); + + head = head_ref.next.load(Self::R); + + i += 1; + } + }); + } +} + +#[cfg(test)] +impl Link { + fn print(&self) { + cs::with(|_| { + // Make sure all previous writes are visible + core::sync::atomic::fence(Ordering::SeqCst); + + println!("Link:"); + + println!( + " val = {:?}, n = 0x{:x}, p = 0x{:x}", + self.val, + self.next.load(Ordering::Relaxed) as usize, + self.prev.load(Ordering::Relaxed) as usize + ); + }); + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn linked_list() { + let wq = LinkedList::::new(); + + let mut i1 = Link::new(10); + let mut i2 = Link::new(11); + let mut i3 = Link::new(12); + let mut i4 = Link::new(13); + let mut i5 = Link::new(14); + + wq.push(unsafe { Pin::new_unchecked(&mut i1) }); + wq.push(unsafe { Pin::new_unchecked(&mut i2) }); + wq.push(unsafe { Pin::new_unchecked(&mut i3) }); + wq.push(unsafe { Pin::new_unchecked(&mut i4) }); + wq.push(unsafe { Pin::new_unchecked(&mut i5) }); + + wq.print(); + + wq.pop(); + i1.print(); + + wq.print(); + + i4.remove_from_list(&wq); + + wq.print(); + + // i1.remove_from_list(&wq); + // wq.print(); + + println!("i2"); + i2.remove_from_list(&wq); + wq.print(); + + println!("i3"); + i3.remove_from_list(&wq); + wq.print(); + + println!("i5"); + i5.remove_from_list(&wq); + wq.print(); + } +} diff --git a/rtic-common/src/waker_registration.rs b/rtic-common/src/waker_registration.rs new file mode 100644 index 0000000..174765c --- /dev/null +++ b/rtic-common/src/waker_registration.rs @@ -0,0 +1,66 @@ +//! Waker registration utility. + +use core::cell::UnsafeCell; +use core::task::Waker; + +/// A critical section based waker handler. +pub struct CriticalSectionWakerRegistration { + waker: UnsafeCell>, +} + +unsafe impl Send for CriticalSectionWakerRegistration {} +unsafe impl Sync for CriticalSectionWakerRegistration {} + +impl CriticalSectionWakerRegistration { + /// Create a new waker registration. + pub const fn new() -> Self { + Self { + waker: UnsafeCell::new(None), + } + } + + /// Register a waker. + /// This will overwrite the previous waker if there was one. + pub fn register(&self, new_waker: &Waker) { + critical_section::with(|_| { + // SAFETY: This access is protected by the critical section. + let self_waker = unsafe { &mut *self.waker.get() }; + + // From embassy + // https://github.com/embassy-rs/embassy/blob/b99533607ceed225dd12ae73aaa9a0d969a7365e/embassy-sync/src/waitqueue/waker.rs#L59-L61 + match self_waker { + // Optimization: If both the old and new Wakers wake the same task, we can simply + // keep the old waker, skipping the clone. (In most executor implementations, + // cloning a waker is somewhat expensive, comparable to cloning an Arc). + Some(ref w2) if (w2.will_wake(new_waker)) => {} + _ => { + // clone the new waker and store it + if let Some(old_waker) = core::mem::replace(self_waker, Some(new_waker.clone())) + { + // We had a waker registered for another task. Wake it, so the other task can + // reregister itself if it's still interested. + // + // If two tasks are waiting on the same thing concurrently, this will cause them + // to wake each other in a loop fighting over this WakerRegistration. This wastes + // CPU but things will still work. + // + // If the user wants to have two tasks waiting on the same thing they should use + // a more appropriate primitive that can store multiple wakers. + old_waker.wake() + } + } + } + }); + } + + /// Wake the waker. + pub fn wake(&self) { + critical_section::with(|_| { + // SAFETY: This access is protected by the critical section. + let self_waker = unsafe { &mut *self.waker.get() }; + if let Some(waker) = self_waker.take() { + waker.wake() + } + }); + } +} -- cgit v1.2.3 From 5c1cefbf4e249c38467e3f6eb4e061e5b8073d6c Mon Sep 17 00:00:00 2001 From: Emil Fresk Date: Mon, 30 Jan 2023 14:49:24 +0100 Subject: Add `rtic-arbiter` --- rtic-arbiter/.gitignore | 2 + rtic-arbiter/CHANGELOG.md | 16 +++++ rtic-arbiter/Cargo.toml | 18 +++++ rtic-arbiter/src/lib.rs | 175 +++++++++++++++++++++++++++++++++++++++++++++ rtic-channel/src/lib.rs | 28 ++------ rtic-common/src/dropper.rs | 26 +++++++ rtic-common/src/lib.rs | 1 + 7 files changed, 242 insertions(+), 24 deletions(-) create mode 100644 rtic-arbiter/.gitignore create mode 100644 rtic-arbiter/CHANGELOG.md create mode 100644 rtic-arbiter/Cargo.toml create mode 100644 rtic-arbiter/src/lib.rs create mode 100644 rtic-common/src/dropper.rs (limited to 'rtic-common') diff --git a/rtic-arbiter/.gitignore b/rtic-arbiter/.gitignore new file mode 100644 index 0000000..1e7caa9 --- /dev/null +++ b/rtic-arbiter/.gitignore @@ -0,0 +1,2 @@ +Cargo.lock +target/ diff --git a/rtic-arbiter/CHANGELOG.md b/rtic-arbiter/CHANGELOG.md new file mode 100644 index 0000000..d3a9d84 --- /dev/null +++ b/rtic-arbiter/CHANGELOG.md @@ -0,0 +1,16 @@ +# Change Log + +All notable changes to this project will be documented in this file. +This project adheres to [Semantic Versioning](http://semver.org/). + +For each category, *Added*, *Changed*, *Fixed* add new entries at the top! + +## [Unreleased] + +### Added + +### Changed + +### Fixed + +## [v1.0.0] - 2023-xx-xx diff --git a/rtic-arbiter/Cargo.toml b/rtic-arbiter/Cargo.toml new file mode 100644 index 0000000..b1afaf4 --- /dev/null +++ b/rtic-arbiter/Cargo.toml @@ -0,0 +1,18 @@ +[package] +name = "rtic-arbiter" +version = "1.0.0" +edition = "2021" + +# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html + +[dependencies] +critical-section = "1" +rtic-common = { version = "1.0.0", path = "../rtic-common" } + +[dev-dependencies] +tokio = { version = "1", features = ["rt", "macros", "time"] } + + +[features] +default = [] +testing = ["critical-section/std", "rtic-common/testing"] diff --git a/rtic-arbiter/src/lib.rs b/rtic-arbiter/src/lib.rs new file mode 100644 index 0000000..487c64c --- /dev/null +++ b/rtic-arbiter/src/lib.rs @@ -0,0 +1,175 @@ +//! Crate + +#![no_std] +#![deny(missing_docs)] +//deny_warnings_placeholder_for_ci + +use core::cell::UnsafeCell; +use core::future::poll_fn; +use core::ops::{Deref, DerefMut}; +use core::pin::Pin; +use core::sync::atomic::{fence, AtomicBool, Ordering}; +use core::task::{Poll, Waker}; + +use rtic_common::dropper::OnDrop; +use rtic_common::wait_queue::{Link, WaitQueue}; + +/// This is needed to make the async closure in `send` accept that we "share" +/// the link possible between threads. +#[derive(Clone)] +struct LinkPtr(*mut Option>); + +impl LinkPtr { + /// This will dereference the pointer stored within and give out an `&mut`. + unsafe fn get(&mut self) -> &mut Option> { + &mut *self.0 + } +} + +unsafe impl Send for LinkPtr {} +unsafe impl Sync for LinkPtr {} + +/// An FIFO waitqueue for use in shared bus usecases. +pub struct Arbiter { + wait_queue: WaitQueue, + inner: UnsafeCell, + taken: AtomicBool, +} + +impl Arbiter { + /// Create a new arbiter. + pub const fn new(inner: T) -> Self { + Self { + wait_queue: WaitQueue::new(), + inner: UnsafeCell::new(inner), + taken: AtomicBool::new(false), + } + } + + /// Get access to the inner value in the `Arbiter`. This will wait until access is granted, + /// for non-blocking access use `try_access`. + pub async fn access(&self) -> ExclusiveAccess<'_, T> { + let mut link_ptr: Option> = None; + + // Make this future `Drop`-safe, also shadow the original definition so we can't abuse it. + let mut link_ptr = LinkPtr(&mut link_ptr as *mut Option>); + + let mut link_ptr2 = link_ptr.clone(); + let dropper = OnDrop::new(|| { + // SAFETY: We only run this closure and dereference the pointer if we have + // exited the `poll_fn` below in the `drop(dropper)` call. The other dereference + // of this pointer is in the `poll_fn`. + if let Some(link) = unsafe { link_ptr2.get() } { + link.remove_from_list(&self.wait_queue); + } + }); + + poll_fn(|cx| { + critical_section::with(|_| { + fence(Ordering::SeqCst); + + // The queue is empty and noone has taken the value. + if self.wait_queue.is_empty() && !self.taken.load(Ordering::Relaxed) { + self.taken.store(true, Ordering::Relaxed); + + return Poll::Ready(()); + } + + // SAFETY: This pointer is only dereferenced here and on drop of the future + // which happens outside this `poll_fn`'s stack frame. + let link = unsafe { link_ptr.get() }; + if let Some(link) = link { + if link.is_poped() { + return Poll::Ready(()); + } + } else { + // Place the link in the wait queue on first run. + let link_ref = link.insert(Link::new(cx.waker().clone())); + + // SAFETY: The address to the link is stable as it is hidden behind + // `link_ptr`, and `link_ptr` shadows the original making it unmovable. + self.wait_queue + .push(unsafe { Pin::new_unchecked(link_ref) }); + } + + Poll::Pending + }) + }) + .await; + + // Make sure the link is removed from the queue. + drop(dropper); + + // SAFETY: One only gets here if there is exlusive access. + ExclusiveAccess { + arbiter: self, + inner: unsafe { &mut *self.inner.get() }, + } + } + + /// Non-blockingly tries to access the underlying value. + /// If someone is in queue to get it, this will return `None`. + pub fn try_access(&self) -> Option> { + critical_section::with(|_| { + fence(Ordering::SeqCst); + + // The queue is empty and noone has taken the value. + if self.wait_queue.is_empty() && !self.taken.load(Ordering::Relaxed) { + self.taken.store(true, Ordering::Relaxed); + + // SAFETY: One only gets here if there is exlusive access. + Some(ExclusiveAccess { + arbiter: self, + inner: unsafe { &mut *self.inner.get() }, + }) + } else { + None + } + }) + } +} + +/// This token represents exclusive access to the value protected by the `Arbiter`. +pub struct ExclusiveAccess<'a, T> { + arbiter: &'a Arbiter, + inner: &'a mut T, +} + +impl<'a, T> Drop for ExclusiveAccess<'a, T> { + fn drop(&mut self) { + critical_section::with(|_| { + fence(Ordering::SeqCst); + + if self.arbiter.wait_queue.is_empty() { + // If noone is in queue and we release exclusive access, reset `taken`. + self.arbiter.taken.store(false, Ordering::Relaxed); + } else if let Some(next) = self.arbiter.wait_queue.pop() { + // Wake the next one in queue. + next.wake(); + } + }) + } +} + +impl<'a, T> Deref for ExclusiveAccess<'a, T> { + type Target = T; + + fn deref(&self) -> &Self::Target { + self.inner + } +} + +impl<'a, T> DerefMut for ExclusiveAccess<'a, T> { + fn deref_mut(&mut self) -> &mut Self::Target { + self.inner + } +} + +#[cfg(test)] +#[macro_use] +extern crate std; + +#[cfg(test)] +mod tests { + // use super::*; +} diff --git a/rtic-channel/src/lib.rs b/rtic-channel/src/lib.rs index 2b237f6..6f816b5 100644 --- a/rtic-channel/src/lib.rs +++ b/rtic-channel/src/lib.rs @@ -14,8 +14,11 @@ use core::{ task::{Poll, Waker}, }; use heapless::Deque; -use rtic_common::wait_queue::{Link, WaitQueue}; use rtic_common::waker_registration::CriticalSectionWakerRegistration as WakerRegistration; +use rtic_common::{ + dropper::OnDrop, + wait_queue::{Link, WaitQueue}, +}; /// An MPSC channel for use in no-alloc systems. `N` sets the size of the queue. /// @@ -417,29 +420,6 @@ impl<'a, T, const N: usize> Drop for Receiver<'a, T, N> { } } -struct OnDrop { - f: core::mem::MaybeUninit, -} - -impl OnDrop { - pub fn new(f: F) -> Self { - Self { - f: core::mem::MaybeUninit::new(f), - } - } - - #[allow(unused)] - pub fn defuse(self) { - core::mem::forget(self) - } -} - -impl Drop for OnDrop { - fn drop(&mut self) { - unsafe { self.f.as_ptr().read()() } - } -} - #[cfg(test)] #[macro_use] extern crate std; diff --git a/rtic-common/src/dropper.rs b/rtic-common/src/dropper.rs new file mode 100644 index 0000000..a4b4d15 --- /dev/null +++ b/rtic-common/src/dropper.rs @@ -0,0 +1,26 @@ +//! A drop implementation runner. + +/// Runs a closure on drop. +pub struct OnDrop { + f: core::mem::MaybeUninit, +} + +impl OnDrop { + /// Make a new droppper given a closure. + pub fn new(f: F) -> Self { + Self { + f: core::mem::MaybeUninit::new(f), + } + } + + /// Make it not run drop. + pub fn defuse(self) { + core::mem::forget(self) + } +} + +impl Drop for OnDrop { + fn drop(&mut self) { + unsafe { self.f.as_ptr().read()() } + } +} diff --git a/rtic-common/src/lib.rs b/rtic-common/src/lib.rs index 3c75856..b8b5e0d 100644 --- a/rtic-common/src/lib.rs +++ b/rtic-common/src/lib.rs @@ -4,5 +4,6 @@ #![deny(missing_docs)] //deny_warnings_placeholder_for_ci +pub mod dropper; pub mod wait_queue; pub mod waker_registration; -- cgit v1.2.3 From 15d788b7fad0254ad3323962b8dd6753cf95796d Mon Sep 17 00:00:00 2001 From: Emil Fresk Date: Tue, 31 Jan 2023 15:55:14 +0100 Subject: Fix spelling error --- rtic-arbiter/src/lib.rs | 2 +- rtic-channel/src/lib.rs | 2 +- rtic-common/src/wait_queue.rs | 12 ++++++------ 3 files changed, 8 insertions(+), 8 deletions(-) (limited to 'rtic-common') diff --git a/rtic-arbiter/src/lib.rs b/rtic-arbiter/src/lib.rs index 519ce2c..09d1b2e 100644 --- a/rtic-arbiter/src/lib.rs +++ b/rtic-arbiter/src/lib.rs @@ -82,7 +82,7 @@ impl Arbiter { // which happens outside this `poll_fn`'s stack frame. let link = unsafe { link_ptr.get() }; if let Some(link) = link { - if link.is_poped() { + if link.is_popped() { return Poll::Ready(()); } } else { diff --git a/rtic-channel/src/lib.rs b/rtic-channel/src/lib.rs index 3cee78b..fef546b 100644 --- a/rtic-channel/src/lib.rs +++ b/rtic-channel/src/lib.rs @@ -267,7 +267,7 @@ impl<'a, T, const N: usize> Sender<'a, T, N> { // which happens outside this `poll_fn`'s stack frame. let link = unsafe { link_ptr.get() }; if let Some(link) = link { - if !link.is_poped() { + if !link.is_popped() { return None; } else { // Fall through to dequeue diff --git a/rtic-common/src/wait_queue.rs b/rtic-common/src/wait_queue.rs index ba8ff54..4ced6ab 100644 --- a/rtic-common/src/wait_queue.rs +++ b/rtic-common/src/wait_queue.rs @@ -58,7 +58,7 @@ impl LinkedList { // Clear the pointers in the node. head_ref.next.store(null_mut(), Self::R); head_ref.prev.store(null_mut(), Self::R); - head_ref.is_poped.store(true, Self::R); + head_ref.is_popped.store(true, Self::R); return Some(head_val); } @@ -102,7 +102,7 @@ pub struct Link { pub(crate) val: T, next: AtomicPtr>, prev: AtomicPtr>, - is_poped: AtomicBool, + is_popped: AtomicBool, _up: PhantomPinned, } @@ -115,14 +115,14 @@ impl Link { val, next: AtomicPtr::new(null_mut()), prev: AtomicPtr::new(null_mut()), - is_poped: AtomicBool::new(false), + is_popped: AtomicBool::new(false), _up: PhantomPinned, } } /// Return true if this link has been poped from the list. - pub fn is_poped(&self) -> bool { - self.is_poped.load(Self::R) + pub fn is_popped(&self) -> bool { + self.is_popped.load(Self::R) } /// Remove this link from a linked list. @@ -133,7 +133,7 @@ impl Link { let prev = self.prev.load(Self::R); let next = self.next.load(Self::R); - self.is_poped.store(true, Self::R); + self.is_popped.store(true, Self::R); match unsafe { (prev.as_ref(), next.as_ref()) } { (None, None) => { -- cgit v1.2.3 From fe77b4538d6cd506d1a18bdc9e17216dc61881db Mon Sep 17 00:00:00 2001 From: Henrik Tjäder Date: Wed, 1 Feb 2023 21:55:05 +0100 Subject: Add alpha.0 and required Cargo fields --- rtic-arbiter/Cargo.toml | 7 +++++-- rtic-channel/Cargo.toml | 7 +++++-- rtic-common/Cargo.toml | 5 ++++- rtic-monotonics/Cargo.toml | 7 +++++-- rtic-time/Cargo.toml | 7 +++++-- 5 files changed, 24 insertions(+), 9 deletions(-) (limited to 'rtic-common') diff --git a/rtic-arbiter/Cargo.toml b/rtic-arbiter/Cargo.toml index b1afaf4..52daa27 100644 --- a/rtic-arbiter/Cargo.toml +++ b/rtic-arbiter/Cargo.toml @@ -1,13 +1,16 @@ [package] name = "rtic-arbiter" -version = "1.0.0" +version = "1.0.0-alpha.0" edition = "2021" +categories = ["concurrency", "embedded", "no-std", "asynchronous"] +description = "rtic-arbiter lib TODO" +license = "MIT OR Apache-2.0" # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html [dependencies] critical-section = "1" -rtic-common = { version = "1.0.0", path = "../rtic-common" } +rtic-common = { version = "1.0.0-alpha.0", path = "../rtic-common" } [dev-dependencies] tokio = { version = "1", features = ["rt", "macros", "time"] } diff --git a/rtic-channel/Cargo.toml b/rtic-channel/Cargo.toml index a0955bc..a6f98e4 100644 --- a/rtic-channel/Cargo.toml +++ b/rtic-channel/Cargo.toml @@ -1,14 +1,17 @@ [package] name = "rtic-channel" -version = "1.0.0" +version = "1.0.0-alpha.0" edition = "2021" +categories = ["concurrency", "embedded", "no-std", "asynchronous"] +description = "rtic-channel lib TODO" +license = "MIT OR Apache-2.0" # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html [dependencies] heapless = "0.7" critical-section = "1" -rtic-common = { version = "1.0.0", path = "../rtic-common" } +rtic-common = { version = "1.0.0-alpha.0", path = "../rtic-common" } [dev-dependencies] tokio = { version = "1", features = ["rt", "macros", "time"] } diff --git a/rtic-common/Cargo.toml b/rtic-common/Cargo.toml index 258caae..35b0f72 100644 --- a/rtic-common/Cargo.toml +++ b/rtic-common/Cargo.toml @@ -1,7 +1,10 @@ [package] name = "rtic-common" -version = "1.0.0" +version = "1.0.0-alpha.0" edition = "2021" +categories = ["concurrency", "embedded", "no-std", "asynchronous"] +description = "rtic-common lib TODO" +license = "MIT OR Apache-2.0" # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html diff --git a/rtic-monotonics/Cargo.toml b/rtic-monotonics/Cargo.toml index 9d364c8..bb8ff6d 100644 --- a/rtic-monotonics/Cargo.toml +++ b/rtic-monotonics/Cargo.toml @@ -1,7 +1,10 @@ [package] name = "rtic-monotonics" -version = "0.1.0" +version = "1.0.0-alpha.0" edition = "2021" +categories = ["concurrency", "embedded", "no-std", "asynchronous"] +description = "rtic-monotonics lib TODO" +license = "MIT OR Apache-2.0" # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html @@ -9,5 +12,5 @@ edition = "2021" cortex-m = { version = "0.7.6" } embedded-hal-async = "0.2.0-alpha.0" fugit = { version = "0.3.6", features = ["defmt"] } -rtic-time = { version = "1.0.0", path = "../rtic-time" } +rtic-time = { version = "1.0.0-alpha.0", path = "../rtic-time" } atomic-polyfill = "1" diff --git a/rtic-time/Cargo.toml b/rtic-time/Cargo.toml index dbcf454..0ba7b11 100644 --- a/rtic-time/Cargo.toml +++ b/rtic-time/Cargo.toml @@ -1,11 +1,14 @@ [package] name = "rtic-time" -version = "1.0.0" +version = "1.0.0-alpha.0" edition = "2021" +categories = ["concurrency", "embedded", "no-std", "asynchronous"] +description = "rtic-time lib TODO" +license = "MIT OR Apache-2.0" # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html [dependencies] critical-section = "1" futures-util = { version = "0.3.25", default-features = false } -rtic-common = { version = "1.0.0", path = "../rtic-common" } +rtic-common = { version = "1.0.0-alpha.0", path = "../rtic-common" } -- cgit v1.2.3 From c2d2b1ba38dd291cfcd7e32f11d725db0ec1cf85 Mon Sep 17 00:00:00 2001 From: Henrik Tjäder Date: Wed, 1 Feb 2023 22:11:50 +0100 Subject: Add authors to each Cargo.toml Copy-paste the default one used for the project --- rtic-arbiter/Cargo.toml | 8 ++++++++ rtic-channel/Cargo.toml | 8 ++++++++ rtic-common/Cargo.toml | 8 ++++++++ rtic-monotonics/Cargo.toml | 8 ++++++++ rtic-time/Cargo.toml | 8 ++++++++ 5 files changed, 40 insertions(+) (limited to 'rtic-common') diff --git a/rtic-arbiter/Cargo.toml b/rtic-arbiter/Cargo.toml index 52daa27..d8b18c4 100644 --- a/rtic-arbiter/Cargo.toml +++ b/rtic-arbiter/Cargo.toml @@ -1,7 +1,15 @@ [package] name = "rtic-arbiter" version = "1.0.0-alpha.0" + edition = "2021" +authors = [ + "The Real-Time Interrupt-driven Concurrency developers", + "Emil Fresk ", + "Henrik Tjäder ", + "Jorge Aparicio ", + "Per Lindgren ", +] categories = ["concurrency", "embedded", "no-std", "asynchronous"] description = "rtic-arbiter lib TODO" license = "MIT OR Apache-2.0" diff --git a/rtic-channel/Cargo.toml b/rtic-channel/Cargo.toml index a6f98e4..900f972 100644 --- a/rtic-channel/Cargo.toml +++ b/rtic-channel/Cargo.toml @@ -1,7 +1,15 @@ [package] name = "rtic-channel" version = "1.0.0-alpha.0" + edition = "2021" +authors = [ + "The Real-Time Interrupt-driven Concurrency developers", + "Emil Fresk ", + "Henrik Tjäder ", + "Jorge Aparicio ", + "Per Lindgren ", +] categories = ["concurrency", "embedded", "no-std", "asynchronous"] description = "rtic-channel lib TODO" license = "MIT OR Apache-2.0" diff --git a/rtic-common/Cargo.toml b/rtic-common/Cargo.toml index 35b0f72..726090a 100644 --- a/rtic-common/Cargo.toml +++ b/rtic-common/Cargo.toml @@ -1,7 +1,15 @@ [package] name = "rtic-common" version = "1.0.0-alpha.0" + edition = "2021" +authors = [ + "The Real-Time Interrupt-driven Concurrency developers", + "Emil Fresk ", + "Henrik Tjäder ", + "Jorge Aparicio ", + "Per Lindgren ", +] categories = ["concurrency", "embedded", "no-std", "asynchronous"] description = "rtic-common lib TODO" license = "MIT OR Apache-2.0" diff --git a/rtic-monotonics/Cargo.toml b/rtic-monotonics/Cargo.toml index bb8ff6d..5e6586e 100644 --- a/rtic-monotonics/Cargo.toml +++ b/rtic-monotonics/Cargo.toml @@ -1,7 +1,15 @@ [package] name = "rtic-monotonics" version = "1.0.0-alpha.0" + edition = "2021" +authors = [ + "The Real-Time Interrupt-driven Concurrency developers", + "Emil Fresk ", + "Henrik Tjäder ", + "Jorge Aparicio ", + "Per Lindgren ", +] categories = ["concurrency", "embedded", "no-std", "asynchronous"] description = "rtic-monotonics lib TODO" license = "MIT OR Apache-2.0" diff --git a/rtic-time/Cargo.toml b/rtic-time/Cargo.toml index 0ba7b11..c7d13bb 100644 --- a/rtic-time/Cargo.toml +++ b/rtic-time/Cargo.toml @@ -1,7 +1,15 @@ [package] name = "rtic-time" version = "1.0.0-alpha.0" + edition = "2021" +authors = [ + "The Real-Time Interrupt-driven Concurrency developers", + "Emil Fresk ", + "Henrik Tjäder ", + "Jorge Aparicio ", + "Per Lindgren ", +] categories = ["concurrency", "embedded", "no-std", "asynchronous"] description = "rtic-time lib TODO" license = "MIT OR Apache-2.0" -- cgit v1.2.3 From 1cda61fbda205920517f7b63af90c97c38ff9af6 Mon Sep 17 00:00:00 2001 From: Emil Fresk Date: Sat, 18 Feb 2023 09:43:06 +0100 Subject: Make some linked list operations unsafe, and document their safety at usage --- rtic-arbiter/src/lib.rs | 14 +++++++++----- rtic-channel/src/lib.rs | 15 +++++++++------ rtic-common/src/lib.rs | 4 ++++ rtic-common/src/wait_queue.rs | 38 ++++++++++++++++++++------------------ rtic-time/src/lib.rs | 19 +++++++++++++------ rtic-time/src/linked_list.rs | 18 ++++++++++++------ 6 files changed, 67 insertions(+), 41 deletions(-) (limited to 'rtic-common') diff --git a/rtic-arbiter/src/lib.rs b/rtic-arbiter/src/lib.rs index 09d1b2e..c70fbf5 100644 --- a/rtic-arbiter/src/lib.rs +++ b/rtic-arbiter/src/lib.rs @@ -54,7 +54,8 @@ impl Arbiter { pub async fn access(&self) -> ExclusiveAccess<'_, T> { let mut link_ptr: Option> = None; - // Make this future `Drop`-safe, also shadow the original definition so we can't abuse it. + // Make this future `Drop`-safe. + // SAFETY(link_ptr): Shadow the original definition of `link_ptr` so we can't abuse it. let mut link_ptr = LinkPtr(&mut link_ptr as *mut Option>); let mut link_ptr2 = link_ptr.clone(); @@ -89,10 +90,13 @@ impl Arbiter { // Place the link in the wait queue on first run. let link_ref = link.insert(Link::new(cx.waker().clone())); - // SAFETY: The address to the link is stable as it is hidden behind - // `link_ptr`, and `link_ptr` shadows the original making it unmovable. - self.wait_queue - .push(unsafe { Pin::new_unchecked(link_ref) }); + // SAFETY(new_unchecked): The address to the link is stable as it is defined + // outside this stack frame. + // SAFETY(push): `link_ref` lifetime comes from `link_ptr` that is shadowed, + // and we make sure in `dropper` that the link is removed from the queue + // before dropping `link_ptr` AND `dropper` makes sure that the shadowed + // `link_ptr` lives until the end of the stack frame. + unsafe { self.wait_queue.push(Pin::new_unchecked(link_ref)) }; } Poll::Pending diff --git a/rtic-channel/src/lib.rs b/rtic-channel/src/lib.rs index 47e4a77..a4e4935 100644 --- a/rtic-channel/src/lib.rs +++ b/rtic-channel/src/lib.rs @@ -240,7 +240,8 @@ impl<'a, T, const N: usize> Sender<'a, T, N> { pub async fn send(&mut self, val: T) -> Result<(), NoReceiver> { let mut link_ptr: Option> = None; - // Make this future `Drop`-safe, also shadow the original definition so we can't abuse it. + // Make this future `Drop`-safe. + // SAFETY(link_ptr): Shadow the original definition of `link_ptr` so we can't abuse it. let mut link_ptr = LinkPtr(&mut link_ptr as *mut Option>); let mut link_ptr2 = link_ptr.clone(); @@ -276,11 +277,13 @@ impl<'a, T, const N: usize> Sender<'a, T, N> { // Place the link in the wait queue on first run. let link_ref = link.insert(Link::new(cx.waker().clone())); - // SAFETY: The address to the link is stable as it is hidden behind - // `link_ptr`, and `link_ptr` shadows the original making it unmovable. - self.0 - .wait_queue - .push(unsafe { Pin::new_unchecked(link_ref) }); + // SAFETY(new_unchecked): The address to the link is stable as it is defined + // outside this stack frame. + // SAFETY(push): `link_ref` lifetime comes from `link_ptr` that is shadowed, + // and we make sure in `dropper` that the link is removed from the queue + // before dropping `link_ptr` AND `dropper` makes sure that the shadowed + // `link_ptr` lives until the end of the stack frame. + unsafe { self.0.wait_queue.push(Pin::new_unchecked(link_ref)) }; return None; } diff --git a/rtic-common/src/lib.rs b/rtic-common/src/lib.rs index b8b5e0d..03d0306 100644 --- a/rtic-common/src/lib.rs +++ b/rtic-common/src/lib.rs @@ -4,6 +4,10 @@ #![deny(missing_docs)] //deny_warnings_placeholder_for_ci +#[cfg(test)] +#[macro_use] +extern crate std; + pub mod dropper; pub mod wait_queue; pub mod waker_registration; diff --git a/rtic-common/src/wait_queue.rs b/rtic-common/src/wait_queue.rs index 4ced6ab..7387a98 100644 --- a/rtic-common/src/wait_queue.rs +++ b/rtic-common/src/wait_queue.rs @@ -68,7 +68,9 @@ impl LinkedList { } /// Put an element at the back of the queue. - pub fn push(&self, link: Pin<&mut Link>) { + /// + /// SAFETY: The link must live until it is removed from the queue. + pub unsafe fn push(&self, link: Pin<&Link>) { cs::with(|_| { // Make sure all previous writes are visible core::sync::atomic::fence(Ordering::SeqCst); @@ -76,17 +78,17 @@ impl LinkedList { let tail = self.tail.load(Self::R); // SAFETY: This datastructure does not move the underlying value. - let link = unsafe { link.get_unchecked_mut() }; + let link = link.get_ref(); if let Some(tail_ref) = unsafe { tail.as_ref() } { // Queue is not empty link.prev.store(tail, Self::R); - self.tail.store(link, Self::R); - tail_ref.next.store(link, Self::R); + self.tail.store(link as *const _ as *mut _, Self::R); + tail_ref.next.store(link as *const _ as *mut _, Self::R); } else { // Queue is empty - self.tail.store(link, Self::R); - self.head.store(link, Self::R); + self.tail.store(link as *const _ as *mut _, Self::R); + self.head.store(link as *const _ as *mut _, Self::R); } }); } @@ -126,7 +128,7 @@ impl Link { } /// Remove this link from a linked list. - pub fn remove_from_list(&mut self, list: &LinkedList) { + pub fn remove_from_list(&self, list: &LinkedList) { cs::with(|_| { // Make sure all previous writes are visible core::sync::atomic::fence(Ordering::SeqCst); @@ -230,17 +232,17 @@ mod tests { fn linked_list() { let wq = LinkedList::::new(); - let mut i1 = Link::new(10); - let mut i2 = Link::new(11); - let mut i3 = Link::new(12); - let mut i4 = Link::new(13); - let mut i5 = Link::new(14); - - wq.push(unsafe { Pin::new_unchecked(&mut i1) }); - wq.push(unsafe { Pin::new_unchecked(&mut i2) }); - wq.push(unsafe { Pin::new_unchecked(&mut i3) }); - wq.push(unsafe { Pin::new_unchecked(&mut i4) }); - wq.push(unsafe { Pin::new_unchecked(&mut i5) }); + let i1 = Link::new(10); + let i2 = Link::new(11); + let i3 = Link::new(12); + let i4 = Link::new(13); + let i5 = Link::new(14); + + unsafe { wq.push(Pin::new_unchecked(&i1)) }; + unsafe { wq.push(Pin::new_unchecked(&i2)) }; + unsafe { wq.push(Pin::new_unchecked(&i3)) }; + unsafe { wq.push(Pin::new_unchecked(&i4)) }; + unsafe { wq.push(Pin::new_unchecked(&i5)) }; wq.print(); diff --git a/rtic-time/src/lib.rs b/rtic-time/src/lib.rs index 5e4457c..3126e6b 100644 --- a/rtic-time/src/lib.rs +++ b/rtic-time/src/lib.rs @@ -208,7 +208,8 @@ impl TimerQueue { let mut link_ptr: Option>> = None; - // Make this future `Drop`-safe, also shadow the original definition so we can't abuse it. + // Make this future `Drop`-safe + // SAFETY(link_ptr): Shadow the original definition of `link_ptr` so we can't abuse it. let mut link_ptr = LinkPtr(&mut link_ptr as *mut Option>>); let mut link_ptr2 = link_ptr.clone(); @@ -226,18 +227,24 @@ impl TimerQueue { } // SAFETY: This pointer is only dereferenced here and on drop of the future - // which happens outside this `poll_fn`'s stack frame. + // which happens outside this `poll_fn`'s stack frame, so this mutable access cannot + // happen at the same time as `dropper` runs. let link = unsafe { link_ptr2.get() }; if link.is_none() { - let mut link_ref = link.insert(Link::new(WaitingWaker { + let link_ref = link.insert(Link::new(WaitingWaker { waker: cx.waker().clone(), release_at: instant, was_poped: AtomicBool::new(false), })); - // SAFETY: The address to the link is stable as it is defined outside this stack - // frame. - let (was_empty, addr) = queue.insert(unsafe { Pin::new_unchecked(&mut link_ref) }); + // SAFETY(new_unchecked): The address to the link is stable as it is defined + //outside this stack frame. + // SAFETY(insert): `link_ref` lifetime comes from `link_ptr` that is shadowed, and + // we make sure in `dropper` that the link is removed from the queue before + // dropping `link_ptr` AND `dropper` makes sure that the shadowed `link_ptr` lives + // until the end of the stack frame. + let (was_empty, addr) = unsafe { queue.insert(Pin::new_unchecked(&link_ref)) }; + marker.store(addr, Ordering::Relaxed); if was_empty { diff --git a/rtic-time/src/linked_list.rs b/rtic-time/src/linked_list.rs index de5ea2a..d4256c9 100644 --- a/rtic-time/src/linked_list.rs +++ b/rtic-time/src/linked_list.rs @@ -93,10 +93,12 @@ impl LinkedList { /// Insert a new link into the linked list. /// The return is (was_empty, address), where the address of the link is for use with `delete`. - pub fn insert(&self, val: Pin<&mut Link>) -> (bool, usize) { + /// + /// SAFETY: The pinned link must live until it is removed from this list. + pub unsafe fn insert(&self, val: Pin<&Link>) -> (bool, usize) { cs::with(|_| { // SAFETY: This datastructure does not move the underlying value. - let val = unsafe { val.get_unchecked_mut() }; + let val = val.get_ref(); let addr = val as *const _ as usize; // Make sure all previous writes are visible @@ -111,7 +113,8 @@ impl LinkedList { let head_ref = if let Some(head_ref) = unsafe { head.as_ref() } { head_ref } else { - self.head.store(val, Ordering::Relaxed); + self.head + .store(val as *const _ as *mut _, Ordering::Relaxed); return (true, addr); }; @@ -121,7 +124,8 @@ impl LinkedList { val.next.store(head, Ordering::Relaxed); // `val` is now first in the queue - self.head.store(val, Ordering::Relaxed); + self.head + .store(val as *const _ as *mut _, Ordering::Relaxed); return (false, addr); } @@ -139,7 +143,8 @@ impl LinkedList { val.next.store(next, Ordering::Relaxed); // Insert `val` - curr.next.store(val, Ordering::Relaxed); + curr.next + .store(val as *const _ as *mut _, Ordering::Relaxed); return (false, addr); } @@ -150,7 +155,8 @@ impl LinkedList { } // No next, write link to last position in list - curr.next.store(val, Ordering::Relaxed); + curr.next + .store(val as *const _ as *mut _, Ordering::Relaxed); (false, addr) }) -- cgit v1.2.3 From 5dc2c1d351d75d150d671994b1c67b2c0f9d16a0 Mon Sep 17 00:00:00 2001 From: Henrik Tjäder Date: Sat, 4 Mar 2023 01:06:46 +0100 Subject: rtic-common: Fix safety section formatting --- rtic-common/src/wait_queue.rs | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'rtic-common') diff --git a/rtic-common/src/wait_queue.rs b/rtic-common/src/wait_queue.rs index 7387a98..b1aa775 100644 --- a/rtic-common/src/wait_queue.rs +++ b/rtic-common/src/wait_queue.rs @@ -69,7 +69,9 @@ impl LinkedList { /// Put an element at the back of the queue. /// - /// SAFETY: The link must live until it is removed from the queue. + /// # Safety + /// + /// The link must live until it is removed from the queue. pub unsafe fn push(&self, link: Pin<&Link>) { cs::with(|_| { // Make sure all previous writes are visible -- cgit v1.2.3