lib.rs
1 #![cfg_attr(docsrs, feature(doc_auto_cfg, doc_cfg))] 2 #![doc = include_str!("../README.md")] 3 // @@ begin lint list maintained by maint/add_warning @@ 4 #![allow(renamed_and_removed_lints)] // @@REMOVE_WHEN(ci_arti_stable) 5 #![allow(unknown_lints)] // @@REMOVE_WHEN(ci_arti_nightly) 6 #![warn(missing_docs)] 7 #![warn(noop_method_call)] 8 #![warn(unreachable_pub)] 9 #![warn(clippy::all)] 10 #![deny(clippy::await_holding_lock)] 11 #![deny(clippy::cargo_common_metadata)] 12 #![deny(clippy::cast_lossless)] 13 #![deny(clippy::checked_conversions)] 14 #![warn(clippy::cognitive_complexity)] 15 #![deny(clippy::debug_assert_with_mut_call)] 16 #![deny(clippy::exhaustive_enums)] 17 #![deny(clippy::exhaustive_structs)] 18 #![deny(clippy::expl_impl_clone_on_copy)] 19 #![deny(clippy::fallible_impl_from)] 20 #![deny(clippy::implicit_clone)] 21 #![deny(clippy::large_stack_arrays)] 22 #![warn(clippy::manual_ok_or)] 23 #![deny(clippy::missing_docs_in_private_items)] 24 #![warn(clippy::needless_borrow)] 25 #![warn(clippy::needless_pass_by_value)] 26 #![warn(clippy::option_option)] 27 #![deny(clippy::print_stderr)] 28 #![deny(clippy::print_stdout)] 29 #![warn(clippy::rc_buffer)] 30 #![deny(clippy::ref_option_ref)] 31 #![warn(clippy::semicolon_if_nothing_returned)] 32 #![warn(clippy::trait_duplication_in_bounds)] 33 #![deny(clippy::unchecked_duration_subtraction)] 34 #![deny(clippy::unnecessary_wraps)] 35 #![warn(clippy::unseparated_literal_suffix)] 36 #![deny(clippy::unwrap_used)] 37 #![deny(clippy::mod_module_files)] 38 #![allow(clippy::let_unit_value)] // This can reasonably be done for explicitness 39 #![allow(clippy::uninlined_format_args)] 40 #![allow(clippy::significant_drop_in_scrutinee)] // arti/-/merge_requests/588/#note_2812945 41 #![allow(clippy::result_large_err)] // temporary workaround for arti#587 42 #![allow(clippy::needless_raw_string_hashes)] // complained-about code is fine, often best 43 #![allow(clippy::needless_lifetimes)] // See arti#1765 44 //! <!-- @@ end lint list maintained by maint/add_warning @@ --> 45 46 #![allow(non_upper_case_globals)] 47 #![allow(clippy::upper_case_acronyms)] 48 49 use caret::caret_int; 50 51 use thiserror::Error; 52 53 caret_int! { 54 /// A recognized subprotocol. 55 /// 56 /// These names are kept in sync with the names used in consensus 57 /// documents; the values are kept in sync with the values in the 58 /// cbor document format in the walking onions proposal. 59 /// 60 /// For the full semantics of each subprotocol, see tor-spec.txt. 61 #[derive(Hash,Ord,PartialOrd)] 62 pub struct ProtoKind(u16) { 63 /// Initiating and receiving channels, and getting cells on them. 64 Link = 0, 65 /// Different kinds of authenticate cells 66 LinkAuth = 1, 67 /// CREATE cells, CREATED cells, and the encryption that they 68 /// create. 69 Relay = 2, 70 /// Serving and fetching network directory documents. 71 DirCache = 3, 72 /// Serving onion service descriptors 73 HSDir = 4, 74 /// Providing an onion service introduction point 75 HSIntro = 5, 76 /// Providing an onion service rendezvous point 77 HSRend = 6, 78 /// Describing a relay's functionality using router descriptors. 79 Desc = 7, 80 /// Describing a relay's functionality using microdescriptors. 81 MicroDesc = 8, 82 /// Describing the network as a consensus directory document. 83 Cons = 9, 84 /// Sending and accepting circuit-level padding 85 Padding = 10, 86 /// Improved means of flow control on circuits. 87 FlowCtrl = 11, 88 } 89 } 90 91 /// How many recognized protocols are there? 92 const N_RECOGNIZED: usize = 12; 93 94 /// Representation for a known or unknown protocol. 95 #[derive(Eq, PartialEq, Clone, Debug, Hash, Ord, PartialOrd)] 96 enum Protocol { 97 /// A known protocol; represented by one of ProtoKind. 98 Proto(ProtoKind), 99 /// An unknown protocol; represented by its name. 100 Unrecognized(String), 101 } 102 103 impl Protocol { 104 /// Return true iff `s` is the name of a protocol we do not recognize. 105 fn is_unrecognized(&self, s: &str) -> bool { 106 match self { 107 Protocol::Unrecognized(s2) => s2 == s, 108 _ => false, 109 } 110 } 111 /// Return a string representation of this protocol. 112 fn to_str(&self) -> &str { 113 match self { 114 Protocol::Proto(k) => k.to_str().unwrap_or("<bug>"), 115 Protocol::Unrecognized(s) => s, 116 } 117 } 118 } 119 120 /// Representation of a set of versions supported by a protocol. 121 /// 122 /// For now, we only use this type for unrecognized protocols. 123 #[derive(Debug, Clone, PartialEq, Eq, Hash, Ord, PartialOrd)] 124 struct SubprotocolEntry { 125 /// Which protocol's versions does this describe? 126 proto: Protocol, 127 /// A bit-vector defining which versions are supported. If bit 128 /// `(1<<i)` is set, then protocol version `i` is supported. 129 supported: u64, 130 } 131 132 /// A set of supported or required subprotocol versions. 133 /// 134 /// This type supports both recognized subprotocols (listed in ProtoKind), 135 /// and unrecognized subprotocols (stored by name). 136 /// 137 /// To construct an instance, use the FromStr trait: 138 /// ``` 139 /// use tor_protover::Protocols; 140 /// let p: Result<Protocols,_> = "Link=1-3 LinkAuth=2-3 Relay=1-2".parse(); 141 /// ``` 142 #[derive(Debug, Clone, Default, Eq, PartialEq, Hash)] 143 pub struct Protocols { 144 /// A mapping from protocols' integer encodings to bit-vectors. 145 recognized: [u64; N_RECOGNIZED], 146 /// A vector of unrecognized protocol versions. 147 unrecognized: Vec<SubprotocolEntry>, 148 } 149 150 impl Protocols { 151 /// Return a new empty set of protocol versions. 152 pub fn new() -> Self { 153 Protocols::default() 154 } 155 /// Helper: return true iff this protocol set contains the 156 /// version `ver` of the protocol represented by the integer `proto`. 157 fn supports_recognized_ver(&self, proto: usize, ver: u8) -> bool { 158 if ver > 63 { 159 return false; 160 } 161 if proto >= self.recognized.len() { 162 return false; 163 } 164 (self.recognized[proto] & (1 << ver)) != 0 165 } 166 /// Helper: return true iff this protocol set contains version 167 /// `ver` of the unrecognized protocol represented by the string 168 /// `proto`. 169 /// 170 /// Requires that `proto` is not the name of a recognized protocol. 171 fn supports_unrecognized_ver(&self, proto: &str, ver: u8) -> bool { 172 if ver > 63 { 173 return false; 174 } 175 let ent = self 176 .unrecognized 177 .iter() 178 .find(|ent| ent.proto.is_unrecognized(proto)); 179 match ent { 180 Some(e) => (e.supported & (1 << ver)) != 0, 181 None => false, 182 } 183 } 184 // TODO: Combine these next two functions into one by using a trait. 185 /// Check whether a known protocol version is supported. 186 /// 187 /// ``` 188 /// use tor_protover::*; 189 /// let protos: Protocols = "Link=1-3 HSDir=2,4-5".parse().unwrap(); 190 /// 191 /// assert!(protos.supports_known_subver(ProtoKind::Link, 2)); 192 /// assert!(protos.supports_known_subver(ProtoKind::HSDir, 4)); 193 /// assert!(! protos.supports_known_subver(ProtoKind::HSDir, 3)); 194 /// assert!(! protos.supports_known_subver(ProtoKind::LinkAuth, 3)); 195 /// ``` 196 pub fn supports_known_subver(&self, proto: ProtoKind, ver: u8) -> bool { 197 self.supports_recognized_ver(proto.get() as usize, ver) 198 } 199 /// Check whether a protocol version identified by a string is supported. 200 /// 201 /// ``` 202 /// use tor_protover::*; 203 /// let protos: Protocols = "Link=1-3 Foobar=7".parse().unwrap(); 204 /// 205 /// assert!(protos.supports_subver("Link", 2)); 206 /// assert!(protos.supports_subver("Foobar", 7)); 207 /// assert!(! protos.supports_subver("Link", 5)); 208 /// assert!(! protos.supports_subver("Foobar", 6)); 209 /// assert!(! protos.supports_subver("Wombat", 3)); 210 /// ``` 211 pub fn supports_subver(&self, proto: &str, ver: u8) -> bool { 212 match ProtoKind::from_name(proto) { 213 Some(p) => self.supports_recognized_ver(p.get() as usize, ver), 214 None => self.supports_unrecognized_ver(proto, ver), 215 } 216 } 217 218 /// Parsing helper: Try to add a new entry `ent` to this set of protocols. 219 /// 220 /// Uses `foundmask`, a bit mask saying which recognized protocols 221 /// we've already found entries for. Returns an error if `ent` is 222 /// for a protocol we've already added. 223 fn add(&mut self, foundmask: &mut u64, ent: SubprotocolEntry) -> Result<(), ParseError> { 224 match ent.proto { 225 Protocol::Proto(k) => { 226 let idx = k.get() as usize; 227 let bit = 1 << u64::from(k.get()); 228 if (*foundmask & bit) != 0 { 229 return Err(ParseError::Duplicate); 230 } 231 *foundmask |= bit; 232 self.recognized[idx] = ent.supported; 233 } 234 Protocol::Unrecognized(ref s) => { 235 if self 236 .unrecognized 237 .iter() 238 .any(|ent| ent.proto.is_unrecognized(s)) 239 { 240 return Err(ParseError::Duplicate); 241 } 242 self.unrecognized.push(ent); 243 } 244 } 245 Ok(()) 246 } 247 } 248 249 /// An error representing a failure to parse a set of protocol versions. 250 #[derive(Error, Debug, PartialEq, Eq, Clone)] 251 #[non_exhaustive] 252 pub enum ParseError { 253 /// A protocol version was not in the range 0..=63. 254 #[error("Protocol version out of range")] 255 OutOfRange, 256 /// Some subprotocol or protocol version appeared more than once. 257 #[error("Duplicate protocol entry")] 258 Duplicate, 259 /// The list of protocol versions was malformed in some other way. 260 #[error("Malformed protocol entry")] 261 Malformed, 262 } 263 264 /// Helper: return a new u64 in which bits `lo` through `hi` inclusive 265 /// are set to 1, and all the other bits are set to 0. 266 /// 267 /// In other words, `bitrange(a,b)` is how we represent the range of 268 /// versions `a-b` in a protocol version bitmask. 269 /// 270 /// ```ignore 271 /// # use tor_protover::bitrange; 272 /// assert_eq!(bitrange(0, 5), 0b111111); 273 /// assert_eq!(bitrange(2, 5), 0b111100); 274 /// assert_eq!(bitrange(2, 7), 0b11111100); 275 /// ``` 276 fn bitrange(lo: u64, hi: u64) -> u64 { 277 assert!(lo <= hi && lo <= 63 && hi <= 63); 278 let mut mask = !0; 279 mask <<= 63 - hi; 280 mask >>= 63 - hi + lo; 281 mask <<= lo; 282 mask 283 } 284 285 /// Helper: return true if the provided string is a valid "integer" 286 /// in the form accepted by the protover spec. This is stricter than 287 /// rust's integer parsing format. 288 fn is_good_number(n: &str) -> bool { 289 n.chars().all(|ch| ch.is_ascii_digit()) && !n.starts_with('0') 290 } 291 292 /// A single SubprotocolEntry is parsed from a string of the format 293 /// Name=Versions, where Versions is a comma-separated list of 294 /// integers or ranges of integers. 295 impl std::str::FromStr for SubprotocolEntry { 296 type Err = ParseError; 297 298 fn from_str(s: &str) -> Result<Self, ParseError> { 299 // split the string on the =. 300 let (name, versions) = { 301 let eq_idx = s.find('=').ok_or(ParseError::Malformed)?; 302 (&s[..eq_idx], &s[eq_idx + 1..]) 303 }; 304 // Look up the protocol by name. 305 let proto = match ProtoKind::from_name(name) { 306 Some(p) => Protocol::Proto(p), 307 None => Protocol::Unrecognized(name.to_string()), 308 }; 309 if versions.is_empty() { 310 // We need to handle this case specially, since otherwise 311 // it would be treated below as a single empty value, which 312 // would be rejected. 313 return Ok(SubprotocolEntry { 314 proto, 315 supported: 0, 316 }); 317 } 318 // Construct a bitmask based on the comma-separated versions. 319 let mut supported = 0_u64; 320 for ent in versions.split(',') { 321 // Find and parse lo and hi for a single range of versions. 322 // (If this is not a range, but rather a single version v, 323 // treat it as if it were a range v-v.) 324 let (lo_s, hi_s) = { 325 match ent.find('-') { 326 Some(pos) => (&ent[..pos], &ent[pos + 1..]), 327 None => (ent, ent), 328 } 329 }; 330 if !is_good_number(lo_s) { 331 return Err(ParseError::Malformed); 332 } 333 if !is_good_number(hi_s) { 334 return Err(ParseError::Malformed); 335 } 336 let lo: u64 = lo_s.parse().map_err(|_| ParseError::Malformed)?; 337 let hi: u64 = hi_s.parse().map_err(|_| ParseError::Malformed)?; 338 // Make sure that lo and hi are in-bounds and consistent. 339 if lo > 63 || hi > 63 { 340 return Err(ParseError::OutOfRange); 341 } 342 if lo > hi { 343 return Err(ParseError::Malformed); 344 } 345 let mask = bitrange(lo, hi); 346 // Make sure that no version is included twice. 347 if (supported & mask) != 0 { 348 return Err(ParseError::Duplicate); 349 } 350 // Add the appropriate bits to the mask. 351 supported |= mask; 352 } 353 Ok(SubprotocolEntry { proto, supported }) 354 } 355 } 356 357 /// A Protocols set can be parsed from a string according to the 358 /// format used in Tor consensus documents. 359 /// 360 /// A protocols set is represented by a space-separated list of 361 /// entries. Each entry is of the form `Name=Versions`, where `Name` 362 /// is the name of a protocol, and `Versions` is a comma-separated 363 /// list of version numbers and version ranges. Each version range is 364 /// a pair of integers separated by `-`. 365 /// 366 /// No protocol name may be listed twice. No version may be listed 367 /// twice for a single protocol. All versions must be in range 0 368 /// through 63 inclusive. 369 impl std::str::FromStr for Protocols { 370 type Err = ParseError; 371 372 fn from_str(s: &str) -> Result<Self, ParseError> { 373 let mut result = Protocols::new(); 374 let mut foundmask = 0_u64; 375 for ent in s.split(' ') { 376 if ent.is_empty() { 377 continue; 378 } 379 380 let s: SubprotocolEntry = ent.parse()?; 381 result.add(&mut foundmask, s)?; 382 } 383 result.unrecognized.sort(); 384 Ok(result) 385 } 386 } 387 388 /// Given a bitmask, return a list of the bits set in the mask, as a 389 /// String in the format expected by Tor consensus documents. 390 /// 391 /// This implementation constructs ranges greedily. For example, the 392 /// bitmask `0b0111011` will be represented as `0-1,3-5`, and not 393 /// `0,1,3,4,5` or `0,1,3-5`. 394 /// 395 /// ```ignore 396 /// # use tor_protover::dumpmask; 397 /// assert_eq!(dumpmask(0b111111), "0-5"); 398 /// assert_eq!(dumpmask(0b111100), "2-5"); 399 /// assert_eq!(dumpmask(0b11111100), "2-7"); 400 /// ``` 401 fn dumpmask(mut mask: u64) -> String { 402 /// Helper: push a range (which may be a singleton) onto `v`. 403 fn append(v: &mut Vec<String>, lo: u32, hi: u32) { 404 if lo == hi { 405 v.push(lo.to_string()); 406 } else { 407 v.push(format!("{}-{}", lo, hi)); 408 } 409 } 410 // We'll be building up our result here, then joining it with 411 // commas. 412 let mut result = Vec::new(); 413 // This implementation is a little tricky, but it should be more 414 // efficient than a raw search. Basically, we're using the 415 // function u64::trailing_zeros to count how large each range of 416 // 1s or 0s is, and then shifting by that amount. 417 418 // How many bits have we already shifted `mask`? 419 let mut shift = 0; 420 while mask != 0 { 421 let zeros = mask.trailing_zeros(); 422 mask >>= zeros; 423 shift += zeros; 424 let ones = mask.trailing_ones(); 425 append(&mut result, shift, shift + ones - 1); 426 shift += ones; 427 if ones == 64 { 428 // We have to do this check to avoid overflow when formatting 429 // the range `0-63`. 430 break; 431 } 432 mask >>= ones; 433 } 434 result.join(",") 435 } 436 437 /// The Display trait formats a protocol set in the format expected by Tor 438 /// consensus documents. 439 /// 440 /// ``` 441 /// use tor_protover::*; 442 /// let protos: Protocols = "Link=1,2,3 Foobar=7 Relay=2".parse().unwrap(); 443 /// assert_eq!(format!("{}", protos), 444 /// "Foobar=7 Link=1-3 Relay=2"); 445 /// ``` 446 impl std::fmt::Display for Protocols { 447 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { 448 let mut entries = Vec::new(); 449 for (idx, mask) in self.recognized.iter().enumerate() { 450 if *mask != 0 { 451 let pk: ProtoKind = (idx as u16).into(); 452 entries.push(format!("{}={}", pk, dumpmask(*mask))); 453 } 454 } 455 for ent in &self.unrecognized { 456 if ent.supported != 0 { 457 entries.push(format!( 458 "{}={}", 459 ent.proto.to_str(), 460 dumpmask(ent.supported) 461 )); 462 } 463 } 464 // This sort is required. 465 entries.sort(); 466 write!(f, "{}", entries.join(" ")) 467 } 468 } 469 470 #[cfg(test)] 471 mod test { 472 // @@ begin test lint list maintained by maint/add_warning @@ 473 #![allow(clippy::bool_assert_comparison)] 474 #![allow(clippy::clone_on_copy)] 475 #![allow(clippy::dbg_macro)] 476 #![allow(clippy::mixed_attributes_style)] 477 #![allow(clippy::print_stderr)] 478 #![allow(clippy::print_stdout)] 479 #![allow(clippy::single_char_pattern)] 480 #![allow(clippy::unwrap_used)] 481 #![allow(clippy::unchecked_duration_subtraction)] 482 #![allow(clippy::useless_vec)] 483 #![allow(clippy::needless_pass_by_value)] 484 //! <!-- @@ end test lint list maintained by maint/add_warning @@ --> 485 use super::*; 486 487 #[test] 488 fn test_bitrange() { 489 assert_eq!(0b1, bitrange(0, 0)); 490 assert_eq!(0b10, bitrange(1, 1)); 491 assert_eq!(0b11, bitrange(0, 1)); 492 assert_eq!(0b1111110000000, bitrange(7, 12)); 493 assert_eq!(!0, bitrange(0, 63)); 494 } 495 496 #[test] 497 fn test_dumpmask() { 498 assert_eq!("", dumpmask(0)); 499 assert_eq!("0-5", dumpmask(0b111111)); 500 assert_eq!("4-5", dumpmask(0b110000)); 501 assert_eq!("1,4-5", dumpmask(0b110010)); 502 assert_eq!("0-63", dumpmask(!0)); 503 } 504 505 #[test] 506 fn test_canonical() -> Result<(), ParseError> { 507 fn t(orig: &str, canonical: &str) -> Result<(), ParseError> { 508 let protos: Protocols = orig.parse()?; 509 let enc = format!("{}", protos); 510 assert_eq!(enc, canonical); 511 Ok(()) 512 } 513 514 t("", "")?; 515 t(" ", "")?; 516 t("Link=5,6,7,9 Relay=4-7,2", "Link=5-7,9 Relay=2,4-7")?; 517 t("FlowCtrl= Padding=8,7 Desc=1-5,6-8", "Desc=1-8 Padding=7-8")?; 518 t("Zelda=7 Gannon=3,6 Link=4", "Gannon=3,6 Link=4 Zelda=7")?; 519 520 Ok(()) 521 } 522 523 #[test] 524 fn test_invalid() { 525 fn t(s: &str) -> ParseError { 526 let protos: Result<Protocols, ParseError> = s.parse(); 527 assert!(protos.is_err()); 528 protos.err().unwrap() 529 } 530 531 assert_eq!(t("Link=1-100"), ParseError::OutOfRange); 532 assert_eq!(t("Zelda=100"), ParseError::OutOfRange); 533 assert_eq!(t("Link=100-200"), ParseError::OutOfRange); 534 535 assert_eq!(t("Link=1,1"), ParseError::Duplicate); 536 assert_eq!(t("Link=1 Link=1"), ParseError::Duplicate); 537 assert_eq!(t("Link=1 Link=3"), ParseError::Duplicate); 538 assert_eq!(t("Zelda=1 Zelda=3"), ParseError::Duplicate); 539 540 assert_eq!(t("Link=Zelda"), ParseError::Malformed); 541 assert_eq!(t("Link=6-2"), ParseError::Malformed); 542 assert_eq!(t("Link=6-"), ParseError::Malformed); 543 assert_eq!(t("Link=6-,2"), ParseError::Malformed); 544 assert_eq!(t("Link=1,,2"), ParseError::Malformed); 545 assert_eq!(t("Link=6-frog"), ParseError::Malformed); 546 assert_eq!(t("Link=gannon-9"), ParseError::Malformed); 547 assert_eq!(t("Link Zelda"), ParseError::Malformed); 548 549 assert_eq!(t("Link=01"), ParseError::Malformed); 550 assert_eq!(t("Link=waffle"), ParseError::Malformed); 551 assert_eq!(t("Link=1_1"), ParseError::Malformed); 552 } 553 554 #[test] 555 fn test_supports() -> Result<(), ParseError> { 556 let p: Protocols = "Link=4,5-7 Padding=2 Lonk=1-3,5".parse()?; 557 558 assert!(p.supports_known_subver(ProtoKind::Padding, 2)); 559 assert!(!p.supports_known_subver(ProtoKind::Padding, 1)); 560 assert!(p.supports_known_subver(ProtoKind::Link, 6)); 561 assert!(!p.supports_known_subver(ProtoKind::Link, 255)); 562 assert!(!p.supports_known_subver(ProtoKind::Cons, 1)); 563 assert!(!p.supports_known_subver(ProtoKind::Cons, 0)); 564 assert!(p.supports_subver("Link", 6)); 565 assert!(!p.supports_subver("link", 6)); 566 assert!(!p.supports_subver("Cons", 0)); 567 assert!(p.supports_subver("Lonk", 3)); 568 assert!(!p.supports_subver("Lonk", 4)); 569 assert!(!p.supports_subver("lonk", 3)); 570 assert!(!p.supports_subver("Lonk", 64)); 571 572 Ok(()) 573 } 574 }