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}