--- marp: true theme: gaia class: invert --- # HappyLock deadlock-free mutexes at compile-time --- ## Four Conditions for Deadlock 1. Mutual Exclusion 2. Non-preemptive Allocation 3. Cyclic Wait 4. Partial Allocation --- ## Preventing Mutual Exclusion Mutual exclusion is the entire point of a mutex. Do you want a `ReadOnly` type? Just use `Arc` or `&T`! --- ## Prevent Non-Preemptive Allocation ```rust let mutex = Mutex::new(10); let mut number = mutex.lock(); let th = thread::spawn(|| { let number = mutex.lock(); // preempts the other lock on number }); th.join(); prinln!("Thread 1: {}", *number); // oops, we don't have access to number anymore! ``` --- ## Preventing Cyclic Wait The language needs to enforce that all locks are acquired in the same order. Rust doesn't have a built-in mechanism which can provide this. Even if it could keep the locks in a certain order, using a `OrderedLock` type, we wouldn't be able to force you to use the mechanism. And you could create two `OrderedLock` types and get deadlock using that. --- ## Preventing Partial Allocation The language needs to enforce *total allocation*. Acquiring a new lock requires releasing all currently-held locks. **This will be our approach for now.** --- ## 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 #include 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"); } return 0; } ``` --- ## We have technology! (the borrow checker) ```rust use happylock::{ThreadKey, Mutex}; fn main() { // each thread can only have one thread key (that's why we unwrap) // ThreadKey is not Send, Sync, Copy, or Clone let key = ThreadKey::get().unwrap(); let mutex = Mutex::new(10); // locking a mutex requires either the ThreadKey or a &mut ThreadKey let mut guard = mutex.lock(key); // this means that a thread cannot lock more than one thing at a time println!("{}", *guard); } ``` --- ## 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. `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 use happylock::{ThreadKey, Mutex, LockCollection}; fn main() { let key = ThreadKey::get().unwrap(); let mutex1 = Mutex::new(5); let mutex2 = Mutex::new(String::new()); let collection = LockCollection::new((mutex1, mutex2)); let guard = collection.lock(key); *guard.1 = format!("{}{}", *guard.1, guard.0); *guard.0 += 1; } ``` --- ## The Lockable API ```rust unsafe trait Lockable { type Guard; unsafe fn lock(&self) -> Self::Guard; unsafe fn try_lock(&self) -> Option; } ``` --- ## That's cool! Lemme try something ```rust use happylock::{ThreadKey, Mutex, LockCollection}; fn main() { let key = ThreadKey::get().unwrap(); let mutex1 = Mutex::new(5); // oh no. this will deadlock us let collection = LockCollection::new((&mutex1, &mutex1)); let guard = collection.lock(key); // the good news is: this doesn't compile } ``` --- ## LockCollection's stub ```rust impl LockCollection { pub fn new(data: L) -> Self { /***/ } } impl LockCollection<&L> { pub fn new_ref(data: &L) -> Self { /***/ } } impl LockCollection { // checks for duplicates pub fn try_new(data: L) -> Option { /***/ } pub unsafe fn new_unchecked(data: L) -> Self { /***/ } } ``` --- ## Changes to Lockable ```rust unsafe trait Lockable { // ... fn get_ptrs(&self) -> Vec; } // not implemented for &L // ergo: the values within are guaranteed to be unique unsafe trait OwnedLockable: Lockable {} ``` --- ## `contains_duplicates` (1st attempt) ```rust fn contains_duplicates(data: L) -> bool { let pointers = data.get_ptrs(); for (i, ptr1) in pointers.iter().enumerate() { for ptr2 in pointers.iter().take(i) { if ptr1 == ptr2 { return true; } } } false } ``` Time Complexity: O(n²) --- ## 2nd attempt: sorting the pointers ```rust fn contains_duplicates(data: L) -> bool { let mut pointers = data.get_ptrs(); pointers.sort_unstable(); pointers.windows(2).any(|w| w[0] == w[1]) } ``` 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. --- ## Solution: Switch to preventing cyclic wait - We're already sorting the pointers by memory address. - So let's keep that order! --- ## 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 Lock` - Start by locking everything - Then call a separate `guard` method to create the guard --- # New traits ```rust unsafe trait Lock { unsafe fn lock(&self); unsafe fn try_lock(&self) -> bool; unsafe fn unlock(&self); } unsafe trait Lockable { // this is a bad name (LockGroup?) type Guard<'g>; fn get_locks<'a>(&'a self, &mut Vec<&'a dyn Lock>); unsafe fn guard<'g>(&'g self) -> Self::Guard<'g>; } ``` --- ## 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 --- ## The End