From a650c42f422639004a29cae6eac2b2a666f5ba10 Mon Sep 17 00:00:00 2001 From: Mica White Date: Sat, 15 Mar 2025 17:14:20 -0400 Subject: Update presentation --- happylock.md | 396 ++++++++++++++++++++++++----------------------------------- 1 file changed, 162 insertions(+), 234 deletions(-) (limited to 'happylock.md') diff --git a/happylock.md b/happylock.md index 37b0640..5d7d51f 100644 --- a/happylock.md +++ b/happylock.md @@ -13,6 +13,38 @@ deadlock-free mutexes at compile-time --- + +# Background + +--- + +## Goals: Background + + - Quick refresh on the borrow checker + - What is a Mutex? + - How Rust does Mutexes + - What is a deadlock? + - How can deadlocks be prevented? + +--- + +## 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}"); +``` + +--- + ## What is a Mutex? It gives mutually-exclusive access for one thread, to prevent races. @@ -37,26 +69,9 @@ This prevents the number from being modified while it is being printed, which wo --- -## 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. +In Rust, the mutex is safer than in C. The mutex protects the data itself rather than sections of code. ```rust static NUMBER: Mutex = Mutex::new(1); @@ -64,7 +79,7 @@ static NUMBER: Mutex = 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(); + let mut number: MutexGuard<'_, i32> = NUMBER.lock().unwrap(); // MutexGuard is a smart pointer that we can modify directly *number += 5; @@ -76,7 +91,7 @@ fn thread_1() { ## What is a deadlock? -The lock function locks until no thread has acquired the thread key. +Locking a mutex in a way that makes it impossible to be unlocked. A simple way to cause deadlock is to lock twice on the same thread. @@ -160,22 +175,25 @@ Acquiring a new lock requires releasing all currently-held locks. --- -## How could an Operating System do this? +## Summary: Background -```c -#include + - Mutexes allow mutually exclusive access to memory + - Rust mutexes use the borrow checker to protect data, rather than sections of code + - The borrow checker ensures the mutex is used somewhat correctly + - Deadlocks prevent threads from making progress because a lock prevents unlocking + - We can prevent deadlocks using total allocation -void main() { - os_mutex_t m = os_mutex_create(); +--- - // the os returns an error if the rules aren't followed - if (os_mutex_lock(&m)) { - printf("Error!\n"); - } +# Preventing Deadlock - return 0; -} -``` +--- + +## Goals: Preventing Deadlock + + - Show how the borrow checker can enforce total allocation + - Lock multiple mutexes at the same time + - Make sure that we lock multiple mutexes, we don't lock the same one twice --- @@ -191,24 +209,19 @@ fn main() { let mutex = Mutex::new(10); - // locking a mutex requires either the ThreadKey or a &mut ThreadKey + // locking a mutex requires the ThreadKey let mut guard = mutex.lock(key); // this means that a thread cannot lock more than one thing at a time println!("{}", *guard); + + // you can get the ThreadKey back by unlocking + let key = Mutex::unlock(guard); } ``` --- -## Performance: it's freaking fast - -`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. - ---- - ## Wait, I need two mutexes ```rust @@ -227,8 +240,6 @@ fn main() { } ``` -This `LockCollection` can be implemented simply by releasing the currently acquired locks and retrying on failure - --- ## The Lockable API @@ -305,6 +316,30 @@ unsafe trait OwnedLockable: Lockable {} --- +## Summary: Preventing Deadlock + + - Using an owned `ThreadKey` type, we can ensure total allocation + - Using a `LockCollection`, we can lock multiple mutexes at the same time + - The marker trait, `OwnedLockable`, can be guaranteed to not contain duplicates at compile-time + - We can check for duplicates at runtime by checking the memory addresses of the locks + +--- + + +# Optimizations to HappyLock + +--- + +## Goals: Optimizations + + - Explain how exactly we check for duplicates + - Naively implement `LockCollection` + - Understand how live-locking hurts total allocation + - Rewrite our collections to prevent cyclic wait, which will improve performance + - Provide a way to create a user-defined locking order + +--- + ## `contains_duplicates` (1st attempt) ```rust @@ -340,6 +375,20 @@ Time Complexity: O(nlogn) --- +## RetryingLockCollection + +```rust +struct RetryingLockCollection { + data: L, +} +``` + +This will try to lock everything in the collection, and release everything if it fails. + +We keep trying until we've locked everything in a row. + +--- + ## Problem: Live-locking Although this library is able to successfully prevent deadlocks, livelocks may still be an issue. @@ -363,17 +412,6 @@ This pattern will probably end eventually, but we should really avoid it, for pe --- -## Problems with This Approach - -- 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 RawLock` - - Start by locking everything - - Then call a separate `guard` method to create the guard - ---- - # New traits ```rust @@ -384,7 +422,7 @@ unsafe trait RawLock { } unsafe trait Lockable { // this is a bad name (LockGroup?) - type Guard<'g>; + type Guard<'g> where Self: 'g; fn get_locks<'a>(&'a self, &mut Vec<&'a dyn RawLock>); unsafe fn guard<'g>(&'g self) -> Self::Guard<'g>; } @@ -392,28 +430,6 @@ unsafe trait Lockable { // this is a bad name (LockGroup?) --- -## Ok let's get started, oh wait - -- self-referential data structures - - for best performance: `RefLockCollection`, `BoxedLockCollection`, `OwnedLockCollection` -- `LockCollection::new_ref` doesn't work without sorting - - So as a fallback, provide `RetryingLockCollection`. It doesn't do any sorting, but unlikely to ever acquire the lock - ---- - -## 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 @@ -423,45 +439,50 @@ struct BoxedLockCollection { } ``` -But what if I don't want to do any lock sorting? +This is the default lock collection in HappyLock --- -## 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 +## Providing our own lock ordering -But what if I don't have ownership of the locks? + - What if we don't want to do any sorting? + - We could make a collection that allows us to define our own order + - This requires that no other ordering is used for the locks in that collection + - `OwnedLockable` can be used for this --- -## Solving self-referential data structures with retrying locks +## Solving self-referential data structures with owned lockables ```rust -struct RetryingLockCollection { +struct OwnedLockCollection { 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! +## Summary: Optimizations -- `BoxedLockCollection`: The default. Sorts the locks by memory address, and locks in that order. Heap allocation is required. + - Livelocking causes perpetual locking and unlocking and retries + - Locks are sorted by memory address before looking for duplicates + - `BoxedLockCollection` sorts in the order of the memory address + - `OwnedLockCollection` allows us to define our own lock order + - `RetryingLockCollection` has the original retry behavior -- `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. + +# Quality of Life Enhancements -- `OwnedLockCollection`: The cheapest option. Locks in the order given. No shared references to inner collection. +--- + +## Goals: Quality of Life + + - Try to lock a mutex using a `&mut ThreadKey` + - Take inspiration from scoped threads to ensure unlocking + - Use marker traits to allow read-only locks + - Use traits to implement `get_mut` and `into_inner` --- @@ -498,6 +519,10 @@ let guard = MUTEX1.lock(&mut key); let guard = MUTEX1.lock(&mut key); ``` +--- + +## Keyable + The problem is that this also compiles ```rust @@ -519,7 +544,15 @@ Let's take inspiration from scoped threads: fn scope<'env, F, T>(f: F) -> T where F: for<'scope> FnOnce(&'scope Scope<'scope, env>) -> T; +``` + +The `Drop` implementation of the `Scope` type will join all of the spawned threads. And because we only have a reference to the `Scope`, we'll never be able to `mem::forget` it. + +--- + +## Scoped Threads +```rust let mut a = vec![1, 2, 3]; let mut x = 0; @@ -537,10 +570,6 @@ scope(|scope| { }); ``` -The `Drop` implementation of the `Scope` type will join all of the spawned -threads. And because we only have a reference to the `Scope`, we'll never be -able to `mem::forget` it. - --- ## Scoped Locks @@ -549,28 +578,14 @@ Let's try the same thing for locks ```rust let mut key = ThreadKey::get().unwrap(); -let mutex_plus_one = MUTEX.scoped_lock(|guard: &mut i32| *guard + 1); -``` - -If you use scoped locks, then you can guarantee that locks will always be -unlocked (assuming you never immediately abort the thread). - ---- - -## 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); +let mutex_plus_one = MUTEX.scoped_lock(&mut key, |guard: &mut i32| *guard + 1); ``` -**Problem:** This can't be used inside of an `OwnedLockCollection` +If you use scoped locks, then you can guarantee that locks will always be unlocked (assuming you never immediately abort the thread). --- -## Allowing reads on `OwnedLockCollection` +## Allowing reads on `LockCollection` ```rust // update RawLock @@ -594,39 +609,15 @@ unsafe trait Sharable: Lockable { ## Not every lock can be read tho ```rust -impl OwnedLockable { +impl LockCollection { 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 -``` - ---- - -## 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` - --- ## `LockableGetMut` @@ -642,7 +633,7 @@ trait LockableGetMut: Lockable { } impl LockableGetMut for (A, B) { - type Inner = (A::Inner<'a>, B::Inner<'b>); + type Inner<'a> = (A::Inner<'a>, B::Inner<'b>); fn get_mut(&mut self) -> Self::Inner<'_> { (self.0.get_mut(), self.1.get_mut()) @@ -651,102 +642,26 @@ impl LockableGetMut for (A, B) { ``` --- - +## Summary: QoL Enhancements -## What's next? + - Using `&mut ThreadKey` won't work because someone could `mem::forget` a lock guard + - To guarantee unlocking, we can use a scoped API + - Marker traits can be used to indicate that a lock can be shared + - Traits can also provide other functionality, like `get_mut` --- -## 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 - ---- - -# 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 -``` - ---- - -## `LockCell` - -This would only allow methods to 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. + +# The Future: Expanding Cyclic Wait --- -## Others +## Goals: Expanding Cyclic Wait -- 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 - - These can deadlock, but it's very hard to do so accidentally + - Show that we sometimes need partial allocation + - Idealize how cyclic wait could be used in these scenarios + - Design an API that could use typestate to support cyclic wait and partial allocation + - Ensure that the `ThreadKey` is not used while multiple partially allocated guards are active --- @@ -872,7 +787,10 @@ But where do we store the `ThreadKey`? ```rust // This type will hold the ThreadKey -struct LockIteratorGuard<'a, 'key, L, Key: Keyable + 'key> +struct LockIteratorGuard<'a, L> { + collection: &'a OwnedLockCollection, + thread_key: ThreadKey, +} ``` --- @@ -896,6 +814,16 @@ LockIteratorGuard::next<'a>(&'a mut self) -> LockIterator<'a, L::Next> ``` --- - +## Summary: Expanding Cyclic Wait + + - Partial allocation is needed in situations like skip lists + - Cyclic wait can be used as a backup in these situations + - Typestate allows us to iterate over the elements of a tuple + - A `ThreadKey` must be stored somewhere while the partially allocated guards are active + - Immutable references to the `ThreadKey` can prove that the `ThreadKey` is not used until *all* of the guards are dropped + +--- + + ## The End -- cgit v1.2.3