netstack3_ip/device/
route_discovery.rs

Help
1// Copyright 2022 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5//! IPv6 Route Discovery as defined by [RFC 4861 section 6.3.4].
6//!
7//! [RFC 4861 section 6.3.4]: https://datatracker.ietf.org/doc/html/rfc4861#section-6.3.4
8
9use core::hash::Hash;
10
11use fakealloc::collections::HashSet;
12use net_types::ip::{Ipv6Addr, Subnet};
13use net_types::LinkLocalUnicastAddr;
14use netstack3_base::{
15    AnyDevice, CoreTimerContext, DeviceIdContext, HandleableTimer, InstantBindingsTypes,
16    LocalTimerHeap, TimerBindingsTypes, TimerContext, WeakDeviceIdentifier,
17};
18use packet_formats::icmp::ndp::NonZeroNdpLifetime;
19
20/// Route discovery state on a device.
21#[derive(Debug)]
22pub struct Ipv6RouteDiscoveryState<BT: Ipv6RouteDiscoveryBindingsTypes> {
23    // The valid (non-zero lifetime) discovered routes.
24    //
25    // Routes with a finite lifetime must have a timer set; routes with an
26    // infinite lifetime must not.
27    routes: HashSet<Ipv6DiscoveredRoute>,
28    timers: LocalTimerHeap<Ipv6DiscoveredRoute, (), BT>,
29}
30
31impl<BT: Ipv6RouteDiscoveryBindingsTypes> Ipv6RouteDiscoveryState<BT> {
32    /// Gets the timer heap for route discovery.
33    #[cfg(any(test, feature = "testutils"))]
34    pub fn timers(&self) -> &LocalTimerHeap<Ipv6DiscoveredRoute, (), BT> {
35        &self.timers
36    }
37}
38
39impl<BC: Ipv6RouteDiscoveryBindingsContext> Ipv6RouteDiscoveryState<BC> {
40    /// Constructs the route discovery state for `device_id`.
41    pub fn new<D: WeakDeviceIdentifier, CC: CoreTimerContext<Ipv6DiscoveredRouteTimerId<D>, BC>>(
42        bindings_ctx: &mut BC,
43        device_id: D,
44    ) -> Self {
45        Self {
46            routes: Default::default(),
47            timers: LocalTimerHeap::new_with_context::<_, CC>(
48                bindings_ctx,
49                Ipv6DiscoveredRouteTimerId { device_id },
50            ),
51        }
52    }
53}
54
55/// A discovered route.
56#[derive(Copy, Clone, Eq, PartialEq, Debug, Hash)]
57pub struct Ipv6DiscoveredRoute {
58    /// The destination subnet for the route.
59    pub subnet: Subnet<Ipv6Addr>,
60
61    /// The next-hop node for the route, if required.
62    ///
63    /// `None` indicates that the subnet is on-link/directly-connected.
64    pub gateway: Option<LinkLocalUnicastAddr<Ipv6Addr>>,
65}
66
67/// A timer ID for IPv6 route discovery.
68#[derive(Copy, Clone, Eq, PartialEq, Debug, Hash)]
69pub struct Ipv6DiscoveredRouteTimerId<D: WeakDeviceIdentifier> {
70    device_id: D,
71}
72
73impl<D: WeakDeviceIdentifier> Ipv6DiscoveredRouteTimerId<D> {
74    pub(super) fn device_id(&self) -> &D {
75        &self.device_id
76    }
77}
78
79/// An implementation of the execution context available when accessing the IPv6
80/// route discovery state.
81///
82/// See [`Ipv6RouteDiscoveryContext::with_discovered_routes_mut`].
83pub trait Ipv6DiscoveredRoutesContext<BC>: DeviceIdContext<AnyDevice> {
84    /// Adds a newly discovered IPv6 route to the routing table.
85    fn add_discovered_ipv6_route(
86        &mut self,
87        bindings_ctx: &mut BC,
88        device_id: &Self::DeviceId,
89        route: Ipv6DiscoveredRoute,
90    );
91
92    /// Deletes a previously discovered (now invalidated) IPv6 route from the
93    /// routing table.
94    fn del_discovered_ipv6_route(
95        &mut self,
96        bindings_ctx: &mut BC,
97        device_id: &Self::DeviceId,
98        route: Ipv6DiscoveredRoute,
99    );
100}
101
102/// The execution context for IPv6 route discovery.
103pub trait Ipv6RouteDiscoveryContext<BT: Ipv6RouteDiscoveryBindingsTypes>:
104    DeviceIdContext<AnyDevice>
105{
106    /// The inner discovered routes context.
107    type WithDiscoveredRoutesMutCtx<'a>: Ipv6DiscoveredRoutesContext<BT, DeviceId = Self::DeviceId>;
108
109    /// Gets the route discovery state, mutably.
110    fn with_discovered_routes_mut<
111        O,
112        F: FnOnce(&mut Ipv6RouteDiscoveryState<BT>, &mut Self::WithDiscoveredRoutesMutCtx<'_>) -> O,
113    >(
114        &mut self,
115        device_id: &Self::DeviceId,
116        cb: F,
117    ) -> O;
118}
119
120/// The bindings types for IPv6 route discovery.
121pub trait Ipv6RouteDiscoveryBindingsTypes: TimerBindingsTypes + InstantBindingsTypes {}
122impl<BT> Ipv6RouteDiscoveryBindingsTypes for BT where BT: TimerBindingsTypes + InstantBindingsTypes {}
123
124/// The bindings execution context for IPv6 route discovery.
125pub trait Ipv6RouteDiscoveryBindingsContext:
126    Ipv6RouteDiscoveryBindingsTypes + TimerContext
127{
128}
129impl<BC> Ipv6RouteDiscoveryBindingsContext for BC where
130    BC: Ipv6RouteDiscoveryBindingsTypes + TimerContext
131{
132}
133
134/// An implementation of IPv6 route discovery.
135pub trait RouteDiscoveryHandler<BC>: DeviceIdContext<AnyDevice> {
136    /// Handles an update affecting discovered routes.
137    ///
138    /// A `None` value for `lifetime` indicates that the route is not valid and
139    /// must be invalidated if it has been discovered; a `Some(_)` value
140    /// indicates the new maximum lifetime that the route may be valid for
141    /// before being invalidated.
142    fn update_route(
143        &mut self,
144        bindings_ctx: &mut BC,
145        device_id: &Self::DeviceId,
146        route: Ipv6DiscoveredRoute,
147        lifetime: Option<NonZeroNdpLifetime>,
148    );
149
150    /// Invalidates all discovered routes.
151    fn invalidate_routes(&mut self, bindings_ctx: &mut BC, device_id: &Self::DeviceId);
152}
153
154impl<BC: Ipv6RouteDiscoveryBindingsContext, CC: Ipv6RouteDiscoveryContext<BC>>
155    RouteDiscoveryHandler<BC> for CC
156{
157    fn update_route(
158        &mut self,
159        bindings_ctx: &mut BC,
160        device_id: &CC::DeviceId,
161        route: Ipv6DiscoveredRoute,
162        lifetime: Option<NonZeroNdpLifetime>,
163    ) {
164        self.with_discovered_routes_mut(device_id, |state, core_ctx| {
165            let Ipv6RouteDiscoveryState { routes, timers } = state;
166            match lifetime {
167                Some(lifetime) => {
168                    let newly_added = routes.insert(route.clone());
169                    if newly_added {
170                        core_ctx.add_discovered_ipv6_route(bindings_ctx, device_id, route);
171                    }
172
173                    let prev_timer_fires_at = match lifetime {
174                        NonZeroNdpLifetime::Finite(lifetime) => {
175                            timers.schedule_after(bindings_ctx, route, (), lifetime.get())
176                        }
177                        // Routes with an infinite lifetime have no timers.
178                        NonZeroNdpLifetime::Infinite => timers.cancel(bindings_ctx, &route),
179                    };
180
181                    if newly_added {
182                        if let Some((prev_timer_fires_at, ())) = prev_timer_fires_at {
183                            panic!(
184                                "newly added route {:?} should not have already been \
185                                 scheduled to fire at {:?}",
186                                route, prev_timer_fires_at,
187                            )
188                        }
189                    }
190                }
191                None => {
192                    if routes.remove(&route) {
193                        invalidate_route(core_ctx, bindings_ctx, device_id, state, route);
194                    }
195                }
196            }
197        })
198    }
199
200    fn invalidate_routes(&mut self, bindings_ctx: &mut BC, device_id: &CC::DeviceId) {
201        self.with_discovered_routes_mut(device_id, |state, core_ctx| {
202            for route in core::mem::take(&mut state.routes).into_iter() {
203                invalidate_route(core_ctx, bindings_ctx, device_id, state, route);
204            }
205        })
206    }
207}
208
209impl<BC: Ipv6RouteDiscoveryBindingsContext, CC: Ipv6RouteDiscoveryContext<BC>>
210    HandleableTimer<CC, BC> for Ipv6DiscoveredRouteTimerId<CC::WeakDeviceId>
211{
212    fn handle(self, core_ctx: &mut CC, bindings_ctx: &mut BC, _: BC::UniqueTimerId) {
213        let Self { device_id } = self;
214        let Some(device_id) = device_id.upgrade() else {
215            return;
216        };
217        core_ctx.with_discovered_routes_mut(
218            &device_id,
219            |Ipv6RouteDiscoveryState { routes, timers }, core_ctx| {
220                let Some((route, ())) = timers.pop(bindings_ctx) else {
221                    return;
222                };
223                assert!(routes.remove(&route), "invalidated route should be discovered");
224                del_discovered_ipv6_route(core_ctx, bindings_ctx, &device_id, route);
225            },
226        )
227    }
228}
229
230fn del_discovered_ipv6_route<
231    BC: Ipv6RouteDiscoveryBindingsContext,
232    CC: Ipv6DiscoveredRoutesContext<BC>,
233>(
234    core_ctx: &mut CC,
235    bindings_ctx: &mut BC,
236    device_id: &CC::DeviceId,
237    route: Ipv6DiscoveredRoute,
238) {
239    core_ctx.del_discovered_ipv6_route(bindings_ctx, device_id, route);
240}
241
242fn invalidate_route<BC: Ipv6RouteDiscoveryBindingsContext, CC: Ipv6DiscoveredRoutesContext<BC>>(
243    core_ctx: &mut CC,
244    bindings_ctx: &mut BC,
245    device_id: &CC::DeviceId,
246    state: &mut Ipv6RouteDiscoveryState<BC>,
247    route: Ipv6DiscoveredRoute,
248) {
249    // Routes with an infinite lifetime have no timers.
250    let _: Option<(BC::Instant, ())> = state.timers.cancel(bindings_ctx, &route);
251    del_discovered_ipv6_route(core_ctx, bindings_ctx, device_id, route)
252}
253
254#[cfg(test)]
255mod tests {
256    use netstack3_base::testutil::{
257        FakeBindingsCtx, FakeCoreCtx, FakeDeviceId, FakeInstant, FakeTimerCtxExt as _,
258        FakeWeakDeviceId,
259    };
260    use netstack3_base::{CtxPair, IntoCoreTimerCtx};
261    use packet_formats::utils::NonZeroDuration;
262
263    use super::*;
264    use crate::internal::base::IPV6_DEFAULT_SUBNET;
265
266    #[derive(Default)]
267    struct FakeWithDiscoveredRoutesMutCtx {
268        route_table: HashSet<Ipv6DiscoveredRoute>,
269    }
270
271    impl DeviceIdContext<AnyDevice> for FakeWithDiscoveredRoutesMutCtx {
272        type DeviceId = FakeDeviceId;
273        type WeakDeviceId = FakeWeakDeviceId<FakeDeviceId>;
274    }
275
276    impl<C> Ipv6DiscoveredRoutesContext<C> for FakeWithDiscoveredRoutesMutCtx {
277        fn add_discovered_ipv6_route(
278            &mut self,
279            _bindings_ctx: &mut C,
280            FakeDeviceId: &Self::DeviceId,
281            route: Ipv6DiscoveredRoute,
282        ) {
283            let Self { route_table } = self;
284            let _newly_inserted = route_table.insert(route);
285        }
286
287        fn del_discovered_ipv6_route(
288            &mut self,
289            _bindings_ctx: &mut C,
290            FakeDeviceId: &Self::DeviceId,
291            route: Ipv6DiscoveredRoute,
292        ) {
293            let Self { route_table } = self;
294            let _: bool = route_table.remove(&route);
295        }
296    }
297
298    struct FakeIpv6RouteDiscoveryContext {
299        state: Ipv6RouteDiscoveryState<FakeBindingsCtxImpl>,
300        route_table: FakeWithDiscoveredRoutesMutCtx,
301    }
302
303    type FakeCoreCtxImpl = FakeCoreCtx<FakeIpv6RouteDiscoveryContext, (), FakeDeviceId>;
304
305    type FakeBindingsCtxImpl =
306        FakeBindingsCtx<Ipv6DiscoveredRouteTimerId<FakeWeakDeviceId<FakeDeviceId>>, (), (), ()>;
307
308    impl Ipv6RouteDiscoveryContext<FakeBindingsCtxImpl> for FakeCoreCtxImpl {
309        type WithDiscoveredRoutesMutCtx<'a> = FakeWithDiscoveredRoutesMutCtx;
310
311        fn with_discovered_routes_mut<
312            O,
313            F: FnOnce(
314                &mut Ipv6RouteDiscoveryState<FakeBindingsCtxImpl>,
315                &mut Self::WithDiscoveredRoutesMutCtx<'_>,
316            ) -> O,
317        >(
318            &mut self,
319            &FakeDeviceId: &Self::DeviceId,
320            cb: F,
321        ) -> O {
322            let FakeIpv6RouteDiscoveryContext { state, route_table, .. } = &mut self.state;
323            cb(state, route_table)
324        }
325    }
326
327    const ROUTE1: Ipv6DiscoveredRoute =
328        Ipv6DiscoveredRoute { subnet: IPV6_DEFAULT_SUBNET, gateway: None };
329    const ROUTE2: Ipv6DiscoveredRoute = Ipv6DiscoveredRoute {
330        subnet: unsafe {
331            Subnet::new_unchecked(Ipv6Addr::new([0x2620, 0x1012, 0x1000, 0x5000, 0, 0, 0, 0]), 64)
332        },
333        gateway: None,
334    };
335
336    const ONE_SECOND: NonZeroDuration = NonZeroDuration::from_secs(1).unwrap();
337    const TWO_SECONDS: NonZeroDuration = NonZeroDuration::from_secs(2).unwrap();
338
339    fn new_context() -> CtxPair<FakeCoreCtxImpl, FakeBindingsCtxImpl> {
340        CtxPair::with_default_bindings_ctx(|bindings_ctx| {
341            FakeCoreCtxImpl::with_state(FakeIpv6RouteDiscoveryContext {
342                state: Ipv6RouteDiscoveryState::new::<_, IntoCoreTimerCtx>(
343                    bindings_ctx,
344                    FakeWeakDeviceId(FakeDeviceId),
345                ),
346                route_table: Default::default(),
347            })
348        })
349    }
350
351    #[test]
352    fn new_route_no_lifetime() {
353        let CtxPair { mut core_ctx, mut bindings_ctx } = new_context();
354
355        RouteDiscoveryHandler::update_route(
356            &mut core_ctx,
357            &mut bindings_ctx,
358            &FakeDeviceId,
359            ROUTE1,
360            None,
361        );
362        bindings_ctx.timers.assert_no_timers_installed();
363    }
364
365    fn discover_new_route(
366        core_ctx: &mut FakeCoreCtxImpl,
367        bindings_ctx: &mut FakeBindingsCtxImpl,
368        route: Ipv6DiscoveredRoute,
369        duration: NonZeroNdpLifetime,
370    ) {
371        RouteDiscoveryHandler::update_route(
372            core_ctx,
373            bindings_ctx,
374            &FakeDeviceId,
375            route,
376            Some(duration),
377        );
378
379        let route_table = &core_ctx.state.route_table.route_table;
380        assert!(route_table.contains(&route), "route_table={route_table:?}");
381
382        let expect = match duration {
383            NonZeroNdpLifetime::Finite(duration) => Some((FakeInstant::from(duration.get()), &())),
384            NonZeroNdpLifetime::Infinite => None,
385        };
386        assert_eq!(core_ctx.state.state.timers.get(&route), expect);
387    }
388
389    fn trigger_next_timer(
390        core_ctx: &mut FakeCoreCtxImpl,
391        bindings_ctx: &mut FakeBindingsCtxImpl,
392        route: Ipv6DiscoveredRoute,
393    ) {
394        core_ctx.state.state.timers.assert_top(&route, &());
395        assert_eq!(
396            bindings_ctx.trigger_next_timer(core_ctx),
397            Some(Ipv6DiscoveredRouteTimerId { device_id: FakeWeakDeviceId(FakeDeviceId) })
398        );
399    }
400
401    fn assert_route_invalidated(
402        core_ctx: &mut FakeCoreCtxImpl,
403        bindings_ctx: &mut FakeBindingsCtxImpl,
404        route: Ipv6DiscoveredRoute,
405    ) {
406        let route_table = &core_ctx.state.route_table.route_table;
407        assert!(!route_table.contains(&route), "route_table={route_table:?}");
408        bindings_ctx.timers.assert_no_timers_installed();
409    }
410
411    fn assert_single_invalidation_timer(
412        core_ctx: &mut FakeCoreCtxImpl,
413        bindings_ctx: &mut FakeBindingsCtxImpl,
414        route: Ipv6DiscoveredRoute,
415    ) {
416        trigger_next_timer(core_ctx, bindings_ctx, route);
417        assert_route_invalidated(core_ctx, bindings_ctx, route);
418    }
419
420    #[test]
421    fn invalidated_route_not_found() {
422        let CtxPair { mut core_ctx, mut bindings_ctx } = new_context();
423
424        discover_new_route(&mut core_ctx, &mut bindings_ctx, ROUTE1, NonZeroNdpLifetime::Infinite);
425
426        // Fake the route already being removed from underneath the route
427        // discovery table.
428        assert!(core_ctx.state.route_table.route_table.remove(&ROUTE1));
429        // Invalidating the route should ignore the fact that the route is not
430        // in the route table.
431        update_to_invalidate_check_invalidation(&mut core_ctx, &mut bindings_ctx, ROUTE1);
432    }
433
434    #[test]
435    fn new_route_with_infinite_lifetime() {
436        let CtxPair { mut core_ctx, mut bindings_ctx } = new_context();
437
438        discover_new_route(&mut core_ctx, &mut bindings_ctx, ROUTE1, NonZeroNdpLifetime::Infinite);
439        bindings_ctx.timers.assert_no_timers_installed();
440    }
441
442    #[test]
443    fn update_route_from_infinite_to_finite_lifetime() {
444        let CtxPair { mut core_ctx, mut bindings_ctx } = new_context();
445
446        discover_new_route(&mut core_ctx, &mut bindings_ctx, ROUTE1, NonZeroNdpLifetime::Infinite);
447        bindings_ctx.timers.assert_no_timers_installed();
448
449        RouteDiscoveryHandler::update_route(
450            &mut core_ctx,
451            &mut bindings_ctx,
452            &FakeDeviceId,
453            ROUTE1,
454            Some(NonZeroNdpLifetime::Finite(ONE_SECOND)),
455        );
456        assert_eq!(
457            core_ctx.state.state.timers.get(&ROUTE1),
458            Some((FakeInstant::from(ONE_SECOND.get()), &()))
459        );
460        assert_single_invalidation_timer(&mut core_ctx, &mut bindings_ctx, ROUTE1);
461    }
462
463    fn update_to_invalidate_check_invalidation(
464        core_ctx: &mut FakeCoreCtxImpl,
465        bindings_ctx: &mut FakeBindingsCtxImpl,
466        route: Ipv6DiscoveredRoute,
467    ) {
468        RouteDiscoveryHandler::update_route(core_ctx, bindings_ctx, &FakeDeviceId, ROUTE1, None);
469        assert_route_invalidated(core_ctx, bindings_ctx, route);
470    }
471
472    #[test]
473    fn invalidate_route_with_infinite_lifetime() {
474        let CtxPair { mut core_ctx, mut bindings_ctx } = new_context();
475
476        discover_new_route(&mut core_ctx, &mut bindings_ctx, ROUTE1, NonZeroNdpLifetime::Infinite);
477        bindings_ctx.timers.assert_no_timers_installed();
478
479        update_to_invalidate_check_invalidation(&mut core_ctx, &mut bindings_ctx, ROUTE1);
480    }
481    #[test]
482    fn new_route_with_finite_lifetime() {
483        let CtxPair { mut core_ctx, mut bindings_ctx } = new_context();
484
485        discover_new_route(
486            &mut core_ctx,
487            &mut bindings_ctx,
488            ROUTE1,
489            NonZeroNdpLifetime::Finite(ONE_SECOND),
490        );
491        assert_single_invalidation_timer(&mut core_ctx, &mut bindings_ctx, ROUTE1);
492    }
493
494    #[test]
495    fn update_route_from_finite_to_infinite_lifetime() {
496        let CtxPair { mut core_ctx, mut bindings_ctx } = new_context();
497
498        discover_new_route(
499            &mut core_ctx,
500            &mut bindings_ctx,
501            ROUTE1,
502            NonZeroNdpLifetime::Finite(ONE_SECOND),
503        );
504
505        RouteDiscoveryHandler::update_route(
506            &mut core_ctx,
507            &mut bindings_ctx,
508            &FakeDeviceId,
509            ROUTE1,
510            Some(NonZeroNdpLifetime::Infinite),
511        );
512        bindings_ctx.timers.assert_no_timers_installed();
513    }
514
515    #[test]
516    fn update_route_from_finite_to_finite_lifetime() {
517        let CtxPair { mut core_ctx, mut bindings_ctx } = new_context();
518
519        discover_new_route(
520            &mut core_ctx,
521            &mut bindings_ctx,
522            ROUTE1,
523            NonZeroNdpLifetime::Finite(ONE_SECOND),
524        );
525
526        RouteDiscoveryHandler::update_route(
527            &mut core_ctx,
528            &mut bindings_ctx,
529            &FakeDeviceId,
530            ROUTE1,
531            Some(NonZeroNdpLifetime::Finite(TWO_SECONDS)),
532        );
533        assert_eq!(
534            core_ctx.state.state.timers.get(&ROUTE1),
535            Some((FakeInstant::from(TWO_SECONDS.get()), &()))
536        );
537        assert_single_invalidation_timer(&mut core_ctx, &mut bindings_ctx, ROUTE1);
538    }
539
540    #[test]
541    fn invalidate_route_with_finite_lifetime() {
542        let CtxPair { mut core_ctx, mut bindings_ctx } = new_context();
543
544        discover_new_route(
545            &mut core_ctx,
546            &mut bindings_ctx,
547            ROUTE1,
548            NonZeroNdpLifetime::Finite(ONE_SECOND),
549        );
550
551        update_to_invalidate_check_invalidation(&mut core_ctx, &mut bindings_ctx, ROUTE1);
552    }
553
554    #[test]
555    fn invalidate_all_routes() {
556        let CtxPair { mut core_ctx, mut bindings_ctx } = new_context();
557        discover_new_route(
558            &mut core_ctx,
559            &mut bindings_ctx,
560            ROUTE1,
561            NonZeroNdpLifetime::Finite(ONE_SECOND),
562        );
563        discover_new_route(
564            &mut core_ctx,
565            &mut bindings_ctx,
566            ROUTE2,
567            NonZeroNdpLifetime::Finite(TWO_SECONDS),
568        );
569
570        RouteDiscoveryHandler::invalidate_routes(&mut core_ctx, &mut bindings_ctx, &FakeDeviceId);
571        bindings_ctx.timers.assert_no_timers_installed();
572        let route_table = &core_ctx.state.route_table.route_table;
573        assert!(route_table.is_empty(), "route_table={route_table:?}");
574    }
575}
netstack3_ip/device/route_discovery.rs

netstack3_ip/device/
route_discovery.rs
