diff options
Diffstat (limited to 'src/blog/how-happylock-works.kuht')
| -rwxr-xr-x | src/blog/how-happylock-works.kuht | 767 |
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<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> |