From 7bd236853ef5ae705328c8fdc492cf60fc6887c1 Mon Sep 17 00:00:00 2001 From: Mica White Date: Wed, 13 Mar 2024 22:44:46 -0400 Subject: Lockable overhaul --- examples/dining_philosophers.rs | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'examples/dining_philosophers.rs') diff --git a/examples/dining_philosophers.rs b/examples/dining_philosophers.rs index 35aa330..34efb0e 100644 --- a/examples/dining_philosophers.rs +++ b/examples/dining_philosophers.rs @@ -1,6 +1,6 @@ use std::{thread, time::Duration}; -use happylock::{LockCollection, Mutex, ThreadKey}; +use happylock::{Mutex, RefLockCollection, ThreadKey}; static PHILOSOPHERS: [Philosopher; 5] = [ Philosopher { @@ -50,8 +50,8 @@ impl Philosopher { thread::sleep(Duration::from_secs(1)); // safety: no philosopher asks for the same fork twice - let forks = - unsafe { LockCollection::new_unchecked([&FORKS[self.left], &FORKS[self.right]]) }; + let forks = [&FORKS[self.left], &FORKS[self.right]]; + let forks = unsafe { RefLockCollection::new_unchecked(&forks) }; let forks = forks.lock(key); println!("{} is eating...", self.name); thread::sleep(Duration::from_secs(1)); -- cgit v1.2.3 From ad76d43dc28b8802d64eb7ddcd9e02d3d12ac89a Mon Sep 17 00:00:00 2001 From: Mica White Date: Thu, 14 Mar 2024 17:21:51 -0400 Subject: Implement sequenced collections --- examples/dining_philosophers.rs | 2 +- examples/double_mutex.rs | 2 +- examples/list.rs | 2 +- src/collection.rs | 18 +-- src/collection/boxed_collection.rs | 60 +++++++++ src/collection/collection.rs | 244 ------------------------------------ src/collection/owned_collection.rs | 68 ++++++++++ src/collection/ref_collection.rs | 245 +++++++++++++++++++++++++++++++++++++ src/lib.rs | 1 - 9 files changed, 381 insertions(+), 261 deletions(-) create mode 100644 src/collection/boxed_collection.rs delete mode 100644 src/collection/collection.rs create mode 100644 src/collection/owned_collection.rs create mode 100644 src/collection/ref_collection.rs (limited to 'examples/dining_philosophers.rs') diff --git a/examples/dining_philosophers.rs b/examples/dining_philosophers.rs index 34efb0e..2f2fa0d 100644 --- a/examples/dining_philosophers.rs +++ b/examples/dining_philosophers.rs @@ -1,6 +1,6 @@ use std::{thread, time::Duration}; -use happylock::{Mutex, RefLockCollection, ThreadKey}; +use happylock::{collection::RefLockCollection, Mutex, ThreadKey}; static PHILOSOPHERS: [Philosopher; 5] = [ Philosopher { diff --git a/examples/double_mutex.rs b/examples/double_mutex.rs index cd627c4..e2b08df 100644 --- a/examples/double_mutex.rs +++ b/examples/double_mutex.rs @@ -1,6 +1,6 @@ use std::thread; -use happylock::{Mutex, RefLockCollection, ThreadKey}; +use happylock::{collection::RefLockCollection, Mutex, ThreadKey}; const N: usize = 10; diff --git a/examples/list.rs b/examples/list.rs index cf344e7..dda468a 100644 --- a/examples/list.rs +++ b/examples/list.rs @@ -1,6 +1,6 @@ use std::thread; -use happylock::{Mutex, RefLockCollection, ThreadKey}; +use happylock::{collection::RefLockCollection, Mutex, ThreadKey}; const N: usize = 10; diff --git a/src/collection.rs b/src/collection.rs index 1c276a6..93adf16 100644 --- a/src/collection.rs +++ b/src/collection.rs @@ -1,13 +1,14 @@ -use std::marker::{PhantomData, PhantomPinned}; -use std::ptr::NonNull; +use std::{marker::PhantomData, ptr::NonNull}; use crate::{ key::Keyable, lockable::{Lock, Lockable}, }; -mod collection; +mod boxed_collection; mod guard; +mod owned_collection; +mod ref_collection; pub struct OwnedLockCollection { data: L, @@ -22,16 +23,7 @@ pub struct RefLockCollection<'a, L> { data: &'a L, } -pub struct BoxedLockCollection(RefLockCollection<'static, L>); - -pub struct PinnedLockCollection { - _unpin: PhantomPinned, - data: L, - locks: Vec>, -} - -unsafe impl Send for PinnedLockCollection {} -unsafe impl Sync for PinnedLockCollection {} +pub struct BoxedLockCollection<'a, L>(RefLockCollection<'a, L>); /// A RAII guard for a generic [`Lockable`] type. pub struct LockGuard<'a, 'key: 'a, L: Lockable<'a>, Key: Keyable + 'key> { diff --git a/src/collection/boxed_collection.rs b/src/collection/boxed_collection.rs new file mode 100644 index 0000000..bcb941b --- /dev/null +++ b/src/collection/boxed_collection.rs @@ -0,0 +1,60 @@ +use std::ops::{Deref, DerefMut}; + +use crate::{Lockable, OwnedLockable}; + +use super::{BoxedLockCollection, RefLockCollection}; + +impl<'a, L> Deref for BoxedLockCollection<'a, L> { + type Target = RefLockCollection<'a, L>; + + fn deref(&self) -> &Self::Target { + &self.0 + } +} + +impl<'a, L> DerefMut for BoxedLockCollection<'a, L> { + fn deref_mut(&mut self) -> &mut Self::Target { + &mut self.0 + } +} + +impl<'a, L> Drop for BoxedLockCollection<'a, L> { + fn drop(&mut self) { + // this was created with Box::new + let boxed = unsafe { Box::from_raw((self.0.data as *const L).cast_mut()) }; + drop(boxed); + } +} + +impl<'a, L: OwnedLockable<'a> + 'a> BoxedLockCollection<'a, L> { + #[must_use] + pub fn new(data: L) -> Self { + let boxed = Box::leak(Box::new(data)); + Self(RefLockCollection::new(boxed)) + } +} + +impl<'a, L: OwnedLockable<'a> + 'a> BoxedLockCollection<'a, &'a L> { + #[must_use] + pub fn new_ref(data: &'a L) -> Self { + let boxed = Box::leak(Box::new(data)); + + // this is a reference to an OwnedLockable, which can't possibly + // contain inner duplicates + Self(unsafe { RefLockCollection::new_unchecked(boxed) }) + } +} + +impl<'a, L: Lockable<'a> + 'a> BoxedLockCollection<'a, L> { + #[must_use] + pub unsafe fn new_unchecked(data: L) -> Self { + let boxed = Box::leak(Box::new(data)); + Self(RefLockCollection::new_unchecked(boxed)) + } + + #[must_use] + pub fn try_new(data: L) -> Option { + let boxed = Box::leak(Box::new(data)); + RefLockCollection::try_new(boxed).map(Self) + } +} diff --git a/src/collection/collection.rs b/src/collection/collection.rs deleted file mode 100644 index a8d25a5..0000000 --- a/src/collection/collection.rs +++ /dev/null @@ -1,244 +0,0 @@ -use std::marker::PhantomData; - -use crate::{key::Keyable, lockable::Lock, Lockable, OwnedLockable}; - -use super::{LockGuard, RefLockCollection}; - -fn get_locks<'a, L: Lockable<'a> + 'a>(data: &'a L) -> Vec<&'a dyn Lock> { - let mut locks = Vec::new(); - data.get_ptrs(&mut locks); - locks.sort_by_key(|lock| std::ptr::from_ref(*lock)); - locks -} - -/// returns `true` if the sorted list contains a duplicate -#[must_use] -fn contains_duplicates(l: &[&dyn Lock]) -> bool { - l.windows(2).any(|window| { - std::ptr::addr_eq(std::ptr::from_ref(window[0]), std::ptr::from_ref(window[1])) - }) -} - -impl<'a, L: Lockable<'a>> AsRef for RefLockCollection<'a, L> { - fn as_ref(&self) -> &L { - self.data - } -} - -impl<'a, L: Lockable<'a>> AsRef for RefLockCollection<'a, L> { - fn as_ref(&self) -> &Self { - self - } -} - -impl<'a, L: Lockable<'a>> AsMut for RefLockCollection<'a, L> { - fn as_mut(&mut self) -> &mut Self { - self - } -} - -impl<'a, L> IntoIterator for &'a RefLockCollection<'a, L> -where - &'a L: IntoIterator, -{ - type Item = <&'a L as IntoIterator>::Item; - type IntoIter = <&'a L as IntoIterator>::IntoIter; - - fn into_iter(self) -> Self::IntoIter { - self.data.into_iter() - } -} - -impl<'a, L: OwnedLockable<'a> + 'a> RefLockCollection<'a, L> { - /// Creates a new collection of owned locks. - /// - /// Because the locks are owned, there's no need to do any checks for - /// duplicate values. - /// - /// # Examples - /// - /// ``` - /// use happylock::{LockCollection, Mutex}; - /// - /// let data = (Mutex::new(0), Mutex::new("")); - /// let lock = LockCollection::new(&data); - /// ``` - #[must_use] - pub fn new(data: &'a L) -> RefLockCollection { - RefLockCollection { - locks: get_locks(data), - data, - } - } -} - -impl<'a, L: Lockable<'a>> RefLockCollection<'a, L> { - /// Creates a new collections of locks. - /// - /// # Safety - /// - /// This results in undefined behavior if any locks are presented twice - /// within this collection. - /// - /// # Examples - /// - /// ``` - /// use happylock::{LockCollection, Mutex}; - /// - /// let data1 = Mutex::new(0); - /// let data2 = Mutex::new(""); - /// - /// // safety: data1 and data2 refer to distinct mutexes - /// let lock = unsafe { LockCollection::new_unchecked((&data1, &data2)) }; - /// ``` - #[must_use] - pub unsafe fn new_unchecked(data: &'a L) -> Self { - Self { - data, - locks: get_locks(data), - } - } - - /// Creates a new collection of locks. - /// - /// This returns `None` if any locks are found twice in the given - /// collection. - /// - /// # Examples - /// - /// ``` - /// use happylock::{LockCollection, Mutex}; - /// - /// let data1 = Mutex::new(0); - /// let data2 = Mutex::new(""); - /// - /// // data1 and data2 refer to distinct mutexes, so this won't panic - /// let lock = LockCollection::try_new((&data1, &data2)).unwrap(); - /// ``` - #[must_use] - pub fn try_new(data: &'a L) -> Option { - let locks = get_locks(data); - if contains_duplicates(&locks) { - return None; - } - - Some(Self { locks, data }) - } - - /// Locks the collection - /// - /// This function returns a guard that can be used to access the underlying - /// data. When the guard is dropped, the locks in the collection are also - /// dropped. - /// - /// # Examples - /// - /// ``` - /// use happylock::{LockCollection, Mutex, ThreadKey}; - /// - /// let key = ThreadKey::get().unwrap(); - /// let lock = LockCollection::new((Mutex::new(0), Mutex::new(""))); - /// - /// let mut guard = lock.lock(key); - /// *guard.0 += 1; - /// *guard.1 = "1"; - /// ``` - pub fn lock<'key: 'a, Key: Keyable + 'key>(&'a self, key: Key) -> LockGuard<'a, 'key, L, Key> { - for lock in &self.locks { - // safety: we have the thread key - unsafe { lock.lock() }; - } - - LockGuard { - // safety: we've already acquired the lock - guard: unsafe { self.data.guard() }, - key, - _phantom: PhantomData, - } - } - - /// Attempts to lock the without blocking. - /// - /// If successful, this method returns a guard that can be used to access - /// the data, and unlocks the data when it is dropped. Otherwise, `None` is - /// returned. - /// - /// # Examples - /// - /// ``` - /// use happylock::{LockCollection, Mutex, ThreadKey}; - /// - /// let key = ThreadKey::get().unwrap(); - /// let lock = LockCollection::new((Mutex::new(0), Mutex::new(""))); - /// - /// match lock.try_lock(key) { - /// Some(mut guard) => { - /// *guard.0 += 1; - /// *guard.1 = "1"; - /// }, - /// None => unreachable!(), - /// }; - /// - /// ``` - pub fn try_lock<'key: 'a, Key: Keyable + 'key>( - &'a self, - key: Key, - ) -> Option> { - let guard = unsafe { - for (i, lock) in self.locks.iter().enumerate() { - // safety: we have the thread key - let success = lock.try_lock(); - - if !success { - for lock in &self.locks[0..i] { - // safety: this lock was already acquired - lock.unlock(); - } - return None; - } - } - - // safety: we've acquired the locks - self.data.guard() - }; - - Some(LockGuard { - guard, - key, - _phantom: PhantomData, - }) - } - - /// Unlocks the underlying lockable data type, returning the key that's - /// associated with it. - /// - /// # Examples - /// - /// ``` - /// use happylock::{LockCollection, Mutex, ThreadKey}; - /// - /// let key = ThreadKey::get().unwrap(); - /// let lock = LockCollection::new((Mutex::new(0), Mutex::new(""))); - /// - /// let mut guard = lock.lock(key); - /// *guard.0 += 1; - /// *guard.1 = "1"; - /// let key = LockCollection::unlock(guard); - /// ``` - #[allow(clippy::missing_const_for_fn)] - pub fn unlock<'key: 'a, Key: Keyable + 'key>(guard: LockGuard<'a, 'key, L, Key>) -> Key { - drop(guard.guard); - guard.key - } -} - -impl<'a, L: 'a> RefLockCollection<'a, L> -where - &'a L: IntoIterator, -{ - /// Returns an iterator over references to each value in the collection. - #[must_use] - pub fn iter(&'a self) -> <&'a L as IntoIterator>::IntoIter { - self.into_iter() - } -} diff --git a/src/collection/owned_collection.rs b/src/collection/owned_collection.rs new file mode 100644 index 0000000..dbc9a45 --- /dev/null +++ b/src/collection/owned_collection.rs @@ -0,0 +1,68 @@ +use std::marker::PhantomData; + +use crate::{lockable::Lock, Keyable, Lockable, OwnedLockable}; + +use super::{LockGuard, OwnedLockCollection}; + +fn get_locks<'a, L: Lockable<'a> + 'a>(data: &'a L) -> Vec<&'a dyn Lock> { + let mut locks = Vec::new(); + data.get_ptrs(&mut locks); + locks +} + +impl<'a, L: OwnedLockable<'a>> OwnedLockCollection { + #[must_use] + pub const fn new(data: L) -> Self { + Self { data } + } + + pub fn lock<'s: 'a, 'key, Key: Keyable + 'key>( + &'s self, + key: Key, + ) -> LockGuard<'a, 'key, L, Key> { + let locks = get_locks(&self.data); + for lock in locks { + // safety: we have the thread key, and these locks happen in a + // predetermined order + unsafe { lock.lock() }; + } + + // safety: we've locked all of this already + let guard = unsafe { self.data.guard() }; + LockGuard { + guard, + key, + _phantom: PhantomData, + } + } + + pub fn try_lock<'key: 'a, Key: Keyable + 'key>( + &'a self, + key: Key, + ) -> Option> { + let locks = get_locks(&self.data); + let guard = unsafe { + for (i, lock) in locks.iter().enumerate() { + // safety: we have the thread key + let success = lock.try_lock(); + + if !success { + for lock in &locks[0..i] { + // safety: this lock was already acquired + lock.unlock(); + } + return None; + } + } + + // safety: we've acquired the locks + self.data.guard() + }; + + Some(LockGuard { + guard, + key, + _phantom: PhantomData, + }) + } +} diff --git a/src/collection/ref_collection.rs b/src/collection/ref_collection.rs new file mode 100644 index 0000000..3e4d5f8 --- /dev/null +++ b/src/collection/ref_collection.rs @@ -0,0 +1,245 @@ +use std::marker::PhantomData; + +use crate::{key::Keyable, lockable::Lock, Lockable, OwnedLockable}; + +use super::{LockGuard, RefLockCollection}; + +#[must_use] +fn get_locks<'a, L: Lockable<'a> + 'a>(data: &'a L) -> Vec<&'a dyn Lock> { + let mut locks = Vec::new(); + data.get_ptrs(&mut locks); + locks.sort_by_key(|lock| std::ptr::from_ref(*lock)); + locks +} + +/// returns `true` if the sorted list contains a duplicate +#[must_use] +fn contains_duplicates(l: &[&dyn Lock]) -> bool { + l.windows(2).any(|window| { + std::ptr::addr_eq(std::ptr::from_ref(window[0]), std::ptr::from_ref(window[1])) + }) +} + +impl<'a, L: Lockable<'a>> AsRef for RefLockCollection<'a, L> { + fn as_ref(&self) -> &L { + self.data + } +} + +impl<'a, L: Lockable<'a>> AsRef for RefLockCollection<'a, L> { + fn as_ref(&self) -> &Self { + self + } +} + +impl<'a, L: Lockable<'a>> AsMut for RefLockCollection<'a, L> { + fn as_mut(&mut self) -> &mut Self { + self + } +} + +impl<'a, L> IntoIterator for &'a RefLockCollection<'a, L> +where + &'a L: IntoIterator, +{ + type Item = <&'a L as IntoIterator>::Item; + type IntoIter = <&'a L as IntoIterator>::IntoIter; + + fn into_iter(self) -> Self::IntoIter { + self.data.into_iter() + } +} + +impl<'a, L: OwnedLockable<'a> + 'a> RefLockCollection<'a, L> { + /// Creates a new collection of owned locks. + /// + /// Because the locks are owned, there's no need to do any checks for + /// duplicate values. + /// + /// # Examples + /// + /// ``` + /// use happylock::{LockCollection, Mutex}; + /// + /// let data = (Mutex::new(0), Mutex::new("")); + /// let lock = LockCollection::new(&data); + /// ``` + #[must_use] + pub fn new(data: &'a L) -> RefLockCollection { + RefLockCollection { + locks: get_locks(data), + data, + } + } +} + +impl<'a, L: Lockable<'a>> RefLockCollection<'a, L> { + /// Creates a new collections of locks. + /// + /// # Safety + /// + /// This results in undefined behavior if any locks are presented twice + /// within this collection. + /// + /// # Examples + /// + /// ``` + /// use happylock::{LockCollection, Mutex}; + /// + /// let data1 = Mutex::new(0); + /// let data2 = Mutex::new(""); + /// + /// // safety: data1 and data2 refer to distinct mutexes + /// let lock = unsafe { LockCollection::new_unchecked((&data1, &data2)) }; + /// ``` + #[must_use] + pub unsafe fn new_unchecked(data: &'a L) -> Self { + Self { + data, + locks: get_locks(data), + } + } + + /// Creates a new collection of locks. + /// + /// This returns `None` if any locks are found twice in the given + /// collection. + /// + /// # Examples + /// + /// ``` + /// use happylock::{LockCollection, Mutex}; + /// + /// let data1 = Mutex::new(0); + /// let data2 = Mutex::new(""); + /// + /// // data1 and data2 refer to distinct mutexes, so this won't panic + /// let lock = LockCollection::try_new((&data1, &data2)).unwrap(); + /// ``` + #[must_use] + pub fn try_new(data: &'a L) -> Option { + let locks = get_locks(data); + if contains_duplicates(&locks) { + return None; + } + + Some(Self { locks, data }) + } + + /// Locks the collection + /// + /// This function returns a guard that can be used to access the underlying + /// data. When the guard is dropped, the locks in the collection are also + /// dropped. + /// + /// # Examples + /// + /// ``` + /// use happylock::{LockCollection, Mutex, ThreadKey}; + /// + /// let key = ThreadKey::get().unwrap(); + /// let lock = LockCollection::new((Mutex::new(0), Mutex::new(""))); + /// + /// let mut guard = lock.lock(key); + /// *guard.0 += 1; + /// *guard.1 = "1"; + /// ``` + pub fn lock<'key: 'a, Key: Keyable + 'key>(&'a self, key: Key) -> LockGuard<'a, 'key, L, Key> { + for lock in &self.locks { + // safety: we have the thread key + unsafe { lock.lock() }; + } + + LockGuard { + // safety: we've already acquired the lock + guard: unsafe { self.data.guard() }, + key, + _phantom: PhantomData, + } + } + + /// Attempts to lock the without blocking. + /// + /// If successful, this method returns a guard that can be used to access + /// the data, and unlocks the data when it is dropped. Otherwise, `None` is + /// returned. + /// + /// # Examples + /// + /// ``` + /// use happylock::{LockCollection, Mutex, ThreadKey}; + /// + /// let key = ThreadKey::get().unwrap(); + /// let lock = LockCollection::new((Mutex::new(0), Mutex::new(""))); + /// + /// match lock.try_lock(key) { + /// Some(mut guard) => { + /// *guard.0 += 1; + /// *guard.1 = "1"; + /// }, + /// None => unreachable!(), + /// }; + /// + /// ``` + pub fn try_lock<'key: 'a, Key: Keyable + 'key>( + &'a self, + key: Key, + ) -> Option> { + let guard = unsafe { + for (i, lock) in self.locks.iter().enumerate() { + // safety: we have the thread key + let success = lock.try_lock(); + + if !success { + for lock in &self.locks[0..i] { + // safety: this lock was already acquired + lock.unlock(); + } + return None; + } + } + + // safety: we've acquired the locks + self.data.guard() + }; + + Some(LockGuard { + guard, + key, + _phantom: PhantomData, + }) + } + + /// Unlocks the underlying lockable data type, returning the key that's + /// associated with it. + /// + /// # Examples + /// + /// ``` + /// use happylock::{LockCollection, Mutex, ThreadKey}; + /// + /// let key = ThreadKey::get().unwrap(); + /// let lock = LockCollection::new((Mutex::new(0), Mutex::new(""))); + /// + /// let mut guard = lock.lock(key); + /// *guard.0 += 1; + /// *guard.1 = "1"; + /// let key = LockCollection::unlock(guard); + /// ``` + #[allow(clippy::missing_const_for_fn)] + pub fn unlock<'key: 'a, Key: Keyable + 'key>(guard: LockGuard<'a, 'key, L, Key>) -> Key { + drop(guard.guard); + guard.key + } +} + +impl<'a, L: 'a> RefLockCollection<'a, L> +where + &'a L: IntoIterator, +{ + /// Returns an iterator over references to each value in the collection. + #[must_use] + pub fn iter(&'a self) -> <&'a L as IntoIterator>::IntoIter { + self.into_iter() + } +} diff --git a/src/lib.rs b/src/lib.rs index 64813af..92b31a0 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -113,7 +113,6 @@ pub mod collection; pub mod mutex; pub mod rwlock; -pub use collection::RefLockCollection; pub use key::{Keyable, ThreadKey}; pub use lockable::{Lockable, OwnedLockable}; -- cgit v1.2.3 From cf49f2900fe3c7abd1bbadacfdc745d6b5bbc235 Mon Sep 17 00:00:00 2001 From: Botahamec Date: Tue, 21 May 2024 14:48:46 -0400 Subject: Fix the Dining Philosophers Problem --- examples/dining_philosophers.rs | 8 ++++++-- src/lockable.rs | 16 ++++------------ src/rwlock/read_lock.rs | 4 ++-- src/rwlock/write_lock.rs | 8 ++++---- 4 files changed, 16 insertions(+), 20 deletions(-) (limited to 'examples/dining_philosophers.rs') diff --git a/examples/dining_philosophers.rs b/examples/dining_philosophers.rs index 2f2fa0d..1340564 100644 --- a/examples/dining_philosophers.rs +++ b/examples/dining_philosophers.rs @@ -61,9 +61,13 @@ impl Philosopher { } fn main() { - let handles = PHILOSOPHERS + let handles: Vec<_> = PHILOSOPHERS .iter() - .map(|philosopher| thread::spawn(move || philosopher.cycle())); + .map(|philosopher| thread::spawn(move || philosopher.cycle())) + // The `collect` is absolutely necessary, because we're using lazy + // iterators. If `collect` isn't used, then the thread won't spawn + // until we try to join on it. + .collect(); for handle in handles { _ = handle.join(); diff --git a/src/lockable.rs b/src/lockable.rs index a5646e1..9b3a4e4 100644 --- a/src/lockable.rs +++ b/src/lockable.rs @@ -124,7 +124,7 @@ unsafe impl OwnedLockable for Mutex {} unsafe impl OwnedLockable for RwLock {} -unsafe impl Lockable for ReadLock { +unsafe impl<'l, T: Send, R: RawRwLock + Send + Sync> Lockable for ReadLock<'l, T, R> { type Guard<'g> = RwLockReadRef<'g, T, R> where Self: 'g; fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { @@ -136,7 +136,7 @@ unsafe impl Lockable for ReadLock { } } -unsafe impl Lockable for WriteLock { +unsafe impl<'l, T: Send, R: RawRwLock + Send + Sync> Lockable for WriteLock<'l, T, R> { type Guard<'g> = RwLockWriteRef<'g, T, R> where Self: 'g; fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { @@ -342,19 +342,12 @@ unsafe impl OwnedLockable for (A, B, C, D, E) +unsafe impl + OwnedLockable for (A, B, C, D, E) { } unsafe impl< - 'a, A: OwnedLockable, B: OwnedLockable, C: OwnedLockable, @@ -366,7 +359,6 @@ unsafe impl< } unsafe impl< - 'a, A: OwnedLockable, B: OwnedLockable, C: OwnedLockable, diff --git a/src/rwlock/read_lock.rs b/src/rwlock/read_lock.rs index 011bd8c..29042b5 100644 --- a/src/rwlock/read_lock.rs +++ b/src/rwlock/read_lock.rs @@ -6,7 +6,7 @@ use crate::key::Keyable; use super::{ReadLock, RwLock, RwLockReadGuard, RwLockReadRef}; -impl Debug for ReadLock { +impl<'l, T: ?Sized + Debug, R: RawRwLock> Debug for ReadLock<'l, T, R> { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { // safety: this is just a try lock, and the value is dropped // immediately after, so there's no risk of blocking ourselves @@ -34,7 +34,7 @@ impl<'l, T, R> From<&'l RwLock> for ReadLock<'l, T, R> { } } -impl AsRef> for ReadLock { +impl<'l, T: ?Sized, R> AsRef> for ReadLock<'l, T, R> { fn as_ref(&self) -> &RwLock { &self.0 } diff --git a/src/rwlock/write_lock.rs b/src/rwlock/write_lock.rs index 1f7112a..8501cd8 100644 --- a/src/rwlock/write_lock.rs +++ b/src/rwlock/write_lock.rs @@ -6,7 +6,7 @@ use crate::key::Keyable; use super::{RwLock, RwLockWriteGuard, RwLockWriteRef, WriteLock}; -impl Debug for WriteLock { +impl<'l, T: ?Sized + Debug, R: RawRwLock> Debug for WriteLock<'l, T, R> { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { // safety: this is just a try lock, and the value is dropped // immediately after, so there's no risk of blocking ourselves @@ -34,9 +34,9 @@ impl<'l, T, R> From<&'l RwLock> for WriteLock<'l, T, R> { } } -impl AsRef> for WriteLock { +impl<'l, T: ?Sized, R> AsRef> for WriteLock<'l, T, R> { fn as_ref(&self) -> &RwLock { - &self.0 + self.0 } } @@ -57,7 +57,7 @@ impl<'l, T, R> WriteLock<'l, T, R> { } } -impl WriteLock { +impl<'l, T: ?Sized, R: RawRwLock> WriteLock<'l, T, R> { /// Locks the underlying [`RwLock`] with exclusive write access, blocking /// the current until it can be acquired. pub fn lock<'s, 'key: 's, Key: Keyable + 'key>( -- cgit v1.2.3 From 86610b631c20832d160c1a38181080232a05b508 Mon Sep 17 00:00:00 2001 From: Botahamec Date: Tue, 21 May 2024 19:17:11 -0400 Subject: Sharable API --- examples/dining_philosophers.rs | 3 +- examples/double_mutex.rs | 3 +- src/collection.rs | 19 ++- src/collection/boxed.rs | 60 ++++++++ src/collection/boxed_collection.rs | 60 -------- src/collection/guard.rs | 8 +- src/collection/owned.rs | 158 +++++++++++++++++++++ src/collection/owned_collection.rs | 65 --------- src/collection/ref.rs | 267 ++++++++++++++++++++++++++++++++++++ src/collection/ref_collection.rs | 244 --------------------------------- src/collection/retry.rs | 271 +++++++++++++++++++++++++++++++++++++ src/collection/retry_collection.rs | 138 ------------------- src/lib.rs | 3 +- src/lockable.rs | 235 ++++++++++++++++++++++++++++++++ 14 files changed, 1009 insertions(+), 525 deletions(-) create mode 100644 src/collection/boxed.rs delete mode 100644 src/collection/boxed_collection.rs create mode 100644 src/collection/owned.rs delete mode 100644 src/collection/owned_collection.rs create mode 100644 src/collection/ref.rs delete mode 100644 src/collection/ref_collection.rs create mode 100644 src/collection/retry.rs delete mode 100644 src/collection/retry_collection.rs (limited to 'examples/dining_philosophers.rs') diff --git a/examples/dining_philosophers.rs b/examples/dining_philosophers.rs index 1340564..70826ba 100644 --- a/examples/dining_philosophers.rs +++ b/examples/dining_philosophers.rs @@ -1,5 +1,6 @@ use std::{thread, time::Duration}; +use happylock::collection::RetryingLockCollection; use happylock::{collection::RefLockCollection, Mutex, ThreadKey}; static PHILOSOPHERS: [Philosopher; 5] = [ @@ -51,7 +52,7 @@ impl Philosopher { // safety: no philosopher asks for the same fork twice let forks = [&FORKS[self.left], &FORKS[self.right]]; - let forks = unsafe { RefLockCollection::new_unchecked(&forks) }; + let forks = unsafe { RetryingLockCollection::new_unchecked(&forks) }; let forks = forks.lock(key); println!("{} is eating...", self.name); thread::sleep(Duration::from_secs(1)); diff --git a/examples/double_mutex.rs b/examples/double_mutex.rs index e2b08df..e9a9c77 100644 --- a/examples/double_mutex.rs +++ b/examples/double_mutex.rs @@ -1,5 +1,6 @@ use std::thread; +use happylock::collection::RetryingLockCollection; use happylock::{collection::RefLockCollection, Mutex, ThreadKey}; const N: usize = 10; @@ -11,7 +12,7 @@ fn main() { for _ in 0..N { let th = thread::spawn(move || { let key = ThreadKey::get().unwrap(); - let lock = RefLockCollection::new(&DATA); + let lock = RetryingLockCollection::new_ref(&DATA); let mut guard = lock.lock(key); *guard.1 = (100 - *guard.0).to_string(); *guard.0 += 1; diff --git a/src/collection.rs b/src/collection.rs index a11d60c..6623c8a 100644 --- a/src/collection.rs +++ b/src/collection.rs @@ -1,15 +1,12 @@ use std::marker::PhantomData; -use crate::{ - key::Keyable, - lockable::{Lock, Lockable}, -}; +use crate::{key::Keyable, lockable::Lock}; -mod boxed_collection; +mod boxed; mod guard; -mod owned_collection; -mod ref_collection; -mod retry_collection; +mod owned; +mod r#ref; +mod retry; pub struct OwnedLockCollection { data: L, @@ -24,15 +21,15 @@ pub struct RefLockCollection<'a, L> { data: &'a L, } -pub struct BoxedLockCollection<'a, L>(RefLockCollection<'a, L>); +pub struct BoxedLockCollection<'a, L: 'a>(RefLockCollection<'a, L>); pub struct RetryingLockCollection { data: L, } /// A RAII guard for a generic [`Lockable`] type. -pub struct LockGuard<'g, 'key: 'g, L: Lockable + 'g, Key: Keyable + 'key> { - guard: L::Guard<'g>, +pub struct LockGuard<'key, Guard, Key: Keyable + 'key> { + guard: Guard, key: Key, _phantom: PhantomData<&'key ()>, } diff --git a/src/collection/boxed.rs b/src/collection/boxed.rs new file mode 100644 index 0000000..8b67ee9 --- /dev/null +++ b/src/collection/boxed.rs @@ -0,0 +1,60 @@ +use std::ops::{Deref, DerefMut}; + +use crate::{Lockable, OwnedLockable}; + +use super::{BoxedLockCollection, RefLockCollection}; + +impl<'a, L: 'a> Deref for BoxedLockCollection<'a, L> { + type Target = RefLockCollection<'a, L>; + + fn deref(&self) -> &Self::Target { + &self.0 + } +} + +impl<'a, L: 'a> DerefMut for BoxedLockCollection<'a, L> { + fn deref_mut(&mut self) -> &mut Self::Target { + &mut self.0 + } +} + +impl<'a, L: 'a> Drop for BoxedLockCollection<'a, L> { + fn drop(&mut self) { + // this was created with Box::new + let boxed = unsafe { Box::from_raw((self.0.data as *const L).cast_mut()) }; + drop(boxed); + } +} + +impl<'a, L: OwnedLockable + 'a> BoxedLockCollection<'a, L> { + #[must_use] + pub fn new(data: L) -> Self { + let boxed = Box::leak(Box::new(data)); + Self(RefLockCollection::new(boxed)) + } +} + +impl<'a, L: OwnedLockable + 'a> BoxedLockCollection<'a, L> { + #[must_use] + pub fn new_ref(data: &'a L) -> Self { + let boxed = Box::leak(Box::new(data)); + + // safety: this is a reference to an OwnedLockable, which can't + // possibly contain inner duplicates + Self(unsafe { RefLockCollection::new_unchecked(boxed) }) + } +} + +impl<'a, L: Lockable + 'a> BoxedLockCollection<'a, L> { + #[must_use] + pub unsafe fn new_unchecked(data: L) -> Self { + let boxed = Box::leak(Box::new(data)); + Self(RefLockCollection::new_unchecked(boxed)) + } + + #[must_use] + pub fn try_new(data: L) -> Option { + let boxed = Box::leak(Box::new(data)); + RefLockCollection::try_new(boxed).map(Self) + } +} diff --git a/src/collection/boxed_collection.rs b/src/collection/boxed_collection.rs deleted file mode 100644 index 1aae1e4..0000000 --- a/src/collection/boxed_collection.rs +++ /dev/null @@ -1,60 +0,0 @@ -use std::ops::{Deref, DerefMut}; - -use crate::{Lockable, OwnedLockable}; - -use super::{BoxedLockCollection, RefLockCollection}; - -impl<'a, L> Deref for BoxedLockCollection<'a, L> { - type Target = RefLockCollection<'a, L>; - - fn deref(&self) -> &Self::Target { - &self.0 - } -} - -impl<'a, L> DerefMut for BoxedLockCollection<'a, L> { - fn deref_mut(&mut self) -> &mut Self::Target { - &mut self.0 - } -} - -impl<'a, L> Drop for BoxedLockCollection<'a, L> { - fn drop(&mut self) { - // this was created with Box::new - let boxed = unsafe { Box::from_raw((self.0.data as *const L).cast_mut()) }; - drop(boxed); - } -} - -impl<'a, L: OwnedLockable> BoxedLockCollection<'a, L> { - #[must_use] - pub fn new(data: L) -> Self { - let boxed = Box::leak(Box::new(data)); - Self(RefLockCollection::new(boxed)) - } -} - -impl<'a, L: OwnedLockable> BoxedLockCollection<'a, &'a L> { - #[must_use] - pub fn new_ref(data: &'a L) -> Self { - let boxed = Box::leak(Box::new(data)); - - // safety: this is a reference to an OwnedLockable, which can't - // possibly contain inner duplicates - Self(unsafe { RefLockCollection::new_unchecked(boxed) }) - } -} - -impl<'a, L: Lockable> BoxedLockCollection<'a, L> { - #[must_use] - pub unsafe fn new_unchecked(data: L) -> Self { - let boxed = Box::leak(Box::new(data)); - Self(RefLockCollection::new_unchecked(boxed)) - } - - #[must_use] - pub fn try_new(data: L) -> Option { - let boxed = Box::leak(Box::new(data)); - RefLockCollection::try_new(boxed).map(Self) - } -} diff --git a/src/collection/guard.rs b/src/collection/guard.rs index e3ffb21..b8561eb 100644 --- a/src/collection/guard.rs +++ b/src/collection/guard.rs @@ -1,18 +1,18 @@ use std::ops::{Deref, DerefMut}; -use crate::{key::Keyable, Lockable}; +use crate::key::Keyable; use super::LockGuard; -impl<'a, 'key: 'a, L: Lockable + 'a, Key: Keyable> Deref for LockGuard<'a, 'key, L, Key> { - type Target = L::Guard<'a>; +impl<'key, Guard, Key: Keyable> Deref for LockGuard<'key, Guard, Key> { + type Target = Guard; fn deref(&self) -> &Self::Target { &self.guard } } -impl<'a, 'key: 'a, L: Lockable + 'a, Key: Keyable> DerefMut for LockGuard<'a, 'key, L, Key> { +impl<'key, Guard, Key: Keyable> DerefMut for LockGuard<'key, Guard, Key> { fn deref_mut(&mut self) -> &mut Self::Target { &mut self.guard } diff --git a/src/collection/owned.rs b/src/collection/owned.rs new file mode 100644 index 0000000..3415ac4 --- /dev/null +++ b/src/collection/owned.rs @@ -0,0 +1,158 @@ +use std::marker::PhantomData; + +use crate::{lockable::Lock, Keyable, Lockable, OwnedLockable, Sharable}; + +use super::{LockGuard, OwnedLockCollection}; + +fn get_locks(data: &L) -> Vec<&dyn Lock> { + let mut locks = Vec::new(); + data.get_ptrs(&mut locks); + locks +} + +unsafe impl Lockable for OwnedLockCollection { + type Guard<'g> = L::Guard<'g> where Self: 'g; + + type ReadGuard<'g> = L::ReadGuard<'g> where Self: 'g; + + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + self.data.get_ptrs(ptrs) + } + + unsafe fn guard(&self) -> Self::Guard<'_> { + self.data.guard() + } + + unsafe fn read_guard(&self) -> Self::ReadGuard<'_> { + self.data.read_guard() + } +} + +unsafe impl Sharable for OwnedLockCollection {} + +unsafe impl OwnedLockable for OwnedLockCollection {} + +impl OwnedLockCollection { + #[must_use] + pub const fn new(data: L) -> Self { + Self { data } + } + + pub fn lock<'g, 'key, Key: Keyable + 'key>( + &'g self, + key: Key, + ) -> LockGuard<'key, L::Guard<'g>, Key> { + let locks = get_locks(&self.data); + for lock in locks { + // safety: we have the thread key, and these locks happen in a + // predetermined order + unsafe { lock.lock() }; + } + + // safety: we've locked all of this already + let guard = unsafe { self.data.guard() }; + LockGuard { + guard, + key, + _phantom: PhantomData, + } + } + + pub fn try_lock<'g, 'key: 'g, Key: Keyable + 'key>( + &'g self, + key: Key, + ) -> Option, Key>> { + let locks = get_locks(&self.data); + let guard = unsafe { + for (i, lock) in locks.iter().enumerate() { + // safety: we have the thread key + let success = lock.try_lock(); + + if !success { + for lock in &locks[0..i] { + // safety: this lock was already acquired + lock.unlock(); + } + return None; + } + } + + // safety: we've acquired the locks + self.data.guard() + }; + + Some(LockGuard { + guard, + key, + _phantom: PhantomData, + }) + } + + #[allow(clippy::missing_const_for_fn)] + pub fn unlock<'g, 'key: 'g, Key: Keyable + 'key>( + guard: LockGuard<'key, L::Guard<'g>, Key>, + ) -> Key { + drop(guard.guard); + guard.key + } +} + +impl OwnedLockCollection { + pub fn read<'g, 'key, Key: Keyable + 'key>( + &'g self, + key: Key, + ) -> LockGuard<'key, L::ReadGuard<'g>, Key> { + let locks = get_locks(&self.data); + for lock in locks { + // safety: we have the thread key, and these locks happen in a + // predetermined order + unsafe { lock.read() }; + } + + // safety: we've locked all of this already + let guard = unsafe { self.data.read_guard() }; + LockGuard { + guard, + key, + _phantom: PhantomData, + } + } + + pub fn try_read<'g, 'key: 'g, Key: Keyable + 'key>( + &'g self, + key: Key, + ) -> Option, Key>> { + let locks = get_locks(&self.data); + let guard = unsafe { + for (i, lock) in locks.iter().enumerate() { + // safety: we have the thread key + let success = lock.try_read(); + + if !success { + for lock in &locks[0..i] { + // safety: this lock was already acquired + lock.unlock(); + } + return None; + } + } + + // safety: we've acquired the locks + self.data.read_guard() + }; + + Some(LockGuard { + guard, + key, + _phantom: PhantomData, + }) + } + + #[allow(clippy::missing_const_for_fn)] + pub fn unlock_read<'g, 'key: 'g, Key: Keyable + 'key>( + guard: LockGuard<'key, L::ReadGuard<'g>, Key>, + ) -> Key { + drop(guard.guard); + guard.key + } +} diff --git a/src/collection/owned_collection.rs b/src/collection/owned_collection.rs deleted file mode 100644 index ea8f2f2..0000000 --- a/src/collection/owned_collection.rs +++ /dev/null @@ -1,65 +0,0 @@ -use std::marker::PhantomData; - -use crate::{lockable::Lock, Keyable, Lockable, OwnedLockable}; - -use super::{LockGuard, OwnedLockCollection}; - -fn get_locks(data: &L) -> Vec<&dyn Lock> { - let mut locks = Vec::new(); - data.get_ptrs(&mut locks); - locks -} - -impl OwnedLockCollection { - #[must_use] - pub const fn new(data: L) -> Self { - Self { data } - } - - pub fn lock<'a, 'key, Key: Keyable + 'key>(&'a self, key: Key) -> LockGuard<'a, 'key, L, Key> { - let locks = get_locks(&self.data); - for lock in locks { - // safety: we have the thread key, and these locks happen in a - // predetermined order - unsafe { lock.lock() }; - } - - // safety: we've locked all of this already - let guard = unsafe { self.data.guard() }; - LockGuard { - guard, - key, - _phantom: PhantomData, - } - } - - pub fn try_lock<'a, 'key: 'a, Key: Keyable + 'key>( - &'a self, - key: Key, - ) -> Option> { - let locks = get_locks(&self.data); - let guard = unsafe { - for (i, lock) in locks.iter().enumerate() { - // safety: we have the thread key - let success = lock.try_lock(); - - if !success { - for lock in &locks[0..i] { - // safety: this lock was already acquired - lock.unlock(); - } - return None; - } - } - - // safety: we've acquired the locks - self.data.guard() - }; - - Some(LockGuard { - guard, - key, - _phantom: PhantomData, - }) - } -} diff --git a/src/collection/ref.rs b/src/collection/ref.rs new file mode 100644 index 0000000..9fe34c9 --- /dev/null +++ b/src/collection/ref.rs @@ -0,0 +1,267 @@ +use std::marker::PhantomData; + +use crate::{key::Keyable, lockable::Lock, Lockable, OwnedLockable, Sharable}; + +use super::{LockGuard, RefLockCollection}; + +#[must_use] +fn get_locks(data: &L) -> Vec<&dyn Lock> { + let mut locks = Vec::new(); + data.get_ptrs(&mut locks); + locks.sort_by_key(|lock| std::ptr::from_ref(*lock)); + locks +} + +/// returns `true` if the sorted list contains a duplicate +#[must_use] +fn contains_duplicates(l: &[&dyn Lock]) -> bool { + l.windows(2) + .any(|window| std::ptr::eq(window[0], window[1])) +} + +impl<'a, L: Lockable> AsRef for RefLockCollection<'a, L> { + fn as_ref(&self) -> &L { + self.data + } +} + +impl<'a, L: Lockable> AsRef for RefLockCollection<'a, L> { + fn as_ref(&self) -> &Self { + self + } +} + +impl<'a, L: Lockable> AsMut for RefLockCollection<'a, L> { + fn as_mut(&mut self) -> &mut Self { + self + } +} + +impl<'a, L> IntoIterator for &'a RefLockCollection<'a, L> +where + &'a L: IntoIterator, +{ + type Item = <&'a L as IntoIterator>::Item; + type IntoIter = <&'a L as IntoIterator>::IntoIter; + + fn into_iter(self) -> Self::IntoIter { + self.data.into_iter() + } +} + +unsafe impl<'c, L: Lockable> Lockable for RefLockCollection<'c, L> { + type Guard<'g> = L::Guard<'g> where Self: 'g; + + type ReadGuard<'g> = L::ReadGuard<'g> where Self: 'g; + + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + ptrs.extend_from_slice(&self.locks); + } + + unsafe fn guard(&self) -> Self::Guard<'_> { + self.data.guard() + } + + unsafe fn read_guard(&self) -> Self::ReadGuard<'_> { + self.data.read_guard() + } +} + +unsafe impl<'c, L: Sharable> Sharable for RefLockCollection<'c, L> {} + +impl<'a, L: OwnedLockable> RefLockCollection<'a, L> { + /// Creates a new collection of owned locks. + /// + /// Because the locks are owned, there's no need to do any checks for + /// duplicate values. + /// + /// # Examples + /// + /// ``` + /// use happylock::{LockCollection, Mutex}; + /// + /// let data = (Mutex::new(0), Mutex::new("")); + /// let lock = LockCollection::new(&data); + /// ``` + #[must_use] + pub fn new(data: &'a L) -> RefLockCollection { + RefLockCollection { + locks: get_locks(data), + data, + } + } +} + +impl<'a, L: Lockable> RefLockCollection<'a, L> { + /// Creates a new collections of locks. + /// + /// # Safety + /// + /// This results in undefined behavior if any locks are presented twice + /// within this collection. + /// + /// # Examples + /// + /// ``` + /// use happylock::{LockCollection, Mutex}; + /// + /// let data1 = Mutex::new(0); + /// let data2 = Mutex::new(""); + /// + /// // safety: data1 and data2 refer to distinct mutexes + /// let lock = unsafe { LockCollection::new_unchecked((&data1, &data2)) }; + /// ``` + #[must_use] + pub unsafe fn new_unchecked(data: &'a L) -> Self { + Self { + data, + locks: get_locks(data), + } + } + + /// Creates a new collection of locks. + /// + /// This returns `None` if any locks are found twice in the given + /// collection. + /// + /// # Examples + /// + /// ``` + /// use happylock::{LockCollection, Mutex}; + /// + /// let data1 = Mutex::new(0); + /// let data2 = Mutex::new(""); + /// + /// // data1 and data2 refer to distinct mutexes, so this won't panic + /// let lock = LockCollection::try_new((&data1, &data2)).unwrap(); + /// ``` + #[must_use] + pub fn try_new(data: &'a L) -> Option { + let locks = get_locks(data); + if contains_duplicates(&locks) { + return None; + } + + Some(Self { locks, data }) + } + + /// Locks the collection + /// + /// This function returns a guard that can be used to access the underlying + /// data. When the guard is dropped, the locks in the collection are also + /// dropped. + /// + /// # Examples + /// + /// ``` + /// use happylock::{LockCollection, Mutex, ThreadKey}; + /// + /// let key = ThreadKey::get().unwrap(); + /// let lock = LockCollection::new((Mutex::new(0), Mutex::new(""))); + /// + /// let mut guard = lock.lock(key); + /// *guard.0 += 1; + /// *guard.1 = "1"; + /// ``` + pub fn lock<'key: 'a, Key: Keyable + 'key>( + &'a self, + key: Key, + ) -> LockGuard<'key, L::Guard<'a>, Key> { + for lock in &self.locks { + // safety: we have the thread key + unsafe { lock.lock() }; + } + + LockGuard { + // safety: we've already acquired the lock + guard: unsafe { self.data.guard() }, + key, + _phantom: PhantomData, + } + } + + /// Attempts to lock the without blocking. + /// + /// If successful, this method returns a guard that can be used to access + /// the data, and unlocks the data when it is dropped. Otherwise, `None` is + /// returned. + /// + /// # Examples + /// + /// ``` + /// use happylock::{LockCollection, Mutex, ThreadKey}; + /// + /// let key = ThreadKey::get().unwrap(); + /// let lock = LockCollection::new((Mutex::new(0), Mutex::new(""))); + /// + /// match lock.try_lock(key) { + /// Some(mut guard) => { + /// *guard.0 += 1; + /// *guard.1 = "1"; + /// }, + /// None => unreachable!(), + /// }; + /// + /// ``` + pub fn try_lock<'key: 'a, Key: Keyable + 'key>( + &'a self, + key: Key, + ) -> Option, Key>> { + let guard = unsafe { + for (i, lock) in self.locks.iter().enumerate() { + // safety: we have the thread key + let success = lock.try_lock(); + + if !success { + for lock in &self.locks[0..i] { + // safety: this lock was already acquired + lock.unlock(); + } + return None; + } + } + + // safety: we've acquired the locks + self.data.guard() + }; + + Some(LockGuard { + guard, + key, + _phantom: PhantomData, + }) + } + + /// Unlocks the underlying lockable data type, returning the key that's + /// associated with it. + /// + /// # Examples + /// + /// ``` + /// use happylock::{LockCollection, Mutex, ThreadKey}; + /// + /// let key = ThreadKey::get().unwrap(); + /// let lock = LockCollection::new((Mutex::new(0), Mutex::new(""))); + /// + /// let mut guard = lock.lock(key); + /// *guard.0 += 1; + /// *guard.1 = "1"; + /// let key = LockCollection::unlock(guard); + /// ``` + #[allow(clippy::missing_const_for_fn)] + pub fn unlock<'key: 'a, Key: Keyable + 'key>(guard: LockGuard<'key, L::Guard<'a>, Key>) -> Key { + drop(guard.guard); + guard.key + } +} + +impl<'a, L: 'a> RefLockCollection<'a, L> +where + &'a L: IntoIterator, +{ + /// Returns an iterator over references to each value in the collection. + #[must_use] + pub fn iter(&'a self) -> <&'a L as IntoIterator>::IntoIter { + self.into_iter() + } +} diff --git a/src/collection/ref_collection.rs b/src/collection/ref_collection.rs deleted file mode 100644 index 41f6b16..0000000 --- a/src/collection/ref_collection.rs +++ /dev/null @@ -1,244 +0,0 @@ -use std::marker::PhantomData; - -use crate::{key::Keyable, lockable::Lock, Lockable, OwnedLockable}; - -use super::{LockGuard, RefLockCollection}; - -#[must_use] -fn get_locks(data: &L) -> Vec<&dyn Lock> { - let mut locks = Vec::new(); - data.get_ptrs(&mut locks); - locks.sort_by_key(|lock| std::ptr::from_ref(*lock)); - locks -} - -/// returns `true` if the sorted list contains a duplicate -#[must_use] -fn contains_duplicates(l: &[&dyn Lock]) -> bool { - l.windows(2) - .any(|window| std::ptr::eq(window[0], window[1])) -} - -impl<'a, L: Lockable> AsRef for RefLockCollection<'a, L> { - fn as_ref(&self) -> &L { - self.data - } -} - -impl<'a, L: Lockable> AsRef for RefLockCollection<'a, L> { - fn as_ref(&self) -> &Self { - self - } -} - -impl<'a, L: Lockable> AsMut for RefLockCollection<'a, L> { - fn as_mut(&mut self) -> &mut Self { - self - } -} - -impl<'a, L> IntoIterator for &'a RefLockCollection<'a, L> -where - &'a L: IntoIterator, -{ - type Item = <&'a L as IntoIterator>::Item; - type IntoIter = <&'a L as IntoIterator>::IntoIter; - - fn into_iter(self) -> Self::IntoIter { - self.data.into_iter() - } -} - -impl<'a, L: OwnedLockable> RefLockCollection<'a, L> { - /// Creates a new collection of owned locks. - /// - /// Because the locks are owned, there's no need to do any checks for - /// duplicate values. - /// - /// # Examples - /// - /// ``` - /// use happylock::{LockCollection, Mutex}; - /// - /// let data = (Mutex::new(0), Mutex::new("")); - /// let lock = LockCollection::new(&data); - /// ``` - #[must_use] - pub fn new(data: &'a L) -> RefLockCollection { - RefLockCollection { - locks: get_locks(data), - data, - } - } -} - -impl<'a, L: Lockable> RefLockCollection<'a, L> { - /// Creates a new collections of locks. - /// - /// # Safety - /// - /// This results in undefined behavior if any locks are presented twice - /// within this collection. - /// - /// # Examples - /// - /// ``` - /// use happylock::{LockCollection, Mutex}; - /// - /// let data1 = Mutex::new(0); - /// let data2 = Mutex::new(""); - /// - /// // safety: data1 and data2 refer to distinct mutexes - /// let lock = unsafe { LockCollection::new_unchecked((&data1, &data2)) }; - /// ``` - #[must_use] - pub unsafe fn new_unchecked(data: &'a L) -> Self { - Self { - data, - locks: get_locks(data), - } - } - - /// Creates a new collection of locks. - /// - /// This returns `None` if any locks are found twice in the given - /// collection. - /// - /// # Examples - /// - /// ``` - /// use happylock::{LockCollection, Mutex}; - /// - /// let data1 = Mutex::new(0); - /// let data2 = Mutex::new(""); - /// - /// // data1 and data2 refer to distinct mutexes, so this won't panic - /// let lock = LockCollection::try_new((&data1, &data2)).unwrap(); - /// ``` - #[must_use] - pub fn try_new(data: &'a L) -> Option { - let locks = get_locks(data); - if contains_duplicates(&locks) { - return None; - } - - Some(Self { locks, data }) - } - - /// Locks the collection - /// - /// This function returns a guard that can be used to access the underlying - /// data. When the guard is dropped, the locks in the collection are also - /// dropped. - /// - /// # Examples - /// - /// ``` - /// use happylock::{LockCollection, Mutex, ThreadKey}; - /// - /// let key = ThreadKey::get().unwrap(); - /// let lock = LockCollection::new((Mutex::new(0), Mutex::new(""))); - /// - /// let mut guard = lock.lock(key); - /// *guard.0 += 1; - /// *guard.1 = "1"; - /// ``` - pub fn lock<'key: 'a, Key: Keyable + 'key>(&'a self, key: Key) -> LockGuard<'a, 'key, L, Key> { - for lock in &self.locks { - // safety: we have the thread key - unsafe { lock.lock() }; - } - - LockGuard { - // safety: we've already acquired the lock - guard: unsafe { self.data.guard() }, - key, - _phantom: PhantomData, - } - } - - /// Attempts to lock the without blocking. - /// - /// If successful, this method returns a guard that can be used to access - /// the data, and unlocks the data when it is dropped. Otherwise, `None` is - /// returned. - /// - /// # Examples - /// - /// ``` - /// use happylock::{LockCollection, Mutex, ThreadKey}; - /// - /// let key = ThreadKey::get().unwrap(); - /// let lock = LockCollection::new((Mutex::new(0), Mutex::new(""))); - /// - /// match lock.try_lock(key) { - /// Some(mut guard) => { - /// *guard.0 += 1; - /// *guard.1 = "1"; - /// }, - /// None => unreachable!(), - /// }; - /// - /// ``` - pub fn try_lock<'key: 'a, Key: Keyable + 'key>( - &'a self, - key: Key, - ) -> Option> { - let guard = unsafe { - for (i, lock) in self.locks.iter().enumerate() { - // safety: we have the thread key - let success = lock.try_lock(); - - if !success { - for lock in &self.locks[0..i] { - // safety: this lock was already acquired - lock.unlock(); - } - return None; - } - } - - // safety: we've acquired the locks - self.data.guard() - }; - - Some(LockGuard { - guard, - key, - _phantom: PhantomData, - }) - } - - /// Unlocks the underlying lockable data type, returning the key that's - /// associated with it. - /// - /// # Examples - /// - /// ``` - /// use happylock::{LockCollection, Mutex, ThreadKey}; - /// - /// let key = ThreadKey::get().unwrap(); - /// let lock = LockCollection::new((Mutex::new(0), Mutex::new(""))); - /// - /// let mut guard = lock.lock(key); - /// *guard.0 += 1; - /// *guard.1 = "1"; - /// let key = LockCollection::unlock(guard); - /// ``` - #[allow(clippy::missing_const_for_fn)] - pub fn unlock<'key: 'a, Key: Keyable + 'key>(guard: LockGuard<'a, 'key, L, Key>) -> Key { - drop(guard.guard); - guard.key - } -} - -impl<'a, L: 'a> RefLockCollection<'a, L> -where - &'a L: IntoIterator, -{ - /// Returns an iterator over references to each value in the collection. - #[must_use] - pub fn iter(&'a self) -> <&'a L as IntoIterator>::IntoIter { - self.into_iter() - } -} diff --git a/src/collection/retry.rs b/src/collection/retry.rs new file mode 100644 index 0000000..3000f8b --- /dev/null +++ b/src/collection/retry.rs @@ -0,0 +1,271 @@ +use crate::{lockable::Lock, Keyable, Lockable, OwnedLockable, Sharable}; +use std::collections::HashSet; +use std::marker::PhantomData; + +use super::{LockGuard, RetryingLockCollection}; + +fn contains_duplicates(data: L) -> bool { + let mut locks = Vec::new(); + data.get_ptrs(&mut locks); + let locks = locks.into_iter().map(|l| l as *const dyn Lock); + + let mut locks_set = HashSet::new(); + for lock in locks { + if !locks_set.insert(lock) { + return true; + } + } + + false +} + +unsafe impl Lockable for RetryingLockCollection { + type Guard<'g> = L::Guard<'g> where Self: 'g; + + type ReadGuard<'g> = L::ReadGuard<'g> where Self: 'g; + + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + self.data.get_ptrs(ptrs) + } + + unsafe fn guard(&self) -> Self::Guard<'_> { + self.data.guard() + } + + unsafe fn read_guard(&self) -> Self::ReadGuard<'_> { + self.data.read_guard() + } +} + +unsafe impl Sharable for RetryingLockCollection {} + +unsafe impl OwnedLockable for RetryingLockCollection {} + +impl RetryingLockCollection { + #[must_use] + pub const fn new(data: L) -> Self { + Self { data } + } +} + +impl<'a, L: OwnedLockable> RetryingLockCollection<&'a L> { + #[must_use] + pub const fn new_ref(data: &'a L) -> Self { + Self { data } + } +} + +impl RetryingLockCollection { + #[must_use] + pub const unsafe fn new_unchecked(data: L) -> Self { + Self { data } + } + + pub fn try_new(data: L) -> Option { + contains_duplicates(&data).then_some(Self { data }) + } + + pub fn lock<'g, 'key: 'g, Key: Keyable + 'key>( + &'g self, + key: Key, + ) -> LockGuard<'key, L::Guard<'g>, Key> { + let mut first_index = 0; + let mut locks = Vec::new(); + self.data.get_ptrs(&mut locks); + + if locks.is_empty() { + return LockGuard { + // safety: there's no data being returned + guard: unsafe { self.data.guard() }, + key, + _phantom: PhantomData, + }; + } + + let guard = unsafe { + 'outer: loop { + // safety: we have the thread key + locks[first_index].lock(); + for (i, lock) in locks.iter().enumerate() { + if i == first_index { + continue; + } + + // safety: we have the thread key + if !lock.try_lock() { + for lock in locks.iter().take(i) { + // safety: we already locked all of these + lock.unlock(); + } + + if first_index >= i { + // safety: this is already locked and can't be unlocked + // by the previous loop + locks[first_index].unlock(); + } + + first_index = i; + continue 'outer; + } + } + + // safety: we locked all the data + break self.data.guard(); + } + }; + + LockGuard { + guard, + key, + _phantom: PhantomData, + } + } + + pub fn try_lock<'g, 'key: 'g, Key: Keyable + 'key>( + &'g self, + key: Key, + ) -> Option, Key>> { + let mut locks = Vec::new(); + self.data.get_ptrs(&mut locks); + + if locks.is_empty() { + return Some(LockGuard { + // safety: there's no data being returned + guard: unsafe { self.data.guard() }, + key, + _phantom: PhantomData, + }); + } + + let guard = unsafe { + for (i, lock) in locks.iter().enumerate() { + // safety: we have the thread key + if !lock.try_lock() { + for lock in locks.iter().take(i) { + // safety: we already locked all of these + lock.unlock(); + } + return None; + } + } + + // safety: we locked all the data + self.data.guard() + }; + + Some(LockGuard { + guard, + key, + _phantom: PhantomData, + }) + } + + pub fn unlock<'key, Key: Keyable + 'key>(guard: LockGuard<'key, L::Guard<'_>, Key>) -> Key { + drop(guard.guard); + guard.key + } +} + +impl RetryingLockCollection { + pub fn read<'g, 'key: 'g, Key: Keyable + 'key>( + &'g self, + key: Key, + ) -> LockGuard<'key, L::ReadGuard<'g>, Key> { + let mut first_index = 0; + let mut locks = Vec::new(); + self.data.get_ptrs(&mut locks); + + if locks.is_empty() { + return LockGuard { + // safety: there's no data being returned + guard: unsafe { self.data.read_guard() }, + key, + _phantom: PhantomData, + }; + } + + let guard = unsafe { + 'outer: loop { + // safety: we have the thread key + locks[first_index].read(); + for (i, lock) in locks.iter().enumerate() { + if i == first_index { + continue; + } + + // safety: we have the thread key + if !lock.try_read() { + for lock in locks.iter().take(i) { + // safety: we already locked all of these + lock.unlock_read(); + } + + if first_index >= i { + // safety: this is already locked and can't be unlocked + // by the previous loop + locks[first_index].unlock_read(); + } + + first_index = i; + continue 'outer; + } + } + + // safety: we locked all the data + break self.data.read_guard(); + } + }; + + LockGuard { + guard, + key, + _phantom: PhantomData, + } + } + + pub fn try_read<'g, 'key: 'g, Key: Keyable + 'key>( + &'g self, + key: Key, + ) -> Option, Key>> { + let mut locks = Vec::new(); + self.data.get_ptrs(&mut locks); + + if locks.is_empty() { + return Some(LockGuard { + // safety: there's no data being returned + guard: unsafe { self.data.read_guard() }, + key, + _phantom: PhantomData, + }); + } + + let guard = unsafe { + for (i, lock) in locks.iter().enumerate() { + // safety: we have the thread key + if !lock.try_read() { + for lock in locks.iter().take(i) { + // safety: we already locked all of these + lock.unlock_read(); + } + return None; + } + } + + // safety: we locked all the data + self.data.read_guard() + }; + + Some(LockGuard { + guard, + key, + _phantom: PhantomData, + }) + } + + pub fn unlock_read<'key, Key: Keyable + 'key>( + guard: LockGuard<'key, L::ReadGuard<'_>, Key>, + ) -> Key { + drop(guard.guard); + guard.key + } +} diff --git a/src/collection/retry_collection.rs b/src/collection/retry_collection.rs deleted file mode 100644 index 73f9e18..0000000 --- a/src/collection/retry_collection.rs +++ /dev/null @@ -1,138 +0,0 @@ -use std::marker::PhantomData; - -use crate::{lockable::Lock, Keyable, Lockable, OwnedLockable}; - -use super::{LockGuard, RetryingLockCollection}; - -fn contains_duplicates(data: L) -> bool { - let mut locks = Vec::new(); - data.get_ptrs(&mut locks); - let mut locks: Vec<_> = locks.into_iter().map(|l| l as *const dyn Lock).collect(); - locks.sort_unstable(); - locks.windows(2).any(|w| std::ptr::addr_eq(w[0], w[1])) -} - -impl RetryingLockCollection { - #[must_use] - pub const fn new(data: L) -> Self { - Self { data } - } -} - -impl<'a, L: OwnedLockable> RetryingLockCollection<&'a L> { - #[must_use] - pub const fn new_ref(data: &'a L) -> Self { - Self { data } - } -} - -impl RetryingLockCollection { - #[must_use] - pub const unsafe fn new_unchecked(data: L) -> Self { - Self { data } - } - - pub fn try_new(data: L) -> Option { - contains_duplicates(&data).then_some(Self { data }) - } - - pub fn lock<'a, 'key: 'a, Key: Keyable + 'key>( - &'a self, - key: Key, - ) -> LockGuard<'a, 'key, L, Key> { - let mut first_index = 0; - let mut locks = Vec::new(); - self.data.get_ptrs(&mut locks); - - if locks.is_empty() { - return LockGuard { - // safety: there's no data being returned - guard: unsafe { self.data.guard() }, - key, - _phantom: PhantomData, - }; - } - - let guard = unsafe { - 'outer: loop { - // safety: we have the thread key - locks[first_index].lock(); - for (i, lock) in locks.iter().enumerate() { - if i == first_index { - continue; - } - - // safety: we have the thread key - if !lock.try_lock() { - for lock in locks.iter().take(i) { - // safety: we already locked all of these - lock.unlock(); - } - - if first_index >= i { - // safety: this is already locked and can't be unlocked - // by the previous loop - locks[first_index].unlock(); - } - - first_index = i; - continue 'outer; - } - } - - // safety: we locked all the data - break self.data.guard(); - } - }; - - LockGuard { - guard, - key, - _phantom: PhantomData, - } - } - - pub fn try_lock<'a, 'key: 'a, Key: Keyable + 'key>( - &'a self, - key: Key, - ) -> Option> { - let mut locks = Vec::new(); - self.data.get_ptrs(&mut locks); - - if locks.is_empty() { - return Some(LockGuard { - // safety: there's no data being returned - guard: unsafe { self.data.guard() }, - key, - _phantom: PhantomData, - }); - } - - let guard = unsafe { - for (i, lock) in locks.iter().enumerate() { - // safety: we have the thread key - if !lock.try_lock() { - for lock in locks.iter().take(i) { - // safety: we already locked all of these - lock.unlock(); - } - return None; - } - } - - // safety: we locked all the data - self.data.guard() - }; - - Some(LockGuard { - guard, - key, - _phantom: PhantomData, - }) - } - - pub fn unlock<'key, Key: Keyable + 'key>(guard: LockGuard<'_, 'key, L, Key>) -> Key { - drop(guard.guard); - guard.key - } -} diff --git a/src/lib.rs b/src/lib.rs index 7e7930f..668f3db 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -113,8 +113,9 @@ pub mod collection; pub mod mutex; pub mod rwlock; +pub use collection::BoxedLockCollection as LockCollection; pub use key::{Keyable, ThreadKey}; -pub use lockable::{Lockable, OwnedLockable}; +pub use lockable::{Lockable, OwnedLockable, Sharable}; #[cfg(feature = "spin")] pub use mutex::SpinLock; diff --git a/src/lockable.rs b/src/lockable.rs index 9b3a4e4..23aeb4c 100644 --- a/src/lockable.rs +++ b/src/lockable.rs @@ -45,6 +45,12 @@ pub unsafe trait Lock: Send + Sync { /// /// It is undefined behavior to use this if the lock is not acquired unsafe fn unlock(&self); + + unsafe fn read(&self); + + unsafe fn try_read(&self) -> bool; + + unsafe fn unlock_read(&self); } pub unsafe trait Lockable { @@ -53,12 +59,21 @@ pub unsafe trait Lockable { where Self: 'g; + type ReadGuard<'g> + where + Self: 'g; + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>); #[must_use] unsafe fn guard(&self) -> Self::Guard<'_>; + + #[must_use] + unsafe fn read_guard(&self) -> Self::ReadGuard<'_>; } +pub unsafe trait Sharable: Lockable {} + /// A type that may be locked and unlocked, and is known to be the only valid /// instance of the lock. /// @@ -80,6 +95,18 @@ unsafe impl Lock for Mutex { unsafe fn unlock(&self) { self.raw().unlock() } + + unsafe fn read(&self) { + self.raw().lock() + } + + unsafe fn try_read(&self) -> bool { + self.raw().try_lock() + } + + unsafe fn unlock_read(&self) { + self.raw().unlock() + } } unsafe impl Lock for RwLock { @@ -94,10 +121,23 @@ unsafe impl Lock for RwLock { unsafe fn unlock(&self) { self.raw().unlock_exclusive() } + + unsafe fn read(&self) { + self.raw().lock_shared() + } + + unsafe fn try_read(&self) -> bool { + self.raw().try_lock_shared() + } + + unsafe fn unlock_read(&self) { + self.raw().unlock_shared() + } } unsafe impl Lockable for Mutex { type Guard<'g> = MutexRef<'g, T, R> where Self: 'g; + type ReadGuard<'g> = MutexRef<'g, T, R> where Self: 'g; fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { ptrs.push(self); @@ -106,11 +146,17 @@ unsafe impl Lockable for Mutex { unsafe fn guard(&self) -> Self::Guard<'_> { MutexRef::new(self) } + + unsafe fn read_guard(&self) -> Self::ReadGuard<'_> { + MutexRef::new(self) + } } unsafe impl Lockable for RwLock { type Guard<'g> = RwLockWriteRef<'g, T, R> where Self: 'g; + type ReadGuard<'g> = RwLockReadRef<'g, T, R> where Self: 'g; + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { ptrs.push(self); } @@ -118,8 +164,14 @@ unsafe impl Lockable for RwLock { unsafe fn guard(&self) -> Self::Guard<'_> { RwLockWriteRef::new(self) } + + unsafe fn read_guard(&self) -> Self::ReadGuard<'_> { + RwLockReadRef::new(self) + } } +unsafe impl Sharable for RwLock {} + unsafe impl OwnedLockable for Mutex {} unsafe impl OwnedLockable for RwLock {} @@ -127,6 +179,8 @@ unsafe impl OwnedLockable for RwLock unsafe impl<'l, T: Send, R: RawRwLock + Send + Sync> Lockable for ReadLock<'l, T, R> { type Guard<'g> = RwLockReadRef<'g, T, R> where Self: 'g; + type ReadGuard<'g> = RwLockReadRef<'g, T, R> where Self: 'g; + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { ptrs.push(self.as_ref()); } @@ -134,11 +188,17 @@ unsafe impl<'l, T: Send, R: RawRwLock + Send + Sync> Lockable for ReadLock<'l, T unsafe fn guard(&self) -> Self::Guard<'_> { RwLockReadRef::new(self.as_ref()) } + + unsafe fn read_guard(&self) -> Self::Guard<'_> { + RwLockReadRef::new(self.as_ref()) + } } unsafe impl<'l, T: Send, R: RawRwLock + Send + Sync> Lockable for WriteLock<'l, T, R> { type Guard<'g> = RwLockWriteRef<'g, T, R> where Self: 'g; + type ReadGuard<'g> = RwLockWriteRef<'g, T, R> where Self: 'g; + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { ptrs.push(self.as_ref()); } @@ -146,11 +206,19 @@ unsafe impl<'l, T: Send, R: RawRwLock + Send + Sync> Lockable for WriteLock<'l, unsafe fn guard(&self) -> Self::Guard<'_> { RwLockWriteRef::new(self.as_ref()) } + + unsafe fn read_guard(&self) -> Self::Guard<'_> { + RwLockWriteRef::new(self.as_ref()) + } } +unsafe impl<'l, T: Send, R: RawRwLock + Send + Sync> Sharable for ReadLock<'l, T, R> {} + unsafe impl Lockable for &T { type Guard<'g> = T::Guard<'g> where Self: 'g; + type ReadGuard<'g> = T::ReadGuard<'g> where Self: 'g; + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { (*self).get_ptrs(ptrs); } @@ -158,11 +226,17 @@ unsafe impl Lockable for &T { unsafe fn guard(&self) -> Self::Guard<'_> { (*self).guard() } + + unsafe fn read_guard(&self) -> Self::ReadGuard<'_> { + (*self).read_guard() + } } unsafe impl Lockable for &mut T { type Guard<'g> = T::Guard<'g> where Self: 'g; + type ReadGuard<'g> = T::ReadGuard<'g> where Self: 'g; + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { (**self).get_ptrs(ptrs) } @@ -170,6 +244,10 @@ unsafe impl Lockable for &mut T { unsafe fn guard(&self) -> Self::Guard<'_> { (**self).guard() } + + unsafe fn read_guard(&self) -> Self::ReadGuard<'_> { + (**self).read_guard() + } } unsafe impl OwnedLockable for &mut T {} @@ -177,6 +255,8 @@ unsafe impl OwnedLockable for &mut T {} unsafe impl Lockable for (A,) { type Guard<'g> = (A::Guard<'g>,) where Self: 'g; + type ReadGuard<'g> = (A::ReadGuard<'g>,) where Self: 'g; + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { self.0.get_ptrs(ptrs); } @@ -184,11 +264,17 @@ unsafe impl Lockable for (A,) { unsafe fn guard(&self) -> Self::Guard<'_> { (self.0.guard(),) } + + unsafe fn read_guard(&self) -> Self::ReadGuard<'_> { + (self.0.read_guard(),) + } } unsafe impl Lockable for (A, B) { type Guard<'g> = (A::Guard<'g>, B::Guard<'g>) where Self: 'g; + type ReadGuard<'g> = (A::ReadGuard<'g>, B::ReadGuard<'g>) where Self: 'g; + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { self.0.get_ptrs(ptrs); self.1.get_ptrs(ptrs); @@ -197,11 +283,17 @@ unsafe impl Lockable for (A, B) { unsafe fn guard(&self) -> Self::Guard<'_> { (self.0.guard(), self.1.guard()) } + + unsafe fn read_guard(&self) -> Self::ReadGuard<'_> { + (self.0.read_guard(), self.1.read_guard()) + } } unsafe impl Lockable for (A, B, C) { type Guard<'g> = (A::Guard<'g>, B::Guard<'g>, C::Guard<'g>) where Self: 'g; + type ReadGuard<'g> = (A::ReadGuard<'g>, B::ReadGuard<'g>, C::ReadGuard<'g>) where Self: 'g; + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { self.0.get_ptrs(ptrs); self.1.get_ptrs(ptrs); @@ -211,11 +303,26 @@ unsafe impl Lockable for (A, B, C) { unsafe fn guard(&self) -> Self::Guard<'_> { (self.0.guard(), self.1.guard(), self.2.guard()) } + + unsafe fn read_guard(&self) -> Self::ReadGuard<'_> { + ( + self.0.read_guard(), + self.1.read_guard(), + self.2.read_guard(), + ) + } } unsafe impl Lockable for (A, B, C, D) { type Guard<'g> = (A::Guard<'g>, B::Guard<'g>, C::Guard<'g>, D::Guard<'g>) where Self: 'g; + type ReadGuard<'g> = ( + A::ReadGuard<'g>, + B::ReadGuard<'g>, + C::ReadGuard<'g>, + D::ReadGuard<'g>, + ) where Self: 'g; + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { self.0.get_ptrs(ptrs); self.1.get_ptrs(ptrs); @@ -231,6 +338,15 @@ unsafe impl Lockable for (A, self.3.guard(), ) } + + unsafe fn read_guard(&self) -> Self::ReadGuard<'_> { + ( + self.0.read_guard(), + self.1.read_guard(), + self.2.read_guard(), + self.3.read_guard(), + ) + } } unsafe impl Lockable @@ -244,6 +360,14 @@ unsafe impl Loc E::Guard<'g>, ) where Self: 'g; + type ReadGuard<'g> = ( + A::ReadGuard<'g>, + B::ReadGuard<'g>, + C::ReadGuard<'g>, + D::ReadGuard<'g>, + E::ReadGuard<'g>, + ) where Self: 'g; + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { self.0.get_ptrs(ptrs); self.1.get_ptrs(ptrs); @@ -261,6 +385,16 @@ unsafe impl Loc self.4.guard(), ) } + + unsafe fn read_guard(&self) -> Self::ReadGuard<'_> { + ( + self.0.read_guard(), + self.1.read_guard(), + self.2.read_guard(), + self.3.read_guard(), + self.4.read_guard(), + ) + } } unsafe impl Lockable @@ -275,6 +409,15 @@ unsafe impl, ) where Self: 'g; + type ReadGuard<'g> = ( + A::ReadGuard<'g>, + B::ReadGuard<'g>, + C::ReadGuard<'g>, + D::ReadGuard<'g>, + E::ReadGuard<'g>, + F::ReadGuard<'g>, + ) where Self: 'g; + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { self.0.get_ptrs(ptrs); self.1.get_ptrs(ptrs); @@ -294,6 +437,17 @@ unsafe impl Self::ReadGuard<'_> { + ( + self.0.read_guard(), + self.1.read_guard(), + self.2.read_guard(), + self.3.read_guard(), + self.4.read_guard(), + self.5.read_guard(), + ) + } } unsafe impl @@ -309,6 +463,16 @@ unsafe impl, ) where Self: 'g; + type ReadGuard<'g> = ( + A::ReadGuard<'g>, + B::ReadGuard<'g>, + C::ReadGuard<'g>, + D::ReadGuard<'g>, + E::ReadGuard<'g>, + F::ReadGuard<'g>, + G::ReadGuard<'g>, + ) where Self: 'g; + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { self.0.get_ptrs(ptrs); self.1.get_ptrs(ptrs); @@ -330,6 +494,40 @@ unsafe impl Self::ReadGuard<'_> { + ( + self.0.read_guard(), + self.1.read_guard(), + self.2.read_guard(), + self.3.read_guard(), + self.4.read_guard(), + self.5.read_guard(), + self.6.read_guard(), + ) + } +} + +unsafe impl Sharable for (A,) {} +unsafe impl Sharable for (A, B) {} + +unsafe impl Sharable for (A, B, C) {} + +unsafe impl Sharable for (A, B, C, D) {} + +unsafe impl Sharable + for (A, B, C, D, E) +{ +} + +unsafe impl Sharable + for (A, B, C, D, E, F) +{ +} + +unsafe impl + Sharable for (A, B, C, D, E, F, G) +{ } unsafe impl OwnedLockable for (A,) {} @@ -373,6 +571,8 @@ unsafe impl< unsafe impl Lockable for [T; N] { type Guard<'g> = [T::Guard<'g>; N] where Self: 'g; + type ReadGuard<'g> = [T::ReadGuard<'g>; N] where Self: 'g; + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { for lock in self { lock.get_ptrs(ptrs); @@ -387,11 +587,22 @@ unsafe impl Lockable for [T; N] { guards.map(|g| g.assume_init()) } + + unsafe fn read_guard<'g>(&'g self) -> Self::ReadGuard<'g> { + let mut guards = MaybeUninit::<[MaybeUninit>; N]>::uninit().assume_init(); + for i in 0..N { + guards[i].write(self[i].read_guard()); + } + + guards.map(|g| g.assume_init()) + } } unsafe impl Lockable for Box<[T]> { type Guard<'g> = Box<[T::Guard<'g>]> where Self: 'g; + type ReadGuard<'g> = Box<[T::ReadGuard<'g>]> where Self: 'g; + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { for lock in self.iter() { lock.get_ptrs(ptrs); @@ -406,11 +617,22 @@ unsafe impl Lockable for Box<[T]> { guards.into_boxed_slice() } + + unsafe fn read_guard(&self) -> Self::ReadGuard<'_> { + let mut guards = Vec::new(); + for lock in self.iter() { + guards.push(lock.read_guard()); + } + + guards.into_boxed_slice() + } } unsafe impl Lockable for Vec { type Guard<'g> = Vec> where Self: 'g; + type ReadGuard<'g> = Box<[T::ReadGuard<'g>]> where Self: 'g; + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { for lock in self { lock.get_ptrs(ptrs); @@ -425,8 +647,21 @@ unsafe impl Lockable for Vec { guards } + + unsafe fn read_guard(&self) -> Self::ReadGuard<'_> { + let mut guards = Vec::new(); + for lock in self { + guards.push(lock.read_guard()); + } + + guards.into_boxed_slice() + } } +unsafe impl Sharable for [T; N] {} +unsafe impl Sharable for Box<[T]> {} +unsafe impl Sharable for Vec {} + unsafe impl OwnedLockable for [T; N] {} unsafe impl OwnedLockable for Box<[T]> {} unsafe impl OwnedLockable for Vec {} -- cgit v1.2.3 From ef191a3e8ecf4093fcd08036e35012c1af173a08 Mon Sep 17 00:00:00 2001 From: Botahamec Date: Wed, 22 May 2024 17:27:35 -0400 Subject: Documentation for types --- Cargo.toml | 2 +- examples/dining_philosophers.rs | 3 +- examples/double_mutex.rs | 3 +- src/collection.rs | 78 +++++++++++++++++++++++-- src/collection/boxed.rs | 8 +-- src/collection/owned.rs | 7 ++- src/collection/ref.rs | 9 +-- src/collection/retry.rs | 8 ++- src/lib.rs | 11 +++- src/lockable.rs | 123 +++++++++++++++++++++++++++++++++------- 10 files changed, 204 insertions(+), 48 deletions(-) (limited to 'examples/dining_philosophers.rs') diff --git a/Cargo.toml b/Cargo.toml index 3091f8c..69b9ef7 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -1,6 +1,6 @@ [package] name = "happylock" -version = "0.1.1" +version = "0.2.0" authors = ["Mica White "] edition = "2021" description = "Free deadlock prevention" diff --git a/examples/dining_philosophers.rs b/examples/dining_philosophers.rs index 70826ba..1340564 100644 --- a/examples/dining_philosophers.rs +++ b/examples/dining_philosophers.rs @@ -1,6 +1,5 @@ use std::{thread, time::Duration}; -use happylock::collection::RetryingLockCollection; use happylock::{collection::RefLockCollection, Mutex, ThreadKey}; static PHILOSOPHERS: [Philosopher; 5] = [ @@ -52,7 +51,7 @@ impl Philosopher { // safety: no philosopher asks for the same fork twice let forks = [&FORKS[self.left], &FORKS[self.right]]; - let forks = unsafe { RetryingLockCollection::new_unchecked(&forks) }; + let forks = unsafe { RefLockCollection::new_unchecked(&forks) }; let forks = forks.lock(key); println!("{} is eating...", self.name); thread::sleep(Duration::from_secs(1)); diff --git a/examples/double_mutex.rs b/examples/double_mutex.rs index 882fc46..ea61f0d 100644 --- a/examples/double_mutex.rs +++ b/examples/double_mutex.rs @@ -1,6 +1,5 @@ use std::thread; -use happylock::collection::RetryingLockCollection; use happylock::{collection::RefLockCollection, Mutex, ThreadKey}; const N: usize = 10; @@ -12,7 +11,7 @@ fn main() { for _ in 0..N { let th = thread::spawn(move || { let key = ThreadKey::get().unwrap(); - let lock = RetryingLockCollection::new_ref(&DATA); + let lock = RefLockCollection::new(&DATA); let mut guard = lock.lock(key); *guard.1 = (100 - *guard.0).to_string(); *guard.0 += 1; diff --git a/src/collection.rs b/src/collection.rs index a84c1ce..c51e3cf 100644 --- a/src/collection.rs +++ b/src/collection.rs @@ -1,6 +1,6 @@ use std::marker::PhantomData; -use crate::{key::Keyable, lockable::Lock}; +use crate::{key::Keyable, lockable::RawLock}; mod boxed; mod guard; @@ -8,25 +8,95 @@ mod owned; mod r#ref; mod retry; +/// Locks a collection of locks, which cannot be shared immutably. +/// +/// This could be a tuple of [`Lockable`] types, an array, or a `Vec`. But it +/// can be safely locked without causing a deadlock. +/// +/// The data in this collection is guaranteed to not contain duplicates because +/// `L` must always implement [`OwnedLockable`]. The underlying data may not be +/// immutably referenced and locked. Because of this, there is no need for +/// sorting the locks in the collection, or checking for duplicates, because it +/// can be guaranteed that until the underlying collection is mutated (which +/// requires releasing all acquired locks in the collection to do), then the +/// locks will stay in the same order and be locked in that order, preventing +/// cyclic wait. +/// +/// [`Lockable`]: `crate::lockable::Lockable` +/// [`OwnedLockable`]: `crate::lockable::OwnedLockable` #[derive(Debug)] pub struct OwnedLockCollection { data: L, } -/// A type which can be locked. +/// Locks a reference to a collection of locks, by sorting them by memory +/// address. /// /// This could be a tuple of [`Lockable`] types, an array, or a `Vec`. But it /// can be safely locked without causing a deadlock. +/// +/// Upon construction, it must be confirmed that the collection contains no +/// duplicate locks. This can be done by either using [`OwnedLockable`] or by +/// checking. Regardless of how this is done, the locks will be sorted by their +/// memory address before locking them. The sorted order of the locks is stored +/// within this collection. +/// +/// Unlike [`BoxedLockCollection`], this type does not allocate memory for the +/// data, although it does allocate memory for the sorted list of lock +/// references. This makes it slightly faster, but lifetimes must be handled. +/// +/// [`Lockable`]: `crate::lockable::Lockable` +/// [`OwnedLockable`]: `crate::lockable::OwnedLockable` pub struct RefLockCollection<'a, L> { data: &'a L, - locks: Vec<&'a dyn Lock>, + locks: Vec<&'a dyn RawLock>, } +/// Locks a collection of locks, stored in the heap, by sorting them by memory +/// address. +/// +/// This could be a tuple of [`Lockable`] types, an array, or a `Vec`. But it +/// can be safely locked without causing a deadlock. +/// +/// Upon construction, it must be confirmed that the collection contains no +/// duplicate locks. This can be done by either using [`OwnedLockable`] or by +/// checking. Regardless of how this is done, the locks will be sorted by their +/// memory address before locking them. The sorted order of the locks is stored +/// within this collection. +/// +/// Unlike [`RefLockCollection`], this is a self-referential type which boxes +/// the data that is given to it. This means no lifetimes are necessary on the +/// type itself, but it is slightly slower because of the memory allocation. +/// +/// [`Lockable`]: `crate::lockable::Lockable` +/// [`OwnedLockable`]: `crate::lockable::OwnedLockable` pub struct BoxedLockCollection { data: Box, - locks: Vec<&'static dyn Lock>, + locks: Vec<&'static dyn RawLock>, } +/// Locks a collection of locks using a retrying algorithm. +/// +/// This could be a tuple of [`Lockable`] types, an array, or a `Vec`. But it +/// can be safely locked without causing a deadlock. +/// +/// The data in this collection is guaranteed to not contain duplicates, but it +/// also not be sorted. In some cases the lack of sorting can increase +/// performance. However, in most cases, this collection will be slower. Cyclic +/// wait is not guaranteed here, so the locking algorithm must release all its +/// locks if one of the lock attempts blocks. This results in wasted time and +/// potential [livelocking]. +/// +/// However, one case where this might be faster than [`RefLockCollection`] is +/// when the first lock in the collection is always the first in any +/// collection, and the other locks in the collection are always locked after +/// that first lock is acquired. This means that as soon as it is locked, there +/// will be no need to unlock it later on subsequent lock attempts, because +/// they will always succeed. +/// +/// [`Lockable`]: `crate::lockable::Lockable` +/// [`OwnedLockable`]: `crate::lockable::OwnedLockable` +/// [livelocking]: https://en.wikipedia.org/wiki/Deadlock#Livelock #[derive(Debug)] pub struct RetryingLockCollection { data: L, diff --git a/src/collection/boxed.rs b/src/collection/boxed.rs index a62a33d..ea840ab 100644 --- a/src/collection/boxed.rs +++ b/src/collection/boxed.rs @@ -1,14 +1,14 @@ use std::fmt::Debug; use std::marker::PhantomData; -use crate::lockable::Lock; -use crate::{Keyable, Lockable, OwnedLockable, Sharable}; +use crate::lockable::{Lockable, OwnedLockable, RawLock, Sharable}; +use crate::Keyable; use super::{BoxedLockCollection, LockGuard}; /// returns `true` if the sorted list contains a duplicate #[must_use] -fn contains_duplicates(l: &[&dyn Lock]) -> bool { +fn contains_duplicates(l: &[&dyn RawLock]) -> bool { l.windows(2) .any(|window| std::ptr::eq(window[0], window[1])) } @@ -18,7 +18,7 @@ unsafe impl Lockable for BoxedLockCollection { type ReadGuard<'g> = L::ReadGuard<'g> where Self: 'g; - fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { self.data.get_ptrs(ptrs) } diff --git a/src/collection/owned.rs b/src/collection/owned.rs index eb5e03a..d77d568 100644 --- a/src/collection/owned.rs +++ b/src/collection/owned.rs @@ -1,10 +1,11 @@ use std::marker::PhantomData; -use crate::{lockable::Lock, Keyable, Lockable, OwnedLockable, Sharable}; +use crate::lockable::{Lockable, OwnedLockable, RawLock, Sharable}; +use crate::Keyable; use super::{LockGuard, OwnedLockCollection}; -fn get_locks(data: &L) -> Vec<&dyn Lock> { +fn get_locks(data: &L) -> Vec<&dyn RawLock> { let mut locks = Vec::new(); data.get_ptrs(&mut locks); locks @@ -15,7 +16,7 @@ unsafe impl Lockable for OwnedLockCollection { type ReadGuard<'g> = L::ReadGuard<'g> where Self: 'g; - fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { self.data.get_ptrs(ptrs) } diff --git a/src/collection/ref.rs b/src/collection/ref.rs index 329f0ae..2e2883a 100644 --- a/src/collection/ref.rs +++ b/src/collection/ref.rs @@ -1,12 +1,13 @@ use std::fmt::Debug; use std::marker::PhantomData; -use crate::{key::Keyable, lockable::Lock, Lockable, OwnedLockable, Sharable}; +use crate::lockable::{Lockable, OwnedLockable, RawLock, Sharable}; +use crate::Keyable; use super::{LockGuard, RefLockCollection}; #[must_use] -pub fn get_locks(data: &L) -> Vec<&dyn Lock> { +pub fn get_locks(data: &L) -> Vec<&dyn RawLock> { let mut locks = Vec::new(); data.get_ptrs(&mut locks); locks.sort_by_key(|lock| std::ptr::from_ref(*lock)); @@ -15,7 +16,7 @@ pub fn get_locks(data: &L) -> Vec<&dyn Lock> { /// returns `true` if the sorted list contains a duplicate #[must_use] -fn contains_duplicates(l: &[&dyn Lock]) -> bool { +fn contains_duplicates(l: &[&dyn RawLock]) -> bool { l.windows(2) .any(|window| std::ptr::eq(window[0], window[1])) } @@ -43,7 +44,7 @@ unsafe impl<'c, L: Lockable> Lockable for RefLockCollection<'c, L> { type ReadGuard<'g> = L::ReadGuard<'g> where Self: 'g; - fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { ptrs.extend_from_slice(&self.locks); } diff --git a/src/collection/retry.rs b/src/collection/retry.rs index 58a0642..d15d7d6 100644 --- a/src/collection/retry.rs +++ b/src/collection/retry.rs @@ -1,4 +1,6 @@ -use crate::{lockable::Lock, Keyable, Lockable, OwnedLockable, Sharable}; +use crate::lockable::{Lockable, OwnedLockable, RawLock, Sharable}; +use crate::Keyable; + use std::collections::HashSet; use std::marker::PhantomData; @@ -7,7 +9,7 @@ use super::{LockGuard, RetryingLockCollection}; fn contains_duplicates(data: L) -> bool { let mut locks = Vec::new(); data.get_ptrs(&mut locks); - let locks = locks.into_iter().map(|l| l as *const dyn Lock); + let locks = locks.into_iter().map(|l| l as *const dyn RawLock); let mut locks_set = HashSet::new(); for lock in locks { @@ -24,7 +26,7 @@ unsafe impl Lockable for RetryingLockCollection { type ReadGuard<'g> = L::ReadGuard<'g> where Self: 'g; - fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { self.data.get_ptrs(ptrs) } diff --git a/src/lib.rs b/src/lib.rs index 668f3db..673d279 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -107,19 +107,24 @@ //! ``` mod key; -mod lockable; pub mod collection; +pub mod lockable; pub mod mutex; pub mod rwlock; -pub use collection::BoxedLockCollection as LockCollection; pub use key::{Keyable, ThreadKey}; -pub use lockable::{Lockable, OwnedLockable, Sharable}; #[cfg(feature = "spin")] pub use mutex::SpinLock; +/// A collection of locks that can be acquired simultaneously. +/// +/// This re-exports [`BoxedLockCollection`] as a sensible default. +/// +/// [`BoxedLockCollection`]: collection::BoxedLockCollection +pub type LockCollection = collection::BoxedLockCollection; + /// A mutual exclusion primitive useful for protecting shared data, which cannot deadlock. /// /// By default, this uses `parking_lot` as a backend. diff --git a/src/lockable.rs b/src/lockable.rs index 23aeb4c..2f98d3a 100644 --- a/src/lockable.rs +++ b/src/lockable.rs @@ -7,14 +7,14 @@ use crate::{ use lock_api::{RawMutex, RawRwLock}; -/// A type that may be locked and unlocked +/// A raw lock type that may be locked and unlocked /// /// # Safety /// /// A deadlock must never occur. The `unlock` method must correctly unlock the /// data. The `get_ptrs` method must be implemented correctly. The `Output` /// must be unlocked when it is dropped. -pub unsafe trait Lock: Send + Sync { +pub unsafe trait RawLock: Send + Sync { /// Blocks until the lock is acquired /// /// # Safety @@ -46,32 +46,111 @@ pub unsafe trait Lock: Send + Sync { /// It is undefined behavior to use this if the lock is not acquired unsafe fn unlock(&self); + /// Blocks until the data the lock protects can be safely read. + /// + /// Some locks, but not all, will allow multiple readers at once. If + /// multiple readers are allowed for a [`Lockable`] type, then the + /// [`Sharable`] marker trait should be implemented. + /// + /// # Safety + /// + /// It is undefined behavior to use this without ownership or mutable + /// access to the [`ThreadKey`], which should last as long as the return + /// value is alive. + /// + /// [`ThreadKey`]: `crate::ThreadKey` unsafe fn read(&self); + // Attempt to read without blocking. + /// + /// Returns `true` if successful, `false` otherwise. + /// + /// Some locks, but not all, will allow multiple readers at once. If + /// multiple readers are allowed for a [`Lockable`] type, then the + /// [`Sharable`] marker trait should be implemented. + /// + /// # Safety + /// + /// It is undefined behavior to use this without ownership or mutable + /// access to the [`ThreadKey`], which should last as long as the return + /// value is alive. + /// + /// [`ThreadKey`]: `crate::ThreadKey` unsafe fn try_read(&self) -> bool; + /// Releases the lock after calling `read`. + /// + /// # Safety + /// + /// It is undefined behavior to use this if the read lock is not acquired unsafe fn unlock_read(&self); } +/// A type that may be locked and unlocked. +/// +/// This trait is usually implemented on collections of [`RawLock`]s. For +/// example, a `Vec>`. +/// +/// # Safety +/// +/// Acquiring the locks returned by `get_ptrs` must allow for the values +/// returned by `guard` or `read_guard` to be safely used for exclusive or +/// shared access, respectively. +/// +/// Dropping the `Guard` and `ReadGuard` types must unlock those same locks. +/// +/// The order of the resulting list from `get_ptrs` must be deterministic. As +/// long as the value is not mutated, the references must always be in the same +/// order. pub unsafe trait Lockable { - /// The guard returned that does not hold a key + /// The exclusive guard that does not hold a key type Guard<'g> where Self: 'g; + /// The shared guard type that does not hold a key type ReadGuard<'g> where Self: 'g; - fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>); + /// Yields a list of references to the [`RawLock`]s contained within this + /// value. + /// + /// These reference locks which must be locked before acquiring a guard, + /// and unlocked when the guard is dropped. The order of the resulting list + /// is deterministic. As long as the value is not mutated, the references + /// will always be in the same order. + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>); + /// Returns a guard that can be used to access the underlying data mutably. + /// + /// # Safety + /// + /// All locks given by calling [`Lockable::get_ptrs`] must be locked + /// exclusively before calling this function. The locks must not be + /// unlocked until this guard is dropped. #[must_use] unsafe fn guard(&self) -> Self::Guard<'_>; + /// Returns a guard that can be used to immutably access the underlying + /// data. + /// + /// # Safety + /// + /// All locks given by calling [`Lockable::get_ptrs`] must be locked using + /// [`RawLock::read`] before calling this function. The locks must not be + /// unlocked until this guard is dropped. #[must_use] unsafe fn read_guard(&self) -> Self::ReadGuard<'_>; } +/// A marker trait to indicate that multiple readers can access the lock at a +/// time. +/// +/// # Safety +/// +/// This type must only be implemented if the lock can be safely shared between +/// multiple readers. pub unsafe trait Sharable: Lockable {} /// A type that may be locked and unlocked, and is known to be the only valid @@ -83,7 +162,7 @@ pub unsafe trait Sharable: Lockable {} /// time, i.e., this must either be an owned value or a mutable reference. pub unsafe trait OwnedLockable: Lockable {} -unsafe impl Lock for Mutex { +unsafe impl RawLock for Mutex { unsafe fn lock(&self) { self.raw().lock() } @@ -109,7 +188,7 @@ unsafe impl Lock for Mutex { } } -unsafe impl Lock for RwLock { +unsafe impl RawLock for RwLock { unsafe fn lock(&self) { self.raw().lock_exclusive() } @@ -139,7 +218,7 @@ unsafe impl Lockable for Mutex { type Guard<'g> = MutexRef<'g, T, R> where Self: 'g; type ReadGuard<'g> = MutexRef<'g, T, R> where Self: 'g; - fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { ptrs.push(self); } @@ -157,7 +236,7 @@ unsafe impl Lockable for RwLock { type ReadGuard<'g> = RwLockReadRef<'g, T, R> where Self: 'g; - fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { ptrs.push(self); } @@ -181,7 +260,7 @@ unsafe impl<'l, T: Send, R: RawRwLock + Send + Sync> Lockable for ReadLock<'l, T type ReadGuard<'g> = RwLockReadRef<'g, T, R> where Self: 'g; - fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { ptrs.push(self.as_ref()); } @@ -199,7 +278,7 @@ unsafe impl<'l, T: Send, R: RawRwLock + Send + Sync> Lockable for WriteLock<'l, type ReadGuard<'g> = RwLockWriteRef<'g, T, R> where Self: 'g; - fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { ptrs.push(self.as_ref()); } @@ -219,7 +298,7 @@ unsafe impl Lockable for &T { type ReadGuard<'g> = T::ReadGuard<'g> where Self: 'g; - fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { (*self).get_ptrs(ptrs); } @@ -237,7 +316,7 @@ unsafe impl Lockable for &mut T { type ReadGuard<'g> = T::ReadGuard<'g> where Self: 'g; - fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { (**self).get_ptrs(ptrs) } @@ -257,7 +336,7 @@ unsafe impl Lockable for (A,) { type ReadGuard<'g> = (A::ReadGuard<'g>,) where Self: 'g; - fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { self.0.get_ptrs(ptrs); } @@ -275,7 +354,7 @@ unsafe impl Lockable for (A, B) { type ReadGuard<'g> = (A::ReadGuard<'g>, B::ReadGuard<'g>) where Self: 'g; - fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { self.0.get_ptrs(ptrs); self.1.get_ptrs(ptrs); } @@ -294,7 +373,7 @@ unsafe impl Lockable for (A, B, C) { type ReadGuard<'g> = (A::ReadGuard<'g>, B::ReadGuard<'g>, C::ReadGuard<'g>) where Self: 'g; - fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { self.0.get_ptrs(ptrs); self.1.get_ptrs(ptrs); self.2.get_ptrs(ptrs); @@ -323,7 +402,7 @@ unsafe impl Lockable for (A, D::ReadGuard<'g>, ) where Self: 'g; - fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { self.0.get_ptrs(ptrs); self.1.get_ptrs(ptrs); self.2.get_ptrs(ptrs); @@ -368,7 +447,7 @@ unsafe impl Loc E::ReadGuard<'g>, ) where Self: 'g; - fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { self.0.get_ptrs(ptrs); self.1.get_ptrs(ptrs); self.2.get_ptrs(ptrs); @@ -418,7 +497,7 @@ unsafe impl, ) where Self: 'g; - fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { self.0.get_ptrs(ptrs); self.1.get_ptrs(ptrs); self.2.get_ptrs(ptrs); @@ -473,7 +552,7 @@ unsafe impl, ) where Self: 'g; - fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { self.0.get_ptrs(ptrs); self.1.get_ptrs(ptrs); self.2.get_ptrs(ptrs); @@ -573,7 +652,7 @@ unsafe impl Lockable for [T; N] { type ReadGuard<'g> = [T::ReadGuard<'g>; N] where Self: 'g; - fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { for lock in self { lock.get_ptrs(ptrs); } @@ -603,7 +682,7 @@ unsafe impl Lockable for Box<[T]> { type ReadGuard<'g> = Box<[T::ReadGuard<'g>]> where Self: 'g; - fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { for lock in self.iter() { lock.get_ptrs(ptrs); } @@ -633,7 +712,7 @@ unsafe impl Lockable for Vec { type ReadGuard<'g> = Box<[T::ReadGuard<'g>]> where Self: 'g; - fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { for lock in self { lock.get_ptrs(ptrs); } -- cgit v1.2.3 From 046c93cbea3236b7adf9e473d299345ee985cbb2 Mon Sep 17 00:00:00 2001 From: Botahamec Date: Thu, 23 May 2024 19:54:38 -0400 Subject: Another dining philosophers test --- examples/dining_philosophers.rs | 4 +- examples/dining_philosophers_retry.rs | 75 +++++++++++++++++++++++++++++++++++ 2 files changed, 77 insertions(+), 2 deletions(-) create mode 100644 examples/dining_philosophers_retry.rs (limited to 'examples/dining_philosophers.rs') diff --git a/examples/dining_philosophers.rs b/examples/dining_philosophers.rs index 1340564..dc4dd51 100644 --- a/examples/dining_philosophers.rs +++ b/examples/dining_philosophers.rs @@ -1,6 +1,6 @@ use std::{thread, time::Duration}; -use happylock::{collection::RefLockCollection, Mutex, ThreadKey}; +use happylock::{collection, Mutex, ThreadKey}; static PHILOSOPHERS: [Philosopher; 5] = [ Philosopher { @@ -51,7 +51,7 @@ impl Philosopher { // safety: no philosopher asks for the same fork twice let forks = [&FORKS[self.left], &FORKS[self.right]]; - let forks = unsafe { RefLockCollection::new_unchecked(&forks) }; + let forks = unsafe { collection::RefLockCollection::new_unchecked(&forks) }; let forks = forks.lock(key); println!("{} is eating...", self.name); thread::sleep(Duration::from_secs(1)); diff --git a/examples/dining_philosophers_retry.rs b/examples/dining_philosophers_retry.rs new file mode 100644 index 0000000..4302bc7 --- /dev/null +++ b/examples/dining_philosophers_retry.rs @@ -0,0 +1,75 @@ +use std::{thread, time::Duration}; + +use happylock::{collection, Mutex, ThreadKey}; + +static PHILOSOPHERS: [Philosopher; 5] = [ + Philosopher { + name: "Socrates", + left: 0, + right: 1, + }, + Philosopher { + name: "John Rawls", + left: 1, + right: 2, + }, + Philosopher { + name: "Jeremy Bentham", + left: 2, + right: 3, + }, + Philosopher { + name: "John Stuart Mill", + left: 3, + right: 4, + }, + Philosopher { + name: "Judith Butler", + left: 4, + right: 0, + }, +]; + +static FORKS: [Mutex<()>; 5] = [ + Mutex::new(()), + Mutex::new(()), + Mutex::new(()), + Mutex::new(()), + Mutex::new(()), +]; + +struct Philosopher { + name: &'static str, + left: usize, + right: usize, +} + +impl Philosopher { + fn cycle(&self) { + let key = ThreadKey::get().unwrap(); + thread::sleep(Duration::from_secs(1)); + + // safety: no philosopher asks for the same fork twice + let forks = [&FORKS[self.left], &FORKS[self.right]]; + let forks = unsafe { collection::RetryingLockCollection::new_unchecked(&forks) }; + let forks = forks.lock(key); + println!("{} is eating...", self.name); + thread::sleep(Duration::from_secs(1)); + println!("{} is done eating", self.name); + drop(forks); + } +} + +fn main() { + let handles: Vec<_> = PHILOSOPHERS + .iter() + .map(|philosopher| thread::spawn(move || philosopher.cycle())) + // The `collect` is absolutely necessary, because we're using lazy + // iterators. If `collect` isn't used, then the thread won't spawn + // until we try to join on it. + .collect(); + + for handle in handles { + _ = handle.join(); + } +} -- cgit v1.2.3