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

diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs
index cd75654b..2d3eed66 100644
--- a/lightning/src/routing/router.rs
+++ b/lightning/src/routing/router.rs
@@ -29,6 +29,72 @@ use alloc::collections::BinaryHeap;
 use core::cmp;
 use core::ops::Deref;
 
+/// A trait defining behavior for routing a payment.
+pub trait Router {
+	/// Finds a [`Route`] between `payer` and `payee` for a payment with the given values.
+	fn find_route(
+		&self, payer: &PublicKey, route_params: &RouteParameters,
+		first_hops: Option<&[&ChannelDetails]>, inflight_htlcs: InFlightHtlcs
+	) -> Result<Route, LightningError>;
+}
+
+/// 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 {
+	/// 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
+	/// id.
+	pub fn used_liquidity_msat(&self, source: &NodeId, target: &NodeId, channel_scid: u64) -> Option<u64> {
+		self.0.get(&(channel_scid, source < target)).map(|v| *v)
+	}
+}
+
+impl Writeable for InFlightHtlcs {
+	fn write<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> { self.0.write(writer) }
+}
+
+impl Readable for InFlightHtlcs {
+	fn read<R: io::Read>(reader: &mut R) -> Result<Self, DecodeError> {
+		let infight_map: HashMap<(u64, bool), u64> = Readable::read(reader)?;
+		Ok(Self(infight_map))
+	}
+}
+
 /// A hop in a route
 #[derive(Clone, Debug, Hash, PartialEq, Eq)]
 pub struct RouteHop {
@@ -185,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.
 //