Lines
97.25 %
Functions
61.22 %
Branches
100 %
//! Implementation of Tor's "subprotocol versioning" feature.
//!
//! # Overview
//! The Tor system is built out of numerous "subprotocols" that are
//! versioned more or less independently. The `tor-protover` crate
//! implements parsing and handling for these subprotocol versions, so
//! that different Tor instances know which parts of the protocol
//! they support.
//! Subprotocol versions are also used to determine which versions of
//! the protocol are required to connect to the network (or just
//! recommended).
//! For more details, see [tor-spec.txt](https://spec.torproject.org/tor-spec)
//! section 9.
//! This crate is part of
//! [Arti](https://gitlab.torproject.org/tpo/core/arti/), a project to
//! implement [Tor](https://www.torproject.org/) in Rust.
//! It's unlikely to be of general interest
//! unless you are writing a Tor implementation, or a program that
//! needs to examine fine-grained details of the Tor network.
//! ## Design notes
//! We're giving `tor-protover` its own crate within arti because it
//! needs to be used to multiple higher level crates that do not
//! themselves depend on one another. (For example, [`tor-proto`]
//! needs to know which variant of a subprotocol can be used with a
//! given relay, whereas [`tor-netdoc`] needs to parse lists of
//! subprotocol versions from directory documents. Eventually,
//! [`arti-client`] will need to check its own list of supported
//! protocols against the required list in the consensus.)
#![deny(missing_docs)]
#![allow(non_upper_case_globals)]
#![warn(noop_method_call)]
#![deny(unreachable_pub)]
#![warn(clippy::all)]
#![deny(clippy::await_holding_lock)]
#![deny(clippy::cargo_common_metadata)]
#![deny(clippy::cast_lossless)]
#![deny(clippy::checked_conversions)]
#![warn(clippy::cognitive_complexity)]
#![deny(clippy::debug_assert_with_mut_call)]
#![deny(clippy::exhaustive_enums)]
#![deny(clippy::exhaustive_structs)]
#![deny(clippy::expl_impl_clone_on_copy)]
#![deny(clippy::fallible_impl_from)]
#![deny(clippy::implicit_clone)]
#![deny(clippy::large_stack_arrays)]
#![warn(clippy::manual_ok_or)]
#![deny(clippy::missing_docs_in_private_items)]
#![deny(clippy::missing_panics_doc)]
#![warn(clippy::needless_borrow)]
#![warn(clippy::needless_pass_by_value)]
#![warn(clippy::option_option)]
#![warn(clippy::rc_buffer)]
#![deny(clippy::ref_option_ref)]
#![warn(clippy::semicolon_if_nothing_returned)]
#![warn(clippy::trait_duplication_in_bounds)]
#![deny(clippy::unnecessary_wraps)]
#![warn(clippy::unseparated_literal_suffix)]
#![deny(clippy::unwrap_used)]
#![allow(clippy::upper_case_acronyms)]
use caret::caret_int;
use thiserror::Error;
caret_int! {
/// A recognized subprotocol.
///
/// These names are kept in sync with the names used in consensus
/// documents; the values are kept in sync with the values in the
/// cbor document format in the walking onions proposal.
/// For the full semantics of each subprotocol, see tor-spec.txt.
pub struct ProtoKind(u16) {
/// Initiating and receiving channels, and getting cells on them.
Link = 0,
/// Different kinds of authenticate cells
LinkAuth = 1,
/// CREATE cells, CREATED cells, and the encryption that they
/// create.
Relay = 2,
/// Serving and fetching network directory documents.
DirCache = 3,
/// Serving onion service descriptors
HSDir = 4,
/// Providing an onion service introduction point
HSIntro = 5,
/// Providing an onion service rendezvous point
HSRend = 6,
/// Describing a relay's functionality using router descriptors.
Desc = 7,
/// Describing a relay's functionality using microdescriptors.
MicroDesc = 8,
/// Describing the network as a consensus directory document.
Cons = 9,
/// Sending and accepting circuit-level padding
Padding = 10,
/// Improved means of flow control on circuits.
FlowCtrl = 11,
}
/// How many recognized protocols are there?
const N_RECOGNIZED: usize = 12;
/// Representation for a known or unknown protocol.
#[derive(Eq, PartialEq, Clone, Debug)]
enum Protocol {
/// A known protocol; represented by one of ProtoKind.
Proto(ProtoKind),
/// An unknown protocol; represented by its name.
Unrecognized(String),
impl Protocol {
/// Return true iff `s` is the name of a protocol we do not recognize.
fn is_unrecognized(&self, s: &str) -> bool {
match self {
Protocol::Unrecognized(s2) => s2 == s,
_ => false,
/// Return a string representation of this protocol.
fn to_str(&self) -> &str {
Protocol::Proto(k) => k.to_str().unwrap_or("<bug>"),
Protocol::Unrecognized(s) => s,
/// Representation of a set of versions supported by a protocol.
/// For now, we only use this type for unrecognized protocols.
#[derive(Debug, Clone)]
struct SubprotocolEntry {
/// Which protocol's versions does this describe?
proto: Protocol,
/// A bit-vector defining which versions are supported. If bit
/// `(1<<i)` is set, then protocol version `i` is supported.
supported: u64,
/// A set of supported or required subprotocol versions.
/// This type supports both recognized subprotocols (listed in ProtoKind),
/// and unrecognized subprotocols (stored by name).
/// To construct an instance, use the FromStr trait:
/// ```
/// use tor_protover::Protocols;
/// let p: Result<Protocols,_> = "Link=1-3 LinkAuth=2-3 Relay=1-2".parse();
#[derive(Debug, Clone, Default)]
pub struct Protocols {
/// A mapping from protocols' integer encodings to bit-vectors.
recognized: [u64; N_RECOGNIZED],
/// A vector of unrecognized protocol versions.
unrecognized: Vec<SubprotocolEntry>,
impl Protocols {
/// Return a new empty set of protocol versions.
pub fn new() -> Self {
Protocols::default()
/// Helper: return true iff this protocol set contains the
/// version `ver` of the protocol represented by the integer `proto`.
fn supports_recognized_ver(&self, proto: usize, ver: u8) -> bool {
if ver > 63 {
return false;
if proto >= self.recognized.len() {
(self.recognized[proto] & (1 << ver)) != 0
/// Helper: return true iff this protocol set contains version
/// `ver` of the unrecognized protocol represented by the string
/// `proto`.
/// Requires that `proto` is not the name of a recognized protocol.
fn supports_unrecognized_ver(&self, proto: &str, ver: u8) -> bool {
let ent = self
.unrecognized
.iter()
.find(|ent| ent.proto.is_unrecognized(proto));
match ent {
Some(e) => (e.supported & (1 << ver)) != 0,
None => false,
// TODO: Combine these next two functions into one by using a trait.
/// Check whether a known protocol version is supported.
/// use tor_protover::*;
/// let protos: Protocols = "Link=1-3 HSDir=2,4-5".parse().unwrap();
/// assert!(protos.supports_known_subver(ProtoKind::Link, 2));
/// assert!(protos.supports_known_subver(ProtoKind::HSDir, 4));
/// assert!(! protos.supports_known_subver(ProtoKind::HSDir, 3));
/// assert!(! protos.supports_known_subver(ProtoKind::LinkAuth, 3));
pub fn supports_known_subver(&self, proto: ProtoKind, ver: u8) -> bool {
self.supports_recognized_ver(proto.get() as usize, ver)
/// Check whether a protocol version identified by a string is supported.
/// let protos: Protocols = "Link=1-3 Foobar=7".parse().unwrap();
/// assert!(protos.supports_subver("Link", 2));
/// assert!(protos.supports_subver("Foobar", 7));
/// assert!(! protos.supports_subver("Link", 5));
/// assert!(! protos.supports_subver("Foobar", 6));
/// assert!(! protos.supports_subver("Wombat", 3));
pub fn supports_subver(&self, proto: &str, ver: u8) -> bool {
match ProtoKind::from_name(proto) {
Some(p) => self.supports_recognized_ver(p.get() as usize, ver),
None => self.supports_unrecognized_ver(proto, ver),
/// Parsing helper: Try to add a new entry `ent` to this set of protocols.
/// Uses `foundmask`, a bit mask saying which recognized protocols
/// we've already found entries for. Returns an error if `ent` is
/// for a protocol we've already added.
fn add(&mut self, foundmask: &mut u64, ent: SubprotocolEntry) -> Result<(), ParseError> {
match ent.proto {
Protocol::Proto(k) => {
let idx = k.get() as usize;
let bit = 1 << u64::from(k.get());
if (*foundmask & bit) != 0 {
return Err(ParseError::Duplicate);
*foundmask |= bit;
self.recognized[idx] = ent.supported;
Protocol::Unrecognized(ref s) => {
if self
.any(|ent| ent.proto.is_unrecognized(s))
{
self.unrecognized.push(ent);
Ok(())
/// An error representing a failure to parse a set of protocol versions.
#[derive(Error, Debug, PartialEq, Eq, Clone)]
#[non_exhaustive]
pub enum ParseError {
/// A protocol version was not in the range 0..=63.
#[error("protocol version out of range")]
OutOfRange,
/// Some subprotocol or protocol version appeared more than once.
#[error("duplicate protocol entry")]
Duplicate,
/// The list of protocol versions was malformed in some other way.
#[error("malformed protocol entry")]
Malformed,
/// Helper: return a new u64 in which bits `lo` through `hi` inclusive
/// are set to 1, and all the other bits are set to 0.
/// In other words, `bitrange(a,b)` is how we represent the range of
/// versions `a-b` in a protocol version bitmask.
/// ```ignore
/// # use tor_protover::bitrange;
/// assert_eq!(bitrange(0, 5), 0b111111);
/// assert_eq!(bitrange(2, 5), 0b111100);
/// assert_eq!(bitrange(2, 7), 0b11111100);
fn bitrange(lo: u64, hi: u64) -> u64 {
assert!(lo <= hi && lo <= 63 && hi <= 63);
let mut mask = !0;
mask <<= 63 - hi;
mask >>= 63 - hi + lo;
mask <<= lo;
mask
/// Helper: return true if the provided string is a valid "integer"
/// in the form accepted by the protover spec. This is stricter than
/// rust's integer parsing format.
fn is_good_number(n: &str) -> bool {
n.chars().all(|ch| ch.is_ascii_digit()) && !n.starts_with('0')
/// A single SubprotocolEntry is parsed from a string of the format
/// Name=Versions, where Versions is a comma-separated list of
/// integers or ranges of integers.
impl std::str::FromStr for SubprotocolEntry {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, ParseError> {
// split the string on the =.
let (name, versions) = {
let eq_idx = s.find('=').ok_or(ParseError::Malformed)?;
(&s[..eq_idx], &s[eq_idx + 1..])
};
// Look up the protocol by name.
let proto = match ProtoKind::from_name(name) {
Some(p) => Protocol::Proto(p),
None => Protocol::Unrecognized(name.to_string()),
if versions.is_empty() {
// We need to handle this case specially, since otherwise
// it would be treated below as a single empty value, which
// would be rejected.
return Ok(SubprotocolEntry {
proto,
supported: 0,
});
// Construct a bitmask based on the comma-separated versions.
let mut supported = 0_u64;
for ent in versions.split(',') {
// Find and parse lo and hi for a single range of versions.
// (If this is not a range, but rather a single version v,
// treat it as if it were a range v-v.)
let (lo_s, hi_s) = {
match ent.find('-') {
Some(pos) => (&ent[..pos], &ent[pos + 1..]),
None => (ent, ent),
if !is_good_number(lo_s) {
return Err(ParseError::Malformed);
if !is_good_number(hi_s) {
let lo: u64 = lo_s.parse().map_err(|_| ParseError::Malformed)?;
let hi: u64 = hi_s.parse().map_err(|_| ParseError::Malformed)?;
// Make sure that lo and hi are in-bounds and consistent.
if lo > 63 || hi > 63 {
return Err(ParseError::OutOfRange);
if lo > hi {
let mask = bitrange(lo, hi);
// Make sure that no version is included twice.
if (supported & mask) != 0 {
// Add the appropriate bits to the mask.
supported |= mask;
Ok(SubprotocolEntry { proto, supported })
/// A Protocols set can be parsed from a string according to the
/// format used in Tor consensus documents.
/// A protocols set is represented by a space-separated list of
/// entries. Each entry is of the form `Name=Versions`, where `Name`
/// is the name of a protocol, and `Versions` is a comma-separated
/// list of version numbers and version ranges. Each version range is
/// a pair of integers separated by `-`.
/// No protocol name may be listed twice. No version may be listed
/// twice for a single protocol. All versions must be in range 0
/// through 63 inclusive.
impl std::str::FromStr for Protocols {
let mut result = Protocols::new();
let mut foundmask = 0_u64;
for ent in s.split(' ') {
if ent.is_empty() {
continue;
let s: SubprotocolEntry = ent.parse()?;
result.add(&mut foundmask, s)?;
Ok(result)
/// Given a bitmask, return a list of the bits set in the mask, as a
/// String in the format expected by Tor consensus documents.
/// This implementation constructs ranges greedily. For example, the
/// bitmask `0b0111011` will be represented as `0-1,3-5`, and not
/// `0,1,3,4,5` or `0,1,3-5`.
/// # use tor_protover::dumpmask;
/// assert_eq!(dumpmask(0b111111), "0-5");
/// assert_eq!(dumpmask(0b111100), "2-5");
/// assert_eq!(dumpmask(0b11111100), "2-7");
fn dumpmask(mut mask: u64) -> String {
/// Helper: push a range (which may be a singleton) onto `v`.
fn append(v: &mut Vec<String>, lo: u32, hi: u32) {
if lo == hi {
v.push(lo.to_string());
} else {
v.push(format!("{}-{}", lo, hi));
// We'll be building up our result here, then joining it with
// commas.
let mut result = Vec::new();
// This implementation is a little tricky, but it should be more
// efficient than a raw search. Basically, we're using the
// function u64::trailing_zeros to count how large each range of
// 1s or 0s is, and then shifting by that amount.
// How many bits have we already shifted `mask`?
let mut shift = 0;
while mask != 0 {
let zeros = mask.trailing_zeros();
mask >>= zeros;
shift += zeros;
let ones = mask.trailing_ones();
append(&mut result, shift, shift + ones - 1);
shift += ones;
if ones == 64 {
// We have to do this check to avoid overflow when formatting
// the range `0-63`.
break;
mask >>= ones;
result.join(",")
/// The Display trait formats a protocol set in the format expected by Tor
/// consensus documents.
/// let protos: Protocols = "Link=1,2,3 Foobar=7 Relay=2".parse().unwrap();
/// assert_eq!(format!("{}", protos),
/// "Foobar=7 Link=1-3 Relay=2");
impl std::fmt::Display for Protocols {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
let mut entries = Vec::new();
for (idx, mask) in self.recognized.iter().enumerate() {
if *mask != 0 {
let pk: ProtoKind = (idx as u16).into();
entries.push(format!("{}={}", pk, dumpmask(*mask)));
for ent in &self.unrecognized {
if ent.supported != 0 {
entries.push(format!(
"{}={}",
ent.proto.to_str(),
dumpmask(ent.supported)
));
// This sort is required.
entries.sort();
write!(f, "{}", entries.join(" "))
#[cfg(test)]
mod test {
#![allow(clippy::unwrap_used)]
use super::*;
#[test]
fn test_bitrange() {
assert_eq!(0b1, bitrange(0, 0));
assert_eq!(0b10, bitrange(1, 1));
assert_eq!(0b11, bitrange(0, 1));
assert_eq!(0b1111110000000, bitrange(7, 12));
assert_eq!(!0, bitrange(0, 63));
fn test_dumpmask() {
assert_eq!("", dumpmask(0));
assert_eq!("0-5", dumpmask(0b111111));
assert_eq!("4-5", dumpmask(0b110000));
assert_eq!("1,4-5", dumpmask(0b110010));
assert_eq!("0-63", dumpmask(!0));
fn test_canonical() -> Result<(), ParseError> {
fn t(orig: &str, canonical: &str) -> Result<(), ParseError> {
let protos: Protocols = orig.parse()?;
let enc = format!("{}", protos);
assert_eq!(enc, canonical);
t("", "")?;
t(" ", "")?;
t("Link=5,6,7,9 Relay=4-7,2", "Link=5-7,9 Relay=2,4-7")?;
t("FlowCtrl= Padding=8,7 Desc=1-5,6-8", "Desc=1-8 Padding=7-8")?;
t("Zelda=7 Gannon=3,6 Link=4", "Gannon=3,6 Link=4 Zelda=7")?;
fn test_invalid() {
fn t(s: &str) -> ParseError {
let protos: Result<Protocols, ParseError> = s.parse();
assert!(protos.is_err());
protos.err().unwrap()
assert_eq!(t("Link=1-100"), ParseError::OutOfRange);
assert_eq!(t("Zelda=100"), ParseError::OutOfRange);
assert_eq!(t("Link=100-200"), ParseError::OutOfRange);
assert_eq!(t("Link=1,1"), ParseError::Duplicate);
assert_eq!(t("Link=1 Link=1"), ParseError::Duplicate);
assert_eq!(t("Link=1 Link=3"), ParseError::Duplicate);
assert_eq!(t("Zelda=1 Zelda=3"), ParseError::Duplicate);
assert_eq!(t("Link=Zelda"), ParseError::Malformed);
assert_eq!(t("Link=6-2"), ParseError::Malformed);
assert_eq!(t("Link=6-"), ParseError::Malformed);
assert_eq!(t("Link=6-,2"), ParseError::Malformed);
assert_eq!(t("Link=1,,2"), ParseError::Malformed);
assert_eq!(t("Link=6-frog"), ParseError::Malformed);
assert_eq!(t("Link=gannon-9"), ParseError::Malformed);
assert_eq!(t("Link Zelda"), ParseError::Malformed);
assert_eq!(t("Link=01"), ParseError::Malformed);
assert_eq!(t("Link=waffle"), ParseError::Malformed);
assert_eq!(t("Link=1_1"), ParseError::Malformed);
fn test_supports() -> Result<(), ParseError> {
let p: Protocols = "Link=4,5-7 Padding=2 Lonk=1-3,5".parse()?;
assert!(p.supports_known_subver(ProtoKind::Padding, 2));
assert!(!p.supports_known_subver(ProtoKind::Padding, 1));
assert!(p.supports_known_subver(ProtoKind::Link, 6));
assert!(!p.supports_known_subver(ProtoKind::Link, 255));
assert!(!p.supports_known_subver(ProtoKind::Cons, 1));
assert!(!p.supports_known_subver(ProtoKind::Cons, 0));
assert!(p.supports_subver("Link", 6));
assert!(!p.supports_subver("link", 6));
assert!(!p.supports_subver("Cons", 0));
assert!(p.supports_subver("Lonk", 3));
assert!(!p.supports_subver("Lonk", 4));
assert!(!p.supports_subver("lonk", 3));
assert!(!p.supports_subver("Lonk", 64));