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/src/wait_queue.rs | 271 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 271 insertions(+) create mode 100644 rtic-common/src/wait_queue.rs (limited to 'rtic-common/src/wait_queue.rs') 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(); + } +} -- 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-common/src/wait_queue.rs | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) (limited to 'rtic-common/src/wait_queue.rs') 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 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-common/src/wait_queue.rs | 38 ++++++++++++++++++++------------------ 1 file changed, 20 insertions(+), 18 deletions(-) (limited to 'rtic-common/src/wait_queue.rs') 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(); -- cgit v1.2.3 From 5dc2c1d351d75d150d671994b1c67b2c0f9d16a0 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Henrik=20Tj=C3=A4der?= 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/src/wait_queue.rs') 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