From 801a870467af4059d2abdc67f2899edebb1f6d6c Mon Sep 17 00:00:00 2001 From: Mica White Date: Sat, 16 Mar 2024 12:41:27 -0400 Subject: retry lock collection --- src/collection.rs | 11 ++++++++--- 1 file changed, 8 insertions(+), 3 deletions(-) (limited to 'src/collection.rs') diff --git a/src/collection.rs b/src/collection.rs index 93adf16..d9c56d3 100644 --- a/src/collection.rs +++ b/src/collection.rs @@ -1,4 +1,4 @@ -use std::{marker::PhantomData, ptr::NonNull}; +use std::{marker::PhantomData}; use crate::{ key::Keyable, @@ -9,6 +9,7 @@ mod boxed_collection; mod guard; mod owned_collection; mod ref_collection; +mod retry_collection; pub struct OwnedLockCollection { data: L, @@ -25,9 +26,13 @@ pub struct RefLockCollection<'a, L> { pub struct BoxedLockCollection<'a, L>(RefLockCollection<'a, L>); +pub struct RetryingLockCollection { + data: L, +} + /// A RAII guard for a generic [`Lockable`] type. -pub struct LockGuard<'a, 'key: 'a, L: Lockable<'a>, Key: Keyable + 'key> { - guard: L::Guard, +pub struct LockGuard<'g, 'key: 'g, L: Lockable + 'g, Key: Keyable + 'key> { + guard: L::Guard<'g>, key: Key, _phantom: PhantomData<&'key ()>, } -- cgit v1.2.3 From cb28fb1ff3b5ea71c6fe11956015c7285cb3f3df Mon Sep 17 00:00:00 2001 From: Mica White Date: Tue, 21 May 2024 13:17:38 -0400 Subject: read-lock changes --- README.md | 6 +----- src/collection.rs | 2 +- src/lockable.rs | 4 ++-- src/rwlock.rs | 6 ++++-- src/rwlock/read_lock.rs | 16 ++++++++-------- src/rwlock/write_lock.rs | 16 ++++++++-------- 6 files changed, 24 insertions(+), 26 deletions(-) (limited to 'src/collection.rs') diff --git a/README.md b/README.md index 51d8d67..66a4fc0 100644 --- a/README.md +++ b/README.md @@ -73,14 +73,10 @@ println!("{}", *data.1); **Avoid `LockCollection::try_new`.** This constructor will check to make sure that the collection contains no duplicate locks. This is an O(n^2) operation, where n is the number of locks in the collection. `LockCollection::new` and `LockCollection::new_ref` don't need these checks because they use `OwnedLockable`, which is guaranteed to be unique as long as it is accessible. As a last resort, `LockCollection::new_unchecked` doesn't do this check, but is unsafe to call. -**Avoid using distinct lock orders for `LockCollection`.** The problem is that this library must iterate through the list of locks, and not complete until every single one of them is unlocked. This also means that attempting to lock multiple mutexes gives you a lower chance of ever running. Only one needs to be locked for the operation to need a reset. This problem can be prevented by not doing that in your code. Resources should be obtained in the same order on every thread. - -**Avoid tuples in `LockCollection`.** Tuples become spinlocks if the first value is already unlocked. This will be fixed in the future. For now, if you need a tuple, make the lock that is most likely to be locked the first element. +**Avoid using distinct lock orders for `RetryingLockCollection`.** The problem is that this collection must iterate through the list of locks, and not complete until every single one of them is unlocked. This also means that attempting to lock multiple mutexes gives you a lower chance of ever running. Only one needs to be locked for the operation to need a reset. This problem can be prevented by not doing that in your code. Resources should be obtained in the same order on every thread. ## Future Work -Although this library is able to successfully prevent deadlocks, livelocks may still be an issue. Imagine thread 1 gets resource 1, thread 2 gets resource 2, thread 1 realizes it can't get resource 2, thread 2 realizes it can't get resource 1, thread 1 drops resource 1, thread 2 drops resource 2, and then repeat forever. In practice, this situation probably wouldn't last forever. But it would be nice if this could be prevented somehow. A more fair system for getting sets of locks would help, but I have no clue what that looks like. - It might to possible to break the `ThreadKey` system by having two crates import this crate and call `ThreadKey::get`. I'm not quite sure how this works, but Rust could decide to give each crate their own key, ergo one thread would get two keys. I don't think the standard library would have this issue. At a certain point, I have to recognize that someone could also just import the standard library mutex and get a deadlock that way. We should add `Condvar` at some point. I didn't because I've never used it before, and I'm probably not the right person to solve this problem. I think all the synchronization problems could be solved by having `Condvar::wait` take a `ThreadKey` instead of a `MutexGuard`. Something similar can probably be done for `Barrier`. But again, I'm no expert. diff --git a/src/collection.rs b/src/collection.rs index d9c56d3..a11d60c 100644 --- a/src/collection.rs +++ b/src/collection.rs @@ -1,4 +1,4 @@ -use std::{marker::PhantomData}; +use std::marker::PhantomData; use crate::{ key::Keyable, diff --git a/src/lockable.rs b/src/lockable.rs index fe14e8c..a5646e1 100644 --- a/src/lockable.rs +++ b/src/lockable.rs @@ -124,7 +124,7 @@ unsafe impl OwnedLockable for Mutex {} unsafe impl OwnedLockable for RwLock {} -unsafe impl<'r, T: Send + 'r, R: RawRwLock + Send + Sync + 'r> Lockable for ReadLock<'r, T, R> { +unsafe impl Lockable for ReadLock { type Guard<'g> = RwLockReadRef<'g, T, R> where Self: 'g; fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { @@ -136,7 +136,7 @@ unsafe impl<'r, T: Send + 'r, R: RawRwLock + Send + Sync + 'r> Lockable for Read } } -unsafe impl<'r, T: Send + 'r, R: RawRwLock + Send + Sync + 'r> Lockable for WriteLock<'r, T, R> { +unsafe impl Lockable for WriteLock { type Guard<'g> = RwLockWriteRef<'g, T, R> where Self: 'g; fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn Lock>) { diff --git a/src/rwlock.rs b/src/rwlock.rs index 7fb8c7a..40c5a6e 100644 --- a/src/rwlock.rs +++ b/src/rwlock.rs @@ -56,7 +56,8 @@ pub struct RwLock { /// that only read access is needed to the data. /// /// [`LockCollection`]: `crate::LockCollection` -pub struct ReadLock<'a, T: ?Sized, R>(&'a RwLock); +#[repr(transparent)] +pub struct ReadLock(RwLock); /// Grants write access to an [`RwLock`] /// @@ -64,7 +65,8 @@ pub struct ReadLock<'a, T: ?Sized, R>(&'a RwLock); /// that write access is needed to the data. /// /// [`LockCollection`]: `crate::LockCollection` -pub struct WriteLock<'a, T: ?Sized, R>(&'a RwLock); +#[repr(transparent)] +pub struct WriteLock(RwLock); /// RAII structure that unlocks the shared read access to a [`RwLock`] pub struct RwLockReadRef<'a, T: ?Sized, R: RawRwLock>( diff --git a/src/rwlock/read_lock.rs b/src/rwlock/read_lock.rs index 133ca7d..a8bb9be 100644 --- a/src/rwlock/read_lock.rs +++ b/src/rwlock/read_lock.rs @@ -6,7 +6,7 @@ use crate::key::Keyable; use super::{ReadLock, RwLock, RwLockReadGuard, RwLockReadRef}; -impl<'a, T: ?Sized + Debug, R: RawRwLock> Debug for ReadLock<'a, T, R> { +impl Debug for ReadLock { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { // safety: this is just a try lock, and the value is dropped // immediately after, so there's no risk of blocking ourselves @@ -28,19 +28,19 @@ impl<'a, T: ?Sized + Debug, R: RawRwLock> Debug for ReadLock<'a, T, R> { } } -impl<'a, T: ?Sized, R> From<&'a RwLock> for ReadLock<'a, T, R> { - fn from(value: &'a RwLock) -> Self { +impl From> for ReadLock { + fn from(value: RwLock) -> Self { Self::new(value) } } -impl<'a, T: ?Sized, R> AsRef> for ReadLock<'a, T, R> { +impl AsRef> for ReadLock { fn as_ref(&self) -> &RwLock { - self.0 + &self.0 } } -impl<'a, T: ?Sized, R> ReadLock<'a, T, R> { +impl ReadLock { /// Creates a new `ReadLock` which accesses the given [`RwLock`] /// /// # Examples @@ -52,12 +52,12 @@ impl<'a, T: ?Sized, R> ReadLock<'a, T, R> { /// let read_lock = ReadLock::new(&lock); /// ``` #[must_use] - pub const fn new(rwlock: &'a RwLock) -> Self { + pub const fn new(rwlock: RwLock) -> Self { Self(rwlock) } } -impl<'a, T: ?Sized, R: RawRwLock> ReadLock<'a, T, R> { +impl ReadLock { /// Locks the underlying [`RwLock`] with shared read access, blocking the /// current thread until it can be acquired. pub fn lock<'s, 'key: 's, Key: Keyable + 'key>( diff --git a/src/rwlock/write_lock.rs b/src/rwlock/write_lock.rs index c6b4c24..a344125 100644 --- a/src/rwlock/write_lock.rs +++ b/src/rwlock/write_lock.rs @@ -6,7 +6,7 @@ use crate::key::Keyable; use super::{RwLock, RwLockWriteGuard, RwLockWriteRef, WriteLock}; -impl<'a, T: ?Sized + Debug, R: RawRwLock> Debug for WriteLock<'a, T, R> { +impl Debug for WriteLock { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { // safety: this is just a try lock, and the value is dropped // immediately after, so there's no risk of blocking ourselves @@ -28,19 +28,19 @@ impl<'a, T: ?Sized + Debug, R: RawRwLock> Debug for WriteLock<'a, T, R> { } } -impl<'a, T: ?Sized, R> From<&'a RwLock> for WriteLock<'a, T, R> { - fn from(value: &'a RwLock) -> Self { +impl From> for WriteLock { + fn from(value: RwLock) -> Self { Self::new(value) } } -impl<'a, T: ?Sized, R> AsRef> for WriteLock<'a, T, R> { +impl AsRef> for WriteLock { fn as_ref(&self) -> &RwLock { - self.0 + &self.0 } } -impl<'a, T: ?Sized, R> WriteLock<'a, T, R> { +impl WriteLock { /// Creates a new `WriteLock` which accesses the given [`RwLock`] /// /// # Examples @@ -52,12 +52,12 @@ impl<'a, T: ?Sized, R> WriteLock<'a, T, R> { /// let write_lock = WriteLock::new(&lock); /// ``` #[must_use] - pub const fn new(rwlock: &'a RwLock) -> Self { + pub const fn new(rwlock: RwLock) -> Self { Self(rwlock) } } -impl<'a, T: ?Sized, R: RawRwLock> WriteLock<'a, T, R> { +impl WriteLock { /// Locks the underlying [`RwLock`] with exclusive write access, blocking /// the current until it can be acquired. pub fn lock<'s, 'key: 's, Key: Keyable + 'key>( -- cgit v1.2.3