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

tor_circmgr/
path.rs
