1
//! Code for estimating good values for circuit timeouts.
2
//!
3
//! We need good circuit timeouts for two reasons: first, they help
4
//! user experience.  If user wait too long for their circuits, or if
5
//! they use exceptionally slow circuits, then Tor will feel really
6
//! slow.  Second, these timeouts are actually a security
7
//! property.
8
// TODO(nickm): explain why!
9

            
10
use std::time::Duration;
11

            
12
pub(crate) mod estimator;
13
pub(crate) mod pareto;
14
pub(crate) mod readonly;
15

            
16
pub(crate) use estimator::Estimator;
17

            
18
/// An object that calculates circuit timeout thresholds from the history
19
/// of circuit build times.
20
pub(crate) trait TimeoutEstimator {
21
    /// Record that a given circuit hop has completed.
22
    ///
23
    /// The `hop` number is a zero-indexed value for which hop just completed.
24
    ///
25
    /// The `delay` value is the amount of time after we first launched the
26
    /// circuit.
27
    ///
28
    /// If this is the last hop of the circuit, then `is_last` is true.
29
    fn note_hop_completed(&mut self, hop: u8, delay: Duration, is_last: bool);
30

            
31
    /// Record that a circuit failed to complete because it took too long.
32
    ///
33
    /// The `hop` number is a the number of hops that were successfully
34
    /// completed.
35
    ///
36
    /// The `delay` number is the amount of time after we first launched the
37
    /// circuit.
38
    fn note_circ_timeout(&mut self, hop: u8, delay: Duration);
39

            
40
    /// Return the current estimation for how long we should wait for a given
41
    /// [`Action`] to complete.
42
    ///
43
    /// This function should return a 2-tuple of `(timeout, abandon)`
44
    /// durations.  After `timeout` has elapsed since circuit launch,
45
    /// the circuit should no longer be used, but we should still keep
46
    /// building it in order see how long it takes.  After `abandon`
47
    /// has elapsed since circuit launch, the circuit should be
48
    /// abandoned completely.
49
    fn timeouts(&mut self, action: &Action) -> (Duration, Duration);
50

            
51
    /// Return true if we're currently trying to learn more timeouts
52
    /// by launching testing circuits.
53
    fn learning_timeouts(&self) -> bool;
54

            
55
    /// Replace the network parameters used by this estimator (if any)
56
    /// with ones derived from `params`.
57
    fn update_params(&mut self, params: &tor_netdir::params::NetParameters);
58

            
59
    /// Construct a new ParetoTimeoutState to represent the current state
60
    /// of this estimator, if it is possible to store the state to disk.
61
    ///
62
    /// TODO: change the type used for the state.
63
    fn build_state(&mut self) -> Option<pareto::ParetoTimeoutState>;
64
}
65

            
66
/// A possible action for which we can try to estimate a timeout.
67
#[non_exhaustive]
68
#[derive(Copy, Clone, Debug, Eq, PartialEq)]
69
pub enum Action {
70
    /// Build a circuit of a given length.
71
    BuildCircuit {
72
        /// The length of the circuit to construct.
73
        ///
74
        /// (A 0-hop circuit takes no time.)
75
        length: usize,
76
    },
77
    /// Extend a given circuit from one length to another.
78
    ExtendCircuit {
79
        /// The current length of the circuit.
80
        initial_length: usize,
81
        /// The new length of the circuit.
82
        ///
83
        /// (Should typically be greater than `initial_length`; otherwise we
84
        /// estimate a zero timeout.)
85
        final_length: usize,
86
    },
87
    /// Send a message to the last hop of a circuit and receive a response
88
    RoundTrip {
89
        /// The length of the circuit.
90
        length: usize,
91
    },
92
}
93

            
94
impl Action {
95
    /// Compute a scaling factor for a given `Action`
96
    ///
97
    /// These values are arbitrary numbers such that if the correct
98
    /// timeout for an Action `a1` is `t`, then the correct timeout
99
    /// for an action `a2` is `t * a2.timeout_scale() /
100
    /// a1.timeout_scale()`.
101
    ///
102
    /// This function can return garbage if the circuit length is larger
103
    /// than actually supported on the Tor network.
104
136
    fn timeout_scale(&self) -> usize {
105
        /// An arbitrary value to use to prevent overflow.
106
        const MAX_LEN: usize = 64;
107

            
108
        /// Return the scale value for building a `len`-hop circuit.
109
138
        fn build_scale(len: usize) -> usize {
110
138
            len * (len + 1) / 2
111
138
        }
112
        // This is based on an approximation from Tor's
113
        // `circuit_expire_building()` code.
114
        //
115
        // The general principle here is that when you're waiting for
116
        // a round-trip through a circuit through three relays
117
        // 'a--b--c', it takes three units of time.  Thus, building a
118
        // three hop circuit requires you to send a message through
119
        // "a", then through "a--b", then through "a--b--c", for a
120
        // total of 6.
121
        //
122
        // This is documented in path-spec.txt under "Calculating
123
        // timeouts thresholds for circuits of different lengths".
124
136
        match *self {
125
130
            Action::BuildCircuit { length } => {
126
130
                // We never down-scale our estimates for building a circuit
127
130
                // below a 3-hop length.
128
130
                //
129
130
                // TODO: This is undocumented.
130
130
                let length = length.clamp(3, MAX_LEN);
131
130
                build_scale(length)
132
            }
133
            Action::ExtendCircuit {
134
4
                initial_length,
135
4
                final_length,
136
4
            } => {
137
4
                let initial_length = initial_length.clamp(0, MAX_LEN);
138
4
                let final_length = final_length.clamp(initial_length, MAX_LEN);
139
4
                build_scale(final_length) - build_scale(initial_length)
140
            }
141
2
            Action::RoundTrip { length } => length.clamp(0, MAX_LEN),
142
        }
143
136
    }
144
}
145

            
146
/// A safe variant of [`Duration::mul_f64`] that never panics.
147
///
148
/// For infinite or NaN or negative multipliers, the results might be
149
/// nonsensical, but at least they won't be a panic.
150
90
fn mul_duration_f64_saturating(d: Duration, mul: f64) -> Duration {
151
90
    let secs = d.as_secs_f64() * mul;
152
90
    // At this point I'd like to use Duration::try_from_secs_f64, but
153
90
    // that isn't stable yet. :p
154
90
    if secs.is_finite() && secs >= 0.0 {
155
        // We rely on the property that `f64 as uNN` is saturating.
156
82
        let seconds = secs.trunc() as u64;
157
82
        let nanos = if seconds == u64::MAX {
158
2
            0 // prevent any possible overflow.
159
        } else {
160
80
            (secs.fract() * 1e9) as u32
161
        };
162
82
        Duration::new(seconds, nanos)
163
    } else {
164
8
        Duration::from_secs(1)
165
    }
166
90
}
167

            
168
#[cfg(test)]
169
mod test {
170
    // @@ begin test lint list maintained by maint/add_warning @@
171
    #![allow(clippy::bool_assert_comparison)]
172
    #![allow(clippy::clone_on_copy)]
173
    #![allow(clippy::dbg_macro)]
174
    #![allow(clippy::mixed_attributes_style)]
175
    #![allow(clippy::print_stderr)]
176
    #![allow(clippy::print_stdout)]
177
    #![allow(clippy::single_char_pattern)]
178
    #![allow(clippy::unwrap_used)]
179
    #![allow(clippy::unchecked_duration_subtraction)]
180
    #![allow(clippy::useless_vec)]
181
    #![allow(clippy::needless_pass_by_value)]
182
    //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
183
    use super::*;
184

            
185
    #[test]
186
    fn action_scale_values() {
187
        assert_eq!(Action::BuildCircuit { length: 1 }.timeout_scale(), 6);
188
        assert_eq!(Action::BuildCircuit { length: 2 }.timeout_scale(), 6);
189
        assert_eq!(Action::BuildCircuit { length: 3 }.timeout_scale(), 6);
190
        assert_eq!(Action::BuildCircuit { length: 4 }.timeout_scale(), 10);
191
        assert_eq!(Action::BuildCircuit { length: 5 }.timeout_scale(), 15);
192

            
193
        assert_eq!(
194
            Action::ExtendCircuit {
195
                initial_length: 3,
196
                final_length: 4
197
            }
198
            .timeout_scale(),
199
            4
200
        );
201
        assert_eq!(
202
            Action::ExtendCircuit {
203
                initial_length: 99,
204
                final_length: 4
205
            }
206
            .timeout_scale(),
207
            0
208
        );
209

            
210
        assert_eq!(Action::RoundTrip { length: 3 }.timeout_scale(), 3);
211
    }
212

            
213
    #[test]
214
    fn test_mul_duration() {
215
        // This is wrong because of leap years, but we'll fake it.
216
        let mega_year = Duration::from_secs(86400 * 365 * 1000 * 1000);
217

            
218
        // Multiply by zero.
219
        let v = mul_duration_f64_saturating(mega_year, 0.0);
220
        assert!(v.is_zero());
221

            
222
        // Multiply by one.
223
        assert_eq!(mul_duration_f64_saturating(mega_year, 1.0), mega_year);
224

            
225
        // Divide by 1000.
226
        let v = mul_duration_f64_saturating(mega_year, 1.0 / 1000.0);
227
        let s = v.as_secs_f64();
228
        assert!((s - (mega_year.as_secs_f64() / 1000.0)).abs() < 0.1);
229

            
230
        // This would overflow if we were using mul_f64.
231
        let v = mul_duration_f64_saturating(mega_year, 1e9);
232
        assert!(v > mega_year * 1000);
233

            
234
        // This would underflow.
235
        let v = mul_duration_f64_saturating(mega_year, -1.0);
236
        assert_eq!(v, Duration::from_secs(1));
237

            
238
        // These are just silly.
239
        let v = mul_duration_f64_saturating(mega_year, f64::INFINITY);
240
        assert_eq!(v, Duration::from_secs(1));
241
        let v = mul_duration_f64_saturating(mega_year, f64::NEG_INFINITY);
242
        assert_eq!(v, Duration::from_secs(1));
243
        let v = mul_duration_f64_saturating(mega_year, f64::NAN);
244
        assert_eq!(v, Duration::from_secs(1));
245
    }
246
}