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}