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> {
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}