1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//! Deadlock-freedom model for the cross-collection lock scheduler.
//!
//! Run with: cargo test -p armdb --features loom --test loom_multi_tx --release
#![cfg(feature = "loom")]
use loom::sync::{Arc, Mutex};
use loom::thread;
/// Minimal stand-in for the scheduler's acquisition step: lock a set of
/// (collection_id, shard_id) mutexes in global canonical order. This models
/// exactly the ordering rule in Db::atomic2 (plan.sort_unstable()).
fn lock_in_canonical_order(locks: &[(usize, Arc<Mutex<u32>>)], plan: &mut [usize]) {
// plan = indices into `locks`, already sorted by the caller's (cid, shard).
let mut held = Vec::new();
for &i in plan.iter() {
held.push(locks[i].1.lock().unwrap());
}
// critical section: touch every held lock
for g in held.iter_mut() {
**g += 1;
}
// guards drop here in reverse — releases all locks
}
#[test]
fn no_deadlock_opposite_argument_order() {
loom::model(|| {
// Two collections A(id=0) and B(id=1), one shard each → two mutexes.
let a = Arc::new(Mutex::new(0u32));
let b = Arc::new(Mutex::new(0u32));
// Thread 1: atomic2(A, B) → canonical plan [A, B] = indices [0, 1].
let (a1, b1) = (a.clone(), b.clone());
let t1 = thread::spawn(move || {
let locks = [(0usize, a1), (1usize, b1)];
let mut plan = vec![0, 1]; // sorted by (cid, shard)
lock_in_canonical_order(&locks, &mut plan);
});
// Thread 2: atomic2(B, A) → but the scheduler re-sorts to canonical plan
// [A, B] = indices [0, 1] as well. Opposite ARGUMENT order, SAME lock order.
let (a2, b2) = (a.clone(), b.clone());
let t2 = thread::spawn(move || {
let locks = [(0usize, a2), (1usize, b2)];
let mut plan = vec![0, 1]; // sorting (cid, shard) gives the same order
lock_in_canonical_order(&locks, &mut plan);
});
t1.join().unwrap();
t2.join().unwrap();
});
}