From 5b7f0a287d0ab1129e205c4455689835929518ab Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Tue, 19 Mar 2024 22:26:37 +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 | 8 ++ lightning/src/routing/router.rs | 191 ++++++++++++++++++++++--------- lightning/src/util/test_utils.rs | 4 + 3 files changed, 149 insertions(+), 54 deletions(-) diff --git a/lightning/src/routing/gossip.rs b/lightning/src/routing/gossip.rs index f7fbff67..40e2619e 100644 --- a/lightning/src/routing/gossip.rs +++ b/lightning/src/routing/gossip.rs @@ -1063,6 +1063,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> { diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs index 5c793df5..3b81e594 100644 --- a/lightning/src/routing/router.rs +++ b/lightning/src/routing/router.rs @@ -1150,6 +1150,14 @@ pub struct FirstHopCandidate<'a> { /// /// This is not exported to bindings users as lifetimes are not expressable in most languages. pub payer_node_id: &'a NodeId, + /// A unique ID which describes the payer. It will not conlfict with any + /// [`super::gossip::NodeInfo::node_counter`]s, but may be equal to one if the payer is a + /// public node. + pub(crate) payer_node_counter: u32, + /// A unique ID which describes the first hop counterparty. It will not conflict with any + /// [`super::gossip::NodeInfo::node_counter`]s, but may be equal to one if the counterparty is + /// a public node. + pub(crate) target_node_counter: u32, } /// A [`CandidateRouteHop::PublicHop`] entry. @@ -1175,7 +1183,15 @@ 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 expressable 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 [`super::gossip::NodeInfo::node_counter`]s, but may be equal + /// to one if the node is a public node. + 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 [`super::gossip::NodeInfo::node_counter`]s, but may be equal + /// to one if the node is a public node. + pub(crate) target_node_counter: u32, } /// A [`CandidateRouteHop::Blinded`] entry. @@ -1191,6 +1207,11 @@ 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 [`super::gossip::NodeInfo::node_counter`]s, but will generally + /// be equal to one from the public network graph (assuming the introduction point is a public + /// node). + source_node_counter: u32, } /// A [`CandidateRouteHop::OneHopBlinded`] entry. @@ -1208,6 +1229,11 @@ 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 [`super::gossip::NodeInfo::node_counter`]s, but will generally + /// be equal to one from the public network graph (assuming the introduction point is a public + /// node). + source_node_counter: u32, } /// A wrapper around the various hop representations. @@ -1330,6 +1356,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 { @@ -1555,6 +1603,7 @@ fn iter_equal(mut iter_a: I1, mut iter_b: I2) #[repr(C)] // Force fields to appear in the order we define them. struct PathBuildingHop<'a> { candidate: CandidateRouteHop<'a>, + target_node_counter: Option, /// 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 @@ -1610,12 +1659,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()); @@ -2051,7 +2101,7 @@ where L::Target: Logger { // 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)> = 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 { @@ -2061,29 +2111,21 @@ where L::Target: Logger { 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 = node_counters.node_counter_from_id(counterparty_node_id); + (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 = hash_map_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)); - } - } + let node_counters = node_counters.build(); // 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 @@ -2092,7 +2134,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 @@ -2139,7 +2182,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); } @@ -2310,15 +2353,19 @@ 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 mut 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(), @@ -2328,8 +2375,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; @@ -2411,6 +2459,7 @@ where L::Target: Logger { 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; @@ -2488,7 +2537,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; @@ -2500,6 +2549,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; @@ -2507,10 +2557,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, @@ -2559,15 +2611,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(); @@ -2595,28 +2651,41 @@ where L::Target: Logger { // 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(OneHopBlindedPathCandidate { hint, hint_idx }) - } else { CandidateRouteHop::Blinded(BlindedPathCandidate { hint, hint_idx }) }; + CandidateRouteHop::OneHopBlinded(OneHopBlindedPathCandidate { + hint, + hint_idx, + source_node_counter: intro_node_counter_opt.unwrap(), + }) + } else { + CandidateRouteHop::Blinded(BlindedPathCandidate { + 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(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, @@ -2656,9 +2725,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_hop_key_cache.get(prev_hop_id).unwrap(); - - if let Some(first_channels) = first_hop_targets.get(target) { + let (target, private_target_node_counter) = + node_counters.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.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 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); @@ -2673,7 +2747,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, @@ -2709,12 +2787,13 @@ 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, @@ -2756,12 +2835,13 @@ 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, @@ -2797,13 +2877,15 @@ 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 @@ -2834,11 +2916,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 15cc0746..6ad2e76d 100644 --- a/lightning/src/util/test_utils.rs +++ b/lightning/src/util/test_utils.rs @@ -169,6 +169,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; @@ -196,6 +198,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.30.2