Lines
92.5 %
Functions
72.22 %
Branches
100 %
//! Logic for selecting relays from a network directory,
//! and reporting the outcome of such a selection.
use crate::{LowLevelRelayPredicate, RelayExclusion, RelayRestriction, RelayUsage};
use tor_basic_utils::iter::FilterCount;
use tor_netdir::{NetDir, Relay, WeightRole};
use std::fmt;
/// Description of the requirements that a relay must implement in order to be selected.
///
/// This object is used to pick a [`Relay`] from a [`NetDir`], or to ensure that a
/// previously selected `Relay` still meets its requirements.
/// The requirements on a relay can be _strict_ or _flexible_.
/// If any restriction is flexible, and relay selection fails at first,
/// we _relax_ the `RelaySelector` by removing that restriction,
/// and trying again,
/// before we give up completely.
#[derive(Clone, Debug)]
pub struct RelaySelector<'a> {
/// A usage that the relay must support.
/// Invariant: This is a RelayUsage.
usage: Restr<'a>,
/// An excludion that the relay must obey.
/// Invariant: This a RelayExclusion.
exclusion: Restr<'a>,
/// Other restrictions that a Relay must obey in order to be selected.
other_restrictions: Vec<Restr<'a>>,
}
/// A single restriction, along with a flag about whether it's strict.
struct Restr<'a> {
/// The underlying restriction.
restriction: RelayRestriction<'a>,
/// Is the restriction strict or flexible?
strict: bool,
impl<'a> Restr<'a> {
/// Try relaxing this restriction.
/// (If this can't be relaxed, just return a copy of it.)
fn maybe_relax(&self) -> Self {
if self.strict {
self.clone()
} else {
Self {
restriction: self.restriction.relax(),
// The new restriction is always strict, since we don't want to
// relax it any further.
strict: true,
/// Information about how a given selection was generated.
/// Records the specifics of how many relays were excluded by each
/// requirement,
/// whether we had to relax the selector, and so on.
/// The caller should typically decide whether an error or warning is necessary,
/// and if so use this to generate a formattable report about what went wrong.
#[derive(Debug, Clone)]
pub struct SelectionInfo<'a> {
/// Outcome of our first attempt to pick a relay.
first_try: FilterCounts,
/// Present if we tried again with a relaxed version of our
/// flexible members.
relaxed_try: Option<FilterCounts>,
/// True if we eventually succeeded in picking a relay.
succeeded: bool,
/// The `RelaySelector` that was used.
/// Used to produce information about which restriction is which.
in_selection: &'a RelaySelector<'a>,
impl<'a> SelectionInfo<'a> {
/// Return true if we eventually picked at least one relay.
/// (We report success on `pick_n_relays` if we returned a nonzero
/// number of relays, even if it is smaller than the requested number.)
pub fn success(&self) -> bool {
self.succeeded
/// Return true if picked at least one relay,
/// but only after relaxing our initial selector.
pub fn result_is_relaxed_success(&self) -> bool {
self.relaxed_try.is_some() && self.succeeded
impl<'a> fmt::Display for SelectionInfo<'a> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match (self.succeeded, &self.relaxed_try) {
(true, None) => write!(f, "Success: {}", FcDisp(&self.first_try, self.in_selection))?,
(false, None) => write!(f, "Failed: {}", FcDisp(&self.first_try, self.in_selection))?,
(true, Some(retry)) => write!(
f,
"Failed at first, then succeeded. At first, {}. After relaxing requirements, {}",
FcDisp(&self.first_try, self.in_selection),
FcDisp(retry, self.in_selection)
)?,
(false, Some(retry)) => write!(
"Failed even after relaxing requirement. At first, {}. After relaxing requirements, {}",
};
Ok(())
/// A list of [`FilterCount`], associated with a [`RelaySelector`].
struct FilterCounts {
/// The [`FilterCount`] created by each restriction.
/// This `Vec` has the same length as the list of restrictions; its items
/// refer to them one by one.
/// Because restrictions are applied as a set of filters, each successive
/// count will only include the relays not excluded by the previous filters.
counts: Vec<FilterCount>,
impl FilterCounts {
/// Create a new empty `FilterCounts`.
fn new(selector: &RelaySelector) -> Self {
let counts = vec![FilterCount::default(); selector.n_restrictions()];
FilterCounts { counts }
/// Helper to display filter counts
struct FcDisp<'a>(&'a FilterCounts, &'a RelaySelector<'a>);
impl<'a> fmt::Display for FcDisp<'a> {
let counts = &self.0.counts;
let restrictions = self.1.all_restrictions();
write!(f, "rejected ")?;
let mut first = true;
let mut found_any_rejected = false;
for (c, r) in counts.iter().zip(restrictions) {
if c.n_rejected == 0 {
continue;
if let Some(desc) = r.restriction.rejection_description() {
if first {
first = false;
write!(f, "; ")?;
write!(f, "{} as {}", c.display_frac_rejected(), desc)?;
found_any_rejected = true;
debug_assert_eq!(c.n_rejected, 0);
if !found_any_rejected {
write!(f, "none")?;
impl<'a> RelaySelector<'a> {
/// Create a new RelaySelector to pick relays with a given
/// [`RelayUsage`] and [`RelayExclusion`].
/// Both arguments are required, since every caller should consider them explicitly.
/// The provided usage and exclusion are strict by default.
// TODO: Possibly have this take a struct with named pieces instead, when we
// get a third thing that we want everybody to think about.
pub fn new(usage: RelayUsage, exclusion: RelayExclusion<'a>) -> Self {
usage: Restr {
restriction: RelayRestriction::for_usage(usage),
},
exclusion: Restr {
restriction: exclusion.into(),
other_restrictions: vec![],
/// Mark the originally provided `RelayUsage` as flexible.
pub fn mark_usage_flexible(&mut self) {
self.usage.strict = false;
/// Mark the originally provided `RelayExclusion` as flexible.
pub fn mark_exclusion_flexible(&mut self) {
self.exclusion.strict = false;
/// Add a new _strict_ [`RelayRestriction`] to this selector.
pub fn push_restriction(&mut self, restriction: RelayRestriction<'a>) {
self.push_inner(restriction, true);
/// Add a new _flexible_ [`RelayRestriction`] to this selector.
pub fn push_flexible_restriction(&mut self, restriction: RelayRestriction<'a>) {
self.push_inner(restriction, false);
/// Helper to implement adding a new restriction.
fn push_inner(&mut self, restriction: RelayRestriction<'a>, strict: bool) {
self.other_restrictions.push(Restr {
restriction,
strict,
});
/// Return the usage for this selector.
pub fn usage(&self) -> &RelayUsage {
// See invariants for explanation of why these `expects` are safe.
self.usage
.restriction
.as_usage()
.expect("Usage not a usage!?")
/// Return the [`WeightRole`] to use when randomly picking relays according
/// to this selector.
fn weight_role(&self) -> WeightRole {
self.usage().selection_weight_role()
/// Return true if `relay` is one that this selector would pick.
pub fn permits_relay(&self, relay: &tor_netdir::Relay<'_>) -> bool {
self.low_level_predicate_permits_relay(relay)
/// Return an iterator that yields each restriction from this selector,
/// including the usage and exclusion.
fn all_restrictions(&self) -> impl Iterator<Item = &Restr<'a>> {
use std::iter::once;
once(&self.usage)
.chain(once(&self.exclusion))
.chain(self.other_restrictions.iter())
/// Return the number of restrictions in this selector,
fn n_restrictions(&self) -> usize {
self.other_restrictions.len() + 2
/// Try to pick a random relay from `netdir`,
/// according to the rules of this selector.
pub fn select_relay<'s, 'd, R: rand::Rng>(
&'s self,
rng: &mut R,
netdir: &'d NetDir,
) -> (Option<Relay<'d>>, SelectionInfo<'s>) {
with_possible_relaxation(
self,
|selector| {
let role = selector.weight_role();
let mut fc = FilterCounts::new(selector);
let relay = netdir.pick_relay(rng, role, |r| selector.relay_usable(r, &mut fc));
(relay, fc)
Option::is_some,
)
/// Try to pick `n_relays` distinct random relay from `netdir`,
pub fn select_n_relays<'s, 'd, R: rand::Rng>(
n_relays: usize,
) -> (Vec<Relay<'d>>, SelectionInfo<'s>) {
let relays = netdir
.pick_n_relays(rng, n_relays, role, |r| selector.relay_usable(r, &mut fc));
(relays, fc)
|relays| !relays.is_empty(),
/// Check whether a given relay `r` obeys the restrictions of this selector,
/// updating `fc` according to which restrictions (if any) accepted or
/// rejected it.
/// Requires that `fc` has the same length as self.restrictions.
/// This differs from `<Self as RelayPredicate>::permits_relay` in taking
/// `fc` as an argument.
fn relay_usable(&self, r: &Relay<'_>, fc: &mut FilterCounts) -> bool {
debug_assert_eq!(self.n_restrictions(), fc.counts.len());
self.all_restrictions()
.zip(fc.counts.iter_mut())
.all(|(restr, restr_count)| {
restr_count.count(restr.restriction.low_level_predicate_permits_relay(r))
})
/// Return true if this selector has any flexible restrictions.
fn can_relax(&self) -> bool {
self.all_restrictions().any(|restr| !restr.strict)
/// Return a new selector created by relaxing every flexible restriction in
/// this selector.
fn relax(&self) -> Self {
let new_selector = RelaySelector {
usage: self.usage.maybe_relax(),
exclusion: self.exclusion.maybe_relax(),
other_restrictions: self
.other_restrictions
.iter()
.map(Restr::maybe_relax)
.collect(),
debug_assert!(!new_selector.can_relax());
new_selector
impl<'a> LowLevelRelayPredicate for RelaySelector<'a> {
fn low_level_predicate_permits_relay(&self, relay: &tor_netdir::Relay<'_>) -> bool {
.all(|r| r.restriction.low_level_predicate_permits_relay(relay))
/// Re-run relay selection, relaxing our selector as necessary.
/// This is a helper to implement our relay selection logic.
/// We try to run `select` to find one or more random relays
/// conforming to `selector`.
/// If `ok` says that the result is good (by returning true),
/// we return that result.
/// Otherwise, we try to _relax_ the selector (if possible),
/// and try again.
/// If the selector can't be relaxed any further,
/// we return the original (not-ok) result.
//
// TODO: Later, we might want to relax our restrictions one by one,
// rather than all at once.
fn with_possible_relaxation<'a, SEL, OK, T>(
selector: &'a RelaySelector,
mut select: SEL,
ok: OK,
) -> (T, SelectionInfo<'a>)
where
SEL: FnMut(&RelaySelector) -> (T, FilterCounts),
OK: Fn(&T) -> bool,
{
let (outcome, count_strict) = select(selector);
let succeeded = ok(&outcome);
if succeeded || !selector.can_relax() {
let info = SelectionInfo {
first_try: count_strict,
relaxed_try: None,
succeeded,
in_selection: selector,
return (outcome, info);
let relaxed_selector = selector.relax();
let (relaxed_outcome, count_relaxed) = select(&relaxed_selector);
relaxed_try: Some(count_relaxed),
succeeded: ok(&relaxed_outcome),
(relaxed_outcome, info)
#[cfg(test)]
mod test {
// @@ begin test lint list maintained by maint/add_warning @@
#![allow(clippy::bool_assert_comparison)]
#![allow(clippy::clone_on_copy)]
#![allow(clippy::dbg_macro)]
#![allow(clippy::mixed_attributes_style)]
#![allow(clippy::print_stderr)]
#![allow(clippy::print_stdout)]
#![allow(clippy::single_char_pattern)]
#![allow(clippy::unwrap_used)]
#![allow(clippy::unchecked_time_subtraction)]
#![allow(clippy::useless_vec)]
#![allow(clippy::needless_pass_by_value)]
//! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
use std::collections::HashSet;
use tor_basic_utils::test_rng::testing_rng;
use tor_linkspec::{HasRelayIds, RelayId};
use tor_netdir::{FamilyRules, Relay, SubnetConfig};
use super::*;
use crate::{
RelaySelectionConfig, TargetPort,
testing::{cfg, split_netdir, testnet},
#[test]
fn selector_as_predicate() {
let nd = testnet();
let id_4 = "$0404040404040404040404040404040404040404".parse().unwrap();
let usage = RelayUsage::middle_relay(None);
let exclusion = RelayExclusion::exclude_identities([id_4].into_iter().collect());
let sel = RelaySelector::new(usage.clone(), exclusion.clone());
let (yes, no) = split_netdir(&nd, &sel);
let p = |r: &Relay<'_>| {
usage.low_level_predicate_permits_relay(r)
&& exclusion.low_level_predicate_permits_relay(r)
assert!(yes.iter().all(p));
assert!(no.iter().all(|r| !p(r)));
fn selector_as_filter() {
let mut fc = FilterCounts::new(&sel);
let (yes, _no) = split_netdir(&nd, &sel);
let filtered: Vec<_> = nd
.relays()
.filter(|r| sel.relay_usable(r, &mut fc))
.collect();
assert_eq!(yes.len(), filtered.len());
let k1: HashSet<_> = yes.iter().map(|r| r.rsa_identity().unwrap()).collect();
let k2: HashSet<_> = filtered.iter().map(|r| r.rsa_identity().unwrap()).collect();
assert_eq!(k1, k2);
// 6 relays are rejected for not being suitable as a general-purpose middle relay
// (no Fast flag or no stable flag)
assert_eq!(fc.counts[0].n_rejected, 12);
// 1 additional relay is rejected for having id_4.
assert_eq!(fc.counts[1].n_rejected, 1);
// The remainder are accepted.
assert_eq!(fc.counts[1].n_accepted, yes.len());
fn selector_pick_random() {
let k_yes: HashSet<_> = yes.iter().map(|r| r.rsa_identity().unwrap()).collect();
let p = |r: Relay<'_>| k_yes.contains(r.rsa_identity().unwrap());
let mut rng = testing_rng();
for _ in 0..50 {
// Select one relay; make sure it is ok.
let (r_rand, si) = sel.select_relay(&mut rng, &nd);
assert!(si.success());
assert!(!si.result_is_relaxed_success());
assert!(p(r_rand.unwrap()));
// Select 20 random relays; make sure they are distinct and ok.
let (rs_rand, si) = sel.select_n_relays(&mut rng, 20, &nd);
assert_eq!(rs_rand.len(), 20);
assert!(rs_rand.iter().cloned().all(p));
let k_got: HashSet<_> = rs_rand.iter().map(|r| r.rsa_identity().unwrap()).collect();
assert_eq!(k_got.len(), 20);
fn selector_report() {
let (_, si) = sel.select_relay(&mut rng, &nd);
assert_eq!(
si.to_string(),
"Success: rejected 12/40 as not usable as middle relay; 1/28 as already selected"
);
// Now try failing.
// (The test network doesn't have ipv6 support.)
let unreachable_port = TargetPort::ipv6(80);
let sel = RelaySelector::new(
RelayUsage::exit_to_all_ports(&cfg(), vec![unreachable_port]),
exclusion.clone(),
let (r_none, si) = sel.select_relay(&mut rng, &nd);
assert!(r_none.is_none());
"Failed: rejected 40/40 as not exiting to desired ports"
fn relax() {
let all_families = FamilyRules::all_family_info();
let id_4: RelayId = "$0404040404040404040404040404040404040404".parse().unwrap();
let r4 = nd.by_id(&id_4).unwrap();
let very_silly_cfg = RelaySelectionConfig {
long_lived_ports: cfg().long_lived_ports,
// This should exclude everyone.
subnet_config: SubnetConfig::new(1, 1),
let exclude_relays = vec![r4];
let exclude_everyone = RelayExclusion::exclude_relays_in_same_family(
&very_silly_cfg,
exclude_relays,
all_families,
let mut sel = RelaySelector::new(usage.clone(), exclude_everyone.clone());
let (r_none, _) = sel.select_relay(&mut rng, &nd);
sel.mark_exclusion_flexible();
let (r_some, si) = sel.select_relay(&mut rng, &nd);
assert!(r_some.is_some());
"Failed at first, then succeeded. At first, rejected 12/40 as not usable as middle relay; \
28/28 as in same family as already selected. \
After relaxing requirements, rejected 12/40 as not usable as middle relay"