select.rs
1 //! Logic for filtering and selecting channels in order to find suitable channels for a target. 2 3 use crate::mgr::state::{ChannelState, OpenEntry, PendingEntry}; 4 use crate::mgr::AbstractChannel; 5 use tor_linkspec::{HasRelayIds, RelayIds}; 6 7 /// Returns `true` if the open channel is allowed to be used for a new channel request to the 8 /// target. 9 pub(crate) fn open_channel_is_allowed<C: AbstractChannel>( 10 chan: &OpenEntry<C>, 11 target: &impl HasRelayIds, 12 ) -> bool { 13 Some(chan) 14 // only usable channels 15 .filter(|entry| entry.channel.is_usable()) 16 // only channels which have *all* the relay ids of `target` 17 .filter(|entry| entry.channel.has_all_relay_ids_from(target)) 18 // TODO: only channels which are canonical or have the same address as `target` 19 .filter(|_entry| true) 20 .is_some() 21 } 22 23 /// Returns `true` if the pending channel could possibly be used for a new channel request to the 24 /// target. You still need to verify the final built channel with [`open_channel_is_allowed`] before 25 /// using it. 26 pub(crate) fn pending_channel_maybe_allowed( 27 chan: &PendingEntry, 28 target: &impl HasRelayIds, 29 ) -> bool { 30 /// An empty [`RelayIds`]. 31 const EMPTY_IDS: RelayIds = RelayIds::empty(); 32 33 // TODO RELAY: The comments and behaviour below assume that it's better to create a new channel 34 // than to wait around for a channel which may or may not end up being usable for `target`. This 35 // has the benefit that malicious circuit extension requests won't delay legitimate circuit 36 // extension requests, but also means that we could end up creating more channels than 37 // necessary. This is different from C-tor, which will wait for a channel even if that channel 38 // might not end up being usable for `target`. For example in tor's `channel_get_for_extend`, 39 // tor will wait for an "in progress" channel if all of the following are true: 40 // 41 // - The requested ids are a subset of the channel's ids. (Note that in the comments below we 42 // require it to be a superset, not a subset.) 43 // - The requested IPv4 or IPv6 address matches either the channel's IPv4 or IPv6 address. (Note 44 // that in the comments below, we require `target`s addresses to exactly match.) 45 // 46 // It might be good to re-evaluate what behaviour we want as we implement more channel code. 47 // 48 // NOTE (opara): It has been decided that C-tor's approach would be better. See the thread at: 49 // https://gitlab.torproject.org/tpo/core/arti/-/merge_requests/2544#note_3094696 50 51 // We want to avoid returning pending channels that were initially created from malicious 52 // channel requests (for example from malicious relay-extend requests) that build channels which 53 // will never complete successfully. Two cases where this can happen are: 54 // 1. A malicious channel request asks us to build a channel to a target with a correct relay id 55 // and address, but also an additional incorrect relay id. Later when the target sends its 56 // CERTS cell, all of the relay ids won't match and the channel will fail to build. We don't 57 // want to assign non-malicious channel requests to this pending channel that will eventually 58 // fail to build. 59 // 2. A malicious channel request asks us to build a channel to a target with an incorrect 60 // address. This pending channel may stall. We don't want to assign non-malicious channel 61 // requests to this pending channel that will stall for potentially a long time. 62 Some(chan) 63 // Only channels where `target`s relay ids are a superset of `entry`s relay ids. 64 // - Hopefully the built channel will gain the additional ids that are requested by 65 // `target`. This should happen in most cases where none of the channels are made 66 // maliciously, since the `target` should return all of its relay ids in its CERTS cell. 67 // - (Addressing 1. above) By only returning pending channels that have a subset of 68 // `target`s relay ids, we ensure that the returned pending channel does not have 69 // additional incorrect relay ids that will intentionally cause the pending channel to 70 // fail. 71 // - If the built channel does not gain the remaining ids required by `target, then we won't 72 // be able to use this channel for the channel request to `target`. But we won't be able 73 // to create a new channel either, since we know that that a new channel also won't have 74 // all of the relay ids. So this channel request was doomed from the start. 75 // - If the built channel gains additional ids that `target` doesn't have, that's fine and 76 // we can still use the channel for `target`. 77 .filter(|entry| target.has_all_relay_ids_from(&entry.ids)) 78 // TODO: Only channels which have the exact same address list as `target` (the two sets of 79 // addresses must match exactly). 80 // - While an EXTEND2 message usually only contains one IPv4 and IPv6 address, `target` 81 // (which is a `HasAddrs`) may have more addresses. According to tor-spec, an EXTEND2 82 // message can contain multiple IPv4 and IPv6 addresses: 83 // > Nodes MUST ignore unrecognized specifiers, and MUST accept multiple instances of 84 // > specifiers other than 'legacy identity' and 'Ed25519 identity'. (Nodes SHOULD reject 85 // > link specifier lists that include multiple instances of either one of those 86 // > specifiers.) 87 // - (Addressing 2. above) By only returning pending channels that have exactly the same 88 // addresses, we ensure that the returned pending channel does not have any incorrect 89 // addresses that will cause the pending channel to stall. 90 // - If the pending channel had additional addresses compared to `target`, the channel could 91 // get built using an address that is not valid for `target` and we wouldn't be able to 92 // use the built channel. 93 // - If the pending channel had fewer addresses compared to `target`, the channel would have 94 // a lower possibility of building successfully compared to a newly created channel to 95 // `target`, so this would not be a good channel for us to return. 96 .filter(|_entry| true) 97 // Don't allow a pending channel that has no relay ids. I don't have a good reason for 98 // excluding this, other than "it seems weird". 99 .filter(|entry| entry.ids != EMPTY_IDS) 100 .is_some() 101 } 102 103 /// Returns the best channel for `target`. 104 // TODO: remove me when the below TODOs are implemented 105 #[allow(clippy::only_used_in_recursion)] 106 pub(crate) fn choose_best_channel<'a, C: AbstractChannel>( 107 channels: impl IntoIterator<Item = &'a ChannelState<C>>, 108 target: &impl HasRelayIds, 109 ) -> Option<&'a ChannelState<C>> { 110 use std::cmp::Ordering; 111 use ChannelState::*; 112 113 let channels = channels.into_iter(); 114 115 /// Compare two channels to determine the better channel for `target`. 116 fn choose_channel<C: AbstractChannel>( 117 a: &&ChannelState<C>, 118 b: &&ChannelState<C>, 119 target: &impl HasRelayIds, 120 ) -> Choice { 121 // TODO: follow `channel_is_better` in C tor 122 match (a, b) { 123 // if the open channel is not usable, prefer the pending channel 124 (Open(a), Building(_b)) if !a.channel.is_usable() => Choice::Second, 125 // otherwise prefer the open channel 126 (Open(_a), Building(_b)) => Choice::First, 127 128 // the logic above, but reversed 129 (Building(_), Open(_)) => choose_channel(b, a, target).reverse(), 130 131 // not much info to help choose when both channels are pending, but this should be rare 132 (Building(_a), Building(_b)) => Choice::Either, 133 134 // both channels are open 135 (Open(a), Open(b)) => { 136 let a_is_usable = a.channel.is_usable(); 137 let b_is_usable = b.channel.is_usable(); 138 139 // if neither open channel is usable, don't take preference 140 if !a_is_usable && !b_is_usable { 141 return Choice::Either; 142 } 143 144 // prefer a channel that is usable 145 if !a_is_usable { 146 return Choice::Second; 147 } 148 if !b_is_usable { 149 return Choice::First; 150 } 151 152 // TODO: prefer canonical channels 153 154 // TODO: prefer a channel where the address matches the target 155 156 // TODO: prefer the one we think the peer will think is canonical 157 158 // TODO: prefer older channels 159 160 // TODO: use number of circuits as tie-breaker? 161 162 Choice::Either 163 } 164 } 165 } 166 167 // preferred channels will be ordered higher, and we choose the max 168 channels.max_by(|a, b| match choose_channel(a, b, target) { 169 Choice::First => Ordering::Greater, 170 Choice::Second => Ordering::Less, 171 Choice::Either => Ordering::Equal, 172 }) 173 } 174 175 /// Similar to [`Ordering`](std::cmp::Ordering), but is easier to reason about when comparing two 176 /// objects that don't have a numeric sense of ordering (ex: returning `Greater` is confusing if the 177 /// ordering isn't numeric). 178 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)] 179 enum Choice { 180 /// Choose the first. 181 First, 182 /// Choose the second. 183 Second, 184 /// Choose either. 185 Either, 186 } 187 188 impl Choice { 189 /// Reverses the `Choice`. 190 /// 191 /// - `First` becomes `Second`. 192 /// - `Second` becomes `First`. 193 /// - `Either` becomes `Either`. 194 fn reverse(self) -> Self { 195 match self { 196 Self::First => Self::Second, 197 Self::Second => Self::First, 198 Self::Either => Self::Either, 199 } 200 } 201 } 202 203 #[cfg(test)] 204 mod test { 205 // @@ begin test lint list maintained by maint/add_warning @@ 206 #![allow(clippy::bool_assert_comparison)] 207 #![allow(clippy::clone_on_copy)] 208 #![allow(clippy::dbg_macro)] 209 #![allow(clippy::mixed_attributes_style)] 210 #![allow(clippy::print_stderr)] 211 #![allow(clippy::print_stdout)] 212 #![allow(clippy::single_char_pattern)] 213 #![allow(clippy::unwrap_used)] 214 #![allow(clippy::unchecked_duration_subtraction)] 215 #![allow(clippy::useless_vec)] 216 #![allow(clippy::needless_pass_by_value)] 217 //! <!-- @@ end test lint list maintained by maint/add_warning @@ --> 218 219 use super::*; 220 221 use std::sync::Arc; 222 use std::time::Duration; 223 224 use tor_linkspec::RelayIds; 225 use tor_llcrypto::pk::ed25519::Ed25519Identity; 226 use tor_llcrypto::pk::rsa::RsaIdentity; 227 use tor_proto::channel::ChannelPaddingInstructionsUpdates; 228 229 #[derive(Debug)] 230 struct FakeChannel { 231 usable: bool, 232 ids: RelayIds, 233 } 234 235 impl AbstractChannel for FakeChannel { 236 fn is_usable(&self) -> bool { 237 self.usable 238 } 239 fn duration_unused(&self) -> Option<Duration> { 240 None 241 } 242 fn reparameterize( 243 &self, 244 _updates: Arc<ChannelPaddingInstructionsUpdates>, 245 ) -> tor_proto::Result<()> { 246 Ok(()) 247 } 248 fn engage_padding_activities(&self) {} 249 } 250 251 impl HasRelayIds for FakeChannel { 252 fn identity( 253 &self, 254 key_type: tor_linkspec::RelayIdType, 255 ) -> Option<tor_linkspec::RelayIdRef<'_>> { 256 self.ids.identity(key_type) 257 } 258 } 259 260 #[derive(Clone, Debug)] 261 struct FakeBuildSpec { 262 ids: RelayIds, 263 } 264 265 impl FakeBuildSpec { 266 fn new(ids: RelayIds) -> Self { 267 Self { ids } 268 } 269 } 270 271 impl HasRelayIds for FakeBuildSpec { 272 fn identity( 273 &self, 274 key_type: tor_linkspec::RelayIdType, 275 ) -> Option<tor_linkspec::RelayIdRef<'_>> { 276 self.ids.identity(key_type) 277 } 278 } 279 280 /// Assert that two `Option<&T>` point to the same data. 281 macro_rules! assert_opt_ptr_eq { 282 ($a:expr, $b:expr) => { 283 assert_opt_ptr_eq!($a, $b,); 284 }; 285 ($a:expr, $b:expr, $($x:tt)*) => { 286 assert_eq!($a.map(std::ptr::from_ref), $b.map(std::ptr::from_ref), $($x)*); 287 }; 288 } 289 290 /// Calls `f` with every permutation of `list`. Don't use with large lists :) 291 fn with_permutations<T>(list: &[T], mut f: impl FnMut(Vec<&T>)) { 292 use itertools::Itertools; 293 for new_list in list.iter().permutations(list.len()) { 294 f(new_list); 295 } 296 } 297 298 /// Helper to make a fake Ed identity from some bytes. 299 fn ed(a: &[u8]) -> Ed25519Identity { 300 let mut bytes = [0; 32]; 301 bytes[0..a.len()].copy_from_slice(a); 302 bytes.into() 303 } 304 305 /// Helper to make a fake rsa identity from some bytes. 306 fn rsa(a: &[u8]) -> RsaIdentity { 307 let mut bytes = [0; 20]; 308 bytes[0..a.len()].copy_from_slice(a); 309 bytes.into() 310 } 311 312 /// Helper to build a `RelayIds` to make tests shorter. 313 fn ids( 314 rsa: impl Into<Option<RsaIdentity>>, 315 ed: impl Into<Option<Ed25519Identity>>, 316 ) -> RelayIds { 317 let mut ids = tor_linkspec::RelayIdsBuilder::default(); 318 if let Some(rsa) = rsa.into() { 319 ids.rsa_identity(rsa); 320 } 321 if let Some(ed) = ed.into() { 322 ids.ed_identity(ed); 323 } 324 ids.build().unwrap() 325 } 326 327 /// Create an open channel entry. 328 fn open_channel<C>(chan: C) -> OpenEntry<C> { 329 OpenEntry { 330 channel: Arc::new(chan), 331 max_unused_duration: Duration::from_secs(0), 332 } 333 } 334 335 /// Create a pending channel entry with the given IDs. 336 fn pending_channel(ids: RelayIds) -> PendingEntry { 337 use crate::mgr::state::UniqPendingChanId; 338 use futures::FutureExt; 339 use oneshot_fused_workaround as oneshot; 340 341 PendingEntry { 342 ids, 343 pending: oneshot::channel().1.shared(), 344 unique_id: UniqPendingChanId::new(), 345 } 346 } 347 348 #[test] 349 fn best_channel_usable_unusable() { 350 // two channels where only the first is usable 351 let channels = [ 352 ChannelState::Open(open_channel(FakeChannel { 353 usable: true, 354 ids: ids(None, ed(b"A")), 355 })), 356 ChannelState::Open(open_channel(FakeChannel { 357 usable: false, 358 ids: ids(None, ed(b"A")), 359 })), 360 ]; 361 362 // should return the usable channel 363 let target = FakeBuildSpec::new(ids(None, ed(b"A"))); 364 with_permutations(&channels, |x| { 365 assert_opt_ptr_eq!(choose_best_channel(x, &target), Some(&channels[0])); 366 }); 367 } 368 369 #[test] 370 fn best_channel_open_pending() { 371 // a usable open channel and a pending channel 372 let channels = [ 373 ChannelState::Open(open_channel(FakeChannel { 374 usable: true, 375 ids: ids(None, ed(b"A")), 376 })), 377 ChannelState::Building(pending_channel(ids(None, ed(b"A")))), 378 ]; 379 380 // should return the open channel 381 let target = FakeBuildSpec::new(ids(None, ed(b"A"))); 382 with_permutations(&channels, |x| { 383 assert_opt_ptr_eq!(choose_best_channel(x, &target), Some(&channels[0])); 384 }); 385 386 // an unusable open channel and a pending channel 387 let channels = [ 388 ChannelState::Open(open_channel(FakeChannel { 389 usable: false, 390 ids: ids(None, ed(b"A")), 391 })), 392 ChannelState::Building(pending_channel(ids(None, ed(b"A")))), 393 ]; 394 395 // should return the pending channel 396 let target = FakeBuildSpec::new(ids(None, ed(b"A"))); 397 with_permutations(&channels, |x| { 398 assert_opt_ptr_eq!(choose_best_channel(x, &target), Some(&channels[1])); 399 }); 400 } 401 402 #[test] 403 fn best_channel_many() { 404 // some misc channels (as we make `choose_best_channel` more complex, hopeful we can add 405 // more channels here) 406 let channels = [ 407 ChannelState::Open(open_channel(FakeChannel { 408 usable: false, 409 ids: ids(None, ed(b"A")), 410 })), 411 ChannelState::Open(open_channel(FakeChannel { 412 usable: true, 413 ids: ids(None, ed(b"A")), 414 })), 415 ChannelState::Building(pending_channel(ids(None, ed(b"A")))), 416 ChannelState::Building(pending_channel(ids(None, None))), 417 ]; 418 419 // should return the open+usable channel 420 let target = FakeBuildSpec::new(ids(None, ed(b"A"))); 421 with_permutations(&channels, |x| { 422 assert_opt_ptr_eq!(choose_best_channel(x, &target), Some(&channels[1])); 423 }); 424 } 425 426 #[test] 427 fn test_open_channel_is_allowed() { 428 // target with an ed relay id 429 let target = FakeBuildSpec::new(ids(None, ed(b"A"))); 430 431 // not allowed: unusable channel 432 assert!(!open_channel_is_allowed( 433 &open_channel(FakeChannel { 434 usable: false, 435 ids: ids(None, ed(b"A")), 436 }), 437 &target, 438 )); 439 440 // allowed: usable channel with correct relay id 441 assert!(open_channel_is_allowed( 442 &open_channel(FakeChannel { 443 usable: true, 444 ids: ids(None, ed(b"A")), 445 }), 446 &target, 447 )); 448 449 // not allowed: usable channel with incorrect relay id 450 assert!(!open_channel_is_allowed( 451 &open_channel(FakeChannel { 452 usable: true, 453 ids: ids(None, ed(b"B")), 454 }), 455 &target, 456 )); 457 458 // not allowed: usable channel with no relay ids 459 assert!(!open_channel_is_allowed( 460 &open_channel(FakeChannel { 461 usable: true, 462 ids: ids(None, None), 463 }), 464 &target, 465 )); 466 467 // allowed: usable channel with additional relay id 468 assert!(open_channel_is_allowed( 469 &open_channel(FakeChannel { 470 usable: true, 471 ids: ids(rsa(b"X"), ed(b"A")), 472 }), 473 &target, 474 )); 475 476 // not allowed: usable channel with missing ed relay id 477 assert!(!open_channel_is_allowed( 478 &open_channel(FakeChannel { 479 usable: true, 480 ids: ids(rsa(b"X"), None), 481 }), 482 &target, 483 )); 484 485 // target with no relay id 486 let target = FakeBuildSpec::new(ids(None, None)); 487 488 // not allowed: unusable channel 489 assert!(!open_channel_is_allowed( 490 &open_channel(FakeChannel { 491 usable: false, 492 ids: ids(None, None), 493 }), 494 &target, 495 )); 496 497 // allowed: usable channel with no relay ids 498 assert!(open_channel_is_allowed( 499 &open_channel(FakeChannel { 500 usable: true, 501 ids: ids(None, None), 502 }), 503 &target, 504 )); 505 506 // target with multiple relay ids 507 let target = FakeBuildSpec::new(ids(rsa(b"X"), ed(b"A"))); 508 509 // not allowed: unusable channel 510 assert!(!open_channel_is_allowed( 511 &open_channel(FakeChannel { 512 usable: false, 513 ids: ids(rsa(b"X"), ed(b"A")), 514 }), 515 &target, 516 )); 517 518 // allowed: usable channel with correct relay ids 519 assert!(open_channel_is_allowed( 520 &open_channel(FakeChannel { 521 usable: true, 522 ids: ids(rsa(b"X"), ed(b"A")), 523 }), 524 &target, 525 )); 526 527 // not allowed: usable channel with partial relay ids 528 assert!(!open_channel_is_allowed( 529 &open_channel(FakeChannel { 530 usable: true, 531 ids: ids(None, ed(b"A")), 532 }), 533 &target, 534 )); 535 assert!(!open_channel_is_allowed( 536 &open_channel(FakeChannel { 537 usable: true, 538 ids: ids(rsa(b"X"), None), 539 }), 540 &target, 541 )); 542 543 // not allowed: usable channel with one incorrect relay id 544 assert!(!open_channel_is_allowed( 545 &open_channel(FakeChannel { 546 usable: true, 547 ids: ids(rsa(b"X"), ed(b"B")), 548 }), 549 &target, 550 )); 551 assert!(!open_channel_is_allowed( 552 &open_channel(FakeChannel { 553 usable: true, 554 ids: ids(rsa(b"Y"), ed(b"A")), 555 }), 556 &target, 557 )); 558 } 559 560 #[test] 561 fn test_pending_channel_maybe_allowed() { 562 // target with an ed relay id 563 let target = FakeBuildSpec::new(ids(None, ed(b"A"))); 564 565 // allowed: channel with same relay id 566 assert!(pending_channel_maybe_allowed( 567 &pending_channel(ids(None, ed(b"A"))), 568 &target, 569 )); 570 571 // not allowed: channel with additional relay id 572 assert!(!pending_channel_maybe_allowed( 573 &pending_channel(ids(rsa(b"X"), ed(b"A"))), 574 &target, 575 )); 576 577 // target with multiple relay ids 578 let target = FakeBuildSpec::new(ids(rsa(b"X"), ed(b"A"))); 579 580 // allowed: channel with same relay ids 581 assert!(pending_channel_maybe_allowed( 582 &pending_channel(ids(rsa(b"X"), ed(b"A"))), 583 &target, 584 )); 585 586 // allowed: channel with fewer relay ids 587 assert!(pending_channel_maybe_allowed( 588 &pending_channel(ids(None, ed(b"A"))), 589 &target, 590 )); 591 assert!(pending_channel_maybe_allowed( 592 &pending_channel(ids(rsa(b"X"), None)), 593 &target, 594 )); 595 596 // not allowed: channel with no relay ids 597 assert!(!pending_channel_maybe_allowed( 598 &pending_channel(ids(None, None)), 599 &target, 600 )); 601 602 // target with no relay ids 603 let target = FakeBuildSpec::new(ids(None, None)); 604 605 // not allowed: channel with a relay id 606 assert!(!pending_channel_maybe_allowed( 607 &pending_channel(ids(None, ed(b"A"))), 608 &target, 609 )); 610 611 // not allowed: channel with no relay ids 612 assert!(!pending_channel_maybe_allowed( 613 &pending_channel(ids(None, None)), 614 &target, 615 )); 616 } 617 }