tor_proto/channel/
padding.rs

1//! Channel padding
2//!
3//! Tor spec `padding-spec.txt` section 2.
4//!
5//! # Overview of channel padding control arrangements
6//!
7//!  1. `tor_chanmgr::mgr::map` collates information about dormancy, netdir,
8//!     and overall client configuration, to maintain a
9//!     [`ChannelPaddingInstructions`](crate::channel::ChannelPaddingInstructions)
10//!     which is to be used for all relevant[^relevant] channels.
11//!     This is distributed to channel frontends (`Channel`s)
12//!     by calling `Channel::reparameterize`.
13//!
14//!  2. Circuit and channel `get_or_launch` methods all take a `ChannelUsage`.
15//!     This is plumbed through the layers to `AbstractChanMgr::get_or_launch`,
16//!     which passes it to the channel frontend via `Channel::note_usage`.
17//!
18//!  3. The `Channel` collates this information, and maintains an idea
19//!     of whether padding is relevant for this channel (`PaddingControlState`).
20//!     For channels where it *is* relevant, it sends `CtrlMsg::ConfigUpdate`
21//!     to the reactor.
22//!
23//!  4. The reactor handles `CtrlMsg::ConfigUpdate` by reconfiguring is padding timer;
24//!     and by sending PADDING_NEGOTIATE cell(s).
25//!
26//! [^relevant]: A "relevant" channel is one which is not excluded by the rules about
27//! padding in padding-spec 2.2.  Arti does not currently support acting as a relay,
28//! so all our channels are client-to-guard or client-to-directory.
29
30use std::pin::Pin;
31// TODO, coarsetime maybe?  But see arti#496 and also we want to use the mockable SleepProvider
32use std::time::{Duration, Instant};
33
34use derive_builder::Builder;
35use educe::Educe;
36use futures::future::{self, FusedFuture};
37use futures::FutureExt;
38use pin_project::pin_project;
39use rand::distr::Distribution;
40use tracing::error;
41
42use tor_cell::chancell::msg::{Padding, PaddingNegotiate};
43use tor_config::impl_standard_builder;
44use tor_error::into_internal;
45use tor_rtcompat::SleepProvider;
46use tor_units::IntegerMilliseconds;
47
48/// Timer that organises wakeups when channel padding should be sent
49///
50/// Use [`next()`](Timer::next) to find when to send padding, and
51/// [`note_cell_sent()`](Timer::note_cell_sent) to reset the timeout when data flows.
52///
53/// A `Timer` can be in "disabled" state, in which case `next()` never completes.
54///
55/// `Timer` must be pinned before use
56/// (this allows us to avoid involving the allocator when we reschedule).
57#[pin_project(project = PaddingTimerProj)]
58pub(crate) struct Timer<R: SleepProvider> {
59    /// [`SleepProvider`]
60    sleep_prov: R,
61
62    /// Parameters controlling distribution of padding time intervals
63    ///
64    /// Can be `None` to mean the timing parameters are set to infinity.
65    parameters: Option<PreparedParameters>,
66
67    /// Gap that we intend to leave between last sent cell, and the padding
68    ///
69    /// We only resample this (calculating a new random delay) after the previous
70    /// timeout actually expired.
71    ///
72    /// `None` if the timer is disabled.
73    /// (This can be done explicitly, but also occurs on time calculation overflow.)
74    ///
75    /// Invariants: this field may be `Some` or `None` regardless of the values
76    /// of other fields.  If this field is `None` then the values in `trigger_at`
77    /// and `waker` are unspecified.
78    selected_timeout: Option<Duration>,
79
80    /// Absolute time at which we should send padding
81    ///
82    /// `None` if cells more recently sent than we were polled.
83    /// That would mean that we are currently moving data out through this channel.
84    /// The absolute timeout will need to be recalculated when the data flow pauses.
85    ///
86    /// `Some` means our `next` has been demanded recently.
87    /// Then `trigger_at` records the absolute timeout at which we should send padding,
88    /// which was calculated the first time we were polled (after data).
89    ///
90    /// Invariants: the value in this field is meaningful only if `selected_timeout`
91    /// is `Some`.
92    ///
93    /// If `selected_timeout` is `Some`, and `trigger_at` is therefore valid,
94    /// it is (obviously) no later than `selected_timeout` from now.
95    ///
96    /// See also `waker`.
97    trigger_at: Option<Instant>,
98
99    /// Actual waker from the `SleepProvider`
100    ///
101    /// This is created and updated lazily, because we suspect that with some runtimes
102    /// setting timeouts may be slow.
103    /// Lazy updating means that with intermittent data traffic, we do not keep scheduling,
104    /// descheduling, and adjusting, a wakeup time.
105    ///
106    /// Invariants:
107    ///
108    /// If `selected_timeout` is `Some`,
109    /// the time at which this waker will trigger here is never *later* than `trigger_at`,
110    /// and never *later* than `selected_timeout` from now.
111    ///
112    /// The wakeup time here may well be earlier than `trigger_at`,
113    /// and sooner than `selected_timeout` from now.  It may even be in the past.
114    /// When we wake up and discover this situation, we reschedule a new waker.
115    ///
116    /// If `selected_timeout` is `None`, the value is unspecified.
117    /// We may retain a `Some` in this case so that if `SleepProvider` is enhanced to
118    /// support rescheduling, we can do that without making a new `SleepFuture`
119    /// (and without completely reorganising this the `Timer` state structure.)
120    #[pin]
121    waker: Option<R::SleepFuture>,
122}
123
124/// Timing parameters, as described in `padding-spec.txt`
125#[derive(Debug, Copy, Clone, Eq, PartialEq, Builder)]
126#[builder(build_fn(error = "ParametersError", private, name = "build_inner"))]
127pub struct Parameters {
128    /// Low end of the distribution of `X`
129    #[builder(default = "1500.into()")]
130    pub(crate) low: IntegerMilliseconds<u32>,
131    /// High end of the distribution of `X` (inclusive)
132    #[builder(default = "9500.into()")]
133    pub(crate) high: IntegerMilliseconds<u32>,
134}
135
136/// An error that occurred whil e constructing padding parameters.
137#[derive(Clone, Debug, thiserror::Error)]
138#[non_exhaustive]
139pub enum ParametersError {
140    /// Could not construct a range: there were no members between low and high.
141    #[error("Cannot construct padding parameters: low bound was above the high bound.")]
142    InvalidRange,
143}
144
145impl ParametersBuilder {
146    /// Try to construct a [`Parameters`] from this builder.
147    ///
148    /// returns an error if the distribution is ill-defined.
149    pub fn build(&self) -> Result<Parameters, ParametersError> {
150        let parameters = self.build_inner()?;
151        if parameters.low > parameters.high {
152            return Err(ParametersError::InvalidRange);
153        }
154
155        Ok(parameters)
156    }
157}
158
159impl_standard_builder! { Parameters: !Deserialize + !Builder + !Default }
160
161impl Parameters {
162    /// Return a `PADDING_NEGOTIATE START` cell specifying precisely these parameters
163    ///
164    /// This function does not take account of the need to avoid sending particular
165    /// parameters, and instead sending zeroes, if the requested padding is the consensus
166    /// default.  The caller must take care of that.
167    pub fn padding_negotiate_cell(&self) -> Result<PaddingNegotiate, tor_error::Bug> {
168        let get = |input: IntegerMilliseconds<u32>| {
169            input
170                .try_map(TryFrom::try_from)
171                .map_err(into_internal!("padding negotiate out of range"))
172        };
173        Ok(PaddingNegotiate::start(get(self.low)?, get(self.high)?))
174    }
175
176    /// Make a Parameters containing the specification-defined default parameters
177    pub fn default_padding() -> Self {
178        Parameters::builder().build().expect("build succeeded")
179    }
180
181    /// Make a Parameters sentinel value, with both fields set to zero, which means "no padding"
182    pub fn disabled() -> Self {
183        Parameters {
184            low: 0.into(),
185            high: 0.into(),
186        }
187    }
188}
189
190/// Timing parameters, "compiled" into a form which can be sampled more efficiently
191///
192/// According to the docs for [`rand::Rng::gen_range`],
193/// it is better to construct a distribution,
194/// than to call `gen_range` repeatedly on the same range.
195#[derive(Debug, Clone)]
196struct PreparedParameters {
197    /// The distribution of `X` (not of the ultimate delay, which is `max(X1,X2)`)
198    x_distribution_ms: rand::distr::Uniform<u32>,
199}
200
201/// Return value from `prepare_to_sleep`: instructions for what caller ought to do
202#[derive(Educe)]
203#[educe(Debug)]
204enum SleepInstructions<'f, R: SleepProvider> {
205    /// Caller should send padding immediately
206    Immediate {
207        /// The current `Instant`, returned so that the caller need not call `now` again
208        now: Instant,
209    },
210    /// Caller should wait forever
211    Forever,
212    /// Caller should `await` this
213    Waker(#[educe(Debug(ignore))] Pin<&'f mut R::SleepFuture>),
214}
215
216impl<R: SleepProvider> Timer<R> {
217    /// Create a new `Timer`
218    #[allow(dead_code)]
219    pub(crate) fn new(sleep_prov: R, parameters: Parameters) -> crate::Result<Self> {
220        let parameters = parameters.prepare()?;
221        let selected_timeout = parameters.select_timeout();
222        // Too different to new_disabled to share its code, sadly.
223        Ok(Timer {
224            sleep_prov,
225            parameters: Some(parameters),
226            selected_timeout: Some(selected_timeout),
227            trigger_at: None,
228            waker: None,
229        })
230    }
231
232    /// Create a new `Timer` which starts out disabled
233    pub(crate) fn new_disabled(
234        sleep_prov: R,
235        parameters: Option<Parameters>,
236    ) -> crate::Result<Self> {
237        Ok(Timer {
238            sleep_prov,
239            parameters: parameters.map(|p| p.prepare()).transpose()?,
240            selected_timeout: None,
241            trigger_at: None,
242            waker: None,
243        })
244    }
245
246    /// Disable this `Timer`
247    ///
248    /// Idempotent.
249    pub(crate) fn disable(self: &mut Pin<&mut Self>) {
250        *self.as_mut().project().selected_timeout = None;
251    }
252
253    /// Enable this `Timer`
254    ///
255    /// (If the timer was disabled, the timeout will only start to run when `next()`
256    /// is next polled.)
257    ///
258    /// Idempotent.
259    pub(crate) fn enable(self: &mut Pin<&mut Self>) {
260        if !self.is_enabled() {
261            self.as_mut().select_fresh_timeout();
262        }
263    }
264
265    /// Set this `Timer`'s parameters
266    ///
267    /// Will not enable or disable the timer; that must be done separately if desired.
268    ///
269    /// The effect may not be immediate: if we are already in a gap between cells,
270    /// that existing gap may not be adjusted.
271    /// (We don't *restart* the timer since that would very likely result in a gap
272    /// longer than either of the configured values.)
273    ///
274    /// Idempotent.
275    pub(crate) fn reconfigure(
276        self: &mut Pin<&mut Self>,
277        parameters: &Parameters,
278    ) -> crate::Result<()> {
279        *self.as_mut().project().parameters = Some(parameters.prepare()?);
280        Ok(())
281    }
282
283    /// Enquire whether this `Timer` is currently enabled
284    pub(crate) fn is_enabled(&self) -> bool {
285        self.selected_timeout.is_some()
286    }
287
288    /// Select a fresh timeout (and enable, if possible)
289    fn select_fresh_timeout(self: Pin<&mut Self>) {
290        let mut self_ = self.project();
291        let timeout = self_.parameters.as_ref().map(|p| p.select_timeout());
292        *self_.selected_timeout = timeout;
293        // This is no longer valid; recalculate it on next poll
294        *self_.trigger_at = None;
295        // Timeout might be earlier, so we will need a new waker too.
296        self_.waker.set(None);
297    }
298
299    /// Note that data has been sent (ie, reset the timeout, delaying the next padding)
300    pub(crate) fn note_cell_sent(self: &mut Pin<&mut Self>) {
301        // Fast path, does not need to do anything but clear the absolute expiry time
302        let self_ = self.as_mut().project();
303        *self_.trigger_at = None;
304    }
305
306    /// Calculate when to send padding, and return a suitable waker
307    ///
308    /// In the usual case returns [`SleepInstructions::Waker`].
309    fn prepare_to_sleep(mut self: Pin<&mut Self>, now: Option<Instant>) -> SleepInstructions<R> {
310        let mut self_ = self.as_mut().project();
311
312        let timeout = match self_.selected_timeout {
313            None => return SleepInstructions::Forever,
314            Some(t) => *t,
315        };
316
317        if self_.waker.is_some() {
318            // We need to do this with is_some and expect because we need to consume self
319            // to get a return value with the right lifetimes.
320            let waker = self
321                .project()
322                .waker
323                .as_pin_mut()
324                .expect("None but we just checked");
325            return SleepInstructions::Waker(waker);
326        }
327
328        let now = now.unwrap_or_else(|| self_.sleep_prov.now());
329
330        let trigger_at = match self_.trigger_at {
331            Some(t) => t,
332            None => self_.trigger_at.insert(match now.checked_add(timeout) {
333                None => {
334                    error!("bug: timeout overflowed computing next channel padding. Disabling.");
335                    self.disable();
336                    return SleepInstructions::Forever;
337                }
338                Some(r) => r,
339            }),
340        };
341
342        let remaining = trigger_at.checked_duration_since(now).unwrap_or_default();
343        if remaining.is_zero() {
344            return SleepInstructions::Immediate { now };
345        }
346
347        //dbg!(timeout, remaining, now, trigger_at);
348
349        // There is no Option::get_pin_mut_or_set_with
350        if self_.waker.is_none() {
351            self_.waker.set(Some(self_.sleep_prov.sleep(remaining)));
352        }
353        let waker = self
354            .project()
355            .waker
356            .as_pin_mut()
357            .expect("None but we just inserted!");
358        SleepInstructions::Waker(waker)
359    }
360
361    /// Wait until we should next send padding, and then return the padding message
362    ///
363    /// Should be used as a low-priority branch within `select_biased!`.
364    ///
365    /// (`next()` has to be selected on, along with other possible events, in the
366    /// main loop, so that the padding timer runs concurrently with other processing;
367    /// and it should be in a low-priority branch of `select_biased!` as an optimisation:
368    /// that avoids calculating timeouts etc. until necessary,
369    /// i.e. it calculates them only when the main loop would otherwise block.)
370    ///
371    /// The returned future is async-cancel-safe,
372    /// but once it yields, the padding must actually be sent.
373    pub(crate) fn next(self: Pin<&mut Self>) -> impl FusedFuture<Output = Padding> + '_ {
374        self.next_inner().fuse()
375    }
376
377    /// Wait until we should next send padding (not `FusedFuture`)
378    ///
379    /// Callers wants a [`FusedFuture`] because `select!` needs one.
380    async fn next_inner(mut self: Pin<&mut Self>) -> Padding {
381        let now = loop {
382            match self.as_mut().prepare_to_sleep(None) {
383                SleepInstructions::Forever => future::pending().await,
384                SleepInstructions::Immediate { now } => break now,
385                SleepInstructions::Waker(waker) => waker.await,
386            }
387
388            // This timer has fired and has therefore been used up.
389            // When we go round again we will make a new one.
390            //
391            // TODO: have SleepProviders provide a reschedule function, and use it.
392            // That is likely to be faster where supported.
393            self.as_mut().project().waker.set(None);
394        };
395
396        // It's time to send padding.
397
398        // Firstly, calculate the new timeout for the *next* padding,
399        // so that we leave the `Timer` properly programmed.
400        self.as_mut().select_fresh_timeout();
401
402        // Bet that we will be going to sleep again, and set up the new trigger time
403        // and waker now.  This will save us a future call to Instant::now.
404        self.as_mut().prepare_to_sleep(Some(now));
405
406        Padding::new()
407    }
408}
409
410impl Parameters {
411    /// "Compile" the parameters into a form which can be quickly sampled
412    fn prepare(self) -> Result<PreparedParameters, tor_error::Bug> {
413        Ok(PreparedParameters {
414            x_distribution_ms: rand::distr::Uniform::new_inclusive(
415                self.low.as_millis(),
416                self.high.as_millis(),
417            )
418            .map_err(into_internal!("Parameters were not a valid range."))?,
419        })
420    }
421}
422
423impl PreparedParameters {
424    /// Randomly select a timeout (as per `padding-spec.txt`)
425    fn select_timeout(&self) -> Duration {
426        let mut rng = rand::rng();
427        let ms = std::cmp::max(
428            self.x_distribution_ms.sample(&mut rng),
429            self.x_distribution_ms.sample(&mut rng),
430        );
431        Duration::from_millis(ms.into())
432    }
433}
434
435#[cfg(test)]
436mod test {
437    // @@ begin test lint list maintained by maint/add_warning @@
438    #![allow(clippy::bool_assert_comparison)]
439    #![allow(clippy::clone_on_copy)]
440    #![allow(clippy::dbg_macro)]
441    #![allow(clippy::mixed_attributes_style)]
442    #![allow(clippy::print_stderr)]
443    #![allow(clippy::print_stdout)]
444    #![allow(clippy::single_char_pattern)]
445    #![allow(clippy::unwrap_used)]
446    #![allow(clippy::unchecked_duration_subtraction)]
447    #![allow(clippy::useless_vec)]
448    #![allow(clippy::needless_pass_by_value)]
449    //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
450
451    use super::*;
452    use futures::future::ready;
453    use futures::select_biased;
454    use itertools::{izip, Itertools};
455    use statrs::distribution::ContinuousCDF;
456    use tokio::pin;
457    use tokio_crate::{self as tokio};
458    use tor_rtcompat::*;
459
460    async fn assert_not_ready<R: Runtime>(timer: &mut Pin<&mut Timer<R>>) {
461        select_biased! {
462            _ = timer.as_mut().next() => panic!("unexpectedly ready"),
463            _ = ready(()) => { },
464        };
465    }
466
467    async fn assert_is_ready<R: Runtime>(timer: &mut Pin<&mut Timer<R>>) {
468        let _: Padding = select_biased! {
469            p = timer.as_mut().next() => p,
470            _ = ready(()) => panic!("pad timer failed to yield"),
471        };
472    }
473
474    #[test]
475    fn timer_impl() {
476        let runtime = tor_rtcompat::tokio::TokioNativeTlsRuntime::create().unwrap();
477        #[allow(deprecated)] // TODO #1885
478        let runtime = tor_rtmock::MockSleepRuntime::new(runtime);
479
480        let parameters = Parameters {
481            low: 1000.into(),
482            high: 1000.into(),
483        };
484
485        let () = runtime.block_on(async {
486            let timer = Timer::new(runtime.clone(), parameters).unwrap();
487            pin!(timer);
488            assert_eq! { true, timer.is_enabled() }
489
490            // expiry time not yet calculated
491            assert_eq! { timer.as_mut().trigger_at, None };
492
493            // ---------- timeout value ----------
494
495            // Just created, not ready yet
496            assert_not_ready(&mut timer).await;
497
498            runtime.advance(Duration::from_millis(999)).await;
499            // Not quite ready
500            assert_not_ready(&mut timer).await;
501
502            runtime.advance(Duration::from_millis(1)).await;
503            // Should go off precisely now
504            assert_is_ready(&mut timer).await;
505
506            assert_not_ready(&mut timer).await;
507            runtime.advance(Duration::from_millis(1001)).await;
508            // Should go off 1ms ago, fine
509            assert_is_ready(&mut timer).await;
510
511            // ---------- various resets ----------
512
513            runtime.advance(Duration::from_millis(500)).await;
514            timer.note_cell_sent();
515            assert_eq! { timer.as_mut().trigger_at, None };
516
517            // This ought not to cause us to actually calculate the expiry time
518            let () = select_biased! {
519                _ = ready(()) => { },
520                _ = timer.as_mut().next() => panic!(),
521            };
522            assert_eq! { timer.as_mut().trigger_at, None };
523
524            // ---------- disable/enable ----------
525
526            timer.disable();
527            runtime.advance(Duration::from_millis(2000)).await;
528            assert_eq! { timer.as_mut().selected_timeout, None };
529            assert_eq! { false, timer.is_enabled() }
530            assert_not_ready(&mut timer).await;
531
532            timer.enable();
533            runtime.advance(Duration::from_millis(3000)).await;
534            assert_eq! { true, timer.is_enabled() }
535            // Shouldn't be already ready, since we haven't polled yet
536            assert_not_ready(&mut timer).await;
537
538            runtime.advance(Duration::from_millis(1000)).await;
539            // *Now*
540            assert_is_ready(&mut timer).await;
541        });
542
543        let () = runtime.block_on(async {
544            let timer = Timer::new(runtime.clone(), parameters).unwrap();
545            pin!(timer);
546
547            assert! { timer.as_mut().selected_timeout.is_some() };
548            assert! { timer.as_mut().trigger_at.is_none() };
549            // Force an overflow by guddling
550            *timer.as_mut().project().selected_timeout = Some(Duration::MAX);
551
552            assert_not_ready(&mut timer).await;
553            dbg!(timer.as_mut().project().trigger_at);
554            assert_eq! { false, timer.is_enabled() }
555        });
556
557        let () = runtime.block_on(async {
558            let timer = Timer::new_disabled(runtime.clone(), None).unwrap();
559            assert! { timer.parameters.is_none() };
560            pin!(timer);
561            assert_not_ready(&mut timer).await;
562            assert! { timer.as_mut().selected_timeout.is_none() };
563            assert! { timer.as_mut().trigger_at.is_none() };
564        });
565
566        let () = runtime.block_on(async {
567            let timer = Timer::new_disabled(runtime.clone(), Some(parameters)).unwrap();
568            assert! { timer.parameters.is_some() };
569            pin!(timer);
570            assert_not_ready(&mut timer).await;
571            runtime.advance(Duration::from_millis(3000)).await;
572            assert_not_ready(&mut timer).await;
573            timer.as_mut().enable();
574            assert_not_ready(&mut timer).await;
575            runtime.advance(Duration::from_millis(3000)).await;
576            assert_is_ready(&mut timer).await;
577        });
578    }
579
580    #[test]
581    #[allow(clippy::print_stderr)]
582    fn timeout_distribution() {
583        // Test that the distribution of padding intervals is as we expect.  This is not so
584        // straightforward.  We need to deal with true randomness (since we can't plumb a
585        // testing RNG into the padding timer, and perhaps don't even *want* to make that a
586        // mockable interface).  Measuring a distribution of random variables involves some
587        // statistics.
588
589        // The overall approach is:
590        //    Use a fixed (but nontrivial) low to high range
591        //    Sample N times into n equal sized buckets
592        //    Calculate the expected number of samples in each bucket
593        //    Do a chi^2 test.  If it doesn't spot a potential difference, declare OK.
594        //    If the chi^2 test does definitely declare a difference, declare failure.
595        //    Otherwise increase N and go round again.
596        //
597        // This allows most runs to be fast without having an appreciable possibility of a
598        // false test failure and while being able to detect even quite small deviations.
599
600        // Notation from
601        // https://en.wikipedia.org/wiki/Pearson%27s_chi-squared_test#Calculating_the_test-statistic
602        // I haven't done a formal power calculation but empirically
603        // this detects the following most of the time:
604        //  deviation of the CDF power from B^2 to B^1.98
605        //  wrong minimum value by 25ms out of 12s, low_ms = min + 25
606        //  wrong maximum value by 10ms out of 12s, high_ms = max -1 - 10
607
608        #[allow(non_snake_case)]
609        let mut N = 100_0000;
610
611        #[allow(non_upper_case_globals)]
612        const n: usize = 100;
613
614        const P_GOOD: f64 = 0.05; // Investigate further 5% of times (if all is actually well)
615        const P_BAD: f64 = 1e-12;
616
617        loop {
618            eprintln!("padding distribution test, n={} N={}", n, N);
619
620            let min = 5000;
621            let max = 17000; // Exclusive
622            assert_eq!(0, (max - min) % (n as u32)); // buckets must match up to integer boundaries
623
624            let cdf = (0..=n)
625                .map(|bi| {
626                    let b = (bi as f64) / (n as f64);
627                    // expected distribution:
628                    // with B = bi / n
629                    //   P(X) < B == B
630                    //   P(max(X1,X1)) < B = B^2
631                    b.powi(2)
632                })
633                .collect_vec();
634
635            let pdf = cdf
636                .iter()
637                .cloned()
638                .tuple_windows()
639                .map(|(p, q)| q - p)
640                .collect_vec();
641            let exp = pdf.iter().cloned().map(|p| p * f64::from(N)).collect_vec();
642
643            // chi-squared test only valid if every cell expects at least 5
644            assert!(exp.iter().cloned().all(|ei| ei >= 5.));
645
646            let mut obs = [0_u32; n];
647
648            let params = Parameters {
649                low: min.into(),
650                high: (max - 1).into(), // convert exclusive to inclusive
651            }
652            .prepare()
653            .unwrap();
654
655            for _ in 0..N {
656                let xx = params.select_timeout();
657                let ms = xx.as_millis();
658                let ms = u32::try_from(ms).unwrap();
659                assert!(ms >= min);
660                assert!(ms < max);
661                // Integer arithmetic ensures that we classify exactly
662                let bi = ((ms - min) * (n as u32)) / (max - min);
663                obs[bi as usize] += 1;
664            }
665
666            let chi2 = izip!(&obs, &exp)
667                .map(|(&oi, &ei)| (f64::from(oi) - ei).powi(2) / ei)
668                .sum::<f64>();
669
670            // n degrees of freedom, one-tailed test
671            // (since distro parameters are all fixed, not estimated from the sample)
672            let chi2_distr = statrs::distribution::ChiSquared::new(n as _).unwrap();
673
674            // probability of good code generating a result at least this bad
675            let p = 1. - chi2_distr.cdf(chi2);
676
677            eprintln!(
678                "padding distribution test, n={} N={} chi2={} p={}",
679                n, N, chi2, p
680            );
681
682            if p >= P_GOOD {
683                break;
684            }
685
686            for (i, (&oi, &ei)) in izip!(&obs, &exp).enumerate() {
687                eprintln!("bi={:4} OI={:4} EI={}", i, oi, ei);
688            }
689
690            if p < P_BAD {
691                panic!("distribution is wrong (p < {:e})", P_BAD);
692            }
693
694            // This is statistically rather cheaty: we keep trying until we get a definite
695            // answer!  But we radically increase the power of the test each time.
696            // If the distribution is really wrong, this test ought to find it soon enough,
697            // especially since we run this repeatedly in CI.
698            N *= 10;
699        }
700    }
701
702    #[test]
703    fn parameters_range() {
704        let ms100 = IntegerMilliseconds::new(100);
705        let ms1000 = IntegerMilliseconds::new(1000);
706        let ms1500 = IntegerMilliseconds::new(1500);
707        let ms9500 = IntegerMilliseconds::new(9500);
708
709        // default
710        let p = Parameters::builder().build().unwrap();
711        assert_eq!(
712            p,
713            Parameters {
714                low: ms1500,
715                high: ms9500
716            }
717        );
718        assert!(p.prepare().is_ok());
719
720        // low < high
721        let mut pb = Parameters::builder();
722        pb.low(ms100);
723        pb.high(ms1000);
724        let p = pb.build().unwrap();
725        assert_eq!(
726            p,
727            Parameters {
728                low: ms100,
729                high: ms1000
730            }
731        );
732        let p = p.prepare().unwrap();
733        let range = Duration::try_from(ms100).unwrap()..=Duration::try_from(ms1000).unwrap();
734        for _ in 1..100 {
735            assert!(range.contains(&p.select_timeout()));
736        }
737
738        // low == high
739        let mut pb = Parameters::builder();
740        pb.low(ms1000);
741        pb.high(ms1000);
742        let p = pb.build().unwrap();
743        assert!(p.prepare().is_ok());
744
745        // low > high (error case)
746        let mut pb = Parameters::builder();
747        pb.low(ms1000);
748        pb.high(ms100);
749        let e = pb.build().unwrap_err();
750        assert!(matches!(e, ParametersError::InvalidRange));
751    }
752}