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 stalls: Cell<u8>,
183 sent: Cell<u32>,
185 delivered: Cell<u32>,
186 dropped: Cell<u32>,
187 duplicated: Cell<u32>,
188}
189
190impl SimNet {
191 #[must_use]
193 pub fn new(seed: u64) -> Self {
194 Self {
195 now: Cell::new(Instant::ZERO),
196 rng: SimRng::new(seed),
197 impairment: Cell::new(Impairment::default()),
198 flight: RefCell::new(Deque::new()),
199 deadlines: RefCell::new(Deque::new()),
200 stalls: Cell::new(0),
201 sent: Cell::new(0),
202 delivered: Cell::new(0),
203 dropped: Cell::new(0),
204 duplicated: Cell::new(0),
205 }
206 }
207
208 pub fn impair(&self, impairment: Impairment) {
210 self.impairment.set(impairment);
211 }
212
213 #[must_use]
215 pub fn node(&self, index: u8) -> SimNode<'_> {
216 SimNode { net: self, index }
217 }
218
219 #[must_use]
221 pub const fn rng(&self) -> &SimRng {
222 &self.rng
223 }
224
225 #[must_use]
227 pub fn sent(&self) -> u32 {
228 self.sent.get()
229 }
230
231 #[must_use]
233 pub fn delivered(&self) -> u32 {
234 self.delivered.get()
235 }
236
237 #[must_use]
239 pub fn dropped(&self) -> u32 {
240 self.dropped.get()
241 }
242
243 #[must_use]
245 pub fn duplicated(&self) -> u32 {
246 self.duplicated.get()
247 }
248
249 #[must_use]
251 pub fn now(&self) -> Instant {
252 self.now.get()
253 }
254
255 pub fn advance_to_next_event(&self) -> bool {
266 let now = self.now.get();
267 let stalled = self.stalls.get() >= 2;
268 let mut next = Instant::MAX;
269 let times = self
270 .deadlines
271 .borrow()
272 .iter()
273 .copied()
274 .chain(self.flight.borrow().iter().map(|f| f.at))
275 .collect::<heapless::Vec<Instant, { QUEUE * 2 }>>();
276 for at in times {
277 if at < next && !(stalled && at <= now) {
278 next = at;
279 }
280 }
281 if next == Instant::MAX {
282 return false;
283 }
284 if next > now {
285 self.now.set(next);
286 self.stalls.set(0);
287 } else {
288 self.stalls.set(self.stalls.get().saturating_add(1));
289 }
290 let mut kept: Deque<Instant, QUEUE> = Deque::new();
292 let now = self.now.get();
293 for d in self.deadlines.borrow().iter() {
294 if *d > now {
295 let _ = kept.push_back(*d);
296 }
297 }
298 *self.deadlines.borrow_mut() = kept;
299 true
300 }
301
302 pub fn advance(&self, d: Duration) {
304 let target = self.now.get().saturating_add(d);
305 while self.now.get() < target {
306 let before = self.now.get();
307 if !self.advance_to_next_event() || self.now.get() > target {
308 self.now.set(target);
309 return;
310 }
311 if self.now.get() == before {
312 self.now.set(target);
314 return;
315 }
316 }
317 }
318
319 fn register_deadline(&self, at: Instant) {
320 let mut d = self.deadlines.borrow_mut();
321 if d.iter().any(|x| *x == at) {
322 return;
323 }
324 let _ = d.push_back(at);
325 }
326
327 fn enqueue(&self, from: PeerAddr, to_node: u8, data: &[u8]) -> Result<()> {
329 self.sent.set(self.sent.get().saturating_add(1));
330 let imp = self.impairment.get();
331
332 if imp.loss_percent > 0 && self.rng.chance(imp.loss_percent) {
333 self.dropped.set(self.dropped.get().saturating_add(1));
334 return Ok(());
335 }
336
337 let copies = if imp.duplicate_percent > 0 && self.rng.chance(imp.duplicate_percent) {
338 self.duplicated.set(self.duplicated.get().saturating_add(1));
339 2
340 } else {
341 1
342 };
343
344 for _ in 0..copies {
345 let jitter = if imp.jitter == Duration::ZERO {
346 Duration::ZERO
347 } else {
348 let max = u32::try_from(imp.jitter.as_micros()).unwrap_or(u32::MAX);
349 Duration::from_micros(u64::from(self.rng.below(max)))
350 };
351 let at = self
352 .now
353 .get()
354 .saturating_add(imp.latency)
355 .saturating_add(jitter);
356
357 let Some(src) = data.get(..data.len().min(MTU)) else {
358 return Err(Error::new(ErrorCode::BufferTooSmall));
359 };
360 let mut buf = [0u8; MTU];
361 let Some(dst) = buf.get_mut(..src.len()) else {
362 return Err(Error::new(ErrorCode::BufferTooSmall));
363 };
364 dst.copy_from_slice(src);
365
366 let entry = InFlight {
367 from,
368 to_node,
369 at,
370 len: src.len(),
371 data: buf,
372 };
373 if self.flight.borrow_mut().push_back(entry).is_err() {
374 self.dropped.set(self.dropped.get().saturating_add(1));
376 return Ok(());
377 }
378 self.register_deadline(at);
379 }
380 Ok(())
381 }
382
383 fn dequeue(&self, node: u8, out: &mut [u8]) -> Option<(usize, PeerAddr)> {
385 let now = self.now.get();
386 let mut flight = self.flight.borrow_mut();
387
388 let mut best: Option<(usize, Instant)> = None;
391 for (i, f) in flight.iter().enumerate() {
392 if f.to_node == node && f.at <= now && best.is_none_or(|(_, at)| f.at < at) {
393 best = Some((i, f.at));
394 }
395 }
396 let (index, _) = best?;
397
398 let mut taken = None;
400 let len = flight.len();
401 for i in 0..len {
402 let Some(entry) = flight.pop_front() else {
403 break;
404 };
405 if i == index {
406 taken = Some(entry);
407 } else {
408 let _ = flight.push_back(entry);
409 }
410 }
411 let entry = taken?;
412
413 let n = entry.len.min(out.len());
414 let (Some(dst), Some(src)) = (out.get_mut(..n), entry.data.get(..n)) else {
415 return None;
416 };
417 dst.copy_from_slice(src);
418 self.delivered.set(self.delivered.get().saturating_add(1));
419 Some((n, entry.from))
420 }
421}
422
423impl Timer for SimNet {
424 fn now(&self) -> Instant {
425 self.now.get()
426 }
427
428 fn sleep_until(&self, deadline: Instant) -> impl Future<Output = ()> {
429 self.register_deadline(deadline);
430 poll_fn(move |_| {
431 if deadline.is_elapsed_at(self.now.get()) {
432 Poll::Ready(())
433 } else {
434 self.register_deadline(deadline);
435 Poll::Pending
436 }
437 })
438 }
439}
440
441impl Clock for SimNet {
442 fn utc(&self) -> Option<u64> {
443 const Y2024: u64 = 757_382_400_000_000;
446 Some(Y2024.saturating_add(self.now.get().as_micros()))
447 }
448
449 fn granularity(&self) -> Granularity {
450 Granularity::MicrosecondsGranularity
451 }
452}
453
454impl Rng for SimNet {
455 fn fill(&self, out: &mut [u8]) -> Result<()> {
456 self.rng.fill(out)
457 }
458}
459
460#[derive(Debug, Clone, Copy)]
462pub struct SimNode<'a> {
463 net: &'a SimNet,
464 index: u8,
465}
466
467impl SimNode<'_> {
468 #[must_use]
470 pub fn addr(&self) -> PeerAddr {
471 let mut a = [0u8; 16];
472 a[0] = 0xfd;
473 a[15] = self.index;
474 PeerAddr::new(a)
475 }
476
477 #[must_use]
479 pub const fn net(&self) -> &SimNet {
480 self.net
481 }
482
483 fn node_of(addr: PeerAddr) -> Option<u8> {
484 if addr.addr[0] != 0xfd {
485 return None;
486 }
487 addr.addr.last().copied()
488 }
489}
490
491impl Udp for SimNode<'_> {
492 fn recv_from(&self, buf: &mut [u8]) -> impl Future<Output = Result<(usize, PeerAddr)>> {
493 poll_fn(move |_| match self.net.dequeue(self.index, buf) {
494 Some(v) => Poll::Ready(Ok(v)),
495 None => Poll::Pending,
496 })
497 }
498
499 fn send_to(&self, buf: &[u8], addr: PeerAddr) -> impl Future<Output = Result<()>> {
500 let result = match Self::node_of(addr) {
501 Some(to) if usize::from(to) < NODES => self.net.enqueue(self.addr(), to, buf),
502 _ => Ok(()),
505 };
506 core::future::ready(result)
507 }
508}
509
510#[derive(Debug, Default)]
512pub struct SimKv {
513 entries:
514 RefCell<heapless::Vec<(heapless::String<64>, heapless::Vec<u8, KV_VALUE>), KV_ENTRIES>>,
515}
516
517impl SimKv {
518 #[must_use]
520 pub fn new() -> Self {
521 Self::default()
522 }
523
524 #[must_use]
526 pub fn len(&self) -> usize {
527 self.entries.borrow().len()
528 }
529
530 #[must_use]
532 pub fn is_empty(&self) -> bool {
533 self.entries.borrow().is_empty()
534 }
535}
536
537impl KvStore for SimKv {
538 fn get(&self, key: &str, out: &mut [u8]) -> impl Future<Output = Result<Option<usize>>> {
539 let result = (|| {
540 let entries = self.entries.borrow();
541 let Some((_, value)) = entries.iter().find(|(k, _)| k.as_str() == key) else {
542 return Ok(None);
543 };
544 let Some(dst) = out.get_mut(..value.len()) else {
545 return Err(Error::new(ErrorCode::BufferTooSmall));
546 };
547 dst.copy_from_slice(value);
548 Ok(Some(value.len()))
549 })();
550 core::future::ready(result)
551 }
552
553 fn set(&self, key: &str, value: &[u8]) -> impl Future<Output = Result<()>> {
554 let result = (|| {
555 let mut entries = self.entries.borrow_mut();
556 let stored =
557 heapless::Vec::from_slice(value).map_err(|_| Error::new(ErrorCode::NoSpace))?;
558 if let Some((_, slot)) = entries.iter_mut().find(|(k, _)| k.as_str() == key) {
559 *slot = stored;
560 return Ok(());
561 }
562 let name =
563 heapless::String::try_from(key).map_err(|_| Error::new(ErrorCode::NoSpace))?;
564 entries
565 .push((name, stored))
566 .map_err(|_| Error::new(ErrorCode::NoSpace))
567 })();
568 core::future::ready(result)
569 }
570
571 fn remove(&self, key: &str) -> impl Future<Output = Result<()>> {
572 let mut entries = self.entries.borrow_mut();
573 if let Some(i) = entries.iter().position(|(k, _)| k.as_str() == key) {
574 entries.swap_remove(i);
575 }
576 core::future::ready(Ok(()))
577 }
578
579 fn remove_prefix(&self, prefix: &str) -> impl Future<Output = Result<()>> {
580 let mut entries = self.entries.borrow_mut();
581 entries.retain(|(k, _)| !k.as_str().starts_with(prefix));
582 core::future::ready(Ok(()))
583 }
584}
585
586#[allow(clippy::panic)]
599pub fn block_on<F: Future>(net: &SimNet, fut: F) -> F::Output {
600 let waker = core::task::Waker::noop();
601 let mut cx = core::task::Context::from_waker(waker);
602 let mut fut = core::pin::pin!(fut);
603 loop {
604 match fut.as_mut().poll(&mut cx) {
605 Poll::Ready(v) => return v,
606 Poll::Pending => {
607 assert!(
608 net.advance_to_next_event(),
609 "simulated deadlock: the future is pending and nothing is scheduled"
610 );
611 }
612 }
613 }
614}
615
616#[cfg(test)]
617#[allow(clippy::arithmetic_side_effects, clippy::indexing_slicing)]
618mod tests {
619 use super::*;
620
621 #[test]
622 fn a_datagram_arrives() {
623 let net = SimNet::new(1);
624 let a = net.node(1);
625 let b = net.node(2);
626 block_on(&net, async {
627 a.send_to(b"hello", b.addr()).await.unwrap();
628 let mut buf = [0u8; 32];
629 let (n, from) = b.recv_from(&mut buf).await.unwrap();
630 assert_eq!(&buf[..n], b"hello");
631 assert_eq!(from, a.addr());
632 });
633 assert_eq!(net.delivered(), 1);
634 }
635
636 #[test]
637 fn virtual_time_costs_nothing() {
638 let net = SimNet::new(1);
639 let start = Timer::now(&net);
640 block_on(&net, async {
641 net.sleep(Duration::from_secs(3600)).await;
642 });
643 assert_eq!(
644 Timer::now(&net).saturating_duration_since(start),
645 Duration::from_secs(3600)
646 );
647 }
648
649 #[test]
650 fn loss_is_deterministic_for_a_seed() {
651 fn run(seed: u64) -> u32 {
652 let net = SimNet::new(seed);
653 net.impair(Impairment::lossy(50));
654 let a = net.node(1);
655 let b = net.node(2);
656 for _ in 0..100 {
657 let _ = block_on(&net, a.send_to(b"x", b.addr()));
658 }
659 net.dropped()
660 }
661 let first = run(7);
662 assert_eq!(first, run(7), "same seed, same drops");
663 assert!(first > 20 && first < 80, "about half of 100, got {first}");
664 }
665
666 #[test]
667 fn jitter_reorders() {
668 let net = SimNet::new(3);
669 net.impair(Impairment::jittery(
670 Duration::from_millis(10),
671 Duration::from_millis(50),
672 ));
673 let a = net.node(1);
674 let b = net.node(2);
675 block_on(&net, async {
676 for i in 0u8..8 {
677 a.send_to(&[i], b.addr()).await.unwrap();
678 }
679 });
680 let mut order = heapless::Vec::<u8, 8>::new();
681 block_on(&net, async {
682 for _ in 0..8 {
683 let mut buf = [0u8; 4];
684 let (n, _) = b.recv_from(&mut buf).await.unwrap();
685 assert_eq!(n, 1);
686 let _ = order.push(buf[0]);
687 }
688 });
689 assert_eq!(order.len(), 8, "everything arrives");
690 assert_ne!(&order[..], &[0, 1, 2, 3, 4, 5, 6, 7], "but not in order");
691 }
692
693 #[test]
694 fn duplicates_are_delivered_twice() {
695 let net = SimNet::new(5);
696 net.impair(Impairment {
697 duplicate_percent: 100,
698 ..Impairment::default()
699 });
700 let a = net.node(1);
701 let b = net.node(2);
702 block_on(&net, async {
703 a.send_to(b"x", b.addr()).await.unwrap();
704 let mut buf = [0u8; 4];
705 b.recv_from(&mut buf).await.unwrap();
706 b.recv_from(&mut buf).await.unwrap();
707 });
708 assert_eq!(net.delivered(), 2);
709 }
710
711 #[test]
712 fn the_key_value_store_round_trips() {
713 let net = SimNet::new(1);
714 let kv = SimKv::new();
715 block_on(&net, async {
716 let mut buf = [0u8; 32];
717 assert_eq!(kv.get("fabrics", &mut buf).await.unwrap(), None);
718 kv.set("fabrics", b"abc").await.unwrap();
719 assert_eq!(kv.get("fabrics", &mut buf).await.unwrap(), Some(3));
720 assert_eq!(&buf[..3], b"abc");
721 kv.set("fabrics", b"de").await.unwrap();
722 assert_eq!(kv.get("fabrics", &mut buf).await.unwrap(), Some(2));
723 kv.set("app/x", b"1").await.unwrap();
724 kv.remove_prefix("app/").await.unwrap();
725 assert_eq!(kv.get("app/x", &mut buf).await.unwrap(), None);
726 assert_eq!(kv.len(), 1);
727 kv.remove("fabrics").await.unwrap();
728 assert!(kv.is_empty());
729 });
730 }
731
732 #[test]
733 fn a_too_small_buffer_is_an_error() {
734 let net = SimNet::new(1);
735 let kv = SimKv::new();
736 block_on(&net, async {
737 kv.set("k", b"0123456789").await.unwrap();
738 let mut small = [0u8; 4];
739 assert_eq!(
740 kv.get("k", &mut small).await.unwrap_err().code(),
741 ErrorCode::BufferTooSmall
742 );
743 });
744 }
745}