use crate::ln::channelmanager::{ChannelDetails, PaymentId};
use crate::ln::features::{Bolt12InvoiceFeatures, ChannelFeatures, InvoiceFeatures, NodeFeatures};
use crate::ln::msgs::{DecodeError, ErrorAction, LightningError, MAX_VALUE_MSAT};
-use crate::offers::invoice::BlindedPayInfo;
+use crate::offers::invoice::{BlindedPayInfo, Invoice as Bolt12Invoice};
use crate::routing::gossip::{DirectedChannelInfo, EffectiveCapacity, ReadOnlyNetworkGraph, NetworkGraph, NodeId, RoutingFees};
use crate::routing::scoring::{ChannelUsage, LockableScore, Score};
use crate::util::ser::{Writeable, Readable, ReadableArgs, Writer};
///
/// The `final_cltv_expiry_delta` should match the expected final CLTV delta the recipient has
/// provided.
- pub fn for_keysend(payee_pubkey: PublicKey, final_cltv_expiry_delta: u32) -> Self {
- Self::from_node_id(payee_pubkey, final_cltv_expiry_delta).with_bolt11_features(InvoiceFeatures::for_keysend()).expect("PaymentParameters::from_node_id should always initialize the payee as unblinded")
+ ///
+ /// Note that MPP keysend is not widely supported yet. The `allow_mpp` lets you choose
+ /// whether your router will be allowed to find a multi-part route for this payment. If you
+ /// set `allow_mpp` to true, you should ensure a payment secret is set on send, likely via
+ /// [`RecipientOnionFields::secret_only`].
+ ///
+ /// [`RecipientOnionFields::secret_only`]: crate::ln::channelmanager::RecipientOnionFields::secret_only
+ pub fn for_keysend(payee_pubkey: PublicKey, final_cltv_expiry_delta: u32, allow_mpp: bool) -> Self {
+ Self::from_node_id(payee_pubkey, final_cltv_expiry_delta)
+ .with_bolt11_features(InvoiceFeatures::for_keysend(allow_mpp))
+ .expect("PaymentParameters::from_node_id should always initialize the payee as unblinded")
+ }
+
+ /// Creates parameters for paying to a blinded payee from the provided invoice. Sets
+ /// [`Payee::Blinded::route_hints`], [`Payee::Blinded::features`], and
+ /// [`PaymentParameters::expiry_time`].
+ pub fn from_bolt12_invoice(invoice: &Bolt12Invoice) -> Self {
+ Self::blinded(invoice.payment_paths().to_vec())
+ .with_bolt12_features(invoice.features().clone()).unwrap()
+ .with_expiry_time(invoice.created_at().as_secs().saturating_add(invoice.relative_expiry().as_secs()))
+ }
+
+ fn blinded(blinded_route_hints: Vec<(BlindedPayInfo, BlindedPath)>) -> Self {
+ Self {
+ payee: Payee::Blinded { route_hints: blinded_route_hints, features: None },
+ expiry_time: None,
+ max_total_cltv_expiry_delta: DEFAULT_MAX_TOTAL_CLTV_EXPIRY_DELTA,
+ max_path_count: DEFAULT_MAX_PATH_COUNT,
+ max_channel_saturation_power_of_half: 2,
+ previously_failed_channels: Vec::new(),
+ }
+ }
+
+ /// Includes the payee's features. Errors if the parameters were not initialized with
+ /// [`PaymentParameters::from_bolt12_invoice`].
+ ///
+ /// This is not exported to bindings users since bindings don't support move semantics
+ pub fn with_bolt12_features(self, features: Bolt12InvoiceFeatures) -> Result<Self, ()> {
+ match self.payee {
+ Payee::Clear { .. } => Err(()),
+ Payee::Blinded { route_hints, .. } =>
+ Ok(Self { payee: Payee::Blinded { route_hints, features: Some(features) }, ..self })
+ }
}
- /// Includes the payee's features. Errors if the parameters were initialized with blinded payment
- /// paths.
+ /// Includes the payee's features. Errors if the parameters were initialized with
+ /// [`PaymentParameters::from_bolt12_invoice`].
///
/// This is not exported to bindings users since bindings don't support move semantics
pub fn with_bolt11_features(self, features: InvoiceFeatures) -> Result<Self, ()> {
}
/// Includes hints for routing to the payee. Errors if the parameters were initialized with
- /// blinded payment paths.
+ /// [`PaymentParameters::from_bolt12_invoice`].
///
/// This is not exported to bindings users since bindings don't support move semantics
pub fn with_route_hints(self, route_hints: Vec<RouteHint>) -> Result<Self, ()> {
Self { max_path_count, ..self }
}
- /// Includes a limit for the maximum number of payment paths that may be used.
+ /// Includes a limit for the maximum share of a channel's total capacity that can be sent over, as
+ /// a power of 1/2. See [`PaymentParameters::max_channel_saturation_power_of_half`].
///
/// This is not exported to bindings users since bindings don't support move semantics
pub fn with_max_channel_saturation_power_of_half(self, max_channel_saturation_power_of_half: u8) -> Self {
fn htlc_minimum_msat(&self) -> u64 {
match self {
- CandidateRouteHop::FirstHop { .. } => 0,
+ CandidateRouteHop::FirstHop { details } => details.next_outbound_htlc_minimum_msat,
CandidateRouteHop::PublicHop { info, .. } => info.direction().htlc_minimum_msat,
CandidateRouteHop::PrivateHop { hint } => hint.htlc_minimum_msat.unwrap_or(0),
}
/// decrease as well. Thus, we have to explicitly track which nodes have been processed and
/// avoid processing them again.
was_processed: bool,
- #[cfg(all(not(feature = "_bench_unstable"), any(test, fuzzing)))]
+ #[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, which requires tracking it here. See comments below where it is
.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());
- #[cfg(all(not(feature = "_bench_unstable"), any(test, fuzzing)))]
+ #[cfg(all(not(ldk_bench), any(test, fuzzing)))]
let debug_struct = debug_struct
.field("value_contribution_msat", &self.value_contribution_msat);
debug_struct.finish()
}
}
+#[inline]
+fn sort_first_hop_channels(
+ channels: &mut Vec<&ChannelDetails>, used_channel_liquidities: &HashMap<(u64, bool), u64>,
+ recommended_value_msat: u64, our_node_pubkey: &PublicKey
+) {
+ // Sort the first_hops channels to the same node(s) in priority order of which channel we'd
+ // most like to use.
+ //
+ // First, if channels are below `recommended_value_msat`, sort them in descending order,
+ // preferring larger channels to avoid splitting the payment into more MPP parts than is
+ // required.
+ //
+ // Second, because simply always sorting in descending order would always use our largest
+ // available outbound capacity, needlessly fragmenting our available channel capacities,
+ // sort channels above `recommended_value_msat` in ascending order, preferring channels
+ // which have enough, but not too much, capacity for the payment.
+ //
+ // Available outbound balances factor in liquidity already reserved for previously found paths.
+ channels.sort_unstable_by(|chan_a, chan_b| {
+ let chan_a_outbound_limit_msat = chan_a.next_outbound_htlc_limit_msat
+ .saturating_sub(*used_channel_liquidities.get(&(chan_a.get_outbound_payment_scid().unwrap(),
+ our_node_pubkey < &chan_a.counterparty.node_id)).unwrap_or(&0));
+ let chan_b_outbound_limit_msat = chan_b.next_outbound_htlc_limit_msat
+ .saturating_sub(*used_channel_liquidities.get(&(chan_b.get_outbound_payment_scid().unwrap(),
+ our_node_pubkey < &chan_b.counterparty.node_id)).unwrap_or(&0));
+ if chan_b_outbound_limit_msat < recommended_value_msat || chan_a_outbound_limit_msat < recommended_value_msat {
+ // Sort in descending order
+ chan_b_outbound_limit_msat.cmp(&chan_a_outbound_limit_msat)
+ } else {
+ // Sort in ascending order
+ chan_a_outbound_limit_msat.cmp(&chan_b_outbound_limit_msat)
+ }
+ });
+}
+
/// Finds a route from us (payer) to the given target node (payee).
///
/// If the payee provided features in their invoice, they should be provided via `params.payee`.
// unblinded payee id as an option. We also need a non-optional "payee id" for path construction,
// so use a dummy id for this in the blinded case.
let payee_node_id_opt = payment_params.payee.node_id().map(|pk| NodeId::from_pubkey(&pk));
- const DUMMY_BLINDED_PAYEE_ID: [u8; 33] = [42u8; 33];
+ const DUMMY_BLINDED_PAYEE_ID: [u8; 33] = [2; 33];
let maybe_dummy_payee_pk = payment_params.payee.node_id().unwrap_or_else(|| PublicKey::from_slice(&DUMMY_BLINDED_PAYEE_ID).unwrap());
let maybe_dummy_payee_node_id = NodeId::from_pubkey(&maybe_dummy_payee_pk);
let our_node_id = NodeId::from_pubkey(&our_node_pubkey);
let mut already_collected_value_msat = 0;
for (_, channels) in first_hop_targets.iter_mut() {
- // Sort the first_hops channels to the same node(s) in priority order of which channel we'd
- // most like to use.
- //
- // First, if channels are below `recommended_value_msat`, sort them in descending order,
- // preferring larger channels to avoid splitting the payment into more MPP parts than is
- // required.
- //
- // Second, because simply always sorting in descending order would always use our largest
- // available outbound capacity, needlessly fragmenting our available channel capacities,
- // sort channels above `recommended_value_msat` in ascending order, preferring channels
- // which have enough, but not too much, capacity for the payment.
- channels.sort_unstable_by(|chan_a, chan_b| {
- if chan_b.next_outbound_htlc_limit_msat < recommended_value_msat || chan_a.next_outbound_htlc_limit_msat < recommended_value_msat {
- // Sort in descending order
- chan_b.next_outbound_htlc_limit_msat.cmp(&chan_a.next_outbound_htlc_limit_msat)
- } else {
- // Sort in ascending order
- chan_a.next_outbound_htlc_limit_msat.cmp(&chan_b.next_outbound_htlc_limit_msat)
- }
- });
+ sort_first_hop_channels(channels, &used_channel_liquidities, recommended_value_msat,
+ our_node_pubkey);
}
log_trace!(logger, "Building path from {} to payer {} for value {} msat.",
path_htlc_minimum_msat,
path_penalty_msat: u64::max_value(),
was_processed: false,
- #[cfg(all(not(feature = "_bench_unstable"), any(test, fuzzing)))]
+ #[cfg(all(not(ldk_bench), any(test, fuzzing)))]
value_contribution_msat,
}
});
#[allow(unused_mut)] // We only use the mut in cfg(test)
let mut should_process = !old_entry.was_processed;
- #[cfg(all(not(feature = "_bench_unstable"), any(test, fuzzing)))]
+ #[cfg(all(not(ldk_bench), any(test, fuzzing)))]
{
// In test/fuzzing builds, we do extra checks to make sure the skipping
// of already-seen nodes only happens in cases we expect (see below).
old_entry.fee_msat = 0; // This value will be later filled with hop_use_fee_msat of the following channel
old_entry.path_htlc_minimum_msat = path_htlc_minimum_msat;
old_entry.path_penalty_msat = path_penalty_msat;
- #[cfg(all(not(feature = "_bench_unstable"), any(test, fuzzing)))]
+ #[cfg(all(not(ldk_bench), any(test, fuzzing)))]
{
old_entry.value_contribution_msat = value_contribution_msat;
}
did_add_update_path_to_src_node = Some(value_contribution_msat);
} else if old_entry.was_processed && new_cost < old_cost {
- #[cfg(all(not(feature = "_bench_unstable"), any(test, fuzzing)))]
+ #[cfg(all(not(ldk_bench), any(test, fuzzing)))]
{
// If we're skipping processing a node which was previously
// processed even though we found another path to it with a
.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(&NodeId::from_pubkey(&prev_hop_id)) {
+ if let Some(first_channels) = first_hop_targets.get_mut(&NodeId::from_pubkey(&prev_hop_id)) {
+ sort_first_hop_channels(first_channels, &used_channel_liquidities,
+ recommended_value_msat, our_node_pubkey);
for details in first_channels {
let first_hop_candidate = CandidateRouteHop::FirstHop { details };
add_entry!(first_hop_candidate, our_node_id, NodeId::from_pubkey(&prev_hop_id),
// 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(&NodeId::from_pubkey(&hop.src_node_id)) {
+ if let Some(first_channels) = first_hop_targets.get_mut(&NodeId::from_pubkey(&hop.src_node_id)) {
+ sort_first_hop_channels(first_channels, &used_channel_liquidities,
+ recommended_value_msat, our_node_pubkey);
for details in first_channels {
let first_hop_candidate = CandidateRouteHop::FirstHop { details };
add_entry!(first_hop_candidate, our_node_id,
balance_msat: 0,
outbound_capacity_msat,
next_outbound_htlc_limit_msat: outbound_capacity_msat,
+ next_outbound_htlc_minimum_msat: 0,
inbound_capacity_msat: 42,
unspendable_punishment_reserve: None,
confirmations_required: None,
println!("Using seed of {}", seed);
seed
}
- #[cfg(not(feature = "no-std"))]
- use crate::util::ser::ReadableArgs;
#[test]
#[cfg(not(feature = "no-std"))]
fn generate_routes() {
use crate::routing::scoring::{ProbabilisticScorer, ProbabilisticScoringFeeParameters};
- let mut d = match super::bench_utils::get_route_file() {
+ let logger = ln_test_utils::TestLogger::new();
+ let graph = match super::bench_utils::read_network_graph(&logger) {
Ok(f) => f,
Err(e) => {
eprintln!("{}", e);
return;
},
};
- let logger = ln_test_utils::TestLogger::new();
- let graph = NetworkGraph::read(&mut d, &logger).unwrap();
- let keys_manager = ln_test_utils::TestKeysInterface::new(&[0u8; 32], Network::Testnet);
- let random_seed_bytes = keys_manager.get_secure_random_bytes();
- // First, get 100 (source, destination) pairs for which route-getting actually succeeds...
- let mut seed = random_init_seed() as usize;
- let nodes = graph.read_only().nodes().clone();
- 'load_endpoints: for _ in 0..10 {
- loop {
- seed = seed.overflowing_mul(0xdeadbeef).0;
- let src = &PublicKey::from_slice(nodes.unordered_keys().skip(seed % nodes.len()).next().unwrap().as_slice()).unwrap();
- seed = seed.overflowing_mul(0xdeadbeef).0;
- let dst = PublicKey::from_slice(nodes.unordered_keys().skip(seed % nodes.len()).next().unwrap().as_slice()).unwrap();
- let payment_params = PaymentParameters::from_node_id(dst, 42);
- let amt = seed as u64 % 200_000_000;
- let params = ProbabilisticScoringFeeParameters::default();
- let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &graph, &logger);
- if get_route(src, &payment_params, &graph.read_only(), None, amt, &logger, &scorer, ¶ms, &random_seed_bytes).is_ok() {
- continue 'load_endpoints;
- }
- }
- }
+ let params = ProbabilisticScoringFeeParameters::default();
+ let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &graph, &logger);
+ let features = super::InvoiceFeatures::empty();
+
+ super::bench_utils::generate_test_routes(&graph, &mut scorer, ¶ms, features, random_init_seed(), 0, 2);
}
#[test]
fn generate_routes_mpp() {
use crate::routing::scoring::{ProbabilisticScorer, ProbabilisticScoringFeeParameters};
- let mut d = match super::bench_utils::get_route_file() {
+ let logger = ln_test_utils::TestLogger::new();
+ let graph = match super::bench_utils::read_network_graph(&logger) {
Ok(f) => f,
Err(e) => {
eprintln!("{}", e);
return;
},
};
+
+ let params = ProbabilisticScoringFeeParameters::default();
+ let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &graph, &logger);
+ let features = channelmanager::provided_invoice_features(&UserConfig::default());
+
+ super::bench_utils::generate_test_routes(&graph, &mut scorer, ¶ms, features, random_init_seed(), 0, 2);
+ }
+
+ #[test]
+ #[cfg(not(feature = "no-std"))]
+ fn generate_large_mpp_routes() {
+ use crate::routing::scoring::{ProbabilisticScorer, ProbabilisticScoringFeeParameters};
+
let logger = ln_test_utils::TestLogger::new();
- let graph = NetworkGraph::read(&mut d, &logger).unwrap();
- let keys_manager = ln_test_utils::TestKeysInterface::new(&[0u8; 32], Network::Testnet);
- let random_seed_bytes = keys_manager.get_secure_random_bytes();
- let config = UserConfig::default();
+ let graph = match super::bench_utils::read_network_graph(&logger) {
+ Ok(f) => f,
+ Err(e) => {
+ eprintln!("{}", e);
+ return;
+ },
+ };
- // First, get 100 (source, destination) pairs for which route-getting actually succeeds...
- let mut seed = random_init_seed() as usize;
- let nodes = graph.read_only().nodes().clone();
- 'load_endpoints: for _ in 0..10 {
- loop {
- seed = seed.overflowing_mul(0xdeadbeef).0;
- let src = &PublicKey::from_slice(nodes.unordered_keys().skip(seed % nodes.len()).next().unwrap().as_slice()).unwrap();
- seed = seed.overflowing_mul(0xdeadbeef).0;
- let dst = PublicKey::from_slice(nodes.unordered_keys().skip(seed % nodes.len()).next().unwrap().as_slice()).unwrap();
- let payment_params = PaymentParameters::from_node_id(dst, 42).with_bolt11_features(channelmanager::provided_invoice_features(&config)).unwrap();
- let amt = seed as u64 % 200_000_000;
- let params = ProbabilisticScoringFeeParameters::default();
- let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &graph, &logger);
- if get_route(src, &payment_params, &graph.read_only(), None, amt, &logger, &scorer, ¶ms, &random_seed_bytes).is_ok() {
- continue 'load_endpoints;
- }
- }
- }
+ let params = ProbabilisticScoringFeeParameters::default();
+ let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &graph, &logger);
+ let features = channelmanager::provided_invoice_features(&UserConfig::default());
+
+ super::bench_utils::generate_test_routes(&graph, &mut scorer, ¶ms, features, random_init_seed(), 1_000_000, 2);
}
#[test]
let route = get_route(&our_node_id, &payment_params, &network_graph.read_only(),
Some(&first_hops.iter().collect::<Vec<_>>()), amt_msat, Arc::clone(&logger), &scorer, &(),
&random_seed_bytes).unwrap();
- // TODO: `get_route` returns a suboptimal route here because first hop channels are not
- // resorted on the fly when processing route hints.
- assert_eq!(route.paths.len(), 3);
+ assert_eq!(route.paths.len(), 2);
assert!(route.paths[0].hops.last().unwrap().fee_msat <= max_htlc_msat);
assert!(route.paths[1].hops.last().unwrap().fee_msat <= max_htlc_msat);
- assert!(route.paths[2].hops.last().unwrap().fee_msat <= max_htlc_msat);
assert_eq!(route.get_total_amount(), amt_msat);
}
}
}
-#[cfg(all(test, not(feature = "no-std")))]
+#[cfg(all(any(test, ldk_bench), not(feature = "no-std")))]
pub(crate) mod bench_utils {
+ use super::*;
use std::fs::File;
+
+ use bitcoin::hashes::Hash;
+ use bitcoin::secp256k1::{PublicKey, Secp256k1, SecretKey};
+
+ use crate::chain::transaction::OutPoint;
+ use crate::sign::{EntropySource, KeysManager};
+ use crate::ln::channelmanager::{self, ChannelCounterparty, ChannelDetails};
+ use crate::ln::features::InvoiceFeatures;
+ use crate::routing::gossip::NetworkGraph;
+ use crate::util::config::UserConfig;
+ use crate::util::ser::ReadableArgs;
+ use crate::util::test_utils::TestLogger;
+
/// Tries to open a network graph file, or panics with a URL to fetch it.
pub(crate) fn get_route_file() -> Result<std::fs::File, &'static str> {
let res = File::open("net_graph-2023-01-18.bin") // By default we're run in RL/lightning
path.pop(); // target
path.push("lightning");
path.push("net_graph-2023-01-18.bin");
- eprintln!("{}", path.to_str().unwrap());
+ File::open(path)
+ })
+ .or_else(|_| { // Fall back to guessing based on the binary location for a subcrate
+ // path is likely something like .../rust-lightning/bench/target/debug/deps/bench..
+ let mut path = std::env::current_exe().unwrap();
+ path.pop(); // bench...
+ path.pop(); // deps
+ path.pop(); // debug
+ path.pop(); // target
+ path.pop(); // bench
+ path.push("lightning");
+ path.push("net_graph-2023-01-18.bin");
File::open(path)
})
.map_err(|_| "Please fetch https://bitcoin.ninja/ldk-net_graph-v0.0.113-2023-01-18.bin and place it at lightning/net_graph-2023-01-18.bin");
#[cfg(not(require_route_graph_test))]
return res;
}
-}
-
-#[cfg(all(test, feature = "_bench_unstable", not(feature = "no-std")))]
-mod benches {
- use super::*;
- use bitcoin::hashes::Hash;
- use bitcoin::secp256k1::{PublicKey, Secp256k1, SecretKey};
- use crate::chain::transaction::OutPoint;
- use crate::sign::{EntropySource, KeysManager};
- use crate::ln::channelmanager::{self, ChannelCounterparty, ChannelDetails};
- use crate::ln::features::InvoiceFeatures;
- use crate::routing::gossip::NetworkGraph;
- use crate::routing::scoring::{FixedPenaltyScorer, ProbabilisticScorer, ProbabilisticScoringFeeParameters, ProbabilisticScoringDecayParameters};
- use crate::util::config::UserConfig;
- use crate::util::logger::{Logger, Record};
- use crate::util::ser::ReadableArgs;
-
- use test::Bencher;
-
- struct DummyLogger {}
- impl Logger for DummyLogger {
- fn log(&self, _record: &Record) {}
- }
- fn read_network_graph(logger: &DummyLogger) -> NetworkGraph<&DummyLogger> {
- let mut d = bench_utils::get_route_file().unwrap();
- NetworkGraph::read(&mut d, logger).unwrap()
+ pub(crate) fn read_network_graph(logger: &TestLogger) -> Result<NetworkGraph<&TestLogger>, &'static str> {
+ get_route_file().map(|mut f| NetworkGraph::read(&mut f, logger).unwrap())
}
- fn payer_pubkey() -> PublicKey {
+ pub(crate) fn payer_pubkey() -> PublicKey {
let secp_ctx = Secp256k1::new();
PublicKey::from_secret_key(&secp_ctx, &SecretKey::from_slice(&[42; 32]).unwrap())
}
#[inline]
- fn first_hop(node_id: PublicKey) -> ChannelDetails {
+ pub(crate) fn first_hop(node_id: PublicKey) -> ChannelDetails {
ChannelDetails {
channel_id: [0; 32],
counterparty: ChannelCounterparty {
short_channel_id: Some(1),
inbound_scid_alias: None,
outbound_scid_alias: None,
- channel_value_satoshis: 10_000_000,
+ channel_value_satoshis: 10_000_000_000,
user_channel_id: 0,
- balance_msat: 10_000_000,
- outbound_capacity_msat: 10_000_000,
- next_outbound_htlc_limit_msat: 10_000_000,
+ balance_msat: 10_000_000_000,
+ outbound_capacity_msat: 10_000_000_000,
+ next_outbound_htlc_minimum_msat: 0,
+ next_outbound_htlc_limit_msat: 10_000_000_000,
inbound_capacity_msat: 0,
unspendable_punishment_reserve: None,
confirmations_required: None,
}
}
- #[bench]
- fn generate_routes_with_zero_penalty_scorer(bench: &mut Bencher) {
- let logger = DummyLogger {};
- let network_graph = read_network_graph(&logger);
+ pub(crate) fn generate_test_routes<S: Score>(graph: &NetworkGraph<&TestLogger>, scorer: &mut S,
+ score_params: &S::ScoreParams, features: InvoiceFeatures, mut seed: u64,
+ starting_amount: u64, route_count: usize,
+ ) -> Vec<(ChannelDetails, PaymentParameters, u64)> {
+ let payer = payer_pubkey();
+ let keys_manager = KeysManager::new(&[0u8; 32], 42, 42);
+ let random_seed_bytes = keys_manager.get_secure_random_bytes();
+
+ let nodes = graph.read_only().nodes().clone();
+ let mut route_endpoints = Vec::new();
+ // Fetch 1.5x more routes than we need as after we do some scorer updates we may end up
+ // with some routes we picked being un-routable.
+ for _ in 0..route_count * 3 / 2 {
+ loop {
+ seed = seed.overflowing_mul(6364136223846793005).0.overflowing_add(1).0;
+ let src = PublicKey::from_slice(nodes.unordered_keys()
+ .skip((seed as usize) % nodes.len()).next().unwrap().as_slice()).unwrap();
+ seed = seed.overflowing_mul(6364136223846793005).0.overflowing_add(1).0;
+ let dst = PublicKey::from_slice(nodes.unordered_keys()
+ .skip((seed as usize) % nodes.len()).next().unwrap().as_slice()).unwrap();
+ let params = PaymentParameters::from_node_id(dst, 42)
+ .with_bolt11_features(features.clone()).unwrap();
+ let first_hop = first_hop(src);
+ let amt = starting_amount + seed % 1_000_000;
+ let path_exists =
+ get_route(&payer, ¶ms, &graph.read_only(), Some(&[&first_hop]),
+ amt, &TestLogger::new(), &scorer, score_params, &random_seed_bytes).is_ok();
+ if path_exists {
+ // ...and seed the scorer with success and failure data...
+ seed = seed.overflowing_mul(6364136223846793005).0.overflowing_add(1).0;
+ let mut score_amt = seed % 1_000_000_000;
+ loop {
+ // Generate fail/success paths for a wider range of potential amounts with
+ // MPP enabled to give us a chance to apply penalties for more potential
+ // routes.
+ let mpp_features = channelmanager::provided_invoice_features(&UserConfig::default());
+ let params = PaymentParameters::from_node_id(dst, 42)
+ .with_bolt11_features(mpp_features).unwrap();
+
+ let route_res = get_route(&payer, ¶ms, &graph.read_only(),
+ Some(&[&first_hop]), score_amt, &TestLogger::new(), &scorer,
+ score_params, &random_seed_bytes);
+ if let Ok(route) = route_res {
+ for path in route.paths {
+ if seed & 0x80 == 0 {
+ scorer.payment_path_successful(&path);
+ } else {
+ let short_channel_id = path.hops[path.hops.len() / 2].short_channel_id;
+ scorer.payment_path_failed(&path, short_channel_id);
+ }
+ seed = seed.overflowing_mul(6364136223846793005).0.overflowing_add(1).0;
+ }
+ break;
+ }
+ // If we couldn't find a path with a higer amount, reduce and try again.
+ score_amt /= 100;
+ }
+
+ route_endpoints.push((first_hop, params, amt));
+ break;
+ }
+ }
+ }
+
+ // Because we've changed channel scores, it's possible we'll take different routes to the
+ // selected destinations, possibly causing us to fail because, eg, the newly-selected path
+ // requires a too-high CLTV delta.
+ route_endpoints.retain(|(first_hop, params, amt)| {
+ get_route(&payer, params, &graph.read_only(), Some(&[first_hop]), *amt,
+ &TestLogger::new(), &scorer, score_params, &random_seed_bytes).is_ok()
+ });
+ route_endpoints.truncate(route_count);
+ assert_eq!(route_endpoints.len(), route_count);
+ route_endpoints
+ }
+}
+
+#[cfg(ldk_bench)]
+pub mod benches {
+ use super::*;
+ use crate::sign::{EntropySource, KeysManager};
+ use crate::ln::channelmanager;
+ use crate::ln::features::InvoiceFeatures;
+ use crate::routing::gossip::NetworkGraph;
+ use crate::routing::scoring::{FixedPenaltyScorer, ProbabilisticScorer, ProbabilisticScoringFeeParameters, ProbabilisticScoringDecayParameters};
+ use crate::util::config::UserConfig;
+ use crate::util::logger::{Logger, Record};
+ use crate::util::test_utils::TestLogger;
+
+ use criterion::Criterion;
+
+ struct DummyLogger {}
+ impl Logger for DummyLogger {
+ fn log(&self, _record: &Record) {}
+ }
+
+ pub fn generate_routes_with_zero_penalty_scorer(bench: &mut Criterion) {
+ let logger = TestLogger::new();
+ let network_graph = bench_utils::read_network_graph(&logger).unwrap();
let scorer = FixedPenaltyScorer::with_penalty(0);
- generate_routes(bench, &network_graph, scorer, &(), InvoiceFeatures::empty());
+ generate_routes(bench, &network_graph, scorer, &(), InvoiceFeatures::empty(), 0,
+ "generate_routes_with_zero_penalty_scorer");
}
- #[bench]
- fn generate_mpp_routes_with_zero_penalty_scorer(bench: &mut Bencher) {
- let logger = DummyLogger {};
- let network_graph = read_network_graph(&logger);
+ pub fn generate_mpp_routes_with_zero_penalty_scorer(bench: &mut Criterion) {
+ let logger = TestLogger::new();
+ let network_graph = bench_utils::read_network_graph(&logger).unwrap();
let scorer = FixedPenaltyScorer::with_penalty(0);
- generate_routes(bench, &network_graph, scorer, &(), channelmanager::provided_invoice_features(&UserConfig::default()));
+ generate_routes(bench, &network_graph, scorer, &(),
+ channelmanager::provided_invoice_features(&UserConfig::default()), 0,
+ "generate_mpp_routes_with_zero_penalty_scorer");
+ }
+
+ pub fn generate_routes_with_probabilistic_scorer(bench: &mut Criterion) {
+ let logger = TestLogger::new();
+ let network_graph = bench_utils::read_network_graph(&logger).unwrap();
+ let params = ProbabilisticScoringFeeParameters::default();
+ let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
+ generate_routes(bench, &network_graph, scorer, ¶ms, InvoiceFeatures::empty(), 0,
+ "generate_routes_with_probabilistic_scorer");
}
- #[bench]
- fn generate_routes_with_probabilistic_scorer(bench: &mut Bencher) {
- let logger = DummyLogger {};
- let network_graph = read_network_graph(&logger);
+ pub fn generate_mpp_routes_with_probabilistic_scorer(bench: &mut Criterion) {
+ let logger = TestLogger::new();
+ let network_graph = bench_utils::read_network_graph(&logger).unwrap();
let params = ProbabilisticScoringFeeParameters::default();
let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
- generate_routes(bench, &network_graph, scorer, ¶ms, InvoiceFeatures::empty());
+ generate_routes(bench, &network_graph, scorer, ¶ms,
+ channelmanager::provided_invoice_features(&UserConfig::default()), 0,
+ "generate_mpp_routes_with_probabilistic_scorer");
}
- #[bench]
- fn generate_mpp_routes_with_probabilistic_scorer(bench: &mut Bencher) {
- let logger = DummyLogger {};
- let network_graph = read_network_graph(&logger);
+ pub fn generate_large_mpp_routes_with_probabilistic_scorer(bench: &mut Criterion) {
+ let logger = TestLogger::new();
+ let network_graph = bench_utils::read_network_graph(&logger).unwrap();
let params = ProbabilisticScoringFeeParameters::default();
let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
- generate_routes(bench, &network_graph, scorer, ¶ms, channelmanager::provided_invoice_features(&UserConfig::default()));
+ generate_routes(bench, &network_graph, scorer, ¶ms,
+ channelmanager::provided_invoice_features(&UserConfig::default()), 100_000_000,
+ "generate_large_mpp_routes_with_probabilistic_scorer");
}
fn generate_routes<S: Score>(
- bench: &mut Bencher, graph: &NetworkGraph<&DummyLogger>, mut scorer: S, score_params: &S::ScoreParams,
- features: InvoiceFeatures
+ bench: &mut Criterion, graph: &NetworkGraph<&TestLogger>, mut scorer: S,
+ score_params: &S::ScoreParams, features: InvoiceFeatures, starting_amount: u64,
+ bench_name: &'static str,
) {
- let nodes = graph.read_only().nodes().clone();
- let payer = payer_pubkey();
+ 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 mut routes = Vec::new();
- let mut route_endpoints = Vec::new();
- let mut seed: usize = 0xdeadbeef;
- 'load_endpoints: for _ in 0..150 {
- loop {
- seed *= 0xdeadbeef;
- let src = PublicKey::from_slice(nodes.unordered_keys().skip(seed % nodes.len()).next().unwrap().as_slice()).unwrap();
- seed *= 0xdeadbeef;
- let dst = PublicKey::from_slice(nodes.unordered_keys().skip(seed % nodes.len()).next().unwrap().as_slice()).unwrap();
- let params = PaymentParameters::from_node_id(dst, 42).with_bolt11_features(features.clone()).unwrap();
- let first_hop = first_hop(src);
- let amt = seed as u64 % 1_000_000;
- if let Ok(route) = get_route(&payer, ¶ms, &graph.read_only(), Some(&[&first_hop]), amt, &DummyLogger{}, &scorer, score_params, &random_seed_bytes) {
- routes.push(route);
- route_endpoints.push((first_hop, params, amt));
- continue 'load_endpoints;
- }
- }
- }
-
- // ...and seed the scorer with success and failure data...
- for route in routes {
- let amount = route.get_total_amount();
- if amount < 250_000 {
- for path in route.paths {
- scorer.payment_path_successful(&path);
- }
- } else if amount > 750_000 {
- for path in route.paths {
- let short_channel_id = path.hops[path.hops.len() / 2].short_channel_id;
- scorer.payment_path_failed(&path, short_channel_id);
- }
- }
- }
-
- // Because we've changed channel scores, its possible we'll take different routes to the
- // selected destinations, possibly causing us to fail because, eg, the newly-selected path
- // requires a too-high CLTV delta.
- route_endpoints.retain(|(first_hop, params, amt)| {
- get_route(&payer, params, &graph.read_only(), Some(&[first_hop]), *amt, &DummyLogger{}, &scorer, score_params, &random_seed_bytes).is_ok()
- });
- route_endpoints.truncate(100);
- assert_eq!(route_endpoints.len(), 100);
+ 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.
let mut idx = 0;
- bench.iter(|| {
+ bench.bench_function(bench_name, |b| b.iter(|| {
let (first_hop, params, amt) = &route_endpoints[idx % route_endpoints.len()];
- assert!(get_route(&payer, params, &graph.read_only(), Some(&[first_hop]), *amt, &DummyLogger{}, &scorer, score_params, &random_seed_bytes).is_ok());
+ assert!(get_route(&payer, params, &graph.read_only(), Some(&[first_hop]), *amt,
+ &DummyLogger{}, &scorer, score_params, &random_seed_bytes).is_ok());
idx += 1;
- });
+ }));
}
}