diff options
Diffstat (limited to 'happylock.md')
| -rw-r--r-- | happylock.md | 197 |
1 files changed, 148 insertions, 49 deletions
diff --git a/happylock.md b/happylock.md index 973b819..c157e19 100644 --- a/happylock.md +++ b/happylock.md @@ -13,6 +13,96 @@ deadlock-free mutexes at compile-time --- +## What is a Mutex? + +It gives mutually-exclusive access for one thread, to prevent races. + +```c +static pthread_mutex_t mutex = PTHREAD_MUTEX_INIT; +static int number = 1; + +void thread_1() { + pthread_mutex_lock(&mutex); + number = 6; + pthread_mutex_unlock(&mutex); +} +void thread_2() { + pthread_mutex_lock(&mutex); + printf("%d", number); + pthread_mutex_unlock(&mutex); +} +``` + +This prevents the number from being modified while it is being printed, which would cause undefined behavior. + +--- + +## Quick Refresh on Borrow Checker Rules + +1. You may have multiple immutable references to a value at a time +2. If there is a mutable reference to a value, then it is the only reference +3. Values cannot be moved while they are being referenced + +```rust +let s = String::new("Hello, world!"); +let r1 = &s; +let r2 = &s; // this is allowed because of #1 +let mr = &mut s; // illegal: rule #2 +drop(s); // also illegal: rule #3 +println!("{r1} {r2}"); +``` + +--- + +## Rust Mutexes + +In Rust, the mutex is safer than in C. The mutex protects data the data itself rather than sections of code. + +```rust +static NUMBER: Mutex<i32> = Mutex::new(1); + +fn thread_1() { + // MutexGuard grants access to the data inside of the mutex + // We cannot access this data without locking first + let number: MutexGuard<'_, i32> = NUMBER.lock().unwrap(); + // MutexGuard is a smart pointer that we can modify directly + *number += 5; + + // when the MutexGuard goes out of scope, it unlocks the mutex for you +} +``` + +--- + +## What is a deadlock? + +The lock function locks until no thread has acquired the thread key. + +A simple way to cause deadlock is to lock twice on the same thread. + +```rust +let number = Mutex::new(1); +let guard1 = number.lock().unwrap(); +// now everybody has to wait until guard1 is dropped + +let guard2 = number.lock().unwrap(); // but wait, guard1 still exists +// and we can't drop guard1, because we have to wait for this to finish +// THIS IS A DEADLOCK! (in C, this causes undefined behavior) + +// we'll never get to do this +println!("{guard1} {guard2}"); +``` + +--- + +## The Dining Philosopher's Problem + +This is another example of deadlock, which is in the category of "deadly embrace" + +<img src="https://external-content.duckduckgo.com/iu/?u=https%3A%2F%2Ffiles.codingninjas.in%2Farticle_images%2Fdining-philosopher-problem-using-semaphores-1-1643507259.jpg&f=1&nofb=1&ipt=d8d17865fc8cb4c2e66454e6833d43e83f3965573786c2c54cff601bae03e8a3&ipo=images" height="480" /> + +--- + ## Four Conditions for Deadlock 1. Mutual Exclusion @@ -70,23 +160,6 @@ Acquiring a new lock requires releasing all currently-held locks. --- -## Quick Refresh on Borrow Checker Rules - -1. You may have multiple immutable references to a value at a time -2. If there is a mutable reference to a value, then it is the only reference -3. Values cannot be moved while they are being referenced - -```rust -let s = String::new("Hello, world!"); -let r1 = &s; -let r2 = &s; // this is allowed because of #1 -let mr = &mut s; // illegal: rule #2 -drop(s); // also illegal: rule #3 -println!("{r1} {r2}"); -``` - ---- - ## How could an Operating System do this? ```c @@ -130,7 +203,7 @@ fn main() { ## Performance: it's freaking fast -`ThreadKey` is a mostly zero-cosst abstraction. It takes no memory at runtime. The only cost is getting and dropping the key. +`ThreadKey` is a mostly zero-cost abstraction. It takes no memory at runtime. The only cost is getting and dropping the key. `Mutex` is a thin wrapper around `parking_lot`. There's also a `spin` backend if needed for some reason. @@ -295,7 +368,7 @@ This pattern will probably end eventually, but we should really avoid it, for pe - I can't sort a tuple - Don't return them sorted, silly - Indexing the locks in the right order - - Have `get_ptrs` return a `&dyn Lock` + - Have `get_ptrs` return a `&dyn RawLock` - Start by locking everything - Then call a separate `guard` method to create the guard @@ -312,7 +385,7 @@ unsafe trait RawLock { unsafe trait Lockable { // this is a bad name (LockGroup?) type Guard<'g>; - fn get_locks<'a>(&'a self, &mut Vec<&'a dyn Lock>); + fn get_locks<'a>(&'a self, &mut Vec<&'a dyn RawLock>); unsafe fn guard<'g>(&'g self) -> Self::Guard<'g>; } ``` @@ -416,10 +489,10 @@ unsafe trait RawLock { unsafe fn unlock_read(&self); } -// update Lockable -unsafe trait Lockable { - // * snip * +// This trait is used to indicate that reading is actually useful +unsafe trait Sharable: Lockable { type ReadGuard<'g> where Self: 'g; + unsafe fn read_guard<'g>(&'g self) -> Self::ReadGuard<'g>; } ``` @@ -429,9 +502,6 @@ unsafe trait Lockable { ## Not every lock can be read tho ```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<..> { /* ... */ } @@ -467,7 +537,7 @@ Allows: `Poisonable<LockCollection>` and `LockCollection<Poisonable>` --- -# `LockableGetMut` and `LockableIntoInner` +# `LockableGetMut` ```rust fn Mutex::<T>::get_mut(&mut self) -> &mut T // already exists in std @@ -508,7 +578,6 @@ impl<A: LockableGetMut, B: LockableGetMut> LockableGetMut for (A, B) { --- - ## OS Locks - Using `parking_lot` makes the binary size much larger @@ -519,14 +588,6 @@ impl<A: LockableGetMut, B: LockableGetMut> LockableGetMut for (A, B) { --- -## 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 @@ -543,17 +604,9 @@ 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 only allow methods to be called which immediately release the lock This would never require a `ThreadKey` @@ -614,9 +667,10 @@ A `Readonly` collection cannot be exclusively locked. - Condvar and Barrier - these have completely different deadlocking rules. someone else should figure this out - LazyLock and OnceLock - - can these even deadlock? + - These can deadlock, but it's very hard to do so accidentally --- + ## 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? @@ -624,7 +678,7 @@ A `Readonly` collection cannot be exclusively locked. ```rust let guard = m1.lock(key); if *guard == true { - let key = Mutex::unlock(m); + let key = Mutex::unlock(guard); let data = [&m1, &m2]; let collection = LockCollection::try_new(data).unwrap(); let guard = collection.lock(key); @@ -660,7 +714,7 @@ This will be hard to do with tuples (but is not be impossible) let key = ThreadKey::get().unwrap(); let collection: OwnedLockCollection<(Vec<i32>, Vec<String>); let iterator: LockIterator<(Vec<i32>, Vec<String>)> = collection.locking_iter(key); -let (guard, next: LockIterator<Vec<String>>) = collection.next(); +let (guard, next: LockIterator<Vec<String>>) = iterator.next(); unsafe trait IntoLockIterator: Lockable { type Next: Lockable; @@ -712,12 +766,57 @@ impl<Current, Rest> LockIterator<Current, Rest> { We're going to be returning a lot of guards. -The `ThreadKey` is held by the `LockIterator`. +The `ThreadKey` needs to be held somewhere while the guards are active. **How do we ensure that the `ThreadKey` is not used again until all of the guards are dropped?** --- +## The Solution + +First, every guard needs to have an immutable reference to the `ThreadKey`. + +```rust +// this is the MutexGuard that doesn't hold a ThreadKey +// We'll modify it to hold an immutable reference to the ThreadKey +// ThreadKey cannot be moved or mutably referenced during this lifetime +struct MutexRef<'a, 'key, T, Key: Keyable + 'key> +struct RwLockReadRef<'a, 'key, T, Key: Keyable + 'key> +struct RwLockWriteRef<'a, 'key, T, Key: Keyable + 'key> +``` + +--- + +## The Solution + +But where do we store the `ThreadKey`? + +```rust +// This type will hold the ThreadKey +struct LockIteratorGuard<'a, 'key, L, Key: Keyable + 'key> +``` + +--- + +## The Solution + +Then `LockIterator` must hold a reference to the guard. + +```rust +struct LockIterator<'a, Current, Rest = ()> +``` + +--- + +## The Solution + +And we can get the first LockIterator by taking a mutable reference to the guard. + +```rust +LockIteratorGuard::next<'a>(&'a mut self) -> LockIterator<'a, L::Next> +``` + +--- <!--_class: invert lead --> ## The End |