use std::collections::{HashMap, HashSet};
use std::sync::atomic::{AtomicU64, Ordering};
use std::sync::Mutex;
use chia_protocol::Bytes32;
use crate::wallet::clock::Clock;
pub const DEFAULT_RESERVATION_TTL_SECS: u64 = 300;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct ReservationId(u64);
impl ReservationId {
pub fn as_u64(self) -> u64 {
self.0
}
}
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
pub enum ReservationError {
#[error("coin {coin_id} is already reserved by an in-flight spend")]
Conflict {
coin_id: Bytes32,
},
#[error(
"the coin reservation store could not be read, so coin selection cannot be trusted: {0}"
)]
Unavailable(String),
}
pub trait CoinReservationStore: Send + Sync + std::fmt::Debug {
fn held(&self, now_unix: u64) -> Result<Vec<Bytes32>, ReservationError>;
fn reserve_all(
&self,
coins: &[Bytes32],
now_unix: u64,
expires_at_unix: u64,
) -> Result<ReservationId, ReservationError>;
fn release(&self, id: ReservationId) -> Result<(), ReservationError>;
}
#[derive(Debug, Clone)]
struct Entry {
coins: Vec<Bytes32>,
expires_at_unix: u64,
}
#[derive(Debug, Default)]
pub struct LocalReservations {
entries: Mutex<HashMap<u64, Entry>>,
next_id: AtomicU64,
}
impl LocalReservations {
pub fn new() -> Self {
Self::default()
}
pub fn reservations(&self) -> CoinReservations<'_> {
CoinReservations::new(self, &crate::wallet::clock::SystemClock)
}
fn expire(entries: &mut HashMap<u64, Entry>, now_unix: u64) {
entries.retain(|_, entry| entry.expires_at_unix >= now_unix);
}
fn lock(&self) -> Result<std::sync::MutexGuard<'_, HashMap<u64, Entry>>, ReservationError> {
self.entries.lock().map_err(|_| {
ReservationError::Unavailable(
"the in-process reservation table was left in an unknown state by a panic".into(),
)
})
}
}
impl CoinReservationStore for LocalReservations {
fn held(&self, now_unix: u64) -> Result<Vec<Bytes32>, ReservationError> {
let mut entries = self.lock()?;
Self::expire(&mut entries, now_unix);
Ok(entries
.values()
.flat_map(|entry| entry.coins.iter().copied())
.collect())
}
fn reserve_all(
&self,
coins: &[Bytes32],
now_unix: u64,
expires_at_unix: u64,
) -> Result<ReservationId, ReservationError> {
let mut entries = self.lock()?;
Self::expire(&mut entries, now_unix);
if coins.is_empty() {
return Ok(ReservationId(self.next_id.fetch_add(1, Ordering::Relaxed)));
}
let held: HashSet<Bytes32> = entries
.values()
.flat_map(|entry| entry.coins.iter().copied())
.collect();
if let Some(clash) = coins.iter().find(|coin_id| held.contains(*coin_id)) {
return Err(ReservationError::Conflict { coin_id: *clash });
}
let id = self.next_id.fetch_add(1, Ordering::Relaxed);
entries.insert(
id,
Entry {
coins: coins.to_vec(),
expires_at_unix,
},
);
Ok(ReservationId(id))
}
fn release(&self, id: ReservationId) -> Result<(), ReservationError> {
self.lock()?.remove(&id.0);
Ok(())
}
}
#[derive(Debug, Clone, Copy)]
pub struct CoinReservations<'a> {
store: &'a dyn CoinReservationStore,
clock: &'a dyn Clock,
ttl_secs: u64,
}
impl<'a> CoinReservations<'a> {
pub fn new(store: &'a dyn CoinReservationStore, clock: &'a dyn Clock) -> Self {
Self {
store,
clock,
ttl_secs: DEFAULT_RESERVATION_TTL_SECS,
}
}
pub fn with_ttl_secs(
store: &'a dyn CoinReservationStore,
clock: &'a dyn Clock,
ttl_secs: u64,
) -> Result<Self, ReservationError> {
if ttl_secs == 0 {
return Err(ReservationError::Unavailable(
"a reservation TTL of zero would lapse before the spend it guards".into(),
));
}
Ok(Self {
store,
clock,
ttl_secs,
})
}
fn now(&self) -> Result<u64, ReservationError> {
self.clock
.now_unix()
.map_err(|e| ReservationError::Unavailable(format!("the clock could not be read: {e}")))
}
pub(crate) fn held(&self) -> Result<HashSet<Bytes32>, ReservationError> {
let now = self.now()?;
Ok(self.store.held(now)?.into_iter().collect())
}
pub(crate) fn reserve(&self, coins: &[Bytes32]) -> Result<ReservationId, ReservationError> {
let now = self.now()?;
let expires_at = now.saturating_add(self.ttl_secs);
self.store.reserve_all(coins, now, expires_at)
}
pub fn release(&self, id: ReservationId) -> Result<(), ReservationError> {
self.store.release(id)
}
}
#[must_use = "dropping this releases the reservation; call commit() to keep the coins held"]
#[derive(Debug)]
pub struct HeldCoins<'a> {
id: ReservationId,
reservations: CoinReservations<'a>,
committed: bool,
}
impl<'a> HeldCoins<'a> {
pub fn commit(mut self) -> ReservationId {
self.committed = true;
self.id
}
pub fn id(&self) -> ReservationId {
self.id
}
}
impl Drop for HeldCoins<'_> {
fn drop(&mut self) {
if self.committed {
return;
}
let _ = self.reservations.release(self.id);
}
}
pub(crate) fn select_and_reserve<'a, T, E, F, M>(
reservations: &CoinReservations<'a>,
attempts: usize,
mut select: F,
unusable: M,
) -> Result<(T, HeldCoins<'a>), E>
where
F: FnMut(&HashSet<Bytes32>) -> Result<(T, Vec<Bytes32>), E>,
M: Fn(ReservationError) -> E,
{
let mut excluded = reservations.held().map_err(&unusable)?;
for _ in 0..attempts.max(1) {
let (chosen, coin_ids) = select(&excluded)?;
match reservations.reserve(&coin_ids) {
Ok(id) => {
return Ok((
chosen,
HeldCoins {
id,
reservations: *reservations,
committed: false,
},
))
}
Err(ReservationError::Conflict { coin_id }) => {
excluded.insert(coin_id);
}
Err(unavailable) => return Err(unusable(unavailable)),
}
}
Err(unusable(ReservationError::Unavailable(
"coin selection kept losing its reservation to another in-flight spend".into(),
)))
}
#[cfg(test)]
mod tests {
use super::*;
use crate::wallet::clock::FixedClock;
use std::sync::atomic::AtomicUsize;
use std::sync::Barrier;
const NOW: u64 = 1_800_000_000;
fn coin(tag: u8) -> Bytes32 {
Bytes32::new([tag; 32])
}
#[test]
fn a_refused_reservation_leaves_the_table_untouched() {
let store = LocalReservations::new();
store
.reserve_all(&[coin(1)], NOW, NOW + 300)
.expect("the first reservation is uncontested");
let error = store
.reserve_all(&[coin(2), coin(1)], NOW, NOW + 300)
.expect_err("coin 1 is already held");
assert_eq!(error, ReservationError::Conflict { coin_id: coin(1) });
let held = store.held(NOW).expect("the table is readable");
assert!(
!held.contains(&coin(2)),
"the coins of a REFUSED reservation must not be held: coin 2 would be stranded with no \
handle able to release it"
);
assert!(held.contains(&coin(1)), "and the granted one still is");
}
#[test]
fn two_concurrent_reservers_cannot_both_take_one_coin() {
const ROUNDS: usize = 100;
const RACERS: usize = 8;
for round in 0..ROUNDS {
let store = LocalReservations::new();
let barrier = Barrier::new(RACERS);
let winners = AtomicUsize::new(0);
let contested = Bytes32::new([round as u8; 32]);
std::thread::scope(|scope| {
for _ in 0..RACERS {
scope.spawn(|| {
barrier.wait();
if store.reserve_all(&[contested], NOW, NOW + 300).is_ok() {
winners.fetch_add(1, Ordering::SeqCst);
}
});
}
});
assert_eq!(
winners.load(Ordering::SeqCst),
1,
"round {round}: exactly one caller may take the coin"
);
}
}
#[test]
fn a_failure_after_reserving_strands_nothing_however_often_it_is_retried() {
let store = LocalReservations::new();
let clock = FixedClock::new(NOW);
let reservations = CoinReservations::new(&store, &clock);
for attempt in 1..=8u8 {
let outcome: Result<Bytes32, ReservationError> = (|| {
let (chosen, _held) = select_and_reserve(
&reservations,
16,
|excluded| {
let pick = (1u8..=32)
.map(coin)
.find(|id| !excluded.contains(id))
.expect("the fixture wallet has coins left");
Ok((pick, vec![pick]))
},
|e| e,
)?;
let _ = chosen;
Err(ReservationError::Unavailable(
"simulated: the read after the reservation failed".into(),
))
})();
assert!(outcome.is_err(), "the fixture must fail after reserving");
assert!(
store.held(NOW).expect("readable").is_empty(),
"attempt {attempt} left coins held for a spend that was never built"
);
}
}
#[test]
fn a_committed_guard_keeps_its_coins() {
let store = LocalReservations::new();
let clock = FixedClock::new(NOW);
let reservations = CoinReservations::new(&store, &clock);
let (_chosen, held) = select_and_reserve(
&reservations,
4,
|_excluded| Ok((coin(7), vec![coin(7)])),
|e: ReservationError| e,
)
.expect("uncontested");
let id = held.commit();
assert!(
store.held(NOW).expect("readable").contains(&coin(7)),
"a committed guard must still be holding its coin"
);
reservations
.release(id)
.expect("and it can still be released by hand");
assert!(store.held(NOW).expect("readable").is_empty());
}
#[test]
fn a_poisoned_table_refuses_both_reads_and_writes() {
let store = LocalReservations::new();
store
.reserve_all(&[coin(4)], NOW, NOW + 300)
.expect("uncontested");
let poisoned = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
let _guard = store.entries.lock().expect("not yet poisoned");
panic!("simulated: a panic while the table was locked");
}));
assert!(poisoned.is_err(), "the fixture must actually panic");
assert!(
matches!(store.held(NOW), Err(ReservationError::Unavailable(_))),
"an unknown table must refuse the read rather than report an empty one"
);
assert!(
matches!(
store.reserve_all(&[coin(5)], NOW, NOW + 300),
Err(ReservationError::Unavailable(_))
),
"and must refuse the write too"
);
}
#[test]
fn reserving_nothing_stores_nothing() {
let store = LocalReservations::new();
for _ in 0..64 {
store
.reserve_all(&[], NOW, NOW + 300)
.expect("an empty reservation cannot conflict");
}
assert_eq!(
store.entries.lock().expect("readable").len(),
0,
"reserving nothing must add no row: nothing ever conflicts with one, so only the TTL "
);
assert!(store.held(NOW).expect("readable").is_empty());
}
#[test]
fn releasing_is_idempotent() {
let store = LocalReservations::new();
let id = store
.reserve_all(&[coin(3)], NOW, NOW + 300)
.expect("uncontested");
store.release(id).expect("the first release succeeds");
store.release(id).expect("and so does the second");
assert!(store.held(NOW).expect("readable").is_empty());
}
#[test]
fn a_zero_ttl_is_refused() {
let store = LocalReservations::new();
let clock = FixedClock::new(NOW);
assert!(matches!(
CoinReservations::with_ttl_secs(&store, &clock, 0),
Err(ReservationError::Unavailable(_))
));
assert!(CoinReservations::with_ttl_secs(&store, &clock, 1).is_ok());
}
#[derive(Debug)]
struct SnipesTheFirstChoice {
forbidden: Bytes32,
inner: LocalReservations,
}
impl CoinReservationStore for SnipesTheFirstChoice {
fn held(&self, _now_unix: u64) -> Result<Vec<Bytes32>, ReservationError> {
Ok(Vec::new())
}
fn reserve_all(
&self,
coins: &[Bytes32],
now_unix: u64,
expires_at_unix: u64,
) -> Result<ReservationId, ReservationError> {
if coins.contains(&self.forbidden) {
return Err(ReservationError::Conflict {
coin_id: self.forbidden,
});
}
self.inner.reserve_all(coins, now_unix, expires_at_unix)
}
fn release(&self, id: ReservationId) -> Result<(), ReservationError> {
self.inner.release(id)
}
}
#[test]
fn a_caller_that_loses_the_race_reselects_rather_than_failing() {
let store = SnipesTheFirstChoice {
forbidden: coin(1),
inner: LocalReservations::new(),
};
let clock = FixedClock::new(NOW);
let reservations = CoinReservations::new(&store, &clock);
let (chosen, _id) = select_and_reserve::<Bytes32, ReservationError, _, _>(
&reservations,
8,
|excluded| {
let pick = if excluded.contains(&coin(1)) {
coin(2)
} else {
coin(1)
};
Ok((pick, vec![pick]))
},
|e| e,
)
.expect("the loser must re-select, not give up");
assert_eq!(chosen, coin(2));
}
#[test]
fn an_endlessly_conflicting_store_is_bounded_rather_than_spinning() {
let store = SnipesTheFirstChoice {
forbidden: coin(1),
inner: LocalReservations::new(),
};
let clock = FixedClock::new(NOW);
let reservations = CoinReservations::new(&store, &clock);
let error = select_and_reserve::<Bytes32, ReservationError, _, _>(
&reservations,
4,
|_excluded| Ok((coin(1), vec![coin(1)])),
|e| e,
)
.expect_err("this cannot succeed and must not hang");
assert!(matches!(error, ReservationError::Unavailable(_)));
}
}