From 43d250dadcdad54836eacd8b447bb36d5c8e6cb5 Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Mon, 24 Jun 2024 23:50:29 +0000 Subject: [PATCH] Drop the `dist` `HashMap` in routing, replacing it with a `Vec`. Now that we have unique, dense, 32-bit identifiers for all the nodes in our network graph, we can store the per-node information when routing in a simple `Vec` rather than a `HashMap`. This avoids the overhead of hashing and table scanning entirely, for a nice "simple" optimization win. --- lightning/src/routing/gossip.rs | 16 ++- lightning/src/routing/router.rs | 168 ++++++++++++++++++++++++------- lightning/src/util/test_utils.rs | 4 + 3 files changed, 145 insertions(+), 43 deletions(-) diff --git a/lightning/src/routing/gossip.rs b/lightning/src/routing/gossip.rs index 5a5379dde..a18f4ca2e 100644 --- a/lightning/src/routing/gossip.rs +++ b/lightning/src/routing/gossip.rs @@ -1102,6 +1102,14 @@ impl<'a> DirectedChannelInfo<'a> { /// Refers to the `node_id` receiving the payment from the previous hop. #[inline] pub fn target(&self) -> &'a NodeId { if self.from_node_one { &self.channel.node_two } else { &self.channel.node_one } } + + /// Returns the source node's counter + #[inline] + pub(super) fn source_counter(&self) -> u32 { if self.from_node_one { self.channel.node_one_counter } else { self.channel.node_two_counter } } + + /// Returns the target node's counter + #[inline] + pub(super) fn target_counter(&self) -> u32 { if self.from_node_one { self.channel.node_two_counter } else { self.channel.node_one_counter } } } impl<'a> fmt::Debug for DirectedChannelInfo<'a> { @@ -1854,21 +1862,21 @@ impl NetworkGraph where L::Target: Logger { (&mut channel_info.node_one_counter, node_id_a), (&mut channel_info.node_two_counter, node_id_b) ]; - for (node_counter, current_node_id) in node_counter_id.iter_mut() { + for (chan_info_node_counter, current_node_id) in node_counter_id.iter_mut() { match nodes.entry(current_node_id.clone()) { IndexedMapEntry::Occupied(node_entry) => { let node = node_entry.into_mut(); node.channels.push(short_channel_id); - **node_counter = node.node_counter; + **chan_info_node_counter = node.node_counter; }, IndexedMapEntry::Vacant(node_entry) => { let mut removed_node_counters = self.removed_node_counters.lock().unwrap(); - **node_counter = removed_node_counters.pop() + **chan_info_node_counter = removed_node_counters.pop() .unwrap_or(self.next_node_counter.fetch_add(1, Ordering::Relaxed) as u32); node_entry.insert(NodeInfo { channels: vec!(short_channel_id), announcement_info: None, - node_counter: **node_counter, + node_counter: **chan_info_node_counter, }); } }; diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs index 0e60d3e33..4c560969e 100644 --- a/lightning/src/routing/router.rs +++ b/lightning/src/routing/router.rs @@ -1188,6 +1188,20 @@ pub struct FirstHopCandidate<'a> { /// /// This is not exported to bindings users as lifetimes are not expressible in most languages. pub payer_node_id: &'a NodeId, + /// A unique ID which describes the payer. + /// + /// It will not conflict with any [`NodeInfo::node_counter`]s, but may be equal to one if the + /// payer is a public node. + /// + /// [`NodeInfo::node_counter`]: super::gossip::NodeInfo::node_counter + pub(crate) payer_node_counter: u32, + /// A unique ID which describes the first hop counterparty. + /// + /// It will not conflict with any [`NodeInfo::node_counter`]s, but may be equal to one if the + /// counterparty is a public node. + /// + /// [`NodeInfo::node_counter`]: super::gossip::NodeInfo::node_counter + pub(crate) target_node_counter: u32, } /// A [`CandidateRouteHop::PublicHop`] entry. @@ -1213,7 +1227,21 @@ pub struct PrivateHopCandidate<'a> { /// Node id of the next hop in BOLT 11 route hint. /// /// This is not exported to bindings users as lifetimes are not expressible in most languages. - pub target_node_id: &'a NodeId + pub target_node_id: &'a NodeId, + /// A unique ID which describes the source node of the hop (further from the payment target). + /// + /// It will not conflict with any [`NodeInfo::node_counter`]s, but may be equal to one if the + /// node is a public node. + /// + /// [`NodeInfo::node_counter`]: super::gossip::NodeInfo::node_counter + pub(crate) source_node_counter: u32, + /// A unique ID which describes the destination node of the hop (towards the payment target). + /// + /// It will not conflict with any [`NodeInfo::node_counter`]s, but may be equal to one if the + /// node is a public node. + /// + /// [`NodeInfo::node_counter`]: super::gossip::NodeInfo::node_counter + pub(crate) target_node_counter: u32, } /// A [`CandidateRouteHop::Blinded`] entry. @@ -1234,6 +1262,13 @@ pub struct BlindedPathCandidate<'a> { /// 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, + /// A unique ID which describes the introduction point of the blinded path. + /// + /// It will not conflict with any [`NodeInfo::node_counter`]s, but will generally be equal to + /// one from the public network graph (assuming the introduction point is a public node). + /// + /// [`NodeInfo::node_counter`]: super::gossip::NodeInfo::node_counter + source_node_counter: u32, } /// A [`CandidateRouteHop::OneHopBlinded`] entry. @@ -1256,6 +1291,13 @@ pub struct OneHopBlindedPathCandidate<'a> { /// 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, + /// A unique ID which describes the introduction point of the blinded path. + /// + /// It will not conflict with any [`NodeInfo::node_counter`]s, but will generally be equal to + /// one from the public network graph (assuming the introduction point is a public node). + /// + /// [`NodeInfo::node_counter`]: super::gossip::NodeInfo::node_counter + source_node_counter: u32, } /// A wrapper around the various hop representations. @@ -1378,6 +1420,28 @@ impl<'a> CandidateRouteHop<'a> { } } + #[inline] + fn src_node_counter(&self) -> u32 { + match self { + CandidateRouteHop::FirstHop(hop) => hop.payer_node_counter, + CandidateRouteHop::PublicHop(hop) => hop.info.source_counter(), + CandidateRouteHop::PrivateHop(hop) => hop.source_node_counter, + CandidateRouteHop::Blinded(hop) => hop.source_node_counter, + CandidateRouteHop::OneHopBlinded(hop) => hop.source_node_counter, + } + } + + #[inline] + fn target_node_counter(&self) -> Option { + match self { + CandidateRouteHop::FirstHop(hop) => Some(hop.target_node_counter), + CandidateRouteHop::PublicHop(hop) => Some(hop.info.target_counter()), + CandidateRouteHop::PrivateHop(hop) => Some(hop.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 { @@ -1667,12 +1731,13 @@ 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()); @@ -2110,7 +2175,7 @@ where L::Target: Logger { // // First cache all our direct channels so that we can insert them in the heap at startup. // Then process any blinded routes, resolving their introduction node and caching it. - let mut first_hop_targets: HashMap<_, Vec<&ChannelDetails>> = + let mut first_hop_targets: HashMap<_, (Vec<&ChannelDetails>, u32)> = hash_map_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 { @@ -2125,10 +2190,10 @@ where L::Target: Logger { .entry(counterparty_id) .or_insert_with(|| { // Make sure there's a counter assigned for the counterparty - node_counter_builder.select_node_counter_for_id(counterparty_id); - Vec::new() + let node_counter = node_counter_builder.select_node_counter_for_id(counterparty_id); + (Vec::new(), node_counter) }) - .push(chan); + .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}); @@ -2149,7 +2214,7 @@ where L::Target: Logger { path.public_introduction_node_id(network_graph) .map(|node_id_ref| *node_id_ref) .or_else(|| { - first_hop_targets.iter().find(|(_, channels)| + first_hop_targets.iter().find(|(_, (channels, _))| channels .iter() .any(|details| Some(*scid) == details.get_outbound_payment_scid()) @@ -2206,7 +2271,8 @@ where L::Target: Logger { // Map from node_id to information about the best current path to that node, including feerate // information. - let mut dist: HashMap = hash_map_with_capacity(network_nodes.len()); + let dist_len = node_counters.max_counter() + 1; + let mut dist: Vec> = vec![None; dist_len as usize]; // 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 @@ -2253,7 +2319,7 @@ where L::Target: Logger { // 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); } @@ -2413,14 +2479,17 @@ where L::Target: Logger { ); 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[$candidate.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(), fee_msat: 0, next_hops_fee_msat: u64::max_value(), @@ -2431,8 +2500,9 @@ where L::Target: Logger { was_processed: 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; @@ -2591,7 +2661,7 @@ where L::Target: Logger { let fee_to_target_msat; let next_hops_path_htlc_minimum_msat; let next_hops_path_penalty_msat; - let skip_node = if let Some(elem) = dist.get_mut(&$node_id) { + 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; @@ -2603,6 +2673,7 @@ where L::Target: Logger { // 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; @@ -2610,10 +2681,12 @@ where L::Target: Logger { }; if !skip_node { - if let Some(first_channels) = first_hop_targets.get(&$node_id) { + 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(FirstHopCandidate { - details, payer_node_id: &our_node_id, + 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, @@ -2662,15 +2735,19 @@ where L::Target: Logger { // 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; + } 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(FirstHopCandidate { - 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(); @@ -2706,14 +2783,14 @@ where L::Target: Logger { // we have a direct channel to the first hop or the first hop is // in the regular network graph. let source_node_opt = introduction_node_id_cache[hint_idx]; - let (source_node_id, _source_node_counter) = if let Some(v) = source_node_opt { v } else { continue }; + let (source_node_id, source_node_counter) = if let Some(v) = source_node_opt { v } else { continue }; if our_node_id == *source_node_id { continue } let candidate = if hint.1.blinded_hops.len() == 1 { CandidateRouteHop::OneHopBlinded( - OneHopBlindedPathCandidate { source_node_id, hint, hint_idx } + OneHopBlindedPathCandidate { source_node_counter, source_node_id, hint, hint_idx } ) } else { - CandidateRouteHop::Blinded(BlindedPathCandidate { source_node_id, hint, hint_idx }) + CandidateRouteHop::Blinded(BlindedPathCandidate { source_node_counter, source_node_id, hint, hint_idx }) }; let mut path_contribution_msat = path_value_msat; if let Some(hop_used_msat) = add_entry!(&candidate, @@ -2721,13 +2798,14 @@ where L::Target: Logger { { path_contribution_msat = hop_used_msat; } else { continue } - if let Some(first_channels) = first_hop_targets.get_mut(source_node_id) { + if let Some((first_channels, peer_node_counter)) = first_hop_targets.get_mut(source_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(FirstHopCandidate { - 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, @@ -2766,11 +2844,14 @@ where L::Target: Logger { 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_target_node_counter) = + let (target, private_target_node_counter) = node_counters.private_node_counter_from_pubkey(&prev_hop_id) + .expect("node_counter_from_pubkey is called on all unblinded_route_hints keys during setup, so is always Some here"); + let (_src_id, private_source_node_counter) = + node_counters.private_node_counter_from_pubkey(&hop.src_node_id) .expect("node_counter_from_pubkey is called on all unblinded_route_hints keys during setup, so is always Some here"); - 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); @@ -2785,7 +2866,11 @@ where L::Target: Logger { info, short_channel_id: hop.short_channel_id, })) - .unwrap_or_else(|| CandidateRouteHop::PrivateHop(PrivateHopCandidate { hint: hop, target_node_id: target })); + .unwrap_or_else(|| CandidateRouteHop::PrivateHop(PrivateHopCandidate { + 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, @@ -2821,13 +2906,14 @@ where L::Target: Logger { .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(FirstHopCandidate { - 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, @@ -2869,13 +2955,14 @@ where L::Target: Logger { // 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(FirstHopCandidate { - 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, @@ -2911,16 +2998,18 @@ where L::Target: Logger { // 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(FirstHopCandidate { details: last_hop_details, .. }) - = ordered_hops.last().unwrap().0.candidate + = candidate { if details.get_outbound_payment_scid() == last_hop_details.get_outbound_payment_scid() { ordered_hops.last_mut().unwrap().1 = details.counterparty.features.to_context(); @@ -2948,11 +3037,12 @@ where L::Target: Logger { // 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!). diff --git a/lightning/src/util/test_utils.rs b/lightning/src/util/test_utils.rs index f6616a8e5..d9da01fee 100644 --- a/lightning/src/util/test_utils.rs +++ b/lightning/src/util/test_utils.rs @@ -177,6 +177,8 @@ impl<'a> Router for TestRouter<'a> { let candidate = CandidateRouteHop::FirstHop(FirstHopCandidate { details: first_hops[idx], payer_node_id: &node_id, + payer_node_counter: u32::max_value(), + target_node_counter: u32::max_value(), }); scorer.channel_penalty_msat(&candidate, usage, &Default::default()); continue; @@ -204,6 +206,8 @@ impl<'a> Router for TestRouter<'a> { let candidate = CandidateRouteHop::PrivateHop(PrivateHopCandidate { hint: &route_hint, target_node_id: &target_node_id, + source_node_counter: u32::max_value(), + target_node_counter: u32::max_value(), }); scorer.channel_penalty_msat(&candidate, usage, &Default::default()); } -- 2.39.5