smoltcp/iface/
neighbor.rs

Help
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 fill(
67        &mut self,
68        protocol_addr: IpAddress,
69        hardware_addr: HardwareAddress,
70        timestamp: Instant,
71    ) {
72        debug_assert!(protocol_addr.is_unicast());
73        debug_assert!(hardware_addr.is_unicast());
74
75        let expires_at = timestamp + Self::ENTRY_LIFETIME;
76        self.fill_with_expiration(protocol_addr, hardware_addr, expires_at);
77    }
78
79    pub fn fill_with_expiration(
80        &mut self,
81        protocol_addr: IpAddress,
82        hardware_addr: HardwareAddress,
83        expires_at: Instant,
84    ) {
85        debug_assert!(protocol_addr.is_unicast());
86        debug_assert!(hardware_addr.is_unicast());
87
88        let neighbor = Neighbor {
89            expires_at,
90            hardware_addr,
91        };
92        match self.storage.insert(protocol_addr, neighbor) {
93            Ok(Some(old_neighbor)) => {
94                if old_neighbor.hardware_addr != hardware_addr {
95                    net_trace!(
96                        "replaced {} => {} (was {})",
97                        protocol_addr,
98                        hardware_addr,
99                        old_neighbor.hardware_addr
100                    );
101                }
102            }
103            Ok(None) => {
104                net_trace!("filled {} => {} (was empty)", protocol_addr, hardware_addr);
105            }
106            Err((protocol_addr, neighbor)) => {
107                // If we're going down this branch, it means the cache is full, and we need to evict an entry.
108                let old_protocol_addr = *self
109                    .storage
110                    .iter()
111                    .min_by_key(|(_, neighbor)| neighbor.expires_at)
112                    .expect("empty neighbor cache storage")
113                    .0;
114
115                let _old_neighbor = self.storage.remove(&old_protocol_addr).unwrap();
116                match self.storage.insert(protocol_addr, neighbor) {
117                    Ok(None) => {
118                        net_trace!(
119                            "filled {} => {} (evicted {} => {})",
120                            protocol_addr,
121                            hardware_addr,
122                            old_protocol_addr,
123                            _old_neighbor.hardware_addr
124                        );
125                    }
126                    // We've covered everything else above.
127                    _ => unreachable!(),
128                }
129            }
130        }
131    }
132
133    pub(crate) fn lookup(&self, protocol_addr: &IpAddress, timestamp: Instant) -> Answer {
134        assert!(protocol_addr.is_unicast());
135
136        if let Some(&Neighbor {
137            expires_at,
138            hardware_addr,
139        }) = self.storage.get(protocol_addr)
140        {
141            if timestamp < expires_at {
142                return Answer::Found(hardware_addr);
143            }
144        }
145
146        if timestamp < self.silent_until {
147            Answer::RateLimited
148        } else {
149            Answer::NotFound
150        }
151    }
152
153    pub(crate) fn limit_rate(&mut self, timestamp: Instant) {
154        self.silent_until = timestamp + Self::SILENT_TIME;
155    }
156
157    pub(crate) fn flush(&mut self) {
158        self.storage.clear()
159    }
160}
161
162#[cfg(feature = "medium-ethernet")]
163#[cfg(test)]
164mod test {
165    use super::*;
166    use crate::wire::ip::test::{MOCK_IP_ADDR_1, MOCK_IP_ADDR_2, MOCK_IP_ADDR_3, MOCK_IP_ADDR_4};
167
168    use crate::wire::EthernetAddress;
169
170    const HADDR_A: HardwareAddress = HardwareAddress::Ethernet(EthernetAddress([0, 0, 0, 0, 0, 1]));
171    const HADDR_B: HardwareAddress = HardwareAddress::Ethernet(EthernetAddress([0, 0, 0, 0, 0, 2]));
172    const HADDR_C: HardwareAddress = HardwareAddress::Ethernet(EthernetAddress([0, 0, 0, 0, 0, 3]));
173    const HADDR_D: HardwareAddress = HardwareAddress::Ethernet(EthernetAddress([0, 0, 0, 0, 0, 4]));
174
175    #[test]
176    fn test_fill() {
177        let mut cache = Cache::new();
178
179        assert!(!cache
180            .lookup(&MOCK_IP_ADDR_1, Instant::from_millis(0))
181            .found());
182        assert!(!cache
183            .lookup(&MOCK_IP_ADDR_2, Instant::from_millis(0))
184            .found());
185
186        cache.fill(MOCK_IP_ADDR_1, HADDR_A, Instant::from_millis(0));
187        assert_eq!(
188            cache.lookup(&MOCK_IP_ADDR_1, Instant::from_millis(0)),
189            Answer::Found(HADDR_A)
190        );
191        assert!(!cache
192            .lookup(&MOCK_IP_ADDR_2, Instant::from_millis(0))
193            .found());
194        assert!(!cache
195            .lookup(
196                &MOCK_IP_ADDR_1,
197                Instant::from_millis(0) + Cache::ENTRY_LIFETIME * 2
198            )
199            .found(),);
200
201        cache.fill(MOCK_IP_ADDR_1, HADDR_A, Instant::from_millis(0));
202        assert!(!cache
203            .lookup(&MOCK_IP_ADDR_2, Instant::from_millis(0))
204            .found());
205    }
206
207    #[test]
208    fn test_expire() {
209        let mut cache = Cache::new();
210
211        cache.fill(MOCK_IP_ADDR_1, HADDR_A, Instant::from_millis(0));
212        assert_eq!(
213            cache.lookup(&MOCK_IP_ADDR_1, Instant::from_millis(0)),
214            Answer::Found(HADDR_A)
215        );
216        assert!(!cache
217            .lookup(
218                &MOCK_IP_ADDR_1,
219                Instant::from_millis(0) + Cache::ENTRY_LIFETIME * 2
220            )
221            .found(),);
222    }
223
224    #[test]
225    fn test_replace() {
226        let mut cache = Cache::new();
227
228        cache.fill(MOCK_IP_ADDR_1, HADDR_A, Instant::from_millis(0));
229        assert_eq!(
230            cache.lookup(&MOCK_IP_ADDR_1, Instant::from_millis(0)),
231            Answer::Found(HADDR_A)
232        );
233        cache.fill(MOCK_IP_ADDR_1, HADDR_B, Instant::from_millis(0));
234        assert_eq!(
235            cache.lookup(&MOCK_IP_ADDR_1, Instant::from_millis(0)),
236            Answer::Found(HADDR_B)
237        );
238    }
239
240    #[test]
241    fn test_evict() {
242        let mut cache = Cache::new();
243
244        cache.fill(MOCK_IP_ADDR_1, HADDR_A, Instant::from_millis(100));
245        cache.fill(MOCK_IP_ADDR_2, HADDR_B, Instant::from_millis(50));
246        cache.fill(MOCK_IP_ADDR_3, HADDR_C, Instant::from_millis(200));
247        assert_eq!(
248            cache.lookup(&MOCK_IP_ADDR_2, Instant::from_millis(1000)),
249            Answer::Found(HADDR_B)
250        );
251        assert!(!cache
252            .lookup(&MOCK_IP_ADDR_4, Instant::from_millis(1000))
253            .found());
254
255        cache.fill(MOCK_IP_ADDR_4, HADDR_D, Instant::from_millis(300));
256        assert!(!cache
257            .lookup(&MOCK_IP_ADDR_2, Instant::from_millis(1000))
258            .found());
259        assert_eq!(
260            cache.lookup(&MOCK_IP_ADDR_4, Instant::from_millis(1000)),
261            Answer::Found(HADDR_D)
262        );
263    }
264
265    #[test]
266    fn test_hush() {
267        let mut cache = Cache::new();
268
269        assert_eq!(
270            cache.lookup(&MOCK_IP_ADDR_1, Instant::from_millis(0)),
271            Answer::NotFound
272        );
273
274        cache.limit_rate(Instant::from_millis(0));
275        assert_eq!(
276            cache.lookup(&MOCK_IP_ADDR_1, Instant::from_millis(100)),
277            Answer::RateLimited
278        );
279        assert_eq!(
280            cache.lookup(&MOCK_IP_ADDR_1, Instant::from_millis(2000)),
281            Answer::NotFound
282        );
283    }
284
285    #[test]
286    fn test_flush() {
287        let mut cache = Cache::new();
288
289        cache.fill(MOCK_IP_ADDR_1, HADDR_A, Instant::from_millis(0));
290        assert_eq!(
291            cache.lookup(&MOCK_IP_ADDR_1, Instant::from_millis(0)),
292            Answer::Found(HADDR_A)
293        );
294        assert!(!cache
295            .lookup(&MOCK_IP_ADDR_2, Instant::from_millis(0))
296            .found());
297
298        cache.flush();
299        assert!(!cache
300            .lookup(&MOCK_IP_ADDR_1, Instant::from_millis(0))
301            .found());
302        assert!(!cache
303            .lookup(&MOCK_IP_ADDR_1, Instant::from_millis(0))
304            .found());
305    }
306}
smoltcp/iface/neighbor.rs

smoltcp/iface/
neighbor.rs
