From bd64ff98530ea5f92ce528009d65203f0f6676fe Mon Sep 17 00:00:00 2001 From: Mica White Date: Wed, 17 Jul 2024 16:37:21 -0400 Subject: Create Poisonable API --- happylock.md | 325 +++++++++++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 305 insertions(+), 20 deletions(-) (limited to 'happylock.md') 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) - ---- - - - -## 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 { + data: *const UnsafeCell, + 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 { + 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 { + 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); +struct WriteLock<'a, T(&'a RwLock); +``` + +**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 OwnedLockable { + pub fn read<..>(&'g self, key: Key) -> LockGuard<..> { /* ... */ } + + pub fn try_read<..>(&'g self, key: Key) -> Option> { /* ... */ } + + 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) + +--- + + + +## What's next? + +--- + +## Poisoning + +```rust +unsafe impl RawLock for LockCollection + +pub struct Poisonable { + inner: L, + poisoned: PoisonFlag, +} + +impl Lockable for Poisonable { + type Guard<'g> = Result, PoisonErrorRef<'g, L::Guard>> + where Self: 'g; + + // and so on... +} +``` + +Allows: `Poisonable` and `LockCollection` + +--- + +## 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; +let b: LockCell; +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 { + 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? + +--- + ## The End -- cgit v1.2.3