tor_circmgr/
path.rs

1//! Code to construct paths through the Tor network
2//!
3//! TODO: I'm not sure this belongs in circmgr, but this is the best place
4//! I can think of for now.  I'm also not sure this should be public.
5
6pub(crate) mod dirpath;
7pub(crate) mod exitpath;
8
9// Care must be taken if/when we decide to make this pub.
10//
11// The `HsPathBuilder` exposes two path building functions,
12// one that uses vanguards, and one that doesn't.
13// We want to strongly encourage the use of the vanguards-aware
14// version of the function whenever the `vanguards` feature is enabled,
15// without breaking any of its existing non-vanguard uses.
16#[cfg(feature = "hs-common")]
17pub(crate) mod hspath;
18
19use std::result::Result as StdResult;
20use std::time::SystemTime;
21
22use rand::Rng;
23
24use tor_error::{bad_api_usage, internal, Bug};
25#[cfg(feature = "geoip")]
26use tor_geoip::{CountryCode, HasCountryCode};
27use tor_guardmgr::fallback::FallbackDir;
28use tor_guardmgr::{GuardMgr, GuardMonitor, GuardUsable};
29use tor_linkspec::{HasAddrs, HasRelayIds, OwnedChanTarget, OwnedCircTarget, RelayIdSet};
30use tor_netdir::{FamilyRules, NetDir, Relay};
31use tor_relay_selection::{RelayExclusion, RelaySelectionConfig, RelaySelector, RelayUsage};
32use tor_rtcompat::Runtime;
33
34#[cfg(all(feature = "vanguards", feature = "hs-common"))]
35use tor_guardmgr::vanguards::Vanguard;
36
37use crate::usage::ExitPolicy;
38use crate::{DirInfo, Error, PathConfig, Result};
39
40/// A list of Tor relays through the network.
41pub struct TorPath<'a> {
42    /// The inner TorPath state.
43    inner: TorPathInner<'a>,
44}
45
46/// Non-public helper type to represent the different kinds of Tor path.
47///
48/// (This is a separate type to avoid exposing its details to the user.)
49///
50/// NOTE: This type should NEVER be visible outside of path.rs and its
51/// sub-modules.
52enum TorPathInner<'a> {
53    /// A single-hop path for use with a directory cache, when a relay is
54    /// known.
55    OneHop(Relay<'a>), // This could just be a routerstatus.
56    /// A single-hop path for use with a directory cache, when we don't have
57    /// a consensus.
58    FallbackOneHop(&'a FallbackDir),
59    /// A single-hop path taken from an OwnedChanTarget.
60    OwnedOneHop(OwnedChanTarget),
61    /// A multi-hop path, containing one or more relays.
62    Path(Vec<MaybeOwnedRelay<'a>>),
63}
64
65/// Identifier for a relay that could be either known from a NetDir, or
66/// specified as an OwnedCircTarget.
67///
68/// NOTE: This type should NEVER be visible outside of path.rs and its
69/// sub-modules.
70#[derive(Clone)]
71enum MaybeOwnedRelay<'a> {
72    /// A relay from the netdir.
73    Relay(Relay<'a>),
74    /// An owned description of a relay.
75    //
76    // TODO: I don't love boxing this, but it fixes a warning about
77    // variant sizes and is probably not the worst thing we could do.  OTOH, we
78    // could probably afford to use an Arc here and in guardmgr? -nickm
79    //
80    // TODO: Try using an Arc. -nickm
81    Owned(Box<OwnedCircTarget>),
82}
83
84impl<'a> MaybeOwnedRelay<'a> {
85    /// Extract an OwnedCircTarget from this relay.
86    fn to_owned(&self) -> OwnedCircTarget {
87        match self {
88            MaybeOwnedRelay::Relay(r) => OwnedCircTarget::from_circ_target(r),
89            MaybeOwnedRelay::Owned(o) => o.as_ref().clone(),
90        }
91    }
92}
93
94impl<'a> From<OwnedCircTarget> for MaybeOwnedRelay<'a> {
95    fn from(ct: OwnedCircTarget) -> Self {
96        MaybeOwnedRelay::Owned(Box::new(ct))
97    }
98}
99impl<'a> From<Relay<'a>> for MaybeOwnedRelay<'a> {
100    fn from(r: Relay<'a>) -> Self {
101        MaybeOwnedRelay::Relay(r)
102    }
103}
104impl<'a> HasAddrs for MaybeOwnedRelay<'a> {
105    fn addrs(&self) -> &[std::net::SocketAddr] {
106        match self {
107            MaybeOwnedRelay::Relay(r) => r.addrs(),
108            MaybeOwnedRelay::Owned(r) => r.addrs(),
109        }
110    }
111}
112impl<'a> HasRelayIds for MaybeOwnedRelay<'a> {
113    fn identity(
114        &self,
115        key_type: tor_linkspec::RelayIdType,
116    ) -> Option<tor_linkspec::RelayIdRef<'_>> {
117        match self {
118            MaybeOwnedRelay::Relay(r) => r.identity(key_type),
119            MaybeOwnedRelay::Owned(r) => r.identity(key_type),
120        }
121    }
122}
123
124#[cfg(all(feature = "vanguards", feature = "hs-common"))]
125impl<'a> From<Vanguard<'a>> for MaybeOwnedRelay<'a> {
126    fn from(r: Vanguard<'a>) -> Self {
127        MaybeOwnedRelay::Relay(r.relay().clone())
128    }
129}
130
131impl<'a> TorPath<'a> {
132    /// Create a new one-hop path for use with a directory cache with a known
133    /// relay.
134    pub fn new_one_hop(relay: Relay<'a>) -> Self {
135        Self {
136            inner: TorPathInner::OneHop(relay),
137        }
138    }
139
140    /// Create a new one-hop path for use with a directory cache when we don't
141    /// have a consensus.
142    pub fn new_fallback_one_hop(fallback_dir: &'a FallbackDir) -> Self {
143        Self {
144            inner: TorPathInner::FallbackOneHop(fallback_dir),
145        }
146    }
147
148    /// Construct a new one-hop path for directory use from an arbitrarily
149    /// chosen channel target.
150    pub fn new_one_hop_owned<T: tor_linkspec::ChanTarget>(target: &T) -> Self {
151        Self {
152            inner: TorPathInner::OwnedOneHop(OwnedChanTarget::from_chan_target(target)),
153        }
154    }
155
156    /// Create a new multi-hop path with a given number of ordered relays.
157    pub fn new_multihop(relays: impl IntoIterator<Item = Relay<'a>>) -> Self {
158        Self {
159            inner: TorPathInner::Path(relays.into_iter().map(MaybeOwnedRelay::from).collect()),
160        }
161    }
162    /// Construct a new multi-hop path from a vector of `MaybeOwned`.
163    ///
164    /// Internal only; do not expose without fixing up this API a bit.
165    fn new_multihop_from_maybe_owned(relays: Vec<MaybeOwnedRelay<'a>>) -> Self {
166        Self {
167            inner: TorPathInner::Path(relays),
168        }
169    }
170
171    /// Return the final relay in this path, if this is a path for use
172    /// with exit circuits.
173    fn exit_relay(&self) -> Option<&MaybeOwnedRelay<'a>> {
174        match &self.inner {
175            TorPathInner::Path(relays) if !relays.is_empty() => Some(&relays[relays.len() - 1]),
176            _ => None,
177        }
178    }
179
180    /// Return the exit policy of the final relay in this path, if this is a
181    /// path for use with exit circuits with an exit taken from the network
182    /// directory.
183    pub(crate) fn exit_policy(&self) -> Option<ExitPolicy> {
184        self.exit_relay().and_then(|r| match r {
185            MaybeOwnedRelay::Relay(r) => Some(ExitPolicy::from_relay(r)),
186            MaybeOwnedRelay::Owned(_) => None,
187        })
188    }
189
190    /// Return the country code of the final relay in this path, if this is a
191    /// path for use with exit circuits with an exit taken from the network
192    /// directory.
193    #[cfg(feature = "geoip")]
194    pub(crate) fn country_code(&self) -> Option<CountryCode> {
195        self.exit_relay().and_then(|r| match r {
196            MaybeOwnedRelay::Relay(r) => r.country_code(),
197            MaybeOwnedRelay::Owned(_) => None,
198        })
199    }
200
201    /// Return the number of relays in this path.
202    #[allow(clippy::len_without_is_empty)]
203    pub fn len(&self) -> usize {
204        use TorPathInner::*;
205        match &self.inner {
206            OneHop(_) => 1,
207            FallbackOneHop(_) => 1,
208            OwnedOneHop(_) => 1,
209            Path(p) => p.len(),
210        }
211    }
212
213    /// Return true if every `Relay` in this path has the stable flag.
214    ///
215    /// Assumes that Owned elements of this path are stable.
216    pub(crate) fn appears_stable(&self) -> bool {
217        // TODO #504: this looks at low_level_details() in questionable way.
218        match &self.inner {
219            TorPathInner::OneHop(r) => r.low_level_details().is_flagged_stable(),
220            TorPathInner::FallbackOneHop(_) => true,
221            TorPathInner::OwnedOneHop(_) => true,
222            TorPathInner::Path(relays) => relays.iter().all(|maybe_owned| match maybe_owned {
223                MaybeOwnedRelay::Relay(r) => r.low_level_details().is_flagged_stable(),
224                MaybeOwnedRelay::Owned(_) => true,
225            }),
226        }
227    }
228}
229
230/// A path composed entirely of owned components.
231#[derive(Clone, Debug)]
232pub(crate) enum OwnedPath {
233    /// A path where we only know how to make circuits via CREATE_FAST.
234    ChannelOnly(OwnedChanTarget),
235    /// A path of one or more hops created via normal Tor handshakes.
236    Normal(Vec<OwnedCircTarget>),
237}
238
239impl<'a> TryFrom<&TorPath<'a>> for OwnedPath {
240    type Error = crate::Error;
241    fn try_from(p: &TorPath<'a>) -> Result<OwnedPath> {
242        use TorPathInner::*;
243
244        Ok(match &p.inner {
245            FallbackOneHop(h) => OwnedPath::ChannelOnly(OwnedChanTarget::from_chan_target(*h)),
246            OneHop(h) => OwnedPath::Normal(vec![OwnedCircTarget::from_circ_target(h)]),
247            OwnedOneHop(owned) => OwnedPath::ChannelOnly(owned.clone()),
248            Path(p) if !p.is_empty() => {
249                OwnedPath::Normal(p.iter().map(MaybeOwnedRelay::to_owned).collect())
250            }
251            Path(_) => {
252                return Err(bad_api_usage!("Path with no entries!").into());
253            }
254        })
255    }
256}
257
258impl OwnedPath {
259    /// Return the number of hops in this path.
260    #[allow(clippy::len_without_is_empty)]
261    pub(crate) fn len(&self) -> usize {
262        match self {
263            OwnedPath::ChannelOnly(_) => 1,
264            OwnedPath::Normal(p) => p.len(),
265        }
266    }
267}
268
269/// A path builder that builds multi-hop, anonymous paths.
270trait AnonymousPathBuilder {
271    /// Return the "target" that every chosen relay must be able to share a circuit with with.
272    fn compatible_with(&self) -> Option<&OwnedChanTarget>;
273
274    /// Return a short description of the path we're trying to build,
275    /// for error reporting purposes.
276    fn path_kind(&self) -> &'static str;
277
278    /// Find a suitable exit node from either the chosen exit or from the network directory.
279    ///
280    /// Return the exit, along with the usage for a middle node corresponding
281    /// to this exit.
282    fn pick_exit<'a, R: Rng>(
283        &self,
284        rng: &mut R,
285        netdir: &'a NetDir,
286        guard_exclusion: RelayExclusion<'a>,
287        rs_cfg: &RelaySelectionConfig<'_>,
288    ) -> Result<(Relay<'a>, RelayUsage)>;
289}
290
291/// Try to create and return a path corresponding to the requirements of
292/// this builder.
293fn pick_path<'a, B: AnonymousPathBuilder, R: Rng, RT: Runtime>(
294    builder: &B,
295    rng: &mut R,
296    netdir: DirInfo<'a>,
297    guards: &GuardMgr<RT>,
298    config: &PathConfig,
299    _now: SystemTime,
300) -> Result<(TorPath<'a>, GuardMonitor, GuardUsable)> {
301    let netdir = match netdir {
302        DirInfo::Directory(d) => d,
303        _ => {
304            return Err(bad_api_usage!(
305                "Tried to build a multihop path without a network directory"
306            )
307            .into())
308        }
309    };
310    let rs_cfg = config.relay_selection_config();
311    let family_rules = FamilyRules::from(netdir.params());
312
313    let target_exclusion = match builder.compatible_with() {
314        Some(ct) => {
315            // Exclude the target from appearing in other positions in the path.
316            let ids = RelayIdSet::from_iter(ct.identities().map(|id_ref| id_ref.to_owned()));
317            // TODO torspec#265: we do not apply same-family restrictions
318            // (a relay in the same family as the target can occur in the path).
319            //
320            // We need to decide if this is the correct behavior,
321            // and if so, document it in torspec.
322            RelayExclusion::exclude_identities(ids)
323        }
324        None => RelayExclusion::no_relays_excluded(),
325    };
326
327    // TODO-SPEC: Because of limitations in guard selection, we have to
328    // pick the guard before the exit, which is not what our spec says.
329    let (guard, mon, usable) = select_guard(netdir, guards, builder.compatible_with())?;
330
331    let guard_exclusion = match &guard {
332        MaybeOwnedRelay::Relay(r) => RelayExclusion::exclude_relays_in_same_family(
333            &config.relay_selection_config(),
334            vec![r.clone()],
335            family_rules,
336        ),
337        MaybeOwnedRelay::Owned(ct) => RelayExclusion::exclude_channel_target_family(
338            &config.relay_selection_config(),
339            ct.as_ref(),
340            netdir,
341        ),
342    };
343
344    let mut exclusion = guard_exclusion.clone();
345    exclusion.extend(&target_exclusion);
346    let (exit, middle_usage) = builder.pick_exit(rng, netdir, exclusion, &rs_cfg)?;
347
348    let mut family_exclusion =
349        RelayExclusion::exclude_relays_in_same_family(&rs_cfg, vec![exit.clone()], family_rules);
350    family_exclusion.extend(&guard_exclusion);
351    let mut exclusion = family_exclusion;
352    exclusion.extend(&target_exclusion);
353
354    let selector = RelaySelector::new(middle_usage, exclusion);
355    let (middle, info) = selector.select_relay(rng, netdir);
356    let middle = middle.ok_or_else(|| Error::NoRelay {
357        path_kind: builder.path_kind(),
358        role: "middle relay",
359        problem: info.to_string(),
360    })?;
361
362    let hops = vec![
363        guard,
364        MaybeOwnedRelay::from(middle),
365        MaybeOwnedRelay::from(exit),
366    ];
367
368    ensure_unique_hops(&hops)?;
369
370    Ok((TorPath::new_multihop_from_maybe_owned(hops), mon, usable))
371}
372
373/// Returns an error if the specified hop list contains duplicates.
374fn ensure_unique_hops<'a>(hops: &'a [MaybeOwnedRelay<'a>]) -> StdResult<(), Bug> {
375    for (i, hop) in hops.iter().enumerate() {
376        if let Some(hop2) = hops
377            .iter()
378            .skip(i + 1)
379            .find(|hop2| hop.clone().has_any_relay_id_from(*hop2))
380        {
381            return Err(internal!(
382                "invalid path: the IDs of hops {} and {} overlap?!",
383                hop.display_relay_ids(),
384                hop2.display_relay_ids()
385            ));
386        }
387    }
388    Ok(())
389}
390
391/// Try to select a guard corresponding to the requirements of
392/// this builder.
393fn select_guard<'a, RT: Runtime>(
394    netdir: &'a NetDir,
395    guardmgr: &GuardMgr<RT>,
396    compatible_with: Option<&OwnedChanTarget>,
397) -> Result<(MaybeOwnedRelay<'a>, GuardMonitor, GuardUsable)> {
398    // TODO: Extract this section into its own function, and see
399    // what it can share with tor_relay_selection.
400    let mut b = tor_guardmgr::GuardUsageBuilder::default();
401    b.kind(tor_guardmgr::GuardUsageKind::Data);
402    if let Some(avoid_target) = compatible_with {
403        let mut family = RelayIdSet::new();
404        family.extend(avoid_target.identities().map(|id| id.to_owned()));
405        if let Some(avoid_relay) = netdir.by_ids(avoid_target) {
406            family.extend(netdir.known_family_members(&avoid_relay).map(|r| *r.id()));
407        }
408        b.restrictions()
409            .push(tor_guardmgr::GuardRestriction::AvoidAllIds(family));
410    }
411    let guard_usage = b.build().expect("Failed while building guard usage!");
412    let (guard, mon, usable) = guardmgr.select_guard(guard_usage)?;
413    let guard = if let Some(ct) = guard.as_circ_target() {
414        // This is a bridge; we will not look for it in the network directory.
415        MaybeOwnedRelay::from(ct.clone())
416    } else {
417        // Look this up in the network directory: we expect to find a relay.
418        guard
419            .get_relay(netdir)
420            .ok_or_else(|| {
421                internal!(
422                    "Somehow the guardmgr gave us an unlisted guard {:?}!",
423                    guard
424                )
425            })?
426            .into()
427    };
428    Ok((guard, mon, usable))
429}
430
431/// For testing: make sure that `path` is the same when it is an owned
432/// path.
433#[cfg(test)]
434fn assert_same_path_when_owned(path: &TorPath<'_>) {
435    #![allow(clippy::unwrap_used)]
436    let owned: OwnedPath = path.try_into().unwrap();
437
438    match (&owned, &path.inner) {
439        (OwnedPath::ChannelOnly(c), TorPathInner::FallbackOneHop(f)) => {
440            assert!(c.same_relay_ids(*f));
441        }
442        (OwnedPath::Normal(p), TorPathInner::OneHop(h)) => {
443            assert_eq!(p.len(), 1);
444            assert!(p[0].same_relay_ids(h));
445        }
446        (OwnedPath::Normal(p1), TorPathInner::Path(p2)) => {
447            assert_eq!(p1.len(), p2.len());
448            for (n1, n2) in p1.iter().zip(p2.iter()) {
449                assert!(n1.same_relay_ids(n2));
450            }
451        }
452        (_, _) => {
453            panic!("Mismatched path types.");
454        }
455    }
456}