1
#![cfg_attr(docsrs, feature(doc_auto_cfg, doc_cfg))]
2
#![doc = include_str!("../README.md")]
3
// @@ begin lint list maintained by maint/add_warning @@
4
#![cfg_attr(not(ci_arti_stable), allow(renamed_and_removed_lints))]
5
#![cfg_attr(not(ci_arti_nightly), allow(unknown_lints))]
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
#![warn(clippy::cognitive_complexity)]
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
#![deny(clippy::print_stderr)]
28
#![deny(clippy::print_stdout)]
29
#![warn(clippy::rc_buffer)]
30
#![deny(clippy::ref_option_ref)]
31
#![warn(clippy::semicolon_if_nothing_returned)]
32
#![warn(clippy::trait_duplication_in_bounds)]
33
#![deny(clippy::unnecessary_wraps)]
34
#![warn(clippy::unseparated_literal_suffix)]
35
#![deny(clippy::unwrap_used)]
36
#![allow(clippy::let_unit_value)] // This can reasonably be done for explicitness
37
#![allow(clippy::uninlined_format_args)]
38
#![allow(clippy::significant_drop_in_scrutinee)] // arti/-/merge_requests/588/#note_2812945
39
#![allow(clippy::result_large_err)] // temporary workaround for arti#587
40
#![allow(clippy::needless_raw_string_hashes)] // complained-about code is fine, often best
41
//! <!-- @@ end lint list maintained by maint/add_warning @@ -->
42

            
43
mod err;
44
#[cfg(feature = "hs-common")]
45
mod hsdir_params;
46
#[cfg(feature = "hs-common")]
47
mod hsdir_ring;
48
pub mod params;
49
mod weight;
50

            
51
#[cfg(any(test, feature = "testing"))]
52
pub mod testnet;
53
#[cfg(feature = "testing")]
54
pub mod testprovider;
55

            
56
#[cfg(feature = "hs-service")]
57
use itertools::chain;
58
use static_assertions::const_assert;
59
use tor_linkspec::{
60
    ChanTarget, DirectChanMethodsHelper, HasAddrs, HasRelayIds, RelayIdRef, RelayIdType,
61
};
62
use tor_llcrypto as ll;
63
use tor_llcrypto::pk::{ed25519::Ed25519Identity, rsa::RsaIdentity};
64
use tor_netdoc::doc::microdesc::{MdDigest, Microdesc};
65
use tor_netdoc::doc::netstatus::{self, MdConsensus, MdConsensusRouterStatus, RouterStatus};
66
use tor_netdoc::types::policy::PortPolicy;
67
#[cfg(feature = "hs-common")]
68
use {hsdir_ring::HsDirRing, std::iter};
69

            
70
use derive_more::{From, Into};
71
use futures::stream::BoxStream;
72
use num_enum::{IntoPrimitive, TryFromPrimitive};
73
use rand::seq::SliceRandom;
74
use serde::Deserialize;
75
use std::collections::HashMap;
76
use std::net::IpAddr;
77
use std::ops::Deref;
78
use std::sync::Arc;
79
use strum::{EnumCount, EnumIter};
80
use tracing::warn;
81
use typed_index_collections::{TiSlice, TiVec};
82

            
83
#[cfg(feature = "hs-common")]
84
use {
85
    itertools::Itertools,
86
    std::collections::HashSet,
87
    tor_error::{internal, Bug},
88
    tor_hscrypto::{pk::HsBlindId, time::TimePeriod},
89
};
90

            
91
pub use err::Error;
92
pub use weight::WeightRole;
93
/// A Result using the Error type from the tor-netdir crate
94
pub type Result<T> = std::result::Result<T, Error>;
95

            
96
#[cfg(feature = "hs-common")]
97
pub use err::OnionDirLookupError;
98

            
99
use params::NetParameters;
100
#[cfg(feature = "geoip")]
101
use tor_geoip::{CountryCode, GeoipDb, HasCountryCode};
102

            
103
#[cfg(feature = "hs-common")]
104
#[cfg_attr(docsrs, doc(cfg(feature = "hs-common")))]
105
pub use hsdir_params::HsDirParams;
106

            
107
/// Index into the consensus relays
108
///
109
/// This is an index into the list of relays returned by
110
/// [`.c_relays()`](ConsensusRelays::c_relays)
111
/// (on the corresponding consensus or netdir).
112
///
113
/// This is just a `usize` inside, but using a newtype prevents getting a relay index
114
/// confused with other kinds of slice indices or counts.
115
///
116
/// If you are in a part of the code which needs to work with multiple consensuses,
117
/// the typechecking cannot tell if you try to index into the wrong consensus.
118
30043011
#[derive(Debug, From, Into, Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Hash)]
119
pub(crate) struct RouterStatusIdx(usize);
120

            
121
/// Extension trait to provide index-type-safe `.c_relays()` method
122
//
123
// TODO: Really it would be better to have MdConsensns::relays() return TiSlice,
124
// but that would be an API break there.
125
pub(crate) trait ConsensusRelays {
126
    /// Obtain the list of relays in the consensus
127
    //
128
    fn c_relays(&self) -> &TiSlice<RouterStatusIdx, MdConsensusRouterStatus>;
129
}
130
impl ConsensusRelays for MdConsensus {
131
15440267
    fn c_relays(&self) -> &TiSlice<RouterStatusIdx, MdConsensusRouterStatus> {
132
15440267
        TiSlice::from_ref(MdConsensus::relays(self))
133
15440267
    }
134
}
135
impl ConsensusRelays for NetDir {
136
15407339
    fn c_relays(&self) -> &TiSlice<RouterStatusIdx, MdConsensusRouterStatus> {
137
15407339
        self.consensus.c_relays()
138
15407339
    }
139
}
140

            
141
/// Configuration for determining when two relays have addresses "too close" in
142
/// the network.
143
///
144
/// Used by [`Relay::in_same_subnet()`].
145
#[derive(Deserialize, Debug, Clone, Copy)]
146
#[serde(deny_unknown_fields)]
147
pub struct SubnetConfig {
148
    /// Consider IPv4 nodes in the same /x to be the same family.
149
    ///
150
    /// If this value is 0, all nodes with IPv4 addresses will be in the
151
    /// same family.  If this value is above 32, then no nodes will be
152
    /// placed im the same family based on their IPv4 addresses.
153
    subnets_family_v4: u8,
154
    /// Consider IPv6 nodes in the same /x to be the same family.
155
    ///
156
    /// If this value is 0, all nodes with IPv6 addresses will be in the
157
    /// same family.  If this value is above 128, then no nodes will be
158
    /// placed im the same family based on their IPv6 addresses.
159
    subnets_family_v6: u8,
160
}
161

            
162
impl Default for SubnetConfig {
163
114112
    fn default() -> Self {
164
114112
        Self::new(16, 32)
165
114112
    }
166
}
167

            
168
impl SubnetConfig {
169
    /// Construct a new SubnetConfig from a pair of bit prefix lengths.
170
    ///
171
    /// The values are clamped to the appropriate ranges if they are
172
    /// out-of-bounds.
173
228632
    pub fn new(subnets_family_v4: u8, subnets_family_v6: u8) -> Self {
174
228632
        Self {
175
228632
            subnets_family_v4,
176
228632
            subnets_family_v6,
177
228632
        }
178
228632
    }
179

            
180
    /// Return true if the two addresses in the same subnet, according to this
181
    /// configuration.
182
11668212
    pub fn addrs_in_same_subnet(&self, a: &IpAddr, b: &IpAddr) -> bool {
183
11668212
        match (a, b) {
184
11668186
            (IpAddr::V4(a), IpAddr::V4(b)) => {
185
11668186
                let bits = self.subnets_family_v4;
186
11668186
                if bits > 32 {
187
806
                    return false;
188
11667380
                }
189
11667380
                let a = u32::from_be_bytes(a.octets());
190
11667380
                let b = u32::from_be_bytes(b.octets());
191
11667380
                (a >> (32 - bits)) == (b >> (32 - bits))
192
            }
193
14
            (IpAddr::V6(a), IpAddr::V6(b)) => {
194
14
                let bits = self.subnets_family_v6;
195
14
                if bits > 128 {
196
4
                    return false;
197
10
                }
198
10
                let a = u128::from_be_bytes(a.octets());
199
10
                let b = u128::from_be_bytes(b.octets());
200
10
                (a >> (128 - bits)) == (b >> (128 - bits))
201
            }
202
12
            _ => false,
203
        }
204
11668212
    }
205

            
206
    /// Return true if any of the addresses in `a` shares a subnet with any of
207
    /// the addresses in `b`, according to this configuration.
208
631408
    pub fn any_addrs_in_same_subnet<T, U>(&self, a: &T, b: &U) -> bool
209
631408
    where
210
631408
        T: tor_linkspec::HasAddrs,
211
631408
        U: tor_linkspec::HasAddrs,
212
631408
    {
213
631414
        a.addrs().iter().any(|aa| {
214
631414
            b.addrs()
215
631414
                .iter()
216
631422
                .any(|bb| self.addrs_in_same_subnet(&aa.ip(), &bb.ip()))
217
631414
        })
218
631408
    }
219
}
220

            
221
/// An opaque type representing the weight with which a relay or set of
222
/// relays will be selected for a given role.
223
///
224
/// Most users should ignore this type, and just use pick_relay instead.
225
#[derive(
226
    Copy,
227
    Clone,
228
    Debug,
229
10052
    derive_more::Add,
230
1380
    derive_more::Sum,
231
16276
    derive_more::AddAssign,
232
    Eq,
233
12
    PartialEq,
234
    Ord,
235
3148
    PartialOrd,
236
)]
237
pub struct RelayWeight(u64);
238

            
239
impl RelayWeight {
240
    /// Try to divide this weight by `rhs`.
241
    ///
242
    /// Return a ratio on success, or None on division-by-zero.
243
1193
    pub fn checked_div(&self, rhs: RelayWeight) -> Option<f64> {
244
1193
        if rhs.0 == 0 {
245
2
            None
246
        } else {
247
1191
            Some((self.0 as f64) / (rhs.0 as f64))
248
        }
249
1193
    }
250

            
251
    /// Compute a ratio `frac` of this weight.
252
    ///
253
    /// Return None if frac is less than zero, since negative weights
254
    /// are impossible.
255
1938
    pub fn ratio(&self, frac: f64) -> Option<RelayWeight> {
256
1938
        let product = (self.0 as f64) * frac;
257
1938
        if product >= 0.0 && product.is_finite() {
258
1936
            Some(RelayWeight(product as u64))
259
        } else {
260
2
            None
261
        }
262
1938
    }
263
}
264

            
265
impl From<u64> for RelayWeight {
266
2378
    fn from(val: u64) -> Self {
267
2378
        RelayWeight(val)
268
2378
    }
269
}
270

            
271
/// An operation for which we might be requesting a hidden service directory.
272
#[derive(Copy, Clone, Debug, PartialEq)]
273
// TODO: make this pub(crate) once NetDir::hs_dirs is removed
274
#[non_exhaustive]
275
pub enum HsDirOp {
276
    /// Uploading an onion service descriptor.
277
    #[cfg(feature = "hs-service")]
278
    Upload,
279
    /// Downloading an onion service descriptor.
280
    Download,
281
}
282

            
283
/// A view of the Tor directory, suitable for use in building circuits.
284
///
285
/// Abstractly, a [`NetDir`] is a set of usable public [`Relay`]s, each of which
286
/// has its own properties, identity, and correct weighted probability for use
287
/// under different circumstances.
288
///
289
/// A [`NetDir`] is constructed by making a [`PartialNetDir`] from a consensus
290
/// document, and then adding enough microdescriptors to that `PartialNetDir` so
291
/// that it can be used to build paths. (Thus, if you have a NetDir, it is
292
/// definitely adequate to build paths.)
293
///
294
/// # "Usable" relays
295
///
296
/// Many methods on NetDir are defined in terms of <a name="usable">"Usable"</a> relays.  Unless
297
/// otherwise stated, a relay is "usable" if it is listed in the consensus,
298
/// if we have full directory information for that relay (including a
299
/// microdescriptor), and if that relay does not have any flags indicating that
300
/// we should never use it. (Currently, `NoEdConsensus` is the only such flag.)
301
///
302
/// # Limitations
303
///
304
/// The current NetDir implementation assumes fairly strongly that every relay
305
/// has an Ed25519 identity and an RSA identity, that the consensus is indexed
306
/// by RSA identities, and that the Ed25519 identities are stored in
307
/// microdescriptors.
308
///
309
/// If these assumptions someday change, then we'll have to revise the
310
/// implementation.
311
56
#[derive(Debug, Clone)]
312
pub struct NetDir {
313
    /// A microdescriptor consensus that lists the members of the network,
314
    /// and maps each one to a 'microdescriptor' that has more information
315
    /// about it
316
    consensus: Arc<MdConsensus>,
317
    /// A map from keys to integer values, distributed in the consensus,
318
    /// and clamped to certain defaults.
319
    params: NetParameters,
320
    /// Map from routerstatus index, to that routerstatus's microdescriptor (if we have one.)
321
    mds: TiVec<RouterStatusIdx, Option<Arc<Microdesc>>>,
322
    /// Map from SHA256 of _missing_ microdescriptors to the index of their
323
    /// corresponding routerstatus.
324
    rsidx_by_missing: HashMap<MdDigest, RouterStatusIdx>,
325
    /// Map from ed25519 identity to index of the routerstatus.
326
    ///
327
    /// Note that we don't know the ed25519 identity of a relay until
328
    /// we get the microdescriptor for it, so this won't be filled in
329
    /// until we get the microdescriptors.
330
    ///
331
    /// # Implementation note
332
    ///
333
    /// For this field, and for `rsidx_by_rsa`,
334
    /// it might be cool to have references instead.
335
    /// But that would make this into a self-referential structure,
336
    /// which isn't possible in safe rust.
337
    rsidx_by_ed: HashMap<Ed25519Identity, RouterStatusIdx>,
338
    /// Map from RSA identity to index of the routerstatus.
339
    ///
340
    /// This is constructed at the same time as the NetDir object, so it
341
    /// can be immutable.
342
    rsidx_by_rsa: Arc<HashMap<RsaIdentity, RouterStatusIdx>>,
343

            
344
    /// Hash ring(s) describing the onion service directory.
345
    ///
346
    /// This is empty in a PartialNetDir, and is filled in before the NetDir is
347
    /// built.
348
    //
349
    // TODO hs: It is ugly to have this exist in a partially constructed state
350
    // in a PartialNetDir.
351
    // Ideally, a PartialNetDir would contain only an HsDirs<HsDirParams>,
352
    // or perhaps nothing at all, here.
353
    #[cfg(feature = "hs-common")]
354
    hsdir_rings: Arc<HsDirs<HsDirRing>>,
355

            
356
    /// Weight values to apply to a given relay when deciding how frequently
357
    /// to choose it for a given role.
358
    weights: weight::WeightSet,
359

            
360
    #[cfg(feature = "geoip")]
361
    /// Country codes for each router in our consensus.
362
    ///
363
    /// This is indexed by the `RouterStatusIdx` (i.e. a router idx of zero has
364
    /// the country code at position zero in this array).
365
    country_codes: Vec<Option<CountryCode>>,
366
}
367

            
368
/// Collection of hidden service directories (or parameters for them)
369
///
370
/// In [`NetDir`] this is used to store the actual hash rings.
371
/// (But, in a NetDir in a [`PartialNetDir`], it contains [`HsDirRing`]s
372
/// where only the `params` are populated, and the `ring` is empty.)
373
///
374
/// This same generic type is used as the return type from
375
/// [`HsDirParams::compute`](HsDirParams::compute),
376
/// where it contains the *parameters* for the primary and secondary rings.
377
#[derive(Debug, Clone)]
378
#[cfg(feature = "hs-common")]
379
pub(crate) struct HsDirs<D> {
380
    /// The current ring
381
    ///
382
    /// It corresponds to the time period containing the `valid-after` time in
383
    /// the consensus. Its SRV is whatever SRV was most current at the time when
384
    /// that time period began.
385
    ///
386
    /// This is the hash ring that we should use whenever we are fetching an
387
    /// onion service descriptor.
388
    current: D,
389

            
390
    /// Secondary rings (based on the parameters for the previous and next time periods)
391
    ///
392
    /// Onion services upload to positions on these ring as well, based on how
393
    /// far into the current time period this directory is, so that
394
    /// not-synchronized clients can still find their descriptor.
395
    ///
396
    /// Note that with the current (2023) network parameters, with
397
    /// `hsdir_interval = SRV lifetime = 24 hours` at most one of these
398
    /// secondary rings will be active at a time.  We have two here in order
399
    /// to conform with a more flexible regime in proposal 342.
400
    //
401
    // TODO: hs clients never need this; so I've made it not-present for thm.
402
    // But does that risk too much with respect to side channels?
403
    //
404
    // TODO: Perhaps we should refactor this so that it is clear that these
405
    // are immutable?  On the other hand, the documentation for this type
406
    // declares that it is immutable, so we are likely okay.
407
    //
408
    // TODO: this `Vec` is only ever 0,1,2 elements.
409
    // Maybe it should be an ArrayVec or something.
410
    #[cfg(feature = "hs-service")]
411
    secondary: Vec<D>,
412
}
413

            
414
#[cfg(feature = "hs-common")]
415
impl<D> HsDirs<D> {
416
    /// Convert an `HsDirs<D>` to `HsDirs<D2>` by mapping each contained `D`
417
6472
    pub(crate) fn map<D2>(self, mut f: impl FnMut(D) -> D2) -> HsDirs<D2> {
418
6472
        HsDirs {
419
6472
            current: f(self.current),
420
6472
            #[cfg(feature = "hs-service")]
421
6472
            secondary: self.secondary.into_iter().map(f).collect(),
422
6472
        }
423
6472
    }
424

            
425
    /// Iterate over some of the contained hsdirs, according to `secondary`
426
    ///
427
    /// The current ring is always included.
428
    /// Secondary rings are included iff `secondary` and the `hs-service` feature is enabled.
429
448
    fn iter_filter_secondary(&self, secondary: bool) -> impl Iterator<Item = &D> {
430
448
        let i = iter::once(&self.current);
431
448

            
432
448
        // With "hs-service" disabled, there are no secondary rings,
433
448
        // so we don't care.
434
448
        let _ = secondary;
435
448

            
436
448
        #[cfg(feature = "hs-service")]
437
448
        let i = chain!(i, self.secondary.iter().filter(move |_| secondary));
438
448

            
439
448
        i
440
448
    }
441

            
442
    /// Iterate over all the contained hsdirs
443
444
    pub(crate) fn iter(&self) -> impl Iterator<Item = &D> {
444
444
        self.iter_filter_secondary(true)
445
444
    }
446

            
447
    /// Iterate over the hsdirs relevant for `op`
448
4
    pub(crate) fn iter_for_op(&self, op: HsDirOp) -> impl Iterator<Item = &D> {
449
4
        self.iter_filter_secondary(match op {
450
            #[cfg(feature = "hs-service")]
451
2
            HsDirOp::Upload => true,
452
2
            HsDirOp::Download => false,
453
        })
454
4
    }
455
}
456

            
457
/// An event that a [`NetDirProvider`] can broadcast to indicate that a change in
458
/// the status of its directory.
459
#[derive(
460
32912
    Debug, Clone, Copy, PartialEq, Eq, EnumIter, EnumCount, IntoPrimitive, TryFromPrimitive,
461
)]
462
#[non_exhaustive]
463
#[repr(u16)]
464
pub enum DirEvent {
465
    /// A new consensus has been received, and has enough information to be
466
    /// used.
467
    ///
468
    /// This event is also broadcast when a new set of consensus parameters is
469
    /// available, even if that set of parameters comes from a configuration
470
    /// change rather than from the latest consensus.
471
    NewConsensus,
472

            
473
    /// New descriptors have been received for the current consensus.
474
    ///
475
    /// (This event is _not_ broadcast when receiving new descriptors for a
476
    /// consensus which is not yet ready to replace the current consensus.)
477
    NewDescriptors,
478
}
479

            
480
/// How "timely" must a network directory be?
481
///
482
/// This enum is used as an argument when requesting a [`NetDir`] object from
483
/// [`NetDirProvider`] and other APIs, to specify how recent the information
484
/// must be in order to be useful.
485
#[derive(Copy, Clone, Eq, PartialEq, Debug)]
486
#[allow(clippy::exhaustive_enums)]
487
pub enum Timeliness {
488
    /// The network directory must be strictly timely.
489
    ///
490
    /// That is, it must be based on a consensus that valid right now, with no
491
    /// tolerance for skew or consensus problems.
492
    ///
493
    /// Avoid using this option if you could use [`Timeliness::Timely`] instead.
494
    Strict,
495
    /// The network directory must be roughly timely.
496
    ///
497
    /// This is, it must be be based on a consensus that is not _too_ far in the
498
    /// future, and not _too_ far in the past.
499
    ///
500
    /// (The tolerances for "too far" will depend on configuration.)
501
    ///
502
    /// This is almost always the option that you want to use.
503
    Timely,
504
    /// Any network directory is permissible, regardless of how untimely.
505
    ///
506
    /// Avoid using this option if you could use [`Timeliness::Timely`] instead.
507
    Unchecked,
508
}
509

            
510
/// An object that can provide [`NetDir`]s, as well as inform consumers when
511
/// they might have changed.
512
///
513
/// It is the responsibility of the implementor of `NetDirProvider`
514
/// to try to obtain an up-to-date `NetDir`,
515
/// and continuously to maintain and update it.
516
///
517
/// In usual configurations, Arti uses `tor_dirmgr::DirMgr`
518
/// as its `NetDirProvider`.
519
pub trait NetDirProvider: UpcastArcNetDirProvider + Send + Sync {
520
    /// Return a network directory that's live according to the provided
521
    /// `timeliness`.
522
    fn netdir(&self, timeliness: Timeliness) -> Result<Arc<NetDir>>;
523

            
524
    /// Return a reasonable netdir for general usage.
525
    ///
526
    /// This is an alias for
527
    /// [`NetDirProvider::netdir`]`(`[`Timeliness::Timely`]`)`.
528
236
    fn timely_netdir(&self) -> Result<Arc<NetDir>> {
529
236
        self.netdir(Timeliness::Timely)
530
236
    }
531

            
532
    /// Return a new asynchronous stream that will receive notification
533
    /// whenever the consensus has changed.
534
    ///
535
    /// Multiple events may be batched up into a single item: each time
536
    /// this stream yields an event, all you can assume is that the event has
537
    /// occurred at least once.
538
    fn events(&self) -> BoxStream<'static, DirEvent>;
539

            
540
    /// Return the latest network parameters.
541
    ///
542
    /// If we have no directory, return a reasonable set of defaults.
543
    fn params(&self) -> Arc<dyn AsRef<NetParameters>>;
544
}
545

            
546
impl<T> NetDirProvider for Arc<T>
547
where
548
    T: NetDirProvider,
549
{
550
104
    fn netdir(&self, timeliness: Timeliness) -> Result<Arc<NetDir>> {
551
104
        self.deref().netdir(timeliness)
552
104
    }
553

            
554
96
    fn timely_netdir(&self) -> Result<Arc<NetDir>> {
555
96
        self.deref().timely_netdir()
556
96
    }
557

            
558
91
    fn events(&self) -> BoxStream<'static, DirEvent> {
559
91
        self.deref().events()
560
91
    }
561

            
562
20
    fn params(&self) -> Arc<dyn AsRef<NetParameters>> {
563
20
        self.deref().params()
564
20
    }
565
}
566

            
567
/// Helper trait: allows any `Arc<X>` to be upcast to a `Arc<dyn
568
/// NetDirProvider>` if X is an implementation or supertrait of NetDirProvider.
569
///
570
/// This trait exists to work around a limitation in rust: when trait upcasting
571
/// coercion is stable, this will be unnecessary.
572
///
573
/// The Rust tracking issue is <https://github.com/rust-lang/rust/issues/65991>.
574
pub trait UpcastArcNetDirProvider {
575
    /// Return a view of this object as an `Arc<dyn NetDirProvider>`
576
    fn upcast_arc<'a>(self: Arc<Self>) -> Arc<dyn NetDirProvider + 'a>
577
    where
578
        Self: 'a;
579
}
580

            
581
impl<T> UpcastArcNetDirProvider for T
582
where
583
    T: NetDirProvider + Sized,
584
{
585
52
    fn upcast_arc<'a>(self: Arc<Self>) -> Arc<dyn NetDirProvider + 'a>
586
52
    where
587
52
        Self: 'a,
588
52
    {
589
52
        self
590
52
    }
591
}
592

            
593
impl AsRef<NetParameters> for NetDir {
594
724
    fn as_ref(&self) -> &NetParameters {
595
724
        self.params()
596
724
    }
597
}
598

            
599
/// A partially build NetDir -- it can't be unwrapped until it has
600
/// enough information to build safe paths.
601
#[derive(Debug, Clone)]
602
pub struct PartialNetDir {
603
    /// The netdir that's under construction.
604
    netdir: NetDir,
605

            
606
    /// The previous netdir, if we had one
607
    ///
608
    /// Used as a cache, so we can reuse information
609
    #[cfg(feature = "hs-common")]
610
    prev_netdir: Option<Arc<NetDir>>,
611
}
612

            
613
/// A view of a relay on the Tor network, suitable for building circuits.
614
// TODO: This should probably be a more specific struct, with a trait
615
// that implements it.
616
47650
#[derive(Clone)]
617
pub struct Relay<'a> {
618
    /// A router descriptor for this relay.
619
    rs: &'a netstatus::MdConsensusRouterStatus,
620
    /// A microdescriptor for this relay.
621
    md: &'a Microdesc,
622
    /// The country code this relay is in, if we know one.
623
    #[cfg(feature = "geoip")]
624
    cc: Option<CountryCode>,
625
}
626

            
627
/// A relay that we haven't checked for validity or usability in
628
/// routing.
629
#[derive(Debug)]
630
pub struct UncheckedRelay<'a> {
631
    /// A router descriptor for this relay.
632
    rs: &'a netstatus::MdConsensusRouterStatus,
633
    /// A microdescriptor for this relay, if there is one.
634
    md: Option<&'a Microdesc>,
635
    /// The country code this relay is in, if we know one.
636
    #[cfg(feature = "geoip")]
637
    cc: Option<CountryCode>,
638
}
639

            
640
/// A partial or full network directory that we can download
641
/// microdescriptors for.
642
pub trait MdReceiver {
643
    /// Return an iterator over the digests for all of the microdescriptors
644
    /// that this netdir is missing.
645
    fn missing_microdescs(&self) -> Box<dyn Iterator<Item = &MdDigest> + '_>;
646
    /// Add a microdescriptor to this netdir, if it was wanted.
647
    ///
648
    /// Return true if it was indeed wanted.
649
    fn add_microdesc(&mut self, md: Microdesc) -> bool;
650
    /// Return the number of missing microdescriptors.
651
    fn n_missing(&self) -> usize;
652
}
653

            
654
impl PartialNetDir {
655
    /// Create a new PartialNetDir with a given consensus, and no
656
    /// microdescriptors loaded.
657
    ///
658
    /// If `replacement_params` is provided, override network parameters from
659
    /// the consensus with those from `replacement_params`.
660
3144
    pub fn new(
661
3144
        consensus: MdConsensus,
662
3144
        replacement_params: Option<&netstatus::NetParams<i32>>,
663
3144
    ) -> Self {
664
3144
        Self::new_inner(
665
3144
            consensus,
666
3144
            replacement_params,
667
3144
            #[cfg(feature = "geoip")]
668
3144
            None,
669
3144
        )
670
3144
    }
671

            
672
    /// Create a new PartialNetDir with GeoIP support.
673
    ///
674
    /// This does the same thing as `new()`, except the provided GeoIP database is used to add
675
    /// country codes to relays.
676
    #[cfg(feature = "geoip")]
677
    #[cfg_attr(docsrs, doc(cfg(feature = "geoip")))]
678
134
    pub fn new_with_geoip(
679
134
        consensus: MdConsensus,
680
134
        replacement_params: Option<&netstatus::NetParams<i32>>,
681
134
        geoip_db: &GeoipDb,
682
134
    ) -> Self {
683
134
        Self::new_inner(consensus, replacement_params, Some(geoip_db))
684
134
    }
685

            
686
    /// Implementation of the `new()` functions.
687
3278
    fn new_inner(
688
3278
        consensus: MdConsensus,
689
3278
        replacement_params: Option<&netstatus::NetParams<i32>>,
690
3278
        #[cfg(feature = "geoip")] geoip_db: Option<&GeoipDb>,
691
3278
    ) -> Self {
692
3278
        let mut params = NetParameters::default();
693
3278

            
694
3278
        // (We ignore unrecognized options here, since they come from
695
3278
        // the consensus, and we don't expect to recognize everything
696
3278
        // there.)
697
3278
        let _ = params.saturating_update(consensus.params().iter());
698

            
699
        // Now see if the user has any parameters to override.
700
        // (We have to do this now, or else changes won't be reflected in our
701
        // weights.)
702
3278
        if let Some(replacement) = replacement_params {
703
3266
            for u in params.saturating_update(replacement.iter()) {
704
2
                warn!("Unrecognized option: override_net_params.{}", u);
705
            }
706
12
        }
707

            
708
        // Compute the weights we'll want to use for these relays.
709
3278
        let weights = weight::WeightSet::from_consensus(&consensus, &params);
710
3278

            
711
3278
        let n_relays = consensus.c_relays().len();
712
3278

            
713
3278
        let rsidx_by_missing = consensus
714
3278
            .c_relays()
715
3278
            .iter_enumerated()
716
126559
            .map(|(rsidx, rs)| (*rs.md_digest(), rsidx))
717
3278
            .collect();
718
3278

            
719
3278
        let rsidx_by_rsa = consensus
720
3278
            .c_relays()
721
3278
            .iter_enumerated()
722
126559
            .map(|(rsidx, rs)| (*rs.rsa_identity(), rsidx))
723
3278
            .collect();
724

            
725
        #[cfg(feature = "geoip")]
726
3278
        let country_codes = if let Some(db) = geoip_db {
727
134
            consensus
728
134
                .c_relays()
729
134
                .iter()
730
771
                .map(|rs| {
731
766
                    let ret = db
732
998
                        .lookup_country_code_multi(rs.addrs().iter().map(|x| x.ip()))
733
766
                        .cloned();
734
766
                    ret
735
771
                })
736
134
                .collect()
737
        } else {
738
3144
            Default::default()
739
        };
740

            
741
        #[cfg(feature = "hs-common")]
742
3278
        let hsdir_rings = Arc::new({
743
3278
            let params = HsDirParams::compute(&consensus, &params).expect("Invalid consensus!");
744
3278
            // TODO: It's a bit ugly to use expect above, but this function does
745
3278
            // not return a Result. On the other hand, the error conditions under which
746
3278
            // HsDirParams::compute can return Err are _very_ narrow and hard to
747
3278
            // hit; see documentation in that function.  As such, we probably
748
3278
            // don't need to have this return a Result.
749
3278

            
750
3278
            params.map(HsDirRing::empty_from_params)
751
3278
        });
752
3278

            
753
3278
        let netdir = NetDir {
754
3278
            consensus: Arc::new(consensus),
755
3278
            params,
756
3278
            mds: vec![None; n_relays].into(),
757
3278
            rsidx_by_missing,
758
3278
            rsidx_by_rsa: Arc::new(rsidx_by_rsa),
759
3278
            rsidx_by_ed: HashMap::with_capacity(n_relays),
760
3278
            #[cfg(feature = "hs-common")]
761
3278
            hsdir_rings,
762
3278
            weights,
763
3278
            #[cfg(feature = "geoip")]
764
3278
            country_codes,
765
3278
        };
766
3278

            
767
3278
        PartialNetDir {
768
3278
            netdir,
769
3278
            #[cfg(feature = "hs-common")]
770
3278
            prev_netdir: None,
771
3278
        }
772
3278
    }
773

            
774
    /// Return the declared lifetime of this PartialNetDir.
775
2
    pub fn lifetime(&self) -> &netstatus::Lifetime {
776
2
        self.netdir.lifetime()
777
2
    }
778

            
779
    /// Record a previous netdir, which can be used for reusing cached information
780
    //
781
    // Fills in as many missing microdescriptors as possible in this
782
    // netdir, using the microdescriptors from the previous netdir.
783
    //
784
    // With HS enabled, stores the netdir for reuse of relay hash ring index values.
785
    #[allow(clippy::needless_pass_by_value)] // prev might, or might not, be stored
786
2
    pub fn fill_from_previous_netdir(&mut self, prev: Arc<NetDir>) {
787
76
        for md in prev.mds.iter().flatten() {
788
76
            self.netdir.add_arc_microdesc(md.clone());
789
76
        }
790

            
791
        #[cfg(feature = "hs-common")]
792
2
        {
793
2
            self.prev_netdir = Some(prev);
794
2
        }
795
2
    }
796

            
797
    /// Compute the hash ring(s) for this NetDir
798
    #[cfg(feature = "hs-common")]
799
3194
    fn compute_rings(&mut self) {
800
3194
        let params = HsDirParams::compute(&self.netdir.consensus, &self.netdir.params)
801
3194
            .expect("Invalid consensus");
802
3194
        // TODO: see TODO by similar expect in new()
803
3194

            
804
3194
        self.netdir.hsdir_rings =
805
3294
            Arc::new(params.map(|params| {
806
3194
                HsDirRing::compute(params, &self.netdir, self.prev_netdir.as_deref())
807
3294
            }));
808
3194
    }
809

            
810
    /// Return true if this are enough information in this directory
811
    /// to build multihop paths.
812
4
    pub fn have_enough_paths(&self) -> bool {
813
4
        self.netdir.have_enough_paths()
814
4
    }
815
    /// If this directory has enough information to build multihop
816
    /// circuits, return it.
817
3388
    pub fn unwrap_if_sufficient(
818
3388
        #[allow(unused_mut)] mut self,
819
3388
    ) -> std::result::Result<NetDir, PartialNetDir> {
820
3388
        if self.netdir.have_enough_paths() {
821
            #[cfg(feature = "hs-common")]
822
3194
            self.compute_rings();
823
3194
            Ok(self.netdir)
824
        } else {
825
194
            Err(self)
826
        }
827
3388
    }
828
}
829

            
830
impl MdReceiver for PartialNetDir {
831
124
    fn missing_microdescs(&self) -> Box<dyn Iterator<Item = &MdDigest> + '_> {
832
124
        self.netdir.missing_microdescs()
833
124
    }
834
125810
    fn add_microdesc(&mut self, md: Microdesc) -> bool {
835
125810
        self.netdir.add_microdesc(md)
836
125810
    }
837
264
    fn n_missing(&self) -> usize {
838
264
        self.netdir.n_missing()
839
264
    }
840
}
841

            
842
impl NetDir {
843
    /// Return the declared lifetime of this NetDir.
844
492
    pub fn lifetime(&self) -> &netstatus::Lifetime {
845
492
        self.consensus.lifetime()
846
492
    }
847

            
848
    /// Add `md` to this NetDir.
849
    ///
850
    /// Return true if we wanted it, and false otherwise.
851
125886
    fn add_arc_microdesc(&mut self, md: Arc<Microdesc>) -> bool {
852
125886
        if let Some(rsidx) = self.rsidx_by_missing.remove(md.digest()) {
853
125812
            assert_eq!(self.c_relays()[rsidx].md_digest(), md.digest());
854

            
855
            // There should never be two approved MDs in the same
856
            // consensus listing the same ID... but if there is,
857
            // we'll let the most recent one win.
858
125812
            self.rsidx_by_ed.insert(*md.ed25519_id(), rsidx);
859
125812

            
860
125812
            // Happy path: we did indeed want this one.
861
125812
            self.mds[rsidx] = Some(md);
862
125812

            
863
125812
            // Save some space in the missing-descriptor list.
864
125812
            if self.rsidx_by_missing.len() < self.rsidx_by_missing.capacity() / 4 {
865
6338
                self.rsidx_by_missing.shrink_to_fit();
866
119474
            }
867

            
868
125812
            return true;
869
74
        }
870
74

            
871
74
        // Either we already had it, or we never wanted it at all.
872
74
        false
873
125886
    }
874

            
875
    /// Construct a (possibly invalid) Relay object from a routerstatus and its
876
    /// index within the consensus.
877
14882217
    fn relay_from_rs_and_rsidx<'a>(
878
14882217
        &'a self,
879
14882217
        rs: &'a netstatus::MdConsensusRouterStatus,
880
14882217
        rsidx: RouterStatusIdx,
881
14882217
    ) -> UncheckedRelay<'a> {
882
14882217
        debug_assert_eq!(self.c_relays()[rsidx].rsa_identity(), rs.rsa_identity());
883
14882217
        let md = self.mds[rsidx].as_deref();
884
14882217
        if let Some(md) = md {
885
14878000
            debug_assert_eq!(rs.md_digest(), md.digest());
886
4217
        }
887

            
888
14882217
        UncheckedRelay {
889
14882217
            rs,
890
14882217
            md,
891
14882217
            #[cfg(feature = "geoip")]
892
14882217
            cc: self.country_codes.get(rsidx.0).copied().flatten(),
893
14882217
        }
894
14882217
    }
895

            
896
    /// Return the value of the hsdir_n_replicas param.
897
    #[cfg(feature = "hs-common")]
898
333
    fn n_replicas(&self) -> u8 {
899
333
        self.params
900
333
            .hsdir_n_replicas
901
333
            .get()
902
333
            .try_into()
903
333
            .expect("BoundedInt did not enforce bounds")
904
333
    }
905

            
906
    /// Return the spread parameter for the specified `op`.
907
    #[cfg(feature = "hs-common")]
908
333
    fn spread(&self, op: HsDirOp) -> usize {
909
333
        let spread = match op {
910
37
            HsDirOp::Download => self.params.hsdir_spread_fetch,
911
            #[cfg(feature = "hs-service")]
912
296
            HsDirOp::Upload => self.params.hsdir_spread_store,
913
        };
914

            
915
333
        spread
916
333
            .get()
917
333
            .try_into()
918
333
            .expect("BoundedInt did not enforce bounds!")
919
333
    }
920

            
921
    /// Select `spread` hsdir relays for the specified `hsid` from a given `ring`.
922
    ///
923
    /// Algorithm:
924
    ///
925
    /// for idx in 1..=n_replicas:
926
    ///       - let H = hsdir_ring::onion_service_index(id, replica, rand,
927
    ///         period).
928
    ///       - Find the position of H within hsdir_ring.
929
    ///       - Take elements from hsdir_ring starting at that position,
930
    ///         adding them to Dirs until we have added `spread` new elements
931
    ///         that were not there before.
932
    #[cfg(feature = "hs-common")]
933
333
    fn select_hsdirs<'h, 'r: 'h>(
934
333
        &'r self,
935
333
        hsid: HsBlindId,
936
333
        ring: &'h HsDirRing,
937
333
        spread: usize,
938
333
    ) -> impl Iterator<Item = Relay<'r>> + 'h {
939
333
        let n_replicas = self.n_replicas();
940
333

            
941
333
        (1..=n_replicas) // 1-indexed !
942
333
            .flat_map({
943
333
                let mut selected_nodes = HashSet::new();
944
333

            
945
358
                move |replica: u8| {
946
36
                    let hsdir_idx = hsdir_ring::service_hsdir_index(&hsid, replica, ring.params());
947
36

            
948
36
                    let items = ring
949
186
                        .ring_items_at(hsdir_idx, spread, |(hsdir_idx, _)| {
950
186
                            // According to rend-spec 2.2.3:
951
186
                            //                                                  ... If any of those
952
186
                            // nodes have already been selected for a lower-numbered replica of the
953
186
                            // service, any nodes already chosen are disregarded (i.e. skipped over)
954
186
                            // when choosing a replica's hsdir_spread_store nodes.
955
186
                            selected_nodes.insert(*hsdir_idx)
956
186
                        })
957
36
                        .collect::<Vec<_>>();
958
36

            
959
36
                    items
960
358
                }
961
333
            })
962
458
            .filter_map(move |(_hsdir_idx, rs_idx)| {
963
140
                // This ought not to be None but let's not panic or bail if it is
964
140
                self.relay_by_rs_idx(*rs_idx)
965
458
            })
966
333
    }
967

            
968
    /// Replace the overridden parameters in this netdir with `new_replacement`.
969
    ///
970
    /// After this function is done, the netdir's parameters will be those in
971
    /// the consensus, overridden by settings from `new_replacement`.  Any
972
    /// settings in the old replacement parameters will be discarded.
973
21
    pub fn replace_overridden_parameters(&mut self, new_replacement: &netstatus::NetParams<i32>) {
974
21
        // TODO(nickm): This is largely duplicate code from PartialNetDir::new().
975
21
        let mut new_params = NetParameters::default();
976
21
        let _ = new_params.saturating_update(self.consensus.params().iter());
977
21
        for u in new_params.saturating_update(new_replacement.iter()) {
978
            warn!("Unrecognized option: override_net_params.{}", u);
979
        }
980

            
981
21
        self.params = new_params;
982
21
    }
983

            
984
    /// Return an iterator over all Relay objects, including invalid ones
985
    /// that we can't use.
986
371779
    pub fn all_relays(&self) -> impl Iterator<Item = UncheckedRelay<'_>> {
987
371779
        // TODO: I'd like if we could memoize this so we don't have to
988
371779
        // do so many hashtable lookups.
989
371779
        self.c_relays()
990
371779
            .iter_enumerated()
991
14750868
            .map(move |(rsidx, rs)| self.relay_from_rs_and_rsidx(rs, rsidx))
992
371779
    }
993
    /// Return an iterator over all [usable](NetDir#usable) Relays.
994
356257
    pub fn relays(&self) -> impl Iterator<Item = Relay<'_>> {
995
356257
        self.all_relays().filter_map(UncheckedRelay::into_relay)
996
356257
    }
997

            
998
    /// Look up a relay's `MicroDesc` by its `RouterStatusIdx`
999
    #[cfg_attr(not(feature = "hs-common"), allow(dead_code))]
    pub(crate) fn md_by_rsidx(&self, rsidx: RouterStatusIdx) -> Option<&Microdesc> {
        self.mds.get(rsidx)?.as_deref()
    }
    /// Return a relay matching a given identity, if we have a
    /// _usable_ relay with that key.
    ///
    /// (Does not return [unusable](NetDir#usable) relays.)
    ///
    ///
    /// Note that a `None` answer is not always permanent: if a microdescriptor
    /// is subsequently added for a relay with this ID, the ID may become usable
    /// even if it was not usable before.
6464
    pub fn by_id<'a, T>(&self, id: T) -> Option<Relay<'_>>
6464
    where
6464
        T: Into<RelayIdRef<'a>> + ?Sized,
6464
    {
6464
        let id = id.into();
6464
        let answer = match id {
6350
            RelayIdRef::Ed25519(ed25519) => {
6350
                let rsidx = *self.rsidx_by_ed.get(ed25519)?;
6230
                let rs = self.c_relays().get(rsidx).expect("Corrupt index");
6230

            
6230
                self.relay_from_rs_and_rsidx(rs, rsidx).into_relay()?
            }
114
            RelayIdRef::Rsa(rsa) => self
114
                .by_rsa_id_unchecked(rsa)
114
                .and_then(UncheckedRelay::into_relay)?,
            other_type => self.relays().find(|r| r.has_identity(other_type))?,
        };
6236
        assert!(answer.has_identity(id));
6236
        Some(answer)
6464
    }
    /// Obtain a `Relay` given a `RouterStatusIdx`
    ///
    /// Differs from `relay_from_rs_and_rsi` as follows:
    ///  * That function expects the caller to already have an `MdConsensusRouterStatus`;
    ///    it checks with `debug_assert` that the relay in the netdir matches.
    ///  * That function panics if the `RouterStatusIdx` is invalid; this one returns `None`.
    ///  * That function returns an `UncheckedRelay`; this one a `Relay`.
    ///
    /// `None` could be returned here, even with a valid `rsi`,
    /// if `rsi` refers to an [unusable](NetDir#usable) relay.
    #[cfg_attr(not(feature = "hs-common"), allow(dead_code))]
2618
    pub(crate) fn relay_by_rs_idx(&self, rs_idx: RouterStatusIdx) -> Option<Relay<'_>> {
2618
        let rs = self.c_relays().get(rs_idx)?;
2618
        let md = self.mds.get(rs_idx)?.as_deref();
2618
        UncheckedRelay {
2618
            rs,
2618
            md,
2618
            #[cfg(feature = "geoip")]
2618
            cc: self.country_codes.get(rs_idx.0).copied().flatten(),
2618
        }
2618
        .into_relay()
2618
    }
    /// Return a relay with the same identities as those in `target`, if one
    /// exists.
    ///
    /// Does not return [unusable](NetDir#usable) relays.
    ///
    /// # Limitations
    ///
    /// This will be very slow if `target` does not have an Ed25519 or RSA
    /// identity.
3586
    pub fn by_ids<T>(&self, target: &T) -> Option<Relay<'_>>
3586
    where
3586
        T: HasRelayIds + ?Sized,
3586
    {
3586
        let mut identities = target.identities();
        // Don't try if there are no identities.
3586
        let first_id = identities.next()?;
        // Since there is at most one relay with each given ID type,
        // we only need to check the first relay we find.
3586
        let candidate = self.by_id(first_id)?;
3576
        if identities.all(|wanted_id| candidate.has_identity(wanted_id)) {
3574
            Some(candidate)
        } else {
2
            None
        }
3586
    }
    /// Check whether there is a relay that has at least one identity from
    /// `target`, and which _could_ have every identity from `target`.
    /// If so, return such a relay.
    ///
    /// Return `Ok(None)` if we did not find a relay with any identity from `target`.
    ///
    /// Return `RelayLookupError::Impossible` if we found a relay with at least
    /// one identity from `target`, but that relay's other identities contradict
    /// what we learned from `target`.
    ///
    /// Does not return [unusable](NetDir#usable) relays.
    ///
    /// (This function is only useful if you need to distinguish the
    /// "impossible" case from the "no such relay known" case.)
    ///
    /// # Limitations
    ///
    /// This will be very slow if `target` does not have an Ed25519 or RSA
    /// identity.
    //
    // TODO HS: This function could use a better name.
    //
    // TODO: We could remove the feature restriction here once we think this API is
    // stable.
    #[cfg(feature = "hs-common")]
20
    pub fn by_ids_detailed<T>(
20
        &self,
20
        target: &T,
20
    ) -> std::result::Result<Option<Relay<'_>>, RelayLookupError>
20
    where
20
        T: HasRelayIds + ?Sized,
20
    {
20
        let candidate = target
20
            .identities()
20
            // Find all the relays that share any identity with this set of identities.
36
            .filter_map(|id| self.by_id(id))
20
            // We might find the same relay more than once under a different
20
            // identity, so we remove the duplicates.
20
            //
20
            // Since there is at most one relay per rsa identity per consensus,
20
            // this is a true uniqueness check under current construction rules.
20
            .unique_by(|r| r.rs.rsa_identity())
20
            // If we find two or more distinct relays, then have a contradiction.
20
            .at_most_one()
20
            .map_err(|_| RelayLookupError::Impossible)?;
        // If we have no candidate, return None early.
20
        let candidate = match candidate {
10
            Some(relay) => relay,
10
            None => return Ok(None),
        };
        // Now we know we have a single candidate.  Make sure that it does not have any
        // identity that does not match the target.
10
        if target
10
            .identities()
14
            .all(|wanted_id| match candidate.identity(wanted_id.id_type()) {
                None => true,
14
                Some(id) => id == wanted_id,
14
            })
        {
6
            Ok(Some(candidate))
        } else {
4
            Err(RelayLookupError::Impossible)
        }
20
    }
    /// Return a boolean if this consensus definitely has (or does not have) a
    /// relay matching the listed identities.
    ///
    ///
    /// If we can't yet tell for sure, return None. Once function has returned
    /// `Some(b)`, it will always return that value for the same `ed_id` and
    /// `rsa_id` on this `NetDir`.  A `None` answer may later become `Some(b)`
    /// if a microdescriptor arrives.
576
    fn id_pair_listed(&self, ed_id: &Ed25519Identity, rsa_id: &RsaIdentity) -> Option<bool> {
576
        let r = self.by_rsa_id_unchecked(rsa_id);
576
        match r {
426
            Some(unchecked) => {
426
                if !unchecked.rs.ed25519_id_is_usable() {
                    return Some(false);
426
                }
426
                // If md is present, then it's listed iff we have the right
426
                // ed id.  Otherwise we don't know if it's listed.
438
                unchecked.md.map(|md| md.ed25519_id() == ed_id)
            }
            None => {
                // Definitely not listed.
150
                Some(false)
            }
        }
576
    }
    /// As `id_pair_listed`, but check whether a relay exists (or may exist)
    /// with the same identities as those in `target`.
    ///
    /// # Limitations
    ///
    /// This can be inefficient if the target does not have both an ed25519 and
    /// an rsa identity key.
138
    pub fn ids_listed<T>(&self, target: &T) -> Option<bool>
138
    where
138
        T: HasRelayIds + ?Sized,
138
    {
138
        let rsa_id = target.rsa_identity();
138
        let ed25519_id = target.ed_identity();
138

            
138
        // TODO: If we later support more identity key types, this will
138
        // become incorrect.  This assertion might help us recognize that case.
138
        const_assert!(RelayIdType::COUNT == 2);
138

            
138
        match (rsa_id, ed25519_id) {
138
            (Some(r), Some(e)) => self.id_pair_listed(e, r),
            (Some(r), None) => Some(self.rsa_id_is_listed(r)),
            (None, Some(e)) => {
                if self.rsidx_by_ed.contains_key(e) {
                    Some(true)
                } else {
                    None
                }
            }
            (None, None) => None,
        }
138
    }
    /// Return a (possibly [unusable](NetDir#usable)) relay with a given RSA identity.
    ///
    /// This API can be used to find information about a relay that is listed in
    /// the current consensus, even if we don't yet have enough information
    /// (like a microdescriptor) about the relay to use it.
12772
    #[cfg_attr(feature = "experimental-api", visibility::make(pub))]
12772
    #[cfg_attr(docsrs, doc(cfg(feature = "experimental-api")))]
13570
    fn by_rsa_id_unchecked(&self, rsa_id: &RsaIdentity) -> Option<UncheckedRelay<'_>> {
13570
        let rsidx = *self.rsidx_by_rsa.get(rsa_id)?;
13299
        let rs = self.c_relays().get(rsidx).expect("Corrupt index");
13299
        assert_eq!(rs.rsa_identity(), rsa_id);
13299
        Some(self.relay_from_rs_and_rsidx(rs, rsidx))
13570
    }
    /// Return the relay with a given RSA identity, if we have one
    /// and it is [usable](NetDir#usable).
308
    fn by_rsa_id(&self, rsa_id: &RsaIdentity) -> Option<Relay<'_>> {
308
        self.by_rsa_id_unchecked(rsa_id)?.into_relay()
308
    }
    /// Return true if `rsa_id` is listed in this directory, even if it isn't
    /// currently usable.
    ///
    /// (An "[unusable](NetDir#usable)" relay in this context is one for which we don't have full
    /// directory information.)
6
    #[cfg_attr(feature = "experimental-api", visibility::make(pub))]
6
    #[cfg_attr(docsrs, doc(cfg(feature = "experimental-api")))]
6
    fn rsa_id_is_listed(&self, rsa_id: &RsaIdentity) -> bool {
6
        self.by_rsa_id_unchecked(rsa_id).is_some()
6
    }
    /// List the hsdirs in this NetDir, that should be in the HSDir rings
    ///
    /// The results are not returned in any particular order.
    #[cfg(feature = "hs-common")]
3194
    fn all_hsdirs(&self) -> impl Iterator<Item = (RouterStatusIdx, Relay<'_>)> {
125782
        self.c_relays().iter_enumerated().filter_map(|(rsidx, rs)| {
125682
            let relay = self.relay_from_rs_and_rsidx(rs, rsidx);
125682
            relay.is_hsdir_for_ring().then_some(())?;
31676
            let relay = relay.into_relay()?;
31668
            Some((rsidx, relay))
125782
        })
3194
    }
    /// Return the parameters from the consensus, clamped to the
    /// correct ranges, with defaults filled in.
    ///
    /// NOTE: that unsupported parameters aren't returned here; only those
    /// values configured in the `params` module are available.
6705
    pub fn params(&self) -> &NetParameters {
6705
        &self.params
6705
    }
    /// Return a [`ProtoStatus`](netstatus::ProtoStatus) that lists the
    /// network's current requirements and recommendations for the list of
    /// protocols that every relay must implement.
    //
    // TODO HS: I am not sure this is the right API; other alternatives would be:
    //    * To expose the _required_ relay protocol list instead (since that's all that
    //      onion service implementations need).
    //    * To expose the client protocol list as well (for symmetry).
    //    * To expose the MdConsensus instead (since that's more general, although
    //      it restricts the future evolution of this API).
    //
    // I think that this is a reasonably good compromise for now, but I'm going
    // to put it behind the `hs-common` feature to give us time to consider more.
    #[cfg(feature = "hs-common")]
111
    pub fn relay_protocol_status(&self) -> &netstatus::ProtoStatus {
111
        self.consensus.relay_protocol_status()
111
    }
    /// Return weighted the fraction of relays we can use.  We only
    /// consider relays that match the predicate `usable`.  We weight
    /// this bandwidth according to the provided `role`.
    ///
    /// If _no_ matching relays in the consensus have a nonzero
    /// weighted bandwidth value, we fall back to looking at the
    /// unweighted fraction of matching relays.
    ///
    /// If there are no matching relays in the consensus, we return 0.0.
10188
    fn frac_for_role<'a, F>(&'a self, role: WeightRole, usable: F) -> f64
10188
    where
10188
        F: Fn(&UncheckedRelay<'a>) -> bool,
10188
    {
10188
        let mut total_weight = 0_u64;
10188
        let mut have_weight = 0_u64;
10188
        let mut have_count = 0_usize;
10188
        let mut total_count = 0_usize;
381492
        for r in self.all_relays() {
381492
            if !usable(&r) {
125624
                continue;
255868
            }
255868
            let w = self.weights.weight_rs_for_role(r.rs, role);
255868
            total_weight += w;
255868
            total_count += 1;
255868
            if r.is_usable() {
252508
                have_weight += w;
252508
                have_count += 1;
253012
            }
        }
10188
        if total_weight > 0 {
            // The consensus lists some weighted bandwidth so return the
            // fraction of the weighted bandwidth for which we have
            // descriptors.
10188
            (have_weight as f64) / (total_weight as f64)
        } else if total_count > 0 {
            // The consensus lists no weighted bandwidth for these relays,
            // but at least it does list relays. Return the fraction of
            // relays for which it we have descriptors.
            (have_count as f64) / (total_count as f64)
        } else {
            // There are no relays of this kind in the consensus.  Return
            // 0.0, to avoid dividing by zero and giving NaN.
            0.0
        }
10188
    }
    /// Return the estimated fraction of possible paths that we have
    /// enough microdescriptors to build.
3394
    fn frac_usable_paths(&self) -> f64 {
3394
        // TODO #504, TODO SPEC: We may want to add a set of is_flagged_fast() and/or
3394
        // is_flagged_stable() checks here.  This will require spec clarification.
127195
        let f_g = self.frac_for_role(WeightRole::Guard, |u| u.is_suitable_as_guard());
127195
        let f_m = self.frac_for_role(WeightRole::Middle, |_| true);
34965
        let f_e = if self.all_relays().any(|u| u.rs.is_flagged_exit()) {
127195
            self.frac_for_role(WeightRole::Exit, |u| u.rs.is_flagged_exit())
        } else {
            // If there are no exits at all, we use f_m here.
            f_m
        };
3394
        f_g * f_m * f_e
3394
    }
    /// Return true if there is enough information in this NetDir to build
    /// multihop circuits.
3392
    fn have_enough_paths(&self) -> bool {
3392
        // TODO-A001: This should check for our guards as well, and
3392
        // make sure that if they're listed in the consensus, we have
3392
        // the descriptors for them.
3392

            
3392
        // If we can build a randomly chosen path with at least this
3392
        // probability, we know enough information to participate
3392
        // on the network.
3392

            
3392
        let min_frac_paths: f64 = self.params().min_circuit_path_threshold.as_fraction();
3392

            
3392
        // What fraction of paths can we build?
3392
        let available = self.frac_usable_paths();
3392

            
3392
        available >= min_frac_paths
3392
    }
    /// Choose a relay at random.
    ///
    /// Each relay is chosen with probability proportional to its weight
    /// in the role `role`, and is only selected if the predicate `usable`
    /// returns true for it.
    ///
    /// This function returns None if (and only if) there are no relays
    /// with nonzero weight where `usable` returned true.
    //
    // TODO this API, with the `usable` closure, invites mistakes where we fail to
    // check conditions that are implied by the role we have selected for the relay:
    // call sites must include a call to `Relay::is_polarity_inverter()` or whatever.
    // IMO the `WeightRole` ought to imply a condition (and it should therefore probably
    // be renamed.)  -Diziet
28454
    pub fn pick_relay<'a, R, P>(
28454
        &'a self,
28454
        rng: &mut R,
28454
        role: WeightRole,
28454
        usable: P,
28454
    ) -> Option<Relay<'a>>
28454
    where
28454
        R: rand::Rng,
28454
        P: FnMut(&Relay<'a>) -> bool,
28454
    {
28454
        let relays: Vec<_> = self.relays().filter(usable).collect();
28454
        // This algorithm uses rand::distributions::WeightedIndex, and uses
28454
        // gives O(n) time and space  to build the index, plus O(log n)
28454
        // sampling time.
28454
        //
28454
        // We might be better off building a WeightedIndex in advance
28454
        // for each `role`, and then sampling it repeatedly until we
28454
        // get a relay that satisfies `usable`.  Or we might not --
28454
        // that depends heavily on the actual particulars of our
28454
        // inputs.  We probably shouldn't make any changes there
28454
        // unless profiling tells us that this function is in a hot
28454
        // path.
28454
        //
28454
        // The C Tor sampling implementation goes through some trouble
28454
        // here to try to make its path selection constant-time.  I
28454
        // believe that there is no actual remotely exploitable
28454
        // side-channel here however.  It could be worth analyzing in
28454
        // the future.
28454
        //
28454
        // This code will give the wrong result if the total of all weights
28454
        // can exceed u64::MAX.  We make sure that can't happen when we
28454
        // set up `self.weights`.
28454
        relays[..]
539812
            .choose_weighted(rng, |r| self.weights.weight_rs_for_role(r.rs, role))
28454
            .ok()
28454
            .cloned()
28454
    }
    /// Choose `n` relay at random.
    ///
    /// Each relay is chosen with probability proportional to its weight
    /// in the role `role`, and is only selected if the predicate `usable`
    /// returns true for it.
    ///
    /// Relays are chosen without replacement: no relay will be
    /// returned twice. Therefore, the resulting vector may be smaller
    /// than `n` if we happen to have fewer than `n` appropriate relays.
    ///
    /// This function returns an empty vector if (and only if) there
    /// are no relays with nonzero weight where `usable` returned
    /// true.
3188
    pub fn pick_n_relays<'a, R, P>(
3188
        &'a self,
3188
        rng: &mut R,
3188
        n: usize,
3188
        role: WeightRole,
3188
        usable: P,
3188
    ) -> Vec<Relay<'a>>
3188
    where
3188
        R: rand::Rng,
3188
        P: FnMut(&Relay<'a>) -> bool,
3188
    {
3188
        let relays: Vec<_> = self.relays().filter(usable).collect();
        // NOTE: See discussion in pick_relay().
53438
        let mut relays = match relays[..].choose_multiple_weighted(rng, n, |r| {
53438
            self.weights.weight_rs_for_role(r.rs, role) as f64
53438
        }) {
            Err(_) => Vec::new(),
3188
            Ok(iter) => iter.map(Relay::clone).collect(),
        };
3188
        relays.shuffle(rng);
3188
        relays
3188
    }
    /// Compute the weight with which `relay` will be selected for a given
    /// `role`.
23278
    pub fn relay_weight<'a>(&'a self, relay: &Relay<'a>, role: WeightRole) -> RelayWeight {
23278
        RelayWeight(self.weights.weight_rs_for_role(relay.rs, role))
23278
    }
    /// Compute the total weight with which any relay matching `usable`
    /// will be selected for a given `role`.
    ///
    /// Note: because this function is used to assess the total
    /// properties of the consensus, the `usable` predicate takes a
    /// [`RouterStatus`] rather than a [`Relay`].
692
    pub fn total_weight<P>(&self, role: WeightRole, usable: P) -> RelayWeight
692
    where
692
        P: Fn(&UncheckedRelay<'_>) -> bool,
692
    {
692
        self.all_relays()
25248
            .filter_map(|unchecked| {
25248
                if usable(&unchecked) {
6828
                    Some(RelayWeight(
6828
                        self.weights.weight_rs_for_role(unchecked.rs, role),
6828
                    ))
                } else {
18420
                    None
                }
25248
            })
692
            .sum()
692
    }
    /// Compute the weight with which a relay with ID `rsa_id` would be
    /// selected for a given `role`.
    ///
    /// Note that weight returned by this function assumes that the
    /// relay with that ID is actually [usable](NetDir#usable); if it isn't usable,
    /// then other weight-related functions will call its weight zero.
12553
    pub fn weight_by_rsa_id(&self, rsa_id: &RsaIdentity, role: WeightRole) -> Option<RelayWeight> {
12553
        self.by_rsa_id_unchecked(rsa_id)
12907
            .map(|unchecked| RelayWeight(self.weights.weight_rs_for_role(unchecked.rs, role)))
12553
    }
    /// Return all relays in this NetDir known to be in the same family as
    /// `relay`.
    ///
    /// This list of members will **not** necessarily include `relay` itself.
    ///
    /// # Limitations
    ///
    /// Two relays only belong to the same family if _each_ relay
    /// claims to share a family with the other.  But if we are
    /// missing a microdescriptor for one of the relays listed by this
    /// relay, we cannot know whether it acknowledges family
    /// membership with this relay or not.  Therefore, this function
    /// can omit family members for which there is not (as yet) any
    /// Relay object.
300
    pub fn known_family_members<'a>(
300
        &'a self,
300
        relay: &'a Relay<'a>,
300
    ) -> impl Iterator<Item = Relay<'a>> {
300
        let relay_rsa_id = relay.rsa_id();
314
        relay.md.family().members().filter_map(move |other_rsa_id| {
24
            self.by_rsa_id(other_rsa_id)
24
                .filter(|other_relay| other_relay.md.family().contains(relay_rsa_id))
314
        })
300
    }
    /// Return the current hidden service directory "time period".
    ///
    /// Specifically, this returns the time period that contains the beginning
    /// of the validity period of this `NetDir`'s consensus.  That time period
    /// is the one we use when acting as an hidden service client.
    #[cfg(feature = "hs-common")]