Skip to main content

shadow_rs/network/router/
mod.rs

1//! A [`Router`] routes [`PacketRc`]s between [`PacketDevice`]s and the
2//! simulated network, enforcing configured send/receive rate limits on the
3//! interfaces and the upstream/downstream links to a modeled network provider.
4//!
5//! The [`Router`] is responsible for actually moving packets around between
6//! sockets and the simulated network. It initiates packet forwarding and
7//! internally schedules tasks to ensure that packets are continually forwarded
8//! over time without exceeding the configured [`RateLimit`]s.
9//!
10//! The [`Router`] implemented here is doing the job of multiple real world
11//! physical components, rather than being a one-to-one mapping to a known
12//! network component. It is managing sending from a physical network interface
13//! card at a certain speed, and also it is managing the first-hop router device
14//! that the network interface card is attached to, shaping traffic, and using a
15//! codel queue to aggregate all its ports up through a single upstream link.
16//!
17//! [`PacketDevice`]s are registered using [`Router::attach_packet_device`],
18//! assigning an [`Ipv4Addr`] to it. The address provided by the caller will
19//! later be passed to [`RouterContext::get_packet_device_fn`] to obtain the
20//! underlying object that implements the [`PacketDevice`] trait. This packet
21//! device supplies the router with a stream of packets (through its
22//! implementation of [`PacketDevice::pop`]) that will be forwarded to the
23//! network, and it acts as a sink for incoming packets with a destination
24//! address matching the packet device's address.
25//!
26//! [`Ipv4Addr::LOCALHOST`] has special meaning, and it is expected that a
27//! packet device will be registered at this address. The router uses the device
28//! as the loopback device, applying its rate limits for local packets being
29//! sent from any device.
30//!
31//! The [`Router`] operates its own event management queues and its scheduler
32//! must be run at appropriate times to faciliate the routing process.
33//! [`Router::run`] must be called with event [`RouterEvent::DeviceInterrupt`]
34//! when a packet device changes state from empty to non-empty, to alert an idle
35//! router to start forwarding packets from that device. [`Router::run`] must be
36//! called with event [`RouterEvent::PacketArrival`] when a packet arrives from
37//! the simulated network. Finally, if [`Router::run`] returns an
38//! [`EmulatedTime`], then [`Router::run`] must be called with event
39//! [`RouterEvent::Wakeup`] at the specified time. All other routing tasks are
40//! handled internally.
41//!
42//! The [`Router`] is designed to avoid directly relying on Shadow runtime
43//! components and to be easy to test with unit tests. This is enabled through
44//! the [`RouterContext`] object, which defines the minimal external API the
45//! router needs to function. This context must be provided when calling
46//! [`Router::run`].
47//!
48//! A variety of queues are used to model rate limits, as shown below. Each tx
49//! queue and rx queue is a lossy rate-limited queue that can drop packets if it
50//! becomes bloated (e.g., if we are allowed to push() to a queue at a faster
51//! rate than we are allowed to pop() from it based on the configured rate
52//! limits). Note, all pop() and push() actions are carried out by the router,
53//! not the individual components listed here.
54//!
55//!   +--------------+               +--------------+
56//!   | PacketDevice |               | PacketDevice |
57//!   +--------------+               +--------------+
58//!          |                              |
59//!  Event::DeviceInterrupt        Event::DeviceInterrupt
60//!          |                              |
61//!          V push()                       V push()
62//!     +-----------+                  +-----------+
63//!     | Interface |                  | Interface |
64//!     | tx queue  |                  | tx queue  |
65//!     +-----------+                  +-----------+
66//!          |                              |
67//!  pop() @ dev tx rate limit    pop() @ dev tx rate limit
68//!          |                              |
69//!          +--------------+---------------+
70//!                         |
71//!                         V push()
72//!               +-------------------+
73//!               |   Global router   |
74//!               |     tx queue      |
75//!               +-------------------+
76//!                         |
77//!             pop() @ upstream tx rate limit
78//!                         |
79//!                         V Context::send_packet_fn()
80//!               +--------------------+
81//!               | packets to network |
82//!               +--------------------+
83//!                        |||
84//!              core link ||| models latency, packet loss
85//!                        ||| unlimited bandwidth
86//!                        VVV
87//!               +----------------------+
88//!               | packets from network |
89//!               +----------------------+
90//!                         |
91//!              RouterEvent::PacketArrival
92//!                         |
93//!                         V push()
94//!               +-------------------+
95//!               |   Global router   |
96//!               |     rx queue      |
97//!               +-------------------+
98//!                         |
99//!             pop() @ downstream rx rate limit
100//!                         |
101//!          +--------------+---------------+
102//!          |                              |
103//!          V push()                       V push()
104//!     +-----------+                  +-----------+
105//!     | Interface |                  | Interface |
106//!     | rx queue  |                  | rx queue  |
107//!     +-----------+                  +-----------+
108//!          |                              |
109//!  pop() @ dev rx rate limit    pop() @ dev rx rate limit
110//!          |                              |
111//!          V push()                       V push()
112//!   +--------------+               +--------------+
113//!   | PacketDevice |               | PacketDevice |
114//!   +--------------+               +--------------+
115//!
116//! Note: the cross-device loopback process is not shown above.
117//!
118
119use std::cell::Ref;
120use std::collections::{BTreeSet, HashMap};
121use std::net::Ipv4Addr;
122
123use atomic_refcell::AtomicRefCell;
124use shadow_shim_helper_rs::emulated_time::EmulatedTime;
125use shadow_shim_helper_rs::simulation_time::SimulationTime;
126
127use crate::cshadow;
128use crate::network::packet::PacketRc;
129use crate::network::{PacketDevice, RateLimit};
130use crate::utility::ObjectCounter;
131
132use self::codel_queue::CoDelQueue;
133use self::task::{TaskKind, TaskQueue};
134use self::token_bucket::TokenBucket;
135
136mod codel_queue;
137mod task;
138mod token_bucket;
139
140/// An alias for the router context, to clearly separate it from other contexts
141/// in the simulator. Code external to the router should probably prefer this
142/// [`RouterContext`] to the [`Context`] syntax for clarity.
143pub type RouterContext<'a, T> = Context<'a, T>;
144
145/// Generalizes the runtime state needed to run the router.
146//
147// This both improves the clarity of the code, and enables unit testing. Note:
148// we name this as Context here, instead of RouterContext, to keep the router's
149// internal implementation more concise.
150#[derive(Clone, Copy, Debug)]
151pub struct Context<'a, T> {
152    /// The current value of the runtime clock.
153    pub now: EmulatedTime,
154    /// If the runtime is in bootstrapping mode, where rate limits are ignored.
155    pub is_bootstrapping: bool,
156    /// The function the router will call when it needs to send a packet over
157    /// the simulated network.
158    pub send_packet_fn: fn(&'a T, PacketRc),
159    /// The function the router will call to obtain the underlying packet device
160    /// for the address configured in [`Router::attach_packet_device`]. The
161    /// underlying device is a src/stream for outgoing packets and a dst/sink
162    /// for incoming packets.
163    pub get_packet_device_fn: fn(&'a T, Ipv4Addr) -> Option<Ref<'_, dyn PacketDevice>>,
164    /// The first argument that will be supplied when calling the
165    /// [`Context::send_packet_fn`] and [`Context::get_packet_device_fn`]
166    /// callback functions.
167    pub fn_arg: &'a T,
168}
169
170/// An alias for a router event, to clearly separate it from other events in the
171/// simulator. Code external to the router should probably prefer this
172/// [`RouterEvent`] to the [`Event`] syntax for clarity.
173pub type RouterEvent = Event;
174
175/// The events handled by the [`Router`].
176//
177// Although there is some overlap, this is designed to be distinct from the
178// router's [`Task`] object: a task in an internal implementation detail and we
179// don't expose all task kinds outside of this module.
180#[derive(Clone, Debug, Eq, PartialEq)]
181pub enum Event {
182    /// A packet has arrived to the host from the simulated network.
183    PacketArrival(PacketRc),
184    /// A packet device has new data that needs to be routed.
185    DeviceInterrupt(Ipv4Addr),
186    /// The router's requested wakeup time has been reached.
187    Wakeup,
188}
189
190// In our internal implementation, every event is a task that needs to be run.
191impl From<Event> for TaskKind {
192    fn from(event: Event) -> Self {
193        match event {
194            Event::PacketArrival(packet) => TaskKind::Deliver(packet),
195            Event::DeviceInterrupt(addr) => TaskKind::TxDevice(addr),
196            Event::Wakeup => TaskKind::ProcessQueue,
197        }
198    }
199}
200
201/// Tracks the current state of the router to help prevent recursive run loops.
202#[derive(Clone, Debug, Eq, PartialEq)]
203enum State {
204    /// The router is currently not executing its runtime logic; it is waiting
205    /// to be notified that a [`Event`] has occured (via a call to
206    /// [`Router::run`]).
207    Idle,
208    /// The router is executing its runtime logic. Any [`Event`]s that occur
209    /// while in this state held in this deferred queue (to be handled when
210    /// running is complete).
211    Running(Vec<Event>),
212}
213
214/// A [`Router`] routes [`PacketRc`]s between [`PacketDevice`]s and the
215/// simulated network, enforcing configured send/receive rate limits on the
216/// interfaces and the upstream/downstream links to a modeled network provider.
217///
218/// For more information, see the module docs for [`crate::network::router`].
219#[derive(Debug)]
220pub struct Router {
221    /// The router's current run state.
222    state: AtomicRefCell<State>,
223    /// The inner collection of queues and interfaces needed to route packets
224    /// while conforming to rate limits.
225    inner: AtomicRefCell<Inner>,
226    /// The collection of tasks the router needs to perform to function.
227    tasks: AtomicRefCell<TaskQueue>,
228    /// The times we have requested an [`Event::Wakeup`] (i.e., the times we
229    /// have returned from [`Router::run`]) that have not yet occurred.
230    wakeup_times: AtomicRefCell<BTreeSet<EmulatedTime>>,
231    /// Counts allocations/deallocations. Declared at the end so a drop is not
232    /// counted until the other struct elements above are dropped.
233    _counter: ObjectCounter,
234}
235
236#[derive(Debug)]
237struct Inner {
238    /// Our global transmit queue. Packets from this queue are routed to the network.
239    txq: RateLimitedQueue,
240    /// Our global receive queue. Packets from the network are routed to this queue.
241    rxq: RateLimitedQueue,
242    /// The attached packet devices, each of which is wrapped with our Interface
243    /// type to manage its tx and rx queues.
244    interfaces: HashMap<Ipv4Addr, Interface>,
245}
246
247impl Inner {
248    fn new(tx_rate: RateLimit, rx_rate: RateLimit) -> Self {
249        Self {
250            txq: RateLimitedQueue::new(tx_rate),
251            rxq: RateLimitedQueue::new(rx_rate),
252            interfaces: HashMap::new(),
253        }
254    }
255}
256
257impl Router {
258    /// Creates a new [`Router`] instance with the given rate limits set on its
259    /// global transmit and receive queues.
260    pub fn new(tx_rate: RateLimit, rx_rate: RateLimit) -> Self {
261        Self {
262            state: AtomicRefCell::new(State::Idle),
263            inner: AtomicRefCell::new(Inner::new(tx_rate, rx_rate)),
264            tasks: AtomicRefCell::new(TaskQueue::new()),
265            wakeup_times: AtomicRefCell::new(BTreeSet::new()),
266            _counter: ObjectCounter::new("Router"),
267        }
268    }
269
270    /// Add a new device at the given address, and assign the given rate limits
271    /// to the associated transmit and receive queues.
272    ///
273    /// It is assumed that the router will be able to obtain a reference to the
274    /// underlying device implementing the [`PacketDevice`] trait when it calls
275    /// [`RouterContext::get_packet_device_fn`] and passes the address provided here. It
276    /// is up to the caller to set the correct router context and addressing.
277    pub fn attach_packet_device(&mut self, addr: Ipv4Addr, tx_rate: RateLimit, rx_rate: RateLimit) {
278        let device = Interface::new(addr, tx_rate, rx_rate);
279        self.inner.borrow_mut().interfaces.insert(addr, device);
280    }
281
282    /// Run the router with the given context to handle the provided [`RouterEvent`].
283    ///
284    /// If this function returns [`Some`], the caller must ensure that
285    /// [`Router::run`] is called again with the [`RouterEvent::Wakeup`] event
286    /// at the contained [`EmulatedTime`].
287    pub fn run<T>(&self, ctx: &Context<T>, event: RouterEvent) -> Option<EmulatedTime> {
288        log::trace!("Router::run({event:?})");
289
290        // If we are already running, defer this event to run in our
291        // pre-existing processing loop to prevent double borrows.
292        if let State::Running(deferred) = &mut *self.state.borrow_mut() {
293            deferred.push(event);
294            return None;
295        }
296
297        // We were idle and now we are running.
298        *self.state.borrow_mut() = State::Running(Vec::new());
299
300        if event == Event::Wakeup {
301            self.wakeup_times.borrow_mut().remove(&ctx.now);
302            self.process_task_queue(ctx);
303        } else {
304            self.schedule(ctx, TaskKind::from(event));
305        };
306
307        // Change state back from running to idle.
308        let prev_state = {
309            let state = &mut *self.state.borrow_mut();
310            std::mem::replace(state, State::Idle)
311        };
312        let State::Running(deferred) = prev_state else {
313            panic!("Expected router in State::Running");
314        };
315
316        // Schedule any events we deferred while we were running.
317        for event in deferred {
318            self.schedule(ctx, TaskKind::from(event));
319        }
320
321        // Decide when to run the router next.
322        let next = self.tasks.borrow().peek().map(|task| task.when);
323        next.and_then(|when| {
324            if !self.wakeup_times.borrow().contains(&when) {
325                self.wakeup_times.borrow_mut().insert(when);
326                Some(when)
327            } else {
328                None
329            }
330        })
331    }
332
333    /// Schedules a task in the routers scheduling queue for future processing.
334    fn schedule<T>(&self, ctx: &Context<T>, kind: TaskKind) {
335        // Compute when we are allowed to run the task based on rate limits.
336        let when = {
337            let inner = self.inner.borrow();
338            match &kind {
339                TaskKind::Deliver(_) => ctx.now,
340                TaskKind::TxGlobal => inner.txq.ready_at(ctx),
341                TaskKind::RxGlobal => inner.rxq.ready_at(ctx),
342                TaskKind::TxDevice(addr) => match inner.interfaces.get(addr) {
343                    Some(iface) => iface.txq.ready_at(ctx),
344                    None => return Router::warn_schedule_failed(&kind, "interface not found"),
345                },
346                TaskKind::RxDevice(addr) => match inner.interfaces.get(addr) {
347                    Some(iface) => iface.rxq.ready_at(ctx),
348                    None => return Router::warn_schedule_failed(&kind, "interface not found"),
349                },
350                TaskKind::ProcessQueue => ctx.now,
351            }
352        };
353
354        // Schedule our task, ensuring forward progression of time.
355        self.tasks.borrow_mut().schedule(kind, when.max(ctx.now));
356    }
357
358    /// Process all scheduled tasks that have been schedule to run at or before
359    /// the current time provided in the context.
360    fn process_task_queue<T>(&self, ctx: &Context<T>) {
361        // Process all scheduled non-future tasks.
362        while self
363            .tasks
364            .borrow()
365            .peek()
366            .is_some_and(|x| x.when <= ctx.now)
367        {
368            // Process the next operation without holding the borrow.
369            let task = self.tasks.borrow_mut().pop().unwrap();
370            self.process(ctx, task.kind);
371
372            // Schedule any new tasks that were generated.
373            for kind in self.collect_interrupts() {
374                self.schedule(ctx, kind);
375            }
376        }
377    }
378
379    /// Process an individual task.
380    fn process<T>(&self, ctx: &Context<T>, kind: TaskKind) {
381        match kind {
382            TaskKind::Deliver(packet) => self.process_deliver(ctx, packet),
383            TaskKind::TxGlobal => self.process_tx_global(ctx),
384            TaskKind::RxGlobal => self.process_rx_global(ctx),
385            TaskKind::TxDevice(addr) => self.process_tx_device(ctx, addr),
386            TaskKind::RxDevice(addr) => self.process_rx_device(ctx, addr),
387            TaskKind::ProcessQueue => {} // Already in progress.
388        }
389    }
390
391    /// A packet arriving from the network gets pushed to our global rx queue.
392    fn process_deliver<T>(&self, ctx: &Context<T>, packet: PacketRc) {
393        self.inner.borrow_mut().rxq.push(ctx, packet);
394    }
395
396    /// Use [`Context::send_packet_fn`] to send all packets ready to be sent.
397    fn process_tx_global<T>(&self, ctx: &Context<T>) {
398        while let Some(packet) = self.inner.borrow_mut().txq.pop(ctx) {
399            (ctx.send_packet_fn)(ctx.fn_arg, packet);
400        }
401    }
402
403    /// Route packets from the global receive queue to the corresponding device
404    /// receive queue.
405    fn process_rx_global<T>(&self, ctx: &Context<T>) {
406        let mut inner = self.inner.borrow_mut();
407
408        while let Some(packet) = inner.rxq.pop(ctx) {
409            let dst_addr = *packet.dst_ipv4_address().ip();
410            if let Some(iface) = inner.interfaces.get_mut(&dst_addr) {
411                iface.rxq.push(ctx, packet);
412            } else {
413                Router::warn_process_failed(
414                    &TaskKind::RxGlobal,
415                    &format!("device not found, packet dst {dst_addr}"),
416                );
417            }
418        }
419    }
420
421    /// Route packets from the underlying packet device to the correct transmit
422    /// queue for that device, and then up to the global transmit queue as rate
423    /// limits allow. Loopback packets are routed over to the loopback receive
424    /// queue.
425    fn process_tx_device<T>(&self, ctx: &Context<T>, addr: Ipv4Addr) {
426        let mut inner = self.inner.borrow_mut();
427
428        // Temporarily remove the device for processing.
429        // TODO: add a drop guard to add it back later, so we don't return
430        // somewhere and forget?
431        let Some(mut iface) = inner.interfaces.remove(&addr) else {
432            Router::warn_process_failed(&TaskKind::TxDevice(addr), "interface not found");
433            return;
434        };
435
436        loop {
437            let pkt = iface.txq.pop(ctx).or_else(|| {
438                if iface.txq.blocked_until.is_some() {
439                    // We reached our rate limit, try again later.
440                    //
441                    // TODO: since we return here, we won't be able to redirect
442                    // loopback packets from this packet device (see below) while we
443                    // are out of tokens. Fixing this may require a deeper redesign
444                    // of shadow's network interface and socket layers.
445                    return None; // returns from closure
446                }
447
448                // Not rate limited yet, check underlying packet device until we get
449                // a packet.
450                while let Some(pkt) = iface.pop(ctx) {
451                    // We got a packet, use the correct rate limit.
452                    //
453                    // NOTE: Unbound UDP sockets may send both local and nonlocal
454                    // packets from the default interface, and may send loopback
455                    // packets, so we must redirect to the right rate limiter.
456                    let src_addr = *pkt.src_ipv4_address().ip();
457                    let dst_addr = *pkt.dst_ipv4_address().ip();
458                    let is_local = src_addr == dst_addr || src_addr.is_loopback();
459
460                    if is_local && !addr.is_loopback() {
461                        if let Some(lo) = inner.interfaces.get_mut(&Ipv4Addr::LOCALHOST) {
462                            // Redirect over loopback, applying its configured rate
463                            // limits instead of this device's rate limits.
464                            lo.txq.push(ctx, pkt);
465                        } else {
466                            Router::warn_routing_failed(&dst_addr, "lo tx interface not found");
467                        }
468                        continue;
469                    } else {
470                        // Push then pop from this device's tx queue so we only
471                        // return a packet if it conforms to the device rate limit.
472                        iface.txq.push(ctx, pkt);
473                        return iface.txq.pop(ctx);
474                    }
475                }
476
477                // The underlying device is empty for now.
478                None
479            });
480
481            let Some(pkt) = pkt else {
482                break;
483            };
484
485            // Got a conforming packet in the txq. Route based on the dst
486            // address. From above, packets with default ip may show up on
487            // loopback for rate limiting, which we now route over to its rxq.
488            let src_addr = *pkt.src_ipv4_address().ip();
489            let dst_addr = *pkt.dst_ipv4_address().ip();
490            let is_local = src_addr == dst_addr || dst_addr.is_loopback();
491
492            if is_local {
493                // Route over loopback to its rxq.
494                if addr.is_loopback() {
495                    iface.rxq.push(ctx, pkt);
496                } else if let Some(lo) = inner.interfaces.get_mut(&Ipv4Addr::LOCALHOST) {
497                    lo.rxq.push(ctx, pkt);
498                } else {
499                    Router::warn_routing_failed(&dst_addr, "lo rx interface not found");
500                }
501            } else {
502                // Route upstream for network transmission.
503                inner.txq.push(ctx, pkt);
504            }
505        }
506
507        // Restore the device in our collection.
508        inner.interfaces.insert(addr, iface);
509    }
510
511    /// Route packets from the device receive queue to the actual underlying
512    /// packet device.
513    fn process_rx_device<T>(&self, ctx: &Context<T>, addr: Ipv4Addr) {
514        let mut inner = self.inner.borrow_mut();
515
516        // Temporarily remove the device for processing.
517        // TODO: add a drop guard to add it back later, so we don't return
518        // somewhere and forget?
519        let Some(mut iface) = inner.interfaces.remove(&addr) else {
520            Router::warn_process_failed(&TaskKind::RxDevice(addr), "device not found");
521            return;
522        };
523
524        while let Some(pkt) = iface.rxq.pop(ctx) {
525            let dst_addr = *pkt.dst_ipv4_address().ip();
526
527            // We may have packets in the loopback queue that have src and dst
528            // ip addresses of the default interface.
529            if addr == dst_addr {
530                iface.push(ctx, pkt);
531            } else if let Some(other) = inner.interfaces.get_mut(&dst_addr) {
532                other.push(ctx, pkt);
533            } else {
534                Router::warn_routing_failed(&dst_addr, "rx device not found");
535            }
536        }
537
538        // Restore the device in our collection.
539        inner.interfaces.insert(addr, iface);
540    }
541
542    /// Checks all interrupts that have occurred on our queues since the last
543    /// time we checked, and collects the corresponding router tasks we need to
544    /// execute to handle the interrupts.
545    fn collect_interrupts(&self) -> impl IntoIterator<Item = TaskKind> {
546        let mut kinds = Vec::new();
547        let mut inner = self.inner.borrow_mut();
548
549        if inner.txq.take_irq() {
550            kinds.push(TaskKind::TxGlobal);
551        }
552
553        if inner.rxq.take_irq() {
554            kinds.push(TaskKind::RxGlobal);
555        }
556
557        for (addr, iface) in inner.interfaces.iter_mut() {
558            if iface.txq.take_irq() {
559                kinds.push(TaskKind::TxDevice(*addr));
560            }
561
562            if iface.rxq.take_irq() {
563                kinds.push(TaskKind::RxDevice(*addr));
564            }
565        }
566
567        kinds
568    }
569
570    fn warn_schedule_failed(kind: &TaskKind, reason: &str) {
571        log::warn!("Router cannot schedule task {kind:?}: {reason}");
572    }
573
574    fn warn_process_failed(kind: &TaskKind, reason: &str) {
575        log::warn!("Router cannot process task {kind:?}: {reason}");
576    }
577
578    fn warn_routing_failed(addr: &Ipv4Addr, reason: &str) {
579        log::warn!("Router cannot route packet on {addr:?}: {reason}");
580    }
581}
582
583/// An object to help us pop and push to an underlying packet device while
584/// conforming to configured rate limits.
585#[derive(Debug)]
586struct Interface {
587    /// The address associated with the underlying packet device.
588    addr: Ipv4Addr,
589    /// The transmit queue, used to model the underlying packet devices send
590    /// speed.
591    txq: RateLimitedQueue,
592    /// The receive queue, used to model the underlying packet devices receive
593    /// speed.
594    rxq: RateLimitedQueue,
595}
596
597impl Interface {
598    /// Create a new interface with rate-limited transmit and receive queues.
599    ///
600    /// The provided address will be used with [`Context::get_packet_device_fn`]
601    /// to obtain the underlying packet device when we need to push/pop to/from
602    /// it.
603    fn new(addr: Ipv4Addr, tx_rate: RateLimit, rx_rate: RateLimit) -> Self {
604        Self {
605            addr,
606            txq: RateLimitedQueue::new(tx_rate),
607            rxq: RateLimitedQueue::new(rx_rate),
608        }
609    }
610
611    /// Pops the next packet directly from the underlying packet device.
612    fn pop<T>(&mut self, ctx: &Context<T>) -> Option<PacketRc> {
613        (ctx.get_packet_device_fn)(ctx.fn_arg, self.addr).and_then(|dev| dev.pop())
614    }
615
616    /// Pushes the packet directly to the underlying packet device.
617    fn push<T>(&mut self, ctx: &Context<T>, packet: PacketRc) {
618        if let Some(dev) = (ctx.get_packet_device_fn)(ctx.fn_arg, self.addr) {
619            dev.push(packet)
620        }
621    }
622}
623
624/// A rate-limited queue that can be popped only if it conforms to the
625/// configured rate limit. The queue is idle until it detects an action that
626/// requires it to be popped again, at which point it will exhibit an interrupt
627/// request.
628///
629/// There are two actions that cause interrupt requests (and that will need us
630/// to schedule a task on the router queue):
631/// 1. The queue changed from empty to nonempty.
632/// 2. The queue changed from ready to rate limited.
633///
634/// [`RateLimitedQueue::take_irq`] should be polled to detect the requests and
635/// schedule the appropriate router task.
636#[derive(Debug)]
637struct RateLimitedQueue {
638    /// The underlying queue storing packets.
639    packets: CoDelQueue,
640    /// The object we use to enforce a rate limit; None means no limit.
641    limiter: Option<TokenBucket>,
642    /// If we reached our rate limit, we become unblocked at this time.
643    blocked_until: Option<EmulatedTime>,
644    /// Tracks the queue's interrupt request state.
645    irq: bool,
646}
647
648impl RateLimitedQueue {
649    /// Creates a new packet queue that can be popped according the the given
650    /// rate limit.
651    fn new(limit: RateLimit) -> Self {
652        Self {
653            packets: CoDelQueue::default(),
654            limiter: limit.into(),
655            blocked_until: None,
656            irq: false,
657        }
658    }
659
660    /// Pushes a packet to the underling queue, tracking if the router needs to
661    /// take action on the queue after the push.
662    fn push<T>(&mut self, ctx: &Context<T>, packet: PacketRc) {
663        if self.packets.is_empty() {
664            self.irq = true;
665        }
666        self.packets.push(packet, ctx.now);
667    }
668
669    /// Pops a packet from the underling queue according to the configured rate
670    /// limit, tracking if the router needs to take action on the queue after
671    /// the pop.
672    ///
673    /// Returns [`None`] if the queue is empty or has become rate limited.
674    fn pop<T>(&mut self, ctx: &Context<T>) -> Option<PacketRc> {
675        // Check that we do not exceed rate limit.
676        if !ctx.is_bootstrapping
677            && let Some(tb) = &mut self.limiter
678            && let Some(packet) = self.packets.peek()
679        {
680            let tokens_needed = u64::try_from(packet.len()).unwrap_or(u64::MAX);
681            match tb.comforming_remove(tokens_needed, &ctx.now) {
682                Ok(_) => self.blocked_until = None,
683                Err(duration) => {
684                    if self.blocked_until.is_none() {
685                        self.irq = true;
686                    }
687                    self.blocked_until = Some(ctx.now.saturating_add(duration));
688                    return None;
689                }
690            }
691        }
692
693        let result = self.packets.pop(ctx.now);
694        // If we had a pending irq but now emptied the queue, cancel it.
695        if self.irq && self.packets.is_empty() {
696            self.irq = false;
697        }
698        result
699    }
700
701    /// Returns true if we have an outstanding interrupt request, and clears our
702    /// internal flag for tracking interrupt requests.
703    fn take_irq(&mut self) -> bool {
704        std::mem::replace(&mut self.irq, false)
705    }
706
707    /// Returns the time when we will not be blocked due to rate limiting (i.e.,
708    /// when [`RateLimitedQueue::pop`] will not return [`None`] because of a
709    /// rate limit block).
710    fn ready_at<T>(&self, ctx: &Context<T>) -> EmulatedTime {
711        self.blocked_until.unwrap_or(ctx.now)
712    }
713}
714
715impl From<RateLimit> for Option<TokenBucket> {
716    fn from(limit: RateLimit) -> Self {
717        match limit {
718            RateLimit::BytesPerSecond(bytes) => Some(create_token_bucket(bytes)),
719            RateLimit::Unlimited => None,
720        }
721    }
722}
723
724/// Configures a token bucket according the the given bytes_per_second rate
725/// limit. We always refill at least 1 byte per millisecond.
726fn create_token_bucket(bytes_per_second: u64) -> TokenBucket {
727    let refill_interval = SimulationTime::from_millis(1);
728    let refill_size = std::cmp::max(1, bytes_per_second / 1000);
729
730    // Only the `capacity` of the bucket is increased by the burst allowance,
731    // not the `refill_size`. Therefore, the long term rate limit enforced by
732    // the token bucket (configured by `refill_size`) is not affected much.
733    let capacity = refill_size + get_burst_allowance();
734
735    TokenBucket::new(capacity, refill_size, refill_interval).unwrap()
736}
737
738/// Returns the "burst allowance" we use in our token buckets.
739///
740/// What the burst allowance ensures is that we don't lose tokens that are
741/// unused because we don't fragment packets. If we set the capacity of the
742/// bucket to exactly the refill size (i.e., without the `CONFIG_MTU` burst
743/// allowance) and there are only 1499 tokens left in this sending round, a full
744/// packet would not fit. The next time the bucket refills, it adds
745/// `refill_size` tokens but in doing so 1499 tokens would fall over the top of
746/// the bucket; these tokens would represent wasted bandwidth, and could
747/// potentially accumulate in every refill interval leading to a significantly
748/// lower achievable bandwidth.
749///
750/// A downside of the `CONFIG_MTU` burst allowance is that the sending rate
751/// could possibly become "bursty" with a behavior such as:
752/// - interval 1: send `refill_size` + `CONFIG_MTU` bytes, sending over the
753///   allowance by 1500 bytes
754/// - refill: `refill_size` token gets added to the bucket
755/// - interval 2: send `refill_size` - `CONFIG_MTU` bytes, sending under the
756///   allowance by 1500 bytes
757/// - refill: `refill_size` token gets added to the bucket
758/// - interval 3: send `refill_size` + `CONFIG_MTU` bytes, sending over the
759///   allowance by 1500 bytes
760/// - repeat
761///
762/// So it could become less smooth and more "bursty" even though the long term
763/// average is maintained. But I don't think this would happen much in practice,
764/// and we are batching sends for performance reasons.
765fn get_burst_allowance() -> u64 {
766    cshadow::CONFIG_MTU.into()
767}
768
769#[cfg(test)]
770mod tests {
771    use super::*;
772    use std::cell::RefCell;
773    use std::collections::VecDeque;
774    use std::net::{Ipv4Addr, SocketAddrV4};
775
776    // The time to start the router events. This needs to stay in sync with the
777    // time in `TokenBucket::new()`.
778    const START_TIME: EmulatedTime = EmulatedTime::SIMULATION_START;
779
780    // For test convenience.
781    const TEST_ADDR: Ipv4Addr = Ipv4Addr::new(10, 0, 0, 1);
782
783    // Length of packet to use in tests.
784    const PACKET_LEN: usize = 1_460;
785
786    // Ensures CoDel queue won't drop packets during test. Equates to 500 bytes
787    // per millisecond refill and ~2,000 byte capacity, so the bucket will have
788    // to block after the first packet of length PACKET_LEN.
789    const BPS_LIMIT_LOW: u64 = 500_000;
790
791    // Ensures CoDel queue won't drop packets during test. Equates to 1,000
792    // bytes per millisecond refill and ~2,500 byte capacity, so the bucket will
793    // have to block after the first packet of length PACKET_LEN.
794    const BPS_LIMIT_HIGH: u64 = 1_000_000;
795
796    struct MockHost {
797        router: Router,
798        interfaces: HashMap<Ipv4Addr, RefCell<MockInterface>>,
799        net_rx: RefCell<VecDeque<PacketRc>>,
800    }
801
802    impl MockHost {
803        fn new(tx_rate: RateLimit, rx_rate: RateLimit) -> Self {
804            Self {
805                router: Router::new(tx_rate, rx_rate),
806                interfaces: HashMap::new(),
807                net_rx: RefCell::new(VecDeque::new()),
808            }
809        }
810
811        fn add_device(&mut self, addr: Ipv4Addr, tx: RateLimit, rx: RateLimit) {
812            let dev = RefCell::new(MockInterface::new(addr));
813            self.interfaces.insert(addr, dev);
814            self.router.attach_packet_device(addr, tx, rx);
815        }
816
817        fn ctx<'a>(&'a self, now: EmulatedTime, boot: bool) -> RouterContext<'a, Self> {
818            RouterContext {
819                now,
820                is_bootstrapping: boot,
821                send_packet_fn: |env, pkt| env.net_rx.borrow_mut().push_back(pkt),
822                get_packet_device_fn: |env, addr| {
823                    env.interfaces
824                        .get(&addr)
825                        .map(|d| d.borrow() as Ref<'_, dyn PacketDevice>)
826                },
827                fn_arg: self,
828            }
829        }
830
831        fn enqueue(&mut self, pkt: PacketRc) {
832            self.interfaces
833                .get(pkt.src_ipv4_address().ip())
834                .unwrap()
835                .borrow_mut()
836                .enqueue(pkt)
837        }
838
839        /// Run the router repeatedly until it returns `None`, i.e. becomes idle.
840        /// Returns the final `EmulatedTime` that the router processed.
841        fn run_router_to_idle(&self, mut now: EmulatedTime) -> EmulatedTime {
842            loop {
843                let ctx = self.ctx(now, false);
844                let next = self.router.run(&ctx, Event::Wakeup);
845                match next {
846                    Some(t) => now = t, // advance simulated time
847                    None => break now,
848                }
849            }
850        }
851
852        fn route_outbound_packet(&mut self, start: EmulatedTime) -> (PacketRc, EmulatedTime) {
853            let (mut pkts, end) = self.route_outbound_packets(1, start);
854            (pkts.pop().unwrap(), end)
855        }
856
857        fn route_outbound_packets(
858            &mut self,
859            n: usize,
860            start: EmulatedTime,
861        ) -> (Vec<PacketRc>, EmulatedTime) {
862            let mut packets = Vec::new();
863
864            // Packet starts in a device (socket) queue.
865            for _ in 0..n {
866                let pkt = create_packet(TEST_ADDR, Ipv4Addr::UNSPECIFIED, PACKET_LEN);
867                self.enqueue(pkt.clone());
868                packets.push(pkt);
869            }
870
871            // Deliver the device interrupt.
872            let ctx = self.ctx(start, false);
873            let res = self.router.run(&ctx, Event::DeviceInterrupt(TEST_ADDR));
874
875            // Run the router until it's idle.
876            let end = if let Some(timeout) = res {
877                self.run_router_to_idle(timeout)
878            } else {
879                start
880            };
881            (packets, end)
882        }
883
884        fn route_inbound_packet(&mut self, start: EmulatedTime) -> (PacketRc, EmulatedTime) {
885            let (mut pkts, end) = self.route_inbound_packets(1, start);
886            (pkts.pop().unwrap(), end)
887        }
888
889        fn route_inbound_packets(
890            &mut self,
891            n: usize,
892            start: EmulatedTime,
893        ) -> (Vec<PacketRc>, EmulatedTime) {
894            let mut packets = Vec::new();
895
896            // A packet starts in the network side.
897            for _ in 0..n {
898                let pkt = create_packet(Ipv4Addr::UNSPECIFIED, TEST_ADDR, PACKET_LEN);
899                packets.push(pkt);
900            }
901
902            // Deliver the packet arrival events.
903            let ctx = self.ctx(start, false);
904
905            // Keep track of timeouts so we wake it up when requested.
906            let mut timeouts = VecDeque::new();
907
908            for pkt in packets.iter() {
909                let res = self.router.run(&ctx, Event::PacketArrival(pkt.clone()));
910                if let Some(timeout) = res {
911                    timeouts.push_back(timeout);
912                }
913            }
914
915            // Advance simulated time.
916            let mut now = start;
917
918            while let Some(next) = timeouts.pop_front() {
919                now = now.max(next);
920                let ctx = self.ctx(now, false);
921                if let Some(timeout) = self.router.run(&ctx, Event::Wakeup) {
922                    timeouts.push_back(timeout);
923                }
924            }
925
926            (packets, now)
927        }
928    }
929
930    struct MockInterface {
931        addr: Ipv4Addr,
932        // Queue of packets the device will return on `pop`.
933        tx: RefCell<VecDeque<PacketRc>>,
934        // Captured packets that were `push`ed by the router.
935        rx: RefCell<VecDeque<PacketRc>>,
936    }
937
938    impl MockInterface {
939        fn new(addr: Ipv4Addr) -> Self {
940            Self {
941                addr,
942                tx: RefCell::new(VecDeque::new()),
943                rx: RefCell::new(VecDeque::new()),
944            }
945        }
946
947        fn enqueue(&self, pkt: PacketRc) {
948            self.tx.borrow_mut().push_back(pkt);
949        }
950    }
951
952    impl PacketDevice for MockInterface {
953        fn get_address(&self) -> Ipv4Addr {
954            self.addr
955        }
956
957        fn pop(&self) -> Option<PacketRc> {
958            self.tx.borrow_mut().pop_front()
959        }
960
961        fn push(&self, packet: PacketRc) {
962            self.rx.borrow_mut().push_back(packet);
963        }
964    }
965
966    fn create_packet(src: Ipv4Addr, dst: Ipv4Addr, len: usize) -> PacketRc {
967        // The Router does not inspect port numbers so set to 0.
968        let src = SocketAddrV4::new(src, 0);
969        let dst = SocketAddrV4::new(dst, 0);
970        PacketRc::new_ipv4_udp_mock_with(src, dst, len)
971    }
972
973    #[test]
974    fn outbound_packet_is_pushed_to_network() {
975        let mut host = MockHost::new(RateLimit::Unlimited, RateLimit::Unlimited);
976        host.add_device(TEST_ADDR, RateLimit::Unlimited, RateLimit::Unlimited);
977
978        let (pkt, end) = host.route_outbound_packet(START_TIME);
979
980        // The packet should have been sent to the network.
981        assert_eq!(host.net_rx.borrow().len(), 1);
982        assert!(host.net_rx.borrow()[0] == pkt);
983
984        // No time has passed.
985        assert_eq!(end, START_TIME);
986    }
987
988    #[test]
989    fn inbound_packet_is_pushed_to_device() {
990        let mut host = MockHost::new(RateLimit::Unlimited, RateLimit::Unlimited);
991        host.add_device(TEST_ADDR, RateLimit::Unlimited, RateLimit::Unlimited);
992
993        let (pkt, end) = host.route_inbound_packet(START_TIME);
994
995        // The packet should have been received by the device.
996        let dev = host.interfaces.get(&TEST_ADDR).unwrap().borrow();
997        let queue = dev.rx.borrow();
998        assert_eq!(queue.len(), 1);
999        assert!(queue[0] == pkt);
1000
1001        // No time has passed.
1002        assert_eq!(end, START_TIME);
1003    }
1004
1005    fn assert_net_rx_after_delay(
1006        host: &MockHost,
1007        pkts: Vec<PacketRc>,
1008        start: EmulatedTime,
1009        end: EmulatedTime,
1010    ) {
1011        // The packet should have been sent to the network.
1012        let queue = host.net_rx.borrow();
1013        assert_eq!(queue.len(), pkts.len());
1014        for i in 0..pkts.len() {
1015            assert!(queue[i] == pkts[i]);
1016        }
1017
1018        // Needed some time to acquire enough tokens to send.
1019        assert!(end > start);
1020    }
1021
1022    #[test]
1023    fn outbound_isp_rate_limited() {
1024        // Use rate limit so the packet will be throttled.
1025        let mut host = MockHost::new(
1026            RateLimit::BytesPerSecond(BPS_LIMIT_LOW),
1027            RateLimit::Unlimited,
1028        );
1029        host.add_device(TEST_ADDR, RateLimit::Unlimited, RateLimit::Unlimited);
1030
1031        let (pkts, end) = host.route_outbound_packets(2, START_TIME);
1032
1033        assert_net_rx_after_delay(&host, pkts, START_TIME, end);
1034    }
1035
1036    #[test]
1037    fn outbound_device_rate_limited() {
1038        // Use rate limit so the packet will be throttled.
1039        let mut host = MockHost::new(RateLimit::Unlimited, RateLimit::Unlimited);
1040        host.add_device(
1041            TEST_ADDR,
1042            RateLimit::BytesPerSecond(BPS_LIMIT_LOW),
1043            RateLimit::Unlimited,
1044        );
1045
1046        let (pkts, end) = host.route_outbound_packets(2, START_TIME);
1047
1048        assert_net_rx_after_delay(&host, pkts, START_TIME, end);
1049    }
1050
1051    #[test]
1052    fn outbound_isp_and_device_rate_limited() {
1053        // Use rate limit so the packet will be throttled.
1054        let mut host = MockHost::new(
1055            RateLimit::BytesPerSecond(BPS_LIMIT_LOW),
1056            RateLimit::Unlimited,
1057        );
1058        // The device can send before the isp so it hits both limits.
1059        host.add_device(
1060            TEST_ADDR,
1061            RateLimit::BytesPerSecond(BPS_LIMIT_HIGH),
1062            RateLimit::Unlimited,
1063        );
1064
1065        let (pkts, end) = host.route_outbound_packets(2, START_TIME);
1066
1067        assert_net_rx_after_delay(&host, pkts, START_TIME, end);
1068    }
1069
1070    fn assert_dev_rx_after_delay(
1071        host: &MockHost,
1072        pkts: Vec<PacketRc>,
1073        start: EmulatedTime,
1074        end: EmulatedTime,
1075    ) {
1076        // The packet should have been received by the device.
1077        let dev = host.interfaces.get(&TEST_ADDR).unwrap().borrow();
1078        let queue = dev.rx.borrow();
1079        assert_eq!(queue.len(), pkts.len());
1080        for i in 0..pkts.len() {
1081            assert!(queue[i] == pkts[i]);
1082        }
1083
1084        // Needed some time to acquire enough tokens to send.
1085        assert!(end > start);
1086    }
1087
1088    #[test]
1089    fn inbound_isp_rate_limited() {
1090        // Use rate limit so the packet will be throttled.
1091        let mut host = MockHost::new(
1092            RateLimit::Unlimited,
1093            RateLimit::BytesPerSecond(BPS_LIMIT_LOW),
1094        );
1095        host.add_device(TEST_ADDR, RateLimit::Unlimited, RateLimit::Unlimited);
1096
1097        let (pkts, end) = host.route_inbound_packets(2, START_TIME);
1098
1099        assert_dev_rx_after_delay(&host, pkts, START_TIME, end);
1100    }
1101
1102    #[test]
1103    fn inbound_device_rate_limited() {
1104        // Use rate limit so the packet will be throttled.
1105        let mut host = MockHost::new(RateLimit::Unlimited, RateLimit::Unlimited);
1106        host.add_device(
1107            TEST_ADDR,
1108            RateLimit::Unlimited,
1109            RateLimit::BytesPerSecond(BPS_LIMIT_LOW),
1110        );
1111
1112        let (pkts, end) = host.route_inbound_packets(2, START_TIME);
1113
1114        assert_dev_rx_after_delay(&host, pkts, START_TIME, end);
1115    }
1116
1117    #[test]
1118    fn inbound_isp_and_device_rate_limited() {
1119        // Use rate limit so the packet will be throttled.
1120        // The isp can send before the device so it hits both limits.
1121        let mut host = MockHost::new(
1122            RateLimit::Unlimited,
1123            RateLimit::BytesPerSecond(BPS_LIMIT_HIGH),
1124        );
1125        host.add_device(
1126            TEST_ADDR,
1127            RateLimit::Unlimited,
1128            RateLimit::BytesPerSecond(BPS_LIMIT_LOW),
1129        );
1130
1131        let (pkts, end) = host.route_inbound_packets(2, START_TIME);
1132
1133        assert_dev_rx_after_delay(&host, pkts, START_TIME, end);
1134    }
1135}