umsh_node/
peer_repeaters.rs

1//! What a node knows about the repeaters around it, and how it answers a
2//! [Peer Repeaters Request](../../docs/protocol/src/mac-commands.md).
3//!
4//! Two sources feed one answer, because neither is enough on its own:
5//!
6//! - **Identities.** A repeater that advertises tells its neighbors its name,
7//!   its position, and the regions it forwards for. None of that can be
8//!   recovered from a hint, and an identity that arrived over several hops
9//!   says nothing about the link to the node that sent it.
10//! - **Transmitter observations** ([`umsh_mac::TransmitterObservations`]).
11//!   Every frame off the air proves who was on it and how well they were
12//!   heard, including hops that never send this node anything of their own.
13//!
14//! A [`RouterHint`] is the first two bytes of a public key and a [`NodeHint`]
15//! the first three, so the observation's key is a prefix of the identity's.
16//! That is what lets the two merge: an identity claims the observation whose
17//! hint it starts with, and an observation nothing claims becomes an entry
18//! naming a hop by its router hint and reporting only what was heard.
19
20use alloc::string::String;
21use alloc::vec::Vec;
22
23use umsh_core::{NodeHint, PublicKey, RouterHint};
24
25use crate::identity::{NodeCapabilities, NodeIdentityPayload, NodeRole};
26use crate::location::NodeLocation;
27
28/// How many identity-bearing repeaters the table remembers.
29///
30/// Sized to the MAC's observation table: the two merge into one listing, and
31/// a listing longer than the 1-byte Total the response reports would have to
32/// be truncated anyway.
33pub const MAX_PEER_REPEATERS: usize = 16;
34
35/// Region codes kept per peer, matching the identity option's own cap.
36pub const MAX_PEER_REGIONS: usize = 10;
37
38/// What one repeater's identity told this node about it.
39#[derive(Clone, Debug, PartialEq, Eq)]
40pub struct PeerRepeaterRecord {
41    /// The whole node hint, since an identity carries the whole key.
42    pub hint: NodeHint,
43    pub name: Option<String>,
44    pub location: Option<NodeLocation>,
45    /// The codes the peer flood-forwards for, derived from the region
46    /// strings its identity carried.
47    pub regions: Vec<[u8; 2]>,
48    /// When the identity arrived, on the monotonic clock.
49    pub last_identity_ms: u64,
50}
51
52impl PeerRepeaterRecord {
53    /// The router hint an observation would be keyed by — the first two
54    /// bytes of the same public key.
55    pub fn router_hint(&self) -> RouterHint {
56        RouterHint([self.hint.0[0], self.hint.0[1]])
57    }
58}
59
60/// The repeaters whose identities this node has seen.
61///
62/// RAM-only: a listing describes a neighborhood as it is now, and a table
63/// restored from flash would name repeaters that may have moved or gone.
64#[derive(Clone, Debug, Default)]
65pub struct PeerRepeaterTable {
66    records: Vec<PeerRepeaterRecord>,
67    /// Bumped on every mutation, so a paging cursor can tell that the list
68    /// it was walking is no longer the list it started on.
69    generation: u16,
70}
71
72impl PeerRepeaterTable {
73    pub fn new() -> Self {
74        Self::default()
75    }
76
77    /// Whether an identity describes a repeater, and so belongs here.
78    ///
79    /// The capability is the claim that matters — a node may forward while
80    /// presenting itself as something else — but a node whose whole role is
81    /// repeating counts even if it advertises no capability bitmap.
82    pub fn is_repeater(identity: &NodeIdentityPayload) -> bool {
83        identity.capabilities.contains(NodeCapabilities::REPEATER)
84            || identity.role == NodeRole::Repeater
85    }
86
87    /// Record what an identity said, if it came from a repeater.
88    ///
89    /// Returns whether the table changed. A repeat identity replaces the
90    /// record rather than merging with it: the newest advertisement is the
91    /// node's own account of itself.
92    pub fn observe_identity(
93        &mut self,
94        from: &PublicKey,
95        identity: &NodeIdentityPayload,
96        now_ms: u64,
97    ) -> bool {
98        if !Self::is_repeater(identity) {
99            return false;
100        }
101        let record = PeerRepeaterRecord {
102            hint: from.hint(),
103            name: identity.name.clone(),
104            location: identity.location,
105            regions: region_codes(identity),
106            last_identity_ms: now_ms,
107        };
108        self.generation = self.generation.wrapping_add(1);
109        if let Some(existing) = self
110            .records
111            .iter_mut()
112            .find(|entry| entry.hint == record.hint)
113        {
114            *existing = record;
115            return true;
116        }
117        if self.records.len() < MAX_PEER_REPEATERS {
118            self.records.push(record);
119            return true;
120        }
121        // Full: the identity heard longest ago is the one whose absence says
122        // the least.
123        let Some(oldest) = self
124            .records
125            .iter_mut()
126            .min_by_key(|entry| entry.last_identity_ms)
127        else {
128            return false;
129        };
130        *oldest = record;
131        true
132    }
133
134    pub fn iter(&self) -> impl Iterator<Item = &PeerRepeaterRecord> {
135        self.records.iter()
136    }
137
138    pub fn len(&self) -> usize {
139        self.records.len()
140    }
141
142    pub fn is_empty(&self) -> bool {
143        self.records.is_empty()
144    }
145
146    /// The value a paging cursor carries, so a follow-up request that
147    /// resumes into a changed list is recognized as stale.
148    pub fn generation(&self) -> u16 {
149        self.generation
150    }
151}
152
153/// Derive the forwarding codes from an identity's region strings.
154///
155/// The identity carries strings and an entry carries codes: the entry format
156/// is tighter on space, and the string form is available from the peer's own
157/// identity when one is wanted.
158fn region_codes(identity: &NodeIdentityPayload) -> Vec<[u8; 2]> {
159    let Some(regions) = identity.supported_regions.as_ref() else {
160        return Vec::new();
161    };
162    regions
163        .iter()
164        .filter_map(|region| region.parse::<umsh_core::RegionCode>().ok())
165        .map(|code| code.to_bytes())
166        .take(MAX_PEER_REGIONS)
167        .collect()
168}
169
170/// One row of a merged listing: everything known about one peer repeater,
171/// from either source or both.
172#[derive(Clone, Debug, PartialEq, Eq)]
173pub struct MergedPeerRepeater {
174    /// Three bytes when an identity supplied the whole node hint, two when
175    /// only an observation named this hop.
176    pub hint: Vec<u8>,
177    pub name: Option<String>,
178    pub location: Option<NodeLocation>,
179    pub regions: Vec<[u8; 2]>,
180    /// The most recent reception, when one was measured.
181    pub rssi_dbm: Option<i16>,
182    pub snr: Option<umsh_hal::Snr>,
183    /// Minutes since this peer was last heard from, by either source.
184    pub last_heard_min: Option<u16>,
185}
186
187/// Merge the identity table with the MAC's transmitter observations.
188///
189/// Identity records come first and claim the observation whose router hint
190/// they start with; each remaining observation becomes a two-byte-hint entry.
191/// Signal figures come only from observations — an identity that arrived
192/// flooded crossed hops this node never heard, so its arrival says nothing
193/// about the link to the peer that owns it.
194pub fn merge<'a>(
195    identities: &PeerRepeaterTable,
196    observations: impl IntoIterator<Item = &'a umsh_mac::TransmitterObservation>,
197    now_ms: u64,
198) -> Vec<MergedPeerRepeater> {
199    let observations: Vec<&umsh_mac::TransmitterObservation> = observations.into_iter().collect();
200    let mut merged = Vec::new();
201    let mut claimed: Vec<RouterHint> = Vec::new();
202
203    for record in identities.iter() {
204        let router_hint = record.router_hint();
205        let observation = observations
206            .iter()
207            .find(|entry| entry.hint == router_hint)
208            .copied();
209        if observation.is_some() {
210            claimed.push(router_hint);
211        }
212        merged.push(MergedPeerRepeater {
213            hint: Vec::from(&record.hint.0[..]),
214            name: record.name.clone(),
215            location: record.location,
216            regions: record.regions.clone(),
217            rssi_dbm: observation.map(|entry| entry.rssi_dbm),
218            snr: observation.map(|entry| entry.snr),
219            last_heard_min: minutes_since(
220                [
221                    Some(record.last_identity_ms),
222                    observation.map(|entry| entry.last_seen_ms),
223                ]
224                .into_iter()
225                .flatten()
226                .max(),
227                now_ms,
228            ),
229        });
230    }
231
232    for observation in observations {
233        if claimed.contains(&observation.hint) {
234            continue;
235        }
236        merged.push(MergedPeerRepeater {
237            hint: Vec::from(&observation.hint.0[..]),
238            name: None,
239            location: None,
240            regions: Vec::new(),
241            rssi_dbm: Some(observation.rssi_dbm),
242            snr: Some(observation.snr),
243            last_heard_min: minutes_since(Some(observation.last_seen_ms), now_ms),
244        });
245    }
246
247    merged
248}
249
250/// Whole minutes between `then_ms` and now, saturating at the two octets the
251/// wire form allows — about 45 days, past which "longer ago than that" is the
252/// only useful answer anyway.
253fn minutes_since(then_ms: Option<u64>, now_ms: u64) -> Option<u16> {
254    let then_ms = then_ms?;
255    let elapsed_min = now_ms.saturating_sub(then_ms) / 60_000;
256    Some(u16::try_from(elapsed_min).unwrap_or(u16::MAX))
257}
258
259#[cfg(test)]
260mod tests {
261    use super::*;
262    use umsh_hal::Snr;
263
264    fn key(seed: u8) -> PublicKey {
265        PublicKey([seed; 32])
266    }
267
268    fn repeater_identity(name: &str, regions: &[&str]) -> NodeIdentityPayload {
269        NodeIdentityPayload {
270            role: NodeRole::Repeater,
271            capabilities: NodeCapabilities::REPEATER,
272            name: Some(String::from(name)),
273            location: None,
274            altitude_m: None,
275            timestamp: None,
276            supported_regions: Some(regions.iter().map(|text| String::from(*text)).collect()),
277            nonce: None,
278            signature: None,
279        }
280    }
281
282    fn observation(hint: RouterHint, last_seen_ms: u64) -> umsh_mac::TransmitterObservation {
283        umsh_mac::TransmitterObservation {
284            hint,
285            rssi_dbm: -95,
286            snr: Snr::from_decibels(2),
287            last_seen_ms,
288        }
289    }
290
291    #[test]
292    fn only_repeaters_are_recorded() {
293        let mut table = PeerRepeaterTable::new();
294        let mut chat = repeater_identity("Handset", &[]);
295        chat.role = NodeRole::Chat;
296        chat.capabilities = NodeCapabilities::TEXT_MESSAGES;
297        assert!(!table.observe_identity(&key(1), &chat, 0));
298        assert!(table.is_empty());
299
300        // The capability alone is enough — a node may forward while
301        // presenting itself as something else.
302        let mut forwarding_handset = chat.clone();
303        forwarding_handset.capabilities |= NodeCapabilities::REPEATER;
304        assert!(table.observe_identity(&key(1), &forwarding_handset, 0));
305        assert_eq!(table.len(), 1);
306    }
307
308    #[test]
309    fn an_identity_supplies_the_name_and_regions_an_observation_cannot() {
310        let mut table = PeerRepeaterTable::new();
311        table.observe_identity(&key(0xAA), &repeater_identity("Ridge", &["SJC"]), 1_000);
312
313        let record = table.iter().next().unwrap();
314        assert_eq!(record.name.as_deref(), Some("Ridge"));
315        assert_eq!(record.regions, [[0x78, 0x53]]);
316        assert_eq!(record.hint, key(0xAA).hint());
317    }
318
319    /// A router hint is a node hint's first two bytes, which is the whole
320    /// reason the two tables can be joined at all.
321    #[test]
322    fn an_identity_claims_the_observation_whose_hint_it_starts_with() {
323        let mut table = PeerRepeaterTable::new();
324        table.observe_identity(&key(0xAA), &repeater_identity("Ridge", &["SJC"]), 60_000);
325        let hint = key(0xAA).hint();
326        let observations = [
327            observation(RouterHint([hint.0[0], hint.0[1]]), 120_000),
328            observation(RouterHint([0x11, 0x22]), 60_000),
329        ];
330
331        let merged = merge(&table, observations.iter(), 180_000);
332        assert_eq!(merged.len(), 2);
333
334        assert_eq!(merged[0].hint, hint.0);
335        assert_eq!(merged[0].name.as_deref(), Some("Ridge"));
336        assert_eq!(merged[0].rssi_dbm, Some(-95));
337        assert_eq!(
338            merged[0].last_heard_min,
339            Some(1),
340            "the newer of the two sources is when it was last heard"
341        );
342
343        // An observation nothing claims still names a hop, by the only name
344        // a trace gives it.
345        assert_eq!(merged[1].hint, [0x11, 0x22]);
346        assert_eq!(merged[1].name, None);
347        assert_eq!(merged[1].rssi_dbm, Some(-95));
348        assert_eq!(merged[1].last_heard_min, Some(2));
349    }
350
351    /// An identity may arrive over hops this node never heard, so it is not
352    /// evidence about the link to the peer that owns it.
353    #[test]
354    fn an_unobserved_identity_reports_no_signal() {
355        let mut table = PeerRepeaterTable::new();
356        table.observe_identity(&key(0xAA), &repeater_identity("Far", &[]), 0);
357        let merged = merge(&table, [].iter(), 60_000);
358        assert_eq!(merged.len(), 1);
359        assert_eq!(merged[0].rssi_dbm, None);
360        assert_eq!(merged[0].snr, None);
361        assert_eq!(merged[0].last_heard_min, Some(1));
362    }
363
364    #[test]
365    fn a_repeat_identity_replaces_the_record_and_moves_the_generation() {
366        let mut table = PeerRepeaterTable::new();
367        table.observe_identity(&key(0xAA), &repeater_identity("Ridge", &["SJC"]), 0);
368        let first = table.generation();
369        table.observe_identity(&key(0xAA), &repeater_identity("Ridge Two", &[]), 1_000);
370        assert_eq!(table.len(), 1);
371        assert_ne!(table.generation(), first);
372        let record = table.iter().next().unwrap();
373        assert_eq!(record.name.as_deref(), Some("Ridge Two"));
374        assert!(
375            record.regions.is_empty(),
376            "the newest account is the whole account"
377        );
378    }
379
380    #[test]
381    fn a_full_table_drops_the_identity_heard_longest_ago() {
382        let mut table = PeerRepeaterTable::new();
383        for seed in 0..MAX_PEER_REPEATERS as u8 {
384            table.observe_identity(
385                &key(seed),
386                &repeater_identity("Peer", &[]),
387                1_000 + u64::from(seed),
388            );
389        }
390        table.observe_identity(&key(200), &repeater_identity("Newcomer", &[]), 9_000);
391        assert_eq!(table.len(), MAX_PEER_REPEATERS);
392        assert!(table.iter().any(|entry| entry.hint == key(200).hint()));
393        assert!(
394            !table.iter().any(|entry| entry.hint == key(0).hint()),
395            "the oldest identity is the one that left"
396        );
397    }
398
399    #[test]
400    fn last_heard_saturates_rather_than_wrapping() {
401        assert_eq!(minutes_since(Some(0), 60_000 * 65_535), Some(u16::MAX));
402        assert_eq!(minutes_since(Some(0), 60_000 * 100_000), Some(u16::MAX));
403        assert_eq!(minutes_since(None, 1_000), None);
404        // A clock that ran backwards reads as "just now", not as 45 days.
405        assert_eq!(minutes_since(Some(5_000), 1_000), Some(0));
406    }
407}
umsh_node/peer_repeaters.rs

umsh_node/
peer_repeaters.rs
