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 = 64> {
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> crate::config::Capacity for ExchangeTable<C, N> {
198 const TOTAL: usize = N;
199 /// The specification sets no per-fabric exchange guarantee, so the whole table is the
200 /// answer: an exchange is opened and closed inside one interaction, and §4.10.5.3's
201 /// reclamation is what keeps a stranger from holding them.
202 const PER_FABRIC: usize = N;
203}
204
205impl<C: Config, const N: usize> ExchangeTable<C, N> {
206 /// An empty table whose first exchange id is `first_id`.
207 ///
208 /// `first_id` should come from [`Rng`](crate::platform::Rng): starting at zero every
209 /// boot makes a node's exchange ids predictable, and predictable ids make it cheaper
210 /// for an off-path attacker to guess one that is live.
211 #[must_use]
212 pub fn new(first_id: u16) -> Self {
213 // Instantiating the check is what makes a `Config` that breaks a specification
214 // minimum a compile error at this line rather than a certification failure later.
215 let () = AssertValid::<C>::CHECK;
216 Self {
217 open: Vec::new(),
218 next_id: first_id,
219 _config: PhantomData,
220 }
221 }
222
223 /// How many exchanges are open.
224 #[must_use]
225 pub fn len(&self) -> usize {
226 self.open.len()
227 }
228
229 /// Whether none are open.
230 #[must_use]
231 pub fn is_empty(&self) -> bool {
232 self.open.is_empty()
233 }
234
235 /// How many more will fit.
236 #[must_use]
237 pub fn capacity_remaining(&self) -> usize {
238 N.saturating_sub(self.open.len())
239 }
240
241 /// Opens an exchange this node initiates, choosing an unused id.
242 pub fn open_initiator(
243 &mut self,
244 session: SessionId,
245 protocol: ProtocolId,
246 params: MrpParams,
247 peer: Option<Peer>,
248 now: Instant,
249 ) -> Result<ExchangeKey> {
250 let id = self.allocate_id(session)?;
251 let key = ExchangeKey {
252 session,
253 id,
254 role: Role::Initiator,
255 };
256 let exchange = Exchange::new(key, protocol, params, now);
257 self.insert(match peer {
258 Some(peer) => exchange.to_peer(peer),
259 None => exchange,
260 })?;
261 Ok(key)
262 }
263
264 /// Opens an exchange the peer initiated.
265 ///
266 /// Returns [`ErrorCode::InvalidState`] if one with that key is already open — a peer
267 /// reusing a live id is either confused or hostile, and silently adopting the second
268 /// one would let it hijack the first.
269 pub fn open_responder(
270 &mut self,
271 session: SessionId,
272 id: ExchangeId,
273 protocol: ProtocolId,
274 params: MrpParams,
275 now: Instant,
276 ) -> Result<ExchangeKey> {
277 let key = ExchangeKey {
278 session,
279 id,
280 role: Role::Responder,
281 };
282 if self.find(key).is_some() {
283 return Err(Error::new(ErrorCode::InvalidState));
284 }
285 self.insert_under_pressure(Exchange::new(key, protocol, params, now), now)?;
286 Ok(key)
287 }
288
289 /// Opens §4.10.5.2's ephemeral exchange: one that exists only to carry a standalone
290 /// acknowledgement and is closed as soon as it has.
291 pub fn open_ephemeral(
292 &mut self,
293 session: SessionId,
294 id: ExchangeId,
295 protocol: ProtocolId,
296 params: MrpParams,
297 now: Instant,
298 ) -> Result<ExchangeKey> {
299 let key = ExchangeKey {
300 session,
301 id,
302 role: Role::Responder,
303 };
304 if let Some(existing) = self.find(key) {
305 return Ok(existing.key);
306 }
307 self.insert_under_pressure(Exchange::new(key, protocol, params, now).ephemeral(), now)?;
308 Ok(key)
309 }
310
311 /// Inserts, reclaiming abandoned entries first if the table is full.
312 ///
313 /// Reaping here as well as on the timer is what makes the bound hold for a node whose
314 /// timers are slow or stopped: the pressure that would have refused a legitimate peer is
315 /// the same pressure that proves some other entry has been idle too long.
316 fn insert_under_pressure(&mut self, exchange: Exchange, now: Instant) -> Result<()> {
317 if self.open.is_full() {
318 self.reap(now, EXCHANGE_IDLE_TIMEOUT);
319 }
320 self.insert(exchange)
321 }
322
323 fn insert(&mut self, exchange: Exchange) -> Result<()> {
324 self.open
325 .push(exchange)
326 .map_err(|_| Error::new(ErrorCode::NoSpace))
327 }
328
329 /// Closes every exchange nothing has used for `idle` and nothing is pending on.
330 ///
331 /// Returns how many went. [`Messaging::poll`](crate::messaging::Messaging::poll) calls
332 /// this, so a node that drives its timers at all gets it without asking — which is the
333 /// point: an exchange table that is only reclaimed when the application remembers to
334 /// reclaim it is one an attacker reclaims on its behalf.
335 pub fn reap(&mut self, now: Instant, idle: Duration) -> usize {
336 let before = self.open.len();
337 self.open.retain(|e| !e.is_abandoned(now, idle));
338 before.saturating_sub(self.open.len())
339 }
340
341 /// When [`ExchangeTable::reap`] would next have something to do.
342 #[must_use]
343 pub fn reap_deadline(&self, idle: Duration) -> Option<Instant> {
344 self.open
345 .iter()
346 .filter(|e| !e.mrp.is_awaiting_ack())
347 .map(|e| e.last_activity.saturating_add(idle))
348 .min()
349 }
350
351 fn allocate_id(&mut self, session: SessionId) -> Result<ExchangeId> {
352 // Try every id once before giving up, so a table that is merely fragmented still
353 // finds one.
354 for _ in 0..=u16::MAX {
355 let id = ExchangeId(self.next_id);
356 self.next_id = self.next_id.wrapping_add(1);
357 let key = ExchangeKey {
358 session,
359 id,
360 role: Role::Initiator,
361 };
362 if self.find(key).is_none() {
363 return Ok(id);
364 }
365 }
366 Err(Error::new(ErrorCode::NoSpace))
367 }
368
369 /// The exchange with this key, if it is open.
370 #[must_use]
371 pub fn find(&self, key: ExchangeKey) -> Option<&Exchange> {
372 self.open.iter().find(|e| e.key == key)
373 }
374
375 /// The exchange with this key, mutably.
376 pub fn find_mut(&mut self, key: ExchangeKey) -> Option<&mut Exchange> {
377 self.open.iter_mut().find(|e| e.key == key)
378 }
379
380 /// Finds the exchange an arriving message belongs to.
381 ///
382 /// `from_initiator` is the message's **I** flag. A message *from* the initiator
383 /// belongs to the exchange in which this node is the **responder**, and the other way
384 /// round — getting this inversion wrong is how a node answers its own request.
385 #[must_use]
386 pub fn find_for_message(
387 &self,
388 session: SessionId,
389 id: ExchangeId,
390 from_initiator: bool,
391 ) -> Option<&Exchange> {
392 let role = if from_initiator {
393 Role::Responder
394 } else {
395 Role::Initiator
396 };
397 self.find(ExchangeKey { session, id, role })
398 }
399
400 /// Closes an exchange, returning whether it was open.
401 pub fn close(&mut self, key: ExchangeKey) -> bool {
402 let Some(i) = self.open.iter().position(|e| e.key == key) else {
403 return false;
404 };
405 if let Some(e) = self.open.get_mut(i) {
406 e.mrp.close();
407 }
408 self.open.swap_remove(i);
409 true
410 }
411
412 /// Closes every exchange on a session — what tearing the session down does.
413 pub fn close_session(&mut self, session: SessionId) -> usize {
414 let before = self.open.len();
415 self.open.retain(|e| e.key.session != session);
416 before.saturating_sub(self.open.len())
417 }
418
419 /// The earliest deadline across every open exchange, which is when the caller's run
420 /// loop should next call [`ExchangeTable::on_timeout`].
421 #[must_use]
422 pub fn poll_deadline(&self) -> Option<Instant> {
423 self.open.iter().filter_map(|e| e.mrp.poll_deadline()).min()
424 }
425
426 /// Hands a passed deadline to every exchange that has one, calling `on_action` for
427 /// each thing that falls out.
428 ///
429 /// Returns how many actions were produced.
430 pub fn on_timeout(
431 &mut self,
432 now: Instant,
433 randomness: u32,
434 mut on_action: impl FnMut(ExchangeKey, super::OnTimeout),
435 ) -> usize {
436 let mut count = 0usize;
437 for exchange in &mut self.open {
438 loop {
439 let action = exchange.mrp.on_timeout(now, randomness);
440 if matches!(action, super::OnTimeout::Nothing) {
441 break;
442 }
443 on_action(exchange.key, action);
444 count = count.saturating_add(1);
445 }
446 }
447 count
448 }
449
450 /// Every open exchange.
451 pub fn iter(&self) -> impl Iterator<Item = &Exchange> {
452 self.open.iter()
453 }
454}
455
456#[cfg(test)]
457mod tests {
458 use super::*;
459 use crate::DefaultConfig;
460 use crate::exchange::OnTimeout;
461
462 type Table = ExchangeTable<DefaultConfig, 8>;
463
464 #[test]
465 fn an_initiated_exchange_gets_an_unused_id() {
466 let mut t = Table::new(100);
467 let a = t
468 .open_initiator(
469 SessionId(1),
470 ProtocolId::INTERACTION_MODEL,
471 MrpParams::default(),
472 None,
473 Instant::ZERO,
474 )
475 .expect("open");
476 let b = t
477 .open_initiator(
478 SessionId(1),
479 ProtocolId::INTERACTION_MODEL,
480 MrpParams::default(),
481 None,
482 Instant::ZERO,
483 )
484 .expect("open");
485 assert_ne!(a.id, b.id);
486 assert_eq!(a.id, ExchangeId(100));
487 assert_eq!(t.len(), 2);
488 }
489
490 #[test]
491 fn the_same_id_in_both_roles_is_two_exchanges() {
492 // Two nodes that each start an exchange may each choose 7. Keying on the id alone
493 // would merge them, and this node would answer its own request.
494 let mut t = Table::new(7);
495 let mine = t
496 .open_initiator(
497 SessionId(1),
498 ProtocolId::SECURE_CHANNEL,
499 MrpParams::default(),
500 None,
501 Instant::ZERO,
502 )
503 .expect("mine");
504 assert_eq!(mine.id, ExchangeId(7));
505 let theirs = t
506 .open_responder(
507 SessionId(1),
508 ExchangeId(7),
509 ProtocolId::SECURE_CHANNEL,
510 MrpParams::default(),
511 Instant::ZERO,
512 )
513 .expect("theirs");
514 assert_eq!(t.len(), 2, "two distinct exchanges");
515 assert_ne!(mine, theirs);
516 assert!(t.find(mine).is_some());
517 assert!(t.find(theirs).is_some());
518 }
519
520 #[test]
521 fn an_arriving_message_finds_the_opposite_role() {
522 let mut t = Table::new(0);
523 let mine = t
524 .open_initiator(
525 SessionId(1),
526 ProtocolId::SECURE_CHANNEL,
527 MrpParams::default(),
528 None,
529 Instant::ZERO,
530 )
531 .expect("open");
532 // The peer's reply carries I = 0, because the peer is not the initiator.
533 let found = t
534 .find_for_message(SessionId(1), mine.id, false)
535 .expect("the reply belongs to my exchange");
536 assert_eq!(found.key, mine);
537 // A message with I = 1 and the same id is a *different* exchange, which is not
538 // open.
539 assert!(t.find_for_message(SessionId(1), mine.id, true).is_none());
540 }
541
542 #[test]
543 fn a_peer_reusing_a_live_id_is_refused() {
544 let mut t = Table::new(0);
545 t.open_responder(
546 SessionId(1),
547 ExchangeId(3),
548 ProtocolId::SECURE_CHANNEL,
549 MrpParams::default(),
550 Instant::ZERO,
551 )
552 .expect("first");
553 assert_eq!(
554 t.open_responder(
555 SessionId(1),
556 ExchangeId(3),
557 ProtocolId::SECURE_CHANNEL,
558 MrpParams::default(),
559 Instant::ZERO,
560 )
561 .unwrap_err()
562 .code(),
563 ErrorCode::InvalidState
564 );
565 }
566
567 #[test]
568 fn the_same_id_on_two_sessions_is_two_exchanges() {
569 let mut t = Table::new(0);
570 t.open_responder(
571 SessionId(1),
572 ExchangeId(5),
573 ProtocolId::SECURE_CHANNEL,
574 MrpParams::default(),
575 Instant::ZERO,
576 )
577 .expect("session 1");
578 t.open_responder(
579 SessionId(2),
580 ExchangeId(5),
581 ProtocolId::SECURE_CHANNEL,
582 MrpParams::default(),
583 Instant::ZERO,
584 )
585 .expect("session 2");
586 assert_eq!(t.len(), 2);
587 }
588
589 #[test]
590 fn a_full_table_is_a_value_not_an_abort() {
591 let mut t = Table::new(0);
592 for _ in 0..8 {
593 t.open_initiator(
594 SessionId(1),
595 ProtocolId::SECURE_CHANNEL,
596 MrpParams::default(),
597 None,
598 Instant::ZERO,
599 )
600 .expect("fits");
601 }
602 assert_eq!(t.capacity_remaining(), 0);
603 assert_eq!(
604 t.open_initiator(
605 SessionId(1),
606 ProtocolId::SECURE_CHANNEL,
607 MrpParams::default(),
608 None,
609 Instant::ZERO,
610 )
611 .unwrap_err()
612 .code(),
613 ErrorCode::NoSpace
614 );
615 }
616
617 #[test]
618 fn closing_a_session_closes_its_exchanges() {
619 let mut t = Table::new(0);
620 for session in [1u16, 1, 2] {
621 t.open_initiator(
622 SessionId(session),
623 ProtocolId::SECURE_CHANNEL,
624 MrpParams::default(),
625 None,
626 Instant::ZERO,
627 )
628 .expect("open");
629 }
630 assert_eq!(t.close_session(SessionId(1)), 2);
631 assert_eq!(t.len(), 1);
632 assert_eq!(t.close_session(SessionId(1)), 0);
633 }
634
635 #[test]
636 fn close_reports_whether_it_did_anything() {
637 let mut t = Table::new(0);
638 let k = t
639 .open_initiator(
640 SessionId(1),
641 ProtocolId::SECURE_CHANNEL,
642 MrpParams::default(),
643 None,
644 Instant::ZERO,
645 )
646 .expect("open");
647 assert!(t.close(k));
648 assert!(!t.close(k));
649 assert!(t.is_empty());
650 }
651
652 #[test]
653 fn the_table_deadline_is_the_earliest_of_them() {
654 let mut t = Table::new(0);
655 let slow = t
656 .open_initiator(
657 SessionId(1),
658 ProtocolId::SECURE_CHANNEL,
659 MrpParams::default(),
660 None,
661 Instant::ZERO,
662 )
663 .expect("open");
664 let fast = t
665 .open_initiator(
666 SessionId(1),
667 ProtocolId::SECURE_CHANNEL,
668 MrpParams::default(),
669 None,
670 Instant::ZERO,
671 )
672 .expect("open");
673
674 assert_eq!(t.poll_deadline(), None, "nothing is in flight yet");
675 if let Some(e) = t.find_mut(slow) {
676 e.mrp.on_send(1, Instant::ZERO, 0).expect("send");
677 }
678 if let Some(e) = t.find_mut(fast) {
679 // An active peer retries sooner: 330 ms against 550 ms.
680 e.mrp.note_peer_activity(Instant::ZERO);
681 e.mrp.on_send(2, Instant::ZERO, 0).expect("send");
682 }
683 let deadline = t.poll_deadline().expect("a deadline");
684 assert_eq!(deadline.as_micros(), 330_000);
685 }
686
687 #[test]
688 fn timeouts_are_reported_per_exchange() {
689 let mut t = Table::new(0);
690 let k = t
691 .open_initiator(
692 SessionId(1),
693 ProtocolId::SECURE_CHANNEL,
694 MrpParams::default(),
695 None,
696 Instant::ZERO,
697 )
698 .expect("open");
699 if let Some(e) = t.find_mut(k) {
700 e.mrp.on_send(9, Instant::ZERO, 0).expect("send");
701 }
702 let deadline = t.poll_deadline().expect("a deadline");
703
704 let mut seen = heapless::Vec::<(ExchangeKey, u32), 4>::new();
705 let n = t.on_timeout(deadline, 0, |key, action| {
706 if let OnTimeout::Retransmit { counter, .. } = action {
707 let _ = seen.push((key, counter));
708 }
709 });
710 assert_eq!(n, 1);
711 assert_eq!(&seen[..], &[(k, 9)]);
712 }
713}