From 801a870467af4059d2abdc67f2899edebb1f6d6c Mon Sep 17 00:00:00 2001 From: Mica White Date: Sat, 16 Mar 2024 12:41:27 -0400 Subject: retry lock collection --- src/collection.rs | 11 +- src/collection/boxed_collection.rs | 10 +- src/collection/guard.rs | 6 +- src/collection/owned_collection.rs | 11 +- src/collection/ref_collection.rs | 12 +- src/collection/retry_collection.rs | 138 +++++++++++++++++++ src/lockable.rs | 274 ++++++++++++++++++------------------- 7 files changed, 295 insertions(+), 167 deletions(-) create mode 100644 src/collection/retry_collection.rs (limited to 'src') diff --git a/src/collection.rs b/src/collection.rs index 93adf16..d9c56d3 100644 --- a/src/collection.rs +++ b/src/collection.rs @@ -1,4 +1,4 @@ -use std::{marker::PhantomData, ptr::NonNull}; +use std::{marker::PhantomData}; use crate::{ key::Keyable, @@ -9,6 +9,7 @@ mod boxed_collection; mod guard; mod owned_collection; mod ref_collection; +mod retry_collection; pub struct OwnedLockCollection { data: L, @@ -25,9 +26,13 @@ pub struct RefLockCollection<'a, L> { pub struct BoxedLockCollection<'a, L>(RefLockCollection<'a, L>); +pub struct RetryingLockCollection { + data: L, +} + /// A RAII guard for a generic [`Lockable`] type. -pub struct LockGuard<'a, 'key: 'a, L: Lockable<'a>, Key: Keyable + 'key> { - guard: L::Guard, +pub struct LockGuard<'g, 'key: 'g, L: Lockable + 'g, Key: Keyable + 'key> { + guard: L::Guard<'g>, key: Key, _phantom: PhantomData<&'key ()>, } diff --git a/src/collection/boxed_collection.rs b/src/collection/boxed_collection.rs index bcb941b..1aae1e4 100644 --- a/src/collection/boxed_collection.rs +++ b/src/collection/boxed_collection.rs @@ -26,7 +26,7 @@ impl<'a, L> Drop for BoxedLockCollection<'a, L> { } } -impl<'a, L: OwnedLockable<'a> + 'a> BoxedLockCollection<'a, L> { +impl<'a, L: OwnedLockable> BoxedLockCollection<'a, L> { #[must_use] pub fn new(data: L) -> Self { let boxed = Box::leak(Box::new(data)); @@ -34,18 +34,18 @@ impl<'a, L: OwnedLockable<'a> + 'a> BoxedLockCollection<'a, L> { } } -impl<'a, L: OwnedLockable<'a> + 'a> BoxedLockCollection<'a, &'a L> { +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)); - // this is a reference to an OwnedLockable, which can't possibly - // contain inner duplicates + // 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> + 'a> BoxedLockCollection<'a, L> { +impl<'a, L: Lockable> BoxedLockCollection<'a, L> { #[must_use] pub unsafe fn new_unchecked(data: L) -> Self { let boxed = Box::leak(Box::new(data)); diff --git a/src/collection/guard.rs b/src/collection/guard.rs index 3b98d29..e3ffb21 100644 --- a/src/collection/guard.rs +++ b/src/collection/guard.rs @@ -4,15 +4,15 @@ use crate::{key::Keyable, Lockable}; use super::LockGuard; -impl<'a, 'key: 'a, L: Lockable<'a>, Key: Keyable> Deref for LockGuard<'a, 'key, L, Key> { - type Target = L::Guard; +impl<'a, 'key: 'a, L: Lockable + 'a, Key: Keyable> Deref for LockGuard<'a, 'key, L, Key> { + type Target = L::Guard<'a>; fn deref(&self) -> &Self::Target { &self.guard } } -impl<'a, 'key: 'a, L: Lockable<'a>, Key: Keyable> DerefMut for LockGuard<'a, 'key, L, Key> { +impl<'a, 'key: 'a, L: Lockable + 'a, Key: Keyable> DerefMut for LockGuard<'a, 'key, L, Key> { fn deref_mut(&mut self) -> &mut Self::Target { &mut self.guard } diff --git a/src/collection/owned_collection.rs b/src/collection/owned_collection.rs index dbc9a45..ea8f2f2 100644 --- a/src/collection/owned_collection.rs +++ b/src/collection/owned_collection.rs @@ -4,22 +4,19 @@ 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> { +fn get_locks(data: &L) -> Vec<&dyn Lock> { let mut locks = Vec::new(); data.get_ptrs(&mut locks); locks } -impl<'a, L: OwnedLockable<'a>> OwnedLockCollection { +impl 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> { + 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 @@ -36,7 +33,7 @@ impl<'a, L: OwnedLockable<'a>> OwnedLockCollection { } } - pub fn try_lock<'key: 'a, Key: Keyable + 'key>( + pub fn try_lock<'a, 'key: 'a, Key: Keyable + 'key>( &'a self, key: Key, ) -> Option> { diff --git a/src/collection/ref_collection.rs b/src/collection/ref_collection.rs index 3e4d5f8..2462182 100644 --- a/src/collection/ref_collection.rs +++ b/src/collection/ref_collection.rs @@ -5,7 +5,7 @@ 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> { +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)); @@ -20,19 +20,19 @@ fn contains_duplicates(l: &[&dyn Lock]) -> bool { }) } -impl<'a, L: Lockable<'a>> AsRef for RefLockCollection<'a, L> { +impl<'a, L: Lockable> AsRef for RefLockCollection<'a, L> { fn as_ref(&self) -> &L { self.data } } -impl<'a, L: Lockable<'a>> AsRef for RefLockCollection<'a, L> { +impl<'a, L: Lockable> AsRef for RefLockCollection<'a, L> { fn as_ref(&self) -> &Self { self } } -impl<'a, L: Lockable<'a>> AsMut for RefLockCollection<'a, L> { +impl<'a, L: Lockable> AsMut for RefLockCollection<'a, L> { fn as_mut(&mut self) -> &mut Self { self } @@ -50,7 +50,7 @@ where } } -impl<'a, L: OwnedLockable<'a> + 'a> RefLockCollection<'a, 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 @@ -73,7 +73,7 @@ impl<'a, L: OwnedLockable<'a> + 'a> RefLockCollection<'a, L> { } } -impl<'a, L: Lockable<'a>> RefLockCollection<'a, L> { +impl<'a, L: Lockable> RefLockCollection<'a, L> { /// Creates a new collections of locks. /// /// # Safety diff --git a/src/collection/retry_collection.rs b/src/collection/retry_collection.rs new file mode 100644 index 0000000..73f9e18 --- /dev/null +++ b/src/collection/retry_collection.rs @@ -0,0 +1,138 @@ +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/lockable.rs b/src/lockable.rs index a09b84b..fe14e8c 100644 --- a/src/lockable.rs +++ b/src/lockable.rs @@ -47,14 +47,16 @@ pub unsafe trait Lock: Send + Sync { unsafe fn unlock(&self); } -pub unsafe trait Lockable<'a> { +pub unsafe trait Lockable { /// The guard returned that does not hold a key - type Guard; + type Guard<'g> + where + Self: 'g; - fn get_ptrs(&'a self, ptrs: &mut Vec<&'a dyn Lock>); + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>); #[must_use] - unsafe fn guard(&'a self) -> Self::Guard; + unsafe fn guard(&self) -> Self::Guard<'_>; } /// A type that may be locked and unlocked, and is known to be the only valid @@ -64,7 +66,7 @@ pub unsafe trait Lockable<'a> { /// /// There must not be any two values which can unlock the value at the same /// time, i.e., this must either be an owned value or a mutable reference. -pub unsafe trait OwnedLockable<'a>: Lockable<'a> {} +pub unsafe trait OwnedLockable: Lockable {} unsafe impl Lock for Mutex { unsafe fn lock(&self) { @@ -94,138 +96,134 @@ unsafe impl Lock for RwLock { } } -unsafe impl<'a, T: Send + 'a, R: RawMutex + Send + Sync + 'a> Lockable<'a> for Mutex { - type Guard = MutexRef<'a, T, R>; +unsafe impl Lockable for Mutex { + type Guard<'g> = MutexRef<'g, T, R> where Self: 'g; - fn get_ptrs(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { ptrs.push(self); } - unsafe fn guard(&'a self) -> Self::Guard { + unsafe fn guard(&self) -> Self::Guard<'_> { MutexRef::new(self) } } -unsafe impl<'a, T: Send + 'a, R: RawRwLock + Send + Sync + 'a> Lockable<'a> for RwLock { - type Guard = RwLockWriteRef<'a, T, R>; +unsafe impl Lockable for RwLock { + type Guard<'g> = RwLockWriteRef<'g, T, R> where Self: 'g; - fn get_ptrs(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { ptrs.push(self); } - unsafe fn guard(&'a self) -> Self::Guard { + unsafe fn guard(&self) -> Self::Guard<'_> { RwLockWriteRef::new(self) } } -unsafe impl<'a, T: Send + 'a, R: RawMutex + Send + Sync + 'a> OwnedLockable<'a> for Mutex {} +unsafe impl OwnedLockable for Mutex {} -unsafe impl<'a, T: Send + 'a, R: RawRwLock + Send + Sync + 'a> OwnedLockable<'a> for RwLock {} +unsafe impl OwnedLockable for RwLock {} -unsafe impl<'a, T: Send + 'a, R: RawRwLock + Send + Sync + 'a> Lockable<'a> for ReadLock<'a, T, R> { - type Guard = RwLockReadRef<'a, T, R>; +unsafe impl<'r, T: Send + 'r, R: RawRwLock + Send + Sync + 'r> Lockable for ReadLock<'r, T, R> { + type Guard<'g> = RwLockReadRef<'g, T, R> where Self: 'g; - fn get_ptrs(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { ptrs.push(self.as_ref()); } - unsafe fn guard(&'a self) -> Self::Guard { + unsafe fn guard(&self) -> Self::Guard<'_> { RwLockReadRef::new(self.as_ref()) } } -unsafe impl<'a, T: Send + 'a, R: RawRwLock + Send + Sync + 'a> Lockable<'a> - for WriteLock<'a, T, R> -{ - type Guard = RwLockWriteRef<'a, T, R>; +unsafe impl<'r, T: Send + 'r, R: RawRwLock + Send + Sync + 'r> Lockable for WriteLock<'r, T, R> { + type Guard<'g> = RwLockWriteRef<'g, T, R> where Self: 'g; - fn get_ptrs(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { ptrs.push(self.as_ref()); } - unsafe fn guard(&'a self) -> Self::Guard { + unsafe fn guard(&self) -> Self::Guard<'_> { RwLockWriteRef::new(self.as_ref()) } } -unsafe impl<'a, T: Lockable<'a>> Lockable<'a> for &'a T { - type Guard = T::Guard; +unsafe impl Lockable for &T { + type Guard<'g> = T::Guard<'g> where Self: 'g; - fn get_ptrs(&self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { (*self).get_ptrs(ptrs); } - unsafe fn guard(&self) -> Self::Guard { + unsafe fn guard(&self) -> Self::Guard<'_> { (*self).guard() } } -unsafe impl<'a, T: Lockable<'a>> Lockable<'a> for &mut T { - type Guard = T::Guard; +unsafe impl Lockable for &mut T { + type Guard<'g> = T::Guard<'g> where Self: 'g; - fn get_ptrs(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { (**self).get_ptrs(ptrs) } - unsafe fn guard(&'a self) -> Self::Guard { + unsafe fn guard(&self) -> Self::Guard<'_> { (**self).guard() } } -unsafe impl<'a, T: OwnedLockable<'a>> OwnedLockable<'a> for &mut T {} +unsafe impl OwnedLockable for &mut T {} -unsafe impl<'a, A: Lockable<'a>> Lockable<'a> for (A,) { - type Guard = (A::Guard,); +unsafe impl Lockable for (A,) { + type Guard<'g> = (A::Guard<'g>,) where Self: 'g; - fn get_ptrs(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { self.0.get_ptrs(ptrs); } - unsafe fn guard(&'a self) -> Self::Guard { + unsafe fn guard(&self) -> Self::Guard<'_> { (self.0.guard(),) } } -unsafe impl<'a, A: Lockable<'a>, B: Lockable<'a>> Lockable<'a> for (A, B) { - type Guard = (A::Guard, B::Guard); +unsafe impl Lockable for (A, B) { + type Guard<'g> = (A::Guard<'g>, B::Guard<'g>) where Self: 'g; - fn get_ptrs(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { self.0.get_ptrs(ptrs); self.1.get_ptrs(ptrs); } - unsafe fn guard(&'a self) -> Self::Guard { + unsafe fn guard(&self) -> Self::Guard<'_> { (self.0.guard(), self.1.guard()) } } -unsafe impl<'a, A: Lockable<'a>, B: Lockable<'a>, C: Lockable<'a>> Lockable<'a> for (A, B, C) { - type Guard = (A::Guard, B::Guard, C::Guard); +unsafe impl Lockable for (A, B, C) { + type Guard<'g> = (A::Guard<'g>, B::Guard<'g>, C::Guard<'g>) where Self: 'g; - fn get_ptrs(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { self.0.get_ptrs(ptrs); self.1.get_ptrs(ptrs); self.2.get_ptrs(ptrs); } - unsafe fn guard(&'a self) -> Self::Guard { + unsafe fn guard(&self) -> Self::Guard<'_> { (self.0.guard(), self.1.guard(), self.2.guard()) } } -unsafe impl<'a, A: Lockable<'a>, B: Lockable<'a>, C: Lockable<'a>, D: Lockable<'a>> Lockable<'a> - for (A, B, C, D) -{ - type Guard = (A::Guard, B::Guard, C::Guard, D::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; - fn get_ptrs(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { self.0.get_ptrs(ptrs); self.1.get_ptrs(ptrs); self.2.get_ptrs(ptrs); self.3.get_ptrs(ptrs); } - unsafe fn guard(&'a self) -> Self::Guard { + unsafe fn guard(&self) -> Self::Guard<'_> { ( self.0.guard(), self.1.guard(), @@ -235,12 +233,18 @@ unsafe impl<'a, A: Lockable<'a>, B: Lockable<'a>, C: Lockable<'a>, D: Lockable<' } } -unsafe impl<'a, A: Lockable<'a>, B: Lockable<'a>, C: Lockable<'a>, D: Lockable<'a>, E: Lockable<'a>> - Lockable<'a> for (A, B, C, D, E) +unsafe impl Lockable + for (A, B, C, D, E) { - type Guard = (A::Guard, B::Guard, C::Guard, D::Guard, E::Guard); - - fn get_ptrs(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + type Guard<'g> = ( + A::Guard<'g>, + B::Guard<'g>, + C::Guard<'g>, + D::Guard<'g>, + E::Guard<'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); self.2.get_ptrs(ptrs); @@ -248,7 +252,7 @@ unsafe impl<'a, A: Lockable<'a>, B: Lockable<'a>, C: Lockable<'a>, D: Lockable<' self.4.get_ptrs(ptrs); } - unsafe fn guard(&'a self) -> Self::Guard { + unsafe fn guard(&self) -> Self::Guard<'_> { ( self.0.guard(), self.1.guard(), @@ -259,19 +263,19 @@ unsafe impl<'a, A: Lockable<'a>, B: Lockable<'a>, C: Lockable<'a>, D: Lockable<' } } -unsafe impl< - 'a, - A: Lockable<'a>, - B: Lockable<'a>, - C: Lockable<'a>, - D: Lockable<'a>, - E: Lockable<'a>, - F: Lockable<'a>, - > Lockable<'a> for (A, B, C, D, E, F) +unsafe impl Lockable + for (A, B, C, D, E, F) { - type Guard = (A::Guard, B::Guard, C::Guard, D::Guard, E::Guard, F::Guard); - - fn get_ptrs(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + type Guard<'g> = ( + A::Guard<'g>, + B::Guard<'g>, + C::Guard<'g>, + D::Guard<'g>, + E::Guard<'g>, + F::Guard<'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); self.2.get_ptrs(ptrs); @@ -280,7 +284,7 @@ unsafe impl< self.5.get_ptrs(ptrs); } - unsafe fn guard(&'a self) -> Self::Guard { + unsafe fn guard(&self) -> Self::Guard<'_> { ( self.0.guard(), self.1.guard(), @@ -292,28 +296,20 @@ unsafe impl< } } -unsafe impl< - 'a, - A: Lockable<'a>, - B: Lockable<'a>, - C: Lockable<'a>, - D: Lockable<'a>, - E: Lockable<'a>, - F: Lockable<'a>, - G: Lockable<'a>, - > Lockable<'a> for (A, B, C, D, E, F, G) +unsafe impl + Lockable for (A, B, C, D, E, F, G) { - type Guard = ( - A::Guard, - B::Guard, - C::Guard, - D::Guard, - E::Guard, - F::Guard, - G::Guard, - ); - - fn get_ptrs(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + type Guard<'g> = ( + A::Guard<'g>, + B::Guard<'g>, + C::Guard<'g>, + D::Guard<'g>, + E::Guard<'g>, + F::Guard<'g>, + G::Guard<'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); self.2.get_ptrs(ptrs); @@ -323,7 +319,7 @@ unsafe impl< self.6.get_ptrs(ptrs); } - unsafe fn guard(&'a self) -> Self::Guard { + unsafe fn guard(&self) -> Self::Guard<'_> { ( self.0.guard(), self.1.guard(), @@ -336,71 +332,63 @@ unsafe impl< } } -unsafe impl<'a, A: OwnedLockable<'a>> OwnedLockable<'a> for (A,) {} -unsafe impl<'a, A: OwnedLockable<'a>, B: OwnedLockable<'a>> OwnedLockable<'a> for (A, B) {} +unsafe impl OwnedLockable for (A,) {} +unsafe impl OwnedLockable for (A, B) {} -unsafe impl<'a, A: OwnedLockable<'a>, B: OwnedLockable<'a>, C: OwnedLockable<'a>> OwnedLockable<'a> - for (A, B, C) -{ -} +unsafe impl OwnedLockable for (A, B, C) {} -unsafe impl< - 'a, - A: OwnedLockable<'a>, - B: OwnedLockable<'a>, - C: OwnedLockable<'a>, - D: OwnedLockable<'a>, - > OwnedLockable<'a> for (A, B, C, D) +unsafe impl OwnedLockable + for (A, B, C, D) { } unsafe impl< 'a, - A: OwnedLockable<'a>, - B: OwnedLockable<'a>, - C: OwnedLockable<'a>, - D: OwnedLockable<'a>, - E: OwnedLockable<'a>, - > OwnedLockable<'a> for (A, B, C, D, E) + A: OwnedLockable, + B: OwnedLockable, + C: OwnedLockable, + D: OwnedLockable, + E: OwnedLockable, + > OwnedLockable for (A, B, C, D, E) { } unsafe impl< 'a, - A: OwnedLockable<'a>, - B: OwnedLockable<'a>, - C: OwnedLockable<'a>, - D: OwnedLockable<'a>, - E: OwnedLockable<'a>, - F: OwnedLockable<'a>, - > OwnedLockable<'a> for (A, B, C, D, E, F) + A: OwnedLockable, + B: OwnedLockable, + C: OwnedLockable, + D: OwnedLockable, + E: OwnedLockable, + F: OwnedLockable, + > OwnedLockable for (A, B, C, D, E, F) { } unsafe impl< 'a, - A: OwnedLockable<'a>, - B: OwnedLockable<'a>, - C: OwnedLockable<'a>, - D: OwnedLockable<'a>, - E: OwnedLockable<'a>, - F: OwnedLockable<'a>, - G: OwnedLockable<'a>, - > OwnedLockable<'a> for (A, B, C, D, E, F, G) + A: OwnedLockable, + B: OwnedLockable, + C: OwnedLockable, + D: OwnedLockable, + E: OwnedLockable, + F: OwnedLockable, + G: OwnedLockable, + > OwnedLockable for (A, B, C, D, E, F, G) { } -unsafe impl<'a, T: Lockable<'a>, const N: usize> Lockable<'a> for [T; N] { - type Guard = [T::Guard; N]; +unsafe impl Lockable for [T; N] { + type Guard<'g> = [T::Guard<'g>; N] where Self: 'g; - fn get_ptrs(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { for lock in self { lock.get_ptrs(ptrs); } } - unsafe fn guard(&'a self) -> Self::Guard { - let mut guards = MaybeUninit::<[MaybeUninit; N]>::uninit().assume_init(); + unsafe fn guard<'g>(&'g self) -> Self::Guard<'g> { + let mut guards = MaybeUninit::<[MaybeUninit>; N]>::uninit().assume_init(); for i in 0..N { guards[i].write(self[i].guard()); } @@ -409,16 +397,16 @@ unsafe impl<'a, T: Lockable<'a>, const N: usize> Lockable<'a> for [T; N] { } } -unsafe impl<'a, T: Lockable<'a>> Lockable<'a> for Box<[T]> { - type Guard = Box<[T::Guard]>; +unsafe impl Lockable for Box<[T]> { + type Guard<'g> = Box<[T::Guard<'g>]> where Self: 'g; - fn get_ptrs(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { for lock in self.iter() { lock.get_ptrs(ptrs); } } - unsafe fn guard(&'a self) -> Self::Guard { + unsafe fn guard(&self) -> Self::Guard<'_> { let mut guards = Vec::new(); for lock in self.iter() { guards.push(lock.guard()); @@ -428,16 +416,16 @@ unsafe impl<'a, T: Lockable<'a>> Lockable<'a> for Box<[T]> { } } -unsafe impl<'a, T: Lockable<'a>> Lockable<'a> for Vec { - type Guard = Vec; +unsafe impl Lockable for Vec { + type Guard<'g> = Vec> where Self: 'g; - fn get_ptrs(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { for lock in self { lock.get_ptrs(ptrs); } } - unsafe fn guard(&'a self) -> Self::Guard { + unsafe fn guard(&self) -> Self::Guard<'_> { let mut guards = Vec::new(); for lock in self { guards.push(lock.guard()); @@ -447,6 +435,6 @@ unsafe impl<'a, T: Lockable<'a>> Lockable<'a> for Vec { } } -unsafe impl<'a, T: OwnedLockable<'a>, const N: usize> OwnedLockable<'a> for [T; N] {} -unsafe impl<'a, T: OwnedLockable<'a>> OwnedLockable<'a> for Box<[T]> {} -unsafe impl<'a, T: OwnedLockable<'a>> OwnedLockable<'a> for Vec {} +unsafe impl OwnedLockable for [T; N] {} +unsafe impl OwnedLockable for Box<[T]> {} +unsafe impl OwnedLockable for Vec {} -- cgit v1.2.3 From cb28fb1ff3b5ea71c6fe11956015c7285cb3f3df Mon Sep 17 00:00:00 2001 From: Mica White Date: Tue, 21 May 2024 13:17:38 -0400 Subject: read-lock changes --- README.md | 6 +----- src/collection.rs | 2 +- src/lockable.rs | 4 ++-- src/rwlock.rs | 6 ++++-- src/rwlock/read_lock.rs | 16 ++++++++-------- src/rwlock/write_lock.rs | 16 ++++++++-------- 6 files changed, 24 insertions(+), 26 deletions(-) (limited to 'src') diff --git a/README.md b/README.md index 51d8d67..66a4fc0 100644 --- a/README.md +++ b/README.md @@ -73,14 +73,10 @@ println!("{}", *data.1); **Avoid `LockCollection::try_new`.** This constructor will check to make sure that the collection contains no duplicate locks. This is an O(n^2) operation, where n is the number of locks in the collection. `LockCollection::new` and `LockCollection::new_ref` don't need these checks because they use `OwnedLockable`, which is guaranteed to be unique as long as it is accessible. As a last resort, `LockCollection::new_unchecked` doesn't do this check, but is unsafe to call. -**Avoid using distinct lock orders for `LockCollection`.** The problem is that this library must iterate through the list of locks, and not complete until every single one of them is unlocked. This also means that attempting to lock multiple mutexes gives you a lower chance of ever running. Only one needs to be locked for the operation to need a reset. This problem can be prevented by not doing that in your code. Resources should be obtained in the same order on every thread. - -**Avoid tuples in `LockCollection`.** Tuples become spinlocks if the first value is already unlocked. This will be fixed in the future. For now, if you need a tuple, make the lock that is most likely to be locked the first element. +**Avoid using distinct lock orders for `RetryingLockCollection`.** The problem is that this collection must iterate through the list of locks, and not complete until every single one of them is unlocked. This also means that attempting to lock multiple mutexes gives you a lower chance of ever running. Only one needs to be locked for the operation to need a reset. This problem can be prevented by not doing that in your code. Resources should be obtained in the same order on every thread. ## Future Work -Although this library is able to successfully prevent deadlocks, livelocks may still be an issue. Imagine thread 1 gets resource 1, thread 2 gets resource 2, thread 1 realizes it can't get resource 2, thread 2 realizes it can't get resource 1, thread 1 drops resource 1, thread 2 drops resource 2, and then repeat forever. In practice, this situation probably wouldn't last forever. But it would be nice if this could be prevented somehow. A more fair system for getting sets of locks would help, but I have no clue what that looks like. - It might to possible to break the `ThreadKey` system by having two crates import this crate and call `ThreadKey::get`. I'm not quite sure how this works, but Rust could decide to give each crate their own key, ergo one thread would get two keys. I don't think the standard library would have this issue. At a certain point, I have to recognize that someone could also just import the standard library mutex and get a deadlock that way. We should add `Condvar` at some point. I didn't because I've never used it before, and I'm probably not the right person to solve this problem. I think all the synchronization problems could be solved by having `Condvar::wait` take a `ThreadKey` instead of a `MutexGuard`. Something similar can probably be done for `Barrier`. But again, I'm no expert. diff --git a/src/collection.rs b/src/collection.rs index d9c56d3..a11d60c 100644 --- a/src/collection.rs +++ b/src/collection.rs @@ -1,4 +1,4 @@ -use std::{marker::PhantomData}; +use std::marker::PhantomData; use crate::{ key::Keyable, diff --git a/src/lockable.rs b/src/lockable.rs index fe14e8c..a5646e1 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<'r, T: Send + 'r, R: RawRwLock + Send + Sync + 'r> Lockable for ReadLock<'r, T, R> { +unsafe impl Lockable for ReadLock { 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<'r, T: Send + 'r, R: RawRwLock + Send + Sync + 'r> Lockable for Read } } -unsafe impl<'r, T: Send + 'r, R: RawRwLock + Send + Sync + 'r> Lockable for WriteLock<'r, T, R> { +unsafe impl Lockable for WriteLock { type Guard<'g> = RwLockWriteRef<'g, T, R> where Self: 'g; fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { diff --git a/src/rwlock.rs b/src/rwlock.rs index 7fb8c7a..40c5a6e 100644 --- a/src/rwlock.rs +++ b/src/rwlock.rs @@ -56,7 +56,8 @@ pub struct RwLock { /// that only read access is needed to the data. /// /// [`LockCollection`]: `crate::LockCollection` -pub struct ReadLock<'a, T: ?Sized, R>(&'a RwLock); +#[repr(transparent)] +pub struct ReadLock(RwLock); /// Grants write access to an [`RwLock`] /// @@ -64,7 +65,8 @@ pub struct ReadLock<'a, T: ?Sized, R>(&'a RwLock); /// that write access is needed to the data. /// /// [`LockCollection`]: `crate::LockCollection` -pub struct WriteLock<'a, T: ?Sized, R>(&'a RwLock); +#[repr(transparent)] +pub struct WriteLock(RwLock); /// RAII structure that unlocks the shared read access to a [`RwLock`] pub struct RwLockReadRef<'a, T: ?Sized, R: RawRwLock>( diff --git a/src/rwlock/read_lock.rs b/src/rwlock/read_lock.rs index 133ca7d..a8bb9be 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<'a, T: ?Sized + Debug, R: RawRwLock> Debug for ReadLock<'a, T, R> { +impl Debug for ReadLock { 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 @@ -28,19 +28,19 @@ impl<'a, T: ?Sized + Debug, R: RawRwLock> Debug for ReadLock<'a, T, R> { } } -impl<'a, T: ?Sized, R> From<&'a RwLock> for ReadLock<'a, T, R> { - fn from(value: &'a RwLock) -> Self { +impl From> for ReadLock { + fn from(value: RwLock) -> Self { Self::new(value) } } -impl<'a, T: ?Sized, R> AsRef> for ReadLock<'a, T, R> { +impl AsRef> for ReadLock { fn as_ref(&self) -> &RwLock { - self.0 + &self.0 } } -impl<'a, T: ?Sized, R> ReadLock<'a, T, R> { +impl ReadLock { /// Creates a new `ReadLock` which accesses the given [`RwLock`] /// /// # Examples @@ -52,12 +52,12 @@ impl<'a, T: ?Sized, R> ReadLock<'a, T, R> { /// let read_lock = ReadLock::new(&lock); /// ``` #[must_use] - pub const fn new(rwlock: &'a RwLock) -> Self { + pub const fn new(rwlock: RwLock) -> Self { Self(rwlock) } } -impl<'a, T: ?Sized, R: RawRwLock> ReadLock<'a, T, R> { +impl ReadLock { /// Locks the underlying [`RwLock`] with shared read access, blocking the /// current thread until it can be acquired. pub fn lock<'s, 'key: 's, Key: Keyable + 'key>( diff --git a/src/rwlock/write_lock.rs b/src/rwlock/write_lock.rs index c6b4c24..a344125 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<'a, T: ?Sized + Debug, R: RawRwLock> Debug for WriteLock<'a, T, R> { +impl Debug for WriteLock { 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 @@ -28,19 +28,19 @@ impl<'a, T: ?Sized + Debug, R: RawRwLock> Debug for WriteLock<'a, T, R> { } } -impl<'a, T: ?Sized, R> From<&'a RwLock> for WriteLock<'a, T, R> { - fn from(value: &'a RwLock) -> Self { +impl From> for WriteLock { + fn from(value: RwLock) -> Self { Self::new(value) } } -impl<'a, T: ?Sized, R> AsRef> for WriteLock<'a, T, R> { +impl AsRef> for WriteLock { fn as_ref(&self) -> &RwLock { - self.0 + &self.0 } } -impl<'a, T: ?Sized, R> WriteLock<'a, T, R> { +impl WriteLock { /// Creates a new `WriteLock` which accesses the given [`RwLock`] /// /// # Examples @@ -52,12 +52,12 @@ impl<'a, T: ?Sized, R> WriteLock<'a, T, R> { /// let write_lock = WriteLock::new(&lock); /// ``` #[must_use] - pub const fn new(rwlock: &'a RwLock) -> Self { + pub const fn new(rwlock: RwLock) -> Self { Self(rwlock) } } -impl<'a, T: ?Sized, R: RawRwLock> WriteLock<'a, T, R> { +impl WriteLock { /// 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