First commit

1 files changed, 767 insertions, 0 deletions

diff --git a/src/blog/how-happylock-works.kuht b/src/blog/how-happylock-works.kuht
new file mode 100755
index 0000000..c1cf631
--- /dev/null
+++ b/src/blog/how-happylock-works.kuht
@@ -0,0 +1,767 @@
+<import "base.kuht" as "base" />
+
+<head>
+	<title>How HappyLock Works</title>
+	<meta name="description" content="Recently, I released version 0.3 of a Rust library which prevents deadlocks at compile-time. I want to explain what I changed, and why it works" />
+</head>
+
+<body>
+
+<article>
+
+<h1>How HappyLock Works</h1>
+
+<p>
+	Recently, I released version 0.3 of my <a href="https://www.lib.rs/happylock">HappyLock</a> crate
+	on crates.io. In this blog post, I wanted to explain what I changed, and why it works.
+</p>
+
+<h2>Background</h2>
+
+<p>
+	There are four conditions necessary for a deadlock to occur. You only need to prevent one of them
+	in order to prevent all deadlocks:
+</p>
+
+<ol>
+	<li>Mutual exclusion</li>
+	<li>Non-preemptive allocation</li>
+	<li>Circular wait</li>
+	<li>Partial allocation</li>
+</ol>
+
+<p>Let's go through each one, and see what we can do.</p>
+
+<h3>Mutual exclusion</h3>
+
+<p>
+	This doesn't make all that much sense to prevent. We could provide some sort of
+	<code>Readonly&lt;T></code> type, but Rust already has <code>&amp;T</code> and
+	<code>Arc&lt;T></code>. So this wouldn't be very useful.
+</p>
+
+<h3>Non-preemptive allocation</h3>
+
+<p>
+	Preventing this would mean that the language can decide to take away your access to a piece of
+	data at any time. Not only would this be incredibly difficult to pull off, it would also just
+	annoying for the programmer to deal with. Something like this would need to happen:
+</p>
+
+<pre>
+let mutex = Mutex::new(5);
+let mut_ref = &amp;mutex;
+let th = thread::spawn(|| {
+	let number = mut_ref.lock();
+	*number = 6;
+});
+
+let number = mut_ref.lock();
+th.join(); // preempts the lock on mut_ref
+println!("{}", number); // oops, we can't use number anymore
+</pre>
+
+<p>
+	We could have some sort of <code>LockCell</code> type, which releases the lock immediately after
+	performing some action, but there are often times where you need to make sure nothing else can
+	mutate the value for a section of code. So this won't always work.
+</p>
+
+<h3>Circular wait</h3>
+
+<p>
+	From what I can tell, most attempts to prevent deadlock go through this route. The idea is what
+	every lock must be acquired <i>in the same order</i>. So if you lock <code>l1</code> and then
+	<code>l2</code> on one thread, then you can't do it in the opposite order on the other thread.
+	This is an interesting approach, but there's no way to enforce it in the language. Some people
+	have resorted to using macros for this, such as in the recently published
+	<a href="https://www.lib.rs/deadlocker">deadlocker crate</a> (which is a very confusing name).
+	But an attempt to make this happen at compile-time won't be dynamic enough for the general case.
+</p>
+
+<p>Keep an eye on this one, because we will make use of it later.</p>
+
+<h3>Partial allocation</h3>
+
+<p>
+	This is the hero we've been waiting for. To prevent this, we need to enforce total allocation. So if
+	you want to lock a new mutex, you must first release the locks you've already acquired, and then
+	acquire a new set of locks. Preventing this is possible in Rust, and less possible in languages that
+	don't have a borrow checker. Let me explain how we'll use the borrow checker.
+</p>
+
+<h2>Exploration</h2>
+
+<p>
+	Say we were making mutexes for an operating system. How would we enforce total allocation? We could
+	simply give an error if someone acquires a new set of locks without releasing the already acquired
+	locks. It'd also mean we'd have to check for an error every time we acquire a new set of locks.
+</p>
+
+<pre>
+mutex_t m1 = new_mutex();
+mutex_t m2 = new_mutex();
+
+mutex_t mutices[] = { m1, m2 };
+if (lock_mutexes(mutices, 2)) {
+	// oh noes!
+}
+
+// now we can use the data
+</pre>
+
+<p>But we're not C. We have technology! And our technology is the borrow checker.</p>
+
+<h3>Borrow Checker Rules</h3>
+
+<p>For those of you who don't know, here's a quick rundown of the borrow checker rules:</p>
+
+<ol>
+	<li>A value may not be moved while references to it exist.</li>
+	<li>Only one mutable reference to a value may exist at a time.</li>
+	<li>A mutable reference and immutable references, must not exist at the same time.</li>
+</ol>
+
+<p>As a quick example of these rules:</p>
+
+<pre>
+let s = String::new("Hello, world!");
+let r1 = &amp;s;
+let r2 = &amp;s; // this is allowed because these references aren't mutable
+let mr = &mut s; // illegal: rule #3
+drop(s); // also illegal: rule #1
+println!("{r1} {r2}");
+</pre>
+
+<h2>A Naive implementation</h2>
+
+<p>
+	So here's the plan: We'll make a new type called <code>ThreadKey</code>. This type cannot be
+	cloned, copied, sent to another thread, or mutably referenced from another thread. The Rust type
+	system is able to enforce all of those things.
+</p>
+
+<pre>
+// no traits are derived, especially not Clone or Copy
+pub struct ThreadKey {
+	phantom: PhantomData&lt;*const ()>, // !Send and !Sync
+}
+</pre>
+
+<p>
+	Then, we can require that when locking a mutex (or a read-write lock), a <code>ThreadKey</code>,
+	or a <code>&amp;mut ThreadKey</code>, must be given.
+</p>
+
+<pre>
+pub fn lock&lt;'s, 'k: 's, Key: Keyable>(&'s self, key: Key) -> MutexGuard&lt;'_, 'k, T, Key, R>
+</pre>
+
+<p>
+	Wow! That's a lot of lifetimes and generics. We'll worry about those later. For now, let's show
+	how this works.
+</p>
+
+<pre>
+use happylock::{ThreadKey, Mutex};
+
+fn main() {
+	// each thread can only have one thread key
+	// the call to unwrap panics if this thread already got its key
+	// 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);
+
+	// we no longer have the thread key, so we can't lock anything else anymore
+
+	println!("{}", *guard);
+}
+</pre>
+
+<p>
+	I recently learned that I wasn't the only person who thought of this. Over a year ago, Adrian
+	Taylor posted on Medium,
+	<a href="https://medium.com/@adetaylor/can-the-rust-type-system-prevent-deadlocks-9ae6e4123037">
+		Can the Rust type system prevent deadlocks?</a>.
+	I was completely unaware of this when I published the crate, despite my search for other
+	implementations of the idea. He also worked on getting inner mutexes to work, which is currently
+	impossible in HappyLock. He didn't attempt to do something more obvious though, which is locking
+	more than one mutex at a time. He also never considered the possibility of using a
+	<code>&amp; mut MutexPermissionToken</code> to make the code more ergonomic.
+</p>
+
+<p>Speaking of which, how do we lock more than one mutex at a time?</p>
+
+<h3>Lock Collections</h3>
+
+<p>
+	It's actually quite simply, we just lock a collection of things. We can have a type, called
+	<code>LockCollection</code>, which takes a collection of locks, and locks them all at the same time.
+	Then, it'll return a <code>LockGuard</code> for the collection.
+</p>
+
+<p>
+	There are different collections we could try to lock, including <code>Vec&lt;T></code>,
+	<code>(A, B)</code>, and <code>(Vec&lt;A>, Vec&lt;B>)</code>, so this'll have to be generic. To
+	enable this, we'll create a trait called <code>Lockable</code>.
+</p>
+
+<p>This isn't the current implementation in HappyLock, but here's a proof-of-concept:</p>
+
+<pre>
+unsafe trait Lockable {
+	type Guard&lt;'a>;
+
+	unsafe fn lock&lt;'a>(&amp;self) -> Self::Guard&lt;'a>;
+
+	unsafe fn try_lock&lt;'a>(&amp;self) -> Option&lt;Self::Guard&lt;'a>>;
+}
+</pre>
+
+<p>Then, we just need to implement on every collection that could hold a lock.</p>
+
+<pre>
+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;
+}
+</pre>
+
+<p>That seems to work pretty well.</p>
+
+<h3>Duplicate Locks</h3>
+
+<p>Let's try something:</p>
+
+<pre>
+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);
+}
+</pre>
+
+<p>
+	The problem is that we passed the same lock in twice. That'll be a problem if we require it to be
+	locked twice. The good news is, this code doesn't compile, because <code>LockCollection::new</code>
+	actually requires a different trait that I haven't mentioned.
+</p>
+
+<pre>
+// not implemented for &impl Lockable
+// ergo: the values within are guaranteed to be unique
+unsafe trait OwnedLockable: Lockable {}
+</pre>
+
+<p>
+	Let me elaborate on this. If the value is owned, then there's no way to pass it twice into the same
+	collection. The same is true for mutable references. So we can safely lock an owned lock without
+	checking for duplicates.
+</p>
+
+<p>
+	But sometimes, it's useful to lock a referenced mutex. For these, we'll need a runtime check for
+	duplicates. So we'll need to add another method to our <code>Lockable</code> trait.
+</p>
+
+<pre>
+unsafe trait Lockable {
+	// ... snip ...
+
+	fn get_ptrs(&amp;self) -> Vec&lt;usize>;
+}
+</pre>
+
+<p>
+	Then we can check for duplicate pointers within a collection. My first implementation of that check
+	was a brute-force O(n²) check. When I posted about this on Reddit, people were quick to point out
+	that this could be made O(nlogn) by sorting the pointers, then checking if the same pointer appeared
+	twice in a row.
+</p>
+
+<pre>
+fn contains_duplicates&lt;L: Lockable>(data: L) -> bool {
+	let mut pointers = data.get_ptrs();
+	pointers.sort_unstable();
+	pointers.windows(2).any(|w| w[0] == w[1])
+}
+</pre>
+
+<p>Of course, you could make this an O(n) check by using a <code>HashSet</code> too.</p>
+
+<p>Now we need a new constructor for <code>LockCollection</code>.</p>
+
+<pre>
+impl&lt;L: Lockable> LockCollection&lt;L> {
+	pub fn try_new(data: L) -> Option&lt;Self> {
+		let ptrs = data.get_ptrs();
+		if contains_duplicates(&ptrs) {
+			return None;
+		}
+
+		Some(Self { data })
+	}
+}
+</pre>
+
+<h2>The Actual Implementation</h2>
+
+<p>
+	Although we have now successfully prevented deadlocks,
+	<a href="https://en.wikipedia.org/wiki/Deadlock#Livelock">livelocking</a> can still be an issue.
+</p>
+
+<p>
+	The first implementation of <code>LockCollection</code> would try to lock everything in order. If
+	one of the locks blocked, then it would release everything it had and try again. It would keep
+	retrying until it successfully locked everything in a row. This resulted in a lot of wasted work. It
+	also made the <code>LockCollection</code> start to resemble a spinlock. This also made the
+	collection prone to livelocking.
+</p>
+
+<p>
+	Imagine this scenario with two threads trying to lock a set of mutexes, but in a different order:
+</p>
+
+<ol>
+	<li>Thread 1 locks mutex 1</li>
+	<li>Thread 2 locks mutex 2</li>
+	<li>Thread 1 tries to lock mutex 2 and fails</li>
+	<li>Thread 2 tries to lock mutex 1 and fails</li>
+	<li>Thread 1 releases mutex 1</li>
+	<li>Thread 2 releases mutex 2</li>
+	<li>Repeat</li>
+</ol>
+
+<p>
+	In practice, this loop would probably end eventually, but it'd be nice if we could prevent it
+	altogether. You could avoid this by locking everything in the same order. But if we could do that,
+	then we would've prevented cyclic wait from before, which would have avoided this whole problem.
+</p>
+
+<h3>Cyclic wait</h3>
+
+<p>
+	Remember when I said we would make use of cyclic wait later? This is where we'll do this. If you
+	recall from earlier, we already sorted the mutex pointers by their memory address. What if we locked
+	them in that order? This was suggested by many people on Reddit, but it took a while to work out
+	exactly how to do this. I can't sort a tuple. So we'll need to lock them in a different order than
+	the one they're returned in. This will require a large change to the existing <code>Lockable</code>
+	trait. Let's see what we can do.
+</p>
+
+<pre>
+unsafe trait Lock {
+	unsafe fn lock(&amp;self);
+	unsafe fn try_lock(&amp;self) -> bool;
+	unsafe fn unlock(&amp;self);
+}
+
+unsafe trait Lockable {
+	type Guard&lt;'g>;
+	fn get_locks&lt;'a>(&amp;'a self, &amp;mut Vec&lt;&amp;'a dyn Lock>);
+	unsafe fn guard&lt;'g>(&amp;'g self) -> Self::Guard&lt;'g>;
+}
+</pre>
+
+<p>
+	<code>Lock</code> is implemented on <code>Mutex</code> and <code>RwLock</code>. <code>Lockable</code>
+	is implemented on the same types as before. These traits are even more unsafe than they were before,
+	now that they can obtain a guard without locking it first. So, we'll just need to be very careful.
+</p>
+
+<p>Now let's try making our new <code>LockCollection</code></p>
+
+<pre>
+struct LockCollection&lt;L> {
+	data: L,
+	locks: Vec&lt;&amp;'self.data dyn Lock>
+	// wait, this is a self-referential struct
+}
+</pre>
+
+<p>
+	Ooh, boy. This is gonna be a problem. We could box the data, but sometimes we don't want to pay the
+	price of memory allocation. We could try using a reference, but then we have an extra lifetime to
+	deal with. It's also sometimes useful to have an owned lock collection. How are we going to do this
+	without creating four lock collection types that do mostly the same thing?
+</p>
+
+<h3>We'll just create four Lock Collection Types that do mostly the same thing</h3>
+
+<p>
+	I'll cover each of the four types, but if you're looking for a sensible default, there's a type alias
+	so that <code>LockCollection</code> points to <code>BoxedLockCollection</code>. It's slower and
+	doesn't allow you to mutate the underlying collection (yet), but it works for most use cases.
+</p>
+
+<p>
+	I'm pretty sure when this gets posted to Reddit, someone will tell me I could've avoided this
+	somehow.
+</p>
+
+<h4><code>RefLockCollection</code></h4>
+
+<pre>
+pub struct RefLockCollection&lt;'a, L> {
+	data: &amp;'a L,
+	locks: Vec&lt;&amp;'a dyn RawLock>,
+}
+</pre>
+
+<p>
+	It needs to sort the locks by address. Yes, that applies even if the collection is owned. Otherwise
+	the locks could be acquired in a different order. We're no longer releasing the locks when we can't
+	acquire them all at once, so they need to be acquired in exactly that order. But it avoids one memory
+	allocation.
+</p>
+
+<h4><code>BoxedLockCollection</code></h4>
+
+<pre>
+pub struct BoxedLockCollection&lt;L> {
+	data: *const UnsafeCell&lt;L>,
+	locks: Vec&lt;&amp;'static dyn RawLock>,
+}
+</pre>
+
+<p>
+	This is similar to <code>RefLockCollection</code>, but it allocates more memory. You may notice that
+	there's no <code>Box</code> in this structure, despite the name. That's because <code>Box</code>
+	needs to be a unique pointer. But because of the references in <code>locks</code>, it's not unique.
+	It's <code>const</code> because of the existing references to the collection, meaning mutating the
+	underlying collection would cause undefined behavior, especially if it means the locks move (such
+	as when a <code>Vec</code> reallocates). It's a raw pointer, because deallocating the data requires
+	a mutable pointer, and creating a mutable pointer from an immutable reference is undefined behavior.
+	The <code>UnsafeCell</code> is used for a similar reason.
+</p>
+
+<p>
+	This is actually the reason why this release is titled 0.3 and not 0.2. I released 0.2 and found
+	these soundness bugs, so I had to make a fix. This was a breaking change, because you can't mutate
+	the underlying collection anymore.
+</p>
+
+<h4><code>OwnedLockCollection</code></h4>
+
+<pre>
+pub struct OwnedLockCollection&lt;L> {
+	data: L,
+}
+</pre>
+
+<p>
+	Since both <code>RefLockCollection</code> and <code>BoxedLockCollection</code> require sorting the
+	locks, it'd be nice if we could sometimes avoid that for owned lock collections. If a set of locks is
+	in an <code>OwnedLockCollection</code>, then it really cannot be used anywhere else. That means as
+	long as references to a <code>OwnedLockCollection</code> always lock in the same order, then it'll
+	never deadlock. That's the only order these particular locks can be locked in. So, we don't bother
+	sorting and just lock them in the order they appear in for the collection.
+</p>
+
+<h4><code>RetryingLockCollection</code></h4>
+
+<p>
+	This is the collection that was used in Happylock 0.1. This does the releasing of all of the locks
+	thing. The upside of this collection is that it can contain references, and still not sort the
+	pointers. Duplicates are checked for by using a <code>HashSet</code>. Because of the lack of sorting,
+	it can be fast in the following case, from the docs:
+</p>
+
+<blockquote>
+	[...] when the first lock in the collection is always the first in any
+	collection, and the other locks in the collection are always locked after
+	that first lock is acquired. This means that as soon as it is locked, there
+	will be no need to unlock it later on subsequent lock attempts, because
+	they will always succeed.
+</blockquote>
+
+<h3>RwLocks</h3>
+
+<p>
+	It doesn't take a genius to realize that my lock collection API is not friendly to read-write locks.
+	In HappyLock 0.1, I had <code>ReadLock</code> and <code>WriteLock</code> wrappers for
+	<code>RwLock</code> to allow reads in collections.
+</p>
+
+<pre>
+struct ReadLock&lt;'a, T(&amp;'a RwLock&lt;T>);
+struct WriteLock&lt;'a, T(&amp;'a RwLock&lt;T>);
+</pre>
+
+<p>
+	This worked fine at the time, but I quickly realized that this would not work for an
+	<code>OwnedLockCollection</code>. To solve this problem, I made more changes to the
+	<code>Lockable</code> API.
+</p>
+
+<pre>
+unsafe trait Lock {
+	// ...
+	unsafe fn read(&amp;self);
+	unsafe fn try_read(&amp;self) -> bool;
+	unsafe fn unlock_read(&amp;self);
+}
+
+unsafe trait Lockable {
+	// ...
+	type ReadGuard&lt;'g>;
+	unsafe fn read_guard&lt;'g>(&amp;'g self) -> Self::ReadGuard&lt;'g>
+}
+
+// A NEW TRAIT
+unsafe trait Sharable: Lockable {}
+</pre>
+
+<p>
+	The <code>Sharable</code> trait is implemented on collections that only contain readable locks.
+	All of the lock collection types then have functions for when their locks are all sharable. That
+	allows us to grant read-access in <code>OwnedLockCollection</code>s.
+</p>
+
+<p>After I was done with that, I updated the documentation and published the new version.</p>
+
+<h2>Performance</h2>
+
+<p>
+	<code>ThreadKey</code> is a zero-cost abstraction. It takes zero space at runtime. The only code is
+	checking to see if the key has already been acquired for a thread. That is a static,
+	lazily-initialized, thread local, boolean check and update, so it's fairly fast.
+</p>
+
+<p>
+	I used <code>lock_api</code> as backends for the <code>Mutex</code> and <code>RwLock</code> types.
+	By default, this library acts as a thin wrapper around <code>parking_lot</code>, so it will be
+	roughly the same speed as <code>parking_lot</code>. There's an optional feature that can be enabled
+	to use <code>spin</code> as well, and you can import your own raw locks if you wish. The standard
+	library locks cannot be used, because it's impossible to implement the <code>lock_api</code> traits
+	on them. If someone adds a <code>Mutex::force_unlock</code> function to the standard library, then I
+	can add that support, and I'll even make it the default. For now, we have to deal with the larger
+	binary size that's given by <code>parking_lot</code>.
+</p>
+
+<p>
+	The only place where performance could be an issue is in the lock collection types. The performance
+	qualities of each type have already been discussed. But to summarize, only the
+	<code>OwnedLockCollection</code> is zero-cost. Both <code>RefLockCollection</code> and
+	<code>BoxedLockCollection</code> allocate memory and sort the lock pointers, and sometimes they'll
+	even need to check for duplicates within the pointers. All of this work is done when the collection
+	is created though, so at least you don't need to worry about it after that. On the other hand, the
+	<code>RetryingLockCollection</code>, when locking, will waste time unlocking and relocking unless the
+	following condition is met:
+</p>
+
+<blockquote>
+	[...] when the first lock in the collection is always the first in any collection, and the other
+	locks in the collection are always locked after that first lock is acquired.
+</blockquote>
+
+<p><code>RetryingLockCollection</code> also checks for duplicates using a <code>HashSet</code>.</p>
+
+<p>In summary, it's pretty fast, but choose the correct lock collection constructor carefully.</p>
+
+<h2>Future Work</h2>
+
+<p>
+	This is summarized on the GitHub repo, but I'll try to go into more depth on my plans for the future
+	of this library.
+</p>
+
+<h3>Poisoning</h3>
+
+<p>
+	Personally, I'm not a big fan of mutex poisoning, but I can see why someone would want to use it. I
+	plan on adding it to Happylock soon, by having a <code>Poisonable</code> wrapper around
+	<code>Lock</code> types. And if I implement <code>Lock</code> on the lock collection types, then
+	it'll even be able to wrap those, which might be useful.
+</p>
+
+<h3>OS Locks</h3>
+
+<p>
+	I originally thought of this as being a must-have for the next version of HappyLock, but after trying
+	it for a bit, I decided to hold off on it. As I mentioned before, there is a binary size cost to
+	using <code>parking_lot</code>. We could save memory by using the locks that are built into the
+	operating system, which is what the standard library does. It would be very convenient if I could
+	just use the standard library as a backend for HappyLock.
+</p>
+
+<p>
+	Unfortunately, there's a reason why the standard library's locks do not implement
+	<code>lock_api</code>'s traits. There's just no way to unlock one of those mutexes without holding
+	onto the guard. If we were to put the guard inside of the mutex, and then drop it when unlocking,
+	that would make it impossible to share the lock across threads, since the guard isn't
+	<code>Send</code>.
+</p>
+
+<p>
+	There are raw mutexes used in the underlying implementation of the standard library, but those aren't
+	public. I've tried simply copying the part of the standard library that implements those traits, but
+	it relies on too much of the rest of the standard library. I don't want importing HappyLock to
+	require recompiling the entire standard library.
+</p>
+
+<p>
+	The next feasible solution, in my opinion, would be to make a new crate that uses the operating
+	system mutexes, and implements <code>lock_api</code> traits on them. I've already started doing this,
+	and it seems very possible. But don't expect it to properly support every platform that the standard
+	library supports.
+</p>
+
+<h3>Compile-Time Duplicate Checks</h3>
+
+<p>
+	The only way to make duplicate checks free is to run them at compile-time. I doubt I'd be able to
+	implement this using procedural macros (feel free to prove me wrong). But, as
+	<a href="https://github.com/pacak">pacak</a> keeps reminding me, it might be possible using const
+	functions with a <a href="https://en.wikipedia.org/wiki/Bloom_filter">Bloom filter</a>. I don't know
+	if const Rust is robust enough for this to be implemented yet, but I do want to give it a try. It
+	wouldn't work for lock collections which require sorting, but it might work for
+	<code>RetryingLockCollection</code>.
+</p>
+
+<h3>Expanding Cyclic Wait</h3>
+
+<p>
+	One other thing I'd like to explore is if there's anything more that can be done with cyclic wait.
+	I could imagine <code>LockCollection&lt;Vec&lt;L>> where L: OwnedLockable</code> having some
+	<code>lock_next</code> method, or maybe an iterator type that would allow you to only lock the first
+	few items as they are needed, rather than locking the entire collection at once. I'm not sure how
+	useful this would be though. I'm sure there are other ideas that I'm not thinking of too.
+</p>
+
+<h3>A <code>LockCell</code> type</h3>
+
+<p>
+	If you've seen the <code>Cell</code> type in Rust, then you know that it's a good zero-cost
+	abstraction that provides safe interior mutability. The downsides are that it cannot be shared
+	between threads and its limited API. But I think it would be neat to add some of its methods as
+	convenience methods for <code>Mutex</code> and <code>RwLock</code>, i.e:
+	<code>Mutex::lock_swap</code>. This would not remove the need for a <code>ThreadKey</code>, since
+	then you'd be able to call <code>lock_swap</code> on a thread that's already locked the mutex.
+</p>
+
+<p>
+	However, if we had methods like <code>Mutex::try_swap</code>, then there'd be no need. The mutex
+	wouldn't be able to block the current thread, and because the lock is released so quickly, it
+	wouldn't block any other threads either. No blocking, means no deadlock. I think the same would be
+	true for <code>try_clone</code> and <code>try_take</code>, but they're scarier since the
+	<code>Clone</code> and <code>Default</code> traits could try to lock the same mutex, resulting in a
+	deadlock. I don't know if it would be possible to access the <code>ThreadKey</code> safely in these
+	methods though. Either way, all of these methods would be fallible, so it's not going to be a
+	perfect solution.
+</p>
+
+<p>
+	But we could introduce a <code>LockCell</code> type, which would be the same as <code>Cell</code>,
+	but it safely implements <code>Sync</code> by using a mutex or rwlock internally. This would not
+	require <code>ThreadKey</code> at all, as long as all of the implemented methods don't lock the
+	<code>LockCell</code> a second time, which is probably impossible.
+</p>
+
+<p>
+	It is a little surprising that a type like this doesn't already exist in the standard library. That
+	might be because it would make race conditions very easy to trigger. Imagine checking to see if two
+	<code>LockCell</code> values were equal for an if-block, but once you get inside the if-block,
+	they're no longer equal. I'll have to think more about this.
+</p>
+
+<pre>
+let a: LockCell&lt;i32>;
+let b: LockCell&lt;i32>;
+
+if a == b {
+	// a and b are no longer equal
+}
+</pre>
+
+<h3>Readonly Lock Collections</h3>
+
+<p>
+	I originally had a different idea of what to do with the <code>Sharable</code> trait. We could avoid
+	checking for duplicates in a lock collection if we knew that the only thing we would do with them is
+	read. At the time, I thought that reading twice on the same thread will never cause a deadlock.
+	However, that's not true on every platform, because of contention. Luckily, the <code>lock_api</code>
+	developers thought ahead by designing a <code>RawRwLockRecursive</code> trait, which I can extend by
+	creating a <code>Recursive</code> subtrait of <code>Lockable</code>.
+</p>
+
+<p>
+	That's cool, but I don't really want to add three more lock collection types for this feature. So
+	maybe this could be a wrapper around the existing lock collection types, i.e.
+	<code>Readonly&lt;<wbr/>RetryingLockCollection&lt;<wbr/>L>></code>. I'd need to implement a
+	<code>LockCollection</code> trait that would have an associated unsafe constructor for creating the
+	collection without checking for duplicates. Then, creating that retrying lock collection would be
+	free (but locking it can still sometimes be expensive).
+</p>
+
+<p>
+	This doesn't only apply to <code>RwLock</code>. If there was a <code>ReentrantMutex</code> type, then
+	we could implement <code>Recursive</code> on that, and use that in a readonly lock collection as well.
+	For those of you who don't know, a <code>ReentrantMutex</code> can be locked several times on the same
+	thread, but not while it's being locked by a different thread. However, the guard can only access the
+	data immutably, because multiple mutable references to data on the same thread is still undefined
+	behavior. It's mostly intended for wrapping <code>Cell</code> or <code>RefCell</code>. Unfortunately,
+	<code>lock_api</code> doesn't have a trait for recursive mutexes. Instead it provides a struct
+	wrapper for <code>RawMutex</code>, called <code>RawReentrantMutex</code>. This is despite the fact
+	that Unix's pthread API already supports recursive mutexes. I might be able to sway the
+	<code>lock_api</code> developers to support this.
+</p>
+
+<h3>No Standard Library</h3>
+
+<p>
+	Doing this without the standard library would be very interesting. But currently, the
+	<code>Lockable</code> interface requires a <code>Vec</code> of pointers, so it might not be feasible.
+	The thread keys are stored in a thread local storage too, but I'll probably come up with some
+	<code>UnsafeKey</code> system to deal with that eventually, in order to support async runtimes.
+</p>
+
+<h3>Other Types from the Standard Library</h3>
+
+<p>
+	It would be fun to add <code>OnceLock</code> or <code>LazyLock</code>, but I don't think it's
+	necessary. I don't think anybody has ever accidentally deadlocked using those interfaces, if at all.
+	In the past I've also considered <code>Condvar</code> and <code>Barrier</code>, but that's trickier.
+	They're kind of the opposite of a mutex, so tricks that work for avoiding deadlocks here won't work
+	on them. I've also never used either of those types before, so I'm probably not the best person to
+	figure that out.
+</p>
+
+<h2>Conclusion</h2>
+
+<p>
+	This has been a very long nerd snipe. But I think this idea could become incredibly useful, which is
+	why I keep pushing for it. It'd be even better if it was a part of the standard libary to begin with,
+	but I'm aware that's not possible anymore.
+</p>
+
+<p>
+	The fact that this is possible makes me appreciate the borrow checker even more. People often think
+	of it as a limitation (myself included), but it solves so many problems that I'm surprised more
+	languages don't adopt it. Not only does it solve memory corruption, but also resource leaks, and now
+	deadlocks. You spend more time specifying your code, but less time debugging it.
+</p>
+
+<p>
+	There's still work that needs to be done (I haven't even begun async runtime support yet), but I hope
+	that as this library becomes more developed, there will be more projects which are immune this error.
+</p>
+
+</article>
+</body>