Struct WaitForGraph

Source

pub struct WaitForGraph { /* private fields */ }

Available on crate feature std only.

Expand description

A directed graph of which transactions are waiting for which.

An edge a -> b means transaction a is blocked waiting for a lock held by transaction b. The graph is a plain adjacency map; build it, then call detect_cycle or cycle_from to find a deadlock.

§Examples

use lock_db::{TxnId, WaitForGraph, VictimPolicy};

let mut g = WaitForGraph::new();
// T1 waits for T2, T2 waits for T1: a deadlock.
g.add_wait(TxnId::new(1), TxnId::new(2));
g.add_wait(TxnId::new(2), TxnId::new(1));

let cycle = g.detect_cycle().expect("a cycle exists");
assert_eq!(cycle.len(), 2);
assert_eq!(WaitForGraph::pick_victim(&cycle, VictimPolicy::Youngest), Some(TxnId::new(2)));

Implementations§

Source §

impl WaitForGraph

Source

pub fn new() -> Self

Creates an empty graph.

Source

pub fn add_wait(&mut self, waiter: TxnId, holder: TxnId)

Records that waiter is blocked waiting for a lock held by holder.

A self-edge (waiter == holder) is ignored: a transaction cannot deadlock against itself.

§Examples

use lock_db::{TxnId, WaitForGraph};

let mut g = WaitForGraph::new();
g.add_wait(TxnId::new(1), TxnId::new(2));
assert_eq!(g.waiter_count(), 1);
g.add_wait(TxnId::new(3), TxnId::new(3)); // self-edge ignored
assert_eq!(g.waiter_count(), 1);

Source

pub fn add_waits(&mut self, waiter: TxnId, holders: &[TxnId])

Records that waiter is blocked by every transaction in holders.

§Examples

use lock_db::{TxnId, WaitForGraph};

let mut g = WaitForGraph::new();
g.add_waits(TxnId::new(1), &[TxnId::new(2), TxnId::new(3)]);
// No cycle: 1 waits for 2 and 3, neither waits back.
assert!(g.detect_cycle().is_none());

Source

pub fn clear_waiter(&mut self, waiter: TxnId)

Removes every edge originating at waiter (it stopped waiting).

Source

pub fn remove_txn(&mut self, txn: TxnId)

Removes txn from the graph entirely — both its own waits and every edge pointing at it.

Source

pub fn is_empty(&self) -> bool

Returns true if no transaction is waiting.

Source

pub fn waiter_count(&self) -> usize

Returns the number of transactions that are waiting (have outgoing edges).

Source

pub fn detect_cycle(&self) -> Option<Vec<TxnId>>

Returns a cycle in the graph if one exists, or None.

The returned vector lists the transactions of one cycle in wait-for order. When several cycles exist, which one is returned is unspecified.

§Examples

use lock_db::{TxnId, WaitForGraph};

let mut g = WaitForGraph::new();
// A chain, no cycle.
g.add_wait(TxnId::new(1), TxnId::new(2));
g.add_wait(TxnId::new(2), TxnId::new(3));
assert!(g.detect_cycle().is_none());

// Close the loop.
g.add_wait(TxnId::new(3), TxnId::new(1));
assert_eq!(g.detect_cycle().map(|c| c.len()), Some(3));

Source

pub fn cycle_from(&self, start: TxnId) -> Option<Vec<TxnId>>

Returns a cycle reachable from start if one exists, or None.

Used for detection at the moment a new wait is added: the only cycle that can have just formed is one reachable from the transaction that added the edge.

§Examples

use lock_db::{TxnId, WaitForGraph};

let mut g = WaitForGraph::new();
g.add_wait(TxnId::new(1), TxnId::new(2));
g.add_wait(TxnId::new(2), TxnId::new(1));
assert!(g.cycle_from(TxnId::new(1)).is_some());
assert!(g.cycle_from(TxnId::new(9)).is_none()); // unknown txn

Source

pub fn pick_victim(cycle: &[TxnId], policy: VictimPolicy) -> Option<TxnId>

Chooses the transaction to abort from a deadlock cycle.

Returns None only for an empty slice. See VictimPolicy for how the choice is made.

§Examples

use lock_db::{TxnId, VictimPolicy, WaitForGraph};

let cycle = [TxnId::new(3), TxnId::new(7), TxnId::new(5)];
assert_eq!(WaitForGraph::pick_victim(&cycle, VictimPolicy::Youngest), Some(TxnId::new(7)));
assert_eq!(WaitForGraph::pick_victim(&cycle, VictimPolicy::Oldest), Some(TxnId::new(3)));