First commit

1 files changed, 555 insertions, 0 deletions

diff --git a/src/blog/unwind-safety-happylock.kuht b/src/blog/unwind-safety-happylock.kuht
new file mode 100755
index 0000000..61c36c8
--- /dev/null
+++ b/src/blog/unwind-safety-happylock.kuht
@@ -0,0 +1,555 @@
+<import "base.kuht" as "base" />
+
+<head>
+	<title>Poisoning, Unwind Safety, Exception Safety, and More in HappyLock</title>
+	<meta name="description" content="HappyLock 0.4 is now out! This is a journey in all things related to safety and panics." />
+</head>
+
+<body>
+
+<article>
+
+<h1>Poisoning, Unwind Safety, Exception Safety, and More in HappyLock</h1>
+
+<p>
+	I'm proud to announce that HappyLock 0.4 has been released. I thought that I should focus on
+	poisoning because I thought, at the time, that it would be simple. I was very wrong. Poisoning
+	exposed a whack-a-mole of challenges to solve, which I will illustrate here. 
+</p>
+
+<h2>A Refresher on HappyLock</h2>
+
+<p>
+	I recommend reading the full article on HappyLock. I've been told it's a very good read. But I'll
+	briefly explain the idea here. Those of you who have already read the full post can skip ahead to
+	the new stuff.
+</p>
+
+<p>
+	HappyLock uses the Rust borrow checker to make deadlocks impossible at compile-time. This is done by
+	having a <code>ThreadKey</code> which is not <code>Send</code>, <code>Copy</code>, or
+	<code>Clone</code>. But it is now <code>Sync</code>. Only one <code>ThreadKey</code> can exist
+	on each thread at a time. In order to lock anything, you must pass either a <code>ThreadKey</code>
+	or a <code>&amp;mut ThreadKey</code> into the <code>lock</code> function. This means that in order to
+	lock anything new, you must first release any resources you have already acquired, preventing partial
+	allocation.
+</p>
+
+<pre>
+fn main() {
+	// This panics if the ThreadKey has already been acquired for this thread
+	let mut key = ThreadKey::get().unwrap();
+
+	let mutex1 = Mutex::new(42);
+	let mutex2 = Mutex::new(76);
+
+	thread::spawn(|| {
+		// You're allowed to have more than one ThreadKey, but not on the same thread
+		let key = ThreadKey::get().unwrap();
+
+		let guard = mutex.lock(&amp;mut key); // Note the key. Nothing else can use it now
+		*guard = 24;
+		drop(guard); // Now we can use the ThreadKey again
+
+		let guard = mutex2.lock(&amp;mut key);
+		*guard = 67;
+	}).join().unwrap();
+
+	let guard = mutex.lock(&amp;mut key);
+	assert_eq!(guard, 24);
+	// the guard is implicitly dropped here
+	let guard = mutex.lock(&amp;mut key);
+	assert_eq!(guard, 67);
+}
+</pre>
+
+<p>
+	If you want to lock multiple mutexes at the same time, you can use a <code>LockCollection</code>,
+	which will ensure that all locks are acquired at the same time, so there's no possibility of deadlock.
+	By default, this works by sorting all of the locks by their memory address, preventing circular wait,
+	but there are other ways to do this with different performance qualities.
+</p>
+
+<pre>
+fn main() {
+	let key = ThreadKey::get().unwrap();
+	let collection = LockCollection::new((Mutex::new(42), Mutex::new("foo")));
+	let guard = collection.lock(key);
+	assert_eq!(guard.0, 42);
+	assert_eq!(guard.1, "foo");
+}
+</pre>
+
+<p>
+	Lots of things can be used in a <code>LockCollection</code>, which have the <code>Lockable</code> trait.
+	There's also the <code>RawLock</code> trait, which is implemented for <code>Mutex</code> and
+	<code>RwLock</code>.
+</p>
+
+
+<h2>What is Unwind Safety</h2>
+
+<p>
+	Unwind safety has nothing to do with the conventional notion of safety in Rust. And although
+	object-safety has recently been rebranded to dyn-compatible, unwind safety cannot be. The notion
+	of unwind safety is actually the entire reasoning why poisoning exists. Imagine the following
+	incredibly contrived scenario.
+</p>
+
+<pre>
+struct MultipleOfFive(i8);
+
+impl MultipleOfFive {
+	fn increment(&amp;mut self) {
+		catch_unwind(|| {
+			for _ in 0..5 {
+				self.0 += 1;
+			}
+		});
+	}
+}
+</pre>
+
+<p>
+	The variant that is supposed to be held here is that a <code>MultipleOfFive</code> is always
+	divisible by five. But what happens if debug assertions are enabled, and our value is 125?
+</p>
+
+<pre>
+125 + 1 = 126
+126 + 1 = 127
+127 + 1 ??? integer overflow! panic!
+</pre>
+
+<p>
+	But, we caught that panic, so now the value will always be 127, even though 127 is not divisible
+	by five. This doesn't result in undefined behavior. It's just very bizarre. This is the purpose
+	of the <code>UnwindSafe</code> trait. It asserts that unwinding won't result in unexpected behavior
+	for the type. In fact, the code from before doesn't compile.
+</p>
+
+<pre>
+struct MultipleOfFive(i8);
+
+impl MultipleOfFive {
+	fn increment(&amp;mut self) {
+		catch_unwind(|| {
+			for _ in 0..5 {
+				self.0 += 1; // compile error: mutable references are not unwind-safe
+			}
+		});
+	}
+}
+</pre>
+
+<p>
+	But again, this cannot be used to prevent undefined behavior. To make this point clear, there
+	is a wrappper type in the standard library that actually lets us work around unwind-safety. We
+	can just use <code>AssertUnwindSafe</code>, which is completely safe to construct.
+</p>
+
+<pre>
+struct MultipleOfFive(i8);
+
+impl MultipleOfFive {
+	fn increment(&amp;mut self) {
+		let this = AssertUnwindSafe(self);
+		catch_unwind(move || {
+			for _ in 0..5 {
+				(*this).0 += 1;
+			}
+		});
+	}
+}
+</pre>
+
+<p>
+	So that begs the question: if mutable references are not unwind safe, why is <code>Mutex</code>
+	unwind safe? That's because of poisoning. Any time when a panic is caught while a 
+	<code>MutexGuard</code> is in scope, the mutex gets poisoned. Any future calls to <code>lock</code>
+	on that mutex will return a <code>PoisonError</code>. Then, it becomes the responsibility of the
+	caller to decide how to handle that error. Most people don't care and just `unwrap` the result.
+	Most people seem to think that providing poisoning by default in the standard library was a mistake.
+	Several locking crates, like parking lot and spin, don't include poisoning at all. There's even some
+	work being done to provide non-poisoning variations of the locking primitive in the standard library.
+	For HappyLock, I want to provide as many of the standard library's features as possible, so I worked
+	out an alternative approach where you can get poisoning, but not by default.
+</p>
+
+<h2>How to Poison a Mutex</h2>
+
+<p>
+	I decided to implement poisoning in the simplest way I could think of. HappyLock is already
+	filled with wrappers, so why not use one here too? Put simply, the implementation looks like
+	this:
+</p>
+
+<pre>
+struct Poisonable&lt;L: RawLock + Lockable> { /* ... */ }
+
+impl Poisonable&lt;L> {
+	// this is way over-simplified but you probably get the point
+	pub fn lock(&amp;self) -> PoisonGuard&lt;L::Guard>;
+}
+</pre>
+
+<p>
+	Unlike with <code>LockCollection</code>, <code>Poisonable</code> requires that <code>L</code> be
+	a <code>RawLock</code>. That's because <code>Poisonable</code> can't decide on its own how to deal
+	with multiple locks without deadlocking. That's the purpose of <code>LockCollection</code>. But,
+	<code>RawLock</code> already has a <code>lock</code> method, so it's easy to just call that to
+	lock whatever we need.
+</p>
+
+<p>
+	At the same time, it would be nice if we could put a <code>LockCollection</code> inside of a
+	<code>Poisonable</code>. So, <code>LockCollection</code> now implements <code>RawLock</code>,
+	so you can create a <code>Poisonable&lt;LockCollection&lt;Vec&lt;Mutex&lt;String>>>></code>
+	and not unwrap every single mutex.
+</p>
+
+<p>
+	There's another method that the standard library's <code>Mutex</code> has that is much harder to
+	implement: <code>get_mut</code>. This is already implemented on HappyLock's <code>Mutex</code>. It
+	also exists on the lock collections, but instead of getting mutable references to the data being
+	locked, it actually returns the collection. For example,
+	<code>LockCollection&lt;Vec&lt;Mutex&lt;i32>>>::get_mut</code> returns a
+	<code>&amp;mut Vec&lt;Mutex&lt;i32>></code>. Doing the same thing on a <code>Poisonable</code> would
+	require calling <code>get_mut</code> twice where the standard library only requires it to be called
+	once.
+</p>
+
+<p>
+	So, I've made a couple more traits: <code>LockableGetMut</code> and <code>LockableIntoInner</code>
+</p>
+
+<pre>
+trait LockableGetMut {
+	type Inner&lt;'a>;
+
+	fn get_mut(&amp;mut self) -> Self::Inner&lt;'_>;
+}
+
+trait LockableIntoInner {
+	type Inner;
+
+	fn into_inner(self) -> Self::Inner;
+}
+</pre>
+
+<p>
+	You might wonder, why not just have the same <code>Inner</code> type on both traits, and then we can
+	have <code>get_mut</code> return <code>&amp;mut Self::Inner</code>. But consider the case of a tuple.
+	In order to have a method like <code>get_mut</code>, we have to create a new tuple with a different
+	type that has no mutexes. But we can't return a mutable reference to a tuple we just created! But,
+	we <em>can</em> implement the function quite simply with this system.
+</p>
+
+<pre>
+impl&lt;A: LockableGetMut, B: LockableGetMut> LockableGetMut for (A, B) {
+	type Inner&lt;'a> = (A::Inner&lt;'a>, B::Inner&lt;'a>);
+
+	fn get_mut(&amp;mut self) -> Self::Inner&lt;'_> {
+		(self.0.get_mut(), self.1.get_mut())
+	}
+}
+</pre>
+
+<p>
+	For consistency, lock collections now also use this functionality, and the previous <code>into_inner</code>
+	method is now called <code>into_child</code>. This is a breaking change, but there are other breaking
+	changes that we'll also need to make here, as we'll soon see.
+</p>
+
+<h2>The Exception Safety of HappyLock</h2>
+
+<p>
+	Exception safety is a less optional form of unwind safety. The Rustonomicon actually refers to
+	unwind-safety as "maximal exception safety". But even if we don't always guarantee that safe code
+	will have the correct behavior, we need to at least make sure that our types are exception-safe
+	to the point where unwinding does not cause potential unwind safety. Here's an example of how this
+	could be violated.
+</p>
+
+<pre>
+impl&lt;T: Clone> Vec&lt;T> {
+	fn push(&mut self, x: &T) {
+		self.reserve(1);
+		unsafe {
+			self.set_len(self.len() + 1);
+			self.ptr().add(1).write(x.clone());
+		}
+	}
+}
+</pre>
+
+<p>
+	The problem is that <code>clone</code> can panic, because you can implement it however you want.
+	If it panics, then the length will be incorrect forever. This is something that you'll always need
+	to be careful about in unsafe code. Now, look at this function in HappyLock.
+</p>
+
+<pre>
+impl&lt;L: OwnedLockable> OwnedLockCollection&lt;L> {
+	pub fn lock&lt;'g, 'key, Key: Keyable + 'key>(
+		&'g self,
+		key: Key,
+	) -> LockGuard&lt;'key, L::Guard&lt;'g>, Key> {
+		let locks = get_locks(&self.data);
+		for lock in locks {
+			// safety: we have the thread key, and these locks happen in a
+			//         predetermined order
+			unsafe { lock.lock() };
+		}
+
+		let guard = unsafe { self.data.guard() };
+		LockGuard {
+			guard,
+			key,
+			_phantom: PhantomData,
+		}
+	}
+}
+</pre>
+
+<p>
+	As we can see, it is considered undefined behavior in HappyLock to cause a deadlock. Now, what
+	would happen if we had a collection of three locks, and the second one panicked. The first mutex
+	would never unlock, and then we could call it again, causing a deadlock, like this.
+</p>
+
+<pre>
+fn main() {
+	let collection = OwnedLockCollection::new((
+		Mutex::new(1),
+		Mutex::new(2),
+		Mutex::new(3)
+	));
+
+	catch_unwind(|| {
+		let key = ThreadKey::get().unwrap();
+		collection.lock();
+		// We'll say for the sake of argument that our second mutex panics here
+		// The first mutex was never unlocked
+	});
+
+	// The ThreadKey was still dropped, so we can re-acquire it.
+	let key = ThreadKey::get().unwrap();
+
+	// But wait, the first mutex is still locked by this thread.
+	collection.lock(); // DEADLOCK!!!
+}
+</pre>
+
+<p>
+	Note that this only becomes a problem if, somehow, parking_lot panics when calling the
+	<code>lock</code> function. This would be considered a bug, but since you can use whatever
+	<code>RawMutex</code> you want with HappyLock, I can't guarantee that this will never happen.
+	This could be solved by just requiring a specific underlying API to be used, but I'm not ready
+	to impose that restriction (yet). Somebody at RustConf suggested using a fancy guard insertion
+	strategy so that the mutexes will automatically unlock on panic. That might work, but I have
+	a simpler solution.
+</p>
+
+<p>
+	We can use the <code>scopeguard</code> library to automatically run code when unwinding. What
+	we'll need to do is keep track of which locks have been locked so far, and then, if we start
+	unwinding, unlock them.
+</p>
+
+<p>
+	Now, if you use the <code>scopeguard</code> crate, this will actually result in a stack overflow,
+	depending on how rigourously you check for this. It won't check to make sure that the panic was
+	caused by your function, so it will keep calling itself, and you'll get a stack overflow. So I
+	made my own utility to check that the unwinding was caused by a specific piece of code
+</p>
+
+<pre>
+fn handle_unwind&lt;R, F: FnOnce -> R, G: FnOnce()>(try_fn: F, catch: G) -> R {
+	let try_fn = AssertUnwindSafe(try_fn);
+	catch_unwind(try_fn).unwrap_or_else(|e| {
+		catch();
+		resume_unwind(e)
+	})
+}
+</pre>
+
+<p>Then we can use it to unlock on failure, like so</p>
+
+<pre>
+unsafe fn ordered_lock(locks: &[&dyn RawLock]) {
+	let locked = Cell::new(0);
+
+	handle_unwind(
+		|| {
+			for lock in locks {
+				lock.raw_lock();
+				locked.set(locked.get() + 1);
+			}
+		},
+		|| attempt_to_recover_locks_from_panic(&locked[0..locked.get()]),
+	)
+}
+
+unsafe fn attempt_to_recover_locks_from_panic(locked: &amp;[&amp;dyn RawLock]) {
+	handle_unwind(
+		|| locked.for_each(|lock| lock.raw_unlock()),
+		|| locked.for_each(|l| l.poison()),
+	)
+}
+</pre>
+
+<p>
+	Ok, so I lied when I said there's no poisoning by default. It's not documented anywhere, but yeah.
+	If the unlock function panics, when we're kinda screwed, so all <code>RawLock</code>s now have to
+	be poisonable. This is a different kind of poisoning, which causes all future calls to the mutex to
+	panic, similar to the poisoning of <code>Once</code>. It's not exposed in the signatures for any of
+	the functions. I don't want you to ever have to think about this kind of poisoning. I emphasize,
+	this should never happen. If it does, then the <code>RawMutex</code> probably contains a bug that
+	already needs to be fixed.
+</p>
+
+<p>
+	The lock that panicked is poisoned, regardless of whether it was locked or not. That's because I have
+	zero clue whether or not it actually locked. I would hope that if the <code>lock</code> function
+	panics, it didn't lock, but I don't know that for sure. I also don't have a good way to check, without
+	excluding support for certain mutexes in the future. Someone might suggest using the result of
+	<code>try_lock</code> to check if it's locked or not, and then unlock it in either case. That person
+	might be surprised to learn that, in C, it is undefined behavior to call <code>try_lock</code> on
+	a mutex that is already acquired by the calling thread. So there's not much I can do other than panic
+	here.
+</p>
+
+<h2>Miscellaneous Changes</h2>
+
+<p>
+	The <code>try_lock</code> function now returns a <code>Result</code> instead of an <code>Option</code>.
+	This is something I've been thinking about for a while now, and the fact that <code>Poisonable</code>
+	now exists makes an even more compelling argument for using <code>Result</code>. If something
+	is already locked, then you can have the key back without having to call <code>ThreadKey::get</code>.
+</p>
+
+<p>
+	I've kinda shown this already in some of the examples, but the <code>RawLock</code> trait methods have
+	been renamed. For example, <code>RawLock::lock</code> is now <code>RawLock::raw_lock</code>.
+</p>
+
+<p>
+	Some of the reading APIs have been moved from <code>Lockable</code> to <code>Sharable</code>. The reason
+	they were in <code>Lockable</code> before was because I had an idea where you could mix sharables
+	with non-sharables in a lock collection, and then calling <code>read</code> would just get an exclusive
+	lock if there was no shared lock available for an entry. Eventually I decided this was a bad idea, but
+	I still had the <code>read_guard</code> method in <code>Lockable</code>. So now it's moved to
+	<code>Sharable</code>.
+</p>
+
+<p>
+	I mentioned this already in the introduction to HappyLock, but <code>ThreadKey</code> is now
+	<code>Sync</code>. This is possible for the same reason that the nightly <code>Exclusive</code>
+	type is <code>Sync</code>. A <code>&amp;ThreadKey</code> is completely useless, so no undefined
+	behavior can be caused because of it. This also allows guards which hold a key (i.e. <code>MutexGuard</code>)
+	to be <code>Sync</code>. They still can't be send because, among other things, dropping a
+	<code>ThreadKey</code> on the wrong thread can lead to having multiple <code>ThreadKey</code>s
+	on the same thread, making deadlock possible. The Rust standard library also doesn't implement
+	<code>Send</code> on its guard types, so I think this is acceptable.
+</p>
+
+<p>
+	I'm now using cargo-diet before I publish HappyLock, so examples are no longer included when you
+	download it.
+</p>
+
+<p>
+	The <code>ThreadKey</code> now uses a <code>Cell&lt;bool></code> instead of an <code>AtomicBool</code>
+	when deciding if you can get a key or not. It's a thread-local variable, so there was no
+	synchronization needed in order to access the value.
+</p>
+
+<p>
+	Speaking of which, I've removed the <code>thread-local</code> crate as a dependency and learned
+	enough to just use the standard library's <code>thread_local</code> macro. It's more efficient
+	anyway. Also, now that <code>LazyCell</code> is in the standard library, I've dropped the
+	<code>once_cell</code> dependency. But this does increase the MSRV substantially.
+</p>
+
+<p>
+	The guard and ref types now implement more traits like <code>Eq</code>, <code>Ord</code> and
+	<code>Hash</code>. This would be a breaking change in the standard library, but this is already
+	a breaking change here.
+</p>
+
+<p>
+	I've been using <code>cargo-mutants</code> to help me write better unit tests. This helped me
+	catch one bug before it was even released. Although, I did still find a bug, so it's not perfect.
+	HappyLock is in this weird state where it's being used and I'm scared of obvious bugs, but it's
+	not used enough to the point where obvious bugs are immediately found and fixed. I should
+	probably start using <code>tarpaulin</code> as well.
+</p>
+
+<h2>The Future</h2>
+
+<p>
+	I'm still deciding what my next course of action will be for this crate. I should write more tests
+	for it before I do another big release. The documentation examples could definitely be improved. Some
+	of my plans for the future have changed. I still would like to try copying the standard library
+	lock implementations at some point. I no longer think compile-time duplicate checks are possible
+	due to the lack of const trait methods in Rust. LockCell and ReadOnlyLockCollection are still just
+	ideas in the back of my mind. But I have acquired a few new ideas since last year.
+</p>
+
+<h3>Once</h3>
+
+<p>
+	It is definitely possible to make a deadlock-free <code>Once</code>, by having <code>call_once</code>
+	require a <code>ThreadKey</code>. I tried somehow fitting it into a <code>LockCollection</code>, but
+	I don't think that's practical, and I don't know why you would ever want more than a single
+	<code>Once</code> at a time. Although, I can see a point to using a <code>Mutex</code> inside of a
+	<code>call_once</code>, so I can also provide a way to pass in a <code>RawLock + Lockable</code> with it.
+</p>
+
+<p>
+	I'm still not sure if I want to include <code>Condvar</code>. It is useful but I don't think I would
+	be able to prevent it from deadlocking. I'll keep it in mind though.
+</p>
+
+<h3>Async</h3>
+
+<p>
+	During my time at RustConf, I realized that the biggest barrier to HappyLock adoption is probably
+	the inability to use it with async Rust. The problem is that you can have multiple tasks running on
+	the same thread, so <code>ThreadKey::get()</code> will return <code>None</code> very often. But a
+	good solution to this would be to have <code>TaskKey</code>s instead, which would only be useful
+	on the async mutexes. But this is something that the async runtime would need to be able to provide.
+	But if the <code>spawn</code> function gave you a <code>TaskKey</code>, then there would be no need
+	to even call a <code>get</code> function for it. The biggest problem here would be that you can't use
+	a blocking lock, because if it's already locked in a task that runs on the same thread, then this
+	would cause a deadlock.
+</p>
+
+<h3>Expanding Cyclic Wait</h3>
+
+<p>
+	A reddit comment gave me an idea on how to pursue this. I don't think I'll go into too much detail
+	right now, but it would involve a <code>IntoLockIterator</code> trait, several new types, adding
+	a <code>&ThreadKey</code> to all of the ref guard types, and quite a bit of type-state analysis.
+	I'll probably talk about this over at the Miami Rust User Group, so join us online if you're
+	interested. I think we can turn HappyLock from a library that primarily prevents partial allocation
+	and prevents cyclic wait as an optimization, to a library that is used to prevent cyclic wait
+	and uses remnants of total allocation to prevent you from screwing up.
+</p>
+
+</article>
+
+<hr/>
+
+<footer>
+	<ol>
+		<li id="footnote-1">
+			I'm not quite sure what software engineering majors do at RIT. I imagine them all sitting
+			around a table, and saying words like "agile" and "scrum" with no context. I took Computer
+			Science. <a class="return" href="#af-1">return</a>
+		</li>
+	</ol>
+</footer>
+
+</body>