bacnet_ops/bbmd/
matrix.rs

1//! The BDT consistency matrix: given the BDT read from each BBMD a survey
2//! found, which entries agree and which don't.
3//!
4//! Row *i*, column *j* says whether BBMD *i*'s BDT lists BBMD *j*. A
5//! working set of BBMDs gives a symmetric grid: each BBMD lists itself
6//! (Annex J.4.3.2 puts the local BBMD's own entry in its table), each peer
7//! that forwards to another is listed back by it, and every table uses one
8//! mask for a given BBMD, since a receiving BBMD tells directed broadcasts
9//! from unicasts by the mask in its own entry (Annex J.4.5). A broken
10//! entry makes broadcasts reach a subnet one way only, which is quiet in
11//! the field: nothing errors, devices just go missing.
12//!
13//! Pure functions only: a front end reads the tables (the TUI's network
14//! worker, the MCP server's network map) and shows the grid or findings.
15
16use std::collections::{BTreeSet, HashMap, HashSet};
17use std::net::{Ipv4Addr, SocketAddrV4};
18
19use bacnet_transport::bvll::BvlcResultCode;
20
21use super::{BdtRow, Outcome};
22
23/// What reading one BBMD's BDT gave.
24pub type Probe = Outcome<Vec<BdtRow>>;
25
26/// One cell of the grid.
27#[derive(Debug, Clone, Copy, PartialEq, Eq)]
28pub enum Cell {
29    /// The row's BDT lists the column with this mask; `mixed` when other
30    /// tables list the column with a different one.
31    Listed {
32        /// The mask.
33        mask: Ipv4Addr,
34        /// Not the mask every table uses for this BBMD.
35        mixed: bool,
36    },
37    /// Not listed, and nothing says it should be.
38    Absent,
39    /// Not listed, but should be: the column lists the row, or this is the
40    /// row's own entry.
41    Missing,
42    /// The row's table could not be read.
43    Unknown,
44}
45
46/// One problem the matrix shows.
47#[derive(Debug, Clone, PartialEq, Eq)]
48pub enum Finding {
49    /// `from` lists `to`, but `to` does not list `from`: broadcasts reach
50    /// `to`'s subnet from `from`'s, and not back.
51    Asymmetric {
52        /// The BBMD whose table has the entry.
53        from: SocketAddrV4,
54        /// The BBMD whose table lacks the entry back.
55        to: SocketAddrV4,
56    },
57    /// The BBMD's BDT has entries, but none for itself.
58    MissingSelf(SocketAddrV4),
59    /// The BBMD's BDT is empty: it forwards broadcasts to no peer, as a
60    /// BBMD that serves only foreign devices may. A note, not a problem.
61    NoPeers(SocketAddrV4),
62    /// The tables list `peer` with different masks.
63    MixedMasks {
64        /// The BBMD listed.
65        peer: SocketAddrV4,
66        /// Every mask used for it, lowest first.
67        masks: Vec<Ipv4Addr>,
68    },
69    /// The BBMD refused the read.
70    Nak {
71        /// The BBMD.
72        bbmd: SocketAddrV4,
73        /// The NAK it answered with.
74        code: BvlcResultCode,
75    },
76    /// The BBMD could not be read.
77    Unreachable {
78        /// The BBMD.
79        bbmd: SocketAddrV4,
80        /// Why.
81        reason: String,
82    },
83}
84
85impl Finding {
86    /// One line for the findings list.
87    pub fn describe(&self) -> String {
88        match self {
89            Self::Asymmetric { from, to } => {
90                format!(
91                    "{from} lists {to}, but {to} does not list {from}: broadcasts go one way only"
92                )
93            }
94            Self::MissingSelf(bbmd) => {
95                format!("{bbmd} has no entry for itself (Annex J.4.3.2)")
96            }
97            Self::NoPeers(bbmd) => {
98                format!("{bbmd} has an empty BDT: it forwards to no peer BBMD")
99            }
100            Self::MixedMasks { peer, masks } => {
101                let masks: Vec<String> = masks.iter().map(Ipv4Addr::to_string).collect();
102                format!(
103                    "{peer} is listed with different masks: {}",
104                    masks.join(", ")
105                )
106            }
107            Self::Nak { bbmd, code } => format!("{bbmd} refused the BDT read ({code})"),
108            Self::Unreachable { bbmd, reason } => format!("{bbmd} could not be read ({reason})"),
109        }
110    }
111}
112
113/// The most BBMDs the grid shows, rows and columns alike; the rest are
114/// counted in [`Matrix::omitted`]. The findings cover them all.
115pub const GRID_CAP: usize = 32;
116
117/// The grid and its findings.
118#[derive(Debug, Clone, PartialEq, Eq)]
119pub struct Matrix {
120    /// The BBMDs, rows and columns alike: those probed in the order the
121    /// survey found them, then those only listed, at most [`GRID_CAP`].
122    pub bbmds: Vec<SocketAddrV4>,
123    /// `cells[row][column]`.
124    pub cells: Vec<Vec<Cell>>,
125    /// BBMDs left out of the grid past [`GRID_CAP`].
126    pub omitted: usize,
127    /// Every problem found, in the order the view lists them.
128    pub findings: Vec<Finding>,
129}
130
131impl Matrix {
132    /// Build the grid from what a survey read. A BBMD some table lists but
133    /// the survey has no probe for is added as a row that could not be read.
134    ///
135    /// The work is bounded by what was read, not by what the tables list:
136    /// the findings compare the tables read with one another, and the grid
137    /// stops at [`GRID_CAP`] BBMDs.
138    pub fn build(probes: &[(SocketAddrV4, Probe)]) -> Self {
139        let mut seen = HashSet::new();
140        let mut bbmds: Vec<SocketAddrV4> = Vec::new();
141        for (bbmd, _) in probes {
142            if seen.insert(*bbmd) {
143                bbmds.push(*bbmd);
144            }
145        }
146        for (_, probe) in probes {
147            for row in probe.table().map_or(&[][..], Vec::as_slice) {
148                if seen.insert(row.address) {
149                    bbmds.push(row.address);
150                }
151            }
152        }
153        // Each BBMD's table, from its first probe.
154        let mut tables: HashMap<SocketAddrV4, &[BdtRow]> = HashMap::new();
155        for (bbmd, probe) in probes {
156            if let Some(rows) = probe.table() {
157                tables.entry(*bbmd).or_insert(rows.as_slice());
158            }
159        }
160        // The mask a table gives a BBMD: its first entry for it.
161        let listed = |row: SocketAddrV4, column: SocketAddrV4| -> Option<Ipv4Addr> {
162            tables
163                .get(&row)?
164                .iter()
165                .find(|entry| entry.address == column)
166                .map(|entry| entry.mask)
167        };
168        let mut findings = Vec::new();
169        for (bbmd, probe) in probes {
170            match probe {
171                Probe::Nak(code) => findings.push(Finding::Nak {
172                    bbmd: *bbmd,
173                    code: *code,
174                }),
175                Probe::Unreachable(reason) => findings.push(Finding::Unreachable {
176                    bbmd: *bbmd,
177                    reason: reason.clone(),
178                }),
179                Probe::Table(_) | Probe::Skipped => {}
180            }
181        }
182        // Every mask the tables give each BBMD.
183        let mut masks: HashMap<SocketAddrV4, BTreeSet<Ipv4Addr>> = HashMap::new();
184        for rows in tables.values() {
185            let mut first = HashSet::new();
186            for entry in rows.iter().filter(|entry| first.insert(entry.address)) {
187                masks.entry(entry.address).or_default().insert(entry.mask);
188            }
189        }
190        let mixed: HashSet<SocketAddrV4> = bbmds
191            .iter()
192            .copied()
193            .filter(|bbmd| masks.get(bbmd).is_some_and(|set| set.len() > 1))
194            .collect();
195        for bbmd in bbmds.iter().filter(|bbmd| mixed.contains(bbmd)) {
196            findings.push(Finding::MixedMasks {
197                peer: *bbmd,
198                masks: masks[bbmd].iter().copied().collect(),
199            });
200        }
201        // The tables read, compared with one another.
202        let read: Vec<SocketAddrV4> = bbmds
203            .iter()
204            .copied()
205            .filter(|bbmd| tables.contains_key(bbmd))
206            .collect();
207        for &row in &read {
208            for &column in &read {
209                if listed(row, column).is_some() {
210                    continue;
211                }
212                if row == column {
213                    findings.push(match tables[&row].is_empty() {
214                        true => Finding::NoPeers(row),
215                        false => Finding::MissingSelf(row),
216                    });
217                } else if listed(column, row).is_some() {
218                    findings.push(Finding::Asymmetric {
219                        from: column,
220                        to: row,
221                    });
222                }
223            }
224        }
225        let omitted = bbmds.len().saturating_sub(GRID_CAP);
226        bbmds.truncate(GRID_CAP);
227        let n = bbmds.len();
228        let mut cells = vec![vec![Cell::Unknown; n]; n];
229        for (r, &row) in bbmds.iter().enumerate() {
230            let Some(table) = tables.get(&row) else {
231                continue;
232            };
233            for (c, &column) in bbmds.iter().enumerate() {
234                cells[r][c] = match listed(row, column) {
235                    Some(mask) => Cell::Listed {
236                        mask,
237                        mixed: mixed.contains(&column),
238                    },
239                    None if row == column && !table.is_empty() => Cell::Missing,
240                    None if row != column && listed(column, row).is_some() => Cell::Missing,
241                    None => Cell::Absent,
242                };
243            }
244        }
245        Self {
246            bbmds,
247            cells,
248            omitted,
249            findings,
250        }
251    }
252
253    /// True when every table was read, the grid shows every BBMD and
254    /// nothing disagrees (an empty table is a note, not a disagreement).
255    pub fn consistent(&self) -> bool {
256        self.omitted == 0
257            && self
258                .findings
259                .iter()
260                .all(|f| matches!(f, Finding::NoPeers(_)))
261            && self
262                .cells
263                .iter()
264                .flatten()
265                .all(|cell| *cell != Cell::Unknown)
266    }
267}
268
269#[cfg(test)]
270mod tests {
271    use super::*;
272
273    const UNICAST: Ipv4Addr = Ipv4Addr::BROADCAST;
274    const SUBNET: Ipv4Addr = Ipv4Addr::new(255, 255, 255, 0);
275
276    fn at(last: u8) -> SocketAddrV4 {
277        SocketAddrV4::new(Ipv4Addr::new(10, 0, last, 1), 47808)
278    }
279
280    fn table(rows: &[(u8, Ipv4Addr)]) -> Probe {
281        Probe::Table(
282            rows.iter()
283                .map(|(last, mask)| BdtRow {
284                    address: at(*last),
285                    mask: *mask,
286                })
287                .collect(),
288        )
289    }
290
291    fn listed(mask: Ipv4Addr) -> Cell {
292        Cell::Listed { mask, mixed: false }
293    }
294
295    #[test]
296    fn symmetric_tables_are_consistent() {
297        let both = table(&[(1, UNICAST), (2, UNICAST)]);
298        let matrix = Matrix::build(&[(at(1), both.clone()), (at(2), both)]);
299        assert_eq!(matrix.bbmds, [at(1), at(2)]);
300        assert!(matrix.findings.is_empty(), "{:?}", matrix.findings);
301        assert!(matrix.consistent());
302        assert!(matrix.cells.iter().flatten().all(|c| *c == listed(UNICAST)));
303    }
304
305    #[test]
306    fn a_one_way_entry_is_flagged_on_the_side_that_lacks_it() {
307        let matrix = Matrix::build(&[
308            (at(1), table(&[(1, UNICAST), (2, UNICAST)])),
309            (at(2), table(&[(2, UNICAST)])),
310        ]);
311        // A lists B; B lacks A.
312        assert_eq!(matrix.cells[0][1], listed(UNICAST));
313        assert_eq!(matrix.cells[1][0], Cell::Missing);
314        assert_eq!(
315            matrix.findings,
316            [Finding::Asymmetric {
317                from: at(1),
318                to: at(2)
319            }]
320        );
321        assert!(!matrix.consistent());
322        assert!(matrix.findings[0].describe().contains("one way"));
323    }
324
325    #[test]
326    fn a_table_without_its_own_entry_is_flagged() {
327        let matrix = Matrix::build(&[
328            (at(1), table(&[(2, UNICAST)])),
329            (at(2), table(&[(1, UNICAST), (2, UNICAST)])),
330        ]);
331        assert_eq!(matrix.cells[0][0], Cell::Missing);
332        assert_eq!(matrix.findings, [Finding::MissingSelf(at(1))]);
333    }
334
335    #[test]
336    fn two_masks_for_one_bbmd_are_flagged_in_its_column() {
337        let matrix = Matrix::build(&[
338            (at(1), table(&[(1, UNICAST), (2, SUBNET)])),
339            (at(2), table(&[(1, UNICAST), (2, UNICAST)])),
340        ]);
341        let mixed = |mask| Cell::Listed { mask, mixed: true };
342        assert_eq!(matrix.cells[0][1], mixed(SUBNET));
343        assert_eq!(matrix.cells[1][1], mixed(UNICAST));
344        assert_eq!(matrix.cells[0][0], listed(UNICAST));
345        assert_eq!(
346            matrix.findings,
347            [Finding::MixedMasks {
348                peer: at(2),
349                masks: vec![SUBNET, UNICAST]
350            }]
351        );
352    }
353
354    #[test]
355    fn unread_peers_are_unknown_and_named() {
356        let matrix = Matrix::build(&[
357            (at(1), table(&[(1, UNICAST), (2, UNICAST), (3, UNICAST)])),
358            (
359                at(2),
360                Probe::Nak(BvlcResultCode::READ_BROADCAST_DISTRIBUTION_TABLE_NAK),
361            ),
362            (at(3), Probe::Unreachable("no answer".into())),
363        ]);
364        assert_eq!(matrix.cells[1], [Cell::Unknown; 3]);
365        assert_eq!(matrix.cells[2], [Cell::Unknown; 3]);
366        // Nothing is known of their tables, so no asymmetry is claimed.
367        assert_eq!(matrix.cells[0], [listed(UNICAST); 3]);
368        assert_eq!(matrix.findings.len(), 2);
369        assert!(matches!(matrix.findings[0], Finding::Nak { bbmd, .. } if bbmd == at(2)));
370        assert!(matches!(
371            matrix.findings[1],
372            Finding::Unreachable { bbmd, .. } if bbmd == at(3)
373        ));
374        assert!(!matrix.consistent());
375    }
376
377    #[test]
378    fn a_listed_bbmd_without_a_probe_is_a_row_that_was_not_read() {
379        let matrix = Matrix::build(&[(at(1), table(&[(1, UNICAST), (4, UNICAST)]))]);
380        assert_eq!(matrix.bbmds, [at(1), at(4)]);
381        assert_eq!(matrix.cells[1], [Cell::Unknown; 2]);
382        assert!(matrix.findings.is_empty());
383        assert!(!matrix.consistent(), "an unread table is not consistent");
384    }
385
386    /// An empty table (a BBMD for foreign devices only) is a note, and the
387    /// grid stays consistent; a peer listing it still makes a one-way entry.
388    #[test]
389    fn an_empty_table_is_a_note_not_a_problem() {
390        let matrix = Matrix::build(&[(at(1), table(&[]))]);
391        assert_eq!(matrix.findings, [Finding::NoPeers(at(1))]);
392        assert_eq!(matrix.cells, [[Cell::Absent]]);
393        assert!(matrix.consistent());
394        let matrix = Matrix::build(&[
395            (at(1), table(&[(1, UNICAST), (2, UNICAST)])),
396            (at(2), table(&[])),
397        ]);
398        assert_eq!(
399            matrix.findings,
400            [
401                Finding::Asymmetric {
402                    from: at(1),
403                    to: at(2)
404                },
405                Finding::NoPeers(at(2)),
406            ]
407        );
408        assert!(!matrix.consistent());
409    }
410
411    #[test]
412    fn peers_that_list_neither_way_are_absent_not_missing() {
413        let matrix = Matrix::build(&[
414            (at(1), table(&[(1, UNICAST), (2, UNICAST), (3, UNICAST)])),
415            (at(2), table(&[(1, UNICAST), (2, UNICAST)])),
416            (at(3), table(&[(1, UNICAST), (3, UNICAST)])),
417        ]);
418        assert_eq!(matrix.cells[1][2], Cell::Absent);
419        assert_eq!(matrix.cells[2][1], Cell::Absent);
420        assert!(matrix.consistent());
421    }
422}
bacnet_ops/bbmd/matrix.rs

bacnet_ops/bbmd/
matrix.rs
