tor_relay_selection/
restriction.rs

Help
1//! Define different restrictions that can be applied to relays.
2
3#[cfg(feature = "geoip")]
4use tor_geoip::HasCountryCode;
5use tor_linkspec::{ChanTarget, HasAddrs, HasRelayIds, RelayIdSet};
6use tor_netdir::{FamilyRules, NetDir, Relay, SubnetConfig};
7use tor_netdoc::types::policy::AddrPortPattern;
8
9use crate::{LowLevelRelayPredicate, RelaySelectionConfig, RelayUsage};
10use std::{fmt, net::IpAddr};
11
12/// A restriction that we use when picking relays.
13///
14/// Differs from [`RelayUsage`] in that it does not say what
15/// the relay is _used for_;
16/// instead, it describes an additional set of requirements that a relay must
17/// satisfy.
18#[derive(Clone, Debug)]
19pub struct RelayRestriction<'a> {
20    /// The actual restriction object.
21    inner: RestrictionInner<'a>,
22}
23
24/// Enumeration of possible [`RelayRestriction`]s.
25///
26/// This is a separate type so that we can hide its variants.
27///
28// TODO: I'm not sure about having this be relative to `'a``,
29// but that is the only way to hold a `Relay<'a>`
30//
31// NOTE: Any time that you are extending this type, make sure that you are not
32// describing a new _mandatory_ restriction that all `RelaySelector` users
33// need to consider adding (or not).  If you *are* describing such a restriction,
34// then it should have its own type, and it should become a new argument to
35// RelaySelector::new().
36#[derive(Clone, Debug)]
37enum RestrictionInner<'a> {
38    /// Do not restrict any relays.
39    ///
40    /// This is present so that we can construct a no-op restriction when
41    /// relaxing a selector.
42    NoRestriction,
43    /// Require a given usage.
44    SupportsUsage(crate::RelayUsage),
45    /// Exclude a set of relays explicitly, by family, or by identity.
46    Exclude(RelayExclusion<'a>),
47    /// Require that, if the relay's contact method uses addresses, the relay
48    /// has at least one address matching one of the provided patterns.
49    HasAddrInSet(Vec<AddrPortPattern>),
50    /// Require that the relay has a given country code.
51    #[cfg(feature = "geoip")]
52    RequireCountry(tor_geoip::CountryCode),
53}
54
55impl<'a> RelayRestriction<'a> {
56    /// Create a restriction that allows every relay.
57    pub(crate) fn no_restriction() -> Self {
58        RelayRestriction {
59            inner: RestrictionInner::NoRestriction,
60        }
61    }
62
63    /// Convert a usage into a restriction.
64    ///
65    /// This is crate-internal since we never want to support requiring a relay
66    /// to provide multiple usages.
67    pub(crate) fn for_usage(usage: crate::RelayUsage) -> Self {
68        RelayRestriction {
69            inner: RestrictionInner::SupportsUsage(usage),
70        }
71    }
72
73    /// Require a relay that appears to be in the provided country,
74    /// according ot our geoip subsystem.
75    #[cfg(feature = "geoip")]
76    pub fn require_country_code(cc: tor_geoip::CountryCode) -> Self {
77        RelayRestriction {
78            inner: RestrictionInner::RequireCountry(cc),
79        }
80    }
81
82    /// Require that a relay has at least one address
83    /// listed in `addr_patterns`.
84    pub fn require_address(addr_patterns: Vec<AddrPortPattern>) -> Self {
85        // TODO: It's plausible that this restriction should be mandatory
86        // whenever we are picking new guards.
87        RelayRestriction {
88            inner: RestrictionInner::HasAddrInSet(addr_patterns),
89        }
90    }
91
92    /// Return a restriction that represents having "relaxed" this restriction.
93    ///
94    /// (Relaxing a restriction replaces it with a no-op, or with an almost-no-op.)
95    pub(crate) fn relax(&self) -> Self {
96        use RestrictionInner::*;
97        match &self.inner {
98            // We must always have a usage, so relaxing a usage must always
99            // return a usage.
100            SupportsUsage(usage) => Self::for_usage(RelayUsage::middle_relay(Some(usage))),
101            // Relaxing any other restriction returns a no-op
102            _ => Self::no_restriction(),
103        }
104    }
105
106    /// If this restriction represents a usage, return a reference to that usage.
107    pub(crate) fn as_usage(&self) -> Option<&RelayUsage> {
108        use RestrictionInner::*;
109        match &self.inner {
110            SupportsUsage(usage) => Some(usage),
111            _ => None,
112        }
113    }
114
115    /// Return a string describing why we rejected the relays that _don't_ match
116    /// this restriction.
117    pub(crate) fn rejection_description(&self) -> Option<&'static str> {
118        use RestrictionInner::*;
119        match &self.inner {
120            NoRestriction => None,
121            SupportsUsage(u) => Some(u.rejection_description()),
122            Exclude(e) => e.rejection_description(),
123            HasAddrInSet(_) => Some("not reachable (according to address filter)"),
124            #[cfg(feature = "geoip")]
125            RequireCountry(_) => Some("not in correct country"),
126        }
127    }
128}
129
130impl<'a> LowLevelRelayPredicate for RelayRestriction<'a> {
131    fn low_level_predicate_permits_relay(&self, relay: &tor_netdir::Relay<'_>) -> bool {
132        use RestrictionInner::*;
133        match &self.inner {
134            NoRestriction => true,
135            SupportsUsage(usage) => usage.low_level_predicate_permits_relay(relay),
136            Exclude(exclusion) => exclusion.low_level_predicate_permits_relay(relay),
137            HasAddrInSet(patterns) => relay_has_addr_in_set(relay, patterns),
138            #[cfg(feature = "geoip")]
139            RequireCountry(cc) => relay.country_code() == Some(*cc),
140        }
141    }
142}
143
144impl<'a> From<RelayExclusion<'a>> for RelayRestriction<'a> {
145    fn from(value: RelayExclusion<'a>) -> Self {
146        RelayRestriction {
147            inner: RestrictionInner::Exclude(value),
148        }
149    }
150}
151
152/// Return true if `relay` has at least one address matching at least one member
153/// of `patterns`.
154fn relay_has_addr_in_set(relay: &Relay<'_>, patterns: &[AddrPortPattern]) -> bool {
155    // NOTE: If we ever make this apply to ChanTarget instead of Relay, we will
156    // need it to call chan_method().socket_addrs() instead, and handle the case
157    // where the transport doesn't use an address.
158    relay
159        .addrs()
160        .iter()
161        .any(|addr| patterns.iter().any(|pat| pat.matches_sockaddr(addr)))
162}
163
164/// A set of relays that we must not use when picking a given
165/// relays.
166///
167/// Exclusions are generally used to make sure that we obey
168/// family-based path-selection rules,
169/// that we avoid putting the same relay into a set more than once,
170/// or similar purposes.
171///
172/// (This is a separate type from [`RelayRestriction`] so that we can
173/// enforce our rule that every [`RelaySelector`](crate::RelaySelector) must
174/// have a `RelayExclusion`.)
175#[derive(Clone, Debug)]
176pub struct RelayExclusion<'a> {
177    /// A list of identities to exclude.
178    ///
179    /// Any relay with any one of these identities is rejecteed.
180    exclude_ids: RelayIdSet,
181    /// A list of subnets from which to exclude addresses.
182    ///
183    /// The side of the subnet is determined by subnet_config.
184    exclude_subnets: Vec<IpAddr>,
185    /// A list of relays to exclude, along with their families.
186    exclude_relay_families: RelayList<'a>,
187    /// The configuration to use when deciding whether two addresses are in the
188    /// same subnet.
189    subnet_config: SubnetConfig,
190    /// The rules to use when deciding whether two relays are in the same family.
191    family_rules: FamilyRules,
192}
193
194/// Helper: wraps `Vec[Relay]`, but implements Debug.
195#[derive(Clone)]
196struct RelayList<'a>(Vec<Relay<'a>>);
197impl<'a> fmt::Debug for RelayList<'a> {
198    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
199        write!(f, "[ ")?;
200        for r in &self.0 {
201            write!(f, "{}, ", r.display_relay_ids())?;
202        }
203        write!(f, "]")
204    }
205}
206
207impl<'a> RelayExclusion<'a> {
208    /// Exclude no relays at all.
209    ///
210    /// This kind of restriction is useful when picking the first relay for
211    /// something,
212    ///
213    // (Note that this is _not_ Default::default, since we don't want people
214    // picking it by mistake.)
215    pub fn no_relays_excluded() -> Self {
216        RelayExclusion {
217            exclude_ids: RelayIdSet::new(),
218            exclude_subnets: Vec::new(),
219            exclude_relay_families: RelayList(Vec::new()),
220            subnet_config: SubnetConfig::no_addresses_match(),
221            family_rules: FamilyRules::ignore_declared_families(),
222        }
223    }
224
225    /// Exclude every relay that has an identity in `ids`.
226    pub fn exclude_identities(ids: RelayIdSet) -> Self {
227        RelayExclusion {
228            exclude_ids: ids,
229            ..RelayExclusion::no_relays_excluded()
230        }
231    }
232
233    /// Exclude every relay that appears in `relays`.
234    pub fn exclude_specific_relays(relays: &[Relay<'a>]) -> Self {
235        let ids: RelayIdSet = relays
236            .iter()
237            .flat_map(Relay::identities)
238            .map(|id_ref| id_ref.to_owned())
239            .collect();
240
241        Self::exclude_identities(ids)
242    }
243
244    /// Try to exclude every relay in the same family as the [`ChanTarget`]
245    /// `ct`.
246    ///
247    /// # Limitations
248    ///
249    /// A ChanTarget does not have a listed family.  Thus, if it does not correspond
250    /// to a relay listed in `netdir`, we can only exclude relays that share the
251    /// same identity, or relays that are in the same subnet.
252    ///
253    /// Whenever possible, it's better to use exclude_relays_in_same_family.
254    pub fn exclude_channel_target_family<CT: ChanTarget>(
255        cfg: &RelaySelectionConfig,
256        ct: &CT,
257        netdir: &'a NetDir,
258    ) -> Self {
259        if let Some(r) = netdir.by_ids(ct) {
260            return Self::exclude_relays_in_same_family(
261                cfg,
262                vec![r],
263                FamilyRules::from(netdir.params()),
264            );
265        }
266
267        let exclude_ids = ct.identities().map(|id_ref| id_ref.to_owned()).collect();
268        let exclude_addr_families = ct.addrs().iter().map(|a| a.ip()).collect();
269
270        Self {
271            exclude_ids,
272            exclude_subnets: exclude_addr_families,
273            subnet_config: cfg.subnet_config,
274            ..Self::no_relays_excluded()
275        }
276    }
277
278    /// Exclude every relay that is in the same family as any member of
279    /// `relays`.
280    ///
281    /// (Remember that every relay is considered to be in the same family as
282    /// itself, so you don't typically need to use `exclude_specific_relays`
283    /// along with this.)
284    ///
285    /// Considers relays that are in the same subnets (according to `cfg`) to
286    /// belong to the same family.
287    pub fn exclude_relays_in_same_family(
288        cfg: &RelaySelectionConfig,
289        relays: Vec<Relay<'a>>,
290        family_rules: FamilyRules,
291    ) -> Self {
292        RelayExclusion {
293            exclude_relay_families: RelayList(relays),
294            subnet_config: cfg.subnet_config,
295            family_rules,
296            ..RelayExclusion::no_relays_excluded()
297        }
298    }
299
300    /// Modify this `RelayExclusion` by adding every exclusion from `other`.
301    ///
302    /// (Any subnet configuration becomes the _union_ of previous subnet
303    /// configurations.)
304    pub fn extend(&mut self, other: &RelayExclusion<'a>) {
305        let RelayExclusion {
306            exclude_ids,
307            exclude_subnets: exclude_addr_families,
308            exclude_relay_families,
309            subnet_config,
310            family_rules,
311        } = other;
312        self.exclude_ids
313            .extend(exclude_ids.iter().map(|id_ref| id_ref.to_owned()));
314        self.exclude_subnets
315            .extend_from_slice(&exclude_addr_families[..]);
316        self.exclude_relay_families
317            .0
318            .extend_from_slice(&exclude_relay_families.0[..]);
319        self.subnet_config = self.subnet_config.union(subnet_config);
320        self.family_rules = self.family_rules.union(family_rules);
321    }
322
323    /// Return a string describing why we rejected the relays that _don't_ match
324    /// this exclusion.
325    pub(crate) fn rejection_description(&self) -> Option<&'static str> {
326        if self.exclude_relay_families.0.is_empty() && self.exclude_subnets.is_empty() {
327            if self.exclude_ids.is_empty() {
328                None
329            } else {
330                Some("already selected")
331            }
332        } else {
333            Some("in same family as already selected")
334        }
335    }
336}
337
338impl<'a> LowLevelRelayPredicate for RelayExclusion<'a> {
339    fn low_level_predicate_permits_relay(&self, relay: &Relay<'_>) -> bool {
340        if relay.identities().any(|id| self.exclude_ids.contains(id)) {
341            return false;
342        }
343
344        if relay.addrs().iter().any(|addr| {
345            self.exclude_subnets
346                .iter()
347                .any(|fam| self.subnet_config.addrs_in_same_subnet(&addr.ip(), fam))
348        }) {
349            return false;
350        }
351
352        if self.exclude_relay_families.0.iter().any(|r| {
353            relays_in_same_extended_family(&self.subnet_config, relay, r, self.family_rules)
354        }) {
355            return false;
356        }
357
358        true
359    }
360}
361
362/// Return true if `r1` and `r2` are in the same "extended" family,
363/// considering both explicitly declared families
364/// and subnet-based extended families.
365fn relays_in_same_extended_family(
366    subnet_config: &SubnetConfig,
367    r1: &Relay<'_>,
368    r2: &Relay<'_>,
369    family_rules: FamilyRules,
370) -> bool {
371    r1.low_level_details().in_same_family(r2, family_rules)
372        || subnet_config.any_addrs_in_same_subnet(r1, r2)
373}
374
375#[cfg(test)]
376mod test {
377    // @@ begin test lint list maintained by maint/add_warning @@
378    #![allow(clippy::bool_assert_comparison)]
379    #![allow(clippy::clone_on_copy)]
380    #![allow(clippy::dbg_macro)]
381    #![allow(clippy::mixed_attributes_style)]
382    #![allow(clippy::print_stderr)]
383    #![allow(clippy::print_stdout)]
384    #![allow(clippy::single_char_pattern)]
385    #![allow(clippy::unwrap_used)]
386    #![allow(clippy::unchecked_duration_subtraction)]
387    #![allow(clippy::useless_vec)]
388    #![allow(clippy::needless_pass_by_value)]
389    //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
390
391    use tor_linkspec::RelayId;
392    use tor_netdir::testnet::construct_custom_netdir;
393
394    use super::*;
395    use crate::testing::{cfg, split_netdir, testnet};
396
397    #[test]
398    fn exclude_nothing() {
399        let nd = testnet();
400        let usage = RelayExclusion::no_relays_excluded();
401        assert!(nd
402            .relays()
403            .all(|r| usage.low_level_predicate_permits_relay(&r)));
404    }
405
406    #[test]
407    fn exclude_ids() {
408        let nd = testnet();
409        let id_0 = "$0000000000000000000000000000000000000000".parse().unwrap();
410        let id_5 = "ed25519:BQUFBQUFBQUFBQUFBQUFBQUFBQUFBQUFBQUFBQUFBQU"
411            .parse()
412            .unwrap();
413        let ids: RelayIdSet = [id_0, id_5].into_iter().collect();
414        let (yes, no) = split_netdir(&nd, &RelayExclusion::exclude_identities(ids));
415
416        let p = |r: &Relay<'_>| !(r.has_identity(id_0.as_ref()) || r.has_identity(id_5.as_ref()));
417        assert_eq!(yes.len(), 38);
418        assert_eq!(no.len(), 2);
419        assert!(yes.iter().all(p));
420        assert!(no.iter().all(|r| !p(r)));
421    }
422
423    #[test]
424    fn exclude_relays() {
425        let nd = testnet();
426        let id_0: RelayId = "$0000000000000000000000000000000000000000".parse().unwrap();
427        let id_5: RelayId = "ed25519:BQUFBQUFBQUFBQUFBQUFBQUFBQUFBQUFBQUFBQUFBQU"
428            .parse()
429            .unwrap();
430        let relay_0 = nd.by_id(&id_0).unwrap();
431        let relay_5 = nd.by_id(&id_5).unwrap();
432
433        let (yes, no) = split_netdir(
434            &nd,
435            &RelayExclusion::exclude_specific_relays(&[relay_0.clone(), relay_5.clone()]),
436        );
437        let p = |r: &Relay<'_>| !(r.same_relay_ids(&relay_0) || r.same_relay_ids(&relay_5));
438        assert_eq!(yes.len(), 38);
439        assert_eq!(no.len(), 2);
440        assert!(yes.iter().all(p));
441        assert!(no.iter().all(|r| !p(r)));
442    }
443
444    /// Helper for testing family exclusions.  Requires a netdir where,
445    /// for every N, relays 2N and 2N+1 are in a family.
446    fn exclude_families_impl(nd: &NetDir, family_rules: FamilyRules) {
447        let id_0: RelayId = "$0000000000000000000000000000000000000000".parse().unwrap();
448        let id_5: RelayId = "ed25519:BQUFBQUFBQUFBQUFBQUFBQUFBQUFBQUFBQUFBQUFBQU"
449            .parse()
450            .unwrap();
451        let relay_0 = nd.by_id(&id_0).unwrap();
452        let relay_5 = nd.by_id(&id_5).unwrap();
453        let excluding_relays = vec![relay_0, relay_5];
454
455        // in the test netdir, all (2n, 2n+1) pairs are in a family.
456        let id_1 = "$0101010101010101010101010101010101010101".parse().unwrap();
457        let id_4 = "$0404040404040404040404040404040404040404".parse().unwrap();
458        let expect_excluded_ids: RelayIdSet = [id_0, id_1, id_4, id_5].into_iter().collect();
459
460        // Case one: No subnet-based exclusion.
461
462        let cfg_no_subnet = RelaySelectionConfig {
463            long_lived_ports: cfg().long_lived_ports,
464            subnet_config: SubnetConfig::new(255, 255),
465        };
466
467        let (yes, no) = split_netdir(
468            nd,
469            &RelayExclusion::exclude_relays_in_same_family(
470                &cfg_no_subnet,
471                excluding_relays.clone(),
472                family_rules,
473            ),
474        );
475        let p = |r: &Relay<'_>| !r.identities().any(|id| expect_excluded_ids.contains(id));
476        assert_eq!(yes.len(), 36);
477        assert_eq!(no.len(), 4);
478        assert!(yes.iter().all(p));
479        assert!(no.iter().all(|r| !p(r)));
480
481        // Case two: default subnet-based exclusion.
482        //
483        // In the test network, addresses are x.0.0.3 where x is the index of
484        // the relay, modulo 5.  Since the default ipv4 subnet family rule looks at /16
485        // prefixes, every one of the 40 relays in the testnet will be in a
486        // family with 8 other relays.
487        let expect_excluded_ids: RelayIdSet = nd
488            .relays()
489            .filter_map(|r| {
490                let rsa = r.rsa_identity().unwrap();
491                let b = rsa.as_bytes()[0];
492                if [0, 1, 4, 5].contains(&b) || [0, 5].contains(&(b % 5)) {
493                    Some(RelayId::from(*rsa))
494                } else {
495                    None
496                }
497            })
498            .collect();
499
500        let (yes, no) = split_netdir(
501            nd,
502            &RelayExclusion::exclude_relays_in_same_family(&cfg(), excluding_relays, family_rules),
503        );
504        for r in &no {
505            dbg!(r.rsa_identity().unwrap());
506        }
507        dbg!(&expect_excluded_ids);
508        dbg!(expect_excluded_ids.len());
509        let p = |r: &Relay<'_>| !r.identities().any(|id| expect_excluded_ids.contains(id));
510        assert_eq!(yes.len(), 30);
511        assert_eq!(no.len(), 10);
512        assert!(yes.iter().all(p));
513
514        assert!(no.iter().all(|r| { !p(r) }));
515    }
516
517    #[test]
518    fn exclude_families_by_list() {
519        exclude_families_impl(
520            &testnet(),
521            *FamilyRules::ignore_declared_families().use_family_lists(true),
522        );
523    }
524
525    #[test]
526    fn exclude_families_by_id() {
527        // Here we construct a network that matches our default testnet,
528        // but without any family lists.
529        // Instead we use "happy family" IDs to match the families from that default testnest.
530        let netdir = construct_custom_netdir(|pos, nb, _| {
531            // Clear the family list.
532            nb.md.family("".parse().unwrap());
533            // This will create an "Unrecognized" family id such that
534            // pos:N  will be shared by nodes in positions 2N and 2N+1.
535            let fam_id = format!("pos:{}", pos / 2);
536            nb.md.add_family_id(fam_id.parse().unwrap());
537        })
538        .unwrap()
539        .unwrap_if_sufficient()
540        .unwrap();
541
542        exclude_families_impl(
543            &netdir,
544            *FamilyRules::ignore_declared_families().use_family_ids(true),
545        );
546    }
547
548    #[test]
549    fn filter_addresses() {
550        let nd = testnet();
551        let reachable = vec![
552            "1.0.0.0/8:*".parse().unwrap(),
553            "2.0.0.0/8:*".parse().unwrap(),
554        ];
555        let reachable = RelayRestriction::require_address(reachable);
556
557        let (yes, no) = split_netdir(&nd, &reachable);
558        assert_eq!(yes.len(), 16);
559        assert_eq!(no.len(), 24);
560
561        let expected = ["1.0.0.3".parse().unwrap(), "2.0.0.3".parse().unwrap()];
562        let p = |r: &Relay<'_>| expected.contains(&r.addrs()[0].ip());
563        assert!(yes.iter().all(p));
564        assert!(no.iter().all(|r| !p(r)));
565    }
566
567    // TODO: Write a geoip test?
568}
tor_relay_selection/restriction.rs

tor_relay_selection/
restriction.rs
