X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Fnetwork_graph.rs;h=3cbcd9120e56b8167583045adbcc3b1c1d031fbb;hb=42f6a8f1113fb17d1c07a5d63e5fd70c1e635040;hp=e11a53b769183cf7bec0bb81c1510cb6565505f7;hpb=7815965bf758dbcf8edf7beac5e4a95291ae7a3e;p=rust-lightning diff --git a/lightning/src/routing/network_graph.rs b/lightning/src/routing/network_graph.rs index e11a53b7..3cbcd912 100644 --- a/lightning/src/routing/network_graph.rs +++ b/lightning/src/routing/network_graph.rs @@ -32,13 +32,13 @@ use util::logger::Logger; use util::events::{MessageSendEvent, MessageSendEventsProvider}; use util::scid_utils::{block_from_scid, scid_from_parts, MAX_SCID_BLOCK}; -use std::{cmp, fmt}; +use prelude::*; +use alloc::collections::{BTreeMap, btree_map::Entry as BtreeEntry}; +use core::{cmp, fmt}; use std::sync::{RwLock, RwLockReadGuard}; -use std::sync::atomic::{AtomicUsize, Ordering}; +use core::sync::atomic::{AtomicUsize, Ordering}; use std::sync::Mutex; -use std::collections::BTreeMap; -use std::collections::btree_map::Entry as BtreeEntry; -use std::ops::Deref; +use core::ops::Deref; use bitcoin::hashes::hex::ToHex; /// The maximum number of extra bytes which we do not understand in a gossip message before we will @@ -152,7 +152,7 @@ macro_rules! secp_verify_sig { }; } -impl RoutingMessageHandler for NetGraphMsgHandler where C::Target: chain::Access, L::Target: Logger { +impl RoutingMessageHandler for NetGraphMsgHandler where C::Target: chain::Access, L::Target: Logger { fn handle_node_announcement(&self, msg: &msgs::NodeAnnouncement) -> Result { self.network_graph.write().unwrap().update_node_from_announcement(msg, &self.secp_ctx)?; Ok(msg.contents.excess_data.len() <= MAX_EXCESS_BYTES_FOR_RELAY && @@ -373,33 +373,39 @@ impl RoutingMessageHandler for N let mut pending_events = self.pending_events.lock().unwrap(); let batch_count = batches.len(); + let mut prev_batch_endblock = msg.first_blocknum; for (batch_index, batch) in batches.into_iter().enumerate() { - // Per spec, the initial first_blocknum needs to be <= the query's first_blocknum. - // Use the query's values since we don't use pre-processed reply ranges. - let first_blocknum = if batch_index == 0 { - msg.first_blocknum - } - // Subsequent replies must be >= the last sent first_blocknum. Use the first block - // in the new batch. Batches beyond the first one cannot be empty. - else { - block_from_scid(batch.first().unwrap()) - }; - - // Per spec, the last end_blocknum needs to be >= the query's end_blocknum. Last - // reply calculates difference between the query's end_blocknum and the start of the reply. - // Overflow safe since end_blocknum=msg.first_block_num+msg.number_of_blocks and first_blocknum - // will be either msg.first_blocknum or a higher block height. - let number_of_blocks = if batch_index == batch_count-1 { - msg.end_blocknum() - first_blocknum + // Per spec, the initial `first_blocknum` needs to be <= the query's `first_blocknum` + // and subsequent `first_blocknum`s must be >= the prior reply's `first_blocknum`. + // + // Additionally, c-lightning versions < 0.10 require that the `first_blocknum` of each + // reply is >= the previous reply's `first_blocknum` and either exactly the previous + // reply's `first_blocknum + number_of_blocks` or exactly one greater. This is a + // significant diversion from the requirements set by the spec, and, in case of blocks + // with no channel opens (e.g. empty blocks), requires that we use the previous value + // and *not* derive the first_blocknum from the actual first block of the reply. + let first_blocknum = prev_batch_endblock; + + // Each message carries the number of blocks (from the `first_blocknum`) its contents + // fit in. Though there is no requirement that we use exactly the number of blocks its + // contents are from, except for the bogus requirements c-lightning enforces, above. + // + // Per spec, the last end block (ie `first_blocknum + number_of_blocks`) needs to be + // >= the query's end block. Thus, for the last reply, we calculate the difference + // between the query's end block and the start of the reply. + // + // Overflow safe since end_blocknum=msg.first_block_num+msg.number_of_blocks and + // first_blocknum will be either msg.first_blocknum or a higher block height. + let (sync_complete, number_of_blocks) = if batch_index == batch_count-1 { + (true, msg.end_blocknum() - first_blocknum) } // Prior replies should use the number of blocks that fit into the reply. Overflow // safe since first_blocknum is always <= last SCID's block. else { - block_from_scid(batch.last().unwrap()) - first_blocknum + 1 + (false, block_from_scid(batch.last().unwrap()) - first_blocknum) }; - // Only true for the last message in a sequence - let sync_complete = batch_index == batch_count - 1; + prev_batch_endblock = first_blocknum + number_of_blocks; pending_events.push(MessageSendEvent::SendReplyChannelRange { node_id: their_node_id.clone(), @@ -433,7 +439,7 @@ where fn get_and_clear_pending_msg_events(&self) -> Vec { let mut ret = Vec::new(); let mut pending_events = self.pending_events.lock().unwrap(); - std::mem::swap(&mut ret, &mut pending_events); + core::mem::swap(&mut ret, &mut pending_events); ret } } @@ -469,15 +475,15 @@ impl fmt::Display for DirectionalChannelInfo { } } -impl_writeable!(DirectionalChannelInfo, 0, { - last_update, - enabled, - cltv_expiry_delta, - htlc_minimum_msat, - htlc_maximum_msat, - fees, - last_update_message -}); +impl_writeable_tlv_based!(DirectionalChannelInfo, { + (0, last_update), + (2, enabled), + (4, cltv_expiry_delta), + (6, htlc_minimum_msat), + (8, htlc_maximum_msat), + (10, fees), + (12, last_update_message), +}, {}, {}); #[derive(Clone, Debug, PartialEq)] /// Details about a channel (both directions). @@ -510,15 +516,15 @@ impl fmt::Display for ChannelInfo { } } -impl_writeable!(ChannelInfo, 0, { - features, - node_one, - one_to_two, - node_two, - two_to_one, - capacity_sats, - announcement_message -}); +impl_writeable_tlv_based!(ChannelInfo, { + (0, features), + (2, node_one), + (4, one_to_two), + (6, node_two), + (8, two_to_one), + (10, capacity_sats), + (12, announcement_message), +}, {}, {}); /// Fees for routing via a given channel or a node @@ -531,24 +537,7 @@ pub struct RoutingFees { pub proportional_millionths: u32, } -impl Readable for RoutingFees{ - fn read(reader: &mut R) -> Result { - let base_msat: u32 = Readable::read(reader)?; - let proportional_millionths: u32 = Readable::read(reader)?; - Ok(RoutingFees { - base_msat, - proportional_millionths, - }) - } -} - -impl Writeable for RoutingFees { - fn write(&self, writer: &mut W) -> Result<(), ::std::io::Error> { - self.base_msat.write(writer)?; - self.proportional_millionths.write(writer)?; - Ok(()) - } -} +impl_writeable_tlv_based!(RoutingFees, {(0, base_msat), (2, proportional_millionths)}, {}, {}); #[derive(Clone, Debug, PartialEq)] /// Information received in the latest node_announcement from this node. @@ -573,48 +562,16 @@ pub struct NodeAnnouncementInfo { pub announcement_message: Option } -impl Writeable for NodeAnnouncementInfo { - fn write(&self, writer: &mut W) -> Result<(), ::std::io::Error> { - self.features.write(writer)?; - self.last_update.write(writer)?; - self.rgb.write(writer)?; - self.alias.write(writer)?; - (self.addresses.len() as u64).write(writer)?; - for ref addr in &self.addresses { - addr.write(writer)?; - } - self.announcement_message.write(writer)?; - Ok(()) - } -} - -impl Readable for NodeAnnouncementInfo { - fn read(reader: &mut R) -> Result { - let features = Readable::read(reader)?; - let last_update = Readable::read(reader)?; - let rgb = Readable::read(reader)?; - let alias = Readable::read(reader)?; - let addresses_count: u64 = Readable::read(reader)?; - let mut addresses = Vec::with_capacity(cmp::min(addresses_count, MAX_ALLOC_SIZE / 40) as usize); - for _ in 0..addresses_count { - match Readable::read(reader) { - Ok(Ok(addr)) => { addresses.push(addr); }, - Ok(Err(_)) => return Err(DecodeError::InvalidValue), - Err(DecodeError::ShortRead) => return Err(DecodeError::BadLengthDescriptor), - _ => unreachable!(), - } - } - let announcement_message = Readable::read(reader)?; - Ok(NodeAnnouncementInfo { - features, - last_update, - rgb, - alias, - addresses, - announcement_message - }) - } -} +impl_writeable_tlv_based!(NodeAnnouncementInfo, { + (0, features), + (2, last_update), + (4, rgb), + (6, alias), +}, { + (8, announcement_message), +}, { + (10, addresses), +}); #[derive(Clone, Debug, PartialEq)] /// Details about a node in the network, known from the network announcement. @@ -639,39 +596,20 @@ impl fmt::Display for NodeInfo { } } -impl Writeable for NodeInfo { - fn write(&self, writer: &mut W) -> Result<(), ::std::io::Error> { - (self.channels.len() as u64).write(writer)?; - for ref chan in self.channels.iter() { - chan.write(writer)?; - } - self.lowest_inbound_channel_fees.write(writer)?; - self.announcement_info.write(writer)?; - Ok(()) - } -} - -const MAX_ALLOC_SIZE: u64 = 64*1024; +impl_writeable_tlv_based!(NodeInfo, {}, { + (0, lowest_inbound_channel_fees), + (2, announcement_info), +}, { + (4, channels), +}); -impl Readable for NodeInfo { - fn read(reader: &mut R) -> Result { - let channels_count: u64 = Readable::read(reader)?; - let mut channels = Vec::with_capacity(cmp::min(channels_count, MAX_ALLOC_SIZE / 8) as usize); - for _ in 0..channels_count { - channels.push(Readable::read(reader)?); - } - let lowest_inbound_channel_fees = Readable::read(reader)?; - let announcement_info = Readable::read(reader)?; - Ok(NodeInfo { - channels, - lowest_inbound_channel_fees, - announcement_info, - }) - } -} +const SERIALIZATION_VERSION: u8 = 1; +const MIN_SERIALIZATION_VERSION: u8 = 1; impl Writeable for NetworkGraph { fn write(&self, writer: &mut W) -> Result<(), ::std::io::Error> { + write_ver_prefix!(writer, SERIALIZATION_VERSION, MIN_SERIALIZATION_VERSION); + self.genesis_hash.write(writer)?; (self.channels.len() as u64).write(writer)?; for (ref chan_id, ref chan_info) in self.channels.iter() { @@ -683,12 +621,16 @@ impl Writeable for NetworkGraph { node_id.write(writer)?; node_info.write(writer)?; } + + write_tlv_fields!(writer, {}, {}); Ok(()) } } impl Readable for NetworkGraph { fn read(reader: &mut R) -> Result { + let _ver = read_ver_prefix!(reader, SERIALIZATION_VERSION); + let genesis_hash: BlockHash = Readable::read(reader)?; let channels_count: u64 = Readable::read(reader)?; let mut channels = BTreeMap::new(); @@ -704,6 +646,8 @@ impl Readable for NetworkGraph { let node_info = Readable::read(reader)?; nodes.insert(node_id, node_info); } + read_tlv_fields!(reader, {}, {}); + Ok(NetworkGraph { genesis_hash, channels, @@ -1139,6 +1083,7 @@ mod tests { use bitcoin::secp256k1::key::{PublicKey, SecretKey}; use bitcoin::secp256k1::{All, Secp256k1}; + use prelude::*; use std::sync::Arc; fn create_net_graph_msg_handler() -> (Secp256k1, NetGraphMsgHandler, Arc>) { @@ -2209,7 +2154,6 @@ mod tests { // used for testing resumption on same block scids.push(scid_from_parts(108001, 1, 0).unwrap()); - scids.push(scid_from_parts(108001, 2, 0).unwrap()); for scid in scids { let unsigned_announcement = UnsignedChannelAnnouncement { @@ -2321,14 +2265,14 @@ mod tests { &node_id_2, QueryChannelRange { chain_hash: chain_hash.clone(), - first_blocknum: 0x00800000, + first_blocknum: 1000, number_of_blocks: 1000, }, true, vec![ ReplyChannelRange { chain_hash: chain_hash.clone(), - first_blocknum: 0x00800000, + first_blocknum: 1000, number_of_blocks: 1000, sync_complete: true, short_channel_ids: vec![], @@ -2396,7 +2340,7 @@ mod tests { ReplyChannelRange { chain_hash: chain_hash.clone(), first_blocknum: 100000, - number_of_blocks: 8000, + number_of_blocks: 7999, sync_complete: false, short_channel_ids: (100000..=107999) .map(|block| scid_from_parts(block, 0, 0).unwrap()) @@ -2404,8 +2348,8 @@ mod tests { }, ReplyChannelRange { chain_hash: chain_hash.clone(), - first_blocknum: 108000, - number_of_blocks: 1, + first_blocknum: 107999, + number_of_blocks: 2, sync_complete: true, short_channel_ids: vec![ scid_from_parts(108000, 0, 0).unwrap(), @@ -2428,7 +2372,7 @@ mod tests { ReplyChannelRange { chain_hash: chain_hash.clone(), first_blocknum: 100002, - number_of_blocks: 8000, + number_of_blocks: 7999, sync_complete: false, short_channel_ids: (100002..=108001) .map(|block| scid_from_parts(block, 0, 0).unwrap()) @@ -2441,7 +2385,6 @@ mod tests { sync_complete: true, short_channel_ids: vec![ scid_from_parts(108001, 1, 0).unwrap(), - scid_from_parts(108001, 2, 0).unwrap(), ], } ] @@ -2455,6 +2398,9 @@ mod tests { expected_ok: bool, expected_replies: Vec ) { + let mut max_firstblocknum = msg.first_blocknum.saturating_sub(1); + let mut c_lightning_0_9_prev_end_blocknum = max_firstblocknum; + let query_end_blocknum = msg.end_blocknum(); let result = net_graph_msg_handler.handle_query_channel_range(test_node_id, msg); if expected_ok { @@ -2476,6 +2422,17 @@ mod tests { assert_eq!(msg.number_of_blocks, expected_reply.number_of_blocks); assert_eq!(msg.sync_complete, expected_reply.sync_complete); assert_eq!(msg.short_channel_ids, expected_reply.short_channel_ids); + + // Enforce exactly the sequencing requirements present on c-lightning v0.9.3 + assert!(msg.first_blocknum == c_lightning_0_9_prev_end_blocknum || msg.first_blocknum == c_lightning_0_9_prev_end_blocknum.saturating_add(1)); + assert!(msg.first_blocknum >= max_firstblocknum); + max_firstblocknum = msg.first_blocknum; + c_lightning_0_9_prev_end_blocknum = msg.first_blocknum.saturating_add(msg.number_of_blocks); + + // Check that the last block count is >= the query's end_blocknum + if i == events.len() - 1 { + assert!(msg.first_blocknum.saturating_add(msg.number_of_blocks) >= query_end_blocknum); + } }, _ => panic!("expected MessageSendEvent::SendReplyChannelRange"), } @@ -2497,3 +2454,30 @@ mod tests { assert!(result.is_err()); } } + +#[cfg(all(test, feature = "unstable"))] +mod benches { + use super::*; + + use test::Bencher; + use std::io::Read; + + #[bench] + fn read_network_graph(bench: &mut Bencher) { + let mut d = ::routing::router::test_utils::get_route_file().unwrap(); + let mut v = Vec::new(); + d.read_to_end(&mut v).unwrap(); + bench.iter(|| { + let _ = NetworkGraph::read(&mut std::io::Cursor::new(&v)).unwrap(); + }); + } + + #[bench] + fn write_network_graph(bench: &mut Bencher) { + let mut d = ::routing::router::test_utils::get_route_file().unwrap(); + let net_graph = NetworkGraph::read(&mut d).unwrap(); + bench.iter(|| { + let _ = net_graph.encode(); + }); + } +}