X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Frouter.rs;h=a6e9a34d8859cdd22091d39954cf4cbd387d2c71;hb=31cbe17ff9d2be628495bb3806dfc4c3de028347;hp=f64d2e4fec9071e5d6db10818c4e838a00eef604;hpb=df45cd5165630731ace4bb887fc92814da5766b3;p=rust-lightning diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs index f64d2e4fe..a6e9a34d8 100644 --- a/lightning/src/routing/router.rs +++ b/lightning/src/routing/router.rs @@ -997,12 +997,7 @@ impl cmp::PartialOrd for RouteGraphNode { // While RouteGraphNode can be laid out with fewer bytes, performance appears to be improved // substantially when it is laid out at exactly 64 bytes. -// -// Thus, we use `#[repr(C)]` on the struct to force a suboptimal layout and check that it stays 64 -// bytes here. -#[cfg(any(ldk_bench, not(any(test, fuzzing))))] const _GRAPH_NODE_SMALL: usize = 64 - core::mem::size_of::(); -#[cfg(any(ldk_bench, not(any(test, fuzzing))))] const _GRAPH_NODE_FIXED_SIZE: usize = core::mem::size_of::() - 64; /// A wrapper around the various hop representations. @@ -1179,7 +1174,7 @@ impl<'a> CandidateRouteHop<'a> { } } - #[inline] + #[inline(always)] fn src_node_counter(&self) -> u32 { match self { CandidateRouteHop::FirstHop { payer_node_counter, .. } => *payer_node_counter, @@ -1346,7 +1341,7 @@ fn iter_equal(mut iter_a: I1, mut iter_b: I2) /// 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(C)] // Force fields to appear in the order we define them. +#[repr(align(128))] struct PathBuildingHop<'a> { candidate: CandidateRouteHop<'a>, target_node_counter: Option, @@ -1356,6 +1351,8 @@ struct PathBuildingHop<'a> { /// 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. @@ -1368,11 +1365,6 @@ struct PathBuildingHop<'a> { /// channel scoring. path_penalty_msat: u64, - // The last 16 bytes are on the next cache line by default in glibc's malloc. Thus, we should - // only place fields which are not hot there. Luckily, the next three fields are only read if - // we end up on the selected path, and only in the final path layout phase, so we don't care - // too much if reading them is slow. - fee_msat: u64, /// All the fees paid *after* this channel on the way to the destination @@ -1389,17 +1381,8 @@ struct PathBuildingHop<'a> { 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::>(); +const _NODE_MAP_SIZE_EXACTLY_TWO_CACHE_LINES: usize = core::mem::size_of::>() - 128; impl<'a> core::fmt::Debug for PathBuildingHop<'a> { fn fmt(&self, f: &mut core::fmt::Formatter) -> Result<(), core::fmt::Error> { @@ -2005,6 +1988,8 @@ where L::Target: Logger { // 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| { @@ -2027,7 +2012,7 @@ where L::Target: Logger { .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); @@ -2038,13 +2023,13 @@ where L::Target: Logger { 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)); @@ -2119,13 +2104,15 @@ where L::Target: Logger { // 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 dist_entry = &mut dist[$candidate.src_node_counter() as usize]; - let mut old_entry = if let Some(hop) = dist_entry { + 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 @@ -2143,6 +2130,7 @@ where L::Target: Logger { 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, }); @@ -2167,7 +2155,7 @@ where L::Target: Logger { 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); } @@ -2307,12 +2295,14 @@ where L::Target: Logger { 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. @@ -2323,21 +2313,24 @@ where L::Target: Logger { 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, 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); + 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); + } } } @@ -2384,6 +2377,33 @@ where L::Target: Logger { 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 @@ -8557,14 +8577,23 @@ pub mod benches { 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( + 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()];