Skip to main content

tor_guardmgr/
sample.rs

1//! Logic for manipulating a sampled set of guards, along with various
2//! orderings on that sample.
3
4mod candidate;
5
6use crate::filter::GuardFilter;
7use crate::guard::{Guard, NewlyConfirmed, Reachable};
8use crate::skew::SkewObservation;
9use crate::{
10    ExternalActivity, GuardParams, GuardUsage, GuardUsageKind, PickGuardError, ids::GuardId,
11};
12use crate::{FirstHop, GuardSetSelector};
13use saturating_time::SaturatingTime as _;
14use tor_basic_utils::iter::{FilterCount, IteratorExt as _};
15use tor_basic_utils::onionperf_types::{OnionperfEvent, OnionperfGuardStatus};
16use tor_error::{internal, warn_report};
17use tor_linkspec::{ByRelayIds, HasRelayIds};
18
19use itertools::Itertools;
20use rand::seq::IndexedRandom;
21use serde::{Deserialize, Serialize};
22use std::borrow::Cow;
23use std::collections::{HashMap, HashSet};
24use tracing::{debug, info, trace};
25use web_time_compat::{Instant, SystemTime};
26
27#[allow(unused_imports)]
28pub(crate) use candidate::{Candidate, CandidateStatus, Universe, UniverseRef, WeightThreshold};
29
30/// A set of sampled guards, along with various orderings on subsets
31/// of the sample.
32///
33/// Every guard in a `GuardSet` is considered to be "sampled": that
34/// is, selected from a network directory at some point in the past.
35/// The guards in the sample are ordered (roughly) by the time at
36/// which they were added.  This list is persistent.
37///
38/// Any guard which we've successfully used at least once is
39/// considered "confirmed".  Confirmed guards are ordered (roughly) by
40/// the time at which we first used them.  This list is persistent.
41///
42/// The guards which we would prefer to use are called "primary".
43/// Primary guards are ordered from most- to least-preferred.
44/// This list is not persistent, and is re-derived as needed.
45///
46/// These lists together define a "preference order".  All primary
47/// guards come first in preference order.  Then come the non-primary
48/// confirmed guards, in their confirmed order.  Finally come the
49/// non-primary, non-confirmed guards, in their sampled order.
50#[derive(Debug, Default, Clone, Deserialize)]
51#[serde(from = "GuardSample")]
52pub(crate) struct GuardSet {
53    /// Map from identities to guards, for every guard in this sample.
54    ///
55    /// The key for each entry is a set of identities which we have
56    /// good (trustworthy-enough) reason to link together.
57    ///
58    /// When we connect to a guard we require it to demonstrate
59    /// that it has *all* of these identities;
60    /// and we do pinning, so that we note down the other identities we discover it has,
61    /// with the intent that we will require them in future.
62    ///
63    /// ### Sources of linkage:
64    ///
65    ///  * If we connect to a relay and it proves a set of identities,
66    ///    that necessarily will include at least the ones we have already.
67    ///    We can add any other identities we have discovered.
68    ///    Justification: the owners of the old ids have made a statement
69    ///    (via the connection protocols) that these other ids are also theirs,
70    ///    and should be required in future.
71    ///
72    ///  * If we obtain a (full) descriptor for a relay, and check the
73    ///    self-signatures by all the identities we have already,
74    ///    we can add any other identities listed in the descriptor.
75    ///    Justification: the owners of the old ids have made an explicit statement
76    ///    that these other ids are also theirs,
77    ///    and should be required in future.
78    ///
79    ///  * For a relay in the netdir, if the netdir links some ids together,
80    ///    we can combine the entries.
81    ///    Justification: the netdir is authoritative for netdir-based relays.
82    ///
83    ///  * For a configured bridge, if our configuration links some identities,
84    ///    we must insist on all those identities.
85    ///    So we combine them.
86    ///
87    /// ### Handling of conflicting entries:
88    ///
89    /// `ByRelayIds` will implicitly delete conflicting entries,
90    /// simply forgetting about them.
91    /// This is OK for netdir relays, since we do not expect this to occur in practice.
92    ///
93    /// For bridges, conflicts may in fact occur,
94    /// since bridge lines are not issued by a single authority,
95    /// and should be afforded limited trust.
96    ///
97    ///  * If the configuration contains bridge lines that mutually conflict,
98    ///    affected bridge lines should be disregarded,
99    ///    or the configuration rejected.
100    ///
101    ///  * If the configuration contains information which is inconsistent with
102    ///    our past experience, we should discard the past experiences which
103    ///    aren't reconcilable with the configuration.
104    ///
105    ///  * We may discover a linkage which demonstrates that the configuration
106    ///    is wrong: for example, two bridge lines for identities X and Y,
107    ///    but in fact there is only one bridge with both identities.
108    ///    In this situation it is OK to effectively disregard some the configuration
109    ///    entries which are at variance with reality, maybe with a warning,
110    ///    but keeping at least one of every usable id set (actually existing bridge)
111    ///    would be good.
112    guards: ByRelayIds<Guard>,
113    /// Identities of all the guards in the sample, in sample order.
114    ///
115    /// This contains the same elements as the keys of `guards`
116    sample: Vec<GuardId>,
117    /// Identities of all the confirmed guards in the sample, in
118    /// confirmed order.
119    ///
120    /// This contains a subset of the values in `sample`.
121    confirmed: Vec<GuardId>,
122    /// Identities of all the primary guards, in preference order
123    /// (from best to worst).
124    ///
125    /// This contains a subset of the values in `sample`.
126    primary: Vec<GuardId>,
127    /// Currently active filter that restricts which guards we can use.
128    ///
129    /// Note that all of the lists above (with the exception of `primary`)
130    /// can hold guards that the filter doesn't permit.  This behavior
131    /// is meant to give good security behavior in the presence of filters
132    /// that change over time.
133    active_filter: GuardFilter,
134
135    /// If true, the active filter is "very restrictive".
136    filter_is_restrictive: bool,
137
138    /// Set to 'true' whenever something changes that would force us
139    /// to call 'select_primary_guards()', and cleared whenever we call it.
140    primary_guards_invalidated: bool,
141
142    /// Fields from the state file that was used to make this `GuardSet` that
143    /// this version of Arti doesn't understand.
144    unknown_fields: HashMap<String, JsonValue>,
145}
146
147/// Which of our lists did a given guard come from?
148#[derive(Debug, Copy, Clone, Eq, PartialEq)]
149pub(crate) enum ListKind {
150    /// A guard that came from the primary guard list.
151    Primary,
152    /// A non-primary guard that came from the confirmed guard list.
153    Confirmed,
154    /// A non-primary, non-confirmed guard.
155    Sample,
156    /// Not a guard at all, but a fallback directory.
157    Fallback,
158}
159
160impl ListKind {
161    /// Return true if this is a primary guard.
162    pub(crate) fn is_primary(&self) -> bool {
163        self == &ListKind::Primary
164    }
165
166    /// Return true if this guard's origin indicates that you can use successful
167    /// circuits built through it immediately without waiting for any other
168    /// circuits to succeed or fail.
169    pub(crate) fn usable_immediately(&self) -> bool {
170        match self {
171            ListKind::Primary | ListKind::Fallback => true,
172            ListKind::Confirmed | ListKind::Sample => false,
173        }
174    }
175}
176
177impl GuardSet {
178    /// Return the lengths of the different elements of the guard set.
179    ///
180    /// Used to report bugs or corruption in consistency.
181    fn inner_lengths(&self) -> (usize, usize, usize, usize) {
182        (
183            self.guards.len(),
184            self.sample.len(),
185            self.confirmed.len(),
186            self.primary.len(),
187        )
188    }
189
190    /// Remove all elements from this `GuardSet` that ought to be referenced by
191    /// another element, but which are not.
192    ///
193    /// This method only removes corrupted elements and updates IDs in the ID
194    /// list (possibly adding new IDs); it doesn't add guards or other data.
195    /// It won't do anything if the `GuardSet` is well-formed.
196    fn fix_consistency(&mut self) {
197        /// Remove every element of `id_list` that does not belong to some guard
198        /// in `guards`, and update the others to have any extra identities
199        /// listed in `guards`.
200        fn fix_id_list(guards: &ByRelayIds<Guard>, id_list: &mut Vec<GuardId>) {
201            id_list.retain_mut(|id| match guards.by_all_ids(id) {
202                Some(guard) => {
203                    *id = guard.guard_id().clone();
204                    true
205                }
206                None => false,
207            });
208        }
209
210        let sample_set: HashSet<_> = self.sample.iter().collect();
211        self.guards.retain(|g| sample_set.contains(g.guard_id()));
212        fix_id_list(&self.guards, &mut self.sample);
213        fix_id_list(&self.guards, &mut self.confirmed);
214        fix_id_list(&self.guards, &mut self.primary);
215    }
216
217    /// Log an internal error if this `GuardSet` is not internally consistent.
218    ///
219    /// If debug assertions are enabled, panic on failure.
220    ///
221    /// Incidentally fixes the consistency of this `GuardSet` if needed.
222    fn assert_consistency(&mut self) {
223        let len_pre = self.inner_lengths();
224        self.fix_consistency();
225        let len_post = self.inner_lengths();
226        if len_pre != len_post {
227            // This is the most convenient way to get a backtrace.  We want a backtrace so that
228            // we can blame the function where the error actually occurred.
229            let e = internal!("Inner length changed from {len_pre:?} to {len_post:?}");
230            warn_report!(
231                e,
232                "Found guard sample in an inconsistent state, and restored it"
233            );
234            debug_assert_eq!(len_pre, len_post);
235        }
236    }
237
238    /// Return the guard that has every identity in `id`, if any.
239    pub(crate) fn get(&self, id: &GuardId) -> Option<&Guard> {
240        self.guards.by_all_ids(id)
241    }
242
243    /// Replace the filter used by this `GuardSet` with `filter`.
244    ///
245    /// Removes all primary guards that the filter doesn't permit.
246    ///
247    /// If `restrictive` is true, this filter is treated as "extremely restrictive".
248    pub(crate) fn set_filter(&mut self, filter: GuardFilter, restrictive: bool) {
249        self.active_filter = filter;
250        self.filter_is_restrictive = restrictive;
251
252        self.assert_consistency();
253
254        let guards = &self.guards; // avoid borrow issues
255        let filt = &self.active_filter;
256        self.primary.retain(|id| {
257            guards
258                .by_all_ids(id)
259                .map(|g| g.usable() && filt.permits(g))
260                .unwrap_or(false)
261        });
262
263        self.primary_guards_invalidated = true;
264    }
265
266    /// Return the current filter for this `GuardSet`.
267    pub(crate) fn filter(&self) -> &GuardFilter {
268        &self.active_filter
269    }
270
271    /// Copy non-persistent status from every guard shared with `other`.
272    ///
273    /// This is used as part of our reload process when we don't own our state
274    /// files, and we're reloading in order to find out what the other Arti
275    /// instance thinks the guards are. At that point, `self` is the set of
276    /// guards that we just loaded from state, and `other` is our old guards,
277    /// which we are using only for their status information.
278    pub(crate) fn copy_ephemeral_status_into_newly_loaded_state(&mut self, mut other: GuardSet) {
279        let old_guards = std::mem::take(&mut self.guards);
280        self.guards = old_guards
281            .into_values()
282            .map(|guard| {
283                let id = guard.guard_id();
284
285                if let Some(other_guard) = other.guards.remove_exact(id) {
286                    guard.copy_ephemeral_status_into_newly_loaded_state(other_guard)
287                } else {
288                    guard
289                }
290            })
291            .collect();
292    }
293
294    /// Return a serializable state object that can be stored to disk
295    /// to capture the current state of this GuardSet.
296    fn get_state(&self) -> GuardSample<'_> {
297        let guards = self
298            .sample
299            .iter()
300            .map(|id| Cow::Borrowed(self.guards.by_all_ids(id).expect("Inconsistent state")))
301            .collect();
302
303        GuardSample {
304            guards,
305            confirmed: Cow::Borrowed(&self.confirmed),
306            remaining: self.unknown_fields.clone(),
307        }
308    }
309
310    /// Reconstruct a guard state from its serialized representation.
311    fn from_state(state: GuardSample<'_>) -> Self {
312        let mut guards = ByRelayIds::new();
313        let mut sample = Vec::new();
314        for guard in state.guards {
315            sample.push(guard.guard_id().clone());
316            guards.insert(guard.into_owned());
317        }
318        let confirmed = state.confirmed.into_owned();
319        let primary = Vec::new();
320        let mut guard_set = GuardSet {
321            guards,
322            sample,
323            confirmed,
324            primary,
325            active_filter: GuardFilter::default(),
326            filter_is_restrictive: false,
327            primary_guards_invalidated: true,
328            unknown_fields: state.remaining,
329        };
330
331        // Fix any inconsistencies in the stored representation.
332        let len_pre = guard_set.inner_lengths();
333        guard_set.fix_consistency();
334        let len_post = guard_set.inner_lengths();
335        if len_pre != len_post {
336            info!(
337                "Resolved a consistency issue in stored guard state. Diagnostic codes: {:?}, {:?}",
338                len_pre, len_post
339            );
340        }
341        debug!(
342            n_guards = len_post.0,
343            n_confirmed = len_post.2,
344            "Guard set loaded."
345        );
346
347        guard_set
348    }
349
350    /// Return `Ok(true)` if `id` is definitely a member of this set, and
351    /// `Ok(false)` if it is definitely not a member.
352    ///
353    /// If we cannot tell, it's because there is a guard in this sample that has
354    /// a _subset_ of the IDs in `id`. In that case, we return
355    /// `Err(guard_ident)`, where `guard_ident`  is the identity of that guard.
356    pub(crate) fn contains(&self, id: &GuardId) -> Result<bool, &GuardId> {
357        let overlapping = self.guards.all_overlapping(id);
358        match &overlapping[..] {
359            [singleton] => {
360                if singleton.has_all_relay_ids_from(id) {
361                    Ok(true)
362                } else {
363                    Err(singleton.guard_id())
364                }
365            }
366            _ => Ok(false),
367        }
368    }
369
370    /// If there are not enough filter-permitted usable guards in this
371    /// sample (according to the current active filter), then add
372    /// more, up to the limits allowed by the parameters.
373    ///
374    /// This is the only function that adds new guards to the sample.
375    ///
376    /// Guards always start out un-confirmed.
377    ///
378    /// Return true if any guards were added.
379    pub(crate) fn extend_sample_as_needed<U: Universe>(
380        &mut self,
381        now: SystemTime,
382        params: &GuardParams,
383        dir: &U,
384    ) -> crate::ExtendedStatus {
385        let mut any_added = crate::ExtendedStatus::No;
386        while self.extend_sample_inner(now, params, dir) {
387            any_added = crate::ExtendedStatus::Yes;
388        }
389        any_added
390    }
391
392    /// Implementation helper for extend_sample_as_needed.
393    ///
394    /// # Complications
395    ///
396    /// For spec conformance, we only consider our filter when selecting new
397    /// guards if the filter is "very restrictive". That makes it possible that
398    /// this function will add fewer filter-permitted guards than we had wanted.
399    /// Because of that, this is a separate function, and
400    /// extend_sample_as_needed runs it in a loop until it returns false.
401    fn extend_sample_inner<U: Universe>(
402        &mut self,
403        now: SystemTime,
404        params: &GuardParams,
405        dir: &U,
406    ) -> bool {
407        self.assert_consistency();
408        let n_filtered_usable = self
409            .guards
410            .values()
411            .filter(|g| {
412                g.usable()
413                    && self.active_filter.permits(*g)
414                    && g.reachable() != Reachable::Unreachable
415            })
416            .count();
417        if n_filtered_usable >= params.min_filtered_sample_size {
418            return false; // We have enough usage guards in our sample.
419        }
420        if self.guards.len() >= params.max_sample_size {
421            return false; // We can't add any more guards to our sample.
422        }
423
424        // What are the most guards we're willing to have in the sample?
425        let max_to_add = params.max_sample_size - self.sample.len();
426        let want_to_add = params.min_filtered_sample_size - n_filtered_usable;
427        let n_to_add = std::cmp::min(max_to_add, want_to_add);
428
429        let WeightThreshold {
430            mut current_weight,
431            maximum_weight,
432        } = dir.weight_threshold(&self.guards, params);
433
434        // Ask the netdir for a set of guards we could use.
435        let no_filter = GuardFilter::unfiltered();
436        let (n_candidates, pre_filter) =
437            if self.filter_is_restrictive || self.active_filter.is_unfiltered() {
438                (n_to_add, &self.active_filter)
439            } else {
440                // The filter will probably reject a bunch of guards, but we sample
441                // before filtering, so we make this larger on an ad-hoc basis.
442                (n_to_add * 3, &no_filter)
443            };
444
445        let candidates = dir.sample(&self.guards, pre_filter, n_candidates);
446
447        // Add those candidates to the sample.
448        let mut any_added = false;
449        let mut n_filtered_usable = n_filtered_usable;
450        for (candidate, weight) in candidates {
451            // Don't add any more if we have met the minimal sample size, and we
452            // have added too much weight.
453            if current_weight >= maximum_weight
454                && self.guards.len() >= params.min_filtered_sample_size
455            {
456                break;
457            }
458            if self.guards.len() >= params.max_sample_size {
459                // Can't add any more.
460                break;
461            }
462            if n_filtered_usable >= params.min_filtered_sample_size {
463                // We've reached our target; no need to add more.
464                break;
465            }
466            if self.active_filter.permits(&candidate.owned_target) {
467                n_filtered_usable += 1;
468            }
469            current_weight += weight;
470            self.add_guard(candidate, now, params);
471            any_added = true;
472        }
473        self.assert_consistency();
474        any_added
475    }
476
477    /// Add `relay` as a new guard.
478    ///
479    /// Does nothing if it is already a guard, or if there is an existing guard
480    /// with any of the same ID keys.
481    fn add_guard(&mut self, relay: Candidate, now: SystemTime, params: &GuardParams) {
482        let id = GuardId::from_relay_ids(&relay.owned_target);
483        if self.guards.contains_any_overlapping(&id) {
484            return;
485        }
486        debug!(guard_id=?id, "Adding guard to sample.");
487        // TODO: I don't think onionperf actually needs the guard fingerpint,
488        // but if it does, add it here.
489        trace!(
490            onionperf = true,
491            event = ?OnionperfEvent::Guard(OnionperfGuardStatus::New),
492            guard_id = ?id,
493        );
494        let guard = Guard::from_candidate(relay, now, params);
495        self.guards.insert(guard);
496        self.sample.push(id);
497        self.primary_guards_invalidated = true;
498    }
499
500    /// Return the number of our primary guards that are missing directory
501    /// information in `universe`.
502    ///
503    /// Note that "missing directory information" is not the same as "absent":
504    /// in this case, we  are counting the primary guards where we cannot tell
505    /// whether they appear in the universe or not because we have not yet
506    /// downloaded their descriptors.
507    pub(crate) fn n_primary_without_id_info_in<U: Universe>(&mut self, universe: &U) -> usize {
508        self.primary
509            .iter()
510            .filter(|id| {
511                let g = self
512                    .guards
513                    .by_all_ids(*id)
514                    .expect("Inconsistent guard state");
515                g.listed_in(universe).is_none()
516            })
517            .count()
518    }
519
520    /// Update the status of every guard  in this sample from a given source.
521    pub(crate) fn update_status_from_dir<U: Universe>(&mut self, dir: &U) {
522        let old_guards = std::mem::take(&mut self.guards);
523        self.guards = old_guards
524            .into_values()
525            .map(|mut guard| {
526                guard.update_from_universe(dir);
527                guard
528            })
529            .collect();
530        // Call "fix consistency", in case any guards got a new ID.
531        self.fix_consistency();
532    }
533
534    /// Re-build the list of primary guards.
535    ///
536    /// Primary guards are chosen according to preference order over all
537    /// the guards in the set, restricted by the current filter.
538    ///
539    /// TODO: Enumerate all the times when this function needs to be called.
540    ///
541    /// TODO: Make sure this is called enough.
542    pub(crate) fn select_primary_guards(&mut self, params: &GuardParams) {
543        // TODO-SPEC: This is not 100% what the spec says, but it does match what
544        // Tor does.  We pick first from the confirmed guards,
545        // then from any previous primary guards, and then from maybe-reachable
546        // guards in the sample.
547
548        // Only for logging.
549        let old_primary = self.primary.clone();
550
551        self.primary = self
552            // First, we look at the confirmed guards.
553            .confirmed
554            .iter()
555            // Then we consider existing primary guards.
556            .chain(self.primary.iter())
557            // Finally, we look at the rest of the sample for guards not marked
558            // as "unreachable".
559            .chain(self.reachable_sample_ids())
560            // We only consider each guard the first time it appears.
561            .unique()
562            // We only consider usable guards that the filter allows.
563            .filter_map(|id| {
564                let g = self
565                    .guards
566                    .by_all_ids(id)
567                    .expect("Inconsistent guard state");
568                if g.usable() && self.active_filter.permits(g) {
569                    Some(id.clone())
570                } else {
571                    None
572                }
573            })
574            // The first n_primary guards on that list are primary!
575            .take(params.n_primary)
576            .collect();
577
578        if self.primary != old_primary {
579            debug!(old=?old_primary, new=?self.primary, "Updated primary guards.");
580        }
581
582        // Clear exploratory_circ_pending for all primary guards.
583        for id in &self.primary {
584            self.guards.modify_by_all_ids(id, |guard| {
585                guard.note_exploratory_circ(false);
586            });
587        }
588
589        // TODO: Recalculate retry times, perhaps, since we may have changed
590        // the timeouts?
591
592        self.assert_consistency();
593        self.primary_guards_invalidated = false;
594    }
595
596    /// Remove all guards which should expire `now`, according to the settings
597    /// in `params`.
598    pub(crate) fn expire_old_guards(&mut self, params: &GuardParams, now: SystemTime) {
599        self.assert_consistency();
600        let n_pre = self.guards.len();
601        // TODO: Might be more ideal to do this after the assert_consistency.
602        for guard in self.guards.values() {
603            if guard.is_expired(params, now) {
604                tracing::trace!(
605                    onionperf = true,
606                    event = ?OnionperfEvent::Guard(OnionperfGuardStatus::Dropped),
607                    guard_id = ?guard.guard_id(),
608                );
609            }
610        }
611        self.guards.retain(|g| !g.is_expired(params, now));
612        let guards = &self.guards;
613        self.sample.retain(|id| guards.by_all_ids(id).is_some());
614        self.confirmed.retain(|id| guards.by_all_ids(id).is_some());
615        self.primary.retain(|id| guards.by_all_ids(id).is_some());
616        self.assert_consistency();
617
618        if self.guards.len() < n_pre {
619            let n_expired = n_pre - self.guards.len();
620            debug!(n_expired, "Expired guards as too old.");
621            self.primary_guards_invalidated = true;
622        }
623    }
624
625    /// Return an iterator over the Id for every Guard in the sample that
626    /// is not known to be Unreachable.
627    fn reachable_sample_ids(&self) -> impl Iterator<Item = &GuardId> {
628        self.sample.iter().filter(move |id| {
629            let g = self
630                .guards
631                .by_all_ids(*id)
632                .expect("Inconsistent guard state");
633            g.reachable() != Reachable::Unreachable
634        })
635    }
636
637    /// Return an iterator that yields an element for every guard in
638    /// this set, in preference order.
639    ///
640    /// Each element contains a `ListKind` that describes which list the
641    /// guard was in, and a `&GuardId` that identifies the guard.
642    ///
643    /// Note that this function will return guards that are not
644    /// accepted by the current active filter: the caller must apply
645    /// that filter if appropriate.
646    fn preference_order_ids(&self) -> impl Iterator<Item = (ListKind, &GuardId)> {
647        self.primary
648            .iter()
649            .map(|id| (ListKind::Primary, id))
650            .chain(self.confirmed.iter().map(|id| (ListKind::Confirmed, id)))
651            .chain(self.sample.iter().map(|id| (ListKind::Sample, id)))
652            .unique_by(|(_, id)| *id)
653    }
654
655    /// Like `preference_order_ids`, but yields `&Guard` instead of `&GuardId`.
656    fn preference_order(&self) -> impl Iterator<Item = (ListKind, &Guard)> + '_ {
657        self.preference_order_ids()
658            .filter_map(move |(p, id)| self.guards.by_all_ids(id).map(|g| (p, g)))
659    }
660
661    /// Return true if `guard_id` is an identity subset for any primary guard in this set.
662    fn guard_is_primary(&self, guard_id: &GuardId) -> bool {
663        // (This could be yes/no/maybe.)
664
665        // This is O(n), but the list is short.
666        self.primary
667            .iter()
668            .any(|p| p.has_all_relay_ids_from(guard_id))
669    }
670
671    /// For every guard that has been marked as `Unreachable` for too long,
672    /// mark it as `Unknown`.
673    pub(crate) fn consider_all_retries(&mut self, now: Instant) {
674        let old_guards = std::mem::take(&mut self.guards);
675        self.guards = old_guards
676            .into_values()
677            .map(|mut guard| {
678                guard.consider_retry(now);
679                guard
680            })
681            .collect();
682    }
683
684    /// Return the earliest time at which any guard will be retriable.
685    pub(crate) fn next_retry(&self, usage: &GuardUsage) -> Option<Instant> {
686        self.guards
687            .values()
688            .filter_map(|g| g.next_retry(usage))
689            .min()
690    }
691
692    /// Mark every `Unreachable` primary guard as `Unknown`.
693    pub(crate) fn mark_primary_guards_retriable(&mut self) {
694        for id in &self.primary {
695            self.guards
696                .modify_by_all_ids(id, |guard| guard.mark_retriable());
697        }
698    }
699
700    /// Return true if all of our primary guards are currently marked
701    /// unreachable.
702    pub(crate) fn all_primary_guards_are_unreachable(&mut self) -> bool {
703        self.primary
704            .iter()
705            .flat_map(|id| self.guards.by_all_ids(id))
706            .all(|g| g.reachable() == Reachable::Unreachable)
707    }
708
709    /// Mark every `Unreachable` guard as `Unknown`.
710    pub(crate) fn mark_all_guards_retriable(&mut self) {
711        let old_guards = std::mem::take(&mut self.guards);
712        self.guards = old_guards
713            .into_values()
714            .map(|mut guard| {
715                guard.mark_retriable();
716                guard
717            })
718            .collect();
719    }
720
721    /// Record that an attempt has begun to use the guard with
722    /// `guard_id`.
723    pub(crate) fn record_attempt(&mut self, guard_id: &GuardId, now: Instant) {
724        let is_primary = self.guard_is_primary(guard_id);
725        self.guards.modify_by_all_ids(guard_id, |guard| {
726            guard.record_attempt(now);
727
728            if !is_primary {
729                guard.note_exploratory_circ(true);
730            }
731        });
732    }
733
734    /// Record that an attempt to use the guard with `guard_id` has just
735    /// succeeded.
736    ///
737    /// If `how` is provided, it's an operation from outside the crate that the
738    /// guard succeeded at doing.
739    pub(crate) fn record_success(
740        &mut self,
741        guard_id: &GuardId,
742        params: &GuardParams,
743        how: Option<ExternalActivity>,
744        now: SystemTime,
745    ) {
746        self.assert_consistency();
747        self.guards.modify_by_all_ids(guard_id, |guard| match how {
748            Some(external) => guard.record_external_success(external),
749            None => {
750                let newly_confirmed = guard.record_success(now, params);
751
752                if newly_confirmed == NewlyConfirmed::Yes {
753                    self.confirmed.push(guard_id.clone());
754                    self.primary_guards_invalidated = true;
755                }
756            }
757        });
758        self.assert_consistency();
759    }
760
761    /// Record that an attempt to use the guard with `guard_id` has just failed.
762    ///
763    pub(crate) fn record_failure(
764        &mut self,
765        guard_id: &GuardId,
766        how: Option<ExternalActivity>,
767        now: Instant,
768    ) {
769        trace!(
770            onionperf = true,
771            event = ?OnionperfEvent::Guard(OnionperfGuardStatus::Down),
772            ?guard_id,
773        );
774        // TODO use instant uniformly for in-process, and systemtime for storage?
775        let is_primary = self.guard_is_primary(guard_id);
776        self.guards.modify_by_all_ids(guard_id, |guard| match how {
777            Some(external) => guard.record_external_failure(external, now),
778            None => guard.record_failure(now, is_primary),
779        });
780    }
781
782    /// Record that an attempt to use the guard with `guard_id` has
783    /// just been abandoned, without learning whether it succeeded or failed.
784    pub(crate) fn record_attempt_abandoned(&mut self, guard_id: &GuardId) {
785        self.guards
786            .modify_by_all_ids(guard_id, |guard| guard.note_exploratory_circ(false));
787    }
788
789    /// Record that an attempt to use the guard with `guard_id` has
790    /// just failed in a way that we could not definitively attribute to
791    /// the guard.
792    pub(crate) fn record_indeterminate_result(&mut self, guard_id: &GuardId) {
793        self.guards.modify_by_all_ids(guard_id, |guard| {
794            guard.note_exploratory_circ(false);
795            guard.record_indeterminate_result();
796        });
797    }
798
799    /// Record that a given guard has told us about clock skew.
800    pub(crate) fn record_skew(&mut self, guard_id: &GuardId, observation: SkewObservation) {
801        self.guards
802            .modify_by_all_ids(guard_id, |guard| guard.note_skew(observation));
803    }
804
805    /// Return an iterator over all stored clock skew observations.
806    pub(crate) fn skew_observations(&self) -> impl Iterator<Item = &SkewObservation> {
807        self.guards.values().filter_map(|g| g.skew())
808    }
809
810    /// Return whether the circuit manager can be allowed to use a
811    /// circuit with the `guard_id`.
812    ///
813    /// Return `Some(bool)` if the circuit is usable, and `None` if we
814    /// cannot yet be sure.
815    pub(crate) fn circ_usability_status(
816        &self,
817        guard_id: &GuardId,
818        usage: &GuardUsage,
819        params: &GuardParams,
820        now: Instant,
821    ) -> Option<bool> {
822        // TODO-SPEC: This isn't what the spec says.  The spec is phrased
823        // in terms of circuits blocking circuits, whereas this algorithm is
824        // about guards blocking guards.
825        //
826        // Also notably, the spec also says:
827        //
828        // * Among guards that do not appear in {CONFIRMED_GUARDS},
829        // {is_pending}==true guards have higher priority.
830        // * Among those, the guard with earlier {last_tried_connect} time
831        // has higher priority.
832        // * Finally, among guards that do not appear in
833        // {CONFIRMED_GUARDS} with {is_pending==false}, all have equal
834        // priority.
835        //
836        // I believe this approach is fine too, but we ought to document it.
837
838        if self.guard_is_primary(guard_id) {
839            // Circuits built to primary guards are always usable immediately.
840            //
841            // This has to be a special case, since earlier primary guards
842            // don't block later ones.
843            return Some(true);
844        }
845
846        // Assuming that the guard is _not_ primary, then the rule is
847        // fairly simple: we can use the guard if all the guards we'd
848        // _rather_ use are either down, or have had their circuit
849        // attempts pending for too long.
850
851        // We treat a more-preferred guard with an exploratory circuit created
852        // _after_ this cutoff as preventing us from using `guard_id`.
853        let cutoff = now.saturating_sub(params.np_connect_timeout);
854
855        for (src, guard) in self.preference_order() {
856            if guard.guard_id() == guard_id {
857                return Some(true);
858            }
859            if guard.usable() && self.active_filter.permits(guard) && guard.conforms_to_usage(usage)
860            {
861                match (src, guard.reachable()) {
862                    (_, Reachable::Reachable) => return Some(false),
863                    (_, Reachable::Unreachable) => (),
864                    (ListKind::Primary, Reachable::Untried | Reachable::Retriable) => {
865                        return Some(false);
866                    }
867                    (_, Reachable::Untried | Reachable::Retriable) => {
868                        if guard.exploratory_attempt_after(cutoff) {
869                            return None;
870                        }
871                    }
872                }
873            }
874        }
875
876        // This guard is not even listed.
877        Some(false)
878    }
879
880    /// Try to select a guard for a given `usage`.
881    ///
882    /// On success, returns the kind of guard that we got, and its filtered
883    /// representation in a form suitable for use as a first hop.
884    ///
885    /// Label the returned guard as having come from `sample_id`.
886    //
887    // NOTE (nickm): I wish that we didn't have to take sample_id as an input,
888    // but the alternative would be storing it as a member of `GuardSet`, which
889    // makes things very complicated.
890    pub(crate) fn pick_guard(
891        &self,
892        sample_id: &GuardSetSelector,
893        usage: &GuardUsage,
894        params: &GuardParams,
895        now: Instant,
896    ) -> Result<(ListKind, FirstHop), PickGuardError> {
897        let (list_kind, id) = self.pick_guard_id(usage, params, now)?;
898        let first_hop = self
899            .get(&id)
900            .expect("Somehow selected a guard we don't know!")
901            .get_external_rep(sample_id.clone());
902        let first_hop = self.active_filter.modify_hop(first_hop)?;
903
904        Ok((list_kind, first_hop))
905    }
906
907    /// Try to select a guard for a given `usage`.
908    ///
909    /// On success, returns the kind of guard that we got, and its identity.
910    fn pick_guard_id(
911        &self,
912        usage: &GuardUsage,
913        params: &GuardParams,
914        now: Instant,
915    ) -> Result<(ListKind, GuardId), PickGuardError> {
916        debug_assert!(!self.primary_guards_invalidated);
917        let n_options = match usage.kind {
918            GuardUsageKind::OneHopDirectory => params.dir_parallelism,
919            GuardUsageKind::Data => params.data_parallelism,
920        };
921
922        // Counts of how many elements were rejected by which of the filters
923        // below.
924        //
925        // Note that since we use `Iterator::take`, these counts won't cover the
926        // whole guard sample on the successful case: only in the failing case,
927        // when we fail to find any candidates.
928        let mut running = FilterCount::default();
929        let mut pending = FilterCount::default();
930        let mut suitable = FilterCount::default();
931        let mut filtered = FilterCount::default();
932
933        let mut options: Vec<_> = self
934            .preference_order()
935            // Discard the guards that are down or unusable, and see if any
936            // are left.
937            .filter_cnt(&mut running, |(_, g)| {
938                g.usable()
939                    && g.reachable() != Reachable::Unreachable
940                    && g.ready_for_usage(usage, now)
941            })
942            // Now remove those that are excluded because we're already trying
943            // them on an exploratory basis.
944            .filter_cnt(&mut pending, |(_, g)| !g.exploratory_circ_pending())
945            // ...or because they don't support the operation we're
946            // attempting...
947            .filter_cnt(&mut suitable, |(_, g)| g.conforms_to_usage(usage))
948            // ... or because we specifically filtered them out.
949            .filter_cnt(&mut filtered, |(_, g)| self.active_filter.permits(*g))
950            // We only consider the first n_options such guards.
951            .take(n_options)
952            .collect();
953
954        if options.iter().any(|(src, _)| src.is_primary()) {
955            // If there are any primary guards, we only consider those.
956            options.retain(|(src, _)| src.is_primary());
957        } else {
958            // If there are no primary guards, parallelism doesn't apply.
959            options.truncate(1);
960        }
961
962        match options.choose(&mut rand::rng()) {
963            Some((src, g)) => Ok((*src, g.guard_id().clone())),
964            None => {
965                let retry_at = if running.n_accepted == 0 {
966                    self.next_retry(usage)
967                } else {
968                    None
969                };
970                Err(PickGuardError::AllGuardsDown {
971                    retry_at,
972                    running,
973                    pending,
974                    suitable,
975                    filtered,
976                })
977            }
978        }
979    }
980
981    /// Return the guards whose bridge descriptors we should request, given our
982    /// current configuration and status.
983    ///
984    /// (The output of this function is not reasonable unless this is a Bridge
985    /// sample.)
986    #[cfg(feature = "bridge-client")]
987    pub(crate) fn descriptors_to_request(&self, now: Instant, params: &GuardParams) -> Vec<&Guard> {
988        /// This constant is here to improve our odds that we can get a working
989        /// bridge if we have any per-circuit filters that would prevent us from
990        /// using our preferred bridge.
991        const MINIMUM: usize = 2;
992
993        let maximum = std::cmp::max(params.data_parallelism, MINIMUM);
994        let data_usage = GuardUsage::default();
995
996        // Here we duplicate some but not all of the restrictions above in
997        // pick_guard_id.  We skip those restrictions that are specific to only
998        // certain kinds of circuits, and those that are temporary restrictions
999        // encouraging us to try more guards.
1000        //
1001        // TODO: we may want to refactor this code and the code in pick_guard_id
1002        // above to share a single function.  Before we do that, however, I want
1003        // to experiment with this logic a bit to make sure that it works and
1004        // doesn't give us surprising results.
1005        self.preference_order()
1006            .filter(|(_, g)| {
1007                g.usable()
1008                    && g.reachable() != Reachable::Unreachable
1009                    && g.ready_for_usage(&data_usage, now)
1010                    && self.active_filter.permits(*g)
1011            })
1012            .take(maximum)
1013            .map(|(_, g)| g)
1014            .collect()
1015    }
1016}
1017
1018use serde::Serializer;
1019use tor_persist::JsonValue;
1020
1021/// State object used to serialize and deserialize a [`GuardSet`].
1022#[derive(Default, Debug, Clone, Serialize, Deserialize)]
1023pub(crate) struct GuardSample<'a> {
1024    /// Equivalent to `GuardSet.guards.values()`, except in sample order.
1025    guards: Vec<Cow<'a, Guard>>,
1026    /// The identities for the confirmed members of `guards`, in confirmed order.
1027    confirmed: Cow<'a, [GuardId]>,
1028    /// Other data from the state file that this version of Arti doesn't recognize.
1029    #[serde(flatten)]
1030    remaining: HashMap<String, JsonValue>,
1031}
1032
1033impl Serialize for GuardSet {
1034    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
1035    where
1036        S: Serializer,
1037    {
1038        GuardSample::from(self).serialize(serializer)
1039    }
1040}
1041
1042impl<'a> From<&'a GuardSet> for GuardSample<'a> {
1043    fn from(guards: &'a GuardSet) -> Self {
1044        guards.get_state()
1045    }
1046}
1047
1048impl<'a> From<GuardSample<'a>> for GuardSet {
1049    fn from(sample: GuardSample) -> Self {
1050        GuardSet::from_state(sample)
1051    }
1052}
1053
1054#[cfg(test)]
1055mod test {
1056    // @@ begin test lint list maintained by maint/add_warning @@
1057    #![allow(clippy::bool_assert_comparison)]
1058    #![allow(clippy::clone_on_copy)]
1059    #![allow(clippy::dbg_macro)]
1060    #![allow(clippy::mixed_attributes_style)]
1061    #![allow(clippy::print_stderr)]
1062    #![allow(clippy::print_stdout)]
1063    #![allow(clippy::single_char_pattern)]
1064    #![allow(clippy::unwrap_used)]
1065    #![allow(clippy::unchecked_time_subtraction)]
1066    #![allow(clippy::useless_vec)]
1067    #![allow(clippy::needless_pass_by_value)]
1068    #![allow(clippy::string_slice)] // See arti#2571
1069    //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
1070    use tor_linkspec::{HasRelayIds, RelayIdType};
1071    use tor_netdir::NetDir;
1072    use tor_netdoc::doc::netstatus::RelayBandwidth;
1073    use tor_netdoc::types::relay_flags::RelayFlag;
1074    use web_time_compat::{InstantExt, SystemTimeExt};
1075
1076    use super::*;
1077    use crate::FirstHopId;
1078    use std::time::Duration;
1079
1080    fn netdir() -> NetDir {
1081        use tor_netdir::testnet;
1082        testnet::construct_netdir().unwrap_if_sufficient().unwrap()
1083    }
1084
1085    #[test]
1086    fn sample_test() {
1087        // Make a test network that gives every relay equal weight, and which
1088        // has 20 viable (Guard + V2Dir + DirCache=2) candidates.  Otherwise the
1089        // calculation of collision probability at the end of this function is
1090        // too tricky.
1091        let netdir = tor_netdir::testnet::construct_custom_netdir(|idx, builder, _| {
1092            // Give every node equal bandwidth.
1093            builder.rs.weight(RelayBandwidth::Measured(1000));
1094            // The default network has 40 relays, and the first 10 are
1095            // not Guard by default.
1096            if idx >= 10 {
1097                builder.rs.add_flags(RelayFlag::Guard);
1098                if idx >= 20 {
1099                    builder.rs.protos("DirCache=2".parse().unwrap());
1100                } else {
1101                    builder.rs.protos("".parse().unwrap());
1102                }
1103            }
1104        })
1105        .unwrap()
1106        .unwrap_if_sufficient()
1107        .unwrap();
1108        // Make sure that we got the numbers we expected.
1109        assert_eq!(40, netdir.relays().count());
1110        assert_eq!(
1111            30,
1112            netdir
1113                .relays()
1114                .filter(|r| r.low_level_details().is_suitable_as_guard())
1115                .count()
1116        );
1117        assert_eq!(
1118            20,
1119            netdir
1120                .relays()
1121                .filter(|r| r.low_level_details().is_suitable_as_guard()
1122                    && r.low_level_details().is_dir_cache())
1123                .count()
1124        );
1125
1126        let params = GuardParams {
1127            min_filtered_sample_size: 5,
1128            max_sample_bw_fraction: 1.0,
1129            ..GuardParams::default()
1130        };
1131
1132        let mut samples: Vec<HashSet<GuardId>> = Vec::new();
1133        for _ in 0..3 {
1134            let mut guards = GuardSet::default();
1135            guards.extend_sample_as_needed(SystemTime::get(), &params, &netdir);
1136            assert_eq!(guards.guards.len(), params.min_filtered_sample_size);
1137            assert_eq!(guards.confirmed.len(), 0);
1138            assert_eq!(guards.primary.len(), 0);
1139            guards.assert_consistency();
1140
1141            // make sure all the guards are okay.
1142            for guard in guards.guards.values() {
1143                let id = FirstHopId::in_sample(GuardSetSelector::Default, guard.guard_id().clone());
1144                let relay = id.get_relay(&netdir).unwrap();
1145                assert!(relay.low_level_details().is_suitable_as_guard());
1146                assert!(relay.low_level_details().is_dir_cache());
1147                assert!(guards.guards.by_all_ids(&relay).is_some());
1148                {
1149                    assert!(!guard.is_expired(&params, SystemTime::get()));
1150                }
1151            }
1152
1153            // Make sure that the sample doesn't expand any further.
1154            guards.extend_sample_as_needed(SystemTime::get(), &params, &netdir);
1155            assert_eq!(guards.guards.len(), params.min_filtered_sample_size);
1156            guards.assert_consistency();
1157
1158            samples.push(guards.sample.into_iter().collect());
1159        }
1160
1161        // The probability of getting the same sample 3 times in a row is (20 choose 5)^-2,
1162        // which is pretty low.  (About 1 in 240 million.)
1163        assert!(samples[0] != samples[1] || samples[1] != samples[2]);
1164    }
1165
1166    #[test]
1167    fn persistence() {
1168        let netdir = netdir();
1169        let params = GuardParams {
1170            min_filtered_sample_size: 5,
1171            ..GuardParams::default()
1172        };
1173
1174        let t1 = SystemTime::get();
1175        let t2 = t1 + Duration::from_secs(20);
1176
1177        let mut guards = GuardSet::default();
1178        guards.extend_sample_as_needed(t1, &params, &netdir);
1179
1180        // Pick a guard and mark it as confirmed.
1181        let id1 = guards.sample[0].clone();
1182        guards.record_success(&id1, &params, None, t2);
1183        assert_eq!(&guards.confirmed, std::slice::from_ref(&id1));
1184
1185        // Encode the guards, then decode them.
1186        let state: GuardSample = (&guards).into();
1187        let guards2: GuardSet = state.into();
1188
1189        assert_eq!(&guards2.sample, &guards.sample);
1190        assert_eq!(&guards2.confirmed, &guards.confirmed);
1191        assert_eq!(&guards2.confirmed, &[id1]);
1192        assert_eq!(
1193            guards
1194                .guards
1195                .values()
1196                .map(Guard::guard_id)
1197                .collect::<HashSet<_>>(),
1198            guards2
1199                .guards
1200                .values()
1201                .map(Guard::guard_id)
1202                .collect::<HashSet<_>>()
1203        );
1204        for g in guards.guards.values() {
1205            let g2 = guards2.guards.by_all_ids(g.guard_id()).unwrap();
1206            assert_eq!(format!("{:?}", g), format!("{:?}", g2));
1207        }
1208    }
1209
1210    #[test]
1211    fn select_primary() {
1212        let netdir = netdir();
1213        let params = GuardParams {
1214            min_filtered_sample_size: 5,
1215            n_primary: 4,
1216            ..GuardParams::default()
1217        };
1218        let t1 = SystemTime::get();
1219        let t2 = t1 + Duration::from_secs(20);
1220        let t3 = t2 + Duration::from_secs(30);
1221
1222        let mut guards = GuardSet::default();
1223        guards.extend_sample_as_needed(t1, &params, &netdir);
1224
1225        // Pick a guard and mark it as confirmed.
1226        let id3 = guards.sample[3].clone();
1227        guards.record_success(&id3, &params, None, t2);
1228        assert_eq!(&guards.confirmed, std::slice::from_ref(&id3));
1229        let id1 = guards.sample[1].clone();
1230        guards.record_success(&id1, &params, None, t3);
1231        assert_eq!(&guards.confirmed, &[id3.clone(), id1.clone()]);
1232
1233        // Select primary guards and make sure we're obeying the rules.
1234        guards.select_primary_guards(&params);
1235        assert_eq!(guards.primary.len(), 4);
1236        assert_eq!(&guards.primary[0], &id3);
1237        assert_eq!(&guards.primary[1], &id1);
1238        let p3 = guards.primary[2].clone();
1239        let p4 = guards.primary[3].clone();
1240        assert_eq!(
1241            [id1.clone(), id3.clone(), p3.clone(), p4.clone()]
1242                .iter()
1243                .unique()
1244                .count(),
1245            4
1246        );
1247
1248        // Mark another guard as confirmed and see that the list changes to put
1249        // that guard right after the previously confirmed guards, but we keep
1250        // one of the previous unconfirmed primary guards.
1251        guards.record_success(&p4, &params, None, t3);
1252        assert_eq!(&guards.confirmed, &[id3.clone(), id1.clone(), p4.clone()]);
1253        guards.select_primary_guards(&params);
1254        assert_eq!(guards.primary.len(), 4);
1255        assert_eq!(&guards.primary[0], &id3);
1256        assert_eq!(&guards.primary[1], &id1);
1257        assert_eq!(&guards.primary, &[id3, id1, p4, p3]);
1258    }
1259
1260    #[test]
1261    fn expiration() {
1262        let netdir = netdir();
1263        let params = GuardParams::default();
1264        let t1 = SystemTime::get();
1265
1266        let mut guards = GuardSet::default();
1267        guards.extend_sample_as_needed(t1, &params, &netdir);
1268        // note that there are only 10 Guard+V2Dir nodes in the netdir().
1269        assert_eq!(guards.sample.len(), 10);
1270
1271        // Mark one guard as confirmed; it will have a different timeout.
1272        // Pick a guard and mark it as confirmed.
1273        let id1 = guards.sample[0].clone();
1274        guards.record_success(&id1, &params, None, t1);
1275        assert_eq!(&guards.confirmed, &[id1]);
1276
1277        let one_day = Duration::from_secs(86400);
1278        guards.expire_old_guards(&params, t1 + one_day * 30);
1279        assert_eq!(guards.sample.len(), 10); // nothing has expired.
1280
1281        // This is long enough to make sure that the confirmed guard has expired.
1282        guards.expire_old_guards(&params, t1 + one_day * 70);
1283        assert_eq!(guards.sample.len(), 9);
1284
1285        guards.expire_old_guards(&params, t1 + one_day * 200);
1286        assert_eq!(guards.sample.len(), 0);
1287    }
1288
1289    #[test]
1290    fn sampling_and_usage() {
1291        let netdir = netdir();
1292        let params = GuardParams {
1293            min_filtered_sample_size: 5,
1294            n_primary: 2,
1295            ..GuardParams::default()
1296        };
1297        let st1 = SystemTime::get();
1298        let i1 = Instant::get();
1299        let sec = Duration::from_secs(1);
1300
1301        let mut guards = GuardSet::default();
1302        guards.extend_sample_as_needed(st1, &params, &netdir);
1303        guards.select_primary_guards(&params);
1304
1305        // First guard: try it, and let it fail.
1306        let usage = crate::GuardUsageBuilder::default().build().unwrap();
1307        let id1 = guards.primary[0].clone();
1308        let id2 = guards.primary[1].clone();
1309        let (src, id) = guards.pick_guard_id(&usage, &params, i1).unwrap();
1310        assert_eq!(src, ListKind::Primary);
1311        assert_eq!(&id, &id1);
1312
1313        guards.record_attempt(&id, i1);
1314        guards.record_failure(&id, None, i1 + sec);
1315
1316        // Second guard: try it, and try it again, and have it fail.
1317        let (src, id) = guards.pick_guard_id(&usage, &params, i1 + sec).unwrap();
1318        assert_eq!(src, ListKind::Primary);
1319        assert_eq!(&id, &id2);
1320        guards.record_attempt(&id, i1 + sec);
1321
1322        let (src, id_x) = guards.pick_guard_id(&usage, &params, i1 + sec).unwrap();
1323        // We get the same guard this (second) time that we pick it too, since
1324        // it is a primary guard, and is_pending won't block it.
1325        assert_eq!(id_x, id);
1326        assert_eq!(src, ListKind::Primary);
1327        guards.record_attempt(&id_x, i1 + sec * 2);
1328        guards.record_failure(&id_x, None, i1 + sec * 3);
1329        guards.record_failure(&id, None, i1 + sec * 4);
1330
1331        // Third guard: this one won't be primary.
1332        let (src, id3) = guards.pick_guard_id(&usage, &params, i1 + sec * 4).unwrap();
1333        assert_eq!(src, ListKind::Sample);
1334        assert!(!guards.primary.contains(&id3));
1335        guards.record_attempt(&id3, i1 + sec * 5);
1336
1337        // Fourth guard: Third guard will be pending, so a different one gets
1338        // handed out here.
1339        let (src, id4) = guards.pick_guard_id(&usage, &params, i1 + sec * 5).unwrap();
1340        assert_eq!(src, ListKind::Sample);
1341        assert!(id3 != id4);
1342        assert!(!guards.primary.contains(&id4));
1343        guards.record_attempt(&id4, i1 + sec * 6);
1344
1345        // Look at usability status: primary guards should be usable
1346        // immediately; third guard should be too (since primary
1347        // guards are down).  Fourth should not have a known status,
1348        // since third is pending.
1349        assert_eq!(
1350            guards.circ_usability_status(&id1, &usage, &params, i1 + sec * 6),
1351            Some(true)
1352        );
1353        assert_eq!(
1354            guards.circ_usability_status(&id2, &usage, &params, i1 + sec * 6),
1355            Some(true)
1356        );
1357        assert_eq!(
1358            guards.circ_usability_status(&id3, &usage, &params, i1 + sec * 6),
1359            Some(true)
1360        );
1361        assert_eq!(
1362            guards.circ_usability_status(&id4, &usage, &params, i1 + sec * 6),
1363            None
1364        );
1365
1366        // Have both guards succeed.
1367        guards.record_success(&id3, &params, None, st1 + sec * 7);
1368        guards.record_success(&id4, &params, None, st1 + sec * 8);
1369
1370        // Check the impact of having both guards succeed.
1371        assert!(guards.primary_guards_invalidated);
1372        guards.select_primary_guards(&params);
1373        assert_eq!(&guards.primary, &[id3.clone(), id4.clone()]);
1374
1375        // Next time we ask for a guard, we get a primary guard again.
1376        let (src, id) = guards
1377            .pick_guard_id(&usage, &params, i1 + sec * 10)
1378            .unwrap();
1379        assert_eq!(src, ListKind::Primary);
1380        assert_eq!(&id, &id3);
1381
1382        // If we ask for a directory guard, we get one of the primaries.
1383        let mut found = HashSet::new();
1384        let usage = crate::GuardUsageBuilder::default()
1385            .kind(crate::GuardUsageKind::OneHopDirectory)
1386            .build()
1387            .unwrap();
1388        for _ in 0..64 {
1389            let (src, id) = guards
1390                .pick_guard_id(&usage, &params, i1 + sec * 10)
1391                .unwrap();
1392            assert_eq!(src, ListKind::Primary);
1393            assert_eq!(
1394                guards.circ_usability_status(&id, &usage, &params, i1 + sec * 10),
1395                Some(true)
1396            );
1397            guards.record_attempt_abandoned(&id);
1398            found.insert(id);
1399        }
1400        assert!(found.len() == 2);
1401        assert!(found.contains(&id3));
1402        assert!(found.contains(&id4));
1403
1404        // Since the primaries are now up, other guards are not usable.
1405        assert_eq!(
1406            guards.circ_usability_status(&id1, &usage, &params, i1 + sec * 12),
1407            Some(false)
1408        );
1409        assert_eq!(
1410            guards.circ_usability_status(&id2, &usage, &params, i1 + sec * 12),
1411            Some(false)
1412        );
1413    }
1414
1415    #[test]
1416    fn everybodys_down() {
1417        let netdir = netdir();
1418        let params = GuardParams {
1419            min_filtered_sample_size: 5,
1420            n_primary: 2,
1421            max_sample_bw_fraction: 1.0,
1422            ..GuardParams::default()
1423        };
1424        let mut st = SystemTime::get();
1425        let mut inst = Instant::get();
1426        let sec = Duration::from_secs(1);
1427        let usage = crate::GuardUsageBuilder::default().build().unwrap();
1428
1429        let mut guards = GuardSet::default();
1430
1431        guards.extend_sample_as_needed(st, &params, &netdir);
1432        guards.select_primary_guards(&params);
1433
1434        assert_eq!(guards.sample.len(), 5);
1435        for _ in 0..5 {
1436            let (_, id) = guards.pick_guard_id(&usage, &params, inst).unwrap();
1437            guards.record_attempt(&id, inst);
1438            guards.record_failure(&id, None, inst + sec);
1439
1440            inst += sec * 2;
1441            st += sec * 2;
1442        }
1443
1444        let e = guards.pick_guard_id(&usage, &params, inst);
1445        assert!(matches!(e, Err(PickGuardError::AllGuardsDown { .. })));
1446
1447        // Now in theory we should re-grow when we extend.
1448        guards.extend_sample_as_needed(st, &params, &netdir);
1449        guards.select_primary_guards(&params);
1450        assert_eq!(guards.sample.len(), 10);
1451    }
1452
1453    #[test]
1454    fn retry_primary() {
1455        let netdir = netdir();
1456        let params = GuardParams {
1457            min_filtered_sample_size: 5,
1458            n_primary: 2,
1459            max_sample_bw_fraction: 1.0,
1460            ..GuardParams::default()
1461        };
1462        let usage = crate::GuardUsageBuilder::default().build().unwrap();
1463
1464        let mut guards = GuardSet::default();
1465
1466        guards.extend_sample_as_needed(SystemTime::get(), &params, &netdir);
1467        guards.select_primary_guards(&params);
1468
1469        assert_eq!(guards.primary.len(), 2);
1470        assert!(!guards.all_primary_guards_are_unreachable());
1471
1472        // Let one primary guard fail.
1473        let (kind, p_id1) = guards
1474            .pick_guard_id(&usage, &params, Instant::get())
1475            .unwrap();
1476        assert_eq!(kind, ListKind::Primary);
1477        guards.record_failure(&p_id1, None, Instant::get());
1478        assert!(!guards.all_primary_guards_are_unreachable());
1479
1480        // Now let the other one fail.
1481        let (kind, p_id2) = guards
1482            .pick_guard_id(&usage, &params, Instant::get())
1483            .unwrap();
1484        assert_eq!(kind, ListKind::Primary);
1485        guards.record_failure(&p_id2, None, Instant::get());
1486        assert!(guards.all_primary_guards_are_unreachable());
1487
1488        // Now mark the guards retriable.
1489        guards.mark_primary_guards_retriable();
1490        assert!(!guards.all_primary_guards_are_unreachable());
1491        let (kind, p_id3) = guards
1492            .pick_guard_id(&usage, &params, Instant::get())
1493            .unwrap();
1494        assert_eq!(kind, ListKind::Primary);
1495        assert_eq!(p_id3, p_id1);
1496    }
1497
1498    #[test]
1499    fn count_missing_mds() {
1500        let netdir = netdir();
1501        let params = GuardParams {
1502            min_filtered_sample_size: 5,
1503            n_primary: 2,
1504            max_sample_bw_fraction: 1.0,
1505            ..GuardParams::default()
1506        };
1507        let usage = crate::GuardUsageBuilder::default().build().unwrap();
1508        let mut guards = GuardSet::default();
1509        guards.extend_sample_as_needed(SystemTime::get(), &params, &netdir);
1510        guards.select_primary_guards(&params);
1511        assert_eq!(guards.primary.len(), 2);
1512
1513        let (_kind, p_id1) = guards
1514            .pick_guard_id(&usage, &params, Instant::get())
1515            .unwrap();
1516        guards.record_success(&p_id1, &params, None, SystemTime::get());
1517        assert_eq!(guards.n_primary_without_id_info_in(&netdir), 0);
1518
1519        use tor_netdir::testnet;
1520        let netdir2 = testnet::construct_custom_netdir(|_idx, bld, _| {
1521            let md_so_far = bld.md.testing_md().expect("Couldn't build md?");
1522            if &p_id1.0.identity(RelayIdType::Ed25519).unwrap() == md_so_far.ed25519_id() {
1523                bld.omit_md = true;
1524            }
1525        })
1526        .unwrap()
1527        .unwrap_if_sufficient()
1528        .unwrap();
1529
1530        assert_eq!(guards.n_primary_without_id_info_in(&netdir2), 1);
1531    }
1532
1533    #[test]
1534    fn copy_status() {
1535        let netdir = netdir();
1536        let params = GuardParams {
1537            min_filtered_sample_size: 5,
1538            n_primary: 2,
1539            max_sample_bw_fraction: 1.0,
1540            ..GuardParams::default()
1541        };
1542        let mut guards1 = GuardSet::default();
1543        guards1.extend_sample_as_needed(SystemTime::get(), &params, &netdir);
1544        guards1.select_primary_guards(&params);
1545        let mut guards2 = guards1.clone();
1546
1547        // Make a persistent change in guards1, and a different persistent change in guards2.
1548        let id1 = guards1.primary[0].clone();
1549        let id2 = guards1.primary[1].clone();
1550        guards1.record_success(&id1, &params, None, SystemTime::get());
1551        guards2.record_success(&id2, &params, None, SystemTime::get());
1552        // Make a non-persistent change in guards2.
1553        guards2.record_failure(&id2, None, Instant::get());
1554
1555        // Copy status: make sure non-persistent status changed, and  persistent didn't.
1556        guards1.copy_ephemeral_status_into_newly_loaded_state(guards2);
1557        {
1558            let g1 = guards1.get(&id1).unwrap();
1559            let g2 = guards1.get(&id2).unwrap();
1560            assert!(g1.confirmed());
1561            assert!(!g2.confirmed());
1562            assert_eq!(g1.reachable(), Reachable::Untried);
1563            assert_eq!(g2.reachable(), Reachable::Unreachable);
1564        }
1565
1566        // Now make a new set of unrelated guards, and make sure that copying
1567        // from it doesn't change the membership of guards1.
1568        let mut guards3 = GuardSet::default();
1569        let g1_set: HashSet<_> = guards1
1570            .guards
1571            .values()
1572            .map(|g| g.guard_id().clone())
1573            .collect();
1574        let mut g3_set: HashSet<_> = HashSet::new();
1575        for _ in 0..4 {
1576            // There is roughly a 1-in-5000 chance of getting the same set
1577            // twice, so we loop until that doesn't happen.
1578            guards3.extend_sample_as_needed(SystemTime::get(), &params, &netdir);
1579            guards3.select_primary_guards(&params);
1580            g3_set = guards3
1581                .guards
1582                .values()
1583                .map(|g| g.guard_id().clone())
1584                .collect();
1585
1586            // There is roughly a 1-in-5000 chance of getting the same set twice, so
1587            if g1_set == g3_set {
1588                guards3 = GuardSet::default();
1589                continue;
1590            }
1591            break;
1592        }
1593        assert_ne!(g1_set, g3_set);
1594        // Do the copy; make sure that the membership is unchanged.
1595        guards1.copy_ephemeral_status_into_newly_loaded_state(guards3);
1596        let g1_set_new: HashSet<_> = guards1
1597            .guards
1598            .values()
1599            .map(|g| g.guard_id().clone())
1600            .collect();
1601        assert_eq!(g1_set, g1_set_new);
1602    }
1603
1604    #[test]
1605    // This is far easier to test with bridge-client support.
1606    #[cfg(feature = "bridge-client")]
1607    fn partial_identity_collision() {
1608        use crate::bridge::BridgeSet;
1609        use std::sync::Arc;
1610        // Construct a configuration with 2 bridges whose IDs overlap partially:
1611        // Same RSA, but different Ed25519.
1612        let bc = Arc::new([
1613            "192.168.0.1:80 $0bac39417268b69b9f514e7f63fa6fba1a788958
1614             ed25519:S2Fya2F0ICBXaGF0ICBJcyAgSGUgIERvaW5nIEhlcmU"
1615                .parse()
1616                .unwrap(),
1617            "192.168.0.2:80 $0bac39417268b69b9f514e7f63fa6fba1a788958
1618             ed25519:dGhpcyBpcyBbpmNyZWRpYmx5IHNpbGx5ISEhISEhISA"
1619                .parse()
1620                .unwrap(),
1621        ]);
1622        let bs = BridgeSet::new(bc, None);
1623        // Here we rely on GuardSet not filtering out anything by default, and
1624        // on GuardParamas having a max_sample_size >=2.
1625        // Otherwise the test won't actually check for correct behavior here.
1626        let mut gs = GuardSet::default();
1627        let params = GuardParams::default();
1628        assert!(params.max_sample_size >= 2);
1629        assert_eq!(gs.active_filter, GuardFilter::unfiltered());
1630        gs.extend_sample_as_needed(SystemTime::get(), &params, &bs);
1631        gs.assert_consistency();
1632    }
1633}