X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Frouter.rs;h=2d3eed6614543cfebf78f1915dc691a04c5d56b0;hb=64b9e83dfed1979adecab83f6efcf10f95ecf987;hp=f102ad8daaae6a79bbfe519b52960d26f73a707e;hpb=9d3324968c175661ae2d11c5c754688978f2fb7f;p=rust-lightning

diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs
index f102ad8d..2d3eed66 100644
--- a/lightning/src/routing/router.rs
+++ b/lightning/src/routing/router.rs
@@ -17,7 +17,7 @@ use bitcoin::secp256k1::PublicKey;
 use crate::ln::channelmanager::ChannelDetails;
 use crate::ln::features::{ChannelFeatures, InvoiceFeatures, NodeFeatures};
 use crate::ln::msgs::{DecodeError, ErrorAction, LightningError, MAX_VALUE_MSAT};
-use crate::routing::gossip::{DirectedChannelInfoWithUpdate, EffectiveCapacity, ReadOnlyNetworkGraph, NetworkGraph, NodeId, RoutingFees};
+use crate::routing::gossip::{DirectedChannelInfo, EffectiveCapacity, ReadOnlyNetworkGraph, NetworkGraph, NodeId, RoutingFees};
 use crate::routing::scoring::{ChannelUsage, Score};
 use crate::util::ser::{Writeable, Readable, Writer};
 use crate::util::logger::{Level, Logger};
@@ -38,20 +38,43 @@ pub trait Router {
 	) -> Result<Route, LightningError>;
 }
 
-/// A map with liquidity value (in msat) keyed by a short channel id and the direction the HTLC
-/// is traveling in. The direction boolean is determined by checking if the HTLC source's public
-/// key is less than its destination. See [`InFlightHtlcs::used_liquidity_msat`] for more
-/// details.
-#[cfg(not(any(test, feature = "_test_utils")))]
-pub struct InFlightHtlcs(HashMap<(u64, bool), u64>);
-#[cfg(any(test, feature = "_test_utils"))]
-pub struct InFlightHtlcs(pub HashMap<(u64, bool), u64>);
+/// A data structure for tracking in-flight HTLCs. May be used during pathfinding to account for
+/// in-use channel liquidity.
+pub struct InFlightHtlcs(
+	// A map with liquidity value (in msat) keyed by a short channel id and the direction the HTLC
+	// is traveling in. The direction boolean is determined by checking if the HTLC source's public
+	// key is less than its destination. See `InFlightHtlcs::used_liquidity_msat` for more
+	// details.
+	HashMap<(u64, bool), u64>
+);
 
 impl InFlightHtlcs {
-	/// Create a new `InFlightHtlcs` via a mapping from:
-	/// (short_channel_id, source_pubkey < target_pubkey) -> used_liquidity_msat
-	pub fn new(inflight_map: HashMap<(u64, bool), u64>) -> Self {
-		InFlightHtlcs(inflight_map)
+	/// Constructs an empty `InFlightHtlcs`.
+	pub fn new() -> Self { InFlightHtlcs(HashMap::new()) }
+
+	/// Takes in a path with payer's node id and adds the path's details to `InFlightHtlcs`.
+	pub fn process_path(&mut self, path: &[RouteHop], payer_node_id: PublicKey) {
+		if path.is_empty() { return };
+		// total_inflight_map needs to be direction-sensitive when keeping track of the HTLC value
+		// that is held up. However, the `hops` array, which is a path returned by `find_route` in
+		// the router excludes the payer node. In the following lines, the payer's information is
+		// hardcoded with an inflight value of 0 so that we can correctly represent the first hop
+		// in our sliding window of two.
+		let reversed_hops_with_payer = path.iter().rev().skip(1)
+			.map(|hop| hop.pubkey)
+			.chain(core::iter::once(payer_node_id));
+		let mut cumulative_msat = 0;
+
+		// Taking the reversed vector from above, we zip it with just the reversed hops list to
+		// work "backwards" of the given path, since the last hop's `fee_msat` actually represents
+		// the total amount sent.
+		for (next_hop, prev_hop) in path.iter().rev().zip(reversed_hops_with_payer) {
+			cumulative_msat += next_hop.fee_msat;
+			self.0
+				.entry((next_hop.short_channel_id, NodeId::from_pubkey(&prev_hop) < NodeId::from_pubkey(&next_hop.pubkey)))
+				.and_modify(|used_liquidity_msat| *used_liquidity_msat += cumulative_msat)
+				.or_insert(cumulative_msat);
+		}
 	}
 
 	/// Returns liquidity in msat given the public key of the HTLC source, target, and short channel
@@ -228,8 +251,7 @@ pub const DEFAULT_MAX_PATH_COUNT: u8 = 10;
 const MEDIAN_HOP_CLTV_EXPIRY_DELTA: u32 = 40;
 
 // During routing, we only consider paths shorter than our maximum length estimate.
-// In the legacy onion format, the maximum number of hops used to be a fixed value of 20.
-// However, in the TLV onion format, there is no fixed maximum length, but the `hop_payloads`
+// In the TLV onion format, there is no fixed maximum length, but the `hop_payloads`
 // field is always 1300 bytes. As the `tlv_payload` for each hop may vary in length, we have to
 // estimate how many hops the route may have so that it actually fits the `hop_payloads` field.
 //
@@ -464,7 +486,7 @@ enum CandidateRouteHop<'a> {
 	},
 	/// A hop found in the [`ReadOnlyNetworkGraph`], where the channel capacity may be unknown.
 	PublicHop {
-		info: DirectedChannelInfoWithUpdate<'a>,
+		info: DirectedChannelInfo<'a>,
 		short_channel_id: u64,
 	},
 	/// A hop to the payee found in the payment invoice, though not necessarily a direct channel.
@@ -537,10 +559,8 @@ fn max_htlc_from_capacity(capacity: EffectiveCapacity, max_channel_saturation_po
 		EffectiveCapacity::Unknown => EffectiveCapacity::Unknown.as_msat(),
 		EffectiveCapacity::MaximumHTLC { amount_msat } =>
 			amount_msat.checked_shr(saturation_shift).unwrap_or(0),
-		EffectiveCapacity::Total { capacity_msat, htlc_maximum_msat: None } =>
-			capacity_msat.checked_shr(saturation_shift).unwrap_or(0),
-		EffectiveCapacity::Total { capacity_msat, htlc_maximum_msat: Some(htlc_max) } =>
-			cmp::min(capacity_msat.checked_shr(saturation_shift).unwrap_or(0), htlc_max),
+		EffectiveCapacity::Total { capacity_msat, htlc_maximum_msat } =>
+			cmp::min(capacity_msat.checked_shr(saturation_shift).unwrap_or(0), htlc_maximum_msat),
 	}
 }
 
@@ -1319,13 +1339,11 @@ where L::Target: Logger {
 					for chan_id in $node.channels.iter() {
 						let chan = network_channels.get(chan_id).unwrap();
 						if !chan.features.requires_unknown_bits() {
-							let (directed_channel, source) =
-								chan.as_directed_to(&$node_id).expect("inconsistent NetworkGraph");
-							if first_hops.is_none() || *source != our_node_id {
-								if let Some(direction) = directed_channel.direction() {
-									if direction.enabled {
+							if let Some((directed_channel, source)) = chan.as_directed_to(&$node_id) {
+								if first_hops.is_none() || *source != our_node_id {
+									if directed_channel.direction().enabled {
 										let candidate = CandidateRouteHop::PublicHop {
-											info: directed_channel.with_update().unwrap(),
+											info: directed_channel,
 											short_channel_id: *chan_id,
 										};
 										add_entry!(candidate, *source, $node_id,
@@ -1410,8 +1428,7 @@ where L::Target: Logger {
 					let candidate = network_channels
 						.get(&hop.short_channel_id)
 						.and_then(|channel| channel.as_directed_to(&target))
-						.and_then(|(channel, _)| channel.with_update())
-						.map(|info| CandidateRouteHop::PublicHop {
+						.map(|(info, _)| CandidateRouteHop::PublicHop {
 							info,
 							short_channel_id: hop.short_channel_id,
 						})
@@ -1859,10 +1876,8 @@ fn add_random_cltv_offset(route: &mut Route, payment_params: &PaymentParameters,
 							random_channel.as_directed_from(&cur_node_id).map(|(dir_info, next_id)| {
 								if !nodes_to_avoid.iter().any(|x| x == next_id) {
 									nodes_to_avoid[random_hop] = *next_id;
-									dir_info.direction().map(|channel_update_info| {
-										random_hop_offset = channel_update_info.cltv_expiry_delta.into();
-										cur_hop = Some(*next_id);
-									});
+									random_hop_offset = dir_info.direction().cltv_expiry_delta.into();
+									cur_hop = Some(*next_id);
 								}
 							});
 						}
@@ -5257,14 +5272,12 @@ mod tests {
 					for channel_id in &cur_node.channels {
 						if let Some(channel_info) = network_channels.get(&channel_id) {
 							if let Some((dir_info, next_id)) = channel_info.as_directed_from(&cur_node_id) {
-								if let Some(channel_update_info) = dir_info.direction() {
-									let next_cltv_expiry_delta = channel_update_info.cltv_expiry_delta as u32;
-									if cur_path_cltv_deltas.iter().sum::<u32>()
-										.saturating_add(next_cltv_expiry_delta) <= observed_cltv_expiry_delta {
-										let mut new_path_cltv_deltas = cur_path_cltv_deltas.clone();
-										new_path_cltv_deltas.push(next_cltv_expiry_delta);
-										candidates.push_back((*next_id, new_path_cltv_deltas));
-									}
+								let next_cltv_expiry_delta = dir_info.direction().cltv_expiry_delta as u32;
+								if cur_path_cltv_deltas.iter().sum::<u32>()
+									.saturating_add(next_cltv_expiry_delta) <= observed_cltv_expiry_delta {
+									let mut new_path_cltv_deltas = cur_path_cltv_deltas.clone();
+									new_path_cltv_deltas.push(next_cltv_expiry_delta);
+									candidates.push_back((*next_id, new_path_cltv_deltas));
 								}
 							}
 						}
@@ -5441,7 +5454,7 @@ mod tests {
 		let usage = ChannelUsage {
 			amount_msat: 0,
 			inflight_htlc_msat: 0,
-			effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: Some(1_000) },
+			effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 1_000 },
 		};
 		scorer.set_manual_penalty(&NodeId::from_pubkey(&nodes[3]), 123);
 		scorer.set_manual_penalty(&NodeId::from_pubkey(&nodes[4]), 456);