matter_kit/exchange/table.rs
1//! The set of open exchanges, sized by [`Config`].
2//!
3//! An exchange is identified by its id *and* by who initiated it (Core §4.10): two nodes
4//! that each start an exchange may each pick the number 7, and they are two different
5//! conversations. Keying the table on the pair is what keeps them apart — keying it on the
6//! id alone is a bug that only appears when both ends are busy.
7
8use core::marker::PhantomData;
9
10use heapless::Vec;
11
12use super::mrp::{Mrp, MrpParams};
13use crate::config::{AssertValid, Config};
14use crate::error::{Error, ErrorCode, Result};
15use crate::msg::{ExchangeId, ProtocolId, SessionId};
16use crate::platform::{Duration, Instant, Peer};
17
18/// Which end of an exchange a node is (Core §4.4.3.1, the **I** flag).
19#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
20pub enum Role {
21 /// This node started the exchange, and sets the **I** flag on what it sends.
22 Initiator,
23 /// The peer started it.
24 Responder,
25}
26
27impl Role {
28 /// The role of whoever is on the other end.
29 #[must_use]
30 pub const fn peer(self) -> Self {
31 match self {
32 Self::Initiator => Self::Responder,
33 Self::Responder => Self::Initiator,
34 }
35 }
36
37 /// Whether this node sets the **I** flag.
38 #[must_use]
39 pub const fn is_initiator(self) -> bool {
40 matches!(self, Self::Initiator)
41 }
42}
43
44/// What identifies an exchange within a node.
45#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
46pub struct ExchangeKey {
47 /// The session it lives on.
48 pub session: SessionId,
49 /// The 16-bit exchange id.
50 pub id: ExchangeId,
51 /// Which end this node is. Part of the key, not a property: the peer may be using the
52 /// same id for an exchange of its own.
53 pub role: Role,
54}
55
56/// One open exchange.
57#[derive(Debug, Clone, Copy, PartialEq, Eq)]
58pub struct Exchange {
59 /// What identifies it.
60 pub key: ExchangeKey,
61 /// Which protocol is speaking over it.
62 pub protocol: ProtocolId,
63 /// Its reliability state.
64 pub mrp: Mrp,
65 /// Where the peer is, once a message has arrived from it or the caller has said.
66 ///
67 /// It decides two things: where a reply goes, and — per Core §4.12.4 — whether MRP runs
68 /// on this exchange at all, since BTP and TCP carry their own reliability.
69 pub peer: Option<Peer>,
70 /// When it was opened.
71 pub opened: Instant,
72 /// When a message last arrived on it or went out on it.
73 ///
74 /// This, not [`Exchange::opened`], is what [`ExchangeTable::reap`] judges: a chunked read
75 /// or a BDX transfer is legitimately long-lived, and reaping by age would cut it off
76 /// mid-transfer. What must not survive is an exchange nothing is *using*.
77 pub last_activity: Instant,
78 /// Whether this is §4.10.5.2's *ephemeral* exchange.
79 ///
80 /// "Create an ephemeral exchange from the incoming message and send an immediate
81 /// standalone acknowledgement … The message SHALL NOT be forwarded to the upper layer …
82 /// The ephemeral exchange created for such duplicate or unknown messages with R Flag set
83 /// is automatically closed in Standalone acknowledgement processing."
84 ///
85 /// It exists for exactly one reason: a reliable message this node cannot act on still owes
86 /// its sender an acknowledgement, or the sender retransmits it five times. Holding a real
87 /// exchange open to do that is what lets a stranger fill the table.
88 pub ephemeral: bool,
89}
90
91impl Exchange {
92 /// Opens an exchange.
93 #[must_use]
94 pub fn new(key: ExchangeKey, protocol: ProtocolId, params: MrpParams, now: Instant) -> Self {
95 Self {
96 key,
97 protocol,
98 mrp: Mrp::new(params),
99 peer: None,
100 opened: now,
101 last_activity: now,
102 ephemeral: false,
103 }
104 }
105
106 /// The same exchange, marked ephemeral (§4.10.5.2).
107 #[must_use]
108 pub const fn ephemeral(mut self) -> Self {
109 self.ephemeral = true;
110 self
111 }
112
113 /// Records that a message arrived on this exchange or went out on it.
114 pub const fn touch(&mut self, now: Instant) {
115 self.last_activity = now;
116 }
117
118 /// Whether nothing has used this exchange for `idle` and nothing is pending on it.
119 ///
120 /// §4.10.5.3 step 2 is the second half: "Wait for all pending retransmissions associated
121 /// with the Exchange to complete. If the retransmission list for the Exchange is empty,
122 /// remove the Exchange. Otherwise, leave the Exchange open and only close it once the
123 /// retransmission list is empty." An exchange still trying to deliver something is not
124 /// abandoned, however quiet the peer has been.
125 #[must_use]
126 pub fn is_abandoned(&self, now: Instant, idle: Duration) -> bool {
127 // "the retransmission list" — a message still awaiting acknowledgement, not merely any
128 // timer. An exchange can also hold a standalone acknowledgement it owes the peer, and
129 // one still owed after the idle timeout means nobody drove the timers at all; letting
130 // that pin an entry forever is the leak this is here to close.
131 if self.mrp.is_awaiting_ack() {
132 return false;
133 }
134 now.as_micros()
135 .saturating_sub(self.last_activity.as_micros())
136 > idle.as_micros()
137 }
138
139 /// The same exchange with its peer known from the start — what an initiator has, since
140 /// it chose who to talk to.
141 #[must_use]
142 pub fn to_peer(mut self, peer: Peer) -> Self {
143 self.peer = Some(peer);
144 self
145 }
146
147 /// Whether the transport underneath supplies its own reliability, so §4.12.4's "SHOULD
148 /// NOT set the R Flag" applies.
149 ///
150 /// An exchange whose peer is not yet known is assumed to be on UDP: MRP is the default
151 /// and the conservative choice, since an unnecessary acknowledgement costs a round trip
152 /// while a missing one costs the message.
153 #[must_use]
154 pub fn is_transport_reliable(&self) -> bool {
155 self.peer.is_some_and(|p| p.is_reliable())
156 }
157}
158
159/// How long an exchange may sit with nothing happening on it before it is reclaimed.
160///
161/// The specification gives no figure — §4.10.5.3 leaves closing to "the application layer or a
162/// fatal connection error" — but leaving that to the application is what makes an exchange
163/// table a remotely exhaustible resource. Every unsecured message with the I Flag set opens an
164/// exchange (§4.10.5.2), and an attacker who can reach the port can send them with any exchange
165/// id it likes. Without reclamation, `N` datagrams costing nothing fill the table for good, and
166/// a node that can no longer open an exchange can no longer establish a session — PASE or CASE,
167/// for the rest of its uptime. Existing sessions keep working, which is what makes it hard to
168/// notice.
169///
170/// Sixty seconds is taken from §5.5's bound on the one exchange most worth attacking: "a
171/// Commissionee SHALL expect a PASE session to be established within 60 seconds of receiving
172/// the initial request". An exchange idle for longer than the specification allows the whole
173/// handshake is not one anybody is still using.
174pub const EXCHANGE_IDLE_TIMEOUT: Duration = Duration::from_secs(60);
175
176/// The fixed-capacity set of open exchanges.
177///
178/// Capacity is `C::SESSIONS * C::EXCHANGES_PER_SESSION`, which is what
179/// [`Config`] says the node was built for. A full table is
180/// [`ErrorCode::NoSpace`] — a value the caller answers `BUSY` with, never an abort.
181#[derive(Debug)]
182pub struct ExchangeTable<C: Config, const N: usize> {
183 open: Vec<Exchange, N>,
184 /// The next exchange id to hand out. §4.4.3.3 only requires that an id not collide
185 /// with a live exchange on the same session; a counter is the simplest thing that
186 /// achieves it.
187 next_id: u16,
188 _config: PhantomData<C>,
189}
190
191impl<C: Config, const N: usize> Default for ExchangeTable<C, N> {
192 fn default() -> Self {
193 Self::new(0)
194 }
195}
196
197impl<C: Config, const N: usize> ExchangeTable<C, N> {
198 /// An empty table whose first exchange id is `first_id`.
199 ///
200 /// `first_id` should come from [`Rng`](crate::platform::Rng): starting at zero every
201 /// boot makes a node's exchange ids predictable, and predictable ids make it cheaper
202 /// for an off-path attacker to guess one that is live.
203 #[must_use]
204 pub fn new(first_id: u16) -> Self {
205 // Instantiating the check is what makes a `Config` that breaks a specification
206 // minimum a compile error at this line rather than a certification failure later.
207 let () = AssertValid::<C>::CHECK;
208 Self {
209 open: Vec::new(),
210 next_id: first_id,
211 _config: PhantomData,
212 }
213 }
214
215 /// How many exchanges are open.
216 #[must_use]
217 pub fn len(&self) -> usize {
218 self.open.len()
219 }
220
221 /// Whether none are open.
222 #[must_use]
223 pub fn is_empty(&self) -> bool {
224 self.open.is_empty()
225 }
226
227 /// How many more will fit.
228 #[must_use]
229 pub fn capacity_remaining(&self) -> usize {
230 N.saturating_sub(self.open.len())
231 }
232
233 /// Opens an exchange this node initiates, choosing an unused id.
234 pub fn open_initiator(
235 &mut self,
236 session: SessionId,
237 protocol: ProtocolId,
238 params: MrpParams,
239 peer: Option<Peer>,
240 now: Instant,
241 ) -> Result<ExchangeKey> {
242 let id = self.allocate_id(session)?;
243 let key = ExchangeKey {
244 session,
245 id,
246 role: Role::Initiator,
247 };
248 let exchange = Exchange::new(key, protocol, params, now);
249 self.insert(match peer {
250 Some(peer) => exchange.to_peer(peer),
251 None => exchange,
252 })?;
253 Ok(key)
254 }
255
256 /// Opens an exchange the peer initiated.
257 ///
258 /// Returns [`ErrorCode::InvalidState`] if one with that key is already open — a peer
259 /// reusing a live id is either confused or hostile, and silently adopting the second
260 /// one would let it hijack the first.
261 pub fn open_responder(
262 &mut self,
263 session: SessionId,
264 id: ExchangeId,
265 protocol: ProtocolId,
266 params: MrpParams,
267 now: Instant,
268 ) -> Result<ExchangeKey> {
269 let key = ExchangeKey {
270 session,
271 id,
272 role: Role::Responder,
273 };
274 if self.find(key).is_some() {
275 return Err(Error::new(ErrorCode::InvalidState));
276 }
277 self.insert_under_pressure(Exchange::new(key, protocol, params, now), now)?;
278 Ok(key)
279 }
280
281 /// Opens §4.10.5.2's ephemeral exchange: one that exists only to carry a standalone
282 /// acknowledgement and is closed as soon as it has.
283 pub fn open_ephemeral(
284 &mut self,
285 session: SessionId,
286 id: ExchangeId,
287 protocol: ProtocolId,
288 params: MrpParams,
289 now: Instant,
290 ) -> Result<ExchangeKey> {
291 let key = ExchangeKey {
292 session,
293 id,
294 role: Role::Responder,
295 };
296 if let Some(existing) = self.find(key) {
297 return Ok(existing.key);
298 }
299 self.insert_under_pressure(Exchange::new(key, protocol, params, now).ephemeral(), now)?;
300 Ok(key)
301 }
302
303 /// Inserts, reclaiming abandoned entries first if the table is full.
304 ///
305 /// Reaping here as well as on the timer is what makes the bound hold for a node whose
306 /// timers are slow or stopped: the pressure that would have refused a legitimate peer is
307 /// the same pressure that proves some other entry has been idle too long.
308 fn insert_under_pressure(&mut self, exchange: Exchange, now: Instant) -> Result<()> {
309 if self.open.is_full() {
310 self.reap(now, EXCHANGE_IDLE_TIMEOUT);
311 }
312 self.insert(exchange)
313 }
314
315 fn insert(&mut self, exchange: Exchange) -> Result<()> {
316 self.open
317 .push(exchange)
318 .map_err(|_| Error::new(ErrorCode::NoSpace))
319 }
320
321 /// Closes every exchange nothing has used for `idle` and nothing is pending on.
322 ///
323 /// Returns how many went. [`Messaging::poll`](crate::messaging::Messaging::poll) calls
324 /// this, so a node that drives its timers at all gets it without asking — which is the
325 /// point: an exchange table that is only reclaimed when the application remembers to
326 /// reclaim it is one an attacker reclaims on its behalf.
327 pub fn reap(&mut self, now: Instant, idle: Duration) -> usize {
328 let before = self.open.len();
329 self.open.retain(|e| !e.is_abandoned(now, idle));
330 before.saturating_sub(self.open.len())
331 }
332
333 /// When [`ExchangeTable::reap`] would next have something to do.
334 #[must_use]
335 pub fn reap_deadline(&self, idle: Duration) -> Option<Instant> {
336 self.open
337 .iter()
338 .filter(|e| !e.mrp.is_awaiting_ack())
339 .map(|e| e.last_activity.saturating_add(idle))
340 .min()
341 }
342
343 fn allocate_id(&mut self, session: SessionId) -> Result<ExchangeId> {
344 // Try every id once before giving up, so a table that is merely fragmented still
345 // finds one.
346 for _ in 0..=u16::MAX {
347 let id = ExchangeId(self.next_id);
348 self.next_id = self.next_id.wrapping_add(1);
349 let key = ExchangeKey {
350 session,
351 id,
352 role: Role::Initiator,
353 };
354 if self.find(key).is_none() {
355 return Ok(id);
356 }
357 }
358 Err(Error::new(ErrorCode::NoSpace))
359 }
360
361 /// The exchange with this key, if it is open.
362 #[must_use]
363 pub fn find(&self, key: ExchangeKey) -> Option<&Exchange> {
364 self.open.iter().find(|e| e.key == key)
365 }
366
367 /// The exchange with this key, mutably.
368 pub fn find_mut(&mut self, key: ExchangeKey) -> Option<&mut Exchange> {
369 self.open.iter_mut().find(|e| e.key == key)
370 }
371
372 /// Finds the exchange an arriving message belongs to.
373 ///
374 /// `from_initiator` is the message's **I** flag. A message *from* the initiator
375 /// belongs to the exchange in which this node is the **responder**, and the other way
376 /// round — getting this inversion wrong is how a node answers its own request.
377 #[must_use]
378 pub fn find_for_message(
379 &self,
380 session: SessionId,
381 id: ExchangeId,
382 from_initiator: bool,
383 ) -> Option<&Exchange> {
384 let role = if from_initiator {
385 Role::Responder
386 } else {
387 Role::Initiator
388 };
389 self.find(ExchangeKey { session, id, role })
390 }
391
392 /// Closes an exchange, returning whether it was open.
393 pub fn close(&mut self, key: ExchangeKey) -> bool {
394 let Some(i) = self.open.iter().position(|e| e.key == key) else {
395 return false;
396 };
397 if let Some(e) = self.open.get_mut(i) {
398 e.mrp.close();
399 }
400 self.open.swap_remove(i);
401 true
402 }
403
404 /// Closes every exchange on a session — what tearing the session down does.
405 pub fn close_session(&mut self, session: SessionId) -> usize {
406 let before = self.open.len();
407 self.open.retain(|e| e.key.session != session);
408 before.saturating_sub(self.open.len())
409 }
410
411 /// The earliest deadline across every open exchange, which is when the caller's run
412 /// loop should next call [`ExchangeTable::on_timeout`].
413 #[must_use]
414 pub fn poll_deadline(&self) -> Option<Instant> {
415 self.open.iter().filter_map(|e| e.mrp.poll_deadline()).min()
416 }
417
418 /// Hands a passed deadline to every exchange that has one, calling `on_action` for
419 /// each thing that falls out.
420 ///
421 /// Returns how many actions were produced.
422 pub fn on_timeout(
423 &mut self,
424 now: Instant,
425 randomness: u32,
426 mut on_action: impl FnMut(ExchangeKey, super::OnTimeout),
427 ) -> usize {
428 let mut count = 0usize;
429 for exchange in &mut self.open {
430 loop {
431 let action = exchange.mrp.on_timeout(now, randomness);
432 if matches!(action, super::OnTimeout::Nothing) {
433 break;
434 }
435 on_action(exchange.key, action);
436 count = count.saturating_add(1);
437 }
438 }
439 count
440 }
441
442 /// Every open exchange.
443 pub fn iter(&self) -> impl Iterator<Item = &Exchange> {
444 self.open.iter()
445 }
446}
447
448#[cfg(test)]
449mod tests {
450 use super::*;
451 use crate::DefaultConfig;
452 use crate::exchange::OnTimeout;
453
454 type Table = ExchangeTable<DefaultConfig, 8>;
455
456 #[test]
457 fn an_initiated_exchange_gets_an_unused_id() {
458 let mut t = Table::new(100);
459 let a = t
460 .open_initiator(
461 SessionId(1),
462 ProtocolId::INTERACTION_MODEL,
463 MrpParams::default(),
464 None,
465 Instant::ZERO,
466 )
467 .expect("open");
468 let b = t
469 .open_initiator(
470 SessionId(1),
471 ProtocolId::INTERACTION_MODEL,
472 MrpParams::default(),
473 None,
474 Instant::ZERO,
475 )
476 .expect("open");
477 assert_ne!(a.id, b.id);
478 assert_eq!(a.id, ExchangeId(100));
479 assert_eq!(t.len(), 2);
480 }
481
482 #[test]
483 fn the_same_id_in_both_roles_is_two_exchanges() {
484 // Two nodes that each start an exchange may each choose 7. Keying on the id alone
485 // would merge them, and this node would answer its own request.
486 let mut t = Table::new(7);
487 let mine = t
488 .open_initiator(
489 SessionId(1),
490 ProtocolId::SECURE_CHANNEL,
491 MrpParams::default(),
492 None,
493 Instant::ZERO,
494 )
495 .expect("mine");
496 assert_eq!(mine.id, ExchangeId(7));
497 let theirs = t
498 .open_responder(
499 SessionId(1),
500 ExchangeId(7),
501 ProtocolId::SECURE_CHANNEL,
502 MrpParams::default(),
503 Instant::ZERO,
504 )
505 .expect("theirs");
506 assert_eq!(t.len(), 2, "two distinct exchanges");
507 assert_ne!(mine, theirs);
508 assert!(t.find(mine).is_some());
509 assert!(t.find(theirs).is_some());
510 }
511
512 #[test]
513 fn an_arriving_message_finds_the_opposite_role() {
514 let mut t = Table::new(0);
515 let mine = t
516 .open_initiator(
517 SessionId(1),
518 ProtocolId::SECURE_CHANNEL,
519 MrpParams::default(),
520 None,
521 Instant::ZERO,
522 )
523 .expect("open");
524 // The peer's reply carries I = 0, because the peer is not the initiator.
525 let found = t
526 .find_for_message(SessionId(1), mine.id, false)
527 .expect("the reply belongs to my exchange");
528 assert_eq!(found.key, mine);
529 // A message with I = 1 and the same id is a *different* exchange, which is not
530 // open.
531 assert!(t.find_for_message(SessionId(1), mine.id, true).is_none());
532 }
533
534 #[test]
535 fn a_peer_reusing_a_live_id_is_refused() {
536 let mut t = Table::new(0);
537 t.open_responder(
538 SessionId(1),
539 ExchangeId(3),
540 ProtocolId::SECURE_CHANNEL,
541 MrpParams::default(),
542 Instant::ZERO,
543 )
544 .expect("first");
545 assert_eq!(
546 t.open_responder(
547 SessionId(1),
548 ExchangeId(3),
549 ProtocolId::SECURE_CHANNEL,
550 MrpParams::default(),
551 Instant::ZERO,
552 )
553 .unwrap_err()
554 .code(),
555 ErrorCode::InvalidState
556 );
557 }
558
559 #[test]
560 fn the_same_id_on_two_sessions_is_two_exchanges() {
561 let mut t = Table::new(0);
562 t.open_responder(
563 SessionId(1),
564 ExchangeId(5),
565 ProtocolId::SECURE_CHANNEL,
566 MrpParams::default(),
567 Instant::ZERO,
568 )
569 .expect("session 1");
570 t.open_responder(
571 SessionId(2),
572 ExchangeId(5),
573 ProtocolId::SECURE_CHANNEL,
574 MrpParams::default(),
575 Instant::ZERO,
576 )
577 .expect("session 2");
578 assert_eq!(t.len(), 2);
579 }
580
581 #[test]
582 fn a_full_table_is_a_value_not_an_abort() {
583 let mut t = Table::new(0);
584 for _ in 0..8 {
585 t.open_initiator(
586 SessionId(1),
587 ProtocolId::SECURE_CHANNEL,
588 MrpParams::default(),
589 None,
590 Instant::ZERO,
591 )
592 .expect("fits");
593 }
594 assert_eq!(t.capacity_remaining(), 0);
595 assert_eq!(
596 t.open_initiator(
597 SessionId(1),
598 ProtocolId::SECURE_CHANNEL,
599 MrpParams::default(),
600 None,
601 Instant::ZERO,
602 )
603 .unwrap_err()
604 .code(),
605 ErrorCode::NoSpace
606 );
607 }
608
609 #[test]
610 fn closing_a_session_closes_its_exchanges() {
611 let mut t = Table::new(0);
612 for session in [1u16, 1, 2] {
613 t.open_initiator(
614 SessionId(session),
615 ProtocolId::SECURE_CHANNEL,
616 MrpParams::default(),
617 None,
618 Instant::ZERO,
619 )
620 .expect("open");
621 }
622 assert_eq!(t.close_session(SessionId(1)), 2);
623 assert_eq!(t.len(), 1);
624 assert_eq!(t.close_session(SessionId(1)), 0);
625 }
626
627 #[test]
628 fn close_reports_whether_it_did_anything() {
629 let mut t = Table::new(0);
630 let k = t
631 .open_initiator(
632 SessionId(1),
633 ProtocolId::SECURE_CHANNEL,
634 MrpParams::default(),
635 None,
636 Instant::ZERO,
637 )
638 .expect("open");
639 assert!(t.close(k));
640 assert!(!t.close(k));
641 assert!(t.is_empty());
642 }
643
644 #[test]
645 fn the_table_deadline_is_the_earliest_of_them() {
646 let mut t = Table::new(0);
647 let slow = t
648 .open_initiator(
649 SessionId(1),
650 ProtocolId::SECURE_CHANNEL,
651 MrpParams::default(),
652 None,
653 Instant::ZERO,
654 )
655 .expect("open");
656 let fast = t
657 .open_initiator(
658 SessionId(1),
659 ProtocolId::SECURE_CHANNEL,
660 MrpParams::default(),
661 None,
662 Instant::ZERO,
663 )
664 .expect("open");
665
666 assert_eq!(t.poll_deadline(), None, "nothing is in flight yet");
667 if let Some(e) = t.find_mut(slow) {
668 e.mrp.on_send(1, Instant::ZERO, 0).expect("send");
669 }
670 if let Some(e) = t.find_mut(fast) {
671 // An active peer retries sooner: 330 ms against 550 ms.
672 e.mrp.note_peer_activity(Instant::ZERO);
673 e.mrp.on_send(2, Instant::ZERO, 0).expect("send");
674 }
675 let deadline = t.poll_deadline().expect("a deadline");
676 assert_eq!(deadline.as_micros(), 330_000);
677 }
678
679 #[test]
680 fn timeouts_are_reported_per_exchange() {
681 let mut t = Table::new(0);
682 let k = t
683 .open_initiator(
684 SessionId(1),
685 ProtocolId::SECURE_CHANNEL,
686 MrpParams::default(),
687 None,
688 Instant::ZERO,
689 )
690 .expect("open");
691 if let Some(e) = t.find_mut(k) {
692 e.mrp.on_send(9, Instant::ZERO, 0).expect("send");
693 }
694 let deadline = t.poll_deadline().expect("a deadline");
695
696 let mut seen = heapless::Vec::<(ExchangeKey, u32), 4>::new();
697 let n = t.on_timeout(deadline, 0, |key, action| {
698 if let OnTimeout::Retransmit { counter, .. } = action {
699 let _ = seen.push((key, counter));
700 }
701 });
702 assert_eq!(n, 1);
703 assert_eq!(&seen[..], &[(k, 9)]);
704 }
705}