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
53
54
55
56
57
58
59
60
//! Deadlock-freedom model for the transaction's lock acquisition step.
//!
//! `Tx::commit` sorts its participants by `collection_id` and each participant's
//! shards ascending (`txn/mod.rs`), then locks in that order. This models the
//! sort plus the acquisition; loom explores the interleavings.
//!
//! Run with: cargo test -p armdb --features loom --test loom_multi_tx --release
#![cfg(feature = "loom")]
use loom::sync::{Arc, Mutex};
use loom::thread;
/// Lock a set of `(collection_id, shard_id)` mutexes in canonical order — the
/// commit path's step 2, with the sort already applied by the caller.
fn lock_in_canonical_order(locks: &[Arc<Mutex<u32>>], plan: &[usize]) {
debug_assert!(plan.windows(2).all(|w| w[0] < w[1]), "plan must be sorted");
let mut held = Vec::new();
for &i in plan {
held.push(locks[i].lock().unwrap());
}
for g in held.iter_mut() {
**g += 1;
}
// Guards drop in reverse — the LIFO release `ShardGuards` performs.
}
#[test]
fn no_deadlock_opposite_argument_order() {
loom::model(|| {
let a = Arc::new(Mutex::new(0u32));
let b = Arc::new(Mutex::new(0u32));
// tx1 names (A, B); tx2 names (B, A). Both sort to [A, B].
let locks1 = [a.clone(), b.clone()];
let t1 = thread::spawn(move || lock_in_canonical_order(&locks1, &[0, 1]));
let locks2 = [a.clone(), b.clone()];
let t2 = thread::spawn(move || lock_in_canonical_order(&locks2, &[0, 1]));
t1.join().unwrap();
t2.join().unwrap();
});
}
#[test]
fn no_deadlock_overlapping_participant_sets() {
loom::model(|| {
// Three shards across two collections; tx1 takes {0, 2}, tx2 takes {1, 2}.
// They overlap on 2 and differ elsewhere — the shape a builder API makes
// routine and a fixed two-argument API could not express.
let locks: Vec<Arc<Mutex<u32>>> = (0..3).map(|_| Arc::new(Mutex::new(0u32))).collect();
let l1 = locks.clone();
let t1 = thread::spawn(move || lock_in_canonical_order(&l1, &[0, 2]));
let l2 = locks.clone();
let t2 = thread::spawn(move || lock_in_canonical_order(&l2, &[1, 2]));
t1.join().unwrap();
t2.join().unwrap();
});
}