bacnet-bip-core 0.13.0

//! The broadcast distribution table (Annex J.4.3), in a fixed array.

use core::fmt;
use core::net::{Ipv4Addr, SocketAddrV4};

use bacnet_bip_codec::{BdtEntries, BdtEntry};

/// The broadcast distribution mask of all ones: forwarded broadcasts go to
/// the peer BBMD itself, which broadcasts them on its subnet (two-hop
/// distribution, Annex J.4.3.1). A peer's subnet mask instead sends them
/// straight to that subnet's directed broadcast address (one-hop).
pub const TWO_HOP_MASK: Ipv4Addr = Ipv4Addr::BROADCAST;

/// An unused row of storage.
const EMPTY_ROW: BdtEntry = BdtEntry::new(
    SocketAddrV4::new(Ipv4Addr::UNSPECIFIED, 0),
    Ipv4Addr::UNSPECIFIED,
);

/// Where a broadcast forwarded to `row`'s subnet is sent (Annex J.4.5): the
/// row's address ORed with its inverted mask, at the row's port. A subnet
/// mask gives that subnet's directed broadcast address, and
/// [`TWO_HOP_MASK`] gives the peer BBMD itself.
///
/// ```
/// use core::net::{Ipv4Addr, SocketAddrV4};
/// use bacnet_bip_core::codec::BdtEntry;
/// use bacnet_bip_core::bbmd::distribution_address;
///
/// let peer = SocketAddrV4::new(Ipv4Addr::new(10, 0, 2, 1), 47808);
/// let one_hop = BdtEntry::new(peer, Ipv4Addr::new(255, 255, 255, 0));
/// assert_eq!(distribution_address(one_hop), SocketAddrV4::new(Ipv4Addr::new(10, 0, 2, 255), 47808));
/// let two_hop = BdtEntry::new(peer, Ipv4Addr::BROADCAST);
/// assert_eq!(distribution_address(two_hop), peer);
/// ```
#[must_use]
pub const fn distribution_address(row: BdtEntry) -> SocketAddrV4 {
    let ip = row.address.ip().to_bits() | !row.mask.to_bits();
    SocketAddrV4::new(Ipv4Addr::from_bits(ip), row.address.port())
}

/// Why [`validate_entry`] refused a BDT row.
///
/// The rules are a local security policy (#529), not Annex J's: each keeps a
/// row from turning forwarded broadcasts into traffic for an address that
/// isn't one BBMD or one subnet.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum EntryError {
    /// UDP port 0.
    ZeroPort,
    /// The address 0.0.0.0.
    UnspecifiedAddress,
    /// The address 255.255.255.255.
    LimitedBroadcastAddress,
    /// An IPv4 multicast address (224.0.0.0/4).
    MulticastAddress,
    /// A mask whose one bits aren't contiguous from the top.
    NonContiguousMask,
    /// A mask shorter than /8, whose broadcast would reach too wide a range.
    MaskTooWide,
    /// The subnet's network address (all host bits zero) under a mask
    /// shorter than /32.
    NetworkAddress,
    /// The subnet's directed broadcast address (all host bits one) under a
    /// mask shorter than /32.
    DirectedBroadcastAddress,
    /// A row whose [`distribution_address`] is 255.255.255.255.
    LimitedBroadcastTarget,
}

impl EntryError {
    /// A short description, as the host transport's errors print it.
    #[must_use]
    pub const fn reason(self) -> &'static str {
        match self {
            Self::ZeroPort => "invalid port 0",
            Self::UnspecifiedAddress => "unspecified IP",
            Self::LimitedBroadcastAddress => "limited-broadcast",
            Self::MulticastAddress => "multicast IP",
            Self::NonContiguousMask => "non-contiguous mask",
            Self::MaskTooWide => "mask prefix too wide (< /8)",
            Self::NetworkAddress => "subnet network address",
            Self::DirectedBroadcastAddress => "subnet directed-broadcast",
            Self::LimitedBroadcastTarget => "limited-broadcast target",
        }
    }
}

impl fmt::Display for EntryError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str(self.reason())
    }
}

impl core::error::Error for EntryError {}

/// Why a BDT was refused. A refused table changes nothing.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum BdtError {
    /// A row broke a rule of [`validate_entry`].
    Invalid {
        /// The row.
        entry: BdtEntry,
        /// The rule it broke.
        reason: EntryError,
    },
    /// Two rows for one B/IP address with different masks.
    ConflictingMasks {
        /// The later of the two rows.
        entry: BdtEntry,
    },
    /// The distinct rows, with this BBMD's own row where the table needs it
    /// added, would not fit.
    Capacity {
        /// Rows the table would hold.
        needed: usize,
        /// Rows the storage holds.
        available: usize,
    },
}

impl fmt::Display for BdtError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::Invalid { entry, reason } => {
                write!(f, "BDT row {} mask {}: {reason}", entry.address, entry.mask)
            }
            Self::ConflictingMasks { entry } => write!(
                f,
                "BDT rows for {} with conflicting masks (one is {})",
                entry.address, entry.mask
            ),
            Self::Capacity { needed, available } => {
                write!(
                    f,
                    "BDT of {needed} rows exceeds the capacity of {available}"
                )
            }
        }
    }
}

impl core::error::Error for BdtError {}

/// Check one BDT row against the local security policy (see
/// [`EntryError`]). Contiguous masks of /8 to /32 pass, with any unicast
/// address that isn't its subnet's network or broadcast address.
pub const fn validate_entry(entry: BdtEntry) -> Result<(), EntryError> {
    let ip = entry.address.ip().to_bits();
    let mask = entry.mask.to_bits();
    let host = !mask;
    let contiguous = host & host.wrapping_add(1) == 0;
    let prefix = mask.count_ones();
    let first_octet = ip >> 24;
    let reason = if entry.address.port() == 0 {
        EntryError::ZeroPort
    } else if ip == 0 {
        EntryError::UnspecifiedAddress
    } else if ip == u32::MAX {
        EntryError::LimitedBroadcastAddress
    } else if matches!(first_octet, 224..=239) {
        EntryError::MulticastAddress
    } else if !contiguous {
        EntryError::NonContiguousMask
    } else if prefix < 8 {
        EntryError::MaskTooWide
    } else if prefix < 32 && ip & host == 0 {
        EntryError::NetworkAddress
    } else if prefix < 32 && ip | mask == u32::MAX {
        EntryError::DirectedBroadcastAddress
    } else if ip | host == u32::MAX {
        EntryError::LimitedBroadcastTarget
    } else {
        return Ok(());
    };
    Err(reason)
}

/// What a canonical pass over a candidate table found.
struct Canonical {
    /// Distinct rows written to the output, in first-seen order.
    stored: usize,
    /// Distinct rows in the candidate; more than `stored` when the output
    /// ran out of room.
    distinct: usize,
}

/// Validate `table` and write its distinct rows to `out` in first-seen order.
///
/// Rows identical to an earlier one are dropped; a second row for an address
/// with a different mask refuses the table. Every row is checked even after
/// `out` is full, so a bad row is reported before a lack of room.
fn canonical_rows(table: BdtEntries<'_>, out: &mut [BdtEntry]) -> Result<Canonical, BdtError> {
    let mut stored = 0;
    let mut distinct = 0;
    // The index of the first distinct row that found no room: from there on,
    // earlier rows are looked up in the candidate itself.
    let mut overflow_from = None;
    for (index, entry) in table.iter().enumerate() {
        if let Err(reason) = validate_entry(entry) {
            return Err(BdtError::Invalid { entry, reason });
        }
        let earlier = match overflow_from {
            None => out[..stored]
                .iter()
                .find(|row| row.address == entry.address)
                .copied(),
            Some(from) => out[..stored]
                .iter()
                .copied()
                .chain(table.iter().take(index).skip(from))
                .find(|row| row.address == entry.address),
        };
        match earlier {
            Some(row) if row.mask != entry.mask => {
                return Err(BdtError::ConflictingMasks { entry })
            }
            Some(_) => {}
            None => {
                distinct += 1;
                match out.get_mut(stored) {
                    Some(slot) if overflow_from.is_none() => {
                        *slot = entry;
                        stored += 1;
                    }
                    _ => {
                        overflow_from.get_or_insert(index);
                    }
                }
            }
        }
    }
    Ok(Canonical { stored, distinct })
}

/// Validate a candidate BDT and write its distinct rows to `out`, in
/// first-seen order; returns how many.
///
/// Every row must pass [`validate_entry`]. A row identical to an earlier one
/// is dropped, and two rows for one B/IP address with different masks
/// refuse the table ([`BdtError::ConflictingMasks`]). When the distinct rows
/// don't fit in `out` the result is [`BdtError::Capacity`], but only after
/// every row has been checked. Unlike [`Bdt::set`], this adds no own row.
pub fn canonicalize(table: BdtEntries<'_>, out: &mut [BdtEntry]) -> Result<usize, BdtError> {
    let found = canonical_rows(table, out)?;
    if found.distinct > found.stored {
        return Err(BdtError::Capacity {
            needed: found.distinct,
            available: out.len(),
        });
    }
    Ok(found.stored)
}

/// A BBMD's broadcast distribution table: up to `N` rows, this BBMD's own
/// row included once [`Bdt::set`] has run (Annex J.4.3.2).
///
/// Rows keep the order they were given in. A table that the caller sets
/// without this BBMD's own address gets a row for it, with
/// [`TWO_HOP_MASK`], at the end; that row follows the address when
/// [`Bdt::set_own_address`] changes it.
#[derive(Clone)]
pub struct Bdt<const N: usize> {
    rows: [BdtEntry; N],
    len: usize,
    own: SocketAddrV4,
    /// The last row is the own row that `set` appended.
    own_row_appended: bool,
}

/// Shows the rows in use, not the whole array.
impl<const N: usize> fmt::Debug for Bdt<N> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("Bdt")
            .field("own", &self.own)
            .field("rows", &self.rows())
            .field("own_row_appended", &self.own_row_appended)
            .finish()
    }
}

impl<const N: usize> Bdt<N> {
    /// Rows the table holds at most.
    pub const CAPACITY: usize = N;

    /// An empty table for the BBMD at `own`, the B/IP address its peers know
    /// it by. It has no rows, not even its own, until [`Bdt::set`].
    #[must_use]
    pub const fn new(own: SocketAddrV4) -> Self {
        Self {
            rows: [EMPTY_ROW; N],
            len: 0,
            own,
            own_row_appended: false,
        }
    }

    /// This BBMD's own B/IP address.
    #[must_use]
    pub const fn own_address(&self) -> SocketAddrV4 {
        self.own
    }

    /// The rows, the own row included, as a table the codec encodes (for a
    /// Read-Broadcast-Distribution-Table-Ack, Annex J.2.4).
    #[must_use]
    pub fn entries(&self) -> BdtEntries<'_> {
        BdtEntries::from_entries(self.rows())
    }

    /// The rows, the own row included.
    #[must_use]
    pub fn rows(&self) -> &[BdtEntry] {
        &self.rows[..self.len]
    }

    /// The rows as last set, without an own row [`Bdt::set`] appended.
    #[must_use]
    pub fn configured_rows(&self) -> &[BdtEntry] {
        &self.rows[..self.len - usize::from(self.own_row_appended)]
    }

    /// Number of rows.
    #[must_use]
    pub const fn len(&self) -> usize {
        self.len
    }

    /// Whether the table has no rows.
    #[must_use]
    pub const fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// The row for the BBMD at `address`, if any; the own row counts.
    #[must_use]
    pub fn row(&self, address: SocketAddrV4) -> Option<BdtEntry> {
        self.rows()
            .iter()
            .find(|row| row.address == address)
            .copied()
    }

    /// Whether `address` has a row; the own row counts.
    #[must_use]
    pub fn contains(&self, address: SocketAddrV4) -> bool {
        self.row(address).is_some()
    }

    /// Replace the table with `table`, as [`canonicalize`] cleans it, plus a
    /// row for this BBMD's own address with [`TWO_HOP_MASK`] when `table` has
    /// none. On error the table is unchanged.
    pub fn set(&mut self, table: BdtEntries<'_>) -> Result<(), BdtError> {
        let mut next = Self::new(self.own);
        let found = canonical_rows(table, &mut next.rows)?;
        let has_own = table.iter().any(|row| row.address == self.own);
        let needed = found.distinct + usize::from(!has_own);
        if needed > N {
            return Err(BdtError::Capacity {
                needed,
                available: N,
            });
        }
        next.len = found.stored;
        next.ensure_own_row();
        *self = next;
        Ok(())
    }

    /// Change this BBMD's own B/IP address, keeping the rows.
    ///
    /// An own row that [`Bdt::set`] appended moves to the new address. A row
    /// the table lists for the old address stays, as an ordinary peer row,
    /// and the new address gets a row unless it has one. On error, for want
    /// of room for that row, nothing changes.
    pub fn set_own_address(&mut self, own: SocketAddrV4) -> Result<(), BdtError> {
        if own == self.own {
            return Ok(());
        }
        let configured = self.configured_rows();
        let has_own = configured.iter().any(|row| row.address == own);
        let needed = configured.len() + usize::from(!has_own);
        if needed > N {
            return Err(BdtError::Capacity {
                needed,
                available: N,
            });
        }
        if self.own_row_appended {
            self.len -= 1;
            self.own_row_appended = false;
        }
        self.own = own;
        self.ensure_own_row();
        Ok(())
    }

    /// Append the own row when the table lacks one. The callers have checked
    /// that it fits.
    fn ensure_own_row(&mut self) {
        if !self.contains(self.own) {
            let BdtEntry { address, mask } = BdtEntry::new(self.own, TWO_HOP_MASK);
            let row = &mut self.rows[self.len];
            // The address's IP and port one at a time: copied whole, its six
            // octets compile to a memmove call on ARMv6-M, about 1.3 KB of
            // code.
            row.address.set_ip(*address.ip());
            row.address.set_port(address.port());
            row.mask = mask;
            self.len += 1;
            self.own_row_appended = true;
        }
    }
}