Skip to main content

tor_netdir/
lib.rs

1#![cfg_attr(docsrs, feature(doc_cfg))]
2#![doc = include_str!("../README.md")]
3// @@ begin lint list maintained by maint/add_warning @@
4#![allow(renamed_and_removed_lints)] // @@REMOVE_WHEN(ci_arti_stable)
5#![allow(unknown_lints)] // @@REMOVE_WHEN(ci_arti_nightly)
6#![warn(missing_docs)]
7#![warn(noop_method_call)]
8#![warn(unreachable_pub)]
9#![warn(clippy::all)]
10#![deny(clippy::await_holding_lock)]
11#![deny(clippy::cargo_common_metadata)]
12#![deny(clippy::cast_lossless)]
13#![deny(clippy::checked_conversions)]
14#![allow(clippy::cognitive_complexity)] // See arti#2556
15#![deny(clippy::debug_assert_with_mut_call)]
16#![deny(clippy::exhaustive_enums)]
17#![deny(clippy::exhaustive_structs)]
18#![deny(clippy::expl_impl_clone_on_copy)]
19#![deny(clippy::fallible_impl_from)]
20#![deny(clippy::implicit_clone)]
21#![deny(clippy::large_stack_arrays)]
22#![warn(clippy::manual_ok_or)]
23#![deny(clippy::missing_docs_in_private_items)]
24#![warn(clippy::needless_borrow)]
25#![warn(clippy::needless_pass_by_value)]
26#![warn(clippy::option_option)]
27#![warn(clippy::or_fun_call)]
28#![deny(clippy::print_stderr)]
29#![deny(clippy::print_stdout)]
30#![warn(clippy::rc_buffer)]
31#![deny(clippy::ref_option_ref)]
32#![warn(clippy::semicolon_if_nothing_returned)]
33#![warn(clippy::trait_duplication_in_bounds)]
34#![deny(clippy::unchecked_time_subtraction)]
35#![deny(clippy::unnecessary_wraps)]
36#![warn(clippy::unseparated_literal_suffix)]
37#![deny(clippy::unwrap_used)]
38#![deny(clippy::mod_module_files)]
39#![allow(clippy::let_unit_value)] // This can reasonably be done for explicitness
40#![allow(clippy::uninlined_format_args)]
41#![allow(clippy::significant_drop_in_scrutinee)] // arti/-/merge_requests/588/#note_2812945
42#![allow(clippy::result_large_err)] // temporary workaround for arti#587
43#![allow(clippy::needless_raw_string_hashes)] // complained-about code is fine, often best
44#![allow(clippy::needless_lifetimes)] // See arti#1765
45#![allow(mismatched_lifetime_syntaxes)] // temporary workaround for arti#2060
46#![allow(clippy::collapsible_if)] // See arti#2342
47#![deny(clippy::unused_async)]
48#![deny(clippy::string_slice)] // See arti#2571
49#![allow(recursion_depth_exceeding_limit)] // arti#2715, rust/issues/159228
50//! <!-- @@ end lint list maintained by maint/add_warning @@ -->
51
52// TODO: add to the list maintained by maint/add_warning once it's available on all crates
53#![warn(unnameable_types)]
54
55pub mod details;
56mod err;
57#[cfg(feature = "hs-common")]
58mod hsdir_params;
59#[cfg(feature = "hs-common")]
60mod hsdir_ring;
61pub mod params;
62mod weight;
63
64#[cfg(any(test, feature = "testing"))]
65pub mod testnet;
66#[cfg(feature = "testing")]
67pub mod testprovider;
68
69use async_trait::async_trait;
70#[cfg(feature = "hs-service")]
71use itertools::chain;
72use tor_error::warn_report;
73#[cfg(feature = "hs-common")]
74use tor_linkspec::OwnedCircTarget;
75use tor_linkspec::{
76    ChanTarget, DirectChanMethodsHelper, HasAddrs, HasRelayIds, RelayIdRef, RelayIdType,
77};
78use tor_llcrypto as ll;
79use tor_llcrypto::pk::{ed25519::Ed25519Identity, rsa::RsaIdentity};
80use tor_netdoc::doc::microdesc::{MdDigest, MicrodescAndHash};
81use tor_netdoc::doc::netstatus::{self, MdConsensus, MdRouterStatus};
82#[cfg(feature = "hs-common")]
83use {hsdir_ring::HsDirRing, std::iter};
84
85use derive_more::{From, Into};
86use futures::{StreamExt, stream::BoxStream};
87use num_enum::{IntoPrimitive, TryFromPrimitive};
88use rand::seq::{IndexedRandom as _, SliceRandom as _, WeightError};
89use serde::Deserialize;
90use std::collections::HashMap;
91use std::net::IpAddr;
92use std::ops::Deref;
93use std::sync::Arc;
94use std::time::SystemTime;
95use strum::{EnumCount, EnumIter};
96use tracing::warn;
97use typed_index_collections::{TiSlice, TiVec};
98
99#[cfg(feature = "hs-common")]
100use {
101    itertools::Itertools,
102    std::collections::HashSet,
103    std::result::Result as StdResult,
104    tor_error::{Bug, internal},
105    tor_hscrypto::{pk::HsBlindId, time::TimePeriod},
106    tor_linkspec::{OwnedChanTargetBuilder, verbatim::VerbatimLinkSpecCircTarget},
107    tor_llcrypto::pk::curve25519,
108};
109
110pub use err::Error;
111pub use weight::WeightRole;
112/// A Result using the Error type from the tor-netdir crate
113pub type Result<T> = std::result::Result<T, Error>;
114
115#[cfg(feature = "hs-common")]
116pub use err::{OnionDirLookupError, VerbatimCircTargetDecodeError};
117
118use params::NetParameters;
119#[cfg(feature = "geoip")]
120use tor_geoip::{CountryCode, GeoipDb, HasCountryCode};
121
122#[cfg(feature = "hs-common")]
123pub use hsdir_params::HsDirParams;
124
125/// Index into the consensus relays
126///
127/// This is an index into the list of relays returned by
128/// [`.c_relays()`](ConsensusRelays::c_relays)
129/// (on the corresponding consensus or netdir).
130///
131/// This is just a `usize` inside, but using a newtype prevents getting a relay index
132/// confused with other kinds of slice indices or counts.
133///
134/// If you are in a part of the code which needs to work with multiple consensuses,
135/// the typechecking cannot tell if you try to index into the wrong consensus.
136#[derive(Debug, From, Into, Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Hash)]
137pub(crate) struct RouterStatusIdx(usize);
138
139/// Extension trait to provide index-type-safe `.c_relays()` method
140//
141// TODO: Really it would be better to have MdConsensns::relays() return TiSlice,
142// but that would be an API break there.
143pub(crate) trait ConsensusRelays {
144    /// Obtain the list of relays in the consensus
145    //
146    fn c_relays(&self) -> &TiSlice<RouterStatusIdx, MdRouterStatus>;
147}
148impl ConsensusRelays for MdConsensus {
149    fn c_relays(&self) -> &TiSlice<RouterStatusIdx, MdRouterStatus> {
150        TiSlice::from_ref(MdConsensus::relays(self))
151    }
152}
153impl ConsensusRelays for NetDir {
154    fn c_relays(&self) -> &TiSlice<RouterStatusIdx, MdRouterStatus> {
155        self.consensus.c_relays()
156    }
157}
158
159/// Configuration for determining when two relays have addresses "too close" in
160/// the network.
161///
162/// Used by `Relay::low_level_details().in_same_subnet()`.
163#[derive(Deserialize, Debug, Clone, Copy, Eq, PartialEq)]
164#[serde(deny_unknown_fields)]
165pub struct SubnetConfig {
166    /// Consider IPv4 nodes in the same /x to be the same family.
167    ///
168    /// If this value is 0, all nodes with IPv4 addresses will be in the
169    /// same family.  If this value is above 32, then no nodes will be
170    /// placed im the same family based on their IPv4 addresses.
171    subnets_family_v4: u8,
172    /// Consider IPv6 nodes in the same /x to be the same family.
173    ///
174    /// If this value is 0, all nodes with IPv6 addresses will be in the
175    /// same family.  If this value is above 128, then no nodes will be
176    /// placed im the same family based on their IPv6 addresses.
177    subnets_family_v6: u8,
178}
179
180impl Default for SubnetConfig {
181    fn default() -> Self {
182        Self::new(16, 32)
183    }
184}
185
186impl SubnetConfig {
187    /// Construct a new SubnetConfig from a pair of bit prefix lengths.
188    ///
189    /// The values are clamped to the appropriate ranges if they are
190    /// out-of-bounds.
191    pub fn new(subnets_family_v4: u8, subnets_family_v6: u8) -> Self {
192        Self {
193            subnets_family_v4,
194            subnets_family_v6,
195        }
196    }
197
198    /// Construct a new SubnetConfig such that addresses are not in the same
199    /// family with anything--not even with themselves.
200    pub fn no_addresses_match() -> SubnetConfig {
201        SubnetConfig {
202            subnets_family_v4: 33,
203            subnets_family_v6: 129,
204        }
205    }
206
207    /// Return true if the two addresses in the same subnet, according to this
208    /// configuration.
209    pub fn addrs_in_same_subnet(&self, a: &IpAddr, b: &IpAddr) -> bool {
210        match (a, b) {
211            (IpAddr::V4(a), IpAddr::V4(b)) => {
212                let bits = self.subnets_family_v4;
213                if bits > 32 {
214                    return false;
215                }
216                let a = u32::from_be_bytes(a.octets());
217                let b = u32::from_be_bytes(b.octets());
218                (a >> (32 - bits)) == (b >> (32 - bits))
219            }
220            (IpAddr::V6(a), IpAddr::V6(b)) => {
221                let bits = self.subnets_family_v6;
222                if bits > 128 {
223                    return false;
224                }
225                let a = u128::from_be_bytes(a.octets());
226                let b = u128::from_be_bytes(b.octets());
227                (a >> (128 - bits)) == (b >> (128 - bits))
228            }
229            _ => false,
230        }
231    }
232
233    /// Return true if any of the addresses in `a` shares a subnet with any of
234    /// the addresses in `b`, according to this configuration.
235    pub fn any_addrs_in_same_subnet<T, U>(&self, a: &T, b: &U) -> bool
236    where
237        T: tor_linkspec::HasAddrs,
238        U: tor_linkspec::HasAddrs,
239    {
240        a.addrs().any(|aa| {
241            b.addrs()
242                .any(|bb| self.addrs_in_same_subnet(&aa.ip(), &bb.ip()))
243        })
244    }
245
246    /// Return a new subnet configuration that is the union of `self` and
247    /// `other`.
248    ///
249    /// That is, return a subnet configuration that puts all addresses in the
250    /// same subnet if and only if at least one of `self` and `other` would put
251    /// them in the same subnet.
252    pub fn union(&self, other: &Self) -> Self {
253        use std::cmp::min;
254        Self {
255            subnets_family_v4: min(self.subnets_family_v4, other.subnets_family_v4),
256            subnets_family_v6: min(self.subnets_family_v6, other.subnets_family_v6),
257        }
258    }
259}
260
261/// Configuration for which listed family information to use when deciding
262/// whether relays belong to the same family.
263///
264/// Derived from network parameters.
265#[derive(Clone, Copy, Debug)]
266pub struct FamilyRules {
267    /// If true, we use family information from lists of family members.
268    use_family_lists: bool,
269    /// If true, we use family information from lists of family IDs and from family certs.
270    use_family_ids: bool,
271}
272
273impl<'a> From<&'a NetParameters> for FamilyRules {
274    fn from(params: &'a NetParameters) -> Self {
275        FamilyRules {
276            use_family_lists: bool::from(params.use_family_lists),
277            use_family_ids: bool::from(params.use_family_ids),
278        }
279    }
280}
281
282impl FamilyRules {
283    /// Return a `FamilyRules` that will use all recognized kinds of family information.
284    pub fn all_family_info() -> Self {
285        Self {
286            use_family_lists: true,
287            use_family_ids: true,
288        }
289    }
290
291    /// Return a `FamilyRules` that will ignore all family information declared by relays.
292    pub fn ignore_declared_families() -> Self {
293        Self {
294            use_family_lists: false,
295            use_family_ids: false,
296        }
297    }
298
299    /// Configure this `FamilyRules` to use (or not use) family information from
300    /// lists of family members.
301    pub fn use_family_lists(&mut self, val: bool) -> &mut Self {
302        self.use_family_lists = val;
303        self
304    }
305
306    /// Configure this `FamilyRules` to use (or not use) family information from
307    /// family IDs and family certs.
308    pub fn use_family_ids(&mut self, val: bool) -> &mut Self {
309        self.use_family_ids = val;
310        self
311    }
312
313    /// Return a `FamilyRules` that will look at every source of information
314    /// requested by `self` or by `other`.
315    pub fn union(&self, other: &Self) -> Self {
316        Self {
317            use_family_lists: self.use_family_lists || other.use_family_lists,
318            use_family_ids: self.use_family_ids || other.use_family_ids,
319        }
320    }
321}
322
323/// An opaque type representing the weight with which a relay or set of
324/// relays will be selected for a given role.
325///
326/// Most users should ignore this type, and just use pick_relay instead.
327#[derive(
328    Copy,
329    Clone,
330    Debug,
331    derive_more::Add,
332    derive_more::Sum,
333    derive_more::AddAssign,
334    Eq,
335    PartialEq,
336    Ord,
337    PartialOrd,
338)]
339pub struct RelayWeight(u64);
340
341impl RelayWeight {
342    /// Try to divide this weight by `rhs`.
343    ///
344    /// Return a ratio on success, or None on division-by-zero.
345    pub fn checked_div(&self, rhs: RelayWeight) -> Option<f64> {
346        if rhs.0 == 0 {
347            None
348        } else {
349            Some((self.0 as f64) / (rhs.0 as f64))
350        }
351    }
352
353    /// Compute a ratio `frac` of this weight.
354    ///
355    /// Return None if frac is less than zero, since negative weights
356    /// are impossible.
357    pub fn ratio(&self, frac: f64) -> Option<RelayWeight> {
358        let product = (self.0 as f64) * frac;
359        if product >= 0.0 && product.is_finite() {
360            Some(RelayWeight(product as u64))
361        } else {
362            None
363        }
364    }
365}
366
367impl From<u64> for RelayWeight {
368    fn from(val: u64) -> Self {
369        RelayWeight(val)
370    }
371}
372
373/// An operation for which we might be requesting a hidden service directory.
374#[derive(Copy, Clone, Debug, PartialEq)]
375// TODO: make this pub(crate) once NetDir::hs_dirs is removed
376#[non_exhaustive]
377pub enum HsDirOp {
378    /// Uploading an onion service descriptor.
379    #[cfg(feature = "hs-service")]
380    Upload,
381    /// Downloading an onion service descriptor.
382    Download,
383}
384
385/// A view of the Tor directory, suitable for use in building circuits.
386///
387/// Abstractly, a [`NetDir`] is a set of usable public [`Relay`]s, each of which
388/// has its own properties, identity, and correct weighted probability for use
389/// under different circumstances.
390///
391/// A [`NetDir`] is constructed by making a [`PartialNetDir`] from a consensus
392/// document, and then adding enough microdescriptors to that `PartialNetDir` so
393/// that it can be used to build paths. (Thus, if you have a NetDir, it is
394/// definitely adequate to build paths.)
395///
396/// # "Usable" relays
397///
398/// Many methods on NetDir are defined in terms of <a name="usable">"Usable"</a> relays.  Unless
399/// otherwise stated, a relay is "usable" if it is listed in the consensus,
400/// if we have full directory information for that relay (including a
401/// microdescriptor), and if that relay does not have any flags indicating that
402/// we should never use it. (Currently, `NoEdConsensus` is the only such flag.)
403///
404/// # Limitations
405///
406/// The current NetDir implementation assumes fairly strongly that every relay
407/// has an Ed25519 identity and an RSA identity, that the consensus is indexed
408/// by RSA identities, and that the Ed25519 identities are stored in
409/// microdescriptors.
410///
411/// If these assumptions someday change, then we'll have to revise the
412/// implementation.
413#[derive(Debug, Clone)]
414pub struct NetDir {
415    /// A microdescriptor consensus that lists the members of the network,
416    /// and maps each one to a 'microdescriptor' that has more information
417    /// about it
418    consensus: Arc<MdConsensus>,
419    /// A map from keys to integer values, distributed in the consensus,
420    /// and clamped to certain defaults.
421    params: NetParameters,
422    /// Map from routerstatus index, to that routerstatus's microdescriptor (if we have one.)
423    mds: TiVec<RouterStatusIdx, Option<Arc<MicrodescAndHash>>>,
424    /// Map from SHA256 of _missing_ microdescriptors to the index of their
425    /// corresponding routerstatus.
426    rsidx_by_missing: HashMap<MdDigest, RouterStatusIdx>,
427    /// Map from ed25519 identity to index of the routerstatus.
428    ///
429    /// Note that we don't know the ed25519 identity of a relay until
430    /// we get the microdescriptor for it, so this won't be filled in
431    /// until we get the microdescriptors.
432    ///
433    /// # Implementation note
434    ///
435    /// For this field, and for `rsidx_by_rsa`,
436    /// it might be cool to have references instead.
437    /// But that would make this into a self-referential structure,
438    /// which isn't possible in safe rust.
439    rsidx_by_ed: HashMap<Ed25519Identity, RouterStatusIdx>,
440    /// Map from RSA identity to index of the routerstatus.
441    ///
442    /// This is constructed at the same time as the NetDir object, so it
443    /// can be immutable.
444    rsidx_by_rsa: Arc<HashMap<RsaIdentity, RouterStatusIdx>>,
445
446    /// Hash ring(s) describing the onion service directory.
447    ///
448    /// This is empty in a PartialNetDir, and is filled in before the NetDir is
449    /// built.
450    //
451    // TODO hs: It is ugly to have this exist in a partially constructed state
452    // in a PartialNetDir.
453    // Ideally, a PartialNetDir would contain only an HsDirs<HsDirParams>,
454    // or perhaps nothing at all, here.
455    #[cfg(feature = "hs-common")]
456    hsdir_rings: Arc<HsDirs<HsDirRing>>,
457
458    /// Weight values to apply to a given relay when deciding how frequently
459    /// to choose it for a given role.
460    weights: weight::WeightSet,
461
462    #[cfg(feature = "geoip")]
463    /// Country codes for each router in our consensus.
464    ///
465    /// This is indexed by the `RouterStatusIdx` (i.e. a router idx of zero has
466    /// the country code at position zero in this array).
467    country_codes: Vec<Option<CountryCode>>,
468}
469
470/// Collection of hidden service directories (or parameters for them)
471///
472/// In [`NetDir`] this is used to store the actual hash rings.
473/// (But, in a NetDir in a [`PartialNetDir`], it contains [`HsDirRing`]s
474/// where only the `params` are populated, and the `ring` is empty.)
475///
476/// This same generic type is used as the return type from
477/// [`HsDirParams::compute`](HsDirParams::compute),
478/// where it contains the *parameters* for the primary and secondary rings.
479#[derive(Debug, Clone)]
480#[cfg(feature = "hs-common")]
481pub(crate) struct HsDirs<D> {
482    /// The current ring
483    ///
484    /// It corresponds to the time period containing the `valid-after` time in
485    /// the consensus. Its SRV is whatever SRV was most current at the time when
486    /// that time period began.
487    ///
488    /// This is the hash ring that we should use whenever we are fetching an
489    /// onion service descriptor.
490    current: D,
491
492    /// Secondary rings (based on the parameters for the previous and next time periods)
493    ///
494    /// Onion services upload to positions on these ring as well, based on how
495    /// far into the current time period this directory is, so that
496    /// not-synchronized clients can still find their descriptor.
497    ///
498    /// Note that with the current (2023) network parameters, with
499    /// `hsdir_interval = SRV lifetime = 24 hours` at most one of these
500    /// secondary rings will be active at a time.  We have two here in order
501    /// to conform with a more flexible regime in proposal 342.
502    //
503    // TODO: hs clients never need this; so I've made it not-present for them.
504    // But does that risk too much with respect to side channels?
505    //
506    // TODO: Perhaps we should refactor this so that it is clear that these
507    // are immutable?  On the other hand, the documentation for this type
508    // declares that it is immutable, so we are likely okay.
509    //
510    // TODO: this `Vec` is only ever 0,1,2 elements.
511    // Maybe it should be an ArrayVec or something.
512    #[cfg(feature = "hs-service")]
513    secondary: Vec<D>,
514}
515
516#[cfg(feature = "hs-common")]
517impl<D> HsDirs<D> {
518    /// Convert an `HsDirs<D>` to `HsDirs<D2>` by mapping each contained `D`
519    pub(crate) fn map<D2>(self, mut f: impl FnMut(D) -> D2) -> HsDirs<D2> {
520        HsDirs {
521            current: f(self.current),
522            #[cfg(feature = "hs-service")]
523            secondary: self.secondary.into_iter().map(f).collect(),
524        }
525    }
526
527    /// Iterate over some of the contained hsdirs, according to `secondary`
528    ///
529    /// The current ring is always included.
530    /// Secondary rings are included iff `secondary` and the `hs-service` feature is enabled.
531    fn iter_filter_secondary(&self, secondary: bool) -> impl Iterator<Item = &D> {
532        let i = iter::once(&self.current);
533
534        // With "hs-service" disabled, there are no secondary rings,
535        // so we don't care.
536        let _ = secondary;
537
538        #[cfg(feature = "hs-service")]
539        let i = chain!(i, self.secondary.iter().filter(move |_| secondary));
540
541        i
542    }
543
544    /// Iterate over all the contained hsdirs
545    pub(crate) fn iter(&self) -> impl Iterator<Item = &D> {
546        self.iter_filter_secondary(true)
547    }
548
549    /// Iterate over the hsdirs relevant for `op`
550    pub(crate) fn iter_for_op(&self, op: HsDirOp) -> impl Iterator<Item = &D> {
551        self.iter_filter_secondary(match op {
552            #[cfg(feature = "hs-service")]
553            HsDirOp::Upload => true,
554            HsDirOp::Download => false,
555        })
556    }
557}
558
559/// An event that a [`NetDirProvider`] can broadcast to indicate that a change in
560/// the status of its directory.
561#[derive(
562    Debug, Clone, Copy, PartialEq, Eq, EnumIter, EnumCount, IntoPrimitive, TryFromPrimitive,
563)]
564#[non_exhaustive]
565#[repr(u16)]
566pub enum DirEvent {
567    /// A new consensus has been received, and has enough information to be
568    /// used.
569    ///
570    /// This event is also broadcast when a new set of consensus parameters is
571    /// available, even if that set of parameters comes from a configuration
572    /// change rather than from the latest consensus.
573    NewConsensus,
574
575    /// New descriptors have been received for the current consensus.
576    ///
577    /// (This event is _not_ broadcast when receiving new descriptors for a
578    /// consensus which is not yet ready to replace the current consensus.)
579    NewDescriptors,
580
581    /// We have received updated recommendations and requirements
582    /// for which subprotocols we should have to use the network.
583    NewProtocolRecommendation,
584}
585
586/// The network directory provider is shutting down without giving us the
587/// netdir we asked for.
588#[derive(Clone, Copy, Debug, thiserror::Error)]
589#[error("Network directory provider is shutting down")]
590#[non_exhaustive]
591pub struct NetdirProviderShutdown;
592
593impl tor_error::HasKind for NetdirProviderShutdown {
594    fn kind(&self) -> tor_error::ErrorKind {
595        tor_error::ErrorKind::ArtiShuttingDown
596    }
597}
598
599/// How "timely" must a network directory be?
600///
601/// This enum is used as an argument when requesting a [`NetDir`] object from
602/// [`NetDirProvider`] and other APIs, to specify how recent the information
603/// must be in order to be useful.
604#[derive(Copy, Clone, Eq, PartialEq, Debug)]
605#[allow(clippy::exhaustive_enums)]
606pub enum Timeliness {
607    /// The network directory must be strictly timely.
608    ///
609    /// That is, it must be based on a consensus that valid right now, with no
610    /// tolerance for skew or consensus problems.
611    ///
612    /// Avoid using this option if you could use [`Timeliness::Timely`] instead.
613    Strict,
614    /// The network directory must be roughly timely.
615    ///
616    /// This is, it must be based on a consensus that is not _too_ far in the
617    /// future, and not _too_ far in the past.
618    ///
619    /// (The tolerances for "too far" will depend on configuration.)
620    ///
621    /// This is almost always the option that you want to use.
622    Timely,
623    /// Any network directory is permissible, regardless of how untimely.
624    ///
625    /// Avoid using this option if you could use [`Timeliness::Timely`] instead.
626    Unchecked,
627}
628
629/// An object that can provide [`NetDir`]s, as well as inform consumers when
630/// they might have changed.
631///
632/// It is the responsibility of the implementor of `NetDirProvider`
633/// to try to obtain an up-to-date `NetDir`,
634/// and continuously to maintain and update it.
635///
636/// In usual configurations, Arti uses `tor_dirmgr::DirMgr`
637/// as its `NetDirProvider`.
638#[async_trait]
639pub trait NetDirProvider: UpcastArcNetDirProvider + Send + Sync {
640    /// Return a network directory that's live according to the provided
641    /// `timeliness`.
642    fn netdir(&self, timeliness: Timeliness) -> Result<Arc<NetDir>>;
643
644    /// Return a reasonable netdir for general usage.
645    ///
646    /// This is an alias for
647    /// [`NetDirProvider::netdir`]`(`[`Timeliness::Timely`]`)`.
648    fn timely_netdir(&self) -> Result<Arc<NetDir>> {
649        self.netdir(Timeliness::Timely)
650    }
651
652    /// Return a new asynchronous stream that will receive notification
653    /// whenever the consensus has changed.
654    ///
655    /// Multiple events may be batched up into a single item: each time
656    /// this stream yields an event, all you can assume is that the event has
657    /// occurred at least once.
658    fn events(&self) -> BoxStream<'static, DirEvent>;
659
660    /// Return the latest network parameters.
661    ///
662    /// If we have no directory, return a reasonable set of defaults.
663    fn params(&self) -> Arc<dyn AsRef<NetParameters>>;
664
665    /// Get a NetDir from `provider`, waiting until one exists.
666    async fn wait_for_netdir(
667        &self,
668        timeliness: Timeliness,
669    ) -> std::result::Result<Arc<NetDir>, NetdirProviderShutdown> {
670        if let Ok(nd) = self.netdir(timeliness) {
671            return Ok(nd);
672        }
673
674        let mut stream = self.events();
675        loop {
676            // We need to retry `self.netdir()` before waiting for any stream events, to
677            // avoid deadlock.
678            //
679            // We ignore all errors here: they can all potentially be fixed by
680            // getting a fresh consensus, and they will all get warned about
681            // by the NetDirProvider itself.
682            if let Ok(nd) = self.netdir(timeliness) {
683                return Ok(nd);
684            }
685            match stream.next().await {
686                Some(_) => {}
687                None => {
688                    return Err(NetdirProviderShutdown);
689                }
690            }
691        }
692    }
693
694    /// Wait until `provider` lists `target`.
695    ///
696    /// NOTE: This might potentially wait indefinitely, if `target` is never actually
697    /// becomes listed in the directory.  It will exit if the `NetDirProvider` shuts down.
698    async fn wait_for_netdir_to_list(
699        &self,
700        target: &tor_linkspec::RelayIds,
701        timeliness: Timeliness,
702    ) -> std::result::Result<(), NetdirProviderShutdown> {
703        let mut events = self.events();
704        loop {
705            // See if the desired relay is in the netdir.
706            //
707            // We do this before waiting for any events, to avoid race conditions.
708            {
709                let netdir = self.wait_for_netdir(timeliness).await?;
710                if netdir.ids_listed(target) == Some(true) {
711                    return Ok(());
712                }
713                // If we reach this point, then ids_listed returned `Some(false)`,
714                // meaning "This relay is definitely not in the current directory";
715                // or it returned `None`, meaning "waiting for more information
716                // about this network directory.
717                // In both cases, it's reasonable to just wait for another netdir
718                // event and try again.
719            }
720            // We didn't find the relay; wait for the provider to have a new netdir
721            // or more netdir information.
722            if events.next().await.is_none() {
723                // The event stream is closed; the provider has shut down.
724                return Err(NetdirProviderShutdown);
725            }
726        }
727    }
728
729    /// Return the latest set of recommended and required protocols, if there is one.
730    ///
731    /// This may be more recent (or more available) than this provider's associated NetDir.
732    fn protocol_statuses(&self) -> Option<(SystemTime, Arc<netstatus::ProtoStatuses>)>;
733}
734
735#[async_trait]
736impl<T> NetDirProvider for Arc<T>
737where
738    T: NetDirProvider,
739{
740    fn netdir(&self, timeliness: Timeliness) -> Result<Arc<NetDir>> {
741        self.deref().netdir(timeliness)
742    }
743
744    fn timely_netdir(&self) -> Result<Arc<NetDir>> {
745        self.deref().timely_netdir()
746    }
747
748    fn events(&self) -> BoxStream<'static, DirEvent> {
749        self.deref().events()
750    }
751
752    fn params(&self) -> Arc<dyn AsRef<NetParameters>> {
753        self.deref().params()
754    }
755
756    async fn wait_for_netdir(
757        &self,
758        timeliness: Timeliness,
759    ) -> std::result::Result<Arc<NetDir>, NetdirProviderShutdown> {
760        self.deref().wait_for_netdir(timeliness).await
761    }
762
763    async fn wait_for_netdir_to_list(
764        &self,
765        target: &tor_linkspec::RelayIds,
766        timeliness: Timeliness,
767    ) -> std::result::Result<(), NetdirProviderShutdown> {
768        self.deref()
769            .wait_for_netdir_to_list(target, timeliness)
770            .await
771    }
772
773    fn protocol_statuses(&self) -> Option<(SystemTime, Arc<netstatus::ProtoStatuses>)> {
774        self.deref().protocol_statuses()
775    }
776}
777
778/// Helper trait: allows any `Arc<X>` to be upcast to a `Arc<dyn
779/// NetDirProvider>` if X is an implementation or supertrait of NetDirProvider.
780///
781/// This trait exists to work around a limitation in rust: when trait upcasting
782/// coercion is stable, this will be unnecessary.
783///
784/// The Rust tracking issue is <https://github.com/rust-lang/rust/issues/65991>.
785pub trait UpcastArcNetDirProvider {
786    /// Return a view of this object as an `Arc<dyn NetDirProvider>`
787    fn upcast_arc<'a>(self: Arc<Self>) -> Arc<dyn NetDirProvider + 'a>
788    where
789        Self: 'a;
790}
791
792impl<T> UpcastArcNetDirProvider for T
793where
794    T: NetDirProvider + Sized,
795{
796    fn upcast_arc<'a>(self: Arc<Self>) -> Arc<dyn NetDirProvider + 'a>
797    where
798        Self: 'a,
799    {
800        self
801    }
802}
803
804impl AsRef<NetParameters> for NetDir {
805    fn as_ref(&self) -> &NetParameters {
806        self.params()
807    }
808}
809
810/// A partially build NetDir -- it can't be unwrapped until it has
811/// enough information to build safe paths.
812#[derive(Debug, Clone)]
813pub struct PartialNetDir {
814    /// The netdir that's under construction.
815    netdir: NetDir,
816
817    /// The previous netdir, if we had one
818    ///
819    /// Used as a cache, so we can reuse information
820    #[cfg(feature = "hs-common")]
821    prev_netdir: Option<Arc<NetDir>>,
822}
823
824/// A view of a relay on the Tor network, suitable for building circuits.
825// TODO: This should probably be a more specific struct, with a trait
826// that implements it.
827#[derive(Clone)]
828pub struct Relay<'a> {
829    /// A router descriptor for this relay.
830    rs: &'a netstatus::MdRouterStatus,
831    /// A microdescriptor for this relay.
832    md: &'a MicrodescAndHash,
833    /// The country code this relay is in, if we know one.
834    #[cfg(feature = "geoip")]
835    cc: Option<CountryCode>,
836}
837
838/// A relay that we haven't checked for validity or usability in
839/// routing.
840#[derive(Debug)]
841pub struct UncheckedRelay<'a> {
842    /// A router descriptor for this relay.
843    rs: &'a netstatus::MdRouterStatus,
844    /// A microdescriptor for this relay, if there is one.
845    md: Option<&'a MicrodescAndHash>,
846    /// The country code this relay is in, if we know one.
847    #[cfg(feature = "geoip")]
848    cc: Option<CountryCode>,
849}
850
851/// A partial or full network directory that we can download
852/// microdescriptors for.
853pub trait MdReceiver {
854    /// Return an iterator over the digests for all of the microdescriptors
855    /// that this netdir is missing.
856    fn missing_microdescs(&self) -> Box<dyn Iterator<Item = &MdDigest> + '_>;
857    /// Add a microdescriptor to this netdir, if it was wanted.
858    ///
859    /// Return true if it was indeed wanted.
860    fn add_microdesc(&mut self, md: MicrodescAndHash) -> bool;
861    /// Return the number of missing microdescriptors.
862    fn n_missing(&self) -> usize;
863}
864
865impl PartialNetDir {
866    /// Create a new PartialNetDir with a given consensus, and no
867    /// microdescriptors loaded.
868    ///
869    /// If `replacement_params` is provided, override network parameters from
870    /// the consensus with those from `replacement_params`.
871    pub fn new(
872        consensus: MdConsensus,
873        replacement_params: Option<&netstatus::NetParamValues>,
874    ) -> Self {
875        Self::new_inner(
876            consensus,
877            replacement_params,
878            #[cfg(feature = "geoip")]
879            None,
880        )
881    }
882
883    /// Create a new PartialNetDir with GeoIP support.
884    ///
885    /// This does the same thing as `new()`, except the provided GeoIP database is used to add
886    /// country codes to relays.
887    #[cfg(feature = "geoip")]
888    pub fn new_with_geoip(
889        consensus: MdConsensus,
890        replacement_params: Option<&netstatus::NetParamValues>,
891        geoip_db: &GeoipDb,
892    ) -> Self {
893        Self::new_inner(consensus, replacement_params, Some(geoip_db))
894    }
895
896    /// Implementation of the `new()` functions.
897    fn new_inner(
898        consensus: MdConsensus,
899        replacement_params: Option<&netstatus::NetParamValues>,
900        #[cfg(feature = "geoip")] geoip_db: Option<&GeoipDb>,
901    ) -> Self {
902        let mut params = NetParameters::default();
903
904        // (We ignore unrecognized options here, since they come from
905        // the consensus, and we don't expect to recognize everything
906        // there.)
907        //
908        // TODO this is rather duplicative of NetParameters::from_netstatus
909        let _ = params.saturating_update(consensus.params().without_defaults().iter());
910
911        // Now see if the user has any parameters to override.
912        // (We have to do this now, or else changes won't be reflected in our
913        // weights.)
914        if let Some(replacement) = replacement_params {
915            for u in params.saturating_update(replacement.iter()) {
916                warn!("Unrecognized option: override_net_params.{}", u);
917            }
918        }
919
920        // Compute the weights we'll want to use for these relays.
921        let weights = weight::WeightSet::from_consensus(&consensus, &params);
922
923        let n_relays = consensus.c_relays().len();
924
925        let rsidx_by_missing = consensus
926            .c_relays()
927            .iter_enumerated()
928            .map(|(rsidx, rs)| (*rs.md_digest(), rsidx))
929            .collect();
930
931        let rsidx_by_rsa = consensus
932            .c_relays()
933            .iter_enumerated()
934            .map(|(rsidx, rs)| (*rs.rsa_identity(), rsidx))
935            .collect();
936
937        #[cfg(feature = "geoip")]
938        let country_codes = if let Some(db) = geoip_db {
939            consensus
940                .c_relays()
941                .iter()
942                .map(|rs| {
943                    db.lookup_country_code_multi(rs.addrs().map(|x| x.ip()))
944                        .cloned()
945                })
946                .collect()
947        } else {
948            Default::default()
949        };
950
951        #[cfg(feature = "hs-common")]
952        let hsdir_rings = Arc::new({
953            let params = HsDirParams::compute(&consensus, &params).expect("Invalid consensus!");
954            // TODO: It's a bit ugly to use expect above, but this function does
955            // not return a Result. On the other hand, the error conditions under which
956            // HsDirParams::compute can return Err are _very_ narrow and hard to
957            // hit; see documentation in that function.  As such, we probably
958            // don't need to have this return a Result.
959
960            params.map(HsDirRing::empty_from_params)
961        });
962
963        let netdir = NetDir {
964            consensus: Arc::new(consensus),
965            params,
966            mds: vec![None; n_relays].into(),
967            rsidx_by_missing,
968            rsidx_by_rsa: Arc::new(rsidx_by_rsa),
969            rsidx_by_ed: HashMap::with_capacity(n_relays),
970            #[cfg(feature = "hs-common")]
971            hsdir_rings,
972            weights,
973            #[cfg(feature = "geoip")]
974            country_codes,
975        };
976
977        PartialNetDir {
978            netdir,
979            #[cfg(feature = "hs-common")]
980            prev_netdir: None,
981        }
982    }
983
984    /// Return the declared lifetime of this PartialNetDir.
985    pub fn lifetime(&self) -> &netstatus::Lifetime {
986        self.netdir.lifetime()
987    }
988
989    /// Record a previous netdir, which can be used for reusing cached information
990    //
991    // Fills in as many missing microdescriptors as possible in this
992    // netdir, using the microdescriptors from the previous netdir.
993    //
994    // With HS enabled, stores the netdir for reuse of relay hash ring index values.
995    #[allow(clippy::needless_pass_by_value)] // prev might, or might not, be stored
996    pub fn fill_from_previous_netdir(&mut self, prev: Arc<NetDir>) {
997        for md in prev.mds.iter().flatten() {
998            self.netdir.add_arc_microdesc(md.clone());
999        }
1000
1001        #[cfg(feature = "hs-common")]
1002        {
1003            self.prev_netdir = Some(prev);
1004        }
1005    }
1006
1007    /// Compute the hash ring(s) for this NetDir
1008    #[cfg(feature = "hs-common")]
1009    fn compute_rings(&mut self) {
1010        let params = HsDirParams::compute(&self.netdir.consensus, &self.netdir.params)
1011            .expect("Invalid consensus");
1012        // TODO: see TODO by similar expect in new()
1013
1014        self.netdir.hsdir_rings =
1015            Arc::new(params.map(|params| {
1016                HsDirRing::compute(params, &self.netdir, self.prev_netdir.as_deref())
1017            }));
1018    }
1019
1020    /// Return true if this are enough information in this directory
1021    /// to build multihop paths.
1022    pub fn have_enough_paths(&self) -> bool {
1023        self.netdir.have_enough_paths()
1024    }
1025    /// If this directory has enough information to build multihop
1026    /// circuits, return it.
1027    pub fn unwrap_if_sufficient(
1028        #[allow(unused_mut)] mut self,
1029    ) -> std::result::Result<NetDir, PartialNetDir> {
1030        if self.netdir.have_enough_paths() {
1031            #[cfg(feature = "hs-common")]
1032            self.compute_rings();
1033            Ok(self.netdir)
1034        } else {
1035            Err(self)
1036        }
1037    }
1038}
1039
1040impl MdReceiver for PartialNetDir {
1041    fn missing_microdescs(&self) -> Box<dyn Iterator<Item = &MdDigest> + '_> {
1042        self.netdir.missing_microdescs()
1043    }
1044    fn add_microdesc(&mut self, md: MicrodescAndHash) -> bool {
1045        self.netdir.add_microdesc(md)
1046    }
1047    fn n_missing(&self) -> usize {
1048        self.netdir.n_missing()
1049    }
1050}
1051
1052impl NetDir {
1053    /// Return the declared lifetime of this NetDir.
1054    pub fn lifetime(&self) -> &netstatus::Lifetime {
1055        self.consensus.lifetime()
1056    }
1057
1058    /// Add `md` to this NetDir.
1059    ///
1060    /// Return true if we wanted it, and false otherwise.
1061    fn add_arc_microdesc(&mut self, md: Arc<MicrodescAndHash>) -> bool {
1062        if let Some(rsidx) = self.rsidx_by_missing.remove(md.digest()) {
1063            assert_eq!(self.c_relays()[rsidx].md_digest(), md.digest());
1064
1065            // There should never be two approved MDs in the same
1066            // consensus listing the same ID... but if there is,
1067            // we'll let the most recent one win.
1068            self.rsidx_by_ed.insert(*md.ed25519_id(), rsidx);
1069
1070            // Happy path: we did indeed want this one.
1071            self.mds[rsidx] = Some(md);
1072
1073            // Save some space in the missing-descriptor list.
1074            if self.rsidx_by_missing.len() < self.rsidx_by_missing.capacity() / 4 {
1075                self.rsidx_by_missing.shrink_to_fit();
1076            }
1077
1078            return true;
1079        }
1080
1081        // Either we already had it, or we never wanted it at all.
1082        false
1083    }
1084
1085    /// Construct a (possibly invalid) Relay object from a routerstatus and its
1086    /// index within the consensus.
1087    fn relay_from_rs_and_rsidx<'a>(
1088        &'a self,
1089        rs: &'a netstatus::MdRouterStatus,
1090        rsidx: RouterStatusIdx,
1091    ) -> UncheckedRelay<'a> {
1092        debug_assert_eq!(self.c_relays()[rsidx].rsa_identity(), rs.rsa_identity());
1093        let md = self.mds[rsidx].as_deref();
1094        if let Some(md) = md {
1095            debug_assert_eq!(rs.md_digest(), md.digest());
1096        }
1097
1098        UncheckedRelay {
1099            rs,
1100            md,
1101            #[cfg(feature = "geoip")]
1102            cc: self.country_codes.get(rsidx.0).copied().flatten(),
1103        }
1104    }
1105
1106    /// Return the value of the hsdir_n_replicas param.
1107    #[cfg(feature = "hs-common")]
1108    fn n_replicas(&self) -> u8 {
1109        self.params
1110            .hsdir_n_replicas
1111            .get()
1112            .try_into()
1113            .expect("BoundedInt did not enforce bounds")
1114    }
1115
1116    /// Return the spread parameter for the specified `op`.
1117    #[cfg(feature = "hs-common")]
1118    fn spread(&self, op: HsDirOp) -> usize {
1119        let spread = match op {
1120            HsDirOp::Download => self.params.hsdir_spread_fetch,
1121            #[cfg(feature = "hs-service")]
1122            HsDirOp::Upload => self.params.hsdir_spread_store,
1123        };
1124
1125        spread
1126            .get()
1127            .try_into()
1128            .expect("BoundedInt did not enforce bounds!")
1129    }
1130
1131    /// Select `spread` hsdir relays for the specified `hsid` from a given `ring`.
1132    ///
1133    /// Algorithm:
1134    ///
1135    /// for idx in 1..=n_replicas:
1136    ///       - let H = hsdir_ring::onion_service_index(id, replica, rand,
1137    ///         period).
1138    ///       - Find the position of H within hsdir_ring.
1139    ///       - Take elements from hsdir_ring starting at that position,
1140    ///         adding them to Dirs until we have added `spread` new elements
1141    ///         that were not there before.
1142    #[cfg(feature = "hs-common")]
1143    fn select_hsdirs<'h, 'r: 'h>(
1144        &'r self,
1145        hsid: HsBlindId,
1146        ring: &'h HsDirRing,
1147        spread: usize,
1148    ) -> impl Iterator<Item = Relay<'r>> + 'h {
1149        let n_replicas = self.n_replicas();
1150
1151        (1..=n_replicas) // 1-indexed !
1152            .flat_map({
1153                let mut selected_nodes = HashSet::new();
1154
1155                move |replica: u8| {
1156                    let hsdir_idx = hsdir_ring::service_hsdir_index(&hsid, replica, ring.params());
1157
1158                    ring.ring_items_at(hsdir_idx, spread, |(hsdir_idx, _)| {
1159                        // According to rend-spec 2.2.3:
1160                        //                                                  ... If any of those
1161                        // nodes have already been selected for a lower-numbered replica of the
1162                        // service, any nodes already chosen are disregarded (i.e. skipped over)
1163                        // when choosing a replica's hsdir_spread_store nodes.
1164                        selected_nodes.insert(*hsdir_idx)
1165                    })
1166                    .collect::<Vec<_>>()
1167                }
1168            })
1169            .filter_map(move |(_hsdir_idx, rs_idx)| {
1170                // This ought not to be None but let's not panic or bail if it is
1171                self.relay_by_rs_idx(*rs_idx)
1172            })
1173    }
1174
1175    /// Replace the overridden parameters in this netdir with `new_replacement`.
1176    ///
1177    /// After this function is done, the netdir's parameters will be those in
1178    /// the consensus, overridden by settings from `new_replacement`.  Any
1179    /// settings in the old replacement parameters will be discarded.
1180    pub fn replace_overridden_parameters(&mut self, new_replacement: &netstatus::NetParamValues) {
1181        // TODO(nickm): This is largely duplicate code from PartialNetDir::new().
1182        let mut new_params = NetParameters::default();
1183        let _ = new_params.saturating_update(self.consensus.params().without_defaults().iter());
1184        for u in new_params.saturating_update(new_replacement.iter()) {
1185            warn!("Unrecognized option: override_net_params.{}", u);
1186        }
1187
1188        self.params = new_params;
1189    }
1190
1191    /// Return an iterator over all Relay objects, including invalid ones
1192    /// that we can't use.
1193    pub fn all_relays(&self) -> impl Iterator<Item = UncheckedRelay<'_>> {
1194        // TODO: I'd like if we could memoize this so we don't have to
1195        // do so many hashtable lookups.
1196        self.c_relays()
1197            .iter_enumerated()
1198            .map(move |(rsidx, rs)| self.relay_from_rs_and_rsidx(rs, rsidx))
1199    }
1200    /// Return an iterator over all [usable](NetDir#usable) Relays.
1201    pub fn relays(&self) -> impl Iterator<Item = Relay<'_>> {
1202        self.all_relays().filter_map(UncheckedRelay::into_relay)
1203    }
1204
1205    /// Look up a relay's [`MicrodescAndHash`] by its [`RouterStatusIdx`]
1206    #[cfg_attr(not(feature = "hs-common"), allow(dead_code))]
1207    pub(crate) fn md_by_rsidx(&self, rsidx: RouterStatusIdx) -> Option<&MicrodescAndHash> {
1208        self.mds.get(rsidx)?.as_deref()
1209    }
1210
1211    /// Return a relay matching a given identity, if we have a
1212    /// _usable_ relay with that key.
1213    ///
1214    /// (Does not return [unusable](NetDir#usable) relays.)
1215    ///
1216    ///
1217    /// Note that a `None` answer is not always permanent: if a microdescriptor
1218    /// is subsequently added for a relay with this ID, the ID may become usable
1219    /// even if it was not usable before.
1220    pub fn by_id<'a, T>(&self, id: T) -> Option<Relay<'_>>
1221    where
1222        T: Into<RelayIdRef<'a>>,
1223    {
1224        let id = id.into();
1225        let answer = match id {
1226            RelayIdRef::Ed25519(ed25519) => {
1227                let rsidx = *self.rsidx_by_ed.get(ed25519)?;
1228                let rs = self.c_relays().get(rsidx).expect("Corrupt index");
1229
1230                self.relay_from_rs_and_rsidx(rs, rsidx).into_relay()?
1231            }
1232            RelayIdRef::Rsa(rsa) => self
1233                .by_rsa_id_unchecked(rsa)
1234                .and_then(UncheckedRelay::into_relay)?,
1235            other_type => self.relays().find(|r| r.has_identity(other_type))?,
1236        };
1237        assert!(answer.has_identity(id));
1238        Some(answer)
1239    }
1240
1241    /// Obtain a `Relay` given a `RouterStatusIdx`
1242    ///
1243    /// Differs from `relay_from_rs_and_rsi` as follows:
1244    ///  * That function expects the caller to already have an `MdRouterStatus`;
1245    ///    it checks with `debug_assert` that the relay in the netdir matches.
1246    ///  * That function panics if the `RouterStatusIdx` is invalid; this one returns `None`.
1247    ///  * That function returns an `UncheckedRelay`; this one a `Relay`.
1248    ///
1249    /// `None` could be returned here, even with a valid `rsi`,
1250    /// if `rsi` refers to an [unusable](NetDir#usable) relay.
1251    #[cfg_attr(not(feature = "hs-common"), allow(dead_code))]
1252    pub(crate) fn relay_by_rs_idx(&self, rs_idx: RouterStatusIdx) -> Option<Relay<'_>> {
1253        let rs = self.c_relays().get(rs_idx)?;
1254        let md = self.mds.get(rs_idx)?.as_deref();
1255        UncheckedRelay {
1256            rs,
1257            md,
1258            #[cfg(feature = "geoip")]
1259            cc: self.country_codes.get(rs_idx.0).copied().flatten(),
1260        }
1261        .into_relay()
1262    }
1263
1264    /// Return a relay with the same identities as those in `target`, if one
1265    /// exists.
1266    ///
1267    /// Does not return [unusable](NetDir#usable) relays.
1268    ///
1269    /// Note that a negative result from this method is not necessarily permanent:
1270    /// it may be the case that a relay exists,
1271    /// but we don't yet have enough information about it to know all of its IDs.
1272    /// To test whether a relay is *definitely* absent,
1273    /// use [`by_ids_detailed`](Self::by_ids_detailed)
1274    /// or [`ids_listed`](Self::ids_listed).
1275    ///
1276    /// # Limitations
1277    ///
1278    /// This will be very slow if `target` does not have an Ed25519 or RSA
1279    /// identity.
1280    pub fn by_ids<T>(&self, target: &T) -> Option<Relay<'_>>
1281    where
1282        T: HasRelayIds + ?Sized,
1283    {
1284        let mut identities = target.identities();
1285        // Don't try if there are no identities.
1286        let first_id = identities.next()?;
1287
1288        // Since there is at most one relay with each given ID type,
1289        // we only need to check the first relay we find.
1290        let candidate = self.by_id(first_id)?;
1291        if identities.all(|wanted_id| candidate.has_identity(wanted_id)) {
1292            Some(candidate)
1293        } else {
1294            None
1295        }
1296    }
1297
1298    /// Check whether there is a relay that has at least one identity from
1299    /// `target`, and which _could_ have every identity from `target`.
1300    /// If so, return such a relay.
1301    ///
1302    /// Return `Ok(None)` if we did not find a relay with any identity from `target`.
1303    ///
1304    /// Return `RelayLookupError::Impossible` if we found a relay with at least
1305    /// one identity from `target`, but that relay's other identities contradict
1306    /// what we learned from `target`.
1307    ///
1308    /// Does not return [unusable](NetDir#usable) relays.
1309    ///
1310    /// (This function is only useful if you need to distinguish the
1311    /// "impossible" case from the "no such relay known" case.)
1312    ///
1313    /// # Limitations
1314    ///
1315    /// This will be very slow if `target` does not have an Ed25519 or RSA
1316    /// identity.
1317    //
1318    // TODO HS: This function could use a better name.
1319    //
1320    // TODO: We could remove the feature restriction here once we think this API is
1321    // stable.
1322    #[cfg(feature = "hs-common")]
1323    pub fn by_ids_detailed<T>(
1324        &self,
1325        target: &T,
1326    ) -> std::result::Result<Option<Relay<'_>>, RelayLookupError>
1327    where
1328        T: HasRelayIds + ?Sized,
1329    {
1330        let candidate = target
1331            .identities()
1332            // Find all the relays that share any identity with this set of identities.
1333            .filter_map(|id| self.by_id(id))
1334            // We might find the same relay more than once under a different
1335            // identity, so we remove the duplicates.
1336            //
1337            // Since there is at most one relay per rsa identity per consensus,
1338            // this is a true uniqueness check under current construction rules.
1339            .unique_by(|r| r.rs.rsa_identity())
1340            // If we find two or more distinct relays, then have a contradiction.
1341            .at_most_one()
1342            .map_err(|_| RelayLookupError::Impossible)?;
1343
1344        // If we have no candidate, return None early.
1345        let candidate = match candidate {
1346            Some(relay) => relay,
1347            None => return Ok(None),
1348        };
1349
1350        // Now we know we have a single candidate.  Make sure that it does not have any
1351        // identity that does not match the target.
1352        if target
1353            .identities()
1354            .all(|wanted_id| match candidate.identity(wanted_id.id_type()) {
1355                None => true,
1356                Some(id) => id == wanted_id,
1357            })
1358        {
1359            Ok(Some(candidate))
1360        } else {
1361            Err(RelayLookupError::Impossible)
1362        }
1363    }
1364
1365    /// Return a boolean if this consensus definitely has (or does not have) a
1366    /// relay matching the listed identities.
1367    ///
1368    /// `Some(true)` indicates that the relay exists.
1369    /// `Some(false)` indicates that the relay definitely does not exist.
1370    /// `None` indicates that we can't yet tell whether such a relay exists,
1371    ///  due to missing information.
1372    fn id_pair_listed(&self, ed_id: &Ed25519Identity, rsa_id: &RsaIdentity) -> Option<bool> {
1373        let r = self.by_rsa_id_unchecked(rsa_id);
1374        match r {
1375            Some(unchecked) => {
1376                if !unchecked.rs.ed25519_id_is_usable() {
1377                    return Some(false);
1378                }
1379                // If md is present, then it's listed iff we have the right
1380                // ed id.  Otherwise we don't know if it's listed.
1381                unchecked.md.map(|md| md.ed25519_id() == ed_id)
1382            }
1383            None => {
1384                // Definitely not listed.
1385                Some(false)
1386            }
1387        }
1388    }
1389
1390    /// Check whether a relay exists (or may exist)
1391    /// with the same identities as those in `target`.
1392    ///
1393    /// `Some(true)` indicates that the relay exists.
1394    /// `Some(false)` indicates that the relay definitely does not exist.
1395    /// `None` indicates that we can't yet tell whether such a relay exists,
1396    ///  due to missing information.
1397    pub fn ids_listed<T>(&self, target: &T) -> Option<bool>
1398    where
1399        T: HasRelayIds + ?Sized,
1400    {
1401        let rsa_id = target.rsa_identity();
1402        let ed25519_id = target.ed_identity();
1403
1404        // TODO: If we later support more identity key types, this will
1405        // become incorrect.  This assertion might help us recognize that case.
1406        const _: () = assert!(RelayIdType::COUNT == 2);
1407
1408        match (rsa_id, ed25519_id) {
1409            (Some(r), Some(e)) => self.id_pair_listed(e, r),
1410            (Some(r), None) => Some(self.rsa_id_is_listed(r)),
1411            (None, Some(e)) => {
1412                if self.rsidx_by_ed.contains_key(e) {
1413                    Some(true)
1414                } else {
1415                    None
1416                }
1417            }
1418            (None, None) => None,
1419        }
1420    }
1421
1422    /// Return a (possibly [unusable](NetDir#usable)) relay with a given RSA identity.
1423    ///
1424    /// This API can be used to find information about a relay that is listed in
1425    /// the current consensus, even if we don't yet have enough information
1426    /// (like a microdescriptor) about the relay to use it.
1427    #[cfg_attr(feature = "experimental-api", visibility::make(pub))]
1428    #[cfg_attr(docsrs, doc(cfg(feature = "experimental-api")))]
1429    fn by_rsa_id_unchecked(&self, rsa_id: &RsaIdentity) -> Option<UncheckedRelay<'_>> {
1430        let rsidx = *self.rsidx_by_rsa.get(rsa_id)?;
1431        let rs = self.c_relays().get(rsidx).expect("Corrupt index");
1432        assert_eq!(rs.rsa_identity(), rsa_id);
1433        Some(self.relay_from_rs_and_rsidx(rs, rsidx))
1434    }
1435    /// Return the relay with a given RSA identity, if we have one
1436    /// and it is [usable](NetDir#usable).
1437    fn by_rsa_id(&self, rsa_id: &RsaIdentity) -> Option<Relay<'_>> {
1438        self.by_rsa_id_unchecked(rsa_id)?.into_relay()
1439    }
1440    /// Return true if `rsa_id` is listed in this directory, even if it isn't
1441    /// currently usable.
1442    ///
1443    /// (An "[unusable](NetDir#usable)" relay in this context is one for which we don't have full
1444    /// directory information.)
1445    #[cfg_attr(feature = "experimental-api", visibility::make(pub))]
1446    #[cfg_attr(docsrs, doc(cfg(feature = "experimental-api")))]
1447    fn rsa_id_is_listed(&self, rsa_id: &RsaIdentity) -> bool {
1448        self.by_rsa_id_unchecked(rsa_id).is_some()
1449    }
1450
1451    /// List the hsdirs in this NetDir, that should be in the HSDir rings
1452    ///
1453    /// The results are not returned in any particular order.
1454    #[cfg(feature = "hs-common")]
1455    fn all_hsdirs(&self) -> impl Iterator<Item = (RouterStatusIdx, Relay<'_>)> {
1456        self.c_relays().iter_enumerated().filter_map(|(rsidx, rs)| {
1457            let relay = self.relay_from_rs_and_rsidx(rs, rsidx);
1458            relay.is_hsdir_for_ring().then_some(())?;
1459            let relay = relay.into_relay()?;
1460            Some((rsidx, relay))
1461        })
1462    }
1463
1464    /// Return the parameters from the consensus, clamped to the
1465    /// correct ranges, with defaults filled in.
1466    ///
1467    /// NOTE: that unsupported parameters aren't returned here; only those
1468    /// values configured in the `params` module are available.
1469    pub fn params(&self) -> &NetParameters {
1470        &self.params
1471    }
1472
1473    /// Return a [`ProtoStatus`](netstatus::ProtoStatus) that lists the
1474    /// network's current requirements and recommendations for the list of
1475    /// protocols that every relay must implement.
1476    //
1477    // TODO HS: I am not sure this is the right API; other alternatives would be:
1478    //    * To expose the _required_ relay protocol list instead (since that's all that
1479    //      onion service implementations need).
1480    //    * To expose the client protocol list as well (for symmetry).
1481    //    * To expose the MdConsensus instead (since that's more general, although
1482    //      it restricts the future evolution of this API).
1483    //
1484    // I think that this is a reasonably good compromise for now, but I'm going
1485    // to put it behind the `hs-common` feature to give us time to consider more.
1486    #[cfg(feature = "hs-common")]
1487    pub fn relay_protocol_status(&self) -> &netstatus::ProtoStatus {
1488        self.consensus.relay_protocol_status()
1489    }
1490
1491    /// Return a [`ProtoStatus`](netstatus::ProtoStatus) that lists the
1492    /// network's current requirements and recommendations for the list of
1493    /// protocols that every relay must implement.
1494    //
1495    // TODO HS: See notes on relay_protocol_status above.
1496    #[cfg(feature = "hs-common")]
1497    pub fn client_protocol_status(&self) -> &netstatus::ProtoStatus {
1498        self.consensus.client_protocol_status()
1499    }
1500
1501    /// Construct a `CircTarget` from an externally provided list of link specifiers,
1502    /// and an externally provided onion key.
1503    ///
1504    /// This method is used in the onion service protocol,
1505    /// where introduction points and rendezvous points are specified using these inputs.
1506    ///
1507    /// This function is a member of `NetDir` so that it can provide a reasonable list of
1508    /// [`Protocols`](tor_protover::Protocols) capabilities for the generated `CircTarget`.
1509    /// It does not (and should not!) look up anything else from the directory.
1510    #[cfg(feature = "hs-common")]
1511    pub fn circ_target_from_verbatim_linkspecs(
1512        &self,
1513        linkspecs: &[tor_linkspec::EncodedLinkSpec],
1514        ntor_onion_key: &curve25519::PublicKey,
1515    ) -> StdResult<VerbatimLinkSpecCircTarget<OwnedCircTarget>, VerbatimCircTargetDecodeError> {
1516        use VerbatimCircTargetDecodeError as E;
1517        use tor_linkspec::CircTarget as _;
1518        use tor_linkspec::decode::Strictness;
1519
1520        let mut bld = OwnedCircTarget::builder();
1521        use tor_error::into_internal;
1522
1523        *bld.chan_target() =
1524            OwnedChanTargetBuilder::from_encoded_linkspecs(Strictness::Standard, linkspecs)?;
1525        let protocols = {
1526            let chan_target = bld.chan_target().build().map_err(into_internal!(
1527                "from_encoded_linkspecs gave an invalid output"
1528            ))?;
1529            match self
1530                .by_ids_detailed(&chan_target)
1531                .map_err(E::ImpossibleIds)?
1532            {
1533                Some(relay) => relay.protovers().clone(),
1534                None => self.relay_protocol_status().required_protocols().clone(),
1535            }
1536        };
1537        bld.protocols(protocols);
1538        bld.ntor_onion_key(*ntor_onion_key);
1539        Ok(VerbatimLinkSpecCircTarget::new(
1540            bld.build()
1541                .map_err(into_internal!("Failed to construct a valid circtarget"))?,
1542            linkspecs.to_vec(),
1543        ))
1544    }
1545
1546    /// Return weighted the fraction of relays we can use.  We only
1547    /// consider relays that match the predicate `usable`.  We weight
1548    /// this bandwidth according to the provided `role`.
1549    ///
1550    /// If _no_ matching relays in the consensus have a nonzero
1551    /// weighted bandwidth value, we fall back to looking at the
1552    /// unweighted fraction of matching relays.
1553    ///
1554    /// If there are no matching relays in the consensus, we return 0.0.
1555    fn frac_for_role<'a, F>(&'a self, role: WeightRole, usable: F) -> f64
1556    where
1557        F: Fn(&UncheckedRelay<'a>) -> bool,
1558    {
1559        let mut total_weight = 0_u64;
1560        let mut have_weight = 0_u64;
1561        let mut have_count = 0_usize;
1562        let mut total_count = 0_usize;
1563
1564        for r in self.all_relays() {
1565            if !usable(&r) {
1566                continue;
1567            }
1568            let w = self.weights.weight_rs_for_role(r.rs, role);
1569            total_weight += w;
1570            total_count += 1;
1571            if r.is_usable() {
1572                have_weight += w;
1573                have_count += 1;
1574            }
1575        }
1576
1577        if total_weight > 0 {
1578            // The consensus lists some weighted bandwidth so return the
1579            // fraction of the weighted bandwidth for which we have
1580            // descriptors.
1581            (have_weight as f64) / (total_weight as f64)
1582        } else if total_count > 0 {
1583            // The consensus lists no weighted bandwidth for these relays,
1584            // but at least it does list relays. Return the fraction of
1585            // relays for which it we have descriptors.
1586            (have_count as f64) / (total_count as f64)
1587        } else {
1588            // There are no relays of this kind in the consensus.  Return
1589            // 0.0, to avoid dividing by zero and giving NaN.
1590            0.0
1591        }
1592    }
1593    /// Return the estimated fraction of possible paths that we have
1594    /// enough microdescriptors to build.
1595    fn frac_usable_paths(&self) -> f64 {
1596        // TODO #504, TODO SPEC: We may want to add a set of is_flagged_fast() and/or
1597        // is_flagged_stable() checks here.  This will require spec clarification.
1598        let f_g = self.frac_for_role(WeightRole::Guard, |u| {
1599            u.low_level_details().is_suitable_as_guard()
1600        });
1601        let f_m = self.frac_for_role(WeightRole::Middle, |_| true);
1602        let f_e = if self.all_relays().any(|u| u.rs.is_flagged_exit()) {
1603            self.frac_for_role(WeightRole::Exit, |u| u.rs.is_flagged_exit())
1604        } else {
1605            // If there are no exits at all, we use f_m here.
1606            f_m
1607        };
1608        f_g * f_m * f_e
1609    }
1610    /// Return true if there is enough information in this NetDir to build
1611    /// multihop circuits.
1612    fn have_enough_paths(&self) -> bool {
1613        // TODO-A001: This should check for our guards as well, and
1614        // make sure that if they're listed in the consensus, we have
1615        // the descriptors for them.
1616
1617        // If we can build a randomly chosen path with at least this
1618        // probability, we know enough information to participate
1619        // on the network.
1620
1621        let min_frac_paths: f64 = self.params().min_circuit_path_threshold.as_fraction();
1622
1623        // What fraction of paths can we build?
1624        let available = self.frac_usable_paths();
1625
1626        available >= min_frac_paths
1627    }
1628    /// Choose a relay at random.
1629    ///
1630    /// Each relay is chosen with probability proportional to its weight
1631    /// in the role `role`, and is only selected if the predicate `usable`
1632    /// returns true for it.
1633    ///
1634    /// This function returns None if (and only if) there are no relays
1635    /// where `usable` returned true.
1636    ///
1637    /// A relay with zero weight will be chosen iff all `usable` relays have
1638    /// zero weight.
1639    //
1640    // TODO this API, with the `usable` closure, invites mistakes where we fail to
1641    // check conditions that are implied by the role we have selected for the relay:
1642    // call sites must include a call to `Relay::is_polarity_inverter()` or whatever.
1643    // IMO the `WeightRole` ought to imply a condition (and it should therefore probably
1644    // be renamed.)  -Diziet
1645    pub fn pick_relay<'a, R, P>(
1646        &'a self,
1647        rng: &mut R,
1648        role: WeightRole,
1649        usable: P,
1650    ) -> Option<Relay<'a>>
1651    where
1652        R: rand::Rng,
1653        P: FnMut(&Relay<'a>) -> bool,
1654    {
1655        let relays: Vec<_> = self.relays().filter(usable).collect();
1656
1657        tracing::trace!(?role, "picking from {} relays", relays.len());
1658
1659        // Preemptively check for and handle an empty sequence ourselves, since it's
1660        // cheap to do so and the `choose_weighted` behavior for this edge-case
1661        // is a bit unpredictable.
1662        // See e.g. <https://github.com/rust-random/rand/issues/1783>
1663        if relays.is_empty() {
1664            tracing::debug!(?role, "No eligible relays");
1665            return None;
1666        }
1667
1668        // This algorithm uses rand::distr::WeightedIndex, and uses
1669        // gives O(n) time and space  to build the index, plus O(log n)
1670        // sampling time.
1671        //
1672        // We might be better off building a WeightedIndex in advance
1673        // for each `role`, and then sampling it repeatedly until we
1674        // get a relay that satisfies `usable`.  Or we might not --
1675        // that depends heavily on the actual particulars of our
1676        // inputs.  We probably shouldn't make any changes there
1677        // unless profiling tells us that this function is in a hot
1678        // path.
1679        //
1680        // The C Tor sampling implementation goes through some trouble
1681        // here to try to make its path selection constant-time.  I
1682        // believe that there is no actual remotely exploitable
1683        // side-channel here however.  It could be worth analyzing in
1684        // the future.
1685        //
1686        // This code will give the wrong result if the total of all weights
1687        // can exceed u64::MAX.  We make sure that can't happen when we
1688        // set up `self.weights`.
1689        match relays[..].choose_weighted(rng, |r| {
1690            let weight = self.weights.weight_rs_for_role(r.rs, role);
1691            tracing::trace!("relay:{id:?} role:{role:?} weight:{weight}", id = r.id());
1692            weight
1693        }) {
1694            Ok(relay) => Some(relay.clone()),
1695            Err(WeightError::InsufficientNonZero) => {
1696                warn!(?self.weights, ?role,
1697                        "After filtering, all {} relays had zero weight. Choosing one at random. See bug #1907.",
1698                        relays.len());
1699                relays.choose(rng).cloned()
1700            }
1701            Err(e) => {
1702                warn_report!(
1703                    e,
1704                    "Unexpected error while choosing from {} relays for role {:?}",
1705                    relays.len(),
1706                    role
1707                );
1708                None
1709            }
1710        }
1711    }
1712
1713    /// Choose `n` items (relays) at random, using the provided weights.
1714    ///
1715    /// This is intended as an internal, easier-to-test, implementation of
1716    /// `pick_n_relays`. `T` is generic for testing, but intended to be `Relay`.
1717    ///
1718    /// Items are chosen without replacement: no item will be returned twice.
1719    ///
1720    /// If *all* items have zero-weight, then up to `n` will be chosen randomly
1721    /// and returned. Otherwise, never returns items with zero-weight.
1722    ///
1723    /// May return fewer than `n` items if there are fewer than `n` with non-zero weight
1724    /// (or all have zero-weight but there are fewer than `n` total).
1725    fn pick_n_weighted<R, T>(rng: &mut R, n: usize, weighted_items: &[(T, u64)]) -> Vec<T>
1726    where
1727        R: rand::Rng,
1728        T: Clone,
1729    {
1730        let mut sampled_items = match weighted_items[..]
1731            .sample_weighted(rng, n, |(_r, w)| *w as f64)
1732        {
1733            Err(e) => {
1734                warn_report!(e, "Unexpected error while sampling a set of items");
1735                Vec::new()
1736            }
1737            Ok(sampled_items) => {
1738                if sampled_items.len() < n {
1739                    // Too few items had nonzero weights: return all of those that are okay.
1740                    let nonzero_weight_items: Vec<_> = weighted_items
1741                        .iter()
1742                        .filter_map(|(i, w)| if *w > 0 { Some(i) } else { None })
1743                        .cloned()
1744                        .collect();
1745                    if nonzero_weight_items.is_empty() {
1746                        tracing::debug!(
1747                            "All {} items had zero weight! Picking some at random. See bug #1907.",
1748                            weighted_items.len()
1749                        );
1750                        let items: Vec<_> =
1751                            weighted_items.iter().map(|(i, _w)| i.clone()).collect();
1752                        if items.len() >= n {
1753                            items.sample(rng, n).cloned().collect()
1754                        } else {
1755                            items
1756                        }
1757                    } else {
1758                        tracing::debug!(
1759                            "After filtering, only had {}/{} items with nonzero weight. Returning them all. See bug #1907.",
1760                            nonzero_weight_items.len(),
1761                            weighted_items.len()
1762                        );
1763                        nonzero_weight_items
1764                    }
1765                } else {
1766                    sampled_items.map(|(i, _w)| i.clone()).collect()
1767                }
1768            }
1769        };
1770        sampled_items.shuffle(rng);
1771        sampled_items
1772    }
1773
1774    /// Choose `n` relay at random.
1775    ///
1776    /// Each relay is chosen with probability proportional to its weight
1777    /// in the role `role`, and is only selected if the predicate `usable`
1778    /// returns true for it.
1779    ///
1780    /// Relays are chosen without replacement: no relay will be
1781    /// returned twice. Therefore, the resulting vector may be smaller
1782    /// than `n` if we happen to have fewer than `n` appropriate relays.
1783    ///
1784    /// Relays with zero-weight will be chosen only if there are *no* usable
1785    /// relays with nonzero-weight.
1786    ///
1787    /// This function returns an empty vector if (and only if) there are no
1788    /// relays where `usable` returned true.
1789    pub fn pick_n_relays<'a, R, P>(
1790        &'a self,
1791        rng: &mut R,
1792        n: usize,
1793        role: WeightRole,
1794        usable: P,
1795    ) -> Vec<Relay<'a>>
1796    where
1797        R: rand::Rng,
1798        P: FnMut(&Relay<'a>) -> bool,
1799    {
1800        let filtered_weighted_relays: Vec<(Relay<'a>, u64)> = self
1801            .relays()
1802            .filter(usable)
1803            .map(|r| (r.clone(), self.weights.weight_rs_for_role(r.rs, role)))
1804            .collect();
1805        let res = NetDir::pick_n_weighted(rng, n, filtered_weighted_relays.as_slice());
1806        let n_found = res.len();
1807        if n_found < n {
1808            warn!(?self.weights, ?role,
1809                "Requested {n} relays, but only {n_usable} were usable, and only {n_found} were chosen after weighting {role:?}.",
1810                n_usable=filtered_weighted_relays.len(),
1811            );
1812        }
1813        res
1814    }
1815
1816    /// Compute the weight with which `relay` will be selected for a given
1817    /// `role`.
1818    pub fn relay_weight<'a>(&'a self, relay: &Relay<'a>, role: WeightRole) -> RelayWeight {
1819        RelayWeight(self.weights.weight_rs_for_role(relay.rs, role))
1820    }
1821
1822    /// Compute the total weight with which any relay matching `usable`
1823    /// will be selected for a given `role`.
1824    ///
1825    /// Note: because this function is used to assess the total
1826    /// properties of the consensus, the `usable` predicate takes a
1827    /// [`MdRouterStatus`] rather than a [`Relay`].
1828    pub fn total_weight<P>(&self, role: WeightRole, usable: P) -> RelayWeight
1829    where
1830        P: Fn(&UncheckedRelay<'_>) -> bool,
1831    {
1832        self.all_relays()
1833            .filter_map(|unchecked| {
1834                if usable(&unchecked) {
1835                    Some(RelayWeight(
1836                        self.weights.weight_rs_for_role(unchecked.rs, role),
1837                    ))
1838                } else {
1839                    None
1840                }
1841            })
1842            .sum()
1843    }
1844
1845    /// Compute the weight with which a relay with ID `rsa_id` would be
1846    /// selected for a given `role`.
1847    ///
1848    /// Note that weight returned by this function assumes that the
1849    /// relay with that ID is actually [usable](NetDir#usable); if it isn't usable,
1850    /// then other weight-related functions will call its weight zero.
1851    pub fn weight_by_rsa_id(&self, rsa_id: &RsaIdentity, role: WeightRole) -> Option<RelayWeight> {
1852        self.by_rsa_id_unchecked(rsa_id)
1853            .map(|unchecked| RelayWeight(self.weights.weight_rs_for_role(unchecked.rs, role)))
1854    }
1855
1856    /// Return all relays in this NetDir known to be in the same family as
1857    /// `relay`.
1858    ///
1859    /// This list of members will **not** necessarily include `relay` itself.
1860    ///
1861    /// # Limitations
1862    ///
1863    /// Two relays only belong to the same family if _each_ relay
1864    /// claims to share a family with the other.  But if we are
1865    /// missing a microdescriptor for one of the relays listed by this
1866    /// relay, we cannot know whether it acknowledges family
1867    /// membership with this relay or not.  Therefore, this function
1868    /// can omit family members for which there is not (as yet) any
1869    /// Relay object.
1870    pub fn known_family_members<'a>(
1871        &'a self,
1872        relay: &'a Relay<'a>,
1873    ) -> impl Iterator<Item = Relay<'a>> {
1874        let relay_rsa_id = relay.rsa_id();
1875        relay.md.family().members().filter_map(move |other_rsa_id| {
1876            self.by_rsa_id(other_rsa_id)
1877                .filter(|other_relay| other_relay.md.family().contains(relay_rsa_id))
1878        })
1879    }
1880
1881    /// Return the current hidden service directory "time period".
1882    ///
1883    /// Specifically, this returns the time period that contains the beginning
1884    /// of the validity period of this `NetDir`'s consensus.  That time period
1885    /// is the one we use when acting as an hidden service client.
1886    #[cfg(feature = "hs-common")]
1887    pub fn hs_time_period(&self) -> TimePeriod {
1888        self.hsdir_rings.current.time_period()
1889    }
1890
1891    /// Return the [`HsDirParams`] of all the relevant hidden service directory "time periods"
1892    ///
1893    /// This includes the current time period (as from
1894    /// [`.hs_time_period`](NetDir::hs_time_period))
1895    /// plus additional time periods that we publish descriptors for when we are
1896    /// acting as a hidden service.
1897    #[cfg(feature = "hs-service")]
1898    pub fn hs_all_time_periods(&self) -> Vec<HsDirParams> {
1899        self.hsdir_rings
1900            .iter()
1901            .map(|r| r.params().clone())
1902            .collect()
1903    }
1904
1905    /// Return the relays in this network directory that will be used as hidden service directories
1906    ///
1907    /// These are suitable to retrieve a given onion service's descriptor at a given time period.
1908    #[cfg(feature = "hs-common")]
1909    pub fn hs_dirs_download<'r, R>(
1910        &'r self,
1911        hsid: HsBlindId,
1912        period: TimePeriod,
1913        rng: &mut R,
1914    ) -> std::result::Result<Vec<Relay<'r>>, Bug>
1915    where
1916        R: rand::Rng,
1917    {
1918        // Algorithm:
1919        //
1920        // 1. Determine which HsDirRing to use, based on the time period.
1921        // 2. Find the shared random value that's associated with that HsDirRing.
1922        // 3. Choose spread = the parameter `hsdir_spread_fetch`
1923        // 4. Let n_replicas = the parameter `hsdir_n_replicas`.
1924        // 5. Initialize Dirs = []
1925        // 6. for idx in 1..=n_replicas:
1926        //       - let H = hsdir_ring::onion_service_index(id, replica, rand,
1927        //         period).
1928        //       - Find the position of H within hsdir_ring.
1929        //       - Take elements from hsdir_ring starting at that position,
1930        //         adding them to Dirs until we have added `spread` new elements
1931        //         that were not there before.
1932        // 7. Shuffle Dirs
1933        // 8. return Dirs.
1934
1935        let spread = self.spread(HsDirOp::Download);
1936
1937        // When downloading, only look at relays on current ring.
1938        let ring = &self.hsdir_rings.current;
1939
1940        if ring.params().time_period != period {
1941            return Err(internal!(
1942                "our current ring is not associated with the requested time period!"
1943            ));
1944        }
1945
1946        let mut hs_dirs = self.select_hsdirs(hsid, ring, spread).collect_vec();
1947
1948        // When downloading, the order of the returned relays is random.
1949        hs_dirs.shuffle(rng);
1950
1951        Ok(hs_dirs)
1952    }
1953
1954    /// Return the relays in this network directory that will be used as hidden service directories
1955    ///
1956    /// Returns the relays that are suitable for storing a given onion service's descriptors at the
1957    /// given time period.
1958    #[cfg(feature = "hs-service")]
1959    pub fn hs_dirs_upload(
1960        &self,
1961        hsid: HsBlindId,
1962        period: TimePeriod,
1963    ) -> std::result::Result<impl Iterator<Item = Relay<'_>>, Bug> {
1964        // Algorithm:
1965        //
1966        // 1. Choose spread = the parameter `hsdir_spread_store`
1967        // 2. Determine which HsDirRing to use, based on the time period.
1968        // 3. Find the shared random value that's associated with that HsDirRing.
1969        // 4. Let n_replicas = the parameter `hsdir_n_replicas`.
1970        // 5. Initialize Dirs = []
1971        // 6. for idx in 1..=n_replicas:
1972        //       - let H = hsdir_ring::onion_service_index(id, replica, rand,
1973        //         period).
1974        //       - Find the position of H within hsdir_ring.
1975        //       - Take elements from hsdir_ring starting at that position,
1976        //         adding them to Dirs until we have added `spread` new elements
1977        //         that were not there before.
1978        // 3. return Dirs.
1979        let spread = self.spread(HsDirOp::Upload);
1980
1981        // For each HsBlindId, determine which HsDirRing to use.
1982        let rings = self
1983            .hsdir_rings
1984            .iter()
1985            .filter_map(move |ring| {
1986                // Make sure the ring matches the TP of the hsid it's matched with.
1987                (ring.params().time_period == period).then_some((ring, hsid, period))
1988            })
1989            .collect::<Vec<_>>();
1990
1991        // The specified period should have an associated ring.
1992        if !rings.iter().any(|(_, _, tp)| *tp == period) {
1993            return Err(internal!(
1994                "the specified time period does not have an associated ring"
1995            ));
1996        };
1997
1998        // Now that we've matched each `hsid` with the ring associated with its TP, we can start
1999        // selecting replicas from each ring.
2000        Ok(rings.into_iter().flat_map(move |(ring, hsid, period)| {
2001            assert_eq!(period, ring.params().time_period());
2002            self.select_hsdirs(hsid, ring, spread)
2003        }))
2004    }
2005
2006    /// Return the relays in this network directory that will be used as hidden service directories
2007    ///
2008    /// Depending on `op`,
2009    /// these are suitable to either store, or retrieve, a
2010    /// given onion service's descriptor at a given time period.
2011    ///
2012    /// When `op` is `Download`, the order is random.
2013    /// When `op` is `Upload`, the order is not specified.
2014    ///
2015    /// Return an error if the time period is not one returned by
2016    /// `onion_service_time_period` or `onion_service_secondary_time_periods`.
2017    //
2018    // TODO: make HsDirOp pub(crate) once this is removed
2019    #[cfg(feature = "hs-common")]
2020    #[deprecated(note = "Use hs_dirs_upload or hs_dirs_download instead")]
2021    pub fn hs_dirs<'r, R>(&'r self, hsid: &HsBlindId, op: HsDirOp, rng: &mut R) -> Vec<Relay<'r>>
2022    where
2023        R: rand::Rng,
2024    {
2025        // Algorithm:
2026        //
2027        // 1. Determine which HsDirRing to use, based on the time period.
2028        // 2. Find the shared random value that's associated with that HsDirRing.
2029        // 3. Choose spread = the parameter `hsdir_spread_store` or
2030        //    `hsdir_spread_fetch` based on `op`.
2031        // 4. Let n_replicas = the parameter `hsdir_n_replicas`.
2032        // 5. Initialize Dirs = []
2033        // 6. for idx in 1..=n_replicas:
2034        //       - let H = hsdir_ring::onion_service_index(id, replica, rand,
2035        //         period).
2036        //       - Find the position of H within hsdir_ring.
2037        //       - Take elements from hsdir_ring starting at that position,
2038        //         adding them to Dirs until we have added `spread` new elements
2039        //         that were not there before.
2040        // 7. return Dirs.
2041        let n_replicas = self
2042            .params
2043            .hsdir_n_replicas
2044            .get()
2045            .try_into()
2046            .expect("BoundedInt did not enforce bounds");
2047
2048        let spread = match op {
2049            HsDirOp::Download => self.params.hsdir_spread_fetch,
2050            #[cfg(feature = "hs-service")]
2051            HsDirOp::Upload => self.params.hsdir_spread_store,
2052        };
2053
2054        let spread = spread
2055            .get()
2056            .try_into()
2057            .expect("BoundedInt did not enforce bounds!");
2058
2059        // TODO: I may be wrong here but I suspect that this function may
2060        // need refactoring so that it does not look at _all_ of the HsDirRings,
2061        // but only at the ones that corresponds to time periods for which
2062        // HsBlindId is valid.  Or I could be mistaken, in which case we should
2063        // have a comment to explain why I am, since the logic is subtle.
2064        // (For clients, there is only one ring.) -nickm
2065        //
2066        // (Actually, there is no need to follow through with the above TODO,
2067        // since this function is deprecated, and not used anywhere but the
2068        // tests.)
2069
2070        let mut hs_dirs = self
2071            .hsdir_rings
2072            .iter_for_op(op)
2073            .cartesian_product(1..=n_replicas) // 1-indexed !
2074            .flat_map({
2075                let mut selected_nodes = HashSet::new();
2076
2077                move |(ring, replica): (&HsDirRing, u8)| {
2078                    let hsdir_idx = hsdir_ring::service_hsdir_index(hsid, replica, ring.params());
2079
2080                    ring.ring_items_at(hsdir_idx, spread, |(hsdir_idx, _)| {
2081                        // According to rend-spec 2.2.3:
2082                        //                                                  ... If any of those
2083                        // nodes have already been selected for a lower-numbered replica of the
2084                        // service, any nodes already chosen are disregarded (i.e. skipped over)
2085                        // when choosing a replica's hsdir_spread_store nodes.
2086                        selected_nodes.insert(*hsdir_idx)
2087                    })
2088                    .collect::<Vec<_>>()
2089                }
2090            })
2091            .filter_map(|(_hsdir_idx, rs_idx)| {
2092                // This ought not to be None but let's not panic or bail if it is
2093                self.relay_by_rs_idx(*rs_idx)
2094            })
2095            .collect_vec();
2096
2097        match op {
2098            HsDirOp::Download => {
2099                // When `op` is `Download`, the order is random.
2100                hs_dirs.shuffle(rng);
2101            }
2102            #[cfg(feature = "hs-service")]
2103            HsDirOp::Upload => {
2104                // When `op` is `Upload`, the order is not specified.
2105            }
2106        }
2107
2108        hs_dirs
2109    }
2110}
2111
2112impl MdReceiver for NetDir {
2113    fn missing_microdescs(&self) -> Box<dyn Iterator<Item = &MdDigest> + '_> {
2114        Box::new(self.rsidx_by_missing.keys())
2115    }
2116    fn add_microdesc(&mut self, md: MicrodescAndHash) -> bool {
2117        self.add_arc_microdesc(Arc::new(md))
2118    }
2119    fn n_missing(&self) -> usize {
2120        self.rsidx_by_missing.len()
2121    }
2122}
2123
2124impl<'a> UncheckedRelay<'a> {
2125    /// Return an [`UncheckedRelayDetails`](details::UncheckedRelayDetails) for this relay.
2126    ///
2127    /// Callers should generally avoid using this information directly if they can;
2128    /// it's better to use a higher-level function that exposes semantic information
2129    /// rather than these properties.
2130    pub fn low_level_details(&self) -> details::UncheckedRelayDetails<'_> {
2131        details::UncheckedRelayDetails(self)
2132    }
2133
2134    /// Return true if this relay is valid and [usable](NetDir#usable).
2135    ///
2136    /// This function should return `true` for every Relay we expose
2137    /// to the user.
2138    pub fn is_usable(&self) -> bool {
2139        // No need to check for 'valid' or 'running': they are implicit.
2140        self.md.is_some() && self.rs.ed25519_id_is_usable()
2141    }
2142    /// If this is [usable](NetDir#usable), return a corresponding Relay object.
2143    pub fn into_relay(self) -> Option<Relay<'a>> {
2144        if self.is_usable() {
2145            Some(Relay {
2146                rs: self.rs,
2147                md: self.md?,
2148                #[cfg(feature = "geoip")]
2149                cc: self.cc,
2150            })
2151        } else {
2152            None
2153        }
2154    }
2155
2156    /// Return true if this relay is a hidden service directory
2157    ///
2158    /// Ie, if it is to be included in the hsdir ring.
2159    #[cfg(feature = "hs-common")]
2160    pub(crate) fn is_hsdir_for_ring(&self) -> bool {
2161        // TODO are there any other flags should we check?
2162        // rend-spec-v3 2.2.3 says just
2163        //   "each node listed in the current consensus with the HSDir flag"
2164        // Do we need to check ed25519_id_is_usable ?
2165        // See also https://gitlab.torproject.org/tpo/core/arti/-/issues/504
2166        self.rs.is_flagged_hsdir()
2167    }
2168}
2169
2170impl<'a> Relay<'a> {
2171    /// Return a [`RelayDetails`](details::RelayDetails) for this relay.
2172    ///
2173    /// Callers should generally avoid using this information directly if they can;
2174    /// it's better to use a higher-level function that exposes semantic information
2175    /// rather than these properties.
2176    pub fn low_level_details(&self) -> details::RelayDetails<'_> {
2177        details::RelayDetails(self)
2178    }
2179
2180    /// Return the Ed25519 ID for this relay.
2181    pub fn id(&self) -> &Ed25519Identity {
2182        self.md.ed25519_id()
2183    }
2184    /// Return the RsaIdentity for this relay.
2185    pub fn rsa_id(&self) -> &RsaIdentity {
2186        self.rs.rsa_identity()
2187    }
2188
2189    /// Return a reference to this relay's "router status" entry in
2190    /// the consensus.
2191    ///
2192    /// The router status entry contains information about the relay
2193    /// that the authorities voted on directly.  For most use cases,
2194    /// you shouldn't need them.
2195    ///
2196    /// This function is only available if the crate was built with
2197    /// its `experimental-api` feature.
2198    #[cfg(feature = "experimental-api")]
2199    pub fn rs(&self) -> &netstatus::MdRouterStatus {
2200        self.rs
2201    }
2202    /// Return a reference to this relay's "microdescriptor" entry in
2203    /// the consensus.
2204    ///
2205    /// A "microdescriptor" is a synopsis of the information about a relay,
2206    /// used to determine its capabilities and route traffic through it.
2207    /// For most use cases, you shouldn't need it.
2208    ///
2209    /// This function is only available if the crate was built with
2210    /// its `experimental-api` feature.
2211    #[cfg(feature = "experimental-api")]
2212    pub fn md(&self) -> &MicrodescAndHash {
2213        self.md
2214    }
2215}
2216
2217/// An error value returned from [`NetDir::by_ids_detailed`].
2218#[cfg(feature = "hs-common")]
2219#[derive(Clone, Debug, thiserror::Error)]
2220#[non_exhaustive]
2221pub enum RelayLookupError {
2222    /// We found a relay whose presence indicates that the provided set of
2223    /// identities is impossible to resolve.
2224    #[error("Provided set of identities is impossible according to consensus.")]
2225    Impossible,
2226}
2227
2228impl<'a> HasAddrs for Relay<'a> {
2229    fn addrs(&self) -> impl Iterator<Item = std::net::SocketAddr> {
2230        self.rs.addrs()
2231    }
2232}
2233#[cfg(feature = "geoip")]
2234impl<'a> HasCountryCode for Relay<'a> {
2235    fn country_code(&self) -> Option<CountryCode> {
2236        self.cc
2237    }
2238}
2239impl<'a> tor_linkspec::HasRelayIdsLegacy for Relay<'a> {
2240    fn ed_identity(&self) -> &Ed25519Identity {
2241        self.id()
2242    }
2243    fn rsa_identity(&self) -> &RsaIdentity {
2244        self.rsa_id()
2245    }
2246}
2247
2248impl<'a> HasRelayIds for UncheckedRelay<'a> {
2249    fn identity(&self, key_type: RelayIdType) -> Option<RelayIdRef<'_>> {
2250        match key_type {
2251            RelayIdType::Ed25519 if self.rs.ed25519_id_is_usable() => {
2252                self.md.map(|m| m.ed25519_id().into())
2253            }
2254            RelayIdType::Rsa => Some(self.rs.rsa_identity().into()),
2255            _ => None,
2256        }
2257    }
2258}
2259#[cfg(feature = "geoip")]
2260impl<'a> HasCountryCode for UncheckedRelay<'a> {
2261    fn country_code(&self) -> Option<CountryCode> {
2262        self.cc
2263    }
2264}
2265
2266impl<'a> DirectChanMethodsHelper for Relay<'a> {}
2267impl<'a> ChanTarget for Relay<'a> {}
2268
2269impl<'a> tor_linkspec::CircTarget for Relay<'a> {
2270    fn ntor_onion_key(&self) -> &ll::pk::curve25519::PublicKey {
2271        self.md.ntor_key()
2272    }
2273    fn protovers(&self) -> &tor_protover::Protocols {
2274        self.rs.protovers()
2275    }
2276}
2277
2278#[cfg(test)]
2279mod test {
2280    // @@ begin test lint list maintained by maint/add_warning @@
2281    #![allow(clippy::bool_assert_comparison)]
2282    #![allow(clippy::clone_on_copy)]
2283    #![allow(clippy::dbg_macro)]
2284    #![allow(clippy::mixed_attributes_style)]
2285    #![allow(clippy::print_stderr)]
2286    #![allow(clippy::print_stdout)]
2287    #![allow(clippy::single_char_pattern)]
2288    #![allow(clippy::unwrap_used)]
2289    #![allow(clippy::unchecked_time_subtraction)]
2290    #![allow(clippy::useless_vec)]
2291    #![allow(clippy::needless_pass_by_value)]
2292    #![allow(clippy::string_slice)] // See arti#2571
2293    //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
2294    use super::*;
2295    use crate::testnet::*;
2296    use float_eq::assert_float_eq;
2297    use std::collections::HashSet;
2298    use std::time::Duration;
2299    use tor_basic_utils::test_rng::{self, testing_rng};
2300    use tor_linkspec::{RelayIdType, RelayIds};
2301
2302    #[cfg(feature = "hs-common")]
2303    fn dummy_hs_blind_id() -> HsBlindId {
2304        let hsid = [2, 1, 1, 1].iter().cycle().take(32).cloned().collect_vec();
2305        let hsid = Ed25519Identity::new(hsid[..].try_into().unwrap());
2306        HsBlindId::from(hsid)
2307    }
2308
2309    // Basic functionality for a partial netdir: Add microdescriptors,
2310    // then you have a netdir.
2311    #[test]
2312    fn partial_netdir() {
2313        let (consensus, microdescs) = construct_network().unwrap();
2314        let dir = PartialNetDir::new(consensus, None);
2315
2316        // Check the lifetime
2317        let lifetime = dir.lifetime();
2318        assert_eq!(
2319            lifetime
2320                .valid_until()
2321                .duration_since(lifetime.valid_after())
2322                .unwrap(),
2323            Duration::new(86400, 0)
2324        );
2325
2326        // No microdescriptors, so we don't have enough paths, and can't
2327        // advance.
2328        assert!(!dir.have_enough_paths());
2329        let mut dir = match dir.unwrap_if_sufficient() {
2330            Ok(_) => panic!(),
2331            Err(d) => d,
2332        };
2333
2334        let missing: HashSet<_> = dir.missing_microdescs().collect();
2335        assert_eq!(missing.len(), 40);
2336        assert_eq!(missing.len(), dir.netdir.c_relays().len());
2337        for md in &microdescs {
2338            assert!(missing.contains(md.digest()));
2339        }
2340
2341        // Now add all the mds and try again.
2342        for md in microdescs {
2343            let wanted = dir.add_microdesc(md);
2344            assert!(wanted);
2345        }
2346
2347        let missing: HashSet<_> = dir.missing_microdescs().collect();
2348        assert!(missing.is_empty());
2349        assert!(dir.have_enough_paths());
2350        let _complete = match dir.unwrap_if_sufficient() {
2351            Ok(d) => d,
2352            Err(_) => panic!(),
2353        };
2354    }
2355
2356    #[test]
2357    fn override_params() {
2358        let (consensus, _microdescs) = construct_network().unwrap();
2359        let override_p = "bwweightscale=2 doesnotexist=77 circwindow=500"
2360            .parse()
2361            .unwrap();
2362        let dir = PartialNetDir::new(consensus.clone(), Some(&override_p));
2363        let params = &dir.netdir.params;
2364        assert_eq!(params.bw_weight_scale.get(), 2);
2365        assert_eq!(params.circuit_window.get(), 500_i32);
2366
2367        // try again without the override.
2368        let dir = PartialNetDir::new(consensus, None);
2369        let params = &dir.netdir.params;
2370        assert_eq!(params.bw_weight_scale.get(), 1_i32);
2371        assert_eq!(params.circuit_window.get(), 1000_i32);
2372    }
2373
2374    #[test]
2375    fn fill_from_previous() {
2376        let (consensus, microdescs) = construct_network().unwrap();
2377
2378        let mut dir = PartialNetDir::new(consensus.clone(), None);
2379        for md in microdescs.iter().skip(2) {
2380            let wanted = dir.add_microdesc(md.clone());
2381            assert!(wanted);
2382        }
2383        let dir1 = dir.unwrap_if_sufficient().unwrap();
2384        assert_eq!(dir1.missing_microdescs().count(), 2);
2385
2386        let mut dir = PartialNetDir::new(consensus, None);
2387        assert_eq!(dir.missing_microdescs().count(), 40);
2388        dir.fill_from_previous_netdir(Arc::new(dir1));
2389        assert_eq!(dir.missing_microdescs().count(), 2);
2390    }
2391
2392    #[test]
2393    fn path_count() {
2394        let low_threshold = "min_paths_for_circs_pct=64".parse().unwrap();
2395        let high_threshold = "min_paths_for_circs_pct=65".parse().unwrap();
2396
2397        let (consensus, microdescs) = construct_network().unwrap();
2398
2399        let mut dir = PartialNetDir::new(consensus.clone(), Some(&low_threshold));
2400        for (pos, md) in microdescs.iter().enumerate() {
2401            if pos % 7 == 2 {
2402                continue; // skip a few relays.
2403            }
2404            dir.add_microdesc(md.clone());
2405        }
2406        let dir = dir.unwrap_if_sufficient().unwrap();
2407
2408        // We  have 40 relays that we know about from the consensus.
2409        assert_eq!(dir.all_relays().count(), 40);
2410
2411        // But only 34 are usable.
2412        assert_eq!(dir.relays().count(), 34);
2413
2414        // For guards: mds 20..=39 correspond to Guard relays.
2415        // Their bandwidth is 2*(1000+2000+...10000) = 110_000.
2416        // We skipped 23, 30, and 37.  They have bandwidth
2417        // 4000 + 1000 + 8000 = 13_000.  So our fractional bandwidth
2418        // should be (110-13)/110.
2419        let f = dir.frac_for_role(WeightRole::Guard, |u| u.rs.is_flagged_guard());
2420        assert!(((97.0 / 110.0) - f).abs() < 0.000001);
2421
2422        // For exits: mds 10..=19 and 30..=39 correspond to Exit relays.
2423        // We skipped 16, 30,  and 37. Per above our fractional bandwidth is
2424        // (110-16)/110.
2425        let f = dir.frac_for_role(WeightRole::Exit, |u| u.rs.is_flagged_exit());
2426        assert!(((94.0 / 110.0) - f).abs() < 0.000001);
2427
2428        // For middles: all relays are middles. We skipped 2, 9, 16,
2429        // 23, 30, and 37. Per above our fractional bandwidth is
2430        // (220-33)/220
2431        let f = dir.frac_for_role(WeightRole::Middle, |_| true);
2432        assert!(((187.0 / 220.0) - f).abs() < 0.000001);
2433
2434        // Multiplying those together, we get the fraction of paths we can
2435        // build at ~0.64052066, which is above the threshold we set above for
2436        // MinPathsForCircsPct.
2437        let f = dir.frac_usable_paths();
2438        assert!((f - 0.64052066).abs() < 0.000001);
2439
2440        // But if we try again with a slightly higher threshold...
2441        let mut dir = PartialNetDir::new(consensus, Some(&high_threshold));
2442        for (pos, md) in microdescs.into_iter().enumerate() {
2443            if pos % 7 == 2 {
2444                continue; // skip a few relays.
2445            }
2446            dir.add_microdesc(md);
2447        }
2448        assert!(dir.unwrap_if_sufficient().is_err());
2449    }
2450
2451    /// Return a 3-tuple for use by `test_pick_*()` of an Rng, a number of
2452    /// iterations, and a tolerance.
2453    ///
2454    /// If the Rng is deterministic (the default), we can use a faster setup,
2455    /// with a higher tolerance and fewer iterations.  But if you've explicitly
2456    /// opted into randomization (or are replaying a seed from an earlier
2457    /// randomized test), we give you more iterations and a tighter tolerance.
2458    fn testing_rng_with_tolerances() -> (impl rand::Rng, usize, f64) {
2459        // Use a deterministic RNG if none is specified, since this is slow otherwise.
2460        let config = test_rng::Config::from_env().unwrap_or(test_rng::Config::Deterministic);
2461        let (iters, tolerance) = match config {
2462            test_rng::Config::Deterministic => (5000, 0.02),
2463            _ => (50000, 0.01),
2464        };
2465        (config.into_rng(), iters, tolerance)
2466    }
2467
2468    #[test]
2469    fn test_pick() {
2470        let (consensus, microdescs) = construct_network().unwrap();
2471        let mut dir = PartialNetDir::new(consensus, None);
2472        for md in microdescs.into_iter() {
2473            let wanted = dir.add_microdesc(md.clone());
2474            assert!(wanted);
2475        }
2476        let dir = dir.unwrap_if_sufficient().unwrap();
2477
2478        let (mut rng, total, tolerance) = testing_rng_with_tolerances();
2479
2480        let mut picked = [0_isize; 40];
2481        for _ in 0..total {
2482            let r = dir.pick_relay(&mut rng, WeightRole::Middle, |r| {
2483                r.low_level_details().supports_exit_port_ipv4(80)
2484            });
2485            let r = r.unwrap();
2486            let id_byte = r.identity(RelayIdType::Rsa).unwrap().as_bytes()[0];
2487            picked[id_byte as usize] += 1;
2488        }
2489        // non-exits should never get picked.
2490        picked[0..10].iter().for_each(|x| assert_eq!(*x, 0));
2491        picked[20..30].iter().for_each(|x| assert_eq!(*x, 0));
2492
2493        let picked_f: Vec<_> = picked.iter().map(|x| *x as f64 / total as f64).collect();
2494
2495        // We didn't we any non-default weights, so the other relays get
2496        // weighted proportional to their bandwidth.
2497        assert_float_eq!(picked_f[19], (10.0 / 110.0), abs <= tolerance);
2498        assert_float_eq!(picked_f[38], (9.0 / 110.0), abs <= tolerance);
2499        assert_float_eq!(picked_f[39], (10.0 / 110.0), abs <= tolerance);
2500    }
2501
2502    #[test]
2503    fn test_pick_multiple() {
2504        // This is mostly a copy of test_pick, except that it uses
2505        // pick_n_relays to pick several relays at once.
2506
2507        let dir = construct_netdir().unwrap_if_sufficient().unwrap();
2508
2509        let (mut rng, total, tolerance) = testing_rng_with_tolerances();
2510
2511        let mut picked = [0_isize; 40];
2512        for _ in 0..total / 4 {
2513            let relays = dir.pick_n_relays(&mut rng, 4, WeightRole::Middle, |r| {
2514                r.low_level_details().supports_exit_port_ipv4(80)
2515            });
2516            assert_eq!(relays.len(), 4);
2517            for r in relays {
2518                let id_byte = r.identity(RelayIdType::Rsa).unwrap().as_bytes()[0];
2519                picked[id_byte as usize] += 1;
2520            }
2521        }
2522        // non-exits should never get picked.
2523        picked[0..10].iter().for_each(|x| assert_eq!(*x, 0));
2524        picked[20..30].iter().for_each(|x| assert_eq!(*x, 0));
2525
2526        let picked_f: Vec<_> = picked.iter().map(|x| *x as f64 / total as f64).collect();
2527
2528        // We didn't we any non-default weights, so the other relays get
2529        // weighted proportional to their bandwidth.
2530        assert_float_eq!(picked_f[19], (10.0 / 110.0), abs <= tolerance);
2531        assert_float_eq!(picked_f[36], (7.0 / 110.0), abs <= tolerance);
2532        assert_float_eq!(picked_f[39], (10.0 / 110.0), abs <= tolerance);
2533    }
2534
2535    #[test]
2536    fn test_pick_multiple_from_insufficient() {
2537        // This is intended to test `NetDir::pick_n_relays`, but targets the internal,
2538        // easier-to-test `NetDir::pick_n_weighted` that is used to implement it.
2539
2540        let mut rng = testing_rng();
2541
2542        // If *any* item (relay) has non-zero weight, then we return only those, even if we asked for more.
2543        let mostly_zeros = vec![("dud1", 0), ("dud2", 0), ("ok", 1), ("dud3", 0)];
2544        for n in [1, 2, 10] {
2545            assert_eq!(
2546                NetDir::pick_n_weighted(&mut rng, n, &mostly_zeros[..]),
2547                vec!["ok"],
2548                "where n={n}"
2549            );
2550        }
2551
2552        // If *all* items have zero weight, and we ask for as many or more than
2553        // we have, we get back all of them.
2554        let all_zeros = vec![("dud1", 0), ("dud2", 0), ("dud3", 0)];
2555        let all_zeros_items = all_zeros.iter().map(|(x, _w)| *x).collect::<Vec<_>>();
2556        for n in [all_zeros.len(), all_zeros.len() + 10] {
2557            let mut res = NetDir::pick_n_weighted(&mut rng, n, &all_zeros[..]);
2558            res.sort();
2559            assert_eq!(res, all_zeros_items, "where n={n}");
2560        }
2561
2562        // If *all* items have zero weight, and we ask for fewer than we have,
2563        // we get back as many as we asked for.
2564        let n = all_zeros.len() / 2;
2565        let res = NetDir::pick_n_weighted(&mut rng, n, &all_zeros[..]);
2566        assert_eq!(res.len(), n);
2567    }
2568
2569    #[test]
2570    fn subnets() {
2571        let cfg = SubnetConfig::default();
2572
2573        fn same_net(cfg: &SubnetConfig, a: &str, b: &str) -> bool {
2574            cfg.addrs_in_same_subnet(&a.parse().unwrap(), &b.parse().unwrap())
2575        }
2576
2577        assert!(same_net(&cfg, "127.15.3.3", "127.15.9.9"));
2578        assert!(!same_net(&cfg, "127.15.3.3", "127.16.9.9"));
2579
2580        assert!(!same_net(&cfg, "127.15.3.3", "127::"));
2581
2582        assert!(same_net(&cfg, "ffff:ffff:90:33::", "ffff:ffff:91:34::"));
2583        assert!(!same_net(&cfg, "ffff:ffff:90:33::", "ffff:fffe:91:34::"));
2584
2585        let cfg = SubnetConfig {
2586            subnets_family_v4: 32,
2587            subnets_family_v6: 128,
2588        };
2589        assert!(!same_net(&cfg, "127.15.3.3", "127.15.9.9"));
2590        assert!(!same_net(&cfg, "ffff:ffff:90:33::", "ffff:ffff:91:34::"));
2591
2592        assert!(same_net(&cfg, "127.0.0.1", "127.0.0.1"));
2593        assert!(!same_net(&cfg, "127.0.0.1", "127.0.0.2"));
2594        assert!(same_net(&cfg, "ffff:ffff:90:33::", "ffff:ffff:90:33::"));
2595
2596        let cfg = SubnetConfig {
2597            subnets_family_v4: 33,
2598            subnets_family_v6: 129,
2599        };
2600        assert!(!same_net(&cfg, "127.0.0.1", "127.0.0.1"));
2601        assert!(!same_net(&cfg, "::", "::"));
2602    }
2603
2604    #[test]
2605    fn subnet_union() {
2606        let cfg1 = SubnetConfig {
2607            subnets_family_v4: 16,
2608            subnets_family_v6: 64,
2609        };
2610        let cfg2 = SubnetConfig {
2611            subnets_family_v4: 24,
2612            subnets_family_v6: 32,
2613        };
2614        let a1 = "1.2.3.4".parse().unwrap();
2615        let a2 = "1.2.10.10".parse().unwrap();
2616
2617        let a3 = "ffff:ffff::7".parse().unwrap();
2618        let a4 = "ffff:ffff:1234::8".parse().unwrap();
2619
2620        assert_eq!(cfg1.addrs_in_same_subnet(&a1, &a2), true);
2621        assert_eq!(cfg2.addrs_in_same_subnet(&a1, &a2), false);
2622
2623        assert_eq!(cfg1.addrs_in_same_subnet(&a3, &a4), false);
2624        assert_eq!(cfg2.addrs_in_same_subnet(&a3, &a4), true);
2625
2626        let cfg_u = cfg1.union(&cfg2);
2627        assert_eq!(
2628            cfg_u,
2629            SubnetConfig {
2630                subnets_family_v4: 16,
2631                subnets_family_v6: 32,
2632            }
2633        );
2634        assert_eq!(cfg_u.addrs_in_same_subnet(&a1, &a2), true);
2635        assert_eq!(cfg_u.addrs_in_same_subnet(&a3, &a4), true);
2636
2637        assert_eq!(cfg1.union(&cfg1), cfg1);
2638
2639        assert_eq!(cfg1.union(&SubnetConfig::no_addresses_match()), cfg1);
2640    }
2641
2642    #[test]
2643    fn relay_funcs() {
2644        let (consensus, microdescs) = construct_custom_network(
2645            |pos, nb, _| {
2646                if pos == 15 {
2647                    nb.rs.add_or_port("[f0f0::30]:9001".parse().unwrap());
2648                } else if pos == 20 {
2649                    nb.rs.add_or_port("[f0f0::3131]:9001".parse().unwrap());
2650                }
2651            },
2652            None,
2653        )
2654        .unwrap();
2655        let subnet_config = SubnetConfig::default();
2656        let all_family_info = FamilyRules::all_family_info();
2657        let mut dir = PartialNetDir::new(consensus, None);
2658        for md in microdescs.into_iter() {
2659            let wanted = dir.add_microdesc(md.clone());
2660            assert!(wanted);
2661        }
2662        let dir = dir.unwrap_if_sufficient().unwrap();
2663
2664        // Pick out a few relays by ID.
2665        let k0 = Ed25519Identity::from([0; 32]);
2666        let k1 = Ed25519Identity::from([1; 32]);
2667        let k2 = Ed25519Identity::from([2; 32]);
2668        let k3 = Ed25519Identity::from([3; 32]);
2669        let k10 = Ed25519Identity::from([10; 32]);
2670        let k15 = Ed25519Identity::from([15; 32]);
2671        let k20 = Ed25519Identity::from([20; 32]);
2672
2673        let r0 = dir.by_id(&k0).unwrap();
2674        let r1 = dir.by_id(&k1).unwrap();
2675        let r2 = dir.by_id(&k2).unwrap();
2676        let r3 = dir.by_id(&k3).unwrap();
2677        let r10 = dir.by_id(&k10).unwrap();
2678        let r15 = dir.by_id(&k15).unwrap();
2679        let r20 = dir.by_id(&k20).unwrap();
2680
2681        assert_eq!(r0.id(), &[0; 32].into());
2682        assert_eq!(r0.rsa_id(), &[0; 20].into());
2683        assert_eq!(r1.id(), &[1; 32].into());
2684        assert_eq!(r1.rsa_id(), &[1; 20].into());
2685
2686        assert!(r0.same_relay_ids(&r0));
2687        assert!(r1.same_relay_ids(&r1));
2688        assert!(!r1.same_relay_ids(&r0));
2689
2690        assert!(r0.low_level_details().is_dir_cache());
2691        assert!(!r1.low_level_details().is_dir_cache());
2692        assert!(r2.low_level_details().is_dir_cache());
2693        assert!(!r3.low_level_details().is_dir_cache());
2694
2695        assert!(!r0.low_level_details().supports_exit_port_ipv4(80));
2696        assert!(!r1.low_level_details().supports_exit_port_ipv4(80));
2697        assert!(!r2.low_level_details().supports_exit_port_ipv4(80));
2698        assert!(!r3.low_level_details().supports_exit_port_ipv4(80));
2699
2700        assert!(!r0.low_level_details().policies_allow_some_port());
2701        assert!(!r1.low_level_details().policies_allow_some_port());
2702        assert!(!r2.low_level_details().policies_allow_some_port());
2703        assert!(!r3.low_level_details().policies_allow_some_port());
2704        assert!(r10.low_level_details().policies_allow_some_port());
2705
2706        assert!(r0.low_level_details().in_same_family(&r0, all_family_info));
2707        assert!(r0.low_level_details().in_same_family(&r1, all_family_info));
2708        assert!(r1.low_level_details().in_same_family(&r0, all_family_info));
2709        assert!(r1.low_level_details().in_same_family(&r1, all_family_info));
2710        assert!(!r0.low_level_details().in_same_family(&r2, all_family_info));
2711        assert!(!r2.low_level_details().in_same_family(&r0, all_family_info));
2712        assert!(r2.low_level_details().in_same_family(&r2, all_family_info));
2713        assert!(r2.low_level_details().in_same_family(&r3, all_family_info));
2714
2715        assert!(r0.low_level_details().in_same_subnet(&r10, &subnet_config));
2716        assert!(r10.low_level_details().in_same_subnet(&r10, &subnet_config));
2717        assert!(r0.low_level_details().in_same_subnet(&r0, &subnet_config));
2718        assert!(r1.low_level_details().in_same_subnet(&r1, &subnet_config));
2719        assert!(!r1.low_level_details().in_same_subnet(&r2, &subnet_config));
2720        assert!(!r2.low_level_details().in_same_subnet(&r3, &subnet_config));
2721
2722        // Make sure IPv6 families work.
2723        let subnet_config = SubnetConfig {
2724            subnets_family_v4: 128,
2725            subnets_family_v6: 96,
2726        };
2727        assert!(r15.low_level_details().in_same_subnet(&r20, &subnet_config));
2728        assert!(!r15.low_level_details().in_same_subnet(&r1, &subnet_config));
2729
2730        // Make sure that subnet configs can be disabled.
2731        let subnet_config = SubnetConfig {
2732            subnets_family_v4: 255,
2733            subnets_family_v6: 255,
2734        };
2735        assert!(!r15.low_level_details().in_same_subnet(&r20, &subnet_config));
2736    }
2737
2738    #[test]
2739    fn test_badexit() {
2740        // make a netdir where relays 10-19 are badexit, and everybody
2741        // exits to 443 on IPv6.
2742        use tor_netdoc::types::relay_flags::RelayFlag;
2743        let netdir = construct_custom_netdir(|pos, nb, _| {
2744            if (10..20).contains(&pos) {
2745                nb.rs.add_flags(RelayFlag::BadExit);
2746            }
2747            nb.md.parse_ipv6_policy("accept 443").unwrap();
2748        })
2749        .unwrap()
2750        .unwrap_if_sufficient()
2751        .unwrap();
2752
2753        let e12 = netdir.by_id(&Ed25519Identity::from([12; 32])).unwrap();
2754        let e32 = netdir.by_id(&Ed25519Identity::from([32; 32])).unwrap();
2755
2756        assert!(!e12.low_level_details().supports_exit_port_ipv4(80));
2757        assert!(e32.low_level_details().supports_exit_port_ipv4(80));
2758
2759        assert!(!e12.low_level_details().supports_exit_port_ipv6(443));
2760        assert!(e32.low_level_details().supports_exit_port_ipv6(443));
2761        assert!(!e32.low_level_details().supports_exit_port_ipv6(555));
2762
2763        assert!(!e12.low_level_details().policies_allow_some_port());
2764        assert!(e32.low_level_details().policies_allow_some_port());
2765
2766        assert!(!e12.low_level_details().ipv4_policy().allows_some_port());
2767        assert!(!e12.low_level_details().ipv6_policy().allows_some_port());
2768        assert!(e32.low_level_details().ipv4_policy().allows_some_port());
2769        assert!(e32.low_level_details().ipv6_policy().allows_some_port());
2770
2771        assert!(
2772            e12.low_level_details()
2773                .ipv4_declared_policy()
2774                .allows_some_port()
2775        );
2776        assert!(
2777            e12.low_level_details()
2778                .ipv6_declared_policy()
2779                .allows_some_port()
2780        );
2781    }
2782
2783    #[cfg(feature = "experimental-api")]
2784    #[test]
2785    fn test_accessors() {
2786        let netdir = construct_netdir().unwrap_if_sufficient().unwrap();
2787
2788        let r4 = netdir.by_id(&Ed25519Identity::from([4; 32])).unwrap();
2789        let r16 = netdir.by_id(&Ed25519Identity::from([16; 32])).unwrap();
2790
2791        assert!(!r4.md().ipv4_policy().allows_some_port());
2792        assert!(r16.md().ipv4_policy().allows_some_port());
2793
2794        assert!(!r4.rs().is_flagged_exit());
2795        assert!(r16.rs().is_flagged_exit());
2796    }
2797
2798    #[test]
2799    fn test_by_id() {
2800        // Make a netdir that omits the microdescriptor for 0xDDDDDD...
2801        let netdir = construct_custom_netdir(|pos, nb, _| {
2802            nb.omit_md = pos == 13;
2803        })
2804        .unwrap();
2805
2806        let netdir = netdir.unwrap_if_sufficient().unwrap();
2807
2808        let r = netdir.by_id(&Ed25519Identity::from([0; 32])).unwrap();
2809        assert_eq!(r.id().as_bytes(), &[0; 32]);
2810
2811        assert!(netdir.by_id(&Ed25519Identity::from([13; 32])).is_none());
2812
2813        let r = netdir.by_rsa_id(&[12; 20].into()).unwrap();
2814        assert_eq!(r.rsa_id().as_bytes(), &[12; 20]);
2815        assert!(netdir.rsa_id_is_listed(&[12; 20].into()));
2816
2817        assert!(netdir.by_rsa_id(&[13; 20].into()).is_none());
2818
2819        assert!(netdir.by_rsa_id_unchecked(&[99; 20].into()).is_none());
2820        assert!(!netdir.rsa_id_is_listed(&[99; 20].into()));
2821
2822        let r = netdir.by_rsa_id_unchecked(&[13; 20].into()).unwrap();
2823        assert_eq!(r.rs.rsa_identity().as_bytes(), &[13; 20]);
2824        assert!(netdir.rsa_id_is_listed(&[13; 20].into()));
2825
2826        let pair_13_13 = RelayIds::builder()
2827            .ed_identity([13; 32].into())
2828            .rsa_identity([13; 20].into())
2829            .build()
2830            .unwrap();
2831        let pair_14_14 = RelayIds::builder()
2832            .ed_identity([14; 32].into())
2833            .rsa_identity([14; 20].into())
2834            .build()
2835            .unwrap();
2836        let pair_14_99 = RelayIds::builder()
2837            .ed_identity([14; 32].into())
2838            .rsa_identity([99; 20].into())
2839            .build()
2840            .unwrap();
2841
2842        let r = netdir.by_ids(&pair_13_13);
2843        assert!(r.is_none());
2844        let r = netdir.by_ids(&pair_14_14).unwrap();
2845        assert_eq!(r.identity(RelayIdType::Rsa).unwrap().as_bytes(), &[14; 20]);
2846        assert_eq!(
2847            r.identity(RelayIdType::Ed25519).unwrap().as_bytes(),
2848            &[14; 32]
2849        );
2850        let r = netdir.by_ids(&pair_14_99);
2851        assert!(r.is_none());
2852
2853        assert_eq!(
2854            netdir.id_pair_listed(&[13; 32].into(), &[13; 20].into()),
2855            None
2856        );
2857        assert_eq!(
2858            netdir.id_pair_listed(&[15; 32].into(), &[15; 20].into()),
2859            Some(true)
2860        );
2861        assert_eq!(
2862            netdir.id_pair_listed(&[15; 32].into(), &[99; 20].into()),
2863            Some(false)
2864        );
2865    }
2866
2867    #[test]
2868    #[cfg(feature = "hs-common")]
2869    fn test_by_ids_detailed() {
2870        // Make a netdir that omits the microdescriptor for 0xDDDDDD...
2871        let netdir = construct_custom_netdir(|pos, nb, _| {
2872            nb.omit_md = pos == 13;
2873        })
2874        .unwrap();
2875
2876        let netdir = netdir.unwrap_if_sufficient().unwrap();
2877
2878        let id13_13 = RelayIds::builder()
2879            .ed_identity([13; 32].into())
2880            .rsa_identity([13; 20].into())
2881            .build()
2882            .unwrap();
2883        let id15_15 = RelayIds::builder()
2884            .ed_identity([15; 32].into())
2885            .rsa_identity([15; 20].into())
2886            .build()
2887            .unwrap();
2888        let id15_99 = RelayIds::builder()
2889            .ed_identity([15; 32].into())
2890            .rsa_identity([99; 20].into())
2891            .build()
2892            .unwrap();
2893        let id99_15 = RelayIds::builder()
2894            .ed_identity([99; 32].into())
2895            .rsa_identity([15; 20].into())
2896            .build()
2897            .unwrap();
2898        let id99_99 = RelayIds::builder()
2899            .ed_identity([99; 32].into())
2900            .rsa_identity([99; 20].into())
2901            .build()
2902            .unwrap();
2903        let id15_xx = RelayIds::builder()
2904            .ed_identity([15; 32].into())
2905            .build()
2906            .unwrap();
2907        let idxx_15 = RelayIds::builder()
2908            .rsa_identity([15; 20].into())
2909            .build()
2910            .unwrap();
2911
2912        assert!(matches!(netdir.by_ids_detailed(&id13_13), Ok(None)));
2913        assert!(matches!(netdir.by_ids_detailed(&id15_15), Ok(Some(_))));
2914        assert!(matches!(
2915            netdir.by_ids_detailed(&id15_99),
2916            Err(RelayLookupError::Impossible)
2917        ));
2918        assert!(matches!(
2919            netdir.by_ids_detailed(&id99_15),
2920            Err(RelayLookupError::Impossible)
2921        ));
2922        assert!(matches!(netdir.by_ids_detailed(&id99_99), Ok(None)));
2923        assert!(matches!(netdir.by_ids_detailed(&id15_xx), Ok(Some(_))));
2924        assert!(matches!(netdir.by_ids_detailed(&idxx_15), Ok(Some(_))));
2925    }
2926
2927    #[test]
2928    fn weight_type() {
2929        let r0 = RelayWeight(0);
2930        let r100 = RelayWeight(100);
2931        let r200 = RelayWeight(200);
2932        let r300 = RelayWeight(300);
2933        assert_eq!(r100 + r200, r300);
2934        assert_eq!(r100.checked_div(r200), Some(0.5));
2935        assert!(r100.checked_div(r0).is_none());
2936        assert_eq!(r200.ratio(0.5), Some(r100));
2937        assert!(r200.ratio(-1.0).is_none());
2938    }
2939
2940    #[test]
2941    fn weight_accessors() {
2942        // Make a netdir that omits the microdescriptor for 0xDDDDDD...
2943        let netdir = construct_netdir().unwrap_if_sufficient().unwrap();
2944
2945        let g_total = netdir.total_weight(WeightRole::Guard, |r| r.rs.is_flagged_guard());
2946        // This is just the total guard weight, since all our Wxy = 1.
2947        assert_eq!(g_total, RelayWeight(110_000));
2948
2949        let g_total = netdir.total_weight(WeightRole::Guard, |_| false);
2950        assert_eq!(g_total, RelayWeight(0));
2951
2952        let relay = netdir.by_id(&Ed25519Identity::from([35; 32])).unwrap();
2953        assert!(relay.rs.is_flagged_guard());
2954        let w = netdir.relay_weight(&relay, WeightRole::Guard);
2955        assert_eq!(w, RelayWeight(6_000));
2956
2957        let w = netdir
2958            .weight_by_rsa_id(&[33; 20].into(), WeightRole::Guard)
2959            .unwrap();
2960        assert_eq!(w, RelayWeight(4_000));
2961
2962        assert!(
2963            netdir
2964                .weight_by_rsa_id(&[99; 20].into(), WeightRole::Guard)
2965                .is_none()
2966        );
2967    }
2968
2969    #[test]
2970    fn family_list() {
2971        let netdir = construct_custom_netdir(|pos, n, _| {
2972            if pos == 0x0a {
2973                n.md.family(
2974                    "$0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B \
2975                     $0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C \
2976                     $0D0D0D0D0D0D0D0D0D0D0D0D0D0D0D0D0D0D0D0D"
2977                        .parse()
2978                        .unwrap(),
2979                );
2980            } else if pos == 0x0c {
2981                n.md.family("$0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A".parse().unwrap());
2982            }
2983        })
2984        .unwrap()
2985        .unwrap_if_sufficient()
2986        .unwrap();
2987
2988        // In the testing netdir, adjacent members are in the same family by default...
2989        let r0 = netdir.by_id(&Ed25519Identity::from([0; 32])).unwrap();
2990        let family: Vec<_> = netdir.known_family_members(&r0).collect();
2991        assert_eq!(family.len(), 1);
2992        assert_eq!(family[0].id(), &Ed25519Identity::from([1; 32]));
2993
2994        // But we've made this relay claim membership with several others.
2995        let r10 = netdir.by_id(&Ed25519Identity::from([10; 32])).unwrap();
2996        let family: HashSet<_> = netdir.known_family_members(&r10).map(|r| *r.id()).collect();
2997        assert_eq!(family.len(), 2);
2998        assert!(family.contains(&Ed25519Identity::from([11; 32])));
2999        assert!(family.contains(&Ed25519Identity::from([12; 32])));
3000        // Note that 13 doesn't get put in, even though it's listed, since it doesn't claim
3001        //  membership with 10.
3002    }
3003    #[test]
3004    #[cfg(feature = "geoip")]
3005    fn relay_has_country_code() {
3006        let src_v6 = r#"
3007        fe80:dead:beef::,fe80:dead:ffff::,US
3008        fe80:feed:eeee::1,fe80:feed:eeee::1,AT
3009        fe80:feed:eeee::2,fe80:feed:ffff::,DE
3010        "#;
3011        let db = GeoipDb::new_from_legacy_format("", src_v6, true).unwrap();
3012
3013        let netdir = construct_custom_netdir_with_geoip(
3014            |pos, n, _| {
3015                if pos == 0x01 {
3016                    n.rs.add_or_port("[fe80:dead:beef::1]:42".parse().unwrap());
3017                }
3018                if pos == 0x02 {
3019                    n.rs.add_or_port("[fe80:feed:eeee::1]:42".parse().unwrap());
3020                    n.rs.add_or_port("[fe80:feed:eeee::2]:42".parse().unwrap());
3021                }
3022                if pos == 0x03 {
3023                    n.rs.add_or_port("[fe80:dead:beef::1]:42".parse().unwrap());
3024                    n.rs.add_or_port("[fe80:dead:beef::2]:42".parse().unwrap());
3025                }
3026            },
3027            &db,
3028        )
3029        .unwrap()
3030        .unwrap_if_sufficient()
3031        .unwrap();
3032
3033        // No GeoIP data available -> None
3034        let r0 = netdir.by_id(&Ed25519Identity::from([0; 32])).unwrap();
3035        assert_eq!(r0.cc, None);
3036
3037        // Exactly one match -> Some
3038        let r1 = netdir.by_id(&Ed25519Identity::from([1; 32])).unwrap();
3039        assert_eq!(r1.cc.as_ref().map(|x| x.as_ref()), Some("US"));
3040
3041        // Conflicting matches -> None
3042        let r2 = netdir.by_id(&Ed25519Identity::from([2; 32])).unwrap();
3043        assert_eq!(r2.cc, None);
3044
3045        // Multiple agreeing matches -> Some
3046        let r3 = netdir.by_id(&Ed25519Identity::from([3; 32])).unwrap();
3047        assert_eq!(r3.cc.as_ref().map(|x| x.as_ref()), Some("US"));
3048    }
3049
3050    #[test]
3051    #[cfg(feature = "hs-common")]
3052    #[allow(deprecated)]
3053    fn hs_dirs_selection() {
3054        use tor_basic_utils::test_rng::testing_rng;
3055
3056        const HSDIR_SPREAD_STORE: i32 = 6;
3057        const HSDIR_SPREAD_FETCH: i32 = 2;
3058        const PARAMS: [(&str, i32); 2] = [
3059            ("hsdir_spread_store", HSDIR_SPREAD_STORE),
3060            ("hsdir_spread_fetch", HSDIR_SPREAD_FETCH),
3061        ];
3062
3063        let netdir: Arc<NetDir> =
3064            crate::testnet::construct_custom_netdir_with_params(|_, _, _| {}, PARAMS, None)
3065                .unwrap()
3066                .unwrap_if_sufficient()
3067                .unwrap()
3068                .into();
3069        let hsid = dummy_hs_blind_id();
3070
3071        const OP_RELAY_COUNT: &[(HsDirOp, usize)] = &[
3072            // We can't upload to (hsdir_n_replicas * hsdir_spread_store) = 12, relays because there
3073            // are only 10 relays with the HsDir flag in the consensus.
3074            #[cfg(feature = "hs-service")]
3075            (HsDirOp::Upload, 10),
3076            (HsDirOp::Download, 4),
3077        ];
3078
3079        for (op, relay_count) in OP_RELAY_COUNT {
3080            let relays = netdir.hs_dirs(&hsid, *op, &mut testing_rng());
3081
3082            assert_eq!(relays.len(), *relay_count);
3083
3084            // There should be no duplicates (the filtering function passed to
3085            // HsDirRing::ring_items_at() ensures the relays that are already in use for
3086            // lower-numbered replicas aren't considered a second time for a higher-numbered
3087            // replica).
3088            let unique = relays
3089                .iter()
3090                .map(|relay| relay.ed_identity())
3091                .collect::<HashSet<_>>();
3092            assert_eq!(unique.len(), relays.len());
3093        }
3094
3095        // TODO: come up with a test that checks that HsDirRing::ring_items_at() skips over the
3096        // expected relays.
3097        //
3098        // For example, let's say we have the following hsdir ring:
3099        //
3100        //         A  -  B
3101        //        /       \
3102        //       F         C
3103        //        \       /
3104        //         E  -  D
3105        //
3106        // Let's also assume that:
3107        //
3108        //   * hsdir_spread_store = 3
3109        //   * the ordering of the relays on the ring is [A, B, C, D, E, F]
3110        //
3111        // If we use relays [A, B, C] for replica 1, and hs_index(2) = E, then replica 2 _must_ get
3112        // relays [E, F, D]. We should have a test that checks this.
3113    }
3114
3115    #[test]
3116    fn zero_weights() {
3117        // Here we check the behavior of IndexedRandom::choose_weighted
3118        // in the presence of items whose weight is 0.
3119        //
3120        // We think that the behavior is:
3121        //   - If all items have weight 0, choose_weighted returns an error.
3122        //   - If any items have non-zero weight, one of them will be returned.
3123        let items = vec![1, 2, 3];
3124        let mut rng = testing_rng();
3125
3126        let a = items.choose_weighted(&mut rng, |_| 0);
3127        assert!(matches!(a, Err(WeightError::InsufficientNonZero)));
3128
3129        let only_one = |n: &i32| if *n == 1 { 1 } else { 0 };
3130        for _ in 0..100 {
3131            let a = items.choose_weighted(&mut rng, only_one);
3132            assert_eq!(a.unwrap(), &1);
3133        }
3134    }
3135}