Skip to main content

matter_kit/discovery/
schedule.rs

1//! *When* to send — RFC 6762's probing, announcing, conflict resolution and rate limits.
2//!
3//! [`responder`](super::responder) decides what a message says; this decides when one may be
4//! sent. Core §4.3 delegates the rules: the instance name "SHALL be unique within the
5//! namespace of the local network", and "name conflict detection is described in Section 9
6//! ('Conflict Resolution') of the Multicast DNS specification".
7//!
8//! Sans-I/O, in the same shape as [`Mrp`](crate::exchange::Mrp): the caller polls with the
9//! current [`Instant`] and a value from its [`Rng`](crate::platform::Rng), gets an [`Action`]
10//! or nothing, and asks [`Schedule::wake_at`] when to come back. A 750 ms claim window is then
11//! testable in microseconds.
12//!
13//! ```
14//! use matter_kit::discovery::schedule::{Action, Schedule};
15//! use matter_kit::platform::{Duration, Instant};
16//!
17//! let mut schedule = Schedule::new();
18//! let mut now = Instant::ZERO;
19//! schedule.start(now, 0);
20//!
21//! // Three probes, 250 ms apart (§8.1) — nothing may be advertised until they pass.
22//! for _ in 0..3 {
23//!     now = schedule.wake_at().unwrap();
24//!     assert_eq!(schedule.poll(now), Some(Action::Probe));
25//!     assert!(!schedule.may_respond());
26//! }
27//!
28//! // 250 ms after the third probe with no conflicting answer, the name is ours.
29//! now = schedule.wake_at().unwrap();
30//! assert_eq!(schedule.poll(now), Some(Action::Announce));
31//! assert!(schedule.may_respond());
32//! # Ok::<(), matter_kit::Error>(())
33//! ```
34
35use crate::platform::{Duration, Instant};
36
37/// RFC 6762 §8.1: the random delay before the first probe, "uniformly distributed in the
38/// range 0-250 ms".
39///
40/// It exists for the case where "several devices are powered on simultaneously" — without it
41/// every device on a freshly powered hub probes in the same millisecond and they all conflict
42/// with each other.
43pub const PROBE_JITTER: Duration = Duration::from_millis(250);
44
45/// RFC 6762 §8.1: "250 ms after the first query, the host should send a second; then, 250 ms
46/// after that, a third."
47pub const PROBE_INTERVAL: Duration = Duration::from_millis(250);
48
49/// RFC 6762 §8.1: "If, by 250 ms after the third probe, no conflicting Multicast DNS
50/// responses have been received, the host may move to the next step, announcing."
51pub const PROBES: u8 = 3;
52
53/// RFC 6762 §8.2: a host that loses a simultaneous-probe tiebreak "defers to the winning host
54/// by waiting one second, and then begins probing for this record again".
55pub const TIEBREAK_DEFER: Duration = Duration::from_secs(1);
56
57/// RFC 6762 §8.1: "If fifteen conflicts occur within any ten-second period, then the host MUST
58/// wait at least five seconds before each successive additional probe attempt."
59pub const CONFLICT_BURST: u8 = 15;
60
61/// The window the fifteen conflicts of [`CONFLICT_BURST`] are counted over.
62pub const CONFLICT_WINDOW: Duration = Duration::from_secs(10);
63
64/// How long a throttled responder waits before each further probe attempt (§8.1).
65pub const CONFLICT_BACKOFF: Duration = Duration::from_secs(5);
66
67/// RFC 6762 §8.3: "The Multicast DNS responder MUST send at least two unsolicited responses,
68/// one second apart."
69pub const ANNOUNCE_INTERVAL: Duration = Duration::from_secs(1);
70
71/// The minimum number of announcements §8.3 requires.
72pub const ANNOUNCEMENTS_MIN: u8 = 2;
73
74/// RFC 6762 §8.3: "a responder MAY send up to eight unsolicited responses, provided that the
75/// interval between unsolicited responses increases by at least a factor of two with every
76/// response sent."
77pub const ANNOUNCEMENTS_MAX: u8 = 8;
78
79/// RFC 6762 §6: "a Multicast DNS responder MUST NOT … multicast a record on a given interface
80/// until at least one second has elapsed since the last time that record was multicast on that
81/// particular interface."
82pub const MULTICAST_INTERVAL: Duration = Duration::from_secs(1);
83
84/// The one exception to [`MULTICAST_INTERVAL`], for defending a name against a probe (§6).
85///
86/// "In this special case only, when responding via multicast to a probe, a Multicast DNS
87/// responder is only required to delay its transmission as necessary to ensure an interval of
88/// at least 250 ms since the last time the record was multicast on that interface." A probing
89/// host has 750 ms in total to hear a defence, so a full second of silence would hand it the
90/// name.
91pub const DEFEND_INTERVAL: Duration = Duration::from_millis(250);
92
93/// RFC 6762 §6: the lower bound of the delay before answering a query that others may also
94/// answer.
95///
96/// "The reason for requiring that the delay be at least 20 ms is to accommodate the situation
97/// where two or more query packets are sent back-to-back" — the responder can then aggregate
98/// its answers into one message.
99pub const SHARED_DELAY_MIN: Duration = Duration::from_millis(20);
100
101/// RFC 6762 §6: the upper bound of that delay.
102pub const SHARED_DELAY_MAX: Duration = Duration::from_millis(120);
103
104/// RFC 6762 §6: the lower bound of the delay when the query has the TC bit set, "to allow
105/// enough time for all the Known-Answer packets to arrive".
106pub const KNOWN_ANSWER_DELAY_MIN: Duration = Duration::from_millis(400);
107
108/// RFC 6762 §6: the upper bound of that delay.
109pub const KNOWN_ANSWER_DELAY_MAX: Duration = Duration::from_millis(500);
110
111/// What the caller should send, now.
112///
113/// Every variant is a multicast to [`MDNS_IPV6_GROUP`](super::MDNS_IPV6_GROUP) except
114/// [`Action::Rename`], which is not a packet at all.
115#[derive(Debug, Clone, Copy, PartialEq, Eq)]
116#[non_exhaustive]
117pub enum Action {
118    /// Multicast a probe query (§8.1).
119    ///
120    /// One question per name being claimed, qtype `ANY`, with the unicast-response bit set —
121    /// "the probes SHOULD be sent as 'QU' questions … to allow a defending host to respond
122    /// immediately via unicast". The proposed records go in the **Authority** section, which
123    /// is what makes [`tiebreak`] possible for anyone else probing at the same moment.
124    Probe,
125    /// Multicast an unsolicited response carrying every record (§8.3).
126    ///
127    /// Unique records — SRV, TXT, AAAA — carry the cache-flush bit; the shared PTRs do not.
128    Announce,
129    /// Multicast every record with a TTL of zero (§10.1), then stop advertising.
130    Goodbye,
131    /// Probing lost: another responder owns the name.
132    ///
133    /// §9's recommended course is to "programmatically change the resource record name in an
134    /// attempt to find a new name that is unique" — for a Matter commissionable node that is
135    /// §4.3.1's own rule, "a new pseudo-randomly selected 64-bit temporary unique identifier
136    /// SHALL be generated". Nothing may be advertised under the old name; call
137    /// [`Schedule::renamed`] once a new one is chosen.
138    Rename,
139}
140
141/// The phase a schedule is in.
142#[derive(Debug, Clone, Copy, PartialEq, Eq)]
143#[non_exhaustive]
144pub enum Phase {
145    /// Not advertising, nothing due.
146    Idle,
147    /// §8.1's probes are in progress. The name is not yet ours and queries go unanswered.
148    Probing,
149    /// §8.3's announcements are in progress. The name is ours.
150    Announcing,
151    /// Probed and announced; answering queries.
152    Established,
153    /// A conflict was lost. The caller owes a new name before anything else can happen.
154    Renaming,
155    /// A goodbye is due, after which the schedule returns to [`Phase::Idle`].
156    Leaving,
157}
158
159/// The startup, conflict and rate-limit schedule of one advertised name.
160///
161/// One per *name*, not per node: a node advertising a commissionable service and an
162/// operational service claims two independent names and can be probing for one while the other
163/// is established.
164#[derive(Debug, Clone)]
165pub struct Schedule {
166    phase: Phase,
167    /// When the next action in the current phase is due.
168    due: Instant,
169    /// How many probes or announcements have gone out in this phase.
170    sent: u8,
171    /// How many announcements this schedule sends, in `ANNOUNCEMENTS_MIN..=ANNOUNCEMENTS_MAX`.
172    announcements: u8,
173    /// §8.1's fifteen-in-ten-seconds counter, and when its window opened.
174    conflicts: u8,
175    window: Instant,
176    throttled: bool,
177}
178
179impl Default for Schedule {
180    fn default() -> Self {
181        Self::new()
182    }
183}
184
185impl Schedule {
186    /// An idle schedule, advertising nothing.
187    #[must_use]
188    pub const fn new() -> Self {
189        Self {
190            phase: Phase::Idle,
191            due: Instant::ZERO,
192            sent: 0,
193            announcements: ANNOUNCEMENTS_MIN,
194            conflicts: 0,
195            window: Instant::ZERO,
196            throttled: false,
197        }
198    }
199
200    /// Sends `n` announcements rather than §8.3's minimum of two, clamped to `2..=8`.
201    ///
202    /// More announcements is more robustness against a lost packet and more traffic; §8.3
203    /// permits up to eight and requires the interval to double each time, which this does.
204    #[must_use]
205    pub const fn with_announcements(mut self, n: u8) -> Self {
206        self.announcements = if n < ANNOUNCEMENTS_MIN {
207            ANNOUNCEMENTS_MIN
208        } else if n > ANNOUNCEMENTS_MAX {
209            ANNOUNCEMENTS_MAX
210        } else {
211            n
212        };
213        self
214    }
215
216    /// The phase the schedule is in.
217    #[must_use]
218    pub const fn phase(&self) -> Phase {
219        self.phase
220    }
221
222    /// Whether the responder may answer queries for this name.
223    ///
224    /// False until the first announcement: RFC 6762 §6 lets a responder answer only with
225    /// records "for which that responder is explicitly authoritative", and a name being probed
226    /// for is not yet owned. Answering during probing is how two devices both conclude they
227    /// won.
228    #[must_use]
229    pub const fn may_respond(&self) -> bool {
230        matches!(self.phase, Phase::Announcing | Phase::Established)
231    }
232
233    /// Begins the startup sequence of §8 — probe, then announce.
234    ///
235    /// §8: a responder does this "whenever \[it\] starts up, wakes up from sleep, receives an
236    /// indication of a network interface 'Link Change' event, or has any other reason to
237    /// believe that its network connectivity may have changed in some relevant way". It is
238    /// also what §4.3.1 requires when a node enters commissioning mode under a new instance
239    /// name.
240    ///
241    /// `randomness` supplies §8.1's 0–250 ms delay; any value will do, its low bits are used.
242    pub fn start(&mut self, now: Instant, randomness: u32) {
243        self.phase = Phase::Probing;
244        self.sent = 0;
245        self.due = now.saturating_add(self.first_probe_delay(randomness));
246    }
247
248    /// Re-announces after the record data changed, without re-probing (§8.4).
249    ///
250    /// "At any time, if the rdata of any of a host's Multicast DNS records changes, the host
251    /// MUST repeat the Announcing step … The host does not need to repeat the Probing step
252    /// because it has already established unique ownership of that name." A Matter node does
253    /// this every time a TXT key moves — `CM` when a commissioning window opens, `SII`/`SAI`
254    /// when the node changes ICD mode.
255    ///
256    /// Ignored while probing or renaming, where the name is not owned and an announcement
257    /// would be a claim the node has no right to make.
258    pub fn updated(&mut self, now: Instant) {
259        if matches!(self.phase, Phase::Announcing | Phase::Established) {
260            self.phase = Phase::Announcing;
261            self.sent = 0;
262            self.due = now;
263        }
264    }
265
266    /// A conflicting response arrived (§9).
267    ///
268    /// A conflict is "a record with the same name, rrtype and rrclass, but inconsistent
269    /// rdata", seen in **any** section of any response. The two cases are different rules:
270    ///
271    /// * **Probing** — §8.1: "the probing host MUST defer to the existing host, and SHOULD
272    ///   choose new names". The next [`Schedule::poll`] yields [`Action::Rename`].
273    /// * **Announced or established** — §9: "reset its conflicted unique record to probing
274    ///   state, and go through the startup steps". It does *not* rename yet; only a probe that
275    ///   draws a conflicting answer loses the name.
276    ///
277    /// Collapsing them either way is wrong: rename-always gives up names the node would have
278    /// won, re-probe-always makes two probing devices loop forever.
279    pub fn on_conflict(&mut self, now: Instant, randomness: u32) {
280        self.note_conflict(now);
281        match self.phase {
282            Phase::Probing => {
283                self.phase = Phase::Renaming;
284                self.due = now;
285                self.sent = 0;
286            }
287            Phase::Announcing | Phase::Established => self.start(now, randomness),
288            Phase::Idle | Phase::Renaming | Phase::Leaving => {}
289        }
290    }
291
292    /// A simultaneous probe was lost on the tiebreak of §8.2.
293    ///
294    /// Not a conflict: the other host has not claimed the name yet, it merely proposed
295    /// lexicographically later data. "\[The host\] defers to the winning host by waiting one
296    /// second, and then begins probing for this record again" — and the second exists to
297    /// outlive a stale probe packet echoed back by a switch, which is why the name is *not*
298    /// abandoned here.
299    pub fn on_tiebreak_loss(&mut self, now: Instant) {
300        if matches!(self.phase, Phase::Probing) {
301            self.sent = 0;
302            self.due = now.saturating_add(TIEBREAK_DEFER);
303        }
304    }
305
306    /// A new name was chosen after [`Action::Rename`]; probing restarts.
307    ///
308    /// §9 step 3 asks that the chosen name be recorded in persistent storage "so that the
309    /// device will use the same name the next time it is power-cycled". A Matter commissionable
310    /// node is the exception and must *not*: §4.3.1 requires a new random instance name on
311    /// every boot, precisely so that it cannot be tracked.
312    pub fn renamed(&mut self, now: Instant, randomness: u32) {
313        if matches!(self.phase, Phase::Renaming) {
314            self.start(now, randomness);
315        }
316    }
317
318    /// Stops advertising, sending §10.1's goodbye first.
319    ///
320    /// The goodbye is "the same resource record name, rrtype, rrclass, and rdata, but an RR
321    /// TTL of zero", which deletes the entry from every cache on the link rather than leaving
322    /// it to expire — a device that reboots into a new instance name would otherwise be two
323    /// devices as far as every commissioner is concerned, for the record's full TTL.
324    ///
325    /// Only a name that was actually announced says goodbye; there is nothing in anyone's
326    /// cache for a name that never got past probing.
327    pub fn stop(&mut self, now: Instant) {
328        if self.may_respond() {
329            self.phase = Phase::Leaving;
330            self.due = now;
331            self.sent = 0;
332        } else {
333            self.phase = Phase::Idle;
334        }
335    }
336
337    /// When the next action becomes due, or `None` if nothing is scheduled.
338    #[must_use]
339    pub const fn wake_at(&self) -> Option<Instant> {
340        match self.phase {
341            Phase::Idle | Phase::Established => None,
342            _ => Some(self.due),
343        }
344    }
345
346    /// The action due at `now`, advancing the schedule, or `None` if nothing is due yet.
347    ///
348    /// Yields at most one action per call. A caller that cannot send — the interface is down,
349    /// the buffer is busy — simply does not call again until it can, and the schedule stays
350    /// where it is; nothing here assumes the send happened.
351    ///
352    /// [`Action::Rename`] is the exception: it repeats on every poll until
353    /// [`Schedule::renamed`], because the schedule cannot make progress without a new name and
354    /// a caller that dropped the first one would otherwise have a node that is silently
355    /// invisible with nothing to explain why.
356    pub fn poll(&mut self, now: Instant) -> Option<Action> {
357        if self.wake_at().is_none_or(|due| now < due) {
358            return None;
359        }
360        match self.phase {
361            // §8.1's window closes 250 ms *after* the third probe, not at it: until then a
362            // conflicting answer still costs the name, so the phase stays `Probing` and
363            // `may_respond` stays false through the whole window.
364            Phase::Probing if self.sent >= PROBES => {
365                self.phase = Phase::Announcing;
366                self.sent = 0;
367                Some(self.announce(now))
368            }
369            Phase::Probing => Some(self.probe(now)),
370            Phase::Announcing => Some(self.announce(now)),
371            Phase::Renaming => Some(Action::Rename),
372            Phase::Leaving => {
373                self.phase = Phase::Idle;
374                Some(Action::Goodbye)
375            }
376            // `wake_at` returned `None` for these, so the guard above already returned.
377            Phase::Idle | Phase::Established => None,
378        }
379    }
380
381    fn probe(&mut self, now: Instant) -> Action {
382        self.sent = self.sent.saturating_add(1);
383        // §8.1's success condition is silence for a further 250 ms *after* the third probe,
384        // not the third probe itself — so the same interval schedules both the next probe and
385        // the check that ends the sequence.
386        self.due = now.saturating_add(PROBE_INTERVAL);
387        Action::Probe
388    }
389
390    fn announce(&mut self, now: Instant) -> Action {
391        // §8.3: "at least two unsolicited responses, one second apart", and if there are more,
392        // "the interval … increases by at least a factor of two with every response sent".
393        let mut interval = ANNOUNCE_INTERVAL;
394        for _ in 0..self.sent {
395            interval = interval.saturating_add(interval);
396        }
397        self.sent = self.sent.saturating_add(1);
398        if self.sent >= self.announcements {
399            self.phase = Phase::Established;
400        } else {
401            self.due = now.saturating_add(interval);
402        }
403        Action::Announce
404    }
405
406    /// §8.1's first-probe delay, plus §8.1's five-second throttle if conflicts are flooding.
407    fn first_probe_delay(&self, randomness: u32) -> Duration {
408        let jitter = Duration::from_micros(
409            u64::from(randomness)
410                .checked_rem(PROBE_JITTER.as_micros())
411                .unwrap_or(0),
412        );
413        if self.throttled {
414            CONFLICT_BACKOFF.saturating_add(jitter)
415        } else {
416            jitter
417        }
418    }
419
420    /// Counts a conflict into §8.1's rolling ten-second window.
421    fn note_conflict(&mut self, now: Instant) {
422        if self.conflicts == 0 || now.saturating_duration_since(self.window) >= CONFLICT_WINDOW {
423            self.window = now;
424            self.conflicts = 1;
425            self.throttled = false;
426        } else {
427            self.conflicts = self.conflicts.saturating_add(1);
428        }
429        if self.conflicts >= CONFLICT_BURST {
430            self.throttled = true;
431        }
432    }
433
434    /// Whether §8.1's fifteen-conflicts-in-ten-seconds throttle is in force.
435    ///
436    /// "This is to help ensure that, in the event of software bugs or other unanticipated
437    /// problems, errant hosts do not flood the network with a continuous stream of multicast
438    /// traffic." Exposed because a device that reaches this state has something wrong with it
439    /// and should say so in a log.
440    #[must_use]
441    pub const fn is_throttled(&self) -> bool {
442        self.throttled
443    }
444}
445
446/// What kind of query is being answered, which decides the delay before answering (§6).
447#[derive(Debug, Clone, Copy, PartialEq, Eq)]
448#[non_exhaustive]
449pub enum Answering {
450    /// A probe query from another host, asking for a name this responder owns.
451    ///
452    /// §6: "answering such probe queries to defend a unique record is a high priority and
453    /// needs to be done without delay". The prober has 750 ms in total.
454    Probe,
455    /// A query every one of whose answers is a record this responder has verified unique.
456    ///
457    /// §6: it "SHOULD NOT impose any random delay before responding" — there is no one else to
458    /// collide with.
459    Unique,
460    /// A query whose answer is a shared record, such as a service PTR.
461    ///
462    /// §6: "each responder SHOULD delay its response by a random amount of time selected with
463    /// uniform random distribution in the range 20-120 ms". This is the common case for a
464    /// `_matterc._udp` browse, which every commissionable node on the link answers.
465    Shared,
466    /// A query with the TC bit set, so Known-Answer packets are still coming (§7.2).
467    ///
468    /// §6: delay 400–500 ms "to allow enough time for all the Known-Answer packets to arrive".
469    KnownAnswerSuppression,
470}
471
472/// How long to wait before answering, per RFC 6762 §6.
473///
474/// `randomness` is any value; its low bits pick the point in the range.
475#[must_use]
476pub fn response_delay(answering: Answering, randomness: u32) -> Duration {
477    let pick = |low: Duration, high: Duration| -> Duration {
478        let span = high.as_micros().saturating_sub(low.as_micros());
479        let draw = u64::from(randomness).checked_rem(span).unwrap_or(0);
480        low.saturating_add(Duration::from_micros(draw))
481    };
482    match answering {
483        Answering::Probe | Answering::Unique => Duration::ZERO,
484        Answering::Shared => pick(SHARED_DELAY_MIN, SHARED_DELAY_MAX),
485        Answering::KnownAnswerSuppression => pick(KNOWN_ANSWER_DELAY_MIN, KNOWN_ANSWER_DELAY_MAX),
486    }
487}
488
489/// RFC 6762 §6's per-record multicast rate limit.
490///
491/// "A Multicast DNS responder MUST NOT (except in the one special case of answering probe
492/// queries) multicast a record on a given interface until at least one second has elapsed
493/// since the last time that record was multicast on that particular interface."
494///
495/// The limit is *per record*; this tracks it per **record set**, one slot per advertisement,
496/// which is coarser and therefore always at least as conservative: it can delay a record that
497/// was individually due, never send one that was not. A per-record table would need a key per
498/// name and type — around eighty entries for the eight advertisements a Matter node may carry
499/// — to buy back at most a few hundred milliseconds on a link this crate is trying to keep
500/// quiet anyway (§4.3: "excessive use of multicast would be detrimental").
501#[derive(Debug, Clone)]
502pub struct MulticastLimiter<const N: usize> {
503    /// When each slot was last multicast, and whether it ever was.
504    last: [(Instant, bool); N],
505}
506
507impl<const N: usize> Default for MulticastLimiter<N> {
508    fn default() -> Self {
509        Self::new()
510    }
511}
512
513impl<const N: usize> MulticastLimiter<N> {
514    /// A limiter that has sent nothing.
515    #[must_use]
516    pub const fn new() -> Self {
517        Self {
518            last: [(Instant::ZERO, false); N],
519        }
520    }
521
522    /// The earliest instant at which slot `index` may be multicast again.
523    ///
524    /// `defending` selects §6's probe exception — 250 ms instead of a second. An unknown index
525    /// may be sent immediately; a limiter cannot rate-limit what it is not tracking, and
526    /// pretending otherwise would silently drop answers.
527    #[must_use]
528    pub fn earliest(&self, index: usize, defending: bool) -> Instant {
529        match self.last.get(index) {
530            Some(&(_, false)) | None => Instant::ZERO,
531            Some(&(at, true)) => at.saturating_add(if defending {
532                DEFEND_INTERVAL
533            } else {
534                MULTICAST_INTERVAL
535            }),
536        }
537    }
538
539    /// Whether slot `index` may be multicast at `now`.
540    #[must_use]
541    pub fn may_send(&self, index: usize, now: Instant, defending: bool) -> bool {
542        now >= self.earliest(index, defending)
543    }
544
545    /// Records that slot `index` was multicast at `now`.
546    pub fn sent(&mut self, index: usize, now: Instant) {
547        if let Some(slot) = self.last.get_mut(index) {
548            *slot = (now, true);
549        }
550    }
551}
552
553/// The outcome of RFC 6762 §8.2's simultaneous-probe tiebreak.
554#[derive(Debug, Clone, Copy, PartialEq, Eq)]
555#[non_exhaustive]
556pub enum Tiebreak {
557    /// Our proposed data is lexicographically later: "it simply ignores the other host's
558    /// probe".
559    Won,
560    /// The other host's data is lexicographically later. Defer for one second, then probe
561    /// again — [`Schedule::on_tiebreak_loss`].
562    Lost,
563    /// The two record sets are identical.
564    ///
565    /// §8.2.1: "this indicates that two devices are advertising identical sets of records, as
566    /// is sometimes done for fault tolerance, and there is, in fact, no conflict."
567    Identical,
568}
569
570/// One record, reduced to what §8.2 compares: class, type, and uncompressed RDATA.
571///
572/// "The determination of 'lexicographically later' is performed by first comparing the record
573/// class (excluding the cache-flush bit …), then the record type, then raw comparison of the
574/// binary content of the rdata without regard for meaning or structure."
575///
576/// The RDATA must be *uncompressed* — "the details of how a particular name is compressed is
577/// an artifact of how and where the record is written into the DNS message; it is not an
578/// intrinsic property of the resource record itself" — so a caller building one from a
579/// received message uses the decompressed name, not the bytes off the wire.
580#[derive(Debug, Clone, Copy, PartialEq, Eq)]
581pub struct Tiebreaker<'a> {
582    /// The record class with the cache-flush bit masked off — `CLASS_IN` for everything Matter
583    /// publishes.
584    pub class: u16,
585    /// The record type's wire value.
586    pub kind: u16,
587    /// The uncompressed RDATA.
588    pub rdata: &'a [u8],
589}
590
591impl Tiebreaker<'_> {
592    /// §8.2's ordering: class, then type, then RDATA bytes as **unsigned** values.
593    ///
594    /// "Note that it is vital that the bytes are interpreted as UNSIGNED values in the range
595    /// 0-255, or the wrong outcome may result" — the RFC's own example is
596    /// `169.254.99.200` against `169.254.200.50`, where reading 200 as `-56` picks the wrong
597    /// winner. Rust's `u8` makes that the default rather than a hazard, and the test keeps it
598    /// that way.
599    ///
600    /// "or one of the resource records runs out of rdata (in which case, the resource record
601    /// which still has remaining data first is deemed lexicographically later)" — which is
602    /// exactly a byte-slice comparison, since a prefix sorts before what extends it.
603    #[must_use]
604    pub fn cmp_lexicographic(&self, other: &Self) -> core::cmp::Ordering {
605        self.class
606            .cmp(&other.class)
607            .then(self.kind.cmp(&other.kind))
608            .then_with(|| self.rdata.cmp(other.rdata))
609    }
610}
611
612/// RFC 6762 §8.2.1's tiebreak over two *sorted* sets of records.
613///
614/// Both sides must already be "sorted into order … using the same lexicographical order",
615/// then they are "compared pairwise … until a difference is found". Sorting is the caller's
616/// because this crate does not allocate: a caller with a fixed array sorts it in place.
617///
618/// "If either list of records runs out of records before any difference is found, then the
619/// list with records remaining is deemed to have won the tiebreak."
620#[must_use]
621pub fn tiebreak<'a, 'b>(
622    ours: impl IntoIterator<Item = Tiebreaker<'a>>,
623    theirs: impl IntoIterator<Item = Tiebreaker<'b>>,
624) -> Tiebreak {
625    let mut ours = ours.into_iter();
626    let mut theirs = theirs.into_iter();
627    loop {
628        return match (ours.next(), theirs.next()) {
629            (None, None) => Tiebreak::Identical,
630            (Some(_), None) => Tiebreak::Won,
631            (None, Some(_)) => Tiebreak::Lost,
632            (Some(mine), Some(yours)) => match mine.cmp_lexicographic(&yours) {
633                core::cmp::Ordering::Equal => continue,
634                core::cmp::Ordering::Greater => Tiebreak::Won,
635                core::cmp::Ordering::Less => Tiebreak::Lost,
636            },
637        };
638    }
639}
640
641#[cfg(test)]
642mod tests {
643    use super::*;
644
645    type Seen<T> = heapless::Vec<T, 32>;
646
647    /// Runs the schedule forward, always at the instant the next action is due.
648    fn drive(schedule: &mut Schedule, steps: usize) -> (Instant, Seen<Action>) {
649        let mut now = Instant::ZERO;
650        let mut seen = Seen::new();
651        for _ in 0..steps {
652            let Some(due) = schedule.wake_at() else { break };
653            now = due;
654            if let Some(action) = schedule.poll(now) {
655                seen.push(action).expect("fewer than 32 actions");
656            }
657        }
658        (now, seen)
659    }
660
661    #[test]
662    fn startup_probes_three_times_then_announces_twice() {
663        let mut schedule = Schedule::new();
664        schedule.start(Instant::ZERO, 0);
665        let (_, actions) = drive(&mut schedule, 8);
666        assert_eq!(
667            actions.as_slice(),
668            &[
669                Action::Probe,
670                Action::Probe,
671                Action::Probe,
672                Action::Announce,
673                Action::Announce
674            ]
675        );
676        assert_eq!(schedule.phase(), Phase::Established);
677    }
678
679    #[test]
680    fn the_probes_are_250ms_apart_and_the_name_is_claimed_750ms_in() {
681        let mut schedule = Schedule::new();
682        // randomness 0 means no jitter, so the arithmetic is exact.
683        schedule.start(Instant::ZERO, 0);
684        let mut at = [Instant::ZERO; 4];
685        for slot in &mut at {
686            let due = schedule.wake_at().expect("scheduled");
687            *slot = due;
688            let _ = schedule.poll(due);
689        }
690        assert_eq!(at[0], Instant::ZERO);
691        assert_eq!(at[1], Instant::ZERO.saturating_add(PROBE_INTERVAL));
692        assert_eq!(
693            at[2],
694            Instant::ZERO.saturating_add(Duration::from_millis(500))
695        );
696        // §8.1: the name is not claimed at the third probe but 250 ms after it.
697        assert_eq!(
698            at[3],
699            Instant::ZERO.saturating_add(Duration::from_millis(750))
700        );
701    }
702
703    #[test]
704    fn the_first_probe_is_jittered_within_250ms() {
705        for randomness in [0u32, 1, 999, 249_999, 250_000, u32::MAX] {
706            let mut schedule = Schedule::new();
707            schedule.start(Instant::ZERO, randomness);
708            let due = schedule.wake_at().expect("scheduled");
709            assert!(due.saturating_duration_since(Instant::ZERO) < PROBE_JITTER);
710        }
711    }
712
713    #[test]
714    fn nothing_is_answered_until_the_first_announcement() {
715        let mut schedule = Schedule::new();
716        assert!(!schedule.may_respond());
717        schedule.start(Instant::ZERO, 0);
718        for _ in 0..PROBES {
719            let due = schedule.wake_at().expect("scheduled");
720            assert_eq!(schedule.poll(due), Some(Action::Probe));
721            assert!(!schedule.may_respond(), "a probed name is not yet owned");
722        }
723        let due = schedule.wake_at().expect("scheduled");
724        assert_eq!(schedule.poll(due), Some(Action::Announce));
725        assert!(schedule.may_respond());
726    }
727
728    #[test]
729    fn announcement_intervals_double() {
730        let mut schedule = Schedule::new().with_announcements(4);
731        schedule.start(Instant::ZERO, 0);
732        let mut announced = Seen::<Instant>::new();
733        for _ in 0..16 {
734            let Some(due) = schedule.wake_at() else { break };
735            if schedule.poll(due) == Some(Action::Announce) {
736                let _ = announced.push(due);
737            }
738        }
739        assert_eq!(announced.len(), 4);
740        let gap = |a: usize, b: usize| announced[b].saturating_duration_since(announced[a]);
741        assert_eq!(gap(0, 1), Duration::from_secs(1));
742        assert_eq!(gap(1, 2), Duration::from_secs(2));
743        assert_eq!(gap(2, 3), Duration::from_secs(4));
744    }
745
746    #[test]
747    fn announcement_count_is_clamped_to_the_rfcs_range() {
748        assert_eq!(Schedule::new().with_announcements(0).announcements, 2);
749        assert_eq!(Schedule::new().with_announcements(1).announcements, 2);
750        assert_eq!(Schedule::new().with_announcements(200).announcements, 8);
751    }
752
753    #[test]
754    fn a_conflict_while_probing_renames() {
755        let mut schedule = Schedule::new();
756        schedule.start(Instant::ZERO, 0);
757        let due = schedule.wake_at().expect("scheduled");
758        assert_eq!(schedule.poll(due), Some(Action::Probe));
759        schedule.on_conflict(due, 0);
760        assert_eq!(schedule.phase(), Phase::Renaming);
761        assert_eq!(schedule.poll(due), Some(Action::Rename));
762        // Nothing happens until a new name is chosen.
763        assert_eq!(schedule.poll(due), Some(Action::Rename));
764        schedule.renamed(due, 0);
765        assert_eq!(schedule.phase(), Phase::Probing);
766    }
767
768    #[test]
769    fn a_conflict_once_established_reprobes_rather_than_renaming() {
770        let mut schedule = Schedule::new();
771        schedule.start(Instant::ZERO, 0);
772        let (now, _) = drive(&mut schedule, 8);
773        assert_eq!(schedule.phase(), Phase::Established);
774        schedule.on_conflict(now, 0);
775        // §9 sends it back to probing; the name is only lost if that probe draws an answer.
776        assert_eq!(schedule.phase(), Phase::Probing);
777        assert!(!schedule.may_respond());
778    }
779
780    #[test]
781    fn a_tiebreak_loss_defers_a_second_and_reprobes_without_renaming() {
782        let mut schedule = Schedule::new();
783        schedule.start(Instant::ZERO, 0);
784        let due = schedule.wake_at().expect("scheduled");
785        let _ = schedule.poll(due);
786        schedule.on_tiebreak_loss(due);
787        assert_eq!(schedule.phase(), Phase::Probing);
788        assert_eq!(
789            schedule.wake_at().expect("scheduled"),
790            due.saturating_add(TIEBREAK_DEFER)
791        );
792        // And the probe sequence starts over rather than continuing from where it was.
793        let (_, actions) = drive(&mut schedule, 8);
794        assert_eq!(
795            actions.iter().filter(|a| **a == Action::Probe).count(),
796            usize::from(PROBES)
797        );
798    }
799
800    #[test]
801    fn fifteen_conflicts_in_ten_seconds_throttles_the_next_probe() {
802        let mut schedule = Schedule::new();
803        let mut now = Instant::ZERO;
804        schedule.start(now, 0);
805        for _ in 0..CONFLICT_BURST {
806            now = now.saturating_add(Duration::from_millis(100));
807            schedule.on_conflict(now, 0);
808            if schedule.phase() == Phase::Renaming {
809                let _ = schedule.poll(now);
810                schedule.renamed(now, 0);
811            }
812        }
813        assert!(schedule.is_throttled());
814        let due = schedule.wake_at().expect("scheduled");
815        assert!(due.saturating_duration_since(now) >= CONFLICT_BACKOFF);
816    }
817
818    #[test]
819    fn conflicts_spread_past_the_window_do_not_throttle() {
820        let mut schedule = Schedule::new();
821        let mut now = Instant::ZERO;
822        schedule.start(now, 0);
823        for _ in 0..40 {
824            now = now.saturating_add(CONFLICT_WINDOW);
825            schedule.on_conflict(now, 0);
826            if schedule.phase() == Phase::Renaming {
827                let _ = schedule.poll(now);
828                schedule.renamed(now, 0);
829            }
830            assert!(!schedule.is_throttled());
831        }
832    }
833
834    #[test]
835    fn an_update_reannounces_without_reprobing() {
836        let mut schedule = Schedule::new();
837        schedule.start(Instant::ZERO, 0);
838        let (now, _) = drive(&mut schedule, 8);
839        schedule.updated(now);
840        let (_, actions) = drive(&mut schedule, 8);
841        assert_eq!(actions.as_slice(), &[Action::Announce, Action::Announce]);
842    }
843
844    #[test]
845    fn an_update_while_probing_is_ignored() {
846        let mut schedule = Schedule::new();
847        schedule.start(Instant::ZERO, 0);
848        let due = schedule.wake_at().expect("scheduled");
849        let _ = schedule.poll(due);
850        schedule.updated(due);
851        assert_eq!(schedule.phase(), Phase::Probing);
852    }
853
854    #[test]
855    fn stopping_an_established_name_says_goodbye_once() {
856        let mut schedule = Schedule::new();
857        schedule.start(Instant::ZERO, 0);
858        let (now, _) = drive(&mut schedule, 8);
859        schedule.stop(now);
860        assert_eq!(schedule.poll(now), Some(Action::Goodbye));
861        assert_eq!(schedule.phase(), Phase::Idle);
862        assert_eq!(schedule.wake_at(), None);
863        assert_eq!(schedule.poll(now), None);
864    }
865
866    #[test]
867    fn stopping_a_name_that_was_never_announced_says_nothing() {
868        let mut schedule = Schedule::new();
869        schedule.start(Instant::ZERO, 0);
870        let due = schedule.wake_at().expect("scheduled");
871        let _ = schedule.poll(due);
872        schedule.stop(due);
873        assert_eq!(schedule.phase(), Phase::Idle);
874        assert_eq!(schedule.poll(due), None);
875    }
876
877    #[test]
878    fn an_established_schedule_has_no_wakeup() {
879        let mut schedule = Schedule::new();
880        schedule.start(Instant::ZERO, 0);
881        let (now, _) = drive(&mut schedule, 8);
882        assert_eq!(schedule.wake_at(), None, "§8.3: no periodic announcements");
883        assert_eq!(
884            schedule.poll(now.saturating_add(Duration::from_secs(3600))),
885            None
886        );
887    }
888
889    #[test]
890    fn polling_early_yields_nothing_and_does_not_advance() {
891        let mut schedule = Schedule::new();
892        schedule.start(Instant::ZERO, 12_345);
893        let due = schedule.wake_at().expect("scheduled");
894        assert_eq!(schedule.poll(Instant::ZERO), None);
895        assert_eq!(schedule.wake_at(), Some(due));
896    }
897
898    #[test]
899    fn response_delays_match_the_rfcs_ranges() {
900        // The bounds are written out rather than taken from the constants: a test that
901        // compares a constant against itself passes however wrong the constant is.
902        let ms = Duration::from_millis;
903        for randomness in [0u32, 7, 5_000, 99_999, u32::MAX] {
904            assert_eq!(response_delay(Answering::Probe, randomness), Duration::ZERO);
905            assert_eq!(
906                response_delay(Answering::Unique, randomness),
907                Duration::ZERO
908            );
909            // §6: "uniform random distribution in the range 20-120 ms".
910            let shared = response_delay(Answering::Shared, randomness);
911            assert!(shared >= ms(20) && shared < ms(120), "{shared:?}");
912            // §6: "in the range 400-500 ms".
913            let known = response_delay(Answering::KnownAnswerSuppression, randomness);
914            assert!(known >= ms(400) && known < ms(500), "{known:?}");
915        }
916        // And the range is actually used: two different draws give two different delays.
917        assert_ne!(
918            response_delay(Answering::Shared, 0),
919            response_delay(Answering::Shared, 50_000)
920        );
921    }
922
923    #[test]
924    fn the_rfcs_own_numbers_are_the_constants() {
925        // Every timing in this module is a number RFC 6762 states outright. Spelling them out
926        // once means a typo in a constant fails here rather than on a link somewhere.
927        assert_eq!(PROBE_JITTER, Duration::from_millis(250));
928        assert_eq!(PROBE_INTERVAL, Duration::from_millis(250));
929        assert_eq!(PROBES, 3);
930        assert_eq!(TIEBREAK_DEFER, Duration::from_secs(1));
931        assert_eq!(CONFLICT_BURST, 15);
932        assert_eq!(CONFLICT_WINDOW, Duration::from_secs(10));
933        assert_eq!(CONFLICT_BACKOFF, Duration::from_secs(5));
934        assert_eq!(ANNOUNCE_INTERVAL, Duration::from_secs(1));
935        assert_eq!(ANNOUNCEMENTS_MIN, 2);
936        assert_eq!(ANNOUNCEMENTS_MAX, 8);
937        assert_eq!(MULTICAST_INTERVAL, Duration::from_secs(1));
938        assert_eq!(DEFEND_INTERVAL, Duration::from_millis(250));
939        assert_eq!(SHARED_DELAY_MIN, Duration::from_millis(20));
940        assert_eq!(SHARED_DELAY_MAX, Duration::from_millis(120));
941        assert_eq!(KNOWN_ANSWER_DELAY_MIN, Duration::from_millis(400));
942        assert_eq!(KNOWN_ANSWER_DELAY_MAX, Duration::from_millis(500));
943    }
944
945    #[test]
946    fn a_record_may_not_be_multicast_twice_within_a_second() {
947        let mut limiter = MulticastLimiter::<4>::new();
948        let now = Instant::ZERO.saturating_add(Duration::from_secs(10));
949        assert!(limiter.may_send(0, now, false), "nothing sent yet");
950        limiter.sent(0, now);
951        assert!(!limiter.may_send(0, now.saturating_add(Duration::from_millis(999)), false));
952        assert!(limiter.may_send(0, now.saturating_add(MULTICAST_INTERVAL), false));
953        // A different slot is unaffected.
954        assert!(limiter.may_send(1, now, false));
955    }
956
957    #[test]
958    fn defending_a_name_only_waits_250ms() {
959        let mut limiter = MulticastLimiter::<2>::new();
960        let now = Instant::ZERO.saturating_add(Duration::from_secs(10));
961        limiter.sent(0, now);
962        let at = now.saturating_add(DEFEND_INTERVAL);
963        assert!(limiter.may_send(0, at, true), "§6's probe exception");
964        assert!(!limiter.may_send(0, at, false));
965    }
966
967    #[test]
968    fn an_untracked_slot_is_never_rate_limited() {
969        let mut limiter = MulticastLimiter::<1>::new();
970        limiter.sent(9, Instant::ZERO.saturating_add(Duration::from_secs(10)));
971        assert!(limiter.may_send(9, Instant::ZERO, false));
972    }
973
974    /// RFC 6762 §8.2's own worked example.
975    #[test]
976    fn rfc_8_2_address_example() {
977        // MyPrinter.local. A 169.254.99.200 versus 169.254.200.50.
978        let lower = Tiebreaker {
979            class: 1,
980            kind: 1,
981            rdata: &[169, 254, 99, 200],
982        };
983        let higher = Tiebreaker {
984            class: 1,
985            kind: 1,
986            rdata: &[169, 254, 200, 50],
987        };
988        // "the third byte, with value 200, is greater than its counterpart with value 99, so
989        // it is deemed the winner" — and reading 200 as a signed -56 would invert this.
990        assert_eq!(tiebreak([higher], [lower]), Tiebreak::Won);
991        assert_eq!(tiebreak([lower], [higher]), Tiebreak::Lost);
992    }
993
994    #[test]
995    fn class_beats_type_beats_rdata() {
996        let big_class = Tiebreaker {
997            class: 2,
998            kind: 1,
999            rdata: &[0],
1000        };
1001        let big_type = Tiebreaker {
1002            class: 1,
1003            kind: 255,
1004            rdata: &[0],
1005        };
1006        let big_rdata = Tiebreaker {
1007            class: 1,
1008            kind: 1,
1009            rdata: &[255],
1010        };
1011        assert_eq!(tiebreak([big_class], [big_type]), Tiebreak::Won);
1012        assert_eq!(tiebreak([big_type], [big_rdata]), Tiebreak::Won);
1013    }
1014
1015    #[test]
1016    fn a_prefix_loses_to_what_extends_it() {
1017        // "one of the resource records runs out of rdata … the resource record which still
1018        // has remaining data first is deemed lexicographically later".
1019        let short = Tiebreaker {
1020            class: 1,
1021            kind: 16,
1022            rdata: &[1, 2],
1023        };
1024        let long = Tiebreaker {
1025            class: 1,
1026            kind: 16,
1027            rdata: &[1, 2, 0],
1028        };
1029        assert_eq!(tiebreak([long], [short]), Tiebreak::Won);
1030    }
1031
1032    #[test]
1033    fn a_longer_set_wins_and_identical_sets_do_not_conflict() {
1034        let a = Tiebreaker {
1035            class: 1,
1036            kind: 16,
1037            rdata: &[1],
1038        };
1039        let b = Tiebreaker {
1040            class: 1,
1041            kind: 33,
1042            rdata: &[2],
1043        };
1044        assert_eq!(tiebreak([a, b], [a]), Tiebreak::Won);
1045        assert_eq!(tiebreak([a], [a, b]), Tiebreak::Lost);
1046        assert_eq!(tiebreak([a, b], [a, b]), Tiebreak::Identical);
1047        assert_eq!(
1048            tiebreak(core::iter::empty(), core::iter::empty()),
1049            Tiebreak::Identical
1050        );
1051    }
1052}