tor_guardmgr/
fallback.rs

1//! Data structures that wrap [`FallbackDir`] and related primitives into
2//! data structures required for bootstrapping Tor properly.
3//!
4//! These data structures primiarily carry some internal state that only gets
5//! observed during bootstrap.
6
7use crate::{dirstatus::DirStatus, skew::SkewObservation};
8use rand::seq::IteratorRandom;
9use tor_dircommon::fallback::{FallbackDir, FallbackList};
10use tor_linkspec::HasRelayIds;
11use web_time_compat::{Duration, Instant};
12
13use crate::{PickGuardError, ids::FallbackId};
14use tor_basic_utils::iter::{FilterCount, IteratorExt as _};
15
16/// A set of fallback directories, in usable form.
17#[derive(Debug, Clone)]
18pub(crate) struct FallbackState {
19    /// The list of fallbacks in the set.
20    ///
21    /// We require that these are sorted and unique by (ED,RSA) keys.
22    fallbacks: Vec<Entry>,
23}
24
25/// Wrapper type for FallbackDir converted into crate::Guard, and the status
26/// information that we store about it.
27///
28/// Defines a sort order to ensure that we can look up fallback directories by
29/// binary search on keys.
30#[derive(Debug, Clone)]
31pub(super) struct Entry {
32    /// The inner fallback directory.
33    fallback: FallbackDir,
34
35    /// Whether the directory is currently usable, and if not, when we can retry
36    /// it.
37    status: DirStatus,
38    /// The latest clock skew observation we have from this fallback directory
39    /// (if any).
40    clock_skew: Option<SkewObservation>,
41}
42
43/// Least amount of time we'll wait before retrying a fallback cache.
44//
45// TODO: we may want to make this configurable to a smaller value for chutney networks.
46const FALLBACK_RETRY_FLOOR: Duration = Duration::from_secs(150);
47
48impl From<FallbackDir> for Entry {
49    fn from(fallback: FallbackDir) -> Self {
50        let status = DirStatus::new(FALLBACK_RETRY_FLOOR);
51        Entry {
52            fallback,
53            status,
54            clock_skew: None,
55        }
56    }
57}
58
59impl HasRelayIds for Entry {
60    fn identity(
61        &self,
62        key_type: tor_linkspec::RelayIdType,
63    ) -> Option<tor_linkspec::RelayIdRef<'_>> {
64        self.fallback.identity(key_type)
65    }
66}
67
68impl From<&FallbackList> for FallbackState {
69    fn from(list: &FallbackList) -> Self {
70        let mut fallbacks: Vec<Entry> = list.iter().map(|fb| fb.clone().into()).collect();
71        fallbacks.sort_by(|x, y| x.cmp_by_relay_ids(y));
72        fallbacks.dedup_by(|x, y| x.same_relay_ids(y));
73        FallbackState { fallbacks }
74    }
75}
76
77impl FallbackState {
78    /// Return a random member of this FallbackSet that's usable at `now`.
79    pub(crate) fn choose<R: rand::Rng>(
80        &self,
81        rng: &mut R,
82        now: Instant,
83        filter: &crate::GuardFilter,
84    ) -> Result<&FallbackDir, PickGuardError> {
85        if self.fallbacks.is_empty() {
86            return Err(PickGuardError::NoCandidatesAvailable);
87        }
88
89        let mut running = FilterCount::default();
90        let mut filtered = FilterCount::default();
91
92        self.fallbacks
93            .iter()
94            .filter_cnt(&mut running, |ent| ent.status.usable_at(now))
95            .filter_cnt(&mut filtered, |ent| filter.permits(&ent.fallback))
96            .choose(rng)
97            .map(|ent| &ent.fallback)
98            .ok_or_else(|| PickGuardError::AllFallbacksDown {
99                retry_at: self.next_retry(),
100                running,
101                filtered,
102            })
103    }
104
105    /// Return the next time at which any member of this set will become ready.
106    ///
107    /// Returns None if no elements are failing.
108    fn next_retry(&self) -> Option<Instant> {
109        self.fallbacks
110            .iter()
111            .filter_map(|ent| ent.status.next_retriable())
112            .min()
113    }
114
115    /// Return a reference to the entry whose identity is `id`, if there is one.
116    fn get(&self, id: &FallbackId) -> Option<&Entry> {
117        match self.fallbacks.binary_search_by(|e| e.cmp_by_relay_ids(id)) {
118            Ok(idx) => Some(&self.fallbacks[idx]),
119            Err(_) => None,
120        }
121    }
122
123    /// Return a mutable reference to the entry whose identity is `id`, if there is one.
124    fn get_mut(&mut self, id: &FallbackId) -> Option<&mut Entry> {
125        match self.fallbacks.binary_search_by(|e| e.cmp_by_relay_ids(id)) {
126            Ok(idx) => Some(&mut self.fallbacks[idx]),
127            Err(_) => None,
128        }
129    }
130
131    /// Return true if this set contains some entry with the given `id`.
132    pub(crate) fn contains(&self, id: &FallbackId) -> bool {
133        self.get(id).is_some()
134    }
135
136    /// Record that a success has occurred for the fallback with the given
137    /// identity.
138    ///
139    /// Be aware that for fallbacks, we only count a successful directory
140    /// operation as a success: a circuit success is not enough.
141    pub(crate) fn note_success(&mut self, id: &FallbackId) {
142        if let Some(entry) = self.get_mut(id) {
143            entry.status.note_success();
144        }
145    }
146
147    /// Record that a failure has occurred for the fallback with the given
148    /// identity.
149    pub(crate) fn note_failure(&mut self, id: &FallbackId, now: Instant) {
150        if let Some(entry) = self.get_mut(id) {
151            entry.status.note_failure(now);
152        }
153    }
154
155    /// Consume `other` and copy all of its fallback status entries into the corresponding entries for `self`.
156    pub(crate) fn take_status_from(&mut self, other: FallbackState) {
157        use itertools::EitherOrBoth::Both;
158
159        itertools::merge_join_by(self.fallbacks.iter_mut(), other.fallbacks, |a, b| {
160            a.fallback.cmp_by_relay_ids(&b.fallback)
161        })
162        .for_each(|entry| {
163            if let Both(entry, other) = entry {
164                debug_assert!(entry.fallback.same_relay_ids(&other.fallback));
165                entry.status = other.status;
166            }
167        });
168    }
169
170    /// Record that a given fallback has told us about clock skew.
171    pub(crate) fn note_skew(&mut self, id: &FallbackId, observation: SkewObservation) {
172        if let Some(entry) = self.get_mut(id) {
173            entry.clock_skew = Some(observation);
174        }
175    }
176
177    /// Return an iterator over all the clock skew observations we've made for fallback directories
178    pub(crate) fn skew_observations(&self) -> impl Iterator<Item = &SkewObservation> {
179        self.fallbacks
180            .iter()
181            .filter_map(|fb| fb.clock_skew.as_ref())
182    }
183}
184
185#[cfg(test)]
186mod test {
187    // @@ begin test lint list maintained by maint/add_warning @@
188    #![allow(clippy::bool_assert_comparison)]
189    #![allow(clippy::clone_on_copy)]
190    #![allow(clippy::dbg_macro)]
191    #![allow(clippy::mixed_attributes_style)]
192    #![allow(clippy::print_stderr)]
193    #![allow(clippy::print_stdout)]
194    #![allow(clippy::single_char_pattern)]
195    #![allow(clippy::unwrap_used)]
196    #![allow(clippy::unchecked_time_subtraction)]
197    #![allow(clippy::useless_vec)]
198    #![allow(clippy::needless_pass_by_value)]
199    #![allow(clippy::string_slice)] // See arti#2571
200    //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
201
202    use super::*;
203    use rand::{Rng, RngExt};
204    use tor_basic_utils::test_rng::testing_rng;
205    use web_time_compat::InstantExt;
206
207    /// Construct a `FallbackDir` with random identity keys and addresses.
208    ///
209    /// Since there are 416 bits of random id here, the risk of collision is
210    /// negligible.
211    fn rand_fb<R: Rng>(rng: &mut R) -> FallbackDir {
212        let ed: [u8; 32] = rng.random();
213        let rsa: [u8; 20] = rng.random();
214        let ip: u32 = rng.random();
215        let mut bld = FallbackDir::builder();
216        bld.ed_identity(ed.into())
217            .rsa_identity(rsa.into())
218            .orports()
219            .push(std::net::SocketAddrV4::new(ip.into(), 9090).into());
220        bld.build().unwrap()
221    }
222
223    #[test]
224    fn construct_fallback_set() {
225        use rand::seq::SliceRandom;
226        use std::cmp::Ordering as O;
227
228        // fabricate some fallbacks.
229        let mut rng = testing_rng();
230        let fbs = vec![
231            rand_fb(&mut rng),
232            rand_fb(&mut rng),
233            rand_fb(&mut rng),
234            rand_fb(&mut rng),
235        ];
236        let fb_other = rand_fb(&mut rng);
237        let id_other = FallbackId::from_relay_ids(&fb_other);
238
239        // basic case: construct a set
240        let list: FallbackList = fbs.clone().into();
241        assert!(!list.is_empty());
242        assert_eq!(list.len(), 4);
243        let mut set: FallbackState = (&list).into();
244
245        // inspect the generated set
246        assert_eq!(set.fallbacks.len(), 4);
247        assert_eq!(
248            set.fallbacks[0].cmp_by_relay_ids(&set.fallbacks[1]),
249            O::Less
250        );
251        assert_eq!(
252            set.fallbacks[1].cmp_by_relay_ids(&set.fallbacks[2]),
253            O::Less
254        );
255        assert_eq!(
256            set.fallbacks[2].cmp_by_relay_ids(&set.fallbacks[3]),
257            O::Less
258        );
259
260        // use the constructed set a little.
261        for fb in fbs.iter() {
262            let id = FallbackId::from_relay_ids(fb);
263            assert_eq!(set.get_mut(&id).unwrap().cmp_by_relay_ids(&id), O::Equal);
264        }
265        assert!(set.get_mut(&id_other).is_none());
266
267        // Now try an input set with duplicates.
268        let mut redundant_fbs = fbs.clone();
269        redundant_fbs.extend(fbs.clone());
270        redundant_fbs.extend(fbs[0..2].iter().map(Clone::clone));
271        redundant_fbs[..].shuffle(&mut testing_rng());
272        let list2 = redundant_fbs.into();
273        assert_ne!(&list, &list2);
274        let set2: FallbackState = (&list2).into();
275
276        // It should have the same elements, in the same order.
277        assert_eq!(set.fallbacks.len(), set2.fallbacks.len());
278        assert!(
279            set.fallbacks
280                .iter()
281                .zip(set2.fallbacks.iter())
282                .all(|(ent1, ent2)| ent1.same_relay_ids(ent2))
283        );
284    }
285
286    #[test]
287    fn set_choose() {
288        dbg!("X");
289
290        let mut rng = testing_rng();
291        let fbs = vec![
292            rand_fb(&mut rng),
293            rand_fb(&mut rng),
294            rand_fb(&mut rng),
295            rand_fb(&mut rng),
296        ];
297        let list: FallbackList = fbs.into();
298        let mut set: FallbackState = (&list).into();
299        let filter = crate::GuardFilter::unfiltered();
300
301        let mut counts = [0_usize; 4];
302        let now = Instant::get();
303        dbg!("A");
304        fn lookup_idx(set: &FallbackState, id: &impl HasRelayIds) -> Option<usize> {
305            set.fallbacks
306                .binary_search_by(|ent| ent.fallback.cmp_by_relay_ids(id))
307                .ok()
308        }
309        // Basic case: everybody is up.
310        for _ in 0..100 {
311            let fb = set.choose(&mut rng, now, &filter).unwrap();
312            let idx = lookup_idx(&set, fb).unwrap();
313            counts[idx] += 1;
314        }
315        dbg!("B");
316        assert!(counts.iter().all(|v| *v > 0));
317
318        // Mark somebody down and make sure they don't get chosen.
319        let ids: Vec<_> = set
320            .fallbacks
321            .iter()
322            .map(|ent| FallbackId::from_relay_ids(&ent.fallback))
323            .collect();
324        set.note_failure(&ids[2], now);
325        counts = [0; 4];
326        for _ in 0..100 {
327            let fb = set.choose(&mut rng, now, &filter).unwrap();
328            let idx = lookup_idx(&set, fb).unwrap();
329            counts[idx] += 1;
330        }
331        assert_eq!(counts.iter().filter(|v| **v > 0).count(), 3);
332        assert_eq!(counts[2], 0);
333
334        // Mark everybody down; make sure we get the right error.
335        for id in ids.iter() {
336            set.note_failure(id, now);
337        }
338        assert!(matches!(
339            set.choose(&mut rng, now, &filter),
340            Err(PickGuardError::AllFallbacksDown { .. })
341        ));
342
343        // Construct an empty set; make sure we get the right error.
344        let empty_set = FallbackState::from(&FallbackList::from(vec![]));
345        assert!(matches!(
346            empty_set.choose(&mut rng, now, &filter),
347            Err(PickGuardError::NoCandidatesAvailable)
348        ));
349
350        // TODO: test restrictions and filters once they're implemented.
351    }
352
353    #[test]
354    fn test_status() {
355        let mut rng = testing_rng();
356        let fbs = vec![
357            rand_fb(&mut rng),
358            rand_fb(&mut rng),
359            rand_fb(&mut rng),
360            rand_fb(&mut rng),
361        ];
362        let list: FallbackList = fbs.clone().into();
363        let mut set: FallbackState = (&list).into();
364        let ids: Vec<_> = set
365            .fallbacks
366            .iter()
367            .map(|ent| FallbackId::from_relay_ids(&ent.fallback))
368            .collect();
369
370        let now = Instant::get();
371
372        // There's no "next retry time" when everybody's up.
373        assert!(set.next_retry().is_none());
374
375        // Mark somebody down; try accessors.
376        set.note_failure(&ids[3], now);
377        assert!(set.fallbacks[3].status.next_retriable().unwrap() > now);
378        assert!(!set.fallbacks[3].status.usable_at(now));
379        assert_eq!(set.next_retry(), set.fallbacks[3].status.next_retriable());
380
381        // Mark somebody else down; try accessors.
382        set.note_failure(&ids[0], now);
383        assert!(set.fallbacks[0].status.next_retriable().unwrap() > now);
384        assert!(!set.fallbacks[0].status.usable_at(now));
385        assert_eq!(
386            set.next_retry().unwrap(),
387            std::cmp::min(
388                set.fallbacks[0].status.next_retriable().unwrap(),
389                set.fallbacks[3].status.next_retriable().unwrap()
390            )
391        );
392
393        // Mark somebody as running; try accessors.
394        set.note_success(&ids[0]);
395        assert!(set.fallbacks[0].status.next_retriable().is_none());
396        assert!(set.fallbacks[0].status.usable_at(now));
397
398        // Make a new set with slightly different members; make sure that we can copy stuff successfully.
399        let mut fbs2: Vec<_> = fbs
400            .into_iter()
401            // (Remove the fallback with id==ids[2])
402            .filter(|fb| FallbackId::from_relay_ids(fb) != ids[2])
403            .collect();
404        // add 2 new ones.
405        let fbs_new = vec![rand_fb(&mut rng), rand_fb(&mut rng), rand_fb(&mut rng)];
406        fbs2.extend(fbs_new.clone());
407
408        let mut set2 = FallbackState::from(&FallbackList::from(fbs2.clone()));
409        set2.take_status_from(set); // consumes set.
410        assert_eq!(set2.fallbacks.len(), 6); // Started with 4, added 3, removed 1.
411
412        // Make sure that the status entries  are correctly copied.
413        assert!(set2.get_mut(&ids[0]).unwrap().status.usable_at(now));
414        assert!(set2.get_mut(&ids[1]).unwrap().status.usable_at(now));
415        assert!(set2.get_mut(&ids[2]).is_none());
416        assert!(!set2.get_mut(&ids[3]).unwrap().status.usable_at(now));
417
418        // Make sure that the new fbs are there.
419        for new_fb in fbs_new {
420            assert!(
421                set2.get_mut(&FallbackId::from_relay_ids(&new_fb))
422                    .unwrap()
423                    .status
424                    .usable_at(now)
425            );
426        }
427    }
428}
tor_guardmgr/fallback.rs

tor_guardmgr/
fallback.rs
