1use core::cell::{Cell, RefCell};
38use core::future::{Future, poll_fn};
39use core::task::Poll;
40
41use heapless::Deque;
42
43use super::{Clock, Duration, Granularity, Instant, KvStore, PeerAddr, Rng, Timer, Udp};
44use crate::error::{Error, ErrorCode, Result};
45
46const QUEUE: usize = 32;
48const MTU: usize = crate::config::MAX_UDP_MESSAGE;
50const NODES: usize = 8;
52const KV_ENTRIES: usize = 32;
54const KV_VALUE: usize = 1024;
56
57#[derive(Debug)]
64pub struct SimRng {
65 state: Cell<u64>,
66}
67
68impl SimRng {
69 #[must_use]
71 pub const fn new(seed: u64) -> Self {
72 Self {
73 state: Cell::new(if seed == 0 {
74 0x9E37_79B9_7F4A_7C15
75 } else {
76 seed
77 }),
78 }
79 }
80
81 pub fn next(&self) -> u64 {
83 let mut x = self.state.get();
84 x ^= x >> 12;
85 x ^= x << 25;
86 x ^= x >> 27;
87 self.state.set(x);
88 x.wrapping_mul(0x2545_F491_4F6C_DD1D)
89 }
90
91 pub fn below(&self, bound: u32) -> u32 {
93 self.next()
96 .checked_rem(u64::from(bound))
97 .and_then(|v| u32::try_from(v).ok())
98 .unwrap_or(0)
99 }
100
101 pub fn chance(&self, percent: u8) -> bool {
103 self.below(100) < u32::from(percent)
104 }
105}
106
107impl Rng for SimRng {
108 fn fill(&self, out: &mut [u8]) -> Result<()> {
109 for chunk in out.chunks_mut(8) {
110 let bytes = self.next().to_le_bytes();
111 for (dst, src) in chunk.iter_mut().zip(bytes.iter()) {
112 *dst = *src;
113 }
114 }
115 Ok(())
116 }
117}
118
119#[derive(Debug, Clone, Copy, Default)]
124pub struct Impairment {
125 pub loss_percent: u8,
127 pub duplicate_percent: u8,
129 pub latency: Duration,
131 pub jitter: Duration,
133}
134
135impl Impairment {
136 #[must_use]
138 pub const fn lossy(loss_percent: u8) -> Self {
139 Self {
140 loss_percent,
141 duplicate_percent: 0,
142 latency: Duration::ZERO,
143 jitter: Duration::ZERO,
144 }
145 }
146
147 #[must_use]
149 pub const fn jittery(latency: Duration, jitter: Duration) -> Self {
150 Self {
151 loss_percent: 0,
152 duplicate_percent: 0,
153 latency,
154 jitter,
155 }
156 }
157}
158
159#[derive(Debug)]
161struct InFlight {
162 from: PeerAddr,
163 to_node: u8,
164 at: Instant,
165 len: usize,
166 data: [u8; MTU],
167}
168
169#[derive(Debug)]
171pub struct SimNet {
172 now: Cell<Instant>,
173 rng: SimRng,
174 impairment: Cell<Impairment>,
175 flight: RefCell<Deque<InFlight, QUEUE>>,
178 deadlines: RefCell<Deque<Instant, QUEUE>>,
180 sent: Cell<u32>,
182 delivered: Cell<u32>,
183 dropped: Cell<u32>,
184 duplicated: Cell<u32>,
185}
186
187impl SimNet {
188 #[must_use]
190 pub fn new(seed: u64) -> Self {
191 Self {
192 now: Cell::new(Instant::ZERO),
193 rng: SimRng::new(seed),
194 impairment: Cell::new(Impairment::default()),
195 flight: RefCell::new(Deque::new()),
196 deadlines: RefCell::new(Deque::new()),
197 sent: Cell::new(0),
198 delivered: Cell::new(0),
199 dropped: Cell::new(0),
200 duplicated: Cell::new(0),
201 }
202 }
203
204 pub fn impair(&self, impairment: Impairment) {
206 self.impairment.set(impairment);
207 }
208
209 #[must_use]
211 pub fn node(&self, index: u8) -> SimNode<'_> {
212 SimNode { net: self, index }
213 }
214
215 #[must_use]
217 pub const fn rng(&self) -> &SimRng {
218 &self.rng
219 }
220
221 #[must_use]
223 pub fn sent(&self) -> u32 {
224 self.sent.get()
225 }
226
227 #[must_use]
229 pub fn delivered(&self) -> u32 {
230 self.delivered.get()
231 }
232
233 #[must_use]
235 pub fn dropped(&self) -> u32 {
236 self.dropped.get()
237 }
238
239 #[must_use]
241 pub fn duplicated(&self) -> u32 {
242 self.duplicated.get()
243 }
244
245 #[must_use]
247 pub fn now(&self) -> Instant {
248 self.now.get()
249 }
250
251 pub fn advance_to_next_event(&self) -> bool {
258 let mut next = Instant::MAX;
259 for d in self.deadlines.borrow().iter() {
260 if *d < next {
261 next = *d;
262 }
263 }
264 for f in self.flight.borrow().iter() {
265 if f.at < next {
266 next = f.at;
267 }
268 }
269 if next == Instant::MAX {
270 return false;
271 }
272 if next > self.now.get() {
273 self.now.set(next);
274 }
275 let mut kept: Deque<Instant, QUEUE> = Deque::new();
277 let now = self.now.get();
278 for d in self.deadlines.borrow().iter() {
279 if *d > now {
280 let _ = kept.push_back(*d);
281 }
282 }
283 *self.deadlines.borrow_mut() = kept;
284 true
285 }
286
287 pub fn advance(&self, d: Duration) {
289 let target = self.now.get().saturating_add(d);
290 while self.now.get() < target {
291 let before = self.now.get();
292 if !self.advance_to_next_event() || self.now.get() > target {
293 self.now.set(target);
294 return;
295 }
296 if self.now.get() == before {
297 self.now.set(target);
299 return;
300 }
301 }
302 }
303
304 fn register_deadline(&self, at: Instant) {
305 let mut d = self.deadlines.borrow_mut();
306 if d.iter().any(|x| *x == at) {
307 return;
308 }
309 let _ = d.push_back(at);
310 }
311
312 fn enqueue(&self, from: PeerAddr, to_node: u8, data: &[u8]) -> Result<()> {
314 self.sent.set(self.sent.get().saturating_add(1));
315 let imp = self.impairment.get();
316
317 if imp.loss_percent > 0 && self.rng.chance(imp.loss_percent) {
318 self.dropped.set(self.dropped.get().saturating_add(1));
319 return Ok(());
320 }
321
322 let copies = if imp.duplicate_percent > 0 && self.rng.chance(imp.duplicate_percent) {
323 self.duplicated.set(self.duplicated.get().saturating_add(1));
324 2
325 } else {
326 1
327 };
328
329 for _ in 0..copies {
330 let jitter = if imp.jitter == Duration::ZERO {
331 Duration::ZERO
332 } else {
333 let max = u32::try_from(imp.jitter.as_micros()).unwrap_or(u32::MAX);
334 Duration::from_micros(u64::from(self.rng.below(max)))
335 };
336 let at = self
337 .now
338 .get()
339 .saturating_add(imp.latency)
340 .saturating_add(jitter);
341
342 let Some(src) = data.get(..data.len().min(MTU)) else {
343 return Err(Error::new(ErrorCode::BufferTooSmall));
344 };
345 let mut buf = [0u8; MTU];
346 let Some(dst) = buf.get_mut(..src.len()) else {
347 return Err(Error::new(ErrorCode::BufferTooSmall));
348 };
349 dst.copy_from_slice(src);
350
351 let entry = InFlight {
352 from,
353 to_node,
354 at,
355 len: src.len(),
356 data: buf,
357 };
358 if self.flight.borrow_mut().push_back(entry).is_err() {
359 self.dropped.set(self.dropped.get().saturating_add(1));
361 return Ok(());
362 }
363 self.register_deadline(at);
364 }
365 Ok(())
366 }
367
368 fn dequeue(&self, node: u8, out: &mut [u8]) -> Option<(usize, PeerAddr)> {
370 let now = self.now.get();
371 let mut flight = self.flight.borrow_mut();
372
373 let mut best: Option<(usize, Instant)> = None;
376 for (i, f) in flight.iter().enumerate() {
377 if f.to_node == node && f.at <= now && best.is_none_or(|(_, at)| f.at < at) {
378 best = Some((i, f.at));
379 }
380 }
381 let (index, _) = best?;
382
383 let mut taken = None;
385 let len = flight.len();
386 for i in 0..len {
387 let Some(entry) = flight.pop_front() else {
388 break;
389 };
390 if i == index {
391 taken = Some(entry);
392 } else {
393 let _ = flight.push_back(entry);
394 }
395 }
396 let entry = taken?;
397
398 let n = entry.len.min(out.len());
399 let (Some(dst), Some(src)) = (out.get_mut(..n), entry.data.get(..n)) else {
400 return None;
401 };
402 dst.copy_from_slice(src);
403 self.delivered.set(self.delivered.get().saturating_add(1));
404 Some((n, entry.from))
405 }
406}
407
408impl Timer for SimNet {
409 fn now(&self) -> Instant {
410 self.now.get()
411 }
412
413 fn sleep_until(&self, deadline: Instant) -> impl Future<Output = ()> {
414 self.register_deadline(deadline);
415 poll_fn(move |_| {
416 if deadline.is_elapsed_at(self.now.get()) {
417 Poll::Ready(())
418 } else {
419 self.register_deadline(deadline);
420 Poll::Pending
421 }
422 })
423 }
424}
425
426impl Clock for SimNet {
427 fn utc(&self) -> Option<u64> {
428 const Y2024: u64 = 757_382_400_000_000;
431 Some(Y2024.saturating_add(self.now.get().as_micros()))
432 }
433
434 fn granularity(&self) -> Granularity {
435 Granularity::MicrosecondsGranularity
436 }
437}
438
439impl Rng for SimNet {
440 fn fill(&self, out: &mut [u8]) -> Result<()> {
441 self.rng.fill(out)
442 }
443}
444
445#[derive(Debug, Clone, Copy)]
447pub struct SimNode<'a> {
448 net: &'a SimNet,
449 index: u8,
450}
451
452impl SimNode<'_> {
453 #[must_use]
455 pub fn addr(&self) -> PeerAddr {
456 let mut a = [0u8; 16];
457 a[0] = 0xfd;
458 a[15] = self.index;
459 PeerAddr::new(a)
460 }
461
462 #[must_use]
464 pub const fn net(&self) -> &SimNet {
465 self.net
466 }
467
468 fn node_of(addr: PeerAddr) -> Option<u8> {
469 if addr.addr[0] != 0xfd {
470 return None;
471 }
472 addr.addr.last().copied()
473 }
474}
475
476impl Udp for SimNode<'_> {
477 fn recv_from(&self, buf: &mut [u8]) -> impl Future<Output = Result<(usize, PeerAddr)>> {
478 poll_fn(move |_| match self.net.dequeue(self.index, buf) {
479 Some(v) => Poll::Ready(Ok(v)),
480 None => Poll::Pending,
481 })
482 }
483
484 fn send_to(&self, buf: &[u8], addr: PeerAddr) -> impl Future<Output = Result<()>> {
485 let result = match Self::node_of(addr) {
486 Some(to) if usize::from(to) < NODES => self.net.enqueue(self.addr(), to, buf),
487 _ => Ok(()),
490 };
491 core::future::ready(result)
492 }
493}
494
495#[derive(Debug, Default)]
497pub struct SimKv {
498 entries:
499 RefCell<heapless::Vec<(heapless::String<64>, heapless::Vec<u8, KV_VALUE>), KV_ENTRIES>>,
500}
501
502impl SimKv {
503 #[must_use]
505 pub fn new() -> Self {
506 Self::default()
507 }
508
509 #[must_use]
511 pub fn len(&self) -> usize {
512 self.entries.borrow().len()
513 }
514
515 #[must_use]
517 pub fn is_empty(&self) -> bool {
518 self.entries.borrow().is_empty()
519 }
520}
521
522impl KvStore for SimKv {
523 fn get(&self, key: &str, out: &mut [u8]) -> impl Future<Output = Result<Option<usize>>> {
524 let result = (|| {
525 let entries = self.entries.borrow();
526 let Some((_, value)) = entries.iter().find(|(k, _)| k.as_str() == key) else {
527 return Ok(None);
528 };
529 let Some(dst) = out.get_mut(..value.len()) else {
530 return Err(Error::new(ErrorCode::BufferTooSmall));
531 };
532 dst.copy_from_slice(value);
533 Ok(Some(value.len()))
534 })();
535 core::future::ready(result)
536 }
537
538 fn set(&self, key: &str, value: &[u8]) -> impl Future<Output = Result<()>> {
539 let result = (|| {
540 let mut entries = self.entries.borrow_mut();
541 let stored =
542 heapless::Vec::from_slice(value).map_err(|_| Error::new(ErrorCode::NoSpace))?;
543 if let Some((_, slot)) = entries.iter_mut().find(|(k, _)| k.as_str() == key) {
544 *slot = stored;
545 return Ok(());
546 }
547 let name =
548 heapless::String::try_from(key).map_err(|_| Error::new(ErrorCode::NoSpace))?;
549 entries
550 .push((name, stored))
551 .map_err(|_| Error::new(ErrorCode::NoSpace))
552 })();
553 core::future::ready(result)
554 }
555
556 fn remove(&self, key: &str) -> impl Future<Output = Result<()>> {
557 let mut entries = self.entries.borrow_mut();
558 if let Some(i) = entries.iter().position(|(k, _)| k.as_str() == key) {
559 entries.swap_remove(i);
560 }
561 core::future::ready(Ok(()))
562 }
563
564 fn remove_prefix(&self, prefix: &str) -> impl Future<Output = Result<()>> {
565 let mut entries = self.entries.borrow_mut();
566 entries.retain(|(k, _)| !k.as_str().starts_with(prefix));
567 core::future::ready(Ok(()))
568 }
569}
570
571#[allow(clippy::panic)]
584pub fn block_on<F: Future>(net: &SimNet, fut: F) -> F::Output {
585 let waker = core::task::Waker::noop();
586 let mut cx = core::task::Context::from_waker(waker);
587 let mut fut = core::pin::pin!(fut);
588 loop {
589 match fut.as_mut().poll(&mut cx) {
590 Poll::Ready(v) => return v,
591 Poll::Pending => {
592 assert!(
593 net.advance_to_next_event(),
594 "simulated deadlock: the future is pending and nothing is scheduled"
595 );
596 }
597 }
598 }
599}
600
601#[cfg(test)]
602#[allow(clippy::arithmetic_side_effects, clippy::indexing_slicing)]
603mod tests {
604 use super::*;
605
606 #[test]
607 fn a_datagram_arrives() {
608 let net = SimNet::new(1);
609 let a = net.node(1);
610 let b = net.node(2);
611 block_on(&net, async {
612 a.send_to(b"hello", b.addr()).await.unwrap();
613 let mut buf = [0u8; 32];
614 let (n, from) = b.recv_from(&mut buf).await.unwrap();
615 assert_eq!(&buf[..n], b"hello");
616 assert_eq!(from, a.addr());
617 });
618 assert_eq!(net.delivered(), 1);
619 }
620
621 #[test]
622 fn virtual_time_costs_nothing() {
623 let net = SimNet::new(1);
624 let start = Timer::now(&net);
625 block_on(&net, async {
626 net.sleep(Duration::from_secs(3600)).await;
627 });
628 assert_eq!(
629 Timer::now(&net).saturating_duration_since(start),
630 Duration::from_secs(3600)
631 );
632 }
633
634 #[test]
635 fn loss_is_deterministic_for_a_seed() {
636 fn run(seed: u64) -> u32 {
637 let net = SimNet::new(seed);
638 net.impair(Impairment::lossy(50));
639 let a = net.node(1);
640 let b = net.node(2);
641 for _ in 0..100 {
642 let _ = block_on(&net, a.send_to(b"x", b.addr()));
643 }
644 net.dropped()
645 }
646 let first = run(7);
647 assert_eq!(first, run(7), "same seed, same drops");
648 assert!(first > 20 && first < 80, "about half of 100, got {first}");
649 }
650
651 #[test]
652 fn jitter_reorders() {
653 let net = SimNet::new(3);
654 net.impair(Impairment::jittery(
655 Duration::from_millis(10),
656 Duration::from_millis(50),
657 ));
658 let a = net.node(1);
659 let b = net.node(2);
660 block_on(&net, async {
661 for i in 0u8..8 {
662 a.send_to(&[i], b.addr()).await.unwrap();
663 }
664 });
665 let mut order = heapless::Vec::<u8, 8>::new();
666 block_on(&net, async {
667 for _ in 0..8 {
668 let mut buf = [0u8; 4];
669 let (n, _) = b.recv_from(&mut buf).await.unwrap();
670 assert_eq!(n, 1);
671 let _ = order.push(buf[0]);
672 }
673 });
674 assert_eq!(order.len(), 8, "everything arrives");
675 assert_ne!(&order[..], &[0, 1, 2, 3, 4, 5, 6, 7], "but not in order");
676 }
677
678 #[test]
679 fn duplicates_are_delivered_twice() {
680 let net = SimNet::new(5);
681 net.impair(Impairment {
682 duplicate_percent: 100,
683 ..Impairment::default()
684 });
685 let a = net.node(1);
686 let b = net.node(2);
687 block_on(&net, async {
688 a.send_to(b"x", b.addr()).await.unwrap();
689 let mut buf = [0u8; 4];
690 b.recv_from(&mut buf).await.unwrap();
691 b.recv_from(&mut buf).await.unwrap();
692 });
693 assert_eq!(net.delivered(), 2);
694 }
695
696 #[test]
697 fn the_key_value_store_round_trips() {
698 let net = SimNet::new(1);
699 let kv = SimKv::new();
700 block_on(&net, async {
701 let mut buf = [0u8; 32];
702 assert_eq!(kv.get("fabrics", &mut buf).await.unwrap(), None);
703 kv.set("fabrics", b"abc").await.unwrap();
704 assert_eq!(kv.get("fabrics", &mut buf).await.unwrap(), Some(3));
705 assert_eq!(&buf[..3], b"abc");
706 kv.set("fabrics", b"de").await.unwrap();
707 assert_eq!(kv.get("fabrics", &mut buf).await.unwrap(), Some(2));
708 kv.set("app/x", b"1").await.unwrap();
709 kv.remove_prefix("app/").await.unwrap();
710 assert_eq!(kv.get("app/x", &mut buf).await.unwrap(), None);
711 assert_eq!(kv.len(), 1);
712 kv.remove("fabrics").await.unwrap();
713 assert!(kv.is_empty());
714 });
715 }
716
717 #[test]
718 fn a_too_small_buffer_is_an_error() {
719 let net = SimNet::new(1);
720 let kv = SimKv::new();
721 block_on(&net, async {
722 kv.set("k", b"0123456789").await.unwrap();
723 let mut small = [0u8; 4];
724 assert_eq!(
725 kv.get("k", &mut small).await.unwrap_err().code(),
726 ErrorCode::BufferTooSmall
727 );
728 });
729 }
730}