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