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    //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
200
201    use super::*;
202    use rand::Rng;
203    use tor_basic_utils::test_rng::testing_rng;
204    use web_time_compat::InstantExt;
205
206    /// Construct a `FallbackDir` with random identity keys and addresses.
207    ///
208    /// Since there are 416 bits of random id here, the risk of collision is
209    /// negligible.
210    fn rand_fb<R: Rng>(rng: &mut R) -> FallbackDir {
211        let ed: [u8; 32] = rng.random();
212        let rsa: [u8; 20] = rng.random();
213        let ip: u32 = rng.random();
214        let mut bld = FallbackDir::builder();
215        bld.ed_identity(ed.into())
216            .rsa_identity(rsa.into())
217            .orports()
218            .push(std::net::SocketAddrV4::new(ip.into(), 9090).into());
219        bld.build().unwrap()
220    }
221
222    #[test]
223    fn construct_fallback_set() {
224        use rand::seq::SliceRandom;
225        use std::cmp::Ordering as O;
226
227        // fabricate some fallbacks.
228        let mut rng = testing_rng();
229        let fbs = vec![
230            rand_fb(&mut rng),
231            rand_fb(&mut rng),
232            rand_fb(&mut rng),
233            rand_fb(&mut rng),
234        ];
235        let fb_other = rand_fb(&mut rng);
236        let id_other = FallbackId::from_relay_ids(&fb_other);
237
238        // basic case: construct a set
239        let list: FallbackList = fbs.clone().into();
240        assert!(!list.is_empty());
241        assert_eq!(list.len(), 4);
242        let mut set: FallbackState = (&list).into();
243
244        // inspect the generated set
245        assert_eq!(set.fallbacks.len(), 4);
246        assert_eq!(
247            set.fallbacks[0].cmp_by_relay_ids(&set.fallbacks[1]),
248            O::Less
249        );
250        assert_eq!(
251            set.fallbacks[1].cmp_by_relay_ids(&set.fallbacks[2]),
252            O::Less
253        );
254        assert_eq!(
255            set.fallbacks[2].cmp_by_relay_ids(&set.fallbacks[3]),
256            O::Less
257        );
258
259        // use the constructed set a little.
260        for fb in fbs.iter() {
261            let id = FallbackId::from_relay_ids(fb);
262            assert_eq!(set.get_mut(&id).unwrap().cmp_by_relay_ids(&id), O::Equal);
263        }
264        assert!(set.get_mut(&id_other).is_none());
265
266        // Now try an input set with duplicates.
267        let mut redundant_fbs = fbs.clone();
268        redundant_fbs.extend(fbs.clone());
269        redundant_fbs.extend(fbs[0..2].iter().map(Clone::clone));
270        redundant_fbs[..].shuffle(&mut testing_rng());
271        let list2 = redundant_fbs.into();
272        assert_ne!(&list, &list2);
273        let set2: FallbackState = (&list2).into();
274
275        // It should have the same elements, in the same order.
276        assert_eq!(set.fallbacks.len(), set2.fallbacks.len());
277        assert!(
278            set.fallbacks
279                .iter()
280                .zip(set2.fallbacks.iter())
281                .all(|(ent1, ent2)| ent1.same_relay_ids(ent2))
282        );
283    }
284
285    #[test]
286    fn set_choose() {
287        dbg!("X");
288
289        let mut rng = testing_rng();
290        let fbs = vec![
291            rand_fb(&mut rng),
292            rand_fb(&mut rng),
293            rand_fb(&mut rng),
294            rand_fb(&mut rng),
295        ];
296        let list: FallbackList = fbs.into();
297        let mut set: FallbackState = (&list).into();
298        let filter = crate::GuardFilter::unfiltered();
299
300        let mut counts = [0_usize; 4];
301        let now = Instant::get();
302        dbg!("A");
303        fn lookup_idx(set: &FallbackState, id: &impl HasRelayIds) -> Option<usize> {
304            set.fallbacks
305                .binary_search_by(|ent| ent.fallback.cmp_by_relay_ids(id))
306                .ok()
307        }
308        // Basic case: everybody is up.
309        for _ in 0..100 {
310            let fb = set.choose(&mut rng, now, &filter).unwrap();
311            let idx = lookup_idx(&set, fb).unwrap();
312            counts[idx] += 1;
313        }
314        dbg!("B");
315        assert!(counts.iter().all(|v| *v > 0));
316
317        // Mark somebody down and make sure they don't get chosen.
318        let ids: Vec<_> = set
319            .fallbacks
320            .iter()
321            .map(|ent| FallbackId::from_relay_ids(&ent.fallback))
322            .collect();
323        set.note_failure(&ids[2], now);
324        counts = [0; 4];
325        for _ in 0..100 {
326            let fb = set.choose(&mut rng, now, &filter).unwrap();
327            let idx = lookup_idx(&set, fb).unwrap();
328            counts[idx] += 1;
329        }
330        assert_eq!(counts.iter().filter(|v| **v > 0).count(), 3);
331        assert_eq!(counts[2], 0);
332
333        // Mark everybody down; make sure we get the right error.
334        for id in ids.iter() {
335            set.note_failure(id, now);
336        }
337        assert!(matches!(
338            set.choose(&mut rng, now, &filter),
339            Err(PickGuardError::AllFallbacksDown { .. })
340        ));
341
342        // Construct an empty set; make sure we get the right error.
343        let empty_set = FallbackState::from(&FallbackList::from(vec![]));
344        assert!(matches!(
345            empty_set.choose(&mut rng, now, &filter),
346            Err(PickGuardError::NoCandidatesAvailable)
347        ));
348
349        // TODO: test restrictions and filters once they're implemented.
350    }
351
352    #[test]
353    fn test_status() {
354        let mut rng = testing_rng();
355        let fbs = vec![
356            rand_fb(&mut rng),
357            rand_fb(&mut rng),
358            rand_fb(&mut rng),
359            rand_fb(&mut rng),
360        ];
361        let list: FallbackList = fbs.clone().into();
362        let mut set: FallbackState = (&list).into();
363        let ids: Vec<_> = set
364            .fallbacks
365            .iter()
366            .map(|ent| FallbackId::from_relay_ids(&ent.fallback))
367            .collect();
368
369        let now = Instant::get();
370
371        // There's no "next retry time" when everybody's up.
372        assert!(set.next_retry().is_none());
373
374        // Mark somebody down; try accessors.
375        set.note_failure(&ids[3], now);
376        assert!(set.fallbacks[3].status.next_retriable().unwrap() > now);
377        assert!(!set.fallbacks[3].status.usable_at(now));
378        assert_eq!(set.next_retry(), set.fallbacks[3].status.next_retriable());
379
380        // Mark somebody else down; try accessors.
381        set.note_failure(&ids[0], now);
382        assert!(set.fallbacks[0].status.next_retriable().unwrap() > now);
383        assert!(!set.fallbacks[0].status.usable_at(now));
384        assert_eq!(
385            set.next_retry().unwrap(),
386            std::cmp::min(
387                set.fallbacks[0].status.next_retriable().unwrap(),
388                set.fallbacks[3].status.next_retriable().unwrap()
389            )
390        );
391
392        // Mark somebody as running; try accessors.
393        set.note_success(&ids[0]);
394        assert!(set.fallbacks[0].status.next_retriable().is_none());
395        assert!(set.fallbacks[0].status.usable_at(now));
396
397        // Make a new set with slightly different members; make sure that we can copy stuff successfully.
398        let mut fbs2: Vec<_> = fbs
399            .into_iter()
400            // (Remove the fallback with id==ids[2])
401            .filter(|fb| FallbackId::from_relay_ids(fb) != ids[2])
402            .collect();
403        // add 2 new ones.
404        let fbs_new = vec![rand_fb(&mut rng), rand_fb(&mut rng), rand_fb(&mut rng)];
405        fbs2.extend(fbs_new.clone());
406
407        let mut set2 = FallbackState::from(&FallbackList::from(fbs2.clone()));
408        set2.take_status_from(set); // consumes set.
409        assert_eq!(set2.fallbacks.len(), 6); // Started with 4, added 3, removed 1.
410
411        // Make sure that the status entries  are correctly copied.
412        assert!(set2.get_mut(&ids[0]).unwrap().status.usable_at(now));
413        assert!(set2.get_mut(&ids[1]).unwrap().status.usable_at(now));
414        assert!(set2.get_mut(&ids[2]).is_none());
415        assert!(!set2.get_mut(&ids[3]).unwrap().status.usable_at(now));
416
417        // Make sure that the new fbs are there.
418        for new_fb in fbs_new {
419            assert!(
420                set2.get_mut(&FallbackId::from_relay_ids(&new_fb))
421                    .unwrap()
422                    .status
423                    .usable_at(now)
424            );
425        }
426    }
427}
tor_guardmgr/fallback.rs

tor_guardmgr/
fallback.rs
