summaryrefslogtreecommitdiff
path: root/src/iface/neighbor.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/iface/neighbor.rs')
-rw-r--r--src/iface/neighbor.rs306
1 files changed, 306 insertions, 0 deletions
diff --git a/src/iface/neighbor.rs b/src/iface/neighbor.rs
new file mode 100644
index 0000000..0c451fa
--- /dev/null
+++ b/src/iface/neighbor.rs
@@ -0,0 +1,306 @@
+// Heads up! Before working on this file you should read, at least,
+// the parts of RFC 1122 that discuss ARP.
+
+use heapless::LinearMap;
+
+use crate::config::IFACE_NEIGHBOR_CACHE_COUNT;
+use crate::time::{Duration, Instant};
+use crate::wire::{HardwareAddress, IpAddress};
+
+/// A cached neighbor.
+///
+/// A neighbor mapping translates from a protocol address to a hardware address,
+/// and contains the timestamp past which the mapping should be discarded.
+#[derive(Debug, Clone, Copy)]
+#[cfg_attr(feature = "defmt", derive(defmt::Format))]
+pub struct Neighbor {
+ hardware_addr: HardwareAddress,
+ expires_at: Instant,
+}
+
+/// An answer to a neighbor cache lookup.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+#[cfg_attr(feature = "defmt", derive(defmt::Format))]
+pub(crate) enum Answer {
+ /// The neighbor address is in the cache and not expired.
+ Found(HardwareAddress),
+ /// The neighbor address is not in the cache, or has expired.
+ NotFound,
+ /// The neighbor address is not in the cache, or has expired,
+ /// and a lookup has been made recently.
+ RateLimited,
+}
+
+impl Answer {
+ /// Returns whether a valid address was found.
+ pub(crate) fn found(&self) -> bool {
+ match self {
+ Answer::Found(_) => true,
+ _ => false,
+ }
+ }
+}
+
+/// A neighbor cache backed by a map.
+#[derive(Debug)]
+pub struct Cache {
+ storage: LinearMap<IpAddress, Neighbor, IFACE_NEIGHBOR_CACHE_COUNT>,
+ silent_until: Instant,
+}
+
+impl Cache {
+ /// Minimum delay between discovery requests, in milliseconds.
+ pub(crate) const SILENT_TIME: Duration = Duration::from_millis(1_000);
+
+ /// Neighbor entry lifetime, in milliseconds.
+ pub(crate) const ENTRY_LIFETIME: Duration = Duration::from_millis(60_000);
+
+ /// Create a cache.
+ pub fn new() -> Self {
+ Self {
+ storage: LinearMap::new(),
+ silent_until: Instant::from_millis(0),
+ }
+ }
+
+ pub fn fill(
+ &mut self,
+ protocol_addr: IpAddress,
+ hardware_addr: HardwareAddress,
+ timestamp: Instant,
+ ) {
+ debug_assert!(protocol_addr.is_unicast());
+ debug_assert!(hardware_addr.is_unicast());
+
+ let expires_at = timestamp + Self::ENTRY_LIFETIME;
+ self.fill_with_expiration(protocol_addr, hardware_addr, expires_at);
+ }
+
+ pub fn fill_with_expiration(
+ &mut self,
+ protocol_addr: IpAddress,
+ hardware_addr: HardwareAddress,
+ expires_at: Instant,
+ ) {
+ debug_assert!(protocol_addr.is_unicast());
+ debug_assert!(hardware_addr.is_unicast());
+
+ let neighbor = Neighbor {
+ expires_at,
+ hardware_addr,
+ };
+ match self.storage.insert(protocol_addr, neighbor) {
+ Ok(Some(old_neighbor)) => {
+ if old_neighbor.hardware_addr != hardware_addr {
+ net_trace!(
+ "replaced {} => {} (was {})",
+ protocol_addr,
+ hardware_addr,
+ old_neighbor.hardware_addr
+ );
+ }
+ }
+ Ok(None) => {
+ net_trace!("filled {} => {} (was empty)", protocol_addr, hardware_addr);
+ }
+ Err((protocol_addr, neighbor)) => {
+ // If we're going down this branch, it means the cache is full, and we need to evict an entry.
+ let old_protocol_addr = *self
+ .storage
+ .iter()
+ .min_by_key(|(_, neighbor)| neighbor.expires_at)
+ .expect("empty neighbor cache storage")
+ .0;
+
+ let _old_neighbor = self.storage.remove(&old_protocol_addr).unwrap();
+ match self.storage.insert(protocol_addr, neighbor) {
+ Ok(None) => {
+ net_trace!(
+ "filled {} => {} (evicted {} => {})",
+ protocol_addr,
+ hardware_addr,
+ old_protocol_addr,
+ _old_neighbor.hardware_addr
+ );
+ }
+ // We've covered everything else above.
+ _ => unreachable!(),
+ }
+ }
+ }
+ }
+
+ pub(crate) fn lookup(&self, protocol_addr: &IpAddress, timestamp: Instant) -> Answer {
+ assert!(protocol_addr.is_unicast());
+
+ if let Some(&Neighbor {
+ expires_at,
+ hardware_addr,
+ }) = self.storage.get(protocol_addr)
+ {
+ if timestamp < expires_at {
+ return Answer::Found(hardware_addr);
+ }
+ }
+
+ if timestamp < self.silent_until {
+ Answer::RateLimited
+ } else {
+ Answer::NotFound
+ }
+ }
+
+ pub(crate) fn limit_rate(&mut self, timestamp: Instant) {
+ self.silent_until = timestamp + Self::SILENT_TIME;
+ }
+
+ pub(crate) fn flush(&mut self) {
+ self.storage.clear()
+ }
+}
+
+#[cfg(feature = "medium-ethernet")]
+#[cfg(test)]
+mod test {
+ use super::*;
+ use crate::wire::ip::test::{MOCK_IP_ADDR_1, MOCK_IP_ADDR_2, MOCK_IP_ADDR_3, MOCK_IP_ADDR_4};
+
+ use crate::wire::EthernetAddress;
+
+ const HADDR_A: HardwareAddress = HardwareAddress::Ethernet(EthernetAddress([0, 0, 0, 0, 0, 1]));
+ const HADDR_B: HardwareAddress = HardwareAddress::Ethernet(EthernetAddress([0, 0, 0, 0, 0, 2]));
+ const HADDR_C: HardwareAddress = HardwareAddress::Ethernet(EthernetAddress([0, 0, 0, 0, 0, 3]));
+ const HADDR_D: HardwareAddress = HardwareAddress::Ethernet(EthernetAddress([0, 0, 0, 0, 0, 4]));
+
+ #[test]
+ fn test_fill() {
+ let mut cache = Cache::new();
+
+ assert!(!cache
+ .lookup(&MOCK_IP_ADDR_1, Instant::from_millis(0))
+ .found());
+ assert!(!cache
+ .lookup(&MOCK_IP_ADDR_2, Instant::from_millis(0))
+ .found());
+
+ cache.fill(MOCK_IP_ADDR_1, HADDR_A, Instant::from_millis(0));
+ assert_eq!(
+ cache.lookup(&MOCK_IP_ADDR_1, Instant::from_millis(0)),
+ Answer::Found(HADDR_A)
+ );
+ assert!(!cache
+ .lookup(&MOCK_IP_ADDR_2, Instant::from_millis(0))
+ .found());
+ assert!(!cache
+ .lookup(
+ &MOCK_IP_ADDR_1,
+ Instant::from_millis(0) + Cache::ENTRY_LIFETIME * 2
+ )
+ .found(),);
+
+ cache.fill(MOCK_IP_ADDR_1, HADDR_A, Instant::from_millis(0));
+ assert!(!cache
+ .lookup(&MOCK_IP_ADDR_2, Instant::from_millis(0))
+ .found());
+ }
+
+ #[test]
+ fn test_expire() {
+ let mut cache = Cache::new();
+
+ cache.fill(MOCK_IP_ADDR_1, HADDR_A, Instant::from_millis(0));
+ assert_eq!(
+ cache.lookup(&MOCK_IP_ADDR_1, Instant::from_millis(0)),
+ Answer::Found(HADDR_A)
+ );
+ assert!(!cache
+ .lookup(
+ &MOCK_IP_ADDR_1,
+ Instant::from_millis(0) + Cache::ENTRY_LIFETIME * 2
+ )
+ .found(),);
+ }
+
+ #[test]
+ fn test_replace() {
+ let mut cache = Cache::new();
+
+ cache.fill(MOCK_IP_ADDR_1, HADDR_A, Instant::from_millis(0));
+ assert_eq!(
+ cache.lookup(&MOCK_IP_ADDR_1, Instant::from_millis(0)),
+ Answer::Found(HADDR_A)
+ );
+ cache.fill(MOCK_IP_ADDR_1, HADDR_B, Instant::from_millis(0));
+ assert_eq!(
+ cache.lookup(&MOCK_IP_ADDR_1, Instant::from_millis(0)),
+ Answer::Found(HADDR_B)
+ );
+ }
+
+ #[test]
+ fn test_evict() {
+ let mut cache = Cache::new();
+
+ cache.fill(MOCK_IP_ADDR_1, HADDR_A, Instant::from_millis(100));
+ cache.fill(MOCK_IP_ADDR_2, HADDR_B, Instant::from_millis(50));
+ cache.fill(MOCK_IP_ADDR_3, HADDR_C, Instant::from_millis(200));
+ assert_eq!(
+ cache.lookup(&MOCK_IP_ADDR_2, Instant::from_millis(1000)),
+ Answer::Found(HADDR_B)
+ );
+ assert!(!cache
+ .lookup(&MOCK_IP_ADDR_4, Instant::from_millis(1000))
+ .found());
+
+ cache.fill(MOCK_IP_ADDR_4, HADDR_D, Instant::from_millis(300));
+ assert!(!cache
+ .lookup(&MOCK_IP_ADDR_2, Instant::from_millis(1000))
+ .found());
+ assert_eq!(
+ cache.lookup(&MOCK_IP_ADDR_4, Instant::from_millis(1000)),
+ Answer::Found(HADDR_D)
+ );
+ }
+
+ #[test]
+ fn test_hush() {
+ let mut cache = Cache::new();
+
+ assert_eq!(
+ cache.lookup(&MOCK_IP_ADDR_1, Instant::from_millis(0)),
+ Answer::NotFound
+ );
+
+ cache.limit_rate(Instant::from_millis(0));
+ assert_eq!(
+ cache.lookup(&MOCK_IP_ADDR_1, Instant::from_millis(100)),
+ Answer::RateLimited
+ );
+ assert_eq!(
+ cache.lookup(&MOCK_IP_ADDR_1, Instant::from_millis(2000)),
+ Answer::NotFound
+ );
+ }
+
+ #[test]
+ fn test_flush() {
+ let mut cache = Cache::new();
+
+ cache.fill(MOCK_IP_ADDR_1, HADDR_A, Instant::from_millis(0));
+ assert_eq!(
+ cache.lookup(&MOCK_IP_ADDR_1, Instant::from_millis(0)),
+ Answer::Found(HADDR_A)
+ );
+ assert!(!cache
+ .lookup(&MOCK_IP_ADDR_2, Instant::from_millis(0))
+ .found());
+
+ cache.flush();
+ assert!(!cache
+ .lookup(&MOCK_IP_ADDR_1, Instant::from_millis(0))
+ .found());
+ assert!(!cache
+ .lookup(&MOCK_IP_ADDR_1, Instant::from_millis(0))
+ .found());
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-25 14:12:13 +0000