From 8ea16a606bfcc1ba535f6cef3cb4c162f91d2eb0 Mon Sep 17 00:00:00 2001 From: Mica White Date: Sat, 9 Mar 2024 14:48:25 -0500 Subject: RwLock --- README.md | 4 +- src/lib.rs | 13 ++- src/lockable.rs | 59 +++++++++- src/mutex.rs | 10 +- src/rwlock.rs | 342 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 419 insertions(+), 9 deletions(-) create mode 100644 src/rwlock.rs diff --git a/README.md b/README.md index a807c3a..a35e1f6 100644 --- a/README.md +++ b/README.md @@ -80,7 +80,7 @@ Although this library is able to successfully prevent deadlocks, livelocks may s I want to try to get this working without the standard library. There are a few problems with this though. For instance, this crate uses `thread_local` to allow other threads to have their own keys. Also, the only practical type of mutex that would work is a spinlock. Although, more could be implemented using the `RawMutex` trait. -Theoretically, it's possible to include the same mutex in a list twice, preventing the entire lock from being obtained. And this is technically a deadlock. A pretty easy to prevent deadlock, but a deadlock nonetheless. This is difficult to prevent, but could maybe be done by giving each mutex an ID, and then ensuring that the same ID doesn't appear twice in a list. This is an O(n^2) operation. +Theoretically, it's possible to include the same mutex in a list twice, preventing the entire lock from being obtained. And this is technically a deadlock. A pretty easy to prevent deadlock, but a deadlock nonetheless. This is difficult to prevent, but could maybe be done by giving each mutex an ID, and then ensuring that the same ID doesn't appear twice in a list. This is an O(n^2) operation, and using an `AtomicUsize` to make the IDs would mean that creating a mutex isn't `const`. More types might be lockable using a `LockGuard`. In addition, some sort of `DynamicLock` type might be useful so that, for example, a `Mutex` and an `RwLock` could be unlocked at the same time inside of a `Vec>`. Although, this wouldn't solve the problem of needing a `Mutex` and a `Mutex` at the same time. This would be better solved usin the existing tuple system. @@ -88,6 +88,6 @@ It'd be nice to be able to use the mutexes built into the operating system. Usin A more fair system for getting sets of locks would help, but I have no clue what that looks like. -A read-write lock would be very useful here, and maybe other primitives such as condvars and barriers? +Maybe adding other primitives such as condvars and barriers? Personally, I don't like mutex poisoning, but maybe it can be worked into the library if you're into that sort of thing. diff --git a/src/lib.rs b/src/lib.rs index 3d30330..3897615 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -7,10 +7,21 @@ mod guard; mod key; mod lockable; + pub mod mutex; +pub mod rwlock; pub use guard::LockGuard; pub use key::{Key, ThreadKey}; pub use lockable::Lockable; -pub use mutex::ParkingMutex as Mutex; pub use mutex::SpinLock; + +/// A mutual exclusion primitive useful for protecting shared data, which cannot deadlock. +/// +/// By default, this uses `parking_lot` as a backend. +pub type Mutex = mutex::Mutex; + +/// A reader-writer lock +/// +/// By default, this uses `parking_lot` as a backend. +pub type RwLock = rwlock::RwLock; diff --git a/src/lockable.rs b/src/lockable.rs index 4271fc8..050f856 100644 --- a/src/lockable.rs +++ b/src/lockable.rs @@ -1,7 +1,11 @@ use std::mem::MaybeUninit; -use crate::mutex::{Mutex, MutexRef}; -use lock_api::RawMutex; +use crate::{ + mutex::{Mutex, MutexRef}, + rwlock::{ReadLock, RwLock, RwLockReadRef, RwLockWriteRef, WriteLock}, +}; + +use lock_api::{RawMutex, RawRwLock}; mod sealed { use super::Lockable as L; @@ -10,6 +14,9 @@ mod sealed { pub trait Sealed {} impl<'a, T, R: RawMutex + 'a> Sealed for Mutex {} + impl<'a, T, R: RawRwLock + 'a> Sealed for RwLock {} + impl<'a, T, R: RawRwLock + 'a> Sealed for ReadLock<'a, T, R> {} + impl<'a, T, R: RawRwLock + 'a> Sealed for WriteLock<'a, T, R> {} impl Sealed for &T {} impl Sealed for &mut T {} impl<'a, A: L<'a>> Sealed for (A,) {} @@ -111,6 +118,54 @@ unsafe impl<'a, T: 'a, R: RawMutex + 'a> Lockable<'a> for Mutex { } } +unsafe impl<'a, T: 'a, R: RawRwLock + 'a> Lockable<'a> for RwLock { + type Output = RwLockWriteRef<'a, T, R>; + + unsafe fn lock(&'a self) -> Self::Output { + self.write_no_key() + } + + unsafe fn try_lock(&'a self) -> Option { + self.try_write_no_key() + } + + fn unlock(guard: Self::Output) { + drop(guard); + } +} + +unsafe impl<'a, T: 'a, R: RawRwLock + 'a> Lockable<'a> for ReadLock<'a, T, R> { + type Output = RwLockReadRef<'a, T, R>; + + unsafe fn lock(&'a self) -> Self::Output { + self.lock_no_key() + } + + unsafe fn try_lock(&'a self) -> Option { + self.try_lock_no_key() + } + + fn unlock(guard: Self::Output) { + drop(guard); + } +} + +unsafe impl<'a, T: 'a, R: RawRwLock + 'a> Lockable<'a> for WriteLock<'a, T, R> { + type Output = RwLockWriteRef<'a, T, R>; + + unsafe fn lock(&'a self) -> Self::Output { + self.lock_no_key() + } + + unsafe fn try_lock(&'a self) -> Option { + self.try_lock_no_key() + } + + fn unlock(guard: Self::Output) { + drop(guard); + } +} + unsafe impl<'a, A: Lockable<'a>> Lockable<'a> for (A,) { type Output = (A::Output,); diff --git a/src/mutex.rs b/src/mutex.rs index 7252dfc..c78d398 100644 --- a/src/mutex.rs +++ b/src/mutex.rs @@ -26,6 +26,7 @@ pub type ParkingMutex = Mutex; /// /// [`lock`]: `Mutex::lock` /// [`try_lock`]: `Mutex::try_lock` +/// [`ThreadKey`]: `crate::ThreadKey` pub struct Mutex { raw: R, value: UnsafeCell, @@ -185,10 +186,12 @@ impl Mutex { /// assert_eq!(*mutex.lock(key), 10); /// ``` pub fn lock<'s, 'k: 's, Key: Keyable>(&'s self, key: Key) -> MutexGuard<'_, 'k, T, Key, R> { - self.raw.lock(); + unsafe { + self.raw.lock(); - // safety: we just locked the mutex - unsafe { MutexGuard::new(self, key) } + // safety: we just locked the mutex + MutexGuard::new(self, key) + } } /// Lock without a [`ThreadKey`]. You must exclusively own the @@ -271,7 +274,6 @@ impl Mutex { /// /// let key = Mutex::unlock(guard); /// ``` - #[allow(clippy::missing_const_for_fn)] pub fn unlock<'a, 'k: 'a, Key: Keyable + 'k>(guard: MutexGuard<'a, 'k, T, Key, R>) -> Key { unsafe { guard.mutex.0.force_unlock(); diff --git a/src/rwlock.rs b/src/rwlock.rs new file mode 100644 index 0000000..16ad3c3 --- /dev/null +++ b/src/rwlock.rs @@ -0,0 +1,342 @@ +use std::{ + cell::UnsafeCell, + marker::PhantomData, + ops::{Deref, DerefMut}, +}; + +use lock_api::RawRwLock; + +use crate::key::Keyable; + +pub type SpinRwLock = RwLock>; + +pub type ParkingRwLock = RwLock; + +pub struct RwLock { + raw: R, + value: UnsafeCell, +} + +pub struct ReadLock<'a, T: ?Sized, R>(&'a RwLock); + +pub struct WriteLock<'a, T: ?Sized, R>(&'a RwLock); + +pub struct RwLockReadRef<'a, T: ?Sized, R: RawRwLock>(&'a RwLock); + +pub struct RwLockWriteRef<'a, T: ?Sized, R: RawRwLock>(&'a RwLock); + +pub struct RwLockReadGuard<'a, 'key, T: ?Sized, Key: Keyable + 'key, R: RawRwLock> { + rwlock: RwLockReadRef<'a, T, R>, + thread_key: Key, + _phantom: PhantomData<&'key ()>, +} + +pub struct RwLockWriteGuard<'a, 'key, T: ?Sized, Key: Keyable + 'key, R: RawRwLock> { + rwlock: RwLockWriteRef<'a, T, R>, + thread_key: Key, + _phantom: PhantomData<&'key ()>, +} + +impl<'a, T: ?Sized + 'a, R: RawRwLock> Deref for RwLockReadRef<'a, T, R> { + type Target = T; + + fn deref(&self) -> &Self::Target { + // safety: this is the only type that can use `value`, and there's + // a reference to this type, so there cannot be any mutable + // references to this value. + unsafe { &*self.0.value.get() } + } +} + +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 + // accessed without locking again + unsafe { self.0.force_unlock_read() } + } +} + +impl<'a, T: ?Sized + 'a, R: RawRwLock> Deref for RwLockWriteRef<'a, T, R> { + type Target = T; + + fn deref(&self) -> &Self::Target { + // safety: this is the only type that can use `value`, and there's + // a reference to this type, so there cannot be any mutable + // references to this value. + unsafe { &*self.0.value.get() } + } +} + +impl<'a, T: ?Sized + 'a, R: RawRwLock> DerefMut for RwLockWriteRef<'a, T, R> { + fn deref_mut(&mut self) -> &mut Self::Target { + // safety: this is the only type that can use `value`, and we have a + // mutable reference to this type, so there cannot be any other + // references to this value. + unsafe { &mut *self.0.value.get() } + } +} + +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 + // accessed without locking again + unsafe { self.0.force_unlock_write() } + } +} + +impl<'a, 'key: 'a, T: ?Sized + 'a, Key: Keyable, R: RawRwLock> Deref + for RwLockReadGuard<'a, 'key, T, Key, R> +{ + type Target = T; + + fn deref(&self) -> &Self::Target { + &self.rwlock + } +} + +impl<'a, 'key: 'a, T: ?Sized + 'a, Key: Keyable, R: RawRwLock> Deref + for RwLockWriteGuard<'a, 'key, T, Key, R> +{ + type Target = T; + + fn deref(&self) -> &Self::Target { + &self.rwlock + } +} + +impl<'a, 'key: 'a, T: ?Sized + 'a, Key: Keyable, R: RawRwLock> DerefMut + for RwLockWriteGuard<'a, 'key, T, Key, R> +{ + fn deref_mut(&mut self) -> &mut Self::Target { + &mut self.rwlock + } +} + +impl<'a, 'key: 'a, T: ?Sized + 'a, Key: Keyable, R: RawRwLock> + RwLockReadGuard<'a, 'key, T, Key, R> +{ + /// Create a guard to the given mutex. Undefined if multiple guards to the + /// same mutex exist at once. + const unsafe fn new(rwlock: &'a RwLock, thread_key: Key) -> Self { + Self { + rwlock: RwLockReadRef(rwlock), + thread_key, + _phantom: PhantomData, + } + } +} + +impl<'a, 'key: 'a, T: ?Sized + 'a, Key: Keyable, R: RawRwLock> + RwLockWriteGuard<'a, 'key, T, Key, R> +{ + /// Create a guard to the given mutex. Undefined if multiple guards to the + /// same mutex exist at once. + const unsafe fn new(rwlock: &'a RwLock, thread_key: Key) -> Self { + Self { + rwlock: RwLockWriteRef(rwlock), + thread_key, + _phantom: PhantomData, + } + } +} + +impl RwLock { + pub const fn new(value: T) -> Self { + Self { + value: UnsafeCell::new(value), + raw: R::INIT, + } + } +} + +impl RwLock { + pub fn into_inner(self) -> T { + self.value.into_inner() + } +} + +impl RwLock { + pub fn get_mut(&mut self) -> &mut T { + self.value.get_mut() + } +} + +impl RwLock { + pub fn read<'s, 'key: 's, Key: Keyable>( + &'s self, + key: Key, + ) -> RwLockReadGuard<'_, 'key, T, Key, R> { + unsafe { + self.raw.lock_shared(); + + // safety: the lock is locked first + RwLockReadGuard::new(self, key) + } + } + + pub(crate) unsafe fn read_no_key(&self) -> RwLockReadRef<'_, T, R> { + self.raw.lock_shared(); + + // safety: the lock is locked first + RwLockReadRef(self) + } + + pub fn try_read<'s, 'key: 's, Key: Keyable>( + &'s self, + key: Key, + ) -> Option> { + unsafe { + if self.raw.try_lock_shared() { + // safety: the lock is locked first + Some(RwLockReadGuard::new(self, key)) + } else { + None + } + } + } + + pub(crate) unsafe fn try_read_no_key(&self) -> Option> { + if self.raw.try_lock_shared() { + // safety: the lock is locked first + Some(RwLockReadRef(self)) + } else { + None + } + } + + pub fn write<'s, 'key: 's, Key: Keyable>( + &'s self, + key: Key, + ) -> RwLockWriteGuard<'_, 'key, T, Key, R> { + unsafe { + self.raw.lock_exclusive(); + + // safety: the lock is locked first + RwLockWriteGuard::new(self, key) + } + } + + pub(crate) unsafe fn write_no_key(&self) -> RwLockWriteRef<'_, T, R> { + self.raw.lock_exclusive(); + + // safety: the lock is locked first + RwLockWriteRef(self) + } + + pub fn try_write<'s, 'key: 's, Key: Keyable>( + &'s self, + key: Key, + ) -> Option> { + unsafe { + if self.raw.try_lock_exclusive() { + // safety: the lock is locked first + Some(RwLockWriteGuard::new(self, key)) + } else { + None + } + } + } + + pub(crate) unsafe fn try_write_no_key(&self) -> Option> { + if self.raw.try_lock_exclusive() { + // safety: the lock is locked first + Some(RwLockWriteRef(self)) + } else { + None + } + } + + unsafe fn force_unlock_read(&self) { + self.raw.unlock_shared(); + } + + unsafe fn force_unlock_write(&self) { + self.raw.unlock_exclusive(); + } + + pub fn unlock_read<'key, Key: Keyable + 'key>( + guard: RwLockReadGuard<'_, 'key, T, Key, R>, + ) -> Key { + unsafe { + guard.rwlock.0.force_unlock_read(); + } + guard.thread_key + } + + pub fn unlock_write<'key, Key: Keyable + 'key>( + guard: RwLockWriteGuard<'_, 'key, T, Key, R>, + ) -> Key { + unsafe { + guard.rwlock.0.force_unlock_write(); + } + guard.thread_key + } +} + +impl<'a, T, R> ReadLock<'a, T, R> { + pub const fn new(rwlock: &'a RwLock) -> Self { + Self(rwlock) + } +} + +impl<'a, T: ?Sized, R: RawRwLock> ReadLock<'a, T, R> { + pub fn lock<'s, 'key: 's, Key: Keyable + 'key>( + &'s self, + key: Key, + ) -> RwLockReadGuard<'_, 'key, T, Key, R> { + self.0.read(key) + } + + pub(crate) unsafe fn lock_no_key(&self) -> RwLockReadRef<'_, T, R> { + self.0.read_no_key() + } + + pub fn try_lock<'s, 'key: 's, Key: Keyable + 'key>( + &'s self, + key: Key, + ) -> Option> { + self.0.try_read(key) + } + + pub(crate) unsafe fn try_lock_no_key(&self) -> Option> { + self.0.try_read_no_key() + } + + pub fn unlock<'key, Key: Keyable + 'key>(guard: RwLockReadGuard<'_, 'key, T, Key, R>) -> Key { + RwLock::unlock_read(guard) + } +} + +impl<'a, T, R> WriteLock<'a, T, R> { + pub const fn new(rwlock: &'a RwLock) -> Self { + Self(rwlock) + } +} + +impl<'a, T: ?Sized, R: RawRwLock> WriteLock<'a, T, R> { + pub fn lock<'s, 'key: 's, Key: Keyable + 'key>( + &'s self, + key: Key, + ) -> RwLockWriteGuard<'_, 'key, T, Key, R> { + self.0.write(key) + } + + pub(crate) unsafe fn lock_no_key(&self) -> RwLockWriteRef<'_, T, R> { + self.0.write_no_key() + } + + pub fn try_lock<'s, 'key: 's, Key: Keyable + 'key>( + &'s self, + key: Key, + ) -> Option> { + self.0.try_write(key) + } + + pub(crate) unsafe fn try_lock_no_key(&self) -> Option> { + self.0.try_write_no_key() + } + + pub fn unlock<'key, Key: Keyable + 'key>(guard: RwLockWriteGuard<'_, 'key, T, Key, R>) -> Key { + RwLock::unlock_write(guard) + } +} -- cgit v1.2.3