<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<T></code> type, but Rust already has <code>&T</code> and
<code>Arc<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 = &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 = &s;
let r2 = &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<*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>&mut ThreadKey</code>, must be given.
</p>
<pre>
pub fn lock<'s, 'k: 's, Key: Keyable>(&'s self, key: Key) -> MutexGuard<'_, '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>& 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<T></code>,
<code>(A, B)</code>, and <code>(Vec<A>, Vec<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<'a>;
unsafe fn lock<'a>(&self) -> Self::Guard<'a>;
unsafe fn try_lock<'a>(&self) -> Option<Self::Guard<'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(&self) -> Vec<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<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<L: Lockable> LockCollection<L> {
pub fn try_new(data: L) -> Option<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(&self);
unsafe fn try_lock(&self) -> bool;
unsafe fn unlock(&self);
}
unsafe trait Lockable {
type Guard<'g>;
fn get_locks<'a>(&'a self, &mut Vec<&'a dyn Lock>);
unsafe fn guard<'g>(&'g self) -> Self::Guard<'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<L> {
data: L,
locks: Vec<&'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<'a, L> {
data: &'a L,
locks: Vec<&'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<L> {
data: *const UnsafeCell<L>,
locks: Vec<&'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<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<'a, T(&'a RwLock<T>);
struct WriteLock<'a, T(&'a RwLock<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(&self);
unsafe fn try_read(&self) -> bool;
unsafe fn unlock_read(&self);
}
unsafe trait Lockable {
// ...
type ReadGuard<'g>;
unsafe fn read_guard<'g>(&'g self) -> Self::ReadGuard<'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<Vec<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<i32>;
let b: LockCell<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<<wbr/>RetryingLockCollection<<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>
|
