Explore how Rust eliminates data races and tackles deadlocks

Nov 24, 2024

Data races

It is known that Rust compiler makes data races impossible in safe Rust. Rust compiler uses ownership model together with Send and Sync trait for that. The code below won't compile because it has data race - I keep mutating xs vector in the main thread while another thread wants to read from it, all of that without synchronization:

Compiler provides useful errors explaining what are the issues:

error[E0373]: closure may outlive the current function, but it borrows `xs`, which is owned by the current function
 --> src/main.rs:5:32
error[E0502]: cannot borrow `xs` as mutable because it is also borrowed as immutable
  --> src/main.rs:10:5

Rust doc on std::thread::spawn has a great explanation regarding the first error, thread lifetime conflict

The 'static constraint means that the closure and its return value must have a lifetime of the whole program execution. The reason for this is that threads can outlive the lifetime they have been created in. Indeed if the thread, and by extension its return value, can outlive their caller, we need to make sure that they will be valid afterwards, and since we can’t know when it will return we need to have them valid as long as possible, that is until the end of the program, hence the 'static lifetime.

The second error is related to simultaneous borrowing. We also cannot have a mutable reference while we have an immutable one to the same value (check References and Borrowing if this is not clear)
A modified version that makes Rust compiler happy

You will get similar output to the below

Thread { id: ThreadId(2), name: None, .. }: [1, 11]
Thread { id: ThreadId(1), name: Some("main"), .. }: [1, 11, 42]

In most of other languages this kind of bugs can go unnoticed (especially if you do not use linters, thread-sanitizers, race condition detectors)

Deadlocks

What is a deadlock? A deadlock is a situation when two or more processes/threads stop making progress indefinitely because they are all waiting for each other to do something. Can we get a deadlock in Rust? Yes, we can! And here are the steps:

Thread T1 acquires mutex m1
Thread T2 acquires mutex m2
Thread T1 tries to acquire mutex m2 and gets blocked forever
Thread T2 tries to acquire mutex m1 and gets blocked forever

Let's write a typical bank account transferring implementation that is prone to the deadlock (code is for educational purposes only without proper checks) . Rust code compiles, it does not use any unsafe block and it hangs forever because of a deadlock

And the main function:

The run of that code never completes and outputs the following:

Started thread T1
Thread { id: ThreadId(2), name: Some("T1"), .. } Started
Thread { id: ThreadId(2), name: Some("T1"), .. } Acquiring mutex `from`: Mutex { data: BankAccount { id: "A", balance: 1000 }, poisoned: false, .. }
Thread { id: ThreadId(2), name: Some("T1"), .. } Acquired mutex `from`: BankAccount { id: "A", balance: 1000 }
Thread { id: ThreadId(3), name: Some("T2"), .. } Started
Thread { id: ThreadId(3), name: Some("T2"), .. } Acquiring mutex `from`: Mutex { data: BankAccount { id: "B", balance: 2000 }, poisoned: false, .. }
Thread { id: ThreadId(3), name: Some("T2"), .. } Acquired mutex `from`: BankAccount { id: "B", balance: 2000 }
Started thread T2
Thread { id: ThreadId(2), name: Some("T1"), .. } Acquiring mutex `to`: Mutex { data: <locked>, poisoned: false, .. }
Thread { id: ThreadId(3), name: Some("T2"), .. } Acquiring mutex `to`: Mutex { data: <locked>, poisoned: false, .. }

Fix deadlock by removing circular wait

The deadlock problem isn't something new in computer science. Coffman conditions defines four necessary and sufficient conditions for deadlock:

Mutual Exclusion
Circular Wait
Hold and Wait
No pre-emption

If you break any of them, you cannot have deadlock! In our case if we can break Circular Wait, we can get rid of a deadlock. How can we do that? By making sure the locks are taken in a specific order, e.g. to put an ordering on the locks that need to be acquired simultaneously, and ensuring that all code acquires the locks in that order.

We can use the addresses of mutexes to enforce consistent locking order (mutex cannot be moved to another location in memory!). Below is the fixed version of transfer method

The full code produced the result below:

Started thread T1
Thread { id: ThreadId(2), name: Some("T1"), .. } Started
Thread { id: ThreadId(2), name: Some("T1"), .. } Acquiring mutex `first`: Mutex { data: BankAccount { id: "A", balance: 1000 }, poisoned: false, .. }
Thread { id: ThreadId(2), name: Some("T1"), .. } Acquired mutex `first`: BankAccount { id: "A", balance: 1000 }
Started thread T2
Thread { id: ThreadId(3), name: Some("T2"), .. } Started
Thread { id: ThreadId(3), name: Some("T2"), .. } Acquiring mutex `first`: Mutex { data: <locked>, poisoned: false, .. }
Thread { id: ThreadId(2), name: Some("T1"), .. } Acquiring mutex `second`: Mutex { data: BankAccount { id: "B", balance: 2000 }, poisoned: false, .. }
Thread { id: ThreadId(2), name: Some("T1"), .. } Acquired mutex `second`: BankAccount { id: "B", balance: 2000 }
Thread { id: ThreadId(3), name: Some("T2"), .. } Acquired mutex `first`: BankAccount { id: "A", balance: 900 }
Thread { id: ThreadId(3), name: Some("T2"), .. } Acquiring mutex `second`: Mutex { data: BankAccount { id: "B", balance: 2100 }, poisoned: false, .. }
Thread { id: ThreadId(3), name: Some("T2"), .. } Acquired mutex `second`: BankAccount { id: "B", balance: 2100 }
Result:
m1: Mutex { data: BankAccount { id: "A", balance: 1200 }, poisoned: false, .. }
m2: Mutex { data: BankAccount { id: "B", balance: 1800 }, poisoned: false, .. }

Fix deadlock using Rust's rich type system

Now is an interesting part, we can use Rust type system to enforce correct order of mutexes. There are multiple implementations available:

ordered-locks
lock-ordering
lock_order in Fuchsia (docs | source), details can be found in the talk Safety in an Unsafe World Rust Conf 2024 by Joshua Liebow-Feeser (@joshlf)

I'm going to use lock_order to let compiler help with deadlocks:

transfer method now looks like

And main function

It produced the output

Started thread T1
Thread { id: ThreadId(2), name: Some("T1"), .. } Started
Thread { id: ThreadId(2), name: Some("T1"), .. } Acquiring mutex for LockFrom
Thread { id: ThreadId(2), name: Some("T1"), .. } Acquired mutex for LockFrom: BankAccount { id: "A", balance: 1000 }
Thread { id: ThreadId(2), name: Some("T1"), .. } Acquiring mutex for LockTo
Thread { id: ThreadId(2), name: Some("T1"), .. } Acquired mutex for LockTo: BankAccount { id: "B", balance: 2000 }
Started thread T2
Thread { id: ThreadId(3), name: Some("T2"), .. } Started
Result:
from: Mutex { data: BankAccount { id: "A", balance: 1200 }, poisoned: false, .. }
to: Mutex { data: BankAccount { id: "B", balance: 1800 }, poisoned: false, .. }

If I try to change the order of locks in thread T2:

Compiler gets unhappy:

error[E0277]: the trait bound `LockFrom: LockAfter<LockTo>` is not satisfied
   --> examples\src\bank_transfer_compile_time.rs:92:34
    |
92  |             let mut b = locked_a.lock::<LockFrom>();
    |                                  ^^^^ the trait `LockAfter<LockTo>` is not implemented for `LockFrom`
    |
    = help: the trait `LockAfter<LockTo>` is not implemented for `LockFrom`
            but trait `LockAfter<Unlocked>` is implemented for it
    = help: for that trait implementation, expected `Unlocked`, found `LockTo`
    = note: required for `LockTo` to implement `LockBefore<LockFrom>`
note: required by a bound in `Locked::<T, L>::lock`
   --> E:\repos\github\REASY\threading-playground-rs\lock-order\src\lib.rs:303:12
    |
300 |     pub fn lock<M>(&mut self) -> <T::Target as LockFor<M>>::Guard<'_>
    |            ---- required by a bound in this associated function
...
303 |         L: LockBefore<M>,
    |            ^^^^^^^^^^^^^ required by this bound in `Locked::<T, L>::lock`

The error isn't super easy to understand, but with some experience you can get used to it (and there is a way to improve custom compiler errors in Rust). It is really cool that Rust type system can help prevent so many bugs, we just need to have a way to encode it into types! If you're interested in this topic, I suggest more readings: The Typestate Pattern in Rust, Static Guarantees

Art’s Substack

Discussion about this post