From 86610b631c20832d160c1a38181080232a05b508 Mon Sep 17 00:00:00 2001 From: Botahamec Date: Tue, 21 May 2024 19:17:11 -0400 Subject: Sharable API --- src/collection/boxed.rs | 60 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 60 insertions(+) create mode 100644 src/collection/boxed.rs (limited to 'src/collection/boxed.rs') 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) + } +} -- cgit v1.2.3 From ebbe3cfce28914d776f3e5f89894fab50911c57e Mon Sep 17 00:00:00 2001 From: Botahamec Date: Wed, 22 May 2024 15:53:49 -0400 Subject: Implemented necessary traits --- .gitignore | 2 + examples/basic.rs | 2 +- examples/double_mutex.rs | 4 +- examples/list.rs | 2 +- src/collection.rs | 9 +- src/collection/boxed.rs | 293 +++++++++++++++++++++++++++++++++++++++++----- src/collection/guard.rs | 25 ++++ src/collection/owned.rs | 50 ++++++++ src/collection/ref.rs | 33 +++--- src/collection/retry.rs | 102 ++++++++++++++++ src/mutex/guard.rs | 57 +++++++++ src/mutex/mutex.rs | 12 +- src/rwlock/read_guard.rs | 43 +++++++ src/rwlock/rwlock.rs | 12 +- src/rwlock/write_guard.rs | 28 +++++ 15 files changed, 612 insertions(+), 62 deletions(-) (limited to 'src/collection/boxed.rs') diff --git a/.gitignore b/.gitignore index 4fffb2f..8fa03a9 100644 --- a/.gitignore +++ b/.gitignore @@ -1,2 +1,4 @@ +/.idea + /target /Cargo.lock diff --git a/examples/basic.rs b/examples/basic.rs index 1d611d3..b9c5641 100644 --- a/examples/basic.rs +++ b/examples/basic.rs @@ -23,5 +23,5 @@ fn main() { let key = ThreadKey::get().unwrap(); let data = DATA.lock(key); - println!("{}", *data); + println!("{data}"); } diff --git a/examples/double_mutex.rs b/examples/double_mutex.rs index e9a9c77..882fc46 100644 --- a/examples/double_mutex.rs +++ b/examples/double_mutex.rs @@ -27,6 +27,6 @@ fn main() { let key = ThreadKey::get().unwrap(); let data = RefLockCollection::new(&DATA); let data = data.lock(key); - println!("{}", *data.0); - println!("{}", *data.1); + println!("{}", data.0); + println!("{}", data.1); } diff --git a/examples/list.rs b/examples/list.rs index dda468a..a649eeb 100644 --- a/examples/list.rs +++ b/examples/list.rs @@ -59,6 +59,6 @@ fn main() { let data = RefLockCollection::new(&DATA); let data = data.lock(key); for val in &*data { - println!("{}", **val); + println!("{val}"); } } diff --git a/src/collection.rs b/src/collection.rs index 6623c8a..a84c1ce 100644 --- a/src/collection.rs +++ b/src/collection.rs @@ -8,6 +8,7 @@ mod owned; mod r#ref; mod retry; +#[derive(Debug)] pub struct OwnedLockCollection { data: L, } @@ -17,12 +18,16 @@ pub struct OwnedLockCollection { /// This could be a tuple of [`Lockable`] types, an array, or a `Vec`. But it /// can be safely locked without causing a deadlock. pub struct RefLockCollection<'a, L> { - locks: Vec<&'a dyn Lock>, data: &'a L, + locks: Vec<&'a dyn Lock>, } -pub struct BoxedLockCollection<'a, L: 'a>(RefLockCollection<'a, L>); +pub struct BoxedLockCollection { + data: Box, + locks: Vec<&'static dyn Lock>, +} +#[derive(Debug)] pub struct RetryingLockCollection { data: L, } diff --git a/src/collection/boxed.rs b/src/collection/boxed.rs index 8b67ee9..a62a33d 100644 --- a/src/collection/boxed.rs +++ b/src/collection/boxed.rs @@ -1,60 +1,295 @@ -use std::ops::{Deref, DerefMut}; +use std::fmt::Debug; +use std::marker::PhantomData; -use crate::{Lockable, OwnedLockable}; +use crate::lockable::Lock; +use crate::{Keyable, Lockable, OwnedLockable, Sharable}; -use super::{BoxedLockCollection, RefLockCollection}; +use super::{BoxedLockCollection, LockGuard}; -impl<'a, L: 'a> Deref for BoxedLockCollection<'a, L> { - type Target = RefLockCollection<'a, L>; +/// 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])) +} + +unsafe impl Lockable for BoxedLockCollection { + 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 BoxedLockCollection {} + +unsafe impl OwnedLockable for BoxedLockCollection {} + +impl IntoIterator for BoxedLockCollection +where + L: IntoIterator, +{ + type Item = ::Item; + type IntoIter = ::IntoIter; + + fn into_iter(self) -> Self::IntoIter { + self.data.into_iter() + } +} + +impl<'a, L> IntoIterator for &'a BoxedLockCollection +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> IntoIterator for &'a mut BoxedLockCollection +where + &'a mut L: IntoIterator, +{ + type Item = <&'a mut L as IntoIterator>::Item; + type IntoIter = <&'a mut L as IntoIterator>::IntoIter; + + fn into_iter(self) -> Self::IntoIter { + self.data.into_iter() + } +} + +impl + OwnedLockable> FromIterator + for BoxedLockCollection +{ + fn from_iter>(iter: T) -> Self { + let iter: I = iter.into_iter().collect(); + Self::new(iter) + } +} + +impl, L: OwnedLockable> Extend for BoxedLockCollection { + fn extend>(&mut self, iter: T) { + self.data.extend(iter) + } +} + +impl AsRef for BoxedLockCollection { + fn as_ref(&self) -> &L { + &self.data + } +} + +impl AsMut for BoxedLockCollection { + fn as_mut(&mut self) -> &mut L { + &mut self.data + } +} - fn deref(&self) -> &Self::Target { - &self.0 +impl Debug for BoxedLockCollection { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + f.debug_struct(stringify!(BoxedLockCollection)) + .field("data", &self.data) + .finish_non_exhaustive() } } -impl<'a, L: 'a> DerefMut for BoxedLockCollection<'a, L> { - fn deref_mut(&mut self) -> &mut Self::Target { - &mut self.0 +impl Default for BoxedLockCollection { + fn default() -> Self { + Self::new(L::default()) } } -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 From for BoxedLockCollection { + fn from(value: L) -> Self { + Self::new(value) } } -impl<'a, L: OwnedLockable + 'a> BoxedLockCollection<'a, L> { +impl BoxedLockCollection { #[must_use] pub fn new(data: L) -> Self { - let boxed = Box::leak(Box::new(data)); - Self(RefLockCollection::new(boxed)) + // safety: owned lockable types cannot contain duplicates + unsafe { Self::new_unchecked(data) } } } -impl<'a, L: OwnedLockable + 'a> BoxedLockCollection<'a, L> { +impl<'a, L: OwnedLockable> 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) }) + // safety: owned lockable types cannot contain duplicates + unsafe { Self::new_unchecked(data) } } } -impl<'a, L: Lockable + 'a> BoxedLockCollection<'a, L> { +impl BoxedLockCollection { #[must_use] pub unsafe fn new_unchecked(data: L) -> Self { - let boxed = Box::leak(Box::new(data)); - Self(RefLockCollection::new_unchecked(boxed)) + let data = Box::new(data); + let mut locks = Vec::new(); + data.get_ptrs(&mut locks); + + // safety: the box will be dropped after the lock references, so it's + // safe to just pretend they're static + let locks = std::mem::transmute(locks); + Self { data, locks } } #[must_use] pub fn try_new(data: L) -> Option { - let boxed = Box::leak(Box::new(data)); - RefLockCollection::try_new(boxed).map(Self) + // safety: we are checking for duplicates before returning + unsafe { + let this = Self::new_unchecked(data); + if contains_duplicates(&this.locks) { + return None; + } + Some(this) + } + } + + #[must_use] + pub fn into_inner(self) -> Box { + self.data + } + + pub fn lock<'g, 'key: 'g, Key: Keyable + 'key>( + &'g self, + key: Key, + ) -> LockGuard<'key, L::Guard<'g>, 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, + } + } + + pub fn try_lock<'g, 'key: 'g, Key: Keyable + 'key>( + &'g 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, + }) + } + + pub fn unlock<'key, Key: Keyable + 'key>(guard: LockGuard<'key, L::Guard<'_>, Key>) -> Key { + drop(guard.guard); + guard.key + } +} + +impl BoxedLockCollection { + pub fn read<'g, 'key: 'g, Key: Keyable + 'key>( + &'g self, + key: Key, + ) -> LockGuard<'key, L::ReadGuard<'g>, Key> { + for lock in &self.locks { + // safety: we have the thread key + unsafe { lock.read() }; + } + + LockGuard { + // safety: we've already acquired the lock + guard: unsafe { self.data.read_guard() }, + key, + _phantom: PhantomData, + } + } + + pub fn try_read<'g, 'key: 'g, Key: Keyable + 'key>( + &'g 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_read(); + + if !success { + for lock in &self.locks[0..i] { + // safety: this lock was already acquired + lock.unlock_read(); + } + return None; + } + } + + // safety: we've acquired the locks + 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 + } +} + +impl<'a, L: 'a> BoxedLockCollection +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() + } +} + +impl<'a, L: 'a> BoxedLockCollection +where + &'a mut L: IntoIterator, +{ + /// Returns an iterator over mutable references to each value in the + /// collection. + #[must_use] + pub fn iter_mut(&'a mut self) -> <&'a mut L as IntoIterator>::IntoIter { + self.into_iter() } } diff --git a/src/collection/guard.rs b/src/collection/guard.rs index b8561eb..8857c5f 100644 --- a/src/collection/guard.rs +++ b/src/collection/guard.rs @@ -1,9 +1,22 @@ +use std::fmt::{Debug, Display}; use std::ops::{Deref, DerefMut}; use crate::key::Keyable; use super::LockGuard; +impl<'key, Guard: Debug, Key: Keyable> Debug for LockGuard<'key, Guard, Key> { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + Debug::fmt(&**self, f) + } +} + +impl<'key, Guard: Display, Key: Keyable> Display for LockGuard<'key, Guard, Key> { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + Display::fmt(&**self, f) + } +} + impl<'key, Guard, Key: Keyable> Deref for LockGuard<'key, Guard, Key> { type Target = Guard; @@ -17,3 +30,15 @@ impl<'key, Guard, Key: Keyable> DerefMut for LockGuard<'key, Guard, Key> { &mut self.guard } } + +impl<'key, Guard, Key: Keyable> AsRef for LockGuard<'key, Guard, Key> { + fn as_ref(&self) -> &Guard { + &self.guard + } +} + +impl<'key, Guard, Key: Keyable> AsMut for LockGuard<'key, Guard, Key> { + fn as_mut(&mut self) -> &mut Guard { + &mut self.guard + } +} diff --git a/src/collection/owned.rs b/src/collection/owned.rs index 3415ac4..eb5e03a 100644 --- a/src/collection/owned.rs +++ b/src/collection/owned.rs @@ -32,12 +32,62 @@ unsafe impl Sharable for OwnedLockCollection {} unsafe impl OwnedLockable for OwnedLockCollection {} +impl IntoIterator for OwnedLockCollection +where + L: IntoIterator, +{ + type Item = ::Item; + type IntoIter = ::IntoIter; + + fn into_iter(self) -> Self::IntoIter { + self.data.into_iter() + } +} + +impl + OwnedLockable> FromIterator + for OwnedLockCollection +{ + fn from_iter>(iter: T) -> Self { + let iter: I = iter.into_iter().collect(); + Self::new(iter) + } +} + +impl, L: OwnedLockable> Extend for OwnedLockCollection { + fn extend>(&mut self, iter: T) { + self.data.extend(iter) + } +} + +impl AsMut for OwnedLockCollection { + fn as_mut(&mut self) -> &mut L { + &mut self.data + } +} + +impl Default for OwnedLockCollection { + fn default() -> Self { + Self::new(L::default()) + } +} + +impl From for OwnedLockCollection { + fn from(value: L) -> Self { + Self::new(value) + } +} + impl OwnedLockCollection { #[must_use] pub const fn new(data: L) -> Self { Self { data } } + #[must_use] + pub fn into_inner(self) -> L { + self.data + } + pub fn lock<'g, 'key, Key: Keyable + 'key>( &'g self, key: Key, diff --git a/src/collection/ref.rs b/src/collection/ref.rs index da18c62..329f0ae 100644 --- a/src/collection/ref.rs +++ b/src/collection/ref.rs @@ -1,3 +1,4 @@ +use std::fmt::Debug; use std::marker::PhantomData; use crate::{key::Keyable, lockable::Lock, Lockable, OwnedLockable, Sharable}; @@ -5,7 +6,7 @@ use crate::{key::Keyable, lockable::Lock, Lockable, OwnedLockable, Sharable}; use super::{LockGuard, RefLockCollection}; #[must_use] -fn get_locks(data: &L) -> Vec<&dyn Lock> { +pub 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)); @@ -19,24 +20,12 @@ fn contains_duplicates(l: &[&dyn Lock]) -> bool { .any(|window| std::ptr::eq(window[0], window[1])) } -impl<'a, L: Lockable> AsRef for RefLockCollection<'a, L> { +impl<'a, L> 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, @@ -69,6 +58,20 @@ unsafe impl<'c, L: Lockable> Lockable for RefLockCollection<'c, L> { unsafe impl<'c, L: Sharable> Sharable for RefLockCollection<'c, L> {} +impl<'a, L: Debug> Debug for RefLockCollection<'a, L> { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + f.debug_struct(stringify!(RefLockCollection)) + .field("data", self.data) + .finish_non_exhaustive() + } +} + +impl<'a, L: OwnedLockable + Default> From<&'a L> for RefLockCollection<'a, L> { + fn from(value: &'a L) -> Self { + Self::new(value) + } +} + impl<'a, L: OwnedLockable> RefLockCollection<'a, L> { /// Creates a new collection of owned locks. /// @@ -142,7 +145,7 @@ impl<'a, L: Lockable> RefLockCollection<'a, L> { return None; } - Some(Self { locks, data }) + Some(Self { data, locks }) } /// Locks the collection diff --git a/src/collection/retry.rs b/src/collection/retry.rs index 3000f8b..58a0642 100644 --- a/src/collection/retry.rs +++ b/src/collection/retry.rs @@ -41,6 +41,81 @@ unsafe impl Sharable for RetryingLockCollection {} unsafe impl OwnedLockable for RetryingLockCollection {} +impl IntoIterator for RetryingLockCollection +where + L: IntoIterator, +{ + type Item = ::Item; + type IntoIter = ::IntoIter; + + fn into_iter(self) -> Self::IntoIter { + self.data.into_iter() + } +} + +impl<'a, L> IntoIterator for &'a RetryingLockCollection +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> IntoIterator for &'a mut RetryingLockCollection +where + &'a mut L: IntoIterator, +{ + type Item = <&'a mut L as IntoIterator>::Item; + type IntoIter = <&'a mut L as IntoIterator>::IntoIter; + + fn into_iter(self) -> Self::IntoIter { + self.data.into_iter() + } +} + +impl + OwnedLockable> FromIterator + for RetryingLockCollection +{ + fn from_iter>(iter: T) -> Self { + let iter: I = iter.into_iter().collect(); + Self::new(iter) + } +} + +impl, L: OwnedLockable> Extend for RetryingLockCollection { + fn extend>(&mut self, iter: T) { + self.data.extend(iter) + } +} + +impl AsRef for RetryingLockCollection { + fn as_ref(&self) -> &L { + &self.data + } +} + +impl AsMut for RetryingLockCollection { + fn as_mut(&mut self) -> &mut L { + &mut self.data + } +} + +impl Default for RetryingLockCollection { + fn default() -> Self { + Self::new(L::default()) + } +} + +impl From for RetryingLockCollection { + fn from(value: L) -> Self { + Self::new(value) + } +} + impl RetryingLockCollection { #[must_use] pub const fn new(data: L) -> Self { @@ -65,6 +140,10 @@ impl RetryingLockCollection { contains_duplicates(&data).then_some(Self { data }) } + pub fn into_inner(self) -> L { + self.data + } + pub fn lock<'g, 'key: 'g, Key: Keyable + 'key>( &'g self, key: Key, @@ -269,3 +348,26 @@ impl RetryingLockCollection { guard.key } } + +impl<'a, L: 'a> RetryingLockCollection +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() + } +} + +impl<'a, L: 'a> RetryingLockCollection +where + &'a mut L: IntoIterator, +{ + /// Returns an iterator over mutable references to each value in the + /// collection. + #[must_use] + pub fn iter_mut(&'a mut self) -> <&'a mut L as IntoIterator>::IntoIter { + self.into_iter() + } +} diff --git a/src/mutex/guard.rs b/src/mutex/guard.rs index 38ea125..35fe1f2 100644 --- a/src/mutex/guard.rs +++ b/src/mutex/guard.rs @@ -1,3 +1,4 @@ +use std::fmt::{Debug, Display}; use std::marker::PhantomData; use std::ops::{Deref, DerefMut}; @@ -7,6 +8,18 @@ use crate::key::Keyable; use super::{Mutex, MutexGuard, MutexRef}; +impl<'a, T: Debug + ?Sized + 'a, R: RawMutex> Debug for MutexRef<'a, T, R> { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + Debug::fmt(&**self, f) + } +} + +impl<'a, T: Display + ?Sized + 'a, R: RawMutex> Display for MutexRef<'a, T, R> { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + Display::fmt(&**self, f) + } +} + impl<'a, T: ?Sized + 'a, R: RawMutex> Drop for MutexRef<'a, T, R> { fn drop(&mut self) { // safety: this guard is being destroyed, so the data cannot be @@ -35,12 +48,40 @@ impl<'a, T: ?Sized + 'a, R: RawMutex> DerefMut for MutexRef<'a, T, R> { } } +impl<'a, T: ?Sized + 'a, R: RawMutex> AsRef for MutexRef<'a, T, R> { + fn as_ref(&self) -> &T { + self + } +} + +impl<'a, T: ?Sized + 'a, R: RawMutex> AsMut for MutexRef<'a, T, R> { + fn as_mut(&mut self) -> &mut T { + self + } +} + impl<'a, T: ?Sized + 'a, R: RawMutex> MutexRef<'a, T, R> { pub unsafe fn new(mutex: &'a Mutex) -> Self { Self(mutex, PhantomData) } } +impl<'a, 'key, T: Debug + ?Sized + 'a, Key: Keyable + 'key, R: RawMutex> Debug + for MutexGuard<'a, 'key, T, Key, R> +{ + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + Debug::fmt(&**self, f) + } +} + +impl<'a, 'key, T: Display + ?Sized + 'a, Key: Keyable + 'key, R: RawMutex> Display + for MutexGuard<'a, 'key, T, Key, R> +{ + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + Display::fmt(&**self, f) + } +} + impl<'a, 'key: 'a, T: ?Sized + 'a, Key: Keyable, R: RawMutex> Deref for MutexGuard<'a, 'key, T, Key, R> { @@ -59,6 +100,22 @@ impl<'a, 'key: 'a, T: ?Sized + 'a, Key: Keyable, R: RawMutex> DerefMut } } +impl<'a, 'key: 'a, T: ?Sized + 'a, Key: Keyable, R: RawMutex> AsRef + for MutexGuard<'a, 'key, T, Key, R> +{ + fn as_ref(&self) -> &T { + self + } +} + +impl<'a, 'key: 'a, T: ?Sized + 'a, Key: Keyable, R: RawMutex> AsMut + for MutexGuard<'a, 'key, T, Key, R> +{ + fn as_mut(&mut self) -> &mut T { + self + } +} + impl<'a, 'key: 'a, T: ?Sized + 'a, Key: Keyable, R: RawMutex> MutexGuard<'a, 'key, T, Key, R> { /// Create a guard to the given mutex. Undefined if multiple guards to the /// same mutex exist at once. diff --git a/src/mutex/mutex.rs b/src/mutex/mutex.rs index 3b8c221..52b6081 100644 --- a/src/mutex/mutex.rs +++ b/src/mutex/mutex.rs @@ -43,12 +43,6 @@ impl Mutex { } } -impl Default for Mutex { - fn default() -> Self { - Self::new(T::default()) - } -} - impl Debug for Mutex { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { // safety: this is just a try lock, and the value is dropped @@ -71,6 +65,12 @@ impl Debug for Mutex { } } +impl Default for Mutex { + fn default() -> Self { + Self::new(T::default()) + } +} + impl From for Mutex { fn from(value: T) -> Self { Self::new(value) diff --git a/src/rwlock/read_guard.rs b/src/rwlock/read_guard.rs index 8428987..da3d101 100644 --- a/src/rwlock/read_guard.rs +++ b/src/rwlock/read_guard.rs @@ -1,3 +1,4 @@ +use std::fmt::{Debug, Display}; use std::marker::PhantomData; use std::ops::Deref; @@ -7,6 +8,18 @@ use crate::key::Keyable; use super::{RwLock, RwLockReadGuard, RwLockReadRef}; +impl<'a, T: Debug + ?Sized + 'a, R: RawRwLock> Debug for RwLockReadRef<'a, T, R> { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + Debug::fmt(&**self, f) + } +} + +impl<'a, T: Display + ?Sized + 'a, R: RawRwLock> Display for RwLockReadRef<'a, T, R> { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + Display::fmt(&**self, f) + } +} + impl<'a, T: ?Sized + 'a, R: RawRwLock> Deref for RwLockReadRef<'a, T, R> { type Target = T; @@ -18,6 +31,12 @@ impl<'a, T: ?Sized + 'a, R: RawRwLock> Deref for RwLockReadRef<'a, T, R> { } } +impl<'a, T: ?Sized + 'a, R: RawRwLock> AsRef for RwLockReadRef<'a, T, R> { + fn as_ref(&self) -> &T { + self + } +} + impl<'a, T: ?Sized + 'a, R: RawRwLock> Drop for RwLockReadRef<'a, T, R> { fn drop(&mut self) { // safety: this guard is being destroyed, so the data cannot be @@ -32,6 +51,22 @@ impl<'a, T: ?Sized + 'a, R: RawRwLock> RwLockReadRef<'a, T, R> { } } +impl<'a, 'key, T: Debug + ?Sized + 'a, Key: Keyable + 'key, R: RawRwLock> Debug + for RwLockReadGuard<'a, 'key, T, Key, R> +{ + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + Debug::fmt(&**self, f) + } +} + +impl<'a, 'key, T: Display + ?Sized + 'a, Key: Keyable + 'key, R: RawRwLock> Display + for RwLockReadGuard<'a, 'key, T, Key, R> +{ + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + Display::fmt(&**self, f) + } +} + impl<'a, 'key: 'a, T: ?Sized + 'a, Key: Keyable, R: RawRwLock> Deref for RwLockReadGuard<'a, 'key, T, Key, R> { @@ -42,6 +77,14 @@ impl<'a, 'key: 'a, T: ?Sized + 'a, Key: Keyable, R: RawRwLock> Deref } } +impl<'a, 'key: 'a, T: ?Sized + 'a, Key: Keyable, R: RawRwLock> AsRef + for RwLockReadGuard<'a, 'key, T, Key, R> +{ + fn as_ref(&self) -> &T { + self + } +} + impl<'a, 'key: 'a, T: ?Sized + 'a, Key: Keyable, R: RawRwLock> RwLockReadGuard<'a, 'key, T, Key, R> { diff --git a/src/rwlock/rwlock.rs b/src/rwlock/rwlock.rs index 7070b0e..9a7590a 100644 --- a/src/rwlock/rwlock.rs +++ b/src/rwlock/rwlock.rs @@ -40,12 +40,6 @@ impl RwLock { } } -impl Default for RwLock { - fn default() -> Self { - Self::new(T::default()) - } -} - impl Debug for RwLock { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { // safety: this is just a try lock, and the value is dropped @@ -68,6 +62,12 @@ impl Debug for RwLock { } } +impl Default for RwLock { + fn default() -> Self { + Self::new(T::default()) + } +} + impl From for RwLock { fn from(value: T) -> Self { Self::new(value) diff --git a/src/rwlock/write_guard.rs b/src/rwlock/write_guard.rs index 16b474e..c8dd58b 100644 --- a/src/rwlock/write_guard.rs +++ b/src/rwlock/write_guard.rs @@ -27,6 +27,18 @@ impl<'a, T: ?Sized + 'a, R: RawRwLock> DerefMut for RwLockWriteRef<'a, T, R> { } } +impl<'a, T: ?Sized + 'a, R: RawRwLock> AsRef for RwLockWriteRef<'a, T, R> { + fn as_ref(&self) -> &T { + self + } +} + +impl<'a, T: ?Sized + 'a, R: RawRwLock> AsMut for RwLockWriteRef<'a, T, R> { + fn as_mut(&mut self) -> &mut T { + self + } +} + impl<'a, T: ?Sized + 'a, R: RawRwLock> Drop for RwLockWriteRef<'a, T, R> { fn drop(&mut self) { // safety: this guard is being destroyed, so the data cannot be @@ -59,6 +71,22 @@ impl<'a, 'key: 'a, T: ?Sized + 'a, Key: Keyable, R: RawRwLock> DerefMut } } +impl<'a, 'key: 'a, T: ?Sized + 'a, Key: Keyable, R: RawRwLock> AsRef + for RwLockWriteGuard<'a, 'key, T, Key, R> +{ + fn as_ref(&self) -> &T { + self + } +} + +impl<'a, 'key: 'a, T: ?Sized + 'a, Key: Keyable, R: RawRwLock> AsMut + for RwLockWriteGuard<'a, 'key, T, Key, R> +{ + fn as_mut(&mut self) -> &mut T { + self + } +} + impl<'a, 'key: 'a, T: ?Sized + 'a, Key: Keyable, R: RawRwLock> RwLockWriteGuard<'a, 'key, T, Key, R> { -- 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 'src/collection/boxed.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 878f4fae4d3c6e64ab3824bf3fc012fbb5293a21 Mon Sep 17 00:00:00 2001 From: Botahamec Date: Wed, 22 May 2024 20:59:09 -0400 Subject: Documentation --- README.md | 8 +- happylock.md | 339 ++++++++++++++++++++++++++++++++++++++++++++++ src/collection.rs | 2 + src/collection/boxed.rs | 231 +++++++++++++++++++++++++++++++ src/collection/owned.rs | 156 +++++++++++++++++++++ src/collection/ref.rs | 116 ++++++++++++++-- src/collection/retry.rs | 248 ++++++++++++++++++++++++++++++++- src/lockable.rs | 336 ++++----------------------------------------- src/mutex/guard.rs | 4 +- src/rwlock/read_guard.rs | 4 +- src/rwlock/read_lock.rs | 2 +- src/rwlock/write_guard.rs | 4 +- 12 files changed, 1122 insertions(+), 328 deletions(-) create mode 100644 happylock.md (limited to 'src/collection/boxed.rs') diff --git a/README.md b/README.md index 01c259e..04e5a71 100644 --- a/README.md +++ b/README.md @@ -48,7 +48,10 @@ let data = data.lock(&mut key); println!("{}", *data); ``` -Unlocking a mutex requires a `ThreadKey` or a mutable reference to `ThreadKey`. Each thread will be allowed to have one key at a time, but no more than that. The `ThreadKey` type is not cloneable or copyable. This means that only one thing can be locked at a time. +Unlocking a mutex requires a `ThreadKey` or a mutable reference to `ThreadKey`. +Each thread will be allowed to have one key at a time, but no more than that. +The `ThreadKey` type is not cloneable or copyable. This means that only one +thing can be locked at a time. To lock multiple mutexes at a time, create a `LockCollection`. @@ -76,7 +79,8 @@ println!("{}", *data.0); println!("{}", *data.1); ``` -In many cases, the [`LockCollection::new`] or [`LockCollection::new_ref`] method can be used, improving performance. +In many cases, the [`LockCollection::new`] or [`LockCollection::new_ref`] +method can be used, improving performance. ```rust use std::thread; diff --git a/happylock.md b/happylock.md new file mode 100644 index 0000000..477e99b --- /dev/null +++ b/happylock.md @@ -0,0 +1,339 @@ +--- +marp: true +theme: gaia +class: invert +--- + + + +# HappyLock + +deadlock-free mutexes at compile-time + +--- + +## Four Conditions for Deadlock + +1. Mutual Exclusion +2. Non-preemptive Allocation +3. Cyclic Wait +4. Partial Allocation + +--- + +## Preventing Mutual Exclusion + +Mutual exclusion is the entire point of a mutex. + +Do you want a `ReadOnly` type? + +Just use `Arc` or `&T`! + +--- + +## Prevent Non-Preemptive Allocation + +```rust +let mutex = Mutex::new(10); +let mut number = mutex.lock(); + +let th = thread::spawn(|| { + let number = mutex.lock(); // preempts the other lock on number +}); +th.join(); + +prinln!("Thread 1: {}", *number); // oops, we don't have access to number anymore! +``` + +--- + +## Preventing Cyclic Wait + +The language needs to enforce that all locks are acquired in the same order. + +Rust doesn't have a built-in mechanism which can provide this. + +Even if it could keep the locks in a certain order, using a `OrderedLock` type, we wouldn't be able to force you to use the mechanism. + +And you could create two `OrderedLock` types and get deadlock using that. + +--- + +## Preventing Partial Allocation + +The language needs to enforce *total allocation*. + +Acquiring a new lock requires releasing all currently-held locks. + +**This will be our approach for now.** + +--- + +## Quick Refresh on Borrow Checker Rules + +1. You may have multiple immutable references to a value at a time +2. If there is a mutable reference to a value, then it is the only reference +3. Values cannot be moved while they are being referenced + +```rust +let s = String::new("Hello, world!"); +let r1 = &s; +let r2 = &s; // this is allowed because of #1 +let mr = &mut s; // illegal: rule #2 +drop(s); // also illegal: rule #3 +println!("{r1} {r2}"); +``` + +--- + +## How could an Operating System do this? + +```c +#include + +void main() { + os_mutex_t m = os_mutex_create(); + + // the os returns an error if the rules aren't followed + if (os_mutex_lock(&m)) { + printf("Error!\n"); + } + + return 0; +} +``` + +--- + +## We have technology! (the borrow checker) + +```rust +use happylock::{ThreadKey, Mutex}; + +fn main() { + // each thread can only have one thread key (that's why we unwrap) + // ThreadKey is not Send, Sync, Copy, or Clone + let key = ThreadKey::get().unwrap(); + + let mutex = Mutex::new(10); + + // locking a mutex requires either the ThreadKey or a &mut ThreadKey + let mut guard = mutex.lock(key); + // this means that a thread cannot lock more than one thing at a time + + println!("{}", *guard); +} +``` + +--- + +## Performance: it's freaking fast + +`ThreadKey` is a mostly zero-cosst abstraction. It takes no memory at runtime. The only cost is getting and dropping the key. + +`Mutex` is a thin wrapper around `parking_lot`. There's also a `spin` backend if needed for some reason. + +--- + +## Wait, I need two mutexes + +```rust +use happylock::{ThreadKey, Mutex, LockCollection}; + +fn main() { + let key = ThreadKey::get().unwrap(); + let mutex1 = Mutex::new(5); + let mutex2 = Mutex::new(String::new()); + + let collection = LockCollection::new((mutex1, mutex2)); + let guard = collection.lock(key); + + *guard.1 = format!("{}{}", *guard.1, guard.0); + *guard.0 += 1; +} +``` + +--- + +## The Lockable API + +```rust +unsafe trait Lockable { + type Guard; + + unsafe fn lock(&self) -> Self::Guard; + + unsafe fn try_lock(&self) -> Option; +} +``` + +--- + +## That's cool! Lemme try something + +```rust +use happylock::{ThreadKey, Mutex, LockCollection}; + +fn main() { + let key = ThreadKey::get().unwrap(); + let mutex1 = Mutex::new(5); + + // oh no. this will deadlock us + let collection = LockCollection::new((&mutex1, &mutex1)); + let guard = collection.lock(key); + + // the good news is: this doesn't compile +} +``` + +--- + +## LockCollection's stub + +```rust +impl LockCollection { + pub fn new(data: L) -> Self { /***/ } +} + +impl LockCollection<&L> { + pub fn new_ref(data: &L) -> Self { /***/ } +} + +impl LockCollection { + // checks for duplicates + pub fn try_new(data: L) -> Option { /***/ } + + pub unsafe fn new_unchecked(data: L) -> Self { /***/ } +} +``` + +--- + +## Changes to Lockable + +```rust +unsafe trait Lockable { + // ... + + fn get_ptrs(&self) -> Vec; +} + + + +// not implemented for &L +// ergo: the values within are guaranteed to be unique +unsafe trait OwnedLockable: Lockable {} + + +``` + +--- + +## `contains_duplicates` (1st attempt) + +```rust +fn contains_duplicates(data: L) -> bool { + let pointers = data.get_ptrs(); + for (i, ptr1) in pointers.iter().enumerate() { + for ptr2 in pointers.iter().take(i) { + if ptr1 == ptr2 { + return true; + } + } + } + + false +} +``` + +Time Complexity: O(n²) + +--- + +## 2nd attempt: sorting the pointers + +```rust +fn contains_duplicates(data: L) -> bool { + let mut pointers = data.get_ptrs(); + pointers.sort_unstable(); + pointers.windows(2).any(|w| w[0] == w[1]) +} +``` + +Time Complexity: O(nlogn) + +--- + +## Missing Features + +- `Condvar`/`Barrier` +- We probably don't need `OnceLock` or `LazyLock` +- Standard Library Backend +- Mutex poisoning +- Support for `no_std` +- Convenience methods: `lock_swap`, `lock_set`? +- `try_lock_swap` doesn't need a `ThreadKey` +- Going further: `LockCell` API (preemptive allocation) + +--- + + + +## What's next? + +--- + +## Problem: Live-locking + +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. + +--- + +## Solution: Switch to preventing cyclic wait + +- We're already sorting the pointers by memory address. +- So let's keep that order! + +--- + +## Problems with This Approach + +- I can't sort a tuple + - Don't return them sorted, silly +- Indexing the locks in the right order + - Have `get_ptrs` return a `&dyn Lock` + - Start by locking everything + - Then call a separate `guard` method to create the guard + +--- + +# New traits + +```rust +unsafe trait Lock { + unsafe fn lock(&self); + unsafe fn try_lock(&self) -> bool; + unsafe fn unlock(&self); +} + +unsafe trait Lockable { // this is a bad name (LockGroup?) + type Guard<'g>; + fn get_locks<'a>(&'a self, &mut Vec<&'a dyn Lock>); + unsafe fn guard<'g>(&'g self) -> Self::Guard<'g>; +} +``` + +--- + +## Ok let's get started, oh wait + +- self-referential data structures + - for best performance: `RefLockCollection`, `BoxedLockCollection`, `OwnedLockCollection` +- `LockCollection::new_ref` doesn't work without sorting + - So as a fallback, provide `RetryingLockCollection`. It doesn't do any sorting, but unlikely to ever acquire the lock + +--- + + + +## The End diff --git a/src/collection.rs b/src/collection.rs index c51e3cf..5dc6946 100644 --- a/src/collection.rs +++ b/src/collection.rs @@ -103,6 +103,8 @@ pub struct RetryingLockCollection { } /// A RAII guard for a generic [`Lockable`] type. +/// +/// [`Lockable`]: `crate::lockable::Lockable` pub struct LockGuard<'key, Guard, Key: Keyable + 'key> { guard: Guard, key: Key, diff --git a/src/collection/boxed.rs b/src/collection/boxed.rs index ea840ab..224eedb 100644 --- a/src/collection/boxed.rs +++ b/src/collection/boxed.rs @@ -119,6 +119,19 @@ impl From for BoxedLockCollection { } impl BoxedLockCollection { + /// 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::{Mutex, LockCollection}; + /// + /// let data = (Mutex::new(0), Mutex::new("")); + /// let lock = LockCollection::new(data); + /// ``` #[must_use] pub fn new(data: L) -> Self { // safety: owned lockable types cannot contain duplicates @@ -127,6 +140,19 @@ impl BoxedLockCollection { } impl<'a, L: OwnedLockable> BoxedLockCollection<&'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::{Mutex, LockCollection}; + /// + /// let data = (Mutex::new(0), Mutex::new("")); + /// let lock = LockCollection::new_ref(&data); + /// ``` #[must_use] pub fn new_ref(data: &'a L) -> Self { // safety: owned lockable types cannot contain duplicates @@ -135,11 +161,31 @@ impl<'a, L: OwnedLockable> BoxedLockCollection<&'a L> { } impl BoxedLockCollection { + /// Creates a new collections of locks. + /// + /// # Safety + /// + /// This results in undefined behavior if any locks are presented twice + /// within this collection. + /// + /// # Examples + /// + /// ``` + /// use happylock::{Mutex, LockCollection}; + /// + /// let data1 = Mutex::new(0); + /// let data2 = Mutex::new(""); + /// + /// // safety: data1 and data2 refer to distinct mutexes + /// let data = (&data1, &data2); + /// let lock = unsafe { LockCollection::new_unchecked(&data) }; + /// ``` #[must_use] pub unsafe fn new_unchecked(data: L) -> Self { let data = Box::new(data); let mut locks = Vec::new(); data.get_ptrs(&mut locks); + locks.sort_by_key(|lock| std::ptr::from_ref(*lock).cast::<()>() as usize); // safety: the box will be dropped after the lock references, so it's // safe to just pretend they're static @@ -147,6 +193,23 @@ impl BoxedLockCollection { Self { data, locks } } + /// Creates a new collection of locks. + /// + /// This returns `None` if any locks are found twice in the given + /// collection. + /// + /// # Examples + /// + /// ``` + /// use happylock::{Mutex, LockCollection}; + /// + /// let data1 = Mutex::new(0); + /// let data2 = Mutex::new(""); + /// + /// // data1 and data2 refer to distinct mutexes, so this won't panic + /// let data = (&data1, &data2); + /// let lock = LockCollection::try_new(&data).unwrap(); + /// ``` #[must_use] pub fn try_new(data: L) -> Option { // safety: we are checking for duplicates before returning @@ -159,11 +222,48 @@ impl BoxedLockCollection { } } + /// Gets the underlying collection, consuming this collection. + /// + /// # Examples + /// + /// ``` + /// use happylock::{Mutex, ThreadKey, LockCollection}; + /// + /// let data1 = Mutex::new(42); + /// let data2 = Mutex::new(""); + /// + /// // data1 and data2 refer to distinct mutexes, so this won't panic + /// let data = (&data1, &data2); + /// let lock = LockCollection::try_new(&data).unwrap(); + /// + /// let key = ThreadKey::get().unwrap(); + /// let guard = lock.into_inner().0.lock(key); + /// assert_eq!(*guard, 42); + /// ``` #[must_use] pub fn into_inner(self) -> Box { self.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::{Mutex, ThreadKey, LockCollection}; + /// + /// let key = ThreadKey::get().unwrap(); + /// let data = (Mutex::new(0), Mutex::new("")); + /// let lock = LockCollection::new(data); + /// + /// let mut guard = lock.lock(key); + /// *guard.0 += 1; + /// *guard.1 = "1"; + /// ``` pub fn lock<'g, 'key: 'g, Key: Keyable + 'key>( &'g self, key: Key, @@ -181,6 +281,30 @@ impl BoxedLockCollection { } } + /// 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::{Mutex, ThreadKey, LockCollection}; + /// + /// let key = ThreadKey::get().unwrap(); + /// let data = (Mutex::new(0), Mutex::new("")); + /// let lock = LockCollection::new(data); + /// + /// match lock.try_lock(key) { + /// Some(mut guard) => { + /// *guard.0 += 1; + /// *guard.1 = "1"; + /// }, + /// None => unreachable!(), + /// }; + /// + /// ``` pub fn try_lock<'g, 'key: 'g, Key: Keyable + 'key>( &'g self, key: Key, @@ -210,6 +334,23 @@ impl BoxedLockCollection { }) } + /// Unlocks the underlying lockable data type, returning the key that's + /// associated with it. + /// + /// # Examples + /// + /// ``` + /// use happylock::{Mutex, ThreadKey, LockCollection}; + /// + /// let key = ThreadKey::get().unwrap(); + /// let data = (Mutex::new(0), Mutex::new("")); + /// let lock = LockCollection::new(data); + /// + /// let mut guard = lock.lock(key); + /// *guard.0 += 1; + /// *guard.1 = "1"; + /// let key = LockCollection::<(Mutex, Mutex<&str>)>::unlock(guard); + /// ``` pub fn unlock<'key, Key: Keyable + 'key>(guard: LockGuard<'key, L::Guard<'_>, Key>) -> Key { drop(guard.guard); guard.key @@ -217,6 +358,25 @@ impl BoxedLockCollection { } impl BoxedLockCollection { + /// Locks the collection, so that other threads can still read from it + /// + /// This function returns a guard that can be used to access the underlying + /// data immutably. When the guard is dropped, the locks in the collection + /// are also dropped. + /// + /// # Examples + /// + /// ``` + /// use happylock::{RwLock, ThreadKey, LockCollection}; + /// + /// let key = ThreadKey::get().unwrap(); + /// let data = (RwLock::new(0), RwLock::new("")); + /// let lock = LockCollection::new(data); + /// + /// let mut guard = lock.read(key); + /// assert_eq!(*guard.0, 0); + /// assert_eq!(*guard.1, ""); + /// ``` pub fn read<'g, 'key: 'g, Key: Keyable + 'key>( &'g self, key: Key, @@ -234,6 +394,31 @@ impl BoxedLockCollection { } } + /// Attempts to lock the without blocking, in such a way that other threads + /// can still read from the collection. + /// + /// If successful, this method returns a guard that can be used to access + /// the data immutably, and unlocks the data when it is dropped. Otherwise, + /// `None` is returned. + /// + /// # Examples + /// + /// ``` + /// use happylock::{RwLock, ThreadKey, LockCollection}; + /// + /// let key = ThreadKey::get().unwrap(); + /// let data = (RwLock::new(5), RwLock::new("6")); + /// let lock = LockCollection::new(data); + /// + /// match lock.try_read(key) { + /// Some(mut guard) => { + /// assert_eq!(*guard.0, 5); + /// assert_eq!(*guard.1, "6"); + /// }, + /// None => unreachable!(), + /// }; + /// + /// ``` pub fn try_read<'g, 'key: 'g, Key: Keyable + 'key>( &'g self, key: Key, @@ -263,6 +448,21 @@ impl BoxedLockCollection { }) } + /// Unlocks the underlying lockable data type, returning the key that's + /// associated with it. + /// + /// # Examples + /// + /// ``` + /// use happylock::{RwLock, ThreadKey, LockCollection}; + /// + /// let key = ThreadKey::get().unwrap(); + /// let data = (RwLock::new(0), RwLock::new("")); + /// let lock = LockCollection::new(data); + /// + /// let mut guard = lock.read(key); + /// let key = LockCollection::<(RwLock, RwLock<&str>)>::unlock_read(guard); + /// ``` pub fn unlock_read<'key, Key: Keyable + 'key>( guard: LockGuard<'key, L::ReadGuard<'_>, Key>, ) -> Key { @@ -276,6 +476,22 @@ where &'a L: IntoIterator, { /// Returns an iterator over references to each value in the collection. + /// + /// # Examples + /// + /// ``` + /// use happylock::{Mutex, ThreadKey, LockCollection}; + /// + /// let key = ThreadKey::get().unwrap(); + /// let data = [Mutex::new(26), Mutex::new(1)]; + /// let lock = LockCollection::new(data); + /// + /// let mut iter = lock.iter(); + /// let mutex = iter.next().unwrap(); + /// let guard = mutex.lock(key); + /// + /// assert_eq!(*guard, 26); + /// ``` #[must_use] pub fn iter(&'a self) -> <&'a L as IntoIterator>::IntoIter { self.into_iter() @@ -288,6 +504,21 @@ where { /// Returns an iterator over mutable references to each value in the /// collection. + /// + /// # Examples + /// + /// ``` + /// use happylock::{Mutex, ThreadKey, LockCollection}; + /// + /// let key = ThreadKey::get().unwrap(); + /// let data = [Mutex::new(26), Mutex::new(1)]; + /// let mut lock = LockCollection::new(data); + /// + /// let mut iter = lock.iter_mut(); + /// let mutex = iter.next().unwrap(); + /// + /// assert_eq!(*mutex.as_mut(), 26); + /// ``` #[must_use] pub fn iter_mut(&'a mut self) -> <&'a mut L as IntoIterator>::IntoIter { self.into_iter() diff --git a/src/collection/owned.rs b/src/collection/owned.rs index d77d568..e1549b2 100644 --- a/src/collection/owned.rs +++ b/src/collection/owned.rs @@ -79,16 +79,67 @@ impl From for OwnedLockCollection { } impl OwnedLockCollection { + /// Creates a new collection of owned locks. + /// + /// Because the locks are owned, there's no need to do any checks for + /// duplicate values. The locks also don't need to be sorted by memory + /// address because they aren't used anywhere else. + /// + /// # Examples + /// + /// ``` + /// use happylock::Mutex; + /// use happylock::collection::OwnedLockCollection; + /// + /// let data = (Mutex::new(0), Mutex::new("")); + /// let lock = OwnedLockCollection::new(data); + /// ``` #[must_use] pub const fn new(data: L) -> Self { Self { data } } + /// Gets the underlying collection, consuming this collection. + /// + /// # Examples + /// + /// ``` + /// use happylock::{Mutex, ThreadKey}; + /// use happylock::collection::OwnedLockCollection; + /// + /// let data = (Mutex::new(42), Mutex::new("")); + /// let lock = OwnedLockCollection::new(data); + /// + /// let key = ThreadKey::get().unwrap(); + /// let inner = lock.into_inner(); + /// let guard = inner.0.lock(key); + /// assert_eq!(*guard, 42); + /// ``` #[must_use] pub fn into_inner(self) -> L { self.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::{Mutex, ThreadKey}; + /// use happylock::collection::OwnedLockCollection; + /// + /// let key = ThreadKey::get().unwrap(); + /// let data = (Mutex::new(0), Mutex::new("")); + /// let lock = OwnedLockCollection::new(data); + /// + /// let mut guard = lock.lock(key); + /// *guard.0 += 1; + /// *guard.1 = "1"; + /// ``` pub fn lock<'g, 'key, Key: Keyable + 'key>( &'g self, key: Key, @@ -109,6 +160,31 @@ impl OwnedLockCollection { } } + /// 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::{Mutex, ThreadKey}; + /// use happylock::collection::OwnedLockCollection; + /// + /// let key = ThreadKey::get().unwrap(); + /// let data = (Mutex::new(0), Mutex::new("")); + /// let lock = OwnedLockCollection::new(data); + /// + /// match lock.try_lock(key) { + /// Some(mut guard) => { + /// *guard.0 += 1; + /// *guard.1 = "1"; + /// }, + /// None => unreachable!(), + /// }; + /// + /// ``` pub fn try_lock<'g, 'key: 'g, Key: Keyable + 'key>( &'g self, key: Key, @@ -139,6 +215,24 @@ impl OwnedLockCollection { }) } + /// Unlocks the underlying lockable data type, returning the key that's + /// associated with it. + /// + /// # Examples + /// + /// ``` + /// use happylock::{Mutex, ThreadKey}; + /// use happylock::collection::OwnedLockCollection; + /// + /// let key = ThreadKey::get().unwrap(); + /// let data = (Mutex::new(0), Mutex::new("")); + /// let lock = OwnedLockCollection::new(data); + /// + /// let mut guard = lock.lock(key); + /// *guard.0 += 1; + /// *guard.1 = "1"; + /// let key = OwnedLockCollection::<(Mutex, Mutex<&str>)>::unlock(guard); + /// ``` #[allow(clippy::missing_const_for_fn)] pub fn unlock<'g, 'key: 'g, Key: Keyable + 'key>( guard: LockGuard<'key, L::Guard<'g>, Key>, @@ -149,6 +243,26 @@ impl OwnedLockCollection { } impl OwnedLockCollection { + /// Locks the collection, so that other threads can still read from it + /// + /// This function returns a guard that can be used to access the underlying + /// data immutably. When the guard is dropped, the locks in the collection + /// are also dropped. + /// + /// # Examples + /// + /// ``` + /// use happylock::{RwLock, ThreadKey}; + /// use happylock::collection::OwnedLockCollection; + /// + /// let key = ThreadKey::get().unwrap(); + /// let data = (RwLock::new(0), RwLock::new("")); + /// let lock = OwnedLockCollection::new(data); + /// + /// let mut guard = lock.read(key); + /// assert_eq!(*guard.0, 0); + /// assert_eq!(*guard.1, ""); + /// ``` pub fn read<'g, 'key, Key: Keyable + 'key>( &'g self, key: Key, @@ -169,6 +283,32 @@ impl OwnedLockCollection { } } + /// Attempts to lock the without blocking, in such a way that other threads + /// can still read from the collection. + /// + /// If successful, this method returns a guard that can be used to access + /// the data immutably, and unlocks the data when it is dropped. Otherwise, + /// `None` is returned. + /// + /// # Examples + /// + /// ``` + /// use happylock::{RwLock, ThreadKey}; + /// use happylock::collection::OwnedLockCollection; + /// + /// let key = ThreadKey::get().unwrap(); + /// let data = (RwLock::new(5), RwLock::new("6")); + /// let lock = OwnedLockCollection::new(data); + /// + /// match lock.try_read(key) { + /// Some(mut guard) => { + /// assert_eq!(*guard.0, 5); + /// assert_eq!(*guard.1, "6"); + /// }, + /// None => unreachable!(), + /// }; + /// + /// ``` pub fn try_read<'g, 'key: 'g, Key: Keyable + 'key>( &'g self, key: Key, @@ -199,6 +339,22 @@ impl OwnedLockCollection { }) } + /// Unlocks the underlying lockable data type, returning the key that's + /// associated with it. + /// + /// # Examples + /// + /// ``` + /// use happylock::{RwLock, ThreadKey}; + /// use happylock::collection::OwnedLockCollection; + /// + /// let key = ThreadKey::get().unwrap(); + /// let data = (RwLock::new(0), RwLock::new("")); + /// let lock = OwnedLockCollection::new(data); + /// + /// let mut guard = lock.read(key); + /// let key = OwnedLockCollection::<(RwLock, RwLock<&str>)>::unlock_read(guard); + /// ``` #[allow(clippy::missing_const_for_fn)] pub fn unlock_read<'g, 'key: 'g, Key: Keyable + 'key>( guard: LockGuard<'key, L::ReadGuard<'g>, Key>, diff --git a/src/collection/ref.rs b/src/collection/ref.rs index 2e2883a..e5c548f 100644 --- a/src/collection/ref.rs +++ b/src/collection/ref.rs @@ -82,10 +82,11 @@ impl<'a, L: OwnedLockable> RefLockCollection<'a, L> { /// # Examples /// /// ``` - /// use happylock::{LockCollection, Mutex}; + /// use happylock::Mutex; + /// use happylock::collection::RefLockCollection; /// /// let data = (Mutex::new(0), Mutex::new("")); - /// let lock = LockCollection::new(&data); + /// let lock = RefLockCollection::new(&data); /// ``` #[must_use] pub fn new(data: &'a L) -> RefLockCollection { @@ -107,13 +108,15 @@ impl<'a, L: Lockable> RefLockCollection<'a, L> { /// # Examples /// /// ``` - /// use happylock::{LockCollection, Mutex}; + /// use happylock::Mutex; + /// use happylock::collection::RefLockCollection; /// /// 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)) }; + /// let data = (&data1, &data2); + /// let lock = unsafe { RefLockCollection::new_unchecked(&data) }; /// ``` #[must_use] pub unsafe fn new_unchecked(data: &'a L) -> Self { @@ -131,13 +134,15 @@ impl<'a, L: Lockable> RefLockCollection<'a, L> { /// # Examples /// /// ``` - /// use happylock::{LockCollection, Mutex}; + /// use happylock::Mutex; + /// use happylock::collection::RefLockCollection; /// /// 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(); + /// let data = (&data1, &data2); + /// let lock = RefLockCollection::try_new(&data).unwrap(); /// ``` #[must_use] pub fn try_new(data: &'a L) -> Option { @@ -158,10 +163,12 @@ impl<'a, L: Lockable> RefLockCollection<'a, L> { /// # Examples /// /// ``` - /// use happylock::{LockCollection, Mutex, ThreadKey}; + /// use happylock::{Mutex, ThreadKey}; + /// use happylock::collection::RefLockCollection; /// /// let key = ThreadKey::get().unwrap(); - /// let lock = LockCollection::new((Mutex::new(0), Mutex::new(""))); + /// let data = (Mutex::new(0), Mutex::new("")); + /// let lock = RefLockCollection::new(&data); /// /// let mut guard = lock.lock(key); /// *guard.0 += 1; @@ -193,10 +200,12 @@ impl<'a, L: Lockable> RefLockCollection<'a, L> { /// # Examples /// /// ``` - /// use happylock::{LockCollection, Mutex, ThreadKey}; + /// use happylock::{Mutex, ThreadKey}; + /// use happylock::collection::RefLockCollection; /// /// let key = ThreadKey::get().unwrap(); - /// let lock = LockCollection::new((Mutex::new(0), Mutex::new(""))); + /// let data = (Mutex::new(0), Mutex::new("")); + /// let lock = RefLockCollection::new(&data); /// /// match lock.try_lock(key) { /// Some(mut guard) => { @@ -242,15 +251,17 @@ impl<'a, L: Lockable> RefLockCollection<'a, L> { /// # Examples /// /// ``` - /// use happylock::{LockCollection, Mutex, ThreadKey}; + /// use happylock::{Mutex, ThreadKey}; + /// use happylock::collection::RefLockCollection; /// /// let key = ThreadKey::get().unwrap(); - /// let lock = LockCollection::new((Mutex::new(0), Mutex::new(""))); + /// let data = (Mutex::new(0), Mutex::new("")); + /// let lock = RefLockCollection::new(&data); /// /// let mut guard = lock.lock(key); /// *guard.0 += 1; /// *guard.1 = "1"; - /// let key = LockCollection::unlock(guard); + /// let key = RefLockCollection::<(Mutex, Mutex<&str>)>::unlock(guard); /// ``` #[allow(clippy::missing_const_for_fn)] pub fn unlock<'key: 'a, Key: Keyable + 'key>(guard: LockGuard<'key, L::Guard<'a>, Key>) -> Key { @@ -260,6 +271,26 @@ impl<'a, L: Lockable> RefLockCollection<'a, L> { } impl<'a, L: Sharable> RefLockCollection<'a, L> { + /// Locks the collection, so that other threads can still read from it + /// + /// This function returns a guard that can be used to access the underlying + /// data immutably. When the guard is dropped, the locks in the collection + /// are also dropped. + /// + /// # Examples + /// + /// ``` + /// use happylock::{RwLock, ThreadKey}; + /// use happylock::collection::RefLockCollection; + /// + /// let key = ThreadKey::get().unwrap(); + /// let data = (RwLock::new(0), RwLock::new("")); + /// let lock = RefLockCollection::new(&data); + /// + /// let mut guard = lock.read(key); + /// assert_eq!(*guard.0, 0); + /// assert_eq!(*guard.1, ""); + /// ``` pub fn read<'key: 'a, Key: Keyable + 'key>( &'a self, key: Key, @@ -277,6 +308,32 @@ impl<'a, L: Sharable> RefLockCollection<'a, L> { } } + /// Attempts to lock the without blocking, in such a way that other threads + /// can still read from the collection. + /// + /// If successful, this method returns a guard that can be used to access + /// the data immutably, and unlocks the data when it is dropped. Otherwise, + /// `None` is returned. + /// + /// # Examples + /// + /// ``` + /// use happylock::{RwLock, ThreadKey}; + /// use happylock::collection::RefLockCollection; + /// + /// let key = ThreadKey::get().unwrap(); + /// let data = (RwLock::new(5), RwLock::new("6")); + /// let lock = RefLockCollection::new(&data); + /// + /// match lock.try_read(key) { + /// Some(mut guard) => { + /// assert_eq!(*guard.0, 5); + /// assert_eq!(*guard.1, "6"); + /// }, + /// None => unreachable!(), + /// }; + /// + /// ``` pub fn try_read<'key: 'a, Key: Keyable + 'key>( &'a self, key: Key, @@ -306,6 +363,22 @@ impl<'a, L: Sharable> RefLockCollection<'a, L> { }) } + /// Unlocks the underlying lockable data type, returning the key that's + /// associated with it. + /// + /// # Examples + /// + /// ``` + /// use happylock::{RwLock, ThreadKey}; + /// use happylock::collection::RefLockCollection; + /// + /// let key = ThreadKey::get().unwrap(); + /// let data = (RwLock::new(0), RwLock::new("")); + /// let lock = RefLockCollection::new(&data); + /// + /// let mut guard = lock.read(key); + /// let key = RefLockCollection::<(RwLock, RwLock<&str>)>::unlock_read(guard); + /// ``` #[allow(clippy::missing_const_for_fn)] pub fn unlock_read<'key: 'a, Key: Keyable + 'key>( guard: LockGuard<'key, L::ReadGuard<'a>, Key>, @@ -320,6 +393,23 @@ where &'a L: IntoIterator, { /// Returns an iterator over references to each value in the collection. + /// + /// # Examples + /// + /// ``` + /// use happylock::{Mutex, ThreadKey}; + /// use happylock::collection::RefLockCollection; + /// + /// let key = ThreadKey::get().unwrap(); + /// let data = [Mutex::new(26), Mutex::new(1)]; + /// let lock = RefLockCollection::new(&data); + /// + /// let mut iter = lock.iter(); + /// let mutex = iter.next().unwrap(); + /// let guard = mutex.lock(key); + /// + /// assert_eq!(*guard, 26); + /// ``` #[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 index d15d7d6..2b9b0a0 100644 --- a/src/collection/retry.rs +++ b/src/collection/retry.rs @@ -6,12 +6,13 @@ use std::marker::PhantomData; use super::{LockGuard, RetryingLockCollection}; +/// Checks that a collection contains no duplicate references to a lock. 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 RawLock); - let mut locks_set = HashSet::new(); + let mut locks_set = HashSet::with_capacity(locks.len()); for lock in locks { if !locks_set.insert(lock) { return true; @@ -119,6 +120,21 @@ impl From for RetryingLockCollection { } impl RetryingLockCollection { + /// Creates a new collection of owned locks. + /// + /// Because the locks are owned, there's no need to do any checks for + /// duplicate values. The locks also don't need to be sorted by memory + /// address because they aren't used anywhere else. + /// + /// # Examples + /// + /// ``` + /// use happylock::Mutex; + /// use happylock::collection::RetryingLockCollection; + /// + /// let data = (Mutex::new(0), Mutex::new("")); + /// let lock = RetryingLockCollection::new(data); + /// ``` #[must_use] pub const fn new(data: L) -> Self { Self { data } @@ -126,6 +142,20 @@ impl RetryingLockCollection { } impl<'a, L: OwnedLockable> RetryingLockCollection<&'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::Mutex; + /// use happylock::collection::RetryingLockCollection; + /// + /// let data = (Mutex::new(0), Mutex::new("")); + /// let lock = RetryingLockCollection::new_ref(&data); + /// ``` #[must_use] pub const fn new_ref(data: &'a L) -> Self { Self { data } @@ -133,19 +163,95 @@ impl<'a, L: OwnedLockable> RetryingLockCollection<&'a L> { } impl RetryingLockCollection { + /// Creates a new collections of locks. + /// + /// # Safety + /// + /// This results in undefined behavior if any locks are presented twice + /// within this collection. + /// + /// # Examples + /// + /// ``` + /// use happylock::Mutex; + /// use happylock::collection::RetryingLockCollection; + /// + /// let data1 = Mutex::new(0); + /// let data2 = Mutex::new(""); + /// + /// // safety: data1 and data2 refer to distinct mutexes + /// let data = (&data1, &data2); + /// let lock = unsafe { RetryingLockCollection::new_unchecked(&data) }; + /// ``` #[must_use] pub const unsafe fn new_unchecked(data: L) -> Self { Self { data } } + /// Creates a new collection of locks. + /// + /// This returns `None` if any locks are found twice in the given + /// collection. + /// + /// # Examples + /// + /// ``` + /// use happylock::Mutex; + /// use happylock::collection::RetryingLockCollection; + /// + /// let data1 = Mutex::new(0); + /// let data2 = Mutex::new(""); + /// + /// // data1 and data2 refer to distinct mutexes, so this won't panic + /// let data = (&data1, &data2); + /// let lock = RetryingLockCollection::try_new(&data).unwrap(); + /// ``` + #[must_use] pub fn try_new(data: L) -> Option { - contains_duplicates(&data).then_some(Self { data }) + (!contains_duplicates(&data)).then_some(Self { data }) } + /// Gets the underlying collection, consuming this collection. + /// + /// # Examples + /// + /// ``` + /// use happylock::{Mutex, ThreadKey}; + /// use happylock::collection::RetryingLockCollection; + /// + /// let data = (Mutex::new(42), Mutex::new("")); + /// let lock = RetryingLockCollection::new(data); + /// + /// let key = ThreadKey::get().unwrap(); + /// let inner = lock.into_inner(); + /// let guard = inner.0.lock(key); + /// assert_eq!(*guard, 42); + /// ``` + #[must_use] pub fn into_inner(self) -> L { self.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::{Mutex, ThreadKey}; + /// use happylock::collection::RetryingLockCollection; + /// + /// let key = ThreadKey::get().unwrap(); + /// let data = (Mutex::new(0), Mutex::new("")); + /// let lock = RetryingLockCollection::new(data); + /// + /// let mut guard = lock.lock(key); + /// *guard.0 += 1; + /// *guard.1 = "1"; + /// ``` pub fn lock<'g, 'key: 'g, Key: Keyable + 'key>( &'g self, key: Key, @@ -202,6 +308,31 @@ impl RetryingLockCollection { } } + /// 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::{Mutex, ThreadKey}; + /// use happylock::collection::RetryingLockCollection; + /// + /// let key = ThreadKey::get().unwrap(); + /// let data = (Mutex::new(0), Mutex::new("")); + /// let lock = RetryingLockCollection::new(data); + /// + /// match lock.try_lock(key) { + /// Some(mut guard) => { + /// *guard.0 += 1; + /// *guard.1 = "1"; + /// }, + /// None => unreachable!(), + /// }; + /// + /// ``` pub fn try_lock<'g, 'key: 'g, Key: Keyable + 'key>( &'g self, key: Key, @@ -241,6 +372,24 @@ impl RetryingLockCollection { }) } + /// Unlocks the underlying lockable data type, returning the key that's + /// associated with it. + /// + /// # Examples + /// + /// ``` + /// use happylock::{Mutex, ThreadKey}; + /// use happylock::collection::RetryingLockCollection; + /// + /// let key = ThreadKey::get().unwrap(); + /// let data = (Mutex::new(0), Mutex::new("")); + /// let lock = RetryingLockCollection::new(data); + /// + /// let mut guard = lock.lock(key); + /// *guard.0 += 1; + /// *guard.1 = "1"; + /// let key = RetryingLockCollection::<(Mutex, Mutex<&str>)>::unlock(guard); + /// ``` pub fn unlock<'key, Key: Keyable + 'key>(guard: LockGuard<'key, L::Guard<'_>, Key>) -> Key { drop(guard.guard); guard.key @@ -248,6 +397,26 @@ impl RetryingLockCollection { } impl RetryingLockCollection { + /// Locks the collection, so that other threads can still read from it + /// + /// This function returns a guard that can be used to access the underlying + /// data immutably. When the guard is dropped, the locks in the collection + /// are also dropped. + /// + /// # Examples + /// + /// ``` + /// use happylock::{RwLock, ThreadKey}; + /// use happylock::collection::RetryingLockCollection; + /// + /// let key = ThreadKey::get().unwrap(); + /// let data = (RwLock::new(0), RwLock::new("")); + /// let lock = RetryingLockCollection::new(data); + /// + /// let mut guard = lock.read(key); + /// assert_eq!(*guard.0, 0); + /// assert_eq!(*guard.1, ""); + /// ``` pub fn read<'g, 'key: 'g, Key: Keyable + 'key>( &'g self, key: Key, @@ -304,6 +473,32 @@ impl RetryingLockCollection { } } + /// Attempts to lock the without blocking, in such a way that other threads + /// can still read from the collection. + /// + /// If successful, this method returns a guard that can be used to access + /// the data immutably, and unlocks the data when it is dropped. Otherwise, + /// `None` is returned. + /// + /// # Examples + /// + /// ``` + /// use happylock::{RwLock, ThreadKey}; + /// use happylock::collection::RetryingLockCollection; + /// + /// let key = ThreadKey::get().unwrap(); + /// let data = (RwLock::new(5), RwLock::new("6")); + /// let lock = RetryingLockCollection::new(data); + /// + /// match lock.try_read(key) { + /// Some(mut guard) => { + /// assert_eq!(*guard.0, 5); + /// assert_eq!(*guard.1, "6"); + /// }, + /// None => unreachable!(), + /// }; + /// + /// ``` pub fn try_read<'g, 'key: 'g, Key: Keyable + 'key>( &'g self, key: Key, @@ -343,6 +538,22 @@ impl RetryingLockCollection { }) } + /// Unlocks the underlying lockable data type, returning the key that's + /// associated with it. + /// + /// # Examples + /// + /// ``` + /// use happylock::{RwLock, ThreadKey}; + /// use happylock::collection::RetryingLockCollection; + /// + /// let key = ThreadKey::get().unwrap(); + /// let data = (RwLock::new(0), RwLock::new("")); + /// let lock = RetryingLockCollection::new(data); + /// + /// let mut guard = lock.read(key); + /// let key = RetryingLockCollection::<(RwLock, RwLock<&str>)>::unlock_read(guard); + /// ``` pub fn unlock_read<'key, Key: Keyable + 'key>( guard: LockGuard<'key, L::ReadGuard<'_>, Key>, ) -> Key { @@ -356,6 +567,23 @@ where &'a L: IntoIterator, { /// Returns an iterator over references to each value in the collection. + /// + /// # Examples + /// + /// ``` + /// use happylock::{Mutex, ThreadKey}; + /// use happylock::collection::RetryingLockCollection; + /// + /// let key = ThreadKey::get().unwrap(); + /// let data = [Mutex::new(26), Mutex::new(1)]; + /// let lock = RetryingLockCollection::new(data); + /// + /// let mut iter = lock.iter(); + /// let mutex = iter.next().unwrap(); + /// let guard = mutex.lock(key); + /// + /// assert_eq!(*guard, 26); + /// ``` #[must_use] pub fn iter(&'a self) -> <&'a L as IntoIterator>::IntoIter { self.into_iter() @@ -368,6 +596,22 @@ where { /// Returns an iterator over mutable references to each value in the /// collection. + /// + /// # Examples + /// + /// ``` + /// use happylock::{Mutex, ThreadKey}; + /// use happylock::collection::RetryingLockCollection; + /// + /// let key = ThreadKey::get().unwrap(); + /// let data = [Mutex::new(26), Mutex::new(1)]; + /// let mut lock = RetryingLockCollection::new(data); + /// + /// let mut iter = lock.iter_mut(); + /// let mutex = iter.next().unwrap(); + /// + /// assert_eq!(*mutex.as_mut(), 26); + /// ``` #[must_use] pub fn iter_mut(&'a mut self) -> <&'a mut L as IntoIterator>::IntoIter { self.into_iter() diff --git a/src/lockable.rs b/src/lockable.rs index 2f98d3a..6b9c7c6 100644 --- a/src/lockable.rs +++ b/src/lockable.rs @@ -311,6 +311,8 @@ unsafe impl Lockable for &T { } } +unsafe impl Sharable for &T {} + unsafe impl Lockable for &mut T { type Guard<'g> = T::Guard<'g> where Self: 'g; @@ -329,323 +331,43 @@ unsafe impl Lockable for &mut T { } } -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 RawLock>) { - self.0.get_ptrs(ptrs); - } - - 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 RawLock>) { - self.0.get_ptrs(ptrs); - self.1.get_ptrs(ptrs); - } - - 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 RawLock>) { - self.0.get_ptrs(ptrs); - self.1.get_ptrs(ptrs); - self.2.get_ptrs(ptrs); - } - - 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 RawLock>) { - self.0.get_ptrs(ptrs); - self.1.get_ptrs(ptrs); - self.2.get_ptrs(ptrs); - self.3.get_ptrs(ptrs); - } - - unsafe fn guard(&self) -> Self::Guard<'_> { - ( - self.0.guard(), - self.1.guard(), - self.2.guard(), - 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 - for (A, B, C, D, E) -{ - type Guard<'g> = ( - A::Guard<'g>, - B::Guard<'g>, - C::Guard<'g>, - D::Guard<'g>, - 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 RawLock>) { - self.0.get_ptrs(ptrs); - self.1.get_ptrs(ptrs); - self.2.get_ptrs(ptrs); - self.3.get_ptrs(ptrs); - self.4.get_ptrs(ptrs); - } - - unsafe fn guard(&self) -> Self::Guard<'_> { - ( - self.0.guard(), - self.1.guard(), - self.2.guard(), - self.3.guard(), - 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 - for (A, B, C, D, E, F) -{ - type Guard<'g> = ( - A::Guard<'g>, - B::Guard<'g>, - C::Guard<'g>, - D::Guard<'g>, - E::Guard<'g>, - F::Guard<'g>, - ) 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 RawLock>) { - self.0.get_ptrs(ptrs); - self.1.get_ptrs(ptrs); - self.2.get_ptrs(ptrs); - self.3.get_ptrs(ptrs); - self.4.get_ptrs(ptrs); - self.5.get_ptrs(ptrs); - } - - unsafe fn guard(&self) -> Self::Guard<'_> { - ( - self.0.guard(), - self.1.guard(), - self.2.guard(), - self.3.guard(), - self.4.guard(), - self.5.guard(), - ) - } +unsafe impl Sharable for &mut T {} - 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(), - self.5.read_guard(), - ) - } -} - -unsafe impl - Lockable for (A, B, C, D, E, F, G) -{ - 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; - - 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 RawLock>) { - self.0.get_ptrs(ptrs); - self.1.get_ptrs(ptrs); - self.2.get_ptrs(ptrs); - self.3.get_ptrs(ptrs); - self.4.get_ptrs(ptrs); - self.5.get_ptrs(ptrs); - self.6.get_ptrs(ptrs); - } - - unsafe fn guard(&self) -> Self::Guard<'_> { - ( - self.0.guard(), - self.1.guard(), - self.2.guard(), - self.3.guard(), - self.4.guard(), - self.5.guard(), - self.6.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(), - 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 OwnedLockable for &mut T {} -unsafe impl Sharable - for (A, B, C, D, E) -{ -} +macro_rules! tuple_impls { + ($($generic:ident)*, $($value:tt)*) => { + unsafe impl<$($generic: Lockable,)*> Lockable for ($($generic,)*) { + type Guard<'g> = ($($generic::Guard<'g>,)*) where Self: 'g; -unsafe impl Sharable - for (A, B, C, D, E, F) -{ -} + type ReadGuard<'g> = ($($generic::ReadGuard<'g>,)*) where Self: 'g; -unsafe impl - Sharable for (A, B, C, D, E, F, G) -{ -} + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { + self.0.get_ptrs(ptrs); + } -unsafe impl OwnedLockable for (A,) {} -unsafe impl OwnedLockable for (A, B) {} + unsafe fn guard(&self) -> Self::Guard<'_> { + ($(self.$value.guard(),)*) + } -unsafe impl OwnedLockable for (A, B, C) {} + unsafe fn read_guard(&self) -> Self::ReadGuard<'_> { + ($(self.$value.read_guard(),)*) + } + } -unsafe impl OwnedLockable - for (A, B, C, D) -{ -} + unsafe impl<$($generic: Sharable,)*> Sharable for ($($generic,)*) {} -unsafe impl - OwnedLockable for (A, B, C, D, E) -{ + unsafe impl<$($generic: OwnedLockable,)*> OwnedLockable for ($($generic,)*) {} + }; } -unsafe impl< - A: OwnedLockable, - B: OwnedLockable, - C: OwnedLockable, - D: OwnedLockable, - E: OwnedLockable, - F: OwnedLockable, - > OwnedLockable for (A, B, C, D, E, F) -{ -} - -unsafe impl< - A: OwnedLockable, - B: OwnedLockable, - C: OwnedLockable, - D: OwnedLockable, - E: OwnedLockable, - F: OwnedLockable, - G: OwnedLockable, - > OwnedLockable for (A, B, C, D, E, F, G) -{ -} +tuple_impls!(A, 0); +tuple_impls!(A B, 0 1); +tuple_impls!(A B C, 0 1 2); +tuple_impls!(A B C D, 0 1 2 3); +tuple_impls!(A B C D E, 0 1 2 3 4); +tuple_impls!(A B C D E F, 0 1 2 3 4 5); +tuple_impls!(A B C D E F G, 0 1 2 3 4 5 6); unsafe impl Lockable for [T; N] { type Guard<'g> = [T::Guard<'g>; N] where Self: 'g; diff --git a/src/mutex/guard.rs b/src/mutex/guard.rs index 35fe1f2..9e8e2e6 100644 --- a/src/mutex/guard.rs +++ b/src/mutex/guard.rs @@ -61,7 +61,9 @@ impl<'a, T: ?Sized + 'a, R: RawMutex> AsMut for MutexRef<'a, T, R> { } impl<'a, T: ?Sized + 'a, R: RawMutex> MutexRef<'a, T, R> { - pub unsafe fn new(mutex: &'a Mutex) -> Self { + /// Creates a reference to the underlying data of a mutex without + /// attempting to lock it or take ownership of the key. + pub(crate) unsafe fn new(mutex: &'a Mutex) -> Self { Self(mutex, PhantomData) } } diff --git a/src/rwlock/read_guard.rs b/src/rwlock/read_guard.rs index da3d101..e46078c 100644 --- a/src/rwlock/read_guard.rs +++ b/src/rwlock/read_guard.rs @@ -46,7 +46,9 @@ impl<'a, T: ?Sized + 'a, R: RawRwLock> Drop for RwLockReadRef<'a, T, R> { } impl<'a, T: ?Sized + 'a, R: RawRwLock> RwLockReadRef<'a, T, R> { - pub unsafe fn new(mutex: &'a RwLock) -> Self { + /// Creates an immutable reference for the underlying data of an [`RwLock`] + /// without locking it or taking ownership of the key. + pub(crate) unsafe fn new(mutex: &'a RwLock) -> Self { Self(mutex, PhantomData) } } diff --git a/src/rwlock/read_lock.rs b/src/rwlock/read_lock.rs index 29042b5..4f2bc86 100644 --- a/src/rwlock/read_lock.rs +++ b/src/rwlock/read_lock.rs @@ -36,7 +36,7 @@ impl<'l, T, R> From<&'l RwLock> for ReadLock<'l, T, R> { impl<'l, T: ?Sized, R> AsRef> for ReadLock<'l, T, R> { fn as_ref(&self) -> &RwLock { - &self.0 + self.0 } } diff --git a/src/rwlock/write_guard.rs b/src/rwlock/write_guard.rs index c8dd58b..ec622d7 100644 --- a/src/rwlock/write_guard.rs +++ b/src/rwlock/write_guard.rs @@ -48,7 +48,9 @@ impl<'a, T: ?Sized + 'a, R: RawRwLock> Drop for RwLockWriteRef<'a, T, R> { } impl<'a, T: ?Sized + 'a, R: RawRwLock> RwLockWriteRef<'a, T, R> { - pub unsafe fn new(mutex: &'a RwLock) -> Self { + /// Creates a reference to the underlying data of an [`RwLock`] without + /// locking or taking ownership of the key. + pub(crate) unsafe fn new(mutex: &'a RwLock) -> Self { Self(mutex, PhantomData) } } -- cgit v1.2.3 From f81d4b40a007fecf6502a36b4c24a1e31807a731 Mon Sep 17 00:00:00 2001 From: Botahamec Date: Thu, 23 May 2024 19:50:32 -0400 Subject: Comments --- src/collection.rs | 20 +++++++++++++++++++- src/collection/boxed.rs | 30 +++++++----------------------- src/collection/owned.rs | 28 +++++----------------------- src/collection/ref.rs | 28 +++++----------------------- src/collection/utils.rs | 44 ++++++++++++++++++++++++++++++++++++++++++++ src/key.rs | 7 +++++++ src/lib.rs | 3 +++ src/lockable.rs | 28 ++++++++++++++++++++++++++-- src/mutex.rs | 5 ++++- src/mutex/guard.rs | 10 ++++++++++ src/mutex/mutex.rs | 4 ++++ src/rwlock/write_lock.rs | 11 +++++------ 12 files changed, 139 insertions(+), 79 deletions(-) create mode 100644 src/collection/utils.rs (limited to 'src/collection/boxed.rs') diff --git a/src/collection.rs b/src/collection.rs index 5dc6946..27ec1c4 100644 --- a/src/collection.rs +++ b/src/collection.rs @@ -7,6 +7,7 @@ mod guard; mod owned; mod r#ref; mod retry; +mod utils; /// Locks a collection of locks, which cannot be shared immutably. /// @@ -24,6 +25,9 @@ mod retry; /// /// [`Lockable`]: `crate::lockable::Lockable` /// [`OwnedLockable`]: `crate::lockable::OwnedLockable` + +// this type caches the idea that no immutable references to the underlying +// collection exist #[derive(Debug)] pub struct OwnedLockCollection { data: L, @@ -47,6 +51,13 @@ pub struct OwnedLockCollection { /// /// [`Lockable`]: `crate::lockable::Lockable` /// [`OwnedLockable`]: `crate::lockable::OwnedLockable` + +// This type was born when I eventually realized that I needed a self +// referential structure. That used boxing, so I elected to make a more +// efficient implementation (polonius please save us) + +// This type caches the sorting order of the locks and the fact that it doesn't +// contain any duplicates. pub struct RefLockCollection<'a, L> { data: &'a L, locks: Vec<&'a dyn RawLock>, @@ -70,9 +81,14 @@ pub struct RefLockCollection<'a, L> { /// /// [`Lockable`]: `crate::lockable::Lockable` /// [`OwnedLockable`]: `crate::lockable::OwnedLockable` + +// This type caches the sorting order of the locks and the fact that it doesn't +// contain any duplicates. pub struct BoxedLockCollection { data: Box, - locks: Vec<&'static dyn RawLock>, + locks: Vec<&'static dyn RawLock>, // As far as you know, it's static. + // Believe it or not, saying the lifetime + // is static when it's not isn't UB } /// Locks a collection of locks using a retrying algorithm. @@ -97,6 +113,8 @@ pub struct BoxedLockCollection { /// [`Lockable`]: `crate::lockable::Lockable` /// [`OwnedLockable`]: `crate::lockable::OwnedLockable` /// [livelocking]: https://en.wikipedia.org/wiki/Deadlock#Livelock + +// This type caches the fact that there are no duplicates #[derive(Debug)] pub struct RetryingLockCollection { data: L, diff --git a/src/collection/boxed.rs b/src/collection/boxed.rs index 224eedb..5ced6d1 100644 --- a/src/collection/boxed.rs +++ b/src/collection/boxed.rs @@ -4,7 +4,7 @@ use std::marker::PhantomData; use crate::lockable::{Lockable, OwnedLockable, RawLock, Sharable}; use crate::Keyable; -use super::{BoxedLockCollection, LockGuard}; +use super::{utils, BoxedLockCollection, LockGuard}; /// returns `true` if the sorted list contains a duplicate #[must_use] @@ -185,6 +185,8 @@ impl BoxedLockCollection { let data = Box::new(data); let mut locks = Vec::new(); data.get_ptrs(&mut locks); + + // cast to *const () because fat pointers can't be converted to usize locks.sort_by_key(|lock| std::ptr::from_ref(*lock).cast::<()>() as usize); // safety: the box will be dropped after the lock references, so it's @@ -310,17 +312,8 @@ impl BoxedLockCollection { 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; - } + if !utils::ordered_try_lock(&self.locks) { + return None; } // safety: we've acquired the locks @@ -424,17 +417,8 @@ impl BoxedLockCollection { 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_read(); - - if !success { - for lock in &self.locks[0..i] { - // safety: this lock was already acquired - lock.unlock_read(); - } - return None; - } + if !utils::ordered_try_read(&self.locks) { + return None; } // safety: we've acquired the locks diff --git a/src/collection/owned.rs b/src/collection/owned.rs index e1549b2..919c403 100644 --- a/src/collection/owned.rs +++ b/src/collection/owned.rs @@ -3,7 +3,7 @@ use std::marker::PhantomData; use crate::lockable::{Lockable, OwnedLockable, RawLock, Sharable}; use crate::Keyable; -use super::{LockGuard, OwnedLockCollection}; +use super::{utils, LockGuard, OwnedLockCollection}; fn get_locks(data: &L) -> Vec<&dyn RawLock> { let mut locks = Vec::new(); @@ -191,17 +191,8 @@ impl OwnedLockCollection { ) -> 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; - } + if !utils::ordered_try_lock(&locks) { + return None; } // safety: we've acquired the locks @@ -315,17 +306,8 @@ impl OwnedLockCollection { ) -> 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; - } + if !utils::ordered_try_read(&locks) { + return None; } // safety: we've acquired the locks diff --git a/src/collection/ref.rs b/src/collection/ref.rs index e5c548f..d8c7f2e 100644 --- a/src/collection/ref.rs +++ b/src/collection/ref.rs @@ -4,7 +4,7 @@ use std::marker::PhantomData; use crate::lockable::{Lockable, OwnedLockable, RawLock, Sharable}; use crate::Keyable; -use super::{LockGuard, RefLockCollection}; +use super::{utils, LockGuard, RefLockCollection}; #[must_use] pub fn get_locks(data: &L) -> Vec<&dyn RawLock> { @@ -221,17 +221,8 @@ impl<'a, L: Lockable> RefLockCollection<'a, L> { 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; - } + if !utils::ordered_try_lock(&self.locks) { + return None; } // safety: we've acquired the locks @@ -339,17 +330,8 @@ impl<'a, L: Sharable> RefLockCollection<'a, L> { 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_read(); - - if !success { - for lock in &self.locks[0..i] { - // safety: this lock was already acquired - lock.unlock_read(); - } - return None; - } + if !utils::ordered_try_read(&self.locks) { + return None; } // safety: we've acquired the locks diff --git a/src/collection/utils.rs b/src/collection/utils.rs new file mode 100644 index 0000000..dc58399 --- /dev/null +++ b/src/collection/utils.rs @@ -0,0 +1,44 @@ +use crate::lockable::RawLock; + +/// Locks the locks in the order they are given. This causes deadlock if the +/// locks contain duplicates, or if this is called by multiple threads with the +/// locks in different orders. +pub unsafe fn ordered_try_lock(locks: &[&dyn RawLock]) -> bool { + 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 false; + } + } + + true + } +} + +/// Locks the locks in the order they are given. This causes deadlock f this is +/// called by multiple threads with the locks in different orders. +pub unsafe fn ordered_try_read(locks: &[&dyn RawLock]) -> bool { + 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_read(); + } + return false; + } + } + + true + } +} diff --git a/src/key.rs b/src/key.rs index 875f4be..4d6504f 100644 --- a/src/key.rs +++ b/src/key.rs @@ -7,6 +7,8 @@ use thread_local::ThreadLocal; use sealed::Sealed; +// Sealed to prevent other key types from being implemented. Otherwise, this +// would almost instant undefined behavior. mod sealed { use super::ThreadKey; @@ -15,6 +17,9 @@ mod sealed { impl Sealed for &mut ThreadKey {} } +// I am concerned that having multiple crates linked together with different +// static variables could break my key system. Library code probably shouldn't +// be creating keys at all. static KEY: Lazy> = Lazy::new(ThreadLocal::new); /// The key for the current thread. @@ -34,6 +39,7 @@ pub struct ThreadKey { /// values invalid. pub unsafe trait Keyable: Sealed {} unsafe impl Keyable for ThreadKey {} +// the ThreadKey can't be moved while a mutable reference to it exists unsafe impl Keyable for &mut ThreadKey {} impl Debug for ThreadKey { @@ -42,6 +48,7 @@ impl Debug for ThreadKey { } } +// If you lose the thread key, you can get it back by calling ThreadKey::get impl Drop for ThreadKey { fn drop(&mut self) { unsafe { KEY.get().unwrap().force_unlock() } diff --git a/src/lib.rs b/src/lib.rs index 9c39c6d..643c3e7 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -176,6 +176,9 @@ pub use key::{Keyable, ThreadKey}; #[cfg(feature = "spin")] pub use mutex::SpinLock; +// Personally, I think re-exports look ugly in the rust documentation, so I +// went with type aliases instead. + /// A collection of locks that can be acquired simultaneously. /// /// This re-exports [`BoxedLockCollection`] as a sensible default. diff --git a/src/lockable.rs b/src/lockable.rs index 6b9c7c6..9f44981 100644 --- a/src/lockable.rs +++ b/src/lockable.rs @@ -14,6 +14,13 @@ use lock_api::{RawMutex, RawRwLock}; /// 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. + +// Why not use a RawRwLock? Because that would be semantically incorrect, and I +// don't want an INIT or GuardMarker associated item. +// Originally, RawLock had a sister trait: RawSharableLock. I removed it +// because it'd be difficult to implement a separate type that takes a +// different kind of RawLock. But now the Sharable marker trait is needed to +// indicate if reads can be used. pub unsafe trait RawLock: Send + Sync { /// Blocks until the lock is acquired /// @@ -175,6 +182,8 @@ unsafe impl RawLock for Mutex { self.raw().unlock() } + // this is the closest thing to a read we can get, but Sharable isn't + // implemented for this unsafe fn read(&self) { self.raw().lock() } @@ -291,8 +300,13 @@ unsafe impl<'l, T: Send, R: RawRwLock + Send + Sync> Lockable for WriteLock<'l, } } +// Technically, the exclusive locks can also be shared, but there's currently +// no way to express that. I don't think I want to ever express that. unsafe impl<'l, T: Send, R: RawRwLock + Send + Sync> Sharable for ReadLock<'l, T, R> {} +// Because both ReadLock and WriteLock hold references to RwLocks, they can't +// implement OwnedLockable + unsafe impl Lockable for &T { type Guard<'g> = T::Guard<'g> where Self: 'g; @@ -335,6 +349,8 @@ unsafe impl Sharable for &mut T {} unsafe impl OwnedLockable for &mut T {} +/// Implements `Lockable`, `Sharable`, and `OwnedLockable` for tuples +/// ex: `tuple_impls!(A B C, 0 1 2);` macro_rules! tuple_impls { ($($generic:ident)*, $($value:tt)*) => { unsafe impl<$($generic: Lockable,)*> Lockable for ($($generic,)*) { @@ -347,6 +363,8 @@ macro_rules! tuple_impls { } unsafe fn guard(&self) -> Self::Guard<'_> { + // It's weird that this works + // I don't think any other way of doing it compiles ($(self.$value.guard(),)*) } @@ -381,6 +399,8 @@ unsafe impl Lockable for [T; N] { } unsafe fn guard<'g>(&'g self) -> Self::Guard<'g> { + // The MaybeInit helper functions for arrays aren't stable yet, so + // we'll just have to implement it ourselves let mut guards = MaybeUninit::<[MaybeUninit>; N]>::uninit().assume_init(); for i in 0..N { guards[i].write(self[i].guard()); @@ -430,7 +450,8 @@ unsafe impl Lockable for Box<[T]> { } unsafe impl Lockable for Vec { - type Guard<'g> = Vec> where Self: 'g; + // There's no reason why I'd ever want to extend a list of lock guards + type Guard<'g> = Box<[T::Guard<'g>]> where Self: 'g; type ReadGuard<'g> = Box<[T::ReadGuard<'g>]> where Self: 'g; @@ -446,7 +467,7 @@ unsafe impl Lockable for Vec { guards.push(lock.guard()); } - guards + guards.into_boxed_slice() } unsafe fn read_guard(&self) -> Self::ReadGuard<'_> { @@ -459,6 +480,9 @@ unsafe impl Lockable for Vec { } } +// I'd make a generic impl> Lockable for I +// but I think that'd require sealing up this trait + unsafe impl Sharable for [T; N] {} unsafe impl Sharable for Box<[T]> {} unsafe impl Sharable for Vec {} diff --git a/src/mutex.rs b/src/mutex.rs index a3baa00..b30c2b1 100644 --- a/src/mutex.rs +++ b/src/mutex.rs @@ -49,8 +49,11 @@ pub struct MutexRef<'a, T: ?Sized + 'a, R: RawMutex>( /// /// [`lock`]: `Mutex::lock` /// [`try_lock`]: `Mutex::try_lock` + +// This is the most lifetime-intensive thing I've ever written. Can I graduate +// from borrow checker university now? pub struct MutexGuard<'a, 'key: 'a, T: ?Sized + 'a, Key: Keyable + 'key, R: RawMutex> { - mutex: MutexRef<'a, T, R>, + mutex: MutexRef<'a, T, R>, // this way we don't need to re-implement Drop thread_key: Key, _phantom: PhantomData<&'key ()>, } diff --git a/src/mutex/guard.rs b/src/mutex/guard.rs index 9e8e2e6..f9324ad 100644 --- a/src/mutex/guard.rs +++ b/src/mutex/guard.rs @@ -8,6 +8,9 @@ use crate::key::Keyable; use super::{Mutex, MutexGuard, MutexRef}; +// This makes things slightly easier because now you can use +// `println!("{guard}")` instead of `println!("{}", *guard)`. I wonder if I +// should implement some other standard library traits like this too? impl<'a, T: Debug + ?Sized + 'a, R: RawMutex> Debug for MutexRef<'a, T, R> { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { Debug::fmt(&**self, f) @@ -63,11 +66,18 @@ impl<'a, T: ?Sized + 'a, R: RawMutex> AsMut for MutexRef<'a, T, R> { impl<'a, T: ?Sized + 'a, R: RawMutex> MutexRef<'a, T, R> { /// Creates a reference to the underlying data of a mutex without /// attempting to lock it or take ownership of the key. + + // This might be useful to export, because it makes it easier to express + // the concept of: "Get the data out the mutex but don't lock it or take + // the key". But it's also quite dangerous to drop. pub(crate) unsafe fn new(mutex: &'a Mutex) -> Self { Self(mutex, PhantomData) } } +// it's kinda annoying to re-implement some of this stuff on guards +// there's nothing i can do about that + impl<'a, 'key, T: Debug + ?Sized + 'a, Key: Keyable + 'key, R: RawMutex> Debug for MutexGuard<'a, 'key, T, Key, R> { diff --git a/src/mutex/mutex.rs b/src/mutex/mutex.rs index 52b6081..89dfef9 100644 --- a/src/mutex/mutex.rs +++ b/src/mutex/mutex.rs @@ -48,6 +48,7 @@ impl Debug for Mutex { // safety: this is just a try lock, and the value is dropped // immediately after, so there's no risk of blocking ourselves // or any other threads + // when i implement try_clone this code will become less unsafe if let Some(value) = unsafe { self.try_lock_no_key() } { f.debug_struct("Mutex").field("data", &&*value).finish() } else { @@ -77,6 +78,9 @@ impl From for Mutex { } } +// We don't need a `get_mut` because we don't have mutex poisoning. Hurray! +// This is safe because you can't have a mutable reference to the lock if it's +// locked. Being locked requires an immutable reference because of the guard. impl AsMut for Mutex { fn as_mut(&mut self) -> &mut T { self.get_mut() diff --git a/src/rwlock/write_lock.rs b/src/rwlock/write_lock.rs index 8501cd8..2cf73cd 100644 --- a/src/rwlock/write_lock.rs +++ b/src/rwlock/write_lock.rs @@ -11,7 +11,9 @@ impl<'l, T: ?Sized + Debug, R: RawRwLock> Debug for WriteLock<'l, T, R> { // safety: this is just a try lock, and the value is dropped // immediately after, so there's no risk of blocking ourselves // or any other threads - if let Some(value) = unsafe { self.try_lock_no_key() } { + // It makes zero sense to try using an exclusive lock for this, so this + // is the only time when WriteLock does a read. + if let Some(value) = unsafe { self.0.try_read_no_key() } { f.debug_struct("WriteLock").field("data", &&*value).finish() } else { struct LockedPlaceholder; @@ -75,11 +77,8 @@ impl<'l, T: ?Sized, R: RawRwLock> WriteLock<'l, T, R> { self.0.try_write(key) } - /// Attempts to create an exclusive lock without a key. Locking this - /// without exclusive access to the key is undefined behavior. - pub(crate) unsafe fn try_lock_no_key(&self) -> Option> { - self.0.try_write_no_key() - } + // There's no `try_lock_no_key`. Instead, `try_read_no_key` is called on + // the referenced `RwLock`. /// Immediately drops the guard, and consequently releases the exclusive /// lock. -- cgit v1.2.3