1use crate::error::{Error, ErrorCode, Result};
42use crate::platform::Duration;
43use crate::platform::Instant;
44
45pub const MRP_MAX_TRANSMISSIONS: u32 = 5;
47
48pub const MRP_BACKOFF_BASE: (u64, u64) = (16, 10);
50
51pub const MRP_BACKOFF_JITTER: (u64, u64) = (1, 4);
53
54pub const MRP_BACKOFF_MARGIN: (u64, u64) = (11, 10);
56
57pub const MRP_BACKOFF_THRESHOLD: u32 = 1;
60
61pub const MRP_STANDALONE_ACK_TIMEOUT: Duration = Duration::from_millis(200);
64
65pub const SESSION_IDLE_INTERVAL: Duration = Duration::from_millis(500);
68
69pub const SESSION_ACTIVE_INTERVAL: Duration = Duration::from_millis(300);
71
72pub const SESSION_ACTIVE_THRESHOLD: Duration = Duration::from_millis(4000);
74
75#[derive(Debug, Clone, Copy, PartialEq, Eq)]
83pub struct MrpParams {
84 pub idle_interval: Duration,
86 pub active_interval: Duration,
88 pub active_threshold: Duration,
90}
91
92impl Default for MrpParams {
93 fn default() -> Self {
94 Self {
95 idle_interval: SESSION_IDLE_INTERVAL,
96 active_interval: SESSION_ACTIVE_INTERVAL,
97 active_threshold: SESSION_ACTIVE_THRESHOLD,
98 }
99 }
100}
101
102impl MrpParams {
103 #[must_use]
110 pub fn clamped(self) -> Self {
111 const MAX_INTERVAL: Duration = Duration::from_millis(3_600_000);
112 const MAX_THRESHOLD: Duration = Duration::from_millis(65_535);
113 Self {
114 idle_interval: min(self.idle_interval, MAX_INTERVAL),
115 active_interval: min(self.active_interval, MAX_INTERVAL),
116 active_threshold: min(self.active_threshold, MAX_THRESHOLD),
117 }
118 }
119
120 #[must_use]
126 pub fn base_interval(&self, peer_active: bool) -> Duration {
127 let i = if peer_active {
128 self.active_interval
129 } else {
130 self.idle_interval
131 };
132 i.mul_ratio(MRP_BACKOFF_MARGIN.0, MRP_BACKOFF_MARGIN.1)
133 }
134}
135
136const fn min(a: Duration, b: Duration) -> Duration {
137 if a.as_micros() <= b.as_micros() { a } else { b }
138}
139
140#[must_use]
145pub fn backoff(base_interval: Duration, n: u32) -> Duration {
146 let exponent = n.saturating_sub(MRP_BACKOFF_THRESHOLD);
147 let mut d = base_interval;
148 for _ in 0..exponent {
149 d = d.mul_ratio(MRP_BACKOFF_BASE.0, MRP_BACKOFF_BASE.1);
150 }
151 d
152}
153
154#[must_use]
161pub fn with_jitter(backoff: Duration, randomness: u32) -> Duration {
162 const RESOLUTION: u64 = 1 << 16;
164 let draw = u64::from(randomness) % RESOLUTION;
165 let denominator = RESOLUTION.saturating_mul(MRP_BACKOFF_JITTER.1);
166 let extra = backoff.mul_ratio(draw.saturating_mul(MRP_BACKOFF_JITTER.0), denominator);
167 backoff.saturating_add(extra)
168}
169
170#[derive(Debug, Clone, Copy, PartialEq, Eq)]
172#[non_exhaustive]
173pub enum OnTimeout {
174 Retransmit {
176 counter: u32,
180 attempt: u32,
182 },
183 SendStandaloneAck {
185 counter: u32,
187 },
188 GiveUp {
191 counter: u32,
193 },
194 Nothing,
196}
197
198#[derive(Debug, Clone, Copy, PartialEq, Eq)]
203pub struct Mrp {
204 params: MrpParams,
205 pending_tx: Option<PendingTx>,
207 pending_ack: Option<PendingAck>,
209 last_heard: Option<Instant>,
211}
212
213#[derive(Debug, Clone, Copy, PartialEq, Eq)]
214struct PendingTx {
215 counter: u32,
216 sent: u32,
218 deadline: Instant,
220}
221
222#[derive(Debug, Clone, Copy, PartialEq, Eq)]
223struct PendingAck {
224 counter: u32,
225 deadline: Instant,
227}
228
229impl Mrp {
230 #[must_use]
232 pub fn new(params: MrpParams) -> Self {
233 Self {
234 params: params.clamped(),
235 pending_tx: None,
236 pending_ack: None,
237 last_heard: None,
238 }
239 }
240
241 #[must_use]
243 pub const fn params(&self) -> MrpParams {
244 self.params
245 }
246
247 #[must_use]
249 pub const fn is_awaiting_ack(&self) -> bool {
250 self.pending_tx.is_some()
251 }
252
253 #[must_use]
255 pub const fn awaiting(&self) -> Option<u32> {
256 match self.pending_tx {
257 Some(tx) => Some(tx.counter),
258 None => None,
259 }
260 }
261
262 #[must_use]
266 pub fn peer_active(&self, now: Instant) -> bool {
267 match self.last_heard {
268 Some(t) => now.saturating_duration_since(t) < self.params.active_threshold,
269 None => false,
270 }
271 }
272
273 pub fn note_peer_activity(&mut self, now: Instant) {
275 self.last_heard = Some(now);
276 }
277
278 pub fn on_send(&mut self, counter: u32, now: Instant, randomness: u32) -> Result<()> {
284 if self.pending_tx.is_some() {
285 return Err(Error::new(ErrorCode::Busy));
286 }
287 let base = self.params.base_interval(self.peer_active(now));
291 let deadline = now.saturating_add(with_jitter(backoff(base, 0), randomness));
292 self.pending_tx = Some(PendingTx {
293 counter,
294 sent: 1,
295 deadline,
296 });
297 Ok(())
298 }
299
300 pub fn take_piggyback(&mut self) -> Option<u32> {
305 self.pending_ack.take().map(|a| a.counter)
306 }
307
308 pub fn on_reliable_received(&mut self, counter: u32, now: Instant, _duplicate: bool) {
315 self.note_peer_activity(now);
316 self.pending_ack = Some(PendingAck {
317 counter,
318 deadline: now.saturating_add(MRP_STANDALONE_ACK_TIMEOUT),
319 });
320 }
321
322 pub fn on_ack(&mut self, counter: u32, now: Instant) -> bool {
328 self.note_peer_activity(now);
329 match self.pending_tx {
330 Some(tx) if tx.counter == counter => {
331 self.pending_tx = None;
332 true
333 }
334 _ => false,
335 }
336 }
337
338 #[must_use]
340 pub fn poll_deadline(&self) -> Option<Instant> {
341 match (self.pending_tx, self.pending_ack) {
342 (Some(tx), Some(ack)) => Some(min_instant(tx.deadline, ack.deadline)),
343 (Some(tx), None) => Some(tx.deadline),
344 (None, Some(ack)) => Some(ack.deadline),
345 (None, None) => None,
346 }
347 }
348
349 pub fn on_timeout(&mut self, now: Instant, randomness: u32) -> OnTimeout {
355 if let Some(ack) = self.pending_ack
358 && ack.deadline.is_elapsed_at(now)
359 {
360 self.pending_ack = None;
361 return OnTimeout::SendStandaloneAck {
362 counter: ack.counter,
363 };
364 }
365
366 if let Some(tx) = self.pending_tx
367 && tx.deadline.is_elapsed_at(now)
368 {
369 if tx.sent >= MRP_MAX_TRANSMISSIONS {
370 self.pending_tx = None;
371 return OnTimeout::GiveUp {
372 counter: tx.counter,
373 };
374 }
375 let base = self.params.base_interval(self.peer_active(now));
378 let wait = with_jitter(backoff(base, tx.sent), randomness);
379 let attempt = tx.sent;
380 self.pending_tx = Some(PendingTx {
381 counter: tx.counter,
382 sent: tx.sent.saturating_add(1),
383 deadline: now.saturating_add(wait),
384 });
385 return OnTimeout::Retransmit {
386 counter: tx.counter,
387 attempt,
388 };
389 }
390
391 OnTimeout::Nothing
392 }
393
394 pub fn close(&mut self) {
396 self.pending_tx = None;
397 self.pending_ack = None;
398 }
399}
400
401const fn min_instant(a: Instant, b: Instant) -> Instant {
402 if a.as_micros() <= b.as_micros() { a } else { b }
403}
404
405#[cfg(test)]
406mod tests {
407 use super::*;
408
409 fn table_21_base() -> Duration {
412 MrpParams::default().base_interval(true)
413 }
414
415 #[test]
416 fn the_margin_is_applied_to_the_peer_interval() {
417 let p = MrpParams::default();
418 assert_eq!(p.base_interval(true).as_millis(), 330, "1.1 * 300");
419 assert_eq!(p.base_interval(false).as_millis(), 550, "1.1 * 500");
420 }
421
422 fn round_ms(d: Duration) -> u64 {
428 d.as_micros().saturating_add(500).wrapping_div(1_000)
429 }
430
431 #[test]
432 fn the_backoff_curve_matches_core_table_21() {
433 let base = table_21_base();
435 let expected = [330u64, 330, 528, 845, 1352];
436 for (n, want) in expected.iter().enumerate() {
437 let got = backoff(base, n as u32);
438 assert_eq!(round_ms(got), *want, "transmission #{n}");
439 }
440 assert_eq!(backoff(base, 0).as_micros(), 330_000);
443 assert_eq!(backoff(base, 2).as_micros(), 528_000);
444 assert_eq!(backoff(base, 3).as_micros(), 844_800);
445 assert_eq!(backoff(base, 4).as_micros(), 1_351_680);
446 }
447
448 #[test]
449 fn maximum_jitter_matches_core_table_21() {
450 let base = table_21_base();
452 let expected = [413u64, 413, 660, 1056, 1690];
453 for (n, want) in expected.iter().enumerate() {
454 let got = round_ms(with_jitter(backoff(base, n as u32), u32::MAX));
456 assert!(
458 got.abs_diff(*want) <= 1,
459 "transmission #{n}: got {got}, table says {want}"
460 );
461 }
462 }
463
464 #[test]
465 fn jitter_only_ever_adds() {
466 let base = table_21_base();
469 for n in 0..MRP_MAX_TRANSMISSIONS {
470 let plain = backoff(base, n);
471 for r in [0u32, 1, 1000, u32::MAX / 2, u32::MAX] {
472 let jittered = with_jitter(plain, r);
473 assert!(jittered >= plain, "n={n} r={r}");
474 assert!(
475 jittered <= plain.saturating_add(plain.mul_ratio(1, 4)),
476 "n={n} r={r}: more than 25% added"
477 );
478 }
479 }
480 }
481
482 #[test]
483 fn a_zero_draw_is_the_unjittered_backoff() {
484 let base = table_21_base();
485 assert_eq!(with_jitter(backoff(base, 0), 0), backoff(base, 0));
486 }
487
488 #[test]
489 fn an_acknowledgement_stops_the_timer() {
490 let mut mrp = Mrp::new(MrpParams::default());
491 let t0 = Instant::ZERO;
492 mrp.on_send(7, t0, 0).expect("first send");
493 assert!(mrp.is_awaiting_ack());
494 assert_eq!(mrp.awaiting(), Some(7));
495 assert!(mrp.poll_deadline().is_some());
496
497 assert!(mrp.on_ack(7, t0), "the pending message is acknowledged");
498 assert!(!mrp.is_awaiting_ack());
499 assert_eq!(mrp.poll_deadline(), None);
500 }
501
502 #[test]
503 fn an_acknowledgement_for_something_else_is_ignored() {
504 let mut mrp = Mrp::new(MrpParams::default());
505 mrp.on_send(7, Instant::ZERO, 0).expect("send");
506 assert!(!mrp.on_ack(6, Instant::ZERO), "not the pending counter");
507 assert!(mrp.is_awaiting_ack(), "still waiting");
508 }
509
510 #[test]
511 fn one_pending_retransmission_per_exchange() {
512 let mut mrp = Mrp::new(MrpParams::default());
514 mrp.on_send(1, Instant::ZERO, 0).expect("first");
515 assert_eq!(
516 mrp.on_send(2, Instant::ZERO, 0).unwrap_err().code(),
517 ErrorCode::Busy
518 );
519 }
520
521 #[test]
522 fn the_ladder_is_five_transmissions_then_give_up() {
523 let mut mrp = Mrp::new(MrpParams::default());
524 let mut now = Instant::ZERO;
525 mrp.on_send(42, now, 0).expect("send");
526
527 let mut attempts = heapless::Vec::<u32, 8>::new();
528 while let Some(deadline) = mrp.poll_deadline() {
529 now = deadline;
530 match mrp.on_timeout(now, 0) {
531 OnTimeout::Retransmit { counter, attempt } => {
532 assert_eq!(counter, 42, "the counter never changes");
533 let _ = attempts.push(attempt);
534 }
535 OnTimeout::GiveUp { counter } => {
536 assert_eq!(counter, 42);
537 break;
538 }
539 other => panic!("unexpected {other:?}"),
540 }
541 }
542 assert_eq!(&attempts[..], &[1, 2, 3, 4]);
544 assert!(!mrp.is_awaiting_ack(), "giving up clears the state");
545 }
546
547 #[test]
548 fn the_cumulative_time_matches_core_table_21() {
549 let mut mrp = Mrp::new(MrpParams::default());
551 mrp.note_peer_activity(Instant::ZERO);
553 let mut now = Instant::ZERO;
554 mrp.on_send(1, now, 0).expect("send");
555
556 let expected = [330u64, 660, 1188, 2033, 3385];
560 let mut totals = heapless::Vec::<u64, 8>::new();
561 let mut rounded_sum = 0u64;
562 let mut previous = Instant::ZERO;
563 while let Some(deadline) = mrp.poll_deadline() {
564 now = deadline;
565 rounded_sum =
566 rounded_sum.saturating_add(round_ms(now.saturating_duration_since(previous)));
567 previous = now;
568 let _ = totals.push(rounded_sum);
569 if matches!(mrp.on_timeout(now, 0), OnTimeout::GiveUp { .. }) {
570 break;
571 }
572 }
573 assert_eq!(
574 &totals[..],
575 &expected[..],
576 "cumulative retransmission times"
577 );
578 assert_eq!(
579 now.saturating_duration_since(Instant::ZERO).as_micros(),
580 3_384_480,
581 "the exact total, before the table's per-step rounding"
582 );
583 }
584
585 #[test]
586 fn a_reliable_message_schedules_a_standalone_acknowledgement() {
587 let mut mrp = Mrp::new(MrpParams::default());
588 let t0 = Instant::ZERO;
589 mrp.on_reliable_received(9, t0, false);
590
591 let deadline = mrp.poll_deadline().expect("an ack deadline");
592 assert_eq!(
593 deadline.saturating_duration_since(t0),
594 MRP_STANDALONE_ACK_TIMEOUT
595 );
596 assert_eq!(
597 mrp.on_timeout(deadline, 0),
598 OnTimeout::SendStandaloneAck { counter: 9 }
599 );
600 assert_eq!(mrp.poll_deadline(), None, "and then nothing is pending");
601 }
602
603 #[test]
604 fn a_piggyback_cancels_the_standalone_acknowledgement() {
605 let mut mrp = Mrp::new(MrpParams::default());
606 mrp.on_reliable_received(9, Instant::ZERO, false);
607 assert_eq!(mrp.take_piggyback(), Some(9));
608 assert_eq!(mrp.poll_deadline(), None, "nothing left to send alone");
609 assert_eq!(mrp.take_piggyback(), None, "and only once");
610 }
611
612 #[test]
613 fn a_duplicate_is_still_acknowledged() {
614 let mut mrp = Mrp::new(MrpParams::default());
617 mrp.on_reliable_received(9, Instant::ZERO, true);
618 assert_eq!(mrp.take_piggyback(), Some(9));
619 }
620
621 #[test]
622 fn an_idle_peer_gets_the_idle_interval() {
623 let mut mrp = Mrp::new(MrpParams::default());
624 let t0 = Instant::ZERO;
625 mrp.on_send(1, t0, 0).expect("send");
626 let deadline = mrp.poll_deadline().expect("a deadline");
627 assert_eq!(
628 deadline.saturating_duration_since(t0).as_millis(),
629 550,
630 "a peer never heard from is idle: 1.1 * 500"
631 );
632 }
633
634 #[test]
635 fn an_active_peer_gets_the_active_interval() {
636 let mut mrp = Mrp::new(MrpParams::default());
637 let t0 = Instant::ZERO;
638 mrp.note_peer_activity(t0);
639 mrp.on_send(1, t0, 0).expect("send");
640 let deadline = mrp.poll_deadline().expect("a deadline");
641 assert_eq!(deadline.saturating_duration_since(t0).as_millis(), 330);
642 }
643
644 #[test]
645 fn a_peer_goes_idle_after_the_active_threshold() {
646 let mut mrp = Mrp::new(MrpParams::default());
647 mrp.note_peer_activity(Instant::ZERO);
648 assert!(mrp.peer_active(Instant::from_micros(0)));
649 let just_inside = Instant::ZERO
650 .saturating_add(SESSION_ACTIVE_THRESHOLD)
651 .saturating_sub(Duration::from_micros(1));
652 assert!(mrp.peer_active(just_inside));
653 let at_threshold = Instant::ZERO.saturating_add(SESSION_ACTIVE_THRESHOLD);
654 assert!(!mrp.peer_active(at_threshold), "the comparison is strict");
655 }
656
657 #[test]
658 fn peer_parameters_from_the_network_are_clamped() {
659 let hostile = MrpParams {
661 idle_interval: Duration::from_secs(86_400),
662 active_interval: Duration::from_secs(86_400),
663 active_threshold: Duration::from_secs(86_400),
664 };
665 let safe = hostile.clamped();
666 assert_eq!(safe.idle_interval.as_millis(), 3_600_000);
667 assert_eq!(safe.active_interval.as_millis(), 3_600_000);
668 assert_eq!(safe.active_threshold.as_millis(), 65_535);
669 assert_eq!(Mrp::new(hostile).params(), safe);
671 }
672
673 #[test]
674 fn both_a_retransmission_and_an_acknowledgement_can_be_due() {
675 let mut mrp = Mrp::new(MrpParams::default());
676 let t0 = Instant::ZERO;
677 mrp.on_send(1, t0, 0).expect("send");
678 mrp.on_reliable_received(2, t0, false);
679
680 let first = mrp.poll_deadline().expect("a deadline");
682 assert_eq!(
683 first.saturating_duration_since(t0),
684 MRP_STANDALONE_ACK_TIMEOUT
685 );
686 assert!(matches!(
687 mrp.on_timeout(first, 0),
688 OnTimeout::SendStandaloneAck { counter: 2 }
689 ));
690 assert!(mrp.poll_deadline().is_some());
692 assert!(mrp.is_awaiting_ack());
693 }
694
695 #[test]
696 fn an_early_timeout_does_nothing() {
697 let mut mrp = Mrp::new(MrpParams::default());
698 mrp.on_send(1, Instant::ZERO, 0).expect("send");
699 assert_eq!(
700 mrp.on_timeout(Instant::from_micros(1), 0),
701 OnTimeout::Nothing
702 );
703 assert!(mrp.is_awaiting_ack(), "and changes nothing");
704 }
705
706 #[test]
707 fn closing_abandons_everything() {
708 let mut mrp = Mrp::new(MrpParams::default());
709 mrp.on_send(1, Instant::ZERO, 0).expect("send");
710 mrp.on_reliable_received(2, Instant::ZERO, false);
711 mrp.close();
712 assert_eq!(mrp.poll_deadline(), None);
713 assert!(!mrp.is_awaiting_ack());
714 }
715}