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}