veridian_kernel/net/routing/
rip.rs

1//! RIP v2 routing daemon (RFC 2453)
2//!
3//! Distance-vector routing protocol with:
4//! - Split horizon with poisoned reverse
5//! - Triggered updates
6//! - Route timeout and garbage collection
7//! - Multicast group 224.0.0.9, port 520
8
9use alloc::{collections::BTreeMap, vec::Vec};
10
11use crate::net::Ipv4Address;
12
13/// RIP infinity metric (unreachable)
14pub const RIP_INFINITY: u32 = 16;
15
16/// RIP v2 default port
17pub const RIP_PORT: u16 = 520;
18
19/// RIP v2 multicast address (224.0.0.9)
20pub const RIP_MULTICAST: Ipv4Address = Ipv4Address([224, 0, 0, 9]);
21
22/// Maximum entries per RIP message
23pub const RIP_MAX_ENTRIES: usize = 25;
24
25/// Default advertisement interval in ticks
26pub const RIP_UPDATE_INTERVAL: u64 = 30;
27
28/// Route timeout in ticks (no update received)
29pub const RIP_TIMEOUT: u64 = 180;
30
31/// Garbage collection timer in ticks (after timeout)
32pub const RIP_GARBAGE_COLLECT: u64 = 120;
33
34/// RIP command type
35#[derive(Debug, Clone, Copy, PartialEq, Eq)]
36#[repr(u8)]
37pub enum RipCommand {
38    Request = 1,
39    Response = 2,
40}
41
42impl RipCommand {
43    fn from_u8(v: u8) -> Option<Self> {
44        match v {
45            1 => Some(Self::Request),
46            2 => Some(Self::Response),
47            _ => None,
48        }
49    }
50}
51
52/// RIP v2 route entry (wire format)
53#[derive(Debug, Clone, Copy, PartialEq, Eq)]
54pub struct RipEntry {
55    /// Address family identifier (2 = IP)
56    pub address_family: u16,
57    /// Route tag for EGP/IGP distinction
58    pub route_tag: u16,
59    /// Destination IP address
60    pub ip_address: Ipv4Address,
61    /// Subnet mask
62    pub subnet_mask: Ipv4Address,
63    /// Next hop address
64    pub next_hop: Ipv4Address,
65    /// Metric (1-16, 16 = infinity)
66    pub metric: u32,
67}
68
69/// RIP v2 message
70#[derive(Debug, Clone, PartialEq, Eq)]
71pub struct RipMessage {
72    /// Command (Request or Response)
73    pub command: RipCommand,
74    /// Version (always 2)
75    pub version: u8,
76    /// Route entries (up to 25)
77    pub entries: Vec<RipEntry>,
78}
79
80impl RipMessage {
81    /// Create a new RIP request message
82    pub fn new_request() -> Self {
83        Self {
84            command: RipCommand::Request,
85            version: 2,
86            entries: Vec::new(),
87        }
88    }
89
90    /// Create a new RIP response message
91    pub fn new_response() -> Self {
92        Self {
93            command: RipCommand::Response,
94            version: 2,
95            entries: Vec::new(),
96        }
97    }
98}
99
100/// Internal route entry stored in the daemon's table
101#[derive(Debug, Clone, PartialEq, Eq)]
102pub struct RipRoute {
103    /// Destination network address
104    pub destination: Ipv4Address,
105    /// Prefix length (e.g. 24 for /24)
106    pub prefix_len: u8,
107    /// Next hop router
108    pub next_hop: Ipv4Address,
109    /// Metric (hop count, 1-16)
110    pub metric: u32,
111    /// Route tag
112    pub route_tag: u16,
113    /// Tick when this route was last updated
114    pub last_update: u64,
115    /// Whether route is in garbage collection state
116    pub garbage: bool,
117    /// Source router that advertised this route
118    pub source: Ipv4Address,
119}
120
121/// Destination key for route table lookups
122#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
123pub struct DestinationKey {
124    /// Network address as u32
125    pub network: u32,
126    /// Prefix length
127    pub prefix_len: u8,
128}
129
130impl DestinationKey {
131    pub fn new(addr: Ipv4Address, prefix_len: u8) -> Self {
132        let mask = prefix_to_mask(prefix_len);
133        Self {
134            network: addr.to_u32() & mask,
135            prefix_len,
136        }
137    }
138}
139
140/// RIP v2 routing daemon
141pub struct RipDaemon {
142    /// Route table indexed by destination
143    routes: BTreeMap<DestinationKey, RipRoute>,
144    /// Current tick counter
145    current_tick: u64,
146    /// Tick when last periodic update was sent
147    last_update_tick: u64,
148    /// Whether a triggered update is pending
149    triggered_update_pending: bool,
150    /// Local router address
151    _router_address: Ipv4Address,
152}
153
154impl RipDaemon {
155    /// Create a new RIP daemon
156    pub fn new(router_address: Ipv4Address) -> Self {
157        Self {
158            routes: BTreeMap::new(),
159            current_tick: 0,
160            last_update_tick: 0,
161            triggered_update_pending: false,
162            _router_address: router_address,
163        }
164    }
165
166    /// Advance the tick counter and age routes
167    pub fn tick(&mut self, ticks: u64) {
168        self.current_tick += ticks;
169    }
170
171    /// Check if periodic update is due
172    pub fn is_update_due(&self) -> bool {
173        self.current_tick.saturating_sub(self.last_update_tick) >= RIP_UPDATE_INTERVAL
174    }
175
176    /// Check if a triggered update is pending
177    pub fn has_triggered_update(&self) -> bool {
178        self.triggered_update_pending
179    }
180
181    /// Clear triggered update flag and record update time
182    pub fn mark_update_sent(&mut self) {
183        self.triggered_update_pending = false;
184        self.last_update_tick = self.current_tick;
185    }
186
187    /// Add or update a route
188    pub fn add_route(&mut self, route: RipRoute) {
189        let key = DestinationKey::new(route.destination, route.prefix_len);
190        self.routes.insert(key, route);
191    }
192
193    /// Remove a route by destination
194    pub fn remove_route(&mut self, destination: Ipv4Address, prefix_len: u8) -> Option<RipRoute> {
195        let key = DestinationKey::new(destination, prefix_len);
196        self.routes.remove(&key)
197    }
198
199    /// Get a route by destination
200    pub fn get_route(&self, destination: Ipv4Address, prefix_len: u8) -> Option<&RipRoute> {
201        let key = DestinationKey::new(destination, prefix_len);
202        self.routes.get(&key)
203    }
204
205    /// Get total number of routes
206    pub fn route_count(&self) -> usize {
207        self.routes.len()
208    }
209
210    /// Age routes: mark timed-out routes for garbage collection, remove expired
211    /// garbage
212    pub fn age_routes(&mut self) {
213        let current = self.current_tick;
214        let mut to_remove = Vec::new();
215
216        for (key, route) in self.routes.iter_mut() {
217            let age = current.saturating_sub(route.last_update);
218
219            if route.garbage {
220                // In garbage collection: remove after RIP_GARBAGE_COLLECT ticks
221                if age >= RIP_TIMEOUT + RIP_GARBAGE_COLLECT {
222                    to_remove.push(*key);
223                }
224            } else if age >= RIP_TIMEOUT {
225                // Route timed out: set metric to infinity, start garbage collection
226                route.metric = RIP_INFINITY;
227                route.garbage = true;
228            }
229        }
230
231        for key in &to_remove {
232            self.routes.remove(key);
233        }
234
235        if !to_remove.is_empty() {
236            self.triggered_update_pending = true;
237        }
238    }
239
240    /// Process an incoming RIP message from a neighbor
241    pub fn process_message(&mut self, msg: &RipMessage, source: Ipv4Address) {
242        match msg.command {
243            RipCommand::Request => {
244                // Requests are handled by generating a response (caller should
245                // call generate_response)
246            }
247            RipCommand::Response => {
248                for entry in &msg.entries {
249                    self.process_response_entry(entry, source);
250                }
251            }
252        }
253    }
254
255    /// Process a single RIP response entry
256    fn process_response_entry(&mut self, entry: &RipEntry, source: Ipv4Address) {
257        // Validate metric
258        let new_metric = (entry.metric + 1).min(RIP_INFINITY);
259        let prefix_len = mask_to_prefix(entry.subnet_mask.to_u32());
260        let key = DestinationKey::new(entry.ip_address, prefix_len);
261
262        let next_hop = if entry.next_hop == Ipv4Address::ANY {
263            source
264        } else {
265            entry.next_hop
266        };
267
268        if let Some(existing) = self.routes.get(&key) {
269            if existing.source == source {
270                // Same source: always update (even if metric increased)
271                let changed = existing.metric != new_metric;
272                let route = RipRoute {
273                    destination: entry.ip_address,
274                    prefix_len,
275                    next_hop,
276                    metric: new_metric,
277                    route_tag: entry.route_tag,
278                    last_update: self.current_tick,
279                    garbage: new_metric >= RIP_INFINITY,
280                    source,
281                };
282                self.routes.insert(key, route);
283                if changed {
284                    self.triggered_update_pending = true;
285                }
286            } else if new_metric < existing.metric {
287                // Better metric from different source: adopt
288                let route = RipRoute {
289                    destination: entry.ip_address,
290                    prefix_len,
291                    next_hop,
292                    metric: new_metric,
293                    route_tag: entry.route_tag,
294                    last_update: self.current_tick,
295                    garbage: false,
296                    source,
297                };
298                self.routes.insert(key, route);
299                self.triggered_update_pending = true;
300            }
301            // Worse metric from different source: ignore
302        } else if new_metric < RIP_INFINITY {
303            // New route
304            let route = RipRoute {
305                destination: entry.ip_address,
306                prefix_len,
307                next_hop,
308                metric: new_metric,
309                route_tag: entry.route_tag,
310                last_update: self.current_tick,
311                garbage: false,
312                source,
313            };
314            self.routes.insert(key, route);
315            self.triggered_update_pending = true;
316        }
317    }
318
319    /// Generate a RIP response message for a neighbor (split horizon with
320    /// poisoned reverse)
321    pub fn generate_response(&self, neighbor: Ipv4Address) -> Vec<RipMessage> {
322        let mut messages = Vec::new();
323        let mut current_msg = RipMessage::new_response();
324
325        for route in self.routes.values() {
326            // Split horizon with poisoned reverse:
327            // Routes learned from this neighbor are advertised back with infinity metric
328            let metric = if route.source == neighbor {
329                RIP_INFINITY
330            } else {
331                route.metric
332            };
333
334            let entry = RipEntry {
335                address_family: 2,
336                route_tag: route.route_tag,
337                ip_address: route.destination,
338                subnet_mask: Ipv4Address::from_u32(prefix_to_mask(route.prefix_len)),
339                next_hop: Ipv4Address::ANY,
340                metric,
341            };
342
343            current_msg.entries.push(entry);
344
345            if current_msg.entries.len() >= RIP_MAX_ENTRIES {
346                messages.push(current_msg);
347                current_msg = RipMessage::new_response();
348            }
349        }
350
351        if !current_msg.entries.is_empty() {
352            messages.push(current_msg);
353        }
354
355        messages
356    }
357}
358
359/// Serialize a RIP message to wire format bytes
360pub fn serialize_message(msg: &RipMessage) -> Vec<u8> {
361    // Header: command(1) + version(1) + zero(2) = 4 bytes
362    // Each entry: 20 bytes
363    let size = 4 + msg.entries.len() * 20;
364    let mut buf = Vec::with_capacity(size);
365
366    buf.push(msg.command as u8);
367    buf.push(msg.version);
368    buf.push(0); // must be zero
369    buf.push(0);
370
371    for entry in &msg.entries {
372        // Address family (2 bytes, big-endian)
373        buf.extend_from_slice(&entry.address_family.to_be_bytes());
374        // Route tag (2 bytes)
375        buf.extend_from_slice(&entry.route_tag.to_be_bytes());
376        // IP address (4 bytes)
377        buf.extend_from_slice(&entry.ip_address.0);
378        // Subnet mask (4 bytes)
379        buf.extend_from_slice(&entry.subnet_mask.0);
380        // Next hop (4 bytes)
381        buf.extend_from_slice(&entry.next_hop.0);
382        // Metric (4 bytes, big-endian)
383        buf.extend_from_slice(&entry.metric.to_be_bytes());
384    }
385
386    buf
387}
388
389/// Deserialize a RIP message from wire format bytes
390pub fn deserialize_message(data: &[u8]) -> Option<RipMessage> {
391    if data.len() < 4 {
392        return None;
393    }
394
395    let command = RipCommand::from_u8(data[0])?;
396    let version = data[1];
397
398    if version != 2 {
399        return None;
400    }
401
402    let entry_data = &data[4..];
403    if !entry_data.len().is_multiple_of(20) {
404        return None;
405    }
406
407    let num_entries = entry_data.len() / 20;
408    if num_entries > RIP_MAX_ENTRIES {
409        return None;
410    }
411
412    let mut entries = Vec::with_capacity(num_entries);
413    for i in 0..num_entries {
414        let offset = i * 20;
415        let e = &entry_data[offset..offset + 20];
416
417        let address_family = u16::from_be_bytes([e[0], e[1]]);
418        let route_tag = u16::from_be_bytes([e[2], e[3]]);
419        let ip_address = Ipv4Address([e[4], e[5], e[6], e[7]]);
420        let subnet_mask = Ipv4Address([e[8], e[9], e[10], e[11]]);
421        let next_hop = Ipv4Address([e[12], e[13], e[14], e[15]]);
422        let metric = u32::from_be_bytes([e[16], e[17], e[18], e[19]]);
423
424        if metric > RIP_INFINITY {
425            return None;
426        }
427
428        entries.push(RipEntry {
429            address_family,
430            route_tag,
431            ip_address,
432            subnet_mask,
433            next_hop,
434            metric,
435        });
436    }
437
438    Some(RipMessage {
439        command,
440        version,
441        entries,
442    })
443}
444
445/// Convert prefix length to 32-bit subnet mask
446fn prefix_to_mask(prefix_len: u8) -> u32 {
447    if prefix_len == 0 {
448        0
449    } else if prefix_len >= 32 {
450        0xFFFF_FFFF
451    } else {
452        !((1u32 << (32 - prefix_len)) - 1)
453    }
454}
455
456/// Convert 32-bit subnet mask to prefix length
457fn mask_to_prefix(mask: u32) -> u8 {
458    mask.leading_ones() as u8
459}
460
461#[cfg(test)]
462mod tests {
463    use super::*;
464
465    #[test]
466    fn test_prefix_to_mask() {
467        assert_eq!(prefix_to_mask(0), 0x0000_0000);
468        assert_eq!(prefix_to_mask(8), 0xFF00_0000);
469        assert_eq!(prefix_to_mask(16), 0xFFFF_0000);
470        assert_eq!(prefix_to_mask(24), 0xFFFF_FF00);
471        assert_eq!(prefix_to_mask(32), 0xFFFF_FFFF);
472    }
473
474    #[test]
475    fn test_mask_to_prefix() {
476        assert_eq!(mask_to_prefix(0x0000_0000), 0);
477        assert_eq!(mask_to_prefix(0xFF00_0000), 8);
478        assert_eq!(mask_to_prefix(0xFFFF_FF00), 24);
479        assert_eq!(mask_to_prefix(0xFFFF_FFFF), 32);
480    }
481
482    #[test]
483    fn test_rip_message_serialize_deserialize() {
484        let msg = RipMessage {
485            command: RipCommand::Response,
486            version: 2,
487            entries: alloc::vec![RipEntry {
488                address_family: 2,
489                route_tag: 0,
490                ip_address: Ipv4Address::new(10, 0, 0, 0),
491                subnet_mask: Ipv4Address::from_u32(prefix_to_mask(8)),
492                next_hop: Ipv4Address::ANY,
493                metric: 1,
494            }],
495        };
496
497        let bytes = serialize_message(&msg);
498        assert_eq!(bytes.len(), 24); // 4 header + 20 entry
499
500        let decoded = deserialize_message(&bytes).unwrap();
501        assert_eq!(decoded.command, RipCommand::Response);
502        assert_eq!(decoded.version, 2);
503        assert_eq!(decoded.entries.len(), 1);
504        assert_eq!(decoded.entries[0].metric, 1);
505        assert_eq!(decoded.entries[0].ip_address, Ipv4Address::new(10, 0, 0, 0));
506    }
507
508    #[test]
509    fn test_deserialize_invalid() {
510        // Too short
511        assert!(deserialize_message(&[1, 2]).is_none());
512        // Wrong version
513        assert!(deserialize_message(&[1, 1, 0, 0]).is_none());
514        // Invalid entry length (not multiple of 20)
515        assert!(deserialize_message(&[2, 2, 0, 0, 0, 0, 0]).is_none());
516    }
517
518    #[test]
519    fn test_rip_daemon_add_remove() {
520        let mut daemon = RipDaemon::new(Ipv4Address::new(192, 168, 1, 1));
521        let route = RipRoute {
522            destination: Ipv4Address::new(10, 0, 0, 0),
523            prefix_len: 8,
524            next_hop: Ipv4Address::new(192, 168, 1, 254),
525            metric: 1,
526            route_tag: 0,
527            last_update: 0,
528            garbage: false,
529            source: Ipv4Address::new(192, 168, 1, 254),
530        };
531
532        daemon.add_route(route);
533        assert_eq!(daemon.route_count(), 1);
534        assert!(daemon.get_route(Ipv4Address::new(10, 0, 0, 0), 8).is_some());
535
536        daemon.remove_route(Ipv4Address::new(10, 0, 0, 0), 8);
537        assert_eq!(daemon.route_count(), 0);
538    }
539
540    #[test]
541    fn test_split_horizon_poisoned_reverse() {
542        let mut daemon = RipDaemon::new(Ipv4Address::new(192, 168, 1, 1));
543        let neighbor = Ipv4Address::new(192, 168, 1, 2);
544
545        daemon.add_route(RipRoute {
546            destination: Ipv4Address::new(10, 0, 0, 0),
547            prefix_len: 8,
548            next_hop: neighbor,
549            metric: 2,
550            route_tag: 0,
551            last_update: 0,
552            garbage: false,
553            source: neighbor,
554        });
555
556        // Response to the same neighbor should poison the route
557        let responses = daemon.generate_response(neighbor);
558        assert_eq!(responses.len(), 1);
559        assert_eq!(responses[0].entries[0].metric, RIP_INFINITY);
560
561        // Response to a different neighbor should show real metric
562        let other = Ipv4Address::new(192, 168, 1, 3);
563        let responses = daemon.generate_response(other);
564        assert_eq!(responses[0].entries[0].metric, 2);
565    }
566
567    #[test]
568    fn test_process_response_new_route() {
569        let mut daemon = RipDaemon::new(Ipv4Address::new(192, 168, 1, 1));
570        let source = Ipv4Address::new(192, 168, 1, 2);
571
572        let msg = RipMessage {
573            command: RipCommand::Response,
574            version: 2,
575            entries: alloc::vec![RipEntry {
576                address_family: 2,
577                route_tag: 0,
578                ip_address: Ipv4Address::new(10, 0, 0, 0),
579                subnet_mask: Ipv4Address::from_u32(prefix_to_mask(8)),
580                next_hop: Ipv4Address::ANY,
581                metric: 1,
582            }],
583        };
584
585        daemon.process_message(&msg, source);
586        assert_eq!(daemon.route_count(), 1);
587
588        let route = daemon.get_route(Ipv4Address::new(10, 0, 0, 0), 8).unwrap();
589        assert_eq!(route.metric, 2); // original 1 + 1 hop
590        assert_eq!(route.next_hop, source); // next_hop was ANY, so use source
591    }
592
593    #[test]
594    fn test_process_response_better_metric() {
595        let mut daemon = RipDaemon::new(Ipv4Address::new(192, 168, 1, 1));
596        let source1 = Ipv4Address::new(192, 168, 1, 2);
597        let source2 = Ipv4Address::new(192, 168, 1, 3);
598
599        // First route with metric 5
600        daemon.add_route(RipRoute {
601            destination: Ipv4Address::new(10, 0, 0, 0),
602            prefix_len: 8,
603            next_hop: source1,
604            metric: 5,
605            route_tag: 0,
606            last_update: 0,
607            garbage: false,
608            source: source1,
609        });
610
611        // Better route with metric 1 from different source
612        let msg = RipMessage {
613            command: RipCommand::Response,
614            version: 2,
615            entries: alloc::vec![RipEntry {
616                address_family: 2,
617                route_tag: 0,
618                ip_address: Ipv4Address::new(10, 0, 0, 0),
619                subnet_mask: Ipv4Address::from_u32(prefix_to_mask(8)),
620                next_hop: Ipv4Address::ANY,
621                metric: 1,
622            }],
623        };
624
625        daemon.process_message(&msg, source2);
626        let route = daemon.get_route(Ipv4Address::new(10, 0, 0, 0), 8).unwrap();
627        assert_eq!(route.metric, 2); // adopted better metric
628        assert_eq!(route.source, source2);
629    }
630
631    #[test]
632    fn test_route_timeout_and_garbage() {
633        let mut daemon = RipDaemon::new(Ipv4Address::new(192, 168, 1, 1));
634
635        daemon.add_route(RipRoute {
636            destination: Ipv4Address::new(10, 0, 0, 0),
637            prefix_len: 8,
638            next_hop: Ipv4Address::new(192, 168, 1, 2),
639            metric: 1,
640            route_tag: 0,
641            last_update: 0,
642            garbage: false,
643            source: Ipv4Address::new(192, 168, 1, 2),
644        });
645
646        // Before timeout
647        daemon.tick(179);
648        daemon.age_routes();
649        let route = daemon.get_route(Ipv4Address::new(10, 0, 0, 0), 8).unwrap();
650        assert_eq!(route.metric, 1);
651        assert!(!route.garbage);
652
653        // After timeout
654        daemon.tick(1);
655        daemon.age_routes();
656        let route = daemon.get_route(Ipv4Address::new(10, 0, 0, 0), 8).unwrap();
657        assert_eq!(route.metric, RIP_INFINITY);
658        assert!(route.garbage);
659
660        // After garbage collection
661        daemon.tick(RIP_GARBAGE_COLLECT);
662        daemon.age_routes();
663        assert_eq!(daemon.route_count(), 0);
664    }
665
666    #[test]
667    fn test_update_timer() {
668        let daemon = RipDaemon::new(Ipv4Address::new(192, 168, 1, 1));
669        assert!(!daemon.is_update_due());
670    }
671
672    #[test]
673    fn test_update_timer_due() {
674        let mut daemon = RipDaemon::new(Ipv4Address::new(192, 168, 1, 1));
675        daemon.tick(30);
676        assert!(daemon.is_update_due());
677
678        daemon.mark_update_sent();
679        assert!(!daemon.is_update_due());
680        assert!(!daemon.has_triggered_update());
681    }
682
683    #[test]
684    fn test_message_splitting() {
685        let mut daemon = RipDaemon::new(Ipv4Address::new(192, 168, 1, 1));
686
687        // Add 30 routes (should split into 2 messages: 25 + 5)
688        for i in 0..30u8 {
689            daemon.add_route(RipRoute {
690                destination: Ipv4Address::new(10, i, 0, 0),
691                prefix_len: 16,
692                next_hop: Ipv4Address::new(192, 168, 1, 2),
693                metric: 1,
694                route_tag: 0,
695                last_update: 0,
696                garbage: false,
697                source: Ipv4Address::new(192, 168, 1, 3),
698            });
699        }
700
701        let responses = daemon.generate_response(Ipv4Address::new(192, 168, 1, 4));
702        assert_eq!(responses.len(), 2);
703        assert_eq!(responses[0].entries.len(), 25);
704        assert_eq!(responses[1].entries.len(), 5);
705    }
706}
veridian_kernel/net/routing/rip.rs

veridian_kernel/net/routing/
rip.rs
