diff options
| -rw-r--r-- | README.md | 2 | ||||
| -rw-r--r-- | examples/dining_philosophers.rs | 5 | ||||
| -rw-r--r-- | examples/double_mutex.rs | 9 | ||||
| -rw-r--r-- | examples/list.rs | 4 | ||||
| -rw-r--r-- | src/collection.rs | 38 | ||||
| -rw-r--r-- | src/lockable.rs | 55 |
6 files changed, 99 insertions, 14 deletions
@@ -71,6 +71,8 @@ println!("{}", *data.1); **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::lock()`, 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. +**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. ## Future Work diff --git a/examples/dining_philosophers.rs b/examples/dining_philosophers.rs index 9600c8c..f8657df 100644 --- a/examples/dining_philosophers.rs +++ b/examples/dining_philosophers.rs @@ -48,7 +48,10 @@ impl Philosopher { fn cycle(&self) { let key = ThreadKey::lock().unwrap(); thread::sleep(Duration::from_secs(1)); - let forks = LockCollection::new([&FORKS[self.left], &FORKS[self.right]]).unwrap(); + + // safety: no philosopher asks for the same fork twice + let forks = + unsafe { LockCollection::new_unchecked([&FORKS[self.left], &FORKS[self.right]]) }; let forks = forks.lock(key); println!("{} is eating...", self.name); thread::sleep(Duration::from_secs(1)); diff --git a/examples/double_mutex.rs b/examples/double_mutex.rs index df11b7a..320f461 100644 --- a/examples/double_mutex.rs +++ b/examples/double_mutex.rs @@ -4,16 +4,14 @@ use happylock::{LockCollection, Mutex, ThreadKey}; const N: usize = 10; -static DATA_1: Mutex<i32> = Mutex::new(0); -static DATA_2: Mutex<String> = Mutex::new(String::new()); +static DATA: (Mutex<i32>, Mutex<String>) = (Mutex::new(0), Mutex::new(String::new())); fn main() { let mut threads = Vec::new(); for _ in 0..N { let th = thread::spawn(move || { let key = ThreadKey::lock().unwrap(); - let data = (&DATA_1, &DATA_2); - let lock = LockCollection::new(data).unwrap(); + let lock = LockCollection::new_ref(&DATA); let mut guard = lock.lock(key); *guard.1 = (100 - *guard.0).to_string(); *guard.0 += 1; @@ -26,8 +24,7 @@ fn main() { } let key = ThreadKey::lock().unwrap(); - let data = (&DATA_1, &DATA_2); - let data = LockCollection::new(data).unwrap(); + let data = LockCollection::new_ref(&DATA); let data = data.lock(key); println!("{}", *data.0); println!("{}", *data.1); diff --git a/examples/list.rs b/examples/list.rs index 368a633..14117ee 100644 --- a/examples/list.rs +++ b/examples/list.rs @@ -37,7 +37,7 @@ fn main() { data.push(&DATA[rand % 6]); } - let Some(lock) = LockCollection::new(data) else { + let Some(lock) = LockCollection::try_new(data) else { continue; }; let mut guard = lock.lock(&mut key); @@ -56,7 +56,7 @@ fn main() { } let key = ThreadKey::lock().unwrap(); - let data = LockCollection::new(&DATA).unwrap(); + let data = LockCollection::new_ref(&DATA); let data = data.lock(key); for val in &*data { println!("{}", **val); diff --git a/src/collection.rs b/src/collection.rs index 4b24a67..34de620 100644 --- a/src/collection.rs +++ b/src/collection.rs @@ -3,13 +3,16 @@ use std::{ ops::{Deref, DerefMut}, }; -use crate::{key::Keyable, lockable::Lockable}; +use crate::{ + key::Keyable, + lockable::{Lockable, OwnedLockable}, +}; /// returns `true` if the list contains a duplicate fn contains_duplicates(l: &[usize]) -> bool { for i in 0..l.len() { - for j in 0..l.len() { - if i != j && l[i] == l[j] { + for j in (i + 1)..l.len() { + if l[i] == l[j] { return true; } } @@ -46,11 +49,36 @@ impl<L> LockCollection<L> { } } +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. + pub const fn new(collection: L) -> Self { + Self { collection } + } + + /// Creates a new collection of owned locks. + /// + /// Because the locks are owned, there's no need to do any checks for + /// duplicate values. + pub const fn new_ref(collection: &L) -> LockCollection<&L> { + LockCollection { collection } + } +} + 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. - pub fn new(collection: L) -> Option<Self> { + /// 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. + pub fn try_new(collection: L) -> Option<Self> { let ptrs = collection.get_ptrs(); if contains_duplicates(&ptrs) { return None; diff --git a/src/lockable.rs b/src/lockable.rs index ddcc1c8..3c217c4 100644 --- a/src/lockable.rs +++ b/src/lockable.rs @@ -29,6 +29,15 @@ mod sealed { impl<'a, T: Lockable<'a>> Sealed for Vec<T> {} } +/// 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 /// /// # Safety @@ -102,6 +111,8 @@ unsafe impl<'a, T: Lockable<'a>> Lockable<'a> for &mut T { } } +unsafe impl<'a, T: OwnedLockable<'a>> OwnedLockable<'a> for &mut T {} + unsafe impl<'a, T: 'a, R: RawMutex + 'a> Lockable<'a> for Mutex<T, R> { type Output = MutexRef<'a, T, R>; @@ -134,6 +145,10 @@ unsafe impl<'a, T: 'a, R: RawRwLock + 'a> Lockable<'a> for RwLock<T, R> { } } +unsafe impl<'a, T: 'a, R: RawMutex + 'a> OwnedLockable<'a> for Mutex<T, R> {} + +unsafe impl<'a, T: 'a, R: RawRwLock + 'a> OwnedLockable<'a> for RwLock<T, R> {} + unsafe impl<'a, T: 'a, R: RawRwLock + 'a> Lockable<'a> for ReadLock<'a, T, R> { type Output = RwLockReadRef<'a, T, R>; @@ -439,6 +454,43 @@ unsafe impl< } } +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 impl<'a, T: Lockable<'a>, const N: usize> Lockable<'a> for [T; N] { type Output = [T::Output; N]; @@ -554,3 +606,6 @@ unsafe impl<'a, T: Lockable<'a>> Lockable<'a> for Vec<T> { Some(outputs) } } + +unsafe impl<'a, T: OwnedLockable<'a>, const N: usize> OwnedLockable<'a> for [T; N] {} +unsafe impl<'a, T: OwnedLockable<'a>> OwnedLockable<'a> for Vec<T> {} |