diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/collection.rs | 125 | ||||
| -rw-r--r-- | src/collection/boxed.rs | 510 | ||||
| -rw-r--r-- | src/collection/collection.rs | 291 | ||||
| -rw-r--r-- | src/collection/guard.rs | 33 | ||||
| -rw-r--r-- | src/collection/owned.rs | 347 | ||||
| -rw-r--r-- | src/collection/ref.rs | 399 | ||||
| -rw-r--r-- | src/collection/retry.rs | 619 | ||||
| -rw-r--r-- | src/collection/utils.rs | 44 | ||||
| -rw-r--r-- | src/key.rs | 9 | ||||
| -rw-r--r-- | src/lib.rs | 120 | ||||
| -rw-r--r-- | src/lockable.rs | 877 | ||||
| -rw-r--r-- | src/mutex.rs | 29 | ||||
| -rw-r--r-- | src/mutex/guard.rs | 75 | ||||
| -rw-r--r-- | src/mutex/mutex.rs | 38 | ||||
| -rw-r--r-- | src/rwlock.rs | 8 | ||||
| -rw-r--r-- | src/rwlock/read_guard.rs | 52 | ||||
| -rw-r--r-- | src/rwlock/read_lock.rs | 22 | ||||
| -rw-r--r-- | src/rwlock/rwlock.rs | 79 | ||||
| -rw-r--r-- | src/rwlock/write_guard.rs | 37 | ||||
| -rw-r--r-- | src/rwlock/write_lock.rs | 35 |
20 files changed, 2740 insertions, 1009 deletions
diff --git a/src/collection.rs b/src/collection.rs index c6cbe2d..27ec1c4 100644 --- a/src/collection.rs +++ b/src/collection.rs @@ -1,23 +1,130 @@ use std::marker::PhantomData; -use crate::{key::Keyable, lockable::Lockable}; +use crate::{key::Keyable, lockable::RawLock}; -mod collection; +mod boxed; mod guard; +mod owned; +mod r#ref; +mod retry; +mod utils; -/// A type which can be locked. +/// 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. To do this, it is very -/// important that no duplicate locks are included within. -#[derive(Debug, Clone, Copy)] -pub struct LockCollection<L> { +/// 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` + +// this type caches the idea that no immutable references to the underlying +// collection exist +#[derive(Debug)] +pub struct OwnedLockCollection<L> { + data: L, +} + +/// 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` + +// 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>, +} + +/// 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` + +// This type caches the sorting order of the locks and the fact that it doesn't +// contain any duplicates. +pub struct BoxedLockCollection<L> { + data: Box<L>, + 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. +/// +/// 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 + +// This type caches the fact that there are no duplicates +#[derive(Debug)] +pub struct RetryingLockCollection<L> { data: L, } /// A RAII guard for a generic [`Lockable`] type. -pub struct LockGuard<'a, 'key: 'a, L: Lockable<'a>, Key: Keyable + 'key> { - guard: L::Output, +/// +/// [`Lockable`]: `crate::lockable::Lockable` +pub struct LockGuard<'key, Guard, Key: Keyable + 'key> { + guard: Guard, key: Key, _phantom: PhantomData<&'key ()>, } diff --git a/src/collection/boxed.rs b/src/collection/boxed.rs new file mode 100644 index 0000000..5ced6d1 --- /dev/null +++ b/src/collection/boxed.rs @@ -0,0 +1,510 @@ +use std::fmt::Debug; +use std::marker::PhantomData; + +use crate::lockable::{Lockable, OwnedLockable, RawLock, Sharable}; +use crate::Keyable; + +use super::{utils, BoxedLockCollection, LockGuard}; + +/// returns `true` if the sorted list contains a duplicate +#[must_use] +fn contains_duplicates(l: &[&dyn RawLock]) -> bool { + l.windows(2) + .any(|window| std::ptr::eq(window[0], window[1])) +} + +unsafe impl<L: Lockable> Lockable for BoxedLockCollection<L> { + type Guard<'g> = L::Guard<'g> where Self: 'g; + + type ReadGuard<'g> = L::ReadGuard<'g> where Self: 'g; + + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { + 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<L: Sharable> Sharable for BoxedLockCollection<L> {} + +unsafe impl<L: OwnedLockable> OwnedLockable for BoxedLockCollection<L> {} + +impl<L> IntoIterator for BoxedLockCollection<L> +where + L: IntoIterator, +{ + type Item = <L as IntoIterator>::Item; + type IntoIter = <L as IntoIterator>::IntoIter; + + fn into_iter(self) -> Self::IntoIter { + self.data.into_iter() + } +} + +impl<'a, L> IntoIterator for &'a BoxedLockCollection<L> +where + &'a L: IntoIterator, +{ + type Item = <&'a L as IntoIterator>::Item; + type IntoIter = <&'a L as IntoIterator>::IntoIter; + + fn into_iter(self) -> Self::IntoIter { + self.data.into_iter() + } +} + +impl<'a, L> IntoIterator for &'a mut BoxedLockCollection<L> +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<L: OwnedLockable, I: FromIterator<L> + OwnedLockable> FromIterator<L> + for BoxedLockCollection<I> +{ + fn from_iter<T: IntoIterator<Item = L>>(iter: T) -> Self { + let iter: I = iter.into_iter().collect(); + Self::new(iter) + } +} + +impl<E: OwnedLockable + Extend<L>, L: OwnedLockable> Extend<L> for BoxedLockCollection<E> { + fn extend<T: IntoIterator<Item = L>>(&mut self, iter: T) { + self.data.extend(iter) + } +} + +impl<L> AsRef<L> for BoxedLockCollection<L> { + fn as_ref(&self) -> &L { + &self.data + } +} + +impl<L> AsMut<L> for BoxedLockCollection<L> { + fn as_mut(&mut self) -> &mut L { + &mut self.data + } +} + +impl<L: Debug> Debug for BoxedLockCollection<L> { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + f.debug_struct(stringify!(BoxedLockCollection)) + .field("data", &self.data) + .finish_non_exhaustive() + } +} + +impl<L: OwnedLockable + Default> Default for BoxedLockCollection<L> { + fn default() -> Self { + Self::new(L::default()) + } +} + +impl<L: OwnedLockable + Default> From<L> for BoxedLockCollection<L> { + fn from(value: L) -> Self { + Self::new(value) + } +} + +impl<L: OwnedLockable> BoxedLockCollection<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(data); + /// ``` + #[must_use] + pub fn new(data: L) -> Self { + // safety: owned lockable types cannot contain duplicates + unsafe { Self::new_unchecked(data) } + } +} + +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 + unsafe { Self::new_unchecked(data) } + } +} + +impl<L: Lockable> BoxedLockCollection<L> { + /// Creates a new collections of locks. + /// + /// # Safety + /// + /// This results in undefined behavior if any locks are presented twice + /// within this collection. + /// + /// # Examples + /// + /// ``` + /// use happylock::{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); + + // 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 + // safe to just pretend they're static + let locks = std::mem::transmute(locks); + 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<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) + } + } + + /// 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<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, 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, + ) -> 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, + } + } + + /// 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, + ) -> Option<LockGuard<'key, L::Guard<'g>, Key>> { + let guard = unsafe { + if !utils::ordered_try_lock(&self.locks) { + return None; + } + + // safety: we've acquired the locks + self.data.guard() + }; + + Some(LockGuard { + guard, + key, + _phantom: PhantomData, + }) + } + + /// Unlocks the underlying lockable data type, returning the key that's + /// associated with it. + /// + /// # Examples + /// + /// ``` + /// use happylock::{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<i32>, Mutex<&str>)>::unlock(guard); + /// ``` + pub fn unlock<'key, Key: Keyable + 'key>(guard: LockGuard<'key, L::Guard<'_>, Key>) -> Key { + drop(guard.guard); + guard.key + } +} + +impl<L: Sharable> BoxedLockCollection<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, 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, + ) -> 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, + } + } + + /// 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, + ) -> Option<LockGuard<'key, L::ReadGuard<'g>, Key>> { + let guard = unsafe { + if !utils::ordered_try_read(&self.locks) { + return None; + } + + // safety: we've acquired the locks + self.data.read_guard() + }; + + Some(LockGuard { + guard, + key, + _phantom: PhantomData, + }) + } + + /// 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<i32>, RwLock<&str>)>::unlock_read(guard); + /// ``` + 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<L> +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() + } +} + +impl<'a, L: 'a> BoxedLockCollection<L> +where + &'a mut L: IntoIterator, +{ + /// 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/collection.rs b/src/collection/collection.rs deleted file mode 100644 index 22a2d11..0000000 --- a/src/collection/collection.rs +++ /dev/null @@ -1,291 +0,0 @@ -use std::marker::PhantomData; - -use crate::{key::Keyable, Lockable, OwnedLockable}; - -use super::{LockCollection, LockGuard}; - -/// returns `true` if the list contains a duplicate -#[must_use] -fn contains_duplicates(l: &mut [usize]) -> bool { - l.sort_unstable(); - l.windows(2).any(|w| w[0] == w[1]) -} - -impl<'a, L: OwnedLockable<'a>> From<L> for LockCollection<L> { - fn from(value: L) -> Self { - Self::new(value) - } -} - -impl<'a, L: Lockable<'a>> AsRef<L> for LockCollection<L> { - fn as_ref(&self) -> &L { - &self.data - } -} - -impl<'a, L: Lockable<'a>> AsMut<L> for LockCollection<L> { - fn as_mut(&mut self) -> &mut L { - &mut self.data - } -} - -impl<'a, L: Lockable<'a>> AsRef<Self> for LockCollection<L> { - fn as_ref(&self) -> &Self { - self - } -} - -impl<'a, L: Lockable<'a>> AsMut<Self> for LockCollection<L> { - fn as_mut(&mut self) -> &mut Self { - self - } -} - -impl<L: IntoIterator> IntoIterator for LockCollection<L> { - type Item = L::Item; - type IntoIter = L::IntoIter; - - fn into_iter(self) -> Self::IntoIter { - self.data.into_iter() - } -} - -impl<'a, L> IntoIterator for &'a LockCollection<L> -where - &'a L: IntoIterator, -{ - type Item = <&'a L as IntoIterator>::Item; - type IntoIter = <&'a L as IntoIterator>::IntoIter; - - fn into_iter(self) -> Self::IntoIter { - self.data.into_iter() - } -} - -impl<'a, L> IntoIterator for &'a mut LockCollection<L> -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<'a, L: OwnedLockable<'a>, I: FromIterator<L> + OwnedLockable<'a>> FromIterator<L> - for LockCollection<I> -{ - fn from_iter<T: IntoIterator<Item = L>>(iter: T) -> Self { - let iter: I = iter.into_iter().collect(); - Self::new(iter) - } -} - -impl<'a, E: OwnedLockable<'a> + Extend<L>, L: OwnedLockable<'a>> Extend<L> for LockCollection<E> { - fn extend<T: IntoIterator<Item = L>>(&mut self, iter: T) { - self.data.extend(iter) - } -} - -impl<'a, L: OwnedLockable<'a>> LockCollection<L> { - /// Creates a new collection of owned locks. - /// - /// Because the locks are owned, there's no need to do any checks for - /// duplicate values. - /// - /// # Examples - /// - /// ``` - /// use happylock::{LockCollection, Mutex}; - /// - /// let lock = LockCollection::new((Mutex::new(0), Mutex::new(""))); - /// ``` - #[must_use] - pub const fn new(data: L) -> Self { - Self { data } - } - - /// Creates a new collection of owned locks. - /// - /// Because the locks are owned, there's no need to do any checks for - /// duplicate values. - /// - /// # Examples - /// - /// ``` - /// use happylock::{LockCollection, Mutex}; - /// - /// let data = (Mutex::new(0), Mutex::new("")); - /// let lock = LockCollection::new_ref(&data); - /// ``` - #[must_use] - pub const fn new_ref(data: &L) -> LockCollection<&L> { - LockCollection { data } - } -} - -impl<L> LockCollection<L> { - /// Creates a new collections of locks. - /// - /// # Safety - /// - /// This results in undefined behavior if any locks are presented twice - /// within this collection. - /// - /// # Examples - /// - /// ``` - /// use happylock::{LockCollection, Mutex}; - /// - /// let data1 = Mutex::new(0); - /// let data2 = Mutex::new(""); - /// - /// // safety: data1 and data2 refer to distinct mutexes - /// let lock = unsafe { LockCollection::new_unchecked((&data1, &data2)) }; - /// ``` - #[must_use] - pub const unsafe fn new_unchecked(data: L) -> Self { - Self { data } - } -} - -impl<'a, L: Lockable<'a>> LockCollection<L> { - /// Creates a new collection of locks. - /// - /// This returns `None` if any locks are found twice in the given - /// collection. - /// - /// # Performance - /// - /// This does a check at runtime to make sure that the collection contains - /// no two copies of the same lock. This is an `O(n^2)` operation. Prefer - /// [`LockCollection::new`] or [`LockCollection::new_ref`] instead. - /// - /// # Examples - /// - /// ``` - /// use happylock::{LockCollection, Mutex}; - /// - /// let data1 = Mutex::new(0); - /// let data2 = Mutex::new(""); - /// - /// // data1 and data2 refer to distinct mutexes, so this won't panic - /// let lock = LockCollection::try_new((&data1, &data2)).unwrap(); - /// ``` - #[must_use] - pub fn try_new(data: L) -> Option<Self> { - let mut ptrs = data.get_ptrs(); - if contains_duplicates(&mut ptrs) { - return None; - } - - Some(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::{LockCollection, Mutex, ThreadKey}; - /// - /// let key = ThreadKey::get().unwrap(); - /// let lock = LockCollection::new((Mutex::new(0), Mutex::new(""))); - /// - /// let mut guard = lock.lock(key); - /// *guard.0 += 1; - /// *guard.1 = "1"; - /// ``` - pub fn lock<'key: 'a, Key: Keyable + 'key>(&'a self, key: Key) -> LockGuard<'a, 'key, L, Key> { - LockGuard { - // safety: we have the thread's key - guard: unsafe { self.data.lock() }, - key, - _phantom: PhantomData, - } - } - - /// Attempts to lock the without blocking. - /// - /// If successful, this method returns a guard that can be used to access - /// the data, and unlocks the data when it is dropped. Otherwise, `None` is - /// returned. - /// - /// # Examples - /// - /// ``` - /// use happylock::{LockCollection, Mutex, ThreadKey}; - /// - /// let key = ThreadKey::get().unwrap(); - /// let lock = LockCollection::new((Mutex::new(0), Mutex::new(""))); - /// - /// match lock.try_lock(key) { - /// Some(mut guard) => { - /// *guard.0 += 1; - /// *guard.1 = "1"; - /// }, - /// None => unreachable!(), - /// }; - /// - /// ``` - pub fn try_lock<'key: 'a, Key: Keyable + 'key>( - &'a self, - key: Key, - ) -> Option<LockGuard<'a, 'key, L, Key>> { - // safety: we have the thread's key - unsafe { self.data.try_lock() }.map(|guard| LockGuard { - guard, - key, - _phantom: PhantomData, - }) - } - - /// Unlocks the underlying lockable data type, returning the key that's - /// associated with it. - /// - /// # Examples - /// - /// ``` - /// use happylock::{LockCollection, Mutex, ThreadKey}; - /// - /// let key = ThreadKey::get().unwrap(); - /// let lock = LockCollection::new((Mutex::new(0), Mutex::new(""))); - /// - /// let mut guard = lock.lock(key); - /// *guard.0 += 1; - /// *guard.1 = "1"; - /// let key = LockCollection::unlock(guard); - /// ``` - #[allow(clippy::missing_const_for_fn)] - pub fn unlock<'key: 'a, Key: Keyable + 'key>(guard: LockGuard<'a, 'key, L, Key>) -> Key { - drop(guard.guard); - guard.key - } -} - -impl<'a, L: 'a> LockCollection<L> -where - &'a L: IntoIterator, -{ - /// Returns an iterator over references to each value in the collection. - pub fn iter(&'a self) -> <&'a L as IntoIterator>::IntoIter { - self.into_iter() - } -} - -impl<'a, L: 'a> LockCollection<L> -where - &'a mut L: IntoIterator, -{ - /// Returns an iterator over mutable references to each value in the - /// collection. - 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 110a935..8857c5f 100644 --- a/src/collection/guard.rs +++ b/src/collection/guard.rs @@ -1,19 +1,44 @@ +use std::fmt::{Debug, Display}; use std::ops::{Deref, DerefMut}; -use crate::{key::Keyable, Lockable}; +use crate::key::Keyable; use super::LockGuard; -impl<'a, 'key: 'a, L: Lockable<'a>, Key: Keyable> Deref for LockGuard<'a, 'key, L, Key> { - type Target = L::Output; +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; fn deref(&self) -> &Self::Target { &self.guard } } -impl<'a, 'key: 'a, L: Lockable<'a>, Key: Keyable> DerefMut for LockGuard<'a, 'key, L, Key> { +impl<'key, Guard, Key: Keyable> DerefMut for LockGuard<'key, Guard, Key> { fn deref_mut(&mut self) -> &mut Self::Target { &mut self.guard } } + +impl<'key, Guard, Key: Keyable> AsRef<Guard> for LockGuard<'key, Guard, Key> { + fn as_ref(&self) -> &Guard { + &self.guard + } +} + +impl<'key, Guard, Key: Keyable> AsMut<Guard> 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 new file mode 100644 index 0000000..919c403 --- /dev/null +++ b/src/collection/owned.rs @@ -0,0 +1,347 @@ +use std::marker::PhantomData; + +use crate::lockable::{Lockable, OwnedLockable, RawLock, Sharable}; +use crate::Keyable; + +use super::{utils, LockGuard, OwnedLockCollection}; + +fn get_locks<L: Lockable>(data: &L) -> Vec<&dyn RawLock> { + let mut locks = Vec::new(); + data.get_ptrs(&mut locks); + locks +} + +unsafe impl<L: Lockable> Lockable for OwnedLockCollection<L> { + type Guard<'g> = L::Guard<'g> where Self: 'g; + + type ReadGuard<'g> = L::ReadGuard<'g> where Self: 'g; + + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { + 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<L: Sharable> Sharable for OwnedLockCollection<L> {} + +unsafe impl<L: OwnedLockable> OwnedLockable for OwnedLockCollection<L> {} + +impl<L> IntoIterator for OwnedLockCollection<L> +where + L: IntoIterator, +{ + type Item = <L as IntoIterator>::Item; + type IntoIter = <L as IntoIterator>::IntoIter; + + fn into_iter(self) -> Self::IntoIter { + self.data.into_iter() + } +} + +impl<L: OwnedLockable, I: FromIterator<L> + OwnedLockable> FromIterator<L> + for OwnedLockCollection<I> +{ + fn from_iter<T: IntoIterator<Item = L>>(iter: T) -> Self { + let iter: I = iter.into_iter().collect(); + Self::new(iter) + } +} + +impl<E: OwnedLockable + Extend<L>, L: OwnedLockable> Extend<L> for OwnedLockCollection<E> { + fn extend<T: IntoIterator<Item = L>>(&mut self, iter: T) { + self.data.extend(iter) + } +} + +impl<L: OwnedLockable> AsMut<L> for OwnedLockCollection<L> { + fn as_mut(&mut self) -> &mut L { + &mut self.data + } +} + +impl<L: OwnedLockable + Default> Default for OwnedLockCollection<L> { + fn default() -> Self { + Self::new(L::default()) + } +} + +impl<L: OwnedLockable + Default> From<L> for OwnedLockCollection<L> { + fn from(value: L) -> Self { + Self::new(value) + } +} + +impl<L: OwnedLockable> OwnedLockCollection<L> { + /// 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, + ) -> LockGuard<'key, L::Guard<'g>, Key> { + let locks = get_locks(&self.data); + for lock in locks { + // safety: we have the thread key, and these locks happen in a + // predetermined order + unsafe { lock.lock() }; + } + + // safety: we've locked all of this already + let guard = unsafe { self.data.guard() }; + LockGuard { + guard, + key, + _phantom: PhantomData, + } + } + + /// 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, + ) -> Option<LockGuard<'key, L::Guard<'g>, Key>> { + let locks = get_locks(&self.data); + let guard = unsafe { + if !utils::ordered_try_lock(&locks) { + return None; + } + + // safety: we've acquired the locks + self.data.guard() + }; + + Some(LockGuard { + guard, + key, + _phantom: PhantomData, + }) + } + + /// Unlocks the underlying lockable data type, returning the key that's + /// associated with it. + /// + /// # Examples + /// + /// ``` + /// use happylock::{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<i32>, 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>, + ) -> Key { + drop(guard.guard); + guard.key + } +} + +impl<L: Sharable> OwnedLockCollection<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::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, + ) -> LockGuard<'key, L::ReadGuard<'g>, Key> { + let locks = get_locks(&self.data); + for lock in locks { + // safety: we have the thread key, and these locks happen in a + // predetermined order + unsafe { lock.read() }; + } + + // safety: we've locked all of this already + let guard = unsafe { self.data.read_guard() }; + LockGuard { + guard, + key, + _phantom: PhantomData, + } + } + + /// 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, + ) -> Option<LockGuard<'key, L::ReadGuard<'g>, Key>> { + let locks = get_locks(&self.data); + let guard = unsafe { + if !utils::ordered_try_read(&locks) { + return None; + } + + // safety: we've acquired the locks + self.data.read_guard() + }; + + Some(LockGuard { + guard, + key, + _phantom: PhantomData, + }) + } + + /// 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<i32>, 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>, + ) -> Key { + drop(guard.guard); + guard.key + } +} diff --git a/src/collection/ref.rs b/src/collection/ref.rs new file mode 100644 index 0000000..d8c7f2e --- /dev/null +++ b/src/collection/ref.rs @@ -0,0 +1,399 @@ +use std::fmt::Debug; +use std::marker::PhantomData; + +use crate::lockable::{Lockable, OwnedLockable, RawLock, Sharable}; +use crate::Keyable; + +use super::{utils, LockGuard, RefLockCollection}; + +#[must_use] +pub fn get_locks<L: Lockable>(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)); + locks +} + +/// returns `true` if the sorted list contains a duplicate +#[must_use] +fn contains_duplicates(l: &[&dyn RawLock]) -> bool { + l.windows(2) + .any(|window| std::ptr::eq(window[0], window[1])) +} + +impl<'a, L> AsRef<L> for RefLockCollection<'a, L> { + fn as_ref(&self) -> &L { + self.data + } +} + +impl<'a, L> IntoIterator for &'a RefLockCollection<'a, L> +where + &'a L: IntoIterator, +{ + type Item = <&'a L as IntoIterator>::Item; + type IntoIter = <&'a L as IntoIterator>::IntoIter; + + fn into_iter(self) -> Self::IntoIter { + self.data.into_iter() + } +} + +unsafe impl<'c, L: Lockable> Lockable for RefLockCollection<'c, L> { + type Guard<'g> = L::Guard<'g> where Self: 'g; + + type ReadGuard<'g> = L::ReadGuard<'g> where Self: 'g; + + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { + ptrs.extend_from_slice(&self.locks); + } + + unsafe fn guard(&self) -> Self::Guard<'_> { + self.data.guard() + } + + unsafe fn read_guard(&self) -> Self::ReadGuard<'_> { + self.data.read_guard() + } +} + +unsafe impl<'c, L: Sharable> Sharable for RefLockCollection<'c, L> {} + +impl<'a, L: 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. + /// + /// Because the locks are owned, there's no need to do any checks for + /// duplicate values. + /// + /// # Examples + /// + /// ``` + /// use happylock::Mutex; + /// use happylock::collection::RefLockCollection; + /// + /// let data = (Mutex::new(0), Mutex::new("")); + /// let lock = RefLockCollection::new(&data); + /// ``` + #[must_use] + pub fn new(data: &'a L) -> RefLockCollection<L> { + RefLockCollection { + locks: get_locks(data), + data, + } + } +} + +impl<'a, L: Lockable> RefLockCollection<'a, L> { + /// Creates a new collections of locks. + /// + /// # Safety + /// + /// This results in undefined behavior if any locks are presented twice + /// within this collection. + /// + /// # Examples + /// + /// ``` + /// use happylock::Mutex; + /// use happylock::collection::RefLockCollection; + /// + /// let data1 = Mutex::new(0); + /// let data2 = Mutex::new(""); + /// + /// // safety: data1 and data2 refer to distinct mutexes + /// let data = (&data1, &data2); + /// let lock = unsafe { RefLockCollection::new_unchecked(&data) }; + /// ``` + #[must_use] + pub unsafe fn new_unchecked(data: &'a L) -> Self { + Self { + data, + locks: get_locks(data), + } + } + + /// Creates a new collection of locks. + /// + /// This returns `None` if any locks are found twice in the given + /// collection. + /// + /// # Examples + /// + /// ``` + /// use happylock::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 data = (&data1, &data2); + /// let lock = RefLockCollection::try_new(&data).unwrap(); + /// ``` + #[must_use] + pub fn try_new(data: &'a L) -> Option<Self> { + let locks = get_locks(data); + if contains_duplicates(&locks) { + return None; + } + + Some(Self { data, locks }) + } + + /// 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::RefLockCollection; + /// + /// let key = ThreadKey::get().unwrap(); + /// let data = (Mutex::new(0), Mutex::new("")); + /// let lock = RefLockCollection::new(&data); + /// + /// let mut guard = lock.lock(key); + /// *guard.0 += 1; + /// *guard.1 = "1"; + /// ``` + pub fn lock<'key: 'a, Key: Keyable + 'key>( + &'a self, + key: Key, + ) -> LockGuard<'key, L::Guard<'a>, Key> { + for lock in &self.locks { + // safety: we have the thread key + unsafe { lock.lock() }; + } + + LockGuard { + // safety: we've already acquired the lock + guard: unsafe { self.data.guard() }, + key, + _phantom: PhantomData, + } + } + + /// Attempts to lock the without blocking. + /// + /// If successful, this method returns a guard that can be used to access + /// the data, and unlocks the data when it is dropped. Otherwise, `None` is + /// returned. + /// + /// # Examples + /// + /// ``` + /// use happylock::{Mutex, ThreadKey}; + /// use happylock::collection::RefLockCollection; + /// + /// let key = ThreadKey::get().unwrap(); + /// let data = (Mutex::new(0), Mutex::new("")); + /// let lock = RefLockCollection::new(&data); + /// + /// match lock.try_lock(key) { + /// Some(mut guard) => { + /// *guard.0 += 1; + /// *guard.1 = "1"; + /// }, + /// None => unreachable!(), + /// }; + /// + /// ``` + pub fn try_lock<'key: 'a, Key: Keyable + 'key>( + &'a self, + key: Key, + ) -> Option<LockGuard<'key, L::Guard<'a>, Key>> { + let guard = unsafe { + if !utils::ordered_try_lock(&self.locks) { + return None; + } + + // safety: we've acquired the locks + self.data.guard() + }; + + Some(LockGuard { + guard, + key, + _phantom: PhantomData, + }) + } + + /// Unlocks the underlying lockable data type, returning the key that's + /// associated with it. + /// + /// # Examples + /// + /// ``` + /// use happylock::{Mutex, ThreadKey}; + /// use happylock::collection::RefLockCollection; + /// + /// let key = ThreadKey::get().unwrap(); + /// 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 = RefLockCollection::<(Mutex<i32>, 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 { + drop(guard.guard); + guard.key + } +} + +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, + ) -> LockGuard<'key, L::ReadGuard<'a>, 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, + } + } + + /// 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, + ) -> Option<LockGuard<'key, L::ReadGuard<'a>, Key>> { + let guard = unsafe { + if !utils::ordered_try_read(&self.locks) { + return None; + } + + // safety: we've acquired the locks + self.data.read_guard() + }; + + Some(LockGuard { + guard, + key, + _phantom: PhantomData, + }) + } + + /// 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<i32>, 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>, + ) -> Key { + drop(guard.guard); + guard.key + } +} + +impl<'a, L: 'a> RefLockCollection<'a, L> +where + &'a L: IntoIterator, +{ + /// Returns an iterator over references to each value in the collection. + /// + /// # 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 new file mode 100644 index 0000000..2b9b0a0 --- /dev/null +++ b/src/collection/retry.rs @@ -0,0 +1,619 @@ +use crate::lockable::{Lockable, OwnedLockable, RawLock, Sharable}; +use crate::Keyable; + +use std::collections::HashSet; +use std::marker::PhantomData; + +use super::{LockGuard, RetryingLockCollection}; + +/// Checks that a collection contains no duplicate references to a lock. +fn contains_duplicates<L: Lockable>(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::with_capacity(locks.len()); + for lock in locks { + if !locks_set.insert(lock) { + return true; + } + } + + false +} + +unsafe impl<L: Lockable> Lockable for RetryingLockCollection<L> { + type Guard<'g> = L::Guard<'g> where Self: 'g; + + type ReadGuard<'g> = L::ReadGuard<'g> where Self: 'g; + + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { + 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<L: Sharable> Sharable for RetryingLockCollection<L> {} + +unsafe impl<L: OwnedLockable> OwnedLockable for RetryingLockCollection<L> {} + +impl<L> IntoIterator for RetryingLockCollection<L> +where + L: IntoIterator, +{ + type Item = <L as IntoIterator>::Item; + type IntoIter = <L as IntoIterator>::IntoIter; + + fn into_iter(self) -> Self::IntoIter { + self.data.into_iter() + } +} + +impl<'a, L> IntoIterator for &'a RetryingLockCollection<L> +where + &'a L: IntoIterator, +{ + type Item = <&'a L as IntoIterator>::Item; + type IntoIter = <&'a L as IntoIterator>::IntoIter; + + fn into_iter(self) -> Self::IntoIter { + self.data.into_iter() + } +} + +impl<'a, L> IntoIterator for &'a mut RetryingLockCollection<L> +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<L: OwnedLockable, I: FromIterator<L> + OwnedLockable> FromIterator<L> + for RetryingLockCollection<I> +{ + fn from_iter<T: IntoIterator<Item = L>>(iter: T) -> Self { + let iter: I = iter.into_iter().collect(); + Self::new(iter) + } +} + +impl<E: OwnedLockable + Extend<L>, L: OwnedLockable> Extend<L> for RetryingLockCollection<E> { + fn extend<T: IntoIterator<Item = L>>(&mut self, iter: T) { + self.data.extend(iter) + } +} + +impl<L> AsRef<L> for RetryingLockCollection<L> { + fn as_ref(&self) -> &L { + &self.data + } +} + +impl<L> AsMut<L> for RetryingLockCollection<L> { + fn as_mut(&mut self) -> &mut L { + &mut self.data + } +} + +impl<L: OwnedLockable + Default> Default for RetryingLockCollection<L> { + fn default() -> Self { + Self::new(L::default()) + } +} + +impl<L: OwnedLockable> From<L> for RetryingLockCollection<L> { + fn from(value: L) -> Self { + Self::new(value) + } +} + +impl<L: OwnedLockable> RetryingLockCollection<L> { + /// 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 } + } +} + +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 } + } +} + +impl<L: Lockable> RetryingLockCollection<L> { + /// Creates a new collections of locks. + /// + /// # Safety + /// + /// This results in undefined behavior if any locks are presented twice + /// within this collection. + /// + /// # Examples + /// + /// ``` + /// use happylock::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<Self> { + (!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, + ) -> LockGuard<'key, L::Guard<'g>, Key> { + let mut first_index = 0; + let mut locks = Vec::new(); + self.data.get_ptrs(&mut locks); + + if locks.is_empty() { + return LockGuard { + // safety: there's no data being returned + guard: unsafe { self.data.guard() }, + key, + _phantom: PhantomData, + }; + } + + let guard = unsafe { + 'outer: loop { + // safety: we have the thread key + locks[first_index].lock(); + for (i, lock) in locks.iter().enumerate() { + if i == first_index { + continue; + } + + // safety: we have the thread key + if !lock.try_lock() { + for lock in locks.iter().take(i) { + // safety: we already locked all of these + lock.unlock(); + } + + if first_index >= i { + // safety: this is already locked and can't be unlocked + // by the previous loop + locks[first_index].unlock(); + } + + first_index = i; + continue 'outer; + } + } + + // safety: we locked all the data + break self.data.guard(); + } + }; + + LockGuard { + guard, + key, + _phantom: PhantomData, + } + } + + /// 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, + ) -> Option<LockGuard<'key, L::Guard<'g>, Key>> { + let mut locks = Vec::new(); + self.data.get_ptrs(&mut locks); + + if locks.is_empty() { + return Some(LockGuard { + // safety: there's no data being returned + guard: unsafe { self.data.guard() }, + key, + _phantom: PhantomData, + }); + } + + let guard = unsafe { + for (i, lock) in locks.iter().enumerate() { + // safety: we have the thread key + if !lock.try_lock() { + for lock in locks.iter().take(i) { + // safety: we already locked all of these + lock.unlock(); + } + return None; + } + } + + // safety: we locked all the data + self.data.guard() + }; + + Some(LockGuard { + guard, + key, + _phantom: PhantomData, + }) + } + + /// 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<i32>, Mutex<&str>)>::unlock(guard); + /// ``` + pub fn unlock<'key, Key: Keyable + 'key>(guard: LockGuard<'key, L::Guard<'_>, Key>) -> Key { + drop(guard.guard); + guard.key + } +} + +impl<L: Sharable> RetryingLockCollection<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::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, + ) -> LockGuard<'key, L::ReadGuard<'g>, Key> { + let mut first_index = 0; + let mut locks = Vec::new(); + self.data.get_ptrs(&mut locks); + + if locks.is_empty() { + return LockGuard { + // safety: there's no data being returned + guard: unsafe { self.data.read_guard() }, + key, + _phantom: PhantomData, + }; + } + + let guard = unsafe { + 'outer: loop { + // safety: we have the thread key + locks[first_index].read(); + for (i, lock) in locks.iter().enumerate() { + if i == first_index { + continue; + } + + // safety: we have the thread key + if !lock.try_read() { + for lock in locks.iter().take(i) { + // safety: we already locked all of these + lock.unlock_read(); + } + + if first_index >= i { + // safety: this is already locked and can't be unlocked + // by the previous loop + locks[first_index].unlock_read(); + } + + first_index = i; + continue 'outer; + } + } + + // safety: we locked all the data + break self.data.read_guard(); + } + }; + + LockGuard { + guard, + key, + _phantom: PhantomData, + } + } + + /// 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, + ) -> Option<LockGuard<'key, L::ReadGuard<'g>, Key>> { + let mut locks = Vec::new(); + self.data.get_ptrs(&mut locks); + + if locks.is_empty() { + return Some(LockGuard { + // safety: there's no data being returned + guard: unsafe { self.data.read_guard() }, + key, + _phantom: PhantomData, + }); + } + + let guard = unsafe { + for (i, lock) in locks.iter().enumerate() { + // safety: we have the thread key + if !lock.try_read() { + for lock in locks.iter().take(i) { + // safety: we already locked all of these + lock.unlock_read(); + } + return None; + } + } + + // safety: we locked all the data + self.data.read_guard() + }; + + Some(LockGuard { + guard, + key, + _phantom: PhantomData, + }) + } + + /// 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<i32>, RwLock<&str>)>::unlock_read(guard); + /// ``` + pub fn unlock_read<'key, Key: Keyable + 'key>( + guard: LockGuard<'key, L::ReadGuard<'_>, Key>, + ) -> Key { + drop(guard.guard); + guard.key + } +} + +impl<'a, L: 'a> RetryingLockCollection<L> +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() + } +} + +impl<'a, L: 'a> RetryingLockCollection<L> +where + &'a mut L: IntoIterator, +{ + /// 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/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 + } +} @@ -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,12 +17,15 @@ 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<ThreadLocal<AtomicLock>> = Lazy::new(ThreadLocal::new); /// The key for the current thread. /// /// Only one of these exist per thread. To get the current thread's key, call -/// [`ThreadKey::get`]. If the `ThreadKey` is dropped, it can be reobtained. +/// [`ThreadKey::get`]. If the `ThreadKey` is dropped, it can be re-obtained. pub struct ThreadKey { phantom: PhantomData<*const ()>, // implement !Send and !Sync } @@ -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() } @@ -14,7 +14,7 @@ //! # Theory //! //! There are four conditions necessary for a deadlock to occur. In order to -//! prevent deadlocks, we need to prevent one of the following: +//! prevent deadlocks, we just need to prevent one of the following: //! //! 1. mutual exclusion //! 2. non-preemptive allocation @@ -22,29 +22,15 @@ //! 4. **partial allocation** //! //! This library seeks to solve **partial allocation** by requiring total -//! allocation. All of the resources a thread needs must be allocated at the -//! same time. In order to request new resources, the old resources must be -//! dropped first. Requesting multiple resources at once is atomic. You either -//! get all of the requested resources or none at all. +//! allocation. All the resources a thread needs must be allocated at the same +//! time. In order to request new resources, the old resources must be dropped +//! first. Requesting multiple resources at once is atomic. You either get all +//! the requested resources or none at all. //! -//! # Performance -//! -//! **Avoid [`LockCollection::try_new`].** This constructor will check to make -//! sure that the collection contains no duplicate locks. This is an O(n^2) -//! operation, where n is the number of locks in the collection. -//! [`LockCollection::new`] and [`LockCollection::new_ref`] don't need these -//! checks because they use [`OwnedLockable`], which is guaranteed to be unique -//! as long as it is accessible. As a last resort, -//! [`LockCollection::new_unchecked`] doesn't do this check, but is unsafe to -//! call. -//! -//! **Avoid using distinct lock orders for [`LockCollection`].** The problem is -//! that this library must iterate through the list of locks, and not complete -//! until every single one of them is unlocked. This also means that attempting -//! to lock multiple mutexes gives you a lower chance of ever running. Only one -//! needs to be locked for the operation to need a reset. This problem can be -//! prevented by not doing that in your code. Resources should be obtained in -//! the same order on every thread. +//! As an optimization, this library also often prevents **circular wait**. +//! Many collections sort the locks in order of their memory address. As long +//! as the locks are always acquired in that order, then time doesn't need to +//! be wasted on releasing locks after a failure and re-acquiring them later. //! //! # Examples //! @@ -105,21 +91,101 @@ //! println!("{}", *data.0); //! println!("{}", *data.1); //! ``` +//! +//! In many cases, the [`LockCollection::new`] or [`LockCollection::new_ref`] +//! method can be used, improving performance. +//! +//! ```rust +//! use std::thread; +//! use happylock::{LockCollection, Mutex, ThreadKey}; +//! +//! const N: usize = 100; +//! +//! static DATA: [Mutex<i32>; 2] = [Mutex::new(0), Mutex::new(1)]; +//! +//! for _ in 0..N { +//! thread::spawn(move || { +//! let key = ThreadKey::get().unwrap(); +//! +//! // a reference to a type that implements `OwnedLockable` will never +//! // contain duplicates, so no duplicate checking is needed. +//! let collection = LockCollection::new_ref(&DATA); +//! let mut guard = collection.lock(key); +//! +//! let x = *guard[1]; +//! *guard[1] += *guard[0]; +//! *guard[0] = x; +//! }); +//! } +//! +//! let key = ThreadKey::get().unwrap(); +//! let data = LockCollection::new_ref(&DATA); +//! let data = data.lock(key); +//! println!("{}", data[0]); +//! println!("{}", data[1]); +//! ``` +//! +//! # Performance +//! +//! **The `ThreadKey` is a mostly-zero cost abstraction.** It doesn't use any +//! memory, and it doesn't really exist at run-time. The only cost comes from +//! calling `ThreadKey::get()`, because the function has to ensure at runtime +//! that the key hasn't already been taken. Dropping the key will also have a +//! small cost. +//! +//! **Consider [`OwnedLockCollection`].** This will almost always be the +//! fastest lock collection. It doesn't expose the underlying collection +//! immutably, which means that it will always be locked in the same order, and +//! doesn't need any sorting. +//! +//! **Avoid [`LockCollection::try_new`].** This constructor will check to make +//! sure that the collection contains no duplicate locks. In most cases, this +//! is O(nlogn), where n is the number of locks in the collections but in the +//! case of [`RetryingLockCollection`], it's close to O(n). +//! [`LockCollection::new`] and [`LockCollection::new_ref`] don't need these +//! checks because they use [`OwnedLockable`], which is guaranteed to be unique +//! as long as it is accessible. As a last resort, +//! [`LockCollection::new_unchecked`] doesn't do this check, but is unsafe to +//! call. +//! +//! **Know how to use [`RetryingLockCollection`].** This collection doesn't do +//! any sorting, but uses a wasteful lock algorithm. It can't rely on the order +//! of the locks to be the same across threads, so if it finds a lock that it +//! can't acquire without blocking, it'll first release all of the locks it +//! already acquired to avoid blocking other threads. This is wasteful because +//! this algorithm may end up re-acquiring the same lock multiple times. To +//! avoid this, ensure that (1) the first lock in the collection is always the +//! first lock in any collection it appears in, and (2) the other locks in the +//! collection are always preceded by that first lock. This will prevent any +//! wasted time from re-acquiring locks. If you're unsure, [`LockCollection`] +//! is a sensible default. +//! +//! [`OwnedLockable`]: `lockable::OwnedLockable` +//! [`OwnedLockCollection`]: `collection::OwnedLockCollection` +//! [`RetryingLockCollection`]: `collection::RetryingLockCollection` -mod collection; mod key; -mod lockable; +pub mod collection; +pub mod lockable; pub mod mutex; pub mod rwlock; -pub use collection::LockCollection; pub use key::{Keyable, ThreadKey}; -pub use lockable::{Lockable, OwnedLockable}; #[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. +/// +/// [`BoxedLockCollection`]: collection::BoxedLockCollection +pub type LockCollection<L> = collection::BoxedLockCollection<L>; + /// 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 0dd9b07..9f44981 100644 --- a/src/lockable.rs +++ b/src/lockable.rs @@ -7,46 +7,35 @@ use crate::{ use lock_api::{RawMutex, RawRwLock}; -/// A type that may be locked and unlocked, and is known to be the only valid -/// instance of the lock. -/// -/// # Safety -/// -/// There must not be any two values which can unlock the value at the same -/// time, i.e., this must either be an owned value or a mutable reference. -pub unsafe trait OwnedLockable<'a>: Lockable<'a> {} - -/// 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 Lockable<'a> { - /// The output of the lock - type Output; - - /// Returns a list of all pointers to locks. This is used to ensure that - /// the same lock isn't included twice - #[must_use] - fn get_ptrs(&self) -> Vec<usize>; +// 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 /// /// # 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. - /// * Call this on multiple locks without unlocking first. + /// 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 lock(&'a self) -> Self::Output; + unsafe fn lock(&self); /// Attempt to lock without blocking. /// - /// Returns `Some` if successful, `None` otherwise. + /// Returns `true` if successful, `false` otherwise. /// /// # Safety /// @@ -55,649 +44,449 @@ pub unsafe trait Lockable<'a> { /// value is alive. /// /// [`ThreadKey`]: `crate::ThreadKey` - unsafe fn try_lock(&'a self) -> Option<Self::Output>; -} + unsafe fn try_lock(&self) -> bool; -unsafe impl<'a, T: Lockable<'a>> Lockable<'a> for &T { - type Output = T::Output; + /// Releases the lock + /// + /// # Safety + /// + /// It is undefined behavior to use this if the lock is not acquired + unsafe fn unlock(&self); - fn get_ptrs(&self) -> Vec<usize> { - (**self).get_ptrs() - } + /// 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); - unsafe fn lock(&'a self) -> Self::Output { - (**self).lock() - } + // 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; - unsafe fn try_lock(&'a self) -> Option<Self::Output> { - (**self).try_lock() - } + /// 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); } -unsafe impl<'a, T: Lockable<'a>> Lockable<'a> for &mut T { - type Output = T::Output; - - fn get_ptrs(&self) -> Vec<usize> { - (**self).get_ptrs() - } +/// A type that may be locked and unlocked. +/// +/// This trait is usually implemented on collections of [`RawLock`]s. For +/// example, a `Vec<Mutex<i32>>`. +/// +/// # 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 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; + + /// 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>); - unsafe fn lock(&'a self) -> Self::Output { - (**self).lock() - } + /// 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<'_>; - unsafe fn try_lock(&'a self) -> Option<Self::Output> { - (**self).try_lock() - } + /// 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<'_>; } -unsafe impl<'a, T: OwnedLockable<'a>> OwnedLockable<'a> for &mut T {} +/// 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 {} -unsafe impl<'a, T: 'a, R: RawMutex + 'a> Lockable<'a> for Mutex<T, R> { - type Output = MutexRef<'a, T, R>; +/// A type that may be locked and unlocked, and is known to be the only valid +/// instance of the lock. +/// +/// # Safety +/// +/// There must not be any two values which can unlock the value at the same +/// time, i.e., this must either be an owned value or a mutable reference. +pub unsafe trait OwnedLockable: Lockable {} - fn get_ptrs(&self) -> Vec<usize> { - vec![self as *const Self as usize] +unsafe impl<T: Send, R: RawMutex + Send + Sync> RawLock for Mutex<T, R> { + unsafe fn lock(&self) { + self.raw().lock() } - unsafe fn lock(&'a self) -> Self::Output { - self.lock_no_key() + unsafe fn try_lock(&self) -> bool { + self.raw().try_lock() } - unsafe fn try_lock(&'a self) -> Option<Self::Output> { - self.try_lock_no_key() + unsafe fn unlock(&self) { + self.raw().unlock() } -} - -unsafe impl<'a, T: 'a, R: RawRwLock + 'a> Lockable<'a> for RwLock<T, R> { - type Output = RwLockWriteRef<'a, T, R>; - fn get_ptrs(&self) -> Vec<usize> { - vec![self as *const Self as usize] + // 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() } - unsafe fn lock(&'a self) -> Self::Output { - self.write_no_key() + unsafe fn try_read(&self) -> bool { + self.raw().try_lock() } - unsafe fn try_lock(&'a self) -> Option<Self::Output> { - self.try_write_no_key() + unsafe fn unlock_read(&self) { + self.raw().unlock() } } -unsafe impl<'a, T: 'a, R: RawMutex + 'a> OwnedLockable<'a> for Mutex<T, R> {} +unsafe impl<T: Send, R: RawRwLock + Send + Sync> RawLock for RwLock<T, R> { + unsafe fn lock(&self) { + self.raw().lock_exclusive() + } -unsafe impl<'a, T: 'a, R: RawRwLock + 'a> OwnedLockable<'a> for RwLock<T, R> {} + unsafe fn try_lock(&self) -> bool { + self.raw().try_lock_exclusive() + } -unsafe impl<'a, T: 'a, R: RawRwLock + 'a> Lockable<'a> for ReadLock<'a, T, R> { - type Output = RwLockReadRef<'a, T, R>; + unsafe fn unlock(&self) { + self.raw().unlock_exclusive() + } - fn get_ptrs(&self) -> Vec<usize> { - vec![self.as_ref() as *const RwLock<T, R> as usize] + unsafe fn read(&self) { + self.raw().lock_shared() } - unsafe fn lock(&'a self) -> Self::Output { - self.lock_no_key() + unsafe fn try_read(&self) -> bool { + self.raw().try_lock_shared() } - unsafe fn try_lock(&'a self) -> Option<Self::Output> { - self.try_lock_no_key() + unsafe fn unlock_read(&self) { + self.raw().unlock_shared() } } -unsafe impl<'a, T: 'a, R: RawRwLock + 'a> Lockable<'a> for WriteLock<'a, T, R> { - type Output = RwLockWriteRef<'a, T, R>; +unsafe impl<T: Send, R: RawMutex + Send + Sync> Lockable for Mutex<T, R> { + type Guard<'g> = MutexRef<'g, T, R> where Self: 'g; + type ReadGuard<'g> = MutexRef<'g, T, R> where Self: 'g; - fn get_ptrs(&self) -> Vec<usize> { - vec![self.as_ref() as *const RwLock<T, R> as usize] + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { + ptrs.push(self); } - unsafe fn lock(&'a self) -> Self::Output { - self.lock_no_key() + unsafe fn guard(&self) -> Self::Guard<'_> { + MutexRef::new(self) } - unsafe fn try_lock(&'a self) -> Option<Self::Output> { - self.try_lock_no_key() + unsafe fn read_guard(&self) -> Self::ReadGuard<'_> { + MutexRef::new(self) } } -unsafe impl<'a, A: Lockable<'a>> Lockable<'a> for (A,) { - type Output = (A::Output,); +unsafe impl<T: Send, R: RawRwLock + Send + Sync> Lockable for RwLock<T, R> { + type Guard<'g> = RwLockWriteRef<'g, T, R> where Self: 'g; + + type ReadGuard<'g> = RwLockReadRef<'g, T, R> where Self: 'g; - fn get_ptrs(&self) -> Vec<usize> { - let mut ptrs = Vec::with_capacity(1); - ptrs.append(&mut self.0.get_ptrs()); - ptrs + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { + ptrs.push(self); } - unsafe fn lock(&'a self) -> Self::Output { - (self.0.lock(),) + unsafe fn guard(&self) -> Self::Guard<'_> { + RwLockWriteRef::new(self) } - unsafe fn try_lock(&'a self) -> Option<Self::Output> { - self.0.try_lock().map(|a| (a,)) + unsafe fn read_guard(&self) -> Self::ReadGuard<'_> { + RwLockReadRef::new(self) } } -unsafe impl<'a, A: Lockable<'a>, B: Lockable<'a>> Lockable<'a> for (A, B) { - type Output = (A::Output, B::Output); +unsafe impl<T: Send, R: RawRwLock + Send + Sync> Sharable for RwLock<T, R> {} - fn get_ptrs(&self) -> Vec<usize> { - let mut ptrs = Vec::with_capacity(2); - ptrs.append(&mut self.0.get_ptrs()); - ptrs.append(&mut self.1.get_ptrs()); - ptrs - } +unsafe impl<T: Send, R: RawMutex + Send + Sync> OwnedLockable for Mutex<T, R> {} - unsafe fn lock(&'a self) -> Self::Output { - loop { - let lock0 = self.0.lock(); - let Some(lock1) = self.1.try_lock() else { - drop(lock0); - std::thread::yield_now(); - continue; - }; +unsafe impl<T: Send, R: RawRwLock + Send + Sync> OwnedLockable for RwLock<T, R> {} - return (lock0, lock1); - } +unsafe impl<'l, T: Send, R: RawRwLock + Send + Sync> Lockable for ReadLock<'l, T, R> { + type Guard<'g> = RwLockReadRef<'g, T, R> where Self: 'g; + + type ReadGuard<'g> = RwLockReadRef<'g, T, R> where Self: 'g; + + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { + ptrs.push(self.as_ref()); } - unsafe fn try_lock(&'a self) -> Option<Self::Output> { - let Some(lock0) = self.0.try_lock() else { - return None; - }; - let Some(lock1) = self.1.try_lock() else { - return None; - }; + unsafe fn guard(&self) -> Self::Guard<'_> { + RwLockReadRef::new(self.as_ref()) + } - Some((lock0, lock1)) + unsafe fn read_guard(&self) -> Self::Guard<'_> { + RwLockReadRef::new(self.as_ref()) } } -unsafe impl<'a, A: Lockable<'a>, B: Lockable<'a>, C: Lockable<'a>> Lockable<'a> for (A, B, C) { - type Output = (A::Output, B::Output, C::Output); - - fn get_ptrs(&self) -> Vec<usize> { - let mut ptrs = Vec::with_capacity(3); - ptrs.append(&mut self.0.get_ptrs()); - ptrs.append(&mut self.1.get_ptrs()); - ptrs.append(&mut self.2.get_ptrs()); - ptrs - } - - unsafe fn lock(&'a self) -> Self::Output { - loop { - let lock0 = self.0.lock(); - let Some(lock1) = self.1.try_lock() else { - drop(lock0); - std::thread::yield_now(); - continue; - }; - let Some(lock2) = self.2.try_lock() else { - drop(lock0); - drop(lock1); - std::thread::yield_now(); - continue; - }; - - return (lock0, lock1, lock2); - } +unsafe impl<'l, T: Send, R: RawRwLock + Send + Sync> Lockable for WriteLock<'l, T, R> { + type Guard<'g> = RwLockWriteRef<'g, T, R> where Self: 'g; + + type ReadGuard<'g> = RwLockWriteRef<'g, T, R> where Self: 'g; + + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { + ptrs.push(self.as_ref()); } - unsafe fn try_lock(&'a self) -> Option<Self::Output> { - let Some(lock0) = self.0.try_lock() else { - return None; - }; - let Some(lock1) = self.1.try_lock() else { - return None; - }; - let Some(lock2) = self.2.try_lock() else { - return None; - }; + unsafe fn guard(&self) -> Self::Guard<'_> { + RwLockWriteRef::new(self.as_ref()) + } - Some((lock0, lock1, lock2)) + unsafe fn read_guard(&self) -> Self::Guard<'_> { + RwLockWriteRef::new(self.as_ref()) } } -unsafe impl<'a, A: Lockable<'a>, B: Lockable<'a>, C: Lockable<'a>, D: Lockable<'a>> Lockable<'a> - for (A, B, C, D) -{ - type Output = (A::Output, B::Output, C::Output, D::Output); - - fn get_ptrs(&self) -> Vec<usize> { - let mut ptrs = Vec::with_capacity(4); - ptrs.append(&mut self.0.get_ptrs()); - ptrs.append(&mut self.1.get_ptrs()); - ptrs.append(&mut self.2.get_ptrs()); - ptrs.append(&mut self.3.get_ptrs()); - ptrs - } - - unsafe fn lock(&'a self) -> Self::Output { - loop { - let lock0 = self.0.lock(); - let Some(lock1) = self.1.try_lock() else { - drop(lock0); - std::thread::yield_now(); - continue; - }; - let Some(lock2) = self.2.try_lock() else { - drop(lock0); - drop(lock1); - std::thread::yield_now(); - continue; - }; - let Some(lock3) = self.3.try_lock() else { - drop(lock0); - drop(lock1); - drop(lock2); - std::thread::yield_now(); - continue; - }; - - return (lock0, lock1, lock2, lock3); - } - } +// 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 fn try_lock(&'a self) -> Option<Self::Output> { - let Some(lock0) = self.0.try_lock() else { - return None; - }; - let Some(lock1) = self.1.try_lock() else { - return None; - }; - let Some(lock2) = self.2.try_lock() else { - return None; - }; - let Some(lock3) = self.3.try_lock() else { - return None; - }; +unsafe impl<T: Lockable> Lockable for &T { + type Guard<'g> = T::Guard<'g> where Self: 'g; - Some((lock0, lock1, lock2, lock3)) + type ReadGuard<'g> = T::ReadGuard<'g> where Self: 'g; + + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { + (*self).get_ptrs(ptrs); } -} -unsafe impl<'a, A: Lockable<'a>, B: Lockable<'a>, C: Lockable<'a>, D: Lockable<'a>, E: Lockable<'a>> - Lockable<'a> for (A, B, C, D, E) -{ - type Output = (A::Output, B::Output, C::Output, D::Output, E::Output); - - fn get_ptrs(&self) -> Vec<usize> { - let mut ptrs = Vec::with_capacity(5); - ptrs.append(&mut self.0.get_ptrs()); - ptrs.append(&mut self.1.get_ptrs()); - ptrs.append(&mut self.2.get_ptrs()); - ptrs.append(&mut self.3.get_ptrs()); - ptrs.append(&mut self.4.get_ptrs()); - ptrs - } - - unsafe fn lock(&'a self) -> Self::Output { - loop { - let lock0 = self.0.lock(); - let Some(lock1) = self.1.try_lock() else { - drop(lock0); - std::thread::yield_now(); - continue; - }; - let Some(lock2) = self.2.try_lock() else { - drop(lock0); - drop(lock1); - std::thread::yield_now(); - continue; - }; - let Some(lock3) = self.3.try_lock() else { - drop(lock0); - drop(lock1); - drop(lock2); - std::thread::yield_now(); - continue; - }; - let Some(lock4) = self.4.try_lock() else { - drop(lock0); - drop(lock1); - drop(lock2); - drop(lock3); - std::thread::yield_now(); - continue; - }; - - return (lock0, lock1, lock2, lock3, lock4); - } + unsafe fn guard(&self) -> Self::Guard<'_> { + (*self).guard() } - unsafe fn try_lock(&'a self) -> Option<Self::Output> { - let Some(lock0) = self.0.try_lock() else { - return None; - }; - let Some(lock1) = self.1.try_lock() else { - return None; - }; - let Some(lock2) = self.2.try_lock() else { - return None; - }; - let Some(lock3) = self.3.try_lock() else { - return None; - }; - let Some(lock4) = self.4.try_lock() else { - return None; - }; - - Some((lock0, lock1, lock2, lock3, lock4)) + unsafe fn read_guard(&self) -> Self::ReadGuard<'_> { + (*self).read_guard() } } -unsafe impl< - 'a, - A: Lockable<'a>, - B: Lockable<'a>, - C: Lockable<'a>, - D: Lockable<'a>, - E: Lockable<'a>, - F: Lockable<'a>, - > Lockable<'a> for (A, B, C, D, E, F) -{ - type Output = ( - A::Output, - B::Output, - C::Output, - D::Output, - E::Output, - F::Output, - ); - - fn get_ptrs(&self) -> Vec<usize> { - let mut ptrs = Vec::with_capacity(6); - ptrs.append(&mut self.0.get_ptrs()); - ptrs.append(&mut self.1.get_ptrs()); - ptrs.append(&mut self.2.get_ptrs()); - ptrs.append(&mut self.3.get_ptrs()); - ptrs.append(&mut self.4.get_ptrs()); - ptrs.append(&mut self.5.get_ptrs()); - ptrs - } - - unsafe fn lock(&'a self) -> Self::Output { - loop { - let lock0 = self.0.lock(); - let Some(lock1) = self.1.try_lock() else { - drop(lock0); - std::thread::yield_now(); - continue; - }; - let Some(lock2) = self.2.try_lock() else { - drop(lock0); - drop(lock1); - std::thread::yield_now(); - continue; - }; - let Some(lock3) = self.3.try_lock() else { - drop(lock0); - drop(lock1); - drop(lock2); - std::thread::yield_now(); - continue; - }; - let Some(lock4) = self.4.try_lock() else { - drop(lock0); - drop(lock1); - drop(lock2); - drop(lock3); - std::thread::yield_now(); - continue; - }; - let Some(lock5) = self.5.try_lock() else { - drop(lock0); - drop(lock1); - drop(lock2); - drop(lock3); - drop(lock4); - std::thread::yield_now(); - continue; - }; - - return (lock0, lock1, lock2, lock3, lock4, lock5); - } +unsafe impl<T: Sharable> Sharable for &T {} + +unsafe impl<T: Lockable> Lockable for &mut T { + type Guard<'g> = T::Guard<'g> where Self: 'g; + + type ReadGuard<'g> = T::ReadGuard<'g> where Self: 'g; + + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { + (**self).get_ptrs(ptrs) } - unsafe fn try_lock(&'a self) -> Option<Self::Output> { - let Some(lock0) = self.0.try_lock() else { - return None; - }; - let Some(lock1) = self.1.try_lock() else { - return None; - }; - let Some(lock2) = self.2.try_lock() else { - return None; - }; - let Some(lock3) = self.3.try_lock() else { - return None; - }; - let Some(lock4) = self.4.try_lock() else { - return None; - }; - let Some(lock5) = self.5.try_lock() else { - return None; - }; - - Some((lock0, lock1, lock2, lock3, lock4, lock5)) + unsafe fn guard(&self) -> Self::Guard<'_> { + (**self).guard() } -} -unsafe impl<'a, A: OwnedLockable<'a>> OwnedLockable<'a> for (A,) {} -unsafe impl<'a, A: OwnedLockable<'a>, B: OwnedLockable<'a>> OwnedLockable<'a> for (A, B) {} -unsafe impl<'a, A: OwnedLockable<'a>, B: OwnedLockable<'a>, C: OwnedLockable<'a>> OwnedLockable<'a> - for (A, B, C) -{ -} -unsafe impl< - 'a, - A: OwnedLockable<'a>, - B: OwnedLockable<'a>, - C: OwnedLockable<'a>, - D: OwnedLockable<'a>, - > OwnedLockable<'a> for (A, B, C, D) -{ -} -unsafe impl< - 'a, - A: OwnedLockable<'a>, - B: OwnedLockable<'a>, - C: OwnedLockable<'a>, - D: OwnedLockable<'a>, - E: OwnedLockable<'a>, - > OwnedLockable<'a> for (A, B, C, D, E) -{ -} -unsafe impl< - 'a, - A: OwnedLockable<'a>, - B: OwnedLockable<'a>, - C: OwnedLockable<'a>, - D: OwnedLockable<'a>, - E: OwnedLockable<'a>, - F: OwnedLockable<'a>, - > OwnedLockable<'a> for (A, B, C, D, E, F) -{ + unsafe fn read_guard(&self) -> Self::ReadGuard<'_> { + (**self).read_guard() + } } -unsafe impl<'a, T: Lockable<'a>, const N: usize> Lockable<'a> for [T; N] { - type Output = [T::Output; N]; +unsafe impl<T: Sharable> Sharable for &mut T {} - fn get_ptrs(&self) -> Vec<usize> { - let mut ptrs = Vec::with_capacity(N); - for lock in self { - ptrs.append(&mut lock.get_ptrs()); - } - ptrs - } - - unsafe fn lock(&'a self) -> Self::Output { - unsafe fn unlock_partial<'a, T: Lockable<'a>, const N: usize>( - guards: [MaybeUninit<T::Output>; N], - upto: usize, - ) { - for (i, guard) in guards.into_iter().enumerate() { - if i == upto { - break; - } - drop(guard.assume_init()); +unsafe impl<T: OwnedLockable> 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,)*) { + type Guard<'g> = ($($generic::Guard<'g>,)*) where Self: 'g; + + type ReadGuard<'g> = ($($generic::ReadGuard<'g>,)*) where Self: 'g; + + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { + self.0.get_ptrs(ptrs); } - } - 'outer: loop { - let mut outputs = MaybeUninit::<[MaybeUninit<T::Output>; N]>::uninit().assume_init(); - if N == 0 { - return outputs.map(|mu| mu.assume_init()); + 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(),)*) } - outputs[0].write(self[0].lock()); - for i in 1..N { - match self[i].try_lock() { - Some(guard) => outputs[i].write(guard), - None => { - unlock_partial::<T, N>(outputs, i); - std::thread::yield_now(); - continue 'outer; - } - }; + unsafe fn read_guard(&self) -> Self::ReadGuard<'_> { + ($(self.$value.read_guard(),)*) } + } + + unsafe impl<$($generic: Sharable,)*> Sharable for ($($generic,)*) {} + + unsafe impl<$($generic: OwnedLockable,)*> OwnedLockable for ($($generic,)*) {} + }; +} + +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<T: Lockable, const N: usize> Lockable for [T; N] { + type Guard<'g> = [T::Guard<'g>; N] where Self: 'g; - return outputs.map(|mu| mu.assume_init()); + type ReadGuard<'g> = [T::ReadGuard<'g>; N] where Self: 'g; + + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { + for lock in self { + lock.get_ptrs(ptrs); } } - unsafe fn try_lock(&'a self) -> Option<Self::Output> { - unsafe fn unlock_partial<'a, T: Lockable<'a>, const N: usize>( - guards: [MaybeUninit<T::Output>; N], - upto: usize, - ) { - for (i, guard) in guards.into_iter().enumerate() { - if i == upto { - break; - } - drop(guard.assume_init()); - } + 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<T::Guard<'g>>; N]>::uninit().assume_init(); + for i in 0..N { + guards[i].write(self[i].guard()); } - let mut outputs = MaybeUninit::<[MaybeUninit<T::Output>; N]>::uninit().assume_init(); - for i in 1..N { - match self[i].try_lock() { - Some(guard) => outputs[i].write(guard), - None => { - unlock_partial::<T, N>(outputs, i); - return None; - } - }; + guards.map(|g| g.assume_init()) + } + + unsafe fn read_guard<'g>(&'g self) -> Self::ReadGuard<'g> { + let mut guards = MaybeUninit::<[MaybeUninit<T::ReadGuard<'g>>; N]>::uninit().assume_init(); + for i in 0..N { + guards[i].write(self[i].read_guard()); } - Some(outputs.map(|mu| mu.assume_init())) + guards.map(|g| g.assume_init()) } } -unsafe impl<'a, T: Lockable<'a>> Lockable<'a> for Box<[T]> { - type Output = Box<[T::Output]>; +unsafe impl<T: Lockable> Lockable for Box<[T]> { + type Guard<'g> = Box<[T::Guard<'g>]> where Self: 'g; + + type ReadGuard<'g> = Box<[T::ReadGuard<'g>]> where Self: 'g; - fn get_ptrs(&self) -> Vec<usize> { - let mut ptrs = Vec::with_capacity(self.len()); - for lock in &**self { - ptrs.append(&mut lock.get_ptrs()); + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { + for lock in self.iter() { + lock.get_ptrs(ptrs); } - ptrs } - unsafe fn lock(&'a self) -> Self::Output { - if self.is_empty() { - return Box::new([]); + unsafe fn guard(&self) -> Self::Guard<'_> { + let mut guards = Vec::new(); + for lock in self.iter() { + guards.push(lock.guard()); } - 'outer: loop { - let mut outputs = Vec::with_capacity(self.len()); - - outputs.push(self[0].lock()); - for lock in self.iter().skip(1) { - match lock.try_lock() { - Some(guard) => { - outputs.push(guard); - } - None => { - drop(outputs); - std::thread::yield_now(); - continue 'outer; - } - }; - } - - return outputs.into_boxed_slice(); - } + guards.into_boxed_slice() } - unsafe fn try_lock(&'a self) -> Option<Self::Output> { - let mut outputs = Vec::with_capacity(self.len()); - for lock in &**self { - match lock.try_lock() { - Some(guard) => { - outputs.push(guard); - } - None => return None, - }; + unsafe fn read_guard(&self) -> Self::ReadGuard<'_> { + let mut guards = Vec::new(); + for lock in self.iter() { + guards.push(lock.read_guard()); } - Some(outputs.into_boxed_slice()) + guards.into_boxed_slice() } } -unsafe impl<'a, T: Lockable<'a>> Lockable<'a> for Vec<T> { - type Output = Vec<T::Output>; +unsafe impl<T: Lockable> Lockable for Vec<T> { + // 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; - fn get_ptrs(&self) -> Vec<usize> { - let mut ptrs = Vec::with_capacity(self.len()); + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { for lock in self { - ptrs.append(&mut lock.get_ptrs()); + lock.get_ptrs(ptrs); } - ptrs } - unsafe fn lock(&'a self) -> Self::Output { - if self.is_empty() { - return Vec::new(); + unsafe fn guard(&self) -> Self::Guard<'_> { + let mut guards = Vec::new(); + for lock in self { + guards.push(lock.guard()); } - 'outer: loop { - let mut outputs = Vec::with_capacity(self.len()); - - outputs.push(self[0].lock()); - for lock in self.iter().skip(1) { - match lock.try_lock() { - Some(guard) => { - outputs.push(guard); - } - None => { - drop(outputs); - std::thread::yield_now(); - continue 'outer; - } - }; - } - - return outputs; - } + guards.into_boxed_slice() } - unsafe fn try_lock(&'a self) -> Option<Self::Output> { - let mut outputs = Vec::with_capacity(self.len()); + unsafe fn read_guard(&self) -> Self::ReadGuard<'_> { + let mut guards = Vec::new(); for lock in self { - match lock.try_lock() { - Some(guard) => { - outputs.push(guard); - } - None => return None, - }; + guards.push(lock.read_guard()); } - Some(outputs) + guards.into_boxed_slice() } } -unsafe impl<'a, T: OwnedLockable<'a>, const N: usize> OwnedLockable<'a> for [T; N] {} -unsafe impl<'a, T: OwnedLockable<'a>> OwnedLockable<'a> for Box<[T]> {} -unsafe impl<'a, T: OwnedLockable<'a>> OwnedLockable<'a> for Vec<T> {} +// I'd make a generic impl<T: Lockable, I: IntoIterator<Item=T>> Lockable for I +// but I think that'd require sealing up this trait + +unsafe impl<T: Sharable, const N: usize> Sharable for [T; N] {} +unsafe impl<T: Sharable> Sharable for Box<[T]> {} +unsafe impl<T: Sharable> Sharable for Vec<T> {} + +unsafe impl<T: OwnedLockable, const N: usize> OwnedLockable for [T; N] {} +unsafe impl<T: OwnedLockable> OwnedLockable for Box<[T]> {} +unsafe impl<T: OwnedLockable> OwnedLockable for Vec<T> {} diff --git a/src/mutex.rs b/src/mutex.rs index cef338e..b30c2b1 100644 --- a/src/mutex.rs +++ b/src/mutex.rs @@ -49,32 +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 ()>, } - -struct MutexLockFuture<'a, T: ?Sized + 'a, R: RawMutex> { - mutex: &'a Mutex<T, R>, - key: Option<crate::ThreadKey>, -} - -impl<'a, T: ?Sized + 'a, R: RawMutex> std::future::Future for MutexLockFuture<'a, T, R> { - type Output = MutexGuard<'a, 'a, T, crate::ThreadKey, R>; - - fn poll( - mut self: std::pin::Pin<&mut Self>, - cx: &mut std::task::Context<'_>, - ) -> std::task::Poll<Self::Output> { - match unsafe { self.mutex.try_lock_no_key() } { - Some(guard) => std::task::Poll::Ready(unsafe { - MutexGuard::new(guard.0, self.key.take().unwrap()) - }), - None => { - cx.waker().wake_by_ref(); - std::task::Poll::Pending - } - } - } -} diff --git a/src/mutex/guard.rs b/src/mutex/guard.rs index c7f25e4..f9324ad 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,21 @@ 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) + } +} + +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,6 +51,49 @@ impl<'a, T: ?Sized + 'a, R: RawMutex> DerefMut for MutexRef<'a, T, R> { } } +impl<'a, T: ?Sized + 'a, R: RawMutex> AsRef<T> for MutexRef<'a, T, R> { + fn as_ref(&self) -> &T { + self + } +} + +impl<'a, T: ?Sized + 'a, R: RawMutex> AsMut<T> for MutexRef<'a, T, R> { + fn as_mut(&mut self) -> &mut T { + self + } +} + +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<T, R>) -> 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> +{ + 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> { @@ -53,6 +112,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<T> + 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<T> + 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 917ab78..89dfef9 100644 --- a/src/mutex/mutex.rs +++ b/src/mutex/mutex.rs @@ -24,11 +24,22 @@ impl<T, R: RawMutex> Mutex<T, R> { data: UnsafeCell::new(data), } } -} -impl<T: ?Sized + Default, R: RawMutex> Default for Mutex<T, R> { - fn default() -> Self { - Self::new(T::default()) + /// Returns the raw underlying mutex. + /// + /// Note that you will most likely need to import the [`RawMutex`] trait + /// from `lock_api` to be able to call functions on the raw mutex. + /// + /// # Safety + /// + /// This method is unsafe because it allows unlocking a mutex while still + /// holding a reference to a [`MutexGuard`], and locking a mutex without + /// holding the [`ThreadKey`]. + /// + /// [`ThreadKey`]: `crate::ThreadKey` + #[must_use] + pub const unsafe fn raw(&self) -> &R { + &self.raw } } @@ -37,6 +48,7 @@ impl<T: ?Sized + Debug, R: RawMutex> Debug for Mutex<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 + // 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 { @@ -54,12 +66,21 @@ impl<T: ?Sized + Debug, R: RawMutex> Debug for Mutex<T, R> { } } +impl<T: ?Sized + Default, R: RawMutex> Default for Mutex<T, R> { + fn default() -> Self { + Self::new(T::default()) + } +} + impl<T, R: RawMutex> From<T> for Mutex<T, R> { fn from(value: T) -> Self { Self::new(value) } } +// 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<T: ?Sized, R> AsMut<T> for Mutex<T, R> { fn as_mut(&mut self) -> &mut T { self.get_mut() @@ -138,15 +159,6 @@ impl<T: ?Sized, R: RawMutex> Mutex<T, R> { } } - /// Lock without a [`ThreadKey`]. You must exclusively own the - /// [`ThreadKey`] as long as the [`MutexRef`] is alive. This may cause - /// deadlock if called multiple times without unlocking first. - pub(crate) unsafe fn lock_no_key(&self) -> MutexRef<'_, T, R> { - self.raw.lock(); - - MutexRef(self, PhantomData) - } - /// Attempts to lock the `Mutex` without blocking. /// /// # Errors diff --git a/src/rwlock.rs b/src/rwlock.rs index 7fb8c7a..8f1ba8f 100644 --- a/src/rwlock.rs +++ b/src/rwlock.rs @@ -22,7 +22,7 @@ pub type ParkingRwLock<T> = RwLock<T, parking_lot::RawRwLock>; /// A reader-writer lock /// /// This type of lock allows a number of readers or at most one writer at any -/// point in time. The write portion of thislock typically allows modification +/// point in time. The write portion of this lock typically allows modification /// of the underlying data (exclusive access) and the read portion of this lock /// typically allows for read-only access (shared access). /// @@ -56,7 +56,8 @@ pub struct RwLock<T: ?Sized, R> { /// that only read access is needed to the data. /// /// [`LockCollection`]: `crate::LockCollection` -pub struct ReadLock<'a, T: ?Sized, R>(&'a RwLock<T, R>); +#[repr(transparent)] +pub struct ReadLock<'l, T: ?Sized, R>(&'l RwLock<T, R>); /// Grants write access to an [`RwLock`] /// @@ -64,7 +65,8 @@ pub struct ReadLock<'a, T: ?Sized, R>(&'a RwLock<T, R>); /// that write access is needed to the data. /// /// [`LockCollection`]: `crate::LockCollection` -pub struct WriteLock<'a, T: ?Sized, R>(&'a RwLock<T, R>); +#[repr(transparent)] +pub struct WriteLock<'l, T: ?Sized, R>(&'l RwLock<T, R>); /// RAII structure that unlocks the shared read access to a [`RwLock`] pub struct RwLockReadRef<'a, T: ?Sized, R: RawRwLock>( diff --git a/src/rwlock/read_guard.rs b/src/rwlock/read_guard.rs index 532a6e7..1eb8bfc 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<T> 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 @@ -26,6 +45,31 @@ impl<'a, T: ?Sized + 'a, R: RawRwLock> Drop for RwLockReadRef<'a, T, R> { } } +impl<'a, T: ?Sized + 'a, R: RawRwLock> RwLockReadRef<'a, T, R> { + /// Creates an immutable reference for the underlying data of an [`RwLock`] + /// without locking it or taking ownership of the key. + #[must_use] + pub(crate) unsafe fn new(mutex: &'a RwLock<T, R>) -> Self { + Self(mutex, PhantomData) + } +} + +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> { @@ -36,6 +80,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<T> + 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/read_lock.rs b/src/rwlock/read_lock.rs index 176fc01..4f2bc86 100644 --- a/src/rwlock/read_lock.rs +++ b/src/rwlock/read_lock.rs @@ -6,7 +6,7 @@ use crate::key::Keyable; use super::{ReadLock, RwLock, RwLockReadGuard, RwLockReadRef}; -impl<'a, T: ?Sized + Debug, R: RawRwLock> Debug for ReadLock<'a, T, R> { +impl<'l, T: ?Sized + Debug, R: RawRwLock> Debug for ReadLock<'l, T, R> { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { // safety: this is just a try lock, and the value is dropped // immediately after, so there's no risk of blocking ourselves @@ -28,19 +28,19 @@ impl<'a, T: ?Sized + Debug, R: RawRwLock> Debug for ReadLock<'a, T, R> { } } -impl<'a, T: ?Sized, R> From<&'a RwLock<T, R>> for ReadLock<'a, T, R> { - fn from(value: &'a RwLock<T, R>) -> Self { +impl<'l, T, R> From<&'l RwLock<T, R>> for ReadLock<'l, T, R> { + fn from(value: &'l RwLock<T, R>) -> Self { Self::new(value) } } -impl<'a, T: ?Sized, R> AsRef<RwLock<T, R>> for ReadLock<'a, T, R> { +impl<'l, T: ?Sized, R> AsRef<RwLock<T, R>> for ReadLock<'l, T, R> { fn as_ref(&self) -> &RwLock<T, R> { self.0 } } -impl<'a, T: ?Sized, R> ReadLock<'a, T, R> { +impl<'l, T, R> ReadLock<'l, T, R> { /// Creates a new `ReadLock` which accesses the given [`RwLock`] /// /// # Examples @@ -52,12 +52,12 @@ impl<'a, T: ?Sized, R> ReadLock<'a, T, R> { /// let read_lock = ReadLock::new(&lock); /// ``` #[must_use] - pub const fn new(rwlock: &'a RwLock<T, R>) -> Self { + pub const fn new(rwlock: &'l RwLock<T, R>) -> Self { Self(rwlock) } } -impl<'a, T: ?Sized, R: RawRwLock> ReadLock<'a, T, R> { +impl<'l, T: ?Sized, R: RawRwLock> ReadLock<'l, T, R> { /// Locks the underlying [`RwLock`] with shared read access, blocking the /// current thread until it can be acquired. pub fn lock<'s, 'key: 's, Key: Keyable + 'key>( @@ -67,12 +67,6 @@ impl<'a, T: ?Sized, R: RawRwLock> ReadLock<'a, T, R> { self.0.read(key) } - /// Creates a shared lock without a key. Locking this without exclusive - /// access to the key is undefined behavior. - pub(crate) unsafe fn lock_no_key(&self) -> RwLockReadRef<'_, T, R> { - self.0.read_no_key() - } - /// Attempts to acquire the underlying [`RwLock`] with shared read access /// without blocking. pub fn try_lock<'s, 'key: 's, Key: Keyable + 'key>( @@ -88,7 +82,7 @@ impl<'a, T: ?Sized, R: RawRwLock> ReadLock<'a, T, R> { self.0.try_read_no_key() } - /// Immediately drops the guard, and consequentlyreleases the shared lock + /// Immediately drops the guard, and consequently releases the shared lock /// on the underlying [`RwLock`]. pub fn unlock<'key, Key: Keyable + 'key>(guard: RwLockReadGuard<'_, 'key, T, Key, R>) -> Key { RwLock::unlock_read(guard) diff --git a/src/rwlock/rwlock.rs b/src/rwlock/rwlock.rs index dc5ab30..5bff5a3 100644 --- a/src/rwlock/rwlock.rs +++ b/src/rwlock/rwlock.rs @@ -5,7 +5,7 @@ use lock_api::RawRwLock; use crate::key::Keyable; -use super::{RwLock, RwLockReadGuard, RwLockReadRef, RwLockWriteGuard, RwLockWriteRef}; +use super::{RwLock, RwLockReadGuard, RwLockReadRef, RwLockWriteGuard}; impl<T, R: RawRwLock> RwLock<T, R> { /// Creates a new instance of an `RwLock<T>` which is unlocked. @@ -24,11 +24,19 @@ impl<T, R: RawRwLock> RwLock<T, R> { raw: R::INIT, } } -} -impl<T: ?Sized + Default, R: RawRwLock> Default for RwLock<T, R> { - fn default() -> Self { - Self::new(T::default()) + /// Returns the underlying raw reader-writer lock object. + /// + /// Note that you will most likely need to import the [`RawRwLock`] trait + /// from `lock_api` to be able to call functions on the raw reader-writer + /// lock. + /// + /// # Safety + /// + /// This method is unsafe because it allows unlocking a mutex while + /// still holding a reference to a lock guard. + pub const unsafe fn raw(&self) -> &R { + &self.raw } } @@ -54,6 +62,12 @@ impl<T: ?Sized + Debug, R: RawRwLock> Debug for RwLock<T, R> { } } +impl<T: ?Sized + Default, R: RawRwLock> Default for RwLock<T, R> { + fn default() -> Self { + Self::new(T::default()) + } +} + impl<T, R: RawRwLock> From<T> for RwLock<T, R> { fn from(value: T) -> Self { Self::new(value) @@ -62,7 +76,7 @@ impl<T, R: RawRwLock> From<T> for RwLock<T, R> { impl<T: ?Sized, R> AsMut<T> for RwLock<T, R> { fn as_mut(&mut self) -> &mut T { - self.get_mut() + self.data.get_mut() } } @@ -82,32 +96,12 @@ impl<T, R> RwLock<T, R> { /// } /// assert_eq!(lock.into_inner(), "modified"); /// ``` + #[must_use] pub fn into_inner(self) -> T { self.data.into_inner() } } -impl<T: ?Sized, R> RwLock<T, R> { - /// Returns a mutable reference to the underlying data. - /// - /// Since this call borrows the `RwLock` mutably, no actual locking needs - /// to take place. The mutable borrow statically guarantees no locks exist. - /// - /// # Examples - /// - /// ``` - /// use happylock::{RwLock, ThreadKey}; - /// - /// let key = ThreadKey::get().unwrap(); - /// let mut lock = RwLock::new(0); - /// *lock.get_mut() = 10; - /// assert_eq!(*lock.read(key), 10); - /// ``` - pub fn get_mut(&mut self) -> &mut T { - self.data.get_mut() - } -} - impl<T: ?Sized, R: RawRwLock> RwLock<T, R> { /// Locks this `RwLock` with shared read access, blocking the current /// thread until it can be acquired. @@ -155,15 +149,6 @@ impl<T: ?Sized, R: RawRwLock> RwLock<T, R> { } } - /// Creates a shared lock without a key. Locking this without exclusive - /// access to the key is undefined behavior. - pub(crate) unsafe fn read_no_key(&self) -> RwLockReadRef<'_, T, R> { - self.raw.lock_shared(); - - // safety: the lock is locked first - RwLockReadRef(self, PhantomData) - } - /// Attempts to acquire this `RwLock` with shared read access without /// blocking. /// @@ -246,19 +231,10 @@ impl<T: ?Sized, R: RawRwLock> RwLock<T, R> { } } - /// Creates an exclusive lock without a key. Locking this without exclusive - /// access to the key is undefined behavior. - pub(crate) unsafe fn write_no_key(&self) -> RwLockWriteRef<'_, T, R> { - self.raw.lock_exclusive(); - - // safety: the lock is locked first - RwLockWriteRef(self, PhantomData) - } - /// Attempts to lock this `RwLock` with exclusive write access. /// /// This function does not block. If the lock could not be acquired at this - /// time, then `None` is returned. Otherwise an RAII guard is returned + /// time, then `None` is returned. Otherwise, an RAII guard is returned /// which will release the lock when it is dropped. /// /// This function does not provide any guarantees with respect to the @@ -290,17 +266,6 @@ impl<T: ?Sized, R: RawRwLock> RwLock<T, R> { } } - /// 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_write_no_key(&self) -> Option<RwLockWriteRef<'_, T, R>> { - if self.raw.try_lock_exclusive() { - // safety: the lock is locked first - Some(RwLockWriteRef(self, PhantomData)) - } else { - None - } - } - /// Unlocks shared access on the `RwLock`. This is undefined behavior is /// the data is still accessible. pub(super) unsafe fn force_unlock_read(&self) { diff --git a/src/rwlock/write_guard.rs b/src/rwlock/write_guard.rs index 6549822..5b41c99 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<T> for RwLockWriteRef<'a, T, R> { + fn as_ref(&self) -> &T { + self + } +} + +impl<'a, T: ?Sized + 'a, R: RawRwLock> AsMut<T> 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 @@ -35,6 +47,15 @@ impl<'a, T: ?Sized + 'a, R: RawRwLock> Drop for RwLockWriteRef<'a, T, R> { } } +impl<'a, T: ?Sized + 'a, R: RawRwLock> RwLockWriteRef<'a, T, R> { + /// Creates a reference to the underlying data of an [`RwLock`] without + /// locking or taking ownership of the key. + #[must_use] + pub(crate) unsafe fn new(mutex: &'a RwLock<T, R>) -> Self { + Self(mutex, PhantomData) + } +} + impl<'a, 'key: 'a, T: ?Sized + 'a, Key: Keyable, R: RawRwLock> Deref for RwLockWriteGuard<'a, 'key, T, Key, R> { @@ -53,6 +74,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<T> + 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<T> + 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> { diff --git a/src/rwlock/write_lock.rs b/src/rwlock/write_lock.rs index d7333ae..15eaacc 100644 --- a/src/rwlock/write_lock.rs +++ b/src/rwlock/write_lock.rs @@ -4,14 +4,16 @@ use lock_api::RawRwLock; use crate::key::Keyable; -use super::{RwLock, RwLockWriteGuard, RwLockWriteRef, WriteLock}; +use super::{RwLock, RwLockWriteGuard, WriteLock}; -impl<'a, T: ?Sized + Debug, R: RawRwLock> Debug for WriteLock<'a, T, R> { +impl<'l, T: ?Sized + Debug, R: RawRwLock> Debug for WriteLock<'l, T, R> { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { // safety: this is just a try lock, and the value is dropped // immediately after, so there's no risk of blocking ourselves // 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; @@ -21,26 +23,26 @@ impl<'a, T: ?Sized + Debug, R: RawRwLock> Debug for WriteLock<'a, T, R> { } } - f.debug_struct("ReadLock") + f.debug_struct("WriteLock") .field("data", &LockedPlaceholder) .finish() } } } -impl<'a, T: ?Sized, R> From<&'a RwLock<T, R>> for WriteLock<'a, T, R> { - fn from(value: &'a RwLock<T, R>) -> Self { +impl<'l, T, R> From<&'l RwLock<T, R>> for WriteLock<'l, T, R> { + fn from(value: &'l RwLock<T, R>) -> Self { Self::new(value) } } -impl<'a, T: ?Sized, R> AsRef<RwLock<T, R>> for WriteLock<'a, T, R> { +impl<'l, T: ?Sized, R> AsRef<RwLock<T, R>> for WriteLock<'l, T, R> { fn as_ref(&self) -> &RwLock<T, R> { self.0 } } -impl<'a, T: ?Sized, R> WriteLock<'a, T, R> { +impl<'l, T, R> WriteLock<'l, T, R> { /// Creates a new `WriteLock` which accesses the given [`RwLock`] /// /// # Examples @@ -52,12 +54,12 @@ impl<'a, T: ?Sized, R> WriteLock<'a, T, R> { /// let write_lock = WriteLock::new(&lock); /// ``` #[must_use] - pub const fn new(rwlock: &'a RwLock<T, R>) -> Self { + pub const fn new(rwlock: &'l RwLock<T, R>) -> Self { Self(rwlock) } } -impl<'a, T: ?Sized, R: RawRwLock> WriteLock<'a, T, R> { +impl<'l, T: ?Sized, R: RawRwLock> WriteLock<'l, T, R> { /// Locks the underlying [`RwLock`] with exclusive write access, blocking /// the current until it can be acquired. pub fn lock<'s, 'key: 's, Key: Keyable + 'key>( @@ -67,12 +69,6 @@ impl<'a, T: ?Sized, R: RawRwLock> WriteLock<'a, T, R> { self.0.write(key) } - /// Creates an exclusive lock without a key. Locking this without exclusive - /// access to the key is undefined behavior. - pub(crate) unsafe fn lock_no_key(&self) -> RwLockWriteRef<'_, T, R> { - self.0.write_no_key() - } - /// Attempts to lock the underlying [`RwLock`] with exclusive write access. pub fn try_lock<'s, 'key: 's, Key: Keyable + 'key>( &'s self, @@ -81,11 +77,8 @@ impl<'a, T: ?Sized, R: RawRwLock> WriteLock<'a, 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<RwLockWriteRef<'_, T, R>> { - 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. |