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/boxed_collection.rs | 10 +-- src/collection/guard.rs | 6 +- src/collection/owned_collection.rs | 11 ++- src/collection/ref_collection.rs | 12 ++-- src/collection/retry_collection.rs | 138 +++++++++++++++++++++++++++++++++++++ 5 files changed, 156 insertions(+), 21 deletions(-) create mode 100644 src/collection/retry_collection.rs (limited to 'src/collection') diff --git a/src/collection/boxed_collection.rs b/src/collection/boxed_collection.rs index bcb941b..1aae1e4 100644 --- a/src/collection/boxed_collection.rs +++ b/src/collection/boxed_collection.rs @@ -26,7 +26,7 @@ impl<'a, L> Drop for BoxedLockCollection<'a, L> { } } -impl<'a, L: OwnedLockable<'a> + 'a> BoxedLockCollection<'a, L> { +impl<'a, L: OwnedLockable> BoxedLockCollection<'a, L> { #[must_use] pub fn new(data: L) -> Self { let boxed = Box::leak(Box::new(data)); @@ -34,18 +34,18 @@ impl<'a, L: OwnedLockable<'a> + 'a> BoxedLockCollection<'a, L> { } } -impl<'a, L: OwnedLockable<'a> + 'a> BoxedLockCollection<'a, &'a L> { +impl<'a, L: OwnedLockable> BoxedLockCollection<'a, &'a L> { #[must_use] pub fn new_ref(data: &'a L) -> Self { let boxed = Box::leak(Box::new(data)); - // this is a reference to an OwnedLockable, which can't possibly - // contain inner duplicates + // safety: this is a reference to an OwnedLockable, which can't + // possibly contain inner duplicates Self(unsafe { RefLockCollection::new_unchecked(boxed) }) } } -impl<'a, L: Lockable<'a> + 'a> BoxedLockCollection<'a, L> { +impl<'a, L: Lockable> BoxedLockCollection<'a, L> { #[must_use] pub unsafe fn new_unchecked(data: L) -> Self { let boxed = Box::leak(Box::new(data)); diff --git a/src/collection/guard.rs b/src/collection/guard.rs index 3b98d29..e3ffb21 100644 --- a/src/collection/guard.rs +++ b/src/collection/guard.rs @@ -4,15 +4,15 @@ use crate::{key::Keyable, Lockable}; use super::LockGuard; -impl<'a, 'key: 'a, L: Lockable<'a>, Key: Keyable> Deref for LockGuard<'a, 'key, L, Key> { - type Target = L::Guard; +impl<'a, 'key: 'a, L: Lockable + 'a, Key: Keyable> Deref for LockGuard<'a, 'key, L, Key> { + type Target = L::Guard<'a>; fn deref(&self) -> &Self::Target { &self.guard } } -impl<'a, 'key: 'a, L: Lockable<'a>, Key: Keyable> DerefMut for LockGuard<'a, 'key, L, Key> { +impl<'a, 'key: 'a, L: Lockable + 'a, Key: Keyable> DerefMut for LockGuard<'a, 'key, L, Key> { fn deref_mut(&mut self) -> &mut Self::Target { &mut self.guard } diff --git a/src/collection/owned_collection.rs b/src/collection/owned_collection.rs index dbc9a45..ea8f2f2 100644 --- a/src/collection/owned_collection.rs +++ b/src/collection/owned_collection.rs @@ -4,22 +4,19 @@ use crate::{lockable::Lock, Keyable, Lockable, OwnedLockable}; use super::{LockGuard, OwnedLockCollection}; -fn get_locks<'a, L: Lockable<'a> + 'a>(data: &'a L) -> Vec<&'a dyn Lock> { +fn get_locks(data: &L) -> Vec<&dyn Lock> { let mut locks = Vec::new(); data.get_ptrs(&mut locks); locks } -impl<'a, L: OwnedLockable<'a>> OwnedLockCollection { +impl OwnedLockCollection { #[must_use] pub const fn new(data: L) -> Self { Self { data } } - pub fn lock<'s: 'a, 'key, Key: Keyable + 'key>( - &'s self, - key: Key, - ) -> LockGuard<'a, 'key, L, Key> { + pub fn lock<'a, 'key, Key: Keyable + 'key>(&'a self, key: Key) -> LockGuard<'a, 'key, L, Key> { let locks = get_locks(&self.data); for lock in locks { // safety: we have the thread key, and these locks happen in a @@ -36,7 +33,7 @@ impl<'a, L: OwnedLockable<'a>> OwnedLockCollection { } } - pub fn try_lock<'key: 'a, Key: Keyable + 'key>( + pub fn try_lock<'a, 'key: 'a, Key: Keyable + 'key>( &'a self, key: Key, ) -> Option> { diff --git a/src/collection/ref_collection.rs b/src/collection/ref_collection.rs index 3e4d5f8..2462182 100644 --- a/src/collection/ref_collection.rs +++ b/src/collection/ref_collection.rs @@ -5,7 +5,7 @@ use crate::{key::Keyable, lockable::Lock, Lockable, OwnedLockable}; use super::{LockGuard, RefLockCollection}; #[must_use] -fn get_locks<'a, L: Lockable<'a> + 'a>(data: &'a L) -> Vec<&'a dyn Lock> { +fn get_locks(data: &L) -> Vec<&dyn Lock> { let mut locks = Vec::new(); data.get_ptrs(&mut locks); locks.sort_by_key(|lock| std::ptr::from_ref(*lock)); @@ -20,19 +20,19 @@ fn contains_duplicates(l: &[&dyn Lock]) -> bool { }) } -impl<'a, L: Lockable<'a>> AsRef for RefLockCollection<'a, L> { +impl<'a, L: Lockable> AsRef for RefLockCollection<'a, L> { fn as_ref(&self) -> &L { self.data } } -impl<'a, L: Lockable<'a>> AsRef for RefLockCollection<'a, L> { +impl<'a, L: Lockable> AsRef for RefLockCollection<'a, L> { fn as_ref(&self) -> &Self { self } } -impl<'a, L: Lockable<'a>> AsMut for RefLockCollection<'a, L> { +impl<'a, L: Lockable> AsMut for RefLockCollection<'a, L> { fn as_mut(&mut self) -> &mut Self { self } @@ -50,7 +50,7 @@ where } } -impl<'a, L: OwnedLockable<'a> + 'a> RefLockCollection<'a, L> { +impl<'a, L: OwnedLockable> RefLockCollection<'a, L> { /// Creates a new collection of owned locks. /// /// Because the locks are owned, there's no need to do any checks for @@ -73,7 +73,7 @@ impl<'a, L: OwnedLockable<'a> + 'a> RefLockCollection<'a, L> { } } -impl<'a, L: Lockable<'a>> RefLockCollection<'a, L> { +impl<'a, L: Lockable> RefLockCollection<'a, L> { /// Creates a new collections of locks. /// /// # Safety diff --git a/src/collection/retry_collection.rs b/src/collection/retry_collection.rs new file mode 100644 index 0000000..73f9e18 --- /dev/null +++ b/src/collection/retry_collection.rs @@ -0,0 +1,138 @@ +use std::marker::PhantomData; + +use crate::{lockable::Lock, Keyable, Lockable, OwnedLockable}; + +use super::{LockGuard, RetryingLockCollection}; + +fn contains_duplicates(data: L) -> bool { + let mut locks = Vec::new(); + data.get_ptrs(&mut locks); + let mut locks: Vec<_> = locks.into_iter().map(|l| l as *const dyn Lock).collect(); + locks.sort_unstable(); + locks.windows(2).any(|w| std::ptr::addr_eq(w[0], w[1])) +} + +impl RetryingLockCollection { + #[must_use] + pub const fn new(data: L) -> Self { + Self { data } + } +} + +impl<'a, L: OwnedLockable> RetryingLockCollection<&'a L> { + #[must_use] + pub const fn new_ref(data: &'a L) -> Self { + Self { data } + } +} + +impl RetryingLockCollection { + #[must_use] + pub const unsafe fn new_unchecked(data: L) -> Self { + Self { data } + } + + pub fn try_new(data: L) -> Option { + contains_duplicates(&data).then_some(Self { data }) + } + + pub fn lock<'a, 'key: 'a, Key: Keyable + 'key>( + &'a self, + key: Key, + ) -> LockGuard<'a, 'key, L, Key> { + let mut first_index = 0; + let mut locks = Vec::new(); + self.data.get_ptrs(&mut locks); + + if locks.is_empty() { + return LockGuard { + // safety: there's no data being returned + guard: unsafe { self.data.guard() }, + key, + _phantom: PhantomData, + }; + } + + let guard = unsafe { + 'outer: loop { + // safety: we have the thread key + locks[first_index].lock(); + for (i, lock) in locks.iter().enumerate() { + if i == first_index { + continue; + } + + // safety: we have the thread key + if !lock.try_lock() { + for lock in locks.iter().take(i) { + // safety: we already locked all of these + lock.unlock(); + } + + if first_index >= i { + // safety: this is already locked and can't be unlocked + // by the previous loop + locks[first_index].unlock(); + } + + first_index = i; + continue 'outer; + } + } + + // safety: we locked all the data + break self.data.guard(); + } + }; + + LockGuard { + guard, + key, + _phantom: PhantomData, + } + } + + pub fn try_lock<'a, 'key: 'a, Key: Keyable + 'key>( + &'a self, + key: Key, + ) -> Option> { + let mut locks = Vec::new(); + self.data.get_ptrs(&mut locks); + + if locks.is_empty() { + return Some(LockGuard { + // safety: there's no data being returned + guard: unsafe { self.data.guard() }, + key, + _phantom: PhantomData, + }); + } + + let guard = unsafe { + for (i, lock) in locks.iter().enumerate() { + // safety: we have the thread key + if !lock.try_lock() { + for lock in locks.iter().take(i) { + // safety: we already locked all of these + lock.unlock(); + } + return None; + } + } + + // safety: we locked all the data + self.data.guard() + }; + + Some(LockGuard { + guard, + key, + _phantom: PhantomData, + }) + } + + pub fn unlock<'key, Key: Keyable + 'key>(guard: LockGuard<'_, 'key, L, Key>) -> Key { + drop(guard.guard); + guard.key + } +} -- cgit v1.2.3