Skip to main content

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}