X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Fscoring.rs;h=2e1efa751867e3f1e6ffd1fd5f19f681765c2060;hb=d28d6a5403682d2d1539bf73552a4490a2309578;hp=a2d314665d1c7d9273fe71529ad2c46e1fe5fc01;hpb=293e5f21ffd286a2037efcf52a025205e624e744;p=rust-lightning diff --git a/lightning/src/routing/scoring.rs b/lightning/src/routing/scoring.rs index a2d31466..2e1efa75 100644 --- a/lightning/src/routing/scoring.rs +++ b/lightning/src/routing/scoring.rs @@ -46,9 +46,8 @@ //! //! # Note //! -//! If persisting [`Scorer`], it must be restored using the same [`Time`] parameterization. Using a -//! different type results in undefined behavior. Specifically, persisting when built with feature -//! `no-std` and restoring without it, or vice versa, uses different types and thus is undefined. +//! Persisting when built with feature `no-std` and restoring without it, or vice versa, uses +//! different types and thus is undefined. //! //! [`find_route`]: crate::routing::router::find_route @@ -59,14 +58,27 @@ use util::ser::{Readable, Writeable, Writer}; use prelude::*; use core::cell::{RefCell, RefMut}; -use core::ops::{DerefMut, Sub}; +use core::ops::DerefMut; use core::time::Duration; -use io::{self, Read}; use sync::{Mutex, MutexGuard}; +use io::{self, Read}; +use sync::{Mutex, MutexGuard}; +/// We define Score ever-so-slightly differently based on whether we are being built for C bindings +/// or not. For users, `LockableScore` must somehow be writeable to disk. For Rust users, this is +/// no problem - you move a `Score` that implements `Writeable` into a `Mutex`, lock it, and now +/// you have the original, concrete, `Score` type, which presumably implements `Writeable`. +/// +/// For C users, once you've moved the `Score` into a `LockableScore` all you have after locking it +/// is an opaque trait object with an opaque pointer with no type info. Users could take the unsafe +/// approach of blindly casting that opaque pointer to a concrete type and calling `Writeable` from +/// there, but other languages downstream of the C bindings (e.g. Java) can't even do that. +/// Instead, we really want `Score` and `LockableScore` to implement `Writeable` directly, which we +/// do here by defining `Score` differently for `cfg(c_bindings)`. +macro_rules! define_score { ($($supertrait: path)*) => { /// An interface used to score payment channels for path finding. /// /// Scoring is in terms of fees willing to be paid in order to avoid routing through a channel. -pub trait Score { +pub trait Score $(: $supertrait)* { /// Returns the fee in msats willing to be paid to avoid routing `send_amt_msat` through the /// given channel in the direction from `source` to `target`. /// @@ -83,7 +95,30 @@ pub trait Score { /// Handles updating channel penalties after failing to route through a channel. fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64); + + /// Handles updating channel penalties after successfully routing along a path. + fn payment_path_successful(&mut self, path: &[&RouteHop]); +} + +impl $(+ $supertrait)*> Score for T { + fn channel_penalty_msat(&self, short_channel_id: u64, send_amt_msat: u64, channel_capacity_msat: Option, source: &NodeId, target: &NodeId) -> u64 { + self.deref().channel_penalty_msat(short_channel_id, send_amt_msat, channel_capacity_msat, source, target) + } + + fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) { + self.deref_mut().payment_path_failed(path, short_channel_id) + } + + fn payment_path_successful(&mut self, path: &[&RouteHop]) { + self.deref_mut().payment_path_successful(path) + } } +} } + +#[cfg(c_bindings)] +define_score!(Writeable); +#[cfg(not(c_bindings))] +define_score!(); /// A scorer that is accessed under a lock. /// @@ -101,6 +136,7 @@ pub trait LockableScore<'a> { fn lock(&'a self) -> Self::Locked; } +/// (C-not exported) impl<'a, T: 'a + Score> LockableScore<'a> for Mutex { type Locked = MutexGuard<'a, T>; @@ -117,13 +153,34 @@ impl<'a, T: 'a + Score> LockableScore<'a> for RefCell { } } -impl> Score for T { - fn channel_penalty_msat(&self, short_channel_id: u64, send_amt_msat: u64, channel_capacity_msat: Option, source: &NodeId, target: &NodeId) -> u64 { - self.deref().channel_penalty_msat(short_channel_id, send_amt_msat, channel_capacity_msat, source, target) +#[cfg(c_bindings)] +/// A concrete implementation of [`LockableScore`] which supports multi-threading. +pub struct MultiThreadedLockableScore { + score: Mutex, +} +#[cfg(c_bindings)] +/// (C-not exported) +impl<'a, T: Score + 'a> LockableScore<'a> for MultiThreadedLockableScore { + type Locked = MutexGuard<'a, T>; + + fn lock(&'a self) -> MutexGuard<'a, T> { + Mutex::lock(&self.score).unwrap() } +} - fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) { - self.deref_mut().payment_path_failed(path, short_channel_id) +#[cfg(c_bindings)] +/// (C-not exported) +impl<'a, T: Writeable> Writeable for RefMut<'a, T> { + fn write(&self, writer: &mut W) -> Result<(), io::Error> { + T::write(&**self, writer) + } +} + +#[cfg(c_bindings)] +/// (C-not exported) +impl<'a, S: Writeable> Writeable for MutexGuard<'a, S> { + fn write(&self, writer: &mut W) -> Result<(), io::Error> { + S::write(&**self, writer) } } @@ -135,23 +192,33 @@ impl> Score for T { /// See [module-level documentation] for usage. /// /// [module-level documentation]: crate::routing::scoring -pub type Scorer = ScorerUsingTime::; - -/// Time used by [`Scorer`]. #[cfg(not(feature = "no-std"))] -pub type DefaultTime = std::time::Instant; - -/// Time used by [`Scorer`]. +pub type Scorer = ScorerUsingTime::; +/// [`Score`] implementation that provides reasonable default behavior. +/// +/// Used to apply a fixed penalty to each channel, thus avoiding long paths when shorter paths with +/// slightly higher fees are available. Will further penalize channels that fail to relay payments. +/// +/// See [module-level documentation] for usage and [`ScoringParameters`] for customization. +/// +/// [module-level documentation]: crate::routing::scoring #[cfg(feature = "no-std")] -pub type DefaultTime = Eternity; +pub type Scorer = ScorerUsingTime::; -/// [`Score`] implementation parameterized by [`Time`]. +// Note that ideally we'd hide ScorerUsingTime from public view by sealing it as well, but rustdoc +// doesn't handle this well - instead exposing a `Scorer` which has no trait implementation(s) or +// methods at all. + +/// [`Score`] implementation. /// /// See [`Scorer`] for details. /// /// # Note /// -/// Mixing [`Time`] types between serialization and deserialization results in undefined behavior. +/// Mixing the `no-std` feature between serialization and deserialization results in undefined +/// behavior. +/// +/// (C-not exported) generally all users should use the [`Scorer`] type alias. pub struct ScorerUsingTime { params: ScoringParameters, // TODO: Remove entries of closed channels. @@ -168,7 +235,7 @@ pub struct ScoringParameters { /// A penalty in msats to apply to a channel upon failing to relay a payment. /// /// This accumulates for each failure but may be reduced over time based on - /// [`failure_penalty_half_life`]. + /// [`failure_penalty_half_life`] or when successfully routing through a channel. /// /// Default value: 1,024,000 msat /// @@ -195,10 +262,12 @@ pub struct ScoringParameters { /// The time required to elapse before any accumulated [`failure_penalty_msat`] penalties are /// cut in half. /// + /// Successfully routing through a channel will immediately cut the penalty in half as well. + /// /// # Note /// - /// When time is an [`Eternity`], as is default when enabling feature `no-std`, it will never - /// elapse. Therefore, this penalty will never decay. + /// When built with the `no-std` feature, time will never elapse. Therefore, this penalty will + /// never decay. /// /// [`failure_penalty_msat`]: Self::failure_penalty_msat pub failure_penalty_half_life: Duration, @@ -216,25 +285,12 @@ impl_writeable_tlv_based!(ScoringParameters, { /// /// Penalties decay over time, though accumulate as more failures occur. struct ChannelFailure { - /// Accumulated penalty in msats for the channel as of `last_failed`. + /// Accumulated penalty in msats for the channel as of `last_updated`. undecayed_penalty_msat: u64, - /// Last time the channel failed. Used to decay `undecayed_penalty_msat`. - last_failed: T, -} - -/// A measurement of time. -pub trait Time: Sub where Self: Sized { - /// Returns an instance corresponding to the current moment. - fn now() -> Self; - - /// Returns the amount of time elapsed since `self` was created. - fn elapsed(&self) -> Duration; - - /// Returns the amount of time passed since the beginning of [`Time`]. - /// - /// Used during (de-)serialization. - fn duration_since_epoch() -> Duration; + /// Last time the channel either failed to route or successfully routed a payment. Used to decay + /// `undecayed_penalty_msat`. + last_updated: T, } impl ScorerUsingTime { @@ -263,17 +319,22 @@ impl ChannelFailure { fn new(failure_penalty_msat: u64) -> Self { Self { undecayed_penalty_msat: failure_penalty_msat, - last_failed: T::now(), + last_updated: T::now(), } } fn add_penalty(&mut self, failure_penalty_msat: u64, half_life: Duration) { self.undecayed_penalty_msat = self.decayed_penalty_msat(half_life) + failure_penalty_msat; - self.last_failed = T::now(); + self.last_updated = T::now(); + } + + fn reduce_penalty(&mut self, half_life: Duration) { + self.undecayed_penalty_msat = self.decayed_penalty_msat(half_life) >> 1; + self.last_updated = T::now(); } fn decayed_penalty_msat(&self, half_life: Duration) -> u64 { - let decays = self.last_failed.elapsed().as_secs().checked_div(half_life.as_secs()); + let decays = self.last_updated.elapsed().as_secs().checked_div(half_life.as_secs()); match decays { Some(decays) => self.undecayed_penalty_msat >> decays, None => 0, @@ -331,47 +392,14 @@ impl Score for ScorerUsingTime { .and_modify(|failure| failure.add_penalty(failure_penalty_msat, half_life)) .or_insert_with(|| ChannelFailure::new(failure_penalty_msat)); } -} - -#[cfg(not(feature = "no-std"))] -impl Time for std::time::Instant { - fn now() -> Self { - std::time::Instant::now() - } - - fn duration_since_epoch() -> Duration { - use std::time::SystemTime; - SystemTime::now().duration_since(SystemTime::UNIX_EPOCH).unwrap() - } - - fn elapsed(&self) -> Duration { - std::time::Instant::elapsed(self) - } -} - -/// A state in which time has no meaning. -#[derive(Debug, PartialEq, Eq)] -pub struct Eternity; - -impl Time for Eternity { - fn now() -> Self { - Self - } - - fn duration_since_epoch() -> Duration { - Duration::from_secs(0) - } - - fn elapsed(&self) -> Duration { - Duration::from_secs(0) - } -} -impl Sub for Eternity { - type Output = Self; - - fn sub(self, _other: Duration) -> Self { - self + fn payment_path_successful(&mut self, path: &[&RouteHop]) { + let half_life = self.params.failure_penalty_half_life; + for hop in path.iter() { + self.channel_failures + .entry(hop.short_channel_id) + .and_modify(|failure| failure.reduce_penalty(half_life)); + } } } @@ -400,7 +428,7 @@ impl Readable for ScorerUsingTime { impl Writeable for ChannelFailure { #[inline] fn write(&self, w: &mut W) -> Result<(), io::Error> { - let duration_since_epoch = T::duration_since_epoch() - self.last_failed.elapsed(); + let duration_since_epoch = T::duration_since_epoch() - self.last_updated.elapsed(); write_tlv_fields!(w, { (0, self.undecayed_penalty_msat, required), (2, duration_since_epoch, required), @@ -420,17 +448,82 @@ impl Readable for ChannelFailure { }); Ok(Self { undecayed_penalty_msat, - last_failed: T::now() - (T::duration_since_epoch() - duration_since_epoch), + last_updated: T::now() - (T::duration_since_epoch() - duration_since_epoch), }) } } +pub(crate) mod time { + use core::ops::Sub; + use core::time::Duration; + /// A measurement of time. + pub trait Time: Sub where Self: Sized { + /// Returns an instance corresponding to the current moment. + fn now() -> Self; + + /// Returns the amount of time elapsed since `self` was created. + fn elapsed(&self) -> Duration; + + /// Returns the amount of time passed since the beginning of [`Time`]. + /// + /// Used during (de-)serialization. + fn duration_since_epoch() -> Duration; + } + + /// A state in which time has no meaning. + #[derive(Debug, PartialEq, Eq)] + pub struct Eternity; + + #[cfg(not(feature = "no-std"))] + impl Time for std::time::Instant { + fn now() -> Self { + std::time::Instant::now() + } + + fn duration_since_epoch() -> Duration { + use std::time::SystemTime; + SystemTime::now().duration_since(SystemTime::UNIX_EPOCH).unwrap() + } + + fn elapsed(&self) -> Duration { + std::time::Instant::elapsed(self) + } + } + + impl Time for Eternity { + fn now() -> Self { + Self + } + + fn duration_since_epoch() -> Duration { + Duration::from_secs(0) + } + + fn elapsed(&self) -> Duration { + Duration::from_secs(0) + } + } + + impl Sub for Eternity { + type Output = Self; + + fn sub(self, _other: Duration) -> Self { + self + } + } +} + +pub(crate) use self::time::Time; + #[cfg(test)] mod tests { - use super::{Eternity, ScoringParameters, ScorerUsingTime, Time}; + use super::{ScoringParameters, ScorerUsingTime, Time}; + use super::time::Eternity; + use ln::features::{ChannelFeatures, NodeFeatures}; use routing::scoring::Score; use routing::network_graph::NodeId; + use routing::router::RouteHop; use util::ser::{Readable, Writeable}; use bitcoin::secp256k1::PublicKey; @@ -609,6 +702,40 @@ mod tests { assert_eq!(scorer.channel_penalty_msat(42, 1, Some(1), &source, &target), 1_384); } + #[test] + fn reduces_channel_failure_penalties_after_success() { + let mut scorer = Scorer::new(ScoringParameters { + base_penalty_msat: 1_000, + failure_penalty_msat: 512, + failure_penalty_half_life: Duration::from_secs(10), + overuse_penalty_start_1024th: 1024, + overuse_penalty_msat_per_1024th: 0, + }); + let source = source_node_id(); + let target = target_node_id(); + assert_eq!(scorer.channel_penalty_msat(42, 1, Some(1), &source, &target), 1_000); + + scorer.payment_path_failed(&[], 42); + assert_eq!(scorer.channel_penalty_msat(42, 1, Some(1), &source, &target), 1_512); + + SinceEpoch::advance(Duration::from_secs(10)); + assert_eq!(scorer.channel_penalty_msat(42, 1, Some(1), &source, &target), 1_256); + + let hop = RouteHop { + pubkey: PublicKey::from_slice(target.as_slice()).unwrap(), + node_features: NodeFeatures::known(), + short_channel_id: 42, + channel_features: ChannelFeatures::known(), + fee_msat: 1, + cltv_expiry_delta: 18, + }; + scorer.payment_path_successful(&[&hop]); + assert_eq!(scorer.channel_penalty_msat(42, 1, Some(1), &source, &target), 1_128); + + SinceEpoch::advance(Duration::from_secs(10)); + assert_eq!(scorer.channel_penalty_msat(42, 1, Some(1), &source, &target), 1_064); + } + #[test] fn restores_persisted_channel_failure_penalties() { let mut scorer = Scorer::new(ScoringParameters {