smoltcp/iface/
neighbor.rs

1// Heads up! Before working on this file you should read, at least,
2// the parts of RFC 1122 that discuss ARP.
3
4use heapless::LinearMap;
5
6use crate::config::IFACE_NEIGHBOR_CACHE_COUNT;
7use crate::time::{Duration, Instant};
8use crate::wire::{HardwareAddress, IpAddress};
9
10/// A cached neighbor.
11///
12/// A neighbor mapping translates from a protocol address to a hardware address,
13/// and contains the timestamp past which the mapping should be discarded.
14#[derive(Debug, Clone, Copy)]
15#[cfg_attr(feature = "defmt", derive(defmt::Format))]
16pub struct Neighbor {
17    hardware_addr: HardwareAddress,
18    expires_at: Instant,
19}
20
21/// An answer to a neighbor cache lookup.
22#[derive(Debug, Clone, Copy, PartialEq, Eq)]
23#[cfg_attr(feature = "defmt", derive(defmt::Format))]
24pub(crate) enum Answer {
25    /// The neighbor address is in the cache and not expired.
26    Found(HardwareAddress),
27    /// The neighbor address is not in the cache, or has expired.
28    NotFound,
29    /// The neighbor address is not in the cache, or has expired,
30    /// and a lookup has been made recently.
31    RateLimited,
32}
33
34impl Answer {
35    /// Returns whether a valid address was found.
36    pub(crate) fn found(&self) -> bool {
37        match self {
38            Answer::Found(_) => true,
39            _ => false,
40        }
41    }
42}
43
44/// A neighbor cache backed by a map.
45#[derive(Debug)]
46pub struct Cache {
47    storage: LinearMap<IpAddress, Neighbor, IFACE_NEIGHBOR_CACHE_COUNT>,
48    silent_until: Instant,
49}
50
51impl Cache {
52    /// Minimum delay between discovery requests, in milliseconds.
53    pub(crate) const SILENT_TIME: Duration = Duration::from_millis(1_000);
54
55    /// Neighbor entry lifetime, in milliseconds.
56    pub(crate) const ENTRY_LIFETIME: Duration = Duration::from_millis(60_000);
57
58    /// Create a cache.
59    pub fn new() -> Self {
60        Self {
61            storage: LinearMap::new(),
62            silent_until: Instant::from_millis(0),
63        }
64    }
65
66    pub fn reset_expiry_if_existing(
67        &mut self,
68        protocol_addr: IpAddress,
69        source_hardware_addr: HardwareAddress,
70        timestamp: Instant,
71    ) {
72        if let Some(Neighbor {
73            expires_at,
74            hardware_addr,
75        }) = self.storage.get_mut(&protocol_addr)
76        {
77            if source_hardware_addr == *hardware_addr {
78                *expires_at = timestamp + Self::ENTRY_LIFETIME;
79            }
80        }
81    }
82
83    pub fn fill(
84        &mut self,
85        protocol_addr: IpAddress,
86        hardware_addr: HardwareAddress,
87        timestamp: Instant,
88    ) {
89        debug_assert!(protocol_addr.is_unicast());
90        debug_assert!(hardware_addr.is_unicast());
91
92        let expires_at = timestamp + Self::ENTRY_LIFETIME;
93        self.fill_with_expiration(protocol_addr, hardware_addr, expires_at);
94    }
95
96    pub fn fill_with_expiration(
97        &mut self,
98        protocol_addr: IpAddress,
99        hardware_addr: HardwareAddress,
100        expires_at: Instant,
101    ) {
102        debug_assert!(protocol_addr.is_unicast());
103        debug_assert!(hardware_addr.is_unicast());
104
105        let neighbor = Neighbor {
106            expires_at,
107            hardware_addr,
108        };
109        match self.storage.insert(protocol_addr, neighbor) {
110            Ok(Some(old_neighbor)) => {
111                if old_neighbor.hardware_addr != hardware_addr {
112                    net_trace!(
113                        "replaced {} => {} (was {})",
114                        protocol_addr,
115                        hardware_addr,
116                        old_neighbor.hardware_addr
117                    );
118                }
119            }
120            Ok(None) => {
121                net_trace!("filled {} => {} (was empty)", protocol_addr, hardware_addr);
122            }
123            Err((protocol_addr, neighbor)) => {
124                // If we're going down this branch, it means the cache is full, and we need to evict an entry.
125                let old_protocol_addr = *self
126                    .storage
127                    .iter()
128                    .min_by_key(|(_, neighbor)| neighbor.expires_at)
129                    .expect("empty neighbor cache storage")
130                    .0;
131
132                let _old_neighbor = self.storage.remove(&old_protocol_addr).unwrap();
133                match self.storage.insert(protocol_addr, neighbor) {
134                    Ok(None) => {
135                        net_trace!(
136                            "filled {} => {} (evicted {} => {})",
137                            protocol_addr,
138                            hardware_addr,
139                            old_protocol_addr,
140                            _old_neighbor.hardware_addr
141                        );
142                    }
143                    // We've covered everything else above.
144                    _ => unreachable!(),
145                }
146            }
147        }
148    }
149
150    pub(crate) fn lookup(&self, protocol_addr: &IpAddress, timestamp: Instant) -> Answer {
151        assert!(protocol_addr.is_unicast());
152
153        if let Some(&Neighbor {
154            expires_at,
155            hardware_addr,
156        }) = self.storage.get(protocol_addr)
157        {
158            if timestamp < expires_at {
159                return Answer::Found(hardware_addr);
160            }
161        }
162
163        if timestamp < self.silent_until {
164            Answer::RateLimited
165        } else {
166            Answer::NotFound
167        }
168    }
169
170    pub(crate) fn limit_rate(&mut self, timestamp: Instant) {
171        self.silent_until = timestamp + Self::SILENT_TIME;
172    }
173
174    pub(crate) fn flush(&mut self) {
175        self.storage.clear()
176    }
177}
178
179#[cfg(feature = "medium-ethernet")]
180#[cfg(test)]
181mod test {
182    use super::*;
183    #[cfg(all(feature = "proto-ipv4", not(feature = "proto-ipv6")))]
184    use crate::wire::ipv4::test::{MOCK_IP_ADDR_1, MOCK_IP_ADDR_2, MOCK_IP_ADDR_3, MOCK_IP_ADDR_4};
185    #[cfg(feature = "proto-ipv6")]
186    use crate::wire::ipv6::test::{MOCK_IP_ADDR_1, MOCK_IP_ADDR_2, MOCK_IP_ADDR_3, MOCK_IP_ADDR_4};
187
188    use crate::wire::EthernetAddress;
189
190    const HADDR_A: HardwareAddress = HardwareAddress::Ethernet(EthernetAddress([0, 0, 0, 0, 0, 1]));
191    const HADDR_B: HardwareAddress = HardwareAddress::Ethernet(EthernetAddress([0, 0, 0, 0, 0, 2]));
192    const HADDR_C: HardwareAddress = HardwareAddress::Ethernet(EthernetAddress([0, 0, 0, 0, 0, 3]));
193    const HADDR_D: HardwareAddress = HardwareAddress::Ethernet(EthernetAddress([0, 0, 0, 0, 0, 4]));
194
195    #[test]
196    fn test_fill() {
197        let mut cache = Cache::new();
198
199        assert!(!cache
200            .lookup(&MOCK_IP_ADDR_1.into(), Instant::from_millis(0))
201            .found());
202        assert!(!cache
203            .lookup(&MOCK_IP_ADDR_2.into(), Instant::from_millis(0))
204            .found());
205
206        cache.fill(MOCK_IP_ADDR_1.into(), HADDR_A, Instant::from_millis(0));
207        assert_eq!(
208            cache.lookup(&MOCK_IP_ADDR_1.into(), Instant::from_millis(0)),
209            Answer::Found(HADDR_A)
210        );
211        assert!(!cache
212            .lookup(&MOCK_IP_ADDR_2.into(), Instant::from_millis(0))
213            .found());
214        assert!(!cache
215            .lookup(
216                &MOCK_IP_ADDR_1.into(),
217                Instant::from_millis(0) + Cache::ENTRY_LIFETIME * 2
218            )
219            .found(),);
220
221        cache.fill(MOCK_IP_ADDR_1.into(), HADDR_A, Instant::from_millis(0));
222        assert!(!cache
223            .lookup(&MOCK_IP_ADDR_2.into(), Instant::from_millis(0))
224            .found());
225    }
226
227    #[test]
228    fn test_expire() {
229        let mut cache = Cache::new();
230
231        cache.fill(MOCK_IP_ADDR_1.into(), HADDR_A, Instant::from_millis(0));
232        assert_eq!(
233            cache.lookup(&MOCK_IP_ADDR_1.into(), Instant::from_millis(0)),
234            Answer::Found(HADDR_A)
235        );
236        assert!(!cache
237            .lookup(
238                &MOCK_IP_ADDR_1.into(),
239                Instant::from_millis(0) + Cache::ENTRY_LIFETIME * 2
240            )
241            .found(),);
242    }
243
244    #[test]
245    fn test_replace() {
246        let mut cache = Cache::new();
247
248        cache.fill(MOCK_IP_ADDR_1.into(), HADDR_A, Instant::from_millis(0));
249        assert_eq!(
250            cache.lookup(&MOCK_IP_ADDR_1.into(), Instant::from_millis(0)),
251            Answer::Found(HADDR_A)
252        );
253        cache.fill(MOCK_IP_ADDR_1.into(), HADDR_B, Instant::from_millis(0));
254        assert_eq!(
255            cache.lookup(&MOCK_IP_ADDR_1.into(), Instant::from_millis(0)),
256            Answer::Found(HADDR_B)
257        );
258    }
259
260    #[test]
261    fn test_evict() {
262        let mut cache = Cache::new();
263
264        cache.fill(MOCK_IP_ADDR_1.into(), HADDR_A, Instant::from_millis(100));
265        cache.fill(MOCK_IP_ADDR_2.into(), HADDR_B, Instant::from_millis(50));
266        cache.fill(MOCK_IP_ADDR_3.into(), HADDR_C, Instant::from_millis(200));
267        assert_eq!(
268            cache.lookup(&MOCK_IP_ADDR_2.into(), Instant::from_millis(1000)),
269            Answer::Found(HADDR_B)
270        );
271        assert!(!cache
272            .lookup(&MOCK_IP_ADDR_4.into(), Instant::from_millis(1000))
273            .found());
274
275        cache.fill(MOCK_IP_ADDR_4.into(), HADDR_D, Instant::from_millis(300));
276        assert!(!cache
277            .lookup(&MOCK_IP_ADDR_2.into(), Instant::from_millis(1000))
278            .found());
279        assert_eq!(
280            cache.lookup(&MOCK_IP_ADDR_4.into(), Instant::from_millis(1000)),
281            Answer::Found(HADDR_D)
282        );
283    }
284
285    #[test]
286    fn test_hush() {
287        let mut cache = Cache::new();
288
289        assert_eq!(
290            cache.lookup(&MOCK_IP_ADDR_1.into(), Instant::from_millis(0)),
291            Answer::NotFound
292        );
293
294        cache.limit_rate(Instant::from_millis(0));
295        assert_eq!(
296            cache.lookup(&MOCK_IP_ADDR_1.into(), Instant::from_millis(100)),
297            Answer::RateLimited
298        );
299        assert_eq!(
300            cache.lookup(&MOCK_IP_ADDR_1.into(), Instant::from_millis(2000)),
301            Answer::NotFound
302        );
303    }
304
305    #[test]
306    fn test_flush() {
307        let mut cache = Cache::new();
308
309        cache.fill(MOCK_IP_ADDR_1.into(), HADDR_A, Instant::from_millis(0));
310        assert_eq!(
311            cache.lookup(&MOCK_IP_ADDR_1.into(), Instant::from_millis(0)),
312            Answer::Found(HADDR_A)
313        );
314        assert!(!cache
315            .lookup(&MOCK_IP_ADDR_2.into(), Instant::from_millis(0))
316            .found());
317
318        cache.flush();
319        assert!(!cache
320            .lookup(&MOCK_IP_ADDR_1.into(), Instant::from_millis(0))
321            .found());
322        assert!(!cache
323            .lookup(&MOCK_IP_ADDR_1.into(), Instant::from_millis(0))
324            .found());
325    }
326}
smoltcp/iface/neighbor.rs

smoltcp/iface/
neighbor.rs
