Merge branch '0.2'

1 files changed, 339 insertions, 0 deletions

diff --git a/happylock.md b/happylock.md
new file mode 100644
index 0000000..477e99b
--- /dev/null
+++ b/happylock.md
@@ -0,0 +1,339 @@
+---
+marp: true
+theme: gaia
+class: invert
+---
+
+<!-- _class: lead 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<T>` type?
+
+Just use `Arc<T>` 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 <oslock.h>
+
+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<Self::Guard>;
+}
+```
+
+---
+
+## 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<L: OwnedLockable> LockCollection<L> {
+    pub fn new(data: L) -> Self { /***/ }
+}
+
+impl<L: OwnedLockable> LockCollection<&L> {
+    pub fn new_ref(data: &L) -> Self { /***/ }
+}
+
+impl<L: Lockable> LockCollection<L> {
+    // checks for duplicates
+    pub fn try_new(data: L) -> Option<Self> { /***/ }
+
+    pub unsafe fn new_unchecked(data: L) -> Self { /***/ }
+}
+```
+
+---
+
+## Changes to Lockable
+
+```rust
+unsafe trait Lockable {
+    // ...
+
+    fn get_ptrs(&self) -> Vec<usize>;
+}
+
+
+
+// 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<L: Lockable>(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<L: Lockable>(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)
+
+---
+
+<!--_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.
+
+---
+
+## 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
+
+---
+
+<!--_class: invert lead -->
+
+## The End