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    /// Finds the exchange an arriving message belongs to, mutably.
393    pub fn find_for_message_mut(
394        &mut self,
395        session: SessionId,
396        id: ExchangeId,
397        from_initiator: bool,
398    ) -> Option<&mut Exchange> {
399        let role = if from_initiator {
400            Role::Responder
401        } else {
402            Role::Initiator
403        };
404        self.find_mut(ExchangeKey { session, id, role })
405    }
406
407    /// Closes an exchange, returning whether it was open.
408    pub fn close(&mut self, key: ExchangeKey) -> bool {
409        let Some(i) = self.open.iter().position(|e| e.key == key) else {
410            return false;
411        };
412        if let Some(e) = self.open.get_mut(i) {
413            e.mrp.close();
414        }
415        self.open.swap_remove(i);
416        true
417    }
418
419    /// Closes every exchange on a session — what tearing the session down does.
420    pub fn close_session(&mut self, session: SessionId) -> usize {
421        let before = self.open.len();
422        self.open.retain(|e| e.key.session != session);
423        before.saturating_sub(self.open.len())
424    }
425
426    /// The earliest deadline across every open exchange, which is when the caller's run
427    /// loop should next call [`ExchangeTable::on_timeout`].
428    #[must_use]
429    pub fn poll_deadline(&self) -> Option<Instant> {
430        self.open.iter().filter_map(|e| e.mrp.poll_deadline()).min()
431    }
432
433    /// Hands a passed deadline to every exchange that has one, calling `on_action` for
434    /// each thing that falls out.
435    ///
436    /// Returns how many actions were produced.
437    pub fn on_timeout(
438        &mut self,
439        now: Instant,
440        randomness: u32,
441        mut on_action: impl FnMut(ExchangeKey, super::OnTimeout),
442    ) -> usize {
443        let mut count = 0usize;
444        for exchange in &mut self.open {
445            loop {
446                let action = exchange.mrp.on_timeout(now, randomness);
447                if matches!(action, super::OnTimeout::Nothing) {
448                    break;
449                }
450                on_action(exchange.key, action);
451                count = count.saturating_add(1);
452            }
453        }
454        count
455    }
456
457    /// Every open exchange.
458    pub fn iter(&self) -> impl Iterator<Item = &Exchange> {
459        self.open.iter()
460    }
461}
462
463#[cfg(test)]
464mod tests {
465    use super::*;
466    use crate::DefaultConfig;
467    use crate::exchange::OnTimeout;
468
469    type Table = ExchangeTable<DefaultConfig, 8>;
470
471    #[test]
472    fn an_initiated_exchange_gets_an_unused_id() {
473        let mut t = Table::new(100);
474        let a = t
475            .open_initiator(
476                SessionId(1),
477                ProtocolId::INTERACTION_MODEL,
478                MrpParams::default(),
479                None,
480                Instant::ZERO,
481            )
482            .expect("open");
483        let b = t
484            .open_initiator(
485                SessionId(1),
486                ProtocolId::INTERACTION_MODEL,
487                MrpParams::default(),
488                None,
489                Instant::ZERO,
490            )
491            .expect("open");
492        assert_ne!(a.id, b.id);
493        assert_eq!(a.id, ExchangeId(100));
494        assert_eq!(t.len(), 2);
495    }
496
497    #[test]
498    fn the_same_id_in_both_roles_is_two_exchanges() {
499        // Two nodes that each start an exchange may each choose 7. Keying on the id alone
500        // would merge them, and this node would answer its own request.
501        let mut t = Table::new(7);
502        let mine = t
503            .open_initiator(
504                SessionId(1),
505                ProtocolId::SECURE_CHANNEL,
506                MrpParams::default(),
507                None,
508                Instant::ZERO,
509            )
510            .expect("mine");
511        assert_eq!(mine.id, ExchangeId(7));
512        let theirs = t
513            .open_responder(
514                SessionId(1),
515                ExchangeId(7),
516                ProtocolId::SECURE_CHANNEL,
517                MrpParams::default(),
518                Instant::ZERO,
519            )
520            .expect("theirs");
521        assert_eq!(t.len(), 2, "two distinct exchanges");
522        assert_ne!(mine, theirs);
523        assert!(t.find(mine).is_some());
524        assert!(t.find(theirs).is_some());
525    }
526
527    #[test]
528    fn an_arriving_message_finds_the_opposite_role() {
529        let mut t = Table::new(0);
530        let mine = t
531            .open_initiator(
532                SessionId(1),
533                ProtocolId::SECURE_CHANNEL,
534                MrpParams::default(),
535                None,
536                Instant::ZERO,
537            )
538            .expect("open");
539        // The peer's reply carries I = 0, because the peer is not the initiator.
540        let found = t
541            .find_for_message(SessionId(1), mine.id, false)
542            .expect("the reply belongs to my exchange");
543        assert_eq!(found.key, mine);
544        // A message with I = 1 and the same id is a *different* exchange, which is not
545        // open.
546        assert!(t.find_for_message(SessionId(1), mine.id, true).is_none());
547    }
548
549    #[test]
550    fn a_peer_reusing_a_live_id_is_refused() {
551        let mut t = Table::new(0);
552        t.open_responder(
553            SessionId(1),
554            ExchangeId(3),
555            ProtocolId::SECURE_CHANNEL,
556            MrpParams::default(),
557            Instant::ZERO,
558        )
559        .expect("first");
560        assert_eq!(
561            t.open_responder(
562                SessionId(1),
563                ExchangeId(3),
564                ProtocolId::SECURE_CHANNEL,
565                MrpParams::default(),
566                Instant::ZERO,
567            )
568            .unwrap_err()
569            .code(),
570            ErrorCode::InvalidState
571        );
572    }
573
574    #[test]
575    fn the_same_id_on_two_sessions_is_two_exchanges() {
576        let mut t = Table::new(0);
577        t.open_responder(
578            SessionId(1),
579            ExchangeId(5),
580            ProtocolId::SECURE_CHANNEL,
581            MrpParams::default(),
582            Instant::ZERO,
583        )
584        .expect("session 1");
585        t.open_responder(
586            SessionId(2),
587            ExchangeId(5),
588            ProtocolId::SECURE_CHANNEL,
589            MrpParams::default(),
590            Instant::ZERO,
591        )
592        .expect("session 2");
593        assert_eq!(t.len(), 2);
594    }
595
596    #[test]
597    fn a_full_table_is_a_value_not_an_abort() {
598        let mut t = Table::new(0);
599        for _ in 0..8 {
600            t.open_initiator(
601                SessionId(1),
602                ProtocolId::SECURE_CHANNEL,
603                MrpParams::default(),
604                None,
605                Instant::ZERO,
606            )
607            .expect("fits");
608        }
609        assert_eq!(t.capacity_remaining(), 0);
610        assert_eq!(
611            t.open_initiator(
612                SessionId(1),
613                ProtocolId::SECURE_CHANNEL,
614                MrpParams::default(),
615                None,
616                Instant::ZERO,
617            )
618            .unwrap_err()
619            .code(),
620            ErrorCode::NoSpace
621        );
622    }
623
624    #[test]
625    fn closing_a_session_closes_its_exchanges() {
626        let mut t = Table::new(0);
627        for session in [1u16, 1, 2] {
628            t.open_initiator(
629                SessionId(session),
630                ProtocolId::SECURE_CHANNEL,
631                MrpParams::default(),
632                None,
633                Instant::ZERO,
634            )
635            .expect("open");
636        }
637        assert_eq!(t.close_session(SessionId(1)), 2);
638        assert_eq!(t.len(), 1);
639        assert_eq!(t.close_session(SessionId(1)), 0);
640    }
641
642    #[test]
643    fn close_reports_whether_it_did_anything() {
644        let mut t = Table::new(0);
645        let k = t
646            .open_initiator(
647                SessionId(1),
648                ProtocolId::SECURE_CHANNEL,
649                MrpParams::default(),
650                None,
651                Instant::ZERO,
652            )
653            .expect("open");
654        assert!(t.close(k));
655        assert!(!t.close(k));
656        assert!(t.is_empty());
657    }
658
659    #[test]
660    fn the_table_deadline_is_the_earliest_of_them() {
661        let mut t = Table::new(0);
662        let slow = t
663            .open_initiator(
664                SessionId(1),
665                ProtocolId::SECURE_CHANNEL,
666                MrpParams::default(),
667                None,
668                Instant::ZERO,
669            )
670            .expect("open");
671        let fast = t
672            .open_initiator(
673                SessionId(1),
674                ProtocolId::SECURE_CHANNEL,
675                MrpParams::default(),
676                None,
677                Instant::ZERO,
678            )
679            .expect("open");
680
681        assert_eq!(t.poll_deadline(), None, "nothing is in flight yet");
682        if let Some(e) = t.find_mut(slow) {
683            e.mrp.on_send(1, Instant::ZERO, 0).expect("send");
684        }
685        if let Some(e) = t.find_mut(fast) {
686            // An active peer retries sooner: 330 ms against 550 ms.
687            e.mrp.note_peer_activity(Instant::ZERO);
688            e.mrp.on_send(2, Instant::ZERO, 0).expect("send");
689        }
690        let deadline = t.poll_deadline().expect("a deadline");
691        assert_eq!(deadline.as_micros(), 330_000);
692    }
693
694    #[test]
695    fn timeouts_are_reported_per_exchange() {
696        let mut t = Table::new(0);
697        let k = t
698            .open_initiator(
699                SessionId(1),
700                ProtocolId::SECURE_CHANNEL,
701                MrpParams::default(),
702                None,
703                Instant::ZERO,
704            )
705            .expect("open");
706        if let Some(e) = t.find_mut(k) {
707            e.mrp.on_send(9, Instant::ZERO, 0).expect("send");
708        }
709        let deadline = t.poll_deadline().expect("a deadline");
710
711        let mut seen = heapless::Vec::<(ExchangeKey, u32), 4>::new();
712        let n = t.on_timeout(deadline, 0, |key, action| {
713            if let OnTimeout::Retransmit { counter, .. } = action {
714                let _ = seen.push((key, counter));
715            }
716        });
717        assert_eq!(n, 1);
718        assert_eq!(&seen[..], &[(k, 9)]);
719    }
720}