});
#[derive(Eq, PartialEq)]
+#[repr(align(64))] // Force the size to 64 bytes
struct RouteGraphNode {
node_id: NodeId,
- lowest_fee_to_node: u64,
- total_cltv_delta: u32,
+ score: u64,
// The maximum value a yet-to-be-constructed payment path might flow through this node.
// This value is upper-bounded by us by:
// - how much is needed for a path being constructed
// - how much value can channels following this node (up to the destination) can contribute,
// considering their capacity and fees
value_contribution_msat: u64,
- /// The effective htlc_minimum_msat at this hop. If a later hop on the path had a higher HTLC
- /// minimum, we use it, plus the fees required at each earlier hop to meet it.
- path_htlc_minimum_msat: u64,
- /// All penalties incurred from this hop on the way to the destination, as calculated using
- /// channel scoring.
- path_penalty_msat: u64,
+ total_cltv_delta: u32,
/// The number of hops walked up to this node.
path_length_to_node: u8,
}
impl cmp::Ord for RouteGraphNode {
fn cmp(&self, other: &RouteGraphNode) -> cmp::Ordering {
- let other_score = cmp::max(other.lowest_fee_to_node, other.path_htlc_minimum_msat)
- .saturating_add(other.path_penalty_msat);
- let self_score = cmp::max(self.lowest_fee_to_node, self.path_htlc_minimum_msat)
- .saturating_add(self.path_penalty_msat);
- other_score.cmp(&self_score).then_with(|| other.node_id.cmp(&self.node_id))
+ other.score.cmp(&self.score).then_with(|| other.node_id.cmp(&self.node_id))
}
}
}
}
+// While RouteGraphNode can be laid out with fewer bytes, performance appears to be improved
+// substantially when it is laid out at exactly 64 bytes.
+const _GRAPH_NODE_SMALL: usize = 64 - core::mem::size_of::<RouteGraphNode>();
+const _GRAPH_NODE_FIXED_SIZE: usize = core::mem::size_of::<RouteGraphNode>() - 64;
+
/// A wrapper around the various hop representations.
///
/// Can be used to examine the properties of a hop,
details: &'a ChannelDetails,
/// The node id of the payer, which is also the source side of this candidate route hop.
payer_node_id: &'a NodeId,
+ /// XXX
+ payer_node_counter: u32,
+ /// XXX
+ target_node_counter: u32,
},
/// A hop found in the [`ReadOnlyNetworkGraph`].
PublicHop {
/// Information about the private hop communicated via BOLT 11.
hint: &'a RouteHintHop,
/// Node id of the next hop in BOLT 11 route hint.
- target_node_id: &'a NodeId
+ target_node_id: &'a NodeId,
+ /// XXX
+ source_node_counter: u32,
+ /// XXX
+ target_node_counter: u32,
},
/// A blinded path which starts with an introduction point and ultimately terminates with the
/// payee.
/// This is used to cheaply uniquely identify this blinded path, even though we don't have
/// a short channel ID for this hop.
hint_idx: usize,
+ /// XXX
+ source_node_counter: u32,
},
/// Similar to [`Self::Blinded`], but the path here only has one hop.
///
/// This is used to cheaply uniquely identify this blinded path, even though we don't have
/// a short channel ID for this hop.
hint_idx: usize,
+ /// XXX
+ source_node_counter: u32,
},
}
}
}
+ #[inline(always)]
+ fn src_node_counter(&self) -> u32 {
+ match self {
+ CandidateRouteHop::FirstHop { payer_node_counter, .. } => *payer_node_counter,
+ CandidateRouteHop::PublicHop { info, .. } => info.source_counter(),
+ CandidateRouteHop::PrivateHop { source_node_counter, .. } => *source_node_counter,
+ CandidateRouteHop::Blinded { source_node_counter, .. } => *source_node_counter,
+ CandidateRouteHop::OneHopBlinded { source_node_counter, .. } => *source_node_counter,
+ }
+ }
+
+ #[inline]
+ fn target_node_counter(&self) -> Option<u32> {
+ match self {
+ CandidateRouteHop::FirstHop { target_node_counter, .. } => Some(*target_node_counter),
+ CandidateRouteHop::PublicHop { info, .. } => Some(info.target_counter()),
+ CandidateRouteHop::PrivateHop { target_node_counter, .. } => Some(*target_node_counter),
+ CandidateRouteHop::Blinded { .. } => None,
+ CandidateRouteHop::OneHopBlinded { .. } => None,
+ }
+ }
+
/// Returns the fees that must be paid to route an HTLC over this channel.
#[inline]
pub fn fees(&self) -> RoutingFees {
/// Fee values should be updated only in the context of the whole path, see update_value_and_recompute_fees.
/// These fee values are useful to choose hops as we traverse the graph "payee-to-payer".
#[derive(Clone)]
+#[repr(align(128))]
struct PathBuildingHop<'a> {
candidate: CandidateRouteHop<'a>,
- fee_msat: u64,
-
- /// All the fees paid *after* this channel on the way to the destination
- next_hops_fee_msat: u64,
- /// Fee paid for the use of the current channel (see candidate.fees()).
- /// The value will be actually deducted from the counterparty balance on the previous link.
- hop_use_fee_msat: u64,
+ target_node_counter: Option<u32>,
+ /// If we've already processed a node as the best node, we shouldn't process it again. Normally
+ /// we'd just ignore it if we did as all channels would have a higher new fee, but because we
+ /// may decrease the amounts in use as we walk the graph, the actual calculated fee may
+ /// decrease as well. Thus, we have to explicitly track which nodes have been processed and
+ /// avoid processing them again.
+ was_processed: bool,
+ /// XXX
+ is_first_hop_target: bool,
/// Used to compare channels when choosing the for routing.
/// Includes paying for the use of a hop and the following hops, as well as
/// an estimated cost of reaching this hop.
/// All penalties incurred from this channel on the way to the destination, as calculated using
/// channel scoring.
path_penalty_msat: u64,
- /// If we've already processed a node as the best node, we shouldn't process it again. Normally
- /// we'd just ignore it if we did as all channels would have a higher new fee, but because we
- /// may decrease the amounts in use as we walk the graph, the actual calculated fee may
- /// decrease as well. Thus, we have to explicitly track which nodes have been processed and
- /// avoid processing them again.
- was_processed: bool,
+
+ fee_msat: u64,
+
+ /// All the fees paid *after* this channel on the way to the destination
+ next_hops_fee_msat: u64,
+ /// Fee paid for the use of the current channel (see candidate.fees()).
+ /// The value will be actually deducted from the counterparty balance on the previous link.
+ hop_use_fee_msat: u64,
+
#[cfg(all(not(ldk_bench), any(test, fuzzing)))]
// In tests, we apply further sanity checks on cases where we skip nodes we already processed
// to ensure it is specifically in cases where the fee has gone down because of a decrease in
value_contribution_msat: u64,
}
-// Checks that the entries in the `find_route` `dist` map fit in (exactly) two standard x86-64
-// cache lines. Sadly, they're not guaranteed to actually lie on a cache line (and in fact,
-// generally won't, because at least glibc's malloc will align to a nice, big, round
-// boundary...plus 16), but at least it will reduce the amount of data we'll need to load.
-//
-// Note that these assertions only pass on somewhat recent rustc, and thus are gated on the
-// ldk_bench flag.
-#[cfg(ldk_bench)]
-const _NODE_MAP_SIZE_TWO_CACHE_LINES: usize = 128 - core::mem::size_of::<(NodeId, PathBuildingHop)>();
-#[cfg(ldk_bench)]
-const _NODE_MAP_SIZE_EXACTLY_CACHE_LINES: usize = core::mem::size_of::<(NodeId, PathBuildingHop)>() - 128;
+const _NODE_MAP_SIZE_TWO_CACHE_LINES: usize = 128 - core::mem::size_of::<Option<PathBuildingHop>>();
+const _NODE_MAP_SIZE_EXACTLY_TWO_CACHE_LINES: usize = core::mem::size_of::<Option<PathBuildingHop>>() - 128;
impl<'a> core::fmt::Debug for PathBuildingHop<'a> {
fn fmt(&self, f: &mut core::fmt::Formatter) -> Result<(), core::fmt::Error> {
let mut debug_struct = f.debug_struct("PathBuildingHop");
debug_struct
- .field("node_id", &self.candidate.target())
+ .field("source_node_id", &self.candidate.source())
+ .field("target_node_id", &self.candidate.target())
.field("short_channel_id", &self.candidate.short_channel_id())
.field("total_fee_msat", &self.total_fee_msat)
.field("next_hops_fee_msat", &self.next_hops_fee_msat)
.field("hop_use_fee_msat", &self.hop_use_fee_msat)
- .field("total_fee_msat - (next_hops_fee_msat + hop_use_fee_msat)", &(&self.total_fee_msat - (&self.next_hops_fee_msat + &self.hop_use_fee_msat)))
+ .field("total_fee_msat - (next_hops_fee_msat + hop_use_fee_msat)", &(&self.total_fee_msat.saturating_sub(self.next_hops_fee_msat).saturating_sub(self.hop_use_fee_msat)))
.field("path_penalty_msat", &self.path_penalty_msat)
.field("path_htlc_minimum_msat", &self.path_htlc_minimum_msat)
.field("cltv_expiry_delta", &self.candidate.cltv_expiry_delta());
first_hops.map(|hops| hops.len()).unwrap_or(0), if first_hops.is_some() { "" } else { "not " },
max_total_routing_fee_msat);
+ let private_hop_targets_node_counter_offset = network_graph.max_node_counter() + 2;
+ let mut private_node_id_to_node_counter = HashMap::new();
+
+ let mut private_hop_key_cache = HashMap::with_capacity(
+ payment_params.payee.unblinded_route_hints().iter().map(|path| path.0.len()).sum()
+ );
+
+ // Because we store references to private hop node_ids in `dist`, below, we need them to exist
+ // (as `NodeId`, not `PublicKey`) for the lifetime of `dist`. Thus, we calculate all the keys
+ // we'll need here and simply fetch them when routing.
+ let payee_node_counter = payee_node_id_opt
+ .and_then(|payee| network_nodes.get(&payee))
+ .map(|node| node.node_counter)
+ .unwrap_or(private_hop_targets_node_counter_offset);
+ private_node_id_to_node_counter.insert(maybe_dummy_payee_node_id, payee_node_counter);
+ private_hop_key_cache.insert(maybe_dummy_payee_pk, (NodeId::from_pubkey(&maybe_dummy_payee_pk), payee_node_counter));
+
+ for route in payment_params.payee.unblinded_route_hints().iter() {
+ for hop in route.0.iter() {
+ let hop_node_id = NodeId::from_pubkey(&hop.src_node_id);
+ let node_counter = if let Some(node) = network_nodes.get(&hop_node_id) {
+ node.node_counter
+ } else {
+ let next_node_counter = private_hop_targets_node_counter_offset + private_node_id_to_node_counter.len() as u32;
+ *private_node_id_to_node_counter.entry(hop_node_id)
+ .or_insert(next_node_counter)
+ };
+ private_hop_key_cache.insert(hop.src_node_id, (hop_node_id, node_counter));
+ }
+ }
+
// Step (1).
// Prepare the data we'll use for payee-to-payer search by
// inserting first hops suggested by the caller as targets.
// Our search will then attempt to reach them while traversing from the payee node.
- let mut first_hop_targets: HashMap<_, Vec<&ChannelDetails>> =
+ let mut first_hop_targets: HashMap<_, (Vec<&ChannelDetails>, u32)> =
HashMap::with_capacity(if first_hops.is_some() { first_hops.as_ref().unwrap().len() } else { 0 });
if let Some(hops) = first_hops {
for chan in hops {
if chan.counterparty.node_id == *our_node_pubkey {
return Err(LightningError{err: "First hop cannot have our_node_pubkey as a destination.".to_owned(), action: ErrorAction::IgnoreError});
}
+ let counterparty_node_id = NodeId::from_pubkey(&chan.counterparty.node_id);
first_hop_targets
- .entry(NodeId::from_pubkey(&chan.counterparty.node_id))
- .or_insert(Vec::new())
- .push(chan);
+ .entry(counterparty_node_id)
+ .or_insert_with(|| {
+ let node_counter = if let Some(node) = network_nodes.get(&counterparty_node_id) {
+ node.node_counter
+ } else {
+ let next_node_counter = private_hop_targets_node_counter_offset + private_node_id_to_node_counter.len() as u32;
+ *private_node_id_to_node_counter.entry(counterparty_node_id)
+ .or_insert(next_node_counter)
+ };
+ (Vec::new(), node_counter)
+ })
+ .0.push(chan);
}
if first_hop_targets.is_empty() {
return Err(LightningError{err: "Cannot route when there are no outbound routes away from us".to_owned(), action: ErrorAction::IgnoreError});
}
}
- let mut private_hop_key_cache = HashMap::with_capacity(
- payment_params.payee.unblinded_route_hints().iter().map(|path| path.0.len()).sum()
- );
-
- // Because we store references to private hop node_ids in `dist`, below, we need them to exist
- // (as `NodeId`, not `PublicKey`) for the lifetime of `dist`. Thus, we calculate all the keys
- // we'll need here and simply fetch them when routing.
- private_hop_key_cache.insert(maybe_dummy_payee_pk, NodeId::from_pubkey(&maybe_dummy_payee_pk));
- for route in payment_params.payee.unblinded_route_hints().iter() {
- for hop in route.0.iter() {
- private_hop_key_cache.insert(hop.src_node_id, NodeId::from_pubkey(&hop.src_node_id));
- }
- }
-
// The main heap containing all candidate next-hops sorted by their score (max(fee,
// htlc_minimum)). Ideally this would be a heap which allowed cheap score reduction instead of
// adding duplicate entries when we find a better path to a given node.
// Map from node_id to information about the best current path to that node, including feerate
// information.
- let mut dist: HashMap<NodeId, PathBuildingHop> = HashMap::with_capacity(network_nodes.len());
+ let dist_len = private_hop_targets_node_counter_offset + private_hop_key_cache.len() as u32 + 1;
+ let mut dist: Vec<Option<PathBuildingHop>> = vec![None; dist_len as usize];
+ let payer_node_counter = network_nodes
+ .get(&our_node_id)
+ .map(|node| node.node_counter)
+ .or_else(|| {
+ private_node_id_to_node_counter.get(&our_node_id).map(|counter| *counter)
+ })
+ .unwrap_or(network_graph.max_node_counter() + 1);
// During routing, if we ignore a path due to an htlc_minimum_msat limit, we set this,
// indicating that we may wish to try again with a higher value, potentially paying to meet an
// when we want to stop looking for new paths.
let mut already_collected_value_msat = 0;
- for (_, channels) in first_hop_targets.iter_mut() {
+ for (_, (channels, _)) in first_hop_targets.iter_mut() {
sort_first_hop_channels(channels, &used_liquidities, recommended_value_msat,
our_node_pubkey);
}
// if the amount being transferred over this path is lower.
// We do this for now, but this is a subject for removal.
if let Some(mut available_value_contribution_msat) = htlc_maximum_msat.checked_sub($next_hops_fee_msat) {
+ let cltv_expiry_delta = $candidate.cltv_expiry_delta();
+ let htlc_minimum_msat = $candidate.htlc_minimum_msat();
let used_liquidity_msat = used_liquidities
.get(&$candidate.id())
.map_or(0, |used_liquidity_msat| {
.checked_sub(2*MEDIAN_HOP_CLTV_EXPIRY_DELTA)
.unwrap_or(payment_params.max_total_cltv_expiry_delta - final_cltv_expiry_delta);
let hop_total_cltv_delta = ($next_hops_cltv_delta as u32)
- .saturating_add($candidate.cltv_expiry_delta());
+ .saturating_add(cltv_expiry_delta);
let exceeds_cltv_delta_limit = hop_total_cltv_delta > max_total_cltv_expiry_delta;
let value_contribution_msat = cmp::min(available_value_contribution_msat, $next_hops_value_contribution);
None => unreachable!(),
};
#[allow(unused_comparisons)] // $next_hops_path_htlc_minimum_msat is 0 in some calls so rustc complains
- let over_path_minimum_msat = amount_to_transfer_over_msat >= $candidate.htlc_minimum_msat() &&
+ let over_path_minimum_msat = amount_to_transfer_over_msat >= htlc_minimum_msat &&
amount_to_transfer_over_msat >= $next_hops_path_htlc_minimum_msat;
#[allow(unused_comparisons)] // $next_hops_path_htlc_minimum_msat is 0 in some calls so rustc complains
let may_overpay_to_meet_path_minimum_msat =
- ((amount_to_transfer_over_msat < $candidate.htlc_minimum_msat() &&
- recommended_value_msat >= $candidate.htlc_minimum_msat()) ||
+ ((amount_to_transfer_over_msat < htlc_minimum_msat &&
+ recommended_value_msat >= htlc_minimum_msat) ||
(amount_to_transfer_over_msat < $next_hops_path_htlc_minimum_msat &&
recommended_value_msat >= $next_hops_path_htlc_minimum_msat));
// payment path (upstream to the payee). To avoid that, we recompute
// path fees knowing the final path contribution after constructing it.
let curr_min = cmp::max(
- $next_hops_path_htlc_minimum_msat, $candidate.htlc_minimum_msat()
+ $next_hops_path_htlc_minimum_msat, htlc_minimum_msat
);
- let path_htlc_minimum_msat = compute_fees_saturating(curr_min, $candidate.fees())
+ let candidate_fees = $candidate.fees();
+ let src_node_counter = $candidate.src_node_counter();
+ let path_htlc_minimum_msat = compute_fees_saturating(curr_min, candidate_fees)
.saturating_add(curr_min);
- let hm_entry = dist.entry(src_node_id);
- let old_entry = hm_entry.or_insert_with(|| {
+
+ let dist_entry = &mut dist[src_node_counter as usize];
+ let old_entry = if let Some(hop) = dist_entry {
+ hop
+ } else {
// If there was previously no known way to access the source node
// (recall it goes payee-to-payer) of short_channel_id, first add a
// semi-dummy record just to compute the fees to reach the source node.
// This will affect our decision on selecting short_channel_id
// as a way to reach the $candidate.target() node.
- PathBuildingHop {
+ *dist_entry = Some(PathBuildingHop {
candidate: $candidate.clone(),
+ target_node_counter: None,
fee_msat: 0,
next_hops_fee_msat: u64::max_value(),
hop_use_fee_msat: u64::max_value(),
path_htlc_minimum_msat,
path_penalty_msat: u64::max_value(),
was_processed: false,
+ is_first_hop_target: false,
#[cfg(all(not(ldk_bench), any(test, fuzzing)))]
value_contribution_msat,
- }
- });
+ });
+ dist_entry.as_mut().unwrap()
+ };
#[allow(unused_mut)] // We only use the mut in cfg(test)
let mut should_process = !old_entry.was_processed;
if src_node_id != our_node_id {
// Note that `u64::max_value` means we'll always fail the
// `old_entry.total_fee_msat > total_fee_msat` check below
- hop_use_fee_msat = compute_fees_saturating(amount_to_transfer_over_msat, $candidate.fees());
+ hop_use_fee_msat = compute_fees_saturating(amount_to_transfer_over_msat, candidate_fees);
total_fee_msat = total_fee_msat.saturating_add(hop_use_fee_msat);
}
score_params);
let path_penalty_msat = $next_hops_path_penalty_msat
.saturating_add(channel_penalty_msat);
- let new_graph_node = RouteGraphNode {
- node_id: src_node_id,
- lowest_fee_to_node: total_fee_msat,
- total_cltv_delta: hop_total_cltv_delta,
- value_contribution_msat,
- path_htlc_minimum_msat,
- path_penalty_msat,
- path_length_to_node,
- };
// Update the way of reaching $candidate.source()
// with the given short_channel_id (from $candidate.target()),
.saturating_add(path_penalty_msat);
if !old_entry.was_processed && new_cost < old_cost {
+ let new_graph_node = RouteGraphNode {
+ node_id: src_node_id,
+ score: cmp::max(total_fee_msat, path_htlc_minimum_msat).saturating_add(path_penalty_msat),
+ total_cltv_delta: hop_total_cltv_delta,
+ value_contribution_msat,
+ path_length_to_node,
+ };
targets.push(new_graph_node);
+ old_entry.target_node_counter = $candidate.target_node_counter();
old_entry.next_hops_fee_msat = $next_hops_fee_msat;
old_entry.hop_use_fee_msat = hop_use_fee_msat;
old_entry.total_fee_msat = total_fee_msat;
// meaning how much will be paid in fees after this node (to the best of our knowledge).
// This data can later be helpful to optimize routing (pay lower fees).
macro_rules! add_entries_to_cheapest_to_target_node {
- ( $node: expr, $node_id: expr, $fee_to_target_msat: expr, $next_hops_value_contribution: expr,
- $next_hops_path_htlc_minimum_msat: expr, $next_hops_path_penalty_msat: expr,
+ ( $node: expr, $node_id: expr, $next_hops_value_contribution: expr,
$next_hops_cltv_delta: expr, $next_hops_path_length: expr ) => {
- let skip_node = if let Some(elem) = dist.get_mut(&$node_id) {
+ let fee_to_target_msat;
+ let next_hops_path_htlc_minimum_msat;
+ let next_hops_path_penalty_msat;
+ let is_first_hop_target;
+ let skip_node = if let Some(elem) = &mut dist[$node.node_counter as usize] {
let was_processed = elem.was_processed;
elem.was_processed = true;
+ fee_to_target_msat = elem.total_fee_msat;
+ next_hops_path_htlc_minimum_msat = elem.path_htlc_minimum_msat;
+ next_hops_path_penalty_msat = elem.path_penalty_msat;
+ is_first_hop_target = elem.is_first_hop_target;
was_processed
} else {
// Entries are added to dist in add_entry!() when there is a channel from a node.
// Because there are no channels from payee, it will not have a dist entry at this point.
// If we're processing any other node, it is always be the result of a channel from it.
debug_assert_eq!($node_id, maybe_dummy_payee_node_id);
+
+ fee_to_target_msat = 0;
+ next_hops_path_htlc_minimum_msat = 0;
+ next_hops_path_penalty_msat = 0;
+ is_first_hop_target = false;
false
};
if !skip_node {
- if let Some(first_channels) = first_hop_targets.get(&$node_id) {
- for details in first_channels {
- let candidate = CandidateRouteHop::FirstHop {
- details, payer_node_id: &our_node_id,
- };
- add_entry!(&candidate, $fee_to_target_msat,
- $next_hops_value_contribution,
- $next_hops_path_htlc_minimum_msat, $next_hops_path_penalty_msat,
- $next_hops_cltv_delta, $next_hops_path_length);
+ if is_first_hop_target {
+ if let Some((first_channels, peer_node_counter)) = first_hop_targets.get(&$node_id) {
+ for details in first_channels {
+ debug_assert_eq!(*peer_node_counter, $node.node_counter);
+ let candidate = CandidateRouteHop::FirstHop {
+ details, payer_node_id: &our_node_id, payer_node_counter,
+ target_node_counter: $node.node_counter,
+ };
+ add_entry!(&candidate, fee_to_target_msat,
+ $next_hops_value_contribution,
+ next_hops_path_htlc_minimum_msat, next_hops_path_penalty_msat,
+ $next_hops_cltv_delta, $next_hops_path_length);
+ }
}
}
short_channel_id: *chan_id,
};
add_entry!(&candidate,
- $fee_to_target_msat,
+ fee_to_target_msat,
$next_hops_value_contribution,
- $next_hops_path_htlc_minimum_msat,
- $next_hops_path_penalty_msat,
+ next_hops_path_htlc_minimum_msat,
+ next_hops_path_penalty_msat,
$next_hops_cltv_delta, $next_hops_path_length);
}
}
// For every new path, start from scratch, except for used_liquidities, which
// helps to avoid reusing previously selected paths in future iterations.
targets.clear();
- dist.clear();
+ for e in dist.iter_mut() {
+ *e = None;
+ }
+ for (node_id, (chans, peer_node_counter)) in first_hop_targets.iter() {
+ // In order to avoid looking up whether each node is a first-hop target, we store a
+ // dummy entry in dist for each first-hop target, allowing us to do this lookup for
+ // free since we're already looking at the `was_processed` flag.
+ //
+ // Note that all the fields (except `is_first_hop_target`) will be overwritten whenever
+ // we find a path to the target, so are left as dummies here.
+ dist[*peer_node_counter as usize] = Some(PathBuildingHop {
+ candidate: CandidateRouteHop::FirstHop {
+ details: &chans[0],
+ payer_node_id: &our_node_id,
+ target_node_counter: u32::max_value(),
+ payer_node_counter: u32::max_value(),
+ },
+ target_node_counter: None,
+ fee_msat: 0,
+ next_hops_fee_msat: u64::max_value(),
+ hop_use_fee_msat: u64::max_value(),
+ total_fee_msat: u64::max_value(),
+ path_htlc_minimum_msat: u64::max_value(),
+ path_penalty_msat: u64::max_value(),
+ was_processed: false,
+ is_first_hop_target: true,
+ #[cfg(all(not(ldk_bench), any(test, fuzzing)))]
+ value_contribution_msat: 0,
+ });
+ }
hit_minimum_limit = false;
// If first hop is a private channel and the only way to reach the payee, this is the only
// place where it could be added.
- payee_node_id_opt.map(|payee| first_hop_targets.get(&payee).map(|first_channels| {
+ payee_node_id_opt.map(|payee| first_hop_targets.get(&payee).map(|(first_channels, peer_node_counter)| {
+ debug_assert_eq!(*peer_node_counter, payee_node_counter);
for details in first_channels {
let candidate = CandidateRouteHop::FirstHop {
- details, payer_node_id: &our_node_id,
+ details, payer_node_id: &our_node_id, payer_node_counter,
+ target_node_counter: payee_node_counter,
};
let added = add_entry!(&candidate, 0, path_value_msat,
0, 0u64, 0, 0).is_some();
// If not, targets.pop() will not even let us enter the loop in step 2.
None => {},
Some(node) => {
- add_entries_to_cheapest_to_target_node!(node, payee, 0, path_value_msat, 0, 0u64, 0, 0);
+ add_entries_to_cheapest_to_target_node!(node, payee, path_value_msat, 0, 0);
},
});
// it matters only if the fees are exactly the same.
for (hint_idx, hint) in payment_params.payee.blinded_route_hints().iter().enumerate() {
let intro_node_id = NodeId::from_pubkey(&hint.1.introduction_node_id);
- let have_intro_node_in_graph =
+ let intro_node_counter_opt =
// Only add the hops in this route to our candidate set if either
// we have a direct channel to the first hop or the first hop is
// in the regular network graph.
- first_hop_targets.get(&intro_node_id).is_some() ||
- network_nodes.get(&intro_node_id).is_some();
- if !have_intro_node_in_graph || our_node_id == intro_node_id { continue }
+ network_nodes.get(&intro_node_id).map(|node| node.node_counter)
+ .or(
+ first_hop_targets.get(&intro_node_id).map(|(_, node_counter)| *node_counter)
+ );
+ if intro_node_counter_opt.is_none() || our_node_id == intro_node_id { continue }
let candidate = if hint.1.blinded_hops.len() == 1 {
- CandidateRouteHop::OneHopBlinded { hint, hint_idx }
- } else { CandidateRouteHop::Blinded { hint, hint_idx } };
+ CandidateRouteHop::OneHopBlinded {
+ hint,
+ hint_idx,
+ source_node_counter: intro_node_counter_opt.unwrap(),
+ }
+ } else {
+ CandidateRouteHop::Blinded {
+ hint,
+ hint_idx,
+ source_node_counter: intro_node_counter_opt.unwrap(),
+ }
+ };
let mut path_contribution_msat = path_value_msat;
if let Some(hop_used_msat) = add_entry!(&candidate,
0, path_contribution_msat, 0, 0_u64, 0, 0)
{
path_contribution_msat = hop_used_msat;
} else { continue }
- if let Some(first_channels) = first_hop_targets.get_mut(&NodeId::from_pubkey(&hint.1.introduction_node_id)) {
+ if let Some((first_channels, peer_node_counter)) = first_hop_targets.get_mut(&NodeId::from_pubkey(&hint.1.introduction_node_id)) {
sort_first_hop_channels(first_channels, &used_liquidities, recommended_value_msat,
our_node_pubkey);
for details in first_channels {
let first_hop_candidate = CandidateRouteHop::FirstHop {
- details, payer_node_id: &our_node_id,
+ details, payer_node_id: &our_node_id, payer_node_counter,
+ target_node_counter: *peer_node_counter,
};
let blinded_path_fee = match compute_fees(path_contribution_msat, candidate.fees()) {
Some(fee) => fee,
let mut aggregate_path_contribution_msat = path_value_msat;
for (idx, (hop, prev_hop_id)) in hop_iter.zip(prev_hop_iter).enumerate() {
- let target = private_hop_key_cache.get(&prev_hop_id).unwrap();
+ let (target, private_target_node_counter) = private_hop_key_cache.get(&prev_hop_id).unwrap();
+ let (_src_id, private_source_node_counter) = private_hop_key_cache.get(&hop.src_node_id).unwrap();
- if let Some(first_channels) = first_hop_targets.get(&target) {
+ if let Some((first_channels, _)) = first_hop_targets.get(&target) {
if first_channels.iter().any(|d| d.outbound_scid_alias == Some(hop.short_channel_id)) {
log_trace!(logger, "Ignoring route hint with SCID {} (and any previous) due to it being a direct channel of ours.",
hop.short_channel_id);
info,
short_channel_id: hop.short_channel_id,
})
- .unwrap_or_else(|| CandidateRouteHop::PrivateHop { hint: hop, target_node_id: target });
+ .unwrap_or_else(|| CandidateRouteHop::PrivateHop {
+ hint: hop, target_node_id: target,
+ source_node_counter: *private_source_node_counter,
+ target_node_counter: *private_target_node_counter,
+ });
if let Some(hop_used_msat) = add_entry!(&candidate,
aggregate_next_hops_fee_msat, aggregate_path_contribution_msat,
.saturating_add(1);
// Searching for a direct channel between last checked hop and first_hop_targets
- if let Some(first_channels) = first_hop_targets.get_mut(&target) {
+ if let Some((first_channels, peer_node_counter)) = first_hop_targets.get_mut(&target) {
sort_first_hop_channels(first_channels, &used_liquidities,
recommended_value_msat, our_node_pubkey);
for details in first_channels {
let first_hop_candidate = CandidateRouteHop::FirstHop {
- details, payer_node_id: &our_node_id,
+ details, payer_node_id: &our_node_id, payer_node_counter,
+ target_node_counter: *peer_node_counter,
};
add_entry!(&first_hop_candidate,
aggregate_next_hops_fee_msat, aggregate_path_contribution_msat,
// Note that we *must* check if the last hop was added as `add_entry`
// always assumes that the third argument is a node to which we have a
// path.
- if let Some(first_channels) = first_hop_targets.get_mut(&NodeId::from_pubkey(&hop.src_node_id)) {
+ if let Some((first_channels, peer_node_counter)) = first_hop_targets.get_mut(&NodeId::from_pubkey(&hop.src_node_id)) {
sort_first_hop_channels(first_channels, &used_liquidities,
recommended_value_msat, our_node_pubkey);
for details in first_channels {
let first_hop_candidate = CandidateRouteHop::FirstHop {
- details, payer_node_id: &our_node_id,
+ details, payer_node_id: &our_node_id, payer_node_counter,
+ target_node_counter: *peer_node_counter,
};
add_entry!(&first_hop_candidate,
aggregate_next_hops_fee_msat,
// Both these cases (and other cases except reaching recommended_value_msat) mean that
// paths_collection will be stopped because found_new_path==false.
// This is not necessarily a routing failure.
- 'path_construction: while let Some(RouteGraphNode { node_id, lowest_fee_to_node, total_cltv_delta, mut value_contribution_msat, path_htlc_minimum_msat, path_penalty_msat, path_length_to_node, .. }) = targets.pop() {
+ 'path_construction: while let Some(RouteGraphNode { node_id, total_cltv_delta, mut value_contribution_msat, path_length_to_node, .. }) = targets.pop() {
// Since we're going payee-to-payer, hitting our node as a target means we should stop
// traversing the graph and arrange the path out of what we found.
if node_id == our_node_id {
- let mut new_entry = dist.remove(&our_node_id).unwrap();
+ let mut new_entry = dist[payer_node_counter as usize].take().unwrap();
let mut ordered_hops: Vec<(PathBuildingHop, NodeFeatures)> = vec!((new_entry.clone(), default_node_features.clone()));
'path_walk: loop {
let mut features_set = false;
- let target = ordered_hops.last().unwrap().0.candidate.target().unwrap_or(maybe_dummy_payee_node_id);
- if let Some(first_channels) = first_hop_targets.get(&target) {
+ let candidate = &ordered_hops.last().unwrap().0.candidate;
+ let target = candidate.target().unwrap_or(maybe_dummy_payee_node_id);
+ let target_node_counter = candidate.target_node_counter();
+ if let Some((first_channels, _)) = first_hop_targets.get(&target) {
for details in first_channels {
if let CandidateRouteHop::FirstHop { details: last_hop_details, .. }
= ordered_hops.last().unwrap().0.candidate
// save this path for the payment route. Also, update the liquidity
// remaining on the used hops, so that we take them into account
// while looking for more paths.
- if target == maybe_dummy_payee_node_id {
+ if target_node_counter.is_none() {
break 'path_walk;
}
+ if target_node_counter == Some(payee_node_counter) { break 'path_walk; }
- new_entry = match dist.remove(&target) {
+ new_entry = match dist[target_node_counter.unwrap() as usize].take() {
Some(payment_hop) => payment_hop,
// We can't arrive at None because, if we ever add an entry to targets,
// we also fill in the entry in dist (see add_entry!).
match network_nodes.get(&node_id) {
None => {},
Some(node) => {
- add_entries_to_cheapest_to_target_node!(node, node_id, lowest_fee_to_node,
- value_contribution_msat, path_htlc_minimum_msat, path_penalty_msat,
+ add_entries_to_cheapest_to_target_node!(node, node_id,
+ value_contribution_msat,
total_cltv_delta, path_length_to_node);
},
}
pub(crate) mod bench_utils {
use super::*;
use std::fs::File;
+ use std::time::Duration;
use bitcoin::hashes::Hash;
use bitcoin::secp256k1::{PublicKey, Secp256k1, SecretKey};
if let Ok(route) = route_res {
for path in route.paths {
if seed & 0x80 == 0 {
- scorer.payment_path_successful(&path);
+ scorer.payment_path_successful(&path, Duration::ZERO);
} else {
let short_channel_id = path.hops[path.hops.len() / 2].short_channel_id;
- scorer.payment_path_failed(&path, short_channel_id);
+ scorer.payment_path_failed(&path, short_channel_id, Duration::ZERO);
}
seed = seed.overflowing_mul(6364136223846793005).0.overflowing_add(1).0;
}
score_params: &S::ScoreParams, features: Bolt11InvoiceFeatures, starting_amount: u64,
bench_name: &'static str,
) {
- let payer = bench_utils::payer_pubkey();
- let keys_manager = KeysManager::new(&[0u8; 32], 42, 42);
- let random_seed_bytes = keys_manager.get_secure_random_bytes();
-
// First, get 100 (source, destination) pairs for which route-getting actually succeeds...
let route_endpoints = bench_utils::generate_test_routes(graph, &mut scorer, score_params, features, 0xdeadbeef, starting_amount, 50);
// ...then benchmark finding paths between the nodes we learned.
+ do_route_bench(bench, graph, scorer, score_params, bench_name, route_endpoints);
+ }
+
+ #[inline(never)]
+ fn do_route_bench<S: ScoreLookUp + ScoreUpdate>(
+ bench: &mut Criterion, graph: &NetworkGraph<&TestLogger>, scorer: S,
+ score_params: &S::ScoreParams, bench_name: &'static str,
+ route_endpoints: Vec<(ChannelDetails, PaymentParameters, u64)>,
+ ) {
+ let payer = bench_utils::payer_pubkey();
+ let keys_manager = KeysManager::new(&[0u8; 32], 42, 42);
+ let random_seed_bytes = keys_manager.get_secure_random_bytes();
+
let mut idx = 0;
bench.bench_function(bench_name, |b| b.iter(|| {
let (first_hop, params, amt) = &route_endpoints[idx % route_endpoints.len()];
projects / rust-lightning / blobdiff