tor_relay_selection/
selector.rs

Help
1//! Logic for selecting relays from a network directory,
2//! and reporting the outcome of such a selection.
3
4use crate::{LowLevelRelayPredicate, RelayExclusion, RelayRestriction, RelayUsage};
5use tor_basic_utils::iter::FilterCount;
6use tor_netdir::{NetDir, Relay, WeightRole};
7
8use std::fmt;
9
10/// Description of the requirements that a relay must implement in order to be selected.
11///
12/// This object is used to pick a [`Relay`] from a [`NetDir`], or to ensure that a
13/// previously selected `Relay` still meets its requirements.
14///
15/// The requirements on a relay can be _strict_ or _flexible_.
16/// If any restriction is flexible, and relay selection fails at first,
17/// we _relax_ the `RelaySelector` by removing that restriction,
18/// and trying again,
19/// before we give up completely.
20#[derive(Clone, Debug)]
21pub struct RelaySelector<'a> {
22    /// A usage that the relay must support.
23    ///
24    /// Invariant: This is a RelayUsage.
25    usage: Restr<'a>,
26
27    /// An excludion that the relay must obey.
28    ///
29    /// Invariant: This a RelayExclusion.
30    exclusion: Restr<'a>,
31
32    /// Other restrictions that a Relay must obey in order to be selected.
33    other_restrictions: Vec<Restr<'a>>,
34}
35
36/// A single restriction, along with a flag about whether it's strict.
37#[derive(Clone, Debug)]
38struct Restr<'a> {
39    /// The underlying restriction.
40    restriction: RelayRestriction<'a>,
41    /// Is the restriction strict or flexible?
42    strict: bool,
43}
44
45impl<'a> Restr<'a> {
46    /// Try relaxing this restriction.
47    ///
48    /// (If this can't be relaxed, just return a copy of it.)
49    fn maybe_relax(&self) -> Self {
50        if self.strict {
51            self.clone()
52        } else {
53            Self {
54                restriction: self.restriction.relax(),
55                // The new restriction is always strict, since we don't want to
56                // relax it any further.
57                strict: true,
58            }
59        }
60    }
61}
62
63/// Information about how a given selection was generated.
64///
65/// Records the specifics of how many relays were excluded by each
66/// requirement,
67/// whether we had to relax the selector, and so on.
68///
69/// The caller should typically decide whether an error or warning is necessary,
70/// and if so use this to generate a formattable report about what went wrong.
71#[derive(Debug, Clone)]
72pub struct SelectionInfo<'a> {
73    /// Outcome of our first attempt to pick a relay.
74    first_try: FilterCounts,
75
76    /// Present if we tried again with a relaxed version of our
77    /// flexible members.
78    relaxed_try: Option<FilterCounts>,
79
80    /// True if we eventually succeeded in picking a relay.
81    succeeded: bool,
82
83    /// The `RelaySelector` that was used.
84    ///
85    /// Used to produce information about which restriction is which.
86    in_selection: &'a RelaySelector<'a>,
87}
88
89impl<'a> SelectionInfo<'a> {
90    /// Return true if we eventually picked at least one relay.
91    ///
92    /// (We report success on `pick_n_relays` if we returned a nonzero
93    /// number of relays, even if it is smaller than the requested number.)
94    pub fn success(&self) -> bool {
95        self.succeeded
96    }
97
98    /// Return true if picked at least one relay,
99    /// but only after relaxing our initial selector.
100    pub fn result_is_relaxed_success(&self) -> bool {
101        self.relaxed_try.is_some() && self.succeeded
102    }
103}
104
105impl<'a> fmt::Display for SelectionInfo<'a> {
106    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
107        match (self.succeeded, &self.relaxed_try) {
108            (true, None) => write!(f, "Success: {}", FcDisp(&self.first_try, self.in_selection))?,
109            (false, None) => write!(f, "Failed: {}", FcDisp(&self.first_try, self.in_selection))?,
110            (true, Some(retry)) => write!(
111                f,
112                "Failed at first, then succeeded. At first, {}. After relaxing requirements, {}",
113                FcDisp(&self.first_try, self.in_selection),
114                FcDisp(retry, self.in_selection)
115            )?,
116            (false, Some(retry)) => write!(
117                f,
118                "Failed even after relaxing requirement. At first, {}. After relaxing requirements, {}",
119                FcDisp(&self.first_try, self.in_selection),
120                FcDisp(retry, self.in_selection)
121            )?,
122        };
123        Ok(())
124    }
125}
126
127/// A list of [`FilterCount`], associated with a [`RelaySelector`].
128#[derive(Debug, Clone)]
129struct FilterCounts {
130    /// The [`FilterCount`] created by each restriction.
131    ///
132    /// This `Vec` has the same length as the list of restrictions; its items
133    /// refer to them one by one.
134    ///
135    /// Because restrictions are applied as a set of filters, each successive
136    /// count will only include the relays not excluded by the previous filters.
137    counts: Vec<FilterCount>,
138}
139
140impl FilterCounts {
141    /// Create a new empty `FilterCounts`.
142    fn new(selector: &RelaySelector) -> Self {
143        let counts = vec![FilterCount::default(); selector.n_restrictions()];
144        FilterCounts { counts }
145    }
146}
147
148/// Helper to display filter counts
149struct FcDisp<'a>(&'a FilterCounts, &'a RelaySelector<'a>);
150impl<'a> fmt::Display for FcDisp<'a> {
151    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
152        let counts = &self.0.counts;
153        let restrictions = self.1.all_restrictions();
154        write!(f, "rejected ")?;
155        let mut first = true;
156        let mut found_any_rejected = false;
157        for (c, r) in counts.iter().zip(restrictions) {
158            if c.n_rejected == 0 {
159                continue;
160            }
161            if let Some(desc) = r.restriction.rejection_description() {
162                if first {
163                    first = false;
164                } else {
165                    write!(f, "; ")?;
166                }
167                write!(f, "{} as {}", c.display_frac_rejected(), desc)?;
168                found_any_rejected = true;
169            } else {
170                debug_assert_eq!(c.n_rejected, 0);
171            }
172        }
173        if !found_any_rejected {
174            write!(f, "none")?;
175        }
176        Ok(())
177    }
178}
179
180impl<'a> RelaySelector<'a> {
181    /// Create a new RelaySelector to pick relays with a given
182    /// [`RelayUsage`] and [`RelayExclusion`].
183    ///
184    /// Both arguments are required, since every caller should consider them explicitly.
185    ///
186    /// The provided usage and exclusion are strict by default.
187    ///
188    // TODO: Possibly have this take a struct with named pieces instead, when we
189    // get a third thing that we want everybody to think about.
190    pub fn new(usage: RelayUsage, exclusion: RelayExclusion<'a>) -> Self {
191        Self {
192            usage: Restr {
193                restriction: RelayRestriction::for_usage(usage),
194                strict: true,
195            },
196            exclusion: Restr {
197                restriction: exclusion.into(),
198                strict: true,
199            },
200            other_restrictions: vec![],
201        }
202    }
203
204    /// Mark the originally provided `RelayUsage` as flexible.
205    pub fn mark_usage_flexible(&mut self) {
206        self.usage.strict = false;
207    }
208
209    /// Mark the originally provided `RelayExclusion` as flexible.
210    pub fn mark_exclusion_flexible(&mut self) {
211        self.exclusion.strict = false;
212    }
213
214    /// Add a new _strict_ [`RelayRestriction`] to this selector.
215    pub fn push_restriction(&mut self, restriction: RelayRestriction<'a>) {
216        self.push_inner(restriction, true);
217    }
218
219    /// Add a new _flexible_ [`RelayRestriction`] to this selector.
220    pub fn push_flexible_restriction(&mut self, restriction: RelayRestriction<'a>) {
221        self.push_inner(restriction, false);
222    }
223
224    /// Helper to implement adding a new restriction.
225    fn push_inner(&mut self, restriction: RelayRestriction<'a>, strict: bool) {
226        self.other_restrictions.push(Restr {
227            restriction,
228            strict,
229        });
230    }
231
232    /// Return the usage for this selector.
233    pub fn usage(&self) -> &RelayUsage {
234        // See invariants for explanation of why these `expects` are safe.
235        self.usage
236            .restriction
237            .as_usage()
238            .expect("Usage not a usage!?")
239    }
240
241    /// Return the [`WeightRole`] to use when randomly picking relays according
242    /// to this selector.
243    fn weight_role(&self) -> WeightRole {
244        self.usage().selection_weight_role()
245    }
246
247    /// Return true if `relay` is one that this selector would pick.
248    pub fn permits_relay(&self, relay: &tor_netdir::Relay<'_>) -> bool {
249        self.low_level_predicate_permits_relay(relay)
250    }
251
252    /// Return an iterator that yields each restriction from this selector,
253    /// including the usage and exclusion.
254    fn all_restrictions(&self) -> impl Iterator<Item = &Restr<'a>> {
255        use std::iter::once;
256        once(&self.usage)
257            .chain(once(&self.exclusion))
258            .chain(self.other_restrictions.iter())
259    }
260
261    /// Return the number of restrictions in this selector,
262    /// including the usage and exclusion.
263    fn n_restrictions(&self) -> usize {
264        self.other_restrictions.len() + 2
265    }
266
267    /// Try to pick a random relay from `netdir`,
268    /// according to the rules of this selector.
269    pub fn select_relay<'s, 'd, R: rand::Rng>(
270        &'s self,
271        rng: &mut R,
272        netdir: &'d NetDir,
273    ) -> (Option<Relay<'d>>, SelectionInfo<'s>) {
274        with_possible_relaxation(
275            self,
276            |selector| {
277                let role = selector.weight_role();
278                let mut fc = FilterCounts::new(selector);
279                let relay = netdir.pick_relay(rng, role, |r| selector.relay_usable(r, &mut fc));
280                (relay, fc)
281            },
282            Option::is_some,
283        )
284    }
285
286    /// Try to pick `n_relays` distinct random relay from `netdir`,
287    /// according to the rules of this selector.
288    pub fn select_n_relays<'s, 'd, R: rand::Rng>(
289        &'s self,
290        rng: &mut R,
291        n_relays: usize,
292        netdir: &'d NetDir,
293    ) -> (Vec<Relay<'d>>, SelectionInfo<'s>) {
294        with_possible_relaxation(
295            self,
296            |selector| {
297                let role = selector.weight_role();
298                let mut fc = FilterCounts::new(selector);
299                let relays = netdir
300                    .pick_n_relays(rng, n_relays, role, |r| selector.relay_usable(r, &mut fc));
301                (relays, fc)
302            },
303            |relays| !relays.is_empty(),
304        )
305    }
306
307    /// Check whether a given relay `r` obeys the restrictions of this selector,
308    /// updating `fc` according to which restrictions (if any) accepted or
309    /// rejected it.
310    ///
311    /// Requires that `fc` has the same length as self.restrictions.
312    ///
313    /// This differs from `<Self as RelayPredicate>::permits_relay` in taking
314    /// `fc` as an argument.
315    fn relay_usable(&self, r: &Relay<'_>, fc: &mut FilterCounts) -> bool {
316        debug_assert_eq!(self.n_restrictions(), fc.counts.len());
317
318        self.all_restrictions()
319            .zip(fc.counts.iter_mut())
320            .all(|(restr, restr_count)| {
321                restr_count.count(restr.restriction.low_level_predicate_permits_relay(r))
322            })
323    }
324
325    /// Return true if this selector has any flexible restrictions.
326    fn can_relax(&self) -> bool {
327        self.all_restrictions().any(|restr| !restr.strict)
328    }
329
330    /// Return a new selector created by relaxing every flexible restriction in
331    /// this selector.
332    fn relax(&self) -> Self {
333        let new_selector = RelaySelector {
334            usage: self.usage.maybe_relax(),
335            exclusion: self.exclusion.maybe_relax(),
336            other_restrictions: self
337                .other_restrictions
338                .iter()
339                .map(Restr::maybe_relax)
340                .collect(),
341        };
342        debug_assert!(!new_selector.can_relax());
343        new_selector
344    }
345}
346
347impl<'a> LowLevelRelayPredicate for RelaySelector<'a> {
348    fn low_level_predicate_permits_relay(&self, relay: &tor_netdir::Relay<'_>) -> bool {
349        self.all_restrictions()
350            .all(|r| r.restriction.low_level_predicate_permits_relay(relay))
351    }
352}
353
354/// Re-run relay selection, relaxing our selector as necessary.
355///
356/// This is a helper to implement our relay selection logic.
357/// We try to run `select` to find one or more random relays
358/// conforming to `selector`.
359/// If `ok` says that the result is good (by returning true),
360/// we return that result.
361/// Otherwise, we try to _relax_ the selector (if possible),
362/// and try again.
363/// If the selector can't be relaxed any further,
364/// we return the original (not-ok) result.
365//
366// TODO: Later, we might want to relax our restrictions one by one,
367// rather than all at once.
368fn with_possible_relaxation<'a, SEL, OK, T>(
369    selector: &'a RelaySelector,
370    mut select: SEL,
371    ok: OK,
372) -> (T, SelectionInfo<'a>)
373where
374    SEL: FnMut(&RelaySelector) -> (T, FilterCounts),
375    OK: Fn(&T) -> bool,
376{
377    let (outcome, count_strict) = select(selector);
378    let succeeded = ok(&outcome);
379    if succeeded || !selector.can_relax() {
380        let info = SelectionInfo {
381            first_try: count_strict,
382            relaxed_try: None,
383            succeeded,
384            in_selection: selector,
385        };
386        return (outcome, info);
387    }
388    let relaxed_selector = selector.relax();
389    let (relaxed_outcome, count_relaxed) = select(&relaxed_selector);
390    let info = SelectionInfo {
391        first_try: count_strict,
392        relaxed_try: Some(count_relaxed),
393        succeeded: ok(&relaxed_outcome),
394        in_selection: selector,
395    };
396    (relaxed_outcome, info)
397}
398
399#[cfg(test)]
400mod test {
401    // @@ begin test lint list maintained by maint/add_warning @@
402    #![allow(clippy::bool_assert_comparison)]
403    #![allow(clippy::clone_on_copy)]
404    #![allow(clippy::dbg_macro)]
405    #![allow(clippy::mixed_attributes_style)]
406    #![allow(clippy::print_stderr)]
407    #![allow(clippy::print_stdout)]
408    #![allow(clippy::single_char_pattern)]
409    #![allow(clippy::unwrap_used)]
410    #![allow(clippy::unchecked_duration_subtraction)]
411    #![allow(clippy::useless_vec)]
412    #![allow(clippy::needless_pass_by_value)]
413    //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
414
415    use std::collections::HashSet;
416
417    use tor_basic_utils::test_rng::testing_rng;
418    use tor_linkspec::{HasRelayIds, RelayId};
419    use tor_netdir::{FamilyRules, Relay, SubnetConfig};
420
421    use super::*;
422    use crate::{
423        testing::{cfg, split_netdir, testnet},
424        RelaySelectionConfig, TargetPort,
425    };
426
427    #[test]
428    fn selector_as_predicate() {
429        let nd = testnet();
430        let id_4 = "$0404040404040404040404040404040404040404".parse().unwrap();
431        let usage = RelayUsage::middle_relay(None);
432        let exclusion = RelayExclusion::exclude_identities([id_4].into_iter().collect());
433        let sel = RelaySelector::new(usage.clone(), exclusion.clone());
434
435        let (yes, no) = split_netdir(&nd, &sel);
436        let p = |r: &Relay<'_>| {
437            usage.low_level_predicate_permits_relay(r)
438                && exclusion.low_level_predicate_permits_relay(r)
439        };
440        assert!(yes.iter().all(p));
441        assert!(no.iter().all(|r| !p(r)));
442    }
443
444    #[test]
445    fn selector_as_filter() {
446        let nd = testnet();
447        let id_4 = "$0404040404040404040404040404040404040404".parse().unwrap();
448        let usage = RelayUsage::middle_relay(None);
449        let exclusion = RelayExclusion::exclude_identities([id_4].into_iter().collect());
450        let sel = RelaySelector::new(usage.clone(), exclusion.clone());
451        let mut fc = FilterCounts::new(&sel);
452
453        let (yes, _no) = split_netdir(&nd, &sel);
454        let filtered: Vec<_> = nd
455            .relays()
456            .filter(|r| sel.relay_usable(r, &mut fc))
457            .collect();
458        assert_eq!(yes.len(), filtered.len());
459
460        let k1: HashSet<_> = yes.iter().map(|r| r.rsa_identity().unwrap()).collect();
461        let k2: HashSet<_> = filtered.iter().map(|r| r.rsa_identity().unwrap()).collect();
462        assert_eq!(k1, k2);
463
464        // 6 relays are rejected for not being suitable as a general-purpose middle relay
465        // (no Fast flag or no stable flag)
466        assert_eq!(fc.counts[0].n_rejected, 12);
467        // 1 additional relay is rejected for having id_4.
468        assert_eq!(fc.counts[1].n_rejected, 1);
469        // The remainder are accepted.
470        assert_eq!(fc.counts[1].n_accepted, yes.len());
471    }
472
473    #[test]
474    fn selector_pick_random() {
475        let nd = testnet();
476        let id_4 = "$0404040404040404040404040404040404040404".parse().unwrap();
477        let usage = RelayUsage::middle_relay(None);
478        let exclusion = RelayExclusion::exclude_identities([id_4].into_iter().collect());
479        let sel = RelaySelector::new(usage.clone(), exclusion.clone());
480
481        let (yes, _no) = split_netdir(&nd, &sel);
482        let k_yes: HashSet<_> = yes.iter().map(|r| r.rsa_identity().unwrap()).collect();
483        let p = |r: Relay<'_>| k_yes.contains(r.rsa_identity().unwrap());
484
485        let mut rng = testing_rng();
486        for _ in 0..50 {
487            // Select one relay; make sure it is ok.
488            let (r_rand, si) = sel.select_relay(&mut rng, &nd);
489            assert!(si.success());
490            assert!(!si.result_is_relaxed_success());
491            assert!(p(r_rand.unwrap()));
492
493            // Select 20 random relays; make sure they are distinct and ok.
494            let (rs_rand, si) = sel.select_n_relays(&mut rng, 20, &nd);
495            assert_eq!(rs_rand.len(), 20);
496            assert!(si.success());
497            assert!(!si.result_is_relaxed_success());
498            assert!(rs_rand.iter().cloned().all(p));
499            let k_got: HashSet<_> = rs_rand.iter().map(|r| r.rsa_identity().unwrap()).collect();
500            assert_eq!(k_got.len(), 20);
501        }
502    }
503
504    #[test]
505    fn selector_report() {
506        let nd = testnet();
507        let id_4 = "$0404040404040404040404040404040404040404".parse().unwrap();
508        let usage = RelayUsage::middle_relay(None);
509        let exclusion = RelayExclusion::exclude_identities([id_4].into_iter().collect());
510        let sel = RelaySelector::new(usage.clone(), exclusion.clone());
511
512        let mut rng = testing_rng();
513        let (_, si) = sel.select_relay(&mut rng, &nd);
514        assert_eq!(
515            si.to_string(),
516            "Success: rejected 12/40 as not usable as middle relay; 1/28 as already selected"
517        );
518
519        // Now try failing.
520        // (The test network doesn't have ipv6 support.)
521        let unreachable_port = TargetPort::ipv6(80);
522        let sel = RelaySelector::new(
523            RelayUsage::exit_to_all_ports(&cfg(), vec![unreachable_port]),
524            exclusion.clone(),
525        );
526        let (r_none, si) = sel.select_relay(&mut rng, &nd);
527        assert!(r_none.is_none());
528        assert_eq!(
529            si.to_string(),
530            "Failed: rejected 40/40 as not exiting to desired ports"
531        );
532    }
533
534    #[test]
535    fn relax() {
536        let all_families = FamilyRules::all_family_info();
537
538        let nd = testnet();
539        let id_4: RelayId = "$0404040404040404040404040404040404040404".parse().unwrap();
540        let r4 = nd.by_id(&id_4).unwrap();
541        let usage = RelayUsage::middle_relay(None);
542        let very_silly_cfg = RelaySelectionConfig {
543            long_lived_ports: cfg().long_lived_ports,
544            // This should exclude everyone.
545            subnet_config: SubnetConfig::new(1, 1),
546        };
547        let exclude_relays = vec![r4];
548        let exclude_everyone = RelayExclusion::exclude_relays_in_same_family(
549            &very_silly_cfg,
550            exclude_relays,
551            all_families,
552        );
553
554        let mut sel = RelaySelector::new(usage.clone(), exclude_everyone.clone());
555        let mut rng = testing_rng();
556        let (r_none, _) = sel.select_relay(&mut rng, &nd);
557        assert!(r_none.is_none());
558
559        sel.mark_exclusion_flexible();
560        let (r_some, si) = sel.select_relay(&mut rng, &nd);
561        assert!(r_some.is_some());
562        assert_eq!(si.to_string(), "Failed at first, then succeeded. At first, rejected 12/40 as not usable as middle relay; \
563                                    28/28 as in same family as already selected. \
564                                    After relaxing requirements, rejected 12/40 as not usable as middle relay");
565    }
566}
tor_relay_selection/selector.rs

tor_relay_selection/
selector.rs
