diff options
| -rw-r--r-- | happylock.md | 325 | ||||
| -rw-r--r-- | src/lib.rs | 1 | ||||
| -rw-r--r-- | src/poisonable.rs | 46 | ||||
| -rw-r--r-- | src/poisonable/error.rs | 47 | ||||
| -rw-r--r-- | src/poisonable/flag.rs | 36 | ||||
| -rw-r--r-- | src/poisonable/guard.rs | 92 | ||||
| -rw-r--r-- | src/poisonable/poisonable.rs | 139 |
7 files changed, 666 insertions, 20 deletions
diff --git a/happylock.md b/happylock.md index 477e99b..0e250fe 100644 --- a/happylock.md +++ b/happylock.md @@ -264,25 +264,6 @@ Time Complexity: O(nlogn) --- -## Missing Features - -- `Condvar`/`Barrier` -- We probably don't need `OnceLock` or `LazyLock` -- Standard Library Backend -- Mutex poisoning -- Support for `no_std` -- Convenience methods: `lock_swap`, `lock_set`? -- `try_lock_swap` doesn't need a `ThreadKey` -- Going further: `LockCell` API (preemptive allocation) - ---- - -<!--_class: invert lead --> - -## What's next? - ---- - ## Problem: Live-locking 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. @@ -310,7 +291,7 @@ Although this library is able to successfully prevent deadlocks, livelocks may s # New traits ```rust -unsafe trait Lock { +unsafe trait RawLock { unsafe fn lock(&self); unsafe fn try_lock(&self) -> bool; unsafe fn unlock(&self); @@ -334,6 +315,310 @@ unsafe trait Lockable { // this is a bad name (LockGroup?) --- +## Solving self-referential data structures with references + +```rust +struct RefLockCollection<'a, L> { + data: &'a L, + locks: Vec<&'a dyn RawLock> +} +``` + +But what if I don't want to manage lifetimes? + +--- + +## Solving self-referential data structures with heap allocation + +```rust +struct BoxedLockCollection<L> { + data: *const UnsafeCell<L>, + locks: Vec<&'static dyn RawLock> +} +``` + +But what if I don't want to do any lock sorting? + +--- + +## Solving self-referential data structures with owned lockables + +```rust +struct OwnedLockCollection<L> { + data: L, +} +``` + +This doesn't allow immutable references to data, but also doesn't require any sorting + +But what if I don't have ownership of the locks? + +--- + +## Solving self-referential data structures with retrying locks + +```rust +struct RetryingLockCollection<L> { + data: L, +} +``` + +This is what we were trying to avoid earlier + +--- + +## Let's make four different lock collection types that do almost the same thing! + +- `BoxedLockCollection`: The default. Sorts the locks by memory address, and locks in that order. Heap allocation is required. + +- `RefLockCollection`: Same as boxed, but requires the caller to manage the lifetimes. + +- `RetryingLockCollection`: Mostly cheap to construct, but will usually fail to lock the data if there is any contention. + +- `OwnedLockCollection`: The cheapest option. Locks in the order given. No shared references to inner collection. + +--- + +## RwLocks in collections + +This is what I used in HappyLock 0.1: + +```rust +struct ReadLock<'a, T(&'a RwLock<T>); +struct WriteLock<'a, T(&'a RwLock<T>); +``` + +**Problem:** This can't be used inside of an `OwnedLockCollection` + +--- + +## Allowing reads on `OwnedLockCollection` + +```rust +// update RawLock +unsafe trait RawLock { + // * snip * + unsafe fn read(&self); + unsafe fn try_read(&self); + unsafe fn unlock_read(&self); +} + +// update Lockable +unsafe trait Lockable { + // * snip * + type ReadGuard<'g> where Self: 'g; + unsafe fn read_guard<'g>(&'g self) -> Self::ReadGuard<'g>; +} +``` + +--- + +## Not every lock can be read doe + +```rust +// This trait is used to indicate that reading is actually useful +unsafe trait Sharable: Lockable {} + +impl<L: Sharable> OwnedLockable<L> { + pub fn read<..>(&'g self, key: Key) -> LockGuard<..> { /* ... */ } + + pub fn try_read<..>(&'g self, key: Key) -> Option<LockGuard<..>> { /* ... */ } + + pub fn unlock_read<..>(guard: LockGuard<..>) { /* ... */ } +} + +// the same methods exist on other lock collections too +``` + +--- + +## Missing Features + +- `Condvar`/`Barrier` +- We probably don't need `OnceLock` or `LazyLock` +- Standard Library Backend +- Mutex poisoning +- Support for `no_std` +- Convenience methods: `lock_swap`, `lock_set`? +- `try_lock_swap` doesn't need a `ThreadKey` +- Going further: `LockCell` API (preemptive allocation) + +--- + +<!--_class: invert lead --> + +## What's next? + +--- + +## Poisoning + +```rust +unsafe impl<L: Lockable + Send + Sync> RawLock for LockCollection<L> + +pub struct Poisonable<L: Lockable + RawLock> { + inner: L, + poisoned: PoisonFlag, +} + +impl<L: Lockable + RawLock> Lockable for Poisonable<L> { + type Guard<'g> = Result<PoisonRef<'g, L::Guard>, PoisonErrorRef<'g, L::Guard>> + where Self: 'g; + + // and so on... +} +``` + +Allows: `Poisonable<LockCollection>` and `LockCollection<Poisonable>` + +--- + +## OS Locks + +- Using `parking_lot` makes the binary size much larger +- Unfortunately, it's impossible to implement `RawLock` on the standard library lock primitives +- Creating a new crate based on a fork of the standard library is hard +- Solution: create a new library (`sys_locks`), which exposes raw locks from the operating system +- This is more complicated than you might think + +--- + +## Expanding Cyclic Wait + +> ... sometimes you need to lock an object to read its value and determine what should be locked next... is there a way to address it? + +```rust +let guard = m1.lock(key); +if *guard == true { + let key = Mutex::unlock(m); + let data = [&m1, &m2]; + let collection = LockCollection::try_new(data).unwrap(); + let guard = collection.lock(key); + + // m1 might no longer be true here... +} +``` + +--- + +## What I Really Want + +```txt +ordered locks: m1, m2, m3 + +if m1 is true + lock m2 and keep m1 locked +else + skip m2 and lock m3 +``` + +We can specify lock orders using `OwnedLockCollection` + +Then we need an iterator over the collection to keep that ordering + +This will be hard to do with tuples (but might not be impossible) + +--- + +## Compile-Time Duplicate Checks + +As Mikhail keeps reminding me, it might be possible to do the duplicate detection at compile-time using a Bloom filter. This is something I'll have to try at some point. + +This would only be useful for `RetryingLockCollection` + +--- + +# Convenience Methods + +`Mutex::lock_swap`, `lock_clone`, etc would be cool + +\ +\ +\ +These methods would still require a `ThreadKey` though + +```rust +let guard = mutex.lock(key); +let cloned = mutex.lock_clone(); // deadlock +``` + +--- + +# Try-Convenience Methods + +- `Mutex::try_swap`, `try_set` would not require a `ThreadKey` +- They can't block the current thread (because `try`), and they can't block other threads (because they release the lock immediately) +- Same probably applies to `try_clone` and `try_take`, but could be a problem if the `Clone` implementation tries to lock something else + +--- + +## `LockCell` + +This would only allow methods tyo be called which immediately release the lock + +This would never require a `ThreadKey` + +Could run into bugs: + +```rust +let a: LockCell<i32>; +let b: LockCell<i32>; +if a == b { + // a and b are no longer equal +} +``` + +--- + +## Readonly Lock Collections + +- The original idea behind `Sharable` was to avoid duplicate checking on collections that will only ever be read. +- Reading can't cause a deadlock? Or so I thought. + +From the standard library documentation: + +```txt +// Thread 1 | // Thread 2 +let _rg1 = lock.read(); | + | // will block + | let _wg = lock.write(); +// may deadlock | +let _rg2 = lock.read(); | +``` + +--- + +## Recursive Trait + +Instead of `Sharable`, use a `Recursive` trait: + +```rust +unsafe trait Recursive: Lockable {} +``` + +Add a `Readonly` wrapper around collections of recursives: + +```rust +pub struct Readonly<L: Recursive> { + inner: L +} +``` + +A `Readonly` collection cannot be exclusively locked. + +--- + +## Others + +- No standard library + - hard, because of thread local, and allocation being required for lock collections +- Condvar and Barrier + - these have completely different deadlocking rules. someone else should figure this out +- LazyLock and OnceLock + - can these even deadlock? + +--- + <!--_class: invert lead --> ## The End @@ -169,6 +169,7 @@ mod key; pub mod collection; pub mod lockable; pub mod mutex; +pub mod poisonable; pub mod rwlock; pub use key::{Keyable, ThreadKey}; diff --git a/src/poisonable.rs b/src/poisonable.rs new file mode 100644 index 0000000..49979e5 --- /dev/null +++ b/src/poisonable.rs @@ -0,0 +1,46 @@ +#[cfg(not(panic = "unwind"))] +use std::convert::Infallible; +use std::marker::PhantomData; +use std::sync::atomic::AtomicBool; + +use crate::lockable::{Lockable, RawLock}; + +mod error; +mod flag; +mod guard; +mod poisonable; + +#[derive(Debug, Default)] +struct PoisonFlag(#[cfg(panic = "unwind")] AtomicBool); + +#[derive(Debug, Default)] +pub struct Poisonable<L: Lockable + RawLock> { + inner: L, + poisoned: PoisonFlag, +} + +pub struct PoisonRef<'flag, G> { + guard: G, + #[cfg(panic = "unwind")] + flag: &'flag PoisonFlag, +} + +pub struct PoisonGuard<'flag, 'key, G, Key> { + guard: PoisonRef<'flag, G>, + key: Key, + _phantom: PhantomData<&'key ()>, +} + +pub struct PoisonError<Guard> { + guard: Guard, +} + +pub enum TryLockPoisonableError<'flag, 'key, G, Key: 'key> { + Poisoned(PoisonError<PoisonGuard<'flag, 'key, G, Key>>), + WouldBlock(Key), +} + +pub type PoisonResult<Guard> = Result<Guard, PoisonError<Guard>>; + +pub type TryLockPoisonableResult<'flag, 'key, G, Key> = + Result<PoisonGuard<'flag, 'key, G, Key>, TryLockPoisonableError<'flag, 'key, G, Key>>; diff --git a/src/poisonable/error.rs b/src/poisonable/error.rs new file mode 100644 index 0000000..98a167c --- /dev/null +++ b/src/poisonable/error.rs @@ -0,0 +1,47 @@ +use core::fmt; +use std::error::Error; + +use super::{PoisonError, PoisonGuard, TryLockPoisonableError}; + +impl<Guard> fmt::Debug for PoisonError<Guard> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_struct("PoisonError").finish_non_exhaustive() + } +} + +impl<Guard> fmt::Display for PoisonError<Guard> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + "poisoned lock: another task failed inside".fmt(f) + } +} + +impl<Guard> Error for PoisonError<Guard> {} + +impl<'flag, 'key, G, Key> fmt::Debug for TryLockPoisonableError<'flag, 'key, G, Key> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match *self { + Self::Poisoned(..) => "Poisoned(..)".fmt(f), + Self::WouldBlock(_) => "WouldBlock".fmt(f), + } + } +} + +impl<'flag, 'key, G, Key> fmt::Display for TryLockPoisonableError<'flag, 'key, G, Key> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match *self { + Self::Poisoned(..) => "poisoned lock: another task failed inside", + Self::WouldBlock(_) => "try_lock failed because the operation would block", + } + .fmt(f) + } +} + +impl<'flag, 'key, G, Key> Error for TryLockPoisonableError<'flag, 'key, G, Key> {} + +impl<'flag, 'key, G, Key> From<PoisonError<PoisonGuard<'flag, 'key, G, Key>>> + for TryLockPoisonableError<'flag, 'key, G, Key> +{ + fn from(value: PoisonError<PoisonGuard<'flag, 'key, G, Key>>) -> Self { + Self::Poisoned(value) + } +} diff --git a/src/poisonable/flag.rs b/src/poisonable/flag.rs new file mode 100644 index 0000000..99e7e4f --- /dev/null +++ b/src/poisonable/flag.rs @@ -0,0 +1,36 @@ +use std::sync::atomic::AtomicBool; +use std::sync::atomic::Ordering::Relaxed; + +use super::PoisonFlag; + +impl PoisonFlag { + #[cfg(panic = "unwind")] + pub const fn new() -> Self { + Self(AtomicBool::new(false)) + } + + #[cfg(not(panic = "unwind"))] + pub const fn new() -> Self { + Self() + } + + #[cfg(panic = "unwind")] + pub fn is_poisoned(&self) -> bool { + self.0.load(Relaxed) + } + + #[cfg(not(panic = "unwind"))] + pub fn is_poisoned(&self) -> bool { + false + } + + #[cfg(panic = "unwind")] + pub fn clear_poison(&self) { + self.0.store(true, Relaxed) + } + + #[cfg(not(panic = "unwind"))] + pub fn clear_poison(&self) { + () + } +} diff --git a/src/poisonable/guard.rs b/src/poisonable/guard.rs new file mode 100644 index 0000000..97b0028 --- /dev/null +++ b/src/poisonable/guard.rs @@ -0,0 +1,92 @@ +use std::fmt::{Debug, Display}; +use std::ops::{Deref, DerefMut}; +use std::sync::atomic::Ordering::Relaxed; + +use crate::Keyable; + +use super::{PoisonGuard, PoisonRef}; + +impl<'flag, Guard> Drop for PoisonRef<'flag, Guard> { + fn drop(&mut self) { + #[cfg(panic = "unwind")] + if std::thread::panicking() { + self.flag.0.store(true, Relaxed); + } + } +} + +impl<'flag, Guard: Debug> Debug for PoisonRef<'flag, Guard> { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + Debug::fmt(&**self, f) + } +} + +impl<'flag, Guard: Display> Display for PoisonRef<'flag, Guard> { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + Display::fmt(&**self, f) + } +} + +impl<'flag, Guard> Deref for PoisonRef<'flag, Guard> { + type Target = Guard; + + fn deref(&self) -> &Self::Target { + &self.guard + } +} + +impl<'flag, Guard> DerefMut for PoisonRef<'flag, Guard> { + fn deref_mut(&mut self) -> &mut Self::Target { + &mut self.guard + } +} + +impl<'flag, Guard> AsRef<Guard> for PoisonRef<'flag, Guard> { + fn as_ref(&self) -> &Guard { + &self.guard + } +} + +impl<'flag, Guard> AsMut<Guard> for PoisonRef<'flag, Guard> { + fn as_mut(&mut self) -> &mut Guard { + &mut self.guard + } +} + +impl<'flag, 'key, Guard: Debug, Key: Keyable> Debug for PoisonGuard<'flag, 'key, Guard, Key> { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + Debug::fmt(&**self, f) + } +} + +impl<'flag, 'key, Guard: Display, Key: Keyable> Display for PoisonGuard<'flag, 'key, Guard, Key> { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + Display::fmt(&**self, f) + } +} + +impl<'flag, 'key, Guard, Key: Keyable> Deref for PoisonGuard<'flag, 'key, Guard, Key> { + type Target = Guard; + + fn deref(&self) -> &Self::Target { + &self.guard.guard + } +} + +impl<'flag, 'key, Guard, Key: Keyable> DerefMut for PoisonGuard<'flag, 'key, Guard, Key> { + fn deref_mut(&mut self) -> &mut Self::Target { + &mut self.guard.guard + } +} + +impl<'flag, 'key, Guard, Key: Keyable> AsRef<Guard> for PoisonGuard<'flag, 'key, Guard, Key> { + fn as_ref(&self) -> &Guard { + &self.guard.guard + } +} + +impl<'flag, 'key, Guard, Key: Keyable> AsMut<Guard> for PoisonGuard<'flag, 'key, Guard, Key> { + fn as_mut(&mut self) -> &mut Guard { + &mut self.guard.guard + } +} diff --git a/src/poisonable/poisonable.rs b/src/poisonable/poisonable.rs new file mode 100644 index 0000000..6c78346 --- /dev/null +++ b/src/poisonable/poisonable.rs @@ -0,0 +1,139 @@ +use std::marker::PhantomData; +use std::panic::{RefUnwindSafe, UnwindSafe}; + +use crate::lockable::{Lockable, RawLock}; +use crate::Keyable; + +use super::{ + PoisonError, PoisonFlag, PoisonGuard, PoisonRef, PoisonResult, Poisonable, + TryLockPoisonableError, TryLockPoisonableResult, +}; + +unsafe impl<L: Lockable + RawLock> Lockable for Poisonable<L> { + type Guard<'g> = PoisonResult<PoisonRef<'g, L::Guard<'g>>> where Self: 'g; + type ReadGuard<'g> = PoisonResult<PoisonRef<'g, L::ReadGuard<'g>>> where Self: 'g; + + fn get_ptrs<'a>(&'a self, ptrs: &mut Vec<&'a dyn RawLock>) { + self.inner.get_ptrs(ptrs) + } + + unsafe fn guard(&self) -> Self::Guard<'_> { + let ref_guard = PoisonRef { + guard: self.inner.guard(), + flag: &self.poisoned, + }; + + if self.is_poisoned() { + Ok(ref_guard) + } else { + Err(PoisonError { guard: ref_guard }) + } + } + + unsafe fn read_guard(&self) -> Self::ReadGuard<'_> { + let ref_guard = PoisonRef { + guard: self.inner.read_guard(), + flag: &self.poisoned, + }; + + if self.is_poisoned() { + Ok(ref_guard) + } else { + Err(PoisonError { guard: ref_guard }) + } + } +} + +impl<L: Lockable + RawLock> From<L> for Poisonable<L> { + fn from(value: L) -> Self { + Self::new(value) + } +} + +impl<L: Lockable + RawLock> Poisonable<L> { + pub const fn new(value: L) -> Self { + Self { + inner: value, + poisoned: PoisonFlag::new(), + } + } + + unsafe fn guard<'flag, 'key, Key: Keyable + 'key>( + &'flag self, + key: Key, + ) -> PoisonResult<PoisonGuard<'flag, 'key, L::Guard<'flag>, Key>> { + let guard = PoisonGuard { + guard: PoisonRef { + guard: self.inner.guard(), + flag: &self.poisoned, + }, + key, + _phantom: PhantomData, + }; + + if self.is_poisoned() { + Ok(guard) + } else { + Err(PoisonError { guard }) + } + } + + pub fn lock<'flag, 'key, Key: Keyable + 'key>( + &'flag self, + key: Key, + ) -> PoisonResult<PoisonGuard<'flag, 'key, L::Guard<'flag>, Key>> { + unsafe { + self.inner.lock(); + self.guard(key) + } + } + + pub fn try_lock<'flag, 'key, Key: Keyable + 'key>( + &'flag self, + key: Key, + ) -> TryLockPoisonableResult<'flag, 'key, L::Guard<'flag>, Key> { + unsafe { + if self.inner.try_lock() { + Ok(self.guard(key)?) + } else { + Err(TryLockPoisonableError::WouldBlock(key)) + } + } + } + + pub fn unlock<'flag, 'key, Key: Keyable + 'key>( + guard: PoisonGuard<'flag, 'key, L::Guard<'flag>, Key>, + ) -> Key { + drop(guard.guard); + guard.key + } + + pub fn is_poisoned(&self) -> bool { + self.poisoned.is_poisoned() + } + + pub fn clear_poison(&self) { + self.poisoned.clear_poison() + } + + pub fn into_inner(self) -> PoisonResult<L> { + if self.is_poisoned() { + Err(PoisonError { guard: self.inner }) + } else { + Ok(self.inner) + } + } + + pub fn get_mut(&mut self) -> PoisonResult<&mut L> { + if self.is_poisoned() { + Err(PoisonError { + guard: &mut self.inner, + }) + } else { + Ok(&mut self.inner) + } + } +} + +impl<L: Lockable + RawLock> RefUnwindSafe for Poisonable<L> {} +impl<L: Lockable + RawLock> UnwindSafe for Poisonable<L> {} |